(57)【要約】【課題】  ２次元画像等の多次元空間における分布データ等を、高効率に符号化することができる。また２次元のデータを１次元の基底データに分解することが可能になるため、コンボリューション演算器において問題となっていた、２次元並列化による配線の問題を解決する。【解決手段】  符号化しようとする２次元画像データｆ（ｘ、ｙ）を入力（Ｓ１０）すると共に、その２次元画像の１次元適応化基底Ｘ（ｘ）、Ｙ（ｙ）を確保し、初期値を設定する（Ｓ１１）。そして、一次元適応化基底に基づき復元画像を生成し（Ｓ１２）、復元画像と入力画像との誤差Ｅを演算し（Ｓ１３）、その誤差Ｅに基づいて１次元適応化基底Ｘ（ｘ）、Ｙ（ｙ）の修正量ΔＸ（ｘ）、ΔＹ（ｙ）を求める（Ｓ１４）。そして、誤差Ｅが下限に達した（Ｓ１６）、或いは、収束した（Ｓ１７）と判断するまで、復元画像の生成と誤差を求めることを行う。【選択図】  図１
2005244927.tif 000002
【特許請求の範囲】
【請求項１】
ｎ個のデータで構成される被符号化データを、ｍ個のデータで構成される適応化基底に符号化する方法であって、
前記適応化基底を初期化するステップと、
所定の変換により前記適応化基底から、ｎ個のデータで構成される復元データを生成する復元ステップと、
所定の誤差評価関数により前記被符号化データと前記復元データとの誤差を算出する誤差算出ステップと、
前記誤差に基づき前記適応化基底を修正する修正ステップと
を有することを特徴とするデータ符号化方法。
【請求項２】
ｎ個のデータで構成される被符号化データを、少なくとも２つの、ｐ個のデータで構成される適応化基底に符号化する方法であって、
前記適応化基底を初期化するステップと、
所定の変換により前記少なくとも２つの適応化基底から、ｎ個のデータで構成される復元データを生成する復元ステップと、
所定の誤差評価関数により、前記被符号化データと前記復元データとの誤差を算出する誤差算出ステップと、
前記誤差に基づき前記少なくとも２つの適応化基底を修正する修正ステップと
を有することを特徴とするデータ符号化方法。
【請求項３】
ｎ個のデータで構成される被符号化データを、少なくとも２つの、ｐ個のデータで構成される適応化基底に符号化する方法であって、
前記適応化基底を初期化するステップと、
所定の変換により１つの前記適応化基底から、ｎ個のデータからなる要素復元データを生成する復元ステップと、
所定の誤差評価関数により、差分被符号化データと前記要素復元データとの誤差を算出する誤差算出ステップと、
前記誤差に基づき前記１つの適応化基底を修正する修正ステップと
を有することを特徴とするデータ符号化方法。
【請求項４】
被符号化データであるｋ次元空間分布データｆ(ｘ1、ｘ2、…、ｘk)を、請求項３に記載の前記被符号化データを用いて、少なくとも１組の、ｋ個の１次元適応化基底組Ｘ1(ｘ1)、Ｘ2(ｘ2)、…Ｘk(ｘk)を生成し、
2005244927.tif 000039
と展開表現することを特徴とするデータ符号化方法。
【請求項５】
被符号化データであるｋ次元空間分布データｆ(ｘ1、ｘ2、…、ｘk)を、ｋ個の１次元適応化基底組Ｘ1(ｘ1)、Ｘ2(ｘ2)…、Ｘk(ｘk) に符号化する方法であって、
前記１次元適応化基底組を初期化するステップと、
前記１次元適応化基底組から、復元データを次式で生成する復元ステップと、
2005244927.tif 000040
所定の誤差評価関数により前記被符号化データと前記復元データとの誤差を算出する誤差算出ステップと、
前記誤差に基づき前記１次元適応化基底組を修正する修正ステップと
を有することを特徴とするデータ符号化方法。
【請求項６】
被符号化データであるｋ次元空間分布データｆ(ｘ1、ｘ2、…、ｘk)を、少なくとも２組の、ｋ個の１次元適応化基底組 に符号化する方法であって、
前記１次元適応化基底組を初期化するステップと、
前記１次元適応化基底組から、復元データを次式で復元する復元ステップと、
2005244927.tif 000041
所定の誤差評価関数により前記被符号化データと前記復元データとの誤差を算出する誤差算出ステップと、
前記誤差に基づき前記１次元適応化基底組を修正する修正ステップと
を有することを特徴とするデータ符号化方法。
【請求項７】
被符号化データであるｋ次元空間分布データ を、少なくとも２組の、ｋ個の１次元適応化基底組 に符号化する方法であって、
前記１次元適応化基底組を初期化するステップと、
１組の前記１次元適応化基底組から、要素復元データを次式で生成する復元ステップと、
2005244927.tif 000042
所定の誤差評価関数により、差分被符号化データと前記要素復元データとの誤差を算出する誤差算出ステップと、
前記誤差に基づき前記１組の１次元適応化基底組を修正する修正ステップと
を有することを特徴とするデータ符号化方法。
【請求項８】
前記復元ステップは、前記少なくとも２つの適応化基底の各々について、所定の変換でｎ個のデータで構成される要素復元データに変換し、前記変換された要素復元データの線形和をとり、前記復元データとすることを特徴とする請求項２に記載のデータ符号化方法。
【請求項９】
前記算出した誤差の収束を判定するステップを更に有し、前記誤差が収束したと判定されるまで、前記修正ステップを繰り返し行うことを特徴とする請求項１、２、５、または６のいずれか１つに記載のデータ符号化方法。
【請求項１０】
前記算出した誤差の収束を判定するステップを更に有し、
前記誤差が収束したと判定されるまで、前記修正ステップを繰り返し行い、前記誤差が収束したと判定された場合に、次の新たな適応化基底、若しくは新たな１次元適応化基底組に対し、前記修正ステップを行う
ことを特徴とする請求項３、または請求項７のいずれか１項に記載のデータ符号化方法。
【請求項１１】
前記差分被符号化データは、前記被符号化データから、前記誤差の収束を判定するステップにより、前記誤差が収束したと判定された全ての前記適応化基底、若しくは前記１次元適応化基底組から復元される前記要素復元データを差し引いたものであることを特徴とする請求項１０に記載のデータ符号化方法。
【請求項１２】
前記修正ステップを、前記算出した誤差が予め定めた目標誤差以下になるまで繰り返し行うことを特徴とする請求項１乃至請求項３、請求項５乃至請求項７のいずれか１項に記載の記載のデータ符号化方法。
【請求項１３】
前記誤差評価関数は、前記符号化データ、若しくは前記差分被符号化データと、前記復元データ、若しくは前記要素復元データの各要素との２乗誤差の総和であることを特徴とする請求項１乃至請求項３、または請求項５乃至請求項７のいずれか１項に記載のデータ符号化方法。
【請求項１４】
前記修正ステップにおいて、前記算出した誤差が減少するように、前記適応化基底、若しくは前記１次元適応化基底組の修正を行うことを特徴とする請求項１乃至請求項３、または請求項５乃至請求項７のいずれか１項に記載のデータ符号化方法。
【請求項１５】
前記修正ステップにおいて、前記適応化基底、若しくは前記１次元適応化基底組の修正量は、前記誤差評価関数の、前記適応化基底の内の修正する要素、若しくは前記１次元適応化基底組の内の修正する要素での偏微分係数に、所定の係数を乗じたものであることを特徴とする請求項１乃至請求項３、または請求項５乃至請求項７のいずれか１項に記載のデータ符号化方法。
【請求項１６】
前記所定の係数は、負の定数であることを特徴とする請求項１５に記載のデータ符号化方法。
【請求項１７】
前記所定の係数は、負の値であり、徐々に０に近づけることを特徴とする請求項１５に記載のデータ符号化方法。
【請求項１８】
前記被符号化データを、所定範囲で分割し、前記所定範囲ごとに符号化を行うことを特徴とする請求項１乃至請求項３、または請求項５乃至請求項７のいずれか１項に記載のデータ符号化方法。
【請求項１９】
前記被符号化データを、空間的に所定範囲で分割し、前記所定範囲ごとに符号化を行うことを特徴とする請求項５乃至請求項７のいずれか１項に記載のデータ符号化方法。
【請求項２０】
前記被符号化データを、周波数空間に変換し符号化を行うことを特徴とする請求項５乃至請求項７のいずれか１項記載のデータ符号化方法。
【請求項２１】
前記被符号化データを、周波数空間に変換し、周波数空間において所定範囲に分割し、前記所定範囲ごとに符号化を行うことを特徴とする請求項５乃至請求項７のいずれか１項に記載のデータ符号化方法。
【請求項２２】
前記被符号化データを、空間的に所定範囲で分割し、前記所定範囲ごとに周波数空間に変換し符号化を行うことを特徴とする請求項５乃至請求項７のいずれか１項に記載のデータ符号化方法。
【請求項２３】
前記被符号化データを、空間的に所定範囲で分割し、前記所定範囲ごとに周波数空間に変換し、前記周波数空間に変換された所定範囲ごとの所定周波数成分を周波数データとして合成し、前記周波数データの符号化を行うことを特徴とする請求項５乃至請求項７のいずれか１項に記載のデータ符号化方法。
【請求項２４】
請求項１、５、２３のいずれか１項に記載のデータ符号化方法により生成される前記適応化基底、若しくは前記１次元適応化基底組から、前記所定の変換により復元データを復元することで、復号化することを特徴とするデータ復号化方法。
【請求項２５】
請求項２、３、６、７、２３のいずれか１項に記載のデータ符号化方法により生成される前記適応化基底、若しくは前記１次元適応化基底組から、前記所定の変換により要素復元データを復元し、前記復元した要素復元データの線形和をとることで、復号化することを特徴とするデータ復号化方法。
【請求項２６】
ｋ次元荷重分布データｗ（ｘ1、ｘ2、…、ｘk）と、ｋ次元分布データである被積和演算データＡ（ｘ1、ｘ2、…、ｘk）とを次式で積和演算を行う積和演算方法であって、
2005244927.tif 000043
前記ｋ次元荷重分布データを、請求項５乃至７のいずれか１項に記載のデータ符号化方法により、少なくとも１組の、ｋ個の１次元適応化基底組Ｘ1l（ｘ1）、Ｘ2l（ｘ2）、…、Ｘkl（ｘk）に符号化し、
前記被積和演算データと、前記１次元適応化基底組を用いて、前記積和演算を次式で求める
2005244927.tif 000044
ことを特徴とする積和演算方法。
【請求項２７】
ｎ個のデータで構成される被符号化データを、ｍ個のデータで構成される適応化基底に符号化する装置であって、
前記適応化基底を初期化する手段と、
所定の変換により前記適応化基底から、ｎ個のデータからなる復元データを生成する復元手段と、
所定の誤差評価関数により前記被符号化データと前記復元データとの誤差を算出する誤差算出手段と、
前記誤差に基づき前記適応化基底を修正する修正手段を有することを特徴とするデータ符号化装置。
【請求項２８】
ｋ次元の被符号化データを、ｋ個の一次元適応化基底の組に符号化するデータ符号化方法であって、
被符号化データを所定のメモリに記憶する記憶ステップと、
前記ｋ個の一次元適応化基底をメモリに確保し、初期化する初期化ステップと、
所定の変換により、前記メモリ内の一次元適応化基底から、ｋ次元の復元データを生成する復元ステップと、
所定の誤差評価関数により前記被符号化データと前記復元データとの誤差を算出する誤差算出ステップと、
該誤差演算ステップで得られた誤差に基づき、前記適応化基底を修正するか否かを判定し、前記適応化基底を修正すると判定した場合には前記メモリの適応化基底を修正して、前記復元ステップ、誤差演算ステップを繰り返し、前記適応化基底を修正しないと判定した場合には、最後の適応化基底を符号化結果として出力する判定ステップと
を備えることを特徴とするデータ符号化方法。
【請求項２９】
前記判定ステップは、誤差が収束したか否かに基づいて適応化基底を修正するか否かを判定し、
収束したと判定した場合であって、被符号化データと前記復元データとの誤差が所定値以上の差を有する場合には、ｋ個の一次元適応化基底の組を更に追加することを特徴とする請求項２８に記載のデータ符号化方法。
【請求項３０】
ｋ次元の被符号化データを、ｋ個の一次元適応化基底の組に符号化するデータ符号化方法であって、
被符号化データを所定のメモリに記憶する被符号化データ記憶手段と、
前記ｋ個の一次元適応化基底を記憶する基底記憶手段と、
該基底記憶手段に記憶されたｋ個の一次元適応化基底を初期化する初期化手段と、
所定の変換により、前記基底記憶手段に記憶されたｋ個の一次元適応化基底から、ｋ次元の復元データを生成する復元手段と、
所定の誤差評価関数により前記被符号化データと前記復元データとの誤差を算出する誤差算出手段と、
該誤差演算手段で得られた誤差に基づき、前記適応化基底を修正するか否かを判定し、前記適応化基底を修正すると判定した場合には前記基底記憶手段に記憶された適応化基底を修正して、前記復元手段、誤差演算手段を繰り返し、前記適応化基底を修正しないと判定した場合には、最後の適応化基底を符号化結果として出力する判定手段と、
を備えることを特徴とするデータ符号化装置。
【請求項３１】
ｋ次元荷重分布データｗ（ｘ1、ｘ2、…、ｘk）と、ｋ次元分布データである被積和演算データＡ（ｘ1、ｘ2、…、ｘk）とを次式で積和演算を行う積和演算装置であって、
2005244927.tif 000045
前記ｋ次元荷重分布データを、請求項５乃至７のいずれか１項に記載のデータ符号化方法により、少なくとも１組の、ｋ個の１次元適応化基底組Ｘ1l（ｘ1）、Ｘ2l（ｘ2）、…、Ｘkl（ｘk）に符号化し、
前記被積和演算データと、前記１次元適応化基底組を用いて、前記積和演算を次式で求める
2005244927.tif 000046
ことを特徴とする積和演算装置。
【請求項３２】
前記積和演算装置において、積和演算を行なう演算素子がアレイ状に構成されていることを特徴とする請求項３１記載の積和演算装置。
【請求項３３】
前記積和演算装置において、１次元適応化基底組がアレイ状に構成された演算素子全てに入力されることを特徴とする請求項３２に記載の積和演算装置。
【請求項３４】
前記積和演算装置において、アレイ状に構成された演算素子全てにおいて前記積和演算が実行されることを特徴とする請求項３３に記載の積和演算装置。
【請求項３５】
前記積和演算装置において、１次元適応化基底組が、アレイ状に構成された演算素子の列・行のそれぞれ一部に入力されることを特徴とする請求項３２に記載の積和演算装置。
【請求項３６】
前記積和演算装置において、アレイ状に構成された演算素子の一部において前記積和演算が実行されることを特徴とする請求項３５に記載の積和演算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データの符号化、特に２次元画像や３次元密度分布等の多次元空間における分布データの符号化技術に関するものである。
【背景技術】
【０００２】
２次元画像等の多次元分布データを符号化する技術としては、ＪＥＰＧ形式の圧縮技術のような、２次元画像データに対し離散コサイン変換を行い、変換されたデータに所定の量子化を行い、それをハフマン符号化等により符号化することで、データ量を圧縮する技術等が一般的である。
【０００３】
また、画像データを予測符号化し、予測符号化による予測誤差データをブロック分割し、ブロック毎に予測誤差の大きいブロックか小さいブロックかを判別しする手法もある（特許文献１）。この文献では、予測誤差の大きいブロックにはベクトル量子化を適用し、ベクトル量子化により検索されたコードブックのベクトル値と予測誤差との差分値を計算し、この差分値と予測誤差の小さいブロックにおける予測誤差をエントロピー符号化し、エントロピー符号とブロック大小判別フラッグとベクトル量子化によるインデックスとを用いて符号化データを作成するものである。このように、省スペースでのデータ保持、高速通信等の観点から、高効率なデータ符号化技術が望まれている。
【０００４】
また、まったく別の観点ではあるが、画像処理等で多用される所定の２次元荷重分布データによる、２次元画像に対する離散的コンボリューション演算を行う演算器において、積和演算素子を大規模並列化し、高速な演算を可能にすることが期待されている。しかし配線の問題等から、積和演算を２次元的に並列化して実行することは困難であった。従って、コンボリューションの２次元荷重分布データを１次元の基底組に分解する方法が望まれている。
【特許文献１】特開平１１−３３１８５２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明は、このような点に鑑みなされたものであり、高効率なデータの符号化、特に２次元画像等の多次元空間における分布データ等を、幾つかの一次元の基底に分解し、符号化する技術を提供とするものである。
【課題を解決するための手段】
【０００６】
この課題を解決するため、例えば本発明の符号化方法は以下の工程を備える。すなわち、
ｎ個のデータで構成される被符号化データを、ｍ個のデータで構成される適応化基底に符号化する方法であって、
前記適応化基底を初期化するステップと、
所定の変換により前記適応化基底から、ｎ個のデータで構成される復元データを生成する復元ステップと、
所定の誤差評価関数により前記被符号化データと前記復元データとの誤差を算出する誤差算出ステップと、
前記誤差に基づき前記適応化基底を修正する修正ステップとを有する。
【発明の効果】
【０００７】
本発明によれば、高効率なデータの符号化、特に２次元画像等の多次元空間における分布データ等を、高効率に符号化することができる。また２次元のデータを１次元の基底データに分解することが可能になるため、コンボリューション演算器において問題となっていた、２次元並列化による配線の問題を解決することができる。
【発明を実施するための最良の形態】
【０００８】
以下、添付図面に従って本発明に係る実施形態を詳細に説明する。
【０００９】
＜第１の実施形態＞
第１の実施形態として、有限範囲で定義される２次元濃淡画像を、２つの１次元適応化基底に符号化する方法を説明する。
【００１０】
図８は本第１の実施形態における装置構成を示すブロック図である。
【００１１】
図中、１は装置全体の制御を司るＣＰＵであり、２はＣＰＵ１の処理手順（プログラム）を記憶しているＲＯＭである。３はＣＰＵ１のワークエリアとして使用されるＲＡＭであり、ここには符号化対象の画像データを格納する画像データエリア３ａ、並びに、基底データを格納するエリア３ｂが確保される。なお、エリア３ａ、３ｂのサイズは入力する画像データサイズに応じて決定されることになる。４は符号化対象の濃淡画像データを入力する画像入力部である。画像入力部としては、イメージスキャナ、撮像素子等であるが、画像データが記憶媒体に記憶されている場合にはその記憶媒体をアクセスする装置であってもよいし、ネットワークを介して画像を受信する場合にはネットワークインタフェースであっても構わない。５は符号化後のデータを格納する外部記憶装置（ハードディスク等）であるが、符号化データをネットワーク上に出力する場合にはネットワークインタフェースでも構わない。
【００１２】
実施形態では説明を簡単なものとするため、符号化対象の画像データは１画素８ビットの多値（濃淡）モノクロ画像として説明する。また、画像は矩形であり、水平方向の画素数がｘmax、垂直方向の画素数がｙmaxであるものとする。画像入力部４がイメージスキャナであれば、読取り解像度、原稿のサイズにより、ｘmax、ｙmaxは一義的に決まるものである。
【００１３】
入力した画像は画像データエリア３ａに格納されるが、座標（ｘ、ｙ）（但し、０≦ｘ＜ｘmax、０≦ｙ＜ｙmax）の画素値を便宜的にｆ（ｘ，ｙ）と表現する。また、入力する画像データのサイズが決定されるので、２つの一次元適応化基底Ｘ（ｘ）、Ｙ（ｙ）を基底エリア３ｂに確保する。ｘ、ｙの取り得る範囲は入力画像のそれと同じである。なお、画素値ｆ（ｘ，ｙ）は８ビットの整数値であるが、一次元適応化基底Ｘ（ｘ）、Ｙ（ｙ）は小数点の値を記憶保持できるように多バイト形式でＲＡＭ３ｂ内の基底エリア３ｂに確保することになる。
【００１４】
以下、本第１の実施形態におけるＣＰＵ１の符号化処理手順を図１のフローチャート（対応するプログラムはＲＯＭ２に格納されている）に従って説明する。
【００１５】
まず、画像入力（ステップＳ１０）において、符号化される２次元濃淡画像である画像ｆ（ｘ，ｙ）を入力し、画像エリア３ａに格納する。次に、基底設定を行う（ステップＳ１１）。ここでは、２つの１次元適応化基底Ｘ（ｘ）、Ｙ（ｙ）について初期値を設定する。但し、この一次元適応化基底Ｘ（ｘ）、Ｙ（ｙ）は、０≦ｘ＜ｘmax、０≦ｙ＜ｙmaxという有限範囲全域において、全てが０ではないような値を設定する。初期段階では乱数関数を用いて設定することになる。なお、ここでは上記のように各定義域を有限としたが、特にこれに限るものではない。すなわち、無限の定義域において定義されたｆ（ｘ，ｙ）、Ｘ（ｘ）、Ｙ（ｙ） においても、後述の誤差Ｅ、及び修正量ΔＸ（ｘ）、ΔＹ（ｙ）が発散しない限り、本手法は適用可能である（但し、メモリ容量は有限であるので、自ずとその限界はある）。
【００１６】
基底復元（ステップＳ１２）では、復元画像ｆ~（ｘ，ｙ）を次のように生成する。
【数１】
2005244927.tif 000003
【００１７】
次いで、ステップＳ１３の誤差演算処理にて、入力画像ｆ（ｘ，ｙ）と復元画像ｆ~（ｘ，ｙ）との誤差Ｅを、次の誤差評価関数を用いて算出する。
【数２】
2005244927.tif 000004
ここで、∫ｆ（ｘ）ｄｘは、ｘの定義領域全範囲におけるｆ（ｘ）の積分を示す。ｙ成分についても同様に積分することになるので、誤差Ｅは入力画像全域における累積誤差となる。また、この誤差Ｅは、後述する誤差収束判定（分岐判定であるステップＳ１６）において用いるため、履歴としてＲＡＭ３に順次記録しておく。
【００１８】
続いて、この誤差Ｅに基づいて、修正量の算出を行う（ステップＳ１４）。ここでは、各１次元適応化基底の修正量ΔＸ（ｘ）、ΔＹ（ｙ）を以下のように算出する。
【数３】
2005244927.tif 000005
ここで、ηx、ηyは修正パラメータであり正の定数である（このηx、ηyの設定については後述する）。
【００１９】
この修正量を得る関数は、誤差Ｅを求める式の偏微分式であることに注意されたい。すなわち、誤差Ｅは常に０以上の値を有するわけであり、究極的には、本実施形態の目標は誤差Ｅが極小値となる１次元適応化基底を求める点にある。現時点での１次元適応化基底による傾きがマイナスであるということは、極小値となる一次元基底は現時点より正の方向に位置することになり、逆に、１次元適応化基底による傾きがプラスであるということは、極小値となる一次元基底は現時点より負の方向に存在することを意味する。それ故、傾きに対してマイナスを乗算することで、傾きに応じた修正量を算出することになる。
【００２０】
次に、処理はステップＳ１５に進み、基底修正処理を行う。これは、ステップＳ１４にて得られた修正量ΔＸ（ｘ）、ΔＹ（ｙ）を修正前の１次元適応化基底をＸ（ｘ）、Ｙ（ｙ）に加算することで、修正後の１次元適応化基底をＸ’（ｘ）、Ｙ’（ｙ）を求めるものである。式で示せば次の通りである。
Ｘ’（ｘ）＝Ｘ（ｘ）＋ΔＸ（ｘ）
Ｙ’（ｙ）＝Ｙ（ｙ）＋ΔＹ（ｙ）
この１次元適応化基底の修正の際には、入力画像ｆ（ｘ、ｙ）が、定義された全てのｘ、ｙの範囲において常に０でない限り、各１次元適応化基底が常に０ではないという上記条件を満たさなければならない。ただし、そのような条件になってしまった場合は、１次元適応化基底の少なくとも一部にランダムに微小の揺らぎを与えるようにすればよい。
【００２１】
上記のステップＳ１２（基底復元処理）からステップＳ１５（基底修正処理）までの１次元適応化基底の修正を、修正された１次元適応化基底に対して、誤差下限判定（ステップＳ１６）、及び誤差収束判定（ステップＳ１７）において終了判定が出されるまで繰り返し実行する。
【００２２】
ここで、ステップＳ１６の誤差下限判定は、誤差算出（ステップＳ１３）で算出した直前の修正の誤差Ｅが、予め定めておいた所定の値以下であった場合に、その時の１次元適応化基底が許容範囲の誤差Ｅを与える１次元適応化基底であるか否かを判定するものである。そして、終了判定の場合には、その時点での１次元適応化基底を符号化データとして記録して処理を終了する。
【００２３】
また、ステップＳ１７の誤差収束判定は、誤差算出（ステップＳ１３）で算出し、記録した誤差Ｅの履歴から、誤差の収束判定を行い、誤差が収束したと判定された場合は、その時の１次元適応化基底が誤差 の極小値を与える１次元適応化基底であるとして終了判定する。収束したと判断した場合の１次元適応化基底は符号化データとして記録して処理を終了する。誤差の収束の判定としては、１回の修正ごとの、誤差Ｅの変化がほとんどない状況（誤差の差分が所定閾値以下の場合）が続いた場合に、誤差が収束したと判定する。
【００２４】
上記説明した処理により、２次元濃淡画像ｆ（ｘ、ｙ）を、２つの１次適応化元基底 Ｘ（ｘ）、Ｙ（ｙ）に符号化することができる。換言すれば、画像データｆ（ｘ、ｙ）は画素数はｘmax×ｙmax画素存在していたのに対し、符号化データはｘmax＋ｙmax個のデータにまで圧縮されたことになる（ただし、入力画像の１画素は８ビットであるのに対し、１次適応化元基底の１要素は数バイト必要になる）。また、この符号化された２つの１次元適応化基底Ｘ（ｘ）、Ｙ（ｙ）の復号化画像ｆdecode（ｘ，ｙ）は、次のようにして復号できる。
ｆdecode（ｘ，ｙ）＝Ｘ（ｘ）×Ｙ（ｙ）
上記符号化処理において、基底設定（ステップＳ１１）において設定する初期の１次元適応化基底Ｘ（ｘ）、Ｙ（ｙ）としては、定義されたｘ、ｙの範囲においてＸ（ｘ）、Ｙ（ｙ）は入力画像 のレンジ程度の値であることが好ましい。好適には、０ではないものの、ほぼ０に近い値となるように設定すると、初期値依存性が少なくなり、適切な１次元適応化基底を得られる可能性が高くなる。
【００２５】
また、修正パラメータηx、ηyは、入力画像ｆ（ｘ、ｙ）のレンジや定義されたｘ、ｙの範囲の幅に応じて定めるのが好ましい。具体的にはηxはｙの範囲の２乗とｆ（ｘ、ｙ）のレンジに反比例し、ηyはｘの範囲の２乗とｆ（ｘ、ｙ）のレンジに反比例させるようにするのが好適である。ここでは修正パラメータをηx、ηyと各１次元適応化基底により異ならせているが、定義されたｘ、ｙの範囲の幅が同程度であれば、同一の値を用いても構わない。この修正パラメータを大きい値に設定すると、少ない回数の１次元適応化基底の修正で誤差下限判定（ステップＳ１６）、若しくは誤差収束判定（ステップＳ１７）での終了判定が出る可能性が高くなるが、誤差Ｅが極小値周辺で大きく振動し、適切な１次元適応化基底を得られない可能性が高くなる。また、小さい値に設定すると、誤差Ｅが極小値付近に落ち着いて、適切な１次元適応化基底を得られる可能性が高くなるが、誤差下限判定（ステップＳ１６）、若しくは誤差収束判定（ステップＳ１７）での終了判定までに、多くの回数の、１次元適応化基底の修正を必要とする可能性が高くなる。上記の点を鑑み、修正パラメータは、誤差Ｅが極小値周辺で大きく振動しない程度に小さく、極端に多くの回数の、１次元適応化基底の修正を必要としない程度の大きな値にしておくことが好適である。また修正パラメータを修正回数に応じて徐々に小さくしていく手法を適用しても良い。
【００２６】
また、誤差下限判定（ステップＳ１６）で用いる、予め定めておく誤差Ｅの許容範囲も、入力画像ｆ（ｘ、ｙ）のレンジや、定義されたｘ、ｙの範囲の幅に応じて定めるのが好ましく、これを大きい値にすると、少ない回数の１次元適応化基底の修正で誤差下限判定（ステップＳ１６）での終了判定が出る可能性が高くなるが、誤差Ｅが高い１次元適応化基底を得る可能性が高くなる。また、小さい値にすると、誤差 が小さい適切な１次元適応化基底を得られる可能性が高くなる。しかし、誤差下限判定（ステップＳ１６）での終了判定までに、多くの回数の、１次元適応化基底の修正を必要とする、若しくは誤差下限判定（ステップＳ１６）での終了判定が出ない可能性が高くなる。
【００２７】
さらに、上記説明した修正量算出（ステップＳ１４）で算出する修正量ΔＸ（ｘ）、ΔＹ（ｙ）を、予め保持しておいた、この修正の前回の修正量ΔＸ＾（ｘ）、ΔＹ＾（ｙ）を用いて、以下のようにすることで、より誤差 の小さい好適な１次元適応化基底を得られる、若しくは少ない修正回数で所望の１次元適応化基底を得られる可能性が高くなる。
【数４】
2005244927.tif 000006
ここでαx、αyは、慣性項係数であり、１未満の正の定数である。ここでは、慣性項係数を各１次元適応化基底により異ならせているが、同一の値を使っても構わない。ここで用いる慣性項は、大きい値に設定する程、上記利点が発生する可能性が高くなるが、上記利点と逆の効果も現れ、１次元適応化基底の修正が不安定になる可能性が高くなるため、あまり大きな値に設定することは好ましくない。また小さい値に設定すると、上記利点の逆の効果が現れる可能性は低くなるが、上記利点を得られる可能性は少なくなる。そのため、この慣性項係数は、１次元適応化基底の修正が不安定にならないような範囲でできる限り大きな値に設定することが好ましい。
【００２８】
以上、第１の実施形態では、有限範囲で定義される２次元濃淡画像ｆ（ｘ、ｙ）を、２つの１次元適応化基底Ｘ（ｘ）、Ｙ（ｙ）に符号化する方法の例として説明したが、符号化対象は２次元に限らない。例えば３次元の空間における密度分布等にも適用可能であるし、それを越える多次元に対しても同様に適用可能である。
【００２９】
＜第２の実施形態＞
上記第１の実施形態では、符号化される２次元画像が比較的単純なものであれば、座標系を適切に選択することにより、誤差の少ない符号化が可能である。つまり、例えば２次元画像が、図５に示すような単純な矩形形状のものであれば、その矩形に直交する直交座標系を用いて符号化すれば、比較的誤差の少ない符号化が可能になる。このようにデータに応じて極座標系等や、３次元データであれば円柱座標系等を適切に選択してやることで、誤差Ｅが少ない符号化が可能である。
【００３０】
しかし、２次元画像が例えば自然画像であるような場合は、上記第１の実施形態で示した方法では、符号化されたデータを用いて復号したデータ（画像データ）と、元のデータの誤差が大きくなってしまう。そこで、本第２の実施形態では、上記第１の実施形態の変形例として、有限範囲で定義される離散的な２次元濃淡画像ｆ（ｘ、ｙ）を、複数の離散的な１次元適応化基底組Ｘｌ（ｘ）、Ｙｌ（ｙ）（ｘ、ｙは整数）に符号化する方法を説明する。
【００３１】
概要を簡単に説明すると、１つの一次元適応化基底を用意し、第１の実施形態と同様の処理を行って誤差Ｅの下限判定、並びに、収束判定を行う。その後、誤差Ｅが十分に小さいとは判断されない場合には、新たな一次元適応化基底組を追加し残された被符号化データと復元データの誤差を小さくするように、再度、同じ処理を繰り返すものである。
【００３２】
装置構成は、第１の実施形態と同じとし、以下、本第２の実施形態に係る処理を図２のフローチャートに従って説明する。
【００３３】
まず、画像入力（ステップＳ２０）において、符号化される離散的な２次元濃淡画像である入力画像ｆ（ｘ、ｙ）を入力する。ここでも第１の実施形態と同様に、ｘ、ｙは所定の定義域をもち、０≦ｘ＜ｘmax、０≦ｙ＜ｙmax とする。また、本第２の実施形態においては、入力画像は離散的であり、ｘ、ｙは整数である。
【００３４】
ここでは、具体的な説明のため、例えば図１０に示す８×８の輝度値データに対して当該処理を行った場合について説明していく。以下、この具体的な数値を用いた例を数値適用例と呼ぶ。図１０に示した数値は、８ｂｉｔ精度の非負整数値であるが、差分が定義できる値であればどのようなデータでも構わない。画像入力（ステップＳ２０）の次は、基底設定処理を行う（ステップＳ２１）。ここでは、離散的な１次元適応化基底組Ｘl（ｘ）、Ｙl（ｙ）（ｘ、ｙは整数）を１つ選択して初期の１次元適応化基底組として設定する。添字「ｌ」は基底番号であり、特に限定はしないが、本第２の実施形態では０から順に、予め定めた基底組数まで順に選択していくことにする。数値適用例で処理を行う画像は、８×８であるので、各１次元適応化基底は、８の要素からなる数値列となる。第１の実施形態で説明したように、ここでの各数値の初期設定は、ほぼ０と見なせる乱数を設定するのが好適であるが、全ての要素が０ではないという条件を満たせばよいので、ここでは簡単のため、全ての添字ｌの、初期の１次元適応化基底組において、図１１に示すような１次元適応化基底組を用いる。図中の式の、括弧内のｔの値は、１次元適応化基底の修正回数を示している。つまり、ｔ＝ｎならば、ｎ回の修正後の１次元適応化基底を意味する。
【００３５】
次に基底復元処理を行う（ステップＳ２２）。ここでは、選択した基底番号ｌの１次元適応化基底組から、要素復元画像ｆl~（ｘ、ｙ）を次のように算出する。
【数５】
2005244927.tif 000007
【００３６】
基底設定処理（ステップＳ２１）直後の、１番最初の基底組を用いた時の、要素復元画像ｆ0~（ｘ、ｙ）に対応する８×８の数値列は図１２に示すようになる。次に、誤差算出（ステップＳ２３）により、誤差Ｅを以下のように算出する。
【数６】
2005244927.tif 000008
上式において、ｆl（ｘ）は差分被符号化画像であり、以下のように表される。
【数７】
2005244927.tif 000009
ここで、
【数８】
2005244927.tif 000010
は、ｘの定義域内全範囲における、ｘが整数の時のｆ（ｘ）の総和を意味する。
【００３７】
また、
【数９】
2005244927.tif 000011
は、ｎ≦ｋ≦ｍのｆk（ｘ）の線形和を意味し、ｍ＜ｎの場合は０となる。数値適用例では、差分被符号化画像ｆ0（ｘ）は、入力画像となるので、誤差Ｅは４８２９１３である。
【００３８】
上記の差分被符号化画像ｆl（ｘ，ｙ）は、入力画像ｆ（ｘ、ｙ）から、基底番号０から基底番号ｌ−１までの、ｌ組の１次元適応化基底組により復元される各要素復元画像を差し引いたものを意味する。つまり、本第２の実施形態では基底番号０から順に１次元適応化基底組を選択していき、各１次元適応化基底組を修正していくので、差分被符号化画像ｆl（ｘ、ｙ）は、入力画像ｆ（ｘ、ｙ）から、既に修正完了した１次元適応化基底組により復元される各要素復元画像を差し引いたものとなる。
【００３９】
次いで、修正量算出（ステップＳ２４）において、基底設定（ステップＳ２１）において選択された１次元適応化基底組Ｘl（ｘ）、及びＹl（ｙ）に対する修正量ΔＸl（ｘ）、及びΔＹl（ｙ）を以下のように算出する。
【数１０−Ａ】
2005244927.tif 000012
若しくは、第１の実施形態で述べた、慣性項計数αx、αyを前回の修正量ΔＸ＾（ｘ）、ΔＹ＾（ｙ）に乗じたものを加算した、以下の式を用いて算出しても構わない。
【数１０−Ｂ】
2005244927.tif 000013
上式においてηx、ηyは修正パラメータであり、第１の実施形態で説明したものと同様のものである。
【００４０】
数値適用例では、「数１０−Ｂ」の式を用いて修正量を算出している。図１１に示した１次元適応化基底組に対する修正量、即ち基底設定処理（ステップＳ２１）直後の場合は、前回の修正量ΔＸ＾（ｘ）、ΔＹ＾（ｙ）は、全ての要素が０であるので、慣性項係数の部分は０となる。このときの修正量を図１３に示す。この図中の式の、括弧内のｔの値は、何回目の修正量であるかを示している。つまり、ｔ＝ｎならば、ｎ回目の１次元適応化基底の修正量となる。ちなみに、ここで用いた修正パラメータは、ηx＝ηy＝０．０００７８、慣性項係数は、αx＝αy＝０．４としている。
【００４１】
上記算出した修正量ΔＸl（ｘ）、及びΔＹl（ｙ）を用い、基底修正（ステップＳ２５）において、基底設定（ステップＳ２１）で選択された１次元適応化基底組Ｘl（ｘ）、Ｙl（ｙ）に対して、修正後の各１次元適応化基底組をＸ'l（ｘ）、Ｙ'l（ｙ） 、修正前の１次元適応化基底組をＸl（ｘ）、Ｙl（ｙ）とした時に、各１次元適応化基底組を次のように修正する。
【数１１】
2005244927.tif 000014
【００４２】
これにより、図１１に示した１次元適応化基底組は、図１４のようになる。この１回目の修正では、初期の１次元適応化基底組の要素が、１つを除いて全て０であったため、１部の要素しか修正されていない。また、０以外である数値も、０．１と、比較的小さいため、最初の修正量は極微量なものとなっている。勿論、好適には全ての数値に乱数を入れておくため、１回目の修正から、全ての要素が修正されることになる。しかし、初期の値は、ほぼ０と見なせる値にしておくことが望ましいので、やはり修正量は微量となる。この修正された１次元適応化基底組を用いて、「数６」で示される式に従い誤差Ｅを算出すると、４８２９１１．４８いう値が得られる。このように、１回目の修正では、誤差Ｅはわずかに減少する程度である。このような修正を、第１の実施形態と同様に、誤差下限判定（ステップＳ２６）において終了判定、若しくは誤差収束判定（ステップＳ２７）において収束判定がなされるまで繰り返し行うことで、基底設定（ステップＳ２１）で選択した基底番号 の１次元適応化基底組が修正される。例えば、図１３に示した１回目の修正量により修正した後の、２回目の修正量は、図１５に示すようになり、この修正により、誤差Ｅは４８２９０６．０５となる。２回目の修正では、まだ修正量が微量であるが、１回目とは異なり、全要素が修正されることになる。この数値適用例の場合、７〜１０回目の修正量が比較的大きくなり、例えば９回目の修正量は、図１６に示すようになる。９回目の修正の、直前の誤差Ｅは、２８６６９６．０２であり、９回目の修正の直後は、誤差Ｅは、１６３４９．２７と大きく減少する。この修正回数と誤差Ｅの変化の関係を図１７に示す。図１７に示すように、誤差Ｅは修正を行うごとに、９回目の修正まで加速的に減少し、その後一旦上昇する。そしてその後は振動しながら徐々に収束していく。９回目の修正後の、大きな上昇は、慣性項係数の影響によるところが大きく、慣性項係数を０とすると、このような大きな上昇は起こりにくいが、収束までの修正回数や、局所的な極小値へのトラップを回避するために有効である。
【００４３】
誤差下限判定（ステップＳ２６）、及び誤差収束判定（ステップＳ２７）での判定処理は、第１の実施形態で示したものと同様である。誤差下限判定（ステップＳ２６）において、終了判定が出た場合は、ここまでに選択され修正された基底組数と、それらの１次元適応化基底組を符号化データとして記録して処理を終了する。上記の数値適用例では、この段階では誤差がまだ大きく、充分な近似ができているとはいえない。例えば、誤差の下限を１００としておくと、ここでは終了判定が出ないことになる。終了判定が出なかった場合は、次の誤差収束判定（ステップＳ２７）に進み、ここで誤差Ｅの収束判定を行う。数値適用例では、３０回程度修正を行うと、誤差Ｅはほぼ収束し、約１６１９９となる。収束後の１次元適応化組を図１８に示す。また、この１次元適応化基底組により復元される要素復元画像ｆ0~（ｘ、ｙ）に対応する８×８の数値列を図１９に示す。図中、１次元適応化基底の修正回数が、ｔ→∞となっているが、これは、誤差Ｅが収束する程度の回数修正を行ったという意味である。
【００４４】
第１の実施形態では、誤差収束判定（ステップＳ２７）において、誤差Ｅが収束したと判定された場合は、終了判定を出し処理を終了したが、本第２の実施形態では、次の処理である差分算出（ステップＳ２８）の処理に進む。収束したと判定されない場合は、基底復元（ステップＳ２２）に戻り、選択された基底番号 の１次元適応化基底組に対する修正を繰り返し実行する。
【００４５】
さて、誤差Ｅが収束したと判定された場合、差分算出（ステップＳ２８）において、基底番号ｌの１次元適応化基底組から復元される要素復元画像ｆ~l（ｘ，ｙ）を
【数１２】
2005244927.tif 000015
で算出し、差分被符号化画像ｆl+1（ｘ、ｙ）を、
【数１３】
2005244927.tif 000016
により生成する。上記説明してきた数値適用例では、ｌ＝０であったので、差分被符号化画像ｆ1（ｘ、ｙ）は、入力画像ｆ（ｘ、ｙ）から、基底番号０の１次元適応化基底組から復元される要素復元画像ｆ~0（ｘ，ｙ）を単純に差し引いたものになる。この差分被符号化画像ｆ1（ｘ、ｙ）に対応する８×８の数値列は、図２０に示したようになる。
【００４６】
次に、基底数判定（ステップＳ２８）において、ここまでに修正が完了した基底組数が、予め定めた所定数に達していた場合は、終了判定を出し、ここまでに選択され修正された基底組数と、それらの１次元適応化基底組を符号化データとして記録して処理を終了する。基底組数が所定数（許容数）に達していない場合は、基底設定（ステップＳ２１）に戻り、新たな１次元適応化基底組を選択して、上記説明した基底復元（ステップＳ２２）から誤差収束判定（ステップＳ２７）までの処理を繰り返し実行し、新たに選択された１次元適応化基底組の修正を行う。
【００４７】
上記説明してきた数値適用例では、まだ１組しか修正が完了していないので、例えば基底組数の許容数を４と設定しておくと、この段階では所定数に達していないので、基底設定（ステップＳ２１）に戻り、次の基底番号１の１次元適応化基底組を選択し、差分算出（ステップＳ２８）において求めた、差分被符号化画像ｆ1（ｘ、ｙ）を用い、「数１０−Ｂ」で示される式に従って、１次元適応化基底組の修正を行っていくことになる。
【００４８】
初期の１次元適応化基底組は、上述のように、全て図１１に示したものであるので、ここで選択される基底番号１の１次元適応化基底組も図１１に示したものと同じである。この時、まず一回目の修正量は、図２１に示したものになり、基底番号０の１回目の修正と同様に、一部の要素しか修正されない。この１回目の修正の、直前の誤差Ｅは、１６１９９．１９であったが、この修正により、誤差Ｅは１６１９９．１４となり、微量ではあるが減少する。そして、２回目の修正量は、図２２に示したようになり、修正後の誤差Ｅは、１６１９９．０７となる。このような修正を、誤差が収束するまで繰り返すことで、誤差Ｅは、約４７４９程度まで減少して収束する。
【００４９】
誤差が収束したら、「数１３」の式に基づき、次の差分被符号化画像ｆ2（ｘ、ｙ）を求める。ここで求めた、差分被符号化画像ｆ2（ｘ、ｙ）は、入力画像ｆ（ｘ、ｙ）から、基底番号０の１次元適応化基底組から復元される要素復元画像ｆ~0（ｘ，ｙ）と、基底番号１の１次元適応化基底組から復元される要素復元画像ｆ~1（ｘ，ｙ）とを差し引いたものになる。
【００５０】
このように、差分被符号化画像は、修正の完了した全ての１次元適応化基底組から復元される要素復元画像を、入力画像から差し引いた物となる。この差分被符号化画像ｆ2（ｘ、ｙ）に対し、基底番号２の、初期の１次元適応化基底組を選択し、「数１０−Ｂ」の式の基づき、この１次元適応化基底組の修正を行うというように、徐々に１次元適応化基底組の数を増やしていく。
【００５１】
数値適用例では、１組目の１次元適応化基底組の修正が完了した後には、上述のように、誤差Ｅが約１６１９９となり、２組目の修正が完了すると、誤差Ｅは、約４７４９となる。そして、３組目、４組目の修正がそれぞれ完了すると、誤差Ｅは約３３１２、約６７１となる。この数値適用例では、基底組数の許容量を４としていたので、誤差の大きさにかかわらず、基底数判定（ステップＳ２８）により、この段階で処理が終了する。もし、誤差下限判定（ステップＳ２６）での誤差の下限を１０００と設定していると、４組目の修正の途中で、誤差が設定した下限を下回るので、下回った段階で処理が終了となる。
しかし、基底組数を増やさずに、まだ誤差が減少する余地があるのに、途中で修正を打ち切るのは、処理時間の高速化としては意義があるが、近似性能という意味では得策ではない。そこで、誤差下限判定（ステップＳ２６）での終了判定は、下限を下回った時の１次元適応化基底組の修正において、誤差が収束したら終了判定とする、というようにしても良い。
【００５２】
基底数判定処理（ステップＳ２８）において用いる、予め定めた基底組の所定数は、無限個と設定しておいても構わないが、そのようにすると、誤差下限判定（ステップＳ２６）で用いる誤差の許容範囲を仮に小さく設定していると、非常に多数の基底組数を必要とする可能性が高くなる。そこで、基底組数に予め制限を与えておくことにより、データ量の上限を定めて上記符号化を行うことができる。
【００５３】
上記方法により符号化した符号化データを復号化画像ｆdecode（ｘ、ｙ） に復号するのは、下記に示すように行えばよい。
【数１４】
2005244927.tif 000017
上式のｋは選択され修正された基底組数を意味する。
【００５４】
このように、本第２の実施形態の符号化方法では、簡単な処理により、符号化された符号化データから、復号化データを得ることができる特徴がある。
【００５５】
数値適用例において得られた４組の１次元適応化基底組と、それにより復元される復号化画像に対応する８×８の数値列を図２３に示す。
【００５６】
この数値適用例では、説明を簡単にするため、符号化する画像を８×８としたが、この程度のサイズの場合は、データの圧縮という意味ではほとんど意味がない。データの圧縮という意味での画像データの符号化では、もう少しサイズの大きいデータに対して符号化を行う方が好適である。
【００５７】
例えば、図２４に示したような、１００×１００画素の画像に対して、上記の符号化を行い、それを復元した例を図２５に示す。
【００５８】
図２５では、左から基底組数が、それぞれ１組、２組、５組、１０組、２０組の場合に復元される復号化画像を示している。ここからわかるように、２０組程度になると充分に近似ができていることがわかる。もし被符号化データである１００×１００の画像の、１つの画素値が、４Ｂｙｔｅの浮動小数点であった場合、データ量は、４Ｂｙｔｅ×１００×１００＝４００００Ｂｙｔｅとなる。これに対し、１次元適応化基底の各要素の値を、同じく４Ｂｙｔｅの浮動小数点とした場合、基底組数２０組で、４Ｂｙｔｅ×（１００［Ｘ方向１次元適応化基底の要素数］＋１００［Ｙ方向１次元適応化基底の要素数］）×２０（基底組数）＝１６０００Ｂｙｔｅとなりデータの圧縮ができていることになる。
【００５９】
しかし実際には、図２４に示したような通常の画像の場合、１つの画素値は１Ｂｙｔｅで表されているので、データ量は１Ｂｙｔｅ×１００×１００＝１００００Ｂｙｔｅになる。この場合、１次元適応化基底の各要素の値を４Ｂｙｔｅの浮動小数点として持つようにすると、逆にデータ量が増えてしまう。しかし、通常の画像のような場合は、実際には１次元適応化基底の各要素の値に４Ｂｙｔｅもの精度は必要なく、例えば８ｂｉｔや６ｂｉｔといった程度の精度で充分となる。そこで、例えば、各１次元適応化基底の上限と下限のみを４Ｂｙｔｅの浮動小数点精度で保持しておき、その上限と下限を用いて、その１次元適応化基底の要素の値を、所望のｂｉｔ数にまるめるようにすればよい。
【００６０】
図２６は、左から、それぞれ８ｂｉｔ、６ｂｉｔ、４ｂｉｔにまるめて符号化した時の、基底組数２０組の場合に復元される復号化画像を示している。図２６の１番左側の８ｂｉｔでまるめたもののデータ量は、｛１Ｂｙｔｅ［８ｂｉｔ］×（１００［Ｘ方向１次元適応化基底の要素数］＋１００［Ｙ方向１次元適応化基底の要素数］）＋４Ｂｙｔｅ×４［１基底組に必要な上限・下限保持データ数］｝×２０［基底組数］＝４３２０Ｂｙｔｅとなり、データ量の圧縮ができている。ちなみに、６ｂｉｔの場合は３３２０Ｂｙｔｅ、４ｂｉｔの場合は２３２０Ｂｙｔｅとなり、データの圧縮ができることがわかる。
【００６１】
上記示した１次元適応化基底の要素の値をまるめる方法に関しては、この方法に限るものではなく、所定の絶対値を用いてまるめるなど、その他の方法を用いても良い。また、１次元適応化基底の要素の値をまるめる場合は、複数の１次元適応化基底組を用いて符号化が完了した後に、値をまるめるようにしても良いが、誤差が蓄積してしまう可能性があるので、１組の１次元適応化基底の修正が完了した段階で、値をまるめる処理を行い、そのまるめた後の１次元適応化基底を用いて、次の１次元適応化基底の修正に用いる差分被符号化画像を求めるようにするのが好適である。
【００６２】
また、さらにサイズが大きい画像、例えば１２８０×９６０の画像等の場合は、上記の符号化方法をそのまま適用しようとすると、１次元適応化基底の要素数が大きいため、誤差の収束が困難となる可能性が高くなる。このような場合には、予め画像を所定のサイズのブロック、例えば５０×５０のサイズのブロックに分割して、それぞれの分割されたブロックに対して、上記の符号化を行うようにすればよい。分割サイズを５０×５０とした場合に、この符号化を図２４の画像に適用して、復号化した画像を図２７に示す。この場合、左上の５０×５０のブロックでは、基底組数が８組であり、右上、左下、右下のブロックでは、それぞれ基底組数が１０組、７組、１２組である。この時、各１次元適応化基底の要素は８ｂｉｔにまるめた。この場合、この符号化後のデータのサイズは、上限、下限保持データも含めて４２９２Ｂｙｔｅとなり、分割せずに１００×１００のサイズのまま８ｂｉｔにまるめて符号化したものに比べ、ややデータ量が小さくなっている。このように、入力画像を適当なサイズで分割し、それぞれに対して符号化を行うことで、構造的に単純なブロックでは少ない基底組数で符号化ができるので、データ量を少なくすることができる。ただし、分割サイズをあまり小さくしすぎると、上述の８×８の例のように、１ブロックごとのデータの圧縮効果が少なり、さらに上限・下限保持データが多くなるので、適当な大きさのサイズにするのが良い。
【００６３】
分割のサイズに関しては、符号化する画像に対して適応的に決めるようにしても良いが、予め所定のサイズにしておくようにしても構わない。分割サイズを予め決めておくと、分割した際に余りが出てくることがある。例えば画像が１２８０×９６０で、分割サイズが５０×５０であり、分割を左上詰で行っていった場合は、画像右端に水平方向に３０画素、画像下端に垂直方向に１０画素の余りが出る。このような場合は、例えば画像右端の部分は３０×５０、画像下端の部分は５０×１０、画像右下の部分は３０×１０のサイズとして、符号化を行えばよい。また、余りの部分も全て５０×５０として、画像外、つまり画像右端の部分なら、左から２０画素分、画像下端の部分ならば、下から４０画素分、画像右下の部分ならば左から２０画素、下から４０画素分を、全て０として符号化を行うようしても構わない。
【００６４】
以上説明したように第２の実施の形態では、有限範囲で定義される離散的な２次元濃淡画像ｆ（ｘ、ｙ）を、複数の離散的な１次元適応化基底組Ｘl（ｘ）、Ｙl（ｙ）に符号化する。この結果、第１の実施形態と比較して、符号化対象が自然画の場合にも、精度良く対処することが可能となる。
【００６５】
＜第３の実施の形態＞
本第３の実施形態では、上記第２の実施形態の変形として、有限範囲で定義される離散的な２次元濃淡画像ｆ（ｘ、ｙ）を、分割したブロック毎の、複数の離散的な１次元適応化基底組Ｘξ,ζl（ｘ）、Ｙξ,ζl（ｙ）に変換し、それを符号化する方法を第３の実施形態として説明する。また、装置構成は第１の実施形態と同じであるものとし、その説明は省略する。
【００６６】
図３は、本第３の実施形態における処理のフローを示したものである。以下、同図に従って本第３の実施形態における処理手順を説明する。
【００６７】
まず、画像入力（ステップＳ３０）において、符号化される離散的な２次元濃淡画像である入力画像ｆ（ｘ、ｙ）を入力する。第１、第２の実施形態と同様、ｘ、ｙの定義域は０≦ｘ＜ｘmax、０≦ｙ＜ｙmaxであり、共に整数である。
【００６８】
次に、画像分割処理（ステップＳ３１）において、入力画像をサイズＬx 、Ｌy （Ｌx 、Ｌy は非負整数）の、以下の式で表される複数のウィンドウＷξ,ζ（ｘ、ｙ）に分割する。
【数１５】
2005244927.tif 000018
ここで、ξ,ζは０以上の整数であり、各ウィンドウの定義域は０≦ｘ＜Ｌx、０≦ｙ＜Ｌyである。また 、ｘ＋ξＬx≧ｘmax、若しくは、ｙ＋ζＬy≧ｙmaxとなるウィンドウでは、ｘ＋ξＬx≧ｘmax、若しくは、ｙ＋ζＬy≧ｙmaxの範囲を切り捨ててしまいＬx、Ｌyよりサイズの小さいウィンドウとすればよい。
【００６９】
次に、ウィンドウ選択処理を行う（ステップＳ３２）。ここでは、画像分割処理（ステップＳ３１）で入力画像を分割して得られたウィンドウから１つのウィンドウをＷξ,ζ（ｘ，ｙ）を選択する。選択の順序に関しては特に限定は無く、今まで選択されていないウィンドウを１つ選択すればよい。
【００７０】
次いで、ウィンドウ選択処理（ステップＳ３２）で選択されたウィンドウＷξ,ζ（ｘ，ｙ）に対し、基底組化処理を行う（ステップＳ３３）。ここでは、選択されたウィンドウＷξ,ζ（ｘ，ｙ）を複数の離散的な１次元適応化基底組Ｘξ,ζl（ｘ）、Ｙξ,ζl（ｙ）に変換する。この基底組化での処理は、第２の実施形態で説明した、複数の１次元適応化基底組に符号化する方法と同様の方法を用いればよい。ここで設定する１次元適応化基底組Ｘξ,ζl（ｘ）、Ｙξ,ζl（ｙ）の定義域は、基本的には０≦ｘ＜Ｌx 、０≦ｙ＜Ｌyとする。また、上記説明した ｘ＋ξＬx≧ｘmax、若しくは、ｙ＋ζＬy≧ｙmaxとなるウィンドウでは、そのウィンドウのサイズを
【数１６】
2005244927.tif 000019
としたとき、
【数１７】
2005244927.tif 000020
とすればよい。この画像分割処理（ステップＳ３１）における処理は、具体的には、第２の実施の形態において説明した、所定のブロックサイズに分割したものと同様である。
【００７１】
基底組化処理（ステップＳ３３）では、第２の実施形態と同様のものであるので、詳細な説明を割愛する。この基底組化処理（ステップＳ３３）により、ウィンドウ選択（ステップＳ３２）で選択された１つのウィンドウＷξ,ζ（ｘ，ｙ）の１次元適応化基底組変換が完了したら、次の選択終了判定処理（ステップＳ３４）に進む。
【００７２】
選択終了判定処理（ステップＳ３４）では、全てのウィンドウを選択したかどうかを判定して、まだ選択されていないウィンドウがある場合は、ウィンドウ選択（ステップＳ３２）に戻り、未選択のウィンドウを選択して、そのウィンドウに対して上記基底組化（ステップＳ３３）により、複数の１次元適応化基底組への変換を行う。全てのウィンドウを選択した場合は、次のＤＣＴ変換処理（ステップＳ３５）に進む。
【００７３】
ＤＣＴ変換処理（ステップＳ３５）では、基底組化処理（ステップＳ３３）で生成された、各ウィンドウＷξ,ζ（ｘ，ｙ）の、複数の離散的な１次元適応化基底組Ｘξ,ζl（ｘ）、Ｙξ,ζl（ｙ）のそれぞれを、ＤＣＴベクトルＵξ,ζl（ｘ）、Ｖξ,ζl（ｙ）に離散コサイン変換する。各１次元適応化基底に対する離散コサイン変換は、以下の変換式を用いて行えばよい。
【数１８】
2005244927.tif 000021
ここでｃxは、ｘ＝０のとき、ｃx＝１／√２である。また、ｘ≠０のとき、ｃx＝１である。ｃyも同様で、ｙ＝０のとき、ｃy＝１／√２であり、ｙ≠０のとき、ｃy＝１である。
【００７４】
上記変換により、基底組化処理（ステップＳ３３）で生成され、全ての離散的な１次元適応化基底Ｘξ,ζl（ｘ）、Ｙξ,ζl（ｙ）それぞれを、ＤＣＴベクトルＵξ,ζl（ｘ）、Ｖξ,ζl（ｙ）に変換する。
【００７５】
次いで、量子化処理（ステップＳ３６）において、ＤＣＴ変換処理（ステップＳ３５）により得られた全てのＤＣＴベクトルＵξ,ζl（ｘ）、Ｖξ,ζl（ｙ）に対して量子化を行い、量子化基底Ｕqξ,ζl（ｘ）、Ｖqξ,ζl（ｙ）を生成する。量子化は、ＤＣＴベクトルの要素数の等しい１次元の量子化係数ベクトルＱx（ｘ）及びＱy（ｙ）を用いて以下に示すように行う。
【数１９】
2005244927.tif 000022
【００７６】
ここで、
2005244927.tif 000023
は、ａを超えない最大の整数を意味し、例えば、
2005244927.tif 000024
となる。本実施形態では、上記のように切捨てを行うが、四捨五入をして整数化するような方法でも構わない。
【００７７】
この量子化係数ベクトルＱx（ｘ）及びＱy（ｙ）は、ＪＰＥＧ形式の量子化係数と同様、高周波成分、つまりｘが大きい成分ほど量子化係数を大きくするのが好ましい。また、量子化係数ベクトルＱx（ｘ）及びＱy（ｙ）の値は、ＤＣＴベクトルのレンジと、各周波数成分で求められる分解能に応じて予め定めておけばよい。
【００７８】
最後に、量子化処理（ステップＳ３６）により得られた量子化基底Ｕqξ,ζl（ｘ）、Ｖqξ,ζl（ｙ）をエントロピー符号化する（ステップＳ３７）。このエントロピー符号化処理では、全ての量子化基底Ｕqξ,ζl（ｘ）、Ｖqξ,ζl（ｙ）を符号化データとして符号化を行う。ここでのエントロピー符号化の方法としては、例えばハフマン符号化や、算術符号化等の公知の符号化方法を用いればよい。そして、エントロピー符号化された量子化基底と、ウィンドウごとの基底数や、ウィンドウサイズ等の復号化に必要なインデックス情報を、符号化データの一部として記録して処理を終了する。インデックス情報に関しては、各インデックス情報を、予め定めて規格化されたものを用いれば省略することも可能である。
【００７９】
本第３の実施形態では、ＤＣＴ変換処理（ステップＳ３５）において、複数の離散的な１次元適応化基底組Ｘξ,ζl（ｘ）、Ｙξ,ζl（ｙ）に対し、そのまま離散コサイン変換を行ったが、特にこれに限るものではなく、各１次元適応化基底組Ｘξ,ζl（ｘ）、Ｙξ,ζl（ｙ）を更に分割し、それぞれに対して離散コサイン変換し、量子化して、エントロピー符号化するようにしても構わない。
【００８０】
上記方法により符号化した符号化データを復号化画像ｆdecode（ｘ，ｙ）に復号するのは、適宜インデックス情報を用いながら、まずエントロピー復号化により量子化基底Ｕqξ,ζl（ｘ）、Ｖqξ,ζl（ｙ）を生成して逆量子化し、復号化ＤＣＴベクトルＵdecodeξ,ζl（ｘ）、Ｖqξ,ζl（ｙ）を復元して、それに対して離散コサイン変換の逆変換を行うことにより、復号化１次元適応化基底Ｘdecodeξ,ζl（ｘ）、Ｙdecodeξ,ζl（ｙ）を復元する。次いで、復元した復号化１次元適応化基底Ｘdecodeξ,ζl（ｘ）、Ｙdecodeξ,ζl（ｙ）に基づき、復号化ウィンドウＷdecodeξ,ζ（ｘ，ｙ）を下記に示す式により生成する。
【数２０】
2005244927.tif 000025
【００８１】
上式のｋξ,ζは、ウィンドウごとの、選択され修正された基底組数である。復号化画像ｆdecode（ｘ、ｙ）は、上記生成した復号ウィンドウＷdecodeξ,ζ（ｘ，ｙ）を合成することで得ることができる。
【００８２】
本第３の実施形態では、第２の実施形態と同様、生成された離散的な１次元適応化基底組Ｘξ,ζl（ｘ）、Ｙξ,ζl（ｙ）から要素復元画像を復元して、差分被符号化画像を生成する。量子化のための誤差を吸収するため、順次生成される離散的な１次元適応化基底組Ｘξ,ζl（ｘ）、Ｙξ,ζl（ｙ）に対し、１次元適応化基底組が生成されるごとにＤＣＴ変換（ステップＳ３５）、及び量子化（ステップＳ３６）を行い、量子化後の量子化基底Ｕqξ,ζl（ｘ）、Ｖqξ,ζl（ｙ）から、ただちに上記復号化と同様の手法で、逆量子化、離散コサイン変換の逆変換を行い、復号化１次元基底Ｘdecodeξ,ζl（ｘ）、Ｙdecodeξ,ζl（ｙ）を生成し、この復号化１次元適応化基底を用いて、要素復元画像を復元して、差分被符号化画像を生成するようにしてもよい。
【００８３】
図２４に示した画像に対してこの符号化を適用し、それを復号化したものを図２８に示す。この符号化においては、画像を８×８のブロックに分割（Ｌx＝Ｌy＝８）して、符号化を行っている。この例では、上記のように１次元適応化基底組が１組生成されるごとに、ＤＣＴ変換、量子化を行い、それを逆量子化し、離散コサイン変換の逆変換を行って、それを用いて差分被符号化画像を生成するようにしている。これにより、量子化による誤差が次の１次元適応化基底組の生成時に吸収されるようになるので、量子化誤差の蓄積を防ぐことができる。８×８のブロックに分割した際に出てくる余りに関しては、画像外を０として全てが８×８のブロックになるようにして符号化を行った。また、量子化係数ベクトルＱx（ｘ）及びＱy（ｙ）は、ともに図２９に示したものを用いた。この場合、復号化に必要となる情報（画像サイズ：４Ｂｙｔｅ×２、各ブロックの基底組数：１Ｂｙｔｅ×ブロック数［１３×１３組］、量子化係数ベクトル：４Ｂｙｔｅ×８）を含めて、３７９０Ｂｙｔｅとなり、第２の実施形態の８ｂｉｔにまるめたものと同程度以上の画質でありながら、さらにデータ量の削減ができている。この例では、８×８のブロックに分割して、符号化を行ったが、例えば２０×２０のブロックに分割する等、その他のサイズで分割するようにしても構わない。
【００８４】
上記第３の実施形態に示した符号化方法では、第２の実施形態でも述べたように、入力画像を複数のウィンドウに分割して基底組化することにより、ウィンドウに対応する基底組数をウィンドウごとに可変にすることができる。そのため、濃度分布が単調なウィンドウ、例えば図５に示したような濃度分布であるウィンドウならば、そのウィンドウは少ない基底組数で誤差の少ない符号化をすることができ、ウィンドウが自然画像のような濃度分布であれば多くの基底組を用いて符号化するというように、基底組数の最適化を行うことができる。また、基底組化したものを離散コサイン変換して量子化し、それをエントロピー符号化することで、さらに高効率の符号化が可能になる。
【００８５】
以上、第３の実施の形態では、有限範囲で定義される離散的な２次元濃淡画像ｆ（ｘ、ｙ）を、分割したブロック毎の、複数の離散的な１次元適応化基底組Ｘdecodeξ,ζl（ｘ）、Ｙdecodeξ,ζl（ｙ）に変換し、それを符号化する方法の例として説明した。
【００８６】
＜第４の実施の形態＞
本第４の実施の形態では、第３の実施形態の変形として、有限範囲で定義される離散的な２次元濃淡画像ｆ（ｘ、ｙ）を２次元離散コサイン変換して量子化し、量子化周波数画像ｆu,vl（ξ,ζ）を生成して、それを複数の離散的な１次元適応化基底組Ｘu,vl（ｘ）、Ｙu,vl（ｙ）に符号化する方法を説明する。
【００８７】
装置構成は第１の実施形態と同様であり、以下、本第４の実施形態の処理を図４のフローチャートに従って説明する。
【００８８】
まず、画像入力（ステップＳ４０）において、符号化される離散的な２次元濃淡画像である入力画像ｆ（ｘ，ｙ）を入力する。ここでもｘ、ｙは、上記第２の実施形態と同様の有限の定義域をもち、整数であるとする。
【００８９】
次に、２次元ＤＣＴ変換処を行う（ステップＳ４１）。ここでは、入力画像ｆ（ｘ，ｙ）を所定サイズ、例えば縦幅８、横幅８の画素サイズの分割画像Ｗξ,ζ（ｘ，ｙ）に分割する。ここでの分割画像Ｗξ,ζ（ｘ，ｙ）は、上記第３の実施形態で示したウィンドウＷξ,ζ（ｘ，ｙ）と同様のものである。ステップＳ４１では、それぞれの分割画像Ｗξ,ζ（ｘ，ｙ）に対して２次元離散コサイン変換を行う。
【００９０】
次いで、２次元離散コサイン変換されたデータを量子化する（ステップＳ４２）。この量子化処理では、所定の量子化係数Ｑ（ｘ，ｙ）を用いて量子化し、量子化画像Ｗqξ,ζ（ｘ，ｙ）を生成する。つまり、ＪＰＥＧ形式の符号化における、２次元離散コサイン変換後、量子化というステップと同様の変換を行う。ここでの変換はＪＰＥＧ形式の変換と同様であるので詳細な説明は割愛する。
【００９１】
本第４の実施形態では、入力画像ｆ（ｘ，ｙ）を縦幅８、横幅８のサイズの分割画像Ｗξ,ζ（ｘ，ｙ）に分割して２次元離散コサイン変換を行い、高周波で値が大きくなるような量子化係数Ｑ（ｘ，ｙ）を用いて量子化するが、特にこれに限定するものではなく、その他のサイズで分割する、若しくは他の量子化係数を用いて量子化しても構わない。
【００９２】
次いで、周波数選択処理を行う（ステップＳ４３）。ここでは、周波数パラメータｕ，ｖを選択し、周波数画像ｆu,v（ξ,ζ）を生成する。ここで、周波数パラメータｕ，ｖは０以上の整数であり、本第４の実施形態では２次元ＤＣＴ変換（ステップＳ４１）で、入力画像ｆ（ｘ，ｙ）を縦幅８、横幅８のサイズの分割画像Ｗξ,ζ（ｘ，ｙ）に分割したので、７までの整数である。そのためここでは、周波数パラメータｕ，ｖは、ともにそれぞれ０から７の８種類あるので、計８×８＝６４の組み合わせから、１つの周波数パラメータの組み合わせを選択する。ここで生成する周波数画像ｆu,v（ξ,ζ）は、量子化（ステップＳ４２）において生成された量子化画像Ｗqξ,ζ（ｘ、ｙ）を用いて以下のように表わされる。
ｆu,v（ξ,ζ）＝Ｗqξ,ζ（ｘ、ｙ）
上式に示すとおり、周波数画像ｆu,v（ξ,ζ）は、各量子化画像Ｗqξ,ζ（ｘ、ｙ）中の、選択された周波数ｕ，ｖの成分を並べたものである。
【００９３】
次の基底組化処理（ステップＳ４４）では、選択された周波数パラメータｕ，ｖに対応して生成された周波数画像ｆu,v（ξ,ζ）を、複数の離散的な１次元適応化基底組Ｘu,vl（ξ）、Ｙu,vl（ζ）に変換する。ここでの処理は第２の実施形態で示した、複数の１次元適応化基底組に符号化する処理と同様であるので説明を割愛する。
【００９４】
選択終了判定（ステップＳ４５）では、全ての周波数パラメータｕ，ｖを選択したかどうかを判定する。本第４の実施形態では、周波数パラメータｕ，ｖの組み合わせは、全６４通りであるので、それを全て選択して、基底組化（ステップＳ４４）によりそれぞれの周波数パラメータｕ，ｖに対応する周波数画像ｆu,v（ξ,ζ）の基底組化が完了していれば、次のエントロピー符号化（ステップＳ４６）に進む。６４通り全ての周波数パラメータｕ，ｖの組み合わせを選択していない場合は、周波数選択（ステップＳ４３）に戻り、まだ選択されていない周波数パラメータｕ，ｖの組み合わせを選択し、基底組化（ステップＳ４４）により、選択された周波数パラメータｕ，ｖに対応する周波数画像ｆu,v（ξ,ζ）の基底組化を行う。
【００９５】
エントロピー符号化（ステップＳ４６）では、基底組化（ステップＳ４４）において生成された基底組Ｘu,vl（ξ）、Ｙu,vl（ζ）をエントロピー符号化し、符号化データとして、復元に必要なインデックス情報とともに記録して処理を終了する。ここでの処理は、上記第３の実施形態で説明したものと同様の処理を行えばよい。
【００９６】
この符号化データから、復号化画像を生成する方法は、第３の実施形態と同様に、適宜インデックス情報を用いながら、まずエントロピー復号化により１次元基底組を復元して、その基底組を用いて周波数画像を復元する。この周波数画像から量子化画像を生成して逆量子化し、それに対し２次元離散コサイン変換の逆変換を行うことで復号化画像を復元することができる。
【００９７】
第３の実施形態が入力画像を空間的に分割して符号化したのに対し、上記第４の実施形態では、周波数空間で分割して符号化する方法を示した。本第４の実施形態では、周波数空間で分割したものに対して１次元の基底組化を行ったが、周波数空間で分割したものをさらに空間的に分割して基底組化を行っても構わない。また、エントロピー符号化（ステップＳ４６）では、生成された基底組をそのままエントロピー符号化したが、１次元適応化基底組を量子化してからエントロピー符号化しても良いし、第３の実施形態と同様に、もう１度離散コサイン変換（１次元）し、量子化してエントロピー符号化しても構わない。
【００９８】
以上、有限範囲で定義される離散的な２次元濃淡画像ｆ（ｘ、ｙ）を２次元離散コサイン変換して量子化し、周波数画像ｆu,v（ξ,ζ）を生成して、それを複数の離散的な１次元適応化基底組Ｘu,vl（ξ）、Ｙu,vl（ζ）に符号化する方法の例として説明した。
【００９９】
＜第５の実施形態＞
上記第１乃至第４の実施形態では、全て２次元データに対する符号化について説明したが、本発明の符号化方法はこれに限るものではなく、多次元のデータに関しても適用できる。そこで本第５の実施の形態では、第２の実施形態の変形として、有限範囲で定義される離散的な３次元データｆ（ｘ，ｙ，ｚ）を、複数の離散的な１次元適応化基底組Ｘl（ｘ）、Ｙl（ｙ）、Ｚl（ｚ）に符号化する方法を説明する。
【０１００】
符号化される離散的な３次元データとしては、３次元空間内の離散的な密度分布データや、離散的な２次元濃淡画像の離散的な時系列データが考えられる。ここでは、３次元データの各要素（２次元濃淡画像の離散的な時系列データの場合には、所定時刻の２次元濃淡画像の画素）が１バイトで表現されるものとして説明する。
【０１０１】
まずはこのような符号化される３次元データｆ（ｘ，ｙ、ｚ）を入力する。ここでも第２の実施形態と同様に、ｘ、ｙ、ｚは所定の定義域０≦ｘ＜ｘmax 、０≦ｙ＜ｙmax 、０≦ｚ＜ｚmaxを有し、整数であるとする。この３次元データに対し、下記の誤差Ｅ、修正量ΔＸl（ｘ）、ΔＹl（ｙ）、ΔＺl（ｚ）に基づいて、第２の実施形態と同様に１次元適応化基底組Ｘl（ｘ）、Ｙl（ｙ）、Ｚl（ｚ）を修正していくことで符号化を行う。
【数２１】
2005244927.tif 000026
上式中のｆl（ｘ，ｙ，ｚ）や、ｆ~l（ｘ，ｙ，ｚ）は、第２の実施形態での差分被符号化画像ｆl（ｘ、ｙ）、要素復元画像ｆ~l（ｘ，ｙ）と同意であり、次元を３次元としただけのものである。その他のパラメータ等に関しても、第２の実施形態と同様のものであるので説明は割愛する。
【０１０２】
上記誤差Ｅ、修正量ΔＸl（ｘ）、ΔＹl（ｙ）、ΔＺl（ｚ）に基づき、第２の実施形態で説明したのと同様の方法で、１次元適応化基底組に対して修正をしていくことで、３次元データを１次元適応化基底組Ｘl（ｘ）、Ｙl（ｙ）、Ｚl（ｚ）に符号化する。各基底の修正に関しては、選択された１次元適応化基底組Ｘl（ｘ）、Ｙl（ｙ）、Ｚl（ｚ）に対して、修正後の各１次元適応化基底組をＸ'l（ｘ）、Ｙ'l（ｙ）、Ｚ'l（ｚ）としたとき、次のように修正する。
【数２２】
2005244927.tif 000027
【０１０３】
最後に、誤差Ｅが所定値以下になるか、若しくは基底数が所定数に達した場合に、今までに選択して修正した１次元適応化基底組Ｘl（ｘ）、Ｙl（ｙ）、Ｚl（ｚ）を記録して処理を終了する。ここでの処理に関しても、第２の実施形態と同様であるので、詳細な説明は割愛する。この場合、１次元適応化基底組Ｘl（ｘ）、Ｙl（ｙ）、Ｚl（ｚ）から復元される復号化データｆdecode（ｘ、ｙ、ｚ）は以下のようになる。
【数２３】
2005244927.tif 000028
上式中、ｋは基底組数である。このように符号化されるデータの次元数が増えた場合でも、上記のように誤差と修正量を求めることで符号化が可能になる。本実施形態では、入力された３次元データをそのまま１次元適応化基底に符号化しているが、上記第３の実施形態等で示したように、所定範囲で分割したり、離散コサイン変換等により周波数空間で分割したりしても構わない。
【０１０４】
以上、有限範囲で定義される離散的な３次元データｆ（ｘ、ｙ、ｚ）を、複数の離散的な１次元適応化基底組Ｘl（ｘ）、Ｙl（ｙ）、Ｚl（ｚ）に符号化する方法の例として説明した。
【０１０５】
＜第６の実施形態＞
上記第１乃至第５の実施形態では、誤差評価関数として、各要素の差の２乗誤差を用いたが、本発明の符号化方法はこれに限るものではなく、その他の誤差評価関数を用いても適用可能である。そこで本発明の第６の実施形態では、第２の実施形態の変形として、ａを参照データ、つまり符号化されるデータとし、ｂを評価データ、つまり符号化されたデータから復元されるデータとした時に、誤差評価関数としてΣ｛１／２×（ａ2−ａｂ）2｝を用い、有限範囲で定義される離散的な２次元濃淡画像ｆ（ｘ、ｙ）を、複数の離散的な１次元適応化基底組Ｘl（ｘ）、Ｙl（ｙ）に符号化する方法を説明する。
【０１０６】
まず、符号化される離散的な２次元濃淡画像ｆ（ｘ、ｙ）を入力する。ここでも第２の実施形態と同様に、ｘ、ｙは所定の定義域０≦ｘ＜ｘmax 、０≦ｙ＜ｙmaxを有し、整数であるとする。この２次元濃淡画像ｆ（ｘ、ｙ）に対し、下記の誤差Ｅ、修正量ΔＸl（ｘ）、ΔＹl（ｙ）に基づいて、第２の実施形態と同様に１次元適応化基底組Ｘl（ｘ）、Ｙl（ｙ）を修正していくことで符号化を行う。
【数２４】
2005244927.tif 000029
【０１０７】
上式中のｆl（ｘ，ｙ）や、ｆ~l（ｘ，ｙ）は、第２の実施形態での差分被符号化画像ｆl(ｘ，ｙ）、要素復元画像ｆ~l（ｘ，ｙ）と同様のものである。また、その他のパラメータ等に関しても、第２の実施形態と同様のものであるので説明は割愛する。
【０１０８】
上記誤差Ｅ、修正量ΔＸl（ｘ）、ΔＹl（ｙ）に基づき、第２の実施形態で説明したのと同様の方法で、１次元適応化基底組を修正をしていくことで、１次元適応化基底組Ｘl（ｘ）、Ｙl（ｙ）に符号化する。各１次元適応化基底組の修正に関しては、選択された１次元適応化基底組Ｘl（ｘ）、Ｙl（ｙ）に対して、修正後の各１次元適応化基底組をＸ'l（ｘ）、Ｙ'l（ｙ）、修正前の基底をＸl（ｘ）、Ｙl（ｙ）とした時に、次のように修正する。
【数２５】
2005244927.tif 000030
【０１０９】
最後に、誤差Ｅが所定値以下になるか、若しくは基底組数が所定数に達した場合に、今までに選択して修正した１次元適応化基底組Ｘl（ｘ）、Ｙl（ｙ）を記録して処理を終了する。ここでの処理に関しても、第２の実施形態と同様であるので、詳細な説明は割愛する。この場合の復号化画像ｆdecode（ｘ，ｙ）は、第２の実施形態で示したものと同様である。
【０１１０】
このように、２乗誤差以外の誤差評価関数を用いても、上記のように誤差と修正量を求めることで符号化が可能になる。本第６の実施形態では、誤差評価関数として、Σ｛１／２×（ａ2−ａｂ）2｝を用いたが、本発明の符号化方法はこれに限るものではなく、被符号化データに近づくことにより誤差が減少するようなものであれば、その他の誤差評価関数であっても構わない。例えば２次元画像であれば、差分被符号化画像と、要素復元画像を微分したものの差分を誤差評価関数に含むようにする等しても良い。そのような誤差評価関数のうち、上記示したような、修正すべきパラメータ、ここではＸl（ｘ）、Ｙl（ｙ）での偏微分が解析的に求められることが好ましいが、解析的に偏微分を求められない場合は、修正すべきパラメータに微小変化を与えた時の誤差の増減から修正量を決めてやるようにすればよい。
【０１１１】
以上、誤差評価関数にΣ１／２×｛ａ2−ａｂ）2｝を用い、有限範囲で定義される離散的な２次元濃淡画像ｆ（ｘ、ｙ）を、複数の離散的な１次元適応化基底組Ｘl（ｘ）、Ｙl（ｙ）に符号化する方法の例として説明した。なお、本第６の実施形態では、特に第２の実施形態に適用する例を説明したが、他の実施形態にも同様に適用できるのは明らかである。
【０１１２】
＜第７の実施形態＞
上記第１乃至第６の実施形態では、多次元のデータを複数個の１次元適応化基底組に符号化する方法を示したが、本発明の符号化方法はこれに限るものではなく、その他のデータに符号化する方法においても適用可能である。そこで本発明の第７の実施形態では、第２の実施形態の変形として、有限範囲で定義される離散的な２次元濃淡画像ｆ（ｘ，ｙ）を、複数の離散的な２次元適応化基底Ｓl（ｘs、ｙs）に符号化する方法を説明することとする。
【０１１３】
まず、符号化される離散的な２次元濃淡画像ｆ（ｘ，ｙ）を入力する。ここでも第２の実施形態と同様に、ｘ、ｙは所定の定義域０≦ｘ＜ｘmax、０≦ｙ＜ｙmaxを有し、整数であるとする。次に基底として、離散的な２次元適応化基底Ｓl（ｘs、ｙs）を１つ選択する。ここでｘs、ｙsは、ｘmaxもしくはｙmaxが偶数である場合は、それぞれの定義域が０≦ｘs＜（ｘmax／２）＋１、０≦ｙs＜（ｙmax／２）＋１となる整数である。ｘmax、ｙmaxが奇数である場合は、それぞれの定義域は０≦ｘs＜（ｘmax／２）＋０．５、０≦ｙs＜（ｙmax／２）＋０．５となる整数である。また、添字ｌは基底番号であり、特に限定はしないが、本第７の実施形態でも０から順に、予め定めた基底数まで順に選択していくことにする。
【０１１４】
次に、選択した基底番号ｌの２次元適応化基底Ｓl（ｘs、ｙs）から、要素復元画像ｆ~l（ｘ、ｙ）を次のように算出する。
【数２６】
2005244927.tif 000031
【０１１５】
上記求めた要素復元画像ｆ~l（ｘ、ｙ）を用いて、誤差Ｅ、及び修正量ΔＳl（ｘs、ｙs）を以下のように算出する。
【数２７】
2005244927.tif 000032
【０１１６】
上式のｆl（ｘ，ｙ）は差分被符号化画像であり、第２の実施形態と同様のものである。また修正量ΔＳl（ｘs、ｙs）を算出する式においてＣ（ｍ、ｎ）は次の値を有する。
・ｎ＝０、且つ、ｍ＝０の場合
Ｃ（ｎ，ｍ）＝１
・ｎ＝±１、且つ、ｍ＝０の場合、又は、ｎ＝０、且つ、ｍ＝±１の場合
Ｃ（ｎ，ｍ）＝０．５
・ｎ＝±１、且つ、ｍ＝±１０の場合
Ｃ（ｎ，ｍ）＝０．２５
ただし、上記算出式において、２ｘs＋ｎ＜０、２ｘs＋ｎ≧ｘmax、２ｙs＋ｍ＜０、又は、２ｙs＋ｎ≧ｙmaxのいずれかに場合には、Ｃ（ｎ，ｍ）＝０とする。
【０１１７】
またηは修正パラメータであり、第２の実施形態で説明したηx、ηyと同様のものである。上記誤差Ｅ、修正量ΔＳl（ｘs、ｙs）に基づき、第２の実施形態で説明したのと同様の方法で、２次元適応化基底に対して修正をしていくことで、入力画像ｆ（ｘ，ｙ）を２次元適応化基底Ｓl（ｘs、ｙs）に符号化する。
【０１１８】
基底の修正に関しては、選択された２次元適応化基底Ｓl（ｘs、ｙs）を次のように修正する。式中、Ｓ'l（ｘs、ｙs）が修正後、Ｓl（ｘs、ｙs）が修正前である。
Ｓ'l（ｘs、ｙs）＝Ｓl（ｘs，ｙs）＋ΔＳl（ｘs，ｙs）
【０１１９】
最後に、誤差Ｅが所定値以下になるか、若しくは基底数が所定数に達した場合に、今までに選択して修正した２次元適応化基底Ｓl（ｘs、ｙs）を記録して処理を終了する。ここでの処理に関しても、第２の実施形態と同様であるので、詳細な説明は割愛する。この方法により符号化した符号化データを復号化画像ｆdecode（ｘ，ｙ）に復号するのは、下記に示すように行えばよい。
【数２８】
2005244927.tif 000033
【０１２０】
上式のｋは選択され修正された基底数である。本第７の実施形態では、生成する２次元適応化基底Ｓl（ｘs、ｙs）を、要素数が入力画像ｆ（ｘ，ｙ）の約１／４の画像としたが、これに限るものではなく、これとは異なる要素数の２次元適応化基底を用いて符号化しても構わない。
【０１２１】
以上、有限範囲で定義される離散的な２次元濃淡画像ｆ（ｘ、ｙ）を、複数の離散的な２次元適応化基底Ｓl（ｘs、ｙs）に符号化する第７の実施形態を説明した。
【０１２２】
＜第８の実施形態＞
上記第１乃至第７の実施形態では、適応化基底として１次元適応化基底や２次元適応化基底を用いて符号化する方法を示したが、本発明の符号化方法はこれに限るものではなく、いくつかのパラメータで構成されるような適応化基底を用いるような場合でも適用可能である。そこで本発明の第８の実施形態では、第２の実施形態の変形として、有限範囲で定義される離散的な２次元濃淡画像ｆ（ｘ，ｙ）を、複数のパラメータで構成される適応化基底に符号化する例を説明する。以下では、具体的な例として、４つのパラメータＡl、ｐl、ｑl、ρlから構成される適応化基底Ｇl（Ａl、ｐl、ｑl、ρl）に符号化する方法を説明する。
【０１２３】
まず、符号化される離散的な２次元濃淡画像ｆ（ｘ，ｙ）を入力する。ここでも第２の実施形態と同様に、ｘ、ｙは所定の定義域 ０≦ｘ＜ｘmax、０≦ｙ＜ｙmaxを有し、整数であるとする。次に初期の適応化基底として、適応化基底Ｇlを１つ選択する。添字ｌは基底番号であり、特に限定はしないが、本第８の実施形態でも０から順に、予め定めた基底数まで順に選択していくことにする。
【０１２４】
次に、選択した基底番号ｌの適応化基底Ｇlから、要素復元画像ｆ~l（ｘ，ｙ）を次のように算出する。
【数２９】
2005244927.tif 000034
【０１２５】
次に、上記求めた要素復元画像ｆ~l（ｘ，ｙ）を用いて、誤差Ｅ、及び修正量ΔＡl、Δｐl、Δｑl、Δρlを以下のように算出する。
【数３０】
2005244927.tif 000035
【０１２６】
上式のｆl（ｘ、ｙ）は差分被符号化画像であり、第２の実施形態と同様のものである。またηA、ηp、ηq、ησは修正パラメータであり、第２の実施形態で説明したηx、ηyと同様のものである。上記誤差Ｅ、修正量ΔＡl、Δｐl、Δｑl、Δρlに基づき、第２の実施形態で説明したのと同様の方法で、適応化基底を構成する各パラメータに対して修正をしていくことで、適応化基底Ｇlに符号化する。
【０１２７】
適応化基底の修正に関しては、選択された基底Ｇlを構成する各パラメータＡl、ｐl、ｑl、ρlを以下のようにして修正する。Ａ'l、ｐ'l、ｑ'l、ρ'lが修正後、Ａl、ｐl、ｑl、ρlが修正前である。
Ａ'l＝Ａl＋ΔＡl
ｐ'l＝ｐl＋Δｐl
ｑ'l＝ｑl＋Δｑl
ρ'l＝ρl＋Δρl
【０１２８】
最後に、誤差Ｅが所定値以下になるか、若しくは基底数が所定数に達した場合に、今までに選択して修正した適応化基底Ｇlを構成する各パラメータＡl、ｐl、ｑl、ρlを記録出力して処理を終了する。ここでの処理に関しても、第２の実施形態と同様であるので、詳細な説明は割愛する。この方法により符号化した符号化データを復号化画像ｆdecode（ｘ，ｙ）に復号するのは、下記に示すように行えばよい。
【数３１】
2005244927.tif 000036
上式のｋは選択され修正された基底数である。本第８の実施形態では、４つのパラメータにより構成される適応化基底Ｇlを用いたが、これに限るものではなく、これとは異なるパラメータ数の適応化基底を用いて符号化しても構わない。
【０１２９】
以上、有限範囲で定義される離散的な２次元濃淡画像ｆ（ｘ，ｙ）を、複数のパラメータから構成される適応化基底Ｇlに符号化する方法の例として説明した。
【０１３０】
＜第９の実施形態＞
本第９の実施形態では、所定の２次元荷重分布データによる、２次元分布データに対する離散的コンボリューション演算において、２次元荷重分布データを第２の実施形態のデータ符号化処理により１次元適応化基底組に変換し、それを用いて２次元分布データに対する離散的コンボリューション演算を行う方法を説明する。ここで示す離散的コンボリューション演算は、例えば、Convolutional Neural Networks（LeCun,Y. and Bengio,Y. ,1995, “Convolutional Networks for Images Speech, and Time Series” in Handbook of Brain Theory and Neural Networks (M.Arbib,Ed.),MIT Press,pp.255-258）における１つの特徴検出細胞面の演算等に用いることができる。この場合、２次元荷重分布データは、シナプス荷重分布と見なせる。
【０１３１】
まず、離散的なコンボリューション演算を行う離散的な２次元荷重分布データｗ（ｘ，ｙ）を入力する。この２次元荷重分布データは離散的であるので、ｘ、ｙは整数とする。この２次元荷重分布データによる、２次元分布データｆ（ｘ，ｙ）に対する離散的コンボリューション演算結果Ｚ（ｘ，ｙ）は以下の式で表される。
【数３２】
2005244927.tif 000037
【０１３２】
次に、入力された２次元荷重分布データｗ（ｘ，ｙ）から、第２の実施形態で示した方法と同様の方法により、１次元適応化基底組Ｘl（ｘ）、Ｙl（ｙ）を生成する。１次元適応化基底組Ｘl（ｘ）、Ｙl（ｙ）の添え字ｌは基底番号である。ここでの詳細な説明は、第２の実施形態で示したものと同様なので説明を割愛する。ここで生成した１次元適応化基底組は、コンボリューション演算を行うたびに生成する必要はなく、予め第２の実施形態で示した方法により生成しておき、生成した１次元適応化基底組を記録して保存しておけばよい。
【０１３３】
生成された１次元適応化基底組により、２次元分布データｆ（ｘ，ｙ）に対する離散的コンボリューション演算結果Ｚ（ｘ，ｙ）は、以下のようになる。
【数３３】
2005244927.tif 000038
【０１３４】
このように、２次元荷重分布データｗ（ｘ，ｙ）を１次元適応化基底組Ｘl（ｘ）、Ｙl（ｙ）に分解し、それを用いて離散的コンボリューション演算を行うことで、従来は図６に示すように、例えば６×６の要素で構成される２次元荷重分布データによる離散的コンボリュ−ション演算であれば、各座標の計３６の要素に独立に２次元荷重分布データの値を与える、つまり各座標に対して独立に２次元荷重分布データの値を信号として送るために３６本の信号線が必要であったが、本実施形態では図７に示すように、計１２本の信号があれば良く、コンボリューション演算器において問題となっていた配線問題を解決することができる。なお、この離散的コンボリューション演算方法を実行するための、積和演算素子をアレイ状に配置したコンボリューション演算器では、図７に示すように１次元適応化基底組Ｘl（ｘ）、Ｙl（ｙ）をアレイの全ての列・行に入力して演算を実行しても良いし、または図９に示すように１次元適応化基底組Ｘl（ｘ）、Ｙl（ｙ）をそれぞれ一部の列・行にのみ入力して、Ｘl（ｘ）とＹl（ｙ）の両方が入力されている、アレイ中の一部の領域（６３）においてのみ演算を実行しても構わない。
【０１３５】
以上、所定の２次元荷重分布データによる、２次元分布データに対する離散的コンボリューション演算において、２次元荷重分布データを第２の実施形態のデータ符号化方法により、１次元適応化基底組に変換し、それを用いて２次元分布データに対する離散的コンボリューション演算を行う方法の例として説明した。
【０１３６】
以上、本発明に係る実施形態を説明したが、本発明は、図８に示すようにコンピュータプログラムによっても実現できることは明らかであるので、本発明はこのようなコンピュータプログラムをもその範疇とする。また、通常コンピュータプログラムは、ＣＤＲＯＭ等のコンピュータ可読記憶媒体に記憶されており、それをコンピュータが有する記憶媒体ドライブ装置にセットし、システムにコピーもしくはインストールすることで実行可能になるわけであるから、本発明はかかるコンピュータ可読記憶媒体をもその範疇とするのは明らかである。
【図面の簡単な説明】
【０１３７】
【図１】第１の実施形態における符号化処理を示すフローチャートである。
【図２】第２の実施形態における符号化処理を示すフローチャートである。
【図３】第３の実施形態における符号化処理を示すフローチャートである。
【図４】第４の実施形態における符号化処理を示すフローチャートである。
【図５】単純な矩形形状の２次元画像の例を示す図である。
【図６】従来の２次元荷重分布データの送信構造を示す図である。
【図７】第９の実施形態の積和演算方法を実行するコンボリューション演算器における、２次元荷重分布データの送信構造を示す図である。
【図８】実施形態における装置構成を示すブロック構成図である。
【図９】第９の実施形態の積和演算方法を実行するコンボリューション演算器における、２次元荷重分布データの送信構造を示す図である。
【図１０】数値適用例における入力画像に対応する８×８の輝度値データを示す図である。
【図１１】数値適用例における初期の１次元適応化基底組を示す図である。
【図１２】数値適用例における初期の１次元適応化基底組から復元される要素復元画像に対応する８×８の数値列を示す図である。
【図１３】数値適用例における基底番号０の１次元適応化基底組の１回目の修正量を示す図である。
【図１４】数値適用例における基底番号０の１回目の修正後の１次元適応化基底組を示す図である。
【図１５】数値適用例における基底番号０の１次元適応化基底組の２回目の修正量を示す図である。
【図１６】数値適用例における基底番号０の１次元適応化基底組の９回目の修正量を示す図である。
【図１７】数値適用例における基底番号０の１次元適応化基底組の修正時の修正回数に対する誤差Ｅの変化を示す図である。
【図１８】数値適用例における基底番号０の誤差Ｅが収束した後の１次元適応化基底組を示す図である。
【図１９】数値適用例における基底番号０の誤差Ｅが収束した後の１次元適応化基底組から復元される要素復元画像に対応する８×８の数値列を示す図である。
【図２０】数値適用例のおける基底番号０の１次元適応化基底組の修正完了後の差分被符号化画像に対応する８×８の数値列を示す図である。
【図２１】数値適用例における基底番号１の１次元適応化基底組の１回目の修正量を示す図である。
【図２２】数値適用例における基底番号１の１次元適応化基底組の２回目の修正量を示す図である。
【図２３】数値適用例における修正完了後の４組の１次元適応化基底組と、それらから復元される復号化画像に対応する８×８の数値列を示す図である。
【図２４】第２の実施形態における入力画像の例を示す図である。
【図２５】第２の実施形態における復号化画像の例を示す図である。
【図２６】第２の実施形態における精度をまるめた場合の復号化画像の例を示す図である。
【図２７】第２の実施形態における入力画像を分割して符号化し、それを復号化した復号化画像の例を示す図である。
【図２８】第３の実施形態における復号化画像の例を示す図である。
【図２９】第３の実施形態における量子化係数ベクトルの例を示す図である。
【図１】
2005244927.tif 000047
【図２】
2005244927.tif 000048
【図３】
2005244927.tif 000049
【図４】
2005244927.tif 000050
【図５】
2005244927.tif 000051
【図６】
2005244927.tif 000052
【図７】
2005244927.tif 000053
【図８】
2005244927.tif 000054
【図９】
2005244927.tif 000055
【図１０】
2005244927.tif 000056
【図１１】
2005244927.tif 000057
【図１２】
2005244927.tif 000058
【図１３】
2005244927.tif 000059
【図１４】
2005244927.tif 000060
【図１５】
2005244927.tif 000061
【図１６】
2005244927.tif 000062
【図１７】
2005244927.tif 000063
【図１８】
2005244927.tif 000064
【図１９】
2005244927.tif 000065
【図２０】
2005244927.tif 000066
【図２１】
2005244927.tif 000067
【図２２】
2005244927.tif 000068
【図２３】
2005244927.tif 000069
【図２９】
2005244927.tif 000070
【図２４】
2005244927.tif 000071
【図２５】
2005244927.tif 000072
【図２６】
2005244927.tif 000073
【図２７】
2005244927.tif 000074
【図２８】
2005244927.tif 000075