Mugichoko's blog

Mugichoko’s blog

プログラミングを中心としたメモ書き.

Lucas-Kanade法のお勉強

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

3つの仮定

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

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

導出

まずは1次元で考える

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

f:id:Mugichoko:20180405062111p:plain

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

f:id:Mugichoko:20180405053609p:plain

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

$$ 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} $$

となる.式3を図示すると,下図のようになる.この図から,1度の計算では x_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} \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{bmatrix} \sum I_x I_x & \sum I_x I_y \\ \sum I_y I_x & \sum I_y I_y \end{bmatrix} \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日)