SegGraph：室外場景三維點云閉環檢測算法

廖瑞杰 楊紹發 孟文霞, 董春梅

1(計算機科學國家重點實驗室(中國科學院軟件研究所) 北京 100190)2(中國科學院大學 北京 100190)3 (中國科學院軟件研究所 北京 100190)

隨著機器人技術的快速發展，移動機器人正在逐步走向完全自主化，而同時定位與地圖創建(sim-ultaneous localization and mapping, SLAM)是機器人能否真正實現完全自主化的關鍵技術之一[1].SLAM是指機器人在未知環境中從某個未知位置開始移動，根據運動傳感器(如里程計等)獲得的信息及環境傳感器(如相機、激光雷達等)獲得的場景信息，在移動過程中同時自主近似計算出當前位置、姿態、運動軌跡并漸進地構建環境地圖.每一步的近似計算和漸進建圖都因運動傳感器的信息偏差而產生誤差，誤差會不斷累積.閉環檢測(loop-closure detection)[2]是避免誤差過多累積的關鍵模塊.閉環檢測的任務是根據環境傳感器信息判斷當前機器人位置是否與之前某時刻位置鄰近，以抵消運動傳感器的累積誤差.機器人在差距較大的不同時刻所經過的2個距離較近的不同位置合稱為1個閉環.閉環檢測的準確度和效率對SLAM均很關鍵.如實際閉環被正確檢出，則可大幅減少相應2個時刻位姿等信息估計的誤差，并進而校正全局相關時刻位姿和地圖信息的誤差.如對在實際相距較遠位置所得的2組點云誤判為閉環，則可能導致全局位姿和地圖信息的近似計算出現較大偏差，甚至導致約束信息不一致而不可解.SLAM的未來發展趨勢是應能支持機器人在大范圍場景長時間自主移動[3].在這些應用場景中，閉環檢測尤其關鍵，難度也更大.

閉環檢測研究依應用場景大致可分為室內場景和室外場景2類，依所用環境傳感器可大致分為基于視覺傳感器(如雙目相機)所得圖像數據和基于三維激光雷達所得點云數據兩大類.本文專注于基于三維激光雷達的室外場景閉環檢測.深度相機能同時獲得關聯的圖像及點云數據，但其只適用于室內場景，而且其所得點云深度信息精度遠小于激光雷達.在室外場景中，由于視覺傳感器所得圖像對光照、天氣等的影響甚為敏感，而三維激光雷達通過激光對環境進行高分辨率掃描獲得環境中各點在雷達坐標系中的位置信息，其所得信息不受光照、天氣等影響，而且精度遠高于從視覺傳感器圖像所估計出來的位置幾何信息.故室外場景閉環檢測當前研究更傾向于基于三維激光雷達所得點云數據.

Fig. 1 Flow of algorithm SegGraph圖1 SegGraph算法流程

基于三維激光雷達所得點云的閉環檢測本質是將2組點云進行比較，以判斷它們是否有較高相似度.在SLAM過程中，將當前時刻所得的1組點云分別與過去某時間段內選取的若干組點云一一進行閉環檢測，將判斷為閉環的2組點云認為是在相鄰近位置所得，并將由此2組點云鄰近而產生的全局約束融入到全局的定位與建圖計算中.本文提出適用于室外場景基于三維激光雷達所得點云數據的新的閉環檢測算法，命名為SegGraph.對作為輸入的2組點云A和B，SegGraph的流程如圖1所示，主要分為點云分割、點云簇圖構建、點云簇特征提取、K-公共子圖檢測四大模塊.

1) SegGraph對點云A和B分別分割成多個點云簇，分割前先對點云作預處理移除大地平面.大地平面通常是場景中最大的平面及對點云相似度判定最沒有參考價值的平面，并且該平面連接了大部分的小平面如建筑物的外墻、汽車表面等，移除大地平面能避免其對點云分割準確度的影響.

2) 以A中點云簇為頂點、以點云簇圖心間距離為邊權值構建完全的帶權無向圖GA，使用同樣的方法對B構建完全圖GB.

3) 判斷GA和GB是否存在有K個頂點的公共子圖，其中K是設定的參數.在匹配GA和GB的子圖時，我們以邊權值(即點云簇圖心間距離)為主要匹配依據.這是因為點云數據中的噪聲及點云分割方法的不完美會導致從鄰近地點得到的2組點云被分割成差別很大的點云簇集，尤其是同一物體表面可能會表現為面積差別很大的點云簇.然而點云簇圖心間距離則相對穩定，這在第3節中有詳細例子說明.另一方面，為提高子圖匹配效率，我們分別對GA和GB中點云簇提取其具有代表性的局部特征，以用于對匹配過程進行剪枝操作和優化，這些特征包括圖心、法向量等.

K-公共子圖的判定是很著名的NP-hard問題[4].我們提出了一個近似算法，基本思路如下：在初始化階段，分別從GA和GB中選取匹配的邊，并組成匹配的2-公共子圖.假如選擇不唯一，則從符合要求的邊對中隨機選取.在遞歸階段，假設當前已找到GA的-子圖HA和GB的-子圖HB，使得HA與HB匹配,其中

本文主要貢獻有3個方面：

1) 提出以邊匹配為主要依據的基于K-公共子圖判定的室外場景三維點云閉環檢測算法SegGraph，提出解決其中核心問題——K-公共子圖判定的近似算法.

2) 基于C++語言和開源的第三方點云庫(point cloud library, PCL)①http:pointclouds.org實現完整的SegGraph算法，代碼在GitHub上發布②https:github.comJarilySegGraph.

3) 以廣被采用的KITTI(Karlsruhe Institute of Technology and Toyota Technological Institute)城市街景數據集③http:www.cvlibs.netdatasetskittieval_odometry.php評估SegGraph，實驗結果顯示SegGraph有良好的準確度和運行效率.

1 相關研究工作

基于激光雷達所得三維點云的室外場景閉環檢測是近年來的研究熱點，仍為一大挑戰.主要有3個難點：1)單組點云含點個數數量龐大(如KITTI數據集中單組點云約含12萬個點)，點在空間分布不均勻，疏密不一；2)點云中各點數據噪聲很大，這是目前激光雷達測量技術的不完美所致；3)激光雷達只能測量不被阻擋的物體表面的點的空間位置，對被阻擋的表面無法取得數據，這就可能導致在相鄰很近但視角不同而得的2組點云可能差別很大.閉環檢測的本質是判別2組點云是否有較高的相似度，從已有研究工作看主要有2類方法.

第1類方法是2組點云點對點的直接匹配.在這類方法中最著名并被廣泛采用的是最近鄰迭代算法(iterative closest point, ICP)[5]和它的改進算法[6].假設從里程計信息或其他方式已取得2組點云的大致幾何轉換對應關系，ICP算法利用迭代一步步近似計算出誤差越來越小的2組點云的幾何轉換對應關系.ICP算法的局限性是需要已有大致精確的幾何轉換對應關系.點對點直接匹配方法還有適用范圍更廣并且不需要先驗信息的4點(4-points congruent sets, 4PCS)算法[7]和它們的改進算法，如超級4點(super-4PCS)算法[8]等.因單組點云含點個數龐大，點對點直接匹配計算效率并不高.另外，此方法對個別點測量誤差較為敏感，容易因局部部分點誤差而導致全局匹配的大偏差.

第2類方法是基于描述子的點云匹配.首先為2組點云各計算出1個較簡約的描述子，然后通過比較描述子來衡量2組點云的相似度.與點對點直接匹配方法相比，基于描述子的方法計算量相對較小，受局部點測量誤差影響也相對較小.描述子的計算方法主要基于3個方面：1)基于場景點云的局部特征；2)基于場景點云的全局特征；3)基于對場景點云進行分割所得的平面集或者物體集.

基于點云局部特征的描述子算法大多是從點云中選取關鍵點并從這些關鍵點抽取局部特征形成特征向量.Bosse和Zlot[9]通過構建1個投票矩陣計算每點經其最近的若干個鄰近點投票所得權值，再基于這些權值選取關鍵點建立描述子，稱為三維Gestalt描述子.Gawel和Cieslewski[10]也用了類似的方法.Zhuang和Jiang[11]則將點云的局部點集轉換成方位圖像,并從這些圖像中計算出SURF(speed up robust features)描述子.Rusu等人[12]采用較經典的快速點特征直方圖(fast point feature histograms, FPFH)構建描述子.受FPFH描述子構建方法的啟發,又產生了視點特征直方圖(viewpoint feature histogram, VFH)[13]描述子和CVFH(clustered viewpoint feature histogram)[14]描述子等.

基于全局特征的描述子計算主要是提取點云的若干全局特征并加以組合構成全局描述子.Rohling等人[15]首先將點云中的點按高度值分成若干層，然后為每層計算出一維的直方圖，最后將這些直方圖組合起來構成全局描述子.2組點云的全局描述子以它們之間的Wasserstein距離來衡量相似度.Granstr?m等人[16]提取出點云中具有旋轉不變性的全局特征并將其組合構成全局描述子，這些具有旋轉不變性的特征包括體積、法向量、距離直方圖等.描述子的匹配用機器學習中用于分類的AdaBoost算法來完成，項皓東[17]繼續了該方法的研究，在一些細節方面做出了相關改進，同樣是把機器學習中的相關算法和傳統方法相結合.Magnusson等人[18]首先將點云按三維網格劃分為多個子集，然后計算每個子集中局部點云的形狀屬性(如球形、線狀或平面等)，最后將每個子集的形狀屬性描述組合構成點云的全局描述子.He等人[19]首先計算點云在多個預先選定的二維平面上的投影并對每個投影構建1個向量，然后將從各投影所得向量組合成1個全局矩陣，最后以對全局矩陣進行奇異值分解所得的左、右奇異向量構成全局描述子.各投影向量描述的計算方法是將平面分成許多小塊并計算各小塊里面所包含的點的個數.

基于點云分割所得平面和物體構建描述子是近年來較新的思路,其能兼顧到點云中的局部特征和全局特征.Fernandez-Moral 等人[20]研究基于RGB深度相機所得點云數據的室內場景閉環檢測，其方法首先從2組點云中分別檢測出屬于某個平面的若干點子集，再對2組點云的平面進行匹配，尋找相匹配的構成場景某一局部的2組平面子集.該方法只適用于有較多含平面表面物體的室內場景，并依賴RGB圖像選取場景某一局部，并不適用于室外場景激光雷達所得三維點云的閉環檢測.

我們的方法SegGraph受SegMatch及其改進方法的啟發，并克服了這2個方法的不足.SegMatch在將2組點云所得的點云簇集進行匹配時，忽略了點云簇間距離的信息，故對閉環檢測準確率影響很大.而改進它的方法中，2組點云的點云簇要首先進行匹配，但在真實的室外場景中，受限于點云分割算法的辨識能力及點云數據中的噪聲干擾，從相鄰很近地點所得的點云簇很難形成一對一的匹配.

SegGraph首先采用受噪聲點干擾程度更小的區域增長分割算法將2組點云A和B各分割成多個點云簇，該方法分割出來的每個點云簇近似于1個光滑的表面，并保留了點云中的關鍵局部特征.假定A和B具有較高的相似度，即使A和B中有很多點云簇難以形成一對一的匹配對，但點云簇間距離是較為穩定的信息，因此，我們以A和B中的點云簇為頂點構建1個帶邊權值的完全圖GA和GB，其中邊的權值是點云簇圖心間的距離.然后我們再以邊匹配為主，檢測GA和GB是否含1個足夠大的(帶權)公共子圖.在公共子圖檢測中，我們將點云簇在分割中較穩定的局部特征如圖心、法向量等作為輔助判定依據，以提高公共子圖的檢測效率.在第4節中的實驗結果顯示了SegGraph能夠取得良好的準確度和運行效率.

2 點云分割與點云簇局部特征提取

本節將詳細介紹 SegGraph算法的第1步——點云分割，即將2組輸入點云分別經移除大地平面后分割成多個點云簇.為了提高SegGraph中K-公共子圖判定的效率，我們還將從每個點云簇中提取其具有代表性的局部特征，包括圖心、法向量、點云數量等.

2.1 大地平面移除

Fig. 2 Visualization of before and after ground plane removal for point cloud 2, sequence 06 KITTI圖2 KITTI 06 序列的第 2 組點云移除大地平面前后的可視化

SegGraph專注于處理室外場景的點云數據，大多數此類場景如城市街景等均有1個較顯著的大地平面.通常大地平面是場景中面積最大的平面，也是對場景相似度比較最沒有參考價值的平面.故先將大地平面移除可以大大減少場景相似度比較的計算量.

SegGraph采用一致性分割算法(SAC segmen-tation)[24]來移除點云中的大地平面.一致性分割算法的功能是從點云中提取與指定目標模型相對應的點云子集，如平面、球體、圓柱等.SegGraph用該算法提取出點云中最大的1個平面，認為其是大地平面，并將其移除.圖2顯示了KITTI數據集 06序列第2組三維點云數據的可視化圖像和將該組點云移除大地平面后的可視化圖像.

2.2 點云分割

SegGraph采用區域增長算法[25]對移除大地平面后的點云數據進行分割.其算法包含3個步驟：

1) 計算曲率.對點云中每個點p，以與p在1個很小的指定范圍內的鄰近點子集信息計算p的曲率.

2) 選取初始種子點集.以點云中曲率小于指定閾值的點構成初始種子點集.

3) 區域增長.從種子點集中取出1個點p，將以p為基礎點構建1個可以近似認為是平滑表面的點云簇，該點云簇包含與p距離在一定范圍內且與p的法向量夾角小于指定閾值的所有點.

點云數據經移除大地平面和分割后，將形成1個點云簇集，每個點云簇可以近似地視為場景中某個平滑表面的一部分.圖3顯示了從KITTI數據集06序列第2組點云所得點云簇集合的可視化圖像，其中，同一個點云簇內的點以相同顏色顯示，相鄰的點云簇用不同的顏色顯示.

Fig.3 Visualization of point clusters resulting from segmentizing point cloud 2, sequence 06, KITTI圖3 KITTI 06序列第2組點云分割所得點云簇集的可視化

2.3 點云簇局部特征提取

為提高SegGraph后續K-公共子圖檢測的效率，我們對點云分割所得點云簇提取關鍵的局部特征.對每個點云簇，我們計算出圖心、法向量、曲率、點的個數等信息.這些信息將輔助SegGraph后續K-公共子圖檢測進一步優化.

3 K-公共子圖檢測

SegGraph的第2步是就2組點云A和B分割所得的點云簇構建帶權值的完全圖GA和GB，并以檢測GA和GB是否含有K-公共子圖來判定A和B的相似度.從點云簇提取的特征將作為輔助匹配信息以提高K-公共子圖檢測的效率.本節將詳述SegGraph中建圖與K-公共子圖檢測算法.

3.1 建 圖

3.2 K-公共子圖檢測

我們將判定2組點云A和B是否相似轉化為檢測GA和GB是否含有K-公共子圖，其中K是預先設定的整數.我們稱GA和GB含有K-公共子圖當且僅當存在UA?VA，UB?VB，|UA|=K=|UB|，而且以UA為頂點集的子圖HA與以UB為頂點集的子圖HB能相匹配，其中HA和HB為完全圖.更確切地說，存在從UA到UB的一一對應的映射f，滿足：

2) 對UA中任意頂點uA，uA所代表的點云簇的圖心、法向量等特征與f(uA)所代表的點云簇的相應特征的差值在指定閾值內.

第1節提到的SegMatch及其改進方法均基于上述的假設，即依據點云簇的形狀、面積及其他局部特征能使2組點云A和B分割所得的大多數點云簇能夠形成唯一匹配，即A中大多數點云簇vA能在VB中找到唯一1個vB，使得vA與vB的形狀、面積及其他局部特征匹配.而這個假設在實際場景所得點云數據的分割中是很難滿足的.主要原因有3點：

1) 激光雷達測量的誤差會使三維點云數據含有一定的噪聲，并且激光雷達所獲取的點云中點的分布并不均勻，且疏密不一.

2) 激光雷達只能掃描未被阻擋的物體表面，視點與視角的輕微變化及場景中瞬間出現的動態物體如車輛等均會使點云數據產生較大的偏差.

3) 點云分割算法有局限，無論是SegMatch中采用的歐基里德分割算法，還是本文采用的區域增長分割算法，均不能完美地使分割出來的點云簇與場景中的實際物體表面一一對應，其他點云分割算法也無法避免此問題.

因而，我們將點云簇間距離作為點云相似度比較的主要依據.圖4展示了KITTI數據集06序列第2組點云和第836組點云在分割后所得點云簇集的可視化圖像.

在圖4的2組點云局部圖中，同個點云簇內的點以相同顏色顯示，鄰近的點云簇之間用不同的顏色顯示，根據KITTI提供的位姿信息，這2組點云獲取地點(即三維激光雷達所處位置)相差僅為0.265 m，可以將2組點云近似看作是對同一個場景的掃描，圖4中X與Y為同一個位置分割出來的2個點云簇，但其面積差別很大，X′與Y′也是類似的情況，但X圖心與X′圖心間距XX′和Y圖心與Y′圖心間距YY′相差卻不大，可作為2組點云相似度比較的主要依據.另一方面，X與Y，X′與Y′的圖心、法向量等信息基本一致，可以作為輔助信息提高點云相似度比較的效率.

K-公共子圖檢測是NP-hard問題.我們提出一種窮盡搜索算法來求解.

算法1.K-公共子圖窮盡搜索算法.

輸入：完全圖GA，GB，整數K，以VA，VB分別記GA，GB的頂點集，以w(v,v′)記GA或GB中邊(v,v′)的權值；

輸出：布爾值，即GA，GB是否含K-公共子圖.

①w(eA)與w(eB)相差小于指定閾值；

2) 初始化.令UA，UB為空集，=0，fAB為空映射.在K-公共子圖搜索過程中，UA是GA頂點集的子集，UB是GB頂點集的子集，fAB是從UA到UB的一一映射.UA，UB，fAB聯合代表已構建的含個頂點的公共子圖，其中|UA|==|UB|，≤K.

3) 公共子圖搜索.調用算法2搜索公共子圖，DetectSubGraph(GA,GB,K,UA，UB,fAB,).

算法2.DetectSubGraph公共子圖搜索算法.

輸入：GA,GB,K,UA,UB,fAB,,其中GA,GB,K同算法1中，UA，UB，fAB聯合構成GA，GB的有個頂點的公共子圖，且≤K；

輸出：布爾值，即UA，UB，fAB是否能擴展為GA，GB的K-公共子圖.

2) 枚舉所有滿足下列條件的頂點對(vA,vB)，記為CVP(candidate vertex pairs).

①vA是GA中在UA外的頂點，vB是GB中在UB外的頂點.

3) 依次對CVP的頂點對(vA,vB)執行下列操作.

① 遞歸調用DetectSubGraph(GA,GB,K,UA∪{vA}UB∪{vB},fAB∪{(vA,vB)},+1).

② 如果返回值為真，則返回真并退出算法.

4) 若至此，則說明CVP中不存在頂點對能與UA，UB，fAB聯合擴展為GA，GB的K-公共子圖，故搜索失敗，返回假并退出算法.

3.3 K-公共子圖檢測近似算法

對實際移動機器人定位與建圖應用，我們提出更高效的K-公共子圖檢測的隨機搜索算法.隨機搜索算法與窮盡搜索算法架構相同，只需將DetectSubGraph算法的步驟3)和步驟4)替換為下列步驟：

隨機從CVP中選取1個頂點對(vA,vB)，然后執行以下步驟.

① 遞歸調用DetectSubGraph(GA,GB,K,UA∪{vA}UB∪{vB},fAB∪{(vA,vB)},+1).

② 如果返回值為真，則返回真并退出算法；如果返回值為假，則返回假并退出算法.

很顯然，窮盡搜索的最壞復雜度是指數級的，隨機搜索的復雜度則是多項式級的.我們在KITTI數據集的實驗表明基于K-公共子圖隨機搜索算法的閉環檢測與基于K-公共子圖窮盡搜索算法的閉環檢測這兩者的準確度差別不大，但是在時間耗損上，隨機搜索算法具有巨大的優勢.

4 實驗與結果

本文所詳述的完整的SegGraph算法均以C++實現(KITTI數據預處理部分利用了Python語言和KITTI官方提供的Python第三方庫實現).我們采用開源的PCL庫[26]來實現算法模塊的部分功能和可視化操作等.程序運行在1個圖形工作站上，其CPU為英特爾雙核i7-2600,主頻3.4 GHz，內存4 GB，操作系統64位Windows 7.我們選取KITTI三維點云數據集[27]中適合用于閉環檢測算法評估的00，05，06，07序列數據進行實驗.這4個序列的三維點云數據是以車載三維激光雷達在真實城市街道中掃描獲得.KITTI官方提供由高精度GPSIMU導航系統測得的準確激光雷達位姿信息，以供閉環檢測算法評估之用.這4個序列中各組點云的位姿信息用MatLab軟件可視化所得軌跡如圖5所示.

圖5中軌跡上每個點代表1組點云(即1次掃描)的位置.激光雷達的運動是從黃色的點開始，由黃綠藍漸變的方向移動，到達藍色的點終止.KITTI的00，05，06，07序列分別含4 541，2 761，1 101，1 101組點云.每組點云由激光雷達在某個位置掃描而得，約有12萬個點.我們以數據集提供的位姿信息作為評估閉環檢測算法準確度的依據.每個序列的各組點云是依次在運行軌跡上的位置掃描所得，所以對掃描次序間隔不大的2組點云，其對機器人定位與建圖依里程計信息估計的誤差并不大，不需再從環境信息加以校正.因而我們在實驗中只選取部分掃描次序間隔大于50的點云對作為閉環檢測實驗的樣本，即對我們選取的每個點云對樣本(A,B)，A和B屬于同一個序列，若A是第iA次掃描所得，B是第iB次掃描所得，則|iA-iB|>50.

Fig. 5 Pose information of KITTI sequences 00,05,06,07圖5 KITTI 00，05，06，07序列的位姿信息

對每個點云對樣本(A,B)，設A和B分別是激光雷達位于全局三維坐標系中位置pA和pB處獲得，若pA，pB相距(歐基里德距離)小于3 m，則認為A，B構成閉環，稱(A,B)為1個正樣本；若pA，pB相距大于或等于3 m，則認為A，B不構成閉環，稱(A,B)為1個負樣本.

按上述實驗設定，我們計算出KITTI 00序列共有7 403個正樣本，由于負樣本數量太多(由圖5可知，激光雷達車重復經過的點占比很少)，我們只從00序列中負樣本中隨機選取10 274個，即對00序列，共采用17 677個樣本進行閉環檢測算法評估.同理，對05，06，07序列，我們選擇所有的正樣本并隨機選取部分負樣本進行實驗，具體來說，05序列共采用4 827個正樣本和10 274個負樣本，06序列1 577個正樣本和10 794個負樣本，07序列1 858個正樣本和11 242個負樣本.

我們依慣例[16]以檢測率D(detection rate)，丟失率MD(missed detection rate)，誤報率FA(false alarm rate)三個指標來衡量閉環檢測的準確度.令P表示實驗中正樣本總數，N表示實驗中負樣本總數.用TP表示實驗中被閉環檢測算法判定為閉環而實際為閉環的樣本數量，用FN表示被算法判定為非閉環而實際為閉環的樣本數量，用FP表示被算法判定為閉環而實際為非閉環的樣本數量，則3個指標的計算公式為

其中,D+MD=1.

好的閉環檢測算法應做到使檢測率很高，丟失率偏低，而誤報率極低，這是因為在機器人即時定位與建圖應用中，閉環通常是在機器人軌跡中成段連續出現的，見圖5中黃色點和藍色點的重疊部分.具體地說，如果存在第i組點云(由第i次掃描所得)與第j組點云形成閉環(i

每個序列參數K的設定是對該序列分別以K=7,8,9,10,11,12運行并綜合選取準確度最優的對應K值，原則是誤報率應極低而檢測率較高.總的來說，單組點云分割后所建的圖頂點數約為40，K的設定要適當.若K取得太小，則容易將許多稍有相似但實際上不是閉環的點云對誤判為閉環；若K取得太大，則因點云數據噪聲影響容易將許多實際為閉環的點云對誤判為非閉環，并且導致K-公共子圖判定的運行時間過大.表1列出了KITTI 06序列在K取不同值時的實驗結果：

Table 1 Accuracy of SegGraph on KITTI Sequence 06 forDifferent Values of K

從表1可以看出，當K=10時，SegGraph在KITTI 06序列上的誤報率只有0.26%，而檢測率仍高達94.23%，所以對這個序列我們將參數K設定為10.其他序列參數K的設定與06序列同理.我們最終的實驗結果見表2:

Table 2 Accuracy of SegGraph on KITTI Sequences00, 05, 06, 07

實驗表明我們提出的SegGraph閉環檢測算法在KITTI 4個序列中都取得了理想的檢測率和較低的丟失率.在誤報率方面，06序列的效果最為明顯，僅為0.26%；00，05序列誤報率都能控制在3%左右；07序列的誤報率偏高，達到了8.74%，由圖5的位姿信息可看出，07序列和其他序列最大的不同在于07序列中激光雷達車幾乎沒有重復走過同一段路線，即圖5中顏色幾乎沒有重合的部分，所以導致了閉環信息較少，同時07序列中有2段相距很遠但結構與外觀都非常相似的街道，這就導致了算法將這些不是閉環的樣本誤判為閉環，該序列在其他閉環檢測算法的實驗中[19]效果也不理想.

我們還測量了SegGraph的運行時間，對單個點云對，SegGraph運行分兩大部分：第1部分是點云分割和點云簇局部特征提取時間；第2部分是K-公共子圖檢測.由于正樣本與負樣本在第2部分所花時間差距甚大，我們對正負樣本在第2部分所花時間分開測量.表3給出了KITTI 06序列的運行時間統計(單位為s)，其中tmin和tmax分別表示單個點云對的最小耗時和最大耗時，tavg表示所有點云對的平均耗時.其他序列的運行時間與06序列類似.

Table 3 Running Time of SegGraph on KITTI Sequence 06表3 SegGraph在KITTI 06序列上的運行時間 s

從表3可以看出，SegGraph第2部分時間中，正樣本的檢測時間大約是負樣本檢測時間的4倍，這是由于在正樣本中，邊匹配成功的較多，相應迭代的次數就更多，所以花費的時間就更長.從總體時間上看，第1部分占據了大部分時間，這是因為在該過程中，使用了區域增長算法來進行點云分割，該算法需要求出點云中每個點的曲率和法向量，這個步驟需要消耗大量的時間.相比于其他適用于城市街道的點云分割算法如歐基里德分割算法，雖然區域增長算法在時間上不占優勢，但是歐基里德算法分割的結果為無規則狀的點云簇，而我們所采用的區域增長分割算法分割出來的點云簇則非常接近光滑的平面，這使得K-公共子圖檢測中基于點云簇局部特征優化更加簡潔和高效.同時，區域增長分割算法相對歐基里德分割算法來說更為精確且魯棒性更好，前者基于曲率的變化增長，后者根據距離的遠近聚類[22]，假如存在一些雷達掃描不可避免的噪聲點，很有可能本應屬于2個點云簇的局部點云被歐基里德算法聚為了同一類，這是因為噪聲點干擾了算法中對距離的判定.而區域增長分割算法受噪聲點干擾的程度遠沒有歐基里德分割算法大.

區域增長分割算法中的主要耗時在于求點云中每個點的曲率和法向量.每個點的曲率和法向量只需從其鄰近若干點的幾何信息計算得出[25]，因而對點云中各個點，其曲率及法向量的計算可以并行執行.如果將這部分計算在多核或GPU平臺上實現，將能大大降低區域增長分割算法的運行時間.這將是我們下一步的工作.

5 總 結

本文提出適用于室外場景三維點云數據的閉環檢測算法SegGraph.算法主要有3個步驟：1)對輸入的2組點云分別移除大地平面后采用區域增長算法分割為點云簇集，并提取每個點云簇的局部特征；2)分別以點云簇集為頂點集，以點云簇間距離為邊的權值，構建無向完全圖；3)通過檢測它們是否含K-公共子圖來判定2組輸入點云是否有較高的相似度，其中K是根據實際情況可以調整的參數.我們提出了檢測K-公共子圖的高效隨機搜索近似算法.在公開數據集KITTI的4個序列上的實驗表明SegGraph有良好的準確度和運行效率.