Recientemente tuve que resolver el problema de optimizar la búsqueda de imágenes duplicadas.
La solución existente se ejecuta en una biblioteca de Python bastante conocida,
Image Match , basada en UNA FIRMA DE IMAGEN PARA CUALQUIER TIPO DE IMAGEN, creada por H. Chi Wong, Marshall Bern y David Goldberg.
Por varias razones, se decidió reescribir todo a Kotlin, al mismo tiempo que abandonó el almacenamiento y la búsqueda en ElasticSearch, que requiere significativamente más recursos, tanto de hierro como humanos, para soporte y administración, a favor de buscar en el caché local en memoria.
Para entender cómo funciona, tuve que sumergirme en el código Python "de referencia", ya que el trabajo original a veces no es del todo obvio, y en un par de lugares me hace recordar "cómo dibujar un búho". En realidad, quiero compartir los resultados de este estudio, al mismo tiempo que les cuento algunas optimizaciones, tanto en términos de volumen de datos como de velocidad de búsqueda. Tal vez alguien sea útil.
Descargo de responsabilidad: existe la posibilidad de que me equivoqué en algún lugar, lo hice mal o no de manera óptima. Bueno, estaré encantado de cualquier crítica y comentario. :)
Cómo funciona
- La imagen se convierte a formato blanco y negro de 8 bits (un punto es un byte en el valor 0-255)
- La imagen se recorta de tal manera que descarte el 5% de la diferencia acumulada (más abajo) de cada uno de los cuatro lados. Por ejemplo, un marco negro alrededor de la imagen.
- Se selecciona una cuadrícula de trabajo (9x9 por defecto), cuyos nodos servirán como puntos de referencia de la firma de la imagen.
- Para cada punto de referencia, sobre la base de un área determinada a su alrededor, se calcula su brillo.
- Para cada punto de referencia, se calcula cuánto es más brillante / más oscuro que sus ocho vecinos. Se utilizan cinco gradaciones, de -2 (mucho más oscuro) a 2 (mucho más brillante).
- Toda esta "alegría" se desarrolla en una matriz unidimensional (vector) y es llamada por la firma de la imagen.
La similitud de las dos imágenes se verifica de la siguiente manera:
Cuanto menor sea la d, mejor. De hecho, d <0.3 es casi una garantía de identidad.
Ahora con más detalle.
Primer paso
Creo que hablar sobre la conversión a escala de grises tiene poco sentido.
Segundo paso
Digamos que tenemos una imagen como esta:
Se puede ver que hay un marco negro de 3 píxeles a la derecha e izquierda y 2 píxeles en la parte superior e inferior, que no necesitamos en absoluto en comparaciónEl límite de corte se determina mediante el siguiente algoritmo:
- Para cada columna, calculamos la suma de las diferencias absolutas de los elementos vecinos.
- Recortamos a izquierda y derecha el número de píxeles cuya contribución a la diferencia acumulativa total es inferior al 5%.
Hacemos lo mismo para las columnas.
Una aclaración importante: si las dimensiones de la imagen resultante son insuficientes para el paso 4, ¡entonces no recortamos!
Paso tres
Bueno, aquí todo es bastante simple, dividimos la imagen en partes iguales y seleccionamos los puntos nodales.
Cuarto paso
El brillo del punto de anclaje se calcula como el brillo promedio de todos los puntos en el área cuadrada a su alrededor. En el trabajo original, la siguiente fórmula se usa para calcular los lados de este cuadrado:
Quinto paso
Para cada punto de referencia, se calcula la diferencia en su brillo con el brillo de sus ocho vecinos. Para aquellos puntos para los que no hay vecinos (filas superior e inferior, columnas izquierda y derecha), la diferencia se toma como 0.
Además, estas diferencias se reducen a cinco gradaciones:
Resulta algo así como esta matriz:
Sexto paso
Creo que no se necesita explicación.
Y ahora sobre la optimización
En el trabajo original, se señala correctamente que a partir de la firma resultante es posible borrar completamente los valores cero a lo largo de los bordes de la matriz, ya que serán idénticos para todas las imágenes.
Sin embargo, si observa detenidamente, puede ver que para dos vecinos cualesquiera, sus gradaciones mutuas serán iguales en valor absoluto. Por lo tanto, de hecho, puede arrojar con seguridad cuatro valores duplicados para cada punto de referencia, reduciendo el tamaño de la firma a la mitad (excluyendo los ceros laterales).
Obviamente, al calcular la suma de los cuadrados, para cada
x definitivamente habrá un módulo igual
x ' y la fórmula para calcular la norma se puede escribir de la siguiente manera (sin entrar a reindexar):
Esto es cierto tanto para el numerador como para ambos términos del denominador.
Además en el trabajo original, se observa que tres bits son suficientes para almacenar cada gradación. Es decir, por ejemplo, en Unsigned Long cabrá 21 gradaciones. Este es un ahorro bastante grande en tamaño, pero, por otro lado, agrega complejidad al calcular la suma de los cuadrados de la diferencia entre dos firmas. Debo decir que esta idea realmente me enganchó con algo y no la solté por un par de días, hasta que una noche se dio cuenta de cómo
comer un pescado , un lugar para guardar y simplificar el cálculo. Cuídate las manos.
Utilizamos un esquema de almacenamiento de 4 bits por gradación:
Sí, solo 16 gradaciones encajarán en un Largo sin signo, contra 21, pero luego la matriz de la diferencia de las dos firmas se calculará con un xor y 15 cambios a la derecha con el cálculo del número de bits establecidos para cada iteración del cambio. Es decir
El signo no nos importa, ya que todos los valores serán al cuadrado.Además, si el valor umbral de la distancia se determina de antemano, cuyos valores ya no nos interesan, luego de bailar un poco en torno a la fórmula de cálculo, puede derivar una condición de filtrado bastante ligera para un conjunto simple de bits.
Se pueden encontrar más detalles sobre la optimización de este algoritmo, con ejemplos de código, en el
artículo anterior . Por separado, recomiendo leer comentarios al respecto: el residente de Khabrovsk,
masyaman, propuso varios métodos bastante interesantes para calcular, incluyendo gradaciones de empaque en tres bits, usando magia de bits.
En realidad, eso es todo. Gracias por su atencion :)