編碼網格模型的方法、已編碼網格模型和解碼網格模型的方法

2023-05-03 11:11:16

編碼網格模型的方法、已編碼網格模型和解碼網格模型的方法
【專利摘要】許多3D網格模型具有大量小的在不同的位置、規模和方向上重複的連接組件。相應的位置由每個組件的至少一個參考點的位置來定義。為了增強編碼相應的參考點的位置，給定的空間被劃分成段（Q1-Q4、r1-r3、sq1-sq3）並確定位於每個特定的段中的點的數量。當至少具有n個點的單元格（Q2）被細分為子單元格（r1）時，添加指示父單元格的所有點是否只在一個子單元格中的指示符。如果是這樣，則編碼唯一非空的子節點的索引，而否則，兩個子單元格之一中是的點的數量被遞減和編碼。本發明避免了單元格的無效細分，並因此提高了壓縮效率。
【專利說明】編碼網格模型的方法、已編碼網格模型和解碼網格模型的 方法【技術領域】[0001]本發明涉及一種編碼網格模型的方法、相應的編碼裝置、已編碼網格模型、解碼網 格模型的方法和相應的解碼裝置。【背景技術】[0002]20世紀90年代初以來已經提出了各種算法來高效地壓縮3D網格。然而，早期的 工作但大多集中在壓縮具有光滑表面和小三角形的單一連接的3D模型。在大多數今天的 大型3D工程模型中有大量的小到中型尺寸的連接組件，每個組件具有平均高達數百個多 邊形。通常這種類型的模型具有多種幾何特徵或在不同的位置、規模和方向上重複的組件。 這種模型被稱為多連接的。分別地壓縮組件導致相對低效的壓縮。通過去除不同的相連接 的組件之間的冗餘可以大大地提高壓縮性能。已知用於在大型3D工程模型中自動發現重 復的幾何特徵的各種方法。他們各自的位置由每個組件的至少一個參考點的3D位置來定 義。然而，有一個問題是如何編碼所述相應參考點的位置。[0003]大多數用於空間點的高效壓縮算法是基於空間樹的，例如，基於kd_樹(如 [0G02]:0.Devillers, P.Gandoin 在 2OOO 年的 IEEE Visualization 第 319-326 頁的 「Geometric compression for interactive transmission，，)或基於八叉樹(如[PK05]: J.L.Peng、C._C.Jay Kuo在2005年的ACM計算機繪圖專業組/ACM學報上關於圖形學的第 24 (3),第 609-606 頁的 「Geometry-guided progressive lossless3D mesh coding with octree (OT) decomposition，，)。[0004]這些算法將給定空間劃分成段，並將輸入空間點的數量設置放在每個特定的分段 中。因此，他們通過隱含的空間樹組織輸入空間點。然後，他們遍歷該樹結構並記錄用於稍 後重構輸入點的必要信息。建立空間樹時，單元格被遞歸地細分直到每個非空單元格足夠 小到只包含一個頂點和使得能夠足夠精確地重構點位置。[0005]單元格對應於節點。初始地，將所有3D點的整個邊界框視為一個單元格或節點。 由於可以從相應單元格的邊界框重構點位置，基於空間樹的算法可以以與單一解析度壓縮 算法相同的壓縮比實現多解析度壓縮。[0006][0G02]中所使用的方法的示例示於圖1。每當父單元格被細分為兩個子單元格 時，編碼兩個子單元格中的一個(例如左或上)中的點的數量。如果父單元格包含P個點，可 以利用算術編碼器使用1g2 (P+1)比特來編碼一個子單元格中的點的數量。[0007]與上述不同，[PK05]將一個非空單元格細分為八個單元格，並且在每次單元格細 分後只編碼非空子單元格的索引。為了提高編碼效率，[PK05]估計將成為非空子單元格的 分組的各種T-元組的偽概率。子單元格的遍歷順序是依照概率降序的。[0008]然而，為了實現緊湊存儲和快速傳輸，如何提高壓縮算法的效率是一個持續的問 題。
【發明內容】
[0009]本發明是基於對以下事實的認識:通過空間樹組織和壓縮空間點的效率主要取決於每個子樹節點是否比其父樹節點包括更少的數據點。如果子節點包含與其父節點相同的數據點(或者分別與其父節點相同數量的數據點)，則相應的細分不是有效的。這種無效的細分增加了已編碼數據的量，從而降低了壓縮效率。無效的細分越多，壓縮比就越低。[0010]本發明的一個優點是它可避免由無效的細分導致的壓縮效率的降低是，從而改善壓縮。[0011]根據本發明，首先根據其空間位置來聚類網格模型的輸入點。每個聚類包含已空間聚集的一組點。然後，使用空間樹(例如kd-樹或八叉樹)壓縮每個聚類。對於每次細分， 確定步驟確定兩個條件--第一，父單元格中的點的數量，第二，該細分是否是有效的，即，所有的所生成的子節點是否具有比父節點少的數據點。在一個實施例中，如果父單元格總共擁有的點小於給定的點的最小數量，任何細分都被傳統化編碼，即，該代碼指示在所定義的一個子單元格中的點的數量。然而，對具有至少所述點的最小數量的父單元格的細分是進行不同地編碼的。[0012]用於決定使用傳統編碼或具有模式指示的編碼模式之一的點的最小數量取決於每個父單元格和每次分割操作的子單元格的數量。為了將一個父單元格劃分為兩個子單元格，該最小數量為四。為了將一個父單元格劃分為多於兩個的子單元格，該最小數量大於四。因此，對於下面給出的所有示例，儘管在其上決定編碼模式的點的最小數量(或編碼模式決定極限值)是四，如果對於父單元格的劃分導致產生多於兩個子單元格，這個數量可以是不同的。[0013]如果父單元格一共有P個點，P至少是四，並且細分是有效的，使得在所定義的一個子單元格中有P1個點((Kp,P),則通過P1-1 (即，子單元格中點的數量減去一)的已編碼值來編碼該有效的細分。[0014]如果父單元格一共有P個點，P至少是四，並且細分是無效的，所有點只在一個子單元格中，則按照下面的方法對該細分進行編碼:該代碼使用預定義的索引方案指示非空子節點的索引，而不是點的數量。[0015]為了在父單元格具有至少四個點時對兩種編碼模式進行區分(即，有效或無效的細分)，將每個樹節點的附加模式指示符插入到結果代碼或輸出數據流。模式指示符指示相應的細分是否是有效的。[0016]編碼產生了一種新的編碼格式，其可被認為是空間樹並包含每個具有至少四個點的樹節點的指示相應的細分是否有效(即，已劃分的父單元格的所有點是否僅在一個子單元格中)的指示符。對於每次細分，隨後是上述格式中的壓縮數據，即，一個子單元格中的點的數量(如果父單元格中的點的總數小於四)，或子單元格中的點的數量減去一(如果父單元格中點的總數至少是四並且細分是有效的)，或唯一非空子節點的索引(如果父單元格中點的總數至少是四並且細分是無效的)。有利地，如果點的數量至少是四，所述索引比編碼的點的數量使用更少的比特。[0017]在解碼根據本發明的編碼格式的數據過程中，遍歷空間樹時，為每次細分計算或確定當前父單元格中的點的數量，並分析指示符(例如，I比特)以便檢測當前細分`是否是有效的。[0018]在一個實施例中，本發明涉及一種編碼網格模型的點的方法，該方法包括以下步 驟:確定點的總數並在代碼中插入所確定的點的總數，其中，使用預定義的碼字長度，根據 其空間坐標將各點聚類成一個或多個聚類，並使用分層的樹來編碼所聚類的點，其中，所述 編碼包括以下步驟:定義所述聚類周圍(即，模型的所有點的周圍)的邊界框，遞歸地劃分該 邊界框，其中，每個劃分步驟將父單元格劃分為預定義數量的子單元格(至少兩個)，並且對 於每個劃分步驟，確定當前父單元格包含的點的數量，確定父單元格的所有點是否在單一 的子單元格中，並如下所示編碼指示所述確定步驟的結果的指示符。[0019]如果所述確定得出父單元格中點的總數小於四，那麼將在特定的(預定義的)一個 子單元格中的點的數量插入到代碼中。[0020]如果所述確定得出父單元格中點的總數大於四並且父單元格中的點被分發給至 少兩個子單元格，則劃分步驟是有效的，並將指示劃分的有效性(例如，通過設置為一的單 一比特)的指示符和在特定的(預定義的)一個子單元格中的點的數量插入到代碼中。[0021]如果所述確定得出父單元格中點的總數大於四並且父單元格的所有點都在單一 的子單元格中，則劃分步驟是無效的，並將指示劃分的無效性(例如，通過設置為零的單一 比特)的第二指示符插入到代碼中，確定包含父單元格的所有點的所述單一子單元格的索 弓丨，並將該索引插入到代碼中。[0022]如果分割產生多於兩個子單元格，編碼模式決定極限值可以大於四，並在插入之 前編碼所述索引。可從由分割步驟產生的子單元格的數量得到用於編碼索引的比特的數量。[0023]在一方面，一種用於解碼網格模型的點的方法包括以下步驟:從編碼的數據集合 至少提取一個值和作為多個點的位置數據的第一數據，所述值表示點的總數並且所述第一 數據定義多個碼字，其中，每個碼字指的是將邊界框劃分為各單元格的多個遞歸劃分之一， 並且每次劃分將當前父單元格劃分為兩個或更多的子單元格，以及基於所述值和所述第一 數據來確定所述點的位置，其中，至少部分碼字包含指示當前單元格劃分步驟是否有效的 指示符(一個比特)。每個碼字的長度是固定的或可變的；如果它是可變的，可在解碼期間根 據給定的規則計算它的長度和值。[0024]對於每個當前的父單元格，它所包含的點的總數是確定的。在一個實施例中，它是 預先計算和存儲的，並且可從存儲器中檢索到。此外，計算用於編碼所確定的點的數量的比 特數計算；它被稍後用於確定碼字長度。如果點的總數小於四，相應的碼字不具有上述指示 符，並被解釋為預定義的一個子單元格中的點的數量。如果點的總數至少是四，相應的碼字 以所述指示符開始，並評價該指示符。根據所述指示符，碼字的其餘比特可以有兩種含義: 他們或者是位於從對當前父單元格的當前劃分所產生的子單元格中的預定義的一個中的 點的減小的數量。由於數量是減小的，因此需要對其加一來得到點的實際數量。碼字的其 餘比特或者是從對當前父單元格的當前劃分所產生的子單元格的索引。該索引是包含父單 元格的所有點的一個子單元格的標識符。如果碼字長度是可變的，則上述確定的比特數(力口 上一個比特作為標記符)是當前的碼字長度。如果碼字的長度是固定的，例如對於第一碼字 (即，模型中點的總數)，它是預定義的。在解碼過程中，每個頂點的位置迭代地定位在更小 的子單元格中，直到到達終止解碼的給定終止條件。[0025]本發明可以用於作為多組件模型中的組件的參考點並且表示該模型的頂點的聚類的點。原則上，本發明還可用於任何網格模型的頂點的點，或由坐標定義的任何其他大型 分組的點。[0026]一般來說，有必要記住父單元格，至少非空單元格中的點的數量。例如，存儲非空 子單元格中的點的數量直到該子單元格成為父單元格的下一次劃分之後。然後，在確定父 單元格中的點的數量時，從存儲器檢索該數量。[0027]本發明還涉及一種用於編碼的裝置，該裝置包括用於根據點的空間坐標來將所述 點聚類成一個或多個聚類的聚類部件，以及用於編碼所聚類的點的編碼部件，其中，所述編 碼部件包括用於定義所述聚類周圍的邊界框的初始化單元，用於遞歸劃分所述邊界框的遞 歸劃分單元，其中所述遞歸劃分的每個劃分步驟將父單元格分割為預定義數量的子單元 格，點分布確定單元，用於為每個劃分步驟和每個要被劃分的當前父單元格確定點的數量， 並用於確定每個父單元格的點的數量是否至少是四，編碼單元，用於如上所述當所述數量 小於四時對點的數量進行編碼，並用於如上所述當所述數量至少是四時編碼子單元格中的 點的減少的數量或子單元格索引。[0028]此外，本發明涉及用於解碼網格模型的解碼器，所述解碼器包括用於從編碼的數 據集合中提取至少第一數據和指示點的總數的初始值的提取部件，用於將邊界框遞歸劃分 為單元格的遞歸劃分部件，其中，每個遞歸劃分將當前父單元格劃分為子單元格，以及用於 根據所述子單元格來確定所述點的位置的確定部件。所述確定部件包括用於確定當前父單 元格中的點的數量的單元，用於根據所確定的當前父單元格中的點的數量來檢測編碼模式 的編碼模式檢測單元，用於從當前父單元格中的點的數量來推斷每個碼字的長度的碼字長 度檢測單元，以及用於如上所述解碼下一碼字的解碼單元。[0029]在一方面，本發明涉及一種在其上存儲有導致計算機執行包含上述編碼步驟的方 法的可執行指令的計算機可讀介質。在一方面，本發明涉及一種在其上存儲有導致計算機 執行包含上述解碼步驟的方法的可執行指令的計算機可讀介質。[0030]在一個實施例中，本發明涉及一種包含多個重複相連接的組件的編碼的網格模 型，其中，所述編碼的網格模型包含至少下列內容的編碼數據:[0031]每個重複相連接的組件的實例，[0032]編碼的相連接的組件的總數，[0033]所述重複相連接的組件的多個副本的位置，所述位置被編碼為樹結構(例如， kd-樹)，以及定義網格模型的邊界區域的數據。邊界區域是所述樹結構所指代的初始父單 元格。被編碼為樹的位置使用上述編碼，即，該編碼包括樹結構的每個節點的碼字，其中，對 於具有至少四個點的節點，如果當前父單元格的點被分發給至少兩個子單元格，所述碼字 以具有第一值的指示符開始，如果當前父單元格的點在單一的子單元格中，所述碼字以具 有不同的第二值的指示符開始，並且其中，所述碼字的剩餘比特或者表示位於預定義的一 個子單元格中的點的數量(如果指示符具有第一值)減去一，或者表示當前父單元格的包括 父單元格的所有點的子單元格的索引(如果指示符具有第二值)。[0034]在從屬權利要求、下面的描述和附圖中公開本發明的有利實施例。【專利附圖】

【附圖說明】[0035]參照附圖描述本發明的示例性實施例，附圖中，[0036]圖1示出2D示例中的kd-樹編碼的原理；[0037]圖2示出使用有效和無效細分的kd-樹中數據點的組織；[0038]圖3a)示出在不同維度上對3D父單元格的劃分，而b)示出在水平、垂直和深度的 維度上對3D父單元格的連續劃分；[0039]圖4示出a)編碼決定步驟的流程圖，b)編碼方法的流程圖和c)解碼方法的流程 圖；[0040]圖5示出a)網格模型的編碼方法的流程圖和b)網格模型的解碼方法的流程圖；[0041]圖6示出編碼示例的細節；以及[0042]圖7示出代碼樹。【具體實施方式】[0043]圖1示出在2D情況下的傳統kd-樹編碼的原理。邊界框10包圍2D模型的點。七 個點位於父單元格之內。kd樹編碼算法從使用預定義的比特數來編碼點的總數開始，然後 遞歸地細分單元格。每次將父單元格細分為兩個子單元格後，它就對兩個子單元格中的一 個中的點的數量進行編碼。下面示例編碼了左側子單元格(垂直分割之後)或上部子單元格 (水平分割之後)中的點的數量。可以彼此獨立地改變這些慣例。如果父單元格包含P個點， 則利用算術編碼器使用1g2 (P+1)比特來編碼一個子單元格中的點的數量。遞歸地應用這 種細分直到每個非空單元格足夠小到只包含一個點並且使得能夠足夠精確地重構點位置。 為了壓縮網格模型的所有點的位置(無論所述點是頂點或聚類參考點)，該算法以被視為第 一划分步驟的當前父單元格的所有位置的整體邊界框10開始。[0044]在圖1的示例中，第一個編碼值是使用32比特編碼的點的總數(7)。然後，應用垂 直分割使得獲得左側子單元格Vl和右側子單元格V2。在下一編碼步驟中，編碼左側子單 元格Vl中的為四的點的數量。由父單元格中點的數量確定用於編碼的比特數:它是1g2 (7+1)=3比特。由此，第二碼字是數字四，使用三個比特對其進行編碼。從父單元格中點的 數量和左側子單元格Vl中點的數量可以計算出右側子單元格V2中點的數量為7-4=3。[0045]在下一步驟中，對前一步驟的子單元格應用水平分割。此時作為當前父單元格Vl 的左側子單兀格Vl被分割為上部子單兀格VlHl和下部子單兀格V1H2。類似地,此時作為 父單元格V2的右側子單元格V2被分割為上部子單元格V2H1和下部子單元格V2H2。該算 法以具有兩個點的上部左側子單元格VlHl繼續。由此，接下來編碼數字2，其中在算術編碼 器中使用1g2 (4+1)=2.3比特(或在捨入後為三比特)。如上所述，不需要對下部左側子單 元格V1H2中點的數量進行編碼，因為它可以從左側單元格Vl和上部左側子單元格VlHl中 點的數量推斷出來。然後，對右側單元格V2應用同樣的步驟導致使用兩個比特來編碼零。 如圖1所示，還需要兩個分割步驟直到每個點在單獨的單元格中，並且還需要更多的步驟 直到每個點充分位於其單元格之內。每個步驟都增加了點位置編碼的精度，但需要編碼越 來越多的I或O。根據所需的精度，附加步驟的數量可能會很高。[0046]所述點可以是頂點或聚類參考點。即，本發明可以應用增強的kd_樹編碼算法至 少用於編碼頂點位置或用於編碼重複相連接的組件的位置。此外，增強的kd_樹算法原則 上也可用於編碼在給定的1D、2D或3D空間中的任何一種空間位置。[0047]圖2示出了 kd-樹的示例，其中，幾個點21-25位於2D網格模型的邊界框20之內。本發明也可以應用於ID模型或3D模型。在下面進一步描述應用該原理來編碼3D網格模型。下面所述的步驟也示於圖6。與許多大型網狀模型中的情況一樣，各點的位置在邊界框中是很不均勻地分布的。在這個示例中，將增強kd-樹編碼算法應用於編碼點的位置，並且假定所要求的精度使得在充分定位聚類之前需要五個初始劃分或分割步驟。可以通過增加分割步驟的數量來提高精度，或通過減少分割步驟的數量來降低精度。另外，根據傳統定義在本示例中，通過「 I」( 1=有效，O=無效)來編碼有效劃分的有效性指示符，並且通過將 「I」分別用於上部或左側子單元格和將「O」分別用於下部或右側子單元格來對子單元格索引進行編碼。注意，可以不同地定義這些傳統，而不會影響本發明或代碼的效率。[0048]第一碼字是使用預定義的比特數(例如，32比特，取決於點的潛在總數)的點的總數。此外，確定模型中點的總數是十三並且確定點的總數大於三。在第一划分步驟中，作為父單元格的邊界框20被垂直劃分為兩個矩形，左側(Q1+Q3)和右側(Q2+Q4)，參見圖6b)。 由於點的總數至少是四，使用根據本發明的編碼模式比特(「有效」比特)，並且由於所產生的兩個矩形都包含點，因此該劃分是有效的。因此，第二碼字是有效指示符(1=「有效」)，後面接上值五，該值五是左側子單元格中點的數量減去一。使用四個比特對其進行編碼，因為編碼父單元格中的點的總數需要四個比特(int(l0g)2(13)=4)。也就是說，在圖3的示例中， 代碼的起始部分如下:13 (點的總數，32比特)，1 (有效比特),5 (第一階段(generation)左側子單元格中點的數量減去一，4比特)。
[0049]第二劃分步驟對所述矩形進行水平劃分，使得產生四個正方形Q1，……，Q4，參見圖6cl)和c2)。從前一步驟已知兩個矩形父單元格中的每一個包含至少四個點。考慮左側矩形，劃分是無效的，因為所產生的正方形子單元格Ql、Q3中的單一的一個包含所有點。 傳統kd-樹編碼將要求編碼上部子單元格Ql中的點的數量(使用3比特)，而根據本發明的增強編碼算法只使用表示該劃分是無效的指示符和包含所有點的子單元格的索引。[0050]子單元格使用索引n=log2 (m)個比特。其中m是父單元格所產生的子單元格的數量。由於在本示例中有兩個子單元格，所述索引只使用1g2 (2)=1比特。在另一實施例中，每個劃分步驟將父單元格分割為m個相等尺寸的子單元格使得使用更多的比特來表示子單元格索引。在數字m是2的更高次冪的情況下，例如4、8、16等，這種情況提供了比m不是2的冪時更有效的代碼，該劃分可以被視為若干簡單劃分步驟的累加(在相同的維度上)。 然而，如果同時進行這些若干步驟，可以提高處理速度。例如，在各點是稀疏分布(與要實現的空間解析度相比)使得非常可能出現若干無效劃分序列時這種累加是有用的。在其他情況下，可能更好選擇n=2。[0051]返回到圖2的示例，其中父單元格被分割為兩個子單元格，有效指示符只有一個比特，從而使接下來的左側矩形Q1+Q3的碼字只包含兩個比特，即「01」(0=無效指示符，I 比特，並且1=子單元格索引，I比特)。有效性指示符(有效/無效)及隨後定義子單元格索引或一個子單元格中點的數量的比特，一般可被視為一個單一碼字。因此，碼字具有可變長度。有利地，包含子單元格索引的碼字通常短於包含代表點的數量的值的碼字。[0052]對右側矩形的劃分是有效的，因此，如圖6c2)所示，通過「I」(有效指示符，I比特) 和「3」(上部子單元格Q2中點的數量減去一，使用3個比特(因為1g2 (父單元格中點的數量)=1g2 (7) =3))來對其進行編碼。[0053]在下文中，使用短的書寫形式「值」。例如，通過三個比特編碼的值五被寫作53b°[0054]在下一步驟中，新一階段子單元格開始並改變分割維度。垂直分割每個正方形 Q1-Q4使得生成大小為rl的矩形，參見圖6dl) -d3)。對於Ql和Q2中的每一個，點的總數至少是4並且劃分是有效的(圖6dl)、d2))。左側矩形中點的數量分別是2和3。分別通過 Ilb-13b和llb_22b來對它們進行編碼。跳過Q3，因為根據上述對Q1+Q3的垂直劃分是無效的事實和該劃分的索引，很顯然Q3是空的。剩餘單元格Q4隻有三(B卩，小於四)個點24，使得通過O2b對其進行編碼(因為「所有點都在右邊的子單元格中」)，參見圖6d3)。[0055]也就是說，在圖3的示例中，此時代碼的起始部分將如下:[0056]1332b (點的總數)-1lb (有效指示符)_54b (第一階段左側子單元格)-Olb-1lb (無效指示符和上部子單元格的索引)_llb (有效指示符)_33b (Q2中點的數量)-llb-l3b-llb-22b (無效比特和矩形子單元格Ql和Q2中點的數量)_02b(所有點都在右邊的矩形子單元格Q4中)。[0057]在下面的劃分步驟中，每個尺寸為rl的(非空)矩形被水平劃分為尺寸為sql的正方形，如圖6el) -e5)所示。因此，從上部左側開始，接下來邊界框上半部分的碼字是 22b-0lb0lb-02b-llb,並且(跳過空的Q3和Q4空的左半部分)邊界框下半部分的碼字是02b。例如，最後的值O2b是指在對Q4的右半部分進行水平劃分後，它所有的點都在下部子單元格中，參見圖6e5)，因為劃分前點的總數小於四。[0058]在下面的劃分步驟中，每個尺寸為sql的(非空)正方形被垂直劃分為尺寸為r2的矩形，如圖6fl)-f5)所示。因此，從上部左側開始，接下來的碼字是22b-0lbllb(Ql中)_02b-0lb (Q2中)-32b (Q4中)。例如，了解到當前父單元格中點的總數已被先前確定為至少是四，值 OlbIlb (參見圖6f2))是指對尺寸為sql的正方形的劃分是無效的(即，「O」)並且唯一佔用的尺寸為r2的矩形在左邊(即，「I」)。[0059]在下面的劃分步驟中，每個尺寸為r2的(非空)矩形被水平劃分為尺寸為sq2的正方形，如圖6gl)-g5)所示。從上部左側開始，接下來的碼字是22b-0lb-0lb (Ql中)_32b-llb (Q2中)-02b (Q4中)。注意,只在圖6g2)所示的劃分中父單元格中點的數量大於三,使得使用了有效性指示符。圖6中,通過(p=4 )或(p>4 )來標記這些情況。[0060]在下面的劃分步驟中，每個尺寸為sq2的(非空)正方形被垂直劃分為尺寸為r3 的矩形，如圖6hl)-h5)所示。從上部左側開始，接下來的碼字是I2b-1lbI2b (Ql*)-l2b-0lb (Q2 中)-12b (Q4 中)。[0061]最後，在最後一個劃分步驟中，每個尺寸為r3的(非空)矩形被水平劃分為尺寸為 sq3的正方形，如圖6il)_i9)所示。從上部左側開始，接下來的碼字是Olb-Olb-12b-12b (Ql 中)?Α (Q2 Φ) -1lb-12b (Q4 中)。[0062]具有相同尺寸的所有子單元格被視為一個子單元格階段。例如，圖2中，如果邊界框20被視為第一階段(父階段)，則正方形Q1，……，Q4屬於第三階段。尺寸為sql的所有正方形(例如，Ql的左側上部正方形和右側下部正方形，Q2的右側上部正方形和左側下部正方形，以及Q4的右側下部正方形)都屬於相同的子單元格階段，即第五階段。注意，對任何特定階段的單元格的處理順序是依賴`於慣例的(見下文)，並可以改變，而無需修改代碼效率。[0063]使用上述編碼，所有點都被定位在尺寸為sq3的正方形的精度範圍內的邊界框中。對於完整的模型，該編碼使用了 102比特:[0064]1332b-llb54b-0lbllb-llb33b-llb-l3b-lib_22b-02b-22b-0lb0lb-02b-llb-02b-22b-0lbllb-02b-0lb-32b_22b_0ib0ib_32b-llb-02b-l2b-llbl2b-l2b-0lb-l2b-0lb-0lb-l2b-l2b-llb-l2b-llb-llb-l2b。[0065]這個簡單示例的傳統編碼(S卩，使用已知的kd-樹算法)將需要更多的一個比特。 因此，本發明提高了編碼效率。[0066]做出的無效細分越多，相較傳統方法的壓縮比改進越高，並且本發明越有利。無效 細分通常在兩種情況下發生:一種是當空間數據點顯示如上述的示例中的顯著的多個空間 聚集。即使對於具有單一空間聚集(即，單一點)的空間點集合，一些無效的細分也是不可避 免的。這是真實的，特別是當單元格中只包含一個點，但對於重構點位置來說還是太大，使 得要求進一步的無效細分來增加空間解析度。因此，點的數量越大而且點的聚類(即，空間 聚集)越顯著並且目標空間解析度越高，則根據本發明的編碼所保存的比特越多。換言之， 當點的空間分布欠均勻時，即，更多的無效細分發生時，編碼效率增加。當點的數量增加時， 這變得更加可能。[0067]有利地，本發明為平均或高複雜度的3D網格模型實現了相當大的比特節約。[0068]本發明的進一步的優點是步驟和所生成的代碼都與現有方法相比大大縮短了。[0069]本發明的進一步的優點是，它考慮了分層編碼的所有層級。[0070]雖然上面的示例使用了 2維(2D)模型，相同的原理可以很容易地用於3維(3D) 模型。如圖3a)所示，3D實施方式的邊界框和單元格是立方體或箱體，S卩，具有正方形或 矩形表面的3D對象。差異是在3D實施方式中父單元格不僅被沿水平和垂直方向劃分， 也可在第三個維度，例如深度上進行劃分。因此，取代上述2D示例中使用的劃分序列h-v-h-v......(h=水平，V =垂直),或等效的劃分序列v-h-v-h......,3D模型的劃分序列可以是 h-v-d-h-v-d-h-v-d-......(d=深度)，或 h-d-v-h-d-v-......或 v-d-h-v-d-h-......。在任何情況下，遞歸分割涉及以交替方式對所有所考慮的維度(每個維度一個新的階段)。[0071]在一個實施例中，還編碼和解碼定義邊界框的數據，例如，尺寸數據和/或位置數 據，以便允許在解碼過程中重構邊界框。[0072]圖3a)示出3D箱體的示例性的後續細分，從該箱體的水平分割ssdl產生第一階 段子單元格的任意一個的垂直分割ssd2，以及第二階段子單元格的任意一個的深度分割 ssd3。這裡應當注意，術語「劃分」、「細分」和「分割」在本文中等效地使用。圖3b)示出一 般的水平分割sdl、垂直分割sd2和深度分割sd3。本發明的有利效果是不依賴於分割維度 的順序次序的(K V用於2D，而h、V、d用於3D)。因此，次序可以是不同的。[0073]圖4a)示出在編碼點分組的位置(例如，網格模型的頂點位置)時要採取的方法步 驟的流程圖。在第一確定步驟40中，確定當前父單元格和該當前父單元格中點的總數。在 第一編碼模式決定步驟50中，確定當前父單元格中點的總數是否至少是四。如果當前父單 元格中點的總數不是至少為四(即，三或更少)，如上所述，下一步驟是用於編碼點的數量的 第一編碼步驟60。也就是說，在特定的預定義的一個子單元格(例如，垂直細分後的左側子 單元格，或水平細分後的上部子單元格，或在3D情況下在深度細分後的前部子單元格)中的 點的數量被插入到代碼中。[0074]如果當前父單元格中點的總數至少為四，那麼接下來進行第二編碼模式決定步驟 70。在第二編碼模式決定步驟70中，確定細分是否有效。如果細分是有效的，即，每個子單 元格具有至少一個點並且沒有單元格是空的，則第二編碼步驟80確定所述特定的預定義的一個子單元格中的點的數量，將其減去一，並將「有效的」標記和減少的點的數量插入到 代碼中。所述減少是有利的，因為在對具有P個點的父單元格進行有效細分後，每個子單元 格可以具有不多於P-1個點，而對P-1而不是P進行編碼可以在每次細分中節省一個比特。[0075]否則，如果細分是無效的，S卩，至少一個子單元格是空的，則在第三編碼步驟90中 將「無效的」比特和非空子單元格的子單元格索引插入到代碼中。所述索引是預定義的，例 如，「I」用於左側、上部或後部子單元格，而「O」用於右側、下部或前部子單元格。當細分產 生k個子單元格時,它使用1g2 (k)比特。[0076]在每個第一、第二和第三編碼步驟之後，如下所述，確定40下一個父單元格。[0077]注意，對於每個維度，特定的預定義的一個子單元格(例如，左側、上部和前部子單 元格)和上述子單元格索引在整個編碼和解碼過程中保持不變。[0078]一般說來，有必要記住各父單元格內，至少是非空的單元格內的點的數量。例如， 存儲非空子單元格內點的數量直到下次劃分該子單元格成為父單元格之後。然後，在確定 該父單元格中點的數量時從存儲器檢索該數量。[0079]圖4b)示出根據本發明的一個實施例的編碼網格模型的方法的流程圖。該方法包 括以下步驟:根據點的空間坐標將其聚類410為一個或多個聚類，並使用分層的樹來編碼 420-450所述聚類的點，其中，所述編碼包括以下步驟:定義420所述聚類周圍(S卩，模型的 所有點的周圍)的邊界框，遞歸地劃分430該邊界框，其中，每個劃分步驟將父單元格劃分 為預定義數量的子單元格，對於每個劃分步驟，確定440要被劃分的當前父單元格的點的 數量，確定該數量是否至少是四，並且如果該數量是三或更少，如上面相對於圖4a)的步驟 40、50、60所描述地來編碼點的數量，然後，如上面相對於圖4a)的步驟70、80、90所描述地 來編碼450各父單兀格。[0080]在本發明的一個實施例中，如果所述確定得出父單元格中點的數量至少是四並且 父單元格中的點被分發給至少兩個子單元格，則劃分步驟是有效的，並將第一指示符插入 到代碼中，並且將在特定的(預定義的)一個子單元格中的點的數量插入到代碼中，所述第 一指示符指示劃分的有效性(例如，設置為一的單一比特)。否則，如果所述確定得出父單 元格中的所有點都在單一的子單元格中，則劃分步驟是無效的，並將指示劃分的無效性(例 如，設置為零的單一比特)的第二指示符插入到代碼中。然後，確定包含所有點的所述單一 子單元格的索引，並將該索引插入到代碼中。[0081]在劃分步驟產生多於兩個子單元格的情況下，根據有效性或無效性的不同定義的 不同實施例是可能的。然而，兩者是互補的，並且每個劃分步驟不是有效的就是無效的。[0082]在一個實施例中，如果父單元格的點被分發給至少兩個子單元格(使得所產生的 所有子節點具有少於父節點的數據點)，則劃分步驟被認為是有效的，並且如果所有點都只 在一個子單元格中，則劃分步驟被認為是無效的。在這種情況下，需要除了一個子單元格之 外的每個子單元格中的點的數量來用於有效劃分(例如，如果劃分產生四個子單元格則是 指示三個子單元格中點的數量的三個值)。[0083]在另一實施例中，如果沒有子單元格是空的，則劃分步驟是有效的，並且如果至少 一個子單元格是空的，則劃分步驟是無效的。在這種情況下，依賴於慣例，可以為無效劃分 編碼空的子單元格或非空子單元格的索引。[0084]如果劃分步驟產生兩個子單元格，上述兩個實施例導致相同的結果。[0085]返回圖4b)，遞歸劃分步驟430大體上具有兩個功能:在一個功能中，它處理所有 非空的當前父單元格。除了作為第一父單元格的邊界框，所有父單元格都是已成為父階段 的前一划分步驟的子單元格。在圖2b)的示例中，這是指當前階段的所有非空子單元格，例 如，階段r2，都是如上所述順序地處理的。處理了當前父階段的所有非空子單元格後，滿足 第一停止條件SCl，並且執行所述遞歸劃分步驟430的第二功能。在第二功能中，改變435 分割維度，這導致下一子單元格階段，並且開始處理非空子單元格的下一階段。例如，如果 當前階段是圖2b)中的r2，則下一階段是sq2。因此，迭代地編碼點的位置。在滿足例如最 小子單元格尺寸(即，所需的空間解析度)或遞歸的最大數量(即，最大處理時間)的第二停 止條件SC2時，所述遞歸劃分終止。預定義的最小子單元格尺寸對應於編碼處理的目標空 間解析度。[0086]這裡，具有相同尺寸的單元格被稱為一個階段。如上所述，以輪換(即，交替)方式 對子單元格的每一階段執行改變435分割維度，例如，水平分割單元格以獲得第一階段子 單元格，垂直分割該第一階段子單元格以獲得第二階段子單元格，並且深度劃分該第二階 段子單元格以獲得第三階段子單元格。[0087]最後，所生成的代碼可以被熵編碼460。在一個實施例中，任何一個劃分步驟的所 有子單元格具有相同的尺寸。[0088]對應於圖4b )示出的上述方法步驟，在本發明的一個實施例中，一種編碼網格模型 的編碼器包括用於根據點的空間坐標來將所述點聚類成一個或多個聚類的聚類部件，以及 用於使用分層樹來編碼所聚類的點的編碼部件，其中，所述編碼部件包括用於定義所述聚 類周圍的邊界框的初始化單元，用於遞歸劃分所述邊界框的遞歸劃分單元，其中每個劃分 步驟將父單元格劃分為預定義數量的子單元格，點分布確定單元，用於為每個劃分步驟和 每個要被劃分的當前父單元格確定點的數量，並用於確定每個父單元格的點的數量是否至 少是最小數量(如果每個父單元格被分割為兩個子單元格，則該數量是四)，以及編碼單元， 當所述數量小於最小數量時，用於如上面相對於圖4a)的步驟40、50、60所描述地對點的數 量進行編碼，並用於如上面相對於圖4a)的步驟70、80、90所描述地來編碼父單元格。[0089]在本發明的一個實施例中，圖4c)示出一種解碼網格模型的方法。它包括以下步 驟:從編碼的數據集合至少提取470包括多個碼字的第一數據和指示點的總數的初始值， 遞歸地將邊界框劃分475為單元格，其中，每次遞歸劃分將當前父單元格劃分為預定義數 量的(兩個或更多的)子單元格，以及根據所述子單元格來確定480所述點的位置，其中，確 定當前父單元格中點的數量，根據所確定的當前父單元格中點的數量來檢測編碼模式，並 解碼k-Ι個下一碼字(其中，k是劃分步驟的子單元格的數量)。從當前父單元格中點的數 量推斷出每個碼字的長度。如果所確定的當前父單元格中點的數量小於四，則使用第一解 碼模式。在第一解碼模式中，每個碼字包含m比特，其中，m—般是1g2(父單元格中點的數 量)，或是根據int (1g2 (父單元格中點的數量))的整數。在第一解碼模式中，如上所述， 長度為m的碼字表示特定的預定義的一個子單元格中點的數量。[0090]如果所確定的當前父單元格中點的數量至少是四，則碼字包含指示該碼字的剩餘 比特的意義的指示符，並且如果所述指示符具有第一值，該碼字的剩餘比特定義位於從當 前父單元格的當前劃分產生的預定義的一個子單元格中的點的數量；或者該碼字的剩餘比 特定義指示從當前父單元格的當前劃分產生的並包括所述父單元格的所有點的子單元格的索引。根據子單元格確定480所述點的位置的步驟包含確定編碼模式和評價碼字中的指 示符。因此，迭代地解碼點的位置。[0091]對應於圖4c)中示出的上述方法步驟，在本發明的一個實施例中，一種解碼網格模 型的解碼器包括用於從編碼的數據集合中提取至少第一數據和指示點的總數的初始值的 所述步驟的提取部件，用於將邊界框遞歸劃分為單元格的所述步驟的遞歸劃分部件(例如， 控制部件)，其中，每個遞歸劃分將當前父單元格劃分為預定義數量(兩個或更多的)的子單 元格，以及用於根據所述子單元格來確定所述點的位置的所述步驟的確定部件。所述確定 部件包括用於確定當前父單元格中的點的數量的單元(例如，計數器)，用於根據所確定的 當前父單元格中的點的數量來檢測編碼模式的編碼模式檢測單元，以及用於解碼k-Ι個下 一碼字的解碼單元(其中，k是劃分步驟的子單元格的數量)。碼字長度檢測單元(例如，計 算器)如上所述從當前父單元格中的點的數量推斷每個碼字的長度。[0092]圖5a)示出本發明的一個實施例，其中，一種編碼網格模型的方法包括以下步驟: 建立通用的空間樹110 (這是可能被隱式包括在下一步驟中的合乎邏輯的步驟)，根據所述 通用的空間樹分析120網格模型，如上面相對於圖4b)的方框410-450、SC1、SC2所描述地 遍歷130空間樹，其中，獲得網格模型的第一編碼表示，並執行對網格模型的第一編碼表示 的熵編碼460，其中，獲得網格模型的第二編碼表示。[0093]圖5b)示出了本發明的實施例，其中，一種用於解碼編碼的網格模型的方法包括以 下步驟:對編碼的網格模型執行熵解碼150，其中，獲得熵解碼的網格模型，重建通用的空 間樹160，根據熵解碼的網格模型重建空間點聚類170，其中如上面相對於圖4c)所描述，將 空間點聚類映射到空間樹的分支和葉子，並且重建網格模型的空間點180，其中，空間位置 與網格模型的每個點相關聯。[0094]本發明還可用於作為多組件或多連接(MC)模型(B卩，具有多個重複組件的網格模 型)中組件的參考點、並表示該模型的頂點的聚類的點。下面兩個實施例對於這種MC模型 特別有利。在這種情況下，將重複組件的副本的各種位置與只需被編碼或解碼一次的重複 組件分開編碼/解碼。解碼過程中，重複組件被複製到它的每個解碼的位置上。例如，在機 器的3D工程模型中，可將使用多次的螺絲作為重複組件進行編碼。[0095]在一個實施例中，本發明是一種用於編碼網格模型，特別是MC網格模型的組件的 參考點的方法，其中，每個參考點代表一個組件並且使用分層樹對各點編碼，並且其中，所 述編碼包括以下步驟:定義要被編碼的點的周圍的邊界框，遞歸地劃分該邊界框，其中，每 個劃分步驟將父單元格劃分為預定義數量的子單元格(至少兩個，其中，在一個實施例中， 任何一個劃分步驟的所有子單元格具有相等的尺寸)，對於每個劃分步驟，為當前父單元格 確定點的總數以及該父單元格的所有點是否在單一的子單元格中，並如上所述至少為包括 四個或更多點的父單元格編碼指示所述確定的結果的指示符。[0096]在一個實施例中，本發明是一種用於從編碼的數據集合來解碼網格模型，特別是 MC網格模型的重複組件的參考點的方法，並且其中，所述解碼包括以下步驟:從編碼的數 據集合至少提取一個值和作為多個點的位置數據的第一數據，所述值代表點的總數並且所 述第一數據定義多個碼字，其中，每個碼字指的是將邊界框劃分為各單元格的多個遞歸劃 分之一，並且每次劃分將當前父單元格劃分為兩個或更多的子單元格，以及基於所述值和 所述第一數據來確定所述點的位置，其中，至少部分碼字包含指示當前單元格劃分步驟是否有效的指示符(一個比特)。此外，所述解碼方法包含使用重複組件替換每個點。[0097]在一個實施例中，本發明涉及一種包含多個重複相連接的組件的編碼的網格模 型，其中，所述編碼的網格模型包含至少下列內容的編碼數據:[0098]每個重複相連接的組件的實例，[0099]編碼的相連接的組件的總數，[0100]所述重複相連接的組件的多個副本的位置，所述位置被編碼為樹結構(例如， kd-樹)，以及網格模型內的邊界區域，其中，所述邊界區域是所述樹結構所指代的初始父單 元格。被編碼為樹的位置使用上述編碼。即，該編碼包括樹結構的每個節點的碼字，其中， 對於具有至少四個點的節點，如果當前父單元格的點被分發給至少兩個子單元格，所述碼 字以具有第一值的指示符開始，如果當前父單元格的點在單一的子單元格中，所述碼字以 具有不同的第二值的指示符開始，並且其中，所述碼字的剩餘比特或者表示位於預定義的 一個子單元格中的點的數量(如果指示符具有第一值)減去一，或者表示當前父單元格的子 單元格的索引，所述子單元格是包括父單元格的所有點的子單元格(如果指示符具有第二 值)。[0101]圖7示出如上面相對於圖6所描述的隨後劃分步驟的樹型表示的一部分。在該 樹的根部711，編碼對應於圖6b)的對父單元格的垂直分割。如上所述，在這種情況下第一 劃分是垂直的是一種預定義的慣例。在節點711、712中，如圖6cl)和c2)所示，編碼對所 生成的子單元格的水平分割。一個劃分步驟是無效的，使得它的一個子單元格732 (或Q3) 是空的。如上所述，不分割空的子單元格並且只隱式地對其編碼。在下一節點731-734中， 如圖6dl)和d3)所示，編碼第三階段單元格的垂直分割。該單元格對應於圖2中的正方形 Q1-Q4。後面的節點741-746對應於圖6el)-e6)，其中，再次地，一個劃分是無效的並且因此 產生空的子單元格745。可以相應地構建該樹的剩餘部分(未示出)。每條線710、720、730、 740、750指的是單元格的階段。在初始地插入點的總數後，可從線710、720、730等獲得根據 本發明的代表編碼的網格模型的代碼。[0102]一般地，第一碼字的長度(點的總數)是固定的，因為無法在解碼期間推斷出其長 度。其他碼字的長度是可變的並且可以如上所述在解碼期間計算他們的長度。此外，通常 從對父單元格的單一划分步驟所產生的所有子單元格都具有實質上相等的尺寸。[0103]注意，對點的編碼/解碼在這裡一般意味著對它們的坐標的編碼/解碼。[0104]下列示例性實施例是特別有利的:[0105]在編碼方法的一個實施例中，如果指示符具有第一值，根據η=取整(1g2 (m+1)), 碼字的剩餘比特的數量依賴於當前父單元格中點的數量，其中，η是碼字的剩餘比特的數 量，m是當前父單元格中點的數量。[0106]在一個實施例中，編碼方法還包括根據輸入點的空間坐標將輸入點聚類成一個或 多個聚類的初始步驟，並且每個點是輸入點的聚類的參考點。[0107]在編碼方法的一個實施例中，網格模型是具有多連接組件的3D網格模型，並且聚 類中的每個點代表一個組件。[0108]在編碼方法的一個實施例中，從對父單元格的單一划分步驟產生的所有子單元格 具有相等的尺寸。[0109]在編碼方法的一個實施例中，遞歸的最大數或最小單元格尺寸被定義為遞歸劃分步驟的終止條件。[0110]在用於2D的編碼方法的一個實施例中，劃分當前父單元格的遞歸劃分步驟以輪 換方式執行水平和垂直分割，並且預定義的一個子單元格不是水平分割的上部或下部子單 元格，就是垂直分割的左側或右側子單元格。[0111]在用於3D的編碼方法的一個實施例中，劃分當前父單元格的遞歸劃分步驟以輪 換方式執行水平、垂直和深度分割，其中，預定義的一個子單元格或者是水平分割的上部或 下部子單元格，或者是垂直分割的左側或右側子單元格，或者是深度分割的前部或後部子 單元格。[0112]在一個實施例中，其中，每個碼字的長度是可變的，所述解碼方法還包括根據給 定的規則計算碼字的長度的步驟。根據該規則，根據η=取整(1g2 (m+Ι))或根據n=l0g2 (m+1)，從當前父單元格中點的數量計算碼字的所述剩餘比特的數量，其中，η是碼字的剩餘 比特的數量，m是當前父單元格中點的數量。[0113]在解碼方法的一個實施例中，網格模型是包含多個重複連接組件的實例的3D網 格模型，並且每個所述點是指示一個所述實例的位置的參考點，並且該方法還包含生成重 復組件的多個實例和根據各自參考點的位置來定位每個副本的最終步驟。[0114]在解碼方法的一個實施例中，從對父單元格的單一划分步驟產生的所有子單元格 具有相等的尺寸。[0115]在解碼方法的一個實施例中，遞歸的最大數或最小單元格尺寸被定義為遞歸劃分 步驟的終止條件。[0116]在用於2D的解碼方法的一個實施例中，劃分當前父單元格的遞歸劃分步驟以輪 換方式執行水平和垂直分割，並且預定義的一個子單元格不是水平分割的上部或下部子單 元格，就是垂直分割的左側或右側子單元格。[0117]在用於3D的解碼方法的一個實施例中，劃分當前父單元格的遞歸劃分步驟以輪 換方式執行水平、垂直和深度分割，並且預定義的一個子單元格或者是水平分割的上部或 下部子單元格，或者是垂直分割的左側或右側子單元格，或者是深度分割的前部或後部子 單元格。[0118]在一個實施例中，編碼的網格模型包含多個重複相連接的組件，其中，編碼的網格 模型包含每個重複相連接的組件的至少一個實例的編碼數據，所述重複相連接的組件的多 個副本的位置，所述位置被編碼為kd_樹，以及[0119]網格模型內的邊界區域，其中，所述邊界區域是kd_樹所指代的初始父單元格，其 中，被編碼為kd_樹的位置使用包括kd_樹的每個節點的碼字的編碼，如果當前父單元格 的點被分發給至少兩個子單元格，所述碼字以具有第一值的指示符開始，如果當前父單元 格的點在單一的子單元格中，所述碼字以具有不同的第二值的指示符開始，並且其中，所述 碼字的剩餘比特或者表示位於預定義的一個子單元格中的點的數量(如果指示符具有第一 值)，或者表示當前父單元格的子單元格的索引，所述子單元格是包括父單元格的所有點的 子單元格(如果指示符具有第二值)。[0120]儘管已經通過將其應用到本發明的示例性實施例來示出、描述並指出了本發明的 基本的新穎特徵，應理解，本領域技術人員可以在不脫離本發明的精神的情況下作出所描 述的裝置和設備的在所公開的設備的形式和細節方面、以及其操作方面的各種省略、替換和變化。例如，雖然已經關於具有正方形的兩倍尺寸的矩形的邊界框公開了本發明，本領域 技術人員將認識到本文所描述的方法和設備可應用於任何矩形邊界框，即使它們的劃分導 致不是正方形的矩形。所有上述慣例可在不脫離本發明的範圍的情況下自由修改。雖然在 上述示例中，對邊界框的第一划分步驟是垂直的，它也可以是水平的。因此，修改給定數量 的水平和垂直劃分步驟的順序次序是可能的。[0121 ] 此外，可以修改示例中使用的任何隱式慣例。例如，相對於圖2b)和上述相關示例， 慣例可以是不論其祖父單元格地逐線或逐列順序處理一個階段的所有當前父單元格(例 如，QDo另一慣例可以是在一個階段的下一祖父單元格進入之前，在任何先前階段j-χ的 它們的相應祖父單元格之內(例如，在Ql之內)逐線或逐列順序處理該階段j的所有當前父 單元格(例如，sql)。此外，另一慣例可以是如在上述示例中所作出的那樣在處理的某一點 上在上述兩個慣例之間進行切換。[0122]特別地表明，以基本相同的方式來執行基本相同的功能以實現相同的結果的那些 元件的所有組合是在本發明的範圍之內的。也完全涉及和考慮從一個描述的實施例到另一 個的元件的替換。[0123]應理解，已經通過示例的方式全面地描述了本發明，並且可以作出不脫離本發明 範圍的對細節的修改。可以獨立地或以任何適當的組合的方式提供在說明書和(適用的地 方)權利要求以及附圖中公開的每個特徵。所述特徵在適當的情況下可以實現在硬體、軟 件、或兩者的組合中。[0124]權利要求中出現的標號只是為了說明，並且不應對權利要求的範圍有任何限制作用。
【權利要求】
1.一種使用分層樹來編碼網格模型的點的方法，其中，所述方法包括以下步驟:-編碼作為點的總數的值；-遞歸地劃分網格模型的點的周圍的邊界框，其中，每個劃分步驟將當前父單元格劃分為預定義數量的子單元格，並且對於每個劃分步驟執行以下步驟:-確定當前父單元格和所述當前父單元格中包含的點的總數；-確定當前父單元格是否包含至少最小數量的點；-如果當前父單元格不包含至少所述最小數量的點，編碼包含預定義的一個子單元格中的點的數量的碼字，並且，否則-確定點分布，其中，根據當前劃分步驟，確定當前父單元格的所有點是否在單一的子單元格中；並且-編碼一個碼字，其中，所述碼字以一個指示符開始，並且其中如果根據所述確定的點分布，當前父單元格的所有點並不都是在單一的子單元格中， 該指示符具有第一值並且該碼字的剩餘比特表示點的數量，該數量是預定義的一個子單元格中點的數量減去一，並且其中如果根據所述確定的點分布，當前父單元格的所有點都在單一的子單元格中，該指示符具有不同的第二值並且該碼字的剩餘比特表示標識包含父單元格的所有點的所述單一子單元格的索引。
2.根據權利要求1所述的方法，其中，如果指示符具有第一值，根據η=取整(1g2 (m+Ι))或n=log2 (m),碼字的剩餘比特的數量依賴於當前父單元格中點的數量,其中，η是碼字的剩餘比特的數量，m是當前父單元格中點的數量。
3.根據權利要求1或2所述的方法，還包括根據輸入點的空間坐標將輸入點聚類成一個或多個聚類的初始步驟，並且每個點是多個輸入點的聚類的參考點。
4.根據權利要求3所述的方法，其中，所述網格模型是具有多連接組件的3D網格模型， 並且其中，聚類的每個參考點代表一個組件。
5.一種解碼網格模型的點的方法，該方法包括以下步驟:-從編碼的數據集合提取至少第一數據和初始值，所述第一數據包含多個碼字，所述初始值指示點的總數；-基於默認數據基於從編碼的數據集合提取的邊界框數據，生成邊界框；-遞歸地將邊界框劃分為單元格，其中，每次遞歸劃分將當前父單元格劃分為兩個或更多的子單元格，並且其中，碼字為父單元格定義子單元格之一；以及 -根據所述子單元格確定所述點的位置，其中，多個碼字中的每一個包含指示該碼字的剩餘比特的含義的指示符，其中，評價該指示符，並且其中，所述碼字的剩餘比特定義-或者是位於從當前父單元格的當前劃分產生的預定義的一個子單元格中的點的數量，如果所述指示符具有第一值；-或者是指示從當前父單元格的當前劃分產生的子單元格的索引，其中，所述子單元格包含所述父單元格的所有點。
6.根據權利要求5所述的方法，其中`，每個碼字的長度是可變的，還包括根據給定的規則計算碼字的長度的步驟，其中，根據η=取整(1g2 (m+1))，從當前父單元格中點的數量計算碼字的所述剩餘比特的數量，其中，η是碼字的剩餘比特的數量，m是當前父單元格中點的數量。
7.根據權利要求5或6所述的方法，其中，所述網格模型是包含重複相連接的組件的多個實例的3D網格模型，並且其中，所述點中的每一個是指示所述實例中的一個的位置的參考點，還包括生成重複組件的多個實例和根據各自參考點的位置來定位每個副本的最終步驟。
8.根據權利要求1-7任一項所述的方法，其中，如果所述網格模型和所述邊界框是二維的，劃分當前父單元格的所述遞歸劃分步驟以輪換方式執行水平和垂直分割，或者如果所述網格模型和所述邊界框是三維的，劃分當前父單元格的所述遞歸劃分步驟以輪換方式執行水平、垂直和深度分割，並且其中，預定義的一個子單元格或者是水平分割的上部或下部子單元格，或者是垂直分割的左側或右側子單元格，或者是深度分割的前部或後部子單元格。
9.根據權利要求1-8任一項所述的方法，其中，從對父單元格的單一划分步驟所產生的所有子單元格具有相等的尺寸。
10.根據權利要求1-9任一項所述的方法，其中，遞歸的最大數量或最小單元格尺寸被定義為遞歸劃分步驟的終止條件。
11.一種包含適於在涉及權利要求1-4中的一項時執行根據權利要求1-4或8-10中的一項的使用分層樹來編碼網格模型的點的方法的處理元件的裝置。
12.—種包含適於在涉及權利要求5-7中的一項時執行根據權利要求5-7中的一項或權利要求8-10中的一項的使用分層樹來解碼網格模型的點的方法的處理元件的裝置。
13.一種在其上存儲有導致計算機在涉及權利要求1-4中的一項時執行根據權利要求 1-4或8-10中任一項的編碼網格模型的方法、或在涉及權利要求5-7中的一項時執行根據權利要求5-7中的一項或權利要求8-10中的一項的解碼網格模型的方法的可執行指令的計算機可讀介質。
14.一種包含多個重複相連接的組件的編碼的網格模型，其中，所述編碼的網格模型包含至少下列內容的編碼數據:-每個重複相連接的組件的一個實例；-編碼的相連接的組件的總數；-所述重複相連接的組件的多個副本的位置，所述位置被編碼在樹結構中，其中，所述樹結構中的節點定義當前父單元格的空間劃分；以及-邊界區域，其中，所述邊界區域是所述樹結構所指代的初始父單元格並包含所述編碼的相連接的組件的總數，並且其中，被編碼為樹結構的位置使用包括該樹結構的每個節點的碼字的編碼格式，如果當前父單元格的點被分發給至少兩個子單元格，所述碼字以具有第一值的指示符開始，否則，所述碼字以具有不同的第二值的指示符開始，並且其中，如果該指示符具有第一值，所述碼字的剩餘比特表示位於預定義的一個子單元格中的點的數量，或者如果該指示符具有第二值，所述碼字的剩餘比特表示當前父單元格的子單元格的索引，所述子單元格包括父單元格的所有點。
15.根據權利要求14所述的編碼的網格模型，其中，如果所述網格模型和所述邊界框是二維的，樹結構中的後續節點定義以輪換方式水平地和垂直地劃分當前父單元格的遞 歸空間劃分步驟，如果所述網格模型和所述邊界框是三維的，樹結構中的後續節點定義以輪換方行水平地、垂直地和深度維度地劃分當前父單元格的遞歸空間劃分步驟，並且其中，預定義的一個子單元格或者是水平劃分的上部或下部子單元格，或者是垂直劃分的左側或右側子單元格，或者是深度劃分的前部或後部子單元格。`
【文檔編號】H04W4/00GK103518387SQ201180070071
【公開日】2014年1月15日 申請日期:2011年4月12日 優先權日:2011年4月12日
【發明者】蔡康穎, 田疆, 孟維亮 申請人:湯姆遜許可公司