分水岭算法

感觉网上的文字介绍写的都太抽象了，自己根据维基百科和英文论文记一下自己原理方面的具体理解。

非常抽象的原理理解

参考链接：meduim上的一篇文章
大部分文章都用这段来进行抽象地比喻和解释的
这段大意就是different valleys start to merge的位置修建barrier，就是分割线。

In any grayscale images, there are areas where the intensity is high and there are some where intensity is low. We can denote these high intensity areas to peaks while low intensity areas to valleys. Think of an image as a topography map, where each pixel’s intensity contributes to the topography map, either a local elevation or a depression. To separate objects in images, we will fill out each valley with water of different colors. Slowly, the water will rise up and to a point water from different valleys start to merge. This is when we build barriers on top of the peak to avoid having the peak underwater. Once the barriers are built out, the barriers constitutes the boundary of the object.

改进：基于标记的分水岭算法

传统分水岭方法（在grayscale image上去找极小值，然后开始扩张）的不足：基于图像梯度的分水岭算法由于存在太多极小区域而产生许多小的集水盆地，带来的结果就是图像过分割。
所以必须对分割相似的结果进行合并。举个例子如一个桌面的图片，由于光照、纹理等因素，桌面会有很多明暗变化，反映在梯度图上就是一个个圈，此时利用分水岭算法就会出现很多小盆地，从而分割出很多小区域。但这显而易见是不符合常识的。因为桌面是一个整体，应该属于同一类，而不是因为纹理而分成不同的部分。

因此需要对分水岭算法进行改进。在OpenCV中采用的是基于标记的分水岭算法。水淹过程从预先定义好的标记图像（像素）开始，这样可以减少很多极小值点盆地产生的影响。较好的克服了过度分割的不足。本质上讲，基于标记点的改进算法是利用先验知识来帮助分割的一种方法。

图示如下：

对比图

举例：opencv中基于标注的分水岭算法

经典的一个硬币分割的例子，涉及到前景的标记marker

Otsu’s binarization二值化
开闭运算：（容易理解的）

Erosion（腐蚀）：确保白色的部分都是foreground（sure foreground area）
另一种确定前景的方法是距离变换加上合适的阈值。
代码如下：

Dilation（膨胀）：确保黑色的部分都是background（sure background area）
剩下的不确定是前景还是背景的部分就需要watershed algorithm来解决。
Note1:
提取肯定是硬币的区域(前景)，可以使用腐蚀操作。腐蚀操作可以去除边缘像素，剩下就可以肯定是硬币了。当硬币之间没有接触时，这种操作是有效的。但是由于硬币之间是相互接触的，我们就有了另外一个更好的选择：距离变换再加上合适的阈值。（代码如下）
Note2:
注意对图像可以取补集，因为这样可以确保背景比前景暗（这样看上去舒服一些）。

#这里的open就是二值化去噪后的图像
distance_transform = cv2.distanceTransform(open, 1, 5)
ret, sure_fg = cv2.threshold(distance_transform, 0.7 * distance_transform.max(), 255, cv2.THRESH_BINARY)
>These areas are normally around the boundaries of coins where foreground and background meet (Or even two different coins meet). We call it border. 
*It can be obtained from subtracting sure_fg area from sure_bg area.*

图像提取

watershed前的标记工作：

# Marker labelling 标记sure的前景
ret, markers = cv2.connectedComponents(sure_fg)

# Add one to all labels so that sure background is not 0, but 1 标记sure的背景
markers = markers+1

# Now, mark the region of unknown with zero 标记为止的部分
markers[unknown==255] = 0

watershed前的准备

应用分水岭算法找到分界线并把边界加在原图上

markers = cv2.watershed(img,markers)
img[markers == -1] = [255,0,0]

下面聊一聊具体算法实现吧。
不错的参考链接
没有用到什么数学知识，就是根据上面的抽象理解来写代码：valley部分的连通区域的扩张。

MATLAB二值化图像的分水岭算法

参考链接
在MATLAB里，需要用到bwdist这个函数来求 the distance transform of the complement of the binary image。即valley中每个点（标记pixel value为0）到其对应最近的非零点的距离。（我的理解：这一步的作用是把二值图像灰度化，这样就有梯度了，有谷底，从谷底开始扩张涨水位。）

distance transform的结果

不错的实现代码：
MATLAB分水岭实现代码

【随笔-2】非常详细的分水岭算法（watershed algorithm）及其改进