(57)【特許請求の範囲】
【請求項１】
ｘ，ｙ及びｚ成分を含む頂点の座標でオブジェクトの位置を表現する座標インタポレータのキー値データを符号化する装置であって、入力された座標インタポレータを所定の量子化ビット数で量子化する量子化器と、量子化された座標インタポレータの各頂点成分に対して所定モードのＤＰＣＭ演算を行って各頂点座標の経時的変化による差分データ及び空間的変化による差分データを生成するＤＰＣＭ処理部と、ＤＰＣＭ演算された各頂点成分の差分データ及び前記差分データに対して行われたＤＰＣＭ演算モードを示すシンボル及び前記シンボルの位置を示すインデックスを生成する辞書符号化器と、前記シンボル及びインデックスをエントロピ符号化するエントロピ符号化器と、を含むことを特徴とする符号化装置。
【請求項２】
前記ＤＰＣＭ処理部は、前記量子化された座標インタポレータの各頂点成分に対し、キーフレーム間の第１差分データを生成する時間ＤＰＣＭ演算と、同じキーフレーム内の頂点間の第２差分データを生成する空間ＤＰＣＭ演算と、キーフレーム及び頂点間の第３差分データを生成する時空間ＤＰＣＭ演算を各々行うＤＰＣＭ演算部と、前記ＤＰＣＭ演算部から入力された第１ないし第３差分データに対し、差分データの範囲を狭める循環量子化を行う循環量子化器と、符号化に必要なビット数によって循環量子化された第１ないし第３差分データのうち何れか１つを選択して出力するＤＰＣＭモード選択部と、を含むことを特徴とする請求項１に記載の符号化装置。
【請求項３】
前記ＤＰＣＭ演算部は、現在キーフレームと以前キーフレームとの頂点の座標差を計算する時間ＤＰＣＭ演算部と、現在キーフレームで各頂点と基準頂点との座標差を計算する空間ＤＰＣＭ演算部と、以前キーフレームの各頂点と各頂点に対応する基準頂点との座標差及び現在キーフレームの各頂点と基準頂点との座標差間の差分データを計算する時空間ＤＰＣＭ演算部と、を含むことを特徴とする請求項２に記載の符号化装置。
【請求項４】
前記基準頂点は、現在の空間ＤＰＣＭ演算が行われる頂点以前にＤＰＣＭ演算が行われた頂点のうち、現在の頂点との差分データの符号化に必要なビット数が最も少ないことを特徴とする請求項３に記載の符号化装置。
【請求項５】
前記循環量子化器は、各頂点成分の差分データ、及び各成分の差分データの最大値及び最小値に対して所定の演算を行って大きさが減少された差分データを生成することを特徴とする請求項２に記載の符号化装置。
【請求項６】
前記循環量子化器は、各頂点成分の差分データの符号によって前記最大値及び最小値に応じた差分データの範囲を加減して循環量子化演算された差分データを生成し、入力された差分データ及び循環量子化された差分データのうち小さい差分データを出力することを特徴とする請求項５に記載の符号化装置。
【請求項７】
前記ＤＰＣＭモード選択部は、各頂点成分の第１ないし第３差分データに対してＳＡＤ演算、分散及びエントロピ演算のうち何れか１つを行い、その結果が最も小さいＤＰＣＭモードの差分データを選択することを特徴とする請求項２に記載の符号化装置。
【請求項８】
前記辞書符号化器は、前記各頂点に対し、各頂点成分データに対して行われたＤＰＣＭモードの組合わせを示すシンボル及び前記シンボルの位置を示すインデックスを生成するＤＰＣＭモード符号化器と、入力された各頂点成分の差分データに対応するシンボル及び前記シンボルの位置を示すインデックスを生成する発生モード符号化器とを含むことを特徴とする請求項１に記載の符号化装置。
【請求項９】
前記発生モード符号化器は、入力された差分データに生じるシンボル及び前記シンボルの位置を示すインデックスをテーブルの形に生成することを特徴とする請求項８に記載の符号化装置。
【請求項１０】
前記辞書符号化器は、入力された各頂点の差分データに所定シンボルの存否を示すシンボルフラグ、及びシンボルの位置を示すインデックスを生成する増加モード符号化器と、前記差分データに対応するシンボルよりなる第１シンボルテーブルのサイズ、及び前記シンボルフラグのサイズを計算し、前記第１シンボルテーブル及びシンボルフラグのサイズに応じて前記ＤＰＣＭモード符号化器から入力された前記各頂点の差分データを前記発生モード符号化器または増加モード符号化器に出力するテーブルサイズ計算部と、をさらに含むことを特徴とする請求項８に記載の符号化装置。
【請求項１１】
前記増加モード符号化器は、前記差分データの最大値によって符号化されるシンボルを示す第２シンボルテーブルをシンボルサイズ順に生成し、入力された差分データに対応するシンボルが前記第２シンボルテーブルに存在するか否かを示すシンボルフラグ、及び前記差分データのシンボルの位置を示すインデックスを生成することを特徴とする請求項１０に記載の符号化装置。
【請求項１２】
前記テーブルサイズ計算部は、前記入力される差分データに含まれたシンボル数及びシンボルの符号化に用いられるビット数に応じて前記第１シンボルテーブルのサイズを計算することを特徴とする請求項１０に記載の符号化装置。
【請求項１３】
前記テーブルサイズ計算部は、前記入力される差分データに含まれるシンボルの符号化に用いられるビット数に応じて増加モードのシンボルフラグのサイズを計算することを特徴とする請求項１０に記載の符号化装置。
【請求項１４】
前記エントロピ符号化器は、入力された差分データの最上位ビットは第１コンテキストを用いてエントロピ符号化し、残りのビットは第２コンテキストを用いてエントロピ符号化することを特徴とする請求項１に記載の符号化装置。
【請求項１５】
ｘ，ｙ及びｚ成分を含む頂点の座標でオブジェクトの位置を表現する座標インタポレータのキー値データを符号化したビットストリームを復号化する装置であって、入力されたビットストリームをエントロピ復号化して差分データのシンボル、前記シンボルの位置を示すインデックス、及びＤＰＣＭ演算モードを含む辞書復号化されるデータを生成するエントロピ復号化器と、前記辞書復号化されるデータに応じて差分データを生成する辞書復号化器と、前記ＤＰＣＭ演算モードに応じて前記辞書復号化器から入力されたキーフレーム間の差分データ及び各頂点間の差分データを復元して量子化されたデータを生成する逆ＤＰＣＭ処理部と、前記量子化されたデータを逆量子化して復元されたキー値データを生成する逆量子化器と、を含むことを特徴とする復号化装置。
【請求項１６】
前記辞書復号化器は、各頂点の各成分データに対して行われたＤＰＣＭモード情報を復号化するＤＰＣＭモード復号化器と、入力された辞書復号化される差分データのシンボル及び前記シンボルの位置を示すインデックスに応じて各頂点の差分データを生成する発生モード復号化器とを含むことを特徴とする請求項１５に記載の復号化装置。
【請求項１７】
前記ＤＰＣＭモード復号化器は、前記各頂点の各成分の差分データに対して行われたＤＰＣＭ演算モードの組合わせを示すシンボル、及び前記シンボルの位置を示すインデックスに応じて各頂点の各成分データのＤＰＣＭ演算モードを復元することを特徴とする請求項１６に記載の復号化装置。
【請求項１８】
前記辞書復号化器は、所定のシンボルが、前記入力された辞書復号化される差分データに存在するか否かを示すシンボルフラグに応じて差分データに含まれたシンボルを復号化し、前記シンボルの位置を示すインデックスに応じて各頂点の差分データを生成する増加モード復号化器と、前記ビットストリームから辞書符号化モードを判読し、前記辞書復号化される差分データを前記発生モード復号化器または前記増加モード復号化器に出力する辞書モード選択部と、をさらに含むことを特徴とする請求項１６に記載の復号化装置。
【請求項１９】
前記逆ＤＰＣＭ処理部は、同じ頂点のキーフレーム間の差分データに対して逆ＤＰＣＭ演算を行う逆時間ＤＰＣＭ演算部と、同じキーフレーム内の各頂点と前記各頂点に対応する基準頂点との差分データに対して逆ＤＰＣＭ演算を行う逆空間ＤＰＣＭ演算部と、前記ＤＰＣＭ演算モードに応じて差分データを前記逆時間ＤＰＣＭ演算部または前記逆空間ＤＰＣＭ演算部に出力する逆ＤＰＣＭモード選択部と、を含むことを特徴とする請求項１５に記載の復号化装置。
【請求項２０】
前記逆ＤＰＣＭ処理部は、現在キーフレームと以前キーフレームの逆空間ＤＰＣＭ演算された結果に対して逆時間ＤＰＣＭ演算を行う逆時空間ＤＰＣＭ演算部をさらに含み、前記逆ＤＰＣＭモード選択部は前記ＤＰＣＭ演算モードに応じて前記差分データを前記逆時間ＤＰＣＭ演算部、前記逆空間ＤＰＣＭ演算部、及び前記逆時空間ＤＰＣＭ演算部のうち何れか１つに出力することを特徴とする請求項１９に記載の復号化装置。
【請求項２１】
前記逆時間ＤＰＣＭ演算部、逆空間ＤＰＣＭ演算部、及び逆時空間ＤＰＣＭ演算部は、前記入力された差分データ、及び前記各成分の差分データの最大値及び最小値に対して所定の逆循環量子化演算を行って差分データの範囲を広げることを特徴とする請求項２０に記載の復号化装置。
【請求項２２】
ｘ，ｙ及びｚ成分を含む頂点の座標でオブジェクトの位置を表現する座標インタポレータのキー値データを符号化する方法であって、
（ａ）量子化器が、座標インタポレータのキー値データを所定の量子化ビット数で量子化する段階と、
（ｂ）ＤＰＣＭ処理部が、量子化された座標インタポレータの各頂点成分に対して所定モードのＤＰＣＭ演算を行って各頂点座標の経時的変化による差分データ及び空間的変化による差分データを生成する段階と、
（ｃ）辞書符号化器が、ＤＰＣＭ演算された各頂点成分の差分データ及び前記差分データに対して行われたＤＰＣＭ演算モードを示すシンボル及び前記シンボルの位置を示すインデックスを生成する段階と、
（ｄ）エントロピ符号化器が、前記シンボル及びインデックスをエントロピ符号化する段階と、を含むことを特徴とする符号化方法。
【請求項２３】
前記ＤＰＣＭ処理部が行う前記（ｂ）段階は、
（ｂ１）前記量子化された座標インタポレータの各頂点成分に対し、キーフレーム間の第１差分データを生成する時間ＤＰＣＭ演算、同じキーフレーム内の頂点間の第２差分データを生成する空間ＤＰＣＭ演算、及びキーフレーム及び頂点間の第３差分データを生成する時空間ＤＰＣＭ演算を各々行う段階と、
（ｂ２）前記第１ないし第３差分データに対し、差分データの範囲を狭める循環量子化を行う段階と、
（ｂ３）符号化に必要なビット数によって循環量子化された第１ないし第３差分データのうち何れか１つを選択する段階と、を含むことを特徴とする請求項２２に記載の符号化方法。
【請求項２４】
前記ＤＰＣＭ処理部が行う前記（ｂ１）段階は、
現在キーフレームと以前キーフレーム間の同一頂点の座標差を計算する時間ＤＰＣＭ演算、現在キーフレームで各頂点と各頂点に対応する基準頂点との座標差を計算する空間ＤＰＣＭ演算、及び以前キーフレームの各頂点と基準頂点との座標差及び現在キーフレームの各頂点と基準頂点との座標差間の差分データを計算する時空間ＤＰＣＭ演算を行うことを特徴とする請求項２３に記載の符号化方法。
【請求項２５】
前記基準頂点は、現在の空間ＤＰＣＭ演算が行われる頂点以前にＤＰＣＭ演算が行われた頂点のうち、現在の頂点との差分データの符号化に必要なビット数が最小の頂点であることを特徴とする請求項２３に記載の符号化方法。
【請求項２６】
前記ＤＰＣＭ処理部が行う前記（ｂ２）段階は、
各頂点成分の差分データ、及び各成分の差分データの最大値及び最小値に所定の演算を行って大きさが減少された差分データを生成することを特徴とする請求項２３に記載の符号化方法。
【請求項２７】
前記ＤＰＣＭ処理部が行う前記（ｂ２）段階は、
各頂点成分の差分データの符号によって前記最大値及び最小値に応じる差分データの範囲を加減して循環量子化演算された差分データを生成し、前記差分データ及び循環量子化された差分データのうち小さい差分データを循環量子化された差分データと決定することを特徴とする請求項２６に記載の符号化方法。
【請求項２８】
前記ＤＰＣＭ処理部が行う前記（ｂ３）段階は、
各頂点成分の第１ないし第３差分データに対してＳＡＤ演算、分散及びエントロピ演算のうち何れか１つを行い、その結果が最小であるＤＰＣＭモードの差分データを選択することを特徴とする請求項２３に記載の符号化方法。
【請求項２９】
前記辞書符号化器が行う前記（ｃ）段階は、
（ｃ１）前記各頂点に対し、各成分データに対して行われたＤＰＣＭモードの組合わせを示すシンボル及び前記シンボルの位置を示すインデックスを生成する段階と、
（ｃ３）各頂点の差分データに対応するシンボル及び前記シンボルの位置を示すインデックスを生成する発生モード符号化演算を行う段階と、を含むことを特徴とする請求項２２に記載の符号化方法。
【請求項３０】
前記辞書符号化器が行う前記（ｃ３）段階は、
入力された差分データに生じるシンボル及び前記シンボルの位置を示すインデックスをテーブルの形に生成することを特徴とする請求項２９に記載の符号化方法。
【請求項３１】
前記辞書符号化器が行う前記（ｃ３）段階は、
入力された各頂点の差分データに対して所定シンボルの存否を示すシンボルフラグ、及びシンボルの位置を示すインデックスを生成する増加モード符号化演算を行う段階をさらに含み、前記（ｃ１）段階及び前記（ｃ３）段階の間に、（ｃ２）前記差分データに対応するシンボルよりなる第１シンボルテーブルのサイズ及び前記シンボルフラグのサイズを計算し、前記各頂点の差分データに対して行われる辞書符号化演算を決定する段階をさらに含むことを特徴とする請求項２９に記載の符号化方法。
【請求項３２】
前記辞書符号化器が行う前記増加モード符号化演算は、
前記差分データの最大値に応じて符号化されるシンボルを示す第２シンボルテーブルをシンボルサイズ順に生成し、前記各頂点成分の差分データに対応するシンボルが前記第２シンボルテーブルに存在するか否かを示すシンボルフラグ、及び前記差分データに対応するシンボルの位置を示すインデックスを生成することを特徴とする請求項３１に記載の符号化方法。
【請求項３３】
前記辞書符号化器が行う前記（ｃ２）段階は、
前記各頂点成分の差分データに含まれたシンボル数及びシンボルの符号化に用いられるビット数に応じて前記第１シンボルテーブルのサイズを計算することを特徴とする請求項３１に記載の符号化方法。
【請求項３４】
前記辞書符号化器が行う前記（ｃ２）段階は、
前記各頂点成分の差分データに含まれるシンボルの符号化に用いられるビット数に応じてシンボルフラグの大きさを計算することを特徴とする請求項３１に記載の符号化方法。
【請求項３５】
前記エントロピ符号化器が行う前記（ｄ）段階は、
入力された差分データの最上位ビットは第１コンテキストを用いてエントロピ符号化し、残りのビットは第２コンテキストを用いてエントロピ符号化することを特徴とする請求項２２に記載の符号化方法。
【請求項３６】
請求項２２ないし３５のうち何れか１項に記載の符号化方法をコンピュータにて判読でき、実行可能なプログラムコードにて記録した記録媒体。
【請求項３７】
ｘ，ｙ及びｚ成分を含む頂点の座標でオブジェクトの位置を表現する座標インタポレータのキー値データを符号化したビットストリームを復号化する方法であって、
（ａ）エントロピ符号化器が、入力されたビットストリームをエントロピ復号化して差分データのシンボル、前記シンボルの位置を示すインデックス、及びＤＰＣＭ演算モードを含む辞書復号化される差分データを生成する段階と、
（ｂ）
辞書復号化器が、前記辞書復号化される差分データのシンボル及びシンボルの位置を示すインデックスに対して所定の辞書復号化演算を行って差分データを生成する辞書復号化段階と、（ｃ）前記ＤＰＣＭ演算モードに応じて前記辞書復号化されたキーフレーム間の差分データ及び各頂点間の差分データを復元して量子化されたデータを生成する段階と、
（ｄ）逆ＤＰＣＭ処理部が、前記量子化されたデータを逆量子化して復元されたキー値データを生成する段階と、を含む復号化方法。
【請求項３８】
前記辞書復号化器が行う前記（ｂ）段階は、
（ｂ１）各頂点に対して行われたＤＰＣＭ演算情報を復号化する段階と、
（ｂ３）辞書復号化される差分データのシンボル及び前記差分データのシンボルの位置を示すインデックスに応じて各頂点の差分データを生成する発生モード復号化演算を行う段階と、を含むことを特徴とする請求項３７に記載の復号化方法。
【請求項３９】
前記辞書復号化器が行う前記（ｂ１）段階は、前記各頂点の各成分の差分データに対して行われたＤＰＣＭ演算モードの組合わせを示すシンボル、及び前記シンボルの位置を示すインデックスに応じて各頂点の各成分データのＤＰＣＭ演算モードを復元することを特徴とする請求項３８に記載の復号化方法。
【請求項４０】
前記辞書復号化器が行う前記（ｂ３）段階は、
入力された辞書復号化される差分データのシンボルフラグに応じて差分データに含まれたシンボルを復号化し、前記シンボルの位置を示すインデックスに応じて各頂点の差分データを生成する増加モード復号化演算段階をさらに含み、
前記（ｂ１）段階と前記（ｂ３）段階との間に、前記ビットストリームから辞書符号化モードを判読して前記辞書復号化されるデータに対して行われる辞書復号化演算を選択する段階を含むことを特徴とする請求項３８に記載の復号化方法。
【請求項４１】
前記逆ＤＰＣＭ処理部が行う前記（ｃ）段階は、
前記ＤＰＣＭ演算モードに応じて差分データに所定の逆ＤＰＣＭ演算を行い、
前記所定の逆ＤＰＣＭ演算は同じ頂点のキーフレーム間の差分データに対して逆ＤＰＣＭ演算を行って量子化されたデータを生成する逆時間ＤＰＣＭ演算、及び同じキーフレーム内の各頂点と前記各頂点に対応する基準頂点との差分データに対して逆ＤＰＣＭ演算を行って量子化されたデータを生成する逆空間ＤＰＣＭ演算を行うことを特徴とする請求項３７に記載の復号化方法。
【請求項４２】
前記逆ＤＰＣＭ処理部が行う前記所定の逆ＤＰＣＭ演算は、
現在キーフレームと以前キーフレームとの逆空間ＤＰＣＭ演算された結果に対して逆時間ＤＰＣＭ演算を行う逆時空間ＤＰＣＭ演算をさらに含むことを特徴とする請求項４１に記載の復号化方法。
【請求項４３】
前記逆ＤＰＣＭ処理部が行う前記逆時間ＤＰＣＭ演算、逆空間ＤＰＣＭ演算、及び逆時空間ＤＰＣＭ演算は前記差分データ、及び前記各成分の差分データの最大値及び最小値に対して所定の逆循環量子化演算を行って差分データの範囲を広げることを特徴とする請求項４２に記載の復号化方法。
【請求項４４】
請求項３７ないし４３のうち何れか１項に記載の復号化方法をコンピュータにて判読でき、実行可能なプログラムコードにて記録した記録媒体。
【請求項４５】
経時的に動くオブジェクトに含まれる各頂点の量子化された座標データ間の差分データを生成する装置であって、
時間成分に応じて変化する同じ頂点間の差分データを生成する時間ＤＰＣＭ演算部と、
同じ時間に各頂点と前記各頂点とに対応する基準頂点間の差分データを生成する空間ＤＰＣＭ演算部と、
前記時間及び空間ＤＰＣＭ演算部から入力された差分データのうち最小の差分データを出力するＤＰＣＭモード選択部と、を含むことを特徴とする差分データ生成装置。
【請求項４６】
相異なる時間に同じ頂点に対して空間ＤＰＣＭ演算された第１差分データを計算し、前記第１差分データに対して時間ＤＰＣＭ演算を行って時間変化による第２差分データを生成する時空間ＤＰＣＭモード演算部をさらに含み、
前記ＤＰＣＭ演算モード選択部は、前記時間、空間、及び時空間ＤＰＣＭ演算部から入力された差分データのうち最小の差分データを出力することを特徴とする請求項４５に記載の差分データ生成装置。
【請求項４７】
前記基準頂点は、現在の空間ＤＰＣＭ演算を行う頂点以前にＤＰＣＭ演算が行われた頂点のうち、現在の頂点との差分データの符号化に必要なビット数が最小の頂点であることを特徴とする請求項４６に記載の差分データ生成装置。
【請求項４８】
前記ＤＰＣＭ演算モード選択部は、
前記各頂点成分に対して前記時間、空間、及び時空間演算部から入力された差分データに対してＳＡＤ演算、分散及びエントロピ演算のうち何れか１つを行って最小の差分データを選択することを特徴とする請求項４６に記載の差分データ生成装置。
【請求項４９】
各頂点成分の時間、空間、及び時空間ＤＰＣＭ演算された差分データ及び差分データの最大範囲に所定の演算を行って大きさが減少された差分データを生成する循環量子化器をさらに含み、前記ＤＰＣＭモード選択部は、前記循環量子化された時間、空間、及び時空間ＤＰＣＭ演算された差分データのうち最小の差分データを選択することを特徴とする請求項４６に記載の差分データ生成装置。
【請求項５０】
前記循環量子化器は、各頂点成分の時間、空間、及び時空間ＤＰＣＭ演算された差分データの符号に応じて前記差分データの範囲を加減して循環量子化演算された差分データを生成し、入力された差分データ及び循環量子化された差分データのうち小さい差分データを出力することを特徴とする請求項４９に記載の差分データ生成装置。
【請求項５１】
経時的に動くオブジェクトに含まれる各頂点の量子化された座標データ間の差分データに対して所定の逆ＤＰＣＭ演算を行って量子化された座標データを生成する装置であって、同じ頂点の時間変化による差分データに対して逆ＤＰＣＭ演算を行う逆時間ＤＰＣＭ演算部と、同じ時間の各頂点と前記各頂点に対応する基準頂点間の差分データに対して逆ＤＰＣＭ演算を行う逆空間ＤＰＣＭ演算部と、前記入力差分データに含まれたＤＰＣＭ演算モードに応じて入力差分データを前記逆時間ＤＰＣＭ演算部または前記逆空間ＤＰＣＭ演算部に出力する逆ＤＰＣＭモード選択部と、を含むことを特徴とする量子化された座標データ生成装置。
【請求項５２】
現在逆空間ＤＰＣＭ演算された結果と以前に逆空間ＤＰＣＭ演算された結果とに対して逆時間ＤＰＣＭ演算を行う逆時空間ＤＰＣＭ演算部をさらに含み、前記逆ＤＰＣＭモード選択部は、前記ＤＰＣＭ演算モードに応じて前記差分データを前記逆時間ＤＰＣＭ演算部、前記逆空間ＤＰＣＭ演算部、及び前記逆時空間ＤＰＣＭ演算部のうち何れか１つに出力することを特徴とする請求項５１に記載の量子化された座標データ生成装置。
【請求項５３】
前記逆時間ＤＰＣＭ処理部、逆空間ＤＰＣＭ演算部、及び逆時空間ＤＰＣＭ演算部は、前記入力された差分データ、及び前記各成分の差分データの最大範囲に対して所定の逆循環量子化演算を行って差分データの範囲を広げることを特徴とする請求項５２に記載の量子化された座標データ生成装置。
【請求項５４】
経時的に動くオブジェクトに含まれる各頂点の量子化された座標データ間の差分データを生成する差分データ生成方法であって、
（ａ）時間ＤＰＣＭ演算部が、時間成分に応じて変化する同じ頂点間の差分データを生成する時間ＤＰＣＭ演算段階と、
（ｂ）空間ＤＰＣＭ演算部が、同じ時間に各頂点と前記各頂点に対応する基準頂点との差分データを生成する空間ＤＰＣＭ演算段階と、
（ｅ）ＤＰＣＭモード選択部が、前記時間及び空間ＤＰＣＭ演算された差分データのうち最小の差分データを出力する段階と、を含むことを特徴とする差分データ生成方法。
【請求項５５】
前記（ｅ）段階前に、（ｃ）
時空間ＤＰＣＭ演算部が、相異なる時間に同じ頂点に対して空間ＤＰＣＭ演算された第１差分データを計算し、前記第１差分データに対して時間ＤＰＣＭ演算を行って時間変化による第２差分データを生成する時空間ＤＰＣＭ演算段階をさらに含み、
前記（ｅ）段階は前記時間、空間、及び時空間ＤＰＣＭ演算された差分データのうち最小の差分データを出力することを特徴とする請求項５４に記載の差分データ生成方法。
【請求項５６】
前記基準頂点は、現在の空間ＤＰＣＭ演算を行う頂点以前にＤＰＣＭ演算が行われた頂点のうち現在の頂点との差分データの符号化に必要なビット数が最小の頂点であることを特徴とする請求項５５に記載の差分データ生成方法。
【請求項５７】
前記ＤＰＣＭモード選択部が行う前記（ｅ）段階は、各頂点成分に対して前記時間、空間、及び時空間演算された差分データに対してＳＡＤ演算、分散及びエントロピ演算のうち何れか１つを行って最小の差分データを出力することを特徴とする請求項５５に記載の差分データ生成方法。
【請求項５８】
前記（ｅ）段階前に、
（ｄ）循環量子化器が、各頂点成分の時間、空間、及び時空間ＤＰＣＭ演算された差分データ及び差分データの最大範囲に所定の演算を行って大きさが減少された差分データを生成する循環量子化段階をさらに含み、
前記ＤＰＣＭモード選択部が行う前記（ｅ）段階は、前記循環量子化された時間、空間、及び時空間ＤＰＣＭ演算された差分データのうち小さい差分データを出力することを特徴とする請求項５５に記載の差分データ生成方法。
【請求項５９】
前記循環量子化器が行う前記（ｄ）段階は、各頂点成分の時間、空間、及び時空間ＤＰＣＭ演算された差分データの符号に応じて前記差分データの範囲を加減して循環量子化演算された差分データを生成し、入力された差分データ及び循環量子化された差分データのうち小さい差分データを出力することを特徴とする請求項５８に記載の差分データ生成方法。
【請求項６０】
経時的に動くオブジェクトに含まれる各頂点の量子化された座標データ間の差分データに所定の逆ＤＰＣＭ演算を行って量子化された座標データを生成する方法であって、
（ａ）逆ＤＰＣＭモード選択部が、前記差分データに含まれたＤＰＣＭ演算モードに応じて差分データに対して行われる逆ＤＰＣＭ演算の種類を選択する段階と、
（ｂ）前記（ａ）段階で選択された逆ＤＰＣＭ演算の種類に応じて所定の逆ＤＰＣＭ演算を行う段階とを含み、
前記所定の逆ＤＰＣＭ演算は同じ頂点の時間変化による差分データに対して逆ＤＰＣＭ演算を行う逆時間ＤＰＣＭ演算部、あるいは、及び同じ時間の各頂点と前記各頂点に対応する基準頂点間の差分データに対して逆ＤＰＣＭ演算を行う逆空間ＤＰＣＭ演算部、の何れかによって行われることを特徴とする量子化された座標データ生成方法。
【請求項６１】
前記所定の逆ＤＰＣＭ演算は、現在逆空間ＤＰＣＭ演算された結果と以前に逆空間ＤＰＣＭ演算された結果に対して逆時間ＤＰＣＭ演算を行う逆時空間ＤＰＣＭ演算部により行われることを特徴とする請求項６０に記載の量子化された座標データ生成方法。
【請求項６２】
前記逆時間ＤＰＣＭ演算部による前記逆時間ＤＰＣＭ演算、前記逆空間ＤＰＣＭ演算部による逆空間ＤＰＣＭ演算、及び前記逆時空間ＤＰＣＭによる逆時空間ＤＰＣＭ演算は、前記差分データ、及び前記各成分の差分データの最大範囲に対して所定の逆循環量子化演算を行って差分データの範囲を広げることを特徴とする請求項６１に記載の量子化された座標データ生成方法。
【請求項６３】
請求項５４ないし５９のうち何れか１項に記載の差分データ生成方法をコンピュータにて判読でき、実行可能なプログラムコードにて記録した記録媒体。
【請求項６４】
請求項６０ないし６２のうち何れか１項に記載の量子化された座標データ生成方法をコンピュータにて判読でき、実行可能なプログラムコードにて記録した記録媒体。
【請求項６５】
キーフレーム上の客体の形態や位置を各々ｘ、ｙ、ｚ成分を有する頂点の座標を用いて示すキー値データ、及び前記キー値データに関する情報を有するキー値データに関する情報を有するキー値ヘッダを含む座標インタポーレータが符号化されたビットストリームを復号化する方法であって、
（ａ）キー値ヘッダ復号化器が、前記キー値ヘッダを復号化する段階と、
（ｂ）キー値データ復号化器が、復号化された前記キー値ヘッダによって前記キー値データを復号化する段階と、を含むことを特徴とする復号化方法。
【請求項６６】
前記（ｂ）段階は、前記キー値データ復号化器が、
エントロピ復号化、辞書復号化（Ｄｉｃｔｉｏｎａｒｙ  Ｄｅｃｏｄｉｎｇ）、逆差分パルス符号変調（Ｉｎｖｅｒｓｅ  Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｕｌｓｅ  Ｃｏｄｅ  Ｍｏｄｕｌａｔｉｏｎ）、及び逆量子化を行うことによって、前記キー値データを復号化することを特徴とする請求項６５に記載の復号化方法。
【請求項６７】
前記キー値データ復号化器は、エントロピ復号化器、辞書復号化器、逆ＤＰＣＭ処理部及び逆量子化器を備えており、
前記（ｂ）段階は、
（ｂ１）前記エントロピ復号化器が、前記キー値データを各成分別にエントロピ復号化する段階と、
（ｂ２）前記辞書復号化器が、前記エントロピ復号化された結果を各成分別に辞書復号化する段階と、
（ｂ３）前記逆ＤＰＣＭ処理部が、前記辞書復号化された結果に対して、各成分別に逆差分パルス符号変調を行う段階と、
（ｂ４）前記逆量子化器が、前記逆差分パルス符号変調が行われた結果を各成分別に逆量子化する段階と、を含むことを特徴とする請求項６５に記載の復号化方法。
【請求項６８】
前記キー値ヘッダは、前記キー値データを頂点モードで復号化するか、あるいは、転置（Ｔｒａｎｓｐｏｓｅ）モードで復号化するかを示すフラグである転置フラグ（ｂＴｒａｎｓｐｏｓｅ）を含み、
前記（ｂ）段階は、
（ｂ５）前記逆量子化器が、前記転置フラグが、前記キー値データを転置モードで復号化することを示すか否かを判断し、前記転置フラグが前記キー値データを転置モードで復号化することを示すと判断されれば、前記逆量子化された結果を転置させる段階をさらに含むことを特徴とする請求項６７に記載の復号化方法。
【請求項６９】
前記キー値ヘッダは、
前記キー値データの量子化時に使われたビット数である量子化ビット数（ｎＫＶＱＢｉｔ）と、
前記キー値データの各成分別最大値及び最小値（ＫＶＭｉｎＭａｘ）と、
前記最大値及び最小値（ＫＶＭａｘＭｉｎ）を読み取るために必要なキー値桁数（ｎＫＶＭＤｉｇｉｔ）と、
前記キー値データを頂点モードで復号化するか、あるいは転置モードで復号化するかを示すフラグの転置フラグ（ｂＴｒａｎｓｐｏｓｅ）と、
前記頂点数（ｎＮｕｍｂｅｒＯｆＣｏｏｒｄ）と、
前記キー値データの量子化された結果の各成分別最大値及び最小値（ｎＸＱＭｉｎＯｆＭｉｎ、ｎＸＱＭａｘＯｆＭｉｎ、ｎＸＱＭｉｎＯｆＭａｘ、ｎＸＱＭａｘＯｆＭａｘ、ｎＹＱＭｉｎＯｆＭｉｎ、ｎＹＱＭａｘＯｆＭｉｎ、ｎＹＱＭｉｎＯｆＭａｘ、ｎＹＱＭａｘＯｆＭａｘ、ｎＺＱＭｉｎＯｆＭｉｎ、ｎＺＱＭａｘＯｆＭｉｎ、ｎＺＱＭｉｎＯｆＭａｘ、ｎＺＱＭａｘＯｆＭａｘ）と、を含むことを特徴とする請求項６５に記載の復号化方法。
【請求項７０】
キーフレーム上の客体の形態や位置を各々ｘ、ｙ、ｚ成分を有する頂点の座標を用いて示すキー値データ、及び前記キー値データに関する情報を有するキー値データに関する情報を有するキー値ヘッダを含む座標インタポーレータを符号化する方法であって、
（ａ）キー値ヘッダ符号化器が、前記キー値ヘッダを符号化する段階と、
（ｂ）キー値データ符号化器が、符号化された前記キー値ヘッダによって前記キー値データを符号化する段階と、を含むことを特徴とする符号化方法。
【請求項７１】
前記（ｂ）段階は、前記キー値データ符号化器が、
量子化、差分パルス符号変調（ＤＰＣＭ：Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｕｌｓｅ  Ｃｏｄｅ  Ｍｏｄｕｌａｔｉｏｎ）、辞書符号化（Ｄｉｃｔｉｏｎａｒｙ  Ｅｎｃｏｄｉｎｇ）、逆差分パルス符号変調（Ｉｎｖｅｒｓｅ  Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｕｌｓｅ  Ｃｏｄｅ  Ｍｏｄｕｌａｔｉｏｎ）、及びエントロピ符号化（Ｅｎｔｒｏｐｙ  Ｅｎｃｏｄｉｎｇ）を行うことによって、前記キー値データを符号化することを特徴とする請求項７０記載の符号化方法。
【請求項７２】
前記キー値データ符号化器は、量子化器、ＤＰＣＭ処理部、辞書符号化器及びエントロピ符号化器を備えており、
前記（ｂ）段階は、
（ｂ１）前記量子化器が、前記キー値データを各成分別に量子化する段階と、
（ｂ２）前記ＤＰＣＭ符号化器が、前記量子化された結果に対して各成分別に差分パルス符号変調を行う段階と、
（ｂ３）前記辞書符号化器が、前記差分パルス符号変調された結果を各成分別に辞書符号化する段階と、
（ｂ４）前記エントロピ符号化器が、前記辞書符号化された結果を各成分別にエントロピ符号化する段階と、を含むことを特徴とする請求項７０に記載の符号化方法。
【請求項７３】
前記差分パルス符号変調は、
キーフレーム間の差分データを生成する時間的差分パルス符号変調（ｔｅｍｐｏｒａｌ  ＤＰＣＭ）、前記キーフレーム内の前記頂点間の差分データを生成する空間的差分パルス符号変調（ｓｐａｔｉａｌ  ＤＰＣＭ）、前記キーフレーム間及び前記頂点間の差分データを生成する時空間的差分パルス符号変調（ｔｅｍｐｏｒａｌ  ａｎｄ  ｓｐａｔｉａｌ  ＤＰＣＭ）のうち、少なくとも何れか一つであることを特徴とする請求項７１に記載の符号化方法。
【請求項７４】
キーフレーム上の客体の形態や位置を各々ｘ、ｙ、ｚ成分を有する頂点の座標を用いて示すキー値データ、及び前記キー値データに関する情報を有するキー値データに関する情報を有するキー値ヘッダを含む座標インタポーレータが符号化されたビットストリームを復号化する装置であって、
前記キー値ヘッダを復号化するキー値ヘッダ復号化器と、
復号化された前記キー値ヘッダによって前記キー値データを復号化するキー値データ復号化器と、を備えることを特徴とする復号化装置。
【請求項７５】
前記キー値データ復号化器は、
エントロピ復号化、辞書復号化（Ｄｉｃｔｉｏｎａｒｙ  Ｄｅｃｏｄｉｎｇ）、逆差分パルス符号変調（Ｉｎｖｅｒｓｅ  Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｕｌｓｅ  Ｃｏｄｅ  Ｍｏｄｕｌａｔｉｏｎ）、及び逆量子化を行うことによって、前記キー値データを復号化することを特徴とする請求項７４記載の復号化装置。
【請求項７６】
前記キー値データ復号化器は、
前記エントロピ復号化器が、前記キー値データを各成分別にエントロピ復号化するエントロピ復号化器と、
前記エントロピ復号化された結果を各成分別に辞書復号化する辞書復号化器と、
前記辞書復号化された結果に対して、各成分別に逆差分パルス符号変調を行う逆ＤＰＣＭ処理部と、
前記逆差分パルス符号変調が行われた結果を各成分別に逆量子化する逆量子化器段階と、を備えることを特徴とする請求項７５に記載の復号化装置。
【請求項７７】
前記キー値ヘッダは、
前記キー値データの量子化時に使われたビット数である量子化ビット数（ｎＫＶＱＢｉｔ）と、
前記キー値データの各成分別最大値及び最小値（ＫＶＭｉｎＭａｘ）と、
前記最大値及び最小値（ＫＶＭａｘＭｉｎ）を読み取るために必要なキー値桁数（ｎＫＶＭＤｉｇｉｔ）と、
前記キー値データを頂点モードで復号化するか、あるいは転置モードで復号化するかを示すフラグの転置フラグ（ｂＴｒａｎｓｐｏｓｅ）と、
前記頂点数（ｎＮｕｍｂｅｒＯｆＣｏｏｒｄ）と、
前記キー値データの量子化された結果の各成分別最大値及び最小値（ｎＸＱＭｉｎＯｆＭｉｎ、ｎＸＱＭａｘＯｆＭｉｎ、ｎＸＱＭｉｎＯｆＭａｘ、ｎＸＱＭａｘＯｆＭａｘ、ｎＹＱＭｉｎＯｆＭｉｎ、ｎＹＱＭａｘＯｆＭｉｎ、ｎＹＱＭｉｎＯｆＭａｘ、ｎＹＱＭａｘＯｆＭａｘ、ｎＺＱＭｉｎＯｆＭｉｎ、ｎＺＱＭａｘＯｆＭｉｎ、ｎＺＱＭｉｎＯｆＭａｘ、ｎＺＱＭａｘＯｆＭａｘ）と、を含むことを特徴とする請求項７４に記載の復号化装置。
【請求項７８】
キーフレーム上の客体の形態や位置を各々ｘ、ｙ、ｚ成分を有する頂点の座標を用いて示すキー値データ、及び前記キー値データに関する情報を有するキー値データに関する情報を有するキー値ヘッダを含む座標インタポーレータを符号化する装置であって、
前記キー値ヘッダを符号化するキー値ヘッダ符号化器と、
符号化された前記キー値ヘッダによって前記キー値データを符号化するキー値データ符号化器と、を備えることを特徴とする符号化装置。
【請求項７９】
前記キー値データ符号化器は、
量子化、差分パルス符号変調、辞書符号化、エントロピ符号化を行うことによって、前記キー値データを符号化することを特徴とする請求項７８に記載の符号化装置。
【請求項８０】
前記キー値データ符号化器は、
前記キー値データを各成分別に量子化する量子化器と、
前記量子化された結果に対して各成分別に差分パルス符号変調を行うＤＰＣＭ処理部と、
前記差分パルス符号変調された結果を各成分別に辞書符号化する辞書符号化器と、
前記辞書符号化された結果を各成分別にエントロピ符号化するエントロピ符号化器と、
を備えることを特徴とする請求項７９に記載の符号化装置。
【請求項８１】
前記差分パルス符号変調は、
キーフレーム間の差分データを生成する時間的差分パルス符号変調（ｔｅｍｐｏｒａｌ  ＤＰＣＭ）、前記キーフレーム内の前記頂点間の差分データを生成する空間的差分パルス符号変調（ｓｐａｔｉａｌ  ＤＰＣＭ）、前記キーフレーム間及び前記頂点間の差分データを生成する時空間的差分パルス符号変調（ｔｅｍｐｏｒａｌ  ａｎｄ  ｓｐａｔｉａｌ  ＤＰＣＭ）のうち、少なくとも何れか一つであることを特徴とする請求項８０に記載の符号化装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は合成イメージの符号化及び復号化装置、並びに方法に関する。具体的に、本発明はキーフレーム基盤のグラフィックアニメーション方式において、オブジェクトの位置をｘ，ｙ及びｚ成分を含む頂点の座標で表現する座標インタポレータのキー値データの符号化及び復号化装置、並びに方法に関する。
【０００２】
【従来の技術】
３次元アニメーション表現技法は、３次元コンピュータゲームまたはコンピュータの仮想現実環境でひろく使われている。ＶＲＭＬ（Virtual Reality Modeling Language）はそのような３次元アニメーション表現技法の代表的な例である。
【０００３】
ＭＰＥＧ−４ ＢＩＦＳ（Binary Format for Scene）及びＶＲＭＬのような国際マルチメディア標準はインタポレータノードを用いたキーフレーム基盤の３次元アニメーションをサポートする。ＭＰＥＧ−４ ＢＩＦＳ及びＶＲＭＬには多様な種類のインタポレータがあるが、その中で代表的なものにスカラーインタポレータ、位置インタポレータ、座標インタポレータ、回転インタポレータ、法線インタポレータ及び色インタポレータがある。各インタポレータの種類、機能及び特徴は下記表１に示した。
【０００４】
【表１】
0003953411.tif 000002
【０００５】
前記表１に記載されたインタポレータのうち、座標インタポレータは、キーフレーム基盤のアニメーションの３次元オブジェクトに含まれる各頂点の位置情報を示すために使われ、キー及びキー値フィールドよりなる。キーフィールドは（−∞〜＋∞）範囲でキーフレームが位置する時間を不連続的な数字で表現する。キー値フィールドはそれぞれのキーが示す時間に３次元オブジェクトに含まれる各頂点の位置情報を示し、各頂点はｘ，ｙ及びｚの３つの成分を有する。したがって、キー値フィールドはキーフィールドと同数のキー値を含む。このような、キーフレーム基盤のアニメーション方式において、所定のキーフレームは時間軸上の任意の時間に位置し、各キーフレーム間のアニメーションデータは線形補間方法によって補間される。
【０００６】
ＭＰＥＧ−４ ＢＩＦＳ及びＶＲＭＬは、線形補間を用いるので、線形インタポレータを用いてスムーズで自然なアニメーションを具現するためには非常に多量のキーデータとキー値データとが要求される。また、このようなスムーズで自然なアニメーションを保存／伝送するためには大容量の記憶装置及び膨大な時間が必要となる。したがって、これらインタポレータの記憶及び伝送のためにはインタポレータを圧縮することが効率的である。
【０００７】
ＭＰＥＧ−４ ＢＩＦＳでは、インタポレータノードを符号化／復号化する方法として、ＰＭＦＣ（Predictive MF Coding）と称される方法がある。図１に示す従来の符号化装置のように、ＰＭＦＣ方法は量子化器、ＤＰＣＭ（Differential Pulse Code Modulation）モジュール及びエントロピ符号化器を用いて座標インタポレータのキー値データを符号化する。量子化器及びＤＰＣＭモジュールは、キー値データの冗長性を除去し、ＤＰＣＭモジュールの出力はエントロピ符号化器に出力される。しかし、この方法は一般的なＤＰＣＭ演算によって得られた差分データをエントロピ符号化するだけなので、符号化効率が高くない。また、従来の符号化装置は、３次元オブジェクトの形を構成する各頂点間の空間的な相関関係を考慮するだけであって、キーフレーム方式のアニメーション方式で相当な比重を占める時間的な相関関係は全然考慮しないために、符号化効率が高くない。
【０００８】
【発明が解決しようとする課題】
本発明が解決しようとする第１の技術的課題は、空間的な相関関係だけでなく時間的な相関関係も考慮して座標インタポレータのキー値データを符号化する符号化方法及び装置を提供するところにある。
【０００９】
本発明が解決しようとする第２の技術的課題は、時間及び空間的な相関関係を考慮して符号化された座標インタポレータのキー値データを復号化する方法及び装置を提供するところにある。
【００１０】
本発明が解決しようとする第３の技術的課題は、空間的な相関関係だけでなく時間的な相関関係までも考慮して座標インタポレータのキー値データを符号化したビットストリームを提供するところにある。
【００１１】
本発明が解決しようとする第４の技術的課題は、本発明の符号化方法及び装置に用いられる、時間及び空間的な相関関係を考慮して３次元オブジェクトの座標データに対してＤＰＣＭ演算を行うＤＰＣＭ演算方法及び装置を提供するところにある。
【００１２】
本発明が解決しようとする第５の技術的課題は、本発明のＤＰＣＭ演算方法及び装置によって生成された差分データを復元する逆ＤＰＣＭ演算方法及び装置を提供するところにある。
【００１３】
【課題を解決するための手段】
前記技術的な課題を達成するための本発明のキー値データ符号化装置は、入力された座標インタポレータを所定の量子化ビット数で量子化する量子化器と、量子化された座標インタポレータの各頂点成分に対して所定モードのＤＰＣＭ演算を行って各頂点座標の経時的変化による差分データ及び空間的変化による差分データを生成するＤＰＣＭ処理部と、ＤＰＣＭ演算された各頂点成分の差分データ及び前記差分データに対して行われたＤＰＣＭ演算モードを示すシンボル及び前記シンボルの位置を示すインデックスを生成する辞書符号化器と、前記シンボル及びインデックスをエントロピ符号化するエントロピ符号化器と、を含む。
【００１４】
前記本発明のキー値データ符号化装置に用いられる差分データ生成装置は、時間成分に応じて変化する同じ頂点間の差分データを生成する時間ＤＰＣＭ演算部と、同じ時間に各頂点と前記各頂点とに対応する基準頂点間の差分データを生成する空間ＤＰＣＭ演算部と、前記時間及び空間ＤＰＣＭ演算部から入力された差分データのうち最小の差分データを出力するＤＰＣＭモード選択部と、を含む。
【００１５】
前述した本発明の技術的課題を達成するための本発明の復号化装置は、入力されたビットストリームをエントロピ復号化してＤＰＣＭ演算された差分データのシンボル、シンボルの位置を示すインデックス、及びＤＰＣＭ演算モードを含む辞書復号化されるデータを生成するエントロピ復号化器と、辞書復号化されるデータに応じて差分データを生成する辞書復号化器と、ＤＰＣＭ演算モードに応じて辞書復号化器から入力されたキーフレーム間の差分データ及び各頂点間の差分データを復元して量子化されたデータを生成する逆ＤＰＣＭ処理部と、量子化されたデータを逆量子化して復元されたキー値データを生成する逆量子化器と、を含む。
【００１６】
前述した本発明のキー値データ復号化装置に用いられる逆ＤＰＣＭ演算装置は、同じ頂点の時間変化による差分データに対して逆ＤＰＣＭ演算を行う逆時間ＤＰＣＭ演算部と、同じ時間の各頂点と前記各頂点に対応する基準頂点間の差分データに対して逆ＤＰＣＭ演算を行う逆空間ＤＰＣＭ演算部と、入力差分データに含まれたＤＰＣＭ演算モードに応じて入力差分データを逆時間ＤＰＣＭ演算部または前記逆空間ＤＰＣＭ演算部に出力する逆ＤＰＣＭモード選択部と、を含む。
【００１７】
前述した本発明の技術的課題を達成するための本発明のキー値データ符号化方法は、（ａ） 座標インタポレータのキー値データを所定の量子化ビット数で量子化する段階と、（ｂ） 量子化された座標インタポレータの各頂点成分に対して所定モードのＤＰＣＭ演算を行って各頂点座標の経時的変化による差分データ及び空間的変化による差分データを生成する段階と、（ｃ） ＤＰＣＭ演算された各頂点成分の差分データ及び差分データに対して行われたＤＰＣＭ演算モードを示すシンボル及びシンボルの位置を示すインデックスを生成する段階と、（ｄ） シンボル及びインデックスをエントロピ符号化する段階と、を含む。
【００１８】
前述した本発明のキー値データ符号化方法に用いられるＤＰＣＭ演算方法は、（ａ） 時間成分にしたがって変化する同じ頂点間の差分データを生成する時間ＤＰＣＭ演算段階と、（ｂ） 同じ時間に各頂点と各頂点に対応する基準頂点間の差分データを生成する空間ＤＰＣＭ演算段階と、（ｅ） 時間及び空間ＤＰＣＭ演算された差分データのうち最小の差分データを出力する段階と、を含む。
【００１９】
前述した本発明の技術的課題を達成するための本発明のキー値データ復号化方法は、（ａ）入力されたビットストリームをエントロピ復号化してＤＰＣＭ演算された差分データのシンボル、シンボルの位置を示すインデックス、及びＤＰＣＭ演算モードを含む辞書復号化されるデータを生成する段階と、（ｂ） 辞書復号化されるデータのシンボル及びシンボルの位置を示すインデックスに所定の辞書復号化演算を行って差分データを生成する辞書復号化段階と、（ｃ） ＤＰＣＭ演算モードに応じて辞書復号化されたキーフレーム間の差分データ及び各頂点間の差分データを復元して量子化されたデータを生成する段階と、（ｄ） 量子化されたデータを逆量子化して復元されたキー値データを生成する段階と、を含む。
【００２０】
前記本発明のキー値データ復号化方法に用いられる逆ＤＰＣＭ演算方法は、（ａ） 差分データに含まれたＤＰＣＭ演算モードに応じて差分データに対して行われる逆ＤＰＣＭ演算の種類を選択する段階と、（ｂ） 前記（ａ）段階で選択された逆ＤＰＣＭ演算の種類によって所定の逆ＤＰＣＭ演算を行う段階とを含み、所定の逆ＤＰＣＭ演算は同じ頂点の時間変化による差分データに対して逆ＤＰＣＭ演算を行う逆時間ＤＰＣＭ演算、及び同じ時間の各頂点と前記各頂点に対応する基準頂点間の差分データに対して逆ＤＰＣＭ演算を行う逆空間ＤＰＣＭ演算を含む。
【００２１】
【発明の実施の形態】
以下、添付した図面に基づいて本発明の望ましい実施形態に係る符号化装置を説明する。
【００２２】
図２は、本発明の望ましい実施例に係る座標インタポレータのキー値データ符号化装置の構成を示すブロック図であり、図３は、本発明の望ましい実施例に係る符号化方法を説明するフローチャートである。
【００２４】
以下、図３に基づいて本発明の符号化方法を説明する。
【００２５】
座標インタポレータのキー値データはＮ×Ｍサイズのマトリックスの形で量子化器３００に入力される（Ｓ４００）。下記表２に、入力された座標インタポレータのキー値データの一例を示した。
【００２６】
【表２】
0003953411.tif 000003
【００２７】
前記表２においてＮはキーデータの数（キーフレーム数）を、Ｍは各キーフレームにおける頂点の数を示す。
【００２８】
本発明の符号化装置は、座標インタポレータのキー値データを符号化するための２つのモードで動作するが、１つは頂点モードであり、他の１つは転置モードである。前記表２には、頂点モードで量子化器３００が量子化するキー値データの構造を記載した。本発明の符号化装置は転置モードで前記表２に記載の入力されたキー値データの量子化に先立ってＭ×Ｎ行列に変換する。転置変換されたデータ行列は、キー値データの復号化過程で逆量子化された後、復号化されたキー値データをＮ×Ｍ行列に再転換して入力されたキー値データと同じキー値データが復元される。
【００２９】
図３を参照すれば、量子化器３００は外部から入力されたキー値データの符号化モードが転置モードか否かをチェックし（Ｓ４１０）、転置モードであれば入力されたＮ×Ｍのキー値データ行列をＭ×Ｎ行列に変換する（Ｓ４２０）。
【００３０】
その後、量子化器３００は所定の量子化ビット数で入力または変換されたキー値データ行列の各成分のデータを量子化し、量子化された各成分のキー値データをＤＰＣＭ処理部３１０に出力し、量子化に用いられた入力データの各成分の最小値及び最大範囲は１０進数体系の実数に変換してキー値ヘッダ符号化器に出力する（Ｓ４３０）。
【００３１】
ＤＰＣＭ処理部３１０は、入力された量子化されたキー値データに対して時間ＤＰＣＭ演算、空間ＤＰＣＭ演算及び時空間ＤＰＣＭ演算を行い、それぞれのＤＰＣＭ演算結果に対して循環量子化を行い、循環量子化された各差分データのうち最小エントロピの差分データを辞書符号化器３４０に出力する（Ｓ４４０）。
【００３２】
辞書符号化器３４０は、入力された差分データに対応する辞書シンボルＳi,j及び位置インデックスＩi,jを生成して出力する（Ｓ４６０）。具体的に、辞書符号化器３４０は入力された差分データに対して行われたＤＰＣＭ演算モードを示すシンボル及び位置インデックスを生成し、差分データを、差分データに存在する値を示すシンボルまたはシンボルフラグ、及びシンボルの位置を示すインデックスで生成してエントロピ符号化器に出力する。
【００３３】
エントロピ符号化器３５０は、入力されたキー値データ成分のシンボル及びインデックスをエントロピ符号化してビットストリームを生成する（Ｓ４８０）。
【００３４】
以下、前述した各段階を図４ないし図１５をさらに参照して詳細に説明する。
【００３５】
図６を参照すれば、量子化器３００は入力された各成分データの最大値及び最小値を選定する（Ｓ４３２）。
【００３６】
量子化器３００は、選定された各成分のデータの最大値及び最小値を用いて各成分データの範囲を計算し、全ての成分データの範囲のうち最大範囲を決定する（Ｓ４３４）。
【００３７】
量子化器３００は、各成分の最小値及び決定された全ての成分の最大範囲を用いて次の数式１に応じて各成分のキー値データを量子化する（Ｓ４３６）。
【００３８】
【数１】
0003953411.tif 000004
【００３９】
数式１において、ｉはキーデータを、ｊは頂点を、ｎＫＶＱＢｉｔは量子化ビットサイズを各々示す。また、ｆＭｉｎ＿Ｘ，ｆＭｉｎ＿Ｙ及びｆＭｉｎ＿Ｚは各成分データの最小値を、ｆＭａｘは各成分データの範囲のうち最大範囲を示す。
【００４０】
量子化器３００は、量子化された各成分のキー値データをＤＰＣＭ処理部３１０に出力し、前述した各成分の最小値ｆＭｉｎ＿Ｘ，ｆＭｉｎ＿Ｙ及びｆＭｉｎ＿Ｚ及び最大範囲ｆＭａｘを１０進数体系の実数に変換してキー値ヘッダ符号化器３７０に出力する。
【００４１】
コンピュータは実数（ｆｌｏａｔｉｎｇ−ｐｏｉｎｔ ｎｕｍｂｅｒ）を３２ビットの２進数の形で記憶する。量子化器３３０は符号化に必要なビット数を減らすために、２進数の形で表現された各成分の最小値ｆＭｉｎ＿Ｘ，ｆＭｉｎ＿Ｙ及びｆＭｉｎ＿Ｚ及び最大範囲ｆＭａｘを１０進数体系の大きさ（以下、“仮数（ｍａｎｔｉｓｓａ）”と称する）及び１０の累乗（以下、“指数（ｅｘｐｏｎｅｎｔ）”と称する）の形に変換する。すなわち、次の数式２のように変換する。
【００４２】
【数２】
0003953411.tif 000005
【００４３】
例えば、実数１２．３４をコンピュータにて２進数の形で表現すれば、下記の通りである。
0003953411.tif 000006
【００４４】
この数を前記式２により１０進数で表現すれば、下記の通りである。
0003953411.tif 000007
【００４５】
また、量子化器３００は１０進数体系の仮数と指数とをビットストリームに含めるためには、それぞれが必要なビット数を計算せねばならない。まず、指数は−３８〜３８範囲の値を有するので、指数は符号（ｓｉｇｎ）を含んで７ビットで表現されうる。また、仮数は、桁数に応じて必要なビットの数が決められる。仮数の値及びこれに必要なビット数（但し、符号ビットは除く。）を下記表１に示す。
【００４６】
【表３】
0003953411.tif 000008
【００４７】
量子化器３００は前述した数式２及び表３に応じて変換された各成分の最小値ｆＭｉｎ＿Ｘ，ｆＭｉｎ＿Ｙ及びｆＭｉｎ＿Ｚ及び最大範囲ｆＭａｘをキー値ヘッダ符号化器に出力する。
【００４８】
以下、図４及び図７に基づき、本発明のＤＰＣＭ処理部及びＤＰＣＭ演算方法を説明する。
【００４９】
図４は、本発明のＤＰＣＭ処理部３１０の構成を示すブロック図である。図面を参照すれば、本発明のＤＰＣＭ処理部３１０は、量子化器３００から入力された各成分データに対して時間ＤＰＣＭ演算、空間ＤＰＣＭ演算及び時空間ＤＰＣＭ演算を行うＤＰＣＭ演算部３２０、ＤＰＣＭ演算部３２０から入力された差分データの範囲を狭める循環量子化器３３０、循環量子化器３３０から入力された差分データのうち何れか１つを選択して出力するＤＰＣＭモード選択部３３５を含む。また、ＤＰＣＭ演算部３２０は入力された量子化された各成分データに対して時間ＤＰＣＭ演算を行う時間ＤＰＣＭ演算部３２１、量子化された各成分のデータに対して空間ＤＰＣＭ演算を行う空間ＤＰＣＭ演算部３２３、及び量子化された各成分データに対して時間及び空間ＤＰＣＭ演算を行う時空間ＤＰＣＭ演算部３２５を含む。
【００５０】
図７は、本発明のＤＰＣＭ演算方法を詳細に説明するフローチャートである。図面を参照すれば、量子化器３００から入力された量子化された各成分のデータは時間ＤＰＣＭ演算部３２１、空間ＤＰＣＭ演算部３２３、及び時空間ＤＰＣＭ演算部３２５に各々入力されてＤＰＣＭ演算が行われる（Ｓ４４２）。
【００５１】
時間ＤＰＣＭ演算部３２１は、現在キーフレームの各頂点の各成分データと以前キーフレームの各頂点の各成分データとの差を計算する。時間ＤＰＣＭ演算は次の数式３で表される。
【００５２】
【数３】
0003953411.tif 000009
【００５３】
前記数式３においてｉはキーデータを、ｊは頂点のインデックスを各々示す。
【００５４】
一方、空間ＤＰＣＭ演算部３２３は同じキーフレームの各頂点間の差を計算する。具体的に、空間ＤＰＣＭ演算部３２３は空間ＤＰＣＭ演算を行う現在頂点以前に空間ＤＰＣＭ演算が行われた頂点に対し、次の数式４を用いてエントロピを計算する。
【００５５】
【数４】
0003953411.tif 000010
【００５６】
前記数式４において、Ｐiは頂点からシンボルが生じる確率であって、Ｆi／Ｎであり、ここでＦiは頂点からそのシンボルが生じる回数であり、Ｎはキーデータの数である。
【００５７】
空間ＤＰＣＭ演算部３２３は頂点のうち、最低のエントロピの頂点を基準頂点と決定し、現在空間ＤＰＣＭ演算が行われる頂点及び基準頂点の成分データ間の差分データを計算する。空間ＤＰＣＭ演算は次の数式５で表される。
【００５８】
【数５】
0003953411.tif 000011
【００５９】
一方、時空間ＤＰＣＭ演算部３２５は現在キーフレームの各頂点に対して空間ＤＰＣＭ演算を行い、現在キーフレームの各頂点に対応する以前キーフレームの各頂点に対して現在キーフレームの各頂点の基準頂点に対応する頂点を基準頂点として空間ＤＰＣＭ演算を行った後、現在キーフレームの頂点に対応する差分データと以前フレームの頂点に対応する差分データ間の差を計算する。すなわち、空間ＤＰＣＭ演算された結果に対して時間ＤＰＣＭ演算を行う。時空間ＤＰＣＭ演算は次の数式６で表される。
【００６０】
【数６】
0003953411.tif 000012
【００６１】
但し、空間ＤＰＣＭ演算及び時空間ＤＰＣＭ演算のうち、
0003953411.tif 000013
が量子化された最小値より小さければ、この値の代りに量子化された最小値がＤＰＣＭ演算に用いられる。また、空間ＤＰＣＭ演算及び時空間ＤＰＣＭ演算のうち、
0003953411.tif 000014
が量子化された最大値より大きければ、この値の代りに量子化された最大値がＤＰＣＭ演算に用いられる。
【００６２】
ＤＰＣＭ演算部３２０は、計算された差分データを循環量子化器３３０に出力し、循環量子化器３３０は時間ＤＰＣＭ演算された差分データ、空間ＤＰＣＭ演算された差分データ、及び時空間ＤＰＣＭ演算された差分データの各々に対して循環量子化を行い、循環量子化された各差分データをＤＰＣＭモード選択部３３５に出力する（Ｓ４４４）。
【００６３】
図１０は、量子化器３００の出力の一例を示し、図１１は図１０に示された量子化されたデータにＤＰＣＭ演算が行われた結果を示す。図１１に示されたように、量子化された値にＤＰＣＭ演算が行われば、符号化されるデータの範囲は２倍まで増加できる。循環量子化の目的は量子化された値のデータ範囲を保ちつつＤＰＣＭ演算を行うことである。
【００６４】
このために、循環量子化はＤＰＣＭ演算された差分データの最大値がＤＰＣＭ演算された最小値と循環的に連結されていると仮定する。したがって、２つの連続された量子化された差分データ間の線形ＤＰＣＭ結果がＤＰＣＭ演算された差分データの最大値の半分より大きければ、差分データの最大範囲を減算してさらに小さな値に示し、２つの連続された量子化された差分データ間の線形ＤＰＣＭ結果がＤＰＣＭ演算された差分データの最小値の半分より小さければ、差分データの最大範囲を合算してさらに小さな値に示す。
循環量子化器３３０の循環量子化演算は次の数式７で表される。
【００６５】
【数７】
0003953411.tif 000015
【００６６】
前記数式７において、ｎＱＭａｘはＤＰＣＭ演算された差分データのうち最大値を、ｎＱＭｉｎはＤＰＣＭ演算された差分データのうち最小値を示す。図１１に示されたＤＰＣＭ演算されたデータに対して循環量子化を行った結果が図１２に示されている。
【００６７】
循環量子化器３３０は、循環量子化された各差分データをＤＰＣＭモード選択部３３５に出力する。
【００６８】
ＤＰＣＭモード選択部３３５は、各頂点に対して入力された時間、空間及び時空間ＤＰＣＭ演算された差分データのエントロピを前述した数式４に応じて計算する（Ｓ４４６）。
【００６９】
その後、ＤＰＣＭモード選択部３３５は計算されたエントロピが最も小さいＤＰＣＭ演算結果を各頂点のＤＰＣＭ演算モードとして選択し、選択されたＤＰＣＭモードによる差分データ及びＤＰＣＭモード情報を辞書符号化器３４０に出力する（Ｓ４４８）。
【００７０】
以下、図５及び図８に基づいて本発明の辞書符号化器３４０及び辞書符号化方法を説明する。
【００７１】
図５は本発明の辞書符号化器３４０の構成を示すブロック図である。図面を参照すれば、辞書符号化器３４０は入力された各頂点の各成分データに対して行われたＤＰＣＭ演算モードを符号化するＤＰＣＭモード符号化器３４２、入力された各頂点の各成分の差分データ値を示すシンボルとシンボルの位置を示すインデックスを生成する発生モード符号化器３４６、入力された各頂点の各成分の差分データのシンボルに対応する設定フラグ及びシンボルの位置を示すインデックスを生成する増加モード符号化器３４８、及び入力された各頂点の各成分の差分データを表現するためのシンボルテーブルの大きさ及びシンボルフラグテーブルの大きさを計算してＤＰＣＭモード符号化器３４２から入力された差分データを発生モード符号化器３４６または増加モード符号化器３４８に出力するテーブルサイズ計算部３４４を含む。
【００７２】
まず、辞書符号化器３４０はＤＰＣＭモード符号化器３４２において、入力された各頂点の差分データの量子化選択フラグの値が１であるかをチェックし、フラグ値が１であれば、後述する過程を行う。しかし、フラグ値が０であれば、これは該当頂点のあらゆるキーフレームでの量子化された値が同一であることを意味するので、辞書符号化過程を略して量子化された値ＱＭｉｎをキー値ヘッダとして符号化する。
【００７３】
図８は本発明の辞書符号化方法を説明する。図面を参照すれば、ＤＰＣＭ処理部３１０で生成された各頂点の各成分の差分データはまずＤＰＣＭモード符号化器３４２に入力され、ＤＰＣＭモード符号化器３４２は入力された各頂点の各成分データのＤＰＣＭモードを示すシンボル及びシンボルの位置を示すインデックスを生成する（Ｓ４６２）。
【００７４】
図１３は本発明のＤＰＣＭモード符号化器３４２がＤＰＣＭモードを符号化する方法を例示する図面である。
【００７５】
図１３を参照すれば、ＤＰＣＭモード符号化器３４２は各頂点に対して各成分のＤＰＣＭモードの組合わせとこれに対応するシンボルを示すテーブルを予め用意する。時間ＤＰＣＭ演算をＴ、空間ＤＰＣＭ演算をＳ、時空間ＤＰＣＭ演算をＴ＋Ｓと表する時、各頂点のＤＰＣＭモードの組合わせは下記表４の記載の通りである。
【００７６】
【表４】
0003953411.tif 000016
【００７７】
各頂点はｘ，ｙ及びｚの３つの成分を含むので、ＤＰＣＭモードの組合わせは２７種に固定される。
【００７８】
一方、図１３に示されたように、入力された各頂点の差分データは各成分のＤＰＣＭ演算モードの組合わせに応じて前記表４の何れか１つのシンボルに対応する。ＤＰＣＭモード符号化器３４２は入力された各頂点のＤＰＣＭモードを表４のシンボルに対応させ、該当シンボルが差分データに存在することを示すべくフラグを設定する。
【００７９】
ＤＰＣＭモード符号化器３４２は入力された各頂点のＤＰＣＭモード組合わせに対応するシンボルを一列に整列し、小さいシンボルからインデックスを生成する。
【００８０】
入力された差分データに対応するＤＰＣＭモードのシンボル列は、図１３に示されたように、（４，１，５，１，４，５）である。この際、最小のシンボルは１（Ｔ，Ｔ，Ｓ）であるために、ＤＰＣＭモード符号化器３４２はデータ列でシンボル１がある位置を示すインデックスを生成するが、シンボル１の位置は１に設定する。したがって、インデックスは（０，１，０，１，０，０）となる。
【００８１】
その後、ＤＰＣＭモード符号化器３４２は、シンボル列のうち１の次に小さいシンボル４（Ｔ，Ｓ，Ｓ）の位置を示すインデックスを生成するが、シンボル４の位置は１に設定する。但し、この場合にシンボル１の位置は考慮しない。したがって、生成されたインデックスは（１，０，１，０）となる。その後、ＤＰＣＭモード符号化器３４２は残りのシンボル５（Ｔ，Ｓ，Ｔ＋Ｓ）の位置を示すインデックスを生成する。したがって、シンボル５を示すインデックスは（１，１）となる。
【００８２】
ＤＰＣＭモード符号化器３４２は設定されたフラグ及びインデックスをテーブルサイズ計算部３４４に出力する。
【００８３】
図５及び図８を再び参照すれば、テーブルサイズ計算部３４４は入力された差分データの発生モード符号化時に用いられるシンボルテーブルのサイズＡ、及び入力された差分データの増加モード符号化時に用いられる既定のシンボルテーブルの各シンボルに対応するシンボルフラグの大きさＢを計算する（Ｓ４６４）。
【００８４】
テーブルサイズ計算部３４４は発生モード符号化器３４６に用いられるシンボルテーブルの大きさ（Ａ＝Ｓ＊（ＡＱＰ＋１））と増加符号化モード符号化器に用いられるシンボルテーブルに対応するシンボルフラグの大きさ（Ｂ＝２(AQP+1)−１）とを比較する（Ｓ４６６）。ここで、Ｓは差分データに含まれるシンボル数であり、ＡＱＰはシンボルを表現するためのビットサイズである。
【００８５】
テーブルサイズ計算部３４４はＡがＢより小さければ、入力された各頂点の差分データを発生モード符号化器３４６に出力し、ＢがＡより小さければ入力された各頂点の差分データを増加モード符号化器３４８に出力する。
【００８６】
以下、図１４をさらに参照して本発明の発生モード符号化器３４６の処理過程を説明する。
【００８７】
発生モード符号化器３４６は入力された差分データで発生した差分値に対応するシンボルとシンボルとの位置を示す位置インデックスを生成する（Ｓ４６８）。
【００８８】
図１４を参照すれば、入力された差分データが（３，７，３，７，−４，７，３，−４，３，７，−４，−４）であるとすれば、発生モード符号化器３４６は入力された各頂点の差分データの差分値に対応するシンボル（３，７，−４）を順次に記載したテーブルを作成する。
【００８９】
発生モード符号化器３４６は入力された差分データ列で最初シンボルの３を符号化した後、以後のキーフレームで３が現れる位置を１に設定し、３が現れていない位置は０に設定して位置インデックスを生成する。シンボル３に対して生成されたインデックスは（０１０００１０１０００）となる。
【００９０】
また、発生モード符号化器３４６は次のシンボルの７に対してインデックスを生成するが、この時、図１４に示されたように、以前シンボルの位置は考慮しない。したがって、シンボル７に対したインデックスは（１０１０１００）となる。
【００９１】
発生モード符号化器３４６で生成されるインデックスは符号化されていないシンボルの位置だけを考慮するので、最後のシンボル−４の位置インデックスは（１１１）となる。
【００９２】
一方、図１４に示された例では、ｂＳｏｌｅＫＶフラグがモード０に設定された。ｂＳｏｌｅＫＶフラグは差分データに含まれたシンボルが一回だけ発生するかを示すフラグであって、もし、シンボルが一回だけ発生してインデックスが全て０であれば、該当シンボルに対するｂＳｏｌｅＫＶフラグは１に設定され、インデックスは符号化されない。発生モード符号化器３４６は、差分データをエントロピ符号化するために各シンボル、シンボルのインデックス、及びｂＳｏｌｅＫＶフラグをエントロピ符号化器３５０に出力する。
【００９３】
以下、図１５に基づいて本発明の増加モード符号化器３４８の処理過程を説明する。
【００９４】
増加モード符号化器３４８はシンボル値の代りにシンボルの存否を示すフラグ及びシンボルの位置を示す位置インデックスを生成する（Ｓ４６９）。
【００９５】
増加モード符号化器３４８は差分データに存在するシンボルをテーブルであらかじめ生成する。テーブルはシンボルの絶対値順に生成され、同じ絶対値のうち正数が負数より上位に位置する。したがって、テーブルに記載されるシンボルの順序は０，１，−１，２，−２，３，−３．．．になる。シンボルテーブルのシンボルに対応するシンボルフラグのサイズは前述したように２(AQP+1)−１と計算されるが、例えば、ＡＱＰが２であれば、ンシンボルフラグで示せるシンボル数は７となる。また、シンボルフラグは各シンボルに対応する値が差分データに存在すれば１に設定され、フラグが１に設定されたシンボルに対してだけ位置インデックスが生成される。
【００９６】
図１５を参照すれば、増加モード符号化器３４８で入力された差分データが図１５と同一である時、差分データに存在するシンボルは（−１，２，−３）であるために、シンボルフラグは（０，０，１，１，０，０，１）の順に設定される。
【００９７】
増加モード符号化器３４８は、シンボルテーブルの上位に位置するシンボルに対応する位置インデックスを先に生成する。図１５に示されたように、増加モード符号化器３４８はシンボルテーブルの最上位シンボルの−１の位置を１に設定し、その他の位置を０に設定してインデックスを（１０１０００１０１０００）と生成する。
【００９８】
次いで、増加モード符号化器３４８はシンボル−１の位置を考慮せず、残りの位置に対してインデックスを（００１０１０１１）と生成する。最後に、増加モード符号化器３４８は以前に符号化されたシンボルの位置を考慮せず、シンボル−３のインデックスを（１１１１）と生成する。増加モード符号化器３４８は差分データをエントロピ符号化するためにフラグと各シンボルの位置インデックスをエントロピ符号化器３５０に出力する。
【００９９】
一方、本発明の発生モード符号化器３４６及び増加モード符号化器３４８で生成されたインデックスは全てｎＴｒｕｅＯｎｅと称されるフラグを有する。このフラグは元の位置インデックスが反転されたか否かを示すものであって、このフラグが０に設定されれば、現在の位置インデックスは元の位置インデックス値が反転されたということを意味する。このように位置インデックスを反転させる理由は、インデックスに１が多く含まれた場合に反転させることによって０の数を増加させて算術符号化効率を高めるためである。
【０１００】
以下、図９に基づいて本発明のエントロピ符号化方法を説明する。
【０１０１】
本発明のエントロピ符号化器３５０は増加モード符号化器３４８から差分データのシンボルを示すフラグ及び位置インデックスを入力されてエントロピ符号化し、発生モード符号化器３４６から差分データのシンボル及び位置インデックスを入力され、シンボルをｅｎｃｏｄｅＳｉｇｎｅｄＱｕａｓｉＡＡＣ（）関数を用いて符号化する。
【０１０２】
ｅｎｃｏｄｅＳｉｇｎｅｄＱｕａｓｉＡＡＣ（）関数は、入力された値と符号に対するコンテキストを用いて適応算術符号化されたビットストリームを生成するが、この関数は０でない最初のビットを符号化した後に符号が符号化され、残りのビットはゼロコンテキストを用いて符号化される。
【０１０３】
図９は、ｅｎｃｏｄｅＳｉｇｎｅｄＱｕａｓｉＡＡＣ（）関数を用いたシンボルの符号化過程を説明するフローチャートである。
【０１０４】
エントロピ符号化器３５０は符号化する差分データのシンボルと各シンボルのビットサイズＱｂｉｔとを入力される（Ｓ４８１）。
【０１０５】
エントロピ符号化器３５０は先に入力されたビットサイズで２を減算して変数ｉに記憶する（Ｓ４８２）。
【０１０６】
その後、エントロピ符号化器３５０は、エントロピ符号化する値ｎＶａｌｕｅの絶対値を変数ｖａｌに記憶した後、ｖａｌにｉだけＳＲ（Ｓｈｉｆｔ Ｒｉｇｈｔ）演算を行い、ＳＲ演算が行われた結果と“１”とのＡＮＤ演算を行って結果をｂｉｔ変数に記憶する（Ｓ４８３）。
【０１０７】
この段階が最初に実行されれば、エントロピ符号化される入力値のうち符号を除いた最初ビットが検出され、以後の段階で最初ビットに次いで１ビットずつ読み出される。
【０１０８】
エントロピ符号化器３５０は、ｖａｌ値が１以下か否かをチェックし（Ｓ４８４）、ｖａｌが１より大きければｑｆ＿ｅｎｃｏｄｅ（）関数を用いてｂｉｔ値をゼロコンテキストによって符号化する（Ｓ４８５）。一方、ｖａｌ値が１以下であれば、ｑｆ＿ｅｎｃｏｄｅ（）関数を用いてｂｉｔ値をｉ番目のコンテキストに応じて符号化する（Ｓ４８６）。
【０１０９】
エントロピ符号化器３５０はｖａｌ値が１以下であれば、ｖａｌ値が１であるかを再びチェックし（Ｓ４８７）、ｖａｌ値が１であればｎＶａｌｕｅ値の符号を設定し（Ｓ４８８）、設定された符号及び符号コンテキストに応じて符号化する（Ｓ４８９）。
【０１１０】
一方、エントロピ符号化器３５０は１ビットの符号化過程が終了されれば、ｉを１だけ減少し（Ｓ４９０）、減少されたＩが０より小さいかをチェックし（Ｓ４９１）、ｉが０より小さくなるまで、前述した第Ｓ４８３段階ないしＳ４９０段階を反復して入力された値をエントロピ符号化する。
【０１１１】
結果的に、前述した過程によって、エントロピ符号化器３５０は入力された値の０でない最初値は該当ビット位置のコンテキストに応じて符号化し、その後のビットは全てゼロコンテキストに応じて符号化する。
【０１１２】
以下、図２を再び参照して本発明のキー値ヘッダ符号化器３７０でキー値ヘッダに符号化される情報を説明する。
【０１１３】
キー値ヘッダ符号化器３７０は入力座標インタポレータを入力されてデータのモード、各キーフレームの頂点数、頂点数を符号化するのに必要なビット数、及び各実数の最大有効桁数を符号化する。
【０１１４】
一方、キー値ヘッダ符号化器３７０は量子化器３００から量子化ビット数、量子化に必要な各頂点の各成分の最小値及び最大範囲、及び量子化された後の各頂点の各成分の最大値及び最小値を符号化する。
【０１１５】
また、キー値ヘッダ符号化器３７０はＤＰＣＭ処理部３１０から各頂点の各成分データに対して行われたＤＰＣＭ演算モードを入力され、辞書符号化器３４０から辞書符号化モードを入力されて符号化する。
【０１１６】
以下、図１６及び図１７に基づいて本発明の符号化された座標インタポレータを復号化する復号化装置及び復号化方法を説明する。
【０１１７】
図１６は本発明の望ましい実施例に係る復号化装置の構成を示すブロック図であり、図１７は本発明の望ましい実施例に係る復号化方法を説明するフローチャートである。
【０１１８】
図１６を参照すれば、本発明の復号化装置は入力されたビットストリームをエントロピ復号化し、ＤＰＣＭ演算された差分データのシンボル、シンボル設定フラグ、前記シンボルの位置を示すインデックス、及びＤＰＣＭ演算モードを含む辞書復号化されるデータを生成するエントロピ復号化器８００、辞書復号化されるデータのシンボル及びシンボルの位置を示すインデックスに応じて差分データを生成する辞書復号化器８１０、ＤＰＣＭ演算モードに応じて差分データに対して所定の逆ＤＰＣＭ演算を行って量子化されたデータを生成する逆ＤＰＣＭ処理部８３０、量子化されたデータを逆量子化して復元されたキー値データを生成する逆量子化器８５０、及びビットストリームから座標インタポレータの復号化に必要な情報を復号化して辞書復号化器８１０、逆ＤＰＣＭ処理部８３０、及び逆量子化器８５０に出力するキー値ヘッダ復号化器８７０を含む。
【０１１９】
図１７に基づいて本発明の復号化方法を説明する。
【０１２０】
座標インタポレータを符号化したビットストリームはエントロピ復号化器８００に入力されれば（Ｓ９１０）、エントロピ復号化器８００はビットストリームを復号化し、ビットストリームが発生モードで符号化された場合には辞書復号化器８１０に各頂点のシンボル及びシンボルの位置インデックスを出力し、増加モードで符号化された場合にはシンボルの存否を示すシンボルフラグ及びシンボルの位置を示すインデックスを辞書復号化器８１０に出力する（Ｓ９２０）。
【０１２１】
辞書復号化器８１０は入力された辞書符号化モードに応じて入力されたシンボル及びインデックスを発生モード復号化したり、入力されたシンボルフラグ及びインデックスを増加モード復号化して差分データを生成し、生成された差分データを逆ＤＰＣＭ処理部８３０に出力する（Ｓ９３０）。
【０１２２】
逆ＤＰＣＭ処理部８３０は入力された差分データに対して各頂点別に、復号化されたＤＰＣＭモードに応じて逆循環量子化及び逆時間ＤＰＣＭ演算、逆空間ＤＰＣＭ演算、及び逆時空間ＤＰＣＭ演算のうち何れか１つの演算を行って量子化されたキー値データを逆量子化器８５０に出力する（Ｓ９４０）。
【０１２３】
逆量子化器８５０は入力された量子化されたキー値データをキー値ヘッダ復号化器８７０から入力された各成分データの最小値及び最大範囲を用いて逆量子化する（Ｓ９５０）。
【０１２４】
また、逆量子化器８５０は逆量子化されたキー値データ行列が符号化される時、転置行列に変換されたか否かをチェックし（Ｓ９６０）、転置行列に変換されたとすれば、転置行列を逆変換する（Ｓ９６５）。
【０１２５】
逆量子化器８５０は復元された座標インタポレータのキー値データを出力する（Ｓ９７０）。
【０１２６】
以下、図１８ないし図２１をさらに参照して本発明の復号化装置及び方法を詳細に説明する。
【０１２７】
エントロピ復号化器８００は入力ビットストリームからＤＰＣＭモードを示すビットストリームを先に復号化し、ｂＳｅｌＦｌａｇ，ｎＫＶＡＣｏｄｉｎｇＢｉｔ，ｎＱＭｉｎ及びｎＱＭａｘなどのデータ配列を復号化する。
【０１２８】
符号化過程でｂＳｅｌＦｌａｇは初期に１に設定され、ｎＫＶＡＣｏｄｉｎｇＢｉｔは初期に０に設定される。もし、ｂＳｅｌＦｌａｇが１である状態で復号化されるならば、エントロピ復号化器８００は他のデータアレイをｎＫＶＡＣｏｄｉｎｇＢｉｔ，ｎＱＭｉｎ，ｎＱＭａｘ復号化する。しかし、ｂＳｅｌＦｌａｇが０である状態で復号化されるならば、エントロピ復号化器８００はｎＱＭｉｎアレイだけを復号化する。
【０１２９】
エントロピ復号化器８００は、前記アレイを復号化した後、辞書符号化モードを示すｎＤｉｃＭｏｄｅＳｅｌｅｃｔを復号化するが、ｎＤｉｃＭｏｄｅＳｅｌｅｃｔ値に応じて復号化するビットストリームは２種に分類される。
【０１３０】
図２２は、座標インタポレータの各頂点と各頂点の成分データのビットストリーム構造を示す図面である。図２２に示されたように復号化されたｎＤｉｃＭｏｄｅＳｅｌｅｃｔ値が０であれば、ビットストリーム構造は発生モード符号化器で符号化されたシンボル及びインデックスの情報を含み、ｎＤｉｃＭｏｄｅＳｅｌｅｃｔ値が１であれば、ビットストリーム構造は増加モード符号化器で符号化されたシンボルの存否を示すシンボルフラグ及び位置インデックスの情報を含む。
【０１３１】
本発明のエントロピ復号化器は、図３４に示されたプログラムコードで具現されるｄｅｃｏｄｅＳｉｇｎｅｄＱｕａｓｉＡＡＣ（）関数を用いた。この関数は、適応算術符号化されたビットストリームを符号及び値に対するコンテキストを用いて復号化する。この関数は、符号ビット以後に判読されるビットに対してゼロコンテキストを用いて復号化する。エントロピ復号化器は復号化されたデータを辞書復号化器８１０に出力する。
【０１３２】
図１８は、本発明の辞書復号化器８１０の構成を示すブロック図であり、図２０は辞書復号化方法を説明するフローチャートである。
【０１３３】
図１８に示されたように、本発明の辞書復号化器８１０は入力された各頂点のＤＰＣＭモードを復元するＤＰＣＭモード復号化器８１２、入力された各頂点の辞書復号化モードを選択する辞書モード選択部８１４、辞書モード選択部８１４から各頂点の各成分のシンボル及びシンボルの位置インデックスを入力されて差分データを復元する発生モード復号化器８１６、及び辞書モード選択部８１４からシンボルフラグ及びシンボル位置インデックスを入力されて差分データを復元する増加モード復号化器８１８を含む。
【０１３４】
図２０を参照すれば、エントロピ復号化された各頂点のシンボル、シンボルフラグ、及び位置インデックスを含む成分データはＤＰＣＭモード復号化器８１２に入力される（Ｓ９３１）。
【０１３５】
ＤＰＣＭモード復号化器８１２は入力された差分データを逆ＤＰＣＭ処理部８３０に出力する前に、逆ＤＰＣＭ処理部８３０で各頂点の各成分の差分データに対して行われる逆ＤＰＣＭ演算モードを復号化する（Ｓ９３２）。
【０１３６】
以下、図２３を参照してＤＰＣＭモード復号化方法を説明する。
【０１３７】
ＤＰＣＭモード復号化方法は各頂点の各成分のＤＰＣＭモードの組合わせを示すシンボルの数字が２７個に固定され、よってシンボルテーブルの大きさが２７に固定されるという点を除けば、後述する増加モード復号化方法と同一である。
【０１３８】
ＤＰＣＭモード復号化器８１２は入力されたＤＰＣＭモードフラグを入力され、フラグに対応するシンボルを入力されたインデックスに応じてデータ列に記録することになる。
【０１３９】
例えば、図２３に示されたように、入力されたＤＰＣＭモードフラグに対応するシンボルは１（ＴＴＳ），４（ＴＳＳ）及び５（ＴＳＴ＋Ｓ）である、各シンボルに対応するインデックスは（０１０１００），（１０１０）及び（１１）である。したがって、シンボル１に対応するインデックスに応じてシンボル１を記録すればデータ列は（Ｘ１Ｘ１ＸＸ）となり、シンボル４に対応するインデックスに応じてシンボル４を記録すればデータ列は（４１Ｘ１４Ｘ）となり、シンボル５に対応するインデックスに応じてシンボル５を記録すればデータ列は（４１５１４５）となる。
【０１４０】
復元されたデータ列（４１５１４５）を各シンボルに対応するＤＰＣＭモードに変換すれば、（ＴＳＳ）（ＴＴＳ）（ＴＳＴ＋Ｓ）（ＴＴＳ）（ＴＳＳ）（ＴＳＴ＋Ｓ）となる。したがって、各頂点の各成分にいかなるＤＰＣＭ演算が行われたかが分かる。
【０１４１】
ＤＰＣＭモード復号化器８１２は各頂点の各成分の差分データを復号化されたＤＰＣＭモード情報と共に辞書モード選択部８１４に出力する。
【０１４２】
辞書モード選択部８１４は各頂点の各成分のｎＤｉｃＭｏｄｅＳｅｌｅｃｔ値に応じてＤＰＣＭモード復号化器８１２から入力された各成分データを発生モード復号化器８１６または増加モード復号化器に出力する（Ｓ９３４）。
【０１４３】
辞書モード選択部８１４は、ｎＤｉｃＭｏｄｅＳｅｌｅｃｔ値が０であれば、該当頂点の成分データを発生モード復号化器８１６に出力し、ｎＤｉｃＭｏｄｅＳｅｌｅｃｔ値が１であれば該当頂点の成分データを増加モード復号化器８１８に出力する。
【０１４４】
発生モード復号化器８１６は入力された各成分のシンボルデータ及び位置インデックスを差分データに復元する（Ｓ９３６）。
【０１４５】
発生モード復号化方法を例示する図２４を参照すれば、発生モード復号化器８１６は辞書モード選択部８１４からシンボルデータを入力され、ｂＳｏｌｅＫＶ及びｎＴｒｕｅＯｎｅフラグをチェックする。
【０１４６】
ｂＳｏｌｅＫＶフラグが入力されたシンボルが複数存在することを示し、ｎＴｒｕｅＯｎｅフラグが以後に入力される位置インデックスが反転されていないことを示せば、発生モード復号化器８１６は入力されたシンボルを位置インデックスが示す位置のデータ列に挿入することによって差分データを復元する。
【０１４７】
例えば、発生モード復号化器８１６は符号化時の発生順にシンボル３，７，−４を入力され、入力されたそれぞれのシンボルに対応するインデックス（０１０００１０１０００），（１０１０１００）及び（１１１）を入力される。
【０１４８】
発生モード復号化器８１６は最初シンボル３を復元される差分データ列に記録し、以後、入力されたインデックスの１が設定された差分データ列の位置にシンボル３を記録する。したがって、図２４に示されたように、シンボル３の発生モード符号化過程が終了されれば、差分データ列は（３ｘ３ｘｘｘ３ｘ３ｘｘｘ）で書込まれる。
【０１４９】
発生モード復号化器は次のシンボル７を復元する。但し、シンボル７を復元する時、差分データ列で以前シンボル３が記録された位置は考慮しない。したがって、シンボル７に対応するインデックスは（０１０１０００１００）でない（１０１０１００）となる。
【０１５０】
発生モード復号化器８１６は、シンボル７を既に復元されたシンボル３が記録されていない最初位置に記録し、その後、シンボル７に対応するインデックスが１に設定された位置にシンボル７を記録する。したがって、シンボル７が復元された差分データ列は（３７３７ｘ７３ｘ３７ｘｘ）となる。
【０１５１】
発生モード復号化器８１６は最後のシンボル−４をインデックス（１１１）に応じて復元し、最終復元された差分データ列は（３７３７−４７３−４３７４−４）となる。
【０１５２】
一方、前述したｂＳｏｌｅＫＶが１に設定されたならば、これは入力されたシンボルが１つだけ差分データに存在するということを意味するので、入力されたシンボルに対応する位置インデックスは存在せず、よって、発生モード復号化器８１６は入力されたシンボルをシンボルが記録されていない差分データ列の最初位置に記録し、次のシンボルの復元過程を行う。
【０１５３】
一方、増加モード復号化器８１８は入力された各成分のシンボルフラグ及び位置インデックスを差分データに復元する（Ｓ９３６）。以下、増加モード復号化方法の一例を示す図２５に基づいて増加モード復号化方法を説明する。
【０１５４】
増加モード復号化器８１８は辞書モード選択部８１４からシンボルの存否を示すシンボルフラグ、位置インデックスの反転有無を示すｎＴｒｕｅＯｎｅフラグ、及び位置インデックスを入力される。
【０１５５】
増加モード復号化器８１８は入力されたシンボルフラグから差分データに含まれるシンボルを復号化するが、増加モード符号化方法で説明したように、シンボルテーブルは大きさ順に整理され、正数が負数より上位に位置する（Ｉ．Ｅ．０，１，−１，２，−２，３，−３など）。また、シンボルフラグのサイズは２(nKVCodingBit+1)−１であり、ｎＫＶＣｏｄｉｎｇＢｉｔはエントロピ復号化器８００で復号化された量子化ビット数を示す。したがって、シンボルフラグが（００１１００１）であれば、増加モード復号化器８１８は差分データに存在するシンボルで−１，２及び−３を復号化する。
【０１５６】
また、シンボルフラグに次いで入力されたインデックスは（１０１０００１０１０００），（００１０１０１１），（１１１１）であり、これらはシンボル（−１，２，３）に各々対応する。
【０１５７】
増加モード復号化器８１８は最初シンボル−１に対応するインデックス（１０１０００１０１０００）で１と設定された位置に−１を記録する。したがって、最初シンボルに対して復元された差分データ列は（−１ｘ−１ｘｘｘ−１ｘ−１ｘｘｘ）である。
【０１５８】
その後、増加モード復号化器８１８は２番目のシンボル２をインデックス（００１０１０１１）の１が設定された位置に記録してシンボル２を復元する。但し、この場合にも最初シンボル−１が記録された位置は考慮しないために、シンボル２まで記録された差分データ列は（−１ｘ−１ｘ２ｘ−１２−１ｘ２２）である。
【０１５９】
増加モード復号化器８１８は最後のシンボル−３をインデックス（１１１１）の１が設定された位置に記録し、シンボル−３を復元する。最終的に復元された差分データ列は（−１−３−１−３２−３−１２−１−３２２）である。
【０１６０】
前記発生モード復号化器８１６及び増加モード復号化器８１８は各頂点の各成分の差分データを復元し、復元された差分データを逆ＤＰＣＭ処理部８３０に出力する（Ｓ９３９）。
【０１６１】
図１９は本発明の逆ＤＰＣＭ処理部８３０の構成を示すブロック図であり、図２１は逆ＤＰＣＭ演算方法を説明するフローチャートである。
【０１６２】
図１９を参照すれば、本発明の逆ＤＰＣＭ処理部８３０は入力された差分データに逆時間ＤＰＣＭ演算及び逆循環量子化を行って量子化された座標インタポレータのキー値データを出力する逆時間ＤＰＣＭ演算部８４２、入力された差分データに逆空間ＤＰＣＭ演算及び逆循環量子化を行って量子化されたキー値データを出力する逆空間ＤＰＣＭ演算部８４４、入力された差分データに逆時空間ＤＰＣＭ演算及び逆循環量子化を行って量子化されたキー値データを出力する逆時空間ＤＰＣＭ演算部８４６、及び入力された各頂点のＤＰＣＭモードによって辞書復号化器８１０から入力された差分データを逆時間ＤＰＣＭ演算部８４２、逆空間ＤＰＣＭ演算部８４４及び逆時空間ＤＰＣＭ演算部８４６のうち何れか１つに出力する逆ＤＰＣＭモード選択部８３５を含む。
【０１６３】
図２１を参照すれば、逆ＤＰＣＭモード選択部８３５は辞書復号化器８１０のＤＰＣＭモード復号化器８１２で復元された各頂点の各成分のＤＰＣＭ演算モードによって入力された差分データに対して行われる逆ＤＰＣＭ演算を決定し、各頂点の各成分の差分データを決定された逆ＤＰＣＭ演算モードに応じて出力する（Ｓ９４２）。
【０１６４】
各ＤＰＣＭ演算部は入力された差分データに対して逆ＤＰＣＭ演算及び逆循環量子化を同時に行う。
【０１６５】
逆時間ＤＰＣＭ演算部８４２は入力された差分データに対して次の数式８に応じて逆時間ＤＰＣＭ演算を行い（Ｓ９４４）、逆空間ＤＰＣＭ演算部８４４は次の数式９に応じて逆空間ＤＰＣＭ演算を行い（Ｓ９４６）、逆時空間ＤＰＣＭ演算部８４６は次の数式１０に応じて逆時空間ＤＰＣＭ演算を行う（Ｓ９４８）。
【０１６６】
【数８】
0003953411.tif 000017
【０１６７】
【数９】
0003953411.tif 000018
【０１６８】
【数１０】
0003953411.tif 000019
【０１６９】
前記数式において
0003953411.tif 000020
はｉ番目キーフレームのｊ番目の頂点の量子化されたキー値データを、Ｄi,jはｉ番目のキーフレームのｊ番目の頂点の差分データを、Ｒｅｆは基準頂点を各々示す。
【０１７０】
前記数式９及び数式１０において、
0003953411.tif 000021
が量子化された最小値より小さければ、量子化された最小値を前記値の代りに使用し、
0003953411.tif 000022
が量子化された最大値より大きければ量子化された最大値を前記値の代りに使用する。
【０１７１】
逆ＤＰＣＭ演算を行った各ＤＰＣＭ演算部は次の数式１１を用いて逆ＤＰＣＭ演算を行い、同時に逆循環量子化を行って符号化過程で減少された差分データの範囲を広げる。
【０１７２】
【数１１】
0003953411.tif 000023
【０１７３】
0003953411.tif 000024
また、ｎＱＭａｘはＤＰＣＭ演算された差分データのうち最大値を、ｎＱＭｉｎはＤＰＣＭ演算された差分データのうち最小値を示す。
【０１７４】
逆ＤＰＣＭ処理部８３０は、各頂点の各成分に対して逆ＤＰＣＭ演算及び逆循環量子化された量子化されたキー値データを逆量子化器８５０に出力する（Ｓ９４９）。
【０１７５】
図１７を再び参照すれば、逆量子化器８５０はキー値ヘッダ復号化器８７０から入力された各成分データの最小値ｆＭｉｎ＿Ｘ，ｆＭｉｎ＿Ｙ及びｆＭｉｎ＿Ｚ及び最大範囲値ｆＭａｘを前記数式２の関係に応じて２進数体系の実数に変換した後、この値を用いて次の数式１２に応じて入力された量子化されたキー値データを逆量子化する。
【０１７６】
【数１２】
0003953411.tif 000025
【０１７７】
前記数式１２においてｎＫＶＱＢｉｔｓは逆量子化に用いられる量子化ビットサイズである。
【０１７８】
一方、逆量子化器８５０は逆量子化された各頂点の各成分のキー値データを表２に記載された行列形式に出力しなければならない。したがって、逆量子化器８５０はキー値データを出力する前に逆量子化されたキー値データのモードが転置モードかをチェックする（Ｓ９６０）。もし、逆量子化されたキー値データが転置モードであれば、逆量子化器８５０は転置行列を逆変換して復号化された座標インタポレータのキー値データを出力する（Ｓ９６５）。
【０１７９】
以上、本発明の符号化／復号化方法及び装置を説明した。
【０１８０】
以下、図２６ないし図３３に基づき、符号化されたビットストリームを復号化するためのＳＤＬ言語形式のプログラムコード及びこれに用いられた各変数の意味を説明する。
【０１８１】
図２６は圧縮された座標インタポレータのビットストリームを判読するための最上位クラスを示す。
【０１８２】
ＣｏｏｒｄＩＫｅｙＶａｌｕｅＨｅａｄｅｒ及びＣｏｏｒｄＩＫｅｙＶａｌｕｅは従来の座標インタポレータノードのキー値フィールドデータに対応するキー値情報を判読するためのクラスである。ｑｆ＿ｓｔａｒｔ（）関数はビットストリームでＡＡＣ符号化された部分を判読する前に算術復号化器を初期化するために用いられる。
【０１８３】
図２７は、キー値データを復号化するために必要なキー値ヘッダ情報をビットストリームで生成するプログラムコードを示す。
【０１８４】
キー値ヘッダデータは、キーヘッダデータが復号化された後に復号化される。キー値ヘッダの主要な情報は頂点数、キー値データに対する量子化媒介変数、及び量子化のための最大値及び最小値である。ｂＴｒａｎｓｐｏｓｅは転置モードか、あるいは頂点モードかを示すフラグであって、この値が１であれば、復号化時に転置モードが選択され、そうでなければ頂点モードが選択される。ＮＫＶＱＢｉｔは実数を逆量子化して復元するのに用いられる量子化ビットである。ｎＣｏｏｒｄＱＢｉｔは頂点数を示すｎＮｕｍｂｅｒＯｆＣｏｏｒｄを示すビットサイズである。ｎＫＶＤｉｇｉｔは逆量子化された後に用いられ、キー値データの最大有効数字を示す。ＫｅｙＶａｌｕｅＭｉｎＭａｘクラスは逆量子化のための最小値及び最大範囲を復元する。各値は仮数と指数とに分離される。残りのヘッダ情報は、キー値データの各成分の量子化された最大値及び最小値のうち最大値及び最小値を示す。例えば、ｎＸＱＭｉｎＯｆＭａｘは各頂点のＸ成分の量子化された最大値のうち最小値を示す。ｎＮｕｍＫｅｙＣｏｄｉｎｇＢｉｔはキーデータ数を示すｎＮｕｍｂｅｒＯｆＫｅｙのビットサイズを示す。このような情報はキー値データを復号化するために必要である。
【０１８５】
図２８及び図２９は、本発明のＤＰＣＭモードの復号化装置を具現するためのプログラムコードを示す図面であり、各変数の意味は次の通りである。
【０１８６】
ｎＤＰＣＭＭｏｄｅ：この整数配列は、各頂点の各成分（ｘ，ｙ，ｚ）に対するＤＰＣＭモードを示す。この値は時間ＤＰＣＭモードの場合には１を、空間ＤＰＣＭモードの場合には２を、時空間ＤＰＣＭモードの場合には３を各々有する。
【０１８７】
ｂＳｅｌＦｌａｇ：ブール配列は、各頂点の各成分に対する選択フラグを示す。このフラグが１に設定された各頂点の各成分だけ辞書符号化器３４０を用いて符号化される。ｓｅｌｅｃｔｉｏｎＦｌａｇＣｏｎｔｅｘｔはｂＳｅｌＦｌａｇを判読するために用いられるコンテキストである。
【０１８８】
ｎＫＶＡＣｏｄｉｎｇＢｉｔ：この整数配列は、各頂点の各成分の符号化ビットを示す。ＡｑｐＸＣｏｎｔｅｘｔ，ａｑｐＹＣｏｎｔｅｘｔ，ａｑｐＺＣｏｎｔｅｘｔは各々Ｘ，Ｙ，Ｚ軸別にｎＫＶＡＣｏｄｉｎｇＢｉｔの値を判読するためのコンテキストである。
【０１８９】
ｎＲｅｆＶｅｒｔｅｘ：この整数配列は、各頂点に対する基準頂点のインデックスを示す。ｒｅｆＣｏｎｔｅｘｔはｎＲｅｆＶｅｒｔｅｘの値を判読するためのコンテキストである。
【０１９０】
ｎＱＭｉｎ：この整数配列は、各頂点の各成分のＤＰＣＭ演算された差分データのうち最小値を示す。ｑＭｉｎＣｏｎｔｅｘｔはｎＱＭｉｎを判読するためのコンテキストであり、ｑＭｉｎＳｉｇｎＣｏｎｔｅｘｔはｎＱＭｉｎの符号を判読するためのコンテキストである。
【０１９１】
ｎＱＭａｘ：この整数配列は、各頂点の各成分のＤＰＣＭ演算された差分データのうち最大値を示す。ｑＭａｘＣｏｎｔｅｘｔはｎＱＭａｘを判読するためのコンテキストであり、ｑＭａｘＳｉｇｎＣｏｎｔｅｘｔはｎＱＭａｘの符号を判読するためのコンテキストである。
【０１９２】
図３０は、本発明のＤＰＣＭモードを復号化するプログラムコードを示し、各変数の意味は次の通りである。
【０１９３】
ｂＡｄｄｒｅｓｓＯｆＤＰＣＭＭｏｄｅ：このブール配列は、ＤＰＣＭ辞書テーブルの各成分に対するＤＰＣＭモードよりなる各ＤＰＣＭシンボルがどこに利用されたかを示す。１つの頂点には３つの成分があり、各成分には３つのＤＰＣＭモード（Ｔ，Ｓ ａｎｄ Ｔ＋Ｓ）が存在しうる。したがって、前記表３に記載されたようにＤＰＣＭモードの組合わせを示す辞書シンボルは２７個がある。ｄｐｃｍＭｏｄｅＤｉｃＡｄｄｒｅｓｓＣｏｎｔｅｘｔはｂＡｄｄｒｅｓｓＯｆＤＰＣＭＭｏｄｅの値を判読するためのコンテキストである。
【０１９４】
ｂＤＰＣＭＩｎｄｅｘ：ブール配列は各頂点に対して如何なるＤＰＣＭシンボルが利用されたかを示す。ｄｐｃｍＭｏｄｅＤｉｃＩｎｄｅｘＣｏｎｔｅｘｔはｂＤＰＣＭＩｎｄｅｘの値を判読するためのコンテキストである。
【０１９５】
図３１は、本発明の辞書符号化モードを復号化するプログラムコードを示す図面であり、変数の意味は次の通りである。
【０１９６】
ｎＤｉｃＭｏｄｅＳｅｌｅｃｔ：このブール値は辞書符号化に如何なる辞書符号化モードが用いられたかを示すが、その値が１であれば増加モードを、０であれば発生モードを各々示す。
【０１９７】
図３２は、本発明の増加モード復号化方法を具現したプログラムコードであり、変数の意味は次の通りである。
【０１９８】
ｂＡｄｄｒｅｓｓ：このブール配列は、量子化されたキー値を示す各増加モード辞書シンボルの利用有無を示す。増加モードテーブルに用いられるシンボル数は２(nKVCodingBit+1)−１の計算結果と同一である。ｄｉｃＡｄｄｒｅｓｓＣｏｎｔｅｘｔはｂＡｄｄｒｅｓｓの値を判読するためのコンテキストである。
【０１９９】
ｎＴｒｕｅＯｎｅ：このブール配列は、インデックスデータの反転有無を示す。この値が１であればインデックスの１値はシンボルの位置を示す真正値と解釈され、この値が０であればインデックスの０値がシンボルの位置を示す真正値と解釈される。
【０２００】
ｂＡｄｄｒＩｎｄｅｘ：このブール配列は、各頂点の各成分に使われた増加モードシンボルを示す。ｄｉｃＩｎｄｅｘＣｏｎｔｅｘｔはｂＡｄｄｒＩｎｄｅｘの値を判読するためのコンテキストである。
【０２０１】
図３３は、本発明の発生モード復号化方法を具現したプログラムコードであり、変数の意味は次の通りである。
【０２０２】
ｎＱＫＶ：この整数配列は、量子化されたキー値データのモード発生モードのシンボルを含む。ＫｖＸＣｏｎｔｅｘｔ，ｋｖＹＣｏｎｔｅｘｔ及びｋｖＺＣｏｎｔｅｘｔはｎＱＫＶの値を判読するためのコンテキストであり、ｋｖＳｉｇｎＣｏｎｔｅｘｔはｎＱＫＶの符号を判読するためのコンテキストである。
【０２０３】
ｂＳｏｌｅＫＶ：このブール値は、復号化されたシンボルが一回だけ発生するかを示す。もし、発生したシンボルが一回だけ生じるならば、ＳｏｌｅＫＶは１に設定される。ｄｉｃＳｏｌｅＫＶＣｏｎｔｅｘｔはｂＳｏｌｅＫＶの値を判読するためのコンテキストである。
【０２０４】
ｂＤｉｃＩｎｄｅｘ：このブール値は、各頂点の各成分に対して如何なる辞書シンボルが使われたのかを示す。ｄｉｃＩｎｄｅｘＣｏｎｔｅｘｔはｂＤｉｃＩｎｄｅｘの値を判読するためのコンテキストである。
【０２０５】
一方、本発明の座標インタポレータキー値データの符号化及び復号化方法及び従来のＭＰＥＧ−４ ＢＩＦＳ ＰＭＦＣ方法による性能実験結果を示すｒａｔｅ−ｄｉｓｔｏｒｔｉｏｎ曲線を図３５に示した。図３５は３８個の座標インタポレータキー値データに対して符号化を行った結果、現れる符号化ビット率と歪曲の程度を示し、図３５から分かるように、本発明の符号化／復号化方法によればさらに効率的になる。
【０２０６】
また、図３６は、（ａ）元のアニメーションデータ、（ｂ） 本発明によって符号化／復号化されたアニメーションデータ、及び（ｃ） 従来の方法によって符号化／復号化されたアニメーションデータを示す。図３６に示されたように、本発明の符号化／復号化方法によれば、従来の方法により符号化／復号化されたアニメーションより元のアニメーションに近い高画質のアニメーションを提供しうる。
【０２０７】
以上、キーフレーム基盤のアニメーションを表現するための座標インタポレータのキー値データの符号化／復号化方法及び装置の望ましい実施例について説明した。本発明の望ましい実施例に用いられたＤＰＣＭ演算方法は座標インタポレータのキー値データに限定されることではなく、経時的に変化される３次元オブジェクトの複数成分を含む頂点データのＤＰＣＭ演算に適用可能なのは当業者には自明なことである。
【０２０８】
図３７は、本発明に係るＤＰＣＭ演算装置の構成を示すブロック図である。
【０２０９】
図３７を参照すれば、本発明に係るＤＰＣＭ演算装置は時間成分によって変化する３次元オブジェクトの同じ頂点間の差分データを生成する時間ＤＰＣＭ演算部２０１０、同じ時間に各頂点と各頂点に該当する基準頂点間の差分データを生成する空間ＤＰＣＭ演算部２０２０、及び時間及び空間ＤＰＣＭ演算部２０２０から入力された差分データのうち最小の差分データを出力するＤＰＣＭモード選択部２０３０を含む。
【０２１０】
望ましくは、本発明のＤＰＣＭ演算装置は空間ＤＰＣＭ演算部２０２０で計算された同じ頂点の差分データ間の時間変化による差分データを計算する時空間ＤＰＣＭ演算部２０４０をさらに含み、この場合にＤＰＣＭモード選択部２０３０は時間、空間及び時空間ＤＰＣＭ演算部２０４０から入力された差分データのうち最小の差分データを出力する。
【０２１１】
各構成要素の動作は前述したＤＰＣＭ処理部に含まれた構成要素の動作と同一である。
【０２１２】
本発明のＤＰＣＭ演算装置は外部から量子化された３次元オブジェクトの頂点座標データを入力される。
【０２１３】
時間ＤＰＣＭ演算部２０１０は入力された頂点座標データに対し、前述した数式３を用いて現在のオブジェクトを表現する頂点座標データと過去のオブジェクトを表現する同じ頂点座標データとの差分データを計算する。
【０２１４】
一方、空間ＤＰＣＭ演算部２０２０は、入力された頂点座標データに対し、前述した数式５を用いて同じ時間軸上に位置し、まずＤＰＣＭ演算が行われた他の頂点と現在入力された頂点間の差分データを計算し、そのうち最小の差分データを有する頂点を基準頂点と選択し、その時の差分データを出力する。
【０２１５】
ＤＰＣＭモード選択部２０３０は、時間ＤＰＣＭ演算部２０１０及び空間ＤＰＣＭ演算部２０２０から入力された差分データの大きさを計算し、最小の差分データをＤＰＣＭ演算情報と共に出力する。
【０２１６】
一方、このＤＰＣＭ演算装置の望ましい実施例に含まれる時空間ＤＰＣＭ演算部２０４０は前述した数式６を用いて入力された３次元オブジェクトの量子化された座標データに前述した空間ＤＰＣＭ演算を行い、現在の頂点の空間ＤＰＣＭ演算結果と過去の同じ頂点の空間ＤＰＣＭ演算結果との時間ＤＰＣＭ演算を行う。
【０２１７】
また、このＤＰＣＭ演算装置の望ましい実施例に含まれる循環量子化器２０５０は前述した数式７を用いて入力された差分データの範囲を狭める。
【０２１８】
図３８は、本発明のＤＰＣＭ演算装置によって生成された差分データを量子化された座標データに変換する逆ＤＰＣＭ演算装置の構成を示すブロック図である。
【０２１９】
本発明の逆ＤＰＣＭ演算装置は同じ頂点の時間変化による差分データに対して逆ＤＰＣＭ演算を行う逆時間ＤＰＣＭ演算部２１１０、同じ時間の各頂点と前記各頂点に対応する基準頂点との差分データに対して逆ＤＰＣＭ演算を行う逆空間ＤＰＣＭ演算部２１２０、及び入力差分データに含まれたＤＰＣＭ演算モードに応じて入力差分データを逆時間ＤＰＣＭ演算部２１１０または逆空間ＤＰＣＭ演算部２１２０に出力する逆ＤＰＣＭモード選択部２１００を含む。
【０２２０】
望ましくは、本発明の逆ＤＰＣＭ演算装置は現在逆空間ＤＰＣＭ演算された結果と以前に逆空間ＤＰＣＭ演算された結果とに対して逆時間ＤＰＣＭ演算を行う逆時空間ＤＰＣＭ演算部２１３０をさらに含む。
【０２２１】
逆ＤＰＣＭ演算装置に含まれた各構成要素の動作は前述した逆ＤＰＣＭ処理部に含まれた構成要素の動作と同一である。
【０２２２】
量子化された座標データに復元される差分データは逆ＤＰＣＭモード選択部２１００に入力され、逆ＤＰＣＭモード選択部２１００は入力された差分データに含まれた各頂点の各成分データに対して行われたＤＰＣＭ演算の種類を判読し、入力された頂点の各成分データを逆時間ＤＰＣＭ演算部２１１０、逆空間ＤＰＣＭ演算部２１２０、及び逆時空間ＤＰＣＭ演算部２１３０のうち何れか１つに出力する。
【０２２３】
入力された差分データに対して逆時間ＤＰＣＭ演算部２１１０は前述した数式８に応じて逆時間ＤＰＣＭ演算を行い、逆空間ＤＰＣＭ演算部２１２０は前述した数式９に応じて逆空間ＤＰＣＭ演算を行い、逆時空間ＤＰＣＭ演算部２１３０は前述した数式１０に応じて逆時空間ＤＰＣＭ演算を行う。
【０２２４】
また、入力された差分データが循環量子化が行われた差分データである場合には、逆ＤＰＣＭ演算を行った各ＤＰＣＭ演算部は前述した数式１１を用いて逆ＤＰＣＭ演算を行いつつ逆循環量子化を行って減少された差分データの範囲を広げる。
【０２２５】
また、本発明はコンピュータにて読出可能な記録媒体にコンピュータにて読出可能なコードとして具現可能である。コンピュータにて読出可能な記録媒体には、コンピュータシステムによって読出されるデータが記憶されるあらゆる種類の記録装置を含む。コンピュータにて読出可能な記録媒体の例としては、ＲＯＭ、ＲＡＭ、ＣＤ−ＲＯＭ、磁気テープ、フレキシブルディスク、光データ記憶装置などがあり、またキャリアウェーブ（例えば、インターネットを介した伝送）の形にで具現されるものも含む。また、コンピュータにて読出可能な記録媒体はネットワークで連結されたコンピュータシステムに分散され、分散方式によりコンピュータにて読出可能なコードが記憶されて実行されうる。
【０２２６】
以上、本発明についてその望ましい実施例を中心に説明した。本発明が属する技術分野で当業者なら、本発明が本発明の本質的な特性から外れない範囲で変形された形で具現可能なのを理解しうる。したがって、開示された実施例は限定的な観点でなく、説明的な観点で考慮されねばならない。本発明の範囲は前述した説明でなく、特許請求の範囲上に示されており、それと同等な範囲内にあるあらゆる違いは本発明に含まれたものと解釈せねばならない。
【０２２７】
【発明の効果】
本発明の座標インタポレータのキー値データ符号化方法及び装置は、座標インタポレータの各頂点間の座標データの差分データだけでなく、各頂点の座標データのキーフレーム間の差分データを共に考慮して座標インタポレータのキー値データを符号化するので、さらなる符号化効率が得られる。
【０２２８】
また、本発明の符号化方法及び装置は生成された差分データを差分値を示すシンボルとシンボルとの位置を示す位置インデックスにて表現することによって、さらなる符号化効率が得られる。
【図面の簡単な説明】
【図１】従来の座標インタポレータキー値データの符号化装置及び復号化装置の構成を示すブロック図である。
【図２】本発明の望ましい実施例に係る座標インタポレータキー値データの符号化装置の構成を示すブロック図である。
【図３】本発明の望ましい実施例に係る座標インタポレータキー値データの符号化方法を説明するフローチャートである。
【図４】本発明の望ましい実施例に係るＤＰＣＭ処理部の構成を示すブロック図である。
【図５】本発明の望ましい実施例に係る辞書符号化器の構成を示すブロック図である。
【図６】本発明の望ましい実施例に係る量子化方法を説明するフローチャートである。
【図７】本発明の望ましい実施例に係るＤＰＣＭ演算方法を説明するフローチャートである。
【図８】本発明の望ましい実施例に係る辞書符号化方法を説明するフローチャートである。
【図９】本発明の望ましい実施例に係るエントロピ符号化方法を説明するフローチャートである。
【図１０】本発明の量子化されたキー値データを示す図面である。
【図１１】本発明のＤＰＣＭ演算されたキー値データを示す図面である。
【図１２】本発明の循環量子化されたキー値データを示す図面である。
【図１３】本発明の望ましい実施例に係るＤＰＣＭモード符号化方法を説明する図面である。
【図１４】本発明の望ましい実施例に係る発生モード符号化方法を説明する図面である。
【図１５】本発明の望ましい実施例に係る増加モード符号化方法を説明する図面である。
【図１６】本発明の望ましい実施例に係る復号化装置の構成を示すブロック図である。
【図１７】本発明の望ましい実施例に係る復号化方法を説明するフローチャートである。
【図１８】本発明の望ましい実施例に係る辞書復号化器の構成を示すブロック図である。
【図１９】本発明の望ましい実施例に係る逆ＤＰＣＭ処理部の構成を示すブロック図である。
【図２０】本発明の望ましい実施例に係る辞書復号化方法を説明するフローチャートである。
【図２１】本発明の望ましい実施例に係る逆ＤＰＣＭ演算方法を説明するフローチャートである。
【図２２】座標インタポレータの各頂点と各頂点の成分データのビットストリーム構造を示す図面である。
【図２３】ＤＰＣＭモード復号化方法を説明する図面である。
【図２４】発生モード復号化方法を説明する図面である。
【図２５】増加モード復号化方法を説明する図面である。
【図２６】本発明の望ましい実施例に係る復号化過程でビットストリームを判読するためのプログラムコード（ＳＤＬ言語）の最上位クラスの例を示す図面である。
【図２７】本発明の望ましい実施例に係る復号化過程でキー値データを復号化するために必要なキー値ヘッダ情報をビットストリームで生成するプログラムコードである。
【図２８】本発明の望ましい実施例に係るＤＰＣＭモードの復号化装置を実現するためのプログラムコードである。
【図２９】本発明の望ましい実施例に係るＤＰＣＭモードの復号化装置を実現するためのプログラムコードである。
【図３０】本発明の望ましい実施例に係るＤＰＣＭモードを復号化するプログラムコードである。
【図３１】本発明の望ましい実施例に係る辞書符号化モードを復号化するプログラムコードである。
【図３２】本発明の望ましい実施例に係る増加モード復号化方法を実現するためのプログラムコードである。
【図３３】本発明の望ましい実施例に係る発生モード復号化方法を実現するためのプログラムコードである。
【図３４】本発明の望ましい実施例に係るエントロピ復号化器で用いられるｄｅｃｏｄｅＳｉｇｎｅｄＱｕａｓｉＡＡＣ（）関数のプログラムコードである。
【図３５】本発明に係る座標インタポレータのキー値データの符号化／復号化方法と従来の技術による符号化／復号化方法の性能を比較したrate-distribution曲線を示すグラフである。
【図３６】本発明に係る座標インタポレータのキー値データの符号化／復号化方法と従来の技術による符号化／復号化方法の性能を比較した図面であり、（ａ）は元のアニメーションデータ、（ｂ）は本発明によって符号化／復号化されたアニメーションデータ、（ｃ）は従来の方法によって符号化／復号化されたアニメーションデータである。
【図３７】本発明のＤＰＣＭ演算装置の構成を示すブロック図である。
【図３８】本発明の逆ＤＰＣＭ演算装置の構成を示すブロック図である。
【符号の説明】
３００      量子化器
３１０      ＤＰＣＭ処理部
３４０      辞書符号化器
３５０      エントロピ符号化器
【図１】
0003953411.tif 000026
【図２】
0003953411.tif 000027
【図３】
0003953411.tif 000028
【図４】
0003953411.tif 000029
【図５】
0003953411.tif 000030
【図６】
0003953411.tif 000031
【図７】
0003953411.tif 000032
【図８】
0003953411.tif 000033
【図９】
0003953411.tif 000034
【図１０】
0003953411.tif 000035
【図１１】
0003953411.tif 000036
【図１２】
0003953411.tif 000037
【図１３】
0003953411.tif 000038
【図１４】
0003953411.tif 000039
【図１５】
0003953411.tif 000040
【図１６】
0003953411.tif 000041
【図１７】
0003953411.tif 000042
【図１８】
0003953411.tif 000043
【図１９】
0003953411.tif 000044
【図２０】
0003953411.tif 000045
【図２１】
0003953411.tif 000046
【図２２】
0003953411.tif 000047
【図２３】
0003953411.tif 000048
【図２４】
0003953411.tif 000049
【図２５】
0003953411.tif 000050
【図２６】
0003953411.tif 000051
【図２７】
0003953411.tif 000052
【図２８】
0003953411.tif 000053
【図２９】
0003953411.tif 000054
【図３０】
0003953411.tif 000055
【図３１】
0003953411.tif 000056
【図３２】
0003953411.tif 000057
【図３３】
0003953411.tif 000058
【図３４】
0003953411.tif 000059
【図３５】
0003953411.tif 000060
【図３６】
0003953411.tif 000061
【図３７】
0003953411.tif 000062
【図３８】
0003953411.tif 000063