[發(fā)明專利]編碼和解碼每個(gè)碼元可具有三個(gè)或更多可能碼元值中的一個(gè)碼元值的碼元序列的方法和裝置

有效

• 申請?zhí)枺?/td>: 201080015657.5
• 申請日: 2010-03-30
• 公開（公告）號(hào): CN102388404A
• 公開（公告）日: 2012-03-21
• 發(fā)明（設(shè)計(jì)）人: 陳衢清;蔡康穎;滕軍;陳志波
• 申請（專利權(quán)）人: 湯姆森特許公司
• 主分類號(hào): G06T9/00
• 分類號(hào): G06T9/00;H04N7/26;H03M7/46
• 代理公司: 北京市柳沈律師事務(wù)所 11105
• 代理人: 呂曉章

技術(shù)領(lǐng)域

在編碼和解碼其中每個(gè)碼元可以具有來自三個(gè)或者更多個(gè)可能碼元值中的一個(gè)碼元值的碼元序列的技術(shù)領(lǐng)域中提出本發(fā)明。

背景技術(shù)

在表示三維(3D)對(duì)象的各種應(yīng)用中，包括游戲、工程設(shè)計(jì)、建筑預(yù)排(architectural?walkthrough)、虛擬現(xiàn)實(shí)、電子商務(wù)，以及科學(xué)可視化中，已經(jīng)廣泛地使用了3D網(wǎng)格。尤其在近年來的3D掃描儀的快速增長的情況下，這些3D網(wǎng)格的原始表示通常需要海量的數(shù)據(jù)。然而，多數(shù)應(yīng)用要求用于存儲(chǔ)和傳輸?shù)?D網(wǎng)格的緊湊的表示。

典型地，3D網(wǎng)格由三種類型的數(shù)據(jù)表示：

拓?fù)鋽?shù)據(jù)，其描述頂點(diǎn)之間的相鄰關(guān)系；它在別處也被稱為連通性數(shù)據(jù)。幾何數(shù)據(jù)，其指定頂點(diǎn)位置和屬性數(shù)據(jù)，指定諸如法向矢量、材料反射率，以及紋理坐標(biāo)之類的性質(zhì)。

拓?fù)鋽?shù)據(jù)和幾何數(shù)據(jù)可以共同地或者單獨(dú)地壓縮。通過底層拓?fù)渚幋a來確定幾何數(shù)據(jù)的編碼順序。幾何數(shù)據(jù)通常通過量化、預(yù)測和熵編碼三個(gè)主要步驟來壓縮。3D網(wǎng)格屬性數(shù)據(jù)通常通過與幾何壓縮類似的方法來壓縮。

在用以編碼3D三角形網(wǎng)格的拓?fù)鋽?shù)據(jù)的方法中，J.Rossignac在1999年1月至3月的IEEE?Transactions?on?Visualization?and?Computer?Graphics，Vol.5，No.1，pp.47-61中的“Edgebreaker：Connectivity?compression?for?triangle?meshes”中提出，邊緣分隔(Edgebreaker)是非常高效并且普遍使用的一種方法。

對(duì)于大的網(wǎng)格，邊緣分隔和熵編碼可以得出(yield)每個(gè)三角形小于1.5比特。邊緣分隔壓縮和解壓縮處理從一個(gè)三角形到相鄰三角形對(duì)網(wǎng)格執(zhí)行相同的遍歷。在每個(gè)階段，壓縮產(chǎn)生用于描述當(dāng)前三角形和已經(jīng)編碼的網(wǎng)格部分的邊界之間的拓?fù)潢P(guān)系的比特。解壓縮解碼這些比特以重構(gòu)整個(gè)拓?fù)鋱D形。通過使用邊緣分隔算法，3D三角形網(wǎng)格的所有拓?fù)鋽?shù)據(jù)是一系列的五種可能的模式碼元：″C″，″R″，″L″，″E″，和″S″。例如，邊緣分隔算法的最終輸出看上去像″CCRRRSLCRSERRELCRRRCRRRE...″。

邊緣分隔的3D網(wǎng)格的五種可能模式碼元中的三種：″L″″″E″″S″的出現(xiàn)不如其它兩種碼元″C″″R″頻繁。例如：

CRCRCRCRCLRECCRCRCRRCRLCCRRCRCRRCCRCRCCRSRCRCRCRRCRCR...

例如，在幾個(gè)3D網(wǎng)格模型，5種模式的出現(xiàn)：

表1：在不同3D模型中五種模式“CRLES”出現(xiàn)的統(tǒng)計(jì)結(jié)果

發(fā)明內(nèi)容

本發(fā)明提出一種用于移除多碼元序列(例如作為在邊緣分隔算法之后的3D網(wǎng)格模型的拓?fù)鋽?shù)據(jù)的表示)內(nèi)的統(tǒng)計(jì)冗余的方法。

首先，將一些碼元組合為新的碼元，并且然后使用某個(gè)上下文模型將新的碼元與其它碼元一起進(jìn)行編碼。如果編碼該新的碼元，則接著編碼組合的細(xì)節(jié)，其中若干上下文模型用于每個(gè)碼元在“多個(gè)串(runs)”的不同位置。

提出了一種壓縮碼元序列的方法，其中每個(gè)碼元可以具有來自三個(gè)或者更多個(gè)可能碼元值中的一個(gè)碼元值，所述方法包括以下步驟：通過未被包括在所述三個(gè)或者更多個(gè)可能碼元值中的另一碼元值來取代每個(gè)串對(duì)(run?pair)而修改碼元序列，所述每個(gè)串對(duì)包含最頻繁的碼元值的第一串碼元和第二頻繁的碼元值的第二串碼元；生成包括所有被取代的串對(duì)的二進(jìn)制序列并且壓縮編碼該二進(jìn)制序列和修改的碼元序列。

另外，提出了一種碼元序列的二進(jìn)制表示，其中每個(gè)碼元可以具有來自n個(gè)可能碼元值中的一個(gè)碼元值，n＞2，并且其中由修改的碼元序列的二進(jìn)制表示和二進(jìn)制序列的二進(jìn)制表示來表示所述碼元序列，其中修改的碼元序列的碼元可以具有來自(n-1)個(gè)可能碼元值中的一個(gè)碼元值。

而且，提出了一種承載這種比特流的存儲(chǔ)介質(zhì)。

在實(shí)施例中，應(yīng)用以下方法來壓縮編碼二進(jìn)制序列：

通過翻轉(zhuǎn)二進(jìn)制序列的比特來生成另一比特序列，其中在所述二進(jìn)制序列中，在僅僅那些被翻轉(zhuǎn)的比特之前是具有兩個(gè)可能比特值中的第一個(gè)的相應(yīng)的先前比特；并且編碼該另一比特序列。

在另一實(shí)施例中，壓縮編碼二進(jìn)制序列可以包括：生成多串1的長度的一元表示的第一序列，生成多串零的長度的一元表示的第二序列，并且比特平面(bit?plane)編碼所生成的一元表示的第一序列和第二序列。