Iconfinderは以前、500 Startup Fundのデモdayでプレゼンするのを見た記憶があります。それから資金調達もできたようで、無事生き残ってますね。

アイコン等の画像ファイルの検索 & 販売をするサイトですが、悪いユーザがIconfinderから画像をダウンロードした後に、そのまま、もしくは多少改変して、Iconfinderにアップして販売しようとする不正行為があるようです。その対策のための検知アルゴリズムについてブログで紹介しています。

一般的な画像データをハッシュ化するアルゴリズムでは、画像のごく一部を修正しただけで大きくハッシュ値が変わってくるので、今回は、dHash (difference hash) と呼ばれるアルゴリズムを利用しています。

1. dHash

オリジナル画像 | 修正された画像

1) 画像をグレースケール化する

画像をデフォルトのPIL法でグレースケール化する。例えば、白はRGBで表現すると(255, 255, 255)だが、グレースケール化後は255となる。また、黒は(0, 0 ,0)であるのが、0となる。

オリジナル画像 | 修正された画像

2) 共通のサイズに圧縮する

共通のサイズ、例えば9 x 8ピクセルのサイズにすることで、画像における高い空間周波数や微細な変化を無視して、72の色彩強度値のみで判断できるようになる。また、画像が修正されたときに拡大 or 圧縮されていたとしても、ハッシュ値への影響を排除できる。

3) 隣接するピクセルを比較する

例えば上記2) の結果が、

>>> from PIL import Image
>>> img = Image.open('data/cat_grumpy_orig_after_step_2.png')
>>> width, height = img.size
>>> pixels = list(img.getdata())
>>> for col in xrange(width):
...   print pixels[col:col+width]
...
[254, 254, 255, 253, 248, 254, 255, 254, 255]
[254, 255, 253, 248, 254, 255, 254, 255, 255]
[253, 248, 254, 255, 254, 255, 255, 255, 222]
[248, 254, 255, 254, 255, 255, 255, 222, 184]
[254, 255, 254, 255, 255, 255, 222, 184, 177]
[255, 254, 255, 255, 255, 222, 184, 177, 184]
[254, 255, 255, 255, 222, 184, 177, 184, 225]
[255, 255, 255, 222, 184, 177, 184, 225, 255]

であれば、最初の値(254)と二番目の値(254)、二番目の値(254)と三番目の値(255)..と順番に隣り合う値を比較していく。

>>> difference = []
>>> for row in xrange(height):
...   for col in xrange(width):
...     if col != width:
...       difference.append(pixels[col+row] > pixels[(col+row)+1])
...
>>> for col in xrange(width-1):
...   print difference[col:col+(width-1)]
...
[False, False, True, True, False, False, True, False]
[False, True, True, False, False, True, False, False]
[True, True, False, False, True, False, False, False]
[True, False, False, True, False, False, False, True]
[False, False, True, False, False, False, True, True]
[False, True, False, False, False, True, True, False]
[True, False, False, False, True, True, False, False]
[False, False, False, True, True, False, False, True]

9個の隣り合う数値を比較するので、8個の判定結果が得られる。それが8セットあることになる。

4) 差異をビット値に変換する

最後に、16進数のstringに変換して、ハッシュ値の保存 / 利用をしやすくする。

2. Pythonでの実装

def dhash(image, hash_size = 8):
    # Grayscale and shrink the image in one step.
    image = image.convert('L').resize(
        (hash_size + 1, hash_size),
        Image.ANTIALIAS,
    )

    pixels = list(image.getdata())

    # Compare adjacent pixels.
    difference = []
    for row in xrange(hash_size):
        for col in xrange(hash_size):
            pixel_left = image.getpixel((col, row))
            pixel_right = image.getpixel((col + 1, row))
            difference.append(pixel_left > pixel_right)

    # Convert the binary array to a hexadecimal string.
    decimal_value = 0
    hex_string = []
    for index, value in enumerate(difference):
        if value:
            decimal_value += 2**(index % 8)
        if (index % 8) == 7:
            hex_string.append(hex(decimal_value)[2:].rjust(2, '0'))
            decimal_value = 0

    return ''.join(hex_string)

3. ハッシュの比較

シンプルなケースとして、画像がごくわずかに修正されただけだと、ハッシュ値は同じである可能性が高い。もしハッシュ値に変化がでる程度まで改変されていた場合は、異なるビットの数を数え（hamming distance）て判断する。（The Hacker Factor Blogによると、10個以上異なるところがあると違う画像、1〜10の間であれば改変の可能性ありと言えるとのこと。）

SELECT pk, hash, BIT_COUNT(
    CONV(hash, 16, 10) ^ CONV('4c8e3366c275650f', 16, 10)
) as hamming_distance
    FROM image_hashes
    HAVING hamming_distance < 4
    ORDER BY hamming_distance ASC;

BIT_COUNTは整数でのみ有効だが、ハッシュは16進数なので、10進数に変換してから計算している。

Jan-Mar/2014: ワザノバTop25アクセスランキング

#iconfinder