level-set介绍

Levelset方法LevelSetMethods是由Sethian和Osher于1988年提出，最近十几年得到广泛的推广与应用。简单的说来，LevelSetMethods把低维的一些计算上升到更高一维，把N维的描述看成是N＋1维的一个水平。举个例子来说，一个二维平面的圆，如x^2+y^2=1可以看成是二元函数f(x,y)=x^2+y^2的1水平，因此，计算这个圆的变化时就可以先求f(x,y)的变化，再求其1水平集。这样做的好处是，第一，低维时的拓扑变化在高维中不再是一个难题；第二，低维需要不时的重新参数化，高维中不需要；第三，高维的计算更精确，更鲁棒；第四，LevelSet方法可以非常容易的向更高维推广；最后，也是非常重要的一点就是，上升到高维空间中后，许多已经成熟的算法可以拿过了直接用，并且在这方面有非常成熟的分析工具，譬如偏微分方程的理论及其数值化等。当然，这种方法最为诟病的就是他增加了计算量，但新的快速算法不断出现，使得这也不是个大问题。用二维曲面与二维平面的交线表示曲线，这在微积分甚至中学数学里都是很平凡的。但是，当我们要描述曲线运动的时候，用LevelSet表示曲线就有很明显的优点。比如说，几条曲线在运动中merge成一条曲线，或一条曲线分裂成几条曲线，这样的拓扑变化是不可能表示成一条连续的参数化曲线的运动。原因很简单，一条连续的参数化曲线是用一个一元连续函数来卞表示的，它显然不能表示几条分开的曲线（这与连续性矛盾）。然而，以上所说的曲线的拓扑变化却可以简单地表示成一个连续变化的的曲面与一个固定的平面的交线。这个曲面本身可以不发生拓扑变化，它可以始终是一个连续的二元函数z=f(x,y)的图象。这样，复杂的曲线运动就可以简单地表示成一个更高一维的函数的演化，这可以用一个发展方程(evolutionequation)来描述，数学里已经有很多工具可以用了。LevelSet的适用范围：这儿只是列举一些经典的领域，但并不完全，如果你能在自己的领域找到新的应用，祝贺你。LevelSet最初始的应用领域就是隐含曲线（曲面）的运动，现在LevelSet已经广泛应用于图像恢复、图像增强、图像分割、物体跟踪、形状检测与识别、曲面重建、最小曲面、最优化以及流体力学中的一些东西。LevelSet需要掌握的知识：学习和应用LevelSet需要掌握偏微分方程理论及其数值化方法，其中又应该着重掌握偏微分方程中的ConversationLaw，TheTheoryofViscositySolution(粘性溶液)andHamilton-JacobiEquation(哈密尔顿-雅可比方程)及其数值化方法。同时，在学习LevelSet的时候也会经常遇到变分法和测度论的一些内容，但对这两方面的要求不高，了解一下就行了。LevelSet的推荐读物：（1）StanleyOsherandRonaldFedkiw.LevelSetMethodsandDynamicImplicitSurfaces.Springer-Verlag(2002).评点：这本书是创始人之一Osher写的，这本书是论述LevelSet的最完整的书籍之一，更偏重于数值化的高精度解，应用领域涉及图像处理以及计算物理。（2）JamesA.Sethian.LevelSetMethodsandFastMarchingMethods.CambridgeUniversityPress(1999).评点：这是另外一个创始人Sethian的作品，与Osher的书互有侧重，互相补充，这本书更偏重于FastMarchingMethods,非结构化网格，涉及的应用领域更广泛。（3）GuillermoSapiro,GeometricPartialDifferentialEquationsandImageAnalysis,CambridgeUniversity.评点：这本书对理解LevelSet也非常有帮助，它更偏重于图像中的几何特征，如曲率等，对几何偏微分方程介绍的比较详细。（4）GillesAubertandPierreKornprobst，Mathematicalproblemsinimageprocessing:PartialDifferentialEquationsandtheCalculusofVariation,Springer,AppliedMathematicalSciences,Vol147,2002。这本书数学味太浓，一般人没兴趣读下去，但如果你确实想对你的方法奠定更好的理论基础，这本书就非常有用了，它可以指导你应该在哪方面下功夫。另外，这边书的前言和第一章写的非常好，非常值得一读。总评：（1）和（2）是学习LevelSet常备案头的手册，如果你想深入，（3）和（4）也应该看一看。LevelSet推荐文章（1）Osher,S.,andSethian,J.A.,FrontsPropagatingwithCurvature-DependentSpeed:AlgorithmsBasedonHamilton–JacobiFormulations,JournalofComputationalPhysics,79,pp.12–49,1988.评点：这是开创LevelSet的一篇文章，必读。~sethian/Publications/publications.html这儿可以下载，但是这儿下载的文章只有文字没有图，要想看真正原版的，到图书馆复印吧。（2）Osher,S.andFedkiw,R.,“LevelSetMethods:AnOverviewandSomeRecentResults”,J.Comput.Phys.169,463-502(2001).评点：这是一篇比较早的综述，UCLACAMReport00-08。可以下载。（3）RichardTsaiandStanlyOsher，levelsetmethodsandtheirapplicationsinimagescience，COMM.MATH.SCI.Vol.1,No.4,pp.623-656评点：这篇综述内容更丰富些，结果也比较新。intlpress.com/CMS/issue4/levelset_imaging_chapter.pdf可以下载。总评：关于Levelset的文章太多，无法一一列举，强烈建议到下面的网址逛一逛，那儿有最新的文章。~imagers/reports.htmLevelSet推荐网站：（1）~sethian/level_set.html评点：这是Sethian的网站，上面关于LevelSet的论述非常多，分门别类，非常清晰。（2）~imagers/评点：这是UCLA的研究组，由Osher创办，关于LevelSet的新进展几乎都跟他们相关，这个网站是关注LevelSet的最新新闻的最好的地方。LevelSet的工具包：~mitchell/ToolboxLS/index.html评点：这是Michell开发的工具包，通用性比较好，缺点是自己修改起来非常麻烦。建议自己重新写这些函数，可以把这个工具包拿来验证自己写的对否。ActiveshapemodelFromWikipedia,thefreeencyclopediaJumpto:navigation,searchActiveshapemodels(ASMs)arestatisticalmodelsoftheshapeofobjectswhichiterativelydeformtofittoanexampleoftheobjectinanewimage,developedbyTimCootesandChrisTaylorin1995[1].TheshapesareconstrainedbythePDM(pointdistributionmodel)StatisticalShapeModeltovaryonlyinwaysseeninatrainingsetoflabelledexamples.Theshapeofanobjectisrepresentedbyasetofpoints(controlledbytheshapemodel).TheASMalgorithmaimstomatchthemodeltoanewimage.Itworksbyalternatingthefollowingsteps:LookintheimagearoundeachpointforabetterpositionforthatpointUpdatethemodelparameterstobestmatchtothesenewfoundpositionsTolocateabetterpositionforeachpointonecanlookforstrongedges,oramatchtoastatisticalmodelofwhatisexpectedatthepoint.TheoriginalmethodologysuggestsusingtheMahalanobisdistancetodetectabetterpositionforeachlandmarkpoint[1].Thetechniquehasbeenwidelyusedtoanalyseimagesoffaces,mechanicalassembliesandmedicalimages(in2Dand3D).Itiscloselyrelatedtotheactiveappearancemodel.Itisalsoknownasa“SmartSnakes”[1]method,sinceitisanalogtoanactivecontourmodelwhichwouldrespectexplicitshapeconstraints.