(57)【特許請求の範囲】
【請求項１】
スキャンされたドキュメントを含む入力デジタル画像から、２値マスク画像を作成する方法であって、
ａ）前記入力デジタル画像を２値化することによって、２値化画像を作成するステップ、
ｂ）前記入力デジタル画像内にある暗い背景に重ねられた明るいテキストを表す第１テキスト領域を、前記２値化画像において検出するステップ、
ｃ）前記２値化画像において前記第１テキスト領域を反転させるステップ、このステップで明るい背景に重ねて示された暗いテキストと同様に、反転した第１テキスト領域が判別可能となるよう、変換した２値画像を形成する、
を有し、
前記第１テキスト領域を反転させるステップは、
−所定の第１の最低値を上回る相当数の画素を有する第１の大きな黒いブロブだけを保つことにより、２値化画像から第１画像を作成するステップ、
−前記第１画像を反転するステップ、
−前記２値化画像を、反転した第１画像と組み合わせるステップ、このステップで第１の大きな黒いブロブが除去されて、第２画像が形成される、
−所定の第２の最低値を上回る相当数の画素を有する第２の大きな黒いブロブだけを保つことにより、前記反転した第１画像から第３画像を作成するステップ、
−前記第３画像を反転するステップ、
−前記反転した第１画像を、反転した第３画像と組み合わせるステップ、このステップで第２の大きな黒いブロブが除去されて、第４画像が形成される、
−前記第２画像と前記第４画像を組み合わせるステップ、このステップで前記変換した２値画像が形成される、
を含む方法。
【請求項２】
さらに、
ｄ）前記入力デジタル画像内にある明るい背景に重ねた暗いテキストを表す第２テキスト領域を、前記２値化画像において検出するステップ、
ｅ）テキストが実在しないテキスト領域を、２値化画像から取り除くステップ、を有する、請求項１に記載の方法。
【請求項３】
さらに、
前記第１および第２テキスト領域を検出するステップの前に、水平および垂直のグラフィック要素を分離するステップ、
前記検出ステップの後に、前記水平および垂直のグラフィック要素を２値化画像へと再導入するステップ、を有する、請求項２に記載の方法。
【請求項４】
前記ステップａ）は、
ａ１）前記入力デジタル画像からグレースケール画像を構築するステップ、
ａ２）前記グレースケール画像内にあるエッジを検出し、エッジ画素および非エッジ画素を含むエッジ２値画像を構築するステップ、
ａ３）周囲の画素に基づいて、前記エッジ画素のそれぞれに対するしきい値を決定するとともに、前記非エッジ画素にゼロのしきい値を与え、しきい値グレースケール画像を構築するステップ、
ａ４）周囲のしきい値に基づいて、エッジ画素に接する前記非エッジ画素のそれぞれに対するしきい値を決定するステップ、
ａ５）最高のしきい値を保つことによって前記しきい値グレースケール画像をスケーリングするステップ、
ａ６）正の値を有する画素からゼロの値を有する画素へ、しきい値を伝搬させるステップ、
ａ７）前記グレースケール画像および前記スケーリングされたしきい値グレースケール画像に基づいて、第１の２値画像を構築するステップ、を含む、請求項１から３のうちのいずれか１つに記載の方法。
【請求項５】
前記ステップａ２）は、前記エッジ検出用にキャニーエッジアルゴリズムの使用を含む、請求項４に記載の方法。
【請求項６】
前記ステップａ）は、さらに、
ａ８）前記グレースケール画像および前記しきい値グレースケール画像に基づいて、第２の２値画像を構築するステップ、
ａ９）前記第１および第２の２値画像を組み合わせることによって、前記２値化画像を構築するステップ、を含む、請求項４に記載の方法。
【請求項７】
前記入力デジタル画像は所定の解像度を有し、
前記２値マスク画像の作成は、２値マスク解像度低減係数により前記解像度を低減するステップを含む、請求項１から６のうちのいずれか１つに記載の方法。
【請求項８】
入力デジタル画像を２値化することによって得られた２値画像において、第１画素ブロブを第２画素ブロブと比較し、該第１および第２画素ブロブが一致したシンボルを表すかどうかを決定する方法であって、
ａ）第１ブロブを拡張し、第２ブロブが前記拡張された第１ブロブの内部に適合するかどうかを検査するステップ、
ｂ）第２ブロブを拡張し、第１ブロブが前記拡張された第２ブロブの内部に適合するかどうかを検査するステップ、
ｃ）もし、ステップａ）及びｂ）の検査結果が「適合する」で有れば、係る適合が誤りでないかどうかの検査を行うステップ、ここで前記検査は、非拡張第１画素ブロブに、非拡張第２画素ブロブには含まれていない線が含まれているかどうかの線チェック、また、その逆の線チェックにより行う、
を有し、
前記ステップｃ）の線チェックは、非拡張第１画素ブロブ及び非拡張第２画素ブロブの対応した位置にそれぞれ含まれる、クロス線で構成されるＮｘＮのクロス、Ｎはビット数を表す、を直接比較するステップを含み、ここで、非拡張第１画素ブロブにおいて考察される第１のＮｘＮのクロスと、非拡張第２画素ブロブにおいて考察される第２のＮｘＮのクロスは、対応した同じ位置にあり、第１のＮｘＮのクロスの２本のクロス線の一方の線の色が、第２のＮｘＮのクロスの２本のクロス線の他方の線の色と異なっている場合は「不適合」と判断する、
方法。
【請求項９】
Ｎが３である、請求項８に記載の方法。
【請求項１０】
さらに、
第１ブロブおよび第２ブロブのいずれか一つがイタリック体のシンボルを表し、他方がイタリック体のシンボルを表さないかどうかの検査をすることにより、適合が誤りであるかどうかのチェックを行うステップを有し、ここでの検査は、第１ブロブおよび第２ブロブが共有する黒色画素の数が、所定のしきい値より高いかどうかを検査することである、請求項８から９のうちのいずれか１つに記載の方法。
【請求項１１】
前記所定のしきい値は、１つのブロブ内にある画素の全量の８０から９０％に等しい、請求項１０に記載の方法。
【請求項１２】
前記スキャンされたドキュメントを含む前記入力デジタル画像を圧縮する圧縮方法であって、
ａ）前記ドキュメントの前景要素のカラー情報を含む前景画像と、前記ドキュメントの背景要素のカラー情報を含む背景画像と、前記圧縮されたデジタル画像を伸張するときに前記前景画像および前記背景画像内にある画素から選択する２値マスク画像と、を有する多数の画像層へと、前記入力デジタル画像を分割するステップ、
ｂ）適切な圧縮技術によって画像層のそれぞれを圧縮し、圧縮されたデジタル画像を得るステップ、
を有し、
ここで、２値マスク画像を作成するステップは、
−前記入力デジタル画像を２値化することによって、２値化画像を作成するステップ、
−前記入力デジタル画像内にある暗い背景に重ねられた明るいテキストを表す第１テキスト領域を、前記２値化画像において検出するステップ、
−前記２値化画像において前記第１テキスト領域を反転させるステップ、このステップで明るい背景に重ねて示された暗いテキストと同様に、反転した第１テキスト領域が判別可能となるよう、変換した２値画像を形成する、
を有し、
前記第１テキスト領域を反転させるステップは、
−所定の第１の最低値を上回る相当数の画素を有する第１の大きな黒いブロブだけを保つことにより、２値化画像から第１画像を作成するステップ、
−前記第１画像を反転するステップ、
−前記２値化画像を、反転した第１画像と組み合わせるステップ、このステップで第１の大きな黒いブロブが除去されて、第２画像が形成される、
−所定の第２の最低値を上回る相当数の画素を有する第２の大きな黒いブロブだけを保つことにより、前記反転した第１画像から第３画像を作成するステップ、
−前記第３画像を反転するステップ、
−前記反転した第１画像を、反転した第３画像と組み合わせるステップ、このステップで第２の大きな黒いブロブが除去されて、第４画像が形成される、
−前記第２画像と前記第４画像を組み合わせるステップ、このステップで前記変換した２値画像が形成される、
を含む方法。
【請求項１３】
前記入力デジタル画像は所定の解像度を有し、
前記前景および背景画像は、それぞれ前景解像度低減係数および背景解像度低減係数により前記解像度を低減することによって構築される、請求項１２に記載の方法。
【請求項１４】
前記ステップｂ）は、
ｂ１）画像圧縮技術によって前記前景および背景画像を圧縮するステップ、
ｂ２）シンボルに基づく圧縮技術によって前記２値マスク画像を圧縮するステップ、を含む、請求項１２または１３に記載の方法。
【請求項１５】
スキャンされたドキュメントを含む入力デジタル画像を圧縮する圧縮方法であって、
ａ）前記ドキュメントの前景要素のカラー情報を含む前景画像と、前記ドキュメントの背景要素のカラー情報を含む背景画像と、前記圧縮されたデジタル画像を伸張するときに前記前景画像および前記背景画像内にある画素から選択する２値マスク画像と、を有する多数の画像層へと、前記入力デジタル画像を分割するステップ、
ｂ）画像圧縮技術によって前記前景および背景画像を圧縮するステップ、
ｃ）シンボルに基づく圧縮技術によって前記２値マスク画像を圧縮するステップ、
を有し、
前記シンボルに基づく圧縮技術は、前記２値マスク画像にある複数の画素ブロブを比較し、シンボルのリストとシンボルの頻度のリストを作成して成され、ここで画素ブロブの比較は、
ｃ１）第１ブロブを拡張し、第２ブロブが前記拡張された第１ブロブの内部に適合するかどうかを検査するステップ、
ｃ２）第２ブロブを拡張し、第１ブロブが前記拡張された第２ブロブの内部に適合するかどうかを検査するステップ、
ｃ３）もし、ステップｃ１）及びｃ２）の検査結果が「適合する」で有れば、係る適合が誤りでないかどうかの検査を行うステップ、ここで前記検査は、非拡張第１画素ブロブに、非拡張第２画素ブロブには含まれていない線が含まれているかどうかの線チェック、また、その逆の線チェックにより行う、
を有し、
前記ステップｃ３）の線チェックは、非拡張第１画素ブロブ及び非拡張第２画素ブロブの対応した位置にそれぞれ含まれる、クロス線で構成されるＮｘＮのクロス、Ｎはビット数を表す、を直接比較するステップを含み、ここで、非拡張第１画素ブロブにおいて考察される第１のＮｘＮのクロスと、非拡張第２画素ブロブにおいて考察される第２のＮｘＮのクロスは、対応した同じ位置にあり、第１のＮｘＮのクロスの２本のクロス線の一方の線の色が、第２のＮｘＮのクロスの２本のクロス線の他方の線の色と異なっている場合は「不適合」と判断する、
方法。
【請求項１６】
前記入力デジタル画像は所定の解像度を有し、
前記２値マスク画像の作成は、２値マスク解像度低減係数により前記解像度を低減するステップを含む、請求項１５に記載の方法。
【請求項１７】
前記入力デジタル画像は所定の解像度を有し、
前記前景および背景画像は、それぞれ前景解像度低減係数および背景解像度低減係数により前記解像度を低減することによって構築される、請求項１５または１６に記載の方法。
【請求項１８】
コンピュータのメモリへと、直接にロード可能なコンピュータプログラムあって、
コンピュータに実行させる手順として、
ａ）前記ドキュメントの前景要素のカラー情報を含む前景画像と、前記ドキュメントの背景要素のカラー情報を含む背景画像と、前記圧縮されたデジタル画像を伸張するときに前記前景画像および前記背景画像内にある画素から選択する前記２値マスク画像と、を有する多数の画像層へと、前記入力デジタル画像を分割する手順、
ｂ）適切な圧縮技術によって画像層のそれぞれを圧縮し、圧縮されたデジタル画像を得る手順、
を含み、
ここで、２値マスク画像を作成する手順は、
−前記入力デジタル画像を２値化することによって、２値化画像を作成する手順、
−前記入力デジタル画像内にある暗い背景に重ねられた明るいテキストを表す第１テキスト領域を、前記２値化画像において検出する手順、
−前記２値化画像において前記第１テキスト領域を反転させる手順、この手順で明るい背景に重ねて示された暗いテキストと同様に、反転した第１テキスト領域が判別可能となるよう、変換した２値画像を形成する、
を含み、
前記第１テキスト領域を反転させる手順は、
−所定の第１の最低値を上回る相当数の画素を有する第１の大きな黒いブロブだけを保つことにより、２値化画像から第１画像を作成する手順、
−前記第１画像を反転する手順、
−前記２値化画像を、反転した第１画像と組み合わせる手順、この手順で第１の大きな黒いブロブが除去されて、第２画像が形成される、
−所定の第２の最低値を上回る相当数の画素を有する第２の大きな黒いブロブだけを保つことにより、前記反転した第１画像から第３画像を作成する手順、
−前記第３画像を反転する手順、
−前記反転した第１画像を、反転した第３画像と組み合わせる手順、この手順で第２の大きな黒いブロブが除去されて、第４画像が形成される、
−前記第２画像と前記第４画像を組み合わせる手順、この手順で前記変換した２値画像が形成される、
を含むプログラム。
【請求項１９】
請求項１８に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項２０】
コンピュータのメモリへと、直接にロード可能なコンピュータプログラムであって、
コンピュータに実行させる手順として、
ａ）前記ドキュメントの前景要素のカラー情報を含む前景画像と、前記ドキュメントの背景要素のカラー情報を含む背景画像と、前記圧縮されたデジタル画像を伸張するときに前記前景画像および前記背景画像内にある画素から選択する２値マスク画像と、を有する多数の画像層へと、前記入力デジタル画像を分割する手順、
ｂ）画像圧縮技術によって前記前景および背景画像を圧縮する手順、
ｃ）シンボルに基づく圧縮技術によって前記２値マスク画像を圧縮する手順、
を含み、
前記シンボルに基づく圧縮技術は、前記２値マスク画像にある複数の画素ブロブを比較し、シンボルのリストとシンボルの頻度のリストを作成して成され、ここで画素ブロブの比較は、
ｃ１）第１ブロブを拡張し、第２ブロブが前記拡張された第１ブロブの内部に適合するかどうかを検査する手順、
ｃ２）第２ブロブを拡張し、第１ブロブが前記拡張された第２ブロブの内部に適合するかどうかを検査する手順、
ｃ３）もし、手順ｃ１）及びｃ２）の検査結果が「適合する」で有れば、係る適合が誤りでないかどうかの検査を行う手順、ここで前記検査は、非拡張第１画素ブロブに、非拡張第２画素ブロブには含まれていない線が含まれているかどうかの線チェック、また、その逆の線チェックにより行う、
を有し、
前記手順ｃ３）の線チェックは、非拡張第１画素ブロブ及び非拡張第２画素ブロブの対応した位置にそれぞれ含まれる、クロス線で構成されるＮｘＮのクロス、Ｎはビット数を表す、を直接比較する手順を含み、ここで、非拡張第１画素ブロブにおいて考察される第１のＮｘＮのクロスと、非拡張第２画素ブロブにおいて考察される第２のＮｘＮのクロスは、対応した同じ位置にあり、第１のＮｘＮのクロスの２本のクロス線の一方の線の色が、第２のＮｘＮのクロスの２本のクロス線の他方の線の色と異なっている場合は「不適合」と判断する、
プログラム。
【請求項２１】
請求項２０に記載のプログラムを記載したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、スキャンされたドキュメントを含む入力デジタル画像を圧縮する、方法、アルゴリズム、およびコンピュータで読み取り可能なプログラム製品に関する。
【背景技術】
【０００２】
ＩＴＵ−Ｔ（国際通信連合の電気通信標準化部門）は、勧告Ｔ．４４において、ミクストラスターコンテント（Ｍｉｘｅｄ  Ｒａｓｔｅｒ  Ｃｏｎｔｅｎｔ：ＭＲＣ）モデルを規定した。このモデルを用いることによって、カラーおよびグレースケールドキュメント画像を、高圧縮レートで、テキストが視認性よく、写真が良好な描写で、圧縮することが可能となる。ＭＲＣモデルは、ドキュメント画像を、２値マスク層、前景層、および背景層の３層に分割する。マスク層は２値画像であり、背景および前景層はカラー（またはグレースケール）画像である。２値マスク層内にあるオン画素は、伸張時にカラー（またはグレースケール）が前景層から取り除かれなければならないことを示す。２値マスク層内にあるオフ画素は、伸張時にカラー（またはグレースケール）が背景層から取り除かれなければならないことを示す。しかしながら、ＩＴＵ−Ｔ  Ｔ．４４は、層への分割方法を特定してはいない。
【０００３】
米国特許第５，７７８，０９２号明細書によると、ＭＲＣモデルに対応して、ドキュメントを表すカラーまたはグレースケール画素マップを圧縮する最初の技術が開示されている。画素マップは、低減された解像度の前景プレーン、低減された解像度の背景プレーン、および高解像度の２値プレーンセレクタを有する３枚のプレーン表現に分解される。前景プレーンは、テキストおよびグラフィック要素などの、前景品目のカラーまたはグレースケール情報を含む。背景プレーンは、そのページおよびそのページに含まれる連続階調写真の「背景」のカラーまたはグレースケール情報を含む。プレーンセレクタは、伸張の間に、前景プレーンまたは背景プレーンのうちのいずれか一方から選択する情報を記憶する。各プレーンは、対応するデータタイプに対する適切な圧縮技術を用いて圧縮される。
【０００４】
米国特許第６，７３１，８００号明細書によると、スキャンされたカラーおよびグレースケールドキュメントを圧縮する別の技術が開示されており、スキャンされたドキュメントのデジタル画像は、３枚の画像プレーン、すなわち前景画像、背景画像、および２値マスク画像に分割される。マスク画像は、ドキュメントの領域が前景に属すること、および背景に属することを記述する。マスク画像を生成するために、適応的しきい値方法により規定されたやり方で低減された元ドキュメントから、局所的に変化可能なしきい値画像が生成され、元ドキュメントのサイズにもう一度戻る。この技術により、さらに反転テキスト（暗い背景上の明るいテキスト）が検出されることが可能となる。反転テキストは、「穴」の概念によって検出される。「穴」は、前景領域、またはすでに入力された別の前景領域に接するブロブである。この方法は、すべてのブロブが追跡されなければならないので、大量のメモリを必要とし、ブロブが互いに接する場合に検査されなければならないので、多大な時間を必要とする。加えて、「黒色」ブロブおよび「白色」ブロブの両方が記録されなければならない。
【０００５】
米国特許第６，７４８，１１５号明細書によると、グレーレベルデジタル画像入力を、弱い接続性を最小化する２レベル入力へ変換するグレーレベルしきい値を選択するために用いる画像圧縮技術が開示されており、弱い接続性は、２×２の配列または複数画素の近傍に含まれている市松模様を有している。変換用のしきい値は、単一のパスにおいてドキュメントを有する複数画素の配列を横切り、連続する２×２近傍を分析し、最初に市松模様が現れるグレーレベル値に対してプラスレジスタを増分し、市松模様がもはや存在しないグレーレベル値に対してマイナスレジスタを増分することによって決定される。
【０００６】
しかしながら、これらの画像圧縮技術の不利な点は、達成される圧縮レートが不十分なことである。さらにしばしば、再構成された画像品質、たとえばテキストの視認性または写真の描写が、圧縮技術によって影響される。
【０００７】
米国特許第５，８３５，６３８号明細書によると、同値類へ分類するテキストの２値画像から抽出されたシンボルを比較する方法および装置が開示されている。ハウスドルフ（Ｈａｕｓｄｏｒｆｆ）類似の方法が、類似のシンボルを比較するために使用される。ビットマップＡに含まれるシンボルが、ビットマップＢに含まれるシンボルと比較される場合、ビットマップＢのシンボルが、過度の誤差密度にならずに、ビットマップＡのシンボルの拡張表現へと、許容範囲内に適合するかどうか、およびビットマップＡのシンボルが、過度の誤差密度にならずに、ビットマップＢのシンボルの拡張表現へと、許容範囲内に適合するかどうかが決定される。両方のテストに通った場合、誤差密度検査が実行され、一致を決定する。
【０００８】
この公知のシンボル比較方法の不利な点は、多くの場合、実際に不一致が発生する場所に、一致が返されてもよいことである。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】米国特許第５，７７８，０９２号明細書
【特許文献２】米国特許第６，７３１，８００号明細書
【特許文献３】米国特許第６，７４８，１１５号明細書
【特許文献４】米国特許第５，８３５，６３８号明細書
【非特許文献】
【００１０】
【非特許文献１】Ｊ．キャニー「エッジ検出に対するコンピュータによるアプローチ」米国電気電子学会、パターン解析および人工知能に関する会報（Ｊ．Ｃａｎｎｙ、「Ａ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ａｐｐｒｏａｃｈ  ｔｏ  Ｅｄｇｅ  Ｄｅｔｅｃｔｉｏｎ」、ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｐａｔｔｅｒｎ  Ａｎａｌｙｓｉｓ  ａｎｄ  Ｍａｃｈｉｎｅ  Ｉｎｔｅｌｌｉｇｅｎｃｅ）、第８巻、６号、１１月、１９８６年
【発明の概要】
【発明が解決しようとする課題】
【００１１】
本発明の第１の目的は、必要とする時間を少なくし、メモリをさらに効率的に使用する画像２値化技術を与えることである。
【００１２】
この第１の目的は、第１の独立請求項の画像２値化技術により達成される。
【００１３】
本発明の第２の目的は、実質的に置き換えの誤差なしに、最小数のモデルクラスを生成するシンボル比較技術を与えることである。
【００１４】
この第２の目的は、第２の独立請求項のシンボル比較技術により達成される。
【００１５】
本発明のさらなる目的は、上述した第１および／または第２態様が適用される画像圧縮技術を与えることである。
【課題を解決するための手段】
【００１６】
本発明の第１の態様において、スキャンされたドキュメントを含む入力デジタル画像から、２値マスク画像を作成する方法が提案される。方法は、（ａ）前記入力デジタル画像を２値化することによって、２値化画像を作成するステップと、（ｂ）前記入力デジタル画像内にある暗い背景に重ねて明るいテキストを表す第１テキスト領域を、前記２値化画像において検出するステップと、（ｃ）前記２値化画像において前記第１テキスト領域を反転させることにより、明るい背景に重ねて示された暗いテキストと同様に、反転した第１テキスト領域が判別可能となるようにするステップと、を有する。これらのステップによって、反転したテキスト（暗い背景に重ねて示された明るいテキスト）が、従来例に対してさらに効率的なやり方で、特により速いスピードで、およびより少ない所要メモリ量で、検出することが可能となる。反転によって、正常テキスト（明るい背景に重ねて示された暗いテキスト）と同様に、反転テキストが判別可能となり、反転テキストを検出し、それを２値マスク内に配置するために、いかなる専用のステップおよびアルゴリズムも必要とはならない。
【００１７】
本発明の第１の態様における方法は、たとえばＭＲＣモデルを用いる画像圧縮技術において適用されることが可能である。このような技術において、正常テキストと同様に反転テキストを記録する有利な点は、反転テキストが背景ではなく前景内に置くことが可能となることである。結果として、反転テキストは、より高い圧縮レートをもたらすことが可能なシンボルに基づく圧縮技術によって圧縮されることが可能である。さらにその上、通常、低解像度を有し低い品質で圧縮される背景画像だけではなく、前景および背景画像に基づいて画像が再構成されるので、再構成された画像内にある反転テキストの視認性を高めることが可能となる。
【００１８】
本発明の第１の態様における方法は、たとえばテキスト認識技術において適用されることが可能である。このような技術において、正常テキストと同様に反転テキストを記録する有利な点は、反転テキストが、正常テキストに加えて認識可能となり、その後テキスト検索が可能となることである。
【００１９】
好ましい実施の形態において、本発明の第１の態様における方法は、さらに、（ｄ）前記入力デジタル画像内にある明るい背景に重ねて暗いテキストを表す第２テキスト領域を、前記２値化画像において検出するステップと、（ｅ）たとえば入力画像内にある写真部分からもたらされる写真要素以外には、テキストが実在しないテキスト領域を、２値化画像から取り除くステップと、を有する。
【００２０】
入力デジタル画像を２値化することによる、２値化画像の作成は、好ましくは、（ａ１）前記入力デジタル画像からグレースケール画像を構築するステップと、（ａ２）前記グレースケール画像内にあるエッジを検出し、エッジ画素および非エッジ画素を含むエッジ２値画像を構築するステップと、（ａ３）周囲の画素に基づいて、前記エッジ画素のそれぞれに対するしきい値を決定するとともに、前記非エッジ画素にゼロのしきい値を与え、しきい値グレースケール画像を構築するステップと、（ａ４）周囲のしきい値に基づいて、エッジ画素に接する前記非エッジ画素のそれぞれに対するしきい値を決定するステップと、（ａ５）最高のしきい値を保つことによって前記しきい値グレースケール画像をスケーリングするステップと、（ａ６）正の値を有する画素からゼロの値を有する画素へ、しきい値を伝搬させるステップと、（ａ７）前記グレースケール画像および前記スケーリングされたしきい値グレースケール画像に基づいて、第１の２値画像を構築するステップと、を含む。これらのステップの有利な点は、入力デジタル画像において種々の輝度およびコントラストを有するさらなる要素を検出するために、第１の２値画像を構築するために使用されるしきい値が変化することである。これにより、ＭＲＣモデル圧縮技術においては、伸張後の再構成された画像の品質を高めることが可能となる。
【００２１】
前記画像内にあるテキストシンボルのエッジを検出するステップ（ａ２）は、好ましくは、テキストシンボルの前記エッジ検出用にキャニーエッジアルゴリズムの使用を含む。キャニーエッジアルゴリズムは、多数のステージアルゴリズムを使用し、広い範囲のエッジを検出する。キャニーエッジアルゴリズムは、たとえば、Ｊ．キャニー「エッジ検出に対するコンピュータによるアプローチ」米国電気電子学会、パターン解析および人工知能に関する会報、第８巻、６号、１１月、１９８６年により開示されており、全体として参照することにより本明細書に援用される。このアルゴリズムの使用により、１つの画像内にあるテキストシンボルの検出および／または認識において、相当な改善をもたらすことが可能となる。
【００２２】
さらに好ましくは、２値画像の作成は、（ａ８）前記グレースケール画像および前記しきい値グレースケール画像に基づいて、第２の２値画像を構築するステップと、（ａ９）前記第１および第２の２値画像を組み合わせることによって、前記２値化画像を構築するステップと、を含む。これらのステップの有利な点は、入力デジタル画像において種々の輝度およびコントラストを有するさらなる要素を検出するために、第２の２値画像を構築するために使用されるしきい値がさらに変化することである。これにより、ＭＲＣモデル圧縮技術においては、伸張後の再構成された画像の品質を高めることが可能となる。
【００２３】
１つの実施の形態において、２値マスク画像の作成は、２値マスク解像度低減係数により入力デジタル画像の解像度を低減するステップを含む。このように、２値マスク解像度は、たとえば、再構成された画像における所望の品質に依存して、ＭＲＣモデル圧縮技術においてユーザ−側で調整可能となる。
【００２４】
本発明の第２の態様は、本発明におけるその他の態様と組み合わせてもよく、組み合わせなくてもよい。この第２の態様では、２値画像において、第１画素ブロブを第２画素ブロブと比較し、該第１および第２画素ブロブが一致シンボルを表すかどうかを決定する方法が提案される。方法は、（ｆ）第１ブロブを拡張し、第２ブロブが前記拡張された第１ブロブの内部に適合するかどうかを検査するステップと、（ｇ）第２ブロブを拡張し、第１ブロブが前記拡張された第２ブロブの内部に適合するかどうかを検査するステップと、を有する。比較方法は、さらに、（ｈ）第１および第２ブロブのうちの一方に存在する線であって、他方には存在しない線を検出するステップと、（ｉ）第１および第２ブロブのうちの一方がイタリック体のシンボルを表し、他方がイタリック体のシンボルを表さないかどうかを決定するステップと、のうち、少なくとも１つのステップを有する。ステップ（ｈ）および（ｉ）は、誤ったシンボル一致の数を効果的に低減する、言い換えれば、不一致シンボルが一致シンボルとして検出されるリスクを効果的に低減することが可能である。
【００２５】
本発明の第２の態様に記載の方法において、好ましくは、ステップ（ｈ）は、Ｎが相当数のビット数、好ましくは３の場合、Ｎ×Ｎのクロスにおいて、前記ブロブのうちの一方内にある１つの線が、他方のブロブ内にある１つの線とは異なるカラーを有するかどうかを検査するステップを含む。
【００２６】
本発明の第２の態様に記載の方法において、好ましくは、ステップ（ｉ）は、第１および第２ブロブが共有する黒色画素の数が、所定のしきい値より高いかどうかを検査するステップを含む。この所定のしきい値は、好ましくは１つのブロブ内にある画素の全量の８０〜９０％に等しく、さらに好ましくは大略８５％に等しい。しかしながら、当業者によって適切と判断されるなら、さらに別のしきい値が使用されてもよい。
【００２７】
本発明におけるすべての上述した態様は、本発明のさらなる態様の部分であってもよく、すなわち、前記スキャンされたドキュメントを含む前記入力デジタル画像を圧縮する圧縮方法であって、（ｊ）前記ドキュメントの前景要素のカラー情報を含む前景画像と、前記ドキュメントの背景要素のカラー情報を含む背景画像と、前記圧縮されたデジタル画像を伸張するときに前記前景画像および前記背景画像内にある画素から選択する前記２値マスク画像と、を有する多数の画像層へと、前記入力デジタル画像を分割するステップと、（ｋ）適切な圧縮技術によって画像層のそれぞれを圧縮し、圧縮されたデジタル画像を得るステップと、を有する。
【００２８】
このさらなる態様において、好ましくは前記２値マスク画像の作成は、２値マスク解像度低減係数により前記入力デジタル画像の解像度を低減するステップを含む。２値マスク解像度は、たとえば、再構成された画像における所望の品質に依存して、ユーザ−側で調整可能である。
【００２９】
このさらなる態様において、好ましくは前記前景および背景画像は、それぞれ前景解像度低減係数および背景解像度低減係数により前記解像度を低減することによって構築される。前景および背景解像度は、たとえば、再構成された画像における所望の品質に依存して、ユーザ−側で調整可能である。
【００３０】
このさらなる態様において、好ましくは、圧縮は、たとえばＪＰＥＧ２０００または当業者には知られているいずれか別の圧縮技術などの、（ｋ１）画像圧縮技術によって前記前景および背景画像を圧縮するステップと、（ｋ２）シンボルに基づく圧縮技術によって前記２値マスク画像を圧縮するステップと、を含む。
【００３１】
本発明による実施の形態の有利な点は、スキャンされたドキュメント用に、再構成された画像の品質に影響せずにより高い圧縮レートが達成されることが可能な画像圧縮技術が与えられることである。
【００３２】
本発明による実施の形態の別の有利な点は、テキストの視認性または写真の描写について実質的に妥協しない画像圧縮技術が、与えられることである。
【００３３】
本発明による実施の形態の別の有利な点は、小型と品質との間のトレードオフを調整するのに、非常に柔軟性のある画像圧縮技術が与えられることである。
【００３４】
本発明による実施の形態の別の有利な点は、たとえば異なるカラーおよび明度のテキスト要素を含んでもよいドキュメント、ならびに／または異なるカラーおよび明度の背景、もしくはたとえば透かしもしくは写真などの一様でない背景上に配置されるテキスト要素を含むドキュメント、などのいずれかのタイプのドキュメントに対して、適切な画像圧縮技術が与えられることである。
【００３５】
本発明による実施の形態の別の有利な点は、暗い背景に重ねて示された明るいテキストを含むドキュメントに対して、適切な画像圧縮技術が与えられることである。
【００３６】
本発明による実施の形態の別の有利な点は、水平および垂直のグラフィック線が高い品質で伸張されることが可能な画像圧縮技術が与えられることである。
【００３７】
本発明による実施の形態の別の有利な点は、特定のタイプのドキュメントに対して設定される必要がある、ドキュメント特定のパラメータが少しも無い画像圧縮技術が与えられることである。
【図面の簡単な説明】
【００３８】
【図１】本発明に従うＭＲＣモデル圧縮アルゴリズムの全体のフローチャートを示す。
【図２】図１のフローチャートにおける分割ステップの詳細なフローチャートを示す。
【図３】図２のフローチャートにおける２値化ステップの詳細なフローチャートを示す。
【図４】図２のフローチャートにおける前景要素の選択ステップの詳細なフローチャートを示す。
【図５】図４のフローチャートにおける大きいブロブ除去ステップおよび白色ブロブ反転ステップの詳細なフローチャートを示す。
【図６】図５のフローチャートにおいてさらに水平および垂直のグラフィック要素が保たれる場合の変形を示す。
【図７】図２のフローチャートにおける背景画像構築ステップの詳細なフローチャートを示す。
【図８】図２のフローチャートにおける前景画像構築ステップの詳細なフローチャートを示す。
【図９】本発明に従うシンボル比較アルゴリズムのフローチャートを示す。
【図１０】図９のシンボル比較アルゴリズムにおけるステップの可視化を示す。
【図１１】図１〜８の方法によって圧縮可能な入力カラー画像の一例を示す。
【図１２】２値化ステップ後における図１１の画像を示す。
【図１３】図１１の画像から構築された２値マスク画像を示す。
【図１４】図１１の画像から構築された背景画像を示す。
【図１５】図１１の画像から構築された前景画像を示す。
【図１６】図１３〜１５の画像によって構築された、再構成された画像を示す。
【図１７】図１３の２値マスク画像が図１２の２値化された画像からいかに構築されるかをステップ的に示す。
【図１８】図１３の２値マスク画像が図１２の２値化された画像からいかに構築されるかをステップ的に示す。
【図１９】図１３の２値マスク画像が図１２の２値化された画像からいかに構築されるかをステップ的に示す。
【図２０】図１３の２値マスク画像が図１２の２値化された画像からいかに構築されるかをステップ的に示す。
【図２１】図１３の２値マスク画像が図１２の２値化された画像からいかに構築されるかをステップ的に示す。
【発明を実施するための形態】
【００３９】
本発明は、次の説明および添付の図面によって、さらに明らかにされる。
【００４０】
本発明は、特定の実施の形態について、およびいくらかの図面を参照して説明される。しかしながら本発明は、これらの実施の形態および図面に限定されず、請求項によってだけ限定される。説明される図面は、図式的なものにすぎず、非限定的である。図面において、要素のいくつかのサイズは、誇張されてもよく、例示的な目的のために、定規に合わせて描かれなくてもよい。寸法および相対的寸法は、本発明の実際の具体化物に必ずしも一致しない。
【００４１】
さらにその上、明細書および請求項における、第１、第２、第３、および類似の用語は、類似の要素間の区別用に使用され、必ずしも順次的または時系列的順番を説明するものではない。用語は、適切な状況の下で交換可能であり、本発明の実施の形態は、本明細書において説明されまたは図示される以外の別の一連の処理において動作することが可能である。
【００４２】
さらにその上、明細書および請求項における、一番上の、一番下の、上方の、下方のおよび類似の用語は、便宜的に使用されており、必ずしも相対的場所を説明するものではない。使用されている用語は、適切な状況の下で交換可能であり、本明細書において説明される本発明の実施の形態は、本明細書において説明されまたは図示される以外の別の方向性において動作することが可能である。
【００４３】
請求項において使用される「有する（含む）」の用語は、閉鎖的限定列挙の意味に解釈されるべきではなく、別の要素またはステップを除外してはいない。この用語は、参照されるような、定められた特徴、統合部分、ステップ、または構成要素の存在を特定するとして解釈される必要があるが、しかし１つ以上の別の特徴、統合部分、ステップもしくは構成要素、またはこれらの組み合わせの存在もしくは追加を除外しない。それゆえに、表現「手段ＡおよびＢを有する（含む）装置」は、構成要素ＡおよびＢに閉鎖的限定解釈されるべきではない。本発明に関して、装置のうち必須の構成要素がＡおよびＢであるということを意味する。
【００４４】
本実施の形態では、「カラー画像」は、カラーラスター画像、すなわちカラー値を表す各画素を有する画素マップを意味すると意図される。
【００４５】
本実施の形態では、「グレースケール画像」は、明度値を表す各画素を有する画素マップを意味すると意図される。
【００４６】
本実施の形態では、「２値画像」または「２値化された画像」は、２値性画像、たとえば黒色＆白色画像、すなわち２値（オンまたはオフ、１または０、黒色または白色）を表す各画素を有する画素マップを意味すると意図される。
【００４７】
本実施の形態では、「２値化」は、カラーまたはグレースケール画像を２値画像に変換する動作を参照すると意図される。
【００４８】
本実施の形態では、２つの２値画像の「ＡＮＤ」動作は、２つの元の画像において対応する画素の論理積を作成し、結果を目標画像内に入れる動作を参照すると意図される。
【００４９】
本実施の形態では、２つの２値画像の「ＯＲ」動作は、２つの元の画像において対応する画素の論理和を作成し、結果を目標画像内に入れる動作を参照すると意図される。
【００５０】
本実施の形態では、２つの２値画像の「ＸＯＲ」動作は、２つの元の画像において対応する画素の排他的論理和を作成し、結果を目標画像内に入れる動作を参照すると意図される。
【００５１】
本実施の形態では、２値画像の「反転」は、元の画像における各画素を反転させ、結果を目標画像内に入れる動作を参照すると意図される。
【００５２】
本実施の形態では、２値画像の「拡張」は、各黒色画素に対して、Ｎ×Ｎの黒色模様を、目標画像内の対応する黒色画素位置を中心とするように、目標画像に加える動作を参照すると意図される。たとえば、３×３黒色模様による拡張は、各黒色画素に対して、３×３黒色模様を目標画像に加える動作を意味する。
【００５３】
本実施の形態では、グレースケール画像の「拡張」は、各画素に対して、この画素を中心とするＮ×Ｎ（たとえば、３×３）の４角形内でもっとも暗い画素の値を検索し、目標画像の対応する画素をこの値にする動作を参照すると意図される。
【００５４】
本実施の形態では、２つの２値画像における「ブロブ（ｂｌｏｂ：塊）」は、接続された黒色または白色画素のグループを参照すると意図される。
【００５５】
次に、画像圧縮方法の例を用いて、本発明の態様が説明される。ここで留意すべきは、説明されるアルゴリズムの多くは、さらに別の方法で与えられてもよく、たとえばテキスト認識などのアルゴリズムであってもよい。さらにその上、本発明の範囲から逸脱せずに、多くの修正が、説明されるステップおよびアルゴリズムになされてもよい。
【００５６】
図１に示される圧縮方法は、ＭＲＣモデルに基づいており、入力されたカラーまたはグレースケール画像は、３つの層に分割され、その後、各層は、適切な圧縮技術によって別々に圧縮される。特に、入力されたカラー画像１は、背景解像度低減係数２、前景解像度低減係数３、および２値マスク解像度低減係数４をパラメータとする分割アルゴリズム１００によって、背景画像５、２値マスク画像６、および前景画像７へと分割される。マスク画像６は２値画像であり、背景および前景画像５、７は、（入力された画像１がカラーまたはグレースケールかどうかに依存して）カラーまたはグレースケール画像である。２値マスク画像６内にあるオン画素は、伸張する場合に、カラー（またはグレースケール）が前景画像７から取り除かれなければならないことを示す。２値マスク画像６内にあるオフ画素は、伸張する場合に、カラー（またはグレースケール）が背景画像５から取り除かれなければならないことを示す。引き続いて、背景画像５は、背景品質８をパラメータとする（たとえば、ＪＰＥＧ２０００などの）画像圧縮技術３００によって圧縮され、２値マスク画像６は、マスク品質９をパラメータとする（たとえば、ＪＢＩＧ２などの）シンボルに基づく圧縮技術によって圧縮され、前景画像７は、前景品質１０を入力とする（たとえばＪＰＥＧ２０００などの）画像圧縮技術５００によって圧縮される。最後に、圧縮された画像は、たとえばＰＤＦなどの、ドキュメント読み取り可能フォーマット内にカプセル化され、圧縮された画像１１を生成する。
【００５７】
分割アルゴリズム１００は、図２〜８によって詳述され、ステップおよびサブアルゴリズムが示される。一般に、図２に示されるように、分割は次のステップを有する。入力された画像１は、適応局所アルゴリズム１１０により２値化され、２値化された画像１２３をもたらす。ステップ１２５において、２値化された画像１２３から前景要素が選択され、２値マスク画像６を構築する。この２値マスク画像６は、入力された画像１に基づいて、ステップ１７０において背景画像５を構築し、ステップ１８０において前景画像７を構築するために使用される。ステップ１７０および１８０は、それぞれ背景解像度低減係数２および前景解像度低減係数３を考慮に入れる。ステップ１２６は、任意選択のステップであり、２値マスク解像度低減係数４に基づいて２値マスク画像６の解像度を低減する。
【００５８】
図３に示されるように、入力された画像１の２値化は、次のステップによる適応局所アルゴリズム１１０を有する。ステップ１１１において、入力された画像１（カラーの場合）は、画素明度を計算することによって、グレースケール画像へと変換される。このグレースケール画像は、ノイズを低減するために（たとえばガウシアンフィルタによって）平滑化されてもよい。
【００５９】
次にステップ１１２では、グレースケール画像においてキャニーエッジ検出アルゴリズムによってエッジが検出される。キャニーエッジ検出アルゴリズムは、１９８６年に、ジョン．エフ．キャニー（Ｊｏｈｎ  Ｆ．Ｃａｎｎｙ）によって開発された。キャニーエッジ検出アルゴリズムは、多数のステージアルゴリズムを使用し、広い範囲のエッジを検出する。キャニーエッジ検出アルゴリズムは、たとえば、Ｊ．キャニー「エッジ検出に対するコンピュータによるアプローチ」米国電気電子学会、パターン解析および人工知能に関する会報、第８巻、６号、１１月、１９８６年において説明されており、全体として参照することにより本明細書に援用される。アルゴリズムは、エッジ輪郭を破壊することを回避するために、２つのしきい値、「Ｔｈｉｇｈ」および「Ｔｌｏｗ」を使用する。エッジ輪郭は、Ｔｈｉｇｈよりも大きい勾配の画素で始まり、Ｔｈｉｇｈよりも低くＴｌｏｗよりも大きな勾配の画素に対してさえも続くことが可能である。本発明によれば、ＴｌｏｗおよびＴｈｉｇｈの典型的な値は、１バイトのグレースケール画像に対してそれぞれ３２および４０である。キャニーエッジ検出アルゴリズムは、グレースケール画像内にあるテキストおよびグラフィック要素のエッジを検出するために、使用される。このようにすることにより、写真のエッジもまた検出されるが、写真要素は、あとで（後述のステップ１６０を参照）フィルタが掛けられるので問題とはならない。キャニーエッジ検出器は２値画像を生成し、この２値画像においてエッジ画素だけが１に設定される。
【００６０】
別のエッジ検出アルゴリズムに対して、キャニーエッジ検出アルゴリズムは、次の有利な点を提供する。
−  良好な検出：このアルゴリズムは、画像内にある実在のエッジをできるかぎり多くマークする。
−  良好な位置決め：マークされたエッジは、実在の画像内にあるエッジにできるだけ近い。
−  最小限の応答：画像内にある所定のエッジはいったんマークされるだけであり、可能であれば、画像ノイズは偽のエッジを作成しない。
【００６１】
次にステップ１１３において、エッジ２値画像出力の各エッジ画素に対して、キャニーエッジアルゴリズム１１２によってしきい値が計算される。しきい値は、最低値と最高値との和の半分となる。最低値は、分析される画素を中心とする３×３の４角形における最低値である。最高値は、分析される画素を中心とする３×３の４角形における最高値である。非エッジ画素は０のしきい値を受ける。
【００６２】
次にステップ１１４において、エッジ画素に接する非エッジ画素に、しきい値が割り当てられる。しきい値は、入力から出力へとコピーされる。非エッジ画素（値＝０）にとっては、３×３の４角形は各画素を中心とする。この４角形内にある画素のしきい値の合計が計算され、エッジ画素があればエッジ画素の数によって分割される。この値は、出力画像上にコピーされる。ステップ１１４の出力はしきい値グレースケール画像である。
【００６３】
次にステップ１１５において、このしきい値グレースケール画像は、ある整数の係数分だけ、好ましくは４だけスケーリングされる。出力画像は０で初期化される。各出力画素に対して、対応する入力画素の値は加算され、非ゼロ値があれば非ゼロ値の数によって分割される。
【００６４】
次にステップ１１６において、しきい値は近隣における値で平均化される。３×３の４角形は、０とは異なる値の各画素を中心とする。この４角形内にある画素のしきい値の合計が計算され、非ゼロ値があれば非ゼロ値の数によって分割される。この値は、出力画像上にコピーされる。
【００６５】
次にステップ１１７において、しきい値は、しきい値を有しない画素へと伝搬する。第１に、しきい値は、ステップ１１４と大略同様に、ゼロ値画素に接する非ゼロ値画素に割り当てられる。第２に、２パス伝搬アルゴリズムが使用される。１番目のパスにおいて、画像は左から右へ、および上から下へスキャンされる。ゼロ値画素の値は、最小の非ゼロ値を有する隣接画素の値にされる。２番目のパスにおいて、画像は右から左へ、および下から上へスキャンされる。再び、ゼロ値画素の値は、最小の非ゼロ値を有する隣接画素の値にされる。このように、すべての画素がしきい値を受ける。
【００６６】
次にステップ１１８において、ステップ１１１からのグレースケール画像出力と、ステップ１１７からのしきい値がスケーリングされたグレースケール画像出力との組み合わせによって、第１の２値画像１１９が構築される。グレースケール画像内にある各画素の値は、スケーリングされたしきい値画像内にある対応する画素のしきい値と比較される。第１の２値画像１１９において、画素値がしきい値を下回るか上回るかに依存して、１または０の値が設定される。
【００６７】
ステップ１２０において、ステップ１１１からのグレースケール画像出力と、ステップ１１４からのしきい値グレースケール画像出力との組み合わせによって、第２の２値画像１２１が構築される。グレースケール画像内にある各画素の値は、しきい値画像内にある対応する画素のしきい値と比較される。第２の２値画像１２１において、画素値がしきい値を下回るか上回るかに依存して、１または０の値が設定される。
【００６８】
最後に２値化アルゴリズム１１０のステップ１２２において、第１の２値画像１１９と第２の２値画像１２１との論理和（ＯＲ）がなされ、２値化された画像１２３を生成する。
【００６９】
２値化された画像１２３は、テキストおよびグラフィック要素に加えて、入力された画像１内にある写真部分からの要素を含む。これらの要素は取り除かれ、２値マスク画像６内には発生しないことが望ましい。さらにその上、黒色のテキスト要素に重ねて示された白色のテキスト要素が反転することにより、白色テキストに重ねて示された黒色テキストと同様に判別可能となる。これは、２値マスク画像６におけるさらなる処理において、非常に有利な点となる。これらのステップは、図４に示される選択アルゴリズム１２５によって実行される。
【００７０】
サブアルゴリズム１３０または１４０によって、２値化された画像１２３から大きいブロブが取り除かれ、白色ブロブが反転する。２つの間の差は、サブアルゴリズム１４０では、水平および垂直のグラフィック要素を保つためのステップが加えられることである。
【００７１】
図５に示されるサブアルゴリズム１３０は、次のステップを有する。ステップ１３１において、大きい黒色ブロブ、すなわち所定の最低値を上回る相当数の画素を有するブロブ、だけが保たれる。次にステップ１３２において、保たれたブロブを含む画像が反転する（ＩＮＶＥＲＴ）。ステップ１３３において、この反転した画像と２値化された画像との論理積（ＡＮＤ）がなされる。これらのステップは、ステップ１３２の画像出力に対して繰り返される。すなわちステップ１３４において、再び大きい黒色ブロブだけが保たれ、ステップ１３５において、保たれたブロブを含む画像が反転し、ステップ１３６において、ステップ１３２の画像出力との論理積がなされる。最後に、ステップ１３７において、ステップ１３３の画像出力とステップ１３６の画像出力との排他的論理和（ＸＯＲ）がなされ、変換された２値画像１３８となる。
【００７２】
図６に示されるサブアルゴリズム１４０は、次のステップを有する。除去ステップ１４１および排他的論理和ステップ１４２によって、２値化された画像１２３から水平および垂直のグラフィック要素が分離される。ステップ１４３〜１４５は、サブアルゴリズム１３０のステップ１３１〜１３３に一致する。さらに、除去ステップ１４６および排他的論理和ステップ１４７によって、ステップ１４４の画像出力から水平および垂直のグラフィック要素が分離される。これらの分離されたグラフィック要素は、ステップ１４８において、排他的論理和ステップ１４２の出力と排他的論理和ステップ１４７の出力との論理和を作成するとによって組み合わせられる。ステップ１４９〜１５１は、サブアルゴリズム１３０のステップ１３４〜１３６に一致する。再びステップ１５２において、論理積ステップ１４５の画像出力と論理積ステップ１５１の画像出力との排他的論理和がなされる。最後にステップ１５６において、排他的論理和ステップ１５２の出力と論理和ステップ１４８の出力との論理和を作成することによって、変換された２値画像１５７が生成され、水平および垂直のグラフィック要素を画像へ戻す。
【００７３】
黒色テキスト要素に重ねて示された白色テキスト要素を反転させる上述したステップの有利な点は、ドキュメントにおけるすべてのブロブの記述（ビットマップまたは実行リスト）を記憶する必要がないことである。従来例の方法では、特に、穴（別のブロブに囲まれたブロブ）を探し出すことによって、黒色ブロブに重ねて示された白色ブロブを反転させるために、これが必要となる。アルゴリズム１３０および１４０において、ブロブは見つけられるやいなや処理され、ブロブが処理された後、その記述は取り除かれる。
【００７４】
図４に戻ると、写真ブロブを取り除くこと（すなわちテキスト要素が存在しないブロブ）によって、変換された２値画像１３８／１５７から２値マスク画像６が生成される。これは、当技術分野で周知の最小記述長原理を使用する、フィルタを掛けるステップ１６０によって達成される。各ブロブに対して、前景要素または背景要素のうちのいずれであるかが決定される。最小記述長原理を適用する場合に、ストラテジーは、ブロブが前景であるとして圧縮される場合と、背景の一部分であるとして圧縮される場合とにおいて、いずれの場合がより良好に圧縮されるかを知ることにある。ブロブは、背景内にある場合、背景画像において圧縮される。ブロブは、前景内にある場合、２値マスク画像および前景画像において圧縮される。それで、異なる圧縮のコストを見積もる必要がある。見積もりは、単純なモデルを用いてなされる。背景モデルは、カラーが滑らかに変化すると仮定する。画素のカラーは、その近隣の画素と大きくは異ならない。画素カラーと局所的平均のカラーとの間の誤差の合計がコストとなる。前景モデルは、ブロブにおけるすべての画素が同じカラーを有していると仮定する。これは、通常は、テキスト要素の場合である。画素カラーと平均のカラーとの間の誤差の合計がコストとなる。２値マスクモデルは、圧縮コストがブロブの周囲に依存すると仮定する。そうすると、
背景コスト  ＜  前景コスト  ＋  周囲＊係数
の場合、ブロブは背景の一部分となり、（フィルタが掛けられる）。
【００７５】
係数はパラメータだけであり、大量のページをテストすることによって調整される。ここで再び、ブロブは、見つけられるやいなや処理される。ブロブが処理された後、記述は取り除かれる。
【００７６】
図７に示されるように、背景画像５は、入力された画像１と、２値マスク画像６と、ユーザ−規定可能なパラメータであってもよい背景解像度低減係数２とを入力とするアルゴリズム１７０によって生成される。ステップ１７１において、２値マスク画像は拡張される。ステップ１７２において、解像度は背景解像度低減係数２によって低減される。同様にステップ１７３において、入力された画像１の解像度は、背景解像度低減係数２によって低減される。その結果、画像は、ステップ１７４において組み合わせられ、「空き」画素を満たす。低減された２値マスク画像においてオンとなる、低減された入力画像における画素のカラーは、２つのステップの順次的なアルゴリズムを用いることによって、変更される。１番目のパスにおいて、２つの画像が左から右へ、および上から下へスキャンされる。「空き」画素に出会った場合（低減された２値マスク内のオフ値）、３×３の４角形は、低減された入力画像内のこの「空き」画素を中心とし、この４角形内にある画素のカラー値の合計が計算され、非空き画素があれば非空き画素の数によって分割される。このカラー値は、低減された入力画像内の画素に割り当てられる。２番目のパスにおいて、２つの画像が右から左へ、および下から上へスキャンされる。再び、「空き」画素に出会った場合、１番目のパスと同様にカラー値がこの「空き」画素に割り当てられる。
【００７７】
図８に示されるように、前景画像７は、入力された画像１と、２値マスク画像６と、ユーザ−規定可能なパラメータであってもよい前景解像度低減係数３とを入力とするアルゴリズム１８０によって生成される。ステップ１８１および１８２において、２値マスク画像は引き続いて反転し、拡張される。ステップ１８３において、解像度は前景解像度低減係数２によって低減される。同様にステップ１８５において、入力された画像１の解像度は、前景解像度低減係数２によって低減される。その結果、画像は、ステップ１８６において組み合わせられ、「空き」画素を満たす。低減された２値マスク画像においてオンとなる、低減された入力画像における画素のカラーは、ステップ１７４に類似の、２つのステップの順次的なアルゴリズムを用いることによって、変更される。
【００７８】
図１〜８の方法によって圧縮された画像の一例が、図１１〜１６に示される。図１１は、３００ｄｐｉでスキャンされたドキュメントである、入力されたカラー画像１を示す。図１２は、２値化１１０後の２値化された画像１２３を示し、図１３は、前景要素１２５の選択後の２値マスク画像６を示す。２値マスク画像もまた３００ｄｐｉの解像度であり、この場合は２値マスク解像度低減係数が１に設定されている（低減なし）ことを意味する。図１４は背景画像５を示し、背景画像５は１００ｄｐｉの解像度であり、背景解像度低減係数が３に設定されていることを意味する。図１５は前景画像７を示し、前景画像７は５０ｄｐｉの解像度であり、前景解像度低減係数が６に設定されていることを意味する。図１６は、圧縮された画像１１の伸張後に達成される、再構成された画像１２を示す。２値マスク画像は３００ｄｐｉの解像度であるので、再構成された画像もまた３００ｄｐｉの解像度であり、すなわち入力された画像１と同じ解像度となる。図１１および１６の比較から、再構成された画像の高い品質が、図１〜８の圧縮方法によって達成可能であることが明らかである。
【００７９】
図１７〜２１は、前景要素選択処理１２５によって、２値化された画像１２３から２値マスク画像６がいかに構築されるかを示す（図４〜６を参照）。図１７は、画像の中央にある垂直の黒色線の分離後、すなわちステップ１４１の後の、２値化された画像１２３を示す。図１８は、大きい黒色ブロブだけが保たれ、反転した後、すなわちステップ１４３および１４４の後の、２値化された画像１２３を示す。図１９は、大きい黒色ブロブを有しない、２値化された画像１２３を示す。これは、ステップ１４５において図１７および１８の画像の論理積を行うことによって達成される。図２０は、ステップ１４６〜１５１の後の結果、すなわち大きい黒色ブロブを有しない、反転した画像を示す。ステップ１５２において、図１９および２０におけるこれら２つの画像の排他的論理和を行うことによって、変換された２値画像１３８／１５７が達成される。変換された２値画像１３８／１５７は、２値化された画像１２３において、大きい黒色ブロブが取り除かれ、白色ブロブが反転した画像となっている。この変換された画像は、図２１に示される。元の画像１内にある暗い背景または「反転したテキスト」に重ねて明るいテキストを表すテキスト領域は、元の画像１内にある明るい背景または「正常テキスト」に重ねて示された暗いテキストと同様に、白色に重ねて示された黒色として表されると理解することが可能である。図１３の２値マスク画像６は、ステップ１６０において、写真ブロブに対してフィルタを掛けることによって、図２１の変換された画像から構築される。
【００８０】
図９は、本発明の第２の態様に従うシンボル分類アルゴリズムを示す。このシンボル分類アルゴリズムは、２値マスク画像６を圧縮するために使用される、シンボルに基づく圧縮アルゴリズム４００の一部分であってもよい。シンボル分類アルゴリズムは、たとえば２値マスク画像６などの２値画像を入力とし、シンボルのリストおよびシンボル発生のリストを出力する。シンボルのリスト内にある品目は、シンボルＩＤおよびシンボルビットマップを含む。発生のリスト内にある品目は、一致シンボルＩＤおよびページ内の発生場所を含む。
【００８１】
シンボル分類アルゴリズムは、次のステップを有する。ステップ４０３および４０４において、第１画素ブロブ４０１が第２画素ブロブ４０２の拡張内に適合するかどうかが決定される。適合しない場合、「不一致」が戻される。適合する場合、ステップ４０５および４０６において、第２画素ブロブ４０２が第１画素ブロブ４０１の拡張内に適合するかどうかが決定される。適合しない場合、「不一致」が戻される。適合する場合、「一致」のように見えるが、しかし誤差を回避するためにさらに２つの検査がなされる。ステップ４０７および４０８において、ブロブ４０１、４０２のうちの一方が、他方において存在しない線を有するかどうかが決定される。さらに詳しくは、これは、ブロブのうちの一方内にある１つの線が、他方のブロブ内にある別の線とは異なるカラーを有する、３×３のクロスを検査するステップを含む。ステップ４０９および４１１において、ブロブ４０１、４０２のうちの一方がイタリック体のシンボルを表し、他方が表さないかどうかが決定される。さらに詳しくは、これは、第１および第２ブロブ４０１、４０２が共有する黒色画素の数が、所定のしきい値４１０を越えるかどうかを検査するステップを含む。この所定のしきい値は、好ましくは１つのブロブ内にある画素の全量の８０〜９０％に等しく、さらに好ましくは大略８５％に等しい。
【００８２】
これらのステップは、図１０において視覚化されている。上の行は、互いの拡張（ステップ４０３〜４０６）へと適合し、結果４２３が一致となる、２つの画素ブロブ４２１および４２２を表す。中央の行は、さらに互いの拡張（ステップ４０３〜４０６）へと適合し、しかし明らかに一致とはならない、２つの画素ブロブ４３１および４３２を表す。この種の誤差は、ブロブのうちの一方内にある１つの線が、他方のブロブ内にある他方の線とは異なるカラーを有する、３×３のクロス４３３、４３４を検査することによって取り除かれる（ステップ４０７〜４０８）。第１ブロブ４３１に重ねて示されたクロス４３３において垂直線４３５は黒色であり、一方、第２ブロブ４３２に重ねて示された対応するクロス４３４内にある水平線４３６は白色であり、結果４３７は不一致となる。下の行は、互いの拡張へとさらに適合し（ステップ４０３〜４０６）、しかし、ブロブ４４２がイタリック体のシンボルであり、ブロブ４４１がイタリック体のシンボルではないので、明らかに一致ではない、２つの画素ブロブ４４１および４４２を表す。この種の誤差は、ブロブ４４１とブロブ４４２との論理積を行い、その結果が４４３に示されるようになる（共通の黒色画素が結果４４３において黒色となる）ステップ、および共通の画素の数がしきい値４１０を越えるかどうかを検査するステップによって取り除かれる（ステップ４０９〜４１１）。この例では、４４３内にある画素の数はしきい値４１０を下回り、それゆえ不一致が検出される。
【図１】
0005501958.tif 000002
【図２】
0005501958.tif 000003
【図３】
0005501958.tif 000004
【図４】
0005501958.tif 000005
【図５】
0005501958.tif 000006
【図６】
0005501958.tif 000007
【図７】
0005501958.tif 000008
【図８】
0005501958.tif 000009
【図９】
0005501958.tif 000010
【図１０】
0005501958.tif 000011
【図１２】
0005501958.tif 000012
【図１３】
0005501958.tif 000013
【図１７】
0005501958.tif 000014
【図１８】
0005501958.tif 000015
【図１９】
0005501958.tif 000016
【図２０】
0005501958.tif 000017
【図２１】
0005501958.tif 000018
【図１１】
0005501958.tif 000019
【図１４】
0005501958.tif 000020
【図１５】
0005501958.tif 000021
【図１６】
0005501958.tif 000022