(57)【要約】複合イメージを圧縮する方法、システムおよびプログラムであって、複合イメージデータを複数のブロックになるように形成すること、複数の上記ブロックの各々に対し複数のクラスからの１つを指定する分類データを、ブロックの優位な圧縮特性に基づいて取得すること、複数の上記ブロックの各々に対し、ブロックの分類データに基づいて選択された非可逆または可逆変換のいずれかから変換データを取得すること、その変換データを１つのエントロピー符号器に送出することと、を含む。一実施形態では、変換データを取得することは、変換のための分類データに基づいて、非可逆変換、第１の可逆変換または第２の可逆変換のうちの少なくとも１つから変換データを取得することを含む。
2004530341.tif 000002
【特許請求の範囲】
【請求項１】
複合イメージを圧縮する方法であって、
複合イメージデータを複数のブロックになるように形成するステップと、
複数の前記ブロックの各々に対し複数のクラスからの１つを指定する分類データを、前記ブロックの優位な圧縮特性に基づいて取得するステップと、
複数の前記ブロックの各々に対し、該ブロックに対する前記分類データに基づいて選択された非可逆または可逆変換のいずれかから変換データを取得するステップと、
その変換データを１つのエントロピー符号器に送出するステップと、
を含む方法。
【請求項２】
前記分類データを取得することは、そのブロックに関連するページ記述言語での情報に基づいて分類データを取得することを含む、請求項１記載の方法。
【請求項３】
前記分類データを取得するステップは、値が所定数より大きい絶対差分だけ異なる、走査線順での隣接するピクセルの数Ｃと、分類される前記ブロックにおけるピクセルの最小値と最大値との差Ｄと、少なくとも１つの閾値Ｔ１と、のパラメータに基づいて、前記ブロックを分類することを含む、請求項４記載の方法。
【請求項４】
前記変換データを取得するステップは、前記分類データに基づいて前記ブロックデータを前記可逆変換かまたは前記非可逆変換だけを通して送ることを含む、請求項１記載の方法。
【請求項５】
前記変換データを取得するステップは、前記ブロックデータを前記可逆変換と前記非可逆変換との両方を通して送ること、その後、前記分類データに基づいて前記変換データとしてこれらの変換のうちの１つから前記データを選択することと、を含む、請求項１記載の方法。
【請求項６】
非可逆変換と前記可逆変換との間の変化を信号で知らせるために、特別なシンボルを前記エントロピー符号器のためのエントロピーテーブルに追加する請求項１記載の方法。
【請求項７】
前記変換データを取得するステップは、前記変換のための前記分類データに基づいて、非可逆変換、第１の可逆変換または第２の可逆変換のうちの少なくとも１つから変換データを取得することを含み、
前記非可逆変換ブロックと前記第１の可逆変換ブロックと前記第２の可逆変換ブロックとの間の変化を信号で知らせるために、２つの特別なシンボルを前記エントロピー符号器のためのエントロピーテーブルに追加する請求項１記載の方法。
【請求項８】
複合イメージを圧縮するシステムであって、
複合イメージデータを複数のブロックになるように形成するブロック形成器と、
複数の前記ブロックの各々に対し複数のクラスからの１つを指定する分類データを、前記ブロックの優位な圧縮特性に基づいて取得する第１のコンポーネントと、
複数の前記ブロックの各々に対し、該ブロックの前記分類データに基づいて選択された非可逆または可逆変換のいずれかから変換データを取得する第２のコンポーネントと、
前記変換データを受取る単一エントロピー符号器と、
を具備するシステム。
【請求項９】
前記第１のコンポーネントは、前記ブロックの前記優位な圧縮特性に基づいて前記ブロックを分類する分類器を備える、請求項８記載のシステム。
【請求項１０】
前記第２のコンポーネントは、前記ブロックを処理するために、少なくとも１つの非可逆変換コンポーネントと、第１の可逆変換コンポーネントと、第２の可逆変換コンポーネントと、を備える、請求項８記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して複合イメージの圧縮の分野に関し、特に、複数の変換を使用して複合イメージを圧縮するが変換データを１つのエントロピー符号器にのみ供給する、方法、構造およびプログラム製品に関する。
【背景技術】
【０００２】
イメージ圧縮は、必要なメモリと内部伝送帯域幅との両方を低減するために、ハードコピー装置（プリンタ、スキャナ）において広く使用される。それら装置によって処理される通常のページは、複合イメージ、すなわち、写真（コントーン（contone））イメージ、図形およびテキストを含むページである。複合文書に対する最良の圧縮性能は、異なるイメージタイプに対して異なる圧縮方法が適用される場合に得られる、ということは確立した事実である。A. SaidおよびA. Drukarevによる「Simplified segmentation for compound image compression」、1999 IEEE International Conference on Image Processing、Kobe、Japan、October 1999を参照のこと。たとえば、写真イメージを処理する最良の方法は、ＪＰＥＧ等、何らかの形態の非可逆圧縮を使用することである。一方、可逆圧縮は、テキストおよび図形に最も適しており、それは、非可逆方法に比較して最良の画質と最良の圧縮とをもたらす。
【０００３】
複合ページのための種々の圧縮方法を使用する必要があることにより、装置において複数のコーデック（コンプレッサ／デコンプレッサ）を使用することに基づくソリューションにたどりつく。たとえば、装置パイプラインにおいてＪＰＥＧコーデック（８×８ブロックでのみ作用する）とＪＰＥＧ−ＬＳコーデック（個々のラインでのみ作用する）とを使用することができ、いずれのページまたはページのいずれの部分をいずれのコーデックで処理すべきかを判断するためにインテリジェントセグメンテーションを使用することができる。この手法により、優れた圧縮性能がもたらされるが、複数のコーデックをサポートしなければならないためシステムの複雑性が増大する。さらに、ＪＰＥＧとＪＰＥＧ  ＬＳ（または他の可逆圧縮方法）との間で基礎となる圧縮アルゴリズムが著しく異なるため、特にハードウェアベース実施態様の場合、それらをともに同じデジタル化されたページで結合することは非常に困難である。かかる結合が困難である一つの重要な理由は、コーデックが異なるセグメント（８×８ブロック対個々のライン）で作用するため、続く変換のための処理に互換性がない、ということである。この場合の最も適当なソリューションは、ページタイプによって、非可逆方法かまたは可逆方法のいずれかをページ全体かまたはページストライプに適用する、というものである。しかしながら、同じ圧縮をページラインのグループに対して使用しなければならないため、テキストと写真とが並んでいる場合、これは問題を解決しない。
【０００４】
ＪＰＥＧ規格の操作および圧縮性能は、以下の通りである。ＪＰＥＧ圧縮のための通常のイメージパスは、以下のステップを含む。イメージが読出され、色変換が実行される。たとえば、ＲＧＢ色空間における入力イメージがＹＣｂＣｒ空間に変換される。色変換後、各色成分が個々に圧縮される。多くの場合、３色成分のうちの２つ（クロミナンス成分、ＣｂおよびＣｒ）が、２または４の係数によってダウンサンプリングされる。各色成分に対して実行されるＪＰＥＧ圧縮における４つの異なる操作は、以下の通りである。
【０００５】
１．ＤＣＴ（離散コサイン変換）
２．量子化
３．量子化された係数のジグザグ走査およびハフマンまたは算術符号化を含む、エントロピー符号化
４．ビットストリーム管理、ここでは、ＪＰＥＧ規格のシンタックス規則にしたがってエントロピー符号器からのコードワードを出力ビットストリームに書く。
【０００６】
ＪＰＥＧ圧縮は、写真イメージにおいて非常にうまく働く。それは、比較的高い圧縮率で視覚的に無損失の（loseless：可逆）圧縮を達成する。
【０００７】
量子化テーブルを、ハフマンテーブルと同様に、異なるタイプの写真イメージと異なる圧縮率とに対して最適な性能を達成するように設計することができる。
【０００８】
図形またはテキスト等、非写真イメージの場合、ＪＰＥＧ規格はそれほど優れた結果をもたらさない。ＤＣＴアーティファクト（歪み、ぼけおよびオリジナルイメージにはない他の効果）は、比較的低圧縮率であっても可視である。以下の簡単な例は、テキストを圧縮するＪＰＥＧの非効率を例示する。２５５にマップされる白レベルと０にマップされる黒レベルとを有する２値イメージを考慮する。ＲＧＢピクチャの２４ビット／ピクセルフォーマットから２値フォーマットへの単純なマッピングは、ピクチャ品質に損失無しに２４：１の圧縮率を提供する。２４：１の圧縮率でテキストに対し視覚的に無損失な性能を達成することは、ＪＰＥＧの場合に非常に困難となる。その理由は、ＤＣＴである。ＤＣＴ符号化は、多くの高周波数コンテンツを含むかまたは入力値の輝度が数レベルしかないブロックでは、うまく働かない。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
本発明は、一実施形態では、複合イメージを圧縮する方法であって、複合イメージデータを複数のブロックになるように形成するステップと、複数のブロックの各々に対し複数のクラスからの１つを指定する分類データを、ブロックの優位な圧縮特性に基づいて取得するステップと、複数のブロックの各々に対し、ブロックに対する分類データに基づいて選択された非可逆または可逆変換のいずれかから変換データを取得するステップと、その変換データを１つのエントロピー符号器に送出するステップと、を含む方法を含む。
【課題を解決するための手段】
【００１０】
本発明のさらなる態様では、ページデータを形成するステップは、ＪＰＥＧ規格と互換性のあるブロックを形成することを含む。
【００１１】
本発明のさらなる態様では、分類データを取得することは、そのブロックに関連するページ記述言語での情報に基づいて分類データを取得することを含む。
【００１２】
本発明のさらなる態様では、非可逆変換はＤＣＴである。
【００１３】
本発明のさらなる態様では、分類データを取得するステップは、値が所定数より大きい絶対差分だけ異なる、走査線順での隣接するピクセルの数Ｃと、分類されているブロックにおけるピクセルの最小値と最大値との差Ｄと、少なくとも１つの閾値Ｔ１と、のパラメータに基づいて、ブロックを分類することを含む。
【００１４】
本発明のさらなる態様では、少なくとも２つの閾値Ｔ１およびＴ２があり、ＣがＴ１より大きい場合、ＤＣＴからのデータが変換データとして使用され、ＣがＴ１以下でありＤがＴ２以下である場合、ＤＣＴからのデータが変換データとして使用され、ＣがＴ１以下でありＤがＴ２より大きい場合、可逆変換からのデータが変換データとして使用される。
【００１５】
本発明のさらなる態様では、変換データを取得するステップは、分類データに基づいてブロックデータを可逆変換かまたは非可逆変換だけを通して送ることを含む。
【００１６】
本発明のさらなる態様では、変換データを取得するステップは、ブロックデータを可逆変換と非可逆変換との両方を通して送ること、その後、分類データに基づいて変換データとしてこれらの変換のうちの１つからデータを選択することと、を含む。
【００１７】
本発明のさらなる態様では、非可逆変換と前記可逆変換との間の変化を信号で知らせるために、特別のシンボルがエントロピー符号器のためのエントロピーテーブルに追加される。
【００１８】
本発明のさらなる態様では、エントロピー符号器に送出するステップは、以下のように先のブロックと現ブロックとの差分を符号化することを含む。すなわち、先のブロックがＤＣＴブロックであり、現ブロックがＤＣＴである場合、現ブロックのＤＣ値と先のブロックのＤＣ値との差分が符号化され、先のブロックがＬＴブロックであり、現ブロックがＤＣＴである場合、現ＤＣＴブロックのＤＣ値と先のＬＴブロックのｙ（０）値との差分が符号化され、先のブロックがＤＣＴブロックであり、現ブロックがＬＴである場合、ｙ（０）値と先のブロックのＤＣ値との差分が符号化され、先のブロックがＬＴブロックであり、現ブロックがＬＴである場合、現ブロックのｙ（０）値と先のブロックのｙ（０）との差分が符号化される。
【００１９】
本発明のさらなる態様では、イメージの第１のブロックはＤＣＴブロックである。
【００２０】
本発明のさらなる態様では、変換データを取得するステップは、変換のための分類データに基づいて、非可逆変換、第１の可逆変換または第２の可逆変換のうちの少なくとも１つから変換データを取得することを含む。
【００２１】
本発明のさらなる態様では、分類データを取得するステップは、値が所定閾値より大きい絶対差分だけ異なる、走査線順での隣接するピクセルの数Ｃと、分類されているブロックにおけるピクセルの最小値と最大値との差Ｄと、ブロックにおける色の数Ｎと、少なくとも２つの閾値Ｔ１およびＴ２と、のパラメータに基づいて、ブロックを分類することを含む。
【００２２】
本発明のさらなる態様では、分類データを取得するステップにおいて、Ｎが２以下である場合、第２の可逆変換からのデータを変換データとして使用し、ＤがＴ２より大きくＣがＴ１以下である場合、第１の可逆変換からのデータを変換データとして使用し、それ以外は、ＤＣＴからのデータを変換データとして使用する。
【００２３】
本発明のさらなる態様では、第２の可逆変換の場合、ブロックのピクセルの輝度値には、２つのレベルＶ０およびＶ１のみが割当てられ、その後それらは、輝度値Ｖ０を有するピクセルが０にマップされ、値Ｖ１を有するピクセルが１にマップされることでマップされ、その後、ピクセルにビットごとのＸＯＲ操作を適用し、「ビットパッキング」を実行することにより１ビットのみにより結果としての量ｙ（ｉ）を表す。
【００２４】
本発明のさらなる態様では、非可逆変換ブロックと第１の可逆変換ブロックと第２の可逆変換ブロックとの間の変化を信号で知らせるために、２つの特別なシンボルがエントロピー符号器のためのエントロピーテーブルに追加される。
【００２５】
本発明のさらなる態様では、本発明は、ブロックが非可逆ブロックか可逆ブロックかに基づき、複数の異なるハフマンテーブルからの１つの符号化に使用するために、エントロピー符号器を選択することを含む。
【００２６】
本発明のさらなる態様では、複合イメージを圧縮するシステムであって、複合イメージデータを複数のブロックになるように形成するブロック形成器と、複数のブロックの各々に対し複数のクラスからの１つを指定する分類データを、ブロックの優位な圧縮特性に基づいて取得する第１のコンポーネントと、複数のブロックの各々に対し、ブロックの分類データに基づいて選択された非可逆または可逆変換のいずれかから変換データを取得する第２のコンポーネントと、変換データを受取る単一エントロピー符号器と、を備えるシステムが提供される。
【００２７】
本発明のさらなる実施形態では、複合イメージを圧縮するコンピュータ読取可能プログラムコードを含むプログラム製品であって、複合イメージデータを複数のブロックになるように形成する第１のコードと、複数のブロックの各々に対し複数のクラスからの１つを指定する分類データを、ブロックの優位な圧縮特性に基づいて取得する第２のコードと、複数のブロックの各々に対し、ブロックに対する分類データに基づいて選択された非可逆または可逆変換のいずれかから変換データを取得する第３のコードと、変換データを受取りエントロピー符号化する第４のコードと、を含むプログラム製品が提供される。
【発明を実施するための最良の形態】
【００２８】
本発明の２つの実施形態を説明するが、これらの実施形態は単に例示的なものであり、本発明はそれらに限定されない。第１の実施形態、ＪＡＤＥ−１は、複雑性の最も低いバージョンである。第２の実施形態、ＪＡＤＥ−ＩＩは、複雑性がわずかに高いが、特にテキストおよび単純な図形のイメージに対して、より高い圧縮率を達成する。
【００２９】
１．１  ＪＡＤＥ−Ｉ
上述したように、イメージの異なる部分に対して異なる圧縮方法が使用される場合、複合イメージにおいて最適な圧縮性能が達成される。本発明によれば、複合イメージは、複数のイメージクラスに分割され、そこでは、各クラスは圧縮に関して同様の特性を有するイメージデータとして定義される。そして、各クラスに対して、異なる圧縮アルゴリズムかまたは同じアルゴリズムに対する異なるパラメータ設定を使用することができるが、互換性のあるフォーマットを使用し、それにより両アルゴリズムに対して後続の処理を実質的に同じにすることができる。
【００３０】
例示的な実施形態に対して実施態様を単純なままにするために、イメージ部分が２つのクラスに分類されるシステムを提供する。それらクラスは、大まかに、写真イメージタイプとテキスト／図形イメージタイプとに対応する。本設計は、ＪＰＥＧまたは他の所定フォーマットと互換性があることが好ましい。たとえばＪＰＥＧフォーマットと一貫性を保つために、例として、各色成分について８×８イメージブロックに対し、分類が実行される。本発明は、このサイズまたは構成のブロックに限定されない。
【００３１】
限定としてではなく例として、非可逆圧縮の場合、変更がまったく無いかまたは最小の変更で、ＪＰＥＧ規格を都合よく使用することができる。可逆圧縮の場合、本発明は可能な限りＪＰＥＧシステムの一部を使用する。しかしながら、入力ピクセルの直接的なハフマン符号化は、可逆圧縮のそれほど効率的ではない形態である。したがって、可逆圧縮は、本発明の一実施形態において、可逆圧縮パスにおいて特別に設計された可逆変換を使用することによって達成される。この実施形態における特別に選択された変換は、イメージサンプルの相関をなくす（decorrelate）役割を果たし、それによりシステムの可逆圧縮性能を大幅に向上させる。この実施形態、ＪＡＤＥ−Ｉのブロック図を、図１Ａおよび図１Ｂに示す。
【００３２】
図１Ａを参照すると、本発明の第１実施形態を実施する構成が示されている。ライン１０に、複合イメージデータが入力される。データは通常、ピクチャ、テキストおよび図形のデータを含む。データは、その一般的な意味で使用される「ページ」と呼ぶプリントジョブの、所定部分に対するものであることが好ましい。ライン１０のページデータは、ブロック形成器１２に供給され、ブロック形成器１２は、ページデータを複数の変換によって使用するために都合のよいブロックにセグメント化する。本発明では、「ブロック」という用語は、各セグメントのデータが連続しているページデータセグメンテーションを包含するように広く定義される。
【００３３】
そして、ブロックは、色空間変換器（ＣＳＣ）１４に供給されることにより、好ましい色空間に変換される。限定としてではなく例として、変換器１４は、本技術分野において既知である標準変換アルゴリズムを使用して、ブロックをＹＣｂＣｒ空間に変換してもよい。ライン１６によって表すようにこの変換の前か、もしくはライン１８によって表すようにこの変換の後に、信号は分類器２０に供給される。分類器２０は、各ブロックのデータを、そのブロックの優勢の圧縮特性に基づいて、複数のクラスからの１つに分類するように動作する。使用してもよい分類アルゴリズムの例を、下に論考する。多くのシステムでは、色空間変換（ＣＳＣ）は、バッファリングされたイメージブロックに対して発生するため、ＣＳＣ１４における色空間変換と並列に分類器２０におけるイメージ分類に必要な動作を実行することが都合がよい場合がある（ただし必須ではない）。分類器２０に入力されるライン１６を使用することにより、このＣＳＣと並列の分類動作が容易になる。
【００３４】
ＣＳＣ１４からの出力は、少なくとも２つの異なる変換に適用される。変換のうちの少なくとも１つは、図１の実施例においてＤＣＴブロック２２と呼ぶ非可逆変換であり、変換のうちの少なくとも１つは、図１の実施例においてＬＴ２４と呼ぶ可逆変換である。好ましい実施形態では、ブロック２２における非可逆変換は、単純に、ＪＰＥＧ規格で使用される離散コサイン変換によって実施される。しかしながら、本発明の互換性要件を満たす他のいかなる非可逆変換を利用してもよい。そして、ＤＣＴ２２からの変換データは、量子化器２６に適用される。量子化器２６を、あり得る変換値の数をより少ない数に変換する機能を達成する種々の異なる量子化方法によって実施してもよい（N.S. JayantおよびP. Nollによる「Digital Coding of Waveforms (Ch.4)」、Prentice-Hall、Englewood Cliffs、NJ、1984を参照のこと）。限定としてではなく例として、量子化器２６を、量子化されたステップサイズで正規化される量子化ＤＣＴ係数を取得するために標準ＪＰＥＧ量子化器によって実施してもよい。ＪＰＥＧ規格（Ｔ．８１）の２８ページの上部の式を参照のこと。可逆変換ＬＴ２４については後述する。
【００３５】
その後、ＬＴ２４からの出力と量子化器２６を介するＤＣＴ変換からの出力とは、判断ブロック３０に加えられ、判断ブロック３０は、これらの出力のうちの１つを、そのブロックデータをさらに処理するために送られる変換データとして選択するように動作する。限定としてではなく例として、判断ブロック３０を、分類器２０からの信号によって制御されるスイッチによって実施することができる。分類器２０からの分類信号は、ブロックが、主としてピクチャに対するデータを含むことを示す場合、ＤＣＴ変換からの出力が選択される。代替的に、分類器２０からの分類信号が、ブロックが主としてテキストに対するデータを含むことを示す場合、ＬＴ２４からの出力が選択される。
【００３６】
図１Ａの説明から分かるように、分類器２０における分類プロセスは、ブロックからのイメージピクセルデータをそれらがＬＴ／ＤＣＴ変換ブロックに入る前に使用する。このため、イメージブロックを、両変換チャネルに並列に送ることができ、スイッチ３０を、通常はエントロピー符号器を含む符号器ＥＮＣ３２での続く処理にデータが送られる直前に、分類器２０からの分類結果に基づいて動作させることができる。
【００３７】
好ましくはソフトウェアを使用するがハードウェアを使用しても実施可能である代替実施形態において、分類プロセスを、ブロックのピクセルデータが変換処理パイプラインに入る前に完了してもよく、それによってブロックは、非可逆または可逆チャネルの両方ではなくいずれかに送られる。この実施態様を、図１Ｂに示す。同じブロックを、同一のナンバリングで提示する。構成の相違は、スイッチ４０が、変換チャネルに入る前に設けられ、分類器２０からの出力信号に基づいてブロックデータの入力に対して変換チャネルのうちの１つを選択するために使用される、ということである。このように、ブロックデータは、両方の変換によって変換されることはない。
【００３８】
好ましい実施形態では、図１Ａおよび図１Ｂに関して説明したすべての操作が、１つの色成分に関連する。この実施形態、すなわちＪＡＤＥ−Ｉは、ＪＰＥＧとの互換性を提供するために、すべての色平面を独立して扱う。また、この実施形態例では、隣接する色成分の依存性を活用しない。これは、システムの複雑性を最小限に維持するために好ましい。
【００３９】
１．２  分類
上述したように、分類器２０の目的は、写真（連続階調すなわちコントーン）イメージタイプブロックとテキスト／図形タイプブロックとを識別することである。なお、目標は、複合ページを写真イメージ、テキストおよび図形部分に正確に分解することではない。そうではなく、たとえばテキストおよび図形のような特徴（色がほとんど無い、同じ色が長く続く、鮮鋭なエッジ）を有すると識別されたブロックが確定される。テキストおよび／または図形として分類されるこれらのブロックは、同じように扱われる。すなわち、可逆チャネル２４を通される。他のブロックはすべて、コントーンブロックであるとみなされ、非可逆チャネル２２に送られる。
【００４０】
ここで、データを分類する１つの好ましい方法およびロジックを説明する。この方法の場合、Ｃが、値が所定の値（０または別の値等）より大きい絶対差分だけ異なる、走査線順の隣接するピクセルの数、すなわちブロックにおけるピクセル変化の数を示すものとする。Ｄが、各８×８ブロックのピクセルにおける最大値と最小値との差を示すものとする。最後に、Ｔ１およびＴ２が、何らかの所定閾値を示すものとする。そして、ブロック分類に、８ビット／ピクセルカラーイメージを用いる実験に基づいて、以下の規則を使用することができる。
【００４１】
これらのパラメータを使用する判断アルゴリズムを実施するために使用することができる決定木の一実施形態のブロック図を、図２に示す。ロジック５０においてＣ＞Ｔ１である（すなわち、ブロックが値の異なる多くのピクセルを有する）場合、ブロックは連続階調ブロックであるものとして分類され、そのブロックはＤＣＴチャネル２２を通される。ロジック５２に示すようにＣ≦Ｔ１である場合、分類決定は、Ｄの値によって決まる。Ｄ＞Ｔ２である（ブロックに大きいエッジがある）場合、ブロックは、可逆チャネルＬＴ２４を通される。Ｄ≦Ｔ２である場合、ブロックは、ＤＣＴ２２パスを通される。閾値Ｔ１、Ｔ２は、アプリケーションによって異なってよい。本設計による実験では、Ｔ２＝３２およびＴ１＝２０の値を使用した。
【００４２】
図１Ａおよび図１Ｂに示す実施形態は、本発明の分類戦略の非常に単純な実施態様を含む。要求に応じておよび設計者に課せられた処理および他の要件にしたがって、より高性能の分類方法を実現してもよい
さらなる実施形態では、分類器を、明示的に構成に含める必要はない。たとえば、ページ記述言語（ＰＤＬ）から作られるイメージを圧縮する場合、テキストおよび図形の位置に関する情報は、そのページの言語記述にすでに存在する場合がある。この場合、実施形態における別個の分類段階は不要である。ブロックのための分類を指定するＰＤＬ情報を、保存してブロックに関連付けてもよく、その後スイッチ３０または４０を動作させるために使用してもよい。限定としてではなく例として、ビット、もしくは３つ以上の分類の場合はバイトを、ブロック内のデータの１つまたは複数の項目に対するＰＤＬ言語からの分類情報によって設定してもよく、そのブロックと関連付けてもよい。スイッチ３０または４０においてそのブロックに対する決定段階に達すると、この関連する分類情報を使用してスイッチを動作させる。したがって、分類データは、アクティブに決定されるのではなく、取得される。
【００４３】
なお、分類器２０は、復号器設計にいかなる影響も与えない。符号器は、いかなる分類戦略を実施することも可能であり、あるいは符号器を、分類規則のより複雑なセットにアップグレードすることができ、符号器が、本明細書において後に定義するようにブロッククラス変化を信号で知らせるシンタックスを使用する限り、ＪＡＤＥ復号器は、符号化ビットストリームを処理することができる。
【００４４】
１．３  可逆変換
ＪＡＤＥ−Ｉ実施形態例に対して選択された可逆変換２４は、モジュロ２５６差分演算である。８×８ピクセルブロックで開始して、このブロックは、図３に示すように、長さ６４のシーケンスにマップされる。入力ピクセル値をｘ［０］、…、ｘ［６３］として示し、出力値をｙ（０）、…、ｙ［６３］として示す。そして、ＬＴの入力と出力との間の変換を、以下の式によって行う。
【００４５】
ｙ（ｎ）＝｜ｘ（ｎ）！ｘ（ｎ！１）＋３８４｜ｍｏｄ２５６！１２８
ｘ（ｎ）＝｜ｘ（ｎ！１）＋ｙ（ｎ）｜ｍｏｄ２５６
モジュロ・差分演算は、可逆変換の完全な可逆性を可能にしながら、可能な限り多くの出力０を導入しようと試みる。この実施例では、正規差分は出力のダイナミックレンジを拡張しないため、その代りにモジュロ差分演算子を選択した。すなわち、出力値ｙ（０）、…ｙ［６３］は、符号付き８ビット整数である。なお、各輝度値が８ビット量であるため、それらの差分は、通常、９ビット（符号付き）量として表される、ということに留意されたい。８ビットのみを使用してその差分をいかに表すことができるかを見るために、まず、ｘ［ｎ］の所与の値の各々に対し、差分は２５６の異なる値のみを有することができる、すなわち、それを１バイトで表すことができる、ということに留意されたい。上記変換のセットは、この観察を利用し、入力値の完全な復元を可能にする。
【００４６】
上に示した可逆変換を、以下の「Ｃ」言語表現を使用して容易に計算することができる。
【００４７】
ｙ（ｎ）＝（ｃｈａｒ）（ｘ（ｎ）！ｘ（ｎ！１））
ｘ（ｎ）＝（ｃｈａｒ）（ｘ（ｎ！１）÷ｙ（ｎ））
これらの式は、ＰｅｎｔｉｕｍベースＰＣおよび一般的なＵＮＩＸワークステーションで使用される２の補数算法に対して有効である。なお、ハードウェアにおいて、ＪＰＥＧエンジンのスループットを維持するために、ＤＣＴアルゴリズム２２と並列にＬＴ２４を実施することができる、ということに留意されたい。
【００４８】
１．４  エントロピー符号化およびＤＣＴとＬＴとの間のスイッチの信号制御
要素３２によって表すエントロピー符号化プロセスを説明するために、非可逆ＤＣＴ３２パスを通されるブロックをＤＣＴブロックと呼び、ＬＴ２４パスを通るブロックをＬＴブロックと呼ぶ。ＤＣＴパスを通るブロックのエントロピー符号化は、ＪＰＥＧエントロピー符号化と厳密に同じである。唯一の相違は、ＬＴブロックのすぐ後に続くＤＣＴブロックのＤＣ成分が処理される方法である。ＪＰＥＧでは、現ブロックと先のブロックとのＤＣ値の差分が符号化される。ＪＡＤＥでは、符号化される差分は以下の通りである。先のブロックがＤＣＴブロックであり、現ブロックがＤＣＴである場合、現ブロックのＤＣ値と先のブロックのＤＣ値との差分が符号化され、先のブロックがＬＴブロックであり、現ブロックがＤＣＴである場合、現ＤＣＴブロックのＤＣ値と先のＬＴブロックのｙ（０）値との差分が符号化され、先のブロックがＤＣＴブロックであり、現ブロックがＬＴである場合、ｙ（０）値と先のブロックのＤＣ値との差分が符号化され、先のブロックがＬＴブロックであり、現ブロックがＬＴである場合、現ブロックのｙ（０）値と先のブロックのｙ（０）との差分が符号化される。
【００４９】
ＬＴブロックのエントロピー符号化は、ＪＰＥＧエントロピー符号化フレームワークを保存するように設計される。ＬＴブロックのｙ（０）の符号化は、それがＤＣ係数であるように行われる。すなわち、現ＬＴブロックと先のＬＴブロックとにおけるｙ（０）の値の差分が符号化される（なお、ｙ（０）は、ＤＣ係数と同様の特性を有するが、「ＤＣ」という術語は、従来、ＤＣＴおよび同様の変換に対してのみ使用される、ということに留意されたい）。ＬＴブロックがＤＣＴブロックのすぐ後に続く場合、現ブロックのｙ（０）と先のブロックのＤＣ値との差分が符号化される。可逆変換の出力における他のすべての値、ｙ［１］、…ｙ［６３］は、それらがＡＣ係数であるかのように符号化される。原則として、最良の圧縮性能は、ＤＣＴブロックとＬＴブロックとに対して異なるハフマンテーブルを使用する場合に達成される。しかしながら、ブロック境界におけるスイッチングテーブルは、高速ハードウェア実施態様に対して行うことは困難である可能性がある。本実施態様では、ＤＣＴブロックとＬＴブロックとの両方に対して同じハフマンテーブルを使用した。
【００５０】
２つの別々のハフマンテーブル、すなわち１つをＤＣＴブロックに対し、１つをＬＴブロックに対し供給することが望ましい場合、かかる構成を、エントロピー符号器３２におけるスイッチを使用して、ブロックがＬＴ変換２４で処理されたかＤＣＴ変換２２で処理されたかによりテーブルを切替えることにより、実施することができる。スイッチを、たとえば、ＬＴブロック２４、ＤＣＴブロック２２および／または分類器２０からの情報によってトリガすることができる。たとえば、ブロックがＬＴブロックとして分類された場合、分類器２０からエントロピー符号器３２への信号に、ビットを設定することができるが、ブロックがＤＣＴブロックとして分類された場合は、設定することができない。
【００５１】
なお、ハフマンテーブルの生成は、本技術分野において周知であり、種々の異なる方法を使用して定式化することができる、ということに留意すべきである。限定としてではなく例として、ハフマンテーブルを、ＪＰＥＧ規格ＣＣＩＴＴ  Ｔ．８１（０９／９２）「Information Technology-Digital Compression and Coding of Continuous-Tone Still Images-Requirements and Guidelines」のＡｎｎｅｘ  Ｋにしたがって定式化することができる。なお、かかるハフマンテーブルを、イメージの大型のセットに基づいて生成することができ、あるいは、単一イメージまたはブロック毎に生成してもよい（すなわち、動的ハフマンテーブル）、ということに留意されたい。
【００５２】
ＤＣＴブロックとＬＴブロックとの間の変化の復号器への信号制御は、ＤＣエントロピー符号化テーブルにおける１つの特別なシンボルを使用することによって行われる。ＪＰＥＧは、１６までのシンボル（８ビットイメージデータの場合は１２シンボル、１２ビットデータの場合は１６シンボル、可逆圧縮の場合は１７シンボル）を有してもよいＤＣ符号化テーブルを使用する。W.B. PennebakerおよびJ.L. Mitchellによる「JPEG still image data compression standard」、Van Nostrand Reinhold、New York、1993を参照のこと。さらに、ＪＰＥＧ規格に対する拡張、「Information technology - digital compression and coding of continuous-tone still images: Extensions」、ISO/IEC 10918-3、ITU-T Recommendation T.84 (1996E)、1996、p.32は、あらゆる量子化に対して使用される１つの特別なシンボルを導入した。この特別なシンボルの数値は、X'15'（Xは１６進表現を表す）である。ＪＡＤＥを使用する本発明の実施形態は、ＤＣテーブルにもう１つシンボルを追加することによりブロックタイプスイッチを指定する。このシンボルは、BL_SWITCH＝X'16'である。このシンボルは、ブロックタイプが先のブロックと異なる場合、エントロピー符号化の前にブロックの第１のシンボルとして挿入される。ブロックにおける要素の残り（ＤＣ／ＡＣ値、ＬＴ値）は、標準ブロックと厳密に同じである。ブロックスイッチシンボルを挿入する規則を、表１に示す。
【００５３】
ブロックスイッチシンボル
【表１】
2004530341.tif 000003
【００５４】
好ましい実施形態では、すべてのＪＰＥＧマーカとＪＰＥＧのビットストリームの特徴とが、いかなる変更も無しにＪＡＤＥに保存される。ＪＡＤＥは、イメージの第１のブロックがＤＣＴブロックであるという規約を使用する。これにより、複合ぺージ全体がコントーンイメージを表す場合に、完全ＪＰＥＧ互換性ストリームの生成が可能になる。
【００５５】
２．  ＪＡＤＥ−ＩＩ実施形態
ＪＡＤＥ−Ｉの実施形態で使用される可逆変換は、非常に単純な可逆変換と分類戦略とに基づいていた。さらなる実施形態では、より高性能な分類戦略を用いる、わずかにより複雑な変換を使用してもよい。この実施形態は、なお極めて単純であり、複数のイメージに対するＪＡＤＥ実施形態の性能に比較して顕著な改良をもたらす。
【００５６】
複合ページの非連続階調部の多くの領域が、均等色背景上の単色テキストを表す。これらの領域は、ＪＡＤＥ−Ｉ分類器２０により可逆チャネルに送られる。ＪＡＤＥ−Ｉは、これらの領域の優れた圧縮を提供するが、テキスト領域が２色しか含まず、そのためより効率的に圧縮することができる、という事実を利用することができない。この状況に対処するために、もう１つの可逆変換をＪＡＤＥ−Ｉに追加する。ＪＡＤＥ−ＩＩと呼ばれるこの変更されたシステムのブロック図を、図４に示す。図４の下部は、非可逆チャネル（ＤＣＴ２２および量子化器２６）を表し、それは一実施形態では図１に示すものと同じであってもよい。上部は、２つの可逆変換２４および１００とそれらの対応する可逆パスＬＴ１およびＬＴ２とを含む、可逆チャネルを表す。ＬＴ２４は、例として、ＪＡＤＥ−ＩのＬＴ（モジュロ２５６差分）と同一であってもよい。ＬＴ２については後述する。
【００５７】
２．１  分類
ＪＡＤＥ−ＩＩの一実施形態における分類器１０２は、ＪＡＤＥ−Ｉに以下の追加を有するものと同一であってもよい。Ｎが、ブロックにおける色の数であるとする。そして、ブロックは、Ｎ≦２である場合にのみ可逆変換ＬＴ２  １００を通される。この状況をＪＡＤＥ−Ｉの分類状況と結合することにより、ＪＡＤＥ−ＩＩに対して以下の分類アルゴリズムが得られる。
ｉｆ  Ｎ≦２  ｄｏ  ＬＴ２；
ｅｌｓｅ  ｉｆ  （Ｄ＞Ｔ２およびＣ≦Ｔ１）  ｄｏ  ＬＴ１；
ｅｌｓｅ  ｄｏ  ＤＣＴ
【００５８】
２．２  可逆変換ＬＴ２
ここでＬＴ２  １００の動作を参照して、オリジナルイメージからの８×８ブロックのピクセルを使用する実施例を論考する。各ピクセル値が８ビットで表されるものとする。２レベルの輝度がある場合、以下のマッピングを適用することにより、非ゼロビットの数をさらに低減することができる。この状況において２レベルに対する輝度値がＶ０およびＶ１であるとすると、輝度値Ｖ０を有するすべてのピクセルを０にマップし、値Ｖ１を有するすべてのピクセルを１にマップする。そして、ビットごとのＸＯＲ（ピクセルに対する操作）を適用し、「ビットパッキング」を行う。すなわち、結果としての８ビット量ｙ［ｉ］の各々を単なる１ビット、すなわち０または１で表す。結果は６４ビット（１ビット／ピクセル）であり、それはＶ０およびＶ１の値とともに、オリジナルブロックからのピクセルの完全な表現を実現する。それら６４ビットを、ｂ［０，…，６３］とする。１０エントリベクトルを考慮する。
【００５９】
Ｇ＝｛Ｖ０，ｄＶ１，ｂ（０：７），ｂ（８：１５），…，ｂ（５６：６３）｝
量ｄＶ１は、８ビット値にマップされた、同じＬＴ２変換で処理された現ブロックのＶ１値と最後のブロックのＶ１値との差分を表す。なお、各輝度値が８ビット量であるため、それらの差分は通常、９ビット（符号付き）量として表される。差分に対して８ビットのみを使用するために、ＪＡＤＥ−Ｉで使用したものと同じ変換を使用する。現ブロックと先のブロックとにおけるＶ１の値を、それぞれＶ１ｎおよびＶ１ｎ−１として示す。そして、以下の公式は、輝度差を、範囲［−１２８，＋１２７］の８ビット量にマップする。
ｄＶ１＝｜Ｖ１ｎ！Ｖ１ｎ−１÷３８４｜ｍｏｄ２５６！１２８
Ｖ１ｎ＝｜Ｖ１ｎ−１＋ｄＶ１｜ｍｏｄ２５６
もしくは、「Ｃ」概念では
ｄＶ１＝（ｃｈａｒ）（Ｖ１ｎ！Ｖ１ｎ−１）
Ｖ１ｎ＝（ｃｈａｒ）（Ｖ１ｎ−１＋ｄＶ１）
【００６０】
ｄＶ１の初期化は、先のブロックのＶ１の値が０であったと仮定することによって実行される。すべての後続するブロックに対し、先の値は、２つの色を有するブロックとして分類された最後に認識されたブロックの値であると想定される。
【００６１】
この特定の可逆変換ＬＴ２を使用する利点は、ベクトルＧに対する式から明確である。６４ピクセルのアレイを表すために１０バイトのみが使用され、それによりエントロピー符号化の前であっても６．４：１圧縮が達成される。
【００６２】
Ｇに対する式においてＶ０およびＶ１が処理される方法に相違があるように見える。Ｖ０には直接の値が使用されるが、Ｖ１には差分が使用される。これらの量を処理する際のこの差分は、エントロピー符号器において除去される。そこでは、連続的なブロックにおけるＶ０の値自体ではなく、それらの差分が符号化される。符号器は、ブロックにおける２つの輝度値のうちのいずれに値Ｖ０が割当てられ、いずれにＶ１の値が割当てられるかを判断するために、いかなる手法を使用することも可能である。たとえば、ブロックの第１のピクセルの値をＶ０とすることができ、あるいはＶ０に先のブロックで使用したものと同じ輝度値を使用することができる。実験により、ＪＡＤＥの性能に対し輝度値の割当のいかなる顕著な影響も示されなかった。
【００６３】
図４に、データのブロックが３つの変換すべてによって処理されるように配置されたスイッチ１０４が示されており、スイッチ１０４が、エントロピー符号器３２に送られる変換データとして変換のうちの１つからデータを選択するために使用される、ということに留意すべきである。この選択は、分類器１０２によるブロックの分類に基づいて行われる。この方式は、図１Ａに示すものと非常に類似している。代替的に、図１Ｂにより、データのブロックが変換のうちの１つのみによって処理されるように、スイッチを、変換のためのパスに入る前に配置することができる。なお、図１におけるように、分類器１０２の入力を、ライン１６またはライン１８のいずれから取ってもよい。
【００６４】
２．３  エントロピー符号化およびＤＣＴとＬＴチャネルとの間のスイッチの信号制御
ＪＡＤＥ−Ｉに対して使用したものと同様の用語を使用することにより、非可逆ＤＣＴ２２を通されるブロックをＤＣＴブロックと呼び、ＬＴ１  ２４を通るブロックをＬＴ１ブロックと呼び、ＬＴ２  １００を通るブロックをＬＴ２ブロックと呼ぶ。ＤＣＴブロックとＬＴ１ブロックとのエントロピー符号化を、ＪＡＤＥ−Ｉについて上述したように実行してもよい。
【００６５】
ＬＴ１ブロックのエントロピー符号化は、ＬＴ１ブロックのものと同様に実行される。成分Ｖ０は、ＤＣ成分として扱われ、ベクトルＱの後続する成分は、１０個の最初に量子化されたＤＣＴ係数であるかのように扱われる。上述したように、ＬＴ２ブロックに対して異なるハフマンテーブルが使用される場合、最良の圧縮性能が達成される。しかしながら、ブロック境界におけるスイッチングテーブルは、高速ハードウェア実施態様に対して行うには困難である可能性がある。好ましい実施形態では、ＤＣＴ、ＬＴ１およびＬＴ２ブロックに対して同じハフマンテーブルが使用される。
【００６６】
ＤＣＴ、ＬＴ１およびＬＴ２ブロック間の変化の信号制御は、ＪＡＤＥ−Ｉにおいて行われる方法と同様に実行される。ＪＡＤＥ−ＩＩはＪＰＥＧに比較して２つの追加のチャネルを有するため、２つの特別なシンボルをＪＰＥＧエントロピーテーブルに追加しなければならない。これらのシンボルは、BL_SWITCH1=X'16'とBL_SWITCH2=X'17'とである。これらのシンボルは、ブロックタイプが先のブロックと異なる場合、エントロピー符号化の前にブロックの最初のシンボルとして挿入される。ブロックスイッチシンボルを挿入する規則を、表２に示す。
【００６７】
すべてのＪＰＥＧマーカおよびＪＰＥＧのビットストリームの特徴は、ＪＡＤＥ−ＩＩに保存される。ＪＡＤＥ−ＩＩの一実施態様では、イメージの最初のブロックがＤＣＴブロックであるという規約が使用される。これにより、複合ページ全体が連続階調イメージを表す場合に、完全なＪＰＥＧ互換性ストリームの生成が可能になる。
【００６８】
ＪＡＤＥ−ＩＩのためのブロックスイッチシンボル
【表２】
2004530341.tif 000004
【００６９】
３  実験結果
ＪＡＤＥを試験するために試験イメージの大型のセットを使用した。セットは、次のものを含む種々のタイプの９０個のイメージを含んでいた。すなわち、コントーンイメージ、ハーフトーンイメージ、図形イメージ、テキスト（白黒およびカラー）および特に、コントーン、図形およびテキストである部分を有する複合イメージである。表記を簡略化するために、イメージに１〜９０のインデックスを割当てた。特に指定のない限り、このセクションにおける図面に示すイメージインデックスとイメージタイプとの間の対応は、以下の通りである。すなわち、イメージ１、２、３は、単一色領域を表すために使用されるディザ状のハーフトーンパターンを有する図形イメージである。ピクセルレベルへ拡大すると、イメージ２および３に、繰返しのピクセルパターンが長く続いたものを見ることができる。イメージ４〜１５は、主としてコントーンイメージであり、残りは、連続階調、テキストおよび図形部分の混合である。通常、高いインデックスを有するイメージほど連続階調部分が小さく、テキストおよび／または単純な図形部分が大きい。
【００７０】
ＪＡＤＥを、２つの別個の符号器、すなわちベースラインＪＰＥＧとＪＰＥＧ  ＬＳとを有する基準システムと比較した。基準システムの動作のデフォルトモードは、ＪＰＥＧ  ＬＳを使用する、というものであると想定した。それは、大型クラスのイメージ（主として、テキスト、図形または両方の組合せ）に対して最良の画質と優れた圧縮とを提供するためである。ＪＰＥＧ  ＬＳの圧縮性能が不十分であることが分かる場合、すなわち、圧縮率が低すぎた場合（それは、純粋な連続階調イメージか、または実質的な連続階調部分を有する複合イメージである場合）、かかるイメージには非可逆ＪＰＥＧが適用される。基準システムは、導入で説明した実際的な理由のためにイメージのセグメンテーションを使用しなかった。
【００７１】
妥当な比較を行うために、ＪＰＥＧとＪＡＤＥとの両方のパラメータを、適切に選択しなければならない。両方の場合において最適化する必要のある重要なパラメータは、量子化テーブルと品質係数Ｑとである（Ｑ係数は、量子化テーブルパラメータをスケーリングするために使用される、ということに留意）。ＪＰＥＧを、写真イメージ部分とテキスト／図形部分との両方を有する複合ページで使用することができるため、その量子化テーブル最適化を、高周波数成分、すなわち図形およびテキストが顕著に劣化しないように行われなければならない。ＪＡＤＥの場合、非可逆ＪＰＥＧ部分は、写真イメージ部分のみに適用されるため、その量子化テーブルはこれらの部分の最適な描写をもたらすように最適化される必要がある。テキストおよび図形部分は、主として可逆チャネルによって処理する。ハフマンテーブルを、異なるタイプのイメージに対して最適化することも可能である。
【００７２】
下に示す実験では、ＪＰＥＧとＪＡＤＥとの両方に対し、同じ量子化テーブルと同じＱ係数（Independent JPEGコード規約を使用するとＱ＝７５）とを使用した。これは、イメージにおける写真部分の品質がＪＡＤＥとＪＰＥＧとの両方で同じであるということを保証した。上述したように、標準ハフマン解析を使用して、ＪＡＤＥに対し別々のハフマンテーブルを展開した。ＪＡＤＥの場合の可逆チャネルの出力の統計は、ＤＣＴの出力と極めて異なるため、非可逆ＤＣＴの出力に対して最適化されるＪＰＥＧハフマンテーブルを使用することはそれほど意味をなさない。テーブルは、試験イメージのセット全体に対して固定であった。
【００７３】
図５は、ＪＡＤＥ−Ｉ、算術符号化を用いたＪＡＤＥ−Ｉ、ベースラインＪＰＥＧおよびＪＰＥＧ  ＬＳの全性能を比較する。この図からわかるように、ＪＡＤＥ−Ｉの性能は、ＪＰＥＧおよびＪＰＥＧ  ＬＳの組合せの性能に全く匹敵する。主として連続階調イメージの領域（グラフの低い方の圧縮率の部分）の場合、予測されるように、ＪＡＤＥおよびＪＰＥＧの性能は極めて類似する。複合イメージの図形および／またはテキスト部分が増大するにしたがい、ＪＡＤＥは、５程度またはそれより大きく、ＪＰＥＧより著しく性能が向上し始める。また、ＪＡＤＥは、このセットのほとんどのイメージに対して、ＪＰＥＧ  ＬＳより優れた圧縮率を示す。これに対する最も顕著な例外は、イメージ２および３である。上述したように、これらのイメージは、同じピクセルパターンの繰返される続きを、幾分か長い白の続きと同様に示し、それらは、ＪＰＥＧ  ＬＳの適応的性質とその長い続きを非常によく圧縮する能力とに非常によく適合する。
【００７４】
図６に、ハフマン符号化を用いたＪＡＤＥ−ＩとＪＡＤＥ−ＩＩとの両方の性能を提示する。平均して、ＪＡＤＥの両バージョンの性能は類似している。しかしながら、ＪＡＤＥ−ＩＩは、「難しい場合」（イメージ１〜２３）において著しく優れて機能する。ＪＤＡＥ−ＩＩの導入の主な理由は、かかる場合にＪＡＤＥの圧縮性能を向上させる、ということであった。
【００７５】
図７は、考慮中のシステムの重要な特性、すなわち、システムがイメージを１パスで所望の率まで圧縮する、すなわち、圧縮ページのサイズより小さく圧縮することができない可能性がどれくらいあるか、を示す。（これが達成されない場合、異なる圧縮率を使用する第２のパスが必要である。）実際的には、これは、システムバッファが符号化パス中にオーバフローすることを意味する。基準システムが第１の符号化パスでＪＰＥＧ  ＬＳを使用し、本システムは所定パラメータＱ、たとえばＱ＝７５を有するＪＡＤＥを使用することを想起されたい。（基準システムが第２のパスで同じ品質係数を有するＪＰＥＧを使用することに留意されたい。）本実験では、最小圧縮率を１５に設定した。この率は、ＪＰＥＧで圧縮しなければならない本セットにおけるすべてのイメージに対して視覚的に無損失な圧縮を達成するために極めて適当であるように見える。なお、この図におけるイメージインデックス付けは、図５において使用したものとは異なる、ということに留意されたい。ここでは、アルゴリズムの各々に対して、圧縮率が増大する順序でイメージが配置される。この図からわかるように、ＪＡＤＥ−Ｉは、本試験セットに対して４０％ほど、第２の圧縮パスの可能性を大幅に低減する。ＪＡＤＥ−ＩＩは、ＪＰＥＧ  ＬＳに比較して約６０％、さらなる実質的節約を提供する。
【００７６】
図８は、ハフマン符号化を用いたＪＡＤＥの可逆性能を示す。複合文書の大部分に対し、ＪＡＤＥの性能は、平均して、ＪＰＥＧ  ＬＳのそれと類似する。ＪＰＥＧ  ＬＳは、単純な図形イメージ２および３の場合にＪＡＤＥ−Ｉより大幅に性能が優れている。しかしながら、ＪＡＤＥ−ＩＩはこのギャップを大幅に狭め、複数のイメージ（イメージ１７等）に対してＪＰＡＧ  ＬＳより性能が優れている。
【００７７】
図９は、算術符号化を用いたＪＡＤＥの可逆性能を比較する。図示するように、算術符号化により、ハフマン符号化を用いたＪＡＤＥとＪＰＥＧ  ＬＳとの両方と比較して圧縮率が非常に大幅に増大する。
【００７８】
図９は、算術符号化を伴うＪＡＤＥの可逆性能を比較する。図から分かるように、算術符号化により、ハフマン符号化を伴うＪＡＤＥとＪＰＥＧ  ＬＳとの両方に比較して圧縮率が非常に大幅に増大する。
【００７９】
また、あらゆる方法に対して実行時間を評価することにより、ソフトウェア複雑性の比較も行った。種々のアルゴリズムの実行時間を比較することは、常に困難なタスクである。多くの要素が、この比較の結果に影響を与える。すなわち、イメージタイプ（たとえば、図形イメージは、写真イメージより高速に圧縮する傾向がある）、圧縮率（圧縮率が高いほど実行時間が短くなる）、ソフトウェア実施態様がいかに優れているか、プラットフォームタイプ（すなわち、ＰｅｎｔｉｕｍベースＰＣ対何らかの独自のＵＮＩＸプロセッサ）、符号器実行時間対復号器実行時間等、である。仮ではあるが、タイミング結果は、あらゆる方法の比較に対する価値ある実際的データを提供する。
【００８０】
ベースラインＪＰＥＧアルゴリズムの実施態様に、ＩＪＧ（Independent JPEG Group）コードを使用した。ＪＡＤＥ実施態様は、そのコードに基づき、ＬＴブロックを追加し、算術符号化実験のためにハフマン符号化部分を算術符号化に置換えた。ＪＰＥＧ  ＬＳデータのために、ＵＢＣ（University of British Columbia、カナダ）パブリックドメインソフトウェアを使用した。タイミング比較を生成するために、アルゴリズムを、ＪＰＥＧおよびＪＡＤＥに対する異なる品質設定に対し、およびイメージのセット全体に対して、異なるプラットフォーム（ＰｅｎｔｉｕｍベースＷｉｎｄｏｗｓ  ＮＴおよびＨＰ−ＰＡ  ＵＮＩＸシステム）で実行させた。
【００８１】
ＪＡＤＥ−ＩおよびＪＡＤＥ−ＩＩの実行時間は、ＪＰＥＧのものと非常に近く、通常は２０％以内であった。算術符号化を用いるＪＡＤＥは、ほとんどのイメージに対してハフマン符号化を用いるＪＡＤＥと略同程度に高速であり、複合文書の場合に２０％以下の実行時間が増大した。算術符号化が常にハフマン符号化よりずっと低速であるという一般的な認識に鑑みて、これは興味ある結果である。このデータから分かるように、算術エントロピー符号化を使用する通常の複合文書の場合、ＪＡＤＥに対する圧縮率は、１００％以上（図５参照）増大し、実行時間は比較的わずかに増大する。写真イメージの場合は、状況が異なる。写真イメージの場合、算術符号化を用いるＪＡＤＥは、ハフマン符号化を用いるＪＡＤＥより略２倍低速であった。
【００８２】
ハフマン符号化を用いるＪＡＤＥをＪＰＥＧ−ＬＳと比較することにより、イメージタイプ、使用されるプロセッサ等により、結果が大幅に変化することが観察された。ほとんどの場合、ＪＡＤＥはＪＰＥＧ  ＬＳより高速に、時に符号器において２倍高速におよび復号器において４倍高速に実行した。しかしながら、ＪＰＥＧ  ＬＳ実行時間がＪＡＤＥの実行時間の約１．７倍高速である場合が数回あった。
【００８３】
複合イメージの圧縮のための新たな方法が開発された。ＪＡＤＥと呼ばれるこの方法は、好ましい実施形態では、ＪＰＥＧイメージ圧縮システムに基づく。この好ましい実施形態では、それは、非可逆圧縮に対しては標準ＪＰＥＧ手法を使用し、可逆圧縮に対してはＪＰＥＧのエントロピー符号化部分を利用する。ＪＡＤＥの圧縮性能は、ＪＰＥＧおよびＪＰＥＧ  ＬＳ等、２つの異なる圧縮エンジンを利用することによって、すなわち２つの異なるエントロピー符号器を使用することによって最新システムによって達成されるものと類似する。ハードウェア実施態様では、本発明の方法により、２つの別々のコンプレッサを有する必要がなくなり、それによりハードウェアコストが約５０％低減する。また、ＪＡＤＥは、高速ソフトウェア実施態様にも向いている。
【００８４】
したがって、本発明は、複合文書の圧縮に対し複雑性の低い代替態様を提供する。新たに開発されたアルゴリズムは、ＪＡＤＥ（ＪＰＥＧベース適応的文書圧縮エンジン（JPEG based Adaptive Document compression Engine））と呼ばれる。それは、ＪＰＥＧアーキテクチャに基づく。それは、可逆圧縮を行うためにＪＰＥＧパイプラインにおいてハフマン符号器を利用する。そうすることにより、ＪＰＥＧシステムにおいてハフマン符号器を「ＪＰＥＧ  ＬＳのような」エントロピー符号器によって置換えることによる等、いくつかの他のソリューションの複雑性の増大が回避される。S Liuによる「JPEG2000: A scalable hybrid lossy/lossless still image compression scheme」、Submission to ISO/IEC JTC1/SC29/WG1、1997と、C. Chrysafis、A. Drukarev、S. LiuおよびN. Memonによる「Some results on DCT-based JPEG experiments」、Document ISO/IEC JTC1/SC29/WG1N748、1998と、を参照のこと。ＪＡＤＥの複雑性は、基本的に、非常にわずかな追加を含んで、ＪＰＥＧの複雑性と同じである。同時に、ある範囲の通常のイメージに対するＪＡＤＥの圧縮性能は、非可逆ＪＰＥＧとＪＰＥＧ  ＬＳ等の最新の可逆圧縮方法とを結合するシステムの性能に匹敵する。本発明のソリューションは、特に、ハードウェア実施態様、特にいかなる場合もＪＰＥＧアルゴリズムを使用しなければならないもの（たとえば、標準準拠である必要があるため、またはイメージ交換を簡略化するため等）に適している。
【００８５】
本発明の好ましい実施形態の上述した説明は、例示および説明の目的のために提示した。それは、網羅的であるようにも本発明を開示した厳密な形態に限定するようにも意図されておらず、変更および変形は、上記教示に鑑みて可能であり、または本発明の実施から獲得することができる。当業者が、企図される特定の使用に適するようにあらゆる実施形態でおよびあらゆる変更態様で本発明を利用することができるように本発明の原理とその実際的な適用とを説明するために、実施形態を選択し説明した。本発明の範囲は、添付の特許請求の範囲とそれらの均等物とによって画定される、ということが意図されている。
【図面の簡単な説明】
【００８６】
【図１Ａ】本発明の第１実施形態を示す略ブロック図である。
【図１Ｂ】本発明の第１実施形態を示す略ブロック図である。
【図２】本発明において分類を実施するために使用してもよい決定木の一実施形態のロジックを示す略ブロック図である。
【図３】可逆変換のための走査パスを示すグラフである。
【図４】本発明の第２のより複雑な実施形態を示す略ブロック図である。
【図５】ＪＡＤＥ−Ｉおよび算術符号化を使用するＪＡＤＥ−ＩＩと、ＪＰＥＧと、ＪＰＥＧ−ＬＳと、に対するイメージ対圧縮率のグラフである。
【図６】ＪＡＤＥ−ＩおよびＪＡＤＥ−ＩＩに対するイメージインデックス対圧縮率のグラフである。
【図７】最小圧縮率１５：１の場合の圧縮率対イメージインデックスのグラフである。
【図８】ハフマン符号化を用いるＪＡＤＥ−ＩおよびＪＡＤＥ−ＩＩの可逆性能に対する圧縮率対イメージインデックスのグラフである。
【図９】算術符号化を用いるＪＡＤＥ−ＩおよびＪＡＤＥ−ＩＩの可逆性能に対する圧縮率対イメージインデックスのグラフである。
【図１Ａ】
2004530341.tif 000005
【図１Ｂ】
2004530341.tif 000006
【図２】
2004530341.tif 000007
【図３】
2004530341.tif 000008
【図４】
2004530341.tif 000009
【図５】
2004530341.tif 000010
【図６】
2004530341.tif 000011
【図７】
2004530341.tif 000012
【図８】
2004530341.tif 000013
【図９】
2004530341.tif 000014
【国際公開パンフレット】
2004530341.tif 000015
2004530341.tif 000016
2004530341.tif 000017
2004530341.tif 000018
2004530341.tif 000019
2004530341.tif 000020
2004530341.tif 000021
2004530341.tif 000022
2004530341.tif 000023
2004530341.tif 000024
2004530341.tif 000025
2004530341.tif 000026
2004530341.tif 000027
2004530341.tif 000028
2004530341.tif 000029
2004530341.tif 000030
2004530341.tif 000031
2004530341.tif 000032
2004530341.tif 000033
2004530341.tif 000034
2004530341.tif 000035
2004530341.tif 000036
2004530341.tif 000037
2004530341.tif 000038
2004530341.tif 000039
2004530341.tif 000040
2004530341.tif 000041
2004530341.tif 000042
2004530341.tif 000043
2004530341.tif 000044
2004530341.tif 000045
2004530341.tif 000046
2004530341.tif 000047
2004530341.tif 000048
2004530341.tif 000049
2004530341.tif 000050
2004530341.tif 000051
2004530341.tif 000052
2004530341.tif 000053
2004530341.tif 000054
2004530341.tif 000055
【国際調査報告】
2004530341.tif 000056
2004530341.tif 000057
2004530341.tif 000058