王朝卿 沈小林 李磊

摘 ?要： 針對灰度直方圖提取算法在計算圖像相似度時，受顏色分布等外界因素干擾較大的問題，提出基于特征點匹配的SIFT算法。其可通過構(gòu)建尺度空間提取特征關(guān)鍵點，求解匹配度來彌補傳統(tǒng)算法在計算圖像相似度時的局限性。實驗結(jié)果表明，相比于傳統(tǒng)算法，SIFT算法能夠通過匹配更多的特征點，從而更好地計算圖像的相似度;對于一組相似圖片，通過SIFT算法能提取出308個特征點，圖片相似度可達63%。

關(guān)鍵詞： 圖像識別; 圖像相似度; 灰度直方圖; 特征點匹配; 關(guān)鍵點; 尺度空間

中圖分類號： TN911.73?34; TP391.4 ? ? ? ? ? ? ? ? ?文獻標(biāo)識碼： A ? ? ? ? ? ? ? ? 文章編號： 1004?373X（2019）09?0031?04

Analysis on image similarity calculation algorithm

WANG Chaoqing1， SHEN Xiaolin1， LI Lei2

（1. School of Electrical and Control Engineering， North University of China， Taiyuan 030051， China;

2. School of Software Engineering， University of Science and Technology of China， Hefei 230000， China）

Abstract： A SIFT algorithm based on feature point matching is proposed to solve the problem that the gray histogram extraction algorithm is heavily disturbed by external factors such as color distribution while calculating image similarity. It can make up for the limitation of traditional algorithm in calculating image similarity by constructing scale space， extracting feature key points and solving matching degree. The experimental results show that， in comparison with the traditional algorithm， the SIFT algorithm can accurately calculate the image similarity by means of matching more feature points; can extract 308 feature points for a group of similar images， and the image similarity can reach up to 63%.

Keywords： image identification; image similarity; gray histogram; feature point matching; key point; scale space

0 ?引 ?言

隨著計算機技術(shù)的不斷進步，圖像識別技術(shù)也得到飛速發(fā)展，并廣泛應(yīng)用于國防科技、交通等領(lǐng)域中[1?3]。而圖像相似度的計算是圖像識別中的重要組成部分。

傳統(tǒng)相似度計算方法根據(jù)圖像生成的灰度直方圖判斷是否相似[4]，但存在受顏色分布等因素干擾明顯的問題。本文采用特征點匹配算法[5]解決上述問題。因其實際應(yīng)用廣泛，諸多學(xué)者在相關(guān)理論研究中投入大量精力，并獲得巨大成果。代表性的有Harris算法[6]、GLOH算法[7]和SIFT算法[8]等。通過實驗采用傳統(tǒng)算法與基于SIFT算法計算圖像相似度并進行比較，分析兩者優(yōu)劣。

1 ?基于灰度直方圖的圖像相似度計算

基于灰度直方圖的圖像相似度計算過程簡潔、執(zhí)行效率高且不需對圖像進行過多的預(yù)處理，已廣泛應(yīng)用于圖像識別等領(lǐng)域。

1.1 ?灰度直方圖

灰度直方圖[9]反映出圖像中出現(xiàn)不同灰度級像素的個數(shù)。若將圖像總像素亮度（灰度級別）視為隨機變量，則其分布情況就表示圖像的統(tǒng)計特性。

假設(shè)任一圖像中變量[r]為灰度級，對其作歸一化處理后，[r∈[0，1]]且為隨機變量。若[r]是連續(xù)的，則可用概率分布函數(shù)[P（r）]表示原始圖像的灰度分布，直方圖與[P（r）]相對應(yīng)，概率密度函數(shù)[p（r）]則為直方圖的累積和，也就是[p（r）]的積分，其公式分別如下：

1.2 ?余弦相似度

根據(jù)圖像的灰度直方圖，將圖像轉(zhuǎn)換為向量形式，通過兩向量之間的余弦值計算圖像的相似度[10]：

1.3 ?算法描述

具體算法過程如下：

1） 將兩張圖像大小調(diào)整為同樣大小;

2） 獲得兩張圖像的灰度直方圖;

3） 將圖像每4個灰度級劃分成一個區(qū)，共64個區(qū);

4） 對每個區(qū)的4個值進行求和運算，得到64個值，以此作為該圖像的向量[11];

5） 計算兩個向量的余弦相似度;

6） 判斷圖像的相似性。

2 ?基于特征點描述的圖像相似度計算

2.1 ?SIFT算法

SIFT（Scale Invariant Feature Transform，尺度不變特征轉(zhuǎn)換）用于描述影像中的局部特征。該算法可有效查找關(guān)鍵特征點，避免圖形變換、光照和遮擋等因素影響。

SIFT圖像匹配算法通過構(gòu)建尺度空間，在該空間內(nèi)檢測局部極值點，消除偏移量過大的極值點及邊緣響應(yīng)，獲得關(guān)鍵點，以此確定主方向，生成關(guān)鍵點描述子，并依據(jù)特征描述符向量進行匹配[5?12]。

2.2 ?算法描述

基于特征點匹配的SIFT算法步驟如下：

1） 構(gòu)建尺度空間

① 構(gòu)建高斯金字塔

高斯卷積核是實現(xiàn)尺度變換[13]的唯一線性核，一幅圖像的尺度空間被定義為對其做可變尺度的高斯卷積：

對于灰度圖像，利用不同大小的[σ]做高斯平滑。同時，將采樣圖像劃分為不同組，每組有若干圖像。一般情況下，上一組圖像的長寬取下一組的2倍。

② 構(gòu)建高斯差分金字塔

③ 極值點檢測

將待檢測圖像與前后兩張圖像共26個鄰域像素點的灰度值逐一比較，檢測極值。

2） 關(guān)鍵點定位

離散空間的極值點并非真正的極值點，為提高關(guān)鍵點的穩(wěn)定性，需擬合尺度空間函數(shù)。利用Taylor展開式求得極值偏移量。當(dāng)任一維度的偏移量大于0.5時，改變當(dāng)前關(guān)鍵點的位置，并在新的位置反復(fù)擬合直至收斂。若超出設(shè)定迭代次數(shù)或偏移量絕對值過小，存在不穩(wěn)定點，可將該點視為非極值點。

此外，高斯差分函數(shù)的邊緣效應(yīng)[14]使特征點在某方向上有較大的曲率，而在垂直方向的主曲率很小，可將該點刪除。

3） 方向分配

根據(jù)高斯差分金字塔中關(guān)鍵點的局部特性計算結(jié)果，可為每一點指定方向，使其具備旋轉(zhuǎn)不變性。梯度模型和方向如下：

式中：[x，y]的正方向分別為右和上;[L]為關(guān)鍵點映射在尺度空間的灰度值;[m（x，y）]為梯度幅值;[θ（x，y）]為關(guān)鍵點所處梯度方向的弧度。按逆時針方向?qū)?60°依次劃分為36個區(qū)域，獲取不同方向的直方圖。可按照[σ=1.5_octv]的高斯分布和[3σ]原則將[m（x，y）]加成，鄰域窗口半徑為3×1.5[σ][_]octv。

為增強算法魯棒性，只保留峰值大于主方向峰值80%的方向為關(guān)鍵點的輔方向。完成上述過程，即獲得SIFT特征點。

4） 關(guān)鍵點特征描述

在關(guān)鍵點尺度空間內(nèi)4×4窗口中計算8個方向的梯度信息，共128維向量表征，即為關(guān)鍵點的描述子。具體步驟如下：

① 因劃分的16個區(qū)域均為[3σ_octv]像素，則其半邊長為[2×3σ_octv]，根據(jù)線性插值法，將半邊長設(shè)為（4+1）×[3σ_octv2]?？紤]到旋轉(zhuǎn)因素，實際計算區(qū)域半徑為：

② 坐標(biāo)軸旋轉(zhuǎn)至關(guān)鍵點方向[15]。

③ 計算三維坐標(biāo)與鄰域空間的距離，按距離的倒數(shù)求權(quán)重，并將梯度幅值按權(quán)重分配到鄰域空間中。

④ 將128維向量歸一化。同時，描述子按對應(yīng)的高斯金字塔尺度大小排序。

5） 特征向量匹配

本文采用最近鄰距離法匹配特征向量[16]。根據(jù)采樣點與兩個鄰域點的特征向量，計算兩者的歐氏距離之比，并同設(shè)定的閾值0.6進行比較。若比值小于該閾值，則認(rèn)定特征向量匹配成功。

6） 相似度計算

計算匹配成功的特征點個數(shù)占圖像中總特征點個數(shù)的百分比，即為圖像的相似度。

3 ?實驗結(jié)果分析

為驗證兩種算法計算圖像相似度的效果，本文在PC機上編寫Matlab程序，對兩組圖像進行相似度分析，如圖1所示。其中圖1a）和圖1b）為相似圖像，圖1c）和圖1d）為不同圖像。

圖1 ?實驗圖像

3.1 ?實驗一

計算兩組圖像的灰度直方圖如圖2～圖5所示。

通過灰度直方圖可知，灰度值集中于前半部分，不難發(fā)現(xiàn)四張圖像主要為暗色調(diào)，與肉眼觀察一致。實驗一的結(jié)果如表1所示。

實驗結(jié)果表明，當(dāng)顏色分布相差不大時，圖像的灰度直方圖較為接近。因此，利用該方法對顏色分布相近的不同圖像進行相似度判斷時存在誤判。

圖2 ?圖1a）的灰度直方圖

圖3 ?圖1b）的灰度直方圖

圖4 ?圖1c）的灰度直方圖