（信号与信息处理专业论文）三维点云数据的预处理研究.pdf

西北工业大学硕士论文:三维点云数据的预处理研究 三维点云数据的预处理研究 权毓舒 何明一 教授 信号与信息处理 摘 要 近年来，三维扫描技术取得了巨大的发展，并且被广泛的应用到c a d / c a m, 逆向工程、国防、文物保护等领域。三维信息获取技术的发展，促进了对于三维 扫描获取的点云数据处理的研究。本课题来自国家8 6 3 高技术项目: “ 近景目 标三 维测量技术”中的有关内容。 本文重点研究点云数据编码压缩方法和邻域搜索算法。( 1 ) 、根据点云数据的 特点，建立八叉树模型，对原始数据进行坐标变换，映射到正整数空间，在此基 础上计算数据的m o rt o n 码。 对m o rt o n码排序、求差，统计码长， 提出了 一种改 进m o rt o n 码的方法。该方法提高了mo rt o n 编码的连续性，降低了八叉树的深度， 减少了 数据存储量。 并可应用三维行程编码等方法进一步压缩优化后的mo rt o n 码。 试验结果证明了算法的有效性。( 2 ) 、 把应用在四叉树模型的编码邻域算法推广到 空间的八又树模型，并与栅格邻域搜索算法做定性比较。此外，还简单介绍了 d e l a u n a y 三角划分方法及其优化准则， h o p p e 的三角网格重构算法。 关 键词:点云、线性八又树、 m o rt o n 码、d e l a u n a y 三角划分、 二角网格重构 西北工业大学硕士论文: 三维点云数据的预处理研究 t h r e e d i me n s i o n a l p o i n t c l o u d p r o c e s s i n g r e s e a r c h au t h o r : s u p e r v i s o r : s u b j e c t : q u a n y u s h u p r o f . h e mi n g y i s i g n a l a n d i n f o r m a t i o n p r o c e s s i n g ab s t r a c t w it h t h e d e v e l o p m e n t o f 3 - d s c a n n i n g t e c h n i q u e s , h o w t o p r o c e s s t h e t h r e e d i m e n s i o n a l p o i n t c l o u d b e c o m e s o n e o f t h e k e y r e s e a r c h f i e ld s . t h i s r e s e a r c h t h e s i s i s f r o m t h e p ro j e c t o f h i - t e c h r e s e a r c h a n d d e v e l o p m e n t p r o g r a m o f c h i n a ( 8 6 3 ) : c lo s e o b j e c t 3 d m e a s u r i n g t e c h n i q u e i n t h i s p a p e r , t h e a u t h o r a i m s a t t h e p r o c e s s i n g o f s p a t ia l s c a tt e r e d p o i n t c lo u d . i t i n c l u d e s s e v e r a l p a rt s : d a t a c o m p r e s s i o n , d a t a s m o o t h i n g , n e i g h b o r f i n d i n g , t r i a n g u l a t i o n and t r i an g le m e s h r e c o n s t r u c t i o n . t h e p a p e r p a y s e m p h a s i s o n d a t a c o m p r e s s i o n m e t h o d o f p o i n t c l o u d . b y a n a l y z i n g t h e f e a t h e r o f t h e p o i n t c l o u d , a n o c t r e e m o d e l i s e s t a b l i s h e d . a n i m p r o v e d e n c o d i n g a l g o r i t h m o f l i n e a r o c t r e e i s p r e s e n t e d . t h i s m e t h o d i n c r e a s e s t h e c o n t i n u i t y o f t h e m o rt o n c o d e , d e c r e a s e s t h e d e p t h o f t h e o c t r e e , and i m p r o v e s d a t a c o m p r e s s i o n r a t i o . t h e t e s t s a r e m a d e t o c o n f i r m t h e v a l i d i t y o f t h e m e t h o d . f u rt h e r m o r e , t w o n e a r e s t n e i g h b o r f i n d i n g a l g o r i t h m s a r e i n t r o d u c e d a n d c o m p a r e d i n c h a p t e r 3 . t r i ang u l a t i o n and t r i ang l e m e s h r e c o n s t r u c t i o n o n t h e s c a tt e r e d p o i n t a r e i n t r o d u c e d i n n e x t p a rt o f t h e p a p e r . d e l a u n a y t r i a n g u l a t i o n a n d , f i v e o p t i m i z e d p r i n c i p l e a n d h o p p e s t r i a n g l e m e s h r e c o n s t r u c t i o n a l g o r i t h m a r e p r e s e n t e d . k e y w o r d s : p o i n t c l o u d ; l i n e a r o c t r e e ; m o rt o n c o d e ; d e l a u n a y t r i ang u l a t i o n ; t r i a n g l e m e s h r e c o n s t r u c t i o n 1 1 西北工业大学硕士论文:三维点云数据的预处理研究 第一章绪论 1 . 1课题研究的背景和意义 本课题来自国家8 6 3 高技术项目: “ 近景目 标三维测量技术” 。 科学计算可视 化 ( v i s u a l i z a t i o n i n s c i e n t i f i c c o m p u t i n g ) 是发达国 家2 0 世纪8 0 年 代 后期 提出并发展起来的一个新的研究领域。科学计算可视化指的是运用计算机图形学 和图像处理技术，将科学计算过程中及计算结果的数据转换为图形及图像在屏幕 上显示出来并进行交互处理的理论、方法和技术，帮助人们洞察数据所蕴含的关 系和规律。借助于交互式的图形、图像系统，人们就能便捷地获得关于数据的直 观、形象深刻和全面的理解。事实上，随着技术的发展，科学计算可视化的含义 已经大大扩展。它不仅包括科学计算数据的可视化，而且包括工程计算数据的可 视化，如有限元分析结果等。也包括测量数据的可视化，如用于医疗领域的计算 机断层扫描 ( c t )数据及核磁共振 ( m r i )数据的可视化，就是最为活跃的研究领 域之一。 可视化的研究涉及到许多不同的领域，如计算机图形学、图像处理、计算机 视觉、信息处理，计算机辅助设计及交互技术等、自 从 1 9 8 7 年，它作为一门科学 确立以来，已经得到了长足的发展，并己经广泛地应用于计算机流体力学、有限 元分析、医学图像处理、数学、物理、地学、气象预报、生命科学等等。 三维空间数据场的可视化是科学计算可视化技术的核心。三维空间数据可视 化的对象既包括计算机的科学计算结果，也包括测量仪器的测量数据。由于三维 扫描仪器测量的数据是空间上物体的方位信息，通常是离散的，因此在论文工作 中可视化的对象一般指的是空间上离散的三维数据。 现代信息技术的发展和应用领域的扩展，使三维信息获取与处理技术应运而 生。工业、国防、医学、影视、广告、军事等各个行业对它的需求日益迫切。三 维信息获取与处理技术是2 0 世纪中期发展的一门新兴的综合性科学技术， 它集合 了电子、机械、光学、计算机及信息科学等多学科的最新成就，是高技术领域的 重要组成部分。三维信息数字化是将真实世界的 立体信息转换为计算机可直接处 理的 数字 信号， 通过 对这些三维数字信号的 预处 理 ( 如 合并、 注册、 去噪、 简化 等 ) 和处理 ( 如曲 面重 建、 分析和识别等) 恢复 物体的 数字 模型。 最近， 随 着计算 机技 术、 数字图像设备、机电光一体化技术、激光及其它光源技术的发展，三维信息获取 设备得到长足的 进步。三维信息获取设备总的发展趋势是，速度从慢到快， 精度 从低到高，从接触测量到非接触测量，从获取小场景到获取大场景。人们可以快 西北工业大学硕士论文:三维点云数据的预处理研究 第一章绪论 1 . 1课题研究的背景和意义 本课题来自国家8 6 3 高技术项目: “ 近景目 标三维测量技术” 。 科学计算可视 化 ( v i s u a l i z a t i o n i n s c i e n t i f i c c o m p u t i n g ) 是发达国 家2 0 世纪8 0 年 代 后期 提出并发展起来的一个新的研究领域。科学计算可视化指的是运用计算机图形学 和图像处理技术，将科学计算过程中及计算结果的数据转换为图形及图像在屏幕 上显示出来并进行交互处理的理论、方法和技术，帮助人们洞察数据所蕴含的关 系和规律。借助于交互式的图形、图像系统，人们就能便捷地获得关于数据的直 观、形象深刻和全面的理解。事实上，随着技术的发展，科学计算可视化的含义 已经大大扩展。它不仅包括科学计算数据的可视化，而且包括工程计算数据的可 视化，如有限元分析结果等。也包括测量数据的可视化，如用于医疗领域的计算 机断层扫描 ( c t )数据及核磁共振 ( m r i )数据的可视化，就是最为活跃的研究领 域之一。 可视化的研究涉及到许多不同的领域，如计算机图形学、图像处理、计算机 视觉、信息处理，计算机辅助设计及交互技术等、自 从 1 9 8 7 年，它作为一门科学 确立以来，已经得到了长足的发展，并己经广泛地应用于计算机流体力学、有限 元分析、医学图像处理、数学、物理、地学、气象预报、生命科学等等。 三维空间数据场的可视化是科学计算可视化技术的核心。三维空间数据可视 化的对象既包括计算机的科学计算结果，也包括测量仪器的测量数据。由于三维 扫描仪器测量的数据是空间上物体的方位信息，通常是离散的，因此在论文工作 中可视化的对象一般指的是空间上离散的三维数据。 现代信息技术的发展和应用领域的扩展，使三维信息获取与处理技术应运而 生。工业、国防、医学、影视、广告、军事等各个行业对它的需求日益迫切。三 维信息获取与处理技术是2 0 世纪中期发展的一门新兴的综合性科学技术， 它集合 了电子、机械、光学、计算机及信息科学等多学科的最新成就，是高技术领域的 重要组成部分。三维信息数字化是将真实世界的 立体信息转换为计算机可直接处 理的 数字 信号， 通过 对这些三维数字信号的 预处 理 ( 如 合并、 注册、 去噪、 简化 等 ) 和处理 ( 如曲 面重 建、 分析和识别等) 恢复 物体的 数字 模型。 最近， 随 着计算 机技 术、 数字图像设备、机电光一体化技术、激光及其它光源技术的发展，三维信息获取 设备得到长足的 进步。三维信息获取设备总的发展趋势是，速度从慢到快， 精度 从低到高，从接触测量到非接触测量，从获取小场景到获取大场景。人们可以快 西北工业大学硕士论文:三维点云数据的预处理研究 速、高精度、方便地对大物体、宽场景进行数字化，产生庞大的三维数据，如何 处理及利用好如此庞大的三维数据，是全世界计算机图形学、信号与信息等学科 所面临的共同问题。 1 . 2三维扫描技术的主要应用领域 1 . 2 . 1 逆向工程 三维扫描技术最广泛的应用在逆向工程中。逆向工程是数字化与快速响应制 造大趋势下的一项重要技术， 是c a d领域中一个相对独立的范畴。传统的产品制 造是先有图纸再有产品，而逆向工程是基于测量数据的产品造型技术，以特定的 方式完成一个实物的三维数字模型， 进而利用 c a d系统完成产品的制造。可以缩 短产品的开发周期，满足新产品的快速响应、个性化、小批量或单件定制的市场 需求。三维扫描识别系统不仅要获得物体的基本数据，而且要对数据进行必要的 处理，建立可以理解、分析、计算、编辑、修改的三维数字化模型。 逆向工程主要包括如下四个过程:三维数据获取;数据预处理;曲面重建及 创建c a d模型。目 前，在逆向工程的研究和应用领域有很大的进展，但也存在不 少问题，其中数据的获取与快速成型技术的发展已趋成熟，而通过测量数据构建 实物数字模型技术相对滞后，严重影响逆向工程的实用化程度。逆向工程的最终 目 标是按照产品的测量数据自 动重建出与现有c a d / c a m系统完全兼容的三维模 型。要实现这一目 标还有很长的路要走，特别是针对大规模 “ 点云数据”的建模， 远没有达到可以直接在c a d系统中应用的程度。 这也是本文对三维散乱数据进行 处理的目的。 1 . 2 . 2文物保护和数字博物馆 对于文物，三维激光扫描仪能以不损伤物体的手段，获得文物的外形尺寸和 表面色彩、纹理，得到文物的三维彩色拷贝。所记录的信息完整全面，而不是像 照片那样仅仅是几个侧面的图像，且这些信息便于长期保存、复制、再现、传输、 查阅和交流，使研究者能够在不直接接触文物的情况下，甚至千里之外，对其进 行直观的研究，这些都是传统的照相等手段所无法比 拟的。有了这些信息，也给 文物复制带来很大的便利。目 前，法国已将这一技术用于文物工作，美国斯坦福 大学利用三维扫描技术实施二 数字化米开朗基罗” 项目 ， 计划将文艺复兴时期的这位 意大利著名雕塑家的作品数字化。欧洲的四家公司、 三所大学、两座博物馆联合 实 施a r c h a t o u r 项目 ， 其主要目 标是以 三维数字技术改 进考古、 旅游领域中的多媒 体系统。英国自 然历史博物馆利用三维扫描仪对文物进行扫描，将其立体色彩数 字模型送到虚拟现实系统中，建立了虚拟博物馆，令参观者犹如进入了远古时代。 国内外都很重视文物的数字化保护，也称之为文物的第二次保护。 西北工业大学硕士论文:三维点云数据的预处理研究 速、高精度、方便地对大物体、宽场景进行数字化，产生庞大的三维数据，如何 处理及利用好如此庞大的三维数据，是全世界计算机图形学、信号与信息等学科 所面临的共同问题。 1 . 2三维扫描技术的主要应用领域 1 . 2 . 1 逆向工程 三维扫描技术最广泛的应用在逆向工程中。逆向工程是数字化与快速响应制 造大趋势下的一项重要技术， 是c a d领域中一个相对独立的范畴。传统的产品制 造是先有图纸再有产品，而逆向工程是基于测量数据的产品造型技术，以特定的 方式完成一个实物的三维数字模型， 进而利用 c a d系统完成产品的制造。可以缩 短产品的开发周期，满足新产品的快速响应、个性化、小批量或单件定制的市场 需求。三维扫描识别系统不仅要获得物体的基本数据，而且要对数据进行必要的 处理，建立可以理解、分析、计算、编辑、修改的三维数字化模型。 逆向工程主要包括如下四个过程:三维数据获取;数据预处理;曲面重建及 创建c a d模型。目 前，在逆向工程的研究和应用领域有很大的进展，但也存在不 少问题，其中数据的获取与快速成型技术的发展已趋成熟，而通过测量数据构建 实物数字模型技术相对滞后，严重影响逆向工程的实用化程度。逆向工程的最终 目 标是按照产品的测量数据自 动重建出与现有c a d / c a m系统完全兼容的三维模 型。要实现这一目 标还有很长的路要走，特别是针对大规模 “ 点云数据”的建模， 远没有达到可以直接在c a d系统中应用的程度。 这也是本文对三维散乱数据进行 处理的目的。 1 . 2 . 2文物保护和数字博物馆 对于文物，三维激光扫描仪能以不损伤物体的手段，获得文物的外形尺寸和 表面色彩、纹理，得到文物的三维彩色拷贝。所记录的信息完整全面，而不是像 照片那样仅仅是几个侧面的图像，且这些信息便于长期保存、复制、再现、传输、 查阅和交流，使研究者能够在不直接接触文物的情况下，甚至千里之外，对其进 行直观的研究，这些都是传统的照相等手段所无法比 拟的。有了这些信息，也给 文物复制带来很大的便利。目 前，法国已将这一技术用于文物工作，美国斯坦福 大学利用三维扫描技术实施二 数字化米开朗基罗” 项目 ， 计划将文艺复兴时期的这位 意大利著名雕塑家的作品数字化。欧洲的四家公司、 三所大学、两座博物馆联合 实 施a r c h a t o u r 项目 ， 其主要目 标是以 三维数字技术改 进考古、 旅游领域中的多媒 体系统。英国自 然历史博物馆利用三维扫描仪对文物进行扫描，将其立体色彩数 字模型送到虚拟现实系统中，建立了虚拟博物馆，令参观者犹如进入了远古时代。 国内外都很重视文物的数字化保护，也称之为文物的第二次保护。 西北工业大学硕士论文:三维点云数据的预处理研究 本课题也是结合陕西的文物进行扫描试验，对兵马俑文物模型进行扫描并完 成数据的处理和三角网格重构。 1 .2 .3其它研究领域 三维扫描技术能够测得物体表面点的三维空间坐标，从这个意义上说，它实 质上是一种立体测量技术。与传统的测量技术相比，它能够实现无接触测量，还 能够完成不规则曲面、柔性物体的扫描，而且扫描精度高、速度快、还原性好， 所有这些特性使得三维扫描技术被广泛的应用到各个领域。图形图像及计算机视 觉技术结合及其应用，使得三维立体信息获取技术，在工业、影视娱乐业、国防、 医学、文物保护、个性化的服装定制、建筑设计等方面获得应用，也有着广阔的 前景。 1 . 3三维信息采集技术 三维扫描是一种信息获取方式，是一种立体测量技术。如何能够快速、准确 地侧量出物体表面点的三维空间坐标是实现三维扫描技术的关键。经过近 2 0 年的 探索和研究，现在有多种方法能够实现三维扫描。根据不同的应用场合和被测对 象，以及对测量精度、速度、范围和成本的不同要求，可以采用不同的方法和装 置。 图1 - 1三维信息获取方法分类图 高效率、高精度地采集物体三维坐标的数据是逆向工程中的第一个环节，是 数据处理、模型重建的基础。随着科学技术的不断发展，三维信息获取技术也随 着新的测量原理、新的材料，新的技术的不断引入而获得长足发展，特别是光学 技术用于三维数字化使得测量精度、速度及范围有了很大的提高;数字显示技术 西北工业大学硕士论文:三维点云数据的预处理研究 本课题也是结合陕西的文物进行扫描试验，对兵马俑文物模型进行扫描并完 成数据的处理和三角网格重构。 1 .2 .3其它研究领域 三维扫描技术能够测得物体表面点的三维空间坐标，从这个意义上说，它实 质上是一种立体测量技术。与传统的测量技术相比，它能够实现无接触测量，还 能够完成不规则曲面、柔性物体的扫描，而且扫描精度高、速度快、还原性好， 所有这些特性使得三维扫描技术被广泛的应用到各个领域。图形图像及计算机视 觉技术结合及其应用，使得三维立体信息获取技术，在工业、影视娱乐业、国防、 医学、文物保护、个性化的服装定制、建筑设计等方面获得应用，也有着广阔的 前景。 1 . 3三维信息采集技术 三维扫描是一种信息获取方式，是一种立体测量技术。如何能够快速、准确 地侧量出物体表面点的三维空间坐标是实现三维扫描技术的关键。经过近 2 0 年的 探索和研究，现在有多种方法能够实现三维扫描。根据不同的应用场合和被测对 象，以及对测量精度、速度、范围和成本的不同要求，可以采用不同的方法和装 置。 图1 - 1三维信息获取方法分类图 高效率、高精度地采集物体三维坐标的数据是逆向工程中的第一个环节，是 数据处理、模型重建的基础。随着科学技术的不断发展，三维信息获取技术也随 着新的测量原理、新的材料，新的技术的不断引入而获得长足发展，特别是光学 技术用于三维数字化使得测量精度、速度及范围有了很大的提高;数字显示技术 西北工业大学硕士论文:三维点云数据的预处理研究 在测量上得到了充分的应用，提高了读数精度和可靠性。目 前，主要的三维信息 采集方法分类如图1 - 1 所示。 1 . 4三维点云数据的预处理技术 三维视觉研究的主要目的是获取物体的三维信息、提取三维物体的几何特征， 建立物体的空间模型，并为视觉系统的高层任务提供所需要的表达和描述。由于 三维数据本身保护理景物的三维几何信息，因此三维图像处理在内容上有所侧重， 在方法上有自己的特点， 三维视觉研究的主要内容包括三维物体表面数据的获取、 平滑、压缩，表面重构与描述，三维目 标识别和加工等。 其中，数据获取主要完成景物及目标的三维信息获取;预处理主要包括三维 物体的表面几何数据去噪、平滑、压缩以及分割等在数据点上的操作处理、描述 则把经底层处理后的数据点特征转变为对景物的表达和描述，三维重建则是用体 模型或者面模型来近似表达用空间三维坐标所表示的三维物休。 消除测量点集中的噪声数据是坐标测量中的难点问题。由于被测物体表面的 反射特性、测距系统中的机械振动、以及量化误差等因素的影响，不可避免地使 测得三维物体的表面数据中包含有系统测量噪声、量化误差以及几何失真，而这 些噪声或误差对后续的特征提取处理影响很大，甚至会导致错误的结果。 所以 在 底层处理中首先要对获得的三维物体表面数据进行预处理。 目前，随着三维扫描仪、逆向工程的广泛应用，对三维散乱数据的处理主要 集中在数据三角化和曲面重构这两个方面，而对于三维点云数据的预处理技术， 相对研究较少，目前国外的研究主要放在噪声点的处理上。本文重点研究三维点 云数据的编码压缩与邻域搜索。 1 . 5本文的主要研究内容 本文主要研究三维点云数据的处理技术。点云数据指的是在三维空间中，无 规则的、随机分布的数据。相关处理主要包括点云数据的特点、用八叉树模型来 描述点云、点云数据的压缩、测量数据平滑、邻域搜索、三角划分、三角网格重 构等方面内容。 本论文将以 me n s i 仪扫描得到的实验数据或互联网上的样本为原始数据，在 此基础上进行数据的处理。针对原始数据和经过去噪、平滑后的数据进行分析和 比较. 通过专用的软件来观察数据处理前后的不同效果，把处理后的数据用于三 角网格重构，以 便可以进一步看到数据预处理对三维重构所起到的积极的意义。 在对数据处理时，应用多个数据源，既有面部细节丰富的兵马俑扫描数据， 也有几何结构简单的机械零件模型。 西北工业大学硕士论文:三维点云数据的预处理研究 在测量上得到了充分的应用，提高了读数精度和可靠性。目 前，主要的三维信息 采集方法分类如图1 - 1 所示。 1 . 4三维点云数据的预处理技术 三维视觉研究的主要目的是获取物体的三维信息、提取三维物体的几何特征， 建立物体的空间模型，并为视觉系统的高层任务提供所需要的表达和描述。由于 三维数据本身保护理景物的三维几何信息，因此三维图像处理在内容上有所侧重， 在方法上有自己的特点， 三维视觉研究的主要内容包括三维物体表面数据的获取、 平滑、压缩，表面重构与描述，三维目 标识别和加工等。 其中，数据获取主要完成景物及目标的三维信息获取;预处理主要包括三维 物体的表面几何数据去噪、平滑、压缩以及分割等在数据点上的操作处理、描述 则把经底层处理后的数据点特征转变为对景物的表达和描述，三维重建则是用体 模型或者面模型来近似表达用空间三维坐标所表示的三维物休。 消除测量点集中的噪声数据是坐标测量中的难点问题。由于被测物体表面的 反射特性、测距系统中的机械振动、以及量化误差等因素的影响，不可避免地使 测得三维物体的表面数据中包含有系统测量噪声、量化误差以及几何失真，而这 些噪声或误差对后续的特征提取处理影响很大，甚至会导致错误的结果。 所以 在 底层处理中首先要对获得的三维物体表面数据进行预处理。 目前，随着三维扫描仪、逆向工程的广泛应用，对三维散乱数据的处理主要 集中在数据三角化和曲面重构这两个方面，而对于三维点云数据的预处理技术， 相对研究较少，目前国外的研究主要放在噪声点的处理上。本文重点研究三维点 云数据的编码压缩与邻域搜索。 1 . 5本文的主要研究内容 本文主要研究三维点云数据的处理技术。点云数据指的是在三维空间中，无 规则的、随机分布的数据。相关处理主要包括点云数据的特点、用八叉树模型来 描述点云、点云数据的压缩、测量数据平滑、邻域搜索、三角划分、三角网格重 构等方面内容。 本论文将以 me n s i 仪扫描得到的实验数据或互联网上的样本为原始数据，在 此基础上进行数据的处理。针对原始数据和经过去噪、平滑后的数据进行分析和 比较. 通过专用的软件来观察数据处理前后的不同效果，把处理后的数据用于三 角网格重构，以 便可以进一步看到数据预处理对三维重构所起到的积极的意义。 在对数据处理时，应用多个数据源，既有面部细节丰富的兵马俑扫描数据， 也有几何结构简单的机械零件模型。 西北工业大学硕士论文:三维点云数据的预处理研究 在测量上得到了充分的应用，提高了读数精度和可靠性。目 前，主要的三维信息 采集方法分类如图1 - 1 所示。 1 . 4三维点云数据的预处理技术 三维视觉研究的主要目的是获取物体的三维信息、提取三维物体的几何特征， 建立物体的空间模型，并为视觉系统的高层任务提供所需要的表达和描述。由于 三维数据本身保护理景物的三维几何信息，因此三维图像处理在内容上有所侧重， 在方法上有自己的特点， 三维视觉研究的主要内容包括三维物体表面数据的获取、 平滑、压缩，表面重构与描述，三维目 标识别和加工等。 其中，数据获取主要完成景物及目标的三维信息获取;预处理主要包括三维 物体的表面几何数据去噪、平滑、压缩以及分割等在数据点上的操作处理、描述 则把经底层处理后的数据点特征转变为对景物的表达和描述，三维重建则是用体 模型或者面模型来近似表达用空间三维坐标所表示的三维物休。 消除测量点集中的噪声数据是坐标测量中的难点问题。由于被测物体表面的 反射特性、测距系统中的机械振动、以及量化误差等因素的影响，不可避免地使 测得三维物体的表面数据中包含有系统测量噪声、量化误差以及几何失真，而这 些噪声或误差对后续的特征提取处理影响很大，甚至会导致错误的结果。 所以 在 底层处理中首先要对获得的三维物体表面数据进行预处理。 目前，随着三维扫描仪、逆向工程的广泛应用，对三维散乱数据的处理主要 集中在数据三角化和曲面重构这两个方面，而对于三维点云数据的预处理技术， 相对研究较少，目前国外的研究主要放在噪声点的处理上。本文重点研究三维点 云数据的编码压缩与邻域搜索。 1 . 5本文的主要研究内容 本文主要研究三维点云数据的处理技术。点云数据指的是在三维空间中，无 规则的、随机分布的数据。相关处理主要包括点云数据的特点、用八叉树模型来 描述点云、点云数据的压缩、测量数据平滑、邻域搜索、三角划分、三角网格重 构等方面内容。 本论文将以 me n s i 仪扫描得到的实验数据或互联网上的样本为原始数据，在 此基础上进行数据的处理。针对原始数据和经过去噪、平滑后的数据进行分析和 比较. 通过专用的软件来观察数据处理前后的不同效果，把处理后的数据用于三 角网格重构，以 便可以进一步看到数据预处理对三维重构所起到的积极的意义。 在对数据处理时，应用多个数据源，既有面部细节丰富的兵马俑扫描数据， 也有几何结构简单的机械零件模型。 西北工业大学硕士论文:三维点云数据的预处理研究 论文将就具体三维点云数据模型、邻域搜索、三角划分、三角网格重构几个 部分进行研究讨论。 西北工业大学硕士论文: 三维点云数据的预处理研究 第二章点云数据的编码压缩与数据平滑 本章主要研究反求工程中三维点云数据的编码压缩与数据平滑。主要包括点 云数据的特点、用八叉树模型来描述点云、点云数据的压缩、测量数据平滑等方 面内容。根据点云数据的特点，建立八又树模型来对其进行mo r to n 编码，并优化 m o r t o n 码，从工程应用角度出发提出了 对完全散乱的密集点云进行压缩的算法。 2 . 1 点云数据的三维模型 应用三维扫描技术获取的原始数据是一种点云数据。点云数据实际上就是密 集的散乱点数据，其特点是数据量大、数据点之间的距离较小。这种点云是一个 空间数据的集合，数据点之间是离散的、散乱分布的;同时，点云又是一个海量 数据的集合，通常具备上万个或者更多的数据点，存储量巨大。综合考虑点云的 这两方面特征，先使用一个三维空间数据模型来描述点云数据，并且基于这种模 型能够高效率的压缩数据的存储量。线性八叉树是常用的三维数据数模型，下文 将重点研究线性八叉树的编码压缩算法及其在三维点云数据中的应用。 2 . 1 . 1八叉树模型 八叉树结构是在 2 0世纪 7 0年代后期至 2 0世纪 8 0年代早期出现的。s a m e t 深刻地研究了 八叉树的结构特征。八叉树 ( o c t r e e )结构是由四叉树 ( q u a d r e e ) 结构推广到三维空间而形成的一种3 d栅格数据结构。其基本思想是将3 d空间区 域划分成三维栅格，每一个小正方体有一个或多个属性数据。八叉树的树形结构 在空间分解上具有很强的优势。八叉树模型将一个立方体大小的三维空间等分成 为八个卦限，每个卦限具有相同的时间和空间的复杂度，如果某个卦限内的物体 属性相同或可以视为相同时就不再细分，否则就将该卦限再细分为八个卦限。通 过循环递归的划分办法，使得每个体元都属于同一属性或者达到规定的限差 八 叉树的 分辨率) 为止。八叉树模型的详细介绍可以 参考文献【 3 , 4 , 5 . 在八叉树到树形结构中，每一个非叶节点都有八个子节点，即按照一分为八 的规则逐层划分。根节点表示整个目 标空间，对应于一个 2 n 边长的立方体 ( n为 八叉树的 层次 数) ， 任何其它节点对应于一个边长为2 的立方体。 非终节点的子节 点的 顺 序对应于父节点子节点的 几何顺序， 非终节点称为灰节点 ( g r e y ) 终节点 要么对应于含有最简单的目 标体，要么对应于预先规定的最小边长， 称为分辨率。 终节点又称为叶节点， 有两种类型， 一种是在目 标数据的内部， 称为实节点( b l a c k ) ; 一种是在目 标数据的外部，称为空节点 ( w h i t e ) . 线性八叉树模型是在普通八叉树模型基础上进一步压缩数据存储量，由于不 西北工业大学硕士论文: 三维点云数据的预处理研究 第二章点云数据的编码压缩与数据平滑 本章主要研究反求工程中三维点云数据的编码压缩与数据平滑。主要包括点 云数据的特点、用八叉树模型来描述点云、点云数据的压缩、测量数据平滑等方 面内容。根据点云数据的特点，建立八又树模型来对其进行mo r to n 编码，并优化 m o r t o n 码，从工程应用角度出发提出了 对完全散乱的密集点云进行压缩的算法。 2 . 1 点云数据的三维模型 应用三维扫描技术获取的原始数据是一种点云数据。点云数据实际上就是密 集的散乱点数据，其特点是数据量大、数据点之间的距离较小。这种点云是一个 空间数据的集合，数据点之间是离散的、散乱分布的;同时，点云又是一个海量 数据的集合，通常具备上万个或者更多的数据点，存储量巨大。综合考虑点云的 这两方面特征，先使用一个三维空间数据模型来描述点云数据，并且基于这种模 型能够高效率的压缩数据的存储量。线性八叉树是常用的三维数据数模型，下文 将重点研究线性八叉树的编码压缩算法及其在三维点云数据中的应用。 2 . 1 . 1八叉树模型 八叉树结构是在 2 0世纪 7 0年代后期至 2 0世纪 8 0年代早期出现的。s a m e t 深刻地研究了 八叉树的结构特征。八叉树 ( o c t r e e )结构是由四叉树 ( q u a d r e e ) 结构推广到三维空间而形成的一种3 d栅格数据结构。其基本思想是将3 d空间区 域划分成三维栅格，每一个小正方体有一个或多个属性数据。八叉树的树形结构 在空间分解上具有很强的优势。八叉树模型将一个立方体大小的三维空间等分成 为八个卦限，每个卦限具有相同的时间和空间的复杂度，如果某个卦限内的物体 属性相同或可以视为相同时就不再细分，否则就将该卦限再细分为八个卦限。通 过循环递归的划分办法，使得每个体元都属于同一属性或者达到规定的限差 八 叉树的 分辨率) 为止。八叉树模型的详细介绍可以 参考文献【 3 , 4 , 5 . 在八叉树到树形结构中，每一个非叶节点都有八个子节点，即按照一分为八 的规则逐层划分。根节点表示整个目 标空间，对应于一个 2 n 边长的立方体 ( n为 八叉树的 层次 数) ， 任何其它节点对应于一个边长为2 的立方体。 非终节点的子节 点的 顺 序对应于父节点子节点的 几何顺序， 非终节点称为灰节点 ( g r e y ) 终节点 要么对应于含有最简单的目 标体，要么对应于预先规定的最小边长， 称为分辨率。 终节点又称为叶节点， 有两种类型， 一种是在目 标数据的内部， 称为实节点( b l a c k ) ; 一种是在目 标数据的外部，称为空节点 ( w h i t e ) . 线性八叉树模型是在普通八叉树模型基础上进一步压缩数据存储量，由于不 西北工业大学硕士论文:三维点云数据的预处理研究 记录中间节点的编码及层次关系，大大节省了存储空间， 特别适合对海量数据的 建模和处理。线性八叉树编码只存储实的叶子节点，叶节点的编码称为地址码， ( r o o t ) ( 1 l e v e l ) 。添翩 常用的地址码是 mo rt o n码， mo rt o n码反映了八又树的层 次信息。 mo rt o n 码比常规八叉 树编码更有优势， 是一种高效 率的编码方式。 八叉树的原理与数据结 构中的二叉树、 四叉树基本相 同， 就像二叉树排序可以方便 的实现一维序列的查找、 四叉 树可以实现2 维平面上的对象 索引一样， 八叉树结构也可以 用作三维空间中数据的索引。 关于基于八叉树模型的三维 点云的邻域搜索算法， 将在第 三章中详细介绍。 ( 2 l e v e l s ) 图2 - 1八叉树模型 2 . 1 . 2 三维点云数据标准化处理 为了便于把三维点云数据按照线性八叉树的结构来划分和进行mo rt o n 编码， 需要先把点云数据作标准化处理。由于m o rt o n 编码的对象必须是正整数， 所以需 要将原始数据放大并平移映射到正整数空间。扫描得到的点云数据仅具有x ,y , : 三 个坐标值，所有的操作都是针对坐标值进行。在进行数据的标准化处理时，用 m y s q l数据库进行操作。 设原始数据集合是s ( z , y , z ) ，读入原始数据到数据库， 生成一个nx 3 的数据表，其中n表示点云数据的个数。 具体步骤如下: 把原始数据扩大1 0 0 整数倍， 其中m为原始数据的小数点后的最大有效位数。 这样操作既保留了原始数据的全部有效位数，又把数据不失真的转化成可以编码 的 整数。得到的数据集合为s ( x , y , z ) . 将步骤1 中的整数集s ( x , y , z ) 平移到正整数空间，目 的是避免对负数的 编码。 用数 据库遍历搜索出s ( x , y , z ) 中二 ， y , : 的 最大、 最小 值。 对所有数据进行平移 变换。 令 x 二 x 一 x.,.; y = y 一 y , z = z 一 z m in ，( 2 . 1 ) 西北工业大学硕士论文:三维点云数据的预处理研究 这样得到新的非负整数集合r i x . y , z 1 a 把世界坐标系 ( wc )映射到便于编码分析的观察参考坐标系 ( v r c ) 。令 a x=x m : 一 x , ay =孺: 一 r , o z =z 一 z m 。 ( 2 2) = m a x ) a x , d y , a z ) 1 = 1 o g , l , 。 = 川 ( 2 3) 这步相当于用边长为l ，空间2 x 2 x 2 大小的正立方体 ( 八叉树的根节点 围平移变换后的点云， 其中” 是空间分辨率的基值。设i 为最小空间分辨率， 树最大深度为 n 层。 )包 八叉 把集合r (x . y . z ， 中全部数据转换成二进制表示，记为b l n a r y r 1x , v , z ) 。 集合r x *, y , z ) 完全保留了原始数据的精度并具备几何不变性，是进制转换和 编码的基础。 下文的讨论也将围绕r i x , y , z i 或b in a r y r i x , y , z ， 展开。 2 . 1 . 3计算 mo r t o n 码 mo rt o n码 线性八叉树编码只存储实的叶子节点，叶节点的编码称为地址码，常用的地 址码是m o r t o n 码。所以一个m o r t o n码就蕴含了空间一个点的三维坐标信息。在 编码中， 结点采用与线性八又树相同到地址码， 即m o r t o r 码。 m o r t o n 码就是将三 维转换成一维表示， 从而实现数据压缩。 m o r t o n 码是现有使用最广泛到一种方法， 它比常规八叉树和基于八进制的线性八叉树更有优势。从存储到角度上，更节省 空间;生成编码也更加迅速。由于不需要记录中间结点，从而省去来大量到中间 结点指针到存储。而且m o r t o n 码以十进制为编码，更加符合人们三使用牙质。当 检查相邻栅格到属性以判断能否合并时，不需要排序，从而节省来排序时间。 2 . 编码原理 在数据预处理的基础上，原始的三维坐标转换成二进制数来表示，用按位交 错排列得方式即可得到二进制表示的m o rt o n 码。 x ; 表示坐标x的二进制的第i 位。 ( x ;= o或 1 ) 。x =x i x 2 . . . x a y =y , y 2 ， 二 y m , z = z 1 z 2 . . . z m e m为x . y . z中 最大值的二进制编码位数。 其余两个坐标在左边用零补位对齐。 注意: 要按照从z , 到y到 x的顺序来排列由x y z生成到 mo rt o n 码。得到是二进制的mo rt o n 码， 可以三位一合并成八进制( 可以和八叉树对应) ， 也可以直接转换成习惯的十进制。 m o rt o n 码反映了八叉树的层次信息。 西北工业大学硕士论文:三维点云数据的预处理研究 图2 - 2 从二进制的x y z坐标生成后mo rt o n 码示意图 3 .计算mo rt o n 码 在点云数据预处理的基础上， 可以 进行mo rt o n 编码。 文献【 8 1 中提供了三种计 算m o rt o n 码的方法， 其中的移位计算法和文献 1 中的比 特运算法本质上是一种方 法，都是利用二进制比特位的移位操作来求mo rt o n 码值的。具体实现可以用文献 1 中 提到的比 特运算法， 求得m o rt o n 码值， 结果见表2 - 1 。 这里简单说明m o rt o n 码就算方法。 设空 间b i n a r y r 3 ( x , y , z , 中 任 一 点长 ( x q , y q , z q ) ， 则v , 的n位二 进 制整数 形式 x q =x - i x - 2 . . . x ix o ， y q =yn一 l y n 一 2 “ y l y o ，2 ， =z . - i z - 2 . . . z 1 z 0 - ( 2 .4 ) 写 成2 的 幂指 数 多 项 式 可 得 : 凡 = 艺x ; 2 , 入y ;2 . 之 。 = 艺z .2 ( 2 . 5 ) 老i=o 空间任一点在线性八叉树中的mo rt o n 码就是从八叉树根节点到叶节点的路径 值。对于2 x 2 x 2 ” 的空间，从根节点到叶节点最大路径深度不超过n o 设 任 一 点 长 ( x q , y 9 , z 9 ) 的 路 径 为 弓 ， 则 有: 尺 二 ( p _ ,p _ 2 p , e (0 , 1, 2 ,3 , 4 , 5 , 6 ,7 点 气 ( x q , y q , z q ) 的 m o rt o n 编 码 为 m e 则m q = p _ , . 8 - + p - 2 . 8 - + + p o . 8 0 ( 八 进 制 ) 应 用 位 移 计 算 法，p , = z , - 2 2 + y , . 2 + x , . 2 - ， 其中0 p p 0 ) i n一1 ( 2 石) ( 2 刀) 为 求x i , y ; , z 位， 只需 在x q , y q , z 9 的 相应位置 进行逻辑乘， 具体实