顏雪軍趙春霞 袁 夏

(南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 210094)

1 引言

圖像局部特征描述子是近年來計(jì)算機(jī)視覺領(lǐng)域的研究熱點(diǎn)之一，被廣泛地應(yīng)用于圖像匹配，目標(biāo)跟蹤，圖像檢索等視覺應(yīng)用中[13]-。局部特征描述方法為局部特征點(diǎn)構(gòu)建魯棒的鄰域信息表示，對尺度、旋轉(zhuǎn)、視角等圖像變換，以及噪聲、遮擋等因素具有很強(qiáng)的適應(yīng)性。局部特征描述子研究一個基本問題是：如何在特征點(diǎn)鄰域內(nèi)尋找到相關(guān)信息并對其進(jìn)行有效的編碼[4]，本文將著重探討局部特征描述子的構(gòu)建方法。

目前，研究者已經(jīng)提出多種局部特征描述方法來定量化描述特征區(qū)域的形狀和紋理特性。最為典型的特征描述子是Lowe提出的SIFT特征[1]，其在特征點(diǎn)鄰域內(nèi)構(gòu)建 3維梯度方向直方圖，產(chǎn)生128維描述向量。SIFT描述子對圖像尺度變換與旋轉(zhuǎn)具有不變性，而且對光照變化，噪聲等也有較強(qiáng)的適應(yīng)能力。Mikolajczyk等人[5]在2005年對各種描述子作了全面的分析后發(fā)現(xiàn)，采用梯度信息的SIFT[1]和GLOH明顯優(yōu)于其它描述子。但同時研究者們發(fā)現(xiàn)計(jì)算構(gòu)建梯度信息是特征描述子構(gòu)建中較為耗時的步驟，而利用灰度信息構(gòu)建特征描述子也是一個有效途徑。文獻(xiàn)[6]提出了基于CS-LBP的局部特征區(qū)域描述方法，CS-LBP僅考慮了像素間比較的符號差，因此計(jì)算速度更快。Gupta等人[7]提出一種基于三值編碼CS-LTP的特征描述子。此外，近年來基于灰度強(qiáng)度序列的特征描述子還有LIOP描述子[8]，MRRID描述子[9]等等。雖然這類局部特征描述方法在計(jì)算效率上一般都優(yōu)于 SIFT方法，但特征描述向量維數(shù)也都達(dá)到128維甚至更高。

Calonder等人[10]通過比較像素對強(qiáng)度來構(gòu)建BRIEF(Binary Robust Independent Elementary Features)特征描述子，BRIEF采用位向量的方式編碼，存儲效率明顯提高。但位向量編碼方式導(dǎo)致BRIEF只能用Hamming距離來計(jì)算特征間距離，很難對搜索速度進(jìn)行優(yōu)化。此外，Takacs等人[11]發(fā)現(xiàn)采用BRIEF描述子的ORB[12]在匹配性能明顯弱于 SIFT方法。文獻(xiàn)[4]提出了對比度上下文直方圖(Contrast Context Histogram, CCH)，該描述子在計(jì)算速度以及特征維數(shù)方面都明顯優(yōu)于 SIFT描述子，但在匹配性能上略弱于SIFT。本文針對CCH存在的性能問題，提出一種新的基于對比度的局部特征描述方法，即獨(dú)立元素對比度直方圖(Independent Elementary Contrast Histogram,IECH)描述子。實(shí)驗(yàn)結(jié)果表明，本文方法匹配性能較CCH有明顯的提高，與SIFT性能相當(dāng)。

2 IECH描述子設(shè)計(jì)

本文先介紹與分析CCH描述子[4]和BRIEF描述子[10]的構(gòu)造方法，并在此基礎(chǔ)上，提出本文的獨(dú)立元素對比度直方圖(IECH)描述子的構(gòu)造方法。

2.1 CCH描述子

CCH描述子在極坐標(biāo)下對局部特征的環(huán)形區(qū)域進(jìn)行劃分。圖1所示為文獻(xiàn)[4]中建議的劃分方式，以中心點(diǎn)Pc為中心，在極徑方向?qū)^(qū)域劃分成4個環(huán)形(或圓形)，再在極角方向按照 8個方向進(jìn)行劃分。因此，區(qū)域被劃分成32個互不相交的子區(qū)域。在每個子區(qū)域中統(tǒng)計(jì)2維正負(fù)對比度直方圖：

n為子區(qū)域個數(shù)，最終的向量維數(shù)為2n×，按照文獻(xiàn)[4]中采用的區(qū)域劃分方式，CCH描述子的維數(shù)為64維。為消除線性光照變化的影響，需要?dú)w一化成單位向量。

2.2 BRIEF描述子

BRIEF特征描述子表現(xiàn)為一個特定長度的位向量，考慮鄰域像素塊，則位向量的值可以通過式(3)計(jì)算：

2.3 IECH描述子構(gòu)造方法

本文采用 DoG檢測算法獲得特征點(diǎn)局部特征像素區(qū)域。為使得構(gòu)建的描述子具有旋轉(zhuǎn)不變性，IECH描述子需要將區(qū)域旋轉(zhuǎn)至特征主方向上。采用本文2.1節(jié)CCH所采用的劃分方式(圖1)將像素塊分割成32個子區(qū)域。按照Huang的建議，在采用4個環(huán)形區(qū)域( 3r= )的情況下，像素塊的半徑為，即特征區(qū)域大小為4141×。

在每個子區(qū)域中，統(tǒng)計(jì)IECH直方圖：

圖1 以Pc為中心的64維CCH描述子局部區(qū)域劃分方式

式(5)采用與式(1)相同的統(tǒng)計(jì)方法，但對比度計(jì)算方法不同。在CCH中，計(jì)算的是區(qū)域i內(nèi)所有像素的灰度強(qiáng)度iI與中心像素Pc之間的對比度強(qiáng)度。我們認(rèn)為，CCH的對比度計(jì)算依賴Pc像素的灰度穩(wěn)定性，Pc的細(xì)微變化都會造成最終CCH描述向量的數(shù)值變化。而在圖像變換以及噪聲的影響下，特征檢測算法無法保障Pc的穩(wěn)定性。此外，為了獲取更多的像素塊空間信息，計(jì)算區(qū)域i內(nèi)所有像素與隨機(jī)選擇的像素點(diǎn)集合b的灰度強(qiáng)度Ib之間的對比度強(qiáng)度，并進(jìn)行直方圖統(tǒng)計(jì)。

最后，將直方圖統(tǒng)計(jì)結(jié)果構(gòu)建成如式(6)所示IECH描述向量：

然后將式(6)歸一化成單位向量來消除線性光照變換的影響。

IECH描述子在構(gòu)建過程中引入了BRIEF描述子中相似的像素對選擇方法，但兩者之間存在明顯的差異。按照2.2節(jié)關(guān)于像素點(diǎn)對集合(,)a b的定義，在IECH中，點(diǎn)集a為區(qū)域內(nèi)像素點(diǎn)的遍歷，點(diǎn)集b采用 BRIEF算法采用的隨機(jī)采樣策略在區(qū)域內(nèi)采樣產(chǎn)生。在半徑為20.5的像素區(qū)域內(nèi)，IECH實(shí)際需要的點(diǎn)對數(shù)為。當(dāng)集合b中的元素全部為鄰域中心點(diǎn)Pc時，IECH描述子退化成CCH描述子。

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

為驗(yàn)證本文算法的性能，本節(jié)在 VS2008環(huán)境下實(shí)現(xiàn)對SIFT, SURF, CCH和IECH的對比實(shí)驗(yàn)。實(shí)驗(yàn)采用Mikolajczyk數(shù)據(jù)集[5]和一個小型圖像數(shù)控庫。匹配結(jié)果采用查全率-查錯率(Recall vs.1-Precision, RP)曲線來評價算法性能，特征相似性采用歐式距離來度量，采用最近鄰準(zhǔn)則(Nearest Neighbor)來決定特征之間的匹配結(jié)果。

3.1 IECH中的測試點(diǎn)集的選擇

如第2.3節(jié)所述，在IECH中使用的像素點(diǎn)對集合(,)a b中，點(diǎn)集b通過采樣選取。參考 BRIEF算法，本文采用如下的采樣策略：

此外，在策略(2)中，采用多個σ值來評價其對IECH描述子性能的影響。選取旋轉(zhuǎn)變換和視角變換兩組圖像來做測試，結(jié)果如圖2所示。在采用高斯采樣的方法中， 除時性能略差外，其它基本相當(dāng)。采用均勻分布采樣的IECH在兩組圖像測試中呈現(xiàn)完全不同的結(jié)果，在旋轉(zhuǎn)變換中效果最好，在視角變換中弱于采用高斯采樣的方法。如圖 2(a)在圖像旋轉(zhuǎn)變換中，特征區(qū)域經(jīng)主方向旋轉(zhuǎn)之后幾乎完全相同，點(diǎn)集b對的覆蓋范圍越大，越能提高生成特征的獨(dú)特性。如圖2(b)在視角變換中，特征點(diǎn)鄰域包含的灰度信息并不一致，均勻采樣的IECH雖然具有較好的獨(dú)特性，但會加大一致特征間的距離，增加誤匹配的風(fēng)險。結(jié)合圖2的結(jié)果，在后續(xù)的實(shí)驗(yàn)中，采用策略(2)且取的高斯采樣來產(chǎn)生點(diǎn)集b。

3.2 圖像匹配實(shí)驗(yàn)

Mikolajczyk數(shù)據(jù)集[5]中的測試圖像包含尺度，旋轉(zhuǎn)，視角，模糊，光照和JPEG壓縮共6種圖像變換，能較為全面地評價描述子在各種圖像變換下的性能。對比算法采用標(biāo)準(zhǔn)的 SIFT, SURF[13]和CCH。實(shí)驗(yàn)中，SIFT特征維數(shù)為 128維，SURF,CCH和IECH均為64維。

在尺度和旋轉(zhuǎn)變換中，New Nork圖像只包含純旋轉(zhuǎn)，Bark圖像包含4倍因子左右的尺度變換。如圖3所示，在純旋轉(zhuǎn)的New Nork圖像中，低查錯率的情況下，CCH和SURF方法的響應(yīng)率明顯低于SIFT方法和IECH方法。在尺度變換中，4種方法的性能較為接近。

圖4給出自然場景Trees和人工場景Bikes兩組模糊變換圖像的特征描述方法匹配結(jié)果。如圖 4(a)和圖4(b)所示，CCH方法在兩組測試圖像中均弱于IECH和SIFT方法，而在Trees數(shù)據(jù)集上，SIFT也要明顯好于本文提出的 IECH。模糊變換會將圖像本身的邊緣紋理信息弱化，這種弱化在自然場景中更為明顯，造成像素點(diǎn)區(qū)域的灰度強(qiáng)度在很小的范圍內(nèi)變化。較遠(yuǎn)像素間的對比度值不能較好地表現(xiàn)這種信息，而 SIFT采用的梯度統(tǒng)計(jì)方法考慮的相鄰像素間的灰度值變化。SURF在模糊變換中優(yōu)于CCH描述子，這與SURF采用的Haar小波分量與梯度一樣考慮的是相鄰像素間灰度變換有關(guān)。

在圖5(a)的光照變換和圖5(b)的JPEG壓縮變換實(shí)驗(yàn)中，4種方法都顯示了較好的匹配性能。

在視角變換中，我們測試4種描述子在大約50度視角變換下的結(jié)構(gòu)圖像(Graffies)和紋理圖像(Walls)中的性能。由于在結(jié)構(gòu)圖像中，最近鄰匹配策略產(chǎn)生的RP曲線不存在水平曲線，所以本文在Graffies數(shù)據(jù)集中采用最近鄰-拒絕域的匹配策略，結(jié)果如圖6(a)所示，SIFT和IECH的結(jié)果優(yōu)于CCH和SURF。在圖6(b)的紋理圖像中，IECH比CCH方法的性能有明顯改進(jìn)，但也低于SIFT。SURF描述子在紋理圖像中與本文方法較為接近。正負(fù)對比度在獲取紋理信息方面存在一定的不足，而梯度和Haar小波響應(yīng)能更好地表現(xiàn)紋理信息。

圖2 點(diǎn)集b的選擇對特征描述方法性能的影響

圖3 旋轉(zhuǎn)與尺度變換效果圖

圖4 模糊變換效果圖

圖5光照變換和JPEG壓縮效果圖

圖6視角變換效果圖

總的來說，本文的IECH描述子在多種圖像變換中較 CCH描述子有明顯的提高，尤其克服了CCH描述子在低查錯率下響應(yīng)率低，紋理和模糊圖像性能較差的問題。在與SURF描述子的對比中，IECH描述子的表現(xiàn)優(yōu)于SURF或相當(dāng)?shù)钠ヅ湫阅?。IECH描述子性能跟SIFT方法較為接近，雖然在各種圖像變換中IECH性能都無法優(yōu)于SIFT方法，但考慮到 SIFT的高維特征能保留更多的區(qū)域信息以提高其性能，IECH描述子在采用64維特征時能獲得較好的匹配性能，在存儲受限的應(yīng)用中具有較高的實(shí)用價值。

3.3 圖像檢索實(shí)驗(yàn)

本文在一個小型的圖像檢索數(shù)據(jù)庫[14]中測試SIFT, SURF, CCH以及IECH的檢索性能。該數(shù)據(jù)庫包含10個場景30幅圖像。檢索性能采用統(tǒng)計(jì)得分的方法計(jì)算，依次將每張圖像作為被檢索圖像，其余作為測試圖像。查找與被檢索圖像最相似的兩張圖像，如果檢索到的兩張圖像與被檢索圖像為同一組圖像，則得2分；只有一張圖像與被檢索圖像在同一組則得1分；否則，不得分。描述子的檢索性能可以用其得分除以總分(60)得到。

采用閾值來決定特征之間的匹配，當(dāng)兩個特征之間距離小于閾值的時候，認(rèn)為是一對匹配。閾值匹配有利于提高特征匹配速度，當(dāng)特征距離小于閾值時直接返回其匹配，不需要遍歷該圖像所有的特征。表 1給出了 SIFT, SURF, CCH和本文方法IECH在圖像檢索實(shí)驗(yàn)中的檢索準(zhǔn)確率，本文方法在圖像檢索實(shí)驗(yàn)中可以達(dá)到與 SIFT相同的檢索準(zhǔn)確率，這是因?yàn)镮ECH本身與SIFT性能較為接近。CCH和SURF在圖像變換實(shí)驗(yàn)中明顯弱于SIFT和IECH方法，在圖像檢索中容易引入更多的誤匹配，因此在檢索準(zhǔn)確率上要低于其它兩種方法。

表1 圖像檢索準(zhǔn)確率

3.4 算法運(yùn)行時間測試

對檢索實(shí)驗(yàn)中所有圖像進(jìn)行描述子生成與匹配來估算特征描述方法的計(jì)算效率。將特征生成次數(shù)歸一化到1000次，特征匹配次數(shù)歸一化到1000000次后的各算法運(yùn)行時間如表2所示。IECH和CCH的特征生成速度要明顯快于SIFT和SURF方法，這是由于SIFT包含反切計(jì)算，而IECH和CCH只需進(jìn)行像素間的對比度計(jì)算。SURF描述子生成單位像素兩個方向的Haar響應(yīng)需要14次加減運(yùn)算。IECH和CCH在單位像素上計(jì)算對比度值只需要1次減法運(yùn)算。這也是IECH和CCH生成速度快于SURF的原因。IECH在計(jì)算速度上略慢于CCH(每1000個特征慢15 ms)。CCH與IECH的差別在于計(jì)算對比度的方法不同，時間復(fù)雜度完全相同。這是由于在IECH中，計(jì)算對比度所需的查找表很難整個裝入CPU的Cache中，計(jì)算過程中容易產(chǎn)生Cache命中失敗需要訪問內(nèi)存的問題，因此速度上會慢于CCH描述子，而且單位特征0.015 ms的時間差距在大多數(shù)應(yīng)用中可以忽略。在特征匹配速度的對比中，64維的SURF, CCH和IECH方法在匹配速度上明顯快于128維的SIFT。

表2 特征描述生成與匹配時間

3.5 IECH性能分析

以上實(shí)驗(yàn)表明，IECH相比于CCH具有明顯的性能優(yōu)勢。本文認(rèn)為這是由于CCH的對比度計(jì)算過度依賴Pc像素的灰度值，Pc的細(xì)微變化都會造成CCH描述向量的數(shù)值變化。在IECH中，計(jì)算對比度的像素點(diǎn)由Pc換成一個像素點(diǎn)集合，因此單一像素點(diǎn)的灰度變化對IECH影響相對較小。

本實(shí)驗(yàn)在描述子生成過程中添加噪聲，評估CCH和IECH描述子在不同噪聲水平下的性能。圖7(a)的實(shí)驗(yàn)中，直接對圖像添加高斯白噪聲，噪聲不僅對描述子生成有影響，也會影響特征點(diǎn)的定位精度。圖7(a)給出了IECH(深色虛線)和CCH(淺色實(shí)線)在不同噪聲水平下的匹配性能，相同的噪聲水平采用相同顏色的曲線表示，如圖 7(a)所示在同等噪聲水平下，IECH均優(yōu)于CCH描述子。

為進(jìn)一步驗(yàn)證灰度強(qiáng)度變化對描述子性能的影響，對原始圖像來產(chǎn)生局部特征點(diǎn)，對像素塊添加均勻分布的隨機(jī)噪聲，然后分別產(chǎn)生IECH和CCH描述子，結(jié)果如圖 7(b)所示。結(jié)果表明，IECH的優(yōu)勢更為明顯，在添加了在[8,8]- 范圍內(nèi)隨機(jī)采樣的白噪聲情況下，IECH性能都略優(yōu)于未添加噪聲的CCH。

以上實(shí)驗(yàn)表明，IECH對噪聲以及像素塊灰度變化的影響更為魯棒，而CCH由于對比度計(jì)算依賴中心像素灰度，使得特征點(diǎn)定位誤差和噪聲等因素都容易造成CCH性能的下降。

4 結(jié)束語

圖7 IECH性能分析

本文借鑒 BRIEF描述子中隨機(jī)采用像素對的思想和CCH描述子低維數(shù)，計(jì)算快速的特點(diǎn)，提出了一種魯棒的低維數(shù)局部特征描述方法，即 IECH描述子。實(shí)驗(yàn)結(jié)果表明，IECH采用低維數(shù)(64維)，具有更快的生成速度，且能夠達(dá)到與 SIFT相當(dāng)?shù)钠ヅ湫阅?。與SURF和CCH描述子相比，IECH描述子在各種圖像變換中均表現(xiàn)出優(yōu)于或相當(dāng)?shù)钠ヅ湫阅埽琁ECH描述子在低查錯率下具有更高的響應(yīng)率，并且在噪聲，模糊變換，紋理圖像等圖像變換中的表現(xiàn)更為魯棒。圖像檢索實(shí)驗(yàn)也驗(yàn)證了本文算法的有效性。在未來的工作中，我們將把IECH算法應(yīng)用到移動機(jī)器人平臺上，實(shí)現(xiàn)機(jī)器人的實(shí)時視覺導(dǎo)航和視覺定位與地圖創(chuàng)建(SLAM)等視覺應(yīng)用的特征匹配中。

[1] Lowe D. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004,60(2): 91-110.

[2] Barreto J P andVasconcelos F. sRD-SIFT: keypoint detection and matching in images with radial distortion[J]. IEEE Transactions on Robotics, 2012, 28(3): 752-760.

[3] Tian Qi, Zhang Shi-liang, Zhou Wen-gang, et al.. Building descriptive and discriminative visual codebook for large-scale image applications[J]. Multimedia Tools and Applications,2011, 51(2): 441-477.

[4] Huang C R, Chen C R and Chung P C. Contrast context histogram: an effcient discriminating local descriptor for object recognition and image matching[J]. Pattern Recognition, 2008, 41(10): 3071-3077.

[5] Mikolajczyk K and Schmid C. A performance evaluation of local descriptors[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(10): 1615-1630.

[6] Heikkila M, Pietikainen M, and Schmid C. Description of interest regions with local binary patterns[J]. Pattern Recognition, 2009, 42(3): 425-436.

[7] Gupta R, Patil H, and Mittal A. Robust order-based methods for feature description[C]. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, San Francisco, 2010: 334-341.

[8] Wang Z, Fan B, and Wu F. Local intensity order pattern for feature description[C]. Proceedings of the IEEE International Conference on Computer Vision, Barcelona, 2011: 603-610.

[9] Fan B, Wu F, and Hu Z. Rotationally invariant descriptors using intensity order pooling[J]. IEEE Transactions on Pattern analysis and Machine Intelligence, 2012, 34(10):2031-2045.

[10] Calonder M, Lepetit V, Strecha C, et al.. Brief: binary robust independent elementary features[C]. Proceedings of the European Conference on Computer Vision, Heidelberg, 2010:778-792.

[11] Takacs G, Chandrasekhar V, Tsai S, et al.. Rotation invariant fast features for large-scale recognition[C]. SPIE Optical Engineering Applications. International Society for Optics and Photonics, 2012: 84991D-84991D-10.

[12] Rublee E, Rabaud V, Konolige K, et al.. ORB: an efficient alternative to SIFT or SURF[C]. Proceedings of the IEEE International Conference on Computer Vision, Barcelona,2011: 2564-2571.

[13] Bay H, Tuytelaars T, and Van Gool L. Surf: speeded up robust features[C]. Proceedings of the European Conference on Computer Vision, Heidelberg, 2006: 404-417.

[14] Ke Y and Sukthankar R. Test image dataset. http://www.cs.cmu.edu/~yke/pcasift/, 2004, 4.