目的

オプティカルフローの概念と、Lucas-Kanade 法を用いたその推定について理解する。
cv.calcOpticalFlowPyrLK() のような関数を使って、動画中の特徴点を追跡する。

オプティカルフロー

オプティカルフローとは、物体やカメラの動きによって生じる、連続する2枚のフレーム間での画像中の物体の見かけの動きのパターンである。これは2次元のベクトル場であり、各ベクトルは最初のフレームから2番目のフレームへの点の移動を示す変位ベクトルである。下の画像を見てほしい(画像提供: オプティカルフローに関する Wikipedia の記事)。

image

これは連続する5枚のフレーム中をボールが移動している様子を示している。矢印はその変位ベクトルを表す。オプティカルフローは次のような分野で多くの応用がある:

Structure from Motion
動画圧縮
動画の手ブレ補正 ...

オプティカルフローはいくつかの仮定の上に成り立つ:

ある物体のピクセル強度は連続するフレーム間で変化しない。
近傍のピクセルは同様の動きをする。

最初のフレーム中のピクセル \(I(x,y,t)\) を考える(ここで新たに時間という次元が追加されていることに注意。これまでは画像だけを扱っていたので時間は不要だった)。このピクセルは、\(dt\) 時間後に撮影された次のフレームで距離 \((dx,dy)\) だけ移動する。これらのピクセルは同一であり強度も変化しないので、次のように表せる。

\[I(x,y,t) = I(x+dx, y+dy, t+dt)\]

次に右辺をテイラー級数で近似し、共通項を消去して \(dt\) で割ると、次の式が得られる。

\[f_x u + f_y v + f_t = 0 \;\]

ここで:

\[f_x = \frac{\partial f}{\partial x} \; ; \; f_y = \frac{\partial f}{\partial y}\]

\[u = \frac{dx}{dt} \; ; \; v = \frac{dy}{dt}\]

上の式はオプティカルフロー方程式と呼ばれる。この式では \(f_x\) と \(f_y\) を求めることができ、これらは画像勾配である。同様に \(f_t\) は時間方向の勾配である。しかし \((u,v)\) は未知である。この1本の方程式を2つの未知変数について解くことはできない。そこでこの問題を解くためにいくつかの手法が提供されており、その1つが Lucas-Kanade である。

Lucas-Kanade法

先ほど、近傍のピクセルはすべて同様の動きをするという仮定を見た。Lucas-Kanade 法では、対象点の周囲の 3x3 のパッチを取る。したがって9個の点はすべて同じ動きをする。これら9個の点について \((f_x, f_y, f_t)\) を求めることができる。こうして問題は、2つの未知変数を持つ9本の方程式を解くことになり、これは過剰決定系である。より良い解は最小二乗法によって得られる。以下が最終的な解であり、これは未知数2つ・方程式2つの問題となっていて、解いて答えを得る。

\[\begin{bmatrix} u \\ v \end{bmatrix} = \begin{bmatrix} \sum_{i}{f_{x_i}}^2 & \sum_{i}{f_{x_i} f_{y_i} } \\ \sum_{i}{f_{x_i} f_{y_i}} & \sum_{i}{f_{y_i}}^2 \end{bmatrix}^{-1} \begin{bmatrix} - \sum_{i}{f_{x_i} f_{t_i}} \\ - \sum_{i}{f_{y_i} f_{t_i}} \end{bmatrix}\]

(この逆行列が Harris コーナー検出器と類似していることに注目。これはコーナーが追跡に適した点であることを示している。)

ユーザの視点から見ると、考え方は単純である。追跡したい点をいくつか与えると、それらの点のオプティカルフローベクトルが得られる。しかしここでも問題がある。これまでは小さな動きを扱ってきた。そのため大きな動きがある場合には失敗する。そこで再びピラミッドを使う。ピラミッドを上っていくと、小さな動きは取り除かれ、大きな動きが小さな動きになる。そこで Lucas-Kanade をそこに適用すれば、スケールとともにオプティカルフローが得られる。

OpenCV.js における Lucas-Kanade オプティカルフロー

次の関数を使用する: cv.calcOpticalFlowPyrLK (prevImg, nextImg, prevPts, nextPts, status, err, winSize = new cv.Size(21, 21), maxLevel = 3, criteria = new cv.TermCriteria(cv.TermCriteria_COUNT+ cv.TermCriteria_EPS, 30, 0.01), flags = 0, minEigThreshold = 1e-4)。

引数

prevImg	1枚目の8ビット入力画像、または buildOpticalFlowPyramid で構築されたピラミッド。
nextImg	prevImg と同じサイズ・同じ型の2枚目の入力画像、またはピラミッド。
prevPts	フローを求める対象となる 2D 点のベクトル。点の座標は単精度浮動小数点数でなければならない。
nextPts	2枚目の画像における入力特徴の計算済みの新しい位置を含む、2次元点(単精度浮動小数点座標)の出力ベクトル。cv.OPTFLOW_USE_ INITIAL_FLOW フラグが渡された場合、このベクトルは入力と同じサイズでなければならない。
status	出力ステータスベクトル(unsigned char 型)。対応する特徴のフローが見つかった場合、ベクトルの各要素は1に設定され、そうでない場合は0に設定される。
err	誤差の出力ベクトル。ベクトルの各要素は対応する特徴に対する誤差に設定される。誤差尺度の種類は flags 引数で設定できる。フローが見つからなかった場合は誤差は定義されない(そのようなケースを見つけるには status 引数を使用する)。
winSize	各ピラミッドレベルにおける探索ウィンドウのサイズ。
maxLevel	0始まりのピラミッドの最大レベル番号。0に設定するとピラミッドは使用されず(単一レベル)、1に設定すると2レベル、以下同様となる。入力にピラミッドが渡された場合、アルゴリズムはピラミッドが持つだけのレベルを使用するが、maxLevel を超えることはない。
criteria	反復探索アルゴリズムの終了条件を指定する引数(指定された最大反復回数 criteria.maxCount に達したとき、または探索ウィンドウの移動量が criteria.epsilon 未満になったとき)。
flags	操作フラグ: cv.OPTFLOW_USE_INITIAL_FLOW は nextPts に格納された初期推定値を使用する。フラグが設定されていない場合は、prevPts が nextPts にコピーされ、初期推定値として扱われる。 cv.OPTFLOW_LK_GET_MIN_EIGENVALS は誤差尺度として最小固有値を使用する(minEigThreshold の説明を参照)。フラグが設定されていない場合は、元の点と移動した点の周囲のパッチ間のL1距離をウィンドウ内のピクセル数で割った値が誤差尺度として使用される。
minEigThreshold	アルゴリズムはオプティカルフロー方程式の 2x2 正規行列の最小固有値を計算し、それをウィンドウ内のピクセル数で割る。この値が minEigThreshold より小さい場合、対応する特徴はフィルタで除外されそのフローは処理されない。これにより不良な点を除去し処理速度を向上できる。

試してみよう

(このコードは次のキーポイントがどれだけ正しいかをチェックしていない。そのため、ある特徴点が画像から消えたとしても、オプティカルフローがそれに近く見える次の点を見つける可能性がある。したがって実際にはロバストな追跡のために、コーナー点を一定の間隔で検出すべきである。)

OpenCV.js における密なオプティカルフロー

Lucas-Kanade 法は疎な特徴セット(この例では Shi-Tomasi アルゴリズムで検出されたコーナー)に対してオプティカルフローを計算する。OpenCV.js は密なオプティカルフローを求める別のアルゴリズムも提供している。これはフレーム内のすべての点についてオプティカルフローを計算する。これは Gunnar Farneback のアルゴリズムに基づいており、2003年に Gunnar Farneback による "Two-Frame Motion Estimation Based on Polynomial Expansion" で説明されている。

次の関数を使用する: cv.calcOpticalFlowFarneback (prev, next, flow, pyrScale, levels, winsize, iterations, polyN, polySigma, flags)

引数

prev	1番目の8ビットシングルチャンネル入力画像。
next	prevと同じサイズかつ同じ型の2番目の入力画像。
flow	prevと同じサイズで型がCV_32FC2の計算されたフロー画像。
pyrScale	各画像のピラミッドを構築するための画像スケール(<1)を指定する引数。pyrScale=0.5 は古典的なピラミッドを意味し、次の各層が前の層の半分の大きさになる。
levels	初期画像を含むピラミッド層の数。levels=1 は追加の層が作成されず元の画像のみが使用されることを意味する。
winsize	平均化ウィンドウのサイズ。大きい値はアルゴリズムの画像ノイズに対するロバスト性を高め、速い動きを検出しやすくするが、より平滑化された動きフィールドになる。
iterations	各ピラミッド層でアルゴリズムが行う反復回数。
polyN	各ピクセルで多項式展開を求めるために使用するピクセル近傍のサイズ。大きい値は画像がより滑らかな曲面で近似されることを意味し、よりロバストなアルゴリズムとより平滑化された動きフィールドが得られる。通常 polyN=5 または 7 とする。
polySigma	多項式展開の基礎として使用する微分を平滑化するためのガウシアンの標準偏差。polyN=5 の場合は polySigma=1.1 に、polyN=7 の場合は polySigma=1.5 が適切な値となる。
flags	以下の組み合わせが可能な操作フラグ: cv.OPTFLOW_USE_INITIAL_FLOW は入力フローを初期フロー近似として使用する。 cv.OPTFLOW_FARNEBACK_GAUSSIAN はオプティカルフロー推定に、同じサイズのボックスフィルタの代わりにガウシアン 𝚠𝚒𝚗𝚜𝚒𝚣𝚎×𝚠𝚒𝚗𝚜𝚒𝚣𝚎 フィルタを使用する。通常このオプションは、ボックスフィルタよりも正確なフローを得られるが、速度は低下する。同程度のロバスト性を得るには、ガウシアンウィンドウの winsize を通常より大きな値に設定する必要がある。