3日で作る高速特定物体認識システム(2) SIFT特徴量の抽出

3日で作る高速特定物体認識システム (1) 物体認識とは（2009/10/18）の続きです。

今回は、画像からSIFT (Scale-Invariant Feature Transform) という局所特徴量を抽出するところを作ってみようと思います。

SIFT特徴量の抽出

まずは、局所特徴量の代表ともいえるSIFTを試してみます。OpenCVにはSIFTを抽出する関数がなかったのでRob Hess氏がC言語で実装したライブラリを試してみます。内部でOpenCVを使っているので事前にOpenCVのインストールが必要です。実装はOpenCV 1.1でされているみたいですが、2.0でもちょっと手直しすると動きました。Rob Hess氏のホームページからSIFT Feature Detectorのzip版を落とします。

（注）Hess氏のサイトが更新されたようで現在はGitHub上のOpenSIFTというプロジェクトで公開されています。

解凍するといろいろファイルができますが、SIFTを抽出するのに最低限必要なのは、

  siftfeat.c - メイン関数
  sift.c sift.h - SIFT抽出用関数
  imgfeatures.c imgfeatures.h - SIFT特徴量を描画、保存する関数
  utils.c utils.h - ユーティリティ関数
  beaver.png - テスト画像

です。これらを自分のプロジェクトに追加します。OpenCV2.0でコンパイルするといくつかエラーが出た*1ので直します。imgfeatures.cの373行目を

cvEigenVV( &M, &V, &E, DBL_EPSILON, 0, 0 );

siftfeat.cの28, 29行目を

char* img_file_name = "beaver.png";
char* out_file_name  = "beaver.sift";

同じく72行目を

cvSaveImage( out_img_name, img, 0);

に修正します。まだいろいろ警告は出ますがとりあえずコンパイルできます。beaver.pngという画像で実行すると下のような画像が表示されます。

矢印の始点はキーポイントの位置、矢印の長さはスケール、矢印の向きは勾配強度がもっとも強い向きを表しているようです。SIFTの表示方法はキーポイントの点だけ表示、矢印で表示、円で表示などいろいろあるみたいですね。スケールや勾配強度が何を意味しているかはもう少し調査が必要です。当面は、SIFTのキーポイントの位置とそれぞれの点が128次元の特徴ベクトルで表せることだけおさえとけばいいかな？

それぞれのキーポイントの128次元ベクトルは、beaver.siftというファイルに保存されています。矢印1本につき128個の数値（128次元ベクトル）です。下のようなファイルです。

114 128    <--- キーポイントの数と特徴ベクトルの次元数
101.350182 136.130755 40.169879 0.771085  <--- 1つめキーポイントのX座標, Y座標, スケール, 向き
 0 0 0 0 3 1 0 0 2 23 46 15 18 3 0 0 6 20 13 1  <--- インデントされている数字が128次元ベクトル（20個で改行が入る）
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 88 36 0 0
 81 95 57 47 185 114 2 7 185 155 19 6 19 6 1 22 22 0 0 0
 0 0 0 1 0 0 0 0 37 8 0 0 91 12 0 1 185 144 11 35
 185 50 0 0 23 28 8 95 40 1 0 0 0 0 0 4 0 0 0 0
 0 0 0 0 11 5 0 0 4 2 0 0 49 20 0 0 1 0 0 1
 0 0 0 0 0 0 0 0
127.871536 71.100579 15.768590 -2.024589  <--- 2つめのキーポイント
 1 2 2 72 63 12 1 1 133 93 1 4 2 7 4 44 133 115 0 0
 0 0 0 20 9 4 0 0 0 0 0 0 23 0 1 9 107 20 1 8
 133 5 0 0 0 1 5 133 132 14 0 0 0 0 8 133 14 1 0 0
 0 0 0 8 26 0 0 0 126 37 8 22 133 47 0 0 0 0 3 52
 131 41 0 0 0 0 2 36 1 0 0 0 0 0 0 2 2 0 0 0
 34 105 80 24 111 15 0 0 0 1 55 66 79 21 0 0 0 0 0 5
 0 0 0 0 0 0 0 0

上の画像の場合、128次元ベクトル114本によって表されるってことですね。この128次元ベクトル114本を物体モデルデータベースに登録しておくことになります。けっこう膨大な数値です。このファイルをよく観察するとどうやらキーポイントはスケールの大きな順（矢印が長い順）に並んでいることがわかります。これまたまだよくわかってないのですが、スケールが大きいキーポイントほど重要と解釈してよいのでしょうか？もし詳しい方がいたらアドバイスください。

キーポイントを点で描画

ここでちょっと改造してみます。キーポイントを矢印ではなく点表示にし、SIFTファイルが1行で1個のキーポイント情報を表すようにします。imgfeature.cの595行目あたりを

//	cvLine( img, start, end, color, 1, 8, 0 );
//	cvLine( img, end, h1, color, 1, 8, 0 );
//	cvLine( img, end, h2, color, 1, 8, 0 );

	cvCircle(img, cvPoint(start_x, start_y), 2, cvScalar(0,255,255,255), -1, 0, 0);

とし、同じファイルの523行目あたり（数字20個おきに改行を入れる部分）をコメントアウトします。

//			if( j % 20 == 0 )
//				fprintf( file, "\n" );

こうすると下のようにキーポイントが点になります。beaver.siftも1つのキーポイントの情報が1行にまとまります。スクリプトで処理するときはこっちの方が楽だと思います。

いくつかの画像でSIFTキーポイントを描画してみます。SIFTが画像のどういうところをキーポイントとしてるか大体想像つきますね。陰陽マークみたいにあまり模様がない画像ではキーポイントが少なくなりがちみたいです。

SIFTの詳細

SIFTのキーポイントは、画像の特徴をよく表している場所ってことはわかりました。では、どういう根拠に基づいてその点が選ばれたのか？128次元ベクトルがどういう風に求められたのか？はアルゴリズムの詳細を詳しく調べる必要があります。SIFTは結構複雑なことをやっていて、ガウシアン平滑化フィルタ、Difference of Gaussian (DoG)、局値検出、画像の微分、強度勾配など画像処理の理論がわかっていないと理解が難しい・・・私もまだおぼろげに理屈がわかってきた程度です。

1つ思い違いをしてたのは、SIFTは色情報を使ってないってことかな。実際、グレースケール画像から抽出してます。いくつか参考にした文献を挙げておきます。これらを参考にそのうちC++版のSIFTを作ってみようと思います。

3日で作る高速特定物体認識システム (3) SURFの抽出（2009/10/30）へつづきます。

• SIFTチュートリアル - 藤吉先生によるSIFTの解説資料、図が豊富でわかりやすい。
• SIFTを1から組むブログ - 手順を追って少しずつ実装しているのでわかりやすい。途中でららら♪ってごまかしてるけど（笑）
• Rob Hess氏のSIFT特徴量抽出モジュールつかってみる - Rob Hess氏のプログラムの実行方法です。
• SIFT++ - 別の実装。こっちも試してみたい。
• SIFT for Matlab - Matlabによる実装。
• Scale-invariant feature transform - Wikipediaの記事。
• Keypoint detector - SIFTの提案者Lowe氏のデモ。
• D. G. Lowe: Object recognition from local scale-invariant features (PDF), Proc. of IEEE Intl. Conf. on Computer Vision (ICCV), pp.1150-1157 (1999) - SIFTの原論文
• D. Lowe: Distinctive imagefeatures from scale-invariant keypoints (PDF), Proc. of Intl. Journal of Computer Vision (IJCV), 60(2), pp.91-110 (2004) - SIFTの原論文

このシリーズの記事一覧

• 3日で作る高速特定物体認識システム (1) 物体認識とは（2009/10/18）
• 3日で作る高速特定物体認識システム (2) SIFT特徴量の抽出（2009/10/24）
• 3日で作る高速特定物体認識システム (3) SURFの抽出（2009/10/30）
• 3日で作る高速特定物体認識システム (4) 特徴点のマッチング（2009/11/2）
• 3日で作る高速特定物体認識システム (5) 物体モデルデータベースの作成（2009/11/14）
• 3日で作る高速特定物体認識システム (6) 線形探索を用いた特定物体認識（2009/11/22）
• 3日で作る高速特定物体認識システム (7) 最近傍探索の高速化（2009/12/12）

*1:MinGWを使ってます。Visual C++なら出ないのかな？