【手撕算法】基于队列实现的区域增长分割算法
前言
上一篇介绍了深度搜索DFS和广度搜索BFS两个算法，本文就是基于BFS算法实现的区域增长算法。
区域增长算法简介
区域增长算法的原理非常简单，就是以一个种子点作为生长的起点，然后将种子周围的点（可以是四邻域也可以是八邻域）进行筛选（筛选条件可以是与种子点像素值是否接近，或者像素梯度是否小于阈值等等）。
如果满足相似性，则该像素归为和种子一类，并对这个像素进行邻域分析，直到没有新的像素为止。这样一个区域的生长就完成了。
这个过程中有几个关键的问题：
- 给定种子点(种子点如何选取？) 种子点的选取很多时候都采用人工交互的方法实现，也有用其他方式的，比如寻找物体并提取物体内部点作为种子点。本文通过鼠标点击得到。
- 确定在生长过程中对相邻像素的筛选准则 灰度图像的差值；彩色图像的颜色等等，都是关于像素与像素间的关系描述。本文采用灰度图像的插值
- 生长的停止条件 当种子同类像素中每一个像素邻域像素都不满足相似条件时。
程序运行效果
动图：
本程序运行生成三个窗口：
- 【原图】用来观看原图
- 【种子图】会包含鼠标点击生成的红色种子
- 【种子增长图】显示了每一个种子所增长出来的区域，为二值图
算法实现
#define WINDOW_1 "原图"
#define WINDOW_2 "种子图"
#define WINDOW_3 "种子增长图"
#define region_radiu 1 //种子半径首先是一些宏定义，包括三个窗口名，种子半径是我们在鼠标点击一个点后，用红色的圆进行标识，圆的半径设为1。
主函数：
int main() {
Mat srcImage, dstImage;
srcImage = imread("唔姆.png",17);
if (srcImage.empty()) {
printf_s("图片读取失败");
return -1;
}
namedWindow(WINDOW_1);//定义一个算法展示窗口
namedWindow(WINDOW_2);
namedWindow(WINDOW_3);
imshow(WINDOW_1, srcImage);//仅显示原图
Region_Growing_Map = Mat::zeros(srcImage.size(), CV_8UC1); //创建一个空白区域，填充为黑色
srcImage.copyTo(dstImage);//用于鼠标回调显示种子位置
setMouseCallback(WINDOW_2, on_MouseHandle, (void*)&dstImage);//调用回调函数
while (1) {
imshow(WINDOW_2, dstImage); //不断的用读取图片更新窗口
if (waitKey(10) == 27) break;//当按下Esc时程序结束
}
cv::waitKey(0);
}主函数主要是进行了图片显示和鼠标回调函数的使用。
鼠标回调函数：
void on_MouseHandle(int event, int x, int y, int flags, void* param)
{
Mat& src = *(cv::Mat*) param;//需要处理的图片
//【1】将读取的图片转灰度
Mat src_gray;
if (src.channels() > 1) {
cv::cvtColor(src, src_gray, COLOR_RGB2GRAY);
//imshow("灰度图", src_gray);
}
else {
src.copyTo(src_gray);
//imshow("灰度图", src_gray);
}
//【2】检测鼠标事件
Point2i pt;
switch (event){//检查鼠标事件
case cv::EVENT_LBUTTONDOWN://左键按下
{
pt = Point2i(x, y);//x行，y列，获取鼠标箭头坐标
circle(src, pt, region_radiu, Scalar(0, 0, 255));
RegionGrow(src_gray, pt, 40); //区域生长
}
break;
case cv::EVENT_RBUTTONDOWN://右键按下
{
Region_Growing_Map = Mat::zeros(src.size(), CV_8UC1);//清空区域增长图
imshow(WINDOW_3, Region_Growing_Map);
}
break;
}
}鼠标回调函数主要完成了两个功能：
其一，将鼠标回调函数操作的图片（也就是我们用来点击生成种子的图片）转为灰度图。转为灰度图不仅可以简化我们的操作，而且我们对种子邻域像素的筛选条件采用的是灰度值的插值小于设定阈值，所以需要对灰度图进行操作。
其二，进行鼠标事件的检测，当鼠标右键按下时，清空Mat类型的全局变量Region_Growing_Map(区域增长图)，也就是清空之前点击的所有种子。
当鼠标左键按下时，在窗口2中绘制出红色种子，然后对该种子进行区域增长。
区域增长函数：
void RegionGrow(cv::Mat& grayImage, Point2i pt, int th)
{
Point2i ptGrowing; //待生长点位置
int nGrowLable = 0; //标记是否生长过
int nSrcValue = 0; //生长起点灰度值
int nCurValue = 0; //当前生长点灰度值
//matDst = Mat::zeros(src.size(), CV_8UC1); //创建一个空白区域，填充为黑色
int X[8] = { -1,0,1,-1,1,-1,0,1 }; //增量数组，方便检查每一像素的八个邻域
int Y[8] = { -1,-1,-1,0,0, 1,1,1 };
queue<Point2i> vcGrowPt; //生长点队列
vcGrowPt.push(pt); //将生长点压入队列中
Region_Growing_Map.at<uchar>(pt.y, pt.x) = 255; //标记生长点
imshow(WINDOW_3, Region_Growing_Map);
nSrcValue = grayImage.at<uchar>(pt.y, pt.x); //记录生长点的灰度值
Point2i step_point;
while (!vcGrowPt.empty()) //生长队列不为空则生长
{
step_point = vcGrowPt.front(); //取出队首生长点
vcGrowPt.pop();
//分别对八个方向上的点进行生长
for (int i = 0; i < 8; i++)
{
ptGrowing.x = step_point.x + X[i];
ptGrowing.y = step_point.y + Y[i];
//检查当前点是否是边缘点，如果是，则跳过
if (ptGrowing.x < 0 || ptGrowing.y < 0 || ptGrowing.x >= grayImage.cols || ptGrowing.y >= grayImage.rows)
{
continue;
}
nGrowLable = Region_Growing_Map.at<uchar>(ptGrowing.y, ptGrowing.x); //当前待生长点的灰度值
//printf_s("%d\n", nGrowLable);
if (nGrowLable == 0) //如果标记点还没有被生长
{
nCurValue = grayImage.at<uchar>(ptGrowing.y, ptGrowing.x);
if (abs(nSrcValue - nCurValue) < th) //在阈值范围内则生长
{
Region_Growing_Map.at<uchar>(ptGrowing.y, ptGrowing.x) = 255; //标记为白色
imshow(WINDOW_3, Region_Growing_Map);
//waitKey(1);
vcGrowPt.push(ptGrowing); //将下一个生长点压入栈中
}
}
}
}
}区域增长函数采用广度搜索算法BFS，基本算法思想：
- 声明一个队列，并将函数传入参数中的种子坐标点压入队列。
- 将Region_Growing_Map（区域增长图）对应种子点灰度值设为255（白色）。
- 若当队列不为空，进行while循环
- 获得队列首个元素坐标点A，并将A从队列中删除。
- 对该点A 执行for循环访问其八个邻域像素B
- 若邻域像素B超出图片边界或者已经被生长过（即该点已经被设置为255白色），则舍去。否则，将该点纳入区域增长（即将其像素值设为255），并将该点加入到队列中。
- 循环重复3-6步，直到队列为空，也就是没有点满足条件结束。
THE END
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-02-06，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读