基于地標(biāo)的點(diǎn)云拓?fù)涞貓D構(gòu)建方法研究

申紫銘，郭鵬，李敏

?

基于地標(biāo)的點(diǎn)云拓?fù)涞貓D構(gòu)建方法研究

申紫銘，郭鵬，李敏

（河北工業(yè)大學(xué)機(jī)械工程學(xué)院，天津 300130）

為了提高構(gòu)建復(fù)雜空間點(diǎn)云拓?fù)涞貓D的效率與準(zhǔn)確性，提出了一種基于地標(biāo)的拓?fù)涞貓D構(gòu)建方法。對目標(biāo)空間進(jìn)行點(diǎn)云數(shù)據(jù)采集，對采集的點(diǎn)云根據(jù)位置信息進(jìn)行區(qū)域劃分，并對每個劃分好的區(qū)域進(jìn)行點(diǎn)云特征提取，將提取的特征作為地標(biāo)信息。對每個地標(biāo)做拓?fù)涮幚?，?gòu)建出拓?fù)涞貓D。實(shí)驗表明，該方法可以有效地構(gòu)建出點(diǎn)云拓?fù)涞貓D，為機(jī)器人的高效導(dǎo)航奠定基礎(chǔ)。

地標(biāo)；拓?fù)涞貓D；特征提??；云數(shù)據(jù)

1 引言

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

但拓?fù)涞貓D的劣勢在于其重在描述目標(biāo)空間的拓?fù)浣Y(jié)構(gòu)，而對目標(biāo)空間無精確的位置關(guān)系要求，在節(jié)點(diǎn)的定義與選擇方面也存在著難點(diǎn)，容易出現(xiàn)因環(huán)境的相似性造成的節(jié)點(diǎn)混淆等問題[6]。針對以上問題，本文提出了一種基于地標(biāo)的拓?fù)涞貓D構(gòu)建方法：對目標(biāo)空間進(jìn)行點(diǎn)云數(shù)據(jù)采集，對采集的點(diǎn)云根據(jù)其位置信息進(jìn)行區(qū)域劃分，對每個劃分好的區(qū)域進(jìn)行點(diǎn)云特征提取，將提取的特征作為地標(biāo)信息，對每個地標(biāo)做拓?fù)涮幚?，?gòu)建出拓?fù)涞貓D。

2 目標(biāo)空間的區(qū)域劃分與地標(biāo)選取

2.1 目標(biāo)空間的區(qū)域劃分

對目標(biāo)空間進(jìn)行區(qū)域劃分時需要機(jī)器人在空間中不斷行走，設(shè)置其行走步長，當(dāng)走到步長值時，將經(jīng)過的區(qū)域設(shè)為局部空間1，然后重復(fù)對局部空間1進(jìn)行點(diǎn)云離散化處理，分析環(huán)境的結(jié)構(gòu)特點(diǎn)，實(shí)現(xiàn)點(diǎn)云的權(quán)重信息精簡，以滿足實(shí)時性的要求，并對其輪廓進(jìn)行分析提取特征，利用不變矩原理計算質(zhì)心位置獲得其局部質(zhì)心坐標(biāo)1，直到劃分完整個目標(biāo)空間，獲得局部空間n與局部質(zhì)心坐標(biāo)n.最終形成局部空間{1，2，…，n}及其局部質(zhì)心坐標(biāo){1，2，…，n}。機(jī)器人的行走過程如圖1所示。

圖1 機(jī)器人的行走過程

2.2 地標(biāo)的選取

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

圖2 凹凸關(guān)系判斷圖

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

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

圖3 物體提取結(jié)果

最后，對每個區(qū)域都進(jìn)行物體提取，將提取出的物體作為地標(biāo)進(jìn)行拓?fù)涞貓D的構(gòu)建，每個提取出的物體的質(zhì)心坐標(biāo)為地標(biāo)的坐標(biāo)，質(zhì)心到物體最遠(yuǎn)點(diǎn)的距離作為地標(biāo)的大小。

3 基于地標(biāo)的拓?fù)涞貓D構(gòu)建

實(shí)驗所用電腦配置Win10系統(tǒng)，4 G內(nèi)存，3.3 GHz的臺式電腦，所用軟件為Matlab2017a，所用的實(shí)驗數(shù)據(jù)為實(shí)驗室的整體空間。實(shí)驗時，使機(jī)器人在房間中漫游行走采集數(shù)據(jù)，按照1 m的步長劃分區(qū)域，采集完信息后對其進(jìn)行特征提取，然后進(jìn)行拓?fù)涞貓D的構(gòu)建。

拓?fù)涞貓D是用一張圖來表示環(huán)境的暢通性。地圖由兩個基本要素節(jié)點(diǎn)和邊組成，其頂點(diǎn)用來表示環(huán)境中的某些物體或者區(qū)域，在本文中使用提取的地標(biāo)作為結(jié)點(diǎn)進(jìn)行構(gòu)建。邊用來表示每個節(jié)點(diǎn)的連通情況，用機(jī)器人行走時所獲取的點(diǎn)云信息中的墻壁表示。在本文中，對簡單的房間進(jìn)行了實(shí)驗，選取其中的桌子作為地標(biāo)，墻壁作為路徑連通，實(shí)驗結(jié)果如圖4所示，為拓?fù)涞貓D的構(gòu)建結(jié)果，其中包含6個頂點(diǎn)和6條路徑，頂點(diǎn)分別為v1、v2、v3、v4、v5、v6，邊為e1、e2、e3、e4、e5、e6。

每個頂點(diǎn)的坐標(biāo)值已知，路徑長度已知，并且在導(dǎo)航時對機(jī)器人提供了專門針對環(huán)境的簡潔說明，則其可以作為導(dǎo)航地圖使用。在匹配拓?fù)涞貓D的節(jié)點(diǎn)時，使用坐標(biāo)變換公式將局部作為轉(zhuǎn)換為全局坐標(biāo)。導(dǎo)航時，只需輸入要到達(dá)的目標(biāo)地點(diǎn)，機(jī)器人則自動沿路徑行走到達(dá)目標(biāo)位置。

圖4 拓?fù)涞貓D

4 結(jié)論

本文提出了一種基于地標(biāo)識別的拓?fù)涞貓D構(gòu)建方法，實(shí)驗結(jié)果表明，該方法可以提高對復(fù)雜空間的點(diǎn)云拓?fù)涞貓D在構(gòu)建時的效率與準(zhǔn)確性，解決了拓?fù)涞貓D構(gòu)建中的節(jié)點(diǎn)選擇問題，為機(jī)器人的高效導(dǎo)航奠定了基礎(chǔ)。

［1］王璐.未知環(huán)境中移動機(jī)器人視覺環(huán)境建模與定位研究［D］.湖南：中南大學(xué)，2007.

［2］王衛(wèi)華，陳衛(wèi)東，席裕庚.基于不確定信息的移動機(jī)器人地圖創(chuàng)建研究進(jìn)展［J］.機(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］羅榮華，洪炳镕.基于信息融合的同時定位與地圖創(chuàng)建研究［J］.哈爾濱工業(yè)大學(xué)學(xué)報，2004，36（5）：566-569.

［5］趙翊捷，陳衛(wèi)東.基于地圖的移動機(jī)器人定位技術(shù)新進(jìn)展［J］.上海交通大學(xué)學(xué)報，2002，36（10）：1435-1438.

［6］樊征，曹其新，楊揚(yáng)，等.面向移動機(jī)器人的拓?fù)涞貓D自動生成［J］.華中科技大學(xué)學(xué)報（自然科學(xué)版）， 2008（Suppl 1）：172-175.

2095－6835（2019）03－0086－02

TP391.4

A

10.15913/j.cnki.kjycx.2019.03.086

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

〔編輯：王霞〕