1. オプティカルフロー (Optical Flow) とは [概要]

オプティカルフロー (Optical flow) とは，視覚(特にデジタル画像)上で，観測者と観測シーンの間で生じた「対象物体・表面・エッジ」などの動きが，画像に投影されることで観察できる，時間的に連続した2枚の画像フレーム間での各店の光学的な各点の動き(Motion)をさす．これを，計算機的に考えるコンピュータビジョンの場合は，動画中の２枚の時間的に隣接した画像フレーム間において，移動前の画素とその画素が移動した後の画素の「対応ペア間の移動ベクトル」が形成する「画像平面上の2次元動きベクトル場(field)」のことを，オプティカルフロー(場)と呼ぶ．

この記事では，古典的なオプティカルフロー推定の基本的な仮定と目的を，まず準備として紹介する (2節)．その準備を踏まえて，次の3,4節で，以下の初期の古典的な2系統について，概要を述べる：

1. [3節] ローカル窓最適化手法の Lucas-Kanade 法の系統
2. [4節] グローバル最適化手法の Horn-Schunck 法の系統

ディジタル画像処理 [改訂第二版] の中の解説など，Lucas-Kanade は昔から日本語の資料が多いので，2節は大枠のみ紹介して，代表手法の変遷のみ捉えられる構成にし，アルゴリズム詳細は省略してある．一方で，4節の Horn-Schunck 系手法の日本語解説は少ないので，力を入れてまとめた．とは言いながら，4節でも代表手法の変遷を示したのみであり，各最適化アルゴリズムの詳細までは触れないので，Referencesの各論文を参考にされたい．

動画中の，フレーム $t$ の 参照画像 $I(t)$ と，次のフレーム $t+1$ の目標画像 $I(t+1)$ の，2枚の画像を入力に用いて，オプティカルフロー(場)の推定は行われる．$I(t)$上の画素$(x,y)$が，$I(t+1)$上のどの座標に移ったかを示す動きベクトル $\mathbf{w}(x,y)=(u,v)$が形成するベクトル場$\mathbf{w}(x,y):\mathrm{\Omega }\to {\mathcal{R}}^2$が，2枚の画像間のオプティカルフロー(場)に相当する．この推定されたオプティカルフローは，3次元空間における各画素が対応する点の動き(Motion)が，画像上に投影された2次元動きベクトル群によって，構成されているとみなせる．

オプティカルフローは，古くは動画圧縮や各種の画像復元問題などにも応用された．近年では，Two-stream型ネットワークによる動画認識においては，入力の特徴量画像(RGB画像に加える第2のView)にも使用される．人間が直感的にも理解しやすい「動きベクトル場」を抽出するので，エッジ検出などと同様に「プリミティブな画像特徴量を抽出する処理」がオプティカルフロー推定であるとも言える．

1.1 Optical Flow 手法の２大分類: ローカル手法 v.s. グローバル手法

オプティカルフローの解法は，対応づけの推定時に，最適化を行う領域の大きさによって，以下の2種類に大別できる：

	最適化範囲	推定の手段	Wikipedia
Lukas-Kanade 法 (3節)	局所最適化	局所領域の動きを 線形モデルで推定．	Lucas–Kanade method
Horn-Schunck 法 (4節)	全体最適化	全画素のフロー(場)を 変分法で一挙に推定．	Horn–Schunck method

1981年当時は，もちろん機械学習は使用していない時期であるので，どちらも最適化問題として，画像空間上の「オプティカルフロー(全画素のベクトル場)」を推定する．

ディープラーニング登場後は，画像Encoder-Decoderに，画像全体のオプティカルフローへの変換を学習させて，「密な推定(Dense Prediction)問題」の1種として取組むことが標準的となった．ただ，この記事が最初にフォーカスする3節, 4節の「1980年頃」は，最適化として取組まれていた．

いずれの方法でも，輝度不変性 (Brightness constancy) と呼ばれる「隣接フレーム間で，同一点(対応する画素同士)の移動前と移動後の輝度は等しい」という仮定を，データ項の制約条件として用いることが提案され，その後も使用された (2節)．

しかし，1980年頃当時のオプティカルフロー向け誤差関数は，輝度値をそのまま用いていた誤差なのであまりナイーブであり，外乱や照明変化や同一画素値の頻発などに弱かった．よって，その後は，ステレオマッチングなど他の対応づけ問題と同じように，注目画素の周辺領域のパッチ単位で計算した統計値（テンプレートマッチングSSDなど）や，よりリッチな局所特徴記述子（SIFTやSURFなど）を，誤差関数のに用いる方向へ発展していった(※ この記事では対象外)．

1.2 記事の構成

2節以降では，以下の順で，オプティカルフロー推定の概要を説明する：

• 2節：オプティカルフローの基本 : 古典的な輝度不変性による推定．
• 3節：ローカル手法 (Lukas-Kanade 法) - 特徴点とモーションモデルによる方法．
• 4節：グローバル手法 (Horn-Schunck法) - 変分法による方法 (dual-TVL1など)

本記事では主に，[Fortun et al., 2015] (サーベイ)に含まれている「2015年までのオプティカルフロー推定の研究」について，3, 4 節で「代表手法の変遷」を把握できるような構成とした ．ディープラーニング登場後の今は使わないような，とても古い手法がほとんどなので，各手法は，詳細には触れないで概要のみ述べている．詳細にまで興味がある場合は，Referecesの各論文を見ていただきたい．

3,4節より後の時代の話として，2015年ごろ以降には『PatchMatch などの「密な対応推定手法」で求めた初期フローを，補間により周囲に伝播させる解法』も登場した．この路線は，Deep Learningをもちいたデータドリブンな手法が盛んになるまで少し流行したが ，これも対象外とする(例：Epic Flowなど)．

また，ステレオカメラで２フレーム分の4枚の画像から3Dフローを計算する「Scene Flow」の問題設定についても，この記事では取り上げない．

2. オプティカルフローの基本 : 輝度不変性による推定．

まず，フレームtの画像上では，座標$\mathbf{x}=(x,y)$の輝度値が$H(x,y)$であり，次のフレーム$t+1$の座標$\mathbf{x}=(x,y)$の輝度値が$I(x,y)$であるとする(図1)．そして，その座標$\mathbf{x}=(x,y)$が移動量$\mathbf{w}=(u,v)$で移動して，$t+1$ フレームの画像では座標 $(x+u,y+v)$ へと移動したものとする．

2節では「輝度不変(2.1節)」と「開口問題(2.2節)」という最低限の基本事項をまずおさえていく．その上で，実際の古典的なフロー推定手法を，ローカル手法(3節)と グローバル(4節)にてそれぞれ紹介したい．

2.1 輝度不変性

サブピクセル精度でオプティカルフローを推定する際には，輝度不変性拘束(brightness constancy constraintと呼ばれる，フローによって移動する前と後の画素値間で，輝度値は同じ値が保たれるという拘束条件を仮定する：

$$\begin{array}{}\text{(2.1)}& H(x,y)=I(x+u,y+v)\end{array}$$

式(2.1)は，言い換えると，「1フレーム間では短時間の移動なので，ある画素が移動前後で輝度値は変化しない」という仮定である．

次に，輝度値不変以外のもうひとつの拘束として，輝度不変が成立する動き(u,v)は小さめであるという仮定も置く．この仮定を用いると，式(2.1)の右辺に対してテイラー展開を適用して１次項のみで線型近似を行い，以下の「線形版」にさし替えることができる：

$$\begin{array}{}\text{(2.2)}& I(x+u,y+v)\approx I(x,y)+u\frac{\partial I}{\partial x}+v\frac{\partial I}{\partial y}+1\frac{\partial I}{\partial t}\end{array}$$

この式(2.2)を用いて，式(2.1)の輝度不変式を更に単純化した，次の条件式をオプティカルフロー拘束 (Optical Flow Constraint) と呼ぶ：

$$\begin{array}{}\text{(2.3)}& u\frac{\partial I}{\partial x}+v\frac{\partial I}{\partial y}+\frac{\partial I}{\partial t}=0\end{array}$$

ここで，フレーム間は短い間隔であると仮定しているため，$\frac{\partial I}{\partial t}=I(x,y)-H(x,y)$ が成立していると仮定する．

「輝度不変 [式(2.1)]」もしくは「オプティカルフロー拘束 [式(2.3)]」の，いずれを拘束として用いる場合も，推定対象の $\mathbf{w}=(u,v)$ では2変数推定する必要があるのに対し，拘束式が1つしか用意されてない状況なので，まだ不良設定問題である．従って，他の仮定を加えて拘束を増やすか，もしくはPrior項も加えて正則化しない限り，まだ解くことができない (※ このあと述べる「開口問題(2.2節)」の原因でもある）．

また，実環境下の画像・映像では「小さい動きのみ」と仮定したといえども，照明変化や反射など常に外乱はあるゆえ「(1画素だけに注目しての) 移動前後で輝度不変」という仮定は，なかなか常時は成立しづらい．ゆえに，より広い局所パッチ単位の画像特徴を元に，対応づけ/データ項の定義を行うことも多い．また，古典的な手法では，エッジ画像やカラー値もデータ項として採用する (データ項の種類については，この記事では触れないので，各参考文献を参照のこと)．

2.2 開口問題 (Aperture problem)

輝度不変性以外にも曖昧性の原因になるのが，開口問題 (Aperture problem) である．開口問題は，狭い限られた開口領域の画素のみしか観測できない際に発生する曖昧性問題である．

典型的には「エッジがどちらに動いたかについて，順方向と逆方向のどちらでも取れる曖昧性 (例: barbar pole illusion)」が例として挙げられる．２フレーム間で狭い領域だけ観測した際に，全画像を観測するとエッジの模様は左向きに動いているのに，観測している局所領域だけはエッジが右向きに写っていると，どちら向きが正しいか局所領域内の画像情報だけでは判定できなくなる．

図2は開口問題の一例の模式図である．縞模様のエッジが斜めに移る背景の手前に，青色矩形の物体が移動した様子が映った，２枚の隣り合うフレームの画像である．この図２の隣接２フレームの画像において，円形窓内を観測しただけでは，まるで上側にシフトしたように見えてしまい，対角線方向の右上方向に動いてる実際の青色矩形の動きを把握できないことになってしまう．

初期の，ローカル手法のオプティカルフロー (3節) では「5×5くらいの局所領域中では，$(u,v)$の値が全て一定である」という仮定を置くことで，開口問題による移動方向の曖昧性を解決することが多い．それが時代を経るにつれて，物体インスタンスを検出できるようになったり，密で高精度な局所マッチング技術なども発展したゆえ，それらの技術を用いて「より大きな領域同士のフレーム間対応」も推定して利用することにより，開口問題の不定性が解決しやすくなっていると言える．

3. ローカル手法：モーションモデルの当てはめ

LukasとKanade [Lukas and Kanade, 1981] は，輝度不変/オプティカルフロー拘束で残る曖昧性を局所領域内の動きは一定であるという仮定を拘束として用いて解決する「ローカル推定手法」が提案された．これをコンピュータビジョン周辺の業界では，Lucas-Kanade法と呼んできた．

Lucas-Kanade法では，局所的な近傍 $\mathcal{N}$ 画素では輝度不変性が成り立つことを利用して，フレーム1の各点 $(x,y)$ の移動ベクトル $(u,v)$ を推定する．つまり，$n\times n$ の局所近傍 (よく用いられるのは $n=15$ )のブロック領域内では，オプティカルフローの移動ベクトル $(u,v)$の値が一定であるとする．そして，フレーム間で，候補点が移動した前後の誤差の自乗和をデータ項に用いた，以下のエネルギー関数を，最小二乗法により当てはめることで， (近傍 $\mathcal{N}$ おける) 移動ベクトル $(u,v)$ の値を推定する：

$$\begin{array}{}\text{(3.1)}& E_{data}(u,v)=\sum _{\mathbf{x}\in \mathcal{N}}(H(x,y)-I(x+u,y+v){)}^2\end{array}$$

式(3.1)のように定めたエネルギー関数は，局所解も多くなりやすいことから，その後は，ニュートン法などの非線形の勾配降下法を用いたり，ガウシアンピラミッド画像を入力とすることなど，「なるべくグローバルな最適解を求める工夫」が順次試されていった．

3.1 「動きが局所的である仮定」の限界

オリジナルの Lucas-Kanade法 [Lucas and Kanade, 1981] では，移動ベクトルの$\mathbf{w}$の２つのパラメータ $(u,v)$ を，画素ごとにローカル領域で求める「平行移動による変換」を仮定した設定となっている．

しかし，この平行移動範囲を狭める仮定条件は，うまく成立する場合が少なく，仮定として厳しすぎる面もあるゆえ，領域幅・高さ $N$ が，$N\le 15$ の小領域ごとの推定でしか，この仮定がうまくはたらかないという，柔軟性の無さがあった．

3.2 アフィン変換をモーションモデルとした発展

そこで，その後は translation の代わりにより自由度を与える意味で「アフィン変換」が Lucas-Kanade 系手法のモーションモデルとして，よく用いられるようになっていった (例：CootesらのActive Appearance Model (Wikipedia)など)．

そうした中でLucas-Kanade法系の手法では，高速化改善である逆合成アルゴリズム(Inverse Compositional Algorithm) [Baker and Matthews 2001, 2004] が提案されたことをきっかけに，「顔のActive Appearance Modelのキーポイント追跡」など (非剛体的)な複数キーポイントの変化の「準リアルタイム位置合わせ問題」に利用されることが多くなり，オプティカルフロー推定ではあまり用いられなくなった．

このあたりの時期から，次の4節の「変分法ベースの手法」が，オプティカルフロー推定の主流となってゆく．

4. グローバル手法：変分法による最適化

4.1 平滑化項の導入と変分法推定

既に2節で述べた通り，オプティカルフローは，画素単位データ項のみの最適化で解こうとすると，拘束条件に対して求めたい変数の方が多いので解けない．従って，画像2枚全体に対する逆問題とするには，なんらかの形で「正則化」が必要となる．

そこで，HornとSchunckの手法 [Horn and Schunk, 1981] では，隣り合う画素の移動ベクトル同士が滑らかである平滑性 (Smoothness)の仮定として，以下の$L^2$ノルム正則化項を，エネルギー関数に導入した：

$$\begin{array}{}\text{(3.2)}& E_{smooth}(u,v)={\int }_{\mathrm{\Omega }}(|\mathrm{\nabla }u(\mathbf{x}){|}^2+|\mathrm{\nabla }v(\mathbf{x}){|}^2)d\mathrm{\Omega }\end{array}$$

輝度不変性によるデータ項$E_{data}(u,v)$に，上記の平滑性の拘束による正則化項$E_{smooth}(u,v)$を重み付けして足し合わせた，以下の画像ドメイン$\omega$に対する目的関数を変分法(Variational Method)を用いて全体最適化する手法を [Horn and Schunk, 1981] は提案した：

$$\begin{array}{}\text{(3.3)}& E_{global}(u,v)=E_{data}(u,v)+\lambda E_{smooth}(u,v)\end{array}$$

式(3.3)は，微分可能な$L^2$ノルムでデータ項・平滑化，共に定義されている．ゆえに，オイラー・ラグランジェ方程式 (Wikipedia)を用いて，解析的に線形に解を求めることができた．しかし，このあと4.2節で述べるように，このグローバルなエネルギー関数のデータ項と正則化項を，別のよりロバストな関数に差し替えて連続最適化で解こうとする際には，色々と工夫が必要となってくる．

以降4.2では，その「連続最適化による変分法を用いた手法」について紹介する．

4.2 変分法を用いた連続最適化による推定

Horn-Schunck 法は，データ項や正則化項に，もっとロバストな関数を導入すると推定の頑健性が上がる期待があり，当時の研究者の研究興味は，その点に集中し始めた．

一方で，変分最適化でフローを推定しようとすると，当時は以下のような課題があった

• エネルギー関数に微分不可能な項を導入するとトリッキーな解法が必要になる
• ロバストなノルムを微分可能な関数に近似し，(結局は)オイラー・ラグランジュ方程式を解くアプローチだと，近似エネルギー関数なせいで，真の解から少し遠くなってしまう．

そこで，微分できないノルムを用いても，効率よく最適化するための手法が研究されていったことで，照明変化や外れ値に強い「ロバストなオプティカルフロー推定手法」が登場することになる (4.2.1節)．

また，変分法に頼りすぎると「注目点の大きな移動」を推定しづらい弱点があったが，「特徴マッチング精度の向上」により，それらの疎な特徴マッチング結果も，変分法手法に取り込むことで，大きな移動も推定できる手法が提案され始めた．(4.2.2節)

以降，それら2系統の改善について順に述べる．

(1) ロバストなノルムの導入

もしデータ項に，外れ値にロバストな$L^1$ノルムを採用できたり，平滑項にエッジ保存性の高い全変動(total variation)を使用できると，変分最適化の推定結果がより安定したものになる．しかし，勾配降下法の中で，それらを採用したエネルギー関数をうまく取り扱える手法はなかなか出てこなかった．

そうした中，以前は最適化しづらかった「 Total-Variation正則化項」を導入したエネルギー関数に対しても，(Chambolle, Pockの) Primal-dualアルゴリズムにより効率的に解くことが可能な Dual-TV L1
[Brox and Malik, 2011] 法が登場した．これにより，ロバスト最適化のハードルが下がり，その$L^1-TV$の組み合わせを用いたオプティカルフロー推定手法が以後人気となった．

(2) 大きな変位への対応

変分法を用いるオプティカルフローは，(他のあらゆる大規模最適化問題同様であるが) 初期値から汎関数を探索するゆえ，小さい移動度のフローしか推定しかできない欠点があった (※ 画像ピラミッドである程度までなら対応可ではある)．動画のフレームレートが低い場合や，シーン中の物体や背景の(相対的)移動速度が大きい場合に生じる大きな変位 (Large displacements) にも対応できるようにしたい．

そこで [Brox and Malik, 2011] は「特徴記述子のマッチング」結果もエネルギー関数に取り入れることで，大きな変位にも対応できる手法を提案した．記述子マッチング項をエネルギー関数に加えることで，「大きな移動の動きベクトル」も考慮したフローを推定できるようになった．

その後，(Adobeの) PatchMatch [Barnes　et al., 2010]などの「密な対応の推定手法」や，上記の「特徴記述子による粗な対応」をフロー推定の際に積極的に使用する提案などが続いてゆく．ただ，冒頭の1節でも述べたように，この記事とある程度構成を対応づけしてあるサーベイ [Fortun et al., 2015] (2015)では，特徴マッチングも用いる手法の初期くらいまでしか紹介されていないこともあって，この記事ではそういった「その後の展開は」割愛したい．

5. まとめ

オプティカルフロー推定について，2節でまず基本的な事項を抑えた．

その後，3,4節では古典的手法を， Luca-Kanade法の系統(ローカルなモーション当てはめ: 3節)と，Horn-Schunck法の系統 (グローバルな変分法: 4節) の2種類に大別し，それぞれの主要な手法を大まかに紹介した．

参考書籍

• ディジタル画像処理 [改訂第二版], ディジタル画像処理編集委員会, 2020.
• Concise Computer Vision: An Introduction into Theory and Algorithms (Undergraduate Topics in Computer Science) , Reinhard Klette, 2014.

References

• [Barnes　et al., 2010] Barnes, C., Shechtman, E., Goldman, D.B. and Finkelstein, A., 2010. The generalized patchmatch correspondence algorithm. In Computer Vision–ECCV 2010: 11th European Conference on Computer Vision, Heraklion, Crete, Greece, September 5-11, 2010, Proceedings, Part III 11 (pp. 29-43). Springer Berlin Heidelberg.
• [Brox and Malik, 2011] T. Brox, J. Malik, Large displacement optical flow: descriptor matching in variational motion estimation, IEEE Trans. PAMI (2011).
• [Fortun et al., 2015] Denis Fortun, Patrick Bouthemy, and Charles Kervrann. "Optical flow modeling and computation: A survey." Computer Vision and Image Understanding 134 (2015): 1-21.
• [Horn and Schunck 1981] B. Horn, B. Schunck, Determining optical flow, Artificial Intelligence 17 (1–3) (1981) 185–203.
• [Lucas and Kanade 1981] B. Lucas, T. Kanade, An iterative image registration technique with an application to stereo vision, in: International Joint Conference on Artificial Intelligence, 1981, pp. 674–679.
• [Wedela and Cremers, 2011] Andreas Wedel , and Daniel Cremers. Stereo scene flow for 3D motion analysis. Springer; 2011 edition.
• [Zach et al., 2007] Zach, C., Pock, T., and Bischof, H., “A Duality Based Approach for Realtime TV-L 1 Optical Flow,” Pattern Recognition 1(1), 214–223 (2007).

外部参照リンク

• Optical flow - wikipedia
• Lucas-Kanade method - wikipedia
• Horn-Schunck method - wikipedia
• OpenCV-Python チュートリアル | オプティカルフロー(Optical Flow)