アップロードされたアイコンが複製であるかどうかを検出する機能は、今後数週間以内に展開される予定です。例えば、ユーザーがアイコンをダウンロードし、それをアップロードして利益を得ようとした場合、その方法によって、アイコンが既に存在するかどうかを検出し、不正なアカウントとしてフラグを立てることが可能になります。多数のファイルの中からファイルが既に存在するかどうかを検出する一般的な方法は、データセット内の各ファイルについてハッシュ値を計算し、そのハッシュ値を配列ライブラリに格納することです。特定のファイルを見つけようとする場合、まずファイルのハッシュが計算され、次にそのハッシュがデータベースで検索されます。
ハッシュアルゴリズムの選択
暗号ハッシュアルゴリズムは、一般的に使用されるハッシュアルゴリズムです。MD5、SHA1、SHA652のような標準ライブラリは、どの言語でも呼び出すことができ、単純なユースケースでは非常に効果的です。
例えばPythonでは、hashlibモジュールをインポートして、文字列やファイルのハッシュを生成する関数を呼び出すことができます。
>>> import hashlib
# Calculating the hash value of a string.
>>> hashlib.md5('The quick brown fox jumps over the lazy dog').hexdigest()
'9e107d9d372bb6826bd81d3542a419d6'
# Loading an image file into memory and calculating it's hash value.
>>> image_file = open('data/cat_grumpy_orig.png').read()
>>> hashlib.md5(image_file).hexdigest()
'3e1f6e9f2689d59b9ed28bcdab73455f'
このアルゴリズムは、改ざんされていないアップロードされたファイルに対しては非常にうまく機能し、入力データにわずかでも変更があると、暗号ハッシュアルゴリズムは、新しいファイルのハッシュが元のファイルのハッシュと完全に異なるという結果をもたらす雪崩効果を引き起こす可能性があります。
例えば、次の例では、文末にフルストップが追加されます。
# Original text.
>>> hashlib.md5('The quick brown fox jumps over the lazy dog').hexdigest()
'9e107d9d372bb6826bd81d3542a419d6'
# Slight modification of the text.
>>> hashlib.md5('The quick brown fox jumps over the lazy dog.').hexdigest()
'e4d909c290d0fb1ca068ffaddf22cbd0'
例えば、イメージ内の猫の鼻の色を変更すると、イメージのハッシュ値が変更されます。
元のイメージ 変更後のイメージ
# Load the original image into memory and calculate it's hash value.
>>> image_file = open('data/cat_grumpy_orig.png').read()
>>> hashlib.md5(image_file).hexdigest()
'3e1f6e9f2689d59b9ed28bcdab73455f'
# Load the modified image into memory and calculate it's hash value.
>>> image_file_modified = open('data/cat_grumpy_modif.png').read()
>>> hashlib.md5(image_file_modified).hexdigest()
'12d1b9409c3e8e0361c24beaee9c0ab1'
知覚ハッシュアルゴリズムは数多くありますが、本稿では、隣接するピクセル間の輝度差を計算し、相対的な勾配を決定する新しいdhashアルゴリズムを提案します。この知覚ハッシュアルゴリズムは、上記のような用途に非常に有効です。知覚ハッシュアルゴリズムは、ファイルコンテンツの様々な特徴からマルチメディアファイルのフィンガープリントを取得します。
dHash
dHashアルゴリズムに入る前に、基本的なことを説明しましょう。カラーイメージはRGBの3原色で構成されており、赤、緑、青のカラーセットと考えることができます。例えば、Python Image Library (PIL)でイメージを読み込み、ピクセル値を表示します。
テストイメージ
>>> from PIL import Image
>>> test_image = Image.open('data/test_image.jpg')
# The image is an RGB image with a size of 8x8 pixels.
>>> print 'Image Mode: %s' % test_image.mode
Image Mode: RGB
>>> print 'Width: %s px, Height: %s px' % (test_image.size[0], test_image.size[1])
Width: 4 px, Height: 4 px
# Get the pixel values from the image and print them into rows based on
# the image's width.
>>> width, height = test_image.size
>>> pixels = list(test_image.getdata())
>>> for col in xrange(width):
... print pixels[col:col+width]
...
[(255, 0, 0), (0, 255, 0), (0, 0, 255), (255, 255, 255)]
[(0, 0, 0), (212, 45, 45), (51, 92, 154), (130, 183, 47)]
[(206, 210, 198), (131, 78, 8), (131, 156, 180), (117, 155, 201)]
[(104, 133, 170), (215, 130, 20), (153, 155, 155), (104, 142, 191)]
イメージのグレイスケーリング
イメージをグレイスケーリングすることで、ピクセル値は輝度値に縮小されます。例えば、白いピクセルは255になり、黒いピクセルは輝度値0になります。
元のイメージ 変更後のイメージ
#p#
イメージを一般的なサイズに縮小
イメージは、幅が大きく高さが1ピクセル値の9*8ピクセルのような一般的なベースサイズに縮小されます。こうすることで、イメージの高周波数部分と詳細部分が取り除かれ、72の強度値を持つサンプルになります。イメージのサイズを変更したり伸ばしたりしてもハッシュ値は変わらないので、すべてのイメージはそのサイズに正規化されます。
元のイメージ 変更後のイメージ
近傍ピクセルの比較
最初の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は2番目の値254と比較され、2番目は3番目と比較され、このように1行につき8つのブール値が得られます。
>>> 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]
バイナリへの変換
ハッシュの保存と使用を容易にするため、8つのブーリアン値は16進文字列に変換されます。
Python
以下は、補完アルゴリズムの完全な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)
最も一般的なケースでは、イメージがわずかに異なっていても、ハッシュ値は同じである可能性が高いため、直接比較することができます。
>>> from PIL import Image
>>> from utility import dhash, hamming_distance
>>> orig = Image.open('data/cat_grumpy_orig.png')
>>> modif = Image.open('data/cat_grumpy_modif.png')
>>> dhash(orig)
'4c8e3366c275650f'
>>> dhash(modif)
'4c8e3366c275650f'
>>> dhash(orig) == dhash(modif)
True
ハッシュを保存するSQLデータベースがあれば、"4 c8e3366c275650f "というハッシュが存在するかどうか、次のように簡単に調べることができます。
SELECT pk, hash, file_path FROM image_hashes
WHERE hash = '4c8e3366c275650f';
この場合、ある文字列から別の文字列に置き換える必要がある最小の文字数、すなわちハミング距離を計算する必要があります。
Wikipediaに2つの文字列間のハミング距離を計算するPythonのサンプルコードがあります。しかし、MySQLデータベースの計算とクエリに基づいて直接計算することも可能です。
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進数に変換してください。
おわりに
冒頭で述べたように、本論文のアルゴリズムは、アイコンの重複投稿を防止するためにIconfinderに適用される予定ですが、知覚ハッシュアルゴリズムの実用的な応用がより期待できます。類似した特徴を持つイメージのハッシュ値は類似しているため、イメージ推薦システムが類似イメージを見つけるのに役立ちます。
