Lucas-Kanade-Methode – Wikipedia

In der Computer Vision ist die Lucas-Kanade-Methode ist eine weit verbreitete Differentialmethode zur optischen Flussschätzung, die von Bruce D. Lucas und Takeo Kanade entwickelt wurde. Es wird angenommen, dass der Fluss in einer lokalen Nachbarschaft des betrachteten Pixels im Wesentlichen konstant ist, und es werden die grundlegenden optischen Flussgleichungen für alle Pixel in dieser Nachbarschaft nach dem Kriterium der kleinsten Quadrate gelöst.^[1][2]

Durch die Kombination von Informationen aus mehreren nahe gelegenen Pixeln kann die Lucas-Kanade-Methode häufig die inhärente Mehrdeutigkeit der optischen Flussgleichung auflösen. Es ist auch weniger empfindlich gegenüber Bildrauschen als punktuelle Methoden. Da es sich jedoch um eine rein lokale Methode handelt, kann sie keine Flussinformationen im Inneren einheitlicher Bereiche des Bildes liefern.

Konzept[edit]

Bei der Lucas-Kanade-Methode wird davon ausgegangen, dass die Verschiebung des Bildinhalts zwischen zwei nahe gelegenen Zeitpunkten (Frames) klein und in der Nähe des Punkts ungefähr konstant ist p unter Berücksichtigung. Somit kann angenommen werden, dass die optische Flussgleichung für alle Pixel innerhalb eines Fensters gilt, das bei zentriert ist p. Der lokale Bildflussvektor (Geschwindigkeitsvektor)

${ displaystyle (V_ {x}, V_ {y})}$

muss befriedigen

${ displaystyle I_ {x} (q_ {1}) V_ {x} + I_ {y} (q_ {1}) V_ {y} = – I_ {t} (q_ {1})}$

${ displaystyle I_ {x} (q_ {2}) V_ {x} + I_ {y} (q_ {2}) V_ {y} = – I_ {t} (q_ {2})}$

after-content-x4

${ displaystyle vdots}$

${ displaystyle I_ {x} (q_ {n}) V_ {x} + I_ {y} (q_ {n}) V_ {y} = – I_ {t} (q_ {n})}$

wo

${ displaystyle q_ {1}, q_ {2}, dots, q_ {n}}$

sind die Pixel im Fenster und

${ displaystyle I_ {x} (q_ {i}), I_ {y} (q_ {i}), I_ {t} (q_ {i})}$

sind die partiellen Ableitungen des Bildes

${ displaystyle I}$

in Bezug auf die Position x, y und Zeit t, am Punkt ausgewertet

${ displaystyle q_ {i}}$

und zur aktuellen Zeit.

Diese Gleichungen können in Matrixform geschrieben werden

${ displaystyle Av = b}$

, wo

${ displaystyle A = { begin {bmatrix} I_ {x} (q_ {1}) & I_ {y} (q_ {1}) \[10pt]I_ {x} (q_ {2}) & I_ {y} (q_ {2}) \[10pt] vdots & vdots \[10pt]I_ {x} (q_ {n}) & I_ {y} (q_ {n}) end {bmatrix}} quad quad quad v = { begin {bmatrix} V_ {x} \[10pt]V_ {y} end {bmatrix}} quad quad quad b = { begin {bmatrix} -I_ {t} (q_ {1}) \[10pt]-I_ {t} (q_ {2}) \[10pt] vdots \[10pt]-I_ {t} (q_ {n}) end {bmatrix}}}$

Dieses System hat mehr Gleichungen als Unbekannte und ist daher normalerweise überbestimmt. Die Lucas-Kanade-Methode erhält eine Kompromisslösung nach dem Prinzip der kleinsten Quadrate. Es löst nämlich das 2 × 2-System

${ displaystyle A ^ {T} Av = A ^ {T} b}$

oder

${ displaystyle mathrm {v} = (A ^ {T} A) ^ {- 1} A ^ {T} b}$

wo

${ displaystyle A ^ {T}}$

ist die Transponierte der Matrix

${ displaystyle A}$

. Das heißt, es wird berechnet

${ displaystyle { begin {bmatrix} V_ {x} \[10pt]V_ {y} end {bmatrix}} = { begin {bmatrix} sum _ {i} I_ {x} (q_ {i}) ^ {2} & sum _ {i} I_ {x} (q_ {i}) I_ {y} (q_ {i}) \[10pt] sum _ {i} I_ {y} (q_ {i}) I_ {x} (q_ {i}) & sum _ {i} I_ {y} (q_ {i}) ^ {2} end { bmatrix}} ^ {- 1} { begin {bmatrix} – sum _ {i} I_ {x} (q_ {i}) I_ {t} (q_ {i}) \[10pt]- sum _ {i} I_ {y} (q_ {i}) I_ {t} (q_ {i}) end {bmatrix}}}$

wobei die zentrale Matrix in der Gleichung eine inverse Matrix ist. Die Summen laufen ab ich= 1 bis n.

Die Matrix

${ displaystyle A ^ {T} A}$

wird oft als Strukturtensor des Bildes am Punkt bezeichnet p.

Gewichtetes Fenster[edit]

Die obige einfache Lösung der kleinsten Quadrate gibt allen die gleiche Bedeutung n Pixel

${ displaystyle q_ {i}}$

im Fenster. In der Praxis ist es normalerweise besser, den Pixeln, die näher am zentralen Pixel liegen, mehr Gewicht zu geben p. Dafür verwendet man die gewichtete Version der Gleichung der kleinsten Quadrate,

${ displaystyle A ^ {T} WAv = A ^ {T} Wb}$

oder

${ displaystyle mathrm {v} = (A ^ {T} WA) ^ {- 1} A ^ {T} Wb}$

wo

${ displaystyle W}$

ist ein n×n Diagonalmatrix mit den Gewichten

${ displaystyle W_ {ii} = w_ {i}}$

der Pixelgleichung zugeordnet werden

${ displaystyle q_ {i}}$

. Das heißt, es wird berechnet

${ displaystyle { begin {bmatrix} V_ {x} \[10pt]V_ {y} end {bmatrix}} = { begin {bmatrix} sum _ {i} w_ {i} I_ {x} (q_ {i}) ^ {2} & sum _ {i} w_ { i} I_ {x} (q_ {i}) I_ {y} (q_ {i}) \[10pt] sum _ {i} w_ {i} I_ {x} (q_ {i}) I_ {y} (q_ {i}) & sum _ {i} w_ {i} I_ {y} (q_ {i} ) ^ {2} end {bmatrix}} ^ {- 1} { begin {bmatrix} – sum _ {i} w_ {i} I_ {x} (q_ {i}) I_ {t} (q_ { ich})\[10pt]- sum _ {i} w_ {i} I_ {y} (q_ {i}) I_ {t} (q_ {i}) end {bmatrix}}}$

Das Gewicht

${ displaystyle w_ {i}}$

wird normalerweise auf eine Gaußsche Funktion des Abstandes zwischen eingestellt

${ displaystyle q_ {i}}$

und p.

Verwenden Sie Bedingungen und Techniken[edit]

Um die Gleichung

${ displaystyle A ^ {T} Av = A ^ {T} b}$

lösbar sein,

${ displaystyle A ^ {T} A}$

sollte invertierbar sein, oder

${ displaystyle A ^ {T} A}$

Eigenwerte erfüllen

${ displaystyle lambda _ {1} geq lambda _ {2}> 0}$

${ displaystyle lambda _ {2}}$

muss nicht zu klein sein. Auch wenn

${ displaystyle lambda _ {1} / lambda _ {2}}$

zu groß ist, bedeutet dies, dass der Punkt p befindet sich an einer Kante, und diese Methode leidet unter dem Aperturproblem. Damit diese Methode richtig funktioniert, ist die Bedingung, dass

${ displaystyle lambda _ {1}}$

und

${ displaystyle lambda _ {2}}$

sind groß genug und haben eine ähnliche Größe. Diese Bedingung gilt auch für die Eckenerkennung. Diese Beobachtung zeigt, dass man leicht erkennen kann, welches Pixel für die Lucas-Kanade-Methode geeignet ist, indem man ein einzelnes Bild untersucht.

Eine Hauptannahme für dieses Verfahren ist, dass die Bewegung klein ist (zum Beispiel weniger als 1 Pixel zwischen zwei Bildern). Wenn die Bewegung groß ist und gegen diese Annahme verstößt, besteht eine Technik darin, zuerst die Auflösung der Bilder zu verringern und dann die Lucas-Kanade-Methode anzuwenden.
^[3]

Um mit dieser Methode eine Bewegungsverfolgung zu erreichen, kann der Strömungsvektor iterativ angewendet und neu berechnet werden, bis ein Schwellenwert nahe Null erreicht ist. An diesem Punkt kann angenommen werden, dass die Bildfenster sehr ähnlich sind.^[1] Auf diese Weise kann der Punkt in jedem aufeinanderfolgenden Verfolgungsfenster über mehrere Bilder in einer Sequenz verfolgt werden, bis er entweder verdeckt ist oder den Rahmen verlässt.

Verbesserungen und Erweiterungen[edit]

Der Ansatz der kleinsten Quadrate geht implizit davon aus, dass die Fehler in den Bilddaten eine Gaußsche Verteilung mit dem Mittelwert Null haben. Wenn man erwartet, dass das Fenster einen bestimmten Prozentsatz von enthält “Ausreißer” (grob falsche Datenwerte, die nicht dem folgen “gewöhnliche” Gaußsche Fehlerverteilung) kann man statistische Analysen verwenden, um sie zu erkennen und ihr Gewicht entsprechend zu reduzieren.

Die Lucas-Kanade-Methode an sich kann nur verwendet werden, wenn der Bildflussvektor

${ displaystyle V_ {x}, V_ {y}}$

zwischen den beiden Rahmen ist klein genug, damit die Differentialgleichung des optischen Flusses Bestand hat, die oft kleiner als der Pixelabstand ist. Wenn der Flussvektor diese Grenze überschreiten kann, z. B. beim Stereo-Matching oder bei der Registrierung verzerrter Dokumente, kann die Lucas-Kanade-Methode weiterhin verwendet werden, um eine grobe Schätzung desselben zu verfeinern, die auf andere Weise erhalten wird. Zum Beispiel durch Extrapolation der für vorherige Frames berechneten Flussvektoren oder durch Ausführen des Lucas-Kanade-Algorithmus für verkleinerte Versionen der Bilder. Tatsächlich ist die letztere Methode die Grundlage des beliebten Feature-Matching-Algorithmus Kanade-Lucas-Tomasi (KLT).

Eine ähnliche Technik kann verwendet werden, um differentielle affine Verformungen des Bildinhalts zu berechnen.

Siehe auch[edit]

Verweise[edit]

Externe Links[edit]