区域生长算法：基于质心的图像分割方法

区域生长（Region Grow）是一种根据事先定义的准则将像素或者子区域聚合成更大区

域的过程。简单地说，就是从图像中的某个像素或区域出发，按照一定的准则，逐步加入邻近像素或区域，当满足一定的条件时，区域生长终止。最后得到整个区域，进而实现目标的提取。基本思想是从一组生长点（可以是单个像素，也可以是某个小区域）开始，搜索其邻域，把图像分割成特征（如（平均）灰度值、纹理、颜色信息等）相似的若干区域。比较相邻区域与生长点特征的相似性，若它们足够相似，则作为同一区域合并，形成新的生长点。以此方式将特征相似的区域不断合并、直到不能合并为止，最后形成特征不同的各区域。这是一个迭代的过程，整个过程象是一个物体内部的区域不断增长，直至其边界对应于物体的真正边界，因而将该算法命名为区域生长，也称区域扩张法。

在实际应用时，要解决三个问题：即确定区域的数目、选择有意义的特征和确定相似性准则。区域生长结果的精度取决于三个要素：初始点（种子点）的选取、生长准则和终止条件。

种子点的选择没有一定的标准，取决于所处理的图像。可以先分析图像的特征，用一些图像的特性，例如在某个区域里亮度最大的点。或者采用交互式的方法，手动选择一点作为初始点，然后按一定策略自动生长。

特征相似性是构成与合并区域的基本准则，相邻性是指所取的邻域方式。根据所用的邻域方式和相似性准则的不同，产生不同的区域生长法。将灰度相关的值作为区域生长准则，区域生长可分为单一型（像素与像素）、质心型（像素与区域）和混合型（区域与区域）三种。

（一）单一型区域生长法

单一型区域生长算法的基本原理是以图像的某个像素为生长点，检查该点的邻近像素，如果是满足要求的特征点，则加入区域中；然后以合并的像素为生长点，重复以上操作，直到没有新的点加入区域中为止，最终形成具有相似特征的像素的最大连通集合。

具体步骤如下：

1）对图像进行扫描，找出尚没有归属的像素。当寻找不到这样的像素时结束操作。

2）把这个像素灰度同其周围（4邻域或8邻域）不属于任何一个区域的像素进行比较，若灰度差值小于某一阈值，则将它们合并为同一个区域，并对合并的像素做标记。

3）从新合并的像素开始，反复进行步骤2）的操作。

4）反复进行步骤2）和3），直到区域不能再合并为止。

5）返回步骤1），寻找能作为新区域出发点的像素。

对于二值图像，假设背景区域的灰度值为255，目标区域的灰度值为0，则单一型区域生长的具体步骤如下：

1）按照从左到右（或者从上到下）的顺序遍历整幅二值图像，找到一个特征点I（i，J）=0。

2）定义两个队列：工作队列Qw（Working Queue）和区域队列Qr（Region Queue）。将Qw和Qr清空，以点（i，j）为起点，按照如下循环进行区域生长：

①把种子点（i，j）加入Qw中，同时加入Qr中。当前指针指向Qw的种子点（i，j）。

②从Qw中取出指针所指的点，判断其m×m邻域内像素的灰度值：如果邻域像素的灰度值为0，则将该点加入Qw中，同时加入Qr中。把该像素和种子点的灰度值都置为背景值255。

③工作队列指针向后移动一位。

④如果当前指针指向Qw末尾，则转向步骤⑤；否则，重复步骤①～步骤③。

⑤输出目标区域队列Qr，继续步骤3）。

3）如果Qr中点的总数小于预先设定的阈值TN，那么转向步骤1），找到下一个特征点作为种子点，重复步骤①～⑤；否则，转向步骤4）。

4）输出区域队列以。

上述算法完全自动进行，不需要操作者的参与。(www.xing528.com)

从以上步骤可以看出，区域生长的结果受到两个参数的影响：邻域大小m和阈值TN。如果m过小，可能搜索不到期望的区域；如果m值过大，会将与目标相邻的背景结构也提取出来。图3-24是对二值化处理之后的X射线冠状动脉造影图像进行区域生长提取血管区域的结果，由图可见，分割结果对m的取值很敏感。

图3-24　邻域宽度m取不同值时的区域生长结果

a）原始灰度图像　b）自适应阈值分割结果　c）m=3的单一区域生长结果　d）m=7的单一区域生长结果　e）m=13的单一区域生长结果

该方法原理简单，但如果区域之间的边缘灰度变化很平缓或边缘交于一点时，两个区域会合并起来，如图3-25所示。解决方法是在步骤2）中不比较相邻像素灰度值，而是比较已存在的区域的平均灰度值与该区域邻接的像素灰度值，即质心型区域生长。

图3-25　边缘对区域扩张的影响

a）平缓的边缘　b）边缘的缝隙

（二）质心型区域生长

质心型区域生长与简单区域生长法类似，唯一不同的是在步骤2）中，改为比较已存在区域的特征与该区域邻接的像素的特征。若差值小于阈值，则将像素归并到区域中。

（三）混合型区域生长

混合型区域生长法是把图像分割成小区域，比较相邻小区域的相似性，如果相似则合并。包括不依赖于起始点的方法和假设检验两种方法。

1.不依赖于起始点的方法具体步骤如下：

1）设灰度差的阈值为0，即判断相似的标准是灰度值相等。用简单区域生长法把具有相同灰度的像素合并到同一区域，得到初始分割图像。

2）从分割图像的一个小区域开始，求出相邻区域间的灰度差，将差值最小的相邻区域合并。

3）反复步骤2）的操作，把区域依次合并。

该方法的缺点是，若不在适当的阶段停止区域合并，整幅图像经区域生长的最终结果就会成为一个区域。

2.假设检验法

根据区域内的灰度分布的相似性进行区域合并。具体步骤如下：

1）把图像分割成互不交叠的、大小为n×n的小区域。

2）比较相邻小区域的灰度直方图，如果灰度分布情况是相似的，则合并成一个区域。相似性判断标准可选用Kolmogorov-Smirnov检测标准

或者Smoothed-Difference检测标准

式中，H1（g）和H2（g）分别是相邻两区域的累积灰度直方图

3）反复进行步骤2）的操作，直至区域不能合并为止。

该方法不仅能分割灰度相同的区域，也能分割纹理性的图像，但难点在于n如何确定。n太大，则区域形状变得不自然，小的目标就会遗漏；n太小，则Kolmogorov-Smirnov和Smoothed-Difference检测标准的可靠性下降，导致分割质量差。实际中一般取n=5～10，由于Smoothed-Difference标准的要求比Kolmogorov-Smirnov严格，采用Smoothed-Difference比Kolmogorov-Smirnov标准会带来更好的结果。