曲线重建的跟踪算法研究.pdf

第26卷第8期 怀化学院学报 V01．26．No．8 2007年 8月 JOURNALOFHUAIHUA UNIVERSITY Aug．，2007 曲线重建的跟踪算法研究 齐秀丽 (绥化学 院 数学系， 黑龙江 绥化 152061) 摘 要：由数据点云进行曲线重建是逆向工程 中的一个重要 问题 ．寻找一种从无序散乱点集 出发重建 曲线的有 效方法，是人们反复研究探索的问题 ．研究了用简单曲线拟合平面上的无序点集的跟踪算法 ． 关键词：数据 点云； 拟合； 重建曲线 中圈分类号：024 文献标识码 ：A 文章编号：1671—9743 (2007)08—0019—03 1 引言 逆向工程 的一个主要任务是 由物理模型经过数据采集 、数据点云预处理 、曲面拟合和建立 CAD几何表 示模型 ．逆 向工程的核心问题是根据采集到的数据点云重建曲线 、曲面 ．由数据点云进行曲线重建是逆 向工 程中的一个重要问题 ，广泛应用在逆向工程与计算机视觉当中 ．寻找一种从无序散乱点集出发重建曲线 的有 效方法 ，是人们不断讨论 的问题 ，其间要考虑到计算量 、准确度等因素作为评价重建方法优劣的衡量标准 ． 本文研究了平面无序点集 曲线重建的跟踪算法 (详见参考文献 [1])，得到一些结论 ． 2 跟踪算法简介 用简单曲线拟合平面上的无序点集的跟踪算法 ，是针对从一个无序散乱点云出发重建曲线的问题而给出 的 ． 2．1 设{P l =1，2，A}为原始数据点集 ．将其投影到一个 网格平面上 ．含有数据点的网格点则称为黑点， 所有的黑点构成平面区域记为 n． 定义 平面上两个网格点 P(i，)，Q(m，n)的距离 d(P，Q)=I —m I+I —n1． 定义 平面上网格点 P的权值 (P)： fmin(d(P，Q)IQ 隹n) P∈n 66(P)： { tO P n 2．2 确定初始点，建立局部坐标系 根据 网格点权值的定义 ，选出适当的网格点为初始点 Q。，选择跟踪方 向，建立点 Q。处的局部坐标系，后面 要建立起一个有限跟踪点列 {Q。，Q。，A，Q }． 收稿 日期 ：2007—07—10 基金项 目：绥化学院青年教师科学技术研究资助项 目，项 目编号：QK071001． 作者简介 ：齐秀丽 (1974一)，女，黑龙江绥化人 ，绥化学院数学与计算科学系副教授 ，主要研究计算数学等 · 2O · 怀化学院学报 20o7年S月 2．3 跟踪方 向的确定 对于当前跟踪点 Ql，作 以O 为圆心，以，为半径的圆，在圆内考察与 的夹角小于 0的数据点PI(即为 圆内的点)．规定 为两个特殊方向的夹角．加入调节因子 ，而构造，|I+ ，2．要选取适合 ，而使得，+=．I = rain． 2．4 跟踪步长的确定 构造 目标函数 ，3，在跟踪方向 上确定新点 ．．．目标函数 ，3取得最小值时，可确定跟踪步长 ． 2．5 终止条件 当跟踪点列满足跟踪条件时，终止跟踪过程 ． 2．6 后置 处理 与拟 合 对于点 ，依据 处网格的权值为二和宽度d，寻找调整点 ．对跟踪点歹jI中的所有点进行这样的后置处 理 ． 3 算法分析 3．1 在整个算法里面，可以影响到重建曲线位置的人为因素有：定义的网格点权值 (P)、网格宽度 的选 取、影响半径 ，的选取 、调节因子 的值 ． 3．2 权值 二(P)的定义，能够反映出该网格点副区域外部的距离 ．权值 (P)，影响到初始点位置的选取，依 照2．1中定义的权值最大的网格点应该落在区域的中心，但不一定出现在数据点云最稠密的位置 ． 借鉴概率论中数学期望的计算办法，有 以下方法寻找初始点，可以选取在数据点云相对密集的位置 ． 对于权值最大的点 Q。，以其为心，以 (P)为半径，作邻域 Ⅳ。(Q。， (P))，考察该邻域 内的所有数据点