[發(fā)明專利]一種基于三維歐式距離變換的房間分割方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202110906798.6
• 申請(qǐng)日: 2021-08-09
• 公開（公告）號(hào): CN113628224A
• 公開（公告）日: 2021-11-09
• 發(fā)明（設(shè)計(jì)）人: 楊帆;張馳;車明亮;張季一;王英利;曹鑫亮;陸佩華
• 申請(qǐng)（專利權(quán)）人: 南通大學(xué)
• 主分類號(hào): G06T7/11
• 分類號(hào): G06T7/11;G06T7/136;G06T7/187
• 代理公司: 南京瑞弘專利商標(biāo)事務(wù)所(普通合伙) 32249
• 代理人: 徐激波

本發(fā)明公開了一種基于三維歐式距離變換的房間分割方法，該方法首先對(duì)激光掃描點(diǎn)云進(jìn)行三維占用概率計(jì)算，將概率值存儲(chǔ)到VDB三維網(wǎng)格數(shù)據(jù)結(jié)構(gòu)中；接著進(jìn)行三維歐式距離變換，計(jì)算每個(gè)體素到其最近鄰占用點(diǎn)的距離值；對(duì)距離變換后的VDB數(shù)據(jù)根據(jù)給定距離閾值進(jìn)行閾值分割，采用內(nèi)部球填充距離值大于給定閾值的空間；根據(jù)填充內(nèi)部球之間的鄰接關(guān)系構(gòu)建拓?fù)鋱D，對(duì)拓?fù)鋱D進(jìn)行連通子圖分割，通過連通子圖中每個(gè)內(nèi)部球所占用的空間疊加三維網(wǎng)格得到初始的房間種子區(qū)域；最后利用波前向生長(zhǎng)算法得到最終的三維房間分割結(jié)果。本發(fā)明直接在三維空間實(shí)現(xiàn)房間分割，可以解決跨樓層空間、房間嵌套房間等復(fù)雜三維室內(nèi)環(huán)境的語(yǔ)義分割問題。

技術(shù)領(lǐng)域

本發(fā)明涉及一種基于三維歐式距離變換的房間分割方法，屬于移動(dòng)機(jī)器人和激光測(cè)量技術(shù)領(lǐng)域。

背景技術(shù)

房間分割(Room segmentation)是機(jī)器人領(lǐng)域重要的研究課題，是機(jī)器人任務(wù)規(guī)劃和導(dǎo)航的主要依據(jù)。幾十年來，研究人員一直在研究占用概率柵格圖像的分割。通常可以采用四種算法實(shí)現(xiàn)占用概率柵格圖像的房間分割：(1)基于Voronoi的房間分割方法；(2)基于特征的房間分割方法；(3)形態(tài)學(xué)房間分割方法；(4)距離變換方法。在機(jī)器人領(lǐng)域中，上述方法主要基于單樓層點(diǎn)云投影到二維證據(jù)柵格圖像實(shí)現(xiàn)，將三維點(diǎn)云投影到二值圖像，實(shí)現(xiàn)了二維平面柵格地圖的房間分割，可以滿足基于每個(gè)樓層進(jìn)行房間分割，然而這些方法難以解決跨樓層空間、房間嵌套房間等復(fù)雜三維室內(nèi)環(huán)境的語(yǔ)義分割問題，是制約非曼哈頓世界室內(nèi)三維建模的瓶頸問題。將二維柵格的房間分割算法直接拓展到三維網(wǎng)格存在很多困難，如存儲(chǔ)空間急劇增長(zhǎng)，計(jì)算時(shí)間長(zhǎng)。但是直接在三維空間實(shí)現(xiàn)房間分割也有許多明顯的優(yōu)勢(shì)，如三維空間可以提供更豐富的幾何和空間結(jié)構(gòu)信息，可以滿足更加廣泛的應(yīng)用需求包括跨樓層空間、房間嵌套房間等復(fù)雜室內(nèi)三維環(huán)境的語(yǔ)義分割。實(shí)現(xiàn)三維房間語(yǔ)義分割需要充分考慮點(diǎn)云包含的幾何和室內(nèi)空間結(jié)構(gòu)信息才能得到更加可靠的分類結(jié)果。

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

針對(duì)上述現(xiàn)有技術(shù)存在的問題，本發(fā)明提供一種基于三維歐式距離變換的房間分割方法，從而解決上述問題。

為了實(shí)現(xiàn)上述目的，本發(fā)明采用的技術(shù)方案是：一種基于三維歐式距離變換的房間分割方法，包括以下步驟；

步驟一：三維空間占用概率網(wǎng)格計(jì)算，對(duì)激光掃描點(diǎn)云所占用的三維空間進(jìn)行三維網(wǎng)格劃分；利用三維布雷森漢姆直線算法確定三維網(wǎng)格中每個(gè)體素的占用概率，根據(jù)激光的掃描視點(diǎn)和被測(cè)物體表面點(diǎn)之間的射線來近似形成自由空間點(diǎn)，將概率值存儲(chǔ)到VDB三維網(wǎng)格數(shù)據(jù)結(jié)構(gòu)中；

步驟二：三維歐式距離變換，計(jì)算每個(gè)體素到其最近鄰占用點(diǎn)的距離值；算法包括兩個(gè)過程可以用類似于上升波和下降波的概念進(jìn)行描述；上升波：當(dāng)一個(gè)障礙物被移除時(shí)，以索引s為最近障礙物的網(wǎng)格單元集合需要按照順序進(jìn)行重置，從而產(chǎn)生一個(gè)類似于上升波的過程；下降波：當(dāng)添加障礙物時(shí)，需要檢查其周圍的網(wǎng)格單元，更新這些網(wǎng)格單元的距離值，從而產(chǎn)生一個(gè)類似于下降波的過程；

步驟三：內(nèi)部球填充，對(duì)距離變換后的VDB三維網(wǎng)格數(shù)據(jù)進(jìn)行閾值分割，采用內(nèi)部球填充距離值大于給定閾值的區(qū)域；

步驟四：房間種子區(qū)域生成，根據(jù)鄰接關(guān)系構(gòu)建內(nèi)部球拓?fù)鋱D，采用連通子圖分割，通過連通子圖中每個(gè)內(nèi)部球所占用的空間疊加三維空間網(wǎng)格得到初始的房間種子區(qū)域；

步驟五：波前向生長(zhǎng)算法，最后利用波前向生長(zhǎng)算法得到最終的三維房間分割結(jié)果，初始房間種子區(qū)域通過波前生長(zhǎng)算法擴(kuò)展到未標(biāo)記的自由空間，直到所有自由體素單元都已標(biāo)記，算法結(jié)束。

進(jìn)一步的，所述步驟三中關(guān)于內(nèi)部球填充的具體實(shí)現(xiàn)步驟為：

2.1、對(duì)閾值分割后的VDB三維網(wǎng)格，每個(gè)體素中存儲(chǔ)著該體素到其最近障礙點(diǎn)的距離值；得到一系列體素Voxels＝{P₁＝d₁，P₂＝d₂，...，P_n＝d_n}；