Introducción a los Hashes perceptivos: Medición de la similitud

Compartir esta publicación

Compartir en facebook
Compartir en linkedin
Compartir en twitter
Compartir en email

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.

img

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:

Ei3 DnhricKbH dzVgskf68IZDJ9C93JK8exILCkCYIOMCSV8fCLnpAGPRqkd34FhZVN2vvrT1dzEiS5L mgWzWA6 fq 0bI9ZVhqjsChcJ7U5IUmhH A5hTQUwzFQ p K BOUe63LQ1AqSfA

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

xuaSWn ijMnneAxP7H qllp8Bgr3yVSvud3PGMbo6f8f5lENzHjw

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.

nqlWT1xINhvcP2RrvWrcKU InLbNTThiHk9socGLaU1IOhp97Z BlKQAZ6L6zQR1r 8dH86ar3zorQjfzhXvvAPreXFGw4bmELHS636l4mGG0r2 BA7onJ8FDYlRHUFExya3 FXGoFwZj8lRmw

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

0IzkUZjb dNX3K89MPHFA51BUocUkzd2WBmFSnrqsYlK6L8tAV

… y después por columna

Oo8vYE5az l1b1v 0x2398L1THDLGbne7 ezwKE0mU13bQdQi c2Se7rf7x41INdBTz8js4saYRkHdcA2A4tiS27Z

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.

w w5IXQKSWyJFKsfoCOlvNyi1Lp4SwLPdC72CK6lVg5 wIig4nyv7nwb48F4Zo63oh4cAjRWX36 bvHuV1GBWdhY6RNQBu3MAXbIeoJ o0eMCcXciX3O3Nyu447v Ai9R4MgoNEL9Ybr9Caekg

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

U65gTV9hpx ARY r23D0MtsVImGYupUAYwd3mzikhLO5hxPgm2WJp5atdGPfjx0f4XRE7qtlB 0ONlUvzMCwQzK5UYDwOnHeJe8g 3YW80nWislbu OSGsN5cZVJNmNFTEfTaskbuzMz8KZUkA

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 #1Imagen #2
9dtGwsIycVXveee92jc VPBVRfa3nA0BOrIJ1rFe8we I1I3hmSOUUqgrMxLQlfNJmoF9poKk OWVzQz16fh8WdStb4V6f6InP5bw1 Z2N9DoBFIbjuC3UrOL owH62gFWrpmOurPr9AYV IgUznE8rmkOsVMZWrNASsuLvfYWe44Eo1s ux69SzBNr2BNRVkhZNFM6GRfK Bt4OOFCAHF4zXaLNFuvsQryhm7eD5HJv innnKF88 rIsy3O6wYE4kdcHa0IP xGRg6qwJBmOQi GMV F36uaA
ImagenpHash
#10011110000111110000011100001101000111010000111100001111000011110
#20011110000111110000011100011111000111110000111100001111000011110

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

Ejemplo #2

Imagen #1Imagen #2
pfp9iiZzgZyeSicYHorBcRsIQ b0I1jpMKD5hMBpJjVdGigQHEPyFyRujxFZ9aaMkM7u24a8gtWa79bU2BVd3SwtquVS2u
ImagenpHash
#100101000101010001010100010101000101010110010101101010010100010101000111100110111
#200101000101010001010100010101000101010110010101101010010100010101000111100110111

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada.

Suscríbete a nuestro boletín de noticias

Recibe actualizaciones de los últimos descubrimientos tecnológicos

Acerca de Apiumhub

Apiumhub reúne a una comunidad de desarrolladores y arquitectos de software para ayudarte a transformar tu idea en un producto potente y escalable. Nuestro Tech Hub se especializa en Arquitectura de Software, Desarrollo Web & Desarrollo de Aplicaciones Móviles. Aquí compartimos con usted consejos de la industria & mejores prácticas, basadas en nuestra experiencia.

Posts populares
Obtén nuestro Libro: Software Architecture Metrics

Global Software Architecture Summit '22

Reserva tu plaza!

Reserva

¿Tienes un proyecto desafiante?

Podemos trabajar juntos

Secured By miniOrange