(57)【要約】【課題】 本発明は、従来の圧縮方法を補完するばかりでなく、新たな圧縮方法を提供することで、１次元時系列データの性質に合わせた圧縮が行なえ、圧縮方法の選択の幅を広げることを可能とすることを目的する。【解決手段】 本発明における時系列データ圧縮方法の全体の処理は第１段階Ｓ１から第９段階Ｓ９で実行される。第１段階Ｓ１は処理Ｐ１から処理Ｐ３で、第２段階Ｓ２は処理Ｐ４で、第３段階Ｓ３は処理Ｐ５と処理Ｐ６で、第４段階Ｓ４は処理７で、第５段階Ｓ５は処理Ｐ８で、第６段階Ｓ６は処理Ｐ９と処理Ｐ１０で、第７段階Ｓ７は処理Ｐ１１で、第８段階Ｓ８は処理Ｐ４から処理Ｐ１３で、第９段階Ｓ９は処理Ｐ１４で実行される。【選択図】      図２
2006203937.tif 000002
【特許請求の範囲】
【請求項１】
ＣＧ画像処理分野における１次元時系列データの圧縮方法であって、
前記１次元時系列データと近似精度の入力を行う第１の工程と、
前記１次元時系列データを近似する補間関数の節点候補を算出する第２の工程と、
前記節点候補に基づき前記補間関数により発生した１次元時系列データと元の１次元時系列データとの誤差を算出し、誤差の最大値と誤差の平均値と誤差の分散との重み付け加算で算出される第１の目的関数の値を算出する第３の工程と、
前記第１の目的関数の値が最小となるように節点候補の変更を繰り返し行い、準最適節点候補を決定する第４の工程と、
前記第４の工程で算出した目的関数の最小値が前記近似精度に基づいて定めた閾値を越えると判断された場合に、節点候補数を変更し、前記第２の工程に戻る第５の工程と、
前記第４の工程で算出した目的関数の最小値が前記近似精度に基づいて定めた閾値を超えないと判断された場合に、当該準最適節点候補のデータとこれに対応する時刻のデータとを圧縮された情報として出力する第６の工程とを含む、
ことを特徴とする時系列データ圧縮方法。
【請求項２】
ＣＧ画像処理分野における１次元時系列データ圧縮プログラムを記録した記録媒体であって、
前記１次元時系列データと近似精度の入力を行う第１の工程と、
前記１次元時系列データを近似する補間関数の節点候補を算出する第２の工程と、
前記節点候補に基づき前記補間関数により発生した１次元時系列データと元の１次元時系列データとの誤差を算出し、誤差の最大値と誤差の平均値と誤差の分散との重み付け加算で算出される第１の目的関数の値を算出する第３の工程と、
前記第１の目的関数の値が最小となるように節点候補の変更を繰り返し行い、準最適節点候補を決定する第４の工程と、
前記第４の工程で算出した目的関数の最小値が前記近似精度に基づいて定めた閾値を越えると判断された場合に、節点候補数を変更し、前記第２の工程に戻る第５の工程と、
前記第４の工程で算出した目的関数の最小値が前記近似精度に基づいて定めた閾値を超えないと判断された場合に、当該準最適節点候補のデータとこれに対応する時刻のデータとを圧縮された情報として出力する第６の工程とを含む、
各工程をコンピューターに実行させるための時系列データ圧縮プログラムを記録した記録媒体。
【請求項３】
ＣＧ画像処理分野における１次元時系列データの圧縮装置であって、
前記１次元時系列データと近似精度の入力を行う入力手段と、
前記１次元時系列データを近似する補間関数の節点候補を算出する節点候補算出手段と、
前記節点候補に基づき前記補間関数により発生した１次元時系列データと元の１次元時系列データとの誤差を算出し、誤差の最大値と誤差の平均値と誤差の分散との重み付け加算で算出される第１の目的関数の値を算出する判定手段と、
前記第１の目的関数の値が最小となるように節点候補の変更を繰り返し行い、準最適節点候補を決定する節点位置最適化手段と、
前記判定手段により、前記第１の目的関数の最小値が前記近似精度に基づいて定めた閾値を越えると判断された場合に、節点候補数を変更し、該節点数が変更された１次元時系列データを前記前記節点候補算出手段に入力する節点数変更手段と、
前記判定手段により、前記目的関数の最小値が前記近似精度に基づいて定めた閾値を超えないと判断された場合に、当該準最適節点候補のデータとこれに対応する時刻のデータとを圧縮された情報として出力する出力手段とを備えた、
ことを特徴とする時系列データ圧縮装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、時系列データ圧縮方法，時系列データ圧縮プログラム記録媒体，および時系列データ圧縮装置に関するものであり、これらは信号処理技術の分野に属するものであるが、剛体多関節物体の動きやメッシュ状の面の変形、弾性物体の変形などを記述した時系列データにも適用できるものである。
【背景技術】
【０００２】
近年のインターネットの発展には目覚ましいものがある。インターネットではＨＴＭＬ（Ｈｙｐｅｒ  Ｔｅｘｔ  Ｍａｋｅｕｐ  Ｌａｎｇｕａｇｅ）により２次元の画像や音声信号を扱うことが可能であることから、インターネットを画像情報や音声情報等の各種マルチメディア情報の伝達媒体として利用することが可能となっている。
しかしながら、このＨＴＭＬは２次元の画像を扱うことは可能であるが、３次元のＣＧ画像を扱うことができず、３次元画像の処理を可能にする言語としてＶＲＭＬ（Ｖｉｒｔｕａｌ  Ｒｅａｌｉｔｙ  Ｍｏｄｅｌｉｎｇ  Ｌａｎｇｕａｇｅ）が提案されるに至っている。
【０００３】
ただ、ＶＲＭＬでは人間の動きを示す３次元ＣＧ画像を表現するのは難しく、これを実現しようとすれば人間を剛体多関節物体とみなし、各関節毎にその位置等を時系列データとして記述すればよいが、この場合、発生するデータの量が膨大になる。
このデータ量の問題を回避するためには、関節位置等の多次元の時系列データを１次元の時系列データに分解し、それぞれの１次元時系列データ毎にその圧縮を行えばよい。
【０００４】
このような１次元時系列データの圧縮方法として、一般的に適用される方法は、音響工学などで信号処理を行う際に用いられている，離散フーリエ変換や離散コサイン変換などの直交変換を用いて情報を圧縮する方法である。
【０００５】
この直交変換に関する参考文献としては、非特許文献１などがある。
また、剛体多関節物体の関節角の時系列データに関する参考文献としては、非特許文献２がある。
【非特許文献１】日本音響学会編，中田和男著，「音声」，コロナ社，１９７７年
【非特許文献２】Unuma,M, et al., "Fourier Principles for Emotion-based Human Figure Animation", SIGGRAPH95 Proceedings, pp91-95, 1995.
【０００６】
ところで、この直交変換を用いて情報を圧縮する方法は、まず、与えられた１次元時系列データを、全ての時刻におけるデータを用いて、離散フーリエ級数展開表現や離散コサイン級数展開表現に変換する。次に、変換された級数展開表現の高周波成分をカットすることで、情報量を圧縮する、というものである。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
そして、このような直交変換を用いて圧縮された情報に対しては、逆フーリエ変換や逆コサイン変換を適用することにより、情報の伸長を行なうことができる。そして、その際、伸長されたデータとしては、元のデータと同じ個数のデータを生成するのみならず、元のデータとは個数が異なる，任意個のデータを生成することも可能であるが、基底が三角関数のため、その性質が伸長されたデータに反映されてしまう。
【０００８】
本発明は、上記のような従来のものの問題点を解決するためになされたもので、１次元時系列データの性質に合わせた圧縮を行なうことができ、伸長されたデータの個数を元のデータの個数と異ならせたとしても、圧縮，伸長の処理の影響が伸長後のデータに及んでしまうことが少なく、また、データの統計的な性質を利用して圧縮を行うのではなく、圧縮の際に指定する，元のデータとの誤差の範囲内に収まるようにデータを圧縮する圧縮方法であるため、従来の圧縮方法を補完する，新たな圧縮方法を提供することができ、圧縮，伸長方法の選択の幅を広げることを可能とする時系列データ圧縮方法，時系列データ圧縮プログラム記録媒体，および時系列データ圧縮装置を得ることを目的としてなされたものである。
【課題を解決するための手段】
【０００９】
この発明の請求項１記載の時系列データ圧縮方法は、ＣＧ画像処理分野における１次元時系列データの圧縮方法であって、前記１次元時系列データと近似精度の入力を行う第１の工程と、前記１次元時系列データを近似する補間関数の節点候補を算出する第２の工程と、前記節点候補に基づき前記補間関数により発生した１次元時系列データと元の１次元時系列データとの誤差を算出し、誤差の最大値と誤差の平均値と誤差の分散との重み付け加算で算出される第１の目的関数の値を算出する第３の工程と、前記第１の目的関数の値が最小となるように節点候補の変更を繰り返し行い、準最適節点候補を決定する第４の工程と、前記第４の工程で算出した目的関数の最小値が前記近似精度に基づいて定めた閾値を越えると判断された場合に、節点候補数を変更し、前記第２の工程に戻る第５の工程と、前記第４の工程で算出した目的関数の最小値が前記近似精度に基づいて定めた閾値を超えないと判断された場合に、当該準最適節点候補のデータとこれに対応する時刻のデータとを圧縮された情報として出力する第６の工程とを含むようにしたものである。
【００１０】
この発明の請求項２記載の時系列データ圧縮プログラム記録媒体は、ＣＧ画像処理分野における１次元時系列データ圧縮プログラムを記録した記録媒体であって、前記１次元時系列データと近似精度の入力を行う第１の工程と、前記１次元時系列データを近似する補間関数の節点候補を算出する第２の工程と、前記節点候補に基づき前記補間関数により発生した１次元時系列データと元の１次元時系列データとの誤差を算出し、誤差の最大値と誤差の平均値と誤差の分散との重み付け加算で算出される第１の目的関数の値を算出する第３の工程と、前記第１の目的関数の値が最小となるように節点候補の変更を繰り返し行い、準最適節点候補を決定する第４の工程と、前記第４の工程で算出した目的関数の最小値が前記近似精度に基づいて定めた閾値を越えると判断された場合に、節点候補数を変更し、前記第２の工程に戻る第５の工程と、前記第４の工程で算出した目的関数の最小値が前記近似精度に基づいて定めた閾値を超えないと判断された場合に、当該準最適節点候補のデータとこれに対応する時刻のデータとを圧縮された情報として出力する第６の工程とを含む各工程をコンピューターに実行させるための時系列データ圧縮プログラムを記録するようにしたものである。
【００１１】
この発明の請求項３記載の時系列データ圧縮装置は、ＣＧ画像処理分野における１次元時系列データの圧縮装置であって、前記１次元時系列データと近似精度の入力を行う入力手段と、前記１次元時系列データを近似する補間関数の節点候補を算出する節点候補算出手段と、前記節点候補に基づき前記補間関数により発生した１次元時系列データと元の１次元時系列データとの誤差を算出し、誤差の最大値と誤差の平均値と誤差の分散との重み付け加算で算出される第１の目的関数の値を算出する判定手段と、前記第１の目的関数の値が最小となるように節点候補の変更を繰り返し行い、準最適節点候補を決定する節点位置最適化手段と、前記判定手段により、前記第１の目的関数の最小値が前記近似精度に基づいて定めた閾値を越えると判断された場合に、節点候補数を変更し、該節点数が変更された１次元時系列データを前記前記節点候補算出手段に入力する節点数変更手段と、前記判定手段により、前記目的関数の最小値が前記近似精度に基づいて定めた閾値を超えないと判断された場合に、当該準最適節点候補のデータとこれに対応する時刻のデータとを圧縮された情報として出力する出力手段とを備えるようにしたものである。
【発明の効果】
【００１２】
この発明の請求項１記載の時系列データ圧縮方法によれば、ＣＧ画像処理分野における１次元時系列データの圧縮方法であって、前記１次元時系列データと近似精度の入力を行う第１の工程と、前記１次元時系列データを近似する補間関数の節点候補を算出する第２の工程と、前記節点候補に基づき前記補間関数により発生した１次元時系列データと元の１次元時系列データとの誤差を算出し、誤差の最大値と誤差の平均値と誤差の分散との重み付け加算で算出される第１の目的関数の値を算出する第３の工程と、前記第１の目的関数の値が最小となるように節点候補の変更を繰り返し行い、準最適節点候補を決定する第４の工程と、前記第４の工程で算出した目的関数の最小値が前記近似精度に基づいて定めた閾値を越えると判断された場合に、節点候補数を変更し、前記第２の工程に戻る第５の工程と、前記第４の工程で算出した目的関数の最小値が前記近似精度に基づいて定めた閾値を超えないと判断された場合に、当該準最適節点候補のデータとこれに対応する時刻のデータとを圧縮された情報として出力する第６の工程とを含むようにしたので、与えられた１次元時系列データの性質に合わせた圧縮が行なえ、伸長後の誤差を前もって把握することができる、時系列データ圧縮方法が得られる効果がある。
【００１３】
この発明の請求項２記載の時系列データ圧縮プログラム記録媒体によれば、ＣＧ画像処理分野における１次元時系列データ圧縮プログラムを記録した記録媒体であって、前記１次元時系列データと近似精度の入力を行う第１の工程と、前記１次元時系列データを近似する補間関数の節点候補を算出する第２の工程と、前記節点候補に基づき前記補間関数により発生した１次元時系列データと元の１次元時系列データとの誤差を算出し、誤差の最大値と誤差の平均値と誤差の分散との重み付け加算で算出される第１の目的関数の値を算出する第３の工程と、前記第１の目的関数の値が最小となるように節点候補の変更を繰り返し行い、準最適節点候補を決定する第４の工程と、前記第４の工程で算出した目的関数の最小値が前記近似精度に基づいて定めた閾値を越えると判断された場合に、節点候補数を変更し、前記第２の工程に戻る第５の工程と、前記第４の工程で算出した目的関数の最小値が前記近似精度に基づいて定めた閾値を超えないと判断された場合に、当該準最適節点候補のデータとこれに対応する時刻のデータとを圧縮された情報として出力する第６の工程とを含む各工程をコンピューターに実行させるための時系列データ圧縮プログラムを記録するようにしたので、与えられた１次元時系列データの性質に合わせた圧縮が行なえ、伸長後の誤差を前もって把握することができる、時系列データ圧縮プログラム記録媒体が得られる効果がある。
【００１４】
この発明の請求項３記載の時系列データ圧縮装置によれば、ＣＧ画像処理分野における１次元時系列データの圧縮装置であって、前記１次元時系列データと近似精度の入力を行う入力手段と、前記１次元時系列データを近似する補間関数の節点候補を算出する節点候補算出手段と、前記節点候補に基づき前記補間関数により発生した１次元時系列データと元の１次元時系列データとの誤差を算出し、誤差の最大値と誤差の平均値と誤差の分散との重み付け加算で算出される第１の目的関数の値を算出する判定手段と、前記第１の目的関数の値が最小となるように節点候補の変更を繰り返し行い、準最適節点候補を決定する節点位置最適化手段と、前記判定手段により、前記第１の目的関数の最小値が前記近似精度に基づいて定めた閾値を越えると判断された場合に、節点候補数を変更し、該節点数が変更された１次元時系列データを前記前記節点候補算出手段に入力する節点数変更手段と、前記判定手段により、前記目的関数の最小値が前記近似精度に基づいて定めた閾値を超えないと判断された場合に、当該準最適節点候補のデータとこれに対応する時刻のデータとを圧縮された情報として出力する出力手段とを備えるようにしたので、与えられた１次元時系列データの性質に合わせた圧縮が行なえ、伸長後の誤差を前もって把握することができる、時系列データ圧縮装置が得られる効果がある。
【発明を実施するための最良の形態】
【００１５】
実施の形態１．
以下、本発明の実施の形態１の時系列データ圧縮方法について、図面を参照しながら説明する。
図１は本発明の実施の形態１における時系列データ圧縮方法の処理の流れを示すものである。
【００１６】
図において、Ｐ４ａは１次元時系列データとその近似精度値の入力を行う入力処理、Ｐ１ａはこの１次元時系列データを近似する補間関数が通過する節点の候補を算出する節点候補算出処理、Ｐ１ｂはこの節点候補算出処理Ｐ１ａにより算出された節点候補の位置を最適化する節点位置最適化処理、Ｐ１ｃはこの節点位置最適化処理Ｐ１ｂにより得られた節点を通る補間関数と元の１次元時系列データとの誤差が入力処理Ｐ４ａで入力した近似精度値に応じた値を満足しているか否かを判定する判定処理、Ｐ１ｄはこの判定処理Ｐ１ｃで近似精度を満足していないと判定された場合に、節点数を変化させる節点数変更処理、Ｐ４ｂは判定処理Ｐ１ｃにより、節点を通る補間関数と元の１次元時系列データとの誤差が入力処理Ｐ４ａで入力した近似精度値に応じた値を満足している場合に圧縮情報としてこの節点およびそのインデックスを出力する出力処理である。
【００１７】
本実施の形態１の時系列データの圧縮方法は、補間関数を使用して、与えられた１次元時系列データのデータ数より少数の節点数を発生することでデータの圧縮を実現しようとするものである。即ち、元の１次元時系列データに近似したデータを再現するのに必要な，補間関数の節点を算出し、その節点以外のデータを省いて伝送することにより、データの圧縮を行うものである。そしてその伸長は、伝送されてきたデータを、圧縮の際に用いた補間関数と同じ補間関数を用いて、圧縮時に省略したデータと同じデータを発生することにより、元の時系列データに近似した時系列データを生成することにより行うものである。
【００１８】
より詳しくは、図１に示すように、入力処理Ｐ４ａにおいて、圧縮すべき１次元時系列データとその近似精度値を入力し、節点候補算出処理Ｐ１ａにおいて、１次元時系列データを構成する全ての１次元データのなかから節点候補を算出し、所定の補間関数がこの節点データを通ることにより元の１次元時系列データを近似した１次元時系列データを生成できるような節点候補を算出し、節点位置最適化処理Ｐ１ｂにおいて、この節点候補を移動して節点位置の最適化を行い、判定処理Ｐ１ｃにおいて、この最適化を行った節点候補を通る所定の補間曲線と元の１次元時系列データとの誤差に基づく値が入力処理Ｐ４ａにおいて入力した近似精度値の範囲内か否かを判定し、近似精度の範囲内であれば、直ちに出力処理Ｐ４ｂにより節点位置の最適化を行った節点候補とそのインデックスを圧縮した１次元時系列データとして出力する。
【００１９】
また、判定処理Ｐ１ｃにおいて、近似精度の範囲内に入らないことが判明すれば、節点数変更処理Ｐ１ｄにおいて、節点数を適宜増加あるいは減少させて節点数の変更を行う。
この節点数変更処理Ｐ１ｄにより節点の変更を行った後に、節点候補算出手段Ｐ１ａに戻って再度節点候補の算出を行い、以下同様の処理を繰り返す。
【００２０】
このように、図１に示されたデータ圧縮方法は、補間関数を使用して、与えられた１次元時系列データのデータ数より少数の節点数を発生することでデータの圧縮を実現しようとするものであるため、補間関数として離散フーリエ級数展開や離散コサイン級数展開を用いれば、それらの係数を求める位置を確実に元の時系列データより減らすことができる。また、節点はその位置のみならず個数についても最適化を行っているので、伸長したデータと元のデータとの誤差が少なく、しかも圧縮率のよい圧縮が可能になっている。また、圧縮の際に、伸長の際に発生する，誤差の範囲を大きく指定すれば、その分、節点数をより減少することが可能となり、より圧縮率のよいデータ圧縮を実現することができる。
【００２１】
但し、これらはデータを伸長した際の再現精度に依存して決まる。また、データの圧縮率は、指定した誤差の精度の範囲内で元の時系列データをいかに近似できるかに依存するため、一般にデータの圧縮率は一定とはならない。
その上で更に、従来技術のように高周波成分についてもそのデータをカットするようにすれば、従来技術よりも更に圧縮率を高めることが可能となる。つまり、従来の技術と併用することにより、従来技術における圧縮率をより高めるための補完方法としても使用できる。
【００２２】
もちろん、高周波成分をカットせず、本実施の形態１の圧縮方法だけでデータを圧縮した場合でも、選択した節点数が、従来技術の圧縮方法における高周波成分のカット後に残った周波数成分の個数よりも少なければ、圧縮率は本発明の方が高いことになる。しかし、それは与えられた１次元時系列データの性質に依存して決まるので、一概に、どちらの方法が圧縮率が高いということはできない。
ただ、本発明により、データ圧縮方法の選択の幅は広げられたことになる。
【００２３】
また、補間関数として多項式形式のもの、例えばスプライン関数などを用いた場合、伸長した場合のデータは、多項式的な変化をするデータとなる。これは、周期性のない１次元時系列データを伸長する場合には、その精度を保持する上で有効に働く。
従って、伸長するデータの個数を元のデータの個数と異ならせて伸長を行ってもその精度を保持できるので、伸長の際に生成するデータを少なくすれば、元のデータを高速に再生でき、高速再生を行ってもそのデータの精度を保持できる。
また、逆に伸長の際に生成するデータを多くすれば、元のデータをスローで再生でき、スローで再生を行ってもそのデータの精度を保持できる。
【００２４】
このように、本実施の形態１は、１次元時系列データの性質に合った圧縮を行なう新たな圧縮方法を提供することで、従来の圧縮方法を補完するばかりでなく、圧縮方法の選択の幅を広げることが可能となるものである。
【００２５】
以下に、本発明の実施の形態１の処理をより詳細に述べるが、その前に、１次元時系列データについて図１２を参照しながら説明する。図１２は１次元時系列データをグラフ化したもので、図中の黒丸は１次元のデータを表わす。このように、１次元のデータとこれに対応する時刻とがペアリングされたデータのことを１次元時系列データという。そして、図１２のようにデータがサンプリングされた時刻をｔ０，．．．，ｔｎと表したとき、ｔｉ−ｔｉ−１の値が任意のｉ＝１，．．．，ｎに対して一定の場合を時間等間隔といい、そうでない場合を時間不等間隔という。
【００２６】
図２は本発明の実施の形態１における時系列データ圧縮方法の処理の流れを示すものである。図２に示したように、全体の処理は第１段階Ｓ１から第９段階Ｓ９までの９つの段階で実行される。第１段階Ｓ１は処理Ｐ１から処理Ｐ３までで構成され、第２段階Ｓ２は処理Ｐ４で構成され、第３段階Ｓ３は処理Ｐ５と処理Ｐ６とで構成され、第４段階Ｓ４は処理Ｐ７で構成され、第５段階Ｓ５は処理Ｐ８で構成され、第６段階Ｓ６は処理Ｐ９と処理Ｐ１０とで構成され、第７段階Ｓ７は処理Ｐ１１で構成され、第８段階Ｓ８は処理Ｐ４から処理Ｐ１３までで構成され、第９段階Ｓ９は処理Ｐ１４で構成されている。
【００２７】
図３は、図２に詳細な処理が示された，図１のフロー処理を行うコンピュータの構成例を示し、図３（ａ）において、１は図２の処理に相当する制御プログラムに従って演算処理を行うＣＰＵ、２はＣＰＵ１が処理を行うデータを記憶するデータメモリ、３は図２の処理に相当する制御プログラムを予め記憶しているメインメモリ、４はこのコンピュータと外部との間でデータの入出力を行う入出力装置、５はこれらＣＰＵ１，データメモリ２，メインメモリ３および入出力装置４が相互にデータ等をやりとりするためのバスである。なお、データメモリ２とメインメモリ３とは同一のメモリを使用して構成してもよい。
ＣＰＵ１は予めメインメモリ３に記憶されている制御プログラムに従って、図２のフローとして示された圧縮処理を実行する。
【００２８】
また、図３（ｂ）はプログラム記録媒体等からプログラムを読み込んで圧縮動作を行うようにしたコンピュータの構成例を示し、図３（ｂ）において、６はバス５につながった外部記憶装置であり、この外部記憶装置の記録媒体には予め図２の処理に相当する制御プログラムが記録されており、外部記憶装置６はその記録媒体より図２の処理に相当する制御プログラムを読み取って、メインメモリ３にロードする。ＣＰＵ１はこのメインメモリ３にロードされた制御プログラムに従って、図２のフローとして示された圧縮処理を実行する。あるいは、入出力装置４を介して外部から供給される制御プログラムをメインメモリ３にロードしてもよい。
【００２９】
次に、以上のように構成された図２の第１段階Ｓ１ないし第９段階Ｓ９について説明する。
まず、処理Ｐ１では、データ圧縮すべき１次元時系列データと、これを近似する補間関数の近似精度値の入力を行なう。処理Ｐ２では１次元時系列データに対しその時刻の順にインデックスをつける。この時刻としては１次元時系列データのサンプル時刻や発生時刻や入力時刻等を用いることができる。なお、このインデックスは時刻の代わりに順次増加するデータや順次減少するデータを用いてもよい。処理Ｐ３では初期の節点数を算出する。その際に使用する節点数の初期値は、補間関数の種類に応じて決まるため、予め、その初期値を設定しておけばよく、従って、例えば、初期のデータ数に対する比を予め決めておくことでこれを算出することができる。ここでは、使用する節点数の初期値として１次元時系列データ全体の個数の１／ａという形で（但し、ａ＞０とする）、初期の節点数を算出するものとする。
【００３０】
処理Ｐ４ではデータ圧縮すべき１次元時系列データの中から、その始めと終りのデータを必ず含み、かつ残りのデータについてはランダムな間隔でデータを選択し、これらを合計すれば上述の算出した節点数と同数となるように節点候補を決定する。
【００３１】
この操作を図１３を用いて説明する。今、仮に節点の個数をｍ＋１とすると、時刻ｔ０におけるデータが始めのデータで、これを最初の節点候補として選択とする。次に、時刻ｔｎにおけるデータが終りのデータで、これを最後の節点候補として選択する。
次に、１／（ｎ−１）の一様確率で生成される乱数により、残りのｍ−１個の節点候補を、互いに重複を許さずに選択する。こうして合計ｍ＋１個の節点候補が選択された後は、これらを時刻の小さい順にソートし、節点候補のインデックスをＩ（ｊ），０≦ｊ≦ｍとして保存しておく。図１３の例では白丸で示したデータが節点候補として選択されたものである。
【００３２】
以上はランダム選択の場合であるが、この節点候補を求める処理Ｐ４はインデックスに関して近似等間隔で選択してもよい。この場合は、まずインデックスに関して間隔［ｎ／ｍ］を算出し、時刻ｔ０における始めのデータから始めてこの間隔［ｎ／ｍ］だけ隔たった節点候補を合計ｍ個選択し、ｍ＋１番目の節点候補として時刻ｔｎにおける終わりのデータを選択することにより終了する。ここで、［ｘ］はガウス記号である。この場合も、前述のようなＩ（ｊ）を保存しておく。
【００３３】
この処理Ｐ４で行う操作は節点候補の位置の初期値を決めるものであり、この種の問題には乱数を用いるのが有効であることが知られているが、本実施の形態１の場合でも、乱数を用いて節点位置を選択した方が近似等間隔で選択した場合よりも実験的に良い値が得られている。
【００３４】
処理Ｐ５ではインデックス番号を独立変数とする補間関数により、各節点候補の間を補間するデータを発生して、元の１次元時系列データを近似する１次元時系列データを得、これと元の１次元時系列データとの誤差を算出する。補間関数は節点を通るものならば何でもよく、例えば、スプライン関数には節点を通る補間関数として使用できる性質がある。ただ、伸長されたデータが元のデータの波形に忠実な波形を再現すべきであれば、元の１次元時系列データを忠実に近似できる補間関数を使用するのが望ましく、逆に高いデータ圧縮率を要求するのであれば、補間関数はさほど近似度を要求されない。その他、離散フーリエ変換を用いた級数展開表現や、離散コサイン変換を用いた級数展開表現なども補間関数として使用できる。ただ、この補間関数は以上に挙げたもののいずれか１つを予め選定しておいて使用する。そして後述する伸長処理の場合に圧縮の際に用いたものと同じ補間関数を使用する。この場合、補間関数はその候補を予め複数用意しておいて、圧縮の際に使用した補間関数の識別子を伸長処理の側に送り、伸長側で圧縮の際と同じ補間関数を用いるようにしてもよい。
【００３５】
図１４は図１２の曲線を補間する補間関数をグラフ化したものである。図中の黒丸は補間関数を用いて白丸で表した節点候補を補間して得たデータであり、これらはデータ圧縮の際には棄却されるものである。この黒丸で示したデータは殆どが元のデータと同じ値になっているが、時刻ｔｎ−１におけるデータに関しては誤差が発生している。
処理Ｐ６では、図１４のように、節点候補以外の１次元時系列データと補間関数との誤差を算出する。図１４の場合、誤差の算出は絶対値誤差を用いて行っているが、この誤差算出は２乗誤差などを用いて行ってもよい。
処理Ｐ７では処理Ｐ６で算出した誤差から、第１目的関数の値を算出する。この第１目的関数は、処理Ｐ６で算出した誤差の最大値と誤差平均と誤差分散をまず求め、これらを重み付け加算して算出することができる。
【００３６】
この目的関数は換言すれば誤差の評価関数であり、選択した節点候補より生成した１次元時系列データと元の１次元時系列データとの誤差の最大値や誤差の平均や誤差の分散がともに小さな値となるものが節点候補として最適なものである，という観点で、誤差の評価がなされるように、誤差の最大値と誤差の平均と誤差の分散とを重み付け加算した値を誤差の評価関数として使用するようにしているものである。
【００３７】
そして、その重み係数は、その値を始めから固定して決めておく方法と、データに応じて可変的に決定する方法とがある。可変的に決定する場合は、例えば、重みを最大誤差、誤差平均、誤差分散について均等に割り振りたいときには、各重みとそれらの値の積が全て等しくなるように決めればよい。最初から決めておく場合は、例えば重み係数の値を予め全て“１／３”とするなどのように決める。一般には、実際のデータを何度か処理して、経験的によいと思われる値を決めることが多い。
【００３８】
処理Ｐ８では第１目的関数の値が最小となるように節点候補の変更を繰り返し行ない、準最適節点候補を決定するのであるが、これについては図１０に示した第１の方法と図１１に示した第２の方法の２通りがある。
【００３９】
この準最適節点候補を決定する処理は、ある節点候補を決めた状態での目的関数の値と、節点候補を変えた状態での目的関数の値とを求めてこれらの差分を求め、この差分が小さくなるように節点候補を選択することにより、局所最適解を得るものである。
この節点候補の決定は、節点の個数が少ない場合は最適解を求めればよいが、節点の個数が多くなると最適解が真に最適となっているか否かは不明となるため、本実施の形態１の場合では局所最適解、すなわち準最適解を得るので十分である。
【００４０】
まず、図１０に示した第１の方法について説明を行なう。図１０から分かるように、この処理は処理Ｐ４１から処理Ｐ５９で構成される。但し前述のように、節点候補のインデックスに対して、時刻が小さい順に番号づけが行なわれており、それをＩ（ｊ），０≦ｊ≦ｍとする。また、以降の図１０の説明においては、ｊはループ制御変数とする。
【００４１】
処理Ｐ４１ではループ制御が行なわれるが、この方法には次の６通りの方法があり、そのうちのいずれか１つを用いてループ制御が行われる。
（１）  奇数のｊについては小さいものから大きいものの順、および偶数のｊについては大きいものから小さいものの順に処理を行なう。
（２）  奇数のｊについては大きいものから小さいものの順、および偶数のｊについては小さいものから大きいものの順に処理を行なう。
（３）  ｊ＝１から［ｍ／２］まで、およびｊ＝ｍ−１から［ｍ／２］＋１まで、順に処理を行なう。
（４）  ｊ＝［ｍ／２］から１まで、およびｊ＝［ｍ／２］＋１からｍ−１まで、順に処理を行なう。
（５）  ｊ＝１からｍ−１まで順に処理を行なう。
（６）  ｊ＝ｍ−１から１まで順に処理を行なう。
処理Ｐ４２では、一連の処理のループを制御するループ制御変数ｊについて、Ｉ（ｊ−１）＜Ｉ（ｊ）−１の関係が成り立つか否かの判定を行なう。もしこの関係が成り立つならば、処理Ｐ４３に移行し、成り立たないならば処理Ｐ４５へ移行する。
【００４２】
処理Ｐ４３では、図１５に示したように節点候補Ｉ（ｊ）と節点候補Ｉ（ｊ）−１とを一時的に交換する。次に、交換後の第１目的関数の値を算出する。関数値を算出した後は交換していた節点候補を元に戻す。
【００４３】
処理Ｐ４４では、処理Ｐ４３で算出した第１目的関数の値から図２の処理Ｐ７で算出した元の第１目的関数の値を減じた値ΔＥ（１−）を算出する。なおΔＥのかっこ内の“１−”は左側に“１”だけずらせる、即ちインデックスを“１”減らすことを意味する。処理Ｐ４５では、先の第１目的関数の値は算出せず、強制的にΔＥ（１−）を“０”とする。
処理Ｐ４６ではＩ（ｊ）＋１＜Ｉ（ｊ＋１）の関係が成り立つか否かの判定を行ない、もし、この関係が成立するならば処理Ｐ４７に移行し、成立しないならば処理Ｐ４９へ移行する。
【００４４】
処理Ｐ４７では、図１５に示したように一時的に節点候補Ｉ（ｊ）と節点候補Ｉ（ｊ）＋１とを交換し、この時の第１目的関数の値を算出する。
処理Ｐ４８では、処理４７で算出した第１目的関数の値から、図２の処理Ｐ７で算出した元の第１目的関数の値を減じた値ΔＥ（１＋）を算出する。処理Ｐ４９では、第１目的関数の値の算出を行なわずに、強制的にΔＥ（１＋）を“０”とする。
【００４５】
処理Ｐ５０では、前記ΔＥ（１−）＜０かつΔＥ（１＋）≧０が成り立つか否かの判定を行なう。もしこの関係が成立するならば、処理Ｐ５１へ移行し、成立しないならば、処理Ｐ５２へ移行する。処理Ｐ５１では、節点候補Ｉ（ｊ）を節点候補Ｉ（ｊ）−１に交換し、交換を行った後は処理Ｐ４１に戻る。
処理Ｐ５２では、ΔＥ（１−）≧０かつΔＥ（１＋）＜０が成り立つか否かの判定を行ない、もしこの関係が成立するならば処理Ｐ５３へ移行し、成立しないならば処理Ｐ５４へ移行する。処理Ｐ５３では節点候補Ｉ（ｊ）を節点候補Ｉ（ｊ）＋１に交換し、交換を行った後は処理Ｐ４１に戻る。
【００４６】
処理Ｐ５４では、ΔＥ（１−）＜０かつΔＥ（１＋）＜０の関係が成り立つか否かの判定を行ない、この関係が成立するならば処理Ｐ５５へ移行し、成立しないならば処理Ｐ４１へ戻る。
処理Ｐ５５では、ΔＥ（１−）≦ΔＥ（１＋）の関係が成り立つか否かの判定を行ない、この関係が成り立つのであれば処理Ｐ５６へ移行し、成り立たないならば処理Ｐ５７へ移行する。処理Ｐ５６では、節点候補Ｉ（ｊ）を節点候補Ｉ（ｊ）−１に交換し、交換が済めば処理Ｐ４１に戻る。処理Ｐ５７では、節点候補Ｉ（ｊ）を節点候補Ｉ（ｊ）＋１に交換し、交換を行った後は処理Ｐ４１へ戻る。
全てのループ制御変数ｊについて、以上の処理が終了したならば、処理Ｐ５８に移行する。
【００４７】
処理Ｐ５８では終了判定を行なう。この終了判定は、全てのｊについて処理Ｐ４１から処理Ｐ５７までの操作が終了した時の第１目的関数の値が元の第１目的関数の値から閾値を減じたものより大きいか、もしくは全てのｊについて、節点候補の前記交換が全く行なわれなかったか否かの判定により実行され、どちらか一方の条件が成立する場合には一連の処理を終了し、終了した時点の解が、準最適節点候補となる。そうでない場合には、処理Ｐ５９において、元の第１目的関数の値を操作が終了した時の第１目的関数に交換し、処理Ｐ４１から処理Ｐ５７の一連の処理を繰り返す。
【００４８】
以上の操作は、処理Ｐ５８における終了判定が成立し、第１目的関数の値が収束するまで繰り返される。なお、この終了判定には、処理の繰り返し回数を基準とする判定条件を付加してもよい。但し、この場合、最適の度合は、繰り返し回数の判定条件を付加しない場合よりも却って悪くなる可能性があるが、処理を必ず一定時間以内で終了させることができる。
【００４９】
次に、図１１に示した第２の方法について説明を行なう。図１１から分かるように、この処理は処理Ｐ６１から処理Ｐ７９で構成される。
但し前述のように、節点候補のインデックスに対して、時刻が小さい順に番号づけが行なわれており、それをＩ（ｊ），０≦ｊ≦ｍと表す。また、図１０の説明の時と同様に、ｊはループ制御変数とする。
【００５０】
処理Ｐ６１は図１０の第１の方法と同様に、一連の処理を繰り返し行うか否かのループ制御を行なうものであり、この方法には次の６通りの方法があり、そのうちのいずれか１つを用いてループ制御が行われる。
（１）  奇数のｊについては小さいものから大きいものの順、および偶数のｊについては大きいものから小さいものの順に処理を行なう。
（２）  奇数のｊについては大きいものから小さいものの順、および偶数のｊについては小さいものから大きいものの順に処理を行なう。
（３）  ｊ＝１から［ｍ／２］まで、およびｊ＝ｍ−１から［ｍ／２］＋１まで、順に処理を行なう。
（４）  ｊ＝［ｍ／２］から１まで、およびｊ＝［ｍ／２］＋１からｍ−１まで、順に処理を行なう。
（５）  ｊ＝１からｍ−１まで順に処理を行なう。
（６）  ｊ＝ｍ−１から１まで順に処理を行なう。
処理Ｐ６２から処理Ｐ７０までは、図１０の第１の方法の処理Ｐ４２から処理Ｐ５０と同様のものである。
【００５１】
処理Ｐ７１では、まず、節点候補Ｉ（ｊ）を節点候補Ｉ（ｊ）−１に交換する。更に、元の第１目的関数の値を、この交換時において算出した第１目的関数の値に更新する。そしてこの更新を行った後、処理Ｐ６１に戻る。
処理Ｐ７２は、図１０の第１の方法の処理Ｐ５２と同様である。
処理Ｐ７３では、まず、節点候補Ｉ（ｊ）を節点候補Ｉ（ｊ）＋１に交換する。更に、元の第１目的関数の値を、この交換時において算出した第１目的関数の値に更新する。そしてこの更新を行った後、処理Ｐ６１に戻る。
処理Ｐ７４と処理Ｐ７５は、図１０の第１の方法の処理Ｐ５４と処理Ｐ５５と同様のものである。
処理Ｐ７６では、節点候補Ｉ（ｊ）を節点候補Ｉ（ｊ）−１に交換する。次に、元の第１目的関数の値を、この交換時において算出した第１目的関数の値に更新する。そしてこの更新を行った後、処理Ｐ６１に戻る。
【００５２】
処理Ｐ７７では、節点候補Ｉ（ｊ）を節点候補Ｉ（ｊ）＋１に交換する。次に、元の第１目的関数の値を、この交換時において算出した第１目的関数の値に更新する。そしてこの更新を行った後、処理Ｐ６１に戻る。
全てのループ制御変数ｊについて、以上の処理が終了したならば、処理Ｐ７８の終了判定を行なうが、これについては図１０の第１の方法の処理Ｐ５８と同様である。処理Ｐ７９については、図１０の第１の方法の処理Ｐ５９と同様である。
【００５３】
この第２の方法は、第１の方法が節点候補に関して一連の処理を実行し終わった時点で第１目的関数値の変更を行うのに対し、節点候補を更新する毎に第１目的関数の値も更新するものである。これら第１，第２の方法のいずれが準最適節点候補の決定方法として優れているかは、データの性質に依存しているので一該には言えないが、一般に目的関数値の収束は第１の方法の方が速いものと思われる。
【００５４】
以上の図１０による第１の方法、または図１１による第２の方法によって、準最適節点候補が決定されたならば、図２の処理Ｐ９により、準最適節点候補を前述の補間関数により、処理Ｐ５と同様の補間を行う。次に、処理Ｐ１０によって、補間により得られた１次元時系列データと元の１次元時系列データとの誤差を処理Ｐ６と同様に算出する。
【００５５】
処理Ｐ１１では、処理Ｐ１０で算出した誤差から、この誤差の最大値と誤差平均と誤差分散との重み付け加算で定義された第２目的関数の値を算出する。この第２目的関数が本来の節点に関する誤差の評価関数である。そしてその重みの値は、例えば、誤差の最大値だけが問題となる時は、最大誤差の重みを“１”、誤差平均と誤差分散については“０”とすればよい。それ以外にも、処理Ｐ７における第１目的関数の時と全く同様に、重みを最大誤差、誤差平均、誤差分散について均等に割り振りたいときには、例えば各重みとそれらの値の積が全て等しくなるように決めたり、最初から決めておく場合は、例えば重み係数の値を予め全て“１／３”とするなどのように決めるようにすればよく、また、第１目的関数の時の、各重みに対する割合などを基準として決定してもよい。
【００５６】
処理Ｐ１２では、処理Ｐ１１で求めた第２目的関数値に対する閾値判定を行なう。例えば、最大誤差の重みを“１”、誤差平均と誤差分散については“０”とした時には、処理Ｐ１において、最初に入力した、近似精度誤差の値そのものを閾値とすればよい。この場合は、全てのデータが近似精度以内か否かの判定を行なっていることになる。閾値判定の結果、閾値より大きいと判定されたときは処理Ｐ１３に移行し、そうでないときは、処理Ｐ１４へと移行する。
【００５７】
処理Ｐ１３では、元の節点数に増分量を加算することで、変更後の節点数を得る。その際の増分量は、予め決めておく。
そして、節点数を所定量増加させると処理Ｐ４に戻り、節点候補の決定以降の一連の処理を行い、処理Ｐ１２で第２目的関数の値が閾値以下と判定されるまで、これらの一連の処理を繰り返す。
【００５８】
そして処理Ｐ１２で第２目的関数の値が閾値以下と判定されると上述のように処理Ｐ１４に移行するが、処理Ｐ１４では、初期時刻と時間間隔量、および、求まった節点候補のインデックス番号とその時のデータ値を出力する。この場合の出力データの形式は、図１６の（ａ）のようになる。
【００５９】
なお、インデックスの出力に関しては、節点候補の個数が最初に入力した１次元時系列データの個数の半分以下か、以上かによって切替えて出力する方法もある。つまり、半分以下の時は、それを示す識別子と節点候補のインデックス番号を出力し、以上の場合は、それを示す識別子と節点候補以外のインデックスを列記する。
また、扱う１次元時系列データの初期時刻と時間間隔が常に一定で、既知の場合は、処理Ｐ１４での出力において、初期時刻と時間間隔を省略してもよい。
【００６０】
このように、本実施の形態１によれば、１次元時系列データを構成する各データのなかから初期の節点候補を決定し、補間関数を用いてこの初期の節点候補から元の１次元時系列データを近似する１次元時系列データを生成して、これらの誤差を算出，評価し、その誤差評価が所期の範囲内に収まるように節点候補を移動させて準最適な節点候補を算出し、この補間関数を用いて準最適な節点候補から元の１次元時系列データを近似する１次元時系列データを生成して、これらの誤差を算出，評価し、その誤差評価が所期の範囲内に収まらないならば、節点数を増やして以上の処理を繰り返すことにより、節点の位置と個数の両者に関して最適化を行い、節点以外のデータについてはこれを伝送しないことによりデータを圧縮するようにしたので、与えられた１次元時系列データの性質に合わせた圧縮が行なうことができる。
また、そのデータの圧縮率は近似精度によってコントロールされるので、伸長後の誤差は前もって把握することができる。
【００６１】
実施の形態２．
実施の形態１では１次元時系列データ圧縮処理をソフトウエアにより実現したが、このデータ圧縮処理は専用のハードウエアにより実現してもよい。
図４は図１の処理フローを専用ハード化した時系列データ圧縮装置を示すものであり、図において、４０ａは１次元時系列データとその近似精度値の入力を行う入力手段、１０ａはこの１次元時系列データを近似する補間関数が通過する節点の候補を算出する節点候補算出手段、１０ｂはこの節点候補算出手段１０ａにより算出された節点候補の位置を最適化する節点位置最適化手段、１０ｃはこの節点位置最適化手段１０ｂにより得られた節点を通る補間関数と元の１次元時系列データとの誤差が入力手段４０ａで入力した近似精度値に応じた値を満足しているか否かを判定する判定手段、１０ｄはこの判定手段１０ｃで近似精度を満足していないと判定された場合に、節点数を変化させる節点数変更手段、４０ｂは判定手段１０ｃにより、節点を通る補間関数と元の１次元時系列データとの誤差が入力手段４０ａで入力した近似精度値に応じた値を満足している場合に圧縮情報としてこの節点およびそのインデックスを出力する出力手段である。
【００６２】
次に動作について説明する。図４に示すように、入力手段４０ａにおいて、圧縮すべき１次元時系列データとその近似精度値を入力し、節点候補算出手段１０ａにおいて、１次元時系列データを構成する全ての１次元データのなかから節点候補を算出し、所定の補間関数がこの節点データを通ることにより元の１次元時系列データを近似した１次元時系列データを生成できるような節点候補を算出し、節点位置最適化手段１０ｂにおいて、この節点候補を移動して節点位置の最適化を行い、判定手段１０ｃにおいて、この最適化を行った節点候補を通る所定の補間曲線と元の１次元時系列データとの誤差に基づく値が入力手段４０ａにおいて入力した近似精度値の範囲内か否かを判定し、近似精度の範囲内であれば、直ちに出力手段４０ｂにより節点位置の最適化を行った節点候補とそのインデックスを圧縮した１次元時系列データとして出力する。
【００６３】
また、判定手段１０ｃにおいて、近似精度の範囲内に入らないことが判明すれば、節点数変更手段１０ｄにおいて、節点数を適宜増加あるいは減少して節点数の最適化を行う。
この節点数変更手段１０ｄにより節点数の変更を行った後に、節点候補算出手段１０ａに戻って再度節点候補の算出を行い、以下同様の処理を繰り返す。
【００６４】
図５は図４の時系列データ圧縮装置のより詳細な構成を示すものである。
図において、４０ａは外部よりデータ圧縮すべき１次元時系列データおよびその近似精度を入力するための入力手段、１１はこの１次元時系列データに対しインデックスを付加するインデックス付加手段、１２はこの１次元時系列データを近似する補間関数が通過する節点の初期の個数を算出する初期節点数算出手段、１３は補間関数が通過する節点の候補を決定する節点候補決定手段、１４はこの節点候補を通る補間関数により節点候補の間にデータを補間する補間実行手段、１５はこの補間関数により得られた１次元時系列データと元の１次元時系列データとの間の誤差を算出する誤差算出手段、１６はこの誤差の評価関数である第１の目的関数値を算出する第１目的関数算出手段、１７はこの節点候補を適宜移動して準最適節点候補を決定する準最適節点候補決定手段、１８はこの準最適節点候補を通る補間関数により準最適節点候補の間にデータを補間する補間実行手段、１９はこの補間関数により得られた１次元時系列データと元の１次元時系列データとの間の誤差を算出する誤差算出手段、２０はこの誤差の評価関数である第２の目的関数値を算出する第２目的関数算出手段、２１はこの第２目的関数の関数値が元の１次元時系列の近似精度に応じた閾値を越えたか否かを判定する閾値判定手段、２２は第２目的関数の関数値が元の１次元時系列データの近似精度に応じた閾値を越えた場合に節点数を変更する節点数変更手段、４０ｂはこの第２目的関数の関数値が元の１次元時系列データの近似精度に応じた閾値を越えない場合に準最適節点候補を元の１次元時系列データの圧縮データとして、インデックスとともに出力する出力手段である。
【００６５】
次に動作について説明する。
まず、入力手段４０ａでは、データ圧縮すべき１次元時系列データと、これを近似する補間関数の近似精度値の入力を行なう。インデックス付加手段１１では１次元時系列データに対しその時刻の順にインデックスをつける。この時刻としては１次元時系列データのサンプル時刻や発生時刻や入力時刻等を用いることができる。なお、このインデックスは時刻の代わりに順次増加するデータや順次減少するデータを用いてもよい。初期節点数算出手段１２では初期の節点数を算出する。その際に使用する節点数の初期値は、補間関数の種類に応じて決まるため、予め、その初期値を設定しておけばよく、従って、例えば、初期のデータ数に対する比を予め決めておくことでこれを算出することができる。ここでは、図２の場合と同様に、使用する節点数の初期値として１次元時系列データ全体の個数の１／ａという形で（但し、ａ＞０とする）、初期の節点数を算出するものとする。
【００６６】
節点候補決定手段１３では、データ圧縮すべき１次元時系列データの中から、その始めと終りのデータを必ず含み、かつ残りのデータについてはランダムな間隔でデータを選択し、これらを合計すれば上述の算出した節点数と同数となるように節点候補を決定する。
この操作は図１３あるいは図１４に示すものと同様に行う。
この節点候補決定手段１３で行う操作は節点候補の位置の初期値を決めるものであり、この種の問題には乱数を用いるのが有効であることが知られているが、本実施の形態２の場合でも、乱数を用いて節点位置を選択した方が近似等間隔で選択した場合よりも実験的に良い値が得られている。
【００６７】
補間実行手段１４ではインデックス番号を独立変数とする補間関数により、各節点候補の間を補間するデータを発生して、元の１次元時系列データを近似する１次元時系列データを得、これと元の１次元時系列データとの誤差を算出する。
この補間関数は図２の場合と同様、スプライン関数や離散フーリエ変換を用いた級数展開表現、離散コサイン変換を用いた級数展開表現などを使用できる。
【００６８】
誤差算出手段１５では、図１４のように、節点候補以外の１次元時系列データと補間関数との誤差を算出する。図１４の場合、誤差の算出は絶対値誤差を用いて行っているが、この誤差算出は２乗誤差などを用いて行ってもよい。
【００６９】
第１目的関数算出手段１６では、誤差算出手段１５で算出した誤差から、第１目的関数の値を算出する。この第１目的関数は、誤差算出手段１５で算出した誤差の最大値と誤差平均と誤差分散をまず求め、これらを重み付け加算して算出することができる。
【００７０】
準最適節点候補決定手段１７では第１目的関数の値が最小となるように節点候補の変更を繰り返し行ない、準最適節点候補を決定するのであるが、これについては、図２の場合と同様，図１０に示した第１の方法と図１１に示した第２の方法の２通りがある。
【００７１】
図１０による第１の方法、または図１１による第２の方法によって、準最適節点候補が決定されたならば、図５の補間実行手段１８により、準最適節点候補を前述の補間関数により、補間実行手段１４と同様に補間する。次に、誤差算出手段１９によって、補間により得られた１次元時系列データと元の１次元時系列データとの誤差を誤差算出手段１５と同様に算出する。
【００７２】
第２目的関数算出手段２０では、誤差算出手段１９で算出した誤差から、この誤差の最大値と誤差平均と誤差分散との重み付け加算で定義された第２目的関数の値を算出する。この第２目的関数が本来の節点に関する誤差の評価関数である。そしてその重みの値は、例えば、誤差の最大値だけが問題となる時は、最大誤差の重みを“１”、誤差平均と誤差分散については“０”とすればよい。それ以外にも、第１目的関数算出手段１６における第１目的関数の時と全く同様に、重みを最大誤差、誤差平均、誤差分散について均等に割り振りたいときには、例えば各重みとそれらの値の積が全て等しくなるように決めたり、最初から決めておく場合は、例えば重み係数の値を予め全て“１／３”とするなどのように決めるようにすればよく、また、第１目的関数の時の、各重みに対する割合などを基準として決定してもよい。
【００７３】
閾値判定手段２１では、第２目的関数算出手段２０で求めた第２目的関数値に対する閾値判定を行なう。例えば、最大誤差の重みを“１”、誤差平均と誤差分散については“０”とした時には、入力手段４０ａにおいて、最初に入力した、近似精度誤差を閾値とすればよい。この場合は、全てのデータが近似精度以内か否かの判定を行なっていることになる。閾値判定の結果、閾値より大きいと判定されたときは節点数変更手段２２に移行し、そうでないときは、出力手段４０ｂへと移行する。
【００７４】
節点数変更手段２２では、節点数の変更を元の節点数に増分を加算することで得る。その際の増分量は、予め決めておく。
そして、節点数を所定量増加させると節点候補決定手段１３に戻り、節点候補の決定以降の一連の処理を行い、閾値判定手段２１で第２目的関数の値が閾値以下と判定されるまで、これらの一連の処理を繰り返す。
【００７５】
そして閾値判定手段２１で第２目的関数の値が閾値以下と判定されると上述のように出力手段４０ｂに移行するが、出力手段４０ｂでは、初期時刻と時間間隔量、および、求まった節点候補のインデックス番号とその時のデータ値を出力する。この場合の出力データの形式は、図１６の（ａ）のようになる。
【００７６】
なお、インデックスの出力に関しては、節点候補の個数が最初に入力した１次元時系列データの個数の半分以下か、以上かによって切替えて出力する方法もある。つまり、半分以下の時は、それを示す識別子と節点候補のインデックス番号を出力し、以上の場合は、それを示す識別子と節点候補以外のインデックスを列記する。
また、扱う１次元時系列データの初期時刻と時間間隔が常に一定で、既知の場合は、出力手段４０ｂでの出力において、初期時刻と時間間隔を省略してもよい。
【００７７】
このように、本実施の形態２によれば、１次元時系列データを構成する各データのなかから初期の節点候補を決定し、補間関数を用いてこの初期の節点候補から元の１次元時系列データを近似する１次元時系列データを生成して、これらの誤差を算出，評価し、その誤差評価が所期の範囲内に収まるように節点候補を移動させて準最適な節点候補を算出し、この補間関数を用いて準最適な節点候補から元の１次元時系列データを近似する１次元時系列データを生成して、これらの誤差を算出，評価し、その誤差評価が所期の範囲内に収まらないならば、節点数を増やして以上の処理を繰り返すことにより、節点の位置と個数の両者に関して最適化を行い、節点以外のデータについてはこれを伝送しないことによりデータを圧縮する処理を専用ハードウエアにより行うようにしたので、与えられた１次元時系列データの性質に合わせた圧縮を迅速に行なうことができる。
また、そのデータの圧縮率は近似精度によってコントロールされるので、伸長後の誤差は前もって把握することができる。
【００７８】
実施の形態３．
次に、本発明の実施の形態３の時系列データ圧縮方法について、図面を参照しながら説明する。
この実施の形態３は、実施の形態１の時系列データ圧縮方法において、いわゆる０列、即ち、１次元時系列データの各データがほぼ“０”とみなし得る範囲内に収まるものが連続する場合に、その処理を省略できるようにしたものである。
【００７９】
図６は本発明の実施の形態３における時系列データ圧縮方法の処理の流れを示すものである。この図６に示したように、全体の処理は図１に示したものと同様であるが、この実施の形態３では、入力処理Ｐ４ａの直後に判定処理Ｐ１ｆを設け、入力処理Ｐ４ａで入力された１次元時系列データが近似精度内におさまるものの場合は直ちに出力処理Ｐ４ｂに移行し、近似精度内に収まらない場合のみ、図１と同様に、節点候補の算出処理Ｐ１ａ等の処理を行うようにしたものである。
【００８０】
図７は、図６の処理をより詳しく示すもので、この図７の処理は、例えば図３のコンピュータにより、第１１段階Ｓ１１から第２０段階Ｓ２０までで実行される。この場合、図３のコンピュータのメインメモリ３には、図７の処理に相当するプログラムが予め、あるいはプログラム記録媒体からロードされる等して記憶されている。第１１段階Ｓ１１は処理Ｐ２１から処理Ｐ２３までで、第１２段階Ｓ１２は処理Ｐ２４で、第１３段階Ｓ１３は処理Ｐ２５で、第１４段階Ｓ１４は処理Ｓ２６と処理Ｓ２７とで、第１５段階Ｓ１５は処理Ｐ２８で、第１６段階Ｓ１６は処理Ｐ２９で、第１７段階Ｓ１７は処理Ｐ３０と処理Ｐ３１とで、第１８段階Ｓ１８は処理Ｐ３２で、第１９段階Ｓ１９は処理Ｐ２５から処理Ｐ３４までで、第２０段階Ｓ２０は処理Ｐ３５で実行される。
【００８１】
以上のように構成された各処理について詳細に説明する。
処理Ｐ２１から処理Ｐ２３までの処理については、図２に示す，本発明の実施の形態１の処理Ｐ１から処理Ｐ３までの処理と同様のものである。
処理Ｐ２４については、与えられた１次元時系列データの全てのデータ値の絶対値が、処理２１において入力された近似精度以下であるか否かについての判定を行なう。その際、近似精度が入力された精度以下であると判定された場合は、いわゆる０列に該当する場合であり、この場合、本実施の形態３の情報圧縮方法では情報圧縮が行われないので、直ちに処理Ｐ３５に移行する。これに対し、少なくとも１つのデータ値の絶対値が近似精度より大きい場合は、処理Ｐ２５に移行する。
【００８２】
処理Ｐ２５から処理Ｐ３４までの処理については、図２における処理Ｐ４から処理Ｐ１３までの処理と同様である。
処理Ｐ３５については、第１３段階Ｓ１３ないし第１９段階Ｓ１９を経て来たた場合には、本発明の実施の形態１の処理Ｐ１４と同様に図１６（ａ）の形式でデータを出力する。これに対し、処理Ｐ２４によって直接処理Ｐ３５に移行して来た場合には、図１６における（ｂ）の形式で出力する。つまり、初期時刻と時間間隔と、全てのデータ値が“０”である旨を示す識別子を出力する。
【００８３】
このように、本実施の形態３によれば、データが近似精度内で“０”とみなし得る範囲内に収まる場合には、その圧縮処理を省略できるようにしたので、“０”とみなせるデータが連続する場合にはその処理を省略でき、特にその個数が多い場合にはより高速なデータ圧縮処理が可能となる効果がある。
【００８４】
実施の形態４．
実施の形態３では１次元時系列データ圧縮処理をソフトウエアにより実現したが、このデータ圧縮処理は専用のハードウエアにより実現してもよい。
図８は図６の処理フローを専用ハード化した時系列データ圧縮装置を示すものであり、図において、図４と同一符号は同一または相当するものを示す。
１０ｆは判定手段であり、入力手段４０ａと節点候補算出手段１０ａとの間に設けられ、入力手段４０ａで入力された１次元時系列データが近似精度内におさまるものの場合は直ちに出力手段４０ｂに移行し、近似精度内に収まらない場合のみ、図６と同様に、節点候補の算出手段１０ａに移行し一連のデータ圧縮処理を行うように、処理の切換制御を行うものである。
【００８５】
図９は図８の時系列データ圧縮装置のより詳細な構成を示すものであり、図において、図５と同一符号は同一または相当するものを示す。２３は入力手段４０ａとインデックス付加手段１１との間に設けられた近似精度内判定手段であり、図８の判定手段１０ｆと同様、入力手段４０ａとインデックス付加手段１１との間に設けられている。
【００８６】
次に図９の動作について説明する。
この図９の時系列データ圧縮装置は、入力手段４０ａとインデックス付加手段１１との間に近似精度内判定手段２３を有しており、近似精度内判定手段２３が、入力手段４０ａで入力された１次元時系列データが近似精度内におさまるか否かの判定を行い、近似精度内におさまる場合は本時系列データ圧縮装置によるデータ圧縮動作が行われない場合であるので、直ちに出力手段４０ｂに移行し、近似精度内に収まらない場合のみ、図６と同様に、インデックス付加手段１１に移行し一連のデータ圧縮処理を行うように、処理の切換制御を行うものである。
【００８７】
このように、本実施の形態４によれば、データが近似精度内で“０”とみなし得る範囲内に収まる場合には、その圧縮処理を省略できるようにしたので、“０”とみなせるデータが連続する場合にその処理を省略でき、特にその個数が多い場合にはより高速なデータ圧縮処理が可能となり、しかもこれらの処理を専用ハードウエアにより行うようにしたので、より一層の高速化が可能となる効果がある。
【００８８】
実施の形態５．
以下では、実施の形態１または実施の形態３の圧縮方法によりデータ圧縮された１次元時系列データを伸長する方法について説明する。
この実施の形態５では、まず、圧縮されたデータの伸長に関して、図１６の（ａ）の形式だけで圧縮されたデータが供給されていることが保証されている場合について説明する。
【００８９】
図１７は実施の形態１の圧縮方法によりデータ圧縮された１次元時系列データ、即ち図１６の（ａ）の形式だけで圧縮されたデータが供給されている場合のデータの伸長方法を示すものである。この伸長方法は３段階により構成されており、図において、Ｐ５ａは実施の形態１による１次元時系列データ圧縮方法で圧縮された圧縮データ等を入力する入力処理、Ｐ１０１ａは補間関数によって圧縮データを補間し伸長を行うデータ伸長処理、Ｐ５ｂは伸長した１次元時系列データを出力する出力処理である。
【００９０】
次にその処理方法について説明する。入力処理Ｐ５ａにおいて、実施の形態１による１次元時系列データ圧縮方法で圧縮された圧縮データと、このデータを伸長した時に生成すべきデータの個数を入力する。次に、データ伸長処理Ｐ１０１ａにおいて、データを圧縮する時に使用したのと同じ補間関数によって圧縮データを補間し伸長を行う。そして、出力処理Ｐ５ｂにおいて、データ伸長処理Ｐ１０１ａによって伸長された１次元時系列データを出力する。
【００９１】
図１８はこの図１７の伸長方法をより詳しく示したものである。
図において、第１段階Ｓ３１は図１７の入力処理Ｐ５ａと同様の入力処理Ｐ１０１から構成されている。第２段階Ｓ３２は圧縮データを補間するデータ補間処理Ｐ１０２，伸長したデータを算出するデータ算出処理Ｐ１０３，伸長したデータに対応する時刻を算出する時刻算出処理Ｐ１０４から構成されている。第３段階Ｓ３３は図１７の出力処理Ｐ５ｂと同様の出力処理Ｐ１０５から構成されている。
【００９２】
この図１８に詳細な処理が示された，図１７の処理は、例えば、図３のコンピュータにより、第１段階Ｓ３１から第３段階Ｓ３３までで実行される。この場合、図３のコンピュータのメインメモリ３には、図１７の処理に相当するプログラムが予め、あるいはプログラム記録媒体からロードされる等して記憶されている。
【００９３】
次にその伸長方法について説明する。まず、その第１段階Ｓ３１において、入力処理Ｐ１０１により、実施の形態１による１次元時系列データ圧縮方法で圧縮された圧縮データと、このデータを伸長した時に生成すべきデータの個数を入力する。
【００９４】
次に第２段階Ｓ３２において、データ補間処理Ｐ１０２により、データを圧縮する時に使用したのと同じ補間関数によって圧縮データを補間し、データの連続化を図り、データ算出処理Ｐ１０３により、その連続化されたものから必要とする個数分のデータを算出し、時刻算出処理Ｐ１０４により、初期時間と時間間隔から時刻を必要とするデータの個数分だけ算出する。但し、補間関数は、圧縮の時と同様にインデックスを独立変数とする関数であり、圧縮データのインデックス列の値を用いて補間関数を生成する。
【００９５】
そして、第３段階Ｓ３３において、出力処理Ｐ１０５により、第２段階Ｓ３２で算出したデータと時刻を伸長した１次元時系列データとして出力する。
以上の伸長方法から分かるように、１次元時系列データを復元する時には、データ数は元のものとは異なった個数にも伸長できる。これは換言すると、１次元時系列データの時間変更を行なうことが可能であることを意味しており、その制御は入力されるデータ数によって行なうことが可能であることを意味している。
【００９６】
このように、本実施の形態５によれば、実施の形態１の方法により情報圧縮された１次元時系列データを伸長でき、しかもその伸長を行うにあたって生成するデータの個数を元の１次元時系列データに対し任意に増減でき、かつその際データの性質を損なうことなく生成データの個数の増減を行うことができる１次元時系列データの伸長方法が得られる効果がある。
【００９７】
実施の形態６．
実施の形態５では１次元時系列データ伸長処理をソフトウエアにより実現したが、このデータ伸長処理は専用のハードウエアにより実現してもよい。
図１９は図１７の処理フローを専用ハード化した時系列データ伸長装置を示すものであり、実施の形態２の圧縮装置によりデータ圧縮された１次元時系列データ、即ち図１６の（ａ）の形式だけで圧縮されたデータが供給されている場合のデータの伸長装置を示すものである。図において、５０ａは実施の形態２による時系列データ圧縮装置で圧縮された圧縮データ等を入力する入力手段、２０ａは補間関数によって圧縮データを補間し伸長を行うデータ伸長手段、５０ｂは伸長した１次元時系列データを出力する出力手段である。
【００９８】
次にその動作について説明する。入力手段５０ａにより、実施の形態２による時系列データ圧縮装置で圧縮された圧縮データと、このデータを伸長した時に生成すべきデータの個数を入力する。次に、データ伸長手段２０ａにより、データを圧縮する時に使用したのと同じ補間関数によって圧縮データを補間し伸長を行う。そして、出力手段５０ｂにより、データ伸長手段２０ａによって伸長された１次元時系列データを出力する。
【００９９】
図２０はこの図１０の伸長装置の構成をより詳しく示したものである。
図において、５０ａは図１９の入力手段５０ａと同様に構成された入力手段である。２１は入力されたデータに対しデータ補間処理を行うデータ補間手段、２２は補間されたデータから伸長されたデータを算出するデータ算出手段、２３はデータに対応する時刻を算出する時刻算出手段である。５０ｂは図１９の出力手段５０ｂと同様に構成された出力手段である。
【０１００】
次にその動作について説明する。まず、入力手段５０ａにより、実施の形態２による時系列データ圧縮装置で圧縮された圧縮データと、このデータを伸長した時に生成すべきデータの個数を入力する。
次にデータ補間手段２１により、データを圧縮する時に使用したのと同じ補間関数によって圧縮データを補間し、データの連続化を図り、データ算出手段２２により、その連続化されたものから必要とする個数分のデータを算出し、時刻算出手段２３により、初期時間と時間間隔から時刻を必要とするデータの個数分だけ算出する。但し、補間関数は、圧縮の時と同様にインデックスを独立変数とする関数であり、圧縮データのインデックス列の値を用いて補間関数を生成する。
【０１０１】
そして、出力手段５０ｂにより、算出したデータと時刻を、伸長した１次元時系列データとして出力する。
このように、本実施の形態６によれば、実施の形態２の装置により情報圧縮された１次元時系列データを専用ハードにより高速に伸長でき、しかもその伸長を行うにあたって生成するデータの個数を元の１次元時系列データに対し任意に増減でき、かつその際データの性質を損なうことなく生成データの個数の増減を行うことができる効果がある。
【０１０２】
実施の形態７．
次に、実施の形態３の圧縮方法によりデータ圧縮された１次元時系列データを伸長する方法について説明する。
この実施の形態７では、図１６（ａ）の形式と図１６（ｂ）の形式のデータが混在して供給されている場合について説明する。
【０１０３】
図２１は実施の形態３の圧縮方法によりデータ圧縮された１次元時系列データ、即ち、図１６（ａ）の形式と図１６（ｂ）の形式が混在してデータが供給されている場合のデータの伸長方法を示すものである。この伸長方法は４段階により構成されており、図において、図１７と同一符号は同一または相当するものを示す。
Ｐ１０１ｂは圧縮データの形式の判別を行なうデータ形式判別処理、Ｐ１０１ｃは圧縮データが全て“０”であると判別された場合にその伸長を行う０データ伸長処理である。
【０１０４】
次にその伸長方法について説明する。図１６（ａ）の形式でデータが供給された場合、データ形式判別処理Ｐ１０１ｂは、そのデータをデータ伸長処理Ｐ１０１ａに渡し、以下、図１７と同様にそのデータを伸長し、出力処理Ｐ５ｂにより出力する。
これに対し、図１６（ｂ）の形式でデータが供給された場合、データ形式判別処理Ｐ１０１ｂは、そのデータを０データ伸長処理Ｐ１０１ｃに渡し、所定の期間にわたって全てが“０”のデータを生成しこれを図１７と同様に出力処理Ｐ５ｂにより出力する。
【０１０５】
図２２はこの図２１の伸長方法をより詳しく示したものである。
この図２２に詳細が示された，図２１の処理は例えば図３のコンピュータにより実行される。この場合、図３のコンピュータには、図２２の処理に相当するプログラムが予め、あるいはプログラム記録媒体からロードされる等して記憶されている。
【０１０６】
図において、第１段階Ｓ４１は図１８の入力処理Ｐ１０１と同様の入力処理Ｐ１０１から構成されている。第２段階Ｓ４２はデータ形式判別処理Ｐ１０６，０データ算出処理Ｐ１０７，時刻算出処理Ｐ１０８から構成されている。第３段階Ｓ４３は図１８の第２段階Ｓ３２と同様、データ補間処理Ｐ１０２，データ算出処理Ｐ１０３，時刻算出処理Ｐ１０４から構成されている。第３段階Ｓ４４は図１８の出力処理Ｐ１０５と同様の出力処理Ｐ１０５から構成されている。
【０１０７】
次にその伸長方法について説明する。まず、第１段階Ｓ４１において、入力処理Ｐ１０１により、１次元時系列データ圧縮方法で圧縮された圧縮データと伸長した時のデータ数を入力する。
【０１０８】
次に第２段階Ｓ４２において、データ形式判別処理Ｐ１０６において、圧縮データの形式の判別を行ない、図１６の（ｂ）の形式の場合、つまり、圧縮データが全て“０”であることを示す識別子の場合は、０データ算出処理Ｐ１０７により、そのデータ数と同数分の“０”を算出し、時刻算出処理Ｐ１０８により、初期時間と時間間隔から時刻をデータ数分だけ算出する。これら算出された“０”データとその時刻は第４段階Ｓ４４における出力処理Ｐ１０５により１次元時系列データとして出力される。
【０１０９】
これに対し、第３段階Ｓ４３は、第２段階Ｓ４２で圧縮データが全て“０”であることを示す識別子ではないと判別された場合、つまり図１６の（ａ）の形式の場合で、この時は、図１８の第２段階Ｓ３２と同様に、圧縮する時に使用した補間関数によって圧縮データを補間し、データの連続化を図り、連続化されたものから入力処理で指定した個数分のデータを算出し、初期時間と時間間隔から時刻をデータと同数分だけ算出する。但し、補間関数は、圧縮の時と同様にインデックスを独立変数とする関数で、圧縮データのインデックス列の値を用いて補間関数を生成する。
【０１１０】
そして、第４段階Ｓ４４において、図１８の第２段階Ｓ３２と同様に、第２段階Ｓ４２または第３段階Ｓ４３で算出したデータと時刻を、データ伸長した１次元時系列データとして出力する。
【０１１１】
以上の伸長方法から分かるように、１次元時系列データを復元する時には、データ数は元のものとは異なった個数にも伸長できる。これは換言すると、１次元時系列データの時間変更を行なうことが可能であることを意味しており、その制御は入力されるデータ数によって行なうことが可能であることを意味している。
【０１１２】
このように、本実施の形態７によれば、実施の形態３の方法により情報圧縮された１次元時系列データを伸長でき、しかもその伸長を行うにあたって生成するデータの個数を元の１次元時系列データに対し任意に増減でき、かつその際データの性質を損なうことなく生成データの個数の増減を行うことができる１次元時系列データの伸長方法が得られる効果がある。
【０１１３】
実施の形態８．
実施の形態７では１次元時系列データ伸長処理をソフトウエアにより実現したが、このデータ伸長処理は専用のハードウエアにより実現してもよい。
図２３は図２１の処理フローを専用ハード化した時系列データ伸長装置を示すものであり、実施の形態４の圧縮装置によりデータ圧縮された１次元時系列データ、即ち、図１６（ａ）の形式と図１６（ｂ）の形式が混在してデータが供給されている場合のデータの伸長装置を示すものである。図において、図１９と同一符号は同一または相当するものを示す。２０ｂは圧縮データの形式の判別を行なうデータ形式判別手段、２０ｃは圧縮データが全て“０”であると判別された場合にその伸長を行う０データ伸長手段である。
【０１１４】
次にその伸長動作について説明する。図１６（ａ）の形式でデータが供給された場合、データ形式判別手段２０ｂは、そのデータをデータ伸長手段２０ａに渡し、以下、図１９と同様にそのデータを伸長し、出力手段５０ｂにより出力する。
【０１１５】
これに対し、図１６（ｂ）の形式でデータが供給された場合、データ形式判別手段２０ｂは、そのデータを０データ伸長手段２０ｃに渡し、所定の期間にわたって全てが“０”のデータを生成しこれを図１９と同様に出力手段５０ｂにより出力する。
【０１１６】
図２４はこの図２３の伸長装置をより詳しく示したものである。図において、図２０と同一符号は同一または相当する部分を示す。２４は入力されたデータの形式を判別するデータ形式判別手段、２５は“０”データを算出する０データ算出手段、２６は“０”データに対応する時刻を算出する時刻算出手段である。
次にその伸長動作について説明する。まず、入力手段５０ａにより、時系列データ圧縮装置で圧縮された圧縮データと伸長した時のデータ数を入力する。
【０１１７】
次に、データ形式判別手段２４において、圧縮データの形式の判別を行ない、図１６の（ｂ）の形式の場合、つまり、圧縮データが全て“０”であることを示す識別子の場合は、０データ算出手段２５により、そのデータ数と同数分の“０”を算出し、時刻算出手段２６により、初期時間と時間間隔から時刻をデータ数分だけ算出する。これら算出された“０”データとその時刻は出力手段５０ｂにより１次元時系列データとして出力される。
【０１１８】
これに対し、データ形式判別手段２４において、圧縮データが全て“０”であることを示す識別子ではないと判別された場合、つまり図１６の（ａ）の形式のデータが入力された場合は、図２０と同様に、圧縮する時に使用した補間関数によって圧縮データを補間し、データの連続化を図り、連続化されたものから入力手段５０ａによって指定された個数分のデータを算出し、初期時間と時間間隔から時刻をデータと同数分だけ算出する。但し、補間関数は、圧縮の時と同様にインデックスを独立変数とし、圧縮データのインデックス列の値を用いて補間関数を生成する。
そして、出力手段５０ｂにおいて、図２０と同様に、算出したデータと時刻を、データ伸長した１次元時系列データとして出力する。
【０１１９】
このように、本実施の形態８によれば、実施の形態４の装置により情報圧縮された１次元時系列データを専用ハードウエアで高速に伸長でき、しかもその伸長を行うにあたって生成するデータの個数を元の１次元時系列データに対し任意に増減でき、かつその際データの性質を損なうことなく生成データの個数の増減を行うことができる効果がある。
【０１２０】
実施の形態９．
なお、本発明は１次元の時系列データにのみ適用できるものではなく、多次元の、即ち複数の１次元時系列データに関する圧縮，伸長に対しても、同様の圧縮，伸長方法や圧縮，伸長装置を適用して実現できる。
例えば、複数の１次元時系列データに対する圧縮は、本発明の実施の形態１，３による圧縮方法や実施の形態２，４による圧縮装置を繰り返し使用することでこれを実行できる。
【０１２１】
本実施の形態９では、このような多次元の時系列データに対しその圧縮を行う場合について、Ｍｏｔｉｏｎ  Ｄａｔａ  Ｃｏｍｐｒｅｓｓｉｏｎを例にとって説明する。
このＭｏｔｉｏｎ  Ｄａｔａ  Ｃｏｍｐｒｅｓｓｉｏｎは既に述べたように、人を剛体多関節物体とみなしてその動きを表現する場合に、人の動きを表現する多次元時系列データのデータ量を圧縮するための手法である。
【０１２２】
Ｍｏｔｉｏｎ  Ｄａｔａは人をモデルとする剛体多関節物体の代表点位置の並進ベクトルと、姿勢ベクトルの３次元空間の座標軸に対する回転量と、各ジョイント（関節）の並進ベクトルと、局所座標系の各座標軸に対する回転量で構成される。
【０１２３】
つまり、剛体多関節物体のジョイント数をｍ、時系列の長さをｎとすると、Ｍｏｔｉｏｎ  Ｄａｔａは
｛Ｍi ＝（Ｃｘi,Ｃｙi,Ｃｚi,θi Cx，θi Cy，θi Cz，ｘi jt0，ｙi jt0，ｚi jt0，θi jtx0，θi jty0，θi jtz0，・・・，ｘi jtm-1，ｙi jtm-1，ｚi jtm-1，θi jtxm-1，θi jtym-1，θi jtzm-1）｜ｉ＝０，１，・・・，ｎ−１｝
で与えられる。但し、この例では回転の順序をｘ軸，ｙ軸，ｚ軸の順に設定しており、Ｃｘi,Ｃｙi,Ｃｚi はルート、即ち剛体上の位置の基準となるポイントの座標値、θi Cx，θi Cy，θi Czはジョイントの姿勢制御角、ｘi jt0，ｙi jt0，ｚi jt0はジョイントのスライド量、θi jtx0，θi jty0，θi jtz0，・・・，ｘi jtm-1，ｙi jtm-1，ｚi jtm-1，θi jtxm-1，θi jtym-1，θi jtzm-1はｍ個のジョイントのｘ軸，ｙ軸，ｚ軸回りの回転角である。
【０１２４】
図２５はこのＭｏｔｉｏｎ  Ｄａｔａの圧縮方法を示すもので、図において、Ｐ２００はＭｏｔｉｏｎ  Ｄａｔａを入力するＭｏｔｉｏｎ  Ｄａｔａ入力処理、Ｐ２０１は多次元の時系列データであるＭｏｔｉｏｎ  Ｄａｔａを次元数と同数の１次元の時系列データに分解する多次元時系列データ分解処理、Ｐ２０２は分解された１次元の時系列データを実施の形態１あるいは実施の形態３の圧縮方法を用いて圧縮する１次元時系列データ圧縮処理、Ｐ２０３は次元数と同数の１次元時系列データの圧縮が全て終了したか否かを判定する判定処理、Ｐ２０４は圧縮された多次元の時系列データを出力する出力処理である。
図２５の処理は、例えば、図３のコンピュータにより、実行される。この場合、図３のコンピュータのメインメモリ３には、図２５の処理に相当するプログラムが予め、あるいはプログラム記録媒体からロードされる等して記憶されている。
【０１２５】
次にその処理について説明する。まず、入力処理Ｐ２００により、多次元時系列データとしてのＭｏｔｉｏｎ  Ｄａｔａを入力する。次に、分解処理Ｐ２０１により、Ｍｏｔｉｏｎ  Ｄａｔａを要素毎の１次元の時系列データに分解し、各１次元時系列データにインデックス番号を与える。
【０１２６】
この分解処理Ｐ２０１以降の処理は実施の形態１または実施の形態３の１次元時系列データの圧縮方法と同様のものである。
即ち、分解処理Ｐ２０１の後の１次元時系列データ圧縮処理Ｐ２０２により、実施の形態１または実施の形態３と同様の圧縮方法により、分解後の各々の１次元時系列データに対し圧縮処理を行う。
そして、判定処理Ｐ２０３により、全ての１次元時系列データに対し圧縮処理を行ったと判定された時に、出力処理Ｐ２０４により、圧縮された各々の１次元時系列データ、即ち圧縮された，多次元のＭｏｔｉｏｎ  Ｄａｔａを出力する。
【０１２７】
このように、本実施の形態９によれば、多次元時系列データを複数の１次元時系列データに圧縮して、各１次元時系列データ毎に実施の形態１または実施の形態３と同様の圧縮方法を適用して圧縮を行うようにしたので、或る１次元時系列データに関して、元の１次元時系列データと補間関数との誤差が少なくデータの圧縮が行われないような区間が存在したとしても、この区間と同じ区間に関して残りの１次元時系列データのなかにはデータ圧縮できるものが存在することが多いため、多次元時系列データ全体として見れば、元の１／４ないし１／５程度にデータ圧縮を行うことが可能となる。
この多次元時系列データとして、例えば、剛体多関節物（人間）の関節角の時系列データを使用した場合に関する実験では、近似精度にも依存するが、圧縮率０．１６８ないし０．２６４を得ることができた。
【０１２８】
なお、このような、剛体多関節の各関節角の動作を表す１次元時系列データの場合には、誤差が動作の先端に向かって累積していく。従って、近似精度を一定にする場合には、そのような関係のない１次元時系列データに対して用いた値より小さくする必要が生じるが、この場合は、全体の圧縮率が低下することになる。このような不具合を避けるためには、近似精度を一定とせずに、剛体多関節物体の元の方の関節に関しては近似精度を通常の場合より小さくとり、先頭に向かって近似精度を順次増加させて用いることで、圧縮率の低下を、近似精度を一定にしておく場合よりは防ぐことができる。
また、時間に関して不等間隔な１次元時系列データに対しては、時間とデータの各々を独立した１次元のデータとして本実施の形態９の多次元時系列データ圧縮方法を適用し、各々を独立に圧縮すればよい。
【０１２９】
実施の形態１０．
実施の形態９は多次元の時系列データの圧縮処理をソフトウエアにより実現したが、このデータ圧縮処理は専用のハードウエアにより実現してもよい。
図２６は図２５の処理フローを専用ハード化した多次元時系列データ圧縮装置を示すものであり、図において、１００ａはＭｏｔｉｏｎ  Ｄａｔａを入力するＭｏｔｉｏｎ  Ｄａｔａ入力手段、５１は多次元の時系列データであるＭｏｔｉｏｎ  Ｄａｔａをその次元と同数の１次元の時系列データに分解する多次元時系列データ分解手段、５２は分解された１次元の時系列データを実施の形態２あるいは実施の形態４の圧縮装置と同様の構成を用いて圧縮する１次元時系列データ圧縮手段、５３は次元数と同数の１次元時系列データの圧縮が全て終了したか否かを判定する判定手段、１００ｂは圧縮された，多次元の時系列データを出力する出力手段である。
【０１３０】
次にその動作について説明する。まず、入力手段１００ａにより、多次元時系列データとしてのＭｏｔｉｏｎ  Ｄａｔａを入力する。次に、多次元時系列データ分解手段５１により、Ｍｏｔｉｏｎ  Ｄａｔａを要素毎の１次元の時系列データに分解し、各１次元時系列データにインデックス番号を与える。
この分解手段５１以降の動作は実施の形態２または実施の形態４の１次元時系列データの圧縮動作と同様のものである。
即ち、分解手段５１の後の１次元時系列データ圧縮手段５２により、実施の形態２または実施の形態４と同様の圧縮動作により、分解後の各々の１次元時系列データに対し圧縮処理を行う。
【０１３１】
そして、判定手段５３により、全ての１次元時系列データに対し圧縮処理を行ったと判定された時に、出力手段１００ｂにより、圧縮された各々の１次元時系列データ、即ち圧縮された多次元のＭｏｔｉｏｎ  Ｄａｔａを出力する。
【０１３２】
このように、本実施の形態１０によれば、多次元時系列データを複数の１次元時系列データに圧縮して、各１次元時系列データ毎に実施の形態２または実施の形態４と同様の圧縮動作を適用して圧縮を行うようにしたので、専用ハードにより高速に圧縮動作を実行することができ、しかも、或る１次元時系列データに関して、元の１次元時系列データと補間関数との誤差が少なくデータの圧縮が行われないような区間が存在したとしても、この区間と同じ区間に関して残りの１次元時系列データのなかにはデータ圧縮できるものが存在することが多いため、多次元時系列データ全体として見れば、元の１／４ないし１／５程度にデータ圧縮を行うことが可能となる。
この多次元時系列データとして、例えば、剛体多関節物（人間）の関節角の時系列データを使用した場合に関する実験では、近似精度にも依存するが、圧縮率０．１６８ないし０．２６４を得ることができた。
【０１３３】
なお、このような、剛体多関節の各関節角の動作を表す１次元時系列データの場合には、誤差が動作の先端に向かって累積していく。従って、近似精度を一定にする場合には、そのような関係のない１次元時系列データに対して用いた値より小さくする必要が生じるが、この場合は、全体の圧縮率が低下することになる。このような不具合を避けるためには、近似精度を一定とせずに、剛体多関節物体の元の方の関節に関しては近似精度を通常の場合より小さくとり、先頭に向かって近似精度を増加させて用いることで、圧縮率の低下を、近似精度を一定にしておく場合よりは防ぐことができる。
また、時間に関して不等間隔な１次元時系列データに対しては、時間とデータの各々を独立した１次元のデータとして本実施の形態１０の多次元時系列データ圧縮装置を適用し、各々を独立に圧縮すればよい。
【０１３４】
実施の形態１１．
本実施の形態１１では、実施の形態９により圧縮された多次元時系列データの伸長方法を扱うものである。図２７は図２５の圧縮方法により圧縮されたＭｏｔｉｏｎ  Ｄａｔａの伸長を例にとってその伸長方法を示すもので、図において、Ｐ３００は圧縮されたＭｏｔｉｏｎ  Ｄａｔａを入力する多次元圧縮データ入力処理、Ｐ３０１は圧縮された多次元の時系列データを複数の，圧縮された１次元の時系列データに分解する多次元圧縮データ分解処理、Ｐ３０２は分解された１次元の時系列データを実施の形態５あるいは実施の形態７の伸長方法を用いて伸長する１次元時系列データ伸長処理、Ｐ３０３は一連の１次元時系列データの伸長が終了したか否かを判定する判定処理、Ｐ３０４は伸長された一連の１次元時系列データを出力する出力処理である。
この図２７の処理は、例えば図３のコンピュータにより実行される。この場合、図３のコンピュータのメインメモリ３には、図２７の処理に相当するプログラムが予め、あるいはプログラム記録媒体からロードされる等して記憶されている。
【０１３５】
次にその処理フローについて説明する。まず、入力処理Ｐ３００により、圧縮されたＭｏｔｉｏｎ  Ｄａｔａを入力する。次に、分解処理Ｐ３０１により、圧縮されたＭｏｔｉｏｎ  Ｄａｔａを要素毎の１次元の圧縮時系列データに分解し、各圧縮１次元時系列データにインデックス番号を与える。
この分解処理Ｐ３０１以降の処理は実施の形態５または実施の形態７の１次元時系列データの伸長方法と同様のものである。
即ち、分解処理Ｐ３０１の後の１次元時系列データ伸長処理Ｐ３０２により、実施の形態５または実施の形態７と同様の伸長方法により、分解後の各々の１次元時系列データに対し伸長処理を行う。
【０１３６】
そして、判定処理Ｐ３０３により、全ての１次元時系列データに対し伸長処理を行ったと判定された時に、出力処理Ｐ３０４により、圧縮された各々の１次元時系列データ、即ち伸長された多次元のＭｏｔｉｏｎ  Ｄａｔａを出力する。
このように、本実施の形態１１によれば、圧縮された多次元時系列データを複数の１次元時系列データに分解して、各１次元時系列データ毎に実施の形態５または実施の形態７と同様の伸長方法を適用して伸長を行うようにしたので、多次元の圧縮された時系列データに対してもその伸長処理を行うことができる。
【０１３７】
そしてその伸長を行う際、生成するデータの個数は元のデータとは異なる個数に設定することが可能なため、特にＭｏｔｉｏｎ  Ｄａｔａを伸長する場合、元のデータに比べて生成するデータの個数を増すことにより、元の剛体多関節物体よりも遅く動作する剛体多関節物体の映像を生成したり、逆に生成するデータの個数を減らすことにより、元の剛体多関節物体よりも速く動作する剛体多関節物体の映像を生成したりすることが可能であり、物体の動作の編集を容易に行うことが可能となる。
【０１３８】
実施の形態１２．
実施の形態１１は多次元の時系列データの伸長処理をソフトウエアにより実現したが、このデータ伸長処理は専用のハードウエアにより実現してもよい。
図２８は図２７の処理フローを専用ハード化した多次元時系列データ伸長装置を示すものであり、図において、２００ａは圧縮されたＭｏｔｉｏｎ  Ｄａｔａを入力する多次元圧縮データ入力手段、６１は圧縮された多次元の時系列データを複数の，圧縮された１次元の時系列データに分解する多次元圧縮データ分解手段、６２は分解された１次元の時系列データを実施の形態６あるいは実施の形態８の伸長装置と同様の構成を用いて伸長する１次元時系列データ伸長手段、６３は一連の１次元時系列データの伸長が終了したか否かを判定する判定手段、２００ｂは伸長された一連の１次元時系列データを出力する出力処理である。
【０１３９】
次にその動作について説明する。まず、入力手段２００ａにより、圧縮されたＭｏｔｉｏｎ  Ｄａｔａを入力する。次に、分解手段６１により、圧縮されたＭｏｔｉｏｎ  Ｄａｔａを要素毎の１次元の圧縮時系列データに分解し、各圧縮１次元時系列データにインデックス番号を与える。
この分解手段６１以降の処理は実施の形態６または実施の形態８の１次元時系列データの伸長装置と同様のものである。
即ち、分解手段６１の後の１次元時系列データ伸長手段６２により、実施の形態６または実施の形態８と同様の伸長装置により、分解後の各々の１次元時系列データに対し伸長処理を行う。
【０１４０】
そして、判定手段６３により、全ての１次元時系列データに対し伸長処理を行ったと判定された時に、出力手段２００ｂにより、圧縮された各々の１次元時系列データ、即ち伸長された多次元のＭｏｔｉｏｎ  Ｄａｔａを出力する。
このように、本実施の形態１２によれば、圧縮された多次元時系列データを複数の１次元時系列データに分解して、各１次元時系列データ毎に実施の形態６または実施の形態８と同様の伸長装置を適用して伸長を行うようにしたので、多次元の圧縮された時系列データに対してもその伸長処理を専用ハードにより高速に行うことができる。
【０１４１】
そしてその伸長を行う際、生成するデータの個数は元のデータとは異なる個数に設定することが可能なため、特にＭｏｔｉｏｎ  Ｄａｔａを伸長する場合、元のデータに比べて生成するデータの個数を増すことにより、元の剛体多関節物体よりも遅く動作する剛体多関節物体の映像を生成したり、逆に生成するデータの個数を減らすことにより、元の剛体多関節物体よりも速く動作する剛体多関節物体の映像を生成したりすることが可能であり、物体の動作の編集を容易に行うことが可能となる。
【産業上の利用可能性】
【０１４２】
以上のように、本発明にかかる時系列データ圧縮方法、時系列データ圧縮プログラムを記録した記録媒体、および時系列データ圧縮装置は、３次元ＣＧ画像として表現された剛体多関節物体を表わす多次元時系列データを分解した１次元時系列データを圧縮する用途に用いて好適である。
【図面の簡単な説明】
【０１４３】
【図１】本発明の実施の形態１における時系列データ圧縮方法の処理構成図。
【図２】本発明の実施の形態１における時系列データ圧縮方法の処理構成図。
【図３】本発明の各実施の形態における時系列データ圧縮方法，時系列データ伸長方法の実行に使用するコンピュータを示す図。
【図４】本発明の実施の形態２における時系列データ圧縮装置の構成図。
【図５】本発明の実施の形態２における時系列データ圧縮装置の構成図。
【図６】本発明の実施の形態３における時系列データ圧縮方法の処理構成図。
【図７】本発明の実施の形態３における時系列データ圧縮方法の処理構成図。
【図８】本発明の実施の形態４における時系列データ圧縮装置の構成図。
【図９】本発明の実施の形態４における時系列データ圧縮装置の構成図。
【図１０】準最適節点候補の第１の決定方法の説明図。
【図１１】準最適節点候補の第２の決定方法の説明図。
【図１２】１次元時系列データの説明図。
【図１３】１次元時系列データの節点候補の説明図。
【図１４】１次元時系列データの節点候補による補間の説明図。
【図１５】準最適節点候補の選択方法の説明図。
【図１６】圧縮データ形式の説明図。
【図１７】本発明の実施の形態５における時系列データ伸長方法の処理構成図。
【図１８】本発明の実施の形態５における時系列データ伸長方法の処理構成図。
【図１９】本発明の実施の形態６における時系列データ伸長装置の構成図。
【図２０】本発明の実施の形態６における時系列データ伸長装置の構成図。
【図２１】本発明の実施の形態７における時系列データ伸長方法の処理構成図。
【図２２】本発明の実施の形態７における時系列データ伸長方法の処理構成図。
【図２３】本発明の実施の形態８における時系列データ伸長装置の構成図。
【図２４】本発明の実施の形態８における時系列データ伸長装置の構成図。
【図２５】本発明の実施の形態９における多次元時系列データ圧縮方法の処理構成図。
【図２６】本発明の実施の形態１０における多次元時系列データ圧縮装置の構成図。
【図２７】本発明の実施の形態１１における多次元時系列データ圧縮方法の処理構成図。
【図２８】本発明の実施の形態１２における多次元時系列データ圧縮方法の構成図。
【符号の説明】
【０１４４】
Ｐ１ａ，Ｐ１ｂ，Ｐ１ｃ，Ｐ１ｄ，Ｐ１ｅ，Ｐ１ｆ，Ｐ４ａ，Ｐ５ａ，Ｐ４ｂ，Ｐ５ｂ，Ｐ１，Ｐ２，Ｐ３，Ｐ４，Ｐ５，Ｐ６，Ｐ７，Ｐ８，Ｐ９，Ｐ１０，Ｐ１１，Ｐ１２，Ｐ１３，Ｐ１４，Ｐ２１，Ｐ２２，Ｐ２３，Ｐ２４，Ｐ２５，Ｐ２６，Ｐ２７，Ｐ２８，Ｐ２９，Ｐ３０，Ｐ３１，Ｐ３２，Ｐ３３，Ｐ３４，Ｐ３５，Ｐ４１，Ｐ４２，Ｐ４３，Ｐ４４，Ｐ４５，Ｐ４６，Ｐ４７，Ｐ４８，Ｐ４９，Ｐ５０，Ｐ５１，Ｐ５２，Ｐ５３，Ｐ５４，Ｐ５５，Ｐ５６，Ｐ５７，Ｐ５８，Ｐ５９，Ｐ６１，Ｐ６２，Ｐ６３，Ｐ６４，Ｐ６５，Ｐ６６，Ｐ６７，Ｐ６８，Ｐ６９，Ｐ７０，Ｐ７１，Ｐ７２，Ｐ７３，Ｐ７４，Ｐ７５，Ｐ７６，Ｐ７７，Ｐ７８，Ｐ７９，Ｐ１０１，Ｐ１０１ａ，Ｐ１０２，Ｐ１０３，Ｐ１０４，Ｐ１０５，Ｐ１０６，Ｐ１０７，Ｐ１０８，Ｐ２００，Ｐ２０１，Ｐ２０２，Ｐ２０３，Ｐ２０４  処理、
Ｓ１，Ｓ２，Ｓ３，Ｓ４，Ｓ５，Ｓ６，Ｓ７，Ｓ８，Ｓ９，Ｓ１１，Ｓ１２，Ｓ１３，Ｓ１４，Ｓ１５，Ｓ１６，Ｓ１７，Ｓ１８，Ｓ１９，Ｓ２０  段階
１  ＣＰＵ
２  データメモリ
３  メインメモリ
４  入出力装置
５  バス
６  外部記憶装置
４０ａ，５０ａ  入力手段
１０ａ  節点候補算出手段
１０ｂ  節点位置最適化手段
１０ｃ  判定手段
１０ｄ  節点数最適化手段
１０ｅ  判定手段
１０ｆ  判定手段
２０ａ  データ伸長手段
２０ｂ  データ形式判別手段
２０ｃ  ０データ伸長手段
２１  データ補間手段
２２  データ算出手段
２３  時刻算出手段
２４  データ形式判別手段
２５  ０データ算出手段
２６  時刻算出手段
４０ｂ，５０ｂ  出力手段
１１  インデックス付加手段
１２  初期節点数算出手段
１３  節点候補決定手段
１４  補間手段
１５  誤差算出手段
１６  第１目的関数算出手段
１７  準最適節点候補決定手段
１８  補間実行手段
１９  誤差算出手段
２０  第２目的関数算出手段
２１  閾値判定手段
２２  節点数変更手段
２３  近似精度内判定手段
【図１】
2006203937.tif 000003
【図２】
2006203937.tif 000004
【図３】
2006203937.tif 000005
【図４】
2006203937.tif 000006
【図５】
2006203937.tif 000007
【図６】
2006203937.tif 000008
【図７】
2006203937.tif 000009
【図８】
2006203937.tif 000010
【図９】
2006203937.tif 000011
【図１０】
2006203937.tif 000012
【図１１】
2006203937.tif 000013
【図１２】
2006203937.tif 000014
【図１３】
2006203937.tif 000015
【図１４】
2006203937.tif 000016
【図１５】
2006203937.tif 000017
【図１６】
2006203937.tif 000018
【図１７】
2006203937.tif 000019
【図１８】
2006203937.tif 000020
【図１９】
2006203937.tif 000021
【図２０】
2006203937.tif 000022
【図２１】
2006203937.tif 000023
【図２２】
2006203937.tif 000024
【図２３】
2006203937.tif 000025
【図２４】
2006203937.tif 000026
【図２５】
2006203937.tif 000027
【図２６】
2006203937.tif 000028
【図２７】
2006203937.tif 000029
【図２８】
2006203937.tif 000030