Locality Sensitive Hash oder pHash?

Question

Ich versuche einen allgemeinen Fingerabdruck memoizator zu implementieren: wir haben eine Datei, die durch einen intelligenten Fingerabdruck (wie pHash für Bilder oder chromaprint für Audio) ausgedrückt werden kann und wenn unsere berechnete (teure) Funktion bereits auf berechnet wurde ähnlich Datei, dann geben wir das gleiche Ergebnis (Vermeidung teurer Berechnung).

Locality Sensitive Hash (LSH) ist eine beliebte und gut performante Lösung für das Approximate nearest neighbor Problem in einem teuren mehrdimensionalen Raum.

pHash ist eine gute Bibliothek, die perzeptuelles Hashing für Bilder implementiert.

Also transformiert pHash eine mehrdimensionale Eingabe (ein Bild) in ein eindimensionales Objekt (einen Hash-Code), was etwas anders ist als LSH (wiederum mehrdimensionale Objekte in LSH).

Also frage ich mich, wie wir eine eindimensionale LSH für pHash-Hash-Werte implementieren könnten? Oder in wenigen Worten: Wie können wir ähnliche pH-Werte in Behältern gruppieren? Könnte es eine Alternative zum klassischen LSH-Ansatz sein (und wenn nicht warum)?

Answer 1

Sie könnten nrandom projections verwenden, um den pHash-Raum in 2^n Buckets aufzuteilen, dann werden ähnliche Bilder höchstwahrscheinlich aus demselben Bucket gefunden. Sie könnten sogar den Hash mit allen 64 möglichen Ganzzahlen mit Hamming-Gewicht 1 XOR, um benachbarte Eimer bequem zu überprüfen und sicher sein, dass Sie alle ungefähren Übereinstimmungen finden würden.

Dies ist nur effizient, wenn Sie Bilder mit fast identischen Hashes (kleine Hamming-Distanz) interessieren. Wenn Sie größere Hamming-Distanzen tolerieren möchten (z. B. 8), wird es schwierig, alle Treffer effizient und genau zu finden. Ich habe eine sehr gute Leistung von scanning through die ganze Tabelle von GPU, sogar meine 3 Jahre alten Laptop GT 650M konnte 700 Millionen Hashes/Sekunde überprüfen!

Edit 1: Sie können denken, 64-Bit-Hash als eine einzige Ecke auf einem 64-dimensionalen Würfel, Mathematik ist einfacher, wenn Ihre normalisieren Ecke -1 und 1 (auf diese Weise ihr Zentrum im Ursprung ist) koordiniert. Sie können m Bilder als Matrix M der Größe m x 64 (eine Zeile/Bild, ein Bit Hash/Spalte) ausdrücken.

einfachste Weg, dies zu 2^n verschiedenen Gruppen aufgeteilt ist n 64-dimensionale Vektoren v_0, v_1, ..., v_n (pick jedes Vektorelement aus Normalverteilung N (0,1)) zu erzeugen, kann diese als eine Matrix ausgedrückt wird V der Größe 64 x n (eine Spalte/Vektor). Es könnte Orthogonalitätserzwingung geben, wie bei Random projection erwähnt, aber ich werde es hier überspringen.

Jetzt durch Berechnung A = (M * V) > 0 erhalten Sie m x n Matrix (ein Bild/Zeile, eine Projektion/Spalte). Als nächstes wandeln Sie die Binärdarstellung jeder Zeile in eine Zahl um. Sie erhalten 2^n verschiedene Möglichkeiten und ähnliche Hashes werden höchstwahrscheinlich am selben Bucket enden.

Dieser Algorithmus funktioniert für jede orthogonale Darstellung von Daten (z. B. SURF Features), nicht nur binäre Zeichenfolgen. Ich bin mir sicher, dass es einfachere (und effizientere) Algorithmen für binäre Hashes gibt, aber dies ist eine Möglichkeit, Zufallsprojektionen zu implementieren.

Ich schlug vor, XORring, denn wenn Bilder nicht identische Hashes haben, dann sind sie nicht garantiert in der gleichen Eimer landen.Indem Sie alle möglichen kleinen Abweichungen vom ursprünglichen Hash überprüfen, können Sie sehen, welche anderen Bins für mögliche Übereinstimmungen möglich sind.

In gewisser Weise ist dies ähnlich wie eine Computerspiel-Engine der 2D-Karte in ein Raster von Zellen der Größe x, teilen könnte dann x brauchen Sie nur von einem Punkt alle Einheiten innerhalb eines Radius zu finden 9-Zellen zu überprüfen (die eine enthält den Punkt + 8 umgebende Zellen), um eine 100% genaue Antwort zu erhalten.