拓撲地圖中的房間檢測

S觟ren Schwertfeger，于天彥

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

拓撲地圖中的房間檢測

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

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

機器人學；拓撲地圖；房間檢測；Alpha Shape

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

所有的地圖都會帶有一定程度的由定位錯誤所帶來的誤差[8]。之前的拓撲地圖質量評估算法通過對拓撲地圖進行匹配，并測量其匹配誤差，從而決定地圖的質量[9，10]。在密閉空間和走廊上，算法的結果良好，但在開放區(qū)域內，由于Voronoi圖對于墻壁上的噪音極其敏感，導致在同一測試環(huán)境的開放區(qū)域內不同地圖對應的拓撲圖無法與基準地圖相匹配。

文中通過將房間視為拓撲圖中的一個節(jié)點，并使此節(jié)點與相鄰走廊相連。對拓撲圖進行了簡化，并提升了匹配準確度。

1 定 義

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

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

2 拓撲圖中的房間檢測

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

2.1 拓撲圖的生成

在此對拓撲圖的生成過程進行簡要說明，更詳細的說明參見文獻[9-10]。本文借助Voronoi圖由二維網(wǎng)格地圖生成拓撲圖。Voronoi圖是對空間的一種小區(qū)域分割方法[11]。在刪除死路徑，合并相近的節(jié)點后，最終得到一個具有節(jié)點、邊和路徑的拓撲地圖。

2.2 尋找房間

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

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

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

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

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

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

2.5 設置房間ID

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

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

2.6 移除短死路徑

僅與兩條互為對偶的路徑相連的節(jié)點被稱為死節(jié)點，這兩條路徑則為死路徑。若一個邊界節(jié)點與一條長度小于minLenThreshold的死路徑相連，則需將死路徑及其對應的死節(jié)點、邊界節(jié)點及與之相連的房間內路徑從拓撲圖中刪除。

因為Alpha Shape無法伸入房間角落部位，故時常會有雖然不在房間多邊形內，但實際上在房間內的節(jié)點（如圖2中節(jié)點10）。由于之后需要由單一節(jié)點表達房間，故需將這些節(jié)點刪除。

2.7 建立包含房間的拓撲圖

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

一個非自交叉的封閉多邊形的中心可由其邊界上的N個點計算得到。設這些點為：

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

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

圖1 含Voronoi圖和Alpha Shape的地圖

圖2 采用房間檢測由圖1生成的拓撲圖

圖3 不采用房間檢測由圖1生成的拓撲圖

3 實 驗

本章將展示算法的有效性，并通過廣泛的實驗證明房間檢測為拓撲圖匹配所帶來的提升。

圖4 含Voronoi圖和Alpha Shape的地圖

圖5 采用房間檢測由圖4生成的拓撲圖

圖6 不采用房間檢測由圖4生成的拓撲圖

3.1 機器人世界杯救援比賽地圖

測試中使用的拓撲地圖由2010新加坡救援機器人世界杯的原始地圖[14，15]生成。這些地圖已被用于一些基于拓撲地圖的測試中，其對應的三維地圖也被用于三維地圖評估測試[16]。

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

3.2 對匹配的影響

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

圖7 Belgioioso地圖

圖8 Edmonton Convention Center

圖9 Longwood地圖

圖10 SDR Site B

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

圖11 Beeson地圖

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

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

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

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

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

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

總的來說，噪點與墻壁間距離越遠，房間檢測所帶來的正面效應就越少，因為它們會越來越多地影響房間的整體拓撲結構，但p值對比率的整體影響較小。效率方面，用于比較的兩幅地圖的拓撲圖生成過程（含房間檢測與匹配）的速度很快，單地圖耗時還不到一秒。

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

4 結 論

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

由于算法生成的地圖具有一定的穩(wěn)定性，可將本文中算法與文獻[7]中的拓撲圖匹配相結合。今后，還可將其與另一文獻[19]中的路徑匹配相整合。未來，這一算法將有助于生成適用于多樣化應用場景的極為魯棒的地圖。

[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]//會議/論文集缺失，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稿件編號：201606004

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