Métrica para encontrar imágenes similares en una base de datos

Question

Hay muchos algoritmos diferentes para calcular la similitud entre dos imágenes, pero no encuentro nada sobre cómo almacenar esta información en una base de datos para que pueda encontrar imágenes similares rápidamente .

Por "similar" me refiero a duplicados exactos que se han girado (incrementos de 90 grados), ajustados por color y/o rescatados (compresión jpeg con pérdida).

Estoy tratando de obtener un "fingerprint" de las imágenes para que pueda buscarlas rápidamente.

Lo mejor que he encontrado hasta ahora es generate a grayscale histogram. Con 16 contenedores y 256 tonos de gris, puedo crear fácilmente una huella digital de 16 bytes. Esto funciona bastante bien, pero no es tan robusto como me gustaría.

Otra solución que probé fue cambiar el tamaño de las imágenes, rotate them, todas orientadas de la misma manera, escala de grises, normalizar los histogramas, reducirlos a 8x8 y reducir los colores a 16 tonos de gris . Aunque las imágenes en miniatura eran muy similares, por lo general estaban apagadas por un píxel o dos, lo que significa que la coincidencia exacta no puede funcionar.

Sin coincidencia exacta, no creo que haya ninguna manera eficiente de agrupar fotos similares (sin comparar cada foto con cada otra foto, es decir, O (n^2)).

Entonces, (1) ¿Cómo puedo crearlo? Creo una huella digital/firma que es invariante a los requisitos mencionados anteriormente? O bien, (2) si eso no es posible, ¿qué otra medida puedo usar de manera tal que, dada una imagen única, puedo encontrar sus mejores coincidencias en una base de datos de miles?

Answer 1

Hay una pequeña cosa confusa en su pregunta: la "huella digital" que vincula a decir explícitamente no la intención de encontrar imágenes similares (cita):

TinEye no suele encontrar imágenes similares (es decir, una diferente imagen con el mismo tema); Encuentra las coincidencias exactas, incluidas las que han sido recortadas, editadas o redimensionadas.

Ahora, dicho esto, voy a suponer que usted sabe lo que está preguntando, y que realmente desea poder encontrar todas las imágenes similares, no solo las copias exactas editadas.

Si quiere tratar de entrar en detalles, le sugiero que busque documentos por Sivic, Zisserman y Nister, Stewenius. La idea que estos dos documentos (y muchos otros últimamente) han usado es intentar aplicar técnicas de búsqueda de texto a bases de datos de imágenes, y buscar en la base de datos de imágenes de la misma manera que Google buscaría su documento (página web)) base de datos.

El documento first al que me he vinculado es un buen punto de partida para este tipo de enfoque, ya que aborda principalmente la gran pregunta: ¿Cuáles son las "palabras" en las imágenes?. Las técnicas de búsqueda de texto se centran en las palabras y basan sus medidas de similitud en los cálculos, incluidos los recuentos de palabras. La representación exitosa de imágenes como colecciones de palabras visuales es, por lo tanto, el primer paso para aplicar técnicas de búsqueda de texto a bases de datos de imágenes.

El documento second expande la idea de usar técnicas de texto, presentando una estructura de búsqueda más adecuada. Con esto, permiten una recuperación de imágenes más rápida y bases de datos de imágenes más grandes.También proponen cómo construir un descriptor de imagen basado en la estructura de búsqueda subyacente.

Las funciones utilizadas como palabras visuales en ambos documentos deben cumplir sus restricciones de invariancia, y la segunda definitivamente debe poder trabajar con el tamaño de base de datos requerido (tal vez incluso el enfoque del primer documento funcionaría).

Finalmente, recomiendo buscar documentos más recientes de los mismos autores (estoy seguro de que Nister hizo algo nuevo, es solo que el enfoque del documento vinculado ha sido suficiente para mí hasta ahora), buscando algunas de sus referencias y simplemente en general buscando documentos relacionados con Imagen basada en contenido (indexación y) recuperación (CBIR) - es un tema muy popular en este momento, por lo que debería haber suficiente.