摘 要：針對不同坐標(biāo)系下部分重疊的稀疏坐標(biāo)點集，提出一種基于距離哈希的同名點快速穩(wěn)健匹配算法。將各點與其鄰近點的距離關(guān)系映射成一個二進制碼身份標(biāo)簽，通過身份標(biāo)簽相似度計算，找出兩個點集中滿足設(shè)定閾值的候選匹配點對，從而建立初始匹配關(guān)系。據(jù)此計算剛體變換矩陣對兩組點集進行配準(zhǔn)，確定兩組點集之間的精確匹配關(guān)系。實驗結(jié)果表明：該算法不僅速度快、準(zhǔn)確率高、對于噪點和低重疊度具有穩(wěn)健性，而且對兩個點集之間的初始相對位置沒有任何限制。

關(guān)鍵詞：機器視覺；稀疏點集；點集匹配；距離哈希；二進制碼

中圖分類號：TP391.7 文獻標(biāo)志碼：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 引言

點云配準(zhǔn)技術(shù)是針對激光掃描儀、結(jié)構(gòu)光測量系統(tǒng)等設(shè)備所獲得的同一物體在不同視角下的海量點云數(shù)據(jù)進行合并的技術(shù)。最經(jīng)典的點云配準(zhǔn)算法是由BESL等^[1]提出的最近點迭代算法（iterative closest point， ICP），通過反復(fù)迭代尋找最佳同名匹配點對，以估計變換矩陣。但算法的運行速度和收斂性很大程度取決于點云的初始位姿，目標(biāo)函數(shù)還易陷入局部最優(yōu)的情況，故需要粗配準(zhǔn)^[2-3]為其提供初始位姿，常作為二次精配準(zhǔn)使用。

一種影響廣泛的經(jīng)典粗配準(zhǔn)方法基于全等4點集（4-points congruent sets，4PCS）^[4]，通過在目標(biāo)點云和源點云之間尋找具有相同拓撲結(jié)構(gòu)的4點對，來計算兩個點集之間的變換矩陣，對噪聲、遮擋和異常值具有較高的魯棒性，4PCS算法的主要問題在于比較慢，提取相似集和驗證變換都比較耗時。Super 4PCS^[5]、volumetric 4PCS^[6]、voxel 4PCS^[[7]等方法都致力于提高4PCS的速度，但對于工業(yè)應(yīng)用仍然配準(zhǔn)精度較低，配準(zhǔn)速度也難以滿足一些較復(fù)雜應(yīng)用的要求。

基于哈希的文件檢索方法^[8]是近年來廣受關(guān)注的在海量數(shù)據(jù)中尋找相似文檔的方法。它的基本思想是通過找到一個合適的哈希函數(shù)，將數(shù)據(jù)庫中的每個項目映射為一個簡單的二進制代碼，并且使得相似的項目具有相似的二進制代碼。受上述基于哈希方法的二進制編碼在相似性匹配和檢索中成功應(yīng)用的啟發(fā)，本文針對部分重疊的稀疏點集的同名點匹配問題，提出一種基于距離哈希的二進制編碼的快速穩(wěn)健匹配方法。

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≤δ都成立，δ為較小常數(shù)，T為點集P和Q之間的剛性變換。則當(dāng)集合C含有元素數(shù)量最多時，兩個點集之間的剛性變換為最佳剛性變換T_best，此時記C=C_max為最大匹配公共集。最大公共集（largest common pointset，LCP）問題^[9]就是通過不斷比較元素尋求C_max，從而獲得兩個點集之間的最佳剛性變換。LCP是點集配準(zhǔn)技術(shù)要達到的目標(biāo)，也是衡量配準(zhǔn)質(zhì)量的一個標(biāo)準(zhǔn)。

1.1 距離哈希編碼

對點集P中任一點p_i，可以借助k-d樹^[10]快速為其查找自身所在點集中的K個鄰近點p_ik（k=1，2，…，K），隨后將點p_i與p_ik之間的歐氏距離轉(zhuǎn)化為二進制身份碼，如圖1所示。為了更清楚地展示編碼過程，圖1中僅顯示p_i的6個鄰近點。

在對兩個點集P和Q中的點進行二進制編碼時，首先會設(shè)立一個長度為l的固定步長，將歐氏距離轉(zhuǎn)化為步數(shù)S。在點p_i與其K個鄰近點p_ik的距離中，d_max為最大距離。對d_max/l向上取整作為該身份碼的長度S，即

S=ceil（d_max/l）（1）

根據(jù)S和l為p_i建立一個二進制位數(shù)組I_D，pi，該數(shù)組含二進制位個數(shù)為S，每一位初始值為0。鄰近點中p_ik與p_i之間的歐氏距離為d_ik，轉(zhuǎn)化成步數(shù)s_ik為

s_ik=ceil（d_ik/l）（2）

若二進制位數(shù)組I_D，pi的第s_ik位為1，則等價于p_i在步數(shù)為s_ik的位置存在一個鄰近點。將每個鄰近點映射到p_i的二進制數(shù)組上，則點p_i與其K個最鄰近點之間的距離特征被轉(zhuǎn)換為二進制碼I_D，pi，定義I_D，pi為點p_i的二進制身份標(biāo)簽。

1.2 相似度比較

通過上一節(jié)距離哈希算法，將點集P和Q中的數(shù)據(jù)點與其臨近點之間的距離關(guān)系映射為二進制身份編碼，從而使得點集中任一點都具有一個二進制碼身份標(biāo)簽。該身份標(biāo)簽在保留原點集各點與其鄰近點之間距離特征的同時大大簡化了數(shù)據(jù)的存儲。在完成兩個點集中所有數(shù)據(jù)的二進制身份編碼后，將點集P中數(shù)據(jù)的身份標(biāo)簽與點集Q中數(shù)據(jù)的身份標(biāo)簽逐一進行對比，即對二進制碼I_D，pi（i=1，2，…，m）和I_D，qj（j=1，2，…，n）進行按位“與”運算，將其結(jié)果記為r=I_D，piamp;I_D，qj，計算r中二進制位值為1的總位數(shù)N_r，則兩點之間的相似度M為

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

式中N_pi和N_qj分別為I_D，pi和I_D，qj中二進制位值為1的總位數(shù)。在點集Q中循環(huán)，求出使M最大的序號J，并記最大相似度M=M_max，若M_max的值大于設(shè)定閾值β，則可認(rèn)為p_i和q_J是一對候選匹配點對。經(jīng)過上述相似度計算和比較后，可獲得點集P和Q之間的初始匹配點對集合C_f。

1.3 基于最鄰近點的精確匹配

在初始匹配點對集合C_f內(nèi)，點對之間可能存在誤匹配的情況，而其中相似度較大的一些點往往是正確的匹配點對。因此，本文在集合C_f中，取相似度最大的L個點對計算初始剛體變換T_f（R_f，t_f），將點集P中的各點轉(zhuǎn)換至Q所在的坐標(biāo)系下，即做變換：

p^f_i=R_fp_i+t_f（4）

經(jīng)過變換后的點集P和Q中的匹配點對應(yīng)該具有相近的位置，對應(yīng)點間距離應(yīng)在三維測量產(chǎn)生的誤差范圍內(nèi)。為此，通過查找最鄰近點的方法來進行更精確的匹配。在點集Q所形成的k-d樹中搜索p^f_i的最鄰近點q_rst，當(dāng)最鄰近點p^f_i與q_rst的距離小于兩組點云的測量誤差之和時，則認(rèn)為p_i和q_j是一對正確的匹配點。最終獲得精確匹配點對集合C_max。在集合C_max基礎(chǔ)上通過奇異值分解算法（singular value decomposition， SVD），即可求解P和Q之間的剛體變換矩陣，進而完成點集之間的配準(zhǔn)。

2 實驗結(jié)果與分析

為驗證本文算法效果，以工業(yè)中常見且具有不同表面特征的直升機和汽車為例進行測試，所采用實驗數(shù)據(jù)為自主研發(fā)的工業(yè)近景攝影測量軟件所獲得的直升機尾部和汽車的特征點集數(shù)據(jù)。

圖2顯示了對直升機尾部數(shù)據(jù)進行匹配及配準(zhǔn)的結(jié)果。圖2（a）中，P為直升機尾部測量數(shù)據(jù)，Q為直升機尾部數(shù)據(jù)的一部分，與P之間存在旋轉(zhuǎn)角度為45°，平移為{1 000， 2 000， 0}的剛體變換，并添加均值為0、方差為0.2的高斯白噪聲，P和Q含數(shù)據(jù)點個數(shù)分別為1 220和190。圖2（b）為采用本文算法對兩組點集進行匹配的結(jié)果，每條藍色線段連接了一對匹配點對（本刊黑白印刷，相關(guān)疑問咨詢作者）。圖2（c）顯示在正確的匹配點對集合基礎(chǔ)上，通過方程求解計算實現(xiàn)了點集之間的配準(zhǔn)。

在三維測量過程中，由于測量角度或測量方式的不同，兩個點集P和Q之間可能存在以下不同重疊關(guān)系：①Q(mào)為P的一部分；②P和Q存在部分交叉；③Q為P存在數(shù)據(jù)缺失情況下P的較稀疏點集。因此，本文采用直升機尾部和汽車點集數(shù)據(jù)，分別對以上3種不同情況進行測試。如圖3所示的汽車數(shù)據(jù)及圖4的直升機尾部數(shù)據(jù)，第1到第3組分別對應(yīng)了兩組點集重疊關(guān)系為以上①、②和③的情況。同時，實際測量過程中也會存在噪聲干擾等情況。為模擬實際環(huán)境，分析算法的魯棒性和配準(zhǔn)精度，實驗中為Q添加均值為0、方差為0.3的高斯白噪聲，并在兩點集之間產(chǎn)生0°～360°之間任意角度的旋轉(zhuǎn)和隨機平移。在情況③下，Q較P具有50%的隨機數(shù)據(jù)丟失。考慮到由于稀疏點集無法提供法向量、曲率或其他線、面等特征，多數(shù)配準(zhǔn)算法對此不適用，經(jīng)典的4PCS方法基于同一平面4點組仿射不變性尋找對應(yīng)關(guān)系，雖不受此類限制，但速度過慢，將本文算法與其較成熟的改進算法super 4PCS方法進行比較。

本文以旋轉(zhuǎn)誤差和平移誤差來評估配準(zhǔn)效果。首先將旋轉(zhuǎn)矩陣R轉(zhuǎn)化為按照固定順序z-y-x內(nèi)旋的歐拉角，采用歐拉角來計算旋轉(zhuǎn)誤差e^R。旋轉(zhuǎn)誤差和平移誤差分別被定義如下：

式中{R_m，t_m}和{R_g，t_g}分別表示剛體變換的實際值和估計值。為進一步比較配準(zhǔn)性能，表1中列出了圖3和圖4中各組不同數(shù)據(jù)分別采用super 4PCS和本文算法時所用時間及誤差。對圖3、圖4和表1的數(shù)據(jù)進行分析可以看出，在配準(zhǔn)精度上，本文算法較super 4PCS具有較大優(yōu)勢，對兩點集處于各種不同重疊關(guān)系均能獲得準(zhǔn)確的配準(zhǔn)結(jié)果。在速度方面，對于汽車數(shù)據(jù)，雖然super 4PCS速度較快，但得到的配準(zhǔn)結(jié)果均有較大偏差。根據(jù)文獻[5]，super 4PCS雖然優(yōu)化了提取4點集的時間，但在點集驗證過程的速度仍然沒有太大改善，對文中點數(shù)不多的模型進行配準(zhǔn)時仍然異常耗費時間。在本文直升機尾部數(shù)據(jù)實驗中，其耗費時間也較長，而本文算法則能快速穩(wěn)定地獲取正確配準(zhǔn)結(jié)果?？梢姳疚乃惴▽τ谌S視覺測量中所獲得的稀疏點集之間的匹配和配準(zhǔn)具有重要意義。

3 結(jié)語

本文對基于標(biāo)記點的三維視覺測量所獲得的稀疏點集數(shù)據(jù)，提出一種基于距離哈希的快速匹配方法。將點集中任一點與鄰近點的距離在剛體變換下的不變性作為點集匹配的特征，通過距離哈希方法將距離關(guān)系映射為一個二進制碼身份標(biāo)簽，快速的二進制碼相似度計算方法能夠?qū)崿F(xiàn)點集間同名匹配點的高效查找。最后通過基于k-d樹的最鄰近點查找方法進行距離校驗，從而實現(xiàn)點集間的精匹配?；谄嚭椭鄙龣C尾部測量數(shù)據(jù)的多個實驗表明，本文算法速度快，準(zhǔn)確率高，對噪點及各種不同重疊情況具有穩(wěn)健性，且對兩個點集之間的初始位置沒有任何限制，對于表面形狀復(fù)雜的物體亦能獲得良好的結(jié)果。

參考文獻：

[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