外部壓力法（EPM）的二值圖像骨架提取

崔雪森，伍玉梅，戴陽，張晶

中國水產(chǎn)科學(xué)研究院 東海水產(chǎn)研究所漁業(yè)資源遙感信息技術(shù)重點開放實驗室，上海 200090

外部壓力法（EPM）的二值圖像骨架提取

崔雪森，伍玉梅，戴陽，張晶

中國水產(chǎn)科學(xué)研究院 東海水產(chǎn)研究所漁業(yè)資源遙感信息技術(shù)重點開放實驗室，上海 200090

1 引言

骨架提取在圖像形態(tài)分析等領(lǐng)域中具有廣泛的應(yīng)用，其算法被大量應(yīng)用于圖像與文字識別、生物形態(tài)檢測等領(lǐng)域[1-3]。常見的骨架提取方法已經(jīng)有眾多報道。其中，Blum[4]最早提出了中軸算法，即對于區(qū)域內(nèi)的每一個點，在邊界中搜索到的最近的點多于一個時，則該點為圖像的骨架單元。但該方法計算耗時長，且抗噪能力差，不能保障骨架線的連通。Zhang-Suen[5]提出了以四個判別條件來判斷當(dāng)前點為可刪除點的方法，可確保圖像的連通性，更容易通過編程實現(xiàn)，是當(dāng)前最為常用的方法。在此基礎(chǔ)上，Holt等[6]提出改善Zhang-Suen的演算法[5]，提高了其運算速度，但該方法會產(chǎn)生有頸部化和細(xì)小分枝問題。近年，曹鐵勇[7]提出了一種基于勢能平衡方式的二值圖像骨架抽取算法。該方法將邊界點作為零勢能的等勢點，計算出處于勢能平衡點上的基本骨架點，由此構(gòu)建出骨架，方法抗噪能力較強，但參與計算的邊界點的半徑較難確定。倪健等[8]通過建立Delaunay三角網(wǎng)，并對三角形進(jìn)行切割得到運動人體的骨架線。該方法思路簡單，但所注意細(xì)節(jié)較多，增加了編程的復(fù)雜性。

本文采用基于力學(xué)的骨架提取方法，考察圖像邊界點上受力情況，判斷是否為圖像的骨架單元，最后對提取結(jié)果中的冗贅單元進(jìn)行刪除。

2 外部壓力法（EPM）細(xì)化原理與算法

2.1 細(xì)化原理

假設(shè)圖像中，除骨架單元（或稱角點）外是可壓縮的，即可在外部壓力的作用下滑向圖像內(nèi)部，將骨架化后的圖像看做是由空白單元對圖像單元擠壓，從而導(dǎo)致邊界點向圖像內(nèi)部逐漸坍塌的結(jié)果。在一幅二值圖像中，假設(shè)一個圖像點p（或稱單元，如圖1所示），同時受到它鄰域八個方向的力作用，設(shè)其中一個為f0，則按順時針方向，該單元所受力的集合表示為F={fi|0≤i≤7}。如果該單元某個鄰域單元為空白，則來自這個方向的力大于0，否則等于0。對于一個尚未確定為骨架單元的點p，分別考察其受各個方向的力，設(shè)定當(dāng)前考察的力f0(f0＞0)的方向為水平或垂直方向，如果：

（1）|f4|＞0，確定當(dāng)前單元為骨架單元；

（2）存在|fi|=0且|fi+1|＞0(i=1，2)，或|fi|＞0且|fi+1|=0 (i=5，6)，確定當(dāng)前單元為骨架單元；

（3）當(dāng)前單元的水平和垂直的鄰域單元中，存在與f0方向相反的力，則當(dāng)前單元滑向鄰域單元，并確定鄰域單元為骨架單元。

將以上三個條件依順序?qū)D像中邊界上的點進(jìn)行判斷。如果滿足條件（1），意味著在一個單元中存在一對方向相反的力，不能再進(jìn)一步擠壓。對于滿足條件（2）的單元，如果將其刪除，則有可能造成細(xì)的斷裂。為了確保骨架的連通，將其暫時保留為骨架單元。當(dāng)滿足條件（3）時，究竟兩個單元如何互相滑動，實際上具有二義性。如果兩個都保留為骨架單元，則圖像不符合骨架的定義[9]，這里選用第一個單元向每二個單元滑動的情況。

圖1 二值圖像中一個點單元所受外部壓力情況

如果以上三個條件均不符合，則當(dāng)前單元滑向圖像內(nèi)部。

確定骨架單元需經(jīng)過上述三個條件的檢驗。對于條件（2），并不能完全確定當(dāng)前點為骨架單元。如圖2所示，（a）和（b）中心點均符合條件（2）的標(biāo)準(zhǔn)（陰影部分表示有任意一個或任意兩個值為1的圖像單元組合），但圖（a）為可刪除的點，而圖（b）卻不能或不適合刪除，否則將破壞最終骨架的連通性或走向。但為了處理簡單，在用本文方法進(jìn)行骨架初步提取時，把這兩種情況的中心點都作為骨架單元予以了保留，從而導(dǎo)致類似于圖2（a）的拐角處會出現(xiàn)骨架單元冗贅的問題。如果以90°、180°、270°角旋轉(zhuǎn)圖2（a），可以得到四種同類情形。

圖2 骨架冗贅單元的判別

當(dāng)這種冗贅單獨出現(xiàn)時并不違反骨架的定義，但當(dāng)連續(xù)出現(xiàn)時，就會使骨架線的寬度大于1，這時要對冗贅單元進(jìn)行清除。

針對這一問題，在用以上三個條件對圖像進(jìn)行骨架單元判別并提取完成后，需要對四種出現(xiàn)問題的情況進(jìn)行查找匹配，然后對中心點的分枝數(shù)進(jìn)行判斷。如果分枝數(shù)大于2，則對其進(jìn)行刪除，否則保留，以此解決骨架單元的冗贅問題。

2.2 細(xì)化具體流程

外部壓力法（EPM）提取骨架的流程，如圖3所示。首先，在二值圖像中搜索得到邊界點集合S，以數(shù)學(xué)形態(tài)學(xué)表示，其邊界點集合為：

其中，Θ為腐蝕運算符，c表示求余集，B為十字形結(jié)構(gòu)元素。

圖3 外部壓力法（EPM）骨架提取流程圖

以圖4（a）中的圖像為例，首先遍歷圖像中每一個邊界點，用上述三個條件判斷是否為骨架單元。第一次遍歷時邊界上各單元受力以及骨架單元確定情況，如表1所示（此表中未列出不符合上述三個條件的邊界點）。

重復(fù)迭代以上過程，直至沒有新的骨架單元出現(xiàn)，再對提取出的骨架中拐角冗贅點進(jìn)行清除，最終得到圖4（d）所示圖像。

2.3 與商業(yè)軟件提取效果比較

以飛機圖形的二值圖像作為例子，應(yīng)用外部壓力法（EPM）對圖5（a）中的圖像進(jìn)行了骨架提取，其結(jié)果如圖5（b）所示。

表1 第一次細(xì)化時各邊界點上的受力方向與骨架單元的確定

圖4 骨架提取時的二值圖像演變過程圖

圖5 骨架提取結(jié)果的比較

圖6 2010年10月8日—15日西北太平洋海表溫度高梯度強度位置（陰影區(qū)域）與等值線疊加圖

圖7 外部壓力法的海表溫度鋒面提取效果

為對本文方法提取效果進(jìn)行比較和結(jié)果的檢驗，在MatLab 6.5環(huán)境下用系統(tǒng)提供的Bwmorph函數(shù)對相同原始圖像的骨架進(jìn)行提取，其結(jié)果如圖5（c）所示。對比這兩種方法的提取結(jié)果，可以看到兩者提取的骨架整體結(jié)構(gòu)基本相同，但用本文方法的結(jié)果很少產(chǎn)生枝丫和毛刺，線條也更加平滑。

3 海洋表層水溫鋒面提取上的應(yīng)用

為了驗證本文方法提取骨架在實際應(yīng)用中的效果，進(jìn)行了海表水溫鋒面的提取。首先由NASA網(wǎng)站（http：// oceancolor.gsfc.nasa.gov/）下載MODIS衛(wèi)星的海表溫度周平均數(shù)據(jù)，時間為2010年10月8日—15日，空間分辨率9 km，跨度為東經(jīng)140°～170°，北緯30°～45°。根據(jù)文獻(xiàn)[10]提供的方法計算出溫度梯度強度，并根據(jù)文獻(xiàn)[11]中迭代閾值選取方法計算得到的梯度閾值為0.024℃/km，依據(jù)此閾值提取出高溫度梯度強度的部分，與水溫等值線疊加，如圖6所示。再利用外部壓力法，提取出溫度鋒面，如圖7。從提取效果看，骨架與等值線分布一致，且均位于高梯度強度條帶的中央，很少有毛刺出現(xiàn)，清晰地反映了黑潮、親潮等較強潮流相互作用所形成的復(fù)雜的鋒面結(jié)構(gòu)，以及渦旋的位置。

4 結(jié)論

本文研究了外部壓力法（EPM）的骨架提取算法，其物理意義明確，是經(jīng)典骨架提取方法的一個補充。與經(jīng)典的Zhang-Suen[5]方法相比，本方法只考慮當(dāng)前點周邊3×3的區(qū)域，判別條件更簡明。而Zhang-Suen[5]法除考慮當(dāng)前點3×3區(qū)域外，還要考慮其周邊點的連通情況，且要處理兩個子迭代（sub-iteration）項，增加了編程處理的復(fù)雜性。

骨架提取現(xiàn)在多采用經(jīng)典形態(tài)學(xué)的方法，各自有其優(yōu)點與不足[12-13]。外部壓力法（EPM）對圖像的細(xì)節(jié)變化較不敏感，因此更適合對圖形整體骨架結(jié)構(gòu)的描繪。

由于本文方法只考慮了力的方向，在應(yīng)用中可根據(jù)實際情況，同時考慮圖像邊界單元所受力的大小，以此影響骨架的走向和偏移程度，這將是下一步研究的方向。

[1]俞凱，吳江琴，莊越挺.基于骨架相似性的書法字檢索[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報，2009，21（6）：746-751.

[2]朱維松，姚礪，萬燕，等.骨架提取算法的研究及在異形纖維中的應(yīng)用[J].東華大學(xué)學(xué)報：自然科學(xué)版，2008，34（5）：605-607.

[3]王俊平，郝躍，荊明娥.IC真實缺陷的骨架提取方法[J].西安電子科技大學(xué)學(xué)報：自然科學(xué)版，2005，32（2）：207-209.

[4]Blum H.A transformation for extracting new descriptors of shape of models for the perception of speech and visual form[M].Cambridge：MIT Press，1967：362-380.

[5]Zhang T Y，Suen C Y.A fast parallel algorithm for thinning digitalpatterns[J].CommunicationsoftheACM，1984，27（3）：236-239.

[6]Holt C M，Stewart A，Clint M，et al.An improved parallel thinning algorithm[J].Communications of the ACM，1987，30（2）：156-160.

[7]曹鐵勇，楊吉斌，張雄偉.基于勢能平衡的圖像骨架抽取算法[J].東南大學(xué)學(xué)報：自然科學(xué)版，2003，33（6）：1-4.

[8]倪健，董強.基于Delaunay三角網(wǎng)的骨架提取算法研究[J].艦船科學(xué)技術(shù)，2006，28（4）：106-108.

[9]嚴(yán)濤，吳恩華.基于多幅圖象的樹木造型方法[J].系統(tǒng)仿真學(xué)報，2000，12（5）：565-571.

[10]Pi Qingling，Hu Jianyu.Analysis of sea surface temperature fronts in the Taiwan Strait and its adjacent area using an advancededgedetectionmethod[J].ScienceChinaEarth Science，2010，53（7）：1008-1016.

[11]郎銳.數(shù)字圖像處理學(xué)[M].北京：北京希望電子出版社，2003：279-285.

[12]廖振偉，史天元，張昆宗.細(xì)化演算法比較[J].地籍測量，2001，20（3）：1-18.

[13]廖志武.2-D骨架提取算法研究進(jìn)展[J].四川師范大學(xué)學(xué)報：自然科學(xué)版，2009，32（5）：676-688.

CUI Xuesen,WU Yumei,DAI Yang,ZHANG Jing

Key&Open Laboratory of Remote Sensing&Information Technology Application in Fisheries,East China Sea Fisheries Research Institute,Chinese Academy of Fishery Sciences,Shanghai 200090,China

A skeleton extraction method is presented based on external pressures around the border points of a binary image. Firstly,the boundaries of binary images are marked to determine forces on border points.By analysis of three conditions of pressure,that whether the point is the skeleton unit or not is determined.The iteration process is carried out until no new skeleton unit appears,then the preliminary skeleton is achieved.Redundant points are searched and erased based on the shape feature analysis by 3×3 area in the skeleton.Then the ultimate skeleton structure map is obtained.The skeleton structure diagram created by EPM is compared with that by the skeleton extraction function（Bwmorph）in commercial software Matlab 6.5.It shows that skeleton lines by EPM are smoother and there are less tiny branches than those in Matlab 6.5.Finally,the method is applied in the sea surface temperature fronts extraction.The results show the position and structure of extracted fronts is accurate and the EPM is feasible in skeleton extraction.

External Pressure Method（EPM）;binary image;skeleton extraction

提出了基于邊界外部壓力的二值圖像結(jié)構(gòu)化骨架提取方法。先標(biāo)記出二值圖像的邊界，判斷各個邊界點的受力情況，通過三個條件判斷各個邊界點是否為骨架單元。迭代這一過程，直到?jīng)]有新的骨架單元產(chǎn)生，即得到初步的骨架結(jié)構(gòu)。通過對骨架中3×3區(qū)域內(nèi)骨架形狀分析，對骨架中的冗贅單元進(jìn)行查找并刪除。將該方法得到的骨架結(jié)構(gòu)圖與軟件Matlab 6.5骨架提取函數(shù)（Bwmorph）得到的骨架結(jié)構(gòu)進(jìn)行了比較，表明用該方法得到的結(jié)果比Matlab 6.5中得到的骨架線條更平滑，而且細(xì)小分枝更少。將該方法應(yīng)用到海表溫度鋒面的提取上，結(jié)果顯示鋒面位置與結(jié)構(gòu)準(zhǔn)確，說明利用該方法進(jìn)行骨架提取是可行的。

外部壓力法；二值圖像；骨架提取

A

TP391.41

10.3778/j.issn.1002-8331.1110-0668

CUI Xuesen,WU Yumei,DAI Yang,et al.Binary image skeleton extraction by External Pressure Method（EPM）.Computer Engineering and Applications,2013,49（13）：138-141.

國家高技術(shù)研究發(fā)展計劃（863）（No.2007AA092202）；中國科學(xué)院海洋環(huán)流與波動重點實驗室開放基金課題（No.KLOCAW1010）。

崔雪森（1973—），男，副研究員，主要研究領(lǐng)域為海洋漁場環(huán)境可視化；伍玉梅（1974—），女，博士，副研究員；戴陽（1969—）。男，博士，副研究員；張晶（1981—），女，助理研究員。E-mail：cuixuesen@eastfishery.ac.cn

2011-11-07

2012-01-02

1002-8331（2013）13-0138-04