Comments
Description
Transcript
「類似画像検索システムを作ろう」（抜粋）［PDFファイル／356KB］
2009-10-03 類似画像検索システムを作ろう OpenCV C++版の OpenCV を使ってカラーヒストグラムを用いた類似画像検索を実験してみました。バッチ処理などのス クリプトは Python を使ってますが、Perl でも Ruby でも似たような感じでできます。 指定した画像と類似した画像を検索するシステムは類似画像検索システムと言います。Google や Yahoo!のイ メージ検索は、クエリにキーワードを入れてキーワードに関連した画像を検索しますが、類似画像検索ではクエ リに画像を与えるのが特徴的です。この分野は、Content-Based Image Retrieval (CBIR)と呼ばれており、 最新のサーベイ論文（Datta,2008）を読むと 1990 年代前半とけっこう昔から研究されてます。 最新の手法では、色、形状、テクスチャ、特徴点などさまざまな特徴量を用いて類似度を判定するそうですが、 今回は、もっとも簡単な「色」を用いた類似画像検索を実験してみます。つまり、指定した画像に色が似ている画 像を検索します。 カラーヒストグラムの計算 カラーヒストグラムとは、画像中に各色が何ピクセルあるか数えて作成した棒グラフです。画像はカラーヒストグ ラムで表せます。たとえば、 のカラーヒストグラムを描画すると となります。各棒は特定の色が画像中に何ピクセルあるかをカウントした値です。上のヒストグラムで突き出てい るのは青色ですね！このヒストグラムの形がお互い似ているほど色が似た画像になります。カラーヒストグラム は、各ビンの Y 軸の値だけ保存しておけばよいので上の図の場合、64 次元ベクトルで表せます。 画像の減色 今回対象とするカラー画像は赤成分（R）、緑成分（G）、青成分（B）は各 8 ビット（256 通り）ですので、表示できる 色数は 256x256x256=16777216 通りになります。これは、色数があまりにも多すぎる（ヒストグラムの棒が 16777216 本、16777216 次元ベクトル）のでばっさり切って 64 色まで減色します。 減色は RGB の各成分を 4 等分して中央の代表値に置き換えることで行います。R が 4 通り、G が 4 通り、B が 4 通りなので表示できる色数は 4x4x4=64 通りになります。オリジナル画像の RGB は減色後の代表値に置き換 えます。たとえば、あるピクセルの輝度が RGB=(58, 150, 238)だったら 64 色 RGB=(32, 160, 224)に置き換え ます。 ※カラー画像の減色を改変 OpenCV を使って減色によって画像がどう変わるか試してみます。 左がオリジナルの画像で右が 64 色に減色した画像です。まあ 64 色あればそこそこ分かりますね！ ヒストグラムの計算 ヒストグラムは各色（64 色）が画像中に何ピクセルあるか数えたものです。先ほど、64 色に減色したので各色に 0 から 63 番まで番号をつけてヒストグラムのビン番号とします。たとえば、ピクセルの RGB 値が RGB=(58, 150, 238)だったら減色すると(redNo,greenNo,blueNo)=(0,2,3)になります（下の画像を参照）。この色を 0-63 までの ビン番号に変換するには、 redNo * 4 * 4 + greenNo * 4 + blueNo でできます。このように定義すると、(redNo,greenNo,blueNo) = (0,0,0)の色は 0 番、(redNo,greenNo,blueNo) = (3,3,3)の色は 63 番に割り当てられます。先ほどの(redNo,greenNo,blueNo) = (0,2,3)は 11 番になりますね。 次に、画像中の全ピクセルを走査して各色が何ピクセルあるか数えてカラーヒストグラムを作ります。 histogram[0]は 0 番目の色のピクセル数、histogram[63]は 63 番目の色のピクセル数です。 このヒストグラムは、検索時にいちいち再計算していては大変なのでファイルに保存しておきます。各数値を各 行に出力した 64 行のファイルです。 カラーヒストグラムの一括計算 次は、さっき作ったカラーヒストグラムを求める hist.exe を使って、画像からヒストグラムを一括計算します。フォ ルダ処理とかは C++より Python の方が楽なので Python スクリプトから hist.exe を実行するようにしました。 画像の類似度 これで全画像のカラーヒストグラムを計算してファイルへ格納できました。次は、いよいよ類似画像検索します。 画像間の類似度には Swain,1991 で提案されている Histogram Intersection を使ってみます。 Histogram Intersection は、2 つのカラーヒストグラムが与えられたときの類似度を与えます。類似度なので 2 つ のヒストグラムが似ているほど大きな値になります。定義は単純で 2 つのヒストグラムを H1,H2、ヒストグラム H の i 番目のビンの値を H[i]と定義すると です。min(X, Y)は X と Y の小さい方の値を返す関数です。つまり、2 つのヒストグラムの対応する各ビンの値で 小さい方を足し合わせていけばいいわけですね。どうしてこれでよいかは少し悩んでしまいますが・・・ヒストグラ ムはどこかが出っ張るとどこかが引っ込む性質があるのがミソかな？2 つのヒストグラムがまったく同じ場合に最 大値をとります。 ただし、ヒストグラムはピクセル数なので画像サイズが大きいほどヒストグラムが高くなってしまいます。そこで、 ピクセル数によって値が変わらないように下のように正規化します。正規化すると Histogram Intersection の値 は 0.0 から 1.0 の値になります。1.0 のとき 2 つのヒストグラムは完全に一致します。 類似画像検索 クエリとして与えた画像とその他全部の画像との Histogram Intersection を計算し、類似度が高い順に上位 10 位を返す Python スクリプトです。Python の画像処理ライブラリ PIL (Python Image Library)を使うので別途イン ストールしてください。全画像のヒストグラムはあらかじめメモリにロードしておきます。メモリに載せられないと結 果が返ってくるのがすごく遅くなると思います。もっと大量の画像になったらメモリに載るようにもっと高度な工夫 が必要になるかも。 実験 ためしに、下のイルカの画像（dolphin_image_0001.hst）をクエリとして似た画像を探して見ます。クエリ文字列 には.hst が必要なので注意してください。 query? > dolphin_image_0001.hst 1.000000 dolphin_image_0001.hst 0.833222 hawksbill_image_0087.hst 0.826443 dolphin_image_0008.hst 0.801974 watch_image_0033.hst 0.797467 airplanes_image_0332.hst 0.776834 revolver_image_0054.hst 0.767412 brain_image_0086.hst 0.764227 airplanes_image_0562.hst 0.760596 dolphin_image_0028.hst 0.754693 airplanes_image_0475.hst 左の数値はクエリと対象画像間の Histogram Intersection（類似度）です。大きいほど似ています。絵がないと わからないので上位 10 位まで画像を載せます。基本的に 1 位はクエリ画像と同じで類似度は 1.0 になります。 中に映っているものが同じかどうかは関係ありません。今は色だけで類似度を判断しているからです。まあ青だ し似ていると言えば似てますねー。 まとめ 今回は、色を用いた類似画像検索を作りました。 • RGB 以外の表色系（HSV とか）を用いる • 減色数の影響を見る • Histogram Intersection の代わりにユークリッド距離、Earth Mover's Distance (EMD)など別のヒストグラム 距離指標を使う • 大規模画像データベースを対象とした効率的な近傍検索アルゴリズムの導入、並列化 • いろいろなデータセットで試す とかいろいろ試したいことがあるので実験してみたいですねー。ただ、今回の結果から明らかなように色だけで は似ているとは思えない画像が入ってしまいます。今後は、色以外の特徴量を用いたり、画像セグメンテーショ ンに進む予定です。さらに一般物体認識に進むと画像中に映っている物体を識別して画像を検索できるかも？ 乞うご期待！ 参考文献 • 演習：画像の類似検索 • 類似画像検索に関する情報 • 画像検索について • 類似画像を見つけてくれる日本発画像検索エンジン Gazopa を試してみた • 似たもの画像をピックアップ・類似画像検索エンジン「TinEye」 • 初見：Google の「似た画像」検索 • 日立、数百万件の画像データから類似画像を 1 秒以内で検索する技術を開発 • Swain, M. J. and Ballard, D. H.: Color Indexing (PDF), International Journal of Computer Vision, 7(1), pp.11-32, 1991 • Datta, R. et al.: Image Retrieval: Ideas, Influences, and Trends of the New Age (PDF), ACM Computing Surveys, vol.40, 2008 関連リンク • Visual Words を用いた類似画像検索（2010/2/27） • 3 日で作る高速特定物体認識システム（2009/10/18） • 類似楽曲検索システムを作ろう（2012/10/14） *1:カラーヒストグラムではなく、Earth Mover's Distance（2012/8/4）という距離尺度を使うと可能です *2:このデータは一般物体認識タスクでよく使われるらしいので飛行機の写真を見せて airplanes と判定できれば正解とする んですかね？