Iconfinder は、デザイナー、開発者、その他のクリエイティブ ワーカー向けに優れたアイコンを提供するアイコン検索エンジンです。現在 340,000 を超えるアイコンをホストしており、有料アイコン ライブラリとしては世界最大です。ユーザーは、Iconfinder の取引セクションでオリジナル作品をアップロードして販売することもできます。毎月、何千ものアイコンが、大量の海賊版画像とともに Iconfinder にアップロードされています。 Iconfinder のエンジニア Silviu Tantos は、この記事で著作権侵害を排除するための斬新で独創的な画像重複検出技術を提案しています。

今後数週間以内に、重複したアップロード アイコンを検出する機能を展開する予定です。たとえば、ユーザーがアイコンをダウンロードし、それをアップロードして収益を得ようとした場合（これは以前にも起こったことです）、当社のアプローチではアイコンがすでに存在するかどうかを検出し、アカウントを不正なものとしてフラグ付けすることができます。多数のファイルの中にファイルが既に存在するかどうかを検出する一般的な方法は、データセット内の各ファイルのハッシュ値を計算し、そのハッシュ値を配列ライブラリに保存することです。特定のファイルを検索する場合は、まずファイルのハッシュ値を計算し、次にデータベースでハッシュ値を検索します。

ハッシュアルゴリズムの選択

暗号ハッシュ アルゴリズムは、一般的に使用されるハッシュ アルゴリズムです。 MD5、 SHA1、SHA256などの標準ライブラリはどの言語にも存在し、単純な使用例には非常に効果的です。

たとえば、 Pythonでは、まずhashlibモジュールをインポートし、次に関数を呼び出して文字列またはファイルのハッシュ値を生成します。

 >>>ハッシュライブラリをインポートする
   
 # 文字列のハッシュ値を計算します。
 >>> hashlib.md5( '素早い茶色のキツネは怠け者の犬を飛び越える' ).hexdigest()
 '9e107d9d372bb6826bd81d3542a419d6'  
   
 # 画像ファイルをメモリに読み込み、そのハッシュ値を計算します。
 >>> image_file = open( 'data/cat_grumpy_orig.png' ).read()
 >>> hashlib.md5(image_file).hexdigest()
 '3e1f6e9f2689d59b9ed28bcdab73455f'  

このアルゴリズムは、改ざんされていないアップロードされたファイルに対しては非常に有効です。入力データにわずかな変更があった場合、暗号化ハッシュ アルゴリズムによって雪崩効果が発生し、新しいファイルのハッシュ値が元のファイルのハッシュ値と完全に異なるものになります。

たとえば、次の例では、文末にピリオドが追加されています。

 # 元のテキスト。
 >>> hashlib.md5( '素早い茶色のキツネは怠け者の犬を飛び越える' ).hexdigest()
 '9e107d9d372bb6826bd81d3542a419d6'  
   
 # テキストを若干修正しました。
 >>> hashlib.md5( '素早い茶色のキツネは怠け者の犬を飛び越えます。' ).hexdigest()
 'e4d909c290d0fb1ca068ffaddf22cbd0'  

たとえば、画像内の猫の鼻の色を変更すると、画像のハッシュ値が変わります。

オリジナル画像 修正画像

# 元の画像をメモリに読み込み、そのハッシュ値を計算します。
 >>> image_file = open( 'data/cat_grumpy_orig.png' ).read()
 >>> hashlib.md5(image_file).hexdigest()
 '3e1f6e9f2689d59b9ed28bcdab73455f'  
   
 # 変更されたイメージをメモリに読み込み、そのハッシュ値を計算します。
 >>> image_file_modified = open( 'data/cat_grumpy_modif.png' ).read()
 >>> hashlib.md5(image_file_modified).hexdigest()
 '12d1b9409c3e8e0361c24beaee9c0ab1'  

知覚ハッシュ アルゴリズムは数多く存在します。この論文では、隣接するピクセル間の輝度差を計算し、相対的な勾配を決定する新しい dhash (差分ハッシュ) アルゴリズムを提案します。上記のユースケースでは、知覚ハッシュが非常にうまく機能します。知覚ハッシュ アルゴリズムは、ファイル コンテンツのさまざまな特徴からマルチメディア ファイルのフィンガープリントを取得し、異なるファイル間の微妙な違いを柔軟に区別できます。

dハッシュ

dHash アルゴリズムについて詳しく説明する前に、まず基本的な知識をいくつか紹介します。カラー画像は RGB の 3 つの原色で構成されており、赤、緑、青の 3 つの原色の色セットとして見ることができます。たとえば、Python Imaging Library (PIL) を使用して画像を読み込み、ピクセル値を出力します。

テスト画像

>>> PILから画像をインポート
>>> test_image = Image.open( 'data/test_image.jpg' ) 
   
 # 画像は 8x8 ピクセルの RGB 画像です。
 >>> '画像モード: %s'を印刷% test_image.mode
画像モード: RGB
 >>> print '幅: %s px、高さ: %s px' % (test_image.size[ 0 ]、test_image.size[ 1 ])
幅: 4ピクセル、高さ: 4ピクセル
   
 # 画像からピクセル値を取得し、それに基づいて行に印刷します
# 画像の幅。
 >>> 幅、高さ = test_image.size
 >>> ピクセル = リスト(test_image.getdata())
 >>> xrange(幅)内の列について:
 ...ピクセルを印刷[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 )]

さて、dHash アルゴリズムに戻りましょう。アルゴリズムには 4 つのステップがあります。この記事では、各ステップを詳しく説明し、元の画像と変更された画像への影響を検証します。最初の 3 つのピクセルの赤、緑、青のカラー強度値はそれぞれ 255 で、他の 2 つのピクセルのカラー強度値はそれぞれ 0 です。純粋な黒のピクセルの 3 つの原色は 0 で、純粋な白のピクセルの 3 つの原色は 255 です。その他の色のピクセルは、3 つの原色値の異なる強度で構成されます。

1. グレースケール画像

画像をグレースケール化すると、ピクセル値が光度値まで削減されます。たとえば、白いピクセル (255, 255, 255) は 255 になり、黒いピクセル (0,0,0) は 0 になります。

元の画像（手順 1 後） 変更後の画像（手順 1 後）

#p#

2. 画像を一般的なサイズに縮小する

画像を、幅と高さが 1 ピクセルの 9 x 8 ピクセルなどの共通の基本サイズに縮小します (このサイズである理由は手順 3 でわかります)。この方法では、画像から高周波と詳細が削除され、72 個の強度値を持つサンプルが生成されます。画像のサイズ変更や拡大を行ってもハッシュ値は変更されないため、すべての画像はこのサイズに正規化されます。

元の画像（手順2の後） 変更された画像（手順2の後）

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

最初の 2 つの手順が実行されると、強度値のリストが取得され、このバイナリ値配列の各行の隣接するピクセルが比較されます。

 >>> PILから画像をインポート
>>> img = Image.open( 'data/cat_grumpy_orig_after_step_2.png' )
 >>> 幅、高さ = img.size
 >>> ピクセル = リスト(img.getdata())
 >>> xrange(幅)内の列について:
 ...ピクセルを印刷[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 、 222 、 184 、 177 ]
 [ 255 、 254 、 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 番目の値と比較され、以下同様にして、行ごとに 8 つのブール値が生成されます。

 >>> 差 = []
 >>> xrange(height)内の行の場合:
 ... xrange(width) の col の場合:
 ... col != width の場合:
 ... 差を追加します(ピクセル[列+行] > ピクセル[(列+行)+ 1 ])
 ...
 >>> xrange(width - 1 )内のcolの場合:
 ... 差を印刷[col:col+(width- 1 )]
 ...
 [誤り、誤り、真、真、誤り、誤り、真、誤り]
 [誤り、真、真、誤り、誤り、真、誤り、誤り]
 [真、真、偽、偽、真、偽、偽、偽]
 [真、偽、偽、真、偽、偽、偽、真]
 [偽、偽、真、偽、偽、偽、真、真]
 [誤り、真、誤り、誤り、誤り、真、真、誤り]
 [真、偽、偽、偽、真、真、偽、偽]
 [偽、偽、偽、真、真、偽、偽、真]

4. バイナリに変換する

ハッシュ値の保存と使用を容易にするために、8 つのブール値は 16 進文字列に変換されます。 True は 1 になり、False は 0 になります。

Python実装

完全な Python で実装された完全なアルゴリズムは次のとおりです。

 def dhash(イメージ、hash_size = 8 ):
    # 画像を 1 ステップでグレースケール化して縮小します。
    画像 = image.convert( 'L' ).resize(
        (ハッシュサイズ + 1 、ハッシュサイズ)、
        Image.ANTIALIAS、
    ） 
   
    ピクセル = リスト(image.getdata()) 
   
    # 隣接するピクセルを比較します。
    差 = [] 
     xrange(hash_size) 内の行の場合: 
         xrange(hash_size)内の列の場合:
            ピクセル左 = image.getpixel((列、行))
            ピクセル右 = image.getpixel((列 + 1 、行))
            差を追加します(pixel_left >pixel_right) 
   
    # バイナリ配列を 16 進文字列に変換します。
    小数値 = 0  
    16進文字列 = [] 
    インデックス、enumerate(差異)の値: 
        値の場合:
            小数点値 += 2 **(インデックス % 8 ) 
         (インデックス % 8 ) == 7 の場合:
            hex_string.append(hex(decimal_value)[ 2 :].rjust( 2 , '0' ))
            小数値 = 0  
   
    戻る  '' .join(16進文字列)

最も一般的なケースでは、画像がわずかに異なる場合、ハッシュ値は同じになる可能性が高いため、直接比較できます。

 >>> PILから画像をインポート
>>> ユーティリティからdhash、hamming_distanceをインポートします
>>> orig = Image.open( 'data/cat_grumpy_orig.png' )
 >>> modif = Image.open( 'data/cat_grumpy_modif.png' )
 >>> dhash(原文)
 '4c8e3366c275650f'  
 >>> dhash(変更)
 '4c8e3366c275650f'  
 >>> dhash(orig) == dhash(modif)
真実

ハッシュ値を保存する SQL データベースがある場合は、ハッシュ値「4c8e3366c275650f」が存在するかどうかを簡単に判断できます。

 image_hashes から pk、hash、file_path を選択
    ここで、ハッシュ = '4c8e3366c275650f' ;

ここで、大きな違いがある画像ではハッシュ値が異なる場合があるため、ある文字列を別の文字列に置き換えるために必要な最小文字数、つまりハミング距離を計算する必要があります。

Wikipedia には、2 つの文字列間のハミング距離を計算する Python のサンプル コードがいくつか掲載されています。ただし、MySQL データベースの計算とクエリに基づいて直接実装することもできます。

 pk、ハッシュ、BIT_COUNT( を選択
    CONV(ハッシュ, 16 , 10 ) ^ CONV( '4c8e3366c275650f' , 16 , 10 )
 ) をハミング距離として
    image_hashesから
    ハミング距離 < 4 である 
    ハミング距離 ASC で並べ替えます。

クエリされた値とデータベース内のハッシュ値に対して XOR 演算を実行し、異なる桁の数をカウントします。 BIT_COUNT は整数に対してのみ動作できるため、すべての 16 進ハッシュ値は 10 進数に変換する必要があります。

結論

この記事では、紹介したアルゴリズムを実装するために Python を使用していますが、もちろん、読者は任意のプログラミング言語を使用してアルゴリズムを実装できます。

はじめに述べたように、この記事のアルゴリズムは、重複したアイコンの送信を防ぐために Iconfinder に適用されます。知覚ハッシュ アルゴリズムは、より実用的な用途を持つことが期待できます。類似した特徴を持つ画像は類似したハッシュ値を持つため、画像推奨システムが類似した画像を見つけるのに役立ちます。

オリジナルリンク: Silviu Tantos翻訳: Bole Online - Xiaoyu

翻訳リンク: http://blog.jobbole.com/65914/