Dados dos archivos de imagen diferentes (en cualquier formato que elija), necesito escribir un programa para predecir la posibilidad de que uno sea la copia ilegal de otro. El autor de la copia puede hacer cosas como rotar, hacer negativos o agregar detalles triviales (además de cambiar la dimensión de la imagen).
¿Conoces algún algoritmo para hacer este tipo de trabajo?
algorithm
image
image-processing
image-recognition
Salvador Dalí
fuente
fuente
Respuestas:
Estas son simplemente ideas que he tenido pensando en el problema, nunca lo probé, ¡pero me gusta pensar en problemas como este!
Antes de que empieces
Considere la normalización de las imágenes, si una tiene 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 prospectivas de la imagen que podrían representar porciones ampliadas de la imagen y varias posiciones y rotaciones. Comienza a complicarse si una de las imágenes es una versión sesgada de otra, estas son las limitaciones que debes identificar y comprometer.
Matlab es una excelente herramienta para probar y evaluar imágenes.
Probar los algoritmos
Debe probar (como mínimo) un gran conjunto de datos de prueba analizados en humanos donde las coincidencias se conocen de antemano. Si, por ejemplo, en los datos de su 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 un 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 calificar sus algoritmos.
Los datos de prueba deben intentar diseñarse para abarcar tantos tipos de dinámicas como sea posible que esperaría encontrar en el mundo real.
Es importante tener en cuenta que cada algoritmo para ser útil debe funcionar mejor que adivinar al azar, de lo contrario, ¡es inútil para nosotros!
Luego puede aplicar su software al mundo real de forma controlada y comenzar a analizar los resultados que produce. Este es el tipo de proyecto de software que puede continuar hasta el infinito, siempre hay ajustes y mejoras que puede hacer, es importante tenerlo en cuenta al diseñarlo, 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':
(Obviamente tendrías una mayor resolución de contadores). Cada vez que encuentra un píxel 'rojo', incrementa el contador rojo. Cada cubo puede ser representativo del espectro de colores, cuanto mayor sea la resolución, más precisa, pero debe experimentar con una tasa de diferencia aceptable.
Una vez que tenga sus totales, compárelos con los totales de una segunda imagen. Es posible que cada imagen tenga una huella bastante única, suficiente para identificar coincidencias.
Detección de bordes
¿Qué hay de usar Edge Detection ? (fuente: wikimedia.org )
Con dos imágenes similares, la detección de bordes debería proporcionarle una huella única utilizable y bastante confiable.
Tome ambas fotos y aplique la 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 vuelva a escalar 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 no coincidencias. Si están dentro de un cierto umbral de error, tienes una coincidencia. De lo contrario, podría intentar reducir la resolución hasta cierto punto y ver si mejora la probabilidad de una coincidencia.
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:
(fuente: meetthegimp.org )
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 hay varias formas de extraer propiedades / datos de esta región de interés y utilizarlos para buscar en su conjunto de datos.
Si tiene más de 2 regiones de interés, puede medir las distancias entre ellas. Tome este ejemplo simplificado:
(fuente: per2000.eu )
Tenemos 3 regiones claras 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 en otras imágenes regiones similares de interés, normalice los valores de distancia y vea si tiene coincidencias potenciales. Esta técnica podría funcionar bien para imágenes rotadas y escaladas. Cuantas más regiones de interés tenga, la probabilidad de una coincidencia aumenta a medida que coincida cada medición de distancia.
Es importante pensar en el contexto de su conjunto de datos. Si, por ejemplo, su conjunto de datos es arte moderno, 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 se trata de imágenes de sitios de construcción, la copiadora ilegal puede interpretar que las regiones de interés son feas y se pueden recortar / editar libremente. Tenga en cuenta las características comunes de su conjunto de datos e intente explotar 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 medio camino, un extremo se transforma en el otro extremo como resultado final.
¿Por qué podría ser útil? Dependiendo del algoritmo de transformación que utilice, puede haber una relación entre la similitud de las imágenes y algunos parámetros del algoritmo de transformación.
En un ejemplo excesivamente simplificado, un algoritmo podría ejecutarse más rápido cuando hay menos cambios por hacer. 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 todo tipo de imágenes copiadas, distorsionadas, sesgadas, con zoom. Una vez más, esta es solo una idea que he tenido, no está basada en ninguna academia investigada hasta donde yo sé (aunque no he buscado mucho), por lo que puede ser mucho trabajo para ti con resultados limitados o sin resultados.
Comprimir
La respuesta de Ow en esta pregunta es excelente, recuerdo haber leído sobre este tipo de técnicas para estudiar IA. Es bastante efectivo para comparar léxicos de corpus.
Una optimización interesante al comparar corpus es que puede eliminar palabras consideradas demasiado comunes, por ejemplo, 'The', 'A', 'And', etc. Estas palabras diluyen nuestro resultado, queremos saber qué tan diferentes son los dos corpus para que se puedan eliminar antes de procesar. ¿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 sobre 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
Nuevamente, 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 corte simplificado efectivo para comparar con la transparencia de sus conjuntos de datos.
Señales inversoras
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.
(fuente: themotorreport.com.au )
Invierta las imágenes y agréguelas a su otra imagen. Escale las posiciones de bucle / repetidamente hasta que encuentre una imagen resultante donde suficientes píxeles sean blancos (¿o negros? Me referiré a ellos como un lienzo neutral) para proporcionarle una coincidencia positiva o parcial.
Sin embargo, considere dos imágenes que son iguales, excepto que una de ellas tiene un efecto de brillo aplicado:
(fuente: mcburrz.com )
Invertir uno de ellos y luego agregarlo al otro no dará como resultado un lienzo neutral, que es a lo que apuntamos. Sin embargo, al comparar los píxeles de ambas imágenes originales, definitivamente podemos ver una relación clara entre los dos.
No he estudiado el color desde hace algunos años, 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 procesar con esta tecnica.
Estructuras de datos de árbol
Al principio, estos no parecen encajar con el 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 los datos fotográficos, por ejemplo, con un amplio espectro de color, pero los dibujos animados u otras imágenes con conjuntos de colores reducidos podrían funcionar.
Esto probablemente no funcionaría, pero es una idea. La estructura de datos trie es excelente para almacenar léxicos, por ejemplo, una dicción . Es un árbol de prefijos. Quizás sea posible construir una imagen equivalente a un léxico, (nuevamente solo puedo pensar en colores) para construir un trie. Si redujo, digamos, una imagen de 300x300 en cuadrados de 5x5, descomponga cada cuadrado de 5x5 en una secuencia de colores que podría construir un trie a partir de los datos resultantes. Si un cuadrado de 2x2 contiene:
Tenemos un código de trie bastante único que extiende 24 niveles, aumentando / disminuyendo los niveles (es decir, reduciendo / aumentando el tamaño de nuestro subcuadrado) puede producir resultados más precisos.
La comparación de árboles de trie debería ser razonablemente fácil y podría proporcionar resultados efectivos.
Más ideas
Me topé con un breve resumen en papel sobre la clasificación de imágenes satelitales , que describe:
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 infructuosas de trabajo gastadas por 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 desafío razonablemente difícil crear un algoritmo con una tasa de coincidencia mejor que aleatoria, y comenzar a mejorar eso realmente comienza a ser bastante difícil de lograr.
Es probable que cada método deba probarse y ajustarse a fondo, si tiene alguna información sobre el tipo de imagen que también verificará, esto sería útil. Por ejemplo, anuncios, muchos de ellos tendrían texto, por lo que el reconocimiento de texto sería una forma 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.
Combinar 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 tener una tasa de falsos positivos del 20%, sería interesante estudiar las propiedades / fortalezas / debilidades de otros algoritmos, ya que otro algoritmo puede Ser eficaz en la eliminación de falsos positivos devueltos por otro.
Tenga cuidado de no caer en el intento de completar el proyecto interminable, ¡buena suerte!
fuente
Lea el periódico: Porikli, Fatih, Oncel Tuzel y Peter Meer. "Seguimiento de covarianza utilizando actualización de modelo basada en medias en colectores riemannianos". (2006) IEEE Computer Vision y Pattern Recognition.
Pude detectar con éxito 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 por salidas de detección de aspecto / borde Sobel, canny y SUSAN, así como los píxeles originales en escala de grises.
fuente
Una idea:
El paso 2 no es trivial. En particular, es posible que deba usar un algoritmo inteligente para encontrar el punto clave más similar en la otra imagen. Los descriptores de puntos son generalmente de muy alta dimensión (como un centenar de parámetros), y hay muchos puntos para examinar. Los kd-trees pueden ser útiles aquí, las búsquedas de hash no funcionan bien.
Variantes:
fuente
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 características similares. Por lo general, esto no hace una lectura muy ligera ...
Uno de los ejemplos más simples que se me ocurre es simplemente usar el espacio de color de cada imagen. Si dos imágenes tienen distribuciones de color muy similares, puede estar razonablemente seguro de que muestran lo mismo. Al menos, puede tener la certeza suficiente para marcarlo o hacer más pruebas. La comparación de imágenes en el espacio de color también resistirá cosas como la rotación, el escalado y algunos recortes. Por supuesto, no resistirá una gran modificación de la imagen o un gran cambio de color (e incluso un simple cambio de tono será algo 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 esencialmente descompone 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. Puede hacer un trabajo adicional para intentar compensar la rotación y el escalado también, y en este caso, ya que comparar algunas 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
fuente
En la forma descrita por usted, el problema es difícil. ¿Considera copiar, pegar parte de la imagen en otra imagen más grande como copia? etc.
Si retrocede, esto es más fácil de resolver si marca con agua las imágenes maestras. Deberá utilizar un esquema de marca de agua para incrustar un código en la imagen. Para dar un paso atrás, a diferencia de algunos de los 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ñales ► 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 ► Deformació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 utilizando el conjunto de datos STIRMARK . Es un estándar aceptado para este tipo de aplicación.
fuente
Esto es solo una sugerencia, puede que no funcione y estoy preparado para que lo llamen.
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 ancho a largo son las mismas en ambas imágenes).
Comprima un mapa de bits de ambas imágenes con un algoritmo de compresión sin pérdidas (por ejemplo, gzip).
Encuentre pares de archivos que tengan tamaños de archivo similares. Por ejemplo, podría ordenar cada par de archivos que tenga según el tamaño de los archivos 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.
fuente
Creo que si está 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 confiabilidad) es usar caras propias: http://en.wikipedia.org/wiki/Eigenface
Otra idea sería transformar ambas imágenes en vectores de sus componentes. Una buena manera de hacer esto es crear un vector que funcione en dimensiones x * y (x es el ancho de su imagen e y es la altura), con el valor de cada dimensión que se aplica al valor de píxel (x, y). Luego ejecute una variante de Vecinos K-Nearest con dos categorías: coincidencia y no coincidencia. Si está lo suficientemente cerca de la imagen original, encajará en la categoría de coincidencia, de lo contrario, no lo hará.
Los vecinos más cercanos de K (KNN) se pueden encontrar aquí, también hay otras buenas explicaciones en la web: http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm
Los beneficios de KNN es que cuantas más variantes compares con la imagen original, más preciso será el algoritmo. La desventaja es que primero necesita un catálogo de imágenes para entrenar el sistema.
fuente
Si está dispuesto a considerar un enfoque completamente diferente para detectar copias ilegales de sus imágenes, podría considerar la marca de agua . (desde 1.4)
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 de la imagen: (desde 1.9)
por supuesto, las preguntas frecuentes llaman a implementar este enfoque: "... muy desafiante", pero si lo logras, obtienes una gran confianza de si la imagen es una copia o no, en lugar de un porcentaje de probabilidad.
fuente
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, el escalado y otras distorsiones (está destinado principalmente a componer fotografías HDR, pero también funciona para cuadros de video y otros documentos). Más información: http://hugin.sourceforge.net/docs/manual/Align_image_stack.html
compare from package imagemagick : un programa que puede encontrar y contar la cantidad de píxeles diferentes en dos imágenes. Aquí hay un tutorial interesante : http://www.imagemagick.org/Usage/compare/ uising el -fuzz N% puede aumentar la tolerancia al error. Cuanto mayor sea la N, mayor será la tolerancia al error para seguir contando dos píxeles como lo mismo.
align_image_stack debe corregir cualquier desplazamiento para que el comando de comparación tenga la posibilidad de detectar los mismos píxeles.
fuente