Boy Meets ML

機械工出身者が機械学習やその界隈の知識を考える

トップ > SfM > SfMについて #3.5：KAZE

SfMについて #3.5：KAZE

SfM features 特徴量 特徴点 KAZE

はじめに

前回の記事の続きです。が、一部追加執筆中となっていますのでご了承ください。

mlengineer.hatenablog.com mlengineer.hatenablog.com

引き続きOpenSfMの精度向上方法を考えていく上で、特徴量抽出手法のうちKAZE、AKAZEという手法についても知る必要があると感じましたので、まずはKAZEの論文1を読んでまとめることにしました。 SfMから若干脱線するので3.5回目ということにします。 （AKAZEは4.5回目になるかも？）

特徴量抽出とはなんぞや？

ある物体aが写っている画像Aと、同一の物体aを異なる位置から撮影した画像A'があったとします。 この物体aは画像Aであろうが画像A'であろうが同じ物体aが写っていることには変わりはありません。 しかし、どうやればコンピュータにこれを教えることができるのでしょうか？

それは物体aの特徴を的確に教えてあげることで実現できそうです。 つまり物体aの特徴とは何なのか？という哲学にも通じそうな問題設定になります。

画像上で物体の特徴を決める上では、従来から2段階の方法をとることが多いです。 これは前回記事でも紹介したとおり以下のような流れで、1段階目を特徴点抽出(Detector)、2段階目(Descriptor)を特徴量記述といいます。 この2段階をまとめて特徴量抽出(Feature Extraction)と呼びます。

Flow of Feature Extraction
Flow of Feature Extraction

なぜ2段階も必要になるのかというと、それぞれの役割を考えると簡単です。 人の視覚・認知能力と違い、コンピュータが画像上から物体aを認識するためには以下のことができるといい感じになりそうです。

  1. 画像に写っている中から物体を見つける(Detectorの役割)
    • ここでいう物体は様々で、物体aだけではなく物体b、物体cなどたくさんあるイメージ
    • 何もしない状態では、コンピュータは背景と物体の区別すらつきません
  2. 画像が異なっていても、その物体を同一視できる/区別できる特徴を把握する(Descriptorの役割)
    • 画像Aには物体a、物体b、物体cが写っているとして、画像A'には物体a、物体d、物体eが写っているとします。 それぞれの画像に写る物体aが同じものであると認識したいですが、その一方で物体aは物体b、c、d、eとも異なるということも認識する必要があります

従来用いられる画像の特徴量抽出という技術は、この2段階をそれぞれ実現するための手法であると言えます。 さて、人は背景が白色で、その手前に黒色の物体が置いてあるとき容易に物体と背景を区別できます。 これは色や輝度の違いがあれば、画像に写る背景と物体を区別できるということになります。 色や輝度の違いとは、ある注目領域に比べてその周辺領域での変化が急激であるということです。 色や輝度の変化が急激な箇所は、画像中では線(エッジ)や角(コーナー)として発生し、この情報を使えば背景と物体の区別がつくということです。 Detectorでも同様にして画像中からエッジやコーナーという特徴点を検出するわけです。

What are the features between objects.
What are the features between objects.

ただし闇雲に特徴点を検出しまくると、今度は安定性に欠けることにも繋がります。 ごま塩ノイズなどが画像に発生しているとき、輝度が急激に変化しているピクセルをありったけ特徴点として認めてしまうと、 物体とは関係のない特徴点だらけになってしまうでしょう。 つまり、Detectorには撮影状況に対するロバスト性が求められます。

一方でDescriptorは特徴点の周辺領域の画像(ピクセル)を用いて、特徴量というベクトル化を行う処理になります。 ベクトル化することで、画像Aの物体は画像A'の物体と同じか？という類似性を数値的に算出することが可能になります。 しかし異なる画像AとA'のそれぞれに同じ物体aが写っていたとしても、その大きさや角度、明るさといった状態が変わってきてしまいます。 このような状況でも画像検索としては、同じ物体aだよ！という結果が望ましいので、 Descriptorに対しても撮影状況が変わっても同一視できる普遍性が重要になってきます。

正確には、物体として認識するためには特徴量を複数個集めてコンピュータに教えてあげることが必要で、 簡単な方法ですが良く用いられる方法がBag-of-Words(BoW)という方法です。 事前にある物体aの画像をたくさん集めて、これらの画像から特徴量をいっぱい取得してあげることで、物体aを構成する特徴量の集合を取得します。この特徴量の集合から新たなベクトルを作ってあげて、それを物体aとして覚えておく方法です(辞書;Dictionaryをつくる、と言います)。 このように多くの物体を辞書に登録しておくことで、物体の認識を行います。

KAZE

KAZEという手法は、P. F. AlcantarillaらによってEur. Conf. on Computer Vision (ECCV) 2012にて発表されたもので、 ECCV 2012はイタリアのフィレンツェで開催されたようです。 本家のサイトはこちら2です。 KAZE=風という手法名であり、そのまま発音してOKです。 OpenSfMでKAZEを改良したAKAZEが利用できるため、そのベースとなっている本手法についても論文を確認したいと思います。

さて、KAZEはDetectorおよびDescriptorの両方をまとめた呼び名です。 この手法の特徴は以下の点です。

  1. 風のように非線形なシステムに従ってその流れを表現するように、画像分野のマルチスケール画像の生成を扱いたい
  2. 非線形拡散フィルタ(nonlinear diffusion filter)を使ってマルチスケール画像から特徴量を抽出する
    • KAZEよりも従来の手法では1枚の画像からガウシアンピラミッドやそれを近似した画像ピラミッドをつかう
    • ガウシアンピラミッドなどは画像全体をぼやけさせるため、ノイズをボヤけさせてくれるが、背景と物体といった境界線までボヤけさせる
    • そのため、特徴点の位置精度の低下を招き、識別性能も低下させてしまう
    • 非線形拡散フィルタを使ってこの問題を解決する
  3. Additive Operator Splitting (AOS)というテクニックを使って非線形拡散フィルタによるマルチスケール画像を作る
    • 従来は前進オイラー法によって非線形フィルタを近似していたが、ステップ幅が小さい必要があり近似の収束性に難があり、うまく非線形フィルタを表現できなかった
    • この問題点に対してAOSを使うことで、安定した非線形スケール空間をつくることを実現
      • AOSは、三重対角行列をもつ線形システムをトーマスのアルゴリズムを使い効率的に解くことが可能

このようにしてKAZEでは画像からスケール不変（物体の大きさに依存しにくい）で変形に強い特徴量抽出を行います。 実験結果ではSURFやCenSurEと比べて若干の計算量増加で抑えています。

以下は論文に沿って見ていきます。

非線形拡散フィルタ

非線形拡散フィルタとはなんぞや？というと次式で表現された、 輝度が時間/スケールに対してどのように発展していくのかを意味する偏微分方程式です。

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

ここで、\text{div}は発散していく何かしらの関数であり、 \nablaは勾配を算出するオペレータです。 cは伝導率を表す関数で画像中の位置(空間)と時間/スケールに依存したものとします。 cと輝度勾配 \nabla Lとの内積をとることで時間/スケール、そして空間的な拡散の仕方を示します。 ただし簡単にするためにcはスカラーでもテンソルでもOKです。 tは時間を意味しますがスケールパラメータとして扱われます。 流体のように時間が経過するにつれ発散するように進展していき、 tが大きくなるに従い複雑な形状ではなく単純な形状を表現するようになります。

画像分野に非線形拡散フィルタが用いられ始めたのは1990年のPerona, P.とMalik, Jらの論文からということでかなり歴史があります。 彼らの論文では伝導率cを輝度勾配の強さ(magnitude)で表現することで画像中にあるエッジでの拡散の強さを低減していたようで、KAZEの文献では次式で表現されています。

c(x,y,t) = g(|\nabla L_{\sigma}(x,y,t)|)

オリジナルの画像Lに対して\nabla L_{\sigma}は\sigmaのガウシアンフィルタをかけてから勾配をとったものです。 このような関数gの形はいくつか提案されていて、Perona, P.とMalik, Jらは次のg_1、g_2を使っています。

g_1 = \exp{ \left\{ - \frac{|\nabla L_{\sigma}|^2}{k^2} \right\}}, g_2 = \frac{1}{1+\frac{|\nabla L_{\sigma}|^2}{k^2}}

kはパラメータで拡散の強さを調整します。 g_1は高コントラストを助長させる効果があり、 g_2を逆に低コントラストで広い領域を助長させる効果があります。

さらに2001年にWeickert, J.は、エッジの両側で拡散の強さは早く、一方でエッジ自体の拡散は弱くなるような次の形状を提案しています。 これによってエッジは非線形拡散を行っても残りやすくなります。

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

このg_3は画像中の物体と物体を跨ぎながら影響するブラーよりも、各物体内や境界線内という限られた領域内に影響するブラーのほうが強くなります。 文献中では、

That selective smoothing prefers intraregional smoothing to in- terregional blurring.

と言及されています。

KAZEの文献では、パラメータkをオリジナル画像に対して平滑化をかけたあとの画像から勾配ヒストグラムを作成し、 70パーセンタイルの値を使っています。 前回記事でOpenSfMのconfigについて触れていますが、AKAZEでもakaze_kcontrast_percentileという同様のパラメータがあり、 70%(=0.7)でとして設定されていることが確認できます。

...
# Params for AKAZE (See details in lib/src/third_party/akaze/AKAZEConfig.h)
akaze_omax: 4                      # Maximum octave evolution of the image 2^sigma (coarsest scale sigma units)
akaze_dthreshold: 0.001            # Detector response threshold to accept point
akaze_descriptor: MSURF            # Feature type
akaze_descriptor_size: 0           # Size of the descriptor in bits. 0->Full size
akaze_descriptor_channels: 3       # Number of feature channels (1,2,3)
akaze_kcontrast_percentile: 0.7
akaze_use_isotropic_diffusion: no
...

より強いコントラストであるエッジを使いたければ、このパラメータを高く設定し、 逆に低いコントラストであるエッジも使いたいときは低めに設定する必要があります。 g_1の場合で、kがどの様な影響を与えているのかは、KAZEの論文Fig.1.[^1]にわかりやすい図があります。 AKAZEを使ってダンテのデスマスクを3次元復元する際に調整する必要がでてくるかもしれません。

Effect of Hyper-parameter k
Effect of Hyper-parameter k

AOS

論文の流れに沿ってみていくと、次はAOSについて言及されています。 ご存知の通り、非線形な偏微分方程式を解析的に解くことは難しいです。 解析的に解くとは、方程式が与えられている場合に、ごにょごにょ手計算を行いL=...という形式で解を求めることです。 解析的に解くことが難しいため、機械学習の界隈では損失関数を決めて最小にするような最適化を行います。

そのため、非線形拡散フィルタに対しては偏微分を離散化する上で、AOSというテクニックを使います。 一般的に非線形な偏微分方程式は線形化して近似するような方法をとります。 先に示したLに関する偏微分方程式は半陰的(semi-implicit)に解くと、次のように書けます。

L^{i+1} = ( I - \tau \sum_{l=1}^m A_l )^{-1} L^{i}

ここでA_lは誘導率を行列化したものです。 半陰的に解くことでステップサイズ\tauに依らず安定的に算出ができる特性を持ちます。 画像分野でのスケール空間で計算を行おうとすると大きな時間幅を扱いたいので、このときに便利になります。 上記の式形状は線形システムとなるので、三重対角行列をもつ線形システムをトーマスのアルゴリズムを使い効率的に解くことが可能となるようです。

KAZEの特徴点検出および特徴量記述

さて、ようやく非線形拡散フィルタによって、オリジナル画像からスケール空間に非線形にぼやけさせた画像たちを生成することができます。 そしてこのぼやけさせた画像たちから特徴点を検出し、その特徴点をベクトル化する特徴量記述を行います。

特徴点の検出は、SIFTと似た方法を取ります。 まずは非線形拡散フィルタの適用方法を述べていきます。

SIFTでは最初のOctaveの中ではオリジナル画像と同じ画像サイズでフィルタをかけていき、 次のOctaveに進むときにダウンサンプリングすることで画像サイズを小さくしていきます。 しかし、KAZEではダウンサンプリングを行わないようです。 またSIFTではガウシアンフィルタの標準偏差\sigmaがピクセル単位となりますが、 非線形拡散フィルタでは時間単位に合わせておきたいため、tと\sigma間のマッピングを決めておきます。

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

octaveがo、sub-levelがsであり、次のように初期スケールレベル\sigma_0に対して定めます。 当然ながら、Nはフィルタをかけた画像を総計何枚作成するのかを示すパラメータで、 OとSはそれぞれいくつのoctaveをつくるか、いくつのsub-levelをつくるのかを示すパラメータですね。 オリジナル画像に対して\sigma_0で一度ガウシアンフィルタをかけて、ノイズやアーチファクトの影響を少し低減しておき、 その後は非線形拡散フィルタを使います。 ガウシアンフィルタをかけた画像を基底画像(base image)として扱い、この画像からパラメータkを定めるわけです。

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

論文[^1]にあるFig.2.を貼り付けますが、明らかにガウシアンフィルタでは全体がぼやけてしまっていますが、 非線形拡散フィルタではエッジ部分をきれいに残しつつも、細かな構造をぼやけさせることに成功しています。

Effect of Nonlinear Diffusion Filter
Effect of Nonlinear Diffusion Filter

あとはHessianを使って特徴点を定めるのですが、スケールで正規化したHessianをKAZEでは使います。 これは、ぼやけさせていくことで各スケールにおける画像の勾配強度が低下していく傾向があるからです。 [tex:Li]の非線形拡散フィルタをかけた画像に対応するスケール\sigma_iの画像と、その前後のスケールの画像たちから極大値を取るような位置を探し出して完了です。

特徴量記述は、ほぼほぼSURFと同じ方法で算出しますので省略します。 論文中では文章のみの記述となっていますので、時間ができたときに図示して追記したいと思います。

結局、KAZEでは64次元でベクトル化した特徴量を得ることができます。

まとめ

最後のほうはSURFやSIFTとかなり類似していたので、説明が荒くなってしまいましたが、 KAZEの特性は論文の図を見るだけでかなりわかったかと思います。 時間ができたときに考察についても追記していきます。

文献

  1. Alcantarilla, Pablo. et. al., KAZE Features,Proc. of the 12th European Conference on Computer Vision(ECCV'12) - Volume Part VI,,2012,Florence, Italy, pp.214-227. ↩

  2. www.robesafe.com↩