PHPで画像の類似度判定のできるライブラリ

最近、大量の画像を分類する趣味をこなしていて、どうも重複画像があるような気がしていたのだが、僕の脳みそでは膨大な画像の中から類似の画像を探すことが出来ない。
そこで、どうにかして類似画像検索が出来ないものかと思っていた。

ImgSeek

そこで検索すると、まず最初に引っかかってくるのはImgSeekであろう。基本的にはLinuxのGUIで動作する画像管理ソフトで、類似画像検索ができるというものだ。Pythonで書かれているが、これのサーバ版というものもあって、それがisk-daemonである。
だが、これがまた安定しない。

数千単位で画像を登録すると、メモリを延々と消費し続ける状態になってしまったり、なにもエラーを吐かずに落ちてしまったりする。
１ファイルの中に複数のDBを作れるので、DBを分割して、１DBあたりの画像数を減らしてみたりもしたが、DB数が50程度を超えた状態で再起動すると、延々とメモリを食いつぶしプロセスが落ちてしまった。

Pythonのコードを追うのも非常に面倒くさかったので、なんか他に方法はないものかとずっと探していた。

libpuzzle

で、偶然見つけたのが、libpuzzleである。名前からして、パズルゲームを作るためのライブラリのように思えてしまうが、ところがどっこい、PHPで画像の近似度判定ができるライブラリなのである。
しかも、このライブラリは
・ImageMagickを使っていない。GDを使う
・BSDライセンスを採用しており、商用利用も可能
・PHPの拡張として実装されており、そのまま使える
と、（僕にとって）良いことづくめなのである！

インストールもとっても簡単！
コンパイルにGDが必要なので、事前にインストールしておく。もちろん、php-develないし、php-devもインストールしておくように。
詳しいことは Libpuzzle with PHP に書いてある。

$ # 依存ライブラリをインストール
$ su
# yum install gd-devel
# # apt-get install libgd-dev
# exit
$ # libpuzzleをダウンロード
$ wget http://download.pureftpd.org/pub/pure-ftpd/misc/libpuzzle/releases/libpuzzle-0.11.tar.bz2
$ tar jxvf libpuzzle-0.11.tar.bz2
$ cd libpuzzle-0.11
$ # libpuzzle本体をまずインストール
$ ./configure
$ make
$ su
# make install
# exit
$ # PHP拡張をインストール
$ cd php/libpuzzle
$ phpize
$ ./configure --with-libpuzzle
$ make
$ su
# make install
# exit
$ # iniファイルに extension=libpuzzle.so を書き足す
$ # CentOSの場合は /etc/php.d にiniファイルがいっぱいあるので、そこに新規ファイルを作る
$ su
# vim /etc/php.d/libpuzzle.ini
# exit
$ cat /etc/php.d/libpuzzle.ini
extension=libpuzzle.so
$

とってもかんたん！

使ってみよう

libpuzzleは基本的に2つのファイルの近似度を判定するライブラリである。
したがって、使い方は以下のようになる。

<?php
// 1つめの画像ファイルのシグネチャを作る
$cvec1 = puzzle_fill_cvec_from_file('img1.jpg');
// 2つめの画像ファイルのシグネチャを作る
$cvec2 = puzzle_fill_cvec_from_file('img2.jpg');

// ２つのシグネチャから、近似度を判定する
$d = puzzle_vector_normalized_distance($cvec1, $cvec2);

// 0に近いほど、似ているということ
if($d < 0.1) echo "そっくりです！";
else if($d < 0.3) echo "かなり似ています";
else if($d < 0.5) echo "似ている、かも？";
else echo "どうやらまったく異なる画像のようです";

画像データベースを構築してみよう

isk-daemonには「似ている画像のリストを返す」命令があったが、libpuzzleには無い。
ならばどうするのかというと、１つ１つ比較していくより他に手がない。
かといって毎回毎回シグネチャを生成していたのでは重くてしょうがない。
そこで、シグネチャをMySQLなどのDBとか、memcachedとか、とにかくどこかに置いておくのが良い。

ちなみに、puzzle_fill_cvec_from_fileで返されるのは文字列なので、MySQLなどでBLOBなカラムを作って、そのままぶち込んでも、害はない。
base64_encodeしてぶち込んでも、もちろん害はない。
$str = base64_encode(gzdeflate($cvec)); とかやっても、もちろん平気だ。
そして、最後に、libpuzzleにはpuzzle_compress_cvecという関数がある。
これをやると、gzdeflateしてbase64_encodeしたものに近い文字列が返ってくる。

なお、うちのCoreSolo（初代Intel Mac mini）な環境では、
シグネチャの生成x100画像で大体1分～1分半。
近似度判定x10000回で大体２～３秒だったので、
シグネチャをどっかに保存しておけば、10万画像の線形比較くらいなら許容範囲ではないかと思われる。

ちなみに内部的には
・画像を9分割して
・それぞれの特徴を分析し、
・ベクトルを生成する（ベクター画像のことではない。もっと数学的なベクトルのこと）
・比較の際には、上記のベクトルの距離を判定する。
ということだそうなので、線形ベクトルに詳しい人なんかは大量のベクトルを距離順に並べ替える、なんていうアルゴリズムを作れば、数百万件の画像でも近似画像が簡単に検索できるようになるかもしれない。
うちの環境では17.5万件の画像の中から類似画像を探すのに、6.8秒ほどかかっている。

僕の目で探すより数万倍速いけどね！！

2011/05/15 追記
CentOSのepelリポジトリにphp-libpuzzleっていうパッケージがある・・・
残念ながらPHP5.3用はまだ無い模様。

プログラミング Linux, PHP