(57)【要約】【課題】  キーデータを効率よく圧縮すること。【解決手段】  本発明の符号化装置は、入力された差分データの正数側の範囲及び負数側の範囲に応じて、正数側の範囲を半分に分け、上位範囲に位置する差分データを負数に変換するディバイド演算を行った後、演算の行われた差分データの範囲に応じて、負数領域に位置した差分データの範囲を狭めるディバイド-アップ演算または正数領域に位置した差分データの範囲を狭めるディバイド-ダウン演算を行って入力された差分データの範囲を狭めるＤＮＤ演算を所定回数行うＤＮＤ演算部と、ＤＮＤ演算された差分データに対して差分データの範囲を正数側または負数側に移動させるシフト-アップ演算を行うシフト-アップ演算部と、ＤＮＤ演算された差分データまたはシフト-アップ演算された差分データを選択的に出力する差分データ選択部、及び差分データ選択部において選択された差分データをエントロピ符号化するエントロピ符号化器を備える。【選択図】  図２
2005348395.tif 000002
【特許請求の範囲】
【請求項１】
キーフレームの時間軸上の位置情報であるキーデータを符号化する符号化装置であって、
入力された全体キーデータのうちキーデータが線形に増える領域を識別して符号化する線形キー符号化器と、
前記線形キー符号化器から入力され、且つ、２進数の体系で表わされた線形キー領域の開始キーデータ及び終了キーデータを１０進数の体系の実数に変換する実数変換部と、
前記全体キーデータのうち前記線形キー領域が除かれたキーデータを入力され、入力されたキーデータを所定の量子化ビットで量子化する量子化器と、
前記量子化されたキーデータに所定の演算を行ってエントロピ符号化するエントロピ符号化部と、
前記線形キー符号化器から線形キーデータ領域に含まれるキーデータの数を入力され、前記実数変換部から変換された線形キー領域の開始キーデータ及び終了キーデータを入力されてキーヘッダとして符号化するキーヘッダ符号化器と、を備えることを特徴とする符号化装置。
【請求項２】
量子化誤差が最小化可能に前記量子化器に入力されるキーデータの最大値及び最小値を調整して前記量子化器に出力する量子化誤差最小化部をさらに備え、前記量子化器は、前記量子化誤差最小化部から入力された最大値及び最小値を用いて入力されたキーデータを所定の量子化ビットで量子化することを特徴とする請求項１に記載の符号化装置。
【請求項３】
キーフレームの時間軸上の位置情報であるキーデータを符号化したビットストリームを復号化する復号化装置であって、
入力されたビットストリームから符号化されたキーデータの復号化に必要なキーヘッダ情報を復号化するキーヘッダ復号化器と、前記ビットストリームをエントロピ復号化して量子化されたキーデータを出力するエントロピ復号化部と、
１０進数の体系に符号化された線形キーデータ領域の開始キーデータ及び終了キーデータと前記量子化されたキーデータを逆量子化するのに用いられる最大値及び最小値とを前記キーヘッダ復号化器から入力され、２進数の体系に変換して出力する実数逆変換部と、
前記最大値及び最小値を用いて前記量子化されたキーデータを逆量子化し、復号化されたキーデータを出力する逆量子化器と、
前記実数逆変換部から線形キー領域の開始キーデータ及び終了キーデータを入力され、線形キーデータを復号化して前記逆量子化器から出力されたキーデータに加える線形キー復号化器と、を備えることを特徴とする復号化装置。
【請求項４】
キーフレームの時間軸上の位置情報であるキーデータを符号化する符号化方法であって、
符号化すべき全体キーデータのうちキーデータが線形に増える線形キー領域を識別して符号化する線形キー符号化段階と、
２進数の体系で表わされた前記線形キー領域の開始キーデータ及び終了キーデータを１０進数の体系の実数に変換する実数変換段階と、
前記全体キーデータのうち前記線形キー領域が除かれたキーデータを所定の量子化ビットで量子化する量子化段階と、
前記量子化されたキーデータに所定の演算を行ってエントロピ符号化するエントロピ符号化段階と、
前記線形キー領域に含まれるキーデータの数、及び前記変換された線形キー領域の開始キーデータ及び終了キーデータをキーヘッダとして符号化するキーヘッダ符号化段階と、を含むことを特徴とする符号化方法。
【請求項５】
前記量子化段階は、
量子化誤差が最小化可能に前記量子化すべきキーデータの最大値及び最小値を調整する量子化誤差最小化段階をさらに含み、前記量子化誤差最小化段階において調整された前記最大値及び最小値を用いて量子化すべきキーデータを所定の量子化ビットで量子化することを特徴とする請求項４に記載の符号化方法。
【請求項６】
キーフレームの時間軸上の位置情報であるキーデータを符号化したビットストリームを復号化する復号化方法であって、
前記ビットストリームから符号化されたキーデータの復号化に必要なキーヘッダ情報を復号化するキーヘッダ復号化段階と、
前記ビットストリームをエントロピ復号化し、量子化されたキーデータを生成するエントロピ復号化段階と、
１０進数の体系に符号化された線形キーデータ領域の開始キーデータ及び終了キーデータと前記量子化されたキーデータを逆量子化するのに用いられる最大値及び最小値とを前記キーヘッダ復号化器から入力されて２進数の体系に変換する実数逆変換段階と、
前記最大値及び最小値を用いて前記量子化されたキーデータを逆量子化し、復号化されたキーデータを生成する逆量子化段階と、
前記線形キー領域の開始キーデータ及び終了キーデータを用いて線形キーデータを復号化し、前記逆量子化されたキーデータに加える線形キー復号化段階と、を含むことを特徴とする復号化方法。
【請求項７】
請求項６に記載の復号化方法をコンピュータにて読取り可能で且つ、実行可能なプログラムコードにて記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キーデータを符号化して復号化する装置及び方法に関する。具体的には、キーデータの線形に増える領域を処理することで符号化効率を高める符号化方法及び装置と、符号化されたキーデータを復号化する方法及び装置とに関する。
【背景技術】
【０００２】
３次元表現技法は、３次元コンピュータゲームやコンピュータシステムの仮想現実環境においてひろく用いられている。３次元アニメーションを表わす手段としては、仮想現実モデリング言語（ＶＲＭＬ）がある。
【０００３】
ＶＲＭＬ及びＭＰＥＧ−４のＢＩＦＳ（Binary Format for Scene）は、キーフレーミング方式に基づくアニメーション表現方式を支援する。このアニメーション表現方式では、所定のキーフレームが任意の時間軸上において決められ、各キーフレーム間のアニメーションデータは線形補間法により補間される。この方式において用いられるキーフレームは、インタポレータノードにより定義され、インタポレータノードは、与えられた範囲（−∞〜＋∞）の実数（floating point number）値として表わされ、キーフレームの時間軸上の位置を示すキーデータと、該当キーにおいてキーフレームの属性及び動き情報などを示すキー値データとによりフィールドを構成する。
【０００４】
一方、区分（piecewise）線形補間特性を有するキーフレーミング方法により実際に動く物体と類似したスムーズなアニメーションを具現するためには、インタポレータノードを通じて相当のキーフレーム情報が供給されなければならず、これは、コスト面及び効率面で深刻な問題を招く。キーフレーミング方法がオフライン上において用いられる時、莫大な量の３次元アニメーションデータを記憶するための大容量の記憶機器が必要である。キーフレーミング方法がオンライン上において用いられる時には、大容量の記憶装置だけではなく、サーバから端末機へと３次元アニメーション情報を伝送するために高速の大容量の伝送線路が要され、伝送エラーが生じる可能性が高まるに伴い、データの信頼性も落ちてしまう。このため、インタポレータノードデータの量を減らし得る効率的な圧縮及び符号化方法が望まれる。
【０００５】
ＭＰＥＧ−４のＢＩＦＳは、アニメーションデータを符号化するための２種の方法を提案する。一つは、量子化だけでアニメーションデータを符号化するＢＩＦＳ−Ｑ方式であり、他の一つは、予測ＭＦフィールド符号化（ＰＭＦＣ）方法と呼ばれる、データの差を符号化するＤＰＣＭ方法である。ＢＩＦＳ−Ｑは、量子化だけを用いるため、効率的な符号化方法であるとは言えず、ＰＭＦＣは、ＤＰＣＭを行った後にデータ冗長性を減らすエントロピ符号化を行うので、ＢＩＦＳ−Ｑより効率的である。キーに対するＰＭＦＣの符号化及び復号化器が図１に示してある。しかし、ＰＭＦＣは、エントロピ符号化に先立ってＤＰＣＭのみを行うだけであって、キーの性質や相関関係を全く考慮しないため、アニメーションデータの符号化の上であまり効率的ではない。
【０００６】
図１を参照すれば、入力キーデータ１０５は、インタポレータノードから符号化装置１００に入力される。量子化器１１０は、入力キーデータを受け取り、データを整数値で量子化する。ＤＰＣＭプロセッサ１１５は、量子化されたキーデータを受け取って差分データを生成する。エントロピ符号化器１２０は、差分データを受け取り、シンボル発生の可能性に対してビット間冗長性を除去し、圧縮されたビットストリーム１２５を生じる。図１の符号化装置１００により生じたビットストリーム１２５は、符号化装置１５０のエントロピ復号化器１５５に入力されてエントロピ復号化され、エントロピ復号化された差分データは、逆ＤＰＣＭプロセッサ１６０により量子化された差分データとして出力され、逆量子化器１６５は、量子化されたキーデータを入力されて逆量子化を行い、復号化されたキーデータを出力する。
【０００７】
しかしながら、前述したような構造を有する符号化装置１００は、キーの性質を考慮しておらず、エントロピ符号化に先立ってＤＰＣＭのみを行う。このため、高い圧縮率の効率的な符号化が達成し難い。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明が解決しようとする第１の技術的な課題は、キーデータの性質を考慮してデータ冗長性を除去することにより、高効率のアニメーションキーデータの圧縮が可能な符号化装置及び方法を提供するところにある。
【０００９】
本発明が解決しようとする第２の技術的な課題は、前記符号化装置及び方法により符号化されたビットストリームを復号化する装置及び方法を提供するところにある。
【課題を解決するための手段】
【００１０】
前記技術的課題を達成するために、本発明の符号化装置は、入力された全体キーデータのうちキーデータが線形に増える領域を識別して符号化する線形キー符号化器と、前記線形キー符号化器から入力され、且つ、２進数の体系で表わされた線形キー領域の開始キーデータ及び終了キーデータを１０進数の体系の実数に変換する実数変換部と、前記全体キーデータのうち前記線形キー領域が除かれたキーデータを入力され、入力されたキーデータを所定の量子化ビットで量子化する量子化器と、前記量子化されたキーデータに所定の演算を行ってエントロピ符号化するエントロピ符号化部と、前記線形キー符号化器から線形キーデータ領域に含まれるキーデータの数を入力され、前記実数変換部から変換された線形キー領域の開始キーデータ及び終了キーデータを入力されてキーヘッダとして符号化するキーヘッダ符号化器と、を備える。
【００１１】
前記技術的課題を達成するために、本発明の復号化装置は、入力されたビットストリームから符号化されたキーデータの復号化に必要なキーヘッダ情報を復号化するキーヘッダ復号化器と、前記ビットストリームをエントロピ復号化して量子化されたキーデータを出力するエントロピ復号化部と、１０進数の体系に符号化された線形キーデータ領域の開始キーデータ及び終了キーデータと前記量子化されたキーデータを逆量子化するのに用いられる最大値及び最小値とを前記キーヘッダ復号化器から入力され、２進数の体系に変換して出力する実数逆変換部と、前記最大値及び最小値を用いて前記量子化されたキーデータを逆量子化し、復号化されたキーデータを出力する逆量子化器と、前記実数逆変換部から線形キー領域の開始キーデータ及び終了キーデータを入力され、線形キーデータを復号化して前記逆量子化器から出力されたキーデータに加える線形キー復号化器と、を備える。
【００１２】
また、前記技術的課題を達成するために、本発明の符号化方法は、符号化すべき全体キーデータのうちキーデータが線形に増える線形キー領域を識別して符号化する線形キー符号化段階と、２進数の体系で表わされた前記線形キー領域の開始キーデータ及び終了キーデータを１０進数の体系の実数に変換する実数変換段階と、前記全体キーデータのうち前記線形キー領域が除かれたキーデータを所定の量子化ビットで量子化する量子化段階と、前記量子化されたキーデータに所定の演算を行ってエントロピ符号化するエントロピ符号化段階と、前記線形キー領域に含まれるキーデータの数、及び前記変換された線形キー領域の開始キーデータ及び終了キーデータをキーヘッダとして符号化するキーヘッダ符号化段階と、を含む。
【００１３】
また、前記技術的課題を達成するために、本発明の復号化方法は、ビットストリームから符号化されたキーデータの復号化に必要なキーヘッダ情報を復号化するキーヘッダ復号化段階と、前記ビットストリームをエントロピ復号化し、量子化されたキーデータを生成するエントロピ復号化段階と、１０進数の体系に符号化された線形キーデータ領域の開始キーデータ及び終了キーデータと前記量子化されたキーデータを逆量子化するのに用いられる最大値及び最小値とを前記キーヘッダ復号化器から入力されて２進数の体系に変換する実数逆変換段階と、前記最大値及び最小値を用いて前記量子化されたキーデータを逆量子化し、復号化されたキーデータを生成する逆量子化段階と、前記線形キー領域の開始キーデータ及び終了キーデータを用いて線形キーデータを復号化し、前記逆量子化されたキーデータに加える線形キー復号化段階と、を含む。
【００１４】
本発明は、キーデータを符号化するに際し、キーデータの性質を用いるために、まず、キーデータの散布度を測定する。上述したように、キーデータは、時間軸上のキーフレームの位置を示すため、最初のキーフレームを示すキーデータから最後のキーフレームを示すキーデータまでキーデータ値は単調増加する。このため、第１次のＤＰＣＭを行った後の差分データはいずれも正数値を有し、第２次のＤＰＣＭを行った後には正数値または負数値を有する。
【００１５】
一般に、キーデータの最大値と最小値との間の範囲が狭いほど重なる値が多くなり、重なる値が多いほどエントロピ符号化器の圧縮率が高まる。このような性質を用いた本発明の符号化方法は、キーデータの範囲を狭めた後にエントロピ符号化を行う。キーデータの範囲を狭めるために、最小散布度を生成するＤＰＣＭ及びＤＮＤ次数、及び該当次数における演算結果が用いられる。キーデータの散布度が小さいほどキーデータ冗長性が高まる。
【発明の効果】
【００１６】
上述した本発明のキーデータ符号化及び復号化方法、並びに装置は、ＤＰＣＭ演算のみを行ってキーデータを符号化する従来の符号化及び復号化装置とは異なって、キーデータの線形に増える領域を処理することによって、キーデータの符号化効率を大幅に改善した。よって、本発明によれば、３次元アニメーションの記憶空間を大幅に縮めることができ、高速のアニメーションデータ伝送が可能となる。
【発明を実施するための最良の形態】
【００１７】
以下、添付した図面に基づき、本発明の好ましい実施の形態を説明する。
図２は、本発明の好ましい実施の形態による符号化器の構成を示す図である。
【００１８】
本発明の符号化器は、キーヘッダ符号化器２７０及びキーデータ符号化器を備える。また、キーデータ符号化器は、線形キー符号化器２００、量子化器２１０、ＤＰＣＭ処理部２２０、シフト部２３０、フォルド処理部２４０、ＤＮＤ処理部２５０及びエントロピ符号化器２６０を備える。
【００１９】
線形キー符号化器２００は、全体のキーデータの範囲においてキーデータが線形に増える領域を識別して符号化する。量子化器２１０は、量子化誤差を最小化する方法を用いて入力されたキーデータを量子化する。ＤＰＣＭ処理部２２０は、量子化されたキーデータを受け取り、キーデータの差分データを生成する。シフト部２３０は、全ての差分データから頻度数が最も高い差分データを引く。フォルド処理部２４０は、全ての差分データを正数の領域または負数の領域に移動させる。ＤＮＤ処理部２５０は、ディバイド、ディバイド-アップ、及びディバイド-ダウンの３種の演算を選択的に行ってキーデータの差分データの範囲を狭める。キーデータに対するエントロピ符号化器２６０は、ビットプレイン単位に差分データを符号化するSignedAAC及びUnsignedAAC関数を用いて差分データを符号化する。
【００２０】
以下、図９及び図１０をさらに参照し、本発明の好ましい実施の形態によるキーデータ符号化方法を説明する。図９及び図１０は、本発明のキーデータ符号化方法を示すフローチャートである。
【００２１】
キーデータが符号化器に入力されれば、キーデータの総数及び各キーデータの桁数などの情報はキーヘッダ符号化器２７０に入力されて符号化され、入力されたキーデータは線形キー符号化器２００において線形キー領域、すなわち、一定の時間間隔をおいてキーフレームが存在してキーデータが同じ差を有し、キーデータが線形に変わる領域の存否を検索し、検索された線形領域を先に符号化する（Ｓ３０００）。
【００２２】
３Ｄｍａｘ、Ｍａｙａなどの有名な３次元アプリケーションソフトウェアは、特定の領域が一定の時間間隔を有するキーを用い、キーフレームに基づくアニメーションを生成する。この場合、線形キーデータ領域は、線形領域が始まるキーデータ、終わるキーデータ及び中間に存在するキーフレームの数さえ分かれば簡単にキーデータを符号化できるので、インタポレータにおいて特定領域のキーの符号化のために線形予測を用いることは極めて有用である。
【００２３】
線形予測に用いられる数式は、下記式１の通りである。
【数１】
2005348395.tif 000003
【００２４】
ここで、ｔSは部分的に線形である領域が始まるキーのデータを示し、ｔEは、部分的に線形である領域が終わるキーのデータを示し、Ｓは、ｔSのインデックスを、Ｅは、ｔEのインデックスを各々示す。第Ｓ番目のキーデータ及び第Ｅ番目のキーデータに対応する特定の領域において前記式１により線形的に予測されたキーデータと実際のキーデータとの誤差は、下記式２により計算できる。
【数２】
2005348395.tif 000004
【００２５】
もし、前記式２により計算された誤差値のうち最大誤差値が所定の臨界値以下であれば、ｔiは［ｔS，ｔE］区間及び所定の誤差内において類似線形であると言える。最大誤差値及び特定の領域が類似線形であるか否かは、下記式３により決められる。
【数３】
2005348395.tif 000005
【００２６】
もし、
2005348395.tif 000006
であれば、ｔiは、［ｔS，ｔE］区間において類似線形である。ここで、nBitsは符号化に用いられる符号化ビット数を示す。
【００２７】
線形キー符号化器２００は、部分的に線形である領域を見つけると、領域の開始点のキーデータ及び終了点のキーデータを実数変換部２０５に出力し、線形キー領域に含まれるキーの数はキーヘッダ符号化器２７０に出力して符号化する。このように、線形符号化を用いることにより、符号化するデータの量を大いに低減できるということが分かる。開始キーデータ及び終了キーデータは、実数変換部２０５において後述する実数変換過程により符号化される。
【００２８】
実数変換部２０５は、開始キーデータ及び終了キーデータを符号化するために２進数の体系で表わされたキーデータを１０進数の体系に変換する。
【００２９】
コンピュータは、実数を３２ビットの２進数の形で記憶する。実数が２進数の形で与えられれば、実数変換部２０５は、実数を１０進数の体系の仮数及び指数に変換する。すなわち、下記式４のように変換される。
【数４】
2005348395.tif 000007
【００３０】
例えば、実数１２．３４をコンピュータにて２進数の形で表わせば、下記の通りである。
2005348395.tif 000008
1: 符号
2: ２進数の体系における仮数
3: ２進数の体系における指数
【００３１】
この数を前記式４により１０進数で表わせば、下記の通りである。
2005348395.tif 000009
1: 符号
2: １０進数の体系における仮数
3: １０進数の体系における指数
【００３２】
１０進数の体系の仮数及び指数をビットストリームに含めるためには、各々が必要とするビット数を計算しなければならない。まず、指数は−３８〜３８の範囲の値を有するため、指数は符号を含んで７ビットで表わせる。また、仮数は、桁数に応じて必要なビットの数が決められる。仮数の値及びこれに必要なビット数（但し、符号ビットは除く。）を下記表１に示す。
【表１】
2005348395.tif 000010
【００３３】
一方、前記のような過程により検索されて変換された線形キー領域の開始キーデータ及び終了キーデータは、図１１及び図１２に示されたような符号化過程により符号化され、キーヘッダ符号化器２７０に出力されてビットストリームに記憶される。
【００３４】
図１１及び図１２は、実数変換部２０５が入力された２つの実数を符号化する過程を示す。図１１及び図１２を参照し、実数変換部２０５が変換された実数を符号化する過程を説明する。
【００３５】
実数変換部２０５は、線形キー符号化器２００から元のキーデータの桁数（original key digit）Ｋｄ、線形領域が始まるキーデータ（Start key）Ｓ、線形領域が終わるキーデータ（end key）Ｅを入力され、前記式４によりキーデータを変換する（Ｓ３０４０）。
【００３６】
実数変換部２０５は、まず、Ｓを符号化するが、Ｓの桁数がＫｄと異なるかを判断し、桁数が異なれば、Ｓの桁数を求めてキーヘッダ符号化器２７０に出力する（Ｓ３０４２）。この時、実数変換部２０５は、digit()関数を用いてＳの桁数を求める。
【００３７】
その後、実数変換部２０５は、Ｓの桁数が７より大きければ、所定のビット数を本発明では、ＩＥＥＥ標準７５４のfloating-point number方式により３２ビットを用い、Ｓの桁数がビットストリームに含まれるようにキーヘッダ符号化器２７０に出力する（Ｓ３０４３）。
【００３８】
一方、Ｓの桁数が０でなくて７より小さければ、実数変換部２０５は、Ｓの符号をキーヘッダ符号化器２７０に出力し（Ｓ３０４４）、Ｓの仮数の絶対値の符号化に必要なビット数を前記表１から求め、求められたビット数として仮数の絶対値をキーヘッダ符号化器２７０に出力する（Ｓ３０４５）。その後、Ｓの指数を求め、符号をキーヘッダ符号化器２７０に出力し、指数を所定のビット数として本発明の実施の形態では６ビットとしてキーヘッダ符号化器２７０に出力する（Ｓ３０４６）。このように、キーデータの変換により、ビットストリームに含まれるビット数は大幅に減る。
【００３９】
一方、Ｓの桁数が０であれば、開始キーデータの符号化過程は終わり、終了キーデータを変換するための過程へ進む。なぜならば、桁数が０であれば、実数は０を意味するため、それ以上の符号化過程が不要であるからである。
【００４０】
実数変換部２０５は、開始キーデータを変換して符号化した後に終了キーデータＥを変換する。Ｅの変換は、Ｓの変換と同じ過程を繰り返すが、単に、Ｅの指数がＳの指数と同じ値を有するか否かを判別し（Ｓ３０４７）、両値が同じであれば、これを示すフラグビットのみをキーヘッダ符号化器２７０に出力し、両値が相異なれば、フラグビット及びＥの指数をＳの指数と同じ方式によりキーヘッダ符号化器２７０に出力する（Ｓ３０４８）。
【００４１】
一方、入力キーデータにおいて線形領域を除いたキーデータは量子化器２１０に入力され、所定の量子化ビットサイズであるnKeyQbitにより量子化される。
【００４２】
しかしながら、復号化器において量子化されたキーデータを復号化して用いる時には、元のキーデータと量子化されたキーデータとの誤差により元のキーデータが完全に復元できない。したがって、本発明の量子化器２１０は、単に入力されるキーデータから最大値及び最小値を求め、求められた値を用いて量子化可能であるだけではなく、量子化誤差最小化部２１５を含んで、量子化誤差が最小化可能に修正された最大値及び最小値を用いて量子化できる。
【００４３】
量子化誤差最小化部２１５は、量子化誤差を最小化するために入力されたデータに対して予め量子化及び逆量子化を行い、量子化の誤差が最小となる量子化の範囲を制御する方法を用いる（Ｓ３１００）。
【００４４】
具体的に説明すれば、固定された量子化に用いられる最大値をMaxとし、調節される量子化に用いられる最小値をMinとした時、Xiを入力値、nQuantBitを量子化に用いられるビットとした時、
2005348395.tif 000011
は、各々下記式５により計算する。
【数５】
2005348395.tif 000012
【００４５】
誤差の和ｅiを減らす方法には２種類があるが、一つは誤差の和が最小となるまでMin値を調節することであり、他の一つは、下記の通りである。
【００４６】
まず、ΔXが入力データの基本ステップサイズであり、ｎが任意の整数であり、ｉが０平均乱数ノイズであるとした時、入力キーデータシーケンスXiをXi=(i+n)ΔX+εiのように表わされる量子化された値であると仮定する。
【００４７】
その後、di=Xi-Xi-1=ΔX+(εi-εi-1)であるとした時、Δ'x=E[di]であり、最小値Minは、Max-Δ'x＊(2nQuantBit−1)となる。
【００４８】
このような過程を通じて求められた量子化誤差を最小化するMin値は、Max値及び量子化器２１０に入力されてキーデータの量子化に用いられる。
【００４９】
量子化誤差が最小となる最大値Max及び最小値Minを受け取った量子化器２１０は、下記式６を用いてキーデータfKeyiの量子化を行う（Ｓ３２００）。
【数６】
2005348395.tif 000013
【００５０】
ここで、ｉは、量子化されたキーデータのインデックスを、nQKeyiは、量子化されたデータの整数配列を、fKeyiは、入力キーデータとしての実数配列を、fKeyMax及びfKeyMinは、量子化誤差最小化部２１５において受け取られた最大値Max及び最小値Minを、nKeyQBitは量子化ビットサイズを各々示す。一方、前記式６において用いられた関数floor(v)は実数ｖを入力され、ｖ以下の最大整数を出力する関数である。
【００５１】
一方、本発明の量子化器２１０は、前記量子化誤差を最小化するアルゴリズムを用いず、簡単に、入力されたキーデータのうち最大値fKeyMax及び最小値fKeyMinを求めて量子化を行うこともできる。
【００５２】
本発明の量子化過程を示す図１３を参照し、量子化過程を詳細に説明する。
【００５３】
量子化器２１０は、キーデータを入力され（Ｓ３２１０）、量子化誤差最小化部２１５から最大値及び最小値が入力されたか否かをチェックする（Ｓ３２２０）。
【００５４】
量子化器２１０は、量子化誤差最小化部２１５から最大値Max及び最小値Minが入力されたならば、量子化に用いる最大値fKeyMax及び最小値fKeyMinをMax及びMinとして設定し（Ｓ３２３０）、設定された最大値及び最小値を前記実数変換部２０５に出力する。量子化に用いられる最大値及び最小値は、前記実数変換過程を通じて変換され符号化されてキーヘッダ符号化器２７０に出力されることにより、復号化に利用可能に最大値及び最小値をキーヘッダに含める。
【００５５】
量子化器２１０は、量子化誤差最小化部２１５から入力された値がなければ、入力されたキーデータのうち最初のキーデータfKey0を最小値fKeyMinとして、そして最後のキーデータfKeyN-1を最大値fKeyMaxとして設定する（Ｓ３２４０）。
【００５６】
その後、量子化器２１０は、設定された最大値が１より小さく、且つ、最小値が０より大きいか否かを判断し（Ｓ３２５０）、そうでなければ、最大値及び最小値を前記実数変換部２０５に出力し、前記過程を通じて変換して符号化した後、キーヘッダ符号化器２７０に出力して復号化に利用可能に最大値及び最小値をキーヘッダに含める（Ｓ３２６０）。
【００５７】
一方、最大値及び最小値が第Ｓ３２５０段階の条件を満足すれば、最大値及び最小値を復号化に利用可能にキーヘッダデータに含めるか否かを示すフラグをチェックする（Ｓ３２７０）。もし、フラグが最大値及び最小値をキーヘッダに含めるように設定されていれば、前記第Ｓ３２６０段階を行って最大値fKeyMax及び最小値fKeyMinを符号化した後にキーヘッダ符号化器２７０に出力し、そうでなければ、量子化器２１０は、最大値及び最小値をキーヘッダに含めない。
【００５８】
最大値及び最小値をキーヘッダに含めない場合は、キーデータ符号化器及びキーデータ復号化器が互いに最大値を１として、且つ、最小値を０として設定して符号化及び復号化を行うことを規約したケースに当たるため、量子化器２１０は、最小値fKeyMinを０として、そして最大値fKeyMaxを１として各々設定する（Ｓ３２８０）。このように設定された量子化に用いられる最大値及び最小値は、既に復号化器に知られているため、別途にキーヘッダに含めない。
【００５９】
一方、量子化器２１０は、前記過程を通じて設定されたfKeyMax及びfKeyMinを前記式６に代入して入力されたキーデータを量子化し、量子化されたキーデータをＤＰＣＭ処理部２２０に出力する（Ｓ３２９０）。
【００６０】
量子化されたキーデータを受け取ったＤＰＣＭ処理部２２０は、所定回数のＤＰＣＭを行って最小の散布度が生成される次数及びイントラキーデータをキーヘッダ符号化器２７０に出力し、ＤＰＣＭ演算の行われたキーデータの差分データをシフト部２３０に出力する（Ｓ３３００）。
【００６１】
以下、図１４を参照し、ＤＰＣＭ処理過程を説明する。ＤＰＣＭ処理部２２０は、入力されたキーデータに対してまず所定の回数だけＤＰＣＭ演算を行い、ＤＰＣＭが行われた回数はＤＰＣＭ次数として記憶する（Ｓ３３１０）。本発明の好ましい実施の形態では、３回のＤＰＣＭ演算を行った。
【００６２】
その後、ＤＰＣＭ処理部２２０は、各次数のＤＰＣＭ演算の結果に対して散布度を計算する（Ｓ３３２０）。この時の散布度を示す統計値として分散、標準偏差、及び四分偏差などが用いられ、本発明の好ましい実施の形態では、四分偏差が散布度として用いられる。
【００６３】
各次数のＤＰＣＭ演算の結果に対する散布度が計算されば、ＤＰＣＭ処理部２２０は、散布度が最小となるＤＰＣＭ次数及び該当次数のＤＰＣＭ結果を選択し、ＤＰＣＭ演算の結果はシフト部２３０に出力し、ＤＰＣＭ次数、各次数のイントラキーデータ及びその他のＤＰＣＭ演算において必要な情報はキーヘッダ符号化器２７０に出力する（Ｓ３３３０）。但し、本発明の好ましい実施の形態では、キーの数が５より小さければ、１次ＤＰＣＭのみを行った。例えば、１次ＤＰＣＭが行われる時には、下記式７を用いてＤＰＣＭ演算を行った。
【数７】
2005348395.tif 000014
【００６４】
ここで、ｉは、量子化されたキーデータのインデックスを、nQKeyiは整数配列を、そしてｉは差分データを各々示す。
【００６５】
一方、ＤＰＣＭ処理部２２０は、選択されたＤＰＣＭの結果、及びＤＰＣＭされたキーデータの差分データを符号化する時に必要なビット数を計算し、所定の記憶場所（本発明の実施の形態では、nQStep＿DPCM）に記憶する（Ｓ３３４０）。但し、符号化に必要なビット数を計算する段階は、後述する符号化すべきキーデータを選択する段階において行っても良いということは当業者に取って自明である。
【００６６】
ＤＰＣＭ結果を受け取ったシフト部２３０は、入力された差分データのうち頻度数が最も高い差分データ（以下、モードと称する）を選択して全ての差分データからモードを引くことにより、符号化されるべきデータを０の周りに集中的に分布せしめて符号化に必要なビット数を減らす（Ｓ３４００）。
【００６７】
シフト演算は、量子化された全てのキーデータの差分データからモードnKeyShiftを引くことにより行われる。このようなシフト演算は、下記式８で表わされる。
【数８】
2005348395.tif 000015
【００６８】
ｉは、量子化されたキーデータのインデックスを示し、nQKeyiは、整数配列を示し、nKeyShiftは、モード値を示す。シフト演算が行われた後には、キーデータの差分データのうち頻度数が最も高い差分データは０となるので、符号化に必要なビット数を大幅に低減できる。
【００６９】
シフト演算が行われたキーデータは、フォルド処理部２４０及びＤＮＤ処理部２５０に出力され、モード値nKeyShiftは、キーヘッダ符号化器２７０に出力されてキーヘッダに含まれる。
【００７０】
シフトされたデータを受け取ったフォルド処理部２４０は、ＤＮＤ演算を行うための前処理段階としてフォルド演算を行い、フォルド演算されたキーデータをＤＮＤ処理部２５０に出力する（Ｓ３５００）。
【００７１】
フォルド演算は、０を中心として負数領域及び正数領域に様々に分布される差分データを正数領域または負数領域に集中させて差分データの範囲を狭めるためのものであり、この実施の形態では、下記式９によりフォルド演算を行って差分データの分布を正数領域に集中させた。
【数９】
2005348395.tif 000016
【００７２】
ここで、ｉは、量子化されたキーデータのインデックスを示し、nQKeyiは、整数配列を示す。フォルド演算により、シフトされたキーデータの差分データのうち正数データは正の偶数に、負数のデータは正の奇数に各々変換される。
【００７３】
フォルド処理部２４０は、フォルド演算が行われたデータを符号化する時に必要なビット数を計算して所定の記憶場所nQStep＿foldに記憶する。第Ｓ３３００段階と同じく、符号化に必要なビット数の計算は、後述するエントロピ符号化する差分データを選択する段階において行っても良いということは当業者に取って自明である。一方、フォルド処理部２４０においてフォルト演算が行われたデータは、ＤＮＤ処理部２５０に出力される。
【００７４】
ＤＮＤ処理部２５０は、エントロピ符号化の効率を高めるために、入力されたキーデータの差分データに対してＤＮＤ演算を所定の回数だけ行ってデータの範囲を狭める（Ｓ３６００）。
【００７５】
以下、図３を参照し、ＤＮＤ処理部２５０を説明する。 ＤＮＤ処理部は、ＤＮＤ演算を行うＤＮＤ演算部２５２、符号化ビット数に応じてエントロピ符号化すべき差分データを選択する第１の差分データ選択部２５４、第１の差分データ選択部においてＤＮＤ演算の行われた差分データが選択されれば、ＤＮＤ演算の行われた差分データに対してシフト-アップ演算を行うシフト-アップ演算部２５６、及びＤＮＤ演算された差分データ及びシフト-アップ演算された差分データのうち散布度が小さい差分データを選択してエントロピ符号化器２６０に出力する第２の差分データ選択部２５８を備える。
【００７６】
まず、ＤＮＤ演算部２５２において行われるＤＮＤ演算について説明する。
【００７７】
フォルド演算された差分データがＤＮＤ演算部２５２に入力されれば、入力された差分データは半分に分けられ、上位範囲に位置する差分データはディバイド関数によって負数領域に移動する。ディバイド関数は、下記式１０のように定義される。
【数１０】
2005348395.tif 000017
【００７８】
ここで、ｊは、入力された差分データのインデックスであり、nQKeyjは、整数配列を示し、nKeyMaxは、入力されたフォルド演算された差分データのうち最大値を示す。差分データの分布が全体差分データが占める範囲の境界領域に集中している場合、ＤＮＤ演算はデータの全体領域を大幅に狭める効果がある。
【００７９】
ディバイド演算後に散布度が計算されるが、この場合、最小限の符号化ビットサイズが選択されるように符号化に必要なビットサイズが散布度として用いられる。
【００８０】
ディバイド演算が行われた後、ディバイド演算と類似した他のＤＮＤ演算のディバイド-アップ演算またはディバイド-ダウン演算が行われるが、行われるべき演算はディバイド演算後のデータの正数側及び負数側の範囲によって決められる。
【００８１】
正数側の範囲の方が大きければ、下記式１１により定義されるディバイド-ダウン演算が行われる。
【数１１】
2005348395.tif 000018
【００８２】
一方、負数側の範囲の方が大きければ、下記式１２により定義されるディバイド-アップ演算が行われる。
【数１２】
2005348395.tif 000019
【００８３】
前記式において、ｊは、量子化されたキーデータのインデックスであり、nQKeyjは、整数配列であり、nKeyMaxは、nQKeyjの最大値であり、nKeyMinは、nQKeyjの最小値である。
【００８４】
以下、ＤＮＤ演算部２５２の演算過程を示す図１５を参照し、ＤＮＤ演算過程を説明する。
【００８５】
ＤＮＤ演算部２５２は、フォルド処理部２４０からキーデータの差分データが入力されれば、入力された差分データのうち最大値nKeyMax及び最小値nKeyMinを求める（Ｓ３６１０）。その後、ＤＮＤ演算部２５２は、最大値及び最小値の絶対値を比較し（Ｓ３６２０）、最大値が最小値の絶対値以上であれば、求められた最大値を現在のＤＮＤ演算次数の最大値として設定する（Ｓ３６２２）。
【００８６】
ＤＮＤ演算部２５２は、ＤＮＤ演算次数が１であるか否かをチェックし（Ｓ３６２４）、次数が１であれば、前記式１０に最大値nKeyMaxを代入してＤＮＤ演算部２５２に入力された差分データに対してディバイド演算を行う（Ｓ３６３０）。
【００８７】
ディバイド演算を行ったＤＮＤ演算部２５２は、符号化に必要なビットサイズを求めるための関数getQBit()を用い、ディバイド演算を行って狭まった差分データの範囲を符号化するために必要なビットサイズを測定する（Ｓ３６４０）。その後、現在のＤＮＤ演算次数が１であれば（Ｓ３６５０）、前記値をＤＮＤ演算後に最小符号化ビットサイズを示す値nQBitDNDに一旦記憶し、ＤＮＤ次数を１だけインクリメントする（Ｓ３６５５）。
【００８８】
その後、ＤＮＤ演算部２５２は、前記過程を再び行うが、第Ｓ３６２４段階において次数が１でなければ、前記式１１にnKeyMax値を代入してディバイド-ダウン演算を行う（Ｓ３６３４）。ＤＮＤ演算部２５２は、ディバイド-ダウン演算が行われた差分データの符号化に必要なビット数を計算し（Ｓ３６４０）、この値が以前の次数のＤＮＤ演算により記憶された符号化に必要な最小値nQBitDNDより小さければ（Ｓ３６５２）、ＤＮＤ演算後に符号化に必要な最小ビットサイズをこの値に代える（Ｓ３６５８）。
【００８９】
一方、第Ｓ３６２０段階において、最小値の絶対値が最大値より大きければ、当該次数の最大値を入力された最小値に更新し（Ｓ３６２３）、最小値を前記式１２に代入してディバイド-アップ演算を行う（Ｓ３６３８）。その後、ＤＮＤ演算部２５２は、ディバイド-アップ演算の行われた差分データの符号化に必要なビット数を計算し（Ｓ３６４０）、この値が以前の次数のＤＮＤ演算により記憶された符号化に必要な最小値nQBitDNDより小さければ（Ｓ３６５２）、ＤＮＤ演算後に符号化に必要な最小ビットサイズをこの値に代える（Ｓ３６５８）。
【００９０】
ＤＮＤ演算部２５２は、所定の回数となるまで前記過程を繰り返すが、ＤＮＤ演算を行う回数は可変的である。例えば、この実施の形態は、ＤＮＤ演算を行う回数を７回として設定した。ＤＮＤ演算部２５２は、符号化に必要な最小ビットサイズnQBitDND及びその時のＤＮＤ演算された差分データを第１の差分データ選択部２５４に出力し、その時の次数をキーヘッダ符号化器２７０に出力してビットストリームに含める。
【００９１】
第１の差分データ選択部２５４は、シフト演算された差分データ、フォルド演算された差分データ及びＤＮＤ演算された差分データを入力され、いかなる演算の結果をエントロピ符号化するかを決める。
【００９２】
図９及び図１０をさらに参照すれば、第１の差分データ選択部２５４は、ＤＮＤ演算後に符号化に必要な最小ビット数nQBitDNDがＤＰＣＭ演算後の符号化ビットサイズnQStep＿DPCM以上であれば（Ｓ３７００）、ＤＰＣＭ演算の結果を選択してシフト演算を行った後、シフトされた差分データをエントロピ符号化器２６０に出力してエントロピ符号化する（Ｓ３７１０）。この場合、ＤＮＤ次数は、−１として設定され、キーヘッダ復号化器２７０に出力されてキーヘッダに含まれる。
【００９３】
しかし、nQBitDNDがＤＰＣＭ後の符号化ビットサイズより小さいものの、フォルド演算後の符号化ビットサイズ以上であれば（Ｓ３７２０）、第１の差分データ選択部２５４は、フォルド演算された差分データをエントロピ符号化器２６０に出力してエントロピ符号化する（Ｓ３７３０）。この場合、ＤＮＤ次数は、０として設定され、キーヘッダ符号化器２７０に出力されてキーヘッダに含まれる。
【００９４】
もし、ＤＮＤ演算された後の差分データの符号化ビット数が最小であれば、第１の差分データ選択部２５４は、ＤＮＤ演算された差分データをシフト-アップ演算部２５６に出力し、シフト-アップ演算部２５６は、差分データを入力され、ＤＮＤ演算された差分データに対して第１の散布度を計算すると共に（Ｓ３７４０）、ＤＮＤ演算された差分データに対して下記式１３で定義されるシフト-アップ演算を行った後（Ｓ３８００）、シフト-アップ演算された差分データの第２の散布度を再び計算する（Ｓ３８１０）。
【数１３】
2005348395.tif 000020
【００９５】
ここで、ｊは、量子化されたキーデータの差分データのインデックスであり、nQKeyjは、整数配列であり、そしてnKeyMaxは、差分データのうち最大値を示す。
【００９６】
ＤＮＤ演算された差分データ及びシフト-アップ演算された差分データを入力された第２の差分データ選択部２５８は、第１の散布度及び第２の散布度を比較し（Ｓ３９００）、シフト-アップ演算後の第２の散布度がＤＮＤ演算後の第１の散布度より小さければ、シフト-アップ演算が行われた差分データをエントロピ符号化器２６０に出力してエントロピ符号化し（Ｓ３９１０）、ＤＮＤ演算に用いられた最大値nKeyMax及び最小値nKeyMin、そして、シフト-アップ演算に用いられた最大値nKeyMaxをキーヘッダ符号化器２７０に出力してキーヘッダに含める。
【００９７】
しかし、ＤＮＤ演算後の第１の散布度がシフト-アップ演算後の第２の散布度より小さければ、第２の差分データ選択部２５８は、ＤＮＤ演算が行われた差分データをエントロピ符号化器２６０に出力してエントロピ符号化し（Ｓ３９２０）、ＤＮＤ演算に用いられた最大値nKeyMax及び最小値nKeyMinのみがキーヘッダ符号化器２７０に出力される。本発明の好ましい実施の形態では、前記第１及び第２の散布度として標準偏差を用いた。
【００９８】
エントロピ符号化器２６０は、符号化すべき差分データの性質に応じて２種の関数演算を行って差分データを符号化する。例えば、ＤＰＣＭが行われてシフト演算が行われた差分データ及びディバイド演算が行われた差分データは、正数及び負数を共に有するため、差分データの符号を含む符号化を行い、フォルド演算された差分データ及びシフト-アップ演算された差分データは正数値のみを有するため、符号を含まない符号化を行う。
【００９９】
本発明の好ましい実施の形態では、符号を含む符号化関数としてencodeSignedAAC関数を用い、符号を含まない符号化関数としてencodeUnsignedAAC関数を用いて差分データを符号化する。
【０１００】
図１６は、encodeSignedAAC関数の一例を示す図面である。図１６を参照すれば、入力値が７４であり、この値に対する符号化ビット数が８であれば、この値の符号は０であり、この値の２進数は１００１０１０となる。符号及び全てのビットプレインは下記のような過程を通じて符号化される。
【０１０１】
第１の段階：２進数をＭＳＢからＬＳＢにビットプレイン単位に符号化する。
第２の段階：符号化中に現在符号化されるビットが０でないか否かをチェックする。
第３の段階：もし、最初の０ではない値であれば、２進数の現在符号化ビットを符号化した後に符号を符号化する。
第４の段階：２進数の残りのビットを符号化する。
【０１０２】
encodeUnsignedAAC関数は、符号無き値に対するコンテキストを用いて適応算術符号化ビットストリームに符号化する。これは、符号コンテキストがあるという点を除ければ、前記encodeSignedAAC関数の処理過程と類似している。
【０１０３】
図１７ないし図２６は、本発明の好ましい実施の形態による演算が行われた後のキーデータを示す図面である。図１７ないし図２６において、横軸は各キーデータのインデックスを示し、縦軸はキーデータの値を示す。
【０１０４】
図１７は、本発明の符号化器に入力された元のキーデータを示す図面である。図１７に示されたキーデータが量子化器２１０に出力されて９ビットの量子化ビットで量子化されれば、図１８に示されたように、量子化されたキーデータが得られる。量子化されたキーデータに対してＤＰＣＭを行えば、図１９のように、キーデータの差分データが得られる。
【０１０５】
その後、量子化されたキーデータの差分データを約７のモード値にシフトすれば、図２０に示されたように、キーデータの差分データが得られ、シフトされた差分データにフォルド演算を行えば、図２１に示されたように、いずれも正数に変換されたデータが得られる。
【０１０６】
フォルドされたデータにＤＮＤ演算を行ったデータを図２２ないし図２４に示す。
【０１０７】
フォルドされたデータに対してまずＤＮＤ演算のうちディバイド演算を行った後の差分データを図２２に示す。示されたように、正数側の範囲は０〜２８であり、負数側の範囲は０〜−２９であるため、負数側の範囲がより広い。したがって、図２２に示されたデータに対してディバイド-アップ演算が行われ、ディバイド-アップ演算の結果を図２３に示す。
【０１０８】
ディバイド-アップ演算によりキーデータの負数側の範囲は正数側の範囲に比べて相当狭まり、ＤＮＤの次の次数においてディバイド-アップ演算された差分データに対してディバイド-ダウン演算が行われる。図２４は、図２３の差分データに対してディバイド-ダウン演算を行った結果を示す図面である。一方、ディバイド-ダウン演算されたキーデータに対してシフト-アップ演算を行った結果を図２５に示す。
【０１０９】
前記図１７ないし図２３では、キーデータ及び差分データの範囲が次第に狭まるということが分かる。しかし、シフト-アップ演算結果を示す図２５及び図２４を比較してみれば、シフト-アップ演算後の符号化されるべき差分データの範囲がより広がったということが分かる。したがって、最終的に符号化すべきキーデータの差分データは、ディバイド-ダウン演算が行われた差分データであることが図２６から分かる。
【０１１０】
一方、キーヘッダ符号化器２７０において符号化されてキーヘッダに記憶される情報を説明する。
【０１１１】
符号化されるべきキーデータらが入力されれば、キーヘッダ符号化器２７０は、入力キーデータからキーデータの桁数及び符号化されるべきキーの総数を入力されて符号化する。その後、キーヘッダ符号化器２７０は、線形キー符号化器２００から線形キー符号化された線形キー領域の存否を示す情報及び線形キー領域のキーデータの数を入力され、実数変換部２０５から実数変換された線形キー領域の開始キーデータ及び終了キーデータを入力される。
【０１１２】
併せて、実数変換部２０５が量子化誤差最小化部２１５から量子化誤差が最小化となる最大値及び最小値を入力されて実数変換した場合には、変換された最大値及び最小値は逆量子化に利用可能に実数変換部２０５からキーヘッダ符号化器２７０に入力されてキーヘッダに含まれる。また、量子化に用いられた量子化ビットサイズもキーヘッダ符号化器２７０に入力されてキーヘッダに含まれる。
【０１１３】
また、キーヘッダ符号化器２７０は、ＤＰＣＭ処理部２２０からＤＰＣＭ演算次数及び各次数におけるイントラキーデータを入力され、シフト部２３０からシフト演算に用いられたモード値を入力され、ＤＮＤ処理部２５０からシフト-アップ演算が行われたか否か、散布度が最小となるＤＮＤ次数及び各ＤＮＤ次数における最大値及び最小値を入力される。
【０１１４】
最後に、キーヘッダ符号化器２７０は、エントロピ符号化器２６０から符号化に用いられた符号化ビット数を入力されてキーヘッダに符号化する。
【０１１５】
以上、本発明の好ましい実施の形態によるキーデータ符号化装置の一例を説明した。当該技術分野の通常の知識を有した者は、前記好ましい実施の形態による符号化装置の様々な変形実施の形態が存在するということが分かるであろう。以下、図４ないし図８を参照し、キーデータの符号化効率を高めるための好ましい実施の形態の変形実施の形態を説明する。一方、前記図２及び図３と同じ機能を行う構成要素には、同じ参照符号を使用した。
【０１１６】
図４を参照すれば、本発明の符号化装置の第２の実施の形態は、量子化器２１０、ＤＰＣＭ処理部２２０、シフト部２３０、フォルド処理部２４０、ＤＮＤ処理部２５０、及びエントロピ符号化器２６０を備える。
【０１１７】
本発明の符号化装置に入力されたキーデータは、まず、量子化器２１０に入力されて所定の量子化ビットで量子化される。量子化されたキーデータは、ＤＰＣＭ処理部２２０に入力され、ＤＰＣＭ処理部２２０は、キーデータにＤＰＣＭ演算を行って生成された差分データをシフト部２３０に出力する。シフト部２３０は、入力された差分データのうち頻度数が最も高い差分データ（モード）を求め、入力された差分データから前記モードを引くシフト演算を行ってフォルド処理部２４０に出力する。フォルド処理部２４０は、入力された差分データを正数領域または負数領域に変換してＤＮＤ処理部２５０に出力する。ＤＮＤ処理部２５０は、入力されたフォルド演算された差分データに対して前記ＤＮＤ演算を行い、シフト演算された差分データ、フォルド演算された差分データ、及びＤＮＤ演算された差分データのうち符号化に必要なビット数が最小となる差分データをエントロピ符号化器２６０に出力してキーデータを符号化することができる。この時、前記ＤＮＤ処理部２５０は、ＤＮＤ演算された差分データに対してシフト-アップ演算を行うことを省略でき、前記符号化器は、従来のキーデータ符号化装置と比較して顕著な符号化効率を示す。
【０１１８】
図５を参照すれば、本発明の符号化装置の第３の実施の形態は、量子化器２１０、ＤＰＣＭ処理部２２０、シフト部２３０、ＤＮＤ処理部２５０、及びエントロピ符号化器２６０を備える。
【０１１９】
本発明の符号化装置に入力されたキーデータは、まず、量子化器２１０に入力されて所定の量子化ビットで量子化される。量子化されたキーデータは、ＤＰＣＭ処理部２２０に入力され、ＤＰＣＭ処理部２２０は、キーデータに対してＤＰＣＭ演算を行って生成された差分データをシフト部２３０に出力する。シフト部２３０は、入力された差分データのうち頻度数が最も高い差分データ（モード）を求め、入力された差分データから前記モードを引くシフト演算を行ってＤＮＤ処理部２５０に出力する。ＤＮＤ処理部２５０は、シフトされた差分データに対して前記ＤＮＤ演算を行い、シフト演算された差分データ及びＤＮＤ演算された差分データのうち符号化に必要なビット数がより小さい差分データを選択し、ＤＮＤ演算された差分データが選択されたならば、ＤＮＤ演算された差分データに対してシフト-アップ演算を行い、ＤＮＤ演算された差分データ及びシフト-アップ演算された差分データのうち符号化に必要なビット数がより小さい差分データをエントロピ符号化器２６０に出力する。エントロピ符号化器２６０は、差分データに対してエントロピ符号化を行ってビットストリームを生成する。前記符号化器は、前記好ましい実施の形態の符号化装置においてフォルド演算過程を省略したが、前記構成だけでも従来のキーデータ符号化装置と比較して顕著な符号化効率を示す。
【０１２０】
図６を参照すれば、本発明の符号化装置の第４の実施の形態は、符号化装置にキーデータの差分データが入力される時、入力された差分データを符号化して出力する符号化装置を説明する。
【０１２１】
第４の実施の形態の符号化装置は、シフト部２３０、フォルド処理部２４０、ＤＮＤ処理部２５０、及びエントロピ符号化器２６０を備える。入力された差分データは、シフト部２３０において差分データのうち頻度数が最も高い差分データが引かれてフォルド処理部２４０に出力される。フォルド処理部２４０は、入力された差分データを正数領域または負数領域に変換してＤＮＤ処理部２５０に出力する。ＤＮＤ処理部２５０は、入力されたフォルド演算された差分データに対して前記ＤＮＤ演算を行い、シフト演算された差分データ、フォルド演算された差分データ、及びＤＮＤ演算された差分データのうち符号化に必要なビット数が最小となる差分データを選択する。ＤＮＤ処理部２５０においてシフトされた差分データまたはフォルド演算された差分データが選択された場合には、選択された差分データはエントロピ符号化器２６０に出力してキーデータを符号化することができる。一方、ＤＮＤ処理部２５０においてＤＮＤ演算された差分データを選択した場合には、ＤＮＤ演算された差分データに対してシフト-アップ演算を行い、ＤＮＤ処理部２５０は、ＤＮＤ演算された差分データ及びシフト-アップ演算された差分データのうち符号化に必要なビット数がより小さい差分データを選択してエントロピ符号化器２６０に出力する。エントロピ符号化器２６０は、入力された差分データをエントロピ符号化してビットストリームを生成する。第４の実施の形態の符号化装置もまた、従来の符号化装置と比較して高い符号化効率を示すということが分かる。
【０１２２】
図７に示された第５の実施の形態の符号化装置は、入力されたキーデータの差分データに対してＤＮＤ演算のみを行って符号化する。第５の実施の形態の符号化装置は、ＤＮＤ演算部２５２、シフト-アップ演算部２５６、差分データ選択部２５８ｂ及びエントロピ符号化器２６０を備える。
【０１２３】
入力されたキーデータの差分データは、ＤＮＤ演算部２５２において前記ＤＮＤ演算が所定回数行われてＤＮＤ演算された差分データは、シフト-アップ演算部２５６及び差分選択部に各々入力される。シフト-アップ演算部２５６は、入力されたＤＮＤ演算された差分データに対して前記シフト-アップ演算を行って差分データ選択部２５８ｂに出力し、差分データ選択部２５８ｂは、入力されたＤＮＤ演算された差分データ及びシフト-アップ演算された差分データの符号化に必要なビット数を比較して符号化に必要なビット数がより小さい差分データをエントロピ符号化器２６０に出力してキーデータのビットストリームを出力する。第５の実施の形態の符号化装置もまた、従来の符号化装置と比較して高い符号化効率を示すということが分かる。
【０１２４】
図８に示された第６の実施の形態の符号化装置は、入力差分データから線形キー領域を識別して符号化することにより、全体キーデータの符号化効率を高める符号化装置である。第６の実施の形態の符号化装置は、線形キー符号化器２００、実数変換部２０５、量子化器２１０、エントロピ符号化部２８０、及びキーヘッダ符号化器２７０を備える。
【０１２５】
キーデータが第６の実施の形態の符号化装置に入力されれば、線形キー符号化器２００は、入力されたキーデータのうちキーデータが線形に増える領域の存否を検索して線形キー領域として判断される領域の開始キーデータ及び終了キーデータを実数変換部２０５に出力し、入力キーデータのうち線形キー領域を除いたキーデータを量子化器２１０に入力する。量子化器２１０に入力されたキーデータは、所定のビットサイズで量子化されてエントロピ符号化部２８０に出力され、エントロピ符号化部２８０は、入力された量子化されたキーデータに対して所定の演算を行ってエントロピ符号化してビットストリームに出力する。
【０１２６】
一方、実数変換部２０５は、２進数の体系で表わされた線形キー領域の開始キーデータ及び終了キーデータを１０進数の体系に変換してキーヘッダ符号化器２７０に出力してビットストリームに含める。一方、第６の実施の形態は、前記量子化誤差最小化部２１５をさらに備えることもできる。
【０１２７】
図２７（ａ）及び図２７（ｂ）は、キーデータ及びキー値データを用いてアニメーションデータを符号化する過程を簡略に示す図面である。
【０１２８】
キー値のアニメーションの経路において、キー値符号化器は、近似化した経路を示す点の集合を見つける。この場合、多数のキー値がデクリメントされ、残りの点は、キー選択フラグにより表わされる。例えば、与えられたキー値曲線が図２７（ａ）の通りであり、４つの点が選択された時、キー選択フラグの配列は、図２７（ｂ）のような値を有する。そして、キー選択フラグは、エントロピ符号化器２６０により符号化され、キー選択フラグに当たるキー値データのみが符号化される。
【０１２９】
以下、図３５ないし図３９を参照し、前記符号化のためのプログラムコード及び各パラメータの意味の一例を説明する。プログラムコード及び各パラメータの意味は、ＳＤＬ言語の形で後述する。
【０１３０】
キーヘッダのプログラムコードは、図３５に示してある。図３５に示されたプログラムコードに用いられた各パラメータの意味を説明する。
【０１３１】
キーヘッダデータは、キーデータを復号化するために必要な情報である。キーヘッダの主たる情報は、キーの数、量子化ビット、イントラキーデータ、ＤＮＤヘッダ及び符号化に必要な実際のビット数である。nKeyQBitは、実数のキー値を復元する逆量子化に用いられる量子化ビットである。nNumKeyCodingBitは、キーデータの数を示すnNumberOfKeyのビットサイズを示す。nKeyDigitは、元のキーデータの最大重要桁数を示し、復号化された値の切り上げに用いられる。キーヘッダに線形キー領域に関する情報が含まれた場合、blsLinearKeySubRegionフラグが１として設定される。この場合、全体キーに含まれる所定のキー領域に含まれたキーは、blsLinearKeySubRegionフラグに追従する復号化されたヘッダ情報を用いて計算できる。bRangeFlagは、キーデータの範囲が０ないし１であるか否かを示す。もし、範囲が０ないし１でなければ、最小値及び最大値はKeyMinMaxから復号化される。KeyMinMaxクラスは、逆量子化のために最小値及び最大値を再構成する。各値は、仮数及び指数に分けられる。nBitSizeは、nQIntraKeyのビットサイズであり、nKeyShiftは、nKeyMaxの最初のビットサイズである。nQIntraKeyは、第１の量子化されたイントラデータの大きさである。これは、nQIntraKeyの符号を示すnQIntraKeySignと共に結合される。これは、残りの量子化されたキーデータを復元するためのベースとして用いられる。インタポレータ圧縮に用いられる全ての符号ビットにおいて、０は正数を、１は負数を各々意味する。nKDPCMOrderは、ＤＰＣＭ次数−１である。次数の範囲は、１ないし３である。量子化されたイントラデータの数は、ＤＰＣＭの次数と同じである。
【０１３２】
nkeyShiftは、符号ビットであるnKeyShiftSignと共にキーデータ復号化器のシフト量を示す整数である。これら両値は、bShiftFlagが１として設定されれば復号化される。nDNDOrderは、ＤＮＤ（Divide-and-Divide）の次数である。ＤＮＤは、キーデータ復号化器において説明する。もし、nDNDOrder値が７であれば、bNoDNDが復号化される。このブール値は、逆ＤＮＤが処理されるか否かを示す。nKeyMax及びnKeyMinは、連続した逆ＤＮＤ演算中にそれぞれ用いられる最大値及び最小値である。nKeyCodingBitは、キーデータの符号化に用いられるビットである。bSignedAACFlagは、ＡＡＣ復号化のためにいかなる復号化方法が用いられるかを示す。もし、値が０であれば、unsignedAAC復号化が行われる。そうでなければ、signedAAC復号化が行われる。bKeyInvertDownFlagは、nKeyInvertDownが用いられるのか否かを示すブール値である。nKeyInvertDownは整数値であり、これを超える全ての量子化されたキーデータを−１以下の負数値に反転させる。nKeyInvertDownが−１であれば、シフト-ダウン演算は行われない。
【０１３３】
図３６は、LinearKeyのプログラムコードを示す図面である。
【０１３４】
LinearKeyのパラメータの意味を説明すれば、nNumLinearKeyCodingBitは、線形に予測可能なキーの数を符号化するために必要なビットの数を示す値である。
【０１３５】
図３７は、KeySelectionFlagのプログラムコードを示す図面である。
【０１３６】
KeySelectionFlagに用いられたパラメータを説明すれば、keyFlagは、ブール配列で第ｉ番目のキーのキー値が符号化されたか否かを示す。nNumOfKeyValueは整数値であって、復号化されるキー値の数を示す。
【０１３７】
図３８は、KeyMinMaxのプログラムコードを示す図面である。
【０１３８】
KeyMinMaxに用いられたパラメータの意味を説明すれば、まず、bMinKeyDigitSameは、全体キーの最も高い重要桁数nKeyDigit及びキーの最大値の最も高い重要桁数が同じであるか否かを示す。nMinKeyDigitは、キーの最大値の最も高い重要桁数を示す。nMinKeyMantissaSignは、nMinKeyMantissaの符号を示す。nMinKeyMantissaは、キーの最小値の仮数をを示す。
【０１３９】
nMinKeyExponentSignは、nMinKeyExponentの符号を示す。nMinKeyExponentは、キーの最小値の指数を示す。
【０１４０】
fKeyMinは、キーの最小値を示す。nMaxKeyDigitSameは、全体キーの最も高い重要桁数nKeyDigit及びキーの最大値の最も高い重要桁数が同じであるかを示す。nMaxKeyDigitは、キーの最大値の重要桁数を示す。nMaxKeyMantissaSignは、nMaxKeyMantissaの符号を示す。nMaxKeyMantissaは、キーの最大値の仮数を示す。
【０１４１】
bSameExponentは、キーの最大値の指数がnMinKeyExponentと同じであるかを示す。nMaxKeyExponentSignは、nMaxKeyExponentの符号を示す。nMaxKeyExponentは、キーの最大値の指数を示す。fKeyMaxは、キーの最大値を示す。
【０１４２】
図３９は、Keyのプログラムコードを示す図面である。
【０１４３】
Keyに用いられたパラメータの意味を説明すれば、nQKeyはビットストリームから復号化される量子化されたキーデータを記憶した配列を示す。KeyContextは、nQKeyの大きさを読み込むのに用いられるコンテキストを意味する。KeySignContextは、nQKeyの符号を読み込むのに用いられるコンテキストを意味する。
【０１４４】
decodeUnsignedAACは、後述する与えられたコンテキストであって、適応的な算術符号化に対して符号無き復号化を行う関数である。decodeSignedAACは、後述する与えられたコンテキストであって、適応的な算術符号化に対して符号あり復号化を行う関数である。
【０１４５】
以下、図２８及び図３３を参照し、本発明の好ましい実施の形態による復号化装置及び方法を説明する。
【０１４６】
図２８は、本発明の好ましい実施の形態による復号化装置の構成を示すブロック図である。本発明の復号化器は、符号化されたビットストリームを受け取り、復号化されたキーデータにより再構成する。
【０１４７】
本発明の復号化器は、キーヘッダ復号化器３７０及びキーデータ復号化器の２部分を備える。また、キーデータ復号化器は、エントロピ復号化器３６０、逆ＤＮＤ処理部３５０、逆フォルド処理部３４０、逆シフト部３３０、逆ＤＰＣＭ処理部３２０、逆量子化器３１０、線形キー復号化器３００及び実数逆変換部３０５を備える。
【０１４８】
図３３は、本発明の好ましい実施の形態による復号化方法を説明するフローチャートである。
【０１４９】
まず、キーデータを圧縮したビットストリームは、キーヘッダ復号化器３７０及びエントロピ復号化器３６０に入力される。
【０１５０】
キーヘッダ復号化器３７０は、各復号化段階別に必要な情報を復号化して各段階に与えるが、キーヘッダ復号化器３７０において復号化される情報は各段階ごとに説明する（Ｓ４０００）。
【０１５１】
ビットストリームを入力されたエントロピ復号化器３６０は、キーヘッダ復号化器３７０から復号化すべき差分データの数と符号化に用いられたビット数、すなわち、復号化すべきビット数を入力され、ビットストリームをエントロピ復号化する（Ｓ４１００）。この時、復号化すべき差分データの数は、与えられたキーデータの数からＤＰＣＭ演算のイントラキーデータの数だけ引いた数となる。
【０１５２】
エントロピ復号化器３６０は、ビットストリームを復号化する時、ビットストリームに含まれた所定の情報（この実施の形態では、bSignedAACFlag）に基づき符号化された差分データが負数であるか、それとも正数であるかを識別し、負数であれば、decodeSignedAAC()関数を用いて復号化し、正数であれば、decodeUnsignedAAC()関数を用いて復号化する。このようにして復号化された差分データは、逆ＤＮＤ処理部３５０に送られる。
【０１５３】
本発明の好ましい実施の形態において、ビットストリームを復号化するための関数を具現するプログラムコードの一例は後述する。
【０１５４】
エントロピ復号化された差分データを受け取った逆ＤＮＤ処理部３５０は、キーヘッダ復号化器３７０からＤＮＤ次数及び各ＤＮＤ次数における最大値nKeyMaxを入力される。
【０１５５】
もし、ＤＮＤ次数が−１であれば、これは、符号化器がＤＮＤ演算された差分データの代わりにＤＰＣＭ演算されてシフトされた差分データをエントロピ符号化したことを示すため、逆シフト演算を行う過程へ直ちに進む。一方、ＤＮＤ次数が０であれば、これは、符号化器がＤＮＤ演算された差分データの代わりにフォルドされた差分データをエントロピ符号化したことを示すために、逆フォルド演算を行う過程へ直ちに進む。しかし、ＤＮＤ次数が０より大きければ、逆ＤＮＤ演算を行う（Ｓ４１５０）。
【０１５６】
まず、逆ＤＮＤ処理部３５０は、シフト-アップ演算の行われた差分データが符号化されたか否かを判断する（Ｓ４１７０）。本発明の好ましい実施の形態においては、ビットストリームに含まれたnKeyInvertDown値が０より大きいか否かをチェックすることにより、シフト-アップ演算の行われた差分データが符号化されたか否かを判断する。
【０１５７】
もし、シフト-アップ演算の行われていない差分データが符号化されたならば、逆ＤＮＤ処理部３５０は、逆ＤＮＤ演算を行う過程へ進む。しかし、シフト-アップ演算の行われた差分データが符号化されたならば、シフト-アップ演算により正数の領域に移動した差分データをさらに元の負数領域に戻す（Ｓ４２００）。本発明の実施の形態は、下記式１４で表わされるシフト-ダウン（以下、“インバート−ダウン”と同じ意味で使用する）演算を行ってシフト-アップ演算された差分データを復元する。
【数１４】
2005348395.tif 000021
【０１５８】
ここで、nKeyInvertDownは、シフト-アップ演算における最大値nKeyMaxと同じ値が用いられる。シフト-ダウン演算によりnKeyInvertDownを超える差分データは−１以下の負数値に変わる。
【０１５９】
シフト-ダウン演算の行われた差分デーに対して各ＤＮＤ次数における値に応じて逆ディバイド-ダウンまたは逆ディバイド-アップ演算が選択的に行われる。
【０１６０】
図３４をさらに参照し、この逆ＤＮＤ演算過程を説明すれば、逆ＤＮＤ処理部３５０は、符号化過程において行われたＤＮＤ演算の次数の回数だけ逆ＤＮＤ演算を行う。すなわち、逆ＤＮＤ処理部３５０は、逆ＤＮＤ次数の初期値をＤＮＤ次数として設定し、逆ＤＮＤ演算を行う都度１ずつデクリメントし、逆ＤＮＤ次数が１となるまで逆ＤＮＤ演算を行う。まず、逆ＤＮＤ処理部３５０は、各次数におけるnKeyMax値をチェックしてnKeyMax値が０以上であるか否かを判断する（Ｓ４３１０）。
【０１６１】
nKeyMax値が０より小さければ、符号化過程においてディバイド-アップ演算が行われた旨を意味するために、逆ＤＮＤ処理部３５０は、逆ディバイド-アップ演算を行って差分データの範囲を負数領域に広める（Ｓ４３２０）。本発明の好ましい実施の形態は、下記式１５のような逆ディバイド-アップ演算を用いた。
【数１５】
2005348395.tif 000022
【０１６２】
しかしながら、もし、nKeyMaxが０以上であれば、逆ＤＮＤ処理部３５０は、逆ＤＮＤ演算の次数が１であるか否かをチェックする。逆ＤＮＤ次数が１でなければ、符号化する時にディバイド-ダウン演算が行われた旨を意味するために、逆ＤＮＤ処理部３５０は、逆ディバイド-ダウン演算を行って差分データの範囲を正数領域に広める（Ｓ４３４０）。
【０１６３】
本発明の好ましい実施の形態は、下記式１６のような逆ディバイド-ダウン演算を用いた。
【数１６】
2005348395.tif 000023
【０１６４】
もし、nKeyMaxが０以上であり、且つ、逆ＤＮＤ演算の次数が１であれば、逆ＤＮＤ処理部３５０は、逆ディバイド演算を行うことにより逆ＤＮＤ演算を終える（Ｓ４３５０）。本発明の好ましい実施の形態は、下記式１７のような逆ディバイド演算を用いた。
【数１７】
2005348395.tif 000024
【０１６５】
逆ＤＮＤ演算の行われたキーデータの差分データは、逆フォルド処理部３４０に入力され、逆フォルド処理部３４０は、逆フォルド演算を行い、正数領域にのみ位置する差分データの範囲を正数及び負数に分離する（Ｓ４４００）。本発明の好ましい実施の形態は、下記式１８のような逆フォルド演算を用いた。
【数１８】
2005348395.tif 000025
【０１６６】
逆フォルドされた差分データは、逆シフト部３３０に出力され、逆シフト部３３０は、キーヘッダ復号化器３７０から符号化器に用いられたモードnKeyShiftを入力され、下記式１９のように入力されたnKeyMax差分データにモードを加える（Ｓ４５００）。
【数１９】
2005348395.tif 000026
【０１６７】
逆シフト部３３０から差分データを入力された逆ＤＰＣＭ処理部３２０は、キーヘッダ符号化器３７０からＤＰＣＭ次数を入力され、差分データを量子化されたキーデータに復元する（Ｓ４６００）。逆シフト部３３０は、下記式２０を用いてＤＰＣＭ次数だけ逆ＤＰＣＭ演算を行う。
【数２０】
2005348395.tif 000027
【０１６８】
ここで、ｉは、差分データ及びキーデータのインデックスを、ｖは整数配列を、delta(i)は差分データを各々示す。
【０１６９】
逆ＤＰＣＭ処理されて生成された量子化されたキーデータは、逆量子化器３１０に入力され、逆量子化器３１０は、キーヘッダ復号化器３７０から量子化ビットサイズnKeyQBit及び逆量子化に用いられる最大値及び最小値が量子化過程において実数変換部２０５により符号化されたか否かを入力され、下記式２１を用いて入力された量子化されたキーデータを逆量子化されたキーデータに変換する（Ｓ４７００）。
【数２１】
2005348395.tif 000028
【０１７０】
符号化器においてキーデータを量子化する時、量子化に用いられた最大値及び最小値が実数変換部２０５において変換されなかったならば、前記式２１のfKeyMin及びfKeyMaxは０及び１として各々設定される。しかし、量子化に用いられた最大値及び最小値が実数変換部２０５において変換されたならば、逆量子化に用いられる最大値及び最小値は、後述する実数逆変換部３０５において逆変換されて入力される最小値及び最大値が各々用いられる。
【０１７１】
上述した逆ＤＮＤ演算過程から逆量子化過程をプログラムコードにて具現した一例は後述する。
【０１７２】
一方、逆量子化器３１０から出力される復号化されたキーデータは、線形キー復号化器３００において復号化された線形キーデータに加えられて復号化されたキーデータを構成する。
【０１７３】
以下、線形キー復号化過程を説明する。
【０１７４】
キーヘッダ復号化器３７０は、ビットストリームからキーヘッダ情報を復号化して線形キーに関する情報があれば、線形キー領域の開始キー及び終了キーを復号化するために必要な情報を実数逆変換部３０５に出力し、線形キー復号化器３００に線形キーとして符号化されたキーの数を出力する。
【０１７５】
線形キー復号化に用いられる開始キー及び終了キー情報を入力された実数逆変換部３０５は。１０進数の体系で表わされた開始キー及び終了キーをさらに２進数の体系に逆変換して線形キー復号化器３００に出力する。
【０１７６】
復号化すべき２つの実数をfKeyMin及びfKeyMaxとすれば、最初の値fKeyMinを逆変換する過程は、下記の通りである。
【０１７７】
キーヘッダ復号化器３７０は、fKeyMinの桁数をビットストリームから読み込む。もし、桁数が０であれば、fKeyMinの値を０として設定した後、fKeyMaxの値を復号化するためにfKeyMaxの桁数をビットストリームから読み込む。もし、桁数が８以上であれば、ＩＥＥＥ標準７５４方式に従って符号化されたものであるため、実数を３２ビットだけ読み込んだ後、fKeyMaxの値を復号化する過程へ進む。
【０１７８】
しかしながら、もし、桁数が１と７との間の値を有すれば、キーヘッダ復号化器３７０は、符号ビットをビットストリームから読み込む。本発明の実施の形態においては、符号ビットが１であれば、MinKeyMantissaSignを−１として、０であれば、MinKeyMantissaSignを１として設定して符号を読み込む。そして、仮数を前記表１の桁数と必要なビット数との関係に基づき必要なビット数を得た後、そのビット数だけビットストリームから読み込み、読み込まれた値をnMinKeyMantissaに記憶する。その後、ビットストリームから１ビットのみを読み込んでMinKeyExponentSignに記憶するが、MinKeyMantissaSignと同じ方式により記憶する。そして、ビットストリームから６ビットのみの指数値を読み込んでnMinKeyExponentに記憶する。
【０１７９】
実数逆変換部３０５は、キーヘッダ復号化器３７０から入力された値を下記式２２に代入してfKeyMinを復元する。
【数２２】
2005348395.tif 000029
【０１８０】
fKeyMaxを復元する過程は、fKeyMinのそれと同じである。但し、fKeyMaxの指数をビットストリームから読み込む前に、fKeyMaxの指数としてfKeyMinと同じ指数が用いられたか否かを判読し、同じ値が用いられたならば、fKeyMinの指数を用い、そうでなければ、fKeyMinの指数をビットストリームから読み込む方式と同じく、fKeyMaxの指数を読み込む。
【０１８１】
一方、実数逆変換部３０５から線形キー領域の開始キー及び終了キーを入力された線形キー復号化器３００は、下記式２３を用いて線形キー領域を復号化する。
【数２３】
2005348395.tif 000030
【０１８２】
ここで、fKeyMin及びfKeyMaxは、線形キー領域の開始キーデータ及び終了キーデータを意味する。
【０１８３】
このようにして復号化された線形キー領域のキーデータは、逆量子化器３１０から出力されたキーデータに加えられて復号化された最終キーデータとして出力される。
【０１８４】
以上、本発明の好ましい実施の形態によるキーデータ復号化装置の一例を説明した。当該技術分野における通常の知識を有した者は、上述した好ましい実施の形態による復号化装置の様々な変形された実施の形態が存在するということが分かるであろう。以下、図２９ないし図３２を参照し、好ましいキーデータ復号化装置の実施の形態を説明する。一方、前記図２８に示された構成要素と同じ機能を行う構成要素には同じ参照符号を使用した。
【０１８５】
図２９を参照すれば、本発明の復号化装置の第２の実施の形態は、エントロピ復号化器３６０、逆ＤＮＤ演算部３５２、逆フォルド処理部３４０、逆シフト部３３０、逆ＤＰＣＭ処理部３２０、及び逆量子化器３１０を備える。
【０１８６】
キーデータを符号化したビットストリームが第２の実施の形態の復号化装置に入力されれば、エントロピ復号化器３６０は、入力されたビットストリームをエントロピ復号化し、復号化された差分データを逆ＤＮＤ演算部３５２に出力する。逆ＤＮＤ演算部３５２は、入力された差分データのＤＮＤ次数をチェックし、入力された差分データがＤＮＤ演算の行われた差分データであるか否かを判断し、ＤＮＤ演算が行われたならば、前記逆ＤＮＤ演算を行って出力し、そうでなければ、バイパスする。
【０１８７】
逆ＤＮＤ演算部３５２から差分データを入力された逆フォルド処理部３４０は、ＤＮＤ次数をチェックして入力された差分データがフォルド演算の行われた差分データであれば、逆フォルド演算を行って逆シフト部３３０に出力し、そうでなければ、逆シフト部３３０にバイパスする。
【０１８８】
一方、逆シフト部３３０は、入力された差分データに対して前記逆シフト演算を行って逆ＤＰＣＭ処理部３２０に出力し、逆ＤＰＣＭ処理部３２０は、差分データを量子化されたキーデータに変換して逆量子化器３１０に出力する。逆量子化器３１０は、量子化された差分データを逆量子化し、復号化されたキーデータを出力する。
【０１８９】
図３０を参照すれば、本発明の復号化装置の第３の実施の形態は、エントロピ復号化器３６０、逆ＤＮＤ処理部３５０、逆シフト部３３０、逆ＤＰＣＭ処理部３２０、及び逆量子化器３１０を備える。
【０１９０】
キーデータを符号化したビットストリームが第３の実施の形態の復号化装置に入力されれば、エントロピ復号化器３６０は、入力されたビットストリームをエントロピ復号化した後、復号化された差分データを逆ＤＮＤ処理部３５０に出力する。逆ＤＮＤ処理部３５０は、入力された差分データに対して符号化過程においてシフト-アップ演算が行われたか否かをチェックし、シフト-アップ演算が行われたならば、前記シフト-ダウン演算を行った後に前記逆ＤＮＤ演算を行って出力し、そうでなければ、逆ＤＮＤ演算を行って逆シフト部３３０に出力する。
【０１９１】
一方、逆シフト部３３０は、入力された差分データに対して前記逆シフト演算を行って逆ＤＰＣＭ処理部３２０に出力し、逆ＤＰＣＭ処理部３２０は、差分データを量子化されたキーデータに変換して逆量子化器３１０に出力する。逆量子化器３１０は、量子化された差分データを逆量子化し、復号化されたキーデータを出力する。
【０１９２】
図３１を参照すれば、本発明の復号化装置の第４の実施の形態は、エントロピ復号化器３６０、逆シフト-アップ演算部３５６、及び逆ＤＮＤ演算部３５２を備える。
【０１９３】
入力されたビットストリームは、エントロピ復号化器３６０において復号化されて差分データに変換された後に逆シフト-アップ演算部３５６に入力される。逆シフト-アップ演算部３５６は、入力された差分データに対して前記シフト-ダウン演算を行い、ＤＮＤ演算された差分データを生成して逆ＤＮＤ演算部３５２に出力する。逆ＤＮＤ演算部３５２は、前記逆ＤＮＤ演算を行って復号化されたキーデータの差分データを出力する。復号化されたキーデータの差分データは、通常の復号化器の構成を用いて復号化されたキーデータを出力することができる。
【０１９４】
図３２を参照すれば、本発明の復号化装置の第５の実施の形態は、線形キー符号化器を用いる符号化装置において符号化されたビットストリームを復号化する復号化装置である。
【０１９５】
入力ビットストリームは、エントロピ復号化部３８０及びキーヘッダ復号化器３７０に入力される。エントロピ復号化部３８０は、ビットストリームにおいてキーデータに当たる部分をエントロピ復号化して所定の演算を行って逆量子化器３１０に出力し、キーヘッダ復号化器３７０は、入力されたビットストリームからキーヘッダに当たるビットストリームを復号化して線形キー復号化器に線形キー領域に含まれるキーデータの数を出力し、実数逆変換部３０５に線形キー領域の開始キーデータ及び終了キーデータ情報を出力する。
【０１９６】
逆量子化器３１０は、入力された量子化されたキーデータを逆量子化して出力し、線形キー復号化器は、実数逆変換部３０５から入力された線形キー領域の開始キーデータ及び終了キーデータを入力されて線形キー領域を復号化し、復号化された線形キー領域を逆量子化器３１０から出力されたキーデータに加えて復号化されたキーデータを出力する。
【０１９７】
図４０ないし図４２を参照し、復号化過程を行う演算を具現したプログラムコードの例を説明する。
【０１９８】
図４０は、符号及び値に対するコンテキストを用いた、適応的算術符号化されたビットストリームから符号あり値を復号化するdecodeSignedAAC()関数を具現するプログラムコードの一例を示す図面である。
【０１９９】
図４１は、符号及び値に対するコンテキストを用いた、適応的算術符号化されたビットストリームから符号なき値を復号化するdecodeUnsignedAAC()関数を具現するプログラムコードの一例を示す図面である。図４１において、qf＿decode()は、ビットストリームから１ビットを読み込む関数である。
【０２００】
図４２は、前記逆ＤＮＤ演算過程から逆量子化過程をプログラムコードにて具現した一例を示す図面である。
【０２０１】
本発明はまた、コンピュータにて読取り可能な記録媒体にコンピュータにて読取り可能なコードとして具現可能である。コンピュータにて読取り可能な記録媒体は、コンピュータシステムによって読取り可能なデータが記憶されるあらゆる種類の記録装置を含む。コンピュータにて読取り可能な記録媒体の例としては、ＲＯＭ、ＲＡＭ、ＣＤ−ＲＯＭ、磁気テープ、フロッピーディスク、光データ記憶装置などがあり、また、キャリアウェーブ（例えば、インターネットを通じた伝送）の形で具現されるものも含む。また、コンピュータにて読取り可能な記録媒体は、ネットワークにより結ばれたコンピュータシステムに分散され、分散方式によりコンピュータにて読取り可能なコードが記憶されて実行できる。
【０２０２】
今まで本発明についてその好ましい実施の形態を中心として説明した。本発明が属する技術分野における通常の知識を有した者は、本発明が本発明の本質的な特性から逸脱しない範囲において変形された形態で具現できることが理解できるであろう。よって、開示された実施の形態は限定的な観点ではなく、説明的な観点からら考慮されるべきである。本発明の範囲は、以上の説明ではなく、特許請求の範囲に示されており、それと同等な範囲内にあるあらゆる違いは、本発明に含まれたものとして解釈されるべきである。
【図面の簡単な説明】
【０２０３】
【図１】通常のキーデータ符号化及び復号化装置の構成を示すブロック図である。
【図２】本発明の好ましい実施の形態による符号化装置の構成を示すブロック図である。
【図３】図２に示されたＤＮＤ処理部の構成を示すブロック図である。
【図４】本発明の符号化装置の第２の実施の形態の構成を示すブロック図である。
【図５】本発明の符号化装置の第３の実施の形態の構成を示すブロック図である。
【図６】本発明の符号化装置の第４の実施の形態の構成を示すブロック図である。
【図７】本発明の符号化装置の第５の実施の形態の構成を示すブロック図である。
【図８】本発明の符号化装置の第６の実施の形態の構成を示すブロック図である。
【図９】本発明の好ましい実施の形態による符号化方法（前半部）を説明するフローチャートである。
【図１０】本発明の好ましい実施の形態による符号化方法（後半部）を説明するフローチャートである。
【図１１】本発明の好ましい実施の形態による実数変換過程（前半部）を説明するフローチャートである。
【図１２】本発明の好ましい実施の形態による実数変換過程（後半部）を説明するフローチャートである。
【図１３】本発明の好ましい実施の形態による量子化過程を説明するフローチャートである。
【図１４】本発明の好ましい実施の形態によるＤＰＣＭ演算過程を説明するフローチャートである。
【図１５】本発明の好ましい実施の形態によるＤＮＤ演算過程を説明するフローチャートである。
【図１６】本発明の好ましい実施の形態によるエントロピ符号化方法の一例を示す図面である。
【図１７】本発明の好ましい実施の形態による演算過程における、本発明の符号化器に入力される元のキーデータを示す。
【図１８】本発明の好ましい実施の形態による演算過程における、量子化されたキーデータを示す。
【図１９】本発明の好ましい実施の形態による演算過程における、ＤＰＣＭを行った後のキーデータの差分データを示す。
【図２０】本発明の好ましい実施の形態による演算過程における、シフトされたキーデータの差分データを示す。
【図２１】本発明の好ましい実施の形態による演算過程における、フォルド演算後の差分データを示す。
【図２２】本発明の好ましい実施の形態による演算過程における、ディバイド演算後の差分データを示す。
【図２３】本発明の好ましい実施の形態による演算過程における、ディバイド−アップ演算後の差分データを示す。
【図２４】本発明の好ましい実施の形態による演算過程における、ディバイド−ダウン演算後の差分データを示す。
【図２５】本発明の好ましい実施の形態による演算過程における、シフト−アップ演算後の差分データを示す。
【図２６】本発明の好ましい実施の形態による演算過程において確定した、最終的に符号化すべきキーデータを示す。
【図２７】（ａ）及び（ｂ）は、キーデータ及びキー値データを用いてアニメーションデータを符号化する過程を簡略に示す図面である。
【図２８】Ａは、本発明の好ましい実施の形態によるキーデータ復号化装置の構成を示すブロック図であり、そして
【図２９】本発明の復号化装置の第２の実施の形態の構成を示すブロック図である。
【図３０】本発明の復号化装置の第３の実施の形態の構成を示すブロック図である。
【図３１】本発明の復号化装置の第４の実施の形態の構成を示すブロック図である。
【図３２】本発明の復号化装置の第５の実施の形態の構成を示すブロック図である。
【図３３】本発明の好ましい実施の形態による復号化方法を説明するフローチャートである。
【図３４】本発明の好ましい実施の形態による逆ＤＮＤ演算過程を説明するフローチャートである。
【図３５】符号化のためのKeyheaderプログラムコードの一例を説明する図面である。
【図３６】符号化のためのLinearKeyプログラムコードの一例を説明する図面である。
【図３７】符号化のためのKeySelectionFlagプログラムコードの一例を説明する図面である。
【図３８】符号化のためのKeyMinMaxプログラムコードの一例を説明する図面である。
【図３９】符号化のためのKeyプログラムコードの一例を説明する図面である。
【図４０】復号化過程を行う演算を具現したプログラムコードの一例として、decodeSignedAAC関数を説明する図面である。
【図４１】復号化過程を行う演算を具現したプログラムコードの一例として、decodeUnsignedAAC関数を説明する図面である。
【図４２】復号化過程を行う演算を具現したプログラムコードの一例として、逆ＤＮＤ演算過程から逆量子化過程を説明する図面である。
【符号の説明】
【０２０４】
２８０      エントロピ符号化部
２９０      線形キーデータ符号化部
【図１】
2005348395.tif 000031
【図２】
2005348395.tif 000032
【図３】
2005348395.tif 000033
【図４】
2005348395.tif 000034
【図５】
2005348395.tif 000035
【図６】
2005348395.tif 000036
【図７】
2005348395.tif 000037
【図８】
2005348395.tif 000038
【図９】
2005348395.tif 000039
【図１０】
2005348395.tif 000040
【図１１】
2005348395.tif 000041
【図１２】
2005348395.tif 000042
【図１３】
2005348395.tif 000043
【図１４】
2005348395.tif 000044
【図１５】
2005348395.tif 000045
【図１６】
2005348395.tif 000046
【図１７】
2005348395.tif 000047
【図１８】
2005348395.tif 000048
【図１９】
2005348395.tif 000049
【図２０】
2005348395.tif 000050
【図２１】
2005348395.tif 000051
【図２２】
2005348395.tif 000052
【図２３】
2005348395.tif 000053
【図２４】
2005348395.tif 000054
【図２５】
2005348395.tif 000055
【図２６】
2005348395.tif 000056
【図２７】
2005348395.tif 000057
【図２８】
2005348395.tif 000058
【図２９】
2005348395.tif 000059
【図３０】
2005348395.tif 000060
【図３１】
2005348395.tif 000061
【図３２】
2005348395.tif 000062
【図３３】
2005348395.tif 000063
【図３４】
2005348395.tif 000064
【図３５】
2005348395.tif 000065
【図３６】
2005348395.tif 000066
【図３７】
2005348395.tif 000067
【図３８】
2005348395.tif 000068
【図３９】
2005348395.tif 000069
【図４０】
2005348395.tif 000070
【図４１】
2005348395.tif 000071
【図４２】
2005348395.tif 000072