Lucas-Kanade-Methode

Die Lucas-Kanade-Methode zur Berechnung des optischen Flusses geht auf die beiden Forscher Bruce D. Lucas und Takeo Kanade zurück. Sie schlugen diese Methode erstmals 1981 vor. Die Methode ist ein beliebtes Verfahren, das noch heute weite Anwendung findet. Die Zusatzbedingung, die zur Berechnung des optischen Flusses benötigt wird, ist die Annahme der Gleichheit des Flusses in der lokalen Umgebung des zentralen Pixels, für den der Fluss bestimmt wird.

Mathematische Grundlagen

Die Lucas-Kanade-Methode beruht auf der Grundgleichung des optischen Flusses. Der Fluss für zwei 3D-Bildvolumina (2D- oder nD-Fälle sind ähnlich) ist gegeben durch $(V_{x},V_{y},V_{z})$. In einer kleinen Umgebung $m\times m\times m$ mit $m>1$, die ihr Zentrum im Voxel $x,y,z$ hat, wird der Fluss als konstant angesehen. Diese Annahme trifft im Allgemeinen dann zu, wenn die Zeitschritte zwischen den Bildern klein genug gewählt werden. $I_{x}$, $I_{y}$, $I_{z}$, $I_{t}$ bezeichnen die partiellen Ableitungen des Bildes in $x$-, $y$-, $z$-Richtung und der Zeit. Nummeriert man die Voxel mit $1\dotsc n$, $n=m^{3}$, so kann ein Gleichungssystem aufgestellt werden:

$I_{x_{1}}V_{x}+I_{y_{1}}V_{y}+I_{z_{1}}V_{z}=-I_{t_{1}}$

$I_{x_{2}}V_{x}+I_{y_{2}}V_{y}+I_{z_{2}}V_{z}=-I_{t_{2}}$

$\vdots$

$I_{x_{n}}V_{x}+I_{y_{n}}V_{y}+I_{z_{n}}V_{z}=-I_{t_{n}}$

Damit erhalten wir mehr als drei Gleichungen für die drei gesuchten Flussvariablen. Es liegt ein überbestimmtes System vor. Es gilt:

${\begin{bmatrix}I_{x_{1}}&I_{y_{1}}&I_{z_{1}}\\I_{x_{2}}&I_{y_{2}}&I_{z_{2}}\\\vdots &\vdots &\vdots \\I_{x_{n}}&I_{y_{n}}&I_{z_{n}}\end{bmatrix}}{\begin{bmatrix}V_{x}\\V_{y}\\V_{z}\end{bmatrix}}={\begin{bmatrix}-I_{t_{1}}\\-I_{t_{2}}\\\vdots \\-I_{t_{n}}\end{bmatrix}}$

Das überbestimmte System kann nun mit der Methode der kleinsten Quadrate gelöst werden:

$A{\vec {v}}=-b$

$A^{T}A{\vec {v}}=A^{T}(-b)$

oder

${\vec {v}}=(A^{T}A)^{-1}A^{T}(-b)$

oder

${\begin{bmatrix}V_{x}\\V_{y}\\V_{z}\end{bmatrix}}={\begin{bmatrix}\sum I_{x_{i}}^{2}&\sum I_{x_{i}}I_{y_{i}}&\sum I_{x_{i}}I_{z_{i}}\\\sum I_{x_{i}}I_{y_{i}}&\sum I_{y_{i}}^{2}&\sum I_{y_{i}}I_{z_{i}}\\\sum I_{x_{i}}I_{z_{i}}&\sum I_{y_{i}}I_{z_{i}}&\sum I_{z_{i}}^{2}\\\end{bmatrix}}^{-1}{\begin{bmatrix}-\sum I_{x_{i}}I_{t_{i}}\\-\sum I_{y_{i}}I_{t_{i}}\\-\sum I_{z_{i}}I_{t_{i}}\end{bmatrix}}$

Die Summe läuft hier von i=1 bis n.

Der Fluss kann somit auf den Bildern durch Berechnung der Ableitungen (=Gradienten) ermittelt werden. Um dem Zentralvoxel mehr Gewicht zu verleihen, verwendet man häufig eine Gewichtungsformel W(i,j,k), mit $i,j,k\in [1,m]$. Hierzu können gaußsche Funktionen verwendet werden. Andere Erweiterungen der Lucas-Kanade-Methode benutzen statistische Methoden, um besser mit Rauschen umzugehen.

Diese Methode wird auch in einem hierarchischen Verfahren angewandt, bei dem der Fluss zuerst auf einer groberen Skala berechnet wird und dann sukzessiv auf einer immer feiner werdenden Skala präzisiert wird.

Eigenschaften

Eine der Eigenschaften der Lucas-Kanade-Methode ist, dass sie (wie andere lokale Methoden zur Berechnung des optischen Flusses) keinen dichten Fluss liefert (d. h. sparse, nicht dense). Die Flussinformation schwindet schnell mit dem Abstand von den Rändern (Kanten oder Ecken). Der Vorteil der Methode besteht in der relativen Robustheit gegenüber Rauschen und kleineren Defekten im Bild.

Literatur

• Lucas B D and Kanade T 1981, An iterative image registration technique with an application to stereo vision. Proceedings of Imaging understanding workshop, pp 121--130 (pdf).
• Lucas B D 1984, Generalized Image Matching by the Method of Differences, Dissertation.

Weblinks

• Bildstabilisierung für ImageJ die auf Lucas–Kanade-Methode beruht.
• KLT: Kanade–Lucas–Tomasi Feature Tracker
• Takeo Kanade