(57)【特許請求の範囲】
【請求項１】
クラスタリングシステムであって、
ドキュメントからマークを抽出するマークエクストラクタと、
既存クラスタを格納するライブラリであって、前記ライブラリは、ローカルライブラリとグローバルライブラリとを備え、前記ローカルライブラリは、前記ドキュメントのカレントページから追加された既存クラスタを備え、前記グローバルライブラリは、前記ドキュメントの先行ページから追加された既存クラスタを備えたライブラリと、
前記ドキュメントから抽出されたマークの少なくとも１つのプロパティを、前記ライブラリに格納されたマークの既存クラスタのマッチングプロパティと比較して、マッチしている既存クラスタを特定するように動作するプロパティマッチングコンポーネントと、
前記ドキュメントから抽出されたマークを、前記マッチしている既存クラスタと比較し、前記マッチしている既存クラスタの中からマッチしているクラスタを特定するように動作するシンボルマッチングコンポーネントと
を備えたことを特徴とするクラスタリングシステム。
【請求項２】
前記既存クラスタのマッチングプロパティが格納されたテーブルをさらに備えたことを特徴とする請求項１に記載のクラスタリングシステム。
【請求項３】
前記マークの少なくとも１つのプロパティは、ｘサイズとｙサイズとであり、前記マッチングプロパティは、前記既存クラスタのｘサイズとｙサイズとを備えたことを特徴とする請求項１に記載のクラスタリングシステム。
【請求項４】
前記マークの少なくとも１つのプロパティは、インクサイズであり、前記マッチングプロパティは、前記既存クラスタのインクサイズを備えたことを特徴とする請求項１に記載のクラスタリングシステム。
【請求項５】
前記マークの少なくとも１つのプロパティは、サイズ変更マーク画像であり、前記マッチングプロパティは、前記既存クラスタのサイズ変更画像を備えたことを特徴とする請求項１に記載のクラスタリングシステム。
【請求項６】
前記プロパティマッチングコンポーネントは、許容範囲のプロパティを計算するように動作することを特徴とする請求項１に記載のクラスタリングシステム。
【請求項７】
前記プロパティマッチングコンポーネントは、前記マークが前記既存クラスタとミスマッチのとき、前記マークを新クラスタとして追加するように動作することを特徴とする請求項１に記載のクラスタリングシステム。
【請求項８】
前記シンボルマッチングコンポーネントは、最もマッチしているクラスタのマッチしているマークの集合に前記マークを追加するように動作することを特徴とする請求項１に記載のクラスタリングシステム。
【請求項９】
前記ライブラリは、前記既存クラスタの出現頻度に従って前記既存クラスタをソートするように動作することを特徴とする請求項７に記載のクラスタリングシステム。
【請求項１０】
請求項１に記載のクラスタリングシステムを採用していることを特徴とするフォトコピア。
【請求項１１】
請求項１に記載のクラスタリングシステムを採用していることを特徴とするファックスマシン。
【請求項１２】
請求項１に記載のクラスタリングシステムを採用していることを特徴とするデジタルカメラ。
【請求項１３】
請求項１に記載のクラスタリングシステムを採用していることを特徴とする画像符号化システム。
【請求項１４】
既存クラスタを格納するライブラリを備えた記憶手段と、該記憶手段に格納されたプログラムを実行する処理ユニットとを含むコンピュータにおけるクラスタリング方法であって、前記ライブラリは、ローカルライブラリとグローバルライブラリとを備え、前記ローカルライブラリは、ドキュメントのカレントページから追加された既存クラスタを備え、前記グローバルライブラリは、前記ドキュメントの先行ページから追加された既存クラスタを備え、前記プログラムは、
前記ドキュメント内のマークを抽出するステップと、
前記ドキュメントから抽出されたマークの第１プロパティを、前記ライブラリに格納された既存クラスタの第１プロパティと比較してマッチする既存クラスタとミスマッチの既存クラスタとを特定するステップと、
前記第１プロパティがマッチするときは、前記ドキュメントから抽出されたマークのビットマップを、前記マッチする既存クラスタのビットマップと比較して、前記マッチする既存クラスタの中からマッチしたクラスタを見つけるステップと、
前記第１プロパティがミスマッチのときと、前記ビットマップがミスマッチのときは、前記マークを新クラスタとして前記ローカルライブラリに追加するステップと
を実行するコンピュータ実行可能命令を備えたことを特徴とする方法。
【請求項１５】
比較される前記第１プロパティは、ｘサイズ、ｙサイズ、インクサイズおよびサイズ変更マーク画像からなるグループの中の少なくとも１つを備えたことを特徴とする請求項１４に記載の方法。
【請求項１６】
前記マークの前記ビットマップからサイズ変更マーク画像を生成することをさらに備えたことを特徴とする請求項１４に記載の方法。
【請求項１７】
前記サイズ変更マーク画像は、前記マークの前記ビットマップを９領域に分割し、３×３の９ピクセルのサイズ変更マーク画像に対応するピクセルに対して９領域の各々のピクセルの大部分を使用することによって生成されることを特徴とする請求項１６に記載の方法。
【請求項１８】
前記マークのホットポイントを計算することをさらに備えたことを特徴とする請求項１４に記載の方法。
【請求項１９】
前記ドキュメントから抽出されたマークの第２プロパティを、前記ライブラリに格納された既存クラスタの第２プロパティと比較して、マッチする既存クラスタとミスマッチの既存クラスタとを特定することを特徴とする請求項１４に記載の方法。
【請求項２０】
前記ドキュメントから抽出されたマークの第３プロパティを、前記ライブラリに格納された既存クラスタの第３プロパティと比較して、マッチする既存クラスタとミスマッチの既存クラスタとを特定することを特徴とする請求項１９に記載の方法。
【請求項２１】
前記マークのビットマップを前記マッチするクラスタのビットマップと比較することは、前記マークの重心と前記クラスタの重心とを計算することと、前記マークと前記マッチするクラスタとの間のｘｏｒ距離を計算することと、前記マークとの最小ｘｏｒ距離を有し、該最小のｘｏｒ距離が許容範囲内にある、最もマッチしたクラスタを選択することとを備えたことを特徴とする請求項１４に記載の方法。
【請求項２２】
既存クラスタを格納するライブラリを備えた記憶手段と、該記憶手段に格納されたプログラムを実行する処理ユニットとを含むコンピュータにおいて、クラスタリング方法を実行するように動作可能であるコンピュータ実行可能命令を格納するコンピュータ読み取り可能な記憶媒体であって、前記ライブラリは、ローカルライブラリとグローバルライブラリとを備え、前記ローカルライブラリは、ドキュメントのカレントページから追加された既存クラスタを備え、前記グローバルライブラリは、前記ドキュメントの先行ページから追加された既存クラスタを備え、前記コンピュータ実行可能命令は、
前記ドキュメント内のマークを抽出するステップと、
前記ドキュメントから抽出されたマスクの第１プロパティを、前記ライブラリに格納された既存クラスタの第１プロパティと比較して、マッチする既存クラスタとミスマッチの既存クラスタとを特定するステップと、
前記第１プロパティがマッチしたときは、前記ドキュメントから抽出されたマークのビットマップを、前記マッチする既存クラスタのビットマップと比較して、前記マッチする既存クラスタの中から最もマッチしたクラスタを見つけるステップと、
前記第１プロパティがミスマッチのときと、前記ビットマップがミスマッチのときは、前記マークを新クラスタとして前記ローカルライブラリに追加するステップと
を備えたことを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項２３】
既存クラスタを格納するライブラリを備えた記憶手段と、該記憶手段に格納されたプログラムを実行する処理ユニットとを含むコンピュータにおいて、クラスタリング方法を実行するように動作可能であるコンピュータ実行可能命令を格納するコンピュータ読み取り可能な記憶媒体であって、前記ライブラリは、ローカルライブラリとグローバルライブラリとを備え、前記ローカルライブラリは、ドキュメントのカレントページから追加された既存クラスタを備え、前記グローバルライブラリは、前記ドキュメントの先行ページから追加された既存クラスタを備え、前記コンピュータ実行可能命令は、
前記ドキュメントの各ページについて、
少なくとも１つのマークを抽出するステップと、
前記少なくとも１つのマークの第１プロパティを、前記ライブラリに格納された既存クラスタの第１プロパティと比較して、マッチする既存クラスタとミスマッチの既存クラスタとを特定するステップと、
前記第１プロパティがマッチしたときは、前記少なくとも１つのマークのビットマップを、前記マッチする既存クラスタのビットマップと比較して、前記マッチする既存クラスタの中から最もマッチしたクラスタを見つけるステップと、
前記第１プロパティがミスマッチのときと、前記ビットマップがミスマッチのときは、前記少なくとも１つのマスクを新クラスタとして前記ローカルライブラリに追加するステップと、
前記ローカルライブラリ内のクラスタを、前記グローバルライブラリ内のクラスタにマージするステップと
を備えたことを特徴とするコンピュータ読み取り可能な記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般的にはドキュメント画像処理に関し、さらに具体的には、クラスタリングを行うシステムと方法に関する。
【０００２】
【従来の技術】
コンピュータを通して利用できる情報量は、コンピュータネットワーク、インターネット（the Internet）およびデジタルストレージ手段の広範な普及と共に飛躍的に増加している。このような情報量の増加に伴って、情報を高速に伝送し、情報を効率的にストアする必要が起こっている。データ圧縮は、情報を効果的に伝送し、格納することを助長する技術である。
【０００３】
データ圧縮は、情報を表現するために必要なスペース量を低減し、多くの情報種別で使用することができる。画像、テキスト、オーディオおよびビデオを含む、デジタル情報を圧縮する要求は、絶えず増加している。代表例として、データ圧縮は、標準的コンピュータシステムで使用されているが、他の技術でもデータ圧縮が利用されている。例えば、これらに限定されないが、デジタルテレビジョンや衛星テレビジョンだけでなく、セルラ電話やデジタル電話などである。
【０００４】
大量の情報を取り扱い、伝送し、処理する要求が増加するのに伴って、そのようなデータを圧縮する要求も増加している。ストレージデバイスの容量は、大幅に増加しているが、情報の要求量は、容量の進歩よりも早いペースで増加している。例えば、未圧縮画像では、必要なスペースが５メガバイトになるのに対し、同じ画像を圧縮すると、必要スペースはわずか２．５メガバイトで済むことになる。従って、データ圧縮を行うと、大量の情報を伝送することが容易になる。ブロードバンド、ＤＳＬ、ケーブルモデムインターネットなどのように、伝送レートが向上している場合でも、未圧縮情報により、伝送限界に容易に達している。例えば、ＤＳＬ回線を利用して未圧縮画像を伝送するには、約１０分かかっている。しかし、同じ画像を圧縮すると、約１分で伝送できるので、データスループットは１０倍に増加することになる。
【０００５】
一般的に、圧縮には、可逆圧縮（lossless）と不可逆圧縮（lossy）の２種類がある。可逆圧縮によると、圧縮したあと元のデータをそっくり回復できるのに対し、不可逆圧縮によると、圧縮したあとに回復されるデータは、元のデータと異なったものになっている。不可逆圧縮では、ある程度のデータ保全性の犠牲は大目に見られているので、可逆圧縮よりも圧縮比率が向上する点で、これらの２圧縮方式の間にはトレードオフが存在している。可逆圧縮は、データをそっくり再構築することに失敗すると、テキストの品質と読み易さが大幅に影響されるので、例えば、重要なテキストを圧縮するときに使用することができる。不可逆圧縮は、ある程度のひずみやノイズが許容されるか、あるいは人間の知覚に感知されないような、画像や重要でないテキストで使用することができる。データ圧縮は、ドキュメントをデジタルで表現したもの（デジタルドキュメント）に特に適している。デジタルドキュメントの代表例としては、テキスト、画像および／またはテキストと画像とがある。カレントデジタルデータに使用されるストレージスペースが低減されるほかに、品質を大幅に低下しないコンパクト・ストレージにより、ドキュメントのカレントハードコピーのデジタル化が促進されるので、オフィスのペーパレス化が実現しやすくなる。このようにオフィスをペーパレス化することは、情報へのアクセスが容易化される、環境コストが節減される、ストレージコストが低減される、といった利益が得られるので、多くの企業の努力目標となっている。さらに、圧縮を行うと、デジタルドキュメントのファイルサイズが小さくなるので、インターネット帯域幅の利用効率が向上するため、より多くの情報を高速に伝送し、ネットワーク輻輳を低減化することが可能になる。情報用の所要ストレージ量を低減すること、効率のよいペーパレスオフィス化への動き、インタフェース帯域幅効率を向上することは、圧縮を行うと得られる、多くの顕著な利益の一部にすぎない。
【０００６】
デジタルドキュメントを圧縮すると、いくつかの目標が達成されるので、デジタルドキュメントの使用はもっと魅力的になるはずである。第１に、圧縮を行うと、大量の情報を短時間で圧縮し、伸張することが可能になるはずである。第２に、圧縮を行うと、デジタルドキュメントを正確に再現することが可能になるはずである。さらに、デジタルドキュメントをデータ圧縮すると、ドキュメントの意図する目的または最終的用途が生かされるはずである。あるデジタルドキュメントは、ハードコピーをファイルし、そこからハードコピーを得るために使用されている。他のドキュメントを、修正および／または編集することができる。多くの従来データ圧縮方法では、テキストおよび／または画像が表示されたとき、そのリフロー（re-flow）を扱うことができないため、効率的かつ効果的方法で圧縮技術が文字を認識し、その文字をワードプロセッサ、ＰＤＡ（personal digital assistant）、セルラ電話などにリフローすることができない。従って、ハードコピーのオフィスドキュメントがスキャンされてデジタル化されたとき、現行の圧縮技術では、不可能ではないにしても、デジタル化ドキュメントを更新し、修正し、あるいは一般的には変更することが困難になっている。
【０００７】
【発明が解決しようとする課題】
デジタルドキュメントは、一般的には、大量のテキスト情報を含んでいる。圧縮を行わないと、８．５インチ×１１インチで、インチ当たり２００ドット（ｄｐｉ）の単一ドキュメントは、ほぼ２ＭＢのストレージスペースを使用している。しかし、テキスト情報は、圧縮を行えるようにするプロパティをもっている。テキスト情報を圧縮する１つのアプローチでは、テキストについてＯＣＲ（optical character recognition）を行い、ドキュメントを、ＡＳＣＩＩなどの標準アルファベットの文字コードの列として表現している。しかし、ＯＣＲは、特に低品質のドキュメントに対しては、完全には信頼性がないので、ＯＣＲを使用するにはいくつかの欠点がある。ドキュメントにノイズがあったり、タイプフェースが変わったり、異常な文字が現れたりすると、いずれもＯＣＲエラーを引き起こす原因になっている。さらに、特殊なフォント、外国語および数学公式は、特殊な問題を引き起こしている。
【０００８】
デジタルドキュメントを圧縮する別のアプローチでは、クラスタリング（clustering）を使用している。クラスタリングでは、ドキュメントの連結コンポーネント（連結コンポーネントとは、あるカラーのピクセルで、連結されたピクセルの集合である）を見つけることが行われる。連結コンポーネントが見つかると、解析され、クラスタと呼ばれる類似の連結コンポーネントが見つけられる。一般的に、クラスタを使用すると、圧縮が大幅に向上するので、ＯＣＲの信頼性問題のいくつかが回避される。例えば、１ページからなる８．５インチ×１１インチで、インチ当たり２００ｄｐｉのドキュメントは、未圧縮のときはほぼ２ＭＢのストレージスペースを使用するが、クラスタリングを使用すると、約２００Ｋだけで済むことになる。ファイルサイズが大幅に低減するのは、各連結コンポーネントが位置と、形状ディクショナリに属する形状を指すポインタとによって要約できるからである。アルゴリズムのクラスタリング部分では、どの形状がディクショナリに属しているか、どの形状が各連結コンポーネントに最も近接しているかが判断される。代表例として、形状ディクショナリは、元のドキュメント画像のサイズの数分の１であるので、複数のページにまたがって共有することもできる。形状を指すポインタは、ページ内の位置（ＸとＹ）と形状番号によって特徴付けることができる。ＸとＹの位置は、先行の位置を使用して圧縮されるのに対し、形状を指すインデックスは、コンテキストまたは言語モデルを使用して圧縮される。従って、クラスタリングを使用すると、圧縮が大幅に向上するが、類似の連結コンポーネント（クラスタ）を見つけるために、連結コンポーネントを解析することは、計算集中型プロセスであるのが一般である。単一ページまたは複数ページのドキュメントは、類似の連結コンポーネントを見つけるために比較される連結コンポーネントが数１０００以上になることがある。
【０００９】
【課題を解決するための手段】
以下は、本発明のいくつかの側面の基本的理解が得られるようにするために、本発明を要約して説明したものである。なお、この要約説明は、本発明の主要／重要なエレメントを明らかにすることを目的するものでも、本発明の範囲を限定するものでもない。その唯一の目的は、後述される詳細説明の序文として本発明のいくつかの概念を要約して提示することである。
【００１０】
本発明は、ドキュメント画像を符号化し、復号化するシステムと方法に関し、さらに具体的にはクラスタリングに関する。クラスタリングでは、大部分が連結ピクセルである類似マークをクラスタにグループ化して圧縮を向上する。クラスタリングは、各マークを他のマークとビットごとに比較してクラスタを特定する必要があるので、大量のメモリとプロセッサ資源を消費することがある。本発明によれば、ミスマッチしたクラスタを特定すると、そのミスマッチしたクラスタとのビットごとの比較を行わないで済むので、メモリとプロセッサ資源の使用量が低減される。ミスマッチを特定するプロセスは、スクリーニング（screening）と呼ぶことができる。スクリーニングは、一部の従来のクラスタリングアプローチでも利用しているが、本発明によれば、クラスタリングをもっと効率化するスクリーニングテストまたはプロパティが選択されている。本発明では、既存クラスタのプロパティが利用され、ドキュメントからの抽出マークのプロパティがクラスタプロパティと比較される。この比較によれば、適時、高価なビットごとの比較を行わなくても、ミスマッチを特定することができる。マークのプロパティがクラスタプロパティのどれともマッチしないときは（マークが既存クラスタから離れすぎていると判断されたときは）、マークは、新クラスタとして追加されるので、ビットごとの比較を行わないで済むことになる。
【００１１】
本発明は、計算効率のよいスクリーニングによってミスマッチを検出し、計算効率のよいアルゴリズムによってポジティブミスマッチを検出して、クラスタリングを行う。
【００１２】
本発明の一側面によれば、クラスタは、クラスタに最初に挿入されるエレメントまたはマークによって特徴付けられている。第１の利点は、新マークをクラスタに追加するとき、クラスタの特徴を計算し直す必要がないことである。このアプローチの第２の利点は、新マークがクラスタに追加されるたびにクラスタ中心が移動または変更されたときに起こる「クラスタドリフト（cluster drift）」が防止されることである。クラスタドリフトを防止すると、同一クラスタの２エレメント間の最大距離の保証が得られることになる。この保証があると、スクリーニングが効率化し、強力化されることになる。このアプローチの主な欠点は、クラスタからマークまでの平均距離が同じであるとき、他のクラスタリングアルゴリズムよりも、得られるクラスタが多くなるという意味で、このクラスタリングが最適でないことである。主な利点は、速度が大幅に向上することである。テキストの圧縮の場合、クラスタの数が１０％増加することは、各クラスタの情報を伝達するディクショナリのサイズは、圧縮ドキュメントのサイズの数分の１であるので、必ずしも重要なことではない。
【００１３】
本発明の一側面によれば、クラスタプロパティは、例えば、テーブルに格納しておくことができる。採用できるクラスタのプロパティの１つとして、ｘサイズとｙサイズがある。ｘサイズとｙサイズは、既存クラスタのサイズ情報を収めている。マークのｘサイズとｙサイズを、既存クラスタのｘサイズとｙサイズと比較すると、ミスマッチを特定することができる。さらに、本発明の別の側面によれば、クラスタは、ｘサイズとｙサイズをインデックスとする、２Ｄバケットテーブル（2D table of buckets）に編成されている。新マークが見つかると、同一のｘサイズとｙサイズのバケットが、２Ｄバケットテーブルから抽出され、そのマークは、バケット内のクラスタと比較される。隣接バケットもサーチすると、もっと正確にマッチしたものを見つけることができる（他のバケットは、すべて無視されるかスクリーニングされる）。ここで、クラスタ中心が「ドリフトしない（no drift）」ものと想定すると、クラスタは、そのバケット内に留まることが保証されるので、好都合である。
【００１４】
利用できるクラスタのもう１つのプロパティは、インクサイズ（ink size）である。一般的に、インクサイズとは、マークまたはクラスタ内のブラックピクセルと総ピクセルとの比率のことである。同様に、マークのインクサイズを既存クラスタのインクサイズと比較すると、ミスマッチを特定することができる。
【００１５】
マークのもう１つのプロパティは、マークの「ホットポイント（hot point）」である。ホットポイントは、マーク上のロケーションであり、これは、重心にすることも、他の手段（例えば、周囲文字のライン方程式）によって計算することもできる。比較が行われるとき、マークのホットポイントとクラスタは、比較が始まる前に位置合わせされ、その結果、多くの場合、平行移動される。もう１つのクラスタプロパティは、縮小マークまたは画像であり、これは、マークおよび／またはクラスタのピクセルサイズの縮小バージョンである。本発明の一側面では、縮小マークはホットポイントの中心に位置し、マークは、縮小マークが固定サイズをもつように再スケーリングされる。この場合も、クラスタがドリフトしないものと想定すると、クラスタの縮小バージョンがクラスタ内のすべてのマークを良好に表現することが保証されるので好都合である。縮小マークを既存クラスタの縮小マークまたは縮小画像と比較すると、ミスマッチを特定することができる。
【００１６】
本発明の別の側面によれば、マークがすべての特徴テスト（feature test）に成功すると、そのマークはもっと直接的な方法でクラスタと比較される。マークからクラスタまでの距離が計算され、第１しきい値と比較される。この距離はＸＯＲ距離にすることも、もっと複雑な距離にすることも、あるいは距離を組み合わせたものにすることも可能であり、各距離は、もっと複雑で、意味のある距離をスクリーニングするときに使用される。距離がそれぞれに対応するしきい値より小であれば（これは実験的に判断することができる）、マークはカレントクラスタに追加される。
【００１７】
本発明の一側面では、クラスタは、最もマッチする可能性のあるクラスタが最初にマークと比較されるようにサイズ順に保存されるので、マッチしたものが早く見つかったときは、比較の回数が低減されることになる。
【００１８】
本発明の別の側面は、クラスタリングシステムである。クラスタリングシステムは、マークエクストラクタ（mark extractor）、ライブラリ、テーブル、マッチングコンポーネント（match component）、およびシンボルマッチングコンポーネント（match symbol component）を含んでいる。マークエクストラクタは、ドキュメントからマークを抽出する。ライブラリは、既存クラスタとその既存クラスタに関する情報をストアするように動作する。テーブルは、既存クラスタのマッチングプロパティ（matching properties）をストアしている。マッチングコンポーネントは、マークの少なくとも１つのプロパティを、マッチングプロパティテーブルに入っているマッチングプロパティと比較して、マッチング既存クラスタを特定するように動作する。シンボルマッチングコンポーネントは、マークをマッチング既存クラスタと比較し、最もマッチするクラスタを特定するように動作し、速度が重要であるときは、マークからクラスタまでの距離が第１しきい値以下になるような、最初のクラスタを特定するように動作する。
【００１９】
本発明の別の側面は、各クラスタの最終的ビットマップがどのように計算されるかに関係している。クラスタリングが終了すると、各クラスタのビットマップは、クラスタ内のすべてのマークをホットポイントに従って位置合せし、クラスタ内のすべてのマークのピクセルの平均値を、ロケーションごとにとることによって評価される。各ロケーションについて、平均値が０．５より大であれば、そのロケーションにあるクラスタのビットマップピクセルは１にセットされ、平均値が０．５より小であれば、そのロケーションにあるクラスタのビットマップピクセルは０にセットされる。平均値が正確に０．５であるときは、８個の隣接マークも平均値がとられ、ピクセル値は、その新平均値が０．５より大であれば１に、そうでなければ０にセットされる。その結果得られたビットマップは、形状ディクショナリに入力され、そのクラスタ内のすべてのマークは、画像が符号化されるときそのビットマップを指している。
【００２０】
本発明の別の側面によれば、クラスタリングの方法が提供されている。ドキュメントが用意される。このドキュメントはバイナリであり、テキスト情報を含んでいるのが代表的である。マークがドキュメントの中で見つけられる。マークの第１プロパティは、既存クラスタの第１プロパティと比較され、マッチするクラスタとミスマッチのクラスタが特定される。マークのビットマップは、マッチするクラスタのビットマップと比較され、マッチするクラスタのうち最もマッチしたクラスタが特定されるか、あるいはクラスタリングの速度を向上するために、マークからクラスタまでの距離が第１しきい値より小であるような最初のクラスタが見つけられる。マークは、マッチしたクラスタがないときは、新クラスタとして追加される。
【００２１】
上述した目的および関連目的を達成するために、以下では、本発明のいくつかの側面が例示されて、以下の説明および添付図面と関連付けて説明されている。これらの側面は、本発明を実施することができる、さまざまな方法を示しており、その方法のすべては、本発明の範囲に含まれるものである。本発明の他の利点と新規特徴は、図面と関連付けて検討するときに、本発明の以下の詳細説明の中で明らかにする。
【００２２】
【発明の実施の形態】
以下、図面を参照して本発明について説明する。なお、図面全体において、類似のエレメントは類似の参照符号を付けて示されている。以下の説明では、説明の便宜上、本発明の理解を完璧なものにするために多数の具体例が詳述されている。なお、説明するまでもなく、本発明はそのような具体例がなくても実施可能である。他の例では、本発明の説明を容易にするために、周知の構造とデバイスはブロック図の形で示されている。
【００２３】
本明細書で使用されている「コンポーネント」という用語は、コンピュータ関連のエンティティのことを意味し、これは、ハードウェアであっても、ハードウェアとソフトウェアを組み合わせたものであっても、ソフトウェアであっても、実行中のソフトウェアであっても構わない。例えば、コンポーネントは、これらに限定されないが、プロセッサ上で実行されるプロセス、プロセッサ、オブジェクト、実行可能命令（executable）、実行スレッド、プログラム、およびコンピュータにすることができる。具体例を挙げると、サーバ上で実行されるアプリケーションとそのサーバは、共にコンポーネントとなることができる。１または複数のコンポーネントは、プロセスおよび／または実行スレッドの中に置いておくことができ、コンポーネントは、１つのコンピュータに置いておくことも、および／または２またはそれ以上のコンピュータ間で分散させることも可能である。
【００２４】
さらに、「ドキュメント画像（document image）」とは、１または複数のカラーを含むドキュメント（例えば、バイナリ（黒／白）、グレースケールおよび／またはカラードキュメント）をデジタルで表現したものを意味している。さらに、ドキュメント画像は、画像、テキストおよび／または画像付きテキストを含むことが可能であり、テキストと画像は重なり合っていることも有り得る。ドキュメント画像は、ドキュメントをバイナリ、ＲＧＢ、ＹＵＶおよび／またはその他の表現を含むことができる。ＲＧＢドキュメント画像は、赤、緑および青コンポーネントを使用して表現される。ＹＵＶドキュメントは、Ｙで示すルミネセンスコンポーネントおよびＵとＶで示すクロミナンスコンポーネントを使用して表現される。ＹＵＶで表現したものが、一般的に圧縮するのに適しているのは、人間の目がＵとＶのひずみを感知しないため、ＵとＶが係数２でサブサンプリングできるからであり、さらに、Ｙは、Ｒ、Ｇ、Ｂ間の相関関係をキャプチャするからである。テキストクラスタリングの目的上、Ｙで表現したものが特に関心のあるのは、ルミナンスが変化した結果のテキストは、一般に読みやすくなっているからである。クロミナンスが変化した結果のテキスト、例えば、ルミナンスが一定であるとき、赤から緑に変化した結果のテキストは、典型的には判読しにくい。従って、カラードキュメントをＹＵＶドキュメントに変換すると、テキスト情報をほぼ残したまま圧縮またはバイナリ化することができる。ドキュメント画像は、一般に「ピクセル」と呼ばれる画素を含んでいる。ドキュメント画像は、任意の形状またはサイズの単一ページまたは複数ページのドキュメントを基礎にすることができる。
【００２５】
図１は、本発明の一側面にかかるクラスタリングシステム１００を示す図である。クラスタリングシステム１００は、ドキュメントからマークを抽出し、見つかったマークと既存クラスタとのビットごとの多数の比較を回避することによって、計算効率のよい方法でマークからクラスタを作成する。クラスタリングシステム１００は、若干の比較を行ってマークとクラスタの間でマッチしたものとミスマッチしたものを特定するので、計算コストのかかる、多数のビットごとの比較を行わないで済むようにする。
【００２６】
マークエクストラクタ１０４は、ドキュメント１０２（例えば、典型的にはテキスト情報を含む）からマークを抽出する。一般的に、ドキュメント１０２は、バイナリドキュメント画像であるが、当然に理解されるように、本発明の別側面では、適当な数のレベルまたはカラーを有するドキュメントにすることも可能である。ドキュメント１０２は、１または複数ページからなり、別のドキュメント画像からレイヤまたはマークを抽出されることができる。マークは、一般的に、所与のカラーの複数の連結ピクセル（connected pixel）であり、これは連結コンポーネントと呼ぶこともできる。多くの場合、マークは、「ｅ」のような、英数文字になっている。しかし、ＯＣＲとは異なり、マークは特殊文字として認識されない。
【００２７】
ドキュメントの中でテキストを普通に表現したものは、白の上の黒いテキストとして表現されたテキストである。このシステム１００は、説明を簡単にするために、ドキュメント１０２のテキストが黒で表現されているものして説明されている。なお、当然に理解されるように、テキストは、他の任意のカラーまたはシェード（shade）上の任意の適当なカラーまたはシェードで表すことも可能である。
【００２８】
マークエクストラクタ１０４は、ドキュメント１０２をスキャンして（例えば、左から右へ、上から下へ）、マークの「シード（seed）」を特定しまたは探し出す。シードは、マークエクストラクタ１０４が最初に特定しまたは探し出した、白以外のピクセルである。マークエクストラクタ１０４は、開始位置またはピクセルからスキャンを開始する。開始位置は、典型的には、ドキュメントの左上隅にあり、各マークが抽出されるたびに更新される。従って、例えば、左端にある最も高いマークが最初に見つけられる。シードが見つかると、連結ピクセルを探し出すアルゴリズムが適用される。そのあと、マークエクストラクタ１０４は、その連結ピクセルを含んでいるマークを抽出し、それをドキュメントから除去する。
【００２９】
プロパティマッチングコンポーネント（match properties component）１０６は、マークエクストラクタからマークを受け取る。プロパティマッチングコンポーネント１０６は、マークの１または複数のプロパティを既存クラスタ１１４の１または複数のプロパティと比較し、ミスマッチを特定する。この比較は、スクリーニングと呼ぶこともできる。１または複数のプロパティの例としては、マークのビットマップ画像、マークの重心、ｘサイズ、ｙサイズ、インクサイズ、位置情報およびサイズ変更マーク画像がある。ストレージコンポーネント１１２は、既存クラスタ１１４の１または複数のプロパティを格納しており、プロパティをプロパティマッチングコンポーネント１０６に提供する。ストレージコンポーネント１１２は、メモリ、ハードドライブ、フラッシュメモリなどの、ストレージデバイスにすることができる。マークの１または複数のプロパティは、必要ならば、プロパティマッチングコンポーネント１０６によって計算することができる。同様に、既存クラスタ１１４の１または複数のプロパティも、必要ならば、プロパティマッチングコンポーネント１０６によって計算することができる。
【００３０】
プロパティマッチングコンポーネント１０６は、１または複数のプロパティの許容値範囲を、しきい値を使用して計算する。しきい値は、例えば、８０％にすることができる。このことは、既存クラスタのプロパティが、マークの対応するプロパティの８０％の範囲内に許容されることを意味している。しきい値は、システムのパフォーマンスを向上するように調整することができる。しかし、しきい値を大きくすると、マークが既存クラスタに追加される可能性が低くなり、得られる圧縮が少なくなる。プロパティの各々について、複数のしきい値を使用することができる。
【００３１】
１または複数のプロパティは、順次に比較することも、並列に比較することもできる。例えば、順次に比較する場合は、マークのｘサイズプロパティを既存クラスタのｘサイズプロパティと比較し、そのあとで、マークのインクサイズを既存クラスタのインクサイズと比較することができる。順次比較を行うと利点があるのは、多数の中から１つの該当クラスタを見つけることが問題である以上、大部分の比較が失敗することが予想されるからである。従って、計算コストが最も安い特徴比較（feature comparison）が最初に行われ、ある比較が失敗したあとは、そのクラスタの残りの比較は行わないで済むことになる。クラスタがミスマッチであると、次のクラスタが考慮される。別の例として、並列に比較を行う場合、マークのｘサイズとインクサイズを、既存クラスタのｘサイズとインクサイズとに比較することができる。並列比較を行うと利点があるのは、複数の比較を同時に行えるからである。並列比較では、利用する比較の数が多くなるが、計算を並列に行うので速度が向上することになる。
【００３２】
ミスマッチであると特定されると、つまり、既存クラスタの１または複数のプロパティの１つが、許容範囲内にないか、あるいはマークからクラスタまでの距離も、許容範囲内にないことが分かると、マークは新クラスタとして既存クラスタに追加される。さらに、システムによるマークの処理は完了する。ドキュメントの別のマークは、システム１００によって処理することができる。
【００３３】
マッチしていると特定されると、つまり、マッチしている既存クラスタが少なくとも１つあることが分かると、シンボルマッチングコンポーネント１１０は、マークのビットマップを、少なくとも１つのマッチしているクラスタのビットマップと比較する。これらのビットマップはビットごとに比較されて、少なくとも１つのマッチしている既存クラスタのうちで、類似のビットマップをもつクラスタが特定される。この比較は、マッチングと呼ぶこともできる。距離マッチングは、２つ以上計算することができる。例えば、ＸＯＲ距離を最初に計算し、つまり、ミスマッチしたビットごとに距離に１が加えられた後で、最初の距離が一定の範囲内にあれば、もっと複雑で、計算コストの高い距離をそのあとに続けることができる。本発明によれば、他の適当なマッチングプロシージャを使用することも可能である。例えば、セットされた隣接ピクセルの数に応じてピクセルに重みを付ける加重排他的ＯＲ（ＷＸＯＲ）、ＷＸＯＲと類似しているが、重みを計算するとき黒から白へのエラーを、白から黒へのエラーと切り離して取り扱う加重ＡＮＤ−ＮＯＴ（ＷＡＮ）、セットされた４またはそれ以上の隣接ピクセルのある位置が、エラーマップの中で見つかったときマッチを拒絶するパターンマッチングと置換（ＰＭＳ：pattern matching and substitution）、ヒューリスティックスを利用して薄いストロークまたはギャップを検出することによってＰＭＳを補強する結合されたサイズ独立ストラテジ（ＣＳＩＳ：combined size-independent strategy）、圧縮ベースのテンプレートマッチング（ＣＴＭ：compression-based template matching）などがある。マッチングプロシージャまたは比較は、最初に許容されるマッチング既存クラスタの個所で終了させ、それをマッチしたクラスタとすることができる。マークのビットマップと少なくとも１つのマッチング既存クラスタのビットマップの偏差を小さくするようなしきい値が選択されている。ビットマップを比較するプロシージャは、以下に、図６を参照して詳しく説明されている。別の方法として、マッチングプロシージャは、少なくとも１つのマッチング既存クラスタのすべてが終わるまで続けていき、最良にマッチしたクラスタまたは最もマッチしたクラスタを、マッチしたクラスタとして特定することもできる。マッチしたクラスタが見つかるか、特定されると、マークはマッチしたクラスタの類似マーク集合に追加される。マッチしたクラスタのビットマップは、マークのビットマップを利用して平均値で更新することができる。
【００３４】
ビットマップに対してミスマッチであると特定されると、つまり、少なくとも１つのマッチングクラスタのどのビットマップも許容されないことが分かると、マークは、新クラスタとして既存クラスタに追加される。さらに、システム１００によるマークの処理は完了する。システム１００は、ドキュメント内に残っているすべてのマークについて続けることができる。
【００３５】
図２は、本発明の一側面にかかる例示マーク２０１を示す図である。連結ピクセルは、連結性プロパティを利用して見つけられる。例示マーク２０１は、テキスト文字（例えば、英字「ｚ」）を表している。典型的には、連結ピクセルを見つけるために８連結性プロパティが使用されているが、４連結性プロパティを使用することもできる。４連結性プロパティは、４つの基本コンパス方向の連結ピクセルだけを特定する。図３は、４連結性プロパティを示し、あるピクセルが、４つの基本コンパス方向の４ピクセルによって囲まれている。８連結性プロパティは、すべてのサーチ可能な隣接方向の連結ピクセルを特定し、直接に隣接する８ピクセルは、８つの主要方向の各々に１つ存在している。図４は、８連結性プロパティを示し、あるピクセルが８つの主要方向４１１の８ピクセルによって囲まれている。例えば、図２のピクセル２０３は、４連結性プロパティと８連結性プロパティに従って特定されている。しかし、４連結性プロパティは、ピクセル２０４を連結ピクセルと特定することはない。
【００３６】
再び図１を参照して説明すると、マークエクストラクタ１０４は、次のアルゴリズムを使用してマークを見つけることができる。最初に、バイナリ画像をランレングス符号化（ＲＬＥ：run length encoding）表現に変換する。ランがｎ個であるとすると、ｎ個の集合を作成し、各集合にランを入れる。次に、ラインごとに、およびランごとに、先行ラインにあって、カレントランに接触しているすべてのランを４連結性または８連結性を使用して見つける。接触するランを収めているすべての集合の結合を実行する。ページの終わりで、残っている集合はマークである。このアルゴリズムは、「UNION-FIND」アルゴリズムと呼ぶことができる。計算量は、O(n log*(n))である。そこでは、ｎはランの数、log*は、Ackerman関数の逆関数である。従って、計算量は、ほぼO(n)であり、ｎはランの数である。さらに、マークは、画像とそのネガティブの両方について計算すると、反転ビデオテキストをクラスタリングすることもできる。
【００３７】
上述したように、マークは、連結ピクセルから構成されているのが一般である。しかし、マークエクストラクタ１０４は、厳密には連結ピクセルでないマークを計算するように適応させることができる。例えば、図５は、英字「ｉ」の下部分５０１を上部ドット５０２と一緒に示している。下部分５０１とドット５０２は、別個の連結ピクセルである。しかし、マークエクストラクタ１０４は、元のマークから別の領域をスキャンすることによって、下部分５０１とドット５０２を単一または結合マークとして特定することができる。
【００３８】
連結コンポーネントまたはマークを結合するには、ライン解析を行うことができる。例えば、連結コンポーネントは、ページ内のその位置に基づいて、ワードに結合することができ、ワードも、ページ内のその位置と角度に基づいてラインに結合することができる。ラインが特定されると、ライン方程式に対して垂直に互いの上に位置している、すべてのマークをマージすると、アクセントとドットマークが、それが属していた文字のマークに付けられることになる。その結果のマークは、当然に結合されていないが、前述したようにクラスタリングアルゴリズムで使用することができる。
【００３９】
マークが特定されると、マークエクストラクタ１０４は、そのマークに対して追加の計算を行うことができる。マークエクストラクタ１０４は、マークの重心、ｘサイズ、ｙサイズ、インクサイズ、エリア、位置情報、ホットポイント、およびサイズ変更画像などの、マークのプロパティを計算することができる。ｘサイズは、マークの最大幅として計算される。ｙサイズは、マークの最大高さとして計算される。マークが２マークの結合（つまり、「ｉ」とそのドット）であれば、ｙサイズは、結合された結果の高さである。インクサイズは、マーク内の黒ピクセルの数であるのに対し、エリアは、マークの境界ボックス内のピクセルの総数（ｘサイズにｙサイズを掛けたもの）である。ミスマッチを検出するために使用すると有用な特徴は、インクパーセンテージである。次の式を使用すると、マークまたはクラスタのインクパーセンテージを計算することができる。
【００４０】
【数１】
0004152789.tif 000002
【００４１】
ホットポイントは、マーク上のロケーションであり、これは重心にすることも、他の手段で計算することもできる。例として、テキストの場合、ライン解析を行い、マークが位置しているラインの方程式を見つけることができる（これは、「ｉ」のドットなどの、マークを結合するラインを見つけるために使用される同じアルゴリズムである）。マークのホットポイントは、ｘ座標では水平方向の重心をもち、ｙ座標では、同じｘ座標を通る垂直方向のラインとライン方程式との交点をもっている。比較を行うとき、マークのホットポイントとクラスタは、比較が始まる前に位置合わせされ、その結果、多くの場合、比較の前にマークが平行移動される。
【００４２】
位置情報としては、マークの座標とオフセットといった情報、参照点および／またはスペース情報がある。
【００４３】
サイズ変更マーク画像は、マークのサイズ変更バージョンである。サイズ変更マーク画像は、マークの縮小バージョン、例えば、３×３ピクセル画像として計算される。サイズ変更マーク画像は、シンボル比較を容易にするために計算される。サイズ変更シンボルは、典型的には、マークよりもピクセルサイズが大幅に小さくなっている。マークをサイズ変更マーク画像にダウンサイズするためにいくつかのアルゴリズムが使用できる。１つのアルゴリズムは、マークをホットポイントの中心に置かれ、マークのエリアをカバーするようにスケーリングされた９領域（３×３）に分割し、これらの領域の各々に交差するときマークの平均値を計算するものである。
【００４４】
別のアルゴリズムでは、いくつかのピクセルをビットマップから除去または破棄するものである。なお、サイズ変更画像を生成するために他のアルゴリズムを使用することも可能であり、これらは、本発明の範囲に属するものである。以上から理解されるように、上記計算は、必要ならば、計算効率を向上するためにシステムが要求するまで先に延ばすことが可能である。
【００４５】
さらに、以上から理解されるように、本発明によれば、既存クラスタとそのプロパティは、ローカルライブラリとグローバルライブラリに保存しておくことができる。ローカルライブラリは、カレントページの既存クラスタを格納しておくために使用でき、グローバルライブラリは、ドキュメント１０２の既存クラスタをグローバルに格納しておくために使用できる。別の側面では、出現頻度の高い既存クラスタ（例えば、関連マークの数が相対的に多いクラスタ）は、グローバルライブラリに保存されるのに対し、出現頻度の低い既存クラスタは、ローカルライブラリに保存される。
【００４６】
図６は、本発明の一側面によるクラスタリングシステム６００を示す図である。クラスタリングシステム６００は、ドキュメントからマークを抽出し、見つかったマークと既存クラスタとの、非常に多数のビットごとの比較を回避することによって計算効率のよい方法でクラスタを作成する。クラスタリングシステム６００は、ミスマッチを特定する比較またはスクリーニング操作をいくつか行うことにより、多数の計算コストの高い、ビットごとの比較を回避する。
【００４７】
一般的に、クラスタは、クラスタに最初に挿入されたエレメントまたはマークによって特徴付けられている。これには、新マークをクラスタに追加するとき、クラスタの特徴を再計算しないで済むという利点がある。このアプローチのもう１つの利点は、新マークがクラスタに追加されるたびにクラスタ中心が移動または変更されたときに起こる「クラスタドリフト」が回避されることである。クラスタドリフトを回避すると、同一クラスタの２エレメント間の最大距離の保証が得られる。この保証により、スクリーニングが効率化し、強力化される。このアプローチの欠点は、クラスタからマークまでの平均距離が同じであるとき、得られるクラスタが他のクラスタリングアルゴリズムより多くなるという意味で、クラスタリングが最適でないことである。しかし、処理速度の向上は、上記欠点を上回っているのが一般である。例として、テキスト比較の場合、各クラスタの情報を伝達するディクショナリのサイズは、典型的には、圧縮ドキュメントのサイズの数分の１であるので、クラスタの数が１０％増加することは、必ずしも重要なことではない。
【００４８】
２次元テーブル６１２は、既存クラスタを格納し、維持している。既存クラスタは以前に見つかった、または特定されたクラスタである。上述したように、クラスタは、少なくとも１つの類似マークの集まりである。２次元テーブル６１２は、既存クラスタのボックスサイズまたは境界ボックスに応じたエントリを収容している。テーブル６１２のそれぞれのエントリは、バケットと呼ばれ、特定のボックスサイズに対応するクラスタのリストを収めている。ボックスサイズとは、マークまたはクラスタのｘサイズとｙサイズのことである。当然に理解されるように、エントリまたはバケットは空であることもある。さらに、典型的には、クラスタは、一定のボックスサイズ以下に収まるので、テーブルには最大ボックスサイズを設定することができる。最大ボックスサイズを超えるクラスタは、別のテーブルに格納しておくことができる（例えば、企業のロゴやシール）。典型的には、相対的に大きいボックスサイズを有するマークは、他のクラスタまたはマークに類似する可能性がない。
【００４９】
図７は、図６のシステム６００で利用できる、可能な２次元テーブルを示すブロック図である。図示のように、エントリまたはバケットは、ｘサイズとｙサイド別に配列されている。１つのバケット７１０は、ｘサイズが１に、ｙサイズがＮになっている。バケット７１０内のクラスタは、図８に示されている。
【００５０】
マークエクストラクタ６０４は、ドキュメント６０２からマークを得るように動作する。ドキュメント６０２は、デジタルドキュメントであり、典型的にはテキスト情報を含んでいる。マークエクストラクタ６０４は、マークを１つずつ除去し、処理する。マークエクストラクタ６０４は、適当なアルゴリズムを使用してマークをドキュメント６０２から抽出し、除去する。それぞれのマークについて、マークエクストラクタ６０４は、マークの特徴またはプロパティを計算および／または取得する。特徴またはプロパティとしては、これらに限定されないが、マークのビットマップ画像、マークの重心、ｘサイズ、ｙサイズ、インクサイズ、位置情報およびサイズ変更マーク画像がある。
【００５１】
サイズマッチングコンポーネント（match size component）６０６は、マークエクストラクタからマークを受け取る。マークは、マークのビットマップ画像、マークの重心、ｘサイズ、ｙサイズ、インクサイズ、位置情報およびサイズ変更マーク画像を含んでいる。サイズマッチングコンポーネント６０６は、許容ｘサイズとｙサイズの範囲を、しきい値を使用して計算する。しきい値は、例えば、１０％にすることができる。すなわち、許容ｘサイズとｙサイズ値が、マークのｘサイズとｙサイズの１０％以内にあるはずであることを意味する。しきい値は、システム６００のパフォーマンスを向上するように調整することができる。しかし、しきい値を大きくすると、典型的には、マッチする既存クラスタが見つかる確率が低くなり、得られる圧縮が低下する。
【００５２】
サイズマッチングコンポーネント６０６は、上記許容範囲内にある１または複数のバケットを得るためにサイズテーブル６１２を参照する。１または複数のバケットは、既存クラスタの一部を収めており、これはサイズマッチングクラスタと呼ぶことができる。サイズマッチングクラスタがないと、マークは、新クラスタとして２次元テーブル６１２に追加される。さらに、サイズマッチングコンポーネント６０６は、初期に特定されたものが１つもないとき、もっと多くのサイズマッチングクラスタを取得するために、サイズ値の範囲を拡大し、あるいは隣接バケットを組み入れることができる。上述したようにクラスタ中心が「ドリフトしない」と想定すると、既存クラスタをそのバケットに残しておくことができるので好都合である。
【００５３】
マークが新クラスタとして追加される場合、マークの情報が２次元テーブル６１２のバケットに追加される。マークの情報としては、これらに限定されないが、ユニークＩＤ、マークのビットマップ画像、マークの重心、ｘサイズ、ｙサイズ、インクサイズ、位置情報およびサイズ変更マーク画像である。マークの画像（今は新クラスタの画像）は、形状ディクショナリに別に格納しておくことができ、そこでは、ライブラリエントリは、形状ディクショナリを指すポインタまたは形状番号だけを収めている。形状ディクショナリは、ローカルおよび／またはグローバルにすることができる。図９は、個別クラスタの例示エントリ９０１を示す図である。当然に理解されるように、エントリ９０１は包括的なものではなく、既存クラスタのエントリに追加情報を入れることもできる。
【００５４】
再び図６を参照して説明すると、サイズマッチングクラスタが少なくとも１つあるときは、マークの処理は、インクマッチングコンポーネント６０８に進む。マークのインクサイズは、それぞれがサイズマッチングクラスタの次のクラスタのインクサイズと比較される。サイズマッチングクラスタの次のクラスタがないときは、マークは、上述したように新クラスタとして既存クラスタに追加される。インクサイズ情報は、マーク内に黒ピクセルの数が占めるパーセンテージ、つまり、黒ピクセルの数とピクセルの総数との比率である。マークのインクサイズが次のクラスタのインクサイズとマッチすると、マークの処理は、シンボルマッチングコンポーネントに進む。マークのインクサイズが次のクラスタのインクサイズとマッチしないときは、インクマッチングコンポーネントは、サイズマッチングクラスタの後に続く次のクラスタについてマークの処理を続ける。
【００５５】
シンボルマッチングコンポーネント６１０はマークの処理を続ける。最初に、シンボルマッチングコンポーネント６１０は、マークのサイズ変更画像を次のクラスタのサイズ変更画像と比較する。サイズ変更画像は、マークまたはクラスタのダウンサイズしたバージョン（例えば、３×３ピクセル表現）である。ダウンサイズしたバージョンは、バイナリではなく、グレースケールピクセルで表現することができる。この比較は、９ピクセルだけが比較されるので、比較的高速に行うことができる。しきい値は、ダウンサイズした表現の変化が制限されるように設定することができる。サイズ変更画像がマッチしないときは（例えば、ミスマッチしている）、マークの処理は、インクマッチングコンポーネント６０８に戻り、そこで、あとに続く次のクラスタが処理される。
【００５６】
ダウンサイズする前に、「参照点」を使用して画像を位置合せしておくと好都合である。参照されるクラスタとマークの参照点は、ダウンサンプリングされる画像を計算するために計算される。ホットポイントとも呼ばれる参照点は、重心として計算することも、他の手段（例えば、周囲マークのライン方程式）で計算することもできる。マークまたはクラスタの重心は、黒ピクセルが各ビットマップに置かれている平均位置として計算される。画像を位置合せするために、他の参照点および複数の参照点を使用することができる。画像がダウンサンプリングされる前に、画像は、ホットポイントがダウンサンプリングされる画像の中心に一致するように位置合せされる。
【００５７】
サイズ変更画像がマッチしたときは、マークのビットマップと次のクラスタのビットマップとのビットごとの比較が行われる。シンボルマッチングコンポーネント６１０は、マークと参照されたクラスタを比較するために、マークから次のクラスタまでの距離を計算する。距離がしきい値内にあるか、しきい値以下であれば、参照されるクラスタがマッチしたものである。そうでなければ、マークの処理は、インクマッチングコンポーネント６０８に戻り、あとに続く次のクラスタから続けられる。
【００５８】
シンボルマッチングコンポーネントによって利用できる、１つの適当な距離は「ｘｏｒ」距離である。「ｘｏｒ」距離は、エラーマップを生成することによって計算される。エラーマップは、マークと参照されるクラスタとをビットごとに排他的ＯＲをとったものである。「ｘｏｒ」距離は、エラーマップ内のピクセルの数である。「ｘｏｒ」距離が計算される前に、画像は、それぞれのホットポイントを重ね合わせることによって位置合せされる。
【００５９】
図１０は、例示エラーマップを示す図である。マークのビットマップは１００１に示されている。既存クラスタのビットマップは、１００２に示されている。マーク１００１と既存クラスタ１００２とのビットごとの排他的OR演算は、エラーマップ１００３に示されている。
【００６０】
本発明によれば、他の距離計算を採用することも可能である。例えば、セットされた隣接ピクセルの数に応じてピクセルに重みを付ける加重排他的ＯＲ（ＷＸＯＲ）、ＷＸＯＲと類似しているが、重みを計算するとき黒から白へのエラーを、白から黒へのエラーと切り離して取り扱う加重ＡＮＤ−ＮＯＴ（ＷＡＮ）、セットされた４つまたはそれ以上の隣接ピクセルのある位置が、エラーマップの中で見つかったときマッチを拒絶するパターンマッチングと置換（ＰＭＳ：pattern matching and substitution）、ヒューリスティックスを利用して薄いストロークまたはギャップを検出することによってＰＭＳを補強する結合されたサイズ独立ストラテジ（ＣＳＩＳ：combined size-independent strategy）、圧縮ベースのテンプレートマッチング（ＣＴＭ：compression-based template matching）などがある。
【００６１】
さらに、それぞれマークとクラスタとを比較するとき、複数の距離を計算し、使用することができる。例えば、上述したＸＯＲ距離を最初に計算したあとで、つまり、ミスマッチしたビットごとに１を距離に加えたあとで、最初の距離が一定の範囲内にあれば、もっと複雑で計算コストの高い距離を計算することができる。
【００６２】
マッチするものが見つかると、マークは、シンボルマッチングコンポーネント６１０によって次のクラスタに追加される。マークには、ユニークなマーク番号が割り当てられており、これは、マッチしたクラスタの集合の中に位置情報と一緒に格納されている。位置情報としては、これらに限定されないが、ｘとｙ位置座標、先行マークからの距離、オフセット情報などがある。既存クラスタには、クラスタに関連するマークの数を示すマークカウントを含めることができる。マッチしたクラスタがローカルライブラリ６１６に置かれていれば、ローカルライブラリ６１６内のクラスタは、各クラスタに属しているマークの数、すなわち、マークカウント別に再ソートすることができる。
【００６３】
サイズマッチングコンポーネント６０６とインクマッチングコンポーネント６０８は、プロパティマッチングコンポーネント６０５と総称されている。プロパティマッチングコンポーネント６０５は、既存クラスタをスクリーニングしてミスマッチを特定する。プロパティマッチングコンポーネント６０５は、本発明の他の側面では、ミスマッチを特定するために比較を行う上で役立つ、マークと既存クラスタの適当なプロパティまたは特徴を含むことができる。さらに、別の側面では、プロパティマッチングコンポーネント６０５は、サイズとインクサイズプロパティのどれも含まないことも、その一方または両方を含むこともできる。
【００６４】
ドキュメント内のマークのすべてまたは大部分が抽出されたあと、２次元テーブルを破棄し、既存クラスタをグローバルライブラリ６１８に転送することができる。さらに、２次元テーブル６１２からのクラスタは、ドキュメント６０２のそれぞれのページの処理を終えたあと、グローバルライブラリ６１８に転送することができる。グローバルライブラリ６１８は、ドキュメントからの既存クラスタを含む。インクサイズのように、既存クラスタと一緒に以前にストアされた情報の一部は、符号化または復号化に不要であるので、破棄することができる。一般的に、クラスタの位置情報とビットマップ画像は、その情報の種類に適している圧縮方式を使用して符号化される。符号化されると、位置情報とビットマップ画像は結合され、ファイルまたはビットストリームに入れられる。さらに、ライブラリ内のクラスタの数を、ファイルまたはビットストリームに入れておくと、ファイルを正しく復号化することができる。従って、ビットストリームは、最終的には、ライブラリ、マークシーケンスおよび位置情報またはオフセットを収めていることになる。当然に理解されるように、ライブラリは、ディクショナリと呼ぶこともでき、クラスタはシンボルと呼ぶこともでき、マークシーケンスはシンボルシーケンスと呼ぶこともできる。
【００６５】
また、すべてのマークが除去されたあとのドキュメントは、残留画像（residual image）と呼ぶことができる。不可逆圧縮では、この残留画像は破棄される場合がある。他方、可逆圧縮と一部の不可逆圧縮では、残留画像は圧縮されているので、ビットストリームに入って転送される。残留画像は、単にノイズとして現れることがあるので、大部分の圧縮方式では、圧縮率が低下するおそれがある。しかし、既存クラスタを利用する圧縮方式は、残留画像の圧縮を大幅に向上する。ドキュメントのレイアウトをさらに分析すると、ドキュメントの圧縮をさらに向上することができる。例えば、クラスタとマークを水平ラインで特定すると、必要とされる位置情報量を低減することができる。さらに、よく出現するクラスタのシーケンスは、マージしたクラスタまたはワード（例えば、「ｔｈｅ」）として１つに結合することができる。
【００６６】
本発明の別の側面によれば、ＯＣＲコンポーネントはライブラリ、マークシーケンスおよび位置情報を受け取り、クラスタから文字を取得して特定する。ＯＣＲコンポーネントは、１または複数のクラスタを結合して、１つの文字にすることができる。これは、複数のクラスタが文字、例えば、「ｅ」を表し、しかも異なるクラスタで表すことができるからである。さらに、ＯＣＲコンポーネントは、受け取った情報を利用して、その情報からワード、センテンスおよびパラグラフを生成する。そのあと、文字および／またはワードは、共通ＡＳＣＩＩライブラリなどのライブラリで表されるので、圧縮がさらに向上する。
【００６７】
復号化側では、ビットストリームが復号化され、再構築ドキュメントが再構築される。圧縮が可逆である場合は、再構築ドキュメントは、元のドキュメントと実質的に同一になっている。圧縮が不可逆の場合でも、典型的には、再構築ドキュメントは、元のドキュメントに実質的に類似している。当然に理解されるように、再構築ドキュメントは、少なくとも１つの他の画像またはレイヤと結合されて、ドキュメント画像を形成するマスクまたはレイヤにすることができる。
【００６８】
以上、白のバックグランドに黒のテキストがあるドキュメントと関連付けて、クラスタリングシステム６００を一般的に説明してきた。しかし、当然に理解されるように、クラスタリングシステム６００は、黒に限定されないが、黒を含む任意のカラーのクラスタを特定するためにドキュメント画像で使用することも可能である。
【００６９】
図示し、上述してきた例示システムに鑑みて、本発明に従って実施できる方法の理解を容易にするために、以下では図１１のフローチャートを参照して説明する。説明を簡単にするために、これらの方法は、一連のブロックとして示され、説明されているが、当然に理解されるように、本発明によれば、一部のブロックは、図示され、以下に説明されている順序とは異なる順序で現れ、および／または他のブロックと同時に現れることがあるので、本発明はブロックの順序に限定されるものではない。さらに、図示のブロックは、本発明に従って方法を実施するためにすべてが必要になるとは限らない。
【００７０】
本発明は、プログラムモジュールのように、１または複数のコンポーネントによって実行されるコンピュータ実行可能命令という広いコンテキストの中で説明することができる。一般的に、プログラムモジュールは、特定のタスクを実行する、あるいは特定の抽象データ型を実装しているルーチン、プログラム、オブジェクト、データ構造などを含む。典型的には、プログラムモジュールの機能は、種々実施形態における要求に応じて、結合されていることもあれば、分散されていることもある。
【００７１】
図１１は、本発明の一側面にかかるクラスタリングの方法を示すフロー図である。ドキュメントは１１０２で用意される。このドキュメントは、バイナリドキュメント画像であり、一定量のテキスト情報を含んでいる。ドキュメントは、任意のサイズの単一ページまたは複数ページのドキュメントにすることができる。さらに、ドキュメントは、別のドキュメント画像からのレイヤまたはコンポーネントにすることもできる。ドキュメント内のテキスト情報は、典型的には、バックグランドが白でテキストが黒であるが、テキスト情報は、バックグラウンドを黒にし、テキストを白にすることもできる（例えば、反転表示）。
【００７２】
次のマークまたはマークは、１１０４でドキュメントから取得される。マークは、図１と図６を参照して説明したような、適当なアプローチまたはアルゴリズムを使用して取得することができる。さらに、ボックスサイズ、インクサイズ、サイズ変更画像および重心がマークに対して計算される。他のプロパティまたは特徴をマークに対して計算することもできる。ボックスサイズは、マークのｘサイズとｙサイズを含んでいる。さらに、処理を容易にするために、ポインタはクラスタテーブル１１１２の先頭にセットされる。マークが１１０６で取得できないときは、つまり、処理すべきマークがドキュメントに残っていないときは、方法は１１０８で完了するか、方法から出ることになる。従って、１１０８では、ドキュメント内のマークはすでに処理され、適当にクラスタリングされている。マークが取得できるときは、既存クラスタの次のクラスタが１１１０で取り出される。次のクラスタは、一般的に、クラスタテーブル１１１２から取り出される。クラスタテーブル１１１２は、既存クラスタを保存している。１１１４で既存クラスタのクラスタが残っていなければ、新クラスタが１１１６で作成される。
【００７３】
この新クラスタの作成は、マークが既存クラスタに正しくマッチしなかったか、マークがドキュメントから抽出された最初のマークであることを示している。上記のように計算されたマークのプロパティまたは特徴は、部分的に新クラスタを構成している。新クラスタは、新しいことにより、他の既存クラスタよりも見つかる可能性が低いのが一般的であるので、新クラスタは、典型的には、クラスタテーブル１１１２の最後に追加される。
【００７４】
その他の場合は、ボックスサイズマッチングまたは比較が１１１８で行われる。ボックスサイズマッチングでは、マークのｘサイズとｙサイズが次のクラスタのそれと比較される。図７を参照して図示し、説明したように、２次元テーブルを使用して、既存クラスタのボックスサイズ情報を保存しておくことができる。典型的には、比較のためのしきい値は、１０パーセントまたは一定のサイズ変化（例えば、１か０）といったように、マークと次のクラスタの寸法変化が微小になるように設定されている。さらに、しきい値は、方法の速度を向上するように、および／または見つかったクラスタの数を減らすように調整すると、圧縮を向上することができる。マークのボックスサイズが次のクラスタのボックスサイズとマッチしないときは（例えば、１０パーセントの範囲内にない）、方法は１１１０から続けられ、そこで次の新クラスタが取得される。
【００７５】
次のクラスタのボックスサイズとマークのボックスサイズがマッチしたときは、インクサイズマッチングが１１２０で行われる。インクサイズマッチングでは、マークのインクサイズが次のクラスタのインクサイズと比較され、これらが同一および／または実質的に類似していれば、マッチしたものとみなされる。インクサイズは、マーク内の黒ピクセルの数とピクセルの総数との比率である。従って、マークのインクサイズと次のクラスタのインクサイズの間に起こり得る偏差は、マークのインクサイズと次のインクサイズが許容しきい値の範囲内にある限り（つまり、実質的に類似している）、マッチしているものとみなすことができる。しきい値は許容値の範囲を決めるので、インクサイズの偏差が大または小になるように調整することができる。さらに、しきい値は、方法の速度を向上するように、および／または見つかったクラスタの数を減らすように調整すると、圧縮を向上することができる。マークのインクサイズが、ミスマッチとも呼ばれるように、次のクラスタのインクサイズとマッチしないときは（例えば、１０パーセントの範囲内にない）、方法は１１１０から続けられ、そこでは、次のクラスタが取得される。
【００７６】
次のクラスタのインクサイズとマークのインクサイズとがマッチしていると、特徴マップマッチングが１１２２で行われる。特徴マップマッチングでは、マークのサイズ変更画像と次のクラスタのサイズ変更画像が比較され、これらが同一および／または実質的に類似していれば、マッチしているものとみなされる。サイズ変更画像は、マークまたはクラスタを３×３ピクセルで表現したものであり、サイズ変更マーク画像と呼ぶこともできる。サイズ変更画像は、マークまたはクラスタの縮小バージョン、例えば、３×３ピクセル画像として計算される。サイズ変更画像は、典型的には、マークの画像よりもピクセルサイズがはるかに小さくなっている。マーク画像をサイズ変更画像にダウンサイズするには、いくつかのアルゴリズムを使用できる。あるアルゴリズムは、マークを９領域（３×３）に分割し、これらはホットポイントの中心に置かれ、マークのエリアをカバーするようにスケーリングされ、これらの領域の各々が交差するとき、マークの平均値を計算する。別のアルゴリズムは、ビットマップからいくつかのピクセルを除去または破棄している。しかし、他のアルゴリズムを使用してサイズ変更画像を生成することも可能であり、これらも本発明の範囲に属するものである。
【００７７】
従って、マークのサイズ変更画像のピクセルと次のクラスタのサイズ変更画像のピクセルとの比較が行われる。９ピクセル全部がマッチしているが、その偏差（しきい値）がマッチしていれば（例えば、７またはそれ以上がマッチしている）、マークのサイズ変更画像と次のクラスタのサイズ変更画像は、マッチしているものとみなされる。ボックスサイズマッチングとインクサイズマッチングの場合と同様に、特徴マップマッチングのしきい値は、方法の速度を向上するように、および／または見つかったクラスタの数を減らすように調整すると、圧縮を向上することができる。ミスマッチとも呼ばれるように、マークのサイズ変更画像と次のクラスタのサイズ変更画像がマッチしないときは、方法は１１１０から続けられ、そこでは、次の新クラスタが取得される。
【００７８】
次のクラスタのサイズ変更画像とマークのサイズ変更画像がマッチしたときは、ＸＯＲインクマッチングが１１２４で行われる。ＸＯＲインクマッチングでは、マークのビットマップから次のクラスタのビットマップまでの、ＸＯＲ距離とも呼ばれる距離が計算される。マークと次のクラスタに対してエラーマップが生成される。エラーマップは、マークのビットマップ画像と次のクラスタのビットマップ画像とをビットごとに排他的ＯＲをとったもので、中心が重心に位置している。そのあと、ミスマッチしたビットごとに１を加えることによって距離が計算される。距離がしきい値より小であれば、マッチしている。距離がしきい値より大であれば、ミスマッチであり、方法は１１１０から続けられ、そこで次の新クラスタが取得される。しきい値は、必要に応じて設定および／または調整することができる。
【００７９】
ｘｏｒインクマッチングでマッチしていると、「ｗａｎ」マッチングが１１２６で行われる。加重ＡＮＤ−ＮＯＴ（ＷＡＮ）と呼ばれるｗａｎマッチングは、１１２４のｘｏｒインクマッチングと同じように行われる。ｗａｎマッチングもエラーマッチを生成するが、重みを計算するとき黒から白へのエラーを、白から黒へのエラーと切り離して扱っている。距離がしきい値より大であれば、ミスマッチであり、方法は１１１０から続けられ、そこで次の新クラスタが取得される。次に、距離がしきい値より小であれば、マッチしており、方法は１１２８から続けられ、そこでマークが次のクラスタに追加される。
【００８０】
マークが次のクラスタに追加されると、クラスタに関連するマークの数が１だけ増えることになる。さらに、位置情報とユニークＩＤを次のクラスタと一緒に格納することができる。クラスタテーブル１１１２は、もっと共通の既存クラスタが最初に方法によって使用されるように再ソートされる。マークが１１２８で次のクラスタに追加されたあと、方法は１１０４から続けられ、そこで別の次のクラスタが取得される。
【００８１】
当然に理解されるように、既存クラスタは、本発明の別の側面によれば、ローカルおよび／またはグローバルライブラリに格納することができる。方法は、カレントページが処理されるまで、ローカルライブラリに格納された既存クラスタに対して実行することができる。次に、ローカルライブラリ内のクラスタは、グローバルライブラリ内のクラスタとマージされてから、方法による次ページの処理を続けることができる。グローバルライブラリとローカルライブラリ内にあって、実質的に類似しているクラスタは、単一のクラスタにマージすることができるが、非類似のクラスタは、グローバルライブラリに追加される。
【００８２】
図１２は、本発明の一側面による計算効率のよいクラスタリングを利用した画像符号化システムを示すブロック図である。システムは、マスクセパレータ１２０２、フォアグラウンドバックグラウンドセグメンタ１２０４、クラスタリングコンポーネント１２０５、マスクエンコーダ１２０６、フォアグラウンドエンコーダ１２０８、バックグラウンドエンコーダ１２１０およびコンバイナコンポーネント１２１２を含んでいる。
【００８３】
マスクセパレータ１２０２は、ドキュメント画像を受け取り、マスクを生成する。ドキュメント画像は、ドキュメントをデジタルで表現したものである。ドキュメント画像は、１または複数ページにすることができる。ドキュメント画像は、典型的には、ドキュメントからスキャンされる。ドキュメント画像は、任意の解像度をもつことができ、これはインチ当りのドット数（ｄｐｉ）で表されるのが一般である。例えば、ファックスドキュメントは、典型的には、約１００〜２００ｄｐｉの解像度を使用している。さらに、ドキュメント画像は、任意のピクセルサイズまたはサイズにすることができる。例えば、ドキュメント画像は、６４０×４８０ピクセルおよび／またはＡ４サイズにすることができる。
【００８４】
マスクセパレータ１２０２によって生成されたマスクは、そのあと、ドキュメント画像をフォアグラウンド画像とバックグラウンド画像にセグメント化または分割するために使用される。マスク画像とも呼ばれるマスクは、バイナリ画像である。ここでは、そのピクセルの値により、各ピクセルがフォアグラウンド画像に属するか、バックグラウンド画像に属するかが決まる。マスクセパレータ１２０２は、マスク、フォアグラウンド画像およびバックグラウンド画像の結合サイズを減少するマスクを生成する。
【００８５】
マスク、フォアグラウンド画像およびバックグラウンド画像の結合サイズを減少するマスクを生成するには、いくつかのアプローチが使用できる。類似の領域、変化が小さいか、または変化の数が減少している領域は、大きな変化をもつ領域よりも圧縮効率がよい傾向がある。例えば、ソリッドカラーをもつ画像は、輝度とカラーが大きく変化する画像よりも圧縮効率がよい。Ｎ個のピクセルをもつドキュメント画像では、取り得るマスクは２Ｎ個である。従って、取り得るすべてのマスクを通して、どのマスクが最小の全結合画像を生成するかを判断することができる。しかし、取り得るすべてのマスクを通すことは、計算コストが高くなる。小さなサブ領域、例えば、２×２ピクセルまたは４×４ピクセルは、偏差を調べるために解析することができる。サブ領域のピクセルは、フォアグラウンドとバックグランド内の偏差を少なくするために、フォアグラウンドとバックグラウンドに分割することができる。そのあと、サブ領域は１つにマージされ、マスク、フォアグラウンド画像およびバックグラウンド画像の結合サイズを小さくするマスクが生成される。マスク、フォアグラウンド画像およびバックグラウンド画像の総サイズを減少するには、他の方法を使用することもできる。
【００８６】
フォアグラウンドバックグランドセグメンタ１２０４は、マスクセパレータ１２０２からのマスクとドキュメント画像を受け取る。フォアグラウンドバックグラウンドセグメンタ１２０４は、マスクを使用してフォアグラウンド画像とバックグラウンド画像をドキュメント画像から生成する。ドキュメント画像のピクセルごとに、マスクの対応するピクセルが参照される。ピクセルは、マスクの対応するピクセルに基づいてフォアグラウンド画像またはバックグラウンド画像に割り振られる。例えば、マスクの対応するピクセルが「１」であれば、そのピクセルはフォアグラウンド画像に割り当てられる。逆に、マスクの対応するピクセルが「０」であれば、そのピクセルはバックグラウンド画像に割り当てられる。以上から理解されるように、「０」または「１」は、フォアグラウンドまたはバックグラウンドが変化することを示している。
【００８７】
バックグラウンド画像とフォアグラウンド画像に穴（hole）または空き領域（vacant regions）があるのは、そこではピクセルが他方の画像に向けられたためである。空き領域は、フォアグラウンド画像とバックグラウンド画像の総圧縮サイズを減少するようにどのような方法でも処理することができる。１つのアプローチは、これらの空き領域をドントケア（don't care）ピクセルで埋めることである。ドントケアピクセルは、画像の圧縮を向上し、サイズを減少するように選択されている。他のアプローチを使用することが可能であり、これらも本発明の範囲に属するものである。
【００８８】
さらに、フォアグラウンド画像とバックグラウンド画像は、相互にばらばらになっている。しかし、このようにすると、最終的に再結合されるドキュメント画像の中に可視エッジが再現されることになる。これらの可視エッジを低減するためにいくつかのアプローチが使用できる。フォアグラウンド画像とバックグラウンド画像は、いくつかのピクセルが相互に拡張されて、画像がばらばらなることがなくなる。従って、再結合ドキュメント画像の中の可視エッジは減少されることになる。
【００８９】
クラスタリングコンポーネント１２０５は、マスクセパレータ１２０２からマスクを受け取り、クラスタ、マークシーケンスおよび位置情報のライブラリを生成する。クラスタリングコンポーネント１２０５は、一度に１つずつ、マスクからマークを見つけ、それを除去する。クラスタリングコンポーネント１２０５は、既存クラスタのプロパティを格納している少なくとも１つのテーブルを利用する。ドキュメントからの抽出マークのプロパティは、少なくとも１つのテーブル内の既存クラスタのプロパティと高速に比較される。この比較では、マークのビットマップと既存クラスタのビットマップとをタイムリでコストのかかる、ビットごとの比較を行わなくても、ミスマッチを特定することができる。マークのプロパティがテーブル内のプロパティのどれともマッチしないときは、マークが新クラスタとして追加され、ビットごとの比較は回避される。
【００９０】
少なくとも１つのテーブルの１つに入れおくことができる、クラスタの１つのプロパティは、ｘサイズとｙサイズである。ｘサイズとyサイズは、既存クラスタのサイズ情報を示している。マークのxサイズとyサイズは、既存クラスタのxサイズとyサイズと高速に比較されて、ミスマッチを特定することができる。少なくとも１つのテーブルの１つに入れておくことができる、クラスタのもう１つのプロパティは、インクサイズである。インクサイズは、一般的に、マークまたはクラスタ内の黒ピクセルと総ピクセルの比率を表している。同様に、マークのインクサイズは、ミスマッチを特定するために既存クラスタのインクサイズと高速に比較することができる。少なくとも１つのテーブルの１つに入れておくことができる、クラスタの最後のプロパティは、縮小マークまたは画像である。縮小マークまたは画像は、マークおよび/またはクラスタのビットマップのピクセルサイズ縮小バージョンである。同様に、縮小マークは、ミスマッチを特定するために既存クラスタの縮小マークまたは縮小画像と高速に比較することができる。これらのプロパティは、図１と図６を参照して詳しく説明されている。
【００９１】
少なくとも１つのテーブルを使用する比較でミスマッチとならなかった既存クラスタが残っていれば、マークのビットマップは、残っている既存クラスタのビットマップと比較される。このビットマップの比較はビットごとの比較である。「ｘｏｒ」距離のような距離は、ビットごとの比較によって計算される。距離が小さくなると、マッチは近接することになる。他の適当な距離比較を使用することが可能であり、これらは本発明の範囲に属するものである。最もマッチした既存クラスタが特定されると、マークは、マッチした既存クラスタに属するマークの集合に追加される。
【００９２】
マークエンコーダ１２０６は、マスク、クラスタのライブラリ、マークシーケンスおよび位置情報を、クラスタリングコンポーネント１２０５から受け取り、マスクを符号化して、圧縮ビットまたは圧縮マスクビットストリームをマスクから生成する。マスクエンコーダ１２０６では、どの符号化手法でも使用できる。しかし、当然に理解されるように、マスクはバイナリであるので、マスクのバイナリ側面を利用する圧縮方法を選択すべきである。典型的には、マスクを符号化するためにバイレベル（bi-level）可逆圧縮方式が使用される。しかし、他の圧縮方法または方式を使用することも可能である。
【００９３】
マスクを符号化するために使用できる圧縮方式の例として、ＣＣＩＴＴ（Consultative Committee on International Telephone and Telegraph）がある。ＣＣＩＴＴは、現在では、ＩＴＵ−Ｔ（International Telecommunications Union  Telecommunications Sector、１９９４年に名前が改められる）として知られている。ＣＣＩＴＴは、標準化グループであり、ファックス／モデム通信に関する可逆圧縮技術の代名詞になっている。このタイプの圧縮は、黒白のテキストと画像、つまり、バイレベル画像で最も効率よく働いている。代表的な圧縮比率は、旧バージョンV.42bisでは４：１、新バージョンV.44 2000では６：１であり、この新バージョンはLempel-Ziv-Jeff-Heath（ＬＺＪＨ）圧縮アルゴリズムに準拠している。
【００９４】
フォアグラウンドエンコーダ１００８は、フォアグラウンド画像を受け取り、フォアグラウンド画像から圧縮ビットまたは圧縮フォアグラウンドビットストリームを生成するようにフォアグラウンド画像を符号化する。フォアグラウンドエンコーダ１２０８では、どの符号化手法を使用することも可能である。例えば、フォアグラウンド画像を符号化するためにプログレッシブ波長符号化（progressive wavelength encoding）またはプログレッシブ変換符号化（progressive transform encoding）を使用することができる。
【００９５】
バックグラウンドエンコーダ１２１０は、バックグラウンド画像を受け取り、バックグラウンド画像から圧縮ビットまたは圧縮バックグラウンドビットストリームを生成するようにバックグラウンド画像を符号化する。例えば、バックグラウンド画像を符号化するためにプログレッシブ波長符号化またはプログレッシブ変換符号化を使用することができる。
【００９６】
上述したように、フォアグラウンド画像とバックグラウンド画像は、ドントケア領域をもっている。ドントケア領域は、いくつかの方法で処理することができる。１つのアプローチは、ドントケア領域をデータで埋めて、正規の圧縮方式を使用することである。最も単純な方法は、画像のドントケア領域を、その画像の平均ピクセル値で埋めることである。しかし、この方法によると、マスク境界に目立った不連続性が発生する。また、この方法によると、ピーク信号対雑音比（ＰＳＮＲ）が一定のとき、必要とするビットレートが増加し、マスクまたはドントケア領域境界付近に目立ったリンギングが発生することになる。別の方法は、各ピクセルに、最も近接した非マスク（または非ドントケア領域）ピクセルのカラーを付けることである。標準的モフォロジックアルゴリズム（morphology algorithm）によれば、このプロセスは、マスクの下のVoronoi-filledドントケア領域に通じるすべてのピクセルにわたって２回パスするだけで行うことができる。そのあと、フォアグラウンドまたはバックグラウンド画像が再構築されると、再構築画像はローパスされ、既知のピクセルがその正しい値に復元される。ローパスフィルタのカットオフ周波数があまり低いときは、シャープなエッジが現れるため、境界付近の必要ビットレートと目立ったリンギングが増加することになる。
【００９７】
コンバイナコンポーネント１２１２は、マスクエンコーダ１２０６、フォアグラウンドエンコーダ１２０８およびバックグラウンドエンコーダ１２１０から圧縮ビットを受け取り、そのビットを出力ストリームまたは出力ファイルに結合する。コンバイナコンポーネント１２１２は、符号化種別、ディクショナリ、ライブラリなどのように、ドキュメント画像を再構築するためにデコーダによって使用できる情報を特定または提供するヘッダ情報を、出力ファイルに入れることができる。
【００９８】
本発明の種々側面を別のコンテキストからとらえるために、図１２と以下の説明は、本発明の種々側面が実現できる１つの、可能な適当なコンピューティング環境１２１０の概要を要約して説明することを目的としている。当然に理解されるように、このコンピューティング環境１２１０は、１つの可能なコンピューティング環境にすぎず、本発明を採用できるコンピューティング環境を限定するものではない。本発明は、１または複数のコンピュータ上で実行できるコンピュータ実行可能命令という広いコンテキストの中で上述してきたが、当然に理解されるように、本発明は、他のプログラムモジュールとの組み合わせでおよび／またはハードウェアとソフトウェアの組み合わせとして実現することも可能である。一般的に、プログラムモジュールには、特定のタスクを実行しまたは特定の抽象データ型を実装しているルーチン、プログラム、コンポーネント、データ構造などがある。さらに、当然に理解されるように、本発明は、他のコンピュータシステム構成で実施することが可能であり、その中には、シングルプロセッサまたはマルチプロセッサコンピュータシステム、ミニコンピュータ、メインフレームコンピュータなどのほかに、パーソナルコンピュータ、ハンドヘルドコンピューティングデバイス、マイクロプロセッサベースまたはプログラマブルコンシューマエレクトロニックスなどが含まれ、これらの各々は、１または複数の関連デバイスに結合して動作させることが可能になっている。本発明の図示側面は、ある種のタスクが通信ネットワークを通してリンクされたリモート処理デバイスによって実行されるような、分散コンピューティング環境で実施することも可能である。分散コンピューティング環境では、プログラムモジュールは、ローカルとリモートの両方のメモリストレージデバイスに置いておくことができる。
【００９９】
図１３は、ここで説明しているシステムと方法をサポートする１つの、可能なハードウェア構成を示す図である。当然に理解されるように、スタンドアロンアーキテクチャが図示されているが、本発明によれば、任意の適当なコンピューティング環境を採用することも可能である。例えば、本発明によれば、採用できるコンピューティングアークテクチャとしては、スタンドアロン、マルチプロセッサ、分散、クライアント／サーバ、ミニコンピュータ、メインフレーム、スーぱコンピュータ、デジタルおよびアナログがあるが、これらに限定されない。
【０１００】
図１３を参照して説明すると、本発明の種々側面を実現する例示環境１３１０はコンピュータ１３１２を含み、コンピュータは処理ユニット１３１４、システムメモリ１３１６、およびシステムメモリを含む種々のシステムコンポーネントを処理ユニット１３１４に結合しているシステムバス１３１８を装備している。処理ユニット１３１４は、商用化されている種々のプロセッサのどれであってもよい。デュアルマイクロプロセッサおよび他のマルチプロセッサアーキテクチャも処理ユニット１３１４として使用することができる。
【０１０１】
システムバス１３１８は、種々タイプのバス構造のいずれかにすることができ、その中には、商用化されている種々のバスアーキテクチャのいずれかを採用するメモリバスまたはメモリコントローラ、ペリフェラルバス、およびローカルバスが含まれている。コンピュータメモリ１３１６には、リードオンリメモリ（ＲＯＭ）１３２０とランダムアクセスメモリ（ＲＡＭ）１３２２がある。スタートアップ時のときのように、コンピュータ１３１２内のエレメント間で情報を転送するのを支援する基本ルーチンからなる基本入出力システム（ＢＩＯＳ：Basic Input/Output System）は、ＲＯＭ１３２０に格納されている。
【０１０２】
コンピュータ１３１２は、ハードディスクドライブ１３２４、例えば、取り外し可能ディスク１３２８との間で読み書きを行う磁気ディスクドライブ１３２６、例えば、ＣＤ−ＲＯＭディスク１３３２を読み取り、あるいは他の光媒体との間で読み書きを行う光ディスクドライブを、さらに装備することができる。ハードディスクドライブ１３２４、磁気ディスクドライブ１３２６、および光ディスクドライブ１３３０は、それぞれハードディスクドライブインタフェース１３３４、磁気ディスクドライブインタフェース１３３６、および光ドライブインタフェース１３３８を介して、システムバス１３１８に接続されている。コンピュータ１３１２は、典型的には、なんらかの形体のコンピュータ可読媒体を少なくとも装備している。コンピュータ可読媒体は、コンピュータ１３１２によってアクセス可能であれば、どのような媒体でも利用可能である。例を挙げると、コンピュータ可読媒体としては、コンピュータストレージ媒体と通信媒体があるが、これらに限定されない。コンピュータストレージ媒体には、コンピュータ可読命令、データ構造、プログラムモジュール、その他のデータなどの情報を格納するために任意の方法または記述で実現されている揮発性および不揮発性の、取り外し可能および取り外し不能媒体が含まれている。コンピュータストレージ媒体としては、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリや他のメモリテクノロジ、ＣＤ−ＲＯＭ、ＤＶＤ（digital versatile disk）や他の磁気ストレージデバイス、あるいはコンピュータ１３１２によってアクセスできる必要情報を格納するために使用できる他の媒体がある。通信媒体は、典型的には、コンピュータ可読命令、データ構造、プログラムモジュールまたは他のデータを、搬送波などの変調されたデータ信号、他のトランスポートメカニズムで具現化しており、その中には任意の情報配信媒体が含まれる。「変調されたデータ信号」という用語は、信号の中の情報を符号化するような方法で、その特徴の１または複数のセットまたは変更されている信号を意味している。通信媒体の例としては、ワイヤドネットワーク、直接ワイヤドコネクションのようなワイヤド媒体、および音響、ＲＦ、赤外線および他のワイヤレス媒体のようなワイヤレス媒体があるが、これらに限定されない。上記に挙げたものを任意に組み合わせたものも、当然にコンピュータ可読媒体の範囲に含まれる。
【０１０３】
いくつかのプログラムモジュールは、ドライブおよびＲＡＭ１３２２に格納しておくことができ、その中には、オペレーティングシステム１３４０、１または複数のアプリケーションプログラム１３４２、他のプログラムモジュール１３４４、およびプログラム非割り込みデータ１３４６が含まれている。コンピュータ１３１２内のオペレーティングシステム１３４０は、いくつかの商用化オペレーティングシステムのどれであってもよい。
【０１０４】
ユーザは、キーボード１３４８およびマウス１３５０などのポインティングデバイスを通して、コマンドと情報をコンピュータ１３１２に入力することができる。その他の入力デバイス（図示せず）としては、マイクロホン、ＩＲリモートコントロール、ジョイスティック、ゲームパッド、サテライトディッシュ、スキャナなどがある。これらおよび他の入力デバイスは、システムバス１３１８に結合されているシリアルポートインタフェース１３５２を通して処理ユニット１３１４に接続されていることが多いが、パラレルポート、ゲームポート、ＵＳＢ（universal serial bus）、ＩＲインタフェースなどの、他のインタフェースで接続することもできる。モニタ１３５４、または他タイプのディスプレイデバイスも、ビデオアダプタ１３５６などのインタフェースを介して、システムバス１３１８に接続されている。モニタのほかに、コンピュータは、スピーカやプリンタなどの、他の周辺出力デバイス（図示せず）を装備している。
【０１０５】
コンピュータ１３１２は、リモートコンピュータ１３５８などの、１または複数のリモートコンピュータへの物理コネクションを使用するネットワーキング環境で動作することができる。リモートコンピュータ１３５８は、ワークステーション、サーバコンピュータ、ルータ、パーソナルコンピュータ、マイクロプロセッサベースのエンターテインメントアプライアンス、ピアデバイスまたは他の共通ネットワークノードにすることが可能であり、説明を簡単にする目的で、メモリストレージデバイス１３６０だけが図示されているが、典型的には、コンピュータ１３１２に関連して上述したエレメントの多くまたは全部を装備している。図示の論理コネクションは、ＬＡＮ（local area network）１３６２とＷＡＮ（wide area network）１３６４を含んでいる。このようなネットワーキング環境は、オフィス、企業内ネットワーク、イントラネットおよびインターネットでは普通になっている。
【０１０６】
ＬＡＮネットワーキング環境で使用されるときは、コンピュータ１３１２は、ネットワークインタフェースまたはアダプタ１３６６を通してローカルネットワーク１３６２に接続されている。ＷＡＮネットワーキング環境で使用されるときは、コンピュータ１３１２は、典型的には、モデム１３６８を装備しており、またはＬＡＮ上のコミュニケーションサーバに接続されているか、インターネットなどのＷＡＮ１３６４上でコミュニケーションを確立するための他の手段を備えている。モデム１３６８は、内蔵型と外付け型があり、どちらも、シリアルポートインタフェース１３５２を介してシステムバス１３１８に接続されている。ネットワーキング環境では、コンピュータ１３１２に関連して図示したプログラムモジュールまたはその一部は、リモートのメモリストレージデバイス１３６０に置いておくことができる。当然に理解されるように、図示のネットワークコネクションは例示であり、コンピュータ相互間の通信リンクを確立する他の手段を使用することもできる。
【０１０７】
図１４は、本発明が作用し合うことができる例示のコンピューティング環境１４００を示す概略ブロック図である。システム１４００は、１または複数のクライアント１４１０を含んでいる。クライアント１４１０は、ハードウェアおよび／またはソフトウェア（例えば、スレッド、プロセス、コンピューティングデバイス）にすることができる。また、システム１４００は、１または複数のサーバ１４３０を含んでいる。サーバ１４３０も、ハードウェアおよび／またはソフトウェア（例えば、スレッド、プロセス、コンピューティングデバイス）にすることができる。サーバ１４３０には、例えば、本発明を採用することによって変換を行うスレッドを置いておくことができる。クライアント１４１０とサーバ１４３０との間で行われる１つのコミュニケーションは、２またはそれ以上のコンピュータプロセス間で伝送されるように構成されたデータパケットの形になっている。システム１４００は、クライアント１４１０とサーバ１４３０間のコミュニケーションを容易化するために採用できる通信フレームワーク１４５０を含んでいる。クライアント１４１０は、クライアント１４１０側で使用される情報を格納するために使用できる１または複数のクライアントデータストア１４６０に動作可能状態で接続されている。同様に、サーバ１４３０は、サーバ１４３０側で使用される情報を格納するために使用できる１または複数のサーバデータストア１４４０に動作可能状態で接続されている。
【０１０８】
以上、本発明の例を示して説明してきた。当然のことであるが、本発明を説明するために想到し得るコンポーネントまたは方法の組み合わせをすべて説明することは不可能であるが、通常の知識を有するものならば理解されるように、本発明によれば、多数のその他の組み合わせや置換も可能である。従って、本発明は、請求項に記載の本発明の精神と範囲に属するような改変、改良および変更をすべて包含するものである。さらに、「含む（include）」という用語が詳細説明または請求項の記載の中で用いられている限りにおいて、この用語は、請求項の記載の中で移行語として用いられるとき解釈される「含む（comprising）」という用語と同じように、「包含的」であることを意味している。
【図面の簡単な説明】
【図１】本発明の一側面にかかるクラスタリングシステムを示すブロック図である。
【図２】本発明の一側面にかかる例示マークを示す図である。
【図３】４連結性プロパティを示す図である。
【図４】８連結性プロパティを示す図である。
【図５】本発明の一側面にかかる例示結合マークを示す図である。
【図６】本発明の一側面にかかるクラスタリングシステムを示すブロック図である。
【図７】本発明の一側面にかかる２次元テーブルを示すブロック図である。
【図８】本発明の一側面にかかる２次元テーブルのエントリを示すブロック図である。
【図９】本発明の一側面にかかる例示クラスタを示す図である。
【図１０】本発明の一側面にかかる例示エラーマップを示す図である。
【図１１】本発明の一側面にかかるクラスタリングを行う方法を示すフロー図である。
【図１２】本発明の一側面にかかるクラスタリングを利用した画像符号化システムを示すブロック図である。
【図１３】本発明を機能させることができる例示動作環境を示す図である。
【図１４】本発明によるコミュニケーション環境を示す概略ブロック図である。
【符号の説明】
１００  クラスタリングシステム
１０２  ドキュメント
１０４  マークエクストラクタ
１０６  プロパティマッチングコンポーネント
１１０  シンボルマッチング
１１２  ストレージコンポーネント
１１４  クラスタプロパティ
【図１】
0004152789.tif 000003
【図２】
0004152789.tif 000004
【図３】
0004152789.tif 000005
【図４】
0004152789.tif 000006
【図５】
0004152789.tif 000007
【図６】
0004152789.tif 000008
【図７】
0004152789.tif 000009
【図８】
0004152789.tif 000010
【図９】
0004152789.tif 000011
【図１０】
0004152789.tif 000012
【図１１】
0004152789.tif 000013
【図１２】
0004152789.tif 000014
【図１３】
0004152789.tif 000015
【図１４】
0004152789.tif 000016