用Python實(shí)現(xiàn)通過(guò)哈希算法檢測(cè)圖片重復(fù)的教程

更新時(shí)間：2015年04月02日 10:17:44 作者：Silviu Tantos

這篇文章主要介紹了用Python實(shí)現(xiàn)通過(guò)哈希算法檢測(cè)圖片重復(fù)的教程,這個(gè)方法被Iconfinder用作防盜版技術(shù),需要的朋友可以參考下

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

我們將在未來(lái)幾周之內(nèi)推出一個(gè)檢測(cè)上傳圖標(biāo)是否重復(fù)的功能。例如，如果用戶下載了一個(gè)圖標(biāo)然后又試圖通過(guò)上傳它來(lái)獲利（曾發(fā)生過(guò)類似案例），那么通過(guò)我們的方法，就可以檢測(cè)出該圖標(biāo)是否已存在，并且標(biāo)記該賬戶欺詐。在大量文件中檢測(cè)某文件是否已經(jīng)存在的一個(gè)常用方法是，通過(guò)計(jì)算數(shù)據(jù)集中每一個(gè)文件的哈希值，并將該哈希值存儲(chǔ)在數(shù)組庫(kù)中。當(dāng)想要查找某特定文件時(shí)，首先計(jì)算該文件哈希值，然后在數(shù)據(jù)庫(kù)中查找該哈希值。
選擇一個(gè)哈希算法

加密哈希算法是一個(gè)常用的哈希算法。類似MD5，SHA1，SHA256這種在任何一種語(yǔ)言都可以找到可調(diào)用的標(biāo)準(zhǔn)庫(kù)，它們對(duì)于簡(jiǎn)單的用例非常有效。

例如，在Python中先導(dǎo)入hashlib模塊，然后調(diào)用函數(shù)就可以生成某一個(gè)字符串或者文件的哈希值。

>>> 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'

這個(gè)算法對(duì)于未被篡改的上傳文件非常有效，如果輸入數(shù)據(jù)有細(xì)微變化，加密哈希算法都會(huì)導(dǎo)致雪崩效應(yīng)，從而造成新文件的哈希值完全不同于原始文件哈希值。

比如下面這個(gè)例子，它在句子的結(jié)尾多加了一個(gè)句號(hào)。

# 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'

如果圖像背景色被改變，圖像被裁剪，旋轉(zhuǎn)或者某一個(gè)像素被修改，那么都無(wú)法在圖像哈希庫(kù)中匹配?？梢?jiàn)傳統(tǒng)哈希算法并不具有實(shí)用性。正如你在上面例子中看到的，哈希值9 e107d9d372bb6826bd81d3542a419d6 和e4d909c290d0fb1ca068ffaddf22cbd0幾乎是不同的(除了幾個(gè)字符)。

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

201542101201416.jpg (649×318)

# 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'

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

dHash

深入學(xué)習(xí)dHash算法前，先介紹一些基礎(chǔ)知識(shí)。一個(gè)彩色圖像是由RGB三原色組成，可以看成一個(gè)紅綠藍(lán)三原色的顏色集。比如利用用Python圖像庫(kù)（PIL)加載一個(gè)圖像，并打印像素值。

201542101238378.jpg (717×717)

Test image

>>> 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)]

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

1.圖像灰度化

通過(guò)灰度化圖像，將像素值減少到一個(gè)發(fā)光強(qiáng)度值。例如,白色像素(255、255、255)成為255而黑色像素(0,0,0)強(qiáng)度值將成為0。

201542101324348.jpg (628×336)

2.將圖像縮小到一個(gè)常見(jiàn)大小

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

201542101403771.jpg (595×259)

3.比較鄰域像素

前兩步實(shí)現(xiàn)后得到一個(gè)強(qiáng)度值列表，比較該二進(jìn)制值數(shù)組的每一行的相鄰像素。

>>> 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]

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

>>> 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]

4.轉(zhuǎn)換為二值

為了方便哈希值存儲(chǔ)和使用，將8個(gè)布爾值轉(zhuǎn)換為16進(jìn)制字符串。Ture變成1，而False變成0。
Python實(shí)現(xiàn)

下面是完整Python實(shí)現(xiàn)的完成算法：

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)

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

>>> 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

如果有一

個(gè)保存哈希值的SQL數(shù)據(jù)庫(kù), 可以這樣簡(jiǎn)單判斷哈希值“4 c8e3366c275650f ”是否存在:

SELECT pk, hash, file_path FROM image_hashes
  WHERE hash = '4c8e3366c275650f';

現(xiàn)在,對(duì)于一些有較大差別的圖像，它們的哈希值可能是不相同的，那么需要計(jì)算由一個(gè)字符串變成另一個(gè)字符串所需替換的最少字符數(shù),即漢明距離。
維基百科上有一些計(jì)算兩個(gè)字符串之間的漢明距離的Python示例代碼。但是也可以直接基于MySQL數(shù)據(jù)庫(kù)上的計(jì)算和查詢來(lái)實(shí)現(xiàn)。

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;

對(duì)所查詢的值與數(shù)據(jù)庫(kù)中的哈希值進(jìn)行異或操作，計(jì)數(shù)不同位數(shù)。由于BIT_COUNT只能操作整數(shù)，所以要將所有十六進(jìn)制的哈希值轉(zhuǎn)成十進(jìn)制。

結(jié)束語(yǔ)

本文使用Python實(shí)現(xiàn)了所介紹的算法，當(dāng)然了讀者可以使用任何編程語(yǔ)言實(shí)現(xiàn)算法。

在簡(jiǎn)介中提過(guò)，本文算法將應(yīng)用到Iconfinder上去防止重復(fù)提交圖標(biāo)，可以預(yù)想，感知哈希算法還有更多實(shí)際應(yīng)用。因?yàn)橛邢嗨铺卣鞯膱D像的哈希值也是相似的，所以它可以幫助圖像推薦系統(tǒng)尋找相似圖像。

您可能感興趣的文章: