基于局部坐標系法線投射的點云精細配準算法

蔡先杰

（四川大學(xué)計算機學(xué)院，成都　610065）

基于局部坐標系法線投射的點云精細配準算法

蔡先杰

（四川大學(xué)計算機學(xué)院，成都610065）

點云配準是逆向工程中用于拼接點云模型的方法，可分為初始配準和精細配準兩個步驟。假設(shè)在已經(jīng)實現(xiàn)初始配準的情況下，提出基于局部坐標系法線投射的點云精細配準算法。通過對點云采樣得到的采樣點建立局部坐標系，然后將采樣點的相鄰點集投影到該坐標系下，就可以得到代表模型的每個局部曲面的控制點集，再用法線投射算法求解出關(guān)聯(lián)點對集并計算兩個點云之間的變換參數(shù)（旋轉(zhuǎn)角度和位移量）。局部坐標系法線投射算法獲取到的關(guān)聯(lián)點對有效性高，能明顯減少迭代次數(shù)，提高配準效率。

點云配準；精細配準；局部坐標系；法線投射；關(guān)聯(lián)點對

0　引言

點云是指通過三維掃描儀掃描物體得到的、用三維點集表示物體表面輪廓的模型。點云技術(shù)是逆向工程的一個重要環(huán)節(jié)，廣泛應(yīng)用于醫(yī)學(xué)、工業(yè)制造與工程［1-2］、數(shù)字娛樂、文物保護等領(lǐng)域。

由于掃描儀的掃描范圍限制，單一掃描儀無法通過一次掃描就得到物體的完整點云模型。要將不同角度掃描得到的多組點云拼成完整的模型，需要用到點云配準技術(shù)。點云配準，是指將具有重疊區(qū)域的兩個點云模型，通過重疊區(qū)域的歐幾里德不變量和幾何特征［3-4］等建立兩個點云的聯(lián)系，將它們映射到同一坐標系下，使之拼接成為一個模型的過程。

點云配準又可分為初始配準和精細配準兩個步驟。初始配準主要是將兩個點云移動到相近的位置，配準結(jié)果比較粗糙。精細配準建立在做了初始配準之后，兩個點云的重疊區(qū)域比較接近的基礎(chǔ)上，進一步對點云進行配準，使重疊區(qū)域達到近似重合的效果。

本文假設(shè)初始配準的步驟已經(jīng)實現(xiàn)，主要對精細配準進行探討。

1　相關(guān)工作

ICP［5-6］是精細配準最著名的算法，大部分點云配準算法，如T.Pajdla［7］等提出的ICRP（查找歐氏距離最近的兩點作為關(guān)聯(lián)點對，再通過二次反向查找最近點的方法篩選點對），都是基于此算法。ICP算法的思想是：

①建立兩個點云之間的聯(lián)系，選取關(guān)聯(lián)點對集合；

②以其中一個點云（目標點云）為基準，通過關(guān)聯(lián)點對集合計算出的變換參數(shù)，將另一個點云（源點云）移向該點云；

③重復(fù)以上步驟，直到兩個點云間的距離小于某一閾值。

ICP算法的實現(xiàn)一般分為4步：點集采樣、點對關(guān)聯(lián)、去噪、計算變換并移動點云。其中，點對關(guān)聯(lián)和去噪是ICP算法的關(guān)鍵步驟。

點對關(guān)聯(lián)一般是在兩個點云距離較近的情況下，進行點到點的最近距離關(guān)聯(lián)、點到切平面交點的關(guān)聯(lián)和點到面的投影關(guān)聯(lián)［8-9］。Rusinkiewicz等［8］指出當(dāng)初始配準的誤差較小時，點到面投影的關(guān)聯(lián)方式優(yōu)于點到點最近距離的關(guān)聯(lián)方式。

去噪主要是利用剛體運動的不變屬性去除噪聲點對，可分為曲面幾何特征約束和點的距離約束。

曲面幾何特征約束是利用物體同一位置的表面幾何特征（法矢、曲率、重心等）在任意視角保持不變的原理，比較關(guān)聯(lián)點對的特征值之差，篩選出差值大于指定閾值的點對。Turk等［10］對構(gòu)建了三角面片的點云模型進行ICP配準，關(guān)聯(lián)點對時加上距離和非邊界附近點的限制，使ICP算法適用于三維掃描點云的配準。Godin等［11-12］等計算點云的曲率、密度向量集，選取關(guān)聯(lián)點對。Sharp等［13］提出ICPIF（Iterative Closest Points using Invariant Features），利用點對距離、曲率、球諧函數(shù)等確定關(guān)聯(lián)點對，在計算點對的距離信息時，使用歐氏距離和特征向量距離的加權(quán)方程。Devrim等［14］用空間點集間的角度和距離參數(shù)確立關(guān)聯(lián)點對。Bae等［15］提出GP-ICPR（Geometric Primitive ICP with the RANSAC）算法，利用曲率的變化量與對應(yīng)點的法矢的夾角來確定點對，然后用變種的RANSAC算法去除噪聲點。王蕊［16］等用曲率及鄰近點的曲率特征，建立10維向量，進行點云配準。Jiang等［17］等提出基于法線夾角的點對關(guān)聯(lián)方法，在目標點云中選取關(guān)聯(lián)點的k個鄰近點，對法線夾角組成的向量求差，根據(jù)鄰近點的法線方向去除點云的噪聲點。Fl?ry［18］等對原ICP算法進行修改，用l1-norm（曼哈頓距離）代替l2-norm（歐氏距離），計算關(guān)聯(lián)點對距離最小的變換矩陣。Xie等［19］將點云投影到垂直于投影軸的平面，建立均勻網(wǎng)格，隨機選取控制點矩陣，建立雙三次B樣條進行法線到面的求交獲取關(guān)聯(lián)點對集。這類算法適合掃描點云和模型點云，對點云的重合度要求也不是很高，但要求點足夠多且足夠密集，且有較好的采樣和去噪聲算法。

點的距離約束是利用剛體運動保證物體重疊區(qū)域關(guān)聯(lián)點之間的距離和關(guān)聯(lián)點與其相鄰點的距離關(guān)系不變的原理，篩選掉距離不在指定閾值內(nèi)的點對。Dorai等［20］利用兩組關(guān)聯(lián)點對的鄰近點距離差小于指定閾值來去除噪聲點對。Zhou和Liu等［21-22］運用矢量運算和三角不等式分析了ICP算法最鄰近點的傳統(tǒng)標準，提出去除噪聲點對的方向約束（Orientation Constraint）、剛性約束（Rigidity Constraint）和匹配誤差約束（Matching Error Constraint），證明了傳統(tǒng)標準可以滿足這三個約束，關(guān)聯(lián)出的點具有較高的匹配質(zhì)量。

然而，對于重疊區(qū)域表面凹凸程度較大的點云模型，重疊區(qū)域有歧義點或者重疊區(qū)域與投影面夾角較大的點云模型，上述算法的處理效果并不是很好。

本文提出了基于局部坐標系法線投射的點云精細配準算法，能高效地處理復(fù)雜模型。

2　算法描述

2.1ICP

Besl等提出的ICP算法是三維點云配準的經(jīng)典算法，其目的主是計算出公式（1）中的R和T，使∑（R，T）最小，式中n表示點云P和點云Q的關(guān)聯(lián)點對數(shù)，pi、qi分別表示P和Q上的第i個關(guān)聯(lián)點，R為旋轉(zhuǎn)矩陣，T為平移向量。

ICP算法基本思想是，通過反復(fù)查找Pk（k為迭代的次數(shù)）和Q的關(guān)聯(lián)點對集，計算旋轉(zhuǎn)矩陣R和平移向量T，更新P的坐標，使P逼近Q，直至P和Q的距離達到閾值（滿足公式（1）中的∑（R，T）＜σ），迭代結(jié)束時返回R和T。ICP查找關(guān)聯(lián)點對的方式是直接計算在Q中距離最近的點qi，若滿足則認為是關(guān)聯(lián)點對。找到Pk和Q中的所有點對后，再通過最小二乘思想擬合出最佳變換關(guān)系。

2.2法線投射雙向插補算法

Xie等［19］用法線投射方法求點云的關(guān)聯(lián)點對，并用雙向插補的距離約束及曲率約束對關(guān)聯(lián)點對進行去除噪聲對的處理。如圖1所示，Xie等［19］主要對ICP算法進行了采樣、關(guān)聯(lián)和去除噪聲點對的修改：采樣時，按垂直于掃描儀的方向建立N×N的網(wǎng)格，將點云P和點云Q中的點分別投影到網(wǎng)格中，然后在每個網(wǎng)格中隨機保留一個點作為采樣點；關(guān)聯(lián)時，使用采樣點作為控制點建立雙三次B樣條曲面，然后用點云P中每個曲面的中心插值點pi沿法線方向與點云Q對應(yīng)曲面求交，得到關(guān)聯(lián)點對（pi，qi）；去除噪聲點對時，在qi附近求插值點qi'，再與P的對應(yīng)曲面塊求交點pi'，再求pi與qi的主曲率（k1（pi），k2（pi），k1（qi），k2（qi））。當(dāng)滿足公式（2）和（3）的條件時，認為（pi，qi）是有效的關(guān)聯(lián)點對。Xie等［19］的算法在處理掃描結(jié)果較好，且初始配準后網(wǎng)格采樣可行的模型時，具有較好的配準效果。

圖1　法線投射雙向插補算法求關(guān)聯(lián)點對

2.3基于局部坐標系法線投射的點云配準算法（LCSNS）

我們獲取的三維點云可能并不包含掃描儀掃描角度參數(shù)。對于這種情況，法線投射雙向插補算法并不適用。于是，針對無法獲知掃描角度的點云模型，本文提出了基于局部坐標系法線投射的點云配準算法（LCSNS，Local Coordinate System Normal Shooting），該算法對某一點云（本文選取的是點云Q）進行隨機采樣或者均勻采樣，得到多個采樣點，再以這些采樣點的相鄰點集為局部點集，建立局部坐標系，然后分別將各點在Q和P上的相鄰點集投影到該坐標系下，或者通過已知控制點矩陣，查找另一點云中最近點為控制點，就可以得到多個局部曲面控制點集，再用法線投射算法求解出關(guān)聯(lián)點對集。由關(guān)聯(lián)點對集，計算點云P變換到點云Q的旋轉(zhuǎn)矩陣R和平移向量T，使點云P逐漸移近點云Q，直至兩個點云達到重疊區(qū)域基本重合的效果或達到迭代結(jié)束條件。

（1）采樣

LCSNS用局部坐標系進行點對關(guān)聯(lián)，除了要求采樣得到的、同一點云模型上的樣本點之間距離足夠大外沒有其他要求。采樣方法不限，為了方便，本文選用隨機采樣方式。

（2）點對關(guān)聯(lián)

①建立局部坐標系

隨機采樣后，對于Q上每個采樣點qi，以qi為中心，選取鄰近的N個點為一個集合，組成分散點云塊。如果輸入的點云帶有法線信息，則選取最接近點云塊重心的點，作為局部坐標系的原點，以該點的法線作為局部坐標系z軸，建立局部坐標系。如果輸入的點云不帶有法線信息（本文假設(shè)法線信息缺失），取點云塊重心點為局部坐標系原點，用PCA算法分析得出局部坐標系的xyz軸。假設(shè)局部坐標系的方向向量為X=（x0，y0，z0），Y=（x1，y1，z1），Z=（x2，y2，z2），原點坐標為（x'，y'，z'），可以根據(jù)局部坐標系方向向量和原點坐標，建立局部坐標系到整個點云模型所處的世界坐標系的轉(zhuǎn)換矩陣MT，如公式（4）所示。

②構(gòu)建網(wǎng)格并獲取控制點矩陣

對于每一個點云塊，通過在其局部坐標系的XOY平面構(gòu)建網(wǎng)格，再將點云塊投影到網(wǎng)格內(nèi)隨機采樣，得到用于擬合局部曲面的控制點矩陣?？紤]到點云塊形狀多變，可能導(dǎo)致一些網(wǎng)格中不包含投影點，本文采用擴展劃分，收縮采樣的方式進行網(wǎng)格構(gòu)建和控制點采樣。將網(wǎng)格劃分為（NG+EG）×（NG+EG）的區(qū)域，其中NG表示控制點矩陣大小，EG表示擴展網(wǎng)格大小。由于點云P的坐標是迭代變化的，所以每次選取關(guān)聯(lián)點對前需要更新P的局部控制點矩陣。每次迭代更新P的坐標后，對于點云Q的控制點矩陣中的每一個點，通過在P上查找最近點，來得到P的局部曲面控制點矩陣。

③關(guān)聯(lián)點對選取

對于點云Q的每一個采樣點qi，按照轉(zhuǎn)換矩陣MT，將其在局部坐標系下的法線轉(zhuǎn)換到世界坐標系中，計算其法線所在的直線與點云P上對應(yīng)點云塊所在的局部曲面（由局部曲面控制點矩陣計算得出）的交點pi，將（pi，qi）作為候選關(guān)聯(lián)點對。

（3）去除噪聲點對

同法線投射雙向插補算法，去掉候選關(guān)聯(lián)點對集中不滿足公式（2）和公式（3）的點對，得到有效關(guān)聯(lián)點對集。

（4）計算變換并移動點云

由有效關(guān)聯(lián)點對集計算出點云P到點云Q的旋轉(zhuǎn)矩陣R和平移向量T，將點云P轉(zhuǎn)換到點云Q的坐標系下。

（5）迭代結(jié)束條件

精細配準是通過迭代精細調(diào)整點云位置的過程，迭代結(jié)束的判斷方式是點云配準的復(fù)雜度、效率和效果的綜合考量。本文采用以下幾種通用的迭代結(jié)束判斷方式：

①迭代次數(shù)，當(dāng)?shù)_到指定次數(shù)后，結(jié)束點云配準。本文發(fā)現(xiàn)，一般初始配準結(jié)束后，精細配準只需20次以內(nèi)的迭代就可以達到較好的匹配效果。

②變換矩陣增量，計算當(dāng)前點云配準的（R，T），若T近似于單位陣，T近似于零向量，則結(jié)束點云配準。

③點云距離，計算最新位置的P'與Q點對間距離之差。當(dāng)P'和Q的距離達到閾值后，結(jié)束點云配準。

④點云距離變化，前后兩次P'與Q點對間距離之差。當(dāng)兩次距離差小于閾值，結(jié)束點云配準。

3　實驗結(jié)果

在這一節(jié)，我們會討論我們的算法（LCSNS）與上文所述的兩種算法（經(jīng)典算法ICP，以更精確的ICRP為代表，以及Xie等［19］的法線投射（Normal Shooting）雙向插補算法，簡稱NS）的適用情況。我們所用的點云模型均是掃描儀從0°開始，以24°為增量對同一三維模型進行掃描得到的結(jié)果。

3.1佛像模型

以如圖2所示的佛像模型為例，各個算法的實驗結(jié)果如圖3、表1和表2所示。

圖2　佛像模型

?色代表從一個角度掃描得到的點云模型）

圖3　佛像模型三種算法配準效果示意圖

表1　不同算法在處理佛像模型時達到收斂條件所用時間對比（單位：ms）

表2　不同算法在處理佛像模型時達到收斂條件所需的迭代次數(shù)對比（單位：次）

3.2龍模型

以如圖4所示的龍模型為例，各個算法的實驗結(jié)果如圖5、表3和表4所示。

圖4　龍模型

圖5　龍模型三種算法配準效果示意圖

通過對比可以看出，LCSNS中，因為目標點云（點云Q）的控制點矩陣一經(jīng)確定后就不再改變，每次迭代過程使用目標點云的控制點矩陣求得新計算出的源點云（點云P）的控制點矩陣，而不是重新通過投影整個點云P到網(wǎng)格平面并隨機采樣的方式來確定點云P上的控制點矩陣，所以效率會優(yōu)于NS算法。

同時，由于結(jié)合了法線投射和最近點查找的方式，所以在達到收斂時所需迭代次數(shù)會明顯少于ICRP算法。

表3　不同算法在處理龍模型時達到收斂條件所用時間對比（單位：ms）

4　結(jié)語

本文提出了基于局部坐標系法線投射的點云精細配準算法（LCSNS），該算法對點云模型的局部點集建立投影坐標系，再將坐標系附近的點集投影到該坐標系下，得到雙三次B樣條曲面控制點矩陣。相對于ICRP和法線投射雙向插補算法，局部坐標系法線投射算法能獲取更好的匹配點對集，從而減少迭代次數(shù)，提高配準效率。

下一步我們將繼續(xù)改進和完善算法，例如研究更好的點云去噪方式等，以提高算法的適用性和效率。

表4　不同算法在處理龍模型時達到收斂條件所需的迭代次數(shù)對比（單位：次）

［1］Larsson S，Kjellander J A P.Motion Control and Data Capturing for Laser Scanning with an Industrial Robot［J］.Robotics and Autonomous Systems，2006，54（6）：453-460.

［2］Dorn M，Browne M，Ghidary S S.Landmark Detection by a Rotary Laser Scanner for Autonomous Robot Navigation in Sewer Pipes［C］. The Second International Conference on Mechatronics and Information Technology.Jecheon（Korea），2003：600-604.

［3］J.V.Wyngaerd，L.V.Gool，Automatic Crude Patch Registration：Toward Automatic 3D Model Building，Computer Vision and Image Understanding 87（1-3）（2002）8-26.

［4］L.Li，N.Schemenauer，X.Peng，Y.Zeng，P.Gu，A Reverse Engineering System for Rapid Manufacturing of Complex Objects，Robotics and Computer-Integrated Manufacturing，18（1）（2002）：53-67.

［5］Besl P J，McKay N D.Method for Registration of 3D Shapes［C］.Robotics-DL Tentative.International Society for Optics and Photonics，1992：586-606.

［6］Chen Y，Medioni G.Object Modeling by Registration of Multiple Range Images［C］.Robotics and Automation，1991.Proceedings.，1991 IEEE International Conference on.IEEE，1991：2724-2729.

［7］T.Pajdla，L.V.Gool，Matching of 3D Curves Using Semi-Differential invariants，in：Fifth International Conference on Computer Vision，Cambridge，MA，USA，1995，pp.390-395.

［8］Rusinkiewicz S，Levoy M.Efficient Variants of the ICP Algorithm［C］.3D Digital Imaging and Modeling，2001.Proceedings.Third International Conference on.IEEE，2001：145-152.

［9］Park S Y，Subbarao M.A Fast Point-to-Tangent Plane Technique for Multi-View Registration［C］.3D Digital Imaging and Modeling，2003.3DIM 2003.Proceedings.Fourth International Conference on.IEEE，2003：276-283.

［10］Turk G，Levoy M.Zippered Polygon Meshes from Range Images［C］.Proceedings of the 21st Annual Conference on Computer Graphics and interactive techniques.ACM，1994：311-318.

［11］Godin G，Boulanger P.Range Image Registration Through Viewpoint Invariant Computation of Curvature［J］，1995.

［12］Godin G，Laurendeau D，Bergevin R.A Method for the Registration of Attributed Range Images［J］，2001.

［13］Sharp G C，Lee S W，Wehe D K.ICP Registration Using Invariant Features［J］.Pattern Analysis and Machine Intelligence，IEEE Transactions on，2002，24（1）：90-102.

［14］Devrim A.Full Automatic Registration of Laser Scanner Point Clouds［J］.ETH Zurich，2003.

［15］Bae K H，Lichti D D.A Method for Automated Registration of Unorganised Point Clouds［J］.ISPRS Journal of Photogrammetry and Remote Sensing，2008，63（1）：36-54.

［16］王蕊，李俊山，劉玲霞，等.基于幾何特征的點云配準算法［J］.華東理工大學(xué)學(xué)報：自然科學(xué)版，2009，35（5）：768-773.

［17］Jiang J，Cheng J，Chen X.Registration for 3D point Cloud Using Angular-Invariant Feature［J］.Neurocomputing，2009，72（16）：3839-3844.

［18］Fl?ry S，Hofer M.Surface Fitting and Registration of Point Clouds Using Approximations of the Unsigned Distance Function［J］. Computer Aided Geometric Design，2010，27（1）：60-77.

［19］Xie Z，Xu S，Li X.A High-Accuracy Method for Fine Registration of Overlapping Point Clouds［J］.Image and Vision Computing，2010，28（4）：563-570.

［20］Dorai C，Wang G，Jain A K，et al.Registration and Integration of Multiple Object Views for 3D Model Construction［J］.Pattern Analysis and Machine Intelligence，IEEE Transactions on，1998，20（1）：83-89.

［21］Zhou H，Liu Y.Accurate Integration of Multi-View Range Images Using K-means Clustering［J］.Pattern Recognition，2008，41（1）：152-175.

［22］Liu Y.Constraints for Closest Point Finding［J］.Pattern Recognition Letters，2008，29（7）：841-851.

A Fine Registration Algorithm of Point Clouds Based on Local Coordinate System Normal Shooting

CAI Xian-jie
（College of Computer Science，Sichuan University，Chengdu 610065）

Registration of point clouds is a method for jointing point cloud models.It can be divided into two stages，the rough registration and the fine registration.Realizes assuming that the former，proposes a fine registration algorithm，which is based on local coordinate system normal shooting（LCSNS），builds local coordinate systems for each point we sample in advance from our point clouds，and adjacent points of each sampled point are projected to the corresponding local coordinate system，then we can get control points sets for building local surfaces，which represent the whole point cloud.After that，corresponding points set of two point clouds can be figured out by using the normal shooting algorithm，and we can finally calculate transformation parameters（about rotation and translation）between two point clouds. By LCSNS，we get more valid corresponding points，which contribute greatly in reducing iterative times and in increasing registration efficiency.

Registration of Point Clouds；Fine Registration；Local Coordinate System；Normal Shooting；Corresponding Points

1007-1423（2016）26-0057-06DOI：10.3969/j.issn.1007-1423.2016.26.014

蔡先杰（1991-），男，廣東澄海人，研究生，研究方向為計算機圖形學(xué)

2016-06-28修改日期：2016-08-30