(57)【特許請求の範囲】
【請求項１】
キーフレーム基盤のグラフィックアニメーション方式で、キーフレームに表現されるオブジェクトの回転変換を表す回転インタポレータのキー値データを符号化したビットストリームを復号化する復号化方法において、
クォータニオンで表現される各キーフレームのキー値データによって前記オブジェクトに適用される回転変換間の差だけの回転変換を示す回転差分値を量子化してエントロピ符号化した回転差分データを復元する段階と、
前記回転差分データのエントロピ復号化方法を示すエントロピ復号化モードを含むエントロピ復号化情報を復元する段階と、
前記エントロピ復号化モードによってエントロピ復号化された回転差分データに逆循環ＤＰＣＭ演算の遂行の如何を示す逆循環ＤＰＣＭ演算次数を含む逆循環ＤＰＣＭ情報を復元する段階と、
前記逆循環ＤＰＣＭ次数によって逆循環ＤＰＣＭ演算が行われた回転差分データを逆量子化して、回転差分値の復元に用いられる逆量子化ビット数を含む量子化情報を復元する段階と、を含むことを特徴とする復号化方法。
【請求項２】
前記回転差分データは、
クォータニオンで表現された回転差分値の３成分だけが量子化されて符号化されたことを特徴とする請求項１に記載の復号化方法。
【請求項３】
前記エントロピ復号化情報は、
前記キー値データの各成分の回転差分データが同じ値であるか否かを示すキー値フラグと、
前記キー値フラグが、各成分の回転差分データがいずれも同じ値であるということを示す場合に、あらゆるキー値データの回転差分データの各成分に復号化される所定の回転差分データをさらに含むことを特徴とする請求項１に記載の復号化方法。
【請求項４】
前記逆循環ＤＰＣＭ情報は、
前記回転差分データに逆循環ＤＰＣＭ演算を行う場合に用いられるイントラ回転差分データをさらに含むことを特徴とする請求項１に記載の復号化方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はアニメーションキー値データの符号化／復号化方法、及び装置に関する。具体的に、本発明は各キーフレームでオブジェクトに印加される回転変換値間の差を符号化／復号化することによって、クォータニオンで変換されて表されたアニメーション回転インタポレータのキー値データを符号化／復号化するキー値データの符号化／復号化方法、及び装置に関する。
【０００２】
【従来の技術】
国際マルチメディア標準の１つであるＭＰＥＧ−４  ＢＩＦＳは、アニメーションのキー及びキー値データを有するインタポレーションノードを用いるキーフレーム基盤のアニメーションを支援するものである。
前記キーフレーム基盤のアニメーションにおいて、スムーズで自然なアニメーションを生成するためには、大量のキー及びキー値データが必要であり、キーフレーム間に位置するフィールドデータは補間により満たされる。また、ＶＲＭＬ及びＭＰＥＧ−４  ＢＩＦＳで補間とは、補間の種類に応じて線形または球形補間を意味するものである。
【０００３】
キー及び対応するキー値は、時間軸上における元のアニメーション軌跡の近似値である。例えば、回転インタポレータノードで表されたアニメーションデータは３次元球の表面上の時間に応じる２次元軌跡として図１に示す。図１に示すように、従来の技術はキーフレーム間の値を補間するために球面線形インタポレーションを支援するので、アニメーション経路は軌跡の断片の集合であると見られる。
【０００４】
ＢＩＦＳが支援する回転インタポレータノードでは、キーデータは、−∞〜＋∞の範囲で、キーフレームが位置する時間を不連続的な数字で表現する。キー値フィールドは、それぞれのキーが示す時間に合成イメージでのオブジェクトの回転情報を示す。各キーデータが示す時間以外の時間でのオブジェクトの回転情報は最も近い以前時間を示すキーデータ及び最も近い後続時間を示すキーデータに対応するキー値データによって球面で線形補間される。
【０００５】
オブジェクトの回転情報を用いる球面線形補間方法は、回転情報を回転軸及び回転角で表現する。ＶＲＭＬでのようにＭＰＥＧ−４  ＢＩＦＳは回転軸と回転角とで表される回転情報を、回転インタポレータノードを通じて表現する。これらキー値データが球面線形補間を用いてスムーズなアニメーションを生成するとき、キーフレーム間のキー値データの差分値は高い相関関係を有するので、データ間の冗長性を招く。したがって、データの差分値を用いる符号化方法を使用することが効率的である。
【０００６】
ＭＰＥＧ−４  ＢＩＦＳでは、回転インタポレーションノードのキー及びキー値データで表されるフィールドデータを符号化するために２種の方法を用いるが、１つはＰＣＭを用いる方法であり、他の１つはＤＰＣＭとエントロピ符号化とを用いる方法である。
【０００７】
まず、ＰＣＭを用いる方法は、符号化されたキーデータ及びキー値データに対して量子化だけを行う。したがって、符号化されるデータの有用な特性が考慮されていないために、この方法は非効率的である。この方法において、回転インタポレータノードのフィールドデータが入力され、フィールドデータのキー値データがクォータニオン空間の値に変換される。
【０００８】
その後、キー及びキー値データが量子化される。量子化されたフィールドデータは２進数形式のデータとして出力される。元フィールドデータとクォータニオン結果間の視覚的な歪曲を評価するために、出力された２進数形式のデータは逆量子化によってフィールドデータに復元され、各復元されたクォータニオン値は回転軸及び回転角で構成されるキー値データ形式に復元される。復元された回転インタポレータノードのフィールドデータは貯蔵され、スクリーンに出力される。また、このデータを用いると、クォータニオン誤差に係る映像の視覚的な歪曲を測定できる。歪曲は次の式（１）を用いて計算することができる。
【０００９】
【数１】
0004205426.tif 000002
【００１０】
前記式（１）中、Ｎはフィールドデータの数を表し、εｉは符号化されたキー値データＱｉとクォータニオン空間で復元されたキー値データである下記の記号ＤＱｉとの間の差分値を表す。
【００１１】
【数２】
0004205426.tif 000003
【００１２】
次いで、ＤＰＣＭ及びエントロピ符号化を用いた方法は連続されたデータ間の相関関係を考慮するので、ＰＣＭを用いた符号化方法より高い符号化効率を示す。ＤＰＣＭ及びエントロピ符号化を用いる方法では、以前に復元されたキー値データと符号化されるキー値データ間の差分値が量子化前に計算され、差分値が量子化される。これにより、差分値から生じるデータの特性が符号化効率を向上させる。
【００１３】
図２及び図３は線形ＤＰＣＭ及びエントロピ符号化を用いるＭＰＥＧ−４  ＰＭＦＣ（Ｐｒｅｄｉｃｔｉｖｅ  ＭＦＦｉｅｌｄ  Ｃｏｄｉｎｇ）の符号化器／復号化器の構成を示すブロック図である。
【００１４】
図２に示す線形ＤＰＣＭ演算部は、次の式（２）を用いて現在キー値データと、以前に復元されたキー値データ間の差分データである前記の記号ＤＱｉとを計算することができる。
【００１５】
【数３】
0004205426.tif 000004
【００１６】
ここで、Ｑｉは時間ｔでクォータニオン形式で表された元の入力キー値データを表し、前記の記号ＤＱｉは誤差補償回路から入力された時間ｔ−１で復元されたキー値データを表す。
【００１７】
しかし、図２に示す符号化方法では、高い符号化効率が示されない。すなわち、この方法の短所は、クォータニオン空間でオブジェクトの回転を決定するキー値データを分析することによって容易にわかる。次の式（３）でキー値データはクォータニオンで表される。
【００１８】
【数４】
0004205426.tif 000005
【００１９】
例えば、前記式（３）で示されるようにクォータニオン空間では、２つのクォータニオンの全ての成分の符号が反対で、大きさが同一であれば、２つのクォータニオンは同一であると判断する。これは２つのクォータニオンによる３次元空間でオブジェクトの回転変換が同一であり、回転変換に影響を与える要素は回転軸ベクトルでなく、回転軸の方向及び回転角であるということを意味する。
【００２０】
しかし、ＭＰＥＧ−４  ＢＩＦＳで用いられたように、前記式（３）を用いてキー値データが表され、連続されたキー値データのベクトル成分間の減算によって線形で差分が計算されれば、差分値は「０」でないということを意味する。これは線形差分値が回転変換の冗長性をよく反映できないということを意味する。このような理由で、前記式（１）で表される歪曲測定方法では画質を正しく測定することが困難である。
【００２１】
【発明が解決しようとする課題】
本発明が解決しようとする技術的課題は、回転変換の冗長性を充実に反映できる回転差分値を計算して回転インタポレータのキー値データを符号化する符号化方法及び符号化装置を提供することにある。
【００２２】
本発明が解決しようとする他の技術的課題は、本発明の回転差分値を符号化することによって符号化されたキー値データを復号化する復号化方法及び装置を提供することにある。
【００２３】
本発明が解決しようとするさらに他の技術的課題は、本発明のキー値データの符号化方法及び装置に用いられる回転差分データを生成する方法及び装置を提供することにある。
【００２４】
【課題を解決するための手段】
前記技術的な課題を解決するための本発明の復号化方法は、キーフレーム基盤のグラフィックアニメーション方式で、キーフレームに表現されるオブジェクトの回転変換を表す回転インタポレータのキー値データを符号化したビットストリームを復号化する復号化方法において、クォータニオンで表現される各キーフレームのキー値データによって前記オブジェクトに適用される回転変換間の差だけの回転変換を示す回転差分値を量子化してエントロピ符号化した回転差分データを復元する段階と、前記回転差分データのエントロピ復号化方法を示すエントロピ復号化モードを含むエントロピ復号化情報を復元する段階と、前記エントロピ復号化モードによってエントロピ復号化された回転差分データに逆循環ＤＰＣＭ演算の遂行の如何を示す逆循環ＤＰＣＭ演算次数を含む逆循環ＤＰＣＭ情報を復元する段階と、前記逆循環ＤＰＣＭ次数によって逆循環ＤＰＣＭ演算が行われた回転差分データを逆量子化して、回転差分値の復元に用いられる逆量子化ビット数を含む量子化情報を復元する段階と、を含む。
【００２５】
また、本発明の復号化方法により復元される前記回転差分データは、クォータニオンで表現された回転差分値の３成分だけが量子化されて符号化されたことを特徴とする。
【００２６】
また、本発明の復号化方法において、前記エントロピ復号化情報は、前記キー値データの各成分の回転差分データが同じ値であるか否かを示すキー値フラグと、前記キー値フラグが、各成分の回転差分データがいずれも同じ値であるということを示す場合に、あらゆるキー値データの回転差分データの各成分に復号化される所定の回転差分データをさらに含む。
【００２７】
また、本発明の復号化方法において、前記逆循環ＤＰＣＭ情報は、前記回転差分データに逆循環ＤＰＣＭ演算を行う場合に用いられるイントラ回転差分データをさらに含む。
【００３５】
【発明の実施の形態】
以下、添付した図面に基づき、本発明の望ましい実施形態に係る回転インタポレータのキー値データ符号化装置及び方法を説明する。
図４は、本発明の望ましい第１実施形態に係るキー値データ符号化装置の構成を示すブロック図である。
【００３６】
図４を参照すると、第１実施形態のキー値データ符号化装置は、各キーフレームのクォータニオンキー値データによってオブジェクトに適用される回転変換間の差だけの回転変換を示す回転差分値を計算し、前記回転差分値を量子化して回転差分データを出力する回転ＤＰＣＭ演算部３００、量子化された回転差分データに対して選択的に線形ＤＰＣＭ演算及び循環ＤＰＣＭ演算を行う循環ＤＰＣＭ演算部４００、回転ＤＰＣＭまたは循環ＤＰＣＭ演算された回転差分データをエントロピ符号化するエントロピ符号化器４５０、及び符号化された回転インタポレータキー値データの復号化に必要な情報を符号化するキー値ヘッダ符号化器５００を含む。
【００３７】
また、回転ＤＰＣＭ演算部３００は、入力された現在のキーフレームでのオブジェクトの回転変換値と以前に出現したキーフレームでのオブジェクトの回転変換値をクォータニオン乗算し、以前に出現したキーフレームでのオブジェクトの回転変換値と現在のキーフレームでのオブジェクトの回転変換値間の回転差分値を計算する第１クォータニオン乗算器３１０、第１クォータニオン乗算器３１０から入力された回転差分値を非線形量子化して量子化された回転差分データを生成する量子化器３４０、量子化された回転差分データを逆量子化して復元された現在のキーフレームの回転差分値を生成する逆量子化器３５０、及び現在のキーフレームの回転差分値を以前に出現したキーフレームまで累積させて計算された以前に出現したキーフレームの回転変換値とクォータニオン乗算して現在のキーフレームの回転変換値を復元する第２クォータニオン乗算器３７０、次のキーフレームの回転変換値が入力されれば復元された現在のキーフレームの回転変換値を第１クォータニオン乗算器３１０に出力する遅延器３９０を含む。
【００３８】
以下、本発明の回転ＤＰＣＭ演算部で行われる回転ＤＰＣＭ演算の概念に対して説明する。
従来のＭＰＥＧ−４  ＢＩＦＳ  ＰＭＦＣで用いられる線形ＤＰＣＭ方法では、現在のキーフレームのオブジェクトの回転変換を示すクォータニオン回転変換値Ｑ１（Ｑ１＝（ｑ１，０，ｑ１，１，ｑ１，２，ｑ１，３））と次のキーフレームのオブジェクトの回転変換を示すクォータニオン回転変換値Ｑ２（Ｑ２＝（ｑ２，０，ｑ２，１，ｑ２，２，ｑ２，３））間の差分値を、次の式（４）により計算した。
【００３９】
【数５】
0004205426.tif 000006
【００４０】
しかし、このような従来の方法は単純なクォータニオン成分間の差分値だけを計算するので実質的な回転差分値を反映する意味のある値ではない。したがって、このような方法は符号化される連続されたキー値データ間の冗長性を効率よく減少させられない。また、従来の方法は符号化されるビット数を減らすために４つのクォータニオン成分のうち最大値を有する成分を除いた３つの成分だけを符号化する。データ復元の観点で、従来の線形ＤＰＣＭ方法では各キー値データのうち符号化されていない最大のクォータニオン成分が如何なるものであるかを示す２ビット大きさの情報が付加的に符号化されて符号化器から復号化器に伝達されねばならない。
【００４１】
したがって、本発明のキー値データ符号化器は、連続したキー値データ間の冗長性を減少させ、このような従来の技術の問題を解決するために、実質的な回転差分値を考慮する回転ＤＰＣＭ演算方法を提案する。
下記の記号Ｄｘを現在のキーフレームでオブジェクトの基準位置を示す基準ベクトルとし、下記の記号ｎθをキーデータがｋｉ−１のときのキー値データとし、下記の記号Ｄｙｉ−１をオブジェクトの回転変換後に前記の記号Ｄｘの変位ベクトルとするとき、クォータニオン空間で回転変換は次の式（５）で表される。
【００４２】
【数６】
0004205426.tif 000007
【００４３】
【数７】
0004205426.tif 000008
【００４４】
【数８】
0004205426.tif 000009
【００４５】
【数９】
0004205426.tif 000010
【００４６】
前記式（５）中、Ｘ０、Ｙｉ−１、Ｑｉ−１、及びＱ＊ｉ−１は、それぞれ前記の記号Ｄｘ，Ｄｙｉ−１、ｎθ，及びｎθ＊の単位クォータニオンを示す。
なお、Ｑ＊ｉ−１はＱｉ−１のクォータニオン共役複素数を表し、ｘはクォータニオン乗算を表す。
【００４７】
同様にして、キーデータがｋｉのとき、クォータニオン空間で回転変換は次の式（６）で表される。
【００４８】
【数１０】
0004205426.tif 000011
【００４９】
連続された２つのキー値データによって与えられる連続された回転変換間の回転差分値は、前記した式（５）、式（６）及び次の式（７）を用いて計算される。
【００５０】
【数１１】
0004205426.tif 000012
【００５１】
したがって、回転差分値は次の式（８）で定義される。
【００５２】
【数１２】
0004205426.tif 000013
【００５３】
一方、本発明の望ましい第１実施形態に係るキー値データ符号化装置は、量子化誤差が次の回転差分値まで伝播されることを防止するために、次のキーフレームの回転変換値と復元された以前に出現したキーフレームの回転変換値である前記記号ＤＱ＊ｉ−１とを用いて回転差分値を、式（８）から次の式（９）のように変形して定義する。
【００５４】
【数１３】
0004205426.tif 000014
【００５５】
以下、本発明の望ましい第１実施形態に係るキー値データ符号化方法を説明するフローチャートである図５を参照しながら、キー値データ符号化方法について説明する。
本発明に係るキー値データ符号化器は、キー値データの符号化のためにＤＰＣＭ演算次数、エントロピ符号化モード、及びキー値データを入力される（ステップＳ３００）。
【００５６】
その後、クォータニオンで表されたキー値データＱｉを入力された第１クォータニオン乗算器３１０は入力されたキー値データＱｉが最初のキー値データＱ０か否かをチェックし（ステップＳ３０５）、最初のキー値データであればクォータニオン乗算を行う累積されたクォータニオン変換値がないので、入力されたキー値データを量子化器３４０に出力し、最初のキー値データでなければ復元された以前に出現したキーフレームのクォータニオン変換値前記の記号ＤＱｉ−１と現在のキーフレームの入力キー値データのクォータニオン変換値Ｑｉとをクォータニオン乗算（下記式（ＱＨ）し、クォータニオン空間で以前に出現したキーフレームと現在のキーフレーム間のキー値データの差分値のクォータニオン回転差分値Ｑｉを計算する（ステップＳ３１０）。
【００５７】
【数１４】
0004205426.tif 000015
【００５８】
量子化器３４０は、第１クォータニオン乗算器３１０から最初のキー値データＱ０またはクォータニオン回転差分値であるＱｉを入力して所定の量子化ビット数で量子化する（ステップＳ３３０）。
【００５９】
全ての回転クォータニオン差分値は単位クォータニオンで表されるので、回転差分値を示すクォータニオンのｎｏｒｍは常に１であり、よって、符号化されていない１成分データは残りの３成分データによって復号化され得る。本発明の望ましい実施形態に係る回転インタポレータキー値データ符号化装置は符号化するデータの量を減らすために、回転差分値のうち最初の成分を除いた３成分だけを符号化する。したがって、回転ＤＰＣＭ演算部に含まれた量子化器３４０は符号化される回転差分値を構成する４つの成分のうち最初の成分を除いた３つの成分だけを量子化する。
【００６０】
但し、本発明の量子化器３４０は一般の線形量子化の代りに非線形量子化を行う。その理由について回転差分値の各成分のＰＤＦ（Ｐｒｏｂａｂｉｌｉｔｙ  Ｄｉｓｔｒｉｂｕｔｉｏｎ  Ｆｕｎｃｔｉｏｎ）の典型的な分布を示す図６（Ａ）に基づいて説明する。
【００６１】
図６（Ａ）に示すように、一般に回転差分値の各成分値は「０」を中心に分布する。このことは、回転差分値が回転情報に存在する冗長性を効率よく減らせることを意味し、これをエネルギーの集中と呼ばれる。したがって、回転差分値が低い範囲の値をより充実に反映して回転差分値を量子化するために、回転差分値の低い範囲により精密な量子化を行う必要がある。このために本発明の量子化器３４０は非線形量子化を行う。ここで、本発明の量子化器３４０は回転差分値に対して非線形スケールファクターを割り当てるためにアークタンジェント曲線を用いる。
【００６２】
図６（Ｂ）は、本発明の量子化に用いられるアーク−タンジェント曲線を示す図面である。
図６（Ｂ）に示すように、アークタンジェント曲線は高い範囲に位置した入力値に対して適切な解像度を提供しつつも、低い範囲に位置した入力値に対してより精密な解像度を提供する。本発明の量子化器３４０は非線形スケール関数を用いて次の式（１０）のように回転差分値を量子化する（ステップＳ３３０）。
【００６３】
【数１５】
0004205426.tif 000016
【００６４】
前記式（１０）中、ｑｉは時間ｔｉで量子化器３４０に入力された回転差分値の各成分を表し、ｑｉ’はｑｉのスケールされた値を表し、ｎＱＢｉｔｓは量子化に用いられる量子化ビット数を表し、ｆｌｏｏｒ（ｘ）は入力されたｘをｘ以下の最大整数に変換する関数を表す。
【００６５】
量子化器３４０は入力された回転差分値に対して量子化を行った後、量子化された回転差分データが符号化する最後のキー値データに対する回転差分データであるか否かをチェックし、最後のキー値データに対する回転差分データであれば、計算された回転差分データを循環ＤＰＣＭ演算部４００に出力し、最後のキー値データに対する回転差分データでなければ、量子化された回転差分データを逆量子化器３５０に出力する（ステップＳ３４０）。
【００６６】
量子化された回転差分データを入力された逆量子化器３５０は回転差分データを逆量子化して復元された回転差分値を出力する（ステップＳ３５０）。
ところが、前述したように、本発明のキー値データ符号化装置は符号化されるビット数を減らすために、クォータニオンで表される回転差分値を構成する４つの成分値のうち最初の成分を除いた３成分を量子化して符号化する。復号化装置の逆量子化器１１３０（図１８参照）及び符号化装置の逆量子化器３５０は量子化された回転差分データの３成分から量子化されていない最初の成分を復元せねばならない。全ての回転クォータニオン差分値は単位クォータニオンで表されるので、回転差分値を示すクォータニオンのｎｏｒｍは常に１であり、よって、量子化されていない最初の成分データは次の式（１１）によって復元され得る。
【００６７】
【数１６】
0004205426.tif 000017
【００６８】
前記式（１１）中、下記の記号Ｄｑ１、Ｄｑ２、及びＤｑ３は各々復元された回転差分値の成分を、Ｄｑ０は復元された３成分を用いて復元された最初の成分を示す。
【００６９】
【数１７】
0004205426.tif 000018
【００７０】
このとき、前記式（１１）を用いて回転差分値の最初の成分を復元するためには、最初の成分が常に正数であることが要求される。このことは、３次元空間において、オブジェクトの回転変換にクォータニオンを適用する場合に出現する次の式（１２）で表されるクォータニオンの性質を用いれば充足され得る。
【００７１】
【数１８】
0004205426.tif 000019
【００７２】
前記式（１２）は、３次元空間でオブジェクトに回転変換が適用されるときに、回転変換値Ｑ及び−Ｑが同一の物理的意味を有することを示す。したがって、符号化装置で回転差分値の最初の成分が負数であれば、回転差分値のあらゆる成分に負の符号を付することによって（−１をかけることによって）容易に正数に変換し得る。
【００７３】
0004205426.tif 000020
【００７４】
したがって、復号化装置は決定された下記の記号Ｄｑ０が復号化された他の３成分値に及ぼす影響を最小化しつつ、このような下記の記号Ｄｑ０を決定する方法が必要であり、このような決定方法は符号化装置の逆量子化器３５０にも適用される。例えば、量子化最小値または量子化最小値の整数倍値が前記の記号Ｄｑ０と決定され得る。このような下記の記号Ｄｑ０を決定するために次の式（１３）が用いられる。
【００７５】
【数１９】
0004205426.tif 000021
【００７６】
【数２０】
0004205426.tif 000022
【００７７】
前記式（１３）中、αは任意の定数を示し、ｍは量子化ビット数を示す。
【００７８】
このような方法は、従来のＭＰＥＧ−４  ＢＩＦＳ  ＰＭＦＣ方式で復号化のために復号化器に伝えられた、それぞれのキー値データに対する２ビットの付加的な情報が不要なので、Ｎ個のキー値データを符号化するとき、従来の方法に比べて２Ｎビットだけ符号化されるビット数を減らす効果がある。
【００７９】
0004205426.tif 000023
【００８０】
【数２１】
0004205426.tif 000024
【００８１】
0004205426.tif 000025
【００８２】
【数２２】
0004205426.tif 000026
【００８３】
【数２３】
0004205426.tif 000027
【００８４】
【数２４】
0004205426.tif 000028
【００８５】
第２クォータニオン乗算器３７０は、復元された現在のキーフレームの回転変換値である前記の記号（ＤＱｉ−１）を遅延器３９０に出力し、遅延器３９０は復元された現在のキーフレームの回転変換値である前記の記号ＤＱｉを次のキーフレームの回転変換値が入力されるまで記憶させた後（前記の記号ＤＱｉ−１＝ＤＱｉ）、第１クォータニオン乗算器３１０に出力する。
【００８６】
第１クォータニオン乗算器３１０は、次に符号化されるキーフレームの回転変換値Ｑｉが入力されれば、遅延器３９０から現在のキーフレームの以前に出現したキーフレームの復元された回転変換値である前記の記号ＤＱｉ−１を入力されてクォータニオン乗算を行って（ＤＱｉ＝ＱｉＨＤＱ＊ｉ−１）、現在のキーフレームの回転変換値と以前に出現したキーフレームの復元された回転変換値間の回転差分値Ｑｉを生成する（ステップＳ３１０）。
【００８７】
生成された回転差分値は量子化器３４０に出力されて前記したように量子化され（ステップＳ３３０）、量子化器３４０は入力された回転差分値が最後のキー値データに関するものであれば、回転差分値を量子化して生成された回転差分データを循環ＤＰＣＭ演算部（４００）に出力する（ステップＳ３４０）。
【００８８】
循環ＤＰＣＭ演算部４００は、入力された値のうち、ＤＰＣＭの次数をチェックし、ＤＰＣＭ次数が０であれば回転差分データに線形、及び循環ＤＰＣＭ演算を行わず、エントロピ符号化器４５０に出力する（ステップＳ４００）。ＤＰＣＭの次数が「０」でなければ、量子化された回転差分データに線形ＤＰＣＭ演算、及び循環ＤＰＣＭ演算を行う（ステップＳ４１０）。
【００８９】
図７（Ａ）は量子化器３４０から出力された差分データの一例を示し、図７（Ｂ）は量子化器３４０から出力された差分データに線形ＤＰＣＭ演算が行われた結果を示す。
【００９０】
図７（Ｂ）に示すように、線形ＤＰＣＭ演算が行われたとき、符号化される差分データの範囲は最初量子化された値の範囲の２倍まで増加し得る。したがって、循環ＤＰＣＭ演算の目的は、差分データの範囲を入力された量子化されたデータの範囲に保ちつつＤＰＣＭ演算を行うことにある。
【００９１】
循環ＤＰＣＭ演算は量子化範囲の最大値と量子化範囲の最小値とが相互連結されていると仮定する。したがって、もし、２つの連続された量子化されたデータ間の線形ＤＰＣＭ結果である差分データが量子化範囲の最大値の半分を超えれば、差分データ値から最大値を減算することで、差分データ値をより小さな値で表現し得る。
【００９２】
また、もし、２つの連続された量子化されたデータ間の線形ＤＰＣＭ結果である差分データが量子化範囲の最小値の半分より小さければ、差分データ値に最大値を加算することで、差分データ値をより小さな範囲の値に表現し得る。
【００９３】
時間ｔｉ及びｔｉ−１で量子化された回転差分データが、各々下記の記号Ｄ’Ｑｉ及びＤ’Ｑｉ−１とするとき、２つの連続された回転差分データの線形ＤＰＣＭ演算は次の式（１４）を用いて行われる。
【００９４】
【数２５】
0004205426.tif 000029
【００９５】
また、循環ＤＰＣＭ演算は、前記式（１４）に従って計算して得られた差分データに対して次の式（１５）を用いて行われる。
【００９６】
【数２６】
0004205426.tif 000030
【００９７】
前記式（１５）中、ｎＱＢｉｔｓは量子化ビット数を表す。図７（Ｂ）に示すようなＤＰＣＭ演算が行われた差分データに対して、循環ＤＰＣＭ演算を行った結果を図５Ｃに示す。図８に示すように循環ＤＰＣＭ演算された差分データは、単純に線形ＤＰＣＭ演算された差分データよりもデータの範囲が大きく減少していることがわかる。
【００９８】
ＤＰＣＭの次数に応じて回転差分データまたは循環ＤＰＣＭ演算された回転差分データを循環ＤＰＣＭ演算部４００から入力されたエントロピ符号化器４５０はビットの冗長性を除去することによってデータを符号化する。
【００９９】
ここで、再び図５に示すように、エントロピ符号化器４５０はまずエントロピ符号化モードをチャックする（ステップＳ４５０）。
【０１００】
さらに、エントロピ符号化モードがＢｉｎａｒｙエントロピ符号化モードである場合には。ＳｉｇｎｅｄＡＡＣ（）関数を用いて差分データを符号化し（ステップＳ４６０）、エントロピ符号化モードがＵｎａｒｙエントロピ符号化モードである場合にはＵｎａｒｙＡＡＣ（）関数を用いて差分データをエントロピ符号化する（ステップＳ４７０）。
【０１０１】
さらに、ＳｉｇｎｅｄＡＡＣ（）関数は、入力されたデータの符号及び大きさを各々ビットプレイン単位で符号化する、適応２進算術符号化器を用いて入力された差分データを符号化する。
【０１０２】
図９はＳｉｇｎｅｄＡＡＣ（）関数の一例を示す図面である。
図９に示すように、入力値が７４であり、この値に対する符号化ビット数が８であれば、この値の符号は０であり、この値の２進数は１００１０１０となる。符号及び全てのビットプレインは次のような過程を通じて符号化される。
【０１０３】
第１段階：２進数をＭＳＢからＬＳＢにビットプレイン単位で符号化する。
第２段階：符号化中に現在符号化されるビットが０であるかをチェックする。
第３段階：もし、最初に０でない符号化ビットが現れれば、２進数の現在の符号化ビットを符号化した後に符号を符号化する。
第４段階：２進数の残余ビットを符号化する。
【０１０４】
一方、Ｕｎａｒｙ  ＡＡＣ関数は符号化する値を一連の０に変換した後、前記０が終了されたことを示す１及びこの値の符号を示す１ビットを用いてシンボルを符号化する。この際、一連の０は値の大きさを示す。
【０１０５】
図１０を参照してＵｎａｒｙ  ＡＡＣ関数について説明する。例えば、符号化する値が２５６であれば、Ｕｎａｒｙ  ＡＡＣ関数は、図１０に示すように、値を２５６個の「０」と、「０」が終了されたことを示す１及び値の符号（正数）を示す「０」を符号化する。Ｕｎａｒｙ  ＡＡＣ関数によって符号化するとき、シンボルのビット冗長性が増加するので符号化効率が高まる。
【０１０６】
以上、本発明で望ましい第１実施形態の回転インタポレータのキー値データ符号化装置について説明した。
以下では、本発明の望ましい第２実施形態に係るキー値データ符号化装置を説明する。本発明の第２実施形態のキー値データ符号化装置は第１実施形態のキー値データ符号化装置において量子化による回転方向誤差を訂正する構成をさらに含む。
【０１０７】
図１１は、回転差分値を用いてクォータニオン回転変換値を符号化する際に生じる回転方向誤差を説明するための図面である。この回転方向誤差は、本発明に含まれる符号化装置で行われるクォータニオン符号化方法が損失符号化方法であるために発生する。
【０１０８】
図１１において、Ｑｉがｉ番目のキーフレームでオブジェクトに適用される現在回転変換値を示し、Ｑｉ−１が以前に出現したキーフレームでオブジェクトに適用された回転変換値を示し、前記の記号ＤＱｉ及びＤＱｉ−１は復号化器でＱｉ及びＱｉ−１から復元された値とするとき、前記４つの回転変換値によって回転されたオブジェクトの位置は図１１に示すように４つの領域で表現され得る。
【０１０９】
すなわち、オブジェクトが最短経路を通じてＱｉ−１からＱｉに回転し、Ｑｉ−１及びＱｉによって回転されたオブジェクトが領域３及び領域１に位置すれば、オブジェクトはＱｉ−１からＱｉに反時計方向に回転する。また、オブジェクトが最短経路を通じてＱｉ−１からＱｉに回転し、Ｑｉ−１及びＱｉによって回転されたオブジェクトが領域２及び領域４に位置すれば、オブジェクトはＱｉ−１からＱｉに時計方向に回転する。
【０１１０】
一方、オブジェクトが符号化されてから復号化された回転情報に応じて回転すれば、復号化器はＱｉ−１及びＱｉに各々対応する前記の記号ＤＱｉ−１及びＤＱｉに応じてオブジェクトを回転させる。したがって、ここで再び図１１に示すように、前記の記号ＤＱｉの位置がＤＱｉ−１に比べて領域２及び領域３にあるならば、オブジェクトは反時計方向に回転し、前記の記号ＤＱｉの位置がＤＱｉ−１に比べて領域１及び領域４にあるならば、オブジェクトは時計方向に回転する。このような事実から、元の符号化された回転変換値でオブジェクトを回転させる場合と、復号化された回転変換値でオブジェクトを回転させる場合とに、領域１及び領域２でオブジェクトが相互反対方向に回転できることがわかる。
【０１１１】
これは、クォータニオン回転変換値を符号化するとき、損失符号化が行われるので、Ｑｉと前記の記号ＤＱｉとが同一ではないからである。領域１及び領域２のような状況は損失符号化で不可避に起こるので、これを解決するために元の回転方向と反対方向への誤った回転を最小化したり、誤った回転方向を元の回転方向と同一にしたりする必要がある。本発明では、後者の方法を提案する。
【０１１２】
再び図１１を参照して、本発明で回転方向誤差を訂正する基本概念を簡単に説明する。領域１及び領域２のような回転方向誤差が検出されれば、符号化されるクォータニオン回転差分値は誤った回転方向が元の方向と同一になるべく強制的に制御される。この場合に、回転方向の不一致が領域２でも生じるが、領域２では領域１とは違って元のクォータニオン値と復元されたクォータニオン値間の差が相対的に小さい。したがって、本発明の第２実施形態に係る回転方向訂正は領域１に対してだけ行われる。
【０１１３】
以下、図１２から図１４に基づいて、回転方向誤差訂正機能を行う本発明に係る第２実施形態のキー値データ符号化装置について説明する。本発明に係る第２実施形態のキー値データ符号化装置は、本発明に係る前記第１実施形態に含まれるキー値データ符号化装置及び回転ＤＰＣＭ演算部の構成のみが異なるものであり、残りの部分の構成は第１実施形態の場合と同一である。したがって、第２実施形態の回転ＤＰＣＭ演算部の構成だけを説明する。
【０１１４】
図１２は本発明の望ましい第２実施形態に係る回転ＤＰＣＭ演算部８００の構成を示すブロック図であり、図１３は図１２に示す回転方向誤差計算器８２０の構成を示すブロック図である。
図１２に示すように、第２実施形態に係る回転ＤＰＣＭ演算部８００は前述した第１実施形態の回転ＤＰＣＭ演算部の構成に、現在のキーフレームでのオブジェクトの回転変換値と以前に出現したキーフレームの復元された回転変換値を入力されて回転方向誤差を計算する回転方向誤差計算器８２０、回転方向誤差計算器８２０から入力された回転誤差値に応じて復号化時に回転方向が変更される程の誤差の発生有無を検出する回転方向誤差検出部８３０、以前に出現したキーフレームの復号化された回転変換値によって回転された位置から元の回転方向と同じ方向に、１８０°回転に近い位置にオブジェクトが回転すべく第１クォータニオン乗算器８１０から入力された回転差分値を訂正して出力する回転方向訂正部８１５、及び回転方向誤差検出部８３０から入力された値に応じて回転方向訂正部８１５から入力された回転方向が訂正された回転差分値と第１クォータニオン乗算器８１０から入力された回転差分値のうち何れか１つを選択して量子化器８４０に出力する回転方向選択部８３５をさらに含む。
【０１１５】
また、図１３に示すように、図１２に示す回転方向誤差計算器８２０は入力された回転変換値を次のフレームの回転変換値が入力されるまで貯蔵する遅延器８２２、入力回転変換値及び遅延器８２２から出力される以前に出現したキーフレームの回転変換値を入力されてクォータニオン乗算して量回転変換値間の回転差分値を計算する第３クォータニオン乗算器８２４、遅延器８２２から出力される以前に出現したキーフレームの回転変換値及び第２クォータニオン乗算器８７０から入力される以前に出現したキーフレームの復元された回転変換値間の回転差分値を計算する第４クォータニオン乗算器、及び入力回転変換値及び第２クォータニオン乗算器８７０から入力される以前に出現したキーフレームの復元された回転変換値間の回転差分値を計算する第５クォータニオン乗算器８２８を含む。
【０１１６】
以下、図１４をさらに参照して本発明の望ましい第２実施形態に係る回転ＤＰＣＭ演算方法を説明する。
現在符号化される回転インタポレータのキー値データＱｉは回転ＤＰＣＭ演算部８００の第１クォータニオン乗算器８１０及び回転方向誤差計算器８２０に入力される（ステップＳ９００）。
【０１１７】
0004205426.tif 000031
【０１１８】
回転方向訂正部８１５は入力された回転差分値を次の式（１６）を用いて訂正し、このように訂正された回転差分値Ｑｓを回転方向選択部８３５に出力し、回転方向誤差計算器８２０は入力された現在のキーフレームの回転変換値Ｑｉと遅延器８９０を通じて第２クォータニオン乗算器８７０から入力された以前に出現したキーフレームの復元された回転変換値である前記の記号ＤＱｉ−１を入力して後述する回転変換値ＱＡ， ＱＢ及びＱＣを計算し、回転方向誤差検出部８３０は回転方向誤差計算器８２０から入力された回転差分値を用いて回転方向誤差の発生有無を検出して回転方向選択部８３５に出力する（ステップＳ９２０）。
【０１１９】
【数２７】
0004205426.tif 000032
【０１２０】
前記式（１６）中、δＴは「０」に近い小さな定数値を表し、（ｑＲ，０、qＲ，１、ｑＲ，２、ｑＲ，３）Ｔは第１クォータニオン乗算器８１０から出力された回転差分値Ｑｉを示す。回転方向誤差計算器８２０、回転方向誤差検出部８３０、及び回転方向訂正部８１５については図９Ｂに基づいて後述する。
【０１２１】
回転方向選択部８３５は、後述する回転方向誤差検出部８３０から入力される論理値に応じて復号化されたとき、元の回転方向とは反対にオブジェクトの回転が起こる程の回転方向誤差が生じたかを決定し、回転方向誤差が生じていないならば第１クォータニオン乗算器８１０から入力される回転差分値を量子化器８４０に出力し、回転方向誤差が生じたならば回転方向訂正部８１５から入力される訂正された回転差分値を量子化器８４０に出力する（ステップＳ９３０）。
【０１２２】
量子化器８４０は回転方向選択部８３５から入力された元回転差分データＱｉまたは訂正された回転差分データＱｓを前述した第１実施形態の量子化方法と同じ方法で量子化する（ステップＳ９４０，ステップＳ９５０）。
【０１２３】
量子化器８４０は量子化された回転差分データが最後のキー値データに関するものであるかをチェックし（ステップＳ９６０）、最後のキー値データに関するものならば、量子化された回転差分データを第１実施形態のように循環ＤＰＣＭ演算部に出力し（ステップＳ９７０）、最後のキー値データがなければ逆量子化器８５０に出力する。
【０１２４】
逆量子化器８５０は入力された量子化された回転差分データ（後記する記号（ＤＱｉ’）を第１実施形態と同じ方法で逆量子化して復元された回転差分値ＤＤＱｉを第２クォータニオン乗算器８７０に出力する（ステップＳ９８０）。
【０１２５】
第２クォータニオン乗算器８７０は復元された回転差分値である前記の記号ＤＤＱｉと、以前に出現したキーフレームの回転変換値である前記の記号ＤＱｉ−１とを乗算して復元された現在のキーフレームの回転変換値ＤＱｉを生成する。第２クォータニオン乗算器８７０は、復元された現在のキーフレームの回転変換値を、遅延器８９０を通じて第１乗算器及び回転方向誤差計算器８２０に出力する（ステップＳ９９０）。
【０１２６】
以下、再び図１４を参照しながら、回転方向誤差計算器８２０、回転方向誤差検出部８３０、及び回転方向訂正部８１５の動作について説明する。
回転方向誤差計算器８２０は、前述した図１１の領域２から領域４に該当する回転差分値を各々計算する。
回転方向誤差計算器８２０は現在符号化されるキーフレームのキー値データの回転変換値を入力され、遅延器８２２を通じて現在のキーフレーム以前に出現したキーフレームの復元された回転変換値を入力され、回転方向誤差を計算する（ステップＳ９２２）。
【０１２７】
現在のキーフレームの回転インタポレータのキー値データの回転変換値は、第３クォータニオン乗算器８２４及び第５クォータニオン乗算器８２８に直接入力され、次のキーフレームの回転変換値が入力されれば遅延器８２２を通じて第４クォータニオン乗算器８２６に入力される。また、第２クォータニオン乗算器８７０から出力された以前に出現したキーフレームの復元された回転変換値は第４クォータニオン乗算器８２６及び第５クォータニオン乗算器８２８に入力される。
【０１２８】
第３クォータニオン乗算器８２４は、現在のキーフレームの回転変換値と以前に出現したキーフレームの回転変換値とをクォータニオン乗算して（ＱＡ＝Ｑｉ×Ｑ＊ｉ−１）、回転差分値ＱＡを回転方向誤差検出部８３０に出力する。回転差分値ＱＡは時間間隔［ｔｉ−１，ｔｉ］でオブジェクトの元回転方向を示す。
【０１２９】
第４クォータニオン乗算器８２６は、以前に出現したキーフレームの回転変換値と以前に出現したキーフレームの復元された回転変換値とをクォータニオン乗算し（ＱＢ＝Ｑｉ−１×ＤＱ＊ｉ−１）、回転差分値ＱＢを回転方向誤差検出部８３０に出力する。第４クォータニオン乗算器８２６で計算された回転差分値ＱＢは時間ｔｉ−１で量子化誤差によるオブジェクトの回転方向誤差及び回転方向を示し、図１１の領域２に対応する。
【０１３０】
第５クォータニオン乗算器８２８は、現在のキーフレームの回転変換値と以前に出現したキーフレームの復元された回転変換値とをクォータニオン乗算して（ＱＣ＝Ｑｉ×ＤＱ＊ｉ−１）、回転差分値ＱＣを回転方向誤差検出部８３０に出力する。第５クォータニオン乗算器８２８で計算された回転差分値ＱＣは時間ｔｉで符号化される回転差分値を示し、図１１の領域４に対応する。
【０１３１】
回転方向誤差検出部８３０は、回転方向誤差計算器８２０から入力された回転差分値ＱＡ、ＱＢ及びＱＣを用いて図１１に示すような領域１のように復号化時にオブジェクトの回転方向が元の回転方向と反対となる場合の発生有無を検出する（ステップＳ９２４）。このために回転方向誤差検出部８３０は次の式（１７）から式（２１）で規制される条件を満たすか否かをチェックする。まず、回転方向誤差検出部８３０は次の式（１７）に記載された条件を満たすかをチェックする。
【０１３２】
【数２８】
0004205426.tif 000033
【０１３３】
前記式（１７）中、回転方向誤差計算器８２０から入力された回転差分値ＱＡがＱＡ＝（ｑＡ，０、ｑＡ，１、ｑＡ，２、ｑＡ，３）Ｔであれば、前記式（１７）中の下記式（１７’）は最初成分の（ｑＡ，１、ｑＡ，２、ｑＡ，３）Ｔを除いた３成分よりなる３次元ベクトル（ｑＣ，１、ｑＣ，２、ｑＣ，３）Ｔを示す。
【０１３４】
【数２９】
0004205426.tif 000034
【０１３５】
また、前記式（１７）中の下記式（１７’’）は回転方向誤差計算器８２０から入力された回転差分値ＱＣの最初の成分を除いた成分よりなる３次元ベクトルを示す。式（１７）は前述した３次元ベクトルの内積が「０」より小さいか否かを示す。
【０１３６】
【数３０】
0004205426.tif 000035
【０１３７】
もし、前記式（１７）の内積が「０」より小さければ、回転差分値ＱＡ及び回転差分値ＱＣによる回転の方向が相反することを示す。式（１７）の内積が「０」より小さければ論理値は「真（ｔｒｕｅ）」と定義され、内積が「０」より大きければ論理値は「偽（ｆａｌｓｅ）」と定義される。
【０１３８】
【数３１】
0004205426.tif 000036
【０１３９】
前記式（１８）中、回転方向誤差計算器８２０から入力された回転差分値ＱＢがＱＢ＝（ｑＢ，０、ｑＢ，１、ｑＢ，２、ｑＢ，３）Ｔであれば、前記式（１８）中の下記式（１８’）は最初成分であるｑＢ，０を除いた３成分よりなる３次元ベクトル（ｑＢ，１、ｑＢ，２、ｑＢ，３）Ｔを示す。
【０１４０】
【数３２】
0004205426.tif 000037
【０１４１】
また、前記式（１８）中の下記式（１８’’）は回転方向誤差計算器８２０から入力された回転差分値ＱＣの最初の成分を除いた成分よりなる３次元ベクトルを示す。式（１８）は前述した３次元ベクトルの内積が「０」より小さいか否かを示す。
【０１４２】
【数３３】
0004205426.tif 000038
【０１４３】
このとき、もし、式（１８）の内積が「０」より小さければ、回転差分値ＱＢ及び回転差分値ＱＣによる回転の方向が相反することを示す。式（１８）の内積が０より小さければ論理値は「真」であると定義され、内積が「０」より大きければ論理値は「偽」であると定義される。
【０１４４】
【数３４】
0004205426.tif 000039
【０１４５】
前記式（１９）中、ｑＡ，０は回転差分値ＱＡの最初の成分を示し、所定の定数ＡＴＨは「０」に近い値に設定される。このとき、もし、式（１９）で、２ｃｏｓ−１｜ｑＡ，０｜が所定の定数であるＡＴＨより大きければ、式（１９）で示される論理式の値は「真」であると定義され、そうでなければ「偽」と定義される。式（１９）が「偽」であるということは、実際に本発明の符号化装置を具現するとき、ＡＴＨより小さな回転角q（＝２ｃｏｓ−１｜ｑＡ，０｜は無視することができるということを意味する。なぜならば、このような小さな誤差による映像の歪曲は主観的な視覚によって判断される歪曲が激しくないだけでなく、本発明が提案する誤差測定方法によって計算するときにも顕著な映像の歪曲を起こさないからである。
【０１４６】
【数３５】
0004205426.tif 000040
【０１４７】
前記式（２０）中、ｑＢ，０は回転差分値ＱＢの最初の成分を示し、所定の定数ＡＴＨは式（１９）で設定された値である。もし、前記式（２０）で２ｃｏｓ−１｜ｑＢ，０｜が所定の定数であるＡＴＨより大きければ、前記式（２０）で示される論理式の値は「真」であると定義され、そうでなければ「偽」であると定義される。
【０１４８】
【数３６】
0004205426.tif 000041
【０１４９】
前記式（２１）中、ｑＣ，０は回転差分値ＱＣの最初の成分を示し、所定の定数ＡＴＨは式（１９）で設定された値である。もし、前記式（２１）で２ｃｏｓ−１｜ｑＣ，０｜が所定の定数であるＡＴＨより大きければ、前記式（２１）で示される論理式の値は「真」であると定義され、そうでなければ「偽」であると定義される。
【０１５０】
回転方向誤差検出部８３０は前記式（１７）から前記式（２１）で示される論理演算の結果に対してＡＮＤ演算を行い、このＡＮＤ演算結果を回転方向選択部８３５に出力する。
【０１５１】
一方、時間ｔで第１クォータニオン乗算器８１０は２つの入力Ｑｉ及び前記の記号ＤＱｉ−１を有している。第１クォータニオン乗算器８１０はこの２つの入力値を用いて回転差分値を出力する。前述したように、領域１の場合に、回転差分値を受信した復号化器はオブジェクトを時計方向に回転させる。しかし、オブジェクトはＱｉ−１によって回転された位置からＱｉによって回転された位置に回転せねばならないために、元の回転方向は反時計方向にならねばならない。
【０１５２】
したがって、回転方向訂正部８１５はオブジェクトが前記の記号ＤＱｉ−１によって回転された位置から元の回転方向と同じ方向、すなわち、図１１で前記の記号ＤＱｉによって回転された位置まで反時計方向に回転すべく方向を訂正する。
【０１５３】
このために、回転方向訂正部８１５は前記の記号ＤＱｉ−１によって回転された位置から反時計方向に１８０°回転に近い位置に回転すべく新しい回転情報を設定する。したがって、回転方向は元の回転方向に訂正され、回転方向誤差は最小化される。このような、回転方向訂正部８１５は第１クォータニオン乗算器８１０から現在のキーフレームの回転差分データＱｉを入力して前述した式（１６）のように方向が訂正された回転差分データを生成して回転方向選択部８３５に出力する（ステップＳ９２６）。
【０１５４】
ここで再び、図１４に示すように、回転方向選択部８３５は回転方向誤差検出部８３０から入力された論理値の「真偽」をチェックし（ステップＳ９３０）、「真」であると判定された場合には、図１１に示される領域１の場合が生じたものと判断し、回転方向訂正部８１５から入力された前記式（１６）で示されるように訂正された回転差分値Ｑｓを量子化器８４０に出力する（ステップＳ９４０）。
【０１５５】
しかし、入力された論理値が「偽」であると判定された場合には、図１１の領域１の場合が生じていないと判断して、第１クォータニオン乗算器８１０から入力された回転差分値Ｑｉを量子化器８４０に出力する（ステップＳ９５０）。
【０１５６】
以上、本発明の望ましい第２実施形態に係るキー値データ符号化装置について説明した。
以下では、本発明で望ましい第３実施形態に係るキー値データ符号化装置について説明する。
【０１５７】
本発明に係る第１実施形態、及び第２実施形態に含まれる符号化装置は、回転差分値のうち、最初の成分値を除いた３成分値を符号化するので、復号化器は量子化誤差によって前述した式（１１）を用いて回転差分値の最初の成分値を復元できない場合もある。例えば、復元された回転差分値の最初の成分が虚数となり得る。
【０１５８】
このような、問題が生じることを防止するべく、本発明に係る第３実施形態に含まれるキー値データ符号化装置の量子化器は、復号化器が最小限の映像歪曲で、回転差分値の最初の成分を正の実数に復元するように、量子化された３成分値を適切に調整する。
【０１５９】
本発明に係る第３実施形態に含まれる符号化装置の構成は、量子化器を除けば、前記第１実施形態または第２実施形態の符号化装置の構成と同一とすることができるので、以下では第３実施形態の量子化器１０００のみについて説明する。
【０１６０】
図１６は、第３実施形態に係る符号化装置に含まれる量子化器の構成を示すブロック図である。
図１６に示すように、第３実施形態に係る量子化器１０００は入力された回転差分値を量子化する量子化部１０１０、量子化された回転差分データの値を調整する量子化データ調整部１０２０、量子化された回転差分データを逆量子化する逆量子化部１０３０、逆量子化された回転差分データの３成分を用いて最初の成分データを復元することで全体回転差分値を復元する回転差分値復元部１０４０、及び復元された差分値と元の入力された回転差分値間の誤差を測定して量子化された回転差分データを更新する誤差測定部１０５０を含んで構成されている。
【０１６１】
図１７は、第３実施形態に含まれる量子化器の処理過程を説明するためのフローチャートである。
【０１６２】
以下、図１７を参照しながら、第３実施形態の量子化過程について説明する。
第１クォータニオン乗算器から回転差分値Ｑが入力されれば、量子化部１０１０は入力された回転差分値を前述した式（１０）を用いて量子化し、量子化された回転差分データである下記の記号ＤＱ’を量子化データ調整部１０２０に出力する（ステップＳ１００５）。
【０１６３】
【数３７】
0004205426.tif 000042
【０１６４】
量子化データ調整部１０２０は次の式（２２）を用いて量子化された回転差分データの３成分を調整する（ステップＳ１０１０）。
【０１６５】
【数３８】
0004205426.tif 000043
【０１６６】
前記式（２２）中、Ｉ，ｊ及びｋは量子化された回転差分データに合算されて回転差分データを調整する整数の変数であり、ｄはＩ、ｊ及びｋの変化範囲である。調整された量子化された３成分値は逆量子化部１０３０に出力される。
【０１６７】
逆量子化部１０３０は調整された量子化された回転差分データＩｉｊｋを逆量子化して回転差分値復元部１０４０に出力する（ステップＳ１０２０）。
逆量子化された回転差分値である下記の記号ＤＤＩｉｊｋの３成分を入力された回転差分値復元部１０４０は前述した式（１１）を用いて最初の成分を復元し、復元された回転差分値を誤差測定部１０５０に出力する（ステップＳ１０３０）。
【０１６８】
【数３９】
0004205426.tif 000044
【０１６９】
誤差測定部１０５０は入力された回転差分値の最初の成分の値をさきにチェックし、最初成分の値が実数であれば次の誤差測定段階を行い、復元された回転差分値の最初の成分が虚数であれば、後述するＳ１０６０段階へ進む（ステップＳ１０４０）。
【０１７０】
誤差測定部１０５０は回転差分値の最初の成分が実数であれば、元の回転差分値と復元された回転差分値間と誤差ｅｉｊｋを測定し（ステップＳ１０４５）、測定された誤差が調整誤差値であるｅｉ＊ｊ＊ｋ＊よりも小さいか否かをチェックする（ステップＳ１０５０）。元の回転差分値と復元された回転差分値間の誤差を測定する方法については図１４を参照して後述する。
【０１７１】
もし、測定された誤差が調整誤差値ｅｉ＊ｊ＊ｋ＊よりも小さければ、現在の誤差値ｅｉｊｋで調整誤差値であるｅｉ＊ｊ＊ｋ＊を更新し（ステップＳ１０５５）、量子化された元の回転差分値に対して調整された値（ｉ，ｊ，ｋ）が調整範囲（−ｄ〜＋ｄ）を超えたか否かをチェックする（ステップＳ１０６０）。もし、超えていなければ、前述したステップＳ１０１０からからステップＳ１０５５を反復的に行うが、この際、前記したステップＳ１０１０で量子化データ調整部１０２０は量子化された回転差分データの第２番目から第４番目の成分を順次１つずつ増加させながら前記したステップＳ１０１０からステップＳ１０５５を行う。
【０１７２】
例えば、量子化データ調整部１０２０は入力された回転差分データの２番目及び３番目の成分はそのまま保ち、ｋ値を（−ｄ〜＋ｄ）範囲で１つず変更させつつ４番目の成分値に合算し、復元された最初の成分を実数にし、誤差が最小となる４つの成分値を探す。ｋが＋ｄ値に至ると再びｋを−ｄに初期化し、ｊ値を（−ｄ〜＋ｄ）範囲で１だけ変更させた後、これを３番目の成分値に合算し、ｋ値を（−ｄ〜＋ｄ）範囲で１だけ変更させつつ４番目の成分値に合算し、復元された最初の成分を実数にして誤差が最小となる４成分値を探す。
【０１７３】
ｊも＋ｄ値に至ると再びｊとｋとを−ｄに初期化し、ｉ値を（−ｄ〜＋ｄ）範囲で１だけ変更させた後、これを２番目の成分値に合算し、ｊ値を３番目の成分値に合算し、ｋ値を（−ｄ〜＋ｄ）範囲で１だけ変更させつつ４番目の成分値に合算し、復元された最初の成分を実数にして誤差が最小となる４成分値を探す。このような過程をｉ，ｊ，ｋが全て＋ｄに至るまで繰り返し、復元された最初の成分を実数にして誤差が最小となる４成分値を探す。
【０１７４】
誤差測定部１０５０は第２番目から第４番目の成分値を共に変更しながら更新された調整誤差値ｅｉ＊ｊ＊ｋ＊が最終誤差値ｅｇｉ＊ｇｊ＊ｇｋ＊よりも小さいか否かをチェックし（ステップＳ１０７０）、調整誤差値が最終誤差値より小さければ最終誤差値ｅｇｉ＊ｇｊ＊ｇｋ＊を調整誤差値ｅｉ＊ｊ＊ｋ＊に更新し、量子化された回転差分データを次の式（２３）のように訂正する（ステップＳ１０７５）。
【０１７５】
【数４０】
0004205426.tif 000045
【０１７６】
最終誤差値ｅｇｉ＊ｇｊ＊ｇｋ＊を更新し、量子化された回転差分データを訂正した誤差測定部１０５０は訂正された回転差分データを量子化データ調整部１０２０に出力する。
【０１７７】
量子化データ調整部１０２０は回転差分データの各成分に合算する変数値を−ｄに再設定し、誤差測定部１０５０から入力された回転差分データに対して前述したステップＳ１０１０からステップＳ１０６０を繰り返し、誤差測定部１０５０から入力された回転差分データを基準に、既存に貯蔵された最終誤差値より小さな誤差値を示す回転差分データの存否をチェックする。
【０１７８】
一方、誤差測定部１０５０は第Ｓ１０７０段階で調整誤差値が最終誤差値より大きいか同じであれば、現在貯蔵された最終誤差値ｅｇｉ＊ｇｊ＊ｇｋ＊に対応する量子化された回転差分データである下記式（２３’）を循環ＤＰＣＭ演算部に出力する（ステップＳ１０８０）。
【０１７９】
【数４１】
0004205426.tif 000046
【０１８０】
以上、本発明の望ましい実施形態である第３実施形態のキー値データ符号化装置について説明した。
以下では、図１８から図２０に基づいて本発明の符号化装置によってキー値データが符号化されたビットストリームを復号化する復号化方法及び装置を説明する。
【０１８１】
図１８は、本発明の望ましい実施形態に係る復号化装置の構成を示すブロック図である。
図１８に示すように、本発明の復号化装置は入力されたビットストリームからクォータニオンで表されたキー値データを復号化するのに必要なヘッダ情報を復号化してキー値データ復号化部１１００に提供するキー値ヘッダ復号化器１１７０、入力されたビットストリームからエントロピ符号化されたキー値データをエントロピ復号化して循環ＤＰＣＭ演算された回転差分データまたは量子化された回転差分データを生成するエントロピ復号化器１１１０、エントロピ復号化器１１１０から入力された循環ＤＰＣＭ演算された回転差分データに逆循環ＤＰＣＭ演算を行って量子化された回転差分データを生成する逆循環ＤＰＣＭ演算部１１２０、量子化された回転差分データを逆量子化して回転差分値を生成する逆量子化器１１３０、及び現在のキーフレームの回転差分値を以前に出現したキーフレームの回転変換値とクォータニオン乗算して現在のキーフレームの回転変換値を生成するクォータニオン乗算器１１４０を含んで構成されている。
【０１８２】
図１８は、本発明の望ましい実施形態に係るキー値データ復号化方法を説明するフローチャートである。
図１８に基づいて本発明の望ましい実施形態に係るキー値データ復号化方法を説明する。
【０１８３】
まず、前述した符号化装置によって符号化されたキー値データのビットストリームはキー値ヘッダ復号化器１１７０及びキー値データ復号化部のエントロピ復号化器１１１０に各々入力される。
【０１８４】
キー値ヘッダ復号化器１１７０は入力されたビットストリームからキー値データの復号化に必要なヘッダ情報を復号化してキー値データ復号化部１１００に提供する（ステップＳ１１００）
【０１８５】
キー値ヘッダ情報にはＤＰＣＭ次数に応じてクォータニオン形式の量子化された第１及び第２イントラキー値データ、及び残りのキー値データを復号化するための多数のフラグが符号化されている。
【０１８６】
もし、ＤＰＣＭ次数が「１」であれば（例えば、前述した多数のフラグのうち１つのｎＫＶＤＰＣＭＯｒｄｅｒが０に設定されたならば）、第１量子化されたキー値データだけイントラキー値データとしてキー値ヘッダ情報に含まれる。もし、第１逆量子化されたキー値データのクォータニオン値が下記式（Ａ）で表されれば、第１逆量子化されたキー値データは次の式（２４）を用いて計算される。
【０１８７】
【数４２】
0004205426.tif 000047
【０１８８】
【数４３】
0004205426.tif 000048
【０１８９】
前記式（２４）中、ｘＳｉｇｎは後述するＯｒｉＩＤＰＣＭＫｅｙＶａｌｕｅＨｅａｄｅｒクラスのｎＦｉｒｓｔＸＳｉｇｎが１であるとき、１値を有し、その他の場合には−１を有する。ｙＳｉｇｎ及びｚＳｉｇｎもｎＦｉｒｓｔＹＳｉｇｎ及びｎＦｉｒｓｔＺＳｉｇｎのような関係を有する。
【０１９０】
最後に、この復元されたクォータニオンは回転インタポレータで使われるために各変位に変換される。キー値データから復元された各変位は４次元ベクトル下記式（Ｂ）で表され、ここで、ｉは現在のキーデータを、下記式（Ｃ）は回転軸ベクトルを、下記の記号Ｄθｉは反時計方向への回転角を示す。したがって、この復元されたクォータニオンは次の式（２５）を用いて各変位に変換される。
【０１９１】
【数４４】
0004205426.tif 000049
【０１９２】
【数４５】
0004205426.tif 000050
【０１９３】
【数４６】
0004205426.tif 000051
【０１９４】
【数４７】
0004205426.tif 000052
【０１９５】
一方、ＤＰＣＭの次数が２であれば、例えば、ｎＫＶＤＰＣＭＯｒｄｅｒが１に設定されたならば、第１及び第２量子化されたキー値データがキー値ヘッダ情報に含まれる。この場合、第１キー値データは前述したように復元される。一方、第２キー値データを復元するために、若干異なる過程が適用されるが、これは、第２量子化されたキー値データの３成分だけが、符号化されたビットストリームを通じて伝送され、また、これらの成分値はイントラキー値データではなく、第１キー値データからの差分値である下記式（Ｄ）で表されるからである。もし、第２差分値のクォータニオン及び逆量子化されたキー値データが下記式（Ｅ）で表されれば、これは次の式（２６）を用いて計算される。
【０１９６】
【数４８】
0004205426.tif 000053
【０１９７】
【数４９】
0004205426.tif 000054
【０１９８】
【数５０】
0004205426.tif 000055
【０１９９】
前記式（２６）中、ｓｅｃｏｎｄＸＳｉｇｎは後述するＯｒｉＩＤＰＣＭＫｅｙＶａｌｕｅＨｅａｄｅｒクラスのｎＳｅｃｏｎｄＸＳｉｇｎが１であるとき、１値を有し、その他の場合には−１を有する。ＳｅｃｏｎｄＹＳｉｇｎ及びｓｅｃｏｎｄＺＳｉｇｎもｎＳｅｃｏｎｄＹＳｉｇｎ及びｎＳｅｃｏｎｄＺＳｉｇｎのような関係を有する。もし、第２逆量子化されたキー値データのクォータニオン値が下記（Ｆ）で表されれば、前記の記号ＤＱ１はＤＤＱ１とＤＱ０との間のクォータニオン乗算で計算される。したがって、下記式（Ｇ）を用いて計算される。
【０２００】
【数５１】
0004205426.tif 000056
【０２０１】
【数５２】
0004205426.tif 000057
【０２０２】
また、キー値ヘッダ復号化器１１７０は復号化されたキー値データ、及びヘッダ情報をキー値復号化部１１００に出力する。
一方、キー値データの差分データが符号化されたビットストリームを入力されたエントロピ復号化器１１１０はキー値ヘッダ復号化器１１７０で復号化された復号化情報を用いて入力されたビットストリームをエントロピ復号化する（ステップＳ１１２０からステップＳ１１２８）。
【０２０３】
図２０は、エントロピ復号化器に入力されるビットストリームのデータ構造を示す図面である。
図２０においてＮ（ｎＮｕｍｂｅｒ  Ｏｆ  Ｋｅｙ  Ｖａｌｕｅ）を符号化されたキー値データの数とするとき、ＤＰＣＭの次数が「０」である場合にはビットストリームに含まれる各成分の回転差分データの数はＮ−１（０、１、…、ｎＮｕｍｂｅｒＯｆＫｅｙＶａｌｕｅ−２）となり、ＤＰＣＭの次数が「１」である場合には、ビットストリームに含まれる各成分の回転差分データの数はＮ−２（０、１、…、ｎＮｕｍｂｅｒ  Ｏｆ  Ｋｅｙ  Ｖａｌｕｅ−３）となる。
【０２０４】
まず、ビットストリームを入力されたエントロピ復号化器１１１０はキー値ヘッダ復号化器１１７０からｋｅｙｖａｌｕｅ＿ｆｌａｇ（ｘ＿ｋｅｙｖａｌｕｅ＿ｆｌａｇ，ｙ＿ｋｅｙｖａｌｕｅ＿ｆｌａｇ，ｚ＿ｋｅｙｖａｌｕｅ＿ｆｌａｇ）を入力され、それぞれのｋｅｙｖａｌｕｅ＿ｆｌａｇ値が１に設定されているかをチェックする（ステップＳ１１２０）。
【０２０５】
このとき、もし、それぞれのｋｅｙｖａｌｕｅ＿ｆｌａｇ値が「０」に設定されていれば、これはキー値ヘッダ復号化器１１７０で復号化された第１及び第２キー値データを除き、全てのキー値データの各成分の量子化されたキー値データまたは差分データが各々後述する「ＯｒｉＩ  Ｋｅｙ  Ｖａｌｕｅ  ＣｏｄｉｎｇＢｉｔクラス」の「ｎＡｌｌ  Ｋｅｙ  Ｖａｌｕｅｓ」と同一であるということを意味する。
【０２０６】
したがって、エントロピ復号化器１１１０は各成分のキー値データをキー値ヘッダ復号化器１１７０から入力された「ｎＡｌｌ  Ｋｅｙ  Ｖａｌｕｅｓ」と同値に復号化し、復号化されたキー値データを逆循環ＤＰＣＭ演算部１１２０に出力する（ステップＳ１１２２）。
【０２０７】
もし、それぞれの「ｋｅｙ  ｖａｌｕｅ＿ｆｌａｇ値」が「０」でない値（例えば、「１」）に設定されているならば、エントロピ復号化器１１１０は入力されたキー値データである下記式（Ｈ）の各成分を復号化するためにキー値ヘッダ復号化器１１７０から入力されたエントロピ復号化モードをチェックする（ステップＳ１１２４）。
【０２０８】
【数５３】
0004205426.tif 000058
【０２０９】
エントロピ復号化モードが２進復号化モードである場合には次の表１に記載されたｄｅｃｏｄｅＳｉｇｎｅｄＡＡＣ（）関数を用いて適応算術符号化されたビットストリームを復号化して量子化された回転差分データを逆循環ＤＰＣＭ演算部１１２０に出力する（ステップＳ１１２６）。
【０２１０】
【表１】
0004205426.tif 000059
【０２１１】
エントロピ復号化モードが２進復号化モードでない場合には、エントロピ復号化器１１１０はｄｅｃｏｄｅＵｎａｒｙ  ＡＡＣ（）関数を用いて入力されたビットストリームを復号化する（ステップＳ１１２８）。ｄｅｃｏｄｅＵｎａｒｙ  ＡＡＣ（）関数はビットストリームから１が判読されるまで０を判読し、判読された０の数を絶対値に変換した後、「１」が判読されたビット次の符号ビットを判読して復号化して量子化された回転差分データを逆循環ＤＰＣＭ演算部１１２０に出力する。ｄｅｃｏｄｅＵｎａｒｙ  ＡＡＣ（）関数の一例を下の表２に記載した。
【０２１２】
【表２】
0004205426.tif 000060
【０２１３】
前記したｄｅｃｏｄｅ  Ｓｉｇｎｅｄ  ＡＡＣ（）関数及びｄｅｃｏｄｅ  Ｕｎａｒｙ  ＡＡＣ（）関数で用いられたｑｆ＿ｄｅｃｏｄｅ（）の関数は、適応エントロピ符号化されたビットストリームから１ビットを判読する関数であって、国際標準化機構公式文書のＩＳＯ／ＩＥＣ  １４４９６−２：１９９９  Ｃｏｄｉｎｇ  ｏｆ  Ａｕｄｉｏ−Ｖｉｓｕａｌ  Ｏｂｊｅｃｔｓ：Ｖｉｓｕａｌに定義されている。
【０２１４】
0004205426.tif 000061
【０２１５】
一方、キー値ヘッダ復号化器１１７０から入力されたＤＰＣＭ次数が１であれば、エントロピ復号化器１１１０から入力されたデータは循環ＤＰＣＭ演算が行われた回転差分データであるために、逆循環ＤＰＣＭ演算部１１２０は逆循環ＤＰＣＭ演算を行う（ステップＳ１１３５）。
【０２１６】
ＮＫＶＱ  Ｂｉｔｓが逆量子化ビット数とするとき、回転差分データを入力された逆循環ＤＰＣＭ演算部１１２０は次の式（２７）を用いて入力された回転差分データ下記の記号ＤＱ’ｉ−２に対して逆循環ＤＰＣＭ演算を行い、量子化された回転差分データである下記の記号ＤＱ’’ｉ−２を計算する（ステップＳ１１３５）。
【０２１７】
【数５４】
0004205426.tif 000062
【０２１８】
その後、逆循環ＤＰＣＭ演算部１１２０は次の式（２８）に応じて入力された値下記の記号ＤＱ’ｉ−２を用いて逆ＤＰＣＭ演算されたＡ値と、逆循環ＤＰＣＭ演算された回転差分データＤＱ’’ｉ−２を用いて逆ＤＰＣＭ演算されたＢ値を求める。
【０２１９】
【数５５】
0004205426.tif 000063
【０２２０】
【数５６】
0004205426.tif 000064
【０２２１】
逆循環ＤＰＣＭ演算部１１２０はＢ＋（２ｎＫＶＱＢｉｔｓ−１−１）値が「０」以上で、量子化範囲の最大値以下であれば、Ｂを逆循環ＤＰＣＭ演算されたデータとして出力し、Ｂ＋（２ｎＫＶＱＢｉｔｓ−１−１）値が「０」より小さいか、量子化範囲の最大値より大きければ、Ａ値を逆循環ＤＰＣＭ演算されたデータとして出力する。
【０２２２】
前述した逆循環ＤＰＣＭ演算部をＣ＋＋形式のプログラムコードにて具現した一例を次の表３に記載した。
【０２２３】
【表３】
0004205426.tif 000065
【０２２４】
逆循環ＤＰＣＭ演算が行われて生成された量子化された回転差分データである下記式（Ｉ）を入力された逆量子化器１１３０は次の式（２９）に応じて逆量子化演算を行って回転差分値である下記（Ｊ）を復元してクォータニオン乗算器１１４０に出力する（ステップＳ１１４０）。
【０２２５】
【数５７】
0004205426.tif 000066
【０２２６】
【数５８】
0004205426.tif 000067
【０２２７】
【数５９】
0004205426.tif 000068
【０２２８】
回転差分値を入力されたクォータニオン乗算器１１４０は次の式（３０）に応じて入力された回転差分値である前記の記号ＤＤＱｉと以前に出現したキーフレームの回転変換値である前記の記号ＤＱｉ−１をクォータニオン乗算して、現在のキーフレームの回転変換値である下記式（Ｋ）を復元する（ステップＳ１１５４）。
【０２２９】
【数６０】
0004205426.tif 000069
【０２３０】
【数６１】
0004205426.tif 000070
【０２３１】
復号化器は回転変換値を復元した後、復元された回転変換値が最後のキー値データに関するものであるかをチェックし（ステップＳ１１５６）、最後のキー値データでなければ前述したステップＳ１１４０からステップＳ１１５４を反復的に行い、最後のキーフレームに関するものであれば復元された回転変換値を出力する（ステップＳ１１５８）。
【０２３２】
一方、ＤＰＣＭ次数が０である場合、逆循環ＤＰＣＭ演算部１１２０は復号化された量子化された回転差分データである下記式（Ｌ）を逆量子化器１１３０に出力し、逆量子化器は次の式（３１）に応じて入力された回転差分データを逆量子化し、回転差分値である下記式（Ｍ）を生成し、生成された回転差分値をクォータニオン乗算器１１４０に出力する（ステップＳ１１４０）。
【０２３３】
【数６２】
0004205426.tif 000071
【０２３４】
【数６３】
0004205426.tif 000072
【０２３５】
【数６４】
0004205426.tif 000073
【０２３６】
回転差分値を入力されたクォータニオン乗算器１１４０はＤＰＣＭ次数が０でない場合と同一に回転変換値を復元するが（ステップＳ１１５０からステップＳ１１５８）、但し、このときには次の式（３２）を用いてクォータニオン乗算を行う。
【０２３７】
【数６５】
0004205426.tif 000074
【０２３８】
以上、本発明の望ましい実施形態の回転インタポレータのキー値データ復号化方法及び復号化装置について説明した。
図２１から図２５は、本発明に係るキー値データ復号化装置を具現するためのプログラムコードの一例として、ＳＤＬ言語形式で具現した例である。以下、図２１から図２５に示す各変数とその意味について説明する。
【０２３９】
図２１は、「Ｃｏｍｐｒｅｓｓｅｄ  Ｏｒｉｅｎｔａｔｉｏｎ  Ｉｎｔｅｒｐｏｌａｔｏｒクラス」を説明する図面である。このクラスは、符号化された回転インタポレータのビットストリームを判読するための最上位クラスである。「ＯｒｉＩ  Ｋｅｙ  Ｖａｌｕｅ  Ｈｅａｄｅｒ」及び「ＯｒｉＩ  ＤＰＣＭ  Ｋｅｙ  Ｖａｌｕｅ」は、従来の回転インタポレータのキーデータに対応するキー値データの情報を判読するためのクラスである。一方、ｑｆ＿ｓｔａｒｔ（）関数は、キー値データが符号化されたビットストリームを判読する前に算術復号化器を初期化するための関数である。
【０２４０】
図２２は、ＯｒｉＩ  Ｋｅｙ  Ｖａｌｕｅ  Ｈｅａｄｅｒクラスを示す図面である。このクラスに用いられた変数の意味は次の通りである。
ｎＫＶＱＢｉｔ：キー値データの逆量子化ビットサイズを示す。
ｎＮｕｍ  Ｋｅｙ  Ｖａｌｕｅ  Ｃｏｄｉｎｇ  Ｂｉｔ：ｎＮｕｍｂｅｒ  Ｏｆ  Ｋｅｙ  Ｖａｌｕｅのビットサイズを示す。
ｎＮｕｍｂｅｒ  Ｏｆ  Ｋｅｙ  Ｖａｌｕｅ：キー値データの数を示す。
ｎＫＶ  ＤＰＣＭ  Ｏｒｄｅｒ：キー値データの復号化に使われる逆ＤＰＣＭ演算の次数を示す。
【０２４１】
「ｎＫＶ  ＤＰＣＭ  Ｏｒｄｅｒ＝０」であれば、逆循環ＤＰＣＭ演算が行われないことを意味し、「ｎＫＶ  ＤＰＣＭ  Ｏｒｄｅｒ＝１」であれば逆循環ＤＰＣＭ演算が行われるべきであることを意味する。
図２３は、Ｏｒｉ  ＤＰＣＭ  Ｋｅｙ  Ｖａｌｕｅ  Ｈｅａｄｅｒクラスを示す図面である。このクラスで使われた変数の意味は次の通りである。
【０２４２】
ｆｉｒｓｔ  ＱＫＶ＿Ｓ，ｆｉｒｓｔ  ＱＫＶ＿Ｘ，ｆｉｒｓｔ  ＱＫＶ＿Ｙ，ｆｉｒｓｔ  ＱＫＶ＿Ｚ：クォータニオン形式の量子化されたキー値データの各成分（ｓ，ｘ，ｙ，ｚ）の最初の値を示す。
【０２４３】
ＮＦｉｒｓｔ  ＸＳｉｇｎ，ｎＦｉｒｓｔ  ＹＳｉｇｎ，ｎＦｉｒｓｔ  ＺＳｉｇｎ：量子化されたキー値データの３成分（ｘ，ｙ，ｚ）の最初の値の符号を示す。
ｓｅｃｏｎｄ  ＱＫＶ＿Ｘ，ｓｅｃｏｎｄ  ＱＫＶ＿Ｙ，ｓｅｃｏｎｄ  ＱＫＶ＿Ｚ：クォータニオン形式の量子化されたキー値データの３成分（ｘ，ｙ，ｚ）の２番目の値を示す。
【０２４４】
ＮＳｅｃｏｎｄ  ＸＳｉｇｎ，ｎＳｅｃｏｎｄ  ＹＳｉｇｎ，ｎＳｅｃｏｎ  ＺＳｉｇｎ：量子化されたキー値データの３成分（ｘ，ｙ，ｚ）の２番目の値の符号を示す。
ｂＩｓ  Ｍｏｒｅ  Ｔｗｏ  ＫＶｓ：このフラグは逆循環ＤＰＣＭ演算が行われるべき場合に、復号化されるキー値データが２つ以上であるか否かを示す。
ｘ＿ｋｅｙ  ｖａｌｕｅ＿ｆｌａｇ，ｙ＿ｋｅｙ  ｖａｌｕｅ＿ｆｌａｇ，ｚ＿ｋｅｙ  ｖａｌｕｅ＿ｆｌａｇ：これらフラグは３成分（ｘ，ｙ，ｚ）各々に対して量子化されたあらゆる値が同異を示す。
【０２４５】
図２４は、ＯｒｉＩＫｅｙＶａｌｕｅＣｏｄｉｎｇＢｉｔクラスを示す図面である。このクラスにおいて使われた変数の意味は次の通りである。
ｎＫＶ  Ｃｏｄｉｎｇ  Ｂｉｔ：この値はイントラキー値データ（ｆｉｒｓｔＱＫＶ＿Ｓ，ｆｉｒｓｔ  ＱＫＶ＿Ｘ，ｆｉｒｓｔ  ＱＫＶ＿Ｙ，ｆｉｒｓｔ  ＱＫＶ＿Ｚａｎｄ  ｓｅｃｏｎｄ  ＱＫＶ＿Ｘ，ｓｅｃｏｎｄ  ＱＫＶ＿Ｙ，ｓｅｃｏｎｄ  ＱＫＶ＿Ｚｉｎ  ＯｒｉＩ  ＤＰＣＭ  Ｋｅｙ  Ｖａｌｕｅ  Ｈｅａｄｅｒ  ｃｌａｓｓ）を除いたあらゆるクォータニオンキー値データの各成分が量子化された後、実際に貯蔵されるのに必要なビット数を示す。
【０２４６】
ｎＡｌｌ  Ｋｅｙ  Ｖａｌｕｅ：この値はそれぞれのｋｅｙ  ｖａｌｕｅ＿ｆｌａｇビットが「０」に設定されたとき、全てのキー値データの各成分の量子化された値を示す。
ｎＳｉｇｎ：この値はｎＡｌｌＫｅｙＶａｌｕｅの符号を示す。
【０２４７】
ｂＩｓ  Ｕｎａｒｙ  ＡＡＣ：このフラグは３成分（ｘ，ｙ，ｚ）それぞれの量子化された値の復号化に用いられる適応算術量子化方法を示す。このフラグが「真」に設定されたならばｕｎａｒｙ  ＡＡＣ復号化関数が用いられ、このフラグが「偽」に設定されたならばｂｉｎａｒｙ  ＡＡＣ復号化関数が用いられる。
【０２４８】
図２５は、ＯｒｉＩ  ＤＰＣＭ  Ｋｅｙ  Ｖａｌｕｅクラスを示す図面である。このクラスで使われた変数の意味は次の通りである。
Ｄｅｌｔａ  Ｋｅｙ  Ｖａｌｕｅ：この配列はキー値データの３成分（ｘ，ｙ，ｚ）に関連した量子化されたキー値データをクォータニオン形式で貯蔵する。この配列に貯蔵された量子化されたキー値データはｄｅｃｏｄｅ  Ｕｎａｒｙ  ＡＡＣまたはｄｅｃｏｄｅ  Ｓｉｇｎｅｄ  ＡＡＣ関数を用いてビットストリームから復号化される。
【０２４９】
ＫＶＸ  Ｓｉｇｎ  Ｃｏｎｔｅｘｔ，ｋＶＹ  Ｓｉｇｎ  Ｃｏｎｔｅｘｔ，ｋＶＺ  Ｓｉｇｎ  Ｃｏｎｔｅｘｔ：このコンテキストはｄｅｃｏｄｅ  Ｕｎａｒｙ  ＡＡＣ、またはｄｅｃｏｄｅ  Ｓｉｇｎｅｄ  ＡＡＣ関数でＤｅｌｔａ  Ｋｅｙ  Ｖａｌｕｅの３成分の符号を復号化するのに用いられるコンテキストである。
【０２５０】
ＫＶＸ  Ｕｎａｒｙ  Ｃｏｎｔｅｘｔ，ｋＶＹ  Ｕｎａｒｙ  Ｃｏｎｔｅｘｔ，ｋＶＺ  Ｕｎａｒｙ  Ｃｏｎｔｅｘｔ：このコンテキストはｄｅｃｏｄｅ  Ｕｎａｒｙ  ＡＡＣ関数でＤｅｌｔａ  Ｋｅｙ  Ｖａｌｕｅの３成分の値を復号化するのに用いられるコンテキストである。
【０２５１】
ＫＶＸ  Ｃｏｎｔｅｘｔ，ｋＶＹ  Ｃｏｎｔｅｘｔ，ｋＶＺ  Ｃｏｎｔｅｘｔ：このコンテキストはｄｅｃｏｄｅ  Ｓｉｇｎｅｄ  ＡＡＣ関数でＤｅｌｔａ  Ｋｅｙ  Ｖａｌｕｅの３成分の値を復号化するのに用いられるコンテキストである。
【０２５２】
以上に説明した望ましい実施形態に係る復号化装置による復号化方法は、以下に示す処理を行うものである。
つまり、この復号化方法は、キーフレーム基盤のグラフィックアニメーション方式で、キーフレームに表現されるオブジェクトの回転変換を示す回転インタポレータのキー値データを符号化したビットストリームを復号化する復号化方法において、クォータニオンで表現される各キーフレームのキー値データによってオブジェクトに適用される回転変換間の差だけの回転変換を示す回転差分値を量子化してエントロピ符号化した回転差分データを復元する段階と、回転差分データのエントロピ復号化方法を示すエントロピ復号化モードを含むエントロピ復号化情報を復元する段階と、エントロピ復号化モードによってエントロピ復号化された回転差分データに逆循環ＤＰＣＭ演算の遂行の如何を示す逆循環ＤＰＣＭ演算次数を含む逆循環ＤＰＣＭ情報を復元する段階と、逆循環ＤＰＣＭ次数によって逆循環ＤＰＣＭ演算が行われた回転差分データを逆量子化して、回転差分値の復元に用いられる逆量子化ビット数を含む量子化情報を復元する段階と、を含む。
【０２５３】
ここで、回転差分データは、クォータニオンで表現された回転差分値の３成分だけが量子化されて符号化されているのが望ましい。
【０２５４】
また、エントロピ復号化情報は、キー値データの各成分の回転差分データが同じ値であるか否かを示すキー値フラグと、キー値フラグが、各成分の回転差分データがいずれも同じ値であるということを示す場合に、あらゆるキー値データの回転差分データの各成分に復号化される所定の回転差分データをさらに含むのが望ましい。
【０２５５】
そして、逆循環ＤＰＣＭ情報は、回転差分データに逆循環ＤＰＣＭ演算を行う場合に用いられるイントラ回転差分データをさらに含むのが望ましい。
【０２５６】
以下、図１６に示す本発明の第３実施形態に係る量子化器１０００に含まれた誤差測定部１０５０で元の回転差分値と量子化された後、逆量子化されて復元された回転差分値間の誤差を測定する方法について説明する。
【０２５７】
また、本発明の誤差測定方法は符号化される前の回転インタポレータのキー値データと符号化されて復号化された回転インタポレータのキー値データ間の誤差を測定するにも用いられる。したがって、前述した誤差測定部で誤差測定に用いられる元の回転差分値及び復元された回転差分値を、符号化される前の回転インタポレータのキー値データ及び復号化された回転インタポレータのキー値データに各々対応させて説明する。
【０２５８】
回転インタポレータのキー値データを符号化する過程で元の回転インタポレータのキー値データと復元された回転インタポレータのキー値データ間の誤差は量子化過程で生じる。
ここで、量子化過程で生じた誤差は、元のキー値データによる回転変換と復元されたキー値データによる回転変換間の回転閣議差分として定義される。
【０２５９】
すなわち、回転インタポレータノードに属する１つのキー値データを下記式（Ｎ）、これを復号化器で復元したキー値データを下記式（Ｏ）とする場合（但し、下記の記号（Ｐ）で表されるベクトルｒは回転軸を表し、θは回転量を表し、その範囲は下記の関係（Ｑｘ）を満たす）、下記式（Ｎ）と下記式（Ｏ）とにより３次元空間上の任意の位置ベクトルｘからベクトルｙ及びベクトルｙへの回転変換がなされるとき、生じる量子化誤差はベクトルｙとベクトルｙの差で計算される。これは量子化誤差ベクトル下記式（Ｒ）の関係を成立させる。下記式（Ｓ）で表されるベクトルｘ、下記式（Ｔｘ）で表されるベクトルｙ及び下記の記号Ｄｙをクォータニオンで表わせば、次の式（３３）ように定義される。
【０２６０】
【数６６】
0004205426.tif 000075
【０２６１】
【数６７】
0004205426.tif 000076
【０２６２】
【数６８】
0004205426.tif 000077
【０２６３】
【数６９】
0004205426.tif 000078
【０２６４】
【数７０】
0004205426.tif 000079
【０２６５】
【数７１】
0004205426.tif 000080
【０２６６】
【数７２】
0004205426.tif 000081
【０２６７】
回転変換を示す前記式（Ｎ）及び前記式（Ｏ）をクォータニオンで表したものを各々Ｑ、下記の記号ＤＱとする場合、次の関係式（３４）を導くことができる。
【０２６８】
【数７３】
0004205426.tif 000082
【０２６９】
【数７４】
0004205426.tif 000083
【０２７０】
ここで、Ａ×Ｂはクォータニオン乗算を表し、Ａ＊はＡの共役複素数を意味する。この関係式によって次の式（３５）が得られる。
【０２７１】
【数７５】
0004205426.tif 000084
【０２７２】
前記式（３５）中、Ｑｅｒｒｏｒは、前記の記号（Ｔｘ）のベクトルｙと前記の記号（Ｄｙ）との間の回転変換関係を示す値で次の式（３６）で定義される。
【０２７３】
【数７６】
0004205426.tif 000085
【０２７４】
したがって、前記の記号（Ｔｘ）のベクトルｙと前記の記号（Ｄｙ）との間の差分回転角をθｅｒｒｏｒとすれば、クォータニオン変換式と式（３６）によりθｅｒｒｏｒは次の式（３７）を用いて求めることができる。
【０２７５】
【数７７】
0004205426.tif 000086
【０２７６】
前記式（３７）中、「・」の記号は内積の演算を意味する。式（３７）は全体アニメーションキーフレームのうち、如何なる特定時間に現れる瞬時量子化誤差を表し、これを全体アニメーション区間に対する量子化誤差を求める式で誘導するために特定時間ｔでの瞬時量子化誤差として示せば次の式（３８）の通りである。
【０２７７】
【数７８】
0004205426.tif 000087
【０２７８】
前記式（９）を回転インタポレータがアニメーションを行う全体キーフレーム区間に対して拡張して全体区間［ｔｍｉｎ，ｔｍａｘ］に対する平均誤差Ｅｍ及び最大誤差Ｅｐを誘導すれば次の通りである。
【０２７９】
ここで、平均誤差Ｅｍを求めるために、図２５に示すように間隔［ｔｉ−１， ｔｉ］から平均誤差の部分和Ｅｉｍを先に求める。以下では、元のキー値データＱｉ−１及びＱｉに対応する復号化されたキー値データを前記の記号ＤＱｉ−１と前記の記号ＤＱｉという。
【０２８０】
また、３次元空間上で捩じれたアニメーション経路によって、図２５に示すように部分領域［ｔｉ−１， ｔｉ］は［ｔｉ−１， ｔｉ’’］及び［ｔｉ’’， ｔｉ］に分離され、各々独立して計算されねばならない。ここで、２つのアニメーション経路（Ｑｉの集合及び前記の記号ＤＱｉの集合）間の距離は時間間隔［ｔｉ−１， ｔｉ］の時間ｔｉ’’で最小となると仮定する。時間ｔｉ−１及び時間ｔｉで瞬間的な誤差は次の式（３９）を用いて計算することができる。
【０２８１】
【数７９】
0004205426.tif 000088
【０２８２】
また、時間間隔［ｔｉ−１，ｔｉ］でｔｉ’’の部分は次の式（４０）のように（ｅｉ−１）／ｅｉに比例する。
【０２８３】
【数８０】
0004205426.tif 000089
【０２８４】
ｔｉ’’での中間クォータニオン値及び瞬間的な誤差は次の数（４１）を用いて計算することができる。
【０２８５】
【数８１】
0004205426.tif 000090
【０２８６】
但し、任意の時間ｔで瞬間的な誤差は次の式（４２）を用いて求めることが可能であるということに留意せねばならない。
【０２８７】
【数８２】
0004205426.tif 000091
【０２８８】
前記式（４２）中、ａｒｃｃｏｓの（）内の式は、それぞれ、下記式（Ｕ）、（Ｖ）で表される。
【０２８９】
【数８３】
0004205426.tif 000092
【０２９０】
しかし、任意の時間ｔでｅ（ｔ）を計算することは容易ではない。したがって、本発明にあっては、次のような線形近似式（４３）を用いることとする。
【０２９１】
【数８４】
0004205426.tif 000093
【０２９２】
前記近似式（４３）により、次の式（４４）を用い、時間間隔［ｔｉ−１，ｔｉ］で平均誤差の部分和Ｅｉｍ及び最大誤差の部分和Ｅｉｐを求めることができる。
【０２９３】
【数８５】
0004205426.tif 000094
【０２９４】
前記式（４４）を整理すると、次の式（４５）のようになる。
【０２９５】
【数８６】
0004205426.tif 000095
【０２９６】
最終的に全体時間間隔［ｔｍｉｎ， ｔｍａｘ］で平均誤差Ｅｍ及び最大誤差Ｅｐは次の式（４６）を用いてめることができる。
【０２９７】
【数８７】
0004205426.tif 000096
【０２９８】
したがって、図１６に示す本発明の第３実施形態に係る量子化器１０００に含まれた誤差測定部１０５０では前記式（３７）に応じて誤差が計算され、クォータニオン空間で量子化誤差による映像歪曲の程度をさらに客観的に測定できる。
【０２９９】
図２６は、本発明に含まれるキー値データ符号化方法と従来のキー値データ符号化方法に係る性能とを比較する図面である。図１５に示すように、本発明のキー値データ符号化方法によれば、従来のＭＰＥＧ−４  ＢＩＦＳ  ＰＭＦＣ方法より符号化ビット数に対する映像歪曲がはるかに減ることがわかる。
【０３００】
本発明のキー値データ符号化方法及び復号化方法は、コンピュータにて読取れる記録媒体にコンピュータにて読取れるコードとして具現し得る。コンピュータにて読取れる記録媒体はコンピュータシステムによって読取られるデータが貯蔵されるあらゆる種類の記録装置を含む。コンピュータにて読取れる記録媒体の例としては、ＲＯＭ，ＲＡＭ，ＣＤ−ＲＯＭ，磁気テープ，フロッピーディスク、光データ貯蔵装置などがあり、またキャリアウェーブ（例えば、インターネットを通じた伝送）の形に具現することも含む。また、コンピュータにて読取れる記録媒体はネットワークで連結したコンピュータシステムに分散され、分散方式でコンピュータにて読取れるコードが貯蔵及び実行され得る。
【０３０１】
以上、本発明についてその望ましい実施形態を中心に説明した。本発明が属する技術分野の当業者であれば、本発明が、本発明の技術的思想に基づく限りにおいて、各種の変形された形を具現することが可能なことは容易に理解される。したがって、本発明は、ここに開示された本発明の実施形態のみに限定されるものではなく、特許請求の範囲で示された本発明と同等の技術的範囲に包含されるあらゆる形態も本発明に含まれるものと解釈される必要がある。
【０３０２】
【発明の効果】
以上説明した通りに構成される本発明によれば、以下の効果を奏する。
すなわち、本発明に係る回転インタポレータキー値データ符号化／復号化方法によれば、各キーフレーム間の回転変換間の回転変換の変量を示す回転差分値を符号化することによって、符号化される連続されたキー値データ間のデータの冗長性を効率よく減少させることができる。
【０３０３】
また、本発明に係るキー値データ符号化／復号化方法によれば、元のキー値データによるオブジェクトの回転方向が量子化誤差によって反対に復元されることを訂正することができる。
【０３０４】
また、本発明に係るキー値データ符号化／復号化方法によれば、クォータニオンで表されるキー値データの成分のうち小さな第２成分値から第４成分値のみを符号化し、第１の成分値が実数に復元さるべく訂正された第２の成分値から第４の成分値を用いて復元することによって、符号化に必要なデータの大きさを減少させることができる。
【図面の簡単な説明】
【図１】  回転インタポレータノードで表されたアニメーションデータの、３次元球の表面上の時間による２次元軌跡を示す図面である。
【図２】  線形ＤＰＣＭ及びエントロピ符号化を用いるＭＰＥＧ−４  ＰＭＦＣの符号化器の構成を示すブロック図である。
【図３】  線形ＤＰＣＭ及びエントロピ符号化を用いるＭＰＥＧ−４  ＰＭＦＣの復号化器の構成を示すブロック図である。
【図４】  本発明の望ましい第１実施形態に含まれるキー値データ符号化装置の構成を示すブロック図である。
【図５】  本発明の望ましい第１実施形態に含まれるキー値データ符号化方法を説明するフローチャートである。
【図６】  図６（Ａ）は回転差分値の各成分のＰＤＦの典型的な分布を示す図面であり、図６（Ｂ）は本発明の非線形量子化に用いられるアークタンジェント曲線を示す図面である。
【図７】  図７（Ａ）は本発明の望ましい実施形態に含まれる量子化器から出力された回転差分データの一例を示す図面であり、図７（Ｂ）は図７（Ａ）に示す差分データに線形ＤＰＣＭ演算が行われた結果を示す図面である。
【図８】  図７（Ｂ）に示す線形ＤＰＣＭ演算された差分データに循環ＤＰＣＭ演算を行った結果を示す図面である。
【図９】  エントロピ符号化に用いられるＳｉｇｎｅｄＡＡＣ（）関数の一例を示す図面である。
【図１０】  Ｂはエントロピ符号化に用いられるＵｎａｒｙ  ＡＡＣ（）関数の一例を示す図面である。
【図１１】  回転差分値を用いてクォータニオン回転変換値を符号化するとき、発生する回転方向誤差を説明する図面である。
【図１２】  本発明の望ましい第２実施形態に係る回転ＤＰＣＭ演算部の構成を示すブロック図である。
【図１３】  図１２に示す回転方向誤差計算器の構成を示すブロック図である。
【図１４】  本発明の望ましい第２実施形態に含まれる回転ＤＰＣＭ演算方法を説明するフローチャートである。
【図１５】  図１４に示す回転方向誤差計算器、回転方向誤差検出部、及び回転方向訂正部の動作を説明するフローチャートである。
【図１６】  本発明の望ましい第３実施形態に含まれる符号化装置に含まれる量子化器の構成を示すブロック図である。
【図１７】  第３実施形態に係る量子化器の処理過程を説明するためのフローチャートである。
【図１８】  本発明の望ましい実施形態に含まれるキー値データ復号化方法を説明するためのフローチャートである。
【図１９】  本発明の望ましい実施形態に含まれるキー値データ復号化方法を説明するためのフローチャートである。
【図２０】  エントロピ復号化器に入力されるビットストリームのデータ構造を示す図面である。
【図２１】  本発明に係るキー値データ復号化装置を具現するプログラムコードの一例を、ＳＤＬ言語形式で具現した例を示す図である。
【図２２】  本発明に係るキー値データ復号化装置を具現するプログラムコードの一例を、ＳＤＬ言語形式で具現した例を示す図である。
【図２３】  本発明に係るキー値データ復号化装置を具現するプログラムコードの一例を、ＳＤＬ言語形式で具現した例を示す図である。
【図２４】  本発明に係るキー値データ復号化装置を具現するプログラムコードの一例を、ＳＤＬ言語形式で具現した例を示す図である。
【図２５】  本発明に係るキー値データ復号化装置を具現するプログラムコードの一例を、ＳＤＬ言語形式で具現した例を示す図である。
【図２６】  元のアニメーション経路と復元されたアニメーション経路間の誤差を計算する方法の一例を説明する図面である。
【図２７】  本発明に係るキー値データ符号化方法と従来のキー値データ符号化方法による性能とを比較して示す図面である。
【符号の説明】
３００回転ＤＰＣＭ演算部
３１０  第１クォータニオン乗算器
３４０  量子化器
３５０  逆量子化器
３７０  第２クォータニオン乗算器
３９０  遅延器
４００  循環ＤＰＣＭ演算部
４５０  エントロピ符号化器
５００  キー値ヘッダ符号化器
【図１】
0004205426.tif 000097
【図２】
0004205426.tif 000098
【図３】
0004205426.tif 000099
【図４】
0004205426.tif 000100
【図５】
0004205426.tif 000101
【図６】
0004205426.tif 000102
【図７】
0004205426.tif 000103
【図８】
0004205426.tif 000104
【図９】
0004205426.tif 000105
【図１０】
0004205426.tif 000106
【図１１】
0004205426.tif 000107
【図１２】
0004205426.tif 000108
【図１３】
0004205426.tif 000109
【図１４】
0004205426.tif 000110
【図１５】
0004205426.tif 000111
【図１６】
0004205426.tif 000112
【図１７】
0004205426.tif 000113
【図１８】
0004205426.tif 000114
【図１９】
0004205426.tif 000115
【図２０】
0004205426.tif 000116
【図２１】
0004205426.tif 000117
【図２２】
0004205426.tif 000118
【図２３】
0004205426.tif 000119
【図２４】
0004205426.tif 000120
【図２５】
0004205426.tif 000121
【図２６】
0004205426.tif 000122
【図２７】
0004205426.tif 000123