"レンダリングドキュメントのコンテンツを識別する微細固有特徴を生成する方法であって、電子ドキュメントレンダリングシステムによってレンダリングされたドキュメントのパターンを識別するために、レンダリングされたドキュメントが電子的に生成されたファイルフォーマットとは無関係に、画像ベース技術を適用し、前記画像ベース技術を適用することは、i.電子プロセッサが、ドキュメントの画像近傍局所のキーポイント候補の位置を識別し、ii.前記電子プロセッサが、前記ドキュメントのコンテンツを示すパターンを識別する微細固有特徴を形成するために、キーポイント候補の前記位置を結合する、ことを含む、方法。前記キーポイント候補を識別することは、前記レンダリングされたドキュメントのページを、一度に一走査線ずつ、走査し、走査線の各々について、前記ドキュメントの画像画素を検討し、現在の画素が新しいブロブに属するか、以前から存在していたブロブに属するか、を現在の画素の位置の各々について判断し、前記ドキュメントのページのブロブ構造およびキーポイントを構築するために、前記現在の画素の周囲で、前記画像近傍局所に対応する画素の近傍局所を使用し、近傍画素値および以前のブロブの割り当てにもとづいて、前記現在の画素の位置に適用されるべきアクションを定義するアクションルックアップテーブルへアドレスを設定し、設定された前記アドレスにもとづいて、前記アクションルックアップテーブルから適切なアクションを取り出し、i前記現在の画素コンテンツが既存のブロブに追加される、ii前記現在の画素に新しいブロブを割り当てる、iii画素位置で既存のブロブを併合する、の少なくとも一つが行われるように、取り出した前記アクションを実行し、前記現在の画素の状態を反映するためにブロブ状態を更新し、前記現在の画素の位置がキーポイント候補であるか否か判断し、検討中の走査線の次の画素の位置に移動し、上記ステップを繰り返し、検討中の走査線の最後に到達するまで、移動し処理を繰り返すことを継続し、現在開いているブロブのいずれかを閉じることができるか否か判断するために、走査線の最後に到達すると、ブロブを閉じる処理を開始し、現在の走査線オペレーションの間、ブロブに新しい画素が追加されていなければ、ブロブを閉じることができ、走査オペレーションの最後にその属性を計算するために閉じることができるブロブのすべてを処理し、前記走査線処理の最後に、処理された閉じたブロブに対応する結果データおよびキーポイントを出力し、最後の走査線が処理されるまで、前の走査線の最後の画素が処理されると、次の走査線に移動し、上記処理ステップを繰り返す、ことを含む、請求項1に記載の方法。前記微細固有特徴を形成することは、単語サイズの微細固有特徴を形成することを含み、前記単語サイズの微細固有特徴を形成することは、単語もしくは近傍局所のキーポイント候補のすべての中心位置を計算し、方向および距離の双方で、時計回りの方向の順序で、前記キーポイント候補をソートし、前記中心位置までのキーポイント候補の距離を計測することによって、前記微細固有特徴を計算し、所定の量子化閾値のセットを用いて、前記キーポイントから中心位置までの距離を量子化することによって、キーポイントの各々についての整数値を決定する、ことを含み、前記量子化閾値はキーポイントの分布を検討することによって、経験的に決定される、請求項1に記載の方法。レンダリングされたドキュメントのコンテンツを識別するために使用される微細固有特徴を生成するように構成されているドキュメント画像処理システムであって、レンダリングされたドキュメントが電子的に生成されたファイルフォーマットとは無関係に、電子ドキュメントレンダリングシステムによってレンダリングされたドキュメントのパターンを識別する画像ベースシステム、を備え、前記画像ベースシステムは、i.前記ドキュメントの画像近傍局所でキーポイント候補の位置を識別するように構成されているキーポイント候補識別手段と、ii.前記ドキュメントのコンテンツを示すパターンを識別する微細固有特徴を形成するために、前記キーポイント候補の位置を結合する手段と、を含む、ドキュメント画像処理システム。本発明の第1の態様は、レンダリングドキュメントのコンテンツを識別する微細固有特徴を生成する方法であって、電子ドキュメントレンダリングシステムによってレンダリングされたドキュメントのパターンを識別するために、レンダリングされたドキュメントが電子的に生成されたファイルフォーマットとは無関係に、画像ベース技術を適用し、前記画像ベース技術を適用することは、i.電子プロセッサが、ドキュメントの画像近傍局所のキーポイント候補の位置を識別し、ii.前記電子プロセッサが、前記ドキュメントのコンテンツを示すパターンを識別する微細固有特徴を形成するために、キーポイント候補の前記位置を結合する、ことを含む。本発明の第2の態様は、第1の態様の方法であって、前記キーポイント候補を識別することは、前記レンダリングされたドキュメントのページを、一度に一走査線ずつ、走査し、走査線の各々について、前記ドキュメントの画像画素を検討し、現在の画素が新しいブロブに属するか、以前から存在していたブロブに属するか、を現在の画素の位置の各々について判断し、前記ドキュメントのページのブロブ構造およびキーポイントを構築するために、前記現在の画素の周囲で、前記画像近傍局所に対応する画素の近傍局所を使用し、近傍画素値および以前のブロブの割り当てにもとづいて、前記現在の画素の位置に適用されるべきアクションを定義するアクションルックアップテーブルへアドレスを設定し、設定された前記アドレスにもとづいて、前記アクションルックアップテーブルから適切なアクションを取り出し、i前記現在の画素コンテンツが既存のブロブに追加される、ii前記現在の画素に新しいブロブを割り当てる、iii画素位置で既存のブロブを併合する、の少なくとも一つが行われるように、取り出した前記アクションを実行し、前記現在の画素の状態を反映するためにブロブ状態を更新し、前記現在の画素の位置がキーポイント候補であるか否か判断し、検討中の走査線の次の画素の位置に移動し、上記ステップを繰り返し、検討中の走査線の最後に到達するまで、移動し処理を繰り返すことを継続し、現在開いているブロブのいずれかを閉じることができるか否か判断するために、走査線の最後に到達すると、ブロブを閉じる処理を開始し、現在の走査線オペレーションの間、ブロブに新しい画素が追加されていなければ、ブロブを閉じることができ、走査オペレーションの最後にその属性を計算するために閉じることができるブロブのすべてを処理し、前記走査線処理の最後に、処理された閉じたブロブに対応する結果データおよびキーポイントを出力し、最後の走査線が処理されるまで、前の走査線の最後の画素が処理されると、次の走査線に移動し、上記処理ステップを繰り返す、ことを含む。本発明の第3の態様は、第1の態様の方法であって、前記微細固有特徴を形成することは、単語サイズの微細固有特徴を形成することを含み、前記単語サイズの微細固有特徴を形成することは、単語もしくは近傍局所のキーポイント候補のすべての中心位置を計算し、方向および距離の双方で、時計回りの方向の順序で、前記キーポイント候補をソートし、前記中心位置までのキーポイント候補の距離を計測することによって、前記微細固有特徴を計算し、所定の量子化閾値のセットを用いて、前記キーポイントから中心位置までの距離を量子化することによって、キーポイントの各々についての整数値を決定する、ことを含み、前記量子化閾値はキーポイントの分布を検討することによって、経験的に決定される。本発明の第4の態様は、レンダリングされたドキュメントのコンテンツを識別するために使用される微細固有特徴を生成するように構成されているドキュメント画像処理システムであって、レンダリングされたドキュメントが電子的に生成されたファイルフォーマットとは無関係に、電子ドキュメントレンダリングシステムによってレンダリングされたドキュメントのパターンを識別する画像ベースシステム、を備え、前記画像ベースシステムは、i.前記ドキュメントの画像近傍局所でキーポイント候補の位置を識別するように構成されているキーポイント候補識別手段と、ii.前記ドキュメントのコンテンツを示すパターンを識別する微細固有特徴を形成するために、前記キーポイント候補の位置を結合する手段と、を含む。本発明は、ドキュメント比較のための異なるアプローチに関する。既存の方法で行われているように、テキストコンテンツを直接的に比較するのではなく、本発明では、ドキュメントコンテンツをレンダリングし、画像ベース技術を使用してドキュメントのパターンを識別する。レンダリングされた画像は、ユーザがドキュメントのページで見るものを反映するユニバーサルな表現であり、アプリケーション固有情報や複雑な独自のフォーマットを有するオリジナルドキュメントコンテンツを解釈する必要がない。この画像ベース技術を使用する場合、ドキュメント間の差異を強調するために、異なるページ間の同様のパターンを探すために、さらなる処理を実行することができる。このような画像ベースマッチングの成功は、識別されたパターンのソースドキュメントと改変ドキュメントとの間での適切な比較を行うために、画像パターンを適切に識別する能力に依存する。本発明では、ソースドキュメントおよび改変ドキュメントの間でのドキュメントコンテンツのマッチング、および/もしくは、画像データベースからのマッチング画像の検出を許可するために、ドキュメントのページコンテンツを識別するために使用される、二次元微細固有特徴を用いた効率的な方法およびシステムを開示する。本発明の方法およびシステムは、ドキュメントの画像近傍局所でのキーポイント候補の識別、および、ドキュメントのコンテンツを表示するパターンを識別する明確に区別可能な二次元微細固有特徴を形成するための特定の手法におけるキーワード候補位置の結合、にもとづく。本発明の発明者は視認可能な固有特徴に関するコンセプトを以前にも紹介している特許文献1、特許文献2、特許文献3など。以前の開示は粗い固有特徴に関連するものであった。以前の開示は、本発明の微細固有特徴コンセプトのコンテキストおよび背景についての教示を提供するが、微細固有特徴コンセプトは、その応用、構成、および、オペレーションの態様において、粗い固有特徴とは異なる。大きな差異は、粗い固有特徴を使用した方法が、雑音、照明のばらつき、および、投影歪みなどの劣化の影響を多く受ける雑音を含む低品質のカメラ入力などのために設計されていることである。一方、本発明の教示が適用されるドキュメントコンテンツ比較のコンテキストにおいては、他の処理技術を必要とする良質なレンダリングの電子コンテンツに適用することが可能である。さらに、粗い固有特徴のコンセプトは、画像についてサーチされた識別のために重要であると判断されたキーポイントおよび関連する画素だけが使用され実施形態のいくつかにおいては、数千のあり得るセットのうち数百のセットだけが使用され、画像の各画素を検討しない。本発明の微細固有特徴技術は、単語の単一の文字の変更もしくは文字の部分的変更を区別するために、ソースドキュメントおよび改変ドキュメントの画像の各画素を検討するように設計されている。したがって、本発明の微細固有特徴は抽出される固有特徴のすべてを使用する。これにより、変更がどんなに小さくとも、ドキュメントにおける変更の各々を識別し、強調するシステムにおいて、本発明のコンセプトを使用することができる。したがって、ユーザが隣合わせで表示されたソースドキュメントおよび改変ドキュメントを見る場合、ユーザは変更のすべてを見ることができる。微細固有特徴を使用する技術では、微細固有特徴を取得するためのメモリ使用量が比較的少なく、計算オーバーヘッドが低い。したがって、本発明のコンセプトは大きな画像データベースにおいて画像を検索するためにも使用することができる。微細固有特徴を計算することはOCR光学文字認識オペレーションより時間を要さず、微細固有特徴を使用する技術は、たとえば、プリンタで印字されたテキストに加えて、信頼可能な光学文字認識が困難であることが知られている線画、描画、手書きテキスト、および、その他のアイテムなどのページ上の任意のタイプのマークを扱うことができる点で光学文字認識よりも優れている。結果として取得される微細固有特徴は、コンテンツの高性能かつ適切な二次元視認可能パターンを検出する際に、よく特色を示し、効率的である。動作速度が問題とはならない場合、微細固有特徴技術の結果は、光学文字認識やたとえば、コンテンツのタイプによってマッチングの結果を改善するために、レンダリングされた画像における他のタイプのコンテンツを識別するために、形状認識、テンプレートマッチング、画像マッチング、テクスチャ解析などの他の画像ベース技術と組み合わされてもよい。本発明における二次元微細視認可能特徴はドキュメントコンテンツを識別し、マッチングするために使用される。微細固有特徴は、コンテンツの外観の固有な二次元位置の特徴を取得する。微細固有特徴は、ロバストであり、よく特色を示し、ルックアップが迅速であり、少ない記憶容量しか必要とせず、大きなドキュメントサイズに対応することができる。微細固有特徴は任意のドキュメントコンテンツを扱うことができ、光学文字認識よりも効率的に処理を行うことができる。図1A~図1CはソースPDFドキュメント100の第一のページの例を示し、図2A~図2Cは対応する改変PDFドキュメント200の第一のページの例を示す。目的は2つのドキュメントを比較し、コンテンツもしくはレイアウト配置のすべての変更を検出して強調し、効率的、直感的、かつ、見やすく、変更を視覚的に目立たせることである。図3A~図3Eは、微細視認可能特徴にもとづく本発明の方法およびシステムを用いて取得することができる、図1A~図1Cおよび図2A~図2Cの第一ページの入力の比較結果の出力300を例示する。図1A~図1Cおよび図2A~図2Cのコンテンツは比較的単純であり、定形書式のようなレイアウトの半構造的テキストを含むとはいえ、このようなページをユーザが素早く見渡し、すべての変更を指摘することは通常困難である。人間の脳は大きな差異をすぐに拾い上げることができるが、ページの構造およびレイアウト全体が似通っている場合、微細な変更をうまく認識するためには、高レベルの視認能力および集中力を必要とする。図1A~図1Cおよび図2A~図2Cに示される書類に類似する契約書の変更および補正を受信する顧客サービススタッフは、変更を探すドキュメントを細かく調べなければならない。手動による比較処理は、時間を要し、退屈であり、ミスを生じやすい。熟練の顧客サービススタッフであっても一定の時間を越えると急速に疲労し、ミスが増える。量や配送日付などの単一の変更を見逃すことによって、重大なビジネスリスクの影響を企業に与えるかもしれない。図3A~図3Eにおいて、図1A~図1C、および/もしくは、図2A~図2Cへのすべての変更は適切に強調され、コンテンツが常に位置合わせされるので、ユーザは隣合わせの表示で2つの画像のコンテンツを視覚的に比較することができ、変更を迅速に認識しやすい。たとえば、図3A~図3Eでは、ペアを比較するために、隣合わせで、該ペアが表示もしくは印刷されている。比較される入力ページは順次処理される。この実施形態において、微細視認可能固有特徴はドキュメントコンテンツにおける同様のパターンを識別するために使用される。二次元視認可能固有特徴はドキュメントページの各々について個別に抽出されて比較される。結果として得られる変更は図3A~図3Eに示されるようにその位置で強調される。本発明の方法の適切さによって、高品質の出力が可能となる。図4は、ドキュメント画像の微細固有特徴を生成する際に使用される、ブロブおよびキーポイント候補を識別する微細固有特徴生成方法400を例示する。本発明において、キーポイントは、コーナー、接合点、および/もしくは、明るいまたは暗いブロブなどの画像における特色を示す位置の識別子である。ブロブは、調べられている画像の画素のグループを含み、キーポイント候補は、対応するブロブの近傍局所画素の一部のドキュメントのコンテンツの明確に識別することができる視認可能なパターンの位置に関連する。キーポイント候補の最終的なセットは、識別され、ブロブ処理の間、繰り返し、併合され、改善されたキーポイントのセットの中から選択される。方法400は、一度に一本の走査線ずつ404、一般的なラスタ走査の順番で、供給されたドキュメントページ402を下に進む。走査線の各々について、画素は、一度に一画素ずつ406、順次調べられる。現在の画素位置の各々について、方法400は、現在の画素が新しいブロブの一部であるか、既存のブロブの一部であるか、を判断し、さらに、現在の画素位置が固有特徴のキーポイント候補であるとみなされるか否か、判断する。実施形態において、この方法は迅速な単一パスのアルゴリズムである。方法400は、ページ全体のブロブ構造およびキーポイントを繰り返し生成するために、対象となっている現在の画素の周囲の小さな近傍領域の画素408を使用する。このアルゴリズムは画像における一つ前の走査線だけを使用するので、小容量のメモリしか必要としない。計算負荷は、すべてのあり得るブロブ処理アクションを予め符号化し、アクションルックアップテーブル410に記憶しておくことにより、最小化される。現在の画素位置の各々について、画素近傍のコンテキスト408が収集され、アクションルックアップテーブル410のアドレスを形成するために整理される。このアドレスにおけるアクションテーブルのコンテンツは、近傍画素値の構成および前のブロブ割り当てにもとづいて、現在の画素位置で適用されるべきアクションを定義している。アクションルックアップテーブル410に記憶されたアクションの中から適切なアクションが識別され、取り出される。入力画素値と前のブロブ割り当てとの組み合わせには多くのパターンがあり得るが、結果として取得されるあり得るアクションの数は実用的には限定される。一般的なアクションの例は、たとえば、1現在の画素に新しいブロブを割り当てる、2現在の画素の左、左上、真上、もしくは右上のいずれかにある既存の前のブロブと現在の画素を併合する、32つの既存のブロブを結合し、現在の画素を結合したブロブと併合する、などである。少数のあり得るアクションは迅速かつ効率的な参照のためにアクションテーブルに記憶される。生成されたアドレスにもとづいて、アクションテーブルから取り出される対象となっている、現在の画素についての適切なアクションが、次に、実行される414。結果として、現在の画素のコンテンツは既存のブロブに追加されてもよく、もしくは、新しいブロブが対象となっている現在の画素に割り当てられてもよく、もしくは、前の2つのブロブが併合されてもよい。ブロブの各々は操作されているシステムメモリにデータ構造によって示される。さらに、一度に一画素ずつ、実行によって、分離したブロブID画像が生成され、更新される414。ブロブID画像の最終的な大きさはオリジナルドキュメント画像と同じである。ブロブID画像の画素値の各々は、その画素位置の現在のブロブID割り当てを示す。アクションが実行され414、現在の画素状態を反映するためにシステムメモリにおいてブロブ状態が更新された後、キーポイント更新オペレーション416は現在の画素位置がキーポイント候補であるか否か判断する。キーポイントは新しい、以前はなかったブロブを発見すると、まず、割り当てられる。本発明の実施形態において、2つの相反するタイプのキーポイントが使用される。1タイプ1のキーポイント:左上方向に進んで探す、2タイプ2のキーポイント:右下方向に進んで探す。現在の画素位置の各々について、a既存のキーポイントの位置が前の位置に相対して更新されてもよく、b新しいキーポイントが割り当てられてもよく、c既存のキーポイントが所定の条件にもとづいて除去されてもよい。たとえば、条件が適切であれば、現在の走査線の前の画素上のタイプ2のキーポイントの位置は現在画素の位置に更新されてもよいし、たとえば、図8A~図8Cにおいて詳細に記載されるように、V形状を形成する2つのブロブの形状において、新しいキーポイントが既存の2つのブロブの交差が集中する位置に導入されてもよい。走査線全体が処理され、走査線の最後の画素418に遭遇するまで、走査線処理はこのような方法で、一度に一画素ずつ、継続される。この時点で、ブロブを閉じる処理420が、現在の開いたブロブのいずれかを閉じることができるか否か判断するために開始される。次の走査線の任意の他のブロブとブロブとの間に不連続な線が少なくとも一つあるので、現在の走査線オペレーションの間、新しい画素が該ブロブに追加されないならば、該ブロブを閉じることができる。閉じることができるすべてのブロブは様々な属性を計算するために処理され、その結果を示すデータおよびキーポイントはキーポイント候補ファイル422に出力される。このオペレーションによって閉じられたブロブによって消費されるメモリは開放され、閉じたブロブのIDのメモリは次の再使用のためにリサイクルされる。記載した実施形態の特定の態様では、開いたブロブの小さなリストを維持し、閉じることができる任意のブロブを、すぐに、除去することによって、小さなメモリ容量でドキュメントページの数千のブロブを処理することができる。前記オペレーションは画像近傍局所でキーポイント候補のセットを識別する。キーポイント候補の位置は、明確な二次元微細固有特徴を形成するために、特定の方法で結合される。最終的に、最後の走査線が処理されるまでたとえば、DONE、走査線処理424を一度に一走査線ずつ行う。図5Aおよび図5Bは、本発明の画像領域局所の局所的画素領域コンテンツの例を示す。図5Aは、5個のドキュメント画像画素500の近傍局所を示す前の走査線で現在の画素BC508の左上、真上、右上にある画素TL502、TC504、TR506の3個の隣接する画素、および、現在の走査線の現在の画素自身であるBC508とその左にある画素BL510の2個の隣接する画素。現在の画素BC508の右にあるX512のマークが付されている画素は含まれない。処理が右方向に進むので、該画素は次の現在の画素となるからである。図5Bは、図5Aと同様の空間配置を有する対応する画素ブロブID割り当てコンテンツを示す。ブロブID画像500aの各々の画素502a~512aは、この位置での現在のブロブID割り当てを示す。局所的近傍コンテンツを形成する画素の特定の数は、特定の実装にもとづいて変更されてもよい。図6は走査線オペレーション600の間、キーポイントの位置を更新し、ブロブを生成し、管理し、開放する処理を示す。開始時に、利用可能なブロブID602のスタックが初期化される。走査線処理604の間に新しいブロブに遭遇すると、新しいブロブが割り当てられ606、スタックの利用可能なブロブIDの上部からIDを割り当てられる602。新しく生成されたブロブは開いたブロブ608の管理リストに追加される。ブロブのデータコンテンツは以下のようなアイテムを含む。1画素数、2ブロブの位置を決定するための連続するx-yの合計、3ブロブの境界および空間的範囲を決定する境界ボックス、4次のブロブおよび前のブロブにリンクするポインタ。このデータは新しいブロブ割り当て毎に初期化される。開いたブロブのデータコンテンツは走査線処理の間にしばしば更新される。新しい画素が既存の開いたブロブに遭遇し、併合されるからである。たとえば、新しい画素が追加されると、画素の数が増加し、現在の画素の位置を反映するために境界ボックスが更新される。アクションコードは、もしあれば、画素毎のサイクルで、開いたブロブのどれが更新されるべきかを決定する。アクションコードは、近傍局所において、画素コンテキスト610を収集し、アクションルックアップテーブル612にアクセスするためにアドレスを形成するためにそれを結合することによって取得される。次に、適切なアクションがアクションルックアップテーブルから取り出され、実行される。アクションは、どの開いたブロブが更新されるべきか、および、どの開いたブロブが併合されることができるか、を示す。さらに、キーポイントの位置も、現在の画素のシチュエーションによって更新される614。最後に、走査線の各々の最後で、閉じることができる任意のブロブを、関連するキーポイントすなわち、閉じられたブロブと関連するキーポイント候補とともにキーポイント候補ファイル618に書き出す616。その後、その開いたブロブを保持していたメモリが開放され、対応する開いたブロブのためのIDが利用可能なIDのスタック602に再使用のために戻され、新しい割り当てに利用可能となる。これにより、ブロブのサイクルが完了する。図7Aおよび図7Bは前の2つの開いたブロブを併合するアクションの例を示す。この例では、現在の画素BC508がTL502およびTR506と同じタイプであることが判断され、BL510およびTC504がブロブに割り当てられていない対応するブロブID=0。図7Aに、シェーディングパターンによって、画素タイプが示されている。ここで、同じタイプとは、アプリケーションによる。たとえば、TL、TRおよびBCは二値ドキュメント画像の黒画素であってもよく、所定の閾値より上または下のグレイスケール値であってもよく、同じ値を有するRGBカラー画素であってもよい。図7Bにおいて、前の走査線には少なくとも2つの開いたブロブがある。ID=3が割り当てられているITLブロブ502aおよびID=5が割り当てられているITRブロブ506aである。前の走査線処理の間、これらは独立した開いたブロブであり、まだ結合されていない。これらのブロブの各々は少なくとも一つの画素を含む現在の画素のコンテキストの外側にある他の画素は図示されない。図7Aにおいて、対象となっている現在の画素BC508はTLとTRとの間の8方向に接続可能なブリッジを形成する。結果的に、前のITLID=3およびITRID=5のブロブは併合され、単一のブロブを形成する。該単一のブロブには、二つのブロブのうち、画素数が大きい方のIDが割り当てられる。併合の後、2つのブロブのうち、画素数が小さい方のIDは解放され、将来の再使用のために利用可能なIDのスタックに戻される。残りの併合されたブロブは、次に、対象となっている現在の画素を含めるために更新される。現在の画素のブロブIDIBC508aのエントリーは併合されたブロブIDの番号を割り当てられ、画素数および境界ボックス情報などの様々なブロブフィールドはこれにしたがって更新される。併合されたブロブの全体的な形状およびコンテンツにもとづいて、新しいキーポイント候補がさらに、現在の画素位置にもたらされてもよい。図8A~図8Cは、V形状オブジェクトのサンプルブロブ800についてキーポイントを更新する方法の実施形態を例示する。図8Aは、最初に、ブロブオブジェクトと交差する一番上の走査線で、一見、接続されていない2つのブロブが発見された場合の、相反するタイプ1のキーポイントとタイプ2のキーポイントの2つのセット802a、804aおよび802b、804bの最初の配置を示す。タイプ1のキーポイントとタイプ2のキーポイントとが新しく発見されたブロブの最初の画素にまず割り当てられる。最初の一番上の走査線処理に沿って新しいブロブの画素に遭遇すると、タイプ2のキーポイントの位置804a、804bが順次更新され、図8Aの矢印方向によって示されるように、新しい画素位置の右側に更新される。一番上の走査線の最後までに、タイプ2のキーポイント位置はV形状の各々のアームの画素まで移動する。一方、タイプ1のキーポイント802a、802bは、この例においては、アームの各々の左上コーナーから移動しない。順次走査線処理を実行する間、図8Bに示されるように、下向きの力がタイプ2のキーポイントに加えられる。順次走査線処理の各々について、タイプ2のキーポイントの位置は、各々のアームの右側の境界に沿って下る画素を移動するように、更新される。最終的に、2つのアームが接合する走査線まで到達すると、各アームの2つの開いたブロブが単一のブロブに併合される。幾何学的に鋭角であるため、第一のタイプ2のキーポイント804aは接合画素位置に留まる。一方、第二のタイプ2のキーポイント804bは、下方に移動し続ける。最終的なキーポイントの位置を図8Cに示す。図9は、以下に展開されるように、本発明の微細固有特徴を生成し、記憶するステップを例示する高レベルフローチャート900を示す。フロー900において、レンダリングされているドキュメント画像が入力され902、画像のキーポイント候補が識別される904。キーポイント候補の微細固有特徴が構築される。その後、構築された固有特徴は固有特徴データベース908に記憶される。図10はレンダリングされたドキュメントの例1000で識別されたキーポイント候補の位置を例示する。キーポイント候補の位置は小さな円1002で、オリジナルドキュメントコンテンツ1004に重畳して示される。不明瞭にしないために、少数の円1002だけが示されている。本発明のコンセプトはテキストコンテンツに限定されるものではない。線画、描画、手書きテキストなどのページ上の任意のタイプのマークが追加的な固有特徴に寄与する。図10において、ブロブ文字形状の各々は、少数のキーポイント候補1002をもたらす。単純な直線セグメントおよびドットは2つのキーポイント候補のみを有する。より複雑な文字形状は追加的なキーポイント候補を有する。しかしながら、文字毎のキーポイント候補の数はこの例では6個を越えず、多くの文字形状が6より少ないキーポイント候補しか必要としない。この例において文字の各々は目立つキーポイント構成を有する。キーポイント候補の数は、適切な光学文字認識のために文字形状を示すために必要とする画素の数よりかなり少ない。ここでの目的は視認可能な固有パターンを単に検出することであり、テキスト文字を認識する必要はない。本発明の方法およびシステムの態様は図10によって明白となる。詳細には、キーポイント候補の位置は、文字形状の各々の左上および右下に、集合しようとする。これによれば、平均文字幅、平均文字高さ、ベースライン位置、アセンダー基本活字体より上部に突き出す部分:b,d,h,k、ディセンダーベースラインの下に突き出す部分:j,yなどの他のテキスト属性などのブロブの様々なパラメータを推定するために、本発明の方法によって結果的に得られるキーポイント候補は有用なものとされる。キーポイント候補の位置は、ページのスキューを判断するためにも使用することができる。キーポイント候補の位置は、文字の間隔距離を計測することによって、単語を形成するために、ブロブによって示される文字のグループ分けを判断するためにも効率的に使用することができる。たとえば、実施形態において、ヒストグラムが、最適単語間隔閾値を判断するために、構築される。閉じたブロブの各々の幅は、関連するキーポイント位置の水平方向の広がりにもとづいて推定される。推定されたブロブの幅は、所定のビン数に量子化される。ヒストグラムは、ページ領域において推定された幅が発生する回数もしくは頻度の配列である。ヒストグラムの配列が計算されると、最大頻度文字幅および誤差限界を判断するために統計的な方法が適用され、推定された文字および単語の間隔が計算される。単語間隔より小さい間隔を有する2つのブロブは閉じた双方向リンクによってワードを形成するためにリンクされる。ブロブ発見順序は通常テキストが読まれる順序とは異なるので、双方向リンクを使用することは有用である。たとえば、単語orderのdブロブは、他の文字より垂直方向に突き出しており、上から下へ走査されるので、最初に発見される可能性が高い。閉じた双方向リンクによって、任意の方向で、ブロブを追跡し、水平方向のキーポイントの座標にもとづいて、適切に読まれる方向に発見順序を設定し直すことができる。おおよその西洋の言語は文字の間隔より広い単語の間隔を有しているので、この処理は、同一の単語に属するブロブをグループ化するために働く。一方で、異なる単語に属するブロブは互いに分離されたままとなる。さらに、ページ内の文字高さ、および/もしくは、動的なテキストサイズの変動に合わせて、ヒストグラムを調節することができる。微細固有特徴の様々なタイプを、所望される特徴サイズおよび必要とされる適切さのレベルに応じて、キーポイント候補の位置から計算することができる。本発明の実施形態において、単語サイズの固有特徴が、ドキュメントのコンテンツをマッチングするために使用される。文字レベルもしくは文字の部分レベルなど固有特徴の粒度をさらに微細にすることが可能であり、それらを使用することにより、特殊化された、もしくは、より要求が多い応用に対応することができる。しかしながら、一般的なドキュメント比較については、単語サイズの固有特徴がたいへんよい結果をもたらすようである。本発明の実施形態において、ブロブの右端のタイプ2のキーポイントから次のブロブ通常のテキスト方向であると仮定しての左端のタイプ1のキーポイントまでの距離が計算され、推定される単語間隔閾値と比較される。キーポイント候補距離が単語間隔閾値よりも小さければ、2つのブロブIDが、各ブロブデータ構造で検出された双方向の次のフィールドおよび前のフィールドを用いてリンクされる。たとえば、図10の下部に示される単語innovationsについて検討する。適切な質の走査によれば、接続されている文字の各々がブロブに対応する。ただし、文字iにはドットがあるため余分なブロブを有する。ブロブの各々は前のフィールドおよび次のフィールドを有する。垂直方向の範囲によって、発見される第一のブロブは文字tおよび2つの文字iである可能性が高い。tおよび次のiの間の距離が単語間隔より短いので、tブロブの次のフィールドはiブロブのインデックスにリンクされ、同様に、iブロブの前のフィールドはtブロブのインデックスにリンクされる。他のブロブが発見されると、関連する次のフィールドおよび前のフィールドを挿入し、これに応じて更新することにより、二重にリンクされたリストに追加される。最初および最後にリンクされたブロブが次のフィールドおよび前のフィールドを用いて相互にリンクされ、任意の始点から任意の順序でメンバーブロブを移動し、キーポイントの位置にもとづいて、読まれる順序にブロブのグループの各々を再設定することができるように、循環ループを形成する。リンク処理は次のブロブを単語にグループ化するために働くが、各単語のブロブの内部的な順序は維持される。図11は、図10の左上コーナーの単語領域を拡大したものである1100。キーポイント候補の位置は円1002によって示されている。単語の各々について、関連するキーポイント候補の位置から微細固有特徴が計算される。微細固有特徴を計算するいくつの方法がある。まず、双方向にリンクされているブロブの単語グループの各々のキーポイント候補のすべての中心位置1102を計算する。中心位置は固有特徴位置でもあるとみなされる。次に、キーポイント候補は時計回りの順序でソートされる。ソートは、方向および距離の双方について行われる。原則的なソートの順序は、図11に示されるように時計回りの順序である。図11に示されるサーチをより詳細に例示するために、曲げることができない薄い金属製の定規が使用されているものと想像する。定規は、1106に沿って配置され、始点1102に左端をピン留めされる。一方の端がピン留めされているので、定規は時計回りもしくは反時計回りに回転することしかできない。定規は、所定の角度で始点から放射する光線を示す。硬い定規が時計回りに回転するので、遭遇する第一のポイントは1104であり、他の小さな円のいずれかではない。遭遇する第二の点は文字Cの開口の下側の端点1106の下側でもっとも近いである。遭遇する順序は、角度によって決定され、距離によって決定されるのではない。以下に説明するように、2つ以上の点が同一の角度にある場合のみ、距離によって順序付けがされる。この例における最初のキーポイント候補は1104であり、これは、基準方向1106から最初に遭遇される。同様に、キーポイント候補1108、1110、1112が、この順序で、遭遇される。しかしながら、2つ以上のポイントがほぼ同様の方向にあれば差異が所定の許容レベル以内であれば、ポイントは、同様の方向のポイントのすべてについて距離によっても順序付けされる。中心位置の周囲のキーポイントの順序付けが確立されると、微細固有特徴が中心位置までのキーポイントの距離から計算される。キーポイントの各々について、キーポイントから中心位置までの距離を所定の量子化閾値のセットを使用して量子化することによって、整数値が決定される。量子化閾値はキーポイントの分布を検討することによって経験的に決定される。キーポイント距離の各々の量子化は、この単語の任意の2つのキーポイント間の最大距離および量子化レベルの数に対して正規化される。明瞭な電子的ドキュメントが入力されると、N=2もしくはN=4などの少数の量子化レベルによって良好な結果がもたらされる。量子化距離値は、固有特徴を形成するために連結される。固有特徴は、量子化された距離を示す複数の整数値の基本的に独特な長い列である。したがって、固有特徴は、多次元空間において高次のベクトルとして解釈されることができ、これにより、固有特徴の明白さが次元性によって増加する。ブロブ毎のキーポイントの数は変更可能であり、量子化される距離の数も変更可能であるので図11に示される例では、2~6の間、固有特徴は固定平均固有特徴長さ通常は2のべき乗に揃えられる。キーポイントの通常の密度のセットについて時折現れるより長い固有特徴の列は、最大固有特徴サイズを制限するために選択される、ある大きな数Pのモジュロを用いて短くされる。特定の固有特徴サイズを越えるデータの余分な任意のビットは折り畳まれ、決定された固有特徴のサイズを保証するために、固有特徴列にモジュロ加算が行われる。さらに、異常に長い列の場合、キーポイントのより不明瞭なパターンを除去するために、ある基準が適用されてもよい。図12は図1A~図3Eに示されるソースドキュメントおよび改変ドキュメントを比較するための実施形態を例示する高レベルフローチャート1200を示す。ステップ1202および1204において、ソースドキュメントおよび改変ドキュメントの微細固有特徴が取得されている。ステップ1206において、ステップ1202およびステップ1204からの情報を用いて、比較オペレーションが開始される。比較は、比較されるドキュメントの間の差異を識別するために調べる任意の複数の比較オペレーションであってよい。その後、ステップ1208において、比較結果を示す単一もしくは複数の画像が、出力される。フローチャート1200は複数のドキュメントと単一のドキュメントとの比較を示すために使用されてもよい。この場合、ステップ1202は単一のドキュメントを示し、ステップ1204はドキュメントデータベースを示す。この場合、比較はデータベースをサーチし、ステップ1208の出力はステップ1202の画像とマッチングする複数の画像を含む。実施形態のいくつかにおいて、本発明のシステムおよび方法は、図13に示されるコンピュータネットワークのパラメータ内で、稼働してもよい。この実施形態におけるコンピュータネットワーク1300は一連の配線1302を含み、配線1302の多くは分岐し、もしくは、配線結合点1304において第三の配線1306と結合されており、スタンドアロンの周辺機器と接続され、もしくは、周辺機器を介して他の機器周辺機器とみなされるコンピュータ1308、1309などと接続されている。ネットワークはカラープリンタ1310もしくはカラープリンタではないプリンタ1312、カラーレーザプリンタ1320、1322、もしくは、カラーレーザプリンタではないプリンタ1324を含んでいてもよい。ネットワークはスキャナ1330、ファックス機器1340、コピー機器1350、カラーコピー機器1352、もしくは、カラープリンタ/スキャナ/ファックス機器の複合機1354を含んでもよい。ネットワークはパーソナルコンピュータ、および/もしくは、スタンドアロンコンピュータ端末1360、もしくは、スタンドアロンハードディスクドライブデータ記憶媒体1364を含んでもよい。ネットワークは無線ネットワーク送受信機器1370および少なくとも一台のラップトップコンピュータ1372もしくは複数台のラップトップコンピュータ1374とのインタフェースを含んでもよい。ネットワークは、インターネット、イントラネット、もしくは、他の通信ネットワークを含んでもよいが、これらに限定されない、ネットワーク1380の任意の形態で相互に接続されていてもよい。他の形態のネットワークとのインタフェースを使用することによって、本発明のシステムおよび方法は、デジタルスチルカメラ1391、デジタルビデオカメラ1392、携帯電話1393、スキャナ1394、携帯端末1395、もしくは、ドキュメント索引システム1396を含むが、これらに限定されない、複数の周辺データ取得機器1390とのインタフェースを有してもよい。本発明のコンセプトは、単一の機器を含むネットワークから数千を越える接続されたデバイスを含むネットワークまで、および、上記構成要素の様々な組み合わせを有するネットワークにおいて実装されてもよい。上記構成要素の様々な構成要素は、上記コンセプトの実装に有用であるように任意の複数の既知の構成要素に配置されたメモリ記憶領域を備えていてもよい。記憶領域は、本発明のコンセプトを含むソフトウェアを保持することができるRAM、ROM、フラッシュメモリもしくは他のタイプのメモリであってよい。他のメモリ記憶領域は、任意の複数のデータベースフォーマットで様々なデジタル画像を保持するように構成されていてもよい。コンピュータを含むが、これに限定されない、図13の様々な構成要素は、ロードされるもしくは構成要素によってアクセス可能なソフトウェアからの命令を処理するプロセッサを含んでもよい。プロセッサを有する様々な構成要素は、一つ以上のプロセッサを有していてもよく、これにより、命令の処理を複数のプロセッサに配分することができる。代替的に、単一のプロセッサが命令を配分するように操作されてもよく、これにより、処理は、マルチスレッド環境で実行されることができる。微細視認可能固有特徴にもとづいてドキュメントのコンテンツを比較することができる、電子的ドキュメントコンテンツのための微細視認可能固有特徴を使用した方法およびシステムを上記した。本発明の方法およびシステムはドキュメントコンテンツの二次元視認可能パターンを識別し、二次元視認可能パターンを付与し、他の関連するドキュメントにおける同じコンテンツを迅速かつ適切に識別する。本発明の方法およびシステムは、アプリケーション固有、および/もしくは、複雑で独特な形態のオリジナルドキュメントコンテンツの代わりに、レンダリングされた出力を用いて任意のタイプのドキュメントコンテンツによって稼働する。上記微細視認可能固有特徴方法およびシステムは、個別のテキスト文字を認識する必要性を軽減する。代わりに、近傍局所でキーポイント候補の位置から計算された局所的な微細視認可能固有特徴が使用される。微細視認可能固有特徴は、コンパクトであり、ロバストであり、たいへん独特な特色を示す。これにより、テキスト単語における単一の文字もしくは文字の部分の変更を容易に識別することができる。上記において、本発明の方法はブロブ毎のロバストであり信頼できる少数のキーポイントを自動的に識別するために迅速な単一パスアルゴリズムを適用する。キーポイントの数はレイアウトの複雑さにもとづく。実施形態において、ドキュメントの微細固有特徴は効率的な参照のためにハッシュテーブルのハッシュ値に変換される。ハッシュテーブルへの単一の参照によって、マッチング位置候補のすべてを含むリストを取り出す。代替的に、問い合わせドキュメントの固有特徴情報が、コレクションの中で最適にマッチングするドキュメントを決定するために使用される。固有特徴は、多次元ベクトル空間として解釈されることができる複数の量子化整数値の列からなる高次元の固有特徴であってもよい。実施形態において、固有特徴はハッシュテーブルのハッシュ値に変換され、ハッシュテーブルのエントリーはリンク付けされた固有特徴のレコードのリストを含んでもよい。固有特徴レコードの各々は、少なくとも、特定の固有特徴の識別およびその値を含む。本発明の一態様は、迅速かつ効率的な固有特徴のマッチングを促進するために、独特の手法で、固有特徴情報を構築する方法である。実施形態のいくつかにおいて、整数値の列である固有特徴に索引付けする方法としてファンツリーと呼ばれるツリーベース法が使用されてもよい。一般的なハッシュ技術と異なり、ファンツリーによれば、高次元空間の近傍固有特徴たとえば、一つもしくは少数の数値の変更を除いて同一の数値列であるたいへん近い固有特徴の効率的なサーチを行うことができ、少なくともハッシュテーブルアプローチと同じくらい処理が速い。上記開示は、ドキュメント比較および検索のための方法の多くの問題に対処する。1.電子ドキュメントコンテンツの同様な視認可能パターンを検出する迅速かつ効率的な方法を提供する。微細ドキュメント固有特徴を含むハッシュテーブルを一回だけ参照することにより、マッチング位置候補のすべてのリストを取り出すことができる。2.本発明の方法およびシステムは、光学文字認識OCR、および/もしくは、文字形状マッチングを使用する代わりに、単純なレイアウトマッチングにもとづいている。高い性能および適切さを有するマッチング位置を識別するための二次元視認可能固有特徴の機能を使用し、本発明の方法およびシステムが計算負荷および消費時間を低減し、適切なマッチング結果を達成することができることを示す。3.既存のテキストベース技術と異なり、本発明の微細視認可能固有特徴は機器によって印刷されたテキストだけでなく、たとえば、線画、描画、および、手書きテキストなどを含む、ページ上の任意のタイプのマークを確実に扱うことができる。4.上記微細視認可能固有特徴は従来の文字形状の光学文字認識に比べ、コンパクトであり、効率的に記憶および検出を行うことができる。文字毎に少数のキーポイントだけが使用されるが、本発明の方法は、ページ上の同様の視認可能なパターンを効率よくかつ適切に検出することができ、光学文字認識でよく生じるエラーや形状マッチングのような問題が生じづらい。5.改良された微細視認可能固有特徴方法は、西洋言語の単語内の単一の文字変更もしくは文字の部分の変更を検出することができる。本発明の方法は、単純な手法で、より微細な固有特徴を使用することにより、複数のストロークを含む他の言語をサポートするために自然に拡張することができる。6.本発明の方法は、画像近傍局所におけるキーポイント候補のセットを識別する。画像近傍局所の位置は、区別可能な二次元微細固有特徴を形成するために、特定の手法で結合される。このアプローチは、所定の時間、限定された開いたブロブを維持し、再利用可能なブロブIDスタックを活用することにより、たいへん少量のメモリ容量しか使用しない。閉じることができる任意のブロブを走査線の最後ですぐに出力し、そのメモリコンテンツを開放し、閉じたブロブIDのメモリは、次の再使用のためにリサイクルされる。これにより、本発明の方法は、任意の所定の時間に数百のブロブを越えて記憶されることがない小さなブロブメモリバッファによってドキュメントページの数万のブロブを適切に扱うことができる。7.ブロブ毎のキーポイントの総数を最小化するために、相反する2つのタイプのキーポイントが、実施形態において使用される。1タイプ1:左上方向に進んで探索するキーポイント、2タイプ2:右下方向に進んで検索するキーポイント。現在の画素位置の各々について、既存のキーポイントの位置は、a前の位置に対して更新されてもよく、b新しいキーポイントが割り当てられてもよく、c既存のキーポイントが所定の条件にもとづいて除去されてもよい。追加的なタイプ1もしくはタイプ2のキーポイントは、2つのブロブが併合される場合、もしくは、分離される場合など所定のランレングス符号化の検討にしたがって、導入されてもよい。8.本発明の方法による識別されたキーポイントは、他の様々な応用にも利用することができる。キーポイント位置は平均的な文字の幅および高さを推定するために使用されてもよい。キーポイント位置は、ベースライン位置およびアセンダーおよびディセンダーの範囲などの追加的なテキスト属性を推定するためにも使用することができる。キーポイント位置は、ブロブ間および単語間空間を推定し、ブロブを単語にグループ化するために使用されることもできる。さらに、キーポイント位置はページスキュー、および/もしくは、テキストの方向を推定するために使用することもできる。さらに、ブロブ毎のキーポイントの数は、ブロブオブジェクトの固有の複雑さを確実に示す。これらの特性は、ドキュメント比較および検索を適切に行うために微細視認可能固有特徴を計算する場合に有用である。"