基于截線法的快速骨架提取算法

高立青　　王延章

基于截線法的快速骨架提取算法

高立青1王延章1

提出了一種快速的骨架提取算法.該方法首先在輪廓離散曲線演化的基礎(chǔ)上，根據(jù)顯著凸頂點(diǎn)的類型將輪廓多邊形進(jìn)行分塊，得到一個(gè)主分支輪廓和多個(gè)水平分支輪廓；然后分別利用水平截線法和垂直截線法提取骨架的主分支和水平分支；最后將水平分支拼接在主分支上，得到完整的骨架.實(shí)驗(yàn)結(jié)果表明，該骨架提取算法可以得到連通的骨架，并在Kimia數(shù)據(jù)集上取得了較好的效果.此外，算法在自然圖像上的效果也很好，尤其適用于視頻中的行人骨架提取.與經(jīng)典骨架提取算法相比，該算法的時(shí)間復(fù)雜度較低，可以滿足實(shí)時(shí)處理的要求.

近似骨架提取，離散曲線演化，顯著閉合輪廓，連通骨架

引用格式高立青，王延章.基于截線法的快速骨架提取算法.自動(dòng)化學(xué)報(bào)，2016，42（7）:1100-1112

物體識(shí)別是計(jì)算機(jī)視覺領(lǐng)域最重要的問題之一.目前識(shí)別率較高的方法是基于紋理、顏色等局部特征的機(jī)器學(xué)習(xí)方法，而這些向量形式的特征并不是我們?nèi)祟惪梢灾苯永斫獾奶卣?形狀是人類視覺認(rèn)知的主要特征之一，基于形狀的匹配方法［1［4］通過學(xué)習(xí)同類物體的骨架信息實(shí)現(xiàn)目標(biāo)的檢測；文獻(xiàn)［5—9］實(shí)現(xiàn)了基于骨架的形狀分類；文獻(xiàn)［10］在文獻(xiàn)［11］所提的骨架思路基礎(chǔ)上，基于離散曲線演化進(jìn)行剪枝，并實(shí)現(xiàn)手寫字符識(shí)別等.

骨架，又稱為物體的中軸（Medial axis）［12］.傳統(tǒng)骨架提取方法主要分為五種類型［13］：

1）拓?fù)浼?xì)化算法（Topology thinning）［14-15］，又稱模擬火燒稻草法.此類算法主要思路是：從所有邊界同時(shí)向輪廓內(nèi)部進(jìn)行細(xì)化，直至得到一維骨架.拓?fù)浼?xì)化算法的優(yōu)點(diǎn)是能得到連通的骨架，保持了原物體的拓?fù)浣Y(jié)構(gòu)，且實(shí)現(xiàn)起來簡單，但是它對(duì)邊界噪聲較敏感，易產(chǎn)生很多較小的分支.

2）基于Voronoi圖的離散域算法［16-17］，即將輪廓多邊形內(nèi)部最大圓盤中心的軌跡作為骨架點(diǎn).Voronoi圖方法所提取的骨架精確，但是易受到邊界噪聲的影響，并且時(shí)間復(fù)雜度較高，不具有魯棒性.

3）基于迭代收縮物體輪廓算法［18-20］.該方法直接對(duì)近似的形狀多邊形進(jìn)行對(duì)稱軸計(jì)算，容易受邊界噪聲影響，并且很難處理有洞的物體形狀的骨架.

4）基于距離變換及其改進(jìn)算法［21-25］.該類算法的主要思路是：首先生成原始模型的距離場，然后提取并連接距離場中的局部極值點(diǎn)，最后適當(dāng)調(diào)整細(xì)化得到骨架.該類算法可以提取準(zhǔn)確的骨架點(diǎn)，但是時(shí)間復(fù)雜度較高.

5）基于數(shù)學(xué)形態(tài)學(xué)算法［26-29］.該方法可以獲得精確的骨架，但時(shí)間復(fù)雜度較高.

骨架化算法存在的主要問題是對(duì)輪廓細(xì)節(jié)過于敏感，容易產(chǎn)生很多小的分支，從而導(dǎo)致后續(xù)的識(shí)別工作幾乎無法進(jìn)行.人類視覺總是可以僅關(guān)注物體骨架的主要分支，而忽略一些由于邊界輪廓微小變化產(chǎn)生的小分支.因此在骨架化的同時(shí)需要對(duì)骨架進(jìn)行剪枝，目前較好的剪枝效果為Bai等提出的基于離散曲線演化［30］的骨架剪枝算法［31］和Shen等提出的基于貝葉斯后驗(yàn)概率的剪枝算法［32］，所應(yīng)用的骨架是采用距離變換［33］方法得到的.雖然這兩種算法提取的骨架很精確，并且沒有細(xì)小分支，但是其算法復(fù)雜度較高，運(yùn)行速度相對(duì)較慢.由于在視頻監(jiān)控應(yīng)用中，智能監(jiān)控的需求是實(shí)現(xiàn)近似實(shí)時(shí)的對(duì)關(guān)鍵事物進(jìn)行識(shí)別和行為分析，因此作為基礎(chǔ)性算法的骨架化算法需要滿足實(shí)時(shí)處理要求，這是傳統(tǒng)骨架化算法所不能實(shí)現(xiàn)的.為滿足實(shí)時(shí)性要求，本文提出一種快速的骨架提取算法.

本文算法的主要框架為：在輪廓多邊形離散曲線演化的基礎(chǔ)上，根據(jù)顯著凹凸頂點(diǎn)將輪廓多邊形進(jìn)行分塊分類；然后選擇平行線族掃描每一個(gè)輪廓塊，用割線的中點(diǎn)來近似最大內(nèi)接圓圓心作為骨架點(diǎn)；最后連接骨架點(diǎn)得到連通的骨架.雖然本文方法得到的骨架點(diǎn)位置并不是很精確的，但對(duì)形狀識(shí)別的影響較小，而且在對(duì)自然圖像的處理中具有良好的效果，尤其是在運(yùn)動(dòng)行人的骨架提取中，文中算法所提取的骨架效果良好，對(duì)于后期行人的行為分析具有一定的實(shí)用性.重要的是，與傳統(tǒng)算法相比，該算法時(shí)間復(fù)雜度低，當(dāng)研究的對(duì)象是視頻圖像時(shí)，算法可以達(dá)到實(shí)時(shí)性要求.

1　骨架提取方法

為了降低骨架提取算法的時(shí)間復(fù)雜度，本文主要采用了平行截線法來近似得到形狀中軸，即用一族平行線截取輪廓，并用截線段的中點(diǎn)來近似輪廓的內(nèi)接圓圓心，以下簡稱截線法.本文中骨架提取算法的主要實(shí)現(xiàn)思路為：首先得到二值圖像的輪廓，當(dāng)處理對(duì)象為視頻時(shí)，采用背景差分法提取出前景（二值圖像）；在對(duì)輪廓預(yù)處理之后，基于離散曲線演化，得到輪廓多邊形上對(duì)曲線形狀影響較大的凹凸頂點(diǎn)，從而實(shí)現(xiàn)原輪廓多邊形的分割與分段；其次，將對(duì)曲線形狀貢獻(xiàn)較大的凸頂點(diǎn)作為骨架圖模型中的端節(jié)點(diǎn)，利用截線法對(duì)閉合輪廓塊進(jìn)行中軸（骨架點(diǎn)）提取.最后連接骨架點(diǎn)得到連通的骨架.本文方法提取出的每個(gè)骨架分支均是物體形狀的主要分支，從而為物體識(shí)別及行為分析提供了較好的全局特征.

1.1輪廓的表示

本文采用梯度方法提取二值圖像中物體的邊緣并通過邊緣掃描得到輪廓鏈.單連通區(qū)域的輪廓只包含一個(gè)閉合的輪廓，而多連通區(qū)域的輪廓可以包含多個(gè)閉合輪廓.為了方便起見，本文將輪廓定義為多邊形無向圖的集合，并做如下符號(hào)化規(guī)定.

定義1.無向圖C：=G（V，E），其中，V= ｛s0，s1，···，sn-1｝為頂點(diǎn)集，E=｛（sj-1，sj）：j= 0，1，···，n-1，下標(biāo)對(duì)n取模｝為邊集，則稱該無向圖C為閉合輪廓.多個(gè)閉合輪廓的并稱為物體輪廓，記為C=C1∪C2∪···∪Cm，其中Ci（1≤i≤m）為閉合輪廓，物體輪廓的點(diǎn)集V（C）=∪C∈CV（C），物體輪廓的邊集E（C）=∪C∈CE（C）.

1.2輪廓的離散曲線演化

在圖像處理中，物體的輪廓線不可避免地受到邊界噪聲的影響，同時(shí)輪廓上一些細(xì)小的突起總是會(huì)產(chǎn)生小的骨架分支.通常這些小的骨架分支不能描述物體的不變特征，而且會(huì)對(duì)識(shí)別過程造成一定的干擾，導(dǎo)致識(shí)別不準(zhǔn)確.在理論和實(shí)驗(yàn)兩方面，離散曲線演化已經(jīng)被證明是一種有效刪除噪聲點(diǎn)的方法［30］.離散曲線演化是一種遞歸刪除對(duì)多邊形形狀貢獻(xiàn)最小的點(diǎn)，從而不斷簡化多邊形的方法，通過不斷演化的過程可以得到多層次的輪廓多邊形，進(jìn)而得到輪廓上顯著的凹凸頂點(diǎn)，即對(duì)輪廓形狀貢獻(xiàn)較大的點(diǎn)，基于該顯著凸頂點(diǎn)可以實(shí)現(xiàn)對(duì)原輪廓的分段.對(duì)于一條閉合輪廓C，V（C）=（s0，s1，···，sn-1），E=｛（sj-1，sj）：j= 0，1，···，n-1，下標(biāo)對(duì)n取模｝，離散曲線演化對(duì)每一個(gè)頂點(diǎn)si定義一種對(duì)形狀貢獻(xiàn)的度量：

其中，ei-1表示連接點(diǎn)si-1和點(diǎn)si的直線段，ei表示連接點(diǎn)si和點(diǎn)si+1的直線段，如圖1所示. l（ei-1）和l（ei）分別表示為線段ei-1和線段ei的長度.β（si）表示頂點(diǎn)si處線段ei-1和線段ei偏轉(zhuǎn)角的弧度值（下標(biāo)均對(duì)n取模）.頂點(diǎn)的K值越大，代表了該頂點(diǎn)對(duì)形狀的貢獻(xiàn)越大.

圖1　頂點(diǎn)si處的離散曲線演化Fig.1　Discrete curve evolution on vertex si

輪廓離散遞歸演化過程（DCE（C0））：

1）依據(jù)式（1）計(jì)算C0中所有頂點(diǎn)的K值；

2）從C0中刪除K值最小的頂點(diǎn)，重新計(jì)算并更新該點(diǎn)相鄰的兩個(gè)頂點(diǎn)的K值；

3）判斷當(dāng)前最小K 值是否大于等于閾值K?；成立則執(zhí)行4），否則轉(zhuǎn)至2）；

4）遞歸結(jié)束.

定義2.一個(gè)閉合輪廓C0，對(duì)C0進(jìn)行離散曲線演化得到新的閉合輪廓，記為DCE（C0）=C?，則稱C0為原始閉合輪廓，C?為顯著閉合輪廓，V（C?）?V（C0）.如果點(diǎn)s∈V（C0）∩V（C?），則稱s為C0中的顯著頂點(diǎn)，如果s在C?中為凸的，則稱s為C0中的顯著凸頂點(diǎn)，反之稱s為C0中的顯著凹頂點(diǎn).

定義3.給定物體輪廓C，將C中每個(gè)閉合輪廓分別執(zhí)行離散曲線演化后，得到的顯著閉合輪廓的并稱為物體顯著輪廓，記為DCE（C）=C?.

為了有效地去除骨架中的細(xì)小分支，與文獻(xiàn)［31］中的方法相同，本文選擇顯著凸頂點(diǎn)作為輪廓分段的分段點(diǎn)，將輪廓分段.只有截線段的兩個(gè)端點(diǎn)位于不同的輪廓分段時(shí)，該截線的中點(diǎn)才被保留下來.（注：當(dāng)兩個(gè)顯著凸頂點(diǎn)在原閉合輪廓中相鄰時(shí)，本文方法選擇這相鄰兩點(diǎn)的中點(diǎn)作為分段點(diǎn)，而不是將兩個(gè)點(diǎn)均作為分段點(diǎn).因?yàn)閷?shí)驗(yàn)發(fā)現(xiàn)在原閉合輪廓中相鄰的兩個(gè)顯著凸頂點(diǎn)通常使得后續(xù)算法產(chǎn)生多余的分叉.）

1.3輪廓的分割

由于水平截線法無法提取出骨架的水平分支，輪廓的水平突起會(huì)導(dǎo)致水平截線骨架點(diǎn)的截線半徑出現(xiàn)急劇增長，因此需要將輪廓C進(jìn)行分塊.

定義4.顯著閉合輪廓中的凸頂點(diǎn)，如果該點(diǎn)在顯著輪廓中的兩條鄰邊位于水平線的上下兩側(cè)，則稱為I型顯著凸頂點(diǎn).顯著閉合輪廓中的凸頂點(diǎn)，如果該點(diǎn)在顯著輪廓中的兩條鄰邊位于水平線的同一側(cè)，則稱為II型顯著凸頂點(diǎn).

I型和II型顯著凸頂點(diǎn)的結(jié)構(gòu)如圖2所示.

圖2　顯著凸頂點(diǎn)的分類Fig.2　Classification of salient convex vertices

由定義4可知，輪廓中的顯著凸頂點(diǎn)分類為兩類，I型顯著凸頂點(diǎn)和II型顯著凸頂點(diǎn).由于I型顯著凸頂點(diǎn)關(guān)聯(lián)的兩條邊在不同的輪廓分段上，因此只有垂直截線才能夠得到I型顯著凸頂點(diǎn)連接的骨架分支，該分支是趨于水平的.相反地，對(duì)于一個(gè)水平分支，其端點(diǎn)對(duì)應(yīng)的顯著凸頂點(diǎn)的兩條鄰邊必然是一條在水平線上方，一條在水平線下方.因此，I型顯著凸頂點(diǎn)對(duì)應(yīng)著水平分支.

為了將水平分支分割出來，只需將I型顯著凸頂點(diǎn)分割出來，因此需要找到I型點(diǎn)兩端的分割點(diǎn)；1）若I型顯著凸頂點(diǎn)兩端分別連接著一個(gè)顯著凹頂點(diǎn)，則這兩個(gè)凹頂點(diǎn)作為分割點(diǎn)；2）若I型顯著凸頂點(diǎn)某一端連接著一個(gè)II型顯著凸頂點(diǎn)，若這兩點(diǎn)間存在凹頂點(diǎn)，則該凹頂點(diǎn)作為分割點(diǎn)，否則選擇夾角最大的凸頂點(diǎn)作為分割點(diǎn).連接這兩個(gè)分割點(diǎn)，即可將水平分支輪廓從原輪廓中分割出來，剩下的作為主分支輪廓.分割出的每一個(gè)水平分支輪廓中的顯著凸頂點(diǎn)都是I型的，主分支輪廓中的顯著凸頂點(diǎn)都是II型的.（注：對(duì)于只有I型顯著凸頂點(diǎn)而沒有II型顯著凸頂點(diǎn)的輪廓，可以將輪廓的所有x坐標(biāo)和y坐標(biāo)交換，得到轉(zhuǎn)置后的輪廓，從而將I型顯著凸頂點(diǎn)轉(zhuǎn)化為II型顯著凸頂點(diǎn)，然后再進(jìn)行處理.）

1.4近似骨架模型

為滿足實(shí)時(shí)性要求，本文所提取的骨架點(diǎn)與傳統(tǒng)方法骨架化有一定區(qū)別，主要采用截線段的中點(diǎn)來代替最大內(nèi)切圓圓心作為骨架點(diǎn).因此需要對(duì)骨架點(diǎn)及其獲取方式進(jìn)行重新定義.本文算法將采用水平截線法得到主分支輪廓的骨架，用垂直截線法得到水平分支輪廓的骨架.水平截線法與垂直截線法是完全類似的，這里我們只討論水平截線法.

定義5.給定一個(gè)物體輪廓C，設(shè)水平直線y=i與C的交點(diǎn)為p個(gè)，記為（按x坐標(biāo)從小到大排序），計(jì)算中點(diǎn)其中0≤j≤p-1；若點(diǎn)位于輪廓內(nèi)部，并且xj和xj+1滿足：

1）位于不同的閉合輪廓上；

因?yàn)樵谟闷叫杏趦傻椎钠叫芯€族截取梯形輪廓時(shí)，得到的骨架點(diǎn)在同一條直線上，所以水平截線法只需選擇過輪廓頂點(diǎn)的水平線.例如，圖3（a）為原始輪廓的一部分，其中頂點(diǎn)A，B，C，D為輪廓多邊形中的四個(gè)頂點(diǎn)，過頂點(diǎn)C的水平截線中點(diǎn)為E，過頂點(diǎn)B的水平截線中點(diǎn)為G，則由于截線中點(diǎn)F的兩個(gè)生成點(diǎn)分別落在邊l2和l5上，頂點(diǎn)F必然會(huì)落在直線段EG上，所以過點(diǎn)F的水平截線是多余的.因此僅需計(jì)算并保留生成點(diǎn)至少有一個(gè)是輪廓頂點(diǎn)的骨架點(diǎn).

圖3　水平截線法的截線中點(diǎn)類型Fig.3　Types of middle points of horizontal secant segments

定義6.當(dāng)骨架點(diǎn)的兩個(gè)生成點(diǎn)至少有一個(gè)點(diǎn)為閉合輪廓的頂點(diǎn)時(shí)，稱這個(gè)骨架點(diǎn)為有效骨架點(diǎn).同時(shí)將顯著凸頂點(diǎn)也記為有效骨架點(diǎn)，主分支輪廓中所有有效骨架點(diǎn)的集合記為Vm.

由于下文中算法僅考慮有效骨架點(diǎn)的生成與連接，因此將有效骨架點(diǎn)簡稱為骨架點(diǎn).

定義骨架點(diǎn)對(duì)應(yīng)的兩個(gè)函數(shù)來確定Vm中骨架點(diǎn)間的鄰接關(guān)系.函數(shù)u，d：Vm■→E（C）×E（C），對(duì)于任意x∈Vm，定義u（x）=（ul，ur），其中ul為過x的截線段（以左右生成點(diǎn)為端點(diǎn)）在微小上移后左端點(diǎn)所在的邊，ur為過x的截線段在微小上移后右端點(diǎn)所在的邊.類似地，定義d（x）為二元組（dl，dr），其中dl為過x的截線段（以左右生成點(diǎn)為端點(diǎn)）在微小下移后左端點(diǎn)所在的邊，dr為過x的截線段在微小下移后右端點(diǎn)所在的邊.

定義7.定義集合εm=｛（x，y）：x，y∈Vm∧?u（x）=d（y）∨d（x）=u（y）￠｝為骨架的邊集，則無向圖（Vm，εm）稱為本文算法提取出的主分支輪廓的骨架.

如圖3（a）中，對(duì)于骨架點(diǎn)E，u（E）=（l2，l6），d（E）= （l2，l5），對(duì)骨架點(diǎn) G，u（G）= （l2，l5），d（G）=（l3，l5），由于d（E）=u（G），所以E和G之間有連邊.

根據(jù)骨架點(diǎn)的兩個(gè)生成點(diǎn)的鄰邊類型，可以將骨架點(diǎn)分為三類：骨架端點(diǎn)、骨架銜接點(diǎn)和普通骨架點(diǎn).

1）若骨架點(diǎn)是II型顯著凸頂點(diǎn)，如圖2（b）所示，稱這樣的骨架點(diǎn)為骨架端點(diǎn).并規(guī)定顯著凸頂點(diǎn)C有u（C）=（l1，l2），d（C）=?；顯著凸頂點(diǎn)D有u（D）=?，d（D）=（l1，l2）.

2）骨架點(diǎn)至少有一個(gè)生成點(diǎn)是輪廓的頂點(diǎn)S，若：

a）點(diǎn)S的兩條鄰邊都在水平線上方，或者都在水平線下方.如圖4（a）中C，E兩點(diǎn)，骨架點(diǎn)C和骨架點(diǎn)E公共的生成點(diǎn)B的兩條鄰邊均在水平線下方.則u（C）=（l2，l5），d（C）=（l2，l3）；u（E）= （l2，l5），d（E）=（l4，l5）.

b）點(diǎn)S一條鄰邊是水平的，且該水平線的兩條鄰邊都在水平線上方，或者都在水平線下方.如圖4（b）中E，F(xiàn)兩點(diǎn)，骨架點(diǎn)E的右生成點(diǎn)A有一條水平鄰邊AB，且該鄰邊AB的兩條鄰邊l2，l3均在水平線上方.則u（E）=（l1，l2），d（E）= （l1，l4）；u（F）=（l3，l4），d（F）=（l1，l4）.

圖4　銜接截線中點(diǎn)Fig.4　Connecting middle points of horizontal secant segments

由于這類骨架點(diǎn)通常連接到骨架的分叉點(diǎn)上，所以稱這類骨架點(diǎn)為骨架銜接點(diǎn).

3）既不是骨架端點(diǎn)也不是骨架銜接點(diǎn)的骨架點(diǎn)稱為普通骨架點(diǎn)，即該骨架點(diǎn)的生成點(diǎn)或者落在一條邊上，或者為輪廓的頂點(diǎn)，且這個(gè)頂點(diǎn)的一條鄰邊在水平線上方，另一條鄰邊在下方.

1.5骨架的拼接

在用水平截線法得到主分支骨架，用垂直截線法得到水平分支骨架后，通過將多個(gè)水平分支骨架拼接在主輪廓骨架上，便可以得到連通的整體骨架.

拼接方法具體描述為：在分割水平分支時(shí)將分割線的中點(diǎn)S人為地標(biāo)注為水平分支輪廓的顯著凸頂點(diǎn)，并作為該水平分支輪廓的輪廓分段點(diǎn)，即中點(diǎn)S為水平分支骨架的一個(gè)端點(diǎn).在主分支輪廓中，將中點(diǎn)S標(biāo)注為主分支輪廓多邊形的頂點(diǎn)，當(dāng)對(duì)主分支輪廓多邊形采用水平截線法時(shí)，會(huì)產(chǎn)生一個(gè)以點(diǎn)S為生成點(diǎn)的骨架點(diǎn)X.在得到主分支骨架和水平分支骨架后，X為主分支骨架中的一個(gè)骨架點(diǎn)，而S為水平分支骨架的一個(gè)端點(diǎn)，通過連接X與S便可實(shí)現(xiàn)水平分支骨架與主分支骨架的拼接.

例如，在圖5（a）中，頂點(diǎn)C為I型顯著凸頂點(diǎn)，以相鄰凹頂點(diǎn)A和D作為分割點(diǎn)，將ABCDA分割出來作為水平分支輪廓，同時(shí)將割線AD的中點(diǎn)L作為該水平分支輪廓的顯著凸頂點(diǎn)，并將L標(biāo)記為剩余輪廓的頂點(diǎn)，而作為II型顯著凸頂點(diǎn)的G點(diǎn)，則不做切分，如圖5（b）中所示.通過連接水平分支骨架端點(diǎn)L和主分支骨架點(diǎn)K，得到最終骨架，如圖5（c）所示.

圖5　水平分支骨架與主分支骨架的拼接Fig.5　Connecting of horizontal branches and main branch

2　算法的描述及復(fù)雜性分析

骨架提取算法主要分為輪廓提取、輪廓簡化、離散曲線演化、截線法提取骨架四個(gè)部分.其中截線法提取骨架又可以分輪廓分割、截線法和骨架拼接三個(gè)階段.算法1和算法2給出了該骨架提取算法的描述，其中算法2為算法1的一個(gè)子算法.

算法1.骨架提取算法

輸入.一個(gè)連通區(qū)域的二值圖像

輸出.一個(gè)連通的骨架

1）用梯度法提取邊緣并通過邊緣掃描得到輪廓像素點(diǎn)；

2）用貪心算法得到輪廓的多邊形近似；

3）設(shè)置閾值K0，將K值過小的多邊形頂點(diǎn)刪除得到原始輪廓C0；

4）對(duì)原始輪廓C0進(jìn)行離散曲線演化，得到顯著輪廓C?；

5）將顯著凸頂點(diǎn)分類為I型和II型；

6）根據(jù)顯著凸頂點(diǎn)的類型，將原始輪廓C0分割為一個(gè)主分支輪廓和多個(gè)水平分支輪廓；

7）用算法2中的方法提取主分支骨架和水平分支骨架；

8）將水平分支骨架拼接在主分支骨架上，得到最終的骨架.

算法2.水平截線法

輸入.一個(gè)主分支輪廓C

輸出.主分支骨架G（V，ε）

1）將C中的顯著凸頂點(diǎn)放到骨架頂點(diǎn)集合V中；

2）按照顯著凸頂點(diǎn)對(duì)C進(jìn)行輪廓分段；

3）將C中頂點(diǎn)的y坐標(biāo)從小到大排序，排除重復(fù)值得到序列（y1，y2，···，yN）；

4）for i=1；i＜N；i++do

5）將水平線y=yi上的C中頂點(diǎn)放到集合Ui中；

6） 將水平線y=yi與E（C）中邊的所有交點(diǎn)放到集合Ui中；

7）對(duì)Ui中的點(diǎn)按照x坐標(biāo)從小到大排序，并將相鄰兩點(diǎn)的中點(diǎn)置于截線中點(diǎn)集合Vi中；

8）從Vi中刪除非有效骨架點(diǎn)；

9）對(duì)Vi中的每一個(gè)骨架點(diǎn)v，計(jì)算函數(shù)值u（v）和d（v）；

10）骨架頂點(diǎn)集合V=V∪Vi；

11）end for

12）按照V中每個(gè)頂點(diǎn)的u值和d值確定邊集合ε.

算法步驟的復(fù)雜度分析：算法1中第1）步輪廓提取的時(shí)間復(fù)雜度為O（mn）（m，n為圖像的長和寬）.算法1中第2）步和第3）步的功能是對(duì)輪廓進(jìn)行簡化，設(shè)第1）步提取出的輪廓總頂點(diǎn)個(gè)數(shù)為N0；第2）步采用貪心算法進(jìn)行頂點(diǎn)刪除實(shí)現(xiàn)輪廓的多邊形近似，得到新的輪廓頂點(diǎn)數(shù)記為N1；第3）步設(shè)定閾值K0，將輪廓上K值小于K0的頂點(diǎn)一次性刪除后（非遞歸刪除），得到原始輪廓C0，頂點(diǎn)個(gè)數(shù)記為N，整個(gè)過程的時(shí)間復(fù)雜度為O（N0）.離散曲線演化（算法1第4）步）在原始輪廓C0基礎(chǔ)上進(jìn)行，采用優(yōu)先隊(duì)列實(shí)現(xiàn)，每一次迭代選擇并刪除隊(duì)列中K值最小的頂點(diǎn)，同時(shí)更新該點(diǎn)兩個(gè)相鄰頂點(diǎn)的K值，其時(shí)間復(fù)雜度為O（NlogN）.輪廓分割過程中需要掃描輪廓中的所有頂點(diǎn)，時(shí)間復(fù)雜度為O（N）.截線法需要對(duì)原始輪廓中所有頂點(diǎn)的y坐標(biāo)進(jìn)行排序（算法2中第3）步），時(shí)間復(fù)雜度為O（NlogN）.通常情況下水平或垂直截線與輪廓的交點(diǎn)為常數(shù)個(gè)，所以算法2中第4）～11）步的時(shí)間復(fù)雜度為O（N）.算法2第12）步計(jì)算骨架的連邊集合可以用哈希表實(shí)現(xiàn)，對(duì)于每個(gè)骨架點(diǎn)v生成兩組鍵值對(duì)：定義鍵為u（v），對(duì)應(yīng)的值為（v，up）；定義鍵為d（v），對(duì)應(yīng)的值為（v，down），其中up，down為骨架點(diǎn)鍵的類型.將鍵相同但是類型不同的骨架點(diǎn)進(jìn)行連邊，使得算法在O（M）的時(shí)間內(nèi)得到最終的骨架，其中M為骨架點(diǎn)的個(gè)數(shù).骨架拼接的時(shí)間復(fù)雜度為O（k），k為骨架分支的個(gè)數(shù).通常情況下骨架點(diǎn)個(gè)數(shù)與輪廓的頂點(diǎn)個(gè)數(shù)為同一個(gè)數(shù)量級(jí)，因此除輪廓提取外本文算法的時(shí)間復(fù)雜度為O（NlogN）（N為原始輪廓頂點(diǎn)個(gè)數(shù)），而除輪廓提取外基于距離變換法的骨架提取算法的時(shí)間復(fù)雜度仍然為O（mn）.

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

在Intel Core i5、CPU主頻1.7GHz和4GB內(nèi)存的64位Windows 7操作系統(tǒng)下，我們基于Microsoft Visual Studio 2010編程平臺(tái)利用Opencv函數(shù)庫對(duì)本文算法進(jìn)行了C++實(shí)現(xiàn).文獻(xiàn)［32］中提出的骨架提取算法是目前最好的骨架提取算法之一，該文獻(xiàn)的作者提供了算法的Matlab實(shí)現(xiàn)源碼.本節(jié)首先討論了本文算法的實(shí)現(xiàn)和參數(shù)的選??；其次在3個(gè)數(shù)據(jù)集上與文獻(xiàn)［32］中算法進(jìn)行了對(duì)比實(shí)驗(yàn)；然后，分析了本文算法在運(yùn)行時(shí)間上的優(yōu)勢；最后簡要說明本文算法對(duì)邊界噪聲的魯棒性.

3.1算法實(shí)現(xiàn)與參數(shù)選取

根據(jù)第2節(jié)中的算法描述對(duì)本文算法進(jìn)行實(shí)現(xiàn).算法的輸入為一張給定的二值圖像，如圖6（a）所示.首先調(diào)用Opencv函數(shù)庫中的輪廓提取函數(shù)得到物體的輪廓，如圖6（b）；然后用貪心算法得到物體輪廓的多邊形近似（如圖6（c））；設(shè)定閾值K0，將對(duì)多邊形形狀貢獻(xiàn)度小于K0的頂點(diǎn)從近似多邊形頂點(diǎn)集中刪除，從而得到原始輪廓C0（如圖6（d））；在原始輪廓C0基礎(chǔ)上進(jìn)行離散曲線演化，得到其顯著凹凸頂點(diǎn)，如圖6（e）所示的輪廓中，顏色深的頂點(diǎn)為顯著凸頂點(diǎn)，顏色淺的頂點(diǎn)為顯著凹頂點(diǎn)；最后在原始輪廓C0上采用截線法得到輪廓的骨架（如圖6（f）），骨架圖的骨架點(diǎn)為圖上形狀內(nèi)的頂點(diǎn).

由于輪廓預(yù)處理中K0值的大小直接影響了原始輪廓的形狀和頂點(diǎn)個(gè)數(shù)，我們首先考察了不同K0值對(duì)原始輪廓C0的影響，如圖7所示.容易看出，通過設(shè)置K0對(duì)多邊形中頂點(diǎn)進(jìn)行過濾，可以使得原始輪廓多邊形更加簡單，去除輪廓的一些細(xì)節(jié)變化，即邊界噪聲.K0值越大，原始輪廓中的頂點(diǎn)個(gè)數(shù)N值越小.因此選擇合適的K0值，不僅可以簡化輪廓的細(xì)節(jié)部分，而且還可以加快后續(xù)算法步驟.但若K0值過大，則不但會(huì)導(dǎo)致原始輪廓失去物體本來的形狀，而且還會(huì)降低所提取的骨架點(diǎn)位置的精確度.根據(jù)實(shí)驗(yàn)效果，本文中設(shè)定K0為1.5.

離散曲線演化過程即迭代刪除隊(duì)列中K值最小的頂點(diǎn)，并更新該點(diǎn)相鄰兩頂點(diǎn)的K值，演化過程停止條件為輪廓上所有頂點(diǎn)的K值均大于閾值K?，此時(shí)輪廓上頂點(diǎn)為顯著頂點(diǎn).離散曲線演化中K?值影響了顯著頂點(diǎn)的個(gè)數(shù)，最終影響骨架中的分支個(gè)數(shù).通過在多個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)效果觀察，本文中設(shè)定K?為15.

3.2算法的實(shí)驗(yàn)結(jié)果對(duì)比

為了考察本文算法在自然場景中的應(yīng)用效果，本文采集了單人行走視頻（幀頻24/s）和人體手臂伸張視頻（幀頻24/s）所提取的前景圖片作為骨架提取實(shí)驗(yàn)的數(shù)據(jù)集.針對(duì)單人行走數(shù)據(jù)集，人體手臂伸展數(shù)據(jù)集和公用數(shù)據(jù)集Kimia三個(gè)數(shù)據(jù)集上與文獻(xiàn)［32］所提算法進(jìn)行對(duì)比實(shí)驗(yàn).

圖6算法流程結(jié)果Fig.6　Procedures of the algorithm

圖7不同的K0值得到的原始輪廓和頂點(diǎn)個(gè)數(shù)NFig.7　Original contour with different vertices number N according to different K0

圖8行人骨架提取結(jié)果Fig.8　Skeletons of walking persons

1）行走數(shù)據(jù)集

行走數(shù)據(jù)集是對(duì)簡單場景中單人行走視頻采用背景差分法所提取的二值前景圖片集.本文算法與文獻(xiàn)［32］中算法的部分實(shí)驗(yàn)結(jié)果如圖8所示.

2）人體伸展數(shù)據(jù)集

人體伸展視頻數(shù)據(jù)集是對(duì)在簡單場景中的人體四肢伸展視頻采用背景差分法所提取的二值前景圖片集.本文算法和文獻(xiàn)［32］中算法的部分實(shí)驗(yàn)結(jié)果如圖9所示.

從圖8和圖9中的實(shí)驗(yàn)結(jié)果可以看出，文獻(xiàn)［32］中算法得到人體骨架的腳部有多余的分叉，而本文算法得到的輪廓多邊形上的顯著凸頂點(diǎn)基本可以代表人體的頭部和四肢，并作為骨架分支的端點(diǎn)出現(xiàn).此外，本文算法得到的骨架為由骨架點(diǎn)和骨架點(diǎn)之間的連邊構(gòu)成的圖模型，而文獻(xiàn)［32］中算法得到的骨架為一些像素點(diǎn)的集合，當(dāng)圖像復(fù)雜、骨架點(diǎn)較多時(shí)會(huì)占用較多存儲(chǔ)空間.

3）公用數(shù)據(jù)集Kimia

Sebastian等［34］給出的Kimia數(shù)據(jù)庫是評(píng)價(jià)形狀匹配性能中常用的數(shù)據(jù)集之一.該數(shù)據(jù)庫由三個(gè)數(shù)據(jù)集組成，分別是Kimia 216、Kimia 99和Silhouette.Kimia 99數(shù)據(jù)庫由9類組成，每類有11個(gè)形狀，共99個(gè)形狀.Kimia 216共有18類形狀，每類有12個(gè)形狀.Silhouette有13類形狀，共149張圖片.圖10中給出了本文算法和文獻(xiàn)［32］中算法的部分實(shí)驗(yàn)結(jié)果.

從圖10中的實(shí)驗(yàn)結(jié)果可以看出：與文獻(xiàn)［32］中結(jié)果相比，物體主分支輪廓左右極度不對(duì)稱時(shí)，如Kimia數(shù)據(jù)集中的傾斜飛機(jī)輪廓、大象輪廓等，本文算法提取的骨架點(diǎn)精確度較差；而當(dāng)物體主分支輪廓左右相對(duì)對(duì)稱時(shí)，如Kimia數(shù)據(jù)集中手掌輪廓、鳥類輪廓和人體輪廓等，則得到的骨架點(diǎn)精確度較好，并且能很好地反映原圖形的拓?fù)浣Y(jié)構(gòu).

3.3算法的運(yùn)行時(shí)間對(duì)比

1）本文算法的各階段時(shí)間分布

本文算法主要分為四個(gè)階段：輪廓提?。ㄋ惴?中第1）步）、輪廓簡化（算法2中第2）、3）步），離散曲線演化（算法2中第4）步），截線法提取骨架（算法2中第5）～8）步）.算法四個(gè)階段在尺寸為1560×2250的二值前景圖片的平均運(yùn)行時(shí)間結(jié)果如表1所示.從實(shí)驗(yàn)結(jié)果可以看出本文算法中截線法提取骨架階段耗時(shí)最長.

2）不同尺寸圖像的運(yùn)行時(shí)間對(duì)比

針對(duì)圖片尺寸為156×225的一張二值行人前景圖片，通過同時(shí)增大圖片的高度和寬度，得到增長倍數(shù)為1倍到10倍的10張圖片.采用本文算法和文獻(xiàn)［32］中算法在這10張圖片上進(jìn)行對(duì)比實(shí)驗(yàn)，由于這兩種算法所提的骨架效果隨圖片倍數(shù)增加效果變化較?。ㄈ鐖D11），因此僅進(jìn)行運(yùn)行時(shí)間的對(duì)比，對(duì)比結(jié)果如表2所示.

從表2中可以看出，文獻(xiàn)［32］中算法的運(yùn)行時(shí)間對(duì)圖片的尺寸更加敏感，在圖像的長和寬同時(shí)放大10倍后，運(yùn)行時(shí)間超過了10分鐘，是放大前運(yùn)行時(shí)間的91倍，而本文算法在放大10倍后的運(yùn)行時(shí)間是放大前的59倍，仍然可以達(dá)到實(shí)時(shí)的效果.

3）在三個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間對(duì)比

本文算法與文獻(xiàn)［32］中算法在不同數(shù)據(jù)集上的單張圖片平均運(yùn)行時(shí)間如表3所示.從實(shí)驗(yàn)結(jié)果中可以看出本文算法在運(yùn)行時(shí)間上有明顯的可滿足實(shí)時(shí)性的優(yōu)勢.

圖9伸展骨架提取結(jié)果Fig.9　Skeletons of persons with arms stretched

3.4骨架魯棒性分析

圖10 Kimia數(shù)據(jù)集骨架提取結(jié)果Fig.10　Skeletons of images from Kimia dataset

表1　圖像骨架提取的運(yùn)行時(shí)間Table 1　The running time of skeletonization

表2　不同尺寸圖片骨架提取的運(yùn)行時(shí)間對(duì)比Table 2　The comparison of running time of skeletonization of different image sizes

給定一張二值前景圖片（如圖12（a）所示），基于中軸理論所得到的的骨架如圖12（b）所示，可以看出該骨架圖存在很多冗余分支，這些分支均由輪廓邊界上的微小變化引起的，這會(huì)在很大程度上降低識(shí)別的精確性.文獻(xiàn)［32］中算法提取的骨架（圖12（c））和本文中算法提取的骨架（圖12（d））中分支較少，而且每一個(gè)分支都表示了物體輪廓的主要形狀.在輪廓邊界發(fā)生微小形變時(shí)，這兩種算法所提取的骨架并不會(huì)發(fā)生變化，因此對(duì)邊界噪聲具有一定的魯棒性.當(dāng)物體輪廓是人體輪廓時(shí)，本文算法提取的骨架更加簡潔，多數(shù)情況下骨架中的分支與人體的頭部和四肢是對(duì)應(yīng)的，這使得本文算法非常適合于基于形狀的行人識(shí)別問題以及用于步態(tài)分析.

圖11放大1，5，10倍實(shí)驗(yàn)結(jié)果Fig.11　Results of skeletonization with original image，magnified 5 times and magnified 10 times

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

與文獻(xiàn)［32］中結(jié)果相比，當(dāng)物體主分支輪廓左右極度不對(duì)稱時(shí)，如Kimia數(shù)據(jù)集中的傾斜飛機(jī)輪廓、大象輪廓等，本文算法提取的骨架點(diǎn)精確度較差；而當(dāng)物體主分支輪廓左右相對(duì)對(duì)稱時(shí)，如Kimia數(shù)據(jù)集中手掌輪廓、鳥類輪廓和人體輪廓等，則得到的骨架點(diǎn)精確度較好，并且能很好地反映原圖形的拓?fù)浣Y(jié)構(gòu).由圖8和圖9可以看出，輪廓多邊形的顯著凸頂點(diǎn)基本可以代表人體的頭部和四肢，并且是作為骨架分支的端點(diǎn)出現(xiàn)，由此說明該算法對(duì)于人體的運(yùn)動(dòng)骨架提取效果較好.表2和表3顯示了本文算法運(yùn)行時(shí)間較快，在考慮視頻前景提取過程所耗時(shí)間的情況下，本文算法平均每秒可以處理約7～8幀圖像，在采用多線程或者進(jìn)行適當(dāng)?shù)拇a優(yōu)化后完全可以滿足視頻實(shí)時(shí)處理的需求.此外，從實(shí)驗(yàn)結(jié)果的骨架圖中也可以看出，由本文算法所提取的骨架的描述方式為圖結(jié)構(gòu)，并且骨架點(diǎn)較少，這不僅節(jié)省了存儲(chǔ)空間，而且對(duì)后續(xù)的識(shí)別處理工作也是非常有利的.另外，本文算法非常適合于行人骨架的提取，所提取的骨架可以很好地應(yīng)用于步態(tài)的研究.

表3　圖像骨架提取的運(yùn)行時(shí)間對(duì)比Table 3　The comparison of running time of skeletonization

圖12不同骨架提取方法中的骨架分支Fig.12　Different skeletons according to different methods

4　結(jié)論

針對(duì)目前傳統(tǒng)骨架化算法時(shí)間復(fù)雜度較大的問題，本文提出了一種快速的骨架提取算法.在處理閉合輪廓的過程中，采用離散曲線演化對(duì)骨架進(jìn)行分段，有效地去除了微小分支；依據(jù)顯著頂點(diǎn)的類型對(duì)閉合輪廓進(jìn)行分割，并對(duì)分割出的每一部分進(jìn)行骨架提取，提高了骨架點(diǎn)的精度.為了滿足實(shí)時(shí)性要求，該方法在保持骨架拓?fù)浣Y(jié)構(gòu)不變的情況下，采用截線段中點(diǎn)來代替最大內(nèi)切圓中心作為骨架點(diǎn)，并結(jié)合骨架點(diǎn)的標(biāo)記信息迅速得到連通的骨架.實(shí)驗(yàn)表明該算法在運(yùn)動(dòng)人體上的效果良好，可以用于行人步態(tài)、行人識(shí)別等進(jìn)一步的研究.與傳統(tǒng)骨架化算法相比，該算法運(yùn)行時(shí)間較快，可以達(dá)到實(shí)時(shí)的要求.由于該骨架提取算法對(duì)左右極度不對(duì)稱的輪廓魯棒性較差，我們將在后續(xù)的研究中進(jìn)一步改進(jìn)該算法，期望找到輪廓的最優(yōu)近似對(duì)稱軸方向，并沿著該近似對(duì)稱軸方向進(jìn)行截線掃描，從而提高算法的魯棒性.

References

1 Zheng Dan-Chen，Han Min.Learning shape distance based on mean first-passage time.Acta Automatica Sinica，2014，40（1）：92-99（鄭丹晨，韓敏.基于期望首達(dá)時(shí)間的形狀距離學(xué)習(xí)算法.自動(dòng)化學(xué)報(bào)，2014，40（1）：92-99）

2 Yang Ya-Fei，Zheng Dan-Chen，Han Min.A shape matching method using spatial features of multi-scaled contours.Acta Automatica Sinica，2015，41（8）：1405-1411（楊亞飛，鄭丹晨，韓敏.一種基于多尺度輪廓點(diǎn)空間關(guān)系特征的形狀匹配方法.自動(dòng)化學(xué)報(bào)，2015，41（8）：1405-1411）

3 Zheng Dan-Chen，Yang Ya-Fei，Han Min.A shape distance learning algorithm based on generalized mean first-passage time.Acta Automatica Sinica，2016，42（2）：246-254（鄭丹晨，楊亞飛，韓敏.一種基于廣義期望首達(dá)時(shí)間的形狀距離學(xué)習(xí)算法.自動(dòng)化學(xué)報(bào)，2016，42（2）：246-254）

4 Bai X，Wang X G，Latecki L J，Liu W，Tu Z.Active skeleton for non-rigid object detection.In：Proceedings of the 12th IEEE International Conference on Computer Vision.Kyoto，Japan：IEEE，2009.575-582

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

6 Bai X，Yang X W，Yu D G，Latecki L J.Skeleton-based shape classification using path similarity.International Journal of Pattern Recognition and Artificial Intelligence，2008，22（4）：733-746

7 Bai X，Liu W，Tu Z.Integrating contour and skeleton for shape classification.In：Proceedings of the 12th IEEE International Conference on Computer Vision Workshops（ICCV Workshops）.Kyoto，Japan：IEEE，2009.360-367

8 Wang B，Shen W，Liu W Y，You X，Bai X.Shape classification using tree-unions.In：Proceedings of the 20th International Conference on Pattern Recognition（ICPR）.Istanbul，Turkey：IEEE，2010.983-986

9 Zhou Yu，Liu Jun-Tao，Bai Xiang.Research and perspective on shape matching.Acta Automatica Sinica，2012，38（6）：889-910（周瑜，劉俊濤，白翔.形狀匹配方法研究與展望.自動(dòng)化學(xué)報(bào)，2012，38（6）：889-910）

10 Chacko B P，Babu A P.Discrete curve evolution based skeleton pruning for character recognition.In：Proceedings of the 7th International Conference on Advances in Pattern Recognition（ICAPR09）.Kolkata，India：IEEE，2009.402-405

11 Rockett P I.An improved rotation-invariant thinning algorithm.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（10）：1671-1674

12 Blum H.Biological shape and visual science（Part I）.Journal of Theoretical Biology，1973，38（2）：205-287

13 Krinidis S，Chatzis V.A skeleton family generator via physics-based deformable models.IEEE Transactions on Image Processing，2009，18（1）：1-11

14 Xie W J，Thompson R P，Perucchio R.A topologypreserving parallel 3D thinning algorithm for extracting the curve skeleton.Pattern Recognition，2003，36（7）：1529-1544

15 Leymarie F，Levine M D.Simulating the grassfire transform using an active contour model.IEEE Transactions on Pattern Analysis and Machine Intelligence，1992，14（1）：56-75

16 Aurenhammer F.Voronoi diagrams—a survey of a fundamental geometric data structure.ACM Computing Surveys （CSUR），1991，23（3）：345-405

17 Brandt J W，Algazi V R.Continuous skeleton computation by Voronoi diagram.CVGIP:Image Understanding，1992，55（3）：329-338

18 Brady M，Asada H.Smoothed local symmetries and their implementation.The International Journal of Robotics Research，1984，3（3）：36-61

19 Mart′?nez-P′erez M P，Jim′enez J，Naval′on J L.A thinning algorithm based on contours.Computer Vision，Graphics，and Image Processing，1987，39（2）：186-201

20 Yu Z，Bajaj C.A segmentation-free approach for skeletonizationofgray-scaleimagesviaanisotropicvector diffusion.In：Proceedingsofthe2004IEEEComputer Society Conference on Computer Vision and Pattern Rewgnition.San Diego，USA：IEEE，2004.DOI：10.1109/CVPR.2004.1315062

21 Choi W P，Lam K M，Siu W C.Extraction of the Euclidean skeleton based on a connectivity criterion.Pattern Recognition，2003，36（3）：721-729

22 Ge Y R，F(xiàn)itzpatrick J M.On the generation of skeletons from discrete Euclidean distance maps.IEEE Transactions on Pattern Analysis and Machine Intelligence，1996，18（11）：1055-1066

23 Niblack C W，Gibbons P B，Capson D W.Generating skeletons and centerlines from the distance transform. CVGIP:Graphical Models and Image Processing，1992，54（5）：420-437

24 Arcelli C，di Baja G S.A one-pass two-operation process to detect the skeletal pixels on the 4-distance transform.IEEE Transactions on Pattern Analysis and Machine Intelligence，1989，11（4）：411-414

25 Arcelli C，di Baja G S.Euclidean skeleton via centreof-maximal-disc extraction.Image and Vision Computing，1993，11（3）：163-173

26 Dimitrov P，Damon J N，Siddiqi K.Flux invariants for shape.In：Proceedings of the 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Madison，WI，USA：IEEE，2003.I-835-I-841

27 Dimitrov P，Phillips C，Siddiqi K.Robust and efficient skeletal graphs.In：Proceedings of the 2000 IEEE Conference on Computer Vision and Pattern Recognition.Hilton Head Island，SC：IEEE，2000.417-423

28 Vasilevskiy A，Siddiqi K.Flux maximizing geometric flows. IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24（12）：1565-1578

29 Latecki L J，Lak¨amper R.Convexity rule for shape decomposition based on discrete contour evolution.Computer Vision and Image Understanding，1999，73（3）：441-454

30 Bai X，Latecki L J.Discrete skeleton evolution.Energy Minimization Methods in Computer Vision and Pattern Recognition.Berlin Heidelberg：Springer，2007.362-374

31 Bai X，Latecki L J，Liu W Y.Skeleton pruning by contour partitioning with discrete curve evolution.IEEE Transactions on Pattern Analysis and Machine Intelligence，2007，29（3）：449-462

32 Shen W，Bai X，Yang X W，Latecki L J.Skeleton pruning as trade-off between skeleton simplicity and reconstruction error.Science China Information Sciences，2013，56（4）：1-14

33 Torsello A，Hancock E R.A skeletal measure of 2D shape similarity.Computer Vision and Image Understanding，2004，95（1）：1-29

34 Sebastian T B，Klein P N，Kimia B B.Recognition of shapes by editing their shock graphs.IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26（5）：550-571

高立青大連理工大學(xué)管理與經(jīng)濟(jì)學(xué)部信息與決策技術(shù)研究所博士研究生.主要研究方向?yàn)橛?jì)算機(jī)視覺，數(shù)據(jù)挖掘.本文通信作者.E-mail:lqgao5@163.com

（GAO Li-QingPh.D.candidate at the Institute of Information and Decision Technology，F(xiàn)aulty of Management and Economics，Dalian University of Technology.Her research interest covers computer vision and data mining.Corresponding author of this paper.）

王延章大連理工大學(xué)管理與經(jīng)濟(jì)學(xué)部信息與決策技術(shù)研究所教授.主要研究方向?yàn)橹悄軟Q策，復(fù)雜系統(tǒng)建模.

E-mail:yzwang@dlut.edu.cn

（WANG Yan-ZhangProfessor at the Institute of Information and Decision Technology，F(xiàn)aulty of Management and Economics，Dalian University of Technology.His research interest covers intelligent decision information decision-making and complex system modeling.）

A Fast Algorithm of Skeleton Extraction Based on Secant Line Method

GAO Li-Qing1WANG Yan-Zhang1

A fast skeleton extraction algorithm is proposed in this paper.Firstly，some vertices of the polygon contour are labeled as salient convex vertices by using discrete curve evolution，then the polygon contour is partitioned into a main branch and several horizontal branches according to the types of these salient convex vertices.Secondly，the horizontal secant lines method is used to get the skeleton of the main branch and the vertical secant line method is used to obtain the skeletons of horizontal branches separately.Finally，by connecting the skeletons of horizontal branches to main branch skeleton，the final skeleton of a given contour is obtained.Experimental results show that the proposed skeleton extraction algorithm has good performance on Kimia data set.In addition，results on pedestrian video are presented to show that the proposed algorithm performs well on natural images，too.Furthermore，the time complexity of the algorithm is lower than those of other classical algorithms and it satisfies the requirement of real-time processing of videos.

Approximate skeleton，discrete curve evolution，salient closed contour，connected skeleton

10.16383/j.aas.2016.c150188

Gao Li-Qing，Wang Yan-Zhang.A fast algorithm of skeleton extraction based on secant line method.Acta Automatica Sinica，2016，42（7）:1100-1112

2015-04-10錄用日期2016-02-28
Manuscript received April 10，2015；accepted February 28，2016“十二五”國家科技支撐計(jì)劃重點(diǎn)項(xiàng)目（2013BAK02B06-03）資助
Supported by Key Project in the National Science&Technology Pillar Program During the Twelfth Five-year Plan Period （2013BAK02B06-03）
本文責(zé)任編委黃慶明
Recommended by Associate Editor HUANG Qing-Ming
1.大連理工大學(xué)管理與經(jīng)濟(jì)學(xué)部信息與決策技術(shù)研究所大連116024 1.Institute of Information and Decision Technology，F(xiàn)aulty of Management and Economics，Dalian University of Technology，Dalian 116024