張少玉

（西安工程大學(xué)　西安　710048）

1　引言

隨著經(jīng)濟(jì)的發(fā)展、人們生活水平的提高，三維模型被廣泛應(yīng)用于醫(yī)療、娛樂、教育等行業(yè)，由此帶來三維建模技術(shù)的發(fā)展，但是由于當(dāng)前技術(shù)的局限性，并不能獲得完整的點云數(shù)據(jù)，每次只能獲得某個角度的點云數(shù)據(jù)，因此就需要多方位地進(jìn)行三維掃描，這就使得在建模之前必須先進(jìn)行點云配準(zhǔn)，即將不同視角下的點云變換到同一坐標(biāo)系下，它是圖像處理、虛擬現(xiàn)實、測繪工程等領(lǐng)域的一項關(guān)鍵技術(shù)，點云配準(zhǔn)的精度和速度直接影響三維建模的精度和速度。

目前點云配準(zhǔn)算法中，最常用的就是Besl［1］和Chen［2］等分別提出的迭代最近點（Iterative Closest Point，ICP）算法，該算法是通過兩片點云的對應(yīng)點不斷迭代確定旋轉(zhuǎn)和平移矩陣，直到滿足收斂條件，但是使用該算法時，若兩片點云的初始姿態(tài)不好，則會形成局部最小化，造成迭代不能收斂到正確的結(jié)果；而且對應(yīng)點的選取速度較慢。因此為了克服ICP算法自身的部分缺陷，許多研究人員對其進(jìn)行了改進(jìn)，其中很多人把點云的剛性特征應(yīng)用進(jìn)來，對其改進(jìn)。點云的剛性特征有曲率、點法向與鄰域點法向的夾角、點法向、局部張量、點與鄰域重心的距離等［3～4］。特征法首先提取點云的剛性特征，利用特征進(jìn)行粗配準(zhǔn)，然后使用特征改進(jìn)的ICP算法進(jìn)行精配準(zhǔn)。戴靜蘭等［5］、Yang等［6］使用曲率特征進(jìn)行配準(zhǔn)，但是估計曲率時需要用到近鄰點，就會受到噪聲的影響，而且估計曲率需要消耗大量的時間。Jiang等［7］使用夾角特征進(jìn)行配準(zhǔn)，雖然其方法提高了點云配準(zhǔn)的誤差收斂速度，但是計算和比較點之間的K維夾角特征耗費了不少時間。RUSU等［8］提出了一種基于法矢量的特征直方圖，根據(jù)法矢量建立局部坐標(biāo)系，用鄰近點的距離關(guān)系和法矢量夾角的直方圖表示該點的特征，但是該方法受噪聲干擾明顯，而且計算量較大。

本文提出一種使用尺度不變特征轉(zhuǎn)換（Scale Invariant Feature Transform，SIFT）特征點的改進(jìn)方法。該方法的基本要求就是兩片點云數(shù)據(jù)有足夠的重合度。該方法直接使用求得的源點云的特征點與體素柵格下采樣后的目標(biāo)點云進(jìn)行配準(zhǔn)，減少了計算特征描述子的環(huán)節(jié)，從而提高了配準(zhǔn)速度，并通過隨機(jī)采樣一致算法（Random Sample Consensus，RANSAC）去除錯誤匹配點對，來提高配準(zhǔn)的精度。雖然王程冬等［9］也提出使用SIFT特征進(jìn)行點云配準(zhǔn)，但是其方法是在二維圖像中進(jìn)行SIFT特征檢測，通過映射關(guān)系來獲得三維對應(yīng)特征點，而本文是直接在三維點云數(shù)據(jù)中進(jìn)行SIFT特征點檢測，避免了因為映射關(guān)系可能會找到錯誤對應(yīng)特征點的可能，同時也大大減少了算法的運行時間。

2　相關(guān)理論

2.1　體素柵格下采樣

由于獲取的點云數(shù)據(jù)數(shù)量比較大，若是全部用來做實驗，則會影響后續(xù)實驗的速度，因此采用部分點云來代替所有的點云來提高速度。PCL中的VoxelGrid類便可實現(xiàn)此目的，其通過輸入的點云數(shù)據(jù)創(chuàng)建一個三維體素柵格（可把體素柵格想象成微小的空間三維立方體的集合），然后在每個體素內(nèi)用體素中所有點的重心來近似顯示體素中其他點。步驟如下：

1）立方體邊長 L 的確定［10～11］。 L 的確定非常關(guān)鍵，在L過大的情況下會降低搜索效率，如果L過小，則會出現(xiàn)很多空的柵格。小立方體柵格邊長為：L=α3s c，其中，α是用來調(diào)節(jié)小立方體柵格的邊長的比例因子，s是比例系數(shù)，c是小柵格中的點云數(shù)量。

3）求得每個小柵格的重心實現(xiàn)下采樣。每個柵格的重心為

用(X0，Y0，Z0)代表該小柵格中的所有點，實現(xiàn)點云的下采樣，達(dá)到精簡點云數(shù)據(jù)的目的。

通過體素柵格下采樣后，點云的數(shù)量減少了，但是點云的形狀特征并未發(fā)生變化，因此在點配準(zhǔn)之前通過此方法來提高配準(zhǔn)速度。如圖1所示，（a）為原點云數(shù)據(jù)，（b）為體素柵格下采樣后的數(shù)據(jù)，可以看出點云的形狀保持不變，只是顯得稍微稀疏。

圖1　體素柵格下采樣結(jié)果

2.2　SIFT算法

SIFT算法［12］是Lowe DG提出的一種基于尺度空間的圖像局部特征描述算法。雖然它只能描述圖像的局部特征，但是該特征對視角變化、仿射變換、噪聲保持一定的穩(wěn)定性，對旋轉(zhuǎn)、尺度縮放、亮度變化保持不變性，其原理如下：

1）尺度空間的生成

把原圖像 I(x，y)與高斯核G(x，y，σ)的卷積定義為一幅圖像的尺度空間L(x，y，σ)：

其中，G(x，y，σ)是尺度可變高斯函數(shù)，σ為尺度空間因子，其決定圖像的平滑程度，(x，y)為圖像像素坐標(biāo)。

2）檢測尺度空間極值點

其中，D(x，y，σ)為高斯差分函數(shù)，引入該函數(shù)是為了有效檢測出尺度空間中的穩(wěn)定特征點，式（8）中，k為常量。在檢測極值點時，每個像素點要與26個點（同尺度的相鄰的8個像素點和其上下相鄰尺度的9×2個點）進(jìn)行比較，如果該像素點的DoG（Dif-ference ofGaussian）算子在這26個鄰域中為最大或最小，則該點為特征點。

3）精確定位極值點

通過擬合三維二次函數(shù)以精確定位特征點的位置和尺度（達(dá)到亞像素精度），同時去除低對比度的特征點和不穩(wěn)定的邊緣響應(yīng)點，以增強(qiáng)匹配穩(wěn)定性，提高抗噪聲能力。對尺度空間DoG函數(shù)進(jìn)行曲線擬合，利用DoG函數(shù)在尺度空間的泰勒展開式：

其中，向量 X=(x，y，σ)，對式（5）進(jìn)行求導(dǎo)并使一階導(dǎo)數(shù)為0，可得特征點精確位置的偏移向量：

4）為每個特征點指定方向參數(shù)

利用特征點鄰域像素的梯度方向分布特性為每個特征點指定方向參數(shù)，使算子具備旋轉(zhuǎn)不變性。每個像素的梯度模和方向分別為

在以特征點為中心的鄰域窗口內(nèi)采樣，并用直方圖統(tǒng)計鄰域像素的梯度方向。梯度直方圖的范圍是0°～360°，每10°為一柱，以梯度模 M作為貢獻(xiàn)權(quán)重，即離中心點越遠(yuǎn)的鄰域其對直方圖的貢獻(xiàn)就越小。

至此，圖像的特征點已檢測完畢，每個特征點有三個信息：位置、所處尺度和方向。如圖2所示，是通過SIFT算法對兩幅圖像進(jìn)行檢測的結(jié)果。

圖2　兩幅圖像SIFT特征檢測結(jié)果

因此，PCL中的SIFTKpoint類將二維圖像中的SIFT算子調(diào)整移植到了3D空間中，該類可以計算出點云的SIFT特征點，使SIFT算子實現(xiàn)了在3D空間中的直接應(yīng)用。如圖3所示，是在一片點云中求得SIFT特征點的結(jié)果，圖中小圓點部分為人體上半身的點云數(shù)據(jù)，方形點就是檢測出來的SIFT特征點。

圖3　點云的SIFT特征點檢測結(jié)果

2.3 RANSAC算法

RANSAC是一種隨機(jī)參數(shù)估計方法，于1981年由 Fischler和Bolles［13］最先提出，主要思路是通過采樣和驗證的策略，求解大部分樣本都能滿足的數(shù)學(xué)模型參數(shù)。具體步驟為

針對應(yīng)用需求，綜合考慮各種通訊方式的傳輸帶寬、覆蓋范圍、實時性、資費，最終選擇采用GPRS/3G/衛(wèi)星通信相結(jié)合的多模傳輸方式。主控制器的數(shù)據(jù)發(fā)送線程實現(xiàn)系統(tǒng)的多模數(shù)據(jù)發(fā)送功能，采用wvdial腳本和ppp腳本配置華為E261聯(lián)通3G無線上網(wǎng)卡和SIM900A型GPRS模塊連接網(wǎng)絡(luò)[13]，衛(wèi)星通信模塊采用ORBCOMM公司的OG2衛(wèi)星調(diào)制解調(diào)器，在3G和GPRS無網(wǎng)絡(luò)的情況下系統(tǒng)自動切換至衛(wèi)星通信模式，通過串口將定位和報警信息數(shù)據(jù)包發(fā)送給衛(wèi)星通信模塊，經(jīng)衛(wèi)星通信模塊發(fā)送至服務(wù)器。

1）從樣本集中選取4對匹配點作為內(nèi)點集合，使用最小方差估計算法對這個集合計算模型參數(shù)；

2）用1）中得到的模型去測試所有的其它匹配點對，如果小于設(shè)定閾值，則加入內(nèi)點集合；

3）如果迭代次數(shù)大于設(shè)定的閾值，則退出；否則重復(fù)步驟1）和2），選取內(nèi)點個數(shù)最多的一組作為合格的匹配點集，并根據(jù)新的內(nèi)點集合重新估計模型。

如圖4所示，是RANSAC算法在二維數(shù)據(jù)集中的簡單應(yīng)用。圖4（a）圖既包含了局內(nèi)點又包含了局外點，圖4（b）中圓形為局內(nèi)點，方形為局外點，直線就是基于RANSAC得到的適應(yīng)數(shù)據(jù)的模型。

圖4　RANSAC算法原理示意圖

3　本文配準(zhǔn)方法

3.1　ICP算法

ICP算法是一個經(jīng)典的點云配準(zhǔn)算法，它的基本原理是不斷地尋找對應(yīng)點集和求解變換關(guān)系，直到找到源點云和目標(biāo)點云之間的旋轉(zhuǎn)矩陣R和平移向量T，最終使源點云與目標(biāo)點云滿足某種條件下的最優(yōu)匹配。

設(shè)源點云為 P={pi|pi∈R3，i=1，2，…，N} ，目標(biāo) 點 云 為 Q={qj|qj∈R3，j=1，2，…，M} ，其 中N≤M。

步驟如下：

2）在目標(biāo)點云Q中尋找源點云P每個點 pi的最近點pi'；

3）計算出源點云和目標(biāo)點云的剛體變換矩陣R和T；

4）更新源點云P，計算得出P'=Rpi+T；

5）計算均方誤差：

6）若dm-dm+1＜γ或者達(dá)到迭代次數(shù)，則停止迭代；否則反復(fù)執(zhí)行2）～5）。

3.2　方法步驟

隨著掃描技術(shù)的發(fā)展，獲取的點云數(shù)量越來越大，這就對后期的處理帶來不便，而經(jīng)典的ICP算法計算效率不高，而且花費時間較多，因此本文提出一種改進(jìn)方法。首先對兩片點云進(jìn)行體素柵格下采樣，通過減少點云的數(shù)量來減少運行時間，其次用源點云的SIFT特征點與目標(biāo)點云進(jìn)行配準(zhǔn)，并用RANSAC算法去除錯誤配對點，為了提高配準(zhǔn)的精度，進(jìn)行變換估計后，保留源點云，重復(fù)上述過程直到滿足設(shè)定條件，步驟如下：

1）設(shè)定閾值λ＞0，用來判斷程序是否終止；

2）對兩片點云進(jìn)行體素柵格下采樣；

3）求取源點云的SIFT特征點。首先定義SIFT特征點檢測；其次設(shè)置尺度相關(guān)參數(shù)，包括點云對應(yīng)體素柵格中體素的最小尺寸，檢測特征點時體素空間尺度的數(shù)目和為在每一個體素空間尺度下計算高斯空間的尺度時所需要的參數(shù)；然后設(shè)置候選特征點應(yīng)有的對比度下限；最后輸入點云，進(jìn)行計算，對結(jié)果進(jìn)行保存；

4）調(diào)用ICP算法，用保存的源點云SIFT特征點集與下采樣后的目標(biāo)點云進(jìn)行配準(zhǔn)；

5）采用RANSAC算法來剔除錯誤的匹配點對；

6）保留變換后的源點云，重復(fù)2）～5），若歐氏適合度評分（源點云到目標(biāo)點云對應(yīng)點對的距離平方和）（其中n為對應(yīng)點對的數(shù)目，和是一對對應(yīng)點中的兩個點）小于給定的閾值λ，則一直重復(fù)2）～5），否則退出。

本文方法流程圖如圖5所示。

圖5　本文方法流程圖

4　實驗結(jié)果與分析

本文用Kinect采集到的人體數(shù)據(jù)來驗證本文方法的有效性。在圖6中，（a）為采集到的兩片點云數(shù)據(jù)，紅色為目標(biāo)點云，綠色為源點云，（b）為直接采用ICP算法進(jìn)行配準(zhǔn)的結(jié)果，可以看到（b）圖中的源點云與（a）中稍有移動，但是不太明顯，使得配準(zhǔn)后的兩片點云并沒有成功融合在一起；（c）為采用本文方法提取的源點云的SIFT特征點，與原數(shù)據(jù)相比點云數(shù)量減少了很多，（d）為采用本文方法配準(zhǔn)的結(jié)果，可以看到兩片點云成功配準(zhǔn)，與（b）相比效果良好。

圖6　實驗結(jié)果

表1是ICP算法與本文方法在時間和精度上的比較，可以看到本文方法在時間上比ICP算法減少了，歐氏適合度評分也比ICP算法小，因此本文方法取得了令人滿意的效果。

表1　ICP算法與本文方法比較

5　結(jié)語

針對ICP算法迭代耗時、精度較差的問題，本文提出結(jié)合SIFT特征點的方法對其進(jìn)行改進(jìn)。首先求出源點云的SIFT特征點，然后用該特征點集與目標(biāo)點云進(jìn)行配準(zhǔn)，并通過RANSAC算法去除錯誤匹配點對，然后保留變換后的源點云進(jìn)行重復(fù)，滿足設(shè)定條件后退出程序。經(jīng)實驗表明本文方法得到了較好的配準(zhǔn)精度和收斂速度。在實際應(yīng)用中，有較高的使用價值。但是對于SIFT特征不明顯的點云，配準(zhǔn)效果較差，這也是本文下一步的研究方向。

［1］Besl P J，Mckay N D.A method for registration of 3D shapes［J］.IEEE Transactionson Pattern Analysisand Machine Intelligence，1992，14（2）：239-256.

［2］Chen Y，Medioni G.Objectmodeling by registration of multiple range images［C］//The 1991 IEEE International Conference on Robotics and Automation，Sacramento，CA，USA，1991：2724-2729.

［3］Wang Sen，Wang Yang，Jin Miao，etal.Conformalgeometry and its applications on 3D shapematching，recognition，and stitching［J］.Medical Engineering&Physics，2007，29（7）：1209-1220.

［4］?str?mK，Karlsson J，EnquistO，etal.Automatic feature point correspondences and shape analysiswithmissing data and outliers using MDL［J］.Image Analysis，2007，4522（5）：21-30.

［5］戴靜蘭，陳志楊，葉修梓.ICP算法在點云配準(zhǔn)中的應(yīng)用［J］.中國圖像圖形學(xué)報，2007，12（3）：517-521.DAIJinglan，CHEN Zhiyang，YE Xiuzi.The Application of ICP Algorithm in Point Cloud Registration［J］.Journal of Image and Graphics，2007，12（3）：517-521.

［6］Yang Shen，Shen Xukun，QiYue，etal.An automated registration method for range images［C］//Proceedings of the 2ndInternationalConferenceonTechnologiesfor E-Learning and Digital Entertainment.Heidelberg，Berlin，Germany：Springer-Verlag，2007：772-783.

［7］Jiang Jun，Chen Jun，Chen Xinglin.Registration for 3-D point cloud using angular-invariant feature［J］.Neuro Computing，2009，72（16-18）：3839-3844.

［8］RUSU R B，BLODOW N，BEETZM.Fast point feature histograms（FPFH）for 3D registration［C］//IEEE International Conference on Robotics and Automation，May 12-17，2009，Kobe，Japan，2009：3212-3217.

［9］王程東，程筱勝，崔海華，等.SIFT算法在點云配準(zhǔn)中的應(yīng)用［J］.傳感器與微系統(tǒng)，2012，31（2）：149-152.WANG Chengdong，CHENG Xiaosheng，CUI Haihua，et al.The Application of SIFTAlgorithm in PointCloud Registration［J］.Transducer and Microsystem Technolodies，2012，31（2）：149-152.

［10］YU H，WANG R，CHEN J，et al.Saliency computation and simplication of point cloud data［C］//Proc.2012 2nd International Conference on Computer Science and Network Technology（ICCSNT 2012）.Changchun，China：IEEEPress，2012：1350-1353.

［11］ZHAO X，WEN MH.Kd-tree based non-uniform simplication of 3D point cloud［C］//Proc.2009 3rd International Conference on Genetic and Evolutionary Computing（ICCSNT 2009）.Guilin，China：IEEE Press，2009：339-342.

［12］Lowe D G.Distinctive image features from scale-invariant key points［J］.International Journal of Computer Vision，2004，60（2）：91-110.

［13］Fischler MA and Bolles R C.Random Sample Consensus：A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography［J］.Communicationsof the ACM，1981，24（6）：381-395.