"ドキュメント画像コンテンツを検出する方法であって、ドキュメント画像ページを複数の画像層に分離することと、前記複数の画像層の二次元ビジュアルフィンガープリントを生成することと、前記画像層の前記形成される二次元ビジュアルフィンガープリントを層カテゴリタイプ別にタグ付けしかつ記憶することと、複数のドキュメント画像ページについて、前記ドキュメント画像ページの分離、前記二次元ビジュアルフィンガープリントの生成及び前記二次元ビジュアルフィンガープリントの記憶を反復することと、前記二次元ビジュアルフィンガープリントを用いて画像コンテンツを検出することを含む方法。前記画像コンテンツを検出することは、クエリドキュメント画像ページを複数のクエリ画像層に分離することと、前記複数のクエリ画像層の二次元ビジュアルフィンガープリントを生成することと、層カテゴリタイプ毎に、前記複数のクエリ画像層の前記二次元ビジュアルフィンガープリントを前記複数の画像層の前記二次元ビジュアルフィンガープリントと比較することと、前記複数のドキュメント画像ページ及び前記クエリ画像ページのうちの少なくとも一方のコンテンツを決定することを含む、請求項1に記載の方法。前記ドキュメント画像ページ毎に前記複数の画像層の各々について前記二次元ビジュアルフィンガープリントを生成することは、同じドキュメント画像ページの他の画像層とは独立して達成される、請求項2に記載の方法。前記二次元ビジュアルフィンガープリントは前記複数の画像層のうちの1つに関連づけられるものとしてラベリングされる、請求項2に記載の方法。前記ドキュメントクエリ画像ページの前記複数のクエリ画像層の各々の前記二次元ビジュアルフィンガープリントを生成することは、他のクエリ画像層とは独立して達成される、請求項2に記載の方法。前記決定することは、そのフィンガープリントが前記クエリドキュメント画像ページのフィンガープリントにある程度マッチングするドキュメント画像ページのリストを生成することと、加重された信頼度及びページ類似レベルの少なくとも一方に基づいて、単一のリストを形成するためにマッチングする前記ドキュメント画像ページのリストを合体することと、前記クエリドキュメント画像ページに最も良く一致するドキュメント画像ページを識別することを含み、前記最も良く一致するドキュメント画像ページは、前記複数の画像層に渡って最も大きい全体的な加重フィンガープリント信頼度またはページ類似レベルを有するドキュメント画像ページである、請求項2に記載の方法。前記画像層の各々の重みは、前記全体マッチングにおける画像層の特定のオブジェクトカテゴリの相対的重要さを高める、または下げるように調整される、請求項2に記載の方法。前記比較することは、特定のカレントピクセルにセンタリングされている局所的画像ウィンドウ内の画像のピクセルの画像特性を、色の数及び様相を決定するために、色尺度検出器によって前記局所的ウィンドウにおけるピクセルの色分布を分析することと、第2のコントラスト尺度検出器によって、前記局所的ウィンドウ内のエッジピクセルの正規化されたコントラスト及びエッジの鮮明さを分析することと、第3のきめ尺度検出器によって、前記局所的ウィンドウ内のピクセルの正規化されたきめのレスポンスを分析することによって調べることを含む、請求項2に記載の方法。コンテンツを検出するために画像のピクセルを分類し、前記画像をフィンガープリントしかつ前記画像の前記フィンガープリントを使用する方法であって、局所的画像ウィンドウを画定することと、特定のカレントピクセルにセンタリングされている前記局所的画像ウィンドウ内の画像のピクセルの画像特性を、i色の数及び様相を決定するために、色尺度検出器によって前記局所的ウィンドウにおけるピクセルの色分布を分析することと、ii第2のコントラスト尺度検出器によって、前記局所的ウィンドウ内のエッジピクセルの正規化されたコントラスト及びエッジの鮮明さを分析することと、iii第3のきめ尺度検出器によって、前記局所的ウィンドウ内のピクセルの正規化されたきめのレスポンスを分析すること、によって調べることと、前記検出器から出力されるピクセルを、テキストピクセル、線画ピクセル及び写真画像ピクセルのうちの少なくとも1つとしてラベリングしかつ決定ルックアップテーブルに格納することと、前記ピクセルのコンテンツを、前記ピクセルへ貼付されるラベルに従ってテキスト画像層、線画画像層及び写真画像層のうちの1つまたはそれ以上にコピーすることと、前記テキスト画像層、前記線画画像層及び前記写真画像層の二次元ビジュアルフィンガープリントを形成することであって、前記画像層の各々の前記二次元ビジュアルフィンガープリントを形成することは他の前記画像層とは独立して達成されることと、前記出力層の前記形成された二次元ビジュアルフィンガープリントを格納することと、前記格納された二次元ビジュアルフィンガープリントを比較して、前記格納された二次元ビジュアルフィンガープリントに一致するクエリドキュメント画像ページのコンテンツを決定することを含む方法。前記比較することは、クエリフィンガープリントを前記ドキュメント画像ページのフィンガープリントと比較することを含み、かつ異なるタイプのクエリフィンガープリントは前記ドキュメント画像ページからの同じタイプのフィンガープリントとのみ比較され、前記テキスト、線画及び写真情報を独立した画像層へ分離することにより、結果的に得られるビジュアルフィンガープリントはカテゴリタイプに対して忠実であり続け、かつテキスト、線画及び写真画像を含む異なるオブジェクトタイプの局所的混合を防止する、請求項9に記載の方法。ドキュメント画像コンテンツを検出する方法、また、コンテンツを検出するために画像のピクセルを分類し、前記画像をフィンガープリントしかつ前記画像の前記フィンガープリントを使用する方法を提供することは利点であろう。本開示のプロセスは、ドキュメント画像コンテンツを検出する方法であって、ドキュメント画像ページを複数の画像層に分離することと、前記複数の画像層の二次元ビジュアルフィンガープリントを生成することと、前記画像層の前記形成される二次元ビジュアルフィンガープリントを層カテゴリタイプ別にタグ付けしかつ記憶することと、複数のドキュメント画像ページについて、前記ドキュメント画像ページの分離、前記二次元ビジュアルフィンガープリントの生成及び前記二次元ビジュアルフィンガープリントの記憶を反復することと、前記二次元ビジュアルフィンガープリントを用いて画像コンテンツを検出することを含む方法を含む。また、本開示のプロセスは、コンテンツを検出するために画像のピクセルを分類し、前記画像をフィンガープリントしかつ前記画像の前記フィンガープリントを使用する方法であって、局所的画像ウィンドウを画定することと、特定のカレントピクセルにセンタリングされている前記局所的画像ウィンドウ内の画像のピクセルの画像特性を、i色の数及び様相を決定するために、色尺度検出器によって前記局所的ウィンドウにおけるピクセルの色分布を分析することと、ii第2のコントラスト尺度検出器によって、前記局所的ウィンドウ内のエッジピクセルの正規化されたコントラスト及びエッジの鮮明さを分析することと、iii第3のきめ尺度検出器によって、前記局所的ウィンドウ内のピクセルの正規化されたきめのレスポンスを分析すること、によって調べることと、前記検出器から出力されるピクセルを、テキストピクセル、線画ピクセル及び写真画像ピクセルのうちの少なくとも1つとしてラベリングしかつ決定ルックアップテーブルに格納することと、前記ピクセルのコンテンツを、前記ピクセルへ貼付されるラベルに従ってテキスト画像層、線画画像層及び写真画像層のうちの1つまたはそれ以上にコピーすることと、前記テキスト画像層、前記線画画像層及び前記写真画像層の二次元ビジュアルフィンガープリントを形成することであって、前記画像層の各々の前記二次元ビジュアルフィンガープリントを形成することは他の前記画像層とは独立して達成されることと、前記出力層の前記形成された二次元ビジュアルフィンガープリントを格納することと、前記格納された二次元ビジュアルフィンガープリントを比較して、前記格納された二次元ビジュアルフィンガープリントに一致するクエリドキュメント画像ページのコンテンツを決定することを含む方法を含む。以下、図1のドキュメント画像ページ100等のテキスト102、線画104及び写真106等の混合型オブジェクトを有するリッチコンテンツドキュメント画像ページを含むドキュメントコレクションにおいて類似コンテンツを発見するための、これによりハイブリッド混合コンテンツフィンガープリントの形成が回避される方法及びシステムを開示する。リッチドキュメント画像ページは、そのページ上に2つ以上のデータタイプを有するドキュメントページである。分類器は、テキスト、線画及び写真のオブジェクトタイプ等の特徴を、局所的画像特性に基づいて自動的に分類する。分類器は、画像コンテンツを、オブジェクトのカテゴリタイプに基づいて複数の画像層に分離する。各画像層を独立してフィンガープリントしかつ結果的に生じるビジュアルフィンガープリントをカテゴリタイプ別にタグづけすることによって、ハイブリッド混合コンテンツフィンガープリントの生成は回避される。ビジュアルフィンガープリントの間にドキュメント画像ページコンテンツを1つの画像層へと扁平にする代わりに、本方法及びシステムは、各々が異なるオブジェクトカテゴリに対応する複数の画像層を生成する。例えば、図1において、3つの画像層108、110及び112は3つのオブジェクトカテゴリタイプ、即ちテキスト102、線画104及び写真106に対応している。別々のオブジェクトカテゴリを表す複数の画像層の各層は、個々にフィンガープリントされる。テキスト、線画及び写真のオブジェクト情報を独立した画像層に分離することにより、結果として生じるビジュアルフィンガープリントはカテゴリタイプに忠実であり続け、異なるカテゴリタイプに渡る情報の局所的混合を防止する。各ビジュアルフィンガープリントは、他のカテゴリによって汚染されることなく、対応するカテゴリの純粋な局所的出現を一意に捕捉する。レンダリングエンジンがタイプ別にページオブジェクトにアクセスできれば、これらの実施形態では、カテゴリタイプによって個々の画像ピクセル毎に完全な割当てを取得することが可能である。この一般的事例において、カテゴリタイプへのピクセルの割当ては取得することが知られていない、または困難である場合がある。さらに、レンダリングオペレーションの間は異なるタイプのオブジェクトが互いに配合または混ざり合うことがあり、よって、結果的に得られるカテゴリを決定することは不可能である。図2のドキュメント画像ページ200に示されているように、テキストオブジェクト202は写真オブジェクト204上に置かれて配合されることがある。分類器は、扁平にされた画像を複数の画像層に分離し、かつカテゴリタイプに画像ピクセルを割り当てるために用いられる。このシステム及び方法は、内部表現のフォーマット及び詳細に関わらず、任意のドキュメントタイプに広く適用されることが可能である。分類器は、コンテンツのタイプを特定のオブジェクトタイプ例えば、テキスト、線画または写真コンテンツとして識別しかつラベリングするために、扁平にされた画像層における局所的画像特性を分析する。オブジェクトラベルは、局所的画像特性に基づいて最も適切なものが貼付分類される。分類は、互いに排他的である必要はない。2つのオブジェクトカテゴリラベル例えば、テキスト及び写真間に重大な不確定性が存在する場合、本方法及びシステムは、双方のラベルを宣言し、テキスト及び写真のフィンガープリントを独立して計算しかつ何れかのセットを順次クエリ画像フィンガープリントとマッチングしてもよい。不確定のピクセルエリア210、212が双方の層に提示される場合には、図2の画像層206及び208にオーバーラップ状況が描かれる。これらの不確定性エリアがどのオブジェクトに分類されるべきかに関する最終的決定は、返される結果を加重することによって下される。他のタイプの混合は通常、先にレンダリングされたオブジェクトの上に部分的に透明なオブジェクトを置いてシースルー効果を生じさせる場合等、透明性が包含される場合に発生する。テキスト、線画または写真コンテンツ間の区別は、各オブジェクトタイプの属性を基礎とする。テキストオブジェクトは、高いコントラスト、2色間のはっきりとしたエッジ遷移、前景テキストカラー及び背景フィルカラーによって特徴づけられる。全景または背景の何れかは、透明であってもよい。これに対して、普通の写真画像オブジェクトは、通常、滑らかなカラーグラデーション、多様なコントラスト及びエッジ情報、並びに多様なきめによって特徴づけられる。クリップアート、描画及び会社ロゴ等のコンピュータで生成される線画及びビジネスグラフィックスのオブジェクトは、エッジのコントラスト及び鮮明さが普通の写真画像より高いマルチモードの色分布を有する傾向がある。図3には、入力された画像ピクセルの局所的画像特性を基礎とする分類が示されている。図示されている分類器302は、入力画像300を受け入れる。入力画像をラベリングされた3つの画像層、即ちaテキスト層360、b線画層370及びc写真層380に分離するために、局所的画像ウィンドウ310が設けられ、入力画像300を引き渡される。局所的画像ウィンドウのサイズは、ビジュアルフィンガープリント方法に依存して一定であっても、可変であってもよい。局所的出現を基礎とするフィンガープリントの場合は、一定のウィンドウサイズが使用される。入力画像300の各画像ピクセル毎に、分類器は、特定のカレント入力画像ピクセルにセンタリングされている局所的画像ウィンドウ310内の画像特性を調べる。ウィンドウコンテンツは、3つの独立した検出器によって並行して調べられる。色尺度検出器320は、色の数及び様相を決定するために局所的ウィンドウ内のピクセルの色分布を分析する。狭く集中された2色はテキスト状の特性を示し、3つ以上のはっきりした色の集合は線画特性を示し、かつ色が滑らかに変わる領域は写真画像を示している。コントラスト尺度検出器330は、局所的ウィンドウ内のエッジピクセルの正規化されたコントラスト及びエッジの鮮明さを分析する。エッジピクセルは、輝度の差が所定のしきい値を超える隣接するピクセルとして分類される。しきい値の値は、局所的ウィンドウのコンテンツから動的に計算される。高いコントラスト及び鮮明なエッジはテキスト状の特性を示し、低いピクセル間コントラストは自然な写真画像を示している。きめ尺度検出器340は、局所的ウィンドウ内のピクセルの正規化されたきめのレスポンスを分析する。きめの反応は、局所的ウィンドウ内部の重複する3x3窓位置において見出される特定ピークの数として規定される。但し、ピークは、任意の水平、垂直または対角方向でその直近の8つの近傍ピクセルの何れよりも指定されたしきい値だけ大きい、または小さい、3x3ウィンドウにおける中心ピクセルを指す。このようなピークの数は、局所的ウィンドウにおける周波数に比例する。きめの尺度の値は、印刷で従来行われているように、シミュレートされる色の幻影を生成するために前もってディザリングされている場合もある中間調及び他のオブジェクトを、シアン、マゼンタ、イエロー及びブラック等の原色による小さい部分集合から弁別する際に有用である。3つの検出器320-340の出力は、決定ルックアップテーブル350へ供給される。決定ルックアップテーブルは、検出器の出力を結合し、かつ局所的画像特性に基づいて、各画像ピクセル毎に、これらの出力をテキスト、線画及び/または写真画像として分類する概して1つの、かつ時には2つ以上の区別的な出力ラベルを生成するように構成される。ルックアップテーブルは、内的には、その各々がaテキスト層360、b線画層370及びc写真層380等の出力層の1つに対する特定の画像ピクセルの割当てを制御する3つの独立したテーブルとして構成される。3つのルックアップテーブルの各々について、色尺度320、コントラスト尺度330及びきめ尺度340の様々な検出器出力値に基づいて別々のアドレスが計算される。ピーク二色分布と結合された場合の高いコントラスト値は、テキストコンテンツの存在を示す可能性が高い。対応するテキスト層のテーブルコンテンツは、コントラスト値が所定のしきい値及び2色の周囲の色尺度出力ピークを超えると入力ピクセルをテキスト層出力へ送るようにプログラムされる。様々な検出器出力が互いに連結されてテーブルへのアドレスが形成され、かつ特定の公式及びしきい値が前もって個々のルックアップテーブルコンテンツへとプログラムされる。決定ルックアップテーブル350の出力は、互いに排他的なラベルを有するように限定されても、されなくてもよい。最後に、調査されているピクセル例えば、中央のウィンドウピクセルのコンテンツは、分類器の決定ルックアップテーブル350により出力されるラベルに従って画像層、即ちテキスト層360、線画層370及び/または写真層380のうちの1つまたはそれ以上へコピーされる。画像層360-380は、局所的画像ウィンドウ310を入力画像面積全体をカバーするように入力画像300内で左から右へ、かつ上から下へスライドしかつ各ウィンドウ位置で上述のプロセスを反復することによって形成される。各画像層は独立してフィンガープリントされ、結果的に得られるビジュアルフィンガープリントはその層のカテゴリレベルに対応してタグ付けされる。次に、フィンガープリントは記憶されてインデックスを付けられる。インデックス付けの間、異なるタイプのフィンガープリント例えば、テキストとラベリングされるフィンガープリント、線画とラベリングされるフィンガープリント及び写真とラベリングされるフィンガープリントは独立してハッシュされ、高速かつ効率的なフィンガープリントルックアップ用に編成される。上述のプロセスはドキュメントコレクションの複数の入力ドキュメント画像について反復され、よって、テキストフィンガープリント、線画フィンガープリント及び写真フィンガープリントとして分類されるフィンガープリントのデータベースが格納される。ドキュメントコンテンツの検索またはマッチングの間、分類器300へクエリドキュメント画像ページが提供され、かつドキュメント画像ページの入力画像と同様にして処理される。クエリドキュメント画像ページは、カテゴリタイプ別に複数の画像層に分離され、各層は先に概説した方法と同じ方法でフィンガープリントされる。結果的に得られるクエリ画像フィンガープリントはカテゴリタイプ別にルックアップされ、ドキュメント画像ページのコレクションの一部として格納されている対応するフィンガープリントと比較される。結果として得られるマッチングするドキュメントのリストは合体され、加重された信頼度及び/またはページ類似レベルに基づいて単一のリストが形成される。コレクション内の最良一致ドキュメントは、次には、全カテゴリタイプ例えば、テキスト、線画、写真画像に渡って最大の全体加重フィンガープリント信頼度及び/またはページ類似レベルを有するドキュメントとなる。各カテゴリ例えば、テキスト、線画または写真画像の重みは、全体マッチングにおける特定のオブジェクトカテゴリの相対的重要さを高める、または下げるように調整されてもよい。異なるタイプのクエリフィンガープリントは、そのコレクションにおける同じタイプのフィンガープリントとのみ比較される。本明細書に記述されているシステム及び方法は、図4に示されているようなネットワークを含む、但しこれに限定されない様々な環境内で動作してもよい。ネットワーク400は一連のワイヤ402等の接続部で構成され、ワイヤ402はワイヤ接合部404で第3のワイヤ406と分岐し、スタンドアロン型周辺デバイスに接続してもよく、または周辺機器を通過してコンピュータ408、409等の他のデバイスへ接続してもよい。ネットワークは、カラープリンタ410、カラー以外のプリンタ412、カラーレーザプリンタ420、422またはカラーレーザ以外の1つのプリンタ424を組み込んでもよい。またネットワークは、スキャナ430、ファックス機440、写真複写機450、カラー写真複写機452、カラープリンタ/スキャナ/ファックスの複合機454も組み込んでもよい。またネットワークは、コンピュータ端末460またはスタンドアロン型ハードドライブデータ記憶媒体464も含んでもよい。またネットワークは、無線ネットワーク送受信機470及びラップトップコンピュータ472または複数のラップトップコンピュータ474とのインタフェースも含んでもよい。ネットワークは、インターネット、イントラネットまたは他の通信ネットワークを含む、但しこれらに限定されない任意の形式のネットワーク480と相互接続してもよい。本システム及び方法は、デジタル静止画カメラ491、デジタルビデオカメラ492、携帯電話493、スキャナ494、パーソナルデータアシスタント495またはドキュメントインデクシングシステム496を含む複数の周辺データ捕捉デバイス490とインタフェースしてもよい。本概念は、単一デバイスを有するネットワークから何千もの、またはそれ以上の接続デバイスを含むネットワークに至る、上述のコンポーネントの様々な組合せを有するネットワークにおいて実装されてもよい。さらに、上述のコンポーネントのうちの様々なものは、後述の概念の実装に有用であり得る幾つかの既知の構成のうちの何れにも配置されるメモリ記憶領域を有してもよい。記憶領域は、RAM、ROM、フラッシュメモリ、ウェブサービス、クラウド記憶ファシリティまたは本出願の概念を組み込むソフトウェアを保持できる他のメモリタイプであってもよい。コンピュータ等、但しこれに限定されない図4のコンポーネントのうちの様々なものは、コンピュータ上にロードされたソフトウェア、またはその他コンポーネントによってアクセス可能なソフトウェアからの命令を処理するためのプロセッサを含む。プロセッサを有するコンポーネントのうちの様々なものは2つ以上のプロセッサを有してもよく、よって命令の処理が複数のプロセッサ間で分割され得ることは理解されるべきである。或いは、単一のプロセッサは命令を分けるように動作することができ、よって処理はマルチスレッド環境において発生することが可能である。コンピュータは上述のもの以外の演算デバイスであってもよく、電子/デジタルプロセッサ並びに、または代替的にグラフィカル電子/デジタルプロセッサGPUを含む。a.1ドキュメントキーポイントの検出キーポイント識別の目的は、キーポイントを発見することにある。図5には、フィンガープリントされるべきターゲット画像510のドキュメントキーポイント位置を検出する一プロセス500が示されている。適応しきい値画像処理、ブラーリング及び接続コンポーネントコレクションによる画像処理は文献において周知である。第1の適応しきい値モジュール520のバイナリ出力画像525は、CCサイズ推定モジュール530へ送信される。CCは接続されるコンポーネントの略語であって、同じ極性を有するバイナリピクセルの最大限に接続されたサブグループである。2つのピクセルは、両者間に同じ極性のピクセル経路が存在する場合に限り、同じ接続コンポーネント内に存在する。CCサイズ推定モジュール530の目的は、ターゲット画像510について一画像毎に、放射状ブラーモジュール540において適用されるべきブラーパラメータ535またはブラーフィルタサイズを動的に推定することにある。ブラーリングプロセスは、ロバストで信頼的かつ反復可能なキーポイント識別を提供し、ノイズを除去しかつページ上の小さい隔絶された特徴を排除する。例えば近似ガウス形状である、但しこれに限定されないブラーフィルタの形状は、望ましくないアーチファクトの導入を防止するに足る滑らかなものであるべきである。放射状ブラーモジュール540の出力は、グレースケール画像545である。適応しきい値モジュール550は、グレースケール放射状ブラー540の画像出力545を適応しきい値処理550によってバイナリ白黒出力555に変換する。第2の適応しきい値モジュール550のバイナリ出力はバイナリ画像555であり、接続コンポーネントモジュール560へ転送される。重心計算モジュール570は、接続コンポーネントモジュール560の出力における各接続コンポーネントの視覚的中心を決定する。接続コンポーネントの各々について、その水平重心位置が、接続コンポーネントの各帰属ピクセルの水平座標を合計しかつその結果を帰属ピクセル総数で除算することによって計算される。垂直重心位置も同様に、各帰属ピクセルの垂直座標を合計して帰属ピクセル数で除算することによって計算される。合計は、接続コンポーネントの分析中にオンザフライで効果的に実行されることが可能である。所定の接続コンポーネントのピクセルメンバのみが、その重心位置に寄与し、他の任意の非帰属ピクセルのホールは無視される。各接続コンポーネントの視覚的重心はサブピクセル精度で計算されるが、これは、多くの言語において、接続コンポーネントはテキストラインに定置される傾向があるためである。重心計算モジュール570からの接続コンポーネント重心位置のリスト575は複製除去モジュール580によって認証され、複製除去モジュール580はキーポイントのリスト585を生成する。認証の目的は、2つの接続コンポーネントが所定の許容差レベル内に同じ重心位置を持たないことの保証にある。ほぼ同じ重心位置を有する複製接続コンポーネントは除去される。複製除去モジュール580の出力における残りの接続コンポーネント重心のリストは、最終的なクエリキーポイント候補リスト595となる。キーポイント候補590の全体数は、入力画像のコンテンツ及び接続コンポーネントの処理タイプに依存する。a.2フィンガープリントの構築この項目では、局所的なキーポイントグループからフィンガープリントを計算しかつこれらのフィンガープリントを効率的に格納するためにフィンガープリントルックアップインデックスまたはデータベースに圧縮するプロセスについて説明する。フィンガープリントは、フィンガープリントのルックアップインデックスまたはデータベースのサイズを縮小しかつ格納要件を低減するために圧縮される。我々は、入力画像において、広範なノイズ、視覚条件及び画像歪においても安定しているロバストな2Dビジュアルフィンガープリントを識別することを目指している。フィンガープリントのサイズは、システムが超大型のドキュメントコレクションサイズを処理すべく効率的にスケールアップできるように最小化されることが可能である。フィンガープリントは、所定のキーポイントとその最近のN-1個の近傍キーポイントとの相対的2D位置から導出される、持続的比率と呼ばれる量子化された変換-不変2D比のシーケンスとして構築される。従って、各フィンガープリントは、特定のキーポイント辺りの小さい画像近傍へ局在化される。フィンガープリントシーケンスは、特定のキーポイントとその最近のN-1個の近傍キーポイントとの間の相対的な2Dジオメトリにのみ依存する。近傍キーポイントの数Nは、フィンガープリントの強度に影響する設計パラメータである。本出願は、フィンガープリントをスキュー、捻れ、回転、平行移動、スケール、解像度の変化及びこれらに類似するもの等の画像歪に対してロバストにする。図6Aに示されているように、オブジェクト表面上で三角形ABC650及び第2の三角形ACD660を構成する同一直線上にない4つの点{A,B,C,D}即ち、610,620,630,640から成る任意の所定の多角形600の場合、三角形の面積比ABC/ACD670が任意のアフィン変換下で一定のままであることは技術上周知である。故に、三角形の比670として示されている1つの三角形の面積比の計算に必要な点は、P=4個のみである。このアフィン変換は、多くの実際的状況におけるカメラ対平坦オブジェクトのジオメトリを説明するための容認できるモデルを提供するために示されている。この変換は、2つの三角形比の積である1つの持続的比率を計算するために、4ではなくP=5点を用いて透視変換を処理するように拡張されることが可能である。従って、単一のフィンガープリントは、時計回り順にソートされた最近のN個の近傍キーポイントによるグループに関する量子化された持続的変換比率のシーケンスで構成される。フィンガープリントのサイズを小さく保つために、変換率はQレベル680に量子化される。Qの値は、便宜的に、2進法の2のべき乗であるように選択されることが可能である。図6Bには、Q=8の場合の量子化プロセスが図6Aの三角形の比680の量子化として示されている。量子化前の三角形の比の有効範囲0,∞は、図6B690に示されているように、0から7まででラベリングされたQ=8個の区間に分けられる。区間の境界は、代表的ドキュメントの大集合に渡って量子化ラベルの略均一な分布をもたらすように経験的に決定される。到来する三角形比の値680は、増大する区間境界と順次比較されて第1の高次または等しい区間境界が決定され、この時点でプロセスは終了し、対応するラベル区間が量子化された結果として割り当てられる。例えば、1.0より低くかつ先行する区間境界より高い到来する三角形の比0.8253694には、量子化された値3が割り当てられる。最近近傍法の使用における潜在的問題は、透視変換下では近いことが必ずしも持続されない点にある。任意のアフィン変換または透視変換下では、所定のキーポイントの最近のN個の近傍キーポイントが正確に同じN個のキーポイントであり続けるという保証はない。それでも、最も近いキーポイントは、もっと遠いキーポイントよりも最近のN個の近傍キーポイントのリスト内に留まる傾向が強い。上述の問題を克服するために、本出願は、アフィン変換または透視変換に対するフィンガープリントのロバスト性をさらに高めるべく近傍キーポイントのうちの1つまたはそれ以上が不在であることを許容する。1つのキーポイントは、局在化された小さい近傍においてアフィン歪が限定的であることを考慮して、除外されることが許容される。従って、所定の各キーポイントは、一度に1つのキーポイントを除外することによって幾つかのフィンガープリントNを生み出す。各フィンガープリントは、残りのキーポイント数、N-1個を放射状の方位順で体系的に歩き、かつP個の点の組合せとして可能な全てのものアフィン変換のP=4、透視変換のP=5について量子化された持続的比率のシーケンスを記録することによって生成される。図7には、フィンガープリントのプロセス700が示されている。フィンガープリントプロセス700への入力は、入力画像705に関するキーポイント候補710のリストである。図7におけるフィンガープリントの第1の処理ステップは、キーポイント三角形分割モジュール720である。ドロネーまたはキーポイント三角形分割720は、局所的近傍において所定の各キーポイントに最も近いキーポイントを識別するために使用される。三角形分割のリンクに従えば、所定の任意キーポイントに最も近いN-1個の近傍キーポイントを効果的に決定することができる。各キーポイント候補及びその最も近いN-1個の近傍キーポイントは、フィンガープリント候補として考慮される。現行のキーポイント候補Kpは各々、入力リスト710から次のキーポイント取得モジュール730によって順次選択される。各キーポイントKpについて、最近近傍キーポイント発見モジュール740は、所定のキーポイントKpへの距離が最も近いN-1個の最近キーポイントを識別する。但し、Nは所定の変数である。最近近傍キーポイント発見モジュールは、ドロネーまたはキーポイント三角形分割結果720を用いて、Kpからの距離の増大順にソートされたKpへの最近キーポイントのリストを返す。返されるリストの最初のエレメントは、常に現行キーポイントKp距離ゼロである。変数Nの値は、1フィンガープリント当たりの演算数として定量化されるフィンガープリントの強度または識別力、即ち全体的なシステムパフォーマンスと、結果的に生じるデータベースのサイズまたはフィンガープリントサイズとの間に妥当な得失評価をもたらすように調整される。本例では、値N=8、12または16が使用される。最近近傍キーポイント発見モジュール740の点は、面積比のシーケンスがデータベース画像とクエリ画像との間で同じキーポイント/近傍に対して一貫性があるように、一貫した順序で取り入れられる必要がある。時計回り順ソートモジュール750は、所定のキーポイントに最も近いN個の近傍キーポイントのリストを時計回り方位の増大順にソートする。時計回り順ソートモジュール750は、ほぼ同一直線上にあるキーポイントの一般的事例に対してキーポイントの順序づけを安定させるための方法及びシステムを含む。時計回り順ソートモジュール750は、リスト上の所定のキーポイントに最も近い最初のM個の最近近傍キーポイントを用いてサブグループの原点中心を計算する。但し、M<Nである。最も遠いN-M個のキーポイントは、アフィンまたは透視変換下では原点が安定したままであることを保証するために、サブグループの原点中心の計算には使用されない。時計回り順ソートモジュール750は、キーポイントの順序づけを決定するために、合計N=8の場合はM=5個の最近近傍キーポイントの平均位置を原点中心として使用する。現行の近傍キーポイントクラスタの原点中心を決定した後、時計回り順ソートモジュール750は、キーポイントを時計回り方位の増大順にソートすることに進む。ソートは、方位及び距離の双方に基づいて行われる。順序は、時計回り方位の増大順である。しかしながら、2つ以上の点がほぼ同じ方位を有していて、その差が予め規定された許容差レベル内であれば、これらの点は略類似方位の全ての点について距離の増大順にさらに順序づけされる。N個のキーポイントによる一意の部分集合の各々について、次のサブグループ組合せモジュール760は、アフィン変換または透視変換の場合に依存して、次のサブグループの組合せであるP=4またはP=5個のキーポイントを体系的かつ系統的に選択する。例えば、N=8の場合、P=4のキーポイントサブグループには一意の組合せが70存在する。P=4個のキーポイントの次のサブグループの組合せの各々について、圧縮された量子化比率モジュール770は単一の持続的比率を計算し、かつ予め規定された区間境界しきい値の集合を用いてこれを量子化する。量子化レベルの数Qは、設計パラメータである。これらの例では、Q=8、またはQ=16が使用されている。量子化しきい値は、特定タイプのドキュメントの大型コレクションにおける持続的比率の分布を調査することによって経験的に決定される。フィンガープリントデータベース785のサイズをさらに縮小するために、圧縮量子化比率モジュール770は、結果的に生じる幾つかの量子化された持続的比率を1つの機械語に圧縮する。例えば、N=8、P=4及びQ=8の場合、70のサブグループ組合せの全体的なフィンガープリントシーケンスは3つ以下の64ビットワードに密に圧縮されることが可能である。圧縮されたフィンガープリントのサイズは、合計3つの64ビットワード及び3つの8ビットバイトを占有し、複数のワードまたはバイトに渡って部分的情報を分割する必要はない。フィンガープリントを計算して圧縮するプロセスは、一度に1つの持続的比率で、最終組合せモジュール780によって最後の組合せが検出されるまで順次継続する。現行のPサブグループ組合せがまだ最後の組合せ781でなければ、最終組合せモジュール780は、次のPサブグループを取得しかつその量子化された持続的比率の計算及びその圧縮へと進むためにこの流れを次のサブグループ組合せモジュール760へとルーティングして戻す。このプロセスは、782において最後のPサブグループ組合せが処理されるまで続く。最後のPサブグループ組合せが処理された時点で、結果的に得られる圧縮されたフィンガープリントデータ783はフィンガープリントデータベース785へ書き込まれる。フィンガープリントデータは、圧縮された各フィンガープリントデータが利用可能になるにつれて、フィンガープリントデータベース785へ一度に1つのフィンガープリントについて順次書き込まれることが可能である。フィンガープリントを書き込むプロセスは、残りの全てのキーポイントについて、最終キーポイントモジュール790によって最後のキーポイントが検出されるまで順次継続する。現行のキーポイント組合せがまだ最後のキーポイント791でなければ、最終キーポイントモジュール790は、次のキーポイントを取得しかつプロセスを反復してその圧縮されたフィンガープリントの計算及びフィンガープリントデータベース785へのその追加へと進むためにこの流れを次のキーポイント取得モジュール730へとルーティングして戻す。フィンガープリントプロセス。最後のキーポイントがアドレス指定されていれば、795においてプロセスは終了する。図8A-図8Bには、フィンガープリントの原点中心の計算が示されている。図8Aは、所定の画像例800に関するプロセスを示す。処理画像は、キーポイントまたはワードの重心が円801-802によって識別されて示されている。図中の他の円も、やはりワードの重心である。例えば、数字1-7もまた、点Xに近い近傍キーポイントであるワードの重心を表している。図8Bは、明瞭さを高めるために背景の処理画像を除去しているが、他は図8Aと同じである。この例では、局所的近傍における7つの追加キーポイント1-7を用いてキーポイントXのフィンガープリントが計算される。第1のステップにおいて、このフィンガープリントの原点中心はキーポイントXに最も近いM=5個のキーポイントを用いて、即ち点{X,1,2,3及び5}の平均位置を用いて計算される。これは、原点中心を点Xから離れて、かつキーポイントXを含むテキストラインYに沿ってキーポイントの同一直線上にあるラインから離れて、点0への矢印線820に従って新たな原点中心へと移動させるものと思われる。7個1-7のうちで最も遠い3つのキーポイント4,6,7は、任意のアフィンまたは透視変換によって点3つまではシフトされるものと見込むことによって点0の位置を安定させるために、原点中心の計算には使用されない。第2のステップでは、8個のキーポイントX及び1-7の全体集合が、新たに計算されたサブグループの原点中心0に対して時計回り順810にソートされ、この場合は結果的に、1,X,2,3,4,5,6,7という最終的な出力シーケンス順序が得られる。キーポイントのこの順序づけに注目すれば、上述の順序づけが基準点に依存することは理解されるべきである。基準点として0が使用されれば、1は0からの点線より上にあることから、結果的なシーケンスは234X5671となっていたであろう。本明細書における代替方法は、Xを基準として使用し続けるがキーポイントの質量は0へ移動されるものと見せかけることであり、これにより先に述べたシーケンスがもたらされる。先では、基準として原初のキーポイント位置を保つ一方で、点0はXの回りを移動してキーポイントシーケンス順をひっくり返させ得ることから、後者が使用されていた。しかしながらこれは、どちらの場合も達成される必要があるものはターゲット画像及びクエリ画像の双方で同じシーケンスを反復できることであるという理由により、どちらの方法で行うことも可能である。第2のステップの目的は、距離ではなく時計回り順にソートすることである点に留意されたい。所定のキーポイントについて最近のN個の近傍キーポイントの順序づけが確立されると、フィンガープリントを生成することができる。フィンガープリントは、近傍におけるキーポイントによるサイズP=4の連続する部分集合から、一度に1つまたはそれ以上のキーポイントを除外しかつ除外されないキーポイントで残りのサブグループ組合せのシーケンスを構築することによって形成される。従って、サブグループ組合せの圧縮されたシーケンスからフィンガープリントのグループを効果的に構築することができる。N個のキーポイントによるP個の部分集合は、体系的かつ一貫した方式で考察される。その各々について、本明細書で記述しているように、そのP部分集合の持続的面積比を計算しかつその面積比を整数にマッピングすることによって整数が決定される。所定のキーポイントのフィンガープリントの長さは、このようなP個の部分集合の合計数である。これは、N個のキーポイントから一意のP個のキーポイントを選択するための組合せの数によって決定される。例えば、N=8及びP=4であれば、サブグループ組合せとして可能性のある数は70個の持続的比率である。このうち、各々長さが35サブグループ組合せである8個のフィンガープリントは、例えば一度に1つのキーポイントを除外することによって構築されることが可能である。a.3高速マッチングのためのフィンガープリント情報の作成図7に示されているように、フィンガープリントデータベース785内のフィンガープリントは、メモリサイズ及びロード時間を縮小するために圧縮フォーマットで記憶される。従って、効率的なフィンガープリントマッチングを促進するために、これらは解凍され、かつ図9のフロー900により示されるようにファン木データ構造に従って一意の方法で編成し直される。フィンガープリントデータベースは、最初の画像クエリ時に一度だけ作成すればよいことに留意されたい。未解凍のフィンガープリントシーケンスを含むファン木データ構造はメモリに保持され、かつ続いて任意数の画像クエリにより再使用されることが可能である。圧縮されたフィンガープリントデータベース785図9の910としても示されているの作成方法は、図7で記述した。次に図9では、フィンガープリント情報を迅速に検索できるように、フィンガープリントデータベースからファン木を構築する方法について説明する。フィンガープリントデータベースのエントリが各々、複数のフィンガープリント候補を発生させることは留意される。本プロセスにおいて、キーポイント除外モジュール920は、フィンガープリントキーポイント930のうちの1つまたはそれ以上を除外することによって複数のフィンガープリントキーポイント組合せ候補を選択する。これは、局所的近傍キーポイント間の1つまたは複数の不在キーポイントを見込んでいる。本実装において、キーポイント除外モジュールは1つのキーポイントを除外する。局所的近傍がN個のキーポイントである場合、各キーポイント毎に1つのデータベースエントリが行われることから、これは、各データベースエントリ毎にN個のフィンガープリント、または1つのキーポイント当たりN個のフィンガープリントを発生させる。フィンガープリントシーケンスモジュール950は、各キーポイント毎にN個のフィンガープリント候補のシーケンスを生成する。例えば、N=8のとき、キーポイント除外モジュール920は、第1のキーポイントを除外して残りの7個のキーポイントを選択することにより第1のフィンガープリントを生成させる。この後、キーポイント除外モジュールは第2のキーポイントを除外して第1のキーポイント及び最後の6個のキーポイントを選択し、第2のフィンガープリントを生成する。このプロセスは、除外されるキーポイント全ての組み合わせが実行されるまで続く。この例では、各データベースエントリは8個のフィンガープリント候補を生成し、各々が7個から4個を選ぶ35通りの長さを有する。N=8及びP=4のとき、4個のキーポイントによるサブグループの一意の組合せは8個から4個を選ぶ=70通りある。これが、キーポイント毎の圧縮フォーマットでデータベース910に格納される。次に、1つのキーポイントが不在である場合のフィンガープリントが生成される。しかしながら、どのキーポイントがなくなるかは事前に分からないため、全ての可能性についての準備が行われる。N=8の場合、1つのキーポイントが不在となる可能性は8通り、即ち第1のキーポイント、または第2のキーポイント、または第3のキーポイント、他と、合計8つの場合がある。これらの事例の各々について、異なるフィンガープリントが計算される。この場合の各フィンガープリントは、原初の8個のうちの1つが不在であるために7個のキーポイントのみを基礎とする。従って、この場合、各フィンガープリントの長さは7個から4個を選ぶ=35であり、それが合計8個存在する。これは、各フィンガープリントが0-7の範囲の35個の整数量子化比率のシーケンスから成ることを意味する。8個のフィンガープリントは、ファン木データへ追加される。クエリ時には、8個のキーポイント現行の1つ及び最近の7個が生成され、かつ同じ方法を使用しかつ同様に一度に1つのキーポイントを除外して再度8個のクエリフィンガープリントが計算される。次に、キーポイントとファン木のコンテンツとのマッチングが試行される。マッチングは、最初にマッチングが達成された時点で停止される。クエリ画像から1つのキーポイントが欠けていればどのキーポイントであるかは問題ではない、8個のうちの1つのクエリフィンガープリントは必ず他の7個が存在する状態で1つとのマッチングを有する。どのキーポイントも欠けていなければ8個全てが存在する、最初の肯定的マッチの後にプロセスが停止してチェックを続ける必要がない場合を除いて、7の任意のグループはマッチすることから8個のマッチが存在することになる。しかしながら、同時に2つ以上のキーポイントが欠けていれば、この位置についてはマッチが存在しない。所望されれば、本システムは、より多くの不在キーポイント例えば、8個のうちの2個、他を許容するように方法を拡張することによって、より多くの不在キーポイントを容易に処理することも可能である。フィンガープリントシーケンスモジュール950から出力されるフィンガープリントデータ960は、現行画像のデータベースから検索される一意の画像ID940と共にフィンガープリントレコード980を形成する。フィンガープリントレコード980は、ファン木アドレス指定モジュール970によってアドレス指定される対応するファン木葉ノード位置に格納される。ファン木葉ノード情報は、対応するフィンガープリントデータ構造990内にフィンガープリントレコード980の連結リストとして格納される。ポピュレートは、実数のフィンガープリントに対応する実際のファン木葉ノードのみに行われる。特定の葉ノードに到達する第1のフィンガープリントは、その葉ノードを最初にポピュレートする。同じ葉ノードにおいて期せずして即ち、同じファン木経路を辿って再度2つ以上のフィンガープリントが到着すれば、新しいフィンガープリント情報は、新しいフィンガープリント情報をその葉ノード上の先行する最後のフィンガープリント情報と連結することによって、その同じ葉ノードへ追加される。クエリオペレーションでは、ドキュメントコレクションにおけるページ画像を作成するために使用される上述のプロセスのうちの様々なものが、幾分かの修正を加えて同様に使用可能であることは理解されるべきである。例えば、図5のキーポイント候補識別プロセスは、例えば画像強調を包含するように修正されて、クエリキーポイント候補の識別に同様に使用されることが可能である。さらに、とりわけノーズガード等の結果精度を高めるための追加的な処理オペレーションも利用可能である。さらに、上記ではキーポイントがそこから生成されかつドキュメントクエリが実行されるオブジェクト例えば、とりわけテキスト、線画、写真を分類するためのシステム及び方法について記述しているが、Kletter、Saund、Janssen、Atkinsonらの局在化された二次元ビジュアルフィンガープリントを用いてドキュメントコレクションにおいて文書画像を発見する方法とシステムと題する米国特許出願第12/147,62420080166-US-NP号に記された方法及びシステムに従って、一実施形態において、ドキュメントのフィンガープリントを発見しかつクエリ検索を実行するための代替処理が本出願の概念に従って使用され得ることは理解されるべきである。例えば、Kletterによる局在化された二次元ビジュアルフィンガープリントを用いて画像コレクションにおいてピクチャ画像を発見する方法と題する米国特許出願第12/163,18620080303-US-NP号は、写真オブジェクトを有するドキュメント画像の改良されたフィンガープリントを提供することができかつとりわけ本出願の分類概念を採用し得るシステム及び方法について記述している。具体的には、上記出願は、キーポイント三角形分割図7の720の代わりにアンカキーポイントを使用している。アンカキーポイント識別モジュールが、入力画像において発見されるキーポイント候補の中からキーポイントの強度、スケール、位置及び/または他のキーポイントへの近接性等の様々な基準に基づいて適切なアンカキーポイントの部分集合を選択すれば、次のキーポイント図7の730を取得した後に、プロセスは、最近の近傍キーポイント図7の740を発見するより前に最近のアンカポイントを発見する。別の差異は、時計回り順プロセスでのソートにおいて、時計回り順ソートモジュール例えば、図7の750は、ターゲット画像とクエリ画像との間に量子化面積比の一貫したシーケンスを提供するために、所定のキーポイントのN-1個の最近のアンカキーポイント及び非アンカキーポイントのリストを時計回り方位の増大順にソートすることにある。各フィンガープリントについて、時計回り順ソートモジュールは、現行キーポイント及び最も近いNa個のアンカキーポイントを用いてサブグループの原点中心を計算する。非アンカキーポイントは、非アンカキーポイントが幾つか余分に存在する、または幾つか欠ける場合でも原点が安定したままであることを保証するために、サブグループの原点中心の計算には使用されない。異なるオブジェクトを別個の画像層に分類しかつ分離することにより、次には、そのオブジェクトクラスをフィンガープリントするプロセスのために、特定のオブジェクトタイプにさらに適する特有のフィンガープリント技術が使用される。例えば、写真オブジェクト即ちピクチャを決定するように設計されるフィンガープリントプロセスが写真層におけるマテリアルをフィンガープリントするために使用可能であり、一方で別個のフィンガープリントプロセスがテキスト層におけるオブジェクトのためのフィンガープリントを生成するために使用される。この能力は、フィンガープリントプロセスの精度を高め、さらには図10に示されているもの等のドキュメント検索及びマッチングプロセスの精度を高める。図10のプロセスは、上述の教示に従って分類されたフィンガープリントを使用しているものと理解される。クエリ時には、図10は、特定のクエリ画像1010に対するリアルタイム画像クエリ1000を、特定のクエリ画像1010においてキーポイント位置1020を識別してクエリキーポイントの局所的グループからクエリキーポイント毎にフィンガープリント情報1030を計算し、既存のファン木フィンガープリントデータ1080におけるクエリフィンガープリント1040をルックアップしかつマッチングしてコレクションにおける最良一致のドキュメントまたはドキュメント集合を決定することによって実行することを示している。各クエリフィンガープリントはファン木のアドレス1050を計算するために使用され、ファン木のアドレス1050は、原初のドキュメントコレクションフィンガープリントレコード1085の部分集合を含む特定のファン木葉ノードリストをもたらす。部分集合リストからの原初の各フィンガープリントは、次に、フィンガープリントマッチング1060のために現行クエリと順次比較される。クエリフィンガープリントが検索されたフィンガープリントレコードのうちの1つとマッチングする度に、そのドキュメントのマッチングするフィンガープリントの数の計数が増分される。さらに、フィンガープリントの強度及びそれがターゲットフィンガープリントとどの程度一意に相関するかに基づいて、各フィンガープリントマッチにスコアが割り当てられる。最後に、フィンガープリントスコア分析モジュール1090は、各ドキュメントについて結果的に得られる蓄積されたスコアのリスト及びマッチングするフィンガープリント1070の計数を調べ、そのコレクション内でクエリ画像1010に最も良く一致する最良一致ドキュメントまたはドキュメント集合1095を決定する。マッチングするドキュメント毎の全体スコアは、フィンガープリントマッチの数とその相対スコアを結合することによって計算される。アプリケーションに依存して、フィンガープリントスコア分析モジュール1090は、全体スコアが最も高い1つのドキュメントを選択する場合もあれば、所定の値より高い全体スコアを有する全てのドキュメントを選択する場合もある。マッチングするドキュメント集合は、次に、図4のコンポーネントのうちの1つによって検索されて印刷され、電子送信され、表示されかつ/または記憶されることが可能である。"