劉芊偉 張朝霞 謝怡婷 張成龍

收稿日期：2023-11-10

基金項(xiàng)目：廣東省自然科學(xué)基金（2014A030313739）

DOI：10.19850/j.cnki.2096-4706.2024.07.030

摘? 要：針對(duì)大規(guī)模點(diǎn)云匹配時(shí)傳統(tǒng)算法速度慢和匹配結(jié)果不一致的問題，提出一種新的點(diǎn)云匹配方法。該方法首先利用KD樹找到點(diǎn)云中深度最小的點(diǎn)并以該點(diǎn)作為種子點(diǎn)，然后通過在深度信息和曲率兩個(gè)方面做以改進(jìn)的區(qū)域生長分割算法提取出點(diǎn)云上表面區(qū)域，并在該區(qū)域提取點(diǎn)云邊界。最后使用改進(jìn)的點(diǎn)對(duì)特征完成點(diǎn)云匹配算法驗(yàn)證。實(shí)驗(yàn)結(jié)果表明，相比傳統(tǒng)算法，該方法在匹配速度以及匹配結(jié)果的一致性方面得到了顯著的提升，在處理大規(guī)模點(diǎn)云匹配上具有實(shí)際應(yīng)用價(jià)值。

關(guān)鍵詞：大規(guī)模點(diǎn)云；KD樹；改進(jìn)的區(qū)域生長分割算法；點(diǎn)對(duì)特征

中圖分類號(hào)：TP312；TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2024）07-0146-05

A Point Cloud Matching Algorithm for Large-scale Scenarios

LIU Qianwei， ZHANG Chaoxia， XIE Yiting， ZHANG Chenglong

（School of Mechatronic Engineering and Automation， Foshan University， Foshan? 528225， China）

Abstract： A new point cloud matching method is proposed to address the issues of slow speed and inconsistent matching results in traditional algorithms in large-scale point cloud matching. This method first uses the KD tree to find the point with the minimum depth in point cloud and uses it as a seed point. Then， an improved region growth segmentation algorithm improving in depth information and curvature is used to extract the upper surface area of point cloud， and the point cloud boundary is extracted in this area. Finally， the point cloud matching algorithm is validated using improved point pair features. The experimental results show that compared with traditional algorithms， the proposed method has significantly improved matching speed and consistency of matching results， and has practical application value in handling large-scale point cloud matching.

Keywords： large-scale point cloud; KD tree; improved region growth segmentation algorithm; point pair feature

0? 引? 言

點(diǎn)云匹配[1]是計(jì)算機(jī)視覺和機(jī)器人領(lǐng)域中的一個(gè)重要問題，其目的是將兩個(gè)或多個(gè)點(diǎn)云對(duì)齊，從而實(shí)現(xiàn)對(duì)點(diǎn)云的精確比較、配準(zhǔn)或合并等操作。點(diǎn)云匹配廣泛應(yīng)用于無序抓取[2]和三維重建[3]等方面。常用的點(diǎn)云匹配算法有基于模板的點(diǎn)云匹配算法和基于特征的點(diǎn)云匹配算法。

基于模板的點(diǎn)云匹配算法[4-7]大致思路是采用物體的三維模型在多視角下進(jìn)行投影，經(jīng)過點(diǎn)云處理后提取特征形成姿態(tài)庫，并將姿態(tài)庫中的圖像逐一與RGB-D圖像進(jìn)行比對(duì)選出最合適的模板作為物體的位姿。Peng等人[4]在LineMOD [5]算法的基礎(chǔ)上提出一種多尺度模板訓(xùn)練方法，該方法在進(jìn)行模板匹配時(shí)，首先將測試圖像劃分為幾個(gè)區(qū)域，然后根據(jù)每個(gè)測試圖像的區(qū)域深度選擇深度相似的訓(xùn)練模板。該算法相比于LineMOD算法，增強(qiáng)了對(duì)模板深度的敏感度，提高了模板匹配的速度。Ye [6]等人通過金字塔的在線分層搜索，收集所有相似度量標(biāo)準(zhǔn)的候選模板。所有候選模板及其相鄰模板都被追蹤到金字塔的下一個(gè)較低級(jí)別。重復(fù)相同操作，直至所有候選模板都被追蹤到金字塔的最低級(jí)別。

基于特征的方法有基于局部特征的方法[8，9]和基于全局特征的方法[10，11]。Liu [8]等人在原有基于快速點(diǎn)特征直方圖匹配算法的基礎(chǔ)上，以豪斯多夫距離搜索對(duì)應(yīng)的點(diǎn)對(duì)，并利用隨機(jī)采樣一致性算法剔除不正確的點(diǎn)對(duì)，從而提高對(duì)應(yīng)關(guān)系的準(zhǔn)確性。Yue [9]等人提出的LPPF特征描述符是對(duì)經(jīng)典點(diǎn)對(duì)特征局部應(yīng)用的改進(jìn)描述符，是通過計(jì)算局部點(diǎn)云鄰域的特征信息而形成的直方圖描述符，配準(zhǔn)精度更高，配準(zhǔn)時(shí)間更短。Guo [10]等人提出一種基于PPF改進(jìn)的識(shí)別框架，特別是提出一種新的基于目標(biāo)中心和點(diǎn)對(duì)特征之間幾何關(guān)系的中心投票策略。該算法對(duì)相似外觀的干擾物、傳感器噪聲和簡單幾何形狀具有鑒別性和魯棒性。Liu [11]等人提出一種使用多個(gè)模型描述目標(biāo)物體的方法——多邊緣外觀模型，以提高識(shí)別率并減少計(jì)算時(shí)間。

本文介紹一種針對(duì)大規(guī)模場景的點(diǎn)云匹配算法，相較于現(xiàn)有的點(diǎn)云匹配算法，該算法在以下三個(gè)方面得到了顯著提升：

1）所提取的特征點(diǎn)是點(diǎn)云的輪廓點(diǎn)，能夠保留更多的點(diǎn)云基本信息，適用于大規(guī)模的點(diǎn)云匹配。

2）對(duì)場景點(diǎn)云進(jìn)行區(qū)域化設(shè)置，并僅對(duì)上表面點(diǎn)云進(jìn)行匹配，解決了點(diǎn)云匹配結(jié)果不一致的情況，同時(shí)提高了點(diǎn)云匹配的速度。

3）改進(jìn)的點(diǎn)對(duì)特征提高了匹配算法的準(zhǔn)確性。

1? 提出的方法

1.1? 點(diǎn)云區(qū)域化

在堆疊大場景中有較多相似特征的點(diǎn)云時(shí)，采用傳統(tǒng)點(diǎn)對(duì)特征匹配算法進(jìn)行多次匹配會(huì)出現(xiàn)匹配結(jié)果不一致的情況，同時(shí)匹配速度也比較緩慢。圖1、圖2為在相同場景下多次使用傳統(tǒng)點(diǎn)對(duì)特征匹配的結(jié)果（圖中帶有箭頭的灰色區(qū)域?yàn)槠ヅ浜竽０妩c(diǎn)云區(qū)域），從圖中可以看到匹配結(jié)果并不一致，且圖2中的點(diǎn)云是底部點(diǎn)云不利于做無序抓取。

為解決傳統(tǒng)點(diǎn)對(duì)匹配算法存在的匹配速度緩慢和匹配結(jié)果不一致的問題，選擇采用點(diǎn)云區(qū)域化的方法。該方法融合了深度信息和曲率，通過對(duì)表面點(diǎn)云進(jìn)行提取和匹配，有效解決了傳統(tǒng)點(diǎn)云匹配算法存在的問題。圖3為提取出來的上表面區(qū)域（圖中灰色區(qū)域）。具體步驟為：通過KD樹找到深度最小的點(diǎn)并將該點(diǎn)作為種子點(diǎn)，根據(jù)一定的判斷條件確定是否將鄰域內(nèi)的點(diǎn)加到當(dāng)前種子點(diǎn)所屬的區(qū)域。判斷條件如下：

1）距離條件：鄰域內(nèi)的點(diǎn)與種子點(diǎn)之間的距離在一定的閾值范圍內(nèi)。

2）曲率條件：鄰域內(nèi)點(diǎn)的曲率ki與種子點(diǎn)的曲率差異在一定的閾值范圍內(nèi)。Mi為點(diǎn)mi的協(xié)方差矩陣，計(jì)算式如式（1）所示，通過式（2）計(jì)算出特征向量和特征值，最小特征值對(duì)應(yīng)的特征向量可以表示一個(gè)區(qū)域中法向量的大致趨勢(shì)，可以作為法向量。而最大特征值可以作為曲率ki表示整個(gè)區(qū)域的彎曲程度。

從初始種子點(diǎn)開始，逐步擴(kuò)展鄰域，根據(jù)上述條件將符合條件的點(diǎn)添加到當(dāng)前區(qū)域中?？梢允褂蒙疃葍?yōu)先搜索等算法來遍歷點(diǎn)云并進(jìn)行區(qū)域生長。

在算法運(yùn)算的過程中，可能會(huì)出現(xiàn)不同種子點(diǎn)生長到同一區(qū)域的情況，此時(shí)可以進(jìn)行區(qū)域合并，將重疊的區(qū)域合并成一個(gè)。

遍歷所有的子區(qū)域，用KD樹判斷深度最小的點(diǎn)位于哪個(gè)子區(qū)域的領(lǐng)域內(nèi)，這時(shí)可以得到包含深度最小點(diǎn)的匹配區(qū)域。

（1）

（2）

其中， 為特征向量； 為特征值，設(shè) ； 為最小特征值； 為mi的法向量； 為最大特征值且為mi的曲率kj。

（3）

1.2? 點(diǎn)云關(guān)鍵點(diǎn)提取

點(diǎn)云關(guān)鍵點(diǎn)是指能夠反映點(diǎn)云幾何形狀的點(diǎn)集。通過點(diǎn)云特征點(diǎn)確定的特征描述符具有平移旋轉(zhuǎn)不變性。選用點(diǎn)云的邊界點(diǎn)作為點(diǎn)云的關(guān)鍵點(diǎn)，能夠在保證點(diǎn)云基本信息不變的情況下得到較好的匹配結(jié)果。

本文通過點(diǎn)云法向量提取點(diǎn)云邊界，該算法通過計(jì)算每個(gè)點(diǎn)的法向量與其相鄰點(diǎn)法向量之間的夾角來識(shí)別邊界點(diǎn)。具體來說，該算法的步驟為：首先計(jì)算每個(gè)點(diǎn)的法向量，通過pi與其最近鄰點(diǎn)集合Ni中所有點(diǎn)的均值pa計(jì)算pi的協(xié)方差矩陣Mi：

（4）

其中，n為pi領(lǐng)域點(diǎn)的個(gè)數(shù)。對(duì)Mi進(jìn)行特征值分解得到特征向量和特征值：

（5）

其中， 為特征向量； 為特征值，設(shè) ，則最小特征值? 是點(diǎn)pi的法向量。首先采用KD樹數(shù)據(jù)結(jié)構(gòu)找到每個(gè)點(diǎn)的相鄰點(diǎn)；然后計(jì)算每個(gè)點(diǎn)的法向量與其相鄰點(diǎn)的法向量之間的夾角，將夾角超過預(yù)設(shè)閾值的點(diǎn)標(biāo)記為邊界點(diǎn)；最后對(duì)邊界點(diǎn)進(jìn)行聚類以識(shí)別多個(gè)不同的邊界。該算法運(yùn)用了點(diǎn)云中每個(gè)點(diǎn)的法向量信息，具有簡單、高效、適用于大規(guī)模點(diǎn)云數(shù)據(jù)集等優(yōu)點(diǎn)。如圖4所示為提取輪廓前后的模板點(diǎn)云圖。

1.3? 改進(jìn)的點(diǎn)對(duì)特征

提取完上表面點(diǎn)云的特征點(diǎn)后，后續(xù)就是對(duì)模板點(diǎn)云進(jìn)行離線建模，對(duì)上表面場景點(diǎn)云進(jìn)行特征計(jì)算。然后通過哈希表查找上表面點(diǎn)云和模板點(diǎn)云相似的特征對(duì)。

傳統(tǒng)點(diǎn)對(duì)特征匹配算法的特征是通過兩個(gè)點(diǎn)之間法向量的關(guān)系得到的，它可以表示兩個(gè)點(diǎn)之間的位置關(guān)系，具體的描述如圖5所示。已知法線n1、n2、點(diǎn)m1和m2，可以通過式（6）得到點(diǎn)對(duì)特征。其中，F(xiàn)1為兩個(gè)點(diǎn)之間的距離，而F2、F3、F4為法向量n1、n2和向量m1m2的夾角。特征描述如圖5所示。

當(dāng)涉及點(diǎn)云的特征匹配時(shí)，傳統(tǒng)方法通常僅關(guān)注點(diǎn)對(duì)之間的關(guān)系，而忽略了整體的點(diǎn)云結(jié)構(gòu)和曲率特性。為了克服這一弊端，本文提出一種改進(jìn)的特征匹配方法，它綜合考慮了鄰域信息和曲率特征，以下是詳細(xì)描述：

首先，引入點(diǎn)的鄰域概念，對(duì)每個(gè)點(diǎn)定義鄰域N1和N2。這樣的設(shè)計(jì)能夠更全面地把握每個(gè)點(diǎn)的特征，不再局限于分析點(diǎn)對(duì)之間的關(guān)系。

隨后，計(jì)算鄰域N1和N2內(nèi)點(diǎn)的協(xié)方差矩陣，分別標(biāo)記為M1和M2。協(xié)方差矩陣是一個(gè)有力的工具，可以描述點(diǎn)在不同坐標(biāo)軸上的分布情況和協(xié)同變化。此外，充分考慮了點(diǎn)云的曲率特性，用于更好地描述點(diǎn)的曲率情況。曲率是描述曲線或曲面彎曲程度的重要概念。傳統(tǒng)的點(diǎn)對(duì)特征很難準(zhǔn)確捕捉點(diǎn)云的曲率特征。因此，在本方法中，通過計(jì)算點(diǎn)云的曲率信息，能夠更加準(zhǔn)確地呈現(xiàn)點(diǎn)云表面的局部特點(diǎn)。綜上，這種方法能夠更全面地描述每個(gè)點(diǎn)的特征。通過結(jié)合點(diǎn)的鄰域結(jié)構(gòu)和曲率信息，提高了特征匹配的準(zhǔn)確性和魯棒性。改進(jìn)的點(diǎn)對(duì)特征計(jì)算式如式（11）所示。F1、F2、F3、F4為傳統(tǒng)的點(diǎn)對(duì)特征，而F5、F6為m1和m2的曲率。特征描述如圖6所示。

（11）

（12）

（13）

2? 實(shí)驗(yàn)部分

本節(jié)描述了本文算法在點(diǎn)云數(shù)據(jù)上的性能測試，并將測試結(jié)果與現(xiàn)有最先進(jìn)描述符的結(jié)果進(jìn)行了比較。場景點(diǎn)云和模板點(diǎn)云通過三維相機(jī)拍攝獲得。其中模板點(diǎn)云的大小為11 980，場景點(diǎn)云的大小為幾十萬的數(shù)量級(jí)，滿足大規(guī)模點(diǎn)云匹配的要求。為了驗(yàn)證本文算法的有效性，在四個(gè)場景下對(duì)PPF、FPFH和本文算法進(jìn)行了比較。

2.1? 算法評(píng)價(jià)指標(biāo)

為了對(duì)比不同算法的實(shí)驗(yàn)效果，使用了均方根誤差（RMSE）和運(yùn)行時(shí)間（TIME）。通過RMSE來確定算法匹配的精度，采用TIME來表示算法的時(shí)間復(fù)雜度。

RMSE用于評(píng)估預(yù)測值與真實(shí)值之間的誤差。在點(diǎn)云匹配中，模板點(diǎn)云經(jīng)過剛體變換后得到一組點(diǎn)云，對(duì)這組點(diǎn)云和場景點(diǎn)云進(jìn)行計(jì)算即可得到均方根誤差。RMSE計(jì)算式如式（14）所示：

（14）

其中，pi為剛體變換后模板點(diǎn)云中的點(diǎn)；qi為場景點(diǎn)云中距離pi最近的點(diǎn)。

2.2? 匹配實(shí)驗(yàn)

針對(duì)三組場景點(diǎn)云進(jìn)行了三種算法的實(shí)驗(yàn)，包括本文算法、FPFH和PPF，記錄了實(shí)驗(yàn)數(shù)據(jù)。實(shí)驗(yàn)結(jié)果如圖7、圖8和圖9所示（圖中帶有箭頭的灰色區(qū)域?yàn)槠ヅ浜竽０妩c(diǎn)云區(qū)域），實(shí)驗(yàn)數(shù)據(jù)如表1所示。在圖7中，（a）和（b）展示了PPF對(duì)場景a進(jìn)行匹配時(shí)的兩次不同結(jié)果，（c）（d）展示了PPF算法對(duì)場景b、c進(jìn)行匹配后的結(jié)果。圖8展示了FPFH算法對(duì)場景a、d、c匹配后的結(jié)果。圖9展示了本文算法對(duì)場景a、b、c匹配后的結(jié)果。

在三個(gè)不同的場景中，分別使用PPF、FPFH和本文算法進(jìn)行了實(shí)驗(yàn)，并記錄了這些算法在每個(gè)場景中的性能指標(biāo)，包括處理的點(diǎn)云數(shù)量、均方根誤差（RMSE）和運(yùn)行時(shí)間（TIME）。相關(guān)數(shù)據(jù)整理在表1中。通過對(duì)這些數(shù)據(jù)的分析，能夠得出以下幾個(gè)結(jié)論。

首先，從數(shù)據(jù)來看，F(xiàn)PFH算法的運(yùn)行速度優(yōu)于PPF算法，但前者在匹配精度上稍有下降。與之相反，本文算法在匹配速度方面不僅超越了FPFH算法，在匹配精度方面亦表現(xiàn)出色，優(yōu)于PPF算法。因此，本文算法在處理大規(guī)模點(diǎn)云匹配任務(wù)方面表現(xiàn)出色。

其次，在使用PPF算法進(jìn)行場景a匹配時(shí)，出現(xiàn)了兩次匹配結(jié)果不一致的情況。而使用本文算法可有效避免這種情況的發(fā)生。

最后，通過匹配結(jié)果的可視化，發(fā)現(xiàn)當(dāng)使用PPF算法和FPFH算法進(jìn)行匹配時(shí)，這些算法會(huì)出現(xiàn)匹配底層的點(diǎn)云。然而，本文算法將匹配點(diǎn)集中在了物體表面上的點(diǎn)云。這一特性有助于避免在無序取任務(wù)中錯(cuò)誤地抓取底層物體。

3? 結(jié)? 論

為了解決傳統(tǒng)點(diǎn)對(duì)特征匹配算法匹配速度慢和匹配不一致的問題，本文提出一種新的點(diǎn)云匹配算法，該算法通過引入改進(jìn)的區(qū)域生長分割和點(diǎn)云的深度信息，加快了匹配速度并提高了匹配的一致性。同時(shí)，在傳統(tǒng)點(diǎn)對(duì)特征的基礎(chǔ)上加入了曲率特征，提高了點(diǎn)云匹配的精度。因此，在應(yīng)對(duì)點(diǎn)云匹配問題時(shí)，本文算法提供一種有效且可行的解決方案。

參考文獻(xiàn)：

[1] 李建微，占家旺.三維點(diǎn)云配準(zhǔn)方法研究進(jìn)展 [J].中國圖像圖形學(xué)報(bào)，2022，27（2）：349-367.

[2] 陶杰，吳堯才，朱熙豪，等.基于3D視覺的水泵生產(chǎn)線零部件無序抓取研究 [J].機(jī)電工程，2022，39（5）：604-611+640.

[3] ZHANG X，CHEN L，ZHANG F F，et al. Research on the Accuracy and Speed of Three-dimensional Reconstruction of Liver Surface Based on Binocular Structured Light [J].IEEE Access，2021，9：87592-87610.

[4] PENG J，SU Y. An Improved Algorithm for Detection and Pose Estimation of Texture-Less Objects [J].Journal of Advanced Computatioanl Intelligence and Intelligent Informatics，2021，25（2）：204-212.

[5] HINTERSTOISSER S，HOLZER S，CAGNIART C，et al. Multimodal Templates for Real-time Detection of Texture-less Objects in Heavily Cluttered Scenes [C]//Proceedings of the 2011 International Conference on Computer Vision. [S.I.]：IEEE Computer Society，2011：858-865.

[6] YE C Q，LI K，JIA L，et al. Fast Hierarchical Template Matching Strategy for Real-Time Pose Estimation of Texture-Less Objects [C]//International Conference on Intelligent Robotics and Applications. Tokyo：Springer，2016：225-236.

[7] HINTERSTOISSER S，CAGNIART C，ILIC S，et al. Gradient response maps for real-time detection of textureless objects [J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34（5）：876-888.

[8] LIU Y S，KONG D H，ZHAO D D，et al. A Point Cloud Registration Algorithm Based on Feature Extraction and Matching [J/OL].Mathematical Problems in Engineering，2018，2018[2023-10-02].https：//doi.org/10.1155/2018/7352691.

[9] YUE X F，LIU Z Y，ZHU J，et al. Coarse-fine Point Cloud Registration Based on Local Point-pair Features and the Iterative Closest Point Algorithm [J].Applied Intelligence，2022，52（11）：12569-12583.

[10] GUO J W，XING X J，QUAN W Z，et al. Efficient Center Voting for Object Detection and 6D Pose Estimation in 3D Point Cloud [J/OL].IEEE Transactions on Image Processing： a Publication of the IEEE Signal Processing Society，2021，30：5072-5084.

[11] LIU D Y，ARAI S，MIAO J Q，et al. Point Pair Feature-Based Pose Estimation with Multiple Edge Appearance Models （PPF-MEAM） for Robotic Bin Picking [J/OL].Sensors，2018，18（8）：2719[2023-09-20]. https：//doi.org/10.3390/s18082719.

作者簡介：劉芊偉（2000—），男，漢族，江西上饒人，碩士研究生在讀，研究方向：三維視覺；張朝霞（1976—），女，漢族，廣東佛山人，副教授，博士，研究方向：三維視覺；謝怡婷（2000—），女，漢族，廣東梅州人，碩士研究生在讀，研究方向：三維視覺；張成龍（1997—），男，漢族，廣東茂名人，碩士研究生在讀，研究方向：三維視覺。