Interest-Operator

Mit Interest-Operatoren werden im Bereich der Bildverarbeitung Algorithmen bezeichnet, die markante Stellen in Bildern extrahieren und gleichzeitig eine oder mehrere Kenngrößen liefern. Markante Stellen sind dabei diejenigen Punkte, die in einer begrenzten Umgebung möglichst einzigartig sind. Das Innere linienhafter Kanten gehört also nicht zu den markanten Punkten, siehe Kantendetektion. Weitere Anforderungen an Interest-Operatoren sind die Invarianz gegenüber Bildänderungen wie geometrischen und radiometrischen Verzerrungen (z. B. Rotationen, Skalierungen), die Unempfindlichkeit gegenüber Rauschen und Interpretierbarkeit (geeignet zur weiteren Bildanalyse).

Das Ergebnis der Suche nach markanten Punkten wird zum Beispiel bei der Berechnung der Epipolargeometrie zwischen zwei Kameras oder beim bildbasierten Tracking verwendet.

Bekannte Interest-Operatoren sind der Moravec-Operator, der Plessy Punkt-Detektor (meist Harris Corner Detector), der FAST-Operator (features from accelerated segment test)^[1] und der Förstner-Operator.

Der Moravec-Operator wurde von Hans Moravec im Jahr 1977 vorgestellt.^[2] Er berechnet die mittleren quadratischen Gradientensummen in den vier Hauptrichtungen des Fensters der Größe k × l {\displaystyle k\times l} .

V 1 = 1 p ( q − 1 ) ∑ i = − k k ∑ j = − l l − 1 ( g ( i , j ) − g ( i , j + 1 ) ) 2 {\displaystyle V_{1}={\frac {1}{p(q-1)}}\sum _{i=-k}^{k}\sum _{j=-l}^{l-1}{\bigl (}g(i,j)-g(i,j+1){\bigr )}^{2}}

V 2 = 1 ( p − 1 ) q ∑ i = − k k − 1 ∑ j = − l l ( g ( i , j ) − g ( i + 1 , j ) ) 2 {\displaystyle V_{2}={\frac {1}{(p-1)q}}\sum _{i=-k}^{k-1}\sum _{j=-l}^{l}{\bigl (}g(i,j)-g(i+1,j){\bigr )}^{2}}

V 3 = 1 ( p − 1 ) ( q − 1 ) ∑ i = − k k − 1 ∑ j = − l l − 1 ( g ( i , j ) − g ( i + 1 , j + 1 ) ) 2 {\displaystyle V_{3}={\frac {1}{(p-1)(q-1)}}\sum _{i=-k}^{k-1}\sum _{j=-l}^{l-1}{\bigl (}g(i,j)-g(i+1,j+1){\bigr )}^{2}}

V 4 = 1 ( p − 1 ) ( q − 1 ) ∑ i = − k k − 1 ∑ j = − l l − 1 ( g ( i , j + 1 ) − g ( i + 1 , j ) ) 2 {\displaystyle V_{4}={\frac {1}{(p-1)(q-1)}}\sum _{i=-k}^{k-1}\sum _{j=-l}^{l-1}{\bigl (}g(i,j+1)-g(i+1,j){\bigr )}^{2}}

V = min ( V 1 , V 2 , V 3 , V 4 ) {\displaystyle V=\min(V_{1},V_{2},V_{3},V_{4})}

mit p = 2 k + 1 {\displaystyle p=2k+1} und q = 2 l + 1 {\displaystyle q=2l+1} .

Liegt der Wert über einer bestimmten Schwelle, liegt ein markanter Punkt vor. Der Moravec-Operator ist sehr leicht zu implementieren und benötigt wenig Rechenzeit. Er ist aber nicht rotationsinvariant und seine Genauigkeit beträgt lediglich 1 Pixel.

Der Harris Corner Detector (selten auch Plessy Punkt-Detektor genannt) wurde 1988 von Harris und Stephens vorgestellt.^[3] Sie beschrieben eine Verbesserung des Moravec-Operators, indem sie die diskreten Verschiebungen und Richtungen mit Hilfe der Autokorrelationsfunktion lösten und damit auch die Genauigkeit der Lokalisierung steigerten.

Die Autokorrelationsmatrix A {\displaystyle A} berechnet sich dabei durch Summierung der Ableitung der Bildfunktion f {\displaystyle f} in dem Gebiet Ω {\displaystyle \Omega } um einen Punkt:^[4]

A = [ ∑ ( i , j ) ∈ Ω f x ( i , j ) 2 ∑ ( i , j ) ∈ Ω f x ( i , j ) ⋅ f y ( i , j ) ∑ ( i , j ) ∈ Ω f x ( i , j ) ⋅ f y ( i , j ) ∑ ( i , j ) ∈ Ω f y ( i , j ) 2 ] . {\displaystyle A={\begin{bmatrix}\sum \limits _{(i,j)\in \Omega }f_{x}(i,j)^{2}&\sum \limits _{(i,j)\in \Omega }f_{x}(i,j)\cdot f_{y}(i,j)\\\sum \limits _{(i,j)\in \Omega }f_{x}(i,j)\cdot f_{y}(i,j)&\sum \limits _{(i,j)\in \Omega }f_{y}(i,j)^{2}\\\end{bmatrix}}.}

f x {\displaystyle f_{x}} und f y {\displaystyle f_{y}} sind dabei die partiellen Ableitungen der Bildfunktion f {\displaystyle f} .

A {\displaystyle A} beschreibt die Nachbarschaftsstruktur um die Stelle ( x , y ) {\displaystyle (x,y)} . Ihr Rang unterscheidet sich je nach Eigenschaft der Umgebung:^[5]

Rang 2: Es liegt ein markanter Punkt vor.

Rang 1: Es liegt eine gerade Kante vor.

Rang 0: Es liegt eine homogene, unstrukturierte Fläche vor.

Die Eigenwerte λ 1 , λ 2 {\displaystyle \lambda _{1},\lambda _{2}} von A {\displaystyle A} ergeben eine Beschreibung der Nachbarschaftsstruktur, die rotationsinvariant ist. Die Eigenwerte sind dabei proportional zu den Grauwertänderungen im Bild entlang der Hauptrichtungen (entspricht der Richtung der Eigenvektoren). Aufgrund dieser Eigenschaften sind die Eigenwerte bestens geeignet um die Nachbarschaftsstruktur zu beurteilen. Eine Analyse des Parameterraumes ergibt prinzipiell drei Fälle, die man unterscheiden kann:

• a) Wenn beide Eigenwerte klein sind, dann sind auch die Grauwertänderungen entlang der Hauptrichtungen klein, d. h. die Grauwerte sind in der Umgebung konstant. Das bedeutet, dass die lokale Autokorrelationsfunktion flach ist.
• b) Wenn ein Eigenwert groß ist und der andere klein, dann ergibt sich eine lokale Autokorrelationsfunktion, die eine klare Kante erkennen lässt. Der große Eigenwert zeigt senkrecht zur Kante eine große Grauwertänderung an, wohingegen der kleine Eigenwert entlang der Kante keine bzw. nur geringfügige Änderung der Grauwerte anzeigt.
• c) Falls beide Eigenwerte groß sind, die Grauwertänderungen in beiden Richtungen also ebenfalls groß sind, sieht die lokale Autokorrelationsfunktion aus wie eine scharfe Bergspitze. Es handelt sich demnach um einen Eckpunkt.

Um eine Klassifikation durchführen zu können zur Unterscheidung der Fälle a) bis c) benötigt man also eine auf die Eigenwerte beruhende Funktion, welche die Punktstärke anzeigt. Um die Eigenwertzerlegung der Matrix A {\displaystyle A} zu umgehen, kann man folgende Beziehungen verwenden:^[3]

det ( A ) = λ 1 ⋅ λ 2 {\displaystyle \det(A)=\lambda _{1}\cdot \lambda _{2}}

spur ⁡ ( A ) = λ 1 + λ 2 {\displaystyle \operatorname {spur} (A)=\lambda _{1}+\lambda _{2}}

Damit kann nun die Punktstärke V {\displaystyle V} direkt aus A {\displaystyle A} mittels der Formel

V = det ( A ) − k spur ⁡ ( A ) 2 {\displaystyle V=\det(A)-k\operatorname {spur} (A)^{2}}

berechnet werden. Um eine Trennung der Kanten von markanten Punkten zu erhalten, wird k = 0 , 04 {\displaystyle k=0{,}04} gewählt. Auf diese Weise erhält man für Punkte positive und für Kanten negative Werte. Eine lokale Nicht-Maxima-Unterdrückung liefert schließlich die Position des Interest-Punktes.

Der Förstner-Operator betrachtet die Aufgabenstellung als Abgleich zweier gleich großen Bildausschnitte, die gegeneinander verschoben und verrauscht sind. Dies wird mittels einer kleinsten Quadrate Ausgleichung im Gauß-Markow-Modell formuliert. Die formale Lösung ergibt sich durch Aufstellen eines Normalgleichungssystems und Invertieren des Gleichungssystems. Der Trick hierbei ist nun, dass man gar nicht an der Lösung des Normalgleichungssystems interessiert ist, sondern lediglich die Präzision abschätzen möchte, mit der man die beiden Bildausschnitte zuordnen kann. Dazu berechnet man die Kovarianzmatrix C = σ ^ Δ g 2 ⋅ N − 1 {\displaystyle C={\widehat {\sigma }}_{\Delta g}^{2}\cdot N^{-1}} . Des Weiteren stellt sich bei Betrachtung der entsprechenden Normalgleichungen heraus, dass die Normalgleichungsmatrix N {\displaystyle N} identisch ist mit der Autokorrelationsmatrix A {\displaystyle A} .^[6][7]

Die Kovarianzmatrix C {\displaystyle C} gibt also an, wie genau die Position des Interestpunkts bestimmt werden kann. Dies lässt sich mittels einer Fehlerellipse visualisieren. Die Halbachsen der Fehlerellipse korrespondieren mit den Eigenvektoren und Eigenwerten λ ~ 1 , λ ~ 2 {\displaystyle {\tilde {\lambda }}_{1},{\tilde {\lambda }}_{2}} der Kovarianzmatrix. Große Gradienten in A {\displaystyle A} (entspricht einer großen Änderung der Grauwerte im Bild) führen demnach zu kleinen Varianzen bzw. Kovarianzen in C {\displaystyle C} und damit zu genauer Bestimmbarkeit. Ein guter Interestpunkt liegt dann vor, wenn die Fehlerellipse möglichst klein und möglichst rund ist. Im Gegensatz dazu besitzt die Fehlerellipse entlang einer ausgeprägten Grauwertkante eine sehr kleine und eine sehr große Halbachse ( λ ~ 1 {\displaystyle {\tilde {\lambda }}_{1}} klein, λ ~ 2 {\displaystyle {\tilde {\lambda }}_{2}} groß), der Punkt wäre also senkrecht zur Kante gut, entlang der Kante jedoch schlecht bestimmt.

Die Eigenwerte der Koeffizientenmatrix Q = N − 1 {\displaystyle Q=N^{-1}} sind außerdem identisch mit den reziproken Eigenwerten von N {\displaystyle N} .^[8] Dies lässt sich vorteilhaft nutzen, um die Inversion von N {\displaystyle N} bzw. A {\displaystyle A} zu umgehen. Die Länge der Halbachsen der Fehlerellipse verhalten sich dann jedoch umgekehrt proportional zu den Eigenwerten λ 1 , λ 2 {\displaystyle \lambda _{1},\lambda _{2}} von N {\displaystyle N} .

Zur Beurteilung des Interestpunktes hat Förstner zwei Maßzahlen definiert: das Gewicht w {\displaystyle w} und die Rundheit q {\displaystyle q} .^[7]

Das Gewicht berechnet sich wie folgt:

w = 1 spur ⁡ ( A − 1 ) = det ( A ) spur ⁡ ( A ) = λ 1 λ 2 λ 1 + λ 2 {\displaystyle w={\frac {1}{\operatorname {spur} (A^{-1})}}={\frac {\det(A)}{\operatorname {spur} (A)}}={\frac {\lambda _{1}\lambda _{2}}{\lambda _{1}+\lambda _{2}}}} .

Es ist umgekehrt proportional zur Größe der Fehlerellipse, d. h., eine kleine Fehlerellipse ergibt ein großes Gewicht. Und die Rundheit ist:^[8]

q = 1 − ( λ 1 − λ 2 λ 1 + λ 2 ) 2 = 4 det ( A ) spur ⁡ ( A ) 2 = 4 λ 1 λ 2 ( λ 1 + λ 2 ) 2 . {\displaystyle q=1-\left({\frac {\lambda _{1}-\lambda _{2}}{\lambda _{1}+\lambda _{2}}}\right)^{2}={\frac {4\det(A)}{\operatorname {spur} (A)^{2}}}={\frac {4\lambda _{1}\lambda _{2}}{(\lambda _{1}+\lambda _{2})^{2}}}.}

Der Wertebereich für q {\displaystyle q} liegt zwischen 0 und 1 ( q = 1 , 0 {\displaystyle q=1,0} ist exakt kreisrund). Durch die gegebenen Formeln lassen sich w {\displaystyle w} und q {\displaystyle q} einerseits ohne Inversion von A {\displaystyle A} oder andererseits ohne Eigenwertzerlegung von A {\displaystyle A} berechnen.

Anhand dieser beiden Kenngrößen kann die Eignung eines Interestpunkts beurteilt werden:

1. Markante Punkte besitzen kleine, kreisförmige Ellipsen (entspricht großem Gewicht und Rundheit nahe 1).
2. Gerade Kanten lassen sich durch langgestreckte Fehlerellipsen detektieren (entspricht einer kleinen Rundheit).
3. Große Ellipsen (entspricht einem kleinen Gewicht) kennzeichnen eine unstrukturierte, gleichförmige Fläche.

Für die praktische Umsetzung wird ein Faltungskern mit einer Fenstergröße von 5 × 5 oder 7 × 7 Pixeln empfohlen. Als Faustregel für einen Interestpunkt kann man die Rundheit q > 0 , 8 {\displaystyle q>0{,}8} angeben. Der Förstner-Operator ist nicht sehr empfindlich gegenüber Änderungen von q {\displaystyle q} . Für w {\displaystyle w} ist die Angabe schwieriger, da sie vom Bildkontrast abhängig ist. Eine Methode besteht darin, x {\displaystyle x} Prozent der Punkte mit den größten Werten auszuwählen, also z. B. von allen Punkten (welche die Bedingung an q {\displaystyle q} erfüllen) die 10 % mit größtem w {\displaystyle w} . Alternativ kann man sich aus dem Mittelwert aller w {\displaystyle w} über das gesamte Bild einen Schwellwert berechnen. Der Wert von w {\displaystyle w} ist zugleich die „Stärke“ des Interestpunkts.

Darüber hinaus ist es notwendig eine lokale Nicht-Maximum-Unterdrückung durchzuführen.

Ebenfalls von Förstner beschrieben wurde die subpixelgenaue Berechnung des Interestpunktes: Obwohl die Bildinformation nur im Pixelraster vorliegt, kann eine interpolierende Version des Operators für ein Kontinuum von Positionen ausgewertet werden und dadurch ein (Eck- oder Zentrums-)Punkt subpixelgenau lokalisiert werden.

• Corner detection in Scikit-image (Python)
• Feature detection in OpenCV (C++, Python)

1. ↑ OpenCV: FAST Algorithm for Corner Detection. Abgerufen am 12. Dezember 2018 (englisch). 
2. ↑ H. P. Moravec: Towards Automatic Visual Obstacle Avoidance. In: Proceedings of the 5th International Joint Conference on Artificial Intelligence. 1977, S. 584. 
3. ↑ ^{a b} C. Harris, M. Stephens: A combined corner and edge detector. In: Proceedings of the 4th Alvey Vision Conference. 1988, S. 147–151 (semanticscholar.org [PDF]). 
4. ↑ OpenCV-Tutorial
5. ↑ Volker Rodehorst, Andreas Koschan: Comparison and Evaluation of Feature Point Detectors. 2006, abgerufen am 6. Juli 2020 (englisch). 
6. ↑ Wolfgang Förstner und E. Gülch: A Fast Operator for Detection and Precise Location of Distinct Points, Corners and Centers of Circular Features. In: Proceedings of the ISPRS Intercommission Workshop on Fast Processing of Photogrammetric Data. 1987, S. 281–305. 
7. ↑ ^{a b} Wolfgang Förstner: Statistische Verfahren für die automatische Bildanalyse und ihre Bewertung bei der Objekterkennung und -vermessung (Habilitation). In: Deutsche Geodätische Kommission bei der Bayerischen Akademie der Wissenschaften (Hrsg.): DGK. Reihe C - Dissertationen, Heft Nr. 370. München 1991 (uni-bonn.de [PDF]). 
8. ↑ ^{a b} Wolfgang Förstner: A Feature Based Correspondence Algorithm For Image Matching. (PDF) In: International Archive of Photogrammetry. 1986, abgerufen am 4. Juli 2020 (englisch).