申紫銘，郭鵬，李敏

?

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

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

1 引言

目前，環(huán)境的空間表示方法主要分為兩大類，分別是幾何地圖和拓?fù)涞貓D。對(duì)復(fù)雜空間進(jìn)行緊湊的表達(dá)時(shí)常通過拓?fù)涞貓D的表達(dá)方法來完成[1]。拓?fù)涞貓D是由Kuipers在1978年首先提出的，以點(diǎn)線面的結(jié)構(gòu)組合形式來表現(xiàn)一個(gè)具有連通性的環(huán)境空間[2]，屬于簡(jiǎn)潔、直觀的環(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ī)器人提供簡(jiǎn)潔、高效的規(guī)劃策略[4]，而且對(duì)存儲(chǔ)空間大小與計(jì)算速度并無特別要求，所以在相同條件下拓?fù)涞貓D的效率較高[5]。

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

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

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

對(duì)目標(biāo)空間進(jìn)行區(qū)域劃分時(shí)需要機(jī)器人在空間中不斷行走，設(shè)置其行走步長，當(dāng)走到步長值時(shí)，將經(jīng)過的區(qū)域設(shè)為局部空間1，然后重復(fù)對(duì)局部空間1進(jìn)行點(diǎn)云離散化處理，分析環(huán)境的結(jié)構(gòu)特點(diǎn)，實(shí)現(xiàn)點(diǎn)云的權(quán)重信息精簡(jiǎn)，以滿足實(shí)時(shí)性的要求，并對(duì)其輪廓進(jìn)行分析提取特征，利用不變矩原理計(jì)算質(zhì)心位置獲得其局部質(zhì)心坐標(biāo)1，直到劃分完整個(gè)目標(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)的提取，對(duì)局部空間中的點(diǎn)云數(shù)據(jù)進(jìn)行特征提取與分割。本文中采用基于LCCP（局部凸連接聚類）的方法對(duì)局部空間中的典型物體進(jìn)行提取。該算法分為兩大部分，分別是基于超體聚類的過分割與基于超體聚類的再聚類。LCCP依賴于點(diǎn)云數(shù)據(jù)的空間形狀信息和法線方向信息，用這些信息完成超體類聚過程。在完成超體類聚后，對(duì)過分割的點(diǎn)云計(jì)算不同塊之間的凹凸關(guān)系，其凹凸關(guān)系是通過CC（Extended Convexity）和SC（Sanity Criterion）判據(jù)來判斷的。判據(jù)方法如圖2所示。

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

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

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

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

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

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

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

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

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

圖4 拓?fù)涞貓D

4 結(jié)論

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

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

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

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

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

2095－6835（2019）03－0086－02

TP391.4

A

10.15913/j.cnki.kjycx.2019.03.086

申紫銘（1994—），男，河北廊坊人，碩士研究生，研究方向?yàn)樘胤N機(jī)器人。

〔編輯：王霞〕