基于水平集模型从不完整点集中进行骨架提取的算法
摘要 本文提出一种基于水平集模型的从图像的不完整点集中提取曲线骨架的算法。我们的算法主要是结合定向点集合的广义旋转对称轴(rsa)对原有的水平集骨架提取算法进行改进,针对图像的点集数据大量缺失的情况的形状进行骨架化处理。具体来说,使用一种迭代算法来计算一个点集的rsa,并对非圆柱形连接区域的特殊处理进行补偿计算出广义圆柱形区域的鲁棒性曲线骨架。实验证明我们的骨架完全满足骨架点位于中心且拓扑结构清晰。 关键词 水平集模型;骨架提取;不完整数据;旋转对称性 中图分类号tp39 文献标识码a 文章编号 1674-6708(2013)85-0226-02
1 简介与rsa概述
骨架化是图像分析与形状描述中一个非常重要的变换,骨架是图像几何形态的重要拓扑描述[1,2]。传统的水平集骨架提取算法[3]只能适用于点集数据完整的情况,而不完整的点集使得提取出的骨架不连续或偏离物体中心,失去其本身的拓扑意义。 在本文中,我们提出了一种算法直接对不完整点集数据进行骨架提取。算法的目标是在没有数据序列作为互补的援助下处理重要丢失数据。不考虑反射对称性,曲线骨架被认为是一个形状的一维结构的旋转对称轴(rsa)。这是实现对不完整点数据的强大处理的一个重要步骤。
我们方法的前提是:the shapes of interest should be covered by generally cylindrical regions except at their joints,尤其针对大量丢失数据区域。为了计算rsa,我们定义一个定向点为rsa点,关于定向标本的本地子集x旋转对称,并要求: 1)最小化和x的法线之间的角度差异。换句话说,就是让尽可能与这些法线角度相同,与旋转对称的概念相一致; 2)最小化到x中点的法线的延长线距离的平方和。 图1说明了我们的定义,图2显示了对重要遗失数据起作用。可清楚看出我们的算法对大量丢失数据不敏感。图3强调了the point that orientation information可以有效地弥补在曲线骨架提取中数据的缺失。
2 通过rsa的曲线骨架提取 2.1 rsa与骨架点的计算
令为一个点集的样本点,通过的切平面,方向为,在离的一个小于的距离内识别一个点集样本点的窄带,这个厚度值是一个全局参数,在这里把它设置为2.5%。
对于复杂的形状,切平面可分割为多个形状子集。因此,我们首先需要从窄带内部进一步确定附近的点集样本点的邻节点。一般来说,在整个窄带上配置这些点是不现实的。不过,我们可以避免解决一个全面的聚类问题,因为。
因此,我们利用mahalanobis距离以获取有关邻节点。我们采
用mahalanobis距离算法来计算点集样本点到法线之间的距离。在点的相关临节点通过计算在基于图的mahalanobis距离连通域上定义:我们首先以为根结点执行广度优先搜索,在围绕的窄带区域内递归添加点集样本点。当数据集随设定的阈值变化,最后计算出的rsa点仍然相当稳定,因为rsa定义本身对丢失的数据具有鲁棒性。因此,我们在实验中选取相对aggressive的阈值。
在样本点,我们希望找到一个通过的最优切平面,models它的最佳旋转对称性。具体来说,的法线必须最佳旋转对称于中的点的法线。相应的优化问题是困难的,非线性的,因此,我们通过迭代的方法解决它。我们定位一个初始方向,迭代更新这个方向通过解下式包含在平面法线和点法线之间的角度变化从相关邻结点与当前切平面联系: 2.2 joint的处理
虽然在分支区域中,计算出的骨架是一个一维结构,但是在joints处并不能保持这样的一维结构。事实上,joints区域大体上为非圆柱形,没有最佳切平面。因此,rsa点在joints处比较分散。我们利用空间的一致性来解决这个问题:close-by samples over the underlying shape of the point set should correspond to close-by skeletal samples。为执行空间的连贯性,我们在rsa点应用拉普拉斯平滑技术。此外,不完善的切平面导致的骨骼集的噪声同时可以被去除。
2.3 水平集骨架提取
我们讨论在fmm的基础上改进算法,结合源点扫描法的精神,用相对简单的计算直接得到骨架。骨架点是由于紧致的边界线段,在界面传播过程中消失的点。也就是说,所有在界面传播的点都来自于边界点,边界里面的点在边界上都有一个源点。所以我们只需确定演化曲线上的每一点来自于边界线上的哪一点。 给定物体的边界,关于的距离变换定义为: (4)
为每个点分配了到边界上最近点的距离,其中。用fmm计算的距离值distance。引入fdt包含两个参数每个点的distance值以及得到这个值的边界点y。
我们把任意两点和之间的距离记为,点的距离方程为。 引入一个边界参数值,初始时,仅在边界线上t=0的点选取任意的一个边界点,从wm=1这个点开始,我们沿着边界线单调地增加1。
初始化边界的wm值之后,wm值随着fmm迭代得到整幅图像的w值。
随着曲面演化,wm值的传播标志着初始边界的wm值到达由初始边界围成的里面每个网格点的位置,这样整幅图像就有了一个w值。 如果当前点的4邻域点wm的差值大于,说明他们不是来源于相邻的点,因为相邻的两个点的wm值的最大差值是。我们仅仅把当
前点的wm值的邻域向更远的地方推进。
一旦计算出全部网格点的值,图像的骨架s即为:
我们选择阈值s对骨架进行滤波,保留的点即骨架点。根据实践证明,骨架的检测算子非常的健壮,而且我们能得到连续的骨架。实际上,相邻点,点的wm值和wml的wm2差值超过给定的阈值s的话,一定有相邻点和它的相邻点的wm值超过s。直观地讲,是因为由于每个网格点计算t值的时候满足方程。
如果图像中间有洞:分别从不同方向初始化wm值,则图像有wml和wm2。骨架为: (7)
3 实验结果与对比分析
为了证明本文方法的鲁棒性,我们选取了血管图像进行实验,因为血管的形状满足本文的前提,即:血管的形状满足血管的分支处可以被圆柱覆盖,且血管的连接处的非圆柱覆盖处我们可以去处理。特别的,我们把点放在物体边缘的边界球面作为初始化节点。在每个分支的初始化节点,我们生成一系列的样本点。
在图4中,我们展示了以为初始节点的骨架提取。图4(a)为原始数据图像,是一个彩色的血管图。我们把它变为灰度图像,如图4(b)所示,由于这种变换,导致了一部分数据缺失。图4(c)使用传统的水平集方法对图像进行骨架化提取,由图可以看出,骨架严重偏离了中心位置,而且产生了很多不必要的毛刺。图4(d)
是本文rsa处理后的骨架提取效果,我们可看出我们的方法提出的骨架一维连续位于血管中央,对数据的大量缺失不敏感。 4 结论和未来工作
骨架(skeleton)是图像几何形态强大的直观拓扑描述,特别是圆柱分支形状和圆柱分支的连接处。但是现实应用中组成图像的点集数据可能会丢失,使得骨架提取的应用受到很大的局限性。我们的方法建立在广义对称轴旋转的曲线骨架提取的概念之上改进了原有的水平集算法,它消除了对有显著丢失数据的图像敏感性。实验与传统的水平集方法进行了效果对比,展示了我们的算法的有效性。我们将关注于将算法拓展到更实际的应用当中去,比如处理二值化后数据大量丢失的dsa脑血管图像的骨架化处理。进一步的工作将在下一步展开。 参考文献
[1]blum.h.a transformation for extracting new descriptors of shape[m].mit press,1967:362-380. [2]blum.h. biological shape and visual science[j].theoretical biology,1973,38:205-287 [3]hilaga,m.,shinagawa,y.,kohmura,t.,and kunii,t.l.2001.topology matching for fully automatic similarity estimation of 3d shapes.in proc.of siggraph,203-212.
因篇幅问题不能全部显示,请点此查看更多更全内容