私が学生の頃にLucas-Kanade法に関して頭の整理のためにまとめた資料です．実装して確認したわけではないので理解が間違っているかも... お気づきの方がおられたらコメントお願い致します．

3つの仮定

Lucas-Kanade (LK) 法は，Bruce D. LucasとTakeo Kanade（金出武雄）によって提案された，オプティカルフローを計算するアルゴリズムである[1]．LK法は，以下の3つを仮定している．

明るさの不変性 フレームが変化しても，ある点の色は変化しない
時間的な連続性 ある点の動きは微小である
空間的な一様性 ある点の周辺は同じ面に属している

導出

まずは1次元で考える

まずは1次元の場合を考える．1列に並んだ連続の画像 $I$ が存在し，その内の画像Iのある点xでの強度値を $I(x)$ とする．

続いて，ある時間 $t$ においての画像 $I$ 中のある点 $x(t)$ での $I$ の強度値を $I(x(t),t)$ とする． $I(x(t),t)$ は「時間が異なれば，画像 $I$ 中のある点の位置も画像自体も変化する」という意味に解釈できる．ここで，時間 $dt$ だけ経過したとすると， $I(x(t+dt),t+dt)$ が得られる．

以上より，まず，明るさの普遍性は，次式で表せる．

$I(x(t+dt),t+dt)−I(x(t),t)=0 \tag{1}$

つまり， $I(x(t),t)$ を時間方向に微分しても変化しないので $0$ となる．

$\frac{\delta I(x(t), t)}{\delta t} = \frac{\delta I}{\delta x}\frac{dx}{dt} + \frac{\delta I}{\delta t} = 0 \tag{2}$

ここで， $\frac{\delta I}{\delta x}$ は空間方向の偏微分， $\frac{dx}{dt}$ は求めたい移動量， $\frac{\delta I}{\delta t}$ は時間方向の偏微分である．尚，2つめの式への変換には合成関数の偏微分法（[4] 参照）を用いる．

$I_x = \frac{\delta I}{\delta x}$ ， $v = \frac{dx}{dt}$ ， $I_t = \frac{\delta I}{\delta t}$ としたとき，求めたい値 $v$ は，

$v = - \frac{I_t}{I_x} \tag{3}$

となる．ただし，1度の計算では求めたい位置の手前までしか到達できない．よって， $x$ 及び $I_t$ の値を更新し，式3を用いて $v$ を繰り返し求めていく必要がある．この処理はNewton法であり，5回程度繰り返せば収束することが知られている[2]．

2次元で考える

式1にy(t)も含めると，式(2)は以下のようになる．

$\frac{\delta I}{\delta x}\frac{dx}{dt} + \frac{\delta I}{\delta y}\frac{dy}{dt} + \frac{\delta I}{\delta t} = 0 \tag{4}$

$I_x u + I_y v + I_t = 0 \tag{5}$

この時，未知数は $u$ と $v$ の2つ，式は1つしかないため解けない．よって， $n$ ( $\geq 2$ ) コの画素 $p_i$ ( $i = {0, 1, ..., n - 1}$ ) について考え，連立方程式を立てる必要がある．これは， $n$ 画素を含む窓を設けることに相当する．ここに空間的な一様性が想定されている．

$\begin{split} I_x(p_0) u + I_y(p_0) v + I_t(p_0) = 0 \\ I_x(p_1) u + I_y(p_1) v + I_t(p_1) = 0 \\ \vdots \qquad\qquad\qquad \\ I_x(p_{n-1}) u + I_y(p_{n-1}) v + I_t(p_{n-1}) = 0 \\ \end{split} \tag{6}$

これを行列で表すと，

$\begin{bmatrix} I_x(p_0) & I_y(p_0) \\\ I_x(p_1) & I_y(p_1) \\\ \vdots & \vdots \\\ I_x(p_{n-1}) & I_y(p_{n-1}) \end{bmatrix} \begin{bmatrix} u\\\ v \end{bmatrix} = - \begin{bmatrix} I_t(p_0)\\\ I_t(p_1)\\\ \vdots \\\ I_t(p_{n-1}) \end{bmatrix} \tag{7}$

となる．これは ${\bf A x} = {\bf b}$ の正規表現となっている．つまり「線形最小二乗」によって $u$ と $v$ を計算できる．これに関しては以下のように計算することが一般的であるようだ．

${\bf A^T Ax } = -{\bf A^T b } \tag{8}$

${\bf x } = -({\bf A^T A })^{-1} {\bf A^T b } \tag{9}$

このとき，

${\bf A^T A } = \begin{pmatrix} \sum I_x I_x & \sum I_x I_y \\\ \sum I_y I_x & \sum I_y I_y \end{pmatrix} \tag{10}$

ただし，式(9)の様に解けるのは， ${\bf A^T Ax }$ に逆行列が存在するときであるから，そのランク（階数）が最大の2（フルランク）を持つときである．これは，Harrisオペレータ[3]との説明にもつながる．

アパーチャ問題

窓を設ける $p_i$ において $i \geq 2$ を想定することで，この問題が発生する．[2]の図解が分かりやすい．

参考文献

[1] Bruce D. Lucas and Takeo Kanade. An Iterative Image Registration Technique with an Application to Stereo Vision. International Joint Conference on Artificial Intelligence, pp. 674-679, 1981.

[2] Gary Bradski and Adrian Kaebler 著, Learning OpenCV, Shroff Publishers & Distributors Pvt Ltd, 2008.

[3] C. Harris and M. Stephens: “A Combined Corner and Edge Detector,” Proc. Alvey Vision Conf., pp. 147-151, 1988.

[4] http://next1.msi.sk.shibaura-it.ac.jp/SHIBAURA/2012-1/calc2/lecture4.pdf（最終更新確認日：2015年7月14日）