基于地標的點云拓撲地圖構建方法研究

申紫銘，郭鵬，李敏

?

基于地標的點云拓撲地圖構建方法研究

申紫銘，郭鵬，李敏

（河北工業大學機械工程學院，天津 300130）

為了提高構建復雜空間點云拓撲地圖的效率與準確性，提出了一種基于地標的拓撲地圖構建方法。對目標空間進行點云數據采集，對采集的點云根據位置信息進行區域劃分，并對每個劃分好的區域進行點云特征提取，將提取的特征作為地標信息。對每個地標做拓撲處理，構建出拓撲地圖。實驗表明，該方法可以有效地構建出點云拓撲地圖，為機器人的高效導航奠定基礎。

地標；拓撲地圖；特征提取；云數據

1 引言

目前，環境的空間表示方法主要分為兩大類，分別是幾何地圖和拓撲地圖。對復雜空間進行緊湊的表達時常通過拓撲地圖的表達方法來完成[1]。拓撲地圖是由Kuipers在1978年首先提出的，以點線面的結構組合形式來表現一個具有連通性的環境空間[2]，屬于簡潔、直觀的環境表示方法。拓撲地圖可將目標空間表示為帶有節點與節點間的相關連接線的拓撲關系結構圖，其中用節點表示目標空間中的某些重要位置點，例如拐角、桌子等，拓撲地圖中的邊用來表示不同的節點間的連接方式[3]。拓撲地圖在路徑規劃中可以起到重要作用，為機器人提供簡潔、高效的規劃策略[4]，而且對存儲空間大小與計算速度并無特別要求，所以在相同條件下拓撲地圖的效率較高[5]。

但拓撲地圖的劣勢在于其重在描述目標空間的拓撲結構，而對目標空間無精確的位置關系要求，在節點的定義與選擇方面也存在著難點，容易出現因環境的相似性造成的節點混淆等問題[6]。針對以上問題，本文提出了一種基于地標的拓撲地圖構建方法：對目標空間進行點云數據采集，對采集的點云根據其位置信息進行區域劃分，對每個劃分好的區域進行點云特征提取，將提取的特征作為地標信息，對每個地標做拓撲處理，構建出拓撲地圖。

2 目標空間的區域劃分與地標選取

2.1 目標空間的區域劃分

對目標空間進行區域劃分時需要機器人在空間中不斷行走，設置其行走步長，當走到步長值時，將經過的區域設為局部空間1，然后重復對局部空間1進行點云離散化處理，分析環境的結構特點，實現點云的權重信息精簡，以滿足實時性的要求，并對其輪廓進行分析提取特征，利用不變矩原理計算質心位置獲得其局部質心坐標1，直到劃分完整個目標空間，獲得局部空間n與局部質心坐標n.最終形成局部空間{1，2，…，n}及其局部質心坐標{1，2，…，n}。機器人的行走過程如圖1所示。

圖1 機器人的行走過程

2.2 地標的選取

目標空間的區域劃分完后，進行地標的提取，對局部空間中的點云數據進行特征提取與分割。本文中采用基于LCCP（局部凸連接聚類）的方法對局部空間中的典型物體進行提取。該算法分為兩大部分，分別是基于超體聚類的過分割與基于超體聚類的再聚類。LCCP依賴于點云數據的空間形狀信息和法線方向信息，用這些信息完成超體類聚過程。在完成超體類聚后，對過分割的點云計算不同塊之間的凹凸關系，其凹凸關系是通過CC（Extended Convexity）和SC（Sanity Criterion）判據來判斷的。判據方法如圖2所示。

圖2 凹凸關系判斷圖

以相鄰兩片法向量與中心線向量的夾角來判斷凹凸性，如圖2所示，當1＞2時，判斷為凹；當1＜2時，判斷為凸。因為所處理的數據會存在噪聲問題，所以在判斷時加入閾值，當1與2差值的絕對值大于時，為了避免誤判，采用下列公式進行判斷：

將每個塊都做完凹凸關系判斷之后，采用區域增長算法將塊的小區域進行聚類形成較大的物體，然后對此提取的物體進行去噪，最后提取結果如圖3所示。

圖3 物體提取結果

最后，對每個區域都進行物體提取，將提取出的物體作為地標進行拓撲地圖的構建，每個提取出的物體的質心坐標為地標的坐標，質心到物體最遠點的距離作為地標的大小。

3 基于地標的拓撲地圖構建

實驗所用電腦配置Win10系統，4 G內存，3.3 GHz的臺式電腦，所用軟件為Matlab2017a，所用的實驗數據為實驗室的整體空間。實驗時，使機器人在房間中漫游行走采集數據，按照1 m的步長劃分區域，采集完信息后對其進行特征提取，然后進行拓撲地圖的構建。

拓撲地圖是用一張圖來表示環境的暢通性。地圖由兩個基本要素節點和邊組成，其頂點用來表示環境中的某些物體或者區域，在本文中使用提取的地標作為結點進行構建。邊用來表示每個節點的連通情況，用機器人行走時所獲取的點云信息中的墻壁表示。在本文中，對簡單的房間進行了實驗，選取其中的桌子作為地標，墻壁作為路徑連通，實驗結果如圖4所示，為拓撲地圖的構建結果，其中包含6個頂點和6條路徑，頂點分別為v1、v2、v3、v4、v5、v6，邊為e1、e2、e3、e4、e5、e6。

每個頂點的坐標值已知，路徑長度已知，并且在導航時對機器人提供了專門針對環境的簡潔說明，則其可以作為導航地圖使用。在匹配拓撲地圖的節點時，使用坐標變換公式將局部作為轉換為全局坐標。導航時，只需輸入要到達的目標地點，機器人則自動沿路徑行走到達目標位置。

圖4 拓撲地圖

4 結論

本文提出了一種基于地標識別的拓撲地圖構建方法，實驗結果表明，該方法可以提高對復雜空間的點云拓撲地圖在構建時的效率與準確性，解決了拓撲地圖構建中的節點選擇問題，為機器人的高效導航奠定了基礎。

［1］王璐.未知環境中移動機器人視覺環境建模與定位研究［D］.湖南：中南大學，2007.

［2］王衛華，陳衛東，席裕庚.基于不確定信息的移動機器人地圖創建研究進展［J］.機器人，2001，23（6）：563-568.

［3］Ghia U，Ghia K N，Shin C T.High-Re solutions for incompressible flow using the Navier-Stokes equations and a multigrid method［J］.Journal of Computational Physics，1985，48（3）：387-411.

［4］羅榮華，洪炳镕.基于信息融合的同時定位與地圖創建研究［J］.哈爾濱工業大學學報，2004，36（5）：566-569.

［5］趙翊捷，陳衛東.基于地圖的移動機器人定位技術新進展［J］.上海交通大學學報，2002，36（10）：1435-1438.

［6］樊征，曹其新，楊揚，等.面向移動機器人的拓撲地圖自動生成［J］.華中科技大學學報（自然科學版）， 2008（Suppl 1）：172-175.

2095－6835（2019）03－0086－02

TP391.4

A

10.15913/j.cnki.kjycx.2019.03.086

申紫銘（1994—），男，河北廊坊人，碩士研究生，研究方向為特種機器人。

〔編輯：王霞〕