崔雪森，伍玉梅，戴陽(yáng)，張晶

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

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

崔雪森，伍玉梅，戴陽(yáng)，張晶

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

1 引言

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

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

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

2.1 細(xì)化原理

假設(shè)圖像中，除骨架單元（或稱(chēng)角點(diǎn)）外是可壓縮的，即可在外部壓力的作用下滑向圖像內(nèi)部，將骨架化后的圖像看做是由空白單元對(duì)圖像單元擠壓，從而導(dǎo)致邊界點(diǎn)向圖像內(nèi)部逐漸坍塌的結(jié)果。在一幅二值圖像中，假設(shè)一個(gè)圖像點(diǎn)p（或稱(chēng)單元，如圖1所示），同時(shí)受到它鄰域八個(gè)方向的力作用，設(shè)其中一個(gè)為f0，則按順時(shí)針?lè)较颍搯卧芰Φ募媳硎緸镕={fi|0≤i≤7}。如果該單元某個(gè)鄰域單元為空白，則來(lái)自這個(gè)方向的力大于0，否則等于0。對(duì)于一個(gè)尚未確定為骨架單元的點(diǎn)p，分別考察其受各個(gè)方向的力，設(shè)定當(dāng)前考察的力f0(f0＞0)的方向?yàn)樗交虼怪狈较颍绻?/p>

（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)前單元滑向鄰域單元，并確定鄰域單元為骨架單元。

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

圖1 二值圖像中一個(gè)點(diǎn)單元所受外部壓力情況

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

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

圖2 骨架冗贅單元的判別

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

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

2.2 細(xì)化具體流程

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

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

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

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

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

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

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

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

圖4 骨架提取時(shí)的二值圖像演變過(guò)程圖

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

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

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

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

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

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

4 結(jié)論

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

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

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

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

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

[3]王俊平，郝躍，荊明娥.IC真實(shí)缺陷的骨架提取方法[J].西安電子科技大學(xué)學(xué)報(bào)：自然科學(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]曹鐵勇，楊吉斌，張雄偉.基于勢(shì)能平衡的圖像骨架抽取算法[J].東南大學(xué)學(xué)報(bào)：自然科學(xué)版，2003，33（6）：1-4.

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

[9]嚴(yán)濤，吳恩華.基于多幅圖象的樹(shù)木造型方法[J].系統(tǒng)仿真學(xué)報(bào)，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].地籍測(cè)量，2001，20（3）：1-18.

[13]廖志武.2-D骨架提取算法研究進(jìn)展[J].四川師范大學(xué)學(xué)報(bào)：自然科學(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)記出二值圖像的邊界，判斷各個(gè)邊界點(diǎn)的受力情況，通過(guò)三個(gè)條件判斷各個(gè)邊界點(diǎn)是否為骨架單元。迭代這一過(guò)程，直到?jīng)]有新的骨架單元產(chǎn)生，即得到初步的骨架結(jié)構(gòu)。通過(guò)對(duì)骨架中3×3區(qū)域內(nèi)骨架形狀分析，對(duì)骨架中的冗贅單元進(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)確，說(shuō)明利用該方法進(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.

國(guó)家高技術(shù)研究發(fā)展計(jì)劃（863）（No.2007AA092202）；中國(guó)科學(xué)院海洋環(huán)流與波動(dòng)重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金課題（No.KLOCAW1010）。

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

2011-11-07

2012-01-02

1002-8331（2013）13-0138-04