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

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

　　摘要：點(diǎn)云配準(zhǔn)是通過(guò)匹配具有重疊部分的數(shù)據(jù)集，將不同坐標(biāo)下的三維數(shù)據(jù)集變換到同一坐標(biāo)系下，得到旋轉(zhuǎn)變換矩陣和平移向量。通過(guò)各種約束條件，建立適當(dāng)?shù)哪Ｐ汀?a class="innerlink" href="http://www.theprogrammingfactory.com/tags/剛性" title="剛性" target="_blank">剛性配準(zhǔn)在變換過(guò)程中不會(huì)發(fā)生形變，而非剛性配準(zhǔn)需要考慮形變等問(wèn)題。剛性配準(zhǔn)和非剛性配準(zhǔn)在約束條件上有所不同，文章從特征、顯著性、正則化等約束條件，對(duì)剛性和非剛性配準(zhǔn)約束條件進(jìn)行了研究討論。

　　關(guān)鍵詞：配準(zhǔn)；剛性；非剛性；形變；約束

　　中圖分類號(hào)：TP391文獻(xiàn)標(biāo)識(shí)碼：ADOI： 10.19358/j.issn.16747720.2016.23.003

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

0引言

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

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

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

1剛性配準(zhǔn)

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

　　1.1變換約束

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

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

　　1.2特征約束

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

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

　　1.3顯著性約束

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

　　1.4正則化約束

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

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

　　1.5搜索約束

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

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

2非剛性配準(zhǔn)

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

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

　　2.1形變約束

　　非剛性變換中，形變模型本身可能產(chǎn)生約束。設(shè)(M,)為具有度量張量的黎曼流形。拉普拉斯貝特拉米操作符Δ由決定，定義表面距離的形式：

　　其中λk和Φk是Δ的特征值和特征函數(shù)。Bronstein通過(guò)路徑長(zhǎng)度t衡量?jī)蓚€(gè)點(diǎn)的連通程度，定義擴(kuò)散距離Ω(λk)=Fouss基于擴(kuò)散距離規(guī)模不變的形式，定義的交換時(shí)間距離

　　2.2特征約束

　　諸如旋轉(zhuǎn)圖像、平均曲率、積分描述符等特征一直應(yīng)用于求取非剛性配準(zhǔn)一致性對(duì)應(yīng)。Sun基于熱擴(kuò)散點(diǎn)提出熱內(nèi)核簽名，該方法具有等距不變特性、多尺度、多信息和穩(wěn)定等特點(diǎn)。Me′moli通過(guò)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ù)的極值，利用積分測(cè)地距離定義顯著點(diǎn)。如果p距離其他網(wǎng)格較遠(yuǎn)，G(p)較大，該方法對(duì)于表面的細(xì)節(jié)變化具有穩(wěn)定性。LITMAN R等人［8］利用最大穩(wěn)定極值區(qū)域檢測(cè)非剛性外形穩(wěn)定區(qū)域。

　　2.4正則化約束

　　在非剛性配準(zhǔn)中，物體表面具有更多的高頻信息，為保護(hù)形變時(shí)的細(xì)節(jié)清晰度等信息，往往需要更多的自由度來(lái)描述物體的形變。但過(guò)多的自由度會(huì)產(chǎn)生不必要的噪聲，大多數(shù)非剛性配準(zhǔn)使用正則化來(lái)進(jìn)行約束。LI H等人［9］對(duì)每個(gè)節(jié)點(diǎn)使用仿射變換A={123}，模擬物體的表面細(xì)節(jié)。為保證整個(gè)變形模型與關(guān)節(jié)一致，最大化局部剛度為：

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

　　其中是深度值。

　　2.5運(yùn)動(dòng)包絡(luò)約束

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

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

3結(jié)論

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

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

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

　　參考文獻(xiàn)

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

　?。?］ 伍龍華, 黃惠. 點(diǎn)云驅(qū)動(dòng)的計(jì)算機(jī)圖形學(xué)綜述［J］. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 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.

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

　?。?］ 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.

　?。?］ 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.

　?。?］ 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.