[發明專利]一種基于多層跳序樹結構的變分辨率點云簡化方法

有效

• 申請號: 202110496447.2
• 申請日: 2021-05-07
• 公開（公告）號: CN113342999B
• 公開（公告）日: 2022-08-05
• 發明（設計）人: 解楊敏;張莉君;楊巧妮;高云涵
• 申請（專利權）人: 上海大學
• 主分類號: G06F16/51
• 分類號: G06F16/51;G06F16/53
• 代理公司: 上海上大專利事務所(普通合伙) 31205
• 代理人: 何文欣

1.一種基于多層跳序樹結構的變分辨率點云簡化方法，其特征在于：包含點云快速存儲以及變分辨率點云簡化兩部分；

其中，點云快速存儲部分包含構建多層級跳序空間、以跳序樹結構存儲點云數據兩個步驟；變分辨率點云簡化部分包含計算有效體積元素局部曲率、變分辨率點云簡化兩個步驟；

所述點云快速存儲部分的具體步驟為：

步驟一、構建多層級的跳序空間：

首先，讀取原始三維點云數據，獲得原始三維點云在X，Y，Z坐標軸上的最大值和最小值，建立包含所有數據的最小外接立方體，并以某一角點為原點建立與原坐標軸平行且方向一致的XYZ坐標系，沿各軸選取基準單位，把點云數據的坐標空間劃分為若干個小立方體；空間中任意一個被劃分的包含點云的小立方體為有效體積元素V_{i，j，k}，其中i，j，k為有效體積元素幾何中心的基于所選基準單位的坐標索引；

其次，設定有效體積元素V_{i，j，k}的分層索引為(i，j，L，k)，其中L是Z方向上所屬層級的索引；設定L的初值為1，設定分層估計值h_L；從XY平面上i，j最小的位置，選擇k值最小的有效體積元素開始，沿Z正方向，依次判斷相鄰兩個有效體積元素之間的k值差是否大于h_L，如果大于，則k值較大的有效體積元素的L索引等于k值較小的有效體積元素的L索引加一，否則，k值較大的有效體積元素的L索引等于k值較小的有效體積元素的L索引，直到完成所有具有該i，j索引的有效體積元素的層級索引L的賦值；遍歷XY平面上其它有效體積元素的位置，重復前述操作，實現所有有效體積元素V_i，j，k的層級索引L的賦值；由有效體積元素V_{i，j，k}以及分層索引(i，j，L，k)構成的空間即為多層級的跳序空間；

步驟二、以跳序樹結構存儲點云數據：

構建深度為4的樹狀存儲結構，樹的交匯處或末端處稱為結點，用于存儲數據；從根結點開始為第0層，它的子節點構成第1層，命名為d1層，同理依次劃分層級，命名得到d2層、d3層、d4層；對任意一個有效體積元素V_{i，j，k}，d1層的結點存儲索引i，d2層的結點存儲索引j，d3層的結點存儲層級索引L，d4層的結點存儲索引k，上述檢索存儲結構稱為跳序樹結構；使用該跳序樹結構存儲的索引，快速檢索到有效體積元素V_{i，j，k}包含的點云坐標集(x，y，z)_ijk；

變分辨率點云簡化部分的具體步驟為：

步驟一、計算有效體積元素局部曲率：

利用主成分分析方法對有效體積元素V_{i，j，k}的局部曲率進行數值估算：

利用公式1計算協方差矩陣C_{i，j，k}：

其中n_{i，j，k}為有效體積元素V_i，j，k中的點云數量，q_r為有效體積元素V_i，j，k中的第r個數據點的三維坐標，O_{i，j，k}為有效體積元素V_{i，j，k}所含數據點的均值三維坐標；

利用公式2計算協方差矩陣C_i，j，k的特征向量和特征值^mλ_{i，j，k}：

利用公式3計算有效體積元素V_i，j，k的局部曲率估值Curv_{i，j，k}為：

⁰λ_i，j，k、¹λ_{i，j，k}、²λ_{i，j，k}依次為協方差矩陣C_{i，j，k}從大到小的特征值；

步驟二、變分辨率點云簡化：

利用公式4計算N_{i，j，k}，N_i，j，k為從有效體積元素V_i，j，k中選取的點云數據數量；

N_{i，j，k}＝a×(Cur_{i，j，k})^b+c (4)

其中，a，b，c是上述點云簡化公式的參數，且a＞0，b＞0，c＞0，由用戶調整，可適應不同的地形情況；從每個有效體積元素V_i，j，k的原始點云數據中，隨機選擇N_{i，j，k}個點云數據作為該有效體積元素簡化后的點云數據集P_{i，j，k}，所有有效體積元素V_{i，j，k}的P_{i，j，k}組成最終的變分辨率點云數據集P。