OpenCV3学习（7.2）——图像分割之二（分水岭算法watershed）
分水岭算法 原理
分水岭算法是一种图像区域分割法，在分割的过程中，它会把跟临近像素间的相似性作为重要的参考依据，从而将在空间位置上相近并且灰度值相近的像素点互相连接起来构成一个封闭的轮廓，封闭性是分水岭算法的一个重要特征。其他图像分割方法，如阈值，边缘检测等都不会考虑像素在空间关系上的相似性和封闭性这一概念，彼此像素间互相独立，没有统一性。分水岭算法较其他分割方法更具有思想性，更符合人眼对图像的印象。
分水岭算法主要用于图像分段，通常是把一副彩色图像灰度化，然后再求梯度图，最后在梯度图的基础上进行分水岭算法，求得分段图像的边缘线，就是根据把图像比作一副地貌，然后通过最低点和最高点去分类！地形的高度是由灰度图的灰度值决定，灰度为0对应地形图的地面，灰度值最大的像素对应地形图的最高点。
对灰度图的地形学解释，我们我们考虑三类点：
1. 局部最小值点，该点对应一个盆地的最低点，当我们在盆地里滴一滴水的时候，由于重力作用，水最终会汇聚到该点。注意：可能存在一个最小值面，该平面内的都是最小值点。
2. 盆地的其它位置点，该位置滴的水滴会汇聚到局部最小点。
3. 盆地的边缘点，是该盆地和其它盆地交接点，在该点滴一滴水，会等概率的流向任何一个盆地。
假设我们在盆地的最小值点，打一个洞，然后往盆地里面注水，并阻止两个盆地的水汇集，我们会在两个盆地的水汇集的时刻，在交接的边缘线上(也即分水岭线)，建一个坝，来阻止两个盆地的水汇集成一片水域。这样图像就被分成2个像素集，一个是注水盆地像素集，一个是分水岭线像素集。
原始的分水岭步骤：
第一步：找到图像的局部最低点，这个方法很多了，可以用一个内核去找，也可以一个一个比较，实现起来不难。
第二步：从最低点开始注水，水开始网上满（图像的说法就是梯度法），其中那些最低点已经被标记，不会被淹没，那些中间点是被淹没的。
第三步：找到局部最高点，就是图中3位置对应的两个点。
第四步：这样基于局部最小值，和找到的局部最大值，就可以分割图像了。
下面的gif图很好的演示了分水岭算法的效果：
opencv改进的分水岭算法：
在真实图像中，由于噪声点或者其它干扰因素的存在，使用分水岭算法常常存在过度分割的现象，这是因为很多很小的局部极值点的存在，比如下面的图像，这样的分割效果是毫无用处的。
为了解决过度分割的问题，可以使用基于标记(mark)图像的分水岭算法，就是通过先验知识，来指导分水岭算法，以便获得更好的图像分段效果。通常的mark图像，都是在某个区域定义了一些灰度层级，在这个区域的洪水淹没过程中，水平面都是从定义的高度开始的，这样可以避免一些很小的噪声极值区域的分割。
下面的gif图很好的演示了基于mark的分水岭算法过程：
上面的过度分段图像，我们通过指定mark区域，可以得到很好的分段效果
分水岭算法opencv实现
函数原型：
void watershed( InputArray image, InputOutputArray markers );第一个参数 image，必须是一个8bit 3通道彩色图像矩阵序列
第二个参数 markers，在执行分水岭函数watershed之前，必须对第二个参数markers进行处理，它应该包含不同区域的轮廓，每个轮廓有一个自己唯一的编号，轮廓的定位可以通过Opencv中findContours方法实现，这个是执行分水岭之前的要求。markers必须包含了种子点信息。Opencv官方例程中使用鼠标划线标记来定义种子，而使用findContours 可以自动标记种子点。而分水岭方法完成之后并不会直接生成分割后的图像，还需要进一步的显示处理。
算法会根据markers传入的轮廓作为种子（也就是所谓的注水点），对图像上其他的像素点根据分水岭算法规则进行判断，并对每个像素点的区域归属进行划定，直到处理完图像上所有像素点。而区域与区域之间的分界处的值被置为“-1”，以做区分。
（初始阶段：把每个标记的所有邻居像素放到有序队列中去，以确定聚水盆的初始边界， 即每个标记（种子，全为正值，1,2,3...）都是一个初始聚水盆，标记的周围一圈的邻居像素就是聚水盆的初始边界，这里用的是一种逆向思维，不是找标记点，而是判断每一个点是否为标记点的邻居,若是，则该点也被扩充为与标记点同类型的标记点， 若是多个标记点的邻居，选择梯度最小的标记点的类型，作为该点的标记点类型。）
markets创建主要有两种方式：手动选取和findContours
手动选取：
要创建mark图像。mark图像格式是有符号整数，其中没有被mark的部分用0表示，其它不同区域的mark标记，我们用非零值表示，通常为1-255，不同mark区域用不同的值表示，这样能够确保结果正确，之所以用有符号整数，是因为opencv在分水岭算法内部，要用-1，-2等来标记注水区域，最终在mark图像中生成的分水岭线就是用-1表示。
我们通常会创建uchar格式的灰度图，指定mark区域，然后转化为有符号整数的图像格式。
首先对整个背景区域我们创建一个mark域，是下图中白色框框住的部分，其灰度值为255，第二个选择mark域为塔，就是黑色框框住的一块区域，其灰度值为64，最后就是树mark域，蓝色框的部分，其灰度值为128。在分水岭算法时候，会分别对这个3个区域来进行注水操作，如果两个注水盆地被一个mark域覆盖，则它们之间不会有分水岭线产生。
对于mark图像，opencv分水岭算法在初始化时候，会把最外圈的值置为-1，作为整个图像的边界，所以我们第一个mark区域，选择倒数第2外圈，因为设置到最外圈，最后还是会被冲掉。
// 标示背景图像
cv::Mat imageMask(image.size(),CV_8U,cv::Scalar(0));
cv::rectangle(imageMask,cv::Point(1,1),cv::Point(image.cols-2,image.rows-2),cv::Scalar(255),1);
// 表示塔
cv::rectangle(imageMask,cv::Point(image.cols/2-10,image.rows/2-10),
cv::Point(image.cols/2+10,image.rows/2+10),cv::Scalar(64),10);
//树
cv::rectangle(imageMask,cv::Point(64,284),
cv::Point(68,300),cv::Scalar(128),5); 初始的mark图像数据如下，黄色的部分为我们的第一个mark区域，值为255，第二个区域为褐红色的区域，值为128，第三个绿色的区域，值为64。
注意：mark图像是32bit的有符号整数，所以在使用分水岭算法前，我们先对mark图像做一个转化。算法执行完后，再转化为0-255的灰度图。
imageMask.convertTo(imageMask,CV_32S);
// 设置marker和处理图像
cv::watershed(image,imageMask);
cv::Mat mark1;
imageMask.convertTo(mark1,CV_8U); imageMask作为输出。此时imageMask图像从无符号整数转化为uchar后，如下图所示，第一个mask区域注水，将会使得整个图像为白色，之后分别在第二个，第三个区域的盆地注水，会产生相应的注水图，注水的区域的值即为mark的值，128和64, 分水岭线则为0，注：在转化前分水岭线的值为-1，转化后成为0。
(注水区域的颜色就是包围该区域的轮廓的颜色)
opencv中分水岭算法的具体实现方式可参考：https://yq.aliyun.com/articles/325556
findContours
（opencv官方教程中使用鼠标选中区域，也是采用find Contours找到标记轮廓，对于标记的原则：你认为它们属于一个区域，就用标记将它们连接起来，对于另一个区域，再用另一个标记连接。就像这样
图片做了三个标记。之后就是对标记掩膜（不是上面的做过标记的图像）进行findContours，进行后续操作。
maskImage = Mat(srcImage.size(), CV_8UC1); // 掩模，在上面做标记，然后传给findContours，srcImage.表示原图
line(maskImage, clickPoint, point, Scalar::all(255), 5, 8, 0);//做标记，白线
对maskImage进行findContours
可参考：https://blog.****.net/sugarannie/article/details/53080168
先介绍一下findContours函数，函数原型：
void findContours( InputOutputArray image, OutputArrayOfArrays contours,
OutputArray hierarchy, int mode,
int method, Point offset=Point());
//! retrieves contours from black-n-white image.
void findContours( InputOutputArray image, OutputArrayOfArrays contours,
int mode, int method, Point offset=Point());第一个参数：image，单通道图像矩阵，可以是灰度图，但更常用的是二值图像，一般是经过Canny、拉普拉斯等边缘检测算子处理过的二值图像；
第二个参数：contours，定义为“vector<vector<Point>> contours”，是一个向量，向量内每个元素保存了一组由连续的Point点构成的点的集合的向量，一个元素包含一组Point点集，就是一个轮廓。 有多少轮廓，向量contours就有多少元素。
第三个参数：hierarchy，定义为“vector<Vec4i> hierarchy”，hierarchy也是一个向量，向量内每个元素保存了一个包含4个int整型的数组。向量hiararchy内的元素和轮廓向量contours内的元素是一一对应的，向量的容量相同。 hierarchy向量内每一个元素的4个int型变量——hierarchy[i][0] ~hierarchy[i][3]，分别表示第 i个轮廓的后一个轮廓、前一个轮廓、父轮廓、内嵌轮廓的索引编号。如果当前轮廓没有对应的后一个轮廓、前一个轮廓、父轮廓或内嵌轮廓的话，则hierarchy[i][0] ~hierarchy[i][3]的相应位被设置为
默认值-1。
第四个参数：int型的mode，定义轮廓的检索模式：
取值一：CV_RETR_EXTERNAL只检测最外围轮廓，包含在外围轮廓内的内围轮廓被忽略
取值二：CV_RETR_LIST 检测所有的轮廓，包括内围、外围轮廓，但是检测到的轮廓不建立等级关系，彼此之间独立，没有等级关系，这就意味着这个检索模式下不存在父轮廓或内嵌轮廓， 所以hierarchy向量内所有元素的第3、第4个分量都会被置为-1。
取值三：CV_RETR_CCOMP 检测所有的轮廓，但所有轮廓只建立两个等级关系，外围为顶层，若外围内的内围轮廓还包含了其他的轮廓信息，则内围内的所有轮廓均归属于顶层
取值四：CV_RETR_TREE， 检测所有轮廓，所有轮廓建立一个等级树结构。外层轮廓包含内层轮廓，内层轮廓还可以继续包含内嵌轮廓。
第五个参数：int型的method，定义轮廓的近似方法：
取值一：CV_CHAIN_APPROX_NONE 保存物体边界上所有连续的轮廓点到contours向量内
取值二：CV_CHAIN_APPROX_SIMPLE 仅保存轮廓的拐点信息，把所有轮廓拐点处的点保存入contours 向量内，拐点与拐点之间直线段上的信息点不予保留
取值三和四：CV_CHAIN_APPROX_TC89_L1，CV_CHAIN_APPROX_TC89_KCOS使用teh-Chinl chain 近似算法
第六个参数：Point偏移量，所有的轮廓信息相对于原始图像对应点的偏移量，相当于在每一个检测出的轮廓点上加上该偏移量，并且Point还可以是负值！
from：https://blog.****.net/dcrmg/article/details/51987348
绘制轮廓drawContours函数：
void drawContours( InputOutputArray image, InputArrayOfArrays contours,
int contourIdx, const Scalar& color,
int thickness=1, int lineType=8,
InputArray hierarchy=noArray(),
int maxLevel=INT_MAX, Point offset=Point() ); InputOutputArray image,//要绘制轮廓的图像
InputArrayOfArrays contours,//所有输入的轮廓，每个轮廓被保存成一个point向量
int contourIdx,//指定要绘制轮廓的编号，如果是负数，则绘制所有的轮廓
const Scalar& color,//绘制轮廓所用的颜色
int thickness = 1, //绘制轮廓的线的粗细，如果是负数，则轮廓内部被填充
int lineType = 8, /绘制轮廓的线的连通性
InputArray hierarchy = noArray(),//关于层级的可选参数，只有绘制部分轮廓时才会用到
int maxLevel = INT_MAX,//绘制轮廓的最高级别，这个参数只有hierarchy有效的时候才有效
//maxLevel=0，绘制与输入轮廓属于同一等级的所有轮廓即输入轮廓和与其相邻的轮廓
//maxLevel=1, 绘制与输入轮廓同一等级的所有轮廓与其子节点。
//maxLevel=2，绘制与输入轮廓同一等级的所有轮廓与其子节点以及子节点的子节点
Point offset = Point()
分水岭算法实现图像自动分割的步骤：
- 图像灰度化、Canny边缘检测
- 查找轮廓，并且把轮廓信息按照不同的编号绘制到watershed的第二个参数markers上，相当于标记注水点。
- watershed分水岭算法
- 绘制分割出来的区域，然后使用随机颜色填充，再跟源图像融合，以得到更好的显示效果。
第3步，watershed分水岭算法的具体实现方式：
原始图像和Mark图像，它们的大小都是32*32，分水岭算法的结果是得到两个连通域的轮廓图。
原始图像：(原始图像必须是3通道图像) Mark图像： 结果图像：
初始的mark图像数据如下，黄色的部分为我们的第一个mark区域，值为255，第二个区域为褐红色的区域，值为128，第三个绿色的区域，值为64。
opencv分水岭算法描述如下：
初始化mark矩阵，生成最初的注水区域。
1.设置mark图像的边框值为-1
2. 标记每个mark区域的边界为-2
3. 对于mark图像一个像素值，如果它本身值为0，但上下左右四邻域有一个像素值不为0，则把该点按照RGB高度值放入相应的队列。
举例说明：如下图像素点，它的mark值为0，但左和上像素值不为0，此时，我们求原始图像中对应像素的高度值，高度值的计算方式如下面公式，其中R表示Red通道值，G表示Green通道值，B表示Blue通道值，下标L表示左，R表示右，T表示上，B表示下，abs表示取绝对值，min和max分别为最小值和最大值函数：
min(max(abs(R-RL), abs(G-GL), abs(B-BL))，
max(abs(R-RT), abs(G-GT), abs(B-BT))，
max(abs(R-RR), abs(G-GR), abs(B-BR))，
max(abs(R-RB), abs(G-GB), abs(B-BB)) ）
上图中指定的像素，它的高度值显然为0，所以我们把(2，2)点放入高度为0的队列中(总共有256个队列，对应0-255的高度)
初始化阶段完成后，我们得到下面的mark图，并把-2对应的边界像素点，按照其对应的RGB高度值放入相应的队列。
之后就进入了递归注水过程，递归过程描述如下（没看懂？？？）：
for(; ; )
{
扫描0-255高度值队列，
如果找到一个像素标记，则弹出该标记，并退出扫描。
如果该像素的四邻域中存在两个不同的非0值，表示该点为两个注水盆地的边缘，即分水岭线，在mark图像中标记该点为-1。
扫描该点的四邻域，是否存在为0的mark域，存在的话把该邻域点按照rgb高度值，放入相应的队列。
}
经过上述的递归过程，最后我们得到的mark图像如下所示，其中绿色格子的-1即为所有的分水岭边界：
from：https://yq.aliyun.com/articles/325556
经过灰度化、滤波、边缘检测、findContours轮廓查找、轮廓绘制等步骤后终于得到了符合Opencv要求的markers，我们把markers转换成8bit单通道灰度图看看它里边到底是什么内容：
findContours检测并绘制到的轮廓和分水岭运算前的markers：
仔细观察就能发现，marksshow图像上不同线条的灰度值是不同的，底部略暗，越往上灰度越高。
看一下代码即知（为每个轮廓设置不同的灰度值主要是为了区分出轮廓，每一个线条代表了一个种子，线条的不同灰度值其实代表了对不同注水种子的编号，有多少不同灰度值的线条，就有多少个种子，图像最后分割后就有多少个区域。）：
drawContours(marks, contours, index, Scalar::all(compCount +1), 1, 8, hierarchy);
drawContours(imageContours, contours, index, Scalar(255), 1, 8, hierarchy);
// 我们来看一下传入的矩阵marks里是什么东西
convertScaleAbs(marks, marksShows);
imshow("marksShow", marksShows);运行分水岭算法后markers变为：
可以看到，执行完watershed之后，merkers里边被分割出来的区域已经非常明显了，空间上临近并且灰度值上相近的区域被划分为一个区域，灰度值是一样，不同区域间被划分开，这其实就是分水岭对图像的分割效果了。
源码：
#include<opencv2\highgui\highgui.hpp>
#include<opencv2\imgproc\imgproc.hpp>
#include<iostream>
#include <opencv2\opencv.hpp>
#include <math.h>
using namespace cv;
using namespace std;
Vec3b RandomColor(int value);
int main() {
Mat imggray;
Mat img = imread("122.png", 1);
cvtColor(img, imggray, CV_RGB2GRAY);
GaussianBlur(imggray, imggray, Size(3, 3), 2);
Canny(imggray, imggray, 80, 140);
vector<vector<Point>> contours;
vector<Vec4i> hierarchy;
findContours(imggray,contours,hierarchy,RETR_TREE, CHAIN_APPROX_SIMPLE, Point());
Mat imageContours = Mat::zeros(img.size(), CV_8UC1); //轮廓
Mat marks(img.size(), CV_32S, Scalar::all(0)); //Opencv分水岭第二个矩阵参数
int index = 0;
int compCount = 0;
for (; index >= 0; index = hierarchy[index][0], compCount++)
{
//对marks进行标记，对不同区域的轮廓进行编号，相当于设置注水点，有多少轮廓，就有多少注水点
drawContours(marks, contours, index, Scalar::all(compCount +1), 1, 8, hierarchy);
drawContours(imageContours, contours, index, Scalar(255), 1, 8, hierarchy);
}
// 我们来看一下传入的矩阵marks里是什么东西
Mat marksShows;
convertScaleAbs(marks, marksShows);
imshow("marksShow", marksShows);
imshow("轮廓", imageContours);
watershed(img, marks);
Mat afterWatershed;
convertScaleAbs(marks, afterWatershed);//将图片转化成为8位图形进行显示
imshow("After Watershed", afterWatershed);
//对每一个区域进行颜色填充
Mat PerspectiveImage = Mat::zeros(img.size(), CV_8UC3);
for (int i = 0; i<marks.rows; i++)
{
for (int j = 0; j<marks.cols; j++)
{
int index = marks.at<int>(i, j);
if (marks.at<int>(i, j) == -1)
{
PerspectiveImage.at<Vec3b>(i, j) = Vec3b(255, 255, 255);
}
else
{
PerspectiveImage.at<Vec3b>(i, j) = RandomColor(index);
}
}
}
imshow("After ColorFill", PerspectiveImage);
//分割并填充颜色的结果跟原始图像融合
Mat wshed;
addWeighted(img, 0.4, PerspectiveImage, 0.6, 0, wshed);
imshow("AddWeighted Image", wshed);
waitKey(0);
}
Vec3b RandomColor(int value) //生成随机颜色函数</span>
{
value = value % 255; //生成0~255的随机数
RNG rng;
int aa = rng.uniform(0, value);
int bb = rng.uniform(0, value);
int cc = rng.uniform(0, value);
return Vec3b(aa, bb, cc);
}OpenCV 源码中分水岭算法 watershed 函数源码注解：https://blog.****.net/u011375993/article/details/46793655
from：https://www.cnblogs.com/wjy-lulu/p/7056466.html
from：https://blog.****.net/dcrmg/article/details/52498440