algorithm - recognition - Algoritmo para comparar dos imágenes
object recognition opencv (9)
Dado dos archivos de imagen diferentes (en el formato que elija), necesito escribir un programa para predecir la posibilidad de que una sea la copia ilegal de otra. El autor de la copia puede hacer cosas como girar, hacer negativo o agregar detalles triviales (así como cambiar la dimensión de la imagen).
¿Conoces algún algoritmo para hacer este tipo de trabajo?
Creo que si estás dispuesto a aplicar el enfoque a todas las orientaciones posibles y a las versiones negativas, un buen comienzo para el reconocimiento de imágenes (con buena fiabilidad) es utilizar las propias caras: http://en.wikipedia.org/wiki/Eigenface
Otra idea sería transformar ambas imágenes en vectores de sus componentes. Una buena forma de hacerlo es crear un vector que opere en x * y dimensiones (x es el ancho de su imagen e y es la altura), con el valor para cada dimensión aplicando al valor de píxel (x, y). Luego ejecuta una variante de K-Nearest Neighbors con dos categorías: match y no match. Si está lo suficientemente cerca de la imagen original, cabe en la categoría de coincidencia, si no, no lo hará.
K Nearest Neighbors (KNN) se puede encontrar aquí, también hay otras buenas explicaciones en la web: http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm
Los beneficios de KNN son que cuantas más variantes compares con la imagen original, más preciso se vuelve el algoritmo. La desventaja es que necesitas un catálogo de imágenes para entrenar al sistema primero.
De hecho, es mucho menos simple de lo que parece :-) La sugerencia de Nick es buena.
Para comenzar, tenga en cuenta que cualquier método de comparación que valga la pena funcionará esencialmente al convertir las imágenes en una forma diferente, una forma que facilita la selección de funciones similares. Usualmente, esto no hace una lectura muy ligera ...
Uno de los ejemplos más simples que puedo pensar es simplemente usar el espacio de color de cada imagen. Si dos imágenes tienen distribuciones de color muy similares, entonces puede estar razonablemente seguro de que muestran lo mismo. Al menos, puede tener suficiente certeza para marcarlo, o hacer más pruebas. Comparar imágenes en el espacio de color también resistirá cosas como rotación, escalado y algunos recortes. Por supuesto, no resistirá la modificación intensa de la imagen ni el cambio de color (incluso un simple cambio de matiz será un tanto complicado).
http://en.wikipedia.org/wiki/RGB_color_space
http://upvector.com/index.php?section=tutorials&subsection=tutorials/colorspace
Otro ejemplo involucra algo llamado Hough Transform. Esta transformación descompone esencialmente una imagen en un conjunto de líneas. Luego puede tomar algunas de las líneas "más fuertes" en cada imagen y ver si se alinean. También puede hacer un trabajo adicional para tratar de compensar la rotación y la escala, y en este caso, dado que comparar unas pocas líneas es MUCHO menos trabajo computacional que hacer lo mismo con imágenes completas, no será tan malo.
http://homepages.inf.ed.ac.uk/amos/hough.html
http://rkb.home.cern.ch/rkb/AN16pp/node122.html
http://en.wikipedia.org/wiki/Hough_transform
Deberá usar un esquema de marca de agua para insertar un código en la imagen. Para dar un paso atrás, a diferencia de algunos enfoques de bajo nivel (detección de bordes, etc.) sugeridos por algunas personas, un método de marca de agua es superior porque:
Es resistente a los ataques de procesamiento de señal ► Mejora de la señal: nitidez, contraste, etc. ► Filtrado: mediana, paso bajo, paso alto, etc. ► Ruido aditivo: gaussiano, uniforme, etc. ► Compresión con pérdida: JPEG, MPEG, etc.
Es resistente a los ataques geométricos ► Transformaciones afines ► Reducción de datos: recorte, recorte, etc. ► Distorsiones locales aleatorias ► Distorsión
Investigue un poco sobre los algoritmos de marca de agua y estará en el camino correcto para resolver su problema. (Nota: Puede comparar su método con el conjunto de datos STIRMARK . Es un estándar aceptado para este tipo de aplicación.
Estas son simplemente ideas. He pensado en el problema, nunca lo intenté pero me gusta pensar en problemas como este.
Antes de que empieces
Considere la posibilidad de normalizar las imágenes, si una es una resolución más alta que la otra, considere la opción de que una de ellas sea una versión comprimida de la otra, por lo tanto, reducir la resolución puede proporcionar resultados más precisos.
Considere escanear varias áreas posibles de la imagen que podrían representar partes ampliadas de la imagen y varias posiciones y rotaciones. Comienza a ser complicado si una de las imágenes es una versión sesgada de otra, estas son el tipo de limitaciones que debe identificar y comprometer.
Matlab es una excelente herramienta para probar y evaluar imágenes.
Probando los algoritmos
Debería probar (como mínimo) un gran conjunto de datos de prueba analizados por humanos donde las coincidencias se conocen de antemano. Si, por ejemplo, en sus datos de prueba tiene 1,000 imágenes donde el 5% de ellas coinciden, ahora tiene un punto de referencia razonablemente confiable. Un algoritmo que encuentra un 10% de positivos no es tan bueno como uno que encuentra el 4% de positivos en nuestros datos de prueba. Sin embargo, un algoritmo puede encontrar todas las coincidencias, pero también tiene una gran tasa de falsos positivos del 20%, por lo que hay varias formas de clasificar sus algoritmos.
Los datos de prueba deben intentar diseñarse para abarcar todos los tipos de dinámica que pueda esperar encontrar en el mundo real.
Es importante tener en cuenta que cada algoritmo que sea útil debe funcionar mejor que la adivinación al azar, de lo contrario, ¡no sirve para nada!
A continuación, puede aplicar su software en el mundo real de forma controlada y comenzar a analizar los resultados que produce. Este es el tipo de proyecto de software que puede continuar infinitamente, siempre hay ajustes y mejoras que puede hacer, es importante tener eso en cuenta cuando se diseña, ya que es fácil caer en la trampa del proyecto interminable.
Cubos de colores
Con dos imágenes, escanee cada píxel y cuente los colores. Por ejemplo, puede tener los ''cubos'':
white
red
blue
green
black
(Obviamente tendrías una mayor resolución de contadores). Cada vez que encuentre un píxel "rojo", incrementará el contador rojo. Cada cangilón puede ser representativo del espectro de colores, mientras más alta sea la resolución, más preciso es, pero debes experimentar con una tasa de diferencia aceptable.
Una vez que tenga sus totales, compárelos con los totales de una segunda imagen. Puede encontrar que cada imagen tiene una huella bastante única, suficiente para identificar coincidencias.
Detección de bordes
¿Qué hay de usar Edge Detection ? alt text http://upload.wikimedia.org/wikipedia/en/thumb/8/8e/EdgeDetectionMathematica.png/500px-EdgeDetectionMathematica.png
Con dos imágenes similares, la detección de bordes debería proporcionarle una huella única utilizable y bastante confiable.
Tome ambas fotografías y aplique detección de bordes. Tal vez mida el grosor promedio de los bordes y luego calcule la probabilidad de que la imagen se pueda escalar, y cambie la escala si es necesario. A continuación se muestra un ejemplo de un filtro Gabor aplicado (un tipo de detección de bordes) en varias rotaciones.
Compare las imágenes píxel por píxel, cuente las coincidencias y las que no coinciden. Si están dentro de un cierto umbral de error, tiene una coincidencia. De lo contrario, podría intentar reducir la resolución hasta cierto punto y ver si la probabilidad de una coincidencia mejora.
Regiones de interés
Algunas imágenes pueden tener segmentos / regiones de interés distintivos. Estas regiones probablemente contrastan mucho con el resto de la imagen, y son un buen elemento para buscar en sus otras imágenes para encontrar coincidencias. Tome esta imagen, por ejemplo:
texto alternativo http://meetthegimp.org/wp-content/uploads/2009/04/97.jpg
El trabajador de la construcción en azul es una región de interés y puede usarse como un objeto de búsqueda. Probablemente haya varias maneras en que puede extraer propiedades / datos de esta región de interés y usarlos para buscar su conjunto de datos.
Si tiene más de 2 regiones de interés, puede medir las distancias entre ellas. Toma este ejemplo simplificado:
texto alternativo http://www.per2000.eu/assets/images/3_dots_black_03.jpg
Tenemos 3 claras regiones de interés. La distancia entre la región 1 y 2 puede ser de 200 píxeles, entre 1 y 3 400 píxeles, y 2 y 3 200 píxeles.
Busque otras imágenes para regiones de interés similares, normalice los valores de distancia y vea si tiene coincidencias potenciales. Esta técnica podría funcionar bien para imágenes giradas y escaladas. Cuantas más regiones de interés tenga, la probabilidad de una coincidencia aumenta a medida que cada medida de distancia coincida.
Es importante pensar en el contexto de su conjunto de datos. Si, por ejemplo, su conjunto de datos es arte moderno, entonces las regiones de interés funcionarían bastante bien, ya que las regiones de interés probablemente fueron diseñadas para ser una parte fundamental de la imagen final. Sin embargo, si está tratando con imágenes de sitios de construcción, las regiones de interés pueden ser interpretadas por la copiadora ilegal como feas y pueden ser recortadas / editadas libremente. Tenga en cuenta las características comunes de su conjunto de datos e intente aprovechar ese conocimiento.
Morphing
Morphing dos imágenes es el proceso de convertir una imagen en la otra a través de un conjunto de pasos:
Tenga en cuenta que esto es diferente a desvanecer una imagen en otra.
Hay muchos paquetes de software que pueden transformar imágenes. Se usa tradicionalmente como un efecto de transición, dos imágenes no se transforman en algo a la mitad, generalmente, un extremo se transforma en el otro extremo como resultado final.
¿Por qué podría esto ser útil? Dependiendo del algoritmo de transformación que utilice, puede haber una relación entre la similitud de imágenes y algunos parámetros del algoritmo de transformación.
En un ejemplo extremadamente simplificado, un algoritmo puede ejecutarse más rápido cuando se realizan menos cambios. Entonces sabemos que hay una mayor probabilidad de que estas dos imágenes compartan propiedades entre sí.
Esta técnica podría funcionar bien para rotar, distorsionar, sesgar, ampliar todos los tipos de imágenes copiadas. Una vez más, esta es solo una idea que he tenido, por lo que tengo entendido, no se basa en ninguna academia investigada (aunque no me he esforzado mucho), por lo que puede ser mucho trabajo para usted con resultados limitados o sin resultados.
Zipping
La respuesta de Ow en esta pregunta es excelente, recuerdo haber leído sobre este tipo de técnicas estudiando IA. Es bastante efectivo al comparar los léxicos del corpus.
Una optimización interesante cuando se comparan los corpúsculos es que se pueden eliminar las palabras que se consideran demasiado comunes, por ejemplo ''The'', ''A'', ''And'', etc. Estas palabras diluyen nuestro resultado, queremos determinar cuán diferentes son los dos corpus. por lo que estos se pueden eliminar antes del procesamiento. ¿Quizás hay señales comunes similares en las imágenes que podrían eliminarse antes de la compresión? Puede valer la pena investigarlo.
La relación de compresión es una forma muy rápida y razonablemente efectiva de determinar qué tan similares son dos conjuntos de datos. Leer acerca de cómo funciona la compresión le dará una buena idea de por qué esto podría ser tan efectivo. Para un algoritmo de lanzamiento rápido, este sería probablemente un buen punto de partida.
Transparencia
De nuevo, no estoy seguro de cómo se almacenan los datos de transparencia para ciertos tipos de imágenes, gif png, etc., pero esto será extraíble y serviría como un recorte simplificado eficaz para comparar con la transparencia de los conjuntos de datos.
Inversión de señales
Una imagen es solo una señal. Si reproduce un ruido de un altavoz y reproduce el ruido opuesto en otro altavoz en perfecta sincronización al mismo volumen, se cancelan mutuamente.
texto alternativo http://www.themotorreport.com.au/wp-content/uploads/2008/07/noise-cancellation.gif
Invierta las imágenes y agréguelas a su otra imagen. Escalar / repetir las posiciones de forma repetitiva hasta que encuentre una imagen resultante donde los píxeles son blancos (o negro? Me referiré a ellos como un lienzo neutral) para proporcionarle una coincidencia positiva o una coincidencia parcial.
Sin embargo, considere dos imágenes que son iguales, excepto que una de ellas tiene un efecto de brillo aplicado:
Invertir uno de ellos y luego agregarlo al otro no dará como resultado un lienzo neutral, que es lo que estamos buscando. Sin embargo, al comparar los píxeles de ambas imágenes originales, podemos ver claramente una relación clara entre los dos.
Hace algunos años que no estudio el color y no estoy seguro si el espectro de color está en una escala lineal, pero si determinó el factor promedio de diferencia de color entre ambas imágenes, puede usar este valor para normalizar los datos antes de procesarlos. esta tecnica.
Estructuras de datos de árbol
Al principio, estos no parecen ajustarse al problema, pero creo que podrían funcionar.
Podría pensar en extraer ciertas propiedades de una imagen (por ejemplo, contenedores de colores) y generar un árbol huffman o una estructura de datos similar. Es posible que pueda comparar dos árboles por similitud. Esto no funcionaría bien para datos fotográficos, por ejemplo, con un amplio espectro de colores, pero dibujos animados u otras imágenes de conjuntos de colores reducidos podrían funcionar.
Esto probablemente no funcionaría, pero es una idea. La estructura de datos de trie es excelente para almacenar léxicos, por ejemplo, una dicción artística . Es un árbol de prefijos. Tal vez sea posible construir una imagen equivalente de un léxico, (de nuevo, solo puedo pensar en los colores) para construir un trie. Si redujo una imagen de 300x300 en cuadrados de 5x5, luego descomponga cada cuadrado de 5x5 en una secuencia de colores, podría construir un trie a partir de los datos resultantes. Si un cuadrado de 2x2 contiene:
FFFFFF|000000|FDFD44|FFFFFF
Tenemos un código trie bastante único que se extiende a 24 niveles, aumentar / disminuir los niveles (IE reducir / aumentar el tamaño de nuestro sub cuadrado) puede producir resultados más precisos.
La comparación de árboles debe ser razonablemente fácil y podría proporcionar resultados efectivos.
Más ideas
Me encontré con una interesante breba de papel sobre la clasificación de las imágenes satelitales , que describe:
Las medidas de textura consideradas son: matrices de coocurrencia, diferencias de nivel de grises, análisis de textura y tono, características derivadas del espectro de Fourier y filtros de Gabor. Algunas características de Fourier y algunos filtros de Gabor fueron buenas elecciones, en particular cuando se usó una sola banda de frecuencia para la clasificación.
Puede valer la pena investigar esas mediciones con más detalle, aunque algunas de ellas pueden no ser relevantes para su conjunto de datos.
Otras cosas a considerar
Probablemente hay muchos documentos sobre este tipo de cosas, por lo que leer algunos de ellos debería ayudar, aunque pueden ser muy técnicos. Es un área extremadamente difícil en informática, con muchas horas de trabajo infructuosas por parte de muchas personas que intentan hacer cosas similares. Mantenerlo simple y construir sobre esas ideas sería la mejor manera de hacerlo. Debería ser un reto bastante difícil crear un algoritmo con una tasa de coincidencia mejor que la aleatoria, y para comenzar a mejorar eso realmente comienza a ser bastante difícil de lograr.
Probablemente sea necesario probar y ajustar cada método exhaustivamente, si tiene alguna información sobre el tipo de imagen que va a verificar también, sería útil. Por ejemplo, los anuncios, muchos de ellos tendrían texto, por lo que el reconocimiento de texto sería una manera fácil y probablemente muy confiable de encontrar coincidencias, especialmente cuando se combina con otras soluciones. Como se mencionó anteriormente, intente explotar las propiedades comunes de su conjunto de datos.
La combinación de medidas y técnicas alternativas, cada una de las cuales puede tener un voto ponderado (dependiendo de su efectividad), sería una forma de crear un sistema que genere resultados más precisos.
Si se emplean múltiples algoritmos, como se mencionó al comienzo de esta respuesta, uno puede encontrar todos los positivos pero tiene una tasa de falsos positivos del 20%, sería interesante estudiar las propiedades / fortalezas / debilidades de otros algoritmos ya que otro algoritmo puede ser efectivo en la eliminación de falsos positivos devueltos por otro.
Tenga cuidado de no caer en el intento de completar el proyecto sin fin, ¡buena suerte!
Esto es solo una sugerencia, podría no funcionar y estoy dispuesto a que me llamen por esto.
Esto generará falsos positivos, pero con suerte no falsos negativos.
Cambie el tamaño de ambas imágenes para que tengan el mismo tamaño (supongo que las proporciones de anchuras a longitudes son las mismas en ambas imágenes).
Comprima un mapa de bits de ambas imágenes con un algoritmo de compresión sin pérdida (por ejemplo, gzip).
Busque pares de archivos que tengan tamaños de archivo similares. Por ejemplo, puedes ordenar cada par de archivos que tienes por lo similares que son los tamaños de archivo y recuperar la X superior.
Como dije, esto definitivamente generará falsos positivos, pero con suerte no falsos negativos. Puede implementar esto en cinco minutos, mientras que el Porikil et. Alabama. probablemente requeriría un trabajo extenso.
Lea el periódico: Porikli, Fatih, Oncel Tuzel y Peter Meer. "Seguimiento de covarianza usando la actualización del modelo basada en los medios en manifolds riemannianos". (2006) IEEE Computer Vision and Pattern Recognition.
Logré detectar regiones superpuestas en imágenes capturadas de cámaras web adyacentes utilizando la técnica presentada en este documento. Mi matriz de covarianza estaba compuesta de salidas de detección de aspecto / borde Sobel, canny y SUSAN, así como también los píxeles de escala de grises originales.
Si está dispuesto a considerar por completo un enfoque diferente para detectar copias ilegales de sus imágenes, podría considerar la watermarking . (desde 1.4)
... inserta información de copyright en el objeto digital sin pérdida de calidad. Siempre que los derechos de autor de un objeto digital estén en cuestión, esta información se extrae para identificar al propietario legítimo. También es posible codificar la identidad del comprador original junto con la identidad del titular de los derechos de autor, lo que permite rastrear cualquier copia no autorizada.
Si bien también es un campo complejo, existen técnicas que permiten que la información de la marca de agua persista a través de la alteración gruesa de la imagen: (de 1.9)
... cualquier transformación de señal de fuerza razonable no puede eliminar la marca de agua. Por lo tanto, un pirata dispuesto a eliminar la marca de agua no tendrá éxito a menos que degraden el documento demasiado para ser de interés comercial.
por supuesto, las preguntas más frecuentes apelan a la implementación de este enfoque: "... muy desafiante", pero si se tiene éxito, se obtiene una gran confianza de si la imagen es una copia o no, en lugar de una probabilidad porcentual.
Si está ejecutando Linux, sugeriría dos herramientas:
align_image_stack del paquete hugin-tools - es un programa de línea de comandos que puede corregir automáticamente la rotación, la escala y otras distorsiones (está principalmente destinado a la composición de fotografías HDR, pero también funciona para marcos de video y otros documentos). Más información: http://hugin.sourceforge.net/docs/manual/Align_image_stack.html
comparar desde el paquete imagemagick - un programa que puede encontrar y contar la cantidad de píxeles diferentes en dos imágenes. Aquí hay un tutorial perfecto: http://www.imagemagick.org/Usage/compare/ uising the -fuzz N% puede aumentar la tolerancia al error. Cuanto mayor sea la N, mayor será la tolerancia de error para contar aún dos píxeles iguales.
align_image_stack debe corregir cualquier desplazamiento para que el comando de comparación realmente tenga la posibilidad de detectar los mismos píxeles.
Una idea:
- use detectores de puntos clave para encontrar descripciones invariables de escala y transformación de algunos puntos de la imagen (por ejemplo, SIFT, SURF, GLOH o LESH).
- intente alinear los puntos clave con descripciones similares de ambas imágenes (como en las puntadas panorámicas), permita algunas transformaciones de imagen si es necesario (por ejemplo, escala y rotación, o estiramiento elástico).
- si muchos puntos clave se alinean bien (existe tal transformación, ese error de alineación del punto clave es bajo, o la "energía" de transformación es baja, etc.), es probable que tenga imágenes similares.
El paso 2 no es trivial. En particular, puede necesitar usar un algoritmo inteligente para encontrar el punto clave más similar en la otra imagen. Los descriptores de puntos suelen ser muy dimensionales (como cien parámetros), y hay muchos puntos para examinar. Los kd-trees pueden ser útiles aquí, las búsquedas de hash no funcionan bien.
Variantes:
- Detecta bordes u otras características en lugar de puntos.