传统图像分割——分水岭算法（watershed）

---

---

前言

本篇文章主要梳理分水岭算法的原理，不涉及编程实现
一些经典的分水岭算法文献：

• [1] Vincent L, Soille P. Watersheds in digital spaces: an efficient algorithm based on immersion simulations[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 1991, 13(06): 583-598.
• [2] Roerdink J B T M, Meijster A. The watershed transform: Definitions, algorithms and parallelization strategies[J]. Fundamenta informaticae, 2000, 41(1, 2): 187-228.
• [3] Najman L, Schmitt M. Watershed of a continuous function[J]. Signal Processing, 1994, 38(1): 99-112.

Matlab代码可参考使用教程：

• https://ww2.mathworks.cn/help/images/marker-controlled-watershed-segmentation.html?s_tid=gn_loc_drop

---

一、什么是分水岭算法？

传统分水岭算法是一种基于拓扑理论的形态学分割方法。通常在基于形态学分割的方法中，会将图片视作地形表面，将图片的每一个灰度级与等高线相对应。由此，图片的每一个局部最小值都会有一个影响区域（influence zone）这些影响区域的边界被称为“分水岭”（相当于是寻找波峰线）这样做的好处在于对于图片梯度的估计非常直接，便于寻找图像的梯度波峰，用于分割。
下图所示为分水岭的一维示意图。更直观一点来讲，首先戳漏每一个局部最小值点，然后水从下到上漫延会逐渐淹没$B{V}_i$这些影响区域（图(a)，也被称为吸水盆地，注意这些不同的吸水盆地内水的高度是一致的）；而随着水位继续上涨中间的小峰值也会被淹没，为了不让两个不同的影响区域合并会建立一个水坝（图(b)中Barrage），这些水坝就是“地形图”的分水岭，也可以想象为图形的边缘。

而对于图像分割任务这种二维的情况，分水岭更难获取，二维的情况如下图所示（分水岭为图中Dam）

---

二、经典的分水岭求解算法

1.定义

• 测地线距离（geodesic distance）：对于一个集合$A$，$a$,$b$为$A$中的两个元素，则定义在$A$中连接$a$与$b$的路径长度的最小值为测地线距离，记作$d_A(a,b)$。具体来讲，如下图所示两个黑点之间的测地线距离为$d_{12}+d_{23}+d_{34}+d_{45}$。在三维曲面空间中两点间的测地距离就是两点间沿着三维曲面的表面走的最短路径。
  

• 测地线影响区域（geodesic influence zone）：对于$A$中的一个点$B_i$，所有与点$B_i$的测地线距离小于距离其他点$B_j$距离的点的集合，即 i z A ( B i ) = { p ∈ A , ∀ j ∈ [ 1 : i − 1 , i + 1 : k ] , d A ( p , B i ) < d A ( p , B j ) } iz_A(B_i)=\{p \in A,\forall j \in [1:i-1,i+1:k],d_A(p,B_i)<d_A(p,B_j)\} izA​(Bi​)={p∈A,∀j∈[1:i−1,i+1:k],dA​(p,Bi​)<dA​(p,Bj​)}

• 集水盆地（catchment basins）：对于数值图像$I$，定义$h_{min}$是图像$I$最小的灰度级，$T_h(I)$是图像$I$中所有灰度级小于等于$h$的像素点，$Mi{n}_h$是图像$I$在灰度级$h$处区域最小值的集合，进而可以通过递归求解得到集合$X_{h_{max}}$。$$X_{h_{min}}=T_{h_{min}}(I)$$ $$\forall h\in [h_{min},h_{max}-1],X_{h+1}=Mi{n}_{h+1}\cup I{Z}_{T_{h+1}(I)}(X_h)$$

2.算法流程

• 首先，把梯度图像中所有的像素按照灰度值分类，并设定一个测地线距离阈值
• 其次，找到灰度值最小的像素点（即$h_{min}$），让阈值从最小值开始增长（$h_{min}+1$,…,$h_{max}$），在增长的过程中计算$h_{min}$与像素点的测地线距离，如果小于设定阈值，则将这些像素淹没，否则在这些像素上设置大坝，这样就对这些邻域像素进行了分类。

示意图如下[4]

[4]摘自https://zhuanlan.zhihu.com/p/67741538
[5]一个讲的比较清晰的视频：https://www.bilibili.com/video/BV1fk4y167Gv?spm_id_from=333.337.search-card.all.click&vd_source=4242990e0fbe2c9c04876ca373dbce12

---

总结

可以看到传统分水岭算法计算量大，并且阈值的选取与灰度级的数量都会影响到分割效果，另外分水岭算法处理复杂图像的效果可能会差。