(57)【特許請求の範囲】
【請求項１】
受け取ったドキュメントを圧縮する方法であって、
複数データ・タイプの未知の組み合わせを含むドキュメントを受け取るステップと、
前記ドキュメントに必要な圧縮量を決定するステップと、
前記ドキュメントの部分に対する局所圧縮制約条件を満たすように選択された圧縮方法で前記ドキュメントの各部分を圧縮するステップと、
前記圧縮された前記ドキュメントの各部分の実際の圧縮データ量と前記局所圧縮制約条件を比較するステップと、
前記局所圧縮制約条件を満たすように、漸次強力になる圧縮技法で前記ドキュメントの各部分を繰り返し圧縮するステップと、
前記局所圧縮制約条件を満たすように繰り返し圧縮された前記ドキュメントの各部分の圧縮データを各々含む複数のパケットであって、各パケットは、当該圧縮データのサイズを示すデータ及びパケットを識別する識別データを含み、各々複数のパケットで構成される複数のストリップ各々を、ストリップに対応する圧縮制約条件を満たすように繰り返し圧縮された複数のストリップの総データ量と前記ドキュメントの全体に対する大域圧縮制約を比較するステップと、
前記大域圧縮制約条件を満たすように、漸次強力になる圧縮技法で前記複数のストリップ各々を繰り返し圧縮するステップと、
を含むことを特徴とする方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ラスタ・イメージのデジタル・イメージ圧縮法に関する。
【０００２】
【従来の技術】
デジタルシステムにおいて、イメージ・フォーマット・ドキュメントは、格納コストを節約し、伝送チャネルによる伝送時間を短縮するため、圧縮される場合が多い。これらのドキュメントには、文字及び図形のような、コンピュータによるレンダリングが施されるドキュメント領域に対して極めて優れた圧縮を実現することが可能な無損失の圧縮を施すことが可能である。しかし、被走査イメージ・データを含むドキュメント領域の圧縮はうまくゆかない。こうしたドキュメントには、連続したトーンの被走査ドキュメント領域にうまく作用する、ＪＰＥＧのような損失のある圧縮テクノロジーを適用することが可能である。コンピュータでレンダリングされる対象によって生じるコントラストの強いエッジに、この圧縮テクノロジー、及び、一般には、変換コーディング・テクノロジーによって、画質の問題が生じることになる。この問題の解決法は、ドキュメントにさまざまな圧縮テクノロジーを適用して、画質及び圧縮性を最適化することである。これによって、保証圧縮率を実現するように、複数の圧縮テクノロジーを管理し、制御するというより大きい難題が生じることになる。
【０００３】
米国特許第５，４７９，５８７号には、ラスタ・データが、プリント・バッファに十分に納まるほど圧縮されるまで、圧縮比が増すようにさまざまな圧縮手順を試みることによって圧縮される、プリント・バッファ最小限化法が開示されている。
【０００４】
【発明が解決しようとする課題】
本発明は、改善された、ラスタ・イメージのデジタル・イメージ圧縮法を提供することを主要な１つの課題とする。
【０００５】
【課題を解決するための手段】
ラスタ・イメージのデジタル・イメージ圧縮法では、イメージの選択部分にさまざまな圧縮法を利用して、圧縮及びセグメンテーション・パラメータに動的調整を施し、画質と圧縮のトレードオフを制御する。イメージは、ディスク、メモリ、及び、Ｉ／Ｏシステムによって効率よく取り扱えるように、単一データ・ストリームに符号化される。
【０００６】
本発明の１つの態様によれば、複数データ・タイプの未知の組み合わせを含むドキュメントを受け取るステップと、ドキュメントに必要な圧縮量を決定するステップと、ある局所圧縮制約条件または１組の局所制約条件を満たすように選択された圧縮方法で前記ドキュメントのいくつかの部分を圧縮するステップと、実際の圧縮と前記局所圧縮制約条件を比較するステップと、前記局所圧縮制約条件を満たすように、漸次強力になる圧縮技法でドキュメントのいくつかの部分を繰り返し圧縮するステップが含まれている、受け取ったドキュメントを圧縮する方法が得られる。この方法によれば、ドキュメントの実際の圧縮とある大域圧縮制約条件または１組の大域圧縮制約条件セットを比較し、前記大域圧縮条件を満たすように、漸次強力になる圧縮技法で前記ドキュメントを繰り返し圧縮することも可能になる。
【０００７】
本発明のもう１つの態様によれば、複数のデータ・タイプの未知の組み合わせを含むドキュメントを受け取るドキュメント入力と、損失のある圧縮及び損失のない圧縮を施す複数のドキュメント圧縮システムと、圧縮されたドキュメント情報と圧縮制約条件を比較して、ドキュメントに加えられた圧縮量が圧縮制約要件を満たすか否かを判定する圧縮比較装置と、前記複数のドキュメント圧縮装置の選択を制御して、圧縮制限要件を満たすように、ドキュメントに施される圧縮率を高めるフィードバック装置と、前記フィードバック装置に応答して、ドキュメントの処理を繰り返し行う反復圧縮プロセッサが含まれている圧縮システムが得られる。
【０００８】
本システムは、複数の圧縮制約条件に従うように、細密なグラニュラリティ（一般に８×８ピクセルのブロック）で行われるイメージ・データの圧縮、人為的可視成分に関して最も耐性のあるブロックに、より強力な圧縮技法を選択的に施す、圧縮が強まるインクリメンタル・バイアスの管理、及び、イメージ圧縮の制御に用いられる可調整セグメンテーション及び圧縮パラメータを管理する安定フィードバック・ループをなす。このシステムの構成要素には、セグメンタに対する適切なフィードバック信号を確定するための、圧縮率情報の処理と、これらのフィードバック信号に応答して、より圧縮が強まるように漸次バイアスを増すことが可能なセグメンタが含まれている。
【０００９】
【発明の実施の形態】
「イメージ」は、全ページ・イメージ、または、全ページ・イメージのある部分である。イメージは、大域圧縮制約条件が繰り返し適用されるデータ・セットである。
【００１０】
「ストリップ」は、局所圧縮制約条件が繰り返し適用される入力イメージの小間隔である。望ましい実施態様の場合、ストリップは８走査線である。
【００１１】
「チャネル」は、単一ストリップ内における同じ一般的なタイプのデータ・セットである。例えば、損失のあるイメージ・チャネルには、複数の損失のある圧縮方法で圧縮されることになるストリップに関する全てのイメージ・データが含まれている。
【００１２】
図１には、本発明を利用することが可能な方法が示されている。１０１において、ラスタ・ドキュメント作成アプリケーション１００によって、走査線順序付きラスタ・フォーマット・ドキュメントが生成される。ラスタ・ドキュメント作成アプリケーションは、ページ記述言語ドキュメントを、コンピュータまたはマイクロプロセッサ・ベースのドキュメント作成システムで実行されるラスタ・フォーマットに変換するラスタ・エディタまたはシステムとすることが可能である。走査線ラスタ・データは、圧縮手段１０２に送られて、圧縮される。フィードバック装置１０３によって、圧縮制約条件または要件が満たされるまで、より強力な圧縮処理を施す反復方法が得られる。出力１２０における圧縮手段１０２の出力は、圧縮データ・ファイルであり、圧縮フォーマット記憶装置１０４に納められる。圧縮データ・ファイルには、圧縮解除を可能にするため、圧縮方法に関する情報が含まれている。ドキュメントの走査線ラスタ・フォーマットを再生するため、圧縮解除手段１０５は、１２２でドキュメントを受信し、圧縮手段１０２によって生成された圧縮データに処理を施す。位置１０６における走査線ラスタ・データは、必要に応じて、さらに処理を加えることが可能である。典型的なシステムの場合、圧縮処理１０２は、ソフトウェアまたはハードウェアによって実施することが可能であるが、一般には、ソフトウェア処理を除外するわけではないが、コンピュータ・システムに組み込まれたハードウェア・ボードによって、圧縮解除処理１０５が施される。
【００１３】
図２には、圧縮データ構造のダイヤグラムが示されている。もとのラスタ・イメージ（図１の入力１０１で受信された）は、２００に示すように複数の個別に圧縮されたストリップの連結として圧縮される。このデータ全体としての平均圧縮比は、圧縮制約条件ｒaを満たさなければならない。２０１において、各圧縮ストリップには、１つ以上の圧縮パケットが含まれている。イメージ・データ・タイプに従って、損失のある、または、損失のない各イメージ・データ圧縮チャネル毎に、圧縮パケットが存在する可能性がある。どの場合にも、無損失の圧縮マップ・データ・パケットが存在することになる（図３の３０４参照）。本明細書において用いられる限りにおいて、マップ・データは、圧縮に関する情報を表しており、圧縮解除処理に用いられるイメージ・データを含むことが可能である。
【００１４】
ストリップのパケット・サイズの和は、圧縮制約条件ｒmを満たさなければならない。２０２において、各パケットには、パケット・タイプ識別子及びサイズ・フィールドと、それに後続する圧縮データが含まれている。圧縮データは、圧縮制約条件ｒbを満たさなければならない。認識しておくべきは、連結リストのような、出力パケット・ストリームのフォーマットの変形が許容されるということである。
【００１５】
システム設計全体に関連した圧縮制約条件にはいろんな理由がある。一般に、それらは、圧縮サブシステムのデータ帯域幅及びバッファ・サイズに関するものである。可能性のある実施態様の１つにおいて、ｒａは、圧縮解除データが必要とされる平均割合を、圧縮データを納めたディスク・ドライブの帯域幅で割った比率である。比率ｒｍは、最大圧縮ストリップ・サイズに制約を加えるものであり、圧縮解除ハードウェアのコンピュータ・システム・バスの帯域幅が決定要因となる。比率ｒｂは、ハードウェア・ボードの各圧縮解除チャネルにおいて利用可能なＦＩＦＯバッファ空間のサイズを表している。
【００１６】
図３において、圧縮システムに対する入力は、出力１０１で受け取る走査線順序付きラスタ・フォーマット・イメージである。入力データは、１回に１ストリップずつ処理される。各ストリップは、その局所ストリップ制約条件（ｒｂ及びｒｍ）が満たされるまで、反復処理を受ける。実施態様の１つでは、このプロセスは、順次実施され、完了するまで続行してから、次のストリップの処理が実施される。しかし、他の処理順序も可能である。イメージ全体が完了すると、圧縮データ集合体を検査して、大域制約条件ｒａが遵守されているか否かが確認される。この検査に不合格になると、入力イメージに対して全プロセスが反復される。
【００１７】
セグメンタ３００は、イメージを内容に従って、損失のある領域と損失のない領域に分割する。本発明は、その教示について、参考までに本明細書において援用されている、２０００年５月１日に提出された、ＺｅｃＫ他による米国特許出願第０９／５６２，１４３号に記載された、イメージ・セグメンテーションを実施する解析及び分類システムを改良したものである。
【００１８】
このセグメンテーションの改良によって、同じ入力データに反復して、漸次圧縮を強めることが可能なパラメータ化セグメンテーションが可能になる。強度を制御するパラメータは、本明細書では「スロットル」と呼ばれる。無損失スロットル３１０の値を増すと、イメージ・ブロックが無損失チャネル３０５に割り当てられる確率が低下する（すなわち、損失のあるチャネルに割り当てられる確率が高くなる）。損失のないスロットルは、表１に示す代替しきい値セットのグループ間からしきい値セットを選択することによって、２０００年５月１日に提出された、ＺｅｃＫ他による米国特許出願第０９／５６２，１４３号の「ビジー・ゾーン」を修正する。このしきい値選択方式によって、各順次無損失スロットル値毎に、可視人為的圧縮成分を生じる可能性が最も少ないイメージ・ブロックが損失のあるチャネルに分類されるブロックになるようにする、改良式セグメンタの選択性が得られる。損失のあるスロットル３１１の値を増すと、損失のあるチャネル内の所定のブロックが、３０６において損失のあるより強力な圧縮方法に割り当てられる確率が高くなる。損失のあるスロットルの値が増す毎に、２０００年５月１日に提出された、ＺｅｃＫ他による米国特許出願第０９／５６２，１４３号の分類ルックアップ・テーブルが、可視人為的成分に関する耐性が最も高いイメージ・ブロックに関するより高いＱテーブルを備えた、ＪＰＥＧ圧縮を指定する１組の新しいルックアップ・テーブルに置き換えられる。３０６に経路指定されるイメージ・データ３０２のブロックには、３０６内の複数の損失のある圧縮のうちからどれを用いるべきかを指定する属性３０３が含まれている。間引きスロットル３１２は、損失のないスロットル及び損失のあるスロットルによって、所望の圧縮率が実現されない場合の、最後の手段として用いられる。このスロットルによって、入力データは、その複雑性を低減するように修正される。スロットル値によって、２×２、４×４、または、８×８にピクセル・ブロックが、それらの平均値に置き換えられる。認識しておくべきは、他のイメージ・フィルタリング法を利用することも可能であるという点である。実際のところ、間引きが実施されることが滅多にないため、その単純性が望ましいということになる。
【００１９】
セグメンタ３００は、圧縮解除システムによるイメージの再アセンブルに必要なセグメンテーション・マップ３０１も生成する。マップ・データは、無損失圧縮手段３０４において無損失圧縮が施される。パッケージャ３０７は、現在のイメージ・ストリップに関する出力パケット・ストリーム３１３を生成する。この時点において、出力パケット・ストリームが、出力２０１のために規定された圧縮制約条件を満たすかについては検証されていない。
【００２０】
圧縮率測定器３０８によって、制約条件が満たされていることが確認されると、圧縮ストリップ・データが出力２０１から放出され、イメージ入力データの次のストリップの処理が続行される。制約条件が満たされない場合、スロットル・パラメータが調整され（３０９）、現在のストリップが再試行される。スロットル調整方式は、本発明の特徴である。この方式の重要部分は、スロットルによって得られるフィードバック・ループが本質的に安定しているということである。無損失スロットルには、無損失チャネルから損失チャネルへとデータを転送する効果がある。損失スロットルによって、個々のブロックにおいて、損失のあるチャネルの圧縮が強まる傾向が増すが、スロットル調整処理については、残りの図のフローチャートに関連して詳述するものとする。
【００２１】
図４には、局所ストリップ制約条件（ｒｂ及びｒｍ）を強化するため、各ストリップのスロットルに施される処理の概要であるフローチャートが示されている。このフローチャートにおける３つの処理モジュールのそれぞれに関する詳細が、次の３つの図に示されている。
【００２２】
図５には、パケット・サイズ制約条件ｒｂを強化するため、各ストリップのスロットルに施される処理のフローチャートが示されている。
【００２３】
図６には、圧縮ストリップ・サイズ制約条件を強化するため、各ストリップのスロットルに施される処理のフローチャートが示されている。このフローチャートに記載されている処理が、ｒｍ制約条件を強化するため、図４において呼び出され、また、ｒａ制約条件を強化するため、図８の処理によっても呼び出される。図６の圧縮制約条件ｒは、ｒｍとｒａのどちらが適用されるかに従って、異なる値をとる。ｒｍの場合、ｒに用いられる実際の値は、目標圧縮率ｒｍよりも２０％制限が厳しくなる。同様に、ｒａの場合、ｒに用いられる値は、大域目標圧縮率ｒａよりも２０％制限が厳しくなる。本明細書において用いられる限りにおいて、「制限が厳しくなる」は、より強力な圧縮を必要とする傾向を表している。後続の再圧縮候補パケット数を増すため、２０％のマージンが利用される。それらの目標をかろうじて満たしたパケットは、他の不十分な圧縮ストリップに反復処理を加えて、極めて強力なスロットル・レベルに達するようにしなければならない確率を低下させるため、より強力なスロットルで再圧縮される。その目標圧縮率を２０％以上超えるパケットだけが、そのままにして、現在の反復処理を受けることになる。認識しておくべきは、２０％のマージンは、経験に基づいて決定されたものであり、変更を受けるということである。
【００２４】
図７には、図４に示すように制約条件ｒｍを強化するため、各ストリップのスロットルに施されるオーバライド処理のフローチャートが示されている。この処理は、損失のないパケット及び損失のあるパケットが、それらのスロットルがインクリメントされない程度には十分うまく圧縮されるが、ストリップが、圧縮マップ・データのオーバヘッドのためにｒｍ制約条件を満たさないという場合に必要になる。
【００２５】
図８には、大域制約条件ｒａを強化するために、各ストリップのスロットルに施される処理のフローチャートが示されている。局所圧縮制約条件を強化して、イメージ全体の初期圧縮が完了すると、圧縮データの集合体を検査して、大域制約条件ｒａの遵守が確認される。この検査に不合格になると、大域制約条件が満たされるまで、このフローチャートに従って、イメージ処理が繰り返される。イメージの再処理を実施することになる場合、各ストリップに関するスロットルの再初期化は行われないという点に留意されたい。全てのスロットルは、終了したところから再開し、大域目標が実現するまで、さらにインクリメントされる。
【００２６】
開示の方法は、さまざまなコンピュータまたはワークステーション・ハードウェア・プラットフォームに用いることが可能な移植性のソース・コードをもたらす、オブジェクト指向ソフトウェア開発環境を利用したソフトウェアにおいて、容易に実施することが可能である。あるいはまた、開示のイメージ処理システムは、標準的な論理回路を用いて、または、とりわけ、ＶＬＳＩ設計を用いた単一チップにおいて、部分的または完全にハードウェアで実施することも可能である。ソフトウェアまたはハードウェア、あるいは、その組み合わせのいずれを用いて実施されようと、このイメージ処理システムは、システムの速度及び効率要件、さらには、用いられている特定の機能、及び、特定のソフトウェアまたはハードウェア・システム、及び、特定のマイクロプロセッサまたはマイクロコンピュータ・システムに応じてさまざまである。しかし、このイメージ処理システムは、適用可能な技術の熟練者であれば、コンピュータ技術の一般知識と共に、本明細書に記載の機能説明から、あまり実験をしなくても、容易に開発することが可能である。
【表１】
0004722321.tif 000002
【図面の簡単な説明】
【図１】本発明が用いられる可能性のあるシステムの図である。
【図２】圧縮データ構造及びその複数の圧縮制約条件に対する関係を示す図である。
【図３】本発明の圧縮法を例示した図である。
【図４】スロットルに施される処理のフローチャートである。
【図５】スロットルに施される処理の細部のフローチャートである。
【図６】スロットルに施される処理の別の細部のフローチャートである。
【図７】スロットルに施される処理の更に別の細部のフローチャートである。
【図８】スロットルに施される別処理のフローチャートである。
【符号の説明】
１００  ラスタ・ドキュメント作成アプリケーション
１０２  圧縮手段
１０３  フィードバック装置
１０４  圧縮フォーマット記憶装置
１０５  圧縮解除手段
３００  セグメンタ
３０４  無損失圧縮手段
３０５  無損失チャネル
３０７  パッケージャ
３０８  圧縮率測定器
【図１】
0004722321.tif 000003
【図２】
0004722321.tif 000004
【図３】
0004722321.tif 000005
【図４】
0004722321.tif 000006
【図５】
0004722321.tif 000007
【図６】
0004722321.tif 000008
【図７】
0004722321.tif 000009
【図８】
0004722321.tif 000010