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

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

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

一般的にMD5SHA1などのハッシュ値は、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回で大体2~3秒だったので、
シグネチャをどっかに保存しておけば、10万画像の線形比較くらいなら許容範囲ではないかと思われる。

激ニコぷんぷん丸のソースコード公開

先日リリースしたiPhoneアプリ「激ニコぷんぷん丸」のソースコードをGitHubにアップした。
特にいいアイデアも浮かばなかったので、多少インパクトがあって実績になりそうなものを作った。
が…色々迷走した挙句、よく分からないアプリが完成した。
使い道がないのでソースコードをGitHubにアップすることにした。
テストコードも書いてなく、あまりいいコードではないけど何かの参考になれば…。

Pinterestのようなインタフェースで、ツイッター上に流れているニコ動を表示するアプリ。
ツイッター上の動画情報は、ツイッターのストリームAPIを使ってリアルタイムに取得している。
クライアント部はObjective-C、サーバ部はRails3(Unicorn + NginX) + MySQL + Redisで出来ている。

とりあえず、クライアントアプリだけ。
pontago/objc-NicoTwi · GitHub

iOS7対応

面倒くさがりなのでブログを書く頻度が少なかったのだが、なるべく細かい記事でも書くことにした。
iOS7がリリースしてしばらく経つのだが、ようやくひと通りiOS7対応が終わった。
後手後手の対応で、アップデートが遅くなってしまいスミマセン。

今回はメジャーアップデートということもあり、大幅なUI変更が加わった。
流行のフラットUIに変わったことで、iOS6以前と両方サポートするアプリは少し大変かもしれない。

ステータスバーが一体化した

一番やっかいな問題が、ステータスバーの一体化だ。
ステータスバーをアプリから操作(色の変更や透過、表示・非表示)出来るようになったため、UINavigationBarなどと違和感なく一体化させることが可能になった。

今まではステータスバーを除いた座標から取得出来ていたのだが、iOS7からはステータスバーの20px分が含まれなくなった。このせいでデザインが崩れてしまうアプリがけっこうあると思う。

手っ取り早いのは、UIWindowをステータスバー分ずらしてしまうことだ。こうすることでiOS6以前と同じように処理することができる。

    if ([[UIDevice currentDevice].systemVersion floatValue] >= 7.0f) {
[[UIApplication sharedApplication] setStatusBarStyle:UIStatusBarStyleLightContent];
self.window.clipsToBounds = YES;
self.window.frame = CGRectMake(0, 20.0f, self.window.frame.size.width, self.window.frame.size.height - 20.0f);
self.window.bounds = CGRectMake(0, 20.0f, self.window.frame.size.width, self.window.frame.size.height);
}

UINavigationBarのbarTintColorやtintColorを変更することで、ステータスバーの色も変わる。

Objective-C – iOS7でナビゲーションバーやステータスバーの文字色を変える – Qiita [キータ]

UINavigationBarの戻るが変わった

前のビューに戻るときのボタンが「<」みたいなのになった。
そのため、backBarButtonItemなどにイメージ付きのUIBarButtonItemを設定すると、「<」分ズレて表示がおかしくなる。

僕は手っ取り早く、backBarButtonItemではなく、leftBarButtonItemに設定してしまった。
具体的には、UINavigationControllerを派生したクラスを作成し、pushViewControllerをオーバーロードする。
その中で、viewControllersをカウントし、0以上の場合(一つ以上ビューがプッシュされている)に、戻るボタンを設定する。例えば以下のようなコードになる。

- (void)pushViewController:(UIViewController *)viewController animated:(BOOL)animated {
if ([self.viewControllers count] > 0) {
viewController.navigationItem.leftBarButtonItem = [[UIBarButtonItem alloc]
initWithImage:[UIImage imageNamed:@"back.png"] style:UIBarButtonItemStylePlain
target:self action:@selector(popViewControllerAnimated_)];
}
[super pushViewController:viewController animated:animated];
}
- (void)popViewControllerAnimated_ {
[self popViewControllerAnimated:YES];
}

カスタムUIBarButtonItemのアイコン色が反映されない

iOS7になってから、ボタンに設定した画像がtinColor(青色とか)で塗りつぶされるようになった。
UIBarButtonItem内にUIButtonをカスタムビューとして設定していたのだが、tintColorで塗りつぶされなかった。
どうやら、UIButtonの種類が、UIButtonTypeSystemまたは、UIButtonTypeRoundedRectの場合にのみtinColorで塗りつぶしされるようだ。

EZ-NET: iOS 7 では標準ボタンの画像が tintColor で塗りつぶされる : iPhone プログラミング

UITableViewのセル背景色が反映されない

UITableViewCellの背景色は、デフォルトで白?になったようだ。
変更する方法は、tableView:willDisplayCell:forRowAtIndexPath:か、tableView:cellForRowAtIndexPath:のどちらかから、backgroundColorをclearColor(もしくは好きな色)に変更するといい。

- (void)tableView:(UITableView *)tableView willDisplayCell:(UITableViewCell *)cell forRowAtIndexPath:(NSIndexPath *)indexPath {
cell.backgroundColor = [UIColor clearColor];
}

疲れたのでこのへんで。