Perceptual Hash

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

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

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

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

アルゴリズム

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

aHash（Average Hash or Mean Hash）
- 輝度値の平均を求め、平均より大なら1でそれ以外は0として64ビットのハッシュ値を算出
pHash（Perceptive Hash）
- DCTを適用して、低周波成分から64ビットのハッシュ値を算出
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 を使って二つのハッシュ値を比較して、ほぼ同じ画像かどうかを判定します。