基于区域生长的图像分割算法及其实现.doc

基于区域生长的图像分割算法及其实现 曾春玲，2011441794 （重庆科技学院测控2011-02）摘要：图像分割的目的是将图像划分为不同的区域，基于区域生长是以直接找寻区域为基础的分割技术。是图像处理和计算机视觉的基本问题之一，是图像处理和图像分析的关键步骤。本文对基于区域的图像分割方法进行了综述，具体介绍了区域生长法和分裂合并法，并分析出这种算法在应用中的优缺点，实现此种算法。关键词：图像分割 区域生长 分裂合并1 引言 区域生长是一种古老的图像分割方法，最早的区域生长图像分割方法是由Levine等人提出的。该方法一般有两种方式，一种是先给定图像中要分割的目标物体内的一个小块或者说种子区域(seed point)，再在种子区域基础上不断将其周围的像素点以一定的规则加入其中，达到最终将代表该物体的所有像素点结合成一个区域的目的；另一种是先将图像分割成很多的一致性较强，如区域内像素灰度值相同的小区域，再按一定的规则将小区域融合成大区域，达到分割图像的目的，典型的区域生长法如T. C.Pong等人提出的基于小面（facet）模型的区域生长法，区域生长法固有的缺点是往往会造成过度分割，即将图像分割成过多的区域 。本文对近年来国内外基于区域的图像分割算法进行了介绍，并分析了各算法在实际应用中的优缺点。从中可以看出，仅仅使用一种算法实现对图像的分割，越来越难以满足实际应用中对图像分割的要求。但是随着图像分割理论的研究，将会有更多的图像分割算法被提出。图像分割算法也将向更快速，更精确的方向发展。2 区域生长法区域生长是一种根据事先定义的准则将像素或子区域聚合成为更大的区域的过程。基本方法是以一组“种子”点开始，将与种子点性质相似（诸如灰度级或衍射的特定范围）的相邻像素附加到生长区域的每个种子上。 区域生长的一个问题是用公式描述一个终止规则。基本上，在没有像素满足加入某个区域的条件时，区域生长就会停止。在此次课程设计中，在算法的设计上充分反映了这一点。在遍历图像的过程中调用函数testnei，测试i,j点处的邻域满足条件的像素。将每次新增长的种子点作为下次遍历的中心点，直到区域不再生长。 2.1区域生长区域生长的基本思想是将具有相似性质的像素集合起来构成区域。具体先对每个需要分割的区域找一个种子像素作为生长起点，然后将种子像素和周围邻域中与种子像素有相同或相似性质的像素（根据某种事先确定的生长或相似准则来判定）合并到种子像素所在的区域中。将这些新像素当作新的种子继续上面的过程，直到没有满足条件的像素可被包括进来。这样一个区域就生长成了。区域生长需要选择一组能正确代表所需区域的种子像素，确定在生长过程中的相似性准则，制定让生长停止的条件或准则。相似性准则可以是灰度级、彩色、纹理、梯度等特性。选取的种子像素可以是单个像素，也可以是包含若干个像素的小区域。大部分区域生长准则使用图像的局部性质。生长准则可根据不同原则制定，而使用不同的生长准则会影响区域生长的过程。2.2区域生长准则区域生长的关键是选择合适的生长或相似准则, 大部分区域生长准则会使用图像的局部性质。生长准则可以根据不同原理制定, 而使用不同的生长准则会影响区域生长的过程。常用的生长准则和方法有三种, 即基于区域灰度差的、基于区域内灰度分布统计性质的、基于区域形状的。2.2.1基于区域灰度差的生长准则 基于区域灰度差的生长准则在我们使用的区域生长方法中, 操作的基本单位是象素, 基于区域灰度差的生长准则步骤如下: 1.对图像进行逐行扫描, 找出尚无归属的象素; 2.以该象素为中心, 检查它相邻的象素, 即将邻域中的象素逐个与它比较, 如果灰度差小于事先确定的阈值, 则将它们合并; 3.以新合并的象素为中心, 再进行步骤2 检测, 直到区域不能进一步扩张; 4.重新回到步骤1, 继续扫描直到不能发现没有归属的象素, 整个生长过程结束。 上述方法是先要进行扫描, 这对区域生长起点的选择有比较大的依赖性, 为克服这个问题可以改进方法如下: 1. 设灰度差的阈值为零, 用上述方法进行区域扩张, 合并灰度相同的象素; 2. 求出所有邻接区域之间的平均灰度差, 合并具有最小灰度差的邻接区域; 3. 设定终止准则, 通过反复进行步骤2 中的操作将区域依次合并, 直到终止准则满足为止, 生长过程结束。 2.2.2基于区域内灰度分布统计性质的生长准则 考虑以灰度分布相似性作为生长准则来决定区域的合并, 具体步骤为: 1.把图像分成互不重叠的小区域; 2.比较邻接区域的累积灰度直方图, 根据灰度分布的相似性进行区域合并;3.设定终止准则, 通过反复进行步骤2 中的操作将各个区域依次合并直到满足终止准则, 生长过程结束。2.3区域生长算法区域生长是一种很重要的图像分割方法。它是指从某个像素出发，比较相邻接像素的特征向量(包括灰度、边缘、纹理等特征)，在预先指定的准则下，若它们足够相似则作为同一区域合并，以此方式使相似特征的区域不断增长，最后形成分割图像。 图1给出已知种子点进行区域生长的一个示例。图1（a）给出需要分割的图像，设已知两个种子像素（标为深浅不同的灰色方块），现要进行区域生长。设这里采用的判定准则是：如果考虑的像素与种子像素灰度值差的绝对值小于某个门限T，则将该像素包括进种子像素所在的区域。图1（b）给出了T=3时的区域生长结果，整幅图被较好地分成2个区域；图1（c）给出了T=1时的区域生长结果，有些像素无法判定；图1（c）给出了T=6时的区域生长的结果，整幅图都被分在一个区域中了。由此可见门限的选择是很重要的。 （a） （b） （c） （d）图1 区域生长的实例Fig.1 Examples of regional growth2.3.1区域生长实现首先确定一个或多个像素点作为种子点，然后按照某种相似性度量增长区域，逐步生成具有某种均匀性的空间区域，并将相邻的具有相似性的像素点或区域归并，直至没有可归并的像素点或小区域为止。实现步骤如下：1.对图像顺序扫描找到第1个还没有归属的像素, 设该像素为(x0, y0); 2.以(x0, y0)为中心, 考虑(x0, y0)的4邻域像素(x, y)如果(x0, y0)满足生长准则, 将(x, y)与(x0, y0)合并(在同一区域内), 同时将(x, y)压入堆栈;3.从堆栈中取出一个像素, 把它当作(x0, y0)返回到步骤2; 4. 当堆栈为空时返回到步骤1; 5. 重复步骤1 - 4直到图像中的每个点都有归属时。生长结束在实际应用区域生长法时需要解决三个问题: 1.选择或确定一组能正确代表所需区域的种子象素( 选取种子) 2.确定在生长过程中能将相邻象素包括进来的准则( 确定门限) 3.确定让生长过程停止的条件或规则( 停止条件) 可以认为，这三个问题需要具体分析，而且每个问题解决的好坏直接关系到区域生长的结果。首先指定几个种子点，然后把图像中灰度值等于种子点的像素点也作为种子点；然后以种子点为中心，若某个像素点与种子点的灰度值的差不超过某个阀值，则认为该像素点和种子点具有相似性。区域生长可以用图像处理工具中的imreconstruct函数来实现。该函数的调用语法为：Outim=imreconstruct(markerim,maskim)其中markerim为标记图像，maskim为模板图像，outim为输出图像，imreconstruct函数的工作过程是一个迭代过程，大致过程如下：1）把f1初始化为标记图像markerim。2）创建一个结构元素B= 。3）重复以下计算知道fk+1=fk， fk+1=（fkB）maskim其中为形态学中的膨胀算子。最后，用图像处理工具箱中的bwlable函数把区域连接起来，以此完成图像的分割。Bwlable函数的调用语法为：1，num=bwlable（bw，n）其中bw为输入图像，n可取4或8，表示四连通或八连通区域，num为找到的连通区域数目，1为输出矩阵，其元素值为整数值，背景标记为0，第一个连通区域被标记为1，第二个连通区域被标记为2，依此类推。2.4应用情况： 区域生长（region growing）是指将成组的像素或区域发展成更大区域的过程。从种子点的集合开始，从这些点的区域增长是通过将与每个种子点有相似属性像强度、灰度级、纹理颜色等的相邻像素合并到此区域。它是一个迭代的过程，这里每个种子像素点都迭代生长，直到处理过每个像素，因此形成了不同的区域，这些区域它们的边界通过闭合的多边形定义。区域生长法的优点是计算简单，对于较均匀的连通目标有较好的分割效果。它的缺点是需要人为确定种子点，对噪声敏感，可能导致区域内有空洞。另外，它是一种串行算法，当目标较大时，分割速度较慢，因此在设计算法时，要尽量提高效率。2.5区域生长的后处理由于非优化参数的设置，区域生长经常会导致欠生长或过生长。人们已经开发了各种各样的后处理。从区域生长和基于边缘的分割中，后处理能获得联合分割的信息。更加简单的后处理是根据一般启发法，并且根据最初应用的均匀性标准，减少分割图像中无法与任何邻接区域合并的最小区域的数量。 图2 脑部图像和区域生长法分割的结果Fig.2 Brain image segmentation and region growing segmentationresults method3 区域分裂合并区域生长是从某个或者某些像素点出发，最后得到整个区域，进而实现目标提取。分裂合并差不多是区域生长的逆过程：从整个图像出发，不断分裂得到各个子区域，然后再把前景区域合并，实现目标提取。分裂合并的假设是对于一幅图像，前景区域由一些相互连通的像素组成的，因此，如果把一幅图像分裂到像素级，那么就可以判定该像素是否为前景像素。当所有像素点或者子区域完成判断以后，把前景区域或者像素合并就可得到前景目标。在这类方法中，最常用的方法是四叉树分解法(如图3所示)。设R代表整个正方形图像区域，P代表逻辑谓词。基本分裂合并算法步骤如下： 图3 四叉树分割后的图像Fig.2 Four fork tree image after segmentation(1)对任一个区域，如果H(Ri)=FALSE就将其分裂成不重叠的四等份；(2)对相邻的两个区域Ri和Rj，它们也可以大小不同（即不在同一层），如果条件H(RiRj)=TRUE满足，就将它们合并起来。(3)如果进一步的分裂或合并都不能，则结束。区域分裂合并算法的基本思想是先确定一个分裂合并的准则,即区域特征一致性的测度,当图像中某个区域的特征不一致时就将该区域分裂成4 个相等的子区域，当相邻的子区域满足一致性特征时则将它们合成一个大区域,直至所有区域不再满足分裂合并的条件为止。当分裂到不能再分的情况时，分裂结束，然后它将查找相邻区域有没有相似的特征，如果有就将相似区域进行合并，最后达到分割的作用。分裂合并法的关键是分裂合并准则的设计。这种方法对复杂图像的分割效果较好，但算法较复杂，计算量大，分裂还可能破坏区域的边界。区域生长比区域分裂合并的方法节省了分裂的过程，而区域分裂合并的方法可以在较大的一个相似区域基础上再进行相似合并，而区域生长只能从单一像素点出发进行生长（合并）。区域生长和分裂合并是两种典型的串行区域分割算法。其特点是将分割过程分解为顺序的多个步骤，其中后续步骤要根据前面步骤的结果进行判断而确定。 在一定程度上区域生长和区域分裂合并算法有异曲同工之妙，互相促进相辅相成的，区域分裂到极致就是分割成单一像素点，然后按照一定的测量准则进行合并，在一定程度上可以认为是单一像素点的区域生长方法。4 总结图像分割是数字图像处理中的一项关键技术，在许多领域均有所应用，多年来一直受到研 究人员的高度重视。然而，目前使用的上千种图像分割算法大都是针对具体问题所提出的，虽然 每年都有新的图像分割算法提出，但是并没有一种通用的算法能适用于所有的图像分割处理。基 于区域的图像分割算法是图像分割算法中较常用的一部分。本文对基于区域的图像分割算法作以 系统的分类和基本的