基于水平集方法的遥感影像分割技术研究外文翻译资料

 2022-10-16 16:06:42

A fast marching level set method for monotonically advancing fronts

J. A. Sethian, Alexandre J. Chorin1[1]

摘要：论文给出了一种基于水平集方法的单调变化轮廓线快速演化方案，使程函方程的的求解变得极其迅速。水平集方法是一种用来计算运动轮廓线的位置的数学技术。它依赖一个初始偏微分方程和以及从双曲型守恒定律借鉴来的技术来演化水平集函数。不论是拓扑结构的变化，还是尖角处的演化，以及曲线的一些相关属性如曲率和法向量的精确定义都可以在这个过程中自然地得到。这篇论文主要论述了这些方法中的一种特殊情形，即界面演化速度仅取决于局部位置的情况。这项技术结合了界面运动的熵条件的相关工作、Hamilton-Jacobi方程的粘性解理论以及快速自适应窄带水平集方法，适用于很多种不同情况，包括分割阴影中的形状，工业化微型芯片生产中的平板印刷衍生计算以及控制理论中的的到达时刻问题。

背景

考虑二维空间中的一个边界或者一条曲线，或者是三维空间中的一个曲面，把一个区域和其他区域分开。试想这个曲线或曲面以一个已知的速度函数沿着它的法向量运动，我们的目的是在界面演化的过程中追踪它的运动轨迹。这里我们只考虑界面在其法线方向上的运动而忽略在切线方向上的运动。

在引文2、3、4中我们可以看到，一个运动界面在演化的过程中可能生成尖角或者产生间断，这种情况下为了使演化可以继续，便需要引入一个弱解。正确的弱解来自于运动界面的熵条件的执行，就像那篇空气动力学的引文中介绍的那样。除此之外，这个满足熵条件的弱解是通过考虑曲率占主导作用的问题中光滑解的极限得到的。

例如，考虑一条初始情况下的余弦曲线，它以F=1的速度运动如图1所示。在运动的过程中运动轮廓线产生了了尖角，对应着曲线斜边上发生了震动，因此弱解必须要在不断的迭代中超越这一点。如果每个点的运动还在继续，那么就会出现燕尾解，如图1A所示，这种解是多值的，而且不能对应一条清晰的能将两个不同区域分开的界面。实际上，一种合适的弱解可以这样的到: 考虑其他光滑的演化方式，在速度规则中加入曲率因素，即让速度（如图1B）。这种光滑解的局限性在于当变为0时，就会产生如图1C所示的弱解；这和通过执行熵条件得到的解一样，就和那个满足标量双曲守恒定律的解类似（见引文2）。这个弱解是不可逆的，对应着运动轮廓线总变化的减少。详细论述见引文3。

图1

正如引文5所论述的那样，作为一项数学技术，这建议我们使用双曲守恒定律来求解运动方程，这就引出了引文6中的水平集公式，这也是我们将要在下文中讨论的内容。

水平集方法

在二维空间中，给出一个闭合曲线的初始位置，以及在其法线方向的速度函数F，水平集方法将视为函数的零水平集。具体做法是令，其中d为平面上的点x与的距离，并且根据x是在外部还是内部将点x标记为plus和minus。然后，根据约束条件，便生成了该界面的演化方程：

(1)

(1)

这是一个比原问题高一维的偏微分方程的初值问题。在图2中（取自引文7）我们展示了一个初始曲线的外向传播和水平函数的伴随运动。水平集方法在这个层面上有若干优点：

  1. 虽然高维水平集函数零水平集对应的零水平集的拓扑结构可能发生改变，但高位水平集函数仍然能保持为一个函数，当形成尖角时也是如此（参见引文6）。
  2. 可以通过离散格网设计出一种计算方法来模拟连续的函数。在充分查明梯度中的空间导数时要慎重。
  3. 通过水平集函数很容易决定轮廓线的几何内部属性，单位法向量由给出，每一个水平集的曲率为。
  4. 在三维空间中，运动界面的方程不改变。

正如引文6所说的那样，上述水平集方法已经被广泛地用于各个方面，包括运动界面。在这些应用中，有些涉及到了最小曲面的迭代(引文8)，还有些涉及到运动曲线或曲面的奇点和测地线（引文9），还有诸如火焰外形变化（引文10，11），流体界面（引文12，13），形状重塑（引文14，15），还有引文16，17中介绍的蚀刻、沉积和光刻技术，在引文18中介绍了对这些核心技术的扩展，比如更快速的方法，引文19中介绍了多流体界面和三点链接中的水平集技术，还有格网迭代（引文7）。这些应用所展现出来的基本欧拉观点已经被很多平均曲率流的理论分析所接受（详情参见引文20，21）。

图2

数值近似

如上所述，对水平集方程（公式1）的合理近似需要生成一个正确的弱解，一种简单的方案在引文6中给出：

(3)

其中，速度函数，并且使用了差分运算符号；例如

在这种数值方法中（以及所有其他近似计算中）的关键点是逆向和处理声点时的正确方向。

窄带法

上述技术不仅要计算与轮廓线相关的零水平集，还要计算出所有水平集的演化，正因如此，这是一个计算量很大的技术，使问题增加了额外的维度。

作为一种代替，我们可以对原有技术做这样的修改使其变得高效起来：在初始化以及更新水平集函数时，只对零水平集附近的网格点的水平集函数值进行变化。这就是所谓的窄带法。这种情况下，对三维空间的网格点的操作的时间复杂度降到了，其中k是窄带有多少个网格的宽度，大大减少了开销。在引文8中详细介绍了窄带法，在引文14中讲了使用窄带法恢复图像的过程，引文18中论述了窄带法的开销。

窄带法的基本理论是根据网格点的位置在窄带中、窄带附近还是窄带外将网格点标记为Alive, Landmines, Faraway，如图3。因此只在被标记为Alive的点上进行水平集函数的计算，一旦演化的过程中触及到了标记为Landmines的点，就重新构建窄带。下面介绍一种应用此方法的快速水平集演化方法。

图3

设想在二维情形中，演化界面是一个运动曲线，我们应当在XY平面中画出演化的零水平集。于是令表示当曲线穿过点的时间，则曲面满足以下方程：

(4)

方程4简单说明了到达时间面与曲线的速度成反比。

这是著名的Eikonal方程的另一种形式，很多应用中都很经常见到对这个问题进行重写后的比较稳定的形式。粘性解的概念与这个方程密切相关，引文22中所讨论的一个核心思想是，使用单调连续的方案会使我们选出偏微分方程的正确粘性极限，正如引文6所使用的水平集方案那样。建议感兴趣的读者查阅此主题相关的大型文献，包括引文22-25中的相关理论和引文26-29的数值算法。现在我们讨论一种依赖于水平集方法和上面所讨论的窄带法的技术。

数值近似

在这一节的讨论中，我们将自身限定在的正方形构成的二维空间中，想象初始轮廓线为，接着我们想象现在有一个关于x周期性变化的正向速度函数，因此，轮廓线在演化中向上远离初始线。运用我们对梯度的近似，于是我们就需要在单元格中为下面的方程找一个解：

(5)

其中，.

由于方程5本质上是在每个网格点上的二维方程（假设其他都是固定的），进行一次典型的迭代直到方程的解收敛到每个网格点上，然后选出其中的可能性最大的值作为按照获得正确粘性解的方法得到的解。Rouy和Tourin(29)介绍了一种迭代求解此问题的算法，在他们的论述里使用了不同的梯度近似方程，它的扩散性更小：

关于此方法的详细内容参见引文29.这个梯度近似方程将会被用在快速水平集演化方法中。

快速水平集演化方法

构建一个快速演化算法的关键在于观察方程6的逆向差分结构。这意味着信息以一种方程演化，那就是从T的较小值向更大的值演化。因此，我们的算法基于“解决”式8通过建立粘性向外从最小的时间价值观念是扫前领先上风时尚由一组分在窄带在现有的前三月这条狭窄的带向前，冻结现有的点的值和带来新的人在狭窄的带结构。关键是在选择的网格点在狭窄的带更新。假设我们想要将一条轮廓线通过N乘N的网格以速度向上演化，代表网格中每个点的速度。在这里，网格点集对应着y轴，并假设.

  1. 初始化
  2. (Alive点：共享点)：令A为所有网格点的集合，令A中每一个点的.
  3. (窄带点：圈)令窄带为所有网格点的集合，并对所有点，使
  4. (Far away点： 矩形)令Far Away点位所有网格点的集合，对所有点使.
  5. 演化
  6. 开始循环：使为窄带中具有最小T值得点。
  7. 将该点加入集合A，并将其从窄带集合中移除。
  8. 标记邻接点 中既不是窄带点和Far Away点。如果是Faraway，则将其从Faraway中移除，并加入到窄带中。
  9. 根据公式6重新计算邻接点的T值，选择最大可能性的解加入到二次方程。
  10. 进行下一次循环

我们在需要时采取周期性边界条件，假设在不需要工作的情况下，以最小的值来确定该窄频带的成员，计算所有网格点的解的总工作量是，是总网格点数。

为什么上述的算法有效？因为我们总是在寻找窄带中的最小值，它的T值必须要正确，其他有着较大T值的宅带点或者faraway点对其没有影响。在邻近点重计算T值的过程（之前没有被接受的点）不能产生比任何其他已经接受了的点更小的T值，因为正确的粘性解是通过选择该二次方程最大可能性的解得到的。因此，在此算法向外演化求解的过程中，总是选择具有最小T值的窄带点，并且只在邻接点中做这一选择。另一种方式来看待这个是每个最小试验值开始惠更斯原理的一个应用，并扩大波前触动并更新所有点。

证明该算法构造一个可行解

这里说明了，上述算法可以产生一个每一处都满足下述方程的离散形式的解：

其中，.已经有建设性的证明给出了。由于的值是建立在从最小值向最大值演化的过程上的，一个只需要表明，每当一个“审判”的价值转换成一个活着的价值，没有邻居的重新计算得到新的值小于允许值。如果这是真的，那么我们将永远在向前行进，从而正确的“迎风”的差分性质将得到尊重。我们将证明我们的结果是二维的，三维的证明是一样的。

若想要更高效的使用上述技术，关键在于更快的定位窄带中具有最小T值的网格点。我们使用一个反向指针的堆排序算法的变形（见引文12和30），更多细节，想象一个窄带点的链表被堆排序算法进行排序之后，最小值便很容易找到了，我们将这些点和指明它们在网格结构中的位置的索引存放在堆排序中。我们维护着一个将二维网格点和网格点在堆排序数组中的位置相互关联起来的伴随数组，临近网格点的值接着被重新计算，接着得到的结果在堆中向上冒泡，直到该结果到达正确的位置上，同时调整网格数组的指针。算法的时间复杂度是，N为参与排序的结果的个数。

上述技术考虑了一个初始平面界面，其内部的窄带点的试验值很容易初始化。假设我们已获得了一条任意的闭合曲线或曲面作为初始轮廓线的位置。这种情况下，我们使用初始窄带水平集方法来初始化这个问题。首先，标记所有网格点为Faraway，使其T值为正无穷大，然后在一个宽度为一个网格点的窄带内建立符号距离函数，初始化高维曲面T。既向前也向后的演化这个曲面直到一个图层的网格点在各个方向上相交，此时计算相交次数。然后收集具有负相交次数的点并将其标记为ALIVE，使其T值为相交次数，具有正相交次数的点标记为窄带点，并使其T值等于正相交次数。然后开始快速演化算法。

结果

简单初始轮廓线。作为第一个例子，我们使用上述算法为一条演化轮廓线计算一个平面发展材料。我们从一个平面轮廓开始，在高度在单位立方体集中在（0.5，0.5，0.5）和遵循向下的接口的演变与速度给定的模型高斯率函数:

(10)

其中. 这率函数对应的驻波效应，从而改变抗拒的材料性质和原因在不断变化的轮廓鲜明的起伏和曲折。在图6中，可以看到此材料被这种初始状态蚀刻出了，这个计算将一直持续直到.

图 4

表1

在表1中，我们给出了函数10在Sparc Workstation 10上的运行时间相关参数，我们注意到加载该文件的模型高斯率函数F总是占用了很大一个比例的时间。

接下来，我们考虑简单的各向同性沉积以上沟槽的案例，对应着速度函数.图7展示了一个被沉积图层填充的二维沟槽，注意到当调用熵条件是产生的尖角。

图5

当今有大量的关于此快速演化水平集方法的应用，包括控制理论中的问题，蚀刻、沉积、光刻技术，以及全球照明系统。同时，上述技术可以得到扩展与修改，比如一般凸速度规律，或者非凸速度函数。我们将在其他地方讨论这些问题。

参考文献

1. Sethian, J. A. (1995) Acta Numerica, in press.

2. Sethian, J. A. (1982) Ph.D. Dissertation (Univ. of California, Berkeley).

3. Sethian, J. A. (1985) Comm. Math. Phys. 101, 487-499.

4. Sethian, J. A. (1990) J. Differ. Geom. 31, 131-161.

5. Sethian, J. A. (1987) in Variational Methods for Free Surface Interfaces, eds. Concus, P. amp;

剩余内容已隐藏，支付完成后下载完整资料

英语原文共 5 页，剩余内容已隐藏，支付完成后下载完整资料

资料编号：[151129]，资料为PDF文档或Word文档，PDF文档可免费转换为Word

原文和译文剩余内容已隐藏，您需要先支付 30元 才能查看原文和译文全部内容！立即支付

以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。

您可能感兴趣的文章