高斯形狀上下文描述子

馮祥衛,馮大政,侯瑞利

(西安電子科技大學雷達信號處理國家重點實驗室,陜西西安 710071)

高斯形狀上下文描述子

馮祥衛,馮大政,侯瑞利

(西安電子科技大學雷達信號處理國家重點實驗室,陜西西安 710071)

利用高斯窗函數,構建了一種新的形狀上下文描述子,并將該描述子應用到形狀配準當中.高斯形狀上下文以參考點為中心建立一組高斯窗函數,根據中心點與其他采樣點之間的歐氏距離,利用盡量多的采樣點計算各個窗函數的值并組成形狀描述子,描述點與點之間的位置關系.通過比較形狀描述子之間的相似性,能夠較為準確地找到兩個形狀間點與點的對應關系.實驗表明,使用高斯形狀上下文作為形狀描述子,比傳統的形狀上下文能夠更加準確地找到點與點的對應關系,使配準算法快速收斂,具有良好的抗噪性和魯棒性.

形狀上下文;高斯窗;形狀描述子;形狀配準;魯棒性

形狀是圖像的重要特征.形狀配準,特別是點配準在圖像處理和模式識別領域得到了廣泛的重視和發展.形狀點配準主要通過迭代算法完成,分為兩個步驟:①尋找兩幅形狀之間的點與點的對應關系;②根據對應關系計算變換.形狀配準問題是一個非常復雜的非凸優化問題,存在多個局部極小點,因此,尋找一個好的初值,即找到準確的點與點的對應關系顯得特別重要.為了解決這個問題,多種形狀描述子被提出和深入研究[1].文獻[2]提出了形狀上下文(Shape Context,SC),并定義了形狀上下文距離.形狀上下文是一種基于輪廓的形狀描述子,細致地描述了邊緣點在形狀中與其他的邊緣點的空間位置關系.兩個點之間的相似程度可以通過比較形狀上下文距離來衡量.形狀間的點與點匹配可以通過最小化形狀上下文距離之和來實現.針對形狀上下文的改進和應用成為了一個研究熱點[3-5].但是,形狀上下文采用的是硬分配的思想,圖像中的每個點僅僅被分配到一個柵格中.在噪聲、形變以及旋轉的影響下,這種決策方式存在一定的缺陷.針對以上問題,筆者提出了高斯形狀上下文(Gaussian Shape Context,GSC)描述子.高斯形狀上下文首先以參考點為圓心按照一定分布規律建立一組高斯窗函數,根據高斯窗函數的中心點與其他采樣點之間的歐氏距離,計算每個窗函數的值,再利用全部高斯窗函數的值組成該點的形狀上下文描述子.高斯形狀上下文描述子充分考慮到了形狀作為整體的存在,利用全部采樣點計算特征表示單元,融合了形狀的局部細節信息和整體信息.與傳統的形狀上下文相比,這種算法不僅能夠找到更為準確的點與點的對應關系,與配準算法較好地結合起來,而且在形變和噪聲影響下有更好的魯棒性.

1　形狀上下文

形狀上下文是一種基于輪廓的形狀描述子[2],如圖1所示.形狀上下文首先對目標輪廓進行均勻采樣,依次選取每個采樣點作為參考點,以該參考點為中心建立極坐標系,并按照角度和距離劃分柵格,統計落入每個柵格內的點數,構成該點的形狀上下文描述子.令P和D分別代表原始形狀和待配準形狀的采樣點集,選取di作為參考點,di∈D,利用該點與余下的Nd-1個采樣點的相對位置關系構建特征向量.以點di為原心建立對數極坐標空間,將對數極坐標空間按照距離和角度劃分為M×N個柵格.統計落入每個柵格內的點數,可以獲得關于點di的特征直方圖:

圖1　形狀上下文

其中,B表示柵格.直方圖hi定義了點di處的形狀上下文.任意選取目標形狀上的某一點pj,pj∈P,令Cij=C(di,pj),表示點di和點pj的匹配距離,根據χ2檢驗統計,可得

其中,Cij表示兩個點之間的“相似度”,即形狀上下文距離.通過比較形狀上下文距離,可以確定形狀間的點與點的對應關系.

2　基于高斯窗函數的形狀上下文

2.1高斯形狀上下文構建原理

形狀特征描述子的構建需要盡量滿足兩個要求:一是盡可能多地保留有用信息,二是需要具備良好的抗噪性和魯棒性.

(1)形狀作為一個具有緊密的內在聯系的整體,每個采樣點之間都存在空間上和結構上的相互關系.因此,特征描述子的每個表示單元應當使用盡量多的采樣點描述點與點之間的位置關系.形狀上下文表示單元都為柵格,柵格僅僅描述了參考點與柵格所在區域的圖像點的關聯,而柵格內與柵格外的采樣點之間的信息被忽略掉.文獻[3]中提出的軟形狀上下文通過對柵格內的點進行離散權值加權并分配到周圍的柵格中,雖然在一定程度上保留了這部分信息,但是軟形狀上下文構造過于簡單,特別是在距離上只有一層,不能較為準確和全面地表示出這種相對關系.高斯形狀上下文構建形狀表示單元時,不再簡單地將整體作為各個表示單元的疊加,而是全面地考慮各個單元之間的相對關系.

(2)形狀上下文通過統計柵格內的點數來構建表示單元.根據式(1),形狀上下文采用的硬分配的方式分配采樣點,每個采樣點僅僅只能被一個柵格統計,表示數值只能是整數,是一種離散的表示方式,而離散表示必然存在著階躍變化.因此,當形狀產生輕微的旋轉或者形變的時候,形狀上下文描述子可能會產生較為劇烈的變化,影響形狀描述子的穩健性.這樣的分配方式對于采樣點在柵格的交界處分布較多的情況,目標產生微小形變,得到的形狀上下文描述子卻有很大的不同.如圖1中所示,形狀發生微小形變,位置由A點移動到B點,但是采樣點分布的微小變化卻引起形狀上下文產生明顯的變化.為解決這個問題,高斯形狀上下文使用連續函數代替階躍函數,用連續的或者近似連續的數值變化表示形狀產生的變化,避免形狀描述子出現劇烈變化,從而提升形狀描述子的魯棒性.

2.2構建高斯形狀上下文表示單元

為了構建包含信息更為豐富、魯棒性更強的形狀表示單元,可以使用高斯窗函數作為特征表示單元對采樣點的空間相對分布進行描述.傳統的形狀上下文采用的統計標準是二值化的、硬分配的,不具備各向同性;而高斯窗函數是連續的、平滑的、軟決策的,且具備各向同性,從而對微小的形變具有較好的不變性.如圖2所示,對杯子的邊緣點進行采樣得到的點為采樣點,定義當前需要描述的采樣點di為參考點.在二維圖像中按照一定的分布規律選取坐標為(x,y)的點作為高斯窗函數的中心,定義該點為形狀表示單元的中心點.該點相對于參考點di在某一坐標系下的距離為l,角度為θ,高斯窗函數的均值為零,標準差為σ,則高斯窗函數為

圖2　高斯形狀上下文

其中,Δx、Δy分別表示點到x、y的距離.形狀上的某一采樣點(i,i)對于該高斯窗函數的加權值為

進一步,通過所有采樣點可以得到以點(x,y)為中心的高斯窗函數的值為

從式(3)～(5)可以得出,使用高斯窗函數作為表示單元保留了距離和角度信息,即l和θ.新的表示單元根據采樣點與中心點的歐氏距離,對全部的采樣點加權計算得出窗函數值,并且距離中心點越近,對形狀表示單元的影響就越大,這與實際情況相符合.由于高斯窗函數的各向同性,使用高斯窗函數作為形狀表示單元在一定程度上也模糊了距離、角度變化以及非剛性形變.同時,針對傳統形狀上下文所采用的“柵格”會出現劇變的情況,高斯窗函數將形狀的變化采取近似連續化數值表示,避免邊緣點的微小挪動導致形狀表示單元出現大的變化,提升了形狀表示單元的魯棒性.高斯窗的大小可以控制形狀表示單元的模糊程度,選擇大的高斯窗重點體現中心點在形狀中的粗略位置信息,選擇小的高斯窗則重點體現中心點附近的細節信息.

2.3構建高斯形狀上下文描述子

單個的高斯窗函數形狀表示單元可以描述所有采樣點相對于中心點(x,y)的分布情況,多個有規律分布的高斯窗函數組成的形狀上下文描述子就能比較全面和精確地描述參考點di在整個形狀中的空間信息.如圖2所示,高斯形狀上下文以參考點di為原點建立極坐標系,并按照角度和距離劃分平面空間,得到的交叉點作為高斯窗函數的中心點.在距離劃分上,可以選擇相同的半徑,即R1=R2=R3,也可以選擇依次增加的半徑,即R1＜R2＜R3.在高斯窗函數的選擇上,高斯窗的大小隨著中心點與參考點的距離的增加而增加,從而使描述子對參考點附近的采樣點分布變化更加敏感.在距離參考點較近的位置細致地刻畫采樣點的分布情況,注重體現結構上的細節變化;距離較遠的采樣點則用來粗略地描述參考點在形狀中的空間位置,讓更多的點產生更大的影響參與表示單元的構建,模糊容易受噪聲影響的細微差別.同時,還可以根據迭代配準算法的配準情況調整高斯窗函數的大小.綜上所述,并根據式(5)計算得到參考點di的M×N+1個高斯窗函數值組成特征描述子:

根據式(2)計算出形狀之間點與點的形狀上下文距離.

高斯形狀上下文描述子是以參考點為中心,利用點與點之間的相對位置關系構建描述子,因此具備平移不變性.利用中心點與采樣點之間歐氏距離矩陣的平均值,對坐標進行歸一化以達到一定的尺度不變性.同時,由于高斯形狀上下文表示單元可以模糊角度和距離差別,因此對輕微的旋轉和不規則形變也具備一定的不變性.對于出現較大旋轉的情況,可以將點的切線方向定義為零度角坐標軸.因此,高斯形狀上下文描述子對參考點形成了由近及遠,由細致到粗略,由點到局部到部分整體的描述,既提升了形狀描述子的穩健性,又保證了精確性.值得注意的是,如果取足夠多的高斯窗,本質上就對形狀做了高斯平滑,濾除了形狀中高頻成分,而噪聲往往存在于高頻成分當中,因此,基于高斯窗函數的形狀上下文描述子具有天然的魯棒性.

3　配準算法

形狀描述子構建完成以后,就需要通過按照一定的標準,比較點與點之間的“相似性”來找到最佳點與點的配準關系,然后根據得到的點與點對應關系計算配準變換.尋找準確的點與點對應關系和配準變換相互依賴,互為前提.找到準確的點與點的對應關系,對算法性能具有重要影響.尋找點與點的對應關系可以通過最小化代價函數實現[6],代價函數的統一形式為

其中,λ為正則化參數.兩個步驟相互迭代,互為前提,直到滿足停止條件為止.薄板樣條函數算法是一種非剛性變換,存在非線性計算,利用的信息比剛性變換要多,因此性能有一定的提升,但是計算較為復雜,計算復雜度為O(N3)[8].

4　仿真實驗

為了驗證筆者提出算法的有效性,進行了以下仿真實驗.實驗中所采用的計算機處理器為Intel i5-3570,主頻為3.4 GHz,內存為4 GB,軟件平臺為MATLAB,版本為R2011b.實驗中利用高斯形狀上下文(GSC)和形狀上下文(SC)方法構建形狀描述子,使用匈牙利算法尋找點與點之間一對一的對應關系,利用薄板樣條函數算法計算配準變換,分別記為GSC+TPS方法和SC+TPS方法.在實驗中首先對配準形狀和待配準形狀進行編碼,其中,對應點標記為相同的編號.進一步,定義配準率r為

其中,N表示采樣點數;i表示原始形狀和待配準形狀對應點的編碼之差,該差不大于m則認為正確配準;ni表示配準圖像和待配準圖像的對應點的編碼之差為i的數目;λi表示配準置信度,λi值越高,表示該點被正確配準的概率越高.在實驗中,取m=2,λ0=1,λ1=0.8,λ2=0.6.配準算法采用薄板樣條函數算法,因此,進一步定義目標形狀和配準形狀對應點之間的距離的平均誤差為

其中,E表示形狀之間配準結果準確度.同時,根據式(8)計算變換所需要的彎曲能量IT.IT越大,表示配準形狀需要做更為劇烈的形變才能完成配準要求.r、E和IT這3個量的大小和收斂速度共同實現對圖像配準算法質量的考查.文中的實驗采用文獻[6]中所用的數據.為保證實驗的公平性,兩種方法的正則化參數λ的取值規則都是相同的,都以水平方向作為零度角.形狀上下文角度方向等分為12組,距離方向分為5組,最終每個點的描述子為60維向量.高斯形狀上下文在角度方向和距離方向,加上參考點的高斯窗,建立12× 5+1=61個高斯窗函數.高斯窗函數的標準差一般在0.25～0.35之間取值,如果形狀較為緊湊,即點與點之間的平均距離小,則可以取相對較小的高斯窗;反之,則取相對較大的高斯窗.

實驗1 采用的形狀如圖3(a)所示,待配準形狀與原始形狀之間存在明顯的平移和非線性形變,沒有添加噪聲.每組實驗迭代配準次數為8次.圖3(b)與3(c)表示兩種方法的最終配準結果,從圖中可以看出, GSC+TPS方法的配準效果要優于SC+TPS方法.圖4給出了兩種方法的性能對比.從性能對比圖4(a)可以發現,GSC+TPS方法較SC+TPS方法的首次配準率要高,GSC+TPS在首次配準時達到了74.40%,第2次配準中達到了88.00%,而SC+TPS首次配準的準確率為69.60%,收斂后配準率為78.80%,顯示出GSC算法在構建形狀描述子時具有良好的區分性.從圖4(b)和4(c)中可以發現,GSC+TPS方法在平均誤差和彎曲能量方面都要明顯小于SC+TPS方法.在收斂速度上,GSC+TPS方法在第2次就達到收斂,而SC+TPS方法在第7次才收斂,GSC+TPS方法的收斂速度要明顯快于SC+TPS方法.在使用匈牙利算法和薄板樣條函數算法中,都存在計算復雜度為O(N3)的操作,因此,GSC+TPS方法能夠快速收斂的性質大大加快了形狀的配準速度,在處理大規模問題,例如識別問題中,具有較大的優勢.該實驗證明了GSC+ TPS方法在形狀產生非線性形變下的有效性.

圖3　SC+TPS與GSC+TPS方法配準圖

圖4　性能對比圖

圖5　配準形狀

實驗2 考查形狀邊緣受到高斯噪聲污染的情況下兩種方法的性能.實驗中高斯噪聲的均值為零,標準差從0.005到0.050,共10組,每組標準差增加0.005,最大迭代次數為100,每組做300次重復試驗.實驗中所采取的原始形狀和部分添加噪聲的形狀如圖5所示.隨著噪聲的增加,待配準圖像產生的變化越來越劇烈,因此尋找對應點,實現配準難度也越來越高.以標準差σ=0.015為例,GSC+TPS方法在配準率、彎曲能量、平均誤差方面均要優于SC+TPS方法.同時,GSC+TPS方法平均只需要3次左右的迭代就達到了收斂,而SC+TPS甚至在除去不收斂的情況下,平均需要8次左右的迭代才能收斂.GSC+TPS方法在噪聲下仍可以快速收斂的性質對于處理容易受噪聲污染的自然圖像時,可以較大地節約計算量.表1給出了GSC+TPS方法和SC+TPS方法的配準率、彎曲能量和平均誤差.從表中可以看出,特別是在噪聲標準差為0.005～0.030時,GSC+TPS方法在各項中性能標準中不僅明顯高于SC+TPS方法,而且各項參數的波動幅度也較小,說明GSC+TPS方法具有較好的抗噪性和魯棒性.隨著噪聲標準差增加到0.045,GSC+ TPS方法的性能只是略優于SC+TPS方法,這是因為過大的噪聲有可能破壞形狀的結構信息,此時進行配準的意義已經不大.該實驗證明了GSC+TPS方法在噪聲情況下的有效性.

表1　SC+TPS與GSC+TPS在高斯噪聲情況下的配準性能

5　結束語

筆者提出了一種基于高斯窗函數的形狀上下文描述子,高斯形狀上下文利用一組高斯窗函數建立柵格,構建性能穩健的形狀描述子,在形變和噪聲情況下能夠尋找到更為準確的點對點對應關系,并且能夠與迭代最近點(Iterative Closest Point,ICP)、薄板樣條函數等計算變換方法結合起來實現圖像的配準任務,具有更高的配準準確率和更快的收斂速度,性能也更為穩健.

[1]ZHANG D,LU G.Review of Shape Representation and Description Techniques[J].Pattern Recognition,2004,37(1): 1-19.

[2]BELONGIE S,MALIK J,PUZICHA J.Shape Matching and Object Recognition Using Shape Contexts[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(4):509-522.

[3]LIU D,CHEN T.Soft Shape Context for Iterative Closest Point Registration[C]//Proceedings of the IEEE International Conference on Image Proceedings:2.Piscataway:IEEE,2004:1081-1084.

[4]SU Y.Spectra of Shape Contexts:an Application to Symbol Recognition[J].Pattern Recognition,2014,47(5): 1891-1903.

[5]PREMACHANDRAN V,KAKARALA R.Perceptually Motivated Shape Context Which Uses Shape Interiors[J]. Pattern Recognition,2013,46(8):2092-2102.

[6]CHUI H,RANGARAJAN A.A New Point Matching Algorithm for Non-rigid Registration[J].Computer Vision and Image Understanding,2003,89(2):114-141.

[7]KUHN H W.The Hungarian Method for the Assignment Problem[J].Naval Research Logistics Quarterly,1955,2(1/ 2):83-97.

[8]BOOKSTEIN F L.Principal Warps:Thin-plate Splines and the Decomposition of Deformations[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1989,11(6):567-585.

(編輯:郭 華)

Gaussian shape context descriptors

FENG Xiangwei,FENG Dazheng,HOU Ruili
(National Key Lab.of Radar Signal Processing,Xidian Univ.,Xi’an 710071,China)

The shape context(SC)descriptors based on the Gaussian window(GSC)are proposed.The GSC descriptors can be used to match shapes.Encircling the reference point,the GSC sets up a group of Gaussian window functions.According to the Euclidean distance between the center points and the sampling points,the GSC describes the spatial relations between sampling points based on the shape descriptors calculated by Gaussian window functions by the use of as many sampling points as possible.More accurate correspondences between two shapes are determined by comparing the similarities of the shape descriptors. Experimental results show that the GSC can find more accurate correspondence relations and provide a good initial value.The proposed descriptors can also make the matching algorithm converge fast,while keeping a good anti-noise and robust performance compared with SC.

shape context;Gaussian window;shape descriptors;shape matching;robust

TP391

A

1001-2400(2016)04-0045-06

10.3969/j.issn.1001-2400.2016.04.009

2015-05-14 網絡出版時間：2015-10-21

國家自然科學基金資助項目(61271293)

馮祥衛(1990-),男,西安電子科技大學博士研究生,E-mail:sdfengxw@126.com.

網絡出版地址：http://www.cnki.net/kcms/detail/61.1076.TN.20151021.1046.018.html