(57)【特許請求の範囲】
【請求項１】
複製ドキュメントコンテンツを検出する方法であって、
クエリドキュメントページをドキュメント検出システムへ入力することと、
二次元ビジュアルフィンガープリントの検出プロセスのビジュアルフィンガープリントを用いて、前記クエリドキュメントページをドキュメントコレクションに格納されたドキュメントのページと比較することと、
前記二次元ビジュアルフィンガープリントの検出を用いる結果を基礎として、前記クエリドキュメントページの複製または異なるドキュメントコンテンツと、前記格納されたドキュメントコレクションの少なくとも１つのドキュメントページとを自動的に強調表示することであって、前記自動的に強調表示することは、非対応フィンガープリントの各クラスタに対して、前記クエリドキュメントページの少なくとも１つ及び前記ドキュメントコレクションの返されるドキュメントの前記ドキュメントページのうちの１つの上へ幾何学的エレメントを生成することを含む、前記自動的に強調表示することと、
を含み、
前記方法は、少なくとも電子的プロセッサを用いて実施され、
前記幾何学的エレメントは前記クラスタの平均に中心が置かれ、かつ前記幾何学的エレメントのサイズは、前記クラスタ内のフィンガープリントロケーション分布の推定される二次モーメントに比例する、
方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、ドキュメントコンテンツの検出に関する。
【背景技術】
【０００２】
複製ドキュメントコンテンツを検出する改善された方法への要求が増大している。また、大規模なドキュメントコレクションにおいて複製ドキュメントコンテンツを検出し、前記検出されるドキュメントコンテンツにおいて、複製または相違するドキュメントコンテンツを自動的に強調表示する方法が望まれている。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
何らかの複製されたコンテンツを含む任意のページを自動的に発見し、この複製コンテンツまたはかかる発見された各ページとクエリページ画像との違いを自動的に強調表示することには利点がある。また、通常デジタルカメラまたは携帯電話のカメラで画像を走査、またはその写真を撮るプロセスの間に発生するスキュー、捻れ、回転、平行移動、スケール、解像度の変化及びこれらに類似するもの等、所定の画像歪に対してフィンガープリントをロバストにすることにも利点がある。また、アフィン変換または透視変換に対するフィンガープリントのロバスト性をさらに高めることも利点がある。  
【課題を解決するための手段】
【０００４】
本開示のプロセスは、複製ドキュメントコンテンツを検出する方法であって、クエリドキュメントページをドキュメント検出システムへ入力することと、二次元ビジュアルフィンガープリント検出プロセスのビジュアルフィンガープリントを用いて、前記クエリドキュメントページをドキュメントコレクションに格納されたドキュメントのページと比較することと、前記二次元ビジュアルフィンガープリントの検出を用いる結果を基礎として、前記クエリドキュメントページの複製または異なるドキュメントコンテンツと、前記格納されたドキュメントコレクションの少なくとも１つのドキュメントページとを、自動的に強調表示することを含む方法を提供する。
【０００５】
また、本開示のプロセスには、大規模なドキュメントコレクションにおいて複製ドキュメントコンテンツを検出し、かつ二次元ビジュアルフィンガープリントを用いて前記検出されるドキュメントコンテンツにおいて複製または相違するドキュメントコンテンツを自動的に強調表示する方法であって、ドキュメントコレクションを生成することと、前記ドキュメントコレクションのドキュメントをビジュアルにフィンガープリントすることと、前記ドキュメントコレクションの前記フィンガープリントされたドキュメントにインデックスを付けることと、前記ドキュメントコレクションの前記ドキュメントの前記インデックスを付けられたフィンガープリントをメモリに記憶することと、クエリドキュメントをコンテンツ検出システムへ提示することと、前記クエリドキュメントをフィンガープリントすることと、前記ドキュメントコレクションの前記ドキュメントの前記インデックスを付けられたフィンガープリントを記憶する前記メモリにおいて、前記クエリドキュメントの前記フィンガープリントを調べることと、前記ドキュメントコレクションにおける、前記クエリドキュメントの前記フィンガープリントにマッチングするフィンガープリントを有するドキュメントのリストを返すことと、前記ドキュメントコレクションにおける前記クエリドキュメントにマッチングするフィンガープリントを有する各ドキュメントについて、フィンガープリント比較を実行することであって、前記比較は、前記フィンガープリントのロケーションと、比較されている前記ドキュメントにおけるその対応する配置とを比較することを含むことと、前記クエリドキュメントと前記ドキュメントコレクションの前記ドキュメントのうちの１つとの間の複製または非複製ドキュメントコレクションの一方を自動的に強調表示することを含む方法を提供する。
【図面の簡単な説明】
【０００６】
【図１】複製コンテンツの検出及び違いの強調表示の例を示す。
【図２】複製コンテンツの検出及び違いの強調表示の例を示す。
【図３】走査されるオリジナルページを示す。
【図４】修正された図３を示す。
【図５】フィンガープリントのロケーションを示す。
【図６】フィンガープリントのロケーションを示す。
【図７】フィンガープリントの比較分析の結果を示す。
【図８】フィンガープリントの比較分析の結果を示す。
【図９】ある環境を提示する。
【図１０】ある方法を示す。
【図１１】ある方法を示す。
【図１２】ある方法を示す。
【図１３】ある方法である。
【図１４Ａ】三角形の比の取得方法を示す。
【図１４Ｂ】三角形の比の量子化である。
【図１５】ある方法である。
【図１６Ａ】ある方法を示す。
【図１６Ｂ】ある方法を示す。
【図１７】ある方法である。
【発明を実施するための形態】
【０００７】
図１及び図２は、二次元（２Ｄ）ビジュアルフィンガープリント及び強調表示の方法を示している。各ドキュメントページ１００及び２００のビジュアルフィンガープリントが抽出され、これらのフィンガープリントは複製ドキュメントコンテンツを識別するために比較される。アフィンまたは透視不変フィンガープリントを用いることにより、同一コンテンツの対応するドキュメントエリアは、ページの方向性及びスケールに関わらず、マッチングビジュアルフィンガープリントを生み出す。オリジナルページと修正ページとの違いは、強調表示される。
【０００８】
従って調査者は、相違する主要なエリアに迅速に注目することができる（長円形１２０、２１０、２２０で強調表示されている）。
【０００９】
図３は、走査されるオリジナルページ３００を示している。図４は、走査される修正ページ４００のクエリ画像を示している。クエリページ画像４００は、意図的に加えられた（例えば、タイムスタンプ及びドキュメント識別子）、並びにコンテンツ変更修正（例えば、名前の変更及びファックスヘッダ）テキスト注釈を含む。
【００１０】
本出願は、コレクションにおける、クエリページ画像４００の何らかの複製されたコンテンツを含む任意のページを自動的に発見し、この複製コンテンツを、またはこのような発見された各ページとクエリページ画像との違いを自動的に強調表示する。
【００１１】
２Ｄビジュアルフィンガープリント技術は、上記をアドレス指定するために用いられる。まず、ドキュメントコレクション内のページは、ビジュアルフィンガープリントを抽出してフィンガープリントインデックスを構築するように処理される。コレクションへのインデックス付けは一度行われるだけでよく、これは、事前に行われることが可能である。
【００１２】
図５は、図３における走査オリジナルページに関して発見されたフィンガープリントロケーションがそのページの走査オリジナルコンテンツ上にスーパーインポーズされた画像５００を示している。フィンガープリントロケーションはノードの円５０２（１つのサンプリングしか付番されていない）として示され、線分５０４（１つのサンプリングしか付番されていない）のグリッドメッシュはフィンガープリントロケーションを繋いでいる。
【００１３】
クエリページ画像は、類似方法で処理される。図６は、図４におけるクエリ画像に関して発見されたフィンガープリントロケーションを伴った画像６００を示している。フィンガープリントロケーションはノードの円６０２（１つのサンプリングしか付番されていない）として示され、線分６０４（１つのサンプリングしか付番されていない）のグリッドメッシュはフィンガープリントロケーションを繋いでいる。
【００１４】
図６におけるクエリ画像のグリッドメッシュ構造を図５における走査オリジナルのグリッドメッシュ構造と比較すると、共通する部分及び異なる部分を識別することができる。
【００１５】
クエリページ画像のフィンガープリントはドキュメントコレクションのフィンガープリントインデックスにおいて、そのコレクションにおける、所定数の類似するフィンガープリントを有する全ページを検索するために調べられる。
【００１６】
マッチングするページはマッチングするフィンガープリントの数を基礎として類似性レベルによって等級を付けられ、降順でソートされる。結果として得られるページは、クエリ画像に対する等級付けされた類似性の順序でユーザへ提示される。
【００１７】
返された各ページに対しては、クエリ画像のフィンガープリントとのフィンガープリント一致関係を決定するためにフィンガープリントの比較分析が実行される。分析は、一意の（非一致）フィンガープリントのクラスタを識別し、各クラスタについて、クラスタの分布及びクラスタの内部またはクラスタに極く近接して発生する一致するフィンガープリントの数、クラスタフィンガープリントの密度、他等の他の要素に比例する２Ｄビジュアル測度（例えば、長円）を計算する。
【００１８】
結果的に生じる長円集合は、クエリページ画像に対する違いのエリアを自動的に強調表示するために、ビジュアル画像ディスプレイ上へ追加またはスーパーインポーズされる。
【００１９】
図７及び図８は、図４におけるクエリページ画像と図３における走査オリジナルページとのフィンガープリント比較分析の結果を示す。図７は、長円７０２、７０４で囲まれた２つの非一致フィンガープリントクラスタで増強された、図３におけるドキュメントページを示している。これらのクラスタは、走査オリジナルページにおける、クエリ画像と共通していないエリアを表す。右下の角におけるクラスタを囲む長円７０４のコンテンツは、「ＵＳＷ  ２１５９」と記されたドキュメント識別ラベルであり、これはオリジナルドキュメントの一部ではないと理解されることに留意されたい。各ドキュメントには、走査プロセスの一部として一意のラベルがスタンピングされる。この事例における点線は、一意の識別スタンプを示している。
【００２０】
図８は、図４におけるクエリ画像のフィンガープリント比較分析の結果８００を、長円８０２、８０４、８０６によって強調表示された図３におけるドキュメントページとの違いと共に示している。図８の上側における２つの実線長円８０２、８０４は、オリジナルドキュメントのコンテンツに対する変化、即ちタイムスタンプ及びテキスト修正の各注釈を強調表示している。図８の右下における点線の長円８０６は、走査プロセスの一部として追加された一意の識別スタンプを示している。図７及び図８には円及びグリッド線が示されているが、実際にはこれらは示されなくてもよく、よって、出力された比較は図１及び図２に示されているもののように見えると思われる。
【００２１】
図４は、図３に示されているオリジナルページの走査／ファックスされたコピーの一例を示しているが、図４の走査／ファックスされた画像は、回転された修正済みのファックスページである。
【００２２】
本明細書に記述されているシステム及び方法は、図９に示されているような環境またはネットワークにおいて動作してもよい。ネットワーク９００は一連のワイヤ９０２等の接続部で構成され、ワイヤ９０２はワイヤ接合部９０４で第３のワイヤ９０６と分岐し、スタンドアロン型周辺デバイスに接続してもよく、または周辺機器を通過してコンピュータ９０８、９０９等の他のデバイスへ接続してもよい。ネットワークは、カラープリンタ９１０またはカラー以外のプリンタ９１２、カラーレーザプリンタ９２０、９２２またはカラーレーザ以外の１つのプリンタ９２４を組み込んでもよい。またネットワークは、スキャナ９３０、ファックス機９４０、写真複写機９５０、カラー写真複写機９５２、カラープリンタ／スキャナ／ファックス機のコンビネーション９５４も組み込んでもよい。またネットワークは、コンピュータ端末９６０またはスタンドアロン型ハードドライブデータ記憶媒体９６４も含んでもよい。またネットワークは、無線ネットワーク送受信機９７０及びラップトップコンピュータ９７２または複数のラップトップコンピュータ９７４とのインタフェースも含んでもよい。ネットワークは、インターネット、イントラネットまたは他の通信ネットワークを含む、但しこれらに限定されない任意の形式のネットワーク９８０と接続してもよい。本システム及び方法は、デジタル静止画カメラ９９１、デジタルビデオカメラ９９２、携帯電話９９３、スキャナ９９４、パーソナルデータアシスタント９９５またはドキュメントインデクシングシステム９９６を含む複数の周辺データ捕捉デバイス９９０とインタフェースしてもよい。本概念は、単一デバイスを有するネットワークから何千もの、またはそれ以上の接続デバイスを含むネットワークに至る、上述のコンポーネントの様々な組合せを有するネットワークにおいて実装されてもよい。さらに、上述のコンポーネントのうちの様々なものは、記述される概念の実装に有用であり得る幾つかの既知の構成のうちの何れにも配置されるメモリ記憶領域を有してもよい。記憶領域は、ＲＡＭ、ＲＯＭ、フラッシュメモリ、ウェブサービス、クラウド記憶ファシリティまたは本出願の概念を組み込むソフトウェアを保持できる他のメモリタイプであってもよい。コンピュータ等、但しこれに限定されない図９のコンポーネントのうちの様々なものは、コンポーネント上にロードされたソフトウェア、またはその他コンポーネントによってアクセス可能なソフトウェアからの命令を処理するためのプロセッサを含む。プロセッサを有するコンポーネントのうちの様々なものは２つ以上のプロセッサを有してもよく、よって命令の処理が複数のプロセッサ間で分割され得ることは理解されるべきである。或いは、単一のプロセッサは命令を分けるように動作することができ、よって処理はマルチスレッド環境において発生することが可能である。コンピュータは上述のもの以外の演算デバイスであってもよく、電子／デジタルプロセッサ並びに、または代替的にグラフィカル電子／デジタルプロセッサ（ＧＰＵ）を含む。
【００２３】
図１０は、大規模なドキュメントコレクションにおける複製ドキュメントコンテンツを検出し、かつ２Ｄビジュアルフィンガープリントを用いて複製／相違ドキュメントコンテンツを自動的に強調表示する方法１０００を示している。まず、ドキュメントコレクション１００２にインデックスが付され、フィンガープリントの高速かつ効率的ルックアップ１００４に合わせた特別な方法（ファン木の使用等）で編成される。このコンテキストにおけるドキュメントコレクションは、１つのロケーションに物理的に位置決めされても、多くのフォルダ、ドライブ、システム、ネットワーク、リモートサーバ、ウェブサービス及び／またはクラウド記憶ファシリティ、他に及ぶサブコレクションの集合において物理的に分散されてもよい抽象論理的なドキュメントコレクションである。
【００２４】
ビジュアルフィンガープリント及びインデクシングプロセス１００４は、コレクション内のドキュメントのページへ適用される。各画像のフィンガープリント及びそのロケーションは、メモリ内に見出されるフィンガープリントルックアップインデックス１００６へ追加される。
【００２５】
フィンガープリントルックアップインデックス１００６は、所定の１つのドキュメントコレクションについて一度完全に構築されるだけでよい。このようにしてコレクションにインデックスが付されれば、このフィンガープリントインデックスは保存されて再使用されることが可能である。フィンガープリントインデックスは、ドキュメントがコレクションに追加されると、またはコレクションから除去されると、インデックスへ新しいドキュメントのフィンガープリントを追加すること、及び削除されるドキュメントの既存のフィンガープリントを除去することによって増分的に更新されることが可能である。増分更新は、別個のスレッドにおけるバックグラウンドプロセスとして適用されてもよい。
【００２６】
複製ドキュメントコンテンツの検出方法は、クエリページ画像１００８によって提示される。クエリページ画像はフィンガープリントされ、これらのフィンガープリントは１０１０においてフィンガープリントルックアップインデックス内で調べられ、コレクションドキュメントのリスト及びクエリページ画像フィンガープリントに一致するマッチングフィンガープリントの数が返される。返されたコレクションドキュメントのリストは、対応するフィンガープリントの数によって（例えば、最大から最小へ）順序づけされる。必要最小限の対応するフィンガープリントより上のマッチングするトップページのみが保持されてもよい。
【００２７】
コレクション内の各マッチングページについて、メモリから一致するフィンガープリントが検索され、クエリフィンガープリント１０１２と比較される。このフィンガープリント比較分析は、クエリページ画像とマッチングドキュメントとの間のフィンガープリントの一致関係を決定するために実行される。分析は、フィンガープリントのロケーション及び対応するその配置を考慮する。一致する同一フィンガープリントの集合はマッチングするドキュメントコンテンツの領域を表し、一方で双方の画像における一意の（非一致）フィンガープリントのクラスタはドキュメントコンテンツの違いを表す。プロセスが採用されているアプリケーションに依存して、複製または非複製ドキュメントコンテンツの何れかが自動的に強調表示されてもよい。複製及び略複製コンテンツを検出するアプリケーションでは、複製コンテンツ（どの場合も２画像間で同一である）ではなく、コンテンツの違いを強調表示することが望ましい場合が多い。
【００２８】
違いを自動的に強調表示する一方法は、クエリ及びマッチング画像コレクションドキュメントの一意の（非一致）フィンガープリントの各クラスタの２Ｄロケーションに関する平均及び標準偏差を計算することである。非一致フィンガープリントの各クラスタについて、長円が計算される。長円のロケーションはクラスタ平均に中心が置かれ、かつ長円のサイズは、クラスタ内のフィンガープリントロケーション分布の推定される二次モーメントに比例する。さらに、長円のサイズは、クラスタ内部またはクラスタに極く近接して発生する任意の一致するフィンガープリントの数及びロケーションに比例して、かつクラスタの複雑さ、形状及びフィンガープリント密度によってさらに制御されてもよい。結果的に生じる長円はビジュアル画像ディスプレイの上に強調色で描かれ、またはスーパーインポーズされ、もしくは別個の画像層またはメタデータに保存される。
【００２９】
図１１は、フィンガープリントルックアップインデックス１００６（図１０参照）を生成するためにドキュメントコレクションのインデクシングの追加的詳細を提供するインデクシング方法１１００を示す。インデクシング方法１１００は、ページ画像シーケンスを処理することと、ビジュアルフィンガープリントを計算することと、フィンガープリント及びそのロケーションを指定された画像フィンガープリントルックアップインデックスへ追加することから構成される。
【００３０】
本実施形態において、プロセス１１００は、走査されるハードコピードキュメント１１０２及び／または電子的生成ドキュメント１１０４を含むドキュメントコレクションに関連して使用されるように示されている。異なるドキュメントタイプは、異なる前処理を必要とする。走査されるハードコピードキュメントは、例えばファックスまたはスキャナのノイズ、ページのスキュー及び画像のダークバックグラウンド等の理想的とは言えない状態を含み得る走査されるページ画像から成る。画像処理ステージ１１０６は、フィンガープリントに先行して画像を修復しかつさらに増強するために含まれてもよい。これに対して、例えばＭｉｃｒｏｓｏｆｔ  Ｗｏｒｄ、Ｅｘｃｅｌ、ＰｏｗｅｒＰｏｉｎｔまたはＡｄｏｂｅ  ＰＤＦ等の電子ドキュメント１１０４は、１１０８において、フィンガープリント用のページ画像シーケンスを生成すべくコンテンツを描くことによってレンダリングされる。
【００３１】
インデクシング方法１１００は、コレクション内のドキュメントからのページ画像１１１０を処理する。ドキュメントをインデクシングする順序は、重大ではない。コレクション内の各ドキュメントについて、システムは、ドキュメントのタイプ、即ち走査されるハードコピーまたは電子ドキュメントがオリジナルであるかどうかを自動的に決定し、かつ適切な処理１１０６または１１０８を各々自動的に適用する。
【００３２】
キーポイント識別１１１２は、各ページ画像における安定しかつ反復可能なキーポイントの識別を担当する。ドキュメントまたは写真ページ画像においてキーポイントを発見する先に開発された方法が、展開されている。ある実施形態は、Ｋｌｅｔｔｅｒ、他の「局在化された二次元ビジュアルフィンガープリントを用いてドキュメントコレクションにおけるドキュメント画像を発見する方法及びシステム」と題する米国特許出願第１２／１４７，６２４号に記述されているワードブロブのセントロイドを基礎としている。
【００３３】
別の実施形態は、Ｋｌｅｔｔｅｒによる「局在化されたスケール空間特性を用いて写真画像における安定したキーポイントを発見するシステム及び方法」と題する米国特許出願第１２／１４７，８６７号に詳述されている。
【００３４】
アプリケーションに依存して、所定の強度しきい値測度より下で発見されるより弱いキーポイントは放棄されてもよい。
【００３５】
１１１４では、結果的に得られたキーポイントから２Ｄビジュアルフィンガープリントが計算される。画像キーポイントからビジュアルフィンガープリントを計算する先に開発された方法が、ジオメトリまたは画像外観を基礎として展開されている。ある実施形態では、ジオメトリを基礎としてドキュメント画像の２Ｄビジュアルフィンガープリントを計算する方法が、Ｋｌｅｔｔｅｒ、他の「局在化された二次元ビジュアルフィンガープリントを用いてドキュメントコレクションにおけるドキュメント画像を発見する方法及びシステム」と題する２００８０１６６−ＵＳ−ＮＰに記述されている。
【００３６】
１１１６では、結果的に得られたフィンガープリント及びそのロケーションが画像コレクションのフィンガープリントインデックス１００６へ追加される。画像のフィンガープリントはインデックスへ追加され、高速かつ効率的なルックアップ（例えば、ファン木の使用等による）を促進するために特別な方法でハッシュされる。ある実施形態では、高速ルックアップ用にメモリ内のフィンガープリントを編成する効率的な一方法がＫｌｅｔｔｅｒ、他の「局在化された二次元ビジュアルフィンガープリントを用いてドキュメントコレクションにおけるドキュメント画像を発見する方法及びシステム」と題する米国特許出願第１２／１４７，６２４号に記述されている。
【００３７】
Ｋｌｅｔｔｅｒによる「局在化された二次元ビジュアルフィンガープリントを用いて画像コレクションにおいて写真画像を発見するシステムと方法」と題する米国特許出願第１２／１６３，１８６号には、画像コレクションにおいて写真画像を発見するための別の実施形態が記述されている
【００３８】
コレクション内の各ドキュメントの各ページに対するプロセス１１００は、最後のページ画像１１１８に出合うまで反復される。出合った時点で、結果的に得られたフィンガープリントルックアップインデックス１００６（図１０も参照）は保存され、かつ再使用されてもよい。フィンガープリントルックアップインデックス１００６は、先に段落[００２１]において概説したように、追加のページがコレクションに加えられると、またはコレクションから除去されると増分的に更新されることが可能である。
【００３９】
図１２は、クエリ画像を使用する２Ｄビジュアルフィンガープリントを用いて複製ドキュメントコンテンツを検出し、コンテンツの違いを自動的に強調表示しかつページの類似性レベル毎にページへ等級を付けるクエリ処理／方法１２００を示している。
【００４０】
クエリ処理１２００は、入力にクエリのページが提示されることによって始まる。先に述べたように、本明細書に記述されているシステムは、走査されるドキュメント１２０２及び電子ドキュメント１２０４を含む、但しこれに限定されない様々なドキュメントタイプによって動作する。クエリページ自体は、走査されるハードコピードキュメント１２０２のページであっても、電子ドキュメント１２０４のページ画像であってもよい。システムは、先に概説したように、ドキュメントのタイプ、即ち走査されるハードコピーまたは電子ドキュメントがオリジナルであるかどうかを（例えば、添付の情報ファイルを読むことによって）自動的に決定し、かつ適切な処理１２０６、１２０８を各々自動的に適用する。システムは、フィンガープリントに先立って改善されたクエリ画像１２１０を生成するために、画像処理を適用して劣化した走査用ハードコピークエリページ１２０２を清浄化しかつ増強してもよい。或いは、システムは、Ｍｉｃｒｏｓｏｆｔ  Ｗｏｒｄ、ＰｏｗｅｒＰｏｉｎｔまたはＰＤＦドキュメントページの電子クエリページをクエリ画像１２１０にレンダリングしてもよい。このとき、処理は、ドキュメントコレクションのページ画像ではなくクエリページ画像の画像に対して行われている。
【００４１】
クエリページ画像には、インデクシングの間に用いられる、１２１２においてキーポイントを識別しかつ１２１４において２Ｄビジュアルフィンガープリントを計算する方法と同じ方法が適用される。結果として得られるフィンガープリントは、１２１６においてコレクションのフィンガープリントルックアップインデックス１００６におけるクエリとして調べられ、ドキュメントコレクションから、クエリページ画像フィンガープリントへマッチングする一致フィンガープリントを有するマッチングページのリスト１２１８が返される。リストは、マッチングする一致フィンガープリントの数、即ちマッチランクによって順序づけされる。
【００４２】
次にプロセスは、１２２０において、リストからのページの１つをマッチングページ１２２２として識別する（次ページ画像を得る）。マッチングページ１２２２の一致フィンガープリントが、メモリインデックス１００６から検索される。次に、１２２６において、マッチングページ１２２２のフィンガープリントとクエリページ画像のフィンガープリント配置１２２４とがフィンガープリント比較分析を受ける。このフィンガープリント比較分析は、クエリページ画像とこのマッチングドキュメントページとの間のフィンガープリントの一致関係を決定するために実行される。分析は、フィンガープリントのロケーションと対応する配置とを比較し、クエリ及びマッチングドキュメント画像における一意の（非一致）フィンガープリントのクラスタを識別する。分析は、マッチングするフィンガープリントロケーションを基礎として、マッチングドキュメントページのクエリページ画像との類似性レベルを計算する。
【００４３】
１２２８では、コンテンツの違いが強調表示される。例えば、各クラスタについて長円が計算される。但し、長円のサイズは、クラスタ内のフィンガープリントロケーションの推定される二次モーメントに比例する。長円のサイズはさらに、クラスタ内部またはクラスタに極く近接して発生する一致フィンガープリントの数及びロケーションに比例して、かつクラスタの複雑さ、形状及びフィンガープリント密度によって調整されてもよい。
【００４４】
返された全ページに対する長円はビジュアル画像ディスプレイの上に強調色で追加またはスーパーインポーズされ、もしくは別個の画像層または注釈付きメタデータに保存される。
【００４５】
フィンガープリント比較分析によって計算された、クエリ画像との指定されたページ類似性レベルに適合する、またはこれを超過する返されたページは各々、一致ドキュメントのリストへ追加される。
【００４６】
プロセスは、１２３０において、その時点のページ画像がマッチングページのリストの最後のページであるかどうかをチェックする。最後のページでなければ、プロセスは１２２０においてリストから次のページ画像を取得し、最後のマッチングするページ画像に遭遇するまでコレクション内の返されたページの各々について処理を反復し、１２３２において完了する。この時点で、マッチングする一致ドキュメントのリストは、複製度が最も高いコンテンツを有するページがまず返されるように、ページ類似性レベルによって等級をつけられる。
【００４７】
最後に、ユーザは一致ドキュメントのリストにざっと目を通すことができる。
【００４８】
以下、キーポイントの識別、フィンガープリントの生成及びファン木の構築に関する上述の論考を、図１３−図１７に関連して拡大する。
ａ．１  ドキュメントのキーポイントの検出
【００４９】
キーポイント識別（例えば、図１１の１１１２及び図１２の１２１２）の目的は、ノイズ、光景照明変動及びスキュー、捻れ、回転、平行移動、スケール、解像度変化及びこれらに類似するもの等のアフィン変換のうちの、但しこれらに限定されない少なくとも１つによって劣化された画像バージョンにおいても、できるだけ多くのキーポイントを発見することにある。
【００５０】
図１３には、フィンガープリントされるべきターゲット画像１３１０のドキュメントキーポイントロケーションを検出する一プロセス１３００が示されている。
【００５１】
第１の適応しきい値モジュール１３２０のバイナリ出力画像１３２５は、ＣＣサイズ推定モジュール１３３０へ送信される。この場合、ＣＣという用語は「接続されるコンポーネント」の略語であって、同じ極性を有するバイナリピクセルの最大限に接続されたサブグループである。２つのピクセルは、両者間に同じ極性のピクセル経路が存在する場合に限り、同じ接続コンポーネント内に存在する。ＣＣサイズ推定モジュール１３３０の目的は、ターゲット画像１３１０について一画像毎に、後続の放射状ブラーモジュール１３４０において適用されるべきブラーパラメータ１３３５またはブラーフィルタサイズを動的に推定することにある。ブラーリングプロセスの目的は、ロバストで高信頼的かつ反復可能なキーポイント識別を提供することにある。またブラーリングは、ごま塩ノイズ等のノイズを除去しかつページ上の小さい隔絶された特徴を排除することに役立つ。例えば近似ガウス形状である、但しこれに限定されないブラーフィルタの形状は、望ましくないアーチファクトの導入を防止するに足る滑らかなものであるべきである。
【００５２】
放射状ブラーモジュール１３４０の出力は、グレースケール画像１３４５である。適応しきい値モジュール１３５０は、グレースケール放射状ブラー１３４０の画像出力１３４５を適応しきい値化１３５０によってバイナリ白黒出力１３５５に変換する。
【００５３】
第２の適応しきい値モジュール１３５０のバイナリ出力は２値画像１３５５であり、接続コンポーネントモジュール１３６０へ転送される。接続コンポーネント法は技術上周知であり、グラフの最大限に接続されたコンポーネントの集合について考察し得る。
【００５４】
重心計算モジュール１３７０は、接続コンポーネントモジュール１３６０の出力における各接続コンポーネントの視覚的中心を決定する。接続コンポーネントの各々について、その水平重心位置が、接続コンポーネントの各帰属ピクセルの水平座標を合計しかつその結果を帰属ピクセル総数で除算することによって計算される。垂直重心位置も同様に、各帰属ピクセルの垂直座標を合計して帰属ピクセル数で除算することによって計算される。合計は、接続コンポーネントの分析中にオンザフライで効果的に実行されることが可能である。所定の接続コンポーネントのピクセルメンバのみが、その重心位置に寄与し、他の任意の非帰属ピクセルの「ホール」は無視されることに留意されたい。各接続コンポーネントの視覚的重心はサブピクセル精度で計算されるが、これは、多くの言語において、接続コンポーネントはテキストラインに定置される傾向があるためである。
【００５５】
キーポイント識別段階の最後の処理ステップでは、重心計算モジュール１３７０からの接続コンポーネント重心位置１３７５のリストが複製除去モジュール１３８０によって認証され、複製除去モジュール１３８０はキーポイント１３８５のリストを生成する。認証の目的は、２つの接続コンポーネントが所定の許容差レベル内に同じ重心位置を持たないことの保証にある。ほぼ同じ重心位置を有する複製接続コンポーネントは除去される。
【００５６】
複製除去モジュール１３８０の出力における残りの接続コンポーネント重心のリストは、最終的なクエリキーポイントリスト候補１３９５となる。キーポイント候補１３９０の全体数は、入力画像のコンテンツ及び接続コンポーネントの処理タイプに依存する。ある典型的な機械印刷ページには、数百個のキーポイントが存在し得る。
ａ．２  フィンガープリントの構成
【００５７】
次に、局在的なキーポイントグループからフィンガープリントを計算しかつこれらのフィンガープリントを圧縮してフィンガープリントルックアップインデックスまたはデータベース（例えば、図１０、図１１、図１２の１００６）に効率的に記憶するプロセスについて説明する。フィンガープリントは、フィンガープリントのルックアップインデックスまたはデータベースのサイズを縮小しかつ格納要件を低減するために圧縮される。
【００５８】
フィンガープリントは、所定のキーポイントとその最近の（Ｎ−１）個の近傍キーポイントとの相対的２Ｄ位置から導出される、持続的比率と呼ばれる量子化された変換−不変２Ｄ比のシーケンスとして構築される。従って、各フィンガープリントは、特定のキーポイント辺りの小さい画像近傍へ局在化される。フィンガープリントシーケンスは、特定のキーポイントとその最近の（Ｎ−１）個の近傍キーポイントとの間の相対的な２Ｄジオメトリにのみ依存する。近傍キーポイントの数Ｎは、フィンガープリントの強度に影響する設計パラメータである。
【００５９】
本出願は、通常デジタルカメラまたは携帯電話のカメラで画像を走査する、または写真を撮るプロセスの間に発生するスキュー、捻れ、回転、平行移動、スケール、解像度の変化及びこれらに類似するもの等の、但しこれらに限定されない所定の画像歪に対してフィンガープリントをロバストにする。
【００６０】
図１４に示されているように、オブジェクト表面上で三角形ＡＢＣ１４５０及び第２の三角形ＡＣＤ１４６０を構成する同一直線上にない４つの点｛Ａ，Ｂ，Ｃ，Ｄ｝（即ち、１４１０，１４２０，１４３０，１４４０）から成る任意の所定の多角形１４００の場合、三角形の面積比（ＡＢＣ／ＡＣＤ）１４７０が任意のアフィン変換下で一定のままであることは技術上周知である。故に、三角形の比１４７０として示されている１つの三角形の面積比の計算に必要な点は、Ｐ＝４個のみである。このアフィン変換は、多くの実際的状況におけるカメラ対平坦オブジェクトのジオメトリを説明するための容認できるモデルを提供するために示されている。
【００６１】
別の実施形態において、この変換は、２つの三角形比の積である１つの持続的比率を計算するために、（４ではなく）Ｐ＝５点を用いて透視変換を処理するように拡張されることが可能である。
【００６２】
従って、単一のフィンガープリントは、時計回り順にソートされた最近のＮ個の近傍キーポイントによるグループに関する量子化された持続的変換比率のシーケンスで構成される。フィンガープリントのサイズを小さく保つために、変換率はＱレベル１４８０に量子化される。ある実施形態において、Ｑの値は、便宜的に、２進法の２のべき乗であるように選択されることが可能である。図１４Ｂには、Ｑ＝８の場合の量子化プロセスが図１４Ａの三角形の比１４８０の量子化として示されている。量子化前の三角形の比の有効範囲（０，∞）は、図１４Ｂ（１４９０）に示されているように、「０」から「７」まででラベリングされたＱ＝８個の区間に分けられる。区間の境界は、代表的ドキュメントの大集合に渡って量子化ラベルの略均一な分布をもたらすように経験的に決定される。到来する三角形比の値１４８０は、増大する区間境界と順次比較されて第１の高次または等しい区間境界が決定され、この時点でプロセスは終了し、対応するラベル区間が量子化された結果として割り当てられる。例えば、１．０より低くかつ先行する区間境界より高い到来する三角形の比０．８２５３６９４には、量子化された値「３」が割り当てられる。
【００６３】
最近近傍法の使用における潜在的問題は、透視変換下では近いことが必ずしも持続されない点にある。任意のアフィン変換または透視変換下では、所定のキーポイントの最近のＮ個の近傍キーポイントが正確に同じＮ個のキーポイントであり続けるという保証はあり得ない。それでも、最も近いキーポイントは、もっと遠いキーポイントよりも最近のＮ個の近傍キーポイントのリスト内に留まる傾向が強い。
【００６４】
上述の問題を克服するために、本出願は、アフィン変換または透視変換に対するフィンガープリントのロバスト性をさらに高めるべく近傍キーポイントのうちの１つまたはそれ以上の不在を許容することを提案する。ある実施形態下では、１つのキーポイントは、局在化された小さい近傍においてアフィン歪が限定的であることを考慮して、除外されることが許容される。従って、所定の各キーポイントは、一度に１つのキーポイントを除外することによって幾つかのフィンガープリントＮを生み出す。各フィンガープリントは、残りのキーポイント数、Ｎ−１個を放射状の方位順で体系的に歩き、かつＰ個の点の組合せとして可能な全てのもの（アフィン変換のＰ＝４、透視変換のＰ＝５）について量子化された持続的比率のシーケンスを記録することによって生成される。
【００６５】
図１５には、フィンガープリントのプロセス１５００が示されている。フィンガープリントプロセス１５００への入力は、入力画像１５０５に関するキーポイント候補１５１０のリストである。図１５におけるフィンガープリントの第１の処理ステップは、キーポイント三角形分割モジュール１５２０である。この実施形態では、ドロネーまたはキーポイント三角形分割１５２０は、局在的近傍において所定の各キーポイントに最も近いキーポイントを識別するために使用される。三角形分割のリンクに従うことにより、所定の任意キーポイントに最も近い（Ｎ−１）個の近傍キーポイントを効果的に決定することができる。
【００６６】
各キーポイント候補及びその最も近い（Ｎ−１）個の近傍キーポイントは、フィンガープリント候補として考慮される。現行のキーポイント候補Ｋｐは各々、入力リスト１５１０から次のキーポイント取得モジュール１５３０によって順次選択される。各キーポイントＫｐについて、最近近傍キーポイント発見モジュール１５４０は、所定のキーポイントＫｐへの距離が最も近い（Ｎ−１）個の最近キーポイントを識別する。但し、Ｎは所定の変数である。最近近傍キーポイント発見モジュールは、ドロネーまたはキーポイント三角形分割結果１５２０を用いて、Ｋｐからの距離の増大順にソートされたＫｐへの最近キーポイントのリストを返す。返されるリストの最初のエレメントは、常に現行キーポイントＫｐ（距離ゼロ）である。変数Ｎの値は、１フィンガープリント当たりの演算数として定量化されるフィンガープリントの「強度」または識別力、即ち全体的なシステムパフォーマンスと、結果的に生じるデータベースのサイズまたはフィンガープリントサイズとの間に妥当な得失評価をもたらすように調整される。本例では、値Ｎ＝８、１２または１６が使用される。
【００６７】
最近近傍キーポイント発見モジュール１５４０の点は、面積比のシーケンスがデータベース画像とクエリ画像との間で同じキーポイント／近傍に対して一貫性があるように、一貫した順序で取り入れられる必要がある。時計回り順ソートモジュール１５５０は、所定のキーポイントに最も近いＮ個の近傍キーポイントのリストを時計回り方位の増大順にソートする。
【００６８】
時計回り順ソートモジュール１５５０は、ほぼ同一直線上にあるキーポイントの一般的事例に対してキーポイントの順序づけを安定させるための方法及びシステムを含む。時計回り順ソートモジュール１５５０は、リスト上の（所定のキーポイントに最も近い）最初のＭ個の最近近傍キーポイントを用いてサブグループの起原の中心を計算する。但し、Ｍ＜Ｎである。最も遠い（Ｎ−Ｍ）個のキーポイントは、アフィン変換または透視変換下では起原が安定したままであることを保証するために、サブグループの起原の中心の計算には使用されない。時計回り順ソートモジュール１５５０は、キーポイントの順序づけを決定するために、合計Ｎ＝８の場合はＭ＝５個の最近近傍キーポイントの平均位置を起原の中心として使用する。
【００６９】
現行の近傍キーポイントクラスタの起原の中心を決定した後、時計回り順ソートモジュール１５５０は、キーポイントを時計回り方位の増大順にソートすることに進む。ソートは、方位及び距離の双方に基づいて行われる。順序は、時計回り方位の増大順である。２つ以上の点がほぼ同じ方位を有していて、その差が予め規定された許容差レベル内であれば、これらの点は略類似方位の全ての点について距離の増大順にさらに順序づけされる。
【００７０】
Ｎ個のキーポイントによる一意の部分集合の各々について、次のサブグループ組合せモジュール１５６０は、アフィン変換または透視変換の場合に依存して、次のサブグループの組合せであるＰ＝４またはＰ＝５個のキーポイントを体系的かつ系統的に選択する。例えば、Ｎ＝８の場合、Ｐ＝４のキーポイントサブグループには一意の組合せが７０存在する。
【００７１】
Ｐ＝４個のキーポイントの次のサブグループの組合せの各々について、圧縮された量子化比率モジュール１５７０は単一の持続的比率を計算し、かつ予め規定された区間境界しきい値の集合を用いてこれを量子化する。量子化レベルの数Ｑは、設計パラメータである。これらの例では、Ｑ＝８、またはＱ＝１６が使用されている。量子化しきい値は、特定タイプのドキュメントの大型コレクションにおける持続的比率の分布を調査することによって経験的に決定される。
【００７２】
フィンガープリントデータベース１５８５のサイズをさらに縮小するために、圧縮された量子化比率モジュール１５７０は、結果的に生じる幾つかの量子化された持続的比率を１つの機械語に圧縮する。例えば、Ｎ＝８、Ｐ＝４及びＱ＝８の場合、７０のサブグループ組合せの全体的なフィンガープリントシーケンスは３つ以下の６４ビットワードに密に圧縮されることが可能である。本出願のある実施形態では、圧縮されたフィンガープリントのサイズは、合計３つの６４ビットワード及び３つの８ビットバイトを占有し、複数のワードまたはバイトに渡って部分的情報を分割する必要はない。
【００７３】
フィンガープリントを計算して圧縮するプロセスは、一度に１つの持続的比率で、最終組合せモジュール１５８０によって最後の組合せが検出されるまで順次継続する。現行のＰサブグループ組合せがまだ最後の組合せ１５８１でなければ、最終組合せモジュール１５８０は、次のＰサブグループを取得しかつその量子化された持続的比率の計算及びその圧縮へと進むためにこの流れを次のサブグループ組合せモジュール１５６０へとルーティングして戻す。このプロセスは、１５８２において最後のＰサブグループ組合せが処理されるまで続く。最後のＰサブグループ組合せが処理された時点で、結果的に得られる圧縮されたフィンガープリントデータ１５８３はフィンガープリントデータベース１５８５へ書き込まれる。フィンガープリントデータは、圧縮された各フィンガープリントデータが利用可能になるにつれて、フィンガープリントデータベース１５８５へ一度に１つのフィンガープリントについて順次書き込まれることが可能である。
【００７４】
最後に、フィンガープリントを書き込むプロセスは、残りの全てのキーポイントについて、最終キーポイントモジュール１５９０によって最後のキーポイントが検出されるまで順次継続する。現行のキーポイント組合せがまだ最後のキーポイント１５９１でなければ、最終キーポイントモジュール１５９０は、次のキーポイントを取得しかつプロセスを反復してその圧縮されたフィンガープリントの計算及びフィンガープリントデータベース１５８５へのその追加へと進むためにこの流れを次のキーポイント取得モジュール１５３０へとルーティングして戻す。フィンガープリントプロセスは、１５９２において最後のキーポイント組合せの最後の一致フィンガープリントが処理されてフィンガープリントデータベース１５８５へ追加されるまでこうして継続される。最後のキーポイントがアドレス指定されていれば、１５９５においてプロセスは終了する。
【００７５】
図１６Ａ−図１６Ｂには、フィンガープリントの起原の中心を計算する方法が示されている。図１６Ａは、所定の画像例１６００に関するプロセスを示す。処理画像は、キーポイントまたはワードの重心が円１６０１−１６０２等の円によって識別されて示されている。図中の他の円も、やはりワードの重心である。例えば、数字（１−７）もまた、点Ｘに近い近傍キーポイントであるワードの重心を表している。図１６Ｂは、明瞭さを高めるために背景の処理画像を除去しているが、他は図１６Ａと同じである。この例では、局在的近傍における７つの追加キーポイント（１−７）を用いてキーポイントＸのフィンガープリントが計算される。第１のステップにおいて、このフィンガープリントの起原の中心はキーポイントＸに最も近いＭ＝５個のキーポイントを用いて、即ち点｛Ｘ，１，２，３及び５｝の平均位置を用いて計算される。これは、起原の中心を点Ｘから離れて、かつキーポイントＸを含むテキストラインＹに沿ってキーポイントの同一直線上にあるラインから離れて、点０への矢印線１６２０に従って新たな起原の中心へと移動させるものと思われる。７個（１−７）のうちで最も遠い３つのキーポイント（４，６，７）は、任意のアフィン変換または透視変換によって点３つまではシフトされるものと見込むことによって点０の位置を安定させるために、起原の中心の計算には使用されない。第２のステップでは、８個のキーポイント（Ｘ及び１−７）の全体集合が、新たに計算されたサブグループの起原の中心（０）に対して時計回り順１６１０にソートされ、この場合は結果的に、（１，Ｘ，２，３，４，５，６，７）という最終的な出力シーケンス順序が得られる。上述の順序づけは、基準点に依存する。基準点として「０」が使用されれば、１は「０」からの点線より上にあることから、結果的なシーケンスは２３４Ｘ５６７１となっていたであろう。本明細書における代替方法は、Ｘを基準として使用し続けるがキーポイントの質量は「０」へ移動されるものと見せかけることであり、これにより先に述べたシーケンスがもたらされる。先では、基準として原初のキーポイント位置を保つ一方で、点「０」はＸの回りを移動してキーポイントシーケンス順をひっくり返させ得ることから、後者が使用されていた。しかしながらこれは、どちらの場合も達成される必要があるものはターゲット画像及びクエリ画像の双方で同じシーケンスを反復できることであるという理由により、どちらの方法で行うことも可能である。第２のステップの目的は、距離ではなく時計回り順にソートすることである。
【００７６】
所定のキーポイントについて最近のＮ個の近傍キーポイントの順序づけが確立されると、フィンガープリントを生成することができる。フィンガープリントは、近傍におけるキーポイントによるサイズＰ＝４の連続する部分集合から、一度に１つまたはそれ以上のキーポイントを除外しかつ除外されないキーポイントで残りのサブグループ組合せのシーケンスを構築することによって形成される。従って、サブグループ組合せの圧縮されたシーケンスからフィンガープリントのグループを効果的に構築することができる。Ｎ個のキーポイントによるＰ個の部分集合は、体系的かつ一貫した方式で考察される。その各々について、本明細書で記述しているように、そのＰ部分集合の持続的面積比を計算しかつその面積比を整数にマッピングすることによって整数が決定される。所定のキーポイントのフィンガープリントの長さは、このようなＰ個の部分集合の合計数である。これは、Ｎ個のキーポイントから一意のＰ個のキーポイントを選択するための組合せの数によって決定される。例えば、Ｎ＝８及びＰ＝４であれば、サブグループ組合せとして可能性のある数は７０個の持続的比率である。このうち、各々長さが３５サブグループ組合せである８個のフィンガープリントは、例えば一度に１つのキーポイントを除外することによって構築されることが可能である。
ａ．３  高速マッチングのためのフィンガープリント情報の作成
【００７７】
図１５において、フィンガープリントデータベース１５８５内のフィンガープリントは、メモリサイズ及びロード時間を縮小するために圧縮フォーマットで記憶されることから、効率的なフィンガープリントマッチングを促進するために、まず解凍されかつファン木データ構造に従って一意の方法で編成し直されなければならない。フィンガープリントデータベースは、最初の画像クエリ時に一度だけ作成すればよい。（未解凍のフィンガープリントシーケンスを含む）ファン木データ構造はメモリに保持され、かつ続いて任意数の画像クエリにより再使用されることが可能である。
【００７８】
圧縮されたフィンガープリントデータベース１７１０の作成方法については、先に例示した（図１５）。フィンガープリント情報は、フィンガープリントデータベース１７１０から検索される。フィンガープリントデータベースのエントリは各々、複数のフィンガープリント候補を発生させる。
【００７９】
キーポイント除外モジュール１７２０は、フィンガープリントキーポイント１７３０のうちの１つまたはそれ以上を除外することによって複数のフィンガープリントキーポイント組合せ候補を選択する。これは、局在的近傍キーポイント間の１つまたは複数の不在キーポイントを見込んでいる。本実装において、キーポイント除外モジュールは１つのキーポイントを除外する。局在的近傍がＮ個のキーポイントである場合、各キーポイント毎に１つのデータベースエントリが行われることから、これは、各データベースエントリ毎にＮ個のフィンガープリント、または１つのキーポイント当たりＮ個のフィンガープリントを発生させる。
【００８０】
フィンガープリントシーケンスモジュール１７５０は、各キーポイント毎にＮ個のフィンガープリント候補のシーケンスを生成する。例えば、Ｎ＝８のとき、キーポイント除外モジュール１７２０は、第１のキーポイントを除外して残りの７個のキーポイントを選択することにより第１のフィンガープリントを生成させる。この後、キーポイント除外モジュールは第２のキーポイントを除外して第１のキーポイント及び最後の６個のキーポイントを選択し、第２のフィンガープリントを生成する。このプロセスは、全てのキーポイント組合せが除外されるまで続く。この例では、各データベースエントリは８個のフィンガープリント候補を生成し、各々が７個から４個を選ぶ３５通りの長さを有する。
【００８１】
Ｎ＝８及びＰ＝４のとき、４個のキーポイントによるサブグループの一意の組合せは（８個から４個を選ぶ）＝７０通りある。これが、キーポイント毎の圧縮フォーマットでデータベース１７１０に格納される。
【００８２】
次に、１つのキーポイントが不在である場合のフィンガープリントが生成される。しかしながら、どのキーポイントがなくなるかは事前に分からないため、全ての可能性についての準備が行われる。Ｎ＝８の場合、１つのキーポイントが不在となる可能性は８通り、即ち第１のキーポイント、または第２のキーポイント、または第３のキーポイント、他と、合計８つの場合がある。これらの事例の各々について、異なるフィンガープリントが計算される。この場合の各フィンガープリントは、（原初の８個のうちの１つが不在であるために）７個のキーポイントのみを基礎とする。この場合、各フィンガープリントの長さは（７個から４個を選ぶ）＝３５であり、それが合計８個存在する。これは、各フィンガープリントが０−７の範囲の３５個の整数（量子化比率）のシーケンスから成ることを意味する。８個のフィンガープリントは、ファン木データへ追加される。
【００８３】
クエリ時間では、８個のキーポイント（現行の１つ及び最近の７個）が生成され、かつ同じ方法を使用しかつ同様に一度に１つのキーポイントを除外して再度８個のクエリフィンガープリントが計算される。次に、キーポイントとファン木のコンテンツとのマッチングが試行される。マッチングは、最初にマッチングが達成された時点で停止される。クエリ画像から１つのキーポイントが欠けていれば（どのキーポイントであるかは問題ではない）、８個のうちの１つのクエリフィンガープリントは必ず（他の７個が存在する状態で１つとの）マッチングを有する。どのキーポイントも欠けていなければ（８個全てが存在する）、最初の肯定的マッチの後にプロセスが停止してチェックを続ける必要がない場合を除いて、（７の任意のグループはマッチすることから）８個のマッチが存在することになる。しかしながら、同時に２つ以上のキーポイントが欠けていれば、この位置についてはマッチが存在しない。所望されれば、本システムは、より多くの不在キーポイント（例えば、８個のうちの２個、他）を許容するように方法を拡張することによって、より多くの不在キーポイントを容易に処理することも可能である。
【００８４】
フィンガープリントシーケンスモジュール１７５０から出力されるフィンガープリントデータ１７６０は、現行画像のデータベースから検索される一意の画像ＩＤ１７４０と共にフィンガープリントレコード１７８０を形成する。フィンガープリントレコード１７８０は、ファン木モジュール１７７０によってアドレス指定される対応するファン木葉ノード位置に格納される。ファン木葉ノード情報は、対応するフィンガープリントデータ構造１７９０内にフィンガープリントレコード１７８０の連結リストとして格納される。ポピュレートは、実数のフィンガープリントに対応する実際のファン木葉ノードのみに行われる。特定の葉ノードに到達する第１のフィンガープリントは、その葉ノードを最初にポピュレートする。同じ葉ノードにおいて期せずして（即ち、同じファン木経路を辿って）再度２つ以上のフィンガープリントが到着すれば、新しいフィンガープリント情報は、新しいフィンガープリント情報をその葉ノード上の先行する最後のフィンガープリント情報と連結することによって、その同じ葉ノードへ追加される。
【図１】
0005753473.tif 000002
【図２】
0005753473.tif 000003
【図３】
0005753473.tif 000004
【図４】
0005753473.tif 000005
【図５】
0005753473.tif 000006
【図６】
0005753473.tif 000007
【図７】
0005753473.tif 000008
【図８】
0005753473.tif 000009
【図９】
0005753473.tif 000010
【図１０】
0005753473.tif 000011
【図１１】
0005753473.tif 000012
【図１２】
0005753473.tif 000013
【図１３】
0005753473.tif 000014
【図１４Ａ】
0005753473.tif 000015
【図１４Ｂ】
0005753473.tif 000016
【図１５】
0005753473.tif 000017
【図１６Ａ】
0005753473.tif 000018
【図１６Ｂ】
0005753473.tif 000019
【図１７】
0005753473.tif 000020