图片识别——均值哈希算法 - 高飞网
649 人阅读

图片识别——均值哈希算法

2017-07-28 02:09:46

    均值哈希算法(Average hash algorithm,AHA)第一次是从著名的阮一峰阮老师的博文《相似图片搜索的原理》看到的。而此篇文章与阮老师也很类似Looks Like It - The Hacker Factor Blog 。这里不对原谅做摘抄,有兴趣的自己看一下,在此对学习过程中的心得和遇到过的问题做一下总结。

    均值哈希算法,是感知哈希算法中最简单的一种,基本原理是对图片降频。对于图片,高频有很多细节,如颜色、亮度、透明度等等,而低频丢弃细节,只有图像结构。

算法步骤

  1. 缩小尺寸。为了保留结构去掉细节,去除大小、横纵比的差异,把图片统一缩放到8*8,共64个像素的图片。
  2. 简化色彩,转化为灰度图。把缩放后的图片转化为64级灰度图。
  3. 计算平均值。计算进行灰度处理后图片的所有像素点的平均值。
  4. 比较像素灰度值。遍历灰度图片每一个像素,如果大于平均值记录为1,否则为0。
  5. 获取指纹。将上一步的比较结果,组合在一起,就构成了一个64位的整数,这就是这张图片的指纹。组合的次序并不重要,只要保证所有图片都采用同样次序就行了

    可见,之所以称之为均值哈希算法,就是因为这种哈希算法,是通过灰度值的平均值,与其他灰度值的差异性得出来的。

哈希值比较

    得到指纹以后,就可以对比不同的图片,看看图片中有多少位是不一样的。理论上,这等同于计算汉明距离(Hamming Distance)。如果不相同的数据位不超过5,就说明两张图很相似;如果大于10,说明这两张是不同的图片(不同的图片,不代表不相似)。

算法优缺点

优点:

  1. 算法简单,计算速度快。
  2. 图片放大或缩小,改变纵横比,或增加减少亮度、对比度、颜色,对hash值改变不会太大。

缺点:

  1. 算法对图片的内容非常敏感,如果内容改变,很容易使得图片的哈希值差别变大。

博文中的python代码

    在阮老师的博文中,给出了一段用python写的源码,笔者本身并没有写过python代码,但根据上面算法的描述,开始并没有得出原文中相似的哈希结果,于是才反回来再看看这段python代码。遇到的问题或者说误解有:

  1. ,这张图片,是算法的第一步,将原图变为8*8的图片,但笔者写的java代码的缩小图片,与该图并不完全一致。
  2. ,这张图片,是算法的最后一步给出的,虽然是黑白的,但并不是灰度图,将图放大后,会看到只有黑白两色,应该是二值化图
  3. 文中给出的16进制哈希值:8f373714acfcf4d0。笔者的代码未能得出相同结果。

imgHash.py如下

#!/usr/bin/python
#coding:utf-8

import glob
import os
import sys

#引入Python Imaging Library (PIL)
from PIL import Image

#支持的图片后缀,window中大小写不敏感,在此只取小写的,否则最后一行结果会打印两次
#EXTS = 'jpg', 'jpeg', 'JPG', 'JPEG', 'gif', 'GIF', 'png', 'PNG'
EXTS = 'jpg', 'gif', 'png'

#均值哈希算法函数
def avhash(im):
    if not isinstance(im, Image.Image):
        im = Image.open(im)#打开图片
    im = im.resize((8, 8), Image.ANTIALIAS).convert('L')#缩小为8*8,平滑图(ANTIALIAS),转为灰度图(L)
    avg = reduce(lambda x, y: x + y, im.getdata()) / 64.#计算像素的平均值
    return reduce(lambda x, (y, z): x | (z << y),
                  enumerate(map(lambda i: 0 if i < avg else 1, im.getdata())),
                  0)#计算哈希值,x|(z<<y)是核心之处,判断了为0还是为1后,每后一位,向右移y位,这里的(y,z)和后面的enumerate对应


#汉明距离计算函数
def hamming(h1, h2):
    h, d = 0, h1 ^ h2
    while d:
        h += 1
        d &= d - 1
    return h

'''
主方法
用法:python imgHash.py image.jpg [dir]
第一个参数是要查找的图片,第二个参数在哪个路径下查找图片
分别计算要查找图片的均值哈希和路径下所有图片的均值哈希
'''
if __name__ == '__main__':
    if len(sys.argv) <= 1 or len(sys.argv) > 3:
        print "Usage: %s image.jpg [dir]" % sys.argv[0]
    else:
        im, wd = sys.argv[1], '.' if len(sys.argv) < 3 else sys.argv[2]
        h = avhash(im)

        os.chdir(wd)
        images = []
        for ext in EXTS:
            images.extend(glob.glob('*.%s' % ext))
        seq = []
        prog = int(len(images) > 50 and sys.stdout.isatty())
        for f in images:
            seq.append((f, hamming(avhash(f), h)))
            if prog:
                perc = 100. * prog / len(images)
                x = int(2 * perc / 5)
                print '\rCalculating... [' + '#' * x + ' ' * (40 - x) + ']',
                print '%.2f%%' % perc, '(%d/%d)' % (prog, len(images)),
                sys.stdout.flush()
                prog += 1
        if prog: print
        for f, ham in sorted(seq, key=lambda i: i[1]):
            print "%d\t%s123" % (ham, f)


这段python代码,2.x版本的,因此不要用3.x版本来运行。笔者用Python 2.7运行成功。

由于代码中使用了PIL,需要先安装。Python Imaging Library (PIL)

现在放两张图片,用以测试:

输出:

C:\Users\Administrator>c:\Python27\python.exe c:\Python27\imgHash2.py c:\imagetest\imgHash\bg2011072103.jpg c:\imagetest\imgHash\
0       bg2011072103.jpg123
32      f.png123

回顾问题

    之前提到过,缩小的图片和灰度图,以及哈希值有疑义,现在用该python代码,分别输出一下这两个图片以级hash值。将原来的代码做如下修改:

im = im.resize((8, 8), Image.ANTIALIAS).convert('L')#缩小为8*8,平滑图(ANTIALIAS),转为灰度图(L)

==>

 im = im.resize((8, 8), Image.ANTIALIAS)
 im.save("c:/imagetest/imgHash/88/hash88.jpg")
 #缩小为8*8,平滑图(ANTIALIAS),转为灰度图(L)
 im = im.convert('L')  
 im.save("c:/imagetest/imgHash/88/hash88_gray.jpg")

h = avhash(im)

之后加上:

print "avhash:%x"%h

输出结果:

avhash:175f2f63435be3e7
0       bg2011072103.jpg123
32      f.png123



结论:

文中的代码也并未得出文中描述的结果。

java实现

下面附上我实验过的代码:

/**
 * 均值哈希算法/Average hash algorithm/AHA
 * <p>
 * 最适用于缩略图,放大图搜索
 * <p>
 * 虽然均值哈希更简单且更快速,但是在比较上更死板、僵硬。<br>
 * 它可能产生错误的漏洞,如有一个伽马校正或颜色直方图被用于到图像。<br>
 * 这是因为颜色沿着一个非线性标尺 - 改变其中“平均值”的位置,并因此改变哪些高于/低于平均值的比特数
 * <p>
 * 
 * @author xuyanhua
 * @data Jan 10, 2017 1:09:46 AM
 */
public class AHash {

    /**
     * 图片指纹
     * 
     * @param imagePath
     * @return
     * @throws IOException
     */
    public static long fingerprint(String imagePath) throws IOException {
        BufferedImage srcImage = ImageIO.read(new File(imagePath));
        /*
         * 1.缩小尺寸. 为了保留结构去掉细节,去除大小、横纵比的差异,把图片统一缩放到8*8,共64个像素的图片
         */
        BufferedImage image8x8 = ImageUtil.resize(srcImage, 8, 8);
        /*
         * 2.简化色彩,转化为灰度图. 把缩放后的图片转化为256阶的灰度图
         */
        int width = image8x8.getWidth();
        int height = image8x8.getHeight();
        int[] grayPix = new int[64];
        int i = 0;
        int sum = 0;
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                int rgb = image8x8.getRGB(x, y);
                int r = rgb >> 16 & 0xff;
                int g = rgb >> 8 & 0xff;
                int b = rgb >> 0 & 0xff;
                int gray = (r * 30 + g * 59 + b * 11) / 100;
                grayPix[i++] = gray;
                sum += gray;
            }
        }
        /* 3.计算平均值, 计算进行灰度处理后图片的所有像素点的平均值 */
        int avg = sum / 64;
        /*
         * 4.比较像素灰度值,遍历灰度图片每一个像素,如果大于平均值记录为1,否则为0. 5.获取指纹
         */
        long figure = 0;
        for (i = 63; i >= 0; i--) {
            long b = (long) (grayPix[i] > avg ? 1 : 0);
            figure |= b << i;
        }
        return figure;
    }

}

计算汉明距离:

public class HammingDistance {
    /**
     * 比较,计算汉明距离 如果不相同的数据位不超过5,就说明两张图片很相似;如果大于10,就说明这是两张不同的图片。
     * 
     * @param file1
     * @param file2
     * @return
     */
    public static int distance(long fg1, long fg2) {
        int distance = 0;
        long res = fg1 ^ fg2;
        for (int i = 0; i < 64; i++) {
            distance += (res >> i & 1);
        }
        return distance;
    }
}


测试代码:

@Test
public void test6() throws IOException {
    String find = "C:/imagetest/imgHash/bg2011072103.jpg";
    long finger = AHash.fingerprint(find);
    System.out.println(Long.toHexString(finger));
        
    String find2 = "C:/imagetest/imgHash/88/bg2011072103.jpg";
    long finger2 = AHash.fingerprint(find2);
    System.out.println(HammingDistance.distance(finger, finger2)+"<-->bg2011072103.jpg");
        
    String find3 = "C:/imagetest/imgHash/88/f.png";
    long finger3 = AHash.fingerprint(find3);
    System.out.println(HammingDistance.distance(finger, finger3)+"<-->f.png");
        
}

输出:

171f3f2343d3e3e7
0<-->bg2011072103.jpg
32<-->f.png

和文中的结果基本一致,hash值略有不同。

拓展

    文中接着说到,实际应用中,往往采用更强大的pHash算法和SIFT算法,可以识别图片的变形,只要变形不超过25%,就能匹配原图,原理基本一致,都是根据图片得到哈希值,再比较哈希。

还没有评论!
54.158.194.80