(57)【特許請求の範囲】
【請求項１】
文書画像の領域についてのピクセルエネルギー計算を実行するピクセルエネルギーコンポーネントであって、当該領域についてのエネルギー計算は、領域の多項式回帰処理を有し、さらに、前景と背景のうちの少なくとも一方のピクセルエネルギーの最小化処理を有する前記領域の分割（ｐａｒｔｉｔｉｏｎ）を計算するピクセルエネルギーコンポーネントと、
前記文書画像の領域の対をマージする領域マージコンポーネントであって、該文書画像の領域の対をマージする処理はピクセルエネルギーの最小化を有し、前景および背景の領域の対の複数の組み合わせを評価して、最小累積エネルギーを有する組み合せの１つを選択する領域マージコンポーネントと、
前記分割に関連する情報をマスクに記憶するマスク記憶コンポーネントとを備えたことを特徴とするセグメント化階層画像システム。
【請求項２】
前記ピクセルエネルギーコンポーネントは、前記領域のピクセルエネルギー分散を計算するために、式
【数１】
0004295537.tif 000015
を利用してエネルギー分散を計算し、
上式で、Ｆは前景であり、
Ｂは背景であり、ｆ（ｘ）はピクセルの値であり、
【数２】
0004295537.tif 000016
は前記前景の平均ピクセル値であり、
【数３】
0004295537.tif 000017
は前記背景の平均ピクセル値であり、
ＮＦは前記前景にあるピクセルの数であり、
ＮＢは前記背景にあるピクセルの数であることを特徴とする請求項１に記載のセグメント化階層画像システム。
【請求項３】
前記ピクセルエネルギーコンポーネントは、前記領域のピクセルエネルギーを計算するために、式
【数４】
0004295537.tif 000018
を利用してエネルギーを計算し、
上式で、Ｆは前景であり、
Ｂは背景であり、ｆ（ｘ，ｙ）は位置ｘ，ｙにおけるピクセルの値であり、
ＡＦ、ＢＦ、ＣＦは、前記前景νＦのエネルギーを最小化するように選択され、
ＡＢ、ＢＢ、ＣＢは、前記背景νＢのエネルギーを最小化するように選択される
ことを特徴とする請求項１に記載のセグメント化階層画像システム。
【請求項４】
前記領域マージコンポーネントは、２つの領域にわたる近似値ｆに基づいて、所与の領域の前景と背景の組み合わせの限定的な部分集合を評価し、累積エネルギーの最も小さい組み合わせを選択することを特徴とする請求項１に記載のセグメント化階層画像システム。
【請求項５】
請求項１に記載の前記セグメント化階層画像システムを利用することを特徴とする写真複写機。
【請求項６】
請求項１に記載の前記セグメント化階層画像システムを利用することを特徴とする文書スキャナ。
【請求項７】
請求項１に記載の前記セグメント化階層画像システムを利用することを特徴とする光学文字認識システム。
【請求項８】
請求項１に記載の前記セグメント化階層画像システムを利用することを特徴とするパーソナルディジタルアシスタント。
【請求項９】
請求項１に記載の前記セグメント化階層画像システムを利用することを特徴とするファクス機。
【請求項１０】
請求項１に記載の前記セグメント化階層画像システムを利用することを特徴とするディジタルカメラ。
【請求項１１】
請求項１に記載の前記セグメント化階層画像システムを利用することを特徴とするディジタルビデオカメラ。
【請求項１２】
請求項１に記載の前記セグメント化階層画像システムを利用することを特徴とするビデオゲームシステム。
【請求項１３】
セグメント化階層画像システムで利用されるマスク生成方法であって、
領域についてのピクセルエネルギーを前記領域の多項式回帰を使用して計算するステップと、
前記領域の前景と背景のうちの少なくとも一方の計算されたピクセルエネルギーを使用して前記領域を分割するステップと、
２つの前記領域の前景および背景の組み合わせを評価して、最小累積エネルギーを有する組み合わせの１つを選択することにより、前記前景と前記背景のうちの少なくとも一方のエネルギーの最小化処理に基づいて隣接する領域の対をマージするステップと、
前記分割の情報をマスクに記憶するステップと
を備えることを特徴とする方法。
【請求項１４】
前記領域についてのピクセルエネルギーを計算するステップはさらに、
前景についてのピクセル値の和を計算するステップと、
背景についてのピクセル値の和を計算するステップと、
前記領域中のほぼすべてのピクセルについて距離の２乗の和を計算するステップと
を備えることを特徴とする請求項１３に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般に文書画像処理に関し、より詳細には、文書画像の前景を背景から分割するマスクを利用して文書画像の圧縮を容易にするシステムおよび方法に関する。
【０００２】
【従来の技術】
コンピュータネットワーク、インターネット、およびディジタル記憶手段が広く普及するなかで、コンピュータを介して入手可能な情報の量は劇的に増加してきた。情報量の増加に伴い、情報を迅速に伝送し効率的に記憶する必要が生じている。データ圧縮は、文書をより効果的に伝送および／または記憶することのできる方法の一つである。
【０００３】
従来のデータ圧縮システムは、例えばシンボルマッチングなど様々な圧縮手法を利用してきた。しかし、画像を有する文書に対して効果的に作用する通常の圧縮手法は、例えばテキストおよび／または手書きを有する文書に対してはうまく作用しない。
【０００４】
データ圧縮は、情報を表すのに必要な空間を削減する。圧縮はどんなタイプの情報にも用いることができる。しかし、画像、テキスト、オーディオ、ビデオを含めたディジタル情報の圧縮がより重要になりつつある。通常、データ圧縮は標準的なコンピュータシステムで用いられる。ただし、限定しないが、ディジタルおよび衛星テレビジョン、ならびにセルラー／ディジタルホンなど、他の技術でもデータ圧縮を利用する。
【０００５】
データ圧縮はいくつかの理由で重要である。データ圧縮により、未圧縮データの場合よりも小さい空間に情報を記憶することができる。多量の情報に対する需要が増大するなかで、多量の情報を供給するためにデータ圧縮が必要とされることがある。記憶デバイスのサイズは著しく増大したが、情報に対する需要はこれらの増大を追い越している。例えば、未圧縮画像が５メガバイトの空間を占めるのに対して、同じ画像を圧縮すれば２．５メガバイトの空間しか占めないことがあり得る。さらに、データ圧縮により、未圧縮情報よりも多量の圧縮情報を転送することができる。ブロードバンド、ＤＳＬ、ケーブルモデムインターネットなど転送レートは上昇したものの、未圧縮情報では容易に伝送限度に達してしまう。例えば、ＤＳＬ回線を介して未圧縮画像を送信すれば１０分かかるとする。しかしデータを圧縮すれば、同じ画像を約１分で送信することができる。
【０００６】
一般に、圧縮にはロスレスとロッシーの２つのタイプがある。ロスレス圧縮では、圧縮後に正確な元データを復元することができるが、ロッシー圧縮では、元データは圧縮解除されたデータと異なる。ロッシー圧縮は、元データからデータを省くことができるので、より高い圧縮率が可能である。ロスレス圧縮は、例えばクリティカルなテキストを圧縮するときに用いることができる。というのは、データを正確に再構築できなければテキストの品質および可読性に重大な影響が及ぶ可能性があるからである。ロッシー圧縮は、ある程度のひずみまたはノイズが許容可能かまたは我々の限られた感覚で感知できない、画像またはクリティカルでないテキストに用いることができる。
【０００７】
データ圧縮は、ディジタル文書に特に適用できる。ディジタル文書または文書画像は、文書のディジタル表現である。ディジタル文書は通常、テキスト、画像、および／または、テキストと画像を含む。現行のディジタルデータのために使用される記憶空間がより少なくなることに加えて、品質を著しく劣化させずにコンパクトに記憶することは、現行のハードコピーのディジタル化を奨励することになり、ペーパーレスオフィスがより実現可能なものになる。ペーパーレスオフィスは、情報へのアクセスを容易にすることや、環境コストの削減、保管コストの削減など多くの利益をもたらすので、このようなペーパーレスオフィスに向けて努力することはビジネスが掲げるべき重要な目標である。さらに、圧縮によってディジタル文書のファイルサイズを縮小することにより、インターネット帯域幅をより効率的に使用することができ、したがって、より多くの情報をより速く伝送し、ネットワーク輻輳を低減することができる。情報のための所要の記憶装置を縮小すること、効率的なペーパーレスオフィスへの動向、およびインターネット帯域幅効率の向上は圧縮技術の多数の著しい利益のほんの一部である。
【０００８】
【発明が解決しようとする課題】
ディジタル文書のデータ圧縮は、ディジタル文書の利用をより魅力あるものにするためのいくつかの目標を有する。第１に、データ圧縮は、短時間で多量の情報を圧縮および圧縮解除できるべきである。第２に、データ圧縮はディジタル文書を正確に再生できるべきである。
【０００９】
加えて、ディジタル文書のデータ圧縮は、文書の目的を利用すべきである。ディジタル文書には、ファイリングやハードコピー提供に使用されるものもあり、校訂および／または編集されるものもある。現行のデータ圧縮では、テキストおよび／または画像が閲覧されるときの還流に対処することができず、圧縮技術によって文字を認識してそれらをワードプロセッサ、パーソナルディジタルアシスタント（ＰＤＡ）、セルラーホンなどに還流できるようにするための効率的かつ効果的な手段を提供することができない。したがって、ハードコピーのオフィス文書をスキャンしてディジタル形式にした場合、現行の圧縮技術では、不可能とは言わないまでも、ディジタル化された文書の更新、修正、またはより一般的に変更が、困難になる可能性がある。
【００１０】
【課題を解決するための手段】
以下、本発明のいくつかの態様に関する基本的な理解を提供するために、本発明の簡単な概要を提示する。この概要は本発明の広範な概観ではない。これは、本発明の鍵となる／クリティカルな要素を識別するものではなく、本発明の範囲を述べるものでもない。この概要の唯一の目的は、本発明のいくつかの概念を、後で提示するより詳細な説明の前置きとして簡単な形で提示することである。
【００１１】
本発明は一般に、文書画像の前景を背景から分割するマスクを利用して文書画像の圧縮を容易にするシステムおよび方法に関する。本発明の一態様によれば、マスクセパレータコンポーネントが、文書画像（例えば文書のバイナリ、ＲＧＢ、および／またはＹＵＶ表現）を入力として受け取る。マスクセパレータコンポーネントは、文書画像を処理し、文書画像の各ピクセルが前景および／または背景に属するかを示すマスク（例えばバイナリ）を出力する。前景（例えばテキスト情報）を背景（例えばグラフィカル情報）と分離することにより、前景および／または背景をより効果的に圧縮することができ、したがってファイルサイズおよび／または送信時間を縮減することができる。次いで、マスクおよび／または文書画像は、圧縮システムの他の部分によって処理することができる（例えば文書画像圧縮の向上を達成するため）。例えば、本発明のシステムおよび／または方法は、テキスト、手書き、ドローイングなどの識別および／または圧縮を容易にするセグメント化階層画像システム全体において利用することができる。
【００１２】
本発明の特定の一態様によれば、マスクセパレータコンポーネントは、ピクセルエネルギーコンポーネント、領域マージコンポーネント、およびマスク記憶コンポーネントを含む。ピクセルエネルギーコンポーネントは、前景および／または背景のエネルギー分散を最小化するように文書画像の領域についてピクセルエネルギー（例えば分散）を計算するように適合される。エネルギー（例えば距離の２乗の和に基づくエネルギー尺度）を、前景および／または背景について得られるであろう圧縮の推定値として用いる。ただし、計算オーバーヘッドを単純化するために、文書画像は領域（例えば２ピクセル×２ピクセル）に分割することができ、領域ごとに前景および／または背景を決定する（例えば前景および／または背景中のエネルギー分散の最小化に少なくとも一部基づいて）。言い換えれば、各領域自体が２つのセット、すなわち前景に属するピクセルと背景に属するピクセルとに分割される。計算オーバーヘッドをさらに最小限に抑えるために、ピクセルエネルギーコンポーネントは計算情報を、領域マージコンポーネントおよび／またはマスク記憶コンポーネントによって使用されるように少なくとも一時的に記憶しておくことができる。
【００１３】
領域マージコンポーネントは、マージできそうな領域の新しい前景および／または新しい背景のエネルギーが第１のしきい値エネルギー未満であるかどうかの決定に少なくとも部分的に基づいて、文書画像の領域の対をマージしてみるように適合される。領域マージコンポーネントは、ピクセルエネルギーコンポーネントによって記憶された計算情報を利用することができる。マージの結果、より広い領域が得られ、この領域はそれ自体の前景背景の分割を特徴として有することになる。マージ前に前景だったピクセルが、マージ後の領域の背景になる可能性があり、その逆の可能性もある。領域マージコンポーネントは、例えば新しい背景および新しい前景のエネルギーの最小化に、少なくとも部分的に基づいて、マージ領域の適した前景および／または背景の分割を決定することができる。
【００１４】
領域マージコンポーネントは、しきい値エネルギーを超えることになるまで、かつ／または文書画像がほぼすべてマージされるまで、連続的により大きい領域をマージしてみることを継続することができる。例えば領域マージコンポーネントは、水平方向に隣接する２×２の領域を２×４の領域にマージすることができる。その後、領域マージコンポーネントは、領域を４×４の領域に垂直方向にマージすることができる。一般に、第１のしきい値エネルギーの値は、試みられるマージによっていくつかのグレーレベルが前景または背景に分割されて、テキストなどの重要な詳細が失われる可能性があるという、潜在的状況を緩和するように選択することができる（例えば３色以上の色が領域中にあるとき）。したがって、文書画像に関連するテキストおよび／またはグラフィックラインの大部分を取り込むマスクを捕えることができる。
【００１５】
ある領域に対するマージが完了すると、この領域についての前景背景の分割がマスクを構成する。例えば、前景に属するピクセルにはマスク中で「１」を割り当て、背景に属するピクセルには「０」を割り当てることができる。残念ながら、マージ操作中に前景と背景の分割を追跡することは、計算コストが高くなる可能性がある。別法（例えばより計算的に効果的な方法）は、マージ領域のほぼすべてのピクセルの平均値を計算して、平均値よりも大きいグレーレベル値を有するピクセルを前景に割り当て、残りのピクセルを背景に割り当てるものである。あるいは、平均値よりも大きいグレーレベル値を有するピクセルを背景に割り当て、残りのピクセルを前景に割り当てることもできる。この２つの別法は、視覚識別できないマスクをもたらすことができる。
【００１６】
その後、マスク記憶コンポーネントは、前景と背景の分割に関連する情報をマスクに記憶するように適合される。したがってマスクは、文書画像の各ピクセルが前景および／または背景に属するかを示す。
【００１７】
本発明の別の態様によれば、計算オーバーヘッドを最小限に抑えるために、小さい領域（例えば４ピクセル×４ピクセル）についてのエネルギーをピクセルエネルギーコンポーネントによって計算することができる。エネルギーが第２のしきい値エネルギー未満である場合は、ほぼすべてのピクセルを前景または背景に割り当て、他方はほぼ空とすることができる。エネルギーが第２のしきい値以上である場合は、前述のように分割を進めることができる。比較的クリーンな文書画像（例えば一定の領域を有するもの）の場合、計算速度の著しい向上を達成することができる。
【００１８】
本発明の別の態様によれば、マスクのサイズを最小限に抑えるために、最終的な領域（例えば第１のしきい値を超えずにマージすることができない領域）の平均前景と平均背景との間の差が第３のしきい値よりも大きい場合、その領域の大域平均値が中間グレーレベル値（例えばグレーレベル値が０から２５５までであれば１２７）よりも高いか低いかに応じて、その領域全体を前景としてまたは背景として宣言する。わずかなディザリングのあるカラー文書では、これらの領域のためのマスクは、この最適化を行わない場合は霜降り状に見えることになり、圧縮コストが高くなる。第３のしきい値は、重要なテキストを失わず、しかも印刷文書をスキャンする際に見られるわずかなディザリングの多くのケースを除去するように選択される（例えば、多くのプリンタは４色から６色しか有さず、完全なカラーパレットを生成するにはディザリングを用いなければならない）。一例では、第３のしきい値には４０の値が適切な選択である。
【００１９】
本発明の別の態様は、ピクセルエネルギーコンポーネントが多項式回帰を利用して前景および／または背景を記述することができるようにする。
【００２０】
本発明の別の態様は、マスクセパレータコンポーネントと前景／背景セグメンタとを有する文書画像分離システムを提供する。マスクセパレータコンポーネントは、文書画像（例えばテキストおよび／または手書きを含む）を処理し、どのピクセルが前景にありどのピクセルが背景にあるかに関する情報をマスクに記憶することができる。その後、前景／背景セグメンタがマスクおよび文書画像を受け取り、文書画像を前景画像と背景画像とに分離することができる。
【００２１】
本発明の別の態様によれば、文書画像変換コンポーネントと、マスク分離コンポーネントと、前景／背景分離コンポーネントとを有する文書画像圧縮システムが提供される。任意選択で、文書画像圧縮システムは、マスクエンコーダ、前景エンコーダ、および／または背景エンコーダを含むこともできる。
【００２２】
本発明の別の態様は、ピクセルエネルギーコンポーネントとマスク記憶コンポーネントとを有するセグメント化階層画像システムを提供する。セグメント化階層画像システムは、多くの文書画像適用例で採用することができ、限定しないがこれらの適用例には、写真複写機、文書スキャナ、光学文字認識システム、パーソナルディジタルアシスタント、ファクス機、ディジタルカメラ、ディジタルビデオカメラ、および／またはビデオゲームシステムが含まれる。
【００２３】
本発明の他の態様は、マスクを生成するための方法、方法体系と、マスク分離コンポーネントに対するコンピュータ使用可能命令を有するコンピュータ可読媒体と、マスクに関連する情報を含み２つ以上のコンピュータプロセス間で伝送されるように適合されたデータパケットとを提供する。マスクは、ピクセルを文書画像の前景と背景のうちの少なくとも一方に割り当てる。マスクは、文書画像の領域におけるピクセルのエネルギーを最小化する計算に少なくとも部分的に基づく。
【００２４】
以上および関連の目的を達成するために、本発明の例示的ないくつかの態様について、後続の説明および添付の図面との関連で本明細書に述べる。ただしこれらの態様は、本発明の原理を採用することのできる様々な方法のほんのわずかを示すものに過ぎず、本発明は、このような態様およびその均等物をすべて含むものとする。本発明の他の利点および新規な特徴は、後続の本発明の詳細な説明を図面と共に考察すれば明らかになるであろう。
【００２５】
【発明の実施の形態】
ここで本発明について図面を参照しながら述べるが、各図面を通して、同じ要素を指す場合は同じ参照番号を使用する。以下の記述では、説明の目的で、本発明の完全な理解を提供するために様々な具体的詳細について述べる。ただし、本発明はこれらの具体的詳細がなくても実施できることは明白であろう。その他の場合では、本発明の記述を容易にするために、周知の構造およびデバイスはブロック図の形で示す。
【００２６】
本明細書では、「コンポーネント」および「システム」という語は、コンピュータに関係するエンティティを指すものとし、ハードウェア、ハードウェアとソフトウェアの組合せ、ソフトウェア、または実行中のソフトウェアとする。例えば、限定しないがコンポーネントは、プロセッサ上で稼動するプロセス、プロセッサ、オブジェクト、実行プログラム、実行のスレッド、プログラム、および／またはコンピュータとすることができる。例として、サーバ上で稼動するアプリケーションもサーバも両方ともコンポーネントとすることができる。１つまたは複数のコンポーネントが１つのプロセスおよび／または実行のスレッドにあるものとすることができ、コンポーネントは、１台のコンピュータ上に局所化してもよく、かつ／または２台以上のコンピュータ間で分散させてもよい。
【００２７】
さらに、「文書画像」は、１つまたは複数の色を含む文書のディジタル表現（例えばバイナリ（例えば黒／白）、グレースケール、および／またはカラー文書）を指すものとする。加えて、文書画像は、画像、テキスト、および／または画像付きテキストを有することができ、テキストと画像が重なっている可能性もある。文書画像は、文書をバイナリ、ＲＧＢ、および／またはＹＵＶで表現したものとすることができる。ＲＧＢ文書画像は、赤、緑、青の成分で表現される。ＹＵＶ文書画像は、Ｙで示される輝度成分とＵおよびＶで示されるクロミナンス成分とを用いて表現される。クロミナンス成分ＵおよびＶは、ＹＵＶ画像の視覚品質を著しく犠牲にすることなく、より少ないビットを使用して表すことができる。ＹＵＶ表現は一般に、ＲＧＢ表現よりもコンパクトかつ使いやすい表現である。文書画像は、「ピクセル」と一般に呼ばれるピクチャ要素を備える。文書画像は、任意の形状またはサイズの、単一ページまたは複数ページの文書に基づくものとすることができる。
【００２８】
図１を参照すると、本発明の一態様によるマスクセパレータコンポーネント１００が示されている。マスクセパレータコンポーネント１００は、文書画像１１０（例えばアーカイブおよび／または送信されることになる文書に基づくもの）を受け取る。例えば、マスクセパレータコンポーネント１００は文書圧縮システム（図示せず）の一部とすることができる。文書画像１１０は、バイナリ、ＲＧＢ、および／またはＹＵＶで表現された文書とすることができる。マスクセパレータコンポーネント１００は、文書画像１１０を処理し、文書画像１１０の各ピクセルが前景および／または背景に属するかを示すマスク１２０（例えばバイナリ）を出力する。次いで、圧縮システム（図示せず）の他の部分によってマスク１２０および／または文書画像１１０を処理して、文書画像１１０の圧縮を行うことができる。
【００２９】
しばし図２を見ると、例示的な文書画像が示してある。この文書画像は、棒に沿って文字「Ｃ」および「Ｏ」を含む。図３に、本発明の一態様による、図２の例示的な文書画像に関連するマスクを示す。図４に、本発明の一態様による、図２の例示的な文書画像と図３のマスクとに関連する背景を示す。点線は、背景「関係あり（ｃａｒｅ）」ピクセルの境界を表す。点線を構成するピクセルと、点線内のピクセルは、背景において「関係なし（ｄｏｎ’ｔ  ｃａｒｅ）」ピクセルである。というのは、文書画像が再組立てされたとき、マスクに記憶された再構築情報に少なくとも部分的に基づいて、前景が背景の上に配置されるからである。文字「Ｃ」「Ｏ」および／または棒が一定の色であり、かつ／あるいは滑らかな色遷移を有する場合、前景の効果的な圧縮は、様々な平滑化技法および／または圧縮技法の１つを用いて達成することができる。背景の効果的な圧縮は、「関係なし」ピクセルをより滑らかな遷移をもたらすピクセル値で置換することによって達成することができる。「関係なし」ピクセルを埋めるための単純なアルゴリズムの一例は、背景をローパスフィルタで処理してから重要なピクセルを復元するものである。この２つのステップを何回か繰り返した後は、「関係なし」ピクセルは滑らかな遷移をもたらす値になり、これらは小さく圧縮される。このアルゴリズムを簡単に改良したものは、超低域のローパスフィルタで開始して、繰返しごとにローパスフィルタのカット周波数を増加させるものである。同様のアルゴリズムを使用して、前景も埋めることができる。
【００３０】
図１に戻るが、マスクセパレータコンポーネント１００は、ピクセルエネルギーコンポーネント１３０、領域マージコンポーネント１４０、およびマスク記憶コンポーネント１５０を含む。
【００３１】
ピクセルエネルギーコンポーネント１３０は、文書画像１１０の領域についてピクセルエネルギー（例えば分散）を計算するように適合される。例えば、文書画像１１０がＹＵＶ表現である場合、ピクセルエネルギーコンポーネント１３０は、ＹＵＶ表現のＹ成分に基づいて、かつ／またはＹＵＶ成分の適した組合せに基づいて、ピクセルエネルギー分散を計算する。計算では、ある領域にわたって前景および背景が一定であると仮定することができる。これらの定数の周りの分散を最小化するマスク１２０を計算することが望ましい。この分散を、前景および／または背景について得られるであろう圧縮の推定値として使用する。あるいは、領域を圧縮し、ビット数を量的に測定してもよい。ただし計算オーバーヘッドは非常に高くつくことになる。したがって、分散は距離の２乗の和に基づくエネルギー尺度でもあるが、これを計算することは、圧縮後の前景および背景のサイズについての許容可能な推定である。
【００３２】
ある領域はＮ個のピクセルの集合Ｓであり、前景Ｆおよび背景Ｂは、Ｆ∪Ｂ＝ＳおよびＦ∩Ｂ＝φとなるようにＳの分割であると仮定する。ｆ（ｘ）がピクセル位置ｘ（ｘ∈Ｓ）における画像の値である場合、前景および背景の分散はそれぞれ以下のとおりである。
【００３３】
【数８】
0004295537.tif 000002
【００３４】
上式で、
【００３５】
【外１】
0004295537.tif 000003
【００３６】
は、それぞれ前景および背景の平均ピクセル値であり、ＮＦおよびＮＢは、それぞれ前景および背景にあるピクセルの数である。これらの分散は以下のように表現することもできることに留意されたい。
【００３７】
【数９】
0004295537.tif 000004
【００３８】
次に、前景および／または背景のエネルギー（例えば分散）の最小化に、少なくとも部分的に基づいて、Ｓの適した分割ＦおよびＢを、ピクセルエネルギーコンポーネント１３０によって決定する（例えば、和Ｅ＝νＦ＋νＢを最小化する）。しかし、可能性あるマスクが２Ｎ個あるので、Ｓの適した分割ＦおよびＢを見つけることは計算集約的になる可能性がある。
【００３９】
計算を単純化するために、文書画像を領域、例えば２ピクセル×２ピクセルの領域に分けることができる。しばし図５を見ると、本発明の一態様による、文書画像の２ピクセル×２ピクセルの領域が示してある。４つのピクセルは、値Ｖ１、Ｖ２、Ｖ３、Ｖ４を有する。２ピクセル×２ピクセルの各領域につき、可能性あるマスクは２４＝１６個しかない。したがって、これら２ピクセル×２ピクセルの各領域につき、１６個の組合せすべてを計算して最小エネルギーを有するものを利用することによって、Ｅ＝ＶＦ＋ＶＢを最小化する最適なＦおよびＢを見つけることが可能である。
【００４０】
しかし、文書画像はスカラー関数なので、Ｋ＝２としたＫ平均クラスタリングアルゴリズムを利用すると、値ｆ（ｘ）をソートすることができ、効率的に計算できる解が得られる。ソートされた順番がＶ１Ｖ２Ｖ３Ｖ４であると仮定すると、Ｋ＝２としたＫ平均クラスタリングアルゴリズムにより、以下のとおり３つの可能性ある分解が得られる。
潜在的前景      潜在的背景
Ｖ１              Ｖ２Ｖ３Ｖ４
Ｖ１Ｖ２            Ｖ３Ｖ４
Ｖ１Ｖ２Ｖ３        Ｖ４
【００４１】
他の組合せもほぼすべて、これと等しいかより高いエネルギーを有することがわかる。隣接しない値のグループ化よりも低い分散を有する隣接した値のグループ化が常にあるはずなので、このことは直感的にわかる。ソートの順番が異なる場合、ピクセルは常に、Ｖ１Ｖ２Ｖ３Ｖ４がソートされるように再ラベリングすることができる。３つの可能性ある前景背景の分解のうちどれが最低エネルギーをもたらすかを決定するのは、この場合単純である。重要なことに、ピクセルエネルギーコンポーネント１３０は、計算オーバーヘッドを最小限に抑えるために部分和
【００４２】
【外２】
0004295537.tif 000005
【００４３】
を記憶することができる。さらにピクセルエネルギーコンポーネント１３０は、少なくとも一時的に、ＮＦおよび／またはＮＢと共に部分和
【００４４】
【外３】
0004295537.tif 000006
【００４５】
の少なくともいくつかを記憶することもできる（例えば領域マージコンポーネント１４０および／またはマスク記憶コンポーネント１５０によって使用されるように）。
【００４６】
さらに、計算オーバーヘッドを最小限に抑えるために、小さい領域（例えば４ピクセル×４ピクセル）についてのエネルギーを計算することができる。エネルギーがしきい値量未満である場合は、これらのピクセルをすべて前景または背景に割り当て、他方は空とすることができる。エネルギーがしきい値エネルギー以上である場合は、前述のように分割を進めることができる。この分割は最適とはなり得ないものの、しきい値が十分に低ければ、悪影響は観測されない。比較的クリーンな文書画像（例えば一定の領域を有するもの）の場合、計算速度の著しい向上を達成することができる。
【００４７】
さらに、ほぼ一定である領域（例えば純粋な前景または純粋な背景）は、前景と背景を分離するマスクを計算した後で設定してもよい。例えば、平均前景と平均背景の差が、経験的に決定できる一定のしきい値（例えば、０から２５５までにわたるグレーレベルの全スケールと比較して値４０を使用することができる）未満である場合、領域全体を前景または背景に設定する（平均が０に近いか２５５に近いかに応じて）。
【００４８】
図１に戻るが、文書画像１１０を２ピクセル×２ピクセルの領域に分割した結果、ピクセルノイズを拾う可能性のあるはっきりした前景および背景を有する領域が得られる。これによってマスク１２０は霜降り状に見えることになる可能性があり、これはテキストおよび／またはグラフィックラインをマスク１２０中に取り込めるようにする目的とは相容れない。したがって、領域マージコンポーネント１４０は、マージできそうな領域の前景および／または背景のエネルギーが第１のしきい値エネルギー未満であるかどうかの決定に少なくとも部分的に基づいて、文書画像１１０の領域の対をマージしてみるように適合される。領域マージコンポーネント１４０は、ピクセルエネルギーコンポーネント１３０によって計算され記憶された部分和
【００４９】
【外４】
0004295537.tif 000007
【００５０】
をＮＦおよび／またはＮＢと共に利用することができる。
【００５１】
各マージの後でこれらの量を再計算しなければならないが、幸いこれもまた、これらの量を前景と背景の組合せに従って合計するだけで、一定時間で行われる。各分割につき、すべての領域にわたる和
【００５２】
【外５】
0004295537.tif 000008
【００５３】
は一定であり、最適な分割を選択するために計算する必要はないことに留意されたい。ただし、領域をマージしないときを判断するために、この量はまだ必要である。
【００５４】
しばし図６を見ると、前景Ｆ１および背景Ｂ１を有する第１の領域と、前景Ｆ２および背景Ｂ２を有する第２の領域との潜在的なマージが示してある。マージされる領域のエネルギーが第１のしきい値エネルギー未満であるかどうかを決定する際、領域マージコンポーネント１５０は、新しい前景および新しい背景のグループ化を計算することができる。２つの領域内のエネルギー分散には、以下のように、新しい前景および新しい背景についての可能性あるグループ化が７つある。
【００５５】
潜在マージ領域の新しい前景    潜在マージ領域の新しい背景
Ｆ１                            Ｂ１Ｆ２Ｂ２
Ｆ１Ｂ１Ｆ２                      Ｂ２
Ｆ１Ｂ２Ｆ２                      Ｂ１
Ｆ２                            Ｆ１Ｂ１Ｂ２
Ｆ１Ｆ２                          Ｂ１Ｂ２
Ｆ１Ｂ１                          Ｆ２Ｂ２
Ｆ１Ｂ２                          Ｆ２Ｂ１
【００５６】
可能性あるグループ化の少なくとも１つが、第１のしきい値エネルギー未満の背景および／または前景エネルギーをもたらす場合、領域マージコンポーネント１４０は、例えば背景および前景のエネルギー（Ｅ＝νＦ＋νＢ）の最小化に、少なくとも部分的に基づいて、マージ領域の適した前景／背景分割を決定することができる。これらのグループ化のどれも第１のしきい値エネルギー未満のエネルギーをもたらさない場合は、マージを行わず、これらの領域はこれ以上マージに向けて考慮しない。デフォルトで、Ｆ１およびＦ２を使用して前景ピクセルを計算し、Ｂ１およびＢ２を使用して背景ピクセルを計算する。
【００５７】
領域マージコンポーネント１４０は、第１のしきい値エネルギーを超えることになるまで、かつ／または文書画像１１０がほぼすべてマージされるまで、より大きい領域をマージしてみることを継続することができる。例えば領域マージコンポーネント１４０は、水平方向に隣接する２×２の領域を、図６に示すような２×４の領域にマージすることができる。その後、領域マージコンポーネント１４０は領域を、図７に示すような４×４の領域に垂直方向にマージすることができる。一般に、第１のしきい値エネルギーの値は、試みられるマージによっていくつかのグレーレベルが前景または背景に分割されて、テキストなどの重要な詳細が失われる可能性があるという、潜在的状況を緩和するように選択することができる（例えば３色以上の色が領域中にあるとき）。例えば、第１の領域には白の上にグレーで書かれたテキストがあり、第２の領域は大部分が黒である場合、この２つの領域をマージすると、グレーおよび白は得られるマージ領域の前景に入り、黒は背景に入り、したがってマスク１２０からテキスト情報がほぼすべて失われる恐れがある。しかし、２つの色が前景と背景のいずれかにマージされるときは、定数はもはやこの領域についての適切なモデルではないので、その領域についてのエネルギーが急増する。
【００５８】
さらに、得られるエネルギーを７つの組合せのほぼすべてについて計算することの別法として、前景および背景の平均値を記憶してもよく、分割は、ソートされた平均値に関して考えることができる。値Ｖ１Ｖ２Ｖ３Ｖ４のソートの場合のように、これは分割の数を３に減らす（Ｆ１Ｂ１Ｆ２Ｂ２を平均値でソートして、その順番を考慮した分割を考える）。
【００５９】
追加で、かつ／または別法として、領域マージコンポーネント１２０は、２つの領域にわたる近似値ｆに基づいて、これら所与の領域の前景と背景の組合せの限定的な部分集合を評価することもできる。領域マージコンポーネント１２０は、累積エネルギーの最も小さい組合せを選択すればよい。
【００６０】
このようなマージによってエネルギーが第１のしきい値を超えて増大することになるためにもう領域をマージできなくなれば、この領域のピクセルを前景と背景に分割することができる。このような分割はマージごとに行うこともできるが、これは計算コストが高くつくことになる。別法として、マージ領域コンポーネント１４０は、マージされた領域のほぼすべてのピクセル値の平均値を計算し、平均値よりも大きい値を有するピクセルを前景に割り当て、残りのピクセルを背景に割り当てることもできる。あるいは、平均値よりも大きい値を有するピクセルを背景に割り当て、残りのピクセルを前景に割り当てることもできる。
【００６１】
再び図１を参照するが、領域マージコンポーネント１４０によってマージし尽くされた後、マスク記憶コンポーネント１５０は、ピクセルエネルギーコンポーネント１３０および／またはマージ領域コンポーネント１４０によって行われた前景と背景の分割に関連する情報をマスク１２０に記憶するように適合される。したがってマスク１２０は、文書画像１１０の各ピクセルが前景および／または背景に属するかを示す。
【００６２】
一実施形態では、計算オーバーヘッドを最小限に抑えるために、小さい領域（例えば４ピクセル×４ピクセル）についてのエネルギーをピクセルエネルギーコンポーネント１３０によって計算することができる。エネルギーが第２のしきい値未満である場合は、ほぼすべてのピクセルを前景または背景に割り当て、他方はほぼ空とすることができる。エネルギーが第２のしきい値以上である場合は、前述のように分割を進めることができる。比較的クリーンな文書画像（例えば一定の領域を有するもの）の場合、計算速度の著しい向上を達成することができる。
【００６３】
別の例では、マスクのサイズを最小限に抑えるために、最終的な領域（例えば第１のしきい値を超えずにマージすることができない領域）の平均前景と平均背景との間の差が第３のしきい値よりも大きい場合、その領域の大域平均値が中間グレーレベル値（例えばグレーレベル値が０から２５５までであれば１２７）よりも高いか低いかに応じて、その領域全体を前景としてまたは背景として宣言する。わずかなディザリングのあるカラー文書では、これらの領域のためのマスクは、この最適化を行わない場合は霜降り状に見えることになり、圧縮コストが高くなる。第３のしきい値は、重要なテキストを失わず、しかも印刷文書をスキャンする際に見られるわずかなディザリングの多くのケースを除去するように選択される（例えば、多くのプリンタは４色から６色しか有さず、完全なカラーパレットを生成するにはディザリングを用いなければならない）。一例では、第３のしきい値には４０の値が適切な選択である。
【００６４】
マスクセパレータ１００について、前景および背景がそれぞれ概して一定であると仮定して述べた。ただし、本発明の一態様によれば、ピクセルエネルギーコンポーネント１３０により、多項式回帰を用いて前景および／または背景を記述することができる。例えば、前景および／または背景の多項式が式αｘ＋βｙ＋μの平面である場合、エネルギーは以下のように定義される。
【００６５】
【数１０】
0004295537.tif 000009
【００６６】
上式で、ｘ、ｙはピクセル位置を示し、αＦ、βＦ、μＦはνＦを最小化するスカラーであり、αＢ、βＢ、μＢはνＢを最小化するスカラーである。αＦ、βＦ、μＦは、３つの未知数および３つの方程式の線形系である量
【００６７】
【数１１】
0004295537.tif 000010
【００６８】
を用いて一定時間で解けることに留意されたい。同じくαＢ、βＢ、μＢも同様にして解くことができる。概して一定である前景および／または背景に関して上述したように、ピクセルエネルギーコンポーネント１３０は、小さい領域をエネルギー最小化に基づいて前景と背景に分割して、この領域についてのピクセルエネルギーを計算することに進む。その後、これらの小さい領域は、試みられるマージごとのエネルギー（Ｅ）の最小化に、少なくとも部分的に基づいて、領域マージコンポーネント１４０によって連続的にマージが試みられる。しかし、前景および背景を平均値でソートすることはできず、したがって７つの組合せすべてをテストして、Ｅを最小化する組合せを見つけなければならない。マージを容易にするために、前景および背景について領域ごとに式
【００６９】
【外６】
0004295537.tif 000011
【００７０】
を記憶することができる。
【００７１】
この場合もやはり計算オーバーヘッドを最小限に抑えるために、小さい領域（例えば４ピクセル×４ピクセル）についてのエネルギーをピクセルエネルギーコンポーネント１３０によって計算することができる。ただしピクセルエネルギーコンポーネント１３０は、この領域にわたる定数に基づくモデルを利用し、かつ／または多項式回帰を利用することができる。
【００７２】
追加で、かつ／または別法として、ピクセルエネルギーコンポーネント１３０は、平面回帰を用いてエネルギーを計算することもできる。前景νＦおよび背景νＢのエネルギーは以下のように定義される。
【００７３】
【数１２】
0004295537.tif 000012
【００７４】
上式で、Ｆは前景であり、Ｂは背景であり、ｆ（ｘ，ｙ）は位置ｘ，ｙにおけるピクセルの値である。さらに、ＡＦ、ＢＦ、ＣＦは、前景νＦのエネルギーを最小化するように選択され、ＡＢ、ＢＢ、ＣＢは、背景νＢのエネルギーを最小化するように選択される。例えば、前景νＦのエネルギーの最小化は、以下の方程式系（３つの未知数、３つの方程式）を解くことによって得られる。
【００７５】
【数１３】
0004295537.tif 000013
【００７６】
例えば次のようになる。
【００７７】
【数１４】
0004295537.tif 000014
【００７８】
背景νＢのエネルギーについても同様の計算を解くことができる。
【００７９】
図１は、マスクセパレータコンポーネント１００に関するコンポーネントを示す概略図だが、本明細書にコンポーネントという語を定義してあるとおり、マスクセパレータコンポーネント１００は１つまたは複数のコンポーネントとして実現できることを理解されたい。したがって、マスクセパレータコンポーネント１００を実現するように動作可能なコンピュータ実行可能コンポーネントは、本発明により、限定しないがＡＳＩＣ（特定用途向け集積回路）、ＣＤ（コンパクトディスク）、ＤＶＤ（ディジタルビデオディスク）、ＲＯＭ（読取り専用メモリ）、フロッピー（登録商標）ディスク、ハードディスク、ＥＥＰＲＯＭ（電気的消去可能かつプログラム可能な読取り専用メモリ）、およびメモリスティックを含めた、コンピュータ可読媒体に記憶できることを理解されたい。
【００８０】
以上に図示および記述した例示的なシステムに鑑みて、本発明により実現することのできる方法体系が、図８および９のフローチャートを参照することでよりよく理解できるであろう。説明を簡単にするためにこの方法体系を一連のブロックとして図示および記述するが、本発明によりいくつかのブロックは、本明細書に図示および記述するのとは異なる順番で、かつ／または他のブロックと同時に行うこともできるので、本発明はブロックの順番によって限定されないことを理解および認識されたい。さらに、本発明による方法体系を実施するために図示のブロックすべてが必要ではない場合もある。
【００８１】
本発明は、１つまたは複数のコンポーネントによって実行される、プログラムモジュールなどのコンピュータ実行可能命令の一般的なコンテキストで述べることができる。一般にプログラムモジュールは、特定のタスクを実施するか特定の抽象データ型を実装する、ルーチン、プログラム、オブジェクト、データ構造などを含む。通常、プログラムモジュールの機能は、望むなら様々な実施形態で結合または分散させることができる。
【００８２】
図８および９を見ると、本発明の一態様によるマスク生成の方法体系８００が示してある。８１０で、文書画像の一領域についてピクセルエネルギー（例えば分散）を計算する。例えば、計算されるピクセルエネルギー分散は、領域の多項式回帰に少なくとも部分的に基づくものとすることができる。さらに、計算されるピクセルエネルギー分散は、領域中のほぼすべてのピクセルについての距離の２乗の和で利用される、前景についての計算済み平均ピクセル値および背景についての計算済み平均ピクセル値を利用して計算することもできる。あるいは、計算されるピクセルエネルギー分散は、背景ピクセル値の合計と、前景ピクセル値の計算合計を利用して計算することもできる。
【００８３】
次に８２０で、前景および／または背景のピクセルエネルギーを最小化するための、領域についてのピクセル分割を計算する。ステップ８３０で、文書画像のほぼすべての領域が分割されたかどうかを判定する。８３０での判定がＮＯの場合は、処理を８１０で継続する。８３０での判定がＹＥＳの場合は、処理を８４０で継続する。
【００８４】
次に８４０で、隣接する領域の対をマージしてみる。８５０で、試みたマージによって新しい前景および／または新しい背景中でしきい値エネルギーを超えることになるかどうかを判定する。８５０での判定がＹＥＳの場合は、処理を８６０で継続する。８５０での判定がＮＯの場合は、８７０でこれらの領域をマージする。８８０で、マージされた領域の新しい前景背景の分割を計算する。８８５で、文書画像のほぼすべての領域のマージが試みられたかどうかを判定する。８８５での判定がＹＥＳの場合は、これ以上の処理は行わない。８８５での判定がＮＯの場合は、処理を８４０で継続する。
【００８５】
８６０で、文書画像のほぼすべての領域のマージが試みられたかどうかを判定する。８６０での判定がＮＯの場合は、８９０で、試みるマージの焦点を、マージされていない次の領域（例えば２ピクセル×２ピクセルの領域）に移す。８６０での判定がＹＥＳの場合は、これ以上の処理は行わない。
【００８６】
次に図１０を参照すると、本発明の一態様による文書画像分離のためのシステム１０００が示してある。システム１０００は、マスクセパレータコンポーネント１００および前景／背景セグメンタ１６０を含む。マスクセパレータ１００は、ピクセルエネルギーコンポーネント１３０、領域マージコンポーネント１４０、およびマスク記憶コンポーネント１５０を含む。
【００８７】
前述のように、本発明の一態様によれば、マスクセパレータコンポーネント１００は文書画像１１０を入力として受け取る。マスクセパレータコンポーネント１００は、文書画像を処理して、マスク１２０を出力として生成する。
【００８８】
前景／背景セグメンタ１６０は、マスク１２０および文書画像１１０を入力として受け取る。前景／背景セグメンタ１６０は、マスク１２０に少なくとも部分的に基づいて、文書画像１１０を前景画像１７０と背景画像１８０とに分離するように適合される。例えばマスク１２０中で「１」で表されるほぼすべてのピクセルは前景画像１７０に入れ、マスク１２０中で「０」で表されるほぼすべてのピクセルは背景画像１８０に入れることができる。反対に、例えばマスク１２０中で「０」で表されるほぼすべてのピクセルは前景画像１７０に入れ、マスク１２０中で「１」で表されるほぼすべてのピクセルは背景画像１８０に入れることもできる。
【００８９】
例えばマスクセパレータコンポーネント１００は、テキストを含む文書画像１１０を処理する際、ピクセル（例えばテキストに関連するもの）を前景として分離して、どのピクセルが前景にあるかに関する情報をマスク１２０に記憶することにより、文書画像１１０を処理することができる。その後、前景／背景セグメンタ１６０は、マスク１２０および文書画像１１０を受け取ることができる。前景／背景セグメンタ１６０は、文書画像１１０を前景画像１７０と背景画像１８０に分離することができる。
【００９０】
図１１を見ると、本発明の一態様による文書画像圧縮のためのシステム１１００が示してある。システム１１００は、文書画像変換コンポーネント１１１０と、マスク分離コンポーネント１００と、前景／背景セグメンタコンポーネント１６０を含む。前景／背景セグメンタ１６０は、マスク１２０および文書画像１１５０を入力として受け取る。前景／背景セグメンタ１６０は、マスク１２０に少なくとも部分的に基づいて、文書画像１１５０を前景画像１７０と背景画像１８０とに分離するように適合される。
【００９１】
図１２に示すように、システム１１００は任意選択で、マスクエンコーダ１１２０、前景エンコーダ１１３０、および／または背景エンコーダ１１４０を含むこともできる。マスク分離コンポーネント１００は、ピクセルエネルギーコンポーネント１３０、領域マージコンポーネント１４０、およびマスク記憶コンポーネント１５０を含む。任意選択で、システム１１００は、前景画像プロセッサ１１７０および／または背景画像プロセッサ１１８０を含むことができる。
【００９２】
文書画像変換コンポーネント１１１０は、文書画像１１５０を受け取り、文書画像の変換済み表現１１６０を出力するように適合される。例えば文書画像変換コンポーネント１１１０は、ＲＧＢ文書画像を受け取り、ＲＧＢ文書画像のＹＵＶ表現を出力することができる。
【００９３】
マスクエンコーダ１１２０は、マスク１２０を符号化するように適合される。例えば、マスク１２０は通常はバイナリなので、マスクエンコーダ１１２０は、従来のバイナリ圧縮技法を利用して効果的なマスク圧縮を達成することができる。マスクエンコーダ１１２０はマスクビットストリームを出力する。
【００９４】
前景エンコーダ１１３０は、前景画像１７０を符号化するように適合される。前景は、前景ピクセルおよび「関係なし」ピクセル（例えば元は背景に属していたピクセル）からなる画像である。前景画像プロセッサ１１７０を使用して、圧縮を容易にする値で「関係なし」ピクセルを埋め、改変済み前景画像を前景エンコーダ１１３０に提供することができる。例えば、前景画像１７０が概して黒色テキスト情報を含む場合は、前景画像全体が黒になるように、「関係なし」ピクセルもまた黒で埋めることができる。前景エンコーダ１１３０は、ＪＰＥＧ、ウェーブレット、または他の任意の画像圧縮アルゴリズムなど、画像圧縮に効果的な圧縮技法を利用することができる。前景エンコーダ１１３０は前景ビットストリームを出力する。
【００９５】
背景エンコーダ１１４０は、背景画像１８０を符号化するように適合される。背景は、背景ピクセルおよび「関係なし」ピクセル（例えば元は前景に属していたピクセル）からなる画像である。背景画像プロセッサ１１８０を使用して、圧縮を容易にする値で「関係なし」ピクセルを埋め、改変済み背景画像を背景エンコーダ１１４０に提供することができる。例えば、背景画像１８０が滑らかな白いページを含む場合は、背景画像全体が白になるように、テキストのあった位置にある「関係なし」ピクセルを白で埋めることができる。背景エンコーダ１１４０は、ＪＰＥＧ、ウェーブレット、または他の任意の画像圧縮アルゴリズムなど、画像圧縮に効果的な圧縮技法を利用することができる。背景エンコーダ１１４０は背景ビットストリームを出力する。
【００９６】
例えば、「関係なし」ピクセルを埋めるための単純なアルゴリズムは、画像をローパスフィルタで処理してから重要なピクセルを復元するものである。この２つのステップを何回か繰り返した後は、「関係なし」ピクセルは滑らかな遷移をもたらす値になり、これらは小さく圧縮される。このアルゴリズムを簡単に改良したものは、超低域のローパスフィルタで開始して、繰返しごとにローパスフィルタのカット周波数を増加させるものである。
【００９７】
さらに、前景エンコーダ１１３０および／または背景エンコーダ１１４０は、マスク１２０を利用して前景および／または背景の圧縮を改善することができる。本発明に関して前景と背景のうちの少なくとも一方のピクセルエネルギー分散の最小化に、少なくとも部分的に基づいて、行われる文書画像の分割に少なくとも部分的に基づくマスクを利用するエンコーダおよび／またはデコーダとしては、多くのものが企図されることを理解されたい。このようなエンコーダおよび／またはデコーダは、本発明と共に利用するのに適したものならどれも、頭記の特許請求の範囲内に含まれるものとする。
【００９８】
マスクビットストリーム、前景ビットストリーム、および／または背景ビットストリームは、単一のビットストリームに結合することができ、かつ／あるいは復号システム（図示せず）に個別に送信することができる。復号システムはマスク１２０を受け取ることができる。あるいは、復号システムは、マスク１２０を利用して、前景ビットストリームおよび／または背景ビットストリームを文書画像に再結合することができる。
【００９９】
本発明のシステムおよび／または方法は、テキスト、手書き、ドローイングなどの識別および／または圧縮を容易にするセグメント化階層画像システム全体において利用できることを理解されたい。さらに、本発明のシステムおよび／または方法は、多くの文書画像適用例で採用することができ、限定しないがこれらの適用例には、写真複写機、文書スキャナ、光学文字認識システム、ＰＤＡ、ファクス機、ディジタルカメラ、ディジタルビデオカメラ、および／またはビデオゲームシステムが含まれることを、当業者なら理解するであろう。
【０１００】
図１３を見ると、セグメント化階層画像システム１３００が示されている。システム１３００は、ピクセルエネルギーコンポーネント１３０およびマスク記憶コンポーネント１５０を含む。
【０１０１】
ピクセルエネルギーコンポーネント１３０は、文書画像の一領域のピクセルエネルギー分散を計算するように適合される。さらに、ピクセルエネルギーコンポーネント１３０は、前景と背景のうちの少なくとも一方のピクセルエネルギー分散の最小化に、少なくとも部分的に基づいて、領域の分割を計算するようにも適合される。
【０１０２】
マスク記憶コンポーネント１５０は、分割に関連する情報をマスクに記憶するように適合される。例えばシステム１３００は、多くの文書画像適用例で採用することができ、限定しないがこれらの適用例には、写真複写機、文書スキャナ、光学文字認識システム、ＰＤＡ、ファクス機、ディジタルカメラ、ディジタルビデオカメラ、および／またはビデオゲームシステムが含まれる。
【０１０３】
本発明の様々な態様に追加のコンテキストを提供するために、図１４および以下の考察で、本発明の様々な態様を実施できる適したコンピューティング環境の一つ１４１０についての簡単かつ一般的な記述を提供する。コンピューティング環境１４１０は、可能なコンピューティング環境の一つに過ぎず、本発明を採用する際に用いることのできるコンピューティング環境を限定するものではないことを理解されたい。本発明を、１つまたは複数のコンピュータ上で実行できるコンピュータ実行可能命令の一般的なコンテキストで上述したが、本発明は他のプログラムモジュールと共に、かつ／またはハードウェアとソフトウェアの組合せとして実施することもできることを理解されたい。一般にプログラムモジュールは、特定のタスクを実施するか特定の抽象データ型を実装する、ルーチン、プログラム、コンポーネント、データ構造などを含む。さらに、この発明的方法は、シングルプロセッサまたはマルチプロセッサのコンピュータシステム、ミニコンピュータ、メインフレームコンピュータ、ならびにパーソナルコンピュータ、ハンドヘルドコンピューティングデバイス、マイクロプロセッサベースのまたはプログラム可能な民生用電子機器など、他のコンピュータシステム構成でも実施できることは理解されるであろう。これらの構成はそれぞれ、１つまたは複数の関連デバイスと動作可能に結合させてもよい。例示した本発明の態様は分散コンピューティング環境で実施することもでき、その場合、いくつかのタスクは通信ネットワークを介してリンクされたリモート処理デバイスによって実施される。分散コンピューティング環境では、プログラムモジュールはローカルとリモートの両方の記憶デバイスに位置することができる。
【０１０４】
図１４に、本明細書に述べたシステムおよび方法をサポートする可能なハードウェア構成の一つを示す。スタンドアロンアーキテクチャを示してあるが、適したものならどんなコンピューティング環境を本発明により採用してもよいことを理解されたい。例えば、限定しないがスタンドアロン、マルチプロセッサ、分散、クライアント／サーバ、ミニコンピュータ、メインフレーム、スーパーコンピュータ、ディジタル、アナログを含めたコンピューティングアーキテクチャを、本発明により採用することができる。
【０１０５】
図１４を参照すると、本発明の様々な態様を実施するための例示的な環境１４１０は、コンピュータ１４１２を含む。コンピュータ１４１２は、プロセッシングユニット１４１４と、システムメモリ１４１６と、システムメモリを含めた様々なシステムコンポーネントをプロセッシングユニット１４１４に結合するシステムバス１４１８とを含む。プロセッシングユニット１４１４は、市販の様々なプロセッサのいずれかとすることができる。デュアルマイクロプロセッサおよび他のマルチプロセッサアーキテクチャをプロセッシングユニット１４１４として使用することもできる。
【０１０６】
システムバス１４１８は、市販の様々なバスアーキテクチャのいずれかを用いたメモリバスまたはメモリコントローラ、周辺バス、およびローカルバスを含めた、いくつかのタイプのバス構造のいずれかとすることができる。コンピュータメモリ１４１６は、読取り専用メモリ（ＲＯＭ）１４２０およびランダムアクセスメモリ（ＲＡＭ）１４２２を含む。ＲＯＭ１４２０には、起動中などにコンピュータ１４１２内の要素間で情報を転送する助けとなる基本ルーチンを含むＢＩＯＳ（ｂａｓｉｃ  ｉｎｐｕｔ／ｏｕｔｐｕｔ  ｓｙｓｔｅｍ）が記憶されている。
【０１０７】
コンピュータ１４１２はさらに、ハードディスクドライブ１４２４と、例えば取外し可能ディスク１４２８に対する読み書きを行うための磁気ディスクドライブ１４２６と、例えばＣＤ−ＲＯＭディスク１４３２の読取りや他の光媒体に対する読み書きを行うための光ディスクドライブ１４３０も含む。ハードディスクドライブ１４２４、磁気ディスクドライブ１４２６、および光ディスクドライブ１４３０は、それぞれハードディスクドライブインタフェース１４３４、磁気ディスクドライブインタフェース１４３６、および光ドライブインタフェース１４３８によってシステムバス１４１８に接続される。コンピュータ１４１２は通常、少なくとも何らかの形のコンピュータ可読媒体を含む。コンピュータ可読媒体は、コンピュータ１４１２からアクセスできる任意の利用可能な媒体とすることができる。限定ではなく例として、コンピュータ可読媒体には、コンピュータ記憶媒体および通信媒体が含まれる。コンピュータ記憶媒体には、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータなどの情報を記憶するための任意の方法および技術で実現される、揮発性および不揮発性の、かつ取外し可能および取外し不可能な媒体が含まれる。コンピュータ記憶媒体には、限定しないがＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたは他のメモリ技術、ＣＤ−ＲＯＭ、ディジタル多用途ディスク（ＤＶＤ）または他の磁気記憶デバイスが含まれ、あるいは、所望の情報を記憶するのに使用できコンピュータ１４１２からアクセスできる他の任意の媒体が含まれる。通信媒体は通常、搬送波や他のトランスポート機構など変調されたデータ信号中に、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータを組み入れたものであり、任意の情報送達媒体が含まれる。「変調されたデータ信号」という語は、信号中の情報が符号化される形で１つまたは複数の特性が設定または変更された信号を意味する。限定ではなく例として、通信媒体には、配線式ネットワークや直接配線式接続などの配線式媒体と、音響、ＲＦ、赤外線、その他の無線媒体などの無線媒体とが含まれる。以上の任意の組合せもコンピュータ可読媒体の範囲に含まれるべきである。
【０１０８】
各ドライブおよびＲＡＭ１４２２には、オペレーティングシステム１４４０、１つまたは複数のアプリケーションプログラム１４４２、その他のプログラムモジュール１４４４、およびプログラム非割込みデータ１４４６を含めて、いくつかのプログラムモジュールを記憶することができる。コンピュータ１４１２中のオペレーティングシステム１４４０は、多くの市販オペレーティングシステムのいずれかとすることができる。
【０１０９】
ユーザは、キーボード１４４８、およびマウス１４５０などのポインティングデバイスを介して、コンピュータ１４１２にコマンドおよび情報を入力することができる。その他の入力デバイス（図示せず）には、マイクロホン、ＩＲリモートコントロール、ジョイスティック、ゲームパッド、衛生受信アンテナ、スキャナなどを含めることができる。これらおよび他の入力デバイスは、システムバス１４１８に結合されたシリアルポートインタフェース１４５２を介してプロセッシングユニット１４１４に接続されることが多いが、パラレルポート、ゲームポート、ユニバーサルシリアルバス（「ＵＳＢ」）、ＩＲインタフェースなど、他のインタフェースで接続されてもよい。モニタ１４５４または他のタイプの表示デバイスもまた、ビデオアダプタ１４５６などのインタフェースを介してシステムバス１４１８に接続される。モニタに加えて、コンピュータは通常、スピーカやプリンタなど他の周辺出力デバイス（図示せず）も含む。
【０１１０】
コンピュータ１４１２は、リモートコンピュータ１４５８など１つまたは複数のリモートコンピュータへの論理接続および／または物理接続を用いて、ネットワーク化された環境で動作することができる。リモートコンピュータ１４５８は、ワークステーション、サーバコンピュータ、ルータ、パーソナルコンピュータ、マイクロプロセッサベースの娯楽機器、ピアデバイス、または他の一般的なネットワークノードとすることができる。簡単にするためにメモリ記憶デバイス１４６０しか示していないが、通常はコンピュータ１４１２に関して述べた要素の多くまたはすべてを含む。図示の論理接続は、ローカルエリアネットワーク（ＬＡＮ）１４６２およびワイドエリアネットワーク（ＷＡＮ）１４６４を含む。このようなネットワーキング環境は、オフィス、企業全体のコンピュータネットワーク、イントラネット、およびインターネットでよくみられるものである。
【０１１１】
コンピュータ１４１２は、ＬＡＮネットワーキング環境で使用されるときは、ネットワークインタフェースまたはアダプタ１４６６を介してローカルネットワーク１４６２に接続される。ＷＡＮネットワーキング環境で使用されるときは通常、コンピュータ１４１２はモデム１４６８を含むか、ＬＡＮ上の通信サーバに接続されるか、あるいは、インターネットなどのＷＡＮ１４６４を介した通信を確立するための他の手段を有する。モデム１４６８は内蔵でも外付けでもよく、シリアルポートインタフェース１４５２を介してシステムバス１４１８に接続される。ネットワーク化された環境では、コンピュータ１４１２に関して示したプログラムモジュールまたはその一部を、リモートのメモリ記憶デバイス１４６０に記憶することができる。図示のネットワーク接続は例示的なものであり、コンピュータ間の通信リンクを確立する他の手段を使用してもよいことは理解されるであろう。
【０１１２】
図１５は、本発明が対話することのできるコンピューティング環境の実例１５００の概略ブロック図である。システム１５００は、１つまたは複数のクライアント１５１０を含む。クライアント１５１０は、ハードウェアおよび／またはソフトウェア（例えばスレッド、プロセス、コンピューティングデバイス）とすることができる。システム１５００は、１つまたは複数のサーバ１５３０も含む。サーバ１５３０もまた、ハードウェアおよび／またはソフトウェア（例えばスレッド、プロセス、コンピューティングデバイス）とすることができる。サーバ１５３０は、例えば、本発明を利用して変換を行うためのスレッドを格納することができる。クライアント１５１０とサーバ１５３０との間における可能な通信の一つは、２つ以上のコンピュータプロセス間で伝送されるように適合されたデータパケットの形とすることができる。システム１５００は、クライアント１５１０とサーバ１５３０との間の通信を容易にするのに利用できる通信フレームワーク１５５０を含む。クライアント１５１０は、クライアント１５１０にとってローカルの情報を記憶するのに利用できる１つまたは複数のクライアントデータ記憶域１５６０に動作可能に接続される。同様に、サーバ１５３０は、サーバ１５３０にとってローカルの情報を記憶するのに利用できる１つまたは複数のサーバデータ記憶域１５４０に動作可能に接続される。
【０１１３】
以上の記述は、本発明の実施例を含む。本発明を記述するためにコンポーネントまたは方法体系の考えられるあらゆる組合せについて述べることは当然不可能だが、本発明のさらに多くの組合せおよび置換が可能であることは、当業者なら理解するであろう。したがって本発明は、頭記の特許請求の趣旨および範囲に含まれるそのような改変、修正、および変形すべてを包含するものとする。さらに、「含む」という語が詳細な説明または特許請求の範囲で使用される限りでは、このような語は、「備える」という語が特許請求の範囲における移行句として採用されるときに解釈されるように、「備える」と同様の形で包括的なものとする。
【図面の簡単な説明】
【図１】本発明の一態様によるマスクセパレータコンポーネントのブロック図である。
【図２】本発明の一態様による例示的な文書画像の図である。
【図３】本発明の一態様による、図２の例示的な文書画像に関連するマスクの図である。
【図４】本発明の一態様による、図２の例示的な文書画像および図３のマスクに関連する背景の図である。
【図５】本発明の一態様による、例示的な２ピクセル×２ピクセルの領域の図である。
【図６】本発明の一態様による、例示的な２ピクセル×４ピクセルの潜在マージ領域の図である。
【図７】本発明の一態様による、例示的な４ピクセル×４ピクセルの潜在マージ領域の図である。
【図８】本発明の一態様による、マスクを生成する方法体系を示すフローチャートである。
【図９】図８の方法体系をさらに示すフローチャートである。
【図１０】本発明の一態様による文書画像分離システムのブロック図である。
【図１１】本発明の一態様による文書画像圧縮のブロック図である。
【図１２】本発明の一態様による文書画像圧縮のブロック図である。
【図１３】本発明の一態様によるセグメント化階層画像システムのブロック図である。
【図１４】本発明の一態様により構成されたシステムのための例示的な動作環境の概略ブロック図である。
【図１５】本発明の一態様による例示的な通信環境の概略ブロック図である。
【符号の説明】
１００  マスクセパレータコンポーネント
１１０、１１５０、  文書画像
１２０  マスク
１３０  ピクセルエネルギーコンポーネント
１４０  領域マージコンポーネント
１５０  マスク記憶コンポーネント
１６０  前景／背景セグメンタコンポーネント
１７０  前景画像
１８０  背景画像
１０００  文書画像分離のためのシステム
１１１０  文書画像変換コンポーネント
１１２０  マスクエンコーダ
１１３０  前景エンコーダ
１１４０  背景エンコーダ
１１７０  前景画像プロセッサ
１１８０  背景画像プロセッサ
１３００  セグメント化階層画像システム
１４１０  適したコンピューティング環境
１４１２  コンピュータ
１４１４  プロセッシングユニット
１４１６  システムメモリ
１４１８  システムバス
１４２０  ＲＯＭ
１４２２  ＲＡＭ
１４２４  ハードディスクドライブ
１４２６  磁気ディスクドライブ
１４２８、１４３２  ディスク
１４３０  光ディスクドライブ
１４３４  ハードディスクドライブインタフェース
１４３６  磁気ディスクドライブインタフェース
１４３８  光ドライブインタフェース
１４４０  オペレーティングシステム
１４４２  アプリケーションプログラム
１４４４  プログラムモジュール
１４４６  データ
１４４８  キーボード
１４５０  マウス
１４５４  モニタ
１４５６  ビデオアダプタ
１４５２  シリアルポートインタフェース
１４５８  リモードコンピュータ
１４６０  メモリ記憶デバイス
１４６２  ＬＡＮ
１４６４  ＷＡＮ
１４６６  ネットワークアダプタ
１４６８  モデム
１５００  本発明が対話することのできるコンピューティング環境
１５１０  クライアント
１５３０  サーバ
１５４０  サーバデータ記憶域
１５５０  通信フレームワーク
１５６０  クライアントデータ記憶域
【図１】
0004295537.tif 000019
【図２】
0004295537.tif 000020
【図３】
0004295537.tif 000021
【図４】
0004295537.tif 000022
【図５】
0004295537.tif 000023
【図６】
0004295537.tif 000024
【図７】
0004295537.tif 000025
【図８】
0004295537.tif 000026
【図９】
0004295537.tif 000027
【図１０】
0004295537.tif 000028
【図１１】
0004295537.tif 000029
【図１２】
0004295537.tif 000030
【図１３】
0004295537.tif 000031
【図１４】
0004295537.tif 000032
【図１５】
0004295537.tif 000033