用哈希算法檢測圖像重復

b77m 9年前發布 | 59K 次閱讀 算法 圖形/圖像處理

Iconfinder 是一個圖標搜索引擎，為設計師、開發者和其他創意工作者提供精美圖標，目前托管超過 34 萬枚圖標，是全球最大的付費圖標庫。用戶也可以在 Iconfinder 的交易板塊上傳出售原創作品。每個月都有成千上萬的圖標上傳到Iconfinder，同時也伴隨而來大量的盜版圖。Iconfinder 工程師 Silviu Tantos 在本文中提出一個新穎巧妙的圖像查重技術，以杜絕盜版。

我們將在未來幾周之內推出一個檢測上傳圖標是否重復的功能。例如，如果用戶下載了一個圖標然后又試圖通過上傳它來獲利（曾發生過類似案例），那么通 過我們的方法，就可以檢測出該圖標是否已存在，并且標記該賬戶欺詐。在大量文件中檢測某文件是否已經存在的一個常用方法是，通過計算數據集中每一個文件的 哈希值，并將該哈希值存儲在數組庫中。當想要查找某特定文件時，首先計算該文件哈希值，然后在數據庫中查找該哈希值。

選擇一個哈希算法

加密哈希算法是一個常用的哈希算法。類似MD5，SHA1，SHA256這種在任何一種語言都可以找到可調用的標準庫，它們對于簡單的用例非常有效。

例如，在Python中先導入hashlib模塊，然后調用函數就可以生成某一個字符串或者文件的哈希值。

  1. >>> import hashlib

  3. # Calculating the hash value of a string.
  4. >>> hashlib.md5(‘The quick brown fox jumps over the lazy dog’).hexdigest()
  5. ‘9e107d9d372bb6826bd81d3542a419d6′

  7. # Loading an image file into memory and calculating it’s hash value.
  8. >>> image_file = open(‘data/cat_grumpy_orig.png’).read()
  9. >>> hashlib.md5(image_file).hexdigest()
  10. ‘3e1f6e9f2689d59b9ed28bcdab73455f’

這個算法對于未被篡改的上傳文件非常有效，如果輸入數據有細微變化，加密哈希算法都會導致雪崩效應，從而造成新文件的哈希值完全不同于原始文件哈希值。

比如下面這個例子，它在句子的結尾多加了一個句號。

  1. # Original text.
  2. >>> hashlib.md5(‘The quick brown fox jumps over the lazy dog’).hexdigest()
  3. ‘9e107d9d372bb6826bd81d3542a419d6′

  5. # Slight modification of the text.
  6. >>> hashlib.md5(‘The quick brown fox jumps over the lazy dog.’).hexdigest()
  7. ‘e4d909c290d0fb1ca068ffaddf22cbd0′
如果圖像背景色被改變，圖像被裁剪，旋轉或者某一個像素被修改，那么都無法在圖像哈希庫中匹配。可見傳統哈希算法并不具有實用性。正如你在上面 例子中看到的，哈希值9 e107d9d372bb6826bd81d3542a419d6 和 e4d909c290d0fb1ca068ffaddf22cbd0幾乎是不同的(除了幾個字符)。

例如，修改圖像中貓咪鼻子的顏色后，圖像的哈希值將改變。

用哈希算法檢測圖像重復

Original image

        用哈希算法檢測圖像重復

Modified image

  1. # Load the original image into memory and calculate it’s hash value.
  2. >>> image_file = open(‘data/cat_grumpy_orig.png’).read()
  3. >>> hashlib.md5(image_file).hexdigest()
  4. ‘3e1f6e9f2689d59b9ed28bcdab73455f’

  6. # Load the modified image into memory and calculate it’s hash value.
  7. >>> image_file_modified = open(‘data/cat_grumpy_modif.png’).read()
  8. >>> hashlib.md5(image_file_modified).hexdigest()
  9. ’12d1b9409c3e8e0361c24beaee9c0ab1′

目前已有許多感知哈希算法，本文將要提出一個新的dhash（差異哈希）算法，該算法計算相鄰像素之間的亮度差異并確定相對梯度。對于以上的用例，感知哈希算法將非常有效。感知哈希算法從文件內容的各種特征中獲得一個能夠靈活分辨不同文件微小區別的多媒體文件指紋。

dHash

深入學習dHash算法前，先介紹一些基礎知識。一個彩色圖像是由RGB三原色組成，可以看成一個紅綠藍三原色的顏色集。比如利用用Python圖像庫（PIL)加載一個圖像，并打印像素值。

用哈希算法檢測圖像重復

Test image

  1. >>> from PIL import Image
  2. >>> test_image  = Image.open(‘data/test_image.jpg’)

  4. # The image is an RGB image with a size of 8×8 pixels.
  5. >>> print ‘Image Mode: %s’ % test_image.mode
  6. Image Mode: RGB
  7. >>> print ‘Width: %s px, Height: %s px’ % (test_image.size[0], test_image.size[1])
  8. Width: 4 px, Height: 4 px

  10. # Get the pixel values from the image and print them into rows based on
  11. # the image’s width.
  12. >>> width, height = test_image.size
  13. >>> pixels = list(test_image.getdata())
  14. >>> for col in xrange(width):
  15. …   print pixels[col:col+width]
  16. …
  17. [(255, 0, 0), (0, 255, 0), (0, 0, 255), (255, 255, 255)]
  18. [(0, 0, 0), (212, 45, 45), (51, 92, 154), (130, 183, 47)]
  19. [(206, 210, 198), (131, 78, 8), (131, 156, 180), (117, 155, 201)]
  20. [(104, 133, 170), (215, 130, 20), (153, 155, 155), (104, 142, 191)]

現在我們回到dHash算法，該算法有四個步驟，本文詳細說明每一步并驗證它在原始圖像和修改后圖像的效果。前三個像素的紅綠藍顏色強度值分別為 255，其余兩個顏色強度值分別為0，純黑色像素三原色為0，純白色像素三原色為255。其它顏色像素則是由不同強度三原色值組成的。

1.圖像灰度化

通過灰度化圖像，將像素值減少到一個發光強度值。例如,白色像素(255、255、255)成為255而黑色像素(0,0,0)強度值將成為0。

用哈希算法檢測圖像重復

Original image (after step 1)

 

用哈希算法檢測圖像重復

Modified image (after step 1)

2.將圖像縮小到一個常見大小

將圖像縮減到一個常見基礎尺寸，比如寬度大高度一個像素值的9*8像素大小（到第三步你就能明白為什么是這個尺寸）。通過這個方法將圖像中的高頻和 細節部分移除，從而獲得一個有72個強度值的樣本。由于調整或者拉伸圖像并不會改變它的哈希值，所以將所有圖像歸一化到該大小。

用哈希算法檢測圖像重復

Original image (after step 2)

 用哈希算法檢測圖像重復

Modified image (after step 2)

3.比較鄰域像素

前兩步實現后得到一個強度值列表，比較該二進制值數組的每一行的相鄰像素。

  1. >>> from PIL import Image
  2. >>> img = Image.open(‘data/cat_grumpy_orig_after_step_2.png’)
  3. >>> width, height = img.size
  4. >>> pixels = list(img.getdata())
  5. >>> for col in xrange(width):
  6. …   print pixels[col:col+width]
  7. …
  8. [254, 254, 255, 253, 248, 254, 255, 254, 255]
  9. [254, 255, 253, 248, 254, 255, 254, 255, 255]
  10. [253, 248, 254, 255, 254, 255, 255, 255, 222]
  11. [248, 254, 255, 254, 255, 255, 255, 222, 184]
  12. [254, 255, 254, 255, 255, 255, 222, 184, 177]
  13. [255, 254, 255, 255, 255, 222, 184, 177, 184]
  14. [254, 255, 255, 255, 222, 184, 177, 184, 225]
  15. [255, 255, 255, 222, 184, 177, 184, 225, 255]

第一個值254和第二個254做比較，第二個值和第三個值比，以此類推，從而每行得到8個布爾值。

  1. >>> difference = []
  2. >>> for row in xrange(height):
  3. …   for col in xrange(width):
  4. …     if col != width:
  5. …       difference.append(pixels[col+row] > pixels[(col+row)+1])
  6. …
  7. >>> for col in xrange(width-1):
  8. …   print difference[col:col+(width-1)]
  9. …
  10. [False, False, True, True, False, False, True, False]
  11. [False, True, True, False, False, True, False, False]
  12. [True, True, False, False, True, False, False, False]
  13. [True, False, False, True, False, False, False, True]
  14. [False, False, True, False, False, False, True, True]
  15. [False, True, False, False, False, True, True, False]
  16. [True, False, False, False, True, True, False, False]
  17. [False, False, False, True, True, False, False, True]

4.轉換為二值

為了方便哈希值存儲和使用，將8個布爾值轉換為16進制字符串。Ture變成1，而False變成0。

Python實現

下面是完整Python實現的完成算法：

  1. def dhash(image, hash_size = 8):
  2.     # Grayscale and shrink the image in one step.
  3.     image = image.convert(‘L’).resize(
  4.         (hash_size + 1, hash_size),
  5.         Image.ANTIALIAS,
  6.     )

  8.     pixels = list(image.getdata())

  10.     # Compare adjacent pixels.
  11.     difference = []
  12.     for row in xrange(hash_size):
  13.         for col in xrange(hash_size):
  14.             pixel_left = image.getpixel((col, row))
  15.             pixel_right = image.getpixel((col + 1, row))
  16.             difference.append(pixel_left > pixel_right)

  18.     # Convert the binary array to a hexadecimal string.
  19.     decimal_value = 0
  20.     hex_string = []
  21.     for index, value in enumerate(difference):
  22.         if value:
  23.             decimal_value += 2**(index % 8)
  24.         if (index % 8) == 7:
  25.             hex_string.append(hex(decimal_value)[2:].rjust(2, ‘0’))
  26.             decimal_value = 0

  28.     return ”.join(hex_string)

最常見情況，圖片稍有不同，哈希值很可能是相同的,所以我們可以直接比較。

  1. >>> from PIL import Image
  2. >>> from utility import dhash, hamming_distance
  3. >>> orig = Image.open(‘data/cat_grumpy_orig.png’)
  4. >>> modif = Image.open(‘data/cat_grumpy_modif.png’)
  5. >>> dhash(orig)
  6. ‘4c8e3366c275650f’
  7. >>> dhash(modif)
  8. ‘4c8e3366c275650f’
  9. >>> dhash(orig) == dhash(modif)
  10. True

如果有一個保存哈希值的SQL數據庫, 可以這樣簡單判斷哈希值“4 c8e3366c275650f ”是否存在:

  1. SELECT pk, hash, file_path FROM image_hashes
  2.     WHERE hash = ‘4c8e3366c275650f’;

現在,對于一些有較大差別的圖像，它們的哈希值可能是不相同的，那么需要計算由一個字符串變成另一個字符串所需替換的最少字符數,即漢明距離。

維基百科上有一些計算兩個字符串之間的漢明距離的Python示例代碼。但是也可以直接基于MySQL數據庫上的計算和查詢來實現。

  1. SELECT pk, hash, BIT_COUNT(
  2.     CONV(hash, 16, 10) ^ CONV(‘4c8e3366c275650f’, 16, 10)
  3. ) as hamming_distance
  4.     FROM image_hashes
  5.     HAVING hamming_distance < 4
  6.     ORDER BY hamming_distance ASC;

對所查詢的值與數據庫中的哈希值進行異或操作，計數不同位數。由于BIT_COUNT只能操作整數，所以要將所有十六進制的哈希值轉成十進制。

結束語

本文使用Python實現了所介紹的算法，當然了讀者可以使用任何編程語言實現算法。

在簡介中提過，本文算法將應用到Iconfinder上去防止重復提交圖標，可以預想，感知哈希算法還有更多實際應用。因為有相似特征的圖像的哈希值也是相似的，所以它可以幫助圖像推薦系統尋找相似圖像。

翻譯： 小魚

英文出處：Silviu Tantos

文章出處：http://developer.51cto.com/art/201405/437631_1.htm

 本文由用戶 b77m 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
 轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
 本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！