基于向量?jī)?nèi)積的新型骨架提取方法

胡斯淼1任洪娥12?于 鳴12姜士輝1齊 紅12

(1.東北林業(yè)大學(xué)信息與計(jì)算機(jī)工程學(xué)院,黑龍江哈爾濱150040; 2.黑龍江省林業(yè)智能裝備工程研究中心,黑龍江哈爾濱150040)

基于向量?jī)?nèi)積的新型骨架提取方法

胡斯淼1,任洪娥1,2?,于 鳴1,2,姜士輝1,齊 紅1,2

(1.東北林業(yè)大學(xué)信息與計(jì)算機(jī)工程學(xué)院,黑龍江哈爾濱150040; 2.黑龍江省林業(yè)智能裝備工程研究中心,黑龍江哈爾濱150040)

為了提高骨架提取的準(zhǔn)確性和連通性,提出了一種基于向量?jī)?nèi)積的新型骨架提取方法。對(duì)二值圖像進(jìn)行歐氏距離變換,獲得了由內(nèi)部像素點(diǎn)指向邊界點(diǎn)的邊界向量,通過(guò)比較內(nèi)部像素點(diǎn)8-鄰域范圍內(nèi)對(duì)應(yīng)邊界向量?jī)?nèi)積值符號(hào)在4個(gè)方向上的變化情況確定了邊界向量方向發(fā)生重大變化的次數(shù),并據(jù)此選取候選骨架點(diǎn);采用基于回歸分析的方法確定延伸方向,并完成連接操作生成完整的骨架線。實(shí)驗(yàn)結(jié)果表明,該算法能夠保證骨架的連通性和完整性,且骨架定位準(zhǔn)確,平均正確率達(dá)到92.27%,同時(shí)可以克服邊界擾動(dòng),是一種有效的骨架提取算法。

骨架;距離變換;向量?jī)?nèi)積

1 引 言

骨架作為一種降維的物體形態(tài)描述方式,不僅可以較為真實(shí)地表示物體的輪廓信息,還能夠反映出物體的拓?fù)浣Y(jié)構(gòu)特性,是一種表示物體形狀的重要工具,目前已經(jīng)廣泛應(yīng)用于計(jì)算機(jī)圖形學(xué)、傳感器網(wǎng)絡(luò)、圖像處理、動(dòng)作識(shí)別、人數(shù)統(tǒng)計(jì)等領(lǐng)域[1-5]。

自Blum在1967年首次以燒草模型給出骨架定義,做出開(kāi)創(chuàng)性研究以來(lái),幾十年來(lái)研究者分別從不同角度對(duì)骨架提取相關(guān)領(lǐng)域進(jìn)行了廣泛且深入的研究。Andrés Solís Montero等人[6]采用基于輪廓逼近和中軸變換的思想對(duì)骨架進(jìn)行剪枝操作,能夠克服邊界噪聲對(duì)骨架提取結(jié)果的影響,并驗(yàn)證了用中軸變換方法所提取出的骨架的重構(gòu)效果較好。Shen Wei等人[7]引入了彎曲潛能比率,通過(guò)與弦長(zhǎng)、最短輪廓段長(zhǎng)相結(jié)合的方式,共同判斷骨架分支的狀態(tài)。楊晨輝等人[8]利用基于距離變換的思想尋找局部極大值,并從中獲取關(guān)鍵點(diǎn),再根據(jù)梯度方向?qū)⑦@些關(guān)鍵點(diǎn)連接起來(lái),最終生成骨架。為進(jìn)一步提高算法效率,莊彩云等人[9]通過(guò)對(duì)像素與邊界的相對(duì)距離進(jìn)行整數(shù)編碼,構(gòu)建了近似最小距離場(chǎng)并生成聚類,再將這些聚類細(xì)化并連接后即得到完整骨架?？滴男鄣热薣10]通過(guò)定義匹配模板、統(tǒng)計(jì)鄰域信息將骨架提取技術(shù)應(yīng)用于靜脈圖像。崔雪森等人[11]是應(yīng)用EPM判定邊界點(diǎn)受力情況確定骨架單元,通過(guò)迭代得到較為平滑的骨架結(jié)構(gòu)。盡管上述方法在一定程度上改善了骨架提取的效果,但仍然存在著易受邊界噪聲影響以及在連通性和骨架位置準(zhǔn)確性之間難以平衡等問(wèn)題。

本文針對(duì)以上問(wèn)題,提出一種基于向量?jī)?nèi)積的新型骨架提取算法。算法的基本思想是通過(guò)歐氏距離變換得到內(nèi)部像素點(diǎn)和其對(duì)應(yīng)最近邊界點(diǎn)的位置,進(jìn)而可以構(gòu)造出從內(nèi)部像素點(diǎn)指向最近邊界點(diǎn)的邊界向量;并利用向量?jī)?nèi)積判斷該內(nèi)部像素點(diǎn)8-鄰域內(nèi)各個(gè)邊界向量方向的變化情況,從而確定候選骨架點(diǎn)的位置;再通過(guò)基于回歸分析的方式完成骨架延伸,最終得到連通的骨架。

2 邊界向量分布及其方向變化的判定

邊界向量是指由內(nèi)部像素點(diǎn)指向?qū)?yīng)最近邊界點(diǎn)的有向向量,在圖像的中心線兩側(cè)邊界向量的分布呈現(xiàn)一定規(guī)律,方向的變化情況也可以通過(guò)數(shù)值來(lái)間接表示。

2.1 邊界向量的分布規(guī)律

圖1是邊界向量分布示意圖。在圖中,虛線部分所代表的兩條邊界線相互平行,兩條邊界線之間的點(diǎn)均為內(nèi)部像素點(diǎn)。Q1、Q2為兩個(gè)邊界點(diǎn),線段Q1Q2與中心線相交于M點(diǎn),由圖中可以看出Q1至M之間的各個(gè)內(nèi)部像素點(diǎn)的邊界向量方向一致,均指向Q1所在邊界;Q2至M之間的各個(gè)內(nèi)部像素點(diǎn)的邊界向量方向一致,且指向Q2所在邊界。不難看出,在中心線的同一側(cè),各像素點(diǎn)的邊界向量的方向趨于相同,不同側(cè)的邊界向量的方向是相反的,所以在中心線附近的點(diǎn)所對(duì)應(yīng)的邊界向量的方向會(huì)經(jīng)歷重大的方向變化,即由指向Q1所在邊界變化為指向Q2所在邊界,如圖1中所示。由骨架定義可知,中心線附近的點(diǎn)成為骨架點(diǎn)的可能性比較高。因此,在進(jìn)行骨架提取的過(guò)程中應(yīng)該著重關(guān)注邊界向量方向發(fā)生重大改變的像素點(diǎn)。

圖1 邊界向量分布Fig.1 Boundary vector distribution

2.2 邊界向量方向變化的判定

由2.1小節(jié)中論述可知,尋找邊界向量方向發(fā)生重大變化的像素點(diǎn)對(duì)于骨架點(diǎn)的選取是至關(guān)重要的,本文采用基于向量?jī)?nèi)積的方式來(lái)判定邊界向量方向的變化情況。

在數(shù)學(xué)中,向量是具有大小和方向的幾何對(duì)象;向量?jī)?nèi)積是以兩個(gè)矢量作為輸入,并輸出一個(gè)實(shí)數(shù)值標(biāo)量的二元運(yùn)算。設(shè)二維向量a＝,二者之間夾角大小可由公式確定。其中,[a,b]＝ x1x2＋y1y2為向量a和向量b的內(nèi)積;分別是向量a和向量b的模值。為簡(jiǎn)便計(jì)算過(guò)程,對(duì)向量進(jìn)行歸一化處理,模值均變?yōu)?,此時(shí)向量之間夾角的余弦值就等于兩個(gè)向量的內(nèi)積值。根據(jù)余弦函數(shù)單調(diào)性可知:當(dāng)夾角在[0°,180°]區(qū)間內(nèi)單調(diào)遞增時(shí),內(nèi)積值在[＋1,－1]區(qū)間內(nèi)單調(diào)遞減,二者之間是一一對(duì)應(yīng)關(guān)系,所以可根據(jù)內(nèi)積值的符號(hào)變化情況判斷某像素點(diǎn)8-鄰域內(nèi)邊界向量方向是否發(fā)生了重大變化。

綜上所述,若某像素點(diǎn)8-鄰域內(nèi)邊界向量方向發(fā)生重大變化,則該像素點(diǎn)成為骨架點(diǎn)的可能性很高,而向量方向的變化情況可以依據(jù)對(duì)應(yīng)的內(nèi)積值變化情況來(lái)判定。

3 骨架提取

3.1 候選骨架點(diǎn)的選取

我們定義候選骨架點(diǎn)的基本條件是:該像素點(diǎn)的邊界向量與8-鄰域內(nèi)各點(diǎn)的邊界向量的內(nèi)積值,其符號(hào)在至少3個(gè)方向上發(fā)生變化。

假設(shè)P0是數(shù)字圖像中當(dāng)前像素點(diǎn),其8-鄰域中像素點(diǎn)為Pi(i＝1,2…8),如圖2所示。根據(jù)前文中所論述的候選骨架點(diǎn)的性質(zhì),若P0為骨架點(diǎn),則P0的8-鄰域范圍內(nèi)各像素點(diǎn)的邊界向量的方向應(yīng)該發(fā)生重大變化,即邊界向量的內(nèi)積值由正變?yōu)榉钦?或由負(fù)變?yōu)榉秦?fù))。

首先對(duì)整幅圖像做歐氏距離變換,得到各像素點(diǎn)所對(duì)應(yīng)的最近邊界點(diǎn),二者共同構(gòu)成邊界向量,即P0對(duì)應(yīng)的邊界向量為a0,Pi對(duì)應(yīng)的邊界向量為ai(i＝1,2…8);然后a0分別與ai做內(nèi)積操作,所得內(nèi)積值記錄在矩陣中,如圖3;再對(duì)比不同方向上的內(nèi)積值符號(hào)的變化情況,即水平方向(a8與a4)、垂直方向(a2與a6)、主對(duì)角線方向(a1與a5)、副對(duì)角線方向(a3與a7),向量方向發(fā)生重大變化的次數(shù)記為Flag;若在至少3個(gè)方向上內(nèi)積值的符號(hào)出現(xiàn)變化,即Flag值大于等于3,則將P0點(diǎn)視作候選骨架點(diǎn)。

圖2 8-鄰域各點(diǎn)Fig.2 8-neighborhood of pixel

圖3 8-鄰域內(nèi)積值Fig.3 8-neighborhood of inner product value

另外,由于在數(shù)字圖像中,像素點(diǎn)的坐標(biāo)是離散的,圖像的斜向邊界呈鋸齒狀,并非直線型,這就造成在圖像邊界上存在許多小的凸起,可能會(huì)出現(xiàn)候選骨架點(diǎn)的冗余現(xiàn)象。針對(duì)這一情況,在選取候選骨架點(diǎn)時(shí)添加了約束條件:候選骨架點(diǎn)必須距離邊界點(diǎn)1個(gè)像素以上。

按照上述整體判定規(guī)則,將滿足條件的像素點(diǎn)賦值為1,其余賦值為0,完成候選骨架點(diǎn)的選取。

3.2 骨架延伸處理

物體的骨架線由兩部分組成,即主骨架線和分支骨架線。通過(guò)3.1中的方法,可以獲得物體的主骨架線以及各分支骨架線,但主骨架線和各分支骨架線之間可能處于分離狀態(tài),所以為了保證骨架連通、完整,就必須對(duì)骨架做延伸處理。

為保證以最少的像素點(diǎn)完成骨架連接,骨架延伸處理遵循鄰近原則,即在一定條件下,對(duì)距離最近的兩個(gè)連通區(qū)域做連接。

假設(shè)初步操作后,所獲得圖像的主骨架線所在連通區(qū)域記為L(zhǎng)T-main,各分支骨架線所在連通區(qū)域記為L(zhǎng)T-i(i＝1,2…N),分別計(jì)算LT-i與LT-main之間的最短直線距離,記作Dis-i;再計(jì)算鄰近分支骨架區(qū)域LT-i與LT-(i＋1)之間的最短直線距離,記作Dis-near-i;若Dis-i小于等于Dis-near-i,在鄰近原則的要求下,該分支骨架線應(yīng)該延伸到主骨架線上。

在Dis-near-i小于Dis-i的情況下,將不同分支骨架中的離散點(diǎn)分別按照式(1):

其中:xi,yi分別對(duì)應(yīng)各分支區(qū)域離散點(diǎn)的橫、縱坐標(biāo),離散點(diǎn)的數(shù)量為m。

構(gòu)建回歸方程y^＝a^＋b^x,再依據(jù)斜率關(guān)系,判定分支骨架的連接方式。若兩個(gè)鄰近分支骨架所對(duì)應(yīng)的回歸方程斜率符號(hào)一致,則說(shuō)明這兩個(gè)分支骨架的延伸方向大致相同,可以將彼此連接;否則分支骨架與主骨架相連接。

在確定分支骨架線的連接對(duì)象后,沿著拓?fù)浞较蜻M(jìn)行延伸。首先,根據(jù)兩個(gè)不同區(qū)域之間的最短直線距離,能夠確定待連接部分的起點(diǎn)和終點(diǎn)坐標(biāo),將分支骨架區(qū)域所確定的點(diǎn)視為起點(diǎn),記作Start,主骨架區(qū)域(或鄰近分支骨架區(qū)域)所確定的點(diǎn)視為終點(diǎn),記作End;以End為參照物, Start相對(duì)于End的相對(duì)位置有8種情況,可以歸為3類:第一類為水平關(guān)系(正左方和正右方),第二類為垂直關(guān)系(正上方和正下方),第三類為斜向關(guān)系(其余4種情況)。按照斜向優(yōu)先原則,進(jìn)行起止點(diǎn)的連接操作,直至在Start和End之間形成一條8-連通的路徑。

基于以上骨架延伸思想所構(gòu)造出的從起點(diǎn)到終點(diǎn)的8-連通路徑,其長(zhǎng)度接近兩點(diǎn)之間的最短直線距離,從而保證了利用較少的像素點(diǎn)將二者連通,在一定程度上能夠避免冗余現(xiàn)象發(fā)生。當(dāng)完成所有分支骨架線與主骨架線之間(或是鄰近分支骨架線之間)的延伸操作后,就得到了一個(gè)完整、連通的骨架線。

3.3 算法流程

基于向量?jī)?nèi)積的新型骨架提取算法由以下幾個(gè)步驟組成:

(1)輸入一幅二值圖像,通過(guò)歐氏距離變換,得到每個(gè)像素點(diǎn)到邊界點(diǎn)的最短距離以及最近邊界點(diǎn)的位置信息;

(2)構(gòu)造每個(gè)內(nèi)部像素點(diǎn)的邊界向量;

(3)計(jì)算每個(gè)內(nèi)部像素點(diǎn)的邊界向量與其8-鄰域各點(diǎn)的邊界向量的內(nèi)積值;

(4)分別在4個(gè)方向?qū)Ρ葍?nèi)積值的符號(hào)變化情況,并以此為依據(jù),選取候選骨架點(diǎn);

(5)依據(jù)分支骨架中離散各點(diǎn),進(jìn)行回歸分析;

(6)基于回歸分析結(jié)果,做延伸處理操作;

(7)輸出完整骨架線。

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

為對(duì)本文算法進(jìn)行較為全面的驗(yàn)證,以MPEG7_CE-Shape圖形數(shù)據(jù)庫(kù)中的圖片為實(shí)驗(yàn)對(duì)象,設(shè)計(jì)了3組實(shí)驗(yàn)。實(shí)驗(yàn)1檢驗(yàn)骨架位置的準(zhǔn)確性;實(shí)驗(yàn)2驗(yàn)證基于回歸分析確定骨架延伸方法的有效性;實(shí)驗(yàn)3是本文方法與其他方法的對(duì)比結(jié)果。

4.1 檢驗(yàn)骨架位置的準(zhǔn)確性

實(shí)驗(yàn)1是檢驗(yàn)骨架位置的準(zhǔn)確性。基于距離場(chǎng)提取骨架的特點(diǎn)是定位準(zhǔn)確,通常認(rèn)為距離場(chǎng)中的極大值點(diǎn)可作為骨架點(diǎn)[12]。因此將本文方法所選取的骨架點(diǎn)與距離場(chǎng)中的極大值點(diǎn)進(jìn)行匹配,以驗(yàn)證骨架位置準(zhǔn)確性。選取30組圖片,統(tǒng)計(jì)極大值點(diǎn)數(shù)量以及與之相匹配的骨架點(diǎn)數(shù)量。表1為部分匹配情況的統(tǒng)計(jì)結(jié)果。由表1可以看出,平均匹配率達(dá)到92.27%,說(shuō)明本文基于Flag值所選取的候選骨架點(diǎn)定位準(zhǔn)確,能夠保證骨架位置的準(zhǔn)確性。

表1 匹配情況的統(tǒng)計(jì)結(jié)果Tab.1 Statistical results of matching

4.2 驗(yàn)證基于回歸分析確定骨架延伸方法的有效性

實(shí)驗(yàn)2是驗(yàn)證基于回歸分析確定骨架延伸方法的有效性。如3.2小節(jié)所述,分支骨架是否能夠正確延伸,影響到骨架最終提取結(jié)果的連通性和合理性。

實(shí)驗(yàn)中,將基于回歸分析的方法與基于距離閾值的方法進(jìn)行了比較。圖4是部分結(jié)果,其中圖4(a)是未進(jìn)行延伸操作之前的圖像;圖4(b)為基于回歸分析進(jìn)行骨架延伸處理后的圖像;圖4 (c)和(d)分別是當(dāng)距離閾值T為3和5的延伸效果。由“蝙蝠”圖像可知,頭部?jī)煞种?yīng)分別與主骨架線相連接?；诰嚯x閾值的方法延伸效果不穩(wěn)定,當(dāng)T＝3時(shí),延伸方向判斷正確;T＝5 時(shí),蝙蝠頭部分支錯(cuò)誤相連,骨架提取結(jié)果有失合理性,出現(xiàn)錯(cuò)誤的原因在于T值偏大。

圖4 不同延伸方法對(duì)應(yīng)的結(jié)果Fig.4 Corresponding results of different extension method

基于距離閾值方法旨在將距離足夠小的分支進(jìn)行連接,只有在滿足最短距離小于等于T值的情況下,才能夠連接兩分支區(qū)域,否則分別與主骨架線相連。由實(shí)驗(yàn)數(shù)據(jù)可知,蝙蝠頭部?jī)煞种еg的最短距離為4.47,在T＝5時(shí),閾值不能起到過(guò)濾作用,出現(xiàn)了連接錯(cuò)誤。所以說(shuō)基于距離閾值方法的弊端是需要依賴人工設(shè)定閾值T來(lái)判斷骨架分支的連接對(duì)象,不能自動(dòng)完成,其有效性受人為因素以及原始圖像的影響較大,不具有普遍適用性?；诨貧w分析的方法通過(guò)對(duì)兩分支區(qū)域各像素點(diǎn)的位置加以分析,確定回歸方程,由于斜率符號(hào)相異,所以兩分支區(qū)域分別與主骨架線相連。結(jié)果表明基于回歸分析的方法可以自動(dòng)完成骨架延伸方向的判定,具有有效性。

4.3 本文算法與其他算法相比較

運(yùn)用本文算法提取圖像骨架,部分實(shí)驗(yàn)結(jié)果如圖5所示。

圖5 實(shí)驗(yàn)結(jié)果圖Fig.5 Experimental results

由實(shí)驗(yàn)結(jié)果可看出,骨架位置準(zhǔn)確,連通性較好,能夠克服邊界擾動(dòng)帶來(lái)的影響。而且該算法對(duì)曲線形物體提取效果良好,在細(xì)節(jié)部分也能產(chǎn)生骨架線,保證了骨架信息的完整性。

另外,為驗(yàn)證本文算法的有效性及優(yōu)越性,分別與改進(jìn)的Zhang-Suen算法、Matlab自帶函數(shù)、文獻(xiàn)[13]中的算法進(jìn)行了對(duì)比實(shí)驗(yàn),圖6是對(duì)比實(shí)驗(yàn)結(jié)果。

圖6 對(duì)比結(jié)果Fig.6 Comparative results

圖6(a)是根據(jù)改進(jìn)的Zhang-Suen算法所提取的骨架,蝙蝠左側(cè)翅膀分支未能成功提取,原因是在按照一定條件刪除輪廓像素點(diǎn)的迭代過(guò)程中,只關(guān)注鄰域信息,沒(méi)有考慮圖像的拓?fù)浣Y(jié)構(gòu)及走勢(shì),導(dǎo)致部分骨架點(diǎn)被遺漏。圖6(b)是利用Matlab自帶的bwmorph函數(shù)進(jìn)行骨架提取的結(jié)果,由于該函數(shù)以形態(tài)學(xué)中的腐蝕和膨脹作為基本操作,對(duì)噪聲特別敏感,所以其無(wú)法有效抑制邊界噪聲帶來(lái)的不良影響。當(dāng)蝙蝠翅膀處出現(xiàn)偶然凸點(diǎn)時(shí),在對(duì)應(yīng)位置產(chǎn)生了多余的骨架分支,所以應(yīng)用局限性較大。圖6(c)是運(yùn)用文獻(xiàn)[13]中的算法所提取的骨架,該算法認(rèn)為鄰域內(nèi)極小內(nèi)積值小于0(即最大夾角為鈍角)是選取骨架點(diǎn)的唯一條件,忽略了極小內(nèi)積值等于0的像素點(diǎn),而其鄰域內(nèi)邊界向量的方向可能會(huì)出現(xiàn)變化,對(duì)應(yīng)的內(nèi)積值可能出現(xiàn)由正變0(或由0變正)的情況,此時(shí)就造成了部分候選骨架點(diǎn)丟失的問(wèn)題。圖6(d)是運(yùn)用本文算法所提取的圖像骨架,能夠得到完整的骨架,而且在分支骨架等細(xì)節(jié)部分也有很好的效果,一定程度上克服了邊界噪聲對(duì)骨架提取結(jié)果的影響。

5 結(jié) 論

本文提出的骨架提取方法借助對(duì)向量?jī)?nèi)積值符號(hào)的判斷,確定了鄰域內(nèi)邊界向量方向發(fā)生重大變化的次數(shù),通過(guò)合理設(shè)置Flag值完成了骨架點(diǎn)的初步篩選;在延伸處理階段,通過(guò)引入回歸分析,在一定程度上避免了連接環(huán)節(jié)誤判現(xiàn)象的發(fā)生,提高了骨架延伸的合理性。以MPEG7_CE-Shape圖形數(shù)據(jù)庫(kù)中的圖片作為實(shí)驗(yàn)對(duì)象,統(tǒng)計(jì)了骨架位置的平均準(zhǔn)確率達(dá)到92.27%;驗(yàn)證了基于回歸分析的延伸方法有效;同時(shí)通過(guò)對(duì)比實(shí)驗(yàn),表明本文方法在保證提取結(jié)果完整性和連通性的前提下,也能較好地克服邊界噪聲帶來(lái)的影響。

[1] Yoon S M,Kuijper A.Human action recognition based on skeleton splitting[J].Expert Systems With Applications,2013,40(17):6848-6855.

[2] Liu W P,Jiang H B,Bai X,et al.Distance transform-based skeleton extraction and its applications in sensor networks[J].IEEE Transactions On Parallel And Distributed Systems,2013,24(9):1763-1772.

[3] 夏菁菁,高琳,范勇,等.基于骨架特征的人數(shù)統(tǒng)計(jì)[J].計(jì)算機(jī)應(yīng)用,2014,34(2):585-588.Xia J J,G L,F X,et al.Peaple counting based on skeleton feature[J].Journal of Computer Applications,2014, 34(2):585-588.(in Chinese)

[4] 王衛(wèi)星,田利平,王悅.基于改進(jìn)的圖論最小生成樹(shù)及骨架距離直方圖分割細(xì)胞圖像[J].光學(xué)精密工程,2013,21 (9):2464-2472.Wang W X,Tian L P,Wang Y.Segmentation of cell images based on improved graph MST and skeleton distance mapping[J].Optics and Precision Engineering,2013,21(9):2464-2472.(in Chinese)

[5] 王平,張力,周長(zhǎng)其.基于種子點(diǎn)的粘連巨噬細(xì)胞圖像的分割方法[J].液晶與顯示,2012,27(6):808-813.Wang P,Zhang L,Zhou C Q.Segmentation method to adhesion macrophage image based on seeding point[J].Chinese Journal of Liquid Crystals and Displays,2012,27(6):808-813.(in Chinese)

[6] Montero A S,Lang J.Skeleton pruning by contour approximation and the integer medial axis transform[J].Computers&Graphics,2012,36(5):477-487.

[7] Shen W,Bai X,Hu R,et al.Skeleton growing and pruning with bending potential ratio[J].Pattern Recognition, 2011,44(2):196-209.

[8] 楊晨暉,劉聰.優(yōu)化的梯度最短路徑骨架提取算法[J].廈門大學(xué)學(xué)報(bào)(自然科學(xué)版),2014,53(2):201-205.Yang C H,Liu C.Skeleton extraction algorithm of optimized gradient path[J].Journal of Xiamen University (Natural Science),2014,53(2):201-205.(in Chinese)

[9] 莊彩云,熊平.基于近似最小距離場(chǎng)的二維圖像骨架提取方法[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(21):164-167.Zhuang C Y,Xiong P.2D image skeleton generation based on approximate minimum distance filed[J].Computer Engineering and Applications,2013,49(21):164-167.(in Chinese)

[10] 康文雄,鄧飛其.利用模板和鄰域信息的靜脈骨架提取新算法[J].中國(guó)圖象圖形學(xué)報(bào),2010,15(3):378-384.Kang W X,Deng F Q.A skeletonization method for vein patterns using template and neighbor information[J].Journal of Image and Graphics,2010,15(3):378-384.(in Chinese)

[11] 崔雪森,伍玉梅,戴陽(yáng),等.外部壓力法(EPM)的二值圖像骨架提取[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(13):138-141,227.Cui X S,Wu Y M,Dai Y,et al.Binary image skeleton extraction by External Pressure Method(EPM)[J].Computer Engineering and Applications,2013,49(13):138-141,227.(in Chinese)

[12] 顏廷秦,周昌雄,劉淑芬.一種距離場(chǎng)約束下的普適細(xì)化算法[J].南京大學(xué)學(xué)報(bào)(自然科學(xué)版),2013,49(2): 189-195.Yan T Q,Zhou C X,Liu S F.A universal thinning algorithm restricted by distance[J].Journal of Nanjing Uni-versity(Natural Science),2013,49(2):189-195.(in Chinese)

[13] 劉怡靜,唐莉萍,曾培峰.基于向量?jī)?nèi)積的骨架提取算法[J].東華大學(xué)學(xué)報(bào)(自然科學(xué)版),2010,36(2):158-164.Liu Y J,Tang L P,Zeng P F.Skeleton extraction algorithm based on vector inner-product[J].Journal of Donghua University(Natural Science),2010,36(2):158-164.(in Chinese)

A new skeleton extraction method based on vector inner production

HU Si-miao1,REN Hong-e1,2?,YU Ming1,2,JIANG Shi-hui1,QI Hong1,2

(1.Information and Computer Engineering College,Northeast Forestry University, Harbin 150040,China; 2.Forestry Intelligent Equipment Engineering Research Center,Harbin 150040,China)

A new method for skeleton extraction based on vector inner product was presented in order to improve the accuracy and connectivity.Euclidean distance transform is used to determine the nearest edge element for each pixel in a binary image.A vector from each pixel that stops at the nearest edge element is defined as edge vector.By comparing the inner product of edge vector within 8-neighborhood of the pixel,the number of significant changes in direction can be determined,and the candidate skeleton points can be selected according to it.Finally,a complete skeleton was generated by extending process based on regression analysis.Experimental results show that the algorithm can guarantee connectivity and integrity of the skeleton,and the average accuracy rate of location reached 92.27%.It also has advantages in reflecting the topological structures of objects and overcoming boundary disturbance.So,it is an effective skeleton extraction algorithm.

skeleton extraction;distance transform;vector inner product

TP391.41

:A

10.3788/YJYXS20153005.0844

1007-2780(2015)05-0844-07

胡斯淼(1990－),女,遼寧沈陽(yáng)人,碩士研究生,研究方向:模式識(shí)別與智能控制。E-mail:491627422＠qq.com

任洪娥(1962－),女,博士,教授,博士生導(dǎo)師,主要研究方向?yàn)槟Ｊ阶R(shí)別與智能控制、現(xiàn)代信息技術(shù)與信息安全。

2015-09-24;

:2015-10-05.

國(guó)家自然科學(xué)基金項(xiàng)目(No.31370566);黑龍江省自然科學(xué)基金重點(diǎn)項(xiàng)目(No.ZD201203)

?通信聯(lián)系人,E-mail:nefu-rhe＠163.com