Snakes算法

上一讲我们讲的图像分割算法主要是基于像素的，这一讲主要是基于曲线的。我们希望能得到一个能够包围住图像轮廓的平滑的曲线，snakes算法就是一个很有用的算法。首先我们将曲线的坐标x、y同一用参数s表示，s范围从0-1代表从起点绕曲线一周再回到原点

我们假定初始化的时候这个曲线已经给定，我们定义这个曲线的能量函数，曲线衍进的过程就是让能量函数降低的的过程，能量函数分为外部能量和内部能量

如下是内部能量的定义，内部能量只与曲线的形状有关。能量由两部分组成：一阶导部分与二阶导部分。一阶导代表曲线的“弹性”，也就是曲线是否被拉伸的非常长；二阶导代表曲线曲折程度，也就是曲线是否弯曲不平滑。曲线弹性越低，弯曲越少能量越低

第二部分是曲线的外部能量，代表曲线与边缘的重合程度。重合程度大的时候能量低。

我们有了能量函数以后如何求它的最小值呢？这涉及到变分法，在此就不细讲了。对于数字图像，我们一般用一定数量的点对曲线进行逼近，之后我们可以用梯度下降法来求得函数的最小值

在曲线衍进的时候还需要注意有时我们需要对曲线的点进行重排（再采样）来保证下一次循环（衍进）时我们有更好的效果

当然这种方法也存在问题，我们的活动轮廓无法看到远处的边缘，因此当周围像素值都差不多的时候曲线可能不会继续向内收敛；第二点是当图像中存在噪声时轮廓很可能和噪声点重合。为了解决这个问题我们可以对图像先进行模糊处理，这相当于将原本的边界变得更加模糊了（即扩大的边界的影响范围），这样就能使轮廓有更好的收敛性

 

梯度向量流

采用模糊处理的效果实际上并不是很好，更好的方法是采用梯度向量流（gradient vector flow）。梯度向量流用一个新的矢量场来代替梯度场，从而替换外部能量的部分。

我们用如下方式定义这个新的矢量场v，当梯度值较大的时候，我们另这个矢量场与梯度场的值大致相同；当梯度值较小的时候我们让v的值尽量平滑的变化。这也就意味着在图像边缘处，v的值与梯度场的值相同，当我们逐渐远离边界的时候，v的值不像梯度场一样立马变小，而是有一个逐渐变小的过程。实际上这个新的场v也是扩大了边界的影响范围，使得轮廓能够在更远的地方捕捉到边缘

如果我们将这个场画出来可以得到如下结果。我们可以看出在这种情况下如果初始轮廓在边界外部，那么轮廓将会收缩；如果初始轮廓在边界内部，那么轮廓将会外扩，即朝着向v的模大的地方衍进

Snakes算法也有很多令人头疼的地方，例如追踪每一个点不是一件容易的事，例如snake无法包围多个物体等等

除此以外由于这种算法是基于边缘的，它还会使曲线与我们不需要的边缘重合，例如以下这个例子：曲线并不能很好地包围手掌，而是被背景木桌的条纹所吸引了

 

水平集

为了解决snakes算法不能包围多个物体与洞的问题，我们有水平集（level set）这个算法。与定义一条曲线不同的是，我们定义了一个三维的函数，二维平面上的曲线实际上是这个函数在z=0的横截面

我们用这种方法可以很好地表示包含多个物体或洞的曲线

举个例子，下面右图是我们需要的曲线，左边是这个曲线对应的函数

这种算法还有很多细节我们就不在这讨论了

我们在以上讨论的算法都是基于图像边缘的，当然我们还有基于图像区域的算法，这种算法的能量只与曲线本身的性质以及两个区域块内的像素有关，而与图像的边界无关

比如以下的例子，我们运用基于区域的算法可以让曲线很好地收敛到斑马周围，因为这种情况下曲线外部的颜色基本是绿色，曲线内部基本是黑白的。但如果我们采用基于边缘的算法来计算，那么这个曲线就会收敛到斑马身上的条纹上