数据简化中的边界提取方法

赵伟玲

(黑龙江科技大学 现代制造工程中心, 哈尔滨 150022)



数据简化中的边界提取方法

赵伟玲

(黑龙江科技大学 现代制造工程中心, 哈尔滨 150022)

针对三维点云数据简化过程中边界特征容易丢失问题,研究了一种点云边界特征提取方法。首先，对点的k近邻进行查找,并进行点的球拟合计算,得到拟合球的半径、点的曲率、点到球心距离。其次,通过数据点周围点的分布均匀性、自适应调节参数公式中的阈值,可以达到检测边界特征的目的。由不同模型的实验数据表明,该算法提取的边界满足了后期数据简化所需。

逆向工程; 点云数据; 曲率; 边界提取

0　引　言

随着产品数字化和快速制造技术的发展,逆向工程得到了越来越多的应用和研究,其各环节的智能化及自动化一直是这一领域的目标。产品逆向工程设计的初期,通过非接触式三维设备测量可得到点云数据。边界特征是表达点云几何特征的重要因素之一,在后续的数据处理中对建模的质量和精度具有重要作用。三维点云数据简化过程中边界特征容易丢失问题,快速从离散点云信息中提取出边界,成为基于点云的逆向工程建模研究的核心之一。

目前,国内外有很多学者对测量数据的边界特征识别进行了研究。张献颖等[1]通过建立点云的三角网格模型提取点云边界特征。该算法边界特征提取准确,但耗费大量的系统资源,运行速度慢。胡鑫等[2]采用图像处理中的梯度求解法来估算数据点的法矢和曲率,通过阈值法得到候选边界点,再利用曲率极值法得到最终边界点,拟合最终边界点得到边界曲线。贺美芳等[3]用局部基面参数化方法求出曲率极值点并从中提取边界点，王宏涛等[4]提出了采用八叉树划分点云空间保留叶节点中距离重心最近点的方法,陈义仁等[5]利用双向最近点搜索算法对提取出来的特征点进行排序并自动生成边界曲线,钱锦锋等[6]由数据点及周围点的分布均匀性进行边界提取。笔者在此基础上,改进了一种点云边界提取方法。

1　数据预处理

1.1k近邻搜索

在数据预处理中,搜索数据点集中每个点的k近邻几乎是一项最基本的工作。这是因为测量得到的散乱数据只包含数据点的三维坐标值,点与点之间没有明显的几何分布信息,都呈散乱无序状态,因此必须建立数据点之间的空间拓扑关系进而搜索每个点的k近邻。散乱数据点k近邻的建立能够极大地简化散乱点云数据后期处理过程的计算复杂度,降低其计算量,并提高重建结果的精度和可靠性。目前常用的k近邻计算方法有空间单元格法、八叉树法和k-d树法。这里选择采用空间单元格法[7-8]。多组实验及经验表明,一般k值取10～30之间是一个较好的选择。

1.2基于球面拟合计算

三维测量数据在小范围内理想意义上所在的曲面应该是很光滑的,所以任何点的局部邻域都可以用平面或者曲面进行很好的拟合。这里，采用球拟合的方法对点的k个邻域点进行拟合,可以很简便得到点的曲率值,为边界提取做必备准备工作。

点p的距离最近k个点Pi(xi,yi,zi)(i=1,2,3,…,k)称为p的k-近邻,通过点p及其k个近邻点,利用最小二乘法拟合便可以得到球心坐标和球半径r,则点的曲率为1/r。

首先计算

(1)

(2)

接着求取矩阵的广义逆矩阵M-1,及F=M-1·N,假设求出的F=[f(0)f(1)f(2)f(3)]T,则

(3)

2　点云边界提取方法

在数据点及周围点的分布均匀性提取边界算法基础上,提出了一种基于曲率的点云边界特征提取算法。该算法根据曲率能反映边界特征,较好的保持原有模型的边界信息[9]。

首先,进行点p的k近邻角度标准差计算,得到点云的外边界。然后,根据点的曲率以及点离拟合球面的距离综合参数补充得到点云边界点。图1是点p所在拟合球面及其距离示意图,d是点p(xp,yp,zp)到拟合球心O(x0,y0,z0)的距离,r是拟合球半径,点p的曲率则用1/r表示,点p到拟合球的距离为b=d-r。

图1　点的球拟合距离

通过点p的k个邻域点,根据球拟合方法可以很容易得到球心O坐标及半径r的大小。这样,得到点p到球心O的距离为

(4)

(5)

其中,α为系数。通过调节系数α可以改变函数值。λ越大,则说明点成为边界的可能性越大。

拟合球的半径反映了被测物形状的起伏程度。通过曲率值的不同对点云进行分片处理,分片的数目可根据曲率的变化量采用自适应法。通过文中函数与设定阈值的比较、距离d与k近邻点到圆心的平均距离比较,可以找到并提取出边界点。

3　实验结果与分析

3.1某加工件的边界提取分析

使用自主研发设备进行非接触式三维测量,点的个数是211 134个。图2是某加工件的点云数据及特征提取显示效果图。其中,图2a是由自主研发的三维扫描系统测量某加工件所得到的点云数据显示效果图,图2b是点云数据经过文献[6]边界提取的显示效果图,图2c是点云数据经过文中方法处理后得到的特征提取效果图。从显示效果可以看出,图2b中的中间轴位置提取的圆形特征不全面,而且四周有的扇形也提取不完整,但是在图2c中可以看出,这些问题都不存在。该方法很好地实现了某加工件的特征提取,为后续的点云简化等数据处理提供了很好的依据。

图2　某加工件的点云数据及特征提取显示效果

3.2米老鼠头像的边界提取分析

这里使用的是米老鼠头像模型的点云数据。图3a是米老鼠半个头像的点云数据显示效果图,图3b是点云数据经过文献6得到的边界特征显示效果图,图3c是点云数据经过文中方法处理后得到的特征提取效果图。比较图3a和3b,图3a中米老鼠的鼻子、嘴巴等一些重要部位的特征利用文献[6]没能提取出来;比较图3b和图3c看出,图3c比图3b多了鼻子、嘴巴、眼睛等重要部位,而图3c中这些特征正好可以把米老鼠的重要特征很好地显示出来。所以，文中方法实现了对米老鼠头像的点云数据特征提取,为数据简化所需边界可进行直接有效的提取。

图3　米老鼠头像的点云数据及特征提取显示效果

4　结束语

研究了一种点云边界特征提取方法,首先对所有点的近邻搜索,并计算k近邻点的球面拟合,得到球半径、点曲率、点到球心距离等基本参数。然后,通过k近邻点的分布均匀性及自适应调节参数公式中的阈值,便可检测出点云数据的边界特征。同时,通过对某加工件和米老鼠的数据实例进行实验分析,验证该算法的可操作性。该算法提取的边界虽然还存在遗漏和误判的情况,但是总体来说该算法在保证数据简化所需边界的前提下,能够对点云数据进行直接有效的边界提取。

[1]张献颖, 周明全, 耿国华. 空间三角网格曲面的边界提取方法[J]. 中国图像图形学报, 2003, 8(10): 1223-1226.

[2]胡鑫, 习俊通, 金烨. 基于图像法的点云数据边界自动提取[J]. 上海交通大学学报, 2002, 36(8): 1118-1120.

[3]贺美芳, 周来水, 朱延娟. 基于局部基面参数化的点云数据边界自动提取[J]. 机械科学与技术, 2004, 23(8): 912-

915.

[4]王宏涛, 张丽艳, 杜佶, 等. 测量点集的简化及其隐式曲面重建误差分析[J]. 中国图象图形学报, 2007, 12(11): 2114-2118.

[5]陈义仁, 王一宾, 彭张节, 等. 一种改进的散乱点云边界特征点提取算法[J]. 计算机工程与应用, 2011, 26(4): 1-7.

[6]钱锦锋, 陈志杨, 张三元, 等. 点云数据压缩中的边界特征检测[J]. 中国图象图形学报, 2005, 10(2): 164-169.

[7]赵伟玲, 谢雪冬, 程俊廷. 保留边界特征的点云简化算法[J]. 黑龙江科技学院学报, 2013, 23(1): 83-88.

[8]刘立强. 散乱点云数据处理相关算法的研究[D]. 西安: 西北大学, 2010: 37-42.

[9]刘立国. 点云模型的光顺去噪研究[D]. 杭州: 浙江大学, 2007: 36-38.

(编辑晁晓筠)

Research of boundary extraction method in data reduction

ZHAO Weiling

(ModernManufactureEngineeringCenter,HeilongjiangUniversityofScience&Technology,Harbin150022,China)

Aimedatpreventingboundaryfeaturelossmorelikelytooccurintheprocessof3Ddatareduction,thispaperhighlightsaboundaryfeatureextractionmethodofpointcloud.Themethodinvolvesfirstlyseekingthekcloseneighborsofthesamplingpoint,andobtainingtheballfittingradius,thepointcurvature,andthedistancebetweenthepointandthecenterofthesphereusingtheball-fittingmethod,whilegetting,andthenachievingtheboundaryfeaturedetection,dependingonthedistributeduniformityoftheclosestneighborsofpointandself-adaptiveadjustmentofthethresholdvalueoftheparameterequation.Theexperimentaldatafromthedifferentmodelsverifytheabilityofthealgorithmtogivetheboundaryadequateforthefollow-updatareduction.

reverseengineering;pointcloud;curvature;boundaryextraction

2013-06-20

国家自然科学基金项目(51075128);国家科技重大专项项目(2010ZX04016-012);博士后研究人员落户黑龙江科研启动资助金项目(LBH-Q12019)

赵伟玲(1981-),女,河北省保定人,讲师,硕士,研究方向:逆向工程、计算机视觉、数据处理,E-mail:weilingzhao@126.com。

10.3969/j.issn.1671-0118.2013.05.015

TP391.41

1671-0118(2013)05-0469-03

A