[發(fā)明專利]一種基于KD樹和優(yōu)化圖變換的點(diǎn)云屬性壓縮方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201710628315.4
• 申請(qǐng)日: 2017-07-28
• 公開（公告）號(hào): CN107403456B
• 公開（公告）日: 2019-06-18
• 發(fā)明（設(shè)計(jì)）人: 李革;邵薏婷
• 申請(qǐng)（專利權(quán)）人: 北京大學(xué)深圳研究生院
• 主分類號(hào): G06T9/00
• 分類號(hào): G06T9/00;G06T9/40
• 代理公司: 北京萬象新悅知識(shí)產(chǎn)權(quán)代理有限公司 11360
• 代理人: 黃鳳茹

1.一種基于KD樹和優(yōu)化圖變換的點(diǎn)云屬性壓縮方法，針對(duì)點(diǎn)云數(shù)據(jù)，通過新的變換塊劃分方法降低子圖問題對(duì)圖變換效率的影響，優(yōu)化圖變換核心參數(shù)，提高圖變換的壓縮性能；包括如下步驟：

1)進(jìn)行點(diǎn)云預(yù)處理，得到點(diǎn)云包圍盒大小：

讀入待處理的點(diǎn)云數(shù)據(jù)，根據(jù)點(diǎn)云的空間分布及位置坐標(biāo)計(jì)算得到包圍盒的大小；

2)采用KD樹劃分方法劃分點(diǎn)云的空間幾何結(jié)構(gòu)，得到點(diǎn)數(shù)均勻分布的變換塊：

對(duì)點(diǎn)云進(jìn)行KD樹劃分時(shí)，每次選擇點(diǎn)云位置坐標(biāo)中分布方差最大的坐標(biāo)軸作為劃分軸，在劃分軸上選取坐標(biāo)大小是中位值的點(diǎn)作為劃分點(diǎn)，迭代劃分直至達(dá)到設(shè)定的KD樹深度；

3)在變換塊內(nèi)構(gòu)建圖，將各變換塊內(nèi)的每?jī)蓚€(gè)點(diǎn)n_i、n_j之間用邊連接起來，得到由點(diǎn)n和邊ε組成的圖G，邊ε_ij的權(quán)重大小ω_ij由設(shè)定參數(shù)σ和核心參數(shù)τ確定；進(jìn)一步得到特征向量矩陣，作為圖的變換矩陣；具體過程如下：

(3-1)在每個(gè)變換塊內(nèi)構(gòu)建一張圖，塊內(nèi)所有的點(diǎn)n都是圖G上的點(diǎn)，每?jī)牲c(diǎn)ni與nj之間用一條邊ε_ij連接，邊ε_ij的權(quán)重大小ω_ij由設(shè)定參數(shù)σ和核心參數(shù)τ確定，表示為式2：

其中，參數(shù)σ是一個(gè)全局變量，反映了點(diǎn)云分布的方差，其大小不影響圖拉普拉斯矩陣特征向量的產(chǎn)生，一般采用經(jīng)驗(yàn)設(shè)定值；參數(shù)τ是判定兩點(diǎn)之間相關(guān)性的距離閾值，決定圖拉普拉斯矩陣的稀疏度，是變換矩陣核心參數(shù)；

(3-2)圖G的相鄰矩陣W是邊權(quán)重ω_ij的集合，反映變換塊內(nèi)各點(diǎn)之間的相關(guān)性；圖G的密度矩陣D是一個(gè)對(duì)角矩陣，表示為D＝diag(D₁,…D_i…,D_n)，其中D_i是相鄰矩陣第i行中非零元素的個(gè)數(shù)，反映了第i個(gè)點(diǎn)與其他點(diǎn)相關(guān)性的密度；圖G的變換算子采用拉普拉斯矩陣L，表示為式3：

L＝D-W (式3)

(3-3)對(duì)拉普拉斯矩陣L通過式4進(jìn)行特征分解，得到特征向量矩陣，作為圖變換矩陣，用于對(duì)點(diǎn)云的屬性信息的壓縮：

L＝AΛA^-1 (式4)

其中，A為特征向量矩陣；

4)對(duì)變換矩陣核心參數(shù)τ進(jìn)行優(yōu)化訓(xùn)練，得到壓縮性能最佳的變換矩陣核心參數(shù)值：

從當(dāng)前點(diǎn)云的所有變換塊中選擇部分作為訓(xùn)練數(shù)據(jù)集，對(duì)訓(xùn)練數(shù)據(jù)集的點(diǎn)云屬性信息進(jìn)行圖變換處理，得到壓縮性能最佳的變換矩陣核心參數(shù)τ的值；重復(fù)多次，直至訓(xùn)練獲得的τ值趨于一個(gè)穩(wěn)定值；具體包括如下過程：

(4-1)從當(dāng)前點(diǎn)云的所有變換塊中隨機(jī)選擇50％作為訓(xùn)練數(shù)據(jù)；

(4-2)采用取值范圍確定的τ′來表示核心參數(shù)τ，τ′的取值范圍是(0,1)，表示為式5：

其中，參數(shù)σ是一個(gè)全局變量，反映了點(diǎn)云分布的方差，其大小不影響圖拉普拉斯矩陣特征向量的產(chǎn)生，一般采用經(jīng)驗(yàn)設(shè)定值；

(4-3)對(duì)訓(xùn)練集進(jìn)行圖變換，以設(shè)定精度遍歷τ′的取值范圍，從中獲得最優(yōu)的碼流壓縮性能，并記錄下此時(shí)的τ′；重新隨機(jī)選擇訓(xùn)練集，多次訓(xùn)練至碼流壓縮比最大時(shí)對(duì)應(yīng)的τ′值趨于一個(gè)穩(wěn)定值，作為τ值；

5)對(duì)點(diǎn)云進(jìn)行屬性壓縮：

將訓(xùn)練得到的變換矩陣核心參數(shù)τ的值運(yùn)用于點(diǎn)云所有變換塊的圖變換處理，得出每個(gè)變換塊經(jīng)過變換后的變換矩陣，由此實(shí)現(xiàn)點(diǎn)云的屬性壓縮。

2.如權(quán)利要求1所述點(diǎn)云屬性壓縮方法，其特征是，步驟1)中計(jì)算包圍盒大小具體過程是：遍歷點(diǎn)云中所有點(diǎn)的三維坐標(biāo)，求出x軸最小坐標(biāo)x_min和最大坐標(biāo)x_max、y軸最小坐標(biāo)y_min和最大坐標(biāo)y_max及z軸最小坐標(biāo)z_min和最大坐標(biāo)z_max；該點(diǎn)云的包圍盒大小通過式1計(jì)算得到：

B＝(x_max-x_min)×(y_max-y_min)×(z_max-z_min) (式1)

其中，B為該點(diǎn)云包圍盒的大小。