(57)【特許請求の範囲】
【請求項１】
キーフレームが位置する時間情報のキーデータ及び前記キーフレームで表されるオブジェクトの回転情報を示すキー値データを含む回転インタポレータを符号化する装置であって、
入力回転インタポレータよりなる第１のアニメーション経路と、前記第１のアニメーション経路から抽出された分節点によって生成される第２のアニメーション経路間の誤差を所定の臨界値以下にする最小数の分節点を前記第１のアニメーション経路から抽出し、抽出された分節点に含まれたキーデータ及びキー値データを出力する分節点抽出部と、
前記分節点抽出部から入力されたキーデータの範囲を減少させて符号化するキー符号化器と、
現在のキーフレームのキー値データと以前のキーフレームのキー値データによってオブジェクトに適用される回転変換の差だけオブジェクトを回転変換させる回転差分値を生成し、前記分節点抽出部から入力されたキー値データを符号化するキー値符号化器と、を含むことを特徴とする符号化装置。
【請求項２】
前記第１のアニメーション経路を、一定の時間間隔を有する所定数の区間にサンプリングし、リサンプリングされたキーデータ及びキー値データを含む回転インタポレータを前記キー符号化器及びキー値符号化器に各々出力するリサンプリング部と、
外部入力信号に応じて入力回転インタポレータを前記リサンプリング部または前記分節点抽出部に出力する選択部と、をさらに含むことを特徴とする請求項１に記載の符号化装置。
【請求項３】
前記第１のアニメーション経路を、一定の時間間隔を有する所定数の区間にサンプリングし、リサンプリングされたキーデータ及びキー値データを含む回転インタポレータを出力するリサンプリング部をさらに含み、
前記分節点抽出部は、前記リサンプリング部から入力された回転インタポレータよりなる経路の分節点を抽出することを特徴とする請求項１に記載の符号化装置。
【請求項４】
前記分節点抽出部から抽出された回転インタポレータよりなるアニメーション経路を一定の時間間隔を有する所定数の区間にサンプリングしてリサンプリングされたキーデータ及びキー値データを含む回転インタポレータを前記キー符号化器及びキー値符号化器に出力するリサンプリング部をさらに含むことを特徴とする請求項１に記載の符号化装置。
【請求項５】
前記リサンプリング部は、回転インタポレータのキーデータ及びキー値データに応じるアニメーション経路を一定の時間間隔を有する所定数の時間区間に分割し、各区間の境界点を符号化するキーデータに、前記各区間でのアニメーション経路上のキー値データを符号化するキー値データに設定して出力することを特徴とする請求項２ないし４のうち何れか１項に記載の符号化装置。
【請求項６】
前記分節点抽出部は、
入力されたアニメーション経路の開始経路点と終了経路点とを抽出し、抽出されていない経路点を１つずつ選択し、選択されていない残りの経路点を前記選択された経路点から球面線形補間する線形補間部と、
入力されたアニメーション経路と前記球面線形補間部で球面線形補間によって生成されたアニメーション経路間の誤差を計算する誤差計算部と、
前記誤差が最小となる分節点を抽出し、抽出された分節点に応じる誤差が所定の臨界値以下であるかを比較し、前記抽出された分節点を出力する判断部と、を含むことを特徴とする請求項１ないし４のうち何れか１項に記載の符号化装置。
【請求項７】
前記抽出された分節点に応じる誤差が所定の臨界値より大きい場合、前記判断部は前記選択された分節点を前記線形補間部に出力し、前記線形補間部は前記判断部から入力された分節点を除いた経路点を１つずつ選択して球面線形補間することを特徴とする請求項６に記載の符号化装置。
【請求項８】
前記誤差計算部は、
経路点に含まれる１つの基準成分に応じて前記入力されたアニメーション経路と前記球面線形補間によって生成されたアニメーション経路とを所定の区間に分割し、分割された区間の面積を求めて各区間の誤差を計算することを特徴とする請求項６に記載の符号化装置。
【請求項９】
前記キー符号化器は、
前記分節点抽出部から入力されたキーデータを所定の量子化ビット数で量子化し、量子化されたキーデータに所定のＤＰＣＭ演算を行って差分データを生成し、前記差分データを符号化することを特徴とする請求項１に記載の符号化装置。
【請求項１０】
前記キー符号化器は、
前記分節点抽出部から入力された回転インタポレータのキーデータを所定の量子化ビット数で量子化する第１量子化器と、
前記量子化されたキーデータの差分データを生成する第１ＤＰＣＭ処理部と、前記差分データと前記差分データの最大値及び最小値との関係に応じて前記差分データの範囲を減らすＤＮＤ演算を行うＤＮＤ処理部と、
前記ＤＮＤ処理部から入力された差分データを符号化する第１エントロピ符号化器と、を含むことを特徴とする請求項１に記載の符号化装置。
【請求項１１】
前記キー符号化器は、
入力される全体キーデータのうちキーデータが線形に増加する領域を識別して符号化する線形キー符号化器をさらに含むことを特徴とする請求項１０に記載の符号化装置。
【請求項１２】
前記キー符号化器は、
前記第１ＤＰＣＭ処理部から入力された差分データのうち最高頻度数の差分データ（モード）を求め、前記差分データで前記モードを減算するシフト部と、前記シフト演算された差分データを正数または負数領域に変換するフォルド処理部とをさらに含み、
前記ＤＮＤ処理部は符号化に必要なビット数に応じて前記シフト部から入力された差分データ、前記フォルド処理部から入力された差分データ、及びＤＮＤ演算された差分データのうち何れか１つを選択して出力することを特徴とする請求項１０に記載の符号化装置。
【請求項１３】
前記キー値符号化器は、
現在のキーフレームの回転変換値と、以前のキーフレームの復元された回転変換値とを用いて、現在のキーフレームのキー値データと以前のキーフレームのキー値データによってオブジェクトに適用される回転変換の差だけ前記オブジェクトを回転変換させる回転差分値を生成し、前記回転差分値を量子化して回転差分データを出力する回転差分データ生成部と、
前記回転差分データをエントロピ符号化するエントロピ符号化器と、を含むことを特徴とする請求項１に記載の符号化装置。
【請求項１４】
前記回転差分データ生成部は、
前記回転差分値のうち３成分値を量子化して回転差分データを生成する量子化部と、
入力された回転差分データの３成分値を調整する量子化データ調整部と、
前記調整された成分値を逆量子化する逆量子化部と、
逆量子化された前記３成分値を用いて量子化されていない１成分値を復元し、復元された回転差分値を生成する回転差分値復元部と、
量子化器に入力された回転差分値と前記復元された回転差分値間の誤差値を測定し、前記誤差値が最小となる調整された回転差分データを出力する誤差測定部と、を含むことを特徴とする請求項１３に記載の符号化装置。
【請求項１５】
前記回転差分データ生成部は、
現在キーフレームでのオブジェクトの回転変換値と復元された以前キーフレームでのオブジェクトの回転変換値とを用いて前記回転差分値を生成する第１クォータニオン乗算器と、
前記回転差分値を量子化して回転差分データを生成する量子化器と、
前記回転差分データを逆量子化し、復元された回転差分値を生成する逆量子化器と、
前記復元された回転差分値を以前キーフレームの回転変換値にクォータニオン乗算して現在のキーフレームの復元された回転変換値を生成する第２クォータニオン乗算器と、を含むことを特徴とする請求項１３に記載の符号化装置。
【請求項１６】
前記回転差分データ生成部は、
現在のキーフレームでのオブジェクトの回転変換値と以前のキーフレームの復元された回転変換値に応じて、元のオブジェクトの回転方向と復号化されたオブジェクトの回転方向とが反対になる回転方向誤差の発生有無を検出する回転方向誤差検出部と、
元のオブジェクトの回転方向と復号化されたオブジェクトの回転方向とが同一になるように前記回転差分値を訂正して出力する回転方向訂正部と、
前記回転方向誤差検出部から入力された回転方向誤差の発生有無により、前記回転差分値及び回転方向訂正部から入力された回転差分値のうち何れか１つを量子化する差分データとして選択する回転方向選択部と、を含むことを特徴とする請求項１３に記載のキー値データ符号化装置。
【請求項１７】
キーフレームが位置する時間情報のキーデータ及び前記キーフレームで表されるオブジェクトの回転情報を示すキー値データを含む回転インタポレータを符号化する装置であって、
入力回転インタポレータよりなるアニメーション経路を一定の時間間隔を有する所定数の区間にサンプリングし、リサンプリングされたキーデータ及びキー値データを含む回転インタポレータを出力するリサンプリング部と、
前記リサンプリング部から入力されたキーデータを符号化するキー符号化器と、
現在のキーフレームのキー値データと以前のキーフレームのキー値データによってオブジェクトに適用される回転変換の差だけオブジェクトを回転変換させる回転差分値を生成し、前記分節点抽出部から入力されたキー値データを符号化するキー値符号化器と、を含むことを特徴とする符号化装置。
【請求項１８】
前記リサンプリング部は、
回転インタポレータのキーデータ及びキー値データに応じるアニメーション経路を一定の時間間隔を有する所定数の時間区間に分割し、各区間の境界点を符号化するキーデータに、前記各区間でのアニメーション経路上のキー値データを符号化するキー値データに設定して出力することを特徴とする請求項１７に記載の符号化装置。
【請求項１９】
前記キー符号化器は、
入力される全体キーデータのうちキーデータが線形に増加する領域を識別して符号化する線形キー符号化器を含むことを特徴とする請求項１７に記載の符号化装置。
【請求項２０】
前記キー値符号化器は、
現在キーフレームの回転変換値及び以前キーフレームの復元された回転変換値を用いて、現在のキーフレームのキー値データと以前のキーフレームのキー値データによってオブジェクトに適用される回転変換の差だけ前記オブジェクトを回転変換させる回転差分値を生成し、前記回転差分値を量子化して回転差分データを出力する回転差分データ生成部と、
前記回転差分データをエントロピ符号化するエントロピ符号化器と、を含むことを特徴とする請求項１７に記載の符号化装置。
【請求項２１】
前記回転差分データ生成部は、
前記回転差分値のうち３成分値を量子化して回転差分データを生成する量子化部と、
入力された回転差分データの３成分値を調整する量子化データ調整部と、
前記調整された成分値を逆量子化する逆量子化部と、
逆量子化された前記３成分値を用いて量子化されていない１成分値を復元し、復元された回転差分値を生成する回転差分値復元部と、
量子化器に入力された回転差分値と前記復元された回転差分値間の誤差値を測定し、前記誤差値が最小となる調整された回転差分データを出力する誤差測定部と、を含むことを特徴とする請求項２０に記載の符号化装置。
【請求項２２】
前記回転差分データ生成部は、
現在のキーフレームの回転変換値と、以前のキーフレームの復元された回転変換値とを用いて前記回転差分値を生成する第１クォータニオン乗算器と、
前記回転差分値を量子化して回転差分データを生成する量子化器と、
前記回転差分データを逆量子化して復元された回転差分値を生成する逆量子化器と、
前記復元された回転差分値を以前キーフレームの回転変換値にクォータニオン乗算して現在キーフレームの復元された回転変換値を生成する第２クォータニオン乗算器と、を含むことを特徴とする請求項２０に記載の符号化装置。
【請求項２３】
前記回転差分データ生成部は、
現在キーフレームでのオブジェクトの回転変換値と以前キーフレームの復元された回転変換値とに応じて、元のオブジェクトの回転方向と復号化されたオブジェクトの回転方向とが反対となる回転方向誤差の発生有無を検出する回転方向誤差検出部と、
元のオブジェクトの回転方向と復号化されたオブジェクトの回転方向とが同一になるように前記回転差分値を訂正して出力する回転方向訂正部と、
前記回転方向誤差検出部から入力された回転方向誤差の発生有無により、前記回転差分値及び回転方向訂正部から入力された回転差分値のうち何れか１つを量子化する差分データとして選択する回転方向選択部と、を含むことを特徴とする請求項２０に記載のキー値データ符号化装置。
【請求項２４】
キーフレームの時間軸上の位置を示すキーデータ及び前記キーフレーム上のオブジェクトの回転情報を示すキー値データを含む回転インタポレータを符号化したビットストリームを復号化する装置であって、
入力ビットストリームからキーデータを復号化するキーデータ復号化器と、
前記入力ビットストリームからキー値データを復号化するキー値データ復号化器と、
復号化されたキー値データ及び前記復号化されたキー値データから球面線形補間されたキー値データを復号化されたキーデータと合成して回転インタポレータを生成するインタポレータ合成器と、を含むことを特徴とする復号化装置。
【請求項２５】
前記インタポレータ合成器は、
現在合成するキーデータに対応する復号化されたキー値データがない場合には、以前に合成されたキーデータに対応する復号化されたキー値データと、以後に合成されるキーデータに対応する復号化されたキー値データとを用いて、現在合成するキーデータに対応するキー値データを球面線形補間することを特徴とする請求項２４に記載の復号化装置。
【請求項２６】
前記キーデータ復号化器は、
前記入力ビットストリームをエントロピ復号化して差分データを生成するエントロピ復号化器と、
前記差分データに所定の逆ＤＰＣＭ演算を行って量子化されたキーデータを生成する逆ＤＰＣＭ処理部と、
前記量子化されたキーデータを逆量子化して復元されたキーデータを生成する逆量子化器と、を含むことを特徴とする請求項２４に記載の復号化装置。
【請求項２７】
前記キー値データ復号化器は、
前記ビットストリームからキー値データをエントロピ復号化して循環ＤＰＣＭ演算された回転差分データまたは量子化された回転差分データを生成するエントロピ復号化器と、
前記ビットストリームから復号化されたＤＰＣＭ演算が行われた回数であるＤＰＣＭ次数に応じてエントロピ復号化器から入力された回転差分データに対して逆循環ＤＰＣＭ演算を行って量子化された回転差分データを生成する逆循環ＤＰＣＭ演算部と、
前記量子化された回転差分データを逆量子化し、各キーフレームのクォータニオンキー値データによってオブジェクトに適用される回転変換の差だけオブジェクトを回転変換させる回転差分値を生成する逆量子化器と、
現在キーフレームの回転差分値を復号化された以前キーフレームの回転変換値とクォータニオン乗算して現在キーフレームの回転変換値を生成するクォータニオン乗算器と、を含むことを特徴とする請求項２４に記載の復号化装置。
【請求項２８】
キーフレームが位置する時間情報のキーデータ及びオブジェクトの回転情報を示すキー値データを含む回転インタポレータを符号化する方法であって、
（ｂ）分節点抽出部が、前記回転インタポレータよりなる第１のアニメーション経路と前記第１のアニメーション経路から抽出された分節点によって生成される第２のアニメーション経路間の誤差を所定の臨界値以下にする最小数の分節点を前記第１のアニメーション経路から抽出して符号化するキーデータ及びキー値データを生成する段階と、
（ｄ）キー符号化器が、前記（ｂ）段階で抽出されたキーデータの範囲を減少させて符号化するキー符号化段階と、
（ｅ）キー値符号化器が、前記（ｂ）段階で抽出されたキー値データに対して、現在のキーフレームのキー値データと以前のキーフレームのキー値データによってオブジェクトに適用される回転変換の差だけオブジェクトを回転変換させる回転差分値を生成して符号化することによって、キー値データを符号化するキー値符号化段階と、を含むことを特徴とする符号化方法。
【請求項２９】
前記（ｂ）段階は、
（ｂ１）線形補間部が、前記第１のアニメーション経路の開始経路点と終了経路点とを抽出する段階と、
（ｂ２）線形補間部が、抽出されていない経路点を１つずつ選択し、選択されていない残りの経路点を前記抽出された経路点から球面線形補間する段階と、
（ｂ３）誤差計算部が、前記第１のアニメーション経路と前記（ｂ２）段階で球面線形補間によって生成された第２のアニメーション経路間の誤差を計算する段階と、
（ｂ４）判断部が、前記誤差が最小となる分節点を抽出し、抽出された分節点に応じる誤差を所定の臨界値と比較し、符号化するキーデータ及びキー値データを決定する段階と、を含むことを特徴とする請求項２８に記載の符号化方法。
【請求項３０】
前記（ｂ）段階前に、
（ａ）リサンプリング部が、前記第１のアニメーション経路を一定の時間間隔を有する所定数の区間にサンプリングし、リサンプリングされたキーデータ及びキー値データを含む回転インタポレータを生成する段階をさらに含み、前記（ｂ）段階は、分節点抽出部が、前記リサンプリング段階で生成された回転インタポレータよりなる経路の分節点を抽出することを特徴とする請求項２８に記載の符号化方法。
【請求項３１】
前記（ａ）段階は、
リサンプリング部が、前記第１のアニメーション経路を一定の時間間隔を有する所定数の時間区間に分割し、各区間の境界点をサンプリングされたキーデータに、前記各区間でのアニメーション経路上のキー値データをサンプリングされたキー値データに設定することを特徴とする請求項３０に記載の符号化方法。
【請求項３２】
前記（ｂ）段階以後に、
（ｃ）リサンプリング部が、前記抽出された分節点に応じる第２のアニメーション経路を一定の時間間隔を有する所定数の区間にサンプリングし、符号化するキーデータ及びキー値データを生成するリサンプリング段階を含むことを特徴とする請求項２８に記載の符号化方法。
【請求項３３】
前記（ｄ）段階は、
キー符号化器が、前記キーデータを所定の量子化ビット数で量子化する段階と、キー符号化器が、量子化されたキーデータに所定のＤＰＣＭ演算を行って差分データを生成する段階と、キー符号化器が、前記差分データをエントロピ符号化する段階と、を含むことを特徴とする請求項２８に記載の符号化方法。
【請求項３４】
前記（ｅ）段階は、
（ｅ１）回転差分データ生成部が、現在のキーフレームの回転変換値と、以前のキーフレームの復元された回転変換値とを用いて、現在のキーフレームのキー値データ及び以前のキーフレームのキー値データによってオブジェクトに適用される回転変換の差だけ前記オブジェクトを回転変換させる回転差分値を生成し、前記回転差分値を量子化して回転差分データを生成する段階と、
（ｅ２）エントロピ符号化器が、前記回転差分データをエントロピ符号化する段階と、を含むことを特徴とする請求項２８に記載の符号化方法。
【請求項３５】
前記（ｅ１）段階は、
（ｅ１１）量子化部が、前記回転差分値のうち３成分値を量子化して回転差分データを生成する段階と、
（ｅ１２）量子化データ調整部が、前記回転差分データの３成分値を調整する段階と、
（ｅ１３）逆量子化部が、前記調整された成分値を逆量子化する段階と、
（ｅ１４）回転差分値復元部が、逆量子化された前記３成分値を用いて量子化されていない１成分値を復元し、復元された回転差分値を生成する段階と、
（ｅ１５）誤差測定部が、前記回転差分値と前記復元された回転差分値間の誤差値を測定し、前記誤差値が最小となる調整された回転差分データをエントロピ符号化される回転差分データとして決定する段階と、を含むことを特徴とする請求項３４に記載の符号化方法。
【請求項３６】
前記（ｅ１）段階は、
（ｅ１１）第１クォータニオン乗算器が、現在キーフレームでのオブジェクトの回転変換値と復元された以前キーフレームでのオブジェクトの回転変換値とを用いて前記回転差分値を生成する段階と、
（ｅ１２）量子化器が、前記回転差分値を量子化して回転差分データを生成する段階と、
（ｅ１３）逆量子化器が、前記回転差分データを逆量子化し、復元された回転差分値を生成する段階と、
（ｅ１４）第２クォータニオン乗算器が、前記復元された回転差分値を以前キーフレームの回転変換値にクォータニオン乗算して現在キーフレームの復元された回転変換値を生成する段階と、を含むことを特徴とする請求項３４に記載の符号化方法。
【請求項３７】
前記（ｅ１）段階は、
（ｅ１１）回転方向誤差検出部が、現在キーフレームでの回転変換値と以前キーフレームの復元された回転変換値に応じて、元のオブジェクトの回転方向と復号化されたオブジェクトの回転方向が反対となる回転方向誤差の発生有無を検出する段階と、
（ｅ１２）回転方向訂正部が、元のオブジェクトの回転方向と復号化されたオブジェクトの回転方向とが同一になるように前記回転差分値を訂正する段階と、
（ｅ１３）回転方向選択部が、前記（ｅ１１）段階で検出された回転方向誤差の発生有無により、前記回転差分値及び前記（ｅ１２）段階で訂正された回転差分値のうち何れか１つを量子化する差分データとして選択する段階と、を含むことを特徴とする請求項３４に記載の符号化方法。
【請求項３８】
キーフレームが位置する時間情報のキーデータ及びオブジェクトの回転情報を示すキー値データを含む回転インタポレータを符号化する方法であって、
（ａ）リサンプリング部が、前記回転インタポレータよりなるアニメーション経路を一定の時間間隔を有する所定数の区間にサンプリングし、リサンプリングされたキーデータ及びキー値データを含む回転インタポレータを生成する段階と、
（ｄ）キー符合化器が、前記（ａ）段階でサンプリングされたキーデータの範囲を減少させて符号化するキー符号化段階と、
（ｅ）キー値符合化器が、前記（ａ）段階でサンプリングされたキー値データに対して、現在のキーフレームのキー値データと以前のキーフレームのキー値データによってオブジェクトに適用される回転変換の差だけオブジェクトを回転変換させる回転差分値を生成して符号化することによってキー値データを符号化するキー値符号化段階と、を含むことを特徴とする符号化方法。
【請求項３９】
前記（ａ）段階は、
リサンプリング部が、前記アニメーション経路を一定の時間間隔を有する所定数の時間区間に分割し、各区間の境界点をサンプリングされたキーデータに、前記各区間でのアニメーション経路上のキー値データをサンプリングされたキー値データに設定することを特徴とする請求項３８に記載の符号化方法。
【請求項４０】
前記（ｅ）段階は、
（ｅ１）回転差分データ生成部が、現在のキーフレームの回転変換値と、以前のキーフレームの復元された回転変換値とを用いて、現在のキーフレームのキー値データ及び以前のキーフレームのキー値データによってオブジェクトに適用される回転変換の差だけ前記オブジェクトを回転変換させる回転差分値を生成し、前記回転差分値を量子化して回転差分データを生成する段階と、
（ｅ２）エントロピ符号化器が、前記回転差分データをエントロピ符号化する段階と、を含むことを特徴とする請求項３８に記載の符号化方法。
【請求項４１】
前記（ｅ１）段階は、
（ｅ１１）量子化部が、前記回転差分値のうち３成分値を量子化して回転差分データを生成する段階と、
（ｅ１２）量子化データ調整部が、前記回転差分データの３成分値を調整する段階と、
（ｅ１３）逆量子化部が、前記調整された成分値を逆量子化する段階と、
（ｅ１４）回転差分値復元部が、逆量子化された前記３成分値を用いて量子化されていない１成分値を復元し、復元された回転差分値を生成する段階と、
（ｅ１５）誤差測定部が、前記回転差分値と前記復元された回転差分値間の誤差値を測定し、前記誤差値が最小となる調整された回転差分データをエントロピ符号化される回転差分データとして決定する段階と、を含むことを特徴とする請求項４０に記載の符号化方法。
【請求項４２】
前記（ｅ１）段階は、
（ｅ１１）第１クォータニオン乗算器が、現在キーフレームでのオブジェクトの回転変換値と復元された以前キーフレームでのオブジェクトの回転変換値とを用いて前記回転差分値を生成する段階と、
（ｅ１２）量子化器が、前記回転差分値を量子化して回転差分データを生成する段階と、
（ｅ１３）逆量子化器が、前記回転差分データを逆量子化して復元された回転差分値を生成する段階と、
（ｅ１４）第２クォータニオン乗算器が、前記復元された回転差分値を以前キーフレームの回転変換値にクォータニオン乗算して現在キーフレームの復元された回転変換値を生成する段階と、を含むことを特徴とする請求項４０に記載の符号化方法。
【請求項４３】
前記（ｅ１）段階は、
（ｅ１１）回転方向誤差検出部が、現在キーフレームでの回転変換値と以前キーフレームの復元された回転変換値に応じて元のオブジェクトの回転方向と復号化されたオブジェクトの回転方向が反対となる回転方向誤差の発生有無を検出する段階と、
（ｅ１２）回転方向訂正部が、元のオブジェクトの回転方向と復号化されたオブジェクトの回転方向とが同一になるように前記回転差分値を訂正する段階と、
（ｅ１３）回転方向選択部が、前記（ｅ１１）段階で検出された回転方向誤差の発生有無により、前記回転差分値及び前記（ｅ１２）段階で訂正された回転差分値のうち何れか１つを量子化する差分データとして選択する段階と、を含むことを特徴とする請求項４０に記載の符号化方法。
【請求項４４】
請求項２８ないし４３のうち何れか１項に記載の符号化方法をコンピュータにて判読でき、実行可能なプログラムコードにて記録した記録媒体。
【請求項４５】
キーフレームの時間軸上の位置を示すキーデータ及び前記キーフレーム上のオブジェクトの回転情報を示すキー値データを含む回転インタポレータを符号化したビットストリームを復号化する方法であって、
（ａ）キーデータ復号化器が、入力ビットストリームからキーデータを復号化する段階と、
（ｂ）キー値データ復号化器が、前記入力ビットストリームからキー値データを復号化する段階と、
（ｃ）インポレータ合成器が、復号化されたキー値データ及び前記復号化されたキー値データから球面線形補間されたキー値データを復号化されたキーデータと合成して回転インタポレータを生成する段階と、を含むことを特徴とする復号化方法。
【請求項４６】
前記（ｃ）段階は、
インタポレータ合成器が、現在合成するキーデータに対応する復号化されたキー値データがない場合には、以前に合成されたキーデータに対応する復号化されたキー値データと、以後に合成されるキーデータに対応する復号化されたキー値データを用いて、現在合成するキーデータに対応するキー値データを球面線形補間することを特徴とする請求項４５に記載の復号化方法。
【請求項４７】
前記（ａ）段階は、
エントロピ復号化器が、前記入力ビットストリームをエントロピ復号化して差分データを生成する段階と、
逆ＤＰＣＭ処理部が、前記差分データに所定の逆ＤＰＣＭ演算及び逆ＤＮＤ演算を行って量子化されたキーデータを生成する段階と、
逆量子化器が、前記量子化されたキーデータを逆量子化して復元されたキーデータを生成する段階と、を含むことを特徴とする請求項４５に記載の復号化方法。
【請求項４８】
前記（ｂ）段階は、
（ｂ１）エントロピ復号化器が、前記ビットストリームからキー値データをエントロピ復号化して循環ＤＰＣＭ演算された回転差分データまたは量子化された回転差分データを生成する段階と、
（ｂ２）逆循環ＤＰＣＭ演算部が、前記ビットストリームから復号化されたＤＰＣＭ演算が行われた回数であるＤＰＣＭ次数に応じて、エントロピ復号化された回転差分データに対して逆循環ＤＰＣＭ演算を行って回転差分データを生成する段階と、
（ｂ３）逆量子化器が、前記回転差分データを逆量子化し、各キーフレームのクォータニオンキー値データによってオブジェクトに適用される回転変換の差だけオブジェクトを回転変換させる回転差分値を生成する段階と、
（ｂ４）クォータニオン乗算器が、現在キーフレームの回転差分値を復号化された以前キーフレームの回転変換値とクォータニオン乗算して現在キーフレームの回転変換値を生成する段階と、を含むことを特徴とする請求項４５に記載の復号化方法。
【請求項４９】
請求項４５ないし４８のうち何れか１項に記載の方法をコンピュータにて判読でき、実行可能なプログラムコードにて記録した記録媒体。
【請求項５０】
キーフレームの時間軸上の位置を示すキーデータ、及び前記キーフレーム上のオブジェクトの回転情報を示すキー値データを含む回転インタポレータを符号化したビットストリームを復号化する方法において、
（ａ１）エントロピ復号化器が、前記ビットストリームをエントロピ復号化して差分データを生成する段階と、
（ａ２）逆ＤＰＣＭ処理部が、前記差分データがＤＮＤ次数（ｎＤＮＤＯｒｄｅｒ）が１以上である場合には逆ＤＮＤ演算、逆ｆｏｌｄｉｎｇ、逆ｓｈｉｆｔ、逆ＤＰＣＭ演算を行い、０である場合には、逆ｆｏｌｄｉｎｇ、逆ｓｈｉｆｔ、逆ＤＰＣＭ演算を行い、−１である場合には、逆ｓｈｉｆｔ、逆ＤＰＣＭ演算を行って量子化されたキーデータを生成する段階と、
（ａ３）逆量子化器が、前記量子化されたキーデータを逆量子化して復元されたキーデータを生成する段階と、
（ｂ１）逆循環ＤＰＣＭ演算部が、前記ビットストリームからキー値データをエントロピ復号化してキー値ヘッダに含まれたＤＰＣＭ次数（ｎＫＶＤＰＣＭＯｒｄｅｒ）が１ならば、逆循環ＤＰＣＭ演算を行って量子化された回転差分データを生成し、０であれば、量子化された回転差分データを生成する段階と、
（ｂ２）逆量子化器が、前記回転差分データを逆量子化し、その結果として各キーフレームのクォータニオンキー値データによってオブジェクトに適用される回転変換の差だけオブジェクトを回転変換させる現在キーフレームの回転差分値を生成する段階と、
（ｂ３）第２クォータニオン乗算器が、前記現在のキーフレームの回転差分値を復号化された以前のキーフレームの回転変換値とクォータニオン乗算し、その結果として現在のキーフレームの回転変換値を生成する段階と、
（ｃ）回転インタポレータ合成器が、前記復号化されたキーデータ及びキー値データから球面線形補間されたキー値データを前記復号化されたキーデータと合成して回転インタポレータを生成するが、復号化しようとする現在キーフレームのキー選択フラグが０である場合、以前キーフレームと次のキーフレームとを補間して現在のキーフレームのキー値データを復元する段階と、を含むことを特徴とする復号化方法。
【請求項５１】
前記逆ＤＮＤの実行の際、
逆ＤＰＣＭ処理部が、前記ＤＮＤ次数（ｎＤＮＤＯｒｄｅｒ）が１以上である場合、ｎＫｅｙＩｎｖｅｒｔＤｏｗｎが−１でなければ、インバートダウンを行う段階と、
逆ＤＰＣＭ処理部が、ＤＮＤ次数（ｎＤＮＤＯｒｄｅｒ）に該当する回数ほど部分逆ＤＮＤを行うが、前記部分逆ＤＮＤは、ｎＫｅｙＭａｘ値が正数であれば、逆ｄｉｖｉｄｅ  ｄｏｗｎを行い、負数であれば、逆ｄｉｖｉｄｅ  ｕｐを行い、最後の部分逆ＤＮＤでは、ｎＫｅｙＭａｘ値が正数であれば、逆ｄｉｖｉｄｅを行う段階と、を含むことを特徴とする請求項５０に記載の復号化方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は３次元アニメーションデータの符号化及び復号化に関する。具体的に、本発明はアニメーションで表される客体に適用される回転情報を示す回転インタポレータの符号化／復号化方法及び装置に関する。
【０００２】
【従来の技術】
国際マルチメディア標準の１つであるＭＰＥＧ−４  ＢＩＦＳは、アニメーションのキー及びキー値データを有するインタポレーションノードを用いるキーフレーム基盤のアニメーションを支援する。
【０００３】
キーフレーム基盤のアニメーションでスムーズで自然なアニメーションを生成するためには、大量のキー及びキー値データが必要であり、キーフレーム間に位置するフィールドデータは補間により満たされる。ＶＲＭＬ及びＭＰＥＧ−４  ＢＩＦＳで補間とは、補間の種類に応じて線形または球形補間を意味する。
【０００４】
キー及び対応するキー値は時間軸上の元のアニメーション軌跡の近似値である。例えば、回転インタポレータノードで表されたアニメーションデータは３次元球の表面上の時間に応じる２次元軌跡として図１に示された。図１に示されたように、従来の技術はキーフレーム間の値を補間するために球面線形インタポレーションを支援するので、アニメーション経路は軌跡の断片の集合と見られる。
【０００５】
ＢＩＦＳが支援する回転インタポレータノードでは、キーデータは（−∞〜＋∞）範囲でキーフレームが位置する時間を不連続的な数字で表現する。キー値フィールドはそれぞれのキーが示す時間に合成イメージでの客体の回転情報を示す。各キーデータが示す時間以外の時間での客体の回転情報は最も近い以前時間を示すキーデータ及び最も近い後続時間を示すキーデータに対応するキー値データによって球面で線形補間される。
【０００６】
客体の回転情報を用いる球面線形補間方法は、回転情報を回転軸及び回転角で表現する。ＶＲＭＬでのようにＭＰＥＧ−４  ＢＩＦＳは回転軸と回転角とで表される回転情報を回転インタポレータノードを通じて表現する。これらキー値データが球面線形補間を用いてスムーズなアニメーションを生成する時、キーフレーム間のキー値データの差分値は高い相関関係を有するので、データ間の冗長性を招く。したがって、データの差分値を用いる符号化方法を使用することが効率的である。
【０００７】
ＭＰＥＧ−４  ＢＩＦＳでは、回転インタポレーションノードのキー及びキー値データで表されるフィールドデータを符号化するために２種の方法を用いるが、１つはＰＣＭを用いる方法であり、他の１つはＤＰＣＭとエントロピ符号化とを用いる方法である。
【０００８】
まず、ＰＣＭを用いる方法は、符号化されたキーデータ及びキー値データに対して量子化だけを行う。したがって、符号化されるデータの有用な特性が考慮されていないために、この方法は非効率的である。この方法において、回転インタポレータノードのフィールドデータが入力され、フィールドデータのキー値データがクォータニオン空間の値に変換される。その後、キー及びキー値データが量子化される。量子化されたフィールドデータは２進数形式のデータとして出力される。元のフィールドデータとクォータニオン結果間の視覚的な歪曲を評価するために、出力された２進数形式のデータは逆量子化によってフィールドデータに復元され、各復元されたクォータニオン値は回転軸及び回転角で構成されるキー値データ形式に復元される。復元された回転インタポレータノードのフィールドデータは貯蔵され、スクリーンに出力される。また、このデータを用いると、クォータニオンエラーに係る映像の視覚的な歪曲を測定できる。歪曲は次の数式１によって計算できる。
【０００９】
【数１】
0003905834.tif 000002
【００１０】
ここで、Ｎはフィールドデータの数を、εｉは符号化されたキー値データＱｉ及
0003905834.tif 000003
【００１１】
次いで、ＤＰＣＭ及びエントロピ符号化を用いた方法は連続されたデータ間の相関関係を考慮するので、ＰＣＭを用いた符号化方法より高い符号化効率を示す。ＤＰＣＭ及びエントロピ符号化を用いる方法では、以前に復元されたキー値データと符号化されるキー値データ間の差分値が量子化前に計算され、差分値が量子化される。これにより、差分値から生じるデータの特性が符号化効率を向上させる。
【００１２】
図２及び図３は線形ＤＰＣＭ及びエントロピ符号化を用いるＭＰＥＧ−４  ＰＭＦＣ（Ｐｒｅｄｉｃｔｉｖｅ  ＭＦＦｉｅｌｄ  Ｃｏｄｉｎｇ）の符号化器／復号化器の構成を示すブロック図である。
【００１３】
図２に示された線形ＤＰＣＭ演算部は次の数式２を用いて現在キー値データ及
0003905834.tif 000004
【００１４】
【数２】
0003905834.tif 000005
【００１５】
ここで、Ｑｉは時間ｔでクォータニオン形式で表された元の入力キー値データで
0003905834.tif 000006
である。
【００１６】
しかし、図２に示された符号化方法は高い符号化効率を示せない。この方法の短所は、クォータニオン空間で客体の回転を決定するキー値データを分析することによって容易に分かる。次の数式３でキー値データはクォータニオンで表される。
【００１７】
【数３】
0003905834.tif 000007
【００１８】
例えば、数式３で記載されたようにクォータニオン空間では、２つのクォータニオンのあらゆる成分の符号が反対で、大きさが同一であれば、２つのクォータニオンは同一であると判断する。これは２つのクォータニオンによる３次元空間で客体の回転変換が同一であり、回転変換に影響を与える要素は回転軸ベクトルでなく、回転軸の方向及び回転角であるということを意味する。しかし、ＭＰＥＧ−４  ＢＩＦＳで用いられたように、前記数式３を用いてキー値データが表され、連続されたキー値データのベクトル成分間の減算によって線形で差分が計算されれば、差分値は０でないということを意味する。これは線形差分値が回転変換の冗長性をよく反映できないということを意味する。このような理由で、前記数式１に記載された歪曲測定方法は画質を正しく測定できない。
【００１９】
【発明が解決しようとする課題】
本発明が解決しようとする技術的課題は、高画質を保ちつつ回転インタポレータを圧縮符号化及び復号化可能に、元の回転インタポレータとの誤差が許容臨界値以下になる分節点を元の回転インタポレータから抽出し、抽出された回転インタポレータを符号化及び復号化する回転インタポレータ符号化／復号化方法及び装置を提供するところにある。
【００２０】
本発明が解決しようとする他の技術的課題は、回転変換の冗長性を充実に反映できる回転差分値を計算して回転インタポレータのキー値データを符号化することによって、高い圧縮率と高画質のアニメーションを提供できる回転インタポレータの符号化／復号化方法及び装置を提供するところにある。
【００２２】
【課題を解決するための手段】
前記技術的な課題を達成するための本発明の回転インタポレータ符号化装置は、入力回転インタポレータよりなる第１のアニメーション経路と、前記第１のアニメーション経路から抽出された分節点によって生成される第２のアニメーション経路間の誤差を所定の臨界値以下にする最小数の分節点を前記第１のアニメーション経路から抽出し、抽出された分節点に含まれたキーデータ及びキー値データを出力する分節点抽出部と、前記分節点抽出部から入力されたキーデータの範囲を減少させて符号化するキー符号化器と、現在のキーフレームのキー値データと以前のキーフレームのキー値データによってオブジェクトに適用される回転変換の差だけオブジェクトを回転変換させる回転差分値を生成し、前記分節点抽出部から入力されたキー値データを符号化するキー値符号化器とを含む。
【００２３】
また、前記技術的な課題を達成するための本発明の回転インタポレータ符号化装置は、前記第１のアニメーション経路を、一定の時間間隔を有する所定数の区間にサンプリングし、リサンプリングされたキーデータ及びキー値データを含む回転インタポレータを前記キー符号化器及びキー値符号化器に各々出力するリサンプリング部と、外部入力信号に応じて入力回転インタポレータを前記リサンプリング部または前記分節点抽出部に出力する選択部と、をさらに含むことが望ましい。
【００２４】
一方、前記技術的な課題を達成するための本発明の他の回転インタポレータ符号化装置は、入力回転インタポレータよりなるアニメーション経路を一定の時間間隔を有する所定数の区間にサンプリングし、リサンプリングされたキーデータ及びキー値データを含む回転インタポレータを出力するリサンプリング部と、前記リサンプリング部から入力されたキーデータを符号化するキー符号化器と、現在のキーフレームのキー値データと以前のキーフレームのキー値データによってオブジェクトに適用される回転変換の差だけオブジェクトを回転変換させる回転差分値を生成し、前記分節点抽出部から入力されたキー値データを符号化するキー値符号化器とを含む。
【００２５】
また、前記技術的な課題を達成するための本発明の回転インタポレータ符号化装置の分節点抽出部は、入力されたアニメーション経路の開始経路点と終了経路点とを抽出し、抽出されていない経路点を１つずつ選択し、選択されていない残りの経路点を前記選択された経路点から球面線形補間する球面線形補間部と、入力されたアニメーション経路と前記球面線形補間部で球面線形補間によって生成されたアニメーション経路間の誤差を計算する誤差計算部と、前記誤差が最小となる分節点を抽出し、抽出された分節点に応じる誤差が所定の臨界値以下であるかを比較し、前記抽出された分節点を出力する判断部と、を含むことが望ましい。
【００２６】
また、前記技術的な課題を達成するための本発明の回転インタポレータ符号化装置のキー値符号化器は、現在のキーフレームの回転変換値と、以前のキーフレームの復元された回転変換値とを用いて、現在のキーフレームのキー値データと以前のキーフレームのキー値データによってオブジェクトに適用される回転変換の差だけ前記オブジェクトを回転変換させる回転差分値を生成し、前記回転差分値を量子化して回転差分データを出力する回転差分データ生成部と、前記回転差分データをエントロピ符号化するエントロピ符号化器と、を含むことが望ましい。
【００２７】
また、前記技術的な課題を達成するための本発明の回転インタポレータ符号化装置のキー値符号化器に含まれる前記回転差分データ生成部は、現在キーフレームでのオブジェクトの回転変換値と復元された以前キーフレームでのオブジェクトの回転変換値とを用いて前記回転差分値を生成する第１クォータニオン乗算器と、前記回転差分値を量子化して回転差分データを生成する量子化器と、前記回転差分データを逆量子化し、復元された回転差分値を生成する逆量子化器と、前記復元された回転差分値を以前キーフレームの回転変換値にクォータニオン乗算して現在のキーフレームの復元された回転変換値を生成する第２クォータニオン乗算器と、を含むことが望ましい。
【００２８】
また、前記技術的な課題を達成するための本発明の回転インタポレータ符号化装置のキー符号化器は、前記分節点抽出部から入力された回転インタポレータのキーデータを所定の量子化ビット数で量子化する第１量子化器と、前記量子化されたキーデータの差分データを生成する第１ＤＰＣＭ処理部と、前記差分データと前記差分データの最大値及び最小値との関係に応じて前記差分データの範囲を減らすＤＮＤ演算を行うＤＮＤ処理部と、前記ＤＮＤ処理部から入力された差分データを符号化する第１エントロピ符号化器と、を含むことが望ましい。
【００２９】
一方、前記技術的な課題を達成するための本発明の回転インタポレータ復号化装置は、入力ビットストリームからキーデータを復号化するキーデータ復号化器と、前記入力ビットストリームからキー値データを復号化するキー値データ復号化器と、復号化されたキー値データ及び前記復号化されたキー値データから球面線形補間されたキー値データを復号化されたキーデータと合成して回転インタポレータを生成するインタポレータ合成器と、を含む。
【００３０】
また、前記技術的な課題を達成するための本発明の回転インタポレータ復号化装置のインタポレータ合成器は、現在合成するキーデータに対応する復号化されたキー値データがない場合には、以前に合成されたキーデータに対応する復号化されたキー値データと、以後に合成されるキーデータに対応する復号化されたキー値データを用いて、現在合成するキーデータに対応するキー値データを球面線形補間することが望ましい。
【００３１】
また、前記技術的な課題を達成するための本発明の回転インタポレータ復号化装置のキーデータ復号化器は、前記入力ビットストリームをエントロピ復号化して差分データを生成するエントロピ復号化器と、前記差分データに所定の逆ＤＰＣＭ演算を行って量子化されたキーデータを生成する逆ＤＰＣＭ処理部と、前記量子化されたキーデータを逆量子化して復元されたキーデータを生成する逆量子化器と、を含むことが望ましい。
【００３２】
また、前記技術的な課題を達成するための本発明の回転インタポレータ復号化装置のキー値データ復号化器は、前記ビットストリームからキー値データをエントロピ復号化して循環ＤＰＣＭ演算された回転差分データまたは量子化された回転差分データを生成するエントロピ復号化器と、前記ビットストリームから復号化されたＤＰＣＭ演算が行われた回数であるＤＰＣＭ次数に応じてエントロピ復号化器から入力された回転差分データに対して逆循環ＤＰＣＭ演算を行って量子化された回転差分データを生成する逆循環ＤＰＣＭ演算部と、前記量子化された回転差分データを逆量子化し、各キーフレームのクォータニオンキー値データによってオブジェクトに適用される回転変換の差だけオブジェクトを回転変換させる回転差分値を生成する逆量子化器と、現在キーフレームの回転差分値を復号化された以前キーフレームの回転変換値とクォータニオン乗算して現在キーフレームの回転変換値を生成するクォータニオン乗算器と、を含むことが望ましい。
【００３３】
一方、前記技術的な課題を達成するための本発明の回転インタポレータ符号化方法は、（ｂ）分節点抽出部が、前記回転インタポレータよりなる第１のアニメーション経路と前記第１のアニメーション経路から抽出された分節点によって生成される第２のアニメーション経路間の誤差を所定の臨界値以下にする最小数の分節点を前記第１のアニメーション経路から抽出して符号化するキーデータ及びキー値データを生成する段階と、（ｄ）キー符号化器が、前記（ｂ）段階で抽出されたキーデータの範囲を減少させて符号化するキー符号化段階と、（ｅ）キー値符号化器が、前記（ｂ）段階で抽出されたキー値データに対して、現在のキーフレームのキー値データと以前のキーフレームのキー値データによってオブジェクトに適用される回転変換の差だけオブジェクトを回転変換させる回転差分値を生成して符号化することによって、キー値データを符号化するキー値符号化段階と、を含む。
【００３４】
また、前記技術的な課題を達成するための本発明の回転インタポレータ符号化方法の前記（ｂ）段階は、（ｂ１）前記第１のアニメーション経路の開始経路点と終了経路点とを選択する段階と、（ｂ２）選択されていない経路点を１つずつ選択し、選択されていない残りの経路点を前記選択された経路点から球面線形補間する段階と、（ｂ３）前記第１のアニメーション経路と前記（ｂ２）段階で球面線形補間によって生成された第２のアニメーション経路間の誤差を計算する段階と、（ｂ４）前記誤差が最小となる分節点を選択し、選択された分節点に応じる誤差を所定の臨界値と比較し、符号化するキーデータ及びキー値データを決定する段階と、を含むことが望ましい。
【００３５】
また、前記技術的な課題を達成するための本発明の回転インタポレータ符号化方法は、前記（ｂ）段階以前に、（ａ）前記第１のアニメーション経路を一定の時間間隔を有する所定数の区間にサンプリングし、リサンプリングされたキーデータ及びキー値データを含む回転インタポレータを生成する段階をさらに含み、前記（ｂ）段階は、前記リサンプリング段階で生成された回転インタポレータよりなる経路の分節点を抽出するか、あるいは、前記（ｂ）段階以後に、（ｃ）前記抽出された分節点に応じる第２のアニメーション経路を一定の時間間隔を有する所定数の区間にサンプリングし、符号化するキーデータ及びキー値データを生成するリサンプリング段階を含むことが望ましい。
【００３６】
一方、前記技術的な課題を達成するための本発明の他の回転インタポレータ符号化方法は、（ａ）リサンプリング部が、前記回転インタポレータよりなるアニメーション経路を一定の時間間隔を有する所定数の区間にサンプリングし、リサンプリングされたキーデータ及びキー値データを含む回転インタポレータを生成する段階と、（ｄ）キー符合化器が、前記（ａ）段階でサンプリングされたキーデータの範囲を減少させて符号化するキー符号化段階と、（ｅ）キー値符合化器が、前記（ａ）段階でサンプリングされたキー値データに対して、現在のキーフレームのキー値データと以前のキーフレームのキー値データによってオブジェクトに適用される回転変換の差だけオブジェクトを回転変換させる回転差分値を生成して符号化することによってキー値データを符号化するキー値符号化段階と、を含む。
【００３７】
また、前記技術的な課題を達成するための本発明の他の回転インタポレータ符号化方法の前記（ｄ）段階は、前記キーデータを所定の量子化ビット数で量子化する段階と、量子化されたキーデータに所定のＤＰＣＭ演算を行って差分データを生成する段階と、前記差分データをエントロピ符号化する段階と、を含むことが望ましい。
【００３８】
また、前記技術的な課題を達成するための本発明の回転インタポレータ符号化方法の前記（ｅ）段階は、（ｅ１）回転差分データ生成部が、現在のキーフレームの回転変換値と、以前のキーフレームの復元された回転変換値とを用いて、現在のキーフレームのキー値データ及び以前のキーフレームのキー値データによってオブジェクトに適用される回転変換の差だけ前記オブジェクトを回転変換させる回転差分値を生成し、前記回転差分値を量子化して回転差分データを生成する段階と、（ｅ２）エントロピ符号化器が、前記回転差分データをエントロピ符号化する段階と、を含むことを特徴とする。
【００３９】
また、前記（ｅ１）段階は、（ｅ１１）第１クォータニオン乗算器が、現在キーフレームでのオブジェクトの回転変換値と復元された以前キーフレームでのオブジェクトの回転変換値とを用いて前記回転差分値を生成する段階と、（ｅ１２）量子化器が、前記回転差分値を量子化して回転差分データを生成する段階と、（ｅ１３）逆量子化器が、前記回転差分データを逆量子化し、復元された回転差分値を生成する段階と、（ｅ１４）第２クォータニオン乗算器が、前記復元された回転差分値を以前キーフレームの回転変換値にクォータニオン乗算して現在キーフレームの復元された回転変換値を生成する段階と、を含むことが望ましい。
【００４０】
一方、前記技術的な課題を達成するための本発明の回転インタポレータ復号化方法は、（ａ）キーデータ復号化器が、入力ビットストリームからキーデータを復号化する段階と、（ｂ）キー値データ復号化器が、前記入力ビットストリームからキー値データを復号化する段階と、（ｃ）インポレータ合成器が、復号化されたキー値データ及び前記復号化されたキー値データから球面線形補間されたキー値データを復号化されたキーデータと合成して回転インタポレータを生成する段階と、を含む。
【００４１】
また、前記技術的な課題を達成するための本発明の回転インタポレータ復号化方法の前記（ｃ）段階は、現在合成するキーデータに対応する復号化されたキー値データがない場合には、以前に合成されたキーデータに対応する復号化されたキー値データと、以後に合成されるキーデータに対応する復号化されたキー値データを用いて、現在合成するキーデータに対応するキー値データを球面線形補間することが望ましい。
【００４２】
また、前記技術的な課題を達成するための本発明の回転インタポレータ復号化方法の前記（ａ）段階は、前記入力ビットストリームをエントロピ復号化して差分データを生成する段階と、前記差分データに所定の逆ＤＰＣＭ演算及び逆ＤＮＤ演算を行って量子化されたキーデータを生成する段階と、前記量子化されたキーデータを逆量子化して復元されたキーデータを生成する段階と、を含むことが望ましい。
【００４３】
また、前記技術的な課題を達成するための本発明の回転インタポレータ復号化方法の前記（ｂ）段階は、（ｂ１）エントロピ復号化器が、前記ビットストリームからキー値データをエントロピ復号化して循環ＤＰＣＭ演算された回転差分データまたは量子化された回転差分データを生成する段階と、（ｂ２）逆循環ＤＰＣＭ演算部が、前記ビットストリームから復号化されたＤＰＣＭ演算が行われた回数であるＤＰＣＭ次数に応じて、エントロピ復号化された回転差分データに対して逆循環ＤＰＣＭ演算を行って回転差分データを生成する段階と、（ｂ３）逆量子化器が、前記回転差分データを逆量子化し、各キーフレームのクォータニオンキー値データによってオブジェクトに適用される回転変換の差だけオブジェクトを回転変換させる回転差分値を生成する段階と、（ｂ４）クォータニオン乗算器が、現在キーフレームの回転差分値を復号化された以前キーフレームの回転変換値とクォータニオン乗算して現在キーフレームの回転変換値を生成する段階と、を含むことが望ましい。
【００４６】
【発明の実施の形態】
以下、添付した図面に基づき、本発明の好ましい実施の形態による回転インタポレータの符号化装置について説明する。
【００４７】
本発明の好ましい実施の形態による符号化装置の構成を示すブロック図である図４を参照すれば、本発明の符号化装置は、分析器４０、キーデータ符号化器２００、キー値データ符号化器３００、及びヘッダ符号化器４００を備える。
【００４８】
本発明の好ましい実施の形態による符号化方法を示すフローチャートである図５を参照すれば、符号化されるべき回転インタポレータは分析器４０に入力され（Ｓ３００）、分析器４０は、回転インタポレータを構成するｘ、ｙ及びｚ成分のキー値データの第１のアニメーション経路から符号化すべきキーデータ及びキー値データを各々抽出して、キーデータはキーデータ符号化器２００に出力し、キー値データはキー値データ符号化器３００に出力する（Ｓ３２０）。
【００４９】
キーデータを受け取ったキーデータ符号化器２００は、キーデータを所定の量子化ビット数で量子化し、量子化されたキーデータに対して所定のＤＰＣＭ演算を行って差分データを求めた後、差分データをエントロピ符号化する（Ｓ３４０）。
【００５０】
また、キー値データを受け取ったキー値データ符号化器３００は、キー値データを所定の量子化ビット数で量子化し、量子化されたキーデータに対して所定のＤＰＣＭ演算を行って差分データを求めた後、差分データを符号化する（Ｓ３６０）。
【００５１】
一方、ヘッダ符号化器４００は、キーデータ符号化器２００及びキー値データ符号化器３００から復号化に必要な情報を受け取って符号化する（Ｓ３８０）。
【００５２】
以下、分析器４０、キーデータ符号化器２００、及びキー値データ符号化器３００の各々の構成を示す図面に基づき、各々の構成及び処理過程について詳細に説明する。
【００５３】
図６は、本発明の好ましい第１の実施の形態による分析器４０の構成を示すブロック図である。
【００５４】
図６を参照すれば、本発明の好ましい第１の実施の形態による分析器４０は、入力回転インタポレータによる第１のアニメーション経路を一定の時間間隔を有する所定数の区間にサンプリングし、キー符号化器、キー値符号化器及びヘッダ符号化器に出力するリサンプリング部４３と、第１のアニメーション経路と、第１のアニメーション経路から抽出された分節点により生成される第２のアニメーション経路との誤差を所定の臨界値以下にする最小数の分節点を第１のアニメーション経路から抽出してキーデータ符号化器、キー値データ符号化器及びヘッダ符号化器に出力する分節点抽出部４２、及び入力回転インタポレータを外部入力信号に基づきリサンプリング部４３または分節点抽出部４２に出力する選択部４１を備える。また、分節点抽出部４２は、線形補間部４２ａ、誤差計算部４２ｂ、及び判断部４２ｃを備える。
【００５５】
図９は、本発明の好ましい第１の実施の形態による分析器４０の処理過程を示すフローチャートである。
【００５６】
図９を参照すれば、選択部４１は、外部より回転インタポレータ及び設定信号を受け取る（Ｓ３２５）。外部より入力される設定信号は、符号化すべきキーデータ及びキー値データを生成する方法を設定する信号並びに符号化すべきキーデータ及びキー値データを生成するモードを設定する生成信号を含む。
【００５７】
まず、キーデータ及びキー値データを生成するモードについて説明する。
【００５８】
分析器４０は、入力された回転インタポレータのキーフレームを減らして全体的に符号化すべきキーデータ及びキー値データの量を減らす。このような分析器４０は、外部より入力されたモード設定信号に基づきアニメーション経路維持モード（ｐａｔｈ−ｐｒｅｓｅｒｖｉｎｇ  ｍｏｄｅ）及びアニメーションキー維持モード（ｋｅｙ−ｐｒｅｓｅｒｖｉｎｇ  ｍｏｄｅ）のうちいずれか一方のモードを有する。
【００５９】
まず、経路維持モードは、回転インタポレータがアニメーション経路の補間を記述するためにのみ用いられ、キーフレームのランダムアクセスが必要ない場合である。経路維持モードにおいては、効率的な符号化のために、所定の誤差範囲内において経路に含まれる回転インタポレータのキーデータ及び対応するキー値データを除去することが認められる。
【００６０】
一方、キー維持モードは、ＭＰＥＧ−４のＢＩＦＳ命令語（例えば、ｒｅｐｌａｃｅ、ｄｅｌｅｔｅ、ｉｎｓｅｒｔなど）を用いてキーフレームにランダムアクセスが必要な場合である。キー維持モードにおいては、インタポレータのキーデータの数がそのまま維持される。経路維持モード及びキー維持モードの詳細については、後述する。
【００６１】
図９をさらに参照すれば、選択部４１は、外部より入力された生成モードに基づき符号化すべきキー及びキー値データの生成モードを選択する。
【００６２】
また、選択部４１は、入力された生成モードがキー維持モードである場合には入力された回転インタポレータを分節点抽出部４２に出力し、入力された生成モードが経路維持モードである場合には入力された生成方法の設定信号に基づき回転インタポレータをキー及びキー値データの生成に必要な情報と共にリサンプリング部４３または分節点抽出部４２に出力する（Ｓ３３０）。
【００６３】
具体的に、リサンプリングにより符号化すべきキー及びキー値データを生成する場合には、回転インタポレータと共にサンプリングすべきキーデータの数（すなわち、時間間隔）及び生成モードをリサンプリング部４３に出力し、分節点抽出により符号化すべきキー及びキー値データを生成する場合には、元の経路と分節点抽出により生成された経路との臨界誤差値及び生成モードを共に分節点抽出部４２出力する。
【００６４】
選択部４１より入力回転インタポレータを受け取ったリサンプリング部４３は、入力回転インタポレータにより形成されたアニメーション経路を所定の時間間隔にてサンプリングしてサンプリングされたキーデータ及びキー値データを生成し、選択部４１より入力回転インタポレータを受け取った分節点抽出部４２は、入力回転インタポレータにより形成された経路と抽出された分節点により形成された経路との誤差を所定の臨界値以下にする最小数の分節点を抽出する（Ｓ３３５）。
【００６５】
図１０は、本発明の好ましい実施の形態によるリサンプリング部４３の処理過程を示すフローチャートである。
【００６６】
図１０に基づき、リサンプリング過程について説明する。
【００６７】
リサンプリング部４３は、選択部４１から回転インタポレータ及びリサンプリングすべきキーデータの数ｍを受け取る（Ｓ５０２）。この時、リサンプリングすべきキーデータの数はユーザによって任意に設定されるか、あるいは予め定義された所定の値となる。
【００６８】
リサンプリング部４３は、入力回転インタポレータにより形成された元の経路の最初及び最後の経路点を選択し、リサンプリングすべきキーデータの初期値ｉを１として設定する（Ｓ５０４）。
【００６９】
その後、リサンプリング部４３は、所定の時間間隔をもって第ｉ番目のキーデータを生成する（Ｓ５０６）。
【００７０】
元のキーデータ及びリサンプリングされたキーデータを示す図１２を参照すれば、入力回転インタポレータのキーデータはキーフレームの時間軸上の位置を表わすために単調増加するが、図１２に示されたように、その間隔が一定ではない。
【００７１】
従って、図１２に示されたように、リサンプリング部４３は、第Ｓ５０４段階において選択された最初及び最後の経路点を表わすキーデータ間の差を受け取ったリサンプリングすべきキーの数で割って時間間隔を求め、求められた一定の時間間隔をもってキーデータをリサンプリングする。
【００７２】
リサンプリング部４３は、リサンプリングにより生成されたキーデータに対応するキー値データを元のアニメーション経路において球面線形補間して生成する（Ｓ５０８）。すなわち、リサンプリングされたキーデータより時間軸上の後方に位置するキーデータに対応するキー値データ及びリサンプリングされたキーデータより時間軸上の前方に位置するキーデータに対応するキー値データを用い、リサンプリングされたキー値データを球面線形補間してキー値データを生成する。
【００７３】
リサンプリング部４３は、補間によりキーデータ及びキー値データをリサンプリングした後、入力されたリサンプリングすべき全てのキーデータに対してキーデータ及びキー値データのリサンプリングが行われたか否かをチェックし、全てのキーデータ及びキー値データがリサンプリングされるまで第Ｓ５０６及びＳ５０８段階を繰り返す（Ｓ５１０）。
【００７４】
図１１は、本発明の好ましい第１の実施の形態による分節点の抽出方法を示すフローチャートであり、図１４ないし図１９は、回転インタポレータ経路から分節点を抽出する過程を段階別に示す図面である。
【００７５】
図６、図１１、及び図１４ないし図１９を参照すれば、本発明の好ましい第１の実施の形態による分節点抽出部４２の線形補間部４２ａは、選択部４１より回転インタポレータ及び臨界誤差値ｅｔｈを受け取る（Ｓ５２０）。受け取られた回転インタポレータよりなる経路は、図１４に示された通りである。
【００７６】
線形補間部４２ａは、図１５に示されたように、入力された回転インタポレータよりなる経路の最初の経路点Ｑ０及び最後の経路点Ｑｎを抽出し、カウンタｉを１として設定する（Ｓ５２２）。
【００７７】
線形補間部４２ａは、最初の経路点Ｑ０及び最後の経路点Ｑｎ間の経路点のうちいずれか一つを任意にまたは順次的に選択し（Ｓ５２４）、選択されていない経路点を選択された経路点から球面線形補間し、選択された経路点及び補間された経路点を誤差計算部４２ｂに出力する（Ｓ５２６）。
【００７８】
誤差計算部４２ｂは、抽出された経路点及び補間された経路点により形成される候補経路と元の経路との誤差ｅを計算して判断部４２ｃに出力する（Ｓ５２８）。経路間の誤差を計算する方法については、後述する。
【００７９】
誤差計算部４２ｂは、選択されていない全ての経路点に対して誤差が計算されたか否かをチェックし、誤差が計算されていない経路点があれば、第Ｓ５２４段階ないし第Ｓ５２８段階を繰り返し行い、全ての抽出されていない点に対して元の経路との誤差を計算する（Ｓ５３０）。
【００８０】
図１６は、前記第Ｓ５２４段階及びＳ５３０段階を示す図面であって、線形補間部４２ａはまず、ｋ１時間に当たるキーデータに対して分節点Ｑ１を抽出し、Ｑ１及びＱｎ間の経路点を球面線形補間して候補１経路を生成し、誤差計算部４２ｂは、元の経路と候補１経路との誤差ｅ１を計算した。その後、前記過程を繰り返して線形補間部４２ａは分節点Ｑｋを抽出し、Ｑ１及びＱｋ間の経路点とＱｋ及びＱｎ間の経路点とを球面線形補間して候補ｋ経路を生成し、誤差計算部４２ｂは、元の経路と候補ｋ経路との誤差ｅｋを計算する。
【００８１】
一方、抽出されていない全ての経路点に対して誤差が計算されれば、全ての経路点に対する誤差は判断部４２ｃに入力され、判断部４２ｃは、誤差が最小となる経路点を抽出し、カウンタｉを１だけインクリメントする（Ｓ５３２）。
【００８２】
判断部４２ｃは、第Ｓ５３２段階において選択された分節点による誤差ｅが入力された所定の臨界誤差値ｅｔｈより大きく、カウンタが最初の経路点Ｑ０及び最後の経路点Ｑｎ間の経路点の数に当たるキーデータの数ｎより大きいかをチェックする（Ｓ５３４）。
【００８３】
もし、計算された誤差が臨界誤差値より小さければ、符号化に必要な分節点がいずれも抽出されたことを意味し、カウンタが表わす選択された分節点の数がｎに同じであれば、全ての元の経路上の全ての経路点として抽出されたことを意味するため、分節点の抽出過程は終わる。
【００８４】
しかし、選択された分節点の数がｎより小さく、且つ、抽出された分節点による誤差が臨界誤差値より大きければ、分節点をさらに抽出しなければならないため、選択された分節点を線形補間部４２ａに出力して第Ｓ５２４段階ないしＳ５３２段階を繰り返し行う。
【００８５】
以下、分析器４０の選択部４１に入力された符号化すべきキーデータ及びキー値データ生成モードが経路維持モードである場合に、リサンプリング部４３及び分節点抽出部４２からキーデータ符号化器２００及びキー値データ符号化器３００に出力されるデータについて説明する。
【００８６】
リサンプリング部４３は、サンプリングされたキーデータ及びキー値データをいずれも符号化すべきキー及びキー値データとしてキーデータ符号化器２００及びキー値データ符号化器３００に出力する。
【００８７】
以下、図２０に基づき、生成モードに基づき分節点抽出部４２から出力されるキーデータ及びキー値データについて説明する。
【００８８】
図２０に示されたように、最終的に抽出された分節点が０、３、６及び８であるとした時、経路維持モードにおいて分析器４０は、分節点０、３、６及び８に当たるキーデータ及びキー値データのみを出力する。
【００８９】
しかし、キー維持モードにおいて分析器４０は、０ないし８の全てのキーデータを符号化すべきデータとして出力し、分節点０、３、６及び８に当たるキー値データはキー選択フラグと共に出力する。キー選択フラグは、下記表１に示す。
【００９０】
【表１】
0003905834.tif 000008
【００９１】
以下、図７に基づき、本発明の好ましい第２の実施の形態による分析器４０について説明する。
【００９２】
図７を参照すれば、第２の実施の形態による分析器４０は、回転インタポレータを受け取ってリサンプリングするリサンプリング部４５、及びリサンプリングされた回転インタポレータの分節点を抽出して符号化すべきキーデータ及びキー値データを出力する分節点抽出部４６を備える。また、分節点抽出部４６は、前記第１の実施の形態の分節点抽出部４６と同様に、線形補間部４６ａ、誤差計算部４６ｂ、及び判断部４６ｃを備える。
【００９３】
本発明の第２の実施の形態による分析器４０に回転インタポレータが入力されれば、リサンプリング部４５は、外部より入力されたモード設定信号に基づき、入力された回転インタポレータにより形成される第１のアニメーション経路を一定の時間間隔を有する所定数の区間にリサンプリングする。
【００９４】
リサンプリング部４５は、リサンプリングされたキーデータ及びキー値データよりなる回転インタポレータを分節点抽出部４６の線形補間部４６ａに出力する。
【００９５】
線形補間部４６ａは、前記図１１の第Ｓ５２２段階ないし第Ｓ５２６段階を行い、回転インタポレータを補間して誤差計算部４６ｂに出力し、誤差計算部４６ｂは第Ｓ５２８及び第Ｓ５３０段階を行い、補間された回転インタポレータにより形成される第２のアニメーション経路と第１のアニメーション経路との誤差を計算する。判断部４６ｃは、誤差が最小となる経路点を選択し、選択された経路点による誤差が臨界誤差値ｅｔｈより大きいか否か、及び全ての経路点が選択されたか否かをチェックし、符号化すべきキーデータ及びキー値データを生成する。
【００９６】
従って、第２の実施の形態による分析器４０に含まれたリサンプリング部４５及び分節点抽出部４６の動作は、第１の実施の形態のリサンプリング部４５及び分節点抽出部４６の動作とほとんど類似している。但し、分節点抽出部４６がリサンプリング部４５から出力されたキー及びキー値データよりなる回転インタポレータを入力され、リサンプリング部４５より入力された回転インタポレータにより形成されるアニメーション経路に対して分節点の抽出を行うという点だけで、前記第１の実施の形態の符号化すべきキー及びキー値データ選択過程とは異なる。
【００９７】
以下、図８に基づき、本発明の好ましい第３の実施の形態による分析器４０について説明する。
【００９８】
図８を参照すれば、第３の実施の形態による分析器４０は、回転インタポレータを入力され、回転インタポレータにより形成される第１のアニメーション経路から分節点を抽出してキーデータ及びキー値データを出力する分節点抽出部４８、及び分節点抽出部４８より入力されたキーデータ及びキー値データよりなる回転インタポレータにより形成される第２のアニメーション経路を所定の時間間隔をもってリサンプリングするリサンプリング部４９を備える。また、分節点抽出部４８は、前記第１の実施の形態の分節点抽出部４８と同様に、球面線形補間部４８ａ、誤差計算部４８ｂ、及び判断部４８ｃを備える。
【００９９】
第３の実施の形態による分節点抽出部４８は、前記第１の実施の形態と同様に、キーデータ及びキー値データを抽出してリサンプリング部４９に出力する。
【０１００】
リサンプリング部４９は、入力されたキーデータ及びキー値データよりなる回転インタポレータにより形成された経路を所定の一定の時間間隔をもってリサンプリングして符号化すべきキーデータ及びキー値データを出力する。リサンプリング部４９の機能は、前記第１及び第２の実施の形態のリサンプリング部４９の機能と類似しているため、その詳細な説明は省く。
【０１０１】
前記第１ないし第３の実施の形態による分析器４０から出力されたキーデータ及びキー値データは、各々キーデータ符号化器２００及びキー値データ符号化器３００に入力される。
【０１０２】
以下、図２１ないし図４０に基づき、本発明の好ましい実施の形態によるキーデータ符号化器２００について説明する。
【０１０３】
図２１は、本発明の好ましい実施の形態によるキーデータ符号化器の構成を示す図面である。
【０１０４】
本発明のキーデータ符号化器２００は、線形キー符号化器９００、量子化器９１０、ＤＰＣＭ処理部９２０、シフト部９３０、フォルド処理部９４０、ＤＮＤ処理部９５０及びエントロピ符号化器９６０を備える。
【０１０５】
線形キー符号化器９００は、全体キーデータの範囲においてキーデータが線形に増える領域を選択して符号化する。量子化器９１０は、量子化誤差を最小化する方法を用いて入力されたキーデータを量子化する。ＤＰＣＭ処理部９２０は、量子化されたキーデータを受け取り、キーデータの差分データを生成する。シフト部９３０は、全ての差分データから頻度数が最も高い差分データを引く。フォルド処理部９４０は、全ての差分データを正数の領域または負数の領域に移動させる。ＤＮＤ処理部９５０は、ディバイド、ディバイド−アップ、及びディバイド−ダウンの３種の演算を選択的に行い、キーデータの差分データの範囲を狭める。キーデータに対するエントロピ符号化器９６０は、ビットプレイン単位に差分データを符号化するＳｉｇｎｅｄＡＡＣ及びＵｎｓｉｇｎｅｄＡＡＣ関数を用いて差分データを符号化する。
【０１０６】
以下、図２３をさらに参照し、本発明の好ましい実施の形態によるキーデータ符号化器について説明する。図２３は、本発明のキーデータ符号化方法を示すフローチャートである。
【０１０７】
キーデータが符号化器に入力されれば、キーデータの総数及び各キーデータの桁数などの情報はヘッダ符号化器４００に入力されて符号化され、入力されたキーデータは線形キー符号化器９００において線形キー領域、すなわち、一定の時間間隔をおいてキーフレームが存在してキーデータが同じ差を有し、キーデータが線形に変わる領域の存否を検索し、検索された線形領域を先に符号化する（Ｓ９０００）。
【０１０８】
３Ｄｍａｘ、Ｍａｙａなどの有名な３次元応用ソフトウェアは、特定の領域が一定の時間間隔を有するキーを用い、キーフレームに基づくアニメーションを生成する。この場合、線形キーデータ領域は、線形領域が始まるキーデータ、終わるキーデータ及び中間に存在するキーフレームの数さえ分かれば簡単にキーデータを符号化できるので、インタポレータにおいて特定領域のキーの符号化のために線形予測を用いることは極めて有用である。
【０１０９】
線形予測に用いられる数式は、下記式４の通りである。
【０１１０】
【数４】
0003905834.tif 000009
【０１１１】
ここで、ｔｓは部分的に線形である領域が始まるキーのデータを示し、ｔＥは、部分的に線形である領域が終わるキーのデータを示し、Ｓは、ｔｓのインデックスを、Ｅは、ｔＥのインデックスを各々示す。第Ｓ番目のキーデータ及び第Ｅ番目のキーデータに対応する特定の領域において前記式４により線形的に予測されたキーデータと実際のキーデータとの誤差は、下記式５により計算できる。
【０１１２】
【数５】
0003905834.tif 000010
【０１１３】
もし、前記式５により計算された誤差値のうち最大誤差値が所定の臨界値以下であれば、ｔｉは［ｔｓ，ｔＥ］区間及び所定の誤差内において類似線形であると言える。最大誤差値及び特定の領域が類似線形であるか否かは、下記式６により決められる。
【０１１４】
【数６】
0003905834.tif 000011
【０１１５】
0003905834.tif 000012
こで、ｎＢｉｔｓは符号化に用いられる符号化ビット数を示す。
【０１１６】
一旦、線形キー符号化器９００は、部分的に線形である領域を見つければ、領域の開始点のキーデータ及び終了点のキーデータは実数変換部９０５に出力し、線形キー領域に含まれるキーの数はヘッダ符号化器４００に出力して符号化する。このように、線形符号化を用いることにより、符号化するデータの量を大いに低減できるということが分かる。開始キーデータ及び終了キーデータは、実数変換部９０５において後述する実数変換過程により符号化される。
【０１１７】
実数変換部９０５は、開始キーデータ及び終了キーデータを符号化するために２進数の体系で表わされたキーデータを１０進数の体系に変換する。
【０１１８】
コンピュータは、実数を３２ビットの２進数の形で貯蔵する。実数が２進数の形で与えられれば、実数変換部９０５は、実数を１０進数の体系の仮数及び指数に変換する。すなわち、下記式７のように変換される。
【０１１９】
【数７】
0003905834.tif 000013
【０１２０】
例えば、実数１２．３４をコンピュータにて２進数の形で表わせば、下記の通りである。
0003905834.tif 000014
１：  符号
２：  ２進数の体系における仮数
３：  ２進数の体系における指数
【０１２１】
この数を前記式７により１０進数で表わせば、下記の通りである。
0003905834.tif 000015
１：  符号
２：  １０進数の体系における仮数
３：  １０進数の体系における指数
【０１２２】
１０進数の体系の仮数及び指数をビットストリームに含めるためには、各々が必要とするビット数を計算しなければならない。まず、指数は−３８〜３８の範囲の値を有するため、指数は符号を含んで７ビットで表わせる。また、仮数は、桁数に応じて必要なビットの数が決められる。仮数の値及びこれに必要なビット数（但し、符号ビットは除く。）を下記表２に示す。
【表２】
0003905834.tif 000016
【０１２３】
一方、前記のような過程により検索されて変換された線形キー領域の開始キーデータ及び終了キーデータは、図２４に示されたような符号化過程により符号化され、ヘッダ符号化器４００に出力されてビットストリームに貯蔵される。
【０１２４】
図２４は、実数変換部９０５が入力された２つの実数を符号化する過程を示す。図２４を参照し、実数変換部９０５が変換された実数を符号化する過程について説明する。
【０１２５】
実数変換部９０５は、線形キー符号化器９００から元のキーデータの桁数（ｏｒｉｇｉｎａｌ  ｋｅｙ  ｄｉｇｉｔ）Ｋｄ、線形領域が始まるキーデータ（ｓｔａｒｔ  ｋｅｙ）Ｓ、線形領域が終わるキーデータ（ｅｎｄ  ｋｅｙ）Ｅを入力され、前記式７によりキーデータを変換する（Ｓ９０４０）。
【０１２６】
実数変換部９０５は、まず、Ｓを符号化するが、Ｓの桁数がＫｄと異なるかを判断し、桁数が異なれば、Ｓの桁数を求めてヘッダ符号化器４００に出力する（Ｓ９０４２）。この際、実数変換部９０５はＤｉｇｉｔ（）関数を用いてＳの桁数を求める。
【０１２７】
その後、実数変換部９０５は、Ｓの桁数が７より大きければ、所定のビット数を（本発明では、ＩＥＥＥ標準７５４のｆｌｏａｔｉｎｇ−ｐｏｉｎｔ  ｎｕｍｂｅｒ方式により３２ビット）を用い、Ｓの桁数がビットストリームに含まれるようにヘッダ符号化器４００に出力する（Ｓ９０４３）。
【０１２８】
一方、Ｓの桁数が０でなくて７より小さければ、実数変換部９０５は、Ｓの符号をヘッダ符号化器４００に出力し（Ｓ９０４４）、Ｓの仮数の絶対値の符号化に必要なビット数を前記表２から求め、求められたビット数として仮数の絶対値をヘッダ符号化器４００に出力する（Ｓ９０４５）。その後、Ｓの指数を求め、符号をヘッダ符号化器４００に出力し、指数を所定のビット数として（本発明の実施の形態では６ビット）ヘッダ符号化器４００に出力する（Ｓ９０４６）。このように、キーデータの変換により、ビットストリームに含まれるビット数は大幅に減る。
【０１２９】
一方、Ｓの桁数が０であれば、開始キーデータの符号化過程は終わり、終了キーデータを変換するための過程へ進む。なぜならば、桁数が０であれば、実数は０を意味するため、それ以上の符号化過程が不要であるからである。
【０１３０】
実数変換部９０５は、開始キーデータを変換して符号化した後に終了キーデータＥを変換する。Ｅの変換は、Ｓの変換と同じ過程を繰り返すが、単に、Ｅの指数がＳの指数と同じ値を有するか否かを判別し（Ｓ９０４７）、両値が同じであれば、これを示すフラグビットのみをヘッダ符号化器４００に出力し、両値が相異なれば、フラグビット及びＥの指数をＳの指数と同じ方式によりヘッダ符号化器４００に出力する（Ｓ９０４８）。
【０１３１】
一方、入力キーデータにおいて線形領域を除いたキーデータは量子化器９１０に入力され、所定の量子化ビットサイズであるｎＫｅｙＱｂｉｔにより量子化される。
【０１３２】
しかしながら、復号化器において量子化されたキーデータを復号化して用いる時には、元のキーデータと量子化されたキーデータとの誤差により元のキーデータが完全に復元できない。したがって、本発明の量子化器９１０は、単に入力されるキーデータから最大値及び最小値を求め、求められた値を用いて量子化可能であるだけではなく、量子化誤差最小化部９１５を含んで、量子化誤差が最小化可能に修正された最大値及び最小値を用いて量子化できる。
【０１３３】
量子化誤差最小化部９１５は、量子化誤差を最小化するために入力されたデータに対して予め量子化及び逆量子化を行い、量子化の誤差が最小となる量子化の範囲を制御する方法を用いる（Ｓ９１００）。
【０１３４】
具体的に説明すれば、固定された量子化に用いられる最大値をＭａｘとし、調節される量子化に用いられる最小値をＭｉｎとした時、Ｘｉを入力値、ｎＱｕａｎｔＢｉｔを量子
0003905834.tif 000017
及び誤差ｅｉは、各々下記式８により計算する。
【０１３５】
【数８】
0003905834.tif 000018
【０１３６】
誤差の和ｅｉを減らす方法には２種類があるが、一つは誤差の和が最小となるまでＭｉｎ値を調節することであり、他の一つは、下記の通りである。
【０１３７】
まず、Δｘが入力データの基本ステップサイズであり、ｎが任意の整数であり、ｉが０平均乱数ノイズであるとした時、入力キーデータシーケンスＸｉをＸｉ＝（ｉ＋ｎ）Δｘ＋εｉのように表わされる量子化された値であると仮定する。
【０１３８】
0003905834.tif 000019
【０１３９】
このような過程を通じて求められた量子化誤差を最小化するＭｉｎ値は、Ｍａｘ値及び量子化器９１０に入力されてキーデータの量子化に用いられる。
【０１４０】
量子化誤差が最小となる最大値Ｍａｘ及び最小値Ｍｉｎを受け取った量子化器９１０は、下記式９を用いてキーデータｆＫｅｙｉの量子化を行う（Ｓ９２００）。
【０１４１】
【数９】
0003905834.tif 000020
【０１４２】
ここで、ｉは、量子化されたキーデータのインデックスを、ｎＱＫｅｙｉは、量子化されたデータの整数配列を、ｆＫｅｙｉは、入力キーデータとしての実数配列を、ｆＫｅｙ  ｍａｘ及びｆＫｅｙ  ｍｉｎは、量子化誤差最小化部９１５において受け取られた最大値Ｍａｘ及び最小値Ｍｉｎを、ｎＫｅｙＱｂｉｔは量子化ビットサイズを各々示す。一方、前記式６において用いられた関数ｆｌｏｏｒ（ν）は実数ｖを入力され、ｖ以下の最大整数を出力する関数である。
【０１４３】
一方、本発明の量子化器９１０は、前記量子化誤差を最小化するアルゴリズムを用いず、簡単に、入力されたキーデータのうち最大値ｆＫｅｙ  ｍａｘ及び最小値ｆＫｅｙ  ｍｉｎを求めて量子化を行うこともできる。
【０１４４】
本発明の量子化過程を示す図２５を参照し、量子化過程を詳細に説明する。
【０１４５】
量子化器９１０は、キーデータを入力され（Ｓ９２１０）、量子化誤差最小化部９１５から最大値及び最小値が入力されたか否かをチェックする（Ｓ９２２０）。
【０１４６】
量子化器９１０は、量子化誤差最小化部９１５から最大値Ｍａｘ及び最小値Ｍｉｎが入力されたならば、量子化に用いる最大値ｆＫｅｙ  ｍａｘ及び最小値ｆＫｅｙ  ｍｉｎをＭａｘ及びＭｉｎとして設定し（Ｓ９２３０）、設定された最大値及び最小値を前記実数変換部９０５に出力する。量子化に用いられる最大値及び最小値は、前記実数変換過程を通じて変換され符号化されてヘッダ符号化器４００に出力されることにより、復号化に利用可能に最大値及び最小値をキーヘッダに含める。
【０１４７】
量子化器９１０は、量子化誤差最小化部９１５から入力された値がなければ、入力されたキーデータのうち最初のキーデータｆＫｅｙ０を最小値ｆＫｅｙ  ｍｉｎとして、そして最後のキーデータｆＫｅｙＮ−１を最大値ｆＫｅｙｍａｘとして設定する（Ｓ９２４０）。
【０１４８】
その後、量子化器９１０は、設定された最大値が１より小さく、且つ、最小値が０より大きいか否かを判断し（Ｓ９２５０）、そうでなければ、最大値及び最小値を前記実数変換部９０５に出力し、前記過程を通じて変換して符号化した後、ヘッダ符号化器４００に出力して復号化に利用可能に最大値及び最小値をキーヘッダに含める（Ｓ９２６０）。
【０１４９】
一方、最大値及び最小値が第Ｓ９２５０段階の条件を満足すれば、最大値及び最小値を復号化に利用可能にキーヘッダデータに含めるか否かを示すフラグをチェックする（Ｓ９２７０）。もし、フラグが最大値及び最小値をキーヘッダに含めるように設定されていれば、前記第Ｓ９２６０段階を行って最大値ｆＫｅｙ  ｍａｘ及び最小値ｆＫｅｙ  ｍｉｎを符号化した後にヘッダ符号化器４００に出力し、そうでなければ、量子化器９１０は、最大値及び最小値をキーヘッダに含めない。
【０１５０】
最大値及び最小値をキーヘッダに含めない場合には、キーデータ符号化器及びキーデータ復号化器が互いに最大値を１として、且つ、最小値を０として設定して符号化及び復号化を行うことを規約したケースに当たるため、量子化器９１０は、最小値ｆＫｅｙ  ｍｉｎを０として、そして最大値ｆＫｅｙ  ｍａｘを１として各々設定する（Ｓ９２８０）。このように設定された量子化に用いられる最大値及び最小値は、既に復号化器に知られているため、別途にキーヘッダに含めない。
【０１５１】
一方、量子化器９１０は、前記過程を通じて設定されたｆＫｅｙ  ｍａｘ及びｆＫｅｙ  ｍｉｎを前記式９に代入して入力されたキーデータを量子化し、量子化されたキーデータをＤＰＣＭ処理部９２０に出力する（Ｓ９２９０）。
【０１５２】
量子化されたキーデータを受け取ったＤＰＣＭ処理部９２０は、所定回数のＤＰＣＭを行って最小の散布度が生成される次数及びイントラキーデータをヘッダ符号化器４００に出力し、ＤＰＣＭ演算の行われたキーデータの差分データをシフト部９３０に出力する（Ｓ９３００）。
【０１５３】
以下、図２６を参照し、ＤＰＣＭ処理過程について説明する。ＤＰＣＭ処理部９２０は、入力されたキーデータに対してまず所定の回数だけＤＰＣＭ演算を行い、ＤＰＣＭが行われた回数はＤＰＣＭ次数として貯蔵する（Ｓ９３１０）。本発明の好ましい実施の形態では、３回のＤＰＣＭ演算を行った。
【０１５４】
その後、ＤＰＣＭ処理部９２０は、各次数のＤＰＣＭ演算の結果に対して散布度を計算する（Ｓ９３２０）。この時の散布度を示す統計値として分散、標準偏差、及び四分偏差などが用いられ、本発明の好ましい実施の形態では、四分偏差が散布度として用いられる。
【０１５５】
各次数のＤＰＣＭ演算の結果に対する散布度が計算されば、ＤＰＣＭ処理部９２０は、散布度が最小となるＤＰＣＭ次数及び該当次数のＤＰＣＭ結果を選択し、ＤＰＣＭ演算の結果はシフト部９３０に出力し、ＤＰＣＭ次数、各次数のイントラキーデータ及びその他のＤＰＣＭ演算において必要な情報はヘッダ符号化器４００に出力する（Ｓ９３３０）。但し、本発明の好ましい実施の形態では、キーの数が５より小さければ、１次ＤＰＣＭのみを行った。例えば、１次ＤＰＣＭが行われる時には、下記式１０を用いてＤＰＣＭ演算を行った。
【０１５６】
【数１０】
0003905834.tif 000021
【０１５７】
ここで、ｉは、量子化されたキーデータのインデックスを、ｎＱＫｅｙｉは整数配列を、そしてｉは差分データを各々示す。
【０１５８】
一方、ＤＰＣＭ処理部９２０は、選択されたＤＰＣＭの結果、及びＤＰＣＭされたキーデータの差分データを符号化する時に必要なビット数を計算し、所定の記憶場所（本発明の実施の形態では、ｎＱＳｔｅｐ＿ＤＰＣＭ）に貯蔵する（Ｓ９３４０）。但し、符号化に必要なビット数を計算する段階は、後述する符号化すべきキーデータを選択する段階において行っても良いということは当業者に取って自明である。
【０１５９】
ＤＰＣＭ結果を受け取ったシフト部９３０は、入力された差分データのうち頻度数が最も高い差分データ（以下、モードと称する。）を選択して全ての差分データからモードを引くことにより、符号化されるべきデータを０の周りに集中的に分布せしめて符号化に必要なビット数を減らす（Ｓ９４００）。
【０１６０】
シフト演算は、量子化された全てのキーデータの差分データからモードｎＫｅｙＳｈｉｆｔを引くことにより行われる。このようなシフト演算は、下記式１１で表わされる。
【０１６１】
【数１１】
0003905834.tif 000022
【０１６２】
ｉは、量子化されたキーデータのインデックスを示し、ｎＱＫｅｙｉは、整数配列を示し、ｎＫｅｙＳｈｉｆｔは、モード値を示す。シフト演算が行われた後には、キーデータの差分データのうち頻度数が最も高い差分データは０となるので、符号化に必要なビット数を大幅に低減できる。
【０１６３】
シフト演算が行われたキーデータは、フォルド処理部９４０及びＤＮＤ処理部９５０に出力され、モード値ｎＫｅｙＳｈｉｆｔは、ヘッダ符号化器４００に出力されてキーヘッダに含まれる。
【０１６４】
シフトされたデータを受け取ったフォルド処理部９４０は、ＤＮＤ演算を行うための前処理段階としてフォルド演算を行い、フォルド演算されたキーデータをＤＮＤ処理部９５０に出力する（Ｓ９５００）。
【０１６５】
フォルド演算は、０を中心として負数領域及び正数領域に様々に分布される差分データを正数領域または負数領域に集中させて差分データの範囲を狭めるためのものであり、この実施の形態では、下記式１２によりフォルド演算を行って差分データの分布を正数領域に集中させた。
【０１６６】
【数１２】
0003905834.tif 000023
【０１６７】
ここで、ｉは、量子化されたキーデータのインデックスを示し、ｎＱＫｅｙｉは、整数配列を示す。フォルド演算により、シフトされたキーデータの差分データのうち正数データは正の偶数に、負数のデータは正の奇数に各々変換される。
【０１６８】
フォルド処理部９４０は、フォルド演算が行われたデータを符号化する時に必要なビット数を計算して所定の記憶場所ｎＱＳｔｅｐ＿ｆｏｌｄに貯蔵する。第Ｓ９３００段階と同じく、符号化に必要なビット数の計算は、後述するエントロピ符号化する差分データを選択する段階において行っても良いということは当業者に取って自明である。一方、フォルド処理部９４０においてフォルト演算が行われたデータは、ＤＮＤ処理部９５０に出力される。
【０１６９】
ＤＮＤ処理部９５０は、エントロピ符号化の効率を高めるために、入力されたキーデータの差分データに対してＤＮＤ演算を所定の回数だけ行ってデータの範囲を狭める（Ｓ９６００）。
【０１７０】
以下、図２２を参照し、ＤＮＤ処理部９５０について説明する。ＤＮＤ処理部は、ＤＮＤ演算を行うＤＮＤ演算部９５２、符号化ビット数に応じてエントロピ符号化すべき差分データを選択する第１の差分データ選択部９５４、第１の差分データ選択部においてＤＮＤ演算の行われた差分データが選択されれば、ＤＮＤ演算の行われた差分データに対してシフト−アップ演算を行うシフト−アップ演算部９５６、及びＤＮＤ演算された差分データ及びシフト−アップ演算された差分データのうち散布度が小さい差分データを選択してエントロピ符号化器９６０に出力する第２の差分データ選択部９５８を備える。
【０１７１】
まず、ＤＮＤ演算部９５２において行われるＤＮＤ演算について説明する。
【０１７２】
フォルド演算された差分データがＤＮＤ演算部９５２に入力されれば、入力された差分データは半分に分けられ、上位範囲に位置する差分データはディバイド関数によって負数領域に移動する。ディバイド関数は、下記式１３のように定義される。
【０１７３】
【数１３】
0003905834.tif 000024
【０１７４】
ここで、ｊは、入力された差分データのインデックスであり、ｎＱＫｅｙｊは、整数配列を示し、ｎＫｅｙＭａｘは、入力されたフォルド演算された差分データのうち最大値を示す。差分データの分布が全体差分データが占める範囲の境界領域に集中している場合、ＤＮＤ演算はデータの全体領域を大幅に狭める効果がある。
【０１７５】
ディバイド演算後に散布度が計算されるが、この場合、最小限の符号化ビットサイズが選択されるように符号化に必要なビットサイズが散布度として用いられる。
【０１７６】
ディバイド演算が行われた後、ディバイド演算と類似した他のＤＮＤ演算のディバイド−アップ演算またはディバイド−ダウン演算が行われるが、行われるべき演算はディバイド演算後のデータの正数側及び負数側の範囲によって決められる。
【０１７７】
正数側の範囲の方が大きければ、下記式１４により定義されるディバイド−ダウン演算が行われる。
【０１７８】
【数１４】
0003905834.tif 000025
【０１７９】
一方、負数側の範囲の方が大きければ、下記式１５により定義されるディバイド−アップ演算が行われる。
【０１８０】
【数１５】
0003905834.tif 000026
【０１８１】
前記式において、ｊは、量子化されたキーデータのインデックスであり、ｎＱＫｅｙｊは、整数配列であり、ｎＱＫｅｙＭａｘは、ｎＱＫｅｙｊの最大値であり、ｎＱＫｅｙＭｉｎは、ｎＱＫｅｙｊの最小値である。
【０１８２】
以下、ＤＮＤ演算部９５２の演算過程を示す図２７を参照し、ＤＮＤ演算過程について説明する。
【０１８３】
ＤＮＤ演算部９５２は、フォルド処理部９４０からキーデータの差分データが入力されれば、入力された差分データのうち最大値ｎＫｅｙＭａｘ及び最小値ｎＫｅｙＭｉｎを求める（Ｓ９６１０）。その後、ＤＮＤ演算部９５２は、最大値及び最小値の絶対値を比較し（Ｓ９６２０）、最大値が最小値の絶対値以上であれば、求められた最大値を現在のＤＮＤ演算次数の最大値として設定する（Ｓ９６２２）。
【０１８４】
ＤＮＤ演算部９５２は、ＤＮＤ演算次数が１であるか否かをチェックし（Ｓ９６２４）、次数が１であれば、前記式１３に最大値ｎＫｅｙＭａｘを代入してＤＮＤ演算部９５２に入力された差分データに対してディバイド演算を行う（Ｓ９６３０）。
【０１８５】
ディバイド演算を行ったＤＮＤ演算部９５２は、符号化に必要なビットサイズを求めるための関数ｇｅｔＱＢｉｔを用い、ディバイド演算を行って狭まった差分データの範囲を符号化するために必要なビットサイズを測定する（Ｓ９６４０）。その後、現在のＤＮＤ演算次数が１であれば（Ｓ９６５０）、前記値をＤＮＤ演算後に最小符号化ビットサイズを示す値ｎＱＢｉｔＤＮＤに一旦貯蔵し、ＤＮＤ次数を１だけインクリメントする（Ｓ９６５５）。
【０１８６】
その後、ＤＮＤ演算部９５２は、前記過程を再び行うが、第Ｓ９６２４段階において次数が１でなければ、前記式１４にｎＫｅｙＭａｘ値を代入してディバイド−ダウン演算を行う（Ｓ９６３４）。ＤＮＤ演算部９５２は、ディバイド−ダウン演算が行われた差分データの符号化に必要なビット数を計算し（Ｓ９６４０）、この値が以前の次数のＤＮＤ演算により貯蔵された符号化に必要な最小値ｎＱＢｉｔＤＮＤより小さければ（Ｓ９６５２）、ＤＮＤ演算後に符号化に必要な最小ビットサイズをこの値に変える（Ｓ９６５８）。
【０１８７】
一方、第Ｓ９６２０段階において、最小値の絶対値が最大値より大きければ、当該次数の最大値を入力された最小値に更新し（Ｓ９６２３）、最小値を前記式１２に代入してディバイド−アップ演算を行う（Ｓ９６３８）。その後、ＤＮＤ演算部９５２は、ディバイド−アップ演算の行われた差分データの符号化に必要なビット数を計算し（Ｓ９６４０）、この値が以前の次数のＤＮＤ演算により貯蔵された符号化に必要な最小値ｎＱＢｉｔＤＮＤより小さければ（Ｓ９６５２）、ＤＮＤ演算後に符号化に必要な最小ビットサイズをこの値に変える（Ｓ９６５８）。
【０１８８】
ＤＮＤ演算部９５２は、所定の回数となるまで前記過程を繰り返すが、ＤＮＤ演算を行う回数は可変的である。例えば、この実施の形態は、ＤＮＤ演算を行う回数を７回として設定した。ＤＮＤ演算部９５２は、符号化に必要な最小ビットサイズｎＱＢｉｔＤＮＤ及びその時のＤＮＤ演算された差分データを第１の差分データ選択部９５４に出力し、その時の次数をヘッダ符号化器４００に出力してビットストリームに含める。
【０１８９】
第１の差分データ選択部９５４は、シフト演算された差分データ、フォルド演算された差分データ及びＤＮＤ演算された差分データを入力され、いかなる演算の結果をエントロピ符号化するかを決める。
【０１９０】
図２３をさらに参照すれば、第１の差分データ選択部９５４は、ＤＮＤ演算後に符号化に必要な最小ビット数ｎＱＢｉｔＤＮＤがＤＰＣＭ演算後の符号化ビットサイズｎＱＳｔｅｐ＿ＤＰＭＣ以上であれば（Ｓ９７００）、ＤＰＣＭ演算の結果を選択してシフト演算を行った後、シフトされた差分データをエントロピ符号化器９６０に出力してエントロピ符号化する（Ｓ９７１０）。この場合、ＤＮＤ次数は、−１として設定され、ヘッダ符号化器４００に出力されてキーヘッダに含まれる。
【０１９１】
しかし、ｎＱＢｉｔＤＮＤがＤＰＣＭ後の符号化ビットサイズより小さいものの、フォルド演算後の符号化ビットサイズ以上であれば（Ｓ９７２０）、第１の差分データ選択部９５４は、フォルド演算された差分データをエントロピ符号化器９６０に出力してエントロピ符号化する（Ｓ９７３０）。この場合、ＤＮＤ次数は、０として設定され、ヘッダ符号化器４００に出力されてキーヘッダに含まれる。
【０１９２】
もし、ＤＮＤ演算された後の差分データの符号化ビット数が最小であれば、第１の差分データ選択部９５４は、ＤＮＤ演算された差分データをシフト−アップ演算部９５６に出力し、シフトアップ演算部９５６は、差分データを入力され、ＤＮＤ演算された差分データに対して第１の散布度を計算すると共に（Ｓ９７４０）、ＤＮＤ演算された差分データに対して下記式１３で定義されるシフト−アップ演算を行った後（Ｓ９８００）、シフト−アップ演算された差分データの第２の散布度を再び計算する（Ｓ９８１０）。
【０１９３】
【数１６】
0003905834.tif 000027
【０１９４】
ここで、ｊは、量子化されたキーデータの差分データのインデックスであり、ｎＱＫｅｙｊは、整数配列であり、そしてｎＫｅｙＭａｘは、差分データのうち最大値を示す。
【０１９５】
ＤＮＤ演算された差分データ及びシフト−アップ演算された差分データを入力された第２の差分データ選択部９５８は、第１の散布度及び第２の散布度を比較し（Ｓ９９００）、シフト−アップ演算後の第２の散布度がＤＮＤ演算後の第１の散布度より小さければ、シフト−アップ演算が行われた差分データをエントロピ符号化器９６０に出力してエントロピ符号化し（Ｓ９９１０）、ＤＮＤ演算に用いられた最大値ｎＫｅｙＭａｘ及び最小値ｎＫｅｙＭｉｎ、そして、シフト−アップ演算に用いられた最大値ｎＫｅｙＭａｘをヘッダ符号化器４００に出力してキーヘッダに含める。
【０１９６】
しかし、ＤＮＤ演算後の第１の散布度がシフト−アップ演算後の第２の散布度より小さければ、第２の差分データ選択部９５８は、ＤＮＤ演算の行われた差分データをエントロピ符号化器９６０に出力してエントロピ符号化し（Ｓ９９２０）、ＤＮＤ演算に用いられた最大値ｎＫｅｙＭａｘ及び最小値ｎＫｅｙＭｉｎのみがヘッダ符号化器４００に出力される。本発明の好ましい実施の形態では、前記第１及び第２の散布度として標準偏差を用いた。
【０１９７】
エントロピ符号化器９６０は、符号化すべき差分データの性質に応じて２種の関数演算を行って差分データを符号化する。例えば、ＤＰＣＭが行われてシフト演算が行われた差分データ及びディバイド演算が行われた差分データは、正数及び負数を共に有するため、差分データの符号を含む符号化を行い、フォルド演算された差分データ及びシフト−アップ演算された差分データは正数値のみを有するため、符号を含まない符号化を行う。
【０１９８】
本発明の好ましい実施の形態では、符号を含む符号化関数としてｅｎｃｏｄｅＳｉｇｎｅｄＡＡＣ関数を用い、符号を含まない符号化関数としてｅｎｃｏｄｅＵｎｓｉｇｎｅｄＡＡＣ関数を用いて差分データを符号化する。
【０１９９】
図３０は、ｅｎｃｏｄｅＳｉｇｎｅｄＡＡＣ関数の一例を示す図面である。図３０を参照すれば、入力値が７４であり、この値に対する符号化ビット数が８であれば、この値の符号は０であり、この値の２進数は１００１０１０となる。符号及び全てのビットプレインは下記のような過程を通じて符号化される。
【０２００】
第１の段階：２進数をＭＳＢからＬＳＢにビットプレイン単位に符号化する。
第２の段階：符号化中に現在符号化されるビットが０でないか否かをチェックする。
第３の段階：もし、最初の０ではない値であれば、２進数の現在符号化ビットを符号化した後に符号を符号化する。
第４の段階：２進数の残りのビットを符号化する。
【０２０１】
ｅｎｃｏｄｅＵｎｓｉｇｎｅｄＡＡＣ関数は、符号無き値に対するコンテキストを用いて適応算術符号化ビットストリームに符号化する。これは、符号コンテキストがあるという点を除ければ、前記ｅｎｃｏｄｅＵｎｓｉｇｎｅｄＡＡＣ関数の処理過程と類似している。
【０２０２】
図３１ないし図４０は、本発明の好ましい実施の形態による演算が行われた後のキーデータを示す図面である。図３１ないし図４０において、横軸は各キーデータのインデックスを示し、縦軸はキーデータの値を示す。
【０２０３】
図３１は、本発明の符号化器に入力された元のキーデータを示す図面である。図３１に示されたキーデータが量子化器９１０に出力されて９ビットの量子化ビットで量子化されれば、図３２に示されたように、量子化されたキーデータが得られる。量子化されたキーデータに対してＤＰＣＭを行えば、図３３のように、キーデータの差分データが得られる。
【０２０４】
その後、量子化されたキーデータの差分データを約７のモード値にシフトすれば、図３４に示されたように、キーデータの差分データが得られ、シフトされた差分データにフォルド演算を行えば、図３５に示されたように、いずれも正数に変換されたデータが得られる。
【０２０５】
フォルドされたデータにＤＮＤ演算を行ったデータを図３６ないし図３８に示す。
【０２０６】
フォルドされたデータに対してまずＤＮＤ演算のうちディバイド演算を行った後の差分データを図３６に示す。示されたように、正数側の範囲は０〜２８であり、負数側の範囲は０〜−２９であるため、負数側の範囲がより広い。したがって、図３６に示されたデータに対してディバイド−アップ演算が行われ、ディバイド−アップ演算の結果を図３７に示す。
【０２０７】
ディバイド−アップ演算によりキーデータの負数側の範囲は正数側の範囲に比べて相当狭まり、ＤＮＤの次の次数においてディバイド−アップ演算された差分データに対してディバイド−ダウン演算が行われる。図３８は、図３７の差分データに対してディバイド−ダウン演算を行った結果を示す図面である。一方、ディバイド−ダウン演算されたキーデータに対してシフト−アップ演算を行った結果を図３９に示す。
【０２０８】
前記図３１ないし図３７では、キーデータ及び差分データの範囲が次第に狭まるということが分かる。しかし、シフト−アップ演算結果を示す図３９及び図３８を比較してみれば、シフト−アップ演算後の符号化されるべき差分データの範囲がより広がったということが分かる。したがって、最終的に符号化すべきキーデータの差分データは、ディバイド−ダウン演算が行われた差分データであることが図４０から分かる。
【０２０９】
一方、ヘッダ符号化器４００において符号化されてキーヘッダに貯蔵される情報を説明する。
【０２１０】
符号化されるべきキーデータが入力されれば、ヘッダ符号化器４００は、入力キーデータからキーデータの桁数及び符号化されるべきキーの総数を入力されて符号化する。その後、ヘッダ符号化器４００は、線形キー符号化器９００から線形キー符号化された線形キー領域の存否を示す情報及び線形キー領域のキーデータの数を入力され、実数変換部９０５から実数変換された線形キー領域の開始キーデータ及び終了キーデータを入力される。
【０２１１】
併せて、実数変換部９０５が量子化誤差最小化部９１５から量子化誤差が最小化となる最大値及び最小値を入力されて実数変換した場合には、変換された最大値及び最小値は逆量子化に利用可能に実数変換部９０５からヘッダ符号化器４００に入力されてキーヘッダに含まれる。また、量子化に用いられた量子化ビットサイズもヘッダ符号化器４００に入力されてキーヘッダに含まれる。
【０２１２】
また、ヘッダ符号化器４００は、ＤＰＣＭ処理部９２０からＤＰＣＭ演算次数及び各次数におけるイントラキーデータを入力され、シフト部９３０からシフト演算に用いられたモード値を入力され、ＤＮＤ処理部９５０からシフト−アップ演算が行われたか否か、散布度が最小となるＤＮＤ次数及び各ＤＮＤ次数における最大値及び最小値を入力される。最後に、ヘッダ符号化器４００は、エントロピ符号化器９６０から符号化に用いられた符号化ビット数を入力されてキーヘッダに符号化する。
【０２１３】
以下、図４１ないし図５５に基づき、本発明の望ましい実施例に係る回転インタポレータのキー値データ符号化器３００及び方法を説明する。
【０２１４】
図４１は、本発明の望ましい第１実施例に係るキー値データ符号化器３００の構成を示すブロック図である。
【０２１５】
図４を参照すれば、第１実施例のキー値データ符号化器３００は、各キーフレームのクォータニオンキー値データによって客体に適用される回転変換間の差だけの回転変換を示す回転差分値を計算し、前記回転差分値を量子化して回転差分データを出力する回転ＤＰＣＭ演算部１３００、量子化された回転差分データに対して選択的に線形ＤＰＣＭ演算及び循環ＤＰＣＭ演算を行う循環ＤＰＣＭ演算部１４００、回転ＤＰＣＭまたは循環ＤＰＣＭ演算された回転差分データをエントロピ符号化するエントロピ符号化器１４５０、及び符号化された回転インタポレータキー値データの復号化に必要な情報を符号化するキー値ヘッダ符号化器４００を含む。
【０２１６】
また、回転ＤＰＣＭ演算部１３００は、入力された現在キーフレームでの客体の回転変換値と以前キーフレームでの客体の回転変換値をクォータニオン乗算し、以前キーフレームでの客体の回転変換値と現在キーフレームでの客体の回転変換値間の回転差分値を計算する第１クォータニオン乗算器１３１０、第１クォータニオン乗算器１３１０から入力された回転差分値を非線形量子化して量子化された回転差分データを生成する量子化器１３４０、量子化された回転差分データを逆量子化して復元された現在キーフレームの回転差分値を生成する逆量子化器１３５０、及び現在キーフレームの回転差分値を以前キーフレームまで累積させて計算された以前キーフレームの回転変換値とクォータニオン乗算して現在キーフレームの回転変換値を復元する第２クォータニオン乗算器１３７０、次のキーフレームの回転変換値が入力されれば復元された現在キーフレームの回転変換値を第１クォータニオン乗算器１３１０に出力する遅延器１３９０を含む。
【０２１７】
以下、本発明の回転ＤＰＣＭ演算部で行われる回転ＤＰＣＭ演算の概念について説明する。
【０２１８】
従来のＭＰＥＧ−４  ＢＩＦＳ  ＰＭＦＣで用いられる線形ＤＰＣＭ方法では、現在キーフレームの客体の回転変換を示すクォータニオン回転変換値Ｑ１（Ｑ１＝（ｑ１，０，ｑ１，１，ｑ１，２，ｑ１，３））と次のキーフレームの客体の回転変換を示すクォータニオン回転変換値Ｑ２（Ｑ２＝（ｑ２，０，ｑ２，１，ｑ２，２，ｑ２，３））間の差分値を次の数式１７に応じて計算した。
【０２１９】
【数１７】
0003905834.tif 000028
【０２２０】
しかし、このような従来の方法は単純なクォータニオン成分間の差分値だけを計算するので実質的な回転差分値を反映する意味のある値ではない。したがって、このような方法は符号化される連続されたキー値データ間の冗長性を効率よく減少させられない。また、従来の方法は符号化されるビット数を減らすために４つのクォータニオン成分のうち最大値を有する成分を除いた３成分だけを符号化する。データ復元の観点で、従来の線形ＤＰＣＭ方法では各キー値データのうち符号化されていない最大のクォータニオン成分が如何なるものかを示す２ビット大きさの情報が付加的に符号化されて符号化器から復号化器に伝達されねばならない。
【０２２１】
したがって、本発明のキー値データ符号化器は、連続したキー値データ間の冗長性を減少させ、このような従来の技術の問題を解決するために、実質的な回転差分値を考慮する回転ＤＰＣＭ演算方法を提案する。
【０２２２】
0003905834.tif 000029
0003905834.tif 000030
クトルとする時、クォータニオン空間で回転変換は次の数式１８のように表される。
【０２２３】
【数１８】
0003905834.tif 000031
【０２２４】
0003905834.tif 000032
数を、ｘはクォータニオン乗算を示す。
【０２２５】
同じ方式でキーデータがｋｉの時、クォータニオン空間で回転変換は次の数式１９で表される。
【０２２６】
【数１９】
0003905834.tif 000033
【０２２７】
連続された２つのキー値データによって与えられる連続された回転変換間の回転差分値は前述した数式１８及び数式１９から次の数式２０のように計算される。
【０２２８】
【数２０】
0003905834.tif 000034
【０２２９】
したがって、回転差分値は次の数式２１で定義される。
【０２３０】
【数２１】
0003905834.tif 000035
【０２３１】
一方、本発明の望ましい第１実施例に係るキー値データ符号化器３００は、量子化誤差が次の回転差分値まで伝播されることを防止するために、次のキーフレ
0003905834.tif 000036
転差分値を数式２１から次の数式２２のように変形して定義する。
【０２３２】
【数２２】
0003905834.tif 000037
【０２３３】
以下、本発明の望ましい第１実施例に係るキー値データ符号化方法を説明するフローチャートである図４２を参照し、キー値データ符号化方法を説明する。
【０２３４】
本発明のキー値データ符号化器は、キー値データの符号化のためにＤＰＣＭ演算次数、エントロピ符号化モード、及びキー値データを入力される（Ｓ１３０００）。
【０２３５】
その後、クォータニオンで表されたキー値データＱｉを入力された第１クォータニオン乗算器１３１０は入力されたキー値データＱｉが最初のキー値データＱ０か否かをチェックし（Ｓ１３０５０）、最初のキー値データであればクォータニオン乗算を行う累積されたクォータニオン変換値がないので、入力されたキー値データを量子化器１３４０に出力し、最初のキー値データでなけれら復元された以
0003905834.tif 000038
ン空間で以前キーフレームと現在キーフレーム間のキー値データの差分値のクォ
0003905834.tif 000039
【０２３６】
量子化器１３４０は第１クォータニオン乗算器１３１０から最初のキー値デー
0003905834.tif 000040
子化する（Ｓ１３３００）。
【０２３７】
あらゆる回転クォータニオン差分値は単位クォータニオンで表されるので、回転差分値を示すクォータニオンのｎｏｒｍは常に１であり、よって、符号化されていない１成分データは残りの３成分データによって復号化されうる。本発明の望ましい実施例に係る回転インタポレータキー値データ符号化器３００は符号化するデータの量を減らすために、回転差分値のうち最初の成分を除いた３成分だけを符号化する。したがって、回転ＤＰＣＭ演算部に含まれた量子化器１３４０は符号化される回転差分値を構成する４つの成分のうち最初の成分を除いた３つの成分だけを量子化する。
【０２３８】
但し、本発明の量子化器１３４０は一般の線形量子化の代りに非線形量子化を行う。その理由を回転差分値の各成分のＰＤＦ（Ｐｒｏｂａｂｉｌｉｔｙ  Ｄｉｓｔｒｉｂｕｔｉｏｎ  Ｆｕｎｃｔｉｏｎ）の典型的な分布を示す図４３に基づいて説明する。
【０２３９】
図４３に示されたように、一般に回転差分値の各成分値は０を中心に分布する。これは回転差分値は回転情報に存在する冗長性を効率よく減らせることを意味し、これをエネルギーの集中と呼ばれる。したがって、回転差分値が低い範囲の値をより充実に反映して回転差分値を量子化するために、回転差分値の低い範囲により精密な量子化を行う必要がある。このために本発明の量子化器１３４０は非線形量子化を行う。ここで、本発明の量子化器１３４０は回転差分値に対して非線形スケールファクターを割り当てるためにアークタンジェント曲線を用いる。
【０２４０】
図４４は、本発明の量子化に用いられるアークータンジェント曲線を示す図面である。
【０２４１】
図４４に示されたように、アークタンジェント曲線は高い範囲に位置した入力値に対して適切な解像度を提供しつつも、低い範囲に位置した入力値に対してより精密な解像度を提供する。本発明の量子化器１３４０は非線形スケール関数を用いて次の数式２３のように回転差分値を量子化する（Ｓ１３３００）。
【０２４２】
【数２３】
0003905834.tif 000041
【０２４３】
0003905834.tif 000042
数を各々示し、ｆｌｏｏｒ（ｘ）は入力されたｘをｘ以下の最大整数に変換する関数である。
【０２４４】
量子化器１３４０は入力された回転差分値に対して量子化を行った後、量子化された回転差分データが符号化する最後のキー値データに対する回転差分データであるか否かをチェックし、最後のキー値データに対する回転差分データであれば、計算された回転差分データを循環ＤＰＣＭ演算部１４００に出力し、最後のキー値データに対する回転差分データでなければ、量子化された回転差分データを逆量子化器１３５０に出力する（Ｓ１３４００）。
【０２４５】
量子化された回転差分データを入力された逆量子化器１３５０は回転差分データを逆量子化して復元された回転差分値を出力する（Ｓ１３５００）。
【０２４６】
ところが、前述したように、本発明のキー値データ符号化器３００は符号化されるビット数を減らすために、クォータニオンで表される回転差分値を構成する４うの成分値のうち最初の成分を除いた３成分を量子化して符号化する。復号化装置の逆量子化器２４３０（図６１参照）及び符号化装置の逆量子化器１３５０は量子化された回転差分データの３成分から量子化されていない最初の成分を復元せねばならない。あらゆる回転クォータニオン差分値は単位クォータニオンで表されるので、回転差分値を示すクォータニオンのｎｏｒｍは常に１であり、よって、量子化されていない最初の成分データは次の数式２４によって復元されうる。
【０２４７】
【数２４】
0003905834.tif 000043
【０２４８】
0003905834.tif 000044
復元された３成分を用いて復元された最初の成分を示す。
【０２４９】
この場合、数式２４を用いて回転差分値の最初の成分を復元するためには最初の成分が常に正数であることが要求される。これは３次元空間で客体の回転変換にクォータニオンを適用する時に現れる次の数式２５のようなクォータニオンの性質を用いれば充足されうる。
【０２５０】
【数２５】
0003905834.tif 000045
【０２５１】
数式２５は３次元空間で客体に回転変換が適用される時、回転変換値Ｑ及び−Ｑは同一な物理的意味を有することを示す。したがって、符号化装置で回転差分値の最初の成分が負数であれば、回転差分値のあらゆる成分に負の符号を付することによって（−１をかけることによって）容易に正数に変換しうる。
【０２５２】
但し、この場合、復元された回転差分値の３成分それぞれの自乗の和が量子化
0003905834.tif 000046
子化器１３４０によって量子化されうる最小値より小さな値と見なしても良い。物理的な側面で、これは客体に約１８０°に近い角の回転変換が行われたものと
0003905834.tif 000047
ような決定方法は符号化装置の逆量子化器１３５０にも適用される。例えば、量
0003905834.tif 000048
決定するために次の数式２６が用いられる。
【０２５３】
【数２６】
0003905834.tif 000049
【０２５４】
数式２６において、αは任意の定数を、ｍは量子化ビット数を示す。
【０２５５】
このような方法は、従来のＭＰＥＧ−４  ＢＩＦＳ  ＰＭＦＣ方式で復号化のために復号化器に伝えられた、それぞれのキー値データに対する２ビットの付加的な情報が不要なので、Ｎ個のキー値データを符号化する時、従来の方法に比べて２Ｎビットだけ符号化されるビット数を減らす効果がある。
【０２５６】
逆量子化器１３５０から出力された復元された回転差分値は第２クォータニオン乗算器１３７０に入力され、第２クォータニオン乗算器１３７０は入力されたキーフレームが符号化される最初のキーフレームか否かをチャックし（Ｓ１３６００）、最初のキーフレームである場合には逆量子化器１３５０から入力された
0003905834.tif 000050
変換値を遅延器１３９０に出力する（Ｓ１３８００）。
【０２５７】
一方、第２クォータニオン乗算器１３７０は入力されたキーフレームが最初の
0003905834.tif 000051
【０２５８】
第２クォータニオン乗算器１３７０は復元された現在キーフレームの回転変換
0003905834.tif 000052
第１クォータニオン乗算器１３１０は次の符号化されるキーフレームの回転変換値Ｑｉが入力されれば、遅延器１３９０から現在キーフレームの以前キーフレー
0003905834.tif 000053
【０２５９】
生成された回転差分値は量子化器１３４０に出力されて前述したように量子化され（Ｓ１３３００）、量子化器１３４０は入力された回転差分値が最後のキー値データに関するものであれば、回転差分値を量子化して生成された回転差分データを循環ＤＰＣＭ演算部１４００に出力する（Ｓ１３４００）。
【０２６０】
循環ＤＰＣＭ演算部１４００は入力された値のうちＤＰＣＭ次数をチャックし、ＤＰＣＭ次数が０であれば回転差分データに線形及び循環ＤＰＣＭ演算を行わず、エントロピ符号化器１４５０に出力する（Ｓ１４０００）。ＤＰＣＭ次数が０でなければ、量子化された回転差分データに線形ＤＰＣＭ演算及び循環ＤＰＣＭ演算を行う（Ｓ１４１００）。
【０２６１】
図４５は、量子化器１３４０から出力された差分データの一例を示し、図１０は量子化器１３４０から出力された差分データに線形ＤＰＣＭ演算が行われた結果を示す。
【０２６２】
図４６に示されたように、線形ＤＰＣＭ演算が行われた時、符号化される差分データの範囲は最初量子化された値の範囲の２倍まで増加しうる。したがって、循環ＤＰＣＭ演算の目的は差分データの範囲を入力された量子化されたデータの範囲に保ちつつＤＰＣＭ演算を行うことである。
【０２６３】
循環ＤＰＣＭ演算は量子化範囲の最大値と量子化範囲の最小値とが相互連結されていると仮定する。したがって、もし、２つの連続された量子化されたデータ間の線形ＤＰＣＭ結果である差分データが量子化範囲の最大値の半分を超えれば、差分データ値から最大値を減算することで、差分データ値をより小さな値で表現しうる。
【０２６４】
また、もし、２つの連続された量子化されたデータ間の線形ＤＰＣＭ結果である差分データが量子化範囲の最小値の半分より小さければ、差分データ値に最大値を加算することで、差分データ値をより小さな範囲の値に表現しうる。
【０２６５】
0003905834.tif 000054
２つの連続された回転差分データの線形ＤＰＣＭ演算は次の数式２７に応じて行われる。
【０２６６】
【数２７】
0003905834.tif 000055
【０２６７】
また、循環ＤＰＣＭ演算は数式２７に応じて計算された差分データに対して次の数式２８に応じて行われる。
【０２６８】
【数２８】
0003905834.tif 000056
【０２６９】
数式２８でｎＱＢｉｔｓは量子化ビット数である。図４６に示されたＤＰＣＭ演算された差分データに対して循環ＤＰＣＭ演算を行った結果を図４７に示した。図４７に示されたように循環ＤＰＣＭ演算された差分データは単純に線形ＤＰＣＭ演算された差分データよりデータの範囲が大きく減少したことが分かる。
【０２７０】
ＤＰＣＭ次数に応じて回転差分データまたは循環ＤＰＣＭ演算された回転差分データを循環ＤＰＣＭ演算部１４００から入力されたエントロピ符号化器１４５０はビットの冗長性を除去することによってデータを符号化する。
【０２７１】
図４２を再び参照すれば、エントロピ符号化器１４５０はまずエントロピ符号化モードを調べる（Ｓ１４５００）。
【０２７２】
エントロピ符号化モードがＢｉｎａｒｙエントロピ符号化モードである場合にはＳｉｇｎｅｄＡＡＣ（）関数を用いて差分データを符号化し（Ｓ１４６００）、エントロピ符号化モードがＵｎａｒｙエントロピ符号化モードである場合にはＵｎａｒｙＡＡＣ（）関数を用いて差分データをエントロピ符号化する（Ｓ１４７００）。
【０２７３】
ＳｉｇｎｅｄＡＡＣ（）関数は入力されたデータの符号及び大きさを各々ビットプレイン単位で符号化する適応２進算術符号化器を用いて入力された差分データを符号化し、その詳細な符号化方法は図３０で説明した。
【０２７４】
一方、ＵｎａｒｙＡＡＣ関数は符号化する値を一連の０に変換した後、前記０が終了されたことを示す１及びこの値の符号を示す１ビットを用いてシンボルを符号化する。この際、一連の０は値の大きさを示す。
【０２７５】
図４８を参照してＵｎａｒｙＡＡＣ関数について説明する。例えば、符号化する値が２５６であれば、ＵｎａｒｙＡＡＣ関数は図４８に示されたように、値を２５６個の０と、０が終了されたことを示す１及び値の符号（正数）を示す０を符号化する。ＵｎａｒｙＡＡＣ関数によって符号化する時、シンボルのビット冗長性が増加するので符号化効率が高まる。
【０２７６】
以上、本発明の望ましい第１実施例に係る回転インタポレータのキー値データ符号化器３００について説明した。
【０２７７】
以下では、本発明の望ましい第２実施例に係るキー値データ符号化器３００を説明する。本発明の第２実施例のキー値データ符号化器３００は第１実施例のキー値データ符号化器３００において量子化による回転方向誤差を訂正する構成をさらに含む。
【０２７８】
図４９は、回転差分値を用いてクォータニオン回転変換値を符号化する時に生じる回転方向誤差を説明する図面である。回転方向誤差は、本発明の符号化装置で行われるクォータニオン符号化方法が損失符号化方法であるために発生する。
【０２７９】
図４９において、Ｑｉがｉ番目のキーフレームで客体に適用される現在回転変換
0003905834.tif 000057
変換値によって回転された客体の位置は図４９に示されたように４つの領域で表現されうる。
【０２８０】
すなわち、客体が最短経路を通じてＱｉ−１からＱｉに回転し、Ｑｉ−１及びＱｉによって回転された客体が領域３及び領域１に位置すれば、客体はＱｉ−１からＱｉに反時計方向に回転する。また、客体が最短経路を通じてＱｉ−１からＱｉに回転し、Ｑｉ−１及びＱｉによって回転された客体が領域２及び領域４に位置すれば、客体はＱｉ−１からＱｉに時計方向に回転する。
【０２８１】
一方、客体が符号化されてから復号化された回転情報に応じて回転すれば、復
0003905834.tif 000058
４にあるならば、客体は時計方向に回転する。このような事実から、元の符号化された回転変換値で客体を回転させる場合と、復号化された回転変換値で客体を回転させる場合とに、領域１及び領域２で客体が相互反対方向に回転できることが分かる。
【０２８２】
これは、クォータニオン回転変換値を符号化する時、損失符号化が行われるの
0003905834.tif 000059
号化で不可避に起こるので、これを解決するために元の回転方向と反対方向への誤った回転を最小化したり、誤った回転方向を元の回転方向と同一にする必要がある。本発明では、後者の方法を提案する。
【０２８３】
再び図４９を参照して本発明の回転方向誤差を訂正する基本概念を簡単に説明する。領域１及び領域２のような回転方向誤差が検出されれば、符号化されるクォータニオン回転差分値は誤った回転方向が元の方向と同一になるべく強制的に制御される。この場合に、回転方向の不一致が領域２でも生じるが、領域２では領域１とは違って元のクォータニオン値と復元されたクォータニオン値間の差が相対的に小さい。したがって、本発明の第２実施例に係る回転方向訂正は領域１に対してだけ行われる。
【０２８４】
以下、図５０ないし図５３に基づいて回転方向誤差訂正機能を行う本発明の第２実施例に係るキー値データ符号化器３００を説明する。本発明の第２実施例のキー値データ符号化器３００は、第１実施例のキー値データ符号化器３００と回転ＤＰＣＭ演算部の構成にのみ違いがあり、残りの構成は第１実施例の場合と同一である。したがって、第２実施例の回転ＤＰＣＭ演算部の構成だけを説明する。
【０２８５】
図５０は本発明の望ましい第２実施例に係る回転ＤＰＣＭ演算部１８００の構成を示すブロック図であり、図５１は図５０に示された回転方向誤差計算器１８２０の構成を示すブロック図である。
【０２８６】
図５０を参照すれば、第２実施例に係る回転ＤＰＣＭ演算部１８００は前述した第１実施例の回転ＤＰＣＭ演算部の構成に、現在キーフレームでの客体の回転変換値と以前キーフレームの復元された回転変換値を入力されて回転方向誤差を計算する回転方向誤差計算器１８２０、回転方向誤差計算器１８２０から入力された回転誤差値に応じて復号化時に回転方向が変更される程の誤差の発生有無を検出する回転方向誤差検出部１８３０、以前キーフレームの復号化された回転変換値によって回転された位置から元の回転方向と同じ方向に、１８０°回転に近い位置に客体が回転すべく第１クォータニオン乗算器１８１０から入力された回転差分値を訂正して出力する回転方向訂正部１８１５、及び回転方向誤差検出部１８３０から入力された値に応じて回転方向訂正部１８１５から入力された回転方向が訂正された回転差分値と第１クォータニオン乗算器１８１０から入力された回転差分値のうち何れか１つを選択して量子化器１８４０に出力する回転方向選択部１８３５をさらに含む。
【０２８７】
また、図５１を参照すれば、図５０に示された回転方向誤差計算器１８２０は入力された回転変換値を次のフレームの回転変換値が入力されるまで貯蔵する遅延器１８２２、入力回転変換値及び遅延器１８２２から出力される以前キーフレームの回転変換値を入力されてクォータニオン乗算して量回転変換値間の回転差分値を計算する第３クォータニオン乗算器１８２４、遅延器１８２２から出力される以前キーフレームの回転変換値及び第２クォータニオン乗算器１８７０から入力される以前キーフレームの復元された回転変換値間の回転差分値を計算する第４クォータニオン乗算器、及び入力回転変換値及び第２クォータニオン乗算器１８７０から入力される以前キーフレームの復元された回転変換値間の回転差分値を計算する第５クォータニオン乗算器１８２８を含む。
【０２８８】
以下、図５２をさらに参照して本発明の望ましい第２実施例に係る回転ＤＰＣＭ演算方法を説明する。
【０２８９】
現在符号化される回転インタポレータのキー値データＱｉは回転ＤＰＣＭ演算部１８００の第１クォータニオン乗算器１８１０及び回転方向誤差計算器１８２０に入力される（Ｓ１９０００）。
【０２９０】
第１クォータニオン乗算器１８１０は前述した第１実施例の第１クォータニオン乗算器と同一に現在入力された回転変換値と第２クォータニオン乗算器１８７０から入力された以前キーフレームの復元された回転変換値をクォータニオン乗
0003905834.tif 000060
択部１８３５に出力する（Ｓ１９１００）。
【０２９１】
回転方向訂正部１８１５は入力された回転差分値を次の数式２９に応じて訂正し、訂正された回転差分値Ｑｓを回転方向選択部１８３５に出力し、回転方向誤差計算器１８２０は入力された現在キーフレームの回転変換値Ｑｉと遅延器１８９０を通じて第２クォータニオン乗算器１８７０から入力された以前キーフレームの
0003905834.tif 000061
計算し、回転方向誤差検出部１８３０は回転方向誤差計算器１８２０から入力された回転差分値を用いて回転方向誤差の発生有無を検出して回転方向選択部１８３５に出力する（Ｓ１９２００）。
【０２９２】
【数２９】
0003905834.tif 000062
【０２９３】
0003905834.tif 000063
８２０、回転方向誤差検出部１８３０、及び回転方向訂正部１８１５については図５３に基づいて後述する。
【０２９４】
回転方向選択部１８３５は後述する回転方向誤差検出部１８３０から入力される論理値に応じて復号化された時、元の回転方向とは反対に客体の回転が起こる程の回転方向誤差が生じたかを決定し、回転方向誤差が生じていないならば第１クォータニオン乗算器１８１０から入力される回転差分値を量子化器１８４０に出力し、回転方向誤差が生じたならば回転方向訂正部１８１５から入力される訂正された回転差分値を量子化器１８４０に出力する（Ｓ１９３００）。
【０２９５】
量子化器１８４０は回転方向選択部１８３５から入力された元回転差分データ
0003905834.tif 000064
方法で量子化する（Ｓ１９４００，Ｓ１９５００）。
【０２９６】
量子化器１８４０は量子化された回転差分データが最後のキー値データに関するものかをチェックし（Ｓ１９６００）、最後のキー値データに関するものならば、量子化された回転差分データを第１実施例のように循環ＤＰＣＭ演算部に出力し（Ｓ１９７００）、最後のキー値データがなければ逆量子化器１８５０に出力する。
【０２９７】
0003905834.tif 000065
１８７０に出力する（Ｓ１９８００）。
【０２９８】
0003905834.tif 000066
成する。第２クォータニオン乗算器１８７０は復元された現在キーフレームの回転変換値を遅延器１８９０を通じて第１乗算器及び回転方向誤差計算器１８２０に出力する（Ｓ１９９００）。
【０２９９】
以下、図５３をさらに参照し、回転方向誤差計算器１８２０、回転方向誤差検出部１８３０、及び回転方向訂正部１８１５の動作について説明する。
【０３００】
回転方向誤差計算器１８２０は前述した図４９の領域２ないし４に該当する回転差分値を各々計算する。
【０３０１】
回転方向誤差計算器１８２０は、現在符号化されるキーフレームのキー値データの回転変換値を入力され、遅延器１８２２を通じて現在キーフレーム以前キーフレームの復元された回転変換値を入力され、回転方向誤差を計算する（Ｓ１９２２０）。
【０３０２】
現在キーフレームの回転インタポレータのキー値データの回転変換値は、第３クォータニオン乗算器１８２４及び第５クォータニオン乗算器１８２８に直接入力され、次のキーフレームの回転変換値が入力されれば遅延器１８２２を通じて第４クォータニオン乗算器１８２６に入力される。また、第２クォータニオン乗算器１８７０から出力された以前キーフレームの復元された回転変換値は第４クォータニオン乗算器１８２６及び第５クォータニオン乗算器１８２８に入力される。
【０３０３】
第３クォータニオン乗算器１８２４は、現在キーフレームの回転変換値と以前
0003905834.tif 000067
ＱＡを回転方向誤差検出部１８３０に出力する。回転差分値ＱＡは時間間隔［ｔｉ−１，ｔｉ］で客体の元回転方向を示す。
【０３０４】
第４クォータニオン乗算器１８２６は、以前キーフレームの回転変換値と以前
0003905834.tif 000068
回転差分値ＱＢを回転方向誤差検出部１８３０に出力する。第４クォータニオン乗算器１８２６で計算された回転差分値ＱＢは時間ｔｉ−１で量子化誤差による客体の回転方向誤差及び回転方向を示し、図４９の領域２に対応する。
【０３０５】
第５クォータニオン乗算器１８２８は、現在キーフレームの回転変換値と以前
0003905834.tif 000069
回転差分値ＱＣを回転方向誤差検出部１８３０に出力する。第５クォータニオン乗算器１８２８で計算された回転差分値ＱＣは時間ｔｉで符号化される回転差分値を示し、図４９の領域４に対応する。
【０３０６】
回転方向誤差検出部１８３０は、回転方向誤差計算器１８２０から入力された回転差分値ＱＡ，ＱＢ及びＱＣを用いて図４９に示された領域１のように復号化時に客体の回転方向が元の回転方向と反対となる場合の発生有無を検出する（Ｓ１９２４０）。このために回転方向誤差検出部１８３０は次の数式１７ないし２１に記載された条件を満たすか否かをチェックする。まず、回転方向誤差検出部１８３０は次の数式３０に記載された条件を満たすかをチェックする。
【０３０７】
【数３０】
0003905834.tif 000070
【０３０８】
数式３０において、回転方向誤差計算器１８２０から入力された回転差分値ＱＡ
0003905834.tif 000071
計算器１８２０から入力された回転差分値ＱＣの最初の成分を除いた成分よりなる３次元ベクトルを示す。数式３０は前述した３次元ベクトルの内積が０より小さいか否かを示す。
【０３０９】
もし、数式３０の内積が０より小さければ、回転差分値ＱＡ及び回転差分値ＱＣによる回転の方向が相反することを示す。数式３０の内積が０より小さければ論理値は真（ｔｒｕｅ）と定義され、内積が０より大きければ論理値は偽（ｆａｌｓｅ）と定義される。
【０３１０】
【数３１】
0003905834.tif 000072
【０３１１】
数式３１において、回転方向誤差計算器１８２０から入力された回転差分値ＱＢ
0003905834.tif 000073
算器１８２０から入力された回転差分値ＱＣの最初の成分を除いた成分よりなる３次元ベクトルを示す。数式３１は前述した３次元ベクトルの内積が０より小さいか否かを示す。
【０３１２】
もし、数式３１の内積が０より小さければ、回転差分値ＱＢ及び回転差分値ＱＣによる回転の方向が相反することを示す。数式３１の内積が０より小さければ論理値は真と定義され、内積が０より大きければ論理値は偽と定義される。
【０３１３】
【数３２】
0003905834.tif 000074
【０３１４】
数式３２においてｑＡ，０は回転差分値ＱＡの最初の成分を示し、所定の定数ＡＴＨ
0003905834.tif 000075
より大きければ、数式３２に記載された論理式の値は真と定義され、そうでなければ偽と定義される。数式３２が偽ということは、実際に本発明の符号化装置を
0003905834.tif 000076
意味する。なぜなら、このような小さな誤差による映像の歪曲は主観的な視覚によって判断される歪曲が激しくないだけでなく、本発明が提案する誤差測定方法によって計算する時にも顕著な映像の歪曲を起こさないからである。
【０３１５】
【数３３】
0003905834.tif 000077
【０３１６】
数式３３でｑＢ，０は回転差分値ＱＢの最初の成分を示し、所定の定数ＡＴＨは数式
0003905834.tif 000078
より大きければ、数式３３に記載された論理式の値は真と定義され、そうでなければ偽と定義される。
【０３１７】
【数３４】
0003905834.tif 000079
【０３１８】
数式３４でｑＣ，０は回転差分値ＱＣの最初の成分を示し、所定の定数ＡＴＨは数式
0003905834.tif 000080
より大きければ、数式３４に記載された論理式の値は真と定義され、そうでなければ偽と定義される。
【０３１９】
回転方向誤差検出部１８３０は前述した数式３０ないし数式３４に記載された論理演算結果に対してＡＮＤ演算を行い、ＡＮＤ演算結果を回転方向選択部１８３５に出力する。
【０３２０】
0003905834.tif 000081
有する。第１クォータニオン乗算器１８１０はこの２つの入力値を用いて回転差分値を出力する。前述したように、領域１の場合に、回転差分値を受信した復号化器は客体を時計方向に回転させる。しかし、客体はＱｉ−１によって回転された位置からＱｉによって回転された位置に回転せねばならないために、元の回転方向は半時計方向にならねばならない。
【０３２１】
0003905834.tif 000082
時計方向に回転すべく方向を訂正する。
【０３２２】
0003905834.tif 000083
方向に１８０°回転に近い位置に回転すべく新しい回転情報を設定する。したがって、回転方向は元の回転方向に訂正され、回転方向誤差は最小化される。このような、回転方向訂正部１８１５は第１クォータニオン乗算器１８１０から現在
0003905834.tif 000084
訂正された回転差分データを生成して回転方向選択部１８３５に出力する（Ｓ１９２６０）。
【０３２３】
図５２を再び参照すれば、回転方向選択部１８３５は回転方向誤差検出部１８３０から入力された論理値の真偽をチェックし（Ｓ１９３００）、真であれば図４９の領域１の場合が生じたと判断し、回転方向訂正部１８１５から入力された前記数式２９に記載されたように訂正された回転差分値Ｑｓを量子化器１８４０に出力する（Ｓ１９４００）。
【０３２４】
しかし、入力された論理値が偽であれば、図４９の領域１の場合が生じていな
0003905834.tif 000085
量子化器１８４０に出力する（Ｓ１９５００）。
【０３２５】
以上、本発明の望ましい第２実施例に係るキー値データ符号化器３００について説明した。
【０３２６】
以下、本発明の望ましい第３実施例に係るキー値データ符号化器３００について説明する。
【０３２７】
本発明の第１実施例及び第２実施例に係る符号化装置は、回転差分値のうち最初の成分値を除いた３成分値を符号化するので、復号化器は量子化誤差によって前述した数式２４を用いて回転差分値の最初の成分値を復元できない場合もある。例えば、復元された回転差分値の最初の成分が虚数となりうる。
【０３２８】
このような、問題が生じることを防止するために、本発明の第３実施例に係るキー値データ符号化器３００の量子化器は復号化器が最小限の映像歪曲で、回転差分値の最初の成分を正の実数に復元するように、量子化された３成分値を適切に調整する。
【０３２９】
本発明の第３実施例に係る符号化装置の構成は量子化器を除けば、前述した第１実施例または第２実施例の符号化装置の構成と同一なので、以下では第３実施例の量子化器２０００についてのみ説明する。
【０３３０】
図５４は、第３実施例に係る符号化装置に含まれる量子化器の構成を示すブロック図である。
【０３３１】
図５４を参照すれば、第３実施例に係る量子化器２０００は入力された回転差分値を量子化する量子化部２０１０、量子化された回転差分データの値を調整する量子化データ調整部２０２０、量子化された回転差分データを逆量子化する逆量子化部２０３０、逆量子化された回転差分データの３成分を用いて最初の成分データを復元することで全体回転差分値を復元する回転差分値復元部２０４０、及び復元された差分値と元の入力された回転差分値間の誤差を測定して量子化された回転差分データを更新する誤差測定部２０５０を含む。
【０３３２】
図５５は、第３実施例に係る量子化器の処理過程を説明するフローチャートである。
【０３３３】
図５５をさらに参照し、第３実施例の量子化過程を説明する。
【０３３４】
0003905834.tif 000086
０は入力された回転差分値を前述した数式２３を用いて量子化し、量子化された
0003905834.tif 000087
【０３３５】
量子化データ調整部２０２０は次の数式３５を用いて量子化された回転差分データの３成分を調整する（Ｓ２０１００）。
【０３３６】
【数３５】
0003905834.tif 000088
【０３３７】
ここで、Ｉ，ｊ及びｋは量子化された回転差分データに合算されて回転差分データを調整する整数の変数であり、ｄはＩ，ｊ及びｋの変化範囲である。調整された量子化された３成分値は逆量子化部２０３０に出力される。
【０３３８】
逆量子化部２０３０は調整された量子化された回転差分データＩｉｊｋを逆量子化して回転差分値復元部２０４０に出力する（Ｓ２０２００）。
【０３３９】
0003905834.tif 000089
は前述した数式２４を用いて最初の成分を復元し、復元された回転差分値を誤差測定部２０５０に出力する（Ｓ２０３００）。
【０３４０】
誤差測定部２０５０は入力された回転差分値の最初の成分の値をさきにチェックし、最初成分の値が実数であれば次の誤差測定段階を行い、復元された回転差分値の最初の成分が虚数であれば、後述するＳ２０６００段階に進め（Ｓ２０４００）。
【０３４１】
誤差測定部２０５０は回転差分値の最初の成分が実数であれば、元の回転差分値と復元された回転差分値間に誤差ｅｉｊｋを測定し（Ｓ２０４５０）、測定された
0003905834.tif 000090
回転差分値と復元された回転差分値間の誤差を測定する方法は図６５を参照して後述する。
【０３４２】
0003905834.tif 000091
して調整された値（ｉ，ｊ，ｋ）が調整範囲（−ｄ〜＋ｄ）を超えたか否かをチェックする（Ｓ２０６００）。もし、超えていなければ、前述した第Ｓ２０１００段階ないし第Ｓ２０５５０段階を反復的に行うが、この際、前述した第Ｓ２０１００段階で量子化データ調整部２０２０は量子化された回転差分データの２番目ないし４番目の成分を順次に１ずつ増加させつつ前述した第Ｓ２０１００段階ないし第Ｓ２０５５０段階を行う。
【０３４３】
例えば、量子化データ調整部２０２０は入力された回転差分データの２番目及び３番目の成分はそのまま保ち、ｋ値を（−ｄ〜＋ｄ）範囲で１つず変更させつつ４番目の成分値に合算し、復元された最初の成分を実数にし、誤差が最小となる４つの成分値を探す。ｋが＋ｄ値に至ると再びｋを−ｄに初期化し、ｊ値を（−ｄ〜＋ｄ）範囲で１だけ変更させた後、これを３番目の成分値に合算し、ｋ値を（−ｄ〜＋ｄ）範囲で１だけ変更させつつ４番目の成分値に合算し、復元された最初の成分を実数にして誤差が最小となる４成分値を探す。ｊも＋ｄ値に至ると再びｊとｋとを−ｄに初期化し、ｉ値を（−ｄ〜＋ｄ）範囲で１だけ変更させた後、これを２番目の成分値に合算し、ｊ値を３番目の成分値に合算し、ｋ値を（−ｄ〜＋ｄ）範囲で１だけ変更させつつ４番目の成分値に合算し、復元された最初の成分を実数にして誤差が最小となる４成分値を探す。この過程をｉ，ｊ，ｋが全て＋ｄに至るまで繰り返し、復元された最初の成分を実数にして誤差が最小となる４成分値を探す。
【０３４４】
誤差測定部２０５０は２番目ないし４番目の成分値を共に変更させつつ更新さ
0003905834.tif 000092
（Ｓ２０７５０）。
【０３４５】
【数３６】
0003905834.tif 000093
【０３４６】
0003905834.tif 000094
部２０５０は訂正された回転差分データを量子化データ調整部２０２０に出力する。
【０３４７】
量子化データ調整部２０２０は回転差分データの各成分に合算する変数値を−ｄに再設定し、誤差測定部２０５０から入力された回転差分データに対して前述した第Ｓ２０１００段階ないし第２０６００段階を繰り返し、誤差測定部２０５０から入力された回転差分データを基準に、既存に貯蔵された最終誤差値より小さな誤差値を示す回転差分データの存否を探す。
【０３４８】
一方、誤差測定部２０５０は第Ｓ２０７００段階で調整誤差値が最終誤差値よ
0003905834.tif 000095
0003905834.tif 000096
２０８００）。
【０３４９】
以上、本発明の望ましい実施例に係る第３実施例のキー値データ符号化器３００について説明した。
【０３５０】
以下、図５６ないし図６３に基づき、本発明の好ましい実施の形態による回転インタポレータを符号化したビットストリームを復号化する復号化装置及び復号化方法について説明する。
【０３５１】
図５６は、本発明の好ましい実施の形態による復号化装置の構成を示すブロック図であり、図５７は、符号化された回転インタポレータを復号化する方法を示すフローチャートである。
【０３５２】
図５６を参照すれば、本発明の復号化装置は、入力されたビットストリームからキーデータを復号化するキーデータ復号化器２１２０、入力されたビットストリームからキー値データを復号化するキー値データ復号化器２１５０、入力されたビットストリームからヘッダ情報を復号化してキーデータ復号化器２１２０及びキー値データ復号化器２１５０に出力するヘッダ復号化器２１１０、及びヘッダ復号化器２１１０より入力された情報に基づき復号化されたキーデータ及びキー値データを合成して復号化された回転インタポレータを出力する回転インタポレータ合成器２１８０を備える。
【０３５３】
図５７を参照すれば、図４に示された符号化装置により符号化された回転インタポレータは、本発明の符号化装置のキーデータ復号化器２１２０、キー値データ復号化器２１５０及びヘッダ復号化器２１１０に各々入力される（Ｓ２１０００）。
【０３５４】
ヘッダ復号化器２１１０は、入力されたビットストリームからヘッダ情報を復号化してキーデータ復号化器２１２０、キー値データ復号化器２１５０及び回転インタポレータ合成器２１８０に各々与える（Ｓ２１１００）。
【０３５５】
キーデータ復号化器２１２０は、入力されたビットストリームからキーデータをエントロピ復号化し、所定の逆ＤＮＤ演算、逆フォルド演算、逆シフト演算などを行い、復号化されたキーデータを生成して回転インタポレータ合成器２１８０に出力する。また、キー値データ復号化器２１５０は、入力されたビットストリームからキー値データをエントロピ復号化し、所定の逆量子化演算及び逆ＤＰＣＭ演算などを行い、復号化されたキー値データを生成して回転インタポレータ合成器２１８０に出力する（Ｓ２１２００）。
【０３５６】
回転インタポレータ合成器２１８０は、ヘッダ復号化器２１１０より入力されたモード設定信号及びキー選択フラグに基づき入力されたキーデータ及びキー値データを合成し、回転インタポレータを合成して出力する（Ｓ２１４００）。
【０３５７】
以下、図５８ないし図６０に基づき、本発明の好ましい実施の形態によるキーデータ復号化器２１２０及び復号化方法について説明する。
【０３５８】
図５８は、本発明の好ましい実施の形態によるキーデータ復号化器２１２０の構成を示すブロック図である。本発明のキーデータ復号化器は、符号化されたビットストリームを受け取り、復号化されたキーデータに再構成する。
【０３５９】
本発明のキーデータ復号化器２１２０は、エントロピ復号化器２２６０、逆ＤＮＤ処理部２２５０、逆フォルド処理部２２４０、逆シフト部２２３０、逆ＤＰＣＭ処理部２２２０、逆量子化器２２１０、線形キー復号化器２２００及び実数逆変換部２２０５を備える。
【０３６０】
図５９は、本発明の好ましい実施の形態によるキーデータ復号化方法を示すフローチャートである。
【０３６１】
まず、入力ビットストリームは、ヘッダ復号化器２１１０及びエントロピ復号化器２２６０に入力される。
【０３６２】
ヘッダ復号化器２１１０は、各復号化段階別に必要な情報を復号化して各段階に与えるが、ヘッダ復号化器２１１０において復号化される情報については各段階ごとに説明する（Ｓ２３０００）。
【０３６３】
ビットストリームを受け取ったエントロピ復号化器２２６０は、ヘッダ復号化器２１１０から復号化すべき差分データの数及び符号化に用いられたビット数、すなわち、復号化すべきビット数を受け取り、ビットストリームをエントロピ復号化する（Ｓ２３１００）。この時、復号化すべき差分データの数は与えられたキーデータの数からＤＰＣＭ演算のイントラキーデータの数だけを引いた数となる。
【０３６４】
エントロピ復号化器２２６０は、ビットストリームを復号化する時、ビットストリームに含まれた所定の情報（この実施の形態では、ｂＳｉｇｎｅｄＡＡＣＦｌａｇ）に基づき符号化された差分データが負数または正数であるかを識別し、負数であれば、ｄｅｃｏｄｅＳｉｇｎｅｄＡＡＣ関数を用いて復号化し、正数であれば、ｄｅｃｏｄｅＵｎｓｉｇｎｅｄＡＡＣ関数を用いて復号化する。このようにして復号化された差分データは、逆ＤＮＤ処理部２２５０に伝わる。
【０３６５】
エントロピ復号化された差分データを受け取った逆ＤＮＤ処理部２２５０は、ヘッダ復号化器２１１０よりＤＮＤ次数及び各ＤＮＤ次数における最大値ｎＫｅｙＭａｘ受け取る。
【０３６６】
もし、ＤＮＤ次数が−１であれば、これは、符号化器がＤＮＤ演算された差分データの代わりにＤＰＣＭ演算されてシフトされた差分データをエントロピ符号化した旨を表わすため、逆シフト演算を行う過程へ直ちに進む。一方、ＤＮＤ次数が０であれば、これは、符号化器がＤＮＤ演算された差分データの代わりにフォルドされた差分データをエントロピ符号化した旨を表わすため、逆フォルド演算を行う過程へ直ちに進む。しかし、ＤＮＤ次数が０より大きければ、逆ＤＮＤ演算を行う（Ｓ２３２００）。
【０３６７】
まず、逆ＤＮＤ処理部２２５０は、シフト−アップ演算の行われた差分データが符号化されたか否かを判断する（Ｓ２３３００）。本発明の好ましい実施の形態においては、ビットストリームに含まれたｎＫｅｙＩｎｖｅｒｔＤｏｗｎ値が０より大きい値であるか否かをチェックすることにより、シフト−アップ演算の行われた差分データが符号化されたか否かを判断する。
【０３６８】
もし、シフト−アップ演算の行われていない差分データが符号化されたならば、逆ＤＮＤ処理部２２５０は、逆ＤＮＤ演算を行う過程へ進む。しかし、シフト−アップ演算の行われた差分データが符号化されたならば、シフト−アップ演算により正数の領域に移動した差分データを再び元の負数領域に変換する（Ｓ２３４００）。本発明の実施の形態は、下記式３７により表わされるシフト−ダウン（以下、″インバートダウン″と同じ意味で用いられる）演算を行い、シフト−アップ演算された差分データを復元する。
【０３６９】
【数３７】
0003905834.tif 000097
【０３７０】
ここで、ｎＫｅｙＩｎｖｅｒｔＤｏｗｎは、シフト−アップ演算における最大値ｎＫｅｙＭａｘと同じ値が用いられる。シフト−ダウン演算によりｎＫｅｙＩｎｖｅｒｔＤｏｗｎを超える差分データは−１以下の負数値に変わる。
【０３７１】
シフト−ダウン演算の行われた差分デーに対して各ＤＮＤ次数におけるｎＫｅｙＭａｘ値に応じて逆ディバイド−ダウンまたは逆ディバイド−アップ演算が選択的に行われる。
【０３７２】
図６０をさらに参照し、この逆ＤＮＤ演算過程を説明すれば、逆ＤＮＤ処理部２２５０は、符号化過程において行われたＤＮＤ演算の次数の回数だけ逆ＤＮＤ演算を行う。すなわち、逆ＤＮＤ処理部２２５０は、逆ＤＮＤ次数の初期値をＤＮＤ次数として設定し、逆ＤＮＤ演算を行う都度１ずつデクリメントし、逆ＤＮＤ次数が１となるまで逆ＤＮＤ演算を行う。まず、逆ＤＮＤ処理部２２５０は、各次数におけるｎＫｅｙＭａｘ値をチェックしてｎＫｅｙＭａｘ値が０以上であるか否かを判断する（Ｓ２３５１０）。
【０３７３】
ｎＫｅｙＭａｘ値が０より小さければ、符号化過程においてディバイド−アップ演算が行われた旨を意味するために、逆ＤＮＤ処理部２２５０は、逆ディバイド−アップ演算を行って差分データの範囲を負数領域に広める（Ｓ２３５３０）。本発明の好ましい実施の形態は、下記式３８のような逆ディバイド−アップ演算を用いた。
【０３７４】
【数３８】
0003905834.tif 000098
【０３７５】
しかしながら、もし、ｎＫｅｙＭａｘが０以上であれば、逆ＤＮＤ処理部２２５０は、逆ＤＮＤ演算の次数が１であるか否かをチェックする。逆ＤＮＤ次数が１でなければ、符号化する時にディバイド−ダウン演算が行われた旨を意味するために、逆ＤＮＤ処理部２２５０は、逆ディバイド−ダウン演算を行って差分データの範囲を正数領域に広める（Ｓ２３５７０）。
【０３７６】
本発明の好ましい実施の形態は、下記式３９のような逆ディバイド−ダウン演算を用いた。
【０３７７】
【数３９】
0003905834.tif 000099
【０３７８】
もし、ｎＫｅｙＭａｘが０以上であり、且つ、逆ＤＮＤ演算の次数が１であれば、逆ＤＮＤ処理部２２５０は、逆ディバイド演算を行うことにより逆ＤＮＤ演算を終える（Ｓ２３５９０）。本発明の好ましい実施の形態は、下記式４０のような逆ディバイド演算を用いた。
【０３７９】
【数４０】
0003905834.tif 000100
【０３８０】
逆ＤＮＤ演算の行われたキーデータの差分データは、逆フォルド処理部２２４０に入力され、逆フォルド処理部２２４０は、逆フォルド演算を行い、正数領域にのみ位置する差分データの範囲を正数及び負数に分離する（Ｓ２３６００）。本発明の好ましい実施の形態は、下記式４１のような逆フォルド演算を用いた。
【０３８１】
【数４１】
0003905834.tif 000101
【０３８２】
逆フォルドされた差分データは、逆シフト部２２３０に出力され、逆シフト部２２３０は、キーヘッダ復号化器２１１０から符号化器に用いられたモードｎＫｅｙＳｈｉｆｔを入力され、下記式４２のように入力されたｎＫｅｙＭａｘ差分データにモードを加える（Ｓ２３７００）。
【０３８３】
【数４２】
0003905834.tif 000102
【０３８４】
逆シフト部２２３０から差分データを入力された逆ＤＰＣＭ処理部２２２０は、キーヘッダ符号化器２１１０からＤＰＣＭ次数を入力され、差分データを量子化されたキーデータに復元する（Ｓ２３８００）。逆シフト部２２３０は、下記式４３を用いてＤＰＣＭ次数だけ逆ＤＰＣＭ演算を行う。
【０３８５】
【数４３】
0003905834.tif 000103
【０３８６】
ここで、ｉは、差分データ及びキーデータのインデックスを、ｖは整数配列を、ｄｅｌｔａ（ｉ）は差分データを各々示す。
【０３８７】
逆ＤＰＣＭ処理されて生成された量子化されたキーデータは、逆量子化器２２１０に入力され、逆量子化器２２１０は、ヘッダ復号化器２１１０から量子化ビットサイズｎＫｅｙＱＢｉｔ及び逆量子化に用いられる最大値及び最小値が量子化過程において実数変換部９０５により符号化されたか否かを入力され、下記式４４を用いて入力された量子化されたキーデータを逆量子化されたキーデータに変換する（Ｓ２３９００）。
【０３８８】
【数４４】
0003905834.tif 000104
【０３８９】
符号化器においてキーデータを量子化する時、量子化に用いられた最大値及び最小値が実数変換部９０５において変換されなかったならば、前記式４４のｆＫｅｙＭｉｎ及びｆＫｅｙＭａｘは０及び１として各々設定される。しかし、量子化に用いられた最大値及び最小値が実数変換部９０５において変換されたならば、逆量子化に用いられる最大値及び最小値は、後述する実数逆変換部２２０５において逆変換されて入力される最小値及び最大値が各々用いられる。
【０３９０】
一方、逆量子化器２２１０から出力される復号化されたキーデータは、線形キー復号化器２２００において復号化された線形キーデータに加えられて復号化されたキーデータを構成する。
【０３９１】
以下、線形キー復号化過程を説明する。
【０３９２】
ヘッダ復号化器２１１０は、ビットストリームからキーヘッダ情報を復号化して線形キーに関する情報があれば、線形キー領域の開始キー及び終了キーを復号化するために必要な情報を実数逆変換部２２０５に出力し、線形キー復号化器２２００に線形キーとして符号化されたキーの数を出力する。
【０３９３】
線形キー復号化に用いられる開始キー及び終了キー情報を入力された実数逆変換部２２０５は、１０進数の体系で表わされた開始キー及び終了キーをさらに２進数の体系に逆変換して線形キー復号化器２２００に出力する。
【０３９４】
復号化すべき２つの実数をｆＫｅｙＭｉｎ及びｆＫｅｙＭａｘとすれば、最初の値ｆＫｅｙＭｉｎを逆変換する過程は、下記の通りである。
【０３９５】
ヘッダ復号化器２１１０は、ｆＫｅｙＭｉｎの桁数をビットストリームから読み込む。もし、桁数が０であれば、ｆＫｅｙＭｉｎの値を０として設定した後、ｆＫｅｙＭａｘの値を復号化するためにｆＫｅｙＭａｘの桁数をビットストリームから読み込む。もし、桁数が８以上であれば、ＩＥＥＥ標準７５４方式に従って符号化されたものであるため、実数を３２ビットだけ読み込んだ後、ｆＫｅｙＭａｘの値を復号化する過程へ進む。
【０３９６】
しかしながら、もし、桁数が１と７との間の値を有すれば、ヘッダ復号化器２１１０は、符号ビットをビットストリームから読み込む。本発明の実施の形態においては、符号ビットが１であれば、ＭｉｎＫｅｙＭａｎｔｉｓｓａＳｉｇｎを−１として、０であれば、ＭｉｎＫｅｙＭａｎｔｉｓｓａＳｉｇｎを１として設定して符号を読み込む。そして、仮数を前記表２の桁数と必要なビット数との関係に基づき必要なビット数を得た後、そのビット数だけビットストリームから読み込み、読み込まれた値をｎＭｉｎＫｅｙＭａｎｔｉｓｓａに貯蔵する。その後、ビットストリームから１ビットのみを読み込んでＭｉｎＫｅｙＥｘｐｏｎｅｎｔＳｉｇｎに貯蔵するが、ＭｉｎＫｅｙＭａｔｉｓｓａＳｉｇｎと同じ方式により貯蔵する。そして、ビットストリームから６ビットのみの指数値を読み込んでｎＭｉｎＫｅｙＥｘｐｏｎｅｎｔに貯蔵する。
【０３９７】
実数逆変換部２２０５は、ヘッダ復号化器２１１０から入力された値を下記式４５に代入してｆＫｅｙＭｉｎを復元する。
【０３９８】
【数４５】
0003905834.tif 000105
【０３９９】
ｆＫｅｙＭａｘを復元する過程は、ｆＫｅｙＭｉｎのそれと同じである。但し、ｆＫｅｙＭａｘの指数をビットストリームから読み込む前に、ｆＫｅｙＭａｘの指数としてｆＫｅｙＭｉｎと同じ指数が用いられたか否かを判読し、同じ値が用いられたならば、ｆＫｅｙＭｉｎの指数を用い、そうでなければ、ｆＫｅｙＭｉｎの指数をビットストリームから読み込む方式と同じく、ｆＫｅｙＭａｘの指数を読み込む。
【０４００】
一方、実数逆変換部２２０５から線形キー領域の開始キー及び終了キーを入力された線形キー復号化器２２００は、下記式４６を用いて線形キー領域を復号化する。
【０４０１】
【数４６】
0003905834.tif 000106
【０４０２】
ここで、ｆＫｅｙＭｉｎ及びｆＫｅｙＭａｘは、線形キー領域の開始キーデータ及び終了キーデータを意味する。
【０４０３】
このようにして復号化された線形キー領域のキーデータは、逆量子化器２２１０から出力されたキーデータに加えられて復号化された最終キーデータとして出力される。
【０４０４】
以下、図６１ないし図６３に基づいて本発明の符号化装置によってキー値データが符号化されたビットストリームを復号化する復号化方法及び装置を説明する。
【０４０５】
図６１は、本発明の望ましい実施例に係る復号化装置の構成を示すブロック図である。
【０４０６】
図６１を参照すれば、本発明の復号化装置は入力されたビットストリームからクォータニオンで表されたキー値データを復号化するのに必要なヘッダ情報を復号化してキー値データ復号化器２１５０に提供するキー値ヘッダ復号化器２１１０、入力されたビットストリームからエントロピ符号化されたキー値データをエントロピ復号化して循環ＤＰＣＭ演算された回転差分データまたは量子化された回転差分データを生成するエントロピ復号化器２４１０、エントロピ復号化器２４１０から入力された循環ＤＰＣＭ演算された回転差分データに逆循環ＤＰＣＭ演算を行って量子化された回転差分データを生成する逆循環ＤＰＣＭ演算部２４２０、量子化された回転差分データを逆量子化して回転差分値を生成する逆量子化器２４３０、及び現在キーフレームの回転差分値を以前キーフレームの回転変換値とクォータニオン乗算して現在キーフレームの回転変換値を生成するクォータニオン乗算器２４４０を含む。
【０４０７】
図６２は、本発明の望ましい実施例に係るキー値データ復号化方法を説明するフローチャートである。
【０４０８】
図６２に基づいて本発明の望ましい実施例に係るキー値データ復号化方法を説明する。
【０４０９】
まず、前述した符号化装置によって符号化されたキー値データのビットストリームはキー値ヘッダ復号化器２１１０及びキー値データ復号化部のエントロピ復号化器２４１０に各々入力される。
【０４１０】
キー値ヘッダ復号化器２１１０は入力されたビットストリームからキー値データの復号化に必要なヘッダ情報を復号化してキー値データ復号化器２１５０に提供する（Ｓ２４１００）
【０４１１】
キー値ヘッダ情報にはＤＰＣＭ次数に応じてクォータニオン形式の量子化された第１及び第２イントラキー値データ、及び残りのキー値データを復号化するための多数のフラグが符号化されている。
【０４１２】
もし、ＤＰＣＭ次数が１であれば（例えば、前述した多数のフラグのうち１つのｎＫＶＤＰＣＭＯｒｄｅｒが０に設定されたならば）、第１量子化されたキー値データだけイントラキー値データとしてキー値ヘッダ情報に含まれる。もし、
0003905834.tif 000107
れば、第１逆量子化されたキー値データは次の数式４８のように計算される。
【０４１３】
【数４８】
0003905834.tif 000108
【０４１４】
数式４８でｘＳｉｇｎは後述するＯｒｉＩＤＰＣＭＫｅｙＶａｌｕｅＨｅａｄｅｒクラスのｎＦｉｒｓｔＸＳｉｇｎが１である時、１値を有し、その他の場合には−１を有する。ｙＳｉｇｎ及びｚＳｉｇｎもｎＦｉｒｓｔＹＳｉｇｎ及びｎＦｉｒｓｔＺＳｉｇｎのような関係を有する。
【０４１５】
最後に、この復元されたクォータニオンは回転インタポレータで使われるために各変位に変換される。キー値データから復元された各変位は４次元ベクトル
0003905834.tif 000109
ニオンは次の数式４９に応じて各変位に変換される。
【０４１６】
【数４９】
0003905834.tif 000110
【０４１７】
一方、ＤＰＣＭ次数が２であれば、例えば、ｎＫＶＤＰＣＭＯｒｄｅｒが１に設定されたならば、第１及び第２量子化されたキー値データがキー値ヘッダ情報に含まれる。この場合、第１キー値データは前述したように復元される。一方、第２キー値データを復元するために、若干異なる過程が適用されるが、これは、第２量子化されたキー値データの３成分だけが、符号化されたビットストリームを通じて伝送され、また、これら成分値はイントラキー値データでなく、第１キ
0003905834.tif 000111
これは次の数式５０によって計算される。
【０４１８】
【数５０】
0003905834.tif 000112
【０４１９】
数式５０で、ｓｅｃｏｎｄＸＳｉｇｎは後述するＯｒｉＩＤＰＣＭＫｅｙＶａｌｕｅＨｅａｄｅｒクラスのｎＳｅｃｏｎｄＸＳｉｇｎが１である時、１値を有し、その他の場合には−１を有する。ＳｅｃｏｎｄＹＳｉｇｎ及びｓｅｃｏｎｄＺＳｉｇｎもｎＳｅｃｏｎｄＹＳｉｇｎ及びｎＳｅｃｏｎｄＺＳｉｇｎのような関係を有する。もし、第２逆量子化されたキー値データのクォータニオン値が
0003905834.tif 000113
【０４２０】
キー値ヘッダ復号化器２１１０は復号化されたキー値データ及びヘッダ情報をキー値復号化器２１５０に出力する。
【０４２１】
一方、キー値データの差分データが符号化されたビットストリームを入力されたエントロピ復号化器２４１０はキー値ヘッダ復号化器２１１０で復号化された復号化情報を用いて入力されたビットストリームをエントロピ復号化する（Ｓ２４１２０ないしＳ２４１２８）。
【０４２２】
図６３は、エントロピ復号化器に入力されるビットストリームの構造を示す図面である。
【０４２３】
図６３においてＮ（ｎＮｕｍｂｅｒＯｆＫｅｙＶａｌｕｅ）を符号化されたキー値データの数とする時、ＤＰＣＭ次数が０である場合にはビットストリームに含まれる各成分の回転差分データの数はＮ−１（０，１，．．．，ｎＮｕｍｂｅｒＯｆＫｅｙＶａｌｕｅ−２）であり、ＤＰＣＭ次数が１である場合にはビットストリームに含まれる各成分の回転差分データの数はＮ−２（０，１，．．．，ｎＮｕｍｂｅｒＯｆＫｅｙＶａｌｕｅ−３）である。
【０４２４】
まず、ビットストリームを入力されたエントロピ復号化器２４１０はキー値ヘッダ復号化器２１１０からｋｅｙｖａｌｕｅ＿ｆｌａｇ（ｘ＿ｋｅｙｖａｌｕｅ＿ｆｌａｇ，ｙ＿ｋｅｙｖａｌｕｅ＿ｆｌａｇ，ｚ＿ｋｅｙｖａｌｕｅ＿ｆｌａｇ）を入力され、それぞれのｋｅｙｖａｌｕｅ＿ｆｌａｇ値が１に設定されているかをチェックする（Ｓ２４１２０）。
【０４２５】
もし、それぞれのｋｅｙｖａｌｕｅ＿ｆｌａｇ値が０に設定されているならば、これはキー値ヘッダ復号化器２１１０で復号化された第１及び第２キー値データを除き、あらゆるキー値データの各成分の量子化されたキー値データまたは差分データが各々後述するＯｒｉＩＫｅｙＶａｌｕｅＣｏｄｉｎｇＢｉｔクラスのｎＡｌｌＫｅｙＶａｌｕｅｓと同一であるということを意味する。したがって、エントロピ復号化器２４１０は各成分のキー値データをキー値ヘッダ復号化器２１１０から入力されたｎＡｌｌＫｅｙＶａｌｕｅｓと同値に復号化し、復号化されたキー値データを逆循環ＤＰＣＭ演算部２４２０に出力する（Ｓ２４１２２）。
【０４２６】
もし、それぞれのｋｅｙｖａｌｕｅ＿ｆｌａｇ値が０でない値（例えば、１）に設定されているならば、エントロピ復号化器２４１０は入力されたキー値デー
0003905834.tif 000114
ら入力されたエントロピ復号化モードをチェックする（Ｓ２４１２４）。
【０４２７】
エントロピ復号化モードが２進復号化モードである場合には次の表１に記載されたｄｅｃｏｄｅＳｉｇｎｅｄＡＡＣ（）関数を用いて適応算術符号化されたビットストリームを復号化して量子化された回転差分データを逆循環ＤＰＣＭ演算部２４２０に出力する（Ｓ２４１２６）。
【０４２８】
【表３】
0003905834.tif 000115
【０４２９】
エントロピ復号化モードが２進復号化モードでない場合には、エントロピ復号化器２４１０はｄｅｃｏｄｅＵｎａｒｙＡＡＣ（）関数を用いて入力されたビットストリームを復号化する（Ｓ２４１２８）。ｄｅｃｏｄｅＵｎａｒｙＡＡＣ（）関数はビットストリームから１が判読されるまで０を判読し、判読された０の数を絶対値に変換した後、１が判読されたビット次の符号ビットを判読して復号化して量子化された回転差分データを逆循環ＤＰＣＭ演算部２４２０に出力する。ｄｅｃｏｄｅＵｎａｒｙＡＡＣ（）関数の一例を下の表４に記載した。
【０４３０】
【表４】
0003905834.tif 000116
【０４３１】
前述したｄｅｃｏｄｅＳｉｇｎｅｄＡＡＣ（）関数及びｄｅｃｏｄｅＵｎａｒｙＡＡＣ（）関数で用いられたｑｆ＿ｄｅｃｏｄｅ（）関数は適応エントロピ符号化されたビットストリームから１ビットを判読する関数であって、国際標準化機構公式文書のＩＳＯ／ＩＥＣ  １４４９６−２：１９９９  Ｃｏｄｉｎｇ  ｏｆ  Ａｕｄｉｏ−Ｖｉｓｕａｌ  Ｏｂｊｅｃｔｓ：Ｖｉｓｕａｌに定義されている。
【０４３２】
エントロピ復号化器２４１０からエントロピ復号化されたキー値データを入力された逆循環ＤＰＣＭ演算部２４２０はキー値ヘッダ復号化器２１１０から入力されたＤＰＣＭ次数をチャックし、ＤＰＣＭ次数が０であればエントロピ復号化器２４１０から入力されたデータは量子化された回転差分データであるために、
0003905834.tif 000117
０）。
【０４３３】
一方、キー値ヘッダ復号化器２１１０から入力されたＤＰＣＭ次数が１であれば、エントロピ復号化器２４１０から入力されたデータは循環ＤＰＣＭ演算が行われた回転差分データであるために、逆循環ＤＰＣＭ演算部２４２０は逆循環ＤＰＣＭ演算を行う（Ｓ２４１３５）。
【０４３４】
ＮＫＶＱＢｉｔｓが逆量子化ビット数とする時、回転差分データを入力された逆循環ＤＰＣＭ演算部２４２０は次の数式５１を用いて入力された回転差分デー
0003905834.tif 000118
（Ｓ２４１３５）。
【０４３５】
【数５１】
0003905834.tif 000119
【０４３６】
その後、逆循環ＤＰＣＭ演算部２４２０は次の数式５２に応じて入力された値
0003905834.tif 000120
【０４３７】
【数５２】
0003905834.tif 000121
【０４３８】
逆循環ＤＰＣＭ演算部２４２０はＢ＋（２ｎＫＶＱＢｉｔｓ−１−１）値が０以上で、量子化範囲の
0003905834.tif 000122
Ｂ＋（２ｎＫＶＱＢｉｔｓ−１−１）値が０より小さいか、量子化範囲の最大値より大きければ、Ａ値
0003905834.tif 000123
【０４３９】
前述した逆循環ＤＰＣＭ演算部をＣ＋＋形式のプログラムコードにて具現した一例を次の表５に記載した。
【０４４０】
【表５】
0003905834.tif 000124
【０４４１】
逆循環ＤＰＣＭ演算が行われて生成された量子化された回転差分データ
0003905834.tif 000125
２４４０に出力する（Ｓ２４１４０）。
【０４４２】
【数５３】
0003905834.tif 000126
【０４４３】
回転差分値を入力されたクォータニオン乗算器２４４０は次の数式５４に応じ
0003905834.tif 000127
１５４）。
【０４４４】
【数５４】
0003905834.tif 000128
【０４４５】
復号化器は回転変換値を復元した後、復元された回転変換値が最後のキー値データに関するものかをチェックし（Ｓ２４１５６）、最後のキー値データでなければ前述した第Ｓ２４１４０段階ないし第２４１５４段階を反復的に行い、最後のキーフレームに関するものであれば復元された回転変換値を出力する（Ｓ２４１５８）。
【０４４６】
一方、ＤＰＣＭ次数が０である場合、逆循環ＤＰＣＭ演算部２４２０は復号化
0003905834.tif 000129
し、逆量子化器は次の数式３１に応じて入力された回転差分データを逆量子化し、
0003905834.tif 000130
ン乗算器２４４０に出力する（Ｓ２４１４０）。
【０４４７】
【数５５】
0003905834.tif 000131
【０４４８】
回転差分値を入力されたクォータニオン乗算器２４４０はＤＰＣＭ次数が０でない場合と同一に回転変換値を復元するが（Ｓ２４１５０ないしＳ２４１５８）、但し、この時には次の数式５６に応じてクォータニオン乗算を行う。
【０４４９】
【数５６】
0003905834.tif 000132
【０４５０】
以上、本発明の望ましい実施例に係る回転インタポレータのキー値データ復号化方法及び復号化装置を説明した。
【０４５１】
以下、復号化されたキーデータ及びキー値データを結合する位置インタポレータ合成器２１８０について説明する。
【０４５２】
図６４は、位置インタポレータ合成器２１８０の処理過程を示すフローチャートである。
【０４５３】
合成器２１８０は、復号化されたキーデータ及びキー値データを入力され、ヘッダ復号化器からキーデータの数、分節点生成モード及びキー選択フラグを入力される（Ｓ２６０００）。
【０４５４】
合成器２１８０は、分節点生成モードをチェックし、分節点生成モードが経路維持モードであれば、復号化されたキーデータ及びキー値データを出力する（Ｓ２６１００）。経路維持モードで分節点が抽出された場合には、キーデータ及びキー値データが互いに対応するため、補間により新しいキー値データを生成する必要がない。しかし、符号化された位置インタポレータがキー維持モードで生成されたならば、キーデータはいずれも符号化されて復号化されたのに対し、キー値データは分節点に当たる場合にのみ符号化されるため、キーデータ及びキー値データが対応しない。従って、後述するように、キー値データを補間しなければならない。
【０４５５】
分節点の抽出に用いられた生成モードがキー維持モードであれば、キーデータと対応するキー値データが存在しているかをチェックするために、キーデータに対応するようにキー選択フラグ配列のインデックスを示すカウンターを設定する（Ｓ２６２００）。
【０４５６】
合成器２１８０は、カウンタが設定されれば、カウンタが指すキーデータに対応するキー値データの存否をチェックし、キー値データが存在すれば、第Ｓ２６５００段階へ進む（Ｓ２６３００）。
【０４５７】
もし、対応するキー値データが存在しなければ、合成器２１８０は、現在のキーデータの以前の分節点であるキーデータに対応するキー値データ及び現在のキーデータ以降の分節点であるキーデータに対応するキー値データに基づき現在のキー値データを線形補間して、キー値データを生成する（Ｓ２６４００）。
【０４５８】
合成器２１８０は、キー値データを線形補間した後、全てのキーデータに対してキー値データの存否及び線形補間が行われたかをチェックし（Ｓ２６５００）、まだチェックしていないキーデータが存在すれば、カウンタを取り替えて第Ｓ２６３００段階から再び行い、全てのキーデータに対してチェックしたならば、合成されたキー及びキーデータを位置インタポレータとして出力する（Ｓ２６６００）。
【０４５９】
以上、回転インタポレータに含まれるキーデータ及び各成分のキー値データを符号化して復号化する方法及び装置について説明した。
【０４６０】
以下では、図６７ないし図７６を参照して本発明の望ましい実施例によってキー及びキー値データを復号化する回転インタポレータ復号化装置を具現するプログラムコードの一例をＳＤＬ言語形式で具現した例を説明する。
【０４６１】
図６７に示されたＣｏｍｐｒｅｓｓｅｄＯｒｉｅｎｔａｔｉｏｎＩｎｔｅｒｐｏｌａｔｏｒクラスは最上位クラスであって回転インタポレータの圧縮ビットストリームを判読するためのクラスである。ＫｅｙＨｅａｄｅｒ，ＫｅｙＳｅｌｅｃｔｉｏｎＦｌａｇ及びＫｅｙクラスは、従来の回転インタポレータのキーフィールドデータに対応するビットストリームからキーデータ情報を判読するためのクラスである。ＯｒｉＩＫｅｙＶａｌｕｅＨｅａｄｅｒ及びＯｒｉＩＤＰＣＭＫｅｙＶａｌｕｅは従来の回転インタポレータのキー値フィールドに対応するキー値情報を判読するためのクラスである。ｑｆ＿ｓｔａｒｔ（）関数はＡＡＣ（Ａｄａｐｔｉｖｅ  Ａｒｉｔｈｍｅｔｉｃ  Ｃｏｄｉｎｇ）を用いてビットストリームの符号化された部分を判読する前に算術復号化器を初期化するのに用いられる。
【０４６２】
図６８に示されたキーヘッダクラスは復号化に必要な情報のキーヘッダを復号化するクラスである。
【０４６３】
キーヘッダの主な情報はキーの数、量子化ビット、イントラキーデータ、ＤＮＤヘッダ及び符号化に必要な実際ビット数である。ｎＫｅｙＱＢｉｔは実数キー値を復元する逆量子化に用いられる量子化ビットである。ｎＮｕｍＫｅｙＣｏｄｉｎｇＢｉｔはキーデータの数を示すｎＮｕｍｂｅｒＯｆＫｅｙのビットサイズを示す。ｎＫｅｙＤｉｇｉｔは元のキーデータの最大重要桁数を示し、復号化された値の切り上げに用いられる。
【０４６４】
キーヘッダに線形キー領域に関する情報が含まれた場合、ｂｌｓＬｉｎｅａｒＫｅｙＳｕｂＲｅｇｉｏｎフラグが１に設定される。この場合、全体キーに含まれる所定の副領域に含まれたキーはｂｌｓＬｉｎｅａｒＬｅｙＳｕｂＲｅｇｉｏｎフラグを追従する復号化されたヘッダ情報を用いて計算されうる。ｂＲａｎｇｅＦｌａｇはキーデータの範囲が０ないし１であるかを示す。もし、範囲が０ないし１でなければ、最小値及び最大値はＫｅｙＭｉｎＭａｘクラスから復号化される。ＫｅｙＭｉｎＭａｘクラスは逆量子化のために最小値及び最大値を再構成する。各値は仮数及び指数に分離されうる。
【０４６５】
ｎＢｉｔＳｉｚｅはｎＱＩｎｔｒａＫｅｙのビットサイズであり、ｎＫｅｙＳｈｉｆｔはｎＫｅｙＭａｘの最初ビットサイズである。ｎＱＩｎｔｒａＫｅｙは第１量子化されたイントラデータの大きさである。これはｎＱＩｎｔｒａＫｅｙの符号を示すｎＱＩｎｔｒａＫｅｙＳｉｇｎと共に結合される。これは残りの量子化されたキーデータを復元するためのベースとして用いられる。インタポレータ圧縮に用いられる全ての符号ビットにおいて、０は正数を、１は負数を各々意味する。ｎＫＤＰＣＭＯｒｄｅｒはＤＰＣＭ次数−１である。次数の範囲は１ないし３である。量子化されたイントラデータの数はＤＰＣＭの次数と同じである。
【０４６６】
ｎＫｅｙＳｈｉｆｔは符号ビットのｎＫｅｙＳｈｉｆｔＳｉｇｎと共にキーデータ復号化器のシフト量を示す整数である。これら２値は、ｂＳｈｉｆｔＦｌａｇが１に設定されれば復号化される。ｎＤＮＤＯｒｄｅｒはＤＮＤ（Ｄｉｖｉｄｅ−ａｎｄ−Ｄｉｖｉｄｅ）の次数である。ＤＮＤはキーデータ復号化器で説明する。もし、ｎＤＮＤＯｒｄｅｒ値が７であれば、ｂＮｏＤＮＤが復号化される。このブール値は逆ＤＮＤが処理されるか否かを示す。ｎＫｅｙＭａｘはそれぞれの連続した逆ＤＮＤ演算の間に使われる最大値及び最小値である。ｎＫｅｙＣｏｄｉｎｇＢｉｔはキーデータの符号化に用いられるビットである。
【０４６７】
ｂＳｉｇｎｅｄＡＡＣＦｌａｇはＡＡＣ復号化のために如何なる復号化方法が用いられるかを示す。もし、値が０であれば、ｕｎｓｉｇｎｅｄＡＡＣ復号化が行われる。それとも、ｓｉｇｎｅｄＡＡＣ復号化が行われる。ｂＫｅｙＩｎｖｅｒｔＤｏｗｎＦｌａｇはｎＫｅｙＩｎｖｅｒｔＤｏｗｎが用いられるか否かを示すブール値である。ｎＫｅｙＩｎｖｅｒｔＤｏｗｎは整数値であって、これを超える全ての量子化されたキーデータを−１以下の負数値に反転させる。ＮＫｅｙＩｎｖｅｒｔＤｏｗｎが−１であれば、シフトダウン演算は行われない。
【０４６８】
図６９は、ＬｉｎｅａｒＫｅｙクラスを示す図面である。ＬｉｎｅａｒＫｅｙクラスで用いられた変数の意味を説明すれば、ｎＮｕｍＬｉｎｅａｒＫｅｙＣｏｄｉｎｇＢｉｔは線形に予測可能なキーの数を符号化するために必要なビット数を示す値である。ｎＮｕｍｂｅｒＯｆＬｉｎｅａｒＫｅｙは線形に予測可能なキーデータの数を示す。
【０４６９】
図７０はＫｅｙＭｉｎＭａｘクラスを示す図面である。
【０４７０】
ＫｅｙＭｉｎＭａｘクラスで用いられた変数の意味を説明すれば、まず、ｂＭｉｎＫｅｙＤｉｇｉｔＳａｍｅは全体キーの最高重要桁数ｎＫｅｙＤｉｇｉｔとキーの最大値の最高重要桁数が同一か否かを示す。ｎＭｉｎＫｅｙＤｉｇｉｔはキーの最大値の最高重要桁数を示す。ＮＭｉｎＫｅｙＭａｎｔｉｓｓａＳｉｇｎはｎＭｉｎＫｅｙＭａｎｔｉｓｓａの符号を示す。ｎＭｉｎＫｅｙＭａｎｔｉｓｓａはキーの最小値の仮数を示す。
【０４７１】
ＮＭｉｎＫｅｙＥｘｐｏｎｅｎｔＳｉｇｎはｎＭｉｎＫｅｙＥｘｐｏｎｅｎｔの符号を示す。ｎＭｉｎＫｅｙｅｘｐｏｎｅｎｔはキーの最小値の指数を示す。
【０４７２】
ｆＫｅｙＭｉｎはキーの最小値を示す。ｎＭａｘＫｅｙＤｉｇｉｔＳａｍｅは全体キーの最高重要桁数ｎＫｅｙＤｉｇｉｔとキーの最大値の最高重要桁数が同一か否かを示す。ｎＭａｘＫｅｙＤｉｇｉｔはキーの最大値の重要桁数を示す。ｎＭａｘＫｅｙＭａｎｔｉｓｓａＳｉｇｎはｎＭａｘＫｅｙＭａｎｔｉｓｓａの符号を示す。ｎＭａｘＫｅｙＭａｎｔｉｓｓａはキーの最大値の仮数を示す。
【０４７３】
ｂＳａｍｅＥｘｐｏｎｅｎｔはキーの最大値のｅｘｐｏｎｅｎｔがｎＭｉｎＫｅｙＥｘｐｏｎｅｎｔと同一か否かを示す。ＮＭａｘＫｅｙＥｘｐｏｎｅｎｔＳｉｇｎはｎＭａｘＫｅｙＥｘｐｏｎｅｎｔの符号を示す。ｎＭａｘＫｅｙＥｘｐｏｎｅｎｔはキーの最大値の指数を示す。ｆＫｅｙＭａｘはキーの最大値を示す。
【０４７４】
図７１はＯｒｉＩＫｅｙＶａｌｕｅＨｅａｄｅｒクラスを示す。このクラスで用いられた変数の意味を説明すれば次の通りである。
【０４７５】
ｂＰｒｅｓｅｒｖｅＫｅｙ：このフラグは現在の復号化モードがキー維持モードか、または経路維持モードかを示す。もし、このフラグが真であれば、現在の復号化モードはキー維持モードである。
【０４７６】
ｎＫＶＱＢｉｔ：この値はキー値データの量子化ビットサイズを示す。
【０４７７】
ｎＫＶＤＰＣＭＯｒｄｅｒ：この値はキー値復号化に用いられる逆ＤＰＣＭ演算の次数を示す。もし、ｎＫＶＤＰＣＭＯｒｄｅｒ＝０であれば、これは１次逆ＤＰＣＭを意味し、ｎＫＶＤＰＣＭＯｒｄｅｒ＝１であれば、２次逆ＤＰＣＭ演算が行われなければならないことを意味する。
【０４７８】
図７２は、ＯｒｉＤＰＣＭＫｅｙＶａｌｕｅＨｅａｄｅｒクラスを示す図面である。このクラスで使われた変数の意味は次の通りである。
【０４７９】
ｆｉｒｓｔＱＫＶ＿Ｓ，ｆｉｒｓｔＱＫＶ＿Ｘ，ｆｉｒｓｔＱＫＶ＿Ｙ，ｆｉｒｓｔＱＫＶ＿Ｚ：クォータニオン形式の量子化されたキー値データの各成分ｓ，ｘ，ｙ，ｚの最初値を示す。
【０４８０】
ＮＦｉｒｓｔＸＳｉｇｎ，ｎＦｉｒｓｔＹＳｉｇｎ，ｎＦｉｒｓｔＺＳｉｇｎ：量子化されたキー値データの３成分ｘ，ｙ，ｚの最初値の符号を示す。
【０４８１】
ｓｅｃｏｎｄＱＫＶ＿Ｘ，ｓｅｃｏｎｄＱＫＶ＿Ｙ，ｓｅｃｏｎｄＱＫＶ＿Ｚ：クォータニオン形式の量子化されたキー値データの３成分ｘ，ｙ，ｚの２番目の値を示す。
【０４８２】
ＮＳｅｃｏｎｄＸＳｉｇｎ，ｎＳｅｃｏｎｄＹＳｉｇｎ，ｎＳｅｃｏｎｄＺＳｉｇｎ：量子化されたキー値データの３成分ｘ，ｙ，ｚの２番目の値の符号を示す。
【０４８３】
ｂＩｓＭｏｒｅＴｗｏＫＶｓ：このフラグは逆循環ＤＰＣＭ演算が行われなければならない場合、復号化されるキー値データが２つ以上であるかを示す。
【０４８４】
ｘ＿ｋｅｙｖａｌｕｅ＿ｆｌａｇ，ｙ＿ｋｅｙｖａｌｕｅ＿ｆｌａｇ，ｚ＿ｋｅｙｖａｌｕｅ＿ｆｌａｇ：これらフラグは３成分ｘ，ｙ，ｚのそれぞれに対して量子化された全ての値が同一か否かを示す。
【０４８５】
図７３は、ＯｒｉＩＫｅｙＶａｌｕｅＣｏｄｉｎｇＢｉｔクラスを示す図面である。このクラスで使われた変数の意味は次の通りである。
【０４８６】
ｎＫＶＣｏｄｉｎｇＢｉｔ：この値はイントラキー値データｆｉｒｓｔＱＫＶ＿Ｓ，ｆｉｒｓｔＱＫＶ＿Ｘ，ｆｉｒｓｔＱＫＶ＿Ｙ，ｆｉｒｓｔＱＫＶ＿ＺａｎｄｓｅｃｏｎｄＱＫＶ＿Ｘ，ｓｅｃｏｎｄＱＫＶ＿Ｙ，ｓｅｃｏｎｄＱＫＶ＿ＺｉｎＯｒｉＩＤＰＣＭＫｅｙＶａｌｕｅＨｅａｄｅｒｃｌａｓｓを除いた全てのクォータニオンキー値データの各成分の量子化に実際に用いられた逆量子化ビット数（または、量子化ビット数）を示す。
【０４８７】
ｎＡｌｌＫｅｙＶａｌｕｅ：この値はそれぞれのｋｅｙｖａｌｕｅ＿ｆｌａｇビットが０に設定された時、全てのキー値データの各成分の量子化された値を示す。
【０４８８】
ｎＳｉｇｎ：この値はｎＡｌｌＫｅｙＶａｌｕｅの符号を示す。
【０４８９】
ｂＩｓＵｎａｒｙＡＡＣ：このフラグは３成分（ｘ，ｙ及びｚ）それぞれの量子化された値の復号化に用いられる適応算術量子化方法を示す。このフラグが真に設定されたならば、ｕｎａｒｙＡＡＣ復号化関数が用いられ、このフラグが偽に設定されたならば、ｂｉｎａｒｙＡＡＣ復号化関数が用いられる。
【０４９０】
図７４は、ＫｅｙＳｅｌｅｃｔｉｏｎＦｌａｇクラスを示す図面である。このクラスに用いられたｋｅｙＦｌａｇはｉ番目のキーデータが符号化されたか否かを示すブール配列であり、ｎＮｕｍＯｆＫｅｙＶａｌｕｅは復号化されるキー値データの数を示す整数値である。
【０４９１】
図７５は、Ｋｅｙクラスを示す図面である。
【０４９２】
Ｋｅｙクラスに用いられた変数の意味を説明すれば、ｎＱＫｅｙはビットストリームから復号化される量子化されたキーデータを貯蔵した配列を示す。ＫｅｙＣｏｎｔｅｘｔはｎＱＫｅｙの大きさを判読するのに用いられるコンテキストを意味する。ＫｅｙＳｉｇｎＣｏｎｔｅｘｔはｎＱＫｅｙの符号を判読するのに用いられるコンテキストを意味する。
【０４９３】
ｄｅｃｏｄｅＵｎｓｉｇｎｅｄＡＡＣは与えられたコンテキストで、適応的算術符号化を符号なき復号化を行う関数である。ｄｅｃｏｄｅＳｉｇｎｅｄＡＡＣは与えられたコンテキストで、適応的算術符号化を符号あり復号化を行う関数である。
【０４９４】
図７６は、ＯｒｉＩＤＰＣＭＫｅｙＶａｌｕｅクラスを示す図面である。このクラスで使われた変数の意味は次の通りである。
【０４９５】
ＤｅｌｔａＫｅｙＶａｌｕｅ：この配列はキー値データの３成分ｘ，ｙ，ｚに関連した量子化されたキー値データをクォータニオン形式で貯蔵する。この配列に貯蔵された量子化されたキー値データはｄｅｃｏｄｅＵｎａｒｙＡＡＣまたはｄｅｃｏｄｅＳｉｇｎｅｄＡＡＣ関数を用いてビットストリームから復号化される。
【０４９６】
ＫＶＸＳｉｇｎＣｏｎｔｅｘｔ，ｋＶＹＳｉｇｎＣｏｎｔｅｘｔ，ｋＶＺＳｉｇｎＣｏｎｔｅｘｔ：このコンテキストはｄｅｃｏｄｅＵｎａｒｙＡＡＣまたはｄｅｃｏｄｅＳｉｇｎｅｄＡＡＣ関数でＤｅｌｔａＫｅｙＶａｌｕｅの３成分の符号を復号化するのに用いられるコンテキストである。
【０４９７】
ＫＶＸＵｎａｒｙＣｏｎｔｅｘｔ，ｋＶＹＵｎａｒｙＣｏｎｔｅｘｔ，ｋＶＺＵｎａｒｙＣｏｎｔｅｘｔ：このコンテキストはｄｅｃｏｄｅＵｎａｒｙＡＡＣ関数でＤｅｌｔａＫｅｙＶａｌｕｅの３成分の値を復号化するのに用いられるコンテキストである。
【０４９８】
ＫＶＸＣｏｎｔｅｘｔ，ｋＶＹＣｏｎｔｅｘｔ，ｋＶＺＣｏｎｔｅｘｔ：このコンテキストはｄｅｃｏｄｅＳｉｇｎｅｄＡＡＣ関数でＤｅｌｔａＫｅｙＶａｌｕｅの３成分の値を復号化するのに用いられるコンテキストである。
【０４９９】
以下、図６ないし図８に示された分節点抽出部４２、４６、及び４８に含まれた誤差計算部４２ｂ、４６ｂ、及び４８ｂで元の回転インタポレータによるアニメーション経路と抽出された分節点によって生成されたアニメーション経路間の誤差測定する方法、及び図５４に示された本発明の第３実施例に係る量子化器２０００に含まれた誤差測定部２０５０で元の回転差分値と量子化された後、逆量子化されて復元された回転差分値間の誤差を測定する方法を説明する。
本発明の誤差測定方法は符号化される前の回転インタポレータと符号化されて復号化された回転インタポレータ間の誤差を測定するのにも用いられる。したがって、以下では、前述した分節点抽出部で分節点が抽出される回転インタポレータの経路及び誤差測定部２０５０で誤差測定に用いられる元の回転差分値を符号化される前の回転インタポレータに対応させ、抽出された分節点によって形成された回転インタポレータの経路及び誤差測定部２０５０で誤差測定に用いられる復元された回転差分値を復号化された回転インタポレータのキー値データに各々対応させて説明する。
【０５００】
回転インタポレータのキー値データを符号化する過程で元の回転インタポレータのキー値データと復元された回転インタポレータのキー値データ間の誤差は量子化過程で生じる。ここで、量子化過程で生じた誤差は元のキー値データによる回転変換と復元されたキー値データによる回転変換間の回転閣議差分として定義される。
【０５０１】
0003905834.tif 000133
【０５０２】
【数５７】
0003905834.tif 000134
【０５０３】
0003905834.tif 000135
場合、次の関係式を誘導しうる。
【０５０４】
【数５８】
0003905834.tif 000136
【０５０５】
ここで、Ａ×Ｂはクォータニオン掛け算を表し、Ａ＊はＡの共役複素数を意味する。この関係式によって次の式を得る。
【０５０６】
【数５９】
0003905834.tif 000137
【０５０７】
【数６０】
0003905834.tif 000138
【０５０８】
0003905834.tif 000139
と数式３６によりθｅｒｒｏｒは次のように求められる。
【０５０９】
【数６１】
0003905834.tif 000140
【０５１０】
ここで、・は内積演算を意味する。数式６１は全体アニメーションキーフレームのうち如何なる特定時間に現れる瞬時量子化誤差を表し、したがって、図５４に示された本発明の第３実施例に係る量子化器２０００に含まれた誤差測定部２０５０では前記数式６１に応じて誤差を計算できる。
【０５１１】
また、これを全体アニメーション区間に対する量子化誤差を求める式で誘導するために特定時間ｔでの瞬時量子化誤差として示せば次の通りである。
【０５１２】
【数６２】
0003905834.tif 000141
【０５１３】
数式６２を回転インタポレータがアニメーションを行う全体キーフレーム区間に対して拡張して全体区間［ｔｍｉｎ，ｔｍａｘ］に対する平均誤差Ｅｍ及び最大誤差Ｅｐを誘導すれば次の通りである。
【０５１４】
0003905834.tif 000142
0003905834.tif 000143
【０５１５】
キーデータ符号化で発生する符号化雑音によって、図６５に示されたような元
0003905834.tif 000144
のアニメーション経路誤差を直接計算できない。したがって、まずキーデータの
0003905834.tif 000145
める。
【０５１６】
【数６３】
0003905834.tif 000146
【０５１７】
数式６３でＳＬＥＲＰ（）関数は球面線形補間を行う関数である。
また、３次元空間上で捩じれたアニメーション経路によって、図６５に示された
0003905834.tif 000147
【０５１８】
【数６４】
0003905834.tif 000148
【０５１９】
0003905834.tif 000149
【０５２０】
【数６５】
0003905834.tif 000150
る。
【０５２１】
【数６６】
0003905834.tif 000151
【０５２２】
但し、任意の時間ｔで瞬間的な誤差は次の数式６７のように計算されるということを留意すべきである。
【０５２３】
【数６７】
0003905834.tif 000152
【０５２４】
0003905834.tif 000153
【０５２５】
しかし、任意の時間ｔでｅ（ｔ）を計算するのは容易ではない。したがって、次のような線形近似式を用いる。
【０５２６】
【数６８】
0003905834.tif 000154
【０５２７】
0003905834.tif 000155
0003905834.tif 000156
【０５２８】
【数６９】
0003905834.tif 000157
【０５２９】
前記数式６９を整理すれば、次の通りである。
【０５３０】
【数７０】
0003905834.tif 000158
【０５３１】
最終的に全体時間間隔［ｔｍｉｎ，ｔｍａｘ］において平均誤差Ｅｍ及び最大誤差Ｅｐは次のように求められる。
【０５３２】
【数７１】
0003905834.tif 000159
【０５３３】
したがって、図６ないし図８に示された分節点抽出部４２、４６、４８に含まれた誤差計算部４２ｂ、４６ｂ、４８ｂでは前記数式７１に応じて誤差は計算でき、またクォータニオン空間で量子化誤差による映像歪曲の程度をさらに客観的に測定できる。
【０５３４】
図６６は、本発明の回転インタポレータ符号化方法及び従来の回転インタポレータ符号化方法に応じる性能を比較する図面である。図６６に示されたように、本発明の回転インタポレータ符号化方法によれば、従来のＭＰＥＧ−４  ＢＩＦＳ
【０５３５】
ＰＭＦＣ方法より符号化ビット数に対して映像歪曲がはるかに減ることが分かる。
【０５３６】
また、本発明はコンピュータにて読出可能な記録媒体にコンピュータが読取可能なコードとして具現しうる。コンピュータが読取可能な記録媒体はコンピュータシステムによって読取られるデータが貯蔵されるあらゆる種類の記録装置を含む。コンピュータにて読取れる記録媒体の例としては、ＲＯＭ、ＲＡＭ、ＣＤ−ＲＯＭ、磁気テープ、フロッピーディスク、光データ貯蔵装置などがあり、またキャリアウェーブ（例えば、インターネットを通じた伝送）の形に具現することも含む。また、コンピュータにて読取れる記録媒体はネットワークで連結したコンピュータシステムに分散され、分散方式でコンピュータにて読取れるコードが貯蔵及び実行されうる。
【０５３７】
以上、本発明についてその望ましい実施例を中心に説明した。本発明が属する技術分野で当業者ならば、本発明が、本発明の本質的な特性から外れない範囲で変形された形に具現可能なのを理解しうる。したがって、開示された実施例を限定的な観点でなく、説明的な観点で考慮せねばならない。本発明の範囲は、前述した説明でなく、特許請求の範囲に示されており、それと同等な範囲内にあるあらゆる違いは本発明に含まれたものと解釈されねばならない。
【０５３８】
【発明の効果】
本発明の回転インタポレータ符号化方法及び装置によれば、高画質のアニメーション映像を保ちつつキーデータ及びキー値データを高効率で符号化及び復号化できる。特に、本発明のデータ経路間の誤差測定方法を用いることによって高画質のアニメーションデータを維持でき、本発明のリサンプリング方法及び分節点抽出方法によって符号化するキーデータ及びキー値データの量を大幅に減らせる。
【０５３９】
また、回転インタポレータのキー値データの回転変換の冗長性を充実に反映できる回転差分値を計算して回転インタポレータのキー値データを符号化することによって、高い圧縮率と高画質のアニメーションを提供できる。
【図面の簡単な説明】
【図１】回転インタポレータノードで表されるアニメーションデータの３次元球の表面上の時間に応じる２次元軌跡を示す図面である。
【図２】線形ＤＰＣＭ及びエントロピ符号化を用いるＭＰＥＧ−４ＰＭＦＣの符号化器及び復号化器の構成を示すブロック図である。
【図３】線形ＤＰＣＭ及びエントロピ符号化を用いるＭＰＥＧ−４ＰＭＦＣの符号化器及び復号化器の構成を示すブロック図である。
【図４】本発明の望ましい実施例に係る回転インタポレータ符号化装置の構成を示すブロック図であり
【図５】本発明の望ましい実施例に係る回転インタポレータ符号化方法を説明するフローチャートである。
【図６】本発明の望ましい実施例に係る分析器の構成を示すブロック図である。
【図７】本発明の望ましい実施例に係る分析器の構成を示すブロック図である。
【図８】本発明の望ましい実施例に係る分析器の構成を示すブロック図である。
【図９】図５に示されたＳ３２０段階の詳細フローチャートである。
【図１０】本発明の望ましい実施例に係るリサンプリング方法を説明するフローチャートである。
【図１１】本発明の望ましい実施例に係る分節点抽出方法を説明するフローチャートである。
【図１２】元のキーデータとリサンプリングされたキーデータを示す図面である。
【図１３】元のアニメーション経路とリサンプリングされたアニメーション経路とを示す図面である。
【図１４】本発明の望ましい実施例に係る分節点抽出方法の一例を示す図面である。
【図１５】本発明の望ましい実施例に係る分節点抽出方法の一例を示す図面である。
【図１６】本発明の望ましい実施例に係る分節点抽出方法の一例を示す図面である。
【図１７】本発明の望ましい実施例に係る分節点抽出方法の一例を示す図面である。
【図１８】本発明の望ましい実施例に係る分節点抽出方法の一例を示す図面である。
【図１９】本発明の望ましい実施例に係る分節点抽出方法の一例を示す図面である。
【図２０】生成モードに応じて分節点抽出部から出力されるキーデータ及びキー値データを説明する図面である。
【図２１】本発明の望ましい実施例に係るキーデータ符号化器の構成を示すブロック図である。
【図２２】図２１に示されたＤＮＤ処理部の構成を示すブロック図である。
【図２３】本発明の望ましい実施例に係るキーデータ符号化方法を説明するフローチャートである。
【図２４】本発明の望ましい実施例に係るキーデータ符号化方法を説明するフローチャートである。
【図２５】本発明の望ましい実施例に係るキーデータ符号化方法を説明するフローチャートである。
【図２６】本発明の望ましい実施例に係るキーデータ符号化方法を説明するフローチャートである。
【図２７】本発明の望ましい実施例に係るキーデータ符号化方法を説明するフローチャートである。
【図２８】本発明の望ましい実施例に係るキーデータ符号化方法を説明するフローチャートである。
【図２９】本発明の望ましい実施例に係るキーデータ符号化方法を説明するフローチャートである。
【図３０】ｅｎｃｏｄｅＳｉｇｎｅｄＡＡＣ関数の一例を示す図面である。
【図３１】本発明の望ましい実施例に係るキーデータを符号化するための演算が行われた後のキーデータを示す図面である。
【図３２】本発明の望ましい実施例に係るキーデータを符号化するための演算が行われた後のキーデータを示す図面である。
【図３３】本発明の望ましい実施例に係るキーデータを符号化するための演算が行われた後のキーデータを示す図面である。
【図３４】本発明の望ましい実施例に係るキーデータを符号化するための演算が行われた後のキーデータを示す図面である。
【図３５】本発明の望ましい実施例に係るキーデータを符号化するための演算が行われた後のキーデータを示す図面である。
【図３６】本発明の望ましい実施例に係るキーデータを符号化するための演算が行われた後のキーデータを示す図面である。
【図３７】本発明の望ましい実施例に係るキーデータを符号化するための演算が行われた後のキーデータを示す図面である。
【図３８】本発明の望ましい実施例に係るキーデータを符号化するための演算が行われた後のキーデータを示す図面である。
【図３９】本発明の望ましい実施例に係るキーデータを符号化するための演算が行われた後のキーデータを示す図面である。
【図４０】本発明の望ましい実施例に係るキーデータを符号化するための演算が行われた後のキーデータを示す図面である。
【図４１】本発明の望ましい第１実施例に係るキー値データ符号化器の構成を示すブロック図である。
【図４２】第１実施例に係るキー値データ符号化方法を説明するフローチャートである。
【図４３】回転差分値の各成分のＰＤＦの典型的な分布を示す図面である。
【図４４】本発明の非線形量子化に用いられるアークタンジェント曲線を示す図面である。
【図４５】本発明の望ましい実施例に係るキー値データ符号化器に含まれた量子化器から出力された回転差分データの一例を示す図面である。
【図４６】図４５に示された差分データに線形ＤＰＣＭ演算が行われた結果を示す図面である。
【図４７】図４６に示された線形ＤＰＣＭ演算された差分データに循環ＤＰＣＭ演算を行った結果を示す図面である。
【図４８】エントロピ符号化に用いられるＵｎａｒｙＡＡＣ（）関数の一例を示す図面である。
【図４９】回転差分値を用いてクォータニオン回転変換値を符号化する時に生じる回転方向誤差を説明する図面である。
【図５０】本発明の望ましい第２実施例に係るキー値データ符号化器の回転ＤＰＣＭ演算部の構成を示すブロック図である。
【図５１】図５０示された回転方向誤差計算器の構成を示すブロック図である。
【図５２】本発明の望ましい第２実施例に係る回転ＤＰＣＭ演算方法を説明するフローチャートである。
【図５３】図５２に示された回転方向誤差計算器、回転方向誤差検出部、及び回転方向訂正部の動作を説明するフローチャートである。
【図５４】本発明の望ましい第３実施例に係るキー値データ符号化器に含まれる量子化器の構成を示すブロック図である。
【図５５】第３実施例に係る量子化器の処理過程を説明するフローチャートである。
【図５６】本発明の望ましい実施例に係る回転インタポレータ復号化装置の構成を示すブロック図である。
【図５７】回転インタポレータ復号化方法を説明するフローチャートである。
【図５８】本発明の望ましい実施例に係るキーデータ復号化器の構成を示すブロック図である。
【図５９】本発明の望ましい実施例に係るキーデータ復号化方法を説明するフローチャートである。
【図６０】本発明の望ましい実施例に係るキーデータ復号化方法を説明するフローチャートである。
【図６１】本発明の望ましい実施例に係る回転インタポレータのキー値データ復号化器の構成を示すブロック図である。
【図６２】望ましい実施例に係るキー値データ復号化方法を説明するフローチャートである。
【図６３】キー値データ復号化器のエントロピ復号化器に入力されるビットストリームの構造を示す図面である。
【図６４】本発明の望ましい実施例に係るキーデータ及びキー値データの回転インタポレータ合成方法を説明するフローチャートである。
【図６５】符号化する回転インタポレータと復号化された回転インタポレータ間の誤差を計算する方法を例示する図面である。
【図６６】本発明の回転インタポレータ符号化方法及び従来の回転インタポレータ符号化方法による性能を比較する図面である。
【図６７】本発明の望ましい実施例に係るキー及びキー値データを復号化する回転インタポレータ復号化装置を具現するプログラムコードの一例をＳＤＬ言語形式で具現した例を示す図面である。
【図６８】本発明の望ましい実施例に係るキー及びキー値データを復号化する回転インタポレータ復号化装置を具現するプログラムコードの一例をＳＤＬ言語形式で具現した例を示す図面である。
【図６９】本発明の望ましい実施例に係るキー及びキー値データを復号化する回転インタポレータ復号化装置を具現するプログラムコードの一例をＳＤＬ言語形式で具現した例を示す図面である。
【図７０】本発明の望ましい実施例に係るキー及びキー値データを復号化する回転インタポレータ復号化装置を具現するプログラムコードの一例をＳＤＬ言語形式で具現した例を示す図面である。
【図７１】本発明の望ましい実施例に係るキー及びキー値データを復号化する回転インタポレータ復号化装置を具現するプログラムコードの一例をＳＤＬ言語形式で具現した例を示す図面である。
【図７２】本発明の望ましい実施例に係るキー及びキー値データを復号化する回転インタポレータ復号化装置を具現するプログラムコードの一例をＳＤＬ言語形式で具現した例を示す図面である。
【図７３】本発明の望ましい実施例に係るキー及びキー値データを復号化する回転インタポレータ復号化装置を具現するプログラムコードの一例をＳＤＬ言語形式で具現した例を示す図面である。
【図７４】本発明の望ましい実施例に係るキー及びキー値データを復号化する回転インタポレータ復号化装置を具現するプログラムコードの一例をＳＤＬ言語形式で具現した例を示す図面である。
【図７５】本発明の望ましい実施例に係るキー及びキー値データを復号化する回転インタポレータ復号化装置を具現するプログラムコードの一例をＳＤＬ言語形式で具現した例を示す図面である。
【図７６】本発明の望ましい実施例に係るキー及びキー値データを復号化する回転インタポレータ復号化装置を具現するプログラムコードの一例をＳＤＬ言語形式で具現した例を示す図面である。
【図１】
0003905834.tif 000160
【図２】
0003905834.tif 000161
【図３】
0003905834.tif 000162
【図４】
0003905834.tif 000163
【図５】
0003905834.tif 000164
【図６】
0003905834.tif 000165
【図７】
0003905834.tif 000166
【図８】
0003905834.tif 000167
【図９】
0003905834.tif 000168
【図１０】
0003905834.tif 000169
【図１１】
0003905834.tif 000170
【図１２】
0003905834.tif 000171
【図１３】
0003905834.tif 000172
【図１４】
0003905834.tif 000173
【図１５】
0003905834.tif 000174
【図１６】
0003905834.tif 000175
【図１７】
0003905834.tif 000176
【図１８】
0003905834.tif 000177
【図１９】
0003905834.tif 000178
【図２０】
0003905834.tif 000179
【図２１】
0003905834.tif 000180
【図２２】
0003905834.tif 000181
【図２３】
0003905834.tif 000182
【図２４】
0003905834.tif 000183
【図２５】
0003905834.tif 000184
【図２６】
0003905834.tif 000185
【図２７】
0003905834.tif 000186
【図２８】
0003905834.tif 000187
【図２９】
0003905834.tif 000188
【図３０】
0003905834.tif 000189
【図３１】
0003905834.tif 000190
【図３２】
0003905834.tif 000191
【図３３】
0003905834.tif 000192
【図３４】
0003905834.tif 000193
【図３５】
0003905834.tif 000194
【図３６】
0003905834.tif 000195
【図３７】
0003905834.tif 000196
【図３８】
0003905834.tif 000197
【図３９】
0003905834.tif 000198
【図４０】
0003905834.tif 000199
【図４１】
0003905834.tif 000200
【図４２】
0003905834.tif 000201
【図４３】
0003905834.tif 000202
【図４４】
0003905834.tif 000203
【図４５】
0003905834.tif 000204
【図４６】
0003905834.tif 000205
【図４７】
0003905834.tif 000206
【図４８】
0003905834.tif 000207
【図４９】
0003905834.tif 000208
【図５０】
0003905834.tif 000209
【図５１】
0003905834.tif 000210
【図５２】
0003905834.tif 000211
【図５３】
0003905834.tif 000212
【図５４】
0003905834.tif 000213
【図５５】
0003905834.tif 000214
【図５６】
0003905834.tif 000215
【図５７】
0003905834.tif 000216
【図５８】
0003905834.tif 000217
【図５９】
0003905834.tif 000218
【図６０】
0003905834.tif 000219
【図６１】
0003905834.tif 000220
【図６２】
0003905834.tif 000221
【図６３】
0003905834.tif 000222
【図６４】
0003905834.tif 000223
【図６５】
0003905834.tif 000224
【図６６】
0003905834.tif 000225
【図６７】
0003905834.tif 000226
【図６８】
0003905834.tif 000227
【図６９】
0003905834.tif 000228
【図７０】
0003905834.tif 000229
【図７１】
0003905834.tif 000230
【図７２】
0003905834.tif 000231
【図７３】
0003905834.tif 000232
【図７４】
0003905834.tif 000233
【図７５】
0003905834.tif 000234
【図７６】
0003905834.tif 000235