第 42 卷第 12 期 2008 年 12 月
Jo urnal of Zhejiang U niversity ( Engineering Science)
浙 江 大 学 学 报 ( 工学版)
Vol . 42 No . 12 Dec. 2008
DO I : 10. 3785/ j. issn. 10082973X. 2008. 12. 012
Fig. 2 Result s of different split algo ri分终止条件包括叶
结点内的点数量或叶结点的最大简化误差 . 对骨架提 取而言 ,处理模型表面的高曲率的细节或噪声点是非 常困难的 ,因此希望通过简化过程来 “抹平” 这些表面 细节以及去除噪声数据 . 本文以叶结点数量为剖分终 止条件 . 为同时控制叶结点数量和简化误差 ,建立了 叶结点的一个优先队列 . 优先队列排序准则为 OBB 的面积 AL 与体积 V L 的混合函数 O ( L ) =α AL + ( 1 α ) V L ,式中 : α为权系数 ,本文实验中取 0. 3. 1. 2 定义简化模型 完成点云数据的 OBB Tree 构建后 , 可以根据 OBB Tree 建立一个不但有几何信息而且有拓扑信 息的几何模型 . 为表述方便 , 先约定以下符号 . 1) T ( P) : 由点云数据 P 所构建的 OBB Tree ,| ( ) T P | 表示 OBB Tree 的叶结点数目 . 2) L i 、 B ( L i ) 及 P ( L i ) : L i 表示 T ( P) 的第 i 个 叶结点 , B ( L i ) 表示 L i 的有向包围盒 ; P ( L i ) 表示 L i 内所包含的部分点云数据 . 3) M ( T ( P) ) : 由 T ( P) 及 P 所确定的几何模 型 . M ( T ( P) ) = { V , E} , 其中 , V = { V ( x , y , z ) , N } 为 M ( T ( P) ) 顶点的坐标以及法向量等几何信息 , E 为拓扑信息 . V 、 E 值按下面的方法确定 . 4) 几何信息 V i = { V i ( x , y , z ) , N i } :每一个叶结 点 L i 对应一个顶点 V i . V i 的坐标 V i ( x , y , z ) 等于 B ( L i ) 的形心坐标 . V i 的法向量 N V i 等于 P ( L i ) 各点 的法向量 N p 的加权平均值 , 即
确定 M ( T ( P) ) 后 , 可由 Dijkst ra 算法确定点云 数据任意两点间的最小测地距离 . 1. 3 讨论 点云的分片数目 n 决定了简化模型对原模型的 近似程度 . n 越大 , 简化模型和点云数据间的几何近 似误差就越小 , 但相应分片和后续骨架处理过程的 计算量也越大 . 对骨架提取而言 , 在拓扑不变的情况 下 , 同一模型在不同简化程度下的多分辨率表示的 骨架应基本一致 . 这也是 Thinning 方法的基础 , 因 此 , 理论上而言只要保证简化模型与原点云数据拓 扑保持不变 , n 越小越好 . 但如果 n 过小 , 拓扑发生 变化时会影响骨架提取效果 , 在图 3 中 , 当简化率取 1/ 400 时 , 会导致部分骨架丢失 . 在本文实验中 , n 取 点云数据点数量的 1/ 50～1/ 120 左右 .
A ne w method for extracting feature skeleton from point cloud
ZOU Wan2ho ng1 , C H EN Zhi2yang2 , YE Xiu2zi1 , ZHAN G San2yuan1
( 1 . S t ate Key L aboratory of CA D an d CG , Zhej i an g U ni versit y , H an gz hou 310027 , Chi na;
浙江大学学报 ( 工学版) 网址 : www. journals. zju. edu. cn/ eng
基金项目 : 国家 “863” 高技术研究发展计划资助项目 (2007AA01Z311 , 2007AA04Z1A5) . 作者简介 : 邹万红 (1976 - ) ,男 ,湖南郴州人 ,博士生 ,主要研究方向为点模型几何造型 、 计算机图形学、 CAD. E2mail : wh_zou @zju. edu. cn 通讯联系人 : 叶修梓 ,男 ,长江学者特聘教授 ,博导 . E2mail : yxz @zju. edu. cn
收稿日期 : 2007209207.
丢失一些模型特征 ,显得较为粗糙 . 本文提出了一种新的点云骨架提取方法 , 算法 大致分以下几个步骤 : 1) 建立简化模型 : 用空间层次剖分的方法对模 型进行分片 ,为每个分片计算一个简化表示 ,可建立 点云数据的简化模型 ; 2) 形成初始骨架 : 根据离散 Mo rse 理论 , 可以 从简化模型中确定特征点 , 用测地线依次连接这些 特征点形成了初始骨架 ; 3) 骨架内推 : 采用可见反力场方法 ,可以将位于 模型表面的初始骨架 “推” 至模型内部 , 对内推后的 骨架按角度聚类和光顺后就得到了最终的骨架 .
Mo rse 理论 ,从简化模型中提取主要的特征点 ,用测地线连接这些主要特征点可得到模型的初步骨架 . 采用可见反
力场方法将初步骨架内推至模型内部 ,对内推后的骨架光顺及聚类后形成最终骨架 . 该方法能够直接处理带噪声 数据的大规模点云数据 ,所形成的骨架连续 . 关键词 : 点云 ; 骨架 ; 层次体包围盒 ; 特征点 ; 可见反力场 中图分类号 : TP391. 41 文献标识码 : A 文章编号 : 10082973X(2008) 1222103205
Fig. 1 Sp here Tree and OBB Tree
L i 和 L j 间添加一条边 E ij = V i V j . 若 B ( L k ) 没有相
交的包围盒 , 为避免叶结点 L k 成为孤立的顶点 , 将
第 12 期
邹万红 ,等 : 一种新的点云数据特征骨架提取方法
2105
L k 与其最近的叶结点的包围盒形心相连 .
中轴是模型的最大内切球球心的轨迹 , 一维骨 架是中轴的子集[ 1 ] . 一维骨架常简称为骨架 ,作为模 型形状信息的低维表示 , 骨架被广泛应用于虚拟导 航、 对象识别和匹配 、 计算机动画 、 三维模型表示和 [2 ] 三维模型编辑 . 目前已有多种方法可用于网格模 型提取骨架 [ 3 ] . 本文的处理对象是点云数据 ,与网格 模型相比 ,点云数据缺少连接拓扑信息 ,多数方法不 能 直 接 用 于 点 云 数 据 的 骨 架 提 取. 虽 然 基 于 Voro noi 图的几何方法 [ 4 ] 能直接处理点云数据 , 但 其显著缺点是对噪声数据比较敏感 . 另一种直接从 点云数据提取骨架的算法是 Level2set 方法 [ 5 ] ,这类 方法同样受噪声数据的影响 , 而且其提取的骨架常
2 . Col le ge of S of t w a re , Zhej i an g U ni versit y of Technolog y , H an gz hou 310014 , Chi na)
Abstract : A simplified geometric model was constructed for point clouds , which is not sensitive to noises. Then feature points were found from the simplified model by Morse theory. Connecting those features by geodesic lines , an initial skeleton could be obtained , which were pushed inside the point cloud by visible repulsive forces. The skeletons were then smoothed and clustered with angle threshold to form a final skeleton. The method can process large point cloud model with noises , and the extracted skeletons are continuous. Key words : point clo ud ; skeleto n ; hierarchical bo und volume ; feat ure point ; visible rep ul sive force field
一种新的点云数据特征骨架提取方法
邹万红1 ,陈志杨2 ,叶修梓1 ,张三元1
( 1. 浙江大学 CAD &C G 国家重点实验室 ,浙江 杭州 310027 ;2. 浙江工业大学 软件学院 ,浙江 杭州 310014)
摘 要 : 为解决点云数据的线骨架提取问题 ,为点云数据的后续几何处理的奠定基础 ,提出了一种新的点云数据骨 架提取方法 . 通过对点云数据的空间层次剖分后建立其简化模型 , 可有效地避免噪声点对骨架的干扰 ; 根据离散
与现有的点云数据骨架提取算法方法相比 ,本文 的方法对噪声数据不敏感 ,能直接处理大规模的点 云 ,而且计算速度快 ,所抽取出来的骨架稳定性较好. 不同于具有严格数学定义的模型中轴或中值 面 ,特征骨架属于线骨架[ 2 ] . 线骨架没有严格的数学 定义 ,通常通过一些定性的方法如连续性 、 中心性对 所提取的骨架进行度量 . 本文所提取的骨架由中心 点和各特征点之间连接构成 ,满足连续性要求 ,通过 可见反力场将骨架内推 ,可满足中心性要求 .
NV i = FZ (
p ∈P( Li)
∑ D ( p ,V )
i
×N p ) .