图像分割是模式识别和计算机视觉领域的重要基础环节，也是当前的研究热点之一。典型的图像分割方法有阈值法[1]、边缘检测方法、多分辨率方法[2]、分裂合并方法等。
    分裂合并的分割方法[3]充分利用图像的整体和局部特征进行分割，算法思路清晰，在图像处理领域备受青睐。该算法主要包括分裂和合并两个阶段。传统算法中，在分裂阶段，将不同质的区域递归分裂为四个一样大小的子区域，直到每个区域都符合一致性。在合并阶段，根据一致性规则将相似的区域合并起来。但这种算法思路直接，容易造成方块效应和过分割。近年来许多文献尝试对该算法进行改进，主要体现在分裂阶段。参考文献[4]用Delaunay三角剖分将图像分割成一些不规则的三角形；参考文献[5]除了在水平和竖直方向上将图像进行分割外，还可以在45°和275°方向上将图像一分为二；参考文献[6]为了解决分割位置固定的缺点，选择了“最优”(“最优”的定义是可以根据需要选取)位置实现水平或者竖直方向的一分为二分割。以上的分裂合并算法都没有考虑到图像的实际边界形状，而是人为地将图像分为一些固定的形状，通过对形状的不断细分来逼近图像的边界。特别在图像的边缘位置，如果分裂不够细的话，容易产生方块效应，进而破坏图像的边界形状。如果分裂较细，则会因为分块过多而容易产生过分割现象。
    边缘检测的方法是基于图像在区域边缘上的像素灰度变化比较剧烈，通过检测不同区域的边缘来解决图像分割问题。边缘检测的分割方法可以获得边界线段，但由于边缘不连续，需要拟合图像的边缘以获得轮廓的连续，而且在边界不明显的地方很难确定区域，同时容易造成过分割[7]。
    为此，本文结合分裂合并算法与边缘检测技术，提出了一种新的分裂合并算法。该算法在分裂过程中直接利用图像的边缘信息，不断将图像分裂为一些不规则形状的一致性区域，然后根据一定规则将相似的区域合并起来。
1 分裂合并分割
    定义1  块：用四分法对图像进行逐层分裂，得到的一系列长方形区域。
    定义2  区域：一个图像分块内，边缘与块边界分隔而成的一些列的不规则区域。
    定义3  一致性：设max(R)为每个区域内的像素与该区域均值的最大差值，在不考虑噪声的情况下设置阈值V，如果某区域的max(R)<V，则认为该区域是一致性区域(或者区域同质);否则，区域不同质。
       本文算法描述如下：(1)对图像进行边缘检测,并且对边缘进行增强处理；(2) 对图像进行区域分裂，并消除边缘像素；(3) 对边缘像素进行归并；(4) 对图像进行区域合并。
1.1 边缘检测
　    边缘检测主要检测图像中像素值变化明显的点。由于在两个不同区域的交界处，像素灰度变化明显，因此，检测出来的边缘可以直接将两个不同的区域隔离开来。理想情况下，一张图像由一些连续的边缘分割成若干个区域，但实际上获得的边缘却是一些不连续的曲线，需要对边缘作进一步处理。目前的边缘检测算子主要有Roberts算子、Prewitt算子、Sobel算子和Canny算子等[8]。本文采用Canny梯度算子对图像进行边缘检测。Canny算子参数中阈值threthold1和threthold2主要用来控制生成边缘。
    图像分割中，为了获取足够多的边缘像素，需要动态地调整阈值。阈值较高时，图像的边缘较少，可直接利用的边缘也少；阈值较低时，图像的边缘较丰富，有利于分裂操作，但却容易造成过分割，同时会在合并步骤中增加不必要的工作量。因此对阈值的选择要达到一个平衡点。本文设threthold1=2threthold2，通过不断地调整阈值，使图像的边缘密度控制在一定的范围内。经多次实验，边缘密度在30%左右时分割效果最理想，其分割图像如图1所示。

    边缘检测后，对边缘图像进行闭操作，连接一些小的边缘开口，可以有效地减少图像分割的次数。
1.2图像分裂
    (1)初始层的确定
    在分裂合并方法中，确定图像块的初始划分，就是从四分树中选择某一层作为初始层，该层图像的划分即为图像块的初始划分。若初始层选择较上层时，由于图像的分块内部边缘长度较长，出现断裂的概率较高，块内各区域相连通的概率较大，需要对块继续四等分。若初始层选择较下层时，图像容易被过分割，造成合并运算量剧增，增加不必要的开销。参考文献[9]采用分块的边缘密度作为初始层的划分标准：当每个图像块的边缘密度均小于给定的阈值时，该层可以作为最佳初始层。本文对此作了改进，把边缘密度为0或边缘密度大于给定阈值的层，作为初始划分层。边缘密度为0时，说明块内的边缘同质的概率较大。边缘密度大于阈值时，说明分块内部边缘丰富，极有可能将分块分割成几个同质的区域。
    如图2所示，每一分块内，图像的边缘将分块分割成若干个区域。判断分块的每一个区域是否满足一致性，若不满足，则将该分块继续进行2&times;2等分。

    (2)分块内区域的搜索
    图像的边缘将图像分割成几个不规则的区域。搜索分块内每个像素所属的四连通区域，将这些像素并入所属的区域中。
   图3(a)所示的图像中，左上角的边缘位置有一个断裂口，使得两个不一致的区域相互连通，因此该块不同质。为了获得同质的区域，需继续对该块进行2&times;2等分。分裂后得到的4个子块中,有3块可以获得同质的区域，只有左上角部分需要继续分裂。对左上角继续分裂，子块中只有四分之一部分需要继续分裂，这样极大地减少了分裂的次数。
　而传统的四分法中，由于只在水平和垂直方向上分裂，对于边缘是斜线的情况，只能不断地将块分裂成一些极小的块，以获取同质的区域。
　图3(b)所示的图像中，右上角和下面的两个区域已经符合一致性的标准，因此只需要对左上角分块继续分裂，比传统方法的分裂次数减少了3/4。同时，在左上角的第二次分裂中，又减少了3/4,经过不断递推，可以得到分裂次数比传统减少了：

    不同图像分裂的区域数如表1所示。

1.3 边缘的归并
    在分裂合并中，图像的边缘像素并没有参加分裂操作。因此需要将边缘的像素归并到已经分裂好的区域中。由于边缘像素处在像素灰度迅速变化的区域，因此归并算法十分简单。对于每个边缘像素，只需判断该像素的八邻域，将该像素归并到与之最相似的八邻域所在的区域中,不断检测图中的边缘像素，执行归并算法，直到每个像素都归并到小区域中即可。
1.4区域合并
    图像分裂成一些不规则的区域后，需要对相似的区域进行合并。由于使用区域内的平均值作为一致性的判别根据，每个区域的最初被包含的元素对该区域的划分影响较大。因此在合并的初期，应该把最相似的区域首先合并。
    设R1为图像中的区域，搜索与R1相邻的每一个区域Rn，设置阈值T2，判断dis2=|average(R1)-average(R2)|。
若dis2<T2，则将Rn并入R1所在区域中，重新计算average(R1)。为了使最相似的区域首先合并，开始时，应赋予T2较小的值，然后使T2不断递增，继续执行上面的合并操作。
2 实验结果分析
    如图4~图6所示,所有(b)图左栏均为采用了本文算法，在边缘的连接处，分块数量并无明显增多，且边界光滑。所有(b)图右栏均为采用传统(一般)的分裂方法，在图像的边缘位置，分块急剧增多，且有明显的方块效应。从(c)图中也可以看出，本文算法在图像边缘明显的区域发挥了较大的作用。在区域边界不明显的区域，本文算法同其他算法一样,只能通过不断地对分块进行分裂，以逼近区域的边界，不可避免地会造成一些方块效应。

    从运行时间上比较,由1.2节中分析可以得知，在边缘位置，本文算法可以明显地减少分裂次数，相应地，合并次数也可以减少许多。而在内部区域则与其他算法一致。不足之处在于,由于本文算法中分裂后的形状不规则，区域分裂过程中需要采用水坝法以确定区域的形状，相对耗时较多。整体上，每张图片的分割时间略高于普通的分裂合并算法。
    本文提出的结合边缘检测和分裂合并的图像分割算法，有效地利用图像边缘信息进行区域分裂。由于最大限度地利用了图像的边缘信息，一定程度上避免了过分割和人为分割造成的方块效应。实验表明，利用改进后的算法分割的边界清晰光滑，效果理想。下一步的研究内容是如何根据图像实际情况自适应地选择相关参数对图像进行分割，以及提高分割的运算速度，适应图像检索系统的需要。
参考文献
[1] Li Judong, Ge Yu, OGUNBNA P. An efficient iteractive algorithm for image thresholding[J].Pattern Recognition Letters,2008,29(9):1311-1316.
[2] 刘国英，傅明.一种基于多分辨分析的简化的分裂-合并图像分割算法[J].长沙理工大学学报，2006，3(4):77-79.
[3] HOROWITZ S L. Picture segmentation by a tree traversal algorithm[J]. Journal of the ACM,1976,23(2):368-388.
[4] BARRA V. Robust segmentation and analysis of DNA microarray spots using an adaptative split and merge algorithm[J]. Computer Methods and Programs in Biomedicine, 2006,81(2):174-180.
[5] WU X. Adaptive Split-and-Merge segmentation based on piecewise least-square approximations[M].IEEE Transactionson Pattern Analysis and Machine Intelligence, 1993:808-815.
[6] MERIGOT A. Revisiting image splitting[C]. Proceedings of IEEE International Conference on Computer Vision.[S.l.]: IEEE Computer Society, 2001:517-524.  
[7] EVANS A N, LIU X U.Amorphological gradient approach  to color edge detetion[J].IEEE Transactions.on Image  Processing, 2006,15(6):1454-1463.
[8] 尹平，王润生.基于边缘信息的分开合并图象分割方法[J].中国图像图形学报, 1998，3(6):450-454.
[9] 谢钧，俞潞，吴乐南.一种改进的Split-Merge图像分割算法[J].计算机应用, 2008,28(7):1744-174.