8.4.2 分水岭算法的数学描述
根据分水岭算法就是通过水不断溢出淹没地貌的思路，对分水岭算法进行算法的数学描述。假设一幅需要分割的灰度图像f(x，y)，梯度图像为g(x，y)，图像中局部极小值点的位置用M1，M2，M3，…，MR表示。min和max表示梯度图中灰度的最小值和最大值。C(Mi)为极小值点Mi对应的积水盆点的集合，溢流过程是以单灰度值增加的，令n 为当前溢流的深度，T[n]表示g(u，v)＜n像素点的集合，即：
图8.31 分水岭算法处理过程图
(a)原始图像；(b)地形俯视图；(c)开始浸没；(d)积水盘的水逐渐汇聚；
(e)不断汇聚(已有分水岭)；(f)分水岭形成图
水流从灰度最小值处开始溢出，随着每次淹没过程中溢流深度从n 变为n+1，需要统计处在平面g(u，v)=n 下面的像素点集合T[n]。而对于每个局部极小值点Mi所在区域，处在平面g(u，v)=n 下面的像素点集合记为Cn(Mi)，计算公式为：
此公式说明可以用“与”操作将对应于Mi所在区域的那些小于n 的像素点提取出来。图8.32给出了上面给出的各个概念的直观解释，由图可以看出Cn(Mi)可以由C(Mi)和T[n]求并集得出，同理Cn(Mi+1)可以由C(Mi+1)和T[n]求并集得出。
若用C[n]表示溢流深度是n 时所有满足像素值小于n 的像素集合，C[n]计算方法如下：
则C[max+1]表示所有区域像素点的并集，计算方法如下：
(https://www.daowen.com)
图8.32 计算Cn(Mi+1) 示意图
在水平面不断增高的过程中，集合Cn(Mi)与T[n]中的像素会一直属于原集合，而随着n的增加，这两个集合中的像素个数是单调函数。容易知道C[n-1]是C[n]的子集，可得C[n]是T[n]的子集，三者之间的关系可以用如下公式表示：
由上面公式可知，每个C[n-1]中的连通组元都包含在T[n]的连通主元中。
分水岭算法开始进行初始化时，令C[min+1]=T[min+1]，然后利用迭代运算计算出溢流深度n 增加时的结果。假设在步骤n 时已经计算出C[n-1]的结果，要从该结果结算出C[n]，可以令S 代表T[n]中连通区域的集合，集合中每个连通区域s∈S[n]和C[n-1]存在三种关系：
关系1：s∩C[n-1]的结果为空集。
关系2：s∩C[n-1]的结果含有C[n-1]中一个连通区域。
关系3：s∩C[n-1]的结果含有C[n-1]中一个以上的连通区域。
对应三种关系的示意图如图8.33所示。
图8.33 计算C［n］ 的示意图
C[n]的计算过程和建立分水岭的时间都与上述关系中的某种关系成立有关。关系1表明随着n的增加，水平面遇到了新的局部极小值点，因此只要把新的连通区域s加入到C[n-1]就可以得到C[n]；关系2表明连通区域s只属于某个极小值区域，各局部极小值溢出的水并没有流进其他积水盆，此时只要把s加入到C[n-1]就可以得到C[n]；关系3表明水平面已经淹没了一个以上的积水盆，因此s中包含了C[n-1]中一个以上的连通区域，此时需要在s中建立分水岭，防止不同的区域会被连通起来。
