论文部分内容阅读
在计算机图形学、计算机视觉、图像处理和逆向工程学等研究领域中,三维重建技术一直是研究的重点内容。随着科学技术的不断发展,类似于德国Z+F三维激光扫描仪等三维激光扫描设备不断推陈出新,三维物体的几何信息得以通过扫描设备保存至存储设备中。同时,随着激光扫描设备精度的不断提高,扫描设备单次扫描所获得的点云模型的数据量成倍增长。随之而来会出现的问题是:密集的点云数据中必然存在大量的冗余数据,这些冗余数据极大地增加了点云数据的存储开销和计算开销,而且影响到了曲面拟合和模型生成等重要后续工作的效率。还要考虑到不同精度的点云建模需要不同精度的原始点云数据,因此,在重建模型可以保留原始三维物体的形状基础上,对点云数据的精简工作成为必然。点云数据的精简是眼下三维建模研究中的热门内容,它可以为后续工作提供便利,提高三维重建的效率。本文关于点云精简的主要研究内容大致分为点云数据曲率的计算、点云数据聚类方法和点云数据的精简算法设计三个主要方面:首先,在点云数据曲率的计算过程中,由于原始的K-Dimensional树(K-D树)近邻查找方法耗费时间长,每一次的查找回溯算法较复杂,本文运用一种改进的K-D树方法来构建点云数据之间的拓扑关系,依此快速寻找出待测点的k个近邻点,并根据这k个数据点和待测点,使用最小二乘法求得局部曲面的参数方程,从而计算点云数据的曲率,实验证明,改进的K-D树方法可以快速寻找出k近邻并计算出待测数据点的曲率值。其次,经典的K-Means聚类算法在对点云数据进行分类的过程中,初始聚类中心和聚类数目的选择,会对聚类结果造成影响。针对此问题,本文在聚类之前首先对原始点云数据建立K-D树,根据K-D树子树两侧数据分布比较均匀的特点,取K-D树中节点数最接近用户指定k值的那一层节点为聚类中心,依此来确定聚类数目和聚类中心。实验表明该方法不仅可以解决聚类中心的选取工作,而且在运行时间方面较经典的K-Means聚类算法拥有更快的收敛速度。点云数据的精简是本文的主要研究内容,本文结合聚类精简法与曲率精简法的优点,首先运用改进的K-Means聚类算法对点云数据进行聚类划分,然后利用K-D树依次计算点云数据的曲率值,通过曲率信息熵识别强特征点并予以保留,各个聚类内部根据最大曲率差区分特征区域与非特征区域,在曲面变化复杂的特征区域中,根据最大、最小曲率点将聚类重新划分为两个不同聚类,重复进行最大曲率差判断,直到满足条件为止;非特征区域保留聚类中心数据点。实验证明,这种混合精简方法能很好的保留点云原始数据的细节特征,并且在非特征区域无大片空洞出现。