陳 卓，宋麗梅，陳昌曼，唐 歡

（天津工業(yè)大學電工電能新技術(shù)天津市重點實驗室，天津 300387）

同一物體不同視角的點云配準方法

陳 卓，宋麗梅，陳昌曼，唐 歡

（天津工業(yè)大學電工電能新技術(shù)天津市重點實驗室，天津 300387）

對兩幅不同視角下的點云采用面表法管理，而后對兩幅不同視角下的點云采用曲率特征的ICP改進算法進行配準處理.具體處理方法為先根據(jù)獲得的兩幅海量點云數(shù)據(jù)進行面表法處理，然后根據(jù)獲得的面表計算每幅點云中的近似曲率，對其中一幅點云的曲率按大小分類，并且每類進行隨機采樣.根據(jù)隨機采樣的結(jié)果按照曲率第一、距離第二的原則在另一幅點云中查找對應(yīng)點，最后求出第一幅點云的旋轉(zhuǎn)和平移矩陣從而完成配準過程.實驗結(jié)果表明：在相同海量點云下，面表法的生成時間比八叉樹法生成時間平均少406 ms，查找時間平均少53.5 ms；并且曲率特征的ICP算法可以迭代25次收斂到0.241 625 mm的精度，基本滿足多視角點云配準的精度高、計算速度快等要求.

物體；視覺；點云配準；ICP算法；點云管理

自21世紀以來，國內(nèi)有很多學者對點云的配準算法進行了研究.1987年，Horn、Arun等用四元數(shù)法提出點集對點集配準方法.這種點集與點集坐標系匹配算法通過實踐證明是一個解決復(fù)雜配準問題的關(guān)鍵方法.1992年，計算機視覺研究者Besl和Mckay介紹了一種高層次的基于自由形態(tài)曲面的配準方法，也稱為迭代最近點法（iterative closest point，ICP）.ICP法經(jīng)過十幾年的發(fā)展，不斷得到完善和補充：Senin等[1]提出夠增強增強ICP配準精度的方法；Martínez等[2]提出了與鐳射光掃描相結(jié)合的ICP配準算法；Lena等[3]分析并改進了ICP算法的匹配錯誤；Sacharow等[4]提出ICP-NI的改進算法；王蕊等[5]和吳祿慎等[6]提出基于特征的點云配準算法；程效軍等[7]研究了點云配準誤差傳播規(guī)律；王程冬[8]等提出一種基于SIFT算法的點云配準.張蕾等[9]和鄭德華等[10]針對點云配準方法進行約束改進；王欣等[11]提出了一種改進方法來對點云進行配準；張金魁[12]提出了基于曲率的局部配準算法；周春艷等[13]研究了三維點云ICP改進算法.因此，本文在上述研究成果與已有研究的結(jié)果[14-15]的基礎(chǔ)上，提出了多視角點云配準的新方法.

1 點云的存儲方式

經(jīng)典的點云的存儲方法有八叉樹、三維網(wǎng)格等算法.八叉樹算法將點云按照樹的結(jié)構(gòu)進行排列，但是無法確定點云內(nèi)部距離最近的兩點，而且無法快速確定該點是否是邊界點，并且該算法的訪問速度比較慢.如果需要找到點云空間中一部分區(qū)域內(nèi)的全部點，可以使用八叉樹算法或者三角網(wǎng)格算法.八叉樹算法需要遍歷整個樹，速度較慢；三角網(wǎng)格算法將空間分割為多個盒子，每個盒子內(nèi)部按序存放點云，該方法消耗的空間與分成盒子的體積大小成反立方關(guān)系，也就是體積越小計算機消耗的空間就越大.本文提出了一種改進的三維網(wǎng)格管理點云的算法——面表法，該方法將消耗的空間大小轉(zhuǎn)變?yōu)槠椒疥P(guān)系，同時不會降低生成和訪問速度.

面表法是三維網(wǎng)格算法的改進，首先要計算點云的包圍盒，計算好包圍盒（xmin，ymin，zmin，xmax，ymax，zmax），取x，y，z中任意2個向量作為基準.例如取x，y向量，給定閾值（假設(shè)閾值為T）進行x，y平面分割，將平面分成（xmin-xmax）×（ymin-ymax）/（T×T）個方塊，然后對整個點云進行遍歷，使得每個點找到對應(yīng)的方塊，并且按照鏈表的方式存儲.如圖1所示.

圖1 面表的生成與點的存儲Fig.1 Generation of surface list method and store points

面表生成后有一個較大的缺陷，就是無法獲知z方向上的大小，因此每個表格中的點應(yīng)該對原鏈表進行再改進.具體改進方法為，每個表格中的點按照閾值對z方向上的大小進行分類.分類方法如圖2所示.

圖2 z方向分類方法Fig.2 z classification method

如果按照面表法尋找點（x0，y0，z0），應(yīng)先提取出該點坐標的x和y方向的坐標（x0，y0），而后根據(jù)自定義的映射規(guī)則找出（x0，y0）所對應(yīng)的表格.假設(shè)自定義的映射規(guī)則是所有點的x，y方向應(yīng)遵循x= [（x0-xmin+0.5×T）/T]，y= [（y0-ymin+0.5×T）/T].生成面表后按照該規(guī)則找到對應(yīng)的（x，y）面表.然后根據(jù)z0找到z方向的分類.找到包含z0的一類后，通過遍歷該類獲知（x0，y0，z0）的位置.遍歷空間區(qū)域的方法為找出該區(qū)域中包含的所有x，y表格：應(yīng)從x低表向x高表順序訪問，訪問到最高位置時，將y表增加1，x置成低表，繼續(xù)訪問，直到y(tǒng)表達到最高位置為止.z表根據(jù)給定的區(qū)域?qū)的分類進行限定，超過或低于該范圍的z類不進行訪問.

2 基于曲率特征的ICP的改進算法

基于曲率特征的ICP算法概述：首先需要獲知兩幅點云的全部曲率特征，由于曲率的含義是根據(jù)均勻平滑的曲面來定義的.因此需要對部分點云進行曲面擬合，然后針對擬合后的曲面進行曲率計算，即可獲知該點的估計曲率.本文選用的曲面模型是二次曲面模型，即需要擬合曲面的點云數(shù)量不能低于4個點.而本文所提出的面表法存儲結(jié)構(gòu)，可以有效地進行曲率計算.由于面表法首先是對全部點云進行x，y平面上的表格分類，然后再對每個x，y表格里進行有序的z分類，因此每一個z方向的表格都代表一個空間體.由于每個空間體內(nèi)點云數(shù)量不同，并且當空間體內(nèi)點云數(shù)量少于4個時，無法對這部分點云進行曲面擬合，因此必須對所有的空間體進行歸并和刪除，即對于空間體內(nèi)較少的點去嘗試找附近有較多點的空間體進行歸并運算，如果找不到附近有較多點的空間體則刪除該空間體.歸并與刪除算法是配準算法的預(yù)處理環(huán)節(jié).在預(yù)處理結(jié)束后，選擇空間體內(nèi)曲面擬合模型，如公式（1）所示：

公式（1）沒有加入旋轉(zhuǎn)和平移，因此這個模型必須將點云旋轉(zhuǎn)平移到原點附近，否則無法擬合.由此可見，對于空間體內(nèi)的點云不能使用公式（1）進行擬合.空間體內(nèi)的點云進行平面擬合如公式（2）所示：

設(shè)空間體Q={q1，q2，…，qn}（n>3），q1點的x坐標表示為xq1，則擬合公式（2）可以表示為公式（3）：

通過解上式可知A、B的數(shù)值，從而獲得平面向量（A，B，-1），這個平面向量單位化后需要轉(zhuǎn)到（0，0，1）.根據(jù)二次曲面模型在原點附近求出的曲率，可以找到空間體中一點作為估計參考點，將空間體Q中所有點帶入平面方程，獲得每個點的狀態(tài)（大于0，或者小于0，或者等于0）.將大于0的所有點設(shè)為點集Qu，將小于0的所有點設(shè)為點集Qd.對Qu、Qd求取方差Δu、Δd，期望Eu、Ed.在Δu、Δd中選擇范數(shù)小的方差Δx對應(yīng)的期望Ex和點集Qx，由于期望Ex是一個空間點，因此只需要從這個空間點引出一條向量為（A，B，-1）的直線l，并從點集Qx中找一點t求取其到直線l的距離.計算通過t點的平面方程式（4）：

將t點坐標代入（x，y，z）中求D.現(xiàn)已知經(jīng)過期望點的直線方程如式（5）所示：

將平面方程與直線方程聯(lián)立可以求解出期望點在平面中的投影點s.接下來就可以計算出點t與投影點s的歐式距離d，實質(zhì)上d就是點t到l的距離.在Qx中找一點tm使得其d的數(shù)值小于等于其他點的d的數(shù)值.將Q中全部點坐標減去tm坐標獲得空間體Q′.對Q′進行旋轉(zhuǎn)變換，進行旋轉(zhuǎn)變換時可使用基于四元數(shù)的旋轉(zhuǎn)矩陣.四元數(shù)q內(nèi)每個元素的定義如公式（6）所示：

式中：（nx，ny，nz）是旋轉(zhuǎn)軸的單位向量，是圍繞該旋轉(zhuǎn)軸的正向角度.因此只需求出旋轉(zhuǎn)軸和所需的角度即可.現(xiàn)已知向量（A，B，-1）單位化后的向量T為（a，b，c），轉(zhuǎn)到的位置為R（0，0，1）.因此僅需算出U=T×R就可以計算出旋轉(zhuǎn)軸的向量.

即旋轉(zhuǎn)軸的向量U為（b，-a，0），θ=arcos（c）（0≤θ≤π）.代入上面的四元數(shù)中，通過四元數(shù)求旋轉(zhuǎn)矩陣后將空間體Q′轉(zhuǎn)到Q″.對空間體Q″進行二次曲面擬合，其擬合過程如式（7）所示：

將二次曲面擬合后對這部分點求高斯曲率如式（8）所示.

通過上式計算出點云A的每個點的高斯曲率后，將點云A分成n類，每類含有點的數(shù)量近似相等，并且下一類中的任何一個點的曲率都要大于上一類任何一點的曲率.接下來對每一類曲率進行隨機采樣其采樣結(jié)果為點云C.

點到點的查找方式：從點云C中抽取一點g.在點云B中按面表法的查找規(guī)則進行查找，選出與g點具有相近曲率的幾個點.最后在這幾個點中找到離g點最近一點h從而完成配對過程.點到面的查找方式為：在找到h點的基礎(chǔ)上，在點云B中找2個點m和n，使這兩點離h點的距離最近.然后令h、m、n三點共面，求g點到平面投影點k，從而完成新的配對.由于在最近距離這一條件上加入了曲率限制，使得算法在穩(wěn)定性、適用性、迭代速度等方面都有不同層次的上升.

3 數(shù)值實驗結(jié)果

面表法生成與查找時間如表1所示.

表1 面表法的查找與生成時間對比Tab.1 Search and generation time contrast of surface list method ms

根據(jù)表1中測試的結(jié)果可以發(fā)現(xiàn)面表法相對于八叉樹法的快速性.由于八叉樹法是針對整部點云進行查找的算法，因此該算法需對整部點云進行查找；而面表法可以通過包圍盒間的關(guān)系進行查找，從而大大減少點云的查找速度.表2、表3給出的是經(jīng)典ICP算法與本文算法對比的迭代值表格.

表2 初值精度較好的2種方法迭代結(jié)果Tab.2 Iteration results of better initial precision of two methods

表3 初值精度較差的2種方法的迭代結(jié)果Tab.3 Iteration results of worse initial precision of two methods

圖3所示為在ICP算法未匹配前對兩幅點云進行了標記點粗匹配，因此該算法能夠很快收斂到兩幅點云匹配精度較高的位置.

圖3 單純ICP匹配結(jié)果Fig.3 ICP matching result

圖4所示為未經(jīng)過標記點粗匹配而將3D掃描儀的掃描結(jié)果直接使用本文算法進行匹配.

圖4 基于曲率ICP算法匹配結(jié)果Fig.4 Matching results of ICP algorithm based on curvature

由于基于曲率特征的匹配，所以兩幅點云依舊能夠收斂到正確位置.其中表2的迭代對比是在初值誤差為0.561的拼接的結(jié)果.在這種情況下經(jīng)典ICP算法使用了10次迭代，而本文算法僅僅使用了7次迭代.在表3對應(yīng)的圖4的迭代結(jié)果中可以發(fā)現(xiàn)，在出現(xiàn)較差初值時，ICP使用了122次迭代，而迭代后的精度只有0.670 429.這個精度沒有任何實際意義，因為在圖3中的未配準前的精度僅僅是0.561 57，并且在圖3（a）中可以看出兩幅點云有較大差距.而使用本文算法后通過24步迭代就可以獲得0.241 625 93的精度.表中無論ICP與本文算法都寫有“搜索域變化”，這也是面表法所特有的.當兩部點云旋轉(zhuǎn)到適當精度時可以調(diào)整比較合適的搜索域來加速整個算法的收斂速度.

4 結(jié)論

本文根據(jù)多視角點云的配準要求提出了面表法與基于曲率特征的ICP算法，并詳細介紹了如何構(gòu)造面表來對點云進行快速訪問.根據(jù)表1中記錄的結(jié)果可知，面表法的生成速度比八叉樹方法的生成速度平均快406 ms，而查找速度平均少53.5 ms.通過實驗表明，本文所提出的改進的ICP算法要比經(jīng)典的ICP算法迭代次數(shù)平均少8.5次.在初值不好的情況下，改進的ICP算法收斂精度可以超過經(jīng)典ICP算法.

[1]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）：39-52.

[2]MARTíNEZ Jorge L，REINA Antonio J，MANDOW Anthony，et al.3D registration of laser range scenes by coincidence of coarse binary cubes[J].Springer-Verlag，2012（23）：857-867.

[3]LENA Maier-Hein，F(xiàn)RANZ Alfred M，DOS SANTOS Hiago R，et al.Convergent iterative closest-point algorithm to accomodate anisotropic and inhomogenous localization error[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34（8）：1520-1531.

[4]SACHAROW A，BALZER J，BIERMANN D，et al.Non-rigid isometric ICP：A practical registration method for the analysis and compensation of form errors in production engineering[J]. Computer-Aided Design，2011（43）：1758-1768.

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

[6]吳祿慎，孔維敬.基于特征點的改進ICP三維點云配準技術(shù)[J].南昌大學學報：工科版，2008（3）：294-297.

[7] 程效軍，施貴剛，王峰，等.點云配準誤差傳播規(guī)律的研究[J].同濟大學學報：自然科學版，2009（12）：1668-1672.

[8] 王程冬，程筱勝，崔海華，等.SIFT算法在點云配準中的應(yīng)用[J].傳感器與微系統(tǒng)，2012（2）：149-152.

[9] 張蕾，冀治航，普杰信，等.約束改進的ICP點云配準方法[J].計算機工程與應(yīng)用，2012（18）：197-200.

[10]鄭德華，岳東杰，岳建平.基于幾何特征約束的建筑物點云配準算法[J].測繪學報，2008（4）：464-468.

[11]王欣，張明明，于曉，等.應(yīng)用改進迭代最近點方法的點云數(shù)據(jù)配準[J].光學精密工程，2012（9）：2068-2077.

[12]張金魁.基于曲面的局部配準算法[J].科技資訊，2011（9）：68-69.

[13]周春艷，李勇，鄒崢嶸.三維點云ICP算法改進研究[J].計算機技術(shù)與發(fā)展，2011（8）：75-77.

[14]SONG Limei，DONG Xiaoxiao，XI Jiangtao，et al.A new phase unwrapping algorithm based on three wavelength phase shift profilometry method[J].Optics&Laser Technology，2013，45：319-329.

[15]SONG Limei，CHEN Changman，CHEN Zhuo，et al.Essential parameters calibration for the 3D scanner using only single camera and projector[J].Optoelectronics Letters，2013，9（2）：143-147.

Points registration of same objects with different view

CHEN Zhuo，SONG Li-mei，CHEN Chang-man，TANG Huan
（Key Laboratory of Advanced Electrical Engineering and Energy Technology，Tianjin Polytechnic University，Tianjin 30087，China）

Two point clouds in two different perspectives is managed by the method of surface and then the ICP algorithm is adopted based on curvature characteristic to improve the registration process.The surface method for processing the acquired point clouds from two different perspectives is used firstly.Then the curvature of two point clouds based on the surface method is calculated,and classify one of two point clouds by the curvature size and sample randomly from different classes.According to the result of random sample,to find the corresponding points which is in another point cloud in accordance with the principle of the curvature first,distance second.At last,calculate rotation matrix and translation matrix of the first point cloud to complete the registration process.Experimental results show that under the condition of the same mass point cloud,surface table generation time is less than the octree generation time on average 406 ms while the finding time is less than average 107 ms.What′s more,the ICP algorithm for curvature features based on curvature features achieves the precision of 0.241 625 mm.It can be basically satisfied the requirements of the multi-view point cloud of high registration precision,fast computing speed,etc.

object；view；points′registration；ICP algorithm；points′management

TP391.7

A

1671-024X（2014）01-0045-05

2013-08-12

國家自然科學基金（60808020，61078041）；天津市應(yīng)用基礎(chǔ)及前沿技術(shù)研究計劃（10JCYBJC07200）

陳 卓（1988—），男，碩士研究生.

宋麗梅（1976—），女，博士，教授，碩士生導師.E-mail：liymay1976@126.com