プログラムdeタマゴ

nodamushiの著作物は、文章、画像、プログラムにかかわらず全てUnlicenseです

画像処理を始めよう ー特徴量1 コーナー検出ー

分散の話書くとか言っておいて、面倒くさくなって放置してた。とりあえず、基礎はいいや、ということで、すっ飛ばして特徴量の話をしていくよー。ここに書いてく話はすでにPDFに一回私が雑にまとめた内容をリファインしながら書いていくつもりだけど、そのPDFが既に2カラムで20P近くあります。いったい記事何回分になるんだろうね。



 最新技術を紹介していくのも良いですが、原点に立ち返ってゆっくり進めていくのも良いでしょう。この記事は焦らず初期の初期からやっていきます。

輪郭

 
 画像の特徴って何でしょう?色々考えられます。画像の色、輝度、輪郭、固有値、固有ベクトル、写っている物体の形状、数、等考えつく物は大体何でも特徴と言えます。

 目的にもよりますが、これらの中でも輪郭は重要です。人間は物体の輪郭に強く反応します。輪郭線さえしっかりしていれば、多少色は適当に塗られていても問題ないぐらいです。ちなみに、脳の中で色を処理する部位と輪郭を処理する部位は異なるそうです。別々に処理して後から結合して意識に上がる頃には一つの情報になっている。う〜ん、人間の無意識部の処理って凄すぎです。

 さて、無意識下でどういった処理が行われているか分かりませんが、我々は輪郭を見て「これは人っぽい」とか「これはネコっぽい」とか、何となく全体をとらえて認識ができます。でも、残念ながら計算機では、配列データとしてこのインデックスは輪郭のフラグが立っているという局所的な情報しか知り得ません。全体の輪郭情報を一つの輪郭として認識し、「この輪郭は〜だ!」なんて言える手法は少なくとも今のところ存在していません。ほんと、人間ってすげーんすよ。
 そもそも、その輪郭を得るにはどうしたら良いの?得られたとして、その輪郭情報をどう使えば良いの?と言う問題も考えなくてはなりません。



コーナー検出

 計算機は全体を全体として、そのままに理解する事は出来ません。少なくとも2013年現在のアルゴリズムでは。そこで、輪郭の中から何らかの特徴的な情報を抜き出してくる必要があります。では、どのような情報を輪郭から持ってこれるでしょうか?簡単に思いつくのが、「勾配強度」「勾配方向」「輪郭の繋がりの長さ」「輪郭の曲がり具合」などが思いつくでしょう。今回はその中でも、「輪郭の曲がり具合」の一つ「頂点の検出」の話をします。


 頂点ってのは輪郭の中でもわかりやすい特徴です。だって、四角形とか三角形とか頂点の数で分類されてるよね。
 頂点は特徴なので、そこから特徴を得るには、例えば角度とか、頂点の個数とか、別な値に変換する必要があります。それら特徴は今後話していく予定のHOGやらShapeContextやらオプティカルフローやらを必要に応じて選びます。




 さて、何はともあれ、頂点ってどうやって認識するのでしょうか?
 そんなの、輪郭を辿っていって、同じ方向に輪郭がなかったら頂点だろうと思うかもしれません。なぜなら、我々人間は画像を一目見て、輪郭がどこにあり、輪郭が曲がっているのか認識できます。しかし、残念ながら計算機は全体を把握するのは大変なんです。そもそも、綺麗に繋がった輪郭画像を出力することが中々難しいんですから。


Moravecのコーナー定義

 コーナーとは何なのか?その一つの定義として、Moravecにより提案された方法があります。彼はコーナーとは「周辺と自己相似性が低い所」と定義しました。



 状況を非常に簡単化した上の図を見ながら説明していきましょう。黒い線でコーナーと呼べるところはわかりやすく一点しかありません。この黒い線をいくつかの領域内でだけ見てみましょう。図の中で黄土色、水色、紫の4つの四角で表しています。
 水色の枠は、コーナーではない線の上を平行移動しただけです。どうでしょうか?領域内に見える黒い線に変化が全くないと言うことが分かると思います。つまり、この二つの水色枠内部の線は非常によく似ていると言えます。紫の枠は線に対して垂直方向に枠を移動させた物です。多少見た目が変わりましたが、よく似ています。このことから、コーナーを含まない輪郭領域は、輪郭方向に移動させても見た目は変わらず、輪郭と垂直方向に移動させると、多少変わるという事が言えます。

 一方、黄土色の枠内部はどうでしょうか?他の三つとは形状が全く異なることが明らかです。つまり、コーナーを含む領域は「どの方向の周辺とも似ていない」という事が言えるわけです。


 これを一言で表すと「周辺パッチ(枠の事)と自己相似性が低いパッチはコーナーを含む」となります。Moravecの具体的な手法は端折り、次のHarrisらの手法で具体的にどういった計算をするのか説明します。




Harrisのコーナー検出

 Moravecのコーナー検出の話を推し進めたのがHarrisのコーナー検出です。


 まず、我々が考えなくてはならない事は「自己相似性とは何なのか?」についてです。画像において似てる似てないを判断する最も単純な方法は、「2つの領域内の同じ点に同じ色があるかどうか」を判断することです。色を扱うと大変なので、今はグレースケール画像を扱うことにしましょう。
 比較する2つの領域の距離を(\delta x,\delta y)とし、

S(\delta x,\delta y)=\sum_{(x,y)\in R}w(x,y)(I(x,y) - I(x+\delta x,y+\delta y))^2  (1)

で、自己相似性を表すことにします。Iは画像、Rは現在調べてる領域を表し、wは点の重みを表します。重みがわざわざついているのは、スムージングの為と元の論文によると書いてあるんだけど、実は数学的な意味はそうではないらしい。
 この数式Sが0に近いほど、二つの領域はよく似ていることになります。つまり、コーナーの検出は自己相似性の低い、すなわちSの値が大きな領域Rを探すことになります。


 いま、2領域の距離(\delta x,\delta y)が非常に小さいとしましょう。すると、(1)はテイラー展開を用いて(2)になります。
S(\delta x,\delta y)=\sum_{(x,y)\in R}w(x,y)(I_x\delta x - I_y\delta y)^2  (2)

 ここでは簡略の為、Iのx方向微分をI_xと言った形で表しています。(2)式を行列形式に変形してみましょう。
\sum_{(x,y)\in R}w(x,y)(\delta x,\delta y)\left(\begin{array}{cc}I_x^2&I_xI_y\\I_yI_x&I_y^2\end{array}\right)(\delta x,\delta y)^T (3)

 ここで、(x,y)に関係ない物はΣの中から出してしまいましょう。

(\delta x,\delta y)\left\{\sum_{(x,y)\in R}w(x,y)\left(\begin{array}{cc}I_x^2&I_xI_y\\I_yI_x&I_y^2\end{array}\right)\right\}(\delta x,\delta y)^T={\bf \delta x M\delta x}^T (4)

 太文字は行列やベクトルであることを表します。

 このMですが、重みwで表されるフィルターWをそれぞれの要素に畳み込んだ物ですのでΣを外して以下のように書き換えられます。
M=\left(\begin{array}{cc}(I_x^2)*W & (I_xI_y)*W \\  (I_xI_y)*W & (I_y^2)*W\end{array}\right)

 このwはガウス関数で定義されています。

 ハリスによると、Sとは局所自己相関関数に類似した物である。Mの固有値をαとβとすると、これらの固有値は局所自己相関関数の主曲率に比例する物である。そして、これらの値は回転不変である。とのこと。ごめん、意味わかんねぇ。納得できねぇ。


 この納得できねぇをなんとか納得させてくれたのが、こちらの解説(注:リンク先はPDF) 曲率を計算するには2階微分が必要なのだが、スムース化の為と言っていたwのガウス関数が実は1階微分を2階微分相当の物に変換する処理になるらしいのだ。


 うん、画像処理というか、工学の世界ではよくあるよ、こういうこと。とりあえず、なんかそれっぽいからそれで良いじゃんって。厳密さよりも利便性、それらしさだからね。


 さて、なんとか納得でき………たということにしよう。Mの固有値とは、主曲率の大きさを表す物なのだと。
 コーナーとは何なのか?の話に戻り、どの方向に動かしても似てないということは、主曲率はどの方向にも大である事をさす。一方、真っ直ぐなエッジ上のように平行移動させた方向にはさして変わらないような場合は、一方だけ大であり、一方は小さい。(二次元平面じゃなくて、(x,y,輝度)の3次元空間での話です。)
 よって、Mの固有値の大小を考えることでコーナーかどうかを判断することが可能になる。


 だが、固有値の計算は面倒くさい。そこでハリスは
R=Det(M)-kTrace^2(M)
を代わりに計算し、これが閾値よりも大きいか小さいか大きいかで判断する。kは実験的に求めるしかなく、0.04〜0.15の値が良いらしい。


 なお、もちろん真面目に固有値を計算してもよく、例えばKanade-Lucas-Tomasi法でのコーナー検出では固有値を計算する。


 ハリスのコーナー検出は様々に拡張されており、回転不変だけでなく、アフィン変換やスケールやらに不変になるようになされたり、3次元空間に拡張されたり、色々進化しているので、調べてみても良いでしょう。



 また、今一般に使われやすいコーナー検出方法はハリスではなく、FAST辺りだと思います。OpenCVでも使えます。FASTは周囲の点の暗い明るいという情報が連続しているかどうかという情報からコーナー判定をします。ただし、実際に連続しているかどうかを計算するのではなく、機械学習によって得られた決定木を用いることで数ピクセルだけ比較し高速に計算するという手法です。これについてもいずれ。




 次回は、みんな大好きSIFT特徴量の予定です。