コンピュータビジョン類似画像検索システムを作ろう(2009/10/3)3日で作る高速特定物体認識システム(2009/10/18)に続くOpenCVプロジェクト第三弾です。今回は、上の二つをふまえてカラーヒストグラムではなく、局所特徴量(SIFTやSURF)を用いた類似画像検索を試してみます。局所特徴量はグレースケール画像から抽出するため、カラーヒストグラムと違って色は見ていません。画像の模様(テクスチャ)で類似性を判定します。EclipseでMinGWを使う方法はEclipseでOpenCV(2009/10/16)を参照してください。C++を使う場合は、少しだけ修正が必要です。Words表現について簡単にまとめておきます。Wordsを用いると画像をただ1つの特徴ベクトルで表現できます。Wordsは、別名としてBag-of-FeaturesやBag-of-Keypointsという呼び方もあります。Wordsという呼び方が一番好きです。この手法はもともと自然言語処理でよく使われるBag-of-Wordsのアナロジーとして画像へ応用した手法だからです。Bag-of-Wordsは文書をベクトルで表現する手法で自然言語処理の分野では当たり前のように使います。簡単に言うと、文書を単語の集合として扱います。実際は、対象文書集合からTF-IDFで特徴語を抽出して文書ベクトルの次元とし、TF-IDFの重みを文書ベクトルの値とする方法がよく使われます。あとでナイーブベイズを利用した文書分類を紹介する予定ですがそのときに使ってみます。画像における単語とは何か?という話になるのですが、それは今まで使ってきた局所特徴量です。Wordsは、テキストの単語⇔画像の局所特徴量と対応させる方法です。Wordsを構築する画像集合を用意します。それぞれの画像から局所特徴量を抽出します。図では、わかりやすいように局所特徴量を小さな画像で表現していますが、実際は128次元のSIFTやSURFの特徴ベクトルです。全部の特徴ベクトルをK個のクラスタにクラスタリングします。クラスタリングにはK-meansという手法がよく使われます。セントロイドも特徴ベクトルと同じく128次元ベクトルで表されます。Wordsができます。Wordが得られます。Wordsを次元とするヒストグラムに変換します。Wordに投票することで行います。最終的にこのヒストグラムが画像の特徴ベクトルになります。この例では、7次元の特徴ベクトルです。Wordは数百から数千個選ぶので数百から数千次元のベクトルになります。Wordsを使うと一枚の画像を数百次元のベクトル一本で表せます。Machineなどの分類器が使いやすくなってうれしいですね。このヒストグラムの形は類似画像ほど似ているはずです。上図だとアコーディオン同士のヒストグラムは似ていますね。ヒストグラム同士の類似度は、類似画像検索システムを作ろう(2009/10/3)で使ったヒストグラムインターセクションなどが使えます。説明が長くなりましたが、実際に試してみます。詳しい説明は参考文献を参照してください。実験で使う画像データセットを用意します。今回は類似画像検索システムを作ろう(2009/10/3)で使ったCaltech101をまた使います。ダウンロードしたデータを解凍すると101_ObjectCategoriesというフォルダの中に101個のカテゴリフォルダ(102個あるけどBACKGROUND_Googleが余計?)があり、その中に画像がたくさんあります。フォルダ(カテゴリ)には飛行機の写真がたくさん入ってます。Faces_easyは少し特殊な画像なのでフォルダごと削除します。次に、フォルダごとに画像ファイルが分散されてるので一括処理しやすいようにcaltech101というフォルダに画像ファイルだけまとめます。各カテゴリフォルダ内の画像ファイル名はimage_0001.jpgとかついてます。airplanes(飛行機)にもdolphin(イルカ)にも同じファイル名がついてるので区別できなくて面倒です。そこで、下のようにカテゴリ名-数字.jpgというファイル名に変換します。caltech101/dolphin-0001.jpg一括して変換するpythonスクリプトです。rename_file)これで、9145枚の画像ファイルだけcaltech101フォルダにリネイムコピーされます。これでヒストグラムの抽出処理などやりやすくなります。yin_yangの10カテゴリの1番目から50番目の画像のみ抽出してcaltech10という500枚の画像からなるサブセットデータ集合を作ります。Wordsを用いた類似画像検索を実装していきます。Word)を求める全画像をヒストグラムに変換するです。ヒストグラムは後で使えるようにファイルに出力します。visual_words.cppまず、メイン関数から。0;}(1)局所特徴量の抽出と(3)ヒストグラムの抽出は長いのでそれぞれloadDescriptors()、calcHistograms()という関数にまとめてあります。クラスタリングは関数を作るほど長くないのでそのままです。K-meansクラスタリングは、cvKMeans2()というOpenCVの関数で簡単にできます。samplesは全画像の局所特徴量の行列(特徴ベクトル数x128次元)です。MAX_CLUSTERはクラスタ数で適当に500としています。Wordsは500個できます。labelsは今回は使いませんが、各特徴ベクトルがどのクラスタに割り当てられたかを表します。centroidは各クラスタのセントロイドベクトルが格納される500クラスタx128次元の行列です。局所特徴量を抽出caltech10の500枚の画像から局所特徴量SURFを抽出します。SURFの抽出方法は、SURFの抽出(2009/10/30)を参照してください。C++にはないと思います。似たような関数があるはずなので修正してください。Wordsを次元としたヒストグラムに変換する関数です。ヒストグラムはタブ区切り形式でhistograms.txtに出力されます。Wordsをkd-treeでインデキシングして検索速度を上げています。kd-treeを用いた高速化は、最近傍探索の高速化(2009/12/12)を参照してください。0;}作成されたヒストグラムファイルをはっときます。Wordsのヒストグラムを用いた類似画像検索では、histograms.txtを使って類似画像検索のプログラムを書いてみます。OpenCVは使わないのでくそ面倒なC++を使う必要ないですね(笑)Pythonでいきます。Intersectionを使います。Intersectionは、類似画像検索システムを作ろう(2009/10/3)を参照してください。Intersectionを計算し、類似度が高い順に上位10位を返すPythonスクリプトです。Library)を使うので別途インストールしてください。全画像のヒストグラムはあらかじめメモリにロードしておきます。main()実行すると、query?と聞いてくるのでcaltech10フォルダの画像ファイル名をクエリとして与えます。この結果としてクエリと類似する上位10個の画像が表示され、result.jpgにも保存します。accordion-0001.jpg1.000000caltech10/accordion-0001.jpg0.762976caltech10/accordion-0049.jpg0.757379caltech10/accordion-0025.jpg0.753379caltech10/accordion-0036.jpg0.748672caltech10/accordion-0042.jpg0.739771caltech10/accordion-0022.jpg0.737838caltech10/accordion-0002.jpg0.734934caltech10/cougar_face-0044.jpg0.733918caltech10/accordion-0037.jpg0.733821caltech10/accordion-0010.jpg実験結果では、いくつかのクエリ画像を与えて試してみます。左上にあるのがクエリ画像です。アコーディオンおー、1個変なの入っているけどちゃんと検索できてますね。Wordsを使う利点ですね。Wordsは色の類似性は見ていないので注意してください。クーガーとかダルメシアンで漫画っぽい絵でも類似判定できてるのはすごいです。ドル札も額面は違うのにちゃんと類似判定できてます。Wordsの学習に使った画像とテスト用の画像が同じのは評価としてはちょっとまずいと思います。評価したい人は学習用画像セットとテスト用画像セットは分けましょう。まとめ今回は、局所特徴量を用いた類似画像検索を作りました。上の結果を見ると何かすごいぞと思うのですが、実際はまったくダメダメなクエリ画像もありました。いうときにうまくいかないかはもう少し調査が必要です。Wordsの学習で使わなかったカテゴリ、たとえばイルカのクエリ画像を与えても類似画像は探せないと思います。Wordsにイルカの特徴が含まれておらずヒストグラムがうまく作れないはずです(まだ試してないのでやってみてください)。Wordsで汎用的な類似画像検索システムを構成するのは難しいのではないか?と推測しています。Wordsを類似画像検索に応用する研究は少ないように思います。Wordsは主に一般物体認識で使われているようです。クエリとして与えた画像のカテゴリ(アコーディオンとかはりねずみとか)を分類するタスクです。Machineを適用した研究をよく見かけます。一般物体認識も試してみたいですね。Wordsは、局所特徴量のクラスタリングが必要なわけですが、はっきり言ってK-meansがネックです。K-meansはすごい遅いです。bayonを使って画像からbag-of-keypointsを求める(この人のブログは愛読してます)を参考にCLUTOやbayonも検討していたのですが、いまいちデータの作り方がわかりませんでした・・・bayonは文書単語行列のようなスパース行列用のクラスタリングアルゴリズムだと理解したのですが、局所特徴量行列のような密な実数値ベクトルにも適用できるのでしょうか?bayonはもう少し詳しく調査してみる予定です。Wordsの図を参考にしました。Wordsを用いた画像クラスタリングの記事です。クラスタリングにK-meansではなくbayonを使っています。Wordsを使っています。目的はともかく(笑)として独自の目的に応用できるのはすごいです。他の記事も参考になります。学術論文にもこんなのがあります。Bag-of-keypointsのわかりやすい解説資料です。