stMind

about Arsenal, Arsene Wenger, Tech, Computer vision and Machine learning

Perceptual Hash

Perceptual Hashは、画像などのメディアデータのハッシュを計算するアルゴリズム群です。
SHA-1MD5とは異なり、画像サイズの違いや回転などの変換で画像が全く同一でない場合でも、元画像と同じハッシュ値を計算してくれます。

どんなことに使われているのか?

アプリケーションとしては次のようなものがあります。

  • コンテンツの重複検出
    • Iconfinderでは、アイコン画像のアップロード時にdHashを用いて登録済みアイコンとの重複を検出する機能を開発中(Detecting duplicate images using Python - The Iconfinder Blog
    • Youtubeではユーザのアップロードした動画と、データベースにある著作権あり動画を比較し、違法アップロードを検出
    • DropboxのCarouselでは、ローカルのファイルからハッシュ値を計算し、サーバ側にバックアップしていないファイルを判定しているよう
  • 類似画像検索
    • TinEye.com
    • Google Image Search

アルゴリズム

入力画像を8x8もしくは8x9にリサイズし、グレースケールに変換するところまでは共通です。

  • aHash(Average Hash or Mean Hash)
    • 輝度値の平均を求め、平均より大なら1でそれ以外は0として64ビットのハッシュ値を算出
  • pHash(Perceptive Hash)
  • dHash(Difference Hash)
    • 隣接するピクセルの輝度値より大なら1でそれ以外は0として64ビットのハッシュ値を算出

詳しいアルゴリズムこちらにありますが、コードを見ると理解しやすいかなとpythonのimagehashからコードを載せてみます。

def average_hash(image, hash_size=8):
        image = image.convert("L").resize((hash_size, hash_size), Image.ANTIALIAS)
        pixels = numpy.array(image.getdata()).reshape((hash_size, hash_size))
        avg = pixels.mean()
        diff = pixels > avg
        # make a hash
        return ImageHash(diff)
def phash(image, hash_size=32):
        image = image.convert("L").resize((hash_size, hash_size), Image.ANTIALIAS)
        pixels = numpy.array(image.getdata(), dtype=numpy.float).reshape((hash_size, hash_size))
        dct = scipy.fftpack.dct(pixels)
        dctlowfreq = dct[:8, 1:9]
        avg = dctlowfreq.mean()
        diff = dctlowfreq > avg
        return ImageHash(diff)
def dhash(image, hash_size=8):
        image = image.convert("L").resize((hash_size + 1, hash_size), Image.ANTIALIAS)
        pixels = numpy.array(image.getdata(), dtype=numpy.float).reshape((hash_size + 1, hash_size))
        # compute differences
        diff = pixels[1:,:] > pixels[:-1,:]
        return ImageHash(diff)

最後は、 ハミング距離 - Wikipedia を使って二つのハッシュ値を比較して、ほぼ同じ画像かどうかを判定します。

ライブラリ

pythonしか使ったことないですが、いくつかあります。

最後に

Perceptual Hashについて書いてみました。
Iconfinderのブログエントリーに関するコメントでlibpuzzleというライブラリが紹介されていたり、他にも色々なアルゴリズムが提案されているみたいですので、興味がある方は調べてみると良いかと思います。

Libpuzzle - A library to find similar pictures