JP4494563B2

JP4494563B2 - トークン化によるイメージ分割を用いたイメージ処理方法および装置

Info

Publication number: JP4494563B2
Application number: JP29760799A
Authority: JP
Inventors: ジェイラクリッジウィリアム; ピーハッテンロッカーダニエル; エフフェルゼンワルブペドロ
Original assignee: Xerox Corp
Current assignee: Xerox Corp
Priority date: 1998-10-22
Filing date: 1999-10-20
Publication date: 2010-06-30
Anticipated expiration: 2019-10-20
Also published as: JP2000132690A; US6295371B1

Description

【０００１】
【発明の属する技術分野】
本発明は、トークン化によるイメージ分割を用いて、イメージを処理する方法及び装置に係り、特に形状比較あるいはトークン化によりイメージの高コントラスト領域のどの部分がテキストに対応するかを検出して、文書イメージをテキスト（あるいはシンボル）と連続階調領域に分割する方法に関する。このような分割は圧縮・伸長等のイメージ処理技術の実装に役立つ。
【０００２】
【従来の技術】
背景として、近年、イメージ処理により、相当高度な認識処理が実現されている。しかし、残念ながらスキャンされたカラーイメージを「見て」、イメージのどの部分がテキストに対応し、その部分が連続的な階調領域（連続階調領域）に対応するのかを判断するのは、コンピュータにとって、依然として困難なことである。
【０００３】
イメージをテキストと連続階調領域とに分割することは、イメージ処理の見地から有用であるため、このことは重要である。一旦テキストをイメージから分離すれば、連続階調領域とは切り離して、例えば光学式文字認識（ＯＣＲ）により、より効率的に処理することができる。
【０００４】
その上、イメージの圧縮・伸長が実装されている環境において、連続階調領域は顕著な品質劣化を伴なわずに、テキストよりも低い解像度で保存できるため、イメージの他の部分からテキストを分割することが重要になる。よく知られている非可逆的（lossy）な連続階調の圧縮方法ではテキストがぼやける。これらの圧縮方法では、テキストの高コントラスト領域を効率的に扱えないためである。
【０００５】
従って、テキストに対応するイメージの部分と対応しない部分を判定する効率的な分割方法を備えることは極めて重要である。公知の方法は以下で説明するように、不十分である。
【０００６】
この点に関して、イメージを分割するための公知の方法は、一般にピクセルレベルの統計値を用いる。すなわち、これらの方法はイメージのあるエリアや領域について、その中のピクセル間のコントラストに基づいてテキストの部分かどうかを判定する。例えば、これら公知の方法の一つによると、分析対象である特定の領域内の高コントラストエリアがテキストに対応すると判定する。しかし、このような方法はテキストではないが、高コントラストである領域がイメージに存在していると、そのようなイメージを効率的に扱うことができない。そのため、テキストではないイメージをテキストとして不適当に扱い、誤ってポジティブな判定結果を与えかねない。すなわち、誤ってテキストが検出されたと判定してしまう可能性がある。
【０００７】
【発明が解決しようとする課題】
このように、上記従来のイメージ処理方法では、コントラストの高い領域を含むイメージを効率的に扱うことができず、そのようなイメージでは、テキストが検出されたと誤って判定してしまうという問題点があった。
【０００８】
そこで、局所的にピクセルレベルの統計値を用いる際に、これらの誤ったポジティブな判定結果を補償するための方法が提案されている。しかしこれらの方法を採用した場合、過補償のため、コンポーネントがテキストであるか否かを判定するための基準が狭められ、表現の状態によってはテキストが失われてしまう。
【０００９】
さらに公知の方法は、ピクセルの輝度のみに注目する。これらの方法は、イメージの一部がテキストであるか連続階調領域であるかについて形状（Shape）を配慮していない。
【００１０】
本発明は上記実情に鑑みて為されたもので、これらの難点を克服する新しい、かつ改良されたイメージ処理方法及び装置を提供することを目的とする。
【００１１】
【課題を解決するための手段】
テキストおよび連続階調領域を含むイメージをイメージ処理装置で処理する方法を提供する。本発明の一側面としての本方法は、しきい値処理を行って、イメージを当該イメージの高コントラスト領域を表すコンポーネントを含む第２のイメージに変換するステップと、前記第２のイメージから、色の変化度とハミング距離と配置の各所定条件に適合すると判定されるコンポーネントを選択するステップと、前記選択されたコンポーネントの外形状の大きさに基づいて、前記選択されたコンポーネントを識別してマークをつけることによりクラスに分類するステップと、１以上のクラスに属する前記選択されたコンポーネントをテキストとして識別するステップと、類似色のコンポーネントに整列して配置されているコンポーネントであって前記選択されたコンポーネントのうち未だ識別されていないコンポーネントを、テキストとして識別するステップと、前記識別されたテキスト近傍に配置されたコンポーネントであって前記選択されたコンポーネントのうち未だ識別されていないコンポーネントを、テキストとして識別するステップと、を含む。
【００１２】
本発明の別の側面としての本方法では、前記しきい値処理された第２のイメージから、白又は黒のピクセルが連結したコンポーネントを抽出するステップは、どのコンポーネントが、連結した黒ピクセルを含むかを判定するステップと、どのコンポーネントが、連結した白ピクセルを含むかを判定するステップと、白又は黒ピクセルが連結したコンポーネントを反転させるステップとを含み、
前記抽出された白又は黒のコンポーネントから、色の変化度とハミング距離と配置の各所定条件に適合すると判定されるコンポーネントを選択するステップは、元のイメージから各コンポーネントの色を判定して、各コンポーネントの色変化度を判定するステップと、前記色変化度が所定のしきい値より小さいコンポーネントを選択するステップと、前記色変化度により選択された各コンポーネントについて２本のスキャンライン間のハミング距離を計算するステップと、前記各コンポーネントごとに平均ハミング距離を計算するステップと、前記平均ハミング距離が所定のしきい値より小さいコンポーネントを選択するステップと、前記平均ハミング距離により選択されたコンポーネントから、他のコンポーネントと整列して配置されていると判定されるコンポーネントを選択するステップとを含み、
本方法はさらに、前記識別されたテキスト近傍に配置され、かつ前記識別されたテキストに比べ、相対的に小さいコンポーネントであって、識別されていないコンポーネントをテキストとして識別するステップ、を含む。
【００１３】
本発明の別の側面として、テキストと連続階調領域を含むイメージを処理するための装置を提供する。本装置は、しきい値処理を行って、イメージを当該イメージの高コントラスト領域を表すコンポーネントを含む第２のイメージに変換する手段と、前記第２のイメージから、色の変化度とハミング距離と配置の各所定条件に適合すると判定されるコンポーネントを選択する手段と、前記選択されたコンポーネントの外形状の大きさに基づいて、前記選択されたコンポーネントを識別してマークをつけることによりクラスに分類する手段と、１以上のクラスに属する前記選択されたコンポーネントをテキストとして識別する手段と、類似色のコンポーネントに整列して配置されているコンポーネントであって、前記選択されたコンポーネントのうち未だ識別されていないコンポーネントを、テキストとして識別する手段と、前記識別されたテキスト近傍に配置されたコンポーネントであって、前記選択されたコンポーネントのうち未だ識別されていないコンポーネントを、テキストとして識別する手段と、前記識別されたテキスト近傍に配置され、かつ前記識別されたテキストに比べ、相対的に小さいコンポーネントであって、識別されていないコンポーネントをテキストとして識別する手段と、を含む。
【００１４】
【発明の実施の形態】
ここで図面を参照しつつ、本発明の実施の形態について説明する。図１及び図２は本発明の実施の形態に係るイメージ処理方法の好適な実施形態を表す全体説明図を与える。ただし、図は発明の好適な実施形態を図示することのみを目的とし、これを制限することが目的ではない。本好適な実施形態に係る方法は主にソフトウェア技術により実装される。しかし、ソフトウェア、ハードウェア、その他の手段又はそれらの組み合わせにかかわらず、本発明の本質的な要素をどのように実装しようと、それらは本発明の範囲内にある。
【００１５】
まず、イメージ内のテキストの出現にはいくつかの顕著な特徴があることが調べられている。すなわち、
（１）テキスト形状（text shape）は周囲の領域に比べて高いコントラストを有する
（２）テキスト形状はグループとして出現する（孤立している文字は稀である）
（３）同じ形状が繰り返して出現する
（４）互いに近いテキスト形状は同じ色を有する傾向がある
（５）任意の与えられたテキスト形状の内部色（塗りつぶし色）は滑らかである傾向がある。つまり、急激に変化するグラデーションで塗りつぶされることは稀である
という特徴である。
【００１６】
これらの特徴は他のものと同様に、イメージコンポーネントの形状に基づいてイメージを分割する好適な方法の基準としての役割を果たす。
【００１７】
図１に示すように、方法１００はイメージをスキャンすることから始められる（ステップ１０２）。図７と関連付けて説明するシステム例のようなシステムに対し、イメージがスキャナ入力された場合、イメージはピクセルの組（array）に対応するビットマップに変換されることを認識されたい。以後区別のため、ここでは「イメージ」とは、オリジナルのイメージとスキャンされたイメージ、あるいは結果として生じたビットマップを指すものとする。
【００１８】
続いて、イメージを白黒イメージに変換するために、局所的なしきい値処理ルーチンが実行される（ステップ１０４）。当分野で公知のことであるが、適応性のしきい値処理ルーチンは通常、１ピクセルの周りの局所的な領域（例えば正方形あるいは長方形のウインドウ）を黒白いずれに塗るべきかを判定するためにその区域を分析する。その区域内のピクセルの変化あるいはコントラストが計算される（例えばヒストグラムが作られる）。このデータに基づいて、しきい値が計算される。しきい値を下回る値を有するピクセルは黒と見なされ、しきい値を上回る値を有するピクセルは白と見なされる。イメージ全体にわたってこのプロセスが複数回行なわれる。これによりテキストを背景から分離して、テキストを判読可能にするのに十分な高コントラストイメージを生成する。もちろん、しきい値処理アルゴリズムは、背景の高コントラスト領域からも多数のテキスト以外の部分を抽出する。つまり、このしきい値処理ルーチンにより、テキストと、テキスト以外の高コントラスト部分とが抽出される。
【００１９】
そして、このしきい値処理されたイメージ（第２のイメージ）から、白又は黒が連結した画像部分（connected component）が抽出される（ステップ１０６及び１０８）。連結した画像部分（連結したコンポーネント）か否かを判断することは、公知の種々の技術により達成できる。これらのコンポーネントは、明るい部分に暗い色（dark-on-light）で、又は、暗い部分に明るい色（light-on-dark）で表された２つの形式のテキストを含む。白が連結したコンポーネントと黒が連結したコンポーネントとのいずれかが反転され（ステップ１１０）、２つの形式は同じ表現形態となる。本発明の一実施形態においては、白が連結したコンポーネントが反転される。従って２値（binary）表現されている、暗い部分に明るい色で表された所定の文字部分は、反転により明るい部分に暗い色の文字部分と同じように見えるようになる。この２値表現により、前景（foreground）のピクセルは、それが元々の画像で背景より暗くても、明るくても、常に黒で表現される。
【００２０】
元々のカラーイメージを分析することにより、各コンポーネントの色が判定される（ステップ１１２）。コンポーネントが十分な大きさであれば、色を判定するために内部ピクセルのみ考慮すればよいことを認識されたい。その理由は、エッジピクセルがイメージの背景に影響される可能性があるからである。次に各コンポーネントの前景ピクセルのすべてにわたる色が平均化され、色変化度（color variance）が判定される（ステップｌ１４）。所定のしきい値以下の色変化を有するコンポーネントが選択される（ステップ１１６）。色変化度の大きい、すなわち所定のしきい値を超えるコンポーネントは、テキストである可能性がないため、放棄される。
【００２１】
残りの各コンポーネントについて、２本の連続した走査ライン（scan line）の間のハミング距離が計算される（ステップ１１８）。ハミング距離は２本のラインの間で異なるビットの数のカウント値である。コンポーネントごとの平均ハミング距離もまた計算され（ステップ１２０）、図２の処理に続く（Ａ）。そして、図２に示すように、所定のしきい値を下回る平均ハミング距離を有するコンポーネントが選択される（ステップ１２２）。大きすぎる平均ハミング距離を有するコンポーネント、すなわち所定のしきい値を超えるコンポーネントは放棄される。すなわち、このステップの処理により、一貫した（コヒーレントな）形状を持たないノイズコンポーネントは排除される。ハミング距離のこのような使い方は、テキスト内の連続したスキャンラインが、例えばテキスト内の文字等のどの単独コンポーネントでも大きく異ならないというテキストの特徴を利用している。
【００２２】
次に、どのコンポーネントがほぼ同じ高さの他のコンポーネントと整列して配置されているか（すなわち近いか）を判定する（ステップ１２４）。続いて、これらのコンポーネントが選択される（ステップ１２６）。このステップの目的は、単語と思われるコンポーネントのグループを見い出すことにある。
【００２３】
これらはイメージのうちのテキスト部分を予め「推測」したものである。このようなコンポーネントは次に分類され、あるいはトークン化される（ステップ１２８）。トークン化は、ほぼ同一の形状を有するコンポーネントを識別して、マークを付ける処理である。また、一意のコンポーネント、すなわち他のいかなるコンポーネントとも同じ形状あるいはほぼ同じ形状を持たないコンポーネントを「単独部分（singleton）」としてマークを付ける。このようにして、各コンポーネントがクラスに分類される。
【００２４】
ここで好適な実施形態（すなわち図１及び図２）のステップ１２８で実行されるシンボル、あるいはコンポーネントを分類するプロセスを図３及び図４を参照しつつ説明する。
【００２５】
図３は、好適な実施形態の比較処理で用いられるシンボルの辞書（以下、「シンボル辞書」と称する）のデータ構造をブロック図で表現したものである。図３に示すように、テーブル２０１は、シンボルの外形状の大きさにより索引付けされたコンテンツを含む。各テーブルのエントリ、例えば、テーブルエントリ２０４は、連結データ（linked data）構造を介して互いに連結（リンク）された１個以上の等価クラス２０２を参照（すなわち指示）している。各等価クラス２０２はクラスにおけるシンボル２０３のインスタンスの別の連結リストを含む。シンボルの各インスタンスは、当該インスタンスをメディア上で見つけることができるように、位置情報と、インスタンスのビットマップと、「最適一致位置（best match position）」を識別する情報とを含む。以下、詳細に説明するように、最適一致位置は、インスタンスがクラスに登録された比較対象（exemplar）と最適に一致するようにシフトされた位置を示す。
【００２６】
好適な実施形態において、テーブル２０１はハッシュテーブルである。ハッシュテーブルは、「大から小（many to few）」の順序づけられたマッピングを生成するための公知のデータ構造であり、ハッシュテーブルのサイズの剰余を返すランダム関数を用いる。このようなハッシュテーブルの性質は、大きさが同じであるシンボルの連結リストを維持し、それにアクセスするために用いられる。連結リストは、リスト内のノードのインスタンスが、リスト内の次のノードを指すという公知のデータ構造である。図３に図示するデータ構造は本発明の範囲を制限するものではないことに注意されたい。等価クラスの編成と、それに対する比較をサポートする他のデータ構造を用いても本発明の思想と範囲からは逸脱しない。すなわち、等価クラスのリスト編成と、比較の演算が可能であれば、どのようなデータ構造であっても構わない。
【００２７】
図３に示すシンボル辞書は潜在的なシンボルの一致（potential symbol match）への参照を可能にすべく用いられるダイナミックな構造である。図４のフローチャートはシンボル辞書を使用して実行される比較処理（matching process）を表している。まず、潜在的一致を含むハッシュテーブルのエントリを検索するため、抽出されたシンボルの大きさ（すなわち、幅と高さ）に対してハッシュ関数が適用される（ステップ３０１）。チェックすべき等価クラスが存在するか否かを判定するためにエントリを調べる（ステップ３０２）。エントリが空でなく、かつそれ以前の比較の試行により連結リストが既に完全に探索されていなければ、そのエントリには調べるべき等価クラスが存在することになる。等価クラスが検出された場合、ステップ３０３で抽出されたシンボルと、その等価クラスの比較対照が一致するか否かが判定される。等価クラスの比較対照は、（１）等価クラスの生成をもたらしたシンボルか、あるいは（２）等価クラスを「コミット」する過程で生成された平均的シンボル（以下に述べる）のいずれかである。シンボルを比較することについては以下に詳述する。いずれの比較対照であっても、あるシンボルが、連結リスト内の比較対照の１つと一致した場合には、当該シンボルは対応する等価クラスに加えられる（ステップ３０４）。等価クラスへのシンボル追加（比較対照としての追加）は、等価クラスのデータ構造にシンボルを追加して行う。一致しない場合、ステップ３０５で連結リストがさらに探索され、比較すべき別の等価クラスが存在するか否かが判定される（ステップ３０２）。
【００２８】
現在探索中のシンボルテーブルエントリの連結リストに、もはや等価クラスが存在しない場合、類似のサイズの等価クラスの全てがチェック済みか否かを判定する（ステップ３０６）。全てチェック済みでなければ、ハッシュテーブルエントリを判定するために用いたサイズパラメータを、まだチェックしていない、当該類似のサイズのものに修正し（ステップ３０８）、新しいテーブルエントリがステップ３０１で評価されることになる。類似サイズの等価クラスの全てがチェック済みならば、新しい等価クラスが作られる（ステップ３０７）。新しい等価クラスは、シンボル辞書の中の、抽出されたシンボルの元の（修正前の）大きさに対応するテーブルエントリの連結リスト構造に格納される。
【００２９】
シンボル分類の過程で他の２つのステップが実行されるが、これらはシンボル辞書管理に相当する。１つは、コミット処理であり、もう１つは等価クラスのマージ処理である。コミット処理は、予め定められた数（例えば１０）番目の抽出されたシンボルが、等価クラスの一部になるときに実行される。すなわち、例えば１０個目の抽出されたシンボルが等価クラスに登録されるときに実行される。コミット処理は平均化された等価クラスの比較対照を生成する。すなわちクラスを代表するビットマップが形成される処理である。このステップが実行される前は、等価クラスの比較対照は単にクラスの生成をもたらした最初のシンボルに過ぎない。平均化されたクラスの比較対照はクラス内のすべてのシンボルをより正確に表すことになる。これはクラスのメンバーであるシンボルを表現しているビットマップを「平均化する」ことにより実現される。平均化は、異なるピクセル位置のそれぞれにおいて「点灯」ピクセルを有するクラスのメンバー（それらの最適一致位置での）のカウント数を含むヒストグラムを維持することにより達成される。つまり、登録された各ピクセルごとに、当該ピクセルが「点灯」している比較対照の個数を用いて平均化を行う。比較対照は、このヒストグラムにしきい値処理を行なうことにより生成される。すなわち、ピクセルごとに、当該ピクセルが点灯している比較対照の個数が所定のしきい値を超えた場合、結果として出力される比較対照において、ピクセルは点灯される。比較対照内の点灯ピクセルの個数がなるべくクラスのメンバー内で点灯ピクセルの個数のメジアン（中央値）に近づくようにしきい値が選択される。
【００３０】
一旦最終的な比較対照が生成されると、すべてのシンボルについて、この平均化されたクラス比較対照と一致するか否かが調べられる。この調査は上述のものと同一の基準を用いる。平均化されたクラス比較対照と一致しないシンボルは、等価クラスから取り除かれて、新たに抽出されたシンボルとして扱われる。すなわち、一致しないシンボルは既存の等価クラス等との一致が調べられることになり、当該一致しなかったシンボルについて図４の処理が行われる。
【００３１】
この平均化処理により、正確なクラス比較対照を提供だけでなく、クラスメンバーのビットマップにより占有されたメモリリソースが解放され、比較処理を効率化できる。
【００３２】
マージ処理とは、等価クラスの比較対照がマージ（すなわち結合）できるか否か判定するために、比較対照同士を比較する処理である。つまり、ほぼ同じ比較対照が登録されていれば、それらを統合して比較対照を一つにすることに相当する。このマージ処理が望ましいのは、それにより等価クラスの総数が減らせるからである。等価クラスの数を減らすことができれば、結果的に性能が向上する。好適な実施形態において、マージ処理は、すべてのシンボルが処理されて等価クラスが生成された後に第２の処理として行われることとしている。しかし、マージ処理は、処理のさまざまな段階（チェックポイント）で実行しても構わない。例えば、複数のページからなる文書を処理している際に、各ページの処理が終了するごとに、このマージ処理を実行してもよい。マージ処理は、上述の比較処理をクラスの比較対照の集合に適用して、その中で比較対照同士が一致すれば、２つのクラスがマージされるという処理で実現できる。
【００３３】
好適な実施形態の比較処理の技術（例えば図４のステップ３０３）は改良されたハウスドルフ法に類似した方法である。２つのシンボルの比較は双方向性である。つまり、２つのビットマップ、ＡとＢとが、同じ形状の２つのインスタンスを表しているか否かを判定するために比較されるとする。各ビットマップは、「消灯」しているピクセル（「白い」点）の背景に対して多くの点灯しているピクセル（「黒い」点）を含む。
【００３４】
比較処理を行なうために、元のビットマップの拡張バージョンである２つの新しいビットマップＡδ、Ｂδが計算される。好適な実施形態において、この拡張はトポロジーを維持している。すなわち局所的な連結状態は元と比べて同じであるが、シンボルの境界線はわずかに濃くなっている。拡張バージョンはシンボルの境界線に影響を与えかねない量子化等の結果として生じる「ノイズ」の許容範囲を表す。次に、Ａ内の黒い点の大部分がＢδの形状の内部に存在するか否か、そしてＢ内の黒い点の大部分が形状Ａδの中に存在するか否かを確認するテストを行なう。これらのテストの両方ともに合格すれば、ＡとＢが同じ形状を表現する（すなわち、それらは一致する）との結論が得られる。
【００３５】
このテストの背景にある原理は、印刷およびスキャンのプロセスのモデルにある。ＡとＢが同じシンボルを表現する（又は同じ形状を有する）ならば、それらの境界線は（大部分は）一致するはずである。しかし、スキャンプロセスは、所定の密度でピクセルの点をサンプリングする方法の一つであるので、各シンボルの境界線は１〜２ピクセル程度ずれてしまう可能性がある。これは、サンプリングの際に用いたピクセルのグリッドに起因している。このように、Ａの境界線がＢの境界線に近くに存在するならば、（そのほうがわずかに厚いため）ＡがＢδの中に存在することになるし、逆もまた同様である。ここで、１方向のみのテストでは、例えば文字"Ｏ"と文字"Ｑ"のようにあるシンボルが他のシンボルのサブセットに似ている場合に誤って一致したとの判断が生じる恐れがあるため、両方向のテストが好ましいことに注意されたい。
【００３６】
比較が行なわれる様子を以下の例を参照しながら説明する。この例で、ビットマップＡはビットマップＢと比較される。すなわちＢはある許容範囲内でＡの内部にフィットするかが調べられる。これが肯定的ならば、逆について同じステップが実行される。すなわちＡはＢの内部にフィットするかが調べられる。一致を判定するステップについて、図５のフローチャートに記述する。簡単のため、ここでは１方向の比較のみを説明する。
【００３７】
図５に示すように、ビットマップＡについて、拡張表現されたビットマップＡ（拡張ビットマップＡと称する）のシンボルを生成するため、トポロジーを維持した拡張処理が行われる（ステップ４０１）。この処理のためのステップは、例えば、１９９６年５月３０日に出願された、米国特許出願第０８／６５５，５４６号の「テキストの２値イメージから抽出されたシンボルを比較するための方法および装置」に記述されている拡張方法が用いられる。次に、拡張ビットマップＡとビットマップＢとに基づいてエラービットマップが生成される（ステップ４０２）。このエラービットマップは、ビットマップＢのうち、拡張ビットマップＡに存在しない点灯ピクセルに相当する。好適な実施形態において、エラービットマップは拡張ビットマップＡに基づき、最初に拡張ビットマップＡの値を反転し（すなわち、１を０に変換する、逆もまた同様）、それからビットマップＢと論理ＡＮＤ処理を実行することにより計算される。その結果、１を値として持つエラーピクセルは拡張ビットマップＡ内部のどこでビットマップＢがフィットしていないかを表す。また、各ビットマップは、その原点が左上隅にあるように表現されることに注意されたい。この並び（配置）に基づいて対応するピクセルに対して、論理ＡＮＤ処理を行う。さらにまた、ここで生成されたエラービットマップは従来技術のエラービットマップ（一般的に２つのビットマップの排他的論理和（ＸＯＲ）である）とは異なる点にも注意されたい。本発明では単純なＸＯＲは機能しない。その理由は、ＸＯＲによると、拡張ビットマップＡにビットマップＢがフィットしない場所だけでなく、拡張ビットマップＡがビットマップＢと重ならない場所でもエラーピクセルを１にしてしまうからである。つまり、ＸＯＲでは、単に拡張ビットマップＡとビットマップＢとのうち、ピクセルの値が異なる部分を抽出するに過ぎないからである。そして、エラービットマップのうち、１を値として持つエラーピクセルの個数をカウントし、エラーカウントとする（ステップ４０３）。
【００３８】
次に、ビットマップＢに含まれるシンボルの大きさに基づいてエラー許容範囲が決定される（ステップ４０４）。このエラー許容範囲はノイズの影響や量子化の影響等を考慮に入れたエラーのしきい値を定義する。好適な実施形態では、小さいシンボルには許容範囲を狭く、シンボルの大きさに比例して、大きいシンボルには、許容範囲をより広くなるように、当該特性を有する非線型関数に基づいてエラー許容範囲が決定される。エラー許容範囲の計算は以下により詳細に説明する。ステップ４０３で計算されたエラーカウントが、ステップ４０４で決定されたエラー許容範囲より大きいか否かが判定され（ステップ４０５）、エラーカウントがエラー許容範囲より大きい場合、ビットマップＢは許された許容範囲内まで拡張ビットマップＡの内部にフィットしておらず、一致もしていないとの結論とする（ステップ４０６）。一方、許容範囲内であれば、エラーカウントがエラー密度限界と比較される（ステップ４０７）。ここでエラー密度限界とは、点灯しているエラーピクセルが密集しているグループを識別するためのしきい値である。すなわち、全体としてのエラーカウントが許容範囲内であっても、エラーとなったピクセルが一カ所に集中している場合には、一致したとはせずに、さらに後に説明するステップ４０９に進むのである。好適な実施形態では、エラー密度限界は３である。エラーピクセルとエラー密度限界を伴うチェック（以下に説明する）に合格すれば、一致した、すなわちビットマップＢは拡張ビットマップＡの内部にフィットしているとの結論とし（ステップ４０８）、最適マッチ位置（後に詳細に説明する）を決定するステップ４１３に進む。
【００３９】
エラーカウントがエラー密度限界より大きい場合、エラー密度チェックが実行される（ステップ４０９）。ここで、ステップ４０２で計算されたエラービットマップは「点灯」エラーピクセルが過剰に密集しているグループを検出するために３×３の正方形内で調べられる。任意の３×３正方形がエラー密度限界を超えるか否かが判定される（ステップ４１０）。いずれかの３×３正方形がエラー密度限界を超える場合には、一致していないとの結論とする（ステップ４１１）。一方、すべての３×３正方形でエラー密度限界を超えないと判定された場合には、一致したとの結論とする（ステップ４１２）。
【００４０】
両方向のテストが行なわれた後、一致しているとの結論である場合、シンボルの分類において「最適一致」位置が検出されたと判断される（ステップ４１３）。「最適一致」位置は、等価クラスの比較対照に対して、２つのビットマップを比較したときに生じるエラーが最も少ない位置をいう。既に説明したように、各ビットマップは、左上隅を原点とした座標系になっている。図５で説明した比較の処理は、各ビットマップの原点が完全に整列して（アラインして）いるものと想定して行なわれているが、このように整列していると、必ずしも最適な一致をもたらさないことがある。好適な実施形態においては、抽出されたシンボルに対応しているビットマップは、大部分の「点灯」ピクセルが並んでいる位置を見いだすために、原点及び一致したビットマップに相対的にシフトされる。これは、２つのビットマップ間の論理ＡＮＤ演算を実行し、その結果について「点灯」ピクセルの数をカウントしながらシフトすることにより行なわれる。論理ＡＮＤ演算の結果、「点灯」ピクセルが最も多く並んでいるシフト位置が「最適一致」位置である。この位置はビットマップと共に保存される。等価クラスがコミットされる際に、等価クラスの最も正確な「最終」形態の生成を容易にするために、この最適一致位置を検出しておくことが望ましい。
【００４１】
図２に示されるように、図４及び図５に示した方法に従って、一旦コンポーネントが分類されると、非単独部分（non-singleton）コンポーネント（又はシンボル）と、１以上のコンポーネントのクラスに属するコンポーネントとが、テキストとして識別される（ステップ１３０）。テキスト文字列は、文書の中で複数回出現するのが一般的であり、他の形状が繰り返される可能性は低い。
【００４２】
色の似ている他のコンポーネントと並んで配置されているか、又は近接して配置された未確認として残されたコンポーネントもテキストとして識別される（ステップ１３２）。色は、図１のステップ１１２〜１１４で予め判定されている。依然として未確認のままになっているコンポーネントのうち、上記の処理過程でテキストとしてマークされたコンポーネントと整列して配置されたコンポーネントもまた、テキストとして識別される（ステップ１３４）。最後に、未確認のコンポーネントのうち、テキストコンポーネントの近くにあって、それよりも小さいコンポーネントがテキストとして識別される（ステップ１３６）。これはつまり、例えばドットやカンマ、「Ｉ」ドット、そしてアクセント記号を識別する処理に相当する。
【００４３】
図６に示すように、図１及び図２に示す処理が行われたならば（ステップ５０２）、テキストとして識別されたコンポーネントは、背景画像から取り除かれる（ステップ５０４）。取り除いた結果、背景画像に生じた穴あき部分は、例えばグレイスケール拡張ルーチン等の局所スムージング（local smoothness）の処理により補充される（ステップ５０８）。これにより、背景画像の空間的高周波成分の大部分が除去され、テキスト部分を取り除く前に比べて、背景画像をリンギング（ringing）の少ない状態で、かつ、高い効率で圧縮することが可能となる。テキスト部分と背景画像の領域に対しては、その後適切かつ望ましい処理が行われる（ステップ５０６、５１０）。
【００４４】
さらに、一意の色の数を減らすために各テキスト形状の色をクラスタリングする。つまり、識別されたテキストの色は、元来同じ色であるべきものが、イメージ処理の過程で異なる色として認識され、それぞれ一意の色となってしまうことがあるので、所定の範囲で近接している色は、同じ色であるとするのである。テキストに使われる色数は、実際には少ないと考えられるため、類似の色を有する形状に対し、同じ色を割り当てる。これらの色はトークンベースのイメージ表現でテキスト形状に従ってソートすることができる。
【００４５】
本発明の好適な実施形態では、一つのイメージを処理する方法の実装例を示したが、好適な実施形態は、これに限られるものではない。同一のドキュメントから抜きだされたイメージのグループに対してこの技術を適用すれば、各イメージを別々に扱うよりも、さらによい結果がもたらされると考えられる。すなわち、（例えば文字、「Ｑ」のように）出現頻度の低いテキスト形状は、膨大な文書の中でならば、より多く見いだすことができるのである。従って、単独部分が出現する可能性が低くなり、テキスト／非テキストの判定の正確性が大きくなる。
【００４６】
本発明の好適な実施形態に係るイメージ処理方法が実装されるイメージ処理装置としてのコンピュータシステムについて、図７を参照しつつ説明する。図示するように、コンピュータシステムはバス９０１を介して接続された複数のコンポーネントから構成されている。図示したバス９０１は本発明を不明瞭にしないよう単純化されている。バス９０１は複数のパラレル・バス（例えばアドレス、データおよび状態バス）だけでなく、階層バス（例えばプロセッサバス、ローカルバスおよびＩ／Ｏバス）をも含む構成としてもよい。いずれにせよ、このコンピュータシステムはさらに内蔵メモリ９０３（内蔵メモリ９０３は一般にランダムアクセス又はリードオンリーメモリの組み合わせであることに注意されたい）からバス９０１経由で与えられた命令を実行するためのプロセッサ９０２を含む。このような命令は、上記の図１〜５のフローチャートで概説した処理ステップを実行するために、ソフトウェアで実装されることが望ましい。プロセッサ９０２と内部メモリ９０３は別々のコンポーネントであってもよいし、あるいはアプリケーションに特化したチップ（ＡＳＩＣチップ）のような単一の集積された回路であってもよい。さらに、プロセッサ９０２と内部メモリ９０３の組み合わせは本発明に係る方法を使用するための装置としての回路を構成する。
【００４７】
バス９０１にはまた、文字等を入力するためのキーボード９０４、圧縮されたテキストイメージデータファイル等のデータを保存するための外部記憶装置９０５、カーソルを操作するためのカーソル制御装置９０６、視覚的出力を表示するためのディスプレイ９０７が接続されている。キーボード９０４は一般に標準ＱＷＥＲＴＹキーボードであるが、電話式のキーパッドであってもよい。外部記憶装置９０５は固定式、あるいは着脱可能な磁気又は光ディスクドライブであってよい。カーソル制御装置９０６は、マウスなどのポインティングデバイスに相当し、一般に、特定の機能の実行をプログラムできるボタンやスイッチが付随している。バス９０１にはさらにスキャナ９０８が接続されている。スキャナ９０８は媒体のビットマップ表現（すなわちスキャンされた文書イメージ）を生成するための手段を提供する。
【００４８】
バス９０１に接続できるオプション機器としてプリンタ９０９、ファクシミリ９１０およびネットワーク接続部９１１が含まれてもよい。プリンタ９０９はビットマップ表現を印刷するために用いられる。ファクシミリ９１０は、例えば本発明に係るイメージ処理方法により処理した画像を、さらに圧縮したイメージデータを伝送する。代替手段として、ファクシミリ９１０は本発明に係るイメージ処理方法で処理され、さらに圧縮された文書イメージを伸長する手段を含んでもよい。ネットワーク接続部９１１はイメージデータを含む、各種のデータを送受信するために用いられる。このように、本発明に係るイメージ処理方法で処理されたイメージデータは、ファックスあるいはネットワーク経由で送受信したり、スキャン処理により取得することができる。
【図面の簡単な説明】
【図１】本発明の好適な実施形態を示すフローチャート図である。
【図２】本発明の好適な実施形態を示すフローチャート図である。
【図３】本発明の実装に用いられるテーブルを表す説明図である。
【図４】分類方法を示すフローチャート図である。
【図５】シンボルの判定処理方法を示すフローチャート図である。
【図６】イメージ処理を示すフローチャート図である。
【図７】本発明のシステム例のブロック図である。
【符号の説明】
９０１バス、９０２プロセッサ、９０３内蔵メモリ、９０４キーボード、９０５外部メモリ、９０６カーソル制御機器、９０７ディスプレイ、９０８スキャナ、９０９プリンタ、９１０ファクシミリ、９１１ネットワーク接続部。

Claims

テキストおよび連続階調領域とを含むイメージをイメージ処理装置で処理する方法であって、
しきい値処理を行って、イメージを当該イメージの高コントラスト領域を表すコンポーネントを含む第２のイメージに変換するステップと、
前記しきい値処理された第２のイメージから、白又は黒のピクセルが連結したコンポーネントを抽出するステップと、
前記抽出された白又は黒のコンポーネントから、色の変化度とハミング距離と配置の各所定条件に適合すると判定されるコンポーネントを選択するステップと、
前記選択されたコンポーネントの外形状の大きさに基づいて、前記選択されたコンポーネントを識別してマークをつけることによりクラスに分類するステップと、
１以上のクラスに属する前記選択されたコンポーネントをテキストとして識別するステップと、
類似色のコンポーネントに整列して配置されているコンポーネントであって前記選択されたコンポーネントうち未だ識別されていないコンポーネントを、テキストとして識別するステップと、
前記識別されたテキスト近傍に配置されたコンポーネントであって前記選択されたコンポーネントのうち未だ識別されていないコンポーネントを、テキストとして識別するステップと、
を含むことを特徴とするイメージ処理方法。
請求項１に記載の方法であって、
前記しきい値処理された第２のイメージから、白又は黒のピクセルが連結したコンポーネントを抽出するステップは、どのコンポーネントが、連結した黒ピクセルを含むかを判定するステップと、どのコンポーネントが、連結した白ピクセルを含むかを判定するステップと、白又は黒ピクセルが連結したコンポーネントを反転させるステップとを含み、
前記抽出された白又は黒のコンポーネントから、色の変化度とハミング距離と配置の各所定条件に適合すると判定されるコンポーネントを選択するステップは、元のイメージから各コンポーネントの色を判定して、各コンポーネントの色変化度を判定するステップと、前記色変化度が所定のしきい値より小さいコンポーネントを選択するステップと、前記色変化度により選択された各コンポーネントについて２本のスキャンライン間のハミング距離を計算するステップと、前記各コンポーネントごとに平均ハミング距離を計算するステップと、前記平均ハミング距離が所定のしきい値より小さいコンポーネントを選択するステップと、前記平均ハミング距離により選択されたコンポーネントから、他のコンポーネントと整列して配置されていると判定されるコンポーネントを選択するステップとを含み、
前記方法はさらに、前記識別されたテキスト近傍に配置され、かつ前記識別されたテキストに比べ、相対的に小さいコンポーネントであって、未だ識別されていないコンポーネントをテキストとして識別するステップ、
を含むことを特徴とするイメージ処理方法。
テキストと連続階調領域とを含むイメージを処理するための装置であって、
しきい値処理を行って、イメージを当該イメージの高コントラスト領域を表すコンポーネントを含む第２のイメージに変換する手段と、
前記しきい値処理された第２のイメージから、白又は黒のピクセルが連結したコンポーネントを抽出する手段と、
前記抽出された白又は黒のコンポーネントから、色の変化度とハミング距離と配置の各所定条件に適合すると判定されるコンポーネントを選択する手段と、
前記選択されたコンポーネントの外形状の大きさに基づいて、前記選択されたコンポーネントを識別してマークをつけることによりクラスに分類する手段と、
１以上のクラスに属する前記選択されたコンポーネントをテキストとして識別する手段と、
類似色のコンポーネントに整列して配置されているコンポーネントであって、前記選択されたコンポーネントのうち未だ識別されていないコンポーネントを、テキストとして識別する手段と、
前記識別されたテキスト近傍に配置されたコンポーネントであって、前記選択されたコンポーネントのうち未だ識別されていないコンポーネントを、テキストとして識別する手段と、
前記識別されたテキスト近傍に配置され、かつ前記識別されたテキストに比べ、相対的に小さいコンポーネントであって、未だ識別されていないコンポーネントをテキストとして識別する手段と、
を含むことを特徴とするイメージ処理装置。