まだプログラマーですが何か?

プログラマーネタとアスリートネタ中心。たまに作成したウェブサービス関連の話も http://twitter.com/dotnsf

タグ:similar

2年前に書いたこのブログエントリの続きのような内容です:
類似画像検索とカラーヒストグラム


類似画像検索を実現するアルゴリズムを調べています。上記のブログエントリでは「カラーヒストグラム」と呼ばれる比較的簡単な方法を紹介しました。今回は Average Hash と呼ばれる方法を紹介します。


まず、この方法は名前に "Hash" というキーワードがついています。一般的なハッシュ(ハッシュ値、ハッシュ関数)では入力値が少しでも異なっていると出力値が全然別の値になる、という特徴があり、その特徴をいかしてパスワード(のハッシュ)を安全に保存したり、ブロックチェーンに応用されたりしています。

ただ今回紹介する Average Hash アルゴリズムで使われるハッシュはその点で意味合いが少し異なり、入力されたデータが似ていた場合に似た値を返すようなハッシュ関数を定義します。このようなハッシュ関数を使って、用意された画像のハッシュ値をあらかじめ求めておきます。そして類似画像を探したい画像についても同じハッシュ関数でハッシュ値を求め、そのハッシュ値が似ている画像は入力データが似ているはずと判断して回答の候補とする、という考え方に基づいた類似画像検索アルゴリズムです。つまり画像として類似しているかどうかを、比較演算が容易なハッシュ値の差で判断しよう、というものです。


より具体的にアルゴリズムを紹介します。例えばハッシュ関数を以下のように定義したとします:
  • 画像のバイナリデータをハッシュ関数の入力値とする
  • nxn のサイズを持つ整数配列がハッシュ関数の出力値とする。なおnは整数値とする
  • ハッシュ関数内ではまず画像を正規化する。具体的には入力画像を縦nピクセル、横nピクセルにリサイズし(画素数はnxn)、更にグレースケール変換する
  • 次にnxnにグレースケールされた画像の各ピクセルの色の濃さ(0~255)を調べ、その値の平均値 avg を求める
  • 再度nxnにグレースケールされた画像の各ピクセルの色の濃さを調べ、その値が avg 以上であればそのピクセルの値は 1 、avg 未満であれば 0 とみなす。これをnxnピクセル分求めて配列にする
  • この配列をハッシュ関数の出力値とする

これだけだと理解しにくいと思ったのでもう少し詳しく順を追って説明します。なお以下の例では n = 16 の例を紹介します。

ハッシュ関数への入力データを以下の画像とします(ちなみにいらすとや様からの画像で、元のサイズは 737x800 ピクセルです):
2019051701



ハッシュ関数ではこの入力画像をまず 16x16 にリサイズし、かつグレースケール化して正規化します。この時点で画像のピクセル数は (16x16=)256 です:
2019051702


この (16x16=)256 個のピクセルを左上から1つずつ取り出して RGB 値を調べます。この値は 0 から 255 の間の整数値で、0 に近いほど黒っぽく、255 に近いほど白っぽいことを意味しています。実際には 16 行ありますが、最初の3行はこのような感じでした:
2019051705


こうして 256 個のピクセルの RGB 値の平均値 avg を求めます。この例では avg = 198.763 であったとします。

改めて 256 個のピクセルの RGB 値をこの avg と比較します。ピクセルの RGB 値が avg 以上だった場合は 1 、avg 未満だった場合は 0 とみなしていきます:
2019051706


この avg と比較した結果を画像の左上から順に並べて配列にします(下図では16個ごとに改行して実際の2次元イメージに近い形にしていますが、実際は改行せずに1次元配列とみなします):
2019051703


この配列がハッシュ値となります。なんとなく元画像の中で白っぽい部分を 1 、黒っぽい部分を 0 とした結果になっていることがわかります。また、このハッシュアルゴリズムだと元画像が似ていると関数実行結果のハッシュ値も似る、ということが理解しやすいと思います。しかもハッシュ値は整数 256 個の配列なので類似性の判断も容易です。

なお、別のこちらの画像(サイズは 470x628)で同じアルゴリズムを実行すると、
smartphone_woman_smile


結果はこのようになりました:
2019051704


どのような画像に対してもまず同じサイズのグレースケール画像に変換しています(つまりグレースケールになった状態での類似性を調べるアルゴリズムです)。また各ピクセルを「その画像の各ピクセルの明るさの平均値よりも明るいか暗いか」で 0 または 1 に変換しています。これによって画像そのものが明るいものだったり暗いものだったりする要素を取り除き、その画像の中での明るい部分と暗い部分に分けるようにしています。そしてその結果がどれだけ似ているのか/似ていないのかを整数配列の類似度という比較的簡単な方法で調べられるようにしている、という特徴があることがわかりますね。


このアルゴリズムを使ってあらかじめ用意した画像の Average Hash 値を調べておきます。そして類似した画像を調べたい画像データが送られてきた場合にまず同じアルゴリズムで 256 個の1次元配列である Average Hash 値を求めれば、「0 と 1 が一致している数が多いほど似ている」と判断できることになります。

この方法であれば(実行パフォーマンスの様子を見ながらではありますが)nの値を大きくしたり、Hash 値を 0 か 1 にするのではく RGB 値をそのまま使って nxn 次元のユークリッド距離を求めることでより精度の高い類似画像検索が可能になります。あるいは別の応用としてグレースケールの手続きを省略して、カラー画像のまま比較することも可能です。


という、類似画像検索のアルゴリズムの1つを紹介しました。そんなに難しい数学知識を必要とせず、比較的理解も実装も応用もしやすいアルゴリズムだと思っています。


ゆるキャラを画像で検索するサービスを作って公開してみました:
http://yuru.mybluemix.net/

まず最初に、自分はある程度ゆるキャラに詳しいと思っています。積極的な興味というよりは、マンホールに詳しくなっていると、最近はそのマンホールのデザインにゆるキャラが使われることが珍しくなくなってきたので、自然と(?)ゆるキャラにも詳しくなってしまうのでした。。
2017011500
 

さて、ゆるキャラに限らないのですが、イマドキ何かを調べようとした時にはまず『ググる』のが定番です。ただ、それは調べるためのキーワードが分かっている場合です。ゆるキャラの場合、名前が分かっていれば名前でググれば確実ですし、名前が分からなくても出身地とかが分かれば「ゆるキャラ 東京都」などで検索すればいくつか候補が見つかるのでそこから調べる方法もあります。

しかし問題は名前も出身地も分からず、検索するためのキーワードがない場合です。例えば目の前に着ぐるみそのゆるキャラ本体がいて、写真は撮れるんだけど、そのゆるキャラがなんという名前で、どこのゆるキャラで、どんな特徴を持っているのか、、、といった情報を調べる具体的な方法がなかったように感じていました。

といった背景もあり、「画像からゆるキャラを調べる」ことができるようなウェブサービスを作ってみた、という経緯です。いわゆる「類似画像検索」を行うため、コグニティブエンジンである IBM WatsonVisual Recognition API を使って実装してみました:
http://yuru.mybluemix.net/


使い方はシンプルで、ウェブサイトをPCかスマホのブラウザで開き、ファイル選択ボタンを押して、ローカルシステムやフォトライブラリ等から目的の画像を選択するだけです:
2017011501


PC の場合に限り、目的の画像ファイルを画面上部のこの辺りにドラッグ&ドロップしても構いません:
2017011502


例えばこの画像のゆるキャラを調べてみることにしました。まあ有名なヒトなので答はわかっているのですが、ちょっとトリッキーなアイテムも写っていて普段と違う画像になっているので、いいサンプルかな、と:
く


この画像を選択するか、画面内にドラッグ&ドロップすると画面が暗転して検索が始まります:
2017011503


暗転から戻ると、検索結果として候補キャラが画面下部に表示されているはずです。最大で100件表示されます:
2017011504


今回の画像の場合、下の方にそれっぽいのが見つかりました:
2017011505


該当する結果の画像をクリックすると、そのゆるキャラの情報がポップアップします。ご存知「くまモン」でした。なお PC であればマウスオーバーでも表示されます:
2017011506


まだまだ学習量が充分ではなく、第一候補となることはまだ珍しいとか、(着ぐるみの写真ではなく)絵の場合には精度が落ちるとか、横から写した画像に弱いとか、背景画像に左右されることが多いとか、まだまだ問題はありますが、一応動くものが作れたと思ってます。

実際の用途としてはある程度いけるかな、と思ってます。もちろん精度高く検索できることが理想ですが、上記で書いたように「名前が分かれば色々調べる方法はあるんだけど、肝心の名前が出てこない」のを解決するツールとして考えると、検索結果の候補の中に含まれていれば、それはそれでオッケーかな、と。


なお、今回のサービスは Visual Recognition の中では現時点でベータ版の /v3/collections/ で始まる API を使って開発しています。今後の仕様変更などがあった場合にサービスがどうなるか何とも言えませんが、なるべく対応させていく予定です。合わせてもう少し学習データの量を増やして検索精度を上げられないか、がんばってみます。


このページのトップヘ