一种二值图像形状分割算法

　　形状分割属于图像的粗分割，一般采用基于数学形态学的分割技术，适用于较为复杂的图像检索、识别和变形等的预处理，可以提高后续处理的速度和效率。本文提出一种新的形状分割算法，先检测出边界的凹角点，然后分析图像骨架分支，根据每个分支两侧近的凹角点确定分割线来进行分割。

　　1 基于二值图像形状的分割算法

　　1.1 凹角点检测

　　角点提取是图像处理中的一个重要任务，研究者提出过许多检测方法，如：利用链码跟踪到的轮廓点计算曲率来判定角点和运用方向导数来检测角点等。本文则运用SUSAN特征检测原则提取剪纸二值图像中外轮廓的凹角点。

　　SUSAN角点检测是一种直接利用图像灰度信息进行角点检测的方法，具有方法简单、定位准确、抗噪能力强的特点。其方法如下：如图1所示，用圆形模板在图像上移动，若模板内的像素与模板中心像素（核）灰度的差值小于一定阈值，则认为该点与核具有相同（或相近）的灰度，满足此条件的像素所组成的区域称为USAN （Univalue Segment Assimilating Nucleus），统计USAN区域面积，将USAN区域面积与一个几何门限比较以判断是否为角点。在二值图像中，分别用0和1代表背景像素和目标像素。对于边界点的USAN，其构成元素均为目标像素，因此可直接统计以边界点为核的USAN面积，即统计目标像素的个数：

　　设圆形模板的半径为R，分析圆形模板在边界线上移动时USAN面积的特点。由图1可知，当圆形模板在位置d时，USAN面积刚好为圆形模板面积的一半；当模板位于a时，USAN面积小于圆形模板面积的一半；当模板位于e时，USAN面积大于圆形模板面积的一半。图1中的a和e位于角点位置，其中e的位置即为要检测的凹角点的位置，而d是位于直线上的点（在局部小范围内，边界线可看作直线）。基于上述分析可知，边界凹角点的USAN面积大于圆形模板面积的一半。检测凹角点方法如下：设需要检测边界曲线上≥β（β>90°，类似图1位置e）的角点，S（R）表示圆形模板的面积（即圆形内像素的总个数）。由扇形和圆的关系可知，其面积比等于角度比，所以USAN面积符合以下条件的边界点为候选凹角点 

　

　1.3 生成所有分割线

　　生成所有分割线具体步骤：

　　（1） 按近原则分别检测骨架线所有分支两侧的凹角点，并将两侧离分支近的的凹角点相连，得到分割线集合θ1。

　　（2）分别计算集合θ1内所有分割线与骨架线的交点个数。

　　（3）根据交点个数判断，找出与骨架分支有且只有一个交点的凹角点连线，得到分割线集合θ2，θ2即是包含初步生成的所有的分割线结果。

　　（4）集合θ2中的每条分割线的首尾端点之间的图像边界的控制点即为一个分割子区域的边界控制点。

　　由以上步骤生成图像的所有分割线如图3所示，图中浅色直线即是生成的分割线。

　　1.4 优化分割线

　　优化一：清除边界的局部形变或局部噪声造成的影响。局部形变或局部噪声会对区域骨架的结构产生较大的影响，虽然采用改进的骨架对这些影响进行了一定的抑制，但有些局部形变或局部噪声还是会形成一些不合适的分割线，如图3中a处的分割线是由局部噪声影响生成的分割线。

　　优化二：去除较短长度的分支两侧凹角点形成的分割线，这类分割线分割出来的子区域比较小，对后期的工作贡献不大。如图3中b处的分割线属于分割后的子区域对形状分析贡献不大的细小区域。

　　优化方法：清除这两类的分割线可通过在骨架提取过程中修剪产生的骨架短枝，但在删除过程中，不能破坏骨架的完整和连通性。采用以下模型进行骨架短枝的删除：

　　式中，l为骨架短枝的长度（像素个数）；结构元素Ki如图4所示。

　　2 实验计算

　　为验证本文算法效率，从二值图像的形状分割算法中选取具有代表性的Limbs算法[4]与本文算法进行用时对比实验，实验在PⅢ处理器（930 MHz）、256 MB内存的微机上进行。在实验中，对30幅各种类型的二值剪纸图像进行了多组试验，结果表明，本文算法所得到的分割结果均达到了一般形状分割的要求，为图像的后续处理（如图像识别以及本文接下来的剪纸图像变形工作）提供了便利，而且处理的图像数据越大，本文算法的时间优势就越明显。表1是两种算法的时间比较。

　　用本文算法的剪纸图像分割结果如图5所示，骨架短枝的修剪长短可由用户根据分割需要以及图像边界噪声的影响程度控制。图5（a）是设置骨架短枝修剪长度为10，将牛的尾巴和蹄子上对后续分析无用的小区域分割线删掉所得优化分割线后的分割结果；图5（b）是设置骨架短枝修剪长度为15，将鸟背上的边界噪声以及爪子的小区域分割线删掉后的分割结果。

　　用Limbs算法的剪纸图像分割结果如图6所示。由于Limbs算法是按照内切圆原则来连接边界点得到分割子区域，对剪纸图像中的牛蹄和鸟的颈部都没有完整分割出来，在后续的剪纸变形处理将会带来一定的影响。因此，本文算法在剪纸图像的形状分割的应用上比Limbs算法可为后续变形处理提供更好的分割结果。

　　本文提出了一种二值图像形状分割算法，该算法将形状分割的两大类型方法结合起来，先检测出边界的凹角点，然后分析图像骨架，将每个分支两侧近的凹角点相连得出形状分割后的子区域。该算法避免了大量的计算，同时通过对修剪骨架短枝减少了边界噪声的影响，并删除了对形状分析贡献不大的子区域分割，从而降低了在进行骨架提取时对骨架提取算法好坏的依赖程度，提高了形状分割的速度和效率，更适合后续的图像分析处理。