類似画像を検索する方法を調べみた その1

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フィルタを使ってエッジの抽出をおこなった画像を、3x3に分割し、各領域のエッジ割合を比較する、という方法のようだ。

気になったのがaHash（AverageHash）という方法だ。

この手法は「Perceptual Hash」という、「比較可能なハッシュ」を生成するための一手法です。

一般的にMD5やSHA1などのハッシュ値は、1バイトでもデータが違えば、まったく違うハッシュ値を返してきますが、「Perceptual Hash」は似たようなデータには似たようなハッシュ値を返してきます。

簡単な画像の類似度計算手法「Average Hash」 » Untitled Blog

どんな方法だろうと見てみると、グレースケール化した画像を8x8ピクセルに縮小化し、色の濃淡でビット列を作成する、ということらしい。

「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万画像の線形比較くらいなら許容範囲ではないかと思われる。