1.引言
在計算機視覺發展初期，機器對客觀世界的視覺感覺主要依賴相機捕獲的二維圖像或圖像序列。然而世界在歐氏空間内是三維的，圖像因為僅僅捕捉了世界在某個視角下投影的資訊将在對物體的尺度和幾何屬性表征上産生不确定性。相比之下，點雲（Point cloud）作為一種最原始的三維資料表征能夠精準地反映物體的真實尺寸和形狀結構，逐漸成為了機器視覺感覺所依賴的另一種資料形式。
圖1 典型的主動式和被動式點雲傳感器。（a）Velodyne 雷射雷達及其掃描的點雲資料，（b）ZED 立體視覺相機及其捕獲的點雲資料。
點雲是一種由若幹離散、無序、無拓撲結構的三維點組成的集合，通常是三維傳感系統所擷取資料的初始形式，具有抗光照和尺度變化等優點。目前主流的點雲資料傳感器分為兩類：主動式和被動式。主動式傳感器又可分為基于 TOF（Time of Flight）系統和三角測量系統兩種，其中 TOF 系統通過測量所發射信号到達物體表面和傳回接收器之間的時間間隔來确定傳感器到物體表面的真實距離，而三角測量系統則通過兩個傳感器在不同地點對物體同一點之間的測量關系計算點的空間位置。被動式傳感器依賴圖像對或圖像序列并根據相機參數來從二維圖像資料中複原出三維資料。典型的主動式傳感器包括 LiDAR（Light Detection And Ranging）、TOF 相機、結構光傳感器等；典型的被動式傳感器包括立體相機、SFM（structure from motion）系統、SFS（shape from shading）系統等。圖1展示了 Velodyne 雷射雷達和 ZED 雙目相機以及它們捕獲的點雲資料。近年來，諸如微軟 Kinect、谷歌 Tango 平闆、英特爾 Real Sense 等廉價傳感器的湧現使得點雲資料的擷取和圖像一樣便捷，進一步推動了三維計算機視覺技術的發展。
圖2 三維點雲局部特征描述與比對示意圖
和圖像感覺類似，對于點雲資料的感覺任務包括檢測、識别、分類、分割、比對等，本專欄緻力于研究點雲視覺任務中一個基礎而關鍵的問題，即點雲之間點對點對應關系的建立。該問題也被稱作三維點比對問題，在計算機視覺、計算機圖形學、遙感、機器人等領域均有着廣泛的應用。以源點雲和目标點雲來命名兩組待比對的點雲序列，當兩組點雲之間發生了旋轉、平移等剛性變換時，稱之為剛性點雲比對資料；當兩組點雲之間發生了伸縮、仿射、變形等非剛性變換時，則稱之為非剛性點雲比對資料。本文研究的資料對象為剛性點雲比對資料，通常為傳感器在不同視角或不同場景下捕獲的剛體目标點雲資料序列。對于剛性點雲比對資料之間的點對應關系建立通常包含兩步：局部幾何特征描述和特征比對。如圖2所示，局部幾何特征描述的目的是用一個特征向量來表征隐含在局部曲面内的空間資訊和幾何資訊；特征比對的目的是通過度量兩組點雲特征集中任意兩個特征的相似性确定初始比對并篩選出正确的比對子集。當點雲資料體量較大時，在初始點雲中檢測若幹稀疏且具有區分能力的關鍵點是一種常用的預處理方案。在二十一世紀初期，曾有一系列點雲關鍵點檢測子被陸續提出，例如三維 Harris 檢測子（Harris 3D，H3D）和本征形狀簽名（intrinsic shape signature，ISS）。但最近關于點雲關鍵點檢測子評估研究指出現有的檢測子在現實應用場景資料中可重複性低且較為耗時。另外，取代傳統關鍵點檢測子的均勻采樣和随機采樣方法在目辨別别以及點雲配準應用中均被證明為一種快速有效的關鍵點選取方式。是以，目前的研究熱點主要集中在點雲局部特征描述和特征比對兩方面。
對于點雲局部特征描述子的品質評估主要展現在以下五個方面：
• 剛體變換不變性—當目标或者傳感器進行了旋轉和平移等剛體運動時，在對應點提取的局部特征應當具有不變性；
• 描述性—因為點和點之間是一一對應的，局部特征需要具有一定的鑒别能力來區分相同目标之内或不同目标之間的局部幾何模式；
• 魯棒性—局部特征需要對由于自遮擋、遮擋、嘈雜、測量距離變化等引起的孔洞、噪聲、資料分辨率變化等幹擾具有魯棒性；
• 時效性—機器人等實時性高的應用平台對于局部特征計算的速度有着嚴格的要求；
• 緊湊性—局部特征的緊湊性取決于其占用的記憶體資源，主要受特征次元和特征資料類型影響，緊湊性高的局部特征有着次元低、二值化等特點。
然而，現有的點雲局部特征仍難以充分滿足上述需求，而且對于資料模态和應用場景的變化較為敏感。對于特征比對的品質評估一方面展現在抗離群點（錯誤比對）的幹擾能力，另一方面展現在比對的效率。評估研究表明大部分現有特征比對算法存在耗時長、對高離群點率敏感的缺陷。
2.研究意義
首先從工程應用的角度來例證本研究所能帶來的社會價值，然後分析目前點雲局部特征描述與比對領域存在的難點與挑戰來表明理論研究意義。點雲局部特征描述與比對在計算機視覺、計算機圖形學、機器人學、遙感等領域具有重要的實際應用價值，對應的應用場景通常取決于兩組點雲序列的分别表征的實體含義，可分為“不同視角”、“不同時刻”、“模型-模型”以及“模型-場景”四類。照此分類，我們分别例舉點雲局部特征描述與比對在如下實際場景中的應用：
•不同視角：此類資料利用點雲之間的點比對關系旨在估算不同視角點雲序列之間的空間變換關系，進而完成姿态歸一化來得到更大視場範圍内的點雲或進行三維重建。在計算機視覺領域的應用包括三維目标重建、三維場景重建以及三維資料融合。在遙感領域的應用包括大場景遙感點雲拼接以及地形場景重建。在文化遺産保護領域的應用包括基于多目點雲拼接重建的古文物數字模型庫建構，在我國該技術已被應用于故宮數字博物館的建立。
•不同時刻：對于該類資料，點雲特征比對可以解算物體在給定時間内所産生的三維旋轉和空間位移變化，進而得到物體在三維空間中的運動資訊包括速度、角速度、動量等并能跟蹤運動物體。在計算機視覺領域的典型應用為三維運動物體的姿态跟蹤。在航空航天領域的應用包括太空非合作目标的運動位姿解算等。
•模型-模型：此類資料主要通過建立兩個屬于同一類别模型之間的特征對應關系來衡量模型之間的相似性。在計算機視覺中的應用包括三維人臉識别和三維物體分類。
•模型-場景：該類資料中模型是指感興趣目标的三維模型，場景資料則為傳感器在特定視角捕獲的、包含感興趣目标的場景資料（通常稱為 2.5D 資料），這類資料廣泛應用于嘈雜和遮擋環境中的三維目辨別别。在計算機視覺中的主要應用為三維目标檢測與識别。在機器人領域的主要應用包括物體的抓取及擺放姿态的估計。在國防領域的應用包括空對地的精準目标打擊等。
圖3 點雲局部特征描述與比對面臨的四類主要挑戰
點雲局部特征描述與比對的研究已曆經三十餘年，盡管取得了一定的進展，例如剛體變換不變性問題的解決，但是仍然面臨着如下挑戰（圖 3）：
•噪聲：由于環境的幹擾和裝置的缺陷等因素，初始捕獲的點雲資料通常含有大量不同尺度的噪聲，這種幹擾在廉價傳感器例如微軟Kinect 擷取的資料中尤為明顯。噪聲的存在将擾亂點雲的局部幾何結構，幹擾特征的精準表達。
•資料分辨率變化：盡管點雲資料具有尺度不變性，但是相同物體在不同距離被捕獲的點雲将呈現出不同的分辨率。這裡點雲的分辨率為一組點雲中任意兩個相鄰點之間的平均距離。不同分辨率的點雲對于物體局部形狀資訊的表達将産生差異，例如低分辨率的點雲難以表征物體微小的局部結構，進而進一步增加了特征描述的困難。
•孔洞：物體豐富的形狀結構也會造成某個視角下捕獲的點雲存在自遮擋現象，進一步形成了孔洞；另外某些物體的材質（例如玻璃）也會導緻點雲資料出現資料缺失。分布在孔洞邊緣的局部區域因為資料不完整的問題，将難以對局部曲面原本具有的幾何結構進行正确表征。即使在理想情況下，該曲面與對應的比對曲面之間的相似度也将大大降低，使得問題更具挑戰性。
•重複模式：現實世界中有許多物體具有軸對稱性，這種對稱性将造成重複模式的存在。由于目标的局部模式是一一對應的，這些重複模式将導緻特征比對的二義性。
上述幹擾的存在一方面影響着點雲局部特征的描述性和魯棒性，另一方面将造成初始比對集中摻雜大量誤比對而進一步給正确比對的識别帶來嚴重幹擾。最近關于點雲局部特征描述子和特征比對方法的實驗評估表明現存方法難以充分克服以上幹擾。
3.點雲局部特征描述研究現狀
點雲局部特征可按照是否基于局部坐标系來分類。我們首先回顧現有的局部坐标系方法，然後簡要介紹目前點雲局部特征描述子的研究進展。
局部坐标系
局部坐标系（local reference frame，LRF）可以分為基于協方差分析和基于點空間分布兩類。對于第一類，Novatnack等人将關鍵點的法向量定義為局部坐标系的z軸，然後為局部鄰域點計算一個協方差矩陣；最大特征值對應的特征向量在z軸的切平面上的投影向量經過歸一化後即為x軸；最後，y軸為x軸和z軸的交叉乘積。Mian等人将協方差矩陣對應的三個特征向量定義為局部坐标系的三個軸。這些基于協方差分析的局部坐标系計算方法并沒有解決參考軸符号二義性的問題。後來Tombari等人首次利用局部幾何特性解決了參考軸符号二義性的問題并提出了一種權重協方差分析方法；該方法被證明具有對噪聲魯棒的特性，然而其主要缺陷為對資料分辨率變化敏感。Guo等人提出首先對局部曲面進行三角化然後為每一個三角面片計算協方差矩陣，其中每個三角面片對應的協方差矩陣具有兩個權重；與其它基于協方差分析的方法不同，該方法首次提出對三角面片進行協方差分析并大大地提升了局部坐标系的魯棒性。
對于第二類方法，Chua和Javis以關鍵點為球心放置一個球體，得到球體與曲面的交叉輪廓，輪廓所有點中到關鍵點法向量切平面投影距離最大的點被用來計算x軸；z軸為關鍵點的法向量，y軸由其餘兩軸叉乘所得。Petrelli等人為了達到抗遮擋的目的，提出采用鄰域點集内一小部分點來計算法向量并作為z軸；鄰域邊緣區域所有點中對應的法向量與關鍵點法向量偏移角最大的點被用來計算x軸，他們後續提出利用局部深度來代替法向量偏移角作為選擇依據來提升局部坐标系的可重複性。然而，大尺度的噪聲對于x軸的計算仍将産生明顯的幹擾。
局部特征
在現有的衆多點雲局部特征描述子中，部分是針對非剛性物體的，被稱為本征局部描述子，具有抗非剛性變化的能力。在該類描述子中，Sun等人利用在曲面進行拉普拉斯-貝爾特拉米運算和其衍生的空間嵌入計算來獲得熱核簽名描述子（heat kernel signature，HKS）；HKS對等容等距變化具有魯棒性而且有一定的抗非等容等距變換能力。随後，Aubry等人憑借一種量子力學的方式來描述曲面的多尺度細節并提出波核簽名描述子（wave kernel signature，WKS），展現出比HKS更強的區分性。除了手工特征，Litman和Bronstein提出一種基于學習的最優譜變換特征（optimal spectral descriptor,OSD），主要通過學習來獲得多種濾波器并在曲面上計算不同頻率的譜特征。Boscaini等人提出各向異性傳播特征（anisotropic diffusion descriptor，ADD），通過任務驅動的學習方式計算了一系列方向性濾波器，解決了諸多應用中存在的各向同性問題。
和主流的局部特征更為接近的是另外一類針對剛性物體的描述子，可以按是否基于局部坐标系LRF劃分為兩類。對于非基于LRF的描述子，Johnson和Hebert提出了自旋圖特征（spin image，SI），他們首先将關鍵點的法向量作為參考軸然後将局部鄰域點投影到以水準和垂直投影距離為坐标的二維平面，最後通過二維累加運算的方式得到一張二維灰階圖；SI是被引用次數最多的描述子之一，但是描述能力有限、對資料分辨率變化敏感。Rusu等人提出利用點特征直方圖（point feature histograms，PFH）的方式來編碼局部曲面的形狀資訊；PFH鑒别能力很強但是極為耗時。為了解決該問題，Rusu等人後來利用簡化版點特征直方圖（simplified point feature histogram，SPFH）來構造快速點特征直方圖（fast point feature histogram，FPFH），具有快速、鑒别能力強的特點。Albarelli等人提出一種低維曲面哈希的描述子并将其應用于博弈論架構下的曲面比對問題中；曲面哈希特征主要基于多尺度的局部屬性統計直方圖計算，包括法向量夾角、積分體積以及它們的結合。
對于基于LRF的特征，Stein和Medioni基于關鍵點與測地鄰域點之間的偏移角、扭轉角和曲率關系來設計點雲的局部特征。Frome等人将二維中的形狀上下文特征（shape context，SC）擴充到三維領域并提出三維形狀上下文特征（3D shape context，3DSC）；3DSC首先将局部球域劃分為多個子空間并計算每個子空間内的點占比來計算特征描述子。Malassiotis憑借在點雲局部曲面上方的虛拟相機對點雲進行“快照”的方式進行特征表達，這種特征表達首次表明了局部深度這種屬性的強區分性，然而因為其僅擷取了局部曲面單個視角資訊的緣故，具有的描述能力仍然有限。Zaharescu等人為每個鄰域點計算了梯度向量并将它們投影在LRF的三個正交平面上；每個平面被劃分為四個象限，每個象限對應一個八維特征，最後所有象限内特征的串接形成了名為MeshHOG的描述子。Tombari等人提出了方向直方圖特征（signature of histograms of orientations，SHOT）；SHOT首先對局部球域進行空間劃分，然後為每個子空間計算一個反映子空間内點的法向量和關鍵點法向偏移角統計量的特征，最後計算每個子空間對應特征的串接向量；盡管SHOT描述性很強，但是對點密度分辨率的變化敏感。最近，Guo等人首先将局部曲面在LRF中不斷旋轉，并對每一次旋轉後的曲面進行投影來計算一些投影後點密度的統計量，最後将這些統計量串接得到旋轉投影統計量特征（rotational projection statistics，RoPS）；RoPS在多個資料集中取得了目前領先的比對性能，其不足主要為在對點分布不均的資料描述性差、計算較為耗時。和RoPS的旋轉投影機制類似，Guo等人利用LRF的三個正交軸來計算三個自旋圖特征，得到的三元自旋圖（triple spin images，TriSI）和RoPS相比抗遮擋能力更強，但仍較為耗時。
4.特征比對研究現狀
特征比對在二維和三維領域内均得到了廣泛的關注。
二維特征比對
Leordeanu和Hebert基于高置信度的比對通常以聚類方式呈現的假設，提出了一種譜分析的方法；其首先為比對集建構一個圖，每個節點代表一個對點對的比對，每條邊代表比對之間的相容性，進而建構出一個鄰接矩陣并從基于該矩陣對應的特征值發現具有一緻性的比對聚類。Torresani等人通過最小化一個關于比對相似度和空間相容性的能量函數來對初始比對進行排序打分。這兩種方法要求初始比對集具有較高的内點率。為了解決該問題，Cho和Lee将圖的機率級數與圖比對相結合，提出了一種漸進比對的架構。然而，大部分圖比對的方法可擴充性不強。Lowe設計了一種高效的方式來為比對的可區分性進行打分，主要基于計算最小與次小特征距離之間的比率；這種方法能有效解決可重複模式造成的比對二義性問題，但是缺乏對比對空間一緻性資訊的利用，得到的比對正确率較低。
三維特征比對
三維特征比對方法中有一部分是直接根據特征相似度或特征比率分數來進行正确比對篩選。幾何剛性限制被用來檢驗兩比對之間的空間一緻性。對于基于投票機制的方法，Tombari和Stefano提出了三維霍夫變換方法（3D Hough voting，3DHV）；借助于LRF之間的變換，該方法将比對投影到一個三維空間并通過找到三維空間核密度最大的點來确定一緻性比對叢集。Johnson和Hebert設計了結合距離和方向資訊的比對限制項并基于此來尋找滿足該限制項的最大特征比對聚類，該聚類則被認為是篩選出的正确比對子集；後來Chen和Bhanu采用了僅包含距離的限制項并表明該改進對于噪聲幹擾具有更強的魯棒性。Buch等人将局部限制和全局限制內建到了一個投票的架構下來判定比對的正确性。
5.點雲配準研究現狀
剛體資料之間的點對應關系最直接的應用為點雲配準，即求解源點雲和目标點雲之間的旋轉和平移資訊。Besk和Mckay提出的疊代最近點法（iterativeclosest point，ICP）為點雲配準領域最為經典的算法之一，ICP算法疊代式地尋找兩組點雲之間的對應點集并更新變換矩陣來完成配準；ICP算法是一種局部的算法，在沒有初始化的情況下容易陷入局部最優。現有的全局配準方法主要分為兩類：基于分支定界（branch and bound，BnB）或點對點對應關系。
對于基于BnB的配準方法，Yang等人提出的Go-ICP算法首次完成了ICP架構下的全局最優配準；Go-ICP算法用一個不确定性球來表達幾何邊界，在配準過程中優化和傳統ICP算法一緻的距離目标函數并根據幾何邊界推導出最小值的下界；Go-ICP設計了一種由一個外部BnB和一個内部BnB組成的嵌套BnB模式；其中外部BnB在旋轉空間SO(3)中進行搜尋，内部BnB在R3空間内搜尋其對應的最佳平移變換。Campbell和Petersson通過對齊兩組點雲對應的混合高斯模型（Gaussian mixture models，GMM）來達到配準點雲的目的，他們采用了一個和Go-ICP相比更為嚴格的幾何界限，即不确定性球的頂部區域；因為該方法在剛體變換的六維空間進行搜尋，其需要借助于GPU進行加速。Bustos等人采用了類似的幾何邊界但是建立了一種基于一緻性集的目标函數；該方法對于最大一緻性集上界的評估依賴将不确定球頂部區域從三維到二維平面上的投影。Lian和Zhang等人提出了APM（asymmetric point matching）算法來解決點集配準問題；APM将點集配準問題模組化成一個凹二次配置設定問題并在BnB架構下進行求解。Straub等人提出了一種基于點雲法向量的二階段BnB算法，其将六維剛體變換空間分解成三維旋轉空間和三維平移空間然後分别在分解後的空間内進行尋優。BnB算法盡管能找到配準全局最優解，但是通常都極為耗時。