Otra de las aplicaciones útiles de los hashes de imágenes, especialmente aquellos que comparan perceptualmente y no estructuralmente, como dHash, son los motores de búsqueda.
En el presente artículo crearemos un motor de búsqueda de imágenes basado en hashes de imágenes, almacenados en una estructura de datos especial, conocida como VP-Tree.
¿Por qué? ¿Qué tiene de especial este tipo de árbol? ¡Sigue leyendo para descubrirlo!
Al final de este artículo habrás aprendido:
¿Preparado? ¡Comencemos!
Los Motores de Búsqueda y la Escalabilidad
La clave para entender las decisiones de implementación tomadas en este artículo radican en esta sección.
En primer lugar, tenemos que repasar cuáles son los elementos básicos de un motor de búsqueda de imágenes:
Un descriptor de imágenes o, en términos más sencillos, un mecanismo para convertir imágenes en vectores con mínima pérdida de información
Un índice de imágenes
Una métrica o función de similitud apropiada para ver qué tan cerca se encuentran dos imágenes con base en su descriptor.
Un buscador como tal
¡ATENTO!
Si deseas ahondar más en los componentes de un motor de búsqueda, te recomiendo que leas este artículo.
Parece una lista de componentes bastante razonable, ¿no?
Sí, indudablemente. Sin embargo, no hay mejor manera de añadir ingentes cantidades de complejidad a un problema aparentemente sencillo que escalándolo, y es ahí cuando crear un motor de búsqueda de imágenes usable, responsivo, se vuelve una tarea mucho más difícil.
El problema de la escalabilidad se reduce a esto:
Mientras más imágenes tienes, más se demora la búsqueda.
No hay manera de escapar a esta realidad; lo único que podemos hacer es mitigarla mediante una serie de decisiones inteligentes, empezando por cómo indexamos y cómo almacenamos las entradas del motor.
Imagina que tenemos este escenario:
Ahora, un usuario nos pasa una imagen como término de búsqueda. El proceso para obtener los resultados sería el siguiente:
- 1Calculamos el hash de la imagen de entrada.
- 2Comparamos el hash con cada una de las 500.000 imágenes.
- 3Mantenemos una lista de las N imágenes más parecidas a la de entrada.
- 4Retornamos el resultado.
El hecho de que tengamos que comparar cada hash en nuestro índice con el de la imagen de entrada es una mala señal, ya que aún si la comparación tardase 0,00001 segundos, nos tardaríamos 5 segundos en devolver los resultados.
Si nuestro motor de búsqueda es un éxito y decidimos expandirlo con otras 500.000 imágenes, estamos hablando de 10 segundos por búsqueda.
INACEPTABLE.
¿Qué hacemos? Podemos empezar por utilizar estructuras de datos especializadas en la escalabilidad, como los VP-Trees.
Una Breve Introducción a los VP-Trees
Una de las estructuras de datos que nos facilita reducir de manera drástica el tiempo de búsqueda (concretamente, de O(n) a O(log n)) es el VP-Tree, cuyo nombre completo en inglés es Vantage-point Trees y, en español, Árboles de Punto de Ventaja.
Estructura de un VP-Tree. Los rectángulos verdes corresponden a los puntos de ventaja. Fuente: https://everyhue.me/media/3016/vptree.png
Los VP-Trees son árboles métricos, que separan los datos en un espacio métrico, donde se escoge un determinado punto en ese espacio, conocido como “vantage point” o “punto de ventaja”, para particionar los elementos en dos conjuntos:
- 1Puntos cercanos al punto de ventaja.
- 2Puntos lejanos al punto de ventaja.
El punto de ventaja es el verde. Aquellos que están fuera del círculo se consideran elementos lejanos, mientras que los que están dentro de la circunferencia se consideran cercanos. Fuente: https://everyhue.me/media/3016/left_right_child.png
Para construir el árbol, aplicamos el procedimiento anterior recursivamente, lo que conduce a una partición de los puntos en conjuntos cada vez más pequeños. El resultado es un árbol donde los nodos vecinos tienen distancias pequeñas entre sí.
¡ATENTO!
Un espacio métrico, en matemáticas, es un conjunto asociado a una métrica. Los puntos o elementos en dicho conjunto están organizados con base a esta métrica, usualmente conocida como función de distancia.
Un ejemplo clásico de un espacio métrico es el espacio tridimensional euclidiano (es decir, el conjunto de puntos del estilo (x, y, z), siendo la métrica de dicho espacio la función de distancia euclidiana).
En nuestro proyecto de Python usaremos una librería de Python que implementa los VP-Trees en un API muy fácil de usar. Más concretamente:
CALTECH 101
Muestra de imágenes de CALTECH 101.
El conjunto de datos sobre el que indexaremos nuestro motor de búsqueda, no es otro que el célebre CALTECH 101, el cual consiste de 9.146 imágenes, distribuidas en, evidentemente, 101 categorías entre las que destacan aviones, motocicletas, camiones, cámaras fotográficas e incluso rostros.
Como ya mencioné en el párrafo anterior, la idea del post de hoy es implementar un motor de búsqueda sobre estas imágenes.
Creación del Entorno de Programación con virtualenv
Empecemos ojeando la estructura del proyecto:
Estructura del proyecto
El código fuente se compone de estos tres archivos:
Debido a que la librería vptree no está disponible en Anaconda, usaremos una herramienta familiar para aislar nuestro ambiente de desarrollo: virtualenv.
Para crear y activar el ambiente, ejecuta estas instrucciones en tu terminal:
Después, tendrás que instalar las siguientes librerías:
Para ello, apóyate en pip, así:
pip install -r requirements.txt
Voilà.
Creando un Motor de Búsqueda con Hashing de Imágenes en OpenCV
Como nuestro motor de búsqueda se fundamenta en los hashes perceptuales (calculados con el algoritmo dHash) de las imágenes, usaremos las funciones auxiliares dhash() y hamming() para, respectivamente, calcular el dHash de una imagen digital, y luego calcular la distancia Hamming entre dos hashes. Ambas funciones están definidas en datasmarts/utils.py:
¡ATENTO!
Cubrí los detalles de estas dos funciones (y mucho más) en este artículo.
El siguiente paso es crear nuestro programa de indexación. Abre datasmarts/index.py e importa las dependencias del script:
Define los parámetros del programa:
Creamos una lista de las rutas a las imágenes a indexar:
Iteraremos sobre cada ruta, abriendo la imagen en la ubicación indicada por la misma con el fin de calcular su dhash y añadirlo al índice hashes:
El siguiente paso es construir el VP-Tree. Fíjate que tenemos que pasarle dos parámetros al constructor:
Por último, serializamos y guardamos los hashes y el VP-Tree. Estos serán útiles en el siguiente programa:
Ahora abre el archivo datasmarts/search.py, que como su nombre indica, contiene la lógica del buscador, e inserta estas líneas para importar las dependencias del programa:
Define los parámetros del programa:
Cargamos el VP-Tree y los hashes:
Leemos la imagen de consulta y la mostramos en pantalla:
Calculamos el dhash de la imagen de consulta:
Usamos el método get_all_in_range() del VP-Tree para traernos los hashes que están a lo sumo 10 unidades (si usamos el valor por defecto de -d/--distance) Hamming de distancia de la imagen de consulta, y ordenamos los resultados de menor a mayor distancia:
Buscamos las imágenes asociadas a los hashes que obtuvimos del árbol, y las mostramos en pantalla, ya que constituyen el resultado del motor de búsqueda:
Para indexar el conjunto de datos, podemos correr este comando:
python datasmarts/index.py -i D:\Data\101_ObjectCategories -t vptree.pickle -a hashes.pickle
Este proceso se demorará en proporción a la cantidad de imágenes. En mi caso, se tomó aproximadamente 30 segundos.
Luego, podemos llevar a cabo una búsqueda así:
python datasmarts/search.py -t vptree.pickle -a hashes.pickle -q queries/image_0009.jpg
Puedes ver el resultado en este video:
Genial, ¿no crees? Aunque algunas de las imágenes resultantes no parecen contener el mismo objeto de la imagen de consulta. Es posible que tengamos que probar con distintos valores de -d/--distance hasta obtener resultados más convincentes.
Resumen
Hoy aprendimos que los motores de búsqueda de imágenes constituyen el contexto ideal para usar hashes perceptuales de imágenes, ya que como vimos en la introducción de este artículo, uno de los ingredientes principales de un buscador es un descriptor de imágenes… qué es lo que, al final del día, es un hash.
Sin embargo, por muy bueno que sea dHash creando representaciones vectoriales de las imágenes indexadas por nuestro buscador, el mayor desafío tiene que ver con la escalabilidad, puesto que si diseñamos nuestro sistema de manera tal que retorne resultados lo más rápido posible, su usabilidad se verá severamente afectada.
Afortunadamente, podemos incrementar la velocidad de respuesta usando estructuras de datos especialmente diseñadas para la escalabilidad, como los VP-Trees, un árbol que almacena los puntos (en este caso, hashes) en ubicaciones estratégicas basadas en puntos de ventaja, de forma que los nodos vecinos tienen distancias pequeñas entre sí.
El mayor beneficio de usar un VP-Tree como espina dorsal de nuestro motor de búsqueda, es que pasamos de una complejidad lineal (O(n)) a una logarítmica (O(log n)). Cool, ¿no?
¿Por qué no te descargas el código para seguir experimentando, y ver si puedes conseguir mejorar los resultados del buscador?
¡Adiós!
