LK法の式の導出 - 画像処理ブログ

勉強会で学んだことを書きます。

この技術についての投稿は、一つの索引用の記事にまとめられています。全体を俯瞰する場合はそちらを御覧ください。

m-yoshi-1700.hatenablog.com

LK法

画像の位置合わせ(Image Registration)の手法 CMUのBruce D. Lucas and Takeo Kanadeが開発

応用例

ステレオカメラのマッチング
パターン認識
モーション解析

特徴

テンプレートマッチに比べて高速
Newton-Raphson法を用いた球解

Webサイト

KLT: An Implementation of the Kanade-Lucas-Tomasi Feature Tracker

論文

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

https://cecas.clemson.edu/~stb/klt/lucas_bruce_d_1981_1.pdf

内容の解説

画像を与える関数をF(x)とする、その関数をhだけ動かしたものをG(x)とする。 hの初期値をh0と置いた時、hは以下の式で求められる。

${ \displaystyle \def\vector#1{\mbox{\boldmath $#1$}} \textbf{h} \approx \left[ \sum_{\textbf{x}} ( \frac {\delta F} {\delta \textbf{x}} )^{\mathrm{T}} \left[ G(\textbf{x}) - F(\textbf{x}) \right] \right] \left[ \sum_{\textbf{x}} ( \frac {\delta F} {\delta \textbf{x}} )^{\mathrm{T}} ( \frac {\delta F} {\delta \textbf{x}} ) \right] ^{-1} }$

この式がLK法の基本になります。この式を以下で導出していきます。

Image Registration

まずは問題の定義から。画像をF(x)で与えられる関数とします。 ※ xは画像上の座標、F(x)は輝度値を返します。対象画像をF(x)、テンプレートをG(x)とした時に、 F(x + h)とG(x)の違いを最小化するようなhを求めたいというのがImage Registrationの問題になります。

f:id:m-yoshi-1700:20170305165203p:plain

F(x + h)とG(x)の違いは以下の様に定義します。

L1ノルム

${ \displaystyle L_{1} norm = \sum_{\textbf{x} \in R} | F(\textbf{x} + \textbf{h}) - G(\textbf{x}) |\ }$

L2ノルム

${ \displaystyle L_{2} norm = \left( \sum_{\textbf{x} \in R} \left[ F(\textbf{x} + \textbf{h}) - G(\textbf{x}) \right]^{2} \right) ^{\frac {1} {2}} }$

Negative of normalized correlation

${ \displaystyle negative of normalized correlation = \frac {- \sum_{\textbf{x} \in R} F(\textbf{x} + \textbf{h}) G(\textbf{x}) } { \left( \sum_{\textbf{x} \in R} \left[ F(\textbf{x} + \textbf{h})\right]^{2} \right) ^{\frac {1} {2}} \left( \sum_{\textbf{x} \in R} \left[ G(\textbf{x})\right]^{2} \right) ^{\frac {1} {2}} } }$

1次元の場合を考える

まずは画像(2次元)でなく、1次元の関数で考えてみます。対象の関数をF(x)、そこからhだけ平行移動した関数をG(x)と置きます。

${ \displaystyle G(x) = F(x + h) }$

ここで、hが十分に小さいと仮定して、F(x)の一次の導関数を考える。

${ \displaystyle F'(\textbf{x}) \approx \frac {F(x + h) - F(x)} {h} = \frac {G(x) - F(x)} {h} \tag{1} }$

この式を変形する。

${ \displaystyle h \approx \frac {G(x) - F(x)} {F'(\textbf{x})} \tag{2} }$

hの式でのhの近似式はxに依存する、そこで一定の範囲について積分をする。

${ \displaystyle h \approx \left[ \sum_{x} \frac {G(x) - F(x)} {F'(\textbf{x})} \right] \left[ \sum_{x} 1 \right] ^{-1} \tag{3} }$

さて、ここでどのようなxがhを求めるのに有効かを考える。 xに対してF(x)の変化が線形であることが望ましいので、F'‘(x)の値が小さいほどhを求めるのに適したxと言える。そこで、F’‘(x)の値を重みとして先ほどの近似の式に用いる。

${ \displaystyle F^{\prime\prime}(x) \approx \frac {G'(x) - F'(x)} {h} \tag{4} }$

ここから、重みをF'‘(x)の逆数と置くと、

${ \displaystyle w(x) = \frac {1} { | G'(x) - F'(x) | } \tag{5} \label{5} }$

この重みを用いて、hの式を書き直します。

${ \displaystyle h \approx \left[ \sum_{x} \frac {w(x) [G(x) - F(x)]} {F'(\textbf{x})} \right] \left[ \sum_{x} w(x) \right] ^{-1} \tag{6} \label{6} }$

ここで、w(x)は式\eqref{5}で定義されたものです。

いやー、はてなブログ便利ですね、式の参照もリンクにしてくれる。

式\eqref{6}を繰り返すことで真値に近づきます。

${ \displaystyle h_{0} = 0\\ h_{k + 1} = h_{k} + \left[ \sum_{x} \frac {w(x) [G(x) - F(x)]} {F'(\textbf{x})} \right] \left[ \sum_{x} w(x) \right] ^{-1} \tag{7} }$

これで1次元の場合のLK方の式の導出は完了です。本日はここまで、一般化と2次元（画像）への拡張は次の記事で。