一种基于二值图像的形状分割算法研究*
2010-05-11王琴竹
王琴竹，唐 莹
(1.运城学院 公共计算机教学部，山西 运城 044000；2.中国建行广西分行信息技术部，广西 南宁 530022)
形状分割属于图像的粗分割，一般采用基于数学形态学的分割技术，适用于较为复杂的图像检索、识别和变形等的预处理，可以提高后续处理的速度和效率。本文提出一种新的形状分割算法，先检测出边界的凹角点，然后分析图像骨架分支，根据每个分支两侧最近的凹角点确定分割线来进行分割。
1 基于二值图像形状的分割算法
1.1 凹角点检测
角点提取[1]是图像处理中的一个重要任务，研究者提出过许多检测方法，如：利用链码跟踪到的轮廓点计算曲率来判定角点和运用方向导数来检测角点[2]等。本文则运用SUSAN特征检测原则[3]提取剪纸二值图像中外轮廓的凹角点。
SUSAN角点检测是一种直接利用图像灰度信息进行角点检测的方法，具有方法简单、定位准确、抗噪能力强的特点。其方法如下：如图1所示，用圆形模板在图像上移动，若模板内的像素与模板中心像素(核)灰度的差值小于一定阈值，则认为该点与核具有相同(或相近)的灰度，满足此条件的像素所组成的区域称为USAN(Univalue Segment Assimilating Nucleus)，统计 USAN区域面积，最后将USAN区域面积与一个几何门限比较以判断是否为角点。在二值图像中，分别用0和1代表背景像素和目标像素。对于边界点的USAN，其构成元素均为目标像素，因此可直接统计以边界点为核的USAN面积，即统计目标像素的个数：
式中，c(r0)是以r0为圆心的模板，c(r，r0)为模板中的目标像素。
图1 SUSAN原则中模板的位置
设圆形模板的半径为R，分析圆形模板在边界线上移动时USAN面积的特点。由图1可知，当圆形模板在位置d时，USAN面积刚好为圆形模板面积的一半；当模板位于a时，USAN面积小于圆形模板面积的一半；当模板位于e时，USAN面积大于圆形模板面积的一半。图1中的a和e位于角点位置，其中e的位置即为要检测的凹角点的位置，而d是位于直线上的点(在局部小范围内，边界线可看作直线)。基于上述分析可知，边界凹角点的USAN面积大于圆形模板面积的一半。检测凹角点方法如下：设需要检测边界曲线上≥β(β>90°，类似图 1位置 e)的角点，S(R)表示圆形模板的面积(即圆形内像素的总个数)。由扇形和圆的关系可知，其面积比等于角度比，所以USAN面积符合以下条件的边界点为候选凹角点：
实际中常按α＋β=360对α和β进行取值。通常，由于角点一定发生在USAN面积极值处，角点附近会产生若干个候选角点。因此对
1.2 骨架提取
(1)基本形态变换定义：设有模板 C，F={F1，F2}，F=F1∪F2且 F1∩F2=Φ为给定的结构元素，X是待变换图像，由此可以对基本形态变换定义如下：
定义1结构元素C对图像X的膨胀为：
定义2结构元素C对图像X的腐蚀为：
定义3结构元素F对图像X的击中变换为：
定义4结构元素F对图像X的形态薄化变换为：XdF=X/(X⊗F)=XI(X⊗F)d
形态薄化变换就是从图像X中删除被F击中的部分，它使图像线划减细，是图像形态细化算法的基础。
(2)改进的序贯同伦形态细化过程就是采用多个分别承担不同方向像素剥离的拓扑同伦结构元素，按细化应遵循的原则，对图像进行反复的迭代薄化运算，直到迭代收敛为止。其模型为：
式中，SK(X)为图像 X的骨架；k是图像细化过程收敛时的总循环次数，取决于图像目标的大小及粗细；结构元素 Di、Ei、Li分别承担不同方向像素的剥离，当 i=4时，Di+1=D5=D1，可以证明这种算法模型也是收敛的。其最大优点是对于大规模的图像矩阵来说，任一个像素的剥落与否可以同时采用4个结构元素进行击中运算。在每次循环中，迭代次数为4，则总迭代次数为4k，收敛速度大为加快。结构元素D、E、L如图2所示。
图2 结构元素 D、E、L
图中，正中间格“1”表示结构元素的原点；“*”表示取“0”或“1”。式(3)模型的程序实现步骤如下：
①X：⇒X1，0：⇒k；
②X1：⇒X2；
③(X2⊗D1)U(X2⊗D2)U(X2⊗E1)U(X2⊗L1)：⇒Y；X2/Y：⇒X2；
④(X2⊗D2)U(X2⊗D3)U(X2⊗E3)U(X2⊗L2)：⇒Y；X2/Y：⇒X2；
⑤(X2⊗D3)U(X2⊗D4)U(X2⊗E3)U(X2⊗L3)：⇒Y；X2/Y：⇒X2；
⑥(X2⊗D4)U(X2⊗D1)U(X2⊗E4)U(X2⊗L4)：⇒Y；X2/Y：⇒X2；
⑦若 X2≠X1；则k+1：⇒k；X2：⇒X1转②；
⑧X2：⇒SK(X)，输出 SK(X)，结束。其中，：⇒为值赋予或图像赋予。
1.3 生成所有分割线
生成所有分割线具体步骤：
(1)按最近原则分别检测骨架线所有分支两侧的凹角点，并将两侧离分支最近的的凹角点相连，得到分割线集合 θ1。
(2)分别计算集合θ1内所有分割线与骨架线的交点个数。
(3)根据交点个数判断，找出与骨架分支有且只有一个交点的凹角点连线，得到分割线集合 θ2，θ2即是包含初步生成的所有的分割线结果。
(4)集合θ2中的每条分割线的首尾端点之间的图像边界的控制点即为一个分割子区域的边界控制点。
由以上步骤生成图像的所有分割线如图3所示，图中浅色直线即是生成的分割线。
图3 生成所有分割线结果
1.4 优化分割线
优化一：清除边界的局部形变或局部噪声造成的影响。局部形变或局部噪声会对区域骨架的结构产生较大的影响，虽然采用改进的骨架对这些影响进行了一定的抑制，但有些局部形变或局部噪声还是会形成一些不合适的分割线，如图3中a处的分割线是由局部噪声影响生成的分割线。
优化二：去除较短长度的分支两侧凹角点形成的分割线，这类分割线分割出来的子区域比较小，对后期的工作贡献不大。如图3中b处的分割线属于分割后的子区域对形状分析贡献不大的细小区域。
优化方法：清除这两类的分割线可通过在骨架提取过程中修剪产生的骨架短枝，但在删除过程中，不能破坏骨架的完整和连通性。采用以下模型进行骨架短枝的删除：
式中，l为骨架短枝的长度(像素个数)；结构元素Ki如图4所示。
图4 结构元素K
2 实验计算
为验证本文算法效率，从二值图像的形状分割算法中选取具有代表性的Limbs算法[4]与本文算法进行用时对比实验，实验在 PⅢ处理器(930 MHz)、256 MB内存的微机上进行。在实验中，对30幅各种类型的二值剪纸图像进行了多组试验，结果表明，本文算法所得到的分割结果均达到了一般形状分割的要求，为图像的后续处理(如图像识别以及本文接下来的剪纸图像变形工作)提供了便利，而且处理的图像数据越大，本文算法的时间优势就越明显。表1是两种算法的时间比较。
表1 两种形状分割算法的性能比较
用本文算法的剪纸图像分割结果如图5所示，骨架短枝的修剪长短可由用户根据分割需要以及图像边界噪声的影响程度控制。图5(a)是设置骨架短枝修剪长度为10，将牛的尾巴和蹄子上对后续分析无用的小区域分割线删掉所得优化分割线后的分割结果；图5(b)是设置骨架短枝修剪长度为15，将鸟背上的边界噪声以及爪子的小区域分割线删掉后的分割结果。
用Limbs算法的剪纸图像分割结果如图6所示。由于Limbs算法是按照最小内切圆原则来连接边界点得到分割子区域，对剪纸图像中的牛蹄和鸟的颈部都没有完整分割出来，在后续的剪纸变形处理将会带来一定的影响。因此，本文算法在剪纸图像的形状分割的应用上比Limbs算法可为后续变形处理提供更好的分割结果。
图5 本文算法优化后的分割线
图6 Limbs算法分割结果
本文提出了一种二值图像形状分割算法，该算法将形状分割的两大类型方法结合起来，先检测出边界的凹角点，然后分析图像骨架，将每个分支两侧最近的凹角点相连得出形状分割后的子区域。该算法避免了大量的计算，同时通过对修剪骨架短枝减少了边界噪声的影响，并删除了对形状分析贡献不大的子区域分割，从而降低了在进行骨架提取时对骨架提取算法好坏的依赖程度，提高了形状分割的速度和效率，更适合后续的图像分析处理。
[1]张坤华，王敬儒，张启衡.多特征复合的角点提取方法[J].中国图像图形学报，2002，7(4)：319-324.
[2]FREEMAN H，DAVIS L S.A corner finding algorithm for chain code curves[J].IEEE Transactions.on Computers，1997， 26： 297-303.
[3]SMITH S M，BRADY J M.SUSAN-a new approach to low levelimageprocessing[R].InternalTechnicalReportTR95SMS1，Defence Research Agency， Chobham Lane， Chertsey， Surry，UK，1995.
[4]KALEEM S， KIMIA B B.Parts of visual form： computational aspects [J].IEEE Transactions on Pattern Analys and Machine Intelligence， 1995，17(3)： 239-251.
