林寶尉 王法勝 孫 怡

1(大連理工大學 遼寧 大連 116023)2(大連東軟信息學院 遼寧 大連 116023)3(大連民族大學 遼寧 大連 116600)

0 引 言

近年來各種3D獲取設備及方法都在迅速的發(fā)展，比如常見的range finder、激光雷達(LiDAR)、運動結構提取、機構光投影及Kinect等。作為3D真實場景的重要表現(xiàn)形式，3D點云已經(jīng)在眾多的研究及應用領域，如計算機視覺、機器人及無人駕駛中被使用。

和2D圖片以及3D曲面不同，點云是一種更自然的對真實場景的描述。其不需要額外的要素間連接關系及其他復雜的拓撲結構。然而，如果在獲取點云信息時使用了不同的設備或者復原方法，生成的點云一般會存在閉塞點、雜波、噪聲、表面稀疏度以及尺度不同等各種問題。其中尺度不同的問題在不同種點云融合時尤其需要解決。

近些年，部分學者提出了多種用來估計點云尺度并且進行點云配準的方法。一般的，這些方法可以分為基于ICP(Iterative Closest Point)的配準方法、基于特征匹配的方法和其他方法。

基于ICP的方法： ICP方法最早由Besl等[1]提出，是使用最廣泛的點云配準方法。該方法主要包括兩個計算步驟：

(1) 在每一次迭代，尋找最近鄰的點；

(2) 計算該次迭代的變換矩陣并計算尺度比。

這種在20世紀60年代提出的點云變化矩陣計算通常被稱作Orthogonal Procrustes問題[2-3]，其不僅適用于剛性問題，通過相似變換矩陣的推定，該方法也可以用于非剛性問題。ICP方法在配準點云的同時，也可以對兩點云間的相對尺度比例進行推定。然而，ICP的一個最大的問題是需要提供給它一個位姿和尺度比例的初始猜測值。如果該猜測值距離全局最優(yōu)解較遠，最終的結果很有可能會收斂在一個局部的最優(yōu)解，從而導致配準失敗。

大量的基于ICP的擴展的方法被同時應用于點云的配準當中。這些方法被分為“point-to-point”[1]、“point-to-plane”[4-5]及“plane-to-plane”[6]三個種類。這些方法基本都可以解決點云的閉塞、雜波、噪聲和表面稀疏等問題。但是它們并沒有解決點云的尺度不同所帶來的問題。

基于特征匹配的方法：和ICP方法不同，基于特征匹配的方法不需要提供初始位姿的猜測即可對點云進行配準。比較常用的方法有spin image[7-8]、NARF[9]等。同樣的，這些方法也沒有解決點云尺度不同的問題。

Point Feature Histogram (PFH)[10]、Fast Point Feature Histogram (FPFH)[11]、3D Shape Context (3DSC)[12]、Rotational Projection Statistics (RoPS)[13]等流行的局部特征方法，雖然能夠提高點云配準的魯棒性。然而這些方法仍然無法解決點云的尺度變化問題，有的方法甚至無法應用于點云場景。

一些3D特征是尺度不變的方法，如3D SIFT[14]、3D SURF[15]等。該類方法都是對2D方法的擴展，它們對3D曲面場景的效果比較好。由于點云無法提供表面的曲率信息，所以這類方法也是無法使用的。

不同于上述特征提取的方法，SHOT[16]和SIPF等[17-18]方法通過對場景紋理等信息的分析來描述局部特征。根據(jù)上述文獻的描述，場景中紋理信息及法向量信息對于提高局部特征的魯棒性具有很好的效果。他們對于閉塞點、雜波和噪聲具有很好的魯棒性。然而對于3D點云來說，由于不同的采集方法，額外的紋理等信息可能不存在。同時，3D點云表面的法向量質(zhì)量也對配準的結果起關鍵作用。

Huang[19]提出了一種基于深度學習的3D點云特征提取方法，并將提取的點云特征應用于多傳感器點云的配準中。根據(jù)文獻中的描述，該方法對于人工合成的數(shù)據(jù)具有很好的魯棒性，但是仍未將該方法應用于真實場景。Lin等[20]提出了一種3D點云配準的方法。該方法是多種已有方法的整合，將3D點云的關鍵點提取，PCA修正，深度神經(jīng)網(wǎng)絡特征描述以及ICP的精度調(diào)整整合到一起，得到了較魯棒的配準結果。該方法對于大尺度場景的數(shù)據(jù)融合、定位等應用具有較好的效果。但是該方法沒有將點云的尺度變化問題考慮進去。

其他方法：最簡單的用來計算尺度的方法可以通過計算點云的邊界值或是通過計算點云分布的標準差等。這些邊界值或者標準差可以用來縮放點云，使點云間的尺度基本相同。但是，這種方法只有在點云完全相互重疊的時候才有效。

Elbaz等[21]提出了一種基于SVD分解的2D特征輔助3D配準方法，Lin等[22]提出了一種結合2D特征的3D特征提取方法。Aubry等[23]提出了一種通過使用3D模型來檢測2D物體的方法。Crivellaro等[24]同樣提出了一種基于2D圖像來配準3D模型的方法。這些方法無法應用于本文所提出的場景之中。

Keyscale、ScaleRatioICP[25-26]是兩種很好的尺度不同點云配準的方法。通過PCA貢獻率來計算能夠代表點云尺度的keyscale，并且計算兩個點云間的相對尺度比來歸一化點云大小。同時，Mellado等[27]也提出了相對尺度比的計算方法來計算不同類型點云的結果。這些方法雖然可以估計出點云間的尺度信息，但是它們并不進行點云的配準操作。

在本文中，提出了一種新的點云配準及尺度估計的方法。該方法是GICP方法的一種擴展。在構建點云配準的成本函數(shù)時，將代表點云尺度的參數(shù)考慮進去。通過對該非線性問題求解來推定剛性變化的變換矩陣。該方法也稱為SGICP方法。

1 SGICP方法

本文提出的SGICP方法是GICP (Generalized-ICP)的擴展。在詳細介紹SGICP方法之前，我們先來簡單介紹GICP方法。

1.1 GICP

(1)

Ci是每個點的協(xié)方差矩陣。

我們定義剛性變換矩陣為T,每一對對應點的配準誤差di則為：

di=bi-Tai

(2)

因為ai和bi屬于互相獨立的高斯分布，則d的分布也屬于高斯分布：

(3)

所以，計算變換矩陣T的成本函數(shù)為：

(4)

1.2SGICP

下面，我們將介紹SGICP的詳細推導。我們將延續(xù)使用GICP中定義的符號。

1.2.1 成本函數(shù)

我們的應用場景是要對不同尺度的點云進行配準和尺度估計。所以，在計算對應點的配準誤差di時，我們加入了尺度變量s：

di=bi-sTai

(5)

因為我們可以將T寫成T=[R][t]，所以上式可寫成：

di=bi-sRai-st

(6)

由于di服從高斯分布，根據(jù)式(3)可以得到新的分布為：

(7)

所以，我們定義新的成本函數(shù)為：

(8)

1.2.2 推導證明

為了計算成本函數(shù)的最優(yōu)化問題，我們需要計算每一次迭代中變換矩陣的導數(shù)。假設最優(yōu)的結果為T*=sT。為了對T*進行求導，我們將T*分解為：

T*=sTT*=s[R][t]T*=[s,x,y,z,φ,θ,ψ]T

(9)

根據(jù)雅可比公式:

(10)

下面，我們將給出f對s、x、y、z、φ、θ、ψ的偏導。

首先計算▽s:

(11)

接下來計算▽x、▽y、▽z:

(12)

相似地有:

(13)

(14)

最后計算▽φ、▽θ、▽ψ:

(15)

相似地有:

(16)

(17)

最后，通過更新s、x、y、z、φ、θ、ψ實現(xiàn)梯度下降算法并計算最優(yōu)的變化矩陣：

(18)

2 實驗結果及分析

我們將通過實驗證明文中提出的算法可以有效地應用于人工以及真實場景數(shù)據(jù)。

2.1 人工場景數(shù)據(jù)

為演示SGICP算法，首先應用于簡單的人工數(shù)據(jù)。該數(shù)據(jù)是斯坦福的兔子3D點云模型，可以從文獻[28]下載。如圖1(a)所示，圖中右邊的兔子是原始點云，含有69 450個點。圖1(a)中左邊的兔被放大1.5倍，并對點數(shù)進行隨機下采樣，得到點數(shù)為543 652的新模型。該點云中沒有明顯的面元素，但是由于兩點云可以互相重疊，所以SGICP可以有效實現(xiàn)點云的尺度估計和點云配準。配準的結果如圖1(b)所示。兩點云可以完整重疊在一起。點云尺度估計的結果為1.500 01(表1所示)。使用GICP失敗的配準結果如果圖1(c)所示。

圖1 原始兔子點云及配準結果

在圖1的實驗基礎上，我們在點云中加入了隨機噪聲。高斯噪音被隨機的加入了點云中每個3D點的x、y、z坐標。高斯均值量分別設置為點云邊界長度的0.1%、0.5%和1.0%。同時，兩個點云都隨機地被刪除80%的3D點。點云配準的結果如圖2和表1所示，SGICP可以得到正確的配準結果。

圖2 加入噪聲后的兔子點云及配準結果

數(shù)據(jù)ICPGICPSGICP原始兔子1．49999(0．00%)failed1．50001(0．00%)噪聲兔子(0．1%)1．49533(0．31%)failed1．50043(0．03%)噪聲兔子(0．5%)1．49673(0．22%)failed1．49985(0．01%)噪聲兔子(1%)1．49087(0．61%)failed1．49562(0．29%)真實場景0．897536(28．22%)failed0．70078(0．11%)

我們同時將該算法應用到斯坦福的Happybuddy及Airplane數(shù)據(jù)中。準確的配準結果如圖3、圖4所示。

圖3 Happy buddy點云配準結果

圖4 Airplane點云及配準結果

2.2 真實場景數(shù)據(jù)

真實場景數(shù)據(jù)采集于Velodyne 32E激光。我們將激光器安裝于汽車頂部，并將激光整體傾斜一定的角度，翻滾角、俯仰角和偏航角分別設置為6.0°、36.0°和-91.0°。當汽車在城市街角場景中行駛并采集點云時，我們連續(xù)采集兩幀數(shù)據(jù)。點云如圖5(a)所示，其中一幀點云被縮放為原始的0.7倍。基于SGICP方法配準的正確結果如圖5(d)所示。同時，我們得到的點云的尺度比為0.700 78 (表1所示)。

圖5 Velodyne32E激光點云及配準結果

SGICP和ICP、GICP的對比結果顯示在圖5(b, c)中。圖6給出了SGICP和ICP方法的優(yōu)化速度對比，由于SGICP使用擴展牛頓法(BFGS)進行優(yōu)化，其收斂速度比ICP的方法快速。另外，ICP方法雖然可以對點云的尺度比進行估計，但是初始的點云位姿非常重要。同時本實驗的真實點云不能互相完整地重疊，所以ICP方法無法應用。

圖6 SGICP與ICP方法的收斂速度對比

我們將SGICP算法應用在比較有挑戰(zhàn)性的數(shù)據(jù)上。我們使用SfM(structure from motion)的方法構建了兩個點云，分別包含549 753及492 032個3D點(如圖7(a)所示)?；赟fM方法構建的3D點云無法得到統(tǒng)一的尺度值，并且包含大量的噪聲及閉環(huán)點。但是使用我們的算法，可以準確對其進行配準。配準結果如圖7(b)所示。

圖7 SfM點云及配準結果

3 結 語

本文提出了一種基于擴展GICP方法的點云配準以及點云尺度估計的方法。通過增加尺度變量重新設計了點云配準的成本函數(shù)，同時給出了新成本函數(shù)對于變換矩陣各分量的偏導值，應用于梯度下降、牛頓法等非線性優(yōu)化方法中，得到了較好的結果。

但是本文的方法對于兩點云尺度差別較大情況無法有效地配準。因為在這種情況下，SGICP無法有效地查找高質(zhì)量的對應點并計算梯度。因此我們建議給出一個初始的粗尺度猜測再應用本算法。

參考文獻

[1] Besl P J,Mckay N D.A method for registration of 3-D shapes[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2002,14(2):239-256.

[2] Hurley J R,Cattell R B.The procrustes program:Producing direct rotation to test a hypothesized factor structure[J].Systems Research & Behavioral Science,1962,7(2):258-262.

[3] Dryden I L,Mardia K V.Statistical shape analysis[J].John Wiley & Sons Ltd Chichester,1998,213(6):663-669.

[4] Zhang Z.Iterative Point Matching for Registration of Free-Form Curves Rapports de Recherche[R].IRA Rapports de Recherche,Programme 4:Robotique,Imageet Vision,no.1658,1992.

[5] Chen Y,Medioni G.Object modeling by registration of multiple range images[C]// IEEE International Conference on Robotics and Automation,1991.Proceedings.IEEE,2002:145-155.

[6] Segal A,H?hnel D,Thrun S.Generalized-ICP[C]// Robotics:Science and Systems V,University of Washington,Seattle,USA,June 28-July 1,2009.

[7] Johnson A E,Hebert M.Surface matching for object recognition in complex three-dimensional scenes[J].Image & Vision Computing,1998,16(9-10):635-651.

[8] Johnson A E,Hebert M.Using spin images for efficient object recognition in cluttered 3D scenes[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,1999,21(5):433-449.

[9] Radu B S,Rusu B,Konolige K,et al.NARF:3D Range Image Features for Object Recognition[C]// Workshop on Defining and Solving Realistic Perception Problems in Personal Robotics at IROS,2010.

[10] Rusu R B,Marton Z C,Blodow N,et al.Persistent Point Feature Histograms for 3D Point Clouds[C]// Intelligent Autonomous Systems 10,IAS 2008.2008:119-128.

[11] Rusu R B,Blodow N,Beetz M.Fast point feature histograms (FPFH) for 3D registration[C]// IEEE International Conference on Robotics and Automation.IEEE,2009:3212-3217.

[12] Frome A,Huber D,Kolluri R,et al.Recognizing Objects in Range Data Using Regional Point Descriptors[M]// Computer Vision-ECCV 2004.Springer Berlin Heidelberg,2004:224-237.

[13] Guo Y,Sohel F,Bennamoun M,et al.Rotational Projection Statistics for 3D Local Surface Description and Object Recognition[J].International Journal of Computer Vision,2013,105(1):63-86.

[14] Scovanner P,Ali S,Shah M.A 3-dimensional sift descriptor and its application to action recognition[C]// Proceedings of the 15th International Conference on Multimedia 2007,Augsburg,Germany,September 24-29,2007:357-360.

[15] Knopp J,Prasad M,Willems G,et al.Hough Transform and 3D SURF for Robust Three Dimensional Classification.[C]// Computer Vision-ECCV 2010-,European Conference on Computer Vision,Heraklion,Crete,Greece,September 5-11,2010,Proceedings.DBLP,2010:589-602.

[16] Tombari F,Salti S,Stefano L D.Unique Signatures of Histograms for Local Surface Description[M]// Computer Vision - ECCV 2010.Springer Berlin Heidelberg,2010.

[17] Lin B,Zhao F,Tamaki T,et al.SIPF:Scale invariant point feature for 3D point clouds[C]// IEEE International Conference on Image Processing.IEEE,2015.

[18] Lin B,Wang F,Sun Y,et al.Boundary points based scale invariant 3D point feature[J].Journal of Visual Communication & Image Representation,2017,48:136-148.

[19] Huang X.Learning a 3D descriptor for cross-source point cloud registration from synthetic data[DB].eprint arXiv:1708.08997,2017.

[20] Lin C C,Tai Y C,Lee J J,et al.A novel point cloud registration using 2D image features[J].Eurasip Journal on Advances in Signal Processing,2017,2017(1):5.

[21] Elbaz G,Avraham T,Fischer A.3D Point Cloud Registration for Localization Using a Deep Neural Network Auto-Encoder[C]// Computer Vision and Pattern Recognition.2017.

[22] Lin B,Tamaki T,Slomp M,et al.3D Keypoints Detection from a 3D Point Cloud for Real-Time Camera Tracking[J].Ieej Transactions on Electronics Information & Systems,2013,133(1):1-7.

[23] Aubry M,Maturana D,Efros A A,et al.Seeing 3D Chairs:Exemplar Part-Based 2D-3D Alignment Using a Large Dataset of CAD Models[C]// Computer Vision and Pattern Recognition.IEEE,2014:3762-3769.

[24] Crivellaro A,Lepetit V.Robust 3D Tracking with Descriptor Fields[C]// Computer Vision and Pattern Recognition.IEEE,2014:3414-3421.

[25] Lin B,Tamaki T,Raytchev B,et al.Scale ratio ICP for 3D point clouds with different scales[C]// IEEE International Conference on Image Processing.IEEE,2014:2217-2221.

[26] Lin B,Tamaki T,Zhao F,et al.Scale alignment of 3D point clouds with different scales[J].Machine Vision & Applications,2014,25(8):1989-2002.

[27] Mellado N,Dellepiane M,Scopigno R.Relative scale estimation and 3D registration of multi-modal geometry using Growing Least Squares.[J].IEEE Transactions on Visualization & Computer Graphics,2016,22(9):2160-2173.

[28] The Stanford 3D Scanning Repository[EB/OL].http://www.graphics.stanford.edu/data/3Dscanrep/.