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

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

中國水產科學研究院 東海水產研究所漁業資源遙感信息技術重點開放實驗室，上海 200090

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

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

中國水產科學研究院 東海水產研究所漁業資源遙感信息技術重點開放實驗室，上海 200090

1 引言

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

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

2 外部壓力法（EPM）細化原理與算法

2.1 細化原理

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

（1）|f4|＞0，確定當前單元為骨架單元；

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

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

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

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

如果以上三個條件均不符合，則當前單元滑向圖像內部。

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

圖2 骨架冗贅單元的判別

當這種冗贅單獨出現時并不違反骨架的定義，但當連續出現時，就會使骨架線的寬度大于1，這時要對冗贅單元進行清除。

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

2.2 細化具體流程

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

其中，Θ為腐蝕運算符，c表示求余集，B為十字形結構元素。

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

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

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

2.3 與商業軟件提取效果比較

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

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

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

圖5 骨架提取結果的比較

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

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

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

3 海洋表層水溫鋒面提取上的應用

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

4 結論

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

骨架提取現在多采用經典形態學的方法，各自有其優點與不足[12-13]。外部壓力法（EPM）對圖像的細節變化較不敏感，因此更適合對圖形整體骨架結構的描繪。

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

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

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

[3]王俊平，郝躍，荊明娥.IC真實缺陷的骨架提取方法[J].西安電子科技大學學報：自然科學版，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].東南大學學報：自然科學版，2003，33（6）：1-4.

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

[9]嚴濤，吳恩華.基于多幅圖象的樹木造型方法[J].系統仿真學報，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]郎銳.數字圖像處理學[M].北京：北京希望電子出版社，2003：279-285.

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

[13]廖志武.2-D骨架提取算法研究進展[J].四川師范大學學報：自然科學版，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

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

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

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.

國家高技術研究發展計劃（863）（No.2007AA092202）；中國科學院海洋環流與波動重點實驗室開放基金課題（No.KLOCAW1010）。

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

2011-11-07

2012-01-02

1002-8331（2013）13-0138-04