(57)【特許請求の範囲】
【請求項１】
文書イメージのカラースペースを変換するカラースペースコンバータと、
前記カラースペースコンバータから前記文書イメージを受け取り、ピクセルエネルギーの最小化に少なくとも一部は基づき前記文書イメージのペアにより少なくとも一部は領域をマージすることにより前記文書イメージのマスクを生成するマスクセパレータと、
前記マスクセパレータから前記マスクを受け取り、前記マスクを処理するマスクプロセッサコンポーネントと、
前記マスクに従って前記文書イメージを前景イメージおよび背景イメージに分割するセグメンタとを備え、前記マスクは前景イメージと背景イメージの推定圧縮を縮小するように生成され、前記推定圧縮はエネルギー分散計算を含み、
前記マスクプロセッサコンポーネントから前記マスクを受け取り、
前記マスク内の接続コンポーネントを判別し、類似の接続コンポーネントを少なくとも１つのスクリーニング特性を使用するクラスタとしてグループにまとめるクラスタ化コンポーネントをさらに備え、
前記クラスタ化コンポーネントから前記マスクを受け取り、前記マスクからレイアウト情報を識別するレイアウトコンポーネントをさらに備え、
前記レイアウトコンポーネントから前記マスクを受け取り、前記マスクをマスクビットストリームにエンコードするマスクエンコーダをさらに備え、
前記セグメンタは偽境界について前記マスクおよび前記文書イメージを分析し、前記偽境界をまたぐいくつかのピクセル分だけ前景マスクおよび背景マスクを拡大する画像修正コンポーネントであって、前記前景マスクおよび前記背景マスクは前記マスクに基づいており、前記前景マスクは前記前景イメージを取得するために前記セグメンタによって使用され、前記背景マスクは前記背景イメージを取得するために前記セグメンタによって使用される画像修正コンポーネントを含み、
前記前景イメージを受け取り、前記前景イメージを前景ビットストリームにエンコードする前景エンコーダと、
前記背景イメージを受け取り、前記背景イメージを背景ビットストリームにエンコードする背景エンコーダと、
前記マスクビットストリーム、前記前景ビットストリーム、および前記背景ビットストリームを組み合わせて組合せビットストリームを生成するコンバイナコンポーネントをさらに備え、
前記クラスタ化コンポーネントから前記マスクを受け取り、前記マスク内の文字を識別する光学式文字認識コンポーネントをさらに備え、
前景ピクセルフィラーおよび背景ピクセルフィラーであって、前記前景ピクセルフィラーは前記前景イメージの注意しなくてよい領域を注意しなくてよいピクセルで埋め、前記背景ピクセルフィラーは前記背景イメージの注意しなくてよい領域を注意しなくてよいピクセルで埋める前景ピクセルフィラーおよび背景ピクセルフィラーをさらに備えることを特徴とする文書システム。
【請求項２】
前記マスクプロセッサコンポーネントは前記マスクからディザリングを識別して除去するディザ検出コンポーネントを備えることを特徴とする請求項１に記載の文書システム。
【請求項３】
前記マスクプロセッサコンポーネントは、前記マスクからノイズを識別して除去するノイズ除去コンポーネントをさらに備えることを特徴とする請求項１に記載の文書システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般に、文書イメージ処理（ｄｏｃｕｍｅｎｔ  ｉｍａｇｅ  ｐｒｏｃｅｓｓｉｎｇ）に関するものであり、特に、文書イメージを識別し圧縮するシステムと方法に関する。
【０００２】
【従来の技術】
コンピュータネットワーク、インターネット、およびデジタル式記憶手段の普及に伴ない、コンピュータを介して入手できる情報量が飛躍的に増大している。この情報量の増大に伴ない、情報を高速で伝送し、かつ情報を効率的に格納することが必要になってきている。情報を効果的に伝送し、かつ格納しやすくする技術の１つがデータ圧縮である。
【０００３】
データ圧縮を利用すると情報を表すために必要な領域を減らすことができ、またデータ圧縮はさまざまな種類の情報に使用できる。イメージ、テキスト、オーディオ、およびビデオを含む、デジタル情報の圧縮技術に対する要求がますます高まってきている。通常、データ圧縮は標準のコンピュータシステムで使用されているが、デジタル衛星テレビや携帯／デジタル電話などの他の技術でもデータ圧縮を利用している。
【０００４】
大量の情報を取り扱い、送信し、処理することに対する要求が高まり、このようなデータの圧縮に対する要求も高まっている。ストレージデバイスの容量は著しく増加したとはいえ、情報に対する要求は容量増大のペースを凌いでいる。たとえば、未圧縮のイメージだと５メガバイトの領域を必要とするところ、たとえば、可逆圧縮で圧縮すると２．５メガバイトの領域で済み、非可逆圧縮で圧縮すると５００キロバイトの領域で済む。したがって、データ圧縮を用いれば、より多くの情報を転送することができる。ブロードバンド、ＤＳＬ、ケーブルモデムインターネットなど、いくら伝送速度が向上しても、情報が未圧縮だとたちまち伝送限界に達してしまう。たとえば、ＤＳＬ回線で未圧縮のイメージを送信すると１０分かかる。しかし、同じ画像を圧縮すれば１分ほどで送信することができ、データ効率の面では１０倍の利得が得られる。
【０００５】
一般に、圧縮には可逆と非可逆の２種類がある。可逆圧縮では、圧縮した後オリジナルデータを正確に復元することができるが、非可逆圧縮では、圧縮後復元したデータはオリジナルデータと異なることがある。非可逆圧縮はある程度データ完全性の損なわれることが許容されるため可逆圧縮に比べて圧縮比が高いという点でこの２つの圧縮モードにはトレードオフの関係がある。たとえば、データを正確に再構成できないとテキストの品質および可読性がひどく影響を受ける可能性があるため重要なテキストを圧縮する場合には可逆圧縮が使用される。非可逆圧縮は、ある程度のひずみやノイズが許容できるか、または人間の感覚では感知できないイメージや重要でないテキストで使用することができる。データ圧縮は、特に、文書のデジタル表現（デジタル文書）に適用することができる。通常、デジタル文書としては、テキスト、イメージ、および／またはテキストとイメージがある。現在のデジタルデータに対する記憶領域が少なくて済むだけでなく、品質の著しい劣化を起こさずにコンパクトに格納できると、文書の現在のハードコピーのデジタル化が促進され、ペーパーレスオフィスの実現可能性がより高くなる。ペーパーレスオフィスを実現すると情報に簡単にアクセスすることができる、環境コストを低減できる、格納コストを低減できるなどのメリットがあるため、このようなペーパーレスオフィスへの努力は多くの企業の目標となっている。さらに、圧縮によりデジタル文書のファイルサイズを縮小すると、インターネット帯域幅をより効率的に活用することができ、より多くの情報をより高速に伝送し、ネットワーク輻輳を緩和することができる。情報に必要な記憶領域の低減、効率的なペーパーレスオフィスへの移行、インターネット帯域幅の効率の向上は、圧縮技術と関連する多くの著しい利点のうちの一部にすぎない。
【０００６】
【発明が解決しようとする課題】
デジタル文書の圧縮は、デジタル文書の利用をより魅力的なものとするために、一定の目標を達成できなければならない。まず、大量の情報を短時間のうちに圧縮、伸張ができなければならない。第２に、圧縮してもデジタル文書を正確に再現できなければならない。さらに、デジタル文書のデータ圧縮では、文書の意図した目的または最終利用を活かさなければならない。ハードコピーのファイリングやハードコピーの提出にデジタル文書が使用される。また改訂や編集を行う文書もある。多くの従来のデータ圧縮方法では、表示したときのテキストおよび／またはイメージのリフロー (re-flow) を処理できず、また圧縮技術を使って文字を認識し、それをワードプロセッサ、パーソナルデジタルアシスタント（ＰＤＡ）、携帯電話などにリフローできる効率的かつ効果的な手段を提供できない。たがって、ハードコピーのオフィス文書をスキャンしてデジタル形式に変換する場合、現在の圧縮技術では、デジタル化された文書を更新したり、訂正したり、あるいは一般に変更したりすることは不可能でないにしても困難である。
【０００７】
多くの場合、圧縮方式は、圧縮率を高めるために、２値、非２値、テキスト、またはイメージなどの文書の特定の種類に合わせて適合されている。しかし、ある種の文書に合わせて適合された圧縮方式は通常、他の種類の文書では効率的ではない。たとえば、テキストベースの文書に合わせて適合された圧縮方式は一般に、イメージ文書に対しては効率が良くない。この問題に対する解決策の１つに、エンコードする文書またはイメージの種類に合わせて改造した圧縮方式を選択するようにする方法がある。しかし、この解決方法では、単一の文書内に複数の種類の情報が含まれるデジタル文書ではうまくいかない。たとえば、雑誌の記事によく見られるような、テキスト情報とともにハイカラーイメージ（ｈｉ−ｃｏｌｏｒ  ｉｍａｇｅ）が含まれるデジタル文書の場合である。このような不具合に対処する１つの方法に、文書を分析して、複数の領域に分割するという方法がある。さまざまな領域を分析し、それらの領域内に含まれる情報の種類を判別することができる。情報の種類に基づいてそれぞれの領域に対して圧縮方式を選択することができる。しかし、この方式は実装するのが極めて困難であり、さまざまなサイズおよび形状の領域が必要で、圧縮が困難である。他の方式として、文書を背景と一定色イメージ（ｃｏｎｓｔａｎｔ  ｃｏｌｏｒ  ｉｍａｇｅ）とに分ける方法がある。これは、背景と一定色イメージに対して異なる圧縮方式を使用できるため都合がよい。しかし、一定色イメージだと、ピクセル値を強制的に一定色にすることにより情報が失われることがある。
【０００８】
さらに、デジタル文書のデータ圧縮では、文書の意図した目的を活かさなければならない。ハードコピーのファイリングやハードコピーの提出にデジタル文書が使用される。また改訂および編集を行う文書があるかもしれない。現在のデータ圧縮では、表示したときのテキストおよび／またはイメージのリフローを処理できず、また圧縮技術を使って文字を認識し、それをワードプロセッサ、パーソナルデジタルアシスタント（ＰＤＡ）、携帯電話などにリフローできる効率的かつ効果的な手段を提供できない。たがって、ハードコピーのオフィス文書をスキャンしてデジタル形式に変換する場合、現在の圧縮技術では、デジタル化された文書を更新したり、訂正したり、あるいは一般に変更したりすることは不可能でないにしても困難である。
【０００９】
【課題を解決するための手段】
本発明のいくつかの態様の基本的な内容を理解できるように、本発明の概要を簡単に述べる。この概要は、本発明の鍵となる要素や決定的な要素を示したり、本発明の範囲を定めることを意図していない。後で提示する詳細な説明の前置きとして本発明のいくつかの概念を簡単に示すことのみを目的とする。
【００１０】
本発明は、一般に、文書イメージのエンコード（ｅｎｃｏｄｉｎｇ）およびデコード（ｄｅｃｏｄｉｎｇ）を行うシステムおよび方法に関する。文書イメージは、複数のレイヤが非２値で表される場合にマスクに従って複数のレイヤに分割される。次に、それぞれのレイヤを処理して、別々に圧縮することにより、文書イメージ全体の圧縮率を高めることができる。
【００１１】
本発明の一態様によれば、マスクは文書イメージから生成される。マスクを生成するのは、文書イメージのマスクおよび複数のレイヤを組み合わせた場合のサイズに対する圧縮推定値を引き下げるためである。その後マスクを使用して文書イメージを複数のレイヤに分割する。このマスクにより、文書イメージのピクセルを決定するか、またはそれぞれのレイヤに割り当てる。マスクおよび複数のレイヤを処理して、別々にエンコードし、文書イメージ全体の圧縮率を高め、圧縮速度を改善する。複数のレイヤは非２値イメージであり、たとえば前景イメージと背景イメージとを備える。
【００１２】
本発明の他の態様によれば、文書イメージは複数のレイヤに分割され、それら複数のレイヤは前景イメージ、背景イメージ、およびマスクを含む。マスクは２値イメージであり、文書イメージを前景イメージと背景イメージに分割するために使用する。一般に、マスクを生成するのは、マスク、前景イメージ、および背景イメージを組み合わせた場合のサイズに対する推定値を引き下げるためである。レイヤを単色に制限するいくつかの従来のシステムとは異なり、前景イメージおよび背景イメージの両方において、適当な範囲の色を使用することができ、単色または一定色に制限されない。マスク、前景イメージ、および背景イメージの追加的な処理を実行できる。マスク、前景イメージ、および背景イメージをエンコードし、組み合わせて単一のビットストリームにする。エンコードには、適当な圧縮方式をいくつでも使用できる。デコードの場合、圧縮されたビットストリームをマスクビットストリーム、前景ビットストリーム、および背景ビットストリームに分割する。マスクビットストリーム、前景ビットストリーム、および背景ビットストリームをマスク、前景イメージ、および背景イメージにデコードする。マスク、前景イメージ、および背景イメージに対する追加的な処理を実行できる。マスクに従って前景イメージおよび背景イメージを組み合わせて再結合文書イメージにする。
【００１３】
本発明のさらに他の態様によれば、マスクセパレータ（ｍａｓｋ  ｓｅｐａｒａｔｏｒ）は文書イメージを受け取り、その文書イメージからマスクを生成する。マスクは２値形式で表される。前景背景セグメンタ（ｆｏｒｅｇｒｏｕｎｄ  ｂａｃｋｇｒｏｕｎｄ  ｓｅｇｍｅｎｔｅｒ）は、マスクおよび文書イメージを受け取り、その文書イメージを前景イメージおよび背景イメージに分割する。マスクエンコーダ（ｍａｓｋ  ｅｎｃｏｄｅｒ）は、マスクをマスクビットストリームにエンコードする。前景エンコーダは、前景イメージを前景ビットストリームにエンコードする。背景エンコーダは、背景を背景ビットストリームにエンコードする。コンバイナコンポーネント（ｃｏｍｂｉｎｅｒ  ｃｏｍｐｏｎｅｎｔ）は、マスクビットストリーム、前景ビットストリーム、および背景ビットストリームを組み合わせて組合せビットストリームを生成する。
【００１４】
前記の目的および関連する目的を達成するために、以下の説明および付属の図面に関して、本発明のいくつかの例示の態様を本明細書で説明する。これらの態様は、本発明を実施するさまざまな方法を示しており、すべて本発明の対象となるものである。本発明の他の利点および新規性のある特徴は、図面とともに本発明の以下の詳細な説明を読むと明らかになるであろう。
【００１５】
【発明の実施の形態】
全体を通して同様の参照番号が同様の要素を参照するために使用されている図面を参照しながら、本発明について説明する。以下の説明では、説明のため本発明を完全に理解できるように多数の特定の詳細を定めている。ただし、こうした具体的内容がなくても本発明を実践できることは明白であろう。他の例では、よく知られている構造およびデバイスはブロック図の形式で示されており、本発明を説明しやすくしている。
【００１６】
本願で使用されているように、「コンポーネント」という用語は、コンピュータ関連の実体（エンティティ）、ハードウェア、ハードウェアとソフトウェアとの組合せ、ソフトウェア、または実行中のソフトウェアのいずれかを指すものとする。たとえば、コンポーネントとして、プロセッサ上で実行されているプロセス、プロセッサ、オブジェクト、実行可能ファイル（ｅｘｅｃｕｔａｂｌｅ）、実行（ｅｘｅｃｕｔｉｏｎ）のスレッド、プログラム、およびコンピュータを挙げることができる。説明のために、サーバ上で実行されているアプリケーションおよびサーバを両方ともコンポーネントとする。１つまたは複数のコンポーネントを１つのプロセッサおよび／または実行のスレッド内に常駐させることができ、またコンポーネントを１台のコンピュータにローカルとして配置し、かつ／または２台またはそれ以上のコンピュータ間に分散させることができる。
【００１７】
さらに、「文書イメージ」は、単色または複数の色を含む文書のデジタル表現を指すものとする（たとえば、２値（白黒）、階調、および／またはカラー文書）。さらに、文書イメージは、イメージ、テキストおよび／またはイメージを含むテキストで構成することができ、場合によってはテキストとイメージとを重ね合わせることもできる。文書イメージは、２値、ＲＧＢ、ＹＵＶ、および／またはその他の文書表現を含むことができる。ＲＧＢ文書イメージは、赤、緑、および青の成分で表される。ＹＵＶ文書イメージは、Ｙで示されるルミネセンス成分とＵおよびＶで示されるクロミナンス成分を使用して表される。ＹＵＶ表現は、一般に、圧縮に適しているが、それは人間の目がＵとＶの歪みに余り敏感に反応せず、したがってＵおよびＶは１／２でサブサンプリング（ｓｕｂｓａｍｐｌｅ）することができ、またＹでＲ、Ｇ、Ｂの相関が得られるからである。テキストのクラスタ化のためには、Ｙ表現は特に興味深いが、それは、テキストが輝度の変化から生じたときにかなり読み取りやすいからである。所与の輝度に対するクロミナンスの変化（たとえば赤から緑）から生じるテキストは所定の輝度においてかなり読みにくい。したがって、カラー文書は、ＹＵＶ文書に変換し、その後、テキスト情報をそれほど失うことなく２値化することができる。文書イメージは、一般に「ピクセル」と呼ばれる画像要素を含む。文書イメージは、任意の形状またはサイズの単一文書または複数ページ文書に基づく。
【００１８】
図１は、本発明の一態様による分割されたレイヤ化イメージエンコードシステム１００を示す高水準ブロック図である。システム１００は、テキスト、手書き、図面などを識別して圧縮し、任意の適当な形状またはサイズの単一文書または複数ページ文書を操作することができる。システム１００は、マスクセパレータ１０２、前景背景セグメンタ１０４、マスクエンコーダ１０６、前景エンコーダ１０８、背景エンコーダ１１０、および組合せコンポーネント１１２を含む。マスクセパレータ１０２は、文書イメージ（たとえば、文書のデジタル表現）を受け取って、マスクを生成する。文書イメージには、１つまたは複素のページを入れることができ、通常は、文書からスキャンされる。文書イメージは、任意の解像度を設定でき、これは一般にドット／インチ（ｄｐｉ）で表される。たとえば、ＦＡＸ送信文書は通常、１５０〜２００ｄｐｉ程度の解像度を使用する。さらに、文書イメージは、実質的にどのようなピクセルサイズまたは文書サイズでも設定でき、たとえば、６４０×４８０ピクセルやＡ４サイズを設定できる。
【００１９】
マスクセパレータ１０２によって生成されるマスクを使用して、文書イメージを２つのレイヤ、前景イメージと背景イメージに分割することができる。本発明の他の態様ではイメージを２つよりも多いレイヤに分割できることは理解されるであろう。マスクは、マスクイメージとも呼ばれ、２値イメージであり、ピクセル値によってそれぞれのピクセルが前景イメージに属するのか、それとも背景イメージに属するのかを判別する。マスクセパレータ１０２によって、前景イメージと背景イメージを組み合わせたサイズが小さくなるようにマスクが生成される。この概念を複数のマスクと複数の前景に拡張し、それでも本発明に従うことができることは理解されるであろう。
【００２０】
マスクを生成するのにさまざまな方式を使用できる。圧縮の場合、同等のピクセル値は異なるピクセル値よりも圧縮率がよい。たとえば、青空の領域は色と強度が変化する領域よりも圧縮率がよい。上述のように、マスクを生成するのは、マスク、前景イメージ、および背景イメージを組み合わせた場合のサイズを引き下げるためである。
【００２１】
使用できる方法の１つに、考えられるマスクのスーパーセットを生成し、そのスーパーセットの最良のマスクを選択する方法がある。ピクセルをＮ個含む文書イメージの場合、可能なマスクは２Ｎ個ある。したがって、可能なすべてのマスクを分析して、どのマスクで組み合わせた全体が最小になるイメージを生成するかを判別することができる。しかし、可能なすべてのマスクを分析することは高い計算能力を必要とし、時間もかかるため、一般的には実用的でない。
【００２２】
他の方法として、文書を複数の領域に細分し、それぞれの領域を分析してピクセルを割り当て、少なくとも一部はエネルギー（たとえば、エネルギー分散 (variance) ）に基づいて領域をマージする方法がある。エネルギー分散（得られる圧縮率の推定）は距離の平方和に基づく測定である。文書の小さな領域、たとえば２×２ピクセルまたは４×４ピクセルをエネルギー分散に関して分析することができる。この小さな領域を前景領域と背景領域に分割し、その小さな領域のエネルギー分散が低減または最小化されるようにできる。可能なすべてのマスクを使用して、使用するマスクを決定できるが、それは、分析された領域がこのような分析を実現可能なものにできる十分な小ささであるからである。たとえば、４ピクセルの領域については、その領域に対してマスクの１６の可能な順列しかない。その小さな領域（たとえば、ペアにして）マージしてまとめ、マスクを生成できるが、それは全体として、マスク、前景イメージ、および背景イメージの組み合わせたサイズを低減する。
【００２３】
前景背景セグメンタ１０４は、マスクセパレータ１０２と文書イメージからマスクを受け取る。前景背景セグメンタ１０４は、マスクを使用して文書イメージを前景イメージと背景イメージに分割する。文書イメージのピクセル毎に、そのマスクの対応するピクセルが参照される。ピクセルは、そのマスクの対応するピクセルに基づき前景イメージまたは背景イメージに割り当てられる。たとえば、マスクの対応するピクセルが「１」であれば、そのピクセルは前景イメージに割り当てられる。逆に、マスクの対応するピクセルが「０」であれば、そのピクセルは背景イメージに割り当てられる。しかし、「０」または「１」が前景を示すのか背景を示すのかは、ユーザー側で定義できることは理解されるであろう（たとえば、「１」は背景に割り当てられ、「０」は前景に割り当てられる）。
【００２４】
さらに、前景イメージおよび背景イメージは互いに交わらない。しかし、マスクの追加的な処理を実行することで、時々重なり合う場合もある異なる前景マスクおよび背景マスクを生成し、マスク境界に沿った結果を低減するか、またはいくつかのピクセルを完全に無視し、圧縮率を高めることができる。次に、前景マスクを使用して、前景イメージを文書イメージから分割し、背景マスクを使用して文書イメージから背景イメージを分割する。この場合、前景イメージと背景イメージは互いに素ではなく、わずかに重なり合い、このような重なり合いのため圧縮率が低下するが、エッジ効果は下がる。前景マスクおよび背景マスクを採用して文書イメージをセグメント分割しても、前景マスクおよび背景マスクは文書イメージの分割後には必要ない。
【００２５】
背景イメージと前景イメージには、ピクセルが他方のイメージに割り当てられた穴または空の領域がある。これらの空の領域は、注意しなくてよい（ｄｏｎ’ｔ  ｃａｒｅ）ピクセルということもできる。それと対照的に、空でない領域は、注意する（ｃａｒｅ）ピクセルということができる。空の領域は、前景と背景のイメージの全体的な圧縮サイズが小さくなるように適当な方法で処理することができる。これらの空の領域を注意しなくてよいピクセル値で塗りつぶすという方法がある。注意しなくてよいピクセル値は、圧縮率を高め、それによりイメージのサイズが小さくなるように選択される。たとえば、背景イメージの例は白色であるが、テキストが配置されているところに注意しなくてよいピクセルが設定されている。この例の、この注意しなくてよいピクセルを白で塗りつぶして、圧縮率を高めることができる。別の方法では、空の領域を塗りつぶさず、たとえばマスクウェーブレット圧縮（ｍａｓｋｅｄ  ｗａｖｅｌｅｔ  ｃｏｍｐｒｅｓｓｉｏｎ）など空の領域を利用する圧縮方式を使用する。本発明によればそれ以外の方法も使用できる。
【００２６】
前景イメージおよび背景イメージに追加的な処理を実行することもできる。背景イメージおよび前景イメージを低解像度に下げて、それぞれの圧縮サイズを小さくすることができる。たとえば、背景イメージと前景イメージを３００ｄｐｉから１００ｄｐｉに引き下げることができる。また、一定色接続コンポーネント（ｃｏｎｓｔａｎｔ  ｃｏｌｏｒ  ｃｏｎｎｅｃｔｅｄ  ｃｏｍｐｏｎｅｎｔｓ）を背景イメージと前景イメージ内で識別することもできる。一定色接続コンポーネントは、実質的に色値が同じである複数の接続ピクセルである。一定色接続コンポーネントは、シードピクセル（ｓｅｅｄ  ｐｉｘｅｌ）を配置し、それに接続されている実質的に同じ色ピクセルを決定するアルゴリズムを利用することにより識別することができる。一定色接続コンポーネントに最小数のピクセルが含まれるようにしきい値または最小ピクセルを設定できる。識別された一定色接続コンポーネントで文書イメージの圧縮率を高めることができる。
【００２７】
マスクエンコーダ１０６は、マスクセパレータ１０２からマスクを受け取り、そのマスクをエンコードして、圧縮されたビットまたはビットの圧縮されたマスクストリームをマスクから生成する。マスクエンコーダ１０６には適当な圧縮方式を使用できる。マスクは２値形式であり、通常はテキスト情報を含む。２値形式とテキスト情報も圧縮する圧縮方式を選択しなければならない。２レベル圧縮方式を使用してマスクをエンコードすることもできる。
【００２８】
マスクをエンコードするのに使用できる圧縮方式としてＣＣＩＴＴ（国際電信電話諮問委員会）方式がある。ＣＣＩＴＴは、現在ＩＴＵ−Ｔ国際電気通信連合−通信部門（１９９４年に名称変更）と呼ばれる規格制定機関であり、ＦＡＸ／モデム通信のための可逆圧縮技術の名称になっている。この種の圧縮は、２値イメージでうまく働く。標準的な圧縮比は、旧バージョンのＶ．４２ｂｉｓでは、４：１、新しいバージョンのＶ．４４  ２０００では６：１で、これはＬｅｍｐｅｌ−Ｚｉｖ−Ｊｅｆｆ−Ｈｅａｔｈ（ＬＺＪＨ）圧縮アルゴリズムに基づいている。本発明により他の適当な圧縮方法または方式を使用してマスクをエンコードすることができることは理解されるであろう。
【００２９】
前景エンコーダ１０８は、前景背景セグメンタ１０４から前景イメージを受け取り、その前景イメージを前景ビットストリームにエンコードする。背景エンコーダ１１０は、前景背景セグメンタ１０４から背景イメージを受け取り、その背景イメージを背景ビットストリームにエンコードする。前景エンコーダ１０８と背景エンコーダ１１０には適当な圧縮方式を使用できる。たとえば、プログレッシブ波長符号化（ＰＷＣ）（ｐｒｏｇｒｅｓｓｉｖｅ  ｗａｖｅｌｅｎｇｔｈ  ｅｎｃｏｄｉｎｇ）、プログレッシブトランスフォームコーディング（ＰＴＣ）（ｐｒｏｇｒｅｓｓｉｖｅ  ｔｒａｎｓｆｏｒｍ  ｃｏｄｉｎｇ）、ＪＰＥＧ、ＪＰＥＧ  ２０００、およびマスクウェーブレット圧縮方式（ｍａｓｋｅｄ  ｗａｖｅｌｅｔ  ｃｏｍｐｒｅｓｓｉｏｎ  ｓｃｈｅｍｅｓ）を使用して前景イメージまたは背景領域をエンコードすることができる。一部の圧縮方式（たとえば、マスクウェーブレット）では、前景エンコーダ１０８および背景エンコーダ１１０は前景イメージおよび背景イメージをエンコードするためにマスクを必要とすることがある。
【００３０】
コンバイナ（ｃｏｍｂｉｎｅｒ）コンポーネント１１２は、マスクエンコーダ１０６、前景エンコーダ１０８、および背景エンコーダ１１０から圧縮されたビット列を受け取り、それらのビットを出力ストリームまたは出力ファイルにまとめる。コンバイナコンポーネント１１２は、エンコーディングの種類、辞書、およびデコーダによって文書イメージを再構成するために使用できるものなどの情報を識別または提供するヘッダ情報を出力ファイルに書き込む。
【００３１】
説明のため、エンコーディングシステムを上述のさまざまなコンポーネントを介してイメージ全体を一度に処理するものとして説明した。しかし、重なり合うスキャン領域を使用してメモリの使用量を減らせることは理解されるであろう。たとえば、このシステムでは、文書イメージの５１２ラインからなる第１の帯状領域（ｓｔｒｉｐ）を処理することができる。次に、重なり合う量、たとえば１０ラインだけ第１の帯状領域と重なり合う第２の帯状領域がシステムによって処理される。文書イメージ全体が処理されるまでそれ以降の帯状領域を処理するため、この重なり合う量により帯状領域の間の変動が緩和される。
【００３２】
上述のように、前景イメージおよび背景イメージは空の領域つまり注意しなくてよい領域を持つ。空の領域はさまざまな方法で取り扱うことができる。１つの方法では、空の領域にデータを書き込み、普通の圧縮手法を用いる。イメージの空の領域を埋める単純なプロセスでは、それらの空の領域にそのイメージに対する平均ピクセル値を書き込む。しかし、このプロセスではマスク境界のところに急激な不連続が生じることがあり、与えられたピーク信号対雑音比（ＰＳＮＲ）に対する必要なビットレートが高まり、マスクまたは空の領域の境界の付近に顕著なリンギングが発生する場合がある。他のプロセスでは、それぞれのピクセルに最も近い非マスク（または注意する領域）ピクセルの色をつける。標準の形態論アルゴリズム（ｍｏｒｐｈｏｌｏｇｙ  ａｌｇｏｒｉｔｈｍ）を使用すると、すべてのピクセルにわたり２パス（ｐａｓｓ）のみでプロセスを実行することができ、マスクの下にボロノイ充填空領域（Ｖｏｒｏｎｏｉ−ｆｉｌｌｅｄ  ｖａｃａｎｔ  ｒｅｇｉｏｎｓ）が生じる。次に、前景イメージまたは背景イメージを再構成したら、再構成されたイメージにローパス（ｌｏｗ−ｐａｓｓｅｄ）を実行し、既知のピクセルをその正しい値に復元する。ローパスフィルタの遮断周波数が低すぎる場合、鋭いエッジが発生し、境界の付近に必要なビットレートが高くなり、顕著なリンギングが増える。
【００３３】
空領域を扱う他の方法として、凸集合への射影を使用する方法がある。たとえば、２つの凸集合、つまり、表示ピクセル上の入力と一致するイメージの集合と０に設定されたある種のウェーブレット係数を持つイメージの集合とを考察する（たとえば、特定の解像度レベルを超える全ての高周波係数）。２つの集合への射影を交互に切り替えることにより、表示ピクセルと一致し、０のウェーブレット係数が多数あることから圧縮率の高いイメージを見つけることができる。
【００３４】
空領域を扱うさらに他の方法では、前景エンコーダ１０８および不規則なグリッドに対して明示的に設計された背景エンコーダ１１０にウェーブレット変換を使用する。このようなウェーブレット分解は、コンピュータビジョンおよびたとえばコンピュータグラフィックスにおける幾何データの圧縮とともに使用される。このようなウェーブレットは、マスクの不規則パターンに適合される。
【００３５】
採用できるウェーブレット変換圧縮方式は、マスクウェーブレット変換である。マスクウェーブレット変換は、ウェーブレット関数がマスクの変化に応じてケースバイケースで変化する前景エンコーダ１０８および背景エンコーダ１１０に使用できる。図１には示されていないが、マスクウェーブレット変換圧縮方式を使用するためにマスクが前景エンコーダ１０８と背景エンコーダに供給されることは理解されるであろう。たとえば、通常の従来のウェーブレット関数では予測にｋ個の値を使用することができる。しかし、マスクと空領域の場合、通常のウェーブレット関数は値が含まれないピクセルを処理することはできない（たとえば、注意しなくてよい領域または空領域内の注意しなくてよいピクセル）。それと対照的に、変更可能なウェーブレット関数では前景イメージおよび背景イメージの使用可能な値または表示領域のみを使用する。したがって、マスクウェーブレット変換では空領域を注意しなくてよいピクセルで埋める必要はない。
【００３６】
図２は、「リフティング（ｌｉｆｔｉｎｇ）」を使用したウェーブレットの従来の一計算ステップの図である。この図は、三次ウェーブレット（ｃｕｂｉｃ  ｗａｖｅｌｅｔ）に関して、位置３の予測ステップと、位置６の対応する更新ステップを示している（分かりやすくするため図では他の位置を省略している）。それぞれの矢印の隣にある係数は、各ステップを実行するために一次結合を計算する方法を示している。たとえば、位置３の「詳細」値（ハイパスフィルタから得られる）は、以下の式を計算して求められる。
ｄ３＝ｓ３−（−ｓ０＋９ｓ２＋９ｓ４−ｓ６）／１６                式１
【００３７】
更新ステップは、以下の式で計算される。
ｓ６＝ｄ６＋（−ｄ３＋９ｄ５＋９ｄ７−ｄ９）／３２                式２
【００３８】
図３は、いくつかのピクセル値が欠損している場合に生じる問題を示している。図では、位置１、２、５、８、９に対する値は用意されていない。明らかに、結果が欠損値に依存するため従来の三次ウェーブレットの計算はうまく実行されない。欠損値を何らかの定数（０またはイメージ全体にわたってとった平均値）に設定すると鋭い不連続性が入り込み、これが圧縮率の低下や望ましくない効果の発生につながる。それとは対照的に、マスクウェーブレット圧縮方式では、ウェーブレット関数はマスクに応じてケースバイケースで変更される。たとえば、リフティングの予測ステップで、ｋ個の値を予測に使用できる場合、次数ｋ−１の多項式を補間に使用する。値を３つしか使用できない場合、三次多項式ではなく二次多項式を使用する。値を１つしか使用できない場合は、定数多項式を使用し、ウェーブレットをＨａａｒウェーブレットとする。信号が次数Ｋ−１の多項式で、ｋ個のピクセルがマスクされていない場合、予測は完全に正確である。
【００３９】
マスクウェーブレット変換の圧縮方式では、偶数位置にある係数から奇数位置にあるすべての係数に対する予測の計算を利用する。奇数係数とその予測との差がウェーブレット係数であり、これは奇数位置にいくつかの０があるハイパスフィルタとみなすことができる。信号ｓがある位置を中心に置かれ、それに応じてインデックスが作成される。説明を簡単にするため、図４に示されているような７タップフィルタに関してこの方式を説明する。図４は、ｓ０がｓ−３、ｓ−１、ｓ１、ｓ３の関数として予測されるリフティングステップを示しており、残渣ｄが計算される。
【００４０】
標準の行列表記に従ってフィルタａには０からｉまでのインデックスがつけられる。ウェーブレット係数ｄは以下の式によって与えられる。
【００４１】
【数１】
0004773678.tif 000002
【００４２】
ただし，ｋはフィルタ内のタップの個数である（この場合ｋ＝７）。ハイパスフィルタのモーメントＭは以下のように書くことができる（ｓｉ＝ｉｎに設定）。
【００４３】
【数２】
0004773678.tif 000003
【００４４】
通常の信号はｊ次の低次多項式（Ｔａｙｌｏｒ展開）を使用して近似し、ａを最初のｊ＋１モーメントが０に設定されるように選択する。すると、ウェーブレット変換は多数の０点を持ち、圧縮率が高くなる。そこで、ｋ＝７であれば、ａは自由度４で、最初の４つのモーメントは０に設定される。これらの結果は以下の系で検証される。
【００４５】
【数３】
0004773678.tif 000004
【００４６】
これは、ｗａ＝ｃと行列表記で書くことができる。この方程式系の解は、よく知られている三次ウェーブレットａ＝［１／１６，−９／１６，−９／１６，１／１６］で使用されている係数である。
【００４７】
この方程式系は、図１に示されているマスクなど、マスクが存在している場合に一般化される。つまり、係数ｓ２ｉ−ｋ／２のうちいくつかが欠損しており、これは行列ｍを導入することによりモデル化することができる。
【００４８】
【数４】
0004773678.tif 000005
【００４９】
ただし、ｗｍａ＝ｃとなるようなｍｉ∈｛０，１｝である。ｍには、式５の方程式内の列を取り除くという効果がある。しかし残念なことにこの方程式系では、ｍｉ＝０の場合には劣決定方程式系であり、そうでない場合には優決定方程式系である。その理由は、表示ピクセルに対応するａｉに課される消えるモーメントの制約が多すぎるからである。これは、ｍｉ≠０となるようなｊ個の係数がある場合に最初のｊ個のモーメントを０にしなければならないという条件を課すことにより解決できる。これは、図５の方程式系の最初のｊ個の式のみを保持することに対応する。劣決定方程式系の係数ａｉ（ａｉにｍｉ＝０を掛けた場合）では、任意の制約条件ａｉ＝０が追加され、このようなことは単一の方程式系で実行できる。
（ｐｗｍ＋ｍ−Ｉ）ａ＝ｐｃ                                        式７
ただし、Ｉは単位行列であり、
【００５０】
【数５】
0004773678.tif 000006
【００５１】
ここで
ｐｉ＝（ｔｒ（ｍ）＞ｉ）？１：０                                  式９
ｐｉに対する制約条件により、式５の方程式系内の行がｍ内の０係数毎に式５の方程式系の最下段の係数から取り除かれる。つまり、０に等しくないｊ個の係数ｍｉがある場合、ｉ＝［０．．ｊ−１］に対してｐｉ＝１、それ以外のときｐｉ＝０である。システムは常にｍｉ∈｛０，１｝の値に対して一意的な解を持つことが容易に検証できる。ｍの可能なすべての値に対するａについての解は、方程式系の式９によって与えられ、以下の表１の三次ウェーブレットについてこれをまとめたが、システムの次元が４の場合にｍの異なる値に対する式９の解を示している。
【００５２】
【表１】
0004773678.tif 000007
【００５３】
次に、信号ｓを上からの予測値で更新する。更新ステップでは、信号に（−１）ｉを掛けた後にローパスフィルタの最初のモーメントが消えることが望ましい。つまり、通常の信号（たとえば、低次多項式として書くことができる）に最高周波数信号（−１）ｉを掛けた場合、ローパスフィルタは０を出力しなければならない。この条件は、前のセクションでのように０モーメント制約として容易にキャストすることができるが、ただし入力はｓｉ＝ｉｎではなくｓｉ＝（−１）ｉｉｎの形式となる。予測ステップと類似の表記を使用すると、更新ステップは次の式に対応する。
【００５４】
【数６】
0004773678.tif 000008
【００５５】
ただし，ｋはフィルタ内のタップの個数である（この場合ｋ＝７）。ローパスフィルタのモーメントは以下のように書くことができる。
【００５６】
【数７】
0004773678.tif 000009
【００５７】
しかし、各ｄｉについて、式は局所的に次のように書き直すことができる（ｓｉ＝（−１）ｉｉｎ）。
【００５８】
【数８】
0004773678.tif 000010
【００５９】
これはｊとｋ／２が奇数だからである。個々のａｉは０モーメントを生成するように設定されるため、以下の式が成立する。
【００６０】
【数９】
0004773678.tif 000011
【００６１】
これは、ｄｊ＝−２ｊｎを意味する。
【００６２】
【数１０】
0004773678.tif 000012
【００６３】
ウェーブレットで通常の信号も圧縮するには、できる限り多くのモーメントをできる限り０に等しくしなければならない。自由度は４なので、最初の４つのモーメントを０に設定できる。以下の方程式系でこの結果を検証することは容易である。
【００６４】
【数１１】
0004773678.tif 000013
【００６５】
これは、ｗｂ＝ｃ’と行列表記で書くことができる。この方程式系の解は、よく知られている三次ウェーブレットｂ＝［−１／３２，９／３２，９／３２，−１／３２］で使用されている係数である。
【００６６】
そこで、係数ｓｉのうちいくつかが欠損していると仮定する。最初に、すべての欠損値が偶数の位置にのみあると仮定する。この方程式系は、前と同様にして解いて以下を検証することができる。
（ｐｗｍ＋ｍ−Ｉ）ｂ＝ｐｃ’                                    式１６
ｍとｐ行列は、ｓ０内を中心とする位置に依存することに留意されたい。それぞれの位置ではマスクの異なる部分が見えるため、それに対応するｍとｐがある。式１６の解は、下に示す表２で与えられ、これは、方程式系の次元が４のときの異なる値に対する式１６の解を表している。式１６を導くために、奇数の位置がマスクされていないと仮定した。いくつかの奇数位置がマスクされていて、マスクされた値の個数がｎよりも小さい場合、ｄｊ＝−２ｊｎと式１６が成立する。そうでない場合、予測ステップでマスクされたピクセルが多すぎて更新ステップでｎ番目のモーメントを無効にできない（ウェーブレット係数は小さいとしても、０ではない）。逆ウェーブレット変換は、リフティング形式主義のおかげで各ステップを局所的に逆に実行することにより容易に計算できる。
【００６７】
【表２】
0004773678.tif 000014
【００６８】
したがって、マスクされたウェーブレット変換を使用して、前景イメージおよび背景イメージをエンコードし、その際に空領域を埋める必要がない。しかし、さまざまな実装において上述のように注意しなくてよい値で空領域を充てんする他のエンコード方法または圧縮方式を使用できることは明白である。
【００６９】
図５は、本発明の一態様によるセグメント化されたレイヤ化イメージデコードシステムを示すブロック図である。システムは、圧縮されたビットストリームを受け取り、組み替えたイメージを圧縮ビットストリームから生成する。このシステムには、セパレータコンポーネント５０２、前景デコーダ５０４、背景デコーダ５０６、マスクデコーダ５０８、およびコンバイナ５１０が含まれる。
【００７０】
セパレータコンポーネント５０２は、圧縮されたビット列を受け取り、それらのビットを分離して前掲ビットストリーム、背景ビットストリーム、およびマスクビットストリームを形成する。セパレータコンポーネント５０２は、ヘッダ情報を使用してビットストリームを分離する。前景デコーダ５０４は、前景ビットストリームを伸張して、前景イメージを生成する。背景デコーダ５０６は、背景ビットストリームを伸張して、背景イメージを生成する。前景デコーダ５０４および背景デコーダ５０６はたとえば、プログレッシブ波形またはプログレッシブ変換など任意の数の伸張方式を使用できる。
【００７１】
マスクデコーダ５０８は、マスクビットストリームを伸張して、マスクまたはマスクイメージを生成する。また、マスクデコーダ５０８はレイアウトおよび／またはリフロー情報を受け取る。さらに、マスクデコーダ５０８は、テキスト情報を再構成するために使用される辞書を取得することができる。マスクデコーダ５０８は、通常、２レベル伸張方式を使用する。一部の圧縮方式（たとえば、マスクウェーブレット）では、前景デコーダ５０４および背景デコーダ５０６は前景イメージおよび背景イメージを取得するためにマスクデコーダ５０８から伸張されたマスクを必要とする場合がある。
【００７２】
コンバイナ５１０は、前景イメージ、背景イメージ、およびマスクを組み合わせて組み換え文書イメージを生成する。組み替えられたイメージは、オリジナルの文書イメージと同一であるかまたは近似的なイメージである。さらに、組み替えられたイメージは所望の表示装置に応じて形状やサイズが異なることがある。たとえば、手紙サイズの文書のスキャンはそれよりもさら小さい画面を持つ携帯型デバイスでは表示が異なることがある。コンバイナ５１０は、マスクに基づいて前景イメージおよび背景イメージから組み替えられた文書イメージのピクセルを生成する。組み替えられた文書のそれぞれのピクセルは、マスクの対応するピクセルを参照することにより決定され、それにより組み替えられた文書のピクセルの出所が前景イメージなのか背景イメージなのかを判別することができる。たとえば、マスクピクセル値１は組み替えられた文書のピクセルの出所が前景イメージの対応するピクセルであることを示す。
【００７３】
図６は本発明の一態様による文書イメージサンプルの図である。図６は、例であり本発明をさらに詳しく説明することのみを目的としている。文書イメージ６０１は、さまざまな色および／または陰影で表される。文書イメージ６０１は、テキスト情報６０２およびイメージ情報６０４および６０３と、背景６０５を含む通常の文書イメージである。図６に示されているパターンは陰影または色を示している。したがって、テキスト情報６０２は、イメージ情報６０３および６０４または背景６０５と異なる色であってよい。さらに、この情報では適当な数の色を使用できる。本発明により、図１のシステムを使用するなど、文書イメージ６０１を３つのコンポーネント、マスク６１０、前景イメージ６１１、および背景イメージ６１２に分割する。本発明の他の態様では、文書イメージを２つまたは３つ以上のレイヤに分割することができる。
【００７４】
マスク６１０は、２値イメージであり、そこで、白黒領域のみで表示される。マスク６１０は、文書イメージのピクセルが前景イメージ６１１に入るのか、背景イメージ６１２に入るのかを決定しまたは割り当てる。マスク６１０はさらに、前景イメージ６１１および背景イメージ６１２のどのピクセルが再構成された文書内に配置されるかを決定することにより再構成された文書イメージを生成するのに使用される。再構成された文書は同一であるか、または文書イメージ６０１を近似したものになっている。
【００７５】
図６から分かるように、前景イメージ６１１はマスク６１０で示されているように文書イメージ６０１の一部を含む。このマスク６１０の黒色ピクセルにより、文書イメージ６０１のピクセルが前景イメージ６１１に割り当てられる。前景イメージ６０３の他の部分を注意しなくてよいピクセル６１５で埋めることができる。上述したように、注意しなくてよいピクセル６１５は、圧縮率を高めるが、再構成されたイメージ内には存在しない。同様に、背景イメージ６１２は、マスク６１０により示されているように文書イメージ６０１の一部を含む。このマスク６１０の白色ピクセルにより、文書イメージ６０１のピクセルが背景イメージ６１２に割り当てられる。図６に示されているように、背景イメージ６０４の他の部分を注意しなくてよいピクセル６０６で埋めることができる。注意しなくてよいピクセル６０６は、圧縮のため存在しており、再構成されたイメージ内に含まれない。テキスト情報６０２のアウトラインが説明のため背景イメージ６１２内に示されている。しかし、テキスト情報６０２は、背景６０５と一致する注意しなくてよいピクセルで埋めて、テキスト情報６０２が背景イメージ６１２内で見えなくすることができることは明白である。
【００７６】
上述のように、図６は本発明による数多くのありうる文書イメージのうちの一例にすぎない。イメージの多くのバリエーションを作成でき、また本発明にそのまま基づく。
【００７７】
図７は、本発明の一態様による分割（セグメント化）されたレイヤ化イメージエンコードシステムを示すブロック図である。システムでは、テキスト、手書き、図面、文書内にあるものなどの情報を識別し、文書を圧縮することができる。システムは、適当な形状またはサイズの単一文書または複数ページ文書に作用する。
【００７８】
カラースペースコンバータ（ｃｏｌｏｒｓｐａｃｅ  ｃｏｎｖｅｒｔｅｒ）７０２は、文書イメージに作用し、文書イメージのカラースペースを変換する。カラースペースは、文書イメージ内で色を表す方法を指す。カラースペースは一般にピクセル毎に色を表示する多数のコンポーネントを有する。たとえば、イメージは、各ピクセルがＲＧＢ成分のそれぞれについて値を持つＲＧＢ（赤、緑、青）カラースペースで表すことができる。さらに、透明成分を追加して、ピクセルの透明性を示すこともできる。ピクセルの色全体は、これらの成分を組み合わせることにより得られる。たとえば、白色はＲＧＢ値２５５、２５５、２５５（１成分につき８ビットと仮定する）を使用して得ることができ、青色はＲＧＢ値０、０、２００で得ることができる。ＲＧＢカラースペースは、イメージの表示や文書のスキャンに使用されることが多い。しかし、ＲＧＢカラースペースは圧縮の妨げになることがある。
【００７９】
文書内の色は一般に、相関および／または相互関係がある。ＲＧＢカラースペースでは、各成分は個別に圧縮されるため（チャネルにより）、同じ情報が何回も符号化される。文書イメージの圧縮を改善するために、文書のカラースペースをより圧縮率の高いカラースペースに変換する。
【００８０】
実現可能なカラースペース変換の１つに、文書イメージをＲＧＢカラースペースからＹＵＶカラースペースに変換する方法がある。Ｙ、Ｕ、Ｖ成分はそれぞれ、ルミネセンス、クロミナンス赤、およびクロミナンス青の成分である。ＹＵＶはもともと、テレビ視聴用に開発されたものである。変換は、圧縮率の高さではなく表示の好みに基づいて開発された。したがって、文書イメージは、以下の式を使ってＲＧＢカラースペースからＹＵＶカラースペースに変換できる。
Ｙ＝０．６Ｇ＋０．３Ｒ＋０．１Ｂ
Ｕ＝Ｒ−Ｙ                                                      式１７
Ｖ＝Ｂ−Ｙ
【００８１】
ＹＵＶカラースペースは、ＲＧＢカラースペースに比べて圧縮率が優れているが、それは、成分間の相関を利用しており、同じ情報が何回も符号化されないからである。相関情報のほとんどは、Ｙ成分に含まれている。式１７は、ＹＵＶ成分が対応するＲＧＢ成分よりも小さな値で表されることを示している。しかし、上述のように、ＹＵＶカラースペースは圧縮率を高めるために設計されたわけではなく、表示性を高めるために設計されたのである。たとえば、表示などのために式１７を修正することにより適当な何らかの目的のために文書イメージを再びＲＧＢカラースペースに変換することができることは明白である。
【００８２】
他のカラースペース変換に、文書イメージをＲＧＢカラースペースからＹＣｏＣｇカラースペースに変換する方法がある。ＹＣｏＣｇ表現では、Ｙで表されるルミネセンス、Ｃｏで表されるクロミナンスオレンジ、Ｃｇで表されるクロミナンスグリーンを利用する。ＲＧＢ成分は、（たとえば、上述の従来のＹＵＶの代わりに）変換を使用してＹＣｏＣｇにマッピングすることができる。
【００８３】
【数１２】
0004773678.tif 000015
【００８４】
ＹＣｏＣｇカラースペースマッピングの利点は、ＲＧＢからＹＣｏＣｇへ、またＹＣｏＣｇからＲＧＢへの逆変換に整数演算を利用できるという点であることが著しい。さらに、逆変換は乗算なしで実行できる。ＹＣｏＣｇカラースペース表現を使用すると、普及しているＹＵＶに比べて圧縮効率が著しく高いが、それは現代的なデジタル画像データに対する主成分分析から得られる統計的に最適な空間に対する近似が優れているからである。アドバンストＹＣｏＣｇカラースペースは、表示目的には設計されておらず、圧縮用に設計されている。さらに、式１８の式または変換では整数演算を使用するため、文書イメージを計算効率の高い方法でＹＣｏＣｇカラースペースに変換することができる。
【００８５】
カラースペースコンバータ７０２は、カラースペースからカラースペースへ文書イメージを変換できることは明白である。たとえば、カラースペースコンバータ７０２は、文書イメージをＹＵＶカラースペースからＹＣｏＣｇカラースペースに変換することができる。さらに、文書イメージがすでに好ましいカラースペース内にある場合、変換は実行されない。
【００８６】
マスクセパレータ７０４は、文書イメージをカラースペースコンポーネント７０２から受け取って、マスクを生成する。マスクセパレータ７０４によって生成されるマスクを使用して、文書イメージを２つのレイヤ、前景イメージと背景イメージに分割する。本発明の他の態様ではイメージを２つよりも多いレイヤに分割できることは理解されるであろう。マスクは、マスクイメージとも呼ばれ、２値イメージであり、各ピクセル値によってピクセルが前景イメージに属するのか、それとも背景イメージに属するのかを判別する。マスクセパレータ７０４によって、マスク、前景イメージ、背景イメージの合わせたサイズが小さくなるようにマスクが生成される。
【００８７】
マスクを生成するのにさまざまな方式が使用できる。圧縮の場合、同等のピクセル値は異なるピクセル値よりも圧縮率がよい。たとえば、青空の領域は色と強度が変化する領域よりも圧縮率がよい。上述のように、マスクを生成するのは、マスク、前景イメージ、および背景イメージを組み合わせた場合のサイズに対する推定値を引き下げるためである。
【００８８】
採用できる方法の１つに、可能なすべてのマスクを生成し、単に最良のものを選択するという方法がある。ピクセルをＮ個含む文書イメージの場合、可能なマスクは２Ｎ個ある。したがって、可能なすべてのマスクを検討して、どれが最小になる組合せイメージを生成するかを判別することができる。しかし、可能なすべてのマスクを検討することは高い計算能力を必要とし、時間もかかるため、一般的には実用的でない。
【００８９】
他の方法として、文書を複数の領域に細分し、それぞれの領域を分析してピクセルを割り当て、領域をマージする方法がある。エネルギー分散は、得られる圧縮率の推定であり、距離の平方和に基づく測定である。文書の小さな領域、たとえば２×２ピクセルまたは４×４ピクセルをエネルギー分散に関して分析することができる。この小さな領域を前景領域と背景領域に分割し、その小さな領域のエネルギー分散が低減または最小化されるようにできる。可能なすべてのマスクを分析して、使用するマスクを決定できるが、それは、領域がこのような分析を実現可能なものにできるほど小さいからである。たとえば、４ピクセルの領域については、その領域に対してマスクの１６の可能な順列しかない。その小さな領域をマージしてまとめ、マスクを生成できるが、それは全体として、マスク、前景イメージ、および背景イメージの組み合わせたサイズを低減する。
【００９０】
マスクを生成する他の方法として、前景および背景がある領域上で一定であり、それらの定数値に関して分散またはエネルギー分散を最小にするか、または実質的に減らすマスクが生成される。ここで分散は、実際にマスクを生成する代わりに、文書イメージを分割して前景と背景のイメージを取得し、それらを圧縮する前景および背景の両方に関して得られる圧縮の推定値として使用される。上述のようにエネルギー分散は、エネルギー測度でもあり（距離の平方の和）、圧縮後の前景および背景のサイズの許容可能な推定値である。まず、マスクを圧縮するコストは完全に無視できる。さらなるステップでは、マスクのサイズを考慮することもできる。
【００９１】
与えられた領域についてその領域がＮ個のピクセルの集合Ｓであり、ＦおよびＢはパーティションである（つまり、Ｆ∪Ｂ＝Ｓかつ
【００９２】
【数１３】
0004773678.tif 000016
【００９３】
）。ｆ（ｘ）がピクセル位置ｘ，ｘ∈Ｓのイメージ値の場合、前景および背景の分散はそれぞれ次のようになる。
【００９４】
【数１４】
0004773678.tif 000017
【００９５】
ただし、
【００９６】
【数１５】
0004773678.tif 000018
【００９７】
は、それぞれ、前景および背景の平均であり、ＮＦおよびＮＢはそれぞれ、前景および背景内のピクセルの個数である。これらの分散は以下のように表すこともできることに留意されたい。
【００９８】
【数１６】
0004773678.tif 000019
【００９９】
和Ｅ＝ｖＦ＋ｖＢを最小にするＳの適当なパーティションＦおよびＢを見つける。このような簡素化を行っても、２Ｎ個のマスクがあり得るため問題はそれでも並外れて困難である。したがって、イメージをさらに２×２ピクセルサブイメージに分割する。それぞれの２×２サブイメージ上に、マスクは２４＝１６個しかあり得ず、これは、このような領域のそれぞれで（１６の組合せすべてを試して、最小のエネルギーで保持することにより）Ｅ＝ｖＦ＋ｖＢを最小にする最適なＦおよびＢを求めることが可能であることを意味している。１６の組合せすべてを試す必要がないことが分かる。問題は、Ｋ＝２の場合のＫ−ｍｅａｎｓ問題と等価であり、ｆ（イメージ）がスカラー関数であるので、解を求められる値ｆ（ｘ）を並べ替え、非常に効率よく計算できる、つまり４ピクセル値すべてを並べ替え、３つのパーティションのうちの１つ（並べ替えに関して）から最低のエネルギーが求められる。それぞれのパーティションにおいて部分和を再利用して、演算回数を最小にすることができる。
【０１００】
しかし、この解法には欠点があり、すべての２×２部分領域はピクセルノイズがごくわずかであってもピックアップする可能性のある異なる前景および背景を持ち、不適切なマスクが生じるというものである。次のステップで、隣接する領域同士を結合する。たとえば、２つの領域１および２と、対応する前景および背景Ｆ１、Ｂ１、およびＦ２、Ｂ２を仮定する。これら４つの集合を組み合わせると、実際に７つの異なる組合せが得られる。
【０１０１】
【表３】
0004773678.tif 000020
【０１０２】
勝利の組合せは、最低エネルギーＥ＝ｖＦ＋ｖＢが得られる組合せである。７つの組合せすべてを試すか、または前景および背景の平均を並べ替えてその並べ替えに関するパーティションのみを考慮することに注意されたい。さらに、それぞれの領域が量
【０１０３】
【数１７】
0004773678.tif 000021
【０１０４】
と前景に対するＮＦおよび
【０１０５】
【数１８】
0004773678.tif 000022
【０１０６】
およびＮＢを保持する場合、Ｅの組合せを一定時間で計算できる。マージした後、通常、これらの量を再計算する必要があるが、幸運なことに、これも一定時間で実行できる。さらに、領域にわたる和
【０１０７】
【数１９】
0004773678.tif 000023
【０１０８】
は、それぞれの領域に関して一定であり、最適なパーティションを選択する目的で計算する必要はないことに注意されたい。さらに領域にわたるこの和
【０１０９】
【数２０】
0004773678.tif 000024
【０１１０】
を使用して、以下に示すように、領域をマージしない場合を決定することもできる。
【０１１１】
隣接する領域同士を組み合わせる操作は、水平方向に隣接する２×２領域を組み合わせて２×４領域にし、その後垂直方向に隣接する２×４領域を組み合わせて４×４領域にすることで行う。４×４領域は、８×８領域に組み合わされ、領域が１つだけ残るまで繰り返され、この領域が前景と背景とに分割される。
【０１１２】
残念なことに、このような手法で複数の階調を前景または背景に入れるマージとなり、領域内に２色を超える色があるときはいつもテキストなどの重要な詳細が失われる可能性がある。たとえば、領域１に白地に灰色で書かれたテキストが置かれ領域２はほとんど黒である場合、これら２つの領域のマージにより灰色と白色が得られる領域の前景に入り、黒が背景に入るため、テキスト情報が失われることになる。しかし、２色を前景または背景のいずれかにマージするときはいつも、その領域に対してエネルギーの急激な増大（または分散）が顕著になるが、それはこのような領域に対しては一定であるということはもはやよいモデルではなくなるからである。そこで、エネルギーＥが実験的に求められる特定のしきい値Ｋを超えた場合に隣接する領域をマージしないようにするアルゴリズムを採用することが望ましい。このアルゴリズムにより、１ページ内のテキストおよびグラフィックスラインの大半を捕捉するマスクが得られる。
【０１１３】
しかし、このアルゴリズムは、数多くの改良点を持ち、その１つは単純領域を採用していることである。小領域（たとえば、４×４）のＩ領域エネルギーを測定し、そのエネルギーが十分に低い場合（実験的に求めた別のしきい値を使用して）、領域全体を前景または背景に配置することができる。したがって、エネルギーがしきい値よりも低い場合に、小さな領域の分割を避けることで、アルゴリズムの動作を高速化することができる。前景および背景に対する一定という仮定を使用する代わりに、多項式回帰を使用して、前景と背景を表すことができる。たとえば、多項式が式αｘ＋βｙ＋μで定められる平面の場合、エネルギーは以下の式で定義される。
【０１１４】
【数２１】
0004773678.tif 000025
【０１１５】
ただし、ｘ、ｙはピクセル位置のインデックスであり、αＦ、βＦおよびμＦはｖＦを最小にするスカラーであり、αＢ、βＢ、およびμＢはｖＢを最小にするスカラーである。αＦ、βＦ、およびμＦは量
【０１１６】
【数２２】
0004773678.tif 000026
【０１１７】
を使用して一定時間内に解くことができる。これは、３つの未知数と３つの方程式からなる一次方程式系であり、同じことがαＢ、βＢ、およびμＢに適用される。前のように、アルゴリズムはボトムアップであり、マージ毎にＥを最小にする。前景および背景は、平均で並べ替えることはできず、したがって、７つの組合せすべてをテストしてＥを最小にする組合せを求める。一定時間内に各テストおよびマージの実行を続けるために、量
【０１１８】
【数２３】
0004773678.tif 000027
【０１１９】
とＮを前景および背景の各領域について保持しなければならない。単純領域の最適化はそれでも可能ではあるが、領域、多項式回帰、またはその両方で一定であることを仮定できる。
【０１２０】
マスクプロセッサコンポーネント７０６は、マスクに対して処理操作を何回でも実行する。マスクプロセッサコンポーネントは、ノイズ除去コンポーネント７０８、およびディザ検出器７１０を含む。本発明の他の態様には他のマスク処理コンポーネントを含めることができることは明白である。本発明の他の態様に多少の処理コンポーネントを含めることができることはさらに明白である。
【０１２１】
ノイズ除去コンポーネント７０８は、マスクからノイズを除去する。上述のように、デジタル文書は通常標準文書内でスキャンすることにより作成される。ある程度のノイズはほとんどいつでも、スキャンおよびデジタル化プロセスを介してデジタル文書に入り込む。たとえば、スキャナのトレー上の指紋や文書の折り返しにより、ノイズおよび／または誤ったマークが文書イメージ内に入り込むことがある。ノイズ除去コンポーネント７０８はまず、マスク内のノイズを識別しようとする。マスクを識別するのにさまざまな方式を使用できる。１つの方法として、接続されたコンポーネントについてマスクを分析する方法がある。接続コンポーネントは、同じ色、たとえば黒色の接続ピクセルである。マスクは左から右に、上から下に、ページ毎にスキャンされ、接続コンポーネントの検索が行われる。接続コンポーネントは、位置および形状またはビットマップ情報とともに格納することができる。その後、文書の各ピクセルを分析して、ノイズの有無を判別する。こうして、ピクセル毎に、５個のピクセルの距離内のすべてのピクセルなどの囲む領域を分析して、囲む領域内の、および／または囲む領域を交差する多数の接続コンポーネントを決定する。接続コンポーネントの個数がしきい値よりも少ない場合、ピクセルはノイズであるとみなされ、マスクから除去される。その後、どちらか圧縮率のよい方という条件でピクセルを前景または背景イメージに割り当てる。本発明によれば他の方法も使用できる。
【０１２２】
一般に、ノイズ除去コンポーネント７０８はランダムに見える、かつ／または文書内のテキストまたはイメージに無関係のように見えるピクセルを識別することができる。ノイズ除去コンポーネント７０８は必ずしも文書からすべてのノイズを除去するわけではないことは明白である。ノイズ除去コンポーネント７０８は、ピクセルを前景イメージまたは背景イメージに割り当てることによりマスクから識別されたノイズを除去する。さらに、ノイズは、たとえばノイズとして識別されたピクセルを囲むピクセルの値で置き換えることで除去することもできる。
【０１２３】
ディザ検出器７１０マスク内のディザリングを検出し、マスクからディザリングを除去する。ディザリングは、モノクロ表示装置またはプリンタにさまざまな灰色の陰影の錯覚を作り出したり、カラー表示装置またはプリンタに追加色を表示するためにコンピュータグラフィックスで採用している手法である。ディザリングは、異なるパターンで色分けされているドットの集まりとしてイメージの領域を処理することに依存している。ハーフトーンと呼ばれる印刷イメージと似ているが、ディザリングは効果の平均を取り、認知された単一の陰影または色をマージすることにより異なる色の青色スポットへの目の傾向を利用する。与えられた領域内の黒色ドットと白色ドットとの比に応じて効果全体が特定の灰色陰影となる。ディザリングは、コンピュータグラフィックスに現実感を加え、低解像度での曲線および対角線のぎざぎざしたエッジを滑らかにする場合に使用される。しかし、ディザリングには文書イメージに関する問題がある。ディザリングは適切に検出し処理しないと、テキスト、手書き、またはグラフィックとして誤って解釈されることがある。
【０１２４】
ディザ検出器７１０は、マスク内のディザリング領域を識別し、それらの領域を分割して、各領域または部分領域が類似したディザリングパターンを持つようにすることができる。ディザ検出器７１０は、識別されたディザリング領域を除去または処理する。たとえば、ディザ検出器７１０はディザリング領域を明るい灰色であるとして識別することがある。ディザ検出器７１０は、ディザリング領域を単に除去したり、その領域を明るい灰色に設定したりできる。領域を陰影に変える場合も文書イメージを変更することになることは明白である。ディザ検出器７１０はさらに、マスクを修正することにより、識別されたディザリング領域を前景または背景に再割り当てすることもできる。
【０１２５】
ディザリングを検出および／または処理するのにさまざまな方式を使用できる。１つの方法として、接続されたコンポーネントについてマスクを分析する方法がある。接続コンポーネントは、同じ色、たとえば黒色の接続ピクセルである。マスクは左から右に、上から下に、ページ毎にスキャンされ、接続コンポーネントの検索が行われる。接続コンポーネントは、位置および形状またはビットマップ情報とともに格納することができる。マスクのピクセル毎に、囲む領域内の、および／または囲む領域と交差する一定量の接続コンポーネントを決定する。囲む領域は、７などのピクセルを囲む多数のピクセルとすることができる。領域内の接続コンポーネントの数がしきい値よりも多い場合、ディザリングは除去される。その後、ピクセルを前景または背景イメージのいずれかに割り当てて、ディザリングを除去することができる。この割り当てを決定するには、領域の背景内のピクセルの数量と領域の前景内のピクセルの数量を計算する。次に、領域の前景内のピクセルの数量が領域の背景内のピクセルの数量よりも多い場合にそれらのピクセルを前景に割り当て、そうでない場合にピクセルを背景に割り当てることができる。本発明ではディザリングやハーフトーン作成を識別および／または処理する他の方法を採用することができる。
【０１２６】
クラスタ化コンポーネント７１２はマスク内のクラスタを識別する。クラスタ化コンポーネント７１２はマスク内に接続コンポーネントを配置する。接続コンポーネントは、たとえば、上述のように、複数の接続ピクセルであり、４方向接続コンポーネントまたは８方向接続コンポーネントのいずれかとすることができる。マスク内に接続コンポーネントを配置した後、クラスタ化コンポーネント７１２は類似の接続コンポーネントを識別して、それらをクラスタとしてグループ化する。クラスタとは類似の接続コンポーネントの１グループのことである。一般に、クラスタは手書きを含む英数字文字を表すが、他の情報も含めることができる。しかし、単一文字を表すクラスタは多数あり得る。クラスタ化を採用すると圧縮率が劇的に向上する。
【０１２７】
圧縮率が高まり、ファイルサイズが縮小する理由は、それぞれの接続コンポーネントが位置、および形状の辞書に属している形状へのポインタにより要約されるということである。この形状は、接続コンポーネントまたはクラスタのビットマップつまり「イメージ」である。接続コンポーネントはマークとも呼ばれる。このアルゴリズムのクラスタ化の態様では、その辞書に属する形状および各接続コンポーネントに最も近い形状を決定する。通常、形状の辞書は、ファイルサイズの数分の１であり、複数ページにわたって共有さえできる。形状へのポインタは、ページ内の位置（ＸおよびＹ）と形状番号により特徴付けられる。ＸおよびＹ位置は、前の位置を使って圧縮できるが、形状インデックスはコンテキストまたは言語モデルを使って圧縮される。
【０１２８】
クラスタ化コンポーネント７１２ではさまざまな方法を使ってクラスタを識別することができる。１つの方法として、マークの形状を互いに比較して、同等の、かつ／または同一のマークを識別する方法がある。既存のクラスタの特性およびマークまたは接続コンポーネントの特性を使用する方法もある。既存のクラスタは、少なくとも１つのマークからなるグループであり、すでにクラスタとして定義されているものである。文書から抽出されたマークの特性を既存のクラスタの特性と比較する。このような比較には、不一致を識別するためにタイミングのよい、ビット毎のコストのかかる比較は不要である。マーク特性と既存のクラスタ特性とが一致しない場合、またマークが既存のクラスタからかけ離れすぎているとみなされる場合、そのマークは新しいクラスタとして追加され、ビット毎の比較は回避される。この方式では、不一致を検出する計算効率のよいスクリーニングとクラスタ化の肯定的一致を検出する計算効率のよいアルゴリズムの両方によりそれ自体と他の方式とを区別する。
【０１２９】
採用できるクラスタの特定の特性は、ｘサイズとｙサイズである。ｘサイズおよびｙサイズは、既存のクラスタのサイズ設定情報を規定する。マークのｘサイズおよびｙサイズを、既存のクラスタのｘサイズおよびｙサイズと比較し、不一致を識別する。本発明の一態様では、クラスタをｘサイズとｙサイズでインデックスを作成した２Ｄバケットテーブルを構成する。新しいマークが見つかると、同一のｘサイズおよびｙサイズのバケットが抽出され、マークがバケット内のクラスタと比較される。隣接するバケットも、さらに正確な一致に関して検索することができる（他のバケットはすべて無視されるかまたはスクリーニングされる）。後述のクラスタ中心に関する「ドリフトなし」の仮定はここでは役立つが、それはクラスタがバケット内にとどまることを保証されるからである。
【０１３０】
マークと既存のクラスタとの比較に使用できる特性の１つにインクサイズがある。インクサイズとは一般に、マークまたはクラスタ内の黒色ピクセルとピクセル全体との比を指す。同様に、マークのインクサイズを、既存のクラスタのインクサイズと比較して、不一致を識別することができる。マークの他の特性に「ホットポイント」がある。ホットポイントはマーク上のある位置であり、重心とすることができ、または他の手段により計算することができる（たとえば、囲む文字の直線方程式）。比較を開始する前にマークのホットポイントとクラスタの位置を揃えると、多くの場合並行移動（ｔｒａｎｓｌａｔｉｏｎ）する。さらに他の特性として、縮小されたマークまたはイメージがあるが、これはピクセルサイズの縮小バージョンで、マークおよび／またはクラスタのビットマップである。本発明の一態様では、縮小マークはホットポイントの中心に置かれ、マークは縮小マークのサイズが固定されるように拡大縮小される。再び、クラスタのドリフトなし仮定が、クラスタの縮小バージョンがクラスタ内のすべてのマークを適切に表現することを保証する際に役立つ。縮小マークと既存のクラスタの縮小マークまたは縮小イメージとを比較して不一致を識別することができる。
【０１３１】
マークに対するすべての特性テストが成功した場合、より直接的な方法でクラスタ化との比較が行われる。マークとクラスタとの距離を計算し、第１のしきい値と比較する。距離がしきい値の範囲内にあれば、マークは既存のクラスタに追加される。マークを第１の許容可能な既存クラスタに追加したり、あるいはマークを、そのマークとの比較から最小距離にある既存クラスタに追加することができる。
【０１３２】
さらに、クラスタ内に配置されている第１の要素によりクラスタを特徴付けることができる。そのような方式の利点は、新しいマークをクラスタに追加する場合でもクラスタの特性の再計算が不要だという点である。この方式の他の利点として、新しいマークをクラスタに追加する毎にクラスタ中心が移動する際に発生する「クラスタドリフト」が避けられるという点が挙げられる。クラスタドリフトがないことは、「ドリフトなし」仮定とも呼ばれるが、これにより、同じクラスタの２つの要素の間の最大距離が保証され、この保証で効率のよい積極的なスクリーニングが行える。このような方式の主な欠点は、ｋ−ｍｅａｎｓなどの他のクラスタ化アルゴリズムと比べて同じクラスタ−マーク間距離に対してクラスタが多くなるという意味でクラスタ化が最適でないという点である。しかし、この方式の著しい利点は速度向上にある。テキスト圧縮が容易になり、クラスタの個数が１０％増えることは問題ではない。というのも、各クラスタの情報を伝達する辞書のサイズが通常、圧縮された文書のサイズの数分の１だからである。
【０１３３】
クラスタ化コンポーネント７１２がマスク内のクラスタを識別した後、マスク上で光学式文字認識（ＯＣＲ）を実行するＯＣＲコンポーネント７１４がマスクを受け取る。ＯＣＲコンポーネント７１４は、マスク内の文字である可能性のあるものを識別し、クラスタ化コンポーネント７０７からのクラスタを利用して、文字に関するクラスタの分析を支援することができる。各クラスタを分析して、クラスタが文字かどうかを判別し、その後、そのクラスタがどのような文字を表すかを判別する。この方式は、言語および／またはアルファベットが異なれば異なる。一般に、クラスタの形状またはビットマップを使用しているアルファベットの形状またはビットマップと比較する。その形状が十分似ていれば、クラスタはその特定の文字であると認識される。見つかったそれぞれの文字の位置情報をその順序とともに保持することができる。文字は、ＡＳＣＩＩなどの標準アルファベットの文字の列として格納できる。
【０１３４】
レイアウトコンポーネント７１６はマスクに作用し、圧縮率を高め、レイアウト情報を伝達する。レイアウト情報を後から使用して、文書イメージをリフローすることができる。レイアウトコンポーネント７１６は、圧縮率を高め、かつ／またはレイアウト情報を伝達するためにさまざまな方式を使用することができる。ある方式では、最初に接続コンポーネントを色、垂直位置、および／または水平位置により整理する。クラスタ化コンポーネント７１２などの、システム７００の他のコンポーネントにより接続コンポーネントを提供することもできる。レイアウトコンポーネント７１６は、その後、少なくとも一部は色、垂直位置、水平位置、結合距離（たとえば、接続コンポーネント間の距離）、接続コンポーネントの高さ、および／または接続コンポーネントの幅に基づき接続コンポーネントを結合または組み合わせる。したがって、結合された接続コンポーネントは２つまたはそれ以上の接続コンポーネントで構成される。結合コンポーネントは、さらに、他の接続コンポーネントまたは他の結合コンポーネントと結合することもできる。レイアウトコンポーネント７１６は、提供するレイアウト情報を生成する。レイアウト情報には、結合コンポーネントの位置、ラインの位置、および文書イメージのその他の情報を含むことができる。
【０１３５】
マスクエンコーダ７１８は、レイアウト分析コンポーネント７１６からマスクを受け取り、そのマスクをエンコードしてマスクビットストリームと呼ばれる圧縮ビットストリームを生成する。マスクエンコーダ７１８では適当な圧縮方式を採用できる。マスクは２値形式であり、通常はテキスト情報を含む。したがって、２値形式およびテキスト情報も圧縮する圧縮方式を選択しなければならない。２レベル圧縮方式を使用してマスクをエンコードすることもできる。さらに、マスクエンコーダ７１８は、たとえば、ライブラリ、辞書、シンボル、テーブルサイズなどのマスクビットストリームをデコードするために使用されるエンコーディング情報をエンコードするかまたは供給する。
【０１３６】
マスクをエンコードするのに使用できる圧縮方式としてＣＣＩＴＴ（国際電信電話諮問委員会）方式がある。ＣＣＩＴＴは、現在ＩＴＵ−Ｔ国際電気通信連合−通信部門（１９９４年に名称変更）と呼ばれる規格制定機関であり、ＦＡＸ／モデム通信のための可逆圧縮技術の名称になっている。この種の圧縮は、２値イメージでうまく働く。標準的な圧縮比は、旧バージョンのＶ．４２ｂｉｓでは、４：１、新しいバージョンのＶ．４４  ２０００では６：１で、これはＬｅｍｐｅｌ−Ｚｉｖ−Ｊｅｆｆ−Ｈｅａｔｈ（ＬＺＪＨ）圧縮アルゴリズムに基づいている。本発明により他の圧縮方法または方式を使用してマスクをエンコードすることができる。
【０１３７】
前景背景セグメンタ７１９は、文書イメージとマスクを受け取り、その文書イメージを前景イメージおよび背景イメージに分離する。本発明のこの態様により、前景イメージおよび背景イメージは文書イメージと実質的に同じサイズである（たとえば、文書イメージが６４０×４８０で、前景イメージが６４０×４８０で、背景イメージが６４０×４８０ピクセル）。しかし、本発明の他の態様では、文書イメージとサイズが実質的に異なる前景イメージおよび背景イメージを生成することができる。前景イメージおよび背景イメージは、組合せまたは組み換えたときに、文書イメージと同一になるかまたは類似する。
【０１３８】
前景背景セグメンタ７１９は、２値形式であるマスクを使用して、前景イメージと背景イメージとを作成する。たとえば、マスク内で１により表されているすべてのピクセルは前景イメージに入り、マスク内で０により表されるすべてのピクセルは背景イメージに入る。逆に、たとえば、マスク内で０により表されているすべてのピクセルは前景イメージに入り、マスク内で１により表されるすべてのピクセルは背景イメージに入ることもできる。しかし、背景イメージおよび前景イメージは通常、ピクセルに値が割り当てられていない。値が割り当てられていないピクセルは、穴、空領域、および／または注意しなくてよいピクセルと呼ばれる。
【０１３９】
さらに、前景背景セグメンタ７１９は、膨張処理コンポーネント７２０と画像修正コンポーネント７２１を含む。膨張処理コンポーネント７２０は、前景イメージおよび／または背景イメージに応じてマスクに作用する。膨張操作は、マスクを受け取りｋを定数（たとえば、２）としてｋ個のピクセルで「１」の領域を拡大する距離変換に基づく形態論操作である。距離は、マンハッタン距離または球面距離である。逆演算である浸食（ｅｒｏｓｉｏｎ）は、逆マスクの膨張処理により実行できる。通常のスキャンされた文書では、テキストはインクのにじみやスキャン時の低ｄｐｉ設定の結果、消えかかっている（ｗａｓｈ  ｏｕｔ）ことが多い。したがって、白色から黒色への遷移は連続的段階的な遷移であり、マスクにより前景と背景との間のハード境界が定義される。前景と背景の両方の境界近くで連続遷移があると、リンギングが入り込み、エンコードに手間がかかることがある。このような影響を緩和するために、境界付近のピクセル値を無視するとよい。これは、複数のピクセルの距離（たとえば、２）だけ、前景および背景の両方に対する「注意しなくてよい」値の膨張処理を実行して行う。テキストの領域周辺で、「注意しなくてよい」ピクセルの膨張処理により、コントラストおよび可読性の両方が高まるが、ファイルサイズは縮小する。しかし、自然のイメージの領域内で膨張処理を使用すると、コントラストが高まる結果、イメージがマンガ的になる。この問題を回避するために、マスクのレイアウト分析を実行し、テキストからなる領域を検出する。膨張操作は、テキスト領域にのみ固有のものとすることができる。膨張処理コンポーネント７２０は、マスクを前景マスクと背景マスクとに分けることができる。その結果、前景および背景の両方に対して注意しなくてよいピクセルが生じる。これらのピクセルはそれでも、妥当な値を割り当てられるが、それは、膨張距離が小さく、前景および背景は通常、圧縮のせいでなめらかであり、したがって注意しなくてよいピクセルに、隣にある注意するピクセルからあまり隔たっていない値を割り当てられる。しかし、注意しなくてよいピクセルの膨張処理時には注意するピクセルの小さいまたは細い領域を完全に抹消しないよう注意しなければならない。このようなことになると、ピクセルは強制されず、注意するピクセルからはるか隔たり、はるか遠い領域からの予測できない色付けが生じることになる。このようなことを防ぐために、距離変換に注意し、極値が注意するから注意しなくてよいに切り替わるのを防ぐ。
【０１４０】
最終的には前景イメージおよび背景イメージを組み合わせて組み換え文書を生成できることは明白である。しかし、鋭いエッジや遷移があると、圧縮は低下し、組み替えられたイメージはエッジやラインなどの視覚的欠陥を生じることがある。たとえば、マスクにより実質的に類似している色領域に偽境界が生じ、実質的に類似している領域の一部が前景イメージに別の一部が背景イメージに置かれることになる場合にこのようなことが発生する。これらの部分は、別々に処理され別々にエンコードされるため、最終的に組み換えたときに偽境界に視覚的に目立ったラインを生じる。さらに、偽境界は本質的にそれぞれの部分でエンコードされるためこれらの部分の圧縮率は低下する可能性がある。
【０１４１】
画像修正コンポーネント７２１はマスクに作用し、文書イメージの「画像修正」を行うため、文書イメージの全体的な圧縮率が改善され、視覚的に、組み替えられた文書イメージも向上する。一般に、画像修正コンポーネント７２１は、マスクを使って偽境界を識別しかつ／または前景および／または背景イメージを拡大する。一方式では、画像修正コンポーネント７２１はマスクを使用して、前景イメージおよび背景イメージ内の偽境界を識別する。検出は、ピクセルの最初のしきい値量（たとえば、５ピクセル）よりも長いマージされた領域境界の水平および／または垂直ラインを識別することで行うが、その際に（１）境界の片側が前景、他方の側が背景であり、（２）いずれかの側のそのラインに沿った直線回帰が第２のしきい値よりも多い量の分だけ異なる（たとえば、直線回帰をピクセルの前景側の境界ピクセル上で実行し、ピクセルの背景側のピクセルに対して直線回帰を実行する）。画像修正コンポーネント７２１は、マスクセパレータ７０４からこの領域情報を取得することができる。画像修正コンポーネント７２１は次に、マスクから別々の前景マスクおよび背景マスクを生成することにより前景および／または背景イメージを拡大する。前景マスクは前景イメージを拡大し、背景マスクは背景イメージを拡大する。一般に、前景イメージおよび背景イメージは偽境界をまたいでピクセル数分拡大される。前景マスクおよび背景マスクは通常、デコードプロセスの一部としてエンコードまたは使用されないことは明白である。組み替え時に、また本発明に従って、画像修正コンポーネント７２１に対して他の方式を使用し、文書イメージの圧縮率を高め、視覚的表示を向上させることができる。
【０１４２】
上述のように、前景背景セグメンタ７１９は、マスクを使用して文書イメージを前景イメージと背景イメージに分割する。前景マスクと背景マスクとが膨張処理コンポーネント７２０および／または画像修正コンポーネントにより生成される場合、前景マスクを使用して文書イメージを前景イメージに分割し、背景マスクを使用して文書イメージを背景イメージに分割する。
【０１４３】
前景ピクセルフィラー（ｆｏｒｅｇｒｏｕｎｄ  ｐｉｘｅｌ  ｆｉｌｌｅｒ）７２２は、前景背景セパレータセグメンタ７１９から前景イメージを受け取る。一般に、前景ピクセルフィラー７２２は、前景イメージ内の注意しなくてよい領域または空領域を識別し、これらの領域を注意しなくてよいピクセルで埋める。これらの領域は、前景イメージ内に空領域または注意しなくてよい領域を残している背景イメージに割り当てられた文書イメージのピクセルから形成される。この注意しなくてよいピクセルは、通常、組み替えられた文書イメージ内に存在し、前景ピクセルフィラー７２２では注意しなくてよいピクセルの視覚的表示を考慮しない。本発明の他の態様では、マスクウェーブレット圧縮方式などの注意しなくてよい領域を適切に扱える圧縮方式を使用することにより注意しなくてよいピクセルを埋める操作を回避することができる。
【０１４４】
上述のように、前景イメージおよび背景イメージは空の領域つまり注意しなくてよい領域を持つ。空の領域はさまざまな方法で取り扱うことができる。１つの方法では、空の領域にデータを書き込み、普通の圧縮手法を用いる。イメージの空の領域を埋める単純なプロセスでは、それらの空の領域にそのイメージに対する平均ピクセル値を書き込む。しかし、このプロセスではマスク境界のところに急激な不連続が生じることがあり、与えられたピーク信号対雑音比（ＰＳＮＲ）に対する必要なビットレートが高まり、マスクまたは空の領域の境界の付近に顕著なリンギングが発生する場合がある。他のプロセスでは、それぞれのピクセルに最も近い非マスク（または注意する領域）ピクセルの色をつける。標準の形態論アルゴリズムを使用すると、すべてのピクセルにわたり２パスのみでプロセスを実行することができ、マスクの下にボロノイ充填空領域が生じる。次に、前景イメージまたは背景イメージを再構成したら、再構成されたイメージにローパスを実行し、既知のピクセルをその正しい値に復元する。ローパスフィルタの遮断周波数が低すぎる場合、鋭いエッジが発生し、境界の付近に必要なビットレートが高くなり、顕著なリンギングが増える。
【０１４５】
空領域を扱う他の方法として、凸集合への射影を使用する方法がある。たとえば、２つの凸集合、つまり、表示ピクセル上の入力と一致するイメージの集合と０に設定されたある種のウェーブレット係数を持つイメージの集合を考察する（たとえば、特定の解像度レベルを超える全ての高周波係数）。２つの集合への射影を交互に切り替えることにより、表示ピクセルと一致し、０のウェーブレット係数が多数あることから圧縮率の高いイメージを見つけることができる。
【０１４６】
空領域を扱う他の方法としてさらに、不規則グリッド用に明示的に設計されたウェーブレット変換を使用する方法がある。このようなウェーブレット分解は、コンピュータビジョンおよびコンピュータグラフィックスにおける幾何データの圧縮の問題で必要になる。このようなウェーブレットは、マスクの不規則パターンに適合される。
【０１４７】
他の方式では、注意しなくてよい領域を注意しなくてよいピクセルで埋めることなく前景イメージを効率よく圧縮できるエンコーディングを行うマスクウェーブレット圧縮方式を使用する。図１に関して説明したようなマスクウェーブレット圧縮方式は、採用できる圧縮方式の１つである。本発明により、注意しなくてよい領域を取り扱う他の適当な方式を使用することができる。
【０１４８】
前景ダウンサンプル（ｄｏｗｎｓａｍｐｌｅ）コンポーネント７２４は、前景ピクセルフィラー７２２から前景イメージを受け取り、前景イメージのダウンサンプリングを行う。前景ダウンサンプルコンポーネント７２４は、前景イメージのサイズを縮小し、前景イメージおよび文書イメージの圧縮率を高める。たとえば、６４０×４８０ピクセルの前景イメージを３２０×２４０にダウンサンプリングできる。前景イメージをダウンサンプリングするのにさまざまな方式を使用できる。方法の１つに、いくつかのピクセルを破棄して前景イメージをダウンサンプリングする方法がある。したがって、たとえば、すべての他のピクセルを破棄することにより前景イメージを６４０×４８０ピクセルから３２０×２４０にダウンサンプリングできる。他の方法として、前景イメージからの対応するピクセルの平均に基づいて新しいピクセルを生成する方法がある。たとえば、前景イメージの新しいピクセルをそれぞれ、８個の隣接するピクセルの平均として生成することができる。さらに他の方法では、三次補間を使ってダウンサンプリングする。さらに本発明によればイメージをダウンサンプリングする他の方法を採用できる。エンコーダで前景および背景をダウンサンプリングする場合、一般に、マスクを使って組み合わせる前にデコーダ内でアップサンプリング（ｕｐｓａｍｐｌｅ）しなければならない。
【０１４９】
前景エンコーダ７２６は、前景イメージをエンコードする。前景エンコーダ７２６は、前景イメージからエンコードされたビットストリームを生成する。このビットストリームは、前景ビットストリームと呼ぶことができる。前景エンコーダ７２６では、多数の適当な圧縮方式を使って、前景イメージをエンコードすることができる。たとえば、採用できるいくつかの圧縮方式例としてプログレッシブウェーブレットエンコーディングまたはプログレッシブトランスフォームエンコーディングがある。
【０１５０】
前景エンコーダ７２６は、さらに、前景イメージの圧縮率を高めるため一定色接続コンポーネントアナライザ（図に示されていない）を含むこともできる。一定色接続コンポーネントでは、クラスタ化コンポーネント７１２について説明したのと同様の方式とアルゴリズムを使用できる。一定色接続コンポーネントアナライザが、前景イメージをスキャンして、一定色接続ピクセルを識別する。一定色接続ピクセルのグループがしきい値よりも大きい場合、そのグループは一定色接続コンポーネントまたは一定色マークとみなされる。「一定色」には、色のいくつかのバリエーションが含まれることが理解される。一定色接続コンポーネントアナライザは、さらに、類似の一定色接続コンポーネントを一定色クラスタにグループ化することができる。一定色クラスタの位置情報、一定色接続コンポーネントのビットマップ、形状、位置情報などの関連情報を前景ビットストリームとともに含めることができる。一定色は、テキストで構成される領域を検出するために、採用されているレイアウトアナライザーを介してテキストに制限することもできる。
【０１５１】
背景ピクセルフィラー７３０は、前景背景セパレータ７１９から背景イメージを受け取る。背景ピクセルフィラー７３０は、背景イメージ内の注意しなくてよい領域を識別し、これらの領域を注意しなくてよいピクセルで埋める。これらの領域は、背景イメージ内に空領域または注意しなくてよい領域を残している前景イメージに割り当てられた文書イメージのピクセルから形成される。この注意しなくてよいピクセルは、通常、組み替えられた文書イメージ内に存在し、背景ピクセルフィラー７３０では注意しなくてよいピクセルの視覚的表示を考慮しない。本発明の他の態様では、マスクウェーブレット圧縮方式などの注意しなくてよい領域を適切に扱える圧縮方式を使用することにより注意しなくてよいピクセルを埋める操作を回避することができる。背景ピクセルフィラー７３０は、実質的に前景ピクセルフィラー７２２と同じ動作をする。
【０１５２】
上述のように、背景イメージおよび前景イメージは空の領域つまり注意しなくてよい領域を持つ。空の領域はさまざまな方法で取り扱うことができる。１つの方法では、空の領域にデータを書き込み、普通の圧縮手法を用いる。イメージの空の領域を埋める単純なプロセスでは、それらの空の領域にそのイメージに対する平均ピクセル値を書き込む。しかし、このプロセスではマスク境界のところに急激な不連続が生じることがあり、与えられたピーク信号対雑音比（ＰＳＮＲ）に対する必要なビットレートが高まり、マスクまたは空の領域の境界の付近に顕著なリンギングが発生する場合がある。他のプロセスでは、それぞれのピクセルに最も近い非マスク（または注意する領域）ピクセルの色をつける。標準の形態論アルゴリズムを使用すると、すべてのピクセルにわたり２パスのみでプロセスを実行することができ、マスクの下にボロノイ充填空領域が生じる。次に、前景イメージまたは背景イメージを再構成したら、再構成されたイメージにローパスを実行し、既知のピクセルをその正しい値に復元する。ローパスフィルタの遮断周波数が低すぎる場合、鋭いエッジが発生し、境界の付近に必要なビットレートが高くなり、顕著なリンギングが増える。
【０１５３】
空領域を扱う他の方法として、凸集合への射影を使用する方法がある。たとえば、２つの凸集合、つまり、表示ピクセル上の入力と一致するイメージの集合と０に設定されたある種のウェーブレット係数を持つイメージの集合を考察する（たとえば、特定の解像度レベルを超える全ての高周波係数）。２つの集合への射影を交互に切り替えることにより、表示ピクセルと一致し、０のウェーブレット係数が多数あることから圧縮率の高いイメージを見つけることができる。
【０１５４】
空領域を扱う他の方法としてさらに、不規則グリッド用に明示的に設計されたウェーブレット変換を使用する方法がある。このようなウェーブレット分解は、コンピュータビジョンおよびコンピュータグラフィックスにおける幾何データの圧縮の問題で必要になる。このようなウェーブレットは、マスクの不規則パターンに適合される。
【０１５５】
他の方式では、注意しなくてよい領域を注意しなくてよいピクセルで埋めることなく背景イメージを効率よく圧縮できるエンコーディングを行うマスクウェーブレット圧縮方式を使用する。図１に関して説明したようなマスクウェーブレット圧縮方式は、採用できる圧縮方式の１つである。本発明により、注意しなくてよい領域を取り扱う他の適当な方式を使用することができる。
【０１５６】
背景ダウンサンプルコンポーネント７３２は、背景ピクセルフィラー７３０から背景イメージを受け取り、背景イメージのダウンサンプリングを行う。背景ダウンサンプルコンポーネント７３２は、背景イメージのサイズを縮小し、背景イメージおよび文書イメージの圧縮率を高める。たとえば、６４０×４８０ピクセルの背景イメージを３２０×２４０にダウンサンプリングできる。背景イメージをダウンサンプリングするのにさまざまな方式を使用できる。方法の１つに、いくつかのピクセルを破棄して背景イメージをダウンサンプリングする方法がある。したがって、たとえば、他のすべてのピクセルを破棄することにより背景イメージを６４０×４８０ピクセルから３２０×２４０にダウンサンプリングできる。他の方法として、背景イメージからの対応するピクセルの平均に基づいて新しいピクセルを生成する方法がある。たとえば、背景イメージの新しいピクセルをそれぞれ、８個の隣接するピクセルの平均として生成することができる。さらに本発明によればイメージをダウンサンプリングする他の方法を採用できる。一般に、前景イメージおよび背景イメージのサイズは、前景ダウンサンプルコンポーネント７２４および背景ダウンサンプルコンポーネント７３２によって縮小された後も実質的に同じである。
【０１５７】
背景エンコーダ７３４は、背景イメージをエンコードする。背景エンコーダ７３４は、背景イメージからエンコードされたビットストリームを生成する。このビットストリームは、背景ビットストリームと呼ぶことができる。背景エンコーダ７３４では、多数の適当な圧縮方式を使って、背景イメージをエンコードすることができる。たとえば、採用できるいくつかの圧縮方式例としてプログレッシブウェーブレットエンコーディングまたはプログレッシブトランスフォームエンコーディングがある。
【０１５８】
背景エンコーダ７３４は、さらに、背景イメージの圧縮率を高めるため一定色接続コンポーネントアナライザ（図に示されていない）を含むこともできる。一定色接続コンポーネントでは、クラスタ化コンポーネント７１２に関して説明したのと同様の方式とアルゴリズムを使用できる。一定色接続コンポーネントアナライザが、背景イメージをスキャンして、一定色接続ピクセルを識別する。一定色接続ピクセルのグループがしきい値よりも大きい場合、そのグループは一定色接続コンポーネントまたは一定色マークとみなされる。「一定色」には、色のいくつかのバリエーションが含まれることが理解される。一定色接続コンポーネントアナライザは、さらに、類似の一定色接続コンポーネントを一定色クラスタにグループ化することができる。一定色クラスタの位置情報、一定色接続コンポーネントのビットマップ、形状、位置情報などの関連情報を背景ビットストリームとともに含めることができる。一定色は、レイアウトアナライザーがテキストで構成される領域を検出するために使用されている場合にテキストに制限することもできる。
【０１５９】
マスクエンコーダ７１８、前景エンコーダ７２６、および背景エンコーダ７３４とともに適当な圧縮方式をいくつでも使用できる。これらの方式のうちいくつかについて上で説明した。マスクエンコーダ７１８、前景エンコーダ７２６、および背景エンコーダ７３４とともに使用できる圧縮方式および追加圧縮方式の詳細をここで説明する。
【０１６０】
本発明で使用できるよく知られている圧縮方式として、ＪＰＥＧ（ＪｏｉｎｔＰｈｏｔｏｇｒａｐｈｉｃ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ）、ＰＷＴ（Ｐｒｏｇｒｅｓｓｉｖｅ  Ｗａｖｅｌｅｔ  Ｔｒａｎｓｆｏｒｍ）、ＪＰＥＧ  ２０００、ＰＴＣ（Ｐｒｏｇｒｅｓｓｉｖｅ  Ｔｒａｎｓｆｏｒｍ  Ｃｏｄｅｃ）、ＧＩＦ（Ｇｒａｐｈｉｃ  Ｉｎｔｅｒｃｈａｎｇｅ  Ｆｏｒｍａｔ）、ＰＮＧ（Ｐｏｒｔａｂｌｅ  Ｎｅｔｗｏｒｋ  Ｇｒａｐｈｉｃｓ）を使用できる。ＪＰＥＧは、標準的圧縮比が２：１である可逆圧縮の設定があるが、一般的には非可逆圧縮であり、離散コサイン変換（ＤＣＴ）に基づいている。この圧縮技術は、一般的に、写真イメージで使用される。ＪＰＥＧは、フルカラー圧縮に対し平均圧縮比２０：１で１ピクセル２４ビットの色（１６００万色）を格納できる。しかし、一般的に、平均圧縮比は１０：１から２０：１で、目立った損失はなく、６０：１〜１００：１が中画質、６０：１〜１００：１が低画質となる。この技術のわずかな欠点として、鋭いエッジに対する処理の難しさと、透明性のサポートが欠如していることが挙げられる。さらに、ＧＩＦ形式よりも表示に時間が長くかかるが、フルカラーや階調スキャンで取り込んだ写真などのイメージに関してはＧＩＦよりも優れている。
【０１６１】
ＰＷＴは、可逆技術の一部であり、他の多くの圧縮技術の基盤となっている。ＰＷＴは、イメージ全体を最初に表示し、時間を追って解像度を繰り返し上げてゆくのが一番よいという考えに基づいている。このため、高忠実度のイメージを効率よく転送できる。特に、低頻度コンポーネントを最初に転送することにより、イメージ全体の低解像度バージョンが転送される。その後、高い頻度のコンポーネントが到着する毎に解像度を上げてゆく。
【０１６２】
ＪＰＥＧ  ２０００は、ウェーブレットベースの圧縮技術を使用するＤＣＴに基づいてＪＰＥＧ規格の代替とする目的で設計された。ＪＰＥＧ  ２０００では、２４ビットカラーを維持しながら、ＪＰＥＧに存在したブロッキングの問題をなくした。さらに、ＪＰＥＧ  ２０００は、非可逆と可逆の両方の圧縮をサポートし、非可逆で圧縮比は２０１：１、可逆では２：１となっている。
【０１６３】
ＰＴＣは、ＪＰＥＧ、ＧＩＦ、ＰＮＧ、Ｍ−ＪＰＥＧ、ＪＰＥＧ−ＬＳおよびその他の形式などの機能のいくつかを組み合わせた圧縮方式であるが、より優れた圧縮効率を持ち、多くの場合、エンコードおよびデコードが著しく高速化されている。ＰＴＣは、ＪＰＥＧに比べてサイズが縮小される。
【０１６４】
ＰＴＣは新しい機能も追加している。追加された重要機能の１つに、スケーラビリティ（またはプログレッシブレンダリング（ｐｒｏｇｒｅｓｓｉｖｅ  ｒｅｎｄｅｒｉｎｇ））がある。元のＰＴＣファイルから、その一部を解析してデコードすることにより、より解像度の低い、または忠実度の低い画像を得ることができる。また、ＰＴＣは１色当たり最大１６ビットまでサポートし、４色チャネルまたは成分（Ｒ、Ｇ、Ｂ、およびアルファ）をサポートするが、ここでアルファとは透明度成分である。また、ＰＴＣは可逆および非可逆エンコーディングを単一コーデックにまとめている。さらに、ＰＴＣ用の効率的な参照コードも利用できる。このコードは、使用メモリ量が少なく、整数演算のみを使用し（浮動小数点演算を使用しない）、正確な再現性を実現している。
【０１６５】
ＰＴＣを実装するために、多解像度変換（ｍｕｌｔｉ−ｒｅｓｏｌｕｔｉｏｎｔｒａｎｓｆｏｒｍ）を使用して、プログレッシブレンダリングを実現する。１つの方法では、ウェーブレットを使用するが、計算コストの低いより効率的な方法では、階層型重複変換（ｈｉｅｒａｒｃｈｉｃａｌ  ｌａｐｐｅｄ  ｔｒａｎｓｆｏｒｍｓ）を使用する。ＰＴＣでは、新しい階層型重複双直交変換（ＬＢＴ：ｈｉｅｒａｒｃｈｉｃａｌ  ｌａｐｐｅｄ  ｂｉｏｒｔｈｏｇｏｎａｌ  ｔｒａｎｓｆｏｒｍ）が、より小さな４×４ブロックサイズと整数係数とを使用することにより、従来のＰＴＣ構成を基に改善し、実質的に乗算なしで計算を実行できるようにしている（従来のＰＴＣ方式の変換では浮動小数点算術演算を使用していた）。重複変換が一般に普及している離散コサイン変換（ＪＰＥＧおよびＭＰＥＧで使用しているＤＣＴ）に勝っている主な利点は、重複変換にはＤＣＴの「ブロッキングの問題」を免れているという点である。また、ＰＴＣで使用しているＬＢＴが多解像度（階層型）形式であるため、リンギングの問題もＤＣＴベースのコーデックに比べてあまり目立たなくなっている。
【０１６６】
ＧＩＦは、平均圧縮比３：１ほどで１ピクセル８ビット色（２５６色）の可逆圧縮形式である。ＧＩＦはＬｅｍｐｅｌ−Ｚｉｖ−Ｗｅｌｃｈ（ＬＺＷ）符号化方式を組み込んでいるため、写真については大きな圧縮率を達成していないが、単純な線の描画に適している。ＧＩＦ圧縮は、あらゆる種類のイメージで利用できるが、ごくわずかしか色を使用しないコンピュータ生成グラフィックスで最も効率よく使用することができ、これがＷｅｂベースのグラフィックス用に普及している理由となっている。さらに、鋭いエッジを含む図表イメージについてはＪＰＥＧよりも圧縮率がよい。
【０１６７】
ＰＮＧは、ＧＩＦに比べて平均１０〜３０％ほどサイズが小さくなる圧縮機能を提供する可逆形式である。これもまた、トゥルーカラーイメージについてはＪＰＥＧよりも優れているが、４８ビット色を使用しておりＪＰＥＧの２４ビット色に勝っている。さらに、ＰＮＧは透明性に対応しており、その圧縮は非対称的、つまり、伸張は高速であるが、圧縮にかなり時間がかかる。ＰＮＧは、インターネットで使用することを目的に開発されており、高速な伸張がプラスされている。さらに、ＰＮＧは、ＬＺＷ符号化を採用しているＧＩＦ形式の代替を目的に設計された。ＰＮＧでは、ＬＺＷ符号化の代わりにフリーウェアのＧｚｉｐ圧縮方式を採用している。
【０１６８】
図８は、本発明の一態様によるセグメント化されたレイヤ化イメージデコードシステムを示すブロック図である。システムは、圧縮されたビット、ビットストリームまたはファイルを受け取り、組み替えたイメージを生成する。このシステムには、セパレータコンポーネント８０２、前景デコーダ８０４、背景デコーダ８０６、マスクデコーダ８０８、リフローコンポーネント８１０、およびコンバイナ８１２が含まれる。
【０１６９】
セパレータコンポーネント８０２は、圧縮されたビット列を受け取り、それらのビットを分離して前景ビットストリーム、背景ビットストリーム、およびマスクビットストリームを形成する。セパレータコンポーネント８０２は、ヘッダ情報を使用してビットストリームを分離する。前景デコーダ８０４は、前景ビットストリームを伸張して、前景イメージを生成する。背景デコーダ８０６は、背景ビットストリームを伸張して、背景イメージを生成する。
【０１７０】
マスクデコーダ８０８は、マスクビットストリームを伸張して、マスクまたはマスクイメージを生成する。また、マスクデコーダ８０８はレイアウトおよび／またはリフロー情報を受け取る。さらに、マスクデコーダ８０８は、テキスト情報を再構成するために使用される辞書を取得することができる。一部の圧縮方式（たとえば、マスクウェーブレット）では、前景デコーダ８０４および背景デコーダ８０６は前景イメージおよび背景イメージを取得するためにマスクデコーダ８０８から伸張されたマスクを取り出す必要がある場合がある。
【０１７１】
リフローコンポーネント８１０は、所望の表示特性に応じて前景イメージ、背景イメージ、およびマスクに作用する。所望の表示特性には、表示ページサイズ、列数、フォントサイズなどの特性を含めることができる。所望の表示特性は、元の文書イメージの特性とかなりかけ離れることがある。たとえば、文書イメージは、レターページサイズと１０ポイントのフォントサイズを有することができる。文書イメージのこれらの特性は、標準のレターペーパーで表示するのに適している。しかし、これらの特性ではポータブルデジタルアシスタント（ＰＤＡ）などの携帯型デバイスで視ることを非常に困難にする。ＰＤＡは、一般に表示画面が狭く、解像度が低い。リフローがないと、ＰＤＡを使用するユーザーはテキストの各行を読むのにスクロールしていかなければならない。したがって、ＰＤＡの場合、所望の表示特性は列サイズ２０、フォントサイズ１４などである。リフローコンポーネント８１０は、所望の表示特性に従って、必要に応じてテキストを折り返し、段落の位置を変更し、センテンスの位置を変更し、イメージの位置を変更し、イメージのサイズを変更し、かつ／またはその他の適当な修正を加えることができる。リフローコンポーネント８１０は、前景イメージ、背景イメージ、および／またはマスクとともにエンコードされたレイアウト情報を利用する。
【０１７２】
コンバイナ８１２は、前景イメージ、背景イメージ、およびマスクを組み合わせて組み換え文書イメージを生成する。組み替えられたイメージは、オリジナルの文書をイメージと同一であるかまたは近似的なイメージである。さらに、組み替えられたイメージは所望の表示特性に応じて形状および／またはサイズが異なることがある。コンバイナ８１２は、マスクに基づいて前景イメージおよび背景イメージから組み替えられた文書イメージのピクセルを生成する。組み替えられた文書のそれぞれのピクセルは、マスクの対応するピクセルを参照することにより決定され、それにより組み替えられた文書のピクセルの出所が前景イメージなのか背景イメージなのかを判別することができる。たとえば、マスクピクセル値１は組み替えられた文書のピクセルの出所が前景イメージの対応するピクセルであることを示す。さらに、コンバイナ８１２は、適当なカラースペース変換を必要に応じて実行する。たとえば、ＹＣｏＣｇカラースペースを使用して、組み替えられたイメージを表現することができる。そこで、この例を続けると、コンバイナ８１２は、ＹＣｏＣｇカラースペースからＲＧＢカラースペースに変換する（たとえば、モニタに表示するために）。
【０１７３】
図９は、本発明の一態様による文書イメージのエンコード方法を示す流れ図である。文書イメージは９０２で与えられる。文書イメージはビットマップイメージであり、通常はＲＧＢである、カラースペース表現を持つ。文書イメージをそのカラースペースから、ＹＵＶやＹＣｏＣｇなどの他のカラースペースに変換し、圧縮率を高めることができる。
【０１７４】
９０４で、文書イメージのマスクが生成される。このマスクは文書イメージに基づく２値イメージである。マスクは、文書イメージをセグメントに分割または前景イメージと背景イメージに分割し、前景イメージと背景イメージが高い圧縮率を持つように生成される。マスクの各ピクセルにより、文書イメージの対応するピクセルを前景イメージに配置するか、背景イメージに配置するかを決定する。圧縮後、マスク、前景イメージ、および背景イメージの合わせたサイズが小さくなるような適当な方法でマスクを生成することができる。
【０１７５】
ノイズ検出、ノイズ訂正、ディザ検出、および処理を限定せずに含むマスクの追加的な処理をそのマスクに対して実行できることは明白である。たとえば、デジタル化プロセスで文書イメージにノイズが入り込むことが多い。たとえば、指紋や汚れを意図せず文書イメージにつけてしまうことがある。ノイズを識別して、マスクから除去することができる。ディザリングは、変化する灰色またはカラーの陰影の錯覚を作り出すために使用される手法である。ディザリングでは、陰影をシミュレートするために領域内のドットの比またはパーセンテージを変える。ディザリングを使用するとイメージを見栄え良くすることができるが、デジタル文書では問題を生じることがある。ディザリングがテキスト、手書きなどとして誤って解釈される可能性がある。マスク内のディザリングを識別して、適宜処理することができる。
【０１７６】
さらに、マスク内のクラスタを識別することができる。マスク内で接続コンポーネントが識別される。接続コンポーネントは、１つまたは複数の接続ドット、通常は黒色ドットのグループである。類似の接続をコンポーネントはクラスタにまとめられる。それぞれのクラスタは、ビットマップとマスク内の位置へのポインタで表すことができる。クラスタを使用することで、膨大な領域を節約できる。クラスタは、文字、手書きなどを表すことができる。
【０１７７】
また、光学式文字認識をマスク上で実行することができる。クラスタは、手書きを表そうとテキストを表そうと、分析してテキストまたは文字を識別することができる。文字が認識されると、文字をたとえば、ＡＳＣＩＩコードとして保存することで、さらにいっそう格納領域を節約することができる。さらに、光学式文字認識を使用することで、リフローを強化し、文書イメージを最終的に組み替えたときに文書イメージの編集を容易に行えるようにできる。
【０１７８】
マスクをさらに分析して、文書イメージのレイアウト特性を識別することもできる。文字、クラスタ、およびイメージ位置を分析することで、レイアウト特性の識別が可能である。センテンス、段落、フォーム、イメージ位置、ページ付けを限定せずに含むレイアウト特性も識別できる。後で使用するため、マスクとともにレイアウト特性を添付またはエンコードすることができる。
【０１７９】
９０６で、マスクに従って文書イメージを前景イメージおよび背景イメージに分割する。たとえば、マスク内で１により表されているすべてのピクセルは前景イメージに入り、０により表されるすべてのピクセルは背景イメージに入る。本発明の他の態様で文書イメージを他の適当な数のレイヤに分割できること、また本発明が図９に関して説明した２つのレイヤに制限されないことは明白である。
【０１８０】
前景イメージおよび背景イメージは文書イメージとサイズが同じである。しかし、前景イメージおよび背景イメージは、ピクセルに値が割り当てられていない。これらのピクセルを穴、空隙、および／または空領域と呼ぶ。穴は、それらのピクセルに対応する値が他のイメージに割り当てられていた場合に発生する。背景イメージおよび前景イメージに画像修正を行うことで、最終的に組み替えられるイメージ内のハードエッジを減らすことができる。画像修正では、前景イメージおよび背景イメージを多数のピクセルで拡大し、鋭いエッジおよび／または遷移を避けるようにする。通常、画像修正では、マスクから前景マスクと背景マスクを生成し、その前景マスクを使って文書イメージから前景イメージを分割し、背景マスクを使って文書イメージから背景イメージを分割する。前景マスクを使用すると前景イメージを拡大しやすくなり、背景マスクを使用すると背景イメージを拡大しやすくなる。
【０１８１】
９０８で、前景イメージ内の穴または空隙を、注意しなくてよいピクセルで埋める。注意しなくてよいピクセルは、圧縮後、前景イメージの圧縮率が高くなり、前景イメージのサイズが小さくなるように選択する。注意しなくてよいピクセルは、さまざまな適当な方法で決定することができる。採用できる方法の１つに、注意しなくてよい領域を文書イメージの平均ピクセル値で埋めるという方法がある。しかし、このプロセスではマスク境界のところに急激な不連続が生じることがあり、与えられたピーク信号対雑音比（ＰＳＮＲ）に対する必要なビットレートが高まり、マスクまたは空の領域の境界の付近に顕著なリンギングが発生する場合がある。他の方法では、注意しなくてよい領域内のそれぞれのピクセルに、最も近い非マスク（または注意する領域）ピクセルの色をつける。標準の形態論アルゴリズムを使用すると、すべてのピクセルにわたり２パスのみでプロセスを実行することができ、マスクの下にボロノイ充填空領域が生じる。次に、前景イメージまたは背景イメージを再構成したら、再構成されたイメージにローパスを実行し、既知のピクセルをその正しい値に復元する。ローパスフィルタの遮断周波数が低くなりすぎる場合、鋭いエッジが発生し、境界の付近に必要なビットレートが高くなり、顕著なリンギングが増える。空領域を扱う他の方法として、凸集合への射影を使用する方法がある。たとえば、２つの凸集合、つまり、表示ピクセル上の入力と一致するイメージの集合と０に設定されたある種のウェーブレット係数を持つイメージの集合を考察する（たとえば、特定の解像度レベルを超える全ての高周波係数）。２つの集合への射影を交互に切り替えることにより、表示ピクセルと一致し、０のウェーブレット係数が多数あることから圧縮率の高いイメージを見つけることができる。本発明により、注意しなくてよい領域を埋める他の適当な方式を使用することができる。
【０１８２】
９１０で、背景イメージ内の穴または空隙を、注意しなくてよいピクセルで埋める。注意しなくてよいピクセルは、圧縮後、背景イメージの圧縮率が高くなり、背景イメージのサイズが小さくなるように選択する。注意しなくてよいピクセルは、前景イメージに関する上述のさまざまな適当な方法で決定することができる。
【０１８３】
本発明の他の態様で空領域を埋めないままにしておくことができることは明白である。したがって、マスクウェーブレット圧縮方式などの圧縮方式を使用して、前景イメージおよび背景イメージをエンコードする際に空領域または注意しなくてよい領域を埋める必要がない。
【０１８４】
９１２で、マスクをエンコードしてマスクビットストリームを生成する。適当な圧縮方式によりマスクをエンコードする。この圧縮方式では、テキスト情報とマスクの２値表現を使用して、マスクの圧縮率を高めることができる。さらに、クラスタ、レイアウト情報などもマスクの圧縮率を高めるに使用できる。
【０１８５】
前景イメージおよび背景イメージに追加的な処理を実行できることは明白である。たとえば、前景イメージおよび背景イメージに対し、ノイズ除去およびダウンサンプリングを実行できる。ノイズ除去では、前景イメージおよび背景イメージ内に存在するノイズを除去したり処理したりする。通常、このようなノイズは、スキャンプロセスや変換プロセスで入り込む。ダウンサンプリングを実行すると、前景イメージと背景イメージのサイズが縮小する。たとえば、６４０×４８０ピクセルの前景イメージと背景イメージを３２０×２４０のサイズのイメージにダウンサンプリングできる。
【０１８６】
９１４で、前景イメージをエンコードして前景ビットストリームを生成する。適当な圧縮方式により前景イメージをエンコードする。前景イメージをエンコードするのに使用できる圧縮方式の例として、ＰＷＣ、ＰＴＣ、ＪＰＥＧ、ＪＰＥＧ  ２００、ＰＮＧ、およびＧＩＦがある。本発明によれば他の圧縮方式も使用できる。
【０１８７】
９１６で、背景イメージをエンコードして背景ビットストリームを生成する。適当な圧縮方式により背景イメージをエンコードする。背景イメージをエンコードするのに使用できる圧縮方式の例として、ＰＷＣ、ＰＴＣ、ＪＰＥＧ、ＪＰＥＧ  ２００、ＰＮＧ、およびＧＩＦがある。本発明によれば他の圧縮方式も使用できる。
【０１８８】
また背景イメージおよび前景イメージを分析して一定色接続コンポーネントを識別し、前景イメージおよび背景イメージの圧縮率をさらに高めることもできる。一定色接続コンポーネントは、実質的に色値が同じである複数の接続ピクセルを備える。一定色接続コンポーネントは、色のシードピクセルを配置し、アルゴリズムを使用して同じ色または実質的に同じ色を持つ接続ピクセルのすべてまたは実質的にすべてを見つけることにより識別することができる。
【０１８９】
マスクビットストリーム、前景ビットストリーム、および背景ビットストリームを９１８で組み合わせて組合せビットストリームにする。組合せビットストリームもファイルでよい。使用したエンコーダ、辞書、シンボル、ライブラリなどの情報を含むヘッダ情報を、組み合わせたビットストリームに追加することもできる。
【０１９０】
図１０は、本発明の一態様による文書イメージをデコードする方法を示す流れ図である。１００２でビットストリームを受け取る。ビットストリームは組み合わせたビットストリームであり、マスクビットストリーム、前景ビットストリーム、背景ビットストリーム、およびヘッダ情報を含む。１００４で、ビットストリームは、マスクビットストリーム、前景ビットストリーム、および背景ビットストリームに分割される。さらに、ヘッダ情報を抽出できる。
【０１９１】
１００６で、マスク、前景イメージ、および背景イメージをマスクビットストリーム、前景ビットストリーム、および背景ビットストリームからそれぞれデコードする。マスク、前景イメージ、および背景イメージを、イメージ成分と総称する。エンコードに使用した圧縮方式と互換性のある伸張方式を使用して、マスク、前景イメージ、および背景イメージをデコードする。ヘッダ情報には、この圧縮／伸張情報を入れることができる。マスクおよび／またはヘッダ情報に、レイアウト情報またはレイアウト特性を入れることができる。さらに、辞書、シンボル、およびその他の情報をマスクからデコードしたり、ヘッダ情報から取得することができる。
【０１９２】
１００８に表示特性を与える。表示特性は、ユーザーによって予め定められた入力とし、かつ／または動的に決定することができる。表示特性には、表示サイズ、フォントサイズ、列などの情報を含めることができる。１０１０で、表示特性に従って、マスク、前景イメージ、および背景イメージを修正する。イメージ成分は、組み換えたときに、表示特性と一致するように修正される。たとえば、マスク内のテキストをリフローして、パン操作なしで狭い画面上に適切に表示できる。
【０１９３】
１０１２でマスク、前景イメージ、および背景イメージを組み合わせて、組み替えられた文書イメージを形成する。マスクに従って前景イメージおよび背景イメージを組み合わせて、組み替えられた文書イメージを形成する。マスクは２値で、組み替えられた文書イメージの各ピクセルはマスクの対応するピクセルに応じて前景イメージまたは背景イメージの対応するピクセルから値を割り当てる。組み替えられた文書イメージは、オリジナルの文書イメージと同一であるかまたは近似的なイメージである。オリジナルの文書イメージは、受け取ったビットストリームに最初にエンコードされた文書イメージである。
【０１９４】
本発明のシステムおよび／または方法をシステム全体で使用することにより、テキスト、手書き、図面などを識別しかつ／または圧縮することが容易になることは理解されるであろう。さらに、当業者であれば、本発明のシステムおよび／または方法は、写真複写機、文書スキャナ、光学式文字認識システム、ＰＤＡ、ＦＡＸマシン、デジタルカメラ、および／またはデジタルビデオカメラを限定せずに含む、さまざまな文書イメージ用途に使用できることを理解するであろう。
【０１９５】
本発明のさまざまな態様に関する背景についてさらに説明するために、図１１および以下の説明では、本発明のさまざまな態様を実装する適当なコンピューティング環境１１１０の簡潔で一般的な説明を行う。コンピューティング環境１１１０は、１つの可能なコンピューティング環境にすぎず、本発明を採用できるコンピューティング環境を制限する意図はないことは理解されるであろう。本発明は、１つまたは複数のコンピュータで実行可能なコンピュータ実行可能命令の一般的コンテキストにおいて上で説明したとおりであるが、本発明は他のプログラムモジュールと組合せ、かつ／またはハードウェアとソフトウェアとの組合せとして、実装できることも理解するであろう。一般に、プログラムモジュールには、特定のタスクを実行する、あるいは特定の抽象データ型を実装するルーチン、プログラム、コンポーネント、データ構造などが含まれる。さらに、本発明の方法が、シングルプロセッサまたはマルチプロセッサのコンピュータシステム、ミニコンピュータ、メインフレームコンピュータ、パーソナルコンピュータ、ハンドヘルドコンピューティングデバイス、マイクロプロセッサベースまたはプログラム可能な民生電子機器（それぞれ１つまたは複数の関連装置に結合できる）などの他のコンピュータシステム構成でも実施できることは明白であろう。本発明の図に示されている態様はさらに、通信ネットワークを介してリンクされているリモート処理デバイスにより複数のタスクが実行される分散コンピューティング環境で実施することも可能である。分散コンピューティング環境では、プログラムモジュールをローカルとリモートの両方のメモリ記憶装置に配置できる。
【０１９６】
図１１は、本発明で説明しているシステムおよび方法を利用するのに助けとなる１つの可能なハードウェア構成を示している。スタンドアロンアーキテクチャが示されているが、本発明により適当なコンピューティング環境を使用できることは理解されるであろう。たとえば、スタンドアロン、マルチプロセッサ、分散、クライアント／サーバ、ミニコンピュータ、メインフレーム、スーパーコンピュータ、デジタルおよびアナログを含むが、これらには限定されないコンピュータアーキテクチャを本発明により使用することができる。
【０１９７】
図１１を参照すると、本発明のさまざまな態様を実装する環境例１１１０は、処理装置１１１４、システムメモリ１１１６、およびシステムメモリを含むさまざまなシステムコンポーネントを処理装置１１１４に結合するシステムバス１１１８を含むコンピュータ１１１２を含む。処理装置１１１４は、さまざまな市販プロセッサがあるがそのうちどれでもよい。デュアルマイクロプロセッサおよびその他のマルチプロセッサアーキテクチャも、処理装置１１１４として採用することができる。
【０１９８】
システムバス１１１８には、さまざまな市販バスアーキテクチャを使用するメモリバスまたはメモリコントローラ、周辺バス、およびローカルバスを含む数種類のバス構造がある。コンピュータメモリ１１１６は、読み取り専用メモリ（ＲＯＭ）１１２０およびランダムアクセスメモリ（ＲＡＭ）１１２２を含む。起動時などにコンピュータ１１１２内の要素間の情報伝送を助ける基本ルーチンを含む基本入出力システム（ＢＩＯＳ）は通常、ＲＯＭ  １１２０に格納される。
【０１９９】
コンピュータ１１１２はさらに、たとえば取り外し可能ディスク１１２８への読み書きを行うハードディスクドライブ１１２４、磁気ディスクドライブ１１２６、および、たとえばＣＤ−ＲＯＭディスク１１３２の読み込みを行ったり、その他の光媒体への読み書きを行う光ディスクドライブ１１３０を含むことができる。ハードディスクドライブ１１２４、磁気ディスクドライブ１１２６、および光ディスクドライブ１１３０は、ハードディスクドライブインタフェース１１３４、磁気ディスクドライブインタフェース１１３６、および光ドライブインタフェース１１３８によりそれぞれ、システムバス１１１８に接続される。コンピュータ１１１２は、通常、少なくともある種の形態のコンピュータ読み取り可能媒体を含む。コンピュータ読み取り可能媒体は、コンピュータ１１１２からアクセスできる使用可能な媒体である。たとえば、コンピュータ読み取り可能媒体は、コンピュータ記憶媒体および通信媒体を含むことができるが、これに限定されるものではない。コンピュータ記憶媒体は、コンピュータ読み取り可能命令、データ構造体、プログラムモジュール、またはその他のデータなどの情報を格納する方法または技術で実装される揮発性および不揮発性、取り外し可能および取り外し不可能媒体を含む。コンピュータ記憶媒体としては、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたはその他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多目的ディスク（ＤＶＤ）もしくはその他の磁気記憶デバイス、または所望の情報を格納するために使用することができコンピュータ１１１２によりアクセスできるその他の媒体があるが、これらに限定されるものではない。通信媒体は、通常、コンピュータ読み取り可能命令、データ構造体、プログラムモジュール、または搬送波もしくはその他のトランスポートメカニズムなどの変調データ信号内のその他のデータを実現し、情報配信媒体を含む。「変調データ信号」という用語は、信号内の情報をエンコードする方法でその特性のうち１つまたは複数を設定または変更した信号を意味する。たとえば、通信媒体としては、有線ネットワークまたは直接配線接続などの有線媒体、および、音響、ＲＦ、赤外線、およびその他の無線媒体などの無線媒体があるが、これらに限定されるものではない。上記のいずれかの組合せもコンピュータ読み取り可能媒体の範囲に収まるであろう。
【０２００】
オペレーティングシステム１１４０、１つまたは複数のアプリケーションプログラム１１４２、その他のプログラムモジュール１１４４、およびプログラム非割り込みデータ１１４６を含む、多数のプログラムモジュールをドライブおよびＲＡＭ  １１２２に格納することができる。コンピュータ１１１２内のオペレーティングシステム１１４０は、多数市販されているオペレーティングシステムのどれでもよい。
【０２０１】
ユーザーは、キーボード１１４８およびマウス１１５０などのポインティングデバイスを介してコンピュータ１１１２にコマンドおよび情報を入力できる。他の入力デバイス（図に示されていない）としては、マイクロフォン、ＩＲリモートコントロール、ジョイスティック、ゲームパッド、衛星放送受信アンテナ、スキャナなどがある。これらの入力デバイスやその他の入力デバイスは、システムバス１１１８に結合されているシリアルポートインタフェース１１５２を介して処理装置１１１４に接続されることが多いが、パラレルポート、ゲームポート、またはユニバーサルシリアルバス（ＵＳＢ）、ＩＲインタフェースなどの他のインタフェースにより接続することもできる。モニタ１１５４やその他のタイプの表示デバイスも、ビデオアダプタ１１５６などのインタフェースを介してシステムバス１１１８に接続される。モニタに加えて、コンピュータは通常、スピーカやプリンタなどの他の周辺出力デバイス（図に示されていない）を含む。
【０２０２】
コンピュータ１１１２は、リモートコンピュータ１１５８などの１つまたは複数のリモートコンピュータへの論理および／または物理接続を使用してネットワーク環境で動作することもできる。リモートコンピュータ１１５８は、ワークステーション、サーバコンピュータ、ルータ、パーソナルコンピュータ、マイクロプロセッサベースの娯楽機器（ｅｎｔｅｒｔａｉｎｍｅｎｔ  ａｐｐｌｉａｎｃｅ）、ピアデバイスまたはその他の共通ネットワークノードでもよく、通常は、コンピュータ１１１２に関係する上述の要素の多くまたはすべてを含むが、簡単のためメモリ記憶装置１１６０のみが図に示されている。図に示されている論理接続は、ローカルエリアネットワーク（ＬＡＮ）１１６２とワイドエリアネットワーク（ＷＡＮ）１１６４を含む。このようなネットワーキング環境は、事務所、企業規模のコンピュータネットワーク、イントラネットおよびインターネットではよくある。
【０２０３】
ＬＡＮネットワーキング環境で使用する場合は、コンピュータ１１１２はネットワークインタフェースまたはアダプタ１１６６を介してローカルネットワーク１１６２に接続される。ＷＡＮネットワーキング環境で使用する場合は、コンピュータ１１１２は通常、モデム１１６８を含むか、またはＬＡＮで通信サーバに接続されるか、またはインターネットなどのＷＡＮ  １１６４上で通信を確立するためのその他の手段を有する。モデム１１６８は、内蔵でも外付けでもよいが、シリアルポートインタフェース１１５２を介してシステムバス１１１８に接続される。ネットワーク環境では、コンピュータ１１１２またはその一部に関して述べたプログラムモジュールは、リモートメモリ記憶装置１１６０に格納できる。図に示されているネットワーク接続は例であり、コンピュータ間に通信リンクを確立するのにその他手段を使用できることは理解されるであろう。
【０２０４】
図１２は、本発明で対話操作できるサンプルコンピューティング環境例１２００の概略ブロック図である。システム１２００は、１つまたは複数のクライアント１２１０を含む。クライアント１２１０は、ハードウェアおよび／またはソフトウェア（たとえば、スレッド、プロセス、コンピューティングデバイス）とすることができる。システム１２００はさらに、１つまたは複数のサーバ１２３０を含む。サーバ１２３０も、ハードウェアおよび／またはソフトウェア（たとえば、スレッド、プロセス、コンピューティングデバイス）である。サーバ１２３０は、たとえば、本発明を採用することにより変換を実行するスレッドを格納できる。クライアント１２１０とサーバ１２３０との間の１つの可能な通信として、２つまたはそれ以上のコンピュータプロセスの間で伝送されるように修正されたデータパケットの形式のものがある。システム１２００は、クライアント１２１０とサーバ１２３０との間の通信を円滑にするための通信フレームワーク１２５０を含む。クライアント１２１０は、情報をクライアント１２１０にローカルで格納するために使用できる１つまたは複数のクライアントデータ記憶装置１２６０に接続し動作させることができる。同様に、サーバ１２３０は、情報をサーバ１２３０にローカルで格納するために使用できる１つまたは複数のサーバデータ記憶装置１２４０に接続し動作させることができる。
【０２０５】
上述の内容には、本発明の実施例が含まれる。もちろん、本発明を説明するためにコンポーネントまたは方法の考えられるすべての組合せを説明することは不可能であるが、当業者であれば、本発明の他の多くの組合せおよび置換が可能であることは理解できるであろう。したがって、本発明は、請求項の精神と範囲に収まるそのようなすべての改変、修正、およびバリエーションを包含するものとする。さらに、「含む」という用語を詳細な説明または請求項で使用している範囲において、このような用語は「備える、含む」という用語と同様の使い方において包括的であることを意図しており、これは「備える、含む」という用語を使用した場合に請求項中の暫定的用語と解釈されるのと同様である。
【図面の簡単な説明】
【図１】本発明の一態様による分割されたレイヤ化イメージエンコードシステムを示すブロック図である。
【図２】ウェーブレットの計算ステップ例の図である。
【図３】いくつかのピクセルが欠損している場合のウェーブレットの計算ステップ例を示す図である。
【図４】マスクウェーブレット（ｍａｓｋｅｄ  ｗａｖｅｌｅｔ）の計算ステップ例を示す図である。
【図５】本発明の一態様による分割されたレイヤ化イメージデコードシステムを示すブロック図である。
【図６】本発明の一態様による文書イメージサンプルの図である。
【図７】本発明の一態様による分割されたレイヤ化イメージエンコードシステムを示すブロック図である。
【図８】本発明の一態様による分割されたレイヤ化イメージデコードシステムを示すブロック図である。
【図９】本発明の一態様による文書のエンコード方法を示す流れ図である。
【図１０】本発明の一態様による文書のデコード方法を示す流れ図である。
【図１１】本発明により構成されているシステムの動作環境例の概略ブロック図である。
【図１２】本発明による通信環境例の概略ブロック図である。
【符号の説明】
１００  レイヤ化イメージエンコードシステム
１０２  マスクセパレータ
１０４  前景背景セグメンタ
１０６  マスクエンコーダ
１０８  前景エンコーダ
１１０  背景エンコーダ
１１２  組合せコンポーネント
５０２  セパレータコンポーネント
５０４  前景デコーダ
５０６  背景デコーダ
５０８  マスクデコーダ
５１０  コンバイナ
６０１  文書イメージ
６０２  テキスト情報
６０３、６０４  イメージ情報
６０５  背景
６１０  マスク
６１１  前景イメージ
６０２  背景イメージ
７０２  カラースペースコンポーネント
７０４  マスクセパレータ
７０６  マスクプロセッサコンポーネント
７０８  雑音除去コンポーネント
７１０  ディザ検出器
７１２  クラスタ化コンポーネント
７１４  ＯＣＲコンポーネント
７１６  レイアウト分析コンポーネント
７１８  マスクエンコーダ
７１９  前景背景セグメンタ
７２０  膨張処理コンポーネント
７２１  画像修正コンポーネント
７２２  前景ピクセルフィラー
７２４  前景ダウンサンプルコンポーネント
７２６  前景エンコーダ
７３０  背景ピクセルフィラー
７３２  背景ダウンサンプルコンポーネント
７３４  背景エンコーダ
８０２  セパレータコンポーネント
８０４  前景デコーダ
８０６  背景デコーダ
８０８  マスクデコーダ
８１０  リフローコンポーネント
８１２  コンバイナ
１１１０  コンピューティング環境
１１１２  コンピュータ
１１１４  処理装置
１１１６  システムメモリ
１１１８  システムバス
１１２０  読み取り専用メモリ（ＲＯＭ）
１１２２  ランダムアクセスメモリ（ＲＡＭ）
１１２４  ハードディスクドライブ
１１２６  磁気ディスクドライブ
１１２８  取り外し可能ディスク
１１３０  光ディスクドライブ
１１３２  ＣＤ−ＲＯＭディスク
１１３４  ハードディスクドライブインタフェース
１１３６  磁気ディスクドライブインタフェース
１１３８  光ドライブインタフェース
１１４０  オペレーティングシステム
１１４２  アプリケーションプログラム
１１４４  プログラムモジュール
１１４６  プログラム非割り込みデータ
１１４８  キーボード
１１５０  マウス
１１５２  シリアルポートインタフェース
１１５４  モニタ
１１５６  ビデオアダプタ
１１５８  リモートコンピュータ
１１６０  メモリ記憶装置
１１６２  ローカルエリアネットワーク（ＬＡＮ）
１１６４  ワイドエリアネットワーク（ＷＡＮ）
１１６６  アダプタ
１１６８  モデム
１２００  コンピューティング環境例
１２３０  サーバ
１２４０  サーバデータ記憶装置
１２５０  通信フレームワーク
１２６０  クライアントデータ記憶装置
【図１】
0004773678.tif 000028
【図２】
0004773678.tif 000029
【図３】
0004773678.tif 000030
【図４】
0004773678.tif 000031
【図５】
0004773678.tif 000032
【図６】
0004773678.tif 000033
【図７】
0004773678.tif 000034
【図８】
0004773678.tif 000035
【図９】
0004773678.tif 000036
【図１０】
0004773678.tif 000037
【図１１】
0004773678.tif 000038
【図１２】
0004773678.tif 000039