Google画像検索のような類似画像を検索する方法を調べてみた。
ぱっと思いつくのは、色や形状などの特徴量を比較し、近似しているものを調べていく方法だ。
この手の情報やライブラリは、けっこう出回っているので、一番お手軽にできそうだ。
他のアプローチとしては、特徴量が近似していないものを探しいくことで、類似性を判定する方法もあるそうだ。
画像同士をつきあわせて類似性を判定するのではなく、彼らは問題をまったく別の角度から捉えた。彼らの方法では、ターゲットの画像(A)を大量のランダムな画像と比較して、それらと当の画像との、もっとも著しい違いを記録する(Ra)。そして、もう一つのターゲット画像(B)に対しても同じ記録を作成する(Rb)。この、RaとRbがほぼ同じなら、画像AとBは類似性が高いだろう。
重要なのは'類似'ではなく'違い'だ–まったく新しい着想に基づく高精度の画像検索アルゴリズム | TechCrunch Japan
画像検索とは
テキストキーワードを用いる方法を、TBIR（Text Based Image Retrieval）、
画像特徴を用いる方法を、CBIR（Content Based Image Retrieval）と呼ぶみたいだ。
TBIRは、画像にキーワードを紐付けて、そのキーワードに類似している画像を検索する方法とのこと。
今回はCBIRについて調べていきたいと思う。
形状特徴を利用する方法
検索していると「モノクロ画像検索のための形状特徴」という論文を発見した。
SobelやCannyフィルタを使ってエッジの抽出をおこなった画像を、3×3に分割し、各領域のエッジ割合を比較する、という方法のようだ。
気になったのがaHash（AverageHash）という方法だ。
この手法は「Perceptual Hash」という、「比較可能なハッシュ」を生成するための一手法です。
一般的にMD5やSHA1などのハッシュ値は、1バイトでもデータが違えば、まったく違うハッシュ値を返してきますが、「Perceptual Hash」は似たようなデータには似たようなハッシュ値を返してきます。
簡単な画像の類似度計算手法「Average Hash」 » Untitled Blog
どんな方法だろうと見てみると、グレースケール化した画像を8×8ピクセルに縮小化し、色の濃淡でビット列を作成する、ということらしい。
「Average Hash」は以下のような手順で生成することができます。
画像のサイズを縮小 (ブログによれば8×8に縮小)
色をグレースケールにする
画像の各ビクセルを使って色の平均値を計算
それぞれのピクセルで色の濃淡を調べ、その色が平均値よりも濃い場合は1を、薄い場合は0を設定する
結果的に8×8=64ビットのビット列ができあがる
pHashというものもあるらしく、DCT（離散コサイン変換）を使っているらしい。
こちらはライブラリ化しており、下記のサイトからダウンロードできるが、ライセンスはGPLとのこと。
pHash.org: Home of pHash, the open source perceptual hash library
libpuzzle
libpuzzleというライブラリが有名なようで、使っている記事がたくさんヒットした。
PHPから簡単に使えるようになっているらしく、BSDライセンスで扱いやすそうだ。
ラッパーを作れば他の言語からも利用できると思う。
Libpuzzle – A library to find similar pictures
しかもけっこう速そうだ。
なお、うちのCoreSolo（初代Intel Mac mini）な環境では、
シグネチャの生成x100画像で大体1分～1分半。
近似度判定x10000回で大体２～３秒だったので、
シグネチャをどっかに保存しておけば、10万画像の線形比較くらいなら許容範囲ではないかと思われる。