基于加權運動平均的多視角點云魯棒配準方法

劉海濤，黃玉庚，肖聚亮，岳?巍

基于加權運動平均的多視角點云魯棒配準方法

劉海濤，黃玉庚，肖聚亮，岳?巍

(天津大學機構理論與裝備設計教育部重點實驗室，天津 300354)

本文提出一種基于加權運動平均的多視角點云配準方法，有效提高了多視角點云配準的效率和精度. 首先，通過雙視角點云配準算法得到點集的相對運動集；提出一種分層漸進式點云配準初值確定方法，該方法計算運動關系圖中三視匹配元一致性度量，逐步挑選最為可靠的匹配元進行頂點初值化與頂點擴展，有效避免了因所選初值與真值偏差較大導致加權運動平均效果不佳的問題；依據上述方法確定配準初值，并根據該初值判斷雙視角匹配結果的可靠性，以剔除相對運動集內包含的外點，最后將剔除外點后的原始相對運動集的內點子集作為加權運動平均算法輸入的相對運動集. 以斯坦福公開數據集為對象開展了對比實驗，基于雙視角配準算法分別獲得了4個測試點集在30%、25%和20%雙視角點云重疊率閾值下的雙視角配準結果，共形成12組相對運動集. 其中，相對運動集誤差隨重疊率閾值的下降逐漸增加. 所提方法在12組運動集上均獲得了最佳的配準結果，證明了本文所提出方法在提高加權運動平均方法計算精度與效率方面的有效性. 此外，當運動集包含大量外點時，采用本文所提方法仍能獲得較為準確的配準結果，證明了本文所提方法的強魯棒性.

多視角點云配準；加權運動平均；回環(huán)一致性；分層漸進

點云配準在工業(yè)測量、計算機視覺和機器人移動建圖等領域應用廣泛[1-2]．根據待配準點集中點云的幀數，點云配準問題可分為兩類：雙視角點云配準與多視角點云配準問題．

雙視角點云配準是實現多視角點云配準的基礎.近幾十年內，相關學者對該問題進行了廣泛研究，并提出一系列配準方法．其中，文獻[3]提出的迭代最近點(iterative closest point，ICP)算法及其衍生算法最為常用．該方法基于迭代求解思想，可實現剛體的有效配準．然而，當雙幀點云僅部分區(qū)域重疊時，ICP算法失效．為了解決上述問題，文獻[4]提出了裁剪ICP(trimmed iterative closest point，TrICP)算法，其在ICP算法的基礎上引入重疊百分比參數，通過去除非重疊區(qū)域，得到雙視角點云的準確配準結果．

多視角點云配準的目標是計算點集中各幀點云和基準點云之間的剛體變換矩陣，繼而將物體或環(huán)境中多個視角掃描測量得到的點云映射到全局坐標系中[2]．為了解決多視角配準問題，Govindu等[5]首次提出了基于運動平均算法的多視角點云配準方法，該方法將所有可獲得的雙視角點云配準結果作為輸入，并借助李代數平均算法計算各變換矩陣．值得指出的是，運動平均算法雖然可作為解決多視角點云配準問題的有效手段，但沒有考慮每個雙視角匹配結果的可靠性和準確性．為了避免上述問題，Guo等[6]通過TrICP算法計算雙視角點云的重疊百分比，并將其視為每個匹配對的權重，提出了加權運動平均方法．該方法可在一定程度上提高運動平均算法的有效性和魯棒性．然而，考慮到TrICP算法易陷入局部最優(yōu)，因此，借助該算法衡量的重疊百分比的準確性無法保證[7]．此外，Li等[7]基于低秩稀疏矩陣分解算法提出了一種自適應加權運動平均方法，利用拉格朗日乘子計算每個相對運動的權重．

雖然基于運動平均算法的配準方法能夠有效解決多視角點云配準問題，但需要指出的是，運動平均算法實質為高斯牛頓迭代法，即通過多次迭代計算問題的加權最小二乘解．當給定初值偏離全局最優(yōu)解時，算法容易陷入局部最優(yōu)，因此，上述算法依賴于良好的配準初值．運動平均算法中用于計算配準初值的方法主要包括廣度搜索生成樹方法和低秩稀疏矩陣分解(low-rank and sparse decomposition，LRS)方法[8]．其中，廣度搜索生成樹方法將其中某一幀點云視為基礎幀，以此作為基點進行廣度搜索．該方法原理簡單，然而當相對運動集中包含大量外點時，無法確保遍歷的雙視角匹配結果的可靠性；LRS算法雖然能夠在相對運動集中包含外點的情況下得到較好的配準初值，但其精度容易受到圖的稀疏性影響．綜上所述，盡管現有方法能夠求解點云配準初值，但相關算法的精度還有待進一步提高．

1?加權運動平均及其初值問題

圖1?點集的相對運動與全局運動關系

Fig.1　　Representation of relative and global motions of data set

若忽略式(9)和式(10)中的一階小量，進一步可得

將式(11)代入式(8)中，有

將式(14)改寫為矩陣形式，即

2?魯棒多視角點云配準方法

2.1?三視匹配元一致性度量

2.2?基于三視匹配元一致性度量的初值確定方法

2.2.2?初值確定方法流程

鑒于加權運動平均算法的有效性依賴于良好的迭代初值，而合理的初值確定方式是有效避開運動關系視圖中的外點，故本節(jié)提出了基于三視匹配元一致性度量的多視角點云配準初值確定方法，其核心思想是：在初始化階段，逐步添加最可靠的三視匹配元，以運動關系視圖中連通分量度數最大的頂點對應的點云作為基礎幀點云；在擴展階段，基于已確定初值的頂點不斷擴展，直至確定所有頂點的初值．算法可分為如下3個步驟．

步驟1 頂點初始化．

圖2?本文方法步驟1示意

步驟2 頂點擴展．

圖3?本文方法步驟2的示意

給定無序多視角點集，利用上述方法可獲得較為精準的配準初值．算法1給出了本文所提方法的整體流程．與基于生成樹的方法不同，本文所提方法在頂點的擴展過程中引入了三視匹配元一致性度量，以度數最大的頂點作為基頂點，而非默認將點集的第1幀或任意幀作為基礎幀，且采用分層增量的方法進行頂點的擴展，降低了外點的影響并有效減小了累積誤差．算法1偽代碼如下．

算法1?漸進式點云配準初值確定方法

repeat

repeat

end for

end while

2.3?外點剔除

由第1節(jié)可知，相對運動集易受到外點的污染，因此根據第2.2節(jié)所提方法確定配準初值后，為了獲得更為精確的內點集合，本節(jié)進一步設計用于篩選內點的準則．

綜上，結合第2.2節(jié)提出的初值確定方法，算法2示出了本文所提魯棒運動平均方法的整體流程．此外，本文權重因子可根據文獻[9]提出的方法確定，限于篇幅，不再贅述．算法2的偽代碼如下．

算法2?基于加權運動平均的多視角點云魯棒配準方法

end for

end for．

repeat

end for

3?實驗與結果分析

本文利用斯坦福公開數據集[14]測試所提出方法的精度和效率，以驗證其有效性與魯棒性．在斯坦福數據集中共選取了Armadillo、Buddha、Bunny、Dragon 4個點集作為實驗對象，其點云幀數分別為12、15、10、15，圖4示出了未進行配準前4個數據集的三維點云．

圖4?4個數據集未進行配準前的三維模型

為體現本文所提方法的優(yōu)勢，將其與文獻[9]、文獻[5]提出的運動平均方法和文獻[8]提出的低秩稀疏矩陣分解方法(分別簡記為WMA、MA、LRS)進行比較．此外，為揭示配準初值對運動平均方法的影響，本文以LRS方法和本文所提出的漸進式配準初值確定方法(簡記為OurInit)得到的結果分別作為MA、WMA算法的輸入進行對比實驗．其中，LRS方法的源代碼作者已提供，其采用MATLAB編程實現，其余方法均采用C++編程實現，所有實驗程序均在RAM為16GB、主頻為2.90GHz的16核筆記本電腦上運行．

3.1?精度與效率對比實驗

為比較不同配準方法的性能，進行了對比實驗．首先選取4個點集中30%重疊率閾值下的雙幀點云，并進行配準，以獲得作為配準算法輸入的相對運動集結果．表1給出了各個測試點集對應相對運動集的匹配對數量、旋轉誤差和平移誤差．表2給出了采用不同配準方法配準4個測試點集時的旋轉、平移誤差以及耗時的比較結果．為進一步對比不同方法的精度，圖5采用橫截面的形式示出了各種方法的配準結果，其中，MA-LRS、MA-OurInit分別表示采用MA算法以LRS和本文所提初值確定方法作為初值時的配準結果，同理，WMA-LRS、WMA-OurInit表示采用WMA算法以LRS和本文所提初值確定方法作為初值時的配準結果．圖6為采用本文所提初值確定方法對Dragon數據集進行初值確定的過程示意.

表1在30%重疊率閾值下的匹配對配準結果組成的相對運動集的誤差統(tǒng)計結果和匹配對數量

Tab.1　　Error statistics information and the number of relative motions consisted of the pair-wise regis-trations of scan pairs with 30% overlap percentage threshold

表2?不同配準方法在測試點集上的配準誤差與運行時間對比結果

Tab.2?Registration errors and runtimes of different multi-view registration methods on four data sets

圖5?以橫截面形式呈現的不同配準方法在4個測試點集上的配準結果對比

圖6?在30%重疊率閾值下本文所提初值確定方法對Dragon數據集進行初值確定的過程示意

由表2可知，相較于LRS方法，采用本文方法確定的初值旋轉誤差與平均誤差均為最小，說明所提初值確定算法具有較好的精度．LRS方法精度不高的解釋如下：LRS方法采用低秩稀疏矩陣分解進行全局運動求解，但由于點云配準問題中部分點云的重疊百分比較低，導致圖較為稀疏，從而導致LRS方法精度受限[8]．本文方法則依賴于三視匹配元一致性度量進行頂點的擴展，因此，圖中存在一致性較好的匹配元是保證本文算法精度的前提．值得指出的是，在實際應用中，因為表面遮擋與掃描面積的局限，為了獲得物體的表面完整的三維點云需要對被測物體進行多個視角的掃描，這便有效地滿足了上述前提．

結合表1和表2可見，MA算法的精度最差，因為該算法把不可靠和可靠的匹配對配準結果均賦予相同的權重，因此，在相對運動集包含較多外點的情況下，MA算法無法保證算法的精度．較于WMA方法，本文所提方法的配準精度更高．因為盡管本文所提方法的核心與WMA和MA兩種方法一致，均采用高斯牛頓迭代法求解，但本文方法精確地確定了配準初值，并剔除了外點，因此實際上該算法的輸入并非包含大量外點的相對運動集，而是其內點子集，從而提高了多視角點云配準結果的精度．值得指出的是，本文基于三視匹配元一致性不斷進行頂點的擴展，即所有擴展的邊與頂點組成的圖是連通的，因此作為算法輸入的內點集合中各幀點云之間均存在有效關聯．

3.2?配準算法的魯棒性實驗與初值影響對比實驗

為說明本文所提方法的魯棒性并揭示不同初值對配準算法的影響，本文在不同重疊率閾值下進行了對比實驗．首先對4個點集中重疊率分別大于25%、20%的雙幀點云進行配準，以此獲得對比實驗的相對運動集．表3和表4分別給出了不同重疊率閾值下各個測試點集對應的相對運動集的匹配對數量、旋轉誤差和平移誤差．結合表1可見，隨著重疊率的下降，測試點集對應的相對運動集中的誤差逐增，說明運動集中受外點污染的程度也隨著重疊率的下降不斷增加．表5和表6分別示出了采用不同配準方法以上述相對運動集作為輸入配準點集時的旋轉、平移誤差以及耗時的比較結果．

表3在25%重疊率閾值下的匹配對配準結果組成的相對運動集的誤差統(tǒng)計結果和匹配對數量

Tab.3　　Error statistics information and the number of relative motions consisted of the pair-wise regis-trations of scan pairs with 25% overlap percentage threshold

表4在20%重疊率閾值下的匹配對配準結果組成的相對運動集的誤差統(tǒng)計結果和匹配對數量

Tab.4　　Error statistics information and the number of rela-tive motions consisted of the pair-wise registrations of scan pairs with 20% overlap percentage threshold

為說明初值對運動平均方法的影響和本文方法的高效性與魯棒性，圖7示出了不同重疊率下WMA-LRS、WMA-OurInit、OurInit和本文所提配準方法對Buddha(25%重疊率閾值)和Dragon(20%重疊率閾值)點集進行配準后的距離誤差映射圖．

結合表2、表5和表6示出的各種配準算法在不同重疊率下的實驗結果對比可知，隨著相對運動集中受外點污染程度的增加，LRS和MA方法獲得的配準結果越發(fā)偏離真實值，其原因在于，MA方法對不可靠的匹配結果極其敏感，即使相對運動集中存在一個外點也可能導致MA方法配準失敗[17]．相比于MA方法，LRS方法對不可靠的匹配結果較為魯棒[17]，但在Buddha、Dragon測試點集上的配準結果表明，隨著不可靠匹配結果的增加，LRS方法的精度將不斷下降，甚至導致配準失敗．

表5?不同配準方法在25%重疊率閾值下對測試點集進行配準后的配準誤差與運行時間對比結果

Tab.5?Registration errors and runtimes of different multi-view registration methods on four data sets with 25% overlap percentage threshold

表6?不同配準方法在20%重疊率閾值下對測試點集進行配準后的配準誤差與運行時間對比結果

Tab.6?Registration errors and runtimes of different multi-view registration methods on four data sets with 20% overlap percentage threshold

圖7　　不同方法在Buddha測試集(25%重疊率閾值)和Dragon測試集(20%重疊率閾值)上的距離誤差映射圖

結合表2、表5、表6與圖7可知，盡管相對運動集中包含大量外點，對于4個測試點集，本文所提初值確定方法和最終配準方法均能獲得最佳和次之的配準結果．因此，在不同重疊率閾值下的對比實驗結果證明了本文方法的魯棒性和有效性．值得指出的是，隨著相對運動集中匹配對數量的不斷增加，本文所提初值確定方法程序運行時間并無明顯的增加．表5和表6中的Dragon實驗結果表明，隨著匹配對數量的增加，本文所提初值確定方法求解程序的運行時間有所減少，且所確定的初值相比于最終運動平均方法獲得的配準結果精度更高．為了揭示該現象產生的原因，圖8所示為在20%重疊率閾值下采用本文所提初值確定方法對Dragon數據集進行初值確定的過程示意．對比圖6示出的30%重疊率閾值下的頂點擴展的順序圖可知，盡管在20%閾值下，(0，3)、(0，12)、(2，12)等匹配對的重疊率較低，其仍能獲得較佳的配準結果．于是在匹配對(0，3)與(2，3)的關聯下，頂點3在第2輪頂點擴展時便已確定初值，無需進行第3輪擴展，且在(0，12)、(2，12)等匹配對的作用下，連通塊的聯結性更強，從而導致20%重疊率閾值下所提出方法實驗結果的精度高于30%重疊率閾值下的實驗結果．綜上，本文提出的初值確定方法能基于三視匹配元一致性度量隱性地剔除相對運動集中不可靠的匹配結果，因此，盡管隨著重疊率的下降，本文所提初值確定方法依舊能在一定程度上依賴三視匹配元一致性度量篩選出具有低重疊率而匹配結果可靠的匹配對，這也從側面揭示了重疊率并非是決定匹配對配準結果準確性的唯一因素，亦揭示了本文基于三視匹配元漸進式進行初值確定方法的有效性與魯棒性．

圖8?在20%重疊率閾值下本文所提初值確定方法對Dragon數據集進行初值確定的過程示意

由表2可見，在30%的重疊率閾值下，盡管OurInit相比于LRS方法精度更高，但WMA-OurInit的配準結果精度與WMA-LRS相比并無明顯提高，而WMA-OurInit的效率甚至比WMA-LRS的效率低．導致WMA-OurInit方法效率較低的原因在于，OurInit的配準結果比WMA更接近真實值，即WMA-OurInit需要進行更多次迭代才能收斂到當前輸入下WMA算法收斂得到的結果．WMA-OurInit算法精度無明顯提高的原因在于，與25%重疊率閾值相比，在30%的重疊率閾值下，相對運動集中包含的外點數量較少，而WMA算法本身對初值選取和外點具有較好魯棒性[9]．對比表5、表6與圖7可知，隨著相對運動集中外點數量的不斷增加，相比于WMA-LRS，WMA-OurInit的精度、效率得到了顯著提升．這是由于隨著外點數量的增加，LRS的配準結果越發(fā)偏離真實值，以LRS配準結果作為輸入初值的WMA-LRS算法權重因子被錯誤地衡量，這將導致權重因子無法真實反映出雙視角匹配結果的可靠性，進一步導致精度降低甚至配準失敗．較于LRS方法，由于OurInit的結果更接近于真實值，因此，WMA-OurInit算法在相對運動集存在較多外點的情況下依舊能獲得較為準確的配準結果，這進一步佐證了本文所提方法的準確性與魯棒性．

4?結?論

本文提出了一種多視角點云魯棒配準方法，給出了方法詳細的實現步驟，得到如下結論．

(2) 在獲得配準初值的基礎上，借助內點篩選準則，提出一種基于加權運動平均的多視角點云魯棒配準方法．以斯坦福公開數據集為對象開展了對比實驗，不同重疊率閾值下的對比實驗結果表明：針對在30%、25%、20% 3種不同重疊率閾值下的相對運動集，本文所提方法均能獲得較好的配準結果，證明了本文所提出方法的有效性與魯棒性．

［1］ 張劍清，鄭?莉. 基于結構光的不規(guī)則工業(yè)鈑金件三維曲面重建[J]. 地理空間信息，2004(6)：9-10，19.

Zhang Jianqing，Zheng Li. 3D surface reconstruction of irregular industrial sheetmetal parts based on structure illumination[J]. Geospatial Information，2004(6)：9-10，19(in Chinese).

［2］ 徐思雨，祝繼華，姜祖濤，等. 無序多視角點云的自主配準方法[J]. 西安交通大學學報，2018，52(11)：134-141.

Xu Siyu，Zhu Jihua，Jiang Zutao，et al. An automatic approach for multi-view registration of unordered range scans[J]. Journal of Xi’an Jiaotong University，2018，52(11)：134-141(in Chinese).

［3］ Besl P J，Mckay H D. A method for registration of 3-D shapes[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence，1992，14(2)：239-256.

［4］ Chetverikov D，Stepanov D，Krsek P. Robust Euclidean alignment of 3D point sets：The trimmed iterative closest point algorithm[J]. Image and Vision Comput-ing，2005，23(3)：299-309.

［5］ Govindu V M，Pooja A. On averaging multiview relations for 3D scan registration[J]. IEEE Transactions on Image Processing，2013，23(3)：1289-1302.

［6］ Guo R，Zhu J，Li Y，et al. Weighted motion averaging for the registration of multi-view range scans[J]. Multimedia Tools and Applications，2018，77(9)：10651-10668.

［7］ Li Z，Liu J，Tian Z，et al. Adaptive weighted motion averaging with low-rank sparse for robust multi-view registration[J]. Neurocomputing，2020，413：230-239.

［8］ Arrigoni F，Rossi B，Fusiello A. Global registration of 3D point sets via LRS decomposition[C]// 14th European Conference on Computer Vision. Berlin，Germany，2016：489-504.

［9］ Zhu J，Hu J，Lu H，et al. Robust motion averaging under maximum correntropy criterion[C]//2021 IEEE International Conference on Robotics and Automation (ICRA). New York，USA，2021：5283-5288.

［10］ 于靖軍，劉辛軍，丁希侖，等. 機器人機構學的數學基礎[M]. 北京：機械工業(yè)出版社，2008.

Yu Jingjun，Liu Xinjun，Ding Xilun，et al. Mathematic Foundation of Mechanisms and Robotics[M]. Beijing：China Machine Press，2008(in Chinese).

［11］ Barfoot T D. State Estimation for Robotics[M]. Cambridge：Cambridge University Press，2017.

［12］ Zach C，Klopschitz M，Pollefeys M. Disambiguating visual relations using loop constraints[C]// 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Los Alamitos，USA，2010：1426-1433.

［13］ Hartley R，Aftab K，Trumpf J. L1 rotation averaging using the Weiszfeld algorithm[C]//24th IEEE Conference on Computer Vision and Pattern Recognition. New York，USA，2011：3041-3048.

［14］ Turk G，Levoy M. Zippered polygon meshes from range images[C]// Proceedings of the 21st Annual Conference on Computer Graphics and Interactive Techniques. New York，USA，1994：311-318.

［15］ Li Z，Zhu J，Lan K，et al. Improved techniques for multi-view registration with motion averaging[C]// 2014 2nd International Conference on 3D Vision. New York，USA，2014：713-719.

［16］ Lei H，Jiang G，Quan L. Fast descriptors and correspondence propagation for robust global point cloud registration[J]. IEEE Transactions on Image Processing，2017，26(8)：3614-3623.

［17］ Zhu J，Guo R，Li Z，et al. Registration of multi-view point sets under the perspective of expectation-maximization[J]. IEEE Transactions on Image Processing，2020，29：9176-9189.

Robust Approach for the Registration of Multi-View Point Sets Based on Weighted Motion Averaging

Liu Haitao，Huang Yugeng，Xiao Juliang，Yue Wei

(Key Laboratory of Mechanism Theory and Equipment Design of Ministry of Education，Tianjin University，Tianjin 300354，China)

This study proposes a method for improving the registration performance of multi-view point sets based on weighted motion averaging. First，the relative motions of scans is estimated utilizing a pair-wise registration algorithm. Subsequently，a novel method for hierarchically estimating the initial global motions using the cycle consistency of triplets was described. This method calculates the consistency of all triplets in the view-graph of motions and gradually selects the reliable triplets for the initialization and expansion of nodes，avoiding the failures of motion averaging caused by improper initialization. With access to the accurate initial global motions，it filters outlier edges by evaluating the reliability of pair-wise registration results. Therefore，the final relative motions，as the input to the algorithm for weighted motion averaging，is the inlier subset of the initial relative motions. A comparative experiment was performed on the Stanford 3D scanning repository. Using the pair-wise registration algorithm，we obtain 12 relative motions for four range scans with overlap percentage thresholds of 30%，25%，and 20%. Among these，the error in relative motions increases when the overlap percentage threshold is decreased. The experimental results on these relative motions demonstrate that the proposed method improves the performance and robustness of the weighted motion averaging algorithm for multi-view registration. Experimental results reveal that the proposed method can obtain accurate registration results even when the set of the relative motions contains a high number of outliers，which verified the robustness of our method.

multi-view point sets registration；weighted motion averaging；cycle consistency；hierarchy

10.11784/tdxbz202202007

TP391

A

0493-2137(2023)07-0690-12

2022-02-14；

2022-05-16.

劉海濤（1981—??），男，博士，教授.

劉海濤，liuht@tju.edu.cn.

國家自然科學基金資助項目(91948301).

Supported by the National Natural Science Foundation of China(No. 91948301).

(責任編輯：王曉燕)