Introducción

Comprobar si los archivos son idénticos es una tarea excesivamente trivial. Es posible comparar directamente todos sus bytes o tal vez calcular un hash de cada archivo y comparar esos valores, pero intentar comparar la similitud del contenido de los archivos es más difícil.

¿Qué significa la similitud? 

¿Cómo puede un ordenador determinar si dos fotos tienen el mismo contenido después de haber sido redimensionadas o comprimidas varias veces?

Debido a la naturaleza con pérdidas de la mayoría de los algoritmos de compresión de imágenes, es imposible comparar los bytes de las imágenes para determinar si tienen el mismo contenido.

Cada vez que se descodifica y codifica una imagen JPEG, se cambian o se pierden datos adicionales. Mientras que los formatos como PNG no tienen pérdidas, el cambio de tamaño de las imágenes también cambiará su contenido, lo que impide las comparaciones directas.

Hay una gran variedad de algoritmos de hashing de imágenes, siendo algunos de los más populares:

• Average Hashing (aHash)
• Median Hashing (mHash)
• Perceptual Hashing (pHash)
• Difference Hashing (dHash)
• Block Hashing (bHash)
• Wavelet Hashing (wHash)
• ColorMoment Hashing

Los algoritmos criptográficos de hash como el MD5 o el SHA256 están diseñados para generar un resultado impredecible. Para ello, están optimizados para cambiar tanto como sea posible para entradas similares. Los hash perceptivos son lo contrario: están optimizados para cambiar lo menos posible para entradas similares. El algoritmo pHash calcula el hashing sobre la Transformada Discreta de Coseno (DCT) que transforma los datos del dominio espacial al dominio de la frecuencia.

Perceptual Hashes (pHashes)

Como se ha señalado anteriormente, esta familia de algoritmos está diseñada para no cambiar mucho cuando una imagen sufre pequeñas modificaciones, como la compresión, la corrección del color y el brillo. El pHashes permite comparar dos imágenes teniendo en cuenta el número de bits diferentes entre la imagen de entrada y la imagen con la que se compara. Esta diferencia se conoce como distancia de Hamming.

Una forma muy sencilla de utilizar este algoritmo sería crear una lista de todas las imágenes conocidas y su hash perceptivo. La distancia hamming se puede calcular con sólo una instrucción xor y popcnt en las CPUs modernas. Este enfoque sería bastante rápido para empezar. Con decenas de miles de imágenes, sería posible obtener resultados en unos pocos segundos, lo que probablemente sea un rendimiento aceptable.

Cuando la cantidad de imágenes empieza a crecer hasta los millones, escanear y comparar secuencialmente contra cada imagen lleva demasiado tiempo. Dado que el hash tiene que ser calculado contra la entrada cada vez, un índice convencional no sería utilizable. 

Afortunadamente, aquí se puede utilizar un BK-tree -un árbol diseñado específicamente para espacios métricos como la distancia de Hamming- en lugar de tener que buscar en cada imagen de la base de datos, lo que reduce en gran medida el espacio necesario para la evaluación.

¿Cómo funciona pHashes?

A continuación se muestra una demostración de cómo funciona pHash utilizando la siguiente imagen como fuente:

El algoritmo pHash calcula inicialmente el valor de gris de la imagen y lo reduce.

En este caso se utiliza un factor de 4, por lo que la imagen se reduce a 8*4×8*4, es decir, una imagen de 32×32.

A esta imagen se le aplica una transformada de coseno discreto, primero por fila…

… y después por columna

Los píxeles con frecuencias altas se encuentran ahora en la esquina superior izquierda, por lo que la imagen se recorta en los 8×8 píxeles superiores izquierdos.

A continuación, calcula la mediana de los valores de gris de esta imagen

Y por último, genera un valor hash de la imagen.

1010010010101101100110011011001101100010100100000111011010101110

Algunos casos de uso relevantes

Gestión de derechos digitales

La protección de los derechos de propiedad intelectual y la gestión de los datos multimedia es esencial para el despliegue de los sistemas de comercio electrónico que implican transacciones sobre dichos datos.

La detección precoz de los recursos sujetos a derechos de autor evita problemas legales complejos y costosos

Deduplicación de datos

pHash proporciona una métrica sobre la similitud entre dos fuentes, que evita la duplicación en el conjunto de datos principal.

La optimización del conjunto de datos principal no sólo supone una mejora en términos de contenidos curados, sino también en términos de costes de infraestructura.

Motor de búsqueda inversa de imágenes

El comercio electrónico es una industria en crecimiento que se ha convertido en una parte notable de los hábitos de muchos consumidores; por ello, muchos sitios intentan aportar nuevas características a las herramientas de filtrado y comparación para mejorar la experiencia del usuario. Una de estas características es permitir a los clientes encontrar productos por una foto para sugerir la coincidencia exacta en caso de éxito o los productos más similares en otros casos. Es lo que se llama un motor de búsqueda inversa de imágenes.

Secuenciación del ADN

Cada nucleótido se codifica como un píxel de intensidad de nivel de gris fijo cuyo hash se calcula a partir de sus características de frecuencia significativa. Esto da lugar a una drástica reducción de datos entre la secuencia y el hash perceptivo, lo que permite a los científicos y genetistas realizar búsquedas masivas y comparar millones de combinaciones con un bajo impacto en la infraestructura.

Detección de signos de enfermedad

En el campo de la agricultura, hay muchas enfermedades destructivas, por ejemplo, las enfermedades de las hojas, que son las más frecuentes y en las que se producen manchas en las hojas. Si estas manchas no se detectan a tiempo, pueden causar graves pérdidas. Para detectar las enfermedades de las hojas, se emplean técnicas de procesamiento de imágenes, muchas de ellas basadas en pHashes.

Implementación en PHP

$ composer require jenssegers/imagehash

<?php

[...]

use Jenssegers\ImageHash\ImageHash;
use Jenssegers\ImageHash\Implementations\DifferenceHash;

$hasher = new ImageHash(new DifferenceHash());

$hash1 = $hasher->hash('path/to/image1.jpg');
$hash2 = $hasher->hash('path/to/image2.jpg');

$distance = $hasher->distance($hash1, $hash2);

Ejemplo #1

Imagen #1	Imagen #2

Una comparación del hash binario revela sólo 3 bits diferentes, por lo que la distancia Hamming es 3.

Ejemplo #2

Imagen #1	Imagen #2

Una comparación del hash binario revela 39 bits diferentes, por lo que la distancia Hamming es de 39.