水平集方法框架

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

零水平集

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

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

$\vec{n}$ 为外法线向量， $\Gamma$ 为演化曲线。我们不妨假设有函数 $\varphi (\vec{x})$，它的零水平集为 $\Gamma$ ，并且满足，
$$\{\begin{array}{rlrl}& \varphi >0& & \vec{x}\in {\Gamma }_{in}\\ & \varphi <0& & \vec{x}\in {\Gamma }_{out}\end{array}$$
这里， ${\Gamma }_{in}$ 表示 $\Gamma$ 内部， ${\Gamma }_{out}$ 表示 $\Gamma$ 外部。那么，对于任意的 $\vec{x}\in \Gamma$ ， $\varphi$ 有如下两个性质：

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

• $$\mathrm{d}\mathrm{i}\mathrm{v}(\frac{\nabla \varphi }{|\nabla \varphi |})=-\kappa$$
  证明：
  ${\varphi }_s$ 在 $\Gamma$ 沿切线方向上恒为零，故有： ${\varphi }_{ss}=0$ ，由链式法则，可知：
  $${\varphi }_{ss}(\vec{x})=\frac{\partial }{\partial s}(\nabla \varphi \cdot {\vec{x}}_s)=\frac{\partial }{\partial s}\nabla \varphi \cdot {\vec{x}}_s+\nabla \varphi \cdot {\vec{x}}_{ss}$$
  由曲率的定义，有 ${\vec{x}}_{ss}=-\kappa \vec{n}$ ，由性质 [xz1] ，有 $\nabla \varphi \cdot \vec{n}=-|\nabla \varphi |$ ，代入上式，移项，可得：
  $$-\kappa |\nabla \varphi |=\frac{\partial }{\partial s}\nabla \varphi \cdot {\vec{x}}_s$$
  将上式左端展开，即证。

水平集方程

如下图所示，

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

如上图所示，曲线上任意一点从当前时刻到下一个时刻，始终保持 $\varphi (\vec{x}(t),t)=0$ ，故对一个特定的时刻 $t$ ，对任意 $\vec{x}\in \Gamma (t)$ ，有以下式子成立：
$$\frac{\partial \varphi (\vec{x},t)}{\partial t}=0$$
使用链式法则，可以得到：
$$\frac{\partial \varphi (\vec{x},t)}{\partial t}+\frac{\partial \varphi (\vec{x},t)}{\partial \vec{x}}\cdot \frac{\partial \vec{x}}{\partial t}=0$$
如图所示，我们将 $t$ 时刻， $\Gamma$ 曲线上的点的速度 $\vec{v}$ 分解为沿外法线方向的速度 ${\vec{v}}_n$ 和切线方向速度 ${\vec{v}}_s$ ，用 $v_n$ 表示 ${\vec{v}}_n$ 的大小，负值表示方向为内法线方向。容易知道， ${\vec{x}}_t=\vec{v}$ ，再由之前的式子 ，那么上式可变为：
$${\varphi }_t(\vec{x},t)-v_n|\nabla \varphi (\vec{x},t)|=0$$
此方程是一个特殊的哈密顿-雅克比方程 （Hamilton-Jacobi Equation） ，一般就称之为水平集方程，需要注意的是，此时方程中的 $\vec{x}\in \Gamma (t)$ 。结合给定的初始曲线，那么曲线演化问题就转化为了解下面一个偏微分方程：
{ ϕ t ( x ⃗ , t ) − v n ∣ ∇ ϕ ( x ⃗ , t ) ∣ = 0 x ⃗ ∈ Γ ( t ) , t &gt; 0 Γ ( 0 ) = { x ⃗ ∣ ϕ ( x ⃗ , 0 ) = 0 } \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})=\{\begin{array}{rlrl}\underset{\vec{y}\in \Gamma }{\min }|\vec{x}-\vec{y}|& & & \vec{x}\in {\Gamma }_{in}\\ -\underset{\vec{y}\in \Gamma }{\min }|\vec{x}-\vec{y}|& & & \vec{x}\notin {\Gamma }_{in}\end{array}$$
${\Gamma }_{in}$ 指 $\Gamma$ 内部，二维情况下， $\vec{x}\in {\mathbf{R}}^2\text{，}\vec{y}\in {\mathbf{R}}^2$ ，那么称 $d$ 为一个符号距离函数，下面把符号距离函数也简称为 SDF 。

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

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

• 对于任意的 $\vec{x}\in \Gamma$ ，由水平集函数的性质可得：
  $$\begin{array}{rlr}& \nabla d=-\vec{n}\cdot |\nabla d|=-\vec{n}& \\ & \Delta d=-\kappa |\nabla d|=-\kappa & \end{array}$$

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