Como comenté en un articulo anterior sobre la detección de Spam en Imágenes, uno de los métodos es la identificación de imágenes duplicadas o casi duplicadas (Near-duplicate detection).

Este proceso consiste de dos partes:

1. La creación de un LSH (Locality Sensitive Hash), es decir, crear una especie de “firma” que tenga la propiedad de que dos imágenes que se parezcan tengan dos firmas parecidas y que dos imágenes que no se parezcan tengan firmas diferentes.
2. Tener estas firmas en una base de datos para dada una “firma” buscar si hay alguna otra imagen cuya firma se parezca lo suficiente.

Existen muchas formas de crear la firma, por ejemplo con el uso de Haar Wavelet, Histogramas de colores, etc. Sin embargo, la parte de la búsqueda es la realmente complicada.

Una firma, puede consistir de 128, 200 o más números enteros. Estas firmas pueden ser vistas como un vector de tantas dimensiones como números la compongan, y de ahí que el título del artículo se refiera a espacios de alta dimensionalidad.

Debido a que buscar los duplicados de una imagen particular (imagen query) es encontrar algún otro “vector” en una base de datos cuya distancia a la imagen query sea menor a cierto umbral, estas búsquedas no son manejables con un sistema de base de datos convencional (No sin recorrer toda la base de datos a cada consulta y calcular la distancia de la imagen query con todas las imágenes de la BBDD).

Sin embargo, hay alternativas. La mayoría de ellas tienen que ver con reducciones dimensionales, es decir tratar de representar en menos dimensiones (con menos números) los mismos datos. Esto resulta bastante bien cuando la data es dispersa, ya que probablemente muchas dimensiones no aporten casi información (por ejemplo, en las estructuras de datos utilizadas para la detección de Spam con SVM (Support Vector Machines) en la que cada palabra es una dimensión y el valor de esa dimensión es la cantidad de veces que aparece la palabra en el texto.

Pero cuando la data no es esparcida, los métodos que se basan exclusivamente en reducciones dimensionales no son tan atractivos.

Es por esto que la propuesta descrita en: Indexing High-Dimensional Data for Efficient In-Memory Similarity Search resulta muy interesante.

En este paper se propone la creación de una estructura llamada un delta-tree, en el que los niveles superiores (más cercanos a la raíz) son de dimensiones menores que los inferiores (de hecho las “hojas” del árbol son los datos sin ninguna reducción dimensional).

Lo que más me llamó la atención fue la forma en la que se realiza la reducción dimensional: SVD:  Singular Value Decomposition. Esta técnica te permite reducir la dimensionalidad de la data con una propiedad interesante:

Dados dos puntos x1 y x2 en el espacio m-dimensional de origen, y dados y1 y y2 sus “versiones reducidas”  en el espacio n-dimensional (con n < m),

d(x1,x2) ≤ d(y1,y2), donde d(a,b) es la distancia que hay entre a y b.

De esta forma se puede recorrer el árbol, descartando las ramas que ya se encuentran muy lejos (por encima del umbral) con menos dimensiones (y por lo tanto menos cálculos) y centrar la búsqueda en las dimensiones superiores en un espacio mucho menor.

Esto me parecía muy bueno para ser verdad, así que me instalé SciLab que es un excelente reemplazo gratis de Matlab (as in beer and in speech), hice una prueba de esta reducción dimensional y comprobé la regla de las distancias empíricamente.

Creé de forma aleatoria una matriz de datos (50 puntos), cada uno de ellos en un espacio de 20 dimensiones, la reduje a 15, 10 y 5 dimensiones y comparé las distancias entre los puntos entre las distintas dimensiones y obtuve gráficos como este:

Un punto de este gráfico se obtiene de la siguiente forma:

Coordenada x = distancia entre los puntos xi y xj en el espacio original (20 dimensiones)

Coordenada y = distancia entre los puntos xi y xj en el espacio reducido (15 dimensiones en este caso)

Como se puede ver existe una gran cercanía de estos puntos a la recta y=x (la correlación de los puntos en la gráfica de 15 dimensiones es de 0.95), con lo que se puede ver que hay una correlación entre las distancias en el espacio original y el espacio reducido.

Haciendo lo mismo con 10 y luego 5 dimensiones obtuve:

Como es lógico se redujo más la correlación pues se pierde más información en la reducción dimensional, pero sigue habiendo una fuerte relación entre las distancias en ambos espacios.

Y, finalmente, con una reducción a 5 dimensiones obtuve:

En el que la correlación si bien existe es bastante débil.

Sin embargo, incluso en este escenario en el que se pierde tanta información por la reducción dimensional, logré verificar que se mantiene la asumpción sobre que las distancias en menores dimensiones son menores que en mayores dimensiones, y por lo tanto el esquema propuesto sirve.

No conozco ningún manejador de base de datos que pudiere utilizar para representar esto… así que supongo que tendré que crear uno