贺永兴，欧新良，2

(1.湖南工业大学计算机与通信学院，湖南 株洲 412008;2.长沙大学计算机科学与技术系，湖南 长沙 410003)

昆虫点云配准方法综述*

贺永兴1，欧新良1，2

(1.湖南工业大学计算机与通信学院，湖南 株洲 412008;2.长沙大学计算机科学与技术系，湖南 长沙 410003)

综述了点云数据的配准方法和相关算法，并对这些配准算法的基本思想加以分析比较，分析了昆虫外形点云的特点及应用领域，对昆虫点云配准技术的发展动态作了介绍，并对未来研究作了展望.

昆虫点云;配准;ICP算法

仿生学是研究模拟生物系统或使人造技术系统具有类似于生物系统功能的科学.由于昆虫具有惊人的环境适应能力，分布极广，并且结构和功能各异，所以昆虫是仿生学研究的主要生物来源.对昆虫外形的仿生学研究具有重要的现实意义，比如对臭蜣螂唇基外形的三维建模有助于切土减能的研究，对蜻蜓翅膀外形的三维建模将有助于直升飞机机翼的研制.其次，昆虫千姿百态的外表和令人惊奇的动作，是三维动画制作的素材宝库.还有，仿生建筑也需要昆虫外形的三维数据模型，昆虫的体型和外表往往能够激发建筑设计师的灵感.

我们要通过建立昆虫外形的模型来研究其外形对生存模式的作用和影响，首先就要利用三维激光扫描设备采集昆虫表面的点云，其次对数据进行预处理，预处理的过程包括点云的配准、去噪、精简、划分、光顺等，其中，点云配准是预处理过程中最重要的一步.

1 点云数据配准的定义

为了对被测物体进行三维重建，我们首先需要获得三维物体表面的真实数据.但是，由于受到测量设备和环境等因素的限制和影响，使得每次测量得到的点云数据只是实体表面的一部分，并且可能出现平移错位和旋转错位，所以我们若要获得物体表面完整的测量数据，就必须对物体进行多次不同角度、不同位置的测量，并将从各个视角得到的点集合并到一个统一的坐标系下，形成一个完整的数据点云，然后才可以方便地进行可视化等操作，这就是点云数据的配准.

点云数据配准在数学上的描述为∶设用{pi|pi∈R3，i=1，2，…，N} 表示第一个点集，用 {qi|qi∈R3，i=1，2，…，M}表示第二个点集，找出两个点集的空间变换，使两个点集中的相同点进行匹配，两个点集的对齐变换是应用最小二乘法使下列目标函数为最小∶min.其中pi'表示在{qi}中找到与{pi}匹配的对应点，使两者离差平方和为最小.

2 点云数据配准的方法

点云数据配准有手动配准、依赖仪器的配准和自动配准.值得注意的是，由于各种因素的影响，采用三维激光扫描获取得到的点云数据，无法避免地在真实数据点中混有不合理的噪声点，其结果将直接影响计算精度，因此在进行数据点集配准之前，需要进行必要的噪声点处理和数据压缩处理.关于数据的噪声点处理和数据压缩处理，可参看文献［1，2］，这里就不再展开讨论.下面就各种点云数据配准方法进行简要的介绍和分析.

2.1 手动配准方法

目前，对点云数据配准的手动方法主要是在测量阶段对数据进行标记，也就是说在被测物体上贴标签，标签一般应贴在相对较平坦的区域或者标定平板上，然后用扫描仪对模型进行旋转扫描，根据前后两个视角观察的三个或三个以上不共线的公共标签来对数据进行配准，从而得到一组特殊的点云，相邻点云之间只存在角度差异.因此，配准时只存在一个配准参数，这种配准方法比较高效，即使不用迭代法也能取得很好的配准效果，但缺点是物体底部和下部的数据点是无法采集的，并且需要相应的硬件支持.

2.2 依赖仪器的配准方法

目前，依赖仪器的配准方法主要是采用激光扫描仪和自动旋转台相互配合的测量方法［3］，利用旋转台控制被测物体绕旋转台中心轴线按规定的旋转角度旋转，工作台每旋转一个位置，激光扫描仪则从不同视角采集一次被测物体的点云数据，从而可实现多视角点云自动旋转对齐，对齐精度取决于旋转台中心轴线与旋转角度的精确度.还有一种可行的方法是固定测量物体，通过关节臂式扫描系统机械手臂的空间运动来记录测量头的空间位置变换.

2.3 自动配准方法

自动配准方法是通过一定的算法或者统计学规律，利用计算机消除两片点云之间的误差和错位，从而达到把两片点云自动配准的效果，通常意义上的点云配准技术即是自动配准技术.点云数据配准的实质是把在不同的坐标系中测量得到的数据点云进行坐标变换，以得到统一坐标系下的整体数据模型.问题的关键是如何求得坐标变换参数R(旋转矩阵)和参数T(平移向量)，使得两视角下测得的三维数据经坐标变换后的距离最小.

目前采用的自动配准技术包括初始配准(粗配准)和精确配准两步.第一步∶初始配准，它的意义在于缩小点云间平移误差和旋转误差，给精确配准提供良好的初值，以此提高配准效率和趋势.第二步∶精确配准，它使点云之间的配准误差达到最小.在点云数据初始配准和精确配准过程中，运用最广泛的算法大致可分为三类∶迭代配准算法、基于曲面的配准算法和基于几何特征的配准算法，下面对这三类算法加以分析和比较.

2.3.1 迭代配准算法

迭代配准算法，即最近点迭代(Iterative ClosestPoint，ICP)算法［4］，1992 年，由Besl和Mckay等提出.ICP 算法主要用于解决基于自由形态曲面的配准问题，它是当前点云数据配准过程中应用最广泛的算法.该算法以四元数配准算法为基础，首先利用牛顿迭代或者搜索方法寻找两组点云对应的最近点对，然后采用欧氏距离作为目标函数进行迭代，从而得到三维的刚体变换.迭代算法虽然精确度很高，但存在很多局限∶首先是ICP算法对两组点云相对的初始位置要求比较高，点云之间初始位置不能相差太大，并且要求两个匹配点集中的一个点集是另外一个点集的子集;其次是ICP算法在求解邻近点对集的过程中采用的是全局搜索，所以配准过程会因为迭代次数太多而导致时间复杂性增加.当位置条件不满足，或相差太大时，我们将无法确定收敛方向，进而影响ICP算法的收敛结果，甚至还有可能陷入局部最优解，使得配准变得不可靠甚至是错误的.所以，在迭代过程中确立正确的对应点集，是避免迭代陷入局部极值的关键，它直接决定了算法的收敛速度与最终的配准精度［5］.鉴于ICP算法在确立对应关系时一般需进行大量耗时的搜索工作，国内外学者亦提出一些加速算法(如使用k－d tree)来提高ICP算法的效率.

2.3.2 基于曲面的配准算法

在无法预知点云数据间的相互关系时，迭代算法的有效性得到了质疑，这时基于曲面描述的配准算法［6］就显示了其优越性.Chen 和 Medioni［7］两位学者在 Besl和 Mckay 的经典ICP算法的基础上进行了改进，运用两个测点曲面在法矢方向的距离来代替某一点到其最近点的距离，并将其作为匹配的目标评价函数，但是要求解一个非线性最小二乘问题，所以速度较慢.这种方法的好处是一开始就可以使迭代误差很快地减小，也就是快速地收敛，但是因为它用切平面来代替真正的曲面，也就是忽略了目标函数中的二次项信息，导致有时候迭代不收敛，尤其当目标物体表面曲率变化明显时.事实上，这种方法是一种Gauss－Newton法，它不保证收敛，但是一旦收敛，其速度会比较快，是二次收敛.

2.3.3 基于几何特征的配准算法

为了有效地解决不存在明确对应关系的点云配准问题，提出了一种基于点云几何特征的配准算法.因为曲率能够表示测点的局部邻域形状变化，具有平移、旋转和缩放不变性，所以可以作为曲面特征识别的重要依据.该算法首先以点云的曲率为联系特征，搜索配准点云的匹配对集合;然后利用邻域特征对各匹配对进行相似性度量，提取有效配准点对，并引入刚体变换中向量几何性质剔除其错配对，生成点云初变换;最后采用ICP算法对点云初配结果进行优化，实现点云精确配准.

朱延娟等［8］根据测点及其邻域点估算每个点的曲面法矢来计算各个测点的曲率，由每个测点的曲率来识别两组点云数据中可以匹配的点对集合，进而进行精确配准，虽然保证了算法的配准精度，但执行中需要进行大量的搜索查找，并且存在多个相似点对，容易增加算法的复杂度.

事实上，基于曲面描述的配准算法和基于几何特征的配准算法可以看作是同一种方法，即基于特征的配准算法，这种方法配准效率较高，并且对于如局部重叠的点云数据，适用性较好.

3 昆虫点云数据的配准方法分析

3.1 昆虫外形点云特点

昆虫外形点云的特点，主要包括昆虫形状特征、体型规格、点云规模等.通常情况下，不同的昆虫可能有完全不同的外形结构，比如有无角突、齿突、脊梁、毛刺、褶皱、鞘翅等，我们可以根据实际的应用来有针对性地研究其外形结构.昆虫的体型尺寸一般不会超过数厘米，小到0.02厘米，因此对它们的三维扫描有一定困难，目前最好的三维激光扫描仪测量精度达到0.01毫米，最好的三维激光扫描显微镜测距精度达到0.01微米，因此昆虫外形点云处理有特殊性，要有一个放大的过程，以便于人眼观察.但是放大后，有一个细节失真的问题要解决.若研究对象是体型较大的昆虫，尺寸在0.1厘米到10厘米范围内，比如蚂蚁、臭蜣螂、蜻蜓等，图形显示本身可以放大几倍到几十倍或几百倍之间，虽然细节失真的问题仍然存在，但对整体点云数据的配准影响不大.

3.2 昆虫点云数据的配准

对采集得到的昆虫点云数据进行配准，我们通常采用基于几何特征的配准方法，由于曲率能够表示测点的局部邻域形状变化，具有平移、旋转和缩放不变性，所以可以作为昆虫曲面特征识别的重要依据.

通常情况下，昆虫外形结构特征异常复杂，昆虫外表面曲率变化剧烈，需要进行多角度多次扫描以减少扫描盲区和死角，以此来获得更多数据信息.有关昆虫点云曲率的估算也必须要适应这种情况，一般的曲率估算误差较大，而昆虫外形显示需要放大，这导致曲率的估算误差也可能放大.为了在重建显示过程中保持昆虫外表形状的几何特征不变，则需要找到更好的曲率估算方法.目前所有点云曲率估算方法的误差都受到点云密度的较大影响，即∶点云密度越大，估算越准确，反之不然.而昆虫点云由于昆虫体型的原因，不可能过高地追求点云密度，因为这会导致对扫描仪精度要求的提高.当前主流扫描仪的精度也是有限的，所以我们只能在曲率估算方法上寻求突破.当今，点云曲率估算方法已经较为成熟，再要提高估算精度似乎有较大的困难，但是由于昆虫外形点云的特殊性，不增加曲率估算精确度，就无法刻画昆虫外形的结构特征.所以，如何在已有点云数据的基础上提高曲率估算精度是摆在众多科研学者面前的一道难题.

有国内学者提出一种从经典的曲率估算公式入手，采用几何的途径提高曲率估算精度的方法，目前的估算方法都是近似的办法，这说明有改进的空间.自由曲面上的微分算子，都是逼近运算的极限值，理论上是可以得到精确解的，但是在具体计算时又是取其逼近值(数值解)，受自由曲面高斯曲率计算公式［9］的启发，离散高斯曲率估算公式所依托的多面体在空间与原型上可以进一步逼近，因此在二者之间进行三维空间插值逼近是有可能的.之前点云配准时所使用的拟合曲面法是基于已有的离散点，在其某个邻域内建立拟合曲面，计算其高斯曲率和其它微分量，而它的精度主要受点云密度和邻域半径的影响，并且计算量比较大.不同于拟合曲面法，若首先建立空间插值模型，在相同已知相邻点数的情况下，置入插值点，设置调节参数，通过实验来获取其逼近精度与调节参数的关系，从而寻找最优阈值，那么，高斯曲率估算的精度将大大提高.

4 研究展望

点云数据配准技术，尤其是昆虫点云数据配准技术是实现逆向工程和仿生工程的关键技术，目前它仍处在发展阶段，有许多问题有待进一步地研究和解决.下述几个方面仍然是今后研究的热点和难点，迫切需要引起研究人员的关注∶

(1)虽然ICP算法以其简便、高效及良好的精度与稳定性成为了精确配准领域的基本算法，但是它大多只能适用于一些特殊场合，比如必须要求待配准点云相对初始位置较近或者具有包含关系.除此之外，在其他场合其性能一般无法令人满意，故提出一种具有普遍适用性并且具有良好可靠性与鲁棒性的ICP算法将是今后研究的重点和难点.

(2)其次是ICP算法在求解邻近点对集的过程中采用的是全局搜索方法，在执行中需要进行大量的搜索查找，并且很容易找到相似的对应点对而重复操作，这直接导致配准过程因迭代次数太多而使时间复杂度大增.所以，需要找到一种快速确立对应点集并过滤错误点集的方法，以此来降低时间复杂度，提高配准效率.

(3)对于昆虫点云数据的配准，尽管基于几何特征的配准方法较为实用，但是由于昆虫外形结构的特殊性以及三维扫描设备精度的限制，根据测点及其邻域点来估算每个点的曲率时，往往存在着较大的估算误差，所以，一般的曲率求解方法不适合于昆虫点云.找到适合昆虫点云数据特性的曲率求解方法将是配准成功的关键.同时，尽可能地降低曲率估算的误差也直接关系到最终配准的精度，故如何快速正确求解昆虫点云数据的曲率将是今后研究的重点和难点.

(4)此外，当昆虫的尺寸小于0.1厘米或者更小时，如何解决昆虫点云数据放大后的细节失真问题，如何求得相关的点云几何特征，进而有效地配准点云将是以后研究的重点和难点.

5 结语

本文对点云数据的一般配准方法和针对昆虫点云数据的配准方法进行了论述.首先总结分析了点云数据配准的主要方法，其次对比较有代表性的配准方法及算法进行了具体的分析和对比，最后阐述了适合昆虫点云配准的方法和研究现状.目前，对配准算法的研究仍然集中在算法的速度、精度、稳定性、收敛性和可靠性等方面，如何改进算法，如何快速配准昆虫点云数据，将是今后的研究重点.

［1］李剑.基于激光测量的自由曲面数字制造基础技术研究［D］.杭州:浙江大学博士学位论文，2001.

［2］吴敏，周来水，王占东，等.测量点云数据的多视拼合技术研究［J］.南京航空航天大学学报，2003，(5):552 －557.

［3］ Vàrady T ，Martin R R，Cox J.Reverse engineering of geometric models——an introduction［J］.Computer Aided Design，1997，29(4):255－268.

［4］Besl P J，McKay N D.A method for registration of 3D shapes［J］.IEEE Transactions on Pattern Analysis Machine Intelligence，1992，14(2):239－256.

［5］Gregory C，Sang W，David K.ICP Registration using invariant features［J］.IEEE Transactions on Pattern Analysis Machine Intelligence，2002，24(1):90 －102.

［6］Chua C S，Jarvis R.Point signatures:A new representation for 3D object recognition［J］.International Journal of Computer Vision，1997，25(1):63 －85.

［7］Chen Y，Medioni G.Object modeling by registration of multiple range images［J］.Image and Vision Computing，1992，10(3):145 －155.

［8］朱延娟，周来水，张丽艳.散乱点云数据配准算法［J］.计算机辅助设计与图形学学报，2006，18(4):475－481.

［9］欧新良，陈松乔，方逵.基于高斯映射下自由曲面的形状分析及边界计算［J］.小型微型计算机系统，2006，(4):735－740.

(责任编校:晴川)

TP391

A

1008－4681(2011)05－0055－03

2011－04－26

湖南省教育厅科技重点项目(批准号∶09A010).

贺永兴(1984－)，男，湖南株洲人，湖南工业大学计算机与通信学院硕士生.研究方向∶计算机图形学.