随着工业化的发展与市场竞争的激烈化，自20世纪以来，我们对产品研发的时间和产品的更新换代速度提出了越来越高的要求，因此迫切需要新的设计制造技术来满足市场需求。传统的制造生产过程通常采用手工绘图、发图、凭图纸组织整个生产过程的技术管理方式，已经远远不能满足生产需求。
CAD技术的迅速发展和推广应用，给古老的制造工业带来了蓬勃的生机，使传统的设计方法与生产组织模式发生了深刻的变化，为企业实现产品设计现代化、缩短设计周期、提高产品质量、增强市场应变能力和生存能力、参与过激市场竞争提供了强有力的技术手段。CAD技术，即计算机辅助设计与制造（Conputer Aided Design & Copnuter Aider Manufature,CAD/CAM）技术，是计算机应用的最重要的领域之一，它指利用计算机技术完成设计过程中的信息检索、分析、计算、综合、修改及文件编制工作。它是先进制造技术的重要组成部分，是计算机在工程中最有影响的应用技术之一。
CAD/CAM技术从根本上改变了过去的技术管理方式，将它变为在图形工作站上交互设计、用数据文件发送产品定义、在统一的数字化产品模型下进行产品设计打样、分析计算、工艺计划、工艺装备设计、数控加工、质量控制、编印产品维护手册、组织备件订货供应等。CAD技术的开发与应用水平已成为衡量一个国家科技现代化和工业现代化水平的重要标志之一。CAD/CAM技术已日趋成熟，其应用范围也从早期的军事、航空航天、机械、电子等工业部门扩展到冶金、建筑、化学、医学、教育、影视、广告等各个专业领域。
然而，随着现代工业制造水平的发展和计算机图形学的发展，许多领域，如仿形加工、模具快速制造、三维服装设计、玩具设计、三维动画、艺术品制作、动植物模拟、人体器官复制、地形测量与数字化再现等，都出现了对“实体数字化”技术的强烈需求，越来越多的产品零件开始大量采用不规则复杂曲面，其设计、生产、检测、试验等环节需要进行大量的三维曲面实体数字化和三维测量，而企业、研究机构甚至个人又迫切地需要得到实体的高精度数字化模型，和快速、高效、准确、移动式的三维测量技术和反求逆向设计技术。利用传统的CAD几何造型技术进行设计不仅费时且不能得到物体真实的几何信息，需要造型方法、设计手段的进一步丰富和发展[2]。
近几十年以来，随着微电子、自动化.、计算机、网络等科学技术的迅猛发展，数字化技术便应运而生了。数字化技术是以计算机硬件、周边设备、协议和网络为基础的信息离散化表述、定量、感知、传递、存储、处理、控制、联网的集成技术。在当今机械制造领域，数字化技术越来越广泛地应用于产品生产中。从产品设计期的CAD三维建模到CAPP实现整个加工工艺计划再到后来的CAM数控加工，数字化技术均起着重要的作用。并且由于数字化技术的应用使得机械制造行业取得长足的发展。以三维光学扫描技术为代表的三维采集技术即是数字化测量中的一只生力军，已经在逆向工程、数字化博物馆、工业检测、影视娱乐、医学、建筑等领域已经得到了广泛的应用，是实现“实体数字化”的一种重要技术。
不同于传统的建模手段，三维光学扫描仪采用非接触的测量方法[5]，来获得物体表面点的三维坐标信息，从而直接得到真实物体表面的采样点，即点云数据，利用点云数据即可以重构出任意曲面，它属于一种立体测量技术。这种方法不受曲面复杂度影响，表面采样密度足够的话可以达到很高的重构精度，能够完成对复杂物体的测量，特点是非接触、精度高、速度快，能大幅节约时间和成本，并且其测量数据通用性比较强。这些优势使三维扫描技术得到了广泛的应用，并且在某些特殊场合，三维测量技术还具有独特的、不可替代的作用。比如测量比较柔软的物体，用传统的接触测量方法，很可能在测量时使物体变形，从而使测量结果不准确，而三维扫描技术以光为测量媒质，不会引起物体表面的形变和损伤。
上述优势促进了三维测量技术在众多领域内的应用，它被广泛应用于汽车工业、飞机工业、机械制造、模具设计、家电等制造行业的三维复杂曲面产品的三维测量、逆向设计、产品质量检测、尺寸检验、变形分析
随着三维测量技术的不断深入发展，用离散的点云来表示物体表面特征的方式成为了学术界的新宠。人们为了表示高复杂度和高度真实感的物体和场景，采用点云作为三维模型的表示方法。在传统造型中，无论是以NURBS为代表的解析曲面还是离散曲面或三角曲面[3]，在最终实现曲面输出产生加工数据或图形显示数据时，都要将曲面离散到点。而点云是一种以物体为中心的绘制方法，其中的绘制图元为点，它是物体表面上最基本的元素，也是绘制过程的最基本单位，因此可以省去中间曲面形态直接绘制，而不需要进行扫描转换，提高了绘制速度。并且由于点云数据表示是整型，一些关键操作，如求交操作，采用异或运算，不涉及浮点运算，因而能够有效地避免计算误差引起的几何不确定性。
然而，该领域在国内，尚无成熟的、可用于工业生产的成果出现，即使在较早研究、使用该技术的国外，三维实体造型技术仍旧存在很多问题有待解决，不能完全发挥其优势。其中很突出的一个问题，就是三维点云处理过程中配准精度与速度的瓶颈无法突破。
其中ICP算法是最为常用、也是发展最为成熟的一种方法[4]，但其在速度与精度方面，还有许多不尽如人意的地方。本次毕业设计，即在这样的背景与前提之下，对三维点云处理中的配准方法进行了一定深度的研究，提出了使用新的基于4PCS的方法[1]，融合入传统的ICP法的配准办法，使之能够以较快的速度，得到满足实用要求精度的点云，使三维测量技术在生产制造中的应用又迈进了一步，具有实用价值。
2.理论意义和应用价值
（1）.理论意义：
随着现代工业制造水平的发展，及产品零件不规则复杂曲面的大量应用，在工业制造过程中需要进行大量的三维曲面实体数字化和三维测量，迫切需要快速、高效、准确、移动式的三维测量技术。而目前国内尚未有能成熟运用于工业制造的点云预处理技术，其关键技术还在进一步研究之中。而这些关键技术直接影响得到最终所需数字模型的精度、计算效率等[6]。因此，必须要对这些关键技术进行深入研究，让数字化比对技术能够真正地应用于实际，满足生产要求。点云的预处理技术就是其中很关键的一环，三维点云预处理研究将极大促进三维光学测量技术的应用。
目前，点云的预处理技术最主要还是集中在速度和精度两个方面。速度上，处理效率不高，尤其针对数据量很大的点云进行三角化和重叠面删除时计算量将成倍地增大，若提高了处理速度则有可能影响拼接精度[7]；精度上，ICP算法要求粗略拼接提供合适的初始位置，否则将造成拼接失败，此外ICP算法在求取对应点时容易夹杂错误的匹配，另外对多视点云全局匹配累积误差均化重视程度不够，从而影响整体拼接精度。这些因素都增加了点云预处理的实用化难度。提高点云预处理的速度和精度，就具有了极其重要的意义。
本次毕业设计拟通过改进点云数据的配准技术，在ICP精配准之前，先进行基于4PCS（4-Points Congruent Sets）的粗配准，这使得我们可以在不减少原始数据点、不限制待配准点云初始位置的情况下，对原始点云进行无损精度的快速配准，在精度、速度方面得到较大改善。并且，经过基于4PCS的方法配准后，所得到的点云数据可以满足后续的ICP法对于需要精配准的点云的位置要求，使精配准的效果有所改善。这对于提高点云预处理的速度和精度，都有很大的意义，为更好地推广与应用三维光学测量技术打下基础。
（2）.应用价值：
近年来，欧洲、美国、加拿大、澳大利亚、日本等国的几十家高技术公司都纷纷开展了对三维扫描技术的研究开发，并已经形成了较大规模的产业。其产品在精度、速度、易操作性等方面都达到了较高的水平。国外的许多著名企业，如通用、大众等，都逐渐开始采用对三维实体数字化、三维光学检测等先进技术，大大降低了产品开发制造成本，缩短了产品开发制造周期。然而国内的数字化技术应用几乎还是空白，点云数据处理技术还没有达到可以真正在工业生产中大量应用的程度，其中点云预处理的配准速度与精度是影响点云技术应用于实际的一个很大的瓶颈，解决这些问题的关键技术需要我们进行进一步的研究，让数字化比对技术能够真正地应用于实际，满足生产要求。
3.国内外研究现状及发展趋势
目前，国内外研究数字化比对检测技术的主要方法按照测量设备可分为：接触式和非接触式测量[8]。接触式测量主要是指通过三坐标测量机（CMM）来进行工件的测量，获得工件上重要点的三维坐标信息。对于三坐标测量机来说，它具有精度高重复性好的优点，但它同时也存在测量速度慢、对被测工件的表面材质有一定要求、不能检测比测量探针小的特征以及采集点数少等缺点，因此大大限制了其发展空间。对于非接触式光学测量设备来说，它具有测量速度快，对工件表面要求低等优点。然而用这种设备获取的工件点云数据的密度较大，因此后续的处理和计算效率成为关键因素[9]。由于三维扫描技术具有独特的优势，所以近二十多年来人们对其进行了大量的研究。
1965年，LRboert在他的论文“二维物体的机器感知”中提出了利用计算机视觉技术获取物体三维信息的可能性，这标志着三维扫描技术新纪元的开始[10]。后来，人们相继提出了一些三维扫描的方法，但是因为计算机视觉技术对电子器件、计算机性能、图象采集设备等要求很高，而当时又达不到这个条件，所以直到80年代后，随着相关技术的发展，三维扫描技术才逐渐形成产业化。
通过三维光学测量系统从现实实体模型中构造出可用于计算机处理的三维几何模型并不是一个简单的问题。三维点云预处理作为其中一个重要环节，存在很多细节值得深入研究和探讨。在计算机图形学（如Siggraph国际会议）、计算机视觉（如ICCV国际会议）、几何处理（如SGP国际会议）、虚拟现实和逆向工程等学科中都有不少研究文献在讨论这个问题，已经成为这些学科的研究热点之一。鉴于点云数据预处理的重要性，长期以来，人们对它进行了大量的研究。
（1）国外发展现状
在国际三维光学扫描领域，点云预处理技术最有代表性的应用是在德国GOM公司的基于结构光的Atos光学扫描系统中得到了应用。Atos光学扫描系统最大优势在于对工件多次扫描后能够快速得到三维实体高精度的单层点云数据。另外，GOM公司还和美国专业逆向软件公司RainDorp(雨滴)合作开发专用的点云处理软件。
从拼接的过程来说，点云的拼接一般分为粗略拼接和精确拼接两步[11]，粗略拼接是为了缩小点云之间的旋转和平移错位以提高精确拼接的效率和趋向，精确拼接则是为了使拼接误差达到最小。精确拼接从变换方式来说，又可分为基于刚性变换的拼接和基于非刚性的拼接两大类。在精确拼接的研究上，最为经典的是ICP算法，其中相关的理论很多[12]。Besl和Chen提出的ICP算法是基于刚性拼接的经典算法，在业界有比较广泛的应用。
传统ICP算法的效率不高，从它被提出至今，国内外研究者一直都在为改进ICP算法而努力。Blais等结合了逆向定标法和随机搜寻法来提高速度，但对拼接精度产生了一定的影响[13]；Li等提出了一种ICL(Iterative Closest Line)算法，通过直接对两个点云中的点连线并寻找对应线段进行拼接，但存在无法保证线段之间对应关系的问题；Devrim Akca等提出将三维数据进行空间网格划分，空间点就落入相应的网格中，从而加速ICP算法中对应点的查找，但是这种方法在采样不均匀的情况下，速度会大大降低；Gelfand提出了一种基于稳定采样的ICP算法，即只有那些被认为是非常有代表性的点才会被用来进行ICP迭代，这样保证了ICP算法的有效性。
如果ICP算法拼接过程中针对的不仅仅是两副点云，而是在综合考虑多副点云的基础上，使得总体拼接误差最小，消除了累计误差的不利影响，那么它就称为全局拼接(Global Registration)。Pulli首先选取一组稳定的全局特征点对，然后利用这组特征点对迭代地ICP将每幅点云拼接到其它所有的点云中，直到最终收敛为止[14]；Gregory等提出在全局拼接封闭环中分配误差的方法来进行全局拼接；Lu提出了一个对多幅点云同时求解最佳刚性ICP变换的全局拼接算法。另外，在对基于刚性变换的ICP算法进行改进的工作中，一些学者还专注于研究点云的初始拼接、距离的定义、对应点的查找、错误点对的剔除以及目标函数的加权等几个方面。