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

1、一种基于水平集的骨架提取方法鲍征炸，周卫平，舒华忠(东南大学影像技术实验室南京210096)摘要：本文实现了基于 levelset 方法的骨架提取。简要介绍了 levelset 及其快速算法一一，快速行进法(FastMarchingMethod),并且在此方法的基础上提出了一种骨架提取算法，并提取骨架，通过与传统 FMMT 法比较，实验结果证明该方法简单有效，并且具有很好的鲁棒性。关键词：水平集，骨架提取，距离变换，FMM 阈值AmethodofextractingskeletonbasedonLevelSetBaoZheng-ye,ZhouWei-ping,ShuHua-zhong(labo

2、fimagescienceandtechnologySoutheastUniversity,NanJing,210096)Abstract:Inthispaper,weuseamethodbasedonLevelSettoextracttheskeletonofobjects.WeintroducedLevelSetandFastMarchingMethod.Andhereitisusedtoextractingskeletonofobjects.WeproposeamethodforextractingskletonbasedonFastMarchingMethod.Thismethodis

3、verysimpleandtheresultiseffective.Keywords:LevelSet,SkeletonExtraction,DistanceTransform,FastMarchingMethod,Threshold0 引言传统的提取骨架的方法有基于数字形态学的方法和基于距离变换的方法，两种方法在连续域都是完备的。但在离散域各有其优缺点，细化得到的骨架具有良好的拓扑性，但是骨架点的位置却不准确；基于距离变换的方法在骨架点的准确度上效果好，但连通性一般却很难保证。本文所采用的基于 LevelSet 方法1的骨架提取方法属于基于距离变换的方法，和一般的距离变换方法相比在于具有更好

4、的稳定性以及拓扑无关性2。曲线在演化过程中可能会产生尖点、断裂为多条曲线，或者两条或多条曲线融合为一条。LevelSet 方法可有效地处理这些情况，缺点是计算复杂度大。直到 sethian 提出了 FastMarchingMethod(FMM),有效降低了 LevelSet 的运算复杂度。LevelSet 的方法才开始广泛运用。基于上述认知，本文实现了基于 FMM3的骨架提取方法，并且在此基础上加以改进。该方法计算简单，更稳定。而且从试验结果看，提取骨架准确性和鲁棒性相当好。1FMM 方法以二维情况为例，简单介绍 FMM 方法3。假设 C(T)是定义在二维平面的曲线，F 是其法线方向上的速度。

5、考虑曲线运动的特殊情况，运动速度 F0,即曲线 C(T)是一直向外运动。假设曲线经过指定点(x,y)的时间为 T(x,y),那么 T(x,y)满足在初始曲线上，T(x,y)=0。式(8)即是著名的 Eikonal 方程的一种形式。利用逆向差分法，可以根据下式得到式(8)的稳定解9:x2-x2y2-y21/2max(Dx；T,0)max(DxyT,0)max(Dx：T,0)max(Dx；T,0)=1/F、y(9),y,y,y,y,yTx,y-Tx_LyxTx1,y-Tx,yy.,Dx,yT=，Dx,yThhFMM 算法中 Fx,y=eV(x,y)|(ct 为常量VI(x,y)为图像I(x,y)灰

6、度的梯度)下面是 FMM 方法的具体算法3，4，5(1)初始化。KNOWN 点：即是曲线 C(0)所在的网格点，或指定的种子点，并记时间T(x,y)=0。INSIDE 点考察 KNOWN 点在曲线外的 4 邻点，如果有不是 KNOWN 点的，则初始化为Acctive 点,并赋予到达时间T(x,y)=1/F(x,y),将所有 Acctive 点放入一个排序堆栈中,排序堆栈按照每点的到达时间由小到大排序。Faraway 点喇余的点初始化为 Faraway 点，并记到达时间T(x,y)=100000。(2)曲线演化。假设A点是所有 INSIDE 点中具有最小时间tmin的点，则标记A点为 KNOWN

7、 点，并将A点从 INSIDE 点中删除。考察A点的 4 邻点若是 KNOWN 点，则不改变时间；若是 INSIDE 点，则更新该点时间，并调整其在排序堆栈中的位置；若是 Faraway 点，则将其标记为 INSIDE 点，更新该点时间，并将其放入排序堆栈中。若某一点的到达时间大于指定阈值，或排序堆栈为空，则循环结束，否则转到。地方。Sethian 在文献3中详细分析了快速行进法的计算复杂度为O(NlogN),这里 N 为图像的点数。显然，FMM 比水平集的直接数值计算法的计算复杂度O(N12)小多了。2 基于 FMM 的骨架提取算法我们讨论如何改进基于 FMM 的骨架提取算法，由文献9知骨架

8、点就是由于紧凑的边界线段，在FMM 界面传播过程中消失的点。所有在界面传播的点都来自于边界，边界里面的点在边界上都有一个源点。我们只需确定演化曲线上的每一点来自边界线上的哪一点。我们为每个网格点增加一个距离值设为 U10,初始时，仅在边界线上 T=0 的点选取任意的一个13y丁,Dx,yT,(10)hh式中,D-和 D+分别为后向和前向差分算子。xDx，T边界点，从 U=1 这个点开始，我们沿着边界线单调的增加 1,如图 2 所示。Figur2Objects(a,c)andtheorderinwhichUisassignedtotheirboundaries(b,d)初始化边界的 U 值后，U

9、 值随着 FMM 的迭代得到整幅图像的 U 值。 随着曲面的演化,U 值的传播标志着初始边界的 U 值到达由初始边界围成的里面每个网格的位置，这样整幅图像每个象素点就有了一个 U 值。相邻的两个点的 U 值的最大差值是 J2,如果 U 的差值大于 2,说明他们不是来源于相邻的点。我们以长方形的骨架为例。图 3 显示了 U 沿着边界进化 3 次的结果。平行边界的，没有骨架点。边界点上的 U 值之间的差值为 1。然而，沿着骨架线，如图 3b 所示，差值增加。slowerleft图 2U 值初始化示意图，a),c)为原始图像，b),d)为增加了 U 值的图像10一旦计算出全部网格点的 U 值，图像的

10、骨架 S 即为:S(0)=i(,j)|m怖，(-U(11)骨架检测算子d=max(Ui1j.Uij,Uij1.Uij)i1,Ji,Ji,J1i,5Q 为图像的边界，这里为 KNOWN 点组成的曲线，也即为零水平集组成的曲线。t 是我们选择的阈值，可以对骨架进行滤波，保留的点就是骨架点，实践证明，不同的阈值可以保留不同的细节11。如上述提到，当 U 随着边界演化时，U 值与相邻点的差值会越来越大。越靠近骨架的点，离边界越远的点，以及初始曲线越尖锐部分的点，U 值的差距就越大。t 与骨架检测算子 d 进行比较，t 值越大，更多大额细节被忽略，也忽略了由于边界噪声形成的骨架；t 值越小，更多的细节被

11、保留，也保留了一些由于边界噪声形成的错误骨架10。这是一个相对的过程。保留更多细节的同时，也会使骨架保留了一些不必要的东西。图 4 不同的图像选取不同的阈值的结果Figure4Feature-basedskeletonpruningfordifferentthresholdst3 试验结果和讨论运用上述算法，进行了实验结果的比较，这是其中 3 个试验结果，分别加入了椒盐噪声，细线条干扰噪声和粗线条干扰噪声，如图 5、6、7 所示。图 5 表示的是在图像中加入椒盐噪声后不同中轴提取方法的结果。图 6 表示的是在图像中加入干扰细线条的噪声后不同中轴提取方法的结果。图 7 表示的是在图像中加入干扰粗

12、线条的噪声后不同中轴提取方法的结果。t=20t=100t=300图 5a）原始图像b）细化算法 c）传统 FMM 方法 d）本文算法（t=100）b）Thinningc）FMMd）OurMethod（t=100）I簪懑II旨则旨如b）细化算法 c）传统 FMM 方法 d）本文算法（t=100）Figure6a)Originalb)Thinningc)FMMd)OurMethod(t=100)Figure5a)Original图 6a）原始图像a)b)c)d)e)图 7a)原始图像 b)细化算法 c)传统 FMM 算法 d)本文算法(t=100)e)本文算法(t=200)Figure7a)Ori

13、ginalb)Thinningc)FMMd)OurMethod(t=100)e)OurMethod(t=200)由实验结果可知，在对待椒盐噪声时，传统的细化算法和 FMM 算法以及本文的算法效果差不多，但是在保证骨架的拓扑性和完整性方面，显然 FMM 和本文算法更具优势，而在加入干扰细线条后，从图 6 可以看出运用本文算法和 FMM 算法干扰细线条噪声基本被滤掉，并且骨架仍然保持较好的完整性，而细化算法受到了明显的干扰而基本不能实现理想的骨架提取，在加入粗线条的干扰噪声后，本文算法的优势就体现出来了，相比 FMM 得到了更好的结果。4 结语本文基于 LevelSet 方法实现了骨架提取，在 s

14、ethian 提出的快速算法快速行进法的基础上进行了改进，改进算法不需要进行繁琐的奇点检测的运算，简化了 FMM 的运算复杂度，另外通过设阈值可以滤除噪声，在保持骨架完整性和滤除噪声方面效果相比经典的细化算法和传统的 FMM 算法有非常明显的优势，效果很理想。参考文献1OsherS,SethianJ.Frontspropagatingwithcurvaturedependentspeed:algorithmbasedontheHamilton-JacobiformulationJ.JournalofComputationalPhisics,198879(1):12-49.2杨猛，汪国平，董士海

15、基于 LevelSet 的曲线演化，软件学报，200213(9):1858-1865.3SethionJ.ALevelSetMethodandFastMarchingMethod:EvolvinginterfacesinComputationalGeometry,FluidMechanics,ComputerVision,andMaterialScience.CambridgeUniversityPress,1996.4SethionJ.AFastMarchingLevelSetMethodforMonotonicallyAdvancingFronts.Proc.Nat.Acad.Sci.19

16、9693(4):1591-1595.5张若文，滕奇志，孙晓刚等.一种快速简便的图像骨架变换方法J.,信息与电子工程，2003.3(1):1-5.6车武军，杨勋年，汪国昭.动态骨架算法J,软件学报，200314(4):818-823.7吴月娥，周康源，李传富等。基于 LevelSet 的医学图像分割。北京生物医学工程。2006,25(3):240-2438杨新图像偏微分方程的原理与应用M,上海交通大学出版社，2003 年第一版.9R.Kimmel,D.Shaked,N.Kiryati,A。M。Bruckstein。SkeletonizationviaDistanceMapsandLevelSetsJ。ComputerVisionandImageUnderstanding,199562(3):382-391.10AlexandruTelea,JarkeJ。vanWijk。AnAugmentedFast