大場景三維掃描與建模方法研究

李文浩,賈同*,呂朝輝,孫小鈞，黃俊文，張松娜

（1.東北大學信息科學與工程學院，沈陽 110819；2.中國傳媒大學信息與通信工程學院，北京 100024）

1 引言

隨著計算機視覺的快速發展，三維視覺相比二維視覺具有“降維打擊”優勢，已在觀演空間舞臺效果展示［1］、虛擬看房［2］、文物保護［3］等多領域進行應用。根據成像方式分類，目前獲取場景三維信息可分為主動視覺與被動視覺兩類方法。主動視覺主要包括結構光［4］［7］與TOF（Time of flight）［5］技術等。被動視覺主要包括雙目與多目視覺技術［6］等。

近年來，結構光已成為三維視覺的主流技術。其主要原理為將編碼光投射至物體表面，再使用相機接收該物體表面反射的結構光圖案。由于接收圖案必會因物體的立體形狀而發生變形，故可以通過該圖案在相機上的位置和形變程度來計算物體表面的空間信息。結構光與TOF、雙目視覺［32］等技術比較而言，具有精度高、非接觸等特點，在三維掃描、精準識別以及形狀測量等方面表現出了優異效果。

根據時空編碼方式，結構光可分為時間編碼和空間編碼。時間編碼方式主要包括多步相移法和格雷碼法等。空間編碼主要包括點、線、面結構光等。其中，點和線結構光［8］可以直接通過相似三角形進行測距。面結構光［9］需要進行編解碼后，才能進一步算出距離，主要有M陣列［9］、隨機散斑編碼［10］等。

獲取場景三維信息后，即可轉化為空間點云信息。由于現有技術不能單次獲取大場景的全部點云信息，因此需要對多幀點云進行配準與重建［3］。點云配準分為粗配準和精配準兩步，粗配準算法可分為兩類，一種是基于窮舉的配準算法，如RANSAC（Random Sample Consensus）配準算法［11］、四點一致集配準算法（4-Point Congruent Set,4PCS）［12］、Super4PCS 算法［13］等；另一種是基于特征匹配的配準算法，如基于點 FPFH（Fast Point Feature Histograms）特征的SAC-IA（Sample Consensus Initial Aligment）［14］、以及基于線特征的 ICL（Iterative Closest Line）［15］算法等。精配準主要采用 PNP（Perspective N Point）［16］、ICP（Iterative Closest Point）［17］及其改進算法等。

ICP可分為閾值法和單向鄰近匹配法。閾值法是通過設定的閾值對點云篩選的一種方法，原理相對簡單。單向鄰近匹配是一種比較常用的匹配算法，同時也是ICP算法在搜尋點對過程中的主要方法。

點云配準之后，需要對點云進行建模才能獲得完整的大場景模型。三維點云建模通常有兩種方式，一種是三維建模軟件主動建模，即將點云導入軟件中進行建模，如Geomagic軟件系統等；另一種是點云逆向建模，主要有泊松算法［18］及其改進算法、Delaunay Triangulation［19］、Slicing-based method［20］等算法。

本文對大場景掃描、點云配準和點云建模的相關技術進行了介紹，并采用改進算法實現大場景三維掃描與建模，獲得了高精度、高魯棒性的三維重建結果。

2 三維深度感知方法

如前所述，結構光是主動深度感知視覺的主要方法。本文提出一種基于全向環結構光［21］的深度感知方法，可歸類為線結構光范疇［8］［9］［10］。

2.1 全向環結構光深度測量系統

如圖1所示為全向環結構光深度測量模型［21］。圖中顯示了由全景相機和全向環結構光組成的深度測量單元，其中S為雙曲面焦距到激光平面的垂心距離，下面簡稱為基線距離S。基線距離由機械測量確定，決定了最終的測量精度。

圖1 全向環結構光深度測量模型

圖中描述了空間點與圖像平面的映射關系，給出了不同空間測量點在平面內的成像情況，以及測量深度與各參數之間的關系。圖中OM為雙曲面鏡的焦點，如果能在相機平面內成像則所有入射光線都交于焦點OM［21］。圖中省略了相機的鏡頭，使用透視投影的方式來描述空間幾何關系，ImageSensor表示相機內的感光元件，Camera所指位置表示感光元件所在位置，感光元件所成圖像如ImageSensor Topview所示，其中H表示圖像的行像素，W表示圖像的列像素。

空間中的點P1，P2，P3在激光平面中的測量深度分別為q1，q2，q3，α1，α2，α3為測量點P1，P2，P3到雙曲面焦距與激光所在平面的夾角。

當測量物體擋住激光的通路時，物體表面反射激光光線到雙曲面鏡，通過相機鏡頭將圖像聚焦在圖像傳感器上。如圖中可以看到不同的測量位置P1，P2，P3在相平面上對應位置為P′1，P′2，P′3。其中OM為雙曲面鏡的焦點，O′M為過雙曲面鏡焦點垂直于傳感器平面的交點，后面稱為中心投影。由圖可知，測量深度q可由S和cosα的乘積得到。

由此關系式可以得出測量深度q、基線距離S和激光平面與被測點和雙曲面鏡焦距連線的夾角α之間的關系，由此關系可以明顯看出，測量距離與基線長度和光斑在傳感器平面內坐標相關。

2.2 全向環結構光深度測量

式（1）中b為雙曲面鏡短軸，c為雙曲面鏡的長軸，f為雙曲面鏡的焦距。其中f為攝像機鏡頭的焦距，通過求得α可以求出三維空間中點P(X,Y,Z)在圖像傳感器中的映射點p(x,y)。當使用的雙曲面鏡參數已知，α只與相機平面內參θ有關，則只要標定出全景相機中心在相平面內的投影中心，再通過激光點定位算法進行激光點定位，則可以求出圖2中的角度α，帶入公式就可以求出測量深度：

圖2 深度測量幾何模型俯視圖

2.3 點云三維坐標計算

根據圖像坐標和空間坐標的對應關系，可以計算出空間點的三維坐標信息。全向環感知系統［22］是一種以觀察者為中心的單視點全景視覺感知系統，因此在點云計算過程中采用笛卡爾坐標系［23］，坐標系如圖3所示。以單目的中心作為坐標系的原點，以中心軸沿著雙曲面鏡方向作為Z軸正方向在空間中建立三維坐標系。其中，q為空間中點到攝像頭的距離，zeta為舵機旋轉角度，phi為全向環結構光中每一點相對于像素坐標系的角度。

圖3 點云三維測量原理圖

根據像素坐標系到空間坐標系的轉換，即可以得到空間坐標系中點的三維坐標公式如下式（5）：

3 點云配準方法

大場景空間大，且空間場景相對復雜。因此，本文首先聯合多種點云濾波模型完成對初始點云數據的精簡；其次提取點云關鍵點并進行多維度特征化描述；然后以特征向量為索引單位，在最鄰近搜索的基礎上，結合比率抑制和雙向篩選完成對應點對搜索，以達到快速收斂；最后根據對應點構建點云變換模型，求出最優解，實現點云配準。

3.1 點云預處理

大場景三維點云地圖的點云數據量較大，點的數量一般在十萬到百萬級別，如果對所有的點進行點云配準操作勢必產生過高的計算負荷。為了能夠在保留原有點云特征的情況下有效減少點的數量，最終提高點云配準效率，本文采用聯合多種濾波方法對點云進行精簡操作。

3.1.1 點云體素網格濾波

體素網格的重心P近似地表示了該網格中其他所有空間點，邊長L決定了體素網格濾波的尺度。

3.1.2 點云離群點剔除

點云分布較為密集的地方信息量就越大，相反點云分布稀疏地方信息量較少。因此離群點所表達的信息量較少，同時離群點容易影響當前點云的呈現效果，而且還可能影響整個點云的配準過程。為了能夠最大限度降低離群噪點產生的上述不良影響，本文采用統計濾波算法［25］對離群噪點進行剔除。

統計濾波算法是一種對每個點的鄰域都進行統計分析的算法。具體流程為：計算每個點到其最近的K個點的平均距離di，其中i=1,2,3…N。假設所有平均距離di滿足高斯分布，則均值μ代表了點云的平均密度，標準差σ代表了點云的密度分布。將平均距離小于設定范圍的點定義為離群點，從點云數據中去除，保留絕大部分滿足設定范圍的點。

3.2 點云關鍵點提取

3.2.1 ISS關鍵點提取

ISS（Intrinsic Shape Signatures）［26］關鍵點是一種通過點云局部空間幾何信息加權確定的關鍵點。遍歷點云中所有點，以每個點Pc為中心，建立空間局部坐標系，以r為半徑，搜索r鄰域內的球形空間所有點，假設鄰域中所有點的個數為n，可以根據下式（7）確定每個點所對應的權值wij：

根據式（7）計算得出的權值構建球形鄰域內所有點的協方差矩陣cov(Pi)，見式（8）：

根據協方差矩陣計算特征值λi，其中i∈{0,1,2}，如下式（9）所示：

3.2.2 SIFT關鍵點提取

點云的3D SIFT（Scale-invariant Feature Transform）［27］特征點是從圖像SIFT二維特征點到3D空間的拓展。SIFT是在不同的尺度空間中提取得到的特征點，SIFT特征點具有較強的抗光照、噪聲干擾能力，同時也不會因點云仿射變換而發生變化。SIFT關鍵點提取可歸納為以下兩個主要步驟。

1.尺度空間極值檢測

要在尺度空間中進行極值檢測首先需要構造高斯差分金字塔模型。三維空間中的尺度信息L(x,y,z,σ)定義如下式（10）：

為了能夠高效檢測出三維空間中的特征點，采用高斯差分DoG（Difference of Gaussian）算子［28］進行尺度空間極值點檢測。

式（11）中，k為乘法因子，利用k可以得到不同尺度。

每個空間點都要在其鄰域內進行篩選比較從而得到極值，包括極大值和極小值。二維圖像中的中間點需要和鄰域內的8個點進行比較，三維空間中的中間點則需要和周圍26個點進行比較。如下圖4所示：

圖4 多維空間鄰域檢測

2.極值點方向確定

極值點方向角θ確定如下式（12）所示：

式（12）中，(xc,yc)為三維空間中心點P坐標。

3.2.3 關鍵點對比與分析

前兩小節分別介紹了最常用的兩種3D特征點檢測算法，本小節對這兩種3D特征點進行對比實驗。

圖5為斯坦福大學利用三維掃描儀構建的兔子點云模型，該模型包含14806個點。本文對該模型進行了點云的兩種關鍵點提取實驗，實驗效果圖如下圖6所示。

圖5 斯坦福點云模型

圖6 兩種特征點效果提取圖

表1 兩種關鍵點數據分析

從外觀上看，ISS關鍵點在所有區域的分布更為均勻，而SIFT關鍵點在平坦區域特征點分布相對較少，在輪廓區域分布更為充分。在表達點云空間結構信息的過程中，輪廓信息尤為重要，因此SIFT關鍵點能夠更為良好地表達出點云的空間結構信息。

從統計數據上比較，在同樣閾值限定的情況下，SIFT關鍵點的數據量更多，這也正是SIFT關鍵點耗時較長的原因。但是大規模點云配準問題的核心在于配準結果的準確性，而不是配準過程的實時性。因此本文可以在犧牲時間的基礎上來提升結果的準確性。

綜上所述，本文選取3D SIFT關鍵點作為后續過程中的特征點。

3.3 點云特征描述

點云特征描述符是對點云特征點的信息表達，一種好的描述符能夠充分表達特征點自身以及特征點周圍的空間信息，同時具備較強的魯棒性。點云特征描述符最終以特征向量的形式進行表達。

一種合格的點云描述符需要滿足以下四點準則：一是點云經過任意三維變換，特征向量不發生任何變化；二是點云經過不同的密度采樣，特征向量保持不變；三是當點云存在部分噪點時，特征向量基本保持不變。四是特征向量本身能夠全面化表述特征點的多維信息。本文依據上述準則對點云的特征描述符進行了分析與選取。

3.3.1 點云固有特征信息

（1）顏色信息

點云中的每個點除了包含對應的XYZ空間位置信息之外，往往包含了彩色信息RGB三種分量。由于相機彩色攝像頭精度較高，在同一時間和同一場景下，物體顏色信息不會發生較大變化，同一個物體會在不同角度采集得到的點云中表現出相同且穩定的RGB分量。因此每個點的RGB分量能夠為后續點云匹配提供相應的約束。

（2）曲率信息

曲率描述了點及其局部點的彎曲程度，形狀不同的點云曲率信息相差較大，因此曲率是點云中比較重要的幾何特征。曲率的計算依賴于該點及其周圍點的坐標，但是并不會因為點云旋轉平移而發生變化，因此曲率信息是點云的固有內在特征。可以采用直接計算的方式求取任意特征點P(X,Y,Z)的曲率，具體的計算過程為：

2）計算出協方差矩陣C。

3）根據特征向量與特征值計算公式（8）計算得出協方差矩陣C的三個特征值λ1、λ2、λ3。式中，λj表示第j個特征值，vj表示第j個特征值對應的特征向量。

4）取λ1、λ2、λ3中的最小特征值λmin=min(λ1,min(λ2,λ3))。

5）根據式（12）計算特征點P(X,Y,Z)對應的曲率ρP，見式（13）。

3.3.2 PFH特征描述

顏色信息和曲率信息只能描述當前點的特征信息，當點云相對復雜時，上述特征信息不夠全面，對于相似性較高區域或者對稱區域容易出現較大的誤差。為了更好地描述該點和周圍點更深層次的空間位置關系，從而得到置信度更高的匹配點對，本文采用PFH特征描述符。

PFH［30］特征描述實質上是對曲率特征更加進一步的表達。它描述了中心點和周圍點之間的法線方向差異，同時建立統計直方圖來表述中心點和周圍點之間的幾何特征。

（1）為了計算兩點之間的法線差異，需要選取兩點連線與法向量夾角較小的一點構建uvw坐標系。計算公式為式（14）：

（2）兩點的信息包括各自的位置坐標(x,y,z)和法線方向信息(nx,ny,nz)。

如圖7所示，兩點之間的相互關系可以用一組角度α?θ以及兩點之間距離d共四個元素進行表示。如式（15）所示：

圖7 局部空間坐標系

（3）構建中心點P的統計分布直方圖。

首先計算查詢點Pq近鄰內對應的所有四個元素，如圖8所示，表示的是一個查詢點Pq的PFH計算的影響區域，Pq用紅色標注并放在圓球的中間位置，半徑為r，Pq的所有k鄰元素（即與點Pq的距離小于半徑r的所有點）全部互相連接在一個網絡中。最終的PFH描述子通過計算鄰域內所有兩點之間關系而得到直方圖，計算復雜度為O(k)。為了創建最終的直方圖，將所有四元素組以統計的方式放入一個直方圖中，這個過程首先把每個特征值范圍劃分為b個子區間，并統計落在每個子區間的點數量，前三個元素均是角度，都和法向量有關，可以將三個元素標準化并放到同一個區間內。

圖8 空間結構示意圖

本文將點云顏色、曲率以及PFH特征相結合，具體包含兩個分量。第一個分量表達了點云中點的自身信息，包括顏色信息以及曲率信息，是一個4維度分量。第二個分量表達了點云關鍵點的PFH特征，是一個125維度分量。

3.4 點云精確配準方法分析及改進

3.4.1 ICP算法中所用到的匹配方法與不足

ICP［17］算法用到的匹配方法可以細分為兩種，分別為閾值法和單向鄰近匹配法。

（1）閾值法

閾值法是通過設定的閾值進行篩選的一種方法。主要思想為：假設得到了兩個待配準點云的特征描述子集合DP和DQ，對于源點云的特征描述子集合DP中的任意一個特征描述子pi，從目標點云的特征描述子集合DQ中通過閾值判斷找到滿足閾值的描述子pj。由于閾值的限定，滿足閾值的描述子數量可能是一個也可能是一個集合。

閾值的設定和實驗結果密切相關，對于不同密度、不同大小、原始空間位置相差較大的點云，事先設定的閾值需要動態變化才能滿足實驗要求，否則會出現錯誤的匹配。同時，由于點云特征點數量較為繁多，滿足閾值要求的點可能較多，巨大的信息干擾使得ICP算法的迭代次數不斷增多。因此閾值法通常只適用于點云空間結構較為簡單、點云匹配步驟較少的情況。

（2）單向鄰近匹配

單向鄰近匹配是ICP算法在搜尋點對過程中的主要方法。單向鄰近匹配的過程為：假設得到了兩個待配準點云的特征描述子集合DP和DQ。遍歷源點云的特征描述子集合DP中的每一個元素pi，在目標點云的特征描述子集合DQ中找到與pi歐式距離最近的描述子pj，得到一對匹配的描述子(pi,pj)。與閾值法不同的是，pj具有唯一性。

單向鄰近匹配算法在尋找對應點過程中是一種單向的搜索，只能滿足從源點云到目標點云之間的搜索。假設利用單向鄰近匹配尋找得到了一組對應點對(pi,pj)，pi對應于pj點，但是并無法證明pj對應于pi點，很可能pj與其他點相對應。因此從原理上分析可知，單向的搜索過程容易出現更多的潛在錯誤點對。

3.4.2 基于雙向匹配與比率篩選的ICP配準

不論是利用閾值法進行特征點對的篩選，或者利用單向鄰近搜索策略進行特征點對篩選，以上策略均會出現大量潛在的誤匹配，因此會造成搜索過程的效率低下。造成效率低下的原因主要有三：

1）閾值的設定較為單一，匹配結果無法令人滿意。

2）單向搜索無法保證匹配點之間的雙向對應。

3）特征維度較高，只利用最鄰近歐氏距離進行比較，相似的結果可能包含有其它大量錯誤的匹配，數據干擾較大。

（1）雙向篩選

ICP［17］方法中單向搜索的基本原理如圖9所示。由于單向的搜索方式無法保證特征點對之間的相互對應，為了能夠最大限度地提升對應點對正確性，本文將原有的單向搜索策略改為雙向搜索策略，原理示意圖如圖10所示：

圖9 單向搜索示意圖

圖10 雙向搜索示意圖

圖10中，左側區域紅色標記點和右側區域藍色標記點分別為源點云P和目標點云Q中提取得到的3D關鍵點。在遍歷源點云P的所有3D關鍵點過程中，紅色標記點P3在目標點云Q中尋找得到了距離最近的點Q5。在ICP的單向搜索過程中，正向匹配點對(P3,Q5)被認定為最佳匹配點對。但是在本文雙向篩選過程中，在得到正向匹配點對(P3,Q5)后，需要對點Q5反向從源點云P中繼續尋找最佳匹配點對。如果在反向搜索過程中，P3是源點云P中距離Q5點歐氏距離最近的點，則反向匹配點對(Q5,P3)被判定為最佳反向點對。由于正向和反向的搜索結果相吻合，因此(Q5,P3)為最佳匹配點對。反之，重新遍歷源點云P中的下一個關鍵點。

（2）比率抑制

由于特征描述維度較高，當特征點存在疑似點時，如果直接利用閾值法，很容易得出錯誤的結果。如圖11所示：

圖11 存在干擾時的特征匹配

圖11中的Pi為源點云中的待匹配特征點，Q1,Q2,Q3,Q4皆為目標點云中距離Pi點最近的四個特征點。根據閾值法可以計算得出，Pi的匹配點為Q1，而其他點Q2,Q3,Q4因到Pi點距離大于Q1到Pi的距離，皆被舍棄。但是閾值法計算結果不具有可靠性，由于特征點對應的特征描述具有高維度性質，歐氏距離最近的點不一定是最佳匹配點。而在干擾點中可能存在最佳的對應點。閾值法的處理過程很容易將潛在的目標點當作干擾點去除。

為了能夠使得計算結果具有可靠性，本文提出比率抑制的方法。對于源點云中的待匹配點Pi，在尋找對應點過程中，計算最鄰近點Qf和次鄰近點Qs分別到原始特征點之間的距離比，如式（16）所示：

設定閾值ε，Lowe［10］在文章中已經給出了閾值ε的經驗閾值為0.8。比較距離比di與閾值ε之間的大小關系。如果di＜ε則認為次臨近點的干擾性較弱，最臨近點的可靠性較高。否則舍棄待匹配特征點Pi，繼續對源點云其它特征點進行查找。比率抑制的示意圖如下圖12所示。

圖12 基于比率抑制的提取效果圖

圖12中，Pj和Q1為經過比率抑制得到的匹配點對，而Q2因為距離遠遠小于Q1，認為Q2在特征匹配過程中的干擾性較弱，舍棄掉Q2點。

4 三維點云建模方法

三維點云建模方法主要是以軟件主動建模為主，通過CloudCompare［30］和Geomagic軟件［31］，對大場景點云進行建模。如圖13（a）所示為實驗室的三維點云圖，以實驗室為對象，對實驗室進行三維建模。

如圖13所示，將實驗室點云文件加載到Cloud-Compare內。首先通過軟件中的裁剪功能，手動將原始點云中的離群點和噪點去除掉，去除后的點云圖如圖13（b）所示；然后將實驗室分成若干部分，分類時可按照物品種類進行分類，比如墻面、地板、桌椅等，通過手動裁剪，將點云進行裁剪，被裁剪后的點云文件如圖13（c）所示，并將裁剪后的點云保存成pts點云文件；將裁剪后的點云加載到Geomagic軟件中，對點云進行去噪、修補漏點和優化點云后，進行封裝并轉為obj三角面片格式，如圖13（d）所示；最后將封裝后的模型導入到3DMax中，并進行拼接，拼接后將其保存為max模型文件。如圖13（e）所示為建模后的實驗室三維模型。

圖13 三維點云建模方法。（a）通過三維掃描與點云配準生成實驗室原始點云；（b）將原始點云加載到CloudCompare；（c）去除離群點和噪點；（d）對實驗室進行分類并裁剪；（e）加載到Geomagic中進行封裝;（f）通過3DMax對封裝后的三角面片進行拼接，生成完整的實驗室模型。

通過CloudCompare、Geomagic和3DMax軟件，可以快速的對原始點云進行建模。同時Geomagic軟件中本身自帶點云去噪、漏洞補全優化功能；3Dmax軟件也可以對模型進行渲染，進一步對模型進行優化，從而達到更好的效果。

5 結論

本文面向大場景三維掃描與建模關鍵問題，首先采用全向環結構光深度感知方法獲取場景的三維點云信息；然后采用基于雙向匹配與比率篩選的ICP配準算法對掃描獲得的點云進行配準，從而獲得完整的大場景點云；最后采用CloudCompare和Geomagic三維軟件對點云進行主動建模，獲得高精度、高魯棒性的大場景三維點云掃描與建模結果。