(57)【要約】【課題】プログラムの出力データを短い時間で圧縮するデータ圧縮装置を提供すること。【解決手段】データ圧縮装置１０は、抽出部１１と圧縮部１２を備える。抽出部１１は、プログラムの入力データに基づいて出力データにおける圧縮すべき箇所を抽出する。圧縮部１２は、抽出された圧縮すべき箇所を出力データにおいて圧縮する。【選択図】図１
2010130208.tif 000002
【特許請求の範囲】
【請求項１】
プログラムの出力データを圧縮するデータ圧縮装置であって、
前記プログラムの入力データに基づいて前記出力データにおける圧縮すべき箇所を抽出する抽出部と、
前記圧縮すべき箇所を前記出力データにおいて圧縮する圧縮部と、を備えることを特徴とするデータ圧縮装置。
【請求項２】
前記抽出部は、第１のデータと該第１のデータと相関のある第２のデータとを抽出することを特徴とする、請求項１に記載のデータ圧縮装置。
【請求項３】
前記入力データは、前記第１のデータと前記第２のデータとを関連づけるデータを含むことを特徴とする、請求項２に記載のデータ圧縮装置。
【請求項４】
前記圧縮部は、前記第１のデータと前記第２のデータとの差分に基づいて、前記出力データを圧縮することを特徴とする、請求項２又は３に記載のデータ圧縮装置。
【請求項５】
前記プログラムは、シミュレーションプログラムであることを特徴とする、請求項１乃至４のいずれか１項に記載のデータ圧縮装置。
【請求項６】
前記シミュレーションプログラムは、電子回路に対するシミュレーションプログラムであることを特徴とする、請求項５に記載のデータ圧縮装置。
【請求項７】
前記入力データは、前記電子回路の接続情報のデータを含むことを特徴とする、請求項６に記載のデータ圧縮装置。
【請求項８】
前記出力データは、前記電子回路に対する入力信号及び出力信号を含むことを特徴とする、請求項６又は７に記載のデータ圧縮装置。
【請求項９】
前記プログラムは、レンダリングプログラムであることを特徴とする、請求項１乃至４のいずれか１項に記載のデータ圧縮装置。
【請求項１０】
前記出力データは、前記レンダリングプログラムによって出力された３次元ＣＧ動画であることを特徴とする、請求項９に記載のデータ圧縮装置。
【請求項１１】
前記入力データは、前記３次元ＣＧ動画に含まれる物体の運動経路、変形その他の変化を表す情報であって前記３次元ＣＧ動画において画像の変化をもたらすものを含むことを特徴とする、請求項１０に記載のデータ圧縮装置。
【請求項１２】
前記入力データは、前記３次元ＣＧ動画のレンダリングにおける、視点の移動、向きの変更、拡大率の変更その他の変化を表す情報であって前記３次元ＣＧ動画において画像の変化をもたらすものを含むことを特徴とする、請求項１０又は１１に記載のデータ圧縮装置。
【請求項１３】
前記入力データは、前記３次元ＣＧ動画のレンダリングにおける、光源の移動、向きの変更、明るさの変更、色調の変更その他の変化を表す情報であって前記３次元ＣＧ動画において画像の変化をもたらすものを含むことを特徴とする、請求項１０乃至１２のいずれか１項に記載のデータ圧縮装置。
【請求項１４】
プログラムの出力データを圧縮するデータ圧縮方法であって、
前記プログラムの入力データに基づいて前記出力データにおける圧縮すべき箇所を抽出する工程と、
前記圧縮すべき箇所を前記出力データにおいて圧縮する工程と、を含むことを特徴とするデータ圧縮方法。
【請求項１５】
前記圧縮すべき箇所は、第１のデータと該第１のデータと相関のある第２のデータとを含むことを特徴とする、請求項１４に記載のデータ圧縮方法。
【請求項１６】
前記入力データは、前記第１のデータと前記第２のデータとを関連づけるデータを含むことを特徴とする、請求項１５に記載のデータ圧縮方法。
【請求項１７】
前記圧縮工程において、前記第１のデータと前記第２のデータとの差分に基づいて、前記出力データを圧縮することを特徴とする、請求項１５又は１６に記載のデータ圧縮方法。
【請求項１８】
プログラムの出力データを圧縮する処理をコンピュータに実行させるデータ圧縮プログラムであって、
前記出力データと前記プログラムの入力データとを入力する処理と、
前記入力データに基づいて前記出力データにおける圧縮すべき箇所を抽出する処理と、
前記圧縮すべき箇所を前記出力データにおいて圧縮する処理と、をコンピュータに実行させることを特徴とするデータ圧縮プログラム。
【請求項１９】
前記圧縮すべき箇所は、第１のデータと該第１のデータと相関のある第２のデータとを含むことを特徴とする、請求項１８に記載のデータ圧縮プログラム。
【請求項２０】
前記入力データは、前記第１のデータと前記第２のデータとを関連づけるデータを含むことを特徴とする、請求項１９に記載のデータ圧縮プログラム。
【請求項２１】
前記圧縮処理において、前記第１のデータと前記第２のデータとの差分に基づいて、前記出力データを圧縮する処理をコンピュータに実行させることを特徴とする、請求項１９又は２０に記載のデータ圧縮プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデータ圧縮装置、方法及びプログラムに関し、特に、シミュレーションプログラムの出力データのデータ圧縮装置、方法及びプログラムに関する。
【背景技術】
【０００２】
近年、コンピュータシミュレーションは、様々な分野で用いられている。しかし、シミュレーションプログラムによって出力されるデータのサイズが膨大となる場合には、記憶領域を圧迫するという問題が生じている。
【０００３】
データを圧縮する方法として、データ間の類似性を利用する方法が用いられる。例えば、データの一部のみをそのまま記録し、他の部分については直接記録せず、記録された一部のデータのうちのいずれのデータと類似関係にあるかという情報、及び、直接記録されないデータと類似関係にあるデータとの差分データを記録する方法が用いられる。差分データは大部分においてゼロに近い値をとることから、値の出現頻度に大きな偏りを有する。したがって、出現頻度の高い値には短い符号長を割り当て、出現頻度の低い値には長い符号長を割り当てることによって、データを圧縮することができる。
【０００４】
なお、特許文献１には、動き補償ブロック探索処理方法において、高い精度で動き方向を選択することにより、符号化効率を向上させる方法が記載されている。また、特許文献２には、動き補償フレーム間予測において、動き検出の処理時間を短縮する方法が記載されている。さらに、特許文献３には、連続した画像間の類似性を用いた動画像圧縮技術において、類似度の高い箇所を効率良く検出する装置が記載されている。
【０００５】
【特許文献１】特開平０５−２８４４８９号公報
【特許文献２】特開平０８−２０５１５４号公報
【特許文献３】特開平２００６−２６２１９８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
以下の分析は、本発明者によってなされたものである。
【０００７】
動画を構成する連続するフレーム同士は互いに類似している。したがって、ある１フレームに続く数フレームについては、最初のフレームとの差分のみを記録することにより、情報量を圧縮することができる。ＭＰＥＧ１その他の標準的な動画圧縮方式においては、単純にフレーム間の差分をとるのではなく、動画に映っている物体のフレーム間における動きを検出してフレーム間の差分をさらに小さくすることによって、高いデータ圧縮率を実現する手法（いわゆる動き補償）が用いられる。
【０００８】
動き補償を実現するには、フレーム間で類似性が高い部分画像がどの方向に移動したかを検出する必要がある。例えば、フレームを１６ピクセル×１６ピクセルの領域に分割し、１ピクセル単位で各方向に動かして、もっとも類似性が高い移動方向を検出する処理が必要とされる。したがって、動き補償においては、多量のデータ比較の処理が発生し、長い計算時間を要するという問題がある。
【０００９】
また、ｇｚｉｐ（ＧＮＵ  ＺＩＰ）その他のデータ圧縮技術においては、データ内の類似関係が用いられる。例えば、Ｌｅｍｐｅｌ−Ｚｉｖアルゴリズムにおいては、データを一定サイズのバッファに読み込み、現在注目しているデータ列が過去に出現しているか否かを検索し、過去に出現している場合には、データ列を過去に出現した位置と長さの情報に置き換える。このとき、出現頻度の高いデータ列は、過去に出現した位置と長さの情報に置き換えられることから、データを圧縮することができる。また、出現頻度の高いデータ列に短い符号長を割り当て、出現頻度の低いデータ列に長い符号長を割り当てることによって、さらにデータ圧縮を行うこともできる。
【００１０】
しかし、かかるデータ圧縮技術においても、現在注目しているデータ列と一致するデータ列を過去のデータ列から検索する際に多量のデータ比較の処理が発生し、長い計算時間を要するという問題がある。
【００１１】
そこで、シミュレーションプログラムその他のプログラムの出力データを短い時間で圧縮するデータ圧縮装置、方法及びプログラムを提供することが課題となる。
【課題を解決するための手段】
【００１２】
本発明の第１の視点に係るデータ圧縮装置は、
プログラムの出力データを圧縮するデータ圧縮装置であって、
前記プログラムの入力データに基づいて前記出力データにおける圧縮すべき箇所を抽出する抽出部と、
前記圧縮すべき箇所を前記出力データにおいて圧縮する圧縮部と、を備える。
【００１３】
本発明の第２の視点に係るデータ圧縮方法は、
プログラムの出力データを圧縮するデータ圧縮方法であって、
前記プログラムの入力データに基づいて前記出力データにおける圧縮すべき箇所を抽出する工程と、
前記圧縮すべき箇所を前記出力データにおいて圧縮する工程と、を含む。
【００１４】
本発明の第３の視点に係るデータ圧縮プログラムは、
プログラムの出力データを圧縮する処理をコンピュータに実行させるデータ圧縮プログラムであって、
前記出力データと前記プログラムの入力データとを入力する処理と、
前記入力データに基づいて前記出力データにおける圧縮すべき箇所を抽出する処理と、
前記圧縮すべき箇所を前記出力データにおいて圧縮する処理と、をコンピュータに実行させる。
【発明の効果】
【００１５】
本発明に係るデータ圧縮装置、方法及びプログラムにより、コンピュータシミュレーションその他のプログラムの出力データを短い時間で圧縮することができる。
【００１６】
プログラムの入力情報を利用して、プログラムの出力データに含まれる互いに相関を有するデータを抽出することによって、データ圧縮において必要とされる相関を有するデータを探索する手間を省くことができるからである。
【発明を実施するための最良の形態】
【００１７】
（第１の実施形態）
本発明の第１の実施形態のデータ圧縮装置について図面を参照して説明する。図１は、本実施形態のデータ圧縮装置１０の構成を示すブロック図である。データ圧縮装置１０は、プログラムの出力データを圧縮するデータ圧縮装置である。図１を参照すると、データ圧縮装置１０は、抽出部１１と圧縮部１２を備える。
【００１８】
抽出部１１は、プログラムの入力データに基づいて出力データにおける圧縮すべき箇所を抽出する。圧縮部１２は、圧縮すべき箇所を出力データにおいて圧縮する。
【００１９】
抽出部１１は、第１のデータと第１のデータと相関のある第２のデータとを抽出することが好ましい。また、入力データは、第１のデータと第２のデータとを関連づけるデータを含むことが好ましい。さらに、圧縮部１２は、第１のデータと第２のデータとの差分に基づいて、出力データを圧縮するようにしてもよい。
【００２０】
プログラムは、シミュレーションプログラムであってもよい。また、シミュレーションプログラムは、電子回路に対するシミュレーションプログラムであってもよい。さらに、入力データは、電子回路の接続情報のデータを含むことが好ましい。また、出力データは、電子回路に対する入力信号及び出力信号を含むものであってもよい。
【００２１】
プログラムは、レンダリングプログラムであってもよい。また、出力データは、レンダリングプログラムによって出力された３次元ＣＧ動画であってもよい。さらに、入力データは、３次元ＣＧ動画に含まれる物体の運動経路、変形その他の変化を表す情報であって３次元ＣＧ動画において画像の変化をもたらすものを含むことが好ましい。
【００２２】
また、入力データは、３次元ＣＧ動画のレンダリングにおける、視点の移動、向きの変更、拡大率の変更その他の変化を表す情報であって３次元ＣＧ動画において画像の変化をもたらすものを含むことが好ましい。さらに、入力データは、３次元ＣＧ動画のレンダリングにおける、光源の移動、向きの変更、明るさの変更、色調の変更その他の変化を表す情報であって３次元ＣＧ動画において画像の変化をもたらすものを含むことが好ましい。
【００２３】
（第２の実施形態）
本発明の第２の実施形態のデータ圧縮方法について図面を参照して説明する。図２は、本実施形態のデータ圧縮方法のフローチャートである。
【００２４】
本実施形態のデータ圧縮方法は、プログラムの出力データを圧縮する方法である。図２を参照すると、まず、プログラムの入力データに基づいて出力データにおける圧縮すべき箇所を抽出する（ステップＳ６１）。次に、抽出された圧縮すべき箇所を出力データにおいて圧縮する（ステップＳ６２）。
【００２５】
（第３の実施形態）
本発明の第３の実施形態のデータ圧縮プログラムについて図面を参照して説明する。図３は、本実施形態のデータ圧縮プログラムを実行させるコンピュータ２０の構成を示すブロック図である。コンピュータ２０は、ＣＰＵ２１、記憶装置２２、入力装置２３、及び出力装置２４を備える。
【００２６】
本実施形態のデータ圧縮プログラムは、プログラムの出力データを圧縮する処理をコンピュータ２０に実行させる。データ圧縮プログラムは、対象とするプログラムの出力データと入力データとを入力する処理をコンピュータ２０に実行させる。また、データ圧縮プログラムは、入力データに基づいて出力データにおける圧縮すべき箇所を抽出する処理をコンピュータ２０に実行させる。さらに、データ圧縮プログラムは、抽出された圧縮すべき箇所を出力データにおいて圧縮する処理をコンピュータ２０に実行させる。
【実施例１】
【００２７】
本発明の第１の実施例について図面を参照して説明する。図４は、シミュレーションの対象となる電子回路を示す。シミュレーションの出力データは、信号１〜６の波形データを含む。信号１及び信号５は、直列に接続された２個のインバータ回路３１の入力信号及び出力信号である。また、信号２及び信号４は、直列に接続された４個のインバータ回路３１の入力信号及び出力信号である。さらに、信号３及び信号６は、直列に接続された６個のインバータ回路３１の入力信号及び出力信号である。
【００２８】
図５は、図４に示した電子回路に対し、適当な入力信号を与えてシミュレーションを行った場合における入力信号と出力信号の波形を示す。信号１乃至３は入力信号の波形を示す。一方、信号４乃至６は出力信号の波形を示す。図中の矢印は、信号同士の関連を示す。
【００２９】
図６は、図５における信号１及び信号５、信号２及び信号４、又は、信号３及び信号６が、それぞれ類似しているものとして、それぞれの信号を適当な時間だけ遅延させて、差分をとったときの波形を示す。ここで、遅延時間は、差分の絶対値の総和が最小となるように選択する。
【００３０】
図５に示すシミュレーションの出力データ、すなわち、信号１ないし６の波形と比較すると、図６に示す差分の波形は０付近に集中している。したがって、図６に示す差分の波形に対して、ゼロに近い値には短い符号長を割り当て、ゼロから離れた値には長い符号長を割り当てることによって、データを圧縮することができる。
【００３１】
この信号差分波形を得るためには、差分の絶対値の総和ができるだけ小さくなるような類似信号を検索する必要がある。さらに、類似信号との間の差分の絶対値の総和ができる限り小さくなるような遅延時間を探索する必要がある。
【００３２】
図７は、所定の２つの信号ｋ、ｎについて、差分の絶対値の総和が最小となるような、遅延時間ｄを求めるフローチャートを示す。ここでは、一例として、遅延時間の最大値は１０ｎｓとし、遅延時間を検索する時間刻みは０．１ｎｓとしている。なお、ＳＡＤとは、２つの信号の差分の絶対値の総和（Ｓｕｍ  ｏｆ  Ａｂｓｏｌｕｔｅ  Ｄｉｆｆｅｒｅｎｃｅ）をいう。
【００３３】
図７（Ａ）を参照すると、まず、遅延時間ｄはゼロに初期化される（ステップＳ１１）。次に、遅延時間が遅延時間の最大値を上回ったか否かを判定する（ステップＳ１２）。遅延時間の最大値を上回った場合には（ステップＳ１２のＹｅｓ）、処理を終了する。それ以外の場合には（ステップＳ１２のＮｏ）、遅延時間ｄにおける信号ｋと信号ｎとの間のＳＡＤを計算する（ステップＳ１３）。
【００３４】
図７（Ｂ）は、ＳＡＤの計算のフローチャートを示す。ＳＡＤは、信号ｋと信号ｎを遅延時間ｄだけ遅延させた信号との間の差分の絶対値との総和として求める（ステップＳ２１）。
【００３５】
次に、遅延時間を時間刻み０．１ｎｓだけ増加させる（ステップＳ１４）。以上のステップＳ１２〜Ｓ１４の工程を、遅延時間が最大値を上回るまで繰り返す。
【００３６】
図８は、図４の電子回路のネットリスト形式による表現である。図８は、一例として、電子回路シミュレータであるＳＰＩＣＥシミュレータの入力データを示す。
【００３７】
図９は、図８のネットリストから、信号１〜６の相互の関係を表した表であり、○が付けられている信号同士に関連があることを示している。
【００３８】
図１２は、図９の表を用いることなく、図６の信号波形のみを用いて、類似信号を検索し、差分の絶対値の総和が最小となる遅延時間ｄを求める従来の方法に対するフローチャートを示す。
【００３９】
ここでは、一例として、遅延時間ｄの最大値は５０ｎｓとした。また、遅延時間ｄを探索する時間刻みは０．１ｎｓとした。図１２（Ａ）を参照すると、信号ｎと信号ｋのあらゆる組合せについて、ＳＡＤの計算が行われる（ステップＳ３１〜Ｓ４０）。ステップＳ３５〜Ｓ３８における処理は、図７（Ａ）のステップＳ１１〜Ｓ１４における処理と同様である。図１２（Ｂ）におけるＳＡＤを求める処理（ステップＳ５１）も、図７（Ｂ）における処理（ステップＳ２１）と同様である。
【００４０】
図１２を参照すると、６つの信号から、類似信号を検索するためにすべての組合せについて検索を行っている。このとき、６Ｃ２＝１５通りの組合せを比較する必要がある。一般に、信号の比較回数は信号の総数の２乗に比例する。したがって、信号の総数が増えるにつれて、比較回数は急激に増大し、膨大な計算時間が必要とされる。
【００４１】
これに対して、本実施例では、図８に示したネットリストから、図９のように信号相互の関係を示した表を生成して類似信号を検出することができる。したがって、本実施例に対するフローチャート（図７）においては、図１２のフローチャートとは異なり、信号ｋ、ｎのすべての組合せを検討するループを必要としない。すなわち、従来の方法（図１２）と比較して、計算時間を大幅に短縮することができる。
【実施例２】
【００４２】
本発明のデータ圧縮装置の第２の実施例について、図面を参照して説明する。本実施例におけるプログラムは、レンダリングプログラムである。
【００４３】
図１０（Ａ）は、３次元ＣＧ（コンピュータ・グラフィックス）によって動画を作成する場合に、レンダリングプログラムに入力される図面の一例を示す。図１０（Ａ）を参照すると、物体４１は、平面４３における経路４２に沿って動く。図１０（Ｂ）は、レンダリングプログラムによって図１０（Ａ）を解釈した結果を示す。図１０（Ｂ）は、動画の各フレームにおける物体４１の位置を示す。
【００４４】
図１１（Ａ）〜（Ｅ）は、図１０（Ａ）に基づいて、レンダリングプログラムが生成した動画の各フレームを示す。図１１（Ａ）〜（Ｅ）のそれぞれが、フレーム１〜５に対応している。図１１（Ａ）〜（Ｅ）おいて、点線で示した立体は、他のフレームにおける物体４１の位置を示す。実際の動画の各フレームにおいては、物体４１は実線で示された箇所のみに表示される。
【００４５】
図１１（Ａ）〜（Ｅ）は、３次元ＣＧのレンダリングプログラムによって生成された動画の各フレームを示す。この動画の動画圧縮を行う場合には、例えば、図１１（Ａ）に示されたフレーム１と、図１１（Ｂ）に示されたフレーム２との類似性を利用する。すなわち、これらのフレーム間の差分のみを記録することによって、動画の情報量を圧縮することができる。
【００４６】
ＭＰＥＧ１その他の標準的動画圧縮方式においては、単純にフレーム間の差分を取るのではなく、動画に映っている物体のフレーム間における動きを検出することによって、フレーム間の差分をより小さくし、高いデータ圧縮率を得る技術（いわゆる動き補償技術）を使用している。したがって、フレーム１における物体４１の位置と、フレーム２における物体４１の位置との差を検出する必要がある。
【００４７】
従来の技術においては、フレームを適当なサイズの部分画像に分割して、前のフレームのどの位置の画像と最も近いかを検索し、動き補償を実現している。一例として、各フレームが３２０×２４０画素で構成される各フレームを、１６×１６画素の３００個の部分画像に分割し、各部分画像が前のフレームのどの位置にもっとも良く一致するかを１画素単位で検索するものとする。このとき、従来の動き補償は、３２０×２４０画素×３００部分画像に相当する２，３０４万回の画像の比較を必要とし、膨大な計算量を要する。
【００４８】
一方、本発明に係るデータ圧縮装置は、図１０（Ａ）に示す物体４１の経路４２を入力情報として利用することで、各フレームにおいて、前のフレームにおける物体４１の位置
を知ることが出来る。例えば、フレーム２おいて、物体４１を含む部分画像は、フレーム１において物体４１があった付近においてもっとも良く一致する。したがって、データ圧縮装置は、この付近のみを検索することによって、画像比較の回数を従来と比較して大幅に削減することができる。
【００４９】
ゆえに、本発明に係るデータ圧縮装置によって、動き補償のためのフレーム間の物体の動きの検出を高速化することができ、圧縮に要する時間を削減することができる。以上の記載は実施例に基づいて行ったが、本発明は、上記実施例に限定されるものではない。
【図面の簡単な説明】
【００５０】
【図１】本発明の第１の実施形態に係るデータ圧縮装置の構成を示すブロック図である。
【図２】本発明の第２の実施形態に係るデータ圧縮方法のフローチャートである。
【図３】本発明の第３の実施形態に係るデータ圧縮プログラムを実行するコンピュータのブロック図である。
【図４】シミュレーションプログラムのシミュレーション対象を示す図である。
【図５】シミュレーションプログラムの出力データを示す図である。
【図６】シミュレーションプログラムの出力データにおいて相関のあるデータ間で差分を求めた結果を示す図である。
【図７】本発明の第１の実施例におけるデータ圧縮方法のフローチャートを示す。
【図８】シミュレーションプログラムの入力データを示す。
【図９】シミュレーションプログラムの出力データにおいて、相関を有するデータを示す。
【図１０】本発明の第２の実施例におけるレンダリングプログラムの出力データを示す図である。
【図１１】本発明の第２の実施例におけるレンダリングプログラムの出力データに含まれる物体の動きを説明するための図である。
【図１２】従来のデータ圧縮方法のフローチャートを示す。
【符号の説明】
【００５１】
１０  データ圧縮装置
１１  抽出部
１２  圧縮部
２０  コンピュータ
２１  ＣＰＵ
２２  記憶装置
２３  入力装置
２４  出力装置
３１  インバータ回路
４１  物体
４２  経路
４３  平面
【図１】
2010130208.tif 000003
【図２】
2010130208.tif 000004
【図３】
2010130208.tif 000005
【図４】
2010130208.tif 000006
【図５】
2010130208.tif 000007
【図６】
2010130208.tif 000008
【図７】
2010130208.tif 000009
【図８】
2010130208.tif 000010
【図９】
2010130208.tif 000011
【図１０】
2010130208.tif 000012
【図１１】
2010130208.tif 000013
【図１２】
2010130208.tif 000014