基于距離哈希的稀疏點(diǎn)集快速匹配算法研究

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

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

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

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

一種影響廣泛的經(jīng)典粗配準(zhǔn)方法基于全等4點(diǎn)集（4-points congruent sets，4PCS）^[4]，通過在目標(biāo)點(diǎn)云和源點(diǎn)云之間尋找具有相同拓?fù)浣Y(jié)構(gòu)的4點(diǎn)對，來計(jì)算兩個(gè)點(diǎn)集之間的變換矩陣，對噪聲、遮擋和異常值具有較高的魯棒性，4PCS算法的主要問題在于比較慢，提取相似集和驗(yàn)證變換都比較耗時(shí)。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ù)中尋找相似文檔的方法。它的基本思想是通過找到一個(gè)合適的哈希函數(shù)，將數(shù)據(jù)庫中的每個(gè)項(xiàng)目映射為一個(gè)簡單的二進(jìn)制代碼，并且使得相似的項(xiàng)目具有相似的二進(jìn)制代碼。受上述基于哈希方法的二進(jìn)制編碼在相似性匹配和檢索中成功應(yīng)用的啟發(fā)，本文針對部分重疊的稀疏點(diǎn)集的同名點(diǎn)匹配問題，提出一種基于距離哈希的二進(jìn)制編碼的快速穩(wěn)健匹配方法。

1 基于哈希的稀疏點(diǎn)云匹配算法

給定同一物體從任意兩個(gè)不同角度獲得的三維點(diǎn)集P和Q，若存在匹配點(diǎn)對集合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為點(diǎn)集P和Q之間的剛性變換。則當(dāng)集合C含有元素?cái)?shù)量最多時(shí)，兩個(gè)點(diǎn)集之間的剛性變換為最佳剛性變換T_best，此時(shí)記C=C_max為最大匹配公共集。最大公共集（largest common pointset，LCP）問題^[9]就是通過不斷比較元素尋求C_max，從而獲得兩個(gè)點(diǎn)集之間的最佳剛性變換。LCP是點(diǎn)集配準(zhǔn)技術(shù)要達(dá)到的目標(biāo)，也是衡量配準(zhǔn)質(zhì)量的一個(gè)標(biāo)準(zhǔn)。

1.1 距離哈希編碼

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

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

S=ceil（d_max/l）（1）

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

s_ik=ceil（d_ik/l）（2）

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

1.2 相似度比較

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

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

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

1.3 基于最鄰近點(diǎn)的精確匹配

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

p^f_i=R_fp_i+t_f（4）

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

2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

3 結(jié)語

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

參考文獻(xiàn)：

[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