李 準(zhǔn)，潘幸子，孫水發(fā),2，李 娜,2

(1. 三峽大學(xué) 水電工程智能視覺監(jiān)測湖北省重點實驗室，湖北 宜昌 443002；2. 南京師范大學(xué) 江蘇省三維打印裝備與制造重點實驗室,江蘇 南京 210042)

?

三維點云配準(zhǔn)約束條件綜述

李 準(zhǔn)1，潘幸子1，孫水發(fā)1,2，李 娜1,2

(1. 三峽大學(xué) 水電工程智能視覺監(jiān)測湖北省重點實驗室，湖北 宜昌 443002；2. 南京師范大學(xué) 江蘇省三維打印裝備與制造重點實驗室,江蘇 南京 210042)

點云配準(zhǔn)是通過匹配具有重疊部分的數(shù)據(jù)集，將不同坐標(biāo)下的三維數(shù)據(jù)集變換到同一坐標(biāo)系下，得到旋轉(zhuǎn)變換矩陣和平移向量。通過各種約束條件，建立適當(dāng)?shù)哪Ｐ汀傂耘錅?zhǔn)在變換過程中不會發(fā)生形變，而非剛性配準(zhǔn)需要考慮形變等問題。剛性配準(zhǔn)和非剛性配準(zhǔn)在約束條件上有所不同，文章從特征、顯著性、正則化等約束條件，對剛性和非剛性配準(zhǔn)約束條件進行了研究討論。

配準(zhǔn)；剛性；非剛性；形變；約束

0 引言

點云配準(zhǔn)是通過匹配具有重疊部分的數(shù)據(jù)集，尋求不同數(shù)據(jù)集之間的一致性對應(yīng)關(guān)系，將不同坐標(biāo)系下的三維數(shù)據(jù)集變換到同一坐標(biāo)系下，最終得到被掃描物體的完整點云集。但在現(xiàn)實應(yīng)用中，由于三維掃描技術(shù)的局限性，不同的數(shù)據(jù)集通常是從不同的觀測點獲取，每一個觀測點都處在不同的坐標(biāo)系下，因此表面配準(zhǔn)是三維數(shù)據(jù)獲取的重要部分，也是計算機視覺[1]、計算機圖形學(xué)[2]等的基礎(chǔ)。點云配準(zhǔn)分為剛性配準(zhǔn)和非剛性配準(zhǔn)。剛性配準(zhǔn)，即被掃描物體不發(fā)生形變等變化；非剛性變換允許被掃描物體發(fā)生諸如形變、清晰度等變化。

剛性配準(zhǔn)，在數(shù)據(jù)的采集過程中會遇到很多困難，包括噪聲、離群點和數(shù)量有限的重疊部分等情況；非剛性配準(zhǔn)不僅要克服剛性配準(zhǔn)的各種問題，還要考慮被掃描物體的形變等問題，非剛性配準(zhǔn)通常缺乏足夠的一致性對應(yīng)關(guān)系，所以需要定義更多可靠的一致性對應(yīng)信息進行配準(zhǔn)。

隨著三維激光點云掃描技術(shù)與點云數(shù)據(jù)處理技術(shù)的不斷進步，不論是剛性配準(zhǔn)還是非剛性配準(zhǔn)，都可以通過建立適當(dāng)?shù)募s束條件加以解決。

1 剛性配準(zhǔn)

剛性變換中，以尋求滿足N個數(shù)據(jù)點的旋轉(zhuǎn)矩陣R以及平移向量t組成的剛體變換為目標(biāo)，對于兩片具有重疊部分的不同點云集P和Q，使其滿足qi=Rpi+t。其中，pi為點云集P上任意點，qi為pi在點云集Q的對應(yīng)點。對于剛性配準(zhǔn)的各種算法，大都是通過各種約束條件，建立配準(zhǔn)算法模型。下面對剛性配準(zhǔn)約束條件進行研究討論。

1.1 變換約束

最近點準(zhǔn)則可以約束潛在的一致性對應(yīng)。該方法是在一個剛體變換中，選取最近點qi∈Q作為pi的匹配，以完成最終配準(zhǔn)。在標(biāo)準(zhǔn)迭代最近點算法ICP中，通過最小化函數(shù)

(1)

進行約束。迭代最近點算法對于初始化要求較高，并且在每一次迭代時更新旋轉(zhuǎn)矩陣R和平移矩陣t。由于ICP算法的良好性能，眾多學(xué)者在此基礎(chǔ)上提出了很多改進算法來提高計算速度以及魯棒性。

1.2 特征約束

剛性變換中，不同視角下被掃描物體曲面幾何特性保持不變。常用的幾何特征如曲率、法矢量等，多種不同的特征可以形成一個特征向量。由于特征維度越高匹配所有特征的概率越低，所以高維特征向量能夠簡化數(shù)據(jù)。但此類方法要求被掃描物體特征較明顯且容易提取，并且在特征提取過程中會花費較多的時間。KASE K等人[3]使用擴展高斯曲率和一個匹配率方程來判斷對應(yīng)點集之間的差異，擴展高斯曲率定義為：

ε=|(k1(pi)-k1(qi))·(k2(pi)-k2(qi))|

(2)

其中pi與qi為不同點云集的對應(yīng)點，k1、k2為主曲率。在配準(zhǔn)過程中通過提取包括旋轉(zhuǎn)圖像、平均曲率等特征，可以極大地簡化數(shù)據(jù)量，從而提高配準(zhǔn)效率。

1.3 顯著性約束

顯著性區(qū)域是一些與其附近區(qū)域性質(zhì)具有很明顯差異的區(qū)域。顯著性可以用來衡量物體表面的局部信息，以及完成對關(guān)鍵點或關(guān)鍵區(qū)域的檢測。在剛性配準(zhǔn)中，顯著性通常與特征結(jié)合在一起來減少對應(yīng)關(guān)系的空間以及潛在的不匹配性，最終獲得更可靠一致性對應(yīng)以完成配準(zhǔn)。常用的顯著性措施包括：幾何尺度空間分析、基于視覺顯著性的尺度和曲率、多尺度滑動和最大穩(wěn)定域極值等。

1.4 正則化約束

正則化通過對目標(biāo)函數(shù)增加懲罰項來進行約束。正則化約束包含先驗信息，在優(yōu)化時避免了局部最小值的出現(xiàn)，提高了搜索效率。GOLD S和RANGARAJAN A[4]將剛性配準(zhǔn)作為一個連續(xù)優(yōu)化問題，同時處理剛性變換和一致性對應(yīng)。該方法基于最近點準(zhǔn)則，定義基于熵的正則化項：

-∑i∑jMijlogMij

(3)

其中，M是所有一致性對應(yīng)的潛在匹配矩陣。由熵的定義可知，當(dāng)所有的點匹配是等可能的，熵達到最大值。該方法有助于目標(biāo)函數(shù)對錯誤表面的分解。

1.5 搜索約束

搜索約束主要針對配準(zhǔn)效率，包括局部化方法和分層搜索的方法。JOST T等人[5]進一步結(jié)合上述由粗到精等級搜索技術(shù)，使用下采樣技術(shù)加快ICP的迭代速度，該方法逐步細化以至得到更可靠的一致性對應(yīng)。Krsek對表面結(jié)構(gòu)特征進行分層，該方法根據(jù)一些顯著點估計歐式變換，然后利用曲率和表面重新定義變換。

對于剛性配準(zhǔn)，從剛性變換、特征、顯著性、正則化和搜索約束進行了研究討論，眾多學(xué)者以此解決了點云的剛性配準(zhǔn)。

2 非剛性配準(zhǔn)

非剛性配準(zhǔn)涉及形變等因素，在表現(xiàn)形式上與剛性變換有所不同。MITRA N J等人[6]提出時空位移模型：

(4)

其中，(Rj,tj)是旋轉(zhuǎn)和平移變換，τj是沿時間軸的變換，上述變換在時空域里連續(xù)的j幀數(shù)據(jù)是一致的，但該方法需要在時域和空域密集地采樣。下面對非剛性變換約束進行研究討論。

2.1 形變約束

d(x,y)2=∑kΩ(λk)(Φk(x)-Φk(y))2

(5)

2.2 特征約束

諸如旋轉(zhuǎn)圖像、平均曲率、積分描述符等特征一直應(yīng)用于求取非剛性配準(zhǔn)一致性對應(yīng)。Sun基于熱擴散點提出熱內(nèi)核簽名，該方法具有等距不變特性、多尺度、多信息和穩(wěn)定等特點。Me′moli通過Gromov-Wasserstein距離，關(guān)聯(lián)并重新解釋HKS與其他的光譜形狀配準(zhǔn)技術(shù)。經(jīng)眾多學(xué)者研究發(fā)展，HKS的變式相繼被提出，Bronstein和Kokkinos使用傅里葉變換避免尺度差異，并定義了尺度不變形式的熱內(nèi)核簽名。

2.3 顯著性約束

與剛性變換中的顯著性約束類似，在非剛性變換中也可以將顯著性應(yīng)用于配準(zhǔn)。KIM V G等人[7]使用形變不變函數(shù)的極值，利用積分測地距離G(p)=∫s∈Pdg(p,s)dP定義顯著點。如果p距離其他網(wǎng)格較遠，G(p)較大，該方法對于表面的細節(jié)變化具有穩(wěn)定性。LITMAN R等人[8]利用最大穩(wěn)定極值區(qū)域檢測非剛性外形穩(wěn)定區(qū)域。

2.4 正則化約束

(6)

LIH等人避免了遮擋造成的空洞影響，最小化：

(7)

2.5 運動包絡(luò)約束

由于運動包絡(luò)是由點的軌道線垂直于其法線場，點云集的一致性對應(yīng)可以由時空表面計算得到。MITRA N J在剛性和非剛性校正中考慮到時空表面，利用瞬時運動學(xué)定義最小化速度場和法線場數(shù)量積。對于非剛性校正，進行下采樣，并計算局部瞬時時空速度，使用正則化將得到的計算結(jié)果應(yīng)用于鄰近點。但時空表面需要非常密集的空間和時間采樣數(shù)據(jù)。

對于非剛性配準(zhǔn)，從形變、特征、顯著性、正則化和運動包絡(luò)約束進行了研究討論，搜索約束與剛性配準(zhǔn)中的類似，在此不加贅述。眾多學(xué)者在此基礎(chǔ)上對非剛性配準(zhǔn)進行了深入的研究探索。

3 結(jié)論

文章陳述了剛性配準(zhǔn)和非剛性配準(zhǔn)的約束條件，通過整合約束條件，建立相應(yīng)的模型，運用計算機可以求解旋轉(zhuǎn)變換和平移向量，以完成點云的配準(zhǔn)。

經(jīng)過眾多學(xué)者的研究，剛性配準(zhǔn)的很多問題已經(jīng)解決。剛性配準(zhǔn)正面向應(yīng)用程序，開發(fā)能夠處理具有不同水平細節(jié)和至關(guān)重要規(guī)律性結(jié)構(gòu)的大型數(shù)據(jù)的剛性配準(zhǔn)技術(shù)，與3D打印聯(lián)系將更緊密。隨著技術(shù)的進步，手持掃描設(shè)備將向小型化、智能化發(fā)展，針對這些無處不在的設(shè)備，實時技術(shù)是一個發(fā)展新方向。

對于非剛性配準(zhǔn)的研究，還處于初始階段。獨立建立極具意義和自然的一致性對應(yīng)，選擇適當(dāng)?shù)淖冃伪硎竞驮u價非剛性方法的適當(dāng)工具是非剛性配準(zhǔn)的兩大難題。由于現(xiàn)實世界中各種各樣的轉(zhuǎn)換，一致性對應(yīng)和先驗信息的缺乏是困擾眾多研究者的難題。隨著點云數(shù)據(jù)處理技術(shù)的不斷進步，具有先驗信息的假設(shè)將日益完善。這些技術(shù)將使非剛性配準(zhǔn)更加成熟。

[1] 陳海松, 李益民, 韓秀清. 基于計算機視覺的高精度圖像拼接[J]. 微型機與應(yīng)用, 2011, 30(15):38-40.

[2] 伍龍華, 黃惠. 點云驅(qū)動的計算機圖形學(xué)綜述[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2015, 27(8):1341-1353.

[3] KASE K, MAKINOUCHI A, NAKAGAWA T. Shape error evaluation method of free-form surfaces[J]. Computer-Aided Design, 1999, 31(8):495-505.

[4] GOLD S, RANGARAJAN A. A graduated assignment algorithm for graph matching[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 1996, 18(4):377-388.

[5] JOST T, HUGLI H. A multi-resolution ICP with heuristic closest point search for fast and robust 3D registration of range images[C].3-D Digital Imaging and Modeling, 2003. 3DIM 2003. Proceedings. Fourth International Conference on. IEEE, 2003: 427-433.

[6] MITRA N J, FL?RY S, OVSJANIKOV M, et al. Dynamic geometry registration[C].Symposium on Geometry Processing. 2007: 173-182.

[7] KIM V G, LIPMAN Y, FUNKHOUSER T. Blended intrinsic maps[C].ACM Transactions on Graphics (TOG). ACM, 2011, 30(4): 76-79.

[8] LITMAN R, BRONSTEIN A M, BRONSTEIN M M. Diffusion-geometric maximally stable component detection in deformable shapes[J]. Computers & Graphics, 2011, 35(3): 549-560.

[9] LI H, ADAMS B, GUIBAS L J, et al. Robust single-view geometry and motion reconstruction[C].ACM Transactions on Graphics (TOG). ACM, 2009, 28(5): 89-97.

Overview of three dimensional point Cloud registration constraints

Li Zhun1，Pan Xingzi1，Sun Shuifa1,2，Li Na1,2

(1. Hubei Key Laboratory of Intelligent Vision Based Monitoring for Hydroelectric Engineering, China Three Gorges University, Yichang 443002, China; 2. Jiangsu Key Laboratory of 3D Printing Equipment and Manufacturing, Nanjing Normal University, Nanjing 210042, China)

Point Cloud registration is to obtain the rotation transformation matrix and the translation vector by matching the data sets with overlapping parts, and transforming the 3D data sets of different coordinates into the same coordinate system. The rigid registration in the transformation process will not be deformed, nonrigid registration need to consider the deformation and other issues. Various constraint conditions can be used to establish the appropriate model. Rigid registration and nonrigid registration are different in the constraint conditions, the paper discusses through the features, significant and regularization.

registration；rigid；nonrigid；deformation；constraint

TP391

A

10.19358/j.issn.1674- 7720.2016.23.003

李準(zhǔn)，潘幸子，孫水發(fā)，等. 三維點云配準(zhǔn)約束條件綜述[J].微型機與應(yīng)用，2016,35(23)：12-14，17.

2016-09-06)

李準(zhǔn)(1992-)，男，碩士研究生，主要研究方向：三維重建。

孫水發(fā)(1977-)，通信作者，男，博士，教授，主要研究方向：圖像處理、計算機視覺。E-mail：watersun@ctgu.edu.cn。