作者：李晋江,董付国,等
出版社：电子工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
散乱数据点三维重构关键问题研究试读：
内 容 简 介
三维重构是指对获取的散乱数据建立其拓扑结构，在此基础上对其进行曲面插值和曲面拟合，最后得到真实物体在计算机内的表示。目前，三维数据获取的能力和精度都有了很大的提高，这为实现物体的三维重构提供了坚实的基础。三维重构是逆向工程、人机交互可视化等的关键技术，在制造业、虚拟现实、科学计算可视化、文物保护等领域有广泛的应用。本书对实现物体高精度三维重构中的数据获取与去噪、数据的配准对齐、孔洞修复及数据压缩、表面建模等关键问题进行了论述。本书适合从事三维重构、逆向工程等相关领域的科研人员阅读，也可作为高等学校相关专业研究生的教学用书。未经许可，不得以任何方式复制或抄袭本书之部分或全部内容。版权所有，侵权必究。图书在版编目（CIP）数据散乱数据点三维重构关键问题研究 /李晋江，董付国，安志勇编著.—北京：电子工业出版社，2011.9ISBN 978-7-121-14419-6Ⅰ. ①散… Ⅱ. ①李… ②董… ③安… Ⅲ. ①三维动画软件—研究 Ⅳ. ①TP391.41中国版本图书馆CIP数据核字（2011）第169254号责任编辑：张 剑（zhang@phei.com.cn）印 刷：装 订：出版发行：电子工业出版社北京市海淀区万寿路173信箱 邮编 100036开 本：720×1 000 1/16 印张：12.25 字数：188千字印 次：2011年9月第1次印刷定 价：58.00元凡所购买电子工业出版社图书有缺损问题，请向购买书店调换。若书店售缺，请与本社发行部联系，联系及邮购电话：（010）88254888。质量投诉请发邮件至zlts@phei.com.cn，盗版侵权举报请发邮件至dbqq@phei.com.cn。服务热线：（010）88258888。前 言
目前三维数据获取的能力和精度都有了很大的提高，这为实现物体的三维重构提供了坚实的基础。三维重构是指对获取的散乱数据建立其拓扑结构，在此基础上对其进行曲面插值和曲面拟合，最后得到真实物体在计算机内的表示。三维重构是逆向工程、人机交互可视化等的关键技术，在制造业、虚拟现实、科学计算可视化、文物保护等领域均有广泛的应用。在现实应用中，实现物体高精度的三维重构，需要进行数据获取与去噪、数据的配准对齐、孔洞修复及数据压缩、表面建模等关键处理，本书将对这些关键问题进行论述。本书共分7章：第一章为绪论，第二章介绍相关几何知识，第三章论述了点云数据光顺去噪问题，第四章讨论了点云数据的对齐配准，第五章对点云数据中的孔洞修复问题进行了阐述，第六章讨论了网格的简化与压缩，第七章讨论了点云数据曲面重建中的一些相关技术。本书由李晋江主持撰写，还有 6 位学者参加了写作和绘图整理工作。其中，董付国编写了本书的第二章；安志勇编写了本书的第三章；王金鹏编写了本书的第一章；李业伟编写了本书的第六章；王勇亮和李洪娟编写了本书的第七章；李晋江负责本书其余章节的编写，并对全书进行统稿。本书的研究工作得到了国家自然科学基金（60970105）、山东省自然科学基金（ZR2009GQ005 和 ZR2010FM044）、山东省优秀中青年科学家奖励基金（2008BS01026 和 BS2009DX038）和山东省教育厅科技计划（J08LJ06）的资助。范辉教授、原达教授和华臻教授自始至终热情关心和积极支持本书的创作，并提出许多宝贵意见，在此谨向他们致以深切的谢意。我个人深切地感谢我的父母、兄弟们，他们对我无私的关爱和鼓励为我在学业上的进步提供了可靠保证；感谢我的妻子和女儿，她们给了我极大的精神支持。由于写作时间和作者水平有限，书中难免存在缺点和错误，敬请批评、指正和帮助。李晋江2011年6月5日于烟台第一章绪 论
目前，三维空间测量技术得到了快速发展和广泛应用，三维数据获取的能力和精度都有了很大的提高，这为实现物体的三维重构提供了坚实的基础。三维重构是指对实际存在的物体，获取其在计算机内表示的技术，这种外形表示是对三维物体进行处理、操作和分析其性质的基础。三维重构是将现实中的三维物体或场景在计算机中进行重建，是CAD/CAM领域的一个研究热点，属于多个学科交叉的课题（涉及计算机图形学、图像处理、信息处理、计算机视觉、计算机辅助设计及交互技术等），在制造业、虚拟现实、3D 游戏、医学、文物保护、电影特技制作等领域有着广泛的应用。在许多领域的实际应用中，需要对现实物体提供高精度的三维重构，例如，在已有模型（汽车模具、飞机涡轮、压缩机叶片等）基础上，建立高精度的数字化模型及设计新的模型；对基于海量数据点生成的数字化模型用现有的三维CAD系统对其进行力学和工艺等分析；在数字博物馆中建立古物的精细逼真模型，使用户可在互联网上看到精美的古代艺术珍品，并通过缩放操作看到珍品的奇妙的艺术细节。1.1 三维数据点的获取
三维数据是使用各种三维数据采集仪采集得到的数据，它记录了有限体表面在离散点上的各种物理参量。它包括的最基本的信息是物体各离散点的三维坐标，也可以包括物体表面的颜色、透明度、纹理特征等。数据获取是指采用某种测量方法和设备测出实物各表面的若干组点的几何坐标，以获得实物的几何信息。快速、全面、完备地获取对象的表面信息，是数据获取所要实现的目标。逆向工程中的数据采集是指通过各种现代化的测量手段，对样件表面进行测量，将其表面实体信息转化成点坐标数据。因此，逆向工程中的数据采集又称为表面数字化。只有获得了样件的表面三维信息，才能实现复杂曲面的建模、评价、改进、制造。因而，高效、高精度地实现样件表面的数据采集，这是逆向工程的主要研究内容之一。数据可以通过多种方式进行获取或采集。同一对象，采用不同的采集方法，经过处理后往往会得出不同的结果，这一问题对于复杂的自由曲面尤其突出。根据采集过程是否破坏工件，采集过程分为非破坏性采集和破坏性采集。非破坏性采集根据测量设备与测件之间的作用方式可分为接触式采集和非接触式采集。1．接触式数据采集方法接触式数据采集方法通常是用机械探头直接接触物体表面，机械臂关节处的传感器确定相对坐标位置，通过探测头反馈回来的光电信号转换为数字面形信息，从而实现对物体面形的扫描和测量。常用的接触式测量工具有三坐标测量机、三坐标测量仪和接触式扫描仪等。根据测头的不同，接触式测量又可分为触发式和连续式，还有基于磁场、超声波的数据采集等。值得一提的是，目前接触式测头有新的发展，出现了软测头技术，而软测头又可分为开关发讯测头和扫描式测微测头。扫描式测头无论从精度还是速度上都优于发讯测头，使CMM技术提高到一个新水平。目前最先进的采用力—位移传感器的扫描测量头，该测头可以在物体表面滑动测量，其扫描速度最高可以达到8mm/min，精度可以达到 30µm。由于接触式扫描方法具有精度高、可靠性好等优点，目前仍有口腔CAD/CAM系统在使用这种扫描方式。1）触发式数据采集方法 触发式数据采集采用触发探头，触发探头的探针由于接触到样件表面受力变形触发采样中的开关，此时数据采集系统就会记录下探针尖（测球中心）的坐标，逐点移动就能得到样件表面轮廓的整体坐标数据。在触发式数据采集过程中，为防止探针受力过大而造成折断，探针需要法向退出，因此数据采集速度较低。2）连续式数据采集方法 连续式数据采集采用模拟量开关采样头。由于接触力较小，扫描速度快，连续式数据采集可以用于采集大规模的数据。3）磁场法 该方式需要将被测工件放在被磁场包围的工作台上，通过手持触针在物体表面运动，触针上的传感器就会感知磁场的变化，从而检测出探针的位置，进而获得样件表面的特征，实现数字化。但该方式不适用于导磁的工件。接触式数据采集的特点如下所述。● 接触式数据采集具有较高的测量精度，且不受物体表面颜色及光照的限制，对物体的边界也能产生准确的测量结果。● 由于接触式数据采集设备测头的限制，数据采集的速度不可能太快，测量的同时可能会丢失某些测头不可到达的工件细节数据。● 不可测量某些测头不可触及的软材料。由于接触式测量方法本身固有的局限性（如速度慢、对硬度较低的模型可能有较大的误差），非接触式测量方法逐渐成为主流，其中的光学测量种类很多，由于其抗干扰能力强、结构简单，因此得到广泛应用。近年来，随着计算机机器视觉这一新兴学科的兴起和发展，用非接触的光电方法对曲面的三维形貌进行快速测量己成为大趋势。这种非接触测量不仅避免了接触测量中需要对测头半径加以补偿所带来的麻烦，而且可以实现对各类表面进行高速三维测量。2．非接触式数据采集方法非接触式方法利用某种与物体表面发生相互作用的物理现象来获取其三维信息，如声、光、电磁等。非接触式按其原理不同，可分为光学式和非光学式，其中光学式包括三角法、结构光法、计算机视觉法和激光干涉法等；非光学式则包括CT测量法、MRI测量法、超声波法和层析法等。按测量过程的不同，非接触式测量又分为主动式测量和被动式测量。主动式测量系统中成像设备发出一束信号，通过接受物体表面反射回来或穿透物体的信号生成图像；被动式测量则没有信号发出。最常用的主动式测量有激光三角形测量法和光栅法。被动式非接触测量系统由物体辐射信号或物体表面反射信号生成图像，无特殊光源，因而设备简单、操作方便、成本低，但算法复杂，基于焦距测距法、全息法属于被动式测量系统。破坏性测量主要是自动断层扫描法，该技术采用逐层去除材料与逐层扫描相结合的方法。1）立体视觉法（被动三角法） 该方法三维信息获取是基于图像分析的方法，典型的被动三角立体视差法（Stero Disparity）是通过固联在某一运动载体（如机器人）上处于不同位置的两台摄像机获取同一运动物体的图像，经过图像处理得到安装在目标体上几个特征标志点（大小、形状已知）像点的中心位置，在此基础上根据透视投影的几何原理，得到标志点的空间位置信息，然后通过两幅图像中的3D匹配点对，计算出物体的运动参数（位置、姿态信息）。常用的匹配算法有灰度相特征法。由于匹配精度的影响，所以较难精确地恢复复杂曲面物体的三维信息。近年来由于机器人技术的发展，计算机视觉技术日益受到重视，基于立体摄影的计算机视觉技术不仅可获得三维环境中物体的几何信息如形状、位置、姿态、运动等，而且能对它们进行描述、存储、识别与理解。2）层切法 层切法可用于测量物体截面轮廓的几何尺寸，其工作过程是，将待测物体用专用树脂材料（填充石墨粉或颜料）完全封装，待树脂固化后，把它装夹到铣床上，进行微吃刀量平面铣削，结果得到包含有物体与树脂材料的截面，然后由数控铣床控制工作台移动到CCD摄像机下，位置传感器向计算机发出信号，计算机收到信号后，触发图像采集系统驱动CCD摄像机对当前截面进行采样、量化，从而得到二维离散数字图像。由于封装材料与物体截面存在明显边界，利用滤波、边缘提取、纹理分析、二值化等数字图像处理技术进行边界轮廓提取，就能得到边界轮廓图像。通过物—像坐标关系的标定，并对此轮廓图像进行边界跟踪，便可获得物体该截面上各轮廓点的坐标值。每次图像摄取与处理完成后，再使数控铣床把待测物体铣去很薄一层（如0.01mm），又得到一个新的横截面，并完成前述的操作过程，就可以得到物体上相邻很小距离的每一截面轮廓的位置坐标。由逐层数据叠加重建三维图形。层析法的特点是可以采集体数据进行体重建，其缺点是速度较慢， CT、MRI 三维重建原理也与层切法类似（但是是非破坏性的），不过由于CT每层切片间距大，获得的数据量也少，重建后的数据精度达不到要求。3）相位法 相位测量法是以测量投影到物体上的变形光栅像的相位为基础，通过相位与高度的映射得到被测物体的三维轮廓，虽然在相位—高度的转换过程中也使用了三角法原理，但其核心技术还是相位的测量，与直接三角法有一定的区别。其基本原理为，将基准栅板投影至被测形体表面，形成被表面形状调制后的变形栅线图像，根据特定的光学投影与成像装置，利用光学函数分析法使得被测曲面高度值与调制栅线图像中的相位值之间建立起一一对应的函数关系。依据解调相位值的不同，相位法三维检测又可分为相移法、卷积技术以及傅里叶变换等，但其基本原理是相关的（其中莫尔云纹法较为特殊）。与直接三角法相比，相位测量法能满足全场的测量，测量精度比较高，测量速度比较快，但是这种方法对物体上的物理断点、阴影等使图样不连续的缺陷会造成较大的误差，往往要通过特定的算法识别并绕过缺陷才能完整而准确地恢复物体的三维轮廓。4）激光全息测量法 这种方法本身不属于相位法，但它必须与相位法结合起来才能用于三维测量。全息图是利用光的相干性将物体发出的光的振幅和相位同时完全地记录下来所得的图样。当进行再现时，通过衍射或第二次傅里叶变换就可以得到宛如物体的三维像。激光全息只能在视觉上重现物体的三维图像，如需定量测量则需与莫尔云纹、光电检测、CCD 数据采集技术结合起来，目前的计算机全息干涉计量技术理论上是可以用于三维立体测量的，但由于全息技术对环境与设备要求高，这种技术远不如投影光栅技术简单实用。5）投影光栅法 其主要使用技术是相位法，技术最成熟，已投入商业使用，但需要拍摄多幅图像。空域相位测量与傅里叶变换只需一幅图像。这是一类主动式全场三角测量技术，通常采用普通白光将正弦光栅或矩形光栅投影于被测物表面上，由CCD摄取变形光栅图像，根据变形光栅图像中条纹像素的灰度值变化，可解算出被测物面的空间坐标。这类测量方法具有很高的测量速度和较高的测量精度。目前发展方向主要集中在投影方式、相位解包裹算法及提高精度上。6）主动三角法（三维激光扫描系统） 也称为激光位移计测器。主动三角法按投影到被测物体上光的图案形状不同，可以分为基于点的三角测量法（点结构光）、基于线的三角测量法（线结构光）和基于图案的三角测量法（图案编码法）。它们的工作原理如图1-1所示。激光束照射到待测物体表面，在其上形成漫反射光斑，光斑经成像物镜在CCD器件上成像。测点距参考平面的距离d决定了CCD器件上像点P的位置。这样，通过解读出P点的位置即可计算出待测距高度。激光位移计测器按传感器的多少可分为单眼式和复眼式两种。单眼式是指配有一个光学传感器（CCD，电荷耦合元件）的激光位移计测装置，而复眼式计测装置有两个或两个以上成对配置的 CCD，其测量时间较单眼式计测装置有所减少，而且可以减少扫描盲区。单眼法获得数据量一般较双眼法减少约25%。图1-1 主动三角法工作原理7）激光三角测距法 激光三角测距法是逆向工程中曲面数据采集运用最广泛的方法，具有以下特点。（1）探针不与样件接触，因而能对松软材料的表面进行数据采集，并能很好地测量到表面尖角、凹位等复杂轮廓。（2）数据采集速度很快，对大型表面可在 CMM或数控机床上迅速完成数据采集。所采集的数据是表面上的实际数据，无须测头补偿。（3）价格较贵，杂散反射，对于垂直壁等表面特征会影响采样精度。目前在技术上成熟的几种扫描方式如机械、激光、相位法、立体摄影和层切法各有其优势。机械式精度可以很高，并能获取倒凹区数据，但采集时间长，发展趋势是换用新型探头加快扫描速度。激光法发展最成熟，系统可靠性强，开发成本低，其缺点是依然有扫描盲区的问题，发展趋势是采用线扫描加快扫描速度，采用改变扫描轨迹以求最大限度地减少扫描盲区。采用相位法中的投影光栅法的系统目前有增多的趋势，其优点是全场、快速，缺点是要喷涂特制的反光层以改善反光性能，开发成本高，与激光扫描法一样也有扫描盲区问题。立体摄影法应用不多，主要是精度问题，但这种方法是最具有发展前景的数据采集方式。层析法是目前较完整地获得所有数据的扫描方式，但精度低，扫描时间较长，主要用于正畸模型数据采集。数据采集方法分类如图1-2所示。图1-2 数据采集方法分类1.2 三维重构关键技术
随着三维重构技术的不断发展，采用离散的点云数据来表示物体表面特征的方式逐渐成为了学术研究的热点，点云模型可以很好地表示高复杂度和高度真实感的物体和场景。近年来，数据采集技术的发展使快速获取三维物体的外形数据成为可能，如何由扫描数据快速、高精度地表示出物体表面是一个重要的、极具挑战性的工作。在获得三维数据点后，主要的后处理工作包括点云去噪、点云配准、孔洞修复、数据简化和压缩、表面重建等，以下将对各个环节分别说明。1.2.1 数据的去噪
测量中由于测量仪器、被测对象及其他方面的因素，不可避免地会引入一些噪声点，而噪声点对模型的重构会有很大的影响。为了更精确地提取特征和得到较好曲面模型，有必要对数据点进行光顺去噪处理，如图1-3所示。对于不同的测量设备噪声产生的原因也各不相同：对于非接触式设备，主要是由于被测物体本身的（如被测物体的位置、表面的粗糙度和波纹、反射特性、颜色及对比度、环境光照条件等）及测量系统的误差引起的；对于接触式设备，更多的是受被测量力带来的系统误差、随机误差及测量设备灵敏度的影响较大。图1-3 数据的去噪测量所得的散乱数据点的排列形式一般有以下4种：扫描线式（数据点几乎都位于同一等截面线上）、阵列式（数据点具有行列的特点）、三角网格式（数据点呈网格状互连）、散乱式（数据点呈完全散乱状，无次序无组织）。前三类数据都属于有序或部分有序数据，对于这类数据通常可采用标准高斯、平均或中值滤波算法来进行去噪。高斯滤波在指定域内的权重为高斯分布，平均效果较小，故能较好地保持数据的原有特征；平均滤波对采样点取值为滤波窗口内各数据点的统计平均值，滤波效果比较平均；中值滤波对采样点取值滤波窗口内各数据点的统计中值，消除数据毛刺的效果较明显。对于最后一类无序散乱点云，因为没有建立点与点之间的拓扑关系，因此就不适宜直接采用平滑滤波的方法，可先建立数据点的拓扑关系再进行去噪处理。通常点云数据的邻域构造有两种方式，即根据欧氏距离和 K 邻域构造。欧氏距离只适用于规则采样表面，而不规则表面可能会导致包含的邻域点过多或过少。K邻域（K-nearest neighbors，K个欧拉距离最近的点）方法提供了一种邻域的自适应估算方法，国内外许多学者对在散乱点云中寻找K邻域进行了很多的研究，常用的方法有如下3种。1）空间单元格法 按照一定的间隔在 x，y，z 三个方向上分别创建一系列平行平面，将数据点的包围盒划分为许多单元格，取各单元格中最靠近单元格中心的数据点作为中心点来代替整个测量数据。2）八叉树法 基于八叉树的方法来分割，根据包围盒与数据点空间分布的对应关系建立点的拓扑关系。3）K-d tree法通常用于查找距离最近的两点，它是一种便于在空间中进行点搜索的数据结构。在找出K邻域后，可进一步找出Delaunay邻域，方法是对某一数据点的邻域在该点切平面上投影并进行Delaunay三角剖分。1.2.2 数据的配准对齐
在对实物进行数据点采样时，由于受到测量设备和环境的限制，往往不能在同一坐标系下将被测物体的几何数据一次测出，物体表面完整测量数据的获得往往需要通过多次测量完成。究其原因，一是被测物体尺寸过大，超出了测量设备的行程；二是在某些区域，受被测实物几何形状的干扰而不能测量到产品的反面。因此，在几何模型构建时，必须将这些不同坐标系下测得的数据点变换到同一个坐标系中，这一处理过程被称为数据点的对齐，或者数据配准、拼合、重定位等，如图 1-4所示。图1-4 点云的配准对齐对齐问题最初是在计算机图形学及动画中提出的，主要是用于处理模型的刚体运动，以及刚性物体相对一个参考的位置。本质上，数据对齐是一个优化问题，目标是找到合适的欧几里得变换参数，使一组数据与另一组数据匹配。三维数据配准技术主要分为如下两大类。● 机器配准：采用经过高精度定标的仪器获取的多视点数据，以及它们之间的原始变换关系，来进行数据间的配准计算；● 自动配准：利用数据中的变换信息，或者利用在数据获取的同时引入的其他信息，对三维数据进行配准计算。Besl和McKay提出的ICP算法（Iteartive Closest Point）配准精度比较高，但是其计算速度也很慢，尽管收敛速度很慢，但仍在图像匹配、计算机可视化及逆向工程等方面得到了广泛的应用，不仅适合于处理数据点的对齐问题，也被用于处理其他一些几何对象的对齐问题（如点集、多边形、曲线和曲面），该方法是目前解决点云数据配准对齐的基本算法。实质上，ICP算法是重复进行“确定对应关系点集，计算最优刚体变化”的过程。对于两个待拼接的点集P和Q，设Q为固定不动的点集（参考点集）， P为目标点集，为了使P能够和Q拼合在一起，首先对点集P中的每一个点在Q中寻找一个与它距离最近的点，并建立点对之间的映射关系，再通过最小二乘法来计算一个最优坐标变换（即旋转矩阵 R 和平移矢量 T），进行迭代求解直到满足精度为止，最终求出 R和T。传统ICP算法只适用于存在明确对应关系的点集之间的定位，且每次迭代都需计算目标点集中每个点在参考点集中的对应点，计算效率不高，国内外许多学者都对ICP算法做出了改进。为了缩小点云之间的旋转和平移错位，需要对点云进行初始配准，目前常见的初始配准方法有以下4种。1）标签法 即在测量时，在被测量物体上贴一些标签作为特征点，之后使用这些特征点进行定位；2）提取特征法 该方式要求点云数据有较明显的特征（如平面特征、轮廓曲线等）；3）主方向贴合法 点云空间上的主方向可通过计算所有点的特征向量来得到，与主方向垂直的两个次方向还可根据特征向量得到，这便建立一个以点云重心为原点、主方向和次方向为坐标轴的一个参考坐标系，初步配准时只需将参考坐标系调整一致即可实现；4）中心重合法 该方法简单地将两个点云的重心重合，只能减少平移错位，无法减少旋转错位。1.2.3 孔洞修复
在逆向工程中，三维重构往往要涉及一些孔洞修复的问题，这些孔洞会对所重构模型的质量产生很大的影响。出现孔洞的主要原因是由于测量或人为因素而导致出现的噪声、冗余、数据缺失等问题。另外，一些逆向工程处理软件在从散乱数据点到三角网格的重建过程中，可能会在数据信息量不足的部位产生孔洞。孔洞修复的目标不仅要对洞、裂缝等进行修复，同时对修复好的区域要尽可能复现类似于周围区域的细节，如图1-5所示。图1-5 孔洞修复对孔洞修复的技术大致可以分为两类，即基于体素的和基于曲面的。基于体素的修复算法是将模型转化为一种体表示（ Volumetric Resentation），它是由称为体素的离散体组成的，然后使用各种方法在体空间进行孔洞修复，该方法计算复杂度高，并且有时会产生错误的拓扑信息。常用的曲面修复方法是基于隐式曲面的（如全局紧支撑的径向基函数拟合、基于MLS曲面重建等），该方法相对简单且容易实现，但所构造的孔洞曲面是光滑的，缺乏曲面的几何特征，适合于对平坦区域孔洞，对于复杂孔洞的修补效果不太理想。依据孔洞特征及算法的需要，可将待修复孔洞划分成简单孔洞、岛屿孔洞、环状孔洞和边界孔洞4种类型。对于简单孔洞，可先获得法向约束点与插值约束点，再建立变分隐式曲面方程，并将该曲面网格化以得到初始孔洞网格，最后再对超出原网格区域范围的初始孔洞网格进行裁剪与缝合。对于岛屿孔洞，由于其内部的孤立三角片数量总数比较小，则可以参考孤立三角片的信息进行简单孔洞修补，此外在进行裁剪与缝合时，裁剪边界顶点的只是岛屿孔洞的外边界。对于环状孔洞，可把它看成是岛屿孔洞的一种（即孔洞内部存在一个三角片数量很多的岛屿）。对于边界孔洞，由于孔洞边界是不封闭的，因此需要构造一些附加点来得到孔洞的封闭边界，之后再利用边界信息获得插值曲面。1.2.4 数据的简化与压缩
通过三维扫描获取的数据量通常都比较大（如光学扫描设备常采集到数十万、数百万甚至更多的数据点）。因此，为了方便编辑处理模型，必须对数据模型进行简化。到目前为止，对点云模型的简化算法大部分是直接将对网格模型简化方法推广到点云模型中。另外，有效的三维模型压缩技术，对减少三维几何数据的存储量，降低其在网上传输所需的带宽等具有十分重要的意义。1．数据的简化点云的简化作为点云处理的一个基础步骤，可以去掉原始点云数据中的冗余部分，得到一个精简的模型，有利于点云的后续的处理和造型。简化方法必须满足能用较少量的点来逼近原始点云模型。当然，逼近程度越高，误差越小，表明简化方法越好。点云简化算法一般分为了三类，即聚类法、迭代简化法和粒子仿真法。聚类分析方法就是把点云数据分裂成多个相互无交集的子集，在每个子集中用一个具有代表性的点来代替所在子集中所有的点，该方法已被应用于许多计算机图形应用领域，用于减少三维物体的复杂性。通常，该方法就是把模型的包围盒细分成多个网格单元，然后用一般性的描述网格单元来替代所有的采样点云。使用固定大小的网格单元并不能适用于非均匀采样点云，而且当栅格过大时，体划分的聚类法很容易把非连接的表面整合到一个栅格内。为了克服这一缺点，基于表面的聚类分析技术开始应用起来。面划分的基本思想是根据采样点的密度大小把相邻采样点划分为一个集合中。可采用区域增长的方法或分层方法来建立聚类，分层方法即把点云以自顶向下的方式分解成多个小的子集。这两种方法都建立了一组簇{C}，对于每个点，存在一个唯一的簇C，满足，然ii′后分别用每个簇的质心来代替这个簇中所有的点，从而得到简化后的点云P，其中质心通过下式得到：聚类分析方法中的一种称为增量式聚类，对于任一点，簇C是通过连续添加0最近邻来建立的，当簇的大小达到最大限制条件时，这种区域增长才会终止，这样表面变化剧烈的区域就会建立起较多的并且较小的簇，下一个簇C将选择C的10邻域中的一个点作为新的种子进行区域增长，但是不包括C中所有的点。当所有0的采样点都已经被分配到{C}的每个簇中时，这个增量式聚类算法终止。i迭代法非常类似于渐进网格简化方法。在网格的简化中，Alexa给每个网格顶点都分配一个误差，然后从小到大排列，最小的顶点最易被简化。简化后重新计算每个顶点的误差，再去除顶点，直至误差在允许的范围内。这种点迭代去除法导致采样后的点云只是原来点云的一个子集，效果不佳。因此，后来有学者提出采用点对（边）的简化来替代点的去除。粒子仿真法是采样多边形面的一种方法，采样点精度与多边形面的面积相关，采样后的点被严格地限制在多边形的面内，从而保证采样后的精度。Turk首先初始化一个随机分布的点云在模型表面上，接着使用一个互斥力来控制随机分布点的位置。由于互斥力会使粒子脱离原来的模型表面，可以对粒子进行移动最小二乘曲面（Moveing Least Squares，MLS）的投影运算，将其投影到原来的表面上。将点的互斥半径大小与曲面变化度结合，就可以得到一个曲率自适应的简化点云。2．数据的压缩三维网格的压缩一般是指多边形网格中几何信息的压缩和连接信息的压缩。网格压缩的研究始于Deering在1995年SIGGRAPH上的一篇名为“Geometry compression”（几何压缩）的论文，并很快成为三维图形领域中一个重要的研究方向。三维网格压缩按照解码方式可分为非渐进压缩（Non-progressive compression）和渐进压缩（Progressive compression）。非渐进压缩是将网格压缩成具有单一目标比特率的码流，所以又称为单一位率压缩（Single-rate compression）。压缩时，将网格中的几何数据和拓扑连接视为一个整体进行编码、传输和解码，解码操作只有在获得整个编码数据序列后才能进行。而渐进压缩是将网格压缩成具有多个目标比特率的码流，可根据接收到的部分数据序列进行解码，重构出不同近似程度的网格。早期的非渐进压缩算法多为拓扑信息驱动的压缩，主要是对拓扑信息进行压缩编码，在此基础上再进行几何数据压缩。拓扑压缩算法主要是解决如何用比较少的比特来表示边或三角形与顶点之间的连接关系的问题。由于几何数据占据了网格数据的大部分，目前的研究以几何数据编码为主，在几何编码的驱动下来进行拓扑信息编码（称为几何信息驱动的压缩方法），有时甚至可以改变原始网格的拓扑连接来获取比较高的压缩率。渐进压缩是将一个简单的粗糙网格和各层次细节的位流序列进行多分辨率分解，并进行编码和传输，渐进压缩能够提供对数据传输中的三维物体中间状态的访问。由于三维网格顶点坐标间具有很强的相关性，其拓扑连接符号表示具有集中性，因此可以引入小波技术，以充分利用小波的能量去相关性、集中性、多分辨率分析等良好特性来提高三维网格的压缩比率和效率，小波变换在非渐进压缩和渐进压缩中都有着重要的作用。压缩连接信息时，可运用某种遍历算法对网格先进行遍历，将遍历后的结果表示成某种序列，再对该序列进行熵编码。对几何信息来说，由于小波变换后大部分小波系数的值集中在零附近，具有较强的去相关能力，有利于进行熵编码。对于渐进压缩而言，可以用一些不同分辨率层次的近似序列来表示一个半正规曲面，可通过小波变换将对应的嵌套细节序列转换为一个基网格和小波系数序列的表示，也可通过小波系数来表示连续的网格层次细节之间的差异。1.2.5 表面重建
表面重建是逆向工程和三维重建中的重要问题，长期以来一直是图形学领域的研究热点，受到研究人员的高度关注。概括来说，所谓曲面重建是指根据几何体的观测数据重建出嵌入三维空间的二维流形。研究人员已提出各种曲面重建方法，这些方法大致可分为插值/拟合重建、细分曲面重建、变形重建、隐式曲面重建、参数曲面重建、基于学习的重建等。（1）插值/拟合重建采用基函数等对采样点作线性或非线性逼近，以求取近似曲面，每一个采样点位于近似曲面上或近似曲面的附近。该方法通常具有较高的精度，当采样点比较稠密时，即使采用低阶多项式逼近，也能获得良好的重建效果。（2）细分曲面是一种利用极限形式逼近需要重建曲面的迭代方法，该方法是Hoppe于1994年提出的。首先通过反求控制顶点求出重建曲面的初始控制网格，然后不断应用细分规则对控制网格进行细分，生成细分曲面。基于不同细分规则的细分曲面不断涌现，基于四边形网格的Catmull-Clark、Doo-Sabin细分算法、基于三角网格光滑曲面Loop细分等。由于细分算法是按一定的规则产生新点的一种迭代法，所以应用细分算法进行曲面重建有着其他算法无法相比的优势，这主要表现在细分算法简单直观，表示方法一致，在进行局部调整的同时可以保证曲面整体的光滑性，能够快速在任意网格上生成光滑曲面，克服参数曲面难以实现的任意拓扑网格中曲面片间光滑拼接的困难。同时，由于细分曲面只是一种离散的表示形式、没有解析表达式，这使得曲面的内在几何量难以计算。（3）变形重建首先定义封闭曲面，然后在外力和内力作用下逐步变形，直至与原数据集吻合。该类型方法的主要思想是，对需要重建的任意拓扑结构的曲面，构造一张初始曲面（如在待建曲面内部建立一个曲面模型），通过赋予曲面一定的物理属性，使曲面在内外力作用下沿着一定的方向进行形变（如在外力作用下内部模型进行膨胀变形），并以重建曲面上的采样数据点作为变形的约束条件，直到近似给定的数据集，此时重建曲面的几何模型处于某一平衡点，这个最终处于某一平衡点的几何模型即为重建曲面。变形模型方法或基于物理变形的曲面重建是一种动态的曲面重建方法，一般来说具有精度高、造型优美、逼真等优点，适用于描述各种生物体、形状造型奇特或柔性变形体，但由于初始变形模型的建立较为困难，以及求解规模庞大导致求解速度慢，限制了此种方法进一步开发与应用。（4）隐式曲面重建将待重建曲面看做某一函数的零水平集，采用优化或拟合的方法得到函数表达式，然后利用Marching Cubes等方法计算曲面采样点。对给定的空间曲面上的测量数据点集，寻求一个函数，使得该函数的零集逼近于数据点集，根据函数选择的不同，可有以下3种常用形式。① 简单曲面：主要包括平面、二次解析曲面、旋转曲面和可展曲面等。这些函数都是多项式函数，利用多项式的零水平集与点云与数据之间距离平方和的最小化。简单曲面的解析表达式十分简单，易于掌握，但其不能描述重建复杂拓扑结构的自由型曲面。② 超二次曲面：主要包括超椭圆面、超环面超单叶双曲面和超双叶双曲面等多种类型的标准超二次曲面、变形的超二次曲面等。超二次曲面建模的过程实际上是对超二次曲面模型进行参数拟合的过程，它是将物体表面用参数方程来描述的，这既能有效地反映物体的空间占有属性，同时也能反映物体的惯性平衡。由于超二次曲面的数学描述很稳定，所以基于此种数学描述的模型重构方法也很稳定。③基于径向基函数（Radial Basis Function，RBF）：它主要利用正定、条件正定函数和径向基函数的非线性逼近能力和抑制样本噪声能力的特性对曲面进行拟合。由于 RBF 插值对待插值数据点的排列几乎没有任何要求，这使得 RBF 在散乱数据的曲线、曲面模型重建领域中非常受欢迎，常用的径向基函数有多二次样条函数、薄板样条及高斯函数等。由于 RBF 插值的计算量非常大，使其应用在很大程度上受到了限制。随着算法的不断改进及局部紧致支撑径向基函数的应用，径向基函数逐渐成为了多变量插值的一个重要的工具。（5）近年来，基于学习的表面重建受到研究人员的关注，如通过训练人工神经网络，使网络实际输出与期望输出之间的距离最小化，训练后的网络连接权值和阈值即代表原曲面的映射关系。根据神经网络模型选择的不同，可形成不同的基于神经网络的曲面重构方法。神经网络方法具有强大的泛函逼近能力，能以任意精度逼近任意连续函数及其各阶导数，适于重建曲面及重建曲面的局部修改，但也存在着收敛难度大，计算费用高等不足，这些不足制约了该方法在任意拓扑形状曲面重建中的应用。1.3 三维重构技术应用
三维重构技术就是将一定方式记录的三维信息加以整理，转化成计算机能识别的数据，并在计算机中进行处理，将三维物体数据结构中蕴含的几何信息恢复成图形、图像显示出来，由此可以方便、快速地对物体进行定量的分析、显示和处理。作为计算机图形学的一个分支，三维重构被应用于机械制造业、汽车业、电子业、航空业、医药学及皮肤医学、古生物学及考古学、建筑业等多种领域。例如，在机器人加工控制中，在加工一个零件的毛坯前，机器人必须先建立毛坯的三维模型；在计算机辅助设计中，一个自然二维体模型的自动生成可作为CAD系统的输入；在动画制作中，为动画制作者提供大量真实世界的模型等。扫描数据的来源可能不同，三维重建技术对各种不同来源的数据有相通之处。三维重构技术广泛应用于研究、生产和生活等民用和工业领域中。民用领域的应用主要包括三维数字摄影、三维型面检测；人体数字化、服装CAD、人体建模、人体数字雕塑、三维面容识别；医学仿生、医学测量与模拟；整形美容及正畸的模拟与评价；三维数字化、数字博物馆、有形文物及档案的管理、鉴定与复制；三维动画影片的制作、三维游戏中三维模型的输入与建立；公安刑侦、脚印、工具痕迹、弹痕采集及数字化。工业领域的应用主要包括工业产品的检测与测量、产品及模具的逆向工程（汽车，航空，家电工业）；零部件形状变形检测、形状测量、工业在线检测；工业产品造型中的逆向三维重构；设计物体模型转换到数字模型；工业产品及零部件的质量检测；工业品的解析；工业研究实验的检测工具；模具设计与检测领域。三维重构是计算机视觉技术的主要内容之一，计算机三维重建理论及其实现技术在战场三维地形建模、战场监视及精确导航等领域有着重要的应用。散乱数据点的曲面重建一直是函数逼近论的一个重要研究内容。近几年来，随着计算机辅助设计与图形学的发展，散乱数据的曲面重建技术得到了广泛的应用，如基于测距技术的几何模型自动生成、医学成像数据的可视化等，该技术的发展有力地促进了造型和可视化等技术的高速发展。下面介绍几种三维重构技术的典型应用。1．逆向工程传统的产品制造通常是先有设计图纸再有产品，称为正向工程（或顺向工程）。而逆向工程（Reverse Engineering，也称为反求工程、反向工程等）是基于测量数据的产品造型技术，它首先重构出一个实物的三维数字模型，然后再利用CAD系统完成产品的制造，可以简单地定义为“理解原始的设计意图和机制”，如图1-6所示。逆向工程可实现对产品的快速设计，极大地缩短了新产品的开发周期，提高了产品精度。在市场竞争日益激烈的形势下，逆向工程是快速消化、吸收先进技术进而创新和开发各种新产品的重要手段，也是快速开发、降低成本、提高竞争能力非常有效的手段。图1-6 逆向工程2．医学图像中的应用计算机图像处理与分析、计算机图形学及虚拟现实技术相结合的医学图像的三维重建技术近年来是国内外研究和应用的热点。通过对人体器官、软组织和病变体进行三维重建，能够更直观、准确地重现观察对象的三维结构，可以辅助医生对病变体及其他感兴趣的区域进行准确的定量分析，大大提高医疗诊断的准确性和正确性。现今在PC上进行CT图像的三维重建流程如图1-7所示。首先，对从成像设备获取的断层数字图像进行预处理；其次，将医生感兴趣的组织从断层图像中分割开来；再次，在相邻两个断层图像间进行内插；最后将重建后的三维图像数据在计算机屏幕上进行立体感显示，要对它进行各种几何变换的运算，实现多种投影显示方式及几何尺寸的测量等。图1-7 三维重建流程图2002年10月，第三军医大学完成了首例中国数字化可视人体数据集，该数据集的薄层断面图像清晰、层厚均匀，且有相应层面的 CT、MRI检查图像对照，完全能满足断层解剖和三维重建的要求。3．数字博物馆数字博物馆是运用数字、网络技术，将现实存在的实体博物馆的职能以数字化方式完整呈现于网络上的博物馆。与实体博物馆相比较，“数字博物馆具有信息实体虚拟化、信息资源数字化、信息传递网络化、信息利用共享化、信息提供智能化、信息展示多样化等特点”。中国数字博物馆建设从20世纪90年代起步，逐步进入快速发展阶段。近年来，中国在数字博物馆建设方面取得了可喜的成绩，从“博物馆数字化”、“博物馆上网”到“数字化博物馆”、“数字博物馆”，从启动“大学数字博物馆建设工程”、“中国数字博物馆工程”到“北京中医药数字博物馆”、“北京数字博物馆平台”、“中国数字科技馆”开通运行，一批数字博物馆、数字科技馆突破时间和空间的限制，方便、快捷地为社会公众提供公益性信息资源服务，成为展示中华历史文化的舞台。1.4 本书的章节安排
本书以点云数据为主要研究对象，对数据的获取与去噪、数据的对齐配准、孔洞修复及数据压缩进行了研究，共分7章，其中第一章主要论述选题背景及意义，以及所涉及研究内容的简要介绍；第二章主要介绍相关几何知识及散乱数据点三维重构中用到的一些经典算法；第三章对点云数据光顺去噪进行了研究；第四章对点云数据的对齐配准进行了研究；第五章对点云数据中的孔洞修复问题进行了研究；第六章对网格的简化与压缩常用算法进行了介绍；第七章对点云数据曲面重建中的网格方法及一些相关技术进行了介绍。第二章相关几何知识
点云数据往往隐含着一个潜在形状，其上的几何微分信息（如切向、法向、曲率等）是点云几何建模和复杂应用的基础。本章主要介绍相关几何知识及散乱数据点三维重构中用到的一些经典算法。2.1 空间曲面的几何
在三维空间中有以下3种办法给出曲面。1）显示表示 以函数的图像来定义。2）隐示表示 以方程来定义。3）参数表示 以参数形式r=r(u, v)来定义，或者写为x=x(u, v) ， y=y(u, v) ， z=z(u, v) ，其中参数u ， v在(u, v)平面某个区域内变动，通常取正方形，即u, v∈[0,1]。x ， y ， z都是u和v的二元可微函数。当(u,v)在u,v∈[0,1]中连续变化时，与其对应的点(x, y, z)就形成一张曲面。曲线的非参数表示存在的问题是，与坐标系相关，会出现斜率为无穷大的情况（如垂线），非平面曲线难用常系数的非参数化函数表示，不利于计算和编程。一条参数曲线的表示形式并不是唯一的。例如，在第一象限内的单位圆弧可表示成取角度为参数时，x和y的关系如图2-1（a）所示，取t为参数时，x和y的关系如图2-1（b）所示。理想情况是，参数的间隔和相对应曲线的弧长呈线性关系。图2-1 单位圆弧的参数曲线表示参数表示比非参数表示更优越，这是因为参数方程的形式不依赖于坐标系的选取，具有形状不变性；在参数表示中，变化率以切矢量表示，不会出现无穷大的情况；对参数表示的曲线、曲面进行平移、比例、旋转等几何变换比较容易；用参数表示的曲线曲面的交互能力强，参数的系数几何意义明确，并提高了自由度，便于控制形状。2.1.1 参数曲线的切矢量、弧长、法矢量和曲率
设曲线的参数方程为1．位置矢量曲线上任一点的位置矢量可表示为2．切矢量图2-2 参数曲线的切矢量在极限情况下，弦长和弧长相等，即T称为P (t )处切线方向的单位矢量。上式说明，如果以弧长为参数，曲线在任意点的切线为单位矢量。切矢量模的大小与选择的参数有关，但方向是不变的，选择弧长为参数，切线为单位矢量，也就是时间标准不一样，速度大小就不同。3．弧长对于正则曲线P(t)从点P(0)到点P(t)的弧长定义为从微积分的意义讲，上式是曲线从P (0)到点P (t )的折线长度的极限，令4．曲率如图 2-3 所示，设以曲线弧长s为参数，曲线上的点P (s )和点处的单位切矢量分别为T(s)和记两切矢的夹角为，。是弧长，所以通常用比的绝对值来度量弧图2-3 曲率计算当0时，曲线在点P(s)处的曲率K(s)为试读结束[说明：试读内容隐藏了图片]