(57)【特許請求の範囲】
【請求項１】
整合性を決定すべく、シンボル画像の第１ビットマップをシンボル画像の第２ビットマップと比較する方法であって、
ａ）  シンボル画像の前記第１ビットマップに関してトポロジー保存式の膨張表示を生成するステップと、
ｂ）  シンボル画像の前記第１ビットマップの前記トポロジー保存式の膨張表示をシンボル画像の前記第２ビットマップと比べて、整合性が存在するかどうかを決定するステップと、
ｃ）  整合性が存在する場合には、シンボル画像の前記第２ビットマップのトポロジー保存式の膨張表示を生成するステップと、
ｄ）  シンボル画像の前記第２ビットマップの前記トポロジー保存式の膨張表示をシンボル画像の前記第１ビットマップと比べて、整合性が存在するかどうかを決定するステップと、
ｅ）  整合性が存在する場合には、シンボル画像の前記第１ビットマップがシンボル画像の前記第２ビットマップに整合すると決定するステップと、を含み、
前記ステップａ）が、前記シンボル画像のピクセルの局所的な連続性が破壊されない場合に、前記第１ビットマップの前記トポロジー保存式の膨張表示中のオフピクセルをオンピクセルに変換するサブステップを含み、
前記ステップｂ）が、
ｂ１）シンボル画像の前記第１ビットマップの前記トポロジー保存式の膨張表示のオンピクセルとオフピクセルのオン・オフを逆転させた後に、前記第２ビットマップとの論理積関数を実行することにより、シンボル画像の前記第１ビットマップの前記トポロジー保存式の膨張表示内には存在しない前記第２ビットマップ内のオンピクセルであるエラーピクセルを示すエラービットマップを生成するサブステップと、
ｂ２）シンボル画像の前記第１ビットマップのサイズ及び所定のエラー許容値ファクターに基づいてエラー許容値を決定するサブステップと、
ｂ３）エラーカウントを算出するために前記エラービットマップに示されているエラーピクセルの数をカウントするサブステップと、
ｂ４）前記エラーカウントが前記エラー許容値よりも大きい場合には、整合性が存在しないと決定するサブステップと、
ｂ５）前記エラーカウントが前記エラー許容値以下である場合には、前記エラービットマップ中のいずれかの所定の部分集合が、所定のエラー密度限界を超えるエラーピクセルの数を有しているかどうかを決定するために前記エラービットマップを調べるサブステップと、
ｂ６）いずれかの部分集合によって前記所定のエラー密度限界が超えられている場合には、整合性が存在しないと決定するサブステップと、
ｂ７）いずれの部分集合によっても前記所定のエラー密度限界が超えられていない場合には、整合性が存在すると決定するサブステップと、を含み、
前記ステップｃ）が、前記シンボル画像のピクセルの局所的な連続性が破壊されない場合に、前記第２ビットマップの前記トポロジー保存式の膨張表示中のオフピクセルをオンピクセルに変換するサブステップを含み、
前記ステップｄ）が、
ｄ１）シンボル画像の前記第２ビットマップの前記トポロジー保存式の膨張表示のオンピクセルとオフピクセルのオン・オフを逆転させた後に、前記第１ビットマップとの論理積関数を実行することにより、シンボル画像の前記第２ビットマップの前記トポロジー保存式の膨張表示内には存在しない前記第１ビットマップ内のオンピクセルであるエラーピクセルを示すエラービットマップを生成するサブステップと、
ｄ２）シンボル画像の前記第２ビットマップのサイズ及び所定のエラー許容値ファクターに基づいてエラー許容値を決定するサブステップと、
ｄ３）エラーカウントを算出するために前記エラービットマップに示されているエラーピクセルの数をカウントするサブステップと、
ｄ４）前記エラーカウントが前記エラー許容値よりも大きい場合には、整合性が存在しないと決定するサブステップと、
ｄ５）前記エラーカウントが前記エラー許容値以下である場合には、前記エラービットマップ中のいずれかの所定の部分集合が、所定のエラー密度限界を超えるエラーピクセルの数を有しているかどうかを決定するために前記エラービットマップを調べるサブステップと、
ｄ６）いずれかの部分集合によって前記所定のエラー密度限界が超えられている場合には、整合性が存在しないと決定するサブステップと、
ｄ７）いずれの部分集合によっても前記所定のエラー密度限界が超えられていない場合には、整合性が存在すると決定するサブステップと、を含む、前記比較方法。
【請求項２】
テキストのビットマップ表示からのシンボルを整合化させる方法であって、
ａ）  テキストの前記ビットマップ表示からシンボル画像を抽出するステップと、
ｂ）  以下のサブステップを実行することによって前記シンボル画像を潜在的な整合画像の等価クラスの標本と比較するステップと、
ｂ１）  前記シンボル画像に関してトポロジー保存式の膨張表示を生成するサブステップと、
ｂ２）  前記シンボル画像の前記トポロジー保存式の膨張表示を前記標本と比べて、整合性が存在するかどうかを決定するサブステップと、
ｂ３）  整合性が存在する場合には、前記標本のトポロジー保存式の膨張表示を生成するサブステップと、
ｂ４）  前記標本のトポロジー保存式の膨張表示を前記シンボル画像と比べて、整合性が存在するかどうかを決定するサブステップと、
ｂ５）  整合性が存在する場合には、前記シンボル画像が前記標本に整合すると決定するサブステップ
ｃ）  ステップｂ）が整合性を算出する場合には、前記シンボル画像を前記潜在的整合画像の等価クラスに追加するステップと、
ｄ）  ステップｂ）が整合性を算出しない場合には、すべての潜在的整合画像が比較されるか又は整合性が見出されるまで、すべての潜在的整合画像に関してステップｂ）を繰返すステップと、
ｅ）  前記シンボル画像がいかなる潜在的整合画像とも整合しない場合には、前記シンボル画像に関する新しい等価クラスを作成して辞書の中に記憶するステップと、を含み、
前記サブステップｂ１）が、前記シンボル画像のピクセルの局所的な連続性が破壊されない場合に、前記トポロジー保存式の膨張表示中のオフピクセルをオンピクセルに変換するステップを含み、
前記サブステップｂ２）が、
シンボル画像の前記トポロジー保存式の膨張表示のオンピクセルとオフピクセルのオン・オフを逆転させた後に、前記標本との論理積関数を実行することにより、シンボル画像の前記トポロジー保存式の膨張表示内には存在しない前記標本内のオンピクセルであるエラーピクセルを示すエラービットマップを生成するステップと、
シンボル画像のサイズ及び所定のエラー許容値ファクターに基づいてエラー許容値を決定するステップと、
エラーカウントを算出するために前記エラービットマップに示されているエラーピクセルの数をカウントするステップと、
前記エラーカウントが前記エラー許容値よりも大きい場合には、整合性が存在しないと決定するステップと、
前記エラーカウントが前記エラー許容値以下である場合には、前記エラービットマップ中のいずれかの所定の部分集合が、所定のエラー密度限界を超えるエラーピクセルの数を有しているかどうかを決定するために前記エラービットマップを調べるステップと、
いずれかの部分集合によって前記所定のエラー密度限界が超えられている場合には、整合性が存在しないと決定するステップと、
いずれの部分集合によっても前記所定のエラー密度限界が超えられていない場合には、整合性が存在すると決定するステップと、を含み、
前記サブステップｂ３）が、前記標本のピクセルの局所的な連続性が破壊されない場合に、前記トポロジー保存式の膨張表示中のオフピクセルをオンピクセルに変換するステップを含み、
前記サブステップｂ４）が、
標本の前記トポロジー保存式の膨張表示のオンピクセルとオフピクセルのオン・オフを逆転させた後に、前記シンボル画像との論理積関数を実行することにより、標本の前記トポロジー保存式の膨張表示内には存在しない前記シンボル画像内のオンピクセルであるエラーピクセルを示すエラービットマップを生成するステップと、
標本のサイズ及び所定のエラー許容値ファクターに基づいてエラー許容値を決定するステップと、
エラーカウントを算出するために前記エラービットマップに示されているエラーピクセルの数をカウントするステップと、
前記エラーカウントが前記エラー許容値よりも大きい場合には、整合性が存在しないと決定するステップと、
前記エラーカウントが前記エラー許容値以下である場合には、前記エラービットマップ中のいずれかの所定の部分集合が、所定のエラー密度限界を超えるエラーピクセルの数を有しているかどうかを決定するために前記エラービットマップを調べるステップと、
いずれかの部分集合によって前記所定のエラー密度限界が超えられている場合には、整合性が存在しないと決定するステップと、
いずれの部分集合によっても前記所定のエラー密度限界が超えられていない場合には、整合性が存在すると決定するステップと、を含む、前記整合化の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、テキストの走査画像の処理の分野に関するものであり、より詳細には、テキストの前記走査画像から抽出されたシンボルを等価クラスに分類するために比較することに関する。
【０００２】
【従来の技術】
テキストの走査画像を操作することは、当たり前のことになった。テキストの走査画像は、テキストを包含する媒体のビットマップ表示である。画像圧縮及び光学的文字認識（ＯＣＲ）のような画像処理作業を実行する所定のアプリケーションは、シンボルを等価クラスにグルーピングすることによって実行されることが可能である。言い換えれば、類似の形状を有するシンボルが識別されるのである。シンボルのこのグルーピングは、シンボル分類法とも呼ばれる。画像圧縮の場合、このグルーピングは、当該形状が位置決めされるべき媒体の上における位置を表示する位置情報と共に当該グループが形状（例えば文字又は数字）の単一事例によって表示されることを許容する。ＯＣＲの場合には、グルーピングは、事例が特定の文字であることを表示する。
【０００３】
シンボル整合性に基づく画像圧縮の具体例は、１９９４年４月１２日に発行されたマーク他（Mark et al）の「画像の圧縮のための方法並びに装置（Method and Apparatus For Compression Of Images）」というタイトルの米国特許第５，３０３，３１３号（’３１３号特許）において説明されている。’３１３号特許では、画像は、シンボル整合化に先立って「事前圧縮（Precompressed）」される。’３１３号特許は、そのような圧縮のためにラン長さの符号化を使用することを説明する。シンボルは、ラン長さの表示から抽出される。投票機構が、シンボル整合性の精度を改善するために、複数の類似性テストと共に使用される。’３１３号特許は、更に、テンプレートがシンボル整合性に基づいて修正され得るようにしたテンプレート合成機構をも開示する。
【０００４】
シンボル整合化に関するもう１つの技術は、ハウスドルフ方式として知られている。ハウスドルフ方式は、距離測定技術を使用するものであり、フッテンロクサー他（Huttenlocher et al）によって、１９９１年６月の「ハウスドルフ距離を使用する画像比較（Comparing Images Using the Hausdorff Distance）」（ＴＲ９１−１２１１号）、及び１９９２年１２月の「ハウスドルフ距離を使用する画像比較のためのマルチ解像技術（A Multi-Resolution Technique for Comparing Images Using the Hausdorff Distance）」（ＴＲ９２−１３２１号）において説明されている。これらは、両者とも、コーネル大学のコンピュータ科学学部（Department of Computer Science, Cornell University）によって発行されたものである。ハウスドルフ距離は、バイナリー画像を比較するために使用されることが可能である点集合を比較するための手段である。詳細には、任意の２つの有限点集合Ａ及びＢとすれば、ハウスドルフ距離は、以下のように定義される：
0004098845.tif 000002
そして、｜ａ−ｂ｜は、２つの任意の点ａ及びｂの間の距離である。
【０００５】
関数ｈ（Ａ，Ｂ）は、Ａの各々の点をＢの最も近い点に対するその距離に基づいてランク付けし、最大にランク付けされるそのような点（最も整合しない点）が、その距離の値を指定する。従って、ｈ（Ａ，Ｂ）＝δ（デルタ）である場合、これは、Ａの各々の点がＢの所定の点の距離δの範囲内にあることを意味する。関数Ｈ（Ａ，Ｂ）は、２つの非対称距離の最大値であり、従って、Ｈ（Ａ，Ｂ）＝δである場合、これは、Ａの各々の点がＢの所定の点のδの範囲内にあって、逆もまた同じであることを意味する。ハウスドルフ距離は、このようにして、δの値が大きくなるにつれて画像の間の類似性が小さくなることを表示するものであり、２つのバイナリー画像（即ち有限点集合）の間の類似性の基準を提供するのである。
【０００６】
ハウスドルフ距離に由来するもう１つの技術は、シンボルが比較されているとき、シンボルを膨張することである。シンボルの膨張は、各々の「オン」ピクセルを１組（概ね小さな）の「オン」ピクセルに置換することによって構成される。画像をもう１つの画像と比較する前に、画像を半径１（４個の直接的な隣接物）又は半径１．５（８個の直接的な隣接物）の円板によって膨張することによれば、量子化の影響は、最小化されることが可能である。
【０００７】
【発明が解決しようとする課題】
そのような膨張を使用するビットマップ比較に関する１つの技術が、ここで説明される。任意の２つの画像ビットマップが与えられ、それらをＡ及びＢと呼び、半径δの円板によるＢの膨張をＢδと呼び、Ａ及びＢδの論理積内における「オン」ピクセルの個数をカウントし、Ａの「オン」ピクセルの個数によって割算するものとする。この比率が大きくなれば、Ｂに対するＡの整合性がより良好になる（１．０が完全な整合性を示す）のである。
【０００８】
【課題を解決するための手段】
テキストのバイナリー画像から抽出されたシンボルを等価クラスに分類するために比較する方法並びに装置が開示される。等価クラスへのシンボルの分類は、画像圧縮及び光学的文字認識のような画像処理作業を可能とするために使用される。本発明は、シンボル整合化プロセスの間に発生する不正確な比較によって引き起こされるエラーの個数を最小化しようと努めるものである。そのようなエラーは、典型的には、走査プロセスの間に発生する量子化の影響の故に発生する可能性がある。量子化の影響は、典型的には、ピクセルが黒から白に変化するシンボルの境界線に沿ってエラーを発生させることになる。
【０００９】
本発明は、ビットマップの類似性を比較するハウスドルフ類似方式に基づくものである。ビットマップＡの中に包含されたシンボル及びビットマップＢの中に包含されたシンボルを考慮するものとする。関係する内容は、ビットマップＡの中に包含されたシンボルがビットマップＢの中に包含されたシンボルと整合するかどうかということである。本発明のシンボル整合化ステップは、以下の通りに構成される：  ビットマップＡの中に包含されたシンボルの膨張表示を包含する第１の比較ビットマップを作成し、ビットマップＢの中に包含されたシンボルのサイズに基づいて第１のエラー許容値を決定し、ビットマップＢの中に包含されたシンボルが第１エラー許容値の閾値内において第１比較ビットマップの中に包含される膨張されたシンボルの中に納まるかどうか、更に過剰なエラー密度が存在しないかどうかを決定し、それが肯定である場合には、ビットマップＢの中に包含されたシンボルの膨張表示を包含する第２の比較ビットマップを作成し、ビットマップＡの中に包含されたシンボルのサイズに基づいて第２のエラー許容値を決定し、ビットマップＡの中に包含されたシンボルが第２エラー許容値の閾値内において第２比較ビットマップの中に包含される膨張されたシンボルの中に納まるかどうか、更に過剰なエラー密度が存在しないかどうかを決定し、両者が適合して過剰なエラー密度が存在しない場合には、ビットマップＡがビットマップＢに整合すると決定するのである。最後に、整合性が決定されるとき、ビットマップの一方を他方に対してシフトさせることによって「最適整合性」位置を発見し、最もエラーが少ない位置を識別することになる。
【００１０】
上述したように、量子化の影響は、シンボルの境界線に沿ってエラーを導入する可能性がある。そのような量子化エラーは、２つの様式で処理される：  １）トポロジー保存式の膨張の使用と、２）非線形のエラー許容値機構の使用という２つの様式である。トポロジー保存式膨張は、シンボルは「肥大化」されるがシンボルの局所的なトポロジー（即ち連続性）は変更されないものである。そのような膨張は、「オン」ピクセルに隣接する「オフ」ピクセルに１組の局所的なルールを適用することによって実行される。非線形エラー許容値機構は、小さなシンボルはエラーを少ししか提供しないか又は全く提供しないが、大きなシンボルは釣り合った大量のエラーを提供するはずであるというアイデアに従うものである。
【００１１】
【発明の実施の形態】
図１は、本発明を利用することが可能であるアプリケーションによって実行されるステップを示すフローチャートである。
図２は、本発明の現在の好適な実施例のシンボル比較及び等価クラス分類において使用されるシンボルの辞書のためのデータ構造のブロック表示である。
図３は、本発明の現在の好適な実施例において実行され得るシンボル比較及び等価クラス分類の過程において図２のシンボル辞書を使用するために実行されるステップを示すフローチャートである。
図４は、本発明の現在の好適な実施例において実行され得るビットマップの中に包含されたシンボルの整合化のためのフローチャートである。
図５は、エラー許容値とシンボルのサイズの間の関係を示すダイヤグラムである。
図６は、本発明の現在の好適な実施例における隣接ピクセルのアイデアを示すダイヤグラムである。
図７は、「オン」ピクセルに隣接する「オフ」ピクセルが「オン」されないときの「例外的な」ピクセルの構成を示す。
図８は、図７の構成における「オフ」ピクセルであるが、それにも関わらず「オン」されるようにした、図７の例外に対する例外を示す。
図９は、本発明の現在の好適な実施例が利用されることが可能であるコンピュータベースのシステムのブロックダイヤグラムである。
【００１２】
テキストのバイナリー画像から抽出されたシンボルを等価クラスに分類するために比較する方法並びに装置が開示される。本発明は、光学的文字認識（ＯＣＲ）データ暗号化又は画像圧縮のような種々のアプリケーションにおいて使用されることが可能である。そのようなアプリケーションは、総合的な画像処理システムの一部として、或いはスタンドアロン型のアプリケーションとして提供されることも可能である。本発明の現在の好適な実施例は、テキスト画像データ圧縮を実行するためのコンピュータベースのシステムにおいて機能するソフトウェアとして実行される。そのようなソフトウェアは、磁気ハード・ディスク又はディスケット、ＣＤ−ＲＯＭのような光学ディスク、記憶媒体を有するＰＣＭＣＩＡカードなどのような適当な記憶媒体に分散されるか又は常駐するものであることも可能である。
【００１３】
以下の用語及びそれらの意味は、本文の説明において使用されるものである：
【００１４】
画像とは、媒体のマーキング又は外観を指す。
【００１５】
画像データとは、画像を再現するために使用されることが可能である画像表示を指す。
【００１６】
等価クラスとは、画像の外観を不都合な様式で変化させることなく互いに置換され得るようにした、画像の中に見出される１組のシンボルである。
【００１７】
等価クラスの標本は、画像が圧縮解除され又はその他の方法で再現されるとき、等価クラスのあらゆる要素に置換されることになる、ビットマップである。
【００１８】
抽出されたシンボル又はシンボルは、画像データから獲得された媒体の上におけるマーキングのビットマップ、ラン長さ又はその他の標準的な符号化の形態にある画像表示である。
【００１９】
シンボル辞書又は辞書は、等価クラスを組織化し維持するために使用される構造であり、画像が圧縮解除され又はその他の方法で再現されるときばかりでなく、分類プロセスにおいても使用される。
【００２０】
現在の好適な実施例のシステムは、等価クラスのリスト（辞書とも呼ばれる）を利用し維持するものである。抽出されたシンボルは、それが既存の等価クラスに追加されるべきであるかどうかを決定するために、等価クラスの標本と比較される。整合性が存在しない場合には、新しい等価クラスが、抽出されたシンボルに従って標本として作成される。
【００２１】
上述したように、本発明は、様々なアプリケーションにおいて使用されることが可能である。図１は、本発明を利用するアプリケーションの一般的なステップを説明するフローチャートである。先ず、ステップ１０１で、画像データを作成するために、原稿が走査される。その画像データは、典型的には、画像のビットマップ表示である。以下で説明されるように、走査ステップは、エラー又はノイズを導入する可能性がある量子化の影響を有するものである。続いて、ステップ１０２では、テキスト及び画像の画像クリーンアップ又はセグメント分割のような種々の演算が、画像データに関して実行され得ることになる。本発明によって処理されるものは、テキスト部分である。画像データのテキスト部分は、続いて、ステップ１０３において、各々のピクセルが単一ビットで表現される表示を作成するために、例えば所定の閾値化技術によって、バイナリー表示に変換される。「黒」即ち「オン」のピクセルは、典型的には、二進法の値１によって表現され、一方、「白」即ち「オフ」のピクセルは、二進法の０として表現される。シンボル分類が始まるのは、このポイントである。
【００２２】
先ず、ステップ１０４で、新しい個別的なシンボルがテキスト画像データから抽出される。現在の好適な実施例では、この抽出は、バイナリー画像の接続要素分析によって行われることになる。接続要素分析は、典型的には、隣接するものであり従ってシンボルを形成している「黒」即ち「オン」のピクセルの集合を発見するプロセスである。当該分野では接続要素分析を実行するための様々な技術が知られており、いかなる技術であっても本発明において適切に使用されることになる。抽出されたシンボルは、上部左側のコーナーを原点とする座標系における境界設定ボックスによって表現される。境界設定ボックスは、抽出されたシンボルのピクセルから構成されるバイナリー値を内容とする。続いて、抽出されたシンボルは、ステップ１０５において、抽出されたシンボルの物理的寸法と同じであるか又は類似するものである、シンボル辞書内に記憶されている先に抽出されたいずれかのシンボルに整合するかどうかが決定される。その物理的寸法は、典型的には、そのシンボルを内包する境界設定ボックスによって表現される。分類プロセスの心臓部が、この比較ステップである。整合性が見出される場合、抽出されたシンボルは、ステップ１０６において、整合したシンボルの等価クラスに追加される。新しいシンボルがいずれの等価クラスにも納まらない場合には、ステップ１０７において、新しい等価クラスが作成される。現在の好適な実施例では、既存のクラスに追加されるシンボルの正確な形状は、以下で説明されるように収容プロセスを保留してセーブされる。１０４から１０７までのステップは、その後、ステップ１０８において、画像内におけるすべてのシンボルに関して繰り返される。
【００２３】
現在の好適な実施例で実行されるようなシンボル分類のプロセスは、図２及び図３を参照して説明される。図２は、現在の好適な実施例の整合化プロセスにおいて使用される、本文ではシンボル辞書と呼ばれるデータ構造のブロック表示である。図２を参照すると、テーブル２０１は、シンボルの境界設定ボックスの寸法によってインデックスを付けられる内容を有する。例えばテーブル・エントリー２０４のような各々のテーブル・エントリーは、連結式データ構造によって連結される１つ又はそれ以上の等価クラス２０２を指示する（即ち指し示す）ものであることが可能である。各々の等価クラス２０２は、当該クラスの中のシンボル２０３に関する事例のもう１つの連結式リストによって構成される。シンボルの各々の事例は、事例が見出され得る媒体の上における位置情報を内包するデータ構造、事例のビットマップ、及び「最適整合位置」を識別する情報によって表現される。以下で詳細に説明されるように、最適整合位置は、事例がクラスの標本と最適に整合する実行可能なシフト位置を表示する。
【００２４】
現在の好適な実施例において、テーブル２０１は、ハッシュテーブルである。ハッシュテーブルは、ハッシュテーブルのサイズを基準として応答する任意の関数を使用して「多数から少数への」マッピングが行われる周知の構造である。この特性は、同じ寸法のものであるシンボルの連結リストを維持し且つそれにアクセスするために使用される。連結リストは、リスト内の節点の事例がリスト内における次の節点を指し示す周知の構造である。図２において説明されたデータ構造は、本発明の範囲を限定するものとしては意図されていないことが留意されるべきである。等価クラスの機構及びそれに対する比較を維持するための代替的なデータ構造の使用は、本発明の精神及び範囲から引き離すことにはならない。
【００２５】
図２において説明されたシンボル辞書は、潜在的なシンボル整合性の照合を可能にするために使用されるダイナミックな構造である。図３のフローチャートは、シンボル辞書の使用に関して整合化プロセスを説明するものである。先ず、ステップ３０１では、ハッシュ関数が、潜在的な整合性を内包するハッシュテーブル・エントリーを発見するために、抽出されたシンボルの寸法（即ち幅及び高さ）に関して実行される。このエントリーは、ステップ３０２において、チェックすべき等価クラスが存在するかどうかを決定するために審査を受ける。そのエントリーは、それが空ではなく、連結リストが先行する整合化の試みにおいて既に完全にトラバースされていない場合には、検査するための等価クラスを有する。等価クラスが識別されると、続いて、ステップ３０３において、抽出されたシンボルと等価クラスの標本が整合するかどうかが決定される。等価クラスの標本は、１）等価クラスが作成される原因となったシンボルであるか、又は２）等価クラスを「収容（committing）」する過程で作成される平均的なシンボル（以下で説明される）のいずれかである。シンボル比較の細部は、以下で詳細に説明される。いずれにせよ、連結リスト内の標本の１つとの整合性が生じる場合には、続いて、そのシンボルは、ステップ３０４において、対応する等価クラスに追加される。シンボルを等価クラスに追加することは、それを等価クラスのデータ構造に追加することを必然的に伴う。整合性が生じない場合には、連結リストが、ステップ３０５において、更にトラバースされ、ステップ３０２によって比較すべきもう１つの等価クラスが存在するかどうかの決定が為される。
【００２６】
現在のシンボルテーブル・エントリーに関して連結リスト内に等価クラスがもはや存在しない場合、ステップ３０６において、すべての類似サイズの等価クラスがチェックされたかどうかを決定するためのチェックが為される。それらがチェックされていない場合には、ハッシュテーブル・エントリーを決定するために使用されたサイズパラメータは、類似サイズのものに修正され、ステップ３０１によって新しいテーブル・エントリーがアクセスされる。すべての類似サイズの等価クラスがチェックされていた場合には、ステップ３０７によって新しい等価クラスが作成される。この新しい等価クラスは、抽出されたシンボルのオリジナルのサイズに対応するテーブル・エントリーの連結リスト内におけるシンボル辞書の中に配置される。
【００２７】
シンボル分類の過程において実行される２つのその他のステップは、シンボル辞書管理として考察されることが可能である。一方は収容であり、もう一方は等価クラスの併合である。収容は、抽出されたシンボルの所定の個数（例えば１０個）が等価クラスの一部になるときに呼び出されるプロセスである。収容プロセスは、平均的な等価クラスの標本が最終決定され、即ちそのクラスを表示するビットマップが収容されることになる、プロセスである。このステップの前には、等価クラスの標本は、単にそのクラスを作成する原因となった第１のシンボルであるに過ぎなかったのである。平均的なクラス標本は、そのクラス内におけるすべてのシンボルに関するより正確な表示である。これは、クラスの要素であるシンボルを表示するビットマップを「平均化」することによって獲得される。平均化は、異なったピクセル位置の各々において「オン」ピクセルを有する（それらの「最適整合」位置合わせにおける）クラスの要素の個数のカウントを内容とするヒストグラムを維持することによって達成される。標本は、このヒストグラムを閾値化することによって生成される。即ち、最終的な標本において、対応するピクセル位置が所定の閾値を越える場合に、ピクセルが「オン」になる。閾値は、標本内における「オン」ピクセルの個数がクラスの要素内における「オン」ピクセルのメジアン数値に可能な限り近いようにして選択される。
【００２８】
一旦、最終的な標本が生成されると、すべてのシンボルは、それらが平均的なクラス標本に整合することを確認するためにチェックを受ける。このチェックは、上述したものと同じ判定基準を使用する。平均的なクラス標本に整合しないそれらのシンボルは、等価クラスから取り除かれ、新たに抽出されたシンボルとして処理される（即ち、それらは既存の等価クラスなどに対して整合化される）。
【００２９】
より正確なクラス標本を提供する以外にも、平均化は、クラスの要素のビットマップによって占有されるメモリ資源を解放することによって総合的な比較プロセスを促進するものである。
【００３０】
併合は、等価クラスの標本が比較されて、それらが併合される（即ち結合される）ことが可能かどうかを決定するプロセスである。併合は、それが等価クラスの総数を削減するので、望ましいことである。等価クラスの個数を削減することは、結果としてパフォーマンスを改善する。現在の好適な実施例では、併合は、すべてのシンボルが処理されて等価クラスが作成された後に第２のパスとして生じる。しかしながら、それは、当該プロセスにおける様々なチェックポイントにおいて（例えばマルチページ文書の各々のページが処理された後に）実行されることも可能である。その併合プロセスは、上述の整合化プロセスがクラス標本の集合に適用され、それらの標本が整合する場合に２つのクラスが結合されるというものであるに過ぎない。
【００３１】
等価クラスの収容及び併合のプロセスは、以下に説明される画像圧縮／圧縮解除の実施例に特に関連するものである。
【００３２】
上述したように、シンボルの整合化は、分類プロセスの心臓部である。現在の好適な実施例の整合化技術は、改良されたハウスドルフ類似の方式である。２つのシンボルの比較は、両方向性である。２つのビットマップＡ及びＢが、同じ形状の２つの事例をそれらが表示しているかどうかを決定するために比較されることを想定するものとする。各々のビットマップは、「オフ」（「白い」点）である背景の点に対してオン（「黒い」点）にされる数多くの点を内包する。
【００３３】
整合化の目的のため、２つの新しいビットマップが、オリジナルのビットマップの膨張したバージョンであるＡδ及びＢδとして計算される。現在の好適な実施例では、その膨張は、トポロジー保存式である。即ち、局所的な連続性はオリジナルと同じであるが、シンボルの境界線が僅かに肥大化されるのである。そのような膨張のための好適な技術は、以下で詳細に説明される。膨張したバージョンは、シンボルの境界線を混乱させる可能性がある量子化及びその他の影響から生じる妥当な「ノイズ」に関して許容範囲を提示するものである。続いて、Ａ内における黒い点の大部分がＢδの形状の内部に位置するかどうか、更にＢ内における黒い点の大部分が形状Ａδの内部に位置するかどうかを確認するテストが行われる。これらのテストの両方に合格すると、Ａ及びＢは、同じ形状を表示する（即ちそれらは整合する）ものであると結論される。
【００３４】
このテストの背後の合理性は、Ａ及びＢが同じシンボルを表示する（即ち同じ形状を有する）ならば、それらの境界線が（大部分に関して）整合するはずであるという印刷及び走査プロセスのモデルにある。しかしながら、走査プロセスは所定密度における点のサンプリングの１つであるので、各々のシンボルの境界線はサンプリングを実行するピクセル・グリッドの故に１つ又は２つのピクセルだけシフトされてしまうかもしれない。従って、Ａの境界線がＢの境界線に接近して位置するならば、ＡはＢδ（それは１ビット肥大しているので）の内部に位置することになり、逆もまた同じであることになる。一方の方向のみを使用することは、１つのシンボルが他のシンボルの部分集合と似ているとき、例えば文字「Ｏ」及び文字「Ｑ」のような場合、間違った整合性を算出する可能性があるので、両方向のテストが必要であると留意されるべきである。
【００３５】
比較が為される様式は、以下の具体例を参照して説明される。この具体例において、ビットマップＡは、ビットマップＢに対して比較される。即ち、Ｂが所定の許容範囲内でＡの内部に納まるか？である。これが肯定で答えられ得る場合には、「他の」側面、即ちＡがＢの内部に納まるか？に関して同じステップが実行される。整合性を決定する各ステップは、図４のフローチャートにおいて説明される。簡潔さのために、比較の一方の側面のみが説明されている。図４を参照すると、ステップ４０１では、トポロジー保存式の膨張が、ビットマップＡ内のシンボルの膨張表示（膨張ビットマップＡと呼ばれる）を作成するために、ビットマップＡにおいて実行される。そのような膨張を実行するステップは、以下で詳細に説明される。続いて、ステップ４０２では、膨張ビットマップＡ及びビットマップＢに関してエラービットマップが計算される。エラービットマップは、膨張ビットマップＡの中には存在しないビットマップＢ内における「オン」ピクセルを表示する。現在の好適な実施例において、エラービットマップは、膨張ビットマップＡに関するものであり、先ず膨張ビットマップＡの値を逆転させ（即ち１を０に変換し、逆もまた同じく変換する）、続いてビットマップＢとの論理積関数を実行することによって計算される。その結果、１の値を有するエラーピクセルは、ビットマップＢが膨張ビットマップＡの内部に納まらないことを表示する。更に、各々のビットマップは、その原点が上部左側のコーナーに位置するようにして表示されることが留意されるべきである。この位置合わせに基づいて、論理積が対応するピクセルにおいて実行されるのである。本文において生成されるエラービットマップが、先行技術のエラービットマップ（典型的には２つのビットマップの排他的論理和）とは異なっていることもまた注目に値する。排他的論理和は、ビットマップＢが膨張ビットマップＡの内部に納まらない場合だけでなく、膨張ビットマップＡがビットマップＢにオーバーラップしない場合にも、値１のエラーピクセルを作成するので、単純な排他的論理和は、本発明では機能しないことになる。１の値を有するエラービットマップ内におけるエラーピクセルの個数は、続いて、ステップ４０３において、エラーカウントを算出するようにカウントされる。
【００３６】
続いて、ステップ４０４では、エラー許容値が、ビットマップＢの中に内包されるシンボルのサイズに基づいて決定される。このエラー許容値は、ノイズの影響及びその他の量子化の影響を考慮に入れてエラーの閾値を定義する。現在の好適な実施例では、エラー許容値は、小さなシンボルには許容値が全く存在せず、大きなシンボルには釣り合った大きな許容値が存在するという特性を有する非線形の関数に基づいて決定される。エラー許容値の計算は、以下で詳細に説明される。続いて、ステップ４０５では、エラーカウントが、計算されたエラー許容値より大きいかどうかが決定される。エラーカウントがそのエラー許容値より大きい場合、ビットマップＢは、その許容された範囲内において膨張ビットマップＡの内部には納まらず、ステップ４０６で示されるように、整合は存在しない。その他の場合には、エラーカウントは、ステップ４０７において、エラー密度限界に対して比較される。エラー密度限界は、「オン」エラーピクセルの接近したグルーピングを識別するための閾値である。現在の好適な実施例において、エラー密度限界は、３である。エラーピクセル及びエラー密度限界に関わるチェック（以下に説明される）に合格すると、ステップ４０８で示されるように、整合性が存在する。即ち、ビットマップＢは、膨張ビットマップＡの内部に納まる。続いて、処理は、ステップ４１３に進んで、最適整合位置を決定することになる（以下でより詳細に説明される）。
【００３７】
エラーカウントがエラー密度限界より大きい場合には、エラー密度チェックが実行される。ここでは、ステップ４０２で計算されたエラービットマップが、ステップ４０９において、「オン」エラーピクセルの過剰なグルーピングを検出すべく、３×３平方増分における検査を受ける。ステップ４１０では、いずれかの３×３平方がエラー密度限界を超過するかどうかの決定が為される。いずれかの３×３平方がエラー密度限界を超過する場合、ステップ４１１で示されるように、整合性は存在しない。いかなる３×３平方もエラー密度限界を超過しないと決定される場合には、ステップ４１２で示されるように、整合性が存在することになる。
【００３８】
両方の方向がテストされ整合性が決定されると、シンボル分類の実施例は、ステップ４１３において「最適整合」位置が識別されるように決定されたことになる。「最適整合」位置は、２つのビットマップが比較されるときに最も少ないエラーを算出する等価クラスの標本に対する位置として定義される。上述したように、各々のビットマップは、上部左側のコーナーを原点として有する座標系において方向付けされている。図４に関して説明された比較は、各々のビットマップの原点が完全に位置合わせされるものと想定して実行される。しかしながら、この位置合わせは、最適の整合性を算出しないかもしれないのである。現在の好適な実施例では、抽出されたシンボルに対応するビットマップは、大部分の「オン」ピクセルが位置合わせされる位置を見出すべく、原点及び整合したビットマップに対してシフトされる。これは、２つのビットマップをシフトさせ、それらの間で論理積関数を実行し、その結果における「オン」ピクセルの個数をカウントすることによって実行される。大部分の「オン」ピクセルを備えてシフトされた位置が、「最適整合」位置なのである。この位置は、ビットマップと共にセーブされる。この最適整合位置を識別することは、等価クラスが収容されるときにそれが等価クラスの最も正確な「最終的」表示の生成を容易にするので、好都合である。
【００３９】
走査プロセスにおいて導入される量子化の影響の故に、シンボルを比較するとき、所定の量のエラーは、容認されるものとして決定される。現在の好適な実施例では、エラー許容値は、文字のサイズに関して非線形である。Ａ及びＢが小さなシンボル（例えば１インチ当り３００ドットで走査される６ポイントの文字）を内容とするビットマップである場合には、それらが、両方向のテストに厳格に合格しなければならない、即ち、Ａのいかなるピクセルも膨張Ｂの外部には全く存在せず、Ｂのいかなるピクセルも膨張Ａの外部には全く存在すべきではないと主張することは、合理的である。逆に、Ａ及びＢが大きなシンボル（例えば１インチ当り３００ドットで走査される１２ポイントの文字）を内容とするビットマップである場合には、厳格な両方向のテストは、シンボル境界線の間の差もまたそれに比例して大きくなり得るので、余りに厳格である可能性がある。そこで、大きなシンボルに関しては、Ａの点のｋ 以外のすべてが膨張Ｂの内部に位置し、且つＢの点のｋ 以外のすべてが膨張Ａの内部に位置することを主張して、ゼロではないエラー許容値が両方向のテストにおいて使用されることになる。
【００４０】
上述したように、使用されるエラー許容値は、Ａ及びＢの「サイズ」の関数であり、両方向テストの各々の側面に関して別個に計算される。シンボルの「サイズ」は、ここでは、シンボル境界設定ボックスの寸法によって単純に測定されるものではなく、シンボルの境界線の長さ（それは「オフ」ピクセルに隣接しているシンボルのビットマップの「オン」ピクセルの個数である）によって測定される。エラー許容値は、Ａ（又はＢ）のサイズが所定の閾値のシンボルサイズ（１００ピクセル）以下である間は、ゼロに留まり、続いて、第２の閾値サイズ（２００ピクセル）までは、「ターゲット」エラー許容値に随伴する比率で増大し、その後、再びエラー許容値が「ターゲット」比率に基づくようにした第３の閾値サイズ（３００ピクセル）までは、２×比率で増大することになる。
【００４１】
エラー許容値は、境界線ピクセルに対するエラーピクセルの比率として定義される。エッジピクセルの個数の３パーセントのエラー許容値は、このモデルにおいて使用されるとき、大部分の文書における妥当な結果を提供するものであると実験的に決定された。しかしながら、上述したように、線形のエラー許容値になってしまうものを単純に使用することは、不十分である。以下のルールは、現在の好適な実施例のエラー許容値の非線形的な性質を説明するものである：
（１）  ｅ（Ａ）をＡ内におけるエッジ（境界線）黒ピクセルの個数とする。
（２）  ｆを「ターゲット」エラー許容値、即ちエッジピクセルの個数の３パーセント（直線の傾き）とする。
ｆ*ｅ（Ａ）≦３ならば、エラー許容値は、０。
３＜ｆ*ｅ（Ａ）≦６ならば、エラー許容値は、ｆ*ｅ（Ａ）−３。
６＜ｆ*ｅ（Ａ）ならば、エラー許容値は、ＭＩＮ（３＋２*（ｆ*ｅ(Ａ)−６），ｆ*ｅ(Ａ)）。
【００４２】
図５は、適用されたこれらのルールのグラフ表示である。図５を参照すると、水平軸５０１は、ｆ*ｅ（Ａ）の値を表わし、垂直軸５０２は、エラー許容値を表わしている。線５０７は、シンボルサイズとエラー許容値の間の関係をプロットするものである。上記のルールを適用すると、線５０７は、以下のような傾斜の値を有する：
（１）  ｆ*ｅ（Ａ）の値が０から３の場合、それは、線分５０３で示されたように傾斜０を有する。
（２）  ｆ*ｅ（Ａ）の値が３から６の場合、それは、線分５０４で示されたように傾斜１（即ち０．０３のターゲットエラー許容値）を有する。
（３）  ｆ*ｅ（Ａ）の値が６から９の場合、それは、線分５０５で示されたように傾斜２（即ちターゲットエラー許容値の２倍）を有する。
（４）  ｆ*ｅ（Ａ）の値が９を越える場合、それは、線分５０６で示されたように傾斜１を有する。
【００４３】
ここで、値３は、第１の閾値５０８を表わし、値６は、第２の閾値５０９を表わし、値９は、第３の閾値５１０を表わしている。
【００４４】
エラー許容値を見積もるためにその他の関数が使用されることも可能であるが、そのような関数は、小さな形状に関しては、いかなるエラーも許容されるべきではなく、大きな形状に関しては、より多くのエラーが許容され得るという特性を有するものでなければならない。
【００４５】
上述したように、整合化プロセスにおいて生成される新しいビットマップ、即ちＡδ及びＢδは、オリジナルのビットマップの膨張表示である。現在の好適な実施例では、トポロジー保存式の膨張が実行される。トポロジー保存式膨張においては、不明瞭ではあっても知覚的には重要である、形状の様相が保存される。これは、文字「ｈ」及び「ｂ」を比較することによって例証される。それらの総体的な形状は、「ｈ」の底部における間隙を除けば、全く同様である。単純に線を肥大化させることは、「ｈ」の底部における間隙を閉鎖して、膨張した「ｈ」（その「ｈ」は膨張した「ｂ」の中に明らかに納まることになる）の内部に「ｂ」を納めてしまうという結果を生じるかもしれない。これは、それらの形状を誤って整合させてしまうことになる。
【００４６】
トポロジー保存式膨張では、「オン」ピクセルの局所的なトポロジーが検査を受け、「オフ」ピクセルは、それを「オン」にすることがオリジナルのビットマップの中に存在する小さな間隙又は孔を閉鎖しない場合にのみ、膨張において「オン」にされる。従って、膨張した「ｈ」は、それでもなお底部における間隙を有し、「ｂ」は、この膨張した形状の境界線の内部には納まらないのである。それらの形状がそのような小さな間隙を内包しない場合には、この膨張は、通常の膨張と同等なものである。
【００４７】
トポロジー保存式膨張技術は、任意の「オフ」ピクセルの膨張値を決定する１組の局所的なルールによって構成される。各々の「オフ」ピクセルは、オリジナルの未膨張のビットマップを参照して検分される。そこで、実際には、作成されている膨張表示は、すべての「オン」ピクセルを直接的にコピーし、「オフ」ピクセルのいずれのものが局所的なルールに基づいて「オン」にされるべきであるかどうかを決定することによって達成される。
【００４８】
図６から図８を参照して説明されるものは、１ピクセルだけ膨張（４個の連続隣接物）する場合のルールである。同様のルールは、２つ又はそれ以上のピクセルだけ膨張するためにも使用されることになる。実際に使用される膨張の量は、オリジナルの画像の印刷密度及び走査密度を包含する様々なファクターに従属することになる。とにかく、図６を参照すると、現在の好適な実施例の膨張は、１２個の隣接するピクセル（シンボル「？」によって夫々に指示される）の値に基づいて任意の「オフ」ピクセル（シンボル「＠」によって指示される）をオンにするか否かを決定することによって機能する。図６から理解され得るように、検査されるピクセルの配列は、水平及び垂直の隣接物がピクセル２個分の深さで検査され、対角線の隣接物がピクセル１個分の深さで検査されるという基本的な特性を有する。
【００４９】
本発明のトポロジー保存式膨張方式の概略的な原理は、その直接的な４個の隣接物（即ち水平方向又は垂直方向の隣接物）の１つがオンである場合には、この１３個のピクセル隣接物の内部における局所的な連続性を変更することにならない限り、中心のピクセルを「オン」にするということである。以下のルールがこの原理を実行するものとして決定された。簡潔さのために、左側の隣接物がオンである場合のみが説明される。その他の場合は、これらのパターンの９０度の回転によって獲得される（３個のその他の隣接物：  上側、右側及び下側に対応する）。シンボル＠は、膨張において「オン」にされるべきか否かに関して検査を受けている「オフ」ピクセルを指示するものであることが想起される。それらのルールを説明する図７及び図８において、シンボルＯは、隣接する「オフ」ピクセルを指示し、シンボルＸは、隣接する「オン」ピクセルを指示している。
【００５０】
パターンＸ＠は、即ち左側の隣接物が「オン」ピクセルである場合は、それが図７で示された例外ピクセル配列の１つであるときを除いて、「オン」を算出する。隣接する所定個数のピクセルのみが例外を引き起こすことが留意されるべきである。これらの場合、その他のピクセルの値が何であるかは問題にならない。図７で示された例外の各々は、評価されているピクセルに隣接する可能性がある孔又は間隙を表わすものである。しかしながら、図８は、図７の例外に対する例外を示している。ピクセル隣接物が図８の配列の１つである場合、評価されているピクセルは、「オン」にされる。
【００５１】
従って、総合的には、総計で４８のテストに関して、夫々に、４つの例外と、それらの例外に対する７つの例外とを備えた４つのルール（左側、右側、上側及び下側の４方向に関する）が存在する。現在の好適な実施例では、これらのテストは、その成果（ピクセルのオン又はオフ）に対する１３ビット（「＠」ピクセルの廻りにおける隣接物）のテーブル・マッピング・パターンを構築するために使用される。
【００５２】
現在の好適な実施例では、ビットマップが膨張されると、それは、走査されて、すべてのピクセル位置が検査される。「オフ」ピクセルに遭遇すると、１３個のピクセルの隣接物は、上述のような成果テーブルの中に１３ビットのインデックスを作成するために使用される。検査されているピクセルは、その後、テーブルの結果に応じて「オン」にされることになる。
【００５３】
実際において、この膨張方式は、先行技術に関連して簡潔に説明されたハウスドルフのビットマップ比較方式を大きく改良するものである。これは、小さな文字及び「微粒子」形状を備えたその他のトークンのビットマップに関して特に重要である。
【００５４】
上述したように、本発明は、好ましくは、テキストの画像圧縮及び圧縮解除のためのシステムにおいて具体化される。機械印刷されたテキストを内容とする走査画像は、等価クラスの中に見出されるシンボルをグルーピングすることによって圧縮されることが可能である。このシステムでは、シンボル分類器が使用されて、抽出されたシンボルを独特な標本によって表示される等価クラスの中に分類する。作成される等価クラスの個数は、抽出されたシンボルの総数よりも非常に少ないことになる。一旦、すべての抽出されたシンボルが等価クラスに分類されてしまうと、圧縮された出力ストリームが作成される。作成された出力ストリームは、標本のＩＤ／位置ペアを随伴する標本から構成される辞書によって構成される。
【００５５】
画像が圧縮解除されるとき、それらのペアの各々は、識別された標本の事例が指定された位置に配置されるようにして処理される。これは、オリジナルのテキスト画像が再現されるまで、すべてのペアに関して継続する。
【００５６】
以上の説明では、走査画像は、１インチ当り３００ドット（ｄｐｉ）の解像度を有するスキャナを使用して作成されるものと想定された。本文で説明された様々な閾値は、この解像度に基づいている。従って、走査画像が３００ｄｐｉとは異なる解像度を備えたスキャナを使用して作成された場合、異なった閾値が使用され得ることが、当該分野の熟練技術者には明白であろう。例えば、テキストを形成する媒体が３００ｄｐｉの解像度を有するプリンタを使用して作成され、走査画像を形成する媒体が６００ｄｐｉの解像度を有するスキャナを使用して作成された場合には、膨張値における更なる修正もまた必要であるかもしれない。この場合には、本文で説明されたピクセル１個分とは異なって、ピクセル２個分までの膨張表示を作成することが必要になるかもしれないのである。
【００５７】
本発明の現在の好適な実施例が使用されることが可能であるコンピュータベースのシステムは、図９を参照して説明される。図９を参照すると、当該コンピュータベースのシステムは、バス９０１を介して連結される多数のコンポーネントから構成される。ここに示されたバス９０１は、本発明を分かりにくいものにしないために簡略化されている。バス９０１は、複数の並列バス（例えばアドレス・バス、データ・バス及びステータス・バス）ばかりでなく、バスの階層（例えばプロセッサ・バス、ローカル・バス及び入出力バス）から構成されても構わない。とにかく、当該コンピュータシステムは、更に、内部メモリ９０３（この内部メモリ９０３は、典型的には、ランダムアクセス・メモリ又はリードオンリー・メモリの組合せであることに留意すること）からバス９０１を介して提供される命令を実行するためのプロセッサ９０２をも含んで成る。そのような命令は、好ましくは、図１、図３及び図４のフローチャートにおいて以上のように概説された処理ステップを実施し、更に、図６から図８に関連して説明されたトポロジー保存式膨張に関するルールをも実行するために、ソフトウェアにおいて実行されるものである。プロセッサ９０２及び内部メモリ９０３は、個別のコンポーネントであっても良いが、特定用途向け集積回路（ＡＳＩＣ）チップのような単一の統合された装置であっても良い。更に、プロセッサ９０２及び内部メモリ９０３の組合せは、本発明の機能性を実行するための回路構成をも含んで成る。
【００５８】
更に、バス９０１には、英数字入力を入力するためのキーボード９０４、圧縮されたテキスト画像のデータファイルのようなデータを記憶するための外部記憶装置９０５、カーソルを操作するためのカーソル制御装置９０６、及び視覚的出力を表示するためのディスプレイ９０７が連結される。キーボード９０４は、典型的には、標準的なクエーティ（ＱＷＥＲＴＹ）キーボードであることになるが、電話機のようなキーパッドであっても構わない。外部記憶装置９０５は、固定式であるか又は取外し可能である磁気的又は光学的なディスクドライブであっても良い。カーソル制御装置９０６は、典型的には、所定の機能のパフォーマンスがそれによってプログラムされることが可能であるボタン又はスイッチを付随して有することになる。バス９０１には、スキャナ９０８もまた連結される。スキャナ９０８は、媒体のビットマップ表示（即ち走査された文書画像）を作成するための手段を提供する。
【００５９】
バス９０１に対して連結されることが可能である光学的な要素は、プリンタ９０９、ファクシミリ要素９１０及びネットワーク接続９１１を包含することになる。プリンタ９０９は、ビットマップ表示を印刷するために使用されることが可能である。ファクシミリ要素９１０は、本発明を使用して圧縮された画像データを送信するために使用される要素を内包することも可能である。二者択一的に、ファクシミリ要素９１０は、本発明を使用して圧縮された文書画像の圧縮解除のための要素を包含することもまた可能である。ネットワーク接続９１１は、画像データを内包するデータを受信及び／又は送信するために使用されることになる。従って、本発明によって利用される画像データは、走査プロセスを介して、受信したファクシミリを経由して、或いはネットワークによって入手されることも可能である。
【図面の簡単な説明】
【図１】  本発明を利用することが可能であるアプリケーションによって実行されるステップを示すフローチャートである。
【図２】  本発明の現在の好適な実施例のシンボル比較及び等価クラス分類において使用されるシンボルの辞書のためのデータ構造のブロック表示である。
【図３】  本発明の現在の好適な実施例において実行され得るシンボル比較及び等価クラス分類の過程において図２のシンボル辞書を使用するために実行されるステップを示すフローチャートである。
【図４】  本発明の現在の好適な実施例において実行され得るビットマップの中に包含されたシンボルの整合化のためのフローチャートである。
【図５】  エラー許容値とシンボルのサイズの間の関係を示すダイヤグラムである。
【図６】  本発明の現在の好適な実施例における隣接ピクセルのアイデアを示すダイヤグラムである。
【図７】  「オン」ピクセルに隣接する「オフ」ピクセルが「オン」されないときの「例外的な」ピクセルの構成を示す。
【図８】  図７の構成における「オフ」ピクセルであるが、それにも関わらず「オン」されるようにした、図７の例外に対する例外を示す。
【図９】  本発明の現在の好適な実施例が利用されることが可能であるコンピュータベースのシステムのブロックダイヤグラムである。
【符号の説明】
２０１  テーブル、２０２  等価クラス、２０３  シンボル、２０４  テーブル・エントリー、９０１  バス、９０２  プロセッサ、９０３  内部メモリ、９０４  キーボード、９０５  外部記憶装置、９０６  カーソル制御装置、９０７  ディスプレイ、９０８  スキャナ、９０９  プリンタ、９１０  ファクシミリ要素、９１１  ネットワーク接続
【図１】
0004098845.tif 000003
【図２】
0004098845.tif 000004
【図３】
0004098845.tif 000005
【図４】
0004098845.tif 000006
【図５】
0004098845.tif 000007
【図６】
0004098845.tif 000008
【図７】
0004098845.tif 000009
【図８】
0004098845.tif 000010
【図９】
0004098845.tif 000011