Veloce e semplice immagine algoritmo di hash

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

Alcune delle immagini sono “computer grafica” – solido-colore pieno invia: trasferisce, rasterizzati testi e ecc…. considerando che ci sono anche “fotografico” immagini contenenti ricca gamma di colori, per lo più liscia, con ragionevole rumore di ampiezza.

Mi piacerebbe anche l’algoritmo di hashing per essere in grado di essere applicate a specifiche parti dell’immagine. Voglio dire, l’immagine può essere diviso in una griglia di celle, e la funzione di hash di ogni cella dovrebbe dipendere solo il contenuto di questa cella. In modo che si possa spot rapidamente se le due immagini sono aree comuni (nel caso sono allineati in modo appropriato).

Nota: ho solo bisogno di sapere se le due immagini (o loro parti) sono identici. Che è, non ho bisogno di abbinare immagini simili, non c’è bisogno di una funzionalità di riconoscimento, di correlazione e di altre tecniche DSP.

Mi chiedo qual è il preferito algoritmo di hash.

Per “fotografico” immagini di XORING tutti i pixel all’interno di una cella della griglia è ok, più o meno. La probabilità che lo stesso valore di hash per le diverse immagini è piuttosto bassa, soprattutto perché la presenza di (quasi bianco) rumore rompe tutte le potenzialità di simmetrie. Più lo spettro di una funzione di hash sembra buono (qualsiasi valore è possibile con quasi la stessa probabilità).

Ma un ingenuo algoritmo non può essere utilizzato con “artificiale” della grafica. Identico pixel, ripetizione di modelli geometrici offset di invarianza sono molto comuni per tali immagini. XORING tutti i pixel darà 0 per ogni immagine, anche con un numero di pixel identici.

Di utilizzare qualcosa come CRT-32 guarda un po ‘ promettente, ma mi piacerebbe figura fuori qualcosa di più veloce. Ho pensato iterativo formula, ogni pixel muta il corrente valore di hash, come questo:

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

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

Grazie in anticipo.

  • perché non si utilizza un normale algoritmo di hash come md5?
  • Horvath: bella domanda. Infatti questo è quello che ho bisogno di più o meno. Tuttavia MD5 è (presumibilmente) affamate, è stato progettato per essere una one-way hash function. OTOH ho bisogno di qualcosa di molto più semplice, dato che non ho le considerazioni di sicurezza. Ho pensato a CRC-32. Ma mi piacerebbe figura fuori qualcosa di ancora più semplice
  • Se si esegue questa operazione su un sacco di immagini, il collo di bottiglia sarà la vostra velocità del disco..
  • Horvath: chi ha detto Che sarà su disco? Per essere precisi io ti do dello scenario di utilizzo: Ci saranno in genere fino a 100-200 le immagini memorizzate nella memoria (di varie dimensioni, “tipico” per un computer desktop, applicazioni). Ogni volta che io “vedo” una nuova immagine che voglio sapere se coincide con quello che ho visto in precedenza.
InformationsquelleAutor valdo | 2012-07-04



2 Replies
  1. 7

    Se si vuole fare è molto veloce, si dovrebbe considerare l’assunzione di un sottoinsieme casuale di pixel per evitare di leggere l’intera immagine. A quel punto, calcolare un hash funzione della sequenza di valori dei pixel. Il sottoinsieme casuale dovrebbe essere selezionata per impostazione deterministica generatore di numeri pseudo casuali con fisso seme in modo che immagini identiche identica sottoinsiemi e, di conseguenza, identici valori hash.

    Questo dovrebbe funzionare ragionevolmente bene anche per le immagini artificiali. Tuttavia, se si dispone di immagini che differiscono l’una dall’altra da un piccolo numero di pixel, questo sta per dare hash collisioni. Più iterazioni dare maggiore affidabilità. Se questo è il caso, per esempio, se le vostre immagini è probabile che le coppie con un solo pixel differenti, è necessario leggere attentamente ogni singolo pixel per calcolare il valore hash. Prendere una semplice combinazione lineare con pseudo-casuale coefficienti sarebbe abbastanza buoni, anche per le immagini artificiali.

    pseudo-codice di un algoritmo semplice

    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
    }
    
    • Grazie per la risposta. Non ho alcun problema a leggere l’intera cella della griglia. La mia celle della griglia sono piuttosto piccole (8×8 o 16×16). Inoltre, quando i valori hash di due immagini sono uguali – assicurare, tuttavia, che le immagini sono uguali. L’unico parametro mancante è la funzione di hash stesso. Che cosa dovrebbe essere?
    • Se non hai bisogno di protezione di crittografia, e solo preoccupato per le immagini artificiali, quindi una semplice combinazione lineare dei pixel con valori casuali coefficienti dovrebbero bastare, come ho descritto. Il problema è analogo a trovare l’hash di un intero array come v1 = [34,2,4,92,3], v2 = [10,3,5,20,3]. Il vostro obiettivo è per trovare un hash di loro per vedere quelli che sono uguali. Scegli una scelta casualmente fisso vettore m = [72,37,1,4,34] inizialmente. Per ogni vettore d’ingresso, il valore di hash di v1 v1*m = 34*72 + 2*37 + 4*1 + 92*4 + 3*34. È possibile calcolare questo numero modulo qualsiasi primo troppo, se ti piace.
  2. 7

    Dare un’occhiata a questo tutorial sul phash algoritmo http://www.hackerfactor.com/blog/index.php?/archives/432-Looks-Like-It.html che viene utilizzato per trovare strettamente corrispondenti immagini.

    • Grazie per la vostra attenzione, ma non è questo che voglio IMHO. L’algoritmo descritto è un bene per la ricerca di “simile” immagini, è anche la scala-invariante. Il mio problema è molto più semplice, e voglio un modo molto più efficiente soluzione
    • Ho aggiunto qualche informazione in più.

Lascia un commento