分水岭算法
1.经典算法原理及实现
传统的目标分割算法主要分为两种
1.基于像素相似性：阈值分割、k-means分割
2.基于像素邻域关系：区域生长、分水岭、基于标记+分水岭
分水岭算法原理
如图中展现了凹凸不平的地貌，视觉上明显的位置有盆地及丘陵，用一维曲线讲对应波峰与波谷，向盆地注水，水会顺这地势先注入地势最低的波谷，然后随着水势升高再注入高一级的波谷，为了保证先注满第一个波谷，需要在右侧波峰出修建大坝，随后依次分水岭注满。
在图像中，地貌对应整个图像的背景，地势对应图像像素点大小。
分水岭算法整个过程：
1.把梯度图像中的所有像素按照灰度值进行分类，并设定一个测地距离阈值。
2.找到灰度值最小的像素点（默认标记为灰度值最低点），让threshold从最小值开始增长，这些点为起始点。
3.水平面在增长的过程中，会碰到周围的邻域像素，测量这些像素到起始点（灰度值最低点）的测地距离，如果小于设定阈值，则将这些像素淹没，否则在这些像素上设置大坝，这样就对这些邻域像素进行了分类。
4.随着水平面越来越高，会设置更多更高的大坝，直到灰度值的最大值，所有区域都在分水岭线上相遇，这些大坝就对整个图像像素的进行了分区。
用上面的算法对图像进行分水岭运算，由于噪声点或其它因素的干扰，可能会得到密密麻麻的小区域，即图像被分得太细（over-segmented，过度分割），这因为图像中有非常多的局部极小值点，每个点都会自成一个小区域。
其中的解决方法：
对图像进行高斯平滑操作，抹除很多小的最小值，这些小分区就会合并。
不从最小值开始增长，可以将相对较高的灰度值像素作为起始点（需要用户手动标记），从标记处开始进行淹没，则很多小区域都会被合并为一个区域，这被称为基于图像标记(mark)的分水岭算法。
opencv 函数
void watershed( InputArray image, InputOutputArray markers );
分割流程总结：
step1: 图像灰度化、滤波、Canny边缘检测
step2:查找轮廓，并且把轮廓信息按照不同的编号绘制到watershed的第二个入参merkers上，相当于标记注水点。
step3:watershed分水岭运算
step4:绘制分割出来的区域，视觉控还可以使用随机颜色填充，或者跟原始图像融合以下，以得到更好的显示效果。
/**
*定义一个使用分水岭算法的辅助类
*/
class WatershedSegmenter{
{
private:
Mat markers;
public:
void setMarkers(Mat&markerImage)
{
markerImage.convertTo(markers,CV_32S);
}
Mat process(Mat&image)
{
watershed(image,markers);
markers.convertTo(markers,CV_8U);
return markes;;
}
};
//接受一个参数，显示结果
void watershedSegment (Mat img){
Mat gray(img.rows, img.cols,CV_8UC1);
cvtColor(img, gray, CV_BGR2GRAY); //转换为8-bit，3通道的灰度图
Mat binary = Mat::zeros(gray.rows, gray.cols, CV_8UC1);
adaptiveThreshold(gray, binary, 255, ADAPTIVE_THRESH_GAUSSIAN_C, THRESH_BINARY_INV, 5, 10); //将灰度图转换为二值图
Mat markers = Mat::zeros(gray.rows, gray.cols, CV_8UC1);
//使用findContour()函数找出图像的轮廓
vector<vector<Point> > contours;
vector<Vec4i> hierarchy;
findContours(binary, contours, hierarchy, CV_RETR_LIST, CV_CHAIN_APPROX_NONE);
//将contours结果放入到markers中，便于访问
int idx = 0;
for( ; idx >= 0; idx = hierarchy[idx][0]){
Scalar color(rand()&255, rand()&255, rand()&255);
drawContours(markers, contours, idx, color, CV_FILLED, 8, hierarchy);
}
//调用分水岭算法分割图像
WatershedSegmenter segmenter;
segmenter.setMarkers(markers);
cv::Mat result = segmenter.process(img);
//显示分割结果
namedWindow("segmentation_result", 0);
imshow("segmentation_result", result);
}
2.分水岭算法C++实现
实现效果：
opencv结果
c++实现效果
#include <opencv2/imgproc/imgproc.hpp>
#include <opencv2/objdetect/objdetect.hpp>
#include <opencv2/highgui/highgui.hpp>
#include<vector>
#include<iostream>
#include<queue>
#include<fstream>
cv::Mat marker_mask;
cv::Mat g_markers;
cv::Mat img0, img, img_gray,wshed;
cv::Point_<int> prev_pt(-1,-1);
using std::vector;
using std::queue;
static void my_watershed(cv::Mat img,cv::Mat& markers,int comp_count);
static void mouse_event(int event,int x, int y,int flags, void*)
{
if(img.rows==0)
return;
if(event==CV_EVENT_LBUTTONUP||!(flags&CV_EVENT_FLAG_LBUTTON))
prev_pt=cv::Point_<int>(-1,-1);
else if(event==CV_EVENT_LBUTTONDOWN)
prev_pt=cv::Point2i(x,y);
else if(event==CV_EVENT_MOUSEMOVE&&(flags&CV_EVENT_FLAG_LBUTTON))
{
cv::Point2i pt(x,y);
if(prev_pt.x<0)
prev_pt=pt;
cv::line(marker_mask,prev_pt,pt,cv::Scalar(255,255,255),1,8,0);
cv::line(img,prev_pt,pt,cv::Scalar(255,255,255),1,8,0);
prev_pt=pt;
cv::imshow("image",img);
}
}
int main()
{
img0=cv::imread("Lenna.png",1);
img=img0.clone();
CvRNG rng = cvRNG(-1);
img_gray=img0.clone();
wshed=img0.clone();
marker_mask=cv::Mat(cv::Size(img0.cols,img0.rows),8,1);
g_markers=cv::Mat(cv::Size(img0.cols,img0.rows),CV_32S,1);
cv::cvtColor(img,marker_mask,CV_BGR2GRAY);
cv::cvtColor(marker_mask,img_gray,CV_GRAY2BGR);
for(int i=0;i<marker_mask.rows;i++)
for(int j=0;j<marker_mask.cols;j++)
marker_mask.at<unsigned char>(i,j)=0;
for(int i=0;i<g_markers.rows;i++)
for(int j=0;j<g_markers.cols;j++)
g_markers.at<int>(i,j)=0;
cv::imshow("image",img);
cv::imshow("watershed transform",wshed);
cv::setMouseCallback("image",mouse_event,0);
for(;;)
{
int c=cv::waitKey(0);
if((char)c==27)
break;
if((char)c=='r')
{
for(int i=0;i<marker_mask.rows;i++)
for(int j=0;j<marker_mask.cols;j++)
marker_mask.at<unsigned char>(i,j)=0;
img0.copyTo(img);
cv::imshow("image",img);
}
if((char)c=='w'||(char)c==' ')
{
vector<vector<cv::Point>> contours;
CvMat* color_tab=0;
int comp_count=0;
cv::findContours(marker_mask,contours,CV_RETR_CCOMP,CV_CHAIN_APPROX_SIMPLE,cv::Point(0,0));
for(int i=0;i<g_markers.rows;i++)
for(int j=0;j<g_markers.cols;j++)
g_markers.at<int>(i,j)=0;
vector<vector<cv::Point> >::iterator iter=contours.begin();
for(int i=0;i<(int)contours.size();i++)
{
cv::drawContours(g_markers,contours,i,cv::Scalar::all(comp_count+1),
1,8,vector<cv::Vec4i>());
comp_count++;
}
if(comp_count==0)
continue;
color_tab=cvCreateMat(1,comp_count,CV_8UC3);
for(int i=0;i<comp_count;i++)
{
uchar* ptr=color_tab->data.ptr+i*3;
ptr[0]=(uchar)(cvRandInt(&rng)%180+50);
ptr[1]=(uchar)(cvRandInt(&rng)%180+50);
ptr[2]=(uchar)(cvRandInt(&rng)%180+50);
}
cv::Mat temp=g_markers.clone();
double t=(double)cvGetTickCount();
//my_watershed(img0,g_markers,comp_count);
cv::watershed(img0,g_markers);
t=(double)cvGetTickCount()-t;
std::cout<<"exec time= "<<t/(cvGetTickFrequency()*1000.)<<std::endl;
for(int i=0;i<g_markers.rows;i++)
for(int j=0;j<g_markers.cols;j++)
{
int idx=g_markers.at<int>(i,j);
uchar* dst=&wshed.at<uchar>(i,j*3);
if(idx==-1)
dst[0]=dst[1]=dst[2]=(uchar)255;
else if(idx<=0||idx>comp_count)
dst[0]=dst[1]=dst[2]=(uchar)8;
else{
uchar* ptr=color_tab->data.ptr+(idx-1)*3;
dst[0]=ptr[0];dst[1]=ptr[1];dst[2]=ptr[2];
}
}
cv::addWeighted(wshed,0.5,img_gray,0.5,0,wshed);
cv::imshow("watershed transform",wshed);
cvReleaseMat(&color_tab);
}
}
return 0;
}
static void my_watershed(cv::Mat img0,cv::Mat& markers,int comp_count)
{
cv::Mat gray=cv::Mat(cv::Size(img0.rows,img0.cols),8,1);
cv::cvtColor(img0,gray,CV_BGR2GRAY);
cv::Mat imge=cv::Mat(cv::Size(img0.rows,img0.cols),8,1);
cv::Sobel(gray,imge,CV_8U,1,1);
vector<queue<cv::Point2i>*>Labeleddata;//图像中各连通区域的点
queue<cv::Point2i>* pque;//某连通区域已包含的点
queue<cv::Point2i> quetem; //用于提取某连通区域中输入种子点中的初始种子点
vector<int*> SeedCounts;
int* Array;
cv:: Point2i temp;
int row=imge.rows,col=imge.cols;
cv::Mat marker_saved=markers.clone();
bool up,down,right,left,uplef,uprig,downlef,downrig;
int m,n;
for(int i=0;i<comp_count;i++)
{
Array=new int[256];
SeedCounts.push_back(Array);//统计某waterlevel的各个连通区域中种子点的个数
pque=new queue<cv::Point2i>[256];
Labeleddata.push_back(pque);//存储该连通区域中种子生长所得的点
}
for(int i=0;i<row;i++)
for(int j=0;j<col;j++)
{
if(markers.at<int>(i,j)>0)
{
temp.x=i;
temp.y=j;
quetem.push(temp);
int num=markers.at<int>(i,j);
markers.at<int>(i,j)=-1;//该点已处理,其他种子点生长时将绕过该点
while(!quetem.empty())
{
up=down=right=left=uplef=uprig=downlef=downrig=false;
temp=quetem.front(); //提取出一个点，在该点的八连通区域内寻找可生长点
m=temp.x;
n=temp.y;
quetem.pop();
if(m-1>=0)//若上方可生长则添加为新种子
{
if(markers.at<int>(m-1,n)==num)
{
temp.x=m-1;
temp.y=n;
quetem.push(temp);
markers.at<int>(m-1,n)=-1;
}
else{
up=true;
}
}
if(m-1>=0&&n-1>=0)
{
if(markers.at<int>(m-1,n-1)==num)
{
temp.x=m-1;
temp.y=n-1;
quetem.push(temp);
markers.at<int>(m-1,n-1)=-1;
}
else{
uplef=true;
}
}
if(m+1<=row-1)
{
if(markers.at<int>(m+1,n)==num)
{
temp.x=m+1;
temp.y=n;
quetem.push(temp);
markers.at<int>(m+1,n)=-1;
}
else{
down=true;
}
}
if(m+1<=row-1&&n+1<=col-1)
{
if(markers.at<int>(m+1,n+1)==num)
{
temp.x=m+1;
temp.y=n+1;
quetem.push(temp);
markers.at<int>(m+1,n+1)=-1;
}
else{
downrig=true;
}
}
if(n+1<=col-1)
{
if(markers.at<int>(m,n+1)==num)
{
temp.x=m;
temp.y=n+1;
quetem.push(temp);
markers.at<int>(m,n+1)=-1;
}
else{
right=true;
}
}
if(m-1>=0&&n+1<=col-1)
{
if(markers.at<int>(m-1,n+1)==num)
{
temp.x=m-1;
temp.y=n+1;
quetem.push(temp);
markers.at<int>(m-1,n+1)=-1;
}
else{
uprig=true;
}
}
if(n-1>=0)
{
if(markers.at<int>(m,n-1)==num)
{
temp.x=m;
temp.y=n-1;
quetem.push(temp);
markers.at<int>(m,n-1)=-1;
}
else{
left=true;
}
}
if(m+1<=row-1&&n-1>=0)
{
if(markers.at<int>(m+1,n-1)==num)
{
temp.x=m+1;
temp.y=n-1;
quetem.push(temp);
markers.at<int>(m+1,n-1)=-1;
}
else{
downlef=true;
}
}
//八连通区域中有未标记点，则该点属于初始种子点
if(up||down||right||left||uplef||downlef||uprig||downrig)
{
temp.x=m;
temp.y=n;
Labeleddata[comp_count-1][imge.at<uchar>(m,n)].push(temp);
SeedCounts[comp_count-1][imge.at<uchar>(m,n)]++;
}
}
}
}
bool active;
int waterlevel;
for(waterlevel=0;waterlevel<180;waterlevel++)
{
active=true;
while(active) //当1-count_com个连通区域都无可生长点时结束循环
{
active=false;
for(int i=0;i<comp_count;i++)//将区域i中将waterlevel梯度以下的点用于区域增长
{
//区域增长，经过多次迭代，直至该区域，该waterlevel无可生长点。
if(!Labeleddata[i][waterlevel].empty())
{
active=true;
//SeedCount中保留了前一轮生长后各区域，各waterlevel的种子点个数，
//本轮生长结束后，将根据Labeleddata中的元素个数更新
while(SeedCounts[i][waterlevel]>0)
{
SeedCounts[i][waterlevel]--;
temp=Labeleddata[i][waterlevel].front();
Labeleddata[i][waterlevel].pop();
m=temp.x;
n=temp.y;
int num=marker_saved.at<int>(m,n);
if(m-1>=0)
{
if(!marker_saved.at<int>(m-1,n))//上方点未处理过
{
temp.x=m-1;
temp.y=n;
marker_saved.at<int>(m-1,n)=num;
if(imge.at<uchar>(m-1,n)<=waterlevel)
Labeleddata[i][waterlevel].push(temp);
else{
//本次生长不处理，可能在waterlevel变化到某值时再用于生长
Labeleddata[i][imge.at<uchar>(m-1,n)].push(temp);
SeedCounts[i][imge.at<uchar>(m-1,n)]++;
}
}
}
if(m+1<=row-1)
{
if(!marker_saved.at<int>(m+1,n))
{
temp.x=m+1;
temp.y=n;
marker_saved.at<int>(m+1,n)=num;
if(imge.at<uchar>(m+1,n)<=waterlevel)
Labeleddata[i][waterlevel].push(temp);
else{
Labeleddata[i][imge.at<uchar>(m+1,n)].push(temp);
SeedCounts[i][imge.at<uchar>(m+1,n)]++;
}
}
}
if(n+1<=col-1)
{
if(!marker_saved.at<int>(m,n+1))
{
temp.x=m;
temp.y=n+1;
marker_saved.at<int>(m,n+1)=num;
if(imge.at<uchar>(m,n+1)<=waterlevel)
Labeleddata[i][waterlevel].push(temp);
else{
Labeleddata[i][imge.at<uchar>(m,n+1)].push(temp);
SeedCounts[i][imge.at<uchar>(m,n+1)]++;
}
}
}
if(n-1>=0)
{
if(!marker_saved.at<int>(m,n-1))
{
temp.x=m;
temp.y=n-1;
marker_saved.at<int>(m,n-1)=num;
if(imge.at<uchar>(m,n-1)<=waterlevel)
Labeleddata[i][waterlevel].push(temp);
else
{
Labeleddata[i][imge.at<uchar>(m,n-1)].push(temp);
SeedCounts[i][imge.at<uchar>(m,n-1)]++;
}
}
}
}
SeedCounts[i][waterlevel]=Labeleddata[i][waterlevel].size();
}
}
}
}
markers=marker_saved.clone();
}
参考：
https://blog.csdn.net/qingyafan/article/details/44260817
https://blog.csdn.net/twowind/article/details/8988282
版权声明：本文为yohnyang原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。