オプティカルフロー(Optical Flow)

0

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解法の分類: ローカル v.s. グローバル

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

  • 1ローカル手法(3節):線形モーションモデルをローカルな範囲(パッチ)の動きに対して当てはめる.(Lukas Kanade 法(1981)[1]の系統 )
  • 2 グローバル手法(4節):Variational Method(変分法)によりグローバルに正則化する.(Horn and Schunck (1981)[2]の系統)

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

1.2 この記事で取り上げる範囲

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

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

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

2 オプティカルフローの基本

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

図1 フレーム間での画素の変位

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

2.1 輝度不変性

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

$$H(x,y) = I(x +u , y+v) \tag{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項も加えて正則化しない限りは解けない(このあと述べる開口問題の原因でもある).

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

2.2 開口問題 (Aperture problem)

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

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

図2 開口問題の例.

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

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

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

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

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

$$E_{data}(u,v) = \sum_{ \mathit{\bf{x}} \in \mathcal{N}} (I(x,y,t) – I(x +u , y+v, t+1))^2 $$

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

オリジナルのLucas-Kanade法(1981)では,移動ベクトルの$\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の手法(1981)では,隣り合う画素の移動ベクトル同士が滑らかであるという平滑性(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$に対するグローバルな目的関数とし,変分法によりこの目的関数$E_{global}(u,v)$を最適化するオプティカルフロー推定法を提案した:

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

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

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

4.2 連続最適化による推定

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

一方で,変分最適化では,「エネルギー関数に微分不可能な項を導入するとトリッキーな解法が必要になる」面があったり,「ロバストなノルムを微分可能な関数に近似し(結局は)オイラー・ラグランジュ方程式を解くアプローチだと,近似エネルギー関数なので真の解から遠くなってしまう」,などの課題などがあった.そこで,微分できないノルムを用いても,効率よく最適化するための手法が研究されていき,照明変化や外れ値に強いオプティカルフロー推定手法が登場することになる.(4.2.1)

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

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

4.2.1 ロバストなノルムの導入

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

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

4.2.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.

外部リンク

0