用Python實現通過哈希算法檢測圖片重復的教程

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

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

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

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

1 2 3 4 5 6 7 8 9 10 >>> 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'

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

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

1 2 3 4 5 6 7 # 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'

如果圖像背景色被改變，圖像被裁剪，旋轉或者某一個像素被修改，那麼都無法在圖像哈希庫中匹配。可見傳統哈希算法並不具有實用性。正如你在上面例子中看到的，哈希值9 e107d9d372bb6826bd81d3542a419d6 和e4d909c290d0fb1ca068ffaddf22cbd0幾乎是不同的(除了幾個字符)。

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

1 2 3 4 5 6 7 8 9 # 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三原色組成，可以看成一個紅綠藍三原色的顏色集。比如利用用Python圖像庫（PIL)加載一個圖像，並打印像素值。

Test image

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 >>> 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)]

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

1.圖像灰度化

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

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

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

3.比較鄰域像素

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 >>> from PIL import Image >>> img = Image.open('data/cat_grumpy_orig_after_step_2.png') >>> width, height = img.size