用哈希算法检测图像重复

b77m 10年前

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