水平集方法框架

水平集方法是现代图像处理中很重要的一个方法，为了说清楚这个东西，我们先介绍几个基本的概念。

零水平集

对于一个函数 $\phi(\vec x)：{\mathbf{R}^n}\rightarrow \mathbf{R}$ϕ(x)：Rn→R（其中$\vec x \in {\mathbf{R}^n}$x∈Rn ，下同），取其值域为零部分对应的定义域：
$\Gamma = \{ \vec x|\phi (\vec x) = 0\}$Γ={x∣ϕ(x)=0}
这里， $\Gamma \in {\mathbf{R}^{n-1}}$Γ∈Rn−1 称为函数 $\phi$ϕ 的零水平集，反之， $\phi$ϕ 称为 $\Gamma$Γ 的一个水平集函数。

通俗地说，函数的水平集是这个函数在某个高度上所有点的一个集合。函数的零水平集有一些良好的性质，在如下图所示的曲面演化问题中，

$\vec n$n 为外法线向量， $\Gamma$Γ 为演化曲线。我们不妨假设有函数 $\phi(\vec x)$ϕ(x)，它的零水平集为 $\Gamma$Γ ，并且满足，
$\left\{ \begin{aligned} &amp;\phi &gt; 0&amp;&amp;\vec x \in {\Gamma_{in}}\\ &amp;\phi &lt; 0&amp;&amp;\vec x \in {\Gamma_{out}}\\ \end{aligned} \right.${​ϕ>0ϕ<0​​x∈Γin​x∈Γout​​
这里， $\Gamma_{in}$Γin​ 表示 $\Gamma$Γ 内部， $\Gamma_{out}$Γout​ 表示 $\Gamma$Γ 外部。那么，对于任意的 $\vec x \in \Gamma$x∈Γ ， $\phi$ϕ 有如下两个性质：

• $\frac{{\nabla \phi }}{{|\nabla \phi |}} = - \vec n$∣∇ϕ∣∇ϕ​=−n
  证明：
  如图所示，设 $\vec s$s 为零水平集 $\Gamma$Γ 的切线方向， $\phi$ϕ 在 $\Gamma$Γ 沿切线方向上恒为零，故有：
  $\frac{{\partial \phi }}{{\partial s}} = 0$∂s∂ϕ​=0 由链式法则，可得：
  ${\phi _s}(\vec x) = \nabla \phi \cdot {{\vec x}_s} = 0$ϕs​(x)=∇ϕ⋅xs​=0
  由此可知 $\nabla \phi$∇ϕ 与切向垂直，对 $\nabla \phi$∇ϕ 进行单位化并根据 $\phi$ϕ 内正外负的情况取符号，即得：
  $\frac{{\nabla \phi }}{{|\nabla \phi |}} = - \vec n$∣∇ϕ∣∇ϕ​=−n

• ${\rm{div}}(\frac{{\nabla \phi }}{{|\nabla \phi |}}) = -\kappa$div(∣∇ϕ∣∇ϕ​)=−κ
  证明：
  $\phi_s$ϕs​ 在 $\Gamma$Γ 沿切线方向上恒为零，故有： $\phi_{ss}=0$ϕss​=0 ，由链式法则，可知：
  ${\phi _{ss}}(\vec x) = \frac{\partial }{{\partial s}}(\nabla \phi \cdot {{\vec x}_s}) = \frac{\partial }{{\partial s}}\nabla \phi \cdot {{\vec x}_s} + \nabla \phi \cdot {{\vec x}_{ss}}$ϕss​(x)=∂s∂​(∇ϕ⋅xs​)=∂s∂​∇ϕ⋅xs​+∇ϕ⋅xss​
  由曲率的定义，有 $\vec x_{ss}=-\kappa \vec n$xss​=−κn ，由性质 [xz1] ，有 $\nabla \phi \cdot \vec n = -|\nabla \phi|$∇ϕ⋅n=−∣∇ϕ∣ ，代入上式，移项，可得：
  $- \kappa |\nabla \phi | = \frac{\partial }{{\partial s}}\nabla \phi \cdot {{\vec x}_s}$−κ∣∇ϕ∣=∂s∂​∇ϕ⋅xs​
  将上式左端展开，即证。

水平集方程

如下图所示，

我们将演化曲线上各点的速度分解到法线方向和切线方向，切线方向的速度不影响曲线几何形状的改变，所以，考虑由曲率驱动的曲线演化问题时，我们可以只考虑曲线上的点沿法向的速度。我们现在寻找一个发展方程 $\phi(\vec x(t),t)$ϕ(x(t),t) ，使得在每一个时刻 $t$t ，它的零水平集 $\Gamma(t)$Γ(t) 恰好是曲线在不同的时刻的状态。

如上图所示，曲线上任意一点从当前时刻到下一个时刻，始终保持 $\phi(\vec x(t),t)=0$ϕ(x(t),t)=0 ，故对一个特定的时刻 $t$t ，对任意 $\vec x \in \Gamma(t)$x∈Γ(t) ，有以下式子成立：
$\frac{{\partial \phi (\vec x,t)}}{{\partial t}} = 0$∂t∂ϕ(x,t)​=0
使用链式法则，可以得到：
$\frac{{\partial \phi (\vec x,t)}}{{\partial t}} + \frac{{\partial \phi (\vec x,t)}}{{\partial \vec x}} \cdot \frac{{\partial \vec x}}{{\partial t}} = 0$∂t∂ϕ(x,t)​+∂x∂ϕ(x,t)​⋅∂t∂x​=0
如图所示，我们将 $t$t 时刻， $\Gamma$Γ 曲线上的点的速度 $\vec v$v 分解为沿外法线方向的速度 $\vec v_n$vn​ 和切线方向速度 $\vec v_s$vs​ ，用 $v_n$vn​ 表示 $\vec v_n$vn​ 的大小，负值表示方向为内法线方向。容易知道， $\vec x_t = \vec v$xt​=v ，再由之前的式子 ，那么上式可变为：
${\phi _t}(\vec x,t) - {v_n}|\nabla \phi (\vec x,t)| = 0$ϕt​(x,t)−vn​∣∇ϕ(x,t)∣=0
此方程是一个特殊的哈密顿-雅克比方程 （Hamilton-Jacobi Equation） ，一般就称之为水平集方程，需要注意的是，此时方程中的 $\vec x \in \Gamma(t)$x∈Γ(t) 。结合给定的初始曲线，那么曲线演化问题就转化为了解下面一个偏微分方程：
$\left\{ \begin{aligned} &amp;{\phi _t}(\vec x,t) - {v_n}|\nabla \phi (\vec x,t)| = 0&amp;\vec x \in \Gamma(t),t&gt;0\\ &amp;\Gamma(0)=\{\vec x|\phi(\vec x,0)=0\}\\ \end{aligned} \right.${​ϕt​(x,t)−vn​∣∇ϕ(x,t)∣=0Γ(0)={x∣ϕ(x,0)=0}​x∈Γ(t),t>0

符号距离函数

符号距离函数 （Signed Distance Function） 是一个水平集函数，它给定了点到某条曲线上距离这个点最近点的距离，也可以说是这个点离曲线的最短距离，它在数学上可以这样表述：

在某区域上给定一条曲线 $\Gamma$Γ ，定义与之相关的函数：
$d(\Gamma,\vec x)= \left\{ \begin{aligned} \mathop {\min }\limits_{\vec y \in \Gamma } |\vec x - \vec y| &amp; &amp; &amp;\vec x \in \Gamma_{in}\\ -\mathop {\min }\limits_{\vec y \in \Gamma } |\vec x - \vec y|&amp; &amp; &amp;\vec x \notin \Gamma_{in}\\ \end{aligned} \right.$d(Γ,x)=⎩⎪⎨⎪⎧​y​∈Γmin​∣x−y​∣−y​∈Γmin​∣x−y​∣​​​x∈Γin​x∈/​Γin​​
$\Gamma_{in}$Γin​ 指 $\Gamma$Γ 内部，二维情况下， $\vec x \in \mathbf{R}^2 \text{，} \vec y\in \mathbf{R}^2$x∈R2，y​∈R2 ，那么称 $d$d 为一个符号距离函数，下面把符号距离函数也简称为 SDF 。

符号距离函数有很多良好的性质，包括在边界上的几乎处处可微，关于凸区域的凸性，以及不同符号距离函数之间和差运算的一些性质，作为重点，列以下两条关于单位法向量和平均曲率的性质：

• 对于任意的 $\vec x \in \Gamma$x∈Γ $|\nabla d| = 1$∣∇d∣=1 这也是符号距离函数的一个判断条件，它是充要的。这里的充分性怎么理解？指的是对任意水平集曲线上的点都要满足。

• 对于任意的 $\vec x \in \Gamma$x∈Γ ，由水平集函数的性质可得：
  $\begin{aligned} &amp;\nabla d = - \vec n \cdot |\nabla d|=-\vec n &amp;\\ &amp;\Delta d = - \kappa |\nabla d| = - \kappa &amp; \end{aligned}$​∇d=−n⋅∣∇d∣=−nΔd=−κ∣∇d∣=−κ​​

以上便是水平集方法的一些相关的基础知识。