圖像相似度計(jì)算算法分析

王朝卿 沈小林 李磊

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

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

中圖分類號： TN911.73?34; TP391.4 ? ? ? ? ? ? ? ? ?文獻(xiàn)標(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 ?引 ?言

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

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

1 ?基于灰度直方圖的圖像相似度計(jì)算

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

1.1 ?灰度直方圖

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

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

1.2 ?余弦相似度

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

1.3 ?算法描述

具體算法過程如下：

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

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

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

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

5） 計(jì)算兩個(gè)向量的余弦相似度;

6） 判斷圖像的相似性。

2 ?基于特征點(diǎn)描述的圖像相似度計(jì)算

2.1 ?SIFT算法

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

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

2.2 ?算法描述

基于特征點(diǎn)匹配的SIFT算法步驟如下：

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

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

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

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

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

③ 極值點(diǎn)檢測

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

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

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

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

3） 方向分配

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

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

為增強(qiáng)算法魯棒性，只保留峰值大于主方向峰值80%的方向?yàn)殛P(guān)鍵點(diǎn)的輔方向。完成上述過程，即獲得SIFT特征點(diǎn)。

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

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

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

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

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

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

5） 特征向量匹配

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

6） 相似度計(jì)算

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

3 ?實(shí)驗(yàn)結(jié)果分析

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

圖1 ?實(shí)驗(yàn)圖像

3.1 ?實(shí)驗(yàn)一

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

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

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

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

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

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