一種面向圖像相似度計算的改進哈希算法

夏雨軒，曲海成，關茜文

（遼寧工程技術大學 軟件學院，遼寧 葫蘆島 125105）

0 引 言

隨著互聯網的飛速發展，多媒體技術的廣泛應用，互聯網中的圖像呈爆炸式增長，數量達到上千億級。針對在海量數據庫中尋找相似圖像這一問題場景，常見的做法是先進行特征提取或者指紋生成，再計算圖像的相似度。現有技術中有基于指紋生成的感知哈希（aHash）、均值哈希（pHash）、差異值哈希（dHash）算法，有基于特征提取的基于局部不變性的SIFT算法，基于深度學習的神經網絡模型。這些技術均能滿足一定程度的需要，對于所述算法和模型，吳迎采用基于SIFT和最臨近匹配算法對圖像相似度進行計算，精度略優于3種Hash算法。徐夢瑩等人采用KAZE與aHash結合的方法對相似圖像進行匹配，正確率較高。胡新榮等人采用改進Hash算法對圖像相似度進行計算，魯棒性較強。趙學敏等人采用基于深度學習的以圖搜圖技術，提供了神經網絡模型提取圖片特征信息并用于照片檔案管理的思路。陳世榮等人采用改進的aHash對遙感圖像格網進行相似度計算，提高了檢測圖像變化的精度。

Hash算法對圖像的縮放、光照等變換的適應性較差。SIFT算法在求主方向階段太過依賴圖像局部像素的梯度方向，有可能使找到的主方向不準確，而后面的特征向量以及匹配嚴重依賴主方向，一旦有偏差效果會顯著下降，且利用高斯濾波構建線性尺度空間來提取圖片特征信息時容易造成圖像邊界清晰度下降和原始圖像的細節丟失等問題，同時，圖像金字塔的層數難于設定：如果層數少，會在匹配時出現誤差；如果層數過多，則會造成keypointer數量過大，帶來龐大的計算負擔。而對于深度神經網絡學習圖像的方法，需要大量數據集去訓練模型，且檢索速度慢、適用場景固定。

在日常應用中，同一個物體會有多種不同角度、不同亮度等的圖像表達，這些不同會改變圖像的具體表示數據，但并不改變圖像的視覺本質內容，對于這類圖像，通過傳統算法處理得到的指紋應基本相同。

由上述論文的理論研究與支撐，針對圖像匹配中相似度計算出現的問題，本文提出一種新的圖像相似度計算方法，具有準確率高、無需訓練、可移植性強等優點，在主觀視覺評價和客觀指標上均取得了較好的結果。

1 幸存哈希算法

本文提出的幸存哈希算法是一種基于無監督學習的哈希方法，無需大量帶標簽的數據集，無需考慮圖像尺寸大小不同而造成的影響，通過將每2個幸存點間距離匯總進一個數組，全相聯映射計算2個數組間所有距離的比值，并設定閾值遍歷取滿足條件的值的個數，通過公式計算圖像相似度，達到匹配的最終目的。圖1為幸存哈希算法的基本結構。

圖1 幸存哈希算法架構Fig.1 Survival hashing algorithm architecture diagram

1.1 Gabor小波濾波器

在圖像處理中，Gabor函數是一個用于邊緣提取的線性濾波器。Gabor濾波器的頻率和方向表達同人類視覺系統類似，與人類的視覺細胞對外界的刺激做出應激反應十分相似。在空間域中，一個二維Gabor濾波器是一個由正弦平面波調制的高斯核函數，可以增強邊緣以及峰、谷、脊輪廓等底層圖像特征，所以可以用來增強圖片關鍵部位的局部特征，提高圖片邊緣輪廓的清晰度。

二維Gabor小波的函數表達式為：

其中，k可由如下方式計算得到：

Gabor小波濾波器和脊椎動物視覺皮層感受野響應的比較見圖2。圖2中，第一行代表脊椎動物的視覺皮層感受野，第二行是Gabor小波濾波器，第三行是兩者的殘差。可見兩者相差極小。Gabor小波濾波器的這一性質，使其在視覺領域中經常被用在圖像的預處理中。

圖2 Gabor小波濾波器和脊椎動物視覺皮層感受野響應的比較Fig.2 Comparison between Gabor wavelet filter and vertebrate visual cortex receptive field response

研究發現，Gabor小波對于光照的敏感度較低，對光照有很好的適應性，同時可以容忍圖片一定程度上由于旋轉和變形而造成的誤差，因此Gabor小波濾波器十分適合紋理表達、分離與輪廓提取。N-Gabor輪廓圖如圖3所示。

圖3 N-Gabor輪廓圖Fig.3 N-Gabor skeleton map

1.2 固定閾值二值化

圖像經過Gabor小波濾波器后可以被清晰地看見輪廓，但輪廓圖有256個灰度等級，不方便進一步操作，故需對輪廓圖進行二值化處理。圖4為NGabor圖像的灰度直方圖。

圖4 N-Gabor圖像的灰度直方圖Fig.4 N-Gabor gray scale histogram of images

二值化的算法分為固定閾值和自適應閾值，由N-Gabor圖像的灰度直方圖可知，若使用自適應二值化算法，可能導致2張形狀完全不同、顏色近似的圖像在下面的步驟中被提取出位置基本一致的幸存點，因此使用固定閾值二值化算法，以127為固定閾值，選定像素灰度值小于127則定義為0，反之則定義為1。圖5為N-Gabor圖像經過固定閾值二值化處理后得到的N-G-binary圖像。

圖5 N-G-binary圖像Fig.5 N-G-binary image

1.3 幸存點定位

上述步驟得到的圖的大小取決于原圖分辨率，若圖片過大，會影響計算效率，且圖中灰度值為0的點存在十分密集的情況，故進行降采樣與類似池化的操作。

將圖片進行高斯模糊后刪除偶數行與列，進行上述操作若干次，直至圖像大小變更為32×32；從左上角第一個像素開始，向右下角逐行進行遍歷，每出現一個灰度值為0的點，建立一個以該點為左上角的矩陣，矩陣長為8，寬為8，其中為N-Gbinary圖像寬度，為N-G-binary圖像高度。得到上述矩陣后，將除左上角像素外其余所有像素灰度值設置為1，即將N-G-binary圖像中灰度值為0的點數量限制在64個以內，最終得到的灰度值為0的點如同幸存下來的點，故取名為幸存點。

1.4 幸存點測距與指紋生成

經上述步驟對圖像進行處理后，從左上角第一個像素開始，向右下角逐行進行遍歷，對得到的圖像中所有灰度值為0的點間進行全相聯映射做比，得到的最多63個距離即為該圖片的指紋。

1.5 指紋比較

其中，為前文所述比值的個數。

2 實驗結果與分析

為了驗證本文算法的可靠性和實用性，本文選用了三維建筑物正面圖像、側面圖像及其經Retinex增強圖像、經典Mikolajczyk標準圖像集中旋轉變換（boat）組，共5張圖像，做3組實驗，分別對5組圖像使用感知哈希算法、均值哈希算法、差異值哈希算法、幸存哈希算法計算其相似度。樣本圖像如圖6所示。

圖6 實驗中所用的樣本圖像Fig.6 Sample images used in the experiment

本文選用的實驗平臺是Windows10操作系統家庭中文版，配置為Intel（R）Core（TM）i5-10300H CPU，16 GB內存，編程環境為Anaconda Spyder，基于OpenCV進行實驗，選擇算法準確率和算法的運行時間作為評價指標，來對本文算法進行分析評估，實驗結果見表1、表2。

表1 各算法在每組圖片上計算的結果Tab.1 Results calculated by each algorithm on each set of images%

表2 各算法在每組圖片上計算的時間Tab.2 Time calculated by each algorithm on each set of pictures s

由表1可知，對于視覺變換的圖像，本文算法計算得出的相似度僅次于均值哈希算法，與其差距甚微；對于光照變換的圖像，本文算法計算得出的相似度高達100%；對于旋轉變換的圖像，本文算法略遜色于均值哈希算法。可以推出本文算法對圖像的具體表示數據有較準確的判斷力，對視覺本質內容識別表現良好。

由表2可知，對于視覺變換和光照變換的圖像，本文算法運行效率高于其它3種算法；對于旋轉變換的圖像，本文算法表現稍差。

3 結束語

本文算法對于計算光照變換的圖像相似度，表現優異，但對于旋轉變換中視角變化大的圖像，效果欠佳，而且在比較光照變換的圖像過程中運行時間較長，這將是后續研究的重點。

本文從網上采集多組數據，同時也使用多種不同算法對圖片進行相似度計算，結果驗證本文算法具有和人類視覺神經高度相似的特性，對圖像多種幾何變換的適應性較強，確實提高了圖片相似度計算的準確率。