基于加權(quán)距離投票的點(diǎn)云匹配算法設(shè)計

韓德川

（中國電子科技集團(tuán)公司第二十研究所，西安 710068）

0 引言

在計算機(jī)應(yīng)用領(lǐng)域，點(diǎn)云匹配是一個非常重要的中間步驟，它在表面重建、三維物體識別、相機(jī)定位等問題中有著極其重要的應(yīng)用。對于點(diǎn)云匹配問題，研究者提出了很多解決方案，如點(diǎn)標(biāo)記法、自旋圖像、主曲率方法、遺傳算法、隨機(jī)采樣一致性算法等，這些算法各有特色，在許多特定的情況下能夠解決點(diǎn)云匹配的問題。但是應(yīng)用最廣泛、影響最大的還是由Besl于1992 年提出的迭代最近點(diǎn)算法（Itera?tiveClosest Point，ICP），該算法重復(fù)進(jìn)行選擇對應(yīng)關(guān)系點(diǎn)對，計算最優(yōu)剛體變換，直到滿足正確配準(zhǔn)的收斂精度要求，其本質(zhì)是基于最小二乘法的最優(yōu)配準(zhǔn)方法。ICP算法雖然因為簡單而被廣泛應(yīng)用，但是它易于陷入局部最大值，同時其嚴(yán)重依賴初始配準(zhǔn)位置，它要求兩個點(diǎn)云的初始位置必須足夠近，并且當(dāng)存在噪聲點(diǎn)、外點(diǎn)時可能導(dǎo)致配準(zhǔn)失敗。除ICP 算法之外，Tsin和Kanade應(yīng)用核密度估計，將點(diǎn)云表示成概率密度，提出了核心相關(guān)算法（Kernel Correla?tion，KC）。這種計算最優(yōu)配準(zhǔn)的方法通過設(shè)置兩個點(diǎn)云間的相似度測量來減小它們的距離。對全局目標(biāo)函數(shù)執(zhí)行最優(yōu)化算法，使目標(biāo)函數(shù)值減小到收斂域。因為一個點(diǎn)云中的點(diǎn)必須和另一個點(diǎn)云中的所有點(diǎn)進(jìn)行比較，所以這種方法的算法復(fù)雜度很高。

在生產(chǎn)制造中，很多時候需要對部件位姿調(diào)整過程中的點(diǎn)云進(jìn)行匹配，例如航天器的自動對接過程，然而上述較為熟知的算法，無法很好地適用于部件位姿調(diào)整過程中的點(diǎn)云匹配任務(wù)，進(jìn)而無法完成姿態(tài)追蹤等問題，對此，本文提出一種基于加權(quán)距離投票的點(diǎn)云匹配算法，完成位姿調(diào)整過程中的部件表面點(diǎn)云匹配。

1 算法原理

本文所提出的點(diǎn)云匹配算法是建立在點(diǎn)云的距離不變性之上的。隨著部件位姿調(diào)整，部件外形在線測量系統(tǒng)可獲得不同視角下的部件表面標(biāo)志點(diǎn)點(diǎn)云數(shù)據(jù)，但標(biāo)志點(diǎn)與其周圍的標(biāo)志點(diǎn)的空間距離是不隨測量視角改變而發(fā)生變化，本文利用部件表面點(diǎn)云的距離不變性來進(jìn)行點(diǎn)云匹配。

圖1 距離不變性示意圖

假設(shè)不同視角下測得移動部件表面局部點(diǎn)云數(shù)據(jù)1 和點(diǎn)云數(shù)據(jù)2 包含部分共有的標(biāo)志點(diǎn)測量數(shù)據(jù)，其中移動部件表面局部點(diǎn)云數(shù)據(jù)1中的測量標(biāo)志點(diǎn)為：={s|s∈,= 1,2…} ，移動部件表面局部點(diǎn)云數(shù)據(jù)2 中的測量標(biāo)志點(diǎn)為：={t|t∈,= 1,2…} 。部件表面測量點(diǎn)云的匹配過程，即找到、中同一測量標(biāo)志點(diǎn)，確定部件表面局部點(diǎn)云間同一測量標(biāo)志點(diǎn)點(diǎn)對集，完成無序點(diǎn)云匹配的過程。設(shè)和中同一部件表面測量標(biāo)志點(diǎn)構(gòu)成的有序子集分 別 為：={p| p∈,= 1,2…} 和={q|q∈,= 1,2…} ，其中(p,q)為匹配測量標(biāo)志點(diǎn)點(diǎn)對，即(p,q)分別為不同視角下同一測量標(biāo)志點(diǎn)的三維空間坐標(biāo)，則點(diǎn)云匹配過程如圖2所示。

圖2 部件表面測量點(diǎn)云匹配

根據(jù)標(biāo)志點(diǎn)的空間距離不變性，若(p,q)、(p,q)為兩組匹配測量標(biāo)志點(diǎn)點(diǎn)對時，必滿足如下約束。

其中，為距離誤差閾值，由雙目測量精度確定。

因此，由于測量標(biāo)志點(diǎn)空間分布的隨機(jī)性，當(dāng)(p,q)為匹配測量標(biāo)志點(diǎn)點(diǎn)對時，p到部件表面局部點(diǎn)云中每個點(diǎn)的距離依次與q到部件表面局部點(diǎn)云中每個點(diǎn)的距離相比較，滿足以下不等式的總個數(shù)最多。

圖3 距離投票示意圖

遍歷過點(diǎn)p的所有邊，并按以上規(guī)則對中頂點(diǎn)進(jìn)行投票，當(dāng)所有的邊投票結(jié)束時，得票最多的點(diǎn)T即為點(diǎn)p的匹配點(diǎn)。重復(fù)以上步驟，直至找到部件表面局部點(diǎn)云和部件表面局部點(diǎn)云中所有的匹配點(diǎn)對。

2 算法實現(xiàn)

（5）遍歷部件表面局部點(diǎn)云中所有頂點(diǎn)的得票數(shù)，得分最多的點(diǎn)T即為待匹配點(diǎn)S的匹配點(diǎn)；

（6）循環(huán)執(zhí)行步驟（3）直至找到所有匹配點(diǎn)對；

3 算法分析

3.1 算法時效性分析

通過不同規(guī)模的點(diǎn)云仿真實驗對點(diǎn)云匹配算法的時效性展開分析，部分點(diǎn)云匹配結(jié)果如圖4所示。其中，圓點(diǎn)云為原始點(diǎn)云，菱形點(diǎn)為目標(biāo)點(diǎn)云，五角星點(diǎn)為由距離投票法計算轉(zhuǎn)換矩陣對原始點(diǎn)云的轉(zhuǎn)換結(jié)果。

圖4 點(diǎn)云匹配時效性分析

點(diǎn)云匹配實驗中點(diǎn)云匹配時間如表1所示。

表1 點(diǎn)云匹配時間統(tǒng)計

通過表1的結(jié)果，作出基于加權(quán)距離投票的點(diǎn)云匹配算法的時間-點(diǎn)數(shù)曲線擬合，結(jié)果如圖5所示。

圖5 點(diǎn)云匹配時間-點(diǎn)數(shù)曲線圖

由圖5所示的實驗數(shù)據(jù)所擬合的點(diǎn)云匹配算法的時間-點(diǎn)數(shù)曲線為：

式中，為匹配時間，為點(diǎn)云數(shù)目。擬合結(jié)果見表2。

表2 擬合結(jié)果準(zhǔn)確性分析

由圖5 可知，當(dāng)點(diǎn)數(shù)在30 以內(nèi)時，時間隨點(diǎn)的個數(shù)增加速度平緩，且由式（3）可知，此時匹配算法耗時在0.011 s 以內(nèi)，滿足算法的實時性要求。

3.2 算法匹配準(zhǔn)確性分析

匹配算法的時效性實驗中，實驗結(jié)果充分證明了匹配算法在點(diǎn)云數(shù)據(jù)理想時是有效的。但在實際部件位姿調(diào)整過程中，由于雙目相機(jī)的視角變化、測量環(huán)境的變化及標(biāo)志點(diǎn)測量算法發(fā)生退化時，會造成部件表面標(biāo)志點(diǎn)點(diǎn)云測量數(shù)據(jù)的測量誤差，所以有必要驗證在點(diǎn)云數(shù)據(jù)質(zhì)量差時，本文點(diǎn)云匹配算法的有效性。

如圖6 所示，由于標(biāo)志點(diǎn)空間位置測量時，必然存在一定的測量誤差，故實驗驗證時，首先給定一組柱面模擬點(diǎn)云數(shù)據(jù)1，給數(shù)據(jù)1 中每一點(diǎn)疊加測量誤差，得到柱面模擬點(diǎn)云數(shù)據(jù)2，對點(diǎn)云數(shù)據(jù)1 進(jìn)行剛體變換后同樣疊加測量誤差，得到點(diǎn)云數(shù)據(jù)3；其中點(diǎn)云數(shù)據(jù)1 為標(biāo)志點(diǎn)的理論空間位置，點(diǎn)云數(shù)據(jù)2、點(diǎn)云數(shù)據(jù)3 為理論標(biāo)志點(diǎn)云在不同視角下的觀測值。此時以點(diǎn)云數(shù)據(jù)2及點(diǎn)云數(shù)據(jù)3進(jìn)行點(diǎn)云匹配模擬實驗。

圖6 測量誤差示意圖

如圖7所示，部件對接工況下，在部件位姿調(diào)整過程中，由于雙目相機(jī)的視角變化、標(biāo)志點(diǎn)的遮擋及標(biāo)志點(diǎn)檢測算法發(fā)生退化會造成部件表面點(diǎn)云數(shù)據(jù)的不完整，此時待匹配局部點(diǎn)云只有部分重疊。故在實驗時，通過將不同視角下的測量點(diǎn)云中各自獨(dú)立刪除部分空間點(diǎn)進(jìn)行模擬實驗。

圖7 部分重疊示意圖

由時效性分析實驗可知，當(dāng)匹配點(diǎn)云中待匹配點(diǎn)數(shù)在30 以內(nèi)時，距離投票算法耗時在0.011 s 內(nèi)，可滿足追蹤算法的實時性要求，故實驗考慮在30 點(diǎn)以內(nèi)的點(diǎn)云匹配問題，部分實驗如圖8所示。

圖8 非完整點(diǎn)云匹配結(jié)果

由表3可知，本文提出的基于加權(quán)距離投票的點(diǎn)云匹配算法，在仿真點(diǎn)云存在測量誤差及點(diǎn)云數(shù)據(jù)不完整的情況下是可靠的。

表3 非完整點(diǎn)云匹配結(jié)果

續(xù)表3

4 結(jié)語

本文給出了基于加權(quán)距離投票的點(diǎn)云匹配算法，從時效性和匹配準(zhǔn)確性兩方面對算法進(jìn)行分析，分析結(jié)果顯示算法滿足實時性要求，在仿真點(diǎn)云存在測量誤差及點(diǎn)云數(shù)據(jù)不完整的情況下，點(diǎn)云匹配算法是可靠的。該算法可以解決點(diǎn)云匹配過程中的一些相關(guān)問題，具有一定的實際意義。