KLTトラッキング - takahiro_itazuriの公倍数的ブログ

はじめに

オプティカルフローや物体追跡について勉強するときにまず出てくるのがKLTトラッキング（Good Features To Track）とも呼ばれる。
今日はそんなKLTについてです。
この方法は「Good Features To Track」という論文で発表されている。
その名の通り、追跡するのに良い点。
画像処理をやってる人は、特徴点というワードを必ず聞いたことがあるでしょう。
これは、画像中で特徴のある点（そのままです）つまり、他と区別ができる点のことである。
そのような点というのは例えば机があったとき、どこに特徴がありそうか、、、。
特徴点としてよく用いられるのはエッジです。画像中で言うと輪郭になるような部分をエッジと呼びます。
このような特徴点を追跡するのが今回の目的です。
「ある画像フレーム内のある点が次フレームでどこに移動しているか」というのが問題の定義です。
このことをオプティカルフローと言ったりします。

オプティカルフローの拘束式

連続する二つの画像 $I(t), I(t+1)$ において、この問題を解くためにまず以下の仮定をします。

1. 画素が移動しても明るさは不変
2. 画素は滑らか（空間的・時間的に微分可能）
3. 画素の移動量は小さい

仮定1から次の式が得られます。

$I(x, y, t) = I(x+dx, y+dy, t+dt) = I(x, y, t) + \frac{\partial I}{\partial x} dx + \frac{\partial I}{\partial y} dy + \frac{\partial I}{\partial t} dt + \epsilon$

ここで二次の微小量を無視すると

$\frac{\partial I}{\partial x} \frac{dx}{dt} + \frac{\partial I}{\partial y} \frac{dy}{dt} + \frac{\partial I}{\partial t} = 0$

物理的な解釈をすると

$\frac{\partial I}{\partial x} = I_x, \frac{\partial I}{\partial y} = I_y, \frac{\partial I}{\partial t} = I_t$

と書くと、先程の式は

$(I_x, I_y)(\frac{\partial x}{\partial t}, \frac{\partial y}{\partial t})^T = -I_t$

f:id:takahiro-itazuri:20170112221308p:plain

つまり、実際の移動ベクトルのエッジに垂直な成分のみしか知り得ないのである。

追跡しやすい点とは

ここで求めたいは $(\partial x / \partial t, \partial y/ \partial t$ なのだが、式の本数は一本では足りない。
つまり、局所的な濃度勾配から完全に定めることはできない。
そこで新たに拘束条件を追加する。
追跡したい点の周囲の小領域においてオプティカルフローは同一である
という拘束を加える。
そもそも移動ベクトルが求めやすい点とはなんだろう。
f:id:takahiro-itazuri:20170112222250p:plain
Aのように濃度が一様な領域では当然だが定まらない。
Bのように一方向のエッジのみしか含まれない場合でも求まらない。（先程と同様）
Cのように複数方向のエッジ成分が含まれているような点でないと、フローは安定して定まらない。
それではCのような領域をどのようにして発見するのか。
f:id:takahiro-itazuri:20170112222515p:plain
ある点 $(x_0, y_0)$ を中心とする小領域とそこから微小量だけ移動した $(x_0 + dx, y_0 + dy)$ を中心とする小領域について考えるときに、
いかなる微小変分 $(dx, dy)$ においてもこの二つの小領域の似ていなければよい。
ここで、この二つの小領域の相違度を画素ごとの差分の二乗和とすると

$E(dx, dy) = \sum_{u, v} (I(x_0+dx+u, y_0+dy+v) - I(x_o+u, y_0+v))^2 w(u, v)$

ここで $w(u, v)$ は例えばガウス関数とする（つまり、真ん中の画素値をより信頼する）。
Taylor展開をして二次の微小項を無視すると

$E(dx, dy) = \sum_{u, v}(I_x(x_0+u, y_0+v) dx + I_y(x_0+u, y_0+v) dy)^2 w(u, v)$

ここで

$\sum_{u, v}I_x(x_0+u, y_0+v) = \sum I_x$

のようにsummationを略記すると、

$E=\sum w I_{x}^{2} dx^2 + 2 \sum w I_x I_y dx dy + \sum w I_{y}^{2} dy^2$

$= \begin{pmatrix}dx & dy\end{pmatrix} \begin{pmatrix}\sum w I_{x}^{2} & \sum w I_x I_y \\ \sum w I_x I_y & \sum w I_{y}^{2} \end{pmatrix} \begin{pmatrix}dx \\ dy\end{pmatrix}$

この真ん中の行列を構造行列(structure matrix)と呼ぶ。
この行列は微小変分 $dx, dy$ に対して相違の量を示している。
このとき、いかなる変分に対しても相違が大きくなるような小領域が追跡点として好ましいということであったので、構造行列の二つの固有値がともに大きくなる小領域が追跡点として好ましいことになる。
f:id:takahiro-itazuri:20170112224638p:plain

f:id:takahiro-itazuri:20170112224638p:plain

たとえば、二つの固有値のどちらかが大きくどちらかが小さいとき、小さい方の固有値に対する固有ベクトルの方向に相違度が小さくなり、またどちらの固有値も小さいとき、どの方向に進んでも相違度が小さいことがわかる。
このことを利用して特徴点を検出するオペレータをHarissオペレータと呼ぶ。

$H(x_0, y_0)=det(G) - k(tr(G))^2 = \lambda_1 \lambda_2 - k(\lambda_1^2 + \lambda_2^2)^2$

追跡の方法

最も単純な追跡の方法として、ブロックマッチングがある。
これは小領域を探索範囲内で走査していき、相違度が最も小さい点を探索する。
f:id:takahiro-itazuri:20170112225943p:plain
しかし、これでは計算量が膨大すぎるので、濃度勾配を利用する。
ここで二つの連続する画像 $I, J$ において、

$I(x, y) = J(x+dx, y+dy)$

$I(x-dx, y-dy) = J(x, y)$

であり、小領域内での相違度は

$\epsilon = \sum_{u, v} (I(x-dx+u, y-dy+v) - J(x+u, y+v))^2 w(u, v)$

$= \sum (I- I_x dx - I_y dy - J)^2 w$

$= (h- I_x dx - I_y dy)-2 w$

$= (h - \begin{pmatrix}I_x & I_y \end{pmatrix} \begin{pmatrix} dx \\ dy \end{pmatrix})^2 w$

ただし $h=I-J$ である。
ここで $\epsilon$ が最小値を取るような $(dx, dy)$ を求めればよいので、 $(dx, dy)$ で $\epsilon$ は極小値を取る。
つまり、微分値は0なので、

$\sum (h - \begin{pmatrix} I_x & I_y \end{pmatrix} \begin{pmatrix} dx \\ dy \end{pmatrix}) \begin{pmatrix} I_x \\ I_y \end{pmatrix} w = 0$

$\sum \begin{pmatrix} I_x^2 & I_x I_y \\ I_x I_y & I_y^2 \end{pmatrix} \begin{pmatrix} dx \\ dy \end{pmatrix} w = \sum h \begin{pmatrix} I_x \\ I_y \end{pmatrix} w$

$G \begin{pmatrix} dx \\ dy \end{pmatrix} = \begin{pmatrix} \sum w (I-J) I_x \\ \sum w (I-J) I_y \end{pmatrix} = e$

このときに構造行列の逆行列が存在すれば、解が求まる。
解の良さは次のようにして確認ができる。

determinantが大きい
二つの固有値がどちらも微小でない
二つの固有値に差がありすぎない

したがって、determinantが大きい点のみを対象に選べばよい。

山登り法

ここで最初に説明した「画素の移動量が小さい」という仮定を思い出してほしい。
f:id:takahiro-itazuri:20170112234647p:plain
ここでは、移動量か大きい物体に対して、無理やり解像度を落とすことで移動量を小さくするという戦法を取ります。
このためのダウンサンプリングした画像群をガウシアンピラミッドと呼びます。
小さい画像からあらかたの位置を求め、解像度を上げていくことで真値に近いフローを求めることができます。

目次

はじめに

オプティカルフローの拘束式

追跡しやすい点とは

追跡の方法

山登り法