三維對象形變信息的編碼方法和裝置的製作方法
2023-05-09 07:53:51
專利名稱：三維對象形變信息的編碼方法和裝置的製作方法
技術領域：
本發明涉及數據壓縮，並且更特別地涉及3維(3D)對象形變信息的編碼方法和裝置。
背景技術：
3維(3D)表示已知用於例如計算機系統的計算機遊戲或虛擬實境世界環境中。在3維模型的情況下，虛擬實境建模語言(VRML)已經成為表示3維對象的主要方式。
在VRML中，3維對象以多邊形網格的形式表示，對象的動畫通過線性鍵控成幀(linear key framing)方法實現。在這種動畫方法中，在任意的時間軸上設置預定的鍵架(key frame)，並且每個鍵架之間的動畫數據通過線性插值方法來插值。這種方法中使用的鍵架由插值節點確定，其中插值節點由現場數據(field data)形成，表示為在時間軸上指示鍵架位置的鍵碼數據，和在相應鍵碼上指示鍵架屬性信息的鍵值(key value)數據。
同時，當與實際移動主體相似的平滑動畫，由鍵控成幀方法表示時，其中鍵控成幀方法具有分段線性插值的特點，大量的鍵架信息應該通過插值節點提供，這促使產生成本和效率上的嚴重問題。當離線使用鍵控成幀方法時，需要大容量的存儲裝置來存儲大量的3D動畫數據。當在線使用鍵控成幀方法時，除了大容量的存儲裝置，3D動畫數據從伺服器到終端的傳輸，需要很高的速度和大容量傳輸路徑，並且與傳輸誤差概率的增加一致，數據可靠性降低。由此，需要有效的壓縮和編碼方法，來減少插值節點數據的量。
為此，使用了差分脈碼調製(DPCM)編碼方法，如
圖1所示。在DPCM方法中，只有數據的差分值被編碼，從而位數減少。DPCM方法用於壓縮與鍵控成幀方法相關的數據。同樣，DPCM方法用於MPEG-4畫面二進位格式(BIFS)。
參考圖1，語法分析程序105識別被編碼的插值節點的數據信息。多路分解器110將插值器節點中被編碼的插值器節點的現場數據分類。更特別地，多路分解器從語法分析程序105接收一個坐標插值器(CI)節點，並且輸出對應於該節點的一個鍵碼(QK)和鍵值(QKV)形成的現場數據。DPCM處理器120接收該CI節點的現場數據，將所述鍵碼和鍵值分開，並且通過產生相鄰鍵碼和鍵值數據的每個差分值(EK，EKV)，去掉數據中的時間冗餘。
圖2是圖1的DPCM處理器的具體圖。參考圖2，當產生當前被編碼的值的差分值時，反向量化器122使時間軸上先前的數據，與解碼裝置150中重建的值相同。
再次參考圖1，量化器130接收這樣產生的差分值(EK，EKV)，並且判斷被編碼數據表示的精度等級，從而提供數據壓縮效率。熵編碼器135接收量化器130中量化的值 去掉與符號發生的概率相關的冗餘，並且產生壓縮的位流140。圖1的編碼裝置100產生的位流140被重建為CI節點，它通過解碼裝置150編碼，其中解碼裝置150執行編碼裝置100執行過程的反向過程。
然而，在去掉插值器節點的現場數據中存在的數據冗餘時，具有上述結構的編碼裝置100和解碼裝置150，只去掉相應於形成3D對象形狀的頂點空間關係的數據冗餘。這樣，一點也不考慮相應於時間相關性的數據冗餘，其中主要在鍵控成幀類型的動畫中發生時間相關性，由此難於提高實際壓縮效率。
發明內容
為了解決上述問題，本發明的第一個目的是提供一種編碼方法和裝置，用於相應於時間和被編碼的3D對象的形變信息，使用空間時間數據相關性，來去掉數據冗餘。
本發明的第二個目的是提供一種編碼方法和裝置，用於相應於時間和被編碼的3D對象的形變信息，產生開始頂點，開始頂點產生符合頂點連接性信息的BFS信息。
本發明的第三個目的是提供一種編碼方法和裝置，用於相應於時間和被編碼的3D對象的形變信息，補償編碼中的量化誤差。
為了實現本發明的目的，這裡提供了一種3維(3D)對象形變信息的編碼方法，其中形成3D對象形狀的頂點信息，由執行3D對象形變的鍵控成幀方法描述，這種編碼方法包括(a)通過語法分析3D對象的節點信息，提取鍵碼，指示時間軸上鍵架的位置；鍵值，指示鍵架的特性信息；和關係信息；(b)從相關信息中產生頂點連接性信息；(c)根據頂點連接性信息，對於去掉時間數據冗餘的每個鍵碼，和去掉空間時間數據冗餘的鍵值，產生差分值；(d)將差分值量化；和(e)通過接收量化的鍵碼和鍵值，去掉位中的冗餘，並且通過熵編碼產生壓縮的位流。
為了實現本發明的另一個目的，這裡提供了一種3維(3D)對象形變信息的編碼方法，其中形成3D對象形狀的頂點信息，由執行3D對象形變的鍵控成幀方法描述，編碼方法包括(a)通過語法分析3D對象的節點信息，提取鍵碼，指示時間軸上鍵架的位置；鍵值，指示鍵架的特性信息；和關係信息；(b)從相關信息中產生頂點連接性信息；(c)將鍵碼和鍵值量化；(d)根據頂點連接性信息，對於去掉時間數據冗餘的每個鍵碼，和去掉空間時間數據冗餘的鍵值，產生差分值；和(e)通過接收量化的鍵碼和鍵值，去掉位中的冗餘，並且通過熵編碼產生壓縮的位流。
為了實現本發明的另一個目的，這裡提供了一種3維(3D)對象形變信息的編碼方法，其中形成3D對象形狀的頂點信息，由執行3D對象形變的鍵控成幀方法描述，編碼方法包括(a)通過語法分析3D對象的節點信息，提取鍵碼，指示時間軸上鍵架的位置；鍵值，指示鍵架的特性信息；和關係信息；(b)產生寬度優先搜索(BFS)的搜索開始信息，用於確定3D對象頂點中的空間數據相關性；(c)從步驟(a)提取的相關信息和步驟(b)產生的搜索開始信息中，產生頂點連接性信息；(d)根據頂點連接性信息，對於去掉時間數據冗餘的每個鍵碼，和去掉空間時間數據冗餘的鍵值，產生差分值；(e)將差分值量化；(f)接收量化的鍵碼和鍵值，並且產生鍵值的位編碼的量化級；和(g)通過接收量化的鍵碼和鍵值，接收位編碼並且去掉量化值的位中冗餘的量化級，並且通過熵編碼產生壓縮的位流。為了實現本發明的另一個目的，這裡提供了一種3維(3D)對象形變信息的編碼方法，其中形成3D對象形狀的頂點信息，由執行3D對象形變的鍵控成幀方法描述，編碼方法包括(a)通過語法分析3D對象的節點信息，提取鍵碼，指示時間軸上鍵架的位置；鍵值，指示鍵架的特性信息；和關係信息；(b)產生寬度優先搜索(BFS)的搜索開始信息，用於確定3D對象頂點中的空間數據關係；(c)從步驟(a)提取的相關信息和步驟(b)產生的搜索開始信息中，產生頂點連接性信息；(d)將鍵碼和鍵值量化；(e)根據頂點連接性信息，對於去掉時間數據冗餘的每個量化的鍵碼，和去掉空間時間數據冗餘的量化的鍵值，產生差分值；(f)接收差分值，並且產生鍵值的位編碼的量化級；和(g)接收位編碼並且去掉量化值的位中冗餘的量化級，並且通過熵編碼產生壓縮的位流。為了實現本發明的另一個目的，這裡提供了一種3維(3D)對象形變信息的編碼裝置，其中形成3D對象形狀的頂點信息，由執行3D對象形變的鍵控成幀方法描述，編碼裝置具有現場數據輸入單元，通過語法分析3D對象的節點信息，提取鍵碼，指示時間軸上鍵架的位置；鍵值，指示鍵架的特性信息；和關係信息；頂點連接性處理單元，用於從相關信息中產生頂點連接性信息；自適應差分脈碼調製(ADPCM)處理單元，根據相關信息和頂點連接性信息，對於去掉時間數據冗餘的每個鍵碼，和去掉時間空間數據冗餘鍵值，產生差分值；量化單元，用於將差分值量化，並且輸出差分值；和熵編碼單元，用於接收量化的鍵碼和鍵值，並且去掉位中的冗餘。
為了實現本發明的另一個目的，這裡提供了一種3維(3D)對象形變信息的編碼裝置，其中形成3D對象形狀的頂點信息，由執行3D對象形變的鍵控成幀方法描述，編碼裝置具有現場數據輸入單元，通過語法分析3D對象的節點信息，提取鍵碼，指示時間軸上鍵架的位置；鍵值，指示鍵架的特性信息；和關係信息；量化單元，用於將鍵碼和鍵值量化；自適應差分脈碼調製(ADPCM)處理單元，用於根據相關信息和頂點連接信息，產生去掉時間數據冗餘的量化鍵碼的插分值，和去掉時間空間數據冗餘的量化鍵值的差分值；熵編碼單元，用於去掉位中的冗餘。
附圖的簡要描述通過參考附圖具體描述本發明的優選實施例，上述的目的和優點將變得更明顯，其中圖1是一種編碼裝置和解碼裝置的方塊圖，其中應用了增量脈碼調製(DPCM)；圖2是圖1的DPCM處理器的詳圖；圖3是根據本發明第一實施例的編碼裝置和解碼裝置的示意性方塊圖，它考慮了時間空間數據相關性；圖4是圖3編碼裝置的編碼方法的流程圖；圖5說明了形成圖3的頂點連接性處理單元的BFS圖的方法；圖6是圖3的自適應增量脈碼調製(ADPCM)處理單元的優選實施例的具體方塊圖；圖7是圖6的差分值產生器的優選實施例的具體方塊圖；圖8說明了用於得到圖7頂點間差分值產生器的鍵值的差分值的計算方法鍵值；圖9說明了用於提取圖6預測器的數據冗餘的預測方法；圖10是圖3的編碼裝置產生的位流結構例子的圖；圖11是寬度優先搜索(BFS)圖的結構例子的圖；圖12是根據本發明第二實施例的編碼裝置和解碼裝置的示意性方塊圖，其中補償了量化誤差；圖13是流程圖，用於解釋圖12的編碼裝置的編碼方法；圖14是圖12的ADPCM處理單元優選實施例的具體方塊圖；圖15說明了預測方法，用於提取圖14預測器的數據冗餘；圖16是圖14的DPCM處理器的優選實施例的方塊圖，其中補償了量化誤差；圖17是根據本發明第三實施例的編碼裝置和解碼裝置的方塊圖，它具有產生開始節點的功能；圖18是根據本發明第四實施例的編碼裝置和解碼裝置的方塊圖，其中補償了量化誤差；圖19是流程圖，用於解釋產生圖17和18的搜索開始節點產生器的搜索開始節點的方法；圖20是圖17和18的位編碼量化級產生單元的具體方塊圖；圖21是流程圖，用於解釋通過圖20的量化級產生器執行的量化級計算方法；而圖22是圖17和18的編碼裝置產生的位流結構例子的圖。
優選實施例的具體描述在被編碼的3D對象的形變信息相應於時間編碼的過程中，通過使用時間空間相關性去掉數據冗餘。這裡，通過確定形成3D對象形狀的頂點的連接性，得到時間空間相關性。使用寬度優先搜索(BFS)方法確定連接性，如圖11所示。同樣，相應於BFS確定的頂點中的相關性，通過重建時間軸上鍵值的改變程度特性值的方法，確定時間數據相關性，這通過根據鍵架方法的鍵碼確定，其中鍵架方法具有分段精確線性插值特性。在本發明的BFS開始時，搜索允許更有效編碼的開始頂點(Start)，並且使用搜索開始頂點，產生更有效的BFS圖。這樣，CI節點的鍵值被有效編碼。此外，在本發明中，通過防止頂點中量化誤差的累加，排除相應的頂點，在3D對象的解碼中，防止對象的每部分分開重建。由此，在表示為多邊形網格或參數網格的3D對象中，3D圖形動畫數據的大量鍵值信息可以被有效壓縮、編碼並解碼，其中隨著時間的流逝，這些鍵碼數據作為3D對象的形變信息提供。
根據本發明第一優選實施例和第二優選實施例的編碼和解碼裝置的整個結構，分別在圖3和12中顯示。根據本發明第三優選實施例和第四優選實施例的編碼和解碼裝置的整個結構，分別在圖17和18中顯示。如後面所解釋的，在表示3D形狀和量化單元位置的方法中，發現了圖3與12的兩個系統之間的功能特性，或圖17與18的兩個系統之間的功能特性。
圖3是根據本發明第一優選實施例的編碼裝置和解碼裝置的示意性方塊圖，它考慮了時間空間數據相關性，並且圖4是流程圖，用於解釋圖3編碼裝置的編碼方法。
參考圖3和4，本發明第一優選實施例的編碼裝置200包括語法分析程序205、多路分解器210、頂點連接性處理單元215、自適應差分脈碼調製(ADPCM)處理單元220、量化單元230和熵編碼單元235。為了執行編碼處理的反向處理，解碼裝置250包括熵解碼單元255、多路分解器260、頂點連接性處理單元265、反向量化單元270、反向ADPCM處理單元275和緩衝器280。這裡，解碼裝置250執行編碼裝置200中執行的編碼過程的反向過程。由此，為了簡短起見，將只解釋編碼裝置200的編碼操作。
首先，在步驟2050中，編碼裝置200通過語法分析程序205將3D對象的節點信息語法分析，並且提取鍵碼、鍵值和相關信息。語法分析程序205通過語法分析被編碼的3D對象的節點信息，將坐標插值器(CI)節點和加索引的端面接收器(IndexFaceSet)(IFS)節點分類。在本發明中，考慮了將CI節點編碼。CI節點用於對3D對象的頂點信息提供形變功能，如變形性(MORPHING)。多路分解器210接收分離的CI節點和IFS節點，並將它們提供給頂點連接性處理單元215和ADPCM處理單元220。這裡，提供IFS節點，作為產生CI節點第一鍵架的差分信息而被參考的信息。通過這樣做，在每個CI節點的第一鍵碼位置確定的鍵架的數據量有效減少，因為CI節點和IFS節點具有1∶1對應。
為了在頂點中產生連接性信息，在步驟2150，頂點連接性處理單元215從多路分解器210接收IFS節點的CoordIdx(CIdx)現場數據，並且形成BFS信息。在ADPCM處理單元220的頂點中，BFS信息用於確定空間相關性。
如圖11所示，BFS信息重新確定3D對象的形式信息，其中3D對象具有BFS類型圖結構那樣的多邊形網格結構。BFS信息將任意頂點附近的所有頂點，形成為子節點，從而表示空間數據相關性。這樣，當3D對象在時間軸上形變時，確定的空間數據相關性可以用於有效地去掉編碼中的數據冗餘，其中使用3D空間中相鄰頂點具有相似的移動向量的特點，進行編碼。
ADPCM處理單元220從多路分解器210接收頂點連接性處理單元215中產生的BFS信息、相應於CI節點的鍵碼(QK)和鍵值(QKV)和IFS節點的坐標(Coord)。然後，在步驟2200，ADPCM處理單元220產生去掉時間數據冗餘的每個鍵碼的差分值(EK，EKV)，和去掉時間空間數據冗餘的鍵值。這樣，在編碼裝置200中編碼的頂點位置值被轉換成差分值，從而去掉時間空間數據冗餘，並且輸入量化單元230。在步驟2300，量化單元230相應於量化尺寸值，調整鍵值數據的表示精度等級，從而提供實際數據壓縮效率。量化的結果值 被輸入到ADPCM處理單元220和熵編碼單元235。在步驟2350，熵編碼單元235使用位符號發生的概率，去掉量化值中的位冗餘，並且產生最終位流240。
在這個編碼過程中，如果量化前鍵值的差分值被量化，然後重建，那麼會在每個重建的頂點中，發生由於量化誤差導致的位置改變。由此，3D對象的每部分可以被重建為這樣的形狀，其中每部分從其它部分分離。通過將量化值的差分值編碼，可以防止這個分離重建，如圖12所示。
圖5說明了根據圖3頂點連接性處理單元的優選實施例的處理過程。參考圖5，在步驟2152，頂點連接性處理單元215接收指示網格結構的形狀的CIdx信息，將CIdx信息存儲在隊列中，並且在步驟2153，根據每個頂點是否通過隊列被訪問，來產生BFS圖。這時，在步驟2155，為了產生最終BFS信息，頂點連接性處理單元125管理隊列，並且在步驟2151和2154，管理是否通過隊列訪問每個頂點的信息。這裡，根據BFS搜索順序，優先訪問的頂點被確定為『-1』，作為頂部頂點。這樣，形成圖11所示的BFS圖。
圖6是圖3的ADPCM處理單元220的優選實施例的具體方塊圖。參考圖6，ADPCM處理單元220包括差分值產生器221、預測器222、多路複合器223、鍵碼的DPCM處理器228和鍵值的DPCM處理器229。差分值產生器221確定所有位置值中的差分值 其中當任意頂點隨時間改變時，得到這些差分值。
圖7是圖6差分值產生器的優選實施例的具體方塊圖。參考圖7，差分值產生器221包括第一計算器2211、第二計算器2212和頂點間差分值產生器2213。第一計算器2211計算鍵碼數據項的數量(nKey)，而第二計算器2212計算IFS節點中存在的頂點的總數量(nV)。使用這些數量，如後面計算鍵值的差分值。
圖8說明了一種用於得到圖7頂點間差分值產生器的鍵值的差分值的計算方法，。參考圖8，在步驟22131，頂點間差分值產生器2213根據頂點連接性處理單元215確定的BFS信息，接收頂點形成信息，並且確定任意第i個頂點 附近的頂點(V)。然後，在根據BFS搜索順序訪問的頂點中，在步驟22132計算3D空間中沿時間軸改變的所有位置值的差分值。在步驟22134和22135，產生差分值，從中去掉了時間區中的數據冗餘。特別在步驟22134，通過使用首先在時間軸上產生的鍵架，作為IFS節點確定的頂點差分的比較值，提高了編碼效率。
再次參考圖6，預測器222接收差分值產生器221產生的差分值，並且提取由於頂點中的空間相關性導致的數據冗餘，其中頂點形成3D對象的形狀。
圖9說明了預測方法，用於提取圖6預測器的數據冗餘。參考圖9，在步驟2221，預測器222優先訪問根據頂點連接性處理單元215確定的BFS搜索順序的頂點，並且確定訪問的第i個頂點附近的頂點(V)。與步驟2221搜索的頂點具有高度空間相關性的頂點，在步驟S2222被確定為BFS搜索順序的頂部頂點b。然後，計算兩個頂點b的3D空間位置值的差分值 它們具有高的空間相關性，並且分別在步驟2221和步驟2222中確定，從而在步驟2225去掉空間數據冗餘。
這時，通過差分值產生器221輸入的差分值，被不改變地用作根據BFS順序優先訪問的頂點。在步驟S2226，從步驟2225得到的3D空間位置值的差分值 中，確定每個部分的最大值和最小值(Max，Min)。最大值和最小值輸入量化單元230，並且用在量化所需的標準化處理中。
這樣，去掉時間空間數據冗餘的鍵值數據的差分值(EKV)，被輸入到DPCM處理單元229，如圖6所示，並且DPCM處理結果值輸出到量化單元230。
作為上述鍵值數據的差分值(EKV)，通過圖6的DPCM處理器228，提供使用時間數據相關性去掉數據冗餘的鍵碼(EK)，其中時間數據相關性在鍵控成幀類型動畫方法中提供。然後，量化單元230通過調整數據表示精度等級，來壓縮數據，並且熵編碼單元235去掉壓縮數據的位冗餘，並形成位流240。
圖10是圖3編碼裝置產生的位流結構的例子圖。由圖10的參考數字2400、2405和2410指示的信息項，是一個CI節點處理單元編碼的位流的部分。頭信息2400作為反向量化單元270執行的反向量化條件提供，從而在解碼裝置250中重建CI節點。作為優選的例子2425，頭信息2400包括鍵碼的量化尺寸(Qstep_K)，鍵值的量化尺寸(Qstep_KV)，和最小值(MinX，MinY和MinZ)和最大值(MaxX，MaxY和MaxZ)，它們用於將量化單元230的差分值標準化為0和1之間的值，包含0和1。
鍵碼信息2405提供時間軸上鍵碼數據插分的量化值。形成鍵碼信息2405，作為優選的例子2405。這裡，Klast是1位指示符，用於對解碼裝置250指示鍵碼數據項的數量。如果Klast為『0』，那麼下一個數據項為鍵碼數據項，而如果Klast為『1』，那麼下一個數據項為鍵值數據項。
提供鍵值信息2410作為優選例子2415，其中形成鍵架的所有頂點的位置值，以BFS搜索順序布置，鍵架符合時間軸上順序發生的每個鍵碼。這裡，當數據在熵編碼單元235中處理時，BFS搜索順序中的頂點布置用於提高位之間的相關性。同樣，在例子2415中以鍵碼順序布置鍵值信息項，用於使延遲時間的發生最小化，直到位流2415重建時導致重建結構為止，並且使解碼裝置250的內存使用最小化。
再次參考圖3，通過上述編碼過程產生的位流240，可以通過編碼過程的反向過程來重建。這裡，編碼裝置250應該通過多路分解器260接收IFS節點信息，從而重建每個節點第一鍵碼的鍵架，並且產生表示3D對象空間相關性的BFS信息。
根據本發明的編碼和解碼過程的主要特性包括去掉由於3D對象形變信息的時間空間相關性導致的數據冗餘；並且使用鍵控成幀動畫方法中提供的IFS節點與CI節點之間的對應性，減少被編碼的數據量。
如上所述，圖3和4的本發明第一優選實施例的編碼裝置和方法，在減少被編碼的數據量方面，這裡提供了一種優於現有技術的性能。然而，如上所述，在將多個部分形成的3D對象的編碼和解碼過程中，由於量化誤差導致的每個重建頂點的位置改變，可以促使產生重建的形狀，其中對象的每個部分從其它部分分離。
為了解決這個問題，在本發明中，這裡提供了一種ADPCM處理前量化數據的編碼方法和裝置，如圖12和13所示。圖12是根據本發明第二優選實施例的編碼裝置300和解碼裝置400的示意性方塊圖，其中補償了量化誤差，並且圖13是流程圖，用於解釋圖12的編碼方法和編碼裝置。
參考圖12，根據本發明第二優選實施例的編碼裝置包括現場數據輸入單元，具有語法分析程序305和多路分解器310；頂點連接性處理單元315；量化單元330；ADPCM處理單元330；和熵編碼單元335。為了執行編碼過程的反向過程，解碼裝置350包括熵解碼單元355、多路分解器360、頂點連接性處理單元365、反向DPCM處理單元370、反向量化單元375和緩衝器380。這裡，語法分析程序305、多路分解器310和頂點連接性處理單元315的功能和程序，與圖3的相同，其解釋將被省略。
參考圖13，現在解釋編碼裝置300的操作。優先在步驟3050，編碼裝置300將3D對象的節點信息語法分析，並且提取鍵碼、鍵值和相關信息。然後在步驟3150產生頂點連接性信息。下面，在步驟3200，量化單元320接收由CI節點的鍵碼和鍵值所形成的現場數據，其中CI節點在多路分解器310中分類，並且將數據量化而不差分。
在步驟3300，ADPCM處理單元330接收CI節點這樣量化的鍵碼和鍵值，BFS信息和Coord信息，並且產生差分值，從而去掉現場數據中的時間空間數據冗餘。在圖3中，在步驟3350，ADPCM的差分結果被發送到量化單元230，但不像圖3，圖13的ADPCM差分結果被發送到熵編碼單元335，然後形成最終位流340。
圖14是圖12的ADPCM處理單元優選實施例的方塊圖。與圖6的ADPCM處理單元相比，圖12的ADPCM處理單元330的預測器332，不具有確定量化中所需頂點的每個X、Y、Z坐標的空間預測差分值的最大值和最小值(Max，Min)的功能。由此，差分值計算器331的具體處理與圖7中的相似，但預測器332，也就是空間預測差分值產生器，不產生量化所需的每個部分的最大值和最小值(Max，Min)，因為預測器332使用量化單元320中量化的數據值。
圖15說明了預測方法，用於提取圖14預測的數據冗餘。參考圖15，預測方法與圖9的預測方法相同，除了步驟2226。由此，為了簡單起見，圖15中顯示的預測方法將被省略。
圖16是圖14的DPCM處理器338和339優選實施例的方塊圖，其中補償了量化誤差。參考圖16，每個DPCM處理器338和339將DPCM結果提供給熵編碼單元335，並且形成最終位流340，不像圖6，其中DPCM結果發送到量化單元320。這時，這樣形成的位流340具有與圖10實際上相同的結構。同樣，通過上述編碼過程的反向過程，位流340在圖12的解碼裝置350中重建為CI節點。
CI節點在差分前這樣量化的鍵碼和鍵值具有後面的效果。形成被編碼的3D對象形狀的所有頂點位置值，這裡提供了一種位置值在3D空間中已經移動與量化誤差相同距離的狀態，由此不將量化誤差傳遞到其它相鄰的頂點。
由此，在解碼過程中，不發生當前頂點以外其它頂點中的量化誤差累加，由此當解碼多個部分形成的3D對象時，防止對象的每部分從其它部分分離的分離重建結構。這時，壓縮效率實際上與圖3中的相同。
這樣，根據本發明第一和第二優選實施例的編碼裝置200和300和解碼裝置250和350，使用頂點連接性處理單元215、315、265和365，有效地將CI節點的鍵碼數據和鍵值數據編碼。這裡，輸入到熵處理單元的數據被編碼為鍵值的量化位，其中在熵編碼之前給出鍵值。在這種方法中，由於通過使用時間空間數據相關性執行編碼，數據的離散度降低，並且數據的分布範圍同樣變窄。由此，熵編碼中鍵值位編碼的量化級，可以減少位編碼，足以表示數據的分布範圍。由此，不丟失量化數據，通過使用位編碼所需的量化級，提高編碼效率，而可以減少被存儲的數據量。
然而，在上述方法中，不考慮BFS搜索中選擇開始頂點的方法，用於形成將鍵值數據編碼的BFS圖。由此，優先搜索任意索引或第一索引的頂點。這是搜索任意頂點而不考慮3D對象結構的方法。由此，需要選擇開始頂點的有效方法。
現在解釋根據本發明第三和第四優選實施例的編碼裝置和解碼裝置，它們改善了將CI節點數據中的鍵值數據壓縮和編碼的方法。
圖17是根據本發明第三優選實施例的編碼裝置和解碼裝置的方塊圖，它們具有產生開始節點的功能，而圖18是根據本發明第四優選實施例的編碼裝置和解碼裝置的方塊圖，其中補償了量化誤差。
參考圖17，根據本發明第三實施例的編碼裝置包括現場數據輸入單元，具有語法分析程序405和多路分解器410；開始頂點產生器412；頂點連接性處理單元415；ADPCM處理單元420；量化單元430；鍵值位編碼產生單元432和熵編碼單元435。為了執行編碼裝置400的編碼過程的反向過程，解碼裝置450包括熵解碼單元455、多路分解器460、開始頂點產生器462、頂點連接性處理單元465、反向量化單元470、反向ADPCM處理單元475和緩衝器480，這裡，與圖3的編碼裝置300的模型相比，除了開始頂點產生器412和462，和鍵值編碼位產生器432。編碼裝置400的模型具有相同的功能和結構，現在解釋編碼裝置400中執行的編碼操作。
多路分解器410接收語法分析程序405中分類的CI節點和IFS節點，並且將節點提供給ADPCM處理單元420和開始頂點產生器412。頂點連接性處理單元415從開始頂點產生器412接收IFS節點的CIdx現場數據和開始頂點信息(Start)，並且形成BFS信息。
ADPCM處理單元420接收頂點連接性處理單元415中產生的BFS信息，和符合IFS節點的CI節點和Coord信息的鍵碼(QK)和鍵值(QKV)，其中IFS節點由多路分解器410提供。然後，ADPCM處理單元420對量化單元430，產生去掉時間數據冗餘的鍵碼，和去掉時間空間數據冗餘的鍵值的每個差分值(EK，EKV)。通過調整鍵值數據相應於量化尺寸值的表示精度等級，量化單元430將數據壓縮。量化的結果值 輸入到ADPCM處理單元420和熵編碼單元435。響應量化結果值 編碼位產生單元432產生位編碼的量化級(Qstep_X，Qstep_Y，Qstep_Z)。位編碼產生的量化級(Qstep_X，Qstep_Y，Qstep_Z)輸入到熵編碼單元435。響應量化級(Qstep_X，Qstep_Y，Qstep_Z)，熵編碼單元435使用位符號發生的概率，去掉量化值 中的位冗餘，並且形成最終位流(壓縮的位流)440。
如上所述，圖3和12的編碼裝置200和300任意索引的頂點或第一索引的頂點開始搜索。與此不同，根據本發明第三優選實施例的編碼裝置400，這裡提供了一種有效的開始頂點。也就是，在開始BFS搜索時，編碼裝置400找到允許更有效地編碼開始頂點(Start)，並且使用它更有效地產生BFS圖。
然而，在編碼裝置400中，被編碼的頂點的位置值在量化前轉換為差分值，從而減少數據冗餘，由此，當差分值量化並重建時，會發生每個重建的頂點的位置改變。這會促使分離的重建，其中對象的每一個部分從其它部分分離。為了減少量化誤差，在本發明中，這裡提供了一種用於減少量化誤差的編碼裝置500和解碼裝置550，如圖18所示。如上所述，通過使用已經量化的值之間的差分值，可以防止量化誤差。對此，圖18的編碼裝置500具有ADPCM處理單元530和量化單元520，其中放置次序是圖17的ADPCM處理單元420和量化單元430的顛倒，並且圖18的解碼裝置550具有反向ADPCM處理單元570和反向量化單元575，其中放置次序是圖17的反向ADPCM處理單元475和反向量化單元470的顛倒。同樣，與圖12的編碼裝置300和解碼裝置350的模塊相比，圖18的編碼裝置500和解碼裝置550的模塊具有相同的功能和結構，除了只在圖18中包括的開始頂點產生器512和562和鍵值位編碼產生器532。由此，相同模塊的解釋將被省略。
圖19是流程圖，用於解釋產生圖17和18的開始頂點產生器的搜索開始頂點。參考圖19，在步驟S4121，每個開始頂點產生器412和512優先接收頂點中的連接性信息(CIdx)，並且得到連接到所有頂點的每個上的頂點的數量(頻率(CIdxi))，並且在步驟S4122，得到頂點中具有最多連接頂點的頂點索引。然後，在步驟4123，得到索引的頂點作為開始頂點(Start)輸出。這個開始頂點(Start)用作BFS搜索的開始頂點。
通常，相鄰的頂點具有相似的移動向量。頂點具有越多的相鄰頂點，當頂點發生改變時，頂點對相鄰頂點具有越大的影響。由此，當對相鄰頂點具有最大影響的頂點被選擇為開始頂點時，BFS搜索圖更有效地產生相鄰圖。如果採用具有最少相鄰頂點的頂點作為開始頂點，從而執行搜索，那麼搜索圖不能有效地產生相鄰圖。由此，通過根據圖19的方法產生開始頂點，產生更有效的搜索圖。
參考圖20，現在解釋鍵值量化級發生單元432的操作，用於產生位編碼的量化級(Qstep_X，Qstep_Y，Qstep_Z)。圖20是圖17和18的位編碼產生單元的具體方塊圖。
參考圖20，位編碼產生單元432包括最大值和最小值計算單元(計算Min Max)4321和量化級產生器(計算Qstep)4322。最大值和最小值計算單元(計算Min Max)4321接收鍵值，符合CI節點的第一鍵架的Coord數據，和BFS搜索圖。最大值和最小值計算單元(計算Min Max)4321還接收鍵值中X的量化數據的最大值(MaxX)和最小值(MinX)，鍵值中Y的量化數據的最大值(MaxY)和最小值(MinY)，和鍵值中Z的量化數據的最大值(MaxZ)和最小值(MinZ)，並且將這些最大值和最小值發送到量化級產生器4322。量化級產生器4322產生位編碼的量化級(Qstep_X，Qstep_Y，Qstep_Z)，足以分別表示X、Y和Z坐標的量化數據的範圍。現在解釋計算量化級的方法，用於得到位編碼的量化級。
圖21是流程圖，用於解釋圖20的量化級產生器執行的量化級計算方法。參考圖21，根據本發明計算量化級的方法，優先接收鍵值中X的量化數據的最大值(MaxX)和最小值(MinX)，鍵值中Y的量化數據的最大值(MaxY)和最小值(MinY)，和鍵值中Z的量化數據的最大值(MaxZ)和最小值(MinZ)。如果輸入最大值(MaX，也就是MaxX、MaxY、MaxZ)和最小值(Min，也就是MinX、MinY、MinZ)，那麼在步驟4325確定最小值(Min)的絕對值是否小於或等於最大值(MaX)。如果結果指示最小值小於或等於最大值(MaX)，那麼位編碼的量化級(Qstep，也就是Qstep_X、Qstep_Y、Qstep_Z)，設置為Qstep＝int{(log2|Min|)+1}，否則位編碼的量化級(Qstep)，設置為Qstep＝int{(log2|Max|)+1}。這樣，得到X、Y、Z坐標量化數據的位編碼量化級，並且從圖20的量化級產生器4322輸出位編碼的量化級(Qstep_X、Qstep_Y、Qstep_Z)。
圖22是圖17和18編碼裝置產生的壓縮位流的結構例子的圖。參考圖22，圖17和18的每個位流440和540包括頭信息4400和鍵值信息4405，其中位流440和540由編碼裝置400和500最終產生。頭信息4400和鍵值信息4405指示在一個CI節點中處理的信息。頭信息4400作為反向量化單元475和575中執行的反向量化的條件而提供，從而在解碼裝置450和550中重建CI節點。作為優選的例子4415，頭信息4400包括鍵值的量化尺寸(Qstep_KV)、鍵值中X的位編碼的量化級(Qstep_X)、鍵值中Y的位編碼的量化級(Qstep_Y)、鍵值中Z的位編碼的量化級(Qstep_Z)、和最小值(MinX、MinY、MinZ)和最大值(MaxX、MaxY、MaxZ)，它們用於將量化單元430的差分值標準化為0到1之間包括的值。例子44100顯示了鍵值信息4405的結構，它包括根據BFS搜索順序的鍵值信息。
如上所述，由編碼過程產生的位流可以由解碼裝置450或550，通過編碼過程的反向過程重建為原始數據。這裡，為了重建每個節點中第一鍵碼的鍵架，並且為了產生BFS信息，用於將3D對象的空間相關性表示為BFS形成單元465和565，解碼裝置450和550應該從開始頂點產生器462或562，接收IFS節點數據和開始頂點(Start)。多路分解器460和560接收IFS數據，並且將CIdx數據發送到開始頂點產生器462或562。
如上所述，在被編碼的3D對象的形變信息相應於時間編碼時，本發明通過使用時間空間相關性去掉了數據冗餘，從而提供更有效的數據壓縮。同樣，通過找到適於在編碼的值中產生有效BFS搜索圖的開始頂點，並且通過使用開始頂點，位編碼的量化級被調整為量化的數據，並且執行編碼。由此，CI節點的鍵值被有效編碼。此外，通過補償量化誤差，除了相應的頂點本身，量化誤差不在頂點中累加。由此，在將多個部分形成的編碼的3D對象進行解碼的過程中，防止了分離重建，其中對象的每部分從其它部分分離。由此，在多邊形網格或參數網格表示的3D對象中，3D圖形動畫數據大量的鍵值信息可以被有效地壓縮、編碼和解碼，其中3D圖形動畫數據作為3D對象隨著時間流逝的形變信息而提供。
權利要求
1.一種3維(3D)對象形變信息的編碼方法，其中通過執行3D對象形變的鍵控成幀方法，描述形成3D對象的形狀的頂點信息，所述編碼方法包括步驟(a)通過語法分析3D對象的節點信息，提取鍵碼，指示時間軸上鍵架的位置；鍵值，指示鍵架的特性信息，和關係信息；(b)從相關的信息中產生頂點連接性信息；(c)根據頂點連接性信息，對於去掉時間數據冗餘的每個鍵碼，和去掉時間空間數據冗餘的每個鍵值，產生差分值；(d)將差分值量化；並且(e)通過接收量化的鍵碼和鍵值，通過熵編碼去掉位中的冗餘，並且產生壓縮的位流。
2.根據權利要求1的編碼方法，其中在步驟(a)，節點信息被分成坐標插值器(CI)節點和加索引的端面接收器(IFS)節點，並且從CI節點提取由鍵碼和鍵值形成的的現場數據，並從IFS節點提取坐標索引(CIdx)現場數據。
3.根據權利要求2的編碼方法，其中在步驟(b)，接收從IFS節點提取的CIdx現場數據作為相關信息，並且形成確定頂點中空間數據相關性的寬度優先搜索(BFS)信息，作為頂點連接性信息。
4.根據權利要求3的編碼方法，其中在步驟(b)，對於每個頂點接收CIdx現場數據，存儲在隊列中，並且根據是否通過隊列訪問每個頂點，產生BFS信息。
5.根據權利要求1的編碼方法，其中步驟(c)進一步包括步驟(c1)接收頂點連接性信息，作為相關信息的IFS節點的坐標信息，和鍵值，並且在3D空間中鍵值改變的所有位置值中，產生差分值；(c2)根據頂點連接性信息，根據頂點中的空間相關性提取差分值的數據冗餘；並且(c3)對於步驟(a)提取的每個鍵碼，和提取由於空間相關性導致的數據冗餘的鍵值，執行差分脈碼調製(DPCM)處理。
6.根據權利要求5的編碼方法，其中計算被編碼的鍵碼數據項的數量，和從作為相關信息的頂點信息中語法分析的IFS頂點的總數量，並且使用計算結果，計算鍵值的差分值。
7.根據權利要求5的編碼方法，其中在步驟(c2)，根據頂點連接性信息的搜索順序訪問頂點，確定訪問的頂點附近的頂點，具有與訪問的頂點高的空間相關性的頂點，被確定為頂部頂點，計算兩個頂點的3D空間位置值的差分值，並且去掉數據冗餘。
8.根據權利要求1的編碼方法，其中在步驟(e)，相應於符號發生的概率去掉位中的冗餘。
9.根據權利要求8的編碼方法，其中編碼方法得到的位流，至少由編碼的鍵碼信息和鍵值信息所形成，鍵碼信息由鍵碼與鍵碼的鍵碼指示符的結合所形成，以鍵架中鍵碼的順序布置鍵值信息，並且根據頂點連接性信息的搜索順序形成鍵架。
10.一種3維(3D)對象形變信息的編碼方法，其中通過執行3D對象形變的鍵控成幀方法，描述形成3D對象形狀的頂點上的信息，所述編碼方法包括步驟(a)通過語法分析3D對象的節點信息，提取鍵碼，指示時間軸上鍵架的位置；鍵值，指示鍵架的特性信息；和關係信息；(b)從相關的信息中產生頂點連接性信息；(c)將所述鍵碼和鍵值量化；(d)根據頂點連接性信息，對於去掉時間數據冗餘的每個鍵碼，和去掉時間空間數據冗餘的量化的鍵值，產生差分值；並且(e)通過接收差分值，通過熵編碼去掉位中的冗餘，並且產生壓縮的位流。
11.根據權利要求10的編碼方法，其中在步驟(a)，節點信息被分成坐標插值器(CI)節點和加索引的端面接收器(IFS)節點，並且從CI節點提取由鍵碼和鍵值所形成的現場數據，並從IFS節點提取坐標索引(CIdx)現場數據。
12.根據權利要求10的編碼方法，其中在步驟(b)，接收從IFS節點提取的CIdx現場數據作為相關信息，並且用於確定頂點中空間數據相關性的寬度優先搜索(BFS)信息，作為頂點連接性信息形成。
13.根據權利要求12的編碼方法，其中在步驟(b)，對於每個頂點接收CIdx現場數據，並且存儲在隊列中，並且根據是否通過隊列訪問每個頂點，產生BFS信息。
14.根據權利要求10的編碼方法，其中步驟(d)進一步包括步驟(d1)接收頂點連接性信息，作為相關信息的IFS節點的坐標信息，和鍵值，並且在3D空間的鍵值改變的所有位置值中，產生差分值；(d2)根據頂點連接性信息，根據頂點中的空間相關性提取差分值中的數據冗餘；並且(d3)對於步驟(a)提取的每個鍵碼，和提取由於空間相關性導致的數據冗餘的鍵值，執行差分脈碼調製(DPCM)處理。
15.根據權利要求10的編碼方法，其中該編碼方法得到的位流至少由編碼的鍵碼信息和鍵值信息所形成，鍵碼信息由鍵碼與鍵碼的鍵碼指示符的結合所形成，以鍵架中鍵碼的順序布置鍵值信息，並且根據頂點連接性信息的搜索順序形成鍵架。
16.一種3維(3D)對象形變信息的編碼方法，其中通過執行3D對象形變的鍵控成幀方法，將形成3D對象形狀的頂點上的信息編碼，所述編碼方法包括步驟(a)通過語法分析3D對象的節點信息，提取鍵碼，指示時間軸上鍵架的位置；鍵值，指示鍵架的特性信息；和關係信息；(b)產生寬度優先搜索(BFS)的搜索開始信息，用於在3D對象的頂點中確定空間數據相關性；(c)從步驟(a)提取的相關信息和步驟(b)產生的搜索開始信息中，產生頂點連接性信息；(d)根據頂點連接性信息，產生去掉時間數據冗餘的每個鍵碼，和去掉時間空間數據冗餘的鍵值的差分值；(e)將差分值量化；(f)接收量化的鍵碼和鍵值，並且產生鍵值位編碼的量化級；並且(g)接收位編碼的量化級，並且去掉量化值的位中的冗餘。
17.根據權利要求16的編碼方法，其中在步驟(a)，節點信息被分成坐標插值器(CI)節點和加索引的端面接收器(IFS)節點，並且從CI節點提取由鍵碼和鍵值所形成的現場數據，並從IFS節點提取坐標索引(CIdx)現場數據。
18.根據權利要求16的編碼方法，其中步驟(b)包括步驟(b1)響應被編碼的頂點中的連接信息，得到連接到每個頂點上的頂點的數量；(b2)得到頂點數量中具有最大數量連接頂點的頂點索引；並且(b3)產生得到索引的頂點，作為搜索開始信息。
19.根據權利要求16的編碼方法，其中步驟(f)步包括步驟(f1)對於形成量化鍵值的每個X、Y和Z坐標，比較最大值和最小值。(f2)如果在每個X、Y和Z坐標中，最小值的絕對值小於或等於最大值，那麼輸出位編碼的量化級，作為Qstep＝int{(log2|Min|)+1}；(f3)如果在每個X、Y和Z坐標中，最小值的絕對值大於最大值，那麼輸出位編碼的量化級作為Qstep＝int{(log2|Max|)+1}。
20.根據權利要求16的編碼方法，其中在步驟(g)，相應於符號發生的概率去掉位中的冗餘。
21.根據權利要求16的編碼方法，其中通過編碼方法得到的位流包括頭信息，具有鍵值的量化尺寸；鍵值X坐標的位編碼的量化級；鍵值Y坐標的位編碼的量化級；鍵值Z坐標的位編碼的量化級；用於將量化的鍵碼和鍵值的差分值標準化為包括0與1及它們之間的值的最小值和最大值；和根據BFS搜索順序的鍵值信息。
22.一種3維(3D)對象形變信息的編碼方法，其中通過執行3D對象形變的鍵控成幀方法，將形成3D對象形狀的頂點上的信息編碼，所述編碼方法包括步驟(a)通過語法分析3D對象的節點信息，提取鍵碼，指示時間軸上鍵架的位置；鍵值，指示鍵架的特性信息；和關係信息；(b)產生寬度優先搜索(BFS)的搜索開始信息，用於確定3D對象的頂點的空間數據相關性；(c)從步驟(a)提取的相關信息和從步驟(b)產生的搜索開始信息中，產生頂點連接性信息；(d)將鍵碼和鍵值量化；(e)根據頂點連接性信息，對於去掉時間數據冗餘的每個量化值，和去掉時間空間數據冗餘的量化的鍵值，產生差分值；(f)接收差分值，並產生鍵值位編碼的量化級；並且(g)接收位編碼的量化級，並且去掉量化值的位中的冗餘。
23.根據權利要求22的編碼方法，其中在步驟(a)，節點信息被分成坐標插值器(CI)節點和加索引的端面接收器(IFS)節點，並且從CI節點提取由鍵碼和鍵值所形成的現場數據，並從IFS節點提取坐標索引(CIdx)現場數據。
24.根據權利要求22的編碼方法，其中步驟(b)步包括步驟(b1)響應被編碼的頂點中的連接信息，得到連接到每個頂點的頂點數量；(b2)得到頂點數量中具有最大數量的連接頂點的頂點索引；並且(b3)產生得到索引的頂點，作為搜索開始信息。
25.根據權利要求22的編碼方法，其中步驟(f)步包括步驟(f1)對於形成量化鍵值的每個X、Y和Z坐標，比較最大值和最小值。(f2)如果在每個X、Y和Z坐標中，最小值的絕對值小於或等於最大值，那麼輸出位編碼的量化級，作為Qstep＝int{(log2|Min|)+1}；(f3)如果在每個X、Y和Z坐標中，最小值的絕對值大於最大值，那麼輸出位編碼的量化級，作為Qstep＝int{(log2|Max|)+1}。
26.根據權利要求22的編碼方法，其中在步驟(g)，相應於符號發生的概率去掉位中的冗餘。
27.根據權利要求22的編碼方法，其中通過編碼方法得到的位流包括頭信息，具有鍵值的量化尺寸；鍵值X坐標的位編碼的量化級；鍵值Y坐標的位編碼的量化級；鍵值Z坐標的位編碼的量化級；用於將量化的鍵碼與鍵碼的差分值標準化為包括在0與1之間的值的最小值和最大值；和根據BFS搜索順序的鍵值信息。
28.一種3維(3D)對象形變信息的編碼裝置，其中通過用於執行3D對象形變的鍵控成幀方法，將形成3D對象形狀的頂點上的信息編碼，所述編碼裝置包括現場數據輸入單元，通過語法分析3D對象的節點信息，提取鍵碼，指示時間軸上鍵架的位置；鍵值，指示鍵架的特性信息，和關係信息；頂點連接性處理單元，從相關信息中產生頂點連接性信息；自適應差分脈碼調製(ADPCM)處理單元，根據相關信息和頂點連接性信息，對於去掉時間數據冗餘的每個鍵碼，和去掉時間空間數據冗餘的每個鍵值，產生差分值；量化單元，用於將差分值量化，並且輸出量化的差分值；熵編碼單元，用於接收量化的鍵碼和鍵值，去掉位中的冗餘。
29.一種3維(3D)對象形變信息的編碼裝置，其中通過執行3D對象形變的鍵控成幀方法，將形成3D對象形狀的頂點上的信息編碼，所述編碼裝置包括現場數據輸入單元，通過語法分析3D對象的節點信息，提取鍵碼，指示時間軸上鍵架的位置；鍵值，指示鍵架的特性信息，和關係信息；量化單元，用於將鍵碼和鍵值量化；自適應差分脈碼調製(ADPCM)處理單元，根據相關信息和頂點連接性信息，對於去掉時間數據冗餘的量化的鍵碼，和去掉時間空間數據冗餘的量化的鍵值，產生差分值；熵編碼單元，用於去掉位中的冗餘。
30.根據權利要求28和29任何之一的編碼裝置，其中現場數據輸入單元包括語法分析程序，用於將節點信息分成坐標插值器(CI)節點和加索引的端面接收器(IFS)節點；和多路分解器，用於從CI節點中提取由鍵碼和鍵值所形成的現場數據，並且從IFS節點提取坐標索引(CIdx)現場數據。
31.根據權利要求30的編碼裝置，其中頂點連接性處理單元從IFS節點接收CIdx現場數據，作為相關信息，並且形成確定頂點中的空間數據相關性的寬度優先搜索(BFS)信息，作為頂點連接性信息。
32.根據權利要求31的編碼裝置，其中頂點連接性處理單元接收CIdx現場數據，對於每個頂點將CIdx現場數據存儲在隊列中，並且根據是否通過隊列訪問每個節點，產生BFS信息。
33.根據權利要求28和29任何之一的編碼裝置，其中ADPCM處理單元包括差分值產生器，用於接收頂點連接性信息，作為相關信息的IFS節點的坐標信息，和鍵值，並且在3D空間的鍵值改變的所有位置值中，產生差分值；預測器，用於根據頂點連接性信息，根據頂點中的空間相關性提取差分值中的數據冗餘；和差分脈碼調製(DPCM)處理器，對於每個鍵碼，和提取由於空間相關性的數據冗餘的鍵值，進行DPCM處理。
34.根據權利要求28和29任何之一的編碼裝置，其中熵編碼單元產生位流，從中使用位符號發生的概率，去掉量化值的位中的冗餘。
35.根據權利要求34的編碼裝置，其中位流至少由編碼的鍵碼信息和鍵值信息所形成，對於鍵碼，鍵碼信息由鍵碼與鍵碼的鍵碼指示符的結合所形成，以鍵架中鍵碼的順序布置鍵值信息，並且根據頂點連接性信息的搜索順序形成鍵架。
36.一種3維(3D)對象形變信息的編碼裝置，其中通過執行3D對象形變的鍵控成幀方法，將形成3D對象形狀的頂點上的信息編碼，所述編碼裝置包括現場數據輸入單元，通過語法分析3D對象的節點信息，提取鍵碼，指示時間軸上鍵架的位置；鍵值，指示鍵架的特性信息；和關係信息；頂點連接性處理單元，用於從相關信息中產生頂點連接性信息；開始頂點產生器，用於從相關信息中確定頂點連接性信息的開始頂點；自適應差分脈碼調製(ADPCM)處理單元，根據頂點連接性信息，對於去掉時間數據冗餘的每個鍵碼，和去掉時間空間數據冗餘的每個鍵值，產生差分值；量化單元，用於將鍵碼和鍵值量化；量化級產生單元，用於接收量化的鍵碼和鍵值，並且產生量化的鍵值X、Y和Z坐標的位編碼的量化級；熵處理單元，用於接收X、Y和Z坐標的位編碼的量化級，並且去掉量化值的位中的冗餘。
37.一種3維(3D)對象形變信息的編碼裝置，其中通過執行3D對象形變的鍵控成幀方法，將形成3D對象形狀的頂點上的信息編碼，所述編碼裝置包括現場數據輸入單元，通過語法分析3D對象的節點信息，提取鍵碼，指示時間軸上鍵架的位置；鍵值，指示鍵架的特性信息；和關係信息；頂點連接性處理單元，用於從相關信息中產生頂點連接性信息；開始頂點產生器，用於從相關信息中確定頂點連接性信息的開始頂點；量化單元，用於將鍵碼和鍵值量化；自適應差分脈碼調製(ADPCM)處理單元，根據頂點連接性信息，對於去掉時間數據冗餘的量化的鍵碼，和去掉時間空間數據冗餘的量化鍵值，產生差分值；量化級產生單元，用於產生差分的鍵值X、Y和Z坐標的位編碼的量化級；和熵處理單元，用於接收X、Y和Z坐標的位編碼的量化級，並且去掉量化值的位中的冗餘。
38.根據權利要求36或37任何之一的編碼裝置，其中現場數據輸入單元包括語法分析程序，用於將節點信息分離成坐標插值器(CI)和加索引的端面接收器(IFS)節點；和多路分解器，用於從CI節點提取由鍵碼和鍵值所形成的現場數據，並且從IFS節點提取坐標索引(CIdx)現場數據。
39.根據權利要求38的編碼裝置，其中響應CIdx現場數據，開始頂點產生器得到連接到所有頂點的每個的頂點數量中具有最大數量的連接頂點的頂點索引，並且產生得到的索引的頂點，作為開始頂點。
40.根據權利要求38的編碼裝置，其中頂點連接性處理單元接收從IFS節點提取的CIdx現場數據，作為相關信息，形成確定頂點中空間數據相關性的寬度優先搜索(BFS)信息，作為頂點連接性信息，接收開始頂點產生器產生的開始頂點信息，並且產生從開始頂點執行搜索的BFS信息。
41.根據權利要求38的編碼裝置，其中量化級產生單元包括最大值和最小值計算單元，用於接收鍵值，符合CI節點的第一鍵架的數據，和頂點連接性信息，並且輸出鍵值X、Y和Z坐標的最大值和最小值；和量化級產生單元，用於產生位編碼的量化級，足以表示對應於X、Y和Z坐標的量化數據的範圍。
42.根據權利要求41的編碼裝置，其中量化級產生器比較最大和最小計算單元輸入的每個X、Y和Z坐標數據項的最大值和最小值，並且如果最小值的絕對值小於或等於最大值，那麼輸出位編碼的量化級，作為Qstep＝int{(log2|Min|)+1}，並且如果最小值的絕對值大於最大值，那麼輸出位編碼的量化級，作為Qstep＝int{(log2|Max|)+1}。
43.根據權利要求36或37任何之一的編碼裝置，其中熵處理單元使用位符號發生的概率，去掉量化值的位中的冗餘，並且輸出結果作為位流。
44.根據權利要求43的編碼裝置，其中位流包括頭信息，具有鍵值的量化尺寸，鍵值X坐標的位編碼的量化級，鍵值Y坐標的位編碼的量化級，鍵值Z坐標的位編碼的量化級，用於將量化單元的差分值標準化為包括在0與1之間的值的最大值和最小值；和根據BFS搜索順序的鍵值信息。
全文摘要
這裡提供了3維(3D)對象形變信息的編碼方法和裝置。3維(3D)對象形變信息的編碼方法,其中通過執行3D對象形變的鍵控成幀方法,描述形成3D對象形狀的頂點的信息,編碼方法包括:(a)通過語法分析3D對象的節點信息,提取:鍵碼,指示時間軸上鍵架的位置;鍵值,指示鍵架的特性信息;和關係信息;(b)從相關信息中產生頂點連接性信息;(c)根據頂點連接性信息,對於去掉時間數據冗餘的每個鍵碼,和去掉時間空間數據冗餘的每個鍵值,產生差分值;(d)將差分值量化;並且(e)通過熵編碼去掉位中的冗餘,並且產生壓縮的位流。
文檔編號G06T19/00GK1384469SQ0212370
公開日2002年12月11日 申請日期2002年2月28日 優先權日2001年2月28日
發明者金成珍, 李信俊 申請人:三星電子株式會社