[發(fā)明專利]一種基于內(nèi)部圓和鄰接圖的房間分割方法

在審

• 申請?zhí)枺?/td>: 202110598912.3
• 申請日: 2021-05-31
• 公開（公告）號: CN113160235A
• 公開（公告）日: 2021-07-23
• 發(fā)明（設計）人: 楊帆;張馳;張季一;車明亮;王英利;曹鑫亮;陸佩華
• 申請（專利權）人: 南通大學
• 主分類號: G06T7/10
• 分類號: G06T7/10;G06T7/62
• 代理公司: 南京瑞弘專利商標事務所(普通合伙) 32249
• 代理人: 徐激波

本發(fā)明公開了一種基于內(nèi)部圓和鄰接圖的房間分割方法,該方法首先對激光掃描得到的二維占用概率柵格地圖進行距離變換，計算每個像素其最近鄰占用點的距離值；接著采用內(nèi)部圓填充自由空間，構建室內(nèi)自由空間的內(nèi)部圓逼近；基于內(nèi)部圓的鄰接關系構建室內(nèi)拓撲網(wǎng)絡，采用帶權重無向鄰接圖構建內(nèi)部圓之間的關聯(lián)關系；基于規(guī)則對無向圖邊進行增加和刪除，實現(xiàn)圖的連通子圖分割；通過對內(nèi)部圓連通子圖進行合并，得到不同的鄰接圓聚類，賦予鄰接圓聚類不同的房間語義信息，最終實現(xiàn)室內(nèi)自由空間（即房間）的語義分割。該方法可以應用于移動機器人激光掃描過程中對室內(nèi)空間的房間分割和任務規(guī)劃。

技術領域

本發(fā)明涉及一種基于內(nèi)部圓和鄰接圖的房間分割方法，屬于移動機器人和激光測量技術領域。

背景技術

在機器人領域，利用激光掃描數(shù)據(jù)建立未知環(huán)境的環(huán)境地圖具有重要意義。隨著技術的發(fā)展，服務機器人變的日益普及，如掃地機器人、導游服務機器人、餐飲服務機器人等，在其工作的過程中都依賴同時定位與建圖技術（SLAM）來實現(xiàn)自己位置估計和環(huán)境感知，進而實現(xiàn)路徑規(guī)劃和任務規(guī)劃。在建筑工程領域，對于大多數(shù)新建筑，最新的國家規(guī)范要求提供建筑信息模型（BIM），但這些模型在建筑竣工后就不再適用了。在建筑物竣工后，每一次設計裝修都會帶來室內(nèi)環(huán)境的變化，需要審核這些變化是否符合安全標準，因此保持建筑物數(shù)據(jù)的現(xiàn)勢性十分必要。目前利用移動激光掃描（MLS）系統(tǒng)構建的室內(nèi)地圖通常是柵格地圖，在表達室內(nèi)空間語義和拓撲結構方面存在不足。如何利用移動激光掃描技術快速生成用戶所需的房間語義信息和拓撲結構，對機器人和人類用戶的室內(nèi)外一體化導航都具有重要意義。

發(fā)明內(nèi)容

針對上述現(xiàn)有技術存在的問題，本發(fā)明提供一種基于內(nèi)部圓和鄰接圖的房間分割方法，從而實現(xiàn)從激光掃描點云數(shù)據(jù)中提取室內(nèi)空間語義和拓撲網(wǎng)絡。

為了實現(xiàn)上述目的，本發(fā)明采用的技術方案是：一種基于內(nèi)部圓和鄰接圖的房間分割方法，其特征在于，包括如下步驟；

步驟一：距離變換，對激光掃描得到的二維占用概率柵格地圖進行距離變換，計算每個像素的最近鄰占用點的距離值；

步驟二：內(nèi)部圓填充，使用內(nèi)部圓表達室內(nèi)自由空間，構建室內(nèi)自由空間的內(nèi)部圓逼近；

步驟三：拓撲鄰接圖構建，利用帶權重無向圖構建內(nèi)部圓之間的關聯(lián)關系，根據(jù)內(nèi)部圓之間的鄰接關系，構建內(nèi)部圓的無向圖表達，無向圖的每個節(jié)點對應著一個內(nèi)部圓，無向圖的邊連接相切的兩個內(nèi)部圓，權重值為切點的初次距離變換值；

步驟四：連通子圖分割，基于規(guī)則對無向鄰接圖的邊進行增加和刪除；

步驟五：連通子圖合并與房間語義賦值，通過合并內(nèi)部連通子圖得到室內(nèi)自由空間的空間結構。

進一步的，所述步驟二中內(nèi)部圓填充的具體步驟為：

2.1、對給定的室內(nèi)激光掃描點云，根據(jù)其占用的空間范圍細分為網(wǎng)格，得到一系列像素，查找每個像素中心的最近鄰點和最近鄰距離，定義每個像素的距離變換集合為

2.2、選擇距離變換值最大的像素為圓心，最大近鄰距離為半徑進行填充；設該像元中心為，其最近鄰距離為，則初次填充圓定義為；

2.3、對未被內(nèi)部圓填充區(qū)域進行距離變換值更新，對比未被填充區(qū)域的像素中心距離最近鄰點的距離dB與像素中心到填充圓邊界的距離dS，更新該像素的距離變換值；

2.4、從距離變換更新后的填充圓外部像素集合中選取最大近鄰距離的像素中心作為新的填充圓圓心，填充新的內(nèi)部圓；

2.5、依次迭代，直至所有像素都被填充完畢，得到非相交填充內(nèi)部圓集合。

進一步的，所述步驟三中拓撲鄰接圖構建的具體實現(xiàn)步驟為：

3.1、初始化鄰接圖GV, E；所有內(nèi)部圓的中心點作為鄰接圖的節(jié)點V；根據(jù)所有內(nèi)部圓的中心點構成集合P，對點集P構建KD樹；

3.2、遍歷每一個內(nèi)部圓的圓心點p，搜索其2半徑范圍的近鄰圓心點；

3.3、判斷近鄰圓與當前圓是否相切，如果是，向鄰接圖G中添加邊；