[發明專利]一種基于內部圓和鄰接圖的房間分割方法

在審

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

1.一種基于內部圓和鄰接圖的房間分割方法，其特征在于，包括如下步驟；

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

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

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

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

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

2.根據權利要求1所述的一種基于內部圓和鄰接圖的房間分割方法，其特征在于，所述步驟二中內部圓填充的具體步驟為：

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

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

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

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

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

3.根據權利要求1所述的一種基于內部圓和鄰接圖的房間分割方法，其特征在于，所述步驟三中拓撲鄰接圖構建的具體實現步驟為：

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

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

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

3.4、依次迭代，直至所有內部圓的圓心點遍歷完畢。

4.根據權利要求1所述的一種基于內部圓和鄰接圖的房間分割方法，其特征在于，所述步驟四中的連通子圖分割的具體實現步驟為：

4.1、設置門的寬度閾值，最小房間面積閾值；

4.2、遍歷鄰接圖G中的每一條邊e，當邊e連接的兩個內部圓的面積足夠大且相鄰兩個內部圓的權重小于給定閾值時，移除該邊e；

4.3、遍歷每一個鄰接圖G中每一個內接圓節點v，如果其相鄰的兩個內部圓面積足夠大，且中心點的距離變換值大于，增加一條邊；如果中心點的距離變換值小于等于，移除權重較小的一條邊；得到新的鄰接圖G’；

4.4、對圖G’進行連通子圖分割，得到連通域集合；

為連通域賦予初始房間語義標記ID。

5.根據權利要求1所述的一種基于內部圓和鄰接圖的房間分割方法，其特征在于，所述步驟五中的連通子圖合并與房間語義賦值的具體實現步驟為：

5.1、遍歷連通域集合C每一個連通子圖，基于初始的無向圖G構建的近鄰子圖列表，同時統計與近鄰子圖的鄰接度，即鄰接的邊數；

5.2、遍歷每一個，判斷與其它連通子圖的鄰接度，根據鄰接度降序排列，取鄰接度最大的子圖，如果子圖的面積小于最小房間面積閾值且通達度大于3，則合并兩個連通子圖；更新的節點集合，更新的近鄰子圖列表和鄰接度統計信息；

5.3、刪除子圖，更新所有其它但不包括的子圖的近鄰和鄰接度統計信息，更新集合；

5.4、對于更新后的集合，依次迭代，直到所有的連通子圖都已經合并；

5.5、將C根據子圖的面積降序排列；遍歷每一個，判斷與其連通的子圖，根據面積降序排列，如果子圖的面積小于最小房間面積閾值，則合并兩個連通子圖；更新的節點集合，更新的近鄰子圖列表和鄰接度統計信息；

5.6、刪除子圖，更新所有其它但不包括的子圖的近鄰和鄰接度統計信息，更新集合；

5.7、對于更新后的集合，依次迭代，直到所有的連通子圖都已經合并；

5.8、輸出房間語義信息到每一個內部圓節點。