編碼和解碼坐標內插符的關鍵字值數據的方法和裝置的製作方法

2023-05-03 02:27:21 3

專利名稱：編碼和解碼坐標內插符的關鍵字值數據的方法和裝置的製作方法
技術領域：
本發明涉及用於編碼和解碼合成圖像的裝置和方法，尤其涉及用於編碼和解碼一種坐標內插符的關鍵字值數據的裝置和方法，其中坐標內插符使用在基於關鍵幀的圖形動畫中的包括x、y、z分量的頂點坐標表示對象的位置。
背景技術：
三維(3D)動畫技術已經廣泛地應用在3D計算機遊戲或虛擬實境計算機應用中。虛擬實境模型語言(VRML)是這種3D動畫技術的典型實例。
國際多媒體標準，例如用於場景(BIFS)和虛擬實境模型語言(VRML)的MPEG-4二進位格式，使用內插符節點支持基於關鍵幀的3D動畫。在MPEG-4BIFS和VRML中，有各種類型的內插符，其包括標量內插符、位置內插符、坐標內插符、定向內插符、法線(normal line)內插符、和色彩內插符，這些內插符以及其功能和特性在表1中示出。
表1


在表1所示的內插符中，坐標內插符被用於表示在構成基於關鍵幀的動畫中的3D對象的每一頂點位置上的信息，並且包括關鍵字和關鍵字值欄位。關鍵欄位使用範圍在-∞和∞之間的不連續數字表示在時間軸上的每一關鍵幀的位置。每一個關鍵字值欄位規定了在由每一關鍵字表示的在確定瞬時的構成3D對象的每一個頂點位置上的信息，並且包括三個分量x、y和z。每一個關鍵字值欄位包括與關鍵欄位一樣多的關鍵字值。在這種基於關鍵幀的動畫中，預定的關鍵幀定位在時間軸的任意位置，並且由線性內插填充在關鍵幀之間的動畫數據。
由於MPEG-4 BIFS和VRML中採用線性內插，所以要求相當量的關鍵字數據和關鍵字值數據來使用線性內插符把動畫表現得儘可能地自然和平滑。此外，為了存儲和發送這種自然和平滑的動畫，需要相當大容量的存儲器和大量的時間。因此，最好是選擇壓縮內插符，以便更容易存儲和發送內插符。
在已經應用在MPEG-4 BIFS中用於編碼和解碼內插符節點的方法之一的預測MF欄位編碼(PMFC)中，使用量化器、差分脈碼調製(DPCM)操作器、和熵編碼器編碼坐標內插符的關鍵字值數據，如圖1所示。參考圖1，量化器和DPCM操作器消除關鍵字值數據的冗餘，DPCM操作器把其操作的結果輸出到熵編碼器。然而，PMFC在對關鍵字值數據進行編碼中並不是充分有效的，因為其只熵編碼從一般DPCM操作獲得的差分數據，並且僅考慮在動畫中構成3D對象頂點之間的空間相關性而不考慮在這種頂點之間的時間相關性，在基於關鍵幀的動畫中，這種時間相關性是很重要的。

發明內容
為解決上述和其它問題，本發明的一個方面提供一種用於編碼坐標內插符的關鍵字值數據的方法和裝置，在其中考慮動畫中的3D對象頂點之間的時間相關性以及空間相關性。
本發明的另一方面提供一種用於解碼編碼的坐標內插符的關鍵字值數據的方法和裝置，在其中考慮動畫中的3D對象頂點之間的時間相關性以及空間相關性。
本發明的另一方面提供一種比特數據流，在其中考慮動畫中的3D對象頂點之間的時間相關性以及空間相關性編碼坐標內插符的關鍵字值數據。
本發明的另一方面提供了一種用於DPCM操作的方法和裝置，該操作被使用在根據本發明的用於編碼坐標內插符的關鍵字值數據的方法和裝置中，並且考慮動畫中的3D對象的頂點之間的時間相關性以及其中的空間相關性對3D對象的坐標數據執行DPCM操作。
本發明的另一方面提供了一種用於反DPCM操作的方法和裝置，其解碼由根據本發明的用於DPCM操作的方法和裝置產生的差分數據。
因此，為了實現本發明的上述和其它方面，其中提供了用於編碼坐標內插符的關鍵字值數據的裝置，其中坐標內插符使用包括x、y和z分量的每一個頂點的坐標表示對象的每一頂點的位置。裝置包括量化器，其以預定的量化比特量化輸入其中的坐標內插符，DPCM處理器，其對量化的坐標內插符的每一頂點的每一分量執行預定模式的DPCM操作，並且因此產生根據每一頂點的坐標的時間變化的差分數據以及根據每一個頂點的坐標的空間變化的差分數據，字典編碼器，其產生表示每一頂點的每一分量的差分數據的符號和已經對差分數據執行的DPCM操作的模式以及表示符號的位置的位置索引，和熵編碼器，熵編碼符號和位置索引。
為了實現本發明的上述和其它方面，其中提供了用於解碼比特數據流的裝置，其中比特數據流中編碼了使用包括x、y和z分量的每一個頂點的坐標表示對象的每一頂點的位置的坐標內插符的關鍵字值數據。裝置包括熵解碼器，其通過熵解碼輸入的比特數據流而產生將要被字典解碼的數據，其中包括差分數據的符號、表示符號位置的位置索引和DPCM操作模式；字典解碼器，其使用將要被字典解碼的數據產生差分數據；反DPCM處理器，其通過恢復在DPCM操作模式之後從字典解碼器輸入的關鍵幀之間的差分數據和頂點之間的差分數據而產生量化數據；以及反量化器，通過反量化量化的數據而產生恢復的關鍵字值數據。
使用在用於解碼比特數據流的裝置中的反DPCM處理器最好包括反時間DPCM操作器，其對關鍵幀中的頂點和另一關鍵幀中的頂點之間的差分數據執行反DPCM操作；反空間DPCM操作器，其對在同一關鍵幀的頂點和其對應參考頂點之間的差分數據執行反DPCM操作；以及反DPCM模式選擇器，其根據DPCM操作模式而把差分數據輸出到反時間DPCM操作器或反空間DPCM操作器。
為了實現本發明的上述和其它方面，其中提供了用於編碼坐標內插符的關鍵字值數據的方法，其中坐標內插符使用包括x、y和z分量的每一個頂點的坐標表示對象的每一頂點的位置。方法包括步驟(a)以預定的量化比特量化坐標內插符的關鍵字值數據，(b)對量化坐標內插符的每一頂點的每一分量執行預定模式的DPCM操作，並且因此產生基於每一個頂點的坐標的時間變化的差分數據和基於每一個頂點的坐標的空間變化的差分數據，(c)產生表示每一頂點的每一分量的差分數據和已經對差分數據執行的DPCM操作的模式的符號，並且產生表示符號位置的位置索引，以及(d)熵編碼符號和位置索引。
為了實現本發明的上述和其它方面，提供了一種方法，用於產生構成隨時間運動的對象的頂點的量化坐標數據之間的差分數據。該方法包括執行時間DPCM操作，其中產生根據時間的推移而改變的每一頂點的坐標數據之間的差分數據；執行空間DPCM操作，其中產生在預定時刻的每一頂點和對應於頂點的參考頂點之間的差分數據；並且輸出時間DPCM的差分數據和空間DPCM的差分數據之間的較小值。
為了實現本發明的上述和其它方面，提供了用於解碼比特數據流的方法，比特數據流中的使用包括x、y和z分量的每一個頂點的坐標表示對象的每一個頂點位置的坐標內插符的關鍵字值數據被編碼。該方法包括(a)通過熵解碼輸入比特數據流而產生將要被字典解碼的數據，其中包括差分數據的符號、表示符號的位置的位置索引和DPCM操作模式；(b)通過對差分數據的符號和位置索引執行字典解碼操作，使用將要被字典解碼的數據產生差分數據；(c)按照DPCM操作模式，通過恢復關鍵幀之間的差分數據和頂點之間的差分數據而產生量化的數據；和(d)通過反量化量化的數據而產生恢復的關鍵字值數據。
為了實現本發明的上述和其它方面，提供一種方法，用於通過對頂點的坐標數據之間的差分數據執行預定的反DPCM操作而產生構成根據時間的推移改變的對象的頂點量化坐標數據。該方法包括(a)根據包括在差分數據中的DPCM操作模式，選擇將要對差分數據執行的反DPCM操作；和(b)執行選擇的反DPCM操作。其中，選擇的反DPCM操作包括反時間DPCM操作，其中對根據時間的推移改變的每一頂點的差分數據執行反DPCM操作；以及反空間DPCM操作，其中對在預定時刻的每一個頂點和對應於頂點的參考頂點之間差分數據執行反DPCM操作。


通過下面結合示例性地示出一例的附圖進行的描述，本發明的上述和其他目的和特點將會變得更加清楚，其中圖1是用於編碼坐標內插符的關鍵字值數據的常規裝置的框圖；圖2A是根據本發明優選實施例的用於編碼坐標內插符的關鍵字值數據的裝置的框圖，而圖2B是根據本發明優選實施例的用於編碼坐標內插符的關鍵字值數據的方法的流程圖；圖3A是根據本發明優選實施例的DPCM處理器的框圖，而圖3B是字典編碼器的框圖；圖4A是根據本發明的優選實施例的量化操作的流程圖，圖4B是DPCM操作的流程圖，圖4C是字典編碼的流程圖，而圖4D是熵編碼的流程圖；圖5A至5C分別是說明根據本發明的量化關鍵字值數據、DPCM的關鍵字值數據和循環量化的關鍵字值數據的示意圖；圖6A是說明根據本發明的優選實施例的DPCM模式編碼的示意圖，圖6B是說明出現模式編碼的示意圖，而圖6C是說明增量模式編碼的示意圖；圖7A是根據本發明優選實施例的用於解碼坐標內插符的關鍵字值數據的裝置的框圖，而圖7B是根據本發明優選實施例的用於解碼坐標內插符的關鍵字值數據的方法的流程圖；圖8A是根據本發明優選實施例的字典解碼器的框圖，而圖8B是反DPCM處理器的框圖；圖9A是根據本發明優選實施例的字典解碼的流程圖，而圖9B是反DPCM操作的流程圖；圖10是說明使用在坐標內插符中的頂點以及每一個頂點的分量的數據的比特數據流的示意圖；圖11A是說明DPCM模式解碼的示意圖，圖11B是說明出現模式解碼的示意圖，而圖11C是說明增量模式解碼的示意圖；圖12至18是說明比特數據流語法的實例的示意圖，其中實現在根據本發明優選實施例進行的解碼過程中從比特數據流讀出比特的次序；圖19是說明程序代碼實例的示意圖，由此實現用於解碼關鍵字值數據的操作；圖20A和20B是用於把根據本發明的用於編碼和解碼坐標內插符的關鍵字值數據的方法的性能與用於編碼和解碼坐標內插符的關鍵字值數據的常規方法的性能相比較的示意圖；及圖21A是根據本發明優選實施例的DPCM操作器的框圖，而圖21B是根據本發明優選實施例的反DPCM操作器的框圖。
具體實施例方式
在下文中，將參照附圖更詳細地描述根據本發明優選實施例的用於編碼坐標內插符的關鍵字值數據的裝置。
圖2A是根據本發明優選實施例的用於編碼坐標內插符的關鍵字值數據的裝置的框圖，而圖2B是根據本發明優選實施例的用於編碼坐標內插符的關鍵字值數據的方法的流程圖。
參考圖2A，用於編碼坐標內插符的關鍵字值數據的裝置包括量化器300，其以預定的量化比特量化表示坐標內插符的關鍵字值數據的每一頂點的每一分量(component)的數據，DPCM處理器310，其對每一頂點的每一個分量的量化數據執行預定的DPCM操作，字典編碼器340，其把差分數據轉換成符號和位置索引，以及熵編碼器350，其熵編碼輸入其中的差分數據的符號和位置索引。
下面參照圖2B描述用於編碼坐標內插符的關鍵字值數據的方法。
參考圖2B，步驟S400中以N×M矩陣的形式把坐標內插符的關鍵字值數據輸入到量化器300。輸入的坐標內插符的關鍵字值數據的實例在下列表中示出。
表2


在表2中，N表示關鍵字數據(關鍵幀)的數目，M表示每一關鍵幀中的頂點的數量。
根據本發明用於編碼坐標內插符的關鍵字值數據的裝置以兩種不同模式操作來編碼坐標內插符的關鍵字值數據。模式之一是頂點模式，而另外一個模式是轉置模式。表2中，示出將以頂點模式在量化器300中量化的關鍵字值數據的結構。在量化表2所示的輸入關鍵字值數據之前，根據本發明的用於編碼坐標內插符的關鍵字值數據的裝置把輸入的關鍵字值數據轉置成MHN矩陣。在解碼關鍵字值數據過程中反量化轉置矩陣，並且把解碼的關鍵字值數據轉換成NHM矩陣，使得能夠恢復與輸入關鍵字值數據一樣的關鍵字值數據。
參考圖2B，在步驟S410中，量化器300檢查從外部輸入的關鍵字值數據的編碼方式是否為轉置模式。如果輸入的關鍵字值數據的編碼模式是轉置模式，則輸入的關鍵字值數據的NHM矩陣在步驟S420中被轉置成MHN矩陣。
其後，量化器300以預定的量化比特量化輸入其中的關鍵字值數據矩陣中的每一個分量的數據，並且在步驟S430把每一個分量的量化的關鍵字值數據輸出到DPCM處理器310。在同一步驟中，量化器300把在每一個分量的輸入的關鍵字值數據當中的最小值和在分量的數據範圍當中的最大範圍轉換成十進位數字，並且把十進位數字輸出到關鍵字值標題(header)編碼器370。
在步驟S440中，DPCM處理器310對輸入其中的量化的關鍵字值數據執行時間DPCM操作、空間DPCM操作和空間-時間DPCM操作，對三個不同的DPCM操作的結果，即對從三個DPCM操作獲得的每一差分數據執行循環量化操作，並且把在它們當中的具有最低熵值的差分數據輸出到字典編碼器340。
字典編碼器340產生並且輸出對應於從DPCM處理器310輸入的差分數據的字典符號Si，j和位置索引Ii，j。具體地說，字典編碼器340產生表明已經對輸入差分數據執行的DPCM操作的模式的字典符號和位置索引，把輸入的差分數據轉換成對應於輸入差分數據的值的符號或符號標誌，和表示符號的位置的位置索引，並且把符號和位置索引輸出到熵編碼器350。
在步驟S480中，熵編碼器350通過熵編碼從字典編碼器340輸入的符號和位置索引而產生比特數據流。
隨後，參照圖3A至6C更詳細地描述步驟S400至S480。
參考圖4A，在步驟S432中，量化器300選擇在每一個分量數據當中的最大值和最小值。
量化器300使用在步驟S432中選擇的最大和最小值計算分量的數據範圍，並且在步驟S434中確定在分量的數據範圍當中的最大範圍。
量化器300使用在每一個分量的數據當中的最小值和在分量的所有的數據範圍當中的最大範圍量化每一個分量的關鍵字值數據，其以下列方程式示出。
V~i,j,x=floor(Vi,j,x-fMin_XfMax(2nKVQBit-1)+0.5)(1)]]>V~i,j,y=floor(Vi,j,y-fMin_YfMax(2nKVQBit-1)+0.5)]]>V~i,j,z=floor(Vi,j,z-fMin_ZfMax(2nKVQBit-1)+0.5)]]>方程式(1)中，i表示關鍵字數據，j表示頂點，而nKVQBit表示量化比特大小。此外，fMin_X、fMin_Y、fMin_Z表示在每一個分量的數據中的最小值，而fMax表示在分量數據範圍中的最大範圍。
量化器300把每一分量的量化關鍵字值數據輸出到DPCM處理器310，把fMin_X、fMin_Y、fMin_Z和fMax變換成十進位數字，並且把十進位數字輸出到關鍵字值標題編碼器370。
計算機把浮點數字存儲為32比特的二進位數字。為了降低用於編碼所需要的比特的數量，量化器300在十進位系統中把fMin_X、fMin_Y。fMin_Z和fMax轉換成其各自的尾數和指數，並且此處理由於下面方程式表示。
例如，浮點數12.34能夠通過計算機轉換成下面所示的二進位數。
010001010111000010100011100000101 2 31符號2二進位中的尾數3二進位中的指數二進位數能夠遵循方程式(2)轉換成隨後所示的十進位數。
0123421 231符號2十進位中的尾數3十進位中的指數為了把十進位中的尾數和指數包括在比特數據流中，量化器300必須計算為了表示尾數和指數所要求的比特數目。具有在-38和38之間的值的指數因此能夠使用7比特連同符號一起表示。表示尾數而需要的比特的數量取決於位數。尾數的值和表示尾數而需要的比特的數量由下表列出。
表3

量化器300把已經遵循方程式(2)和表3轉換的在每一個分量的數據中的最小值fMin_X、fMin_Y和fMin_Z以及在分量的數據範圍中的最大範圍fMax輸出到關鍵字值標題編碼器370。
下面參照圖3A和4B描述根據本發明的DPCM處理器和DPCM操作。
圖3A是根據本發明的DPCM處理器310的框圖。參考圖3A，DPCM處理器310包括DPCM操作器320，其對從量化器300輸入的每一分量的數據執行時間DPCM操作、空間DPCM操作和空間-時間DPCM操作，循環量化器330，其降低從DPCM操作器320輸入的差分數據的範圍，以及DPCM模式選擇器335，其選擇從循環量化器330輸入的差分數據中的一個。DPCM操作器320包括時間DPCM操作器321，其對每一個分量的量化數據執行時間DPCM操作，空間DPCM操作器323，其對每一個分量的量化數據執行空間DPCM操作，以及空間-時間DPCM操作器325，對每一個分量的量化數據執行空間-時間DPCM操作。
圖4B是根據本發明優選實施例的DPCM操作的流程圖。參考圖4B，在步驟S442中，每一個分量的量化數據從量化器300輸入到時間DPCM操作器321、空間DPCM操作器323、和空間-時間DPCM操作器325，然後在各自的操作器321、323以及325中對每一個分量的量化數據執行時間DPCM操作、空間DPCM操以及空間-時間DPCM操作。
時間DPCM操作器321計算在當前關鍵幀中的頂點的分量數據和在先前關鍵幀中的頂點的分量數據之間的差值。時間DPCM操作由下面方程式表示。
Di,j=V~i,j-V~i-1,j(3)]]>方程式(3)中，i表示關鍵字數據，j表示頂點的位置索引。
空間DPCM操作器323計算在同關鍵幀中的頂點之間的差值。具體地說，空間DPCM操作器323使用下面方程式計算先前頂點的熵，在當前頂點受到空間DPCM操作之前已經對先前頂點執行了空間DPCM操作。
Entropy(P)=-i=0N-1Pilog2Pi(4)]]>在方程式(4)中，Pi表示某符號在頂點產生的概率，並且等於Fi/N，其中Fi表示符號被產生了多少次，而N表示關鍵字數據的數量。
空間DPCM操作器323把在頂點中的具有最低熵的頂點確定為參考頂點，並且計算在當前受到空間DPCM操作的頂點的數據和參考頂點的數據之間差分數據。空間操作由下面方程式表示。
Di,j=V~i,j-V~i,Ref(5)]]>空間-時間DPCM操作器325對當前關鍵幀的頂點執行空間DPCM操作，使用在先前關鍵幀的頂點中的頂點作為參考頂點對先前關鍵幀的頂點執行空間DPCM操作，其中其對應於的當前關鍵幀的參考頂點，並且計算在對應於當前關鍵幀的頂點的差分數據和對應於先前關鍵幀的頂點的差分數據之間的差分數據。換句話說，空間-時間DPCM操作器325對空間DPCM操作的結果執行時間DPCM操作。空間-時間DPCM操作由下面方程式表示。
Di,j=V~i,j-{V~i-1,j+(V~i,Ref-V~i-1,Ref)}(6)]]>在空間DPCM操作和空間-時間DPCM操作過程中，如果 或{V~i-1,j+(V~i,Ref-V~i-1,Ref)}]]>小於在每一分量的量化數據中的最小值，則最小值被用於空間DPCM操作和空間-時間DPCM操作。另一方面，如果 或{V~i-1,j+(V~i,Ref-V~i-1,Ref)}]]>大於在每一分量的量化數據中的最大值，則最大值被用於空間DPCM操作和空間-時間DPCM操作。
在步驟S444中，DPCM操作器320把計算的差分數據輸出到循環量化器330，並且循環量化器330對時間DPCM的差分數據、空間DPCM差分數據和空間-時間DPCM差分數據執行循環量化操作，並且把循環量化的結果輸出到DPCM模式選擇器335。
圖5A是量化器300的輸出實例的曲線圖，而圖5B是對圖5A中所示的量化數據執行DPCM操作的結果的曲線圖。如圖5B所示，通過執行對量化數據的DPCM操作，將要被編碼的數據範圍能夠增加為其原數據範圍的兩倍。循環量化的目的是在保持量化值的數據範圍的同時執行DPCM操作。
在本發明中，假設在DPCM的差分數據中的最大值被循環連接到在DPCM的差分數據中的最小值而執行循環量化。如果對兩個連續量化數據執行的線性DPCM操作的結果大於在從DPCM操作器320輸出的DPCM差分數據中的最大值的一半，則從線性DPCM的結果中減去從DPCM操作器320輸出的DPCM差分數據的最大範圍值，以便產生具有較小絕對值的值。另一方面，如果線性DPCM的結果小於最大範圍中的最小值的一半，則把最大範圍值加到線性DPCM的結果，以便產生具有較小絕對值的值。
通過下面的方程式表示循環量化器330的操作。
CircularQuanti zation(Xi)…(7)X′i＝Xi-(nQMax-nQMin+1) (if Xi≥0)X′i＝Xi+(nQMax-nQMin+1) (otherwise)X~i=min(|Xi|,|Xi|)]]>在方程式(7)中，nQMax表示在DPCM的差分數據中的最大值，而nQMin表示在DPCM的差分數據中的最小值。圖5C示出對圖5B所示的DPCM的差分數據執行循環量化的結果。
循環量化器330把循環量化的差分數據輸出到DPCM模式選擇器335。
在步驟S446中，DPCM模式選擇器335遵循方程式(4)計算從時間DPCM操作、空間DPCM操作和空間-時間DPCM操作獲得的每一DPCM差分數據的熵。
隨後，DPCM模式選擇器335在步驟S448中選擇在時間DPCM操作、空間DPCM操作、空間-時間DPCM操作的結果中具有最低熵的DPCM差分數據作為每一頂點的DPCM操作模式，並且把對應於選擇的DPCM模式的DPCM差分數據和關於DPCM模式的信息輸出到字典編碼器340。
隨後，參照圖3B和4C描述字典編碼器340和其操作。
圖3B是根據本發明的字典編碼器340的框圖。參考圖3B，字典編碼器340包括DPCM模式編碼器342，其編碼已經對輸入其中的每一個頂點的每一分量的數據執行的DPCM的模式，出現模式編碼器346，其產生表示每一頂點的每一分量的差分數據的值的符號和表示符號的位置的位置索引，增量模式編碼器348，其產生對應於符號和表示符號位置的位置索引的符號標誌，以及表格大小計算器344，其計算用於表示每一頂點的每一分量的差分數據的符號表格以及符號標誌表格的大小，並且把從DPCM模式編碼器342輸入的差分數據輸出到出現模式編碼器346或增量模式編碼器348。
字典編碼器340檢測每一頂點的每一分量的差分數據的量化選擇標誌是否為1，如果是，則執行將在下面描述的後續處理。另一方面，如果某頂點的差分數據的量化選擇標誌是0，其意味著頂點所有關鍵幀中具有相同的量化值，則字典編碼器340將省略字典編碼處理，並且把量化值Qmin編碼成關鍵字值標題。
圖4C是根據本發明的字典編碼處理的流程圖。參考圖4C，在步驟S462中，在DPCM處理器310中已經產生的每一頂點的每一分量的差分數據被輸入到DPCM模式編碼器342中，然後DPCM模式編碼器342產生表示已經對每一頂點的每一分量的數據執行的DPCM操作模式的符號，以及表示符號的位置的位置索引。
圖6A是說明根據本發明的DPCM模式在編碼器342中執行的編碼DPCM模式的方法的示意圖。參考圖6A，DPCM模式編碼器342預先製備表格，其中示出每一頂點的每一分量的DPCM模式和其分別的符號，如圖表4所示。表4示出DPCM操作以及其對應符號的組合。表4中，時間DPCM操作、空間DPCM操作和空間-時間DPCM操作分別表示為T、S和T+S。
表4

每一頂點包括三個分量x、y和z，並且相應的DPCM操作的組合的數量是27。
如圖6A所示，根據差分數據已經通過的DPCM操作，每一個頂點的差分數據對應於表4示出的符號中的一個。DPCM模式編碼器342使得頂點的DPCM模式對應於表4中示出的其各自的符號，並且設置表示符號存在於各自的頂點差分數據中的標誌。
DPCM模式編碼器342把對應於頂點的DPCM模式的符號排列在列中，並且以從用於具有較小幅值的符號的位置索引到用於具有最大幅值的符號的位置索引的次序產生用於符號的位置索引。
如圖6A所示，對應於頂點差分數據的DPCM模式的符號的數組是(4，1，5，1，4，5)。在符號當中，1是最小的符號，並且對應於(T，T，S)。DPCM模式編碼器342產生用於符號1的位置索引，使得符號的數組中出現1的位置由1表示。因此，位置索引是(0，1，0，1，0，0)。
隨後，DPCM模式編碼器342產生用於次最小符號4的位置索引，其對應於DPCM模式(T，S，S)，使得其中4的位置由1表示。在用於符號4的位置索引的產生中，不計算符號1的位置。因此，用於符號4的位置索引是(1，0，1，0)。以同樣方式，DPCM模式編碼器342產生用於符號5的位置索引，其對應於(T，S，T+S)。用於符號5的位置索引是(1，1)。
隨後，DPCM模式編碼器342把標誌和位置索引輸出到表格大小計算器344。
再一次參考圖3B和4C，表格大小計算器344計算用於編碼在出現模式中的輸入的差分數據的符號表的大小(A)，以及用於編碼在遞增模式中的輸入的差分數據的符號標誌的大小(B)，其對應於步驟S464中在預先設置的符號表中的符號。
在步驟S446中，表格大小計算器344把使用在出現模式編碼器346中的符號表的大小A＝S*(AQP+1)(其中S表示差分數據中包括的符號的數量而AQP表示用於表示符號的比特的大小)與對應各自符號的符號標誌的大小B＝2AQP+1-1(其中AQP表示用於表示符號的比特的大小)相比較。
如果A小於B，則表格大小計算器344把每一個頂點的差分數據輸出到出現模式編碼器346，如果B小於A，則把差分數據輸出到增量模式編碼器348。
下面參照圖6B描述出現模式編碼器346的操作。
在步驟S468中，出現模式編碼器346產生對應於每一頂點的輸入差分數據的值的符號，以及表示其各自符號的位置的位置索引。
參考圖6B，當頂點的輸入差分數據是(3，7，3，7，-4，7，3，-4，3，7，-4，-4)，時，在步驟S468中出現模式編碼器346製備表格，其中對應於每一頂點的差分數據的差分值的符號3，7，和-4被順序地寫入一行。
出現模式編碼器346編碼符號數組中的第一個符號3並且產生針對符號3的位置索引，以使3處在而位置由1表示而其它位置由0表示。針對符號3的位置索引是(0 1 0 0 0 1 0 1 0 0 0)。
隨後，出現模式編碼器346產生用於下符號7的位置索引。如圖6B所示，在產生用於下符號的位置索引的過程中，前個符號的位置不被再次計算。因此，針對符號7的位置索引是(1 0 1 0 1 0 0)。
在出現模式編碼器346中，僅考慮尚未編碼的符號位置產生用於符號的全部位置索引，因此用於符號-4的位置索引是(1 1 1)。
在圖6B中，標誌bSoleKV被設置為0。標誌bSoleKV表示在差分數據的符號數組中符號是否僅出現一次。如果符號僅出現一次並且因此其位置索引僅包括0，則用於對應符號的bSoleBK被設置為1，並且對應符號的位置索引不被編碼。出現模式編碼器346把輸入差分數據的符號、符號的位置索引以及bSoleKV輸出到用於熵編碼差分數據的熵編碼器350。
隨後參照圖6C描述根據本發明的增量模式編碼器348的操作。
在步驟S469，增量模式編碼器348產生表示包含在預定符號表中的符號是否存在於輸入的差分數據中的符號標誌以及用於符號的位置索引。
增量模式編碼器348預先產生用於被期望存在於輸入差分數據中的符號的表格。在表格中，以從具有最低絕對值的符號到具有最大絕對值的符號的次序把符號排列在列中，並且在具有相同的絕對值的兩個符號之間，具有正值的符號被放置在比另一符號更高的行中。因此，符號寫入表格中的次序是0，1，-1，2，-2，3，-3，....。對應於符號表中的符號的符號標誌的大小是2AQP+1-1。例如，如果AQP是2，則能夠由符號標誌表示的符號的數量是7。如果對應於符號的值存在於差分數據中，則符號標誌設置為1。僅針對其符號標誌被設置為1的符號產生位置索引。
參考圖6C，如果輸入到增量模式編碼器348的差分數據是(-1，-3，-1，-3，2，-3，-1，2，-1，-3，2，2)，則存在於差分數據中的符號是(-1，2，-3)，並且因此確定符號標誌為(0，0，1，1，0，0，1)。
增量模式編碼器348產生用於符號的位置索引，其中符號在符號表中的定位在比其它符號高的行中。如圖6C所示，增量模式編碼器348設置符號-1所在的位置，其中其在符號表中的差分數據中存在的符號中排位最高，並且以0設置其它位置，使得用於符號-1的位置索引是(1 0 1 0 0 0 1 0 1 0 0 0)。
隨後，增量模式編碼器348產生用於符號2的位置索引(0 0 1 0 1 0 1 1)而不考慮已經編碼的符號-1的位置。最後，增量模式編碼器348產生用於符號3的位置索引(1 1 1 1)而不考慮已經編碼的符號-1和符號2的位置。增量模式編碼器348把用於其各自符號的符號標誌和位置索引輸出到熵編碼器350。
由出現模式編碼器346和增量模式編碼器348產生的全部位置索引具有稱為nTrueOne的標誌，其表示原來的位置索引是否已經反。具體地說，如果nTrueOne被設置為0，則認為位置索引是通過反其原來位置索引而獲得的。在位置索引包括許多1的情況中，有可能通過反位置索引而增強算法編碼效率，以便增加0的數量。
隨後參照圖4描述熵編碼器350的操作。
根據本發明的熵編碼器350熵編碼從增量模式編碼器348輸入的表示差分數據的符號的符號標誌和用於符號的位置索引，並且使用函數enodeSignedQuasiAAC熵編碼從出現模式編碼器346輸入的差分數據的符號和其各自的位置索引。
在encodeSignedQuasiAAC中，使用涉及輸入值和其符號的內容產生一種自適應算法編碼的比特數據流。具體地說，在encodeSignedQuasiAAC中，不為0的第一比特被編碼，隨後編碼其符號，並且使用零內容編碼其它比特。
圖4D是使用encodeSignedQuasiAAC編碼符號的處理的流程圖。
在步驟S481中，熵編碼器350接收將要被編碼的差分數據的符號nValue和其比特大小QBit。
在步驟S482，熵編碼器350從nQBit減去2，並且存儲相減的結果作為可變i。
在步驟S483中，熵編碼器350把符號nValue的絕對值存儲作為變量val，並且對val執行次數為i的右移位(SR)操作。熵編碼器350對1和SR操作的結果執行邏輯″與″操作，並且把邏輯″與″操作的結果存儲作為變量比特。
在使用encodeSignedQuasiAAC編碼符號的處理的第一周期中，檢測除了符號位以外的將要被熵編碼的輸入值中的第一比特，並且在隨後的周期中逐個讀出其它比特。
在步驟S484中熵編碼器350檢測val是否大於1。如果val大於1，則在步驟S485中在零上下文(context)之下使用函數qf_encode編碼′比特′的值。另一方面，如果val不是大於1，則在步驟S486中在第i上下文中使用函數qf_encode編碼′比特′的值。
當val不大於1時，在步驟S487中熵編碼器350再一次檢驗val是否為1。如果val是1，則在步驟S488中設置nValue的符號，並且在步驟S489中根據其符號和符號上下文編碼nValue。
當完成針對一個比特的編碼處理時，熵編碼器350在步驟S490中把i減1，隨後在步驟S491中檢測i的當前值是否小於0。通過重複地執行S483至S490，熵編碼器350熵編碼輸入值，直到i小於0為止。
因此，按照分配到第一比特的上下文，熵編碼器350編碼輸入值不是0的第一比特，並且編碼按照零上下文的其它比特。
隨後參照圖2A描述在關鍵字值標題編碼器370中的將要被編碼成關鍵字值標題的信息。
關鍵字值標題編碼器370接收輸入的坐標協調程序並且編碼數據模式、每一關鍵幀中的頂點的數目、用於頂點數目的所需要的比特數、以及每一浮點數的有效位的最大數目。
關鍵字值標題編碼器370編碼量化比特數、每一頂點的每一分量的關鍵字值數據中的最小值和每一頂點的每一分量的數據範圍中的最大數據範圍、以及每一頂點的每一分量的量化數據中的最大和最小值。
關鍵字值標題編碼器370從DPCM處理器310接收已經對每一頂點的每一分量的數據執行的DPCM操作的模式，從字典編碼器340接收字典編碼模式，並且編碼DPCM操作模式和字典編碼方式。
隨後參照圖7A和7B描述根據本發明的用於解碼編碼的坐標內插符的裝置和方法。
圖7A是根據本發明優選實施例的用於解碼編碼的坐標內插符的裝置的框圖，而圖7B是根據本發明優選實施例的用於解碼編碼的坐標內插符的方法的流程圖。
參考圖7A，根據本發明的用於解碼編碼的坐標內插符的裝置包括熵解碼器800，其熵解碼輸入的比特數據流並且因此產生將要被字典解碼的數據，其中數據包括DPCM差分數據的符號、符號標誌、用於符號的位置索引和DPCM操作模式；字典解碼器810，根據將要被字典編碼的數據的符號和其位置索引產生差分數據；反DPCM處理器830，根據DPCM操作模式而對差分數據執行預定的反DPCM操作來產生量化數據；反量化器850，通過反量化量化數據而產生恢復的關鍵字值數據；以及關鍵字值標題解碼器870，從輸入的比特數據流解碼用於解碼坐標內插符所需要的信息，並且把信息輸出到字典解碼器810、反DPCM處理器830和反量化器850。
下面參照圖7B描述根據本發明的用於解碼編碼的坐標內插符的方法。
在步驟S910中，其中的坐標內插符被編碼的比特數據流被輸入到熵解碼器800，然後在步驟S920中，熵解碼器800解碼輸入的比特數據流。如果輸入的比特數據流已經以出現模式編碼，則熵解碼器800把每一頂點的符號和其位置索引輸出到字典解碼器810。另一方面，如果輸入的比特數據流已經以增量模式編碼，則熵解碼器800把表示符號的存在的符號標誌和用於符號的位置索引輸出到字典解碼器810。
在步驟S930中，根據輸入的字典編碼模式，字典解碼器810通過解碼從熵解碼器800以出現模式輸入的符號和位置索引或通過解碼從熵解碼器800以增量模式輸入的符號標誌和位置索引而產生差分數據，並且把產生的差分數據輸出到反DPCM處理器830。
根據輸入差分數據的解碼的DPCM工作模式，反DPCM處理器830在步驟S940中通過對從字典解碼器810輸入的差分數據執行反時間DPCM操作、反空間DPCM操作以及反空間-時間DPCM操作中的一個而產生量化的關鍵字值數據，並且把量化的關鍵字值數據輸出到反量化器850。
在步驟S950中，反量化器850使用從關鍵字值標題解碼器870輸入的每一個分量的數據中的最小值和最大數據範圍而反量化從反DPCM處理器830輸入的量化的關鍵字值數據。
在步驟S960中，反量化器850檢查反量化的關鍵字值數據矩陣是否已經在編碼處理過程中轉換成轉置矩陣，並且如果反量化的關鍵字值數據的矩陣已經轉置，則在步驟S965中反地變換轉置矩陣。
在步驟S970中，反量化器850輸出恢復的坐標內插符的關鍵字值數據。
隨後，參照圖8A至9B更詳細地描述用於解碼編碼的坐標內插符的裝置和方法。
熵解碼器800首先從輸入比特數據流解碼表示DPCM模式的比特數據流，然後解碼包括bSelFlag、nKVACodingBit、nQMin、和nQMax的數組。
在編碼處理中，首先分別把bSelFlag和nKVACodingBit設置為1和0。如果bSelFlag被解碼成1，則熵解碼器800解碼nKVACodingBit、nQMin和nQMax。另一方面，如果bSelFlag被解碼成0，則熵解碼器800隻解碼nQMin。
在解碼數據bSelFlag、nKVACodingBit、nQMin和nQMax的數組以後，熵解碼器800解碼表示字典編碼模式的nDicModeSelect。根據nDicModeSelect的值，將要被解碼的比特數據流被分成下面將被描述的兩個不同種類。
圖10是示意圖，說明坐標內插符的每一頂點和每一個頂點的分量數據的比特數據流的結構。如圖10所示，如果nDicModeSelect是0，比特數據流包括已經在出現模式編碼器中編碼的符號和位置索引。另一方面，如果nDicModeSelect是1，則比特數據流包括已經在增量模式編碼器中編碼的符號標誌和位置索引。
上面已經描述的根據本發明的熵解碼器使用以圖19所示的程序代碼實現的函數decodeSignedQuasiAAC。在函數encodeSignedQuasiAA中，使用涉及輸入值和其符號的上下文解碼一種自適應算法編碼的比特數據流。具體地說，在函數decodeSignedQuasiAAC中，使用零上下文解碼符號位之後的比特。熵解碼器800把解碼的數據輸出到字典解碼器810。
圖8A是根據本發明的字典解碼器810的框圖，而圖9A是字典編碼的流程圖。
如圖8A所示，字典解碼器810包括DPCM模式解碼器812，其恢復輸入其中的每一頂點的DPCM模式；字典模式選擇器814，其選擇輸入每一頂點的字典解碼模式；出現模式解碼器816，從字典模式選擇器814接收每一頂點的每一分量的符號和針對符號的位置索引，並且恢復差分數據；以及增量模式解碼器818，其從字典模式選擇器814接收符號標誌和用於符號的位置索引，並且恢復差分數據。
參考圖9A，在步驟S93 1中，包括符號、符號標誌和位置索引的每一頂點的熵解碼的分量數據被輸入到DPCM模式解碼器812。
在字典解碼的差分數據被輸出到反DPCM處理器830之前，在步驟S932中，DPCM模式解碼器812解碼反DPCM操作的模式，其中反DPCM操作是在反DPCM處理器830中將對每一頂點的每一分量的差分數據執行的操作。
隨後參考圖11A描述DPCM模式解碼。
除了表示每一頂點的每一分量的DPCM模式的組合的符號數目被固定在27、因此符號表的大小也被固定在27之外，DPCM模式解碼與稍後將被描述的增量模式解碼相同。
DPCM模式解碼器812接收DPCM模式標誌並且按照輸入的位置索引把對應於DPCM模式標誌的符號記錄在數組中。
例如，如圖11A所示，對應於輸入DMCM模式標誌的符號是1(T T S)，4(TS S)，和5(T S T+S)，並且其各自的索引是(0 1 0 1 0 0)、(1 0 1 0)和(1 1)。因此，使用符號1和其位置索引(0 1 0 1 0 0)恢復數據數組(array)(X 1 X 1 X X)，使用符號4和其位置索引(1 0 1 0)恢復數據數組(4 1 X 1 4 X)，以及使用符號5和其位置索引(1 1)恢復數據數組(4 1 5 1 4 5)。
恢復的數據數組(4 1 5 1 4 5)被轉換成DPCM模式(T S S)(T T S)(T ST+S)(T T S)(T S S)(T S T+S)的組合的數組。因此，有可能表明已經根據恢復的數據數組對每一頂點的每一分量執行了哪一種DPCM。
DPCM模式解碼器812把每一頂點的每一分量的差分數據連同解碼的DPCM模式信息一起輸出到字典模式選擇器814。
在步驟S934中，根據每一頂點的每一分量的nDicModeSelect的值，字典模式選擇器814把從DPCM模式解碼器812輸入的每一頂點的分量數據輸出到出現模式解碼器816或增量模式解碼器818。
如果nDicModeSelect是0，則字典模式選擇器814把頂點的分量數據輸出到出現模式解碼器816，而如果nDicModeSelect是1，則字典模式選擇器814把頂點的分量數據輸出到增量模式解碼器818。
在步驟S936中，出現模式解碼器816把每一個分量的符號數據和位置索引恢復成差分數據。
圖11B是說明出現模式解碼的實例的示意圖。參考圖11B，出現模式解碼器816從字典模式選擇器814接收符號數據並且檢驗bSoleKV和nTrueOne。
如果bSoleKV表示在差分數據中有多個輸入符號並且nTrueOne表示位置索引尚未反，則出現模式解碼器816通過在數據數組中由其各自的位置索引表示的各自的位置插入輸入符號而恢復差分數據。
例如，出現模式解碼器816順序地接收符號3、7和-4以及其各自的位置索引(0 1 0 0 0 1 0 1 0 0 0)、(1 0 1 0 1 0 0)和(1 1 1)。
在按照位置索引(0 1 0 0 0 1 0 1 0 0 0)的差分數據數組中出現模式解碼器816記錄第一符號3。因此，通過把符號3插入在差分數據數組中的對應於位置索引(0 1 0 0 0 1 0 1 0 0 0)中1所處在的位置而獲得(3 X 3 X X X 3 X 3 X X X)。
出現模式解碼器816恢復隨後的符號7。在恢復符號7的過程中，不考慮差分數據數組中的符號3的位置，使得用於符號7的位置索引不是(0 1 0 1 0 0 0 10 0)，而是(1 0 1 0 1 0 0)。
出現模式解碼器816在差分數據數組中的沒被符號3佔用的位置中的第一位置記錄符號7，然後在差分數據數組中對應於位置索引(1 0 1 0 1 0 0)中的1處在的位置記錄符號7。因此，在恢復符號7之後，差分數據數組是(3 7 3 7 X 73 X 3 7 X X)。
出現模式解碼器816按照索引(1 1 1)恢復符號-4，並且因此產生差分數據數組是(3 7 3 7 -4 7 3 -4 3 7 4 -4)。
如果bSoleKV被設置為1，則意味著在差分數據中僅存在輸入符號，並且沒有用於輸入符號的位置索引。因此，出現模式解碼器816把輸入符號記錄在空白差分數據數組中的第一位置，並且執行用於恢復下一個符號的處理。
在步驟S936中，增量模式解碼器818把每一個分量的符號標誌和位置索引恢復成差分數據。隨後參考圖11C描述增量模式解碼。
增量模式解碼器818從字典模式選擇器814接收表示在差分數據中是否存在符號的符號標誌、表示位置索引是否已經反的nTrueOne以及位置索引。
增量模式解碼器818根據輸入符號標誌解碼在差分數據中包括的符號。像用於增量模式編碼的符號表一樣，在用於增量模式解碼的符號表中，按照從具有最低絕對值的符號到具有最大絕對值的符號的次序把符號排列為一列，並且在具有相同絕對值的兩個符號之間，具有正值的符號排列在比另外的符號高的一行中。符號標誌的大小是2nKVCodingBit+1-1，其中nKVCodingBit表示在熵解碼器800中解碼的量化比特的數量。因此，如果符號標誌是(0 0 1 1 0 0 1)，則增量模式解碼器818解碼存在於差分數據中作為符號存在的-1，2，和-3。
符號標誌之後輸入的位置索引分別是(1 0 1 0 0 0 1 0 1 0 0 0)，(0 0 1 0 1 01 1)，和(1 1 1 1)並且分別對應於符號-1、2和3。
增量模式解碼器818在差分數據數組中的對應於位置索引(1 0 1 0 0 0 10 1 0 0 0)中1處在的位置的位置上記錄符號-1，使得產生的數據數組是(-1 X -1X X X -1 X -1 X X X)。
隨後，增量模式解碼器818通過在差分數據數組中的對應於在位置索引(00 1 0 1 0 1 1)中1處在的位置的位置中記錄2而恢復符號2。在恢復符號2的過程中，不考慮差分數據數組中的第一個符號-1的位置，使得產生的差分數據數組是(-1 X-1 X 2 X-1 2-1 X 2 2)。
增量模式解碼器81通過在差分數據數組中的對應於在位置索引(1 1 1 1)中的1處在的位置的位置上記錄-3而恢復符號-3，使得產生的差分數據數組是(-1 -3 -1 -3 2 -3 -1 -3 2 2)。
在步驟S939中，出現模式解碼器816和增量模式解碼器818恢復每一頂點的每一分量的差分數據，並且把恢復的差分數據輸出到反DPCM處理器830。
圖8B是根據本發明的反DPCM處理器830的框圖，而圖9B是反DPCM操作的流程圖。
參考圖8B，根據本發明的反DPCM處理器830包括反時間DPCM操作器842，其對輸入的差分數據執行反時間DPCM操作和反循環量化操作，然後輸出坐標內插符的量化的關鍵字值數據；反空間DPCM操作器844，其對輸入的差分數據執行反空間DPCM操作和反循環量化操作，隨後輸出量化的關鍵字值數據；反空間-時間DPCM操作器846，對輸入的差分數據執行反空間-時間DPCM操作和反循環量化操作，隨後輸出量化的關鍵字值數據；以及反DPCM模式選擇器835，其把輸入其中的差分數據輸出到反時間DPCM操作器842、反空間DPCM操作器844和反空間-時間DPCM操作器846中的一個上。
參考圖9B，在步驟S942中，反DPCM模式選擇器835根據在DPCM模式解碼器812中恢復的每一頂點的每一分量的DPCM操作模式確定將對輸入其中的差分數據執行的反DPCM操作，並且按照反DPCM操作模式而輸出每一頂點的每一分量的輸入的差分數據。
DPCM操作器842、844和846中的每一個同時對輸入其中的差分數據執行反DPCM操作和反循環量化操作。
在步驟S944中，反時間DPCM操作器842遵循方程式(8)對輸入的差分數據執行反時間DPCM操作，在步驟S946中，反空間DPCM操作器844遵循方程式(9)對輸入的差分數據執行反空間DPCM操作，在步驟S948中，反空間-時間DPCM操作器846遵循方程式(10)對輸入的差分數據執行反空間-時間DPCM操作。
V~i,j=Di,j+V~i-1,j(8)]]>V~i,j=Di,j+V~i,Ref(9)]]>V~i,j=Di,j+{V~i-1,j+(V~i,Ref-V~i-1,Ref)}(10)]]>在方程式(8)至(10)中， 表示在第i關鍵幀中的第j個頂點的量化關鍵字值數據，Di，j表示在第i關鍵幀中的第j個頂點的差分數據，而Ref表示參考頂點。
方程式(9)和(10)中，如果 或{V~i-1,j+(V~i,Ref-V~i-1,Ref)}]]>小於每一分量的量化關鍵字值數據的最小值，則使用最小值而不使用 或{V~i-1,j+(V~i,Ref-V~i-1,Ref)}.]]>如果 或{V~i-1,j+(V~i,Ref-V~i-1,Ref)}]]>大於每一個分量的量化關鍵字值數據中的最大值，則使用最大值而不使用 或{V~i-1,j+(V~i,Ref-V~i-1,Ref)}.]]>DPCM操作器842、844和846中的每一個都使用方程式(11)執行反DPCM操作並且同時執行反循環量化操作，以便擴展已經在編碼處理過程中降低的差分數據的範圍。
InverseCircularQuantization(Xi)~:(11)]]>Xi=X~i-(nQMax-nQMin+1)---(ifX~i0)]]>Xi=X~i+(nQMax-nQMin+1)---(otherwise)]]>X^i=X^i-1+X~i---(if nQMinX^i-1+X~inQMax)]]>X^i=X^i-1+Xi---(f nQMinX^i-1+XinQMax)]]>在方程式(11)中， 是與DIJ相同的輸入值， 是與 或{V~i-1,j+(V~i,Ref-V~i-1,Ref)}]]>一樣的先前反循環量化的值。nQMax和nQMin分別表示在DPCMed差分數據中的最大值和最小值。
在步驟S949中，反DPCM處理器830把已經反DPCM的和反循環量化的每一頂點的每一分量的關鍵字值數據輸出到反量化器850。
參考圖7B，遵循方程式(2)，反量化器850把在從關鍵字值標題解碼器870輸入的輸入分量數據中的最小值fMin_X、fMin_Y和fMin_Z和最大範圍值fMax轉換成二進位數，並且通過把fMin_X、fMin_Y、fMin_Z和fMax代入到方程式(12)中而反量化從反DPCM處理器830輸入的量化關鍵字值數據。
V^i,j,x=fMin_X+V~i,j,x2nKVQBits-1fMax(12)]]>V^i,j,y=fMin_Y+V~i,j,y2nKVQBits-1fMax]]>V^i,j,z=fMin_Z+V~i,j,z2nKVQBits-1fMax]]>方程式(12)中，nKVQBits表示用於反量化的量化比特的大小。
反量化器850必須以表2示出的矩陣的形式輸出每一頂點的每一分量的反量化的關鍵字值數據。為了實現此目的，在步驟S960中，反量化器850在輸出反量化的關鍵字值數據之前檢驗反量化的關鍵字值數據的模式是否為轉置模式。如果反量化的關鍵字值數據的模式是轉置模式，則在步驟S965中，反量化器850通過反變換轉置矩陣而產生並且輸出坐標內插符的解碼的關鍵字值數據。
隨後，參照圖12至18描述用於解碼編碼的比特數據流和使用在這種程序代碼中的變量的SDL程序代碼。
圖12示出用於讀出壓縮坐標內插符的比特數據流的最高類(class)。
CoordIKeyValueHeader和CoordIKeyValue是用於讀出對應於一般坐標內插符節點的關鍵字值欄位數據的關鍵字值信息的類。函數qf_start被用於在讀出AAC-編碼的數據之前初始化算法解碼器。
圖13表示使用用於解碼關鍵字值數據所需要的關鍵字值標題信息用於產生比特數據流的程序代碼。
在關鍵字標題數據被解碼之後解碼關鍵字值標題數據。關鍵字值標題包括頂點數目、用於量化的關鍵字值數據參數和用於量化的最大和最小值。bTranspose是表示是否為轉置模式或頂點模式的標誌。如果bTranspose是1，則在解碼處理中選擇轉置模式。另一方面，如果bTranspose是0，選擇頂點模式。nKVQBit是用於通過反量化恢復浮點數字的量化比特。nCoordQBit是用於表示代表頂點數量nNumberOfCoord的比特的大小。在反量化後使用nKVDigit，並且表示關鍵字值數據有效位的最大值數。類KeyValueMinMax恢復用於反量化的最小值和被分成尾數和指數的最大數據範圍。標題信息的其它部分包括在最大值以及每一頂點的每一分量的量化關鍵字值數據中的最大值和最小值中的最小值。具體地說，nXQMinOfMax表示在每一個頂點的x分量的量化關鍵字值數據中的最大值當中的最小值。nNumKeyCodingBit代表表示關鍵字數據數的nNumberofKey的比特大小。需要包括nXQMinofMax和nNumberOfKey信息來解碼關鍵字值數據。
圖14A和14B是表示根據本發明用於實現解碼DPCM模式的裝置的程序代碼。圖14A和14B所示每一變量的含意如下。
nDPCMMode表示每一頂點的每一分量(x，y，z)的DPCM模式。當nDPCMMode被設置為1，2，或3時，分別表示時間DPCM模式、空間DPCM模式，或時間空間的DPCM模式。
bSelFlag是用於選擇每一頂點的每一分量的標誌。使用字典編碼器340僅編碼其bSelFlag被設置為1的每一個頂點的分量。selectionFlagContext是用於讀出bSelFlag的上下文。
nKVACodingBit表示用於每一頂點的每一分量的編碼比特。aqpXContext、aqpYContext和aqpZContext是分別用於X軸、Y軸和Z軸的上下文，被用於讀出nKVACodingBit。
nRefVertex是用於全部頂點的參考頂點的索引。refContext是用於讀出nRefVertex的上下文。
nQMin表示在每一頂點的每一分量的DPCMed差分數據中的最小值。qMinContext表示用於讀出nQMin的上下文，而qMinSignContext是用於讀出nQMin的符號的上下文。
nQMax表示在每一頂點的每一分量的DPCMed差分數據中的最大值。qMaxContext是用於讀出nQMax的上下文，而aMaxSignContext是用於讀出nQMax的符號的上下文。
圖15是說明根據本發明的用於解碼DPCM模式的程序代碼，並且圖15所示的每一變量的含意如下。
bAddressOfDPCMMode表示每一DPCM字典符號的用法，其通過用於在DPCM字典表格中的每一分量的DPCM模式的組合構成。每一頂點包括三個分量，並且在每一個頂點的分量中可能存在三個不同種類的DPCM，T、S和T+S模式。如圖3所示，有27個表示三個DPCM模式的組合的字典符號。dpcmModeDicAddressContext是用於讀出bAddressOfDPCMMode的上下文。
bDPCMIndex表示哪個DPCM符號已經用於每一個頂點。dpcmModelDicIndexContext是用於讀出bDPCMIndex的上下文。
圖16是表示根據本發明用於解碼字典編碼模式的程序代碼的示意圖，圖16示出每一變量的含意如下。
dDicModeSelect表示已經在字典編碼過程中使用的字典編碼模式。當dDicModeSelect是1時，意味著字典編碼模式是增量模式。另一方面，如果dDicModeSelect是0，則意味著字典編碼模式是出現模式。
圖17是表示根據本發明用於實現增量模式解碼方法的程序代碼的示意圖，圖17示出每一變量的含意如下。
bAddress表明是否已經使用了表示量化關鍵字值的增量模式字典符號。使用在增量模式表格中的符號的數量是2nKVCodingBit+1-1。dicAddressContext是用於讀出bAddress的上下文。
nTrueOne表示索引數據是否已經反。當nTrueOne是1時，在位置索引中的1值被認為是表示符號的位置的實際值。當nTrueOne是0時，在位置索引中的0值被認為是表示符號的位置的實際值。
bAddrIndex表示用於每一頂點的每一分量的增量模式符號。dicIndexContext是用於讀出bAddrIndex的上下文。
圖18是說明根據本發明的用於實現出現模式解碼方法的程序代碼，並且圖18所示的每一變量的含意如下。
nQKV包括出現模式符號，它是量化的關鍵字值數據。kvXContext、kvYContext和kvZContext是用於讀出nQKV的上下文，而kvSignContext是用於讀出nQKV的符號的上下文。
bSoleKV表示是否解碼符號在差分數據中僅出現一次。如果解碼符號在差分數據中僅出現一次，則soleKV被設置為1。dicSoleKVContext是用於讀出bSoleKV的上下文。
bDicIndex表示哪個字典符號已經被用於每一頂點的每一分量。dicIndexContext是用於讀出bDicIndex的上下文。
圖20A是表示執行根據本發明的用於編碼和解碼坐標內插符的關鍵字值數據的方法和傳統的MPEG-4BIFS PMFC方法的執行測試性能的結果的速率失真曲線。具體地說，圖20A示出在失真度和在編碼坐標內插符的38個關鍵字值數據情況下的編碼比特率之間的關係。如圖20A所示，用於編碼和解碼坐標內插符的關鍵字值數據的方法具有比傳統的MPEG-4BIFS PMFC方法更高的效率。
圖20B包括三個示意圖(a)、(b)和(c)。具體地說，在圖20B中，(a)表示動畫數據，(b)表示根據本發明編碼/解碼的動畫數據，而(c)表示遵循常規編碼/解碼方法而被編碼/解碼的動畫數據。如圖20B所示，根據本發明用於編碼和解碼坐標內插符的關鍵字值數據的方法能夠提供比常規編碼/解碼方法更高質量的動畫，其大為接近原始的動畫。
上面已經參照附圖描述了根據本發明用於編碼/解碼坐標內插符的關鍵字值數據以便顯示基於關鍵幀的動畫的方法和裝置，其中示出了本發明的優選實施例。本專業技術人員顯然清楚，採用在本發明優選實施例中的DPCM操作不局限於只應用到坐標內插符的關鍵字值數據，而是同樣能應用到包括多個分量來描述三維對象的頂點數據。
圖21A是根據本發明的DPCM操作器的框圖。參考圖21A，根據本發明的DPCM操作器包括時間DPCM操作器2010，其產生構成隨時間的推移而變化的3D對象的在預定時刻頂點數據和另一預定的時刻的頂點數據之間的差分數據；空間DPCM操作器2020，其產生在頂點的數據和在預定時刻的參考頂點的數據之間差分數據；以及DPCM模式選擇器2030，其輸出在從時間DPCM操作器2010輸入的差分數據和從空間DPCM操作器2020輸入的差分數據之間的較小的差分數據。
根據本發明的DPCM操作器最好還包括空間-時間DPCM操作器2040，其計算在頂點和關鍵幀中的參考頂點之間的差分數據之間的差分數據，以及通過對空間DPCM操作的結果執行時間DPCM操作而計算其在另一關鍵幀中的對應的差分數據。即使在提供有空間-時間DPCM操作器的情況中，DPCM模式選擇器2030仍然輸出在從時間DPCM操作器2010輸入的差分數據、從空間DPCM操作器2020輸入的差分數據和從空間-時間DPCM操作器2040輸入的差分數據當中的最小的差分數據。
根據本發明的DPCM操作器的單元的操作與上述的DPCM處理器的對應單元的操作相同。
根據本發明DPCM操作器接收來自外部的構成3D對象頂點的量化坐標數據。
當頂點表示當前對象時，時間DPCM操作器2010使用方程式(3)計算在頂點的坐標數據之間的差分數據，並且當頂點表示先前對象時計算頂點的坐標數據。
空間DPCM操作器2020使用方程式(5)計算已經執行了DPCM操作的頂點和存在於同一個時間軸上作為DPCMed頂點的之間的差分數據，選擇具有最小差分數據的頂點作為參考頂點，並且輸出差分數據。
DPCM模式選擇器2030計算從時間DPCM操作器2010輸入的差分數據和從空間DPCM操作器2020輸入的差分數據的大小，並且連同DPCM操作信息一起輸出具有較小大小的差分數據。
根據本發明的優選實施例，可以進一步包括在DPCM操作器中的空間-時間DPCM操作器2040，使用方程式(6)對3D對象的量化坐標數據執行上述的空間DPCM操作，並且對當前頂點執行空間DPCM操作以及對先前頂點執行空間DPCM操作的結果執行上述的時間DPCM操作。
包括在根據本發明優選實施例的DPCM操作器中的循環量化器2050使用方程式(7)降低輸入其中的差分數據的範圍。
圖21B是反DPCM操作器的框圖，反DPCM操作器把由根據本發明的DPCM操作器產生的差分數據轉換成量化坐標數據。
根據本發明的反DPCM操作器包括反時間DPCM操作器2110，其對在預定時刻的頂點的數據和在另一預定時刻的頂點的數據之間的差分數據執行反DPCM操作；反空間DPCM操作器2120，其對頂點的數據和在預定瞬時的參考頂點的數據之間的差分數據執行反空間DPCM操作；以及反DPCM模式選擇器2100，其根據已經對差分數據執行的DPCM操作的模式，把差分數據輸出到反時間DPCM操作器2110或反空間DPCM操作器2120。
根據本發明的反DPCM操作器最好還包括反空間-時間DPCM操作器2130，對當前反空間DPCM操作的結果以及先前反空間DPCM操作的結果執行反空間-時間DPCM操作。
根據本發明的反DPCM操作器的單元的操作與上述的反DPCM處理器的對應單元的操作相同。
將要被恢復成量化坐標數據的差分數據被輸入到反DPCM模式選擇器2100。隨後，反DPCM模式選擇器2100識別已經對包括在輸入的差分數據中的每一頂點的分量數據執行了哪一種DPCM，並且把每一個頂點的分量數據輸出到反時間DPCM操作器2110、反空間DPCM操作器2120和反空間-時間DPCM操作器2130。
反時間DPCM操作器2110遵循方程式(8)對輸入其中的差分數據執行反時間DPCM操作，反空間DPCM操作器2120遵循方程式(9)對輸入其中的差分數據執行反空間DPCM操作，並且反空間-時間DPCM操作器2130遵循方程式(10)對輸入其中的差分數據執行空間-時間DPCM操作。
如果輸入的差分數據已經被循環量化，則DPCM操作器2110、2120和2130的每一個都使用方程式(11)對其各自的反DPCM的差分數據執行反循環量化操作，以便擴展各自的反DPCM差分數據的範圍。
本發明能夠實現為寫在計算機可讀取記錄介質上的計算機可讀代碼。其中，計算機可讀記錄介質包括能夠由計算機系統讀出的任何種類的記錄介質。例如，計算機可讀記錄介質可以包括ROM、RAM、CD-ROM、磁帶、軟盤、光數據存儲器、載波(通過網際網路發送)等。計算機可讀記錄介質能夠分散到經過網絡連接的計算機系統，並且計算機能夠以分散的方法讀出記錄介質。
考慮了在不同關鍵幀中的頂點的坐標數據之間的差分數據以及坐標內插符的頂點的坐標數據之間的差分數據，根據本發明的用於編碼坐標內插符的關鍵字值數據的方法和裝置通過編碼坐標內插符的關鍵字值數據而具有高編碼效率。
此外，根據本發明的用於編碼坐標內插符的關鍵字值數據的方法和裝置通過使用對應於差分數據的值的符號和針對其各自符號的位置索引表示差分數據而具有更高的編碼效率。
雖然已經參照幾個優選實施例展示和描述了本發明，但是本領域技術人員將理解，在不背離本所附的如權利要求定義的精神和範圍的條件下可以進行各種形式和細節上的改變。
本發明不限於上述實施例，在不脫離本發明範圍的情況下，可以進行各種變形和修改。
權利要求
1.用於產生構成根據時間的推移而移動的對象的頂點量化坐標數據之間的差分數據的裝置，該裝置包括時間DPCM操作器，其產生根據時間的推移改變的每一頂點坐標數據之間的差分數據；空間DPCM操作器，其產生在每一個頂點和在預定時刻的頂點的參考頂點之間的差分數據；及DPCM模式選擇器，其輸出在從時間DPCM操作器輸入的差分數據和從空間DPCM操作器輸入的差分數據之間的較小的差分數據。
2.如權利要求1所述的裝置，還包括空間-時間DPCM操作器，其計算通過在不同時刻對的同頂點執行空間DPCM操作而獲得的第一差分數據，並且對第一差分數據執行時間DPCM操作，以便產生第二差分數據，其中DPCM操作選擇器輸出在從時間DPCM操作器輸入的差分數據、從空間DPCM操作器輸入的差分數據和從空間-時間DPCM操作器輸入的差分數據當中的最小的一個。
3.如權利要求2所述的裝置，其中在當前頂點受到空間DPCM操作之前的已經DPCM的頂點當中，參考頂點是具有用於編碼在本身和受到空間DPCM操作的當前頂點之間的差分數據所需要的最小比特數目的頂點。
4.如權利要求2所述的裝置，其中DPCM模式選擇器對從時間DPCM操作器輸入的差分數據、從空間DPCM操作器輸入的差分數據和從空間-時間DPCM操作器輸入的差分數據執行SAD操作、分散操作和熵操作中的一個，並且選擇在對應操作的結果當中的最小的差分數據。
5.如權利要求2所述的裝置，還包括循環量化器，其通過對時間DPCM的差分數據、空間DPCM的差分數據、空間-時間DPCM的差分數據和差分數據的最大範圍執行預定的操作而產生具有降低大小的差分數據，其中DPCM模式選擇器在對時間DPCM的差分數據、空間DPCM的差分數據、空間-時間DPCM的差分數據和差分數據的最大範圍執行預定操作的結果當中選擇最小的差分數據。
6.如權利要求5所述的裝置，其中循環量化器根據時間DPCM的差分數據、空間DPCM的差分數據和時間空間DPCM的差分數據符號，通過把每一頂點的每一分量的差分數據的範圍值加到差分數據或從差分數據減去範圍值而產生循環量化的差分數據，並且輸出在輸入的差分數據和循環量的化差分數據之間的較小的。
7.通過對頂點的坐標數據之間的差分數據執行預定的反DPCM操作而產生構成根據時間的推移而改變的對象的頂點的量化的坐標數據的裝置，該裝置包括反時間DPCM操作器，其對根據時間的推移而改變的每一頂點的差分數據執行反DPCM操作；反空間DPCM操作器，其對在每一個頂點和對應於預定時刻的頂點的參考頂點之間的差分數據執行反DPCM操作；及反DPCM模式選擇器，其根據包括在輸入差分數據中的DPCM操作模式把輸入其中的差分數據輸出到反時間DPCM操作器或反空間DPCM操作器。
8.如權利要求7所述的裝置，還包括反空間-時間DPCM操作器，其對當前反空間DPCM操作的結果和先前的反空間DPCM操作的結果執行反時間DPCM操作，其中反DPCM模式選擇器根據DPCM操作模式把差分數據輸出到反時間DPCM操作器、反空間DPCM操作器和反空間-時間DPCM操作器中的一個上。
9.如權利要求8所述的裝置，其中通過對差分數據和每一頂點的每一分量的差分數據的最大範圍執行反循環量化操作，反時間DPCM操作器、反空間DPCM操作器和反空間-時間DPCM操作器擴展差分數據的範圍。
10.一種用於產生構成隨時間移動的對象的頂點量化坐標數據之間的差分數據的方法，該方法包括下述步驟(a)執行時間DPCM操作，其中產生在根據時間的推移而改變的每一頂點的坐標數據之間的差分數據；(b)執行空間DPCM操作，其產生在每一個頂點和在對應於預定時刻的頂點的參考頂點之間的差分數據；及(e)輸出在時間DPCM的差分數據和空間DPCM的差分數據之間的較小的差分數據。
11.如權利要求10所述的方法，在步驟(e)之前還包括步驟(c)，計算通過在不同時刻對同一個頂點執行空間DPCM操作獲得的第一差分數據，並且對第一差分數據執行時間DPCM操作以便產生第二差分數據，其中在步驟(e)中，輸出在時間DPCM的差分數據、空間DPCM的差分數據和時間空間的DPCM的差分數據當中的最小的一個。
12.如權利要求11所述的方法，其中在當前頂點受到空間DPCM操作之前已經DPCM的頂點當中，參考頂點是具有用於編碼在本身和受到空間DPCM操作的當前頂點之間的差分數據所需要的最小比特數目的頂點。
13.如權利要求11所述的方法，其中在步驟(e)中，對從時間DPCM操作器輸入的差分數據、從空間DPCM操作器輸入的差分數據和從空間-時間DPCM操作器輸入的差分數據執行SAD操作、分散操作和熵操作中的一個，並且隨後輸出在執行的操作的結果中的最小的差分數據。
14.如權利要求11所述的方法，在步驟(e)之前還包括步驟(d)，執行循環量化工作，其中通過對時間DPCM的差分數據、空間DPCM的差分數據、空間-時間DPCM的差分數據和差分數據的最大範圍執行預定操作而產生具有縮減大小的差分數據，其中在步驟(e)中，輸出在對時間DPCM的差分數據、空間DPCM的差分數據、空間-時間DPCM的差分數據和差分數據的最大範圍執行預定操作的結果中的最小的差分數據。
15.如權利要求14所述的方法，其中在步驟(d)中，根據時間DPCM的差分數據、空間DPCM的差分數據和空間-時間DPCM的差分數據的符號，通過把每一頂點的每一分量的差分數據的範圍值加到差分數據或從差分數據減去範圍值而產生循環量化的數據，並且輸出在差分數據和循環量化的數據之間的較小值。
16.用於通過對頂點的坐標數據之間的差分數據執行預定的反DPCM操作而產生構成根據時間的推移改變的對象的頂點量化坐標數據的方法，該方法包括下述步驟(a)根據包括在差分數據中的DPCM操作模式，選擇將要對差分數據執行的反DPCM操作；及(b)執行選擇的反DPCM操作，其中選擇的反DPCM操作包括反時間DPCM操作，其中對根據時間的推移改變的每一頂點的差分數據執行反DPCM操作；以及反空間DPCM操作，其中對在預定時刻的每一個頂點和對應於頂點的參考頂點之間差分數據執行反DPCM操作。
17.如權利要求16所述的方法，還包括反空間-時間DPCM操作，其中對當前反空間DPCM操作的結果和先前反空間DPCM操作的結果執行反時間DPCM操作。
18.如權利要求17所述的方法，其中在反時間DPCM操作、反空間DPCM操作和反空間-時間DPCM操作中，通過對差分數據和每一頂點的每一分量的差分數據的最大範圍執行反循環量化操作，擴展差分數據的範圍。
全文摘要
一種用於編碼/解碼使用在三維圖形動畫中的坐標內插符關鍵字值數據的方法和裝置。用於編碼使用包括x、y和z分量的每一個頂點的坐標表示對象的每一頂點的位置的坐標內插符的關鍵字值數據的裝置包括量化器，以預定的量化比特量化輸入其中的坐標內插符，DPCM處理器，對量化的坐標內插符的每一頂點的每一分量執行預定模式的DPCM操作，並且因此產生基於每一頂點的坐標的時間變化的差分數據以及基於每一個頂點的坐標的空間變化的差分數據，字典編碼器，產生表示每一頂點的每一分量的差分數據的符號和已經對差分數據執行的DPCM操作的模式以及表示符號的位置的位置索引，和熵編碼器，熵編碼符號和位置索引。
文檔編號G06T15/70GK1664863SQ20051006557
公開日2005年9月7日 申請日期2002年11月27日 優先權日2001年11月27日
發明者李信俊, 鄭錫潤, 張義善, 禹相玉, 韓萬鎮, 金道均, 張敬子 申請人:三星電子株式會社