KAZE理論を読んでみた #C++

　卒業論文でOpenCVに実装されたA-KAZEを使っていますが、実際の理論が書かれた資料は作者様が発表したKAZEについての論文しかなかったので、読んで和訳してみました。
多分盛大に間違っていると思うので間違っているところはぜひ指摘してくださいm(__)m

最初に

今回読んだ論文はこちら。
読んだ範囲は３章（非線形拡散フィルタリング）と４章（実装理論）だけ。５章（結果と比較）も早いうちに読みきりたい。

３章　”非線形拡散フィルタリング”

偏微分方程式

まず、非線形空間における（明るさの）拡散を表す偏微分方程式は一般的に下式１で示される。

\frac{\partial L}{\partial t} = div(c(x,y,z) \cdot \nabla L)

このうち関数ｃはconductivity functionの頭文字で、対象画像の構造に上式を対応させるための関数らしい。Lは明るさ（luminance)のLかな？
関数cはスカラーでもベクトルでもよいが対象画像の微分構造に依存する。AKAZEではそれぞれのスケールレベルで勾配の大きさが拡散をコントロールしている領域に着目して関数ｃを定義している。

同じ着眼点を持っていた先行論文の中にPerona氏とMalik氏の論文¹がある
この論文は画像のエッジ部分の拡散を低減するような関数cを提案している。（下式）

c(x,y,t)=g(|\nabla L_\sigma (x,y,t)|) \\
g_1 =exp(- \frac{|\nabla L_\sigma |^2}{k^2}) \\
g_2 =\frac{1}{1+\frac{|\nabla L_\sigma |^2}{k^2} }

kは拡散レベルを制御するコントラストパラメータで任意の数に設定できる。
$g_1$はハイコントラストのエッジを促進し、$g_2$は小さい範囲に基づいて広域を進める(和訳できないorz)。しかし、選択的な平滑化としては広域ぼかし(interregional blurring)よりも広域平滑化(interregional smoothing)のほうが好ましい。なので、筆者らは以下の関数$g_3$を提案している。

g_3=\begin{cases}
1 & |\nabla_\sigma|^2=0 & \\
1-exp(-\frac{3.315}{(|\nabla L_\sigma|/k)^8)} &  |\nabla_\sigma|^2 \neq0
\end{cases}

コントラストパラメータkは任意に設定できるが画像の評価の平均から自動的に算出することもできる。
各エッジはkによって強調されたり消されたりする。論文５ページのFig.1からはコントラストパラメータkの数値が大きくなるほど弱いエッジが減っているのがわかる。
一般的に、コントラストパラメータkが大きくなるほど、大きな勾配を持つ部分が残される。

AOS手法

AOS手法とは微分方程式を差分の形式で表し離散的にすることでPCで計算できるようにする手法である。
偏微分方程式を離散化する手法として陰的手法と半陰的手法がある。Wickert氏らによる論文²にはベクトル行列で表記された方程式の離散化手法が示されている（下式3）。

\frac{L^{i+1}-L^i}{\tau}=\sum^{m}_{l=1}A_l (L^i)L^{i+1},

$A_l$は各次元のための画像伝導率(image conductivities)を行列で表している。
この内、$L^{i+1}$は次のように表すことができる。

L^{i+1}=\Big(I-\tau \sum^{m}_{l=1}A_l (L^i)\Big)^{-1}L^i.

これを解くためには線形方程式が条件として必要だがガウスの消去法によって高速に解くことができる。

4章 ”KAZE特徴点"

この章では実際にKAZE特徴点を抽出するdescriptorがどのように導かれるかが書かれている。順に流れを追っていくことにする。

非線形スケールスペースの計算

対数的段階での離散化スケールスペースはオクターブOとサブレベルSの連続で整理されている。
オクターブOとサブレベルSはスケールσと下式のように対応している。

\sigma_i(o,s)=\sigma_0 2^\frac{o+s}{S}  \\
o \in[0 \cdots O-1] \\
s \in[0 \cdots S-1] \\
i \in[0 \cdots N]

ここで$\sigma_0$はベーススケールレベルを表し、Nは処理された画像枚数を表す。
上式はピクセル単位で表現されているが、3章の拡散フィルタは時間軸で定義されているため、以下の式を利用して時間軸へ変換する。

t_i = \frac{1}{2}\sigma_{i}^{2},\ (i=0,1,\cdots,N)

一般的には非線形スケールスペースにおいておのおののフィルタ画像と$t_i$は一致しないがKAZEではガウス空間で拡散関数gを1と等しくすることで一致させることができる。

実際のフローとしては入力画像に対して次の処理を行う。

標準偏差$\sigma_0$のガウス関数で畳み込みを行う。
元画像のヒストグラムからコントラストパラメータkと進化時間$t_i$を見積もる
AOSを利用して非線形空間を形成する。

こうして得られた非線形スケールスペースとガウシアンスケールスペースを比較するとガウシアンフィルタに比べて強いエッジが強力なエッジが変化しないで残っていることがわかる。(論文Fig.2)

特徴点検出

特徴点を見つけるためには複数のスケールレベルにおいてヘッセ行列にある特定の点がその空間を標準化した際に見せる反応を抽出する。
下式は標準化する際に用いる微分演算子である。

L_{Hessian}=\sigma^2(L_{xx}L_{yy}-L^2_{xy})

異なるスケールレベルでの反応を解析するために、その空間の最大値とその位置を探索する。(使われている高速化・簡略化手法は省略)最終的に、特徴点の位置は、Brown,M氏の論文³で提案された方法を使用してサブピクセルレベルで推測することができる。
一次と二次の導関数の組は異なる導関数の3×3のスクエアフィルタに近似できる。また、二次導関数は連続したスクエアフィルタを用いて近似できる。こうして得られたフィルタはSobel filterをはじめとしたほかのフィルタよりも回転に対して強いが、すべてのピクセルにおいてマルチスケールの導関数を計算しなければならない。しかし、検出時に同じ導関数の組を再利用することで計算量を抑えることができる。

特徴量記述

　descriptorを構築するために特徴点ごとに方向(Dominant Orientation)を見積もる必要がある。これは、各特徴点ごとに半径$\sigma_i$ごとに$6\sigma_i$までの範囲を探索することで発見します。各特徴点の一次導関数$L_x$と$L_y$は特徴点のガウス関数によって重み付けされます。このときの導関数の反応がベクトル空間内の点として記され、特徴点の方向は$\pi/3$の角度をカバーしている円形範囲にある反応の総和によって発見される。
　descriptorは、M-SURFの記述子に非線形空間用のフレームワークを追加して構築する。特徴量をスケール$\sigma_i$で記述するために、大きさ$\sigma_i$の一次導関数$L_x$と$L_y$は$24\sigma_i \times 24\sigma_i$の正方形のグリッドの上で計算される。このグリッドはさらに$4\times4$の副領域に分割されている($2\sigma_i$のオーバーラップがあるが)。各副領域での導関数の反応は副領域の中心で計算されたガウス関数($\sigma_1=2.5\sigma_i$)によって重み付けされ、descriptorベクトル$d_v=(\sum L_x, \sum L_y, \sum|L_x|, \sum|L_y|)$に合算される。そして、副領域のdescriptorベクトルは特徴点を中心としたガウス関数($\sigma_2 =1.5\sigma_i$)によって重み付けされる。特徴点の方向を検討するとき、各領域のサンプルもその方向に基づいて回転する。最終的に長さ64のdescriptorベクトルは単位ベクトルの中でコントラストに左右されずに一般化される。

つまり・・・？

KAZE特徴量は細かく分割された非線形空間にある特徴点の導関数を求め、それを重み付けしたうえでまとめてベクトル化する。そうして作ったベクトルを童謡の手順でまとめて標準化することで表現されるのかな？
そして、表現された特徴量はほかの特徴量と比べて回転に対して強い不変性をもつことがメリットとしてあげられるということかな。
こんなとこでどうでしょうか

参考文献(原文まま）

Prona,P. Malik,J: Scale-space and edge detection using annisotropic diffusion IEEE Trans. Pattern Anal. Machine Intell. 12(1990) 1651-1686 ↩
Weickert,J. ter Haar Romeny,B. Viergever,M.A.: Efficient and reliable schemes for non-linear diffusion filtering. IEEE Trans. Image Processing 7(1998) ↩
Brown,M. Lowe,D.: Invariant features from interest point groups. In: British Machine Vision Conf.(BMVC), Cardiff, UK(2002) ↩

KAZE理論を読んでみた

最初に

３章 ”非線形拡散フィルタリング”