一种基于水平集的骨架提取方法1.2

一种基于水平集的骨架提取方法鲍征烨，周卫平，舒华忠(东南大学影像技术实验室南京210096)摘要：本文实现了基于levelset方法的骨架提取。简要介绍了levelset及其快速算法——快速行进法（FastMarchingMethod），并且在此方法的基础上提出了一种骨架提取算法，并提取骨架，通过与传统FMM算法比较，实验结果证明该方法简单有效，并且具有很好的鲁棒性。关键词：水平集，骨架提取，距离变换，FMM，阈值AmethodofextractingskeletonbasedonLevelSetBaoZheng-ye，ZhouWei-ping，ShuHua-zhong（labofimagescienceandtechnology，SoutheastUniversity，NanJing，210096）Abstract:Inthispaper,weuseamethodbasedonLevelSettoextracttheskeletonofobjects.WeintroducedLevelSetandFastMarchingMethod.Andhereitisusedtoextractingskeletonofobjects.WeproposeamethodforextractingskletonbasedonFastMarchingMethod.Thismethodisverysimpleandtheresultiseffective.Keywords:LevelSet,SkeletonExtraction,DistanceTransform,FastMarchingMethod,Threshold0引言传统的提取骨架的方法有基于数字形态学的方法和基于距离变换的方法，两种方法在连续域都是完备的。但在离散域各有其优缺点，细化得到的骨架具有良好的拓扑性，但是骨架点的位置却不准确；基于距离变换的方法在骨架点的准确度上效果好，但连通性一般却很难保证。本文所采用的基于LevelSet方法[1]的骨架提取方法属于基于距离变换的方法，和一般的距离变换方法相比在于具有更好的稳定性以及拓扑无关性[2]。曲线在演化过程中可能会产生尖点、断裂为多条曲线，或者两条或多条曲线融合为一条。LevelSet方法可有效地处理这些情况，缺点是计算复杂度大。直到sethian提出了FastMarchingMethod(FMM)，有效降低了LevelSet的运算复杂度。LevelSet的方法才开始广泛运用。基于上述认知，本文实现了基于FMM[3]的骨架提取方法，并且在此基础上加以改进。该方法计算简单，更稳定。而且从试验结果看，提取骨架准确性和鲁棒性相当好。1FMM方法以二维情况为例，简单介绍FMM方法[3]。假设Ｃ(T)是定义在二维平面的曲线，F是其法线方向上的速度。考虑曲线运动的特殊情况，运动速度F≥0，即曲线Ｃ(T)是一直向外运动。假设曲线经过指定点(,)xy的时间为T(,)xy，那么T(,)xy满足1TF（8）在初始曲线上，T(ｘ，ｙ)=0。式(8)即是著名的Eikonal方程的一种形式。利用逆向差分法，可以根据下式得到式（8)的稳定解[9]:22221/2,,,,,[max(,0)max(,0)max(,0)max(,0)]1/xxyyxyxyxyxyxyDTDTDTDTF(9)式中，D和D分别为后向和前向差分算子。,1,1,,,1,,,1,,,,,,,xyxyxyxyxyxyxyxyxxyyxyxyxyxyTTTTTTTTDTDTDTDThhhh;(10)FMM算法中(,),IxyxyFe(为常量(,)Ixy为图像(,)Ixy灰度的梯度)下面是FMM方法的具体算法[3，4，5](1)初始化。①KNOWN点：即是曲线Ｃ(0)所在的网格点，或指定的种子点，并记时间(,)0Txy。②INSIDE点:考察KNOWN点在曲线外的4邻点，如果有不是KNOWN点的，则初始化为Acctive点，并赋予到达时间(,)1/(,)TxyFxy，将所有Acctive点放入一个排序堆栈中，排序堆栈按照每点的到达时间由小到大排序。③Faraway点:剩余的点初始化为Faraway点，并记到达时间(,)100000Txy。(2)曲线演化。①假设Ａ点是所有INSIDE点中具有最小时间mint的点，则标记Ａ点为KNOWN点，并将Ａ点从INSIDE点中删除。②考察Ａ点的4邻点:若是KNOWN点，则不改变时间;若是INSIDE点，则更新该点时间，并调整其在排序堆栈中的位置;若是Faraway点，则将其标记为INSIDE点，更新该点时间，并将其放入排序堆栈中。③若某一点的到达时间大于指定阈值，或排序堆栈为空，则循环结束，否则转到①。地方。Sethian在文献[3]中详细分析了快速行进法的计算复杂度为(log)ONN，这里N为图像的点数。显然，FMM比水平集的直接数值计算法的计算复杂度2()ON小多了。2基于FMM的骨架提取算法我们讨论如何改进基于FMM的骨架提取算法，由文献[9]知骨架点就是由于紧凑的边界线段，在FMM界面传播过程中消失的点。所有在界面传播的点都来自于边界，边界里面的点在边界上都有一个源点。我们只需确定演化曲线上的每一点来自边界线上的哪一点。我们为每个网格点增加一个距离值设为U[10]，初始时，仅在边界线上T＝0的点选取任意的一个边界点，从U＝1这个点开始，我们沿着边界线单调的增加1，如图2所示。图2U值初始化示意图，a)，c)为原始图像，b)，d)为增加了U值的图像[10]Figur2Objects(a,c)andtheorderinwhichUisassignedtotheirboundaries(b,d)初始化边界的U值后，U值随着FMM的迭代得到整幅图像的U值。随着曲面的演化，U值的传播标志着初始边界的U值到达由初始边界围成的里面每个网格的位置，这样整幅图像每个象素点就有了一个U值。相邻的两个点的U值的最大差值是2，如果U的差值大于2，说明他们不是来源于相邻的点。我们以长方形的骨架为例。图3显示了U沿着边界进化3次的结果。平行边界的，没有骨架点。边界点上的U值之间的差值为1。然而，沿着骨架线，如图3b所示，差值增加。图3U随着FMM演化示意图a)边界线和骨架，b)U值演化3次的结果[10]。Figure3Rectangleanditsskeleton(a).DetailoftheaugmentedFMMresultaroundtherectangle’slowerleftcorner一旦计算出全部网格点的U值，图像的骨架S即为：1,,,1,(){(,)|max(,)}ijijijijSijUUUUt（11）骨架检测算子d＝1,,,1,max(,)ijijijijUUUU(12)为图像的边界，这里为KNOWN点组成的曲线，也即为零水平集组成的曲线。t是我们选择的阈值，可以对骨架进行滤波，保留的点就是骨架点，实践证明，不同的阈值可以保留不同的细节[11]。如上述提到，当U随着边界演化时，U值与相邻点的差值会越来越大。越靠近骨架的点，离边界越远的点，以及初始曲线越尖锐部分的点，U值的差距就越大。t与骨架检测算子d进行比较，t值越大，更多大额细节被忽略，也忽略了由于边界噪声形成的骨架；t值越小，更多的细节被保留，也保留了一些由于边界噪声形成的错误骨架[10]。这是一个相对的过程。保留更多细节的同时，也会使骨架保留了一些不必要的东西。t=20t=100t=300图4不同的图像选取不同的阈值的结果Figure4Feature-basedskeletonpruningfordifferentthresholdst3试验结果和讨论运用上述算法，进行了实验结果的比较，这是其中3个试验结果，分别加入了椒盐噪声，细线条干扰噪声和粗线条干扰噪声，如图5、6、7所示。图5表示的是在图像中加入椒盐噪声后不同中轴提取方法的结果。图6表示的是在图像中加入干扰细线条的噪声后不同中轴提取方法的结果。图7表示的是在图像中加入干扰粗线条的噪声后不同中轴提取方法的结果。图5a)原始图像b)细化算法c)传统FMM方法d)本文算法(t=100)Figure5a)Originalb)Thinningc)FMMd)OurMethod(t=100)图6a)原始图像b)细化算法c)传统FMM方法d)本文算法(t=100)Figure6a)Originalb)Thinningc)FMMd)OurMethod(t=100)a）b）c）d）e）图7a)原始图像b)细化算法c)传统FMM算法d)本文算法(t=100)e)本文算法（t＝200）Figure7a)Originalb)Thinningc)FMMd)OurMethod(t=100)e)OurMethod(t=200)由实验结果可知，在对待椒盐噪声时，传统的细化算法和FMM算法以及本文的算法效果差不多，但是在保证骨架的拓扑性和完整性方面，显然FMM和本文算法更具优势，而在加入干扰细线条后，从图6可以看出运用本文算法和FMM算法干扰细线条噪声基本被滤掉，并且骨架仍然保持较好的完整性，而细化算法受到了明显的干扰而基本不能实现理想的骨架提取，在加入粗线条的干扰噪声后，本文算法的优势就体现出来了，相比FMM得到了更好的结果。4结语本文基于LevelSet方法实现了骨架提取，在sethian提出的快速算法－快速行进法的基础上进行了改进，改进算法不需要进行繁琐的奇点检测的运算，简化了FMM的运算复杂度，另外通过设阈值可以滤除噪声，在保持骨架完整性和滤除噪声方面效果相比经典的细化算法和传统的FMM算法有非常明显的优势，效果很理想。参考文献[1]OsherS,SethianJ.Frontspropagatingwithcurvaturedependentspeed:algorithmbasedontheHamilton-Jacobiformulation[J].JournalofComputationalPhisics,198879(1):12-49.[2]杨猛,汪国平,董士海基于LevelSet的曲线演化,软件学报，200213(9):1858-1865.[3]SethionJ.ALevelSetMethodandFastMarchingMethod:EvolvinginterfacesinComputationalGeometry,FluidMechanics,ComputerVision,andMaterialScience.CambridgeUniversityPress,1996.[4]SethionJ.AFastMarchingLevelSetMethodforMonotonicallyAdvancingFronts.Proc.Nat.Acad.Sci.199693(4):1591-1595.[5]张若文,滕奇志,孙晓刚等.一种快速简便的图像骨架变换方法[J].,信息与电子工程,2003.3(1):1-5.[6]车武军,杨勋年,汪国昭.动态骨架算法[J],软件学报,200314(4)：818-823.[7]吴月娥，周康源，李传富等。基于LevelSet的医学图像分割。北京生物医学工程。2006，25(3):240-243[8]杨新《图像偏微分方程的原理与应用》[M],上海交通大学出版社,2003年第一版.[9]R.Kimmel，D.Shaked，N.Kiryati，A。M。Bruckstein。SkeletonizationviaDistanceMapsandLevelSets[J]。ComputerVisionandImageUnderstanding,199562(3):382-391.[10]AlexandruTelea，JarkeJ。vanWijk。AnAugmentedFastMarchingMethodforComputingSkeletonsan