局部特征描述子中的數(shù)學(xué)原理

孫卓婷 王福龍

摘 ?要：近十年來，傳統(tǒng)的圖像檢測與匹配算法進(jìn)入瓶頸期，以深度學(xué)習(xí)為首的圖像特征檢測與匹配正展露尖角，將傳統(tǒng)算法和深度學(xué)習(xí)相互融合已是大勢所趨。文章簡要敘述了幾種經(jīng)典檢測算法中特征描述子的生成流程，從數(shù)學(xué)角度嚴(yán)謹(jǐn)?shù)仃U述了局部描述子對圖像存在噪聲、光照和旋轉(zhuǎn)變化等干擾因素具有良好魯棒性的原理，并分析討論了其性能及優(yōu)缺點。

關(guān)鍵詞：局部特征;特征描述子;光照不變性;旋轉(zhuǎn)不變性;PCA

中圖分類號：TP391.4 ? ? ?文獻(xiàn)標(biāo)識碼：A文章編號：2096-4706（2021）14-00103-06

Abstract： In recent ten years， traditional image detection and matching algorithms have entered a bottleneck period. Image feature detection and matching led by deep learning are showing sharp corners. It is a general trend to integrate traditional algorithms and deep learning. This paper briefly describes the generation process of feature descriptors in several classic detection algorithms， rigorously expounds the principle that local descriptors have good robustness to image interference factors such as noise， illumination， and rotation changes from a mathematical point of view， and analyzes and discusses its performance， advantages and disadvantages.

Keywords： local feature; feature descriptor; illumination invariance; rotation invariance; PCA

0 ?引 ?言

近十年來，由于計算機(jī)性能不斷攀升、海量數(shù)據(jù)不斷涌現(xiàn)，以深度學(xué)習(xí)為首的學(xué)習(xí)算法推進(jìn)了圖像配準(zhǔn)算法的革新。新的研究表明：圖像配準(zhǔn)算法正從手工選擇特征向從數(shù)據(jù)中學(xué)習(xí)特征過渡，將學(xué)習(xí)算法和具有實時性和一定數(shù)學(xué)理論支撐的傳統(tǒng)圖像配準(zhǔn)算法融合，有助于該領(lǐng)域的改革和創(chuàng)新。因此用數(shù)學(xué)原理詳細(xì)解釋近些年經(jīng)典特征檢測算法中的特征描述子的各個特性以及優(yōu)缺點，可以為更好地解決復(fù)雜環(huán)境下獲取圖像特征的問題提供堅實的理論基礎(chǔ)。

圖像的局部特征相較于全局特征更能獲取受各種干擾因素影響的真實圖像特征，所以往往使用圖像局部特征進(jìn)行匹配。這個局部特征作為匹配過程的基礎(chǔ)，應(yīng)與其他區(qū)域具有強(qiáng)區(qū)分度。特征點作為圖像穩(wěn)定的稀疏特征，含有該特征點在圖像中的位置、朝向、大小等結(jié)構(gòu)信息，在基于點特征匹配算法中起著不可替代的作用。從特征點周圍取一個圖像塊，將其轉(zhuǎn)換成更小的數(shù)據(jù)集，這個新的數(shù)據(jù)集稱為圖像塊的“局部描述子”，反映著特征點周圍像素的信息，通常用特征向量來表示，用于比對。一個優(yōu)秀的局部描述子還應(yīng)可以魯棒地處理各種圖像變換的情況，因此構(gòu)建局部描述子時，不變性成了其核心問題，在實際匹配中，需要考慮特征描述子的尺度不變性、視角變化不變性、旋轉(zhuǎn)不變性以及光照不變性等。基于梯度直方圖及基于局部二進(jìn)制特征的描述是局部特征描述子主要方法。

1 ?基于梯度直方圖的局部描述子

基于梯度直方圖的局部描述子，顧名思義，是利用梯度幅值對特征點鄰域內(nèi)的梯度方向加權(quán)統(tǒng)計，從而生成梯度方向直方圖來構(gòu)造特征描述子的一種方法。該方法所構(gòu)造的特征將整幅圖像進(jìn)行分塊處理，對圖像局部區(qū)域的位置和空間進(jìn)行量化，使得圖像局部像素點直接的差異信息明確，并且在對直方圖進(jìn)行歸一化后，一定程度上可以消除光照影響，使得圖像數(shù)據(jù)維度降低。但因其核心是獲取梯度，因此計算量大。

1.1 ?SIFT

尺度不變特征變換（Scale-invariant feature transform， SIFT）[1]，是Lowe等在2004年提出的用于圖像處理領(lǐng)域的一種描述子。該算法生成特征描述子流程如下：首先為特征點鄰域像素的梯度幅值和方向確定一個主方向，這是為了讓描述子具有旋轉(zhuǎn)不變性。然后將坐標(biāo)軸旋轉(zhuǎn)到對應(yīng)的主方向，并在主方向上取特征點周圍的22個鄰域，每個鄰域內(nèi)含44個像素，再把360度的幅角范圍進(jìn)行8等分，計算每個鄰域上8個方向的梯度方向直方圖，生成一個分塊區(qū)域，如圖1所示。為了增強(qiáng)描述子的魯棒性，Lowe建議用44共16個分塊區(qū)域，因此每個特征點生成一個128維的SIFT特征，且該特征向量具有尺度和旋轉(zhuǎn)不變性。

最后，為了獲得光照不變性，特征描述子由分量平方之和的平方根歸一化（即L2范數(shù)），其數(shù)學(xué)原理為：

由此可見，對于數(shù)字圖像經(jīng)線性變換前后，其梯度方向不變，對應(yīng)的梯度幅值增大為原來的a倍。而SIFT描述子是由特征點鄰域內(nèi)的像素點的梯度方向和梯度幅值以加權(quán)累加方式組成，即在變換前后的兩個特征向量只差一個常數(shù)倍，即這兩個特征向量共線，用L2范數(shù)歸一化后結(jié)果相同，從而消除了光照對該描述子的影響。

1.2 ?PCA-SIFT

PCA-SIFT[4]，Ke等于2004年提出通過主成分分析（Principal Component Analysis， PCA），將SIFT的128維特征描述向量做去相關(guān)處理，從而達(dá)到降維目的。該算法流程為：首先按特征點主方向，在特征點周圍選取一個41×41矩形鄰域，計算其水平和垂直兩個方向的偏導(dǎo)數(shù)，得到39×39×2=3 042維的向量（最外層像素不計算偏導(dǎo)數(shù)），并對其歸一化處理。此時，所有特征描述子向量構(gòu)成一個k×3 042大小的描述子矩陣（其中k為特征點數(shù)目）。接著，計算該矩陣的協(xié)方差矩陣及矩陣對應(yīng)的特征值和特征向量。在這個步驟里，需要對特征值的大小進(jìn)行降序排列，選取前n個特征值對應(yīng)的特征向量，組成一個n×3 042大小的投影矩陣。最后，對投影矩陣與描述子矩陣作乘法，即可實現(xiàn)降維，且降維后的矩陣大小為k×n。該算法巧妙地將SIFT特征和PCA方法相結(jié)合，不僅彌補(bǔ)了SIFT特征維數(shù)過大的缺陷，還濾除了描述子向量中大量干擾信息。

PCA是通過“去冗余”和“降噪”來達(dá)到降維目的。“去冗余”是指使保留下來的維度中方差盡可能大，“降噪”是指使保留下來的維度間的相關(guān)性盡可能小。協(xié)方差矩陣恰恰是度量維度間關(guān)系的工具，其主對角線上的元素是各個維度的方差，非對角線元素是兩兩維度間的協(xié)方差。換句話說，PCA降維問題可轉(zhuǎn)換為使協(xié)方差矩陣中非對角線元素都基本為零的問題。這就需要找到一個轉(zhuǎn)換矩陣，使得新的協(xié)方差矩陣能夠盡量地對角化。而對于一個n階對稱矩陣，必定存在正交矩陣P，使得：

P-1AP =PTAP =Λ ? ? ? ? ? ? ? ? ? ? ? ? ? ?（7）

其中，Λ是以A的n個特征值為對角元的對角矩陣[5]。P是特征值對應(yīng)的特征向量矩陣并正交化所得。協(xié)方差矩陣A恰恰是一個對稱矩陣，這便是PCA降維過程中，選擇協(xié)方差矩陣的原因。

特征向量矩陣P就是PCA-SIFT中提及的“投影矩陣”，它是正交矩陣，基向量兩兩正交，說明兩個向量相關(guān)性很小，數(shù)據(jù)在這兩個維度上的相關(guān)性很小，這樣的特性也更加印證了投影矩陣選擇的正確性。

對角矩陣Λ對角線上的元素還是各個維度上的新方差，并且有tr（Λ）>tr（A），這是因為通過對角化后，各個維度間的相關(guān)性已經(jīng)減到最弱，噪聲和冗余的數(shù)據(jù)被刪減，每個維度本身擁有的方差自然比之前大。而對角線上較小的新方差則是冗余的維度，這就是PCA-SIFT描述子構(gòu)造投影矩陣時選擇前若干個最大特征值所對應(yīng)的特征向量的原因。新的協(xié)方差矩陣Λ1是以前若干個最大特征值為對角元的對角矩陣。

1.3 ?GLOH

梯度位置方向直方圖（Gradient Location-Orientation Histogram， GLOH）[6]，是K. Mikolajczyk于2005年提出的SIFT描述子的變體，通過圓形劃分取代SIFT的方形并用PCA降維來提高其獨立性和穩(wěn)健性。具體體現(xiàn)在：GLOH計算SIFT描述子中4×4的網(wǎng)格鄰域改成對數(shù)極坐標(biāo)下半徑分別為6、11、15的同心圓。每層同心圓按角度方向分為8等分，共生成17個子塊（第一層沒有按角度劃分），如圖3所示。在每個子塊中計算梯度方向直方圖，梯度方向分為16個區(qū)間，因此生成一個17×16=272維的特征向量。受PCA-SIFT啟發(fā)，通過投影矩陣對每個特征點作PCA降維處理，最終得到一個128維的特征向量。

圖像f（x，y）到g（ρ，θ）的對數(shù)極坐標(biāo)變換定義[7]為：

其中，ρ表示對數(shù)極坐標(biāo)的極徑，θ表示角度，（xc，yc）是笛卡爾坐標(biāo)系的變換中心，在SIFT特征中該變換中心相當(dāng)于特征點，（x，y）表示笛卡爾坐標(biāo)系的像素點，在SIFT特征中指特征點鄰域內(nèi)的像素點。

對數(shù)極坐標(biāo)是對人眼的仿生模擬。人眼的中心凸起有聚焦的作用，即視焦點區(qū)域清晰，外圍逐漸模糊。對數(shù)極坐標(biāo)下的像素都分布在原點（在GLOH特征中指特征點）附近，隨著極徑的增大，越遠(yuǎn)離中心點的區(qū)域分辨率越低，從而簡化了圖像?？梢詫⒃撟儞Q看作對圖像作了如圖4的濾波，也就是說，GLOH相當(dāng)于通過對數(shù)極坐標(biāo)變換對離特征點較近的像素點做了一次加權(quán)處理，因此其計算復(fù)雜度會增大。

由式（9）可見，圖像在笛卡爾坐標(biāo)系下的旋轉(zhuǎn)和尺度變換，在對數(shù)極坐標(biāo)下，相應(yīng)的轉(zhuǎn)化為沿θ軸和ρ軸上的位移。即對數(shù)極坐標(biāo)具有旋轉(zhuǎn)不變性和尺度不變性。由此可見，在對數(shù)極坐標(biāo)系下的人眼仿生模擬特性以及旋轉(zhuǎn)不變性使得GLOH特征描述子在生成過程中，計算復(fù)雜度增加，但可以不需要特征點的主方向。

1.4 ?SURF

加速穩(wěn)健特征（Speeded Up Robust Features， SURF）[8]，是Herbert Bay于2006年提出的SIFT算法加速版。具體體現(xiàn)在：在特征點檢測上，采用了積分圖像和快速hessian矩陣檢測技術(shù)提高計算速度。在生成特征描述子過程中，surf特征仿照SIFT特征的思想，通過對每個特征點建立一個主方向以保證其選擇不變性，只是選取主方向的方式不同：surf特征首先利用積分圖像加權(quán)計算特征點周圍半徑為6σ（σ為尺度）的圓域內(nèi)像素的水平和垂直方向的Haar小波響應(yīng)（邊長為4σ）。再以特征點為中心，將張角為60°的扇形區(qū)域內(nèi)的響應(yīng)累加得到一個矢量，按此過程遍歷整個圓，如圖5（a）所示，取最長矢量為主方向。然后，將坐標(biāo)軸旋轉(zhuǎn)到主方向，在特征點附近取一定大小的矩形區(qū)域，分成4×4個分塊區(qū)域，每個分塊區(qū)域以σ為步長取5×5個采樣點，根據(jù)距離中心點的遠(yuǎn)近加權(quán)計算兩個方向的haar小波響應(yīng)，如圖5（b）所示。最后統(tǒng)計響應(yīng)值∑dx，∑dy，∑|dx|，∑|dy|形成特征向量，得到4×4×4=64維的SURF特征描述子。SURF特征具有和SIFT特征相近的性能，如尺度、旋轉(zhuǎn)和光照不變性，但維數(shù)卻大大減少，在對匹配精度要求不是非常高的實際應(yīng)用中，SURF更能做到實時性。

1.5 ?DAISY描述子

DAISY特征描述子是由Tola[9]等人于2008年提出的面向稠密特征提取的可快速計算的特征描述子。不同于SIFT和GLOH特征分塊統(tǒng)計梯度方向直方圖，DAISY特征采用高斯卷積進(jìn)行梯度方向直方圖加權(quán)，即在特定方向上與多個高斯濾波器進(jìn)行卷積，利用高斯濾波函數(shù)性質(zhì)中的可分離性，可以大大提高計算效率。DAISY描述子用類似“雛菊”的結(jié)構(gòu)來替換SIFT描述子中的矩形鄰域，如圖6所示，圍繞著特征點，每8個藍(lán)色采樣點以45°為間隔建立一層同心圓，各個采樣點分布在同心圓環(huán)上，不同高斯尺度建立不同大小的同心圓環(huán)，越外層，高斯尺度值越大。每個圓圈代表一個直方圖區(qū)域，各向同性的高斯核和圓形網(wǎng)格相結(jié)合，使得圖像發(fā)生旋轉(zhuǎn)時，特征點附近的像素不會變化，在直方圖上表現(xiàn)為直方圖柱子順序的改變，因此不需要像SIFT特征一樣計算特征點的主方向來保持描述子的旋轉(zhuǎn)不變性，可以直接用其結(jié)構(gòu)中第二層梯度直方圖來判斷方向[10]。

根據(jù)這個表達(dá)式可知，圖像與高斯核做卷積運算時，可以先和水平方向上的一維高斯核計算，再和垂直方向上一維高斯核進(jìn)行計算，最終輸出圖像。

由此可見，DAISY特征通過改進(jìn)SIFT的分塊策略，利用高斯卷積的可分離性進(jìn)行梯度方向直方圖的分塊匯聚，對每個特征點的計算量由平方階降為線性階，大大提高了計算效率，從而快速稠密地提取特征描述子。

2 ?基于局部二進(jìn)制的描述子

基于梯度直方圖的局部描述子對圖像各種變換（旋轉(zhuǎn)、縮放、遮擋）具有完全或部分的魯棒性，但為獲取梯度而進(jìn)行的大量計算以及其豐富的浮點型描述子信息所需的大量存儲空間，使得它不能在實時應(yīng)用場景中使用。隨著移動設(shè)備運行需要的不斷增長，二進(jìn)制局部描述子應(yīng)運而生，該描述子生成簡單，所需存儲空間小，在進(jìn)行特征匹配時，匹配速度遠(yuǎn)超浮點型描述符。

2.1 ?BRIEF

BRIEF（BinaryRobust Independent Elementary Features）[12]描述子由Michael Calonder等人于2010年提出，該算法是使用二進(jìn)制針對已經(jīng)檢測到的特征點進(jìn)行編碼的描述子，擯棄了傳統(tǒng)的梯度直方圖描述特征點方法，把局部描述子的簡化做到了極致。它以特征點為中心選取一塊方形區(qū)域，先對該區(qū)域做平滑處理，過濾掉冗余信息，再在該區(qū)域內(nèi)以某種特定的方式選擇若干個像素點對（點對兩個像素間的順序以及點對順序不再更改），然后比較像素點對的灰度值，最后將所有點對的比較結(jié)果按特定的順序排列，形成一串二值編碼，該編碼即該特征描述子唯一匹配碼。但由于僅采用單像素點的灰度值進(jìn)行判斷，因此不具備旋轉(zhuǎn)不變性和尺度不變性。

2.2 ?ORB

ORB（Oriented FAST and Rotated BRIEF）[13]是由Ethan Rublee等人于2011年中提出的將FAST特征檢測與BRIEF特征描述相結(jié)合的一種新的特征提取和描述的算法。主要針對BRIEF不具備旋轉(zhuǎn)不變性進(jìn)行改進(jìn)，即計算特征點以一定半徑范圍內(nèi)的質(zhì)心，特征點坐標(biāo)到質(zhì)心形成一個向量作為該特征點的方向，從而解決旋轉(zhuǎn)不變性的問題。除此之外，它還使用數(shù)據(jù)學(xué)習(xí)的方法來替代手工選擇像素點對。而事實上，傳統(tǒng)特征算法自2010年后與學(xué)習(xí)算法之間的界限變得模糊，而學(xué)習(xí)算法依賴數(shù)據(jù)的特性，使得混合使用手工標(biāo)注的描述子和學(xué)習(xí)算法成為趨勢。

2.3 ?BRISK

BRISK（Binary Robust in Variant Scalable Keypoints）[14]是2011年由Leutenegger等人提出的根據(jù)像素值間的比較結(jié)果生成的二進(jìn)制字符串，其采樣模板受DAISY特征啟發(fā)，采用與不同于DAISY特征的采用方式，即以特征點為中心，對特征點周圍若干個點進(jìn)行均勻采樣形成同心圓環(huán)，再分別進(jìn)行不同的高斯平滑，以取代DAIYSY特征的8點采樣，如圖7所示，藍(lán)點為采樣位置，紅圈大小反映高斯平滑程度。

這些二進(jìn)制描述子中每對像素點進(jìn)行灰度比較后僅生成一個二進(jìn)制位，可以表示每對像素點的差異，但差異指向并不明確，因為灰度值相差較高和較低的兩對像素點的比較結(jié)果是相同的，從而可能導(dǎo)致丟失感興趣區(qū)域中的紋理信息。因此二進(jìn)制描述子對噪聲十分敏感。

3 ?結(jié) ?論

圖像獲取技術(shù)的迅猛發(fā)展使得采集的圖像信息越來越復(fù)雜豐富，傳統(tǒng)手工選擇的特征檢測與匹配算法總是基于各種前提假設(shè)對龐大的數(shù)字圖像信息進(jìn)行簡化，因此不具備很好的泛化能力。近十年來，傳統(tǒng)的圖像檢測與匹配算法進(jìn)入瓶頸期。以深度學(xué)習(xí)為首的圖像特征檢測與匹配正展露尖角。但因為深度學(xué)習(xí)所需的普適性的數(shù)據(jù)集難以獲取，且其計算量十分龐大。因此將傳統(tǒng)算法和深度學(xué)習(xí)相互融合成為趨勢，使得該技術(shù)同時具有實時、泛化能力。而這一切的前提需要完備的數(shù)學(xué)理論做支撐，因此，本文選取了具有代表性幾種特征描述子，簡要敘述了其生成流程，并對里面提及的性能進(jìn)行詳細(xì)數(shù)學(xué)原理的分析，意在期望更多研究者透徹了解傳統(tǒng)特征描述子，以此推動這一課題的發(fā)展。

參考文獻(xiàn)：

[1] LOWE D G. Distinctive Image Features from Scale-Invariant Keypoints [J].International Journal of Computer Vision，2004，60（2）：91-110.

[2] LAX P D.泛函分析 [M].侯成軍，王利廣，譯.北京：人民郵電出版社，2010.

[3] MAITRE H，等著.數(shù)字圖像處理 [M].孫洪，譯.北京：電子工業(yè)出版社，2009.

[4] KE Y，SUKTHANKAR R. PCA-SIFT：a more distinctive representation for local image descriptors [C]//Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington：IEEE，2014：506-513.

[5] 劉仲奎，楊永保，程輝，等.高等代數(shù) [M].北京：高等教育出版社，2003.

[6] MIKOLAJCZYK K，SCHMID C. A performance evaluation of local descriptors [C]//2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition，2003.Proceedings.Madison：IEEE，2005：1615-1630.

[7] 冉洪成.基于對數(shù)極坐標(biāo)的圖像匹配綜述 [J].現(xiàn)代計算機(jī)，2020，4（4）：65-69.

[8] BAY H，ESS A，TUYTELAARS T，et al. SURF：Speeded up robust features [J].Computer Vision and Image Understanding，2008，110（3）：346-359.

[9] TOLA E，LEPETIT V，F(xiàn)UA P. DAISY：An Efficient Dense Descriptor Applied to Wide-Baseline Stereo [J].IEEE Trans on Pattern Analysis and Machine Intelligence，2010，32（5）：815-830.

[10] FISCHER J，RUPPEL A，WEISSHARDT F，et al. A rotation invariant feature descriptor O-DAISY and its FPGA implementation [C]//https：//ieeexplore.ieee.org/xpl/conhome/6034548/proceeding.San Francisco：IEEE，2011：2365-2370.

[11] LINDEBERG T. Scale-space theory： a basic tool for analyzing structures at different scales [J].Journal of Applied Statistics，1994，21（1-2）：225-270.

[12] CALONDER M，LEPETIT V，STRECHA C，et al. BRIEF：Binary Robust Independent Elementary Features [C]//Computer Vision–ECCV.Springer-Verlag，2010：778-792.

[13] RUBLEE E，RABAUD V，KONOLIGE K，et al. ORB：An efficient alternative to SIFT or SURF [C]//2011 International Conference on Computer Vision. Barcelona：IEEE，2011，58（11）：2564-2571.

[14] LEUTENEGGER S，CHLI M，SIEGWART R Y. BRISK：binary robust in variant scalable keypoints [C]//2011 International Conference on Computer Vision.Barcelona：IEEE，2011：2548-2555.

作者簡介：孫卓婷（1996—），女，漢族，廣東惠州人，碩士在讀，研究方向：圖像處理、模式識別;王福龍（1968—），男，漢族，廣東廣州人，教授，博士，研究方向：圖像處理、模式識別和智能控制及應(yīng)用。