伯將軍，郭書軍，伍淳華

（1.北方工業(yè)大學(xué) 信息工程學(xué)院，北京 100144；2.北京郵電大學(xué) 信息安全中心，北京 100876）

基于內(nèi)容的圖像信息檢索是多媒體信息檢索領(lǐng)域中重要的組成部分，對圖像的內(nèi)容進行準(zhǔn)確快速的描述一直都是圖像檢索技術(shù)中研究的重點和難點。傳統(tǒng)的圖像特征提取方法，基本上是圍繞圖像的顏色、紋理、形狀和空間關(guān)系來展開的[1]。這些方法能部分地描述圖像的特征，但是得到的特征魯棒性很差，在遇到修改，甚至故意破壞后無法再檢索出相似的圖像。另外一類是基于變換域的不變特征描述方法，由于變換域的固有屬性，這一類算法通常難以抵抗對圖像的裁剪攻擊。

SIFT算法提取圖像的特征描述子作為圖像的摘要，特征描述子對圖像的局部特征有很強的描述能力，并且具有很強的魯棒性，對尺度縮放、旋轉(zhuǎn)、平移、仿射變換、光照變化、剪切、降維等修改有很好的魯棒性[2]。SIFT算法的提取的特征點多且穩(wěn)定，它通過多方法來實現(xiàn)特征點的提取，通過多尺度的特征點檢測能得到尺度不變性，通過對特征點進行梯度計算能得到旋轉(zhuǎn)不變性，特征點歸一化運算去除了光照變化的影響，豐富的特征點保證了在剪切過后的圖像也能有很高的識別率。但是SIFT算法本身有很高的算法復(fù)雜度，再加上精細(xì)的局部特征描述能力，得到的特征向量具有很高的維度，給匹配算法也帶來了很高的時間復(fù)雜度。針對這個問題，本文首先通過K-Means算法對SIFT算法豐富的特征點進行聚類，并合理控制聚類的參數(shù)以達到對特征點進行合理的過濾，過濾后的特征點通常具有豐富的梯度信息以保存特征點領(lǐng)域的圖像信息。在此基礎(chǔ)上，為了降低匹配算法的復(fù)雜度，將各特征點的梯度值進行過濾，保留主方向以壓縮特征信息。仿真實驗表明，以上方法大幅度裁減了SIFT描述子的描述空間，在保證圖像版權(quán)檢索準(zhǔn)確性的同時提高了算法的效率。

1 SIFT特征提取算法

1.1 特征提取

1.1.1 尺度檢測及計算空間極值點

應(yīng)用高斯卷積和可以在尺度空間搜索極值點，從而得到尺度不變性，定義[3]如下：

上式中：D為高斯差分核，G為高斯濾波函數(shù)，I為圖像，L為圖像與高斯差分核的卷積。

對輸入圖像進行增量式的高斯卷積，得到共o組，每組有s層的高斯金字塔。本文選取的值為：o=4，s=3。

對每個像素點在其DoG尺度空間的鄰域中搜索極值點，初步得到特征點的位置。領(lǐng)域范圍為同尺度的8個相鄰點和上下相鄰尺度對應(yīng)的9×2個點共26個點。先對極值點應(yīng)用DoG函數(shù)的二階泰勒展開式D（x）得到特征點位置和尺度坐標(biāo)，見式（3）。在后續(xù)處理中對極值點進行過濾。

其中 x=（x，y，σ）T，用來表示采樣點和特征點間的位置和尺度變化。令一階導(dǎo)為0，可得到特征點的位置偏移x?：

通過高斯差分函數(shù)的海塞矩陣舍去不穩(wěn)定的邊緣響應(yīng)點。

則邊緣檢測過程如下：

令α為H的最大特征值，β為最小特征值，且令α=γβ，則有：

1.1.2 為特征點分配方向

在高斯空間中，計算特征點的梯度的模和方向來獲取旋轉(zhuǎn)不變性。

其中，m為特征點的梯度的模，θ為特征點的方向。

此時，圖像的特征點檢測完畢，每個特征點的3個屬性：位置、尺度、方向已經(jīng)確定，其中一個特征點可能有多個方向，可以增加方向以增強匹配的魯棒性，減少方向以降低運算復(fù)雜度。

在完成計算特征點后，根據(jù)特征信息生成特征點描述子。以特征點為中心取8×8領(lǐng)域分割成2×2的窗口，將窗口內(nèi)各像素按高斯加權(quán)后歸入位置網(wǎng)格，窗口所有點對同一網(wǎng)格的貢獻之和作為描述子在此維中的值。將采樣點與特征點的相對方向生成方向直方圖，由于方向值為相對方向，所以特征描述子具有旋轉(zhuǎn)不變性，由此得到2×2×8=32維特征點的SIFT描述子。

高斯加權(quán)函數(shù)：

對特征描述子進行歸一化，以消除光照條件的影響，在某維度取值大于設(shè)定的閥值時，取閥值代入歸一化進行運算，得到對不均勻光照魯棒的描述子。

1.2 特征匹配

通常用歐氏距離作為SIFT描述子的距離函數(shù)[4]：

然后根據(jù)距離比率來決定是否匹配到特征點，即圖像A的特征點與圖像B的特征點中的最鄰近距離和次鄰近距離的比值小于設(shè)定的閥值ε時，此特征點匹配成功。即匹配條件為：

此處根據(jù)經(jīng)驗值設(shè)ε=0.44。

2 基于SIFT的圖像版權(quán)檢索

基于SIFT算法圖像版權(quán)檢索流程如下：1）計算局部極值點，2）過濾局部極值點，3）K-Means 聚類過濾，4）生成特征點梯度值，5）特征點梯度值過濾，6）生成描述子。其中步驟1）和4）保持與原SIFT一致，主要目的在于繼承原算法優(yōu)良的準(zhǔn)確性，步驟2）、3）和5）是以提高生成描述子效率而增加的處理過程，額外的處理過程會增加運算負(fù)擔(dān)，但是由于描述子的生成時間占SIFT特征提取的80%以上，如圖1所示，并且減少特征點個數(shù)能提高描述子的生成效率，所以通過額外的過濾運算來減少特征點的數(shù)量，以達到提高特征提取全過程的效率。

圖1 SIFT算法時間復(fù)雜度分析圖Fig.1 Figure of time complexity analysis

2.1 利用K-Means算法對特征點過濾

在計算得到局部極值點的坐標(biāo)集M，對此集合應(yīng)用KMeans聚類算法，過程如下：

1）從極值點集合M中任意選擇k個點作為初始聚類中心；

2）根據(jù)每個聚類對象（局部極值點）的質(zhì)心，計算每個對象與這些中心對象的距離；并根據(jù)最小距離重新對相應(yīng)對象進行劃分；

3）重新計算重新劃分過的聚類的質(zhì)心；

4）循環(huán)2）和3）直到每個聚類不再發(fā)生變化為止。

在上述過程中，有兩個決定聚類效果的因素，初始聚類點的個數(shù)k和步驟4）中迭代次數(shù)。首先，初始聚類點數(shù)的選擇由圖像的分辨率決定，因為分辨率高的圖像帶有的信息更多，所以初始聚類點數(shù)k滿足式（15）。

其次，為了兼顧運算效率和特征點的過濾比例，步驟2）和3）的迭代次數(shù)不多于3次。

2.2 特征點梯度值過濾

在SIFT算法中，每個特征點會擁有多個梯度信息，豐富的梯度信息能表達更詳細(xì)的圖像信息，但也會給運算帶來更大的負(fù)擔(dān)，于是本文對特征點的梯度信息進行過濾，過濾掉梯度的模值較小的方向，從而精簡特征點的維數(shù)，降低描述子生成的時間，如式（16）。

其中，m表示梯度的模，T表示梯度信息，TF為過濾的結(jié)果。

2.3 圖像描述子生成

為了進一步降低復(fù)雜度，提高運處效率，降低特征描述子的維數(shù)，在生成描述子時的取景窗選擇4×4的鄰域，將鄰域分成2×2的網(wǎng)格，計算網(wǎng)格內(nèi)采樣點與特征點的相對方向，通過高斯加權(quán)后歸并得到8值直方圖，所有點在同一值中的和即為這一維在描述子中的值，從而生成2×2×8共32維的特征描述子。生成的描述子維數(shù)相對原始SIFT算法的128維，復(fù)雜度大幅下降，但高維度向量的匹配運算復(fù)雜度較高，這時通過PCA向量主成份分析，來使得向量的匹配效率得到進一步提高。

圖2顯示了SIFT算法的特征提取結(jié)果和本文算法特征提取結(jié)果，在左圖中有898個局部極值點，得到的特征向量一共有5 854個。右圖中的算法裁減之后，局部極值點為194個，得到的特征向量一共有520個，描述空間大幅減小，運算效率得到提高。在對圖像庫進行檢索過程中，為了進一步提高運算效率，對特征庫建立基于K-D樹的索引，使用BBF（Best-Bin-First）得到K-D樹的k鄰近，其中k取2。采取近似算法不是總能得到最佳結(jié)果，但是會大幅提高速度。

圖2 特征值裁減前后對比Fig.2 Eigenvalues before and after reduction

3 仿真實驗及分析

根據(jù)前文中描述的特征點裁減，通過仿真比較算法的有效性，本試驗比較的指標(biāo)為查全率，查準(zhǔn)率和查找時間，本實驗采用WINDOWS平臺，1 G內(nèi)存，Intel Cure 2 Duo E7500處理器。采用Corel1000圖庫，并采用StirMark?基準(zhǔn)測試程序獲得各圖像的修改樣本[7]。

檢索過程通過C++程序?qū)崿F(xiàn)的測試平臺進行，測試檢索過程中的所有性能指標(biāo)為目的。檢索以未修改的圖像作為檢索條件，以修改過的所有圖像組成的圖像庫作為檢索數(shù)據(jù)庫。原始圖像由Corel1000數(shù)據(jù)庫中1 000幅圖像組成，通過StirMark修改得到的圖像數(shù)據(jù)庫共115 000幅圖像。通過算法裁減過后，特征點數(shù)量點也有大幅下降，這樣匹配的特征點數(shù)也相應(yīng)減少，這樣將影響到圖像的匹配性能，提取特征點的時間和匹配圖像需要的時間。匹配結(jié)果樣例如圖3所示，圖中顯示了圖像修改的主要類型，以及特征點數(shù)量，同時還包含了匹配特征點數(shù)量。匹配的準(zhǔn)確性由查全率Pr和查準(zhǔn)率Pc來衡量，查找時間由每種修改平均值得到。如式（18）和式（19）所示。

圖3 特征提取和匹配的對比Fig.3 Comparison of feature extraction and matching

（說明：①仿射變換；②總面積濾波；③剪切50%；④JPEG壓縮，質(zhì)量因數(shù)25；⑤9領(lǐng)域中值濾波；⑥高斯白噪聲20 dB；⑦尺度變化縮小到50%；⑧旋轉(zhuǎn)15°；⑨剪切旋轉(zhuǎn)2°。括號的格式為：提取的特征點/匹配的特征點。圖3的上部為裁減前的特征點，圖3的下部為裁減之后生成特征點。）

由SIFT算法的匹配原則，本文放寬對匹配的限制，從修改后的圖像中提取的特征點數(shù)為N，當(dāng)匹配點數(shù)M滿足公式M>N*10%時[8]，圖像匹配成功。由表1中的數(shù)據(jù)統(tǒng)計了各種修改類型對圖像處理后的檢索結(jié)果，結(jié)果的優(yōu)劣由查全率和查準(zhǔn)率來體現(xiàn)，表中數(shù)據(jù)顯示，通過裁減后的算法在匹配性能有所下降，表現(xiàn)在一幅圖像中特征點的匹配點比例降低了4%～18%，由于算法本身的匹配性能，匹配比例的下降對查全率和查準(zhǔn)率的影響很小，在裁減前的查全率和查準(zhǔn)率分別為98.3%和98.8%，而裁減后分別為97.7%和97.8%。本文通過采取對特征點進行合理裁減的方法獲得不降低準(zhǔn)確性的前提下效率提高，檢索過程的時間分析如下。

表2描述的時間為算法未經(jīng)裁減處理的情形，由此可以看了出在SIFT算法中，計算穩(wěn)定的特征點所占有的時間比例為5%左右，而大部分時間在計算特征點描述子，并且描述子的復(fù)雜度也直接影響檢索過程的時間。所以如果能在求解局部極值點的過程中保證極值點的分布合理的同時，減少局部極值點數(shù)，必然能為描述子的計算減輕負(fù)擔(dān)，從而提高時間效率。

表1 裁減前后的匹配性能比較Tab.1 Performance comparison before and after the algorithm cutting

表2 算法裁減前的處理時間Tab.2 Processing time before algorithms reduce

表3 裁減后的處理時間Tab.3 Processing time after algorithms reduce

由表2和表3對比可以看出，局部極值點的計算時間有所增加，但是描述子計算時間和特征匹配時間卻得到了大幅降低，這是因為在求解局部極值的過程中通過增加過濾極值點的過程來降低極值點的數(shù)量，這增加了運算負(fù)擔(dān)，但是帶來的好處是顯而易見的，就是總體運算效率得到增強，即是犧牲局部運算效率來提升全局運算效率。參照實驗數(shù)據(jù)可以得出，求局部極值點的時間成本上升幅度小于1%，而描述子計算和匹配計算的效率提高了12倍以上，實驗結(jié)果支持了算法的有效性。

4 結(jié)束語

SIFT在局部特征的描述能力在版權(quán)搜索中非常有效，因為具有版權(quán)的圖像必然是一幅具體的圖像，而不是一類圖像，而SIFT在描述圖像局部特征的能力在此得到充分利用，SIFT對于圖像分類因為“語義鴻溝”具有天然的缺陷，但對于具體圖像的識別具有天然的優(yōu)勢，對圖像的修改必然會保持原有圖像的特征，失去原有圖像的特征則失去圖像修改的意義。本文在對SIFT算法時間開銷分析的基礎(chǔ)上，重點改造耗時最長的描述子生成過程和圖像匹配過程，并取得良好的效果。出于同樣的分析，本文中提出的解決方案可以同樣應(yīng)用在其他分類圖像的搜索場景中。

[1]Datta R，Joshi D，Li J，et al.Image retrieval：ideas，influences and trends of the new age[J].ACM Computing Surveys， 2008，40（2）：5-33.

[2]Jczyk K M，Schmid C.A performance evaluation of local descriptors[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（10）：1615-1630.

[3]Lowe D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60（2）：91-110.

[4]Kekre H B，SarodeT K，Thepade S D.Image retrieval using color-texture features from DCT on VQ codevectors obtained bydekre’sfastcodebook generation [J].ICGST-GVIP Journal，2009，9（5）：1-8.

[5]張恒博.基于內(nèi)容的圖像數(shù)據(jù)庫檢索的技術(shù)研究 [D].大連：大連理工大學(xué)，2008.

[6]梁棟.基于內(nèi)容的圖像檢索中若干關(guān)鍵問題研究 [D].上海：上海交通大學(xué)，2005.