titles and image algorithm comparison computer-vision

and - image alt text



Comparación de imágenes-algoritmo rápido (8)

Estoy buscando crear una tabla base de imágenes y luego comparar cualquier imagen nueva con eso para determinar si la nueva imagen es un duplicado exacto (o cercano) de la base.

Por ejemplo: si desea reducir el almacenamiento de la misma imagen 100 veces, puede almacenar una copia de la misma y proporcionarle enlaces de referencia. Cuando se ingresa una nueva imagen, usted quiere compararla con una imagen existente para asegurarse de que no sea un duplicado ... ¿ideas?

Una idea mía fue reducir a una pequeña miniatura y luego seleccionar aleatoriamente ubicaciones de 100 píxeles y comparar.

A continuación hay tres enfoques para resolver este problema (y hay muchos otros).

  • El primero es un enfoque estándar en visión computacional, coincidencia de puntos clave. Esto puede requerir algunos conocimientos previos para implementar, y puede ser lento.

  • El segundo método utiliza solo el procesamiento de imágenes elementales, y es potencialmente más rápido que el primer enfoque, y su implementación es sencilla. Sin embargo, lo que gana en comprensibilidad, carece de robustez: la coincidencia falla en imágenes a escala, rotadas o decoloradas.

  • El tercer método es rápido y robusto, pero es potencialmente el más difícil de implementar.

Coincidencia de puntos clave

Mejor que escoger 100 puntos al azar es escoger 100 puntos importantes . Ciertas partes de una imagen tienen más información que otras (especialmente en los bordes y esquinas), y estas son las que querrá usar para la coincidencia inteligente de imágenes. Google " extracción de puntos clave " y " coincidencia de puntos clave " y encontrará bastantes trabajos académicos sobre el tema. En estos días, los puntos clave SIFT son posiblemente los más populares, ya que pueden coincidir con imágenes en diferentes escalas, rotaciones e iluminación. Algunas implementaciones de SIFT se pueden encontrar here .

Una desventaja de la coincidencia de puntos clave es el tiempo de ejecución de una implementación ingenua: O (n ^ 2m), donde n es el número de puntos clave en cada imagen ym es el número de imágenes en la base de datos. Algunos algoritmos inteligentes pueden encontrar la coincidencia más cercana más rápidamente, como quadtrees o particiones de espacio binario.

Solución alternativa: método de histograma

Otra solución menos robusta pero potencialmente más rápida es crear histogramas de características para cada imagen y elegir la imagen con el histograma más cercano al histograma de la imagen de entrada. Implementé esto como una licenciatura, y usamos 3 histogramas de color (rojo, verde y azul), y dos histogramas de textura, dirección y escala. Daré los detalles a continuación, pero debo tener en cuenta que esto solo funcionó bien para hacer coincidir las imágenes MUY similar a las imágenes de la base de datos. Las imágenes redimensionadas, rotadas o descoloridas pueden fallar con este método, pero pequeños cambios como el recorte no romperán el algoritmo

El cálculo de los histogramas de color es sencillo: simplemente seleccione el rango para sus grupos de histogramas y, para cada rango, calcule la cantidad de píxeles con un color en ese rango. Por ejemplo, considere el histograma "verde" y suponga que seleccionamos 4 cubos para nuestro histograma: 0-63, 64-127, 128-191 y 192-255. Luego, para cada píxel, observamos el valor verde y agregamos un recuento al grupo apropiado. Cuando hayamos terminado de contar, dividimos el total de cada grupo por el número de píxeles en toda la imagen para obtener un histograma normalizado para el canal verde.

Para el histograma de la dirección de la textura, comenzamos realizando la detección de bordes en la imagen. Cada punto de borde tiene un vector normal que apunta en la dirección perpendicular al borde. Cuantificamos el ángulo del vector normal en uno de 6 cubos entre 0 y PI (ya que los bordes tienen simetría de 180 grados, convertimos los ángulos entre -PI y 0 para que estén entre 0 y PI). Después de calcular el número de puntos de borde en cada dirección, tenemos un histograma no normalizado que representa la dirección de la textura, que normalizamos al dividir cada grupo por el número total de puntos de borde en la imagen.

Para calcular el histograma de escala de textura, para cada punto de borde, medimos la distancia al siguiente punto de borde más cercano con la misma dirección. Por ejemplo, si el punto de borde A tiene una dirección de 45 grados, el algoritmo camina en esa dirección hasta que encuentra otro punto de borde con una dirección de 45 grados (o dentro de una desviación razonable). Después de calcular esta distancia para cada punto de borde, volcamos esos valores en un histograma y lo normalizamos dividiendo por el número total de puntos de borde.

Ahora tienes 5 histogramas para cada imagen. Para comparar dos imágenes, toma el valor absoluto de la diferencia entre cada grupo de histogramas y luego suma estos valores. Por ejemplo, para comparar las imágenes A y B, deberíamos calcular

|A.green_histogram.bucket_1 - B.green_histogram.bucket_1|

para cada grupo en el histograma verde, y repita para los otros histogramas, y luego sume todos los resultados. Cuanto menor sea el resultado, mejor será el partido. Repita para todas las imágenes en la base de datos, y la coincidencia con el resultado más pequeño gana. Probablemente querrá tener un umbral, por encima del cual el algoritmo concluye que no se encontró ninguna coincidencia.

Tercera elección - Puntos clave + árboles de decisión

Un tercer enfoque que probablemente sea mucho más rápido que los otros dos es el uso de bosques de texto semánticos (PDF). Esto implica extraer puntos clave simples y usar un árbol de decisión de colección para clasificar la imagen. Esto es más rápido que la simple coincidencia de puntos clave SIFT, porque evita el costoso proceso de coincidencia, y los puntos clave son mucho más simples que SIFT, por lo que la extracción de puntos clave es mucho más rápida. Sin embargo, conserva la invariancia del método SIFT a la rotación, la escala y la iluminación, una característica importante de la que carecía el método del histograma.

Actualización :

Mi error: el documento Semantic Texton Forests no se refiere específicamente a la coincidencia de imágenes, sino al etiquetado de regiones. El artículo original que hace coincidir es este: Reconocimiento de puntos clave mediante árboles aleatorios . Además, los documentos a continuación continúan desarrollando las ideas y representan el estado del arte (c. 2010):

Como señaló Cartman, puede utilizar cualquier tipo de valor hash para encontrar duplicados exactos.

Un punto de partida para encontrar imágenes cercanas podría estar here . Esta es una herramienta utilizada por las compañías de CG para verificar si las imágenes renovadas siguen mostrando esencialmente la misma escena.

Creo que reducir el tamaño de la imagen a un tamaño casi de icono, digamos 48x48, luego convertir a escala de grises, luego tomar la diferencia entre píxeles o Delta, debería funcionar bien. Debido a que estamos comparando el cambio en el color de los píxeles, en lugar del color de los píxeles reales, no importará si la imagen es ligeramente más clara o más oscura. Los cambios grandes serán importantes ya que los píxeles que se vuelven demasiado claros / oscuros se perderán. Puede aplicar esto en una fila, o tantas como desee para aumentar la precisión. A lo sumo, tendría que hacer 47x47 = 2,209 restas para formar una clave comparable.

El mejor método que conozco es usar un hash perceptivo. Parece que hay una buena implementación de código abierto de tal hash disponible en:

http://phash.org/

La idea principal es que cada imagen se reduzca a un pequeño código hash o "huella digital" al identificar las características más destacadas en el archivo de imagen original y al hacer una representación compacta de esas características (en lugar de incluir directamente los datos de la imagen). Esto significa que la tasa de falsos positivos se reduce mucho con respecto a un enfoque simplista, como reducir las imágenes a una imagen diminuta del tamaño de una huella digital y comparar huellas digitales.

phash ofrece varios tipos de hash y puede utilizarse para imágenes, audio o video.

Elegir 100 puntos aleatorios podría significar que imágenes similares (o en ocasiones incluso distintas) se marcarían como iguales, lo que supongo que no es lo que quieres. Los hashes MD5 no funcionarían si las imágenes fueran de formatos diferentes (png, jpeg, etc.), tuvieran tamaños diferentes o tuvieran metadatos diferentes. Reducir todas las imágenes a un tamaño más pequeño es una buena apuesta, hacer una comparación de píxel por píxel no debería tomar mucho tiempo, siempre y cuando se use una buena biblioteca de imágenes / lenguaje rápido, y el tamaño sea lo suficientemente pequeño.

Puede intentar que sean pequeños, y si son iguales, realice otra comparación en un tamaño más grande; podría ser una buena combinación de velocidad y precisión ...

Si tiene una gran cantidad de imágenes, observe un filtro Bloom , que utiliza múltiples hashes para obtener un resultado probabilístico pero eficiente. Si el número de imágenes no es enorme, entonces un hash criptográfico como md5 debería ser suficiente.

Tengo una idea que puede funcionar y es muy probable que sea muy rápida. Puede submuestrear una imagen para decir una resolución de 80x60 o comparable, y convertirla a escala de grises (después del submuestreo será más rápido). Procesa las dos imágenes que quieras comparar. Luego ejecute la suma normalizada de las diferencias cuadradas entre dos imágenes (la imagen de consulta y cada una desde la base de datos), o incluso mejor, la Correlación cruzada normalizada, que da una respuesta más cercana a 1, si ambas imágenes son similares. Luego, si las imágenes son similares, puede proceder a técnicas más sofisticadas para verificar que se trata de las mismas imágenes. Obviamente, este algoritmo es lineal en términos de cantidad de imágenes en su base de datos, por lo que aunque será muy rápido hasta 10000 imágenes por segundo en el hardware moderno. Si necesita invariancia a la rotación, entonces se puede calcular un gradiente dominante para esta imagen pequeña, y luego se puede rotar todo el sistema de coordenadas a la orientación canónica, aunque esto será más lento. Y no, no hay invarianza a escala aquí.

Si desea algo más general o el uso de grandes bases de datos (millones de imágenes), entonces debe analizar la teoría de la recuperación de imágenes (en los últimos 5 años apareció una gran cantidad de artículos). Hay algunos punteros en otras respuestas. Pero podría ser una exageración, y el enfoque de histograma sugerido hará el trabajo. Aunque creo que la combinación de muchos enfoques rápidos diferentes será aún mejor.

Esta publicación fue el punto de partida de mi solución, muchas buenas ideas aquí, así que pensé en compartir mis resultados. La idea principal es que he encontrado una manera de sortear la lentitud de la coincidencia de imágenes basada en puntos clave mediante el aprovechamiento de la velocidad de phash.

Para la solución general, lo mejor es emplear varias estrategias. Cada algoritmo es el más adecuado para ciertos tipos de transformaciones de imagen y puede aprovechar eso.

En la parte superior, los algoritmos más rápidos; En la parte inferior la más lenta (aunque más precisa). Puede omitir los lentos si se encuentra una buena coincidencia en el nivel más rápido.

  • basado en hash de archivos (md5, sha1, etc.) para duplicados exactos
  • hash perceptivo (phash) para imágenes reescaladas
  • basado en características (SIFT) para imágenes modificadas

Estoy teniendo muy buenos resultados con phash. La precisión es buena para imágenes reescaladas. No es bueno para imágenes modificadas (perceptualmente) (recortadas, rotadas, reflejadas, etc.). Para lidiar con la velocidad de hash debemos emplear un caché de disco / base de datos para mantener los hashes para el pajar.

Lo realmente bueno de phash es que una vez que construye su base de datos hash (que para mí es de aproximadamente 1000 imágenes / seg), las búsquedas pueden ser muy, muy rápidas, en particular cuando puede mantener toda la base de datos hash en la memoria. Esto es bastante práctico ya que un hash solo tiene 8 bytes.

Por ejemplo, si tiene 1 millón de imágenes, se requeriría una matriz de 1 millón de valores hash de 64 bits (8 MB). En algunas CPU, esto encaja en el caché L2 / L3! En el uso práctico, he visto una comparación de corei7 a más de 1 Giga-hamm / s, solo es una cuestión de ancho de banda de memoria para la CPU. ¡Una base de datos de 1 billón de imágenes es práctica en una CPU de 64 bits (se necesitan 8 GB de RAM) y las búsquedas no excederán de 1 segundo!

Para las imágenes modificadas / recortadas, parece que un detector de características / puntos clave invariables a la transformación como SIFT es el camino a seguir. SIFT producirá buenos puntos clave que detectarán el recorte / rotación / espejo, etc. Sin embargo, la comparación del descriptor es muy lenta en comparación con la distancia de hamming utilizada por el phash. Esta es una limitación importante. Hay muchas comparaciones que hacer, ya que hay un máximo de comparadores IxJxK para buscar una imagen (I = número de imágenes de pajar, J = puntos clave de destino por imagen de pajar, K = puntos de destino clave por imagen de aguja).

Para solucionar el problema de la velocidad, traté de usar phash alrededor de cada punto clave encontrado, utilizando la función tamaño / radio para determinar el sub-rectángulo. El truco para hacer que esto funcione bien, es aumentar / reducir el radio para generar diferentes niveles indirectos (en la imagen de la aguja). Normalmente, el primer nivel (sin escala) coincidirá, pero a menudo se necesitan algunos más. No estoy 100% seguro de por qué funciona esto, pero me imagino que habilita funciones que son demasiado pequeñas para que funcione phash (phash reduce las imágenes a 32x32).

Otro problema es que SIFT no distribuirá los puntos clave de manera óptima. Si hay una sección de la imagen con muchos bordes, los puntos clave se agruparán allí y no obtendrá ninguno en otra área. Estoy usando GridAdaptedFeatureDetector en OpenCV para mejorar la distribución. No estoy seguro de qué tamaño de cuadrícula es el mejor, estoy usando una cuadrícula pequeña (1x3 o 3x1 según la orientación de la imagen).

Probablemente desee escalar todas las imágenes del pajar (y la aguja) a un tamaño más pequeño antes de la detección de características (yo uso 210px a lo largo de la dimensión máxima). Esto reducirá el ruido en la imagen (siempre es un problema para los algoritmos de visión de computadora), también enfocará el detector en características más prominentes.

Para las imágenes de personas, puede probar la detección de rostros y usarla para determinar el tamaño de la imagen a escalar y el tamaño de la cuadrícula (por ejemplo, la cara más grande a escala de 100 px). El detector de características cuenta con múltiples niveles de escala (usando pirámides) pero hay una limitación en la cantidad de niveles que usará (esto es, por supuesto, ajustable).

El detector de puntos clave probablemente funcione mejor cuando devuelve menos que la cantidad de funciones que deseaba. Por ejemplo, si pides 400 y obtienes 300 de vuelta, eso es bueno. Si recibes 400 de vuelta cada vez, probablemente hay que dejar de lado algunas funciones buenas.

La imagen de la aguja puede tener menos puntos clave que las imágenes del pajar y aún así obtener buenos resultados. Agregar más no necesariamente le brinda grandes ganancias, por ejemplo, con J = 400 y K = 40, mi índice de aciertos es aproximadamente del 92%. Con J = 400 y K = 400, la tasa de aciertos solo sube al 96%.

Podemos aprovechar la velocidad extrema de la función de hamming para resolver escalas, rotaciones, reflejos, etc. Se puede usar una técnica de paso múltiple. En cada iteración, transforme los sub-rectángulos, re-hash, y ejecute de nuevo la función de búsqueda.