Algoritmo di hashing dell'immagine semplice e veloce

Question

Ho bisogno di un algoritmo di hashing dell'immagine (preferibilmente semplice e veloce). Il valore di hash viene utilizzato in una tabella di ricerca, non per la crittografia.

Alcune delle immagini sono "computer graphic" - cioè ripieni a colori pieni, testi rasterizzati e così via, mentre ci sono anche immagini "fotografiche" - contenenti uno spettro di colori ricco, per lo più regolare, con un'ampiezza di rumore ragionevole.

Mi piacerebbe anche che l'algoritmo di hash potesse essere applicato a specifiche parti dell'immagine. Voglio dire, l'immagine può essere divisa in celle di griglia e la funzione di hash di ogni cella dovrebbe dipendere solo dal contenuto di questa cella. In modo che si possa individuare rapidamente se due immagini hanno aree comuni (nel caso siano allineate in modo appropriato).

Nota: Ho solo bisogno di sapere se due immagini (o loro parti) sono identici . Cioè, non ho bisogno di abbinare immagini simili, non c'è bisogno di riconoscimento delle funzioni, correlazione e altre tecniche DSP.

Mi chiedo quale sia l'algoritmo di hashing preferito.

Per le immagini "fotografiche", solo XOR-in tutti i pixel all'interno di una cella della griglia è ok più o meno. La probabilità dello stesso valore di hash per immagini diverse è piuttosto bassa, soprattutto perché la presenza del rumore (quasi bianco) rompe tutte le simmetrie potenziali. Inoltre, lo spettro di tale funzione di hash sembra buono (qualsiasi valore è possibile con quasi la stessa probabilità).

Ma un algoritmo così ingenuo non può essere utilizzato con la grafica "artificiale". Pixel identici, pattern ripetuti, invarianza di offset geometrica sono molto comuni per tali immagini. XOR-tutti i pixel daranno 0 per ogni immagine con un numero pari di pixel identici.

L'utilizzo di qualcosa come CRT-32 sembra un po 'promettente, ma mi piacerebbe immaginare qualcosa di più veloce. Ho pensato di formula iterativa, ogni nuovo pixel muta il valore hash corrente, in questo modo:

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

Facendo numero primo modulo dovrebbe probabilmente dare una buona dispersione, in modo che io sto sporgendosi verso questa opzione. Ma mi piacerebbe sapere se ci sono varianti migliori.

Grazie in anticipo.

Answer 1

Se si desidera renderlo molto veloce, è consigliabile prendere in considerazione un sottoinsieme casuale dei pixel per evitare di leggere l'intera immagine. Quindi, calcola una funzione hash sulla sequenza di valori a quei pixel. Il sottoinsieme casuale deve essere selezionato da un generatore di numeri pseudo-casuali deterministico con seme fisso in modo che le immagini identiche producano sottoinsiemi identici e di conseguenza hash identici.

Questo dovrebbe funzionare abbastanza bene anche per le immagini artificiali. Tuttavia, se si dispone di immagini che differiscono l'una dall'altra per un piccolo numero di pixel, questo darà collisioni di hash. Altre iterazioni danno una maggiore affidabilità. Se questo è il caso, ad esempio, se è probabile che le tue immagini abbiano coppie con un pixel diverso, devi leggere ogni pixel per calcolare il valore hash. Prendere una semplice combinazione lineare con coefficienti pseudo-casuali sarebbe abbastanza buono anche per le immagini artificiali.

pseudo-codice di un semplice 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

Date un'occhiata a questo tutorial l'algoritmo phash http://www.hackerfactor.com/blog/index.php?/archives/432-Looks-Like-It.html che viene utilizzato per trovare le immagini corrispondenti a stretto contatto.