¿Cómo encontrar imágenes similares con Python?

El problema: imágenes que no coinciden (y deberían coincidir)

Una de las tareas en Librera implica recopilar la información de un libro en base a su ISBN, para lo cual en algunos casos se recurre al webscraping.

En algunos casos, al obtener la portada de un libro desde algún servicio externo como Google Books API, Goodreads API o scrapeando alguna web verificábamos que obteníamos una portada incorrecta.

Nuestro proceso para obtener la portada de un libro implicaba:

Consultar varias fuentes (API's)
Escoger la portada en base al tamaño de la imagen, ya que un mayor tamaño, véase ancho x alto implicaba "mayor calidad".

Nota: No descargamos cada imagen, sino que tan solo verificábamos los primeros bits del archivo, ya que allí se encuentra información como las medidas de la misma.

Pero con el tiempo notamos que algunas portadas no coincidían por equis motivos (luego se vio que esto era un 0.005% o menos de las imágenes)

La solución: comparar imágenes para encontrar coincidencias

Crear un script que descargue la portada de varias fuentes y las compare. La portada "escogida" además de tener el mayor tamaño, debe ser similar a alguna de las otras portadas, ya que es "altamente improbable" que el error se produzca entre varias fuentes.

Y es por ello que escribo este post, resumiendo mi pequeña investigación sobre el tema.

Algoritmos para crear "hash" de imágenes

La comparación de las imágenes la podemos realizar de varias formas. En este caso, utilizaremos un hash¹, que sería un string que actua a modo de resumen de cada imagen.

Los hash creados se deben caracterizar por:

Ser únicos para cada imagen
Si una imagen sufre una ligera variación, el hash resultante debe variar mínimamente también.

Para nuestras pruebas usaremos el cover del libro "Toda Mafalda":

cover de toda mafalda

Existen algunos algoritmos usualmente empleados en estos temas y son:

Average Hash

El procedimiento del cálculo es el siguiente:

Generar una miniatura con tamaño fijo de la imagen: de este modo los cálculos serán más rápidos de realizar y los tamaños se homogenizan. Podemos trabajar con la medida de 8x8 con lo que tendremos 64 píxeles.
Reducimos los colores transformando la imagen a escala de grises.
Realizamos el cálculo de la media de los 64 valores
Ahora revisamos si cada bit es mayor o menor a la media, con lo que tendremos 64 bits (0 o 1)
Construimos el hash: transformamos la cadena de valores binarios a hexadecimal con lo que tendremos algo similar a: *ffffeff1e1e0661c *

proceso de average hash

Perceptual Hash

Debido a su implementación, el algoritmo de Average Hash es rápido y sencillo, pero también debido a su naturaleza, puede llegar a generar varios falsos positivos al momento de comparar imágenes similares cuando se realizan ajustes al "gama" de la imagen.

El proceso es:

Escalamos la imagen, pero a diferencia del algoritmo "Average Hash" se recomienda utilizar un mayor tamaño como "32x32"
Reducimos los colores transformando la imagen a escala de grises.
Calculamos la DCT o [Transformada de cosenos discreta]²
Reducimos la DCT: El cálculo anterior nos brinda una matrix de 32x32, pero solo tomaremos los 8x8 píxeles del lado superior izquierdo, lo que nos representa las menores frecuencias
Calculamos el valor promedio (similar al algoritmo anterior)
Cálculamos el hash: establecemos los 64 bits en 0 o 1 según si cada valor supera o no el valor promedio calculado
Construimos el hash: transformamos la cadena de valores binarios a hexadecimal con lo que tendremos algo similar a: e6cd90620d947bce

Otros algoritmos

Tenemos otros algoritmos que pueden ser revisados en las referencias al final del post como:

Block Hash
Diference Hash
Wavelet Hash
Median Hash

¿Cómo comparamos los hashes de las imaǵenes?

Para nuestras pruebas, ajustamos el brillo, contraste y escala de la imagen original para analizar los hashes:

comparación de imágenes

Asumiendo que hemos calculado el hash escogido para nuestras imágenes, ¿cómo los comparamos?

Utilizamos un método conocido como Distancia de Hamming³.

Para las imágenes de prueba, los phash (perceptual hash) son:

    e6cd90620d947bce
    e6ed90e609947b8c

La distancia de hamming calcula el número de bits que deben cambiar entre dos cadenas para ser idénticas.

En este caso, el resultado es de "6", y al ser menor a 10 según algunos autores (Dr. Neal Krawetz) se podría decir que las imágenes son similares.