感知哈希算法型 -- 找出相似的圖片

Google 圖片搜索功能

        在谷歌圖片搜索中, 用戶可以上傳一張圖片, 谷歌顯示因特網中與此圖片相同或者相似的圖片.

        比如我上傳一張照片試試效果:

原理講解

        參考Neal Krawetz博士的這篇文章, 實現這種功能的關鍵技術叫做"感知哈希算法"(Perceptual Hash Algorithm), 意思是為圖片生成一個指紋(字符串格式), 兩張圖片的指紋越相似, 說明兩張圖片就越相似. 但關鍵是如何根據圖片計算出"指紋"呢? 下面用最簡單的步驟來說明一下原理:

第一步 縮小圖片尺寸

        將圖片縮小到8x8的尺寸, 總共64個像素. 這一步的作用是去除各種圖片尺寸和圖片比例的差異, 只保留結構、明暗等基本信息.

       

第二步 轉為灰度圖片

         將縮小后的圖片, 轉為64級灰度圖片.

       

第三步 計算灰度平均值

         計算圖片中所有像素的灰度平均值

第四步 比較像素的灰度

        將每個像素的灰度與平均值進行比較, 如果大于或等于平均值記為1, 小于平均值記為0.

第五步 計算哈希值

         將上一步的比較結果, 組合在一起, 就構成了一個64位的二進制整數, 這就是這張圖片的指紋.

第六步 對比圖片指紋

        得到圖片的指紋后, 就可以對比不同的圖片的指紋, 計算出64位中有多少位是不一樣的. 如果不相同的數據位數不超過5, 就說明兩張圖片很相似, 如果大于10, 說明它們是兩張不同的圖片.

代碼實現 (C#版本)

        下面我用C#代碼根據上一節所闡述的步驟實現一下.

using System;
using System.IO;
using System.Drawing;

namespace SimilarPhoto
{
    class SimilarPhoto
    {
        Image SourceImg;

        public SimilarPhoto(string filePath)
        {
            SourceImg = Image.FromFile(filePath);
        }

        public SimilarPhoto(Stream stream)
        {
            SourceImg = Image.FromStream(stream);
        }

        public String GetHash()
        {
            Image image = ReduceSize();
            Byte[] grayValues = ReduceColor(image);
            Byte average = CalcAverage(grayValues);
            String reslut = ComputeBits(grayValues, average);
            return reslut;
        }

        // Step 1 : Reduce size to 8*8
        private Image ReduceSize(int width = 8, int height = 8)
        {
            Image image = SourceImg.GetThumbnailImage(width, height, () => { return false; }, IntPtr.Zero);
            return image;
        }

        // Step 2 : Reduce Color
        private Byte[] ReduceColor(Image image)
        {
            Bitmap bitMap = new Bitmap(image);
            Byte[] grayValues = new Byte[image.Width * image.Height];

            for(int x = 0; x<image.Width; x++)
                for (int y = 0; y < image.Height; y++)
                {
                    Color color = bitMap.GetPixel(x, y);
                    byte grayValue = (byte)((color.R * 30 + color.G * 59 + color.B * 11) / 100);
                    grayValues[x * image.Width + y] = grayValue;
                }
            return grayValues;
        }

        // Step 3 : Average the colors
        private Byte CalcAverage(byte[] values)
        {
            int sum = 0;
            for (int i = 0; i < values.Length; i++)
                sum += (int)values[i];
            return Convert.ToByte(sum / values.Length);
        }

        // Step 4 : Compute the bits
        private String ComputeBits(byte[] values, byte averageValue)
        {
            char[] result = new char[values.Length];
            for (int i = 0; i < values.Length; i++)
            {
                if (values[i] < averageValue)
                    result[i] = '0';
                else
                    result[i] = '1';
            }
            return new String(result);
        }

        // Compare hash
        public static Int32 CalcSimilarDegree(string a, string b)
        {
            if (a.Length != b.Length)
                throw new ArgumentException();
            int count = 0;
            for (int i = 0; i < a.Length; i++)
            {
                if (a[i] != b[i])
                    count++;
            }
            return count;
        }
    }
}

        谷歌服務器里的圖片數量是百億級別的, 我電腦里的圖片數量當然沒法比, 但以前做過爬蟲程序, 電腦里有40,000多人的頭像照片, 就拿它們作為對比結果吧! 我計算出這些圖片的"指紋", 放在一個txt文本中, 格式如下.

        用ASP.NET寫一個簡單的頁面, 允許用戶上傳一張圖片, 后臺計算出該圖片的指紋, 并與txt文本中各圖片的指紋對比, 整理出結果顯示在頁面中, 效果如下:

本文地址: http://www.cnblogs.com/technology/archive/2012/07/12/Perceptual-Hash-Algorithm.html