本文介绍一种区域生长法进行图像分割的数据组织方式和实现方法，给出了核心代码，可用该方法实现立体匹配中的非法点检测。

区域生长法图像分割是直接根据像素的相似性和连通性来对图像进行聚类的算法。基本原理是，给出若干种子点，然后依次对这些种子点进行如下操作，直到种子点集合为空：判断种子点四邻域或八邻域的像素点是否和种子点相似（灰度相似或其他测度相似），如果相似则将该点加入种子点集合，否则不作处理。

该算法原理很简单，但在数据结构的组织上却需要技巧，本文介绍一种简易的数据组织方式实现该算法。

如上图所示，左图为一幅W*H大小的图像示意图，利用区域生长法图像分割算法，该图像被分割（聚类）为7块；右图为相应的数据结构，图像分割的结果属于图像空间数据，其实就是一系列的像素点坐标数组或与像素点坐标直接关联的属性数组如FLAG的数组等，这个数组的维度一定是W*H，而分割结果体现在数组元素的排列顺序：同一类别的元素连续存储。然而类别的界限无法用该数组表明，而只能用另外一个描述数组，这里我们称之为图像空间数据的“元数据”数据，这个数组的有效维度为空间数据的类别数，即7，每个元素代表的是空间数据数组中每个类别的元素个数，其实也就相应地表明了每个类别的指针位置。

下面，我们说明这个算法的代码实现过程：

首先定义图像空间数据的结构体和几个重要变量：

	typedef struct{
		unsigned short x;
		unsigned short y;
	}seedpoint;
	enum FLAG{VALID, INVALID, VALID_SEG,INVALID_SEG};//图像空间数据标示
	FLAG *flag;//图像空间数据标示数组
	seedpoint *InvalidSeedPts;//种子点数组
	int num_InvalidSeedPts;//种子点数量
	seedpoint *segmentation_invalidpts;//存储分割结果的数组
	seedpoint *temp_invalidpts;//算法中临时变量
	int num_classes;//分割类别数目
	int *num_class;//空间数据“元数据”数组，存储分割结果每个类别的数目

void Segmentation(int delt_connect)
{
	int counter=0;
	int temp_num_invalidpts=0;

	seedpoint point,temppoint;
	for (int i=0;i<num_InvalidSeedPts;i++)
	{
		point = InvalidSeedPts[i];
		if (flag[point.x*width+point.y] == VALID)
		{
			segmentation_invalidpts[counter] = point;
			counter++;

			temp_num_invalidpts=0;
			temp_invalidpts[temp_num_invalidpts] = point;
			temp_num_invalidpts++;
			int j=0;

			flag[point.x*width+point.y] = VALID_SEG;

			while (j<temp_num_invalidpts)
			{
				point = temp_invalidpts[j];
				if ((point.x>0)&&(point.x<(height-1))&&(point.y>0)&&(point.y<(width-1)))
				{
					int index1 = point.x*width+point.y;
					if((flag[(point.x-1)*width+point.y]==VALID))
					{
						temppoint.x = point.x-1;
						temppoint.y = point.y;

						int index2 = temppoint.x*width+temppoint.y;
						int delt = abs(buf[index1] - buf[index2]);

						if(delt < delt_connect)
						{
							segmentation_invalidpts[counter] = temppoint;
							counter++;
							temp_invalidpts[temp_num_invalidpts] = temppoint;
							temp_num_invalidpts++;
							flag[(point.x-1)*width+point.y]=VALID_SEG;	
						}
					}
					if((flag[(point.x+1)*width+point.y]==VALID))
					{
						temppoint.x = point.x+1;
						temppoint.y = point.y;

						int index2 = temppoint.x*width+temppoint.y;
						int delt = abs(buf[index1] - buf[index2]);

						if(delt < delt_connect)
						{
							segmentation_invalidpts[counter] = temppoint;
							counter++;
							temp_invalidpts[temp_num_invalidpts] = temppoint;
							temp_num_invalidpts++;
							flag[(point.x+1)*width+point.y]=VALID_SEG;
						}
					}
					if((flag[point.x*width+point.y+1]==VALID))
					{
						temppoint.x = point.x;
						temppoint.y = point.y+1;

						int index2 = temppoint.x*width+temppoint.y;
						int delt = abs(buf[index1] - buf[index2]);

						if(delt < delt_connect)
						{
							segmentation_invalidpts[counter] = temppoint;
							counter++;
							temp_invalidpts[temp_num_invalidpts] = temppoint;
							temp_num_invalidpts++;
							flag[point.x*width+point.y+1]=VALID_SEG;
						}
					}
					if((flag[point.x*width+point.y-1]==VALID))
					{
						temppoint.x = point.x;
						temppoint.y = point.y-1;

						int index2 = temppoint.x*width+temppoint.y;
						int delt = abs(buf[index1] - buf[index2]);

						if(delt < delt_connect)
						{
							segmentation_invalidpts[counter] = temppoint;
							counter++;
							temp_invalidpts[temp_num_invalidpts] = temppoint;
							temp_num_invalidpts++;
							flag[point.x*width+point.y-1]=VALID_SEG;
						}
					}
				}
				j++;
			}
			num_class[num_classes] = temp_num_invalidpts;
			num_classes++;
		}
	}
}

其中，左图为原始结果，中图为非法点检测结果，右图为非法点FLAG图像。

区域生长法图像分割的实现方法