水平集

《基于活动轮廓模型的图像分割》朱国普哈工大活动轮廓的经典博士学位论文水平集算法简介（LevelSet）一、水平集的定义与实数c对应的可微函数f:R^n—R的水平集是实点集{(x1,x2,...,xn)|f(x1,x2,...,xn)=c}，称可微函数f为水平集函数。[举例]函数f(x,y,z)=x^2+y^2+z^2对应于常数c的水平集是以(0，0，0)为球心，sqrt(c)为半径的球面。当n=2,称水平集为水平曲线(LEVELCURVE)。当n=3,称水平集为水平曲面(LEVELSURFACE)。二、水平集的核心思想LevelSet方法是由Sethian和Osher于1988年提出，最近十几年得到广泛的推广与应用。简单的说来，LevelSet方法把低维的一些计算上升到更高一维，把N维的描述看成是N＋1维的一个水平。举个例子来说，一个二维平面的圆，如x^2+y^2=1可以看成是二元函数f(x,y)=x^2+y^2的1水平，因此，计算这个圆的变化时就可以先求f(x,y)的变化，再求其1水平集。这样做的好处是，第一，低维时的拓扑变化在高维中不再是一个难题；第二，低维需要不时的重新参数化，高维中不需要；第三，高维的计算更精确，更鲁棒；第四，LevelSet方法可以非常容易的向更高维推广；最后，也是非常重要的一点就是，上升到高维空间中后，许多已经成熟的算法可以拿过了直接用，并且在这方面有非常成熟的分析工具，譬如偏微分方程的理论及其数值化等。当然，这种方法最为诟病的就是他增加了计算量，但新的快速算法不断出现，使得这也不是个大问题。考虑两个分离的圆形火焰，都以一个恒定的速度向外燃烧（见图(a)），其界面的演化是可以预测的，当这两个分离的界面燃烧到一起时，演化界面合并为一个单独的转播前沿（见图(b)），这种拓扑结构的变化使得离散参数化遇到真正的困难，因为要得到扩展火焰的真正边界，就必须从燃烧的区域中去除原属于两个界面的边界点。要想系统地确定这些点是一个困难的问题，然而一个窍门就是采用一个更高一维的空间，这就是水平集方法的基本思想。（）红色的曲面是相应的水平集函数的图像,的某个水平面决定了左上角的形状，假设其中的蓝色平面即为x-y平面（不同时刻截取C水平集不同的部位），则形状的边界可以表示为的零水平集（灰影所示）在不同时刻演化的过程（即只有两个变量，所以图像的分割过程可以看成是水平集函数的零水平集(z=0)不断演化的过程）例如在t1时刻水平集函数为z=x2+y2-1,零水平集函数为x2+y2-1=0，在t2时刻水平集函数为z=2x2+3y2-4,零水平集函数为2x2+3y2-4=0，在图像分割过程中，可将图像边界的演化看成是水平集函数的演化过程，图像的边界是水平集函数的0水平集。出自（出自博士学位论文基于活动轮廓模型的图像分割朱国普哈工大），因为在曲线上的距离为0，所以将曲线（目标边界）的演化看成是零水平集的演化。水平集函数图（如下图）的建立就是根据一个点（x,y）与曲线的距离Phi，共三个变量进行建立的（分别对应图中的x,y,z坐标轴）。图像分割与水平集怎么联系起来？出自《水平集方法及其在图像分割中的应用研究》中国科技大学对于求最小化一个能量泛函方程（泛函（里面的变量是一个函数））例如上面的两个方程，要求使得能量最小时的变量的值（有的变量是函数），这个时候可以采用欧拉拉格朗日方程来解决。当能量函数为微积分方程时可以考虑欧拉方程。欧拉-拉格朗日方程（Euler-Lagrangeequation）为变分法中的一条重要方程。它提供了求泛函的临界值（平稳值）函数，也就是此泛函的临界点的一个方法。如果变换后的欧拉方程中有多个变量，则采用固定一部分变量，求另一个变量的方法（这类方法一般需要对变量进行初始化）。比如snake模型可以将求目标函数最小时的变量值转化为相应的欧拉方程由于这个欧拉方程没有解析解（可能要求多个变量），所以可以引入虚拟时间变量t,通过给曲线赋一个初值可以求得以上的值，然后再通过梯度下降法求得曲线的值，然后再将此曲线作为一个初始曲线按照以上的求解方法进行迭代求解，直到达到收敛条件（一般迭代到上面的phi(x)/phi(t)=0，在数值实现上有限差分法、动态规划法、有限元法、贪婪算法以及一些与人工智能有关的方法，使用最广泛的是有限差分法(出自博士学位论文基于活动轮廓模型的图像分割朱国普哈工大)或者可以设置为多少轮等）当轮廓线的拓扑结构发生改变时，就必须将该轮廓线重新进行参数化。通常轮廓线的重新参数化过程（针对拓扑结构变化的重新参数化）需要采取相当繁琐的附加措施，因此，参数活动轮廓模型一般不考虑轮廓线发生拓扑变化的情况（出自博士学位论文基于活动轮廓模型的图像分割朱国普哈工大）。而参数活动轮廓模型的这个缺点也严重地束缚了它在图像分割中的应用。模型：M-S模型：第一项表示曲线的弧长，保持曲线的光滑性。第二项表示区域内部亮度的变化，变化尽量的小，保持区域的光滑。第三项是数据拟合项。CV模型：前两项是数据拟合项（灰度常量表示某个区域内部亮度的平均值，假设区域内部的灰度是均匀的、变化较小的），第三项是曲线的弧长，保持曲线的连续性和光滑性。虽然snake模型中也有这项来表示曲线的连续性，但是snake的曲线是用参数表示的，对于多目标时，一个连续曲线不可能分裂成两个曲线。而将其换成水平集函数的形式后，水平集函数的拓扑变化比较方便，且能保持连续性，所以可以应对多目标问题。带有偏场的模型：假设偏场的变化是缓慢的（在极小的区域内，像素点的偏场是相同的）第一项是拟合项，K表示的是一个区域权重，随着像素点的位置不同，加的权重不同（假设不同区域内是有不同偏场的）第二项是曲线光滑项。第三项是正则化项，保证水平集演化的稳定性。求解：水平集函数值（不论CV模型还是李纯明的模型）的求法一般都是使用梯度下降法。CV模型：（梯度下降）phi0=phi0+dt.*force;（CV代码，force即上式，其中的div（）是按照曲率计算的）在CV模型中，先固定c1,c2然后求Phi0，其中c1和c2是相关区域内部灰度的平均值。李春明模型：水平集函数求解方法（梯度下降）u(:,:,2)=u(:,:,2)+timestep*(L2+P2+A2);也是先固定其他变量C和B，求u。然后再求C和B，交替进行。其中div(▽phi/abs(▽phi))的求法是先求phi的梯度▽phi（分别在x和y方向的），然后再求▽phi/abs(▽phi)的梯度（X方向和Y方向），然后再将这两个梯度相加获得div。如下公式所示在CV模型求解过程中，div（）的求解是按照曲率计算的在水平集的应用中（CV模型和李春明的模型），理论上使用Heaviside函数和Dirac函数容易理解，但是实际进行数值计算时，用的是式子(3-44)（用此公式逼近Heaviside函数和Dirac函数）