(57)【特許請求の範囲】
【請求項１】
記号ストリーム中の記号をエンコードして、その記号ストリームに対応する信号を表すのに必要なデータ量を圧縮するための方法であって、
記号ストリーム中の現在の記号を獲得するステップと、及び
現在の記号をエンコードするステップであって、係るエンコードするステップが、
現在の記号に対して局所的な記号値に関して、係る記号値によって共通に保持される特徴に基づいてモデル化値を決定するためにモデル化関数を使用し、
確率値をストリーム中の各記号と関連させる確率関数を決定するためにモデル化値を使用し、
現在の記号をエンコードする際に前記確率関数を使用することを含む、エンコードするステップとからなる、方法。
【請求項２】
前記確率関数を決定するためにモデル化値を使用することが、関数の所定のセット中において確率関数を指定するためのアドレスとしてモデル化値を用いることを含む、請求項１の方法。
【請求項３】
前記確率関数を決定するためにモデル化値を使用することが、確率関数中の変数としてモデル化値を用いることを含む、請求項１の方法。
【請求項４】
前記確率関数を決定するためにモデル化値を使用することが、暗号化値を用いることを含む、請求項１の方法。
【請求項５】
前記暗号化値が公衆キー暗号化システムにおける公衆キーである、請求項４の方法。
【請求項６】
記号ストリーム中の記号をデコードするための方法であって、
エンコードされた値のストリーム中の現在のエンコード記号を獲得するステップと、及び
現在のエンコード記号をデコードするステップであって、係るデコードするステップが、
現在のエンコード記号に対して局所的な記号値に関して、係る記号値によって共通に保持される特徴に基づいてモデル化値を決定するためにモデル化関数を使用し、
確率値をストリーム中の各記号と関連させる確率関数を決定するためにモデル化値を使用し、
現在のエンコード記号をデコードする際に前記確率関数を使用することを含む、デコードするステップとからなる方法。
【請求項７】
前記方法が、記号ストリーム中の最初の記号を受信することに応じて、
ストリーム中の記号をデコードするための最初の確率関数を生成し、及び
モデル化値が計算されるまで、前記最初の確率関数を用いてストリーム中の記号をデコードすることをさらに含む、請求項６の方法。
【請求項８】
前記最初の確率関数を生成することが、最初のモデル化値をデコードするために暗号化値を使用することを含む、請求項７の方法。
【請求項９】
前記確率関数を決定するためにモデル化値を使用することが、関数の所定のセット中において確率関数を指定するためのアドレスとしてモデル化値を用いることを含む、請求項６の方法。
【請求項１０】
前記確率関数を決定するためにモデル化値を使用することが、確率関数中の変数としてモデル化値を用いることを含む、請求項６の方法。
【請求項１１】
前記方法が、現在のエンコード記号を１より多い記号で置き換えることをさらに含む、請求項６の方法。
【請求項１２】
記号ストリーム中の記号をエンコードするためのシステムであって、
記号ストリーム中の現在の記号に対して局所的な記号値に関して、係る記号値によって共通に保持されている特徴に基づいてモデル化値を決定するためのモデル化モジュールと、
前記モデル化モジュールに結合され、モデル化値を用いて、前記記号ストリーム中の各記号と確率値を関連させる確率関数を決定するための分類モジュールと、
前記モデル化モジュールに結合され、前記記号ストリーム中における現在の記号の確率を決定するための確率マッピングシステムと、及び
前記確率マッピングシステムに結合され、現在の記号を現在の記号の確率に基づいてエンコードするためのエントロピーコーダとからなる、システム。
【請求項１３】
前記分類モジュールが、確率関数を含むテーブルをさらに含む、請求項１２のシステム。
【請求項１４】
前記モデル化モジュールが、連続する同一の記号の数をカウントし、そのカウントに基づいてモデル化値を生成するための記号カウンタをさらに含む、請求項１２のシステム。
【請求項１５】
記号ストリーム中の記号をデコードするためのシステムであって、
現在のエンコード記号に対して局所的な記号値に関して、係る記号値によって共通に保持される特徴に基づいてモデル化値を決定するためのモデル化モジュールと、
前記モデル化モジュールに結合され、モデル化値を用いて、前記記号ストリーム中の各記号と確率値を関連させる確率関数を決定するための分類モジュールと、
前記モデル化モジュールに結合され、現在のエンコード記号の確率を決定するための確率マッピングシステムと、及び
前記確率マッピングシステムに結合され、現在のエンコード記号を現在のエンコード記号の確率に基づいてデコードするためのエントロピーデコーダとからなる、システム。
【請求項１６】
前記分類モジュールが、確率関数を含むテーブルをさらに含む、請求項１５のシステム。
【請求項１７】
記号ストリーム中の現在の記号を獲得するステップと、及び
現在の記号をエンコードするステップであって、係るエンコードするステップが、
現在の記号に対して局所的な記号値に関して、係る記号値によって共通に保持される特徴に基づいてモデル化値を決定するためにモデル化関数を使用し、
確率値をストリーム中の各記号と関連させる確率関数を決定するためにモデル化値を使用し、
現在の記号をエンコードする際に前記確率関数を使用することを含む、エンコードするステップとを行うコンピュータプログラムを格納している、コンピュータで読み取り可能な記憶媒体。
【請求項１８】
記号ストリーム中の記号をエンコードして、その記号ストリームに対応する信号を表すのに必要なデータ量を圧縮するための方法であって、
記号ストリーム中の現在の記号を獲得するステップと、及び
現在の記号をエンコードするステップであって、係るエンコードするステップが、
現在の記号に対して局所的な記号値に関して、係る局所的な記号値の大きさに基づいてモデル化値を決定するためにモデル化関数を使用し、
確率値をストリーム中の各記号と関連させる連続的な確率関数を決定するためにモデル化値を使用し、
現在の記号をエンコードする際に前記確率関数を使用することを含む、エンコードするステップとからなる、方法。
【請求項１９】
前記連続的な確率関数を決定するためにモデル化値を使用することが、関数の所定のセット中において連続的な確率関数を指定するためのアドレスとしてモデル化値を用いることを含む、請求項１８の方法。
【請求項２０】
前記連続的な確率関数を決定するためにモデル化値を使用することが、連続的な確率関数中の変数としてモデル化値を用いることを含む、請求項１８の方法。
【請求項２１】
前記連続的な確率関数を決定するためにモデル化値を使用することが、暗号化値を用いることを含む、請求項１８の方法。
【請求項２２】
前記暗号化値が公衆キー暗号化システムにおける公衆キーである、請求項２１の方法。
【請求項２３】
記号ストリーム中の記号をデコードするための方法であって、
エンコードされた値のストリーム中の現在のエンコード記号を獲得するステップと、及び
現在のエンコード記号をデコードするステップであって、係るデコードするステップが、
現在のエンコード記号に対して局所的な記号値に関して、係る局所的な記号値の大きさに基づいてモデル化値を決定するためにモデル化関数を使用し、
確率値をストリーム中の各記号と関連させる連続的な確率関数を決定するためにモデル化値を使用し、
現在のエンコード記号をデコードする際に前記連続的な確率関数を使用することを含む、デコードするステップとからなる方法。
【請求項２４】
前記方法が、記号ストリーム中の最初の記号を受信することに応じて、
ストリーム中の記号をデコードするための最初の確率関数を生成し、及び
モデル化値が計算されるまで、前記最初の確率関数を用いてストリーム中の記号をデコードすることをさらに含む、請求項２３の方法。
【請求項２５】
前記最初の確率関数を生成することが、最初のモデル化値をデコードするために暗号化値を使用することを含む、請求項２４の方法。
【請求項２６】
前記連続的な確率関数を決定するためにモデル化値を使用することが、関数の所定のセット中において連続的な確率関数を指定するためのアドレスとしてモデル化値を用いることを含む、請求項２３の方法。
【請求項２７】
前記連続的な確率関数を決定するためにモデル化値を使用することが、連続的な確率関数中の変数としてモデル化値を用いることを含む、請求項２３の方法。
【請求項２８】
前記方法が、現在のエンコード記号を１より多い記号で置き換えることをさらに含む、請求項２３の方法。
【請求項２９】
記号ストリーム中の記号をエンコードするためのシステムであって、
記号ストリーム中の現在の記号に対して局所的な記号値に関して、係る局所的な記号値の大きさに基づいてモデル化値を決定するためのモデル化モジュールと、
前記モデル化モジュールに結合され、モデル化値を用いて、前記記号ストリーム中の各記号と確率値を関連させる連続的な確率関数を決定するための分類モジュールと、
前記モデル化モジュールに結合され、前記記号ストリーム中における現在の記号の確率を決定するための確率マッピングシステムと、及び
前記確率マッピングシステムに結合され、現在の記号を現在の記号の確率に基づいてエンコードするためのエントロピーコーダとからなる、システム。
【請求項３０】
前記分類モジュールが、連続した確率関数を含むテーブルをさらに含む、請求項２９のシステム。
【請求項３１】
前記モデル化モジュールが、連続する同一の記号の数をカウントし、そのカウントに基づいてモデル化値を生成するための記号カウンタをさらに含む、請求項２９のシステム。
【請求項３２】
記号ストリーム中の記号をデコードするためのシステムであって、
現在のエンコード記号に対して局所的な記号値に関して、係る局所的な記号値の大きさに基づいてモデル化値を決定するためのモデル化モジュールと、
前記モデル化モジュールに結合され、モデル化値を用いて、前記記号ストリーム中の各記号と確率値を関連させる連続的な確率関数を決定するための分類モジュールと、
前記モデル化モジュールに結合され、現在のエンコード記号の確率を決定するための確率マッピングシステムと、及び
前記確率マッピングシステムに結合され、現在のエンコード記号を現在のエンコード記号の確率に基づいてデコードするためのエントロピーデコーダとからなる、システム。
【請求項３３】
前記分類モジュールが、連続的な確率関数を含むテーブルをさらに含む、請求項３２のシステム。
【請求項３４】
記号ストリーム中の現在の記号を獲得するステップと、及び
現在の記号をエンコードするステップであって、係るエンコードするステップが、
現在の記号に対して局所的な記号値に関して、係る局所的な記号値の大きさに基づいてモデル化値を決定するためにモデル化関数を使用し、
確率値をストリーム中の各記号と関連させる連続的な確率関数を決定するためにモデル化値を使用し、
現在の記号をエンコードする際に前記確率関数を使用することを含む、エンコードするステップとを行うコンピュータプログラムを格納している、コンピュータで読み取り可能な記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は信号処理に関し、より詳しくは、信号の処理におけるエントロピーコーディングのための装置及び方法に関する。
【０００２】
【発明の背景】
従来の電子信号処理の1つの欠点は、信号を表すのに用いられるデータ量を低減させるために用いられる技術に関するものであった。信号を表すのに必要なデータ量を低減する1つの方法は、データ圧縮技術を用いることによるものである。
【０００３】
エントロピーコーディングは、信号を表すデータの量を低減させるための、1つの技術である。エントロピーコーディングは、実際の値が格納される仕方を変化させ、即ち実際の値を再定義して、信号を表すのに使用される情報の量を低減させる。例えば、イメージのコーディングに用いられる単純な型式のコーディングは、ピクセルを表す実際値に代えて、差分値を使用する。具体的には、差分コーディングにより、イメージ内の各ピクセルと、それに先行するピクセルとの間の差が保持されるものである。このコーディング型式は、イメージがすぐれて相関的である場合には、良好な圧縮をもたらす。なぜならピクセル間の差分値が小さいからである。しかしながら、差分コーディングは、相関度が高くない多くのイメージ、即ち他の型式のデータ信号を適切に圧縮することができないという点で、不具合を有するものである。
【０００４】
多くの従来のプロセッサは、記号（シンボル）ストリームを表すために、固定的な確率を用いている。固定確率コーディングの1つの型式は、可変長コーディングであり、そこにおいて値は、予想される出現頻度に基づいてコード化（符号化）される。具体的には、仮にある値が、処理すべきイメージ内に頻繁に出現することが予想される場合、その値を表すためには短いコード（例えば1）が使用される。しかし、別の値については頻繁でなく出現すると予想される場合、その値は長いコード（例えば000001）によって表される。Huffman型式のような固定確率コーディングは、値の分散が予想できるような信号については圧縮性をもたらすが、値が大きくばらつく場合にはさほど有効ではない。しかしこうした場合は屡々起きる。なぜならデータというものは、確率分布中において、急激で極端な、局所的変化を行い得るからである。
【０００５】
この型式の信号処理に対する改良として具現化されたコーディングシステムは、履歴コーディングと呼ばれるものであり、信号中の最近の記号について集められた統計を用いて信号をエンコードする。このシステムの1つの具現化形態は、信号中における記号のタリー、つまりカウントを記録するためのテーブルの使用を包含する。各々の記号について記録されたタリーは、その記号がどのようにエンコードされるべきかを決定する。こうした履歴コーディングシステムには、幾つかの欠点がある。第1に、処理のオーバヘッドは処理すべきデータの解像度の関数である。比較的大きな記号のセットは、大きな計算オーバヘッドを必要とする。また、記号のセットを大きくして信号の解像度を高めようとする場合、意味のある統計を集めるためには、より多くの近隣データが必要になる。従って、記号のセットが大きい場合、局所的な確率が急激に変化しているとすれば、サンプルサイズが大きいと、局所的な確率を迅速且つ正確に決定するのに対して実際に障害となりうる。記号のセットが大きくなるにつれて、ある特定の記号が局所的な近隣において繰り返される可能性は段々と低くなる。
【０００６】
データ分布の収集に基づいてコーディングの問題点を解決しようとする試みによって導かれたシステムは複雑であり、ハードウェア的に実施が困難であると共に、迅速な実行か、コスト的な合理性の何れかが容易には達成できず、局所的な確率については低い頻度でしか近似をもたらさない。こうしたコーディング方法はまた、転送される符号化ストリームに対し、有効な暗号化保護を実施することができない。エントロピーコーディングを暗号化と組み合わせることにより、通信の機密保護（セキュリティ）と効率の双方が改善される。
【０００７】
このように、データ量をより効率的に低減でき、またリアルタイム環境でそれを実行可能なエントロピーコーディング方式を実施する、信号処理に対するニーズが残存している。加えて、信号処理の間に暗号化技術を効果的に実行して、記号ストリームの無許可受信又は使用を防止可能なようにするニーズもある。
【０００８】
【発明の概要】
本発明は、記号ストリームに対応する信号を表すのに必要なデータ量を圧縮するために、その記号ストリーム中にある記号をエンコードするためのシステム及び方法である。現在の記号を符号化する場合、現在の記号に対して局所的な記号をサンプリングすることの関数として、モデル化モジュールによってモデル化値が計算される。分類モジュールがこのモデル化値を用いて、当該ストリームに対応する確率関数を生成し、或いは検索する。この確率関数は、現在の記号がストリーム中で次に来る記号となる確率を計算するために用いられる。現在の記号のエンコードは、現在の記号がストリーム中で次に来る記号となる確率に基づいて行われる。エンコーダは、得られた確率に基づいて、記号をエンコードするためにビットを幾らか用いる。
【０００９】
本システム及び方法はまた、モデル化値を決定し、モデル化値を確率関数へとマッピングするためにエンコーダによって実行されたのと同じプロセスを用いて、記号をデコードするために使用することができる。エンコードされた記号中のビットの特徴がデコーダによって使用されて、エンコーダにより予測された確率が決定される。デコーダにより検索（復元）された確率関数は逆ルックアップでもって用いられて、エンコードされた元の記号値が決定される。さらにまた、適切なモデル化、分類、又は確率関数を選択するために暗号化値を使用することができ、それによってストリームに対する無許可のデコードが防止される。
【００１０】
本発明のこれらの、及びその他の詳細且つ具体的な目的及び特徴は、添付図面を参照して行われる以下の詳述において、より完全に開示されるものである。
【００１１】
【好ましい実施例の説明】
本発明は、記号ストリームの形態を有する信号を圧縮し、コーディングするためのシステム及び方法である。こうした信号は暗号化コードを用いてエンコードされ、それによってストリームの無許可なデコードが防止される。本発明は、リアルタイムで転送される記号ストリーム、又は離散的なデータセット中にあるデータの双方を圧縮する。記号ストリームに対してオペレーション（演算）が加えられて、データのモデル化及び分類が可能にされ、記号ストリーム中の記号に対して適切なコーディングを行うことができるようになる。好ましくは、エントロピーコーダに対して呈示される記号ストリームは、相対的にゼロ中心とされるが、これは記号ストリームに対してウェーブレット変換のような適切な変換が行われる場合に特にそうである。
【００１２】
図1は、本発明のコーディングシステムのブロック図である。このシステムは、モデル化モジュール110と、分類モジュール120と、確率マッピングシステム130と、エントロピーコーダ140とからなる。エントロピーコーダ140は、モデル化モジュール110、分類モジュール120、及び確率マッピングシステム130により記号ストリームに対して行われたオペレーションの結果に基づいて、確率関数を受け取る。エントロピーコーダ140はまた、暗号化アルゴリズムを用いて、圧縮され暗号化された記号ストリームをもたらすことができる。
【００１３】
モデル化モジュール110は、定量化された記号ストリームを受け取る。モデル化モジュール110はこの定量化された記号を用いて、モデル化値、又はモデル化値のセットを計算し、ストリームを特徴付ける。好ましい実施例では、モデル化値は数値であり、これは最も最近の定量化された記号値に基づいて計算される。モデル化値の局所的な予測が、関数B[t]を用いて行われ、これは記号ストリーム中の点tにおける局所モデル化値を近似する。例えばこのモデル化値は次のようにして、記号ストリームの局所サンプルに対してオペレーションを行う関数を用いて決定できる。
【００１４】
モデル化値 = B[s(t-1), s(t-2) ... s(t-n)]   （式1）
この式で、時間tにおけるモデル化値は、最後のn個の記号に対してオペレーションを行う関数B[s(t)]によって近似される。モデル化モジュール110により使用可能で、モデル化値の生成に役立ち、また非常に種々多様なイメージ型式に対して良好に動作する好ましい関数は、記号により表される大きさについての短期加重平均である。次の式は、加重平均を生成するためにモデル化モジュール110が使用可能である。
【００１５】
【式１】
0003686583.tif 000002
【００１６】
式中、wsはt-1からt-nまでの時間における記号値の加重和であり、nは加重和中に含まれる記号の数である。この加重和の式は、最も最近の記号に対して最大の重み付けを与える。なぜなら最後のオブジェクトは多くの場合、ストリーム中にある次の値についての実際の確率を近似する関数について、最適な予測をもたらすからである。1つの実施例では、加重和がモデル化値115であり、分類モジュール120に渡される。或いはまた、加重和はモデル化値115を生成するために、さらに計算に付されることができる。このことは、幾つかの値についてはモデル化値115を生成するために特別な関数を使用する一方で、他の値についてはモデル化値115の生成のために異なる関数を用いることを含む。例えば、加重和が1よりも大きい場合には対数関数を使用し、一方で加重和が1よりも小さい場合には、加重和とモデル化値115の間を直接にマッピングすることができる。さらにまた、ここではモデル化値115を単一の数値として記載したが、モデル化値115はさらに、記号ストリーム中のオブジェクトに関する情報をもたらす多重値からなることができる。モデル化値115は、例えば偏差値を含んで、定量化された記号の値の間における偏差を示すことができる。モデル化値115が発生されたなら、それは分類モジュール120へと渡される。
【００１７】
分類モジュール120は、モデル化モジュール110からモデル化値115を受け取る。分類モジュール120はこのモデル化値115を用いて、記号ストリームを確率関数へと分類、即ちマッピングする。分類モジュール120は、モデル化値115に基づいて、例えばこの値を関数の係数として用いて確率関数を生成することができ、或いは単にこの値を用いて記号ストリームを確率関数へとマッピングすることができる。この値が記号ストリームを確率関数へとマッピングするために用いられる場合、新たなモデル化値115の各々を確率関数に対する調節を行うように用いて、確率関数を連続的に生成することができる。さらにまた、分類モジュール120は記号ストリームを幾つかの離散的な確率関数の1つに対してマッピングすることができる。
【００１８】
例えば、データがベル型関数を近似する場合、形状の異なる幾つかのベル型関数のセットを準備することができる。モデル化値115は、定量化された記号値が相互に変化する量に基づいて発生でき、また関数の形を定義するために使用可能である。例えば、殆どの値が似たようなものであれば、記号ストリームは背が高くて細いベル型関数へとマッピングすることができる。値の間に多くのばらつきがあれば、記号ストリームは背が低くて幅広のベル型関数へとマッピングすることができる。こうした場合、記号ストリーム中の記号値の標準偏差のような計算値を用いることにより、モデル化値115を、記号値相互の間における変動を示す尺度にすることができる。
【００１９】
確率関数、及びこの関数の形を定義する何らかのパラメータは、確率マッピングシステム130へと渡される。この確率マッピングシステム130は確率関数を用いて、記号のセット中における記号の1又はより多くのものについて、確率を決定する。あるオブジェクトの確率は、記号ストリーム中でそのオブジェクトをエンコードするために、どれだけのビットが用いられることになるかを決定する。そのオブジェクトが出現確率の低いものであった場合には、そのオブジェクトをエンコードするためにより多くのビットが使用される。他方、確率マッピングシステム130が、そのオブジェクトは非常に確率の高いものであると判定した場合には、僅かに数ビット又は1ビット未満のみを用いて、その情報は記号ストリーム上で転送される。何れの場合でも、確率関数を用いて生成された確率値は、確率マッピングシステム130からコーダ140へと渡される。
【００２０】
コーダ140は記号ストリーム中にある記号を、確率マッピングシステム130により提供された確率に基づいてエンコード又はデコードする。コーダ140は、入力される記号ストリームを確率又は確率関数に基づいて符号化可能な、何らかのパラメータ化されたエンコーダでよい。コーダ140は記号ストリームを受け取り、ストリーム中の記号をそれ相応にエンコードし又はデコードする。
【００２１】
さて図2を参照すると、本発明により記号ストリームをエンコードするエンコード装置の概略が示されている。このエンコード装置はモデル化システム210と、分類化器220と、確率マップ230と、エントロピーコーダ240と、制御装置285とからなる。記号ストリームはモデル化システム210により受け取られ、定量化された記号値が用いられて、加重和が生成される。加重和は、モデル化値115を生成するために使用可能な関数の一例としてのみ用いられており、代替的な、或いは付加的な関数を用いることが可能である。この例では、2を底とする加重和の対数を用いてさらに計算が行われ、分類化器220に渡されるモデル化値115が生成されている。
【００２２】
モデル化システム210はまた、ゼロカウントエンコーダ260を含んでいる。このゼロカウントエンコーダ260は、ゼロのストリングがあるかどうかにつき、ストリームを監視する。例えば加重和の計算値がゼロに等しい場合など、このエンコーダがトリガ（付勢）される事象が生じた場合、ゼロカウントエンコーダ260はゼロの数を辿り始める。トリガ事象の後に通過する最初のゼロは、ゼロカウントエンコーダ260にモデル化値115を転送させ、それによりゼロカウントエンコーダ260がモデル化値115と加重和関数250の両者を提供することを示す。次の記号もまたゼロの場合、ゼロカウントエンコーダ260はモデル化値115を転送する前に、ストリーム中の次の記号の受信を待つ。その記号がゼロではない場合は、加重和の対数を用いて発生されたモデル化値115が再度用いられて、ストリームをエンコードする。しかしながら、次の記号もゼロの場合には、ゼロカウントエンコーダ260は-1のモデル化値115を転送する。このモデル化値115は、ゼロ値が2つ通過したことを示す。ゼロのストリームが続くならば、ゼロカウントエンコーダ260はモデル化値115を転送するに先立って、徐々に大きくなるゼロのセットのカウントを継続する。例えば、ストリーム中の2つのゼロというストリングに基づいて-1というモデル化値115が転送された後、ゼロカウントエンコーダ260は、4つのゼロが通過するまでは、-2という次のモデル化値115を転送しない。このプロセスが継続すると、次のモデル化値115の転送よりも前にセット中にあるゼロの数は2の累乗で増大する。次のゼロのセットが完成する前にストリーム中に非ゼロ値がある場合には、加重和の計算に従って計算されたモデル化値115が用いられる。
【００２３】
分類化器220は、モデル化システム210により渡されたモデル化値115（単数又は複数）を用いて、確率関数を発生又は選択する。分類化器220は、図1に関して記述した分類モジュール120と確率マッピングシステム130の機能を営む。この実施例において分類化器220は、格納されている確率関数の1つをモデル化値115に基づいて検索し、確率マップ230をエントロピーコーダのコードルックアップテーブル275へと転送する。現在の記号の確率は、コードルックアップテーブル275から検索され、コードアセンブラ280に転送される。コードアセンブラ280はこの確率、及び記号のエンコードに用いられた他のパラメータを受け取り、この記号をエンコードストリーム150に出力する。
【００２４】
ゼロのストリングをエンコードするために、ゼロ検出回路265もまた、エントロピーコーダ240に設けられている。ゼロカウントエンコーダ260がモデル化値115を分類化器220に転送したとき、エントロピーコーダ240はそのモデル化値115に対応して、ゼロのセットを単一のエンコード記号として符号化する。モデル化値115は、エンコード記号により表された、セット中のゼロの数を決定する。例えば-3というモデル化値115は、ストリーム150中の単一のエンコードされたゼロにより8つのゼロ（23）が表されることを示す。かくして、ゼロ検出回路265は、そのセットに対応するゼロをカウントして除去し、完全なセットの各々ごとに、単一のエンコードされていないゼロをコードアセンブラへと渡し、エンコードさせる。コードアセンブラ280によりエンコードされた単一のゼロは、ストリーム150中に挿入されて、最後のモデル化値115に対応するセット中にある全てのゼロを表す。全ての非ゼロ値、或いは通常通りに符号化されたゼロ値は、ゼロ検出回路265からは無視される。
【００２５】
このエンコード装置はまた、制御装置285を含む。この制御装置285は、モデル化システム210、分類化器220、及びエンコーダ240の間における転送を監視して、信号が適切な時間的位相関係にあることを保証する。図示されたエンコード装置は、本発明の1つの実施例であるが、システム中に含まれる具体的な構成部品、及び部品の各々により使用される機能は、実施例ごとに変化しうるものである。
【００２６】
さて図3を参照すると、本発明に従って記号ストリームをデコードする装置の概略が示されている。このデコード装置は、モデル化システム210と、分類化器220と、確率マップ230と、エントロピーデコーダ340とからなる。エンコードストリーム150は最初に、エントロピーデコーダ340により受信される。このデコーダ340は確率マップ230を検索し、エンコードされた記号の特徴を用いて、その記号をデコードする。エンコードのプロセスには、記号の確率を予測し、その確率に基づいてその記号をエンコードすることが含まれていた。デコードのプロセスは、このプロセスを逆に実行する。データのエンコードに用いられたビットの特徴がデコーダ340をイネーブルして、そのデータのエンコードに用いられた確率が計算される。デコーダ340は確率マップ230を用いて、計算された確率を元の記号と対応させる。元の記号は、得られるデコードストリーム105中において、符号化された記号を置き換える。
【００２７】
ストリーム150が最初にデコーダ340により受信された場合、分類化器220とモデル化システム210は、受信中のストリーム150に対応する確率マップ230を生成するのに十分なだけの値を受信していない。ストリーム150中にある最初の幾つかの記号をデコードするためには、デフォルトの確率マップ230又は関数250を使用することができる。これにより、エンコーダ240とデコーダ340が、同じ記号については同じ確率を計算することが保証される。ストリーミングビデオといった多くの応用例において、記号ストリームは、使用される関数を示す特別な記号を格納するのに使用可能な開始フレームを有する。例えば、ゼロの如き初期化記号を用いてストリームを開始させることができ、またデコーダは、エンコードされた値がゼロであることを知っている。従ってそのデコーダは、ゼロのエンコードに用いられたビットの数を用いて、確率マップ230の生成に用いられる関数を示すことができる。このデコード方式はまた、集束するエラー値をももたらし得るものであり、正しくない確率マップを用いてデコードされた値は時間の経過と共に、適切な確率マップ230を生成するモデル化値115を生成するようになる。
【００２８】
さらにまた、最初の確率関数の選択は、暗号化値に基づくものであってもよい。こうした暗号化値は、その値を計算するために異なる変数を用いる、どのような暗号化手段によって発生してもよい。例えばソフトウェアプログラムのシリアル番号とユーザ名を、公衆キー暗号化システム中で用いることができる。公衆キー暗号化システムは各人に対し、公衆キーと個人キーの2つのキーの取得をもたらす。これらのキーは各人が、メッセージを暗号化（ロック）し、或いはエンコードされたメッセージを解読（アンロック）することを許容する。各人の公衆キーは公開され、個人キーは秘密裏に保たれる。メッセージは意図する受取人の公衆キーを用いて暗号化され、シリアル番号とユーザ名といった変数を用いて発生される個人キーを用いた場合にのみ解読可能である。値のデコードに用いられる確率関数の決定は、記号の適切な解読に基づくものであるから、この方法は記号ストリームの無許可な受信を防止するのに用いることができる。公衆キー暗号化は暗号化方法の一例として用いられたものであり、他の暗号化方法も使用可能である。
【００２９】
最初の確率関数が検索され、対応する確率マップ230がデコーダ340に転送されたならば、エンコードされた記号ストリーム150は、それがエンコードされた場合と同様のプロセスを用いてデコードされる。デコードされた記号の定量化された値がモデル化システム210に転送され、エンコード側と同様の仕方でもってモデル化値115が発生される。モデル化値115は次いで分類化器220に渡され、対応する確率関数が用いられて、確率マップ230が生成される。データのエンコードに用いられたビットの特徴によりデコーダ340がイネーブルされ、エンコードされた場合にその記号について計算された確率が計算される。確率マップ230はデコーダにより受信され、コードルックアップテーブル275に入れられる。次いでコードルックアップテーブル275はコード逆アセンブラ380により使用されて、計算された確率と元の記号とが対応付けされる。結果として得られたデコード値は、デコード記号ストリーム105として転送される。付加的に、ゼロカウント機構270が設けられて、ゼロカウントシステムを用いてエンコードされたゼロをデコードする。モデル化システム210により受信されるデコード記号ストリーム105中にトリガ事象が生じた場合、値はコード逆アセンブラ380に転送される。ゼロカウント機構270はコード逆アセンブラ380に対して、ストリーム105中に入れられるゼロの数を示すゼロカウントを提供する。
【００３０】
次に図4を参照すると、確率関数のサンプル（例証的）セットが示されている。分類モジュール120は、受け取ったモデル化値115に基づいてこれらの関数を生成することができ、また特定のモデル化値115に対してマッピングされた関数を格納することができる。モデル化値115はストリームを特徴付け、対応する最適な関数の識別を可能にする。
【００３１】
図示したとろから例証されるように、関数410, 420, 430は、同じ定量化値について異なる確率を反映したものである。例えば、モデル化値115が記号ストリームを関数420に対してマッピングを行う場合、ゼロを獲得する確率は約0.01であると計算される。より多くのゼロが受信されるならば、モデル化値115は低下して、新たなモデル化値115により関数410がマッピングされて、ストリーム中における次の記号がゼロ記号である確率の増大（約0.02）が示される。その結果、ストリーム中においてゼロをエンコードするのに用いられるビット数はより少なくなり、コーディングの効率は増大する。
【００３２】
本発明のデータコーディング方法を例示するフローチャートが図5に示されている。この方法は、記号ストリームがモデル化モジュール110により受信されたところから始まる。モデル化モジュール110は、現在の記号を受信505する。モデル化モジュール110は定量化値を用いて、モデル化値115を計算510する。加重平均関数のような関数が用いられて、モデル化値115が計算される。使用される関数の型式、及び使用される関数のパラメータは、エンコードされるデータの特徴に応じて変化しうる。例えば、その関数により加重平均が計算されるならば、加重平均を計算するのに用いられる要素の数を制御するパラメータは、記号ストリームに基づいて変化しうる。記号ストリーム中に時折スパイクがあるならば、加重平均はより多くの値を用いて計算することができ、また安定した傾向のあるストリームについて加重平均を計算する場合は、値はより少なくても構わない。加重平均を使用する場合、計算されたモデル化値115は単一の数値であるが、他の関数が記号ストリームをモデル化する1又はより多くの値を生成する場合もある。加重平均はさらに、モデル化値115の計算という別の機能でもって使用することもできる。
【００３３】
好ましい実施例では、モデル化値115は、定量化された記号の加重平均の2を底とする対数を取り、この対数値を丸めて最も近い整数値とすることによって計算510される。こうして計算されたモデル化値115は、分類モジュール120に転送される。しかしながら、ストリームの具体的な特徴に基づいてモデル化値115を計算するために、他の関数をも使用することができる。これは特に、所定範囲の値についてはモデル化関数を使用できない場合に当てはまる。例えば、加重平均がゼロに等しい場合、対数関数は何の情報ももたらさない。こうした条件の下では、モデル化モジュール110は付加的なモデル化関数を提供して、別のモデル化値115を発生させることができる。例えば、修正モデル化値115として第2のモデル化値115を、ストリーム中にあるゼロの数を用いて計算できる。加重平均がゼロに等しく、次の記号もまたゼロである場合、モデル化モジュール110はモデル化値115又はゼロを分類モジュール120に渡すことができる。代替的な関数を用いて発生されたモデル化値115は、加重平均がゼロである場合に限って使用可能とされる。このことは、圧縮において多大の融通性をもたらす。なぜなら記号ストリームの特定の部分は、改良されたモデル化値115関数で予測可能な仕方でもって変化しうるからである。モデル化関数相互の間で行ったり来たりするプロセスのさらなる詳細は、図6のテーブルを参照して説明する。
【００３４】
分類モジュール120は、モデル化値を確率関数に対してマッピング515する。この確率関数は、モデル化値を累乗関数の底として用いるといった風にしてモデル化値を用いて生成可能であり、また分類モジュール120に格納されている関数のセットから確率関数を選択するために使用することができる。例えば、分類モジュール120は記号ストリームの異なる型式を反映する16個の選択された関数を格納するために使用でき、またモデル化値115はこれらの16個の確率関数の中から選択を行うために使用できる。代替的に、この関数はモデル化値115が変化するにつれて連続的に調節される関数であってもよい。選択された確率関数又は関数は、確率マッピングシステム130に対して転送520される。
【００３５】
確率マッピングシステム130は、確率関数を受信する。ストリームがエンコード530されている場合には、確率マッピングシステム130は、現在の記号がストリーム中の次の記号である確率を含めて、確率マップ230を計算525する。これらの確率は、コードアセンブラ280による検索のためにこれらの確率を格納する、コードルックアップテーブル275に提供される。現在の記号の確率は、記号のエンコードに使用されるビットの数を決定する。この記号は適切な確率に対してマッピング550される。この記号は、現在の記号がストリーム中の次の記号である確率が、記号セット中の他の記号である確率に対して非常に高い場合には、僅かに数ビットのみを用いてエンコード555される。現在の記号のこの相対的な確率が減少するにつれて、この記号をエンコードするために使用されるビットは多くなる。エンコードされた記号は次いで、エンコードされた記号ストリーム150として転送560される。
【００３６】
ストリームがデコード530されている場合には、確率マップはコードルックアップテーブル275に渡される。これは、エンコードされた記号中にあるビット数を、その記号をエンコードするためにコーダにより用いられた確率に対してマッピング535する手段をもたらす。例えば、その記号をエンコードするために1ビットしか用いられていないとすれば、エンコード側で計算された確率は非常に高かったことになる。例えば1又は0の何れが用いられたかといった、そのビットの特徴がまた使用されて、確率はさらに改善される。例えば単一のゼロが用いられている場合、その記号は確率関数中で最も高い確率に対して対応させられる。
【００３７】
デコーダは次いでこれらの確率を、適切な定量化された記号に対してマッピング540し、これらの記号はデコード記号ストリーム中において、エンコードされた記号を置き換える。エンコード側では、モデル化値115及び対応する確率関数に基づいて、各々の記号にはある確率が割り当てられている。今度はこのプロセスが逆に行われる。例えば、数「N」が記号であって、確率関数によればストリーム中の次の記号である確率が最も高いものである場合、コーダは記号を「N」として、最小数のビットでもってデコードする。このプロセスは繰り返され、新たなモデル化値115と、対応する確率関数とが、各々の記号を動的にデコードするために用いられる。デコードされた記号は次いで、ストリーム内へと転送545される。
【００３８】
以下の説明は、本方法によりコード化される記号ストリームの一例を示している。例示の目的で、モデル化値115及び他の関連するファクタに対応する確率関数により与えられるとろこにより、記号ストリーム中の次の記号としてゼロを取得する確率が図6のテーブルに示されているものとする。この例示的な実施例において、モデル化モジュール110は、ストリーム中の最後の4つの記号の加重平均について、2を底とする調節された対数を計算することにより、モデル化値115を決定する。計算された値は最も近い整数値に丸められ、このモデル化値115は分類モジュール120に渡される。加えて、この例では分類モジュール120は、モデル化値115の各々に対してマッピングされた確率関数の選択肢を格納している。最後に、記号セットのサイズとしては4096が用いられ、分類モジュール120には24個の関数が格納される。この例においてこれらのパラメータを使用することは、データ転送に対する本発明の実際的な適用を例示することを意図しているが、特許請求の範囲を限定することは意図していない。モデル化値115の計算、確率関数、及び記号のセットについてはどのような異なる数を用いて、本発明を具体化することも可能である。
【００３９】
現在の記号に先行するストリーム中の最後の4つの記号が非常に高い記号値を与えるものであり、その結果加重平均が768であったと仮定する。この加重平均についての2を底とする調節された対数値は10に等しく、このモデル化値115は分類モジュール120に渡される。10に等しいモデル化値115に対応する確率関数が分類モジュール120によって検索され、確率マッピングシステム130に渡される。確率マッピングシステム130により与えられる確率はエンコーダによって用いられ、記号がエンコードされる。さらに、転送中の現在の記号がゼロであると仮定する。テーブルを参照すると、最初の記号がゼロに等しい確率は1535分の1であると計算される。ゼロは非常に期待できないから、このゼロは約12ビットを用いてエンコードされる。これらの12ビットはエントロピーデコーダ240により、符号化された値のストリーム150に与えられる。
【００４０】
さて、次の記号（2番目の記号）もまたゼロであると仮定する。これはモデル化値115の低減につながるが、これは最初の記号よりも前の記号の値に依存して、恐らくは9への低減となる。次いで、9に等しいモデル化値115に対応する確率分布が使用されて、この第2の記号がエンコードされる。この第2の記号は最初の記号と同様にしてエンコードされ、コーダ240により、符号化された値のストリーム150に与えられる。しかしながらこの場合には、この記号のエンコードには11ビットしか必要としない。なぜなら確率分布により、ゼロに関してより大きな可能性が示されるからである。低い値（ゼロの如き）に遭遇するにつれて、分類モジュール120は、こうした値についてより可能性が大きいことを示す確率関数を渡し、エンコード効率は増大する。加えて、特にこの場合のように、4つといった如く限られた数の値を用いた加重和が使用される場合には、適当な確率分布はストリームに適切なものへと、迅速に遷移する。この方法は、ゼロカウントに従ってモデル化値115を計算する、代替関数の使用によって補強される。例えば、4つの連続するゼロに遭遇した場合、5つ目の記号については、ゼロのモデル化値115に対応する関数を使用することができる。次の例は、異なる型式のストリームについてモデル化値115を計算するために用いられる、2つの関数の間における遷移を例示する。例示の目的上、ストリームが平均値でゼロを有する場合に、代替的な関数が実施されると仮定する。
【００４１】
先の実施例において用いたと同じパラメータを引き続き使用して、先行する値が高いという履歴の故に、10というモデル化値115に対応する関数を使用した後に、後続の4つの記号（記号1から4）がゼロであったとする。これらの記号は、計算されたモデル化値115に対してマッピングされる確率関数に従ってエンコードされ、エントロピーコーダ240により生成される符号化された値のストリーム150に与えられる。5番目の記号については、加重和はゼロに等しくなり、モデル化値115がゼロに等しい確率分布が使用される。
【００４２】
しかしながら、モデル化値115がゼロの場合には、代替関数が使用されて、付加的なモデル化値115が与えられる。この場合、ゼロカウント法が好ましく実施される。5番目の記号がゼロに等しくない場合、この記号は先行するモデル化値115に対応する分布を用いて、前述した標準的なエンコードプロセスを使用してエンコードされる。しかしながら、5番目の記号がゼロに等しいと仮定してみる。このゼロは、新たなモデル化値115を生成するため直ちに使用されるものではない。上記に説明したように、この記号をエンコードするのに使用される確率関数は、後続の記号の値に依存する。6番目の記号もまたゼロに等しいと仮定する。2つの連続するゼロに遭遇することになるから、新たなモデル化値115として-1が計算される。モデル化値115が-1の場合には、2つの（21）ゼロに等価なものとして、1つのゼロがエンコーダにより、符号化された値のストリーム150に挿入される。かくして単一の符号化されたゼロが、5番目と6番目の記号に対応する2つのゼロを実際に表すことになる。
【００４３】
ストリーム105中にさらに4つのゼロ（記号7-10について）が渡される場合、-2というモデル化値115が計算され、これら4つのゼロのセットは符号化された値のストリームにおいて、単一のゼロによって表されることになる。かくしてコーダ240は、記号5-10について実際の値「000000」に代えて、符号化された値のストリーム150中に「00」を挿入することになる。-3というモデル化値115に対応するゼロのセットが完成するには、さらに8個のゼロ（記号11-18について）がストリーム105中に渡されねばならない。この時点において、8つの連続するゼロは1つのゼロとして格納されることになる。かくして「000」は、記号5-18についての実際の値「00000000000000」に関する符号化された値のストリームでありうる。このプロセスは、次のモデル化値115が計算される迄に、セット中に必要とされるゼロの数を倍々にすることによって継続される。
【００４４】
しかしここで、10に等しいモデル化値115を有する初期状態の後に、記号1-14のみがゼロであり、記号15が非ゼロであったと仮定してみる。符号化された値のストリーム150は、記号1-4のゼロについての適切なコーディングと、記号5-10についての「00」を含むことになる。8つのゼロ（11-18）に対応することになる、連続する3つ目のゼロは、符号化された値のストリーム150中には含まれない。そうではなしに、いったん非ゼロ値の記号15に遭遇したならば、それは在来のコーディング方式（bは-3に等しいという関数）を用いてエンコードされ、符号化された値のストリーム150に挿入される。付加的に、記号11-14についての4つのゼロはコード語によって表され、次のゼロのセットが符号化された値のストリーム150中に直接に挿入されることが示される。
【００４５】
（ECn）という指定が、n番目の記号についての符号化された値（例えば最初の記号については、上述のようにEC1は11ビットの情報である）と仮定する。結果として得られる符号化された値の例示的なストリーム150は順に、（EC1）,（EC2）,（EC3）,（EC4）,0,0,（EC15）,（コード語）となる。代替的に、（コード語）は、符号化された値のストリーム中で先行する（V15）ことができる。この例におけるゼロの連続は、符号化された値のストリーム150中でコンパクトに与えられることになる。例えば符号化された値のストリーム150中の「00000」は、元の記号のストリーム105からの44個のゼロを表すことになる。実際、モデル化値115がマイナス12に等しい場合には、符号化された値のストリーム150中における単一のゼロは、元の記号ストリーム105中における4096個（212）のゼロを表すことになる。4096というのは単に例示的な限界であって、本発明はより大きな連続するゼロ表示についても実施可能なものである。付加的に、ゼロは方法を例証するために使用したものであり、ゼロでない値を中心とする他の方式も実施可能である。さらにまた、好ましい実施例では2の階乗を実施したが、本方法は2を底としなければならないものではない。
【図面の簡単な説明】
【図１】  本発明のコーディングシステムのブロック図である。
【図２】  本発明により記号ストリームをエンコードする、エンコード装置の概略図である。
【図３】  本発明により記号ストリームをデコードする、デコード装置の概略図である。
【図４】  記号ストリームのエンコード及びデコードに用いられる確率関数のサンプルセットである。
【図５】  本発明のデータコーディング方法を例示するフローチャートである。
【図６】  記号ストリームをエンコードするプロセスを例示する、サンプル値によるテーブルである。
【図１】
0003686583.tif 000003
【図２】
0003686583.tif 000004
【図３】
0003686583.tif 000005
【図４】
0003686583.tif 000006
【図５】
0003686583.tif 000007
【図６】
0003686583.tif 000008