基于距离哈希的稀疏点集快速匹配算法研究

摘 要：针对不同坐标系下部分重叠的稀疏坐标点集，提出一种基于距离哈希的同名点快速稳健匹配算法。将各点与其邻近点的距离关系映射成一个二进制码身份标签，通过身份标签相似度计算，找出两个点集中满足设定阈值的候选匹配点对，从而建立初始匹配关系。据此计算刚体变换矩阵对两组点集进行配准，确定两组点集之间的精确匹配关系。实验结果表明：该算法不仅速度快、准确率高、对于噪点和低重叠度具有稳健性，而且对两个点集之间的初始相对位置没有任何限制。

关键词：机器视觉；稀疏点集；点集匹配；距离哈希；二进制码

中图分类号：TP391.7 文献标志码：B 文章编号：1671-5276（2024）04-0169-04

Research on Sparse Point Set Fast Matching Algorithm Based on Distance Hash

WU Linpeng，ZHOU Ling，YANG Han，ZHAO Jiayi，ZHANG Liyan

（Nanjing University of Aeronautics and Astronautics，Nanjing 210016， China）

Abstract：Based on distance hash， proposes a fast and robust matching algorithm with homonymous points for partially overlapping sparse coordinate point tsets in different coordinate systems. A binary code identity tag is mapped according to the distance relationship between each point and its adjacent points. Through the similarity calculation of identity tags， the corresponding similar point pairs meeting the set threshold in two point sets are found to establish the initial matching， based on which， the rigid body transformation matrix is calculated to register the two point sets， and the precise matching between the two point sets is defined. The experiment results show that the proposed algorithm is fast， accurate， robust to noises and low overlapping， and hasno restriction on the initial relative position between two point sets.

Keywords：machine vision；sparse point sets；point sets matching；distance hash；binary code

0 引言

点云配准技术是针对激光扫描仪、结构光测量系统等设备所获得的同一物体在不同视角下的海量点云数据进行合并的技术。最经典的点云配准算法是由BESL等^[1]提出的最近点迭代算法（iterative closest point， ICP），通过反复迭代寻找最佳同名匹配点对，以估计变换矩阵。但算法的运行速度和收敛性很大程度取决于点云的初始位姿，目标函数还易陷入局部最优的情况，故需要粗配准^[2-3]为其提供初始位姿，常作为二次精配准使用。

一种影响广泛的经典粗配准方法基于全等4点集（4-points congruent sets，4PCS）^[4]，通过在目标点云和源点云之间寻找具有相同拓扑结构的4点对，来计算两个点集之间的变换矩阵，对噪声、遮挡和异常值具有较高的鲁棒性，4PCS算法的主要问题在于比较慢，提取相似集和验证变换都比较耗时。Super 4PCS^[5]、volumetric 4PCS^[6]、voxel 4PCS^[[7]等方法都致力于提高4PCS的速度，但对于工业应用仍然配准精度较低，配准速度也难以满足一些较复杂应用的要求。

基于哈希的文件检索方法^[8]是近年来广受关注的在海量数据中寻找相似文档的方法。它的基本思想是通过找到一个合适的哈希函数，将数据库中的每个项目映射为一个简单的二进制代码，并且使得相似的项目具有相似的二进制代码。受上述基于哈希方法的二进制编码在相似性匹配和检索中成功应用的启发，本文针对部分重叠的稀疏点集的同名点匹配问题，提出一种基于距离哈希的二进制编码的快速稳健匹配方法。

1 基于哈希的稀疏点云匹配算法

给定同一物体从任意两个不同角度获得的三维点集P和Q，若存在匹配点对集合C{p_i，q_j（i=1，2，…，m，j=1，2，…，n），其中∀p_i P，q_j Q，T（p_i）－q_j≤δ都成立，δ为较小常数，T为点集P和Q之间的刚性变换。则当集合C含有元素数量最多时，两个点集之间的刚性变换为最佳刚性变换T_best，此时记C=C_max为最大匹配公共集。最大公共集（largest common pointset，LCP）问题^[9]就是通过不断比较元素寻求C_max，从而获得两个点集之间的最佳刚性变换。LCP是点集配准技术要达到的目标，也是衡量配准质量的一个标准。

1.1 距离哈希编码

对点集P中任一点p_i，可以借助k-d树^[10]快速为其查找自身所在点集中的K个邻近点p_ik（k=1，2，…，K），随后将点p_i与p_ik之间的欧氏距离转化为二进制身份码，如图1所示。为了更清楚地展示编码过程，图1中仅显示p_i的6个邻近点。

在对两个点集P和Q中的点进行二进制编码时，首先会设立一个长度为l的固定步长，将欧氏距离转化为步数S。在点p_i与其K个邻近点p_ik的距离中，d_max为最大距离。对d_max/l向上取整作为该身份码的长度S，即

S=ceil（d_max/l）（1）

根据S和l为p_i建立一个二进制位数组I_D，pi，该数组含二进制位个数为S，每一位初始值为0。邻近点中p_ik与p_i之间的欧氏距离为d_ik，转化成步数s_ik为

s_ik=ceil（d_ik/l）（2）

若二进制位数组I_D，pi的第s_ik位为1，则等价于p_i在步数为s_ik的位置存在一个邻近点。将每个邻近点映射到p_i的二进制数组上，则点p_i与其K个最邻近点之间的距离特征被转换为二进制码I_D，pi，定义I_D，pi为点p_i的二进制身份标签。

1.2 相似度比较

通过上一节距离哈希算法，将点集P和Q中的数据点与其临近点之间的距离关系映射为二进制身份编码，从而使得点集中任一点都具有一个二进制码身份标签。该身份标签在保留原点集各点与其邻近点之间距离特征的同时大大简化了数据的存储。在完成两个点集中所有数据的二进制身份编码后，将点集P中数据的身份标签与点集Q中数据的身份标签逐一进行对比，即对二进制码I_D，pi（i=1，2，…，m）和I_D，qj（j=1，2，…，n）进行按位“与”运算，将其结果记为r=I_D，piamp;I_D，qj，计算r中二进制位值为1的总位数N_r，则两点之间的相似度M为

M=2N_r/（N_pi+N_qj）（3）

式中N_pi和N_qj分别为I_D，pi和I_D，qj中二进制位值为1的总位数。在点集Q中循环，求出使M最大的序号J，并记最大相似度M=M_max，若M_max的值大于设定阈值β，则可认为p_i和q_J是一对候选匹配点对。经过上述相似度计算和比较后，可获得点集P和Q之间的初始匹配点对集合C_f。

1.3 基于最邻近点的精确匹配

在初始匹配点对集合C_f内，点对之间可能存在误匹配的情况，而其中相似度较大的一些点往往是正确的匹配点对。因此，本文在集合C_f中，取相似度最大的L个点对计算初始刚体变换T_f（R_f，t_f），将点集P中的各点转换至Q所在的坐标系下，即做变换：

p^f_i=R_fp_i+t_f（4）

经过变换后的点集P和Q中的匹配点对应该具有相近的位置，对应点间距离应在三维测量产生的误差范围内。为此，通过查找最邻近点的方法来进行更精确的匹配。在点集Q所形成的k-d树中搜索p^f_i的最邻近点q_rst，当最邻近点p^f_i与q_rst的距离小于两组点云的测量误差之和时，则认为p_i和q_j是一对正确的匹配点。最终获得精确匹配点对集合C_max。在集合C_max基础上通过奇异值分解算法（singular value decomposition， SVD），即可求解P和Q之间的刚体变换矩阵，进而完成点集之间的配准。

2 实验结果与分析

为验证本文算法效果，以工业中常见且具有不同表面特征的直升机和汽车为例进行测试，所采用实验数据为自主研发的工业近景摄影测量软件所获得的直升机尾部和汽车的特征点集数据。

图2显示了对直升机尾部数据进行匹配及配准的结果。图2（a）中，P为直升机尾部测量数据，Q为直升机尾部数据的一部分，与P之间存在旋转角度为45°，平移为{1 000， 2 000， 0}的刚体变换，并添加均值为0、方差为0.2的高斯白噪声，P和Q含数据点个数分别为1 220和190。图2（b）为采用本文算法对两组点集进行匹配的结果，每条蓝色线段连接了一对匹配点对（本刊黑白印刷，相关疑问咨询作者）。图2（c）显示在正确的匹配点对集合基础上，通过方程求解计算实现了点集之间的配准。

在三维测量过程中，由于测量角度或测量方式的不同，两个点集P和Q之间可能存在以下不同重叠关系：①Q为P的一部分；②P和Q存在部分交叉；③Q为P存在数据缺失情况下P的较稀疏点集。因此，本文采用直升机尾部和汽车点集数据，分别对以上3种不同情况进行测试。如图3所示的汽车数据及图4的直升机尾部数据，第1到第3组分别对应了两组点集重叠关系为以上①、②和③的情况。同时，实际测量过程中也会存在噪声干扰等情况。为模拟实际环境，分析算法的鲁棒性和配准精度，实验中为Q添加均值为0、方差为0.3的高斯白噪声，并在两点集之间产生0°～360°之间任意角度的旋转和随机平移。在情况③下，Q较P具有50%的随机数据丢失。考虑到由于稀疏点集无法提供法向量、曲率或其他线、面等特征，多数配准算法对此不适用，经典的4PCS方法基于同一平面4点组仿射不变性寻找对应关系，虽不受此类限制，但速度过慢，将本文算法与其较成熟的改进算法super 4PCS方法进行比较。

本文以旋转误差和平移误差来评估配准效果。首先将旋转矩阵R转化为按照固定顺序z-y-x内旋的欧拉角，采用欧拉角来计算旋转误差e^R。旋转误差和平移误差分别被定义如下：

式中{R_m，t_m}和{R_g，t_g}分别表示刚体变换的实际值和估计值。为进一步比较配准性能，表1中列出了图3和图4中各组不同数据分别采用super 4PCS和本文算法时所用时间及误差。对图3、图4和表1的数据进行分析可以看出，在配准精度上，本文算法较super 4PCS具有较大优势，对两点集处于各种不同重叠关系均能获得准确的配准结果。在速度方面，对于汽车数据，虽然super 4PCS速度较快，但得到的配准结果均有较大偏差。根据文献[5]，super 4PCS虽然优化了提取4点集的时间，但在点集验证过程的速度仍然没有太大改善，对文中点数不多的模型进行配准时仍然异常耗费时间。在本文直升机尾部数据实验中，其耗费时间也较长，而本文算法则能快速稳定地获取正确配准结果。可见本文算法对于三维视觉测量中所获得的稀疏点集之间的匹配和配准具有重要意义。

3 结语

本文对基于标记点的三维视觉测量所获得的稀疏点集数据，提出一种基于距离哈希的快速匹配方法。将点集中任一点与邻近点的距离在刚体变换下的不变性作为点集匹配的特征，通过距离哈希方法将距离关系映射为一个二进制码身份标签，快速的二进制码相似度计算方法能够实现点集间同名匹配点的高效查找。最后通过基于k-d树的最邻近点查找方法进行距离校验，从而实现点集间的精匹配。基于汽车和直升机尾部测量数据的多个实验表明，本文算法速度快，准确率高，对噪点及各种不同重叠情况具有稳健性，且对两个点集之间的初始位置没有任何限制，对于表面形状复杂的物体亦能获得良好的结果。

参考文献：

[1] BESL P J，MCKAY N D. A method for registration of 3-D shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，1992，14（2）：239-256.

[2] DÍEZY，ROUREF，LLADÓX，et al. A qualitative review on 3D coarse registration methods[J]. ACM Computing Surveys，2015，47（3）：1-36.

[3] BUENO M， GONZÁLEZ J ， MARTÍNEZ S， et al. Automatic point cloud coarse registration using geometric keypoint descriptors for indoor scenes[J]. Automation in Construction，2017，81：134-148.

[4] AIGER D，MITRA N J，COHEN-OR D. 4-points congruent sets for robust pairwise surface registration[J]. ACM Transactions on Graphics，2008，27（3）：1-10.

[5] MELLADO N，AIGER D，MITRA N J. Super 4PCS fast global pointcloud registration via smart indexing[J]. Computer Graphics Forum， 2014， 33（5）： 205-215

[6] HUANG J D，KWOK T H，ZHOU C. V4PCS：volumetric 4PCS algorithm for global registration[J]. Journal of Mechanical Design，2017，139（11）：111403.

[7] XU Y S， BOERNER R， YAO W，et al. Pairwise coarse registration of point clouds in urban scenes using voxel-based 4-planes congruent sets[J]. ISPRS Journal of Photogrammetry and Remote Sensing， 2019， 151： 106-123.

[8] TIAN D H， JIA X Q， MA R， et al. BinDeep： a deep learning approach to binary code similarity detection[J]. Expert Systems with Applications， 2021，168：114348.

[9] JUAREZ PAULINO D S ， DIBIO L B， FLAVIO B V. A dynamic approach for approximate pairwise alignment based on 4-points congruence sets of 3D points[C]//2011 18th IEEE International Conference on Image Processing， Brussels，Belgium：IEEE，2011：889-892.

[10] BENTLEY J L. Multidimensional binary search trees used for associative searching[J]. Communications of the ACM，1975，18（9）：509-517.

收稿日期：2023-02-15