基于感知哈希算法的相似图片识别

April 8, 2016
JavaAlgorithm

最近几年,谷歌和百度等搜索引擎都上线了一种以图搜图的功能,用户可以通过上传一张图片,搜索引擎可以检索出来与其相似的图片,这篇文章将介绍一种算法来对相似图片进行识别。

baidustu

感知哈希算法(Perceptual hash algorithm)

它的作用是对每张图片生成一个”指纹”字符串,然后比较不同图片的指纹。如果结果越接近,就说明图片越相似。这个算法最大的优势就是快速。但是就结果来看只能识别非常相近的图片,并且两张图片的比例要尽可能一样,比如两张图片中都画着一个iPhone,但是图1是4:3的比例,图2
是 4:5的比例的话,这个算法可能会判出较低的相似度,文章结尾有我想出的提升方法。

这个算法有以下步骤:

1.压缩图片

对于识别的图片,把他压缩成8×8像素的图片,在这个过程中,图片的所有细节会丢失,只留下大概的颜色。

8x8

代码实现:

  1. public static BufferedImage resizeImg(BufferedImage img,int width,int height){
  2. int inputWidth = img.getWidth();
  3. int inputHeight = img.getHeight();
  4. int xJump = inputWidth/width;
  5. int yJump = inputHeight/height;
  6. BufferedImage outputImg = new BufferedImage(width,height,BufferedImage.TYPE_INT_RGB);
  7. int counter = 0;
  8. for (int i=0;i<inputHeight;i = i+yJump){
  9. for (int j=0;j<inputWidth; j=j+xJump){
  10. int rgb = img.getRGB(j,i);
  11. if (counter!=width*height){
  12. outputImg.setRGB(counter%width,counter/height,rgb);
  13. counter++;
  14. }
  15. }
  16. }
  17. }

2. 灰度转换

将转换后的64像素逐个分析,通过每个像素的RGB值算出灰度值得到一个8×8的灰度图片

gray

代码实现:

  1. private static int getGray(int rgb){
  2. int a = rgb & 0xff000000;//将最高位(24-31)的信息(alpha通道)存储到a变量
  3. int r = (rgb >> 16) & 0xff;//取出次高位(16-23)红色分量的信息
  4. int g = (rgb >> 8) & 0xff;//取出中位(8-15)绿色分量的信息
  5. int b = rgb & 0xff;//取出低位(0-7)蓝色分量的信息
  6. rgb = (r * 77 + g * 151 + b * 28) >> 8; // NTSC luma,算出灰度值
  7. return a | (rgb << 16) | (rgb << 8) | rgb;//将灰度值送入各个颜色
  8. }

3. 计算灰度平均值

将所有64个像素的灰度值相加并且除以64,得到灰度的平均值

代码实现:

首先设计一个方法来得到64个像素灰度的数组:

  1. private static ArrayList getGrayList(BufferedImage img){
  2. ArrayList list = new ArrayList();
  3. for (int i=0;i<img.getWidth();i++){
  4. for (int j=0;j<img.getHeight();j++){
  5. int rgb = img.getRGB(i,j);
  6. int gray = getGray(rgb);
  7. list.add(gray);
  8. }
  9. }
  10. return list;
  11. }

之后通过调用以下代码来计算平均值

  1. private static int getGrayAvg(ArrayList list){
  2. int totalGray = 0;
  3. for (int i=0;i<list.size();i++){
  4. totalGray += (int)list.get(i);
  5. }
  6. int avgGray = totalGray/list.size();
  7. return avgGray;
  8. }

4. 计算哈希值

使用灰度平均值来和每个像素的灰度值进行比较,若当前像素的灰度值比平均值大,则记为1,反之几位0。这一过程完成后将会得到一个64位的01字符串,这个字符串就是图片的“指纹”了,只要通过对不同图片的指纹比较就可以得出图片是否相似。

imgcompare

代码实现:

  1. public static String generateHash(BufferedImage img){
  2. String hashVal = "";
  3. ArrayList list = getGrayList(img);
  4. int avgGray = getGrayAvg(list);
  5. for (int i=0;i<list.size();i++){ if ((int)list.get(i)>=avgGray){
  6. hashVal += "1";
  7. }else {
  8. hashVal += "0";
  9. }
  10. }
  11. return hashVal;
  12. }

5.计算汉明距离

两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说,它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。

比如: Mike 和 Mika 的汉明距离就是 1 ,
从字符串Mika变成Mike需要改变最后一个字符a为e。00001111和10001110的汉明距离为2。

得到两个64位长度的哈希值后,计算他们的汉明距离,如果汉明距离小于15的话就说明图片有着较高的相似度了。

diatance

代码实现:

  1. public static int getDistance(BufferedImage img1, BufferedImage img2){
  2. String hash1 = ImageUtil.generateHash(img1);
  3. String hash2 = ImageUtil.generateHash(img2);
  4. int distance = 0;
  5. for (int i=0 ; i<hash1.length();i++){
  6. if (hash1.charAt(i) != hash2.charAt(i)){
  7. distance++;
  8. }
  9. }
  10. System.out.println("Distance: "+distance);
  11. double similarity = (64-distance)/64.0;
  12. System.out.println("Similarity: "+similarity*100+"%");
  13. return distance;
  14. }

img-compare

改进措施

测试了几张图片,发现在某些情况下效果并不是非常的好,和开篇所说的一样,这个算法收图片比例影响很大,并且不管多大的图片只保留了64个像素显得细节丢失的太多了,之前写过一篇关于高斯模糊算法的文章。可以通过高斯模糊算法来获取那64个像素的模糊像素,这样,即使还是压缩成64个像素,但是每个像素却包含了原本那个像素周围像素的信息,这样在进行处理的效果应该会更好。

可以在GitHub上下载这个项目:点击前往

Comments

July 21, 2018 at 10:52 am

There are no comments

keyboard_arrow_up