外部压力法（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