Oriented Difference of Gaussians (ODOG)という視覚モデル[1]を用いた画像のフィルタリングをフーリエ変換を用いて高速化する方法を考えてみる． ODOGは，明度知覚に関する様々な効果をうまく説明できるモデルとして知られていて， ODOGモデルは1枚の画像が与えっれたとき，人間が知覚する明度が画素値になった1枚の画像に変換する．この変換の一部は畳み込み演算になっているので，高速フーリ変換アルゴリズムを使うと単純に畳み込み演算で計算するよりも，画像やODOGフィルタのカーネルを一旦フーリ変換し，結果を逆フーリエ変換して元に戻す方がむしろ高速になる．

ODOGって

まず，ODOGがどういう数式モデルなのかを説明しないと，話が始まらない．簡単に言うと，このODOGは，DoG^[2]という異なるサイズのガウス関数の差で，二次微分のような効果があるフィルタの二次元版のフィルタがベースになっている．二次元版のDoGは，方向に依存したフィルタになっていて，様々なスケールと方向のDoGを，元の画像にかけて，ある重みで足し合わせたものになる．

具体的には，入力画像$p(x_1,x_2)$に対して，ある方向$\alpha=k\pi/3$ $(k=0,\cdots,5)$，あるスケール$\sigma_1=3.0(1/2)^{l}$ $(l=0,\cdots,7)$のDoGカーネル$f_{k,l}(x_1, x_2)$を畳み込んだものが$q_{k,l}(x_1, x_2)$だとすると， ODOGの出力$R(x_1,x_2)$は次の式で定義される．

\begin{array}{r} R (x_{1}, x_{2}) = \frac{1}{6} \sum_{k = 0}^{5} \frac{Q_{k} (x_{1}, x_{2})}{| | Q_{k} (x_{1}, x_{2}) | |_{2}} \end{array}

\begin{array}{r} Q_{k} (x_{1}, x_{2}) = \sum_{l = 0}^{6} w_{l} \cdot q_{k, l} (x_{1}, x_{2}) \end{array}

\begin{array}{r} w_{l} = (8 / 3 σ_{1})^{- \frac{1}{10}} \end{array}

\begin{array}{r} q_{k, l} (x_{1}, x_{2}) = f_{k, l} (x_{1}, x_{2}) * p (x_{1}, x_{2}) \end{array}

ただし，$||\cdot||_2$は，$L^2$ノルムであり，次のように定義される．

\begin{array}{r} {(| | Q_{k} (x_{1}, x_{2}) | |_{2})}^{2} = \int_{Ω} Q (x_{1}, x_{2})^{2} d x_{1} d x_{2} \end{array}

この式のもう少し詳しい説明は，論文[1]か[3]を参照して欲しい．

畳み込み演算をフーリエ変換で高速化する

上の式（ $???$ ）から（ $???$ ）の中でどの部分をフーリエ変換で高速化できるのか？フーリエ変換で畳み込み演算が掛け算になることを利用できるのは式（ $???$ ）．そこで，まず式（ $???$ ）をフーリエ変換する．

関数$f$のフーリエ変換を$\mathcal{F}[f]$と表すと，式（ $???$ ）両辺のフーリエ変換は次のようになる．

\begin{array}{r} F [q_{k, l}] = F [f_{k, l}] F [p] \end{array}

ODOGのカーネル$f$のフーリエ変換$\mathcal{F}[f_{k,l}]$は，「ODOGカーネルのフーリエ変換」で紹介しているように，予め解析的に計算することができる．

足し算を分解する

フーリエ変換は線形写像なので足し算の部分は分解でき，係数は前に出すことができる．具体的には，式（ $???$ ）の総和記号以下は足し算なので次のように計算できる．

\begin{array}{rcl} F [Q_{k}] & = & F [\sum_{l = 0}^{6} w_{l} \cdot q_{k, l}] \\ = & \sum_{l = 0}^{6} w_{l} \cdot F [q_{k, l}] \end{array}

ここで式（ $???$ ）を代入すると，変数$l$を含まない$\mathcal{F}[p]$は係数と同じように扱えるので総和記号の前に出すことができる．

\begin{array}{rcl} F [Q_{k}] & = & \sum_{l = 0}^{6} w_{l} \cdot F [f_{k, l}] F [p] \\ = & F [p] \sum_{l = 0}^{6} w_{l} \cdot F [f_{k, l}] \end{array}

この$\sum_{l=0}^6 w_l\cdot \mathcal{F}[f_{k,l}]$の部分は，$k$を定めると予め数値計算しておくことができる．変数$k$の値は0から7の8つのみなので，予め計算したものを配列として保存しておけば実行時計算する必要はない．

また，$\mathcal{F}[p]$については，$p(x_1,x_2)$が画像なので，この画像に対してフーリエ変換を一度計算すれば良い．

正則化項の計算を高速化する

$\mathcal{F}[Q]$の計算法は示したけど，正則化項$||Q_k(x_1, x_2)||_2$の計算をするには単純には一旦$\mathcal{F}[Q]$を逆フーリエ変換$\mathcal{F^{-1}}$して$Q$を求める必要がある．しかし，パーシバルの定理によるとフーリエ変換前後のエネルギーは（係数を除いて）保存されるので，実は逆フーリエ変換は必要ない．

\begin{array}{r} E_{k} = \int_{Ω} Q_{k} (x_{1}, x_{2})^{2} d x_{1} d x_{2} = \frac{1}{2 π} \int_{Ω} F [Q_{k}] (t_{1}, t_{2})^{2} d t_{1} d t_{2} \end{array}

再び足し算を分解する

式（ $???$ ）の両辺をフーリエ変換して，足し算部分を分解し，上で計算したものを代入する．

\begin{array}{r} F [R] = \frac{1}{6} \sum_{k = 0}^{5} \frac{F [Q_{k}]}{\sqrt{E_{k}}} \end{array}

高速化アルゴリズム

フーリエ変換を高速フーリエ変換（FFT）に変えると，一連の処理は次のようになる．

入力画像$f$に対してFFTすることにより$P=\mathcal{F}[p]$を計算する．
$F_k = \sum_{l=0}^6 w_l\cdot \mathcal{F}[f_{k,l}]$を計算して配列に蓄積する．
$\mathcal{F}[Q_k]$を計算する．
$\mathcal{F}[Q_k]$の全画素の自乗和により$E_k$を計算する．
$\mathcal{F}[R]$を計算する．
逆高速フーリエ変換により$R$を計算する．

参考文献

Barbara Blakeslee and Mark E. McCourt: "A multiscale spatial filtering account of the White effect, simultaneous brightness contrast and grating induction," Vision Research, vol. 39, issue 26, pp. 4361-4377, 1999.
doi: 10.1016/S0042-6989(99)00119-4
"Difference of Gaussians" in Wikipedia
https://en.wikipedia.org/wiki/Difference_of_Gaussians
Barbara Blakeslee, Davis Cope, and Mark E. McCourt1: "The Oriented Difference of Gaussians (ODOG) Model of Brightness Perception: Overview and Executable," Behavior Research Methods, pp. 306–312, vol. 48, no. 1, 2016.
doi: 10.3758/s13428-015-0573-4

武相荘

2018年8月19日日曜日

フーリエ変換によるODOGフィルタ計算の高速化