二进制编码八叉树的海量点云邻域快速搜索算法

海量点云的邻域搜索是点云数据处理的关键技术,是对点云进行进一步处理的基础.针对海量点云数据邻域搜索效率较低的问题,提出了一种基于二进制编码八叉树的快速搜索算法.首先构建八叉树,利用一种二进制编码方式对八叉树的各个节点进行编码,即对空间3个维度分别进行编码;其次对邻域点进行查找过程,根据搜索半径直接确定需要搜索的高度;最后在确定的节点高度下,根据编码的特点直接计算所需要查询的邻域节点.实验结果表明,该算法准确性高、速度快,能够实现海量点云数据的快速邻域搜索.     

点云数据在深度学习中表示方法的研究

为了实现在深度学习中能够端到端表示点云模型,提出基于八叉树和K-D树（OctKD）的点云数据表示方法。该方法将无组织的点云转换为体素空间,在体素空间对三维模型进行八叉树剖分,改进了八叉树编码方式;构建节点间的邻接关系,在GPU端并行构建八叉树;为了克服八叉树编码检索效率低的问题,采用三维K-D树索引单个三维空间点。实验结果表明该方法能够真实反映模型本身的细节特征,提高了点云模型的构造时间和检索效率。这种新的数据结构实现将点云转换为卷积神经网络可以接收的数据形式。     

带洞点云多层同步表面重建方法

针对法向信息缺失和采样点缺失的带有洞的散乱点云数据,提出了一种高效高质量的多层同步表面重建方法.首先利用动态等高线检测出含有洞的八叉树节点,并且基于HPR（hidden point removal）映射计算出八叉树顶点的内外状态,建立带有顶点内外标识的空间有向状态八叉树,然后基于八叉树节点内法向测试方法保证基于k近邻表面重建过程中采样点的法向的正确性,且该空间有向状态八叉树可以支持不同层次的点云同步重建,在保证重建结果正确性的前提下,提高重建效率.     

基于八叉树模型的三维点云数据预处理研究

三维点云数据密度大,包含有大量的冗余数据,并不适合直接用于后续曲面重构。文中重点计论了基于八叉树模型的点云数据预处理的方法。实例表明,该方法对点云数据处理的灵活性和适应性都较好,能够满足曲线和曲面重构的要求。     

三维激光点云数据的可视化研究

大量的点云数据是通过三维激光扫描得到的,而点云数据的显示快慢受到了数据索引的直接影响,这是一个基础性问题。经过研究,八叉树与叶节点KD树相结合的混合空间索引结构以及LOD构建的层次细节模型是用来解决点云数据管理与可视化效率不高的问题的有效方法。在局部,通过在叶子节点中构建的KD树实现高效的查询和显示;在全局,为了实现快速检索与调度使用了八叉树模型。采用这种混合数据模型进行点云组织,建立空间索引,并对点云数据进行LOD构建,实现了点云数据的高效检索以及可视化。     

采用多尺度近邻体素特征的TLS林分点云分类

针对局部空间中林分点云多呈不规则分布的现状,提出了一种基于多尺度近邻体素特征的地面激光雷达林分点云分类方法。首先,通过特征选择获得六个特征,迭代使用四个尺度的八叉树分割点云,并在每个尺度下迭代遍历每个体素,搜索九个近邻体素计算点特征,实现四个尺度基于近邻体素重心的点特征估计;然后,使用LightGBM分类器完成训练,将该分类器模型应用于测试集实现林分点云分类;最后,通过分类准确率和计算特征用时作为评价指标对该方法实验结果进行评价。分析结果表明,该方法特征计算效率有较大幅度提升,可有效应用于人工林的点云分类任务。     

基于八叉树编码的点云数据精简方法

针对逆向工程中的点云数据预处理,分析了现有数据精简方法的不足,提出了基于八叉树编码的均匀精简方法。应用八叉树编码法划分点云邻域空间为多个指定边长的子立方体,保留每个子立方体中距中心点最近的点,实现从空间整体角度对点云的精简。对涡轮叶片测量数据进行了精简测试,证明了该算法的有效性和实用性。     

大规模点云内外存调度绘制技术

为实现大规模点云的快速绘制,提出以部分内存访问机制为基础、以节点点数上限为叶节点形成条件的平衡八叉树存储结构。设计点云内外存调度绘制流程,包括节点可见性判断、内外存数据调度和点云绘制等环节。为提高可见性判断的效率,在视点与节点距离、夹角约束条件的基础上给出节点可视半径约束。利用实测大规模点云数据进行实验,结果证明,该技术可以在有限的内存资源条件下,以较小的内存消耗实现上亿级规模点云从整体到局部的流畅绘制。     

基于OBB树的无网格几何数据处理

提出一种新的基于有向包围盒树(Oriented Boundmg Box,OBB树)的处理无网格几何数据方案.与最常用的八叉树比较,它具有三方面优点:首先,OBB树反映了统计意义上的几何模型空间分布,它不仅提供了辅助的层次结构,其本身还可以用于生成原始几何模型的形状逼近;其次,OBB树的节点数目和所需内存比八叉树少,且更贴近几何模型;其三,遍历OBB树的代价略高于八叉树,收敛速度却更快.针对点云模型,作者将OBB树结构应用于点云模型的自适应绘制.实验结果验证了OBB树的上述优点.     

基于八叉树空间分割的NURBS曲面重构方法

对三维模型和点云曲面重构方法进行深入研究,根据应用特点提出八叉树空间分割和N U RBS曲面重构方法。利用八叉树的快速收敛特性对三维实体的点云数据进行分割、精简,采用N U RBS方法对局部网格曲面进行重构;采用八叉树和四叉树相混合的数据结构,渐进地进行网格曲面的重构。存储结构采用扩展式八叉树结构,编码采用8进制前缀编码方法。利用O penG L设计一个实验模型系统验证了该算法的可行性和有效性。     

基于多重特征匹配的点云配准算法

针对最近点迭代（ICP）算法搜索匹配点对规则单一、准确度低的问题,提出一种基于多重特征匹配的点云配准算法。首先采用改进自适应八叉树算法分割点云,通过移动最小二乘法（MLS）对其叶节点进行局部拟合后,计算点的多重特征;然后提出了基于多重特征的点对相似度,选取满足相似度约束的点对作为匹配点对,进而求取旋转矩阵和平移矩阵实现点云配准。实验表明,该算法能在保持点云配准速度较高的基础上,有效提升配准的准确度,且准确度的提升幅度随着点集数量的增大呈升高趋势。     

基于光学图像的多粒度随动环境感知算法

针对快速三维建模中的室内外随动环境感知问题,提出一种基于光学图像的多粒度随动环境感知算法.该算法根据多种光学图像生成拟合真实三维环境的多粒度点云模型,然后通过概率八叉树压缩并统一表示已生成的多粒度三维模型.进而伴随相机轨迹每个时间节点,通过卡尔曼滤波动态融合多粒度点云模型的概率八叉树表示.最终生成唯一的时态融合概率八叉树三维模型,简称TFPOM,使TFPOM能够在较少的噪声影响下以任意粒度动态拟合真实环境.该算法配合剪枝和归并策略能够适应多粒度融合和多粒度表示的环境建模要求,有效压缩环境模型存储空间,实现鲁棒的随动环境感知,便于基于环境模型的视觉导航,增强现实等应用.实验结果表明,该算法能够在以可穿戴设备为代表的内含多种异构光学图像传感器,低计算效能的平台上实时得到充分拟合真实动态环境的多粒度TFPOM,基于该模型的视觉导航具有较小的轨迹误差.     

结合稀疏八叉树卷积神经网络的牙齿预备体颈缘线提取方法

针对传统手工提取牙齿预备体颈缘线需要交互标记特征点,操作复杂,效率低的问题,提出了一种基于稀疏八叉树的卷积神经网络自动提取牙齿预备体颈缘线的方法.首先利用稀疏八叉树的空间划分,牙齿预备体模型被预处理为带有标签信息的稀疏点云,构建牙齿预备体数据集;其次利用已训练的卷积神经网络模型将牙齿预备体点云分割为2部分;然后采用密集条件随机场优化分割点云的边界,再将边界点拟合及插值获取新的边界点集;最后连接边界点在预备体模型上对应的投影点形成牙齿预备体颈缘线.在牙齿预备体数据集上的实验结果表明,卷积神经网络模型的预测准确率达到97.23%,通过对该方法提取的预备体颈缘线与专业医生提取的颈缘线之间的曲线偏差进行对比分析,验证了该方法的有效性.     

面向体数据的虚拟八叉树模型研究

针对常规八叉树和线性八叉树的不足,提出了一种基于多级Z-Order曲线、无指针/无位置码的虚拟八叉树模型。在时间方面,由于采用了规则划分的节点数据块及其简单高效的索引结构,新模型具有很高的内存访问效率;在空间方面,由于节点中无指针和位置码信息,而且采用了新的基于规则节点块的合并和压缩原则,新模型具有很好的存储效率。测试结果表明,虚拟八叉树模型同时具有指针八叉树在时间效率、线性八叉树在空间效率两方面的优势,是一种高效的三维体数据组织模型,在体图形学相关的领域中具有重要的研究意义和应用价值。     

基于最近邻接点的涡点搜索算法

为了实现对优化迭代初始点(涡点)的预处理,保证从各个初始点迭代得到不同的局部最优点,进而通过对比研究获得全局最优点,提出了以基于Pan-距离的最近邻接点搜索为核心、涡点之间必有凸起为判断准则的涡点搜索算法.该算法以Pan-距离作为高维数据点之间的相似度描述参数.基于Pan-距离的高维空间邻接点搜索算法有效地降低了涡点搜索的计算负担.算例结果表明,在抽样点密度足够的情况下,该算法可实现高维空间涡点的快速有效搜索.     

基于八叉树及KD 树的混合型点云数据存储结构

通过对现有点云数据存储结构进行综合分析及比较,提出了一种基于八叉树及KD树的混合型点云数据存储结构模型,文中对该模型的基本原理、实现步骤及快速索引的建立等进行了全面的论述,最后以一组实测数据为例,比较了KD树、八叉树和本文提出的混合结构三种不同数据组织方式的检索效率,证明了所提出存储结构的有效性及实用性。     

局部表面拟合的点云模型法向估计及重定向算法

为了提高对点云模型处理的有效性,提出一种对点云模型的法向估计和重定向方法.首先利用基于局部平面拟合的主元分析方法得到初步法向估计;然后改进移动最小二乘曲面实现局部曲面拟合,进一步得到更加准确的法向,实现了点云模型的去噪光顺;最后通过增加切向约束规则来修正法向重定向中的法向传播方向.实验结果表明,对于具有复杂细节(如紧邻面、尖角形状等)的点云模型,该方法可以提高法向计算的准确度,并得到光顺的点云模型.在实际应用中,该方法可以很好地应用于点云模型的预处理,为后续的模型处理和分析提供良好的数据基础.     

基于八叉树空间分割的k近邻搜索算法

以三维扫描得到的散乱点云为基础,提出了一种基于空间八叉树的快速k近邻搜索算法,通过对点集建立包围盒,利用八叉树记录分割过程,从而使近邻点的搜索只局限于采样点所在的包围盒及其周围的包围盒,并通过剪枝策略使搜索范围进一步缩小。大量真实数据的实验结果表明：该算法可以很好地提高近邻点的搜索速度。     

基于保特征无参数投影的快速几何重建

为了使现有的无参数化投影算法拥有更好的保特征能力,提出一种保特征的基于无参数投影的点模型几何重建算法.首先,提出一个结合联合双边滤波器的局部优化投影算子,并利用点集的空间信息和几何特征信息,有效地保持了几何模型的特征;进一步,使用八叉树剖分技术对算法进行加速,为处理大规模点云提供了支撑;此外,还给出了自适应局部支撑的计算方法.实验结果表明,文中算法比无参数化投影算法保特征、速度快.     

基于八叉树邻域分析的光线跟踪加速算法

八叉树是加速光线跟踪常用的层次划分结构,为加快八叉树跟踪光线的过程,论文 研究了运用八叉树邻域分析提高光线与八叉树节点之间的碰撞检测速度的方法,提出了一种结构 简单、计算效率更高的八叉树节点的邻域分析算法。运用该算法可由现碰撞节点快速计算出下一 碰撞节点,避免了采用大量递归搜索计算,从而提高了图像的渲染速度。实验结果表明,使用论 文提出的邻域分析进行碰撞检测,效率比传统算法提高了3 倍以上,大大提高了光线跟踪的速度。