基于骨架和統計直方圖的形狀匹配算法

張桂梅，鄭加寬，儲 珺

ZHANG Guimei,ZHENG Jiakuan,CHU Jun

南昌航空大學 計算機視覺研究所，南昌330063

Institute of Computer Vision,Nanchang Hangkong University,Nanchang 330063,China

1 引言

形狀匹配是計算機視覺中的重要問題，已經被應用在多個領域，如目標識別、圖像檢索、機器人導航和醫學圖像分析等。但目標存在柔性變化和局部遮擋是形狀目標識別面臨的主要困難。

形狀通常由目標范圍的二值圖像所表示，不同于紋理、顏色等其他特征，它是目標物體最本質的特征，具有形象客觀代表目標所具備的基本結構[1]。形狀特征的提取算法大致分為兩類：一類是基于輪廓的方法，一類是基于區域的方法[2]。一般基于輪廓的形狀特征描述方法僅考慮形狀的輪廓信息，提取輪廓特征信息來描述形狀更符合人類生理視覺，Fourier[3]描述子和小波描述子[4]是兩種經典的基于輪廓的形狀特征描述方法，但Fourier描述子不提供形狀的局部信息，并且對噪聲很敏感，小波描述子對形狀輪廓曲線的起點很依賴，小波系數易受噪聲的干擾同時不具有平移、旋轉和縮放不變性。基于區域的形狀特征描述方法考察閉合輪廓內所有的像素，可以更好地表達形狀表現出來的特征，對抵抗輪廓噪聲等等干擾下具有明顯的優勢。典型的基于區域的描述子有區域面積、區域重心、形狀參數、偏心率和不變矩[5]等，基于區域的結構化方法有凸包[6]和中軸（又稱骨架）[7]等。

骨架是對形狀的一種有效描述符，它不但包含了到目標邊界的距離信息，同時包含了目標形狀的拓撲結構，具有處理數據量小，但能準確表示物體形狀等特點。同時文獻[8]研究表明由于骨架特征點內切圓半徑值和骨架路徑長度不隨肢體的變化而變化，所以基于骨架的形狀匹配方法更適合處理目標存在柔性變化和局部遮擋。Bai[9]提出了一種基于骨架路徑識別形狀目標的方法，通過提取當前骨架端點到其他所有骨架端點間的骨架路徑特征，度量端點間相似性。陳珺[10]提出描述接合點，并通過計算骨架圖接合點間的相似性來識別目標。該方法只考慮了形狀主要部分的信息，忽略了形狀的細節信息。

直方圖[11]能把所有信息統計到一圖中，在圖像處理中有重要的作用，本文結合直方圖，用圖來反應骨架結構，主要是統計骨架上所有信息。既能保留骨架主要部分信息，又能保留骨架細節部分信息。Belongies[12]提出形狀上下文概念，考察形狀輪廓特征點與周圍輪廓上特征點的相對空間分布信息，利用二維直方圖來統計分布信息對該特征點的描述。Ling[13]提出形狀輪廓點之間的內部距離概念，該距離是對形狀上下文進行了改進，更加能描述形狀的幾何特征。

文獻[9-10]提出利用骨架作為形狀描述符，提取骨架路徑上部分骨架點作為特征點，進行骨架特征點的相似性度量，雖然時間復雜度比基于輪廓描述方法有所減少，但當等分骨架點提取不準確時，易導致骨架端點的誤匹配，同時文獻[9]要求提取端點位于輪廓上，文獻[10]方法只考慮了接合點的穩定性，但忽略了接合點到端點的細節特征。文獻[12-13]采用輪廓上的點作為特征點，即需要提取當前輪廓特征點與其他特征點在輪廓空間分布關系結合二維統計直方圖來進行相似性度量，但其計算復雜度大，對輪廓局部遮擋時不能有效地識別目標。

針對這些問題，本文提出一種結合骨架和二維統計直方圖識別柔性變化及局部遮擋目標方法，本文的主要貢獻如下：

（1）提出了將骨架接合點作為待描述的特征點，基于骨架接合點構造不變特征；骨架結合點相對于輪廓上的像素點有很大的減少從而能大大提高匹配的效率，同時又比骨架端點提取更穩定，從而能提高匹配的精度。

（2）提出基于骨架接合點構造不變特征量直方圖化方法，結合直方圖的描述方法既能保留目標形狀的主要特征，又能保留目標形狀的細節特征，即能充分地描述形狀的拓撲結構和統計信息。

（3）基于骨架結合點將目標形狀分塊，通過對目標形狀每個骨架結合點的分塊描述匹配實現對整個目標的匹配，所以該方法能有效克服目標存在柔性變化和局部遮擋而難于識別的問題。

2 骨架及特征點

2.1 骨架

1973 年Blum[7]曾提出過一種叫“燒草”的方法，把一塊草地，從各個方向點燃向中心燃燒，燒到火熄滅的位置為止，將火熄滅的位置形成的脊線定義為骨架（又稱中軸）。如圖1 虛線部分所示。

根據骨架基本特征，給定了如下三個定義：

定義1若一個骨架點在骨架上只存在于一個點與其相鄰，則該骨架點被稱為骨架端點；若一個骨架點存在三個或更多的相鄰點，則稱其為骨架接合點。若一個骨架點既不是端點也不是接合點，則稱其為連接點，所有的連接點組合又稱為骨架枝。如圖1 所示，v1，v2，v3為端點，O1接合點，O2為連接點，l1，l2，l3為骨架枝。

圖1 形狀及其骨架

定義2假設有一骨架點O，以骨架點O為圓心以r值為半徑畫圓，使之內切于形狀輪廓且與輪廓至少有兩個切點，此時r值稱為骨架點O的最大圓半徑值。如圖1 所示，以O1，O2為圓心，r1，r2為半徑值的最大圓分別于形狀輪廓相切于點A，B，C和點D，E。

定義3若骨架上存在兩個骨架點O和P，以O為起始點沿著骨架到另一骨架點P所經過的所有骨架點的組合稱為骨架路徑，它的長度稱為路徑距離。如圖1所示，O1O2，O1v1，O1v2，O1v3為所示骨架路徑。

2.2 特征點

本文選取骨架的接合節點作為待描述的特征點，因為使用骨架結合點做骨架路徑的起點時，距離重心的信息將會增多；而選擇骨架端節點做骨架路徑的起點時，骨架分支的信息將會增多，很明顯骨架分支在很多情況下是不穩定，所以骨架接合點相比骨架端點更穩定。根據提取的接合點將目標形狀分成不同的子形狀塊，每塊形狀都有與其對應的骨架枝。如圖1 所示：基于接合點O1可以將形狀分成三塊，每塊形狀都有骨架枝與其對應，骨架枝l1對應于區域OAV1C，骨架枝l2對應于區域OAV2B，骨架枝l3對應于區域OBV3C。

3 構造特征不變量

3.1 特征量的選取

給定一幅形狀骨架，記其一個骨架接合點為O，基于提取的接合點O可以將骨架分成幾個不同形狀的骨架枝，利用骨架點到接合點O的路徑距離li和此骨架點對應的最大圓盤半徑ri兩不變特征量來描述此骨架點，最后利用骨架點集合（除接合點O以外所有骨架點）來描述接合點O。如圖2 所示，設骨架點集合為S（除接合點O以外的所有骨架點）S={si|i=1，2，…，k}，si表示第i個骨架點，有一骨架點p，基于骨架點p可構造兩個特征量：一是該骨架點的最大圓盤半徑值r，另一個是該骨架點到接合點O的路徑距離l，其中p1和p2為骨架點p的最大圓與輪廓的切點。

圖2 骨架接合點的特征量構造

將每個骨架點的兩不變特征量統計整合到一個二維直方圖中，利用該直方圖描述目標形狀，該描述子能充分反映形狀的骨架結構和統計信息。在統計直方圖中，通常用橫坐標表示對應骨架點到接合點O的路徑距離，縱坐標表示骨架點對應的最大圓盤半徑值，所以基于骨架點集合S，在二維統計直方圖可表示為如式（1）所示。其中X={( )ri，li|i=1，2，…，k}為直方圖參數，hij為集合S的數據元素落入矩形區域([xi-1，xi]，[yi-1，yi])中的個數，xi∈[0，1]，yi∈[0，1]。xi為直方圖橫坐標，表示骨架點si到接合點O的路徑距離li，yi表示此骨架點最大圓半徑值ri，H(S，X)表示基于接合點O將骨架分塊后，對骨架接合點O描述的二維統計直方圖。

一幅骨架可以有多個接合點，每個接合點都可以將形狀分成不同大小的塊，每個塊都有對應的骨架枝，可以將此接合點對應的所有骨架枝在一幅二維直方圖中表達出來，用來對此骨架接合點進行描述。因此不同的接合點，其二維直方圖表述不同，所以通過接合點的二維直方圖描述對整個目標形狀進行描述。

如圖3（a）所示為一幅bird 輪廓及其骨架圖，O1和O2為bird 骨架的接合點，基于點O1可以將骨架分成L1，L2，L3三部分，如圖3（b）所示；基于點O2可以將骨架分成L1'，L2'，L3'三部分，如圖3（c）所示。對接合點O1的直方圖描述如圖3（d）所示，對接合點O2的直方圖描述如圖3（e）所示，從圖中可以發現在同一幅骨架圖中，不同的接合點，其直方圖描述差異很大，所以基于結合點的描述方法具有較好的可區分性。

圖3 bird 接合點O1，O2 及其直方圖描述

3.2 特征的不變性處理

為了保證骨架結構特征對目標平移、旋轉具有不變性，對兩個特征量進行如公式（2）和公式（3）所示的歸一化，其中ri表示骨架點S集合中第i個骨架點對應的最大圓半徑值，rmax為S中所有最大圓半徑值中最大的一個；lipath表示骨架點S集合中第i個骨架點到描述的骨架接合點O的骨架路徑，lmaxpath為所有骨架點對應的骨架路徑中最大值。

經過上述特征量歸一化后，保證了骨架結構特征的平移、旋轉不變性，但不能保證對尺度變換變化的不變性。為此，需對二維統計直方圖進行歸一化，如式（4）所示，其中|F|為集合S的勢。

4 算法描述

4.1 相似性度量

設模型圖G1有n個接合點，目標圖G2有m個接合點，則G1可表示為G1=(H1，H2，…，Hn)，G2可以表示為G2=(H1'，H2'，…，Hm')，其中Hi為模型圖接合點i的二維統計直方圖，Hj'表示目標圖接合點j的二維統計直方圖。d(Hi，Hj')代表接合點i和接合點j之間的距離，采用直方圖各元素差的加權和作為為兩幅骨架接合點之間的距離值（即差異度），如式（5）和式（6）所示，其中wk表示權值，M，N表示將二維統計直方圖分成M×N塊，k表示所屬第幾塊。

最后根據公式（7）建立圖矩陣，并利用匈牙利算法[7]找到d(G1，G2)最優匹配，在匈牙利算法中模型圖G1每一個接合點Hi都可以在目標圖G2中找到與其對應的接合點Hj'。由于G1和G2擁有的接合點的個數可能不相同，通過在d(G1，G2)中另增加常數行（一行中元素為相等的常數）使其成為一個方矩陣（行數和列數相等的矩陣）。使用匈牙利算法的目的是使接合點保持全局一致，匈牙利算法雖然不能完全保證匹配序列的順序關系，但不會影響最終的相似性度量，它不但計算復雜度低，而且結果精度也能得到保證。

4.2 匹配算法描述

（1）基于文獻[14]方法提取形狀目標骨架，并提取骨架接合點。

（2）基于骨架結合點將目標形狀分塊，按照3.1 節方法提取對每個接合點的特征量。

（3）按照3.2 節方法對提取的特征量進行歸一化并將其直方圖化。

（4）按照4.1 節中的直方圖各元素差的加權和作為兩接合點的相似性度量。

（5）建立接合點匹配圖矩陣，運用匈牙利算法找到每個接合點最優匹配。

5 實驗及結果分析

為了驗證算法的有效性，使用標準數據集Aslan &Tari56、Kimia99 和Kimia216 進行測試實驗。實驗中選取適當的直方圖參數M×N把描述接合點的直方圖進行分塊，即圓盤半徑比例特征(0，1]區間分成M個，骨架路徑比例特征(0，1]區間分成N個，選取M×N=5×10。

5.1 算法的魯棒性分析

從Kimia99 數據集每類中選取一幅形狀，如圖4 所示，顯示為每幅形狀的輪廓、對應的骨架和骨架中一個接合點（黑色粗點表示），圖5 顯示圖4 中標記的接合點的二維直方圖描述，從圖5 中可以發現不同類形狀的接合點描述其二維統計直方圖插差異較大，說明基于骨架直方圖的描述方法具有很好的可區分性。

圖4 Kimia99 數據集中9 種不同類形狀

為了檢驗算法魯棒性，從以下三方面來驗證：

算法的相似變換驗證（平移、旋轉和縮放），如圖6（a）和圖6（b）所示為模型圖，圖7（a）和圖7（b）為相似變換后的目標圖，匹配結果如圖8（a）和圖8（b）所示，圖6（a）中兩個接合點找到與圖7（a）中兩個接合點匹配，圖6（b）中六個接合點找到與圖7（b）中六個接合點匹配。

算法的柔性變化驗證，如圖6（c）和圖6（d）所示為模型圖，圖7（c）和圖7（d）為相似變換后的目標圖，匹配結果如圖8（c）和圖8（d）所示，雖然目標圖姿態發生了變化，但提取的接合點是穩定的且接合點的二維直方圖表示具有唯一性，所以接合點都能找到對應的匹配點。

算法的局部遮擋驗證，如圖6（e）和圖6（f）所示為模型圖，圖7（e）和圖7（f）為相似變換后的目標圖，匹配結果如圖8（e）和圖8（f）所示，圖6（e）中四個接合點與圖7（e）中四個接合點匹配，圖6（f）中雖然有四個接合點但由于圖7（f）中存在部分遮擋導致只有三個接合點，但是通過匈牙利算法，仍能找到模型圖與目標圖的最優匹配。

圖5 對應圖4 中標記點的直方圖描述

圖8 模型圖與目標圖匹配結果示意圖

5.2 算法性能評價

使用Tari 數據集主要是測試算法對非剛性物體的適用性，Tari 數據集共有14 類物體如圖9（a）所示，每類物體包括4 個形狀，故共有56 個形狀。每輸入一個形狀與測試集中的樣本進行比較，按相似程度進行排序，找到相似度最高的前三個圖像。并將該方法與文獻[9]和文獻[13]進行比較，其結果如表1 所示，從表中數據可以看出本文的算法能全部檢測出同類經過柔性變化的目標，即檢測精度為100%。

表2 Kimia216 檢索結果

圖9 Aslan & Tari56 和Kimia216 數據 集

表1 Aslan & Tari56

在Kimia216 數據集上進行測試，Kimia216 包含18個類，每個類包括12 個形狀，共有216 個形狀，是形狀測試數據庫MPEG7_CE-Shape-1_Part_B 中的一個子集，如圖9（b）所示。每輸入一個待檢索形狀，計算其與數據庫中的每個形狀之間的距離，然后把距離最小的形狀作為第一相似形狀，依次類推，共檢索到第十一相似形狀，最后統計每一級圖像與待檢索圖像屬于一類個數。與兩種經典的形狀識別算法（SC[12]，Shock Edit[15]）及文獻[9]比較，其結果如表2 所示，發現本文算法要優于以上算法，主要由于本文算法采用了骨架接合點作為特征點，并結合了二維統計直方圖描述方法，具有更好的對同類相似目標的區分能力。

5.3 時間復雜度分析

本文采用基于離散曲線演化的生長骨架算法[14]提取骨架，其時間復雜度為O(mn)，其中m，n分別為二值圖像的寬和高。設提取的骨架總共有k個骨架點，求其到骨架接合點的路徑距離時間復雜度為O(k)，假設將二維直方圖分成M×N塊，則構造直方圖需要的時間復雜度為O(max(M，N)×k)，最后采用匈牙利算法找到最優匹配，其時間復雜度為（ni和mj為骨架接合點個數，假設ni＞mj），所以總的時間復雜度不大于

6 結論

提出了一種新的結合骨架和直方圖的形狀匹配方法。由于本文提出利用骨架接合點作為特征點，骨架結合點較骨架端點提取更穩定，從而能提高匹配精度；本文算法根據結合點將目標形狀分塊，基于接合點構造不變特征量并將這些特征量直方圖化，二維統計直方圖既能保留形狀的主要特征，又能保留形狀的細節特征，故本文算法能處理柔性變化和局部遮擋的目標形狀。理論分析和實驗結果均表明，該算法能有效地進行柔性目標的識別，并能處理局部遮擋。

[1] 周瑜，劉俊濤，白翔.形狀匹配方法研究與展望[J].自動化學報，2012，38（6）：889-910.

[2] Zhang Dengsheng，Lu Guojun.Review of shape representation and description techniques[J].Patten Recognition，2004，37（l）：10-16.

[3] Erie P，Sun Fu King.Shape discrimination using Fourier descriptors[J].IEEE Transactions on Systems，Man and Cybernetics，1977，7（3）：170-179.

[4] Chuang Gene C H，Kuo C C Jay.Wavelet descriptor of planar curves：theory and application[J].IEEE Transactions on Image Processing，1996，5（1）：56-70.

[5] Liao S X，Pawlak M.On Image analysis by moments[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1996，18（3）：254-266.

[6] Davies E R.Machine vision：theory，algorithms，practicalities[M].New York：Academic Press，1997：171-191.

[7] Blum H.Biological shape and visual science（Part l）.Theoretical Biology，1973，38：205-287.

[8] Sebastian T，Kimia B.Curves skeleton in object recognition[J].Signal Processing，2005，85（2）：247-263.

[9] Bai X，Latecki L J.Path similarity skeleton graph matching[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2008，30（7）：1282-1292.

[10] 陳珺，白翔，劉文予.基于骨架接合節點特征的形狀識別與分類[J].計算機科學，2011，38（1）：279-281.

[11] 湯進，江波，羅斌.基于直方圖的形狀描述及骨架圖匹配算法[J].華南理工大學學報：自然科學版，2010，38（7）：27-32.

[12] Belongie S，Malik J，Puzhieha J.Shape matching and object recognition using shape contexts[J].IEEE Transactions Patten Analysis and Machine Intelligence，2002，24（4）：509-522.

[13] Ling H B，Jacobs D W.Shape classification using Inner-Distance[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2007，29（2）：286-299.

[14] 丁頤，劉文予，鄭宇化.基于距離變換的連通骨架算法[J].紅外與毫米波學報，2005，24（4）：281-285.

[15] Aslan C，Tari S.An axis-based representation for recognition[C]//Proceeding of the IEEE International Conference on Computer Vision，2005：1339-1346.