OpenCV圖像哈希計算及漢明距離的計算

OpenCV均值哈希與感覺哈希計算，比對圖像相似度，當計算出來的漢明距離越大，圖像的相似度越小，漢明距離越小，圖像的相似度越大，這種沒有基于特征點的圖像比對用在快速搜尋引擎當中可以有效的進行圖像搜尋.

離散傅裡葉變換的推導 具體代碼和OpenCV代碼請移步到

部落格

下面附上Mathmetica代碼

設X (n) 是一個長度為M的有限長序列，則定義X (n) 的N點離散傅裡葉變換為

X (k) = DFT[x (n)] = 
\!\(\*UnderscriptBox[
OverscriptBox[\(\[Sum]\), \(N - 1\)], \(K = 0\)]\) 
   x (n) Subscript[W, N]^kn , k = 0, 1, ..., N - 1
X (k) 的傅裡葉逆變換為
x (n) = IDFT[X (k)] = 
\!\(\*UnderscriptBox[
OverscriptBox[\(\[Sum]\), \(N - 1\)], \(k = 0\)]\)X (k) Subscript[
    W^-kn, N], k = 0, 1, 2, 3, 4, ...., N - 1
式中, Subscript[W, N] = 
 e^(-j*2 \[Pi]/N) N稱為DFT變換區間長度，N \[GreaterSlantEqual] 
 M通常稱 (1) 式和 (2) 式為離散傅裡葉變換對。
下面來證明IDFT[X (k)] 的唯一性
把 (1) 代入 (2) 有
IDFT[X (k)] = (1/N) 
\!\(\*UnderscriptBox[
OverscriptBox[\(\[Sum]\), \(N - 1\)], \(k = 0\)]\)[
\!\(\*UnderscriptBox[
OverscriptBox[\(\[Sum]\), \(N - 1\)], \(m = 0\)]\) 
       x (m) Subscript[W^mk, N]] Subscript[W^-kn, N] =
  
\!\(\*UnderscriptBox[
OverscriptBox[\(\[Sum]\), \(N - 1\)], \(m = 0\)]\)x (m) (1/N) 
\!\(\*UnderscriptBox[
OverscriptBox[\(\[Sum]\), \(N - 1\)], \(k = 0\)]\)Subscript[W^(
     k (m - n)), N]
(1/N) 
\!\(\*UnderscriptBox[
OverscriptBox[\(\[Sum]\), \(N - 1\)], \(k = 0\)]\)Subscript[W^(
   k (m - n)), N] = { 
\!\(\*OverscriptBox[
UnderscriptBox[\(\[Placeholder]\), \(0\ \ \ \ \ \ \ \ \ \ \ \ \ \ m \
\[NotEqual] n + MN, M為整數\)], \(1\ \ \ \ \ \ \ \ \ \ \ \ \ m = n + MN, 
     M為整數\)]\)  
    是以，在變換區間上滿足下式
     IDFT[X (k)] = x (n), 0 \[LessSlantEqual] n \[LessSlantEqual] N - 1
      (2) 式定義的離散傅裡葉變換是唯一的。           

感覺哈希

string p_hashCode(Mat src) {
    //第一步，轉換顔色空間，簡化圖像像素
    Mat img, dst;//初始化矩陣IO
    string rst(64, '\0');//初始化哈希值
    double dIdex[64];//初始化矩陣清單
    double mean = 0.0;//初始化均值
    int k = 0;//初始化矩陣行列計數
    //判斷圖像空間，當圖像空間為3位空間的時候轉換圖像空間為灰階矩陣
    if (src.channels() == 3) {
        cvtColor(src, src, CV_BGR2GRAY);
        img = Mat_<double>(src);
    } else {
        img = Mat_<double>(src);
    }

    // 第二步，縮放尺寸 
    //這裡将整個圖像縮放到變成一個8*8的圖像矩陣，漢明長度為8*8=64個位元組長度
    //最快速的去除高頻和細節，隻保留結構明暗的方法就是縮小尺寸。
    //将圖檔縮小到8x8的尺寸，總共64個像素。摒棄不同尺寸、比例帶來的圖檔差異。
    resize(img, img, Size(8, 8));

    // 第三步，離散餘弦變換，DCT系數求取
    //離散餘弦變換(DCT for Discrete Cosine Transform)是與傅裡葉變換相關的一種變換      
    //它類似于離散傅裡葉變換(DFT for Discrete Fourier Transform),但是隻使用實數
    dct(img, dst);

    /* 第四步，求取DCT系數均值（左上角8*8區塊的DCT系數）*/
    for (int i = 0; i < 8; ++i) {//疊代矩陣行
        for (int j = 0; j < 8; ++j) {//疊代矩陣列
            //第i行j列的圖像灰階值
            dIdex[k] = dst.at<double>(i, j);
            //計算均值,此均值相對于8*8矩陣的總像素點的均值
            mean += dst.at<double>(i, j) / 64;
            k++;
        }
    }

    // 第五步，計算哈希值
    //周遊像素矩陣，當矩陣的灰階值大于均值的時候哈希為1，當矩陣的灰階值小于均值     
    //的時候哈希為2
    for (int i = 0; i < 64; ++i) {
        if (dIdex[i] >= mean) {
            rst[i] = '1';
        } else {
            rst[i] = '0';
        }
    }
    return rst;
}           

均值哈希計算

string a_hashCode(Mat src) {
    string rst(64, '\0');
    Mat img;
    if (src.channels() == 3)
        cvtColor(src, img, CV_BGR2GRAY);
    else
        img = src.clone();
     //第一步，縮小尺寸。
     //将圖檔縮小到8x8的尺寸，總共64個像素
    resize(img, img, Size(8, 8));
    /* 第二步，簡化色彩(Color Reduce)。
       将縮小後的圖檔，轉為64級灰階。*/
    uchar *pData;
    for (int i = 0; i < img.rows; i++) {
        //取出矩陣每一行的資料
        pData = img.ptr<uchar>(i);
        for (int j = 0; j < img.cols; j++) {
            //将矩陣每一列的資料除以4
            pData[j] = pData[j] / 4;
        }
    }
    //第三步，計算平均值。
    //計算所有64個像素的灰階平均值.
    int average = mean(img).val[0];
    //第四步，比較像素的灰階。
    //将每個像素的灰階，與平均值進行比較。大于或等于平均值記為1,小于平均值記為0 
    Mat mask = (img >= (uchar) average);
    //第五步，計算哈希值
    int index = 0;
    for (int i = 0; i < mask.rows; i++) {
        pData = mask.ptr<uchar>(i);
        for (int j = 0; j < mask.cols; j++) {
            if (pData[j] == 0)
                rst[index++] = '0';
            else
                rst[index++] = '1';
        }
    }
    return rst;
}           

計算漢明距離

/**
漢明距離函數取哈希字元串進行比對，兩字元串長度必須相等才能計算準确的距離
*/
int HanmingDistance(string &str1, string &str2) {
    //判斷當兩個字元串的長度是否相等
    if ((str1.size() != 64) || (str2.size() != 64))
        return -1;
    int difference = 0;
    //周遊字元串比較兩個字元串的0與1的不相同的地方，不相同一次就長度增加1進而計   
    //算總距離
    for (int i = 0; i < 64; i++) {
        if (str1[i] != str2[i])
            difference++;
    }
    return difference;
}