SIFT局部特征描述算法在圖像版權(quán)搜索中的應(yīng)用

伯將軍，郭書軍，伍淳華

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

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

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

1 SIFT特征提取算法

1.1 特征提取

1.1.1 尺度檢測(cè)及計(jì)算空間極值點(diǎn)

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

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

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

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

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

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

則邊緣檢測(cè)過程如下：

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

1.1.2 為特征點(diǎn)分配方向

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

其中，m為特征點(diǎn)的梯度的模，θ為特征點(diǎn)的方向。

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

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

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

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

1.2 特征匹配

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

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

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

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

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

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

2.1 利用K-Means算法對(duì)特征點(diǎn)過濾

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

1）從極值點(diǎn)集合M中任意選擇k個(gè)點(diǎn)作為初始聚類中心；

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

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

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

在上述過程中，有兩個(gè)決定聚類效果的因素，初始聚類點(diǎn)的個(gè)數(shù)k和步驟4）中迭代次數(shù)。首先，初始聚類點(diǎn)數(shù)的選擇由圖像的分辨率決定，因?yàn)榉直媛矢叩膱D像帶有的信息更多，所以初始聚類點(diǎn)數(shù)k滿足式（15）。

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

2.2 特征點(diǎn)梯度值過濾

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

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

2.3 圖像描述子生成

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

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

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

3 仿真實(shí)驗(yàn)及分析

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

SIFT在局部特征的描述能力在版權(quán)搜索中非常有效，因?yàn)榫哂邪鏅?quán)的圖像必然是一幅具體的圖像，而不是一類圖像，而SIFT在描述圖像局部特征的能力在此得到充分利用，SIFT對(duì)于圖像分類因?yàn)椤罢Z(yǔ)義鴻溝”具有天然的缺陷，但對(duì)于具體圖像的識(shí)別具有天然的優(yōu)勢(shì)，對(duì)圖像的修改必然會(huì)保持原有圖像的特征，失去原有圖像的特征則失去圖像修改的意義。本文在對(duì)SIFT算法時(shí)間開銷分析的基礎(chǔ)上，重點(diǎn)改造耗時(shí)最長(zhǎng)的描述子生成過程和圖像匹配過程，并取得良好的效果。出于同樣的分析，本文中提出的解決方案可以同樣應(yīng)用在其他分類圖像的搜索場(chǎ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ù)庫(kù)檢索的技術(shù)研究 [D].大連：大連理工大學(xué)，2008.

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