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

在審

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

1.一種基于三維歐式距離變換的房間分割方法，其特征在于，包括以下步驟；

步驟一：三維空間占用概率網格計算，對激光掃描點云所占用的三維空間進行三維網格劃分；利用三維布雷森漢姆直線算法確定三維網格中每個體素的占用概率，根據激光的掃描視點和被測物體表面點之間的射線來近似形成自由空間點，將概率值存儲到VDB三維網格數據結構中；

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

步驟三：內部球填充，對距離變換后的VDB三維網格數據進行閾值分割，采用內部球填充距離值大于給定閾值的區域；

步驟四：房間種子區域生成，根據鄰接關系構建內部球拓撲圖，采用連通子圖分割，通過連通子圖中每個內部球所占用的空間疊加三維空間網格得到初始的房間種子區域；

步驟五：波前向生長算法，最后利用波前向生長算法得到最終的三維房間分割結果，初始房間種子區域通過波前生長算法擴展到未標記的自由空間，直到所有自由體素單元都已標記，算法結束。

2.根據權利要求1所述的一種基于三維歐式距離變換的房間分割方法，其特征在于，所述步驟三中關于內部球填充的具體實現步驟為：

2.1、對閾值分割后的VDB三維網格，每個體素中存儲著該體素到其最近障礙點的距離值；得到一系列體素Voxels＝{P₁＝d₁，P₂＝d₂，...，P_n＝d_n}；

2.2、首先選擇距離變換值最大的體素為球心，最大近鄰距離為半徑進行填充；設該體素中心為P_maxd，其最近鄰距離為D_max＝max{D}，則初次填充球定義為S₁＝(O，R)＝(P_max，D_max)；

2.3、接著在所有已填充球的外部體素集合中選取具有最大近鄰距離的體素中心作為新的填充球球心，填充新的內部球。

2.4、為了減小內部球之間的重疊，每次進行填充球外部體素集合判斷時，通過限定搜索區域為當前填充球1.5倍半徑區域來提高填充的效率；

2.5、依次迭代，直至所有體素都被填充完畢，得到相交填充內部球集合S＝{S₁，S₂，...，S_n}。

3.根據權利要求1所述的一種基于三維歐式距離變換的房間分割方法，其特征在于，所述步驟四中房間種子區域生成的具體實現步驟為：

3.1、首先初始化拓撲圖GV，E，該拓撲圖以所有內部球的球心點作為圖的節點V。同時將所有內部球的球心點構成集合P，對球心點點集P構建KD樹；

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

3.3、判斷近鄰球p_j與當前球p_i是否相交，如果是，即內部球具有一定程度的相互重疊，則向拓撲圖G中添加邊E←E∪e(p_i，p_j)；

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

3.5、對圖G進行連通子圖分割，得到連通域集合C＝{C₁，C₂，...，C_n}；為連通域賦予初始房間語義標記ID；將連通域中每個內部球占據的空間所包含的體素標記為相應的初始房間標記ID，得到包含房間種子區域信息的體素網格S_{initial_label}。

4.根據權利要求1所述的一種基于三維歐式距離變換的房間分割方法，其特征在于，所述步驟五中波前向生長算法的具體實現步驟為：

4.1、為波前向生長算法深度拷貝初始房間語義標記S_{initial_label}，記作S_{copy_label}；對于任意一個體素單元s，遍歷其在初始房間語義標記S_{initial_label}中的26個近鄰體素，如果近鄰中存在一個房間語義標記值s_label，則將當前體素賦值為s_label；

4.2、利用S_{copy_label}更新S_{initial_label}；

4.3、重復4.1-4.2步驟，直到所有的體素都已經被賦予一個房間語義標記；

4.4、得到最終的房間語義分割結果，保存為VDB格式*.vdb文件。