オプティカルフロー (Optical Flow) [動きモデルによるローカル手法 v.s. 変分法によるグローバル手法]

1 概要

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

動画中の,フレームtの参照画像$I(t)$と,次のフレームt+1の目標画像$I(t+1)$の,2枚の画像を入力に用いてオプティカルフローの推定は行われる.$I(t)$上の画素$(x,y)$が,$I(t+1)$上のどの座標に移ったかを示す動きベクトル $\mathit{\bf{w}}(x,y) = (u,v)$が形成するベクトル場$\mathit{\bf{w}}(x,y) : \Omega \rightarrow \mathcal{R}^{2}$が,2枚の画像間のオプティカルフローに相当する.

3次元空間における各画素が対応する点の動き(Motion) が,画像上に投影された2次元ベクトル群によって,オプティカルフローは構成されているとみなせる.オプティカルフローは,古くは動画圧縮や各種の画像復元問題などにも応用され,近年では動画認識全般において入力の特徴量画像にも使用される.また,人間が直感的にも理解しやすい「動きベクトル場」を抽出するので,エッジ検出などと同様に「プリミティブな画像特徴量を抽出する処理」であるとも言える.

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

オプティカルフローの研究での解法を大きく分類する際には,古典的には,以下の2種類の主要なアプローチに分類されてきた:

  1. ローカル手法 (3節):線形モーションモデルをローカルな領域(パッチ)の動きに対して当てはめて,局所最適化する.(Lukas Kanade 法 (1981) [1] の系統 ) (Wikipedia)
  2. グローバル手法 (4節):Variational Method (変分法) を用いて,グローバルに全画素の動きベクトルを正則化(=全体最適化)する.(Horn and Schunck (1981) [2] の系統) (Wikiepdia)

いずれの方法で推定する際も,輝度不変性(Brightness constancy) と呼ばれる「隣接フレーム間で,同一点(対応する画素同士)の移動前と移動後の輝度は等しい」という仮定を,データ項の制約として用いることが初期の手法で提案され,その後も使用された (2節).しかし,その(1980頃)当時の主流であった「1画素同士の輝度値比較」に基づく最適化を行うと,画素値をそのまま用いる初期手法はどれもあまりにナイーブな最適化にあり,外乱や照明変化や同一画素値の頻発などに弱かった.よってその後は,生の輝度値の代わりに,(ステレオや他の対応づけ問題と同じように) 注目画素の周辺領域のパッチ単位で計算したデータ項を用いたり,よりリッチな局所特徴記述子も用いるように発展していった.

1.2 この記事の構成

本記事では主に,[3]のサーベイに含まれている「2015年までのオプティカルフロー推定の研究」について,上記2分類に沿って,発展のきっかけを作った主要研究だけ,概要を取り上げていく.2015年ごろ以降には「PatchMatchなどの密な対応推定手法で求めた初期フローを,補間により周囲に伝播させる解法」も登場し,Deep Learningによる学習ベースの手法が盛んになるまでは少し流行したが ,この記事では対象外とする(Epic Flowなど).また,ステレオカメラで2フレーム分の4枚の画像から3Dフローを計算する「Scene Flow」の問題設定についても,この記事では取り上げない.

以降この記事の2節以降では,以下の順で,オプティカルフロー推定の概要を説明する:

  • 2節:Optical Flow の基本 : 古典的な輝度不変性の仮定を用いた推定方法.
  • 3節:ローカル手法 – 特徴点とモーションモデルによる方法.
  • 4節:グローバル手法 – 変分法による方法 (dual-TVL1など)

2 Optical Flow の基本 : 古典的な,輝度不変性の仮定を用いた推定方法.

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

Optical Flow のフレーム間での画素の変異
図1 フレーム間での画素の変位:Hはフレームtの画像で,Iはフレームt+1の画像を示す.

この2節で,「輝度不変(2.1)」と「開口問題(2.2)」の最低限の基本事項が抑えらた上で,実際のフロー推定手法を,その後のローカル手法(3節)と グローバル(4節)にてそれぞれ紹介したい.

2.1 輝度不変性

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

$$H(x,y) = I(x +u , y+v) \tag{1}$$

言い換えると,1フレーム間では短時間の移動なので,ある画素が移動前後で輝度値は変化しないという仮定である.次に,輝度値不変以外のもうひとつの拘束として,輝度不変が成立する動き(u,v)は小さめであるという仮定も置く.この仮定を用いると,(1)の右辺に対してテイラー展開を適用し,1次項のみで線型近似を行い以下の「線形版」にさし替えることができる:

$$ 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} \tag{2}$$

この式(2)を用いて,式(1)の輝度不変式を更に単純化した次の条件式をオプティカルフロー拘束 (Optical flow constraint) と呼ぶ:

$$u \frac {\partial I}{\partial x} + v \frac {\partial I}{\partial y} + \frac {\partial I}{\partial t} = 0 \tag{3}$$

ここで,フレーム間は短い間隔であるので,$\frac {\partial I}{\partial t} = I(x,y) – H(x,y) $ である

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

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

2.2 開口問題 (Aperture problem)

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

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

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

図2 開口問題の例.

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

3 ローカル手法:動きモデルの当てはめ

LukasとKanade [1] は,輝度不変/オプティカルフロー拘束で残る曖昧性を「$n \times n$の局所近傍(よく用いられるのはn=15)のブロック領域内では,オプティカルフローの移動ベクトル $(u,v)$の値が一定である」という局所領域内の動きは一定であるという仮定を用いた,オプティカルフローのローカル推定手法を提案された.これを業界では,Lucas-Kanade法と呼んできた.

Lucas-Kanade法では,以下のように,局所近傍$\mathcal{N}$の各画素の輝度不変性による誤差の自乗和をデータ項に用いたエネルギー関数を,最小二乗法で当てはめることにより,近傍$\mathcal{N}$ における移動ベクトル(u,v)の値を推定する:

$$E_{data}(u,v) = \sum_{ \bm{x} \in \mathcal{N}} (H(x,y) – I(x +u , y+v))^2 $$

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

オリジナルのLucas-Kanade法 [1]では,移動ベクトルの$\mathit{\bf{w}}$の2つのパラメータ$(u,v)$を各画素ごとにローカル領域で求める,「translation (平行移動)による変換」を仮定する設定となっている.しかし,translation は家庭として厳すぎる面もあり,N = 15 以下の小領域ごとの推定に限られてしまう柔軟性の無さがあった.そこで,その後は translation の代わりにより自由度を与える意味で「アフィン変換」が Lucas-Kanade 系の手法のモーションモデルとして用いられるようになっていった (例:CootesらのActive Appearance Modelなど).

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

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

4.1 平滑化項の導入による,エネルギー関数のグローバル化

既に2節で述べた通り,オプティカルフローはデータ項のみで解こうとすると,拘束条件に対して求めたい変数の方が多いので解けない.従って,画像2枚全体に対する逆問題としてオプティカルフローを(逆問題として)推定するには,なんらかの正則化が必要となる.

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

$$ E_{smooth}(u,v) = \int_{\Omega}(|\nabla u(\mathit{\bf{x}})|^2 + |\nabla v(\mathit{\bf{x}})|^2) d\Omega $$

輝度不変性によるデータ項$E_{data}(u,v)$と,上記の平滑性の仮定による正則化項$E_{smooth}(u,v)$を重み付けして足し合わせた,以下の画像ドメイン$\omega$に対するグローバルな目的関数であるエネルギー関数を,変分法(Variational Method)を用いてグローバルに最適化する手法を提案した:

$$ E_{global}(u,v) = E_{data}(u,v) + \lambda E_{smooth}(u,v)$$

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

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

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

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

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

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

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

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

以降,その2系統の改善について述べる.

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

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

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

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

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

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

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

5 まとめ

オプティカルフロー推定についてLuca-Kanade法の系統(ローカルなモーション当てはめ)と,Horn-Schunck法の系統 (グローバルな変分法) の2つに分類する形で,それぞれ大まかに主要な古典的手法を紹介した.

References

  • [1] 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.
  • [2] B. Horn, B. Schunck, Determining optical flow, Artificial Intelligence 17 (1–3) (1981) 185–203.
  • [3] Fortun, Denis, Patrick Bouthemy, and Charles Kervrann. “Optical flow modeling and computation: A survey.” Computer Vision and Image Understanding 134 (2015): 1-21.
  • [4] Wedel, Andreas, and Daniel Cremers. Stereo scene flow for 3D motion analysis. Springer; 2011 edition.
  • [5] 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).
  • [6] T. Brox, J. Malik, Large displacement optical flow: descriptor matching in variational motion estimation, IEEE Trans. PAMI (2011).
  • [7] Marco Alexander Treiber, “Optimization for Computer Vision – An Introduction to Core Concepts and Methods”, Springer, 2013.
  • [8] R Klette, CONCISE COMPUTER VISION: An Introduction Into Theory and Algorithms. Springer, 2019.
  • [9] デジタル画像処理 [改訂第二版], 画像情報教育振興協会, 2020.

外部参照リンク