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

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

基于向量內積的新型骨架提取方法

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

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

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

骨架;距離變換;向量內積

1 引 言

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

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

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

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

邊界向量是指由內部像素點指向對應最近邊界點的有向向量,在圖像的中心線兩側邊界向量的分布呈現(xiàn)一定規(guī)律,方向的變化情況也可以通過數(shù)值來間接表示。

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

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

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

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

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

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

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

3 骨架提取

3.1 候選骨架點的選取

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

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

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

圖2 8-鄰域各點Fig.2 8-neighborhood of pixel

圖3 8-鄰域內積值Fig.3 8-neighborhood of inner product value

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

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

3.2 骨架延伸處理

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

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

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

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

其中:xi,yi分別對應各分支區(qū)域離散點的橫、縱坐標,離散點的數(shù)量為m。

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

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

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

3.3 算法流程

基于向量內積的新型骨架提取算法由以下幾個步驟組成:

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

(2)構造每個內部像素點的邊界向量;

(3)計算每個內部像素點的邊界向量與其8-鄰域各點的邊界向量的內積值;

(4)分別在4個方向對比內積值的符號變化情況,并以此為依據(jù),選取候選骨架點;

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

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

(7)輸出完整骨架線。

4 實驗結果與分析

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

4.1 檢驗骨架位置的準確性

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

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

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

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

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

圖4 不同延伸方法對應的結果Fig.4 Corresponding results of different extension method

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

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

運用本文算法提取圖像骨架,部分實驗結果如圖5所示。

圖5 實驗結果圖Fig.5 Experimental results

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

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

圖6 對比結果Fig.6 Comparative results

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

5 結 論

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

[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].計算機應用,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].光學精密工程,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] 王平,張力,周長其.基于種子點的粘連巨噬細胞圖像的分割方法[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].廈門大學學報(自然科學版),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] 莊彩云,熊平.基于近似最小距離場的二維圖像骨架提取方法[J].計算機工程與應用,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].中國圖象圖形學報,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] 崔雪森,伍玉梅,戴陽,等.外部壓力法(EPM)的二值圖像骨架提取[J].計算機工程與應用,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] 顏廷秦,周昌雄,劉淑芬.一種距離場約束下的普適細化算法[J].南京大學學報(自然科學版),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].東華大學學報(自然科學版),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－),女,遼寧沈陽人,碩士研究生,研究方向:模式識別與智能控制。E-mail:491627422＠qq.com

任洪娥(1962－),女,博士,教授,博士生導師,主要研究方向為模式識別與智能控制、現(xiàn)代信息技術與信息安全。

2015-09-24;

:2015-10-05.

國家自然科學基金項目(No.31370566);黑龍江省自然科學基金重點項目(No.ZD201203)

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