Suchen Sie nach ähnlichen Bildern und analysieren Sie einen einzelnen Algorithmus

Ich musste kürzlich das Problem der Optimierung der Suche nach doppelten Bildern lösen.

Die vorhandene Lösung läuft auf einer ziemlich bekannten Python-Bibliothek, Image Match , basierend auf einer Bildsignatur für jede Art von Bild , verfasst von H. Chi Wong, Marshall Bern und David Goldberg.

Aus mehreren Gründen wurde beschlossen, alles in Kotlin umzuschreiben und gleichzeitig den Speicher und die Suche in ElasticSearch aufzugeben, was erheblich mehr eiserne und menschliche Ressourcen für die Unterstützung und Verwaltung erfordert, um im lokalen In-Memory-Cache zu suchen.

Um zu verstehen, wie es funktioniert, musste ich mich in den Python-Referenzcode eintauchen, da die ursprüngliche Arbeit manchmal nicht ganz offensichtlich ist und ich mich an einigen Stellen daran erinnere, wie man eine Eule zeichnet. Eigentlich möchte ich die Ergebnisse dieser Studie teilen und gleichzeitig einige Optimierungen in Bezug auf Datenvolumen und Suchgeschwindigkeit erläutern. Vielleicht wird jemand nützlich sein.

Haftungsausschluss: Es besteht die Möglichkeit, dass ich irgendwo etwas durcheinander gebracht habe, es falsch gemacht habe oder nicht optimal. Nun, ich freue mich über Kritik und Kommentare. :) :)

Wie funktioniert es:

1. Das Bild wird in das 8-Bit-Schwarzweißformat konvertiert (ein Punkt ist ein Byte im Wert 0-255).
2. Das Bild wird so beschnitten, dass 5% der akkumulierten Differenz (weiter unten) von jeder der vier Seiten verworfen werden. Zum Beispiel ein schwarzer Rahmen um das Bild.
3. Es wird ein Arbeitsraster ausgewählt (standardmäßig 9 x 9), dessen Knoten als Referenzpunkte für die Bildsignatur dienen.
4. Für jeden Referenzpunkt wird anhand eines bestimmten Bereichs um ihn herum seine Helligkeit berechnet.
5. Für jeden Referenzpunkt wird berechnet, um wie viel er heller / dunkler als seine acht Nachbarn ist. Es werden fünf Abstufungen verwendet, von -2 (viel dunkler) bis 2 (viel heller).
6. All diese „Freude“ entfaltet sich in einem eindimensionalen Array (Vektor) und wird durch die Bildsignatur aufgerufen.

Die Ähnlichkeit der beiden Bilder wird wie folgt überprüft:



Je niedriger das d, desto besser. Tatsächlich ist d <0,3 fast eine Identitätsgarantie.

Jetzt genauer.

Erster Schritt

Ich denke, dass es wenig Sinn macht, über die Konvertierung in Graustufen zu sprechen.

Zweiter Schritt

Nehmen wir an, wir haben ein Bild wie dieses:


Es ist zu sehen, dass es rechts und links einen schwarzen Rahmen von 3 Pixeln und oben und unten 2 Pixel gibt, den wir im Vergleich überhaupt nicht brauchen

Die Grenzgrenze wird durch den folgenden Algorithmus bestimmt:

1. Für jede Spalte berechnen wir die Summe der absoluten Differenzen benachbarter Elemente.
   
2. Wir beschneiden links und rechts die Anzahl der Pixel, deren Beitrag zur kumulierten Gesamtdifferenz weniger als 5% beträgt.

Wir machen das gleiche für Spalten.

Eine wichtige Klarstellung: Wenn die Abmessungen des resultierenden Bildes für Schritt 4 nicht ausreichen, beschneiden wir nicht!

Schritt drei

Nun, hier ist alles ganz einfach, wir teilen das Bild in gleiche Teile und wählen die Knotenpunkte aus.

Vierter Schritt

Die Helligkeit des Ankerpunkts wird als durchschnittliche Helligkeit aller Punkte im quadratischen Bereich um ihn herum berechnet. In der Originalarbeit wird die folgende Formel verwendet, um die Seiten dieses Quadrats zu berechnen:

Fünfter Schritt

Für jeden Referenzpunkt wird der Unterschied in seiner Helligkeit mit der Helligkeit seiner acht Nachbarn berechnet. Für die Punkte, für die es keine Nachbarn gibt (obere und untere Reihe, linke und rechte Spalte), wird die Differenz als 0 angenommen.

Ferner werden diese Unterschiede auf fünf Abstufungen reduziert:


Es stellt sich so etwas wie diese Matrix heraus:

Sechster Schritt

Ich denke, es ist keine Erklärung erforderlich.

Und jetzt zur Optimierung

In der Originalarbeit wird zu Recht darauf hingewiesen, dass aus der resultierenden Signatur Nullwerte entlang der Kanten der Matrix vollständig gelöscht werden können, da sie für alle Bilder identisch sind.


Wenn Sie jedoch genau hinschauen, können Sie feststellen, dass für zwei Nachbarn die gegenseitigen Abstufungen im absoluten Wert gleich sind. Daher können Sie für jeden Referenzpunkt sicher vier doppelte Werte ausgeben, wodurch die Größe der Signatur um die Hälfte reduziert wird (ohne seitliche Nullen).


Offensichtlich gibt es bei der Berechnung der Quadratsumme für jedes x definitiv ein gleiches Modulo x ', und die Formel zur Berechnung der Norm kann ungefähr so ​​geschrieben werden (ohne sich mit der Neuindizierung zu befassen):


Dies gilt sowohl für den Zähler als auch für beide Terme des Nenners.

Weiter in der ursprünglichen Arbeit wird angemerkt, dass drei Bits ausreichen, um jede Abstufung zu speichern. Das heißt, im Unsigned Long passen 21 Abstufungen. Dies ist eine ziemlich große Größenersparnis, erhöht jedoch die Komplexität bei der Berechnung der Summe der Quadrate der Differenz zwischen den beiden Signaturen. Ich muss sagen, dass mich diese Idee sehr gefesselt hat und sie einige Tage lang nicht losgelassen hat, bis eines Abends klar wurde, wie man einen Fisch isst , ein Ort, an dem man die Berechnung speichern und vereinfachen kann. Pass auf deine Hände auf.

Wir verwenden ein solches Schema für die Speicherung, 4 Bits pro Abstufung:

Ja, nur 16 Abstufungen passen in eine vorzeichenlose Länge gegen 21, aber dann wird das Array der Differenz der beiden Signaturen mit einem x oder 15 Verschiebungen nach rechts berechnet, wobei die Anzahl der für jede Iteration der Verschiebung festgelegten Bits berechnet wird. Das heißt,


Das Vorzeichen spielt für uns keine Rolle, da alle Werte quadriert werden.

Wenn der Schwellenwert der Entfernung im Voraus bestimmt wird, dessen Werte für uns nicht mehr interessant sind, können Sie nach einigem Herumtanzen der Berechnungsformel eine ziemlich leichte Filterbedingung für eine einfache Anzahl von gesetzten Bits ableiten.

Weitere Details zur Optimierung dieses Algorithmus mit Codebeispielen finden Sie im vorherigen Artikel . Ich empfehle separat, Kommentare dazu zu lesen - der in Chabrowsk ansässige Masyaman schlug einige ziemlich interessante Methoden zur Berechnung vor, einschließlich Packungsabstufungen in drei Bits mit Bitmagie .

Eigentlich ist das alles. Vielen Dank für Ihre Aufmerksamkeit. :) :)