(57)【要約】【課題】可能な限り少ない数のビットを用いて、変換係数の値および変換データ・セットにおける変換係数の位置を送信または記憶することにより、効率的な圧縮を行う。【解決手段】例えばイメージやオーディオ信号などのデータ圧縮の方法。ウェーブレット変換やＤＣＴなどの変換を用いてデータをエンコードするステップと、最大重みビット及び／又はビット値により変換係数をグループ化するステップと、それらをグループ毎に送信するステップとを備える。マッチング・パースイットのように、変換にコードブックを用いる場合、係数はコードブック値により更にグループ化される。一実施形態では、方法は、データが、係数の位置およびグループにより完全に記述されることを可能にし、何れの係数値の情報も記憶や送信する必要がないようにする。【選択図】図２
2011045140.tif 000002
【特許請求の範囲】
【請求項１】
データ圧縮の方法であって、データに変換を適用して複数の変換係数を導き出すステップと、前記係数を複数のグループに分割するステップと、前記グループを圧縮データとして順に記憶または送信するステップとを備える方法。
【請求項２】
請求項１に記載のデータ圧縮の方法であって、前記係数は係数値の特徴に従ってグループ化される、方法。
【請求項３】
請求項２に記載のデータ圧縮の方法であって、前記係数はそれらの第１重みビットに従ってグループ化される、方法。
【請求項４】
請求項２に記載のデータ圧縮の方法であって、前記係数はそれらのビット値に従ってグループ化される、方法。
【請求項５】
請求項２に記載のデータ圧縮の方法であって、前記係数は、まだ記憶も送信もされていない次のビットの値に従ってグループ化される、方法。
【請求項６】
請求項２に記載のデータ圧縮の方法であって、前記係数は符号によりグループ化される、方法。
【請求項７】
請求項２に記載のデータ圧縮の方法であって、前記係数は振幅によりグループ化される、方法。
【請求項８】
請求項１に記載のデータ圧縮の方法であって、それぞれの係数は個々の副情報と関連しており、前記係数は前記副情報の特徴に従ってグループ化される、方法。
【請求項９】
請求項１ないし８の何れかに記載のデータ圧縮の方法であって、前記変換はコードブックに頼るものであり、前記係数はコードブック参照からなるか又はコードブック参照を含み、前記係数はそれらの個々のコードブック参照に従ってグループ化される、方法。
【請求項１０】
データ圧縮の方法であって、請求項２ないし９の何れか２つ以上の請求項に記載された複数のグループ化により、係数が任意の所望される順にグループ化される方法。
【請求項１１】
請求項１に記載のデータ圧縮の方法であって、所与の係数についてのエンコードされる全ての情報は、その係数が置かれるグループから決定され得る、方法。
【請求項１２】
請求項１に記載のデータ圧縮の方法であって、それぞれの係数についての位置情報が記憶または送信されるものであり、前記係数が置かれるグループのアイデンティフィケーション以外の値関連の情報は記憶または送信されない、方法。
【請求項１３】
請求項１に記載のデータ圧縮の方法であって、それぞれの係数についての位置情報が、前記係数が置かれるグループから決定され得る値関連の情報以外の全ての残りの値関連の情報と共に、記憶または送信される、方法。
【請求項１４】
請求項１ないし１２の何れかに記載のデータ圧縮の方法であって、前記グループは記憶または送信される前にランレングス・エンコードされる、方法。
【請求項１５】
請求項１に記載のデータ圧縮の方法であって、前記変換はウェーブレット変換である、方法。
【請求項１６】
請求項１に記載のデータ圧縮の方法であって、前記変換は高速フーリエ変換である、方法。
【請求項１７】
請求項１に記載のデータ圧縮の方法であって、前記変換は離散コサイン変換である、方法。
【請求項１８】
請求項１に記載のデータ圧縮の方法であって、前記変換は重複直交変換である、方法。
【請求項１９】
請求項１に記載のデータ圧縮の方法であって、前記データはスチル・イメージまたはビデオを表す、方法。
【請求項２０】
請求項１に記載のデータ圧縮の方法であって、前記データはオーディオ・ストリームを表す、方法。
【請求項２１】
請求項１に記載のデータ圧縮の方法であって、前記データはテキストを表す、方法。
【請求項２２】
請求項１ないし２１の何れかに記載の方法を実施するコンピュータ・プログラム。
【請求項２３】
請求項２２に記載のコンピュータ・プログラムを担持する機械読取可能なデータ担体。
【請求項２４】
請求項２２に記載のコンピュータ・プログラムを表すビット・ストリーム。
【請求項２５】
請求項１ないし２１の何れかに記載の方法を実行するコーダ。
【請求項２６】
請求項２５に記載のコーダを含むコーデック。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ圧縮の方法および装置に関し、特にスチル・イメージやビデオ・イメージおよび／またはオーディオ・データの圧縮のための方法および装置に関するが、これらに専用というわけではない。
【背景技術】
【０００２】
イメージ・データおよびオーディオ・データの圧縮のための多数の既知の手法がある。その例としては、スチル画像のエンコードおよびデコードのためのジョイント・ピクチャ・エキスパート・グループ（ＪＰＥＧ）・アルゴリズムや、ビデオ・データのエンコードおよびデコードのためのムービング・ピクチャ・エキスパート・グループ（ＭＰＥＧ）・アルゴリズムなどがある。これらおよび他の多くのエンコードおよびデコード・システムは、離散コサイン変換（Discrete Cosine Transform）（ＤＣＴ）などのような空間変換（spatial transform）を使用して、元のイメージ・データを、圧縮された形にする。他のアルゴリズムは、代替の変換、例えばウェーブレット変換（Wavelet Transform）などを用いる。
【０００３】
典型的には、選択された変換からの出力は一連の変換係数であり、それは、全体として、オリジナル・データ（元のデータ）のエンコードされ圧縮された形を定義する。データを、例えばインターネットや低帯域ワイヤレス接続などのような通信媒体を通じて転送する必要がある場合、係数はバイナリ形態（ビット）へと変換され、そのバイナリ形態にされた係数が、任意の好適な通信プロトコルに従って転送されたり、任意の適切な形で（例えば、ディスクやメモリに）記憶される。
【０００４】
「埋め込み式（embedded）」システム（量子化器（quantizer）を用いる）では、変換係数は、レイヤーズ・オブ・シグニフィカンス（layers of significance、重みのあるレイヤ）（ビット・プレーン（bit planes））の順に並べられ、最大重みビット（モースト・シグニフィカント・ビット、most significant bits）が通常は最初に転送される。このような「埋め込み式」コード化手法では、受信側は、最初に低解像度イメージ受信し、伝送が進行するにつれてイメージは徐々に精密にされて高解像度になる。この手法は、受信側が受信しているイメージが、受信側の必要性に見合う十分な解像度となった任意の時に、受信側が伝送を終了できるようにする。
【０００５】
殆どの埋め込み式システムは、重み切り替え（significance-switching、シグニフィカンス・スイッチング）の概念を用いる。即ち、システムは、それぞれの係数の最大重みビットの位置をデコーダへ助言するための或る機構を提供する。シグニフィカンス・スイッチングなしでは、第１重みビット（ファースト・シグニフィカント・ビット、first significant bit）がまだ到達していない係数に関する重みのないビット（インシグニフィカント・ビット、insignificant bits）を反復して送ることになり、かなりの量の使用可能な帯域が無駄に使われる。これは、正の係数については、第１重みビット（即ち、１）がまだ到達していないときに零（０）を反復して送ることを意味する。シャピロ（Shapiro）のシステムなどのような幾つかのシステムでは、これを、一度に１つのビット・プレーンをスキャンすることにより行う。IEEE Transactions on Signal Processing, 41 (12)、3445乃至3462ページ、１９９３年１２月のシャピロを参照されたい（更には、US-A-5321776およびUS-A-5315670に記載されている)。他のシステムは、デコーダへ最大重みビット位置を明確に送ることにより、最大重みビットの位置を通知する。例えば文献WO-A-99/08449およびWO-A-98/37700に説明されているシステムのような幾つかのシステムは、ビット伝送効率を改善するためにマスキング技術を用いる。
【０００６】
デジタル・システムにおいて負の数を表すための異なる表記のシステムがあり、その最も重要なことは、「符号および大きさ（sign and magnitude）の表記」と「２の補数（twos complement）の表記」とである。情報は、多くの場合に２の補数の表記でコンピュータに記憶されるが、圧縮アルゴリズムを記述するために、多くの場合に符号および大きさの表記が使用される。本発明の説明は、符号および大きさの表記に関連して行われ、この場合において、正の数の第１重みビット（first significant bit）（ＦＳＢ）およびその負のバージョンは、データ・ワードにおいて同じ位置にある。
【０００７】
上記の全ての技術では、それぞれの個別の係数の第１重みビットは最初に送られ、それに続いて、より重みの低い連続するビットが、ビット・プレーン毎に、送られる。特定のカットオフ・ビット・プレーンに到達すると、システムは、係数を更に精細化する価値はないと考慮し、その結果として、カットオフ・ビット・プレーンの下に存在し得る更なるビットは送られない。
【０００８】
最近、ＦＳＢに続いて一定の数のビットが送られた後にそれ以上送る価値はない、ということが提案されている（「Proceedings of the IEEE International Conference on Image Processing 2000、バンクーバ」のモンロ（Monro）その他を参照されたい。これは更にＷＯ０２／１３５３８に説明されている。）。これは、ＦＳＢに続くビット・パターンの数が限られていることを示唆する。例えば、特定の係数のＦＳＢに２つの更なるビットが続くと定められることが知られている場合、そのパターンは４つの組み合わせのみ、即ち、１１、１０、０１または００（大きさにおける降順で示す）である。
【発明の概要】
【発明が解決しようとする課題】
【０００９】
これらの全ての技術、およびこれらと同様の他の技術の目的は、可能な限り少ない数のビットを用いて、変換係数の値および変換データ・セットにおけめ変換係数の位置を送信または記憶することにより、効率的な圧縮を行うことである。データを送るために必要な理論的なビット数（エントロピ）を最小化するために、受渡機構のための係数のオーダーリング（順序付け）およびパッケージング（パッケージ化）の設計を支えるための多大な工夫がなされてきた。標準的な手法は、位置情報を最小数のビットで表すことを目的としており、それにより、データの値を定めるビットに使用できる使用可能な帯域を可能な限り多くすることを目的としている。
【課題を解決するための手段】
【００１０】
本発明では、データの値ではなく位置について注意を注ぐことにより、上記の手法は完全に放棄され、エントロピは改善される。極論的には、本発明は、データ・セットを完全に位置情報で記述し、値の情報を全く送らないようにすることを企図する。
【００１１】
本発明の第１の態様によるとデータ圧縮の方法が提供され、この方法は、データに変換を適用して複数の変換係数を導き出すステップと、それらの係数を複数のグループに分割するステップと、それらのグループを圧縮データとして順に記憶または送信するステップとを備える。これらのグループは好適には同じ確率ではない。
【００１２】
本発明は、更に、この方法を実施するコンピュータ・プログラム、およびそのようなコンピュータ・プログラムを担持する機械読取可能データ担体（例えば、ＣＤ）、およびそのようなコンピュータ・プログラムを表すビット・ストリーム（例えば、インターネットを介してダウンロードされるもの）が、その範囲にはいる。本発明は、更に、この方法を実施するコーダ（coder）、およびそのようなコーダを含むコーデックが、その範囲にはいる。
【００１３】
係数値の特徴に従って（または何らかの副情報に従って）係数を全てまたは部分的にグループ化し、値に関連する情報ではなく位置情報を明確に送ることを強調することにより、当出願人は、効率が更に改善されることを発見した。これは、驚くべきことに、グループの数が多い場合（例えば、係数の数と同じ場合）にも適用される。可能なグループの数よりもデータ値の数が少ない場合、幾つかのグループは空にされ、そして、効率は、送信のためにグループをランレングス符号化することにより、更に改善される。
【００１４】
グループへと分割することによりエントロピが低減されるのは、データの非定常性（non-stationarity）と関連する幾つかの理由による。例えば、係数値またはコードブック・エントリは、僅かに異なる発生頻度を有し得、また、位置依存型であり得る。係数をグループへと分割することにより、グループの統計値の差は暴露され、それにより、グループが組み合わされた場合よりも合計エントロピを低下させることになる。
【００１５】
グループあたりの値の平均数が１より小さくとも、ここに説明する方法は、コーダがデコーダへ空グループのランがあることを伝えるように構成する場合には、なおも効率を上げられるようにする。
【００１６】
本発明は、多数の様式で実施することが可能であり、ここでは、例として、幾つかの特定の実施形態を添付図面を参照して説明する。
【図面の簡単な説明】
【００１７】
【図１】図１は、４×４イメージの２スケール・ウェーブレット変換の例を示す。
【図２】図２は、ビット・プレーンへと分割された図１の係数を示す。
【図３】図３は、本発明の実施形態に従った第１の係数のグループ化を示す。
【図４】図４は、第２のグループ化を示す。
【発明を実施するための形態】
【００１８】
ここで図１を参照すると、この図は、通信媒体を介しての前方への送信または記憶のためにビット単位（bit-wise）エンコードを行うために我々が望み得るタイプのウェーブレット変換の出力を示す。この例において、図１に示す出力は４×４イメージの２スケール・ウェーブレット変換を表すが、実際的な実施形態では、係数値およびイメージ・サイズの範囲は典型的にもっと大きく、また、ウェーブレット・スケールの数も大きい。ビット単位エンコードが行われるデータ・セットは、必ずしもウェーブレット変換の係数である必要ではなく（なお、そうであることが好ましいことではある）、本発明は、例えばＦＦＴ、ＤＣＴ、重複直交変換（lapped orthogonal transform）その他を含む任意の他のタイプの変換の係数からなる出力セットへも、同等に適用可能である。下記の方法は、他のデータ・セット、即ち、必ずしもイメージやオーディオを表すものではないデータ・セットの効率的なビット単位の圧縮にも使用することも可能である。ここに説明する方法は、例えばスプレッド・シート・データやワード・プロセッシング・データなどの効率的なビット単位の圧縮のために、同等に好適に作用する。例えば色、フォント、言語、更には臭いなどのような何れの関連する特徴も、係数のグループ化の基礎となり得る。
【００１９】
この方法は、従来のように係数値をバイナリ・ビットに変換し、図２に示すように個々にビット・プレーンを考慮することから開始する。図２では、簡素化するために、２つの係数１、２のみを示す。これらの係数の第１のものは、ビット・プレーン１７に第１重みビット（ＦＳＢ）２１を有し、第２のものは、ビット・プレーン１６にＦＳＢ２２を有する。図において、埋められた矩形部分は１を表し、空いている矩形部分は０を表す。
【００２０】
図２中の考慮されているデータ・セット２５は、図１に示すデータ・セットの全体または単にその一部であり得る。ここで、圧縮されたデータ・セットはウェーブレット変換の係数を含み、図２のデータ・セット２５は、図１に示す個々のサブバンド１１の１つを表し得る。
【００２１】
シャピロ（Shapiro）のシステムのような１つのタイプの従来の「埋め込み式」システムでは、変換された係数のビットは、通常、レイヤ毎に送られるものであり、最大重みビットが最初に送られる。従って、そのようなシステムでは、通常はビット２１が最初に送られ、それに続いて順にビット・プレーン１６、１５、１４の重みビットが送られる。このシステムでは、所定のスレッショルド・ビット・プレーン（この例では１４）より下からはビットが送られない。ビット・プレーン上のビットがあるところをデコーダが理解できるように、送られる各ビットについての一意の位置も識別される必要がある。これは多種の方法で行うことができ、その一例は、適当なビット・プレーン上のジグザグのスキャン経路２７に沿ってビットの位置を指定することである。他の多くのスキャン手法も知られている。
【００２２】
対照してみると、本発明では、係数のビットは、ビット・プレーン毎に加工しない状態で送信されるものではなく、送信または記憶の前にグループ化される。これは、多くの方法で行われ得る。好適な実施形態では、図３に示すように、係数は、最初に、それらの第１重みビットによりグループ化される。ここで、仮定として、送信される係数が全部で８つあり、これらが２つのグループに分割され、第１グループは、ＦＳＢがビット・プレーン１７上にあるものであり、第２グループは、ＦＳＢがビット・プレーン１６上にあるものであるとする。係数１および係数２は既に図２に示したものに対応し、係数３ないし係数８は明瞭化のために図２には示していない。
【００２３】
係数を２つのグループへと分割すると、更に、図４に示すように細かく分割する。この例では、係数は、ビット値により更に分割される。これらは４つのビット値（Ｖ１、Ｖ２、Ｖ３、Ｖ４）の合計であり、それがＦＳＢの２つの可能な値と組み合わされて、８つのグループの合計を生じるものであり、そのうちの３つは空である。次に、グループは、それぞれの個別グループ内の係数がビット・プレーン１７毎に送信されることにより、１つずつ送信（または記憶）される。従って、この例においては、最初に係数１が送信され、次に係数３および係数５がビット・プレーン毎に送信され、そして次に、係数４、次に係数２および７がビット・プレーン毎に、そして最後に、係数６および係数８がビット・プレーン毎に、送信される。
【００２４】
ここで「ビット値」はビットのシーケンス（一連のビット）を意味し、従って、例えば、もし係数がＦＳＢにより既に分割されており、２つの更なるビットのみが送信されることが決定されている場合、８つの可能な係数またはデータ値１０１ｘｘｘ、即ち、１０１０００、１０１００１、１０１０１０などの何れもが、同じグループに置かれる。なぜなら、ＦＳＢに続くビットのシーケンスは各場合とも０１であるからである。デジタル・データは離散的な数の値のみをとるので、グループの数は、多数のビットが送信される場合には多くなり得るが、なおも制限されたものとなる。
【００２５】
たとえビット値が等しい確率であっても、なおも、ビット値によりグループへと分割することによりデータの埋め込みを改善する。この例において、４つの可能なビット値が生じ、それらは１１、１０、０１、００（大きさにおける降順で示す）である。この順でグループを送ることにより、埋め込みを改善できる。なぜなら、デコードされるイメージまたは信号へ最も多くのパワーを加えるビット値が最初に送信されるからである。
【００２６】
また、可変深さエンコードを用いることも可能であり、言い換えると、異なる係数について異なる数のビットを送ることも可能である。純粋な位置情報を送信する場合、幾つかの係数は他の係数よりも高精度で送られる必要があるということを、デコーダは知る必要がない。なぜなら、デコーダが必要とする全ての情報はグループによって完全に記述されるからである。非常に高精度で送られる幾つかの係数は、一意的なビット値を有することになるようであり、従って、それら自体のグループへ行き着く。それに対して、非常に低精度で送られる係数は、一意的ではないビット値を有することになるようであり、従って、すべて同じグループへ行き着く。
【００２７】
別の可能性（それ自体で使用することも、１以上の上述の手法と組み合わせて使用することも可能）としては、係数をビット・プレーン毎に送信するが、まだ送信されていない次のビットの値に従って、各場合において係数をグループ化することがある。例えば、係数を、次のビットが１であるグループと、次のビットが０であるグループとの２つのグループに分割することができる。次に、最初のグループが送信（または記憶）され、それに続いて第２のグループが送信（または記憶）される。従って、有効に、係数自体の値ではなく、グループ内の各係数の位置を単に送信する。この手法は、多数のビットを送信する場合でもうまく働く。この技術は、ＦＳＢがスキャンされているビット・プレーンにおけるそのＦＳＢの位置により表示され（signaled）、１つのみの更なるビットが定義される場合において、ここに説明した本発明を適用するものとして見られることができる。しかしながら、この手法は、改善された標準のビット・プレーン・スキャン技術に使用することもできる。なぜなら、第１に、０のビットの前に１のビットが表示される場合に、埋め込み処理を改善するからであり、第２に、従業者は、洗練（refinement）において０のビットおよび１のビットが同じ確率で発生しないことを認識しているからである。
【００２８】
更に別の例（図示せず）では、代替のグループ化を用いることができる。例えば、係数がコードブック番号またはアトム（atom）を定義する場合には、グループは、ＦＳＢの代わりにそれに基づくか、またはＦＳＢに加えてそれにも基づく。典型的には、グループは、下記のもの、即ち、ＦＳＢ、振幅、ビット値、アトム／コードブック、係数と関連する任意の他の情報（副情報）のうちの任意の１つを個々に含み得るかまたは任意の組み合わせを含み得る。符号によるグループ化も可能であるが、多くの状況において、特に有用というわれではない。なぜなら、＋符号のグループは、通常、−符号のグループと等しい確率であるからである。
【００２９】
他のグループ化パラメータは除外されず、圧縮されるデータ・セットの種類によっては、ここで説明したパラメータ以外のパラメータを用いるのが好都合な場合もある。例えば、ウェーブレット変換などのような変換を用いてデータを周波数依存サブバンドへと分割した場合、サブバンド自体が第１または第２のグループの基礎を形成し得る。このような手法は、本方法を、従来のアルゴリズム、例えば、上述のシャピロの論文「Embedded Image Coding Using Zerotrees of Waveley Coefficients」に記載されたゼロツリー・ウェーブレット・アルゴリズム（Zerotree Wavelet Algorithm）（ＥＺＷ）などと関連して使用する場合に、好都合であり得る。任意の関連する特徴、例えば、色、フォント、言語、更には臭いなどのようなものも、係数のグループ化の基礎を形成することができる。
【００３０】
グループ化の順は、手元にあるアプリケーションに従って任意の都合のよい方法で定義できる。従って、最初にＦＳＢによりグループ化し、次にアトムによりグループ化すると都合がよいことが多く、これにより好適な埋め込みが行われるが、望まれる場合には、最初にアトムによりグループ化し、次にＦＳＢによりグループ化することも、同等に可能である。
【００３１】
幾つかの実施形態では、グループは、或るものが最終的に一意的な係数またはデータ・アイテムとなり、全てのその属性がそのグループにより定義されるように、選択される。そのような場合、特定の係数の全ての属性が、そのグループにより一意的に定義され、これは、もはや何れの係数情報も送る必要はない、ということを意味する。その代わりに、システムは、単に、データ・セット内の係数の位置に関する情報を送る必要がある。明確な係数の大きさ（coefficient magnitude）を送らないということは、直感に反するように思えるが、その情報は実際はもはや必要ではない。なぜなら、デコーダがデータ・セットを再構築するために必要とする全てのものは、位置情報内に、および（潜在的に）それらグループ自体により、含まれているからである。典型的には、そのような手法は、符号および他の属性によるグループ化を必要とする。
【００３２】
グループ自体は、任意の好都合な手法で、伝送のためにエンコードされる。エントロピを更に低減させるために、実際には、ランレングス・コード化、ハフマン、算術コード化（arithmetic coding）の技術や他の無損失圧縮アルゴリズムを、送信される一連の係数へ適用できることが、当然、理解されるであろう。標準的な方法では、各係数の値は、通常はビット毎に送信され、その送信は、ＦＳＢから開始され、或る所定のカットオフ点で終了する。これは、固定されたビット・プレーン（例えばプレーン１４）か、または各係数についてのＦＳＢの下の或る所定の深さ（例えば、図２の文字Ｐで示されるような、それぞれの場合においてｍｓｐの３ビット下）かの何れかである。
【００３３】
このようにしてデータをグループ化することにより、デコーダ（デコーダは、コーダにより使用されるアルゴリズムを知っている）は、ＦＳＢのビット・プレーンを、単に、受信したデータ・ストリームにおけるそのＦＳＢの位置から、決定することができるものであり、ＦＳＢの値を別に送信される必要ない。
【００３４】
もちろん、デコーダは、受信したデータ・ストリング中のそれがある場所を知ることができるようにする必要がある。これは、エンド・オブ・グループ（グループの終わり）（ＥＯＧ）記号を各グループの終わりに送ることによって、または各グループを送信する前に、幾つの値が後続するかを信号で知らせることによって、達成することができる。また、幾つかの状況では、コーダが、何れのグループがポピュレート（populate）されるかをエンコーダに知らせるマスクを送信するのが、便利である。代替例としては、グループ自体をランレングス・エンコードして、同一のグループの長いラン（特に、空のグループ）が送信されないようにする。
【００３５】
好適な実施形態においては、グループの位置をランレングス・コード化し、同時に、グループ化に使用しない他の属性を送信する。代替例では、ランレングス・コード化によりグループの位置を知らせた後に、他の属性を、グループを通じてのスキャンとして、送信することができる。
【００３６】
この技術の現在の実施形態において、グループ化のレベルは、ユーザ選択可能なスイッチにより定められ、それは下記のようである。
０．ＦＳＢのみによるグループ化
１．ＦＳＢ、およびビット値によるグループ化
２．（適当なデータ・セットに対しては）ＦＳＢと、ビット値と、アトム／コードブックの番号と、おそらくは符号とによるグループ化
【００３７】
下記の記載は、４つのスードコード（擬似コード）のリストであり、種種の転送の可能性を示している。各ケースにおいて、データは、既に、必要とされる数のグループへと分割されているものと仮定されている。
【００３８】
リスト１
・  各グループについて
・  グループについての位置情報を、グループ化されていないデータと共に、送信する
・  グループの終わりを知らせる
【００３９】
リスト２
・  各グループについて
・  幾つの値があるかを知らせる
・  グループについての位置情報を、グループ化されていないデータと共に、送信する
【００４０】
リスト３（多くの空のグループがある場合）
・  反復する
・  次の空ではないグループの前に幾つの空のグループがあるかを知らせる
・  空ではないグループのそれぞれについて
・  グループについての位置情報を、グループ化されていないデータと共に、送信する
・グループの終わりを知らせる
・  全てのグループがスキャンされるまで
【００４１】
リスト４（多くの空のグループがある場合）
・  反復する
・  次の空ではないグループの前に幾つの空のグループがあるかを知らせる
・  空ではないグループのそれぞれについて
・  幾つの値があるかを知らせる
・  グループについての位置情報を、グループ化されていないデータと共に、送信する
・  全てのグループがスキャンされるまで
【００４２】
説明した方法は、適用可能なところでは、係数が相関させられている場合に、予測アルゴリズム（係数の位置を予測するためのもの）と関連して使用することができる。これはエントロピを更に低減し得る。
【００４３】
図１ないし図４は、２次元データ・セットを圧縮する方法の使用を示しているが、この方法は、１次元データ・セット、例えば、変換されたオーディオ信号などの圧縮にも同様に適用可能であることが、理解されるであろう。説明した方法は、例えばワード・プロセッシング・ファイルやスプレッドシート・ファイルなどを含むテキスト情報の圧縮にも同様に適用可能であり、また、他の広範囲のデータにも適用可能である。実際、説明した方法は、変換が適用されるか否かにかかわらず、任意の（圧縮可能な）データを圧縮するために使用できる。
【図１】
2011045140.tif 000003
【図２】
2011045140.tif 000004
【図３】
2011045140.tif 000005
【図４】
2011045140.tif 000006
【手続補正書】
【提出日】平成22年11月22日(2010.11.22)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データ圧縮の方法であって、
データに変換を適用して複数の変換係数を導き出すステップと、
前記係数を複数の係数のグループに分割するステップであって、それにより、前記係数が係数値の特徴に従ってグループ化されるものであり、前記係数がそれらの第１シグニフィカント・ビットに従ってグループ化されるものであり、前記係数が複数の前記グループにより任意の所望される順にグループ化されるものである、ステップと、
前記係数が置かれるグループ内のそれぞれの係数についての位置情報を含む圧縮データを順に記憶または送信するステップと、を備え、
前記係数を複数の係数のグループに分割するステップでは、前記係数をバイナリ・ビットに変換し、各々の係数の第１シグニフィカント・ビットがどのビット・プレーン上にあるかに基づいて、前記係数を複数のグループに分割する、方法。
【請求項２】
請求項１に記載のデータ圧縮の方法であって、前記係数が複数の前記グループにより任意の所望される順にグループ化される処理において、前記係数はそれらのビット値に基づく順にグループ化される、方法。
【請求項３】
請求項１に記載のデータ圧縮の方法であって、前記係数が複数の前記グループにより任意の所望される順にグループ化される処理において、前記係数は、ビット・プレーン毎での送信のために、まだ記憶も送信もされていない次のビットの値に基づく順にグループ化される、方法。
【請求項４】
請求項１に記載のデータ圧縮の方法であって、前記係数が複数の前記グループにより任意の所望される順にグループ化される処理において、前記係数は符号に基づく順にグループ化される、方法。
【請求項５】
請求項１に記載のデータ圧縮の方法であって、前記係数が複数の前記グループにより任意の所望される順にグループ化される処理において、前記係数は振幅に基づく順にグループ化される、方法。
【請求項６】
請求項１に記載のデータ圧縮の方法であって、それぞれの係数は個々の副情報と関連しており、前記係数が複数の前記グループにより任意の所望される順にグループ化される処理において、前記係数は前記副情報の特徴に基づく順にグループ化される、方法。
【請求項７】
請求項１に記載のデータ圧縮の方法であって、前記係数が置かれるグループ内のそれぞれの係数についての位置情報は、送信するためにエンコードされる、方法。
【請求項８】
請求項１に記載のデータ圧縮の方法であって、前記係数が置かれるグループ内のそれぞれの係数についての位置情報が、全ての残りの値関連の情報と共に、記憶または送信される、方法。
【請求項９】
請求項１ないし７の何れかに記載のデータ圧縮の方法であって、前記係数の前記グループは記憶または送信される前にランレングス・エンコードされる、方法。
【請求項１０】
請求項１に記載のデータ圧縮の方法であって、前記変換はウェーブレット変換である、方法。
【請求項１１】
請求項１に記載のデータ圧縮の方法であって、前記変換は高速フーリエ変換である、方法。
【請求項１２】
請求項１に記載のデータ圧縮の方法であって、前記変換は離散コサイン変換である、方法。
【請求項１３】
請求項１に記載のデータ圧縮の方法であって、前記変換は重複直交変換である、方法。
【請求項１４】
請求項１に記載のデータ圧縮の方法であって、前記データはスチル・イメージまたはビデオを表す、方法。
【請求項１５】
請求項１に記載のデータ圧縮の方法であって、前記データはオーディオ・ストリームを表す、方法。
【請求項１６】
請求項１に記載のデータ圧縮の方法であって、前記データはテキストを表す、方法。
【請求項１７】
コンピュータ・プログラムであって、コンピュータを、
データに変換を適用して複数の変換係数を導き出す手段と、
前記係数を複数の係数のグループに分割する手段であって、それにより、前記係数が係数値の特徴に従ってグループ化されるものであり、前記係数がそれらの第１シグニフィカント・ビットに従ってグループ化されるものであり、前記係数が複数のグループ化により任意の所望される順にグループ化されるものである、手段と、
前記係数が置かれるグループ内のそれぞれの係数についての位置情報を含む圧縮データを順に記憶または送信する手段と、して機能させ、
前記係数を複数の係数のグループに分割する手段は、前記係数をバイナリ・ビットに変換し、各々の係数の第１シグニフィカント・ビットがどのビット・プレーン上にあるかに基づいて、前記係数を複数のグループに分割する、コンピュータ・プログラム。
【請求項１８】
コンピュータ・プログラムが記録されたコンピュータ読取可能な記録媒体であって、コンピュータを、
データに変換を適用して複数の変換係数を導き出す手段と、
前記係数を複数の係数のグループに分割する手段であって、それにより、前記係数が係数値の特徴に従ってグループ化されるものであり、前記係数がそれらのファースト・シグニフィカント・ビットに従ってグループ化されるものであり、前記係数が複数のグループ化により任意の所望される順にグループ化されるものである、手段と、
前記係数が置かれるグループ内のそれぞれの係数についての位置情報を含む圧縮データを順に記憶または送信する手段と、して機能させ、
前記係数を複数の係数のグループに分割する手段は、前記係数をバイナリ・ビットに変換し、各々の係数の第１シグニフィカント・ビットがどのビット・プレーン上にあるかに基づいて、前記係数を複数のグループに分割する、コンピュータ・プログラムを記録した記録媒体。
【請求項１９】
コーダであって、
データに変換を適用して複数の変換係数を導き出す手段と、
前記係数を複数の係数のグループに分割する手段であって、それにより、前記係数が係数値の特徴に従ってグループ化されるものであり、前記係数がそれらの第１シグニフィカント・ビットに従ってグループ化されるものであり、前記係数が複数のグループ化により任意の所望される順にグループ化されるものである、手段と、
前記係数が置かれるグループ内のそれぞれの係数についての位置情報を含む圧縮データを順に記憶または送信する手段と、を備え、
前記係数を複数の係数のグループに分割する手段は、前記係数をバイナリ・ビットに変換し、各々の係数の第１シグニフィカント・ビットがどのビット・プレーン上にあるかに基づいて、前記係数を複数のグループに分割する、コーダ。
【請求項２０】
コーダを含むコーデックであって、
前記コーダが、
データに変換を適用して複数の変換係数を導き出す手段と、
前記係数を複数の係数のグループに分割する手段であって、それにより、前記係数が係数値の特徴に従ってグループ化されるものであり、前記係数がそれらの第１シグニフィカント・ビットに従ってグループ化されるものであり、前記係数が複数のグループ化により任意の所望される順にグループ化されるものである、手段と、
前記係数が置かれるグループ内のそれぞれの係数についての位置情報を含む圧縮データを順に記憶または送信する手段と、を備え、
前記係数を複数の係数のグループに分割する手段は、前記係数をバイナリ・ビットに変換し、各々の係数の第１シグニフィカント・ビットがどのビット・プレーン上にあるかに基づいて、前記係数を複数のグループに分割する、コーデック。
【外国語明細書】
2011045140000001.pdf