類似画像検索システムを作ろう
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色減色画像を描画するOpenCVプログラムです。
#include "cv.h" #include "highgui.h" #include <cstdio> // 64色に減色 // R:4等分、G:4等分、B:4等分で4x4x4=64色 uchar decleaseColor(int value) { if (value < 64) { return 32; } else if (value < 128) { return 96; } else if (value < 196) { return 160; } else { return 224; } return 0; // 未到達 } int main(int argc, char **argv) { // 画像のロード IplImage *img = cvLoadImage("Data/dolphin_image_0001.jpg", CV_LOAD_IMAGE_COLOR); if (img == NULL) { printf("cannot load image\n"); return 1; } // 減色画像のメモリ確保 IplImage *outImage = cvCreateImage(cvGetSize(img), img->depth, 3); // 64色に減色 for (int y = 0; y < img->height; y++) { // y行目のデータの先頭ポインタを取得 uchar *pin = (uchar *)(img->imageData + y * img->widthStep); uchar *pout = (uchar *)(outImage->imageData + y * outImage->widthStep); for (int x = 0; x < img->width; x++) { int blue = pin[3*x+0]; int green = pin[3*x+1]; int red = pin[3*x+2]; // 64色に減色した画像を作成 pout[3*x+0] = decleaseColor(blue); pout[3*x+1] = decleaseColor(green); pout[3*x+2] = decleaseColor(red); } } // ウィンドウを作成 cvNamedWindow("Original Image", CV_WINDOW_AUTOSIZE); cvNamedWindow("Declease Color Image", CV_WINDOW_AUTOSIZE); // 画像を描画 cvShowImage("Original Image", img); cvShowImage("Declease Color Image", outImage); cvWaitKey(0); // 画像をファイルへ出力 cvSaveImage("original.jpg", img); cvSaveImage("color64.jpg", outImage); // 後始末 cvDestroyAllWindows(); cvReleaseImage(&img); cvReleaseImage(&outImage); return 0; }
k-Meansというクラスタリングアルゴリズムで減色するサンプルがありました。これは、今回の目的には合わないと思います。画像によって用いる64色（パレット）が異なってしまうからです。これでは、異なる画像間でカラーヒストグラムを比較できなくなってしまいます*1。
ヒストグラムの計算
ヒストグラムは各色（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番になりますね。
下は、オリジナル画像のRGB輝度値からヒストグラムのビン番号を求める関数です。
/** * オリジナル画像のRGBからヒストグラムのビン番号を計算 * @param[in] red 赤の輝度（0-255） * @param[in] green 緑の輝度（0-255） * @param[in] blue 青の輝度（0-255） * @return ヒストグラムのビン番号（64色カラーインデックス） */ int rgb2bin(int red, int green, int blue) { int redNo = red / 64; int greenNo = green / 64; int blueNo = blue / 64; return 16 * redNo + 4 * greenNo + blueNo; }
次に、画像中の全ピクセルを走査して各色が何ピクセルあるか数えてカラーヒストグラムを作ります。OpenCVで画像をロードし、画像の各ピクセル値にアクセスして、ビン番号に変換してから数え上げています。カラーヒストグラムを作るだけなら先ほどのようにわざわざ減色画像を作る必要はありません。
/** * ヒストグラムを計算 * @param[in] filename 画像ファイル名 * @param[out] histogram ヒストグラム * @return 正常終了で0、異常終了で-1 */ int calcHistogram(char *filename, int histogram[64]) { // ヒストグラムを初期化 for (int i = 0; i < 64; i++) { histogram[i] = 0; } // 画像のロード IplImage *img = cvLoadImage(filename, CV_LOAD_IMAGE_COLOR); if (img == NULL) { cerr << "cannot open image: " << filename << endl; return -1; } // 64色に減色してヒストグラムを計算 for (int y = 0; y < img->height; y++) { // y行目のデータの先頭ポインタを取得 uchar *pin = (uchar *)(img->imageData + y * img->widthStep); for (int x = 0; x < img->width; x++) { int blue = pin[3*x+0]; int green = pin[3*x+1]; int red = pin[3*x+2]; // カラー値（0-63）をカウント int bin = rgb2bin(red, green, blue); histogram[bin] += 1; } } cvReleaseImage(&img); return 0; }
この関数を実行するとhistogramには各ビンのピクセル数が格納されます。カラーヒストグラムは64次元ベクトルです。histogram[0]は0番目の色のピクセル数、histogram[63]は63番目の色のピクセル数です。
このヒストグラムは、検索時にいちいち再計算していては大変なのでファイルに保存しておきます。各数値を各行に出力した64行のファイルです。
/** * ヒストグラムをファイルに出力 * @param[in] filename 出力ファイル名 * @param[in] histogram ヒストグラム * @return 正常終了で0、異常終了で-1 */ int writeHistogram(char *filename, int histogram[64]) { ofstream outFile(filename); if (outFile.fail()) { cerr << "cannot open file: " << filename << endl; return -1; } for (int i = 0; i < 64; i++) { outFile << histogram[i] << endl; } outFile.close(); return 0; }
以上の手続きをまとめたメイン関数です。
/** * メイン関数 hist.exe [入力画像ファイル名] [出力ヒストグラムファイル名] * @param[in] argc * @param[out] argv * @return 正常終了で0、異常終了で-1 */ int main(int argc, char **argv) { int ret; if (argc < 2) { cerr << "usage: hist.exe [image file] [hist file]" << endl; return -1; } char *imageFile = argv[1]; char *histFile = argv[2]; cout << imageFile << " -> " << histFile; // ヒストグラムを計算 int histogram[64]; ret = calcHistogram(imageFile, histogram); if (ret < 0) { cerr << "cannot calc histogram" << endl; return -1; } // ヒストグラムをファイルに出力 ret = writeHistogram(histFile, histogram); if (ret < 0) { cerr << "cannot write histogram" << endl; return -1; } cout << " ... OK" << endl; return 0; }
コンパイルするとexeファイルができます。（注）OpenCVのインストールとリンカの設定が必要です。EclipseでOpenCV（2009/10/16）参照。
hist.exe dolphin_image_0001.jpg dolphin_image_0001.hst
のように使います。dolphin_image_0001.hstはヒストグラムを格納するファイル名です。
画像データセットを用意
実験で使う画像データセットを用意します。自分の持っている画像データやFlickrから集めてもよいと思いますが、有名なテストデータがいくつか公開されているのでそれを使います。これらのデータセットは、一般物体認識タスクのデータセットなのですがまあいいかな？もし類似画像検索用のデータをご存知でしたらコメントいただけるとうれしいです。
この実験では、Caltech 101を使いました。131MB、9145画像とデータ規模も手軽です。本当は、150万枚のtinyimagesで試したいけどもっと高度な検索手法を使わないと太刀打ちできないですねー。ダウンロードしたデータを解凍すると101_ObjectCategoriesというフォルダの中に101個のカテゴリフォルダ（102個あるけどBACKGROUND_Googleが余計？）があり、その中に画像がたくさんあります。たとえば、airplanesフォルダ（カテゴリ）には飛行機の写真がたくさん入ってます*2。サイズはそれぞれ異なりますが、大体300x300くらいでしょうか？いろんな画像があって見てるだけで楽しいです。
（注）以下、BACKGROUND_GoogleとFacesフォルダは削除しています。
フォルダごとに画像ファイルが分散されてるので一括処理しやすいようにcaltech101というフォルダに画像ファイルだけまとめます。また各カテゴリフォルダ内の画像ファイル名はimage_0001.jpgとかついてます。airplanes（飛行機）にもdolphin（イルカ）にも同じファイル名がついてるので区別できなくて面倒です。そこで、下のように変換します。
airplanes/image_0001.jpg -> caltech101/airplanes_image_0001.jpg
dolphin/image_0001.jpg -> caltech101/dolphin_image_0001.jpg
一括して変換するpythonスクリプトです。
#coding:utf-8 import codecs import os import shutil TARGET = "101_ObjectCategories" OUTDIR = "caltech101" for category in os.listdir(TARGET): for file in os.listdir("%s/%s" % (TARGET, category)): image_file = "%s/%s/%s" % (TARGET, category, file) # 101_ObjectCategories/airplanes/image_0001.jpg rename_file = "%s/%s_%s" % (OUTDIR, category, file) # caltech101/airplanes_image_0001.jpg print "%s -> %s" % (image_file, rename_file) shutil.copyfile(image_file, rename_file)
これで、9145枚の画像ファイルだけcaltech101フォルダにリネイムコピーされます。これでヒストグラムの抽出処理などやりやすくなります。
カラーヒストグラムの一括計算
次は、さっき作ったカラーヒストグラムを求めるhist.exeを使って、画像からヒストグラムを一括計算します。フォルダ処理とかはC++よりPythonの方が楽なのでPythonスクリプトからhist.exeを実行するようにしました。histフォルダを作成してから実行するとcaltech101フォルダの全画像のヒストグラムファイルが作られます。ファイル名は、xxx.jpgならxxx.hstです。うちのマシンは、CPUがCore i7 8コア、メモリが3GBですが、9000枚の画像のヒストグラム変換処理に25分40秒かかりました。
#coding:utf-8 import codecs import os TARGET = "caltech101" OUTDIR = "hist" for file in os.listdir(TARGET): image_file = "%s/%s" % (TARGET, file) # caltech101/xxx.jpg hist_file = "%s/%s.hst" % (OUTDIR, file[:-4]) # hist/xxx.hst os.system("hist.exe %s %s" % (image_file, hist_file))
画像の類似度
これで全画像のカラーヒストグラムを計算してファイルへ格納できました。次は、いよいよ類似画像検索します。画像間の類似度には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)を使うので別途インストールしてください。全画像のヒストグラムはあらかじめメモリにロードしておきます。メモリに載せられないと結果が返ってくるのがすごく遅くなると思います。もっと大量の画像になったらメモリに載るようにもっと高度な工夫が必要になるかも。
#coding:utf-8 import codecs import os import sys from PIL import Image IMAGE_DIR = "caltech101" HIST_DIR = "hist" # ヒストグラムをロードする def load_hist(): hist = {} for file in os.listdir(HIST_DIR): h = [] print "load %s ... " % file, fp = open("%s/%s" % (HIST_DIR, file), "r") for line in fp: line = line.rstrip() h.append(int(line)) fp.close() hist[file] = h print "OK" return hist # 正規化Histogram Intersectionを計算する def calc_hist_intersection(hist1, hist2): total = 0 for i in range(len(hist1)): total += min(hist1[i], hist2[i]) return float(total) / sum(hist1) def main(): hist = load_hist() while True: # クエリとなるヒストグラムファイル名を入力 query_file = raw_input("query? > ") # 終了 if query_file == "quit": break # 存在しないヒストグラムファイル名のときは戻る if not hist.has_key(query_file): print "no histogram" continue # クエリと他の全画像の間で類似度を計算 result = [] query_hist = hist[query_file] for target_file in hist.keys(): target_hist = hist[target_file] d = calc_hist_intersection(query_hist, target_hist) result.append((d, target_file)) # 類似度の大きい順にソート result.sort(reverse=True) # 上位10位を表示（1位はクエリ画像） # PILを使って300x300を1単位として2行5列で10個の画像を並べて描画 p = 0 canvas = Image.new("RGB", (1500, 600), (255,255,255)) # 白いキャンバス for score, filename in result[0:10]: print "%f\t%s" % (score, filename) img = Image.open("caltech101/" + filename[:-4] + ".jpg") pos = (300*(p%5), 300*(p/5)) canvas.paste(img, pos) p += 1 canvas.resize((1500/2, 600/2)) canvas.show() canvas.save(query_file + ".jpg", "JPEG") if __name__ == "__main__": main()
実験
ためしに、下のイルカの画像（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と判定できれば正解とするんですかね？
