水平集算法讨论提纲

水平集算法讨论提纲1.基本思想水平集方法（LevelSetMethod）主要是从界面传播等研究领域中逐步发展起来的，是一种用于界面追踪和形状缄默的数值方法。其最大的优点是可以在笛卡尔网格上对演化中的曲线（面）进行数值结算，而不必对曲线（面）进行参数化，其遵循的是欧拉变分（Euler）框架，计算过程是在固定网格上进行的。水平集方法的另一个优点是可以方便地处理演化曲线（面）的拓扑结构改变。一般说来，构成水平集方法有三个要素：（1）高一维标量场的隐式数据表达；（2）用于控制演化过程的偏微分方程（PDE）；（3）数值求解方案。1.1水平集的嵌入水平集方法的基本思想是讲待求解的未知曲线或者曲面内嵌到一个高一维的标量场中。设未知曲线或曲面的方程为tzyxS;,,，其演化方程为：tXNtXSt,,（1.1）其中N为曲线或曲面上一点XP的法向量，为该点上沿法向量方向上的演化速度。当把未知曲线或曲面tzyxS;,,内嵌到高一维的标量场中时，假设该曲线或曲面为标量场1的水平集（等势线或等势面）：consttSuRtStSu,|,:,2（1.2）不失一般性，可以假设其为零势线或零势面，或统称为零水平集。边界内部边界上面边界外部,0,0,0,tSu1绝大多数文献上都将“标量场”表述为“水平集函数”。本文认为使用“标量场”可以更好的理解水平集方法的几何意义，所以在本文中通常都会使用“标量场”这个词来表述演化空间。但是需要明白这两个词实际上指的是同一个意思即可。（1.2）式两边对时间t求微分可得：0tSutu（1.3）将（1.1）式代入（1.3）式可得：uuuuuNtu（4）（1.4）式就是高一维标量场的演化方程。这样，就把原本是曲线或者曲面的演化方程转化成了高一维标量场的演化方程。在标量场中，只要求出其零水平集即可得到最终曲线或者曲面的演化结果。值得指出的是，水平集方法只是众多求解偏微分方程的数值解法之一。图1是一个水平集演化的示意图，从图中可以看出，水平集方法可以很好的处理曲线或者曲面演化过程中出现的拓扑结构改变问题，同时不需要已知曲线或者曲面的参数形式。图1水平集演化过程中的拓扑结构改变1.2偏微分方程由1.1节可知水平集演化的原始动力来自曲线或曲面的演化。2.数值解算方案2.1标量场初始化水平集演化是通过高一维的标量场的演化来实现曲线或曲面的演化的。因此水平集演化的实施首先需要定义一个高一维的标量场，然后给出曲线或者曲面演化的初值。标量场通常可以离散化表示为用一个空间均匀的格网，标量场的初值依赖于初始的曲线或者曲面的形状。一般情况下，初始的曲线或者曲面都是用一些简单的曲线（矩形和圆）或者曲面（正方体表面或者球面）表示。标量场的初始化如图2所示。图2标量场的初始化上图以曲线演化为例。其中，0C为初始曲线。标量场中每一个格网点上的场值iju初始化为符号距离函数（signeddistancefunction，SDF）：曲线内部在曲线上曲线外部,,0,;,;,sgn0;,00ijijddCjidistCjitjiu（2.1）关于符号距离函数，目前看到的文献2指出：首先，曲线或者曲面的隐式表达与它的符号距离函数是等价的；其次，从数值计算角度上讲，由于符号距离函数保证了1u，因此可以保证离散网格的大小为1，使得数值计算具有较高的精2《水平集方法及其在图像分割中的应用研究》，中国科技大学，博士学位论文，王晓峰，2009。度3。从公式（2.1）可以发现，计算符号距离函数需要解决两个问题：（1）判断点在出事曲线或者曲面的内部还是外部；（2）计算点到初始曲线或者曲面的最短距离。2.2基于PDE的演化标量场初始化以后，就可以依据偏微分方程（1.4）式对标量场中每一个格网点的场值进行迭代。2.3内插零水平集由于曲线或者曲面相当于标量场中的零水平集（零势线或零势面），因此当标量场中每一个格网点的场值发生改变后，曲线或者曲面的位置和形状就会发生变化。新的曲线或者曲面的位置和形状可以通过在标量场中内插得到。具体做法可以对每一个格网点进行检测，如果该点的场值和它邻域中的格网点的场值的符号不同，那么就可以在这两个格网点之间通过线性内插得到一个零水平集点，连接所有的零水平集点或者对所有的零水平集点重构三角网即可得到新的曲线或者曲面的位置与形状。2.4演化终止条件目前还没有看到有文献讨论演化的终止条件。但是，根据前述对水平集方法的理解，暂定演化终止条件为零水平集上每一个点在法向上的速度函数的模足够小：tyxC,,（2.2）2.5标量场格网间距与演化时间间隔在给定标量场网格间隔h的情况下，时间步长t的选择要满足CFL（Courant-Friedrichs-Levy）条件：ht（2.3）为了保证演化的稳定性和收敛性，CFL条件对于时间步长t和速度给出了一个上限。这个条件的含义可以理解为曲线或者曲面在每一次迭代过程中位置的变化都不会超过一个网格的尺寸h。3文献中这一段话目前尚未很好的理解，需要进一步查找并阅读更原始的文献。3.解算方案的变化3.1重新初始化水平集方法本身存在一个问题，即在演化了一段时间之后，水平集函数会发生震荡，并渐渐失去光滑性和距离函数特性，如此发展下去会造成误差的累积，从而导致最终的计算结果偏离真实情况。为此可以引入一个折中方法，即重新初始化（re-initialization），也就是说每隔一段时间重构标量场，使其保持为符号距离函数，之所以说是折中方法，原因在于重新初始化和初始化的本质上是一样的，只不过是作用时间上的不同，都是在保证精度的情况下牺牲了效率。由2.1节的初始化过程可知，标量场初始化的计算成本是很高的。如何快速生成符号距离函数，对于提高水平集方法的计算效率至关重要！目前已知的研究工作包括：（1）Sethian（1996）提出使用快速步进法（FastMarchingMethod）来解决这一问题。基本思想是通过完全二叉树对邻域中所有点的到达顺序进行排序，并找出到达时间最小点，使得计算复杂度降至mnOlog；（2）Tsai（2002）提出了源点扫描法（VoronoiSourceScanningMethod），李俊等（2002）对其做了进一步的改进，使得计算复杂度减少到NO，N为扫描过的网格点数。（3）已经有学者提出了在水平集演化方法中避免重新初始化的方法4，即引入调和距离函数的方法。在本文后面的“演化匹配的实施细节”中将会介绍到这种方法的一个应用。虽然重新初始化乐意保证标量场（水平集函数）的稳定性和收敛性，但其计算量比较大。在某些情况下，比如水平集函数不光滑或者水平集函数的一边比另外一边更加陡峭时，经过重新初始化后的零水平集会产生较大的误差。如果水平集函数远离符号距离函数的话，则实际上重新初始化根本不起作用（Li,2005）。3.2窄带理论通常情况下，水平集演化都是在全局域上进行计算的。例如图像分割的演化算法就是在图像的全局域上进行的，因此对于尺寸较大的图像来说其计算量是非常大的。为了解决这个问题，Chop（1993）最早提出了窄带（narrowband）方法的思想，而Adalsteinssonetal（1995）给出了具体的实现方法。这是一种水平集演化的快速数值实现方法，其基本思想并不复杂，就是在数值演化过程中只更新零水平集周围的一个窄带形状区域里标量场的值。由于窄带区域内的王个点相4J.GomesandO.Faugeras.Reconcilingdistancefunctionsandlevelsets.JournalofVisualCommunicationandImageRepresentation,11:209-223,2000.对较少，因此整个演化过程中的计算量可以得到大大减少。下图给出了窄带方法的示意图，图中的黑线即零水平集。（a）是三维曲面上的窄带示意图，（b）是相对应的二维平面上的示意图，图中的黑点位于窄带之内，是需要更新的网格点，通常称之为激活点。图3窄带方法示意图（a）三维空间示意图（b）二维平面示意图窄带法存在的一个问题就是：经过若干次迭代之后，零水平集可能会落在窄带范围之外，此时就需要更新窄带水平集函数，包括两个步骤：（1）更新窄带的内外边界，使得零水平集重新落在窄带区域内，同时保持窄带宽度即内外边界的距离为2。（2）重新初始化水平集函数为符号距离函数。窄带更新的次数和窄带的宽度有关。如果宽度过小，则零水平集可能会在很少的迭代次数之后就落在窄带之外，从而导致在演化过程中需要进行多次更新，而更新的内容就包括了较为耗时的水平集函数重新初始化，因此计算量会增加；但是如果窄带的宽度过大的话，则需要更新的激活点的数目就比较大，计算量同样会增加。因此在演化之前需要选择合适的窄带宽度，比较合理的取值范围是16~122。此外，由于窄带法只更新零水平集附近的格网点的场值，因此如果曲线或者曲面的初始位置和形状距离最终结果很远的话，演化可能无法收敛到最终结果上去。因此在窄带法中，需要初始曲线或者曲面具有一定得精度，或者换言之，初始曲线和曲面已经被放置在目标轮廓的附件，在这种情况下可能仅需要更新几次窄带或者不更新窄带，就可以使得零水平集落在目标轮廓上。窄带方法在具体实现过程中需要解决如何快速判断格网点是否落在窄带范围之内。以曲面的演化为例，曲面通常是表示为三角网。因此曲面的窄带范围就可以分割为一系列三角柱体，其底面的形状和大小就是三角网中的某个三角面片，柱体棱线的方向为三角面片的法线方向，柱体的高为窄带的宽度2。此时就需要一种快速算法判断某个空间三维格网点是否落在这个三角柱体内部。3.3多尺度水平集演化多尺度水平集演化的思想类似于影像匹配中的金字塔影像匹配策略，即通过构建一系列不同尺度的标量场（网格间隔不同）来进行演化。其中大尺度标量场的演化结果作为小尺度标量场演化的初值。这种演化从较大的尺度一直演化到最终实际应用所需要的精度。显然这种演化策略具有两个优势：（1）可以加快演化计算的效率。大尺度标量场中格网点数量少，因而计算量就比较小。虽然大尺度标量场的演化结果的精度不好，但是可以作为小尺度标量场演化的初值，此时由于初值比较接近最终结果，因此演化迭代的次数可以得到减少；（2）多尺度演化策略还可以有效的避免曲线或者曲面在演化过程中落入某个错误的局部极值处，从而避免最终结果出现错误。4.演化匹配的实施细节本节主要讨论用水平集演化方法实现多视影像的密集匹配方法56。多视匹配的演化方程为：,,,txutxttxu（4.1）其中沿曲面法向的速度函数为：ssTNNTSNNsNdTraceHNH22（4.2）速度函数可以看成是三项的和。高阶项一阶项正则项;;2;2ssTNNTSNNSNdTraceNHH（4.3）其中H代表曲面上一点的平均曲率，N代表曲面上一点的单位法向量，ST代表曲面上一点处的切平面。是影像之间的相关能量，S、N、SN、NN分别为相关能量的一阶和二阶导数。5OlivierFaugeras,RenaudKeriven.VariationalPrinciples,SurfaceEvolution,PDE's,LevelSetMethodsandtheStereoProblem.RR-3021,1996.inria-000736736O.Faugeras,J.Gomes,R.Keriven.ComputationalStereo-AVariationalMethod.GeometricLevelSetMethodsinImaging,Vision,andGraphics.StanleyOsher,NikosParagios.ISBN:978-0-387-95488-2(Prin