algoritmo de hashing de imagen rápido y simple

Question

Necesito un algoritmo de hashing de imagen (preferiblemente simple y rápido). El valor hash se usa en una tabla de búsqueda, no para criptografía.

Algunas de las imágenes son "gráficos de computadora", es decir, rectas llenas de color, textos rasterizados, etc., mientras que también hay imágenes "fotográficas" que contienen un amplio espectro de colores, generalmente suaves, con una amplitud de ruido razonable.

También me gustaría que el algoritmo hash pueda aplicarse a partes de imágenes específicas. Quiero decir, la imagen se puede dividir en celdas de cuadrícula, y la función de hash de cada celda debe depender solo del contenido de esta celda. Para que uno pueda detectar rápidamente si dos imágenes tienen áreas comunes (en caso de que estén alineadas apropiadamente).

Nota: Sólo necesito saber si dos imágenes (o sus partes) son idénticos . Es decir, no es necesario que coincida con imágenes similares, no hay necesidad de reconocimiento de características, correlación y otras técnicas DSP.

Me pregunto cuál es el algoritmo hash preferido.

Para imágenes "fotográficas" simplemente XOR-ing todos los píxeles dentro de una celda de cuadrícula está bien más o menos. La probabilidad del mismo valor hash para diferentes imágenes es bastante baja, especialmente porque la presencia del ruido (casi blanco) rompe todas las simetrías potenciales. Además, el espectro de dicha función hash se ve bien (cualquier valor es posible con casi la misma probabilidad).

Pero tal ingenuo algoritmo no se puede usar con gráficos "artificiales". Los píxeles idénticos, los patrones que se repiten, la invarianza de desplazamiento geométrico son muy comunes para tales imágenes. XOR-ing todos los píxeles darán 0 para cualquier imagen con un número par de píxeles idénticos.

Usar algo como CRT-32 parece algo prometedor, pero me gustaría descubrir algo más rápido. Pensé en la fórmula iterativa, cada nuevo píxel muta el valor hash actual, así:

hashValue = (hashValue * /*something*/ | newPixelValue) % /* huge prime */ 

Haciendo número primo módulo probablemente debería dar una buena dispersión, de modo que me estoy inclinando hacia esta opción. Pero me gustaría saber si hay mejores variantes.

Gracias de antemano.

Answer 1

Si desea hacerlo muy rápido, debe considerar tomar un subconjunto aleatorio de los píxeles para evitar leer toda la imagen. A continuación, calcule una función hash en la secuencia de valores en esos píxeles. El subconjunto aleatorio debe ser seleccionado por un generador de número pseudoaleatorio determinista con una semilla fija para que las imágenes idénticas produzcan subconjuntos idénticos y, en consecuencia, valores de hash idénticos.

Esto debería funcionar razonablemente bien incluso para imágenes artificiales. Sin embargo, si tiene imágenes que difieren entre sí por un pequeño número de píxeles, esto dará colisiones hash. Más iteraciones dan una mayor fiabilidad. Si ese es el caso, por ejemplo, si su conjunto de imágenes es probable que tenga pares con un píxel diferente, debe leer cada píxel para calcular el valor del hash. Tomar una combinación lineal simple con coeficientes pseudoaleatorios sería lo suficientemente bueno incluso para imágenes artificiales.

pseudo-código de un algoritmo

Random generator = new generator(2847) // Initialized with fixed seed 
int num_iterations = 100 

int hash(Image image) { 
    generator.reset() //To ensure consistency on each evaluation 
    int value = 0 
    for num_iteration steps { 
     int nextValue = image.getPixel(generator.nextInt()%image.getSize()).getValue() 
     value = value + nextValue*generator.nextInt() 
    } 
    return value 
} 

Answer 2

Echa un vistazo a este tutorial sobre el algoritmo phash http://www.hackerfactor.com/blog/index.php?/archives/432-Looks-Like-It.html que se utiliza para encontrar imágenes de cerca a juego.