顧旭波，張永舉，張 健，吳良成，郭 玲

(1.江蘇省特種設備安全監(jiān)督檢驗研究院 吳江分院,江蘇 蘇州 215200；2.南京理工大學 自動化學院,南京 210094)

基于SIFT算法及閾值篩選的點云配準技術研究

顧旭波1，張永舉1，張 健1，吳良成2，郭 玲2

(1.江蘇省特種設備安全監(jiān)督檢驗研究院 吳江分院,江蘇 蘇州 215200；2.南京理工大學 自動化學院,南京 210094)

隨著三維測量技術應用領域的逐漸拓寬，點云數據處理技術的需求日益迫切，而多視點點云配準，是其中的基礎技術環(huán)節(jié);在此針對傳統(tǒng)ICP算法魯棒性差、對迭代初值敏感、計算效率低等缺點，提出一種SIFT算法與閾值篩選相結合的點云配準算法;在參考點云和待配準點云中，通過計算SIFT關鍵點及各點主曲率，獲得初始匹配點集；然后根據相似三角形閾值和法向量夾角閾值，進一步優(yōu)化點對間的旋轉平移關系;實驗結果證明，相對于傳統(tǒng)算法，改進算法能夠以更短的時間來獲得準確的配準效果，并且其自動化程度高以及能有效提高點云配準的效率和精度。

關鍵點；SIFT算子；點云配準；相似三角形

0 引言

近十年來，隨著電子、計算機技術的發(fā)展，三維測量設備的成本不斷降低、應用領域不斷拓寬，涵蓋了工業(yè)生產、生物復制、醫(yī)療醫(yī)學、教育教學等各個領域。

不同的三維測量技術，有不同的適用范圍，主要有：1)接觸式測量，如三維坐標測量機、多自由度測量臂等，適于少量關鍵點的測量；2)基于激光技術的測量，適于中長距離、規(guī)模較大的被測對象，測量速度相對較慢、精度較低；3)基于結構光技術的測量，適用于較近距離、較小物體的測量，測量速度較快、精度高[1]。

三維測量設備采集到的數據稱作點云，是物體表面采樣點、相對于測量設備內部的坐標原點和坐標軸的三維坐標，數據量大、且點之間沒有明確的拓撲關系，一般稱作散亂點云，必須經過處理才能得到有用的信息。一般來說，測量過程往往要經過多點測量，因此，點云數據處理首要的問題，就是將多個測量點得到的點云數據配準至同一坐標系下，也稱作點云拼接。

常用的點云配準方法有：1)在被測表面預置標記點，測量時，需保證兩次測量數據中至少有3個以上不共面的公共標記點，從而解算出兩坐標系間的變換關系；2)基于ICP(Iterative Closest Point，最近點迭代)算法，利用兩幅點云中重疊部分的數據進行迭代，直至距離最小?？梢?，依靠算法的點云配準優(yōu)勢體現在，無需在物體表面布置標記點，工作量小、且適用于不允許表面粘貼的被測物；但其弊端在于，傳統(tǒng)ICP算法對初值的要求較高，即兩幅待配準點云的初始位置要較為接近，一般通過手工方式實現，因而影響了算法的自動化程度。

本文從初始匹配入手，首先依據SIFT算法提取關鍵點集，并計算其中各點主曲率，進而得到初始匹配點對；然后通過法向量夾角閾值以及相似三角形閾值去除錯誤的對應點對，而后運用最小二乘法以及SVD(Singular Value Decomposition)法進行點云變換矩陣的求解。實驗證明，本文的算法能更好的滿足實際應用需求。

1 點云的粗配準

點云配準的主要目的就是得到參考點云與待配準點云之間的對應關系，從而求取兩點云間的旋轉矩陣R和平移矩陣T。為降低兩個點云之間的旋轉錯位以及平移錯位，減少精確配準的計算量，點云的粗配準是配準技術不可或缺的一個環(huán)節(jié)。粗配準是在沒有估計兩個點云初始位置關系的前提下，粗略地估算出點云之間的旋轉平移參數。

目前粗配準的研究技術，Chua[2]等提出一種點簽名法，該方法首先計算得到每個點的特征描述，然后比對兩片點云的點特征從而完成點云的初始配準。這種方法需要計算每個點的特征，使其計算過程龐大而且復雜，不利于大數據點云的配準。Feldmar[3]等提出一種基于主曲率的粗配準，該算法計算點的主曲率，然后通過點云之間主曲率相似的點來進行點云的粗配準。這個算法不僅容易受到噪聲點的影響，而且由于邊緣點的存在，容易得到錯誤的初始匹配。鐘瑩[4]等提出一種基于PCA(Principal Components Analysis)的粗配準，該算法對點云計算均值以及協(xié)方差矩陣，并以均值點為原點，以協(xié)方差矩陣的特征向量為坐標軸構建新的坐標系，把兩點云轉換到新坐標系下完成粗配準。許斌[5]等提出一種基于特征的配準方法，首先估算出點云的點法矢量，然后把點云以點云密度的不同來劃分區(qū)段，再以不同區(qū)段的主曲率的極值為條件來得到點云的初始配準參數。

本文首先使用SIFT算法來提取點云的關鍵點，從而方便后續(xù)點云主曲率的計算，并比對主曲率的極值來得到初始的配準點對，完成點云之間的粗配準。

1.1 關鍵點提取

SIFT特征匹配算法是David G.Lowe教授基于現有不變量技術特征檢測方法提出的，是一種基于尺度空間并對圖像縮放、旋轉甚至仿射變換保持不變性的特征匹配算法[6]。

關鍵點又叫興趣點，它是3D點云上通過定義檢測標準從而獲取到的具有穩(wěn)定性、區(qū)別性的點集。依技術而言，關鍵點相比于原始點云來說，其包含的數據量大大減少。而且結合關鍵點與局部特征描述形成的關鍵點描述子，可以一定程度上代表原始點云，這就為后續(xù)點云的主曲率計算提供相當大的便利。

SIFT算法提取關鍵點的主要步驟如下：

1)關鍵點的檢測。對輸入點云，構造尺度高斯金字塔LOG(Laplacian of Gaussian)；依據DOG(Difference of Gaussian)算子，構造高斯差分金字塔DOG；差分金字塔中的每一個像素點與周圍的26個像素點進行灰度值比較；若該點為極點，則把該點作為候選極值點，也就是關鍵點。

2)關鍵點的篩選。通過三維二次函數精確定位關鍵點，然后分析并除去低對比度關鍵點和邊緣響應關鍵點，最終篩選出關鍵點集。

假設參考點云為A，待配準點云為B，經過上述算法的提取，可以得到A、B關鍵點的集合Al={a1,a2,a3,…,am′}和Bl={b1,b2,b3,…,bn′}，其中m′和n′是A、B點云中關鍵點數。

1.2 初始匹配點對搜索

點的曲率表示該點的局部領域曲面的變化趨勢，是點的一種重要的幾何特征。而且曲率作為二次導數，很容易就受到噪聲的干擾，所以用曲率來搜索匹配點對能有效地抑制噪聲，提高點云配準的效率[7]。

對于給定點云A，計算其中任意一點ai的曲率，由于曲面和由ai的法向量和某一切向量所確定的平面的交集是一個平面曲線，如此就有一個曲率；若選擇不同的切向量，這個曲率會發(fā)生變化，并且有兩個極值即最大和最小曲率，稱為主曲率k1和k2，極值方向即為主方向。通過兩個主曲率可以得到點ai處的另外兩種曲率形式：高斯曲率和平均曲率。高斯曲率K反映了某一點處曲面的一般彎曲程度，而平均曲率H在微分幾何中是一個“外在的”彎曲測量標準，局部描述了該曲面嵌入在周圍三維空間中的曲率。

目前，曲率的估算方法中最常用的是二次曲面擬合方法。假設二次曲面S(u,v)用式表示：

S(u,v)=au2+buv+cv2+du+ev

(1)

(2)

(3)

(4)

由此可以得出，主曲率k1和k2的計算公式：

(5)

以ai點的主曲率為判斷條件遍歷待配準點云，則可得到與ai點曲率相差不大的匹配點。由于實際測量以及曲率計算不可避免地產生誤差，需要建立約束條件來得到匹配點對：

(6)

式中,δ1為誤差閾值，bj為待匹配點云中的任意一點。當bj滿足上式時，(ai,bj)記為一對匹配點；否則，舍棄；依此方法遍歷待匹配點云中的所有點。

2 點云的精配準

通過前面的粗配準，已得到一些初始匹配點對，但由于有很多相似曲率的點以及誤差的存在，使得配準的效率遠遠達不到實際應用的要求。因此，仍需進行精配準。

本文基于前述方法獲得的初始匹配點集，采用相似三角形閾值以及法向量夾角閾值等特征，對點對進一步進行篩選，從而提高配準的精度及效率，最后運用最小二乘法以及SVD法求解剛體變換矩陣。

2.1 相似三角形閾值篩選

對于任意一個三角形，在經過比例放大、旋轉、平移變換之后，總是與原三角形相似的?？稍邳c云配準中應用此特性，在參考點云與待配準點云中分別構建三角形，依據相似原理，明確點集的對應關系。

假設在A中任意3個不共線的點ai、aj、ak，在B中找到各自的對應點bu、bv、bw，假設(ai,bu)和(aj,bv)是確定的對應點，判斷(ak,bw)是否為對應點。由上述原理可知，不管兩個點集之間存在怎樣的旋轉和平移，由二者構成的的三角形總是相似的。兩三角形的各邊長如下表示：

Δaij=ai-aj、Δaik=ai-ak、Δajk=aj-ak

(7)

Δbuv=bu-bv、Δbuw=bu-bw、Δbvw=bv-bw

(8)

由相似原理，可以得到下列對應關系：

(9)

定義兩個三角形的相似度ω的過程如下：

(10)

(11)

(12)

若二者組成的三角形的相似度ω大于給定閾值δ2，則剔除ak和bw對應點對，否則保留。

2.2 法向量夾角閾值篩選

相似三角形閾值篩選能夠去除部分誤匹配點，但對于存在噪聲的點云，基于一種特征的篩選往往達不到穩(wěn)定的效果。因此，本文通過法向量夾角閾值法進一步進行篩選。

目前，點云的法向量估計方法中使用最廣泛的是局部表面擬合法，即將任意點ɑi的鄰域所擬合的最小二乘曲面的法向量，作為ɑi的法向量。但該方法只能得到法向量所在的直線，無法確定其內、外指向。本文使用文獻[8]中的算法解決上述問題。該算法以法向距離閾值為判斷條件，可以將點云劃分為平坦點和非平坦點，在進行法矢量方向調整時，依據點的種類的不同選擇不同的調整順序，加快了調整路徑的選擇速率，提高法矢方向調整的效率，而且還用了三次最近距離法解決了死鎖問題。

以經過相似三角形閾值篩選的點集為研究對象，計算各點的法向量，設定夾角閾值θ進行篩選。步驟如下：

Step1:選取經過主曲率判斷的初始匹配點集A′和B′。通過K鄰域協(xié)方差分析法計算各點集中點的法向量。

協(xié)方差公式如下：

(13)

Step2:歸一化各對應點的法向量，計算夾角β，若β小于設定的閾值θ，保留此對應點對，否則剔除。

2.3 改進的點云配準算法

點云配準算法的基本原理是使用最小二乘法的優(yōu)化思想，通過計算下列函數，獲得使其取得最小值的R和T，也就是剛體變換矩陣[3-5，9]。

(14)

式(7)中,Ai為參考點集；Bi為待配準點集中對應Ai的最近點；R為3×3的旋轉矩陣；T為3×1的平移矢量。f(R,T)是參考點集經過變換后，其中任意點與其在待配準點集中的對應點的距離平方和。只有當f(R,T)達到最小時，此時的R和T才是最終的剛體變換矩陣。

基于上文的總結，本文提出了一種改進算法，步驟如下：

Step1：在點集A和B中，根據SIFT算子，選擇關鍵點集Ai0和Bi0。

Step2：對關鍵點集Ai0和Bi0，依據主曲率搜索初始匹配點集Ai1和Bi1。

Step3：對點集Ai1和Bi1應用相似三角形閾值進行篩選，剔除錯誤的匹配點對，得到對應點集Ai2和Bi2。

Step4：對點集Ai2和Bi2應用法向量夾角閾值進一步的篩選，選定需要計算的初值對應點集Ai3和Bi3。

Step5：應用SVD(Singular Value Decomposition)法求得點集Ai3和Bi3之間的旋轉矩陣R和平移矢量T。

Step6：計算Ai4=R1Ai3+T1，也即是點云點集Ai3經過變換后所得到點集Ai4，然后重復Step4到Step6，直到滿足條件：

(15)

其中,Rk和Tk為第k-2次迭代所得到的旋轉矩陣和平移矩陣；δ3表示大于零的誤差閾值，也是收斂判斷條件。

3 實驗結果與分析

本文算法在VS2013平臺上使用C++語言實現，并調用點云處理函數庫PCL 1.8.0實現[9-11]，電腦主頻2.3 GHz，內存8 G，操作系統(tǒng)為Windows 10 64位。

為了驗證本文改進ICP算法的精度以及效率，與傳統(tǒng)ICP算法相比較，進行了三維點云配準實驗。原始點云數據來源于DAVID SLS-3結構光3D掃描儀所采集的貓模型和吊鉤數據。前者包含約1萬個數據點，后者約26萬個。

圖1為貓模型的實驗結果。其中圖1(a)為原始數據，因兩次分別從不同位置采集數據，導致數據在各自的局部坐標系下，因此在視圖上是分離的；圖1(b)為使用傳統(tǒng)ICP算法的配準結果，配準精度差強人意，但無法滿足高精建模和測量的要求；圖1(c)為本文算法的結果，可見，配準的精細度有顯著提高，尤其在耳朵、腿等部位效果尤其明顯。

圖1 貓模型點云的配準

圖2為吊鉤點云的實驗結果。圖2(a)為原始數據；圖2(b)為傳統(tǒng)ICP算法的結果，匹配出現了明顯的錯誤；圖2(c)為本文算法的實驗結果，能夠較好地滿足應用需求。此外，算法精度的定量化描述及時間效率如表1所示，通過與原始算法的比較，體現了本文改進算法的優(yōu)勢。

圖2 吊鉤點云的配準

被測物體點數量/個時間/ms誤差傳統(tǒng)ICP算法本文算法傳統(tǒng)ICP算法本文算法貓模型10000673514116550.00730.0006吊鉤2693271.042e61.263e40.27390.0011

4 結語

點云配準在三維測量技術中的作用舉足輕重，精確、高效的配準是對后續(xù)建模、測量等處理的有力保證。本文提出的改進點云配準算法，先利用SIFT算子找到關鍵點集，使用主曲率進行粗配準，運用閾值改進的點云配準算法進行精確配準，提高了算法效率。經過實驗表明：與傳統(tǒng)ICP算法相比較，本文算法在計算速率以及配準效果上都有明顯的優(yōu)勢，滿足了實際應用的要求。

[1] 鄭南寧.計算機視覺與模式識別[M].北京：國防工業(yè)出版社，1998.

[2] Chua C S, Jarvis R. Point Signatures: A new representation for 3D object recognition[J]. International Journal of Computer Vision, 1997, 25(1):63-85.

[3] Feldmar J, Ayache N. Rigid, affine and locally affine registration of free-form surfaces[M]. Kluwer Academic Publishers, 1996.

[4] 鐘 瑩, 張 蒙. 基于改進ICP算法的點云自動配準技術[J].控制工程, 2014, 21(1):37-40.

[5] 許 斌, 李忠科, 呂培軍,等. 基于特征的點云精確配準算法[J]. 計算機應用與軟件, 2013(11):112-114.

[6] Lowe D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004, 60(2): 91-110.

[7] 歐陽江帆. 基于幾何特征向量的三維人臉識別研究[D].廈門：廈門大學, 2009.

[8] 劉大峰, 戴 寧, 孫全平,等. 面向曲面重構的切平面法矢方向調整算法[J]. 機械科學與技術, 2008, 27(2):192-197.

[9] Saad K R, Colombo A S, Ribeiro A P, et al. Reliability of photogrammetry in the evaluation of the postural aspects of individuals with structural scoliosis[J]. Journal of Bodywork & Movement Therapies, 2012, 16(2):210-216.

[10] Senin N, Colosimo B M, Pacella M. Point set augmentation through fitting for enhanced ICP registration of point clouds in multisensor coordinate metrology[J]. Robotics and Computer-Integrated Manufacturing, 2013, 29(1):39-52.

[11] Point cloud library website.Point cIoud data[EB/OL].[2014—10—06].http://www.pointclouds.org/(in Chinese).[PCL點云庫官網．點云數據庫[EB/0L]．[2014—10—06]．http://www.pointcIouds.org/.

Research on Point Cloud Registration Technology Based on SIFT Algorithm and Threshold Filter

Gu Xubo1,Zhang Yongju1,Zhang Jian1,Wu Liangcheng1,Guo Ling2

(1.Special Equipment Safety Supervision Inspection Institute of Jiangsu Province, Wujiang Branch, Suzhou 215200,China; 2.School of Automation, Nanjing university of science and technology, Nanjing 210094,China)

With widening application of 3D measurement technology, the demand for cloud point data processing technology is becoming more and more urgent, and the multi view point cloud registration is one of the fundamental technologies.A point cloud registration algorithm combining SIFT algorithm with threshold selection is proposed to overcome the disadvantages of the traditional ICP algorithm, such as poor robustness, sensitive to iterative initial value and low computational efficiency.Firstly, the initial matching set between the reference point cloud and the point cloud to be registered is obtained by calculating the SIFT key points and their main curvatures;then rotation and translation between corresponding are optimized based on the similar triangle threshold and the vector angle threshold.Experiments show that, compared with the traditional algorithm, the improved algorithm can achieve accurate registration results in shorter time, and it is highly automated and can effectively improve the efficiency and accuracy of point cloud registration.

key point；SIFT operator；point cloud registration；similar triangles

2017-05-22；

2017-06-08。

江蘇省質監(jiān)局2016年度科研項目(KJ168357)。

顧旭波(1970-)，男，江蘇無錫人，碩士，主要從事特種設備安全方向的研究。

郭 玲(1976-)，女，江蘇南京人，副教授，碩士生導師，主要從事三維點云數據處理方向的研究。

1671-4598(2017)12-0247-04

10.16526/j.cnki.11-4762/tp.2017.12.064

TP391.7

A