Harris Eckendetektor: Enthüllung der Magie der Bildmerkmalserkennung

Von Fouad Sabry

Was ist Harris Eckendetektor?

Der Harris-Eckendetektor ist ein Eckenerkennungsoperator, der häufig in Computer-Vision-Algorithmen verwendet wird, um Ecken zu extrahieren und auf Merkmale eines Bildes zu schließen. Es wurde erstmals 1988 von Chris Harris und Mike Stephens nach der Verbesserung des Eckendetektors von Moravec eingeführt. Im Vergleich zu seinem Vorgänger berücksichtigt der Eckendetektor von Harris die Differenz der Eckenbewertung in Bezug auf die Richtung direkt, anstatt für alle 45-Grad-Winkel verschobene Patches zu verwenden, und hat sich als genauer bei der Unterscheidung zwischen Kanten und Ecken erwiesen. Seitdem wurde es verbessert und in viele Algorithmen übernommen, um Bilder für nachfolgende Anwendungen vorzuverarbeiten.

Wie Sie davon profitieren

(I) Erkenntnisse und Validierungen zu den folgenden Themen:

Kapitel 1: Harris-Eckendetektor

Kapitel 2: Eckenerkennung

Kapitel 3: Strukturtensor

Kapitel 4: Harris-Detektor für affine Regionen

Kapitel 5: Lucas-Kanade-Methode

Kapitel 6: Hessische Matrix

Kapitel 7: Lernen geometrischer Merkmale

Kapitel 8: Tensordichte

Kapitel 9: Mehrotra-Prädiktor-Korrektor-Methode

Kapitel 10: Diskreter Laplace-Operator

(II) Beantwortung der häufigsten öffentlichen Fragen zum Harris Corner Detector.

(III) Beispiele aus der Praxis für den Einsatz des Harris-Eckendetektors in vielen Bereichen.

Für wen dieses Buch ist

Fachleute, Studenten und Doktoranden, Enthusiasten, Bastler und diejenigen, die über das Grundwissen oder die Informationen zu Harris-Eckdetektoren jeglicher Art hinausgehen möchten.

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

Buchvorschau

Kapitel 1: Harris Eckendetektor

Der Harris-Eckendetektor wird häufig in Computer-Vision-Algorithmen für die Eckenextraktion und Merkmalsinferenz eingesetzt und ist eine Art Eckenerkennungsoperator. Chris Harris und Mike Stephens brachten ihn erstmals 1988 auf den Markt, nachdem sie Moravecs Eckendetektor verfeinert hatten. Seitdem wurde es verfeinert und in eine Vielzahl von Algorithmen implementiert, die zur Vorbereitung von Bildern für die Verwendung in anderen Kontexten verwendet werden.

Eine Ecke ist eine Position, an der sich zwei tangentiale Hauptkanten treffen. Eine Möglichkeit, sich eine Ecke vorzustellen, ist der Treffpunkt zweier Kanten, wobei eine Kante eine deutliche Verschiebung des Tonwerts innerhalb eines Bildes darstellt. Wichtige Bildmerkmale oder Interessenpunkte sind Ecken, da sie unverändert bleiben, wenn das Bild verschoben, gedreht oder beleuchtet wird. Die Ecken eines Bildes machen vielleicht nur einen kleinen Bruchteil des Ganzen aus, aber sie enthalten einige der wichtigsten Funktionen für die Wiederherstellung von Bildinformationen und können verwendet werden, um die Datenmenge zu reduzieren, die für Aufgaben wie Bewegungsverfolgung, Bildzusammenfügung, Erstellung von 2D-Mosaiken, Stereovision, Bilddarstellung,  Und so weiter.

Viele verschiedene Eckdetektoren wurden von Forschern entwickelt, um die Ecken des Bildes zu extrahieren, aber der Kanade-Lucas-Tomasi (KLT)-Operator und der Harris-Operator zeichnen sich als die einfachsten, effizientesten und vertrauenswürdigsten aus. Diese beiden gängigen Ansätze sind mit der lokalen Strukturmatrix verwandt und von ihr abhängig. Der Harris-Eckendetektor wird bevorzugt für den Einsatz beim Stereoabgleich und beim Abrufen von Bilddatenbanken verwendet, da er trotz Licht- und Rotationsänderungen eine hohe Genauigkeit beibehält. Der Harris-Eckendetektor ist trotz seiner Mängel und Einschränkungen immer noch eine entscheidende und grundlegende Methode in vielen Computer-Vision-Anwendungen.

Ohne den Umfang einzuschränken, wird hier von 2-dimensionalen Graustufenbildern ausgegangen.

Dieses Bild sei gegeben durch I .

Erwägen Sie, ein Bildfeld {\displaystyle (x,y)\in W} (Fenster) zu nehmen und es um zu verschieben {\displaystyle (\Delta x,\Delta y)} .

Die SSD vergleicht den Abstand zwischen diesen beiden Patches, bezeichnet f als , ist das Ergebnis von:

{\displaystyle f(\Delta x,\Delta y)={\underset {(x_{k},y_{k})\in W}{\sum }}\left(I(x_{k},y_{k})-I(x_{k}+\Delta x,y_{k}+\Delta y)\right)^{2}}

{\displaystyle I(x+\Delta x,y+\Delta y)} kann durch eine Taylor-Erweiterung angenähert werden.

Seien I_{x} und I_y die partiellen Ableitungen von I , so dass

{\displaystyle I(x+\Delta x,y+\Delta y)\approx I(x,y)+I_{x}(x,y)\Delta x+I_{y}(x,y)\Delta y}

Daraus ergibt sich die Annäherung.

{\displaystyle f(\Delta x,\Delta y)\approx {\underset {(x,y)\in W}{\sum }}\left(I_{x}(x,y)\Delta x+I_{y}(x,y)\Delta y\right)^{2},}

deren Antworten durch Matrizen dargestellt werden können:

{\displaystyle f(\Delta x,\Delta y)\approx {\begin{pmatrix}\Delta x&\Delta y\end{pmatrix}}M{\begin{pmatrix}\Delta x\\\Delta y\end{pmatrix}},}

wobei M einen Tensor der Struktur bezeichnet,

{\displaystyle M={\underset {(x,y)\in W}{\sum }}{\begin{bmatrix}I_{x}^{2}&I_{x}I_{y}\\I_{x}I_{y}&I_{y}^{2}\end{bmatrix}}={\begin{bmatrix}{\underset {(x,y)\in W}{\sum }}I_{x}^{2}&{\underset {(x,y)\in W}{\sum }}I_{x}I_{y}\\{\underset {(x,y)\in W}{\sum }}I_{x}I_{y}&{\underset {(x,y)\in W}{\sum }}I_{y}^{2}\end{bmatrix}}}

Die Algorithmen zur Erkennung von Harris-Ecken werden oft in fünf Stufen unterteilt.

Farbe zu Graustufen

Räumliche Ableitungsberechnung

Aufbau von Struktur-Tensoren

Berechnung der Harris-Antwort

Reduzierte Unterdrückung

Um die Verarbeitungsgeschwindigkeit bei der Verwendung des Harris-Eckendetektors für ein Farbbild zu verbessern, wird es zunächst in Graustufen konvertiert.

Graustufen-Bildpixelwerte sind nur die gewichteten Summen der entsprechenden RGB-Werte, {\displaystyle \sum _{C\,\in \,\{R,G,B\}}w_{C}\cdot C} z. B. wo,

{\displaystyle w_{R}=0.299,\ w_{G}=0.587,\ w_{B}=1-(w_{R}+w_{G})=0.114.}

Als nächstes sind die Zinsderivate die in Bezug auf x und y, und wir werden sie bestimmen, {\displaystyle I_{x}(x,y)} und {\displaystyle I_{y}(x,y)} .

Mit {\displaystyle I_{x}(x,y)} , {\displaystyle I_{y}(x,y)} können wir den Strukturtensor konstruieren M .

Für {\displaystyle x\ll y} hat man {\displaystyle {\tfrac {x\cdot y}{x+y}}=x{\tfrac {1}{1+x/y}}\approx x.} In diesem Schritt erhalten wir mit dieser Näherung den kleinsten Eigenwert des Strukturtensors:

{\displaystyle \lambda _{\min }\approx {\frac {\lambda _{1}\lambda _{2}}{(\lambda _{1}+\lambda _{2})}}={\frac {\det(M)}{\operatorname {tr} (M)}}}

mit dem Trace {\displaystyle \mathrm {tr} (M)=m_{11}+m_{22}} .

Im Folgenden finden Sie eine alternative Harris-Antwortberechnung, die häufig verwendet wird:

{\displaystyle R=\lambda _{1}\lambda _{2}-k(\lambda _{1}+\lambda _{2})^{2}=\det(M)-k\operatorname {tr} (M)^{2}}

wobei k eine empirisch bestimmte Konstante ist; {\displaystyle k\in [0.04,0.06]} .

Wenn wir die lokalen Maxima als Ecken innerhalb des Fensters finden, das ein 3 x 3-Filter ist, können wir die besten Werte auswählen, um Ecken zu kennzeichnen.

Detektor für Harris-Laplace-geformte Ecken

Eckendetektor mit differentieller morphologischer Zerlegung

Ein Eckendetektor, der auf mehrskaligen bilateralen Strukturtensoren basiert

Registrierung, Stitching und Ausrichtung von Bildern

Erstellung von 2D-Mosaiken

Rekonstruktion und Modellierung von 3D-Szenen

Bewegungserkennung

Objekterkennung

Inhaltsbasiertes Abrufen und Indizieren von Bildern

Video-Tracking

{Ende Kapitel 1}

Kapitel 2: Eckenerkennung

In Computer-Vision-Systemen wird die Eckenerkennung verwendet, um die Art eines Bildes abzuleiten, indem bestimmte Arten von Merkmalen extrahiert werden. Bewegungsanalyse, Bildregistrierung, Videoverfolgung, Mosaik, Panorama-Stitching, 3D-Rekonstruktion und Objekterkennung nutzen die Eckenerkennung auf die eine oder andere Weise. Es gibt eine gewisse Doppelarbeit zwischen der Eckenerkennung und der Interessenpunkterkennung.

Eine Ecke ist der Punkt, an dem sich zwei Kanten treffen. Eine alternative Definition einer Ecke ist ein Punkt mit zwei unterschiedlichen Kantenrichtungen, die unmittelbar daran angrenzen.

Ein Interessenpunkt ist eine bestimmte Stelle innerhalb eines Bildes, die genau identifiziert werden kann. Ein Interessenpunkt ist nicht auf eine Ecke beschränkt, sondern kann auch so etwas wie ein lokales Maximum oder Minimum in der Intensität, der Abschluss einer Linie oder ein Punkt in einer Kurve sein, an dem die Krümmung am höchsten ist.

In der Praxis erkennen die meisten Eckenerkennungs-Ansätze nur interessante Stellen, und die Begriffe werden in der Literatur mehr oder weniger synonym verwendet.

Verschiedene Autoren verwenden die Begriffe Ecke, Interessenpunkt und Merkmal synonym, was die Diskussion weiter trübt. Insbesondere gibt es eine Reihe von Blob-Detektoren, die als Interessenpunktoperatoren bezeichnet werden können, aber allgemein als Eckdetektoren bekannt sind. Auch die Existenz einer Ridge-Erkennung zur Identifizierung linearer Objekte ist bekannt.

Aufgrund ihrer inhärenten Fragilität erfordern Eckendetektoren in der Regel den Einsatz erheblicher Redundanz, um die Auswirkungen einzelner Fehler auf den Erkennungsprozess zu mindern.

Die Qualität eines Eckendetektors kann gemessen werden, indem seine Fähigkeit getestet wird, dieselbe Ecke in Bildern zu identifizieren, die ansonsten vergleichbar sind, aber Transformationen wie Skalierung, Drehung und Beleuchtungsänderungen unterzogen wurden.

Korrelation ist eine einfache Methode zur Erkennung von Ecken in Bildern, aber sie wird schnell rechenintensiv und ineffizient. Die von Harris und Stephens (unten) vorgeschlagene Methode, die eine Verbesserung einer von Moravec vorgeschlagenen Methode darstellt, bildet die Grundlage eines populären alternativen Ansatzes.

Dieser Ansatz, der auf die Anfänge der Eckenerkennung zurückgeht, verwendet eine Selbstähnlichkeitsschwelle, um Ecken zu identifizieren. Die Technik untersucht die Nähe eines auf dem Pixel zentrierten Patches zu anderen Patches, die es stark überlappen, um festzustellen, ob eine Ecke vorhanden ist. Die Ähnlichkeit wird berechnet, indem die quadratischen Abweichungen (SSD) der zugehörigen Pixel in jedem Patch summiert werden. Wenn die Zahl kleiner ist, gibt es eine größere Übereinstimmung.

Wenn sich das Pixel in einem Bereich mit gleichmäßiger Helligkeit befindet, haben benachbarte Felder ein ähnliches Aussehen. Wenn sich das Pixel in der Nähe einer Kante befindet, variiert das Erscheinungsbild von benachbarten Feldern, die senkrecht zur Kante stehen, erheblich, während nahe gelegene Felder, die parallel zur Kante verlaufen, das Erscheinungsbild nur geringfügig ändern. Wenn sich das Pixel auf einem multidirektional variablen Feature befindet, hat keines der benachbarten Felder ein gemeinsames Erscheinungsbild.

Als minimale Summe der quadratischen Differenzen (SSD) zwischen einem Patch und seinen Nachbarn die Eckenstärke (horizontal, vertikal und auf den beiden Diagonalen). Alle umgebenden Felder werden unterschiedlich angezeigt, wenn dieser Wert hoch ist, da die Streuung entlang aller Schichten gleich oder größer als dieser Wert ist.

Um zu bestimmen, ob ein interessantes Feature an einer bestimmten Stelle vorhanden ist, muss die Eckenstärkezahl für alle möglichen Positionen berechnet werden.

Laut Moravec besteht einer der Hauptnachteile dieses Operators darin, dass er nicht isotrop ist, was bedeutet, dass er fälschlicherweise eine Kante als Zinspunkt auswählt, wenn sie nicht senkrecht zu den Richtungen ihrer Nachbarn (horizontal, vertikal oder diagonal) steht.