雑記/2015-07-05

2015-7-5[日] 簡易類似画像判定のメモ

別件ググってて類似画検索のネタみかけて、だけど特定のモノを(綿密に)探すタイプで、どちらかというと大量のものを分類したいなあ...と、一応 以前 かなり簡易だけれど そういうものを作りかけて放置していたので それをネタに。

キッカケは忘れたけれど、以下のような近似画チェックを思いついて (でもこれは良くない例)

1. 画像の全画素の輝度の平均と、画像を縦横２等分４分割した領域各々での輝度の平均を求め、各領域の平均と全体の平均を比べ、明るければ1 でなければ0 で4bitの値を作る.
2. 4分割した各領域を対象に、先と同様に その領域の輝度平均と さらにそこを４分割した各領域の輝度平均を比較して 4bit *4エリアの16bitを得る.
3. さらに同様に(16分割されてる)各領域を４分割して 4bit * 4*4エリア=64bitを得る.(場合によってはさらにもう一段階....)
4. 広い順に上位に詰めて 4+16+64=84bit値を作り、その84bit値をキーにソートすればそこそこ同じ(類似)画像が近くに並ぶんじゃね？と(実際には輝度yだけじゃなく u,vも)

思いついた時はいいアイデアのような気がして作り始めたけれど多少面倒くさくて、実はもう似たようなものがあるかも、とググれば案の定、もっとシンプルで良いものがあった。

こちら等 で 紹介されてる Avarage Hash 法.

• 画像を縦横8等分64分割し、分割された各領域の輝度の平均と、画像全体の輝度の平均と比べ、明るいか等しければ1、暗ければ 0で 64bit の値(ビットパターン)を得る。

画像を8x8サイズに縮小して上記のような64bit整数値(ビットパターン)を得るだけ。再帰する必要なんてなかった。
今どきの64bitCPUだと すこぶる低コストで画像同士の比較ができる。32bitCPUでも64を 32bit値 ２つに分けて処理できる類なので かなり軽い。

(以下ビット演算慣れした人には釈迦に説法の類だけど)

画像 a と画像 b の 上記明暗の64ビットパターンを a.ptn と b.ptn とすると、排他的論理和(xor)を用いて

　uint64_t d_ptn = a.ptn ^ b.ptn;

のようにして差異のビットパターン d_ptn を得られる。xorの結果は違う部分のビットが1になっているので、d_ptn 中の 1 になってるbit数が少ないほど 類似している(可能性が高い)ということになる。

64bit値中の1のビットの数を数えるのは、今どきの64bit CPUだと、

　__popcnt64 (VC) や __builtin_popcountll (GCC)

でコンパイラがネイティブなマシンコードにインライン展開してくれたりする。
そういうネイティブのがなくてもこちらで紹介されてるpopcount(numofbits5) 処理で

unsigned popcnt64(uint64_t bits) {
   bits = (bits & 0x5555555555555555UL) + ((bits >> 1) & 0x5555555555555555UL);
   bits = (bits & 0x3333333333333333UL) + ((bits >> 2) & 0x3333333333333333UL);
   bits = (bits & 0x0f0f0f0f0f0f0f0fUL) + ((bits >> 4) & 0x0f0f0f0f0f0f0f0fUL);
   bits = (bits & 0x00ff00ff00ff00ffUL) + ((bits >> 8) & 0x00ff00ff00ff00ffUL);
   bits = (bits & 0x0000ffff0000ffffUL) + ((bits >> 16) & 0x0000ffff0000ffffUL);
   return (unsigned)(bits) + (unsigned)(bits >> 32);
}

な感じで結構高速に求められる。
ので 2枚の絵の類似判定の雰囲気は (a.ptn, b.ptn は画像ロード時に予め作成してるとして)

if (popcnt64(a.ptn ^ b.ptn) <= 類似とみなす差異ビット数)
    類似画像の処理
else
    別画像の処理

１回当たりのチェックがこれだけ低コストならば、数千(万)程度の画像数なら、総当りチェックしても 割りと実用的な(ガマンできそうな)速度になりそうで、試してみるとそこそこいい感じだった。

総当りして、違いが少ないもの同士をリンクしておいて、後でリンクされたグループ内で調整して並べなおして... 等ちょっとめんどくさいけれど。

※ 実のところ 総当りチェックせず単純にビットパターンでソートだけでも 結構よかったりする。同一とみなしたもの(8x8縮小画同士の差が0)が連続するだけでなく、画像の上のほうが一緒で違いが下のほうにしかない場合なんかも近くに並ぶので…… もちろん上側が違って下側が似てる場合などは離れてしまっているのだけど。
(※左上から右下へ横縦繰返でスキャンして64ビットを作ってる場合)

で、どの程度を近似とみなすか、が面倒、てか肝。 同一判定なら Average Hash 法の説明で書かれている7%ほど(64点だと 4,5個)でよいかもだろうけど、も少し増やすと同一ではないけどちょっと違う類似画像もひっかかりやすくなって....

それなりな結果が出てると欲が出てきてしまうもので、類似判定の精度上げるために、さらに以下のようなチェック等追加

1. 画像のアスペクト比がある程度以上違えば別画像
2. (以下、先にチェックした8x8ビットパターンのうち 違うと判定したビット以外の部分をさらにチェックする形で)
3. yuvの y(輝度)だけでなく u, v についても8x8で同様にチェック
4. u,vのビットパターンが オール1の時はモノクロ化画像なので考慮
5. 輝度について 明るい部分のみ・暗い部分のみをそれぞれの輝度平均を用いて明暗ビットパターンを作ってチェック
6. 輝度16x16ビットパターンも補助的に利用.
7. ビットパターンの違いが少なくも多くもない微妙な場合は、(ビット化する前の)輝度ピクセル同士の差もチェック

等等 ごちゃごちゃ追加して 判定 重くなってくるわけですが。(の わりにはまだまだ誤判定有)

ちなみに 16x16パターンについては、同一画の判定としては8x8より精度よさそうだけど、類似物を集めるという面ではシビアになりすぎるのか分が悪い感じだった。ので補助的に利用。速度を思えば無しのほうがよさげだけど、この判定でマシになるケースもあるし、で。逆に4x4は荒すぎて結局8x8の判定便りになるぽいから あまり意味なく(でも最初にざっくりとしたソートするのに使ったかも)
※ そもそも8x8(16x16)縮小画での比較なので、近似/類似でなく ちゃんと同一を判定するのは困難なんだけども

こういう判定は面白いけれど難しい。いろいろサンプル食わして それなりな線を目指すのだけどサンプル違うとガラッと誤判定多かったりね、手間の割には精度よくならないわな。根本的に簡易なので、もっとよくしたいなら別のアルゴリズムにする/を併用する、ほうがよさそう。けどググって出てくる本格的な類似画判定のアルゴリズムは速度を思うと……(だし、そこまで気合入れて類似画分類処理を作りたいわけでもなく)

お試しプログラム

と、ま、以前 試しに作ってみてたコマンドライン・ツールは これ。
win64用とwin32用 の exe のみ。
※追記2016-08-25: ソース同梱のzipに差し替えました。

指定したjpegファイル群を調べて、類似のあったファイル名だけ表示したり、全ファイルを類似情報を元に名前付けて copy や move するバッチ生成したり、類似順にファイルの日付を付直したり出来ます。
※いまどきの類似画検索/分類ツール使ったことないので使い物になるかは知らない

変換例。左or上がソース、右or下が類似並替結果。フォルダのキャプチャは縦横50%縮小してわかりにくいけれど、変換結果はバッチ出力して、名前付け替えてのコピー。

※画像は 株式会社ブリリアントサービスのフリー素材 (タイトル：ジュエルセイバーFREE URL：http://www.jewel-s.jp/) のものを使用。 jewel-s-free100j より適当に13枚を選んでα無 jpg画像にし類似画像の順番がバラけるよう適当に変名した。また うち１枚を、拡大、モノクロ化、文字書込、したものも追加。(ruig-smp.zip)

処理速度については、i7-3770(3.4GHz) mem32GB の win8.1x64 マシンで、適当に寄せ集めたjpeg画像自分で撮った写真や net で拾ったイラストや写真等)を HDD(3TB)に置いて win64用exeで試したところ、

と いう感じだった。
(続けざまに同じ変換をするとosのファイルキャッシュが効いて2回目のファイル読込2.2秒ほど)

並替準備――画像縮小してソート・キーになるビットパターン生成等――はちょい負荷あるが、 並替自体は 許容できそうな範囲(ただ類似画の量が多いともっと増える)、 主にjpg展開+ファイル読込に時間がかかっている模様。

jpg 展開は libjpeg-turbo を用いて、また、ある程度巨大画像については サムネール機能利用して処理短縮を図っているけどこの時間。(jpg は8x8ピクセルのブロック単位で扱う工程があって最後まできっちり展開せず処理端折って縦横8分の1(1/64縮小)の荒い画像を得ることができる。ただ王道な縮小と誤差はあるので、その誤差も無視できる程度に1/64画像が大きい――比較用8x8画よりも2桁ほど広い――場合のみ利用) (※libjpeg側のサムネール取得関数は1/8とは限ってないので も少し工夫あるのかもしれない)

単純に1スレッドでファイルごとに読込→展開→並替準備をシーケンシャルに繰り返し処理してるので、そのへん並列化できれば少しはマシになりそうな気はする。(劇的には無理だろうけど。ただ画像ビュワー等で自前でサムネール生成保存するような場合なら一緒に類似ソート・キーも保存しておけば そこそこ使えそうな手段な気もする)

あ、と、実際にソート結果を反映したrename(move)したりcopyしたりは生成したバッチで行うので それなりに時間かかります。