基于Hausdorff距离改进的ICP算法

郑晓璐，潘广贞，杨 剑，杨小青

（中北大学 计算机与控制工程学院，山西 太原030051）

0 引 言

为了得到被测物体的完整数据模型，需要对多次测量的数据进行一个合适的坐标变换，将不同视角的点云数据变换到统一的坐标系内进行可视化操作，这就是点云的配准［1－4］。

Besl等提出了一种基于自由形态曲面的高层次配准方法［5］，即 为 经 典 的 迭 代 最 近 点 （iterative closest point，ICP）算法。首先根据一定的准则确立对应点集P与Q，其中对应点对的个数为n。然后通过最小二乘法迭代计算最优的坐标变换，即旋转矩阵和平移矢量t，使得误差函数最小；随后DAI提出了一种使用曲率特征点和K－D 树寻找最近点的方法［6］。然而该些算法对点云没有进行预处理。之后国内外的许多学者对ICP进行了不同程度的研究和改进。随着三维扫描设备精度的提高，数据规模和配准精度也在提高，经典的ICP算法不能满足实时性的需求，因此本文在对各种ICP算法进行研究后，提出了一种基于Hausdorff距离处理点云的ICP 算法。在获得大量点云数据后，以数据点主曲率和Hausdorff距离［7］为依据，利用正态分布图将点云分为关键点和非关键点，关键点充分保留了点云的几何特征，用来进行配准，而非关键点作为几何特征不明显的点，为提高算法效率不予以配准。采用K－D 树［8］加速查找，利用最小二乘迭代计算最优的坐标变换，完成点云的配准。数据规模巨大的点云配准精度问题由此得到解决。

1 点云预处理

1.1 曲率计算

点云的曲率［9］是描述点云曲面几何特征的主要数学手段，曲率是在连续且二阶可导的曲面上定义的，没有拓扑结构，因此离散的三维点云不能直接计算曲率。在局部坐标系内拟合一张连续曲面来计算各点的曲率，常用到的曲率分别有高斯曲率、平均曲率和主曲率。

设（d）＝du：dv 为曲面S：r＝r（u：v）在P 点处的主方向，沿主方向的主曲率为Kn，则Kn满足

即Kn是二次方程的根，也就是方程K2n－2 HKn＋K ＝0的根

则曲面S 的高斯曲率为

则曲面S 的平均曲率为

则主曲率

1.2 关键点选取

Hausdorff距离［10］是研究分形空间的一个重要的基本概念，是描述两组点集之间相似程度的一种度量，它是两个点集之间距离的一种定义形式：假设有两组集合A ＝｛a1，a2，…ap｝，B ＝｛b1，b2，…bq｝，则A，B 两点集之间Hausdorff距离定义为

其中，d（A，B）和d（B，A）分别表示集合A 到集合B 和集合B 到集合A 的单向Hausdorff距离，分别定义如下

其中， · 表示某种距离范数。

通过计算点与其邻域之内点之间Hausdorff距离作为依据，将点集P 分为关键点P′和非关键点P″（P′∪P″＝P且P′∩P″＝Φ）。关键点P′指几何特征比较明显，对点云配准起至关重要的点。非关键点P″指几何特征不明显，配准时可以忽略的点。对于任意点M 和它的邻近点N ，其主曲率分别为k1，k2和。点M 和N 之间的曲率差别可以看作是｛k1，k2｝和｛｝之间的差别。我们可以通过一个相对度量H 来衡量Hausdorff距离

当分母接近0时，误差较大。于是，我们引进临界值ε。当 ki＋＜ε 时， ki＋应该转换为，用来防止误差较大。

M 点的Hausdorff距离可定义为：HM＝max（H1，H2，H3，…，Hk）。其中：H1，H2，H3，…Hk为点M 与其邻域内k个邻近点的Hausdorff距离值。HM可以反映出M 点曲率的变化情况，对曲率变化大的区域保留足够多的特征点，用来突出模型的曲面特征，而在曲率变化小的区域保留少量的点，所有保留的点即为关键点。即当HM较大时，M 处的几何特征比较明显。我们采用HM值的正态分布图来获取点云的关键点。因为正态分布是自然界中一种常见的分布，存在于自然现象、生产、生活及科学技术等领域，我们绘制出点集P 的H 值正态分布图，模型大致如图1所示，横坐标是HM，纵坐标是在值为HM的点云个数n，在正态分布图中找到值H0使得小于H0的点 （图中阴影部分）占点总数的20%，即为非关键点，剩余80%为关键点 （经实验验证，28比例的划分效果比较理想）。关键点非关键点的划分使我们对点集P 进行了预处理，找出了集合特征明显的特征点。然后对几何特征明显的点进行配准，一方面节省了时间，另一方面使配准更具有针对性。我们在接下来的ICP配准时利用的就是这些几何特征明显的关键点，用来调高配准的精确度。

图1 点云正态分布

点集预处理算法流程说明如下：

步骤1 计算出集合P 中所有点的主曲率，利用式（5）计算。

步骤2 计算每个点及其邻域点的Hausdorff距离，并取最大值为该点的Hausdorff值，利用式 （8）计算。

步骤3 将集合P 中所有点的Hausdorff值进行统计，并绘制出HM正态分布图。

步骤4 根据上文介绍的分类方法，利用正态分布图H 值的分布情况将点云分为关键点P′和非关键点P″。

步骤5 完成点云的预处理。

2 改进的ICP算法

对两个三维点集P′和Q 进行ICP配准，步骤如下：

步骤1 利用k－d tree寻找P′中每一个点在Q 点集中对应的最近点。

步骤2 求得上述对应点对平均距离最小的刚体变换，即旋转变换向量qR和平移变换向量qT以及误差。

步骤3 对于P′使用上步求得的变换向量得到新的变换点集。

步骤4 当新的变换点集与参考点集Q 满足式 （9）的目标函数时，停止计算。否则跳转到步骤2 一直迭代，直到达到目标函数的要求。

步骤5 完成点云的配准。

本文采用了基于Hausdorff距离改进的ICP 算法，目的在于解决ICP算法的高精度要求。利用曲率能表示邻域形状变化的特性，引入Hausdorff距离的点集定义，对点云进行预处理，使得点云的配准更具有针对性。高精确度的优势使得该算法可应用于海量数据的逆向工程，本文的算法流程如图2所示。

图2 本文算法流程

3 实验结果与分析

为了验证本文算法的正确性和有效性，以经典算法作为对比，对三维模型进行了仿真实验。本文实验的硬件环境为Intel Xeon 的处理器，6.00G 内存的64位的win7操作系统。软件环境为PCL 点云库、Visual Studio2010、cmake3.0、华硕Xtion Pro Live。实验数据均取自PCL官网提供的pcd格式文件。

3.1 配准结果

点云bunny的点数分别为20480、18566，下面分别给出了经典ICP算法和本文ICP 算法的配准结果。图3 （a）为两片未配准的点云，浅灰色为源点云，深灰色为目标点云。图3 （b）为经典ICP算法的配准图。图3 （c）为本文改进的ICP算法的配准图。图4为经过30次迭代计算后的自由刚体变换。对比图3 （b）和图3 （c），图3 （c）中 浅灰部分深灰部分距离小于图3 （b）对应浅灰深灰点云之间的距离，可以得出图3 （c）的配准精度得到进一步提高。

图3 bunny实验配准

图4 bunny最优刚体变换

点云robot的点数分别为20991、19352，下面图分别给出了经典ICP算法和本文ICP算法的配准结果。图5 （a）为两片未配准的点云，图5 （b）为经典ICP算法的配准图。图5 （c）为本文改进的ICP算法的配准图。图6为经过30次迭代计算后的自由刚体变换。对比图5 （b）和图5 （c），图5 （c）中浅灰部分深灰部分距离小于图5 （b）对应浅灰深灰点云之间的距离，可以得出图5 （c）的配准精度有了很大的提高。

3.2 结果分析

图5 robot实验配准

图6 robot最优刚体变换

实验的配准精度我们可以用配准误差来衡量。表1列出了经典ICP算法和本文改进算法的时间和精度，分别对bunny、robot、horse、dragon进行了实验。从表数据分析来看，bunny在时间上由3.842s缩短到了2.957s，配准精度由0.3929mm 提高到了0.1604 mm。我们可以得出，在配准时间几乎相近的情况下利用基于Hausdorff距离的改进算法能有效的找出均匀的关键点，实验精度有了很大的提高，取得了令人满意的效果。

表1 点云配准比较

由图7可以看出本文改进算法的配准误差明显低于经典算法，并且随着数据量的增大配准误差越低。改进算法配准在精度上有明显的优势，并且随着数据量的增大配准精度的优势越明显。因此该配准算法可以应用在对配准精度要求较高，点云凹凸性较明显的物体上。

4 结束语

图7 改进算法与经典算法的配准误差比较

本文在研究了各种ICP 算法后，针对点云数据量大、对配准精度要求较高的情况，提出了一种基于Hausdorff距离改进的算法。采用三维点云拟合曲面的主曲率和点邻域内Hausdorff距离相结合的方法，利用正态分布图选择出点云几何特征明显的关键点。然后采用K－D 树加速查找，通过最小二乘迭代进行点云ICP 配准。实验结果表明，本文提出的算法提高了点云配准的精确度。在实际应用中，本算法适合对配准精度要求较高，点云凹凸性比较明显的物体配准上。

［1］DUN WZ，HUN G，HONG LX，et al.The research of optical 3D measuring precision influencing factor in reverse engineering ［J］.Applied Mechanics and Materials，2010，33：157－162.

［2］Hacene A，Mekki A.Bio－CAD reverse engineering of freeform surfaces by planar contours［J］.Computer－Aided Design＆Applications，2011，8 （1）：37－42.

［3］XU Gang，WANG Chunyan.Based on vitural reality modeling language medical volume data reconstruction ［J］.Automation and Instrumentation，2012 （4）：38－40 （in Chinese）. ［徐刚，王春燕.基于虚拟现实建模语言的医学体数据三维重建研究［J］.自动化与仪器仪表，2012 （4）：38－40.］

［4］Karen RS，Alexandra SC.Reliability of photogrammetry in the evaluation of postural aspect of individuals with structural scoliosis［J］.Journal of Bodywork and Movement Therapies，2011，16 （2）：210－216.

［5］LI Shifei，WANG Ping，SHEN Zhenkang.A survey of iterative closest point algorithm ［J］.Signal Processing，2009，25（10）：1582－1588 （in Chinese）.［李世飞，王平，沈振康.迭代最近点算法研究进展 ［J］.信号处理，2009，25 （10）：1582－1588.］

［6］YANG Xianhui，WANG Huinan.Application research of ICP algorithm in 3Dpoint cloud alignment［J］.Computer Simulation，2010，27 （8）：235－288 （in Chinese）. ［杨现辉，王惠南.ICP算法在3D点云配准中的应用研究 ［J］.计算机仿真，2010，27 （8）：235－288.］

［7］ZHU Yu，KANG Baosheng，LI Hong’an，et al.An improved method to streamline point cloud ［J］.Computer Application，2012，32 （2）：521－524 （in Chinese）. ［朱煜，康宝生，李洪安，等.一种改进的点云精简方法 ［J］.计算机应用，2012，32 （2）：521－524.］

［8］YU Xiaogao，YU Xiaopeng.Based on angular similarity K－nearest neighbor search algorithm ［J］.Application Research of Computers，2009，26 （9）：239－256 （in Chinese）. ［余小高，余小鹏.一种基于角相似性的K－最近邻搜索算法 ［J］.计算机应用研究，2009，26 （9）：239－256.］

［9］Bu Yanlong，Peng Shuangchun，Wangnan，et al.Constriction of mutual information based matching－suitable features for SAR image aided navigation ［C］／／International Conference on Environmental Science and Information Application Technology，2009.

［10］BAI Yanbing.Free－form surfaces Haudorff diatance approximation calculation to freedom of curves and surfaces［D］.Beijing：Tsinghua University，2011 （in Chinese）.［白彦冰.自由曲面到自由曲线曲面的Hausdorff距离近似值的计算 ［D］.北京：清华大学，2011.］