前提

タスク概要

Optical Flowでは「2枚の画像」を入力し、「1枚目(source)から2枚目(target)にかけてどのように画像が動いたか」をベクトル形式で出力します。

よく用いられるデータセット

Optical Flowの評価や学習にあたってはSintel・KITTI・FlyingChairなどがよく用いられます。

Sintel(RAFT GitHubに基づいて作成)

Flying Chairs(FlowNet論文より)

上記の図では出力されたベクトルの大きさを計算し、カラーマップが作成されていることに注意が必要です。特に論文ではベクトル形式ではなく、カラーマップでの出力が記載されることが多いので抑えておく必要があります。

また、Optical Flowのデータセットの構築にあたっては一般的な画像などのタスクなどのように人がアノテーションを作成するのは難しいことも抑えておくと良いです。どのピクセルがどのピクセルに動いたのかを1つ1つ確認するのはあまり現実的な作業ではありません。Optical Flowのデータセットの作成にあたっては、3D演算をレンダリングするのと同様な手法を用いて生成が行われます。たとえばSintelはBrenderを用いて作成された3Dアニメーションを活用することで構築されるデータセットです。同様にFlowNetの研究過程で構築されたデータセットであるFlying Chairsでは、3Dで表現された椅子を回転させレンダリングを行うことでデータセットの構築が行われます。このように、Optical Flowのデータセットの構築にあたっては3Dからレンダリングを元に構築されることが多いことに注意しておくと良いです。

評価指標

Optical Flowの評価にあたっては、EPE(End Point Error)という指標がよく用いられます。評価に用いるのと同様にDeepLearningにおける損失関数(loss function)の定義にあたってもEPEは用いられます。

EPEはGround Truthのベクトルと予測したベクトルの差の二乗和を計算した手法です。和を用いる場合はピクセルの数に比例して値が大きくなるので、二乗の平均を用いるaverage EPEがOptical Flowの評価にあたって一般的に用いられます。Ground Truthのベクトルを$V_{\mathrm{gt}} \in \mathbb{R}^{W \times H \times 2}$、予測結果のベクトルを$V_{\mathrm{pred}} \in \mathbb{R}^{W \times H \times 2}$とする場合に、average EPEの$\mathrm{EPE}_{\mathrm{average}}$は下記のように定義されます。

\mathrm{EPE}_{\mathrm{average}} = \frac{1}{2WH} \sum_{i=1}^{W} \sum_{j=1}^{H} \sum_{d=1}^{2} ||V_{\mathrm{gt}}(i,j,d) - V_{\mathrm{pred}}(i,j,d)||^{2}

疎なOptical Flowと密なOptical Flow

Optical Flowのアルゴリズムには計算量の兼ね合いから疎なOptical Flowと密なOptical Flowの2つに分類されます。この2つの分類は各アルゴリズムの計算量と大きく関連します。

Optical Flowのアルゴリズムは基本的に「Sourceのピクセルがどこに動いたのか」を計算するものであるので、「どのSourceの位置を選択するか」によって計算量が大きく変わります。疎なOptical Flowは予め点を決めてその点がどこに動いたのかを計算するのに対し、密なOptical Flowは全ての点についてどこに動いたのかを計算します。

Lucas-Kanadeは疎、Farneback・DISやDeepLearningを用いる手法は密なOptical Flowが実現されます。特にDeepLearningを用いる手法は全体を見た際にU-Netのような構成になる場合が多く、基本的にend-to-endで処理が行われるので密なOptical Flowになることが多いです。

Optical Flowのアルゴリズムの構築にあたっての基本的な考え方

大枠

Optical Flowのアルゴリズムの構築にあたっては、「制約式に基づいた最適化を行うDeepLearning以前の手法」と、「DeepLearningを用いた手法」の2つに大別されます。「DeepLearningを用いた手法」も「相関を用いる手法」と「相関を用いない手法」の2つに分けられます。

Brightness Constancy

DeepLearning以前の手法における制約については「Sourceのピクセルの画素値がTargetにおける移動先の画素値と一致する(Brightness Constancy)」というのが基本になります。この制約に加えて「近傍のパッチが同じように動く(Constant Flow)」という制約を用いることで導出されるLucas-Kanade法と、「出力されるベクトルは$x$方向$y$方向ともに滑らかに変化する(Smooth Flow)」という制約を用いることで導出されるHorn-Schunk法などがOptical Flowの基本アルゴリズムです。共通して用いられるBrightness Constancyは下記のような式で表されます。

I_{x} u + I_{y} v + I_{t} = 0 \quad (1)

上記の$I_{x}, I_{y}, I_{t}$はそれぞれ$x$方向、$y$方向、$t$方向の画素の変化であり、どれも入力される2枚の画像から計算を行うことが可能です。ここで$u, v$が未知数であり式が1つだけでは解くことができないので、さらに制約を加えることでそれぞれのアルゴリズムの導出を行います。また、$(1)$式はBrightness Constancyの式である$I(x + dx, y + dy, t + dt) = I(x, y, t)$より、下記のように導出されることもあわせて抑えておくと良いです。

\begin{align}
I(x + dx, y + dy, t + dt) &= I(x, y, t) \\
\cancel{I(x, y, t)} + \frac{\partial I}{\partial x} dx + \frac{\partial I}{\partial y} dy + \frac{\partial I}{\partial t} dt &= \cancel{I(x, y, t)} \\
\frac{\partial I}{\partial x} dx + \frac{\partial I}{\partial y} dy + \frac{\partial I}{\partial t} dt &= 0 \\
\frac{\partial I}{\partial x} \frac{dx}{dt} + \frac{\partial I}{\partial y} \frac{dy}{dt} + \frac{\partial I}{\partial t} \frac{\cancel{dt}}{\cancel{dt}} &= 0 \\
I_{x} u + I_{y} v + I_{t} = 0 \quad (1)
\end{align}

ここで上記の$(1)$式が1次のテイラー展開に基づいて導出されていることに着目しておくと良いです。下記に基づいて1次のテイラー展開に基づく方程式の解に基づいてニュートン法のUpdateが行えることを合わせて抑えておくとLucas-Kanade法における漸化式の導出を行うことができます。

Multi-Scale＆Refinement

Optical Flowの計算アルゴリズムではパフォーマンスの向上にあたって、Multi-ScaleやRefinementという考え方がよく用いられます。まずMulti-Scaleは大きな変化と小さな変化の双方を取り扱うにあたって用いられる考え方であり、疎から密(coarse-to-fine)の順に計算を行うことで効率的に計算が行われます。

疎な画像の作成にあたっては従来的には分散の大きなガウシアンフィルタを用いることで画像をぼかすなどが行われていた一方で、近年ではCNNにおけるプーリング処理のようにダウンサンプリングを行うというのが主流です。

また、Refinementは繰り返し演算によって予測結果を少しずつ調整するという手法です。DIS(Dense Inverse Search)ではHorn-Schunk法などに基づいてVariational Refinementが実行されます。DeepLearningベースでSotAを実現したRAFTではRefinementにRNNが用いられます。

研究トレンド

基本アルゴリズム

Lucas-Kanade法やHorn-Schunck法についてはCMU講義資料がわかりやすいので、当項では以下この資料を参考にまとめます。

Lucas-Kanade(基本的な式の導出)

Lucas-Kanade法では「Sourceのピクセルの画素値がTargetにおける移動先の画素値と一致する(Brightness Constancy)」と「近傍のパッチが同じように動く(Constant Flow)」の2つを元にアルゴリズムが導出されます。

Lucas-Kanade法では$5 \times 5$のパッチが同時に動くという仮定をおくのが一般的です。$5 \times 5$のパッチのそれぞれのインデックスの$i, j \in \{1, 2, 3, 4, 5 \}$を用いてそれぞれのパッチのピクセルを$p_{i,j}$とおくとき、$(1)$式は下記のように書き直すことができます。

I_{x}(p_{i,j}) u + I_{y}(p_{i,j}) v + I_{t}(p_{i,j}) = 0 \quad (2)

$(2)$式は$i, j \in \{1, 2, 3, 4, 5 \}$について成立することより、下記のような連立方程式が得られます。

\begin{align}
I_{x}(p_{1,1}) u + I_{y}(p_{1,1}) v &= - I_{t}(p_{1,1}) \\
I_{x}(p_{1,2}) u + I_{y}(p_{1,2}) v &= - I_{t}(p_{1,2}) \\
  & \vdots \\
I_{x}(p_{5,3}) u + I_{y}(p_{5,3}) v &= - I_{t}(p_{5,3}) \\
I_{x}(p_{5,4}) u + I_{y}(p_{5,4}) v &= - I_{t}(p_{5,4}) \\
I_{x}(p_{5,5}) u + I_{y}(p_{5,5}) v &= - I_{t}(p_{5,5})
\end{align}

上記の連立方程式は下記のように行列で表すことも可能です。

\begin{align}
\left( \begin{array}{cc} I_{x}(p_{1,1}) & I_{y}(p_{1,1}) \\ I_{x}(p_{1,2}) & I_{y}(p_{1,2}) \\ \vdots & \vdots \\ I_{x}(p_{5,3}) & I_{y}(p_{5,3}) \\ I_{x}(p_{5,4}) & I_{y}(p_{5,4}) \\ I_{x}(p_{5,5}) & I_{y}(p_{5,5}) \end{array} \right) \left( \begin{array}{c} u \\ v \end{array} \right) &= -\left( \begin{array}{c} I_{t}(p_{1,1}) \\ I_{t}(p_{1,2}) \\ \vdots \\ I_{t}(p_{5,3}) \\ I_{t}(p_{5,4}) \\ I_{t}(p_{5,5}) \end{array} \right) \\
A \mathbf{x} &= -\mathbf{b} \quad (3) \\
A \in \mathbb{R}^{25 \times 2}, \, & \mathbf{x} \in \mathbb{R}^{2 \times 1}, \, \mathbf{b} \in \mathbb{R}^{25 \times 1}
\end{align}

上記の$(3)$式に下記のような変形を行うことで、Optical Flowの出力に対応する未知数の$u, v$の計算が可能です。

\begin{align}
A \mathbf{x} &= -\mathbf{b} \quad (3) \\
A^{\mathrm{T}} A \mathbf{x} &= - A^{\mathrm{T}} \mathbf{b} \\
\mathbf{x} &= - (A^{\mathrm{T}} A)^{-1} A^{\mathrm{T}} \mathbf{b}
\end{align}

上記に出てくる$A^{\mathrm{T}} A$は下記のように表すことができることも抑えておくと良いです。

A^{\mathrm{T}} A = \left( \begin{array}{cc} \displaystyle \sum_{i=1}^{5}\sum_{j=1}^{5} I_{x}(p_{i,j})^{2} & \displaystyle \sum_{i=1}^{5}\sum_{j=1}^{5} I_{x}(p_{i,j})I_{y}(p_{i,j}) \\ \displaystyle \sum_{i=1}^{5}\sum_{j=1}^{5} I_{y}(p_{i,j})I_{x}(p_{i,j}) & I_{y}(p_{i,j})^{2} \end{array} \right)

この計算は「出力ベクトルの次元の2乗$\times$パッチのサイズ」の計算量が必要になるかつLucas-Kanadeのループ処理の中で一番計算量の多い処理になります。よって、後述のDISではこの計算が1度で済むようにSourceではなくTargetを用いてこのヘッセ行列を計算し(Inverse)、Sourceを動かすRefinementを行うことで計算量の削減が試みられます。

Lucas-Kanade法(ニュートン法に基づくRefinement)

$(1)$～$(3)$式ではLucas-Kanade法の基本的な導出について取り扱いましたが、Lucas-Kanade法を実際に用いるにあたっては漸化式を用いてRefinementを行うことが一般的です。Lucas-Kanade法ではニュートン法に基づいてRefinementの漸化式を導出するので以下で式変形について確認します。

\begin{align}
I(x + u + \Delta u, y + v + \Delta v, t + 1) & \simeq I(x+u, y+v, t) + I_{x} \Delta u + I_{y} \Delta v + I_{t} \cdot 1 \\
  &= I(x+u, y+v, t) + I_{x} \Delta u + I_{y} \Delta v + I_{t}
\end{align}

上記は$I(x + u + \Delta u, y + v + \Delta v, t + 1)$の1次のテイラー展開です。上記より、Brightness Constancyの式は下記のように表すことができます。

\begin{align}
I(x + u + \Delta u, y + v + \Delta v, t + 1) &= I(x + u, y + v, t) \\
\cancel{I(x+u, y+v, t)} + I_{x} \Delta u + I_{y} \Delta v + I_{t} & \simeq \cancel{I(x + u, y + v, t)} \\
I_{x} \Delta u + I_{y} \Delta v + I_{t} & \simeq 0
\end{align}

上記の式は「Lucas-Kanade法(基本的な式の導出)」と同様に解くことができます。

\begin{align}
\left( \begin{array}{c} \Delta u \\ \Delta v \end{array} \right) &= - (A^{\mathrm{T}} A)^{-1} A^{\mathrm{T}} \mathbf{b} \\
A &= \left( \begin{array}{cc} I_{x}(p_{1,1}) & I_{y}(p_{1,1}) \\ I_{x}(p_{1,2}) & I_{y}(p_{1,2}) \\ \vdots & \vdots \\ I_{x}(p_{5,3}) & I_{y}(p_{5,3}) \\ I_{x}(p_{5,4}) & I_{y}(p_{5,4}) \\ I_{x}(p_{5,5}) & I_{y}(p_{5,5}) \end{array} \right), \quad \mathbf{b} = \left( \begin{array}{c} I_{t}(p_{1,1}) \\ I_{t}(p_{1,2}) \\ \vdots \\ I_{t}(p_{5,3}) \\ I_{t}(p_{5,4}) \\ I_{t}(p_{5,5}) \end{array} \right)
\end{align}

上記で取り扱ったように、方程式を1次のテイラー展開に基づいて解いた結果を元に、ニュートン法のUpdateの式を得ることができます。Lucas-Kanade法では下記のようなUpdateの式が得られます。

\begin{align}
\left( \begin{array}{c} \Delta u \\ \Delta v \end{array} \right) &= - (A^{\mathrm{T}} A)^{-1} A^{\mathrm{T}} \mathbf{b} \\
\left( \begin{array}{c} u_{n+1} \\ v_{n+1} \end{array} \right) &= \left( \begin{array}{c} u_{n} \\ v_{n} \end{array} \right) + \left( \begin{array}{c} \Delta u \\ \Delta v \end{array} \right)
\end{align}

上記のヘッセ行列$A^{\mathrm{T}} A$をSource画像について計算すると漸化式の各ステップ毎に計算が必要になるので、Lucas-Kanade法を用いるにあたってはTarget画像についてヘッセ行列を計算し各ステップで同じヘッセ行列を使うInverse Searchという手法が用いられることが多いです。Inverse SearchはDISでも採用されています。

Horn-Schunck法

Horn-Schunck法はBrightness Constancyに加えて「出力されるベクトルは$x$方向$y$方向ともに滑らかに変化する(Smooth Flow)」という制約を用いて導出を行う手法です。

\begin{align}
\hat{u}_{kl} &= \bar{u}_{kl} - \frac{I_{x}\bar{u}_{kl} + I_{x}\bar{v}_{kl} + I_{t}}{\lambda^{-1} + I_{x}^{2} + I_{y}^{2}} \\
\hat{v}_{kl} &= \bar{v}_{kl} - \frac{I_{x}\bar{u}_{kl} + I_{x}\bar{v}_{kl} + I_{t}}{\lambda^{-1} + I_{x}^{2} + I_{y}^{2}}
\end{align}

Horn-Schunck法は上記の式に基づく繰り返し演算を行うことで$u$と$v$の計算を行います。$\hat{u}$と$\bar{u}$を交互に計算しUpdateを行うのでDISに用いられるVariational Refinementと同様な計算を行うと解釈できると推測されます(要出展)。以下、Horn-Schunck法の導出を行います。

Horn-Schunck法では「Brightness Constancy」と「Smooth Flow」を同時に取り扱うにあたって、それぞれ下記のように$L_{b}$と$L_{s}$を定義します。

\begin{align}
L_{b} &= \sum_{i=1}^{W} \sum_{j=1}^{H} E_{b}(i,j) = \sum_{i=1}^{W} \sum_{j=1}^{H} [I_{x}(i,j) u_{ij} + I_{y}(i,j) v_{ij} + I_{t}(i,j)]^{2} \\
L_{s} &= \sum_{i=1}^{W} \sum_{j=1}^{H} E_{s}(i,j) \\
E_{s}(i,j) &= \frac{1}{4} \left[ (u_{ij}-u_{i+1,j})^{2} + (u_{ij}-u_{i,j+1})^{2} + (v_{ij}-v_{i+1,j})^{2} + (v_{ij}-v_{i,j+1})^{2} \right]
\end{align}

Horn-Schunck法では上記の$L_{b}$と$L_{s}$を元に目的関数$L$を下記のように定義します。

L = L_{s} + \lambda L_{b}

このとき、$\displaystyle \frac{\partial L}{\partial u_{kl}}$は下記のように計算できます。

\begin{align}
\frac{\partial L}{\partial u_{kl}} &= 2(u_{kl} - \bar{u}_{kl}) + 2 \lambda (I_{x} u_{kl} + I_{y} v_{kl} + I_{t}) I_{x} \\
\bar{u}_{kl} &= \frac{1}{4} \left[ u_{i+1,j} + u_{i-1,j} + u_{i,j+1} + u_{i,j-1} \right] \\
I_{x} &= I_{x}(k,l), \, I_{y} = I_{y}(k,l), \, I_{t} = I_{t}(k,l)
\end{align}

上記では表記の簡略化にあたって$I_{x} = I_{x}(k,l), , I_{y} = I_{y}(k,l), , I_{t} = I_{t}(k,l)$のように定義しました。同様に$\displaystyle \frac{\partial L}{\partial v_{kl}}$は下記のように計算できます。

\begin{align}
\frac{\partial L}{\partial v_{kl}} &= 2(v_{kl} - \bar{v}_{kl}) + 2 \lambda (I_{x} u_{kl} + I_{y} v_{kl} + I_{t}) I_{y} \\
\bar{v}_{kl} &= \frac{1}{4} \left[ v_{i+1,j} + v_{i-1,j} + v_{i,j+1} + v_{i,j-1} \right] \\
I_{x} &= I_{x}(k,l), \, I_{y} = I_{y}(k,l), \, I_{t} = I_{t}(k,l)
\end{align}

ここで$\displaystyle \frac{\partial L}{\partial u_{kl}}=0$のとき、下記のような方程式を得ることができます。

\begin{align}
\frac{\partial L}{\partial u_{kl}} &= 0 \\
2(u_{kl} - \bar{u}_{kl}) + 2 \lambda (I_{x} u_{kl} + I_{y} v_{kl} + I_{t}) I_{x} &= 0 \\
(1 + \lambda I_{x}^{2}) u_{kl} + \lambda I_{x} I_{y} v_{kl} &= \bar{u}_{kl} - \lambda I_{x} I_{t} \quad (4)
\end{align}

同様に$\displaystyle \frac{\partial L}{\partial v_{kl}}=0$より下記のような方程式が得られます。

\begin{align}
\frac{\partial L}{\partial u_{kl}} &= 0 \\
2(v_{kl} - \bar{v}_{kl}) + 2 \lambda (I_{x} u_{kl} + I_{y} v_{kl} + I_{t}) I_{y} &= 0 \\
\lambda I_{x} I_{y} u_{kl} + (1 + \lambda I_{y}^{2}) v_{kl} &= \bar{u}_{kl} - \lambda I_{y} I_{t} \quad (5)
\end{align}

$(4)$式、$(5)$式は下記のように行列とベクトルの積の形式で表すことができます。

\begin{align}
\left( \begin{array}{c} (1 + \lambda I_{x}^{2}) u_{kl} + \lambda I_{x} I_{y} v_{kl} \\ \lambda I_{x} I_{y} u_{kl} + (1 + \lambda I_{y}^{2}) v_{kl} \end{array} \right) &= \left( \begin{array}{c} \bar{u}_{kl} - \lambda I_{x} I_{t} \\ \bar{v}_{kl} - \lambda I_{y} I_{t} \end{array} \right) \\
\left( \begin{array}{cc} (1 + \lambda I_{x}^{2}) & \lambda I_{x} I_{y} \\ \lambda I_{x} I_{y} & (1 + \lambda I_{y}^{2}) \end{array} \right) \left( \begin{array}{c} u_{kl} \\ v_{kl} \end{array} \right) &= \left( \begin{array}{c} \bar{u}_{kl} - \lambda I_{x} I_{t} \\ \bar{v}_{kl} - \lambda I_{y} I_{t} \end{array} \right) \quad (6)
\end{align}

$2 \times 2$行列の逆行列の公式を用いることで$(6)$式は下記のように解くことができます。

\begin{align}
& \left( \begin{array}{cc} (1 + \lambda I_{x}^{2}) & \lambda I_{x} I_{y} \\ \lambda I_{x} I_{y} & (1 + \lambda I_{y}^{2}) \end{array} \right) \left( \begin{array}{c} u_{kl} \\ v_{kl} \end{array} \right) = \left( \begin{array}{c} \bar{u}_{kl} - \lambda I_{x} I_{t} \\ \bar{v}_{kl} - \lambda I_{y} I_{t} \end{array} \right) \quad (6) \\
\left( \begin{array}{c} u_{kl} \\ v_{kl} \end{array} \right) &= \left( \begin{array}{cc} (1 + \lambda I_{x}^{2}) & \lambda I_{x} I_{y} \\ \lambda I_{x} I_{y} & (1 + \lambda I_{y}^{2}) \end{array} \right)^{-1} \left( \begin{array}{c} \bar{u}_{kl} - \lambda I_{x} I_{t} \\ \bar{v}_{kl} - \lambda I_{y} I_{t} \end{array} \right) \\
  &= \frac{1}{1 + \lambda(I_{x}^{2}+I_{y}^{2})} \left( \begin{array}{cc} (1 + \lambda I_{y}^{2}) & -\lambda I_{x} I_{y} \\ -\lambda I_{x} I_{y} & (1 + \lambda I_{x}^{2}) \end{array} \right) \left( \begin{array}{c} \bar{u}_{kl} - \lambda I_{x} I_{t} \\ \bar{v}_{kl} - \lambda I_{y} I_{t} \end{array} \right) \\
  &= \frac{1}{1 + \lambda(I_{x}^{2}+I_{y}^{2})} \left( \begin{array}{c} (1 + \lambda I_{y}^{2})(\bar{u}_{kl} - \lambda I_{x} I_{t}) - \lambda I_{x} I_{y}(\bar{v}_{kl} - \lambda I_{y} I_{t}) \\ -\lambda I_{x} I_{y}(\bar{u}_{kl} - \lambda I_{x} I_{t}) + (1 + \lambda I_{x}^{2})(\bar{v}_{kl} - \lambda I_{y} I_{t}) \end{array} \right) \\
  &= \frac{1}{1 + \lambda(I_{x}^{2}+I_{y}^{2})} \left( \begin{array}{c} (1 + \lambda I_{y}^{2})\bar{u}_{kl} - \lambda I_{x} I_{y} \bar{v}_{kl} - \lambda I_{x} I_{t}) \\ - \lambda I_{x} I_{y} \bar{u}_{kl} + (1 + \lambda I_{x}^{2})\bar{v}_{kl} - \lambda I_{y} I_{t}) \end{array} \right) \\
  &= \left( \begin{array}{c} \bar{u}_{kl} \\ \bar{v}_{kl} \end{array} \right) + \frac{1}{1 + \lambda(I_{x}^{2}+I_{y}^{2})} \left( \begin{array}{c} -\lambda I_{x}^{2} \bar{u}_{kl} - \lambda I_{x} I_{y} \bar{v}_{kl} - \lambda I_{x} I_{t} \\ -\lambda I_{x} I_{y} \bar{u}_{kl} - \lambda I_{y}^{2} \bar{v}_{kl} - \lambda I_{y} I_{t} \end{array} \right) \\
  &= \left( \begin{array}{c} \bar{u}_{kl} \\ \bar{v}_{kl} \end{array} \right) - \frac{1}{1 + \lambda(I_{x}^{2}+I_{y}^{2})} \left( \begin{array}{c} (\lambda I_{x} \bar{u}_{kl} + \lambda I_{y} \bar{v}_{kl} + \lambda I_{t})I_{x} \\ (\lambda I_{x} \bar{u}_{kl} + \lambda I_{y} \bar{v}_{kl} + \lambda I_{t})I_{y} \end{array} \right) \\
  &= \left( \begin{array}{c} \bar{u}_{kl} \\ \bar{v}_{kl} \end{array} \right) - \frac{1}{\lambda^{-1} + I_{x}^{2} + I_{y}^{2}} \left( \begin{array}{c} (I_{x} \bar{u}_{kl} + I_{y} \bar{v}_{kl} + I_{t})I_{x} \\ (I_{x} \bar{u}_{kl} + I_{y} \bar{v}_{kl} + I_{t})I_{y} \end{array} \right) \quad (7)
\end{align}

$(7)$式がHorn-Schunck法におけるUpdateの式に対応します。

OpenCV

Farneback

Farnebackはテイラー展開(Polynomial Expansion)を用いることでシンプルにOptical Flowの推定を行うアルゴリズムです。

Farneback論文より

Farnebackは上記に基づいて導出される$\mathbf{d}$をOptical Flowのベクトルの推定結果とするアルゴリズムです。

Farnebackについて詳しくは下記で取り扱いました。

DIS

DIS(Dense Inverse Search)は密なOptical Flowを実現する手法で、OpenCVなどで採用されています。DISの特徴には下記の3点が挙げられます。

1. inverse search for patch correspondence
2. dense displacement field creation through patch aggregation along multiple scales
3. variational refinement

1.はLucas-Kanadeの計算量の改善にあたって用いられるInverse Search、2.はMulti-Scaleでの密なベクトル場の構築、3.はHorn-Schunk法を採用することによるEMアルゴリズム的な繰り返し演算(variational)によるrefinementにそれぞれ対応します。

DIS論文Figure.1

上図から確認できるように、DISではFarnebackと同じ計算スピードでより高いパフォーマンスが実現されています。DISについて詳しくは下記で取り扱いました。

DeepLearning

FlowNet

FlowNetは教師あり学習によって学習を行ったCNNを用いてOptical Flowの推論を行った手法です。FlowNet論文ではFlowNetS(FlowNetSimple)とFlowNetC(FlowNetCorr)の主に2種類のネットワーク構成が用いられており、それぞれ下図のような処理が行われます。

FlowNet論文 Figure.2

FlowNetSは二枚の画像を重ねて入力するオーソドックスなCNNであり、チャネル数が3である一般的なRGB画像を二枚重ねることでチャネル数が6となることを抑えておくと良いです。FlowNetCは2つの画像にCNNを適用することで得たFeatureMapに基づく相関を計算することで構築するネットワークです。

FlowNet論文 Table.2

FlowNet論文 Figure.6

FlowNet論文のSintelやKITTIでのパフォーマンス(EPE; EndPoint Error)は上記より確認できます。また、FlowNetではDeepLearningの学習に用いる大規模データセットであるFlying Chairsが合わせて作成されており、Flying Chairsは昨今の研究でも学習用のデータセットに用いられることが多いので抑えておくと良いです。

FlowNet論文 Table.1

FlowNet論文 Figure.5

FlowNet2.0

FlowNet2.0はFlowNetのカスタマイズによって他のState-of-the-Artの手法と同等のパフォーマンス(AEE; Average EndPoint Error)を実現した研究です。

FlowNet論文 Table.4

FlowNet2.0論文 Figure.2

RAFT

RAFT(Recurrent All-Pairs Field Transforms)は2020年時点でKITTIやSintelのSotAを達成したDeepLearningの手法です。RAFTの学習にはFlying Charisが用いられており、KITTIやSintelで高いパフォーマンスが実現されたことから汎用的に用いることができると概ね言えます。

RAFT論文Figure.1

RAFTのアルゴリズムは主に「Encoder」、「4D($W \times H \times W \times H$)の相関の計算」、「RNNを用いたRefinement」の3つの要素から構成されます。

RAFT論文Table.1

RAFTのパフォーマンスについては上記などを確認しておくと良いです。また、詳細の処理の流れについては著者実装について下記で詳しく確認を行いました。

FlowFormer

FlowFormerはTransformerを用いてOptical Flowの学習を行った研究です。

FlowFormer論文Figure.1

FlowFormerの大まかな処理の流れは上図のように表され、全体的にはRAFTと同様な処理が行われています。

FlowFormer論文Table.1

また、上記より、FlowFormerがRAFTのパフォーマンス(AEPE; Average End-Point-Error)を上回っていることが確認できます。

DDVM

DDVM(Denoising Diffusion Vision Model)はDiffusion Modelを用いてOptical Flowの学習を行った研究です。

DDVM論文Algorithm.1

DDVMの大まかな処理の流れは上記のAlgorithmを確認すると良いです。

DDVM論文Table.1

また、上記より、DDVMがRAFTのパフォーマンス(AEPE; Average End-Point-Error)を上回っていることが確認できます。