基于骨架和統(tǒng)計直方圖的形狀匹配算法

張桂梅，鄭加寬，儲 珺

ZHANG Guimei,ZHENG Jiakuan,CHU Jun

南昌航空大學(xué) 計算機(jī)視覺研究所，南昌330063

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

1 引言

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

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

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

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

文獻(xiàn)[9-10]提出利用骨架作為形狀描述符，提取骨架路徑上部分骨架點作為特征點，進(jìn)行骨架特征點的相似性度量，雖然時間復(fù)雜度比基于輪廓描述方法有所減少，但當(dāng)?shù)确止羌茳c提取不準(zhǔn)確時，易導(dǎo)致骨架端點的誤匹配，同時文獻(xiàn)[9]要求提取端點位于輪廓上，文獻(xiàn)[10]方法只考慮了接合點的穩(wěn)定性，但忽略了接合點到端點的細(xì)節(jié)特征。文獻(xiàn)[12-13]采用輪廓上的點作為特征點，即需要提取當(dāng)前輪廓特征點與其他特征點在輪廓空間分布關(guān)系結(jié)合二維統(tǒng)計直方圖來進(jìn)行相似性度量，但其計算復(fù)雜度大，對輪廓局部遮擋時不能有效地識別目標(biāo)。

針對這些問題，本文提出一種結(jié)合骨架和二維統(tǒng)計直方圖識別柔性變化及局部遮擋目標(biāo)方法，本文的主要貢獻(xiàn)如下：

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

（2）提出基于骨架接合點構(gòu)造不變特征量直方圖化方法，結(jié)合直方圖的描述方法既能保留目標(biāo)形狀的主要特征，又能保留目標(biāo)形狀的細(xì)節(jié)特征，即能充分地描述形狀的拓?fù)浣Y(jié)構(gòu)和統(tǒng)計信息。

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

2 骨架及特征點

2.1 骨架

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

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

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

圖1 形狀及其骨架

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

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

2.2 特征點

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

3 構(gòu)造特征不變量

3.1 特征量的選取

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

圖2 骨架接合點的特征量構(gòu)造

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

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

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

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

3.2 特征的不變性處理

為了保證骨架結(jié)構(gòu)特征對目標(biāo)平移、旋轉(zhuǎn)具有不變性，對兩個特征量進(jìn)行如公式（2）和公式（3）所示的歸一化，其中ri表示骨架點S集合中第i個骨架點對應(yīng)的最大圓半徑值，rmax為S中所有最大圓半徑值中最大的一個；lipath表示骨架點S集合中第i個骨架點到描述的骨架接合點O的骨架路徑，lmaxpath為所有骨架點對應(yīng)的骨架路徑中最大值。

經(jīng)過上述特征量歸一化后，保證了骨架結(jié)構(gòu)特征的平移、旋轉(zhuǎn)不變性，但不能保證對尺度變換變化的不變性。為此，需對二維統(tǒng)計直方圖進(jìn)行歸一化，如式（4）所示，其中|F|為集合S的勢。

4 算法描述

4.1 相似性度量

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

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

4.2 匹配算法描述

（1）基于文獻(xiàn)[14]方法提取形狀目標(biāo)骨架，并提取骨架接合點。

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

（3）按照3.2 節(jié)方法對提取的特征量進(jìn)行歸一化并將其直方圖化。

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

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

5 實驗及結(jié)果分析

為了驗證算法的有效性，使用標(biāo)準(zhǔn)數(shù)據(jù)集Aslan &Tari56、Kimia99 和Kimia216 進(jìn)行測試實驗。實驗中選取適當(dāng)?shù)闹狈綀D參數(shù)M×N把描述接合點的直方圖進(jìn)行分塊，即圓盤半徑比例特征(0，1]區(qū)間分成M個，骨架路徑比例特征(0，1]區(qū)間分成N個，選取M×N=5×10。

5.1 算法的魯棒性分析

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

圖4 Kimia99 數(shù)據(jù)集中9 種不同類形狀

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

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

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

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

圖5 對應(yīng)圖4 中標(biāo)記點的直方圖描述

圖8 模型圖與目標(biāo)圖匹配結(jié)果示意圖

5.2 算法性能評價

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

表2 Kimia216 檢索結(jié)果

圖9 Aslan & Tari56 和Kimia216 數(shù)據(jù) 集

表1 Aslan & Tari56

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

5.3 時間復(fù)雜度分析

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

6 結(jié)論

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

[1] 周瑜，劉俊濤，白翔.形狀匹配方法研究與展望[J].自動化學(xué)報，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] 陳珺，白翔，劉文予.基于骨架接合節(jié)點特征的形狀識別與分類[J].計算機(jī)科學(xué)，2011，38（1）：279-281.

[11] 湯進(jìn)，江波，羅斌.基于直方圖的形狀描述及骨架圖匹配算法[J].華南理工大學(xué)學(xué)報：自然科學(xué)版，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].紅外與毫米波學(xué)報，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.