吳建立，劉宏申

(安徽工業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,安徽 馬鞍山 243000)

一種新的形狀描述與識別方法

吳建立，劉宏申

(安徽工業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,安徽 馬鞍山 243000)

在形狀上下文基礎(chǔ)上，提出一種新的形狀描述符。該形狀描述符以形狀質(zhì)心為參考坐標(biāo)原點建立對數(shù)極坐標(biāo)，并由質(zhì)心與邊界樣本點之間的距離及其內(nèi)角兩維構(gòu)成，其中內(nèi)角采用質(zhì)心與邊界點連線與輪廓切線之間的切角。這種新的形狀描述子計算簡單，能較好地區(qū)分不同的形狀，且具有平移、縮放和旋轉(zhuǎn)不變性，適合使用神經(jīng)網(wǎng)絡(luò)來作為識別分類器。最后以神經(jīng)網(wǎng)絡(luò)算法作為分類器，在MNIST手寫數(shù)字?jǐn)?shù)據(jù)庫和Kimia圖像數(shù)據(jù)庫進(jìn)行了實驗驗證。實驗結(jié)果顯示：該方法在單目標(biāo)形狀圖像檢索中取得了較好的檢索效果，同時顯著地減少了檢索所需的時間，適用于較大型圖像數(shù)據(jù)庫的檢索任務(wù)。

形狀匹配；形狀上下文；形狀檢索；神經(jīng)網(wǎng)絡(luò)；手寫數(shù)字識別

隨著科技的發(fā)展，形狀相似性檢索與圖像識別成為圖像處理領(lǐng)域中最為主要的研究問題。近些年來，形狀檢索與識別方法在圖像處理領(lǐng)域有著較為廣泛的應(yīng)用。用于形狀描述的方法有很多[1-2]。形狀描述方法主要分為基于圖像區(qū)域和基于圖像輪廓的描述方法?；趫D像區(qū)域的描述方法使用圖像的全部信息來對圖像進(jìn)行描述，這類方法主要有幾何不變矩法，由Hu在1962年提出[3]；基于圖像輪廓的描述方法使用圖像的外部邊緣信息對圖像進(jìn)行描述，這類方法主要有小波輪廓描述符(wavelet descriptor)[4]、Freeman鏈碼[5]、形狀上下文描述子(shape contexts)[6-7]等。其中，形狀上下文描述子是近年來提出的性能較為優(yōu)秀的描述符，在形狀相似性檢索領(lǐng)域獲得了較為廣泛的應(yīng)用，但其也存在著不足之處。

形狀上下文描述符由Serge Belongie等在2000年提出[6-7]，主要利用對數(shù)極坐標(biāo)來統(tǒng)計邊界樣本點相對于參考坐標(biāo)原點的位置關(guān)系對圖像進(jìn)行描述，取得了相對較好的檢索準(zhǔn)確率，且在圖像檢索和匹配領(lǐng)域有著廣泛地應(yīng)用[8-10]。它屬于基于形狀輪廓的描述子，主要統(tǒng)計邊界樣本點相對于其他邊界樣本點的相對位置關(guān)系。其中，兩個邊界樣本點之間的相似程度可以通過比較形狀上下文距離來衡量。為了實現(xiàn)兩個形狀之間的相似性匹配，形狀上下文算法使用薄板樣條函數(shù)(TPS)[11-12]和匈牙利算法[10]來尋找兩個形狀之間樣本點的最佳匹配，以此來最小化形狀間的距離，從而達(dá)到匹配的目的。但是薄板樣條函數(shù)的匹配屬于強力匹配，在比較形狀相似度的過程中需要尋找兩個待匹配形狀邊界樣本點之間的最佳對應(yīng)關(guān)系，從而最小化形狀上下文距離，故在匹配過程中耗時大，限制了形狀上下文描述符在較大型圖像數(shù)據(jù)庫檢索任務(wù)中的應(yīng)用。

針對傳統(tǒng)形狀上下文描述符在形狀匹配過程中的耗時等問題，Greg Mori等[13]提出了一種快速剪枝的方法。該算法先使用傳統(tǒng)形狀上下文對形狀進(jìn)行描述，之后對得到的形狀上下文描述子進(jìn)行聚類(一般使用K-means算法進(jìn)行聚類)，并將聚類得到的類別作為新的形狀描述子。這些改進(jìn)雖然降低了檢索過程中的時間消耗，但由于是對得到的形狀上下文進(jìn)行聚類，降低了匹配的精度。文獻(xiàn)[16]將傳統(tǒng)形狀上下文描述符與神經(jīng)網(wǎng)絡(luò)相結(jié)合，提出了一種結(jié)合神經(jīng)網(wǎng)絡(luò)的形狀上下文描述符，但該算法為了減少算法的復(fù)雜度，僅選取較少的邊界樣本點的形狀上下文作為神經(jīng)網(wǎng)絡(luò)的輸入，雖然降低了算法檢索所需的時間，卻犧牲了算法匹配的精度。針對現(xiàn)有描述方法在檢索中比較耗時。而改進(jìn)算法雖然提高了檢索速度，但是損失了準(zhǔn)確性的問題。本文提出了一種新的形狀描述符，并將其作為神經(jīng)網(wǎng)絡(luò)分類器的輸入特征，以此來進(jìn)行形狀相似性檢索。使用MNIST手寫數(shù)字?jǐn)?shù)據(jù)庫[14]和Kimia99圖像數(shù)據(jù)庫[15]來測試本文提出的方法，對比實驗結(jié)果顯示本文提出的方法較傳統(tǒng)形狀上下文算法的準(zhǔn)確率雖有所降低，但檢索所需時間遠(yuǎn)低于傳統(tǒng)形狀上下文。相較文獻(xiàn)[16](記為SC+BP)中的方法，檢索需要的時間基本相同，但是檢索準(zhǔn)確率有所提高。本文方法減少了相似性檢索所需的時間，適用于較大型圖像數(shù)據(jù)庫的檢索任務(wù)。

1 改進(jìn)的形狀描述符

1.1 形狀及切角表示

對于給定的形狀，邊界樣本點與其質(zhì)心的空間位置關(guān)系反映了形狀的某些特征，因此可以用邊界樣本點相對于形狀質(zhì)心的空間位置關(guān)系來對形狀進(jìn)行描述。對于一個給定的形狀，用canny輪廓分割算法提取其邊界輪廓，并采用均勻采樣算法對獲得的形狀輪廓進(jìn)行均勻采樣，得到輪廓樣本點集合P={p1,p2,…,pn}，其中n表示采樣的樣本點數(shù)目。這些邊界樣本點基本可以對形狀輪廓進(jìn)行描述(見圖1，表示圖像輪廓及樣本點提取效果圖)，并計算形狀的質(zhì)心坐標(biāo)p0(x0,y0)。質(zhì)心的計算方法如式(1)所示，其中S表示待計算目標(biāo)；I(i,j)表示目標(biāo)的灰度值。圖1中(a)表示原始圖像；(b)表示形狀輪廓提取結(jié)果；(c)表示輪廓均勻采樣結(jié)果，*表示形狀質(zhì)心。

(1)

圖1 圖像輪廓提取效果圖

然而，圖像的形狀千變?nèi)f化，并不是所有形狀的輪廓都是連續(xù)的或者只有單個目標(biāo)。對于圖像中只有一個目標(biāo)形狀，但是輪廓不連續(xù)的情況(如圖2(a)所示)，由于本文方法只是選取部分邊界樣本點來計算新的形狀描述符，因此對于這種邊界不連續(xù)的情況，按照上述方法進(jìn)行邊界樣本點提取即可。對于一個圖像中有多個目標(biāo)的形狀(如圖2(b)所示)，若只計算整個圖像的質(zhì)心，則不會獲得更好的效果。針對這種情況，分別獲取每個子形狀的輪廓及其對應(yīng)的質(zhì)心(如圖2(c)和(d)所示)，對于多個目標(biāo)的復(fù)雜形狀，采用分割法將其分割成不同的子形狀來進(jìn)行考慮。假設(shè)Q表示多目標(biāo)形狀，則其對應(yīng)的邊界樣本點及質(zhì)心可以表示為：

Q={[α1,α2,…,αn],[β1,β2,…,βm],…}

P={p1,p2,…,pn}

其中：α和β分別表示子形狀的邊界樣本點；P={p1,p2,…,pn}表示子形狀的質(zhì)心。

圖2 多目標(biāo)圖像示例

傳統(tǒng)形狀上下文使用對數(shù)極坐標(biāo)來統(tǒng)計邊界樣本點之間的相對位置關(guān)系，但是其不具備旋轉(zhuǎn)不變性。文獻(xiàn)[16]使用傳統(tǒng)形狀上下文作為神經(jīng)網(wǎng)絡(luò)的輸入特征，使得其對形狀之間的旋轉(zhuǎn)缺少魯棒性。分析邊界樣本點和形狀質(zhì)心之間的關(guān)系，發(fā)現(xiàn)邊界樣本點及其輪廓切線、形狀質(zhì)心之間的夾角具有旋轉(zhuǎn)不變性。對于給定的形狀邊界樣本點集合P={p1,p2,…,pn}和形狀質(zhì)心p0(x0,y0)，選取邊界樣本點ρ∈P，它與形狀質(zhì)心之間的歐式距離記為Γ(ρ,p0)，ρ點處的輪廓切線記為T，則T和Γ之間的夾角記為β，將該夾角稱為切角(tangent-angle)，如圖3所示。對同一形狀進(jìn)行相應(yīng)的旋轉(zhuǎn)并計算旋轉(zhuǎn)之后的切角，發(fā)現(xiàn)其角度并沒有發(fā)生變化，如圖4所示。

圖3 切角示意圖

圖4 旋轉(zhuǎn)后的切角示意

1.2 構(gòu)建描述符

hi(k)=#{q≠pi:(q-pi)∈bin(k)}

(2)

半徑角度15°30°45°60°75°90°105°120°135°150°165°1800.1250000000000000.250000000000000.52200121200211177660370085209978098111078

圖6 圖1中人形圖像對應(yīng)的新描述符

Fig.6 New descriptor of human image in Figure 1

2 形狀相似性匹配

形狀之間的相似性度量直接影響識別和檢索的有效性和準(zhǔn)確性，同時匹配算法的選擇也影響著匹配效率及所需時間。研究者一直致力于研究如何有效地表示形狀在特征上的相似度。Serge Belongie等[6-7]提出的形狀上下文算法在匹配過程中使用匈牙利算法[10]結(jié)合薄板樣條函數(shù)(TPS)對形狀進(jìn)行迭代匹配。這種匹配方法雖然能夠較好地進(jìn)行形狀間相似性的匹配，但是需要尋找形狀樣本點之間的最佳對應(yīng)關(guān)系，以此來最小化匹配形狀之間的形狀距離，從而達(dá)到形狀匹配的目的。雖然這種方法能匹配形狀之間的相似程度，也具有較好的準(zhǔn)確性和魯棒性，但是屬于強力匹配，且匹配的過程十分耗時，使得該方法只適于小型圖像數(shù)據(jù)庫的檢索任務(wù)，很難應(yīng)用于較大型圖像數(shù)據(jù)庫的檢索任務(wù)。

對形狀上下文相關(guān)算法的匹配過程進(jìn)行深入的研究，發(fā)現(xiàn)它們都是先進(jìn)行樣本點與樣本點之間的匹配，再計算形狀之間的距離，這極大增加了相似性匹配的時間。為了減少形狀匹配的時間消耗，本文采用被廣泛使用的神經(jīng)網(wǎng)絡(luò)算法來度量形狀之間的相似性。神經(jīng)網(wǎng)絡(luò)在處理分類相關(guān)問題時有著很好的分類效果，且所需要的時間性能較匈牙利等算法有著較大的提高。本文將新的形狀特征描述符作為神經(jīng)網(wǎng)絡(luò)的輸入特征來進(jìn)行形狀相似性檢索，將神經(jīng)網(wǎng)絡(luò)的輸出作為形狀的類別。雖然使用神經(jīng)網(wǎng)絡(luò)失去了相似性度量的一些精度，但是卻極大縮短了匹配過程中所消耗的時間。簡單地說，新的形狀描述符可以被看作統(tǒng)計樣本點落入柵格中個數(shù)的直方圖，可以將這些直方圖作為神經(jīng)網(wǎng)絡(luò)的特征輸入來進(jìn)行形狀相似度匹配。這種新的方法可用于較大型圖像數(shù)據(jù)庫的檢索任務(wù)，極大提高了算法的實用性。

為了減少輸入特征的數(shù)目，對每個形狀提取100個樣本點，在距離方向上進(jìn)行5等分(分別為0.125,0.25，0.5，1，2)，角度方向進(jìn)行12等分，這樣每個形狀可以得到60個特征(柵格)。過多的特征對形狀匹配的精確度提升不大，也會增加神經(jīng)網(wǎng)絡(luò)的特征輸入和匹配的時間，影響算法的效率。

3 仿真實驗及結(jié)果分析

為了驗證本文提出方法的魯棒性和其在檢索時間方面的提升效果，使用MNIST手寫數(shù)字?jǐn)?shù)據(jù)庫[14]、Kimia99圖像數(shù)據(jù)庫[15]進(jìn)行實驗驗證。實驗中原始形狀上下文算法記為SC+TPS。由于形狀上下文算法中樣本點數(shù)目過多，為了減少神經(jīng)網(wǎng)絡(luò)算法的復(fù)雜度，選取固定間隔的6個形狀上下文(因為形狀上下文對相近點比較敏感)，記為SC+BP。實驗中使用到的神經(jīng)網(wǎng)絡(luò)為BP神經(jīng)網(wǎng)絡(luò)，具有1個隱藏節(jié)點，輸出特征數(shù)為圖像的類別數(shù)目。

3.1 MNIST手寫數(shù)據(jù)庫匹配

MNIST數(shù)據(jù)庫[14](mixed national institute of standards and technology database)是一個大型的用于訓(xùn)練不同圖像處理系統(tǒng)的手寫數(shù)字?jǐn)?shù)據(jù)庫。MNIST數(shù)據(jù)庫包含60 000個訓(xùn)練圖像和10 000個測試圖像。訓(xùn)練集和測試集的一半來自MNIST訓(xùn)練數(shù)據(jù)庫，另一半來自MNIST測試數(shù)據(jù)庫。為了減少實驗的復(fù)雜度，從MNIST手寫數(shù)字?jǐn)?shù)據(jù)庫中選取600幅手寫數(shù)字圖像作為測試數(shù)據(jù)集，其中共有10類手寫數(shù)字圖像，每類60幅圖像，共計600幅圖像。使用其中的300幅圖像作為訓(xùn)練數(shù)據(jù)集，剩下的300幅作為測試數(shù)據(jù)集。神經(jīng)網(wǎng)絡(luò)算法使用反向神經(jīng)網(wǎng)絡(luò)(back propagation neural network)。對于BP神經(jīng)網(wǎng)絡(luò)的配置，輸入層的大小由輸入特征的數(shù)目決定，輸出層的大小由字符類別的數(shù)目決定(此處為10)，隱藏層的大小由輸入層和輸出層的大小共同決定。使用1個隱藏層的BP神經(jīng)網(wǎng)絡(luò)，其隱藏層的節(jié)點數(shù)為100，這些配置信息一般由驗證圖像數(shù)據(jù)集來決定。圖8展示了部分手寫數(shù)字。

表1為SC+TPS(傳統(tǒng)形狀上下文算法)、SC+BP(文獻(xiàn)[16]方法)和本文方法在MNIST手寫數(shù)字?jǐn)?shù)據(jù)集中檢索的結(jié)果?？梢钥闯觯弘m然本文所述方法識別的準(zhǔn)確率略微低于SC+TPS算法，但在檢索時間方面遠(yuǎn)低于SC+TPS算法。這是因為：SC采樣的Hungarian+TPS方法屬于強力匹配，匹配過程十分耗時，而使用BP神經(jīng)網(wǎng)絡(luò)的本文方法不需要尋找兩個待匹配形狀之間點的對應(yīng)關(guān)系，這極大地縮短了匹配過程需要的時間。因此，本文方法適用于較大型圖像數(shù)據(jù)庫的檢索任務(wù)。

表1 MNIST手寫數(shù)字?jǐn)?shù)據(jù)庫檢索示例Table 1 Retrieval example of MNIST handwritten number

圖7 MNIST匹配速度對比

圖8 部分MNIST手寫數(shù)字

3.2 Kimia數(shù)據(jù)庫匹配測試與分析

Kimia圖像數(shù)據(jù)庫[15]由Kimia25、Kimia99和Kimia216 等圖像數(shù)據(jù)庫組合而成。為了減少實驗復(fù)雜度和所需時間，僅選取其中的Kimia99數(shù)據(jù)庫來進(jìn)行匹配準(zhǔn)確性和匹配時間的相關(guān)測試。Kimia99 圖像數(shù)據(jù)庫中共有9種不同類別的圖像，每種不同的類別主要有11個不同的圖像，該圖像數(shù)據(jù)庫共有99個不同的形狀圖像，如圖9所示。將圖像數(shù)據(jù)庫中的每種形狀依次作為待匹配的圖像，檢索圖像數(shù)據(jù)庫中與它相似的圖像，并對查詢到的相似圖像進(jìn)行準(zhǔn)確度統(tǒng)計。改進(jìn)的方法與SC+TPS算法、文獻(xiàn)[16]方法(記為SC+BP)對Kimia99數(shù)據(jù)庫的形狀檢索結(jié)果及檢索速度如表2、圖10所示，其中橫坐標(biāo)對應(yīng)圖10中9個不同類別形狀標(biāo)號，縱坐標(biāo)為檢索每一類所需時間。從圖10可以看出：本文算法的檢索率與SC+TPS相當(dāng)，但是檢索速度有了較大的提升；SC+BP算法和本文算法在檢索時間方面不相上下，但是檢索準(zhǔn)確率低于本文算法。

表2 Kimia99數(shù)據(jù)庫檢索結(jié)果

圖9 Kimia99圖像數(shù)據(jù)庫

圖10 匹配速度對比

4 結(jié)束語

為了減少大型圖像數(shù)據(jù)庫檢索任務(wù)所需時間，提高匹配算法的運算速率，本文提出了一種新的結(jié)合神經(jīng)網(wǎng)絡(luò)的匹配算法。實驗結(jié)果顯示本文算法不僅具有一定的魯棒性，且極大地縮短了檢索時間，使得算法能應(yīng)用于較大型圖像數(shù)據(jù)庫的檢索任務(wù)，提高了算法的實用性。本次實驗中使用的是BP神經(jīng)網(wǎng)絡(luò)，未來計劃進(jìn)行與其他神經(jīng)網(wǎng)絡(luò)算法的結(jié)合實驗，進(jìn)一步增加算法的魯棒性和有效性。

[1] ZHANG D,LU G.Review of shape representation and description techniques[J].Pattern Recognition,2004,37(1):1-19.

[2] 丁險峰，吳洪，張宏江，等.形狀匹配綜述[J].自動化學(xué)報，2001,27(5):678-694.

DING Xianfeng,WU Hong,ZHANG Hongjiang,et al.Review on Shape Matching[J].Acta Automatica Sinica,2001,27(5):678-694.

[3] HU M K.Visual pattern recognition by moment invariants[J].IRE Transactions on Information Theory,1962(8):179-187.

[4] YADAV R B,NISHCHAL N K,GUPTA A K,et al.Retrieval and classification of shape-based objects using Fourier,generic Fourier,and wavelet-Fourier descriptors technique:A comparative study[J].Optics and Lasers in engineering,2007,45(6):695-708.

[5] FREEMAN H.Computer Processing of Line Drawing Images[J].ACM Computing Surveys,1974,6(1):57-97.

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

[7] BELONGIE S,MALIK J,PUZICHA J.Shape Context:A New Descriptor for Shape Matching and Object Recognition[C]//Advances in Neural Information Processing Systems 13:Proc.2000 Conf.USA:[s.n.],2000:831-837.

[8] 吳曉雨,何彥,楊磊,等.基于改進(jìn)形狀上下文特征的二值圖像檢索[J].光學(xué)精密工程,2015,23(1):302-309.

WU Xiaoyu,HE Yan,YANG Lei,et al.Binary image retrieval based on improved shape context algorithm[J].Optics and Precision Engineering,2015,23(1):302-309.

[9] 鄭丹晨,韓敏.基于改進(jìn)典型形狀上下文特征的形狀識別方法[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報,2013,25(2):215-220.

ZHENG Danchen,HAN Min.Improved Shape Recognition Method Based on Representative Shape Context[J].Journal of Computer-Aided Design and Computer Graphics,2013,25(2):215-220.

[10]PAPADIMITRIOU C,STIEGLITZ K.Combinatorial Optimization:Algorithms and Complexity[M].[S.l.]:Prentice Hall,1982.

[11]DUCHON J.Splines Minimizing Rotation-Invariant Semi-Norms in Sobolev Spaces[J].Lecture Notes in Mathematics,1977,571:85-100..

[12]MEINGUET J.Multivariate Interpolation at Arbitrary Points Made Simple[J].ZAMP,1979(5):439-468.[13]MORI G,BELONGIE S,MALIK J.Efficient shape matching using shape contexts[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2005(11):1832-1837.[14]LECUN Y,BOTTOU L,BENGIO Y,et al.Gradient-based learning applied to document recognition[J].Proceedings of the IEEE,1998,86(11):2278-2324.

[15]XIANG B,YANG X,LATECKI L J,et al.Learning Context-Sensitive Shape Similarity by Graph Transduction[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2010,32(5):861-874.

[16]JULCA-AGUILAR F,VIARD-GAUDIN C,MOUCHèRE H,et al.Integration of Shape Context and Neural Networks for Symbol Recognition[C]//Colloque International Francophone sur l’écrit et le Document 2014(CIFED).France:[s.n.],2014.

(責(zé)任編輯 楊黎麗)

A New Method of Shape Description and Recognition

WU Jian-li, LIU Hong-shen

(School of Computer Science and Technology, Anhui University of Technology, Ma’anshan 243000, China)

Based on the shape context, a new shape descriptor was proposed. The shape descriptor was based on the shape of the center of mass to establish the polar coordinates of the reference point, and was formed by the distance and inner-angle between the centroid and boundary samples, and the inner-angle used the tangent-angle between the centroid and the boundary line and contour tangent angle. This new shape descriptor is simple to calculate, and can be good to distinguish between different shapes, and are invariant to translations and scaling, and is very suitable for using neural networks as recognition classifier. At last, the neural network algorithm was used as the classifier, and experimental results in MNIST handwritten numerals database and Kimia databases were shown that the method has achieved good results in single object shape image retrieval, and significantly reduces the search time, and is suitable for large image databases retrieval tasks.

shape matching; shape context; shape retrieval; neural network; handwritten digit recognition

2016-10-28

吳建立(1991—)，男，安徽池州人，碩士研究生，主要從事數(shù)字圖像處理與模式識別研究，E-mail:wujianli1991@163.com。

吳建立，劉宏申.一種新的形狀描述與識別方法[J].重慶理工大學(xué)學(xué)報(自然科學(xué))，2017(2):110-116.

format：WU Jian-li, LIU Hong-shen.A New Method of Shape Description and Recognition[J].Journal of Chongqing University of Technology(Natural Science)，2017(2):110-116.

10.3969/j.issn.1674-8425(z).2017.02.019

TP391.4

A

1674-8425(2017)02-0110-07