KLTトラッキング
はじめに
オプティカルフローや物体追跡について勉強するときにまず出てくるのがKLTトラッキング(Good Features To Track)とも呼ばれる。
今日はそんなKLTについてです。
この方法は「Good Features To Track」という論文で発表されている。
その名の通り、追跡するのに良い点。
画像処理をやってる人は、特徴点というワードを必ず聞いたことがあるでしょう。
これは、画像中で特徴のある点(そのままです)つまり、他と区別ができる点のことである。
そのような点というのは例えば机があったとき、どこに特徴がありそうか、、、。
特徴点としてよく用いられるのはエッジです。画像中で言うと輪郭になるような部分をエッジと呼びます。
このような特徴点を追跡するのが今回の目的です。
「ある画像フレーム内のある点が次フレームでどこに移動しているか」というのが問題の定義です。
このことをオプティカルフローと言ったりします。
オプティカルフローの拘束式
連続する二つの画像において、この問題を解くためにまず以下の仮定をします。
1. 画素が移動しても明るさは不変
2. 画素は滑らか(空間的・時間的に微分可能)
3. 画素の移動量は小さい
仮定1から次の式が得られます。
ここで二次の微小量を無視すると物理的な解釈をすると と書くと、先程の式は
つまり、実際の移動ベクトルのエッジに垂直な成分のみしか知り得ないのである。
追跡しやすい点とは
ここで求めたいはなのだが、式の本数は一本では足りない。
つまり、局所的な濃度勾配から完全に定めることはできない。
そこで新たに拘束条件を追加する。
追跡したい点の周囲の小領域においてオプティカルフローは同一である
という拘束を加える。
そもそも移動ベクトルが求めやすい点とはなんだろう。
Aのように濃度が一様な領域では当然だが定まらない。
Bのように一方向のエッジのみしか含まれない場合でも求まらない。(先程と同様)
Cのように複数方向のエッジ成分が含まれているような点でないと、フローは安定して定まらない。
それではCのような領域をどのようにして発見するのか。
ある点を中心とする小領域とそこから微小量だけ移動したを中心とする小領域について考えるときに、
いかなる微小変分においてもこの二つの小領域の似ていなければよい。
ここで、この二つの小領域の相違度を画素ごとの差分の二乗和とすると
Taylor展開をして二次の微小項を無視すると
ここでのようにsummationを略記すると、この真ん中の行列を構造行列(structure matrix)と呼ぶ。
この行列は微小変分に対して相違の量を示している。
このとき、いかなる変分に対しても相違が大きくなるような小領域が追跡点として好ましいということであったので、構造行列の二つの固有値がともに大きくなる小領域が追跡点として好ましいことになる。
たとえば、二つの固有値のどちらかが大きくどちらかが小さいとき、小さい方の固有値に対する固有ベクトルの方向に相違度が小さくなり、またどちらの固有値も小さいとき、どの方向に進んでも相違度が小さいことがわかる。
このことを利用して特徴点を検出するオペレータをHarissオペレータと呼ぶ。
追跡の方法
最も単純な追跡の方法として、ブロックマッチングがある。
これは小領域を探索範囲内で走査していき、相違度が最も小さい点を探索する。
しかし、これでは計算量が膨大すぎるので、濃度勾配を利用する。
ここで二つの連続する画像において、
ただしである。
ここでが最小値を取るようなを求めればよいので、では極小値を取る。
つまり、微分値は0なので、
このときに構造行列の逆行列が存在すれば、解が求まる。
解の良さは次のようにして確認ができる。
したがって、determinantが大きい点のみを対象に選べばよい。
山登り法
ここで最初に説明した「画素の移動量が小さい」という仮定を思い出してほしい。
ここでは、移動量か大きい物体に対して、無理やり解像度を落とすことで移動量を小さくするという戦法を取ります。
このためのダウンサンプリングした画像群をガウシアンピラミッドと呼びます。
小さい画像からあらかたの位置を求め、解像度を上げていくことで真値に近いフローを求めることができます。