Geometrisches Hashing: Effiziente Algorithmen zur Bilderkennung und -anpassung

Von Fouad Sabry

Was ist geometrisches Hashing?

In der Informatik ist geometrisches Hashing eine Methode zum effizienten Auffinden zweidimensionaler Objekte, die durch diskrete Punkte dargestellt werden, die einer affinen Transformation unterzogen wurden, obwohl es Erweiterungen für andere Objektdarstellungen und Transformationen gibt. In einem Offline-Schritt werden die Objekte kodiert, indem jedes Punktpaar als geometrische Basis behandelt wird. Die übrigen Punkte können mit zwei Parametern bezüglich dieser Basis invariant dargestellt werden. Für jeden Punkt werden seine quantisierten transformierten Koordinaten als Schlüssel und die Indizes der Basispunkte als Wert in der Hash-Tabelle gespeichert. Anschließend wird ein neues Basispunktpaar ausgewählt und der Vorgang wiederholt. Im Online-(Erkennungs-)Schritt werden zufällig ausgewählte Datenpunktpaare als Kandidatenbasen betrachtet. Für jede Kandidatenbasis werden die verbleibenden Datenpunkte entsprechend der Basis codiert und mögliche Entsprechungen des Objekts werden in der zuvor erstellten Tabelle gefunden. Die Kandidatenbasis wird akzeptiert, wenn eine ausreichend große Anzahl der Datenpunkte eine konsistente Objektbasis indiziert.

Wie Sie davon profitieren

(I) Erkenntnisse und Validierungen zu den folgenden Themen:

Kapitel 1: Geometrisches Hashing

Kapitel 2: Analytische Geometrie

Kapitel 3: Kartesisches Koordinatensystem

Kapitel 4: 2D-Computergrafik

Kapitel 5: Koordinatensystem

Kapitel 6: Übersetzung (Geometrie)

Kapitel 7: Hough-Transformation

Kapitel 8: Skalierungsinvariante Feature-Transformation

Kapitel 9: Homographie

Kapitel 10: Lernen geometrischer Merkmale

(II) Beantwortung der häufigsten öffentlichen Fragen zum geometrischen Hashing.

(III) Beispiele aus der Praxis für die Verwendung von geometrischem Hashing in vielen Bereichen.

Für wen dieses Buch ist

Fachleute, Studenten und Doktoranden, Enthusiasten, Hobbyisten und diejenigen, die für jede Art von geometrischem Hashing über das Grundwissen oder die Informationen hinausgehen möchten.

• Sprache: Deutsch
• Herausgeber: Eine Milliarde Sachkundig [German]
• Erscheinungsdatum: 11. Mai 2024

Buchvorschau

Kapitel 1: Geometrisches Hashing

Es gibt Erweiterungen für verschiedene Objektdarstellungen und -transformationen, aber in der Informatik wird geometrisches Hashing verwendet, um Objekte in zwei Dimensionen effizient zu lokalisieren, die durch diskrete Punkte dargestellt werden, die eine affine Transformation durchlaufen haben. Offline wird jedes Punktpaar als geometrische Grundlage für die Codierung der Objekte verwendet. Zwei Parameter ermöglichen eine basisinvariante Darstellung der verbleibenden Punkte. Die Hash-Tabelle verwaltet ein Wertepaar: die Indizes der Basispunkte für jeden Schlüssel und die quantisierten konvertierten Koordinaten für jeden Wert. Das Verfahren wird dann wiederholt, diesmal mit einem anderen Satz von Basispunkten. In der Online-(Erkennungs-)Phase werden beliebige Paarungen von Datenpunkten als mögliche Grundlagen bewertet. Um realisierbare Entsprechungen zwischen dem Objekt und jeder Kandidatenbasis zu finden, werden die verbleibenden Datenpunkte entsprechend der Basis kodiert. Wenn ein ausreichend großer Anteil der Datenpunkte auf eine konstante Objektbasis verweist, wird die Kandidatenbasis akzeptiert.

In der Computer Vision wurde erstmals geometrisches Hashing für die 2D- und 3D-Objekterkennung vorgeschlagen, Objekterkennung mit geometrischem Hashing.

Nehmen wir an, wir möchten überprüfen, ob ein Modellbild in einem Eingabebild zu sehen ist.

Geometrisches Hashing ist eine Methode, mit der dies erreicht werden kann.

Die Technik könnte verwendet werden, um ein einzelnes Objekt unter vielen in einer Datenbank zu identifizieren. In diesem Szenario muss die Hashtabelle sowohl die Posendaten als auch den Basisindex des Objektmodells verfolgen.

Um das Beispiel übersichtlich zu halten, verwenden wir einfach ein paar Punktmerkmale und gehen davon aus, dass ihre Beschreibungen ausschließlich von ihren Koordinaten stammen (in der Praxis könnten lokale Deskriptoren wie SIFT für die Indizierung verwendet werden).

Lernen Sie die definierenden Merkmale des Modells kennen.

Angenommen, 5 Feature-Punkte sind im Modellbild mit den Koordinaten zu finden (12,17); (45,13); (40,46); (20,35); (35,25) , sehen Sie sich das Foto an.

Stellen Sie eine Grundlage für die Beschreibung der Koordinaten der Feature-Punkte bereit.

Die beiden Punkte, die die Grundlage für eine Ähnlichkeitstransformation im zweidimensionalen Raum bilden.

Der Startpunkt befindet sich auf halbem Weg entlang der Linie, die die beiden Punkte (P1, P2) verbindet, in unserer Fallstudie P4, die x' Achse ist auf einen von ihnen gerichtet, der y' orthogonal ist und durch den Ursprung verläuft.

Die Skala wird so gewählt, dass der absolute Wert von x' für beide Basispunkte 1 ist.

Erklären Sie, wo sich die Dinge in Bezug auf dieses Fundament befinden, d.h.

Berechnen Sie die Transformationen zu den neuen Achsen.

Um die Erkennung widerstandsfähiger gegen Rauschen zu machen, sollten die Koordinaten diskretisiert werden, es wird ein 0,25-Einheiten-Bin verwendet.

Wir erhalten also die Koordinaten (-0.75,-1.25); (1.00,0.00); (-0.50,1.25); (-1.00,0.00); (0.00,0.25)

Verwenden Sie eine Hashtabelle mit den Features als Index, um das Fundament zu speichern (in diesem Fall nur transformierte Koordinaten). Die Anzahl der Elemente, die mit dem Basispaar gelagert werden sollen, wenn mehr als zwei zugeordnet werden sollen.

Wechseln Sie zu einem neuen Basispaar und fahren Sie von dort aus fort (Schritt 2). Um mit Okklusionen umzugehen, ist dies unerlässlich. Alle Paare, die nicht linear sind, sollten idealerweise aufgelistet werden. Nach zwei Iterationen, in denen das Paar (P1, P3) ausgewählt wird, präsentieren wir die Hash-Tabelle.

Hashtabelle:

Die meisten Hashtabellen erlauben es nicht, doppelte Schlüssel mit separaten Werten zu verknüpfen.

Im wirklichen Leben wird man also keine Basisschlüssel (1.0, 0.0) und (-1.0, (Hash-Tabelle, Wert 0) codieren.

Lokalisieren Sie visuelle Reizpunkte im gegebenen Bild.

Wählen Sie einen zufälligen Startpunkt. Das Eingabebild enthält das Zielelement wahrscheinlich nicht, wenn es keine angemessene willkürliche Grundlage gibt, um festzustellen, ob es vorhanden ist oder nicht.

Beschreiben Sie die Positionen der Feature-Punkte des neuen Koordinatensystems. Führen Sie die traditionelle Quantisierung der resultierenden Koordinaten durch.

Überprüfen Sie die konvertierten Punkt-Features des Eingabebilds anhand der Hash-Tabelle. Für den Fall, dass die Punkt-Features gleich oder sehr ähnlich sind, sollte die Anzahl für die relevante Basis erhöht werden (und der Objekttyp, falls vorhanden).

Wenn die Anzahl einer bestimmten Basis größer als ein Schwellenwert ist, entspricht diese Basis wahrscheinlich einer in Schritt 2 ausgewählten Bildbasis. Dazu konvertieren wir zunächst das Koordinatensystem des Bildes in das des Modells (für das fiktive Objekt). Wenn es funktioniert, wird das Element gefunden. Wenn nicht, kehren Sie zum vorherigen Schritt zurück.

Es scheint, dass die einzigen Transformationen, die dieser Ansatz verarbeiten kann, die von Größe, Position und Ausrichtung sind. Möglicherweise ist das Element jedoch bereits im bereitgestellten Image in einem Spiegelbildformat vorhanden. Folglich muss das Objekt auch durch geometrisches Hashing auffindbar sein. Gespiegelte Objekte können auf zwei verschiedene Arten identifiziert werden.

Machen Sie die linke Seite des Vektordiagramms positiv und die rechte Seite negativ. Um das gleiche Ergebnis beim Multiplizieren mit x zu erhalten, addieren Sie einfach -1.

Verwenden Sie eine Dreiergruppe als Ausgangspunkt. Dies ermöglicht die Identifizierung von Reflexionen (oder Objekten). Eine andere Methode des geometrischen Hashings verwendet einen Satz von drei Punkten als Grundlage.

Hashing funktioniert ähnlich für höherdimensionale Daten, wie oben gezeigt. Für die Basis dreidimensionaler Daten sind drei Punkte erforderlich. Die x-Achse wird durch die ersten beiden Punkte und die y-Achse durch den dritten Punkt (mit dem ersten Punkt) definiert. Mit der Rechte-Hand-Regel kann eine Achse konstruiert werden, und die z-Achse steht senkrecht dazu. Die resultierende Basis ist abhängig von der Reihenfolge, in der die Punkte eingegeben werden.

{Ende Kapitel 1}

Kapitel 2: Analytische Geometrie

Die analytische Geometrie, oft auch Koordinatengeometrie oder kartesische Geometrie genannt, ist ein Zweig der Mathematik, der sich mit dem Studium der Geometrie aus kartesischer Sicht befasst. Synthetische Geometrie ist das Gegenteil davon.

Physik, Ingenieurwesen, Luftfahrt, Raketentechnik, Weltraumwissenschaft und Raumfahrt nutzen alle analytische Geometrie. Sie ist die Grundlage für mehrere Zweige der zeitgenössischen Geometrie, wie z. B. algebraische, differentielle, diskrete und computergestützte Geometrie.

Bei der Arbeit mit Gleichungen mit Ebenen, Geraden und Kreisen wird in der Regel das kartesische Koordinatensystem verwendet. In der Geometrie werden die zweidimensionale euklidische Ebene und der dreidimensionale euklidische Raum untersucht. Die analytische Geometrie, wie sie typischerweise in Lehrbüchern definiert und gelehrt wird, befasst sich mit der Erzeugung und Darstellung geometrischer Formen im numerischen Sinne und der Extraktion numerischer Informationen aus diesen Darstellungen. Das Cantor-Dedekind-Axiom garantiert, dass Berechnungen in der Geometrie des linearen Kontinuums nur mit der Algebra der reellen Zahlen durchgeführt werden können.

Es wurde argumentiert, dass der griechische Mathematiker Menaechmus die analytische Geometrie entwickelte, weil er eine Technik verwendete, die der Verwendung von Koordinaten beim Lösen von Problemen und beim Beweisen von Theoremen ähnelte.

Der persische Mathematiker Omar Khayyam aus dem 11. Jahrhundert erkannte eine starke Beziehung zwischen Geometrie und Algebra und bewegte sich in die richtige Richtung, als er dazu beitrug, die Lücke zwischen numerischer und geometrischer Algebra zu schließen: 248

Die analytische Geometrie wurde unabhängig voneinander von René Descartes und Pierre de Fermat erfunden, die kartesische Geometrie, ein Synonym für analytische Geometrie, trägt den Namen Descartes.

Descartes machte bedeutende Fortschritte mit den Methoden in einem Essay mit dem Titel La Géométrie (Geometrie), einem Anhang zu seinem 1637 veröffentlichten Diskurs über die Methode, seine Vernunft richtig zu lenken und nach der Wahrheit in den Wissenschaften zu suchen.

La Geometrie, die vollständig in seiner Muttersprache, Französisch, ihren theoretischen Grundlagen usw. verfasst war, legte den Grundstein für die Entwicklung der Infinitesimalrechnung in Europa.

Die Arbeit stieß zunächst auf Skepsis, was zum Teil auf die zahlreichen Lücken in der Argumentation und die verworrene Mathematik zurückzuführen war.

Descartes' Meisterwerk wurde erst als das anerkannt, was es war, nachdem van Schooten es 1649 ins Lateinische übersetzt und kommentiert hatte (und nachdem er weiter daran gearbeitet hatte).

Als Ergebnis dieses Ansatzes wurde Descartes damit beauftragt, kompliziertere Gleichungen zu lösen, was die Verfeinerung der Techniken zur Behandlung von Polynomgleichungen größeren Ausmaßes erforderlich machte.

Leonhard Euler war der erste, der Kurven und Flächen im Raum systematisch mit der Koordinatenmethode untersuchte.

In der analytischen Geometrie wird ein Koordinatensystem für die Ebene eingeführt, und jedem Punkt werden zwei reelle Zahlen zugewiesen. Jedem Punkt im euklidischen Raum sind ebenfalls drei Koordinaten zugeordnet. Die Bedeutung der Koordinaten wird durch den gewählten Bezugspunkt bestimmt. Es gibt viele verschiedene Koordinatensysteme, aber die folgenden sind die häufigsten:

Kartesische Koordinaten, bei denen jeder Punkt eine x-Koordinate hat, die seine horizontale Position darstellt, und eine y-Koordinate, die seine vertikale Position darstellt, sind das am weitesten verbreitete Koordinatensystem. Diese werden in der Regel als gepaarter Ausdruck (x, y) dargestellt. Jeder Punkt im dreidimensionalen euklidischen Raum kann mit dieser Methode durch