(57)【要約】【課題】データ充填の方法及び装置を本明細書及び特許請求の範囲に記載する。【解決手段】一実施例では、方法は、画像、及び画像に関連したマスクを受け取る工程と、ブロックベースの反復マルチパス・データ充填処理を実行して、複合文書圧縮の一部として層を充填する工程とを備える。【選択図】図９
2008054325.tif 000002
【特許請求の範囲】
【請求項１】
画像、及び前記画像に関連したマスクを受け取る工程と、
ブロックベースの反復マルチパス・データ充填処理を実行して、複合文書の圧縮の一部として層を充填する工程と
を備える方法。
【請求項２】
請求項１記載の方法であって、ブロックベースの反復マルチパス・データ充填処理を実行する工程が、前記層の1つ又は複数のブロックそれぞれについての値を、前記ブロックそれぞれを含むウィンドウの画素値に基づいて判定する工程を備え、前記ウィンドウがブロック・サイズよりも大きい方法。
【請求項３】
請求項１記載の方法であって、フォアグラウンド層及びバックグラウンド層の少なくとも１つのブロックを分類する工程を更に備える方法。
【請求項４】
請求項３記載の方法であって、ブロックを分類する工程は、
各画素を中心としたウィンドウを検査し、
前記各画素とは異なる値を有する画素が前記ウィンドウにあるかを判定し、
前記各画素とは異なる値を有する画素が前記ウィンドウ内の前記各画素近くにある場合に前記各画素をエッジとして分類することによって画素を分類する工程を備える方法。
【請求項５】
請求項３記載の方法であって、ブロックを分類する工程がマスク値によって画素を分類する工程を備える方法。
【請求項６】
請求項３記載の方法であって、ブロックを分類する工程は、ケア画素のみを有する各ブロック、ドントケア画素のみを含む各ブロック、及び少なくとも１つのドントケア画素に少なくとも１つのケア画素が隣接していることによってもたらされるエッジを含む各ブロックを識別する工程を備える方法。
【請求項７】
請求項６記載の方法であって、ブロックベースの反復マルチパス・データ充填処理を実行する工程は、第１のパス中にブロック毎に、
ケア画素のみを含んでいるとして分類された、前記層内の各ブロックを、前記画像内の対応するブロックの画素値で充填する工程と、
エッジを含んでいるとして分類された各ブロック内のドントケア画素を、前記各ブロックを含むウィンドウ内のケア画素の平均に基づいた値で充填する工程であって、前記ウィンドウがブロック・サイズよりも大きい工程と、
エッジを含んでいるとして分類された各ブロック内のケア画素を、前記画像内の対応するブロックにおける対応する画素の画素値で充填する工程と
を備える方法。
【請求項８】
請求項７記載の方法であって、ブロックベースの反復マルチパス・データ充填処理を実行する工程は、
近傍ブロック組が何れも先行パスにおいて充填されていない場合、非充填として各非充填ブロックを維持する工程と、
前記各非充填ブロックの各画素に、１つ又は複数の先行パスにおいて充填された近傍ブロックの平均の平均を有する値を割り当てる工程と
を含む、前記各非充填ブロックについて後続パスを実行する工程を更に備える方法。
【請求項９】
請求項８記載の方法であって、
パスの設定された数、前記後続パスの実行を繰り返す工程と、
前記設定された数のパスを実行した後、前記層内の一ブロックにおける判定されていない画素それぞれに、前記一ブロックに最も近い別のブロックにおける画素値と、前記一ブロックにおける画素値の中点とのブロック平均を割り当てる工程と
を更に備える方法。
【請求項１０】
請求項３記載の方法であって、ブロックを分類する工程は、エッジ画素を備えたケア画素のみを有する各ブロック、エッジ画素なしのケア画素のみを有する各ブロック、エッジ画素を備えたドントケア画素のみを含む各ブロック、エッジ画素なしのドントケア画素のみを含む各ブロック、及び、少なくとも１つのドントケア画素に少なくとも１つのケア画素が隣接していることによってもたらされるエッジを含む各ブロックを識別する工程を備える方法。
【請求項１１】
請求項１０記載の方法であって、ブロックベースの反復マルチパス・データ充填処理を実行する工程は、第１のパス中にブロック毎に、
エッジ画素を備えたケア画素のみを含むとして分類されたか、エッジ画素なしのケア画素のみを含むとして分類されたか、エッジ画素を備えたドントケア画素のみを含むとして分類されたか、又は、少なくとも１つのドントケア画素に少なくとも１つのケア画素が隣接していることによってもたらされるエッジを含むとして分類された各ブロックにおける各エッジ画素又はドントケア画素に、前記各ブロックを含むウィンドウにおけるケア非エッジ画素の平均に基づいた値を割り当てる工程と、
エッジ画素なしのドントケア画素のみを含む各ブロックにおける各ケア画素を、前記画像における対応するブロックの対応する画素値に割り当てる工程と
を備える方法。
【請求項１２】
請求項１１記載の方法であって、ブロックベースの反復マルチパス・データ充填処理を実行する工程は、
近傍ブロック組が何れも、すぐ前のパスにおいて充填されていない場合、非充填として各非充填ブロックを維持する工程と、
前記各非充填ブロックの各画素に、前記すぐ前のパスにおいて充填された近傍ブロックの平均の平均を有する値を割り当てる工程と
を含む、前記各非充填ブロックについて後続パスを実行する工程を更に備える方法。
【請求項１３】
請求項１２記載の方法であって、前記層のブロック全てが充填されるまで非充填ブロックそれぞれについて前記後続パスの実行を繰り返す工程を更に備える方法。
【請求項１４】
請求項１２記載の方法であって、
パスの設定された数、前記後続パスの実行を繰り返す工程と、
前記設定された数のパスを実行した後、前記層内の一ブロックにおける判定されていない画素それぞれを、前記一ブロックに最も近い別のブロックにおける画素値の平均、及びグレイレベル中点値を有する群における値に割り当てる工程と
を更に備える方法。
【請求項１５】
請求項１記載の方法であって、前記ブロックベースの反復マルチパス・データ充填処理を実行する工程が、前記マルチパス・データ充填処理の各パスにおける各ブロックの充填ステータスを把握するためにデータ充填スタータス・テーブルを維持する工程を備える方法。
【請求項１６】
請求項１記載の方法であって、前記マスクが、グレイレベル・マスクから生成されるバイナリ・マスクである方法。
【請求項１７】
請求項１記載の方法であって、前記ブロックベースの反復マルチパス・データ充填処理を実行する工程は、実行されているパス、及びブロックに対応する画像のコンテンツを有する群のうちの１つ又は複数に基づいてブロック・サイズを適合させる工程を備える方法。
【請求項１８】
請求項１記載の方法であって、前記ブロックベースの反復マルチパス・データ充填処理を実行する工程は、
画素及びその関連したマスクのブロックの第１の行をバッファに読み出す工程と、
ブロックの第２の行のエッジ・ブロック、内部ブロック及びドントケア・ブロックを判定する工程と、
最後の行を含まないが最後の行までの後続行毎に一パスを判定する工程であって、先行パスにおいて判定されたブロックの隣にブロックの画素があるか否かが判定される工程と、
前記最後の行に対して最終パスを実行する工程と
を備える方法。
【請求項１９】
請求項１記載の方法であって、前記ブロックベースの反復マルチパス・データ充填処理と合成したスケーリングを実行する工程であって、それによって、充填された画像のスケーリングされたサイズのバージョン用の、前記画像のサイズよりも小さなサイズを有するバッファを用いる工程を更に備える方法。
【請求項２０】
マスクを生成するためのマスク生成器と、
画像、及び前記画像に関連したマスクを受け取り、ブロックベースの反復マルチパス・データ充填処理を実行して、複合文書圧縮の一部として層を充填するためのマルチパス・データ充填装置と
を備える装置。
【請求項２１】
画像、及び前記画像に関連したマスクを受け取る手順と、
ブロックベースの反復マルチパス・データ充填処理を実行して、複合文書圧縮の一部として層を充填する手順と
をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に複合文書の圧縮の分野に関し、特に複合文書の圧縮に用いるデータ充填手法に関する。
【背景技術】
【０００２】
混合ラスタ・コンテンツ（MRC）は、複合文書の圧縮のITU標準（T.44）である。この標準では、文書画像が複数の層に分離され、各層が、その層に適した特定の符号器によって圧縮される。通常の３層MRC文書は、バイナリ・マスク、フォアグラウンド層及びバックグラウンド層を含む。ここでは、マスクの各画素値を用いて、ラスタ画像の再構成においてフォアグラウンド画素とバックグラウンド画素との間で選択する。一般に、3層MRC符号器は、マスク生成と、データ充填（フォアグラウンド及びバックグラウンドの生成）と、フォアグラウンド及びバックグラウンドのスケーリングと、それに続く、各層の別個の圧縮を含む。
【０００３】
マスク生成は不可欠であるが、データ充填も、高い圧縮性能を達成するうえで非常に重要である。一般に、MRCベースの符号器のデータ充填手法では、フォアグラウンド層及びバックグラウンド層において「ドントケア」画素（すなわち、再構成に関係のない画素）全ての充填が必要である。可逆圧縮の場合、「ドントケア」画素はビット・レートにのみ影響を及ぼす。しかし、非可逆圧縮を用いて、より低いビット・レートを得る場合、「ドントケア」画素の下手な選択によって、復号化中に「ケア」画素（すなわち、再構成に関係がある画素）が変わり得る。「ドントケア」画素は画像の再構成に直接関係がないが、前述の画素の値の選択は、圧縮のレート-歪み特性に対してかなりの影響を及ぼし得る。例えば、フォアグラウンド層及びバックグラウンド層におけるドントケア画素に、単一の色値が充填されると仮定する。この場合、不快なリンギング・アーチファクトが、JPEGやJPEG2000などの何れかの非可逆圧縮によってフォアグラウンドとバックグラウンドとの境界において復元画像が生じ得る。したがって、MRC圧縮の利点はかなり失われる。
【０００４】
前述の課題を解決するために提案されている手法がいくつか存在している。前述の手法は、３つのカテゴリ（すなわち、空間領域データ充填、反復周波数領域データ充填、及びマスク依存変換）に分類することが可能である。
【０００５】
空間領域データ充填手法は一般に単純かつ高速である。反復周波数領域データ充填手法は、より高い圧縮性能をもたらすが、計算量的に更に費用がかかる。マスク依存変換手法は、非常に高い圧縮性能をもたらすが、フォアグラウンド層及びバックグラウンド層の圧縮にマスクとフォアグラウンド／バックグラウンドとの間の相互作用を必要とし、MRCとの完全な準拠性を有しない。
【０００６】
特に、一部を以下に説明するいくつかの空間領域データ充填アルゴリズムが存在している。一空間領域データ充填手法では、ケア画素及びドントケア画素の混合を含むブロックそれぞれにおいて複数のパスが実行される。各パスでは、非充填画素それぞれは、近傍ケア画素の平均によって判定される。この手順は、「ホール」全てが充填されるまで繰り替えされる。更なる情報については、De  Queriozによる「On  Data-Filling  Algorithms  for  MRC  Layers,  Proc.  IEEE  Intl.  Conf.  on  Image  Processing,  ICIP,  Vancouver,  Canada,  Vol.  II,  pp.  586-589,  Sep.  2000」を参照されたい。
【０００７】
別の空間領域データ充填手法は、ドントケア画素の内挿のために単一パスのブロックベースのデータ充填アルゴリズムを含む、符号器によってマッチングされる層分離手法を実行する。特に、ケア画素及びドントケア画素の混合を含むブロック毎に、ドントケア画素の値が、そのブロックのケア画素の平均に基づいて割り当てられる。各ドントケア・ブロックには、所定の値、又は先行充填ブロックの平均値が充填される。更なる情報については、「Coder  Matched  Layer  Separation  and  Interpolation  for  Compression  of  Compound  Documents」と題する西暦2005年９月発行の米国特許第６９４１０２４号明細書を参照されたい。
【０００８】
別の空間領域データ充填手法は、ルラテック（Luratech）社によって開発されたルラドキュメント（LuraDocument）において実現される。この手法では、フォアグラウンド及びバックグラウンドが、3分の１に減少させた分解能で生成される。ケア画素及びドントケア画素を含む３×３のブロックそれぞれでは、エッジ画素以外のケア画素全ての平均がとられる。次いで、５×５の平均化フィルタを用いて、「ホール」全てが充填されるまで、前述の平均値を用いてドントケア画素を反復的に内挿する。この手法は、平均化においてエッジ画素を除外することを考慮に入れる。それによって、リンギング・アーチファクトが削減される。更なる情報については、Thierschmann他による「A  Scalable  DSP  Architecture  For  High-Speed  Color  Document  Compression、  Document  Recognition  and  Retrieval  VIII,  Kantor他、  Editors  Proceedings  of  SPIE  Vol.  4307  (2001),  San  Jose,  CA,  January  2001」を参照されたい。
【０００９】
マルチ分解能セグメント化及び充填（MSF）は、ウェーブレット領域において用いられるマルチ分解能データ充填アルゴリズムである。この手法は、データ充填のエッジ効果を処理する「非可逆エッジ」の考え方を用いる。更なる情報については、「Multi-resolution  Segmentation  and  Fill」と題する西暦2004年8月25日付け出願の米国特許出願第10/927,323号明細書を参照されたい。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
データ充填の方法及び装置を本明細書及び特許請求の範囲に記載する。
【課題を解決するための手段】
【００１１】
一実施例では、方法は、画像、及び画像に関連したマスクを受け取る工程と、ブロックベースの反復マルチパス・データ充填処理を実行して、複合文書の圧縮の一部として層を充填する工程とを備える。
【発明を実施するための最良の形態】
【００１２】
本発明は、以下に表す詳細な説明から、かつ、本発明の種々の実施例に付随する図面からより深く理解されるであろう。しかし、これらは、特定の実施例に本発明を限定するものとして解されるべきでなく、説明及び理解のために過ぎない。
【実施例】
【００１３】
データ充填の方法、装置及び製品について説明する。一実施例では、本明細書及び特許請求の範囲記載のデータ充填手法は、複合文書圧縮のために画像層を生成する。この手法は、「ケア」画素周辺の領域をブロックベースのスケールで反復的に発展させて、「ドントケア」画素及びエッジ画素を内挿する。これは、ケア画素領域近くの色の不連続性の可能性を潜在的に最小にし、よって、不可逆圧縮によるリンギング・アーチファクトを最小にする。
【００１４】
以下の説明では、数多くの詳細を表して本発明をより徹底的に説明している。しかし、こうした特定の詳細なしで本発明を実施し得ることは当業者には明らかであろう。一方、周知の構造及び装置は、詳細にではなく、構成図形式で示して、本発明を分かりにくくすることがないようにしている。
【００１５】
以下の詳細な説明の一部は、コンピュータ・メモリ内のデータ・ビットに対する演算のアルゴリズム及び記号表現によって提示している。前述のアルゴリズムの記述及び表現は、当該技術分野における他の当業者に自らの成果の本質を最も効果的に伝えるうえでデータ処理技術分野における当業者によって用いられる手段である。アルゴリズムは本明細書では、かつ一般には、所望の結果につながる筋の通った一連の工程であるように考え出されている。工程とは、物理的数量の物理的操作を必要とするものである。必然的ではないが通常は、前述の数量は、記憶、転送、合成、比較、及びその他の方法で操作することができる電気信号又は磁気信号の形式を呈する。ビット、値、構成要素、記号、文字、項、数字又は同様なものとして前述の信号を慣用の理由で場合によっては表すことが好都合であることが明らかになった。
【００１６】
しかし、前述及び同様な語は全て、適切な物理的数量と関連付けられるものとし、前述の数量に付される好都合なラベルに過ぎない。以下の記載から明らかなように別途明記しない限り、本明細書を通して、「processing」、「computing」、「calculating」、「determining」、「displaying」等などの語を利用した記載は、コンピュータ・システムのメモリ内、レジスタ内やその他のそうした情報記憶装置内、情報伝送装置内や情報表示装置内の物理的数量として同様に表す他のデータにコンピュータ・システムのレジスタ内及びメモリ内の物理的（電子的）数量として表すデータを操作し、変換する、コンピュータ・システム、又は同様な電子計算装置の動作及び処理を表す。
【００１７】
本発明は、本明細書及び特許請求の範囲記載の動作を行う装置にも関する。この装置は、必要な目的で特別に構成することができるか、又は、コンピュータに格納されたコンピュータ・プログラムによって選択的に起動又は再構成する汎用コンピュータを備え得る。前述のコンピュータ・プログラムは、コンピュータ読み取り可能な記憶媒体（電子命令を格納するのに適しており、それぞれがコンピュータ・システム・バスに結合されている何れかのタイプのディスク（フロッピー（登録商標）・ディスク、光ディスク、CDーROM及び光磁気ディスクを含む）、リード・オンリー・メモリ（ROM）、ランダム・アクセス・メモリ（RAM）、EPROM、EEPROM、磁気カード若しくは光カード、又は何れかのタイプの媒体（これらに限定されない）など）に格納することができる。
【００１８】
本明細書及び特許請求の範囲記載のアルゴリズム及びディスプレイは、何れの特定のコンピュータやその他の装置にも固有に関係していない。種々の汎用システムを本明細書及び特許請求の範囲記載の教示によってプログラムとともに用いることができるか、又は、要求される方法工程を実行するために、より専用の装置を構成することが好都合であることが明らかになり得る。前述の種々のシステムに要求される構造は以下の記載から明らかになる。更に、本発明は、何れの特定のプログラミング言語を参照しても説明されていない。各種のプログラミング言語を用いて、本明細書及び特許請求の範囲記載の本発明の教示を実現することができる。
【００１９】
マシン読み取り可能な媒体は、マシン（例えば、コンピュータ）によって読み取り可能な形式で情報を記憶するか又は伝送する何れかの機構を含む。例えば、マシン読み取り可能な媒体は、リード・オンリー・メモリ（「ROM」）、ランダム・アクセス・メモリ（「RAM」）、磁気ディスク記憶媒体、光記憶媒体、フラッシュ・メモリ装置、電気的、光学的、音響的やその他の形式の伝搬信号（例えば、搬送波、赤外線信号、ディジタル信号等）等を含む。
【００２０】
概要
ブロックベースの反復マルチパス・データ充填手法を記載する。この手法は、マスク及び元の画像を入力として取り込み、充填されたフォアグラウンド層及びバックグラウンド層を出力として生成する。図１は、マスク１０１と、元の画像１０２と、当初非充填のフォアグラウンド層１０３及びバックグラウンド層１０４との例を示す。一実施例では、フォアグラウンド層１０３及びバックグラウンド層１０４は８×８のブロックに分離される。しかし、他のブロック・サイズ（正方形でないブロック・サイズを含む）を用いることができる。
【００２１】
簡単にするために、以下の記載は２つの層の一方（例えば、フォアグラウンド層）に手法を適用することにのみ焦点を当てる。しかし、同様なことが、他方の層（例えば、バックグラウンド層）にあてはまる。
【００２２】
フォアグラウンド層の場合、本明細書及び特許請求の範囲の目的で、マスク内に示される黒色の画素は全て「ケア」画素（すなわち、関係する画素）として規定され、白色の画素は全て、「ドントケア」画素（すなわち、関係がない画素）として規定される。一実施例では、フォアグラウンド層のケア画素のみを用いて復号化画像を再構成する。
【００２３】
図２は、複合文書圧縮器の一実施例の構成図である。図２を参照すれば、ラスタ画像２０１がマスク生成装置２０２に入力される。これに応答して、マスク生成装置２０２がマスク２１０を生成する。マスク２１０は、可逆圧縮装置２０６による可逆圧縮を受ける。一実施例では、可逆／非可逆圧縮装置２０６は、周知の圧縮手法（例えば、これらに限られないが、JBIG、JBIG2、MMR等など）を行う。可逆圧縮装置２０６の出力は、圧縮されたマスク・データである。
【００２４】
マスタ２１０及びラスタ画像２０１は、マルチパス・データ充填装置２０３にも入力される。前述の入力に応答して、マルチパス・データ充填装置２０３は、データ充填処理を実行し、フォアグラウンド層２１１及びバックグラウンド層２１２を生成する。一実施例では、マルチパス・データ充填装置２０３は、ブロックベースの反復マルチパス・データ充填処理を実行して、複合文書圧縮の一部としてバックグラウンド層２１２及びフォアグラウンド層２１１を生成する。
【００２５】
一実施例では、ブロックベースの反復マルチパス・データ充填処理は、ブロック分類を行い、次いで、ブロック内の画素に値をその分類に基づいて反復処理を用いて割り当てる工程を備える。一実施例では、画素ブロックを分類する工程は、まず、各画素を２つのタイプ（すなわち、エッジ画素及び非エッジ画素）の一方に分類し、次いで、ブロックを別々のタイプに、各ブロックにおけるエッジ画素、ドントケア画素及びケア画素の見え方によって分類することによって行われる。画素を分類する１つの方法は、各画素を中心とした画素分類ウィンドウを検査する工程と、ウィンドウ内の何れかの画素が、その画素とは異なるマスク値を有するかを判定する工程と、ウィンドウ内のその画素周辺の何れかの画素がその画素とは異なるマスク値を有する場合にその画素をエッジとして分類する工程とを備える。一実施例では、この画素分類ウィンドウは3×3のウィンドウである。
【００２６】
分類後、ブロックへの値の割り当てが行われる。一実施例では、層（例えば、フォアグラウンド層又はバックグラウンド層）の１つ又は複数のブロック（例えば、エッジを備えたブロック）毎の値の割り当ては、そのブロックを含むウィンドウ内の画素値の平均に基づく。前述の場合には、ウィンドウはブロック・サイズよりも大きい。例えば、一実施例では、ウィンドウが２４画素×２４画素である一方、ブロック・サイズは８画素×８画素である。別の実施例では、ウィンドウ・サイズは形状が矩形であり、少なくとも一側部は、ブロック・サイズの倍数でない。
【００２７】
ウィンドウ・サイズ選択は、複合文書圧縮に用いる圧縮アルゴリズム、複合文書圧縮に用いる変換、及び画像のコンテンツを有する群のうちの１つ又は複数に基づく。
【００２８】
図２に戻れば、一実施例では、フォアグラウンド層２１１はスケーリング装置２０４によってスケーリングされ、スケーリング装置２０４はスケーリングされたフォアグラウンド層を出力し、バックグラウンド層２１２はスケーリング装置２０５によってスケーリングされる。
【００２９】
何れかの任意のスケーリング後、フォアグラウンド層２１１は圧縮器２０７を用いて圧縮される。一実施例では、圧縮器２０７は非可逆圧縮を実行する。一実施例では、圧縮器２０７はJPEG２０００圧縮を行う。別の実施例では、圧縮器２０７はJPEG圧縮を行う。圧縮器２０７は圧縮データ２２０の一部を出力する。
【００３０】
更に、何れかの任意のスケーリング後、バックグラウンド層２１２は圧縮器２０８を用いて圧縮される。一実施例では、圧縮器２０８は非可逆圧縮を実行する。一実施例では、圧縮器２０８はJPEG２０００圧縮を行う。別の実施例では、圧縮器２０８はJPEG圧縮を行う。圧縮器２０８は圧縮データ２２０の一部を出力する。
【００３１】
データ充填処理の一実施例の例
一実施例では、データ充填処理は、画素分類と、ブロック分類と、初期化手順と、それに続く、層（例えば、フォアグラウンド、バックグラウンド等）におけるデータの処理ブロックの複数パスとを含む。
【００３２】
ブロック分類に関しては、一実施例において、初期化として、非充填フォアグラウンド層の８×８ブロック全てが、３つのタイプのうちの１つにマスク画像を用いて分類される。前述の３つのタイプは、内部ブロック、「ドントケア」ブロック及びエッジ・ブロックを含む。内部ブロックはケア画素のみを含み、ドントケア・ブロックはドントケア画素のみを含み、エッジ・ブロックは、ケア画素及びドントケア画素の混合を含む。図３は３つのブロック・タイプの例を示す。文字「I」、「X」及び「E」は、フォアグラウンド層に現れている「R」画像に対して、内部ブロック、ドントケア・ブロック及びエッジ・ブロックを別個に示す。
【００３３】
一実施例では、データ充填ステータス・テーブルが、各パスにおける各ブロックの充填ステータスを把握するためにデータ充填処理全体を通じて維持される。一実施例では、テーブル内のステータスについて３つの値が規定される。
【００３４】
0‐非充填ブロック
1‐このパスにおいて充填されたばかりのブロック
2‐先行パスにおいて充填されたブロック
他のマーキング手法を用いることができることを当業者は認識するであろう。
【００３５】
一実施例では、第１のパスに先行する初期化手順の一部として、データ充填ステータス・テーブルにおいて維持される各ブロックのデータ充填ステータスは、ブロックが非充填である旨を示すようセットされる（例えば、0にセットされる）。各パスの終わりに、かつ次のパスの開始の前に、テーブルにおいて番号１を備えた、充填されている場所全てが番号２に変更される。各パス中に、処理されたブロックのステータスは、充填された直後に１にセットされる。図５は、データ充填手順全体の順次パス及び関連したステータス・テーブルを示す。図５を参照すれば、左列が、フォアグラウンド層に対するデータ充填手順のセグメント化されたパスを示す一方、右列はステータス・テーブルを示す。ゼロのパスでは、ブロック毎のデータ充填ステータスが非充填である旨をステータス・テーブルは示す。第１のパス後、ブロックの大半のデータ充填ステータスは、なお非充填である一方、ブロックの一部は、充填されているものとして示されている（第１のタイプのクロスハッチングによって示されている）。第２のパス後、先行パスにおいて充填されているものは、先行パスとは別の第２のタイプのクロスハッチングによって示されている一方、一部のブロックは非充填として示されており、他のものはこのパスにおいて充填されたものとして第１のタイプのクロスハッチングによって示されている。最後に、最後のパスでは、ブロックは全て、先行パスにおいて充填されているものとして第２のタイプのクロスハッチングを用いて示されている。
【００３６】
初期化後、特別な第１のパスが実行される。第１のパスでは、エッジ・ブロック及び内部ブロック全てが処理される。内部ブロック毎に、元の画像からの画素値が複製され、ブロック内、及び充填されたフォアグラウンド内又はバックグラウンド内のその対応する画素位置に割り当てられる。エッジ・ブロック毎に、現行エッジ・ブロックをその中心に有するより大きなウィンドウが選択される。一実施例では、ウィンドウは、図４に示すように２４×２４である。前述のように他のウィンドウ・サイズを用いることができる。前述のウィンドウは、形状が正方形（例えば、１２×１２）であり得るか、又は、形状が矩形であり、２つの側部とは寸法が異なる上部及び底部を有する。フォアグラウンドの現行ブロックのドントケア画素には次いで、ウィンドウ内のケア画素の平均の値が割り当てられる。現行ブロックに対応するデータ充填ステータスにおけるエントリは次いで、現行パスにおいて充填された旨を示すよう（例えば、１に）セットされる。現行ブロックの平均値は、後に用いるためにメモリ・バッファに保存される。第１のパスの最後に、データ充填ステータス・テーブルにおける１の値全てが２に変更される。
【００３７】
特別な第１のパスを実行した後、１つ又は複数の後続パスが実行される。後続パスでは、充填されたエッジ・ブロック及び内部ブロックの値を用いてドントケア・ブロックを反復的に内挿する。各パスでは、非充填ブロック毎に、その８つの近傍ブロック毎のデータ充填ステータスがまず検査される。８つの近傍ブロックが何れも、先行パスにおいて充填されていない場合、現行ブロックのデータ充填ステータスは、非充填に留まり、現行パスについてスキップされる。さもなければ、現行ブロックの各画素には、先行パスにおいて充填された近傍ブロック全ての平均の平均値が割り当てられる。現行ブロックのデータ充填ステータスは、現行ブロックがこのパスにおいて充填された旨を示すようデータ充填ステータス・テーブルにおいてセットされる（例えば、１にセットされる）。現行ブロックの平均値は、次のパスに用いるためにブロック平均バッファに保存される。各パスの最後に、データ充填ステータス・テーブルにおける１の値全てが２に変更される。
【００３８】
フォアグラウンド層（及びバックグラウンド層）のブロック全てが充填されると反復手順が終了する。
【００３９】
図9は、データ充填処理の一実施例において第１のパスを実行する処理の一実施例を示すフロー図である。この処理は画素の分類に続く。処理は、ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア（汎用コンピュータ・システム上若しくは専用マシン上で実行されるものなど）、又は両方の組み合わせを備え得る処理ロジックによって実行される。
【００４０】
図９を参照すれば、処理は、層の選択から始まる（処理ブロック９０１）。層は、フォアグラウンド層又はバックグラウンド層であり得る。前述の層から、処理ロジックは第１のブロックを選択する（処理ブロック９０２）。一実施例では、ブロックは、フォアグラウンド層又はバックグラウンド層における８×８のブロックである。ブロックを選択した後、処理ロジックは、ブロックがドントケア・ブロックであるかを判定する（処理ブロック９０３）。肯定の場合、処理は処理ブロック９１０に移行する。処理ブロック９１０では、処理ロジックは、現行ブロックが最終ブロックであるか否かを検査する。肯定の場合、パスは終了する。否定の場合、処理は処理ブロック９０４に移行する。処理ブロック９０４では処理ロジックは次のブロックを選択し、処理は処理ブロック９０３に続く。
【００４１】
処理ブロック９０３では、ブロックがドントケア・ブロックでない場合、処理ブロックは、ブロックが内部ブロックであるか否かを検査する（処理ブロック９０５）。肯定の場合、処理ブロックは、元の画像からの元の画素値でブロックを充填し（処理ブロック９０６）、このパスにおいて充填された旨を示すようブロックのブロック充填ステータスをセットし（処理ブロック９０７）、処理は、処理ブロック９１０に移行し、処理ブロック９１０では処理が続く。
【００４２】
ブロックが内部ブロックでない場合、処理は処理ブロック９０８に移行する。処理ブロック９０８では、処理ロジックは、ブロック内のケア画素を、元の画像からの元の画素値で充填し、ブロック内のドントケア画素を、ブロックよりも大きなウィンドウ領域におけるケア画素全部の平均で充填する。一実施例では、ウィンドウは２４×２４のウィンドウであるが、他のウィンドウを選択することができる。その後、処理ロジックは、ブロックがこのパスにおいて充填された旨を示すようブロック充填ステータスをセットし（処理ブロック９０９）、処理は、処理ブロック９１０に移行する。処理ブロック９１０では、処理が続く。
【００４３】
図10は、データ充填処理の第１の実施例における後続パスを実行する処理の一実施例を示すフロー図である。処理は、ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア（汎用コンピュータ・システム上若しくは専用マシン上で実行されるものなど）、又は両方の組み合わせを備え得る処理ロジックによって実行される。
【００４４】
図10を参照すれば、処理は、層の選択から始まる（処理ブロック１００１）。一実施例では、処理ロジックはフォアグラウンド層又はバックグラウンド層を選択する。前述の層から、処理ロジックは第１のブロックを選択する（処理ブロック１００２）。一実施例では、ブロックは、８×８のブロックである。他のブロック・サイズを用いることができる。
【００４５】
処理ロジックは次いで、ブロックが非充填ブロックであるか否かを検査する（処理ブロック１００３）。否定の場合、処理は処理ブロック１００８に移行する。処理ブロック１００８では、処理ロジックは、現行ブロックが最終ブロックであるか否かを検査する。肯定の場合、処理は終了する。否定の場合、処理は処理ブロック１００４に移行する。処理ブロック１００４では、処理ロジックは次のブロックを選択し、処理は処理ブロック１００３に続く。処理ブロック１００３では、ブロックが非充填ブロックの場合、処理ロジックは、何れかの先行パスにおいて充填された周囲ブロックが存在しているかを検査する（処理ブロック１００５）。否定の場合、処理は処理ブロック１００８に移行する。処理ブロック１００８では処理が続く。周囲ブロックの１つ又は複数が先行パスにおいて充填された場合、処理ロジックはブロックを、先行パスにおいて充填された周囲ブロック全ての値の平均の平均値で充填し（処理ブロック１００６）、現行パスにおいてブロックが充填された旨を示すようブロック充填ステータスをセットし（処理ブロック１００７）、次いで、処理は処理ブロック１００８に移行し、処理ブロック１００８では処理が続く。
【００４６】
特別なエッジ処理を備えた別のデータ充填の実施例
前述のデ―タ充填処理に対する精緻化は、ブロックの内挿のための平均化においてエッジ効果を考慮に入れる。前述の実施例とこの実施例との差を以下に説明する。
【００４７】
ブロックの分類に関しては、初期処理として、エッジ画素全てが、ブロック内挿における特別な処理に用いるために、バイナリ・マスク画像において検出される。図６に示すように、画素は、所定のサイズのウィンドウ（例えば、３×３のウィンドウ）におけるその近傍の何れかとは異なるマスク値（すなわち、黒又は白）を有する場合、エッジとして検出される。一実施例では、ブロック分類処理は、エッジ画素を備えた内部ブロック、エッジ画素なしの内部ブロック、エッジ画素を備えたドントケア・ブロック、エッジ画素なしのドントケア・ブロック、及び（ドントケア画素、エッジ画素及びケア画素を備えた）エッジ・ブロックを含む５つのブロック・タイプ・カテゴリーに分類する。内部ブロック、ドントケア・ブロック及びエッジ・ブロックの定義は、前述と同様である。
【００４８】
図７は、５つのブロック・タイプの例を示す。ここで文字「U」、「I」、「V」、「X」及び「E」は、エッジ画素を備えた内部ブロック、エッジ画素なしの内部ブロック、エッジ画素を備えたドントケア・ブロック、エッジ画素なしのドントケア・ブロック、及びエッジ・ブロックそれぞれに対応する。ブロックAが含んでいるのは全てケア画素であり、ブロックBが含んでいるのは全てドントケア画素である。しかし、何れも、ブロック境界に沿ってエッジ画素を含む。
【００４９】
前述のように、データ充填ステータス・テーブルを用いて、層内のブロックの充填ステータスを追跡する。この実施例における定義及び更新の手順は、前述の実施例と同様である。図８は、後述する特別なエッジ処理を備えたデータ充填手順全体の順次パス及び関連したスタータス・テーブルを示す。図８が、エッジ付近の領域が図５中のものよりもずっと平滑である（これは、特別なエッジ処理を施すことによってリンギング・アーチファクトをかなり削減することが可能であることを示す）ことを示していることが分かる。図8を参照すれば、左列が、フォアグラウンド層に対するデータ充填手順のセグメント化されたパスを示す一方、右列はステータス・テーブルを示す。ゼロのパスでは、ブロック毎のデータ充填ステータスが非充填である旨をステータス・テーブルは示す。第１のパス後、ブロックの大半のデータ充填ステータスは、なお非充填である一方、より多くのブロックが、充填されているものとして示されている（第１のタイプのクロスハッチングによって示されている）。第２のパス後、先行パスにおいて充填されているものは、先行パスとは別の第２のタイプのクロスハッチングによって示されている一方、一部のブロックは非充填として示されており、他のものはこのパスにおいて充填されるものとして第１のタイプのクロスハッチングによって示されている。最後に、最終パスでは、ブロックは全て、先行パスにおいて充填されているものとして第２のタイプのクロスハッチングを用いて示されている。
【００５０】
第１の特別なパスに関しては、エッジ効果がブロック内挿において考慮に入れられる。このパスでは、タイプ「I」、「E」、「U」及び「V」を備えたブロックが処理される。特に、図４に示すようにウィンドウ（例えば、２４×２４のウィンドウ）における画素値に基づいた値を割り当てる場合、現行ブロックにおけるエッジ画素又はドントケア画素それぞれには、ウィンドウ内の非エッジのケア画素全ての平均値が割り当てられる。この平均値はブロック平均バッファに保存される。ブロック内にエッジ画素しか存在しておらず、ウィンドウ内に非エッジのケア画素が存在していない場合、現行ブロック内のケア画素全てに割り当てられる値は、元の画像における対応する画素位置の値である。すなわち、平均化は行われない。データ充填ステータスは更に、現行ブロックについてブロックが非充填である旨を示すよう（例えば、0に）セットされる。
【００５１】
後続パスでは、１つの特別な処理のみが考慮に入れられる。非充填ブロック毎に、ケア画素があれば、ケア画素は全て、変わらない状態に維持され、ブロック内の他の画素（ドントケア画素）は全て、前述の実施例と同様に内挿される。内挿画素の平均もブロック平均バッファに保存される。
【００５２】
同様に、このデータ充填処理は、前述の実施例と同様に終了する。
【００５３】
図11は、データ充填処理の別の実施例において第１のパスを実行する処理の一実施例を示すフロー図である。処理は、ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア（汎用コンピュータ・システム上若しくは専用マシン上で実行されるものなど）、又は両方の組み合わせを備え得る処理ロジックによって実行される。
【００５４】
図11を参照すれば、処理は、処理ロジックによる、層の選択から始まる（処理ブロック１１０１）。処理ロジックはフォアグラウンド層又はバックグラウンド層を選択することができる。処理ロジックは次いで、第１のブロックを、選択された層から選択する（処理ブロック１１０２）。一実施例では、処理ロジックは、８×８のブロックを選択する。しかし、他のブロック・サイズを用いることができる。
【００５５】
ブロックを選択した後、処理ロジックは、現行ブロックが、エッジ画素なしのドントケア・ブロックであるか否かを検査する（処理ブロック１１０３）。肯定の場合、処理は処理ブロック１１１４に移行する。処理ブロック１１１４では、処理ロジックは、現行ブロックが最終ブロックであるか否かを検査する。肯定の場合、パスは終了する。否定の場合、処理ロジックは次のブロックを選択し（処理ブロック１１０５）、処理ブロック１１０３に移行する。処理ブロック１１０３では処理が続く。ブロックが、エッジ画素なしのドントケア・ブロックでない場合、処理ロジックは、現行ブロックが、エッジ画素なしの内部ブロックであるか否かを検査する（処理ブロック１１０５）。肯定の場合、処理ブロックは、元の画像における対応する画素位置からの値で現行ブロックを充填し（処理ブロック１１０６）、このブロックがこのパスにおいて充填された旨を示すようブロック充填ステータスをセットし（処理ブロック１１０７）、処理は、処理ブロック１１１４に移行し、処理ブロック１１１４では処理が続く。
【００５６】
現行ブロックが、エッジ画素なしの内部ブロックでない場合、処理ロジックは処理ブロック１１０８に移行する。処理ブロック１１０８では、処理ロジックは、より大きなウィンドウにおける非エッジのケア画素の数を集計する。一実施例では、ウィンドウは２４画素×２４画素である。しかし、ブロック・サイズよりも大きな他のウィンドウ・サイズを用いることができる。より大きなウィンドウにおける非エッジのケア画素の数を集計した後、処理ロジックは、現行ブロックにおいて非エッジのケア画素が存在しているか否かを検査する（処理１１０９）。否定の場合、処理ブロックは、元の画像における対応する画素位置の値で現行ブロック内エッジ画素のみを充填し（処理ブロック１１１０）、現行ブロックがこのパスにおいて非充填である旨を示すようブロック充填ステータスをセットし（処理ブロック１１１１）、処理は、処理ブロック１１１４に移行し、処理ブロック１１１４では処理が続く。現行ブロック内に１つ又は複数の非エッジのケア画素が存在している場合、処理ブロックは、元の画像における対応する画素位置の値で非エッジのケア画素を充填し、２４×２４のウィンドウにおける非エッジのケア画素全ての平均でブロックにおける他の画素全てを充填し（処理ブロック１１１２）、現行ブロックがこのパスにおいて充填された旨を示すようブロック充填ステータスをセットし（処理ブロック１１１３）、処理は、処理ブロック１１１４に移行し、処理ブロック１１１４では処理が続く。
【００５７】
図12は、データ充填処理の図１１に対応する別の実施例における後続パスを実行する処理の一実施例を示すフロー図である。処理は、ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア（汎用コンピュータ・システム上若しくは専用マシン上で実行されるものなど）、又は両方の組み合わせを備え得る処理ロジックによって実行される。
【００５８】
図12を参照すれば、処理は、層の選択から始まる（処理ブロック１２０１）。一実施例では、処理ロジックはフォアグラウンド層又はバックグラウンド層を選択することができる。前述の層から、処理ロジックは第１のブロックを選択する（処理ブロック１２０２）。一実施例では、ブロックは、８×８のブロックである。他のブロック・サイズを用いることができる。
【００５９】
処理ロジックは次いで、現行ブロックが非充填ブロックであるか否かを検査する（処理ブロック１２０３）。否定の場合、処理は処理ブロック１２０８に移行する。処理ブロック１２０８では、処理ロジックは、現行ブロックが最終ブロックであるか否かを検査する。肯定の場合、パスは終了する。否定の場合、処理は処理ブロック１２０４に移行する。処理ブロック１２０４では、処理ロジックは次のブロックを選択し、処理は処理ブロック１２０３に続く。ブロックが非充填ブロックの場合、処理ロジックは、先行パスにおいて充填された周囲ブロックが存在しているかを検査する（処理ブロック１２０５）。否定の場合、処理は処理ブロック１２０８に移行する。処理ブロック１２０８では処理が続く。先行パス中に充填された周囲ブロックが１つ又は複数存在している場合、処理ロジックは、現行ブロックにおけるドントケア画素を、先行パス充填周囲ブロックの画素全ての平均の平均値で充填し（処理ブロック１２０６）、ブロック充填ステータスを「このパスにおいて充填された」にセットし（処理ブロック１２０７）、処理は処理ブロック１２０８に移行し、処理ブロック１２０８では処理が続く。
【００６０】
他の実施例
最終番号のパスの変形
前述のように、データ充填処理は、終了するためにいくつかのパスを要し得る。例えば、画像の最上行に一エッジ・ブロックしか存在していない場合（で、内部ブロックが存在していない場合）、ページの左下のブロックの内容を判定するために画像内のブロックの全行について一パスが必要である。前述のパスは、計算量が少ないが、一部のアプリケーションの場合、複数回、メモリを巡回しないことが重要である。よって、一実施例では、特定の固定数のパス後、「最終」パスを実行することが可能である。最終パスでは、未判定画素を有する各ブロックが、判定された画素を備えた最も近いブロックの画素値のブロック平均にセットされる。最も近い単一ブロックが2つ以上存在している場合、ブロックには、最も近いブロック全てのブロック平均の平均値が割り当てられる。一実施例では、判定された画素を備えた最も近いブロックを判定しなくてもよいようにグレイレベル中点値を最終パスにおいて用いる。別の実施例では、ブロックに所定値が割り当てられる。
【００６１】
最も近い判定画素ブロックを最終パスにおいて用いることによって、ある程度の非対称性が画像にもたらされる一方、このことは、何れのエッジ画素からも遠い所で生じ、よって、再構成値に影響を及ぼさない。
【００６２】
ローリング・バッファの変形
場合によっては、固定数の行で動作することが有益である。MRCを、固定サイズのバッファにおいて動作する圧縮アルゴリズム及びセグメント化アルゴリズムに用いることができる。固定サイズのバッファにおいてこのデータ充填とMRCを行うためには、特定の修正が必要である。画像の幅と幅が同じであり、N行の深さを有するバッファが利用可能な場合、データ充填は次のように行うことが可能である（この場合の行は、ブロックの行である。）
次の手順を繰り返す。この手順は、ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア（汎用コンピュータ・システム上若しくは専用マシン上で実行されるものなど）、又は両方の組み合わせを備え得る処理ロジックによって実行される。ローリング・バッファに関連した処理ロジックは、画素及びマスクのブロックの一行をバッファに読み出す。エッジ・ブロックの判定はこの行について行うことが可能でない。この行の下の画素は未知であるからである。処理ロジックは、第２の行におけるブロックがエッジ・ブロックであるか、内部ブロックであるか、又は「ドントケア」ブロックであるかを判定する。第３乃至第N−１の行では、処理ロジックは、通常の割り当て処理の一パスを実行する（先行パスにおいて判定されたブロックの隣のブロックの画素を判定する）。ブロックの第Nの行について、処理ロジックは、「最終」パスを実行し、ブロックの第Nの行を出力ファイルに書き出す。出力を書き出すための処理は最初のN−１回、スキップされる。ブロックはまだ画像画素を含んでいないからである。その後、処理ロジックはブロック全てを一行上に移動させる。バッファ内容のサンプルを以下に示す。
【００６３】
この行には最終パスが行われている（第Nの行）
この行は通常のパスを行う（第N−１の行）
この行は通常のパスを行う（第３の行）
エッジ・ブロック、内部ブロック、ドントケア・ブロックを判定する（第２の行）
読み込む。しかし処理しない（第１の行）
当然、高速の実現形態は、ブロックの行が上に移動させられた際の画素の複製を避けるためにポインタを用いる。
【００６４】
この手法の潜在的な課題は、平衡のとれていない色境界が２つのテキスト領域間に生じ得ることである。例えば、最上行がテキスト領域（例えば、A）を含んでおり、最下行又はその近くの場所が、異なるフォアグラウンド色を備えた別のテキスト領域（例えば、B）を含んでいる場合、ローリング・バッファ手法は結局、領域Aと領域Bとの間の大半のドントケア領域を領域Aの色でのみ充填することになる。これは、領域A及び領域Bが、ローリング・バッファ手法の下で同時に展開される訳でないからである（すなわち、Bは常にA後に展開し、したがって、Aが常に優性である）。この課題を避けるために、一実施例では、特定の更なるパスを行って、領域Aの色によって既を充填された、AとBとの間にあるがBに近いドントケア領域内のデータ充填を更新する。これは、計算量をある程度増やすことになる。
【００６５】
データ充填及び画像スケーリングの合成
図２に示すように、フォアグラウンド層及びバックグラウンド層は任意的には、データ充填処理に続いてスケーリング（通常、ダウンサンプリング）される。この場合、画像のスケーリング処理及びデータ充填処理は互いに無関係である。本願のデータ充填方法はこのようにして動作し得るが、データ充填処理をスケーリング処理と合成すると、改良された性能を得ることが可能である。
【００６６】
図１４は、前述のプロセッサのブロック図である。データ・ファイル処理をスケーリングと合成するために、充填された画像のバッファ２２２は、元の画像サイズでなく、スケーリングされたサイズで割り当てられる。スケーリングは通常、ダウンスケーリングであるため、これはより小さなバッファになる。「内部画素」（すなわち、非エッジのケア画素）は、充填されたバッファ２２２に複製される場合、スケーリング係数１４０１に基づいてスケーリングされる。このスケーリング処理は、一度に一データ・ブロックに対してしか行われない。ドントケア画素が判定される場合、スケーリングは必要でなく、スケーリングされたブロック全体には単に平均値が充填される。
【００６７】
スケーリングが行われる場合、一実施例では、ブロック・サイズが変えられる。例えば、3分の１の係数（非常に一般的な係数）を用いてダウンスケーリングする場合、９×９のブロック・サイズを用いることが有用である。このようにして、各ブロックは、スケーリングされた画素の３×３のブロックに対応する。
【００６８】
スケーリング及びデータ充填の合成はいくつかの利点を有する。例えば、スケーリング及びデータ充填の合成によって計算量が削減され、データ充填アルゴリズムは、圧縮システムによって使用される画素を上回る画素を判定しなくてよく、充填されている（フォアグラウンド及びバックグラウンドが考慮に入れられる場合、画素の少なくとも５０％には、特定の平均値が充填されることになる）画素のスケーリングは必要でない。ブロック・サイズは、スケーリング係数に基づいて選ぶことが可能である。更に、無関係に最適化するのではなく、スケーリングを含めることによってシステムを品質について最適化することが可能であるので、フォアグラウンド及びバックグラウンドの品質を向上させることが可能である。
【００６９】
本明細書記載の説明は、フォアグラウンド、バックグラウンド及びマスクの使用を示しているが、特定の圧縮システムでは、複数の層を用いる。複数の層の場合、再構成は以下のように進み得る。まず、現行画像がバックグラウンド画像にセットされる。次いで、更なる層毎に、マスク・オブジェクト及び画像オブジェクトが存在している。画像オブジェクトからの画素を、現行画像にマスク・オブジェクトに基づいて混合する。このことは、JPM標準（ISO／IEC１５４４４−６）に詳細に記載されている。
【００７０】
本願開示の場合、各画像オブジェクトに対応するマスクは、「ケア」、「ドントケア」及び「エッジ画素」の判定に用いるものであることを認識することが重要である。バックグラウンド画像の場合、圧縮ファイルに格納されたマスクは存在しない。実際に、ドントケア画素は、他の層全てからのマスクを合成することによって判定される（一層におけるケア画素である画素は何れも、バックグラウンドにおけるケア画素でない）。
【００７１】
JPMを含む特定の階層型文書圧縮手法においてグレイスケール・マスクを用いることも考えられる。この場合、２つの層を、マスクの値に比例して混合する。画素を充填する方法を判定する目的でケア画素及びドントケア画素を判定するために、バイナリ・マスクを生成することが必要である。バイナリ・マスクは、当業者に知られているいくつかのやり方でグレイスケール・マスクから作成することが可能である。最も単純な方法は、マスクを閾値処理する（すなわち、特定値を上回る値全てを１に変換し、それ以外全てをゼロに変換する）ことである。フォアグラウンド及びバックグラウンドに別々のマスクを用いることが望ましいことがあり得る。例えば、グレイスケール・マスクが中位値（例えば、１２８）を有する場合、フォアグラウンド及びバックグラウンドにおいて画素が「ケア」画素であることが望ましいことがあり得る。これは高品質につながる。あるいは、１２８の中位値を備えたマスク画素は、フォアグラウンド及びバックグラウンドにおいて「ドントケア」とみなし得る。これは、高い圧縮性能につながる。
【００７２】
コンピュータ・システムの例
図１３は、本明細書及び特許請求の範囲記載の１つ又は複数の動作を実行することができる例示的なコンピュータ・システムを示すブロック図である。図１３を参照すれば、コンピュータ・システム１３００は、例示的なクライアント・サーバ・コンピュータ・システムを備え得る。コンピュータ・システム１３００は、情報を通信する通信機構すなわちバス１３１１と、バス１３１１に結合され、情報を処理するプロセッサ１３１２とを含む。プロセッサ１３１２は、マイクロプロセッサ（例えば、ペンティアム(登録商標)、パワーPC（商標）、アルファ（商標）等など）を含むが、マイクロプロセッサに限定されない。
【００７３】
システム１３００は、バス１３１１に結合され、情報、及びプロセッサ１３１２によって実行される対象の命令を記憶するランダム・アクセス・メモリ（RAM）やその他のダイナミック記憶装置１３０４（主メモリと表す）を更に備える。主メモリ１３０４は、プロセッサ１３１２による命令の実行中の一時変数やその他の中間情報の記憶にも用いることができる。
【００７４】
コンピュータ・システム１３００は、バス１３１１に結合され、スタティック情報と、プロセッサ１３１２のための命令とを記憶するリード・オンリー・メモリ（ROM）及び／又はその他のスタティック記憶装置１３０６、並びに、データ記憶装置１３０７（磁気ディスク又は光ディスク、及びその対応するディスク・ドライブなど）も備える。データ記憶装置１３０７は、バス１３１１に結合され、情報及び命令を記憶する。
【００７５】
コンピュータ・システム１３００は、バス１３１１に結合され、コンピュータ・ユーザに向けて情報を表示する表示装置１３２１（陰極線管（CRT）ディスプレイや液晶ディスプレイ（LCD）など）に更に結合され得る。英数字入力装置１３２２（英数字キーやその他のキーを含む）は更に、情報及びコマンド選択をプロセッサ１３１２に通信するためにバス１３１１に結合され得る。更なるユーザ入力装置は、バス１３１１に結合され、方向情報及びコマンド選択をプロセッサ１３１２に通信し、ディスプレイ１３２１上のカーソル移動を制御するカーソル制御部１３２３（マウス、トラックボール、トラックパッド、スタイラスやカーソル方向キーなど）である。
【００７６】
バス１３１１に結合することができる別の装置は、媒体（紙、フィルムや同様なタイプの媒体など）上に情報をマーキングするのに用いることができるハードコピー装置１３２４である。バス１３１１に結合することができる別の装置は、電話機、又はハンドヘルド型パーム・デバイスに通信するための有線／無線通信機能部１３２５である。
【００７７】
システム１３００及び関連したハードウェアの構成部分の何れか又は全てを本発明において用いることができる。しかし、コンピュータ・システムの他の構成は、装置の一部又は全部を含み得る。
【００７８】
発明の多くの改変及び修正が、当業者が前述の記載を読んだ後に明らかになることに疑いの余地はないが、例証として示し、説明している特定の実施例は何れも、限定的であるとみなされることを意図するもので決してない。したがって、種々の実施例の詳細への参照は、本発明に不可欠なものとみなす構成のみをそれ自体が記載した特許請求の範囲記載の範囲を限定することを意図するものでない。
【図面の簡単な説明】
【００７９】
【図１】フォアグラウンド層及びバックグラウンド層へのポインタを備えた元の画像及びマスクの例を示す図である。
【図２】複合文書圧縮システムの一実施例の構成図である。
【図３】３つの分類ブロック・タイプ（内部ブロック、ドントケア・ブロック及びエッジ・ブロック）の例を示す図である。
【図４】図３の例の上に配置された２４×２４のウィンドウを示す図である。
【図５】データ充填手順の例を示す図である。
【図６】マスク領域内の３×３の近傍におけるエッジ画素検出を示す図である。
【図７】エッジ画素を備えた内部ブロックと、エッジ画素なしの内部ブロックと、エッジ画素を備えたドントケア・ブロックと、エッジ画素なしのドントケア・ブロックと、エッジ・ブロックとの５つの分類ブロック・タイプの例を示す図である。
【図８】特別なエッジ処理を備えたデータ充填手順の一実施例の順次パス及び関連したスタータス・テーブルを示す図である。
【図９】第１のデータ充填手法の第１のパスを実行する処理の一実施例を示すフロー図である。
【図１０】第１のデータ充填手法における後続パスを実行する処理の一実施例を示すフロー図である。
【図１１】第２のデータ充填手法における第１のパスを実行する処理の一実施例を示すフロー図である。
【図１２】第２のデータ充填手法における後続パスを実行する処理の一実施例を示すフロー図である。
【図１３】本明細書及び特許請求の範囲記載の１つ又は複数の動作を実行することができる例示的なコンピュータ・システムを示すブロック図である。
【図１４】複合文書圧縮器の別の実施例の構成図である。
【符号の説明】
【００８０】
101  マスク
102  元の画像
103  非充填フォアグラウンド
104  非充填バックグラウンド
201  ラスタ画像
202  マスク生成
204  スケーリング
205  スケーリング
206  可逆圧縮
207  非可逆圧縮
208  非可逆圧縮
210  マスク
211  フォアグラウンド
212  バックグラウンド
220  圧縮データ
221  ステータス・バッファ
222  充填されたバッファ
302  マルチパス・データ充填
1300  コンピュータ・システム
1304  主メモリ
1306  スタティック・メモリ
1307  大容量記憶メモリ
1311  バス
1312  プロセッサ
1320  外部ネットワーク・インタフェース
1321  ディスプレイ
1322  キーボード
1323  カーソル制御装置
1324  ハードコピー装置
1401  スケール係数
1403  ブロック・スケーリングを備えたデータ充填
【図１】
2008054325.tif 000003
【図２】
2008054325.tif 000004
【図３】
2008054325.tif 000005
【図４】
2008054325.tif 000006
【図５】
2008054325.tif 000007
【図６】
2008054325.tif 000008
【図７】
2008054325.tif 000009
【図８】
2008054325.tif 000010
【図９】
2008054325.tif 000011
【図１０】
2008054325.tif 000012
【図１１】
2008054325.tif 000013
【図１２】
2008054325.tif 000014
【図１３】
2008054325.tif 000015
【図１４】
2008054325.tif 000016