S觟ren Schwertfeger，于天彥

（1.中國(guó)科學(xué)院 上海微系統(tǒng)與信息技術(shù)研究所，上海200050；2.上?？萍即髮W(xué) 上海200031）

拓?fù)涞貓D中的房間檢測(cè)

（1.中國(guó)科學(xué)院 上海微系統(tǒng)與信息技術(shù)研究所，上海200050；2.上?？萍即髮W(xué) 上海200031）

測(cè)繪是許多機(jī)器人應(yīng)用的一個(gè)重要組成部分。為了評(píng)估測(cè)繪步驟的表現(xiàn)，需要對(duì)其得出的地圖的質(zhì)量進(jìn)行衡量。地圖對(duì)定位與路徑規(guī)劃而言都至關(guān)重要。本文以先前比較機(jī)器人所生成地圖與基準(zhǔn)地圖的拓?fù)浣Y(jié)構(gòu)的嘗試中已經(jīng)使用的拓?fù)鋱D匹配法為基礎(chǔ)，采用Alpha Shape法對(duì)房間等地圖開(kāi)放區(qū)域的檢測(cè)進(jìn)行了擴(kuò)展，通過(guò)在450幅由不同原始地圖添加噪聲后形成的地圖上進(jìn)行的充分測(cè)試，顯示房間檢測(cè)為匹配算法的穩(wěn)定性與魯棒性帶來(lái)提升。

機(jī)器人學(xué)；拓?fù)涞貓D；房間檢測(cè)；Alpha Shape

在機(jī)器人領(lǐng)域，環(huán)境地圖是其所在環(huán)境的模型，該地圖通常用二維網(wǎng)格地圖的形式表達(dá)。而拓?fù)鋱D則是僅包含地點(diǎn)及其連接的更抽象表達(dá)。拓?fù)涞貓D已在許多方面得到應(yīng)用，如地圖融合[1]、地點(diǎn)檢測(cè)[2，3]或規(guī)劃[4]。同時(shí)也有不同的二維網(wǎng)格地圖生成方法，如基于細(xì)化[5]或 Voronoi圖[6-7]。

所有的地圖都會(huì)帶有一定程度的由定位錯(cuò)誤所帶來(lái)的誤差[8]。之前的拓?fù)涞貓D質(zhì)量評(píng)估算法通過(guò)對(duì)拓?fù)涞貓D進(jìn)行匹配，并測(cè)量其匹配誤差，從而決定地圖的質(zhì)量[9，10]。在密閉空間和走廊上，算法的結(jié)果良好，但在開(kāi)放區(qū)域內(nèi)，由于Voronoi圖對(duì)于墻壁上的噪音極其敏感，導(dǎo)致在同一測(cè)試環(huán)境的開(kāi)放區(qū)域內(nèi)不同地圖對(duì)應(yīng)的拓?fù)鋱D無(wú)法與基準(zhǔn)地圖相匹配。

文中通過(guò)將房間視為拓?fù)鋱D中的一個(gè)節(jié)點(diǎn)，并使此節(jié)點(diǎn)與相鄰走廊相連。對(duì)拓?fù)鋱D進(jìn)行了簡(jiǎn)化，并提升了匹配準(zhǔn)確度。

1 定 義

圖由一個(gè)節(jié)點(diǎn)集合V、一個(gè)邊集合E所組成的有序?qū)=（V，E）定義。拓?fù)鋱D為包含節(jié)點(diǎn)及節(jié)點(diǎn)間可作為行駛路線的邊的圖。節(jié)點(diǎn)是圖中邊的起始或終止位置。邊則用于表示圖中節(jié)點(diǎn)間的連接關(guān)系，而路徑由首尾相連且不含其內(nèi)部連接節(jié)點(diǎn)的邊構(gòu)成。其始節(jié)點(diǎn)為第一條邊的始節(jié)點(diǎn)。其終節(jié)點(diǎn)是最后一條邊的終節(jié)點(diǎn)。一條邊只可能屬于一條路徑。單向路徑（邊）是兩個(gè)節(jié)點(diǎn)間的一條有向路徑（邊），其對(duì)偶路徑（邊）的始節(jié)點(diǎn)是其終節(jié)點(diǎn)，其對(duì)偶路徑（邊）的終節(jié)點(diǎn)則是其始節(jié)點(diǎn)。始節(jié)點(diǎn)或終結(jié)點(diǎn)僅與路徑自身及其對(duì)偶路徑相連的路徑為死路徑。

房間定義為邊緣上的任意兩個(gè)障礙物間距離大于某固定閾值的區(qū)域。本文中，房間為Alpha Shape算法生成的多邊形。邊界節(jié)點(diǎn)是位于某一路徑與某一房間交叉處的節(jié)點(diǎn)。房間ID為房間的標(biāo)識(shí)，其默認(rèn)值為-1。房間中心節(jié)點(diǎn)是房間檢測(cè)完成后，在房間中心位置新生成的節(jié)點(diǎn)。

2 拓?fù)鋱D中的房間檢測(cè)

房間內(nèi)部有很少或無(wú)障礙物，其內(nèi)部生成的拓?fù)鋱D的邊與路徑對(duì)墻壁附近的噪點(diǎn)較敏感。本文中，由Alpha Shape法獲取的內(nèi)部多邊形將被視為不同的房間。隨后，建立每個(gè)房間多邊形的中心節(jié)點(diǎn)，并在路徑與多邊形的交點(diǎn)處建立新節(jié)點(diǎn)，除邊界節(jié)點(diǎn)之外的所有房間內(nèi)部節(jié)點(diǎn)及內(nèi)部邊被刪除后，需將邊界節(jié)點(diǎn)與房間中心節(jié)點(diǎn)用邊相連。

2.1 拓?fù)鋱D的生成

在此對(duì)拓?fù)鋱D的生成過(guò)程進(jìn)行簡(jiǎn)要說(shuō)明，更詳細(xì)的說(shuō)明參見(jiàn)文獻(xiàn)[9-10]。本文借助Voronoi圖由二維網(wǎng)格地圖生成拓?fù)鋱D。Voronoi圖是對(duì)空間的一種小區(qū)域分割方法[11]。在刪除死路徑，合并相近的節(jié)點(diǎn)后，最終得到一個(gè)具有節(jié)點(diǎn)、邊和路徑的拓?fù)涞貓D。

2.2 尋找房間

此處使用Alpha Shape算法來(lái)檢測(cè)房間多邊形。Alpha Shape是最初由 Edelsbrunner、Kirkpatrick 與Seidel所定義[12]的歐幾里德平面中與一個(gè)有限點(diǎn)集的形狀相關(guān)的一系列線段所構(gòu)成的簡(jiǎn)單曲線。其使用的Alpha值可對(duì)其內(nèi)部障礙物之間的最小距離加以限制。

2.3 邊界節(jié)點(diǎn)的生成

擁有各房間所對(duì)應(yīng)的多邊形后，還要在路徑與各房間的交點(diǎn)處添加新的“邊界節(jié)點(diǎn)”。此處通過(guò)對(duì)路徑進(jìn)行逐一檢查，以尋找該路徑是否與房間有交點(diǎn)，若有，需確定交點(diǎn)的具體位置，并返回一個(gè)存有交點(diǎn)位置與其所在路徑始節(jié)點(diǎn)間路徑長(zhǎng)度的列表，列表中的長(zhǎng)度將用于隨后的路徑切割。

2.4 在邊界節(jié)點(diǎn)處切割路徑

對(duì)于所有生成的邊界節(jié)點(diǎn)，切割長(zhǎng)度lvoric是其所在路徑始節(jié)點(diǎn)與該節(jié)點(diǎn)間的路徑長(zhǎng)度，該長(zhǎng)度介于0和路徑全長(zhǎng)之間。當(dāng)切割長(zhǎng)度接近0或接近路徑全長(zhǎng)lvori時(shí)，由于浮點(diǎn)數(shù)表達(dá)不精確，需使用閾值ε確定接近程度（ε設(shè)為0.000 000 01）。在始節(jié)點(diǎn)或終節(jié)點(diǎn)切割時(shí)只返回含有Evori的列表，否則返回含有切割后的兩條新路徑的列表。

在對(duì)某單向路徑Evorik（1≤k≤M）進(jìn)行切割時(shí)，通過(guò)對(duì)其中首尾相連的單向邊 （Etopo1、Etopo2、...、EtopoN）長(zhǎng)度（ltopo1、ltopo2、...、ltopoN）進(jìn)行累加，并與 lvoric 進(jìn)行比較，以確定切割位置。若切割后返回的單向路徑列表的大小為1時(shí)，只需將其切割位置的始節(jié)點(diǎn)或終節(jié)點(diǎn)標(biāo)記為邊界節(jié)點(diǎn)，否則需采用相同參數(shù)切割其對(duì)偶路徑，添加新的邊界節(jié)點(diǎn)，并在其邊連接列表中加入新建立的邊及其對(duì)偶邊。該邊界節(jié)點(diǎn)的房間ID與該位置與此路徑相交的多邊形的房間ID相同。

2.5 設(shè)置房間ID

邊界節(jié)點(diǎn)的房間ID已在切割時(shí)設(shè)置，而其他節(jié)點(diǎn)的房間ID為默認(rèn)值-1。這些節(jié)點(diǎn)中，有的在房間多邊形內(nèi)，有的不在任何房間多邊形內(nèi)。多邊形內(nèi)節(jié)點(diǎn)的房間ID被設(shè)為Alpha Shape所生成的多邊形列表中該多邊形所對(duì)應(yīng)的ID，而其他節(jié)點(diǎn)的房間ID則保持不變。全部節(jié)點(diǎn)設(shè)置完成后，房間ID為默認(rèn)值-1的節(jié)點(diǎn)將可被視為不在任何房間多邊形內(nèi)。

其后，比較每條路徑的始節(jié)點(diǎn)和終節(jié)點(diǎn)的房間ID相等與否，若兩者相同，則判斷該值是否為默認(rèn)值，若為默認(rèn)值則忽略，否則將該路徑及其對(duì)偶路徑的房間ID設(shè)為該值。若兩者不同，當(dāng)該路徑為死路徑且長(zhǎng)度不大于閾值minLenThreshold（設(shè)為20個(gè)像素）時(shí)，將其末節(jié)點(diǎn)（只有兩條路徑相連的始節(jié)點(diǎn)或終節(jié)點(diǎn)）房間ID設(shè)為兩者中的非默認(rèn)值，這會(huì)為之后移除短死路徑帶來(lái)便利。

2.6 移除短死路徑

僅與兩條互為對(duì)偶的路徑相連的節(jié)點(diǎn)被稱為死節(jié)點(diǎn)，這兩條路徑則為死路徑。若一個(gè)邊界節(jié)點(diǎn)與一條長(zhǎng)度小于minLenThreshold的死路徑相連，則需將死路徑及其對(duì)應(yīng)的死節(jié)點(diǎn)、邊界節(jié)點(diǎn)及與之相連的房間內(nèi)路徑從拓?fù)鋱D中刪除。

因?yàn)锳lpha Shape無(wú)法伸入房間角落部位，故時(shí)常會(huì)有雖然不在房間多邊形內(nèi)，但實(shí)際上在房間內(nèi)的節(jié)點(diǎn)（如圖2中節(jié)點(diǎn)10）。由于之后需要由單一節(jié)點(diǎn)表達(dá)房間，故需將這些節(jié)點(diǎn)刪除。

2.7 建立包含房間的拓?fù)鋱D

將所有房間內(nèi)路徑和除邊界節(jié)點(diǎn)之外的房間內(nèi)節(jié)點(diǎn)移除后，還需逐一建立代表房間的新節(jié)點(diǎn)。這些節(jié)點(diǎn)位于多邊形中心位置，并與所有該房間的邊界節(jié)點(diǎn)相連，同時(shí)擁有該多邊形（圖中的有色區(qū)域）的相關(guān)信息。

一個(gè)非自交叉的封閉多邊形的中心可由其邊界上的N個(gè)點(diǎn)計(jì)算得到。設(shè)這些點(diǎn)為：

則多邊形的中心為（Cx，Cy），其中

上述公式[13]中，邊界上的點(diǎn)沿多邊形的邊界依次出現(xiàn)，且被逐一按其出現(xiàn)順序編號(hào)。其中，點(diǎn)（xN，yN）與（x0，y0）相同。

圖1 含Voronoi圖和Alpha Shape的地圖

圖2 采用房間檢測(cè)由圖1生成的拓?fù)鋱D

圖3 不采用房間檢測(cè)由圖1生成的拓?fù)鋱D

3 實(shí) 驗(yàn)

本章將展示算法的有效性，并通過(guò)廣泛的實(shí)驗(yàn)證明房間檢測(cè)為拓?fù)鋱D匹配所帶來(lái)的提升。

圖4 含Voronoi圖和Alpha Shape的地圖

圖5 采用房間檢測(cè)由圖4生成的拓?fù)鋱D

圖6 不采用房間檢測(cè)由圖4生成的拓?fù)鋱D

3.1 機(jī)器人世界杯救援比賽地圖

測(cè)試中使用的拓?fù)涞貓D由2010新加坡救援機(jī)器人世界杯的原始地圖[14，15]生成。這些地圖已被用于一些基于拓?fù)涞貓D的測(cè)試中，其對(duì)應(yīng)的三維地圖也被用于三維地圖評(píng)估測(cè)試[16]。

圖1、4展示了地圖及其生成的復(fù)雜的Voronoi圖和Alpha Shape，圖2、5則展示了修剪后的拓?fù)鋱D及檢測(cè)出的房間，與不采用房間檢測(cè)直接生成的拓?fù)鋱D（圖3、6）相比，可見(jiàn)拓?fù)鋱D復(fù)雜度有了明顯降低。

3.2 對(duì)匹配的影響

測(cè)試過(guò)程選用了5幅地圖，一幅來(lái)自文獻(xiàn)[3]（命名為“Beeson”），一幅來(lái)自數(shù)據(jù)庫(kù)[17]（命名為“Belgioioso”），其它三幅（“EdmontonConvention Center”、“Longwood”、“SDR Site B”）則來(lái)自另一數(shù)據(jù)庫(kù)[18]。為了保證一致的測(cè)試條件，首先對(duì)參與測(cè)試的地圖進(jìn)行了灰度化和細(xì)化，隨后，從原地圖中刪除一定比例的黑色像素點(diǎn)（設(shè)為白色），再以隨機(jī)方式選擇同樣數(shù)量的黑色像素點(diǎn)，并將距離每個(gè)選中的黑色像素點(diǎn)一個(gè)固定距離內(nèi)的某個(gè)像素點(diǎn)（具體距離與位置隨機(jī)確定）設(shè)為黑色，由此為地圖添加隨機(jī)噪點(diǎn)。

圖7 Belgioioso地圖

圖8 Edmonton Convention Center

圖9 Longwood地圖

圖10 SDR Site B

測(cè)試中，比例（p）為{2%，8%，14%}，距離 dr為{1，2，3}。 圖 11 中展示了當(dāng) dr為 1，p=2 時(shí)，對(duì) Beeson地圖使用房間檢測(cè)算法的結(jié)果。為使結(jié)果更明顯，房間區(qū)域用不同深度的顏色表示。

圖11 Beeson地圖

對(duì)于每個(gè)不同的{dr，p}值對(duì)，需由每個(gè)原始地圖生成10個(gè)隨機(jī)化后的地圖用于測(cè)試，其中第一個(gè)地圖為基準(zhǔn)地圖，用于與其它地圖進(jìn)行匹配。匹配過(guò)程中，對(duì)每個(gè)由隨機(jī)化地圖所生成的拓?fù)鋱D中的每個(gè)節(jié)點(diǎn)進(jìn)行遍歷，同時(shí)在由基準(zhǔn)地圖生成的拓?fù)鋱D中找到與之距離最近的節(jié)點(diǎn)（視為匹配），并累計(jì)該距離。遍歷后累計(jì)值（視為匹配誤差和）的均值可作為房間檢測(cè)算法穩(wěn)定度的度量。在由同一地圖以不同隨機(jī)化程度生成的地圖上，該值見(jiàn)表1～5。

表1 Beeson地圖距離比較（alpha值：200）

表2 Belgioioso地圖距離比較（alpha值：250）

表3 Edmonton地圖距離比較（alpha值：500）

表4 Longwood地圖距離比較（alpha值：250）

從結(jié)果中可見(jiàn)，使用房間檢測(cè)后的拓?fù)鋱D有明顯的優(yōu)勢(shì)。這一結(jié)果當(dāng)然也與具體地圖有關(guān)，若其中障礙物間距與Alpha Shape算法的Alpha值接近，則房間自身很容易受噪點(diǎn)影響（如圖9的Longwood地圖，表4）。這時(shí)，房間檢測(cè)所帶來(lái)的優(yōu)勢(shì)就變得很有限。而其他包含大房間的地圖則從房間檢測(cè)中獲益良多。這在圖 11（Beeson地圖，表 1）與圖 7（Belgioioso地圖，表2）中都有一定體現(xiàn)。

總的來(lái)說(shuō)，噪點(diǎn)與墻壁間距離越遠(yuǎn)，房間檢測(cè)所帶來(lái)的正面效應(yīng)就越少，因?yàn)樗鼈儠?huì)越來(lái)越多地影響房間的整體拓?fù)浣Y(jié)構(gòu)，但p值對(duì)比率的整體影響較小。效率方面，用于比較的兩幅地圖的拓?fù)鋱D生成過(guò)程（含房間檢測(cè)與匹配）的速度很快，單地圖耗時(shí)還不到一秒。

表5 SDR地圖距離比較（alpha值：422）

4 結(jié) 論

文中展示了基于Alpha Shape算法，對(duì)二維網(wǎng)格地圖的房間檢測(cè)過(guò)程，并使用提取出的房間多邊形對(duì)拓?fù)鋱D進(jìn)行修改。由此產(chǎn)生的拓?fù)鋱D僅使用單一節(jié)點(diǎn)表示一個(gè)房間，通過(guò)在通向房間的邊與房間的交點(diǎn)處增加新節(jié)點(diǎn)的方式，很好地保持了原拓?fù)鋱D中房間與其周?chē)?jié)點(diǎn)間的連接關(guān)系。算法在機(jī)器人世界杯救援比賽地圖上表現(xiàn)良好。測(cè)試中，基于上述方法生成的450幅隨機(jī)化地圖，對(duì)算法穩(wěn)定度和可重復(fù)性進(jìn)行了客觀評(píng)估。

由于算法生成的地圖具有一定的穩(wěn)定性，可將本文中算法與文獻(xiàn)[7]中的拓?fù)鋱D匹配相結(jié)合。今后，還可將其與另一文獻(xiàn)[19]中的路徑匹配相整合。未來(lái)，這一算法將有助于生成適用于多樣化應(yīng)用場(chǎng)景的極為魯棒的地圖。

[1]Saeedi S， Paull L， Trentini M， et al.Group mapping:A topological approach to map merging for multiple robots[J].Robotics&Automation Magazine，IEEE，2014，21（2）:60-72.

[2]KaraoguzH，BozmaH I.Reliabletopological place detection in bubble space[C]//Robotics andAutomation (ICRA),2014 IEEE International Conference on,2014:697-702.

[3]Beeson P， Jong N K， KuipersB.Towards autonomous topological place detection using the extended voronoi graph [C]//Robotics and Automation,2005.ICRA 2005.Proceedings of the 2005 IEEE International Conference on,2005:4373-4379.

[4]Konolige K， Marder-eppstein E， Marthi B.Navigation in hybrid metric-topological maps[C]//Robotics and Automation （ICRA），2011 IEEE International Conference on,2011:3041-3047.

[5]Portugal D，Rocha R P.Extracting topological information from grid MAPS for robot navigation[C]//ICAART （1）， 2012:137-143.

[6]Gadre A S， Du S，Stilwell D J.A topological map based approach to long range operation of an unmanned surface vehicle[C]//ACC，2012:5401-5407.

[7]Lau B，Sprunk C，Burgard W.Improved updating of Euclidean distance maps and Voronoi diagrams[C]//Intelligent Robots and Systems （IROS）,2010 IEEE/RSJ International Conference on,2010:281-286.

[8]Schwertfeger S， Jacoff A， Pellenz J，et al.Using a fiducial map metric for assessing map quality in the context of robocup rescue[C]//Safety,Security,and Rescue Robotics (SSRR),2011 IEEE International Symposium on,2011:208-214.

[9]Schwertfeger S，Birk A.Evaluation of map quality by matching and scoring high-level,topological map structures [C]//Robotics and Automation（ICRA）,2013 IEEE International Conference on,2013:2221-2226.

[10]Schwertfeger S，Birk A.Map evaluation using matched topology graphs[J].Autonomous Robots,2016，40（5）:761-787.

[11]Klein R.Abstract voronoi diagrams and their applications[G].Computational Geometry and its Applications.Würzburg,FRG:Springer,1988:148-157.

[12]Edelsbrunner H，Kirkpatrick D G，Raimund S.On the shape of a set of points in the plane[J].Information Theory， IEEE Transactions on，1983，29（4）:551-559.

[13]Bourke P.Calculating the area and centroid of a polygon[Z]，1988.

[14]Sheh R，Kimura T，Ehsan M，et al.The robo cup rescue robot league:guiding robots towards fieldable capabilities[C]//Advanced Robotics and its Social Impacts （ARSO）,2011 IEEE Workshop on,2011:31-34.

[15]Sheh R，Jacoff A，Ann-Marie V，et al.Advancing the state of urban search and rescue robotics through the robocuprescue robot league competition[C]//Field and service robotics,2014:127-142.

[16]Birk A， Others.Using fiducialsin 3D map evaluation[C]//2015 IEEE International Symposium on Safety,Security,and Rescue Robotics（SSRR），2015:1-7.

[17]University of Freiburg. Robotics datasets:Belgioioso castle[Z].2002.

[18]HOWARD A,ROY N.The robotics data set repository(radish)[Z].2003.

[19]Schwertfeger S，YU Tian-yan.Matching paths in topological maps[C]//會(huì)議/論文集缺失，2016.

Room detection for topological maps

Mapping is an important part of many robotic applications.In order to measure the performance of the mappingprocess we have to measure the quality of its result:the map.The map is essential for robotic algorithms like localizationand path planning.In this paper，based on the Topology Graph matching method which has been used in comparingthe topology of the robot generated map to the topology of a ground truth map，a novel algorithm with Alpha Shapeis applied to open areas'detection as an extension of the previous approach.On 450 maps which are generated by adding noise to different original maps，the experiments show the algorithm makes the matching method more stable and robust.

Robotics； topological map； room detection； alpha shape

TP242

A

1674－6236（2017）12-0027-06

2016-06-01稿件編號(hào)：201606004

S觟ren Schwertfeger（1979—），男，德國(guó)人，博士，博士后研究員，助理教授。研究方向：搜救機(jī)器人的智能化功能及其性能評(píng)估。