海量点云的Out-of-Core快速均匀精简方法

海量点云的Out-of-Core快速均匀精简方法
【技术领域】
[0001] 本发明提供海量点云的Out-of-Core快速均匀精简方法，可用于精简超出主存容 限的实物表面海量采样数据，属于产品逆向工程领域。
【背景技术】
[0002] 在逆向工程中，为精确表示实物的空间信息，由光栅投影式=维测量仪等扫描设 备获得点云数据规模趋于海量，甚至超出通用计算机主存储器的容量，导致点云数据无法 进行可视化及交互性操作，需要对其进行精简处理。
[0003]目前，点云数据的精简方法分为均匀精简法与保形精简法。均匀精简法利用包围 盒、网格划分等来精简点云数据，能够快速均匀精简点云，但损失部分点云的几何特征。保 形精简算法对点云数据=角化，计算=角面片的法向量，并估计其曲率，基于曲率去除部分 =角面片从而精简数据，能够很好地保留点云的几何特征，但精简速度过低。为能够快速显 示与操作点云数据，应采用均匀精简方法对点云进行精简。
[0004] 为有效均匀精简点云数据，主要的均匀精简方法包括Sun等在《Clouddata modelingemployingaunifiednon-redundanttriangularmesh》 （Computer-Aided Design，2001，33(2) ;183-193)采用包围盒法来简化测量散乱点云数据、叶冬荣等在《基于 二次精简的散乱点云精简方法》（计算机系统应用，2014,23巧）：182-185)首先利用切平面 进行初次精简，然后利用均匀网格法对精简后的点云重采样进行二次精简等。上述方法能 够快速有效的精简点云数据，但当点云数据规模趋于海量，甚至超出通用计算机的主存容 限时，点云数据无法一次性加载到主存中，上述精简方法将无法使用。

【发明内容】

[0005] 本发明的目的是针对目前海量点云的精简方法存在的主要问题，提出一种海量点 云的Out-of-Core快速均匀精简方法，不仅能够快速精简超出主存容限的海量散乱点云， 且能够达到较好精简效果。
[0006] 本发明的目的是通过如下技术方案实现的： 一种海量点云的Out-of-Core快速均匀精简方法，其特征在于；（1)为超出主存容限 的海量点云构建主存-辅存分级存储机制，将海量点云的动态索引结构存储在主存储器 中，将动态索引结构的数据结点存储在辅存储器中；(2)获取海量点云主存-辅存分级存 储机制第句言索引层的结点的集合为冲任一结点；（3)获取集合中结点的 总数厶|'^^将用于存储海量点云最终精简结果的集合钟刀始化为空集；(4)将点集0 初始化为空集，并将结点'包含的点数据添加到点集冲，计算点集嫌]均值点&?，
式中2>;表示点集冲所有点在^^方向的坐标值之和，减示冲数据点的总数， 为点集0所在坐标系的维度；（5)获取点集冲距离Am最近的点C，将g添加到集合/^， ;做重复执行（4)~(5)，直至f二￡ ;(7)伪最终海量点云的精简结果。
[0007] 所述的海量点云的Out-of-Core快速均匀精简方法，其特征在于步骤（1)构建主 存-辅存分级存储机制的具体步骤为；（1)初始化；i<-l，新建CR树的根结点巧；（2)构 建用于存储叶结点子结点数据的点链表P/. ;(3)读取点云文件中第i行点数据4,若/g.为 空，则跳转至（16) ; (4)将点数据/,插入巧；妨根据/,利用CR树动态空间索引的选择子 树算法获取叶结点巧化）若数据库SQLite中对应叶结点/前数据表口存在，则利用数据库 SQLite的读取语句将邱余表头数据外的其他数据拷贝到中，F^A，调整结点K利用 数据库SQLite的删除语句将幼人数据库SQLite中删除；（7)若.巧中元素的总数￡ < ，则构建数据表C，将结点及巧.中的数据存储到口中，其中表头为K巧.中的数据在 后，清空主存储器中的点链表巧，。，并跳转至（15) ; (8)将的子结点转化为点集供利用k均值聚类算法对点集ea行聚类，将点集巧>为A个子集{谷.....&};巧）利用结点/冲的 子结点与点集0的双射关系，将结点/前子结点分裂为k个新的结点{ii...，巧}; (10)若 巧叶结点，J'^1，否则，固龄至（14) ;(11)利用数据库SQLite新建数据表语句构建新的 数据表马，并利用数据库SQLite插入语句将及其包含的点数据存储到￡>,中，其中表头为 其它为f,'包含的点数据，+ 重复（11)，直至i二奏。结束；（13)清空主存 储器中的点链表巧；（14)获取结点/前父结点|：>，^*^1=]5，将1^个新的结点巧，...，|*^ 逐个插入到冲，若冲的子结点总数《>姐，返回巧）；（15)f片1，返回（3) ;(16) 海量点云主存-辅存分级存储机制构建完成。
[0008] 所述的海量点云的Out-of-Core快速均匀精简方法，其特征在于步骤巧）子结点 转化为点集的方法为；将上溢结点的子结点转化为子结点包围盒的中屯、点，转化公式为 A二C牌㈱）似 式中表示上溢结点尸中任一子结点/i的包围盒，C(A')表示包围盒X的中屯、点。
[0009] 本发明与现有技术相比，具有W下优点： (1) CR树与SQLite相结合构建的主存-辅存分级存储机制能有效存储与管理超出主 存容限的海量点云数据； (2) 利用距离均值点最近的点代替每簇点集有效提高了精简效率； (3) 将上溢结点的子结点用其包围盒的中屯、点代替，能够有效表示结点的空间分布， 同时提高了建树效率； (4) 海量点云的Out-of-Core快速均匀精简方法可用于交互性显示与观察海量点云 的几何特征，同时可作为海量散乱点云进一步进行保形精简的预处理工作。
【附图说明】
[0010] 图1是本发明海量点云的Out-of-Core快速均匀精简方法的程序实现流程图； 图2是改进的CR树上溢结点的点集表示效果图； 图3是海量点云主存-辅存分级存储机制结构示意图； 图4~图6是对结点进行k均值聚类的过程示意图； 图7是实施例一海量点云精简试验所采用的一种实物表面样点一一blade点云模型； 图8是实施例二海量点云精简试验所采用的一种实物表面样点一一佛像体点云模型； 图9-11是实例一blade点云模型不同结点层的精简效果图； 图12-14是实例二佛像点云模型不同结点层的精简效果图。
【具体实施方式】
[0011] 下面结合附图及实施例对本发明作进一步说明。
[0012] 图1是本发明海量点云的Out-of-Core快速均匀精简方法的程序实现流程图，可 采用C程序设计语言实现。海量散乱点云精简方法的程序主要模块包括改进CR树结点表 示方法、海量点云CR树动态索引结构的构建、CR树与数据库SQLite相结合实现海量点云 主存-辅存分级存储机制的构建、选取目标结点层及该目标结点层的结点集、获取结点集 中每个结点中距离结点均值点最近的点等。
[0013] 图2是改进的CR树上溢结点的点集表示效果图，将上溢结点的子结点转化为子结 点包围盒的中屯、点，转化公式为 巧'二C(玄(/；)) 似 式中SW)表示上溢结点/冲任一子结点/：的包围盒，CC的表示包围盒X的中屯、点。
[0014]图3是海量点云主存-辅存分级存储机制结构示意图，构建过程的具体步骤为： (1)初始化新建CR树的根结点F,; (2)构建用于存储叶结点子结点数据的点链 表巧；做读取点云文件中第带点数据/，,，若为空，则跳转至（16);(4)将点数据 插入沪t;(5)根据利用CR树动态空间索引的选择子树算法获取叶结点巧化）若数据 库SQLite中对应叶结点/前数据表C存在，则利用数据库SQLite的读取语句将邱余表头 数据外的其他数据拷贝到吗中，F^li，调整结点K利用数据库SQLite的删除语句将 公从数据库SQLite中删 除；（7)若B中元素的总数X<A/，则构建数据表凤将结点饿 ii中的数据存储到口中，其中表头为Kii中的数据在庐么后，清空主存储器中的点链表 Pi,并跳转至（15) ;(8)将的子结点转化为点集供利用k均值聚类算法对点集ea 行聚类，将点集巧>为A个子集{谷:.…岛];(9)利用结点/冲的子结点与点集0的双射关 系，将结点/前子结点分裂为k个新的结点;(1〇)若巧3叶结点，否则， 跳转至（14);(11)利用数据库SQLite新建数据表语句构建新的数据表〇,.，并利用数据库 SQLite插入语句将及其包含的点数据存储到A中，其中表头为其它为气包含的点数 据，y户i*I;(12)重复（11)，直至J?二结束；（13)清空主存储器中的点链表巧；（14) 获取结点/前父结点Fp，F 将k个新的结点巧，.-..馬}逐个插入到/^，若的子 结点总数》>乂^返回巧）；（15) + 返回（3);(16)海量点云主存-辅存分级存 储机制构建完成。
[001引图4~图6是对结点进行k均值聚类算法的过程示意图，其中图4为若干个结点的 示意图，k均值聚类算法的具体步骤；（1)从结点集合FI/;}中随机选取k个对象，作为k个 簇各自的中屯、；(2)分别计算剩下的每个对象到中屯、的距离，并将该些点分别划归到最近 的聚类中，如图5所示；（3)计算每个聚类中所有对象中屯、点的坐标平均值，并将该个平均 值作为新的聚类中屯、；（4)将FtO中全部点按照新的中屯、重新聚类；（5)重复进行（4)， 直至聚类结果不再变化，如图6所示。
[0016] 图7是实施例一海量散乱点云精简试验所采用的一种实物表面样点一一blade点 云模型，应用本发明所述的海量点云的Out-of-Core快速均匀精简方法进行精简。图7所 示blade点云模型包含180524735个样点，总体分布近似均匀，采用光栅投影式=维测量仪 获得，CR树中上溢结点子结点数所容许的最大值为30,构建的CR树动态结构高度为8,平 均结点利用率17. 16,建树时间为1328. 25s，图9为取目标结点层h为7的精简效果图，精 简后的点云包含10619102个样点，精简所用时间为65. 82s，图10为取目标结点层h为6的 精简效果图，精简后的点云包含624653个样点，精简所用时间为43. 05s，图11为取目标结 点层h为5的精简效果图，精简后的点云包含36744个样点，精简所用时间为34. 82s。
[0017]图8是实施例二海量散乱点云精简试验所采用的一种实物表面样点一一佛像点 云模型，应用本发明所述的海量点云的Out-of-Core快速均匀精简方法进行精简。图8所 示佛像点云模型包含90556712个样点，总体分布近似均匀，采用光栅投影式=维测量仪获 得，CR树中上溢结点子结点数所容许的最大值为30,构建的CR树动态结构高度为8,平均 结点利用率17. 03,建树时间为1065. 34s，图12为取目标结点层h为7的精简效果图，精简 后的点云包含5326865个样点，精简所用时间为49. 34s，图13为取目标结点层h为6的精 简效果图，精简后的点云包含313345个样点，精简所用时间为33. 87s，图14为取目标结点 层h为5的精简效果图，精简后的点云包含18432个样点，精简所用时间为27. 65秒。
[0018] W上所述，仅是本发明的较佳实施例而已，并非是对本发明作其它形式的限制，任 何熟悉本专业的技术人员可能利用上述揭示的技术内容加W变更或改型为等同变化的等 效实施例。但是凡是未脱离本发明技术方案内容，依据本发明的技术实质对W上实施例所 作的任何简单修改、等同变化与改型，仍属于本发明技术方案的保护范围。
【主权项】
1. 一种海量点云的Out-of-Core快速均勾精简方法，其特征在于步骤依次 为：（1)为超出主存容限的海量点云构建主存-辅存分级存储机制，将海量点云 的动态索引结构存储在主存储器中，将动态索引结构的数据结点存储在辅存储 器中；（2)获取海量点云主存-辅存分级存储机制第A层索引层的结点的集合 F+i+O，/：为冲任一结点；⑶获取集合Π/.沖结点的总数^ ? P i，将用于存储海量点 云最终精简结果的集合辨刀始化为空集；(4)将点集供U始化为空集，并将结点/丨包含的点 数据添加到点集沖，计算点集(61?均值点fw，式中Σι表示点集?ψ所有点在j轴方向的坐标值之和，λ表示?ψ数据点的总数，i/ 为点集你斤在坐标系的维度；（5)获取点集沖距离€"最近的点f，将譬添加到集合_， 重复执行（4)~(5)，直至I' = i：;(7) /?最终海量点云的精简结果。2. 根据权利要求1所述的海量点云的Out-of-Core快速均勾精简方法，其特征在于步 骤（1)将CR树动态空间索引与数据库SQLite相结合为海量点云构建主存-辅存分级存 储机制，具体步骤为：（1)初始化：i ^ Hf ^ 30,新建CR树的根结点C ; (2)构建用 于存储叶结点子结点数据的点链表1i ;(3)读取点云文件中第i行点数据&，若心为空， 则跳转至（16) ;(4)将点数据.插入Pz ;(5)根据/;.利用CR树动态空间索引的选择子树 算法获取叶结点^ (6)若数据库SQLite中对应叶结点/柏数据表0存在，则利用数据库 SQLite的读取语句将坏余表头数据外的其他数据拷贝到Ji中，Fe Pi，调整结点尺利用 数据库SQLite的删除语句将你人数据库SQLite中删除；（7)若巧中元素的总数& < ，则构建数据表Λ将结点/? ii中的数据存储到々中，其中表头为/； 中的数据在 后，清空主存储器中的点链表，并跳转至（15) ; (8)将_的子结点转化为点集β利用 k均值聚类算法对点集0?行聚类，将点集必>为A个子集；(9)利用结点/=中的 子结点与点集P的双射关系，将结点/柏子结点分裂为k个新的结点{巧 ;...:6丨；（1〇)若 /?叶结点，./^1，否则，跳转至（14) ; (11)利用数据库SQLite新建数据表语句构建新的 数据表巧，并利用数据库SQLite插入语句将5及其包含的点数据存储到A中，其中表头为 其它为6包含的点数据，- + 重复（11)，直至_/ = ?!结束；（13)清空主存 储器中的点链表巧；（14)获取结点/柏父结点Fi3H 将k个新的结点 逐个插入到_，若/^的子结点总数《>Μ，返回⑶；（15) f ^ Kl，返回（3) ; (16) 海量点云主存-辅存分级存储机制构建完成。3. 根据权利要求2所述的海量点云的Out-of-Core快速均勾精简方法，其特征在于步 骤（8)子结点转化为点集的方法为：将上溢结点的子结点转化为子结点包围盒的中心点， 转化公式为式中邊迖)表示上溢结点/冲任一子结点/;的包围盒，C(.t)表示包围盒X的中心点。
【专利摘要】本发明提供一种海量点云的Out-of-Core快速均匀精简方法，属于产品逆向工程领域，其特征在于：改进CR树结点分裂算法；将上溢结点子结点集转化为子结点包围盒的中心点集；利用CR树与数据库SQLite构建海量点云的主存-辅存分级存储机制；运用海量点云的主存-辅存分级存储机制对海量散乱点云进行Out-of-Core管理；计算CR树目标结点层中每个结点所包含点集的均值点；将距离均值点最近的点作为该点集的精简结果；根据所选目标结点层的不同实现海量散乱点云不同程度的精简。本发明方法不仅能够快速实现超出主存容限的海量散乱点云的精简，且能够达到较好的精简效果。
【IPC分类】G06F17/30
【公开号】CN104881498
【申请号】CN201510341824
【发明人】孙殿柱, 聂乐魁, 李延瑞, 郭洪帅
【申请人】山东理工大学
【公开日】2015年9月2日
【申请日】2015年6月19日