(57)【特許請求の範囲】
【請求項１】
アニメーション軌跡から所定数のブレークポイントを抽出し、前記抽出されたブレークポイントに対応するキー及びキー値を出力する補間分析部と、
前記補間分析部から出力されるキーを符号化するキー符号化部と、
前記補間分析部から出力されるキー値を符号化するキー値符号化部と、
前記キー符号化部、及びキー値符号化部で符号化されたキー、及びキー値を、エントロピー符号化して符号化されたビットストリームとして出力するエントロピーエンコーダと、を具備し、
前記キー符号化部は、前記補間分析部から入力されたキーを、差分パルス符号変調（ＤＰＣＭ）量子化方式によって符号化することを特徴とするアニメーション軌跡の圧縮装置。
【請求項２】
アニメーション軌跡から所定数のブレークポイントを抽出し、前記抽出されたブレークポイントに対応するキー及びキー値を出力する補間分析部と、
前記補間分析部から出力されるキーを符号化するキー符号化部と、
前記補間分析部から出力されるキー値を符号化するキー値符号化部と、
前記キー符号化部、及びキー値符号化部で符号化されたキー、及びキー値を、エントロピー符号化して符号化されたビットストリームとして出力するエントロピーエンコーダと、を具備し、
前記キー値符号化部は、前記補間分析部から入力されたキー値を、差分パルス符号変調（ＤＰＣＭ）量子化方式によって符号化することを特徴とするアニメーション軌跡の圧縮装置。
【請求項３】
前記補間分析部は、元のアニメーション軌跡のブレークポイントの中から抽出された所定数のブレークポイントによって得られるアニメーション軌跡と、元のアニメーション軌跡との差を最小化させる方向に、前記ブレークポイントの個数を決定することを特徴とする請求項１または請求項２に記載のアニメーション軌跡の圧縮装置。
【請求項４】
前記補間分析部は、元のアニメーション軌跡の両端の点を出発点として各ブレークポイントの中から元のアニメーション軌跡との差が最小となるように近似化された軌跡を示すブレークポイントを探し出し、近似化されたアニメーション軌跡が前記元のアニメーション軌跡と近づくまでこのような過程を繰り返すことを特徴とする請求項１または請求項２に記載のアニメーション軌跡の圧縮装置。
【請求項５】
前記ブレークポイントは、元のアニメーション軌跡と、近似化されたアニメーション軌跡との面積の差を最小化させるように決定されることを特徴とする請求項４に記載のアニメーション軌跡の圧縮装置。
【請求項６】
前記差分パルス符号変調（ＤＰＣＭ）量子化方式は、現在値と直前値との差を符号化する、あるいは、直前値と更にその直前値との差に直前値を足した近似値と、現在値との差を符号化することを特徴とする請求項１または請求項２に記載のアニメーション軌跡の圧縮装置。
【請求項７】
符号化されたビットストリームが入力されると、このビットストリームをエントロピーデコーディングするエントロピーデコーダと、
前記エントロピーデコーディングされた結果が入力されると、そのキーを復号化するキー復号化部と、
前記エントロピーデコーディングされた結果が入力されると、そのキー値を復号化するキー値復号化部と、
前記キー復号化部、及びキー値復号化部によって復号化されたキー、及びキー値に基づく線形補間法によって、空のキー値を求めて元のアニメーション軌跡に復元する補間復元部と、を具備し、前記キー復号化部は、前記エントロピーデコーダから入力されたデコーディングされた結果を、差分パルス符号変調（ＤＰＣＭ）逆量子化方式によって復号化することを特徴とするアニメーション軌跡の復元装置。
【請求項８】
符号化されたビットストリームが入力されると、このビットストリームをエントロピーデコーディングするエントロピーデコーダと、
前記エントロピーデコーディングされた結果が入力されると、そのキーを復号化するキー復号化部と、
前記エントロピーデコーディングされた結果が入力されると、そのキー値を復号化するキー値復号化部と、
前記キー復号化部、及びキー値復号化部によって復号化されたキー、及びキー値に基づく線形補間法によって、空のキー値を求めて元のアニメーション軌跡に復元する補間復元部と、を具備し、前記キー値復号化部は、前記エントロピーデコーダから入力されたデコーディングされた結果を、差分パルス符号変調（ＤＰＣＭ）逆量子化方式で復号化することを特徴とするアニメーション軌跡の復元装置。
【請求項９】
元のアニメーション軌跡から所定数のブレークポイントを抽出する段階と、
前記抽出されたブレークポイントを用いてキー及びキー値を抽出し、これらを符号化する段階と、
前記符号化されたキー及びキー値をエントロピー符号化し、これらを符号化してビットストリームを求める段階と、を具備し、前記キーの符号化は差分パルス符号変調（ＤＰＣＭ）量子化方式によることを特徴とするアニメーション軌跡の圧縮方法。
【請求項１０】
元のアニメーション軌跡から所定数のブレークポイントを抽出する段階と、
前記抽出されたブレークポイントを用いてキー及びキー値を抽出し、これらを符号化する段階と、
前記符号化されたキー及びキー値をエントロピー符号化し、これらを符号化してビットストリームを求める段階と、を具備し、前記キー値の符号化は差分パルス符号変調（ＤＰＣＭ）量子化方式によることを特徴とするアニメーション軌跡の圧縮方法。
【請求項１１】
符号化されたビットストリームが入力されると、これをエントロピーデコーディングする段階と、
前記エントロピーデコーディングされた結果から、キー及びキー値を復号化する段階と、
前記復号化されたキー及びキー値に基づく線形補間法によって空のキー値を求め、元のアニメーション軌跡を復元する段階と、
を具備し、前記キーの復号化は差分パルス符号変調（ＤＰＣＭ）逆量子化方式によることを特徴とするアニメーション軌跡の復元方法。
【請求項１２】
符号化されたビットストリームが入力されると、これをエントロピーデコーディングする段階と、
前記エントロピーデコーディングされた結果から、キー及びキー値を復号化する段階と、
前記復号化されたキー及びキー値に基づく線形補間法によって空のキー値を求め、元のアニメーション軌跡を復元する段階と、
を具備し、前記キー値の復号化は差分パルス符号変調（ＤＰＣＭ）逆量子化方式によることを特徴とするアニメーション軌跡の復元方法。
【請求項１３】
アニメーション軌跡が符号化されたビットストリームの生成方法において、
アニメーション軌跡の各ブレークポイントのｘ、ｙ、ｚ座標に対応するキー値の中で、どの座標軸のキー値が選択されたかを示すアレイ型キーフラグと、
各ブレークポイントでｘ、ｙ、ｚ座標に対応するキー値の中から少なくとも１つのキー値が選択されることを示すアレイ型キーと、
各ブレークポイントで選択されたキー値を示すアレイ型キー値と、をデータフォーマットに含ませることを特徴とするビットストリームの生成方法。
【請求項１４】
Ｘ、Ｙ、Ｚ座標軸に対応する、キー値の最小値と、Ｘ、Ｙ、Ｚ座標軸に対応する、キー値の最大値とを更にデータフォーマットに含ませることを特徴とする請求項１３に記載のアニメーション軌跡が符号化されたビットストリームの生成方法。
【請求項１５】
前記アレイ型キーフラグは、Ｍ（Ｍ≦ｎ、ｎは元のキーの個数）個のデータを含むことを特徴とする請求項１３に記載のアニメーション軌跡が符号化されたビットストリームの生成方法。
【請求項１６】
前記アレイ型キーは、Ｍ（Ｍ≦ｎ、ｎは元のキーの個数）個のデータを含むことを特徴とする請求項１３に記載のアニメーション軌跡が符号化されたビットストリームの生成方法。
【請求項１７】
前記キー値は、ｘ軸に対するｐ（ｐ≦ｎ、ｎはキーの個数）個の第１キー値、ｙ軸に対するｑ（ｑ≦ｎ、ｎはキーの個数）個の第２キー値及びｚ軸に対するｒ（ｒ≦ｎ、ｎはキーの個数）個の第３キー値を具備することを特徴とする請求項１３に記載のアニメーション軌跡が符号化されたビットストリームの生成方法。
【請求項１８】
（ａ）元のアニメーション軌跡の上にあるブレークポイントの中から両端の２個のブレークポイントを選択する段階と、
（ｂ）前記選択された両端のブレークポイントを除いた残りのブレークポイントの中から１個のブレークポイントを選択する段階と、
（ｃ）前記選択されたブレークポイントを用いて、前記選択されたブレークポイントを除いた残りのブレークポイントのキー値を補間する段階と、
（ｄ）前記選択されたキー値及び前記補間されたキー値に基づいて近似化された軌跡を形成し、元のアニメーション軌跡と前記近似化されたアニメーション軌跡との差が最小であるアニメーション軌跡を選択し、前記選択されたアニメーション軌跡に対応するブレークポイントを選択する段階と、
（ｅ）前記選択されたブレークポイントを除いた残りのブレークポイントの中から１個のブレークポイントを選択した後、前記（ｃ）段階を再び繰り返し、前記元のアニメーション軌跡と前記近似化されたアニメーション軌跡との差が許容差よりも小さくなるまで繰り返す段階と、
を含むことを特徴とするアニメーション軌跡のブレークポイント抽出方法。
【請求項１９】
前記元のアニメーション軌跡と前記近似化されたアニメーション軌跡との差は、元のアニメーション軌跡及び近似化された軌跡によって形成される台形およびネジレ台形の面積の和で表現されることを特徴とする請求項１８に記載のアニメーション軌跡のブレークポイント抽出方法。
【請求項２０】
前記元のアニメーション軌跡と前記近似化されたアニメーション軌跡との差は、回転インターポレータの場合に、元のアニメーション軌跡に対する回転変換と前記近似化された軌跡に対する回転変換との差である差分回転変換における差分回転角として定義されることを特徴とする請求項１８に記載のアニメーション軌跡のブレークポイント抽出方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、３次元グラフィックスモデルのアニメーションに係り、特にアニメーションに使用されるアニメーション軌跡（ｐａｔｈ）を、線形近似化の手法を用いて圧縮及び復元する装置、この装置で行われる圧縮及び復元方法、並びにこのためのデータのフォーマットに関する。
【０００２】
【従来の技術】
グラフィックスに基づいた３次元アニメーション（ａｎｉｍａｔｉｏｎ；動画）の場合、３次元モデルで表現されたオブジェクト（客体）のアニメーションに対する空間上の動き、回転、モデル自体のモルフィング（ｍｏｒｐｈｉｎｇ）、色の変移などを表現するためにインターポレータ（ｉｎｔｅｒｐｏｌａｔｏｒ）が使用される。
【０００３】
図１は、一般の３次元アニメーションにおけるアニメーション軌跡を説明するための図であって、縦軸はキー値（ＫＥＹ＿ＶＡＬＵＥ）を、横軸はキー（ＫＥＹ）を各々示す。
図１に示すアニメーション軌跡２０は３次元モデル１０のアニメーションの痕跡を表現したものである。このアニメーション情報の軌跡（アニメーション軌跡）２０は、図１に示すように経時的に変化する２次元曲線の形態を有する。アニメーション軌跡２０を表現する方式は種々あり、このような様々な方式は１９８９年に、Ｐｒｅｎｔｉｃｅ  Ｈａｌｌ社から出版された「Ｆｕｎｄａｍｅｎｔａｌｓ  ｏｆ  Ｄｉｇｉｔａｌ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ」の第９章に開示されている。
【０００４】
インターポレータによる表現では図１に示すような曲線状のアニメーション軌跡２０を複数個のセグメント（分節）を用いて直線状に分けて表現することができる。このような表現において必要な情報は、各直線のブレークポイント（ｂｒｅａｋ  ｐｏｉｎｔ；分節点）または頂点である。
ここで、前記「ブレークポイント」または「頂点」は、図１に示すアニメーション軌跡２０において黒色の点「●」で表されている。線形補間（または挿入）（Ｌｉｎｅａｒ  Ｉｎｔｅｒｐｏｌａｔｉｏｎ）の手法を用いると、これらの各ブレークポイントから元の曲線を復元することができる。
【０００５】
図２は、仮想現実モデリング言語（ＶＲＭＬ：Ｖｅｒｔｕａｌ  Ｒｅａｌｉｔｙ  Ｍｏｄｅｌｉｎｇ  Ｌａｎｇｕａｇｅ）、またはＭＰＥＧ（Ｍｏｖｉｎｇ  Ｐｉｃｔｕｒｅ  Ｅｘｐｅｒｔ  Ｇｒｏｕｐ）−４で使用されるアニメーション軌跡の表現例（Ｓｃａｌａｒ  Ｉｎｔｅｒｐｏｌａｔｏｒ）を示す図である。ここで処理されるべき情報はキー及びキー値を含み、与えられた情報から前記線形補間作業が行われる。
【０００６】
インターポレータの種類には大別して６種、すなわち、スカラーインターポレータ、位置インターポレータ、回転インターポレータ、座標インターポレータ、法線インターポレータ及び色インターポレータがある。
ここで、スカラーインターポレータは、図２に示すように表現することができる。各インターポレータの種類、特徴及び機能を次の表１に示す。表１に示すように、与えられたキーとこれらのキーによるキー値の集合という点において、これらのインターポレータは相等しい。
【０００７】
【表１】
0003694477.tif 000002
【０００８】
図３は、３次元アニメーションのデータ形式を説明するための図面であって、エンコーダ３０、デコーダ４０及び３次元アニメーションファイルフォーマット５０を示す。
ここで、エンコーダ３０からデコーダ４０に出力される３次元アニメーションファイルフォーマット５０は、モデルデータ、アニメーションデータ、属性、ビデオ／テクスチャー及びサウンドで構成されている。
【０００９】
図３を参照すると、インターポレータは３次元アニメーション軌跡を効率よく表現するアニメーションデータに該当する。ＶＲＭＬ／ＭＰＥＧ−４で表現される３次元アニメーションデータは、図３に示すような情報で構成される。従来のオーディオ、ビデオ、３次元モデルに対しては、標準化された圧縮技術が提供されていたが、アニメーション軌跡を決定するインターポレータの場合には、表現中心の汎用圧縮技術のみが提供されている。オーディオ／ビデオを除いたアニメーションの場合、アニメーション軌跡のデータ量は、３次元モデルと共にデータの大部分を占めることになる。したがって、３次元モデルの圧縮技術と共にアニメーション軌跡に対する圧縮技術が必須である。ＭＰＥＧ−４ＢＩＦＳ（Ｂｉｎａｒｙ  Ｆｏｒｍａｔ  ｆｏｒ  Ｓｃｅｎｅ）でアニメーションに対する基本的な量子化／圧縮方法を提供するが、これはインターポレータのための専用圧縮機術ではない汎用圧縮技術であって、圧縮性能が脆弱という問題点がある。これについては、２０００年にニューヨークで開催されたマルチメディア及びエキスポに関する国際会議（Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎｍｕｌｔｉｍｅｄｉａ  ａｎｄ  Ｅｘｐｏ）の会報に記載されている、Ｅｕｅｅ  Ｓ．Ｊａｎｇによって発表された「３Ｄ  Ａｎｉｍａｔｉｏｎ  Ｃｏｄｉｎｇ：ｉｔｓ  Ｈｉｓｔｏｒｙ  ａｎｄ  Ｆｒａｍｅｗｏｒｋ」で開示されている。
【００１０】
図４（Ａ）及び図４（Ｂ）は各々、前記アニメーション軌跡に対する従来の圧縮装置及び復元装置のブロック図であって、図４（Ａ）に示す従来の圧縮装置はスカラー量子化部６０を有して構成され、図４（Ｂ）に示す従来の復元装置はスカラー逆量子化部７０を有して構成されている。
【００１１】
図４（Ａ）に示すスカラー量子化部６０は、元のアニメーション軌跡がｋｅｙ、ｋｅｙ＿ｖａｌｕｅ（ここで、ｋｅｙはキーを、ｋｅｙ＿ｖａｌｕｅはキー値を各々示す。）の形で入力端子ＩＮ１を通して入力されてスカラー量子化され、このようにスカラー量子化された結果である符号化されたビットストリームは、出力端子ＯＵＴ１を通して出力される。また、図４（Ｂ）に示すスカラー逆量子化部７０は、符号化されたビットストリームを、入力端子ＩＮ２を通して入力され、復元されたアニメーション軌跡（ｋｅｙ、ｋｅｙ＿ｖａｌｕｅ）の形のデータとして出力端子ＯＵＴ２を通して出力する。
【００１２】
従来のＭＰＥＧ−４ＢＩＦＳでのインターポレータの圧縮は、図４（Ａ）に示すようにスカラー量子化を経て実行される。図４（Ａ）に示す従来の圧縮過程は、インターポレータのみならず、ＢＩＦＳでの圧縮が要求されるあらゆる要素にも共通して提供される方式である。図４（Ｂ）に示す従来の復元装置に入力された符号化されたビットストリームは、圧縮の順序を逆に実行することによりスカラー逆量子化部７０を経てアニメーション軌跡が復元される。図４（Ａ）及び図４（Ｂ）では、インターポレータから提供されるキー及びキー値等が各種類ごとの特性を考慮することなく同じ方式で圧縮されるので、充分な圧縮効果を発揮することができないという問題点がある。
【００１３】
【発明が解決しようとする課題】
前記問題点を解決するために、本発明の第１の目的は、インターポレータ形式のアニメーションデータを効率よく圧縮して、迅速なデータの伝送及び記憶を可能にする、線形近似化の手法を用いたアニメーション軌跡の圧縮装置及びその方法を提供することにある。
【００１４】
また、本発明の第２の目的は、圧縮されたアニメーション軌跡のデータを効率的に復元することができるアニメーション軌跡の復元装置及びその方法を提供することにある。
【００１５】
更に、本発明の第３の目的は、アニメーション軌跡データの圧縮に用いられるアニメーション軌跡に対する圧縮用データフォーマットを提供することにある。
【００１６】
【課題を解決するための手段】
前記第１の目的を達成するために、本発明に係る第１の態様は、アニメーション軌跡から所定数のブレークポイントを抽出し、前記抽出されたブレークポイントに対応するキー及びキー値を出力する補間分析部と、前記補間分析部から出力されるキーを符号化するキー符号化部と、前記補間分析部から出力されるキー値を符号化するキー値符号化部と、前記キー符号化部、及びキー値符号化部で符号化されたキー、及びキー値を、エントロピー符号化して符号化されたビットストリームとして出力するエントロピーエンコーダとを具備することを特徴とするアニメーション軌跡の圧縮装置を提供する。
【００１７】
本発明に係る第２の態様は、前記第１の態様において、補間分析部が、元のアニメーション軌跡のブレークポイントの中から抽出された所定数のブレークポイントによって得られるアニメーション軌跡と、元のアニメーション軌跡との差を最小化させる方向に、前記ブレークポイントの個数を決定することを特徴とするアニメーション軌跡の圧縮装置を提供する。
また、本発明に係る第３の態様は、前記第１の態様において、キー符号化部が、補間分析部から入力されたキーを、差分パルス符号変調（ＤＰＣＭ：Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｕｌｓｅ  Ｃｏｄｉｎｇ  Ｍｏｄｕｌａｔｉｏｎ）量子化方式によって符号化することを特徴とするアニメーション軌跡の圧縮装置を提供する。
更に、本発明に係る第４の態様は、前記第１の態様において、キー値符号化部が、補間分析部から入力されたキー値を、差分パルス符号変調（ＤＰＣＭ）量子化方式によって符号化することを特徴とするアニメーション軌跡の圧縮装置を提供する。
【００１８】
また、本発明に係る第５の態様は、前記第１の態様において、補間分析部が、元のアニメーション軌跡の両端の点を出発点として、各ブレークポイントの中から元のアニメーション軌跡との差が最小となるように近似化された軌跡を示すブレークポイントを探し出し、近似化されたアニメーション軌跡が前記元のアニメーション軌跡と近づくまでこのような過程を繰り返すことを特徴とするアニメーション軌跡の圧縮装置を提供する。
更に、本発明に係る第６の態様は、前記第５の態様において、前記ブレークポイントが、元のアニメーション軌跡と、近似化されたアニメーション軌跡との面積の差を最小化させるように決定されることを特徴とするアニメーション軌跡の圧縮装置を提供する。
そして、本発明に係る第７の態様は、前記第３または第４の態様において、前記差分パルス符号変調（ＤＰＣＭ）量子化方式が、現在値と直前値との差を符号化する、あるいは、直前値と更にその直前値との差に直前値を足した近似値と、現在値との差を符号化することを特徴とするアニメーション軌跡の圧縮装置を提供する。
【００１９】
前記第２の目的を達成するために、本発明に係る第８の態様は、符号化されたビットストリームが入力されると、このビットストリームをエントロピーデコーディングするエントロピーデコーダと、前記エントロピーデコーディングされた結果が入力されると、そのキーを復号化するキー復号化部と、前記エントロピーデコーディングされた結果が入力されると、そのキー値を復号化するキー値復号化部と、前記キー復号化部、及びキー値復号化部によって復号化されたキー、及びキー値に基づく線形補間の手法によって、空のキー値を求めて元のアニメーション軌跡に復元する補間復元部とを具備することを特徴とするアニメーション軌跡の復元装置を提供する。
【００２０】
本発明に係る第９の態様は、前記第８の態様において、キー復号化部が、エントロピーデコーダから入力されたデコーディングされた結果を、差分パルス符号変調（ＤＰＣＭ）逆量子化方式によって復号化することを特徴とするアニメーション軌跡の復元装置を提供する。
また、本発明に係る第１０の態様は、前記第８の態様において、キー値復号化部が、エントロピーデコーダから入力されたデコーディングされた結果を、差分パルス符号変調（ＤＰＣＭ）逆量子化方式で復号化することを特徴とする請求項８に記載のアニメーション軌跡の復元装置を提供する。
【００２１】
前記第１の目的を達成するために、本発明に係る第１１の態様は、元のアニメーション軌跡から所定数のブレークポイントを抽出する段階と、前記抽出されたブレークポイントを用いてキー及びキー値を抽出し、これらを符号化する段階と、前記符号化されたキー及びキー値をエントロピー符号化し、これらを符号化してビットストリームを求める段階とを具備することを特徴とするアニメーション軌跡の圧縮方法を提供する。
【００２２】
前記第２の目的を達成するために、本発明に係る第１２の態様は、符号化されたビットストリームが入力されると、これをエントロピーデコーディングする段階と、前記エントロピーデコーディングされた結果から、キー及びキー値を復号化する段階と、前記復号化されたキー及びキー値に基づく線形補間の手法によって空のキー値を求め、元のアニメーション軌跡を復元する段階とを具備することを特徴とするアニメーション軌跡の復元方法を提供する。
【００２３】
前記第３の目的を達成するために、本発明に係る第１３の態様は、アニメーション軌跡の各ブレークポイントのｘ、ｙ、ｚ座標に対応するキー値の中で、どの座標軸のキー値が選択されたかを示すアレイ型キーフラグと、各ブレークポイントでｘ、ｙ、ｚ座標に対応するキー値の中から少なくとも１つのキー値が選択されることを示すアレイ型キーと、各ブレークポイントで選択されたキー値を示すアレイ型キー値とを具備することを特徴とするアニメーション軌跡が符号化されたビットストリームのデータフォーマットを提供する。
【００２４】
本発明に係る第１４の態様は、前記第１２の態様において、Ｘ、Ｙ、Ｚ座標軸に対応するキー値の最小値と、Ｘ、Ｙ、Ｚ座標軸に対応する、キー値の最大値とを更に含んで構成されることを特徴とするアニメーション軌跡が符号化されたビットストリームのデータフォーマットを提供する。
また、本発明に係る第１５の態様は、前記第１２の態様において、アレイ型キーフラグが、Ｍ（Ｍ≦ｎ、ｎは元のキーの個数）個のデータを含むことを特徴とするアニメーション軌跡が符号化されたビットストリームのデータフォーマットを提供する。
更に、本発明に係る第１６の態様は、前記第１２の態様において、前記アレイ型キーが、Ｍ（Ｍ≦ｎ、ｎは元のキーの個数）個のデータを含むことを特徴とするアニメーション軌跡が符号化されたビットストリームのデータフォーマットを提供する。
そして、本発明に係る第１７の態様は、前記第１２の態様において、前記キー値は、ｘ軸に対するｐ（ｐ≦ｎ、ｎはキーの個数）個の第１キー値、ｙ軸に対するｑ（ｑ≦ｎ、ｎはキーの個数）個の第２キー値及びｚ軸に対するｒ（ｒ≦ｎ、ｎはキーの個数）個の第３キー値を具備することを特徴とするアニメーション軌跡が符号化されたビットストリームのデータフォーマットを提供する。
【００２５】
前記第３の目的を達成するために、本発明に係る第１８の態様は、（ａ）元のアニメーション軌跡の上にあるブレークポイントの中から両端の２個のブレークポイントを選択する段階と、（ｂ）前記選択された両端のブレークポイントを除いた残りのブレークポイントの中から１個のブレークポイントを選択する段階と、（ｃ）前記選択されたブレークポイントを用いて、前記選択されたブレークポイントを除いた残りのブレークポイントのキー値を補間する段階と、（ｄ）前記選択されたキー値、及び前記補間されたキー値に基づいて近似化された軌跡を形成し、元のアニメーション軌跡と前記近似化されたアニメーション軌跡との差が最小であるアニメーション軌跡を選択し、前記選択されたアニメーション軌跡に対応するブレークポイントを選択する段階と、（ｅ）前記選択されたブレークポイントを除いた残りのブレークポイントの中から１個のブレークポイントを選択した後、前記（ｃ）段階を再び繰り返し、前記元のアニメーション軌跡と前記近似化されたアニメーション軌跡との差が許容差よりも小さくなるまで繰り返す段階とを含むことを特徴とするアニメーション軌跡のブレークポイント抽出方法を提供する。
【００２６】
本発明に係る第１９の態様は、前記第１８の態様において、元のアニメーション軌跡と前記近似化されたアニメーション軌跡との差が、元のアニメーション軌跡、及び近似化された軌跡によって形成される台形、またはネジレ台形の面積の和で表現されることを特徴とするアニメーション軌跡のブレークポイント抽出方法を提供する。
本発明に係る第２０の態様は、前記第１８の態様において、元のアニメーション軌跡と前記近似化されたアニメーション軌跡との差が、回転インターポレータの場合に、元のアニメーション軌跡に対する回転変換と前記近似化された軌跡に対する回転変換との差である差分回転変換における差分回転角として定義されることを特徴とするアニメーション軌跡のブレークポイント抽出方法を提供する。
【００２７】
なお、本発明では、ＶＲＭＬ／ＭＰＥＧ−４で一般に使用されているインターポレータ表現を用いることができる。このインターポレータが使用される分野は、主にオンラインコンピューターゲーム、アニメーション広告である。
【００２８】
【発明の実施の形態】
以下、添付した図面に基づき本発明を詳細に説明する。
図５（Ａ）は本発明に係るアニメーション軌跡の圧縮装置のブロック図である。図５（Ａ）に示すように、本発明に係るアニメーション軌跡の圧縮装置は、補間分析部８０、キー符号化部８２、キー値符号化部８４及びエントロピーエンコーダ８６を含んで構成される。また、図５（Ｂ）は本発明に係るアニメーション軌跡の復元装置のブロック図である。図５（Ｂ）に示すように、本発明に係るアニメーション軌跡の復元装置は、エントロピーデコーダ９０、キー復号化部９２、キー値復号化部９４及び補間復元部９６を含んで構成される。
【００２９】
図５（Ａ）に示す本発明に係るアニメーション軌跡の圧縮装置に含まれる補間分析部８０は、符号化するキーとキー値とを選定するものであり、各種インターポレータの特性を考慮して設計することができる。詳細な説明は後述する。
図６は、図５（Ａ）に示す本発明に係るアニメーション軌跡の圧縮装置において、本発明に係る望ましい１実施形態のブロック図である。本発明に係る１実施形態のアニメーション軌跡の圧縮装置は、図６に示すように、正規化部１００及びブレークポイント最小化部１０２を含む補間分析部８０、差分パルス符号変調（ＤＰＣＭ：Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｕｌｓｅ  Ｃｏｄｉｎｇ  Ｍｏｄｕｌａｔｉｏｎ）量子化部１０４を含むキー符号化部８２、ＤＰＣＭ量子化部１０６を含むキー値符号化部８４及びエントロピーエンコーダ８６を含んで構成されている。
【００３０】
図７は、図５（Ｂ）に示す本発明に係るアニメーション軌跡の復元装置において、本発明に係る望ましい１実施形態のブロック図である。本発明に係る１実施形態のアニメーション軌跡の復元装置は、図７に示すように、エントロピーデコーダ９０、ＤＰＣＭ逆量子化部１２６を含むキー復号化部９２、ＤＰＣＭ逆量子化部１２８を含むキー値復号化部９４及びキー及びキー値復元部９５を含む補間復元部９６を有して構成されている。
【００３１】
補間分析部８０（図５（Ａ）、図６）の入力として提供されるインターポレータ表現は、キー（Ｋ）とキー値（ＫＶ）とを含む。図６に示す本発明に係る１実施形態のアニメーション軌跡の圧縮装置において、補間分析部８０は、入力端子ＩＮ３を通して入力されたアニメーション軌跡が最小のブレークポイントで表示されるようにブレークポイントの個数を調節するようになっている。アニメーション軌跡に対する元のブレークポイントの個数がＮ個であれば、補間分析部８０を経て出るブレークポイントの個数はＭ（Ｍ≦Ｎ）個に調整される。すなわち、補間分析部８０は、入力端子ＩＮ３を通して入力された元のアニメーション軌跡からブレークポイントを抽出する役割を果たす。
【００３２】
インターポレータでは、キーとキー値は各々正規化して使用される。このため、正規化部１００（図６）は、入力端子ＩＮ３を通して入力した元のアニメーション軌跡で、キー及びキー値を各々正規化してブレークポイント最小化部１０２に出力する。ＶＲＭＬによって支持されるｋｅｙは０以上１以下の値を有する。
【００３３】
補間分析部８０（図６）がブレークポイントの個数を調整する方式としては、調整されたブレークポイントによって形成されるアニメーション軌跡と元のアニメーション軌跡との差を最小化させる方向でブレークポイントの個数を決定する方式を採用することができる。このとき、ブレークポイント最小化部１０２は、正規化部１００から出力される、正規化されたキー及びキー値から最小限のブレークポイントが抽出されるようにする。例えば、位置インターポレータの場合、実際の軌跡と、補間分析部８０を通して決定される量子化された軌跡との間に最小の面積誤差が生じるようにブレークポイントを決定することができる。
【００３４】
一方、図６に示すブレークポイント最小化部１０２で実行される線形近似化法を用いたブレークポイントの抽出方法について説明すると次の通りである。
図８から図１５は、線形近似化の手法を用いたブレークポイント抽出の本発明に係る望ましい１実施形態を説明するための図面であって、アニメーション軌跡の上に表示された各点はブレークポイントを示す。図８は元のアニメーションの軌跡を表し、図９は軌跡の両端の点Ａ、Ｂを探す状態を表し、図１０は元の軌跡と最も近いブレークポイントを選択する過程を表し、図１１は１次抽出されたブレークポイントＡ、Ｂ、Ｃ（図中、白抜きの点「○」で示す）を表し、図１２は元の軌跡と近い２次ブレークポイントを抽出する過程を表し、図１３は２次抽出されたブレークポイントＡ、Ｂ、Ｃ、Ｄ（図中、白抜きの点「○」で示す）を表し、図１４は３次抽出されたブレークポイントＡ、Ｂ、Ｃ、Ｄ、Ｅを表し、図１５は４次抽出されたブレークポイントＡ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ（図中、白抜きの点「○」で示す）を表す。
【００３５】
与えられた元のアニメーション軌跡が図８に示すような軌跡である場合、元のアニメーション軌跡のブレークポイント（Ｎ個）の中で、元の軌跡との間の差が最小化となるような近似化された軌跡を示すブレークポイント（Ｍ個、２≦Ｍ≦Ｎ）を探し出す過程が、両端の点Ａ、Ｂを出発点として繰り返される。このような過程を、図９から図１５に示す。その際、前記ブレークポイントの抽出は、前記のように近似化された軌跡が元の軌跡に充分に近い状態であると判断されるまで反復される。
【００３６】
以下、元のアニメーション軌跡と、近似化されたアニメーション軌跡との面積の差を用いて、近似化された軌跡と実際の軌跡との間の差を求める方法について、添付した図面を参照しながらに説明する。
図１６は、実際のアニメーション軌跡２００と近似化されたアニメーション軌跡２１０との差を求める方法を説明するための図面である。図１６を参照すると、前記両者の軌跡の差は、台形またはネジレ台形で表現されている。下記式（１）は図１６に示す台形（Ｄ  ＴＲＡＰＥＺＯＩＤ：台形Ｄ）の面積を求める公式であり、下記式（２）は図１６に示すネジレ台形（ＴＷＩＳＴＥＤ＿ＴＲＡＰＥＺＯＩＤ）の面積を求める公式である。したがって、実際のアニメーション軌跡２００と近似化されたアニメーション軌跡２１０との差は、台形とネジレ台形の面積の和で表現され、これらの台形の面積の和（図１６中、破線で囲んだ範囲内の台形またはネジレ台形の和）が下記式（３）で表される前記両者の軌跡の面積差ＤAとなる。
【００３７】
【数１】
0003694477.tif 000003
【００３８】
【数２】
0003694477.tif 000004
【００３９】
【数３】
0003694477.tif 000005
【００４０】
本発明にあっては、前記式（３）で表される面積差ＤAを最小化させる方向にブレークポイントを抽出するものである。前述したように、ブレークポイント最小化部１０２が、前記ブレークポイントを抽出するようになっている。すなわち、図６に示す補間分析部８０を経由して、アニメーション軌跡の基本的ブレークポイントが抽出される。
なお、無損失処理が必要な場合には、前記抽出されたブレークポイントの個数（Ｍ）は元のブレークポイントの個数と同一であってもよい。
【００４１】
また、位置インターポレータの場合、キー値がＸ、Ｙ、Ｚ座標軸の３次元空間上の位置を表示するために、アニメーション軌跡は、Ｘ、Ｙ、Ｚ座標軸上の３つの曲線で表される。図６の補間分析部８０は、前記座標軸の各軸で独立してブレークポイントの抽出を行なうことができる。その際、前記座標軸の各軸ごとにブレークポイントは異なる。以下に示す表２は、８つのブレークポイントＰ０、Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６、Ｐ７を有する実際の軌跡を、補間分析部８０を経由させることによって、新たなブレークポイントを抽出した結果を示す。
【００４２】
【表２】
0003694477.tif 000006
【００４３】
表２において、ｋｅｙ＿ｆｌａｇはキーフラグを、ｋｖx、ｋｖy及びｋｖzは各々、座標軸Ｘ、Ｙ、Ｚに対応するキー値を示す。
ここで、「０」は各ブレークポイントで当該軸に対応するキー値が選択されたこと（例えば、ブレークポイントＰ０に対してＸ軸キー値ｋｖxが選択されたこと）を意味し、「Ｘ」は各ブレークポイントで当該軸に該当するキー値が選択されなかったことを意味する。キーフラグは各ブレークポイントでｘ、ｙ、ｚ座標に対応するキー値の中で、どの軸のキー値が選択されたかを示し、例えば、「７」はあらゆる軸のキー値が選択されたことを意味し、「６」はｘ軸のキー値ｋｖxが選択されず、残りは選択されたことを意味する。
【００４４】
表２に示すように、ブレークポイントＰ１、Ｐ３、Ｐ６は、Ｘ、Ｙ、Ｚの座標軸に対応するキー値の中からいずれのキー値も選択されず（ｋｖx、ｋｖy、ｋｖzが「Ｘ」で示されている）、不要なブレークポイントであると判定されたものである（キーフラグにおいて、「−」と表示されている）。
【００４５】
また、表２のＰ０、Ｐ７は、軌跡の両端の点であり、あらゆる軸でブレークポイントとして抽出された場合を示し、Ｐ２はＸ軸ではブレークポイントとして選択されなかったが、他の軸ではブレークポイントとして選択されたものである。したがって、図６の補間分析部８０では、元の８つのブレークポイントの代わりに、５つのブレークポイントに対応するキーが選定され、この選定されたブレークポイントに対応して各軸のキー値が決定される。表２ではキーが５つ、キー値が１１個必要な場合が示されている。このようなキーとキー値との対応関係は、付加的に伝送されるキーフラグ（ｋｅｙ＿ｆｌａｇ）によって表現される。このような表現によって、キーとキー値の個数は、実際の軌跡に対応する４×８＝３２から、１６個のキーとキー値、更に１つの付加的なキーフラグ（ｋｅｙ＿ｆｌａｇ）に減少することになる。本発明にあっては、このような過程を通して表現の簡素化が実行される。
【００４６】
図２４から図２９は、球面の線形近似化法を用いたブレークポイント抽出の、本発明に係る望ましい更に他の実施形態を説明するための図面であって、回転インターポレータでブレークポイント（または「キーフレーム」とも言う。）を減少させる方法に関するものである。
【００４７】
図２４は元のアニメーション軌跡の上で、各時間でのｎ＋１個の各ブレークポイントにおけるキー値（Ｑ0、Ｑ1、Ｑ2、…、Ｑn）を示しており、これらのキー値に対応する点を黒色の点（図中「●」）で示す。図２５に示すように、まずアニメーション軌跡の上にある各ブレークポイントの中から両端の２個のブレークポイント（Ｑ0、Ｑn）を選択する。このように選択された点を白抜きの点（図中「○」）で示す。
【００４８】
図２６は、前記のように選択された両端のブレークポイントを除いた残りのブレークポイントの中から１個のブレークポイント（３番目のブレークポイント）を選択する過程を示す図である。この際、３番目のブレークポイント候補を選択する方法は全部でｎ−１種ある。図２６は、２種の候補（Ｑ1、Ｑk）選択した例を示している。そして、前記ｎ−１種の候補の各々に対して選択された合計で３つのブレークポイントを用いて、選択されなかったブレークポイントのキー値を、球面の線形補間法によって補間する。元のアニメーション軌跡を、この補間法によって求めたｎ−１種のアニメーション軌跡の候補と各々比較してアニメーション軌跡の誤差が最小となるアニメーション軌跡を選択し、このアニメーション軌跡の選択によって、ｎ−１種のブレークポイント候補の中から選択されたアニメーション軌跡の候補に対応したブレークポイントを選択する。図２７では、その１例として候補２の軌跡が選択されたことを示している。軌跡間の誤差は平均誤差Ｅmを用いて求められる。
【００４９】
そして、図２８に示すように、図２７で選択された３つのブレークポイントを除いた残りのブレークポイントの中から１個のブレークポイントを選択した後、前述した図２６、図２７に示すような過程を実行して４番目のブレークポイントを選択する。一例として図２９は候補１の軌跡が選択されたことを示す。そして、図２８と関連したブレークポイント選択過程を、平均誤差が許容誤差より小さくなるまで反復して元の軌跡のブレークポイントの個数と同一、あるいは元の軌跡のブレークポイントの個数よりも少ない数のブレークポイントを抽出する。
【００５０】
また、前述した平均誤差Ｅmは、次のようにして求めることができる。まず、量子化誤差を、元のアニメーション軌跡に対する回転変換と、復元されたアニメーション軌跡に対する回転変換との差の差分回転変換での差分回転角として定義する。すなわち、下記記号（Ｓ１）は回転インターポレータのノードに属した１つのキー値を示し、これを復号化器で復元したキー値を下記記号（Ｓ２）で表す場合（但し、下記ベクトル（Ｓ３）は回転軸を示し、下記記号（Ｓ４）は回転量を示し、その範囲は下記記号（Ｓ５）を満たす。）、下記記号（Ｓ１）と下記記号（Ｓ２）とにより、３次元空間上の任意の位置ベクトル（Ｓ６）からベクトル（Ｓ７）及びベクトル（Ｓ８）への回転変換が行われるとき、生じる量子化誤差は下記ベクトル（Ｓ７）と下記ベクトル（Ｓ８）との差から求められる。この量子化誤差は下記式（Ｅ）で表される関係を成立させる。
ここで、下記ベクトル（Ｓ６）、ベクトル（Ｓ７）、ベクトル（Ｓ８）を四元数（ｑｕａｔｅｒｎｉｏｎ）で表すと下記式（５）、（５´）で定義される。
【００５１】
【数４】
0003694477.tif 000007
【００５２】
【数５】
0003694477.tif 000008
【００５３】
【数６】
0003694477.tif 000009
【００５４】
【数７】
0003694477.tif 000010
【００５５】
【数８】
0003694477.tif 000011
【００５６】
【数９】
0003694477.tif 000012
【００５７】
【数１０】
0003694477.tif 000013
【００５８】
【数１１】
0003694477.tif 000014
【００５９】
【数１２】
0003694477.tif 000015
【００６０】
【数１３】
0003694477.tif 000016
【００６１】
回転変換を示す前記（Ｓ１）と（Ｓ２）とを四元数で表現したものを、各々ＱとＱ’とする場合、下記式（５）、（５´）が導出される。
【００６２】
【数１４】
0003694477.tif 000017
【００６３】
前記式（５）、（５´）において、Ａ＊Ｂの形はＡとＢとの四元数乗算を表し、Ａ＊はＡのコンジュゲートを意味する。前記式（５）、（５´）によって下記式（６）が導出される。
【００６４】
【数１５】
0003694477.tif 000018
【００６５】
前記式（６）中、Ｑ″は前記ベクトル（Ｓ７）とベクトル（Ｓ８）との回転変換関係を示す値であって下記式（７）で定義される。
【００６６】
【数１６】
0003694477.tif 000019
【００６７】
前記式（７）より、前記ベクトル（Ｓ７）とベクトル（Ｓ８）との差分回転角をθ″とすれば、四元数変換式と前記式（７）とから、差分回転角θ″は下記式（８）より求められる。
【００６８】
【数１７】
0003694477.tif 000020
【００６９】
前記式（１０）中、「・」は内積の演算を意味する。前記式（８）はアニメーションの全てのブレークポイントの中で、ある特定時間に現れる瞬時量子化誤差を表す。アニメーションの全区間の量子化誤差を求める式を導出するために特定時間ｔにおける瞬時量子化誤差を表すと下記式（９）の通りである。
【００７０】
【数１８】
0003694477.tif 000021
【００７１】
前記式（９）を、回転インターポレータがアニメーションを行なう全てのブレークポイントの区間に拡張し、この全体区間［ｔ0、…、ｔL］に対する平均エラーＥm及び最大エラーＥpを導出すると下記式（１０）の通りである。
【数１９】
0003694477.tif 000022
【００７２】
ここで、平均エラーＥmを求めるために区間［ｔi-1、ｔi］で、下記式（１１）で表される部分和をまず求める。
【００７３】
【数２０】
0003694477.tif 000023
【００７４】
一方、下記式（１２）が成り立ち、これより、下記式（１３）が導出される。
【００７５】
【数２１】
0003694477.tif 000024
【００７６】
【数２２】
0003694477.tif 000025
【００７７】
前記式（１３）において、下記記号（Ｓ１０）の関数の積分区間［０、１］における定積分を算出するのが比較的難しいため、前記式（１３）を下記式（１４）に近似する。
【００７８】
【数２３】
0003694477.tif 000026
【００７９】
【数２４】
0003694477.tif 000027
【００８０】
また、下記式（１５）が成り立つ。
【００８１】
【数２５】
0003694477.tif 000028
【００８２】
前記式（１４）に示すように近似化された関数を用いて、部分和（下記記号（Ｓ１１））を求めると下記式（１６）の通りである。
【００８３】
【数２６】
0003694477.tif 000029
【００８４】
【数２７】
0003694477.tif 000030
【００８５】
前記式（１６）を整理すると、下記式（１７）の通りである。
【００８６】
【数２８】
0003694477.tif 000031
【００８７】
前記式（１７）で表される部分和（前記記号（Ｓ１１））を全体区間［ｔ0、ｔL］で積算して平均エラーＥmを求めると下記式（１８）の通りである。
【００８８】
【数２９】
0003694477.tif 000032
【００８９】
このとき、最大エラーＥpは、各区間［ｔi-1、ｔi］における最大エラー（下記記号（Ｓ１２））を下記式（１９）で求めたうちの最大値である。
【００９０】
【数３０】
0003694477.tif 000033
【００９１】
【数３１】
0003694477.tif 000034
【００９２】
以上説明した近似化された関数より、下記式（２０）が導出される。
【００９３】
【数３２】
0003694477.tif 000035
【００９４】
前記式（２０）より、全体区間［ｔ0、ｔL］の最大値は、下記式（２１）の通りである。
【００９５】
【数３３】
0003694477.tif 000036
【００９６】
図６に示す補間分析部８０は、キーの個数、正規化されたキー値の最小値と最大値、キーの解像度、キー値の解像度及びキーフラグの情報１１４を、エントロピーエンコーダ８６に送る。その際、補間分析部８０は、キー１１０をキー符号化部８２に送り、正規化されたキー値の最小値と最大値、及びキー値に関する情報１１２をキー値符号化部８４に送る。
【００９７】
次に、キー符号化部８２、及びキー値符号化部８４で実行されるキー符号化、及びキー値符号化について説明する。キー及びキー値は、各々キー符号化部８２及びキー値符号化部８４を通してＤＰＣＭ方式により量子化圧縮が実行される。このように量子化された情報は、その他の情報と共にエントロピーエンコーダ８６を経て最終圧縮されて符号化されたビットストリームとして出力端子ＯＵＴ３を通じ出力される。例えば、キー符号化部８２のＤＰＣＭ量子化部１０４は、補間分析部８０から入力されたキーをＤＰＣＭ量子化方式で符号化（すなわち、直前値と現在値との差を符号化）し、符号化された結果をエントロピーエンコーダ８６に出力する。その際、キー値符号化部８４のＤＰＣＭ量子化部１０６は、補間分析部８０から入力されたキー値及びキー値の最小値及び最大値を、ＤＰＣＭ量子化方式で符号化（すなわち、直前値と現在値との差を符号化）し、このように符号化された結果をエントロピーエンコーダ８６に出力する。
【００９８】
図１７は、量子化過程を示す図面であって、一般に使われるＤＰＣＭ符号化方式を示す。図１７を参照すると、キーの場合、下記式（２２）で表されるように最終誤差ｅを量子化して圧縮する。また、図１０は下記式（２２）を説明するための図面である。
【００９９】
【数３４】
0003694477.tif 000037
【０１００】
前記式（２２）より、直前値Ｋi-1と、更にその直前値Ｋi-2との差ｄ1を求めた後、その差ｄ1に直前値Ｋi-1を加算した近似値（下記記号（Ｓ１３））と現在値Ｋiとの差を最終誤差ｅとする。一方、簡単には直前値Ｋi-1と現在値Ｋiとの差を最終誤差ｅと見なしてもよい。
【０１０１】
【数３５】
0003694477.tif 000038
【０１０２】
図１８（Ａ）〜（Ｅ）は、本発明に係る符号化されたビットストリームのフォーマットを示す図面である。図１８（Ａ）は、本発明に係る符号化されたビットストリームのフォーマットであって、キーの個数ｎ＿ｋｅｙ、キーの解像度ｋ＿ｒｅｓ、キー値の解像度ｋｖ＿ｒｅｓ、キー値の最小値及び最大値［ｍｉｎ／ｍａｘ］（ここで、［  ］内はｍｉｎとｍａｘの配列を意味する。）２３０、キーフラグ［ｋｅｙ＿ｆｌａｇ］２３２、キー［ｋｅｙ］２３４及びキー値［ｋｖ］２３６で構成される。図１８（Ｂ）は、図１８（Ａ）に示すキー値の最小値及び最大値２３０のフォーマットを示し、図１８（Ｃ）はキーフラグ２３２のフォーマットを示し、図１８（Ｄ）はキー２３４のフォーマットを示し、図１８（Ｅ）はキー値２３６のフォーマットを示す。
【０１０３】
図１８（Ａ）に示すアレイ型キー値の最大値及び最小値２３０は、図１８（Ｂ）に示すように、Ｘ、Ｙ、Ｚの各座標軸に対応する最小値ｍｉｎx、ｍｉｎy、ｍｉｎz及びＸ、Ｙ、Ｚの各座標軸に対応する最大値ｍａｘx、ｍａｘy、ｍａｘzで構成される。アレイ型キーフラグ２３２は、図１８（Ｃ））に示すようにｎ個（ｎはキーの個数を示す。）のキーフラグｋｅｙ＿ｆｌａｇ0、ｋｅｙ＿ｆｌａｇ1k、ｋｅｙ＿ｆｌａｇ2、…、ｋｅｙ＿ｆｌａｇn-1で構成される。
【０１０４】
ここで、前記の表２に示すブレークポイントＰ１、Ｐ３、Ｐ６のように不要であると分類されたブレークポイントの値（分節値）に対するキー及びキーフラグに関するデータは省略される。したがって、前記アレイ型キー及びキーフラグは、元のキーの個数ｎよりも少ないデータより構成することができる。このようなアレイ型キー２３４は、図１８（Ｄ）に示すように、ｎ個のキーｋｅｙ0、ｋｅｙ1、ｋｅｙ2、…、ｋｅｙn-1で構成される。また、このようなアレイ型キー値２３６は、図１８（Ｅ）に示すようにｐ（ｐ≦ｎ、ｎはキーの個数）個の第１キー値ｋｖ＿Ｘ0、…、ｋｖ＿Ｘp、ｑ（ｑ≦ｎ、ｎはキーの個数）の第２キー値ｋｖ＿Ｙ0、…、ｋｖ＿Ｙq及びｚ（ｚ≦ｎ、ｎはキーの個数）の第３キー値ｋｖ＿Ｚ0、…、ｋｖ＿Ｚrで構成される。
【０１０５】
一方、本発明に係るアニメーション復元装置及びその方法は、前記圧縮過程とは逆の順序で実行される。図７に示すエントロピーデコーダ９０は、入力端子ＩＮ４を通して入力された符号化されたビットストリームを入力してエントロピーデコーディングし、このようにエントロピーデコーディングされた結果をキー復号化部９２及びキー値復号化部９４に各々出力する。
【０１０６】
また、キー復号化部９２及びキー値復号化部９４（図５（Ｂ）、図７）は各々、エントロピーデコーディングされた結果の量子化されたキー及びキー値が入力されると、キーフラグのような付加情報を用いて、前記キー及びキー値を量子化される前のデータに復元させる。すなわち、キー復号化部９２はエントロピーデコーディングされた結果が入力されるとキーを復号化し、キー値復号化部９４はこのようにエントロピーデコーディングされた結果が入力されるとキー値を復号化する。このため、キー復号化部９２は、ＤＰＣＭ逆量子化部１２６として具現することができる。また、キー値復号化部９４は、ＤＰＣＭ逆量子化部１２８として具現することができる。各ＤＰＣＭ逆量子化部１２６、１２８は、エントロピーデコーダ９０から入力されたデコーディングされたデータをＤＰＣＭ逆量子化方式で復号化する。
【０１０７】
また、補間復元部９６は、キー復号化部９２及びキー値復号化部９４で復号化されたデータが入力されると、これらを元のアニメーション軌跡に復元させる。補間復元部９６は、エントロピーデコーダ９０からキーの個数、正規化されたキー値の最小値と最大値、キーの解像度、キー値の解像度及びキーフラグなどの情報１２４が入力され、キー復号化部９２からキー１２０が入力され、キー値復号化部９４から正規化されたキー値の最小値と最大値、及びキー値に関する情報１２２が入力される。
【０１０８】
更に、補間復元部９６は、入力された情報に基づいて、空のキー値を線形補間法によって復元させる。例えば、前記の表２で、ブレークポイントＰ２のＸ軸キー値は、ブレークポイントＰ０、Ｐ４のキー値に基づいて線形補間法の過程を通して復元される。このため、補間復元部９６はキー及びキー値復元部９５として具現され、このように復元されたアニメーション軌跡としてキー、キー値の形で出力端子ＯＵＴ４を通して出力する。
【０１０９】
図１９は、プログラム言語として表現した本発明に係る復号化処理過程を説明するための図面である。図１９に示す表は、いわゆるビットストリームシンタックス（ｓｙｎｔａｘ）である。
本発明に係る線形近似化法を用いたアニメーション軌跡の圧縮方法、及び従来のＭＰＥＧ−４ＢＩＦＳを用いたインターポレータ圧縮方法を添付図面に基づき、比較して説明する。
【０１１０】
図２０〜図２３は、本発明に係る圧縮方法と従来の圧縮方法とを比較するために行なった実験アニメーションシーケンスのグラフであって、縦軸は歪曲度を、横軸はビット数を各々示し、本発明に係るアニメーション軌跡の圧縮方法は太線で、従来の圧縮方法は点線で示されている。図２０〜図２３は互いに異なるアニメーション軌跡を適用したときのシミュレーション結果を示している。図２１−図２０−図２３−図２２の順に優れた結果が得られることがわかる。同じビット率であれば、本発明に係る圧縮方法は従来のＢＩＦＳの方法よりも優れた画質を得ることができ、また、同じ画質であれば、本発明に係る圧縮方法は従来のＢＩＦＳの方法に比べて優れた圧縮率を実現できることがわかる。
【０１１１】
【発明の効果】
以上説明した通りに構成される本発明によれば以下の効果を奏する。
すなわち、アニメーション軌跡に対するインターポレータ表現の核心は、ブレークポイントを通じた軌跡の単純化であるにもかかわらず、従来のアニメーション軌跡の表現においてはキーの間隔が一定に形成されるため、ブレークポイントがオーバーサンプリングされるのに対し、本発明によればブレークポイントの分析を通して、最小のブレークポイントで単純化され、符号化されたビットストリームを得ることができるので、ＤＰＣＭ方式の圧縮を実行することによってブレークポイントの間にも線形相関性を高く維持することができ、このような高い相関性によって効率的に圧縮することが可能な線形近似化法を用いたアニメーション軌跡の圧縮及び復元方法、並びにその装置を提供することができる。
【図面の簡単な説明】
【図１】一般の３次元アニメーションにおいてアニメーション軌跡を説明するための図面である。
【図２】仮想現実モデリング言語またはＭＰＥＧ−４で使われるアニメーション軌跡の表現例を示す。
【図３】３次元アニメーションのデータ形式を説明するための図面である。
【図４】図４（Ａ）はアニメーション軌跡に対する従来の圧縮装置のブロック図、図４（Ｂ）はアニメーション軌跡に対する従来の復元装置のブロック図である。
【図５】図５（Ａ）は本発明に係るアニメーション軌跡の圧縮装置のブロック図、図５（Ｂ）は本発明に係るアニメーション軌跡の復元装置のブロック図である。
【図６】図５（Ａ）に示す本発明に係るアニメーション軌跡の圧縮装置において、本発明の望ましい１実施形態のブロック図である。
【図７】図５（Ｂ）に示す本発明に係るアニメーション軌跡の復元装置において、本発明の望ましい１実施形態のブロック図である。
【図８】線形近似化法を用いたブレークポイント抽出の本発明に係る望ましい１実施形態を説明するための図面であって、元のアニメーションの軌跡を示す図である。
【図９】線形近似化法を用いたブレークポイント抽出の本発明に係る望ましい１実施形態を説明するための図面であって、軌跡の両端の点Ａ、Ｂを探す状態を示す図である。
【図１０】線形近似化法を用いたブレークポイント抽出の本発明に係る望ましい１実施形態を説明するための図面であって、元の軌跡と最も近いブレークポイントを選択する過程を示す図である。
【図１１】線形近似化法を用いたブレークポイント抽出の本発明に係る望ましい１実施形態を説明するための図面であって、１次抽出されたブレークポイントＡ、Ｂ、Ｃを示す図である。
【図１２】線形近似化法を用いたブレークポイント抽出の本発明に係る望ましい１実施形態を説明するための図面であって、元の軌跡と近い２次ブレークポイントを抽出する過程を示す図である。
【図１３】線形近似化法を用いたブレークポイント抽出の本発明に係る望ましい１実施形態を説明するための図面であって、２次抽出されたブレークポイントＡ、Ｂ、Ｃ、Ｄを示す図である。
【図１４】線形近似化法を用いたブレークポイント抽出の本発明に係る望ましい１実施形態を説明するための図面であって、３次抽出されたブレークポイントＡ、Ｂ、Ｃ、Ｄ、Ｅを示す図である。
【図１５】線形近似化法を用いたブレークポイント抽出の本発明に係る望ましい１実施形態を説明するための図面であって、４次抽出されたブレークポイントＡ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆを示す図である。
【図１６】実際のアニメーション軌跡と近似されたアニメーション軌跡との差を求める方法を説明するための図面である。
【図１７】量子化過程を示す図面であって、一般に使われるＤＰＣＭ符号化方式を示す。
【図１８】（Ａ）〜（Ｅ）は、本発明に係る符号化されたビットストリームのフォーマットを示す図面である。
【図１９】文法表現に変えて表現した本発明に係る復号化処理過程を説明するための図面である。
【図２０】本発明に係る圧縮方法と従来の圧縮方法とを比較するために行なった実験のアニメーションシーケンスに関するグラフであって、１例のアニメーション軌跡に適用したときのシミュレーション結果を示す図である。
【図２１】本発明に係る圧縮方法と従来の圧縮方法とを比較するために行なった実験のアニメーションシーケンスに関するグラフであって、１例のアニメーション軌跡に適用したときのシミュレーション結果を示す図である。
【図２２】本発明に係る圧縮方法と従来の圧縮方法とを比較するために行なった実験のアニメーションシーケンスに関するグラフであって、１例のアニメーション軌跡に適用したときのシミュレーション結果を示す図である。
【図２３】本発明に係る圧縮方法と従来の圧縮方法とを比較するために行なった実験のアニメーションシーケンスに関するグラフであって、１例のアニメーション軌跡に適用したときのシミュレーション結果を示す図である。
【図２４】元のアニメーション軌跡の上で、各時間でのｎ＋１個の各ブレークポイントにおけるキー値（Ｑ0、Ｑ1、Ｑ2、…、Ｑn）を示す図である。
【図２５】アニメーション軌跡の上にある各ブレークポイントの中から両端に該当する２個のブレークポイント（Ｑ0、Ｑn）を選択する様子を示す図である。
【図２６】選択された両端のブレークポイントを除いた残りのブレークポイントの中から１個のブレークポイント（３番目のブレークポイント）を選択する過程を示す図である。
【図２７】候補２の軌跡が選択されたことを示す図である。
【図２８】図２７で選択された３つのブレークポイントを除いた残りのブレークポイントの中から１個のブレークポイントを選択した後、前述した図２６、図２７のような過程を実行して４番目のブレークポイントを選択する様子を示す図である。
【図２９】図２７において、候補１の軌跡が選択されたことを示す図である。
【符号の説明】
８０  補間分析部
８２  キー符号化部
８４  キー値符号化部
８６  エントロピーエンコーダ
９０エントロピーデコーダ
９２  キー復号化部
９４  キー値復号化部
９６  補間復元部
１００  正規化部
１０２  ブレークポイント最小化部
１０４、１０６  ＤＰＣＭ量子化部
１１０  キー
１１２  正規化されたキー値の最小値と最大値、及びキー値に関する情報
１１４  キーフラグの情報
１２２  正規化されたキー値の最小値と最大値、及びキー値に関する情報
１２４  キーの個数、正規化されたキー値の最小値と最大値、キーの解像度、キー値の解像度及びキーフラグなどの情報
１２６  ＤＰＣＭ逆量子化部
１２８  ＤＰＣＭ逆量子化部
【図１】
0003694477.tif 000039
【図２】
0003694477.tif 000040
【図３】
0003694477.tif 000041
【図４】
0003694477.tif 000042
【図５】
0003694477.tif 000043
【図６】
0003694477.tif 000044
【図７】
0003694477.tif 000045
【図８】
0003694477.tif 000046
【図９】
0003694477.tif 000047
【図１０】
0003694477.tif 000048
【図１１】
0003694477.tif 000049
【図１２】
0003694477.tif 000050
【図１３】
0003694477.tif 000051
【図１４】
0003694477.tif 000052
【図１５】
0003694477.tif 000053
【図１６】
0003694477.tif 000054
【図１７】
0003694477.tif 000055
【図１８】
0003694477.tif 000056
【図１９】
0003694477.tif 000057
【図２０】
0003694477.tif 000058
【図２１】
0003694477.tif 000059
【図２２】
0003694477.tif 000060
【図２３】
0003694477.tif 000061
【図２４】
0003694477.tif 000062
【図２５】
0003694477.tif 000063
【図２６】
0003694477.tif 000064
【図２７】
0003694477.tif 000065
【図２８】
0003694477.tif 000066
【図２９】
0003694477.tif 000067