JP2002540711A - 有限アルファベットデータのロスレス適応符号化 - Google Patents

Abstract

(57)【要約】 符号化器が、量子化ウェーブレット係数を並べ替えてデータ依存型データ構造を使用する必要なしに大小ウェーブレット係数を分離したグループにクラスタ化する。次に、係数が適応的にランレングスコードに基づき符号化され、これは量子化係数のストリングを表現するため使用されたコードワードを制御するパラメータを継続的に修正し、コードワードで使用されたビット数の最小化を求める。指標の行列が最も粗い係数を左上隅に含み、代替方法で低高および高低サブバンドをより大型のブロックに充填し、低高サブバンドに行列の最上部を含め、高低サブバンドに行列の左側を含める。最短コードワードが、可能性の最も高いキャラクタの、２^ｋ（ｋはパラメータ）の長さのランを表現するため割り当てられる。ｋは遭遇している連続キャラクタに基づき調整され、キャラクタが同一のとき増加され、異なるとき減少される。復号器は、上記を逆の順序で適用する。

Description

【発明の詳細な説明】

【０００１】 （発明の分野） 本発明は、一般にイメージ圧縮の分野に関し、詳細には、デジタルビクチャの
改善されたウェーブレット符号化および復号に関する。 （関連出願の参照） 本願は、本願と同一譲受人に譲渡された、同日出願の、弁理士整理番号７７７
．２６４ＵＳ１を有する「Ｉｍａｇｅ Ｅｎｃｏｄｉｎｇ Ｕｓｉｎｇ Ｒｅｏ
ｒｄｅｒｉｎｇ ａｎｄ Ｂｌｏｃｋｉｎｇ ｏｆ Ｗａｖｅｌｅｔ Ｃｏｅｆ
ｆｉｃｉｅｎｔｓ Ｃｏｍｂｉｎｅｄ Ｗｉｔｈ Ａｄａｐｔｉｖｅ Ｅｎｃｏ
ｄｉｎｇ」、および、７７７．２６５ＵＳ１を有する「Ｒｅｏｒｄｅｒｉｎｇ
Ｗａｖｅｌｅｔ Ｃｏｅｆｆｉｃｉｅｎｔｓ Ｆｏｒ Ｉｍｐｒｏｖｅｄ Ｅｎ
ｃｏｄｉｎｇ」という名称の同時係属出願に関連し、これらは参照のため本明細
書に組み込まれる。

【０００２】 （著作権の注記／許諾） 本特許明細書の開示の一部は、著作権保護を受けるマテリアルを含む。著作権
所有者は、特許商標局の特許ファイルまたは記録において現れるような、特許明
細書または特許開示の、いかなる者によるファクシミリ複製にも異議を有するも
のでないが、そうでない場合はいかなるすべての著作権も留保するものである。
以下の注記は、以下で、かつ、本明細書の図面において記載されたようなソフト
ウェアおよびデータに適用される。すなわち、Ｃｏｐｙｒｉｇｈｔ（著作権）１
９９９，Ｍｉｃｒｏｓｏｆｔ Ｃｏｒｐｏｒａｔｉｏｎ，Ａｌｌ Ｒｉｇｈｔｓ
Ｒｅｓｅｒｖｅｄ。

【０００３】 （背景） デジタルピクチャは、Ｗｅｂページ、ＣＤ−ＲＯＭ百科事典、デジタルカメラ
、およびその他、多数の応用例において使用されている。たいていの場合、ピク
チャを少量のストレージに適合させるため、あるいは短時間でダウンロードされ
るために、ピクチャを圧縮することが必要である。例えば、典型的なデジタルカ
メラでは、ピクチャが、１０２４×７６８画素（ピクセル）の解像度で、ピクセ
ルにつき１２〜２４ビットの解像度で撮られる。したがって、各イメージにおけ
る生データが、約１．２〜２．５メガバイトである。いくつかのピクチャをコン
ピュータディスケットに適合させるため、例えば、各ピクチャによって使用され
たデータ量を減らすことが必要である。達成される圧縮率が大きいほど、より多
くのピクチャがディスケットまたはメモリカードに適合し、より高速に、電話回
線など、帯域幅が制限された伝送媒体を介して転送することができる。

【０００４】 イメージ圧縮は、過去２０年間に渡って広範に研究されてきた。ＪＰＥＧ規格
は、ＩＳＯ（Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｔａｎｄａｒｄｓ Ｏｒｇａｎｉ
ｚａｔｉｏｎ）のＪＰＥＧ（ｊｏｉｎｔ ｐｈｏｔｏｇｒａｐｈｉｃ ｅｘｐｅ
ｒｔｓ ｇｒｏｕｐ）委員会によって定義されたものであり、１９９２年に定義
され、最も普及した、デジタルピクチャを圧縮する方法である。ＪＰＥＧでは、
小型の正方形のブロックのピクセル（サイズ８×８）が周波数領域に、離散コサ
イン変換（ＤＣＴ）によってマップされる。ＤＣＴ係数が量子化され（スケール
ファクタによって除算され、最も近い整数に丸められる）、１次元のベクトルに
、固定のジグザク走査パターンを介してマップされる。このベクトルが、ランレ
ングスおよびハフマン符号化の組合せを介して符号化される。

【０００５】 ＪＰＥＧにおける小型の８×８ブロックの独立処理は、実施の視点から、特に
低コストのハードウェアにおいて利点である。しかし、これは、ＪＰＥＧの主な
問題、すなわち、ブロッキングアーチファクト（ｂｌｏｃｋｉｎｇ ａｒｔｉｆ
ａｃｔｓ）にも通じる。隣接ブロックからの量子化エラーはブロック間では相関
しないが、ブロック内で相関するので、８×８ブロックの境界が、復元されたイ
メージにおいて、隣接ブロック間の符号化における潜在的な差により可視となる
。このようなアーチファクトは、タイリングまたはブロッキングアーチファクト
と呼ばれ、これらはオーバーラップ基底関数による変換を使用することによって
低減させることができる（が、完全に解消することはできない）。

【０００６】 ブロッキングアーチファクトを除去するための効率的な方法は、ブロックＤＣ
Ｔをウェーブレット分解によって置き替えることであり、これは効率的な時間周
波数表現を提供する。大変よい圧縮性能を、ウェーブレット係数を量子化および
符号化することによって、得ることができる。

【０００７】 多数のウェーブレットベースのイメージ圧縮システムが、過去数年における技
術論文において報告されている。ウェーブレットによれば、典型的にはＪＰＥＧ
より２０％〜５０％よい範囲の圧縮率を達成することが可能である。より重要に
は、ウェーブレット変換が、ＪＰＥＧの妨げとなるブロッキングアーチファクト
を有していないピクチャに通じる。したがって、ウェーブレットベースの変換が
、ますます普及しつつある。実際に、ＪＰＥＧの次の改訂はＪＰＥＧ２０００と
称され、ここでは、考慮中のすべての提案がウェーブレットを使用する。

【０００８】 いくつかの従来のウェーブレット変換は、イメージを、１６サブバンドに対応
する係数に分解する。これは、サブバンドの４×４の行列の結果となり、これが
大きいブロックフォーマットと呼ばれ、スペクトル分解およびチャネルの順序付
けを表す。文字ＬおよびＨが使用されて、各サブバンドのためのローパスフィル
タリングおよびハイパスフィルタリングがそれぞれ識別される。最初のサブバン
ドがＬＬおよびＨＬ係数を含み、各集合（ｓｅｔ）における最初の文字（ｌｅｔ
ｔｅｒ）が水平フィルタリングに対応し、第２のものが垂直フィルタリングに対
応する。２つの段階が、各サブバンドフィルタリングの結合において使用される
。順序付けが、左から右へ、かつ、下から上へ増大する周波数に対応する。この
順序付けが固定されて、符号化および復号が、固定された方法において機能する
ことができる。次いで、係数の量子化が実行され、その後にある形式の係数の圧
縮符号化が続き、さらにイメージを圧縮するために適応ハフマン符号化または算
術符号化が含まれる。これらの形式の符号化は、データタイプに依存するゼロツ
リー構造を含んで、大変複雑になる可能性がある。これらの符号化器はかなり複
雑であり、多数が、圧縮される異なるイメージに合わせて修正される必要があり
、これらをハードウェアにおいて実施することを困難にする。

【０００９】 ウェーブレット圧縮係数および同様の有限アルファベットデータに作用し、ハ
ードウェアやソフトウェアでも実施されるような、簡素な符号化技術への要求が
ある。

【００１０】 （発明の概要） 適応符号化が、より小さい絶対値の値がより大きい絶対値を有するものより発
生する可能性が高い、符号付き整数データにおいて実行される。この符号化はビ
ットプレーンにおいて実行され、これが、復元の精度における、ロスレス（エラ
ーなし）から様々なレベルの近似復元までのスケーラビリティを可能にする。ハ
フマン符号化とは異なり、コードテーブルが必要ではなく、これは、簡素な規則
がコードワードを入力ストリングから決定するためである。

【００１１】 １つの形式では、各ビットプレーンについて、最短のコードワード（単一の０
）が割り当てられ、最も可能性の高い入力、ゼロの、長さ２^ｋを有するランが表
現され、ｋは、コードワードにおいて使用されたビットの数を最小化することを
求め、量子化された係数のストリングを表現するために使用されたコードワード
を制御するパラメータである。ｋは、より長いランに遭遇するときに増加し、そ
うでない場合、たとえば、そのランにおけるものとは異なったシンボルに遭遇す
るときに減少するように適合される。ビットプレーンの符号化は、適応算術符号
化器など、いかなる効率的なエントロピー符号化器によっても行うことができる
が、一実施態様においては、新しい適応ランレングスおよびＧｏｌｏｍｂ−Ｒｉ
ｃｅ符号化器が使用される。

【００１２】 ゼロツリーなど、データ依存型データ構造、または、ツリーにおける集合区画
（ｓｅｔ ｐａｒｔｉｔｉｏｎｓ）のための別々のリストの使用を必要としない
ことにより、ハードウェア実施をより構築しやすく、ソフトウェア実施はより高
速で動作することができる。

【００１３】 （詳細な説明） 本発明の例示的実施形態の以下の詳細な説明では、添付の図面への参照が行わ
れ、これは本明細書の一部を形成し、例示として、本発明を実施することができ
る特定の例示的実施形態が図示される。これらの実施形態が、当業者が本発明を
実施できるようにするために十分な詳細において記載され、他の実施形態を利用
できること、および、論理的、機械的、電気的、かつ他の変更を、本発明の精神
または範囲から逸れることなく行うことができることを理解されたい。したがっ
て、以下の詳細な説明は、限定の意味において取られるものではなく、本発明の
範囲は、付属の特許請求の範囲によってのみ定義される。

【００１４】 詳細な説明は、多数のセクションに分割される。第１のセクションは、本発明
を実施するコンピュータシステムの動作を記載する。この後に、量子化されたウ
ェーブレット係数の固定並べ替え、および、それらの適応ランレングス符号化の
高レベルの記載が続く。このような符号化されたデータのための復号器も記載さ
れる。次いで、高レベルの記載から選択されたブロックのさらなる詳細が、フロ
ーチャートの使用によって記載される。この後に、このような符号化器および復
号器の、ソフトウェアアプリケーションのオフィス一式における使用の一般的な
記載が続く。結論は、いくつかの潜在的な利点を記載し、さらなる代替実施形態
を記載する。

【００１５】 ハードウェアおよび動作環境 図１は、本発明を実施することができる適切なコンピューティング環境の、簡
単で一般的な説明を提供する。本発明が以下で、一般に、パーソナルコンピュー
タ（ＰＣ）によって実行される命令を含む、コンピュータ実行可能プログラムモ
ジュールに関連して記載される。プログラムモジュールには、ルーチン、プログ
ラム、オブジェクト、コンポーネント、データ構造などが含まれ、これらが特定
のタスクを実行し、あるいは特定の抽象データ型を実施する。本発明を他のコン
ピュータシステム構成により実施することができ、これらには、マルチメディア
機能を有するハンドヘルドデバイス、マルチプロセッサシステム、マイクロプロ
セッサに基づくプログラム可能な家庭用電化製品、ネットワークＰＣ、ミニコン
ピュータ、メインフレームコンピュータなどが含まれることは、当業者には理解
されよう。本発明はまた、分散コンピューティング環境において実施することも
でき、タスクがリモート処理デバイスによって実行され、これらが通信ネットワ
ークを介してリンクされる。分散コンピューティング環境では、プログラムモジ
ュールを、ローカルおよびリモートのメモリストレージ装置に位置付けることが
できる。

【００１６】 図１は、汎用コンピューティングデバイスを従来のパーソナルコンピュータ２
０の形式において示し、これが、処理装置２１、システムメモリ２２、および、
システムメモリおよび他のシステム構成要素を処理装置２１に結合するシステム
バス２３を含む。システムバス２３を、いくつかのタイプのいずれにすることも
でき、これには、メモリバスまたはメモリコントローラ、周辺バス、およびロー
カルバスが含まれ、これは様々なバス構造のいずれを使用することもできる。シ
ステムメモリ２２が読取り専用メモリ（ＲＯＭ）２４およびランダムアクセスメ
モリ（ＲＡＭ）２５を含む。基本入出力システム（ＢＩＯＳ）２６は、ＲＯＭ２
４に格納され、情報をパーソナルコンピュータ２０の構成要素間で転送する基本
ルーチンを含む。ＢＩＯＳ２６は、システムのための起動ルーチンも含む。パー
ソナルコンピュータ２０はさらに、ハードディスク（図示せず）から読み取りか
つこれに書き込むためのハードディスクドライブ２７、リムーバブル磁気ディス
ク２９から読み取りかつこれに書き込むための磁気ディスクドライブ２８、およ
び、ＣＤ−ＲＯＭまたは他の光媒体など、リムーバブル光ディスク３１から読み
取りかつこれに書き込むための光ディスクドライブ３０を含む。ハードディスク
ドライブ２７、磁気ディスクドライブ２８、および光ディスクドライブ３０が、
システムバス２３へ、それぞれハードディスクドライブインターフェース３２、
磁気ディスクドライブインターフェース３３、および光ディスクドライブインタ
ーフェース３４によって接続される。ドライブおよびそれらの関連付けられたコ
ンピュータ読取り可能媒体が、パーソナルコンピュータ２０用の、コンピュータ
可読命令、データ構造、プログラムモジュールおよび他のデータの不揮発性スト
レージを提供する。本明細書に記載された例示的環境は、ハードディスク、リム
ーバブル磁気ディスク２９およびリムーバブル光ディスク３１を使用するが、コ
ンピュータによりアクセス可能なデータを格納することができる他のタイプのコ
ンピュータ読取り可能媒体も例示的動作環境において使用できることは、当業者
には理解されよう。このような媒体には、磁気カセット、フラッシュメモリカー
ド、デジタル汎用ディスク、ベルヌーイカートリッジ、ＲＡＭ、ＲＯＭなどが含
まれる可能性がある。

【００１７】 プログラムモジュールを、ハードディスク、磁気ディスク２９、光ディスク３
１、ＲＯＭ２４およびＲＡＭ２５において格納することができる。プログラムモ
ジュールには、オペレーティングシステム３５、１つまたは複数のアプリケーシ
ョンプログラム３６、他のプログラムモジュール３７およびプログラムデータ３
８が含まれる可能性がある。ユーザが、コマンドおよび情報をパーソナルコンピ
ュータ２０へ、キーボード４０およびポインティングデバイス４２など、入力装
置を介して入力することができる。他の入力装置（図示せず）には、マイクロフ
ォン、ジョイスティック、ゲームパッド、衛星放送受信アンテナ、スキャナなど
が含まれる可能性がある。これらおよび他の入力装置が、しばしば処理装置２１
へ、システムバス２３に結合されたシリアルポートインターフェース４６を介し
て接続されるが、これらを、パラレルポート、ゲームポートまたはユニバーサル
シリアルバス（ＵＳＢ）など、図１において図示されていない他のインターフェ
ースを介して接続することもできる。モニタ４７または他の表示装置も、システ
ムバス２３へ、ビデオアダプタ４８などのインターフェースを介して接続する。
モニタに加えて、パーソナルコンピュータは典型的には、スピーカおよびプリン
タなど、他の周辺出力装置（図示せず）を含む。

【００１８】 パーソナルコンピュータ２０は、ネットワーク環境において、リモートコンピ
ュータ４９など、１つまたは複数のリモートコンピュータへの論理接続を使用し
て動作することができる。リモートコンピュータ４９は、別のパーソナルコンピ
ュータ、サーバ、ルータ、ネットワークＰＣ、ピアデバイス、または他の共通ネ
ットワークノードにすることができる。これは典型的には、パーソナルコンピュ
ータ２０に関して上で記載された構成要素の多数またはすべてを含むが、ストレ
ージ装置５０のみが図１に例示されている。図１に示された論理接続は、ローカ
ルエリアネットワーク（ＬＡＮ）５１およびワイドエリアネットワーク（ＷＡＮ
）５２を含む。このようなネットワーキング環境は、オフィス、企業全体のコン
ピュータネットワーク、イントラネットおよびインターネットにおいて一般的で
ある。

【００１９】 ＬＡＮネットワーキング環境に配置されるとき、ＰＣ２０がローカルネットワ
ーク５１へ、ネットワークインターフェースまたはアダプタ５３を介して接続す
る。インターネットなど、ＷＡＮネットワーキング環境において使用されるとき
、ＰＣ２０が典型的には、モデム５４、または、ネットワーク５２を介して通信
を確立するための他の手段を含む。モデム５４は、ＰＣ２０の内部あるいは外部
にすることができ、システムバス２３へ、シリアルポートインターフェース４６
を介して接続する。ネットワーク環境では、２０内に常駐するように示されるＭ
ｉｃｒｏｓｏｆｔ（登録商標）Ｗｏｒｄを含むものなどのプログラムモジュール
、またはその一部を、リモートストレージ装置５０に格納することができる。も
ちろん、図示されたネットワーク接続は例示的であり、通信リンクをコンピュー
タ間で確立する他の手段で置換することができる。

【００２０】 ソフトウェアは、オブジェクト指向プログラミング方法を含む、多数の異なる
方法を使用して設計することができる。Ｃ＋＋およびＪａｖａ（登録商標）は、
共通のオブジェクト指向コンピュータプログラミング言語の２つの例であり、こ
れらはオブジェクト指向プログラミングに関連付けられた機能性を提供する。オ
ブジェクト指向プログラミング方法は、データメンバ（変数）、および、このデ
ータにおいて動作するメンバ関数（メソッド）を、クラスと呼ばれる単一のエン
ティティにカプセル化するための手段を提供する。オブジェクト指向プログラミ
ング方法は、既存のクラスに基づいて新しいクラスを作成するための手段も提供
する。

【００２１】 オブジェクトは、クラスのインスタンスである。オブジェクトのデータメンバ
は、コンピュータメモリ内部に格納される属性であり、メソッドは、このデータ
上で動作して潜在的に他のサービスを提供する実行可能コンピュータコードであ
る。オブジェクトの概念が本発明において活用され、本発明のある態様が、一実
施形態においてオブジェクトとして実施される。

【００２２】 インターフェースは、関係する関数のグループであり、名前付きユニットに編
成される。各インターフェースを、ある識別子によって一意に識別することがで
きる。インターフェースはインスタンス化を有しておらず、つまり、インターフ
ェースは定義でしかなく、インターフェースによって指定されるメソッドを実施
するために必要とされた実行可能コードを有していない。オブジェクトは、イン
ターフェースによって指定されたメソッドのための実行可能コードを提供するこ
とによって、インターフェースをサポートすることができる。オブジェクトによ
って供給された実行可能コードは、インターフェースによって指定された定義に
従わなければならない。オブジェクトは、追加のメソッドを提供することもでき
る。インターフェースが、オブジェクト指向プログラミング環境における、ある
いはそれによる使用に限定されないことは、当業者には理解されよう。

【００２３】 高レベルの符号化器および復号器の説明 ウェーブレット変換に基づいたイメージピクセル符号化器の簡素化されたブロ
ック図が、図２に示され、対応する復号器が図３に示される。符号化器および復
号器が、イメージピクセルデータに関して各入力および出力として記載され、他
のデータも望まれるように変換することができる。図示の実施形態では、イメー
ジピクセルデータがウェーブレット変換ブロック２１０に提供され、これが周知
の方法で動作して、ウェーブレット係数を量子化ブロック２２０へ提供する。ウ
ェーブレット係数は、背景のセクションで記載されたような大きいブロックフォ
ーマットである。量子化は、一様量子化器（ｕｎｉｆｏｒｍ ｑｕａｎｔｉｚｅ
ｒ）によって実行され、これが、しきい値Ｔを定義する量子化ステップによって
制御される。これは、各係数の表現が、ステップの中間における値によって、ス
テップの間に入る結果となる。Ｔが小さいほど、量子化において受ける損失が少
ない。したがって、ブロック２２０の出力は一連の整数の数値であり、これらが
、量子化されたウェーブレット係数である。多数の他の応用例におけるように、
量子化器を、標準の丸めに基づくように、あるいは、ゼロに向かう丸めにおける
（「不感帯（ｄｅａｄ ｚｏｎｅ）」を有する量子化器としても知られる）よう
にすることができる。

【００２４】 並べ替えおよびブロッキング機能またはブロック２３０が、ウェーブレット係
数を、同様の値のクラスタにグループ化する。これは、ゼロになる可能性が最も
高い周波数係数のブロックの、クラスタ化または共にグループ化の結果となる。
並べ替えは、データが単調に減衰する振幅の分布を有する傾向があるという意味
において、類似データのグループ化の可能性を増大させる。最初のブロックが、
より大振幅のデータを有する傾向があるが、後続のブロックでは、ウェーブレッ
ト係数の振幅が減衰する傾向がある。グループ化は、走査順序を固定することに
よって行われ、これはデータ独立である。このようなグループ化の１つの集合（
ｓｅｔ）が、図４において、６４ブロックのウェーブレット係数を有する例につ
いて示される。図４では、低周波数の構成要素が、グループ化の左上隅に向かっ
て配置され、各レベルの低高および高低サブバンドからの係数のブロックが交番
させられる。並べ替えおよびブロッキングブロック２３０が、マクロブロックの
シーケンスを、指示された走査順序で提供する。最初のブロック０は、ウェーブ
レットツリーのレベル０のすべての係数を含む。これは、最も粗い解像度に対応
する。ブロック０〜３は、レベル１のすべての係数を含む。ブロック０〜１５は
、レベル２のすべての係数を含み、レベル３は、ブロック０〜６３を含む。ブロ
ックが、各レベルの低高および高低サブバンドから交互になり、低高がシーケン
スの最上部であることに留意されたい。以下の数学的説明のセクションでは、こ
の特定の順序付けの利点を論じる。他の順序付けは、当業者によって理解される
ように可能であるが、上の順序付けが他のものよりよく動作すると思われる。次
いで、ビットが、最上位のビットで開始して、順次に符号化される。

【００２５】 適応符号化ブロック２４０がマクロブロックを受信し、これらを無損失な方法
（ｌｏｓｓｌｅｓｓ ｍａｎｎｅｒ）で符号化する。ブロックのクラスタ化が、
圧縮するデータを提供し、これが大きなゼロのクラスタを有する。ビットプレー
ンに基づいて符号化することによってさらにデータを並べ替えることが、大きな
ゼロのストリング（ｓｔｒｉｎｇｓ ｏｆ ｚｅｒｏｓ）を発見する可能性を増
大させる。最初のビットプレーンについて最上位のビットで開始することが、ゼ
ロの長いストリングのより高い可能性に通じる。さらに、これは、最も関連のあ
るデータが最初に符号化されることも保証する。第３または第４のビットプレー
ンが符号化されるときまで、確率は、１とは対照的にゼロについてほぼ等しく、
直線的二進符号化を効果的に使用することができる。

【００２６】 符号化器は、適応ランレングス修正を有するＧｏｌｏｍｂ−Ｒｉｃｅ符号化器
の適合である。簡素な項では、２^ｋ個のゼロのストリングが、ゼロに等しい単一
のビットからなるコードワードによって表現される。ゼロコードワードによって
表現されたゼロのストリングの長さは、パラメータｋによって制御され、これは
データに遭遇したときに、観察されたゼロの頻度に基づいて変わる。ゼロ値が符
号化されたとき、ゼロがより可能性が高いと仮定され、そのためパラメータｋの
値が増加される。ゼロでない値に遭遇したとき、ｋが減少される。このような増
加および減少の量を適切に制御することによって、符号化器が、変化するゼロの
確率を有するビットのストリングをよく追跡することができ、実際にこの確率を
推定するオーバーヘッドの必要性がない。フィードバックループ２４５が使用さ
れて、符号化器２４０のバックワード適応的な性質が表現される。この符号化は
、効率的な圧縮、および、入力データの統計量における変化への高速な適合に備
える。符号化器２４０がビットストリームを外部に提供し、これは、最も関連の
ある情報がビットストリームの最初で提供されることにおいて、効果的にプログ
レッシブである。最下位のビットが最後のビットプレーンで符号化されるので、
より低解像度のビットストリームでは、解像度忠実性ブロック２５０で表現され
たように、これらを効果的に廃棄するかあるいは符号化しないことができる。こ
れは、データのより低い帯域幅伝送に有用である。

【００２７】 図３においてブロック形式で図示されたような復号は、本質的に符号化および
データ変換の逆である。図２の符号化器によって生成されたものなど、符号化さ
れたデータのビットストリームが、ロスレス適応復号ブロック３１０で受信され
る。ビットストリームを直接、復号器から、ローカルのストレージから、あるい
はリモートの復号器またはストレージから、衛星伝送、ケーブル伝送または他の
ネットワークによってなど、多数の実行可能伝送媒体の１つを介して受信するこ
とができる。復号ブロック３１０が、符号化中に開発された規則を、フィードフ
ォワード線３１５を介して受信する。ブロック３１０が本質的に、使用されるス
トリング長を受信し、データを規則に従って復元する。再度、これはブロックレ
ベルで動作するが、これは本発明の要件ではない。これは単に、より大量のメモ
リを必要とするか、あるいは、このようなメモリが使用可能でなかった場合はペ
ージングを必要とする、イメージまたは他のデータの表現全体を同時に処理する
ことよりも、好都合にする。忠実性低減の１つの形式を、ブロック３１０で、ビ
ットプレーンにおける最後のビットを復号しないことのみによって実行すること
ができる。これは効果的に、パラメータＴによって制御されたステップサイズを
倍増する。これは、データの忠実性を低減するための簡素な方法である。

【００２８】 ブロック３１０から出たデータは、ブロック２３０から来る整数データに等し
くなるべきである。しかし、３２０のイメージのより高解像度の層を、このポイ
ントで、ブロック３２０で示されたように除去することができ、これは、より高
い周波数ウェーブレット係数を効果的に使用しないことのみによる。これは、イ
メージまたはイメージの集合を表示するために使用されたウィンドウが小型であ
った場合、有用となる。次いで、ブロック３３０が使用されて、ブロックが元の
位置へ戻るようにアンシャッフルあるいは並べ替えされる。並べ替えブロック３
３０の出力は、受信されたビットストリームにおけるヘッダによって提供される
ステップサイズを使用することによって、ブロック３４０で戻すように再乗算さ
れる必要がある整数の数値である。これが、復元されたウェーブレット係数を提
供する。ヘッダは、イメージサイズがどれほど大きいかについての情報、および
、他の標準イメージフォーマットのデータも提供する。次いで、逆ウェーブレッ
ト変換が、周知の方法で３５０で実行される。選択された所望の忠実性または解
像度低減以外の損失のみが、量子化ステップにおいて受けられ、これがＴパラメ
ータの修正によって制御可能であることに留意されたい。

【００２９】 解像度低減オプションブロック３２０は、少数の異なる方法において動作する
ことができる。データを除去するための１つの方法は、含まれた整数をゼロにす
ることによる。解像度を低減するためのさらなる方法は、アンシャッフルブロッ
ク３３０の動作を修正することであり、これに、値を所望のポイントでゼロにす
るように命令することができる。アンシャッフルブロック３３０および逆ウェー
ブレット変換ブロック３５０に、どこでゼロが開始するかを伝えることによって
、このようなポイントでの実際のデータの不必要な処理をなくすように、これら
を容易に修正することができる。

【００３０】 本発明の適応符号化および復号は、変化する統計量と共に、クラスタ化された
ゼロを有するデータにおいて、大変よく動作する。このタイプのデータを、ゼロ
のいずれの側においても確率の近い指数減衰を有するデータの高い確率を有する
ものとして特徴付けることもできる。静的イメージデータおよびビデオなど、マ
ルチメディアデータがこの特性を有する。さらに、多数のタイプの物理データの
変換も、このタイプの特性を有する。物理データを取り込むとき、情報は通常、
少数の場所においてのみ起こり、これは、他のデータの大部分がゼロであること
を意味する。データの対称性も、このタイプの符号化が最適に機能するために望
まれる特性である。すなわち、負および正の値の指数的減少が、情報スパイクの
いずれの側においても有益である。このような物理データの例には、ＥＣＧおよ
び他の生物測定（ｂｉｏｍｅｔｒｉｃ）タイプのデータが含まれる。

【００３１】 符号化の数学的説明 図２および図３を参照して上で論じられた変換および符号化および復号の数学
的説明が、次に提供される。以下のステップが、符号化アルゴリズムを定義する
。

【００３２】 １．イメージアレイｘ（ｍ，ｎ）、ｍ＝０，１，．．．，Ｍ−１、ｎ＝０，１
，．．．，Ｎ−１が与えられると、そのウェーブレット変換係数Ｘ（ｒ，ｓ）、
ｒ＝０，１，．．．，Ｍ−１、ｓ＝０，１，．．．，Ｎ−１を計算する。

【００３３】 ２．各係数Ｘ（ｒ，ｓ）が、以下に従って量子化される。

【００３４】

【数１】

【００３５】 ただし、ｓｇｎ（・）は通常のシグナム（ｓｉｇｎｕｍ）関数であり、Ｔは量子
化しきい値である。このステップは、連続のウェーブレット係数Ｘ（ｒ，ｓ）を
整数のシーケンスｑ（ｒ，ｓ）にマップする。これは、情報損失を導入する唯一
のステップである。

【００３６】 ３．量子化された係数が並べ替えられ、以下に従ってブロックにグループ化さ
れる。

【００３７】

【数２】

【００３８】 ｌ＝０，１，．．．，Ｌ−１およびｋ＝０，１，．．．，Ｋ−１では、Ｌ＝Ｍ_Ｂ Ｎ_Ｂがブロックサイズであれば、Ｋ＝ＭＮ／Ｌがブロックの総数であり、Ｍ_Ｂお
よびＮ_ＢがＭ_Ｂ＝Ｍ／２^ＪおよびＮ_Ｂ＝Ｎ／２^Ｊによって定義される。パラメー
タＪが、ｕ_ｋ（ｌ）にグループ化される量子化された係数の方形ブロックのサイ
ズ、よってブロックサイズを制御する。

【００３９】 各ｋでは、左上隅の指標（ｒ_ｋ，ｓ_ｋ）が、先に記載された走査順序に従って
定義される。

【００４０】 ４．ブロックが、固定サイズＬＫ_ＢのマクロブロックＵ_ｉに、Ｕ_ｉ＝｛ｕ_ｋ（
ｌ）｝の形式でグループ化され、ｋ＝ｉＫ_Ｂ，ｉＫ_Ｂ＋１，．．．，ｉＫ_Ｂ＋Ｋ _Ｂ −１である。各マクロブロックでは、そのビットプレーンが、適応ランレング
ス／Ｒｉｃｅ（ＲＬＲ）符号化器に従って、連続して量子化される。Ｕ_ｉのため
のＲＬＲコードによって使用されたビット数の二進符号化と、その後に続く実際
のＲＬＲ出力ビットが、出力ビットストリームに追加される。

【００４１】 次いで、以下のステップが使用されて、ＰＷＣビットストリームが復号される
。

【００４２】 １．マクロブロックＵ_ｉにおけるＲＬＲ符号化ビットを、ｉ＝０，１，．．．
，Ｉ_ｍａｘ−１について復号する。Ｉ_ｍａｘ＜Ｋであった場合、ウェーブレット
係数のより低解像度のバージョンが回復される。所望の復元精度が与えられると
、各マクロブロック内で、最初の少数のビットプレーンのみが復号されることに
留意されたい。復号しないように選択されるビットプレーンｑ（ｒ，ｓ）におけ
るすべてのビットが、ゼロに設定される。解像度のスケーラビリティが、Ｉ_{ｍａ ｘ} ＜Ｋを選択することによって達成されるが、忠実性のスケーラビリティは、各
マクロブロックのためのビットプレーンの部分集合のみを復号することによって
達成される。

【００４３】 ２．ｑ（ｒ，ｓ）を回復した後、ウェーブレット係数が以下によって復元され
る。

【００４４】

【数３】

【００４５】 （３）における復元規則と結合された（２）における量子化規則が、原点の周
囲に不感帯を有する一様量子化器を含み、これが、ラプラシアン（ダブルサイド
エクスポーネンシャル）確率分布を有するランダム変数の最小エントロピースカ
ラ量子化について最適であることに近いことに留意されたい。

【００４６】 ＰＷＣ符号化器のステップ３において記載されたように、ウェーブレット係数
を並べ替えるため、左上隅の指標（ｒ_ｋ，ｓ_ｋ）のシーケンスが定義される。図
４で示された走査順序が使用され、Ｍ_Ｂ＝Ｍ／２^ＪおよびＮ_Ｂ＝Ｎ／２^Ｊが各ブ
ロックのサイズを制御する。パラメータＪは、ブロックゼロが正確に、最も粗い
解像度ですべてのウェーブレット係数、例えば、すべてのスケーリング関数の係
数を含むように、選択されるべきである。したがって、Ｊは、ウェーブレット変
換で使用された解像度レベルの数（ツリー深度）に等しくするべきである。これ
は、図４の、すべての左上隅の指標（ｒ_ｋ，ｓ_ｋ）のシーケンスから推断するこ
とが容易である。

【００４７】 図４から、いかなる所望のレベルの解像度でも完全な係数の集合を復号するた
めに、インデックス０からＫ_ｍａｘ−１までのすべてのブロックを使用すること
が望ましいことが明らかであり、Ｋ_ｍａｘは４の累乗である。したがって、ＰＷ
Ｃ復号器のステップ１では、Ｋ_ｍａｘが４の累乗であるようにＩ_ｍａｘ−１が選
択される。

【００４８】 同一解像度レベル内の低高（ＬＨ）および高低（ＨＬ）ウェーブレット係数の
代替走査の理由は、簡素である。元のイメージが特定の特徴（または特徴なし）
をある空間位置で有すると仮定すると、その位置に対応するＬＨおよびＨＬサブ
バンドのクラスタが、大きい（あるいは小さい）値を有する可能性が高い。した
がって、同一空間位置に対応するＬＨおよびＨＬサブバンドからのこのペアのブ
ロックが、マクロブロックにおいて連続して、あるいは、少なくとも近似して、
あるいは、互いに接近して見えるようにすることによって、大小の値のクラスタ
を作成する可能性がより高い。これが、量子化された係数のビットプレーンにお
ける長いゼロのランの確率を増大させる。

【００４９】 図７のフローチャートは、図４に示された順序において係数のブロックを書く
ために使用されたアルゴリズムを記載する。アルゴリズムは、コンピュータプロ
グラム命令において、あるいは、ハードウェア、ファームウェア、または望まれ
るようなすべての組合せにおいて実施することができる。アルゴリズムが開始ブ
ロック７１０で入力される。７１５で、Ｍ×Ｎの量子化されたウェーブレット係
数を含む入力行列Ｑが読み取られる。係数は、量子化ブロック２２０によって提
供されたものなどである。７２０で、ウェーブレットレベルの数が、周知の方法
でＪＷとして定義される。ブロック７２５で、ブロックサイズがＮＨ×ＮＶとし
て定義され、ＮＨはＭ／（２^ＪＷ）に等しく、ＮＶはＮ／（２^ＪＷ）に等しい。
次いで、７３０で、最初の出力ブロックが書き込まれ、ＩＨおよびＩＶがそれぞ
れＮＨおよびＮＶとして初期化され、これは、サイズがより大きいさらなるブロ
ックの書込みのためのループを定義することにおける使用のためである。簡素化
された例では、図４において、行列Ｑが１６×１６であり、４レベルであり、ブ
ロックサイズが１であると仮定する。これが、初期の１のＩＨおよびＩＶを提供
する。さらなる例では、ブロックサイズがより大きく、８×８または１６×１６
など、またはさらに高いものなどである。

【００５０】 判断ブロック７４０が使用されて、係数の行列全体が書き込まれたかどうかが
、ＩＨがＭ未満であるかどうかを調べるために検査することによって決定される
。ＩＨがなおＭ未満であった場合、より多くの係数が書き込まれる必要がある。
図４を見るとわかるように、最初の係数のブロックは１×１のサイズであり、次
いで、これらが２×２および４×４などに増大する。次の集合のフローチャート
のブロックが使用されて、続くブロックが書き込まれ、これは、１から、ブロッ
ク７４５でＩＨ／ＮＨとして設定されるブロックサイズパラメータＮＢＬＫへル
ープすることによる。７５０でＩを使用して、７５５でＪを使用して定義された
入れ子ループが使用されて、７６０で、出力ブロックＬＨおよびＨＬの書込みの
順序が制御される。ＪがＮＥＸＴ文７６２でインクリメントされ、ＩがＮＥＸＴ
文７６４でインクリメントされる。これは、このブロックの行が最初にこの特定
の実施において書き込まれる結果となる。列も、望まれた場合は最初に書き込ま
れることが可能であり、あるいは、いかなる他の順序の書込みも使用することが
できる。初めてループを介して、１６×１６のサイズおよび４レベルの行列が与
えられると、ＮＢＬＫも１であり、そのためブロック４３０および４４０のみが
書き込まれる。

【００５１】 ＬＨおよびＨＬブロックの書込みの後に続いて、７７０および７７５で、第２
の入れ子ループの集合（ｓｅｔ）が、再度ＩおよびＪを使用してセットアップさ
れて、７８０で出力ブロックを書き込むための位置が定義される。この出力ブロ
ックは同一レベルのＨＨブロックに対応し、これは最初に通過するブロック４５
０である。ＮＥＸＴ ＪおよびＮＥＸＴ Ｉ文が入れ子ループを、それぞれ７８
２および７８４で完了する。ＨＨブロックが、上のＬＨおよびＨＬブロックと同
時に書き込まれている可能性もあり、これは、入れ子ループが等しいためである
ことに留意されたい。このレベルのすべてのブロックが書き込まれた後、７９０
で、ＩＨおよびＩＶが２の指数としてインクリメントされ、次いで、７４０で比
較されて、ＩＨがなおＭ未満であるかどうかが調べられる。ＩＨがＭ未満でなか
った場合、７９５で、アルゴリズムが、本発明による完全な並べ替えられたウェ
ーブレット係数の集合を提供した後、終了する。

【００５２】 ２回目に入れ子ループを介して、ブロック４５５、４６０および４７０が書き
込まれ、その後に、３回目に入れ子ループを介してブロック４８０、４７５およ
び４９０が続く。より高いレベルを有する、より大きい行列のサイズも企図され
る。

【００５３】 復号のために元の順序を回復するため、単に、並べ替えアルゴリズムの出力を
、それが書き込まれた方法と同一方法で読み取ることができる。必要とされるも
のは、元の行列のサイズ、および、書き込まれたレベルの数の知識だけである。
次いで、書込み順序が単に逆にされて、係数が元の順序で提供される。直接マッ
ピングも使用することができるが、著しい追加の帯域幅を設ける必要がある。

【００５４】 ビットプレーン符号化の詳細 符号化ブロック２４０によって実行された処理は、表１の図の助けによってよ
り容易に理解することができる。ビットプレーンは単に、入力の量子化されたウ
ェーブレット係数または他のデータの二進表現（絶対値＋符号）における、特定
のインデックスのビットのシーケンスである。例えば、表１は、値のシーケンス
｛９，−６，１，０，−２，３，−４，−１，２｝のためのビットプレーンを示
す。この表では、ビットプレーン４がシーケンス｛１００００００００｝であり
、ビットプレーン３がシーケンス｛０１００００１００｝であり、ビットプレー
ン２がシーケンス｛０１００１１００１｝であり、ビットプレーン１がシーケン
ス｛１０１００１０１０｝である。

【００５５】

【表１】

【００５６】 表１における入力データでは、より小さい絶対値の値が発生する可能性がより
高いようであり、これは、量子化されたウェーブレットデータおよび有限アルフ
ァベットデータの典型でもある。上のパターンから、より高いビットプレーンが
、より高いゼロの頻度を示す傾向があることがわかり、これは、より高い絶対値
の入力値がより可能性が少ないためである。ビットプレーン１（最下位のビット
）および符号ビットプレーン（ｓｉｇｎ ｂｉｔ ｐｌａｎｅ）は典型的には、
ほぼ等しい頻度のゼロおよび１を有する。

【００５７】 図５のフローチャートは、ビットプレーンを介して入力データを効率的に符号
化するためのアルゴリズムを記載し、５０５で開始する。５１０で、ビットプレ
ーンが最初に、Ｎ個の数値を含む入力バッファｘから読み取られる。５１５で、
ビットプレーン数ｂｍａｘが計算され、５２０で、有効フラグベクトルｓｆｌｇ
がすべてゼロに設定される。

【００５８】 ５２５で、ビットプレーンインデックス変数ビットがｂｍａｘに等しく設定さ
れ、そのため符号化が最上位のビットプレーンで開始する。５３０で、インデッ
クス「ｂｉｔ」によってポイントされたビットの値が、ビットプレーンベクトル
ｂｐを形成する。ブロック５３５および５４０で示されたように、各プレーンｂ
ｐについて、ビットが２つの部分集合に分割される。ｘ１は、「１」エントリが
より高いプレーンにおいて見られていない位置に対応し、これらが有効ビットと
呼ばれる。ｘ２は、「１」が既により高いプレーンにおいて見られている位置に
対応し、これらがリファインビット（ｒｅｆｉｎｅｍｅｎｔ ｂｉｔｓ）と呼ば
れる。

【００５９】 ブロック５４５で、ｘ１が、適応ランレングスＧｏｌｏｍｂ−Ｒｉｃｅ（ＡＲ
ＬＧＲ）符号化器により符号化され、これは、ｘ１におけるより高いゼロの頻度
から利益を得る。ｘ１において１に等しいあらゆるビットについて、符号ビット
も符号化され、出力コードの最後に追加される。

【００６０】 ブロック５５０で、ｘ２が直線二進符号化により符号化される。これは、ｘ２
ビットを出力ストリームに追加することによって行われる。符号化効率における
最小損失に遭遇し、これは、ゼロおよび１が、ｘ２では通常、等しく可能性があ
るためである。

【００６１】 符号ビットはビットプレーンとは呼ばれず、これは、これらがビットプレーン
として処理されないためであることに留意されたい。符号ビットは、各ビットプ
レーンのｘ１ベクトルを符号化する処理において送信される。したがって、ベク
トルｘ１を、アルファベットから引き出されるもの｛０，＋１，−１｝、すなわ
ちビットおよび符号であると見なすこともできる。

【００６２】 図５におけるフローチャートの重要な特性は、どれがｘ１に属するビットであ
るか、および、どれがｘ２に属するビットであるかについての情報が、明示的に
符号化される必要がないことである。ベクトルｓｆｌｇがビットの割振りをｘ１
に制御し、ｓｆｌｇが最初にすべてゼロに初期化され、次いで、各ビットプレー
ンが符号化された後に５５５で更新される。したがって、復号器が容易にｓｆｌ
ｇへの変更を追跡することができる。次のビットプレーンに継続するため、５６
０でｂｉｔがデクリメントされ、５６５で、最後のプレーンが復号されたかどう
かを調べるために検査される。そうでなかった場合、制御が、次のビットプレー
ンの符号化のためにブロック５３０へ進む。ｂｉｔがゼロに等しかったか、ある
いは、より低解像度の符号化が望まれた場合はより高い数であった場合、５７０
で、すべてのｘ１およびｘ２符号化の出力を含む出力バッファが書き込まれ、５
７５で処理が終了する。

【００６３】 適応ランレングス＋Ｇｏｌｏｍｂ−Ｒｉｃｅ（ＡＲＬＧＲ）符号化器は、符号
化利得が存在するところにある。これは、多数のゼロを有する長いベクトルｘ１
を、より少ないゼロを有するより小さいコードにおいてマップする。ＡＲＬＧＲ
符号化器を、以下に示されたように、関連付けられた符号ビットを有するか、あ
るいは、有していない二進シーケンスを符号化することに使用することができる
。ＡＲＧＬＲ符号化器を理解するために、最初に、ランレングス符号化およびＧ
ｏｌｏｍｂ−Ｒｉｃｅ符号化の基礎を考察されたい。

【００６４】 その一般的な形式では、ランレングス（ＲＬ）符号化の背景にある基本的な考
えは、入力データベクトルにおける同一値の長いストリングを、繰り返される値
およびその値が何回繰り返されるべきであるかを指定するコードによって、置き
替えることである。このような反復ストリングが十分長く、十分多かった場合、
ＲＬ符号化が、データベクトルを表現するために必要とされるビット数における
著しい低減に通じる。

【００６５】 ＲＬ符号化を、０または１のいずれかが現れる可能性が著しくより高い、二進
データの符号化に適用することができる。一例は、グラフィックスファイルにお
いて、例えば、白の背景においてデジタル化された黒の描画である。白い画素（
ピクセル）が０に等しいビットによって表現され、黒の点が１に等しいビットに
よって表現された場合、ゼロの方が現れる可能性がはるかに高いことが明らかで
ある。実際に、多数の標準のグラフィックスファイルフォーマットが、ＲＬ符号
化を使用している。

【００６６】 １９６６年、Ｇｏｌｏｍｂが、正の数の表現のための簡素なコードを提案した
。数が幾何学的確率分布を有するソースから引き出された場合、すなわち、Ｐｒ
ｏｂ｛ｘ＝ｎ｝＝ａｂ^ｎであり、ａおよびｂがパラメータであった場合、Ｇｏｌ
ｏｍｂコードが本当に最適（予想された最小の長さ）であることが、後に示され
た。数年後、Ｒｉｃｅが無関係に、実際に実施することが大変容易であるＧｏｌ
ｏｍｂコードの部分集合を導出した。これらのコードが、Ｇｏｌｏｍｂ−Ｒｉｃ
ｅコードとして知られるようになった。

【００６７】 本発明では、二進数のソースのためのＧｏｌｏｍｂ−Ｒｉｃｅコードが、ＲＬ
コードと結合される。結果として生じたランレングス＝Ｇｏｌｏｍｂ−Ｒｉｃｅ
コードが、表２に示される。このコードは、パラメータｋによって特徴付けられ
、これがコードワード０に関連付けられたランの長さを制御し、この最大ランレ
ングスは２^ｋに等しい。

【００６８】

【表２】

【００６９】 以前に記載されたビットプレーン符号化器におけるｘ１ベクトルの符号化では
、符号を、ゼロでない各ビットのコードワードに追加する必要がある。そのため
、ＲＬＧＲコードの簡素な拡張が、表３に示されたように使用される。

【００７０】

【表３】

【００７１】 入力ベクトルの所与のソースでは、｛０，１｝または｛０，＋１，−１｝アル
ファベットのいずれかを使用して、パラメータｋが、予想されたコード長を最小
にするために選択されるべきである。ソースがメモリを有しておらず、経時的に
一定の統計量を有し、Ｐ_０＝Ｐｒｏｂ｛シンボル＝０｝によって特徴付けられた
場合、ｋの最適値をＰ_０の関数として計算することが容易である。

【００７２】 しかし、実際には、二進（または二進＋符号）ベクトルは定常ではない。典型
的な例は、ピクチャまたは走査された文書の量子化されたウェーブレット係数な
ど、物理的世界から得られたデータを含む。したがって、ＲＬＧＲパラメータｋ
を経時的に調整して、データのローカルな統計量に最適に合致させる必要がある
。多数の戦略（ｓｔｒａｔｅｇｉｅｓ）が考察されており、たいていは入力デー
タを適切な長さのブロックに分割することを含む。各ブロックについて、Ｐ_０が
推定され、次いで、ｋの最適値が計算される。次いで、追加のコードが各ブロッ
クの始めで送信されてｋの値が示され、これが復号器によって使用されるべきで
ある。

【００７３】 符号化器２４０は新しい手法を採る。バックワード適応戦略（ｂａｃｋｗａｒ
ｄ ａｄａｐｔｉｖｅ ｓｔｒａｔｅｇｙ）が、ＲＬＧＲパラメータｋを変更す
るために使用される。バックワード適応によって、ｋにおける変化が、直接的に
入力データではなく、符号化されたシンボルに基づいて計算されることを意味す
る。基本戦略は、次のシンボルを符号化することにおいて使用されるｋの値が、
先に符号化されたデータにのみ依存するべきであるということである。したがっ
て、復号器が、変化するｋの値を回復するために行う必要のあることは、符号化
器と同一適合規則を適用することだけである。したがって、復号を簡素化するた
めに、このような規則を、計算するために可能な限り簡素にすることが重要であ
る。

【００７４】 新しい適応ランレングス＋Ｇｏｌｏｍｂ−Ｒｉｃｅ（ＡＲＬＧＲ）符号化器２
４０は、パラメータｋを変更するための以下の規則を使用する。ブロック６０４
で、いくつかのパラメータが最初に定義される。スケールファクタＬが最初に定
義され、これが使用されて、ｋｐがＬ＊ｋとして定義される。ｋｐは補助パラメ
ータであり、その値が、それぞれ量ＵｐまたはＤｎだけ上がるかあるいは下がり
、ｋの小数の移動を、浮動小数点演算の使用なしに許可する。最後に、Ｕｑが定
義され、これが使用されて、出力コードがゼロであり、かつｋがゼロに等しかっ
た場合、ｋｐが上に移動される。６０６で、入力バッファｘが読み取られ、Ｍ個
の数値を含む。６０８で、ｋがｋ０に設定され、ｋｐがＬ＊ｋに設定され、ｒｕ
ｎが０に設定される。この処理は、入力データの長期の統計量のためによい選択
であるｋの値、例えば、ｋ＝２で開始される。６１０で、最初のシンボルｘｉｎ
ｄｅｘ＝１で開始して、シンボルがｘ（ｘｉｎｄｅｘ）に設定され、ｒｕｎｍａ
ｘが２^ｋに設定される。

【００７５】 符号化処理の概観として、ソースシンボルを符号化した後、ｋｐが、送られた
出力コードに基づいて調整される。出力コードが０であり、ｋ≠０であった場合
、ｋｐが所定のインクリメントステップＵｐでインクリメントされ、すなわち、
ｋｐ＝ｋｐ＋Ｕｐに設定される。出力コードが０であり、ｋ＝０であった場合、
ｋｐが所定のインクリメントステップＵｑでインクリメントされ、すなわち、ｋ
ｐ＝ｋｐ＋Ｕｑに設定される。出力コードが１で開始した場合（ゼロでない入力
に対応する）、ｋｐが所定のデクリメントステップＤｎでデクリメントされ、す
なわち、ｋｐ＝ｋｐ−Ｄｎに設定される。次の入力シンボルを符号化するための
ｋの値が、ｋ＝［ｋｐ／Ｌ］に設定される（すなわち、ｋｐ／Ｌを最も近い整数
に切り捨てる）。

【００７６】 このアルゴリズムは簡素な戦略に基づいている。ゼロのランに遭遇した場合、
ｋが増加されて、より長いシーケンスのゼロを、単一の出力ビット＝０によって
取り込むことができるようにする。ゼロでないシンボルに遭遇した場合、ｋが減
少されて、過度に長い出力コードが回避される。上の補助パラメータｋｐおよび
スケールファクタＬの使用が、小数ステップにおけるｋの調整を、上に示された
ように浮動小数点演算を使用する必要なく、可能にする。

【００７７】 ＡＲＬＧＲ符号化器において試験されたデータの大部分では、性能が、以下の
パラメータの典型的な選択、すなわち、Ｌ＝４、Ｕｐ＝４、Ｄｎ＝５およびＵｑ
＝２について、きわめてよかった（符号化率がソースエントロピーに大変接近す
る）。いくつかの場合、これらのパラメータにおける調整が、さらにわずかに高
性能に通じる可能性がある。

【００７８】 図６におけるフローチャートの説明に戻ると、ブロック６０２、６０４、６０
６、６０８、６１０および６１２を参照して、上に記載されたような、後に続く
パラメータの初期化および定義が、６１４で最初に検査されて、それがゼロに等
しいかどうかが調べられる。そうであった場合、かつ、ｓｙｍｂｏｌがゼロであ
った場合、６１８でＵｑがｋｐに加算される。６２０でゼロが出力バッファに追
加され、６２２で、ｋｐが範囲外、すなわちｋｐｍａｘを超えた場合、これがク
リップされる。６２４で、ｋが、スケールファクタｋｐ／Ｌ未満の最大整数に設
定される。次いで、Ｘｉｎｄｅｘがインクリメントされ、６２８で決定されたと
きにＭ未満であった場合、６１２で次のｓｙｍｂｏｌが選択される。Ｍより大き
かった場合、６３０で出力ビットバッファが書き込まれ、６４０で処理が終了す
る。

【００７９】 判断ブロック６１６に戻って参照すると、ｓｙｍｂｏｌがゼロに等しくなかっ
た場合、６４２で、１が出力ビットバッファに追加され、６４４で、データが符
号ビットを有した場合、ｓｙｍｂｏｌの符号ビットが出力ビットバッファに追加
され、処理が６２２に進んで、ｋｐが範囲内であるかどうかを調べるために検査
する。

【００８０】 ブロック６１４で、ｋが１に等しくなかった場合、６５０で、ｓｙｍｂｏｌの
さらなる検査が実行される。ｓｙｍｂｏｌがゼロに等しくなかった場合、６５２
で、１が出力ビットバッファに追加され、６５４で、ｒｕｎのｋビット値が出力
ビットバッファに追加される。６５６で、Ｄｎがｋｐから減算され、処理が６４
４へ進み、任意選択の符号ビットが追加される。

【００８１】 ６５０で、ｓｙｍｂｏｌがゼロであると判明した場合、６２２でｒｕｎが検査
されて、これがｒｕｎｍａｘに等しいかどうかが調べられる。そうでなかった場
合、６２２で、ｋｐがｋｐｍａｘを超えないようにクリップされる。６６２で、
ｒｕｎがｒｕｎｍａｘに等しかった場合、６６４で、０が出力ビットバッファに
追加され、６６６で、ｒｕｎがゼロに設定される。最後に、Ｕｐがｋｐに加算さ
れ、処理が再度、ｋｐのクリップのためにブロック６２２へ戻り、６２４でｋの
設定、６２６でｘｉｎｄｅｘをインクリメントし、６２８で、最後のシンボルが
処理されたかどうかを調べるために検査する。そうであった場合、６３０で情報
が出力ビットバッファに書き込まれ、６４０で処理が終了する。

【００８２】 表４において、量子化されたウェーブレット係数におけるビットプレーン符号
化器を使用した結果が示される。簡素なビットプレーン符号化器が、計算的によ
り簡素であるにもかかわらず、適応算術符号化器（これらが最新式であると見な
されている）よりもよく実行することに留意されたい。

【００８３】

【表４】

【００８４】 この符号化器の主な利点は、算術符号化器によって共有されていない、スケー
ラビリティである。記載されたビットプレーン符号化により、より低忠実性のバ
ージョンの信号を、プレーン１より高いビットプレーンで復号処理を停止するこ
とによって、容易に得ることができる。これは、情報のプログレッシブ伝送およ
び復元、および、インターネットなど、通信チャネルの重要な機能を可能にする
。もう１つのスケーラビリティの応用例は、例えば、デジタルカメラにおけるも
のである。ユーザがより多数のピクチャを撮影することを望み、既に格納された
ピクチャの品質を犠牲にすることをいとわなかった場合、既存のイメージのより
低いビットプレーンを除去して、新しいピクチャのためにストレージを開放する
ことができる。

【００８５】 ＡＲＬＧＲ符号化器を、ビットプレーン符号化器におけるその使用に関連して
記載するが、これは、値０が値１よりもおそらくはるかに多い二進データのため
の汎用符号化器として、大変有用である可能性がある。これは特に、確率分布が
絶えず変化している場合において真である。例えば、４８０×６４０ピクセルの
解像度で走査された白黒の描画を符号化する問題を考察する。白＝０および黒＝
１のマッピングを仮定すると、ＡＲＬＧＲ符号化器を直接データへ適用すること
ができる。しかし、符号化器２４０は、１のランをあまりよく処理せず、そのた
め、差分演算子が最初にピクセルのすべての行に渡って適用される。２番目の行
で開始して下へ移動し、各ピクセル値が、上の行における同じピクセルと同一色
を有した場合は０で、異なる色を有した場合は１で置き替えられる。これが、列
に渡って繰り返される。結果として生じたビットが、ＡＲＬＧＲ符号化器２４０
により符号化される。

【００８６】 これが、白または黒のランの、ゼロのランへのマッピングを提供し、情報のい
かなる損失もない。これにより、データがＡＲＬＧＲ符号化により適切となる。
表５は、このような簡素な符号化器の性能の、他の手法との比較を示す。

【００８７】

【表５】

【００８８】 ＡＲＬＧＲ符号化器２４０アルゴリズムは、標準のファックス符号化アルゴリ
ズムより、性能がほぼ２倍すぐれている。これは、ファックスアルゴリズムによ
って使用されたバイトの５５％のみを使用する。実際に、新しいＡＲＬＧＲに基
づいた符号化器は、最新式の適応算術符号化器にすら、この特定のイメージでは
小さい差で優った。加えて、これは最低の計算上の複雑性を有した。これは単な
る一例であり、この結果が、使用されたイメージおよびパラメータの調整に応じ
て変わる可能性があることに留意されたい。

【００８９】 図８において、一式のオフィスプログラムのブロック図が、８１０で概して図
示される。１つの特定のオフィス（登録商標）一式は、８１２で示された複数の
高レベルアプリケーションを含み、文書処理、Ｅメール、スプレッドシート、プ
レゼンテーションツール、写真操作プログラムおよびブラウザなどのアプリケー
ションを含む。これらのアプリケーションをサポートすることは、８２６および
８１８の、少なくとも２レベル低いソフトウェア、ハードウェア、またはそれら
の組合せの機能である。図示された機能は、ビデオイン／アウト機能８２６およ
びファックス／スキャナ機能８１８を含む。多数の他の機能もこのレベルで存在
することができる。

【００９０】 詳細には、ビデオ機能が、ビデオを表示し、ビデオおよびイメージデータを外
部ソースから受信するための能力を提供する。ビデオおよびファックス／スキャ
ナ機能が、本明細書に記載され、ブロック８３２に示された符号化器および復号
器を利用して、先に記載されたような符号化および復号機能を提供する。生のイ
メージまたは他の適切なデータが、ピクセルまたは他の形式において取り込まれ
、符号化器８３２が使用されてこれを符号化する。さらに、符号化されたデータ
が、本明細書に記載されたタイプの符号化を使用するいずれかのソースから得ら
れた場合、８３２の復号器が、それを受信するアプリケーションによって呼び出
されて、それを表示可能あるいは使用可能なフォーマットに変換あるいは復号す
る。

【００９１】 Ｍｉｃｒｏｓｏｆｔ Ｏｆｆｉｃｅ（登録商標）、または、より多数のアプリ
ケーションも統合することができる後続の製品など、統合されたオフィス一式な
どを含むことができる多数のアプリケーションが、圧縮あるいは解凍（ｄｅｃｏ
ｍｐｒｅｓｓ）される必要のあるデータを処理する可能性がますます高いことに
留意されたい。本発明は、他の形式の符号化の代替物を提供し、これはＪＰＥＧ
に存在するブロッキングアーチファクトを除去し、ソフトウェア、ハードウェア
、または、望まれたような混成形式において、実施することがより複雑でない。
８３２の符号化器／復号器も、このようなオフィス一式に統合することが容易で
ある。

【００９２】 結論 量子化されたウェーブレット係数の並べ替えが実行され、データ依存型データ
構造を使用する必要なしに大小のウェーブレット係数が分離したグループにクラ
スタ化される。次いで、係数が適応的に、ランレングスコードに基づいて符号化
され、これは、量子化された係数のストリングを表現するために使用されたコー
ドワードを制御するパラメータを継続的に修正し、コードワードにおいて使用さ
れたビット数を最小化することを求める。順序付けパターンが固定され、係数符
号化が、各イメージについて修正されたテーブルを必要としないので、本発明は
、より容易なハードウェアまたはソフトウェア実施に役立つ。さらなる利点には
、ブロッキングアーチファクトの解消、および、イメージデータのためのいかな
る所望の圧縮率のための単一パス符号化も含まれる。

【００９３】 上の符号化およびブロッキングを逆の順序で適用する復号器が記載される。符
号化された係数の復号が最初に実行され、その後に係数のアンシャッフルが続く
。次いで、アンシャッフルされた係数が、逆ウェーブレット変換を受けて、イメ
ージピクセルなど、変換され圧縮されたデータが回復される。適応算術符号化を
、並べ替えに関連して使用して、類似の圧縮の利点を得ることもできるが、わず
かに高い複雑さを伴う。

【００９４】 ゼロツリーなど、データ依存型データ構造、または、ツリーにおける集合区画
のための別々のリストの使用を必要としないことによって、ハードウェア実施が
より構築しやすい。この応用例は、本発明のいかなる適合または変形形態をも包
含することを意図されるものである。本発明が特許請求の範囲およびその均等物
によってのみ限定されることが、明白に意図されるものである。

【図面の簡単な説明】

【図１】 本発明を実施することができるコンピュータシステムのブロック図である。

【図２】 ウェーブレット係数を並べ替え、次いで、ロスレス適応方法において符号化す
る符号化器のブロック図である。

【図３】 図２の符号化器によって生成された、符号化された係数を復号かつアンシャッ
フルする復号器のブロック図である。

【図４】 図２の符号化器によって生成された、並べ替えられたウェーブレット係数のブ
ロック図である。

【図５】 係数をビットプレーンに分離する、図２の係数符号化器の高レベルの動作を示
すフローチャートである。

【図６】 図２のランレングス適応符号化器の動作のさらなる詳細を示すフローチャート
である。

【図７】 図４に示されたものに適合する、並べ替えられた方法における、係数の行列の
書込みを示すフローチャートである。

【図８】 図２の符号化器および図３の復号器の、イメージデータを処理するソフトウェ
アアプリケーション一式における使用を示すブロック図である。

【手続補正書】特許協力条約第３４条補正の翻訳文提出書

【提出日】平成１３年４月１２日（２００１．４．１２）

【手続補正１】

【補正対象書類名】明細書

【補正対象項目名】特許請求の範囲

【補正方法】変更

【補正の内容】

【特許請求の範囲】

【手続補正２】

【補正対象書類名】明細書

【補正対象項目名】０００１

【補正方法】変更

【補正の内容】

【０００１】 （発明の分野） 本発明は、一般にイメージ圧縮の分野に関し、詳細には、デジタルビクチャの
改善されたウェーブレット符号化および復号に関する。

【手続補正３】

【補正対象書類名】明細書

【補正対象項目名】０００９

【補正方法】変更

【補正の内容】

【０００９】 ウェーブレット係数を順序付けするためのゼロツリーに基づく手法の複雑さに
対する１つの解決策が、Ｏｒｄｅｎｔｌｉｃｈ Ｅ．他の文献、「Ａ ｌｏｗ
ｃｏｍｐｌｅｘｉｔｙ ｍｏｄｅｌｉｎｇ ａｐｐｒｏａｃｈ ｆｏｒ ｅｍｂ
ｅｄｄｅｄ ｃｏｄｉｎｇ ｏｆ ｗａｖｅｌｅｔ ｃｏｍｐｒｅｓｓｉｏｎ
ｃｏｅｆｆｉｃｉｅｎｔｓ」 Ｐｒｏｃｅｅｄｉｎｇｓ ＤＣＣ ′９８Ｄａｔ
ａ Ｃｏｍｐｒｅｓｓｉｏｎ Ｃｏｎｆｅｒｅｎｃｅ（ＣＡＴ．Ｎｏ．９８ＴＢ
１００２２５），Ｐｒｏｃｅｅｄｉｎｇｓ ＤＣＣ ′９８Ｄａｔａ Ｃｏｍｐ
ｒｅｓｓｉｏｎ Ｃｏｎｆｅｒｅｎｃｅ，Ｓｎｏｗｂｉｒｄ，ＵＴ，ＵＳＡ，３
０Ｍａｒｃｈ−１ Ａｐｒｉｌ １９９８，ｐａｇｅ４０８−４１７，ＸＰ００
０９２５０９６ １９９８ ＬｏｓＡｌａｍｉｔｏｓ，ＣＡ，ＵＳＡ，ＩＥＥＥ
Ｃｏｍｐｕｔ．Ｓｏｃ，ＵＳＡ ＩＳＢＮ ０−８１８６−８４０６−２によ
り開示されている。Ｏｒｄｅｎｔｌｉｃｈは２段階のプロセスを開示しており、
そこでは係数の一集合（ａ ｓｅｔ ｏｆ ｃｏｅｆｆｉｃｉｅｎｃｅｓ）が、
その集合の外にある、前もって符号化された情報に応じて複数の係数の集合に分
解される。第２の段階では、選択される順序付け（ｏｒｄｅｒｉｎｇ）によって
制約される通常のコンテキストモデル化を使用して複数の係数の集合を分解する
。この場合、結果として生じるキャラクタは、適応ランレングスＧｏｌｏｍｂ−
Ｒｉｃｅ符号化器を使用して符号化される。 ウェーブレット圧縮係数および同様の有限アルファベットデータに作用し、ハ
ードウェアやソフトウェアでも実施されるような、簡素な符号化技術への要求が
ある。

───────────────────────────────────────────────────── フロントページの続き (31)優先権主張番号 ０９／２７６，９５４ (32)優先日 平成11年３月26日(1999．3．26) (33)優先権主張国 米国（ＵＳ） (81)指定国 ＥＰ(ＡＴ，ＢＥ，ＣＨ，ＣＹ， ＤＥ，ＤＫ，ＥＳ，ＦＩ，ＦＲ，ＧＢ，ＧＲ，ＩＥ，Ｉ Ｔ，ＬＵ，ＭＣ，ＮＬ，ＰＴ，ＳＥ)，ＯＡ(ＢＦ，ＢＪ ，ＣＦ，ＣＧ，ＣＩ，ＣＭ，ＧＡ，ＧＮ，ＧＷ，ＭＬ， ＭＲ，ＮＥ，ＳＮ，ＴＤ，ＴＧ)，ＡＰ(ＧＨ，ＧＭ，Ｋ Ｅ，ＬＳ，ＭＷ，ＳＤ，ＳＬ，ＳＺ，ＴＺ，ＵＧ，ＺＷ )，ＥＡ(ＡＭ，ＡＺ，ＢＹ，ＫＧ，ＫＺ，ＭＤ，ＲＵ， ＴＪ，ＴＭ)，ＡＥ，ＡＧ，ＡＬ，ＡＭ，ＡＴ，ＡＵ， ＡＺ，ＢＡ，ＢＢ，ＢＧ，ＢＲ，ＢＹ，ＣＡ，ＣＨ，Ｃ Ｎ，ＣＲ，ＣＵ，ＣＺ，ＤＥ，ＤＫ，ＤＭ，ＤＺ，ＥＥ ，ＥＳ，ＦＩ，ＧＢ，ＧＤ，ＧＥ，ＧＨ，ＧＭ，ＨＲ， ＨＵ，ＩＤ，ＩＬ，ＩＮ，ＩＳ，ＪＰ，ＫＥ，ＫＧ，Ｋ Ｐ，ＫＲ，ＫＺ，ＬＣ，ＬＫ，ＬＲ，ＬＳ，ＬＴ，ＬＵ ，ＬＶ，ＭＡ，ＭＤ，ＭＧ，ＭＫ，ＭＮ，ＭＷ，ＭＸ， ＮＯ，ＮＺ，ＰＬ，ＰＴ，ＲＯ，ＲＵ，ＳＤ，ＳＥ，Ｓ Ｇ，ＳＩ，ＳＫ，ＳＬ，ＴＪ，ＴＭ，ＴＲ，ＴＴ，ＴＺ ，ＵＡ，ＵＧ，ＵＺ，ＶＮ，ＹＵ，ＺＡ，ＺＷ Ｆターム(参考） 5C059 MA24 MA32 MA35 MC04 MC11 MC30 MC38 ME06 ME08 ME11 ME17 PP01 PP02 PP24 SS20 SS26 TA46 TB17 TC00 UA02 UA05 UA06 UA29 UA39 5C078 AA04 BA53 CA31 DA01 DA02 DB19 EA08 5J064 AA04 BA08 BA16 BC16 BC26

Claims (30)

【特許請求の範囲】
1. 【請求項１】 有限アルファベットデータキャラクタを符号化する方法であ
   って、 適応ランレングス符号化器のストリング長を初期化すること、 符号化パラメータに基づいて前記ストリング長を修正すること、および、 既に符号化されたキャラクタに基づいて前記符号化パラメータを修正すること
   を含むことを特徴とする方法。
2. 【請求項２】 前記符号化パラメータは、予想されたキャラクタに遭遇する
   たびに増加されることを特徴とする請求項１に記載の方法。
3. 【請求項３】 前記予想されたキャラクタはゼロであることを特徴とする請
   求項２に記載の方法。
4. 【請求項４】 前記符号化パラメータは、予想されたキャラクタに遭遇しな
   いたびに減少されることを特徴とする請求項１に記載の方法。
5. 【請求項５】 前記予想されたキャラクタはゼロであることを特徴とする請
   求項４に記載の方法。
6. 【請求項６】 前記キャラクタは、ビットプレーンに基づいて符号化される
   ことを特徴とする請求項１に記載の方法。
7. 【請求項７】 最下位のビットプレーンは、二進符号化を使用して符号化さ
   れることを特徴とする請求項６に記載の方法。
8. 【請求項８】 前記符号化の解像度を修正するために最上位のビットプレー
   ンのみが符号化されることを特徴とする請求項６に記載の方法。
9. 【請求項９】 ゼロのストリングは、小さい値によって表現されることを特
   徴とする請求項１に記載の方法。
10. 【請求項１０】 より長いストリングについて一般により短い値によってス
    トリングを表現すること、および、プロジレッシブ符号化されたビットストリー
    ムを提供することをさらに含むことを特徴とする請求項１に記載の方法。
11. 【請求項１１】 請求項１に記載の方法をコンピュータに実行させる命令が
    格納されていることを特徴とするコンピュータ読取り可能媒体。
12. 【請求項１２】 有限アルファベットデータを符号化する方法であって、 適応ランレングス符号化器のストリング長を初期化すること、および、 累乗ｋによって前記ストリング長を修正することを含み、ｋは適応パラメータ
    であり、さらに、 ゼロが符号化されるたびに前記適応パラメータｋを増加すること、および、 １が符号化されるたびに前記適応パラメータｋを減少することを含み、ストリ
    ング長は、ビットプレーンに基づいて符号化されるシンボルによって表現される
    こと を特徴とする方法。
13. 【請求項１３】 ｋは整数であり、符号化パラメータを一度に小数だけイン
    クリメントするためにスケールファクタＬが使用されることを特徴とする請求項
    １２に記載の方法。
14. 【請求項１４】 前記データはウェーブレット変換係数を含むことを特徴と
    する請求項１２に記載の方法。
15. 【請求項１５】 前記データは生物測定値を表すことを特徴とする請求項１
    ２に記載の方法。
16. 【請求項１６】 前記データは、ファックスされるイメージの走査を表すこ
    とを特徴とする請求項１２に記載の方法。
17. 【請求項１７】 有限アルファベットデータを符号化するための符号化器で
    あって、 適応ランレングス符号化器のストリング長を初期化する手段と、 符号化パラメータに基づいて前記ストリング長を修正する手段と、 既に符号化されたデータに基づいて前記符号化パラメータを修正する手段と を含むことを特徴とする符号化器。
18. 【請求項１８】 コンピュータによって復号するための圧縮されたイメージ
    を表現するデータ構造が格納されているコンピュータ読取り可能媒体であって、
    前記データ構造は、 １およびゼロのストリングを表現する複数の値と、 選択されたストリングの長さを修正するために使用される、先に符号化された
    データに基づいて選択されたゼロのストリングに関連付けられた符号化パラメー
    タと を含むことを特徴とするコンピュータ読取り可能媒体。
19. 【請求項１９】 請求項１８の符号化器によって符号化されたデータを復号
    することを特徴とする復号器。
20. 【請求項２０】 バックワード適応ランレングス符号化を使用して、符号化
    された有限アルファベットデータキャラクタを復号する方法であって、 適応ランレングス復号器のストリング長を初期化すること、 復号パラメータに基づいて前記ストリング長を修正すること、および、 既に復号されたキャラクタに基づいて前記符号化パラメータを修正すること を含むことを特徴とする方法。
21. 【請求項２１】 前記復号パラメータは、予想されたキャラクタに遭遇する
    たびに増加されることを特徴とする請求項２０に記載の方法。
22. 【請求項２２】 前記予想されたキャラクタはゼロであることを特徴とする
    請求項２２に記載の方法。
23. 【請求項２３】 前記復号パラメータは、予想されたキャラクタに遭遇しな
    いたびに減少されることを特徴とする請求項２０に記載の方法。
24. 【請求項２４】 前記予想されたキャラクタはゼロであることを特徴とする
    請求項２３に記載の方法。
25. 【請求項２５】 前記キャラクタはビットプレーンに基づいて復号されるこ
    とを特徴とする請求項２０に記載の方法。
26. 【請求項２６】 最下位のビットプレーンは、二進符号化を使用して復号さ
    れることを特徴とする請求項２５に記載の方法。
27. 【請求項２７】 前記復号の解像度を修正するために最上位のビットプレー
    ンのみが復号されることを特徴とする請求項２６に記載の方法。
28. 【請求項２８】 ゼロのストリングは、小さい値によって表現されることを
    特徴とする請求項２０に記載の方法。
29. 【請求項２９】 バックワード適応ランレングス符号化を使用して、符号化
    された有限アルファベットデータキャラクタを復号する方法をコンピュータに実
    行させるためのコンピュータ実行可能命令が格納されているコンピュータ読取り
    可能媒体であって、前記方法は、 適応ランレングス復号器のストリング長を初期化すること、 復号パラメータに基づいて前記ストリング長を修正すること、および、 既に復号されたキャラクタに基づいて前記符号化パラメータを修正すること を含むことを特徴とするコンピュータ読取り可能媒体。
30. 【請求項３０】 有限アルファベットデータを復号するための復号器であっ
    て、 適応ランレングス符号化されたデータを復号するためのストリング長を初期化
    する手段と、 復号パラメータに基づいて前記ストリング長を修正する手段と、 既に復号されたデータに基づいて前記符号化パラメータを修正する手段と を含むことを特徴とする復号器。