特徴量抽出のブームなんてDeep Learningみたいな話題のせいで、とっくに過ぎ去った感はあるけど、SIFT(Scale-Invariant Feature Transform)がどうして物体の大きさや回転に不変なのか不思議でたまらなかった。なにか規格化のようなものをやってるだろうと思うけど、想像ができなかった。今回初めて画像の特徴量抽出の勉強をするけど、この手法の考え方って画像以外の別のものにも応用できるエッセンスが詰まっているんじゃなかろうか、と思うようになった。（カメラの光学系認識なんかにつかえると面白いんやけどなー）
ちまたにはわかりやすい資料も結構落ちている。更にOpenCVなんかを使えば一発で実行できる。でもそれじゃ勉強にならないので、ここではSIFTの原理を紹介しつつPythonで実装していきたい。
参考文献は以下の２つ。
前者は開発者Loweさんが書いた論文。後者は日本語でそのまとめ＋αな感じ。.
C++で実装されたプログラムについては
http://www.robots.ox.ac.uk/~vedaldi/code/siftpp.html
http://www.robots.ox.ac.uk/~vedaldi/code/siftpp.html
が大変参考になった。
有名な話かもしれませんが、SIFTは特許が取られていますので、商用利用する場合はちゃんと権利確認をしてください。
有名な話かもしれませんが、SIFTは特許が取られていますので、商用利用する場合はちゃんと権利確認をしてください。
さて、では蛇でもわかるように説明しながらやっていきましょう。
[1]の論文ではSIFTは4つの過程を踏むことになっている。
k=2**(1/3.)は1オクターブに3枚の画像をとることを想定している。つまり3枚とればσが2倍になる。ねぶた祭りの写真で効果を見てみる。
1枚目は原画像、2枚めはσ=1.6の時のDoG画像、3枚目は2オクターブ上がってσ=4.8の時のDoG画像。DoGのピクセル値は負の値もとるので適当なオフセットを加えて保存。DoG≒Laplacian Filterなので微分画像になってエッジが強調されているのがわかる。論文[1]によると、1オクターブに3つくらいのスケールサンプルを取得して、その時のσは1.6というふうに実験から決定している。では何オクターブ分サンプルすればよいのか?? 論文に記載はなかったけど、VLFeat(特徴量抽出ライブラリ)の説明によるとできるだけたくさん(だいたいlog2(min(width, height)オクターブくらい)が良いらしい。
2オクターブ目のガウシアンフィルタは計算量を抑えるために画像を半分にリサイズして1σのフィルタを掛けるとよい。ではこの時点でどのくらいの特徴候補点があるか調べてみたい。速さが気になるけど、Pure Pythonで組んでみよう。結果は下のようになった。検出された候補点を白丸で表す。丸の大きさはDoG画像の画素値を表していて、今回は1から50ピクセルに規格化してある。
候補点は全部で1500くらい検出されたので少し見にくいが、暗くコントラストの低い部分は点が小さく、顔の部分など構造をもった部分は点が大きいように思える。
まず、コントラストの低いところ(上の図の暗いところなど)は削りたい。これは検出されたDoG画像の画素値にスレッショルドを設けることで排除できる。論文[1]では画素レンジを[0,1]としたときに0.03としている。
次にエッジ上の点を消去して、コーナーの点だけを残したい。エッジ上の点は強く反応するけど、変化に対して場所が変わり易いからだ。確かに、コーナーだと1点に決まるけど、エッジ上の点は無限に点が反応してしまう気がする。
さて、コーナーか、エッジかを見分ける方法はどうするか??SIFTでは極値での主曲面(Principal Curvature)を使うらしい。エッジなら片方に長細い曲面になっているはず、ということだ。これを調べるのに、極値でのDoG画像のヘッセ行列(2階微分した行列)の固有値を使う。この固有値の比があるスレッショルド以上ならエッジとみなすというわけである。論文では10としてある。
これらをやるついでと言ってはなんやけど、より正確な極値をサブピクセルの精度で求めることができる。具体的にには上でも求めた極値において、DoG関数の2次のテーラー展開を行い、2次式なら極値は解析的に求まるので、
となる(論文[1], 式(3))。こうしたほうが精度が上がるそうだ。たぶん理由はピラミッドとかを作ったときに精度が落ちたんやろう。SIFTが提案された初期にはこの補間はやってなかったようだ。どうやらLowe先生のお弟子さんが考えたらしい。
これを実装すると以下のようになる。一番上は何もしきい値を設けてない場合。2番めはローコントラストの部分を取り除いた画像。3番目はエッジ部分を取り除いた画像。
[1]の論文ではSIFTは4つの過程を踏むことになっている。
- Scale-space extrema detection:
- スケールスペースを探索して特徴点となる候補点を見つける。(→スケール変換に対してロバストになる)
- Keypoint localization:
- ノイズ耐性のない点やエッジ上の点を除外して候補点の絞り込みを行う。
- Orientation assignment:
- 特徴点周辺の強度と向きを計算し、方向ヒストグラムを作成し、特徴点の向きを決定する。(回転に対してロバストになる)
- Keypoint descriptor:
- 輝度勾配と方向からなる特徴量ベクトルを作成。(→規格化することで照明変化にロバストになる)
このうち、要点となるのは"Scale-space"と"Orientation Histogram(勾配ヒストグラム)"だと思う。後者はHoG(Histogram of Oriented Gradient)の考えに非常に近い(HoGは具体的に勉強してないのでホントはわかりません)。SIFTではこの2つの重要な考え方を組み合わせて、1,2で重要な注目すべき点を見つけて、3,4でその周辺の形状をパラメータ化するという過程を踏む。その他ちょっとしたテクニックもあるけど、要点はそうだ。
1. Scale-space extrema detection
まずスケールスペースというのを導入する。要するに画像は普通は縦と横の2次元(x,y)で考えるけど、これに大きさの次元も加えて考えましょうということ。それで、大きさ方向パラメータを振ったときに極値があれば、そこを特徴点の候補としましょう、ということ。この極値がどんな大きさの画像でも同じパラメータで表せられれば良い。そんなうまいScale-spaceの取り方が唯一存在していて、それがガウシアン画像(ガウスカーネルでフィルタされた画像)だという。標準偏差σをパラメータとしてこれを変化させていく。別々のσ間での差分画像をDoG画像(Difference of Gaussian)と言い、SIFTではこのDoG画像の極値を探していく。下の図は論文[1]より。
このとき、DoGの注目画素の隣接26箇所(9+8+9)を調べて一番大きいまたは小さいときに極値としてそのときのσの値をその候補点のスケールとして登録する。
ではPythonでDoG画像がどんなものか再現してみる。Pythonで画像にガウスフィルタを適用するのにScipyのモジュールを使わせて頂く。PythonとNumpyで画像を扱う場合はこちらを参考に。
from scipy.ndimage.filters import gaussian_filter
import numpy as np
import Image
org = Image.open("nebuta.jpg").convert('L')
org.show()
sigma = 1.6*3 #first scale
img = np.array(org, np.float64)
g1img = gaussian_filter(img, sigma) #first scale image
k= 2**(1/3.)
g2img = gaussian_filter(img, k*sigma) #second scale image
dog = (g2img - g1img)
pmin = np.min(dog)
pmax = np.max(dog)
dog -= pmin
dog *= 255 / (pmax - pmin)
Image.fromarray(dog).show() #show DoG image
k=2**(1/3.)は1オクターブに3枚の画像をとることを想定している。つまり3枚とればσが2倍になる。ねぶた祭りの写真で効果を見てみる。
1枚目は原画像、2枚めはσ=1.6の時のDoG画像、3枚目は2オクターブ上がってσ=4.8の時のDoG画像。DoGのピクセル値は負の値もとるので適当なオフセットを加えて保存。DoG≒Laplacian Filterなので微分画像になってエッジが強調されているのがわかる。論文[1]によると、1オクターブに3つくらいのスケールサンプルを取得して、その時のσは1.6というふうに実験から決定している。では何オクターブ分サンプルすればよいのか?? 論文に記載はなかったけど、VLFeat(特徴量抽出ライブラリ)の説明によるとできるだけたくさん(だいたいlog2(min(width, height)オクターブくらい)が良いらしい。
2オクターブ目のガウシアンフィルタは計算量を抑えるために画像を半分にリサイズして1σのフィルタを掛けるとよい。ではこの時点でどのくらいの特徴候補点があるか調べてみたい。速さが気になるけど、Pure Pythonで組んでみよう。結果は下のようになった。検出された候補点を白丸で表す。丸の大きさはDoG画像の画素値を表していて、今回は1から50ピクセルに規格化してある。
候補点は全部で1500くらい検出されたので少し見にくいが、暗くコントラストの低い部分は点が小さく、顔の部分など構造をもった部分は点が大きいように思える。
2. Keypoint Localization
ご覧の通り無駄な点が多すぎるのでここで候補点を絞りたい。まず、コントラストの低いところ(上の図の暗いところなど)は削りたい。これは検出されたDoG画像の画素値にスレッショルドを設けることで排除できる。論文[1]では画素レンジを[0,1]としたときに0.03としている。
次にエッジ上の点を消去して、コーナーの点だけを残したい。エッジ上の点は強く反応するけど、変化に対して場所が変わり易いからだ。確かに、コーナーだと1点に決まるけど、エッジ上の点は無限に点が反応してしまう気がする。
さて、コーナーか、エッジかを見分ける方法はどうするか??SIFTでは極値での主曲面(Principal Curvature)を使うらしい。エッジなら片方に長細い曲面になっているはず、ということだ。これを調べるのに、極値でのDoG画像のヘッセ行列(2階微分した行列)の固有値を使う。この固有値の比があるスレッショルド以上ならエッジとみなすというわけである。論文では10としてある。
これらをやるついでと言ってはなんやけど、より正確な極値をサブピクセルの精度で求めることができる。具体的にには上でも求めた極値において、DoG関数の2次のテーラー展開を行い、2次式なら極値は解析的に求まるので、
これを実装すると以下のようになる。一番上は何もしきい値を設けてない場合。2番めはローコントラストの部分を取り除いた画像。3番目はエッジ部分を取り除いた画像。
続く…
面白く読みました。続きをお待ちしています。
返信削除