對位置內插器進行編碼和解碼的方法和裝置的製作方法

2023-08-03 23:41:41 5

專利名稱：對位置內插器進行編碼和解碼的方法和裝置的製作方法
技術領域：
本發明涉及一種用於對三維動畫數據進行編碼和解碼的方法，更具體講，涉及用於對表示目標在三維動畫路徑中的位置的位置內插器進行編碼和解碼的方法和裝置。
背景技術：
在3D計算機遊戲或虛擬實境計算機應用中，已經廣泛採用了三維(3D)動畫技術。虛擬實境造型語言(VRML)是這種3D動畫技術的典型例子。
諸如用於景物的MPEG-4二進位格式(BIFS)和虛擬實境造型語言(VRML)的國際多媒體標準使用內插器節點支持基於關鍵幀的3D動畫。在MPEG-4BIFS和VRML中，有包括標量內插器、位置內插器、坐標內插器、定向內插器、標準行間內插器和顏色內插器在內的各種內插器，這些內插器和它們的功能及特徵示於表1中。
表1

在表1所示的內插器中，位置內插器被用於表示有關動畫路徑的位置的信息，並且由密鑰和密鑰值欄位組成。密鑰欄位使用在-∞和∞之間範圍內的不連續數表示在時間軸上每個關鍵幀的位置。每個密鑰值欄位規定與在某個時刻由每個密鑰表示的目標的位置相關的信息並由三個分量x、y和z組成。密鑰值欄位中的每一個包括與密鑰欄位中的每一個所具有的密鑰值相同數量的密鑰值。
在圖1A和1B中示出了位置內插器的例子。具體來說，圖1A示出了密鑰數據，圖1B示出了密鑰值數據。MPEG-4BIFS提供了一種用於編碼和解碼內插器節點的方法，稱之為預測MF編碼(PMFC)。
圖2為常規的PMFC編碼器以及常規的PMFC解碼器的框圖。如圖2所示，在PMFC中，使用量化器、差分脈衝碼調製(DPCM)操作器和熵編碼器對位置內插器的密鑰數據和密鑰值數據進行編碼。參見圖2，量化器和DPCM操作器消除了密鑰數據和密鑰值數據中的冗餘，並且DPCM操作器將其操作的結果輸出給熵編碼器。但是，由於PMFC只對從一般DPCM操作中獲得的差分數據進行熵編碼，所以其在編碼密鑰數據和密鑰值數據方面不夠有效。另外，由於熵編碼器存在局限性，幾乎不可能提供高質量的動畫。

發明內容
為了解決上述以及其他問題，本發明的一個方面是提供一種用於編碼和解碼位置內插器的方法和裝置，它們能夠提供具有高壓縮率的高質量動畫。
本發明的另一個方面是提供一種測量原始位置內插器和經過解碼的位置內插器之間的誤差的方法，以及一種利用測量原始位置內插器和經過解碼的位置內插器之間的誤差的方法，提取輸入位置內插器的斷點的方法。
因此，為了實現本發明的上述和其他方面，提供了一種用於編碼位置內插器的裝置，該位置內插器包括用於指示關鍵幀在時間軸上的位置的密鑰數據和用於指示目標的位置的密鑰值數據。所述裝置包括一個斷點提取器，用於從由輸入給它的位置內插器組成的第一動畫路徑中提取最小數量的斷點，這可能在第一動畫路徑和由所提取的斷點產生的第二動畫之間引起不大於預定的可允許誤差極限的誤差；一個密鑰數據編碼器，用於編碼從斷點提取器輸入的密鑰數據；和一個密鑰值數據編碼器，用於編碼從斷點提取器輸入的密鑰值數據。
為了實現本發明的上述和其他方面，提供了一種用於編碼位置內插器的裝置，該位置內插器包括用於指示關鍵幀在時間軸上的位置的密鑰數據和指示目標位置的密鑰值數據。該裝置包括一個重取樣器，用於將由密鑰數據和密鑰值數據組成的動畫路逕取樣為預定數量的具有預定時間間隔的部分，並輸出包括重取樣的密鑰數據和重取樣的密鑰值數據的位置內插器；一個密鑰數據編碼器，用於編碼從重取樣器輸入的密鑰數據；以及一個密鑰值編碼器，用於編碼從重取樣器輸入的密鑰值數據。
為了實現本發明上述和其他的方面，提供了一種用於將比特流解碼為位置內插器的裝置，包括用於指示關鍵幀在時間軸上的位置的密鑰數據和用於指示目標位置的密鑰值數據的位置內插器被編碼進該比特流中，所述裝置包括一個密鑰數據解碼器，用於解碼來自輸入比特流的密鑰數據；一個密鑰值數據解碼器，用於解碼來自輸入比特流的密鑰值數據；和一個位置內插器合成器，用於通過將經過解碼的密鑰值數據與利用經過解碼的密鑰值數據進行線性內插的密鑰值數據合成，生成位置內插器。
為了實現本發明的上述和其他的方面，提供了一種用於編碼位置內插器的方法，該位置內插器包括用於指示關鍵幀在時間軸上的位置的密鑰數據和用於指示目標的位置的密鑰值數據，所述方法包括(b)通過從由位置內插器組成的第一動畫路徑中提取最小數量的斷點，產生將被編碼的密鑰數據和密鑰值數據，這可以在第一動畫路徑和將由所提取的斷點產生的第二動畫之間引起不大於預定的可允許誤差極限的誤差；(d)編碼在步驟(b)中產生的密鑰數據；以及(e)編碼在步驟(b)中產生的密鑰值數據。
為了實現本發明的上述和其他的方面，提供了一種用於編碼位置內插器的方法，該位置內插器包括用於指示關鍵幀在時間軸上的位置的密鑰數據和用於指示目標位置的密鑰值數據。所述方法包括(b)將由位置內插器組成的動畫路逕取樣為預定數量的具有預定時間間隔的部分，並且由此產生包括重取樣的密鑰數據和重取樣的密鑰值數據的位置內插器；(d)編碼在步驟(b)中產生的密鑰數據；和(e)編碼在步驟(b)中產生的密鑰值數據。
為了實現本發明上述和其他的方面，提供了一種用於將比特流解碼為位置內插器的方法，包括用於指示關鍵幀在時間軸上的位置的密鑰數據和用於指示目標位置的密鑰值數據的位置內插器被編碼進該比特流中。所述方法包括(a)解碼來自輸入比特流的密鑰數據；(b)解碼來自輸入比特流的密鑰值數據；和(c)通過將經過解碼的密鑰值數據與利用具有經過解碼的密鑰數據的經過解碼的密鑰值數據進行線性內插的密鑰值數據合成，生成位置內插器。
為了實現本發明的上述和其他的方面，提供了一種用於計算在由多個第一路徑點組成的第一路徑和由多個第二路徑點組成的第二路徑之間的誤差的方法，其中每一個第一路徑點由多個數據分量組成，每一個第二路徑點由多個數據分量組成。所述方法包括(a)將多個路徑點內插到第一和第二動畫路徑中，從而使第一和第二動畫路徑就包括在每個路徑點中的參考數據分量而言具有相同的路徑點；(b)根據參考數據分量將第一和第二動畫路徑分為預定數量的部分，從而使預定數量的部分分別對應於路徑點；(c)計算每個部分中的第一和第二動畫路徑之間的誤差；以及(d)檢查是否已經對所有預定數量的部分執行了步驟(c)，然後對在步驟(c)中獲得的誤差進行規範。
為了實現本發明的上述和其他的方面，提供了一種利用線性逼近從由包括多個分量數據的路徑點組成的路徑中提取斷點的方法。所述方法包括(a)提取原始路徑的開始點和結束點；(b)從未提取的路徑點中選擇一個路徑點並利用所選擇的路徑點對其他未選擇的路徑點進行線性內插；(c)計算在原始路徑和使用內插路徑點產生的內插動畫路徑之間的誤差；(d)對所有未被選擇的路徑點執行步驟(b)和(c)並提取導致在原始動畫路徑和內插路徑之間最小誤差的路徑點；以及(e)將原始路徑和使用包括在步驟(d)中提取的路徑點的所有被提取路徑點所產生的路徑之間的誤差與預定的可允許誤差極限進行比較，檢查計算的誤差是否小於可允許的誤差極限，如果是，則完成提取斷點的處理，如果不，則重複執行步驟(b)到(d)。


通過下面結合附圖對本發明的優選實施例進行的詳細描述，本發明的上述和其他方面以及優點都將變得更加清楚，其中圖1A示出了位置內插器的密鑰數據，圖1B示出了位置內插器的x、y和z分量的密鑰值數據；圖2為MPEG-4BIFS PMFC編碼器和MPEG-4 BIFS PMFC解碼器的框圖；圖3A為按照本發明的優選實施例的、用於對位置內插器進行編碼的裝置的框圖，圖3B為按照本發明的優選實施例的、用於對位置內插器進行編碼的方法的流程圖；圖4A到4C為按照本發明優選實施例的分析器的例子的框圖；
圖5A為示出了圖3B所示步驟S320的詳細流程圖；圖5B為按照本發明優選實施例的重取樣方法的流程圖；圖5C為按照本發明優選實施例的提取斷點方法的流程圖；圖6A示出了原始密鑰數據和重取樣的密鑰數據，和圖6B示出了原始動畫路徑和重取樣的動畫路徑；圖7A到7F示出了按照本發明優選實施例的提取斷點的方法；圖8示出了以發生方式從斷點提取器輸出的密鑰數據和密鑰值數據；圖9A為按照本發明優選實施例的密鑰數據編碼器的框圖；圖9B為在圖9A中示出的DND處理器的框圖；圖10A到圖10G為按照本發明優選實施例的、編碼密鑰數據的方法的流程圖；圖11示出了函數encodeSignedAAC的一個例子；圖12A到12J示出了按照本發明優選實施例的、通過執行編碼操作獲得的密鑰數據；圖13A為按照本發明優選實施例的密鑰值數據編碼器的框圖；圖13B為圖13A中所示的量化誤差最小化器的框圖，和圖13C為圖13A中所示的DPCM處理器的框圖；圖14A到14H為按照本發明優選實施例的、編碼密鑰值數據的方法的流程圖；圖15A示出了對量化密鑰值數據執行一般預測DPCM操作的結果，和圖15B示出來對量化密鑰值數據執行經過修改的預測DPCM操作的結果；圖16A示出了量化數據，圖16B和16C分別示出了對圖16A所示的量化數據執行DPCM操作的結果以及對圖16A所示的量化數據執行循環量化DPCM操作的結果；圖17示出了函數UnaryAAC的例子；圖18A和18B示出了函數SQAAC的例子；圖19A為按照本發明優選實施例的、用於解碼位置內插器的裝置的框圖，和圖19B為按照本發明優選實施例的、用於解碼位置內插器的方法的流程圖；圖20為按照本發明優選實施例的密鑰數據解碼器的框圖；圖21A和21B為按照本發明優選實施例的、解碼密鑰數據的方法的流程圖；
圖22A為按照本發明優選實施例的密鑰值數據解碼器的框圖，和圖22B為在圖22A中所示的逆DPCM處理器的框圖；圖23A到23E為按照本發明優選實施例的、解碼密鑰值數據的方法的流程圖；圖24為按照本發明優選實施例的、用於合成位置內插器的密鑰數據和密鑰值數據的方法的流程圖；圖25A和25B示出了在圖3A所示分析器中執行的、測量在動畫路徑之間的誤差的方法；圖26A到26C示出了用於測量在將被編碼的位置內插器和解碼的位置內插器之間的誤差的方法；以及圖27為用於測量在將被編碼的位置內插器和解碼的位置內插器之間的誤差的方法的流程圖。
圖28A-28J是本發明所使用的一部分程序。
具體實施例方式
此後，結合示出了本發明優選實施例的附圖，更加全面地對本發明進行描述。
圖13A為按照本發明優選實施例的、用於編碼位置內插器的裝置的框圖。參看圖13A，所述用於編碼位置內插器的裝置包括分析器40、密鑰數據編碼器200、密鑰值數據編碼器300和標題編碼器400。
圖3B為按照本發明優選實施例的、用於編碼位置內插器的方法的流程圖。參看圖3B，將被編碼的位置內插器在步驟S300被輸入給所述分析器40。在步驟S320，分析器40從包括所述位置內插器的x、y和z分量的密鑰值數據的第一動畫路徑中提取將被編碼的密鑰數據和密鑰值數據，將所提取的密鑰數據輸出給密鑰數據編碼器200，並將所提取的密鑰值數據輸出給密鑰值數據編碼器300。
在步驟S340，密鑰數據編碼器200使用預定數量的量化比特量化從分析器40輸入的密鑰數據，通過對量化的密鑰數據執行預定的DPCM操作，產生差分數據並對所述差分數據熵編碼。
在步驟S360，密鑰值數據編碼器300使用預定數量的量化比特量化從分析器40輸入的密鑰值數據，通過對所述量化數據執行預定的DPCM操作產生差分數據並編碼所述差分數據。
在步驟S380，標題編碼器400從密鑰數據編碼器200和密鑰值數據編碼器300中接收解碼所述密鑰數據和密鑰值數據所需的信息並編碼所述信息。
下面將結合附圖更加詳細的描述分析器40、密鑰數據編碼器200及密鑰值數據編碼器300的結構和操作。
圖4A為按照本發明第一實施例的分析器40的例子的框圖。雖然可以使用分析器40對密鑰值數據的所有分量(x、y和z)執行提取將被編碼的密鑰數據和密鑰值數據的處理，但是，為了便於說明，下面的段落僅僅描述對密鑰值數據的一個分量的處理。
參看圖4A，按照本發明第一實施例的分析器包括重取樣器43，用於在輸入位置內插器的基礎上，將第一動畫路逕取樣成彼此之間具有預定時間間隔的預定數量的部分，並將經過取樣的第一動畫路徑輸出給密鑰編碼器200、密鑰值編碼器300、和標題編碼器400；斷點提取器42，用於提取最小數量的斷點，這樣可以避免在所述第一動畫路徑和根據從第一動畫路徑提取的斷點產生的第二動畫路徑之間的誤差超過預定的可允許誤差極限，並且所述斷點提取器42將所提取的斷點輸出給密鑰數據編碼器200、密鑰值編碼器300、和標題編碼器400；以及選擇器41，用於響應一個外部輸入信號將輸入的位置內插器輸出給重取樣器43或斷點提取器42。斷點提取器42包括線性內插器42a、誤差計算器42b和確定單元42c。
圖5A的流程圖示出了根據本發明第一實施例的分析器40的操作。參看圖5A，在步驟325，選擇器41從外部接收位置內插器和設置信號。該設置信號包括用於確定產生將被編碼的密鑰數據和密鑰值數據的方法的產生方法設置信號和用於確定產生將被編碼的密鑰數據和密鑰值數據的模式的產生模式設置信號。
在下面的段落中，將首先描述用於產生密鑰數據和密鑰值數據的模式。
分析器40通過減少輸入給它的、位置內插器的關鍵幀的數量來減少密鑰數據和密鑰值數據的數量。假設分析器40依據從外部輸入給它的模式設置信號具有動畫路徑保存模式或動畫密鑰保存模式。
在動畫路徑保存模式中，位置內插器僅用於描述對動畫路徑的插入，並且對關鍵幀的隨機存取是不需要的。為了在預定誤差範圍內有效地編碼動畫路徑保存模式下的位置內插器，可以刪除位置內插器中的密鑰數據和與密鑰數據對應的密鑰值數據。
另一方面，在動畫密鑰保存模式中，必須使用諸如『替換』、『刪除』或『插入』的MPEG-4BIFS命令對關鍵幀進行隨機存取。在動畫密鑰保存模式中，位置內插器中的密鑰數據的數量不會改變。後面將更詳細地描述動畫路徑保存模式和動畫密鑰保存模式。
再次參看圖5A，選擇器41按照從外部輸入的產生模式，選擇用於產生將被編碼的密鑰數據和密鑰值數據的模式。在步驟S330，選擇器41向斷點提取器42輸出輸入的位置內插器。如果輸入的產生模式是動畫路徑保存模式，則在步驟S330，選擇器41響應從外部輸入的產生方法設置信號，向重取樣器43或斷點提取器42輸出輸入的位置內插器和產生密鑰數據及密鑰值數據所需的信息。
具體地說，在通過重取樣產生將被編碼的密鑰數據和密鑰值數據的情況下，選擇器41將密鑰數據的數量(即時間間隔)和產生模式與位置內插器一起輸出給重取樣器43。在通過提取斷點產生將被編碼的密鑰數據和密鑰值數據的情況下，選擇器41將原始動畫路徑和將通過所提取的斷點產生的路徑之間的可允許誤差極限以及產生模式輸出給斷點提取器42。
重取樣器43通過以預定時間間隔，對從選擇器41輸入的位置內插器產生的動畫路徑進行取樣，產生取樣的密鑰數據和取樣的密鑰值數據，而斷點提取器42在步驟S335提取最小數量的斷點，這樣可以避免在由輸入位置內插器產生的動畫路徑和將由所提取的斷點產生的動畫路徑之間的誤差超過預定的可允許誤差極限。
圖5B的流程圖示出了按照本發明的優選實施例的重取樣器43的操作。參看圖5B，在步驟S502，重取樣器43從選擇器41接收位置內插器和將被重取樣的密鑰數據的數量(m)。將被重取樣的密鑰數據的數量(m)可以由用戶任意設置或預先被設置為預定值。
在步驟S504，重取樣器43選擇由輸入的位置內插器產生的原始動畫路徑的第一路徑點和最後路徑點，並將要被重取樣的密鑰數據的初始值(i)設置為1。
然後，在步驟S506中，重取樣器43以預定時間間隔產生第i個密鑰數據。
圖6A示出了原始密鑰數據和重取樣的密鑰數據。由於輸入的位置內插器的密鑰數據表示關鍵幀在時間軸上的位置，所以，密鑰數據單調增加，但是密鑰數據之間的間隔是不規則的，如圖6A所示。
因此，如圖6A所示，重取樣器43通過將分別表示在步驟504選擇的第一路徑點和最後路徑點的密鑰數據之間的差值除以將被重取樣的密鑰數據的數量獲得預定時間間隔，然後以該預定時間間隔對要被重取樣的密鑰數據進行重取樣。
在步驟S508中，重取樣器43通過使用原始動畫路徑進行線性內插，產生與由重取樣產生的密鑰數據對應的密鑰值數據。換言之，使用與剛好在重取樣的密鑰數據之後的密鑰數據對應的密鑰值數據和與剛好在重取樣的密鑰數據之前的密鑰數據對應的密鑰值數據，對與重取樣的密鑰數據對應的密鑰值數據進行線性內插。
然後，在步驟S510中，重取樣器43確認是否已經對所有要被重取樣的密鑰數據執行了重取樣處理並重複執行步驟S506和S508，直到所有的密鑰數據和它們的對應密鑰值數據都被重取樣為止。
圖5C的流程圖示出了按照本發明第一實施例的提取斷點的方法，圖7A到7F示出了按照本發明的優選實施例的、從位置內插器提取斷點的每個步驟。
參看圖4A、5C和圖7A到7F，在步驟S520中，斷點提取器42的線性內插器42a從選擇器41接收位置內插器和一個可允許的誤差極限eth。圖7A示出了由輸入的位置內插器構成的動畫路徑。
如圖7A所示，在步驟S522中，線性內插器42a提取由輸入的位置內插器構成的動畫路徑的第一路徑點Q0和最後路徑點Qn，並將計數器(i)設置為1。
在步驟S524中，線性內插器42a任意地或順序地逐一選擇在第一路徑點Q0和最後路徑點Qn之間的路徑點。接著，在步驟S526中，線性內插器42a使用所選擇的路徑點線性內插還沒有被選擇的路徑點，並向誤差計算器42b輸出所選擇的路徑點和經過內插的路徑點。
在步驟S528中，誤差計算器42b計算在原始動畫路徑和由所選擇的路徑點和經過內插的路徑點構成的候選動畫路徑之間的誤差(e)，並將誤差(e)輸出給確定單元42c。計算誤差(e)的方法將在後面進行說明。
誤差計算器42b檢查在還沒有被線性內插器42a選擇的路徑點當中是否仍然存在當計算誤差(e)時沒有被考慮到的路徑點。如果存在當計算誤差(e)時還沒有被考慮到的路徑點，則在步驟S530中，誤差計算器42b通過重複執行步驟S524到S528，計算在所述路徑點和原始動畫路徑之間的誤差。
圖7C示出了步驟S524到S530。參看圖7C，線性內插器42a通過在第一路徑點Q0和斷點Q1之間線性內插多個路徑點，在預定的時刻k1提取與密鑰數據對應的斷點Q1和產生第一候選動畫路徑。誤差計算器42b計算原始動畫路徑和第一候選動畫路徑之間的誤差e1。此後，利用相同的方式，線性內插器42a通過在所述第一路徑點Q0和斷點Qk之間以及在斷點Qk和最後路徑點Qn之間線性內插多個路徑點提取另一個的斷點Qk並產生第k個候選動畫路徑。誤差計算器42b計算在原始動畫路徑和第k個候選動畫路徑之間的誤差(ek)。
如果已經對還沒有被線性內插器42a選擇的所有路徑點執行了步驟S524到S530，那麼，在原始動畫路徑和其中的每個都是按照步驟S524到S530產生的候選動畫路徑之間的誤差被輸出給確定單元42c。然後，在步驟S532中，確定單元42c選擇一個斷點，該斷點形成與原始動畫路徑有最小誤差的候選動畫路徑，並將所述計數器(i)的值加1。
在步驟S534中，確定單元42c檢查在原始動畫路徑和由所提取的斷點構成的候選動畫路徑之間的誤差(e)是否大於可允許的誤差極限eth以及計數器(i)的值是否大於密鑰數據的數量(n)，即在第一路徑點Q0和最後路徑點Qn之間的路徑點的數量。
如果誤差(e)小於可允許的誤差極限eth，則意味著已經提取了編碼所需的所有斷點。如果最後選擇作為將被編碼的斷點的數量等於『n』，則意味著對所有路徑點進行提取斷點的處理都被完成。
但是，如果所選擇的斷點的數量小於n並且誤差(e)大於可允許的誤差極限eth，這意味著仍然存在要被提取的斷點，所提取的斷點被輸出給線性內插器42a，然後再次執行步驟S524到S532。
下面將描述假設當產生模式是動畫路徑保存模式時，從重取樣器43和斷點提取器42輸出給密鑰數據編碼器200和密鑰值數據編碼器300的數據。
重取樣器43分別向密鑰數據編碼器200和密鑰值數據編碼器300輸出密鑰數據和密鑰值數據，並分別作為將被編碼的密鑰數據和密鑰值數據。
下面結合圖8，描述在產生模式的基礎上從斷點提取器42輸出的密鑰數據和密鑰值數據。
如圖8所示，假設最後被提取的斷點被稱為0，3，6和8，利用密鑰選擇標記輸出與斷點0，3、6和8對應的密鑰數據和密鑰值數據，表示如下表所示。
表2

上面描述了按照本發明第一實施例的分析器40的結構。但是，對於本領域普通技術人員來說，很明顯，分析器40可以僅僅由斷點提取器42組成而沒有選擇器41和重取樣器43或者僅僅由重取樣器43組成而沒有選擇器41和斷點提取器42。
下面將描述按照本發明第二實施例的分析器40的例子。
參看圖4B，按照本發明第二實施例的分析器40包括用於接收和重取樣位置內插器的重取樣器45，和用於提取重取樣的位置內插器的斷點並輸出將被編碼的密鑰數據和密鑰值數據的斷點提取器46。本發明第二實施例中的斷點提取器46與本發明第一實施例的斷點提取器類似，也包括線性內插器46a、誤差計算器46b和確定單元46c。
當位置內插器被輸入給分析器40時，重取樣器45將由位置內插器構成的第一動畫路徑重取樣為彼此具有預定時間間隔的預定數量的部分。
重取樣器45將由取樣的密鑰數據和取樣的密鑰值數據組成的位置內插器輸出給斷點提取器46的線性內插器46a。
線性內插器46a通過執行圖5C所示的步驟S522到S526，內插位置內插器，並將內插的位置內插器輸出給誤差計算器46b。誤差計算器46b通過執行步驟S528和S530，計算第一動畫路徑和由所述內插的位置內插器組成的第二動畫路徑之間的誤差。確定單元46C選擇將導致在所述第一和第二動畫路徑之間最小誤差的一個路徑點，確認對應的誤差是否大於可允許的誤差極限eth，並確認第一動畫路徑的所有路徑點是否都已經被選擇，並且產生將被編碼的密鑰數據和密鑰值數據。
如上所述，在按照本發明第二實施例的分析器40中，除了斷點提取器46接收由從重取樣器45輸出的密鑰數據和密鑰值數據組成的位置內插器和對由從重取樣器45輸入的位置內插器構成的動畫路徑執行的提取斷點處理以外，重取樣器45和斷點提取器46的操作與本發明第一實施例中的對應部件的操作相同。
下面結合圖4C描述按照本發明第三實施例的分析器40的例子。
參看圖4C，分析器40包括斷點提取器48，用於接收位置內插器，從由位置內插器構成的第一動畫路徑中提取斷點，並輸出密鑰數據和密鑰值數據；還包括重取樣器49，用於以預定時間間隔，對由位置內插器構成的第二動畫路徑重取樣，該位置內插器由從斷點提取器48輸入的密鑰數據和密鑰值數據組成。與本發明第一和第二實施例的斷點提取器類似，斷點提取器48也包括線性內插器48a、誤差計算器48b和確定單元48c。
與本發明第一實施例的斷點提取器相似，斷點提取器48向重取樣器49輸出從第一動畫路徑提取的密鑰數據和密鑰值數據。
重取樣器49以預定時間間隔，對從斷點提取器48輸入的、由包括密鑰數據和密鑰值數據的位置內插器組成的動畫路徑重取樣，並輸出將被編碼的密鑰數據和密鑰值數據。重取樣器49的功能與本發明第一和第二實施例的重取樣器相同，這裡不再重複。
從在本發明第一到第三實施例中的分析器40輸出的密鑰數據和密鑰值數據分別被輸出給密鑰數據編碼器200和密鑰值數據編碼器300。
下面結合圖9A到12J，描述按照本發明優選實施例的密鑰數據編碼器200的例子。
圖9A的框圖示出了按照本發明優選實施例的密鑰數據編碼器200的例子。參看圖9A，密鑰數據編碼器200包括線性密鑰編碼器900、量化器910、DPCM處理器920、移位器930、摺疊處理器940、DND處理器950和熵編碼器960。
線性密鑰編碼器900識別其中在整個密鑰數據範圍中密鑰數據線性增加的區域並編碼該區域。量化器910使用能夠使量化誤差最小的量化方法，量化輸入給它的密鑰數據。DPCM處理器920接收量化的密鑰數據並產生該密鑰數據的差分數據。移位器930從差分數據中減去所有差分數據中具有最高頻率的差分基準點。摺疊處理器940將差分數據傳輸給正數或負數區域。DND處理器950通過對所述差分數據選擇執行分頻操作、上分頻操作和下分頻操作，減小密鑰數據的差分數據的範圍。熵編碼器960使用被用於對每個比特平面上的差分數據進行編碼的函數SignedAAC或UnsignedAAC，編碼差分數據。
下面將結合圖10A和10B，描述密鑰數據編碼器200的操作。圖10A和10B的流程圖示出了按照本發明優選實施例的編碼密鑰數據的方法。
當密鑰數據被輸入給密鑰數據編碼器200時，密鑰數據的數量和每個密鑰數據的數位被輸入給標題編碼器400並被編碼。線性密鑰編碼器900從輸入的密鑰數據中搜索線性密鑰區域，即關鍵幀被以預定時間間隔置位的區域，密鑰數據彼此之間具有相同的差值，由此，密鑰數據線性增加，然後，在步驟S9000中，首先編碼線性密鑰區域。
諸如3Dmax或Maya等著名的3D應用軟體在一個特定的區域中，使用其間具有預定時間間隔的密鑰，產生基於關鍵幀的動畫。在這種情況下，可以很容易地使用線性密鑰數據區域的開始和結束密鑰數據和存在於它們之間的關鍵幀的數量，編碼密鑰數據。因此，線性預測對於在某個區域中使用內插器編碼密鑰是非常有用的。
下面的等式被用於線性預測。t(i)=tE-tSE-S+tS(0iE-S,SE)(1)]]>這裡，tS表示部分線性區域開始的密鑰的數據，tE表示部分線性區域結束的密鑰的數據，S表示tS的下標和E表示tE的下標。使用下述等式可以計算在從第S個密鑰數據到第E個密鑰數據的特定區域範圍中的實際密鑰數據和按照等式(1)線性預測的密鑰數據之間的誤差。ei=t(i)-ti+s=tE-tSE-Si+tS-ti+S(2)]]>如果使用等式(2)計算的誤差當中的最大值不大於一個預定的臨界值，則可以認為ti在區域[tS，tE]中或某個誤差範圍內是共線的。使用下述等式(3)確定最大誤差值ti是否與一個特定區域共線。Ep=MAXi=0,..(E-S)|ei|=MAXi=o,(E-S)|tE-tSE-Si+tS-ti+S|(3)]]>如果Ep12nBits+1,]]>則ti與區域[tS，tE]共線。這裡，nBits表示用於編碼的比特數。
如果線性密鑰編碼器900尋找部分線性區域，則部分線性密鑰數據區域的開始和結束密鑰數據被輸出給浮點數轉換器905。包括在線性密鑰數據區域中的密鑰的數量被輸出給標題編碼器400並被編碼。使用線性編碼可以顯著地減少要被編碼的數據的數量。
使用浮點數轉換對開始密鑰數據和結束密鑰數據進行編碼，這將在後面描述。
浮點數轉換器905將由二進位系統表示的密鑰數據轉換為十進位系統，以便編碼開始密鑰數據和結束密鑰數據。
計算機將所述浮點數存儲為32位的二進位數。如果給出以二進位系統表示的浮點數，則浮點數轉換器905將該浮點數轉換為十進位系統的尾數和指數，這一處理由下述等式表示。 例如，如下所示，可以利用計算機將浮點數12.34轉換為二進位數。01100010101110000101000112100000103]]>1符號；2二進位系統的尾數；3二進位系統的指數。
如下所示，按照等式(4)可以將二進位數轉換成十進位數。011234223]]>1符號；2十進位系統的尾數；3十進位系統的指數。
為了將十進位系統的尾數和指數包括在比特流中，必須計算表示尾數和指數所需的比特數。尾數具有-38和38之間的值，由此能夠與其符號一起用7位表示。表示尾數所需的比特數根據數位決定。尾數的值和表示該尾數需要的比特數示於下表中。
表3

使用上述過程已經被搜索和轉換的、所述線性密鑰數據區域中的開始和結束密鑰數據被按照圖10C和10D所示的編碼處理進行編碼，並輸出給標題編碼器400和存儲在比特流中。
圖10C和10D示出了對輸入給浮點數轉換器905的兩個浮點數進行編碼的處理。下面結合圖10C和10D，描述浮點數轉換器905編碼浮點數的方法。
在步驟S9040中，浮點數轉換器905接收原始密鑰數據的數位Kd、開始密鑰數據S和結束密鑰數據E並按照等式(4)對它們進行轉換。
浮點數轉換器905首先編碼S。具體地說，浮點數轉換器905檢查S的數位是否與Kd不同，如果S的數位與Kd不同，在步驟S9042中獲得S的數位並輸出給標題編碼器400。浮點數轉換器905用函數Digit獲得S的數位。
如果S的數位大於7，則在步驟S9043中，使用預定數量的比特(在本發明中，按照IEEE標準754的浮點數方式，使用32比特)將S輸出給標題編碼器400，從而使S的數位能夠被包括在比特流中。
如果S的數位不是0並且小於7，則在步驟S9044中，浮點數轉換器905將S的符號輸出給標題編碼器400。使用表3獲得編碼S的尾數的絕對值所需的比特數。接著，在步驟S9045中，使用從表3獲得的比特數將S的尾數的絕對值輸出給標題編碼器400。在步驟S9046中，浮點數轉換器905計算S的指數，並將S的符號輸出給標題編碼器400，和將指數作為例如6比特的預定數量的比特輸出給標題編碼器400。這種密鑰數據轉換使得可以明顯地減少包括在所述比特流中的比特數。
如果S的數位是0，則對開始密鑰數據的編碼結束，由於當S的數位是0時，對應的浮點數也是不需要編碼的0，所以該方法轉到對結束密鑰數據進行轉換。
在轉換和編碼開始密鑰數據S之後，浮點數轉換器905對結束密鑰數據E進行轉換。E的轉換幾乎與S的轉換相同。具體地說，在步驟S9047中，檢查E的指數是否與S的指數相同。如果E的指數與S的指數相同，只把表示E的指數與的S的指數相同的標記比特輸出給標題編碼器400。如果E的指數與S的指數不同，則在步驟S9048中，以與將S的指數輸出給標題編碼器400相同的方式，將E的指數及標記比特輸出給標題編碼器400。
不屬於線性密鑰區域的輸入密鑰數據中的密鑰數據被輸入到量化器910中，並被按照預定的量化比特尺寸、即nKeyQBit，進行量化。
但是，在使用解碼器解碼量化的密鑰數據的情況下，由於原始密鑰數據和量化的密鑰數據之間的誤差，不可能完好地將原始數據恢復。因此，本發明的量化器910獲得輸入密鑰數據當中的最大值和最小值，並使用該最大值和最小值量化輸入密鑰數據。另外，本發明包括一個量化誤差最小化器915，從而可以使用輸入密鑰數據當中的最大值和最小值使原始密鑰數據和它們的量化密鑰數據之間的誤差最小。
步驟S9100中，量化誤差最小化器915在使用用於控制量化範圍的方法預先量化或逆量化輸入密鑰數據，從而可以使量化誤差最小。
具體地說，如果用於量化的混合最大值用Max表示，將被控制的用於量化的最小值用Min表示，輸入值用Xi表示，用於量化的比特數用nQuantBit表示，那麼，利用下述等式可以獲得量化輸入值 ，逆量化值 ，和誤差ei。X~i=floor(Xi-MinMax-Min*(2nQuantBit-1)+0.5)(5)]]>X~i=X~i*(Max-Min)2nQuantBit-1+Min]]>ei=Xi-X^i]]>有兩種用於減少誤差和∑ei的方法。一種用於減少誤差和的方法是通過連續地控制Min，直到誤差和最小為止。另一種如下所述。
首先，讓我們假設Xi＝(i+n)ΔX+εi，其中，Xi指示輸入密鑰數據的順序，ΔX指示輸入數據的基本步長，n是一個任意整數和εi指示平均值為0的隨機噪聲。
下面，當di≡Xi-Xi-1＝ΔX+(εi-εi-1)時，Δ′X＝E[di]並且Min＝Max-Δ′X*(2nQuantBit-1)。
可以使量化誤差最小的Min以及Max被輸入給量化器910並用於量化密鑰數據。
在步驟S9200中，量化器910接收能夠使量化誤差最小的最大值Max和最小值Min，並利用等式(6)量化密鑰數據fKeyi。nQKey=floor(fKeyi-fKeyMinfKeyMax-fKeyMin(2nKeyQBit-1)+0.5)(6)]]>這裡，i表示量化密鑰數據的下標，nQKeyi表示量化密鑰數據的整數數組，fKeyi表示量化密鑰數據的浮點數的數組，fKeyMax表示從量化誤差最小化器915輸入的最大值，fKeyMin表示從量化誤差最小化器915輸入的最小值，和nKeyQBit表示量化比特尺寸。在等式(6)中，函數floor(v)是一個輸出不大於某個浮點值v的最大整數的函數。
本發明的量化器910可以不使用這種減少量化誤差的算法，在這種情況下，僅使用輸入密鑰數據中的最大和最小值fKeyMax和fKeyMin來進行量化。
下面結合圖10E更完整地描述本發明的量化處理。
在步驟S9210中，量化器910接收密鑰數據，並且在步驟S9220中檢查是否已經從量化誤差最小化器915輸入了最大和最小值MAX和MIN。
如果已經輸入了MAX和MIN，量化器910在步驟S9230中分別將用於量化的最大和最小值fKeyMax和fKeyMin設置為MAX和MIN，並將新設置的最大和最小值fKeyMax和fKeyMin輸出給浮點數轉換器905。經過上述浮點數轉換處理，最大和最小值fKeyMax和fKeyMin被轉換和編碼並輸出給標題編碼器400，從而它們能夠被包括在在解碼中使用的密鑰標題中。
如果不存在從量化誤差最小化器915輸入的值，則在步驟S9240中，量化器910分別將第一密鑰數據fKey0和最後密鑰數據fKeyn-1設置為最小值fKeyMin和最大值fKeyMax。
接著，在步驟S9250中，量化器910檢查最大值fKeyMax是否小於1但大於0以及最小值fKeyMin是否大於0。如果最大值fKeyMax不小於1或不大於0，那麼，最大和最小值fKeyMax和fKeyMin被輸出給浮點數轉換器905並通過上述浮點數轉換被轉換和編碼。接著，在步驟S9260中，已經被轉換和編碼的最大和最小值fKeyMax和fKeyMin被包括在密鑰標題中，從而可以在解碼時使用它們。
另一方面，如果最大值fKeyMax小於1並且最小值fkeyMin大於0，則在步驟S9270中，檢查用於指示在用於解碼的密鑰標題中是否將包括最大和最小值fKeyMax和fKeyMin的標記。如果該標記已經被設置，從而使最大和最小值fKeyMax和fKeyMin能夠被包括在密鑰標題中，則執行步驟S9260，以便將最大和最小值fKeyMax和fKeyMin輸出給標題編碼器400。如果還沒有設置該標記，則量化器910不允許將最大和最小值fKeyMax和fKeyMin包括在標題中。
在最大和最小值fKeyMax和fKeyMin沒有被包括在標題中的情況下，假設密鑰數據編碼器和密鑰數據解碼器被分別用於執行編碼和解碼，從而將最大和最小值fKeyMax和fKeyMin分別設置為1和0。在這種情況下，量化器910在步驟S9280中分別將最大和最小值fKeyMax和fKeyMin設置為1和0。對於密鑰數據解碼器來講，最大和最小值fKeyMax和fKeyMin是已知的，因此，它們不需要被包括在密鑰標題中。
在步驟S9290中，量化器910通過將已經經過上述處理設置的最大和最小值fKeyMax和fKeyMin代入等式(6)，量化輸入密鑰數據並將量化的密鑰數據輸出給DPCM處理器920。
DPCM處理器920接收量化的密鑰數據，並對量化的密鑰數據執行預定次數的DPCM。接著，DPCM處理器920向標題編碼器400輸出DPCM的階數以及在每個DPCM循環內獲得的內部密鑰數據，利用DPCM的階數可以獲得在離散度方面的最小值。在步驟S9300中，DPCM處理器920將由DPCM產生的差分數據輸出給移位器930。
參看圖10F，在步驟S9310中，DPCM處理器920對輸入密鑰數據執行預定次數的DPCM並將DPCM的循環數存儲為DPCM的階數。在本發明的優選實施例中，DPCM可以被執行3次。
此後，在步驟S9320中，DPCM處理器920計算每個DPCM循環結果的離散度。這裡，所述離散度可以由離差、標準偏差或四分位差表示，在本發明的優選實施例中，可以使用四分位差。
接著，DPCM處理器920選擇DPCM的一個循環，通過這個循環，可以獲得離散度的最小值，並向移位器930輸出所選擇的DPCM的階數的結果。在步驟S9330中，所選擇的DPCM的循環、每個DPCM循環的內部密鑰數據和DPCM所需的其他信息段被輸出給標題編碼器400。但是，在本發明的優選實施例中，如果密鑰的數量小於5，則僅僅執行一次DPCM。例如，按照等式(7)執行DPCM的第一循環。
Δi＝nQKeyi+1-nQKeyi...(7)這裡，i表示量化密鑰數據的下標，nQKeyi表示整數數組，和Δi表示差分數據。
在步驟S9340中，DPCM處理器920計算編碼所選擇的DPCM循環的結果需要的比特數和已由DPCM產生的在預定存儲器(nQStep_DPCM)中的密鑰數據的差分數據。對於本領域普通技術人員來講很明顯，可以在選擇將被編碼的密鑰數據的後續步驟之後執行編碼所需的、對比特數的計算。
移位器930從由DPCM處理器920輸入的所有差分數據中選擇具有最高頻率的差分基準點(此後稱之為模式)。然後，在步驟S9400中，移位器930從所有差分數據中減去該模式，以便將大多數將被編碼的數據安排在0的周圍並減少編碼所需的比特數。
執行這種從所有量化的密鑰數據中減去模式nKeyshift的移位操作，這種移位操作可由下述等式表示。
shift(nQKeyi)＝nQkeyi-nKeyShift ...(8)這裡，i表示量化密鑰數據的下標，nQKeyi表示整數數組，和nKeyShift表示模式值。作為移位操作的結果，具有最高頻率的差分數據變成0，從而可以明顯減少編碼所需的比特數。
已經被經過移位操作的密鑰數據被輸出給摺疊處理器940和DND處理器950，模式值nKeyShift被輸出給標題編碼器400從而被包括在密鑰標題中。
在步驟S9500中，摺疊處理器940對移位器930的輸出執行摺疊操作並將摺疊操作的結果輸出給DND處理器950。
摺疊操作被用於通過將差分數據集中在正或負數區域內，減少在正數區域和負數區域廣泛離散的差分數據的範圍。在本實施例中，按照等式(9)執行摺疊操作，以便將差分數據集中在所述正數區域中。
fold(nQKeyi)＝2·nQKeyi(如果nQKeyi≥0)...(9)＝2|nQKeyi|-1(如果nQKeyi＜0)這裡，i表示量化密鑰數據的下標，nQKeyi表示整數數組。作為摺疊操作的結果，正差分數據被轉換為偶數，負差分數據被轉換為奇數。
摺疊處理器940計算編碼已經經過摺疊操作的差分數據所需的比特數，並將其存儲在預定的存儲器nQStep_fold中。在這個步驟中，對於本領域普通技術人員很明顯，編碼所需比特數的計算可以在選擇將被熵編碼的差分數據的後續步驟之後執行。在摺疊處理器940中通過摺疊操作產生的數據被輸出給DND處理器950。
為了提高熵編碼的效率，在步驟S9600中，DND處理器950對輸入的密鑰數據的差分數據執行預定次數的DND操作，由此減少差分數據的範圍。
參看圖9B，DND處理器950包括DND操作器952，用於對差分數據執行DND操作；第一差分數據選擇器954，用於根據編碼所需的比特數選擇將被熵編碼的差分數據；上移位操作器956，用於對已經被執行了DND操作的差分數據執行上移位操作；和第二差分數據選擇器958，用於從只經過DND操作的差分數據和已經被執行上移位操作的差分數據之間選擇具有較低離散度的差分數據，並將所選擇的差分數據輸出給熵編碼器960。
在下面的段落中，將描述在DND操作器952中執行的DND操作。
當已經在摺疊處理器940中被執行了摺疊操作的差分數據被輸入給DND操作器952時，它們被分成兩組，比另一組差分數據具有較高範圍的一組差分數據通過一個分頻函數被移動到正數區域。該分頻函數是通過下述等式定義的。
divide(nQKeyj，nKeyMax) ...(10)＝nQKeyj-(nKeyMax+1) (如果nQKeyj＞ )＝nQKeyj-(nKeyMax+1) (如果nQKeyj＞ )這裡，j表示輸入差分數據的下標，nQKeyj表示整數數組，和nKeyMax表示已經被進行摺疊操作的差分數據當中的最大值。特別是，在大多數差分數據沿著由所有差分數據佔據的整個區域的邊界密集排列的情況下，使用分頻操作可以明顯地減少所有差分數據的整個區域。
在分頻操作之後，計算離散度，在這種情況下，編碼所需的比特數被用作測量離散度，以便可以在用於編碼的比特尺寸中選擇最小值。
在DND操作之後，進一步執行不同類型的DND操作，即上分頻操作或下分頻操作。根據差分數據的正範圍尺寸和差分數據的負範圍尺寸確定是執行上分頻操作還是執行下分頻操作。
如果具有正值的差分數據的範圍大於具有負值的差分數據的範圍，則執行由下述等式定義的下分頻操作。
divide-down(nQKeyj，nKeyMax) ...(11)＝-2(nKeyMax-nQKeyj+1)+1 (如果nQKeyj＞ )＝nQKeyj(如果0≤nQKeyj≤ )＝2·nQKeyj(如果nQKeyj＜0)另一方面，如果具有正值的差分數據的範圍大於具有負值的差分數據的範圍，則執行由下述等式定義的上分頻操作。
divide-up(nQKeyj，nKeyMin) ...(12)＝nQKeyj(nQKeyj≥0)＝2·nQKeyj( ≤nQKeyj≤0)＝2(nKeyMin-nQKeyj-1)+1 (nQKeyj＜ )在等式(11)和(12)中，j表示量化密鑰數據的下標，nQKeyj表示整數數組，nKeyMax表示nQKeyj的最大值，nKeyMin表示nQKeyj的最小值。
下面將結合圖10G描述DND操作器952的操作。
當所述輸入密鑰的差分數據是從摺疊處理器940輸入時，在步驟S9610中，DND操作器952獲得輸入差分數據當中的最大值nKeyMax和最小值nKeyMin。然後，在步驟S9620中，DND操作器952將nKeyMax的絕對值與nKeyMin的絕對值進行比較。如果nKeyMax不小於nKeyMin的絕對值，則DND操作器952在步驟S9622將nKeyMax設置為當前DND操作循環中的最大值。
在步驟S9624中，DND操作器952檢查DND操作的階數是否是1，換言之，檢查DND操作的階數是否是1，如果是，則在步驟S9630中，DND操作器952通過將所述最大值代入等式(10)，對輸入差分數據執行分頻操作。
此後，在步驟S9640中，DND操作器952使用函數getQBit測量用於編碼已經被使用分頻操作減少了的差分數據範圍所需的比特尺寸。在步驟S9650中，如果DND操作的階數證明是1，則編碼所需的比特尺寸被存儲作為指示用於編碼的最小尺寸的值nQBitDND，並在步驟S9655中將DND操作的階數增加1。
接著，DND處理器952再次執行步驟S9610到S9622。如果在步驟S9624中DND操作的階數不是1，則DND操作器在步驟S9634中執行下分頻操作，將所述最大值nKeyMax代入等式(11)。在步驟S9640中，DND操作器952計算編碼已經被執行下分頻操作的差分數據所需的比特數。如果該數小於在DND操作的前一循環中存儲的最小值nQBitDND，則在步驟S9658中，在DND操作之後，它取代編碼所需的最小比特尺寸。
在步驟S9620中，如果最小值nKeyMin的絕對值大於所述最大值nKeyMax的絕對值，則在步驟S9623中，在DND操作的當前循環中的最大值被更新為最小值，然後在步驟S9628中執行上分頻操作，用所述最小值替換等式(12)中的nKeyMin。此後，在步驟S9640中，DND操作器952計算用於編碼已經被執行上分頻操作的差分數據的比特數。如果在步驟S9652中證明該計算的結果小於在DND操作的前一循環中已經存儲的nQBitDND，則在步驟S9658中，它取代用於在DND操作之後進行編碼所需的最小比特數nQBitDND。
DND處理器952執行預定次數的DND操作，並且DND操作的執行次數可以改變。例如，在本實施例中，DND操作被執行7次。DND操作器952向第一差分數據選擇器954輸出nQBitDND和與nQBitDND對應的差分數據。DND操作器952向標題編碼器400輸出DND的階數並使得能夠將它們包括在比特流中，利用這個階數已經產生了相應的差分數據。
第一差分數據選擇器954接收已經被執行移位操作的差分數據、已經被執行摺疊操作的差分數據和已經被執行DND操作的差分數據，並確定將對這三個差分數據當中的哪個差分數據進行熵編碼。
參看圖10A和10B，如果在步驟S9700中，用於在DND操作之後進行編碼所需的最小比特數nQBitDND不小於用於在DPCM操作之後進行編碼所需的比特的尺寸nQStep-DPCM，則第一差分數據選擇器954選擇DPCM的結果並對它們執行移位操作。接著，在步驟S9710中，第一差分數據選擇器954向熵編碼器960輸出移位操作的結果並允許它們被熵編碼。在這種情況下，DND操作的階數被設置為-1，並被輸出給標題編碼器400，並被包括在密鑰標題中。
但是，如果證明在步驟S9720中執行的結果小於nQStep-DPCM且不小於用於在摺疊操作之後進行編碼的比特尺寸，則第一差分數據選擇器954在步驟S9730中將經過摺疊操作的差分數據輸出給熵編碼器960並允許它們被熵編碼，在這種情況下，DND操作的階數被設置為0，並被輸出給標題編碼器400，並被包括在密鑰標題中。
如果用於在DND操作之後編碼差分數據所需的比特數最小，則第一差分數據選擇器954向上移位操作器956輸出經過DND操作的差分數據，然後，上移位操作器956在步驟S9740中計算從第一差分數據選擇器954輸入的差分數據的第一離散度。接著，在步驟S9800中，上移位操作器956對經過DND操作的差分數據執行由下述等式規定的上移位操作，並在步驟S9810中計算上移位操作結果的第二離散度。
shift-up(nQKeyj，nKeyMax) ...(13)＝nQKeyj(如果nQKeyj≥0)＝nKeyMax-nQKeyj(如果nQKeyj＜0)這裡，j表示量化的密鑰數據的差分數據的下標，nQKeyj表示整數數組，和nKeyMax表示差分數據當中的最大值。
當輸入已經被執行了DND操作的差分數據和已經被執行了上移位操作的差分數據時，在步驟S9900中，第二差分數據選擇器958將第一離散度與第二離散度進行比較。如果第二離散度小於第一離散度，則在步驟S9910中，第二差分數據選擇器958向熵編碼器960輸出經過上移位操作的差分數據並允許它們被熵編碼。第二差分數據選擇器958向標題編碼器400輸出在DND操作中使用的最大和最小值nKeyMax和nKeyMin以及在上移位操作中使用的最大值nKeyMax，並允許將它們包括在密鑰標題中。
但是，如果第一離散度小於所述第二離散度，則在步驟S9920中，第二差分數據選擇器958向熵編碼器960輸出經過DND操作的差分數據並允許對它們進行熵編碼。然後，第二差分數據選擇器958向標題編碼器400僅輸出在DND操作中使用的最大和最小值nKeyMax和nKeyMin。在本發明的優選實施例中，可以使用標準偏差作為第一和第二離散度的測量。
熵編碼器960根據差分數據的特徵，對差分數據執行兩種不同的功能。例如，被執行了DPCM操作和移位操作的差分數據和僅僅被執行了分頻操作的差分數據具有正和負值，由此，需要執行用於編碼每個差分數據的符號以及差分數據本身的處理。另一方面，由於被執行了摺疊操作的差分數據僅具有正值，所以，僅執行用於編碼差分數據的處理。
在本發明的優選實施例中，函數encodeSignedAAC被用於編碼差分數據和它們的符號，函數encodeUnsignedAAC被用於僅僅編碼差分數據。
圖11示出了函數encodeSignedAAC例子。參見圖11，當輸入值是74和用於編碼該輸入值的比特數是8時，它的符號是0，與二進位數1001010相同。以下述方式對符號和它的所有比特平面編碼第一步驟按照從它的最高有效位(MSB)到最低有效位(LSB)的順序，對每個比特面上的二進位數進行編碼；第二步驟檢查當前正在被編碼的比特是否是0；第三步驟如果當前正在被編碼的比特不是0，則接著編碼該二進位數的符號；以及第四步驟編碼該二進位數的剩餘比特。
函數encodeUnsignedAAC使用關於值的上下文將沒有符號的值編碼為適當的算術編碼比特流。除了存在符號上下文之外，這個函數幾乎與函數encodeSignedAAC相同。
圖12A到12J示出了已經經過根據本發明的優選實施例的操作的密鑰數據的圖表。在圖12A到12J中，水平軸表示每個密鑰數據的下標，垂直軸表示密鑰數據的值。
圖12A示出了輸入給本發明的編碼器的原始密鑰數據的圖表。圖12A所示的密鑰數據被輸出給量化器910，然後被利用9個量化比特進行量化，從而獲得圖12B所示的量化密鑰數據。如果對圖12B所示的量化密鑰數據執行DPCM，則獲得圖12C所示的差分數據。
接著，使用大約7的模式值移位量化密鑰數據的差分數據從而獲得圖12D所示的差分數據。此後，如果對移位後的差分數據執行摺疊操作，可以獲得只有正值的數據，如圖12E所示。
對圖12E所示經過摺疊的數據執行DND操作的結果示於圖12F到12H中。具體來說，圖12F示出了對摺疊數據執行分頻操作的結果。如圖12F所示，正密鑰數據值的範圍是從0到28，負密鑰數據值的範圍是從-29到0，這意味著負密鑰數據值的範圍大於正密鑰數據值的範圍。因此，需要對圖12F所示的數據執行上分頻操作，上分頻操作的結果示於圖12G中。
作為上分頻操作的結果，負密鑰數據值的範圍被明顯減少，從而使其比正密鑰數據值的範圍小得多。在DND操作的後續循環中，對上分頻操作的結果執行下分頻操作。圖12H示出了對圖12G所示的差分數據執行下分頻操作的結果。在圖12I中示出了對圖12H所示的密鑰數據執行上移位操作的結果。
如圖12A到12G所示，密鑰數據和差分數據的範圍被逐漸減少。但是，如圖12H和121所示，在上移位操作之後，差分數據的範圍比以前增加很多，這表示圖12H所示被執行了下分頻操作的差分數據是將被最後編碼的差分數據，如圖12J所示。
下面結合附圖，描述在標題編碼器400中編碼並存儲在密鑰標題中的信息。
當輸入將被編碼的密鑰數據時，標題編碼器400對密鑰數據的數位以及將被編碼的密鑰的數量進行編碼。接著，標題編碼器400從線性密鑰編碼器900中接收有關在輸入密鑰中是否存在經過線性密鑰編碼的線性密鑰數據區域的信息和該線性密鑰數據區域中的密鑰數據的數量，並從浮點數轉換器905中接收已經經過浮點數轉換的線性密鑰數據區域的開始和結束密鑰數據。
在浮點數轉換器905接收可以引起最小量化誤差的最大和最小值並將其轉換成浮點數的情況下，經過轉換的最大和最小值被從浮點數轉換器905輸入給標題編碼器400，從而它們可以被再次用於逆量化。另外，量化比特的尺寸也被輸入給標題編碼器400並被包括在標題中。
標題編碼器400從DPCM處理器920接收在DPCM的每個循環中的DPCM的階數和內部密鑰數據，並從移位器930接收已經被用於移位操作的模式值。另外，標題編碼器400從DND處理器950接收關於是否已經執行了上移位操作的信息、能夠使差分數據的離散度最小的DND的階數以及在每個DND操作循環中的最大和最小值。最後，標題編碼器400從熵編碼器960中接收用於編碼的比特數並將其編碼為密鑰標題。
下面結合圖13A到18B描述密鑰值數據編碼器300的操作和結構。
圖13A的框圖示出了按照本發明的優選實施例的密鑰值數據編碼器300的例子，圖14A示出了根據本發明的優選實施例的，編碼密鑰值數據的方法的流程圖。
參看圖13A，所述密鑰值數據編碼器300包括規範器1300，用於根據所有分量數據範圍當中的最大數據範圍，規範輸入給它的每個分量的密鑰值數據；量化器1310，用於使用預定數量的量化比特，量化規範的密鑰值數據；量化誤差最小化器1320，用於從規範器中接收最小值和最大範圍，調節最小和最大值以便使量化誤差最小，並輸出經過調節的最大和最小值；浮點數轉換器1330，用於從量化誤差最小化器1320中接收最小值和最大範圍，將經過調節的最大範圍和最小值轉換成十進位系統的浮點數；DPCM處理器1340，用於獲得量化密鑰數據的差分數據和預測差分數據，並對差分數據和預測差分數據執行循環量化操作以減少它們的範圍；以及熵編碼器1350，用於熵編碼差分數據並輸出其中密鑰值數據已經被編碼的比特流。
下面結合圖14A描述密鑰值數據編碼器300的操作。
在步驟S14000中，規範器1300接收每個分量(x、y和z)的數據並在步驟S14120中按照等式(14)計算x、y和z分量的數據範圍。然後，規範器1300通過在步驟S14140中進行比較，計算在x、y和z分量數據範圍當中的最大數據範圍。Maxj=Maxi=0n(P-ij)(14)]]>Minj=Mini=0n(P-ij)]]>Rangemax＝Max(Maxx-Minx，Maxy-Miny，Maxz-Minz)然後，規範器1300在步驟S14160使用下面的等式，規範x、y和z分量中每個分量的數據。 在等式(14)和(15)中，n表示數據的數量，i＝0，1，...，n-1，和j表示分量x、y和z中的每一個。
如等式(15)所示，使用在x、y和z分量的數據範圍當中的最大數據範圍Rangemax規範x、y和z分量。作為這種規範的結果，關於不具有最大數據範圍Rangemax的分量的數據的冗餘增加了，因此，編碼效率也增加了。
規範器1300向浮點數編碼器1330輸出每一個分量的密鑰值數據當中的最小值x_min，y_min和z_min、所有分量的密鑰值數據當中的最大值max、與一個分量相關並可以從中得到最大值max的信息nWhichAxis以及原始密鑰值數據的數位nKeyValueDigit，從而使這些信息被作為密鑰值標題包括在比特流中。規範器1300將規範的密鑰值數據輸出給量化器1310。
x、y和z分量中每個分量的、經過規範的密鑰值數據被輸入給量化器1310，然後，量化器1310在步驟S14200中使用預定數量的量化比特nQuantBit對經過規範的密鑰值數據進行量化。P~ij=floor(P-i,j2nQuantBit-1)+0.5)(16)]]>在等式(16)中，函數floor被用於將輸入的浮點數轉換成不大於該輸入浮點數的最大整數。量化器1310向DPCM處理器1340和量化誤差最小化器1320輸出量化的密鑰值數據。
圖13B的框圖示出了按照本發明的優選實施例的量化誤差最小化器1320的例子。參看圖13B，量化誤差最小化器1320包括初始值設置單元1321，用於設置最小誤差值emin、經過調節的最小值min』、量化誤差最小值minmin；經過調節的最小值更新單元1323，用於通過執行預定操作更新經過調節的最小值min』；確定單元1325，用於在更新的經過調節的最小值的數位和值的基礎上，將量化誤差最小值minmin確定為將被用於逆量化的最小值；和誤差值更新單元1327，用於使用更新的經過調節的最小值計算量化誤差值，並且如果所計算的誤差值小於最小誤差值emin，將經過調節的最小值min』和所計算的誤差值分別更新為量化誤差最小值minmin和最小誤差值emin，並將更新的結果輸出給經過調節的最小值更新單元1323。
就量化誤差最小化器1320通過對輸入數據執行量化和逆量化控制量化範圍從而使量化誤差最小這個事實而言，量化誤差最小化器1320與量化誤差最小化器915類似。
下面結合圖14C描述根據本發明的量化誤差最小化器1320的操作。
在步驟S14320中，初始值設置單元1321接收與輸入給量化器1310的數據相同的數據以及從量化器1310輸出的量化數據。
初始值設置單元1321從所輸入的數據中獲得最大值max和最小值min並計算最小值min的數位。接著，在步驟S14340中，初始值設置單元1321通過使用最大值max和最小值min對量化數據進行逆量化來計算量化誤差e，並將該量化誤差e設置為初始最小誤差值emin。
初始值設置單元1321從輸入數據的最小值min中減去將量化步長QuantSpace除以2的結果並將減法結果設置為初始經過調節的最小值min』。然後，在步驟S14360中，初始值設置單元1321將初始經過調節的最小值min』設置為量化誤差最小值minmin並將經過調節的最小值min』輸出給經過調節的最小值更新單元1323。
經過調節的最小值更新單元1323通過執行預定的操作，更新從初始值設置單元1321輸入的經過調節的最小值min』。根據本發明的優選實施例，經過調節的最小值更新單元1323在步驟S14380中按照等式(17)更新從初始值設置單元1321輸入的經過調節的最小值min』並向確定單元1325輸出更新的經過調節的最小值min』。min=Mantissa(min+1)10Exponent(min)(17)]]>在步驟S14400中，確定單元1325計算更新的經過調節的最小值min』的數位，將計算的結果與在初始值設置單元1321中計算的輸入數據當中的最小值min的數位進行比較，並將更新的經過調節的最小值min』與將輸入數據中的最小值min與將量化比特尺寸QuantSpace除以2的結果進行的結果進行比較。
如果經過更新和調節的最小值min』的數位大於輸入數據當中的最小值min的數位，或者如果經過更新和調節的最小值min』大於min+QuantSpace2,]]>則確定單元1325將當前存儲的量化誤差最小值minmin確定為將被用於逆量化的最小值，並將量化誤差最小值minmin輸出給輸出單元1329。如果經過更新和調節的最小值min』的數位不大於輸入數據當中最小值min的數位並且經過更新和調節的最小值min』的數位不大於min+QuantSpace2,]]>則確定單元1325將更新的經過調節的最小值min』輸出給誤差值更新單元1327。
在步驟S14440中，誤差值更新單元1327使用更新的經過調節的最小值min』和由初始值設置單元1321獲得的最大值max對量化數據進行逆量化並計算量化誤差e。
誤差值更新單元1327在步驟S14460中將新計算的誤差值e與最小誤差值emin進行比較。作為比較的結果，如果新計算的誤差值e小於最小誤差值emin，則誤差值更新單元1327在步驟S14480中利用新計算的誤差值e更新最小誤差值emin並利用更新的經過調節的最小值min』更新量化誤差最小值minmin。另一方面，如果新計算的誤差值e大於最小誤差值emin，則誤差值更新單元1327再次執行步驟S14380而不更新最小誤差值emin和量化誤差最小值minmin。
通過上述處理獲得的、用於使量化誤差最小的最大和最小值被輸出給浮點數編碼器1330並被編碼為標題信息。然後，該標題信息被包括在由熵編碼器1350產生的比特流中。
下面結合圖14D描述在浮點數轉換器1330中執行的步驟S14500。浮點數轉換器1330的功能與圖9A所示的浮點數轉換器905類似。
在步驟S14510中，浮點數編碼器1330接收x、y和z分量中每個分量的密鑰值數據當中的最小值x_min，y_min和z_min、具有最大範圍的分量的最大值max、與最大值max所屬分量相關的信息nWhichAxis以及原始密鑰值數據的數位nKeyValueDigit。
為了通過減少編碼所需的比特數來提高編碼密鑰值數據的效率，浮點數編碼器1330在步驟S14520中按照等式(4)將由二進位數表示的x_min，y_min，z_min和max轉換成十進位數。
浮點數編碼器1330在步驟S14530中檢查x_min，y_min，z_min的數位是否相同。如果它們不相同，則在步驟S14540中將它們輸出給標題編碼器400並編碼為標題信息。
如果x_min，y_min，z_min的數位相同，浮點數編碼器1330在步驟S14550中檢查它們是否與原始密鑰值數據的數位相同。如果x_min，y_min，z_min的數位與原始密鑰值數據的數位不同，那麼，在步驟S14560中，在x_min，y_min，z_min的數位中只有一個被輸出給標題編碼器400並被編碼為標題信息。
此後，在步驟S14570中，浮點數編碼器1330檢查從哪一個分量的密鑰值數據當中選擇在x、y和z分量的所有密鑰值數據當中的最大值max，並確定max的數位是否與從中獲得最大值max的分量的密鑰值數據中的最小值的數位相同。
如果max的數位與可以獲得最大值max的分量的密鑰值數據當中的最小值的數位不相同，則它被輸出給標題編碼器400並被編碼為標題信息。另一方面，如果max的數位與最大值max所屬的分量的密鑰值數據當中的最小值的數位相同，則在步驟S14580中，描述它們相同的狀態信息被輸出給標題編碼器400。
浮點數編碼器1330的前述操作用於編碼轉換後的浮點數的尾數，下面將描述將浮點數的指數信息編碼為密鑰值標題的處理。
浮點數編碼器1330在步驟S14590中識別x_min，y_min，z_min和max的指數的絕對值當中哪一個是最大值，將所識別的最大值存儲為nMaxExp，並將nMaxExp編碼為多個比特的密鑰值標題。
此後，浮點數編碼器1330在步驟S14600中檢查x_min，y_min，z_min和max的指數的符號是否相同。如果相同，則bSameSignExp被設置為1並且在步驟S14610將它們的符號輸出給標題編碼器400。另一方面，如果它們不同，則在步驟S14620中，bSameSignExp被設置為0，然後，與x_min，y_min，z_min和max的指數相關的信息的編碼結束。
參看圖14E，浮點數編碼器1330在將x_min，y_min，z_min和max編碼成標題信息之前，在步驟S14630中編碼經轉換的浮點數的符號。
接著，在步驟S14640中，浮點數編碼器1330參照表3計算編碼浮點數所需的比特數，並將具有與計算結果相同的比特的浮點數的尾數輸出給標題編碼器400。
在步驟S14650中，浮點數編碼器1330參照表3計算編碼nMaxExp所需的比特數並將與計算結果具有相同比特的浮點數的指數輸出給標題編碼器400。
在步驟S14660中，浮點數編碼器1330在bSameSignExp的基礎上檢查x_min，y_min，z_min和max的指數是否具有相同的符號。如果它們不具有相同的符號，則在步驟S14670中，將它們的符號輸出給標題編碼器400並編碼，由此完成對從規範器1300輸入的x、y和z分量中每個分量的密鑰數據當中最大值和最小值的編碼處理。
浮點數編碼器1330按照前述步驟，將從量化誤差最小化器1320輸入的並能夠使每個分量的量化誤差最小的最大和最小值編碼為標題信息。
圖13C的框圖示出了按照本發明的優選實施例的DPCM處理器1340的例子，圖14F示出了按照本發明的優選實施例的DPCM操作方法的流程圖。
參看圖13C，DPCM處理器1340包括循環DPCM操作器1341，它包括用於執行一般DPCM操作並輸出差分數據的DPCM操作器1342和用於對輸入給它的差分數據執行循環量化操作從而減少它們的範圍的循環量化操作器1343；預測循環DPCM操作器1345，它包括用於對輸入給它的量化數據執行預測DPCM操作並輸出預測的差分數據的預測DPCM操作器1346以及用於對輸入給它的差分數據執行循環量化操作從而減少它們的範圍的循環量化器1347；以及選擇器1349，用於在輸入給它的差分數據的值的基礎上從由循環DPCM操作器1341輸入的差分數據和由預測循環DPCM操作器1345輸入的差分數據之間選擇一個。
下面參照圖14F描述按照本發明的優選實施例的DPCM操作。
在步驟S14720，量化的密鑰值數據被輸入給循環DPCM操作器1341和預測循環DPCM操作器1345。
在DPCM操作器1341中，通過對輸入給它的量化數據執行一般DPCM操作產生差分數據，並將所產生的差分數據輸出給循環量化器1343。然後，循環量化器1343步驟S14740a中對從DPCM操作器1342輸入的差分數據執行循環量化。
具體地說，DPCM操作器1342通過從當前的量化數據中減去以前的量化數據來計算差分數據。然後，循環量化器1343對所計算的差分數據執行循環量化。循環DPCM操作器1341的操作由下述等式表示。P^i=CircularQuantization(P~i-P~i-1)(i=1,2,,n)(18)]]>在等式(18)中，n表示數據的數量。下面將描述循環量化。
在步驟S14740b中，在預測循環DPCM操作器1345中的預測DPCM操作器1346通過對輸入給它的差分數據執行預測DPCM操作計算預測差分數據，然後循環量化器1347對預測的差分數據執行循環量化。
具體地說，預測DPCM操作器1346通過從當前量化數據中減去預測數據產生預測差分數據並將其輸出。為了獲得與當前量化數據有關的預測數據，通過從在前的量化數據中減去在所述在前量化數據之前的量化數據獲得差分值，然後把它加到在前的差分數據上，從而計算與當前數據相關的預測數據。
由預測DPCM操作器1346計算的預測數據不能超過輸入給它的量化數據的最大範圍。換言之，如果預測數據超過了在輸入量化數據的量化範圍中的最大值，則預測DPCM操作器1346將預測數據設置為輸入量化數據的量化範圍中的最大值，並通過從預測數據中減去當前數據產生與當前數據相關的差分數據。如果預測數據小於輸入數據的量化範圍中的最小值，則預測DPCM操作器1346將當前的數據確定為預測差分數據。此後，預測DPCM操作器1346的這個操作被稱之為「修改的預測DPCM操作」。
由預測DPCM操作器1346計算的預測差分數據被輸入給循環量化器1347並被執行循環量化操作。
預測循環DPCM操作器1346的操作可以由下述等式表示。P~^i=(2nQuaneBit-1)-P~i]]>(如果2P~i-1-P~i-2>2nQuantBit-1]]>) ...(19)P~^i=P~i]]>(如果2P~i-1-P~i-20]]>)P~^i=P~i-(2P~i-1-P~i-2)]]>(否則)P^i=CircularQuantization(P~^i)]]>在等式(19)中，i是2和n-1之間的整數，n表示數據的數量。
圖15A示出了對具有最大值為1024和最小值為0的50個量化數據執行簡單預測DPCM操作的結果，圖15B示出了對與圖15A所示情況相同的數據執行經過修改的預測DPCM操作的結果，由此在與數據相關的預測數據值超過數據當中的最大值或低於最小值的情況下，按照等式(19)調節與數據相關的差分數據。
作為簡單預測DPCM操作的結果，如圖15A和15B所示，預測差分數據具有大約3,000的寬範圍。作為經過修改的預測DPCM操作的結果，如圖16B所示，預測差分數據具有不大於2,000的窄範圍。這意味著在經過修改的預測DPCM操作中比簡單預測DPCM操作中更容易獲得具有較窄範圍的預測差分數據。
下面將描述循環量化。
圖16A示出了量化數據，和圖16B示出了對圖16A所示數據執行DPCM操作的結果。如圖16B所示，在DPCM操作之後，差分數據的範圍可以增加到在DPCM操作之前使用的範圍的兩倍寬。因此可以說，使用循環量化操作，從而使得能夠在將已經被執行了DPCM操作的差分數據範圍保持在輸入數據範圍之內的同時，執行DPCM操作。
在假設量化範圍中的最大值和最小值被彼此循環連接的基礎上，執行循環量化操作。因此，如果作為對兩個連續的量化數據執行線性DPCM的結果的差分數據大於量化範圍中的最大值的一半，則可以通過從差分數據的每一個當中減去最大值來減小它們的值。
如果差分數據小於量化範圍中的最小值的一半，則可以通過將量化範圍中的最大值加到差分數據的每一個上，進一步減小它們的值。
假設X和 分別表示輸入差分數據和循環量化的差分數據，循環量化可以由下述等式表示。CircularQuantization(Xi)=X^i=Min(|Xi|,|Xi|)(20)]]>X′i＝Xi-(2nQBits-1)(如果X≥0)X′i＝Xi+(2nQBits-1)(否則)在等式(20)中，nQBits表示用於量化的比特尺寸。圖16C示出了對圖16B所示的差分數據執行循環量化的結果。
再次參看圖14F，循環量化的差分數據和循環量化的預測差分數據被輸出給選擇器1349，然後，選擇器1349在步驟S14760中對輸入的差分數據執行差分絕對值求和(SAD)操作。這裡，執行SAD操作以便使輸入數據的絕對值都被相加。在步驟S14760中，選擇器1349將循環量化差分數據的所有絕對值相加並將循環量化預測差分數據的所有絕對值相加。
然後，選擇器1349在步驟S14780中將量化差分數據的絕對值的和與預測差分數據的絕對值的和進行比較，在量化差分數據和預測差分數據之間，選擇具有較小絕對值和的差分數據並輸出所選擇的差分數據。選擇器1349選擇具有較小絕對值和的差分數據的原因在於按照推理它們具有較窄範圍的值。例如，在熵編碼預測差分數據中，可以期望編碼絕對值和較小的差分數據所需的比特數少於編碼絕對值和較大的差分數據所需的比特數。
對於本領域技術人員來講很明顯，SAD操作僅僅是選擇某一組差分數據的方法中的一種，因此，選擇器1349可以採用不同方法來選擇差分數據。
再次參看圖14A，在步驟S14800中，從DPCM處理器1340輸出的差分數據在熵編碼器1350中被進行熵編碼。
參看圖14G，熵編碼器1350熵編碼x、y和z分量中每個分量的密鑰值數據的差分數據。
熵編碼器1350參考x、y和z分量中每個分量的差分數據，檢查x、y和z分量的量化值是否相同，即，x、y和z分量的差分數據是否是0，如果它們是相同，則在步驟S14810中完成熵編碼。例如，在三維動畫的情況下，一列火車在與x分量方向相同的水平方向運動，x分量的密鑰值數據是變化的。但是，在y和z分量中存在少量變化。所以，如果所述y和z分量被量化，估計它們將會具有相同的值。因此，不需要對實際相同的所有密鑰值數據進行編碼，由此，通過只將密鑰值數據中的一個編碼成標題信息可以提高編碼效率。
如果x、y和z分量中每個分量的量化密鑰值數據不同，則熵編碼器1350在步驟S14820中讀出已經被預先設置的預定值。此後，熵編碼器1350使用unaryAAC函數在步驟S14830中對x、y和z分量中每個分量的量化密鑰值數據的差分數據進行編碼，或在步驟S14850中使用連續量化AAC函數對它們進行編碼。
下面結合圖17描述unaryAAC函數。unaryAAC函數把將被編碼的符號轉換為由多個0、一個用於指示所述多個0結束的標記位1和表示所述符號的符號的一個比特組成的預定數量的比特。這裡，所述多個0對應於所述符號的幅值。例如，使用unaryAAC函數將256編碼為由256個0、用於指示所述0結束的一個標記位1和表示256的符號即加號的0組成的一系列比特。由於unaryAAC函數使表示將被編碼的符號的比特的冗餘度增加，由此提高了編碼符號的效率。
參考圖14H、18A和18B，將描述使用SQAAC函數編碼符號的方法。SQAAC函數編碼連續更新量化範圍的符號。
圖18A示出了使用SQAAC函數編碼符號的方法。如圖18A所示，將被編碼的輸入符號是1，和編碼範圍中的最小值和最大值分別是0和9。
參看圖18A，在編碼所述符號的第一步驟中，編碼範圍被分成兩個子域，即上界和下界，然後檢查將被編碼的符號，即1，是屬於上界還是屬於下界。由於1屬於下界，所以0被編碼並且下界被更新為一個新的編碼範圍。因此，用於第二步驟的新編碼範圍是從0到4。
在第二步驟中，從0到4的新編碼範圍被分成兩個子域，即上界和下界，然後檢查1是屬於上界還是屬於下界。由於1屬於下界，所以，0被編碼，編碼範圍中的最大值被更新為是下界中最大值的1。因此，用於第三步驟的、通常為下界的新編碼範圍是從0到1。
在第三步驟中，0-1的編碼範圍被分成上限值和下限值，然後檢查1是與上限值還是與下限值相同。由於1等於上限值，所以，1被編碼，然後相應編碼範圍中的最小值被更新為1。因此，新的編碼範圍是[1，1]，由此，它的最大值和最小值彼此相同。當在一個編碼範圍中的最大和最小值相同時，使用SQAAC函數的編碼處理完成。
圖14H示出了在按照本發明的熵編碼器1350中執行的，使用SQAAC函數編碼一個分量的密鑰值數據的差分數據的處理的流程圖。
參看圖14H，熵編碼器1350在步驟S14920中接收密鑰值數據的差分數據(此後稱之為符號)、熵編碼符號所需的比特數nQP、表示首先將被編碼成比特流的符號的下標的nStartIndex和將被編碼的符號的數量(n)。
熵編碼器1350在步驟S14940中編碼符號的正負號並將符號轉換為正數。符號被轉換為正數的原因在於在後續處理中不允許負數。
熵編碼器1350在步驟S14960中識別正數當中的最大值，將最大值存儲為nMax，並將nMax編碼成與nQP一樣多的比特。
熵編碼器1350在步驟S14980中初始化一個符號將在其中被編碼的範圍，並將該編碼範圍中的最小值 和最大值 分別設置為0和nMax。另外，熵編碼器1350將一個比特的標記 分派給每個符號。標記 被用於在編碼符號的過程中改變概率模型。在開始時，標記 被設置為『假』並且當下一個將被編碼的值為1時被轉換為『真』，此後，截止到目前為止用於編碼符號的概率模型被其他的模型取代。
接著，熵編碼器1350在步驟S15000中識別假設被首先編碼的x、y和z分量中每個分量的差分基準點(i＝nStartIndex)並將表示對所有符號的編碼是否已經完成的標記bDone設置為『真』。
熵編碼器1350重複執行將在下面描述的步驟S15020到S15180，直到用於每個符號編碼的編碼範圍中的最大值和最小值變得相同為止，即，直到沒有符號還需要被編碼為止。這裡，當在與一個符號相關的編碼範圍中的最大和最小值相同時，可以認為對符號的編碼已經完成。
熵編碼器1350在步驟S15020中檢查 是否等於 。如果 等於 ，則方法移動到編碼下一個符號的步驟，如果不等，在步驟S15040中，bDone被設置為『假』，這意味著當前符號(當前正在被編碼的符號)的編碼還沒有完成。
熵編碼器1350在步驟S15060中計算在用於當前符號的編碼範圍中的中間值nMid並在步驟S15080中將這個中間值nMid與當前符號的值進行比較。在本發明的優選實施例中，使用下述等式計算中間值nMid。nMid=P^imax+P^imin2+P^imin+1]]>在步驟S15100中，作為比較的結果，如果當前符號值不大於所述中間值nMid，這意味著當前符號屬於下界，則向比特流發出一個0，並且用於當前符號的編碼範圍中的最大範圍 被中間值nMid代替。
另一方面，如果當前符號值大於中間值nMid，則發出一個1給比特流並且在用於當前符號的編碼範圍中的最小值 被中間值nMid所取代。噹噹前正在被編碼的符號的值第一次超過中間值nMid時，換言之，當1第一次被發給比特流時， 在步驟S15120中被設置為『真』，從而改變了用於編碼符號的概率模型。
有兩種在SQAAC函數中使用的概率模型。一種是notFoundContext，用於熵編碼在從每個符號第一次發出1之前輸出的比特，另一種是FoundContext，用於熵編碼在從每個符號第一次發出1之後輸出的比特。使用兩種不同的概率模型的目的是增加在使用notFoundContext期間產生0的概率。由於產生0的概率增加，所述熵編碼符號的效率增加了。
然後，熵編碼器1350在步驟S15140中檢查 是真還是假。如果 是真，則熵編碼器1350在步驟S15160中使用FoundContext編碼符號，如果是假，熵編碼器1350在步驟S15180中使用notFoundContext編碼符號。
當從步驟S15020到步驟S15180的用於編碼當前符號範圍的處理被完成時，這意味著熵編碼器僅僅在一個階段中完成了當前符號的編碼，在步驟S15200中，熵編碼器1350將編碼下標增加1。接著，熵編碼器1350在步驟S15220中檢查當前階段中的所有符號是否都已經被編碼。如果在當前階段中仍舊還有需要被編碼的符號，則熵編碼器1350再次執行步驟S15020到步驟S15220。
當在一階段中的所有符號都被完全編碼時，在步驟S15240中，熵編碼器1350根據標記bDone檢查是否所有階段的編碼都已經完成。如果bDone是真，則熵編碼器1350完成了對當前分量的整個編碼處理並開始對後續的分量編碼，如果不是真，則熵編碼器1350再次執行步驟S15000到S15220，以便編碼剩餘的符號。
圖18B示出了使用SQAAC函數編碼多個符號的處理。特別是，圖18B示出了使用SQAAC函數編碼0、1、2、3、4和9的處理。
再次參看圖14B，如果按照本發明的、用於編碼數據的裝置通過熵編碼所有輸入的密鑰值數據產生一個比特流，那麼，標題編碼器400在步驟S15300中將解碼編碼的密鑰值數據所需的信息編碼為標題信息，並將密鑰值標題信息加到比特流中，並輸出所生成的比特流。
標題編碼器400編碼將被編碼的輸入密鑰值數據的數量與數位以及所述密鑰值數據的量化比特尺寸。接著，標題編碼器400識別x、y和z分量中的每一個是否具有相同的量化值(例如，即使x、y和z分量中的每個分量的密鑰值數據是變化的，由於所述x分量的密鑰值數據的變化程度非常小，所以，x分量的量化密鑰值也具有相同的值)並將結果編碼為一個標記。
例如，如果x分量的量化值不相同，那麼，不管是循環DPCM操作還是預測循環DPCM操作都已經被用於編碼x分量的密鑰值數據，並且不管是將使用unaryAAC函數還是使用SQAAC函數編碼的x分量的密鑰值數據都將被編碼成標記。如果不期望使用unaryAAC函數編碼x分量的密鑰值數據，那麼，x分量的編碼比特尺寸和將被熵編碼的x分量的開始下標被編碼成密鑰值標題。
類似的，如果y和z分量中每個分量的密鑰值數據不同，那麼，與前述x分量的標題信息正好對應的y和z分量的標題信息被編碼成一個標題。
如果x分量的量化值不同，則unaryAAC函數不被用於對x分量的密鑰值數據編碼，並且將被編碼的x分量的開始下標是1，然後，第一量化密鑰值的基準點被編碼為內部基準點。按照相同的方式，y和z分量中每個分量的第一量化密鑰值基準點被編碼為一個內部基準點。
標題編碼器400識別x、y和z分量中的哪一個分量具有最大數據範圍。如果x分量具有最大數據範圍，則標題編碼器400將變量nWhichAxis設置為0。如果y分量具有最大數據範圍，則標題編碼器400將nWhichAxis設置為1。如果分量z具有最大數據範圍，則標題編碼器400將nWhichAxis設置為2。然後，標題編碼器400使用浮點數編碼器1330將nWhichAxis、x_min、y_min、z_min和max編碼成密鑰標題。
再次參見圖3A和3B，按照本發明的、用於編碼位置內插器的裝置編碼密鑰數據和密鑰值數據，並使用標題編碼器400編碼標題信息(在步驟S380)，並輸出其中所述位置內插器已經與編碼的密鑰數據、編碼的密鑰值數據和編碼的標題信息一起被編碼的一個比特流。
下面結合圖19A到24詳細描述按照本發明的優選實施例的，用於解碼其中位置內插器已經被編碼的比特流的方法和裝置。
圖19A的框圖示出了按照本發明的優選實施例的，用於解碼編碼的位置內插器的裝置，圖19B示出了按照本發明的優選實施例的，用於解碼編碼的位置內插器的方法的流程圖。
參看圖19A，用於解碼編碼的位置內插器的裝置包括密鑰數據解碼器1920，用於解碼來自輸入比特流的密鑰數據；密鑰值數據解碼器1950，用於解碼來自輸入比特流的密鑰值數據；標題解碼器1910，用於解碼來自輸入比特流的標題信息並將解碼的標題信息輸出給密鑰數據解碼器1920和密鑰值數據解碼器1950；以及位置內插器合成器1980，用於利用從標題解碼器1910輸入的解碼的標題信息，合成解碼的密鑰數據和解碼的密鑰值數據並輸出解碼的位置內插器。
參看圖19B，在步驟S19000中，被用於編碼圖3A所示的位置內插器的裝置編碼的比特流被輸入給密鑰數據解碼器1920、密鑰值數據解碼器1950和標題解碼器1910。
在步驟S19100中，標題解碼器1910解碼來自輸入比特流的標題信息並將解碼的標題信息輸出給密鑰數據解碼器1920、密鑰值數據解碼器1950和位置內插器合成器1980。
密鑰數據解碼器1920熵解碼來自輸入比特流的密鑰數據，通過對密鑰數據執行預定的逆DND操作、逆摺疊操作和逆移位操作產生解碼的密鑰數據並將解碼的密鑰數據輸出給位置內插器合成器1980。另外，在步驟S19200中，密鑰值解碼器1950熵解碼來自輸入比特流的密鑰值數據，通過對密鑰值數據執行預定的逆量化操作和逆DPCM操作產生解碼的密鑰值數據，並將解碼的密鑰值數據輸出給位置內插器合成器1980。
在步驟S19400中，位置內插器合成器1980通過使用包括模式設置信號和密鑰選擇標記在內的解碼的標題信息合成從密鑰數據解碼器1920輸入的解碼的密鑰值數據和從密鑰值數據解碼器1950輸入的解碼的密鑰值數據，恢復位置內插器。
下面結合圖20到21B詳細描述密鑰數據解碼器1920的結構和操作。按照本發明的密鑰數據解碼器1920接收編碼的比特流並將其組成解碼的密鑰數據。
密鑰數據解碼器1920包括熵解碼器2060、逆DND處理器2050、逆摺疊處理器2040、逆移位器2030、逆DPCM處理器2020、逆量化器2010、線性密鑰解碼器200和浮點數逆轉換器2005。
圖21A示出了按照本發明的優選實施例的用於解碼密鑰數據的方法的流程圖。
將比特流輸入給標題解碼器1910和熵解碼器2060。
標題解碼器1910在步驟S21000中解碼用於解碼的每個步驟所需的信息並將它們提供給它們相應的解碼步驟。下面將隨著每個解碼步驟，描述由標題解碼器1910解碼的信息。
在步驟S21100中，熵解碼器2060從標題解碼器1910接收將被解碼的差分數據的數量以及已經被用於編碼的比特數，即將被用於解碼的比特數，並解碼輸入的比特流。差分數據的數量等於從密鑰數據的數量中減去通過執行DPCM所獲得的內部密鑰數據的數量的結果。
熵解碼器2060根據包括在比特流中的預定信息，例如本發明中的bSignedAACFlag，識別將被解碼的差分數據是具有負值還是具有正值。如果編碼的差分數據具有負值，則熵解碼器2060使用函數decodeSignedAAC對它們進行解碼。另一方面，如果編碼的差分數據僅具有正值，則熵解碼器2060使用函數decodeUnsignedAAC對它們進行解碼。此後，解碼的差分數據被發送給逆DND處理器2050。
逆DND處理器2050從標題解碼器1910中接收DND的階數和在每個DND循環中的最大值nKeyMax。
如果DND的階數是-1，這意味著正在被解碼的編碼差分數據已經經過DPCM操作和移位操作而不是經過DND被進行熵解碼，並且該方法直接進入到執行逆移位操作的步驟。如果DND的階數是0，這意味著正在被解碼的編碼差分數據已經經過摺疊操作而不是DND被進行熵解碼，由此該方法直接進入到執行逆摺疊操作的步驟。如果所述DND的數階大於0，則在步驟S21200中執行逆DND操作。
逆DND處理器2050在步驟S21300中確定正在被解碼的編碼差分數據是否已經經過上移位操作被編碼。在本發明的優選實施例中，通過檢查包括在比特流中的nKeyInvertDown是否大於0來確定正在被解碼的編碼差分數據是否已經經過上移位操作被編碼。
如果正在被解碼的編碼差分數據還沒有經過上移位操作，則該方法進入到執行逆DND的步驟。另一方面，如果正在被解碼的編碼差分數據已經經過上移位操作，則在步驟S21400中通過執行上移位操作已經從正數區域變換到負數區域的差分數據被移回到負數區域。在本發明的優選實施例中，通過執行由下述等式表示的下移位操作(反向向下的操作)恢復已經經過上移位操作的差分數據。
invert-down(v) ...(22)＝v (如果v≤nKeyInvertDown)＝nKeyInvertDown-v(如果v＞nKeyInvertDown)這裡，nKeyInvertDown與在上移位操作中使用的最大值nKeyMax具有相同的值。作為上移位操作的結果，具有高於nKeyInvertDown的值的差分數據被轉換為低於-1的負值。
根據在每個DND循環中的最大值nKeyMax，對已經經過下移位操作的差分數據有選擇地執行逆下分頻操作或逆上分頻操作。
參看圖21B，逆DND處理器2050執行與差分數據在編碼過程中被執行的DND操作次數相同次數的逆DND操作。換言之，逆DND處理器2050將逆DND的階數的初始值設置為等於DND的階數。接著，逆DND處理器2050每執行一次逆DND操作，即從逆DND的階數的初始值中減1，並保持執行DND操作直到逆DND的階數變成1為止。在步驟S21510中，逆DND處理器2050搜索每個DND循環中的nKeyMax並檢查每個nKeyMax是否不小於0。
如果nKeyMax小於0，則意味著在編碼處理中已經執行了上分頻操作，由此，逆DND處理器2050在步驟S21530中通過執行逆上分頻操作將正在被解碼的差分數據的範圍擴展到負數區域。在本發明的優選實施例中，可以使用由下述等式(23)定義的逆上分頻操作。
inverse-divide-up(v) ...(23)＝v (如果v≥0)=(nKeyMaxi-1)-v-12]]>(如果v＜0，v mod 2≠0)=v2]]>(如果v＜0，v mod 2＝0)但是，如果nKeyMax不小於0，則逆DND處理器2050檢查逆DND的階數是否是1。如果逆DND的階數不是1，則意味著對在編碼處理過程中正在被解碼的差分數據已經執行了下分頻操作，因此逆DND處理器2050通過在步驟S21570中執行逆下分頻操作將差分數據的範圍擴展到正數區域。
在本發明的優選實施例中，使用由下述等式定義的逆下分頻操作。
inverse-divide-down(v) ...(24)＝v (如果v≥0)=(nKeyMaxi+1)+v-12]]>(如果v＜0，v mod2≠0)=v2]]>(如果v＜0，v mod2＝0)如果nKeyMax不小於0並且逆DND的階數是1，那麼，逆DND處理器2050在步驟S21590中執行逆分頻操作之後，完成全部逆DND操作。在本發明的優選實施例中，使用由下述等式(25)定義的逆分頻操作。
inverse-divide(v) ...(25)＝v(如果v≥0)＝v+(nKeyMax0+1) (如果v＜0)在步驟S21600中，已經經過逆DND操作的密鑰數據的差分數據被輸入給逆摺疊處理器2040，逆摺疊處理器2040對差分數據執行逆摺疊操作，因此，一直在正數區域中的差分數據被分成正值和負值。在本發明的優選實施例中，使用等式(26)定義的逆摺疊操作。inverse-fold(v)=-(v+1)2]]>(如果v mod 2≠0) ...(26)=v2]]>(如果v mod 2＝0)＝0 (如果v＝0)已經經過逆摺疊操作的差分數據被輸出給逆移位器2030，逆移位器2030在步驟S21700中將已經在編碼過程中使用並從標題解碼器1910輸入的模式nKeyShift加到差分數據上。下述等式表示這個操作。
inverse-shift(v)＝v+nKeyShift ...(27)在步驟S21800中，逆DPCM處理器2020使用從標題解碼器1910輸入的DPCM的階數將從逆移位器2030輸入的差分數據復原成量化的密鑰數據。逆移位器2030執行次數與下述等式(28)規定的DPCM的階數相同的逆DPCM操作。
v(i+1)＝v(i)+delta(i)...(28)這裡，i表示差分數據和密鑰數據的下標，v表示整數數組，delta(i)表示差分數據。
已經經過逆DPCN操作的量化密鑰數據被輸入給逆量化器2010。然後，在步驟S21900中，逆量化器2010從標題解碼器1910接收關於浮點數轉換器905是否對用於逆量化的量化比特尺寸nKeyQBit以及最大和最小值進行編碼的信息，並使用下述等式將所述量化密鑰數據轉換成逆量化的密鑰數據。inverse-quantize(v)=fKeyMin+v2nKeyQBit-1(fKeyMax-fKeyMin)(29)]]>如果在編碼密鑰數據的處理中用於量化的最大和最小值還沒有被浮點數轉換器905轉換，等式(29)中所示的fKeyMin和fKeyMax分別被設置為0和1。但是，如果浮點數轉換器905已經對用於量化的最大和最小值進行了轉換，那麼，被浮點數逆轉換器2005逆轉換的最大和最小值被分別用做用於逆量化的最大和最小值。
從逆量化器2010輸出的解碼的密鑰數據被加到在線性密鑰解碼器2000中解碼的密鑰數據上，由此，構成經過解碼的密鑰數據。
下面將描述線性密鑰解碼處理。
標題解碼器1910解碼來自比特流的密鑰標題信息。如果與線性密鑰數據區域相關的信息存在於比特流中，則標題解碼器1910將解碼線性密鑰數據區域的開始和結束密鑰所需的信息輸出給浮點數逆轉換器2005，並將被編碼為線性密鑰的密鑰的數量輸出給線性密鑰解碼器2000。
浮點數逆轉換器2005將由十進位數表示的所述線性密鑰數據區域的開始和結束密鑰逆轉換為二進位數，並將該二進位數輸出給線性密鑰解碼器2000。
假設將被解碼的兩個浮點數分別被稱做fKeyMin和fKeyMax，下面描述解碼fKeyMin的處理。
標題解碼器1910從比特流中讀出fKeyMin的數位。如果fKeyMin的數位是0，則fKeyMin被設置為0，並從比特流中讀出fKeyMax的數位，以便解碼fKeyMax。如果fKeyMax的數位不小於8，則意味著fKeyMax已經被遵循IEEE標準754進行了解碼。因此，在它的32比特被讀出以後解碼浮點數的fKeyMax。
但是，如果fKeyMax的數位位於1和7之間，則標題解碼器1910從比特流中讀出一個符號位。在本發明的優選實施例中，如果符號位是1，則MinKeyMantissaSign被設置為-1。相反，如果符號位是0，則MinKeyMantissaSign被設置為1。此後，參考示出了尾數的數位和編碼所需比特數之間關係的表3，獲得解碼所需的比特數。接著，和解碼所需比特數相同的比特流的比特被讀出並存儲在nMinKeyMantissa中。然後，讀出比特流的下一位並以與尾數的符號被存儲在MinKeyMantissaSign中相同的方式將其存儲在MinKeyExponentSign中。與指數值對應的比特流的下面6位被讀出並存儲在nMinKeyExponent中。
浮點數逆轉換器2005通過將從標題解碼器1910輸入的值代入等式(30)復原fKeyMin。fKeyMin=MinKeyMantissaSign*nMinKeyMantissa10MinKeyExponentSign*nMinKeyExponent(30)]]>復原fKeyMax的處理與復原fKeyMin的處理相同。具體地說，它確定在從比特流中讀出fKeyMax的指數之前，與fKeyMin的指數相同的值是否被用做fKeyMax的指數。如果與fKeyMin的指數相同的值沒有被用做fKeyMin的指數，則以和從比特流中讀出fKeyMin的指數相同的方式從比特流中讀出fKeyMax的指數。
線性密鑰解碼器2000從浮點數逆轉換器2005中讀出線性密鑰數據區域的開始和結束密鑰，並按照下述等式(31)解碼線性密鑰數據區域。Keyi=fKeyMin+(fKeyMax-fKeyMin)*i(nNumberOfLinearKey-1)(31)]]>(i＝0，...，nNumberOfL inearKey-1)這裡，fKeyMin和fKeyMax分別表示線性密鑰數據區域的開始和結束密鑰數據。
使用前述方法解碼的在線性密鑰數據區域中的密鑰數據被加到從逆量化器2010輸出的密鑰數據上，然後加法的結果被輸出為最後的密鑰數據。
下面結合圖22A和23E描述按照本發明的優選實施例的密鑰值數據解碼器1950的結構和操作。
參看圖22A，密鑰值數據解碼器1950包括熵解碼器2220，用於對輸入給它的比特流熵解碼並輸出差分數據；逆DPCM處理器2230，用於對從熵解碼器2220輸入的差分數據執行逆循環DPCM操作或逆預測循環DPCM操作並輸出量化的密鑰值數據；逆量化器2240，用於逆量化從逆DPCM處理器2230輸入的量化密鑰值數據並輸出規範的密鑰值數據；浮點數解碼器2260，用於從標題解碼器1910接收最小和最大值，將x、y和z分量中每個分量的密鑰值數據當中的最小值和具有最大範圍的分量的最大值轉換成二進位數，並將該二進位數輸出給逆量化器2240；和逆規範器2250，用於從浮點數解碼器2260接收x、y和z分量中每個分量的密鑰值數據當中的最小值和具有最大範圍的分量的最大值，根據來自浮點數解碼器1160的最小值和最大值計算最大範圍，然後逆規範從逆量化器2250輸入的密鑰值數據。
下面結合圖23A描述按照本發明的優選實施例的，用於解碼密鑰值數據的方法。參看圖23A，經過編碼的密鑰值數據的比特流被輸入給熵解碼器1120和標題解碼器1910。然後，在步驟S23000中，標題解碼器1910解碼來自比特流的、解碼所需的標題信息並輸出解碼的標題信息給熵解碼器2220、逆DPCM處理器2230和逆量化器2240。
在步驟S23200中，熵解碼器2220熵解碼比特流並輸出差分數據給逆DPCM處理器2230。
圖23A詳細地示出了熵解碼處理的流程圖。參見圖23A，在步驟S23200中，將比特流Pi輸入給熵解碼器2220。
在步驟S23220中，熵解碼器2220檢查分量，例如x，的密鑰值數據是否具有相同的量化值。如果分量的密鑰值數據具有相同的量化值，則在步驟S23230中，該分量的所有符號都被解碼並將它們設置為從標題解碼器1910輸入的最小值，例如，fMin_X。
如果分量的密鑰值數據不具有相同的量化值，則在步驟S23240中，熵解碼器2220檢查是否已經使用unary AAC函數編碼了該密鑰值數據。如果已經使用unary AAC函數編碼了該密鑰值數據，則在步驟S23250中使用unaryAAC函數對它們解碼。
unary AAC函數從比特流中讀出0直到比特1出現為止，將0的數量轉換成絕對值，讀出比特『1』的下一位作為值的正負號，如果該位是『0』，則該值的正負號為正，如果該位是『1』，則該值的正負號為負，然後輸出被解碼的值。
如果分量的密鑰值數據還未被用unary AAC函數編碼，則熵解碼器2220在步驟S23300中使用將在下面描述的SQ AAC函數解碼其中分量的密鑰值數據已經被編碼的比特流。
在步驟S23310中，熵解碼器2220解碼來自比特流的所有符號的正負號，解碼最大值nMax，並且初始化所有符號的解碼範圍(從0到nMax的範圍)和將標記 設置為『假』。
然後，熵解碼器2220在步驟S23320中確定首先將被解碼的密鑰值基準點(i＝nStartIndex)並將bDone設置為『真』。
熵解碼器2220再次執行步驟S23330到S23430以便解碼符號。
具體地說，熵解碼器2220在步驟S23330中檢查在解碼範圍中的最大值 和最小值 是否相同。
如果 和 相同，則在步驟S23340中，將被編碼的符號被確定為解碼範圍中的最大值(或最小值)，如果不同，則在步驟S23350中，熵解碼器2220將bDone設置為『假』並利用下述等式(32)更新解碼範圍中的中間值nMid。 熵解碼器2220在步驟S23360中檢查上下文標記 是否是真以便確定用於解碼的概率模型。如果所述上下文標記 是真，熵解碼器2220在步驟S23370中使用FoundContext解碼比特流，如果是假，則熵解碼器2220在步驟S23380中使用notFoundContext解碼比特流。
已經對來自比特流的一個比特解碼的熵解碼器2220在步驟S23390中檢查從比特流中解碼的比特是否是1，如果不是，熵解碼器2220在步驟S23400中利用中間值nMid代替解碼範圍中的最大值 。如果述比特流中解碼的比特是1，熵解碼器2220在步驟S23410中利用中間值nMid替換在解碼範圍中的最小值 並將上下文標記 設置為『真』。
熵解碼器2220在步驟S23420中將解碼下標i加1，在步驟S23430中檢查當前階段的分量的所有密鑰值數據是否都已經被解碼，如果還有剩餘的符號需要被解碼，則執行步驟S23330到S23420。
如果當前階段中所有的密鑰值數據都已經被解碼，則熵解碼器2220在步驟S22440中檢查是否需要附加階段去解碼當前分量的密鑰值數據，如果是，則再次執行步驟S23320到S23430。熵解碼器檢查當前分量的所有密鑰值數據是否都已經被解碼，熵解碼器開始解碼下一個分量的密鑰值數據。
參看圖22A和23B，由熵解碼器2220解碼的密鑰值數據的差分數據被輸入給逆DPCM處理器2230，然後，逆DPCM處理器2230依據對輸入的差分數據執行的DPCM的類型，對輸入的差分數據執行逆循環DPCM操作或逆預測循環DPCM操作。
下面結合圖23D描述在步驟S23500中的逆DPCM操作。參看圖23D，已經被執行了逆DPCM操作的差分數據被輸入給確定單元1132。然後，在步驟S23520中，確定單元1132識別對輸入的差分數據執行的DPCM的種類，在識別結果的基礎上確定將對輸入的差分數據執行哪種逆DPCM，並將差分數據輸出給逆循環DPCM操作器2234或逆預測循環DPCM操作器2238。
如果差分數據被輸入給逆循環DPCM操作器2234，並且nMax是差分數據量化範圍中的最大值，則逆循環DPCM操作器2234在步驟S23540中通過對輸入的差分數據 執行逆循環量化，獲得逆循環量化的差分數據 ，這由下述等式表示。 (如果 )...(33) (如果 )此後，逆循環DPCM操作器2234通過分別將輸入的差分數據 和逆循環量化的差分數據 代入等式(34)，獲得逆DPCM的差分基準點的值A和逆DPCM的差分基準點的值B。
在等式(34)中，n表示數據的數量，和i表示1和n-1之間的整數。
如果A不小於0且不大於nMax，則逆循環DPCM操作器2234輸出A作為逆循環DPCM數據 。如果A小於0或大於nMax，則在步驟S23580中，逆循環DPCM操作器2234輸出B。
逆預測循環DPCM操作器2238在步驟S23540中通過使用等式(33)，對預測的差分數據 執行逆預測循環量化，獲得逆循環量化的預測差分數據 。
在步驟S23560中，如果P=2P~i-1+P~i-2]]>，其中，P表示用於解碼的預測數據，逆預測循環DPCM操作器2338通過將 代入等式(35)計算A和將 代入等式(36)計算B。 (如果P＞nMax) ...(35) (如果P＜0) (否則) (如果P＞nMax)...(36) (如果P＜0) (否則)在等式(35)和(36)中，n表示數據的數量，i是1和n-1之間的一個整數。
如果A不小於0並且不大於nMax，則逆預測循環DPCM操作器2238輸出A作為逆預測循環DPCM的數據 。如果A小於0或大於nMax，則逆預測循環DPCM操作器2238在步驟S23580中輸出B作為 。
逆DPCM處理器2230輸出由逆DPCM操作產生的量化密鑰值數據 給逆量化器2240，然後，逆量化器2240在步驟S23700中使用從標題解碼器1910輸入的量化比特nKeyValueQBit逆量化 。當n表示從標題解碼器1910輸入的密鑰值數據的數量時，在逆量化器2240中執行的逆量化可以由下述等式表示。P^ij=P~ij(2nKeyValueQBits-1)]]>(i＝nStartIndex，...，n；j＝x，y，z)...(37)逆量化器2240通過對x、y和z分量中每個分量的密鑰值數據執行逆量化，產生規範的數據並將x、y和z分量中每個分量的規範的密鑰值數據輸出給逆規範器2250。
逆規範器2250在步驟S23800中使用從浮點數解碼器2260輸入的信息，逆規範規範的密鑰值數據。下面將結合圖23E更加詳細地描述在逆規範器2250中執行的逆規範。
浮點數解碼器2260在步驟S23820中從標題解碼器1910中接收將被用於逆規範的最大值fMax，並且分別接收x、y和z分量的最小值fMin_X、fMin_Y和fMin_Z，以及與哪個分量軸具有最大值相關的信息nWhichAxis和與編碼類型相關的信息bUse32Float。
浮點數解碼器2260在步驟S23840中將以十進位數表示的fMax、fMin_X、fMin_Y和fMin_Z轉換為二進位數並將該二進位數輸出給逆規範器2250。
在步驟S23860中，逆規範器2250根據bUse32Float識別fMax、fMin_X、fMin_Y和fMin_Z是否是被用IEEE標準754的浮點數格式編碼的，如果它們不是被用IEEE標準754的浮點數格式編碼的，則逆規範器2250使用下述等式計算在最大數據範圍中的最大值Rangemax。如果fMax、fMin_X，fMin_Y和fMin_Z是被用IEEE標準754的浮點數格式編碼的，則逆規範器2250確定fMax為Rangemax。
Rangemax＝fMax-fMin_X(如果nWhichAxis＝0)...(38)Rangemax＝fMax-fMin_Y(如果nWhichAxis＝1)Rangemax＝fMax-fMin_Z(如果nWhichAxis＝2)如果Rangemax被確定，則逆規範器2250在步驟S23880中根據Rangemax使用下述等式逆規範x、y和z分量中每個分量的數據。P^i,x=P~^i,xRangemax+fMin_X(39)]]>P^i,y=P~^i,yRangemax+fMin_Y]]>P^i,z=P~^i,zRangemax+fMin_Z(i=0,1,n)]]>在等式(39)中，n表示數據的數量。
逆規範器2250在步驟S23900中將逆規範的密鑰值數據輸出給位置內插器合成器1980。
下面將描述用於合成解碼的密鑰數據和解碼的密鑰值數據的位置內插器合成器1980。
圖24示出了位置內插器合成器1980的操作流程圖。
位置內插器合成器1980在步驟S24000中接收解碼的密鑰數據和解碼的密鑰值數據，並從標題解碼器1910接收密鑰數據的數量、斷點產生模式和密鑰選擇標記。
當所述斷點產生模式是動畫路徑保存模式時，在步驟S24100中，位置內插器合成器1980輸出解碼的密鑰數據和解碼的密鑰值數據。在已經以動畫路徑保存模式提取了斷點的情況下，密鑰數據對應於密鑰值數據，因此不需要使用內插產生新的密鑰值數據。但是，如果已經以動畫密鑰保存模式提取了斷點，則意味著在所有密鑰數據都已經被編碼和解碼的同時，只有與斷點對應的密鑰值數據被編碼。因此，在這種情況下，密鑰數據不對應於密鑰值數據，由此需要內插密鑰值數據，這將在下面的段落中描述。
當斷點產生模式是動畫密鑰保存模式時，為了標記出是否存在與密鑰數據對應的密鑰值數據，在步驟S24200中設置一個用於指示密鑰選擇標記數組的下標的計數器，以便與密鑰數據對應。
步驟S24300中，位置內插器合成器1980檢查是否存在由計數器指示的、與密鑰數據對應的密鑰值數據。如果存在由計數器指示的、與密鑰數據對應的密鑰值數據，則位置內插器合成器1980進入到步驟S24500。
如果不存在由計數器指示的、與密鑰數據對應的密鑰值數據，則位置內插器合成器1980在步驟S24400中，通過使用與由兩個連續斷點指示的密鑰數據對應的密鑰值數據，線性內插當前的密鑰值數據產生密鑰值數據，所述兩個連續斷點包括在由計數器指示的密鑰數據之前的一個斷點和由計數器指示的密鑰數據之後的一個斷點。
此後，位置內插器合成器1980在步驟S24500中檢查所有的密鑰數據是否都具有它們的對應密鑰值數據以及是否已經對不具有它們對應的密鑰值數據的所有密鑰數據執行了線性內插。如果仍然存在沒有被檢查的密鑰數據，則位置內插器合成器1980在步驟S24600中更新計數器並再次執行步驟S24300到S24500。如果所有的密鑰數據都已經被檢查，位置內插器合成器1980輸出密鑰數據和合成的密鑰值數據作為位置內插器。
下面結合圖25A到27描述測量動畫路徑之間的誤差的方法。
圖25A和25B示出了測量動畫路徑之間的誤差的方法，該方法是在本發明第一到第三最佳實施例中任何一個的分析器40中執行的。
使用在動畫路徑之間的面積計算在動畫路徑之間的誤差，如圖25A和25B所示。
在圖25中，原始位置內插器的路徑點和通過內插從分析器40的誤差計算器154提取的路徑點產生的位置內插器的路徑點分別被稱之為Pi，j和 。另外，在圖25中，原始動畫路徑和使用內插的位置內插器產生的動畫路徑分別使用實線和虛線標記。這裡，i和j表示位置內插器的密鑰值數據的分量。
如圖25A和25B所示，原始動畫路徑和使用內插的位置內插器產生的動畫路徑之間的誤差可以由包括規則梯形和扭轉的梯形的兩個不同形狀的梯形表示。分析器40的誤差計算器154通過根據構成每個動畫路徑的密鑰數據，將每個分量的兩個動畫路徑分成預定數量的部分，計算每個部分中兩個動畫路徑之間的誤差，並將所有的誤差相加，來產生兩個動畫路徑之間的最後誤差。
特別是，誤差計算器154通過在時間軸上安排原始位置內插器和輸入給它的內插的位置內插器產生兩個動畫路徑。此後，誤差計算器154將兩個動畫路徑中的每一個分成預定數量的部分。
誤差計算器154檢查在每個部分中的兩個動畫路徑之間的誤差是形成梯形還是扭轉的梯形。如果在一個部分中的兩個動畫路徑之間的誤差形成一個梯形，則誤差計算器154使用等式(40)計算梯形的面積。如果在該部分中的兩個動畫路徑之間的誤差形成扭轉的梯形，則誤差計算器154使用等式(41)計算扭轉的梯形的面積。ei,j=12(|P^i-1,j-Pi-1,j|+|P^i,j-Pi,j|)(|ti,j-ti-1,j|)(40)]]>ei,j=(P^i-1,j-Pi-1,j)2+(P^i,j-Pi,j)22(|P^i-1,j-Pi-1,j|+|P^i,j-Pi,j|)(|ti,j-ti-1,j|)(41)]]>利用下述等式(42)計算在一個分量的所有部分中的兩個動畫路徑之間的誤差和。ej=i=0n-1ei,j]]>(j＝x，y，z)...(42)誤差計算器154將從等式(42)獲得的誤差的和輸出給確定單元156，確定單元156在將從誤差計算器154輸入的誤差和與一個可允許的誤差極限比較之後，確定斷點。
另外，可以通過將與密鑰值數據的x、y和z分量中每個分量相關的兩個動畫路徑之間的誤差相加並且根據空間對誤差進行規範，計算在所有部分中的兩個動畫路徑之間的誤差，如等式(43)所示。Maxj=Maxi=0n-1(P-i,j)(43)]]>Minj=Mini=0n-1(P-i,j)]]>Rangemax＝Max(Maxx-Minx，Maxy-Miny，Maxz-Minz)ei,j=ex+ey+ez3Rangemax]]>(i＝0，...，n-1)，j＝x，y，z)根據本發明的用於測量兩個動畫路徑之間的誤差的方法，可以被用於計算在使用輸入給用於編碼位置內插器的一個裝置的位置內插器產生的第一動畫路徑和使用解碼的位置內插器產生的第二動畫路徑之間的誤差。
圖26A到26C示出了計算第一和第二動畫路徑之間的誤差的處理，圖27示出了計算第一和第二動畫路徑之間的誤差的處理的流程圖。
下面結合圖26A到26C以及圖27描述計算第一和第二動畫路徑之間的誤差的方法。
由於解碼的位置內插器的密鑰數據和密鑰值數據在編碼處理過程中已經經過了加法、減法、內插和量化，所以，解碼的位置內插器與原始位置內插器不同。具體地說，由於與在分析器40中執行的計算兩個動畫路徑之間的誤差的處理不同，密鑰數據是變化的，所以，必須對所述密鑰數據的位置進行補償。
圖26A示出了在第一和第二動畫路徑之間形成的規則梯形，圖26B示出了在第一和第二動畫路徑之間形成的扭轉的梯形。如上所述，必須使構成第一動畫路徑的密鑰數據對應於構成第二動畫路徑的密鑰數據，以便通過將第一和第二動畫路徑分成多個部分，測量在第一和第二動畫路徑之間的誤差，如等式(40)到(42)所示。
參看圖26C和27，在步驟S27000中，在第一動畫路徑上不存在但在第二動畫路徑上存在的、與密鑰數據對應的路徑點被插入到第一動畫路徑中，並且，在第二動畫路徑上不存在但在第一動畫路徑上存在的與密鑰數據對應的路徑點被插入到第二動畫路徑中。
然後，在步驟S27100中，根據存在的路徑點和內插的路徑點，將第一和第二動畫路徑分成多個部分。
首先驗證在每個部分中的第一和第二動畫路徑之間的誤差是形成梯形還是扭轉的梯形，然後，在步驟S27200中使用等式(40)和(41)計算在第一和第二動畫路徑之間的誤差。
此後，在步驟S27300中，通過相加以及在時間上和空間上對所有部分中的第一和第二動畫路徑之間的誤差進行規範，來計算使用原始位置內插器產生的第一動畫路徑和使用解碼的位置內插器產生的第二動畫路徑之間的誤差。第一和第二動畫路徑之間誤差的規範可以由下述等式規定。ei,j=ex+ey+ez2(tmax-tmin)Rangemax]]>(i＝0，...，n-1，j＝x，y，z)...(44)在等式(44)中，tMax和tMin分別表示動畫路徑的開始密鑰數據和結束密鑰數據，Rangemax是從等式(43)獲得的值。
此後，圖28A到28J示出了SDL程序代碼的例子，利用該程序代碼實現按照本發明的優選實施例的、用於解碼位置內插器的裝置。
圖28A示出了一個類CompressedPositionInterpolator。CompressedPositionInterpolator是用於讀出定向內插器的編碼比特流的最高級。CompressedPositionInterpolator包括子類KeyHeader、PoslKeyValueHeader、KeySelectionFlag、Key和PoslKeyValue。KeyHeader和PoslKeyValueHeader包括用於解碼Key和PoslKeyValue的標題信息。當與密鑰數據對應的密鑰值數據被包括在PoslKeyValue中時，KeySelectionFlag具有一系列用於指示每個密鑰數據的標記。Key和PoslKeyValue是用於從一個比特流中分別讀出密鑰數據和密鑰值數據的類。
圖28B示出了用於解碼密鑰標題的類，密鑰標題是解碼處理所需的信息。
密鑰標題類包括密鑰數據、量化比特、內部密鑰數據、DND標題的數量以及實際用於解碼的比特數。nKeyQBit表示在逆量化中用於復原浮點數密鑰值的量化比特。NNumberCodingBit表示代表密鑰數據數量的nNumberOfKey的比特尺寸。NKeyDigit表示原始密鑰數據最高有效位的數量並被用於完成解碼值。
當與線性密鑰子區域相關的信息被包括在密鑰標題中時，標記blsLinearKeySubRegion被設置為1。在這種情況下，可以使用在標記blsLinearKeySubRegion後的解碼標題信息計算包括在整個密鑰區域內的特定線性密鑰子區域中的密鑰。BRangeFlag表示密鑰數據的範圍是否是從0到1。如果密鑰數據的範圍不是從0到1，則從類KeyMinMax中解碼密鑰數據範圍內的最小和最大值。KeyMinMax復原進行逆量化所需的最小和最大值。前述值中的每一個都能夠被分成其各自的尾數和指數。
nBitSize是nQIntraKey的比特尺寸，和nKeyShift是nKeyMax的初始比特尺寸。NQIntraKey表示第一量化內部數據的幅值並與表示nQIntraKey的正負的nQIntraKeySign相結合。nQIntraKey被用做復原其他量化密鑰數據的基礎。在內插器壓縮中使用的所有正負號位中，值『0』表示正號，值『1』表示負號。NKDPCMOrder表示DPCM的階數減1的值。DPCM的階數可以是1、2或3。量化的內部數據的數量與DPCM的階數相同。
nKeyShift與正負號位nKeyShiftSign一起是表示在密鑰數據解碼器中移位量的整數。如果bShiftFlag被設置為『真』，則nKeyShift和nKeyShiftSign被解碼。nDNDOrder是分頻-和-分頻(DND)操作的階數。上面已經利用密鑰數據解碼器描述了DND操作。如果nDNDOrder的值是7，則bNoDND被解碼。BNoDND表示是否將執行逆DND操作。nKeyMax是在逆DND操作的連續循環中使用的最大值或最小值。NkeyCodingBit表示用於編碼密鑰數據的比特。BSignedAACFlag表示在AAC解碼中將被執行的解碼處理。如果bSignedAACFlag被設置為0，則將執行一個沒有正負號的AAC解碼處理。反之，將執行有正負號的AAC解碼處理。bKeyInvertDownFlag是一個用於表示是否將使用nKeyInvertDown的布爾值。nKeylnvertDown是一個用於把所有大於其本身的量化密鑰數據轉換成不大於-1的負值的整數。如果nKeyInvertDown被設置為-1，則將不執行下移位操作。
圖28C示出了類LinearKey。在圖28C中，nNumLinearKeyCodingBit是表示編碼預定數量的線性可預測密鑰所需的比特數的值。nNumberOfLinearKey是表示線性可預測密鑰的數量的值。
圖28D示出了類KeyMinMax。在圖28D中，bMinKeyDigitSame是表示所有密鑰的最高有效位的數量(nKeyDigit)和密鑰中的最小值的最高有效位的數量是否相同的標記。nMinKeyDigit是表示密鑰中的最小值的最高有效位的數量的值。nMinKeyMantissaSign是表示nMinKeyMantissaSign的正負號的值。
nMinKeyMantissa是表示在密鑰中的最小值的尾數的值。nMinKeyExponentSign是表示nMinKeyExponent的正負號的值。
nMinKeyExponent是表示密鑰中的最小值的指數的值。fKeyMin是表示密鑰中的最小值的值。bMaxKeyDigitSame是表示所有密鑰的最高有效位的數量nKeyDigit和密鑰中的最大值的最高有效位的數量是否相同的標記。nMaxKeyDigit是表示密鑰中的最大值的最高有效位的數量的值。nMaxKeyMantissaSign是表示nMaxKeyMantissa的正負號的值。nMaxKeyMantissa是表示密鑰中的最大值的尾數的值。
bSameExponent是表示密鑰中的最大值的指數是否與nMinKeyExponent相同的標記。nMaxKeyExponentSign是表示nMaxKeyExponent的正負號的值。nMaxKeyExponent是表示密鑰中的最大值的指數的值。FkeyMax是表示密鑰中的最大值的值。
圖28E示出了類PoslKeyValueHeader。在圖28E中，bPreserveKey表示當前的解碼模式是否是動畫密鑰保存模式，nKVQBit表示密鑰值數據的量化比特尺寸。
x_keyvalue_flag，y_keyvalue_flag和z_keyvalue_flag分別表示x、y和z分量，和nKVDigit表示密鑰值數據中每一個的最高有效位的最大數量。NKVDPCMOrder_X，nKVDPCMOrder_Y和nKVDPCMOrder_Z分別對應於用於x、y和z分量中每個分量的密鑰值數據的DPCM的階數。如果已經執行DPCM，則標記被設置為0，如果已經執行預測DPCM，則該標記被設置為1。
blsUnaryAAC_X，blsUnaryAAC_Y和blsUnaryAAC_Z中的每一個都表示在熵編碼期間已經使用了unary AAC函數。nKVCodingBit_X，nKVCodingBit_Y和nKVCodingBit_Z表示分別用於x、y和z分量的量化比特。nStartIndex_X，nStartIndex_Y和nStartIndex_Z表示每個分量軸的開始下標。firstKV_X，firstKV_Y和firstKV_Z分別表示已經被首先量化的x、y和z分量中每個分量的密鑰值基準點。
圖28F示出了類KeyValueMinMax。參看圖28F，類KeyValueMin復原已經被用於規範密鑰值數據的最大和最小值。bUse32float表示32位浮點數是否已經被用於存儲最大和最小值。如果bUse32Float是0，則十進位的浮點數已經被用於存儲所述最大和最小值。
nWhichAxis表示在x、y和z分量中具有最大數據範圍的分量。在本實施例中，如果nWhichAxis是0，則X軸具有最大數據範圍。如果nWhichAxis是1，則Y軸具有最大數據範圍，和如果nWhichAxis是2，則Z軸具有最大數據範圍。
BAllSameMantissaDigitFlag表示x、y和z分量中的每個分量的密鑰值數據當中的最小值的尾數是否具有相同的數位，bSameKVDigitFlag表示最小值的尾數的數位與nKeyDigit相同。nMantissaDigit_X，nMantissaDigit_Y和nMantissaDigit_Z表示x、y和z分量中的每個分量的密鑰值數據中的最小值的尾數的數位。
BMaxDigitFlag表示最大值的尾數是否與最小值的尾數具有相同的數位。如果最大值的尾數的數位不同於最小值的尾數的數位，則從比特流中讀出最大值的尾數的數位。
nMantissaDigit_M表示最大值的尾數的數位，nExponentBits表示用於編碼最大值的指數所需的比特數。BAllSameExponentSign表示x、y和z分量的正負號是否相同，nExponentSign表示當bAllSaneExponentSign是真時的指數的正負號。
fpnMin_X、fpnMin_Y、fpnMin_Z和fpnMax表示在十進位系統中被解碼的浮點數。下面將利用FloatingPointNumber描述解碼fpnMin_X，fpnMin_Y和fpnMin_Z和fpnMax的方法。fMin_X，fMin_Y和fMin_Z表示x、y和z分量中每個分量的密鑰值當中的最小值，fMax表示具有最大範圍的分量的密鑰值數據當中的最大值。
圖28G示出了類FloatingPointNumber。類FloatingPointNumber表示使用十進位系統的浮點數。nMantissa表示十進位系統中的浮點數的尾數，nExponent表示浮點數的指數。
nSign表示十進位系統中的浮點數的正負號，nExponentSign表示十進位系統中的浮點數的指數的正負號。
圖28H示出了類KeySelectionFlag。在圖28H中，KeyFlag表示第i個密鑰數據的密鑰值數據是否已經被編碼，nNumOfKeyValue是表示將被解碼的密鑰值數據的數量的整數。
圖28I示出了類Key。在圖28I中，nQKey是來自比特流的、將被解碼的量化密鑰數據的數組。KeyContext是用於讀出nQKey的幅值的上下文，KeySignContext是用於讀出nQKey的正負號的上下文。
decodeUnsignedAAC是用於對自適應算術編碼的數據執行無符號解碼處理的函數，decodeSignedAAC是對自適應算術編碼的數據執行有符號解碼處理的函數。
圖28J示出了類PoslKeyValue。參看圖28J，在存儲在PoslKeyValue中的變量中，KeyValue_X，KeyValue_Y和KeyValue_Z分別表示在位置內插器中x、y和z分量的每個分量的密鑰值數據的數組。如果nStartIndex_X被設置為0，則使用算術解碼器從比特流中解碼KeyValue_X
。以相同的方式確定KeyValue_Y
和KeyValue_Z
。當從比特流中算術解碼KeyValue_X
、KeyValue_Y
和KeyValue_Z
時，使用decodeUnaryAAC或decodeSQAAC函數。
上下文模型kVXSignContext、kVYSignContext和kVZSignContext被分別用於解碼KeyValue_X、KeyValue_Y和KeyValue_Z的正負號。上下文模型kVXSignContext、kVYSignContext和kVZSignContext被傳輸給decodeUnaryAAC或decodeSQAAC函數。
MaxValueContext、FoundContext和NotFoundContext被用於熵解碼密鑰值的絕對值。例如，kVXMaxValueContext、kVXFoundContext和kVXNotFoundContext被用於解碼KeyValue_X。MaxValueContext、FoundContext和NotFoundContext被傳輸給decodeUnaryAAC或decodeSQAAC函數。
上下文模型kVXUContext、kVYUContext和kVZUContext被用於解碼KeyValue_X，KeyValue_Y和KeyValue_Z，並被傳輸給decodeUnaryAAC函數。
本發明可以利用寫在計算機可讀記錄介質上的計算機可讀代碼實現。這裡，計算機可讀記錄介質包括任何一種可以被計算機系統讀出的記錄介質。例如，計算機可讀記錄介質包括ROM、RAM、CD-ROM、磁帶、軟盤、光數據存儲器和載波(經過網際網路傳輸)。計算機可讀記錄介質可以被分散到經過網際網路連接的計算機系統中，並且一臺計算機可以以分散的方式閱讀記錄介質。
按照用於編碼本發明的位置內插器的方法和裝置，可以在保持高質量動畫的同時高效率地編碼和解碼密鑰數據和密鑰值數據。另外，通過使用測量在動畫路徑之間的誤差的方法可以保持高質量的動畫數據。此外，通過使用本發明的重取樣方法和斷點提取方法可以明顯減少將被編碼的密鑰數據和密鑰值數據的數量。
儘管本發明是參照其優選實施例來具體描述的，但是本領域的技術人員應該理解，在不脫離由所附權利要求限定的本發明的精神和範圍的情況下，可以對其進行形式和細節的各種修改。
權利要求
1.一種用於對位置內插器進行編碼的裝置，所述位置內插器包括用於指示關鍵幀在時間軸上的位置的密鑰數據和用於指示目標位置的密鑰值數據，該裝置包括一個斷點提取器，用於從由輸入給它的位置內插器構成的第一動畫路徑中提取最小數量的斷點，這些斷點能夠在第一動畫路徑和由所提取的斷點生成的第二動畫路徑之間引起不大於預定的可允許誤差極限的誤差；一個密鑰數據編碼器，用於對從所述斷點提取器輸入的密鑰數據進行編碼；以及一個密鑰值數據編碼器，用於對從所述斷點提取器輸入的密鑰值數據進行編碼。
2.如權利要求1所述的裝置，其中，所述斷點提取器包括一個線性內插器，用於提取輸入動畫路徑的開始路徑點和結束路徑點，在所述開始和結束路徑點之間選擇路徑點，並用所選擇的路徑點和所提取的路徑點對還未被選擇的其他路徑點進行內插；一個誤差計算器，用於計算在輸入動畫路徑和由所述線性內插器利用內插生成的內插動畫路徑之間的誤差；以及一個確定單元，用於提取斷點，利用這些斷點可以使輸入動畫路徑和內插動畫路徑之間的誤差最小，並且如果對應的誤差不大於預定的可允許誤差極限，則輸出所提取的斷點。
3.如權利要求2所述的裝置，其中，如果與所提取的斷點對應的誤差大於預定的可允許誤差極限，則所述確定單元向所述線性內插器輸出所提取的斷點，然後，所述線性內插器通過選擇除從所述確定單元輸入的被提取的斷點以外的路徑點執行內插。
4.如權利要求2所述的裝置，其中，所述誤差計算器根據由兩個動畫路徑的路徑點構成的一個參考分量，將輸入動畫路徑和內插動畫路徑分成預定數量的部分，並通過測量每個部分中的輸入動畫路徑和內插動畫路徑之間的面積，計算在每個部分中的輸入動畫路徑和內插動畫路徑之間的誤差。
5.如權利要求2所述的裝置，其中，所述誤差計算器根據由多個路徑點表示的密鑰數據之間的距離和分別與密鑰數據對應的密鑰值數據之間的距離，測量輸入動畫路徑和內插動畫路徑之間的誤差。
6.如權利要求1所述的裝置，還包括一個重取樣器，用於將所述第一動畫路逕取樣為預定數量的具有預定時間間隔的多個部分，並輸出包括重取樣的密鑰數據和重取樣的密鑰值數據的位置內插器；以及一個選擇器，用於依據外部輸入信號，將輸入給它的位置內插器輸出給重取樣器或斷點提取器。
7.如權利要求6所述的裝置，其中，所述斷點提取器包括一個線性內插器，用於提取輸入動畫路徑的開始路徑點和結束路徑點，在所述開始和結束路徑點之間選擇路徑點，並利用所選擇的路徑點和所提取的路徑點對還未被選擇的其他路徑點進行內插；一個誤差計算器，用於計算輸入動畫路徑和由線性內插器利用內插產生的內插動畫路徑之間的誤差；以及一個確定單元，用於提取斷點，利用這些斷點可以使輸入動畫路徑和內插動畫路徑之間的誤差最小，如果對應的誤差不大於預定可允許誤差極限，則輸出所提取的斷點。
8.如權利要求6所述的裝置，其中，所述重取樣器將由位置內插器的密鑰數據和密鑰值數據構成的動畫路徑分成預定數量的具有預定時間間隔的部分，將每個部分的結束點作為將被編碼的密鑰數據輸出，並將存在於每個部分中的動畫路徑上的密鑰值數據作為將被編碼的密鑰值數據輸出。
9.如權利要求1所述的裝置，還包括一個重取樣器，用於將所述第一動畫路逕取樣為預定數量的具有預定時間間隔的部分，並輸出包括重取樣的密鑰數據和重取樣的密鑰值數據的位置內插器，其中，所述斷點提取器從由從所述重取樣器輸入的位置內插器構成的動畫路徑中提取斷點。
10.如權利要求9所述的裝置，其中，所述斷點提取器包括一個線性內插器，用於提取輸入動畫路徑的開始路徑點和結束路徑點，在所述開始和結束路徑點之間選擇路徑點，並用所選擇的路徑點和所提取的路徑點對還未被選擇的其他路徑點進行內插；一個誤差計算器，用於計算在輸入動畫路徑和由所述線性內插器利用內插生成的內插動畫路徑之間的誤差；以及一個確定單元，用於提取斷點，利用這些斷點可以使輸入動畫路徑和內插動畫路徑之間的誤差最小，並且如果對應的誤差不大於預定可允許誤差極限，則輸出所提取的斷點。
11.如權利要求9所述的裝置，其中，所述重取樣器將由位置內插器的密鑰數據和密鑰值數據構成的動畫路徑分成預定數量的具有預定時間間隔的部分，將每個部分的結束點作為將被編碼的密鑰數據輸出，並將存在於每個部分中的動畫路徑上的密鑰值數據作為將被編碼的密鑰值數據輸出。
12.如權利要求1所述的裝置，還包括一個重取樣器，用於將由從所述斷點提取器提取的位置內插器構成的動畫路逕取樣為預定數量的具有預定時間間隔的部分，並將包括重取樣的密鑰數據和重取樣的密鑰值數據的位置內插器輸出給所述密鑰數據編碼器和密鑰值數據編碼器。
13.如權利要求12所述的裝置，其中，所述斷點提取器包括一個線性內插器，用於提取輸入動畫路徑的開始路徑點和結束路徑點，在所述開始和結束路徑點之間選擇路徑點，並利用所選擇的路徑點和所提取的路徑點對還未被選擇的其他路徑點進行內插；一個誤差計算器，用於計算輸入動畫路徑和由線性內插器利用內插產生的內插動畫路徑之間的誤差；和一個確定單元，用於提取斷點，利用這些斷點可以使輸入動畫路徑和內插動畫路徑之間的誤差最小，檢查對應的誤差是否不大於預定的可允許誤差極限，並且輸出所提取的斷點。
14.如權利要求13所述的裝置，其中，所述重取樣器將由位置內插器的密鑰數據和密鑰值數據構成的動畫路徑分成預定數量的具有預定時間間隔的部分，將每個部分的結束點作為將被編碼的密鑰數據輸出，並將存在於每個部分中動畫路徑上的密鑰值數據作為將被編碼的密鑰值數據輸出。
15.如權利要求1所述的裝置。其中，所述密鑰數據編碼器包括一個量化器，用於利用多個量化比特量化輸入的差分數據；一個DPCM處理器，用於產生量化密鑰數據的差分數據；一個移位器，用於獲得差分數據中具有最高頻率的差分基準點(模式)，並從每個差分數據中減去該模式；一個摺疊處理器，用於將差分數據轉換為正數區域或負數區域；一個DND處理器，用於根據轉換後的差分數據與它們當中的最大和最小值的關係，對轉換後的差分數據執行DND操作，以減少它們的範圍，在從所述移位器輸入的差分數據、從所述摺疊處理器輸入的差分數據和已經被執行了DND操作的差分數據中選擇一個差分數據，並且輸出所選擇的差分數據；以及一個熵編碼器，用於對從所述DND處理器輸入的差分數據進行熵編碼。
16.如權利要求1所述的裝置，其中，所述密鑰值數據編碼器包括一個量化器，用於利用預定的量化比特對輸入給它的數據進行量化；一個DPCM處理器，用於獲得量化數據的差分數據和預測差分數據，並且對差分數據執行循環量化操作，以便輸出減少了尺寸的差分數據；以及一個熵編碼器，用於對從所述DPCM處理器輸入的差分數據進行熵編碼。
17.一種用於對位置內插器進行編碼的裝置，所述位置內插器包括用於指示關鍵幀在時間軸上的位置的密鑰數據和用於指示目標位置的密鑰值數據，該裝置包括一個重取樣器，用於將由密鑰數據和密鑰值數據構成的動畫路逕取樣為預定數量的具有預定時間間隔的部分，並且輸出包括重取樣的密鑰數據和重取樣的密鑰值數據的位置內插器；一個密鑰數據編碼器，用於對從所述重取樣器輸入的密鑰數據進行編碼；以及一個密鑰值數據編碼器，用於對從所述重取樣器輸入的密鑰值數據進行編碼，其中，所述密鑰值編碼器包括一個量化器，用於利用預定的量化比特對輸入給它的數據進行量化；一個DPCM處理器，用於獲得量化數據的差分數據和預測差分數據，並且對差分數據執行循環量化操作，以便輸出減少了尺寸的差分數據；以及一個熵編碼器，用於對從所述DPCM處理器輸入的差分數據進行熵編碼。
18.如權利要求17所述的裝置，其中，所述重取樣器將由位置內插器的密鑰數據和密鑰值數據構成的動畫路徑分成預定數量的具有預定時間間隔的部分，將每個部分的結束點作為將被編碼的密鑰數據輸出，並將存在於每個部分中的動畫路徑上的密鑰值數據作為將被編碼的密鑰值數據輸出。
19.一種用於對比特流進行解碼的裝置，在所述比特流中，包括用於指示關鍵幀在時間軸上的位置的密鑰數據和用於指示目標位置的密鑰值數據的位置內插器被編碼，所述裝置包括一個密鑰數據解碼器，用於對來自輸入比特流的密鑰數據進行解碼；一個密鑰值數據解碼器，用於對來自輸入比特流的密鑰值數據進行解碼；以及一個位置內插器合成器，用於通過合成解碼的密鑰值數據和被用解碼的密鑰值數據線性內插的密鑰值數據，生成位置內插器。
20.如權利要求19所述的裝置，其中，如果不存在與當前正在被執行位置內插器合成的密鑰數據對應的解碼的密鑰值數據，則所述位置內插器合成器使用與在前合成的密鑰數據對應的解碼的密鑰值數據和與下一個將被合成的密鑰數據對應的解碼的密鑰值數據，對與當前正在被執行位置內插器合成的密鑰數據對應的密鑰值數據進行內插。
21.如權利要求19所述的裝置，其中，所述密鑰數據解碼器包括一個熵解碼器，用於通過對輸入比特流進行熵解碼產生差分數據；一個逆DPCM處理器，用於通過對差分數據執行預定的逆DPCM操作，產生量化的密鑰數據；以及一個逆量化器，用於通過對量化的密鑰數據進行逆量化，產生復原的密鑰數據。
22.如權利要求19所述的裝置，其中，所述密鑰值數據解碼器包括一個熵解碼器，用於通過對輸入比特流進行熵解碼產生差分數據；一個逆DPCM處理器，用於通過對差分數據執行預定的逆DPCM操作，產生量化的密鑰值數據；以及一個逆量化器，用於通過對量化的密鑰值數據進行逆量化，產生復原的密鑰值數據。
23.一種用於對位置內插器進行編碼的方法，所述位置內插器包括用於指示關鍵幀在時間軸上的位置的密鑰數據和用於指示目標位置的密鑰值數據，所述方法包括如下步驟(b)通過從由所述位置內插器構成的第一動畫路徑中提取最小數量的斷點產生將被編碼的密鑰數據和密鑰值數據，這些斷點會在所述第一動畫路徑和將通過所提取的斷點產生的第二動畫路徑之間引起一個不大於預定的可允許誤差極限的誤差；(d)對在步驟(b)中產生的密鑰數據進行編碼；以及(e)對在步驟(b)中產生的密鑰值數據進行編碼。
24.如權利要求23所述的方法，其中，步驟(b)包括如下步驟(b1)提取第一動畫路徑的開始路徑點和結束路徑點；(b2)選擇在開始和結束路徑點之間的路徑點，並且用所選擇的路徑點和所提取的路徑點對還未被提取的其他路徑點進行內插；(b3)計算在第一動畫路徑和通過在步驟(b2)中的內插產生的第二動畫路徑之間的誤差；以及(b4)提取多個斷點，利用這些斷點可以使第一動畫路徑與第二動畫路徑之間的誤差最小，如果對應的誤差不大於預定的可允許誤差極限，則確定將被編碼的密鑰數據和密鑰值數據。
25.如權利要求24所述的方法，其中，在步驟(b3)中，根據由第一和第二動畫路徑的路徑點構成的一個參考分量，將第一動畫路徑和第二動畫路徑中的每一個都分成預定數量的部分，並通過測量每個部分中第一動畫路徑和第二動畫路徑之間的面積，計算每個部分中第一動畫路徑和第二動畫路徑之間的誤差。
26.如權利要求25所述的方法，其中，在步驟(b3)中，根據在由路徑點指示的密鑰數據之間的距離和在分別與密鑰數據對應的密鑰值數據之間的距離，測量在第一動畫路徑和第二動畫路徑之間的面積。
27.如權利要求25所述的方法，其中，在步驟(b4)中，如果與所提取的斷點對應的誤差大於預定的可允許誤差極限，則再次執行步驟(b2)到(b4)。
28.如權利要求23所述的方法，還包括(a)在步驟(b)之前，通過將第一動畫路逕取樣為預定數量的具有預定時間間隔的部分，生成包括重取樣的密鑰數據和重取樣的密鑰值數據的位置內插器，其中，在步驟(b)中，從由在步驟(a)中生成的位置內插器構成的動畫路徑中提取斷點。
29.如權利要求28所述的方法，其中，在步驟(a)中，將第一動畫路徑分成預定數量的具有預定時間間隔的多個部分，將每個部分的結束點設置為取樣的密鑰數據，並且將在每個部分中第一動畫路徑上的密鑰值數據設置為取樣的密鑰值數據。
30.如權利要求23所述的方法，還包括(c)通過在步驟(b)之後將用所提取的斷點構成的第二動畫路逕取樣為預定數量的具有預定時間間隔的多個部分，生成將被編碼的密鑰數據和密鑰值數據。
31.如權利要求30所述的方法，其中，在步驟(c)中，將第二動畫路徑分成預定數量的具有預定時間間隔的多個部分，將每個部分的結束點設置為將被編碼的密鑰數據，並且將在每個部分中的第一動畫路徑上的密鑰值數據設置為將被編碼的密鑰值數據。
32.如權利要求23所述的方法，其中，步驟(d)包括如下步驟利用預定數量的量化比特，對密鑰數據進行量化；通過對量化的數據執行預定的DPCM操作產生差分數據；以及對該差分數據進行熵編碼。
33.如權利要求23所述的方法，其中，步驟(e)包括如下步驟利用預定數量的量化比特，對密鑰值數據進行量化；通過對量化的密鑰值數據執行預定的DPCM操作產生差分數據；以及對該差分數據進行熵編碼。
34.一種用於對位置內插器進行編碼的方法，所述位置內插器包括用於指示關鍵幀在時間軸上的位置的密鑰數據和用於指示目標位置的密鑰值數據，所述方法包括如下步驟(b)將由所述位置內插器構成的動畫路逕取樣為預定數量的具有預定時間間隔的部分，並生成包括重取樣的密鑰數據和重取樣的密鑰值數據的位置內插器；(d)對在步驟(b)中生成的密鑰數據進行編碼；以及(e)對在步驟(b)中生成的密鑰值數據進行編碼，其中，步驟(e)包括如下步驟用預定的量化比特，對在步驟(b)中生成的密鑰數據進行量化；獲得差分數據和預測差分數據，並通過對插分數據執行循環量化操作，生成減少了尺寸的差分數據；以及對減少了尺寸的差分數據進行熵編碼。
35.如權利要求34所述的方法，其中，在步驟(b)中，將動畫路徑分成預定數量的具有預定時間間隔的部分，將每個部分的結束點設置為取樣的密鑰數據，並且將在每個部分中的第一動畫路徑上的密鑰值數據設置為取樣的密鑰值數據。
36.一種計算機可讀記錄介質，其中記錄有實現權利要求23所述方法的計算機可讀程序代碼。
37.一種計算機可讀記錄介質，其中記錄有實現權利要求24所述方法的計算機可讀程序代碼。
38.一種計算機可讀記錄介質，其中記錄有實現權利要求28所述方法的計算機可讀程序代碼。
39.一種計算機可讀記錄介質，其中記錄有實現權利要求30所述方法的計算機可讀程序代碼。
40.一種計算機可讀記錄介質，其中記錄有實現權利要求34所述方法的計算機可讀程序代碼。
41.一種用於對比特流進行解碼的方法，在所述比特流中，包括指示關鍵幀在時間軸上的位置的密鑰數據和指示目標位置的密鑰值數據的位置內插器已經被編碼，所述方法包括如下步驟(a)對來自輸入比特流的密鑰數據進行解碼；(b)對來自輸入比特流的密鑰值數據進行解碼；(c)通過合成解碼的密鑰值數據和被用具有解碼的密鑰數據的解碼的密鑰值數據線性內插的密鑰值數據，生成位置內插器。
42.如權利要求41所述的方法，其中，在步驟(c)中，如果不存在與當前正在被執行位置內插器合成的密鑰數據對應的解碼的密鑰值數據，用與在前合成的密鑰數據對應的解碼的密鑰值數據和與下一個將被合成的密鑰數據對應的解碼的密鑰值數據，對與當前正在被執行位置內插器合成的密鑰數據對應的密鑰值數據進行內插。
43.如權利要求41所述的方法，其中步驟(a)包括通過對輸入比特流進行熵解碼，生成差分數據；通過對差分數據執行預定的DPCM操作和逆DND操作，生成量化的密鑰數據；以及通過對量化的密鑰數據進行逆量化，生成復原的密鑰數據。
44.如權利要求41所述的方法，其中步驟(b)包括通過對輸入比特流進行熵解碼，生成差分數據；通過對差分數據執行預定的逆DPCM操作，生成量化的密鑰值數據；以及通過對量化的密鑰值數據進行逆量化，生成復原的密鑰值數據。
45.一種計算機可讀記錄介質，其中記錄有實現權利要求41所述方法的計算機可讀程序代碼。
46.一種計算機可讀記錄介質，其中記錄有實現權利要求42所述方法的計算機可讀程序代碼。
47.一種計算機可讀記錄介質，其中記錄有實現權利要求43所述方法的計算機可讀程序代碼。
48.一種計算機可讀記錄介質，其中記錄有實現權利要求44所述方法的計算機可讀程序代碼。
49.一種方法，用於計算第一路徑和第二路徑之間的誤差，其中，由其中的每一個都包括多個數據分量的多個第一路徑點構成的第一路徑，由其中的每一個都包括多個數據分量的多個第二路徑點構成的第二路徑，該方法包括如下步驟(a)將多個路徑點插入到第一和第二動畫路徑中，從而使第一和第二動畫路徑就包括在每個路徑點中的參考數據分量而言具有相同路徑點；(b)根據參考數據分量，將第一和第二路徑中的每一個分成預定數量的部分，從而使預定數量的部分分別對應於路徑點；(c)計算在每個部分中的第一和第二動畫路徑之間的誤差；以及(d)檢查是否已經對所有預定數量的部分執行了步驟(c)，並對在步驟(c)中得到的誤差進行規範。
50.如權利要求49所述的方法，其中，在步驟(c)中，利用參考數據之間的距離和除參考分量數據以外的分量數據之間的距離，計算在每個部分中的第一和第二路徑之間的誤差。
51.如權利要求50所述的方法，其中，參考分量數據是包括在位置內插器節點中的密鑰數據，並且在步驟(c)中，通過將密鑰數據之間的距離設置為梯形的高度並且將其他分量數據之間的距離設置為梯形的上邊和下邊來計算在每個部分中第一和第二動畫路徑之間的誤差。
52.如權利要求49所述的方法，其中，在步驟(d)中，獲得路徑點的參考分量數據的極值，然後，利用該極值對在步驟(c)中獲得的誤差進行規範。
53.一種計算機可讀記錄介質，其中記錄有實現權利要求49所述方法的計算機可讀程序代碼。
54.一種方法，用於利用線性逼近從由包括多個分量數據的路徑點組成的數據中提取斷點，該方法包括如下步驟(a)提取原始路徑的開始點和結束點；(b)選擇一個未被提取的路徑點，並且利用所選擇的路徑點和所提取的路徑點對其他未被選擇的路徑點進行線性內插；(c)計算原始路徑和利用內插的路徑點生成的內插動畫路徑之間的誤差；(d)對所有未被選擇的路徑點執行步驟(b)和(c)，並提取導致原始動畫路徑和內插路徑之間最小誤差的路徑點；以及(e)將原始路徑和利用包括在步驟(d)中提取的路徑點在內的所提取的路徑點生成的路徑之間的誤差與預定的可允許誤差極限進行比較，然後重複執行步驟(b)到(d)。
55.如權利要求54所述的方法，其中，步驟(c)包括如下步驟(c1)將原始路徑和內插路徑分成預定數量的部分，從而使預定數量的部分分別與路徑點對應；以及(c2)利用每個路徑點的參考分量數據之間的距離和在每個路徑點的其他分量數據之間的距離，計算原始路徑和內插路徑之間的誤差。
56.如權利要求55所述的方法，其中，路徑點對應於表示三維動畫的位置內插器，參考分量數據對應於包括在位置內插器節點中的密鑰數據，並且在步驟(c2)中，通過將密鑰數據之間的距離設置為梯形的高並且將其他分量數據之間的距離設置為該梯形的上邊和下邊，計算在每個部分中的原始動畫路徑和內插動畫路徑之間的誤差。
57.如權利要求55所述的方法，其中，路徑點對應於表示三維動畫的位置內插器，參考分量數據對應於指示關鍵幀在時間軸上的位置的密鑰數據，而其他分量數據對應於指示目標在動畫中的位置的密鑰值數據。
58.一種計算機可讀記錄介質，其中記錄有實現權利要求54所述方法的計算機可讀程序代碼。
59.一種計算機可讀記錄介質，其中記錄有實現權利要求55所述方法的計算機可讀程序代碼。
60.一種方法，用於利用線性逼近從由路徑點構成的動畫路徑中提取斷點，其中，路徑點包括多個關鍵幀在時間軸上的位置和目標在每個關鍵幀中的位置，該方法包括如下步驟(a)提取與原始動畫路徑的開始點和結束點對應的關鍵幀；(b)選擇未被提取的關鍵幀，並且利用所選擇的關鍵幀和所提取的關鍵幀對其他關鍵幀進行線性內插；(c)計算原始動畫路徑和利用內插的關鍵幀生成的內插動畫路徑之間的誤差；(d)對所有未被選擇的關鍵幀執行步驟(b)和(c)，並提取導致原始動畫路徑和內插動畫路徑之間最小誤差的關鍵幀；以及(e)將原始動畫路徑和利用與在步驟(d)中選擇的關鍵幀對應的路徑點生成的動畫路徑之間的誤差與預定的可允許誤差極限進行比較，然後重複執行步驟(b)到(d)。
61.如權利要求60所述的方法，其中，步驟(c)包括如下步驟(c1)將原始動畫路徑和內插動畫路徑分成預定數量的部分，從而使預定數量的部分分別與關鍵幀對應；以及(c2)利用用於分割每個動畫路徑的關鍵幀之間的間隔和關於目標在關鍵幀中的位置的信息段之間的差，計算在原始動畫路徑和內插動畫路徑之間的誤差。
62.如權利要求61所述的方法，其中，在步驟(c2)中，通過將在關鍵幀之間用於分割每個動畫路徑的間隔設置為梯形的高並且將關於目標在關鍵幀中的位置的信息段之間的差分別設置為梯形的上邊和下邊，計算每個部分中原始動畫路徑和內插動畫路徑之間的誤差。
63.一種比特流，在所述比特流中，對包括指示關鍵幀在時間軸上的位置的密鑰數據和指示目標位置的密鑰值數據的位置內插器進行編碼，所述比特流包括對密鑰數據進行編碼/解碼所需的密鑰數據編碼/解碼信息；以及對密鑰值數據進行編碼/解碼所需的密鑰值數據編碼/解碼信息，其中，密鑰數據編碼/解碼信息包括逆DND操作信息，包括說明將要對差分數據執行預定數量的逆DND循環的逆DND的階數和在逆DND操作的每個循環中使用的差分數據當中的最大和最小值，其中，差分數據是通過對該比特流進行熵解碼生成的，以便擴展差分數據的範圍；第一逆DPCM操作信息，包括將要對經過逆DND的差分數據執行的逆DPCM操作的階數，對經過逆DND的差分數據執行的逆DPCM操作，從而將經過逆DND的差分數據轉換為量化密鑰數據和用於逆DPCM操作的每個循環的內部密鑰數據；以及第一逆量化信息，用於在逆量化中通過對量化密鑰數據執行逆量化，生成復原的密鑰數據，並且密鑰值數據編碼/解碼信息包括熵解碼信息，包括一個標記，用於指示將被執行的熵解碼操作，通過對來自比特流的密鑰值數據執行熵解碼操作，生成第二插分數據；第二逆DPCM操作信息，包括關於對差分數據執行逆DPCM操作以便在逆DPCM操作的每個循環中將第二差分數據轉換為量化的密鑰值數據和內部密鑰值數據的信息；第二逆量化信息，包括用於通過對量化的密鑰值數據進行逆量化，復原原始密鑰值數據的預定數量的逆量化比特；和逆規範信息，用於對通過利用逆量化比特進行逆量化而被復原的復原密鑰值數據進行逆規範，逆規範信息包括說明具有最大密鑰值數據範圍的分量的標記、在最大密鑰值數據範圍中的最大值和在每個分量的密鑰值數據當中的最小值。
64.如權利要求63所述的比特流，其中，逆DND操作信息還包括一個標記，用於說明是否對將被執行逆DND操作的差分數據執行下移位操作。
65.如權利要求63所述的比特流，其中，第一量化信息包括用於對量化密鑰數據和量化密鑰數據當中的最大和最小值進行逆量化的逆量化比特尺寸。
66.如權利要求65所述的比特流，其中，量化密鑰數據當中的最大和最小值被用於使量化的密鑰數據的量化誤差最小。
67.如權利要求63所述的比特流，其中，密鑰數據編碼/解碼信息還包括用於對在比特流中的、密鑰數據線性增加的線性密鑰區域進行解碼的線性密鑰解碼信息，該線性密鑰解碼信息包括用於說明在整個密鑰數據範圍中是否存在線性密鑰區域的標記、包括在線性密鑰區域中的密鑰數據的數量以及線性密鑰區域的開始和結束密鑰數據。
68.如權利要求63所述的比特流，其中，密鑰值數據編碼/解碼信息還包括被包括在比特流中的、經過編碼的密鑰值數據的數量和密鑰值數據的最大數位。
69.如權利要求63所述的比特流，其中，第二逆量化信息包括在每個分量的密鑰值數據當中的、用於使量化的密鑰值數據的量化誤差最小的最小值。
全文摘要
提供了一種用於對包括密鑰數據和密鑰值數據的位置內插器進行編碼和解碼的方法和裝置。用於對位置內插器進行編碼的方法包括(b)通過從由位置內插器構成的第一動畫路徑中提取最小數量的斷點，生成將被編碼的密鑰數據和密鑰值數據，這些斷點可以在第一動畫路徑和將由所提取的斷點生成的第二動畫路徑之間引起不大於預定的可允許誤差極限的誤差；(d)對在步驟(b)中生成的密鑰數據進行編碼；以及(e)對在步驟(b)中生成的密鑰值數據進行編碼。
文檔編號H04N7/32GK1432971SQ0215429
公開日2003年7月30日 申請日期2002年11月27日 優先權日2001年11月27日
發明者金道均, 鄭錫潤, 張義善, 禹相玉, 李信俊, 韓萬鎮, 張敬子 申請人:三星電子株式會社