biscuitの博客

水平集的思想#

显式地跟踪一条轮廓曲线 $C(p,t)$ 需要处理拓扑变化（分裂、合并）——曲线在演化过程中可能从一条断成两条，或者两条合成一条，显式表达处理起来非常麻烦。

水平集将曲线隐式地表示为一个更高维函数 $\phi(x,y,t)$ 的零水平集：

$\phi$ 通常初始化为符号距离函数：曲线内部的点 $\phi < 0$，外部的点 $\phi > 0$，曲线上的点 $\phi = 0$。曲线演化转化为 $\phi$ 随时间的变化，而 $\phi$ 在每一步都是单值函数，拓扑变化自动处理。

Eikonal 方程与快速行进法#

当曲线始终沿法线方向以速度 $F > 0$ 向外传播时（单向传播，不回流），到达时间 $T(x,y)$ 满足 Eikonal 方程：

其中 $T(x,y)$ 表示波前从初始种子点传播到像素 $(x,y)$ 所需的时间，$F(x,y)$ 是传播速度。若 $F$ 处处为 1，则 $T$ 就是距离变换——这就是 Eikonal 方程与距离变换的关系。

FMM 的核心思路是：用类似 Dijkstra 算法的思想，按照到达时间从小到大的顺序逐像素更新 $T$ 值。每个像素维护三种状态：

• 已知（Known）：$T$ 值已经确定，不再更新。
• 窄带（Narrow Band / Trial）：$T$ 值已由邻居计算得出但尚未确定，是当前传播的前沿。
• 未到（Far）：尚未被波及。

算法循环从窄带中取出 $T$ 值最小的像素，将其标记为 Known，用 Eikonal 方程更新它的四个邻域像素。直到所有像素都被标记为 Known 或达到停止条件。

离散 Eikonal 方程的求解（二维，取 $\max$ 形式的 Godunov 差分）：

其中 $D_x^{-}, D_x^{+}$ 分别是向后和向前差分。这个公式确保了到达时间解是物理合理的（满足因果关系），使得波前不会”倒流”。

速度函数设计#

$F(x,y)$ 控制传播行为，决定了分割的边界最终停在何处。两种经典设计：

基于边缘的速度：用图像梯度幅值来减速。梯度大的地方可能是物体边界，波前应该慢下来：

当图像梯度大时，$F$ 接近 0，传播停止；平坦区域梯度小，$F$ 接近 1，传播迅速。$G_\sigma$ 是高斯平滑核。

基于区域的速度：利用统计信息（强度均值、方差）驱动模型，适应弱边界场景。

分割流程#

1. 在目标内部或边缘附近指定种子点（初始零水平集）。
2. 计算边缘指示函数 $g(x,y)$ 或自定义速度图。
3. 运行 FMM，逐像素计算到达时间 $T(x,y)$，传播到整个图像。
4. 设定到达时间阈值 $T_{\max}$（或最大迭代步数），$T(x,y) \leq T_{\max}$ 的区域作为分割结果。

FMM 的计算复杂度为 $O(N \log N)$，$N$ 为像素总数，其中 $\log$ 因子来自窄带队列的堆维护。