點雲壓縮 GPCC屬性編碼 LOD劃分方式介紹(G-PCC codec description v12)

目錄

一、LOD生成

原理

代碼實作

二、LOD生成的可擴充複雜性實作

原理

代碼實作

三、LOD屬性編碼的dist2值計算方法

四、基于正常采樣的LOD生成

未完待續

LOD是一種基于層次變換的方法，是Level Of Details的縮寫，即細節層次，由Clark于1976年首次提出，已廣泛用于計算機圖形的實時3D技術中。

G-PCC提出了利用LOD對點雲屬性壓縮的方法，現階段LOD在點雲壓縮中的主要作用是屬性資訊的預測編碼。

G-PCC标準中屬性編碼LOD劃分方法如下

一、LOD生成

原理

LOD生成過程(如圖1)是根據計算曼哈頓(manhadun)距離和使用者自定義距離

的關系将點雲資料中各點重新組織成一系列的層次

。 (曼哈頓距離介紹見：曼哈頓(Manhattan)距離_點雲渣的部落格-CSDN部落格)。使用者自定義距離

，并且需滿足以下兩個條件：

1. 

2. 

LOD算法實作步驟如下：

1. 将所有點标記為未通路，并将通路點集表示為V，初始狀态時，V設定為空。

2. 該步驟是循環周遊的過程，每次周遊得到一個空間劃分的子層。細化層次

生成過程如下：

        1）循環周遊所有點

        2) 如果已通路目前點，則忽略該點

        3) 否則，計算目前點到集合V的最小距離D

        4) 如果距離D小于

，則忽略目前點

        5) 如果 D >= 

 , 則目前點标記為已通路，并添加到 

 和 V

        6) 重複此過程，直到周遊所有點

3. 将空間子層進行合并，得到每一層LOD空間劃分的結果，第

層的LOD劃分，即

 是根據空間子層

 、

 、... 、

 的并集得到的。

4. 重複此過程，直到生成所有LOD或通路完所有點。

圖1 （源自mpeg-pcc标準文檔）

代碼實作

待續

二、LOD生成的可擴充複雜性實作

原理

為了提供提升方案的可擴充複雜性實作，G-PCC引入了：

        （1）使用自下而上的方法來建構LOD，而不是自上而下的技術；

        （2）使用近似最近鄰搜尋替代精确最近鄰搜尋加速LOD的建構；

          (3)  使用了莫頓碼 (莫頓碼原理見：莫頓碼（Morton code）介紹_點雲渣的部落格-CSDN部落格)

設 

 ，

 是與點雲相關聯的位置集合，設 

 ，

 為與 

 相關聯的莫頓碼。

 和 

 為兩個使用者自定義參數，分别指定初始采樣距離和LOD之間的距離比。（ 

 ）

首先，根據相關的莫頓碼按升序對點進行排序。假設 

 是根據這個過程排序的點索引數組。算法疊代進行，對每次疊代k，提取屬于 

 的點，并從 

 開始建構直到将所有點配置設定給LOD。

算法執行過程如下：

1. 初始化采樣距離D為：

2. 對于每次疊代k（k = 0...LOD層數）。設 L(k)是屬于第k各LOD點的索引集合，O(k)是屬于高于k的點的集合。L(k) 和 O(k) 的計算如下：

        （1）if k = 0， L(k) = {} else L(k) = L(k-1)

        （2）O(k) = {}

3. 按順序周遊存儲在數組 

 中的索引。每次選擇索引 i 并計算 i 到 O(k)的最近SR1點的距離。SR1是使用者定義的參數，用于控制最近鄰居搜尋的準确性。例如，SR1可以選擇為8、16或64。SR1的值越小，計算複雜度和最近鄰搜尋的準确性就越低。如果到SR1點的距離中的任何一個小于D，則将 i 添加到數組L(k)，否則，将 i 添加到數組O(k)中。

4. 疊代所有點，直到周遊完

中所有索引。在這個階段，計算L(k)和O(k)用于建構與L(k)相關的預測器。設R(k) =L(k) - L(k-1) 是需要添加到LOD(k-1)以獲得LOD(k)的點的集合。我們希望在O(k)中找到 i 的h個近鄰 (h為使用者自定義參數，用于控制預測的鄰居的最大數量)，并計算與 i 相關的預測權重

。算法執行過程如下：

        （1）初始化計數器 j = 0

        （2）對于 R(k) 中的每個點 i ，

                1）設 

 是與 i 相關聯的Morton碼，設 

 是與數組O(k)的第 j 個元素相關聯的

          Morton碼。

                2）當（Mi ≥ Mj ∧ ( j < SizeOf( O(k) ) ）時，将計數器 j 遞增1（j = j+1）

                3）計算

 到與 O(k) 的索引相關聯的點的距離，這些點在數組的範圍 [j-SR2，j+SR2]内，并跟蹤h個最近的鄰居（n1，n2，…，nh）及其相關的平方距離 

 。SR2是使用者定義的參數，用于控制最近鄰居搜尋的準确性。SR2的可能值為8、16、32和64。SR2的值越小，計算複雜度和最近鄰搜尋的準确性越低。

                      a. 如果目前點和最後一個處理點之間的距離低于門檻值，則使用最後一個點的鄰居作

                為初始猜測，并在它們周圍搜尋。

                      b. 疊代到 n=1，2，3，4…last點

                      c. 排除距離大于使用者自定義門檻值的點

5.  

, 

代碼實作

待續

​​​​​​​三、LOD屬性編碼的dist2值計算方法

引入了一種計算LOD生成參數的低複雜度、全自動非标準技術。

為LOD屬性編碼選擇dist2值的一般原則是在最佳細節層次和次細節層次中獲得1:4的點數比。目前的dist2值最初是在響應提案時确定的。

對于新的測試序列，dist2值（最初是一個清單）是從相似的測試序列中複制而來的，幾乎不考慮正确性。

LOD子采樣方案是下采樣的一種形式。它需要一個平方距離值來計算二次采樣率。用于編碼點雲的八叉樹也是下采樣的形式。對于八叉樹的每一級，它在每個方向上以2倍的因子向下采樣。

該方法的一個出發點是使用在八叉樹編碼過程中可以發現的資訊來近似八叉樹級别，産生總點數的四分之一的比率。假設密度均勻，最終發現類似表面的結構并進行下采樣。由于實際上這不可能發生在兩個八叉樹級别之間的精确轉換中，是以通過在轉換兩端的級别之間進行線性插值來得到LOD子采樣的平方距離。圖2顯示了不同序列的每個八叉樹級别中的點的比率。

                                        圖2（源自，mpeg-pcc标準文檔）

具體流程如下：

1. 設lvln是第n個最低八叉樹級别中唯一點的個數。lvl0表示源點雲中唯一點的個數。
2. 設lvlRation=lvln / lvl0為第n級唯一點與源點雲中唯一點的數量之比。
3. 找到滿足以下條件的最小a， lvlRatioa > ¼
4. 在lvlRatioa和lvlRationa+1的值之間進行線性插值，以确定y=¼時的x0值：

x0 = (¼ − lvlRatioa) / (lvlRatioa+1 − lvlRatioa) + a + 1

      5. 将平方距離确定為

雖然基本方法提供了一個合理的近似值，但并不總是産生所需的比率。平方距離值可以通過如下疊代插值來細化，以便以增加計算工作量為代價提高RD性能。

以i=0開始

1. 使用平方距離di對點進行LoD二次采樣，以确定最佳LoD點的真實比率lodRatioxi。
2. 線性插值如下：

​​​​​​​

      3. 重複使用連續值if i，直到達到以下任一條件：

               1） lodRatioxi非常接近¼，  

                2）di的連續值已收斂。（因為di是整數，是以可能收斂）

       4. 使用最終疊代中的di作為LoD生成的dist2。

四、基于正常采樣的LOD生成

介紹了一種低複雜度的LOD生成過程，該過程可以更好地捕捉初始點分布，并可以對不規則采樣點雲上定義的非平滑屬性信号進行更有效的預測。它具有線性複雜性，并且不需要對點進行第二次重新排序。相反，它直接利用用于确定預測鄰居的點的基于莫頓的排序。

設 

是有序索引的集合和 

 表示整個點雲的關聯LOD。它不是定義一組采樣距離，而是定義一組表示為 

 的采樣率，其中 

 是描述

 的采樣率的整數（例如，

=4）。與 LOD

 相關聯的索引的有序數組，表示為 

 , 通過對 

 進行二次采樣來計算，同時保留每

 個索引中的一個索引。采樣率kl可以用LOD進一步更新，以便更好地适應點雲分布。更準确地說，編碼器可以在比特流中針對預定義的一組點（例如，每個連續的H＝1024個點）顯式地編碼要應用于最新可用kl值的不同值或更新。kl可以基于信号的特性或點雲分布、先前的統計資料自動确定，或者可以是固定的。可以針對每個屬性（例如，顔色、反射率）和每個通道（例如，Y和U/V）定義不同的子采樣率

未完待續