(57)【特許請求の範囲】
【請求項１】
グラフィックアニメーションデータのうち時間変数に該当するキーデータを符号化させる符号化装置において、
前記キーデータを量子化して量子化されたデータを生成する量子化器と、
前記量子化されたデータを差分パルス符号変調（ＤＰＣＭ）処理し、ＤＰＣＭ処理されたデータを入力としてＤＰＣＭ処理を繰り返し行いつつ生成されるＮ次のＤＰＣＭデータのうち最も低い散布度を有するＤＰＣＭデータを選択して出力するＤＰＣＭ処理部と、
前記ＤＰＣＭ処理部から出力されるＤＰＣＭデータに存在する極端値を除去してデータの変化幅を狭める極端値除去部と、
前記極端値除去部から出力されるデータから２進ビットの冗長度を除去して圧縮及び符号化された２進ビットストリームを生成するエントロピエンコーダとを含み、
前記極端値除去部は、
前記ＤＰＣＭ処理部から出力されるデータのうち最も高い頻度数を有するデータを零に変え、残りのデータは零を中心としてその平均値が零に近いように分布させる前処理部と、
前記前処理されたデータから正の極端値及び負の極端値を除去して最大値と最小値との間の範囲を狭める主処理部とを含むことを特徴とする符号化装置。
【請求項２】
前記ＤＰＣＭ処理部は、
前記量子化されたデータをＤＰＣＭ処理し、ＤＰＣＭ処理されたデータを入力としてＤＰＣＭ処理を繰り返し行いつつＮ次のＤＰＣＭデータを生成するＮ次ＤＰＣＭ処理部と、
前記Ｎ次ＤＰＣＭ処理部から出力されるＤＰＣＭデータの散布度を次数別に求めて出力する散布度計算部と、
前記散布度計算部で求めた散布度のうち最も低い散布度を有する次数のＤＰＣＭデータを選択して前記極端値除去部に出力する最低散布度抽出部とを含むことを特徴とする請求項１に記載の符号化装置。
【請求項３】
前記前処理部は、
前記ＤＰＣＭ処理部から出力される差分データのうち最も高い頻度数を有するデータ（最頻値）を求めるモード生成器と、
前記差分データから前記モード生成器で求めた最頻値を引いて最頻値だけシフトさせるシフト処理部と、
前記シフト処理されたデータのうち零以下の値を有するデータを正数に変えるフォルド処理部と、
前記フォルド処理部で処理されたデータからその大きさに基づき所定の値を引いて最大値と最小値とのデータ範囲を狭める減算処理部とを含むことを特徴とする請求項１に記載の符号化装置。
【請求項４】
前記主処理部は、
前記前処理されたデータから最大値及び最小値を抽出してその絶対値を比較し、比較された結果に基づき最大値の半分よりも大きいデータを零に近い値に変えるディバイド−ダウン処理、または最小値の半分よりも小さいデータを零に近い値に変えるディバイド−アップ処理をＭ次に亘って繰り返し行い、ディバイド処理されたデータを生成するディバイド−アップ／ダウン処理部と、
前記ディバイド−アップ／ダウン処理部から出力されるディバイド−アップデータ又はディバイド−ダウンデータの散布度を各次数別に求め、最も低い散布度を有する次数のディバイド処理されたデータを選択して出力するデータ出力部とを含むことを特徴とする請求項１に記載の符号化装置。
【請求項５】
グラフィックアニメーションデータのうち時間変数に該当するキーデータを符号化させる符号化方法において、
（ａ）前記キーデータを量子化して量子化されたデータを生成する段階と、
（ｂ）前記量子化されたデータをＤＰＣＭ処理し、ＤＰＣＭ処理されたデータを入力としてＤＰＣＭ処理を繰り返し行いつつ生成されるＮ次のＤＰＣＭデータのうち最も低い散布度を有するデータを選択して出力する段階と、
（ｃ）前記（ｂ）段階で出力されるデータに存在する極端値を除去してデータの変化幅を狭める段階と、
（ｄ）前記（ｃ）段階で出力されるデータから２進ビットの冗長度を除去して圧縮及び符号化された２進ビットストリームを生成する段階とを含み、
前記（ｂ）段階は、
（ｂ１）前記量子化されたデータをＤＰＣＭ処理し、ＤＰＣＭ処理されたデータを入力としてＤＰＣＭ処理を繰り返し行いつつＮ次のＤＰＣＭデータを生成する段階と、
（ｂ２）前記（ｂ１）段階で生成された各次数別ＤＰＣＭデータの散布度を求める段階と、
（ｂ３）前記（ｂ２）段階で求めた散布度のうち最も低い散布度を有する次数のＤＰＣＭデータを選択して出力する段階とを含み、
前記（ｃ）段階は、
（ｃ１）前記（ｂ）段階で生成された差分データのうち最も高い頻度数を有する差分値を最頻値として求める段階と、
（ｃ２）前記差分データの各々から前記最頻値を引く段階と、
（ｃ３）前記（ｃ２）段階で処理されたデータのうち零以下の値を有するデータを正数に変える段階と、
（ｃ４）前記（ｃ３）段階で処理されたデータからその大きさに基づき所定の値を引いて最大値と最小値との間のデータ範囲を狭める段階と、
（ｃ５）最大値及び最小値を抽出してその絶対値を比較し、比較された結果に基づき最大値の半分よりも大きいデータを零に近いに変えるか、最小値の半分よりも小さいデータを零に近い値に変える処理をＭ次に亘って繰り返し行い、ディバイド処理されたデータを生成する段階と、
（ｃ６）前記（ｃ５）段階で生成されたデータの散布度を各次数別に求め、最も低い散布度を有する次数のディバイド処理されたデータを極端値が除去されたデータとして選択して出力する段階とを含むことを特徴とする符号化方法。
【請求項６】
請求項５に記載の符号化方法をコンピュータで実行可能なプログラムコードにて記録した記録媒体。
【請求項７】
伝送しようとするデータを符号化させる符号化装置において、符号化効率を高めるために前記伝送しようとするデータに存在する極端値を除去する方法であって、
（ａ）前記伝送しようとするデータのうち最も高い頻度数を有するデータを最頻値として求める段階と、
（ｂ）前記伝送しようとするデータの各々から前記最頻値を引く段階と、
（ｃ）前記（ｂ）段階で処理されたデータのうち零以下の値を有するデータを正数に変える段階と、
（ｄ）前記（ｃ）段階で処理されたデータからその大きさに基づき所定の値を引いて最大値と最小値との間のデータ範囲を狭める段階と、
（ｅ）最大値及び最小値を抽出してその絶対値を比較し、比較された結果に基づき最大値の半分よりも大きいデータを零に近い値に変えるか、又は最小値の半分よりも小さいデータを零に近い値に変える処理をＭ次に亘って繰り返し行い、ディバイド処理されたデータを生成する段階と、
（ｆ）前記（ｅ）段階で生成されたデータの散布度を各次数別に求め、最も低い散布度を有する次数のディバイド処理されたデータを極端値が除去されたデータとして選択して出力する段階とを含むことを特徴とする極端値除去方法。
【請求項８】
前記（ｃ）段階は、
（ｃ１）前記（ｂ）段階で出力された値が零以上であるか否かを判断する段階と、
（ｃ２）前記（ｃ１）段階で零よりも小さいと判断されれば、その絶対値を２倍にした後に１を引いて前記（ｂ）段階で生成されたデータを正数に変える段階と、
（ｃ３）前記（ｃ１）段階で零よりも大きいと判断されれば、前記（ｃ２）段階で生成されたデータ値を２倍にする段階とを含むことを特徴とする請求項７に記載の極端値除去方法。
【請求項９】
前記（ｄ）段階は、
（ｄ１）前記（ｃ）段階で生成されたデータが最大値の半分よりも大きいか否かを判断する段階と、
（ｄ２）前記（ｄ１）段階で最大値の半分よりも大きいと判断されれば、前記（ｃ）段階で生成されたデータから（最大値＋１）を引いて負数に変える段階と、
（ｄ３）前記（ｄ１）段階で最大値の半分よりも大きくないと判断されれば、その値をそのまま保つ段階とを含むことを特徴とする請求項７に記載の極端値除去方法。
【請求項１０】
前記（ｅ）段階は、
（ｅ１）前記（ｄ）段階で生成されたデータの最大値及び最小値を抽出してその絶対値を比較する段階と、
（ｅ２）前記（ｅ１）段階で最大値の絶対値が大きければ、最大値の半分よりも大きいデータを零に近い値に変えるディバイド−ダウン処理を行った後に前記（ｄ１）段階へ戻り、ディバイド次数を１だけインクリメントする段階と、
（ｅ３）前記（ｅ１）段階で最小値の絶対値が大きければ、最小値の半分よりも小さいデータを零に近い値に変えるディバイド−アップ処理を行った後に前記（ｅ１）段階へ戻り、ディバイド次数を１だけインクリメントする段階と、
（ｅ４）前記ディバイド次数がＭ次になれば、前記ディバイド−ダウン又はディバイド−アップ処理されたデータの散布度を次数別に求める段階と、
（ｅ５）前記（ｅ４）段階で最も低い散布度を有するディバイド−ダウン又はディバイド−アップデータを極端値が除去されたデータとして生成する段階とを含むことを特徴とする請求項９に記載の極端値除去方法。
【請求項１１】
前記（ｅ２）段階は、
（ｅ２１）前記（ｅ１）段階で最大値の絶対値が大きければ、前記（ｄ）段階で前記ディバイド処理されたデータが零以上であるか否かを判断する段階と、
（ｅ２２）前記（ｅ２１）段階で前記ディバイド処理されたデータが零よりも小さければ、前記ディバイド処理されたデータに２をかけた値をディバイドダウンされたデータとして生成する段階と、
（ｅ２３）前記（ｅ２１）段階で前記ディバイド処理されたデータが零以上であれば、前記ディバイド処理されたデータが最大値の半分よりも大きいか否かを判断する段階と、
（ｅ２４）前記（ｅ２３）段階で前記ディバイド処理されたデータが最大値の半分よりも大きいと判断されれば、下記式により求められるデータをディバイドダウンされたデータとして生成する段階と、
DiK = 1-2(max(EiK)-EiK+1)
（ここで、DiKはディバイドダウンされたデータであり、EiK は前記ディバイド処理されたデータであり、max(EiK) は最大値である。）
（ｅ２５）前記（ｅ２３）段階で前記ディバイド処理されたデータが最大値の半分よりも大きくないと判断されれば、前記ディバイド処理されたデータをディバイドダウンされたデータとして生成する段階とを含むことを特徴とする請求項１０に記載の極端値除去方法。
【請求項１２】
前記（ｅ３）段階は、
（ｅ３１）前記（ｅ１）段階で最小値の絶対値が大きければ、前記（ｄ）段階で前記ディバイド処理されたデータが負数であるか否かを判断する段階と、
（ｅ３２）前記（ｅ３１）段階で前記ディバイド処理されたデータが負数でないと判断されれば、前記ディバイド処理されたデータをそのままディバイドアップされたデータとして生成する段階と、
（ｅ３３）前記（ｅ３１）段階で前記ディバイド処理されたデータが負数であると判断されれば、前記ディバイド処理されたデータが最小値の半分よりも小さいか否かを判断する段階と、
（ｅ３４）前記（ｅ３３）段階で前記ディバイド処理されたデータが最小値の半分よりも小さいと判断されれば、下記式により求められる値をディバイドアップ処理されたデータとして生成する段階と、
DiK = 1+2(min(EiK)-EiK-1)
（ここで、DiK はディバイドアップされたデータであり、EiK は前記ディバイド処理されたデータであり、min(EiK) は最小値である。）
（ｅ３５）前記（ｅ３３）段階で前記ディバイド処理されたデータが最小値の半分よりも小さくないと判断されれば、前記ディバイド処理されたデータに２をかけた値をディバイドアップされたデータとして生成する段階とを含むことを特徴とする請求項１０に記載の極端値除去方法。
【請求項１３】
請求項７に記載の極端値除去方法をコンピュータで実行可能なプログラムコードにて記録した記録媒体。
【請求項１４】
グラフィックアニメーションデータのうち時間変数に該当するキーデータを符号化及び復号させるデータ処理システムにおいて、
前記キーデータを量子化して量子化されたデータを生成する量子化器と、
前記量子化されたデータをＤＰＣＭ処理し、ＤＰＣＭ処理されたデータを入力としてＤＰＣＭ処理を繰り返し行いつつ生成されるＮ次のＤＰＣＭデータのうち最も低い散布度を有するデータを選択して出力するＤＰＣＭ処理部と、
前記ＤＰＣＭ処理部から出力されるデータに存在する極端値を除去してデータの変化幅を狭める極端値除去部と、
前記極端値除去部から出力されるデータから２進ビットの冗長度を除去して圧縮及び符号化された２進ビットストリームを生成するエントロピエンコーダを含む符号化器と、
前記符号化器で圧縮及び符号化されて伝送される２進ビットストリームを受信し、前記符号化過程の逆過程を経て前記２進ビットストリームを元のキーデータに復元する復号器とを含み、
前記極端値除去部は、
前記ＤＰＣＭ処理部から出力されるデータのうち最も高い頻度数を有するデータを零に変え、残りのデータは零を中心としてその平均値が零に近いように分布させる前処理部と、
前記前処理されたデータから正の極端値及び負の極端値を除去して最大値と最小値との間の範囲を狭める主処理部とを含むことを特徴とするデータ処理システム。
【請求項１５】
外部の符号化装置から最も低い散布度を有するＤＰＣＭ次数情報、最も低い散布度を有するディバイド次数情報及び前記符号化装置での極端値除去過程に使われる最頻値、最大値及びディバイド次数別極端値情報を含むヘッダデータと、ＤＰＣＭ及び極端値が除去されたキーデータを圧縮及び符号化した２進ビットストリームを伝送されてグラフィックアニメーションデータのうち時間変数に該当する元のキーデータに復元する復号装置において、
前記伝送された２進ビットストリームを復元して前記ヘッダデータ及び前記ＤＰＣＭ並びに極端値が除去されたキーデータを復元するエントロピデコーダと、
前記エントロピデコーダで復元されたヘッダデータの最頻値、最大値及びディバイド次数別極端値情報に基づき、前記符号化装置での極端値除去過程で除去された極端値を復元する逆極端値除去部と、
前記逆極端値除去部で極端値が復元されたキーデータを前記最も低い散布度を有するＤＰＣＭ次数に該当する回数だけ繰り返して逆ＤＰＣＭ処理を行い、その処理結果を出力する逆ＤＰＣＭ処理部と、
前記逆ＤＰＣＭ処理部から出力される逆ＤＰＣＭデータを逆量子化して逆量子化されたデータを前記元のキーデータとして生成する逆量子化器とを含み、
前記逆極端値除去部は、
前記復元されたヘッダデータで前記ディバイド次数別極端値を零と比較し、零以上であれば前記エントロピデコーダで復元されたキーデータを逆ディバイドダウン処理し、零よりも小さければ逆ディバイドアップ処理して正の極端値又は負の極端値を復元する主処理部と、
前記主処理部で極端値が復元されたデータを前記最頻値だけシフトして零を中心として分布するキーデータを最頻値を中心として分布するように復元する後処理部とを含むことを特徴とする復号装置。
【請求項１６】
前記後処理部は、
前記主処理部で極端値が復元されたデータにその大きさに基づき所定の値を加えて前記極端値が復元されたデータをいずれも零以上に変える逆減算処理部と、
前記逆減算処理されたデータで奇数を負の奇数に変える逆フォルド処理部と、
前記逆フォルド処理されたデータを前記最頻値だけシフトして零を中心として分布するデータを最頻値を中心として分布するように復元する逆シフト処理部とを含むことを特徴とする請求項１５に記載の復号装置。
【請求項１７】
外部の符号化装置から最も低い散布度を有するＤＰＣＭ次数情報、最も低い散布度を有するディバイド次数情報及び前記符号化装置での極端値除去過程に使われる最頻値、最大値及びディバイド次数別極端値情報を含むヘッダデータと、ＤＰＣＭ及び極端値が除去されたキーデータを圧縮及び符号化した２進ビットストリームを伝送されてグラフィックアニメーションデータのうち時間変数に該当する元のキーデータに復元する復号装置で行われる復号方法において、
（ａ）前記伝送された２進ビットストリームを復元して前記ヘッダデータ及び前記ＤＰＣＭ並びに極端値が除去されたキーデータを復元する段階と、
（ｂ）前記（ａ）段階で復元されたヘッダデータの最頻値、最大値及びディバイド次数別極端値情報に基づき、前記符号化装置での極端値除去過程で除去された極端値を復元する段階と、
（ｃ）前記（ｂ）段階で極端値が復元されたキーデータを前記最も低い散布度を有するＤＰＣＭ次数に該当する回数だけ繰り返して逆ＤＰＣＭ処理を行う段階と、
（ｄ）前記（ｃ）段階で逆ＤＰＣＭ処理されたデータを逆量子化して逆量子化されたデータを前記元のキーデータとして生成する段階とを含み、
前記（ｂ）段階は、
（ｂ１）前記復元されたヘッダデータで前記ディバイド次数別極端値を零と比較し、零以上であれば前記（ａ）段階で復元されたキーデータを逆ディバイドダウン処理し、零よりも小さければ逆ディバイドアップ処理して正の極端値又は負の極端値を復元する段階と、
（ｂ２）前記（ｂ１）段階で極端値が復元されたデータを前記最頻値だけシフトして零を中心として分布するキーデータを最頻値を中心として分布するように復元する段階とを含むことを特徴とする復号方法。
【請求項１８】
前記（ｂ１）段階の逆ディバイドダウン処理は、
（ｂ２１）前記（ａ）段階で復元されたキーデータが零以上であれば、前記復元されたキーデータを逆ディバイドダウンされたデータとして生成する段階と、
（ｂ２２）前記（ａ）段階で復元されたキーデータが負の奇数であれば、下記式により求められるデータを逆ディバイドダウンされたデータとして生成する段階と、
0003699066.tif 000010
（ここで、EiKは逆ディバイドダウン処理されたデータであり、maxiは次数別極端値であり、DiKは前記（ａ）段階で復元されたキーデータである。）
（ｂ２３）前記（ａ）段階で復元されたキーデータが負の偶数であれば、前記（ａ）段階で復元されたキーデータを２で割った値を逆ディバイドダウンされたデータとして生成する段階とを含み、
前記（ｂ１）段階の逆ディバイドアップ処理は、
（ｂ２４）前記（ａ）段階で復元されたキーデータが零以上であれば、前記復元されたキーデータを逆ディバイドアップされたデータとして生成する段階と、
（ｂ２５）前記（ａ）段階で復元されたキーデータが負の奇数であれば、下記式により求められるデータを逆ディバイドアップされたデータとして生成する段階と、
0003699066.tif 000011
（ここで、EiKは逆ディバイドアップ処理されたデータであり、maxiは次数別極端値であり、DiKは前記（ａ）段階で復元されたキーデータである。）
（ｂ２６）前記（ａ）段階で復元されたキーデータが負の偶数であれば、前記（ａ）段階で復元されたキーデータを２で割った値を逆ディバイドアップされたデータとして生成する段階とを含むことを特徴とする請求項１７に記載の復号方法。
【請求項１９】
前記（ｂ２）段階は、
（ｂ２１）前記（ｂ１）段階で極端値が復元されたデータにその大きさに基づき前記最大値を加えて前記極端値が復元されたデータをいずれも零以上に変える段階と、
（ｂ２２）前記（ｂ２１）段階で処理されたデータで奇数を負の奇数に変える逆フォルド処理段階と、
（ｂ２３）前記（ｂ２２）段階で逆フォルド処理されたデータを前記最頻値だけシフトして零を中心として分布するデータを前記最頻値を中心として分布するように復元する逆シフト処理段階とを含むことを特徴とする請求項１７に記載の復号方法。
【請求項２０】
前記（ｂ２１）段階は、
前記（ｂ１）段階で生成されたデータが零以上であるか否かを判断し、零以上であると判断されればその値を保ち、零よりも小さいと判断されれば前記（ｂ１）段階で生成されたデータに（最大値＋１）を加えることを特徴とする請求項１９に記載の復号方法。
【請求項２１】
前記（ｂ２２）段階は、
（ｂ２２１）前記（ｂ２１）段階で処理されたデータが奇数であれば、下記式により求められるデータを逆フォルド処理されたデータとして生成する段階と、
0003699066.tif 000012
（ここで、EKは逆フォルド処理されたデータであり、DKは（ｂ２１）段階で処理されたデータである。）
（ｂ２２２）前記（ｂ２１）段階で処理されたデータが零又は偶数であれば、前記（ｂ２１）段階で処理されたデータを２で割った値を逆フォルド処理されたデータとして生成する段階とを含むことを特徴とする請求項１９に記載の復号方法。
【請求項２２】
請求項１７に記載の復号方法をコンピュータで実行可能なプログラムコードにて記録した記録媒体。
【請求項２３】
請求項５に記載の符号化方法を実行する手段としてコンピュータを機能させるためのプログラム。
【請求項２４】
請求項７に記載の極端値除去方法を実行する手段としてコンピュータを機能させるためのプログラム。
【請求項２５】
請求項１７に記載の復号方法を実行する手段としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はグラフィックアニメーションデータの符号化装置に係り、特に、グラフィックアニメーションデータのうち時間変数に該当するキー情報を符号化／復号させる装置及びその方法に関する。
【０００２】
【従来の技術】
グラフィックアニメーションは２次元又は３次元オブジェクトの形態及び属性情報を表現し、各オブジェクトの形態や属性などの経時的な変化及び動き情報を様々な方法により表現する。オブジェクトを時間軸上でアニメーションするための代表的な表現形式として、バーチュアル・リアリティ・マークアップ・ランゲージ（ＶＲＭＬ）がある。このアニメーション方式は３次元オブジェクトに対するキーフレーミング法により任意の時間軸上に特定のキーフレーミングを設定し、設定された各キーフレーム間のアニメーションを線形補間法により表現する。この方式で使われるキーフレームはインタポレータノードを通して定義されるが、このノードはキーフレームの時間軸上の位置を表わすキーデータと、該当キーでキーフレーム属性と動き情報を表わすキー値データとによりフィールドを構成する。すなわち、キーはアニメーションを表現する時間を０〜１の不連続した値で表わし、キー値は各キーが表わす時間で合成映像内のあるオブジェクトの属性及び位置値を表わす。図１は、キー及びキー値の相関関係の一例を示すグラフである。
【０００３】
一方、区分的な線形補間法特性を有するキーフレーミング方式により実際の運動体と類似した自然なアニメーションを表現する場合には、インタポレータノードを通じて大量のキーフレーム情報が与えられる必要があり、これはアプリケーション分野に適用する時にコスト及び効率の面で深刻な短所として現れる。すなわち、オフラインのアプリケーションでは膨大な量の３次元アニメーションデータを保存するための大容量の記憶装置が必要となる。また、オンラインのアプリケーションではオフラインアプリケーションでの問題だけではなく、サーバからユーザ端末へと３次元アニメーションデータを伝送する時に伝送路の大容量化及び高速化が要求される。加えて、伝送エラーの発生確率が高くなるに伴い、データの信頼性低下が問題となる。このような側面から、インタポレータノードのデータの量を減少させる効果的な圧縮及び符号化機能が望まれる。
【０００４】
図２は、従来の技術による符号化及び復号装置の概略ブロック図である。
【０００５】
図２に示すように、従来技術の手法では、一般に、差分パルス符号変調方式（ＤＰＣＭ）によりアニメーションデータを符号化させている。これは、キーフレーミングアニメーション方式の特性がＤＰＣＭ方式に好適であって、データを圧縮するのに有効な方法であるためである。また、このＤＰＣＭにより符号化を行う方法は、ＭＰＥＧ−４ ＢＩＦＳ（Ｂｉｎａｒｙ Ｆｏｒｍａｔ ｆｏｒ Ｓｃｅｎｅ）符号化の手法としても用いられている。
【０００６】
図２に示すように、ＭＰＥＧ−４ ＢＩＦＳ符号化手法のキーデータ符号化法は、ＤＰＣＭ処理が一回のみである１次ＤＰＣＭを用いた符号化法である。図２において、量子化器１０５は符号化するインタポレータノードのキーデータＫを量子化する。ＤＰＣＭ処理部１１０は量子化されたキーデータＱK中の時間軸上で隣り合うデータ間の差分値ＥKを生成する。ＤＰＣＭ処理されたキーデータはエントロピエンコーダ１１５に入力されて圧縮され、２進ビットストリーム１２０として生成される。符号化器１００で生成した圧縮された２進ビットストリーム１２０は符号化器１００とは逆の処理として構成される復号器１５０を通じて復元されてキーデータＫ＾として生成される。すなわち、圧縮された２進ビットストリーム１２０はエントロピデコーダ１５５、逆ＤＰＣＭ処理部１６０及び逆量子化器１６５を経つつキーデータＫ＾に復元される。
【０００７】
図３は図２に示すＤＰＣＭ処理部１１０の詳細図であり、図４は図２に示す逆ＤＰＣＭ処理部１６０の詳細図である。
【０００８】
一方、エントロピエンコーダ１１５での符号化効率を高めるためには、符号化するデータ、すなわち、ＤＰＣＭ処理部１１０から出力されるデータＥKの冗長度が高いことが好ましい。しかし、図２に示すように、一括的に１次ＤＰＣＭのみ行う場合、１次ＤＰＣＭを通して得られた符号化に好適なデータ以外のデータでは圧縮効果があまり高くないという短所がある。
【０００９】
【発明が解決しようとする課題】
本発明が解決しようとする第１の課題は、符号化するキーデータの冗長度を高めて符号化効率を高める符号化及び復号装置を提供することである。
【００１０】
本発明が解決しようとする第２の課題は、前記符号化及び復号装置で行われる符号化及び復号方法を提供することである。
【００１１】
本発明が解決しようとする第３の課題は、前記符号化及び復号方法をコンピュータで実行可能なプログラムコードにて記録した記録媒体を提供することである。
【００１２】
本発明が解決しようとする第４の課題は、前記符号化装置で前記符号化方法により生成されるビットストリームをコンピュータで読み取り可能なプログラムコードにて記録した記録媒体を提供することである。
【００１３】
本発明が解決しようとする第５の課題は、符号化装置での符号化効率を高めるために、符号化するデータに存在する極端値を除去する方法を提供することである。
【００１４】
本発明が解決しようとする第６の課題は、前記符号化装置を用いたデータ処理システムを提供することである。
【００１５】
本発明が解決しようとする第７の課題は、前記符号化及び復号方法を実行する手段としてコンピュータを機能させるためのプログラムを提供することである。
【００１６】
【課題を解決するための手段】
前記第１の課題を解決するために、グラフィックアニメーションデータのうち時間変数に該当するキーデータを符号化させる本発明に係る符号化装置は、キーデータを量子化して量子化されたデータを生成する量子化器と、量子化されたデータをＤＰＣＭ処理し、ＤＰＣＭ処理されたデータを入力としてＤＰＣＭ処理を繰り返し行いつつ生成されるＮ次のＤＰＣＭデータのうち最も低い散布度を有するＤＰＣＭデータを選択して出力するＤＰＣＭ処理部と、ＤＰＣＭ処理部から出力されるＤＰＣＭデータに存在する極端値を除去してデータの変化幅を狭める極端値除去部と、極端値除去部から出力されるデータから２進ビットの冗長度を除去して圧縮及び符号化された２進ビットストリームを生成するエントロピエンコーダとを含むことを特徴とする。
【００１７】
前記第１の課題を解決するために、外部の符号化装置から最も低い散布度を有するＤＰＣＭ次数情報、最も低い散布度を有するディバイド次数情報及び前記符号化装置における極端値除去過程に使われる最頻値、最大値及びディバイド次数別極端値情報を含むヘッダデータと、ＤＰＣＭ及び極端値が除去されたキーデータを圧縮及び符号化した２進のビットストリームを伝送されてグラフィックアニメーションデータのうち時間変数に該当する元のキーデータに復元する本発明に係る本発明に係る復号装置は、伝送された２進ビットストリームを復元してヘッダデータ及びＤＰＣＭ並びに極端値が除去されたキーデータを復元するエントロピデコーダと、エントロピデコーダで復元されたヘッダデータの最頻値、最大値及びディバイド次数別極端値情報に基づき、符号化装置で行われる極端値除去過程で除去された極端値を復元する逆極端値除去部と、逆極端値除去部で極端値が復元されたキーデータを最も低い散布度を有するＤＰＣＭ次数に該当する回数だけ繰り返して逆ＤＰＣＭ処理を行い、その処理結果を出力する逆ＤＰＣＭ処理部と、逆ＤＰＣＭ処理部から出力される逆ＤＰＣＭデータを逆量子化し、逆量子化されたデータを元のキーデータとして生成する逆量子化器とを含むことを特徴とする。
【００１８】
前記第２の課題を解決するために、グラフィックアニメーションデータのうち時間変数に該当するキーデータを符号化させる本発明に係る符号化方法は、キーデータを量子化して量子化されたデータを生成する（ａ）段階と、量子化されたデータをＤＰＣＭ処理し、ＤＰＣＭ処理されたデータを入力としてＤＰＣＭ処理を繰り返し行いつつ生成されるＮ次のＤＰＣＭデータのうち最も低い散布度を有するデータを選択して出力する（ｂ）段階と、ＤＰＣＭ処理部から出力されるデータに存在する極端値を除去してデータの変化幅を狭める（ｃ）段階と、極端値除去部から出力されるデータから２進ビットの冗長度を除去して圧縮及び符号化された２進ビットストリームを生成する（ｄ）段階とを含むことを特徴とする。
【００１９】
前記第２の課題を解決するために、外部の符号化装置から最も低い散布度を有するＤＰＣＭ次数情報、最も低い散布度を有するディバイド次数情報及び前記符号化装置で行われる極端値除去過程に使われる最頻値、最大値及びディバイド次数別極端値情報を含むヘッダデータと、ＤＰＣＭ及び極端値が除去されたキーデータを圧縮及び符号化した２進のビットストリームを伝送されてグラフィックアニメーションデータのうち時間変数に該当する元のキーデータに復元する復号装置で行われる本発明に係る復号方法は、伝送された２進のビットストリームを復元してヘッダデータ及びＤＰＣＭ並びに極端値が除去されたキーデータを復元する（ａ）段階と、（ａ）段階で復元されたヘッダデータの最頻値、最大値及びディバイド次数別極端値情報に基づき、符号化装置で行われる極端値除去過程で除去された極端値を復元する（ｂ）段階と、（ｂ）段階で極端値が復元されたキーデータを最も低い散布度を有するＤＰＣＭ次数に該当する回数だけ繰り返して 逆ＤＰＣＭ処理を行う（ｃ）段階と、（ｃ）段階で逆ＤＰＣＭ処理されたデータを逆量子化して逆量子化されたデータを元のキーデータとして生成する（ｄ）段階とを含むことを特徴とする。
【００２０】
前記第３の課題を解決するために、前記符号化方法又は復号方法は、コンピュータで実行可能なプログラムコードにて記録媒体に記録することができる。
【００２１】
前記第４の課題を解決するために、前記符号化装置で前記符号化方法により生成されるビットストリームは、キーデータを量子化した量子化ビット数を格納するフィールドと、キーデータの符号化に必要な実際のビット数を格納するフィールドと、最頻値、最小値及び最大値の伝送に必要なビット数を格納するフィールドと、キーデータの数を格納するフィールドと、最も低い散布度を有するＤＰＣＭ次数及び最も低い散布度を有するディバイド次数を各々格納するフィールドと、最頻値、最小値及び最大値を各々格納するフィールドを含むヘッダ情報を格納するヘッダ情報フィールドと、符号化されたキーデータを格納するキー情報フィールドとを含むことを特徴とする。このビットストリームは、記録媒体又は伝送媒体によって提供可能である。
【００２２】
前記第５の課題を解決するために、伝送しようとするデータを符号化させる符号化装置において、符化効率を高めるために前記伝送しようとするデータに存在する極端値を除去する方法は、前記伝送しようとするデータのうち最も高い頻度数を有するデータを最頻値として求める（ａ）段階と、前記伝送しようとするデータの各々から前記最頻値を引く（ｂ）段階と、前記（ｂ）段階で処理されたデータのうち零以下の値を有するデータを正数に変える（ｃ）段階と、前記（ｃ）段階で処理されたデータからその大きさに基づき所定の値を引いて最大値と最小値との間のデータ範囲を狭める（ｄ）段階と、最大値及び最小値を抽出してその絶対値を比較し、比較された結果に基づき最大値の半分よりも大きいデータを零に近い値に変えるか、又は最小値の半分よりも小さいデータを零に近い値に変える処理をＭ次に亘って繰り返し行い、ディバイド処理されたデータを生成する（ｅ）段階と、前記（ｅ）段階で生成されたデータの散布度を各次数別に求め、最も低い散布度を有する次数のディバイド処理されたデータを極端値が除去されたデータとして選択して出力する（ｆ）段階とを含むことを特徴とする。前記極端値除去方法は、コンピュータで実行可能なプログラムコードにて記録媒体に記録することができる。
【００２３】
前記第６の課題を解決するために、グラフィックアニメーションデータのうち時間変数に該当するキーデータを符号化及び復号させる本発明に係るデータ処理システムは、キーデータを量子化して量子化されたデータを生成する量子化器と、量子化されたデータをＤＰＣＭ処理し、ＤＰＣＭ処理されたデータを入力としてＤＰＣＭ処理を繰り返し行いつつ生成されるＮ次のＤＰＣＭデータのうち最も低い散布度を有するデータを選択して出力するＤＰＣＭ処理部と、ＤＰＣＭ処理部から出力されるデータに存在する極端値を除去してデータの変化幅を狭める極端値除去部と、極端値除去部から出力されるデータから２進ビットの冗長度を除去して圧縮及び符号化された２進ビットストリームを生成するエントロピエンコーダを含む符号化器と、符号化器で圧縮及び符号化されて伝送される２進ビットストリームを受信し、符号化過程の逆過程を経て前記２進ビットストリームを元のキーデータに復元する復号器とを含むことを特徴とする。
【００２４】
前記第７の課題を解決するために、コンピュータを前記符号化及び復号方法を実行する手段として機能させるためのプログラムを提供することができる。
【００２５】
【発明の実施の形態】
以下、添付した図面に基づき、本発明に係る符号化装置及びその方法について詳細に説明する。
【００２６】
図５は、本発明に係る符号化及び復号装置の概略ブロック図であって、符号化器３００は量子化器３０５と、ＤＰＣＭ処理部３１０と、極端値除去部３２０と、エントロピエンコーダ３５０とを含み、復号器３６０はエントロピデコーダ３６５と、逆ＤＰＣＭ処理部３７５と、逆極端値除去部３７０と、逆量子化器３８０とを含む。
【００２７】
図５を参照すれば、符号化器３００は符号化するキーデータＫをその特性に応じてＮ次に亘ってＤＰＣＭを行い、ＤＰＣＭの行われたデータのうち最も低い散布度を有する次数のＤＰＣＭデータを選択し、選択されたデータの極端値を除去した後に符号化させて圧縮されたビットストリーム３５５を生成する。
【００２８】
より具体的には、量子化器３０５は入力されるキーデータＫを量子化して量子化されたデータＱKを生成する。ここで、キーデータＫは既にパーシング処理過程を経て実数に変えられたデータである。このような実数のキーデータＫは量子化器３０５から与えられた量子化ビット数ＱＳｔｅｐ＿Ｋに基づき整数値のキーデータＱKに変わる。すなわち、量子化される。キーの数がｎであり、ｎ〜１のインデックスを有するならば、量子化器３０５でキーデータＫ0〜Ｋn-1は量子化されたデータＱ0〜Ｑn―1に変わる。
【００２９】
ＤＰＣＭ処理部３１０は量子化されたデータＱKをＤＰＣＭ処理し、ＤＰＣＭ処理されたデータを入力としてＤＰＣＭ処理を繰り返し行いつつ生成されるＮ次のＤＰＣＭデータのうち最も低い散布度を有するデータ、すなわち、繰り返し性の高いデータＥKを選択して出力する。すなわち、１次ＤＰＣＭは量子化されたデータＱKを入力としてＤＰＣＭ処理し、２次ＤＰＣＭは１次ＤＰＣＭの結果データを入力としてＤＰＣＭ処理し、３次ＤＰＣＭは２次ＤＰＣＭの結果データを入力としてＤＰＣＭ処理する。そして、ＤＰＣＭ処理部３１０は各次数のＤＰＣＭデータに対する散布度を求め、最も低い散布度を有する次数のＤＰＣＭデータを選択して出力する。例えば、２次ＤＰＣＭの結果データが最も低い散布度を有するならば、ＤＰＣＭ処理部３１０は２次ＤＰＣＭの結果データを選択して極端値除去部３２０に出力する。このように、データの冗長度を高めれば、以降の符号化過程でエントロピエンコーダ３５０は冗長化されたデータを一つのデータに符号化できるので、符号化効率を高めることができる。ＤＰＣＭ処理部３１０の詳細については、図６に基づき後述する。
【００３０】
極端値除去部３２０はＤＰＣＭ処理部３１０から出力されるデータＥKに存在する極端値を除去することにより、データの変化幅が狭まったデータＤKを生成する。データＥKに存在する極端値はデータの平均から遠く離れている値であって、データの散布度を高めると共に、データの圧縮符号化効率を落とす。極端値除去部３２０の詳細については、図７に基づき後述する。
【００３１】
エントロピエンコーダ３５０はデータＤKから冗長度、すなわち、２進ビットの冗長度を除去して圧縮及び符号化させ、圧縮された２進ビットストリーム３５５を生成する。圧縮された２進ビットストリーム３５５の構造の詳細については、図１２に基づき後述する。
【００３２】
復号過程は前記符号化過程の逆過程を経て２進ビットストリームデータを入力としてエントロピデコーダ３６５で整数のデータに復元し、符号化過程の逆過程を経て復元された実数のキー値Ｋ＾に変える。復元されたキーデータは量子化過程で生じる誤差だけ逆量子化の過程で誤差が生じる。
【００３３】
図６は、本発明の一実施の形態によるＤＰＣＭ処理部３１０のブロック図である。ＤＰＣＭ処理部３１０は、Ｎ次ＤＰＣＭ処理部３１４、散布度計算部３１６及び最低散布度抽出部３１８を含む。
【００３４】
Ｎ次ＤＰＣＭ処理部３１４は現在量子化されたデータＱiを入力としてＮ回に亘ってＤＰＣＭ処理を繰り返し行い、ＤＰＣＭ処理の結果を散布度計算部３１６に出力する。１次ＤＰＣＭは現在の量子化されたデータＱiから以前の量子化されたデータＱi-1を引くことにより１次ＤＰＣＭ処理の結果である差分値Ｅiが求められる。２次ＤＰＣＭは現在の１次ＤＰＣＭの結果データから以前の１次ＤＰＣＭの結果データを引くことにより求められる。このような方法により、Ｎ次に亘ってのＤＰＣＭ処理を行う。ＤＰＣＭ処理部３１４は図２に示された通りであり、図２を参照すれば、バッファ１７５は現在のＱiを以降に差分値を求める時にＱi-1として用いるための中間バッファである。
【００３５】
散布度計算部３１６は、Ｎ次ＤＰＣＭ処理部３１４から各次数別に出力されるＤＰＣＭデータの散布度を求めて出力する。普通使われる散布度としては、分散、標準偏差、四分位偏差、範囲などがある。
【００３６】
最低散布度抽出部３１８は、散布度計算部３１６から各次数別散布度の値が出力されれば、最も低い散布度を有する次数のＤＰＣＭデータＥ0からＥn-1のデータを選択して出力する。
【００３７】
図７は、本発明の一実施の形態による極端値除去部３２０のブロック図である。極端値除去部３２０は、前処理部３２４及び主処理部３３４を含む。
【００３８】
前処理部３２４は、極端値除去のための前処理過程を行い、ＤＰＣＭ処理部３１０から出力されるデータのうち高い頻度数を有するデータを特定値、例えば“０”に変えると共に、残りのデータは“０”を中心として分布させる。具体的には、前処理部３２４はモード生成器３２６と、シフト処理部３２８と、フォルド処理部３３０と、減算処理部３３２とを含む。
【００３９】
モード生成器３２６は、ＤＰＣＭ処理部３１０から出力される差分データＥKのうち最も高い頻度数を有するデータ、すなわち最頻値を求める。
【００４０】
シフト処理部３２８は、下記数式１のように、差分データからモード生成器３１０で求めた最頻値を引く。
【００４１】
【数１】
0003699066.tif 000002
【００４２】
このように、差分データから最頻値を引けば、最頻値のような差分データは０に変わり、残りの差分値も最頻値を引いた値に変わる。すなわち、最頻値だけシフトされる。そして、シフトされたデータは０を中心として分布される。
【００４３】
フォルド処理部３３０は、０以下の値、すなわち負数を正数に変える。フォルド処理部３３０の詳細については、図８に基づき後述する。
【００４４】
減算処理部３３２は、フォルド処理部３３０で処理されたデータからその大きさに基づき所定の値を引くことにより最大値と最小値との間のデータ範囲を狭める。減算処理部３３２の詳細については、図１０に基づき後述する。
【００４５】
以上述べたように、極端値除去の前処理過程が完了すれば、主処理部３３４により正の極端値及び負の極端値を除去して最大値と最小値との間の範囲を狭める。具体的に、主処理部３３４はディバイドアップ／ダウン処理部３２２及びデータ出力部３１２を含む。
【００４６】
ディバイドアップ／ダウン処理部３２２は前処理部３２４から出力されるデータから最大値ｍａｘ及び最小値ｍｉｎを抽出する（３３６）。そして、抽出された最大値及び最小値の絶対値を比較し（３３８）、最大値の絶対値が最小値の絶対値以上であれば、最大値の半分よりも大きいデータを零に近い値に変えるディバイド−ダウン処理を行い（３４０）、最小値の絶対値が大きければ、最小値の半分よりも小さいデータを零に近い値に変えるディバイド−アップ処理を行う（３４２）。ディバイドアップ／ダウン処理部３２２は、ディバイド−ダウン又はディバイド−アップされたデータを再び入力として前述した動作をＭ次に亘って繰り返し行い、ディバイドアップ／ダウンデータを生成する。ディバイド−ダウン処理の詳細及びディバイド−アップ処理の詳細については各々図１１及び図１２に基づき後述する。
【００４７】
データ出力部３５２は、ディバイド−アップ／ダウン処理部３２２から出力されるＭ次に亘って生成されるディバイドアップデータ又はディバイドダウンデータの散布度を各々求め（３１２）、最も低い散布度を有する次数のディバイド−アップ又はディバイドダウンデータを選択して出力する（３４６）。
【００４８】
すなわち、ディバイド−アップ／ダウン処理を繰り返し行えば、最大値の半分よりも大きいデータ、又は最小値の半分よりも小さいデータが零に近く分布され、これにより、零を中心として広く分布されていたデータが零に近く分布される。一方、次数が高くなるといって、ディバイドアップデータ又はディバイドダウンデータが零に一層近く分布されるとは限らない。これにより、Ｍ次のディバイドアップデータ又はディバイドダウンデータの散布度を求め、そのうち最も低い散布度を有するデータを取ることにより、零に近く分布されつつ最大値と最小値との間の範囲が最も狭い次数のディバイドアップデータ又はディバイドダウンデータが抽出可能になる。結局、極端値を除去してからは一層狭まった範囲を有するデータを得ることができる。
【００４９】
一方、減算処理部３３２及びディバイド−ダウン処理３４０のためにはデータの最大値が必要であり、ディバイド−アップ処理３４２のためにはデータの最小値が必要である。また、これら最大値及び最小値に関するデータはヘッダ情報として復号部３６０（図５参照）に伝送する必要がある。これにより、復号部３６０は符号化部３００の逆過程を経て正常なデータの復号が行えるようになる。
【００５０】
図８は、図７に示されたフォルド処理部３３０の動作の詳細を示すフローチャートである。
【００５１】
図７及び図８を参照すれば、フォルド処理部３３０はシフト処理部３２８から出力されたデータが零以上であるか否かを判断し（第４３５段階）、零よりも大きいと判断されれば、シフト処理部３２８から出力されるデータEiKに２をかけた値をフォルド処理部３３０の出力データDiK として生成する（第４４５段階）。これに対し、第４３５段階で、シフト処理部３２８の出力データEiKが零よりも小さいと判断されれば、下記数式２により計算される値をフォルド処理部３３０の出力データDiKとして生成する（第４４０段階）。
【００５２】
【数２】
0003699066.tif 000003
【００５３】
このような過程を通じて、負数は正の奇数となり、以前の正数は正の偶数となる。
【００５４】
図９は、図７に示された減算処理部３３２の動作を詳細に示すフローチャートである。
【００５５】
図７及び図９を参照すれば、フォルド処理部３３０から出力されるデータから最大値ｍａｘを抽出した後、フォルド処理部３３０の出力データEiKが最大値の半分よりも大きいか否かを判断する（第４５５段階）。第４５５段階で、フォルド処理部３３０から出力されるデータEiKが最大値の半分よりも大きいと判断されれば、下記数式３により負数に変え（第４６５段階）、そうでなければ、その値をそのまま保って減算処理部３３０の出力データDiKとして生成する（第４６０段階）。
【００５６】
【数３】
0003699066.tif 000004
【００５７】
このような減算処理部３３２の動作によれば、データの範囲が狭まる効果がある。すなわち、以前のデータの範囲が０〜最大値であれば、この減算処理部３３２を通じて−ｍａｘ／２から＋ｍａｘ／２の最大範囲を有すると共に、０を中心としてデータが分布される。また、フォルド処理部３３０で処理されたデータが０及び最大値の両端に集中しているほど、この処理過程を経ればデータの範囲は一層狭まる。
【００５８】
図１０は、図７に示されたディバイド−ダウン３４０の動作を詳細に示すフローチャートである。
【００５９】
図７及び図１０を参照すれば、減算処理部３３２から出力されたデータから最大値及び最小値データを各々抽出してその絶対値を比較する。比較の結果、最大値が最小値以上であれば、ディバイド−ダウン３４０処理を行う。ディバイド−ダウン３４０処理は、まず、減算処理部３３２から出力されたデータEiKが零以上であるか否かを判断し（第５０５段階）、データが零よりも小さいと判断されれば、その値を２倍にしてディバイドデータDiKとして生成する（第５２５段階）。もし、第５０５段階で、減算処理部３３２から出力されるデータEiKが零以上であると判断されれば、最大値の半分よりも大きいか否かを判断する（第５１０段階）。第５１０段階で、減算処理部３３２から出力されるデータが最大値の半分以下であると判断されれば、その値をそのままディバイドデータDiKとして生成する（第５２０段階）。これに対し、第５１０段階で、減算処理部３３２から出力されるデータが最大値の半分よりも大きいと判断されれば、下記数式４により求められる値をディバイドデータDiKとして生成する（第５１５段階）。
【００６０】
【数４】
0003699066.tif 000005
【００６１】
このように、ディバイド−ダウン処理を通じて最大値の半分よりも大きいデータを負の奇数に変え、以前の負数は負の偶数に変える。これは、データの範囲を狭める効果がある。
【００６２】
図１１は、図７に示すディバイド−アップ３４２の動作を詳細に示すフローチャートである。
【００６３】
図７及び図１１を参照すれば、減算処理部３３２から出力されたデータから最大値及び最小値データを各々抽出してその絶対値を比較する。比較の結果、最大値が最小値よりも小さければ、ディバイド−アップ３４２処理を行う。ディバイド−アップ処理は、まず、減算処理部３３２から出力されるデータEiKが零よりも小さいか否かを判断する（第５３５段階）。第５３５段階で、減算処理部３３２から出力されるデータEiKが零よりも小さくないと判断されれば、減算処理部３３２から出力されるデータをそのままディバイドデータDiKとして生成する（第５５５段階）。もし、第５３５段階で、減算処理部３３２から出力されるデータEiKが零よりも小さいと判断されれば、その値が最小値の半分よりも小さい否かを判断する（第５４０段階）。第５４０段階で、減算処理部３３２から出力されるデータEiKが最小値の半分よりも小さくないと判断されれば、減算処理部３３２の出力データを２倍にした値をディバイドデータDiKとして生成する（第５５０段階）。これに対し、第５４０段階で、減算処理部３３２から出力されるデータが最小値の半分よりも小さいと判断されれば、下記数式５により計算された値をディバイドデータDiKとして生成する（第５４５段階）。
【００６４】
【数５】
0003699066.tif 000006
【００６５】
これにより、ディバイド−アップ処理により最小値の半分よりも小さいデータが負の奇数に変えられ、最小値の半分よりも小さくない負のデータが負の偶数に変えられる。これもまた、データの範囲を狭める効果がある。
【００６６】
図１２は、図５に示すエントロピエンコーダ３５０を介して伝送されビットストリームの構造図である。ビットストリームは、ヘッダ情報６００とキー情報６０５とに大別される。キー情報６１５としては、実数のキーデータが量子化、ＤＰＣＭ、極端値除去過程を経て範囲が狭まった整数のデータを符号化させたデータが伝送される。この時、前端から最も低い散布度を有するＤＰＣＭの次数Ｏｒｄｅｒ＿ＤＰＣＭに該当する数のデータがヘッダ情報として伝送される。例えば、最も低い散布度を有するＤＰＣＭの次数が２次であれば、前端から第２番目のデータがヘッダ情報として伝送される。これは、一般的にＤＰＣＭ処理後に、ＤＰＣＭ次数に該当する数の前端データは他のデータとは大きい差を有する極端値であるためである。すなわち、エントロピエンコーダの符号化効率を高めるために、他のデータと大きい差を有するデータはキー情報から引いてヘッダ情報として伝送する。結局、キー情報６１５としては、ヘッダ情報として伝送されるキーデータの数Ｋｅｙorder＿DPCM-1及び残りのキーデータを伝送する。
【００６７】
ヘッダ情報の構成６１０は、下記の通りである。まず、キーデータに対する量子化ビット数ＱＳｔｅｐ＿Ｋがある。そして、ＤＰＣＭ及び極端値除去処理を通じてデータの範囲が狭まり、これにより、符号化に必要な実際のビット数が減る。この時に必要なビット数ＱＳｔｅｐ＿Ｃを伝送する。次に、最頻値、最大値、最小値を伝送するために必要なビット数ＱＳｔｅｐ＿Ｓ、キーの数＃Ｋｅｙ、最も低い散布度を有するＤＰＣＭ次数Ｏｒｄｅｒ＿ＤＰＣＭ、最も低い散布度を有するディバイド次数Ｏｒｄｅｒ＿ＤＮＤ及び最頻値Ｍｏｄｅを伝送する。次に、最も低い散布度を有するＤＰＣＭの次数Ｏｒｄｅｒ＿ＤＰＣＭに該当する数のキーデータＫｅｙ0，．．．，Ｋｅｙorder＿DPCM-1を伝送する。この時、符号が分かるように、１ビットの符号ビットも含めて伝送する。次に、最も低い散布度を有するディバイド次数Ｏｒｄｅｒ＿ＤＮＤに該当する数の最大値又は最小値データは極端値Ｍａｘ0，．．．，Ｍａｘorder＿DND-1として伝送する。これは、極端値除去部３２０のディバイド−アップ３４０及びディバイド−ダウン３４２処理に使われるデータの最大値及び最小値であり、ここに減算処理部３３２で使われる最大値を含めて、あるいは別途に伝送でき、１ビットの符号ビットを含めて、０であれば正の最大値、１であれば負の最小値であることを表わす。
【００６８】
一方、図５に基づき述べたように、復号過程は符号化器３００で生成し伝送された２進のビットストリームデータを入力として前記符号化過程の逆過程を通じて行われる。この時、２進ビットストリームデータには、図１２に基づき述べたように、復号過程で必要なデータ、例えば最も低い散布度を有するＤＰＣＭ次数情報、最も低い散布度を有するディバイド次数情報及び前記符号化装置で行われる極端値除去過程に使われる最頻値、ディバイド次数別極端値及び最大値情報を含むヘッダデータ及びキーデータが含まれる。
【００６９】
図５を参照すれば、エントロピデコーダ３６５は、符号化器３００から伝送された２進ビットストリームを復元し、ヘッダデータ及びＤＰＣＭ並びに極端値除去処理されたキーデータを復元する。
【００７０】
逆極端値除去部３７０はエントロピデコーダ３６５で復元されたヘッダデータの最頻値、ディバイド次数別極端値及び最大値情報に基づき、符号化器３００の極端値除去部３２０で極端値除去過程により除去された極端値を復元する。逆極端値除去部３７０の詳細については、図１３に基づき後述する。
【００７１】
逆ＤＰＣＭ処理部３７５は、逆極端値除去部３７０で極端値が復元されたキーデータを図３に示された逆ＤＰＣＭ処理器により、最も低い散布度を有するＤＰＣＭ次数に該当する回数だけ繰り返して逆ＤＰＣＭ処理を行い、その処理結果を出力する。
【００７２】
逆量子化器３８０は、逆ＤＰＣＭ処理部３７５から出力される逆ＤＰＣＭデータを逆量子化し、逆量子化されたデータを元の実数のキー値Ｋ＾に変える。復元されたキーデータＫ＾は量子化中に生じる誤差だけ逆量子化中に誤差が生じる。
【００７３】
図１３は、本発明の一実施の形態による逆極端値除去部（図５の３７０）のブロック図であって、図７に示された極端値除去部の逆処理過程を有し、主処理部７１０及び後処理部７５０を含んでなる。
【００７４】
図１３を参照すれば、主処理部７１０は、図７の主処理部３３４の逆過程を行うものであって、まず、復元されたヘッダデータでディバイド次数別極端値を零と比較する（第７１４段階）。極端値が零以上であれば、キーデータを逆ディバイドダウン処理し（第７１６段階）、極端値が零よりも小さければ、キーデータを逆ディバイドアップ処理して（第７１８段階）キーデータの正の極端値又は負の極端値を復元する。ここで、逆ディバイドダウン処理は、図１０に示されたディバイドダウン処理の逆順に行う。その処理結果は下記数式６の通りである。
【００７５】
【数６】
0003699066.tif 000007
（ここで、EiKは逆ディバイドダウン又は逆ディバイドアップ処理されたデータであり、DiKはエントロピデコーダ３６５で復元されたキーデータであり、Maxiはディバイド次数別極端値である。）
【００７６】
同様に、逆ディバイドアップ処理は、図１１に示されたディバイドアップ処理の逆順に行われ、その処理結果は下記数式７の通りである。
【００７７】
【数７】
0003699066.tif 000008
【００７８】
逆ディバイドダウン又は逆ディバイドアップ処理後に、ディバイド次数ｉが零であるか否かを判断し（第７２０段階）、ディバイド次数が零であると判断されれば、後処理部７５０で後処理を行う。一方、ディバイド次数ｉが零でないと判断されれば、ディバイド次数ｉを一ずつデクリメントしつつ（第７２２段階）ディバイド次数ｉが零になるまで逆ディバイドダウン又は逆ディバイドアップ処理を繰り返し行う。
【００７９】
後処理部７５０は、図７の前処理部３２４とは逆の構造を有し、主処理部７１０で極端値が復元されたデータを最頻値だけシフトして、零を中心として分布するキーデータを最頻値を中心として分布するように復元する。具体的に、後処理部７５０は、逆減算処理部７５２、逆フォルド処理部７５４及び逆シフト処理部７５６を含んでなる。
【００８０】
逆減算処理部７５２は、図７の減算処理部３３２の逆処理過程であって、主処理部７１０で極端値が復元されたデータにその大きさに基づき、復元されたヘッダデータの最大値を加えて復元されたデータをいずれも零以上に変える。具体的に、主処理部７１０で逆ディバイドダウン又は逆ディバイドアップ処理されたキーデータが零以上であればその値を保ち、零よりも小さければ主処理部７１０で生成されたデータに（最大値＋１）を加える。
【００８１】
逆フォルド処理部７５４は、図７に示されたフォルド処理部３３０の逆処理部であって、逆減算処理部７５２で処理されたデータが奇数又は零又は偶数であるか否かを判断し、下記数式８により求められるデータを逆フォルド処理されたデータとして生成する。
【００８２】
【数８】
0003699066.tif 000009
（ここで、EKは逆フォルド処理されたデータであり、DKは逆減算処理部７５２で処理されたデータである。）
【００８３】
逆シフト処理部７５６は、逆フォルド処理部７５４で処理されたデータをヘッダデータで最頻値だけシフトし、零を中心として分布するデータを最頻値を中心として分布するように復元する。
【００８４】
前述のような処理過程を有する本発明は、アニメーションデータのうちキーデータを符号化させるに当たって、そのデータの特性に好適な次数のＤＰＣＭを行うことにより低い散布度を有するデータを選択し、さらにＮ次のＤＮＤを行うことによりデータの範囲を一層狭める。これにより、データの特性がエントロピエンコーダ３５０を通じて圧縮及び符号化されるのに一層効率的で且つ好適に変わり、その結果、符号化効率が高められる。すなわち、２進ビットストリームを生成するに当たって、２進データの冗長度を高めると共に、エントロピエンコーダでこのビットデータの冗長度を除去するので、符号化効率が高められる。結局、キーデータの符号化効率を高めることにより、ぼう大な量のアニメーションデータを一層効率良く圧縮してデータの量を減らし、効率良い保存及び伝送、処理を可能にする。
【００８５】
以上述べたように、本発明によれば、符号化するキーデータをその特性に応じて最も低い散布度を有するデータを選択することにより、符号化するデータの冗長度を高めて符号化効率を高められる。一般的に、データの散布度が低いほどデータの冗長度が高くなり、これにより、エントロピ符号化の効率が高められる。このため、１次以上のＤＰＣＭ、すなわちＮ次ＤＰＣＭを行うことにより得られるデータのうち最も低い散布度を有するデータを選択し、Ｎ次のＤＰＣＭ後にも現れる極端値を除去することにより、符号化効率を高めることができる。
【００８６】
本発明はまた、コンピュータで読み取り可能な記録媒体にコンピュータにより読み取り可能なコード（コンピュータプログラムないしデータ構造）として実現可能である。コンピュータにより読み取り可能な記録媒体はコンピュータシステムにより読み取り可能なデータが保存されるあらゆる種類の記憶装置を含む。コンピュータにより読み取り可能な記録媒体の例としては、ＲＯＭ、ＲＡＭ、ＣＤ−ＲＯＭ、磁気テープ、フレキシブルディスク、光データ記憶装置などがある。本発明はまた、情報伝送媒体により伝送可能なコード（プログラムないしデータ構造）として実現可能である。情報を伝送可能な媒体としては、広くキャリアウェーブ（例えば、インターネットを通して伝送）の形に実現されるものも含む。また、コンピュータにより読み取り可能な記録媒体はネットワークに接続されたコンピュータシステムに分散され、分散方式によりコンピュータにより読み取り可能なコードが保存されて実行可能である。
【００８７】
以上、図面及び明細書において最適の実施形態が開示された。ここで、特定の用語が使われたが、これは単に本発明を説明するために使われたものであって、意味の限定や特許請求の範囲上に記載された本発明の範囲を制限するために使われたものではない。従って、この技術分野の当業者であれば、これより各種の変形及び均等な他の実施形態が可能であるという点は理解できるであろう。よって、本発明の真の技術的な保護範囲は特許請求の範囲上の技術的な思想によって定まるべきである。
【００８８】
【発明の効果】
以上述べたように、本発明に係るグラフィックアニメーションデータの符号化装置及びその方法によれば、符号化するキーデータをその特性に応じてＮ次ＤＰＣＭ処理して最も低い散布度を有するデータを選択することにより、符号化するデータの冗長度を高めて符号化効率を高めることができる。さらに、ＤＰＣＭ後にも現れる極端値を除去することにより、符号化効率を高めることができる。
【図面の簡単な説明】
【図１】キー及びキー値の相関関係の一例を示すグラフである。
【図２】従来の技術による符号化及び復号装置を概略的に示すブロック図である。
【図３】ＤＰＣＭ（図２の１１０）の詳細図である。
【図４】逆ＤＰＣＭ（図２の１６０）の詳細図である。
【図５】本発明に係る符号化及び復号装置の概略ブロック図である。
【図６】本発明の一実施の形態によるＤＰＣＭ処理部（図５の３１０）のブロック図である。
【図７】本発明の一実施の形態による極端値除去部（図５の３２０）のブロック図である。
【図８】フォルド処理部（図７の３３０）の動作の詳細を示すフローチャートである。
【図９】減算処理部（図７の３３２）の動作の詳細を示すフローチャートである。
【図１０】ディバイド−ダウン（図７の３４０）の動作の詳細を示すフローチャートである。
【図１１】ディバイド−アップ（図７の３４０）の動作の詳細を示すフローチャートである。
【図１２】エントロピエンコーダ（図５の３５０）を通じて伝送されるビットストリームの構造図である。
【図１３】本発明の一実施の形態による逆極端値除去部（図５の３７０）のブロック図である。
【図１】
0003699066.tif 000013
【図２】
0003699066.tif 000014
【図３】
0003699066.tif 000015
【図４】
0003699066.tif 000016
【図５】
0003699066.tif 000017
【図６】
0003699066.tif 000018
【図７】
0003699066.tif 000019
【図８】
0003699066.tif 000020
【図９】
0003699066.tif 000021
【図１０】
0003699066.tif 000022
【図１１】
0003699066.tif 000023
【図１２】
0003699066.tif 000024
【図１３】
0003699066.tif 000025