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つを紹介しました。そんなに難しい数学知識を必要とせず、比較的理解も実装も応用もしやすいアルゴリズムだと思っています。