(57)【特許請求の範囲】
【請求項１】
コンピュータに、非可逆圧縮して符号化された信号を入力し、その復号信号が存在する第１のベクトル空間において任意の実数ベクトルを一つの凸集合Ｘに直交射影する第１の射影手段と、前記第１の射影手段を介して凸射影が収束したかどうかを判定し、凸射影が収束したと判定された場合に、集合Ｘに属する実数ベクトルｘを求めて復号信号として出力する収束判定手段と、凸射影が収束していないと判定された場合に、前記第１のベクトル空間の任意のベクトルを前記第１のベクトル空間とは異なる前記第２のベクトル空間において一つの凸集合Ｙに直交射影した後、前記第１の射影手段に移行させて、前記符号化された信号を初期値として、集合Ｘと集合Ｙへの直交射影を繰り返させる第２の射影手段として機能させるための符号化データの復号プログラム。
【請求項２】
請求項１に記載の符号化データの復号プログラムにおいて、
前記集合Ｘと前記集合Ｙは、各成分がとり得る値の範囲が有限であるベクトルの集合として定義される
ことを特徴とする符号化データの復号プログラム。
【請求項３】
請求項１に記載の符号化データの復号プログラムにおいて、
コンピュータに、前記収束判定手段により凸射影が収束したと判定された場合に、集合Ｘに属する実数ベクトルを整数ベクトルに変換する整数化手段と、整数ベクトルが集合Ｙに属するか否かを判定し、集合Ｙに属すると判定された場合に整数ベクトルを復号ベクトルとして出力する終了判定手段と、集合Ｙに属しないと判定された場合に、前記集合Ｙを縮小してその部分集合である新たな凸集合Ｗを生成する縮小手段と、変換された整数ベクトルを前記凸集合Ｗに直交射影した後、前記第１の射影手段に移行させて、前記符号化された信号を初期値として、集合Ｗと集合Ｘの間で直交射影を行って実数ベクトルｘを繰り返し修正させる第３の射影手段としてさらに機能させるための符号化データの復号プログラム。
【請求項４】
請求項３に記載の符号化データの復号プログラムにおいて、
前記集合Ｗは、各成分がとり得る値の範囲が有限であるベクトルの集合として定義され、その範囲が前記集合Ｙを定義する各成分の範囲をそれぞれｋ（ｋ＜１）倍に縮小したもので与えられる
ことを特徴とする符号化データの復号プログラム。
【請求項５】
請求項１に記載の符号化データの復号プログラムにおいて、
前記符号化された信号は、前記第２のベクトル空間のベクトルを第１の量子化ベクトルで量子化したものであり、前記集合Ｙは、このベクトルを第２の量子化ベクトルで量子化したときに、一つのベクトルｙに一致するようなベクトルの集合として定義される
ことを特徴とする符号化データの復号プログラム。
【請求項６】
請求項５に記載の符号化データの復号プログラムにおいて、
前記第１の量子化ベクトルと前記第２の量子化ベクトルが同一である
ことを特徴とする符号化データの復号プログラム。
【請求項７】
非可逆圧縮して符号化された信号を入力し、その復号信号が存在する第１のベクトル空間において任意の実数ベクトルを一つの凸集合Ｘに直交射影する第１の射影ステップと、
前記第１の射影ステップを介して凸射影が収束したかどうかを判定し、凸射影が収束したと判定された場合に、集合Ｘに属する実数ベクトルｘを求めて復号信号として出力する収束判定ステップと、
凸射影が収束していないと判定された場合に、前記第１のベクトル空間の任意のベクトルを前記第１のベクトル空間とは異なる前記第２のベクトル空間において一つの凸集合Ｙに直交射影した後、前記第１の射影ステップに移行させて、前記符号化された信号を初期値として、集合Ｘと集合Ｙへの直交射影を繰り返させる第２の射影ステップと
を備えた符号化データの復号方法。
【請求項８】
請求項７に記載の符号化データの復号方法において、
前記集合Ｘと前記集合Ｙは、各成分がとり得る値の範囲が有限であるベクトルの集合として定義される
ことを特徴とする符号化データの復号方法。
【請求項９】
請求項７に記載の符号化データの復号方法において、
前記収束判定ステップにより凸射影が収束したと判定された場合に、集合Ｘに属する実数ベクトルを整数ベクトルに変換する整数化ステップと、
整数ベクトルが集合Ｙに属するか否かを判定し、集合Ｙに属すると判定された場合に整数ベクトルを復号ベクトルとして出力する終了判定ステップと、
集合Ｙに属しないと判定された場合に、前記集合Ｙを縮小してその部分集合である新たな凸集合Ｗを生成する縮小ステップと、
変換された整数ベクトルを前記凸集合Ｗに直交射影した後、前記第１の射影ステップに移行させて、前記符号化された信号を初期値として、集合Ｗと集合Ｘの間で直交射影を行って実数ベクトルｘを繰り返し修正させる第３の射影ステップと
をさらに備えたことを特徴とする符号化データの復号方法。
【請求項１０】
請求項９に記載の符号化データの復号方法において、
前記集合Ｗは、各成分がとり得る値の範囲が有限であるベクトルの集合として定義され、その範囲が前記集合Ｙを定義する各成分の範囲をそれぞれｋ（ｋ＜１）倍に縮小したもので与えられる
ことを特徴とする符号化データの復号方法。
【請求項１１】
請求項７に記載の符号化データの復号方法において、
前記符号化された信号は、前記第２のベクトル空間のベクトルを第１の量子化ベクトルで量子化したものであり、前記集合Ｙは、このベクトルを第２の量子化ベクトルで量子化したときに、一つのベクトルｙに一致するようなベクトルの集合として定義される
ことを特徴とする符号化データの復号方法。
【請求項１２】
請求項１１に記載の符号化データの復号方法において、
前記第１の量子化ベクトルと前記第２の量子化ベクトルが同一である
ことを特徴とする符号化データの復号方法。
【請求項１３】
非可逆圧縮して符号化された信号を入力し、その復号信号が存在する第１のベクトル空間において任意の実数ベクトルを一つの凸集合Ｘに直交射影する第１の射影手段と、
前記第１の射影手段を介して凸射影が収束したかどうかを判定し、凸射影が収束したと判定された場合に、集合Ｘに属する実数ベクトルｘを求めて復号信号として出力する収束判定手段と、
凸射影が収束していないと判定された場合に、前記第１のベクトル空間の任意のベクトルを前記第１のベクトル空間とは異なる前記第２のベクトル空間において一つの凸集合Ｙに直交射影した後、前記第１の射影手段に移行させて、前記符号化された信号を初期値として、集合Ｘと集合Ｙへの直交射影を繰り返させる第２の射影手段と
を備えた符号化データの復号装置。
【請求項１４】
請求項１３に記載の符号化データの復号装置において、
前記集合Ｘと前記集合Ｙは、各成分がとり得る値の範囲が有限であるベクトルの集合として定義される
ことを特徴とする符号化データの復号装置。
【請求項１５】
請求項１３に記載の符号化データの復号装置において、
前記収束判定手段により凸射影が収束したと判定された場合に、集合Ｘに属する実数ベクトルを整数ベクトルに変換する整数化手段と、
整数ベクトルが集合Ｙに属するか否かを判定し、集合Ｙに属すると判定された場合に整数ベクトルを復号ベクトルとして出力する終了判定手段と、
集合Ｙに属しないと判定された場合に、前記集合Ｙを縮小してその部分集合である新たな凸集合Ｗを生成する縮小手段と、
変換された整数ベクトルを前記凸集合Ｗに直交射影した後、前記第１の射影手段に移行させて、前記符号化された信号を初期値として、集合Ｗと集合Ｘの間で直交射影を行って実数ベクトルｘを繰り返し修正させる第３の射影手段と
をさらに備えたことを特徴とする符号化データの復号装置。
【請求項１６】
請求項１５に記載の符号化データの復号装置において、
前記集合Ｗは、各成分がとり得る値の範囲が有限であるベクトルの集合として定義され、その範囲が前記集合Ｙを定義する各成分の範囲をそれぞれｋ（ｋ＜１）倍に縮小したもので与えられる
ことを特徴とする符号化データの復号装置。
【請求項１７】
請求項１３に記載の符号化データの復号装置において、
前記符号化された信号は、前記第２のベクトル空間のベクトルを第１の量子化ベクトルで量子化したものであり、前記集合Ｙは、このベクトルを第２の量子化ベクトルで量子化したときに、一つのベクトルｙに一致するようなベクトルの集合として定義される
ことを特徴とする符号化データの復号装置。
【請求項１８】
請求項１７に記載の符号化データの復号装置において、
前記第１の量子化ベクトルと前記第２の量子化ベクトルが同一である
ことを特徴とする符号化データの復号装置。
【発明の詳細な説明】
【技術分野】  この発明は、非可逆圧縮して符号化された信号を入力し、その復号信号を出力する符号化データの復号プログラム及び方法並びに装置に関するものである。
【背景技術】  画像や音声などの情報をデジタル信号として伝送・蓄積する場合には、その冗長性を利用してデータ量を小さくする符号化技術が広く用いられる。この場合、人間の視覚・聴覚の特性が小さな歪みに鈍感であることを利用して再生信号に歪みを許容すれば、より大きな圧縮が可能となる。このような符号化方式は、原信号を正確には再現しないので、非可逆符号化と呼ばれる。
非可逆符号化によって符号化されたデータを復号する方法は、一般に符号化方法が与えられればその逆の処理を行うことによって実現することができる。図８は、例えば画像の符号化として広く用いられているＪＰＥＧ（Ｊｏｉｎｔ  Ｐｈｏｔｏｇｒａｐｈｉｃ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ）符号化データの復号装置を示すブロック図であり、ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｃｏｎｓｕｍｅｒ  Ｅｌｅｃｔｒｏｎｉｃｓ，１９９２年２月号の２１ページに開示されたものである。図８に示す復号装置は、符号化されたストリームを入力する可変長復号器８０と、逆量子化器８１と、逆ＤＣＴ（Ｄｉｓｃｒｅｔｅ  Ｃｏｓｉｎｅ  Ｔｒａｎｓｆｏｒｍ）変換器８２と、リミッタ８３と、整数化器８４とを備えている。リミッタ８３と整数化器８４は上記文献に開示されていないが、一般に広く用いられているものであり、以下の説明に重要なので付加した。
次に動作について説明する。ＪＰＥＧ符号化は、原信号をブロック単位にＤＣＴ変換し、その量子化インデックスを符号化するものであるから、復号化器はこの逆の処理を行えばよい。図８において、可変長復号化器８０は、ＪＰＥＧのストリームをＤＣＴ係数の量子化インデックスに復号する。逆量子化器８１は、この量子化インデックスをＤＣＴ係数に復号する。逆ＤＣＴ変換器８２は、このＤＣＴ係数に逆変換を施し、元の信号を再生する。逆ＤＣＴ変換器８２の出力は実数であり、再生信号をデジタルで表現する場合には、これを一定範囲の離散信号に変換しなければならない。この変換は、リミッタ８３と整数化器８４によって実行される。リミッタ８３は、逆ＤＣＴ変換器８２の出力を既定の範囲にクリップし、整数化器２３は、その結果を整数に変換する。クリップと整数化の処理は順序が逆であってもよい。この結果、整数化器８４の出力には、デジタルデータとして表現可能な形式の出力が得られる。以上の処理はブロック単位に行われ、最後に全てのブロックを統合して復号データを得る。
リミッタ８３と整数化器８４における処理は、多対一の写像であるから、その出力から元のＤＣＴ係数を復元することはできない。このことは、ストリームとして表現されていたＤＣＴ係数の量子化インデックスの一部の情報は復号によって失われることを意味する。
この情報の消失は、再生される画像が人間によって消費されるためだけに存在する場合には大きな問題ではなかった。すなわち、復号で導入されるこのような誤差は、人間に知覚されない微小なものであるため、問題とならなかった。しかし、通信の多様化に伴って、符号化された画像の構造を保持することの重要性が認識されつつある。例えば、二次利用のために、復号画像をロスレスで再符号化したり、電子透かしなどの情報が画像に含まれたりして、その情報を復号後も保持しなければならない場合がある。従来の復号方法は、ロスレスな再符号化や電子透かしの残存を保証することができなかった。
従来の符号化データの復号方法では、逆変換された信号のクリッピングや整数化によって誤差が導入され、復号された信号をもう一度符号化した場合に同じ符号化ストリームが得られないという問題がある。
また、クリッピングや整数化による誤差のために、量子化されたＤＣＴ係数の中に埋め込まれていた情報が消失するという問題がある。
この発明は、このような問題を解決するためになされたもので、復号されたデータをもう一度符号化した場合に元のストリームが完全に復元できる符号化データの復号プログラム及び方法並びに装置を提供することを目的とする。
また、ストリームとして表現されていた信号の構造を一定の量子化精度の範囲で保ち、量子化されたＤＣＴ係数の中に埋め込まれていた情報を完全に保持できる符号化データの復号プログラム及び方法並びに装置を提供することを目的とする。
【発明の開示】
この発明に係る符号化データの復号装置及び方法は、非可逆圧縮して符号化された信号を入力し、その復号信号が存在する第１のベクトル空間において任意の実数ベクトルを一つの凸集合Ｘに直交射影する第１の射影手段（またはステップ）と、前記第１の射影手段（またはステップ）を介して凸射影が収束したかどうかを判定し、凸射影が収束したと判定された場合に、集合Ｘに属する実数ベクトルｘを求めて復号信号として出力する収束判定手段（またはステップ）と、凸射影が収束していないと判定された場合に、前記第１のベクトル空間の任意のベクトルを前記第１のベクトル空間とは異なる前記第２のベクトル空間において一つの凸集合Ｙに直交射影した後、前記第１の射影手段（またはステップ）に移行させて、前記符号化された信号を初期値として、集合Ｘと集合Ｙへの直交射影を繰り返させる第２の射影手段（またはステップ）とを備えたものである。
また、この発明に係る符号化データの復号プログラムは、コンピュータに、符号化データの復号装置の各手段として機能させるためのものである。
【図面の簡単な説明】  図１は、この発明のアプローチを説明するためのもので、復号された変換係数がクリップされることによって量子化インデックスの値が変化する例を模式的に示した図、
図２は、この発明の実施の形態１を説明するもので、図１の二つの集合ＸとＹに対して、ｙｃを初期値として、集合Ｘと集合Ｙへの直交射影を繰り返すことにより、ベクトルｘ０、ｘ１、・・・、ｘｎが順に求められる様子を示す図、
図３は、図２の集合Ｙの部分集合をなす別の凸集合Ｗ（＝ｋＹ）を示す図、
図４は、この発明に係る符号化データの復号プログラム及び方法を説明するためのハードウエアとしての符号化データの復号装置をコンピュータにより構成した場合を示すブロック図、
図５は、図４のＲＯＭ４Ｂに格納されてＣＰＵ４Ａの制御に基づいて動作する符号化データの復号プログラムの内容を示すフローチャート、
図６は、図５に示すフローチャートに対応するもので、この発明に係る符号化データの復号装置の機能構成を示すブロック図、
図７は、この発明の実施の形態２を説明するもので、伝送されたＤＣＴ係数の量子化インデックスをＱｃで逆量子化して得られるベクトルｙｃを初期値として、集合Ｘと集合Ｙの間で凸射影を繰り返し、その共通の要素であるベクトルｘｎが求められる様子を示す図、
図８は、従来の符号化データの復号装置を示すブロック図である。
【発明を実施するための最良の形態】  以下、この発明を実施するための最良の形態を示す図面に基づいて具体的に説明する。
まず、この発明が解決しようとする問題とそれに対するアプローチについて具体的に説明する。なお、以下では、便宜上、画像データを圧縮するＪＰＥＧ符号化を対象として説明するが、この発明の適用はこれに限られるものではない。
図１は、復号された変換係数がクリップされることによって量子化インデックスの値が変化する例を模式的に示したものである。図１において、ｙｃは量子化されたＤＣＴ係数のベクトルであり、復号時に既知のベクトルである。このベクトルは、図８における逆量子化器８１の出力に得られるベクトルである。
また、Ｙはｙｃに量子化されるＤＣＴ係数のベクトルの集合を表す。ｙｃは逆ＤＣＴ変換器８２によって、時間領域の信号に変換され、次に、リミッタ８３によって一定の値の範囲にクリップされる。Ｘはそのような値の範囲にあるベクトルの集合を表す。リミッタ８３の処理は、逆ＤＣＴされたｙｃを集合Ｘに直交射影する処理とみなせる。図１において、リミッタ８３の出力ベクトルをｘ０で表した。
このベクトルは実数ベクトルのため、これを整数化して最終的な復号ベクトルｘｄを得る。ここで、クリップにより、ベクトルｘｄは集合Ｙの外に復号されている。このことは、ベクトルｘｄを再び符号化した場合に、その量子化ベクトルはｙｃに一致せず、復号によって量子化されたＤＣＴ係数の情報が失われることを意味する。
この発明は、この問題を解決するため、凸射影法を符号化ストリームの復号に利用するものである。凸射影法は、二つの集合Ｘ、Ｙが共に凸集合、つまり集合に属する二つの要素を両端の点とする線分上の点はまたその集合に属するという性質を持つ集合であるとき、任意の初期値から始めて集合Ｘと集合Ｙへの直交射影を繰り返すことによりその共通解を求める手法である。
図２は、図１の各成分がとり得る範囲が有限であるベクトルの二つの集合ＸとＹに対して、ｙｃを初期値として、集合Ｘと集合Ｙへの直交射影を繰り返すことにより、ベクトルｘ０、ｘ１、・・・、ｘｎが順に求められる様子を示している。この操作を繰り返せば、ｘｉは集合ＸとＹに共通に属するベクトルｘｎに限りなく近くなる。ここで、集合ＸとＹは、その成分が一定の範囲にある集合として定義されたから、明らかに凸集合である。したがって、共通解ｘｎは必ず求めることができる。
そこで、ｘｎに最も近い整数ベクトルをｘｄとするとき、ｘｄが集合Ｙの要素であれば（ｘｄは必ず集合Ｘの要素である）、符号化された量子化ベクトルが持っていた情報は保存される。なぜならば、このベクトルを再び符号化すれば、その量子化ベクトルはｙｃに一致するからである。
ベクトルｘｄが集合Ｙの要素でない場合には別の整数ベクトルを探索しなければならない。図３には、集合Ｙそのものでなく、その部分集合をなす別の凸集合Ｗ（＝ｋＹ）が示されている。ここで、集合Ｗは、各成分がとり得る値の範囲が有限であるベクトルの集合として定義され、例えば、集合Ｙの各成分の範囲をｋ（ｋ＜１）倍に縮小した集合などとすればよい。ｙｃを初期値とし、集合Ｘと集合Ｗの間で直交射影を繰り返せば、Ｘ∩Ｙのより深くに存在する別のベクトルｘｎが探索されることがわかる。
したがって、このベクトルを整数ベクトルに変換してｘｄとすれば、これが集合Ｙに属する確率は高くなる。以上の考察から、ｋの値を小さくしながら、凸射影によるベクトルの探索を行えば、集合Ｘと集合Ｙに共通に存在する整数ベクトルが高い確率で得られることが理解される。
実施の形態１．
図４は、この発明に係る符号化データの復号プログラム及び方法を説明するためのハードウエアとしての符号化データの復号装置をコンピュータにより構成した場合のブロック図である。図４に示す符号化データの復号装置４のハードウエア構成としては、ＣＰＵ４Ａと、処理プログラムとしての符号化データの復号プログラム及び固定データ等を記憶するＲＯＭ４Ｂと、処理データ及び入力データ等を一時記憶するＲＡＭ４Ｃと、入出力部４Ｄとを備えており、非可逆圧縮して符号化された信号を入力して、前記ＲＯＭ４Ｂに格納された符号化データの復号プログラムに従いＣＰＵ４Ａの制御に基づいて処理された結果が復号信号として出力される。
図５は、前記ＲＯＭ４Ｂに格納されてＣＰＵ４Ａの制御に基づいて動作する符号化データの復号プログラムのフローチャートを示すものである。図５において、初期化ステップＳ５１では、受信したＤＣＴ係数の量子化インデックスｙｑを逆量子化して凸射影のための初期ベクトルｙを得る。また、ｋの値を１にセットする。すなわち、次式で表される処理を行う。
ｙ←Ｑ−１（ｙｑ）
ｋ←１
ただし、Ｑ−１（・）は逆量子化の演算を表す。
このときのｙの値は、後のステップで必要なので、ｙｃとして保持しておく。
次に、射影ステップＳ５２において、ベクトルｙは、逆変換が施された後、集合Ｘへ直交射影される。ここで、集合Ｘへの直交射影は、具体的には、ｙを逆変換したベクトルの各成分をａからｂ（ａ＜ｂ）の範囲にクリップすればよく、さらに詳細に述べれば、ａより小さな成分はａに、ｂより大きな成分はｂに変更し、それ以外の成分はそのままとすればよい。ここで、画像信号が８ビットで表現される典型的な場合には、ａ＝０、ｂ＝２５５などとすればよい。この処理は、次式で表される。
ｘ←Ｐｘ（Ｔ−１（ｙ））
ただし、Ｔ−１（・）は逆変換、Ｐｘ（・）は集合Ｘへの直交射影を表す。
次に、収束判定ステップＳ５３は、この集合Ｘへの直交射影によってベクトルが変化したかどうかを確認し、変化が小さければ、凸射影が収束したとして整数化ステップＳ５５へ進み、変化が大きければ、射影ステップＳ５４へ進む。ここで、変化の大きさは例えば、
｜ｘ−Ｔ−１（ｙ）｜＜ε
などで判定すればよい。ただし、｜・｜はベクトルのユークリッドノルム、εは演算回路の精度で決まる正数である。
次に、射影ステップＳ５４は、ｘをＤＣＴ変換してＴ（ｘ）（Ｔ（・）はＤＣＴ変換を表す）を求め、これを集合ｋＹへ直交射影する。ここで、この直交射影は、Ｔ（ｘ）を量子化したときにそれがｙｃに等しくなるように、Ｔ（ｘ）の各成分を一定の範囲に修正すればよい。この修正は、射影ステップＳ５２と同様に実行することができる。射影ステップＳ５４の処理は、
ｙ←ＰｋＹ（Ｔ（ｘ））
で表される。ただし、ＰｋＹ（・）は集合ｋＹへの直交射影である。
前記収束判定ステップＳ５３で凸射影の収束が得られた場合には、整数化ステップＳ５５でｘを整数ベクトルに変換する。
次に、終了判定ステップＳ５６では、この整数ベクトルが集合Ｙに属するかどうかを確認し、属する場合にはこのベクトルを出力ベクトルとして、復号を終了する。この終了判定は、整数ベクトルをＤＣＴ変換した後、それを量子化した結果がｙｃと一致するかどうかを見ればよい。すなわち、
Ｑ（Ｔ（ｉｎｔ（ｘ）））＝ｙｃ
が成り立てば、ｘは集合Ｙの要素である。ここで、ｉｎｔ（・）は整数化、Ｑ（・）は量子化の演算子である。
上式が成り立たない場合は、縮小ステップＳ５７によってｋの値を小さくし、射影ステップＳ５８によってｘを集合ｋＹへ直交射影した後、直交射影ステップＳ５２に戻って凸射影を繰り返す。ここで、縮小ステップＳ５７の処理は１より小さい実数ｒを用いて、
ｋ←ｒｋ
などとすればよい。また、射影ステップＳ５８の処理は、射影ステップＳ５４の処理と全く同じである。
図６は、上述した図５に示す符号化データの復号プログラム及び方法を説明するフローチャートに対応するもので、この発明に係る符号化データの復号装置の機能構成を示すブロック図である。
図６に示すように、符号化データの復号装置の機能構成としては、非可逆圧縮して符号化された信号を入力し、その復号信号が存在する第１のベクトル空間において任意の実数ベクトルを一つの凸集合Ｘに直交射影する第１の射影手段６１と、第１の射影手段６１を介して凸射影が収束したかどうかを判定し、凸射影が収束したと判定された場合に、集合Ｘに属する実数ベクトルｘを求めて復号信号として出力する収束判定手段６２と、凸射影が収束していないと判定された場合に、第１のベクトル空間の任意のベクトルを第１のベクトル空間とは異なる第２のベクトル空間において一つの凸集合Ｙに直交射影した後、第１の射影手段６１に移行させて、符号化された信号を初期値として、集合Ｘと集合Ｙへの直交射影を繰り返させる第２の射影手段６３とを備えている。
さらに、この符号化データの復号装置は、収束判定手段６２により凸射影が収束したと判定された場合に、集合Ｘに属する実数ベクトルを整数ベクトルに変換する整数化手段６４と、整数ベクトルが集合Ｙに属するか否かを判定し、集合Ｙに属すると判定された場合に整数ベクトルを復号ベクトルとして出力する終了判定手段６５と、集合Ｙに属しないと判定された場合に、集合Ｙを縮小してその部分集合である新たな凸集合Ｗを生成する縮小手段６６と、変換された整数ベクトルを凸集合Ｗに直交射影した後、第１の射影手段６１に移行させて、前記符号化された信号を初期値として、集合Ｗと集合Ｘの間で直交射影を行って実数ベクトルｘを繰り返し修正させる第３の射影手段６７とを備えている。
ここで、図６に示す各機能構成は、図５に示すフローチャートにおける各ステップに対応する。すなわち、第１の射影手段６１は射影ステップＳ５２に対応し、収束判定手段６２は収束判定ステップＳ５３に対応し、第２の射影手段６３は射影ステップＳ５４に対応し、整数化手段６４は整数化ステップＳ５５に対応し、終了判定手段６５は終了判定ステップＳ５６に対応し、縮小手段６６は縮小ステップＳ５７に対応し、第３の射影手段６７は射影ステップＳ５８に対応している。
この発明の方法は、その収束性が証明されていない。すなわち、ｋを十分小さくしても終了判定ステップＳ５６において終了の判定がなされず、集合Ｘと集合Ｙに共通に存在する整数ベクトルを見つけることができない場合がある。これは、特に量子化が細かい場合に生じやすい。なぜならば、量子化が細かくなるにしたがって、集合Ｙの大きさは減少し、その結果、共通集合Ｘ∩Ｙに含まれる整数ベクトルが少なくなるためである。
そこで、この発明は、また、特に量子化が細かい場合には、符号化の量子化ベクトルとは別の精度の量子化ベクトルを定め、その量子化精度の範囲で符号化されたＤＣＴ係数が持つ情報を保持する復号方法を与える。
実施の形態２．
この発明の実施の形態２に係る符号化データの復号プログラムと方法及び装置は、図４ないし図６に示す実施の形態１と同一構成を備える。しかし、いくつかのステップで異なる処理を行う必要がある。
実施の形態２では、符号化のための量子化ベクトルとは別に符号化データの構造が保たれていることを判定するための量子化ベクトルが用いられる。この量子化ベクトルをＱｗ、符号化のための量子化ベクトルをＱｃとする。実施の形態１では、Ｑｗ＝Ｑｃ（＝Ｑ）であった。ここで、集合Ｘは実施の形態１と同様に定義される。集合Ｙは、Ｑｗで量子化したときにその結果がｙｗとなるようなＤＣＴ係数ベクトルの集合として定義される。Ｑｗは集合Ｙの中に十分な数の整数ベクトルが存在するように設定される。
図７は、伝送されたＤＣＴ係数の量子化インデックスをＱｃで逆量子化して得られるベクトルｙｃを初期値として、集合Ｘと集合Ｙの間で凸射影を繰り返し、その共通の要素であるベクトルｘｎが求められる様子を示す。ここで、ｙｃは集合Ｙの要素である。この図７で示されるように、ＱｗとＱｃが異なる実施の形態２では、Ｑｃを用いてベクトルｙの初期値を求め、Ｑｗを用いて集合Ｙを定義するようにすればよい。
以下、図５において、実施の形態１と異なるステップを具体的に説明する。初期化ステップ５１では、ｙの初期値として、Ｑｃを用いてベクトルｙの初期値を求める。すなわち、
ｙ←Ｑｃ−１（ｙｑ）
ｋ←１
を計算する。ただし、ｙｑは受信したＤＣＴ係数の量子化インデックスである。また、後の判定のために、このｙをＱｗで量子化・逆量子化したベクトル
ｙｗ←Ｑｗ−１（Ｑｗ（ｙ））
を求めておく。
射影ステップＳ５２、収束判定ステップＳ５３、射影ステップＳ５４、整数化ステップＳ５５は実施の形態１と同一である。終了判定ステップＳ５６は、量子化パラメータとしてＱｗを用いて、次式が成り立つかどうかを見ることにより終了の判定を行う。
Ｑｗ（Ｔ（ｉｎｔ（ｘ））））＝ｙｗ
ただし、ｘは射影ステップＳ５２の出力ベクトルである。
縮小ステップＳ５７、射影ステップＳ５８は実施の形態１と同様である。
以上により、実施の形態２では、復号ベクトルを再びＤＣＴ変換し、これをＱｗで量子化した結果は、もとの符号化データをＱｗで量子化した結果と一致するので、符号化データの構造が、Ｑｗの精度の範囲で復号された信号に保持される。したがって、例えば、電子透かしなどの情報を、復号データの中にＱｗの精度で残すことが可能になる。
量子化パラメータＱｗを適切にとることによって、ほとんどの場合にＸ∩Ｙに存在する整数ベクトルが得られることは、実験により示すことができる。表１は、ＪＰＥＧ符号化された二つの画像データを復号した場合に、全てのブロックでそのような解が得られたことを示す実験結果である。
ここで、Ｑｗ（量子化幅のベクトル）は全てのＤＣＴ係数に対して８とした。表１において、ｎはｋを修正した回数を示し、ｎに対応するｋの値が２列目に示されている。実験はＱｃを３通りに設定し、符号化の精度を変えて行った。
【表１】
0004323519.tif 000002
この符号化の精度はパラメータｑで表されている。ｑの値が小さいほどＱｃの値は小さく、符号化の精度は高い。ｑ＝１．０においては、Ｑｗ＝Ｑｃが成り立っている。画像１は自然画像、画像２はくさび模様のテスト画像である。これらの画像のＤＣＴブロックの総数はそれぞれ、８１９２０、２３０４である。
以上のパラメータを用いて、図１の流れ図に沿って復号を行い、終了判定ステップＳ５６においてｎ回目に終了の判定がなされるブロックの数を数えた。この数が、第３列以降に記入されている。例えば、ｑ＝１．０で符号化した画像１を復号した場合には、８１９２０ブロックのうち、８１７８７のブロックでは、ｋ＝１で復号が終了し、以下、ｋ＝０．９５０、ｋ＝０．９０３、ｋ＝０．８５７、ｋ＝０．８１５で終了したブロックの数がそれぞれ７７、４８、６、２であったことを示している。この場合には、ｋ＝０．８１５までに全てのブロックにおいて、復号が終了したことがわかる。同様に、他のパラメータについても、全てブロックに対して、ｋ＝０．６６３までに解が得られていることがわかる。
以上ではＪＰＥＧ符号化を取り上げ、ＤＣＴ変換を用いた画像符号化について説明を行ったが、この発明は、画像符号化に限られるものではなく、音声などの符号化データにも適用できる。また、集合Ｙを適切に与えることによって、ＤＣＴ変換だけでなく、ウェーブレット変換など他の符号化方式にも適用できる。さらに、静止画像の符号化だけでなく、ＭＰＥＧなどの動画像の符号化にも適用できる。
【図１】
0004323519.tif 000003
【図２】
0004323519.tif 000004
【図３】
0004323519.tif 000005
【図４】
0004323519.tif 000006
【図５】
0004323519.tif 000007
【図６】
0004323519.tif 000008
【図７】
0004323519.tif 000009
【図８】
0004323519.tif 000010