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

一种基于水平集的骨架提取方法鲍征烨，周卫平，舒华忠 (东南大学 影像技术实验室 南京 210096)摘要：本文实现了基于level set方法的骨架提取。简要介绍了level set及其快速算法快速行进法（Fast Marching Method），并且在此方法的基础上提出了一种骨架提取算法，并提取骨架，通过与传统FMM算法比较，实验结果证明该方法简单有效，并且具有很好的鲁棒性。关键词：水平集，骨架提取，距离变换，FMM，阈值 A method of extracting skeleton based on Level SetBao Zheng-ye，Zhou Wei-ping，Shu Hua-zhong （lab of image science and technology，Southeast University，NanJing，210096）Abstract: In this paper,we use a method based on Level Set to extract the skeleton of objects. We introduced Level Set and Fast Marching Method. And here it is used to extracting skeleton of objects. We propose a method for extracting skleton based on Fast Marching Method.This method is very simple and the result is effective.Key words: Level Set, Skeleton Extraction, Distance Transform, Fast Marching Method, Threshold0 引言传统的提取骨架的方法有基于数字形态学的方法和基于距离变换的方法，两种方法在连续域都是完备的。但在离散域各有其优缺点，细化得到的骨架具有良好的拓扑性，但是骨架点的位置却不准确；基于距离变换的方法在骨架点的准确度上效果好，但连通性一般却很难保证。本文所采用的基于Level Set 方法1的骨架提取方法属于基于距离变换的方法，和一般的距离变换方法相比在于具有更好的稳定性以及拓扑无关性 2。曲线在演化过程中可能会产生尖点、断裂为多条曲线，或者两条或多条曲线融合为一条。Level Set 方法可有效地处理这些情况，缺点是计算复杂度大。直到sethian提出了 Fast Marching Method(FMM)，有效降低了Level Set的运算复杂度。Level Set的方法才开始广泛运用。基于上述认知，本文实现了基于FMM3的骨架提取方法，并且在此基础上加以改进。该方法计算简单，更稳定。而且从试验结果看，提取骨架准确性和鲁棒性相当好。 1 FMM方法以二维情况为例，简单介绍FMM方法3。假设(T)是定义在二维平面的曲线，F是其法线方向上的速度。考虑曲线运动的特殊情况，运动速度F0，即曲线(T)是一直向外运动。假设曲线经过指定点的时间为T，那么T满足 （8）在初始曲线上，T(，)=0。式(8)即是著名的Eikonal方程的一种形式。利用逆向差分法，可以根据下式得到式（8)的稳定解9: (9)式中， 和分别为后向和前向差分算子。; (10)FMM算法中( 为常量为图像灰度的梯度) 下面是FMM方法的具体算法3，4，5(1)初始化。KNOWN点：即是曲线(0)所在的网格点，或指定的种子点，并记时间。INSIDE点:考察KNOWN点在曲线外的4 邻点，如果有不是KNOWN点的，则初始化为Acctive点，并赋予到达时间，将所有Acctive点放入一个排序堆栈中，排序堆栈按照每点的到达时间由小到大排序。Faraway点:剩余的点初始化为Faraway点，并记到达时间。(2)曲线演化。假设点是所有INSIDE点中具有最小时间的点，则标记点为KNOWN点，并将点从INSIDE点中删除。考察点的4邻点:若是KNOWN点，则不改变时间;若是INSIDE点，则更新该点时间，并调整其在排序堆栈中的位置;若是Faraway点，则将其标记为INSIDE点，更新该点时间，并将其放入排序堆栈中。若某一点的到达时间大于指定阈值，或排序堆栈为空，则循环结束，否则转到。地方。Sethian在文献3中详细分析了快速行进法的计算复杂度为，这里N为图像的点数。显然，FMM比水平集的直接数值计算法的计算复杂度小多了。2 基于FMM的骨架提取算法我们讨论如何改进基于FMM的骨架提取算法，由文献9知骨架点就是由于紧凑的边界线段，在FMM界面传播过程中消失的点。所有在界面传播的点都来自于边界，边界里面的点在边界上都有一个源点。我们只需确定演化曲线上的每一点来自边界线上的哪一点。我们为每个网格点增加一个距离值设为U10，初始时，仅在边界线上T0的点选取任意的一个边界点，从U1这个点开始，我们沿着边界线单调的增加1，如图2所示。 图2 U值初始化示意图，a)，c)为原始图像，b)，d)为增加了U值的图像10Figur2 Objects (a,c) and the order in which U is assigned to their boundaries (b,d) 初始化边界的U值后，U值随着FMM的迭代得到整幅图像的U值。随着曲面的演化，U值的传播标志着初始边界的U值到达由初始边界围成的里面每个网格的位置，这样整幅图像每个象素点就有了一个U值。 相邻的两个点的U值的最大差值是，如果U的差值大于2，说明他们不是来源于相邻的点。我们以长方形的骨架为例。图3显示了U沿着边界进化3次的结果。平行边界的，没有骨架点。边界点上的U值之间的差值为1。然而，沿着骨架线，如图3b所示，差值增加。图3 U随着FMM演化示意图a)边界线和骨架，b)U值演化3次的结果10。Figure 3 Rectangle and its skeleton (a). Detail of the augmentedFMM result around the rectangles lower left corner一旦计算出全部网格点的U值，图像的骨架S即为： （11） 骨架检测算子d (12)为图像的边界，这里为KNOWN点组成的曲线，也即为零水平集组成的曲线。t是我们选择的阈值，可以对骨架进行滤波，保留的点就是骨架点，实践证明，不同的阈值可以保留不同的细节11。 如上述提到，当U随着边界演化时，U值与相邻点的差值会越来越大。越靠近骨架的点，离边界越远的点，以及初始曲线越尖锐部分的点，U值的差距就越大。t与骨架检测算子d进行比较，t值越大，更多大额细节被忽略，也忽略了由于边界噪声形成的骨架；t值越小，更多的细节被保留，也保留了一些由于边界噪声形成的错误骨架10。这是一个相对的过程。保留更多细节的同时，也会使骨架保留了一些不必要的东西。 t=20 t=100 t=300图4 不同的图像选取不同的阈值的结果Figure 4 Feature-based skeleton pruning for different thresholds t3 试验结果和讨论运用上述算法，进行了实验结果的比较，这是其中3个试验结果，分别加入了椒盐噪声，细线条干扰噪声和粗线条干扰噪声，如图5、6、7所示。图5表示的是在图像中加入椒盐噪声后不同中轴提取方法的结果。图6表示的是在图像中加入干扰细线条的噪声后不同中轴提取方法的结果。图7表示的是在图像中加入干扰粗线条的噪声后不同中轴提取方法的结果。图5 a) 原始图像 b)细化算法 c)传统FMM方法 d)本文算法(t=100) Figure 5 a) Original b) Thinning c) FMM d)Our Method(t=100) 图6 a) 原始图像 b)细化算法 c)传统FMM方法 d)本文算法(t=100)Figure 6 a) Original b) Thinning c) FMM d)Our Method(t=100) a） b） c） d） e）图7 a) 原始图像 b) 细化算法 c)传统FMM算法d)本文算法(t=100) e)本文算法（t200）Figure 7 a) Original b) Thinning c) FMM d)Our Method(t=100) e) Our Method(t=200)由实验结果可知，在对待椒盐噪声时，传统的细化算法和FMM算法以及本文的算法效果差不多，但是在保证骨架的拓扑性和完整性方面，显然FMM和本文算法更具优势，而在加入干扰细线条后，从图6可以看出运用本文算法和FMM算法干扰细线条噪声基本被滤掉，并且骨架仍然保持较好的完整性，而细化算法受到了明显的干扰而基本不能实现理想的骨架提取，在加入粗线条的干扰噪声后，本文算法的优势就体现出来了，相比FMM得到了更好的结果。4 结语本文基于Level Set方法实现了骨架提取，在sethian提出的快速算法快速行进法的基础上进行了改进，改进算法不需要进行繁琐的奇点检测的运算，简化了FMM的运算复杂度，另外通过设阈值可以滤除噪声，在保持骨架完整性和滤除噪声方面效果相比经典的细化算法和传统的FMM算法有非常明显的优势，效果很理想。参考文献1 Osher S,Sethian J. Fronts propagating with curvature dependent speed:algorithm based on the Hamilton-Jacobi formulationJ. Journal of ComputationalPhisics, 1988 79(1):12-49.2 杨猛,汪国平,董士海 基于Level Set的曲线演化,软件学报，2002 13(9):1858-1865.3 Sethion J. A Level Set Method and Fast Marching Method:Evolving interfaces in Computational Geometry,Fluid Mechanics,Computer Vision, and Material Science.Cambridge University Press,1996.4 Sethion J. A Fast Marching Level Set Method for Monotonically Advancing Fronts. Proc.Nat.Acad.Sci. 1996 93(4):1591-1595.5 张若文,滕奇志,孙晓刚等.一种快速简便的图像骨架变换方法J.,信息与电子工程, 2003.3(1):1-5.6 车武军,杨勋年,汪国昭. 动态骨架算法J,软件学报, 2003 14(4)：818-823.7 吴月娥，周康源，李传富等。基于Level Set的医学图像分割。北京生物医学工程。2006，25(3):240-2438 杨新 图像偏微分方程的原理与应用M, 上海交通大学出版社, 2003年第一版.9 R.Kimmel，D.Shaked，N.Kiryati，A。M。Bruckstein。 Skeletonization via Distance Maps and Level SetsJ。 Computer Vision and Image Understanding, 1995 62(3):382-391.10 Alexandru Telea， Jarke J。 van Wijk。 An Augmented Fast Marching Method for Computing Ske