蔡先杰

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

基于局部坐標(biāo)系法線投射的點(diǎn)云精細(xì)配準(zhǔn)算法

蔡先杰

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

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

點(diǎn)云配準(zhǔn)；精細(xì)配準(zhǔn)；局部坐標(biāo)系；法線投射；關(guān)聯(lián)點(diǎn)對(duì)

0　引言

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

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

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

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

1　相關(guān)工作

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

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

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

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

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

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

去噪主要是利用剛體運(yùn)動(dòng)的不變屬性去除噪聲點(diǎn)對(duì)，可分為曲面幾何特征約束和點(diǎn)的距離約束。

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

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

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

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

2　算法描述

2.1ICP

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

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

2.2法線投射雙向插補(bǔ)算法

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

圖1　法線投射雙向插補(bǔ)算法求關(guān)聯(lián)點(diǎn)對(duì)

2.3基于局部坐標(biāo)系法線投射的點(diǎn)云配準(zhǔn)算法（LCSNS）

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

（1）采樣

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

（2）點(diǎn)對(duì)關(guān)聯(lián)

①建立局部坐標(biāo)系

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

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

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

③關(guān)聯(lián)點(diǎn)對(duì)選取

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

（3）去除噪聲點(diǎn)對(duì)

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

（4）計(jì)算變換并移動(dòng)點(diǎn)云

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

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

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

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

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

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

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

3　實(shí)驗(yàn)結(jié)果

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

3.1佛像模型

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

圖2　佛像模型

?色代表從一個(gè)角度掃描得到的點(diǎn)云模型）

圖3　佛像模型三種算法配準(zhǔn)效果示意圖

表1　不同算法在處理佛像模型時(shí)達(dá)到收斂條件所用時(shí)間對(duì)比（單位：ms）

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

3.2龍模型

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

圖4　龍模型

圖5　龍模型三種算法配準(zhǔn)效果示意圖

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

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

表3　不同算法在處理龍模型時(shí)達(dá)到收斂條件所用時(shí)間對(duì)比（單位：ms）

4　結(jié)語

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

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

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

［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］王蕊，李俊山，劉玲霞，等.基于幾何特征的點(diǎn)云配準(zhǔn)算法［J］.華東理工大學(xué)學(xué)報(bào)：自然科學(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-），男，廣東澄海人，研究生，研究方向?yàn)橛?jì)算機(jī)圖形學(xué)

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