(57)【特許請求の範囲】
【請求項１】
データストアに格納されているオンラインドキュメントの読み込みおよび／またはインデックス作成のためのシステムであって、
オンラインドキュメントを格納するデータストアと、
プロセッサと
を備え、前記プロセッサが、
オンラインドキュメントが印刷される場合に前記オンラインドキュメントのイメージを生成し、前記オンラインドキュメントに関連付けて前記データストアに格納するキャッシングプログラムと、
物理的ドキュメントの少なくとも一部の取り込まれたイメージを受け取るプログラムと、
前記オンラインドキュメントのイメージおよび前記物理的ドキュメントのイメージに対する署名をイメージごとに生成する署名生成プログラムであって、前記イメージ内の各単語の場所を示す座標および当該単語の幅に基づいて署名を生成する、署名生成プログラムと、
前記オンラインドキュメントのイメージに対する署名と、前記物理的ドキュメントのイメージに対する署名を比較することにより、前記物理的ドキュメントのイメージに対応するオンラインドキュメントのイメージを特定する検索プログラムと
を実行するよう構成されることを特徴とするシステム。
【請求項２】
前記署名生成プログラムは、前記オンラインドキュメントのイメージに対する署名に基づいてハッシュテーブルを生成し、前記オンラインドキュメントのイメージに関連付けて前記データストアに格納することを特徴とする請求項１に記載のシステム。
【請求項３】
前記プロセッサが、さらに、ハッシュテーブルに格納されている座標および幅と一致する前記物理的ドキュメントのイメージ内の単語の数に基づいて、前記ハッシュテーブルに信頼度スコアを割り当てるスコアリングプログラムを実行するよう構成されることを特徴とする請求項２に記載のシステム。
【請求項４】
前記信頼度スコアが最高であるハッシュテーブルに関連する前記オンラインドキュメントのイメージは、前記物理的ドキュメントのイメージに対応するイメージとして選択されることを特徴とする請求項３に記載のシステム。
【請求項５】
前記署名生成プログラムは、さらに前記座標および前記幅に関する許容誤差しきい値に基づいて署名を生成することを特徴とする請求項１に記載のシステム。
【請求項６】
前記署名生成プログラムは、前記イメージを複数のセグメントに分割してセグメントごとに署名を生成し、
前記検索プログラムは、前記オンラインドキュメントのイメージの所定のセグメントに対する署名と、前記所定のセグメントに対応する前記物理的ドキュメントのイメージのセグメントに対する署名を比較することを特徴とする請求項１に記載のシステム。
【請求項７】
前記検索プログラムは、前記物理的ドキュメントのイメージの前記所定のセグメントに対する署名と一致する署名を有する前記オンラインドキュメントのイメージについて、さらに、前記物理的ドキュメントのイメージの他のセグメントに対する署名と、前記他のセグメントに対応する前記オンラインドキュメントのイメージのセグメントに対する署名を比較することを特徴とする請求項６に記載のシステム。
【請求項８】
前記検索プログラムは、前記物理的ドキュメントのイメージの所定のセグメントに対する署名と一致する署名を有する前記オンラインドキュメントのイメージの数が、所定のしきい値になるまで比較を行うことを特徴とする請求項７に記載のシステム。
【請求項９】
前記プロセッサが、さらに、
前記オンラインドキュメントのイメージおよび前記物理的ドキュメントのイメージに関する、複数の階層レベルを有する木表現を生成するプログラムであって、イメージを複数のセグメントに分割して第１の階層レベルのノードに関連付け、前記第１の階層レベルのノードに関連付けられたセグメントをさらに分割して第２の階層レベルのノードに関連付け、各セグメント内に単語が存在するかどうかを示す値を各ノードに割り当てる、木表現を生成するプログラムと、
前記オンラインドキュメントのイメージに関する木表現と前記物理的ドキュメントのイメージに関する木表現を比較する比較プログラムであって、前記オンラインドキュメントの第１のノードに割り当てられた値が、前記第１のノードに関連付けられたセグメント内に単語が存在しないことを示し、前記第１のノードに対応する、前記物理的ドキュメントの第２のノードに割り当てられた値が、前記第２のノードに関連付けられたセグメント内に単度が存在することを示す場合、前記オンラインドキュメントのイメージを、前記検索プログラムの比較対象から除外する、比較プログラムと
を実行するよう構成されることを特徴とする請求項１に記載のシステム。
【請求項１０】
前記プロセッサが、さらに、前記物理的ドキュメントのイメージ内のノイズを低減するプログラムを実行するよう構成されることを特徴とする請求項１に記載のシステム。
【請求項１１】
前記プロセッサが、さらに、前記物理的ドキュメントのイメージのグレースケールイメージを生成するプログラムを実行するよう構成されることを特徴とする請求項１に記載のシステム。
【請求項１２】
前記プロセッサが、さらに、前記キャッシングプログラムによって生成されるオンラインドキュメントを所定の条件に基づいて判別し、前記キャッシングプログラムに通知する人工知能プログラムを実行するよう構成されることを特徴とする請求項１に記載のシステム。
【請求項１３】
前記キャッシュプログラムは、前記オンラインドキュメントのイメージをページごとに生成することを特徴とする請求項１に記載のシステム。
【請求項１４】
前記データストアは、前記オンラインドキュメントのイメージに関連付けて、前記オンラインドキュメントの場所を識別するＵＲＬ、前記オンラインドキュメントのイメージに対する署名、および前記オンラインドキュメントのイメージの前記木表現を格納することを特徴とする請求項１３に記載のシステム。
【請求項１５】
データストアに格納されているオンラインドキュメントの読み込みおよび／またはインデックス作成を容易にするためにコンピュータによって実行される方法であって、
キャッシングプログラムが、オンラインドキュメントが印刷される場合に前記オンラインドキュメントのイメージを生成し、前記オンラインドキュメントに関連付けて前記データストアに格納するステップと、
クエリプログラムが、物理的ドキュメントの少なくとも一部の取り込まれたイメージを受け取るステップと、
署名生成プログラムが、前記オンラインドキュメントのイメージに対する署名を生成するステップと、
前記署名生成プログラムが、前記物理的ドキュメントのイメージに対する署名を生成するステップと、
検索プログラムが、前記オンラインドキュメントのイメージに対する署名と、前記物理的ドキュメントのイメージに対する署名を比較して、前記物理的ドキュメントのイメージに対応するオンラインドキュメントのイメージを特定するステップと
を含み、
前記署名は、前記イメージ内の各単語の場所を示す座標および当該単語の幅に基づいて生成されることを特徴とする方法。
【請求項１６】
前記署名生成プログラムは、前記イメージを複数のセグメントに分割してセグメントごとに署名を生成し、
前記検索プログラムは、前記オンラインドキュメントのイメージの所定のセグメントに対する署名と、前記所定のセグメントに対応する前記物理的ドキュメントのイメージのセグメントに対する署名を比較することを特徴とする請求項１５に記載の方法。
【請求項１７】
スコアリングプログラムが、前記座標および幅と一致する前記物理的ドキュメントのイメージ内の単語の数に基づいて、前記オンラインドキュメントのイメージに対する署名に信頼度スコアを割り当てるステップを含むことを特徴とする請求項１６に記載の方法。
【請求項１８】
さらに、
木表現を生成するプログラムが、
前記物理的ドキュメントのイメージに関する、複数の階層レベルを有する木表現を生成するステップであって、
前記物理的ドキュメントのイメージを複数のセグメントに分割して、第１の階層レベルのノードに関連付けるステップと、
前記第１の階層レベルのノードに関連付けられたセグメントをさらに分割して、第２の階層レベルのノードに関連付けるステップと
を含み、各セグメント内に単語が存在するかどうかを示す値が各ノードに割り当てられる、前記物理的ドキュメントのイメージの木表現を生成するステップと、
前記オンラインドキュメントのイメージに関する、複数の階層レベルを有する木表現を生成するステップであって、
前記オンラインドキュメントのイメージを複数のセグメントに分割して、第１の階層レベルのノードに関連付けるステップと、
前記第１の階層レベルのノードに関連付けられたセグメントをさらに分割して、第２の階層レベルのノードに関連付けるステップと
を含み、各セグメント内に単語が存在するかどうかを示す値が各ノードに割り当てられる、前記オンラインドキュメントのイメージの木表現を生成するステップと、
比較プログラムが、
前記オンラインドキュメントのイメージに関する木表現と前記物理的ドキュメントのイメージに関する木表現を比較するステップであって、前記オンラインドキュメントの第１のノードに割り当てられた値が、前記第１のノードに関連付けられたセグメント内に単語が存在しないことを示し、前記第１のノードに対応する、前記物理的ドキュメントの第２のノードに割り当てられた値が、前記第２のノードに関連付けられたセグメント内に単度が存在することを示す場合、前記オンラインドキュメントのイメージを、前記検索プログラムの比較対象から除外するステップと
を含むことを特徴とする請求項１５に記載の方法。
【請求項１９】
ノイズ低減プログラムが、前記検索プログラムによるオンラインドキュメントのイメージの特定に先立って、前記物理的ドキュメントのイメージ内のノイズを低減するステップを含むことを特徴とする請求項１５に記載の方法。
【請求項２０】
ノイズを低減することは、
幅がしきい値で定められた幅よりも大きいマーキングを除去するフィルタを備えることと、
幅がしきい値で定められた幅よりも小さいマーキングを除去するフィルタを備えることと、
高さがしきい値で定められた高さよりも大きいマーキングを除去するフィルタを備えることと、
高さがしきい値で定められた高さよりも小さいマーキングを除去するフィルタを備えることのうちの１つを含むこと
を特徴とする請求項１９に記載の方法。
【請求項２１】
グレースケールプログラムが、前記検索プログラムによるオンラインドキュメントのイメージの特定に先立って、前記物理的ドキュメントのイメージのグレースケールイメージを生成するステップを含むことを特徴とする請求項１５に記載の方法。
【請求項２２】
データストアに格納されているオンラインドキュメントの読み込みおよび／またはインデックス作成のためのシステムであって、
オンラインドキュメントを格納するデータストアと、
オンラインドキュメントが印刷される場合に前記オンラインドキュメントのイメージを生成し、前記オンラインドキュメントに関連付けて前記データストアに格納する手段と、
物理的ドキュメントの少なくとも一部の取り込まれたイメージを受け取る手段と、
前記オンラインドキュメントのイメージおよび前記物理的ドキュメントのイメージに対する署名をイメージごとに生成する手段であって、前記イメージ内の各単語の場所を示す座標および当該単語の幅に基づいて署名を生成する手段と、
前記オンラインドキュメントのイメージに対する署名と、前記物理的ドキュメントのイメージに対する署名を比較することにより、前記物理的ドキュメントのイメージに対応するオンラインドキュメントのイメージを特定する手段と
を備えることを特徴とするシステム。
【請求項２３】
前記署名を生成する手段は、さらに前記座標および前記幅に関する許容誤差しきい値に基づいて署名を生成することを特徴とする請求項２２に記載のシステム。
【請求項２４】
前記署名を生成する手段は、前記オンラインドキュメントのイメージおよび前記物理的ドキュメントのイメージを複数のセグメントに分割してセグメントごとに署名を生成し、
前記特定する手段は、前記物理的ドキュメントのイメージの所定のセグメントに対する署名と、前記所定のセグメントに対応する前記オンラインドキュメントのイメージのセグメントに対する署名を比較することを特徴とする請求項２２に記載のシステム。
【請求項２５】
データストアに格納されているオンラインドキュメントの読み込みおよび／またはインデックス作成を容易にする方法をコンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体であって、前記方法は、
キャッシングプログラムが、オンラインドキュメントが印刷される場合に前記オンラインドキュメントのイメージを生成し、前記オンラインドキュメントに関連付けて前記データストアに格納するステップと、
クエリプログラムが、物理的ドキュメントの少なくとも一部の取り込まれたイメージを受け取るステップと、
署名生成プログラムが、前記オンラインドキュメントのイメージに対する署名を生成するステップと、
前記署名生成プログラムが、前記物理的ドキュメントのイメージに対する署名を生成するステップと、
検索プログラムが、前記オンラインドキュメントのイメージに対する署名と、前記物理的ドキュメントのイメージに対する署名を比較して、前記物理的ドキュメントのイメージに対応するオンラインドキュメントのイメージを特定するステップと
を含み、
前記署名は、前記イメージ内の各単語の場所を示す座標および当該単語の幅に基づいて生成されることを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項２６】
コンピュータを、データストアに格納されているオンラインドキュメントの読み込みおよび／またはインデックス作成のためのシステムとして機能させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体であって、
オンラインドキュメントが印刷される場合に前記オンラインドキュメントのイメージを生成し、前記オンラインドキュメントに関連付けて前記データストアに格納するキャッシングプログラムと、
物理的ドキュメントの少なくとも一部の取り込まれたイメージを受け取るプログラムと、
前記オンラインドキュメントのイメージおよび前記物理的ドキュメントのイメージに対する署名をイメージごとに生成する署名生成プログラムであって、前記イメージ内の各単語の場所を示す座標および当該単語の幅に基づいて署名を生成する、署名生成プログラムと、
前記オンラインドキュメントのイメージに対する署名と、前記物理的ドキュメントのイメージに対する署名を比較することにより、前記物理的ドキュメントのイメージに対応するオンラインドキュメントのイメージを特定する検索プログラムと
を備えることを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項２７】
請求項１に記載のシステムを含むことを特徴とするパーソナルデジタルアシスタント。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、格納されているドキュメントのインデックス署名（ｉｎｄｅｘ  ｓｉｇｎａｔｕｒｅ）と格納されているドキュメントの印刷版から生成されたインデックス署名とを比較することによる格納されているオンラインドキュメントのインデックス作成および／または検索に関する。
【背景技術】
【０００２】
コンピューティングおよび通信分野における技術進歩により、ドキュメントを介した情報のやり取りに関する商慣行が大きく変わった。現在では、書式付きドキュメントは、遠く離れていても、オンラインでほとんど瞬時に配送することができる。しかし、ビジネスおよび個人環境においては、印刷されたドキュメントに対しかなりの量の校訂および／または編集作業が行われる。例えば、作業環境内での会合は、通常、印刷されたドキュメントを出席者に印刷されたドキュメントを配布する作業を含む。さらに、多くの個人は、コンピュータの画面上での読み取りおよび／または編集ではなく紙の上でのドキュメントの読み取りおよび／または編集を好んでいる。
【０００３】
相当量のドキュメントが印刷されるビジネスまたは個人環境では、それぞれのオンライン版に対するそのようなドキュメントのインデックス作成は問題がある。汚れおよび破れを含むドキュメントの損傷は、印刷されたドキュメントに書き込まれる注釈とあわせて、印刷されたドキュメントをそれぞれのオンライン版に関係付けることをさらに難しくする原因といえる。例えば、ドキュメントは、会合で印刷し配布することができ、会合の出席者は、ドキュメント内の情報とともに会合に関する考え方に従ってペンまたは類似のマーキングツールを使って注釈を入れることができる。その後、ドキュメントは、フォルダに入れられ、その会合から別の場所に運ばれるときに、折り畳まれたり、しみがついたり、破られたり、他の同様の形で損傷する可能性がある。それ以降、ドキュメントは、他のドキュメントの堆積の中に、何時間も、何日も、さらには何カ月もの間置かれたままになることがある。印刷されたドキュメントのオンライン版が置かれるのが望ましい場合、そのようなオンライン版を特定するのにかなりの時間がかかることがある。さらに、ドキュメントのオンライン版が特定できない場合、ドキュメントをコンピュータに再入力するためのリソースを割り当てなければならない場合もある。
【０００４】
ドキュメントの物理的に存在する版（例えば印刷版）に基づいてドキュメントのオンライン版を特定することが問題になる他のシナリオも存在する。例えば、ベンダは、発注書草稿を準備し、消費者にＦＡＸで送信することができ、そのような発注書を受け取った消費者は、ペンまたは他の適当なマーキングツールを使ってドキュメントを物理的に修正することによりＦＡＸドキュメントの内容を修正することができる。これ以降、消費者は、修正されたドキュメントをＦＡＸを使ってベンダに中継することができる。印刷されたドキュメントのオンライン版を特定するために、ベンダは人手でデータベース内を検索して印刷版のドキュメントとオンライン版のドキュメントとを照合しなければならない。ドキュメントのオンライン版と印刷版との相互関連付けには、かなりの時間を要する場合があり、特に、例えばドキュメント作成した人が印刷されたドキュメントと対応するオンライン版との照合を手助けできない場合（例えば、個人が休暇、退職などでいない場合）には時間がかかる。
【０００５】
対応するオンラインドキュメントを使って物理的ドキュメントのインデックスを作成することに関連する問題を解消する従来のシステムおよび／または方法では、印刷されたドキュメントを識別情報でマーキングする必要がある。例えば、それぞれの印刷されたドキュメントにファイルロケーションを含めることができる（例えば、それぞれの印刷されたドキュメントのヘッダに入れると、対応するオンライン版に関係する拡張ファイルロケーションを印刷した場合に、オンライン版を特定できる）。そうする代わりに、一意的なバーコードをそれぞれの印刷されたドキュメントに表記し、バーコードを使って、ドキュメントのオンライン版を特定するようにもできる。例えば、バーコードスキャナを使用して、印刷されたドキュメントに表示されているバーコードをスキャンし、そのスキャン結果に基づいてドキュメントの対応するオンライン版を読み出すことができる。しかし、このような識別情報があると、ドキュメントは乱雑な、見てくれの悪い印象を与える。さらに、破れ、染み、注釈、またはその他の物理的損傷／改変が印刷されたドキュメントに加わると、そのような従来のシステムおよび／または方法は実質的に役立たないといってよい。例えば、バーコードの一部が印刷されたドキュメントから引きはがされている場合、バーコードスキャナは、バーコードを正常に読み取ることができない。同様に、ドキュメントに染みがあると、ドキュメントのオンライン版の印刷箇所が読み取り不能になる場合がある。光学式文字認識（ＯＣＲ）も、印刷版に基づいてドキュメントのオンライン版を特定することに関連して採用することができる。例えば、印刷されたドキュメントを（例えば、スキャナ、デジタルカメラなどを使って）デジタル化し、コンピューティングコンポーネントにより、ＯＣＲを使用して、印刷されたドキュメントのデジタル化されたドキュメント内の特定の文字を識別し、そのような文字を印刷されたドキュメントのオンライン版の中の対応する文字と照合することができる。しかし、そのような手法だと、かなりのコンピューティング資源を必要とする。さらに、データベースには、数百または数千ものドキュメントが収められている場合があり、複数のドキュメントに対しＯＣＲを実行すると、かなり時間がかかることがある。印刷されたドキュメントに基づいてドキュメントのオンライン版を特定するために使用される他のアプリケーションでは、キーワード（例えば、修正日またはその他のキーワード）を利用して、オンライン版を特定する。しかし、キーワードを取得することは難しく、複数のドキュメントにそのような複数のキーワードが含まれていることがある。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
少なくとも上記の説明を鑑みると、オンラインドキュメントおよびそれに対応する物理的ドキュメントの確実なインデックス作成を行うシステムおよび／または方法だけでなく、ドキュメントの印刷版およびオンラインドキュメントに関連付けられている情報（例えば、データベースのレコード、ワークフローなど）に基づいてオンラインドキュメントの検索を可能にするシステムおよび／または方法が、当業では切実に必要とされている。
【課題を解決するための手段】
【０００７】
以下では、本発明のいくつかの態様の基本的な内容を理解できるように、本発明の要約を簡単に述べる。この要約は、本発明の概要を広範囲にわたって述べたものではない。この要約は、本発明の鍵となるまたは重要な意味を持つ要素を示すことも、本発明の範囲を定めることも意図としていない。後で述べる詳細な説明の前置きとして、本発明のいくつかの概念を簡略化した形式で述べることのみを目的とする。
【０００８】
本発明を実施することにより、格納されているドキュメントに関係付けられた署名をそのような格納されているドキュメントに対応する印刷されたドキュメントのイメージに関係付けられている署名とを比較することによる格納されているオンラインドキュメントのインデックス作成および／または検索が容易になる。本発明では、ドキュメントの単語レベルのトポロギーのプロパティを利用して署名を生成し、それによって、格納されているドキュメントの検索を、従来のシステムおよび／または方法に関連する欠点を伴わずに、迅速に、しかも確実に完了することができる。格納されているオンラインドキュメントを識別する署名は、それぞれのドキュメント内の単語レイアウトに関係するデータを取得することを介して生成される。署名は、ノイズ（例えば印刷ノイズ）が存在していてもその署名でドキュメントを識別できる方法で生成できることは理解されるであろう。したがって、署名はドキュメントに非常に特異的である特徴に関連しているため、それぞれの署名により特定のドキュメントを確実に識別することができる。例えば、２つの異なるドキュメントが実質的に類似の単語レイアウトパターンを持つ確率は極めて小さいため、ドキュメント内の複数の単語の少なくとも一部の位置とともにドキュメント内の複数の単語の幅を利用して、ドキュメントを確実に識別する署名を作成できる。本発明の一態様によれば、署名は、印刷されたドキュメントに対応付けることができるオンラインドキュメントのイメージを含むデータストアをロードすると生成される。例えば、データストアは、印刷されたドキュメントのイメージに基づいて特定のオンラインドキュメントを特定する要求を受け取ると、ロードする（そして、署名を生成する）ことができる。印刷されたドキュメントのイメージの単語レイアウトを利用する署名は、イメージを受け取ると生成され、その後、そのような署名とオンラインドキュメントに関係する署名との比較を行うことができる（例えば、格納されているオンラインドキュメントのイメージを利用することで生成される署名）。その後、印刷されたドキュメントのイメージの署名に実質的に一致しているといって間違いのない署名に関連付けられているオンラインドキュメントを取り出すことができる。
【０００９】
本発明の一態様によれば、ドキュメントのイメージは、自動生成することができ、ドキュメントを印刷すると、そのイメージに関係する署名が生成され、データストア内に格納することができる。これにより、すべての印刷されたドキュメントについて、指定されたデータストア内のそのようなドキュメントの格納されるオンライン版に関係する署名が必ず存在する。したがって、ドキュメントを作成し、ドキュメントの印刷後、ビットマップ（またはその他の適当なイメージフォーマット）を自動生成することができる。ドキュメントを識別する署名は、オンラインドキュメントのイメージが生成された後に生成され、データストアに格納することができる。その後、ドキュメントは、再び修正して印刷することができ、その結果、オリジナルのドキュメントに関係する署名を改変せずに、修正されたドキュメントに関係する署名が自動生成され格納される。その後、オンラインドキュメントの単語レイアウトを表す署名を印刷されたドキュメントの後から取り込まれたイメージの署名と比較し、後から取り込まれたイメージの署名と実質的に一致しているといって間違いのない署名に関係するドキュメントのオンライン版を読み出すことができる。
【００１０】
しかし、印刷されたドキュメントに複数の注釈、汚れ、折り目、およびその他の物理的修正が含まれる場合、印刷されたドキュメントとドキュメントのオンライン版との照合の際に難しい問題が発生することがある。したがって、本発明では、ドキュメントの単語レイアウトを利用して署名を生成するのに先立ってそのような物理的修正を特定し、除去する。本発明と関連して注釈、マークアップ、およびその他のノイズを除去するフィルタが用意される。さらに、印刷されたドキュメントの取り込まれたイメージのグレースケールイメージを生成することによりノイズを減らすことができる。例えば、特定の照明が与えられた場合、白色の背景と黒色のレタリングのドキュメントのイメージは、黄色の背景および緑色のレタリングを持つように見える場合がある。イメージをグレースケール化すると、イメージが該当する色を含まない場合に発生しうる問題を効果的緩和することができる。
【００１１】
本発明の他の態様によれば、オンラインドキュメントの署名および／または印刷されたドキュメントのイメージの署名は、印刷されたドキュメントのイメージを取得する際に発生しうる回転および／または平行移動を含むことができる。例えば、印刷されたドキュメントは、スキャナ内で正確に揃えられない場合がある（例えば、ドキュメントのイメージがイメージ境界に関して平行移動および／または回転することがある）。このような誤差が考慮されない場合、印刷されたドキュメントのイメージの署名は、対応するオンラインドキュメントの署名と実質的に一致しない可能性がある。したがって、印刷されたドキュメントのイメージを取り込む時に発生しうる誤差を考慮することで、対応するオンラインドキュメントの配置および読み込みが確実に行える。
【００１２】
本発明では、さらに、オンラインドキュメントの多数の署名を印刷されたドキュメントのイメージの署名と比較するために要する時間に関連して生じる可能性のある問題も対象とする。例えば、データストアに数千ものドキュメントまたはドキュメントのイメージが含まれていた場合、ドキュメントまたはイメージに関係する署名を完全に比較するために望ましい時間以上の時間を要することがある。このような問題を解決するために、本発明では、考慮すべきオンラインドキュメントの署名の数を素早く減らすシステムおよび／または方法を提示する。ドキュメントの木表現を生成することができるが、木表現とはイメージの特定のセグメントが１つまたは複数の単語を含むかどうかに基づくイメージの階層表現のことである。例えば、１つのイメージを複数のセグメントに分割して、値をそのようなセグメントに関連付け、その値をセグメントに１つまたは複数の単語が含まれているかどうかを比較コンポーネントに通知するために使用することができる。この後、それらのセグメントを複数のセグメントに分割して、値をそれらのセグメントに関連付け、その値を、セグメントに１つまたは複数の単語が含まれているかどうかを比較コンポーネントに通知するために使用する。その後、印刷されたドキュメントのイメージに関係する木表現を複数のドキュメントのオンライン版に関係する木表現と比較することができる。それらの木表現は、署名に比べて複雑でなく、それらの木表現を使用することにより、印刷されたドキュメントの取り込まれたイメージに少なくとも一部は基づいてドキュメントのオンライン版を特定することに関して考慮されている署名の数を素早く減らすことができる。
【００１３】
本発明の他の態様によれば、オンラインドキュメントの署名を複数のセグメントに分割し、印刷されたドキュメントのイメージの署名も同様に分割することができる。その後、格納されているオンラインドキュメントの署名のセグメントを印刷されたドキュメントに関係するイメージの署名の対応するセグメントと比較することができる。本発明の他の態様によれば、署名はハッシュテーブルとすることができ、比較されたセグメントに一致が１つあれば（またはしきい値数分の一致があれば）、ハッシュテーブル全体がさらに考慮対象となる。したがって、セグメントのすべての系列を比較する必要はなく、まして、ハッシュテーブル全体の全行を必要とすることはない。オンラインドキュメントのいくつかのセグメントが印刷されたドキュメントに関係するハッシュテーブルの対応するセグメントとの１つまたはしきい値数だけの一致を有しない、オンラインドキュメントのハッシュテーブルは考慮対象から外される。考慮対象となっている多数のハッシュテーブルがしきい値に達した場合、残りのハッシュテーブルと印刷されたドキュメントに関係するハッシュテーブルとのさらに徹底した比較が実行される。残りのハッシュテーブル毎に信頼度スコアを生成し（例えば、一致する各行に１ポイントを与え、ポイント総数を総計することができる）、ハッシュテーブルの１つまたは複数の信頼度スコアがしきい値を超えている場合、信頼度スコアが最高のハッシュテーブルに関係するドキュメントのオンライン版をハイパーリンク、ＵＲＬ、またはその他の適当な方法を介してユーザに返すことができる。信頼度スコアがしきい値を超えるハッシュテーブルが残っていない場合、異なるセグメントまたはセグメントの組み合わせがないか、破棄されたハッシュテーブルを再度考慮することができる。上記の実施例は、ハッシュテーブルを署名として使用できることを述べているが、格納することができ、オンラインドキュメントの署名として働くデータ構造を本発明に関して採用できることは理解されるであろう。
【００１４】
前記および関係する目的を遂行するために、本発明は、次に、以下で詳しく説明され、請求項で特に指摘される特徴を含む。以下の説明および付属する図面では、本発明のいくつかの例示される態様を詳細に取りあげる。ただし、これらの態様は本発明の原理を採用するさまざまな方法のうちわずかのみを示しており、本発明はこのような態様およびその等価物すべてを含むことを意図している。本発明の他の目的、利点、および新規性のある特徴は、図面を参照しつつ本発明の以下の詳細な説明を読むと明白になるであろう。
【発明を実施するための最良の形態】
【００１５】
次に、本発明は、本明細書全体を通して類似の番号は類似の要素を示すために使用される図面を参照しつつ説明される。以下の説明では、説明を目的として、本発明を完全に理解できるようにする多数の具体的詳細を述べている。しかし、本発明は具体的詳細を知らなくても実施できることは明白であろう。他の場合には、本発明を説明しやすくするために、よく知られている構造およびデバイスがブロック図形式で示されている。
【００１６】
本出願で使用されているように、「コンポーネント」、「ハンドラ」、「モデル」、「システム」などの用語は、コンピュータ関連のエンティティ、つまりハードウェア、ハードウェアとソフトウェアの組み合わせ、ソフトウェア、または実行中のソフトウェアのいずれかを指すことを意図されている。例えば、コンポーネントとして、プロセッサ上で実行されているプロセス、プロセッサ、オブジェクト、実行可能ファイル、実行のスレッド、プログラム、および／またはコンピュータなどがある。例示するため、サーバ上で実行されているアプリケーションとサーバは両方ともコンポーネントであってよい。１つまたは複数のコンポーネントを１つのプロセスおよび／または実行スレッド内に常駐させることができ、またコンポーネントを１台のコンピュータにローカルとして配置し、および／または２台以上のコンピュータ間に分散させることができる。また、これらのコンポーネントは、さまざまなデータ構造を格納するさまざまなコンピュータ可読媒体から実行することができる。これらのコンポーネントは、１つまたは複数のデータパケット（例えば、ローカルシステム、分散システム、および／または信号を介した他のシステムとのインターネットなどのネットワーク上で他のコンポーネントと相互にやり取りする一方のコンポーネントからのデータ）を伴う信号を使うなどするローカルおよび／またはリモートプロセスを介して通信することができる。
【００１７】
次に図１を参照すると、印刷されたドキュメントのデジタル化されたイメージに少なくとも一部は基づいてドキュメントのオンライン版の自動インデックス作成および／または読み込みを容易にするシステム１００が例示されている。オンラインドキュメントは、出所をワードプロセッサまたはその他の類似するタイピングアプリケーション、またはその代わりにペンおよびタッチセンシティブスクリーンとすることができることは理解されるであろう。システム１００を使って、ドキュメント内に現れる単語のトポロギーのプロパティを利用することにより、印刷されたドキュメントをそのようなドキュメントのオンライン版と比較することができる。システム１００は、データストア１０４内に常駐するオンラインドキュメントのイメージ１０３を生成することを容易にするキャッシングコンポーネント１０２を備える。ドキュメントのオンライン版のイメージ１０３は、データストア１０４に格納され、これにより、そのようなイメージとともに他の関連するデータ（例えば、ドキュメントのオンライン版、ドキュメントのオンライン版の場所を識別するリンクのＵＲＬ、木表現（以下で詳述する）など）を後で取り出すことができる。例えば、キャッシングコンポーネント１０２は、ユーザがそのようなドキュメントを印刷する際にドキュメントのオンラインイメージ１０３を自動的に生成し、その後、ドキュメントのオンライン版のイメージ１０３をデータストア１０４に中継するプリントドライバとすることができる。したがって、ドキュメントが印刷されるのと実質的に類似したタイミングで、ドキュメントのビットマップ（またはその他の適当なファイル形式）が、キャッシングコンポーネント１０２を介して生成され、ドキュメントのオンライン版のイメージ１０４および／またはその他の関連する情報がデータストア１０４内に格納される。本発明の他の態様によれば、イメージを生成する特定のドキュメントを選択するためにユーザが使用することができるユーザインターフェースを提供することができる。例えば、キャッシュコンポーネント１０２の自動イメージ生成機能のオンおよび／またはオフの切り替えを行うためのコンポーネント（例えば、「ファイルへ出力」印刷オプションと似ている）を備えることができる。
【００１８】
したがって、データストア１０４は、複数のオンラインドキュメントのイメージ１０３を格納し、オンラインドキュメントのそれぞれのイメージはすでに印刷されているドキュメント１０６の少なくとも一部に対応する。例えば、それぞれのイメージ１０３は、ドキュメント１０６の個々のページに対応付けることができる。印刷されたドキュメント１０６がそのような印刷されたドキュメント１０６の素性をユーザに知らせる明示的な情報を含まない場合、システム１００を使用して、データストア１０４内の対応するイメージ１０３を特定することができる。例えば、印刷されたドキュメント１０６が会合で配布され、会合の出席者が修正事項を追加するドキュメントのオンライン版を特定したい場合がある。同様に、ユーザは、印刷されたドキュメント１０６にさまざまな注釈を施したが、単純にドキュメント１０６にそのような注釈を含まないドキュメントが欲しい場合がある。印刷されたドキュメント１０６のデジタルイメージ１０８は、スキャナ、デジタルカメラ、またはその他の適当なデバイスを介して取得することができる。デジタルイメージ１０８を受け取った後、検索コンポーネント１１０は、データストア１０４を検索して、印刷されたドキュメント１０６のオンライン版の対応するイメージ１０３を特定する。
【００１９】
検索コンポーネント１１０は、キャッシングコンポーネント１０２を介して生成されたイメージ１０３を受け取り、キャッシングコンポーネント１０２を介して生成されたそれぞれのオンラインイメージ１０３に関係する署名１１４の作成を容易にする署名生成コンポーネント１１２を備える。署名生成コンポーネント１１２は、さらに、デジタルイメージ１０８を受け取り、それに関する署名１１６を生成する。本発明の一態様により、署名生成コンポーネント１１２は、オンラインドキュメントのイメージ１０３の署名１１４を、イメージをデータストア１０４に格納しながら生成することができる（例えば、キャッシングコンポーネント１０２は、イメージ１０３がデータストア１０４に中継されるのと実質的に類似したタイミングで、デジタルイメージ１０３を署名生成コンポーネント１１２に中継することができる）。このような実施形態は、署名１１４がすでに生成されており、署名１１４を生成するのに要する処理時間が不要になるので、データストア１０４を検索するのに要する時間を短縮するという利点を持つ。本発明の他の態様によれば、署名生成コンポーネント１０４は、データストア１０４がロードされる毎に署名１１４を生成することができる。この実施例だと、オンラインドキュメントの格納されているイメージ１０３の署名１１４用のメモリを連続して割り当てる必要がないため、データストア１０４内の格納スペースを節約できるであろう。前述の実施例から、署名生成コンポーネント１１２は、キャッシングコンポーネント１０２を介してイメージを受け取った後、適当な時期にオンラインドキュメントのイメージ１０３に対する署名１１４を生成するために使用することができ、上述の実施例は本発明の範囲を限定することを意図していないことは理解されるであろう。
【００２０】
署名生成コンポーネント１１２は、オンラインドキュメントのイメージ１０３内の単語のトポロギーのプロパティに少なくとも一部は基づきデータストア１０４内のオンラインドキュメントのイメージ１０３の署名１１４を生成する。例えば、単語のジオメトリは、そのような単語を含むドキュメントの署名を生成するために使用することができる。単語のトポロギーのプロパティに基づいて署名１１４を生成することは、単語は通常低い解像度では異なる単語と衝突しないため（個々の文字は低い解像度だと融合する可能性が高い）、従来のシステムに対する改善となっている。さらに、文字の特性と比較して単語のトポロギーのプロパティに基づきそのような署名１１４を生成するのに要する時間が短くて済むが、本発明を利用することで得られる迅速さの向上と引き換えに精度が損なわれる。２つの異なるドキュメント同士の単語のレイアウトが実質的に類似している可能性はかなり小さいため、精度は悪影響を受けない。
【００２１】
オンラインドキュメントのイメージ１０３内の単語のトポロギーのプロパティは、キャッシングコンポーネント１０２を介して生成されたオンラインイメージ１０３を拡張することにより得られ、それによって、異なる単語が衝突しない形で、単語の文字が融合するようにできる。イメージを拡張するとは、異なる単語を融合させずに単語の文字を融合させる適当な方法を指す。例えば、イメージ１０３の解像度は、単語の個々の文字が互いにつながるまで変えることができる。より具体的には、生成されたイメージを２値化し、複数の単語内のつながっている構成要素を計算することができる。その後、そのような、つながっている構成要素を拡張し、単語の中の文字を結合する。本発明の一態様によれば、キャッシングコンポーネント１０２を介して生成されたイメージを拡張した後、署名１１４は、イメージ１０３内の結果として得られた単語ブロックの幾何学的特性に基づいて生成される。例えば、イメージ１０３の複数のピクセルをＸ−Ｙ座標で表し、単語の場所をそのような座標（ピクセル）に基づいて定義することができる。署名生成コンポーネント１１２が署名１１４を生成するのに要する処理時間を最短にするために、イメージ内の単語の場所をＸ−Ｙ座標によりそのような単語の特定の幾何学的位置に定義することができる。例えば、それぞれの単語の位置は、単語の特定の角のＸ−Ｙ位置により定義することができる（例えば、Ｘ−Ｙ位置は、それぞれの単語の左上角に関して定めることができる）。単語の幅もまた、異なるドキュメントの単語レイアウトをさらに定義するために使用することができる。したがって、本発明の一態様によれば、署名生成コンポーネント１１２は、イメージ１０３内の単語のＸおよびＹ座標、および単語の幅Ｗに少なくとも一部は基づき署名１１４を生成することができる。例えば、１つまたは複数の機能を使用し、イメージ内の単語のＸ、Ｙ、およびＷ座標に基づき、イメージに関係する署名を生成することができる。より具体的には、署名生成コンポーネント１１２は、オンラインドキュメント１０３のイメージ内にある単語のＸ、Ｙ、およびＷ座標を使用することにより、データストア１０４内のオンラインドキュメントのそれぞれのイメージ１０３に対しハッシュテーブルを生成することができる。しかし、署名生成コンポーネント１１２を使用して、異なるイメージの区別および／または印刷されたドキュメント１０６に実質的に類似しているイメージの検索および読み込みを行うことができる適当な署名１１４を作成することができることは理解されるであろう。
【００２２】
本発明の他の態様によれば、署名生成コンポーネント１１２は、データストア１０４内のオンラインドキュメントのイメージ１０３の署名１１４を生成するとき発生しうる誤りを考慮することができる。例えば、印刷されたドキュメント１０６がスキャンされるか、またはデジタルカメラにより写真撮影された場合、その結果得られるイメージ１０８は、データストア１０４内のドキュメント１０６の対応するオンラインイメージと比較して、平行移動および／または回転することができる。署名生成コンポーネント１１２で平行移動および／または回転の誤差を考慮する方法例を示すために、Ｘ、Ｙ、およびＷ座標を使用して署名１１４を生成する際に誤差の大きさのしきい値を考慮することができる。より具体的には、配列［Ｘ＋ｃ，Ｘ−ｃ］、［Ｙ＋ｄ，Ｙ−ｄ］、および［Ｗ＋ｅ，Ｗ−ｅ］を使用して、署名を生成することができるが、この場合、ＸおよびＹは１つの単語の少なくとも一部の位置を示し、Ｗは単語の幅であり、ｃはｘ方向の許容誤差であり、ｄはｙ方向の許容誤差であり、ｅは単語の幅に対する許容誤差である。したがって、配列内の値の組み合わせで、単語の位置および幅を示すことができる（例えば、（Ｘ＋ｃ，Ｙ−ｄ，Ｗ＋ｅ）は（Ｘ，Ｙ，Ｗ）の実際の位置および幅を持つ単語の位置および幅を示すことが可能である）。したがって、署名生成コンポーネント１１２は、印刷されたドキュメント１０６のデジタルイメージ１０８を取得する際に生じる可能性のある誤差を考慮しつつ、単語レベルのトポロギーのプロパティを使用して、データストア１０４内に格納されているオンラインドキュメントのイメージ１０３の署名１１４を生成することができる。本発明の他の態様によれば、前処理手法を使用して、デジタルイメージ１０８に内在する平行移動および／または回転を緩和することができる。より具体的には、すべての単語（例えば、つながっている構成要素）の中間地点を決定することにより平行移動を緩和し、エントロピーが十分に最小化されるまでつながっている構成要素を射影することにより所望の水平方向を特定することができる。さらに、水平方向における一致を１８０度で完了させ、さらに回転および／または平行移動誤差を制限することができる。
【００２３】
署名生成コンポーネント１１２は、署名１１４が生成されるのとほぼ同じ方法で印刷されたドキュメント１０６のデジタルイメージ１０８の署名１１６を作成することができる。デジタルイメージ１０８の解像度は、署名生成コンポーネント１１２でデジタルイメージ１０８の単語レベルのトポロギーのプロパティを取得するために必要な場合に変更することができる。例えば、デジタルイメージ１０８の解像度を変更し、デジタルイメージ１０８内の単語の特定の部分の位置（例えば、左上角）をＸおよびＹ座標により定義することができる。その後、単語の幅Ｗを使用して、単語をさらに定義することができる。したがって、Ｘ、Ｙ、およびＷの値は、デジタルイメージ１０８内の単語毎に存在し、署名生成コンポーネント１１２では、デジタルイメージ１０８内の単語のＸ、Ｙ、およびＷ値に少なくとも一部は基づきイメージ１０８の署名を生成することができる。キャッシングコンポーネント１０２を介して生成されたイメージの署名１１４内であり得る平行移動および／または回転誤差はすでに考慮されているため、これ以上署名１１６内のそのような誤差を考慮する必要はないと思われる。しかし、本発明では、署名１１４および１１６の両方で生じうる誤差を考慮すること、署名１１４および１１６のいずれかで生じうる誤差を考慮すること、および署名１１４および１１６のいずれでも誤差を考慮しないことを考察している。本発明の他の態様により、回転されたドキュメントの署名を生成して、データストア１０４内に格納することができる。例えば、オンラインドキュメントのイメージ１０３に関係する署名が生成され、格納された場合、署名生成コンポーネント１１２は、そのドキュメントに対し回転および／または平行移動が行われているかのように署名を生成することができる。
【００２４】
署名１１４および１１６が署名生成コンポーネント１１２により生成された後、データストア１０４内に格納されているオンラインドキュメントに関係する署名１１４の少なくとも一部は、印刷されたドキュメント１０６のデジタルイメージ１０８に関係する署名１１６と実質的に一致していなければならない。検索コンポーネント１１０は、署名１１６および署名１１４を受け取り、署名１１６と署名１１４とを比較する比較コンポーネント１１８を備える。例えば、署名１１４および１１６がハッシュテーブルの場合、比較コンポーネント１１８は、キャッシュされているイメージに対応するハッシュテーブルのエントリとデジタルイメージ１０８に対応するハッシュテーブルのエントリとの一致回数をカウントすることができる。その後、比較コンポーネント１１８は、署名１１６との一致回数が最大である署名１１４に関係するオンラインドキュメントを返すことができる。そうする代わりに、比較コンポーネント１１８は、署名１１６の特定の部分内で一致の割合が最高である署名１１４に関係するドキュメントを返すことができる（例えば、印刷されたドキュメント１０６の一部が破られており、それらの署名の部分間での一致の割合が最良のドキュメントを示すことができる）。さらに、署名１１４に存在する情報が不十分な場合、比較コンポーネント１１８はそのような十分な情報の欠如をユーザに知らせることができる。
【００２５】
本発明の特定の一態様によれば、比較コンポーネント１１８は、署名１１４と署名１１６との多層比較を実行することができる。そのような多層検索は、オンラインドキュメントのかなりの量のイメージがデータストア１０４内に格納されている場合に有益である。例えば、署名１１４の一部のみを署名１１６の実質的に類似している部分と比較することができる。署名１１４および１１６のそのような部分同士の間に一致が存在する場合、後で考慮できるようにそれらの署名１１４は保持される。その部分内に一致１１６のない署名１１４は除外されそれ以上考慮されない。これ以降、署名１１４の小さい方の部分と署名１１６の著しく小さい方の部分とを比較して、その小さい部分内での署名１１６との一致を含む署名１１４が考慮されるようになるが、署名１１６との一致を含まない署名１１４は除外される。署名１１４および１１６の分割は、しきい値で定められた数の署名１１４が残るまで繰り返すことができる。それ以降、比較コンポーネント１１８は、残りの署名１１４のうちどれについて署名１１６との一致の数が最高であるか、および／または最高のパーセンテージであるかを判別することができる。本発明の他の態様によれば、署名１１６との一致の数および／またはパーセンテージが最高である署名１０４に関係するオンラインドキュメントがユーザに返される。例えば、ドキュメントが印刷されたときに存在していたドキュメントのオンライン版をユーザに返すことができる。さらに、ＵＲＬおよび／またはリターンパスをユーザに与え、ドキュメントの印刷時に存在していたドキュメントのオンライン版をそのようなユーザが取得することが可能であるようにできる。
【００２６】
本発明の一態様によれば、データストア１０４を使用することにより、オンラインドキュメントのイメージ１０３だけでなくイメージ１０３に関連付けられている他のデータをも少なくとも一時的に格納することができる。例えば、そのデータストア１０４は、概念上、リレーショナルデータベースとすることができるが、ユーザによって印刷されたページに関係するページイメージは、主たるエンティティとみなすことができる。この後、イメージ１１４の署名、イメージ１０３の階層木表現（以下で詳述する）、イメージ１０３の１つに対応するドキュメントのオンライン版の場所を識別するＵＲＬ、対応するイメージ１０３が印刷されたときに存在していたドキュメントのオンライン版（例えば、そのようなドキュメントがそれ以降修正されていた場合に望ましい）、およびその他の適当な情報など、複数の異なるデータをイメージ１０３に関連付けることができる。しかし、本発明では、他の実施形態が考察されており、付属の請求項の範囲内に置かれることを意図されている。例えば、格納スペースが異常に高額であり、それぞれの印刷ページのオンラインイメージを永続的に格納しておくと費用がかかることがある。このような場合、オンラインイメージ１０３を生成して、一時的に格納し、署名１１４を生成するようにできる。その後、署名１１４は、一次エンティティとなり、ドキュメントのオンライン版（またはドキュメントのイメージ）を取得するために使用することができるＵＲＬまたはその他の情報を関連付けることができる。
【００２７】
次に図２を参照すると、そのような印刷されたドキュメントの後で取得されるイメージに少なくとも一部は基づくドキュメントが印刷されたときに存在していた印刷されたドキュメントのオンライン版の自動インデックス作成のおよび／または読み込みを容易にするシステム２００が例示されている。システム２００は、オンラインドキュメントのオンラインイメージ２０４を自動生成し、そのようなイメージ２０４をデータストア２０６に中継するキャッシングコンポーネント２０２を含む。本発明の一態様によれば、キャッシングコンポーネント２０２はドキュメントのデジタルイメージ２０４を生成し、ドキュメントが印刷されるのと実質的に類似したタイミングでイメージ２０４を格納することができる。したがって、それぞれの印刷されたドキュメント（例えば、すべての印刷されたドキュメントの各ページ）の少なくとも一部は、データストア２０６内に相関関係のあるイメージ２０４を持つことができる。キャッシングコンポーネント２０２は、さらに、データストア２０６内、またはコンピュータ内の他の格納場所に格納されているそれぞれのオンラインドキュメントのデジタルイメージ２０４を生成することもできる。さらに、人工知能コンポーネント２０８をキャッシングコンポーネント２０２とともに使用することにより、キャッシングコンポーネント２０２を介して生成されたそのようなドキュメントのイメージ１０３を含むオンラインドキュメントはどれであるかを判別することもできる。例えば、人工知能コンポーネント２０８は、どのオンラインドキュメントにおいて関係のあるイメージを生成すべきであるかを推論することができる。
【００２８】
本明細書で使用しているように、「推論」という用語は、一般に、イベントおよび／またはデータを介して得られるような一組の観察結果から、システム、環境、および／またはユーザの状態を推理または推論するプロセスを指す。推論を使用して特定のコンテキストまたはアクションを識別したり、例えば複数の状態について確率分布を求めることができる。推論は確率的であってよい、つまり、データおよびイベントの考察に基づいて注目している状態に関する確率分布を計算することができる。推論は、さらに、一組のイベントおよび／またはデータから高水準のイベントを構成するために使用される手法を指す場合もある。このような推論を行うことで、イベント同士が時間的に近い関係による相関関係があるかどうか、またイベントおよびデータが１つまたは複数のイベントおよびデータソースを発生元としているかどうかに関係なく、一組の観察されたイベントおよび／または格納されているイベントデータから新しいイベントまたはアクションが構築される。さまざまな分類スキームおよび／またはシステム（例えば、ベクトルマシン、ニューラルネットワーク、エキスパートシステム、ベイジアン信念ネットワーク（Ｂａｙｅｓｉａｎ  ｂｅｌｉｅｆ  ｎｅｔｗｏｒｋｓ）、ファジー論理、データフュージョンエンジン（ｄａｔａ  ｆｕｓｉｏｎ  ｅｎｇｉｎｅｓ）などをサポートする）を、主題の発明に関する自動および／または推論アクションを実行することに関連して使用することができる。
【００２９】
例えば、人工知能コンポーネント２０８は、長時間にわたってユーザを観察し、特定のユーザ状態およびコンテキストを与えた場合にユーザが通常どのドキュメントをキャッシュするかを「学習する」ことができる。より具体的には、人工知能コンポーネント２０８は、ユーザが生成したいのは、特定のプログラム（例えば、Ｍｉｃｒｏｓｏｆｔ  Ｗｏｒｄ（登録商標））で作成および／または保存したドキュメントのイメージだけであると推論することができる。他の実施例では、人工知能コンポーネント２０８は、ユーザが望んでいるのは、特定の時刻および／または曜日に印刷されたドキュメントのイメージを生成することだけである、またはユーザが望んでいるのは、特定の命名規則でドキュメントのイメージを生成することだけであることを「学習する」ことができる。したがって、人工知能コンポーネント２０８は、データストア２０６に必要な格納スペースの量を減らすとともに、データストア２０６を検索するのに要する時間を短縮することができる（例えば、検索するオンラインドキュメントのイメージ２０４は少ないので）。
【００３０】
データストア２０６内で、印刷されたドキュメント２１４のデジタルイメージ２１２と実質的に類似しているオンラインドキュメントのイメージ２０４の検索を簡単に行えるようにする検索コンポーネント２１０が用意されている。検索コンポーネント２１０は、生成されたイメージを受け取り、生成されたイメージの署名２１８を作成するだけでなく、印刷されたドキュメント２１４のデジタルイメージ２１２を受け取り、それに関係する署名２２０を生成する署名生成コンポーネント２１６を含む。署名２１８および２２０は、単語レベルのトポロギーのプロパティに基づいて生成される。例えば、キャッシングコンポーネントを介して生成されたイメージ２０４およびデジタルイメージ２１２の解像度を変更して、異なる単語を融合することなく単語の文字を融合させることができる。その後、それぞれの単語は、それぞれの単語のイメージおよび幅の範囲のＸ−Ｙ座標により識別することができる。これらの座標は、署名生成コンポーネント２１６により、データストア２０６内のオンラインドキュメントのそれぞれのイメージ２０４に関係付けられた署名だけでなく、オンラインドキュメントの複数のイメージ２０４のうちの１つに関係付けられている署名に実質的に類似している署名２２０を生成するために使用することができる。さらに、署名２１８および／または署名２２０では、印刷されたドキュメント２１４をデジタル化するときに発生しうる平行移動および／または回転誤差を考慮することができる。署名生成コンポーネント２１６は、さらに、１つまたは複数の機能に関連して前述の座標および幅を使用することにより、署名２１８および／または２２０として働くハッシュテーブルを生成することもできる。
【００３１】
本発明の他の態様では、人工知能コンポーネント２０８は、署名生成コンポーネント２１６とともに動作し、キャッシングコンポーネントによりデータストア２０６にイメージ２０４が格納され、署名生成コンポーネント２１６により署名２１８が生成される特定のオンラインドキュメントを判別することができる。例えば、特定のユーザ状態およびコンテキストが与えられた場合、人工知能コンポーネント２０８は、印刷されたオンラインドキュメントのサブセットのみにおいて対応するイメージ２０４が格納され署名が生成されることを推論することができる。より具体的には、ユーザは、通常、特定の処理プログラムで生成されたオンラインドキュメントのインデックス作成および／または読み込みを試みることができる。したがって、人工知能コンポーネント２０８は、そのような処理プログラムで作成されたオンラインドキュメントのみを処理するようにキャッシングコンポーネント２０２および署名生成コンポーネント２１６に通知することができる。
【００３２】
署名生成コンポーネント２１６が署名を生成した後、比較コンポーネント２２２は、署名２１８および２２０を受け取り、オンラインドキュメントのイメージ２０４に関係付けられている署名２１８とデジタルイメージ２１２の署名２２０とを比較する。デジタルイメージ２１２の署名２２０に最も実質的に一致する署名２１８からの署名が、比較コンポーネント２２２により特定され、そのような署名に対応するオンラインドキュメントがユーザに返される。例えば、比較コンポーネント２２２は、対応する署名２１８および２２０を比較することにより印刷されたドキュメント２１４のデジタルイメージ２１２と最もよく一致するデータストア２０６内のオンラインドキュメントのイメージ２０４を特定する。この後、最もよく一致するイメージ２０４に関連付けられているＵＲＬおよび／またはその他の情報を取得し、ユーザに返すことができる。ドキュメントのオンライン版がデータストア２０６内に格納されていない場合、ドキュメントのオンライン版の場所をユーザに知らせるＵＲＬおよび／またはその他の情報をユーザに返すことができる。ドキュメントのオンライン版がデータストア２０６内に格納されている場合、そのようなドキュメントは直接ユーザに中継することができる。本発明の一態様によれば、比較コンポーネント２２２は、署名２２０に最も実質的に一致する署名２１８のうちの１つの署名を特定するために多層比較手法を使用することができる。例えば、署名２１８の一部のみを、署名２２０の実質的に類似している部分に突き合わせて比較することができる。署名２１８および２２０のさらに小さく分割した部分を、しきい値で定められた数の署名２１８が考察のため残るまで繰り返すことができる。この後、署名２１８の残りのサブセットについては、署名２２０と突き合わせて詳しく比較することができる。そうする代わりに、署名２１８の残りのサブセットは、署名２２０とランダムにスポットチェックすることができる（例えば、署名２１８の残りのサブセットのランダムな部分を署名２２０の実質的に類似しているランダム部分と突き合わせて比較することができる）。
【００３３】
次に図３を参照すると、印刷されたドキュメントのデジタルイメージに少なくとも一部は基づき格納されているオンラインドキュメントの自動インデックス作成および／または読み込みを行うための方法３００が例示されている。説明を簡単にするために、方法３００を図に示し、一連の活動として記述するが、本発明は活動の順序によって制限されるわけではなく、本発明により、いくつかの活動はその図に示されているここで説明しているのと異なる順序でおよび／または他の活動と同時に実行することも可能である。例えば、当業者であれば、方法を代わりに一連の相互に関連のある状態またはイベントとして状態図などの中に表すことが可能であることを理解し、認識するであろう。さらに、本発明により、方法を実装するために例示されているすべての活動が必要なわけではない。
【００３４】
３０２で、ドキュメントのハードコピーが印刷される。３０４で、印刷されたドキュメントの少なくとも一部のイメージが生成される。例えば、番号ＮのイメージをＮページあるドキュメントについて生成することができ、その場合、それぞれのページには、イメージが関連付けられている。本発明の一態様によれば、プリントドライバを使用して、ドキュメントを印刷しつつドキュメントのイメージを自動生成することができる（例えば、「ファイルへプリント」オプションに類似している）。さらに、それぞれのオンラインでドキュメントのイメージは、ドキュメントを印刷するのに先立って生成し、格納することができる。したがって、印刷されるドキュメントに関して、データストア内に対応するデジタルイメージが存在する。３０５で、印刷されたドキュメントのデジタルイメージが作成される。例えば、デジタルカメラまたはスキャナは、印刷されたドキュメントのデジタルイメージを生成するために使用することができる。３０６で、生成されたデジタルイメージの解像度およびデジタルカメラまたはスキャナを介して得られた印刷されたドキュメントのデジタルイメージの解像度は、印刷されたドキュメントのデジタルイメージをデータストア内のオンラインドキュメントのイメージのうちの１つと照合することに関して単語レベルのトポロギーのプロパティを簡単に使用できるように変更される。例えば、イメージは拡張され、それによって、個々の文字は融合して１つにまとめられるが、異なる単語はつながることはない。デジタルカメラまたはスキャナにより取り込まれたイメージの解像度が、すでに、十分に低い場合、解像度の調整は不要である。
【００３５】
３０８で、データストア内に格納されているそれぞれの生成されたイメージについて署名が１つ生成され、そこで、署名はイメージの単語レイアウトを使用して、そのような署名が一意であることを確実にする。例えば、各単語の特定の部分の位置（例えば、角）は、単語のそのような部分のＸ−Ｙ座標により定義することができる。さらに、単語の幅もまた、それぞれのドキュメントの単語レイアウトをさらに定義するために使用することができる。２つの異なるドキュメントが同一の単語レイアウトを持つ確率はかなり小さいため、単語レイアウトを定義するこれらのＸ、Ｙおよび幅の値は、それぞれのドキュメントを識別する署名を生成するために効果的に使用することができる。本発明の一態様によれば、生成される署名はハッシュテーブルとすることができる。ハッシュテーブルは、サイズの面で、またユーザが照合のスピードと照合の確実さとの効率的な妥協点を見つけられるという点で望ましいといえる。さらに、しきい値の大きさの誤差を定義することができ、生成された署名ではそのような誤差を考慮することができる。例えば、平行移動および／または回転誤差は、印刷されたドキュメントのデジタルイメージを取り込む際に発生しうる（例えば、デジタルカメラでドキュメントを写真撮影する場合）。取り込まれたドキュメントの署名におけるこのような誤差の発生可能性を考慮することにより、そのような誤差のためデータストア内で印刷されたドキュメントのデジタルイメージに実質的に一致する特定のイメージを見つけられないという事態にならないようにできる。
【００３６】
３１０で、印刷されたドキュメントのイメージの署名が生成される。このような署名は、格納されているイメージの署名がステップ３０８で生成されたのと実質的に類似している方法により生成される。署名生成におけるこのような整合性により、署名生成および／または署名照合において両方とも最適な効率を達成できる。例えば、格納されているイメージの署名がハッシュテーブルである場合、デジタルイメージの署名も、ハッシュテーブルとすることができ、それにより、そのようなハッシュテーブル間の比較を効率的に行うことができる。さらに、平行移動および／または回転誤差も格納されているイメージの署名内で考慮されているため、印刷されたドキュメントのデジタルイメージの署名で再びそのような誤差を考慮することは望ましくないであろう。
【００３７】
３１２で、３０８と３１０でそれぞれ生成された署名を比較し、印刷されたドキュメントのデジタルイメージの署名と最もよく一致するオンラインドキュメントの署名を判別する。例えば、署名がハッシュテーブルであれば、印刷されたドキュメントのイメージに関係するハッシュテーブルの各エントリを格納されているイメージに関係するすべてのハッシュテーブルの各エントリと比較することができる。その後、印刷されたドキュメントのデジタルイメージのハッシュテーブルとの一致回数が最も多い格納されているイメージのハッシュテーブルを使用して、そのようなハッシュテーブルに関係するオンラインドキュメントをユーザに返すことができる。より具体的には、印刷されたドキュメントの後から取得されたイメージと最もよく一致するオンラインドキュメントの格納されているイメージを特定するために、署名同士を比較する。その後、オンラインドキュメントの場所を識別するＵＲＬまたはその他の適当なメカニズムを取得し、ユーザに返すことができる。しかし、ハッシュテーブル内で１行ずつ照合すると、データストア内に格納されているイメージが多い（したがって、そのようなイメージに関係する署名が多数存在する）場合にはかなりの時間を要する可能性がある。そこで、本発明の他の態様によれば、印刷されたドキュメントのデジタルイメージの署名の一部とデータストア内のオンラインドキュメントのイメージに関係付けられている署名の実質的に類似している部分とを比較することができる。その後、その部分の中にある印刷されたドキュメントのデジタルイメージの署名との１つまたは複数の一致が含まれるオンラインドキュメントのイメージの署名が、さらに考慮できるように保持されるが、印刷されたドキュメントのデジタルイメージの署名との一致がない格納されているイメージの署名は、それ以上考慮されない。その後、署名の繰り返し小さくなって行く部分を、しきい値であらかじめ定義されている個数の署名が残るまで、考慮される署名の数を実際に減らして行くのと実質的に似た方法で比較することができる。そのような残りの署名は、印刷されたドキュメントのデジタルイメージの署名と徹底的に比較することができる。
【００３８】
さらに、排他的検索を使用すれば、ドキュメントの印刷版に基づき印刷されたドキュメントのオンライン版の特定作業を高速化することができる。例えば、オンラインドキュメントから生成されたイメージに対応する木表現だけでなく印刷されたドキュメント取り込まれたイメージに対する木表現をも生成することができる。より具体的には、それぞれのイメージ（生成され格納されているイメージおよび取り込まれたイメージ）は、異なる数のセグメントに分割することができる。その後、１つの単語を含むそれぞれのセグメントにある値（例えば、１）を割り当て、単語を含まないそれぞれのセグメントに違う値（例えば、０）を割り当てることができる。それぞれのセグメントは、さらに、小さなセグメントに分割し、再び、１つの単語を含むそれぞれのセグメントにある値を割り当て、単語を含まないそれぞれのセグメントに違う値を割り当てることができる。それぞれのセグメントは、望ましい個数のセグメントが作成されるまで分割することができ、その際に、それぞれのセグメントは、セグメント内に単語が存在するかどうかに応じて値が割り当てられる。したがって、階層が生成され、そこでは、それぞれのセグメントは、階層内の特定のレベルに関連付けられる。例えば、ドキュメント全体は階層の最上位レベルにあり、第１のセグメント分割は階層の第２レベルに関係付けられ、第２のセグメント分割は階層の第３レベルに関係付けられ、というように構成される。この木表現は、イメージに関係する署名が生成されるのと実質的に類似のタイミングで生成され格納されるようにできる。署名の比較に先立って、オンラインドキュメントに関係付けられている木表現と印刷されたドキュメントの取り込まれたイメージとを比較し、印刷されたドキュメントのイメージと照合できないオンラインドキュメントの格納されているイメージを素早く破棄することができる。例えば、取り込まれたイメージのセグメントが１つの単語を含み、生成され／格納されたイメージの対応するセグメントは単語を含まない場合、生成され／格納されているイメージをそれ以降の考慮の対象から外すことができる。しかし、生成され／格納されたイメージのセグメントが単語を含み、取り込まれたイメージの対応するセグメントが単語を含まない場合、例えば印刷されたドキュメントが一部破られているためなので、生成され／格納されているイメージは破棄されず、本当なら単語を含んでいたであろうセグメントはそのような破れのせいで取り込まれたイメージ内に反映されないことは理解されるであろう。イメージ（生成されたイメージおよび取り込まれたイメージ）の木表現を利用することにより、比較のため考慮すべき署名の数を減らすことができ、それによって、そのようなドキュメントの取り込まれたイメージに基づいてオンラインドキュメントを特定するのに要する時間を短縮することができる。
【００３９】
３１４で、データストアに格納されている署名の少なくともサブセットと印刷されたドキュメントのデジタルイメージに関係する署名との一致の信頼度に関して判定が行われる。高い信頼度の一致が存在する場合、３１６で、一致する署名に対応するオンラインドキュメントがユーザに返される。より具体的には、印刷されたドキュメントの後から取得されたイメージと最もよく一致するオンラインドキュメントの格納されているイメージを特定するために、署名同士を比較する。その後、オンラインドキュメントの場所を識別するＵＲＬまたはその他の適当なメカニズムを取得し、ユーザに返すことができる。信頼度しきい値を超える一致が存在しない場合、３１８で、多層比較方式を使用してドキュメント比較したかどうかに関する判定が行われる。多層比較を使用しなかった場合、３２０で、ユーザに対し、高い信頼度の一致が存在しないことが通知される。多層比較方式を使用する場合、３２２で、データストア内のオンラインドキュメントのイメージに関係付けられている署名のすべての部分と印刷されたドキュメントのイメージの署名の有効なすべての部分との比較が行われたかどうかに関して判定される。印刷されたドキュメントのイメージの署名は、無効な部分を含むことがあり（例えば、物理的な損傷および／またはノイズの除去により生じる署名のギャップ）、したがって、それらの無効な部分とオンラインドキュメントのイメージに関係付けられている署名との比較は有益ではないであろう。すべての部分がチェックされた場合、３２０で、ユーザに対し、高い信頼度の一致が存在しないことが通知される。そうでない場合、３２４で、署名の異なる部分を使用して、署名同士を比較し、実質的な一致が存在しないことを確認することができる。そのような方式は、印刷されたドキュメントの一部が印刷時に破れてしまい、印刷されたドキュメントの署名の少なくとも一部が印刷されたドキュメントのオンライン版のイメージに関係付けられている署名の対応する部分と実質的に一致しなくなっている場合に有効である。したがって、署名の異なる部分を選択し、そのような署名の比較にそれほど時間をかけることなく署名の比較の効率を維持することができる。次に、３１２で、印刷されたドキュメントのイメージの署名のこの異なる部分は、オンラインドキュメントのイメージに関係付けられている署名の対応する部分と比較される。高信頼度一致が見つかった場合、３１６で、印刷されたドキュメントのイメージの署名との一致が最も高い信頼度の一致である署名に対応するオンラインドキュメントがユーザに返される。より具体的には、印刷されたドキュメントの後から取得されたイメージと最もよく一致するオンラインドキュメントの格納されているイメージを特定するために、署名同士を比較する。その後、オンラインドキュメントの場所を識別するＵＲＬまたはその他の適当なメカニズムを取得し、ユーザに返すことができる。
【００４０】
次に図４を参照すると、印刷されたドキュメントの取り込まれたイメージに少なくとも一部は基づいて印刷されたドキュメントのオンライン版の自動インデックス作成および／または読み込みを容易にするシステム４００が例示されている。システム４００は、オンラインドキュメントの少なくとも一部のイメージ４０４を自動生成するキャッシングコンポーネント４０２を備える。例えば、イメージ４０４は、オンラインドキュメントのページ毎に生成され、データストア４０６に順次格納されるようにできる。本発明の一態様によれば、キャッシングコンポーネント４０２は、ドキュメントが印刷されるときに必ずオンラインドキュメントの少なくとも一部のイメージ４０４を生成し格納する。したがって、印刷されたドキュメントのページ毎に、ドキュメントのそのようなページの対応するイメージ４０４は生成された後、少なくとも一時的に格納される。ドキュメント４０４のオンライン版のそれらのイメージ４０４は、データストア４０６内に格納される。印刷されたドキュメントの少なくとも一部（例えば、１ページ）のオンラインイメージ４１０を作成するために、デジタルカメラ、スキャナ、またはその他の適当なメカニズムを使用することができる。ノイズ低減コンポーネント４１２は、オンラインイメージ４１０を受け取るが、このコンポーネントはオンラインイメージ４１０内に存在する望ましくないマーキングおよびその他のノイズを低減するために用意される。ノイズ低減コンポーネント４１２は、対応するオンラインドキュメントのイメージ４０４内には存在していない不要なマーキングを除去するフィルタ４１４に関連付けられている。例えば、フィルタ４１４を使用すると、アンダーライン、逸脱したマーキング、およびその他の類似の注釈を簡単に除去することができる。同様に、フィルタ４１４は、オンラインイメージ４１０内の特定の色を探索し、そのような色のレンダリングおよび／またはマーキングを除去することができる。ノイズ低減コンポーネント４１２は、さらに、ノイズ低減を容易に行えるようにドキュメントの色を自動的に調整するグレースケールコンポーネント４１６も備えることができる。例えば、ドキュメントを黄色の用紙に印刷する場合があるが、そのようなドキュメントのイメージ４０４の背景色が白である場合である。したがって、グレースケールコンポーネント４１６は、イメージ４１０の色を変更し、格納されているイメージ４０４と確実に整合するようにできる。
【００４１】
ノイズ低減コンポーネント４１２を介してオンラインイメージ４１０からノイズが低減された後、検索コンポーネント４１８は、そのようなオンラインイメージ４１０を使用してデータストア４０６を検索し、オンラインイメージ４１０と実質的に一致する（したがって、印刷されたドキュメント４０８に実質的に一致する）オンラインドキュメントのイメージ４０４のうちの１つを特定することができる。検索コンポーネント４１８は、キャッシングコンポーネント４０２を介して生成されたイメージ４０４を受け取り、それに関係する署名４２２を作成する署名生成コンポーネント４２０を備えるが、オンラインドキュメントのイメージ４０４のそれぞれは、そのようなイメージ４０４を識別する署名４２２に関連付けられている。署名４２２は、生成されたイメージ４０４内の単語レイアウトに基づいて生成される。例えば、署名生成コンポーネント４２０では、キャッシングコンポーネント４０２を介して生成されたイメージ４０４内の各単語の位置と幅を使用して、署名４２２を生成することができる。署名生成コンポーネント４２０は、さらに、印刷されたドキュメント４０８のオンラインイメージ４１０を受け取り、それに関係する署名４２４を生成する。したがって、印刷されたドキュメント４０８に実質的な損傷がなかった場合には、署名４２４の少なくとも一部は、データストア４０６内のオンラインドキュメントのイメージ４０４に関係付けられている署名４２２のうちの１つの少なくとも対応する部分と実質的に一致する。本発明の一態様によれば、署名生成コンポーネント４２０は、印刷されたドキュメント４０８のオンラインイメージ４１０を取得しているときに発生しうる平行移動および／または回転誤差を考慮することができる。署名４２４および４２２の生成後、検索コンポーネント４２０に関連付けられている比較コンポーネント４２６は、署名４２２と４２４とを比較することにより、印刷されたドキュメント４０８に対応するオンラインドキュメント４０４のイメージを特定することができる。より具体的には、印刷されたドキュメント４０８のイメージ４１０と最もよく一致するオンラインドキュメントのイメージ４０４を特定するために、署名４２２と４２４とを比較する。その後、オンラインドキュメントの場所を識別するＵＲＬまたはその他の適当なメカニズムを取得し、ユーザに返すことができる。
【００４２】
次に図５を参照すると、ドキュメントのイメージ５００の拡張例が示されている。ドキュメント５００は、複数の文字からなる複数の単語を含む。従来のシステムおよび／または方法では、光学式文字認識を使用して印刷されたドキュメントと対応するオンラインイメージとの照合を円滑に行えるようにする。しかし、そのようなＯＣＲにはかなり時間がかかり、検索を必要とするオンラインイメージが多数あると、ＯＣＲは非常に大きな負担となりうる。したがって、本発明では、単語を融合せずにそのような複数の文字を融合するための文字の拡張について考察する。例えば、イメージ５００の解像度は、そのような文字を融合させるために変えることができる。その後、イメージ５００は個々の文字を含まず、単語のレイアウト５０２を含むことになる。２つのドキュメントが実質的に類似している単語レイアウトを含む確率は極めて小さいので、単語レイアウト５０２に基づいてイメージ５００に対する署名を生成することができる。
【００４３】
次に図６を参照すると、複数の融合された文字からなる単語６００の例が示されている。ドキュメント内の単語６００の位置は、座標Ｘ、Ｙ、およびＷにより定義することができるが、ただし、ＸはＸ方向の単語６００の特定の部分のピクセル位置であり、ＹはＹ方向の単語６００の特定の部分のピクセル位置であり、Ｗは単語６００の幅である。本発明の一態様によれば、単語６００の左上角は、単語６００の位置を定義するＸ、Ｙ位置として使用される。しかし、ドキュメント内の単語６００のどの部分も、単語６００の位置（例えば、左下角、右上角、中央など）を定義するために使用できることは理解されるであろう。
【００４４】
本発明の他の態様によれば、位置の誤差は、Ｘ、Ｙ、およびＷ方向の許容誤差しきい値を与えることにより考慮することができる。例えば、Ｘ、Ｙ、およびＷは、単語６００の位置を定義し、Ｘ方向のｚの許容誤差、Ｙ方向のｑ、および幅のｐが、それぞれ与えられる。したがって、そのような位置が署名生成に使用される場合、位置は、（［Ｘ−ｚ，Ｘ＋ｚ］，［Ｙ−ｑ，Ｙ＋ｑ］，［Ｗ−ｐ，Ｗ＋ｐ］）として定義することができる。しかし、単語６００を含むイメージが実質的に高い解像度である場合、十分な許容誤差に必要なピクセルの数は大きくなりすぎることがある（例えば、そのような高解像度のイメージに対する署名の生成は、かなり時間がかかることがあり、また格納するのにも、かなりの領域を必要とすることがある）。したがって、本発明の他の態様によれば、イメージの解像度を変えることにより、物理的境界内のピクセルの個数を減らすことができる。そうする代わりに、ピクセルを効果的に組み合わせ物理的境界内のピクセルの個数を減らす１つまたは複数の機能を用意することもできる。複数の単語を含むドキュメントの署名は、単語６００に関して示されている座標と類似のＸ、Ｙ、およびＷ座標を使用することにより生成することができる。そこで、印刷されたドキュメントのオンラインイメージの署名をキャッシュされているイメージの複数の署名と比較して、印刷されたドキュメントの署名と実質的に一致する署名を特定し、それをユーザに返すことができる。
【００４５】
次に図７を参照すると、単語レイアウト例のイメージ７００が示されている。イメージ７００は、複数の単語７０２を含み、単語レイアウトは、イメージ７００内の各単語の位置および幅を定義することにより定義することができる。その後、署名は、イメージ７００の単語レイアウトを使用することにより生成することができる。例えば、署名は、Ｘ方向、Ｙ方向、および幅の単語７０２のイメージ７００における位置に対応する値が「ＴＲＵＥ」であるハッシュテーブルとすることができる。より具体的には、単語位置がＸ＝３、Ｙ＝４、およびＷ（幅）＝７で定義されている場合、Ｘ＝３、Ｙ＝４、およびＷ＝７に対応するハッシュテーブル内の位置は、値がＴＲＵＥとなる。さらに、Ｘ、Ｙ、およびＷに関して許容誤差を規定することにより誤差を考慮することができる。例えば、ｚ＝ｑ＝ｐ＝２の許容誤差が使用され、ｚはＸにおける許容誤差に対応し、ｑはＹにおける許容誤差に対応し、ｐはＷにおける許容誤差に対応している場合、すべてのハッシュテーブルエントリ（［３−２，３＋２］，［４−２，４＋２］，［７−２，７＋２］）はＴＲＵＥとなる（例えば、（１，２，５）、（２，２，５）、（３，２，５）、（４，２，５），．．．）。したがって、イメージ７００は、関連する許容誤差を持つ単語７０２の位置および幅を使用して、イメージ７００を確実に識別する関係付けられた署名を持つことができる。
【００４６】
次に、図８を参照すると、ドキュメントのイメージに対する署名として使用することができるハッシュテーブル８００の実施例が示されている。左欄８０２は、イメージ上の位置およびイメージ内の単語の幅に対応するハッシュテーブルを持つ位置を表し、右欄８０４は、それらの位置に関連付けられている「ＴＲＵＥ」および「ＦＡＬＳＥ」値を含む。「ＴＲＵＥ」値は、ハッシュテーブル８００内の対応するエントリにより示される位置に、示される幅の単語が存在することを示し、「ＦＡＬＳＥ」値は、ハッシュテーブル８００内の対応するエントリにより示される位置に、示される幅の単語が存在しないことを示す（例えば、「ＴＲＵＥ」値は、１で示すことができ、「ＦＡＬＳＥ」値は、０で示すことができる）。例えば、ハッシュテーブル８００の第１行は、幅１６の単語がＸ−Ｙ位置（３１、２１）に存在しないことを示す。ハッシュテーブル８００の第２行は、幅１７の単語がＸ−Ｙ位置（３１、２１）に存在することを示す。さらに、ハッシュテーブル８００は、印刷されたドキュメントのオンラインイメージを取得する際に発生しうる平行移動および／または回転誤差を考慮する方法で作成できる。例えば、位置Ｘ＝５１、Ｙ＝１７にある幅Ｗ＝１４の単語は、実際には、イメージ内に存在する可能性がある。しかし、ハッシュテーブルは、Ｘ＝［５０，５２］およびＹ＝［１６，１８］で単語の幅が１３から１５であることを示すことができる。したがって、実際に、単一単語に関係するハッシュテーブル８００内に複数の「ＴＲＵＥ」値がありうる（例えば、前述の例では、単一の単語に対して２７個の「ＴＲＵＥ」値がある）。
【００４７】
本発明の他の態様によれば、ハッシュテーブル８００を圧縮するための関数を実現することができる（例えば、この関数は、ハッシュテーブル８００により表されるイメージの解像度を変更することができる）。例えば、単語の左上角は、ピクセル（１６１，１１２）で定義される位置を持ち、単語の幅は５４であるが、１６１はｘ方向のピクセル位置を表し、１１２はｙ方向のピクセル位置を表し、単語の幅はピクセル単位である。その後、このピクセル位置および幅をある値（グリッドサイズ）で除算し、ハッシュテーブル８００の圧縮および／または伸長を行うことができる（例えば、複数のピクセルでも単一座標で識別できる）。したがって、グリッドサイズが５の場合、（１６１，１１２）と相関関係がある単語の位置は、
【００４８】
【数１】
0004718841.tif 000002
【００４９】
により定義することができる。さらに、単語の幅は、同じファクタにより、またはその代わりに、異なるファクタにより低減することができる。例えば、幅低減値（ｗｉｄｔｈｅｒｒ）は、３とすることができ、その結果、幅は
【００５０】
【数２】
0004718841.tif 000003
【００５１】
により定義される。これらの値の例を使用して、結果として修正された位置を、値Ｘ＝３２、Ｙ＝２２、およびＷ＝１８により定義することができる（例えば、余りを丸める、および／または切り捨てることができる）。ハッシュテーブル８００をこのように圧縮すると、署名の解像度が効果的に下げられ、その結果、検索をより早く完了させることができる（代わりに精度を犠牲にする）。その後、印刷されたドキュメントのデジタルイメージを取り込む際に発生しうる平行移動および／または回転誤差を、値毎に許容誤差しきい値を設定することにより考慮することができる。例えば、それぞれの値において誤差しきい値を１として、単語の位置および幅を識別することができる。したがって、ハッシュテーブル８００は、（［３１，３３］，［２１，２３］，［１７，１９］）と相関関係のあるハッシュテーブル８００内の位置について「ＴＲＵＥ」値を含む。
【００５２】
本発明のさらに他の態様によれば、単語の位置および幅に対応する値を格納する必要性を緩和するための関数を使用し、そのような値を単一の一意的な値、これ以降キーと呼ぶ値で置き換えることができる。例えば、単語の最大幅（ｍａｘｗｉｄｔｈｗｏｒｄ）のしきい値およびピクセル単位の１ページの最大幅（または調整されたピクセル値の最大幅）（ｍａｘｗｉｄｔｈｐａｇｅ）を定義することができる。すると、Ｈ（Ｘ，Ｙ，Ｗ）は、
Ｙ×ｍａｘｗｉｄｔｈｐａｇｅ×ｍａｘｗｉｄｔｈｗｏｒｄ＋Ｘ×ｍａｘｗｉｄｔｈｗｏｒｄ  ＋  Ｗ
と定義できる。ｍａｘｗｉｄｔｈｐａｇｅおよびｍａｘｗｉｄｔｈｗｏｒｄは、大きな素数にとることができるが、上記の式は単にハッシュ関数の一実施例に過ぎないことは理解されるであろう。ドキュメント内の単語の位置および幅をマッピングする他のハッシュ関数も考察される（例えば、完全ハッシュ関数も使用できる）。このような関数を使用することにより、ハッシュテーブル８００内のＸ、Ｙ、Ｗ値を破棄することができる（したがって、ハッシュテーブル８００の格納および／または異なるハッシュテーブルとの比較に必要なメモリを減らすことができる）。さらに、ハッシュテーブル８００では、すべての偽の値を破棄して、そのようなハッシュテーブル８００を格納するために必要なメモリを減らすことができる（例えば、このようなハッシュテーブルは、「ＴＲＵＥ」値に関連付けられたキーのみを含む）。ハッシュテーブル８００は、ドキュメントのイメージを表すことができる署名として例示されているが、他のデータ形式および／または構造が考慮されており、付属の請求項の範囲内にあることが意図されていることは理解されるであろう。さらに、従来のハッシュテーブルよりも壊れやすくないことが知られている近似的なハッシュテーブルを本発明とともに使用することができる。
【００５３】
次に、図９を参照すると、ハッシュテーブル８００（図８）は、立方体９００として例示されており、これにより、このようなハッシュテーブル８００が分かりやすくなっている。立方体９００は、ハッシュテーブル８００に関係するイメージの幅（例えば、ピクセル単位）によりＸ方向に束縛され、ハッシュテーブル８００に関係するイメージの高さ（例えば、ピクセル単位）によりＹ方向に束縛され、あらかじめ定義されているしきい値（例えば、ピクセル単位の単語の最大許容幅）によりＷ方向に束縛されている。したがって、幅１０００ピクセル、高さ１２００ピクセルのイメージに対して立方体９００の外側境界はＸ＝１０００、Ｙ＝１２００、およびＷ＝５０とすることができ、あらかじめ定義されている最大単語幅は５０である。さらに、立方体９００のサイズは、イメージの高さおよび幅を共通の値で割ることにより縮小することができ、さらに幅の値で割ることにより縮小することができる。例えば、イメージの高さおよび幅は、５で割り、幅の値は、２で割ることができる。したがって、上述の例については、立方体９００はＸ＝２００、Ｙ＝２４０、およびＷ＝２５の境界を持つ。
【００５４】
立方体９００は、ハッシュテーブル８００内の「ＴＲＵＥ」値に対応する容積領域９０２および９０４を含む。容積領域９０２、９０４は、印刷されたドキュメントのデジタルイメージを取り込む際に平行移動および／または回転により生じうる誤差が考慮されているため、３次元である。容積領域９０２および９０４の中心が、イメージ内の単語の実際の位置および幅であり、そのような点は、誤差に関するあらかじめ定義されているしきい値により伸長される。そうでない場合、そのような「ＴＲＵＥ」値は、立方体９００内の個別の点として現れるであろう。第２のハッシュテーブルとハッシュテーブル８００とを比較する場合、第２のハッシュテーブルに対応する立方体で転置された立方体９００を考え、立方体間に重なりの発生があるかどうかを判別することができる。その後、２つの立方体の間の多数の重なりを表にして利用し、立方体が実質的に類似しているドキュメントに関係しているかどうかを判別することができる。
【００５５】
次に図１０を参照すると、ノイズを含む印刷されたドキュメントのイメージ１０００の実施例が示されている。ドキュメント１０００は、複数の単語およびそれらの単語に関係する複数の注釈を含む。イメージの１行目のアンダーラインとなっているライン１００２が存在する。イメージ１０００の２行目の単語「ｃａｎ」は、一部単語を上書きする注釈１００４に関連付けられている。イメージ１０００全体にわたって複数のマーキング１００６が存在し、それらのマーキングは、ペン、鉛筆、汚れ、食べ物などによると考えられる。最後に、手書きの単語１８００がイメージ１０００に追加されている。これらの注釈およびマーキング１００２〜１００８は、印刷されたドキュメント上に付いており、ドキュメントのオリジナルのオンライン版には存在していない。したがって、イメージ１０００の署名を生成するのに先立ってそれらの注釈を除去すると都合がよい。ノイズ低減の結果は、「きれいな」単語、つまり、注釈を介してつながっていない単語、染みがついていたり不明瞭であったりしない単語などでなければならない。
【００５６】
次に図１１を参照すると、注釈を取り除いた後のイメージ１０００（図１０）が例示されている。図１０および１１に関して例示されているようなノイズの低減は単なる例であり、そのようなノイズ低減を行った結果、図１１に示されているのと異なる形で見える可能性があることは理解されるであろう。ライン１００２（図１０）は、しきい値で定められた幅にわたってすべてのマーキングを除去するフィルタを用意することにより除去することができる。例えば、単語の最大許容幅を定義し、その許容幅を超えるマーキングを除去することができる。さらに、単語の最小許容幅を定義し、前提条件となる最小幅を満たさないマーキングを除去することができる。したがって、マーキング１００６（図１０）は、イメージ１０００からフィルタで除去することができるが、それは、そのようなマーキングが幅の前提条件を満たしていないからである。同様に、単語の最大高さおよび最小高さも、イメージ１０００内の望ましくない注釈を除去するためにあらかじめ定義しておくことができる。イメージ内に境界を定義し、そのような境界の外側にあるマーキングを除去することができる。他の実施例では、イメージ内の特定の色を変える、および／または除去することができる。さらに、注釈に直接関連付けられているイメージ１０００内の単語（例えば、単語「ｃａｎ」）を、ドキュメント内の単語レイアウトの独自の性質だけでなく典型的なドキュメント内の単語の数により本発明の確実さに影響を及ぼすことなく排除することができる。より具体的には、複数の単語をドキュメント内のノイズとして除去することができ、しかも、対応するイメージを特定する効率および／または確実さに影響を及ぼすことがない。さらに、本発明では、ドキュメント内に埋め込まれているイメージをノイズとして除去することができ、それによって、単語レイアウトに基づきそのようなドキュメントを識別することができる。本発明では、印刷されたドキュメントのイメージ内のノイズ（注釈１００２〜１００８など）をフィルタにより効果的に除去することができる多数のフィルタ処理手法を考察している。
【００５７】
次に、図１２を参照すると、キャッシュされているイメージを識別するために署名として使用されるハッシュテーブルを生成する方法１２００が例示されている。１２０２で、許容可能誤差のしきい値量が定義される。そのような許容可能誤差を与えることは、イメージの署名および印刷されたドキュメントのイメージの署名に基づいてイメージを特定する際に重要と考えられる。許容誤差が与えられていない場合、印刷されたドキュメントに実質的に類似しているイメージが平行移動および／または回転誤差のせいで特定されない可能性が存在する。
【００５８】
１２０４で、イメージ内の各単語の少なくとも一部の幾何学的位置が決定される。例えば、イメージ内の各単語の左上角の位置を判別し、一時的に格納することができる。しかし、ドキュメント内の単語の一部（または単語全体）は、イメージの単語レイアウトを表すことに関連して特定できることは理解されるであろう。１２０６で、ドキュメント内の各単語の幅を、例えば、各単語の幅にそってピクセルの数を数えることにより決定することができる。その後、ピクセル単位で測定された幅を縮尺して、望むサイズの署名を生成することができる。
【００５９】
１２０８で、「キー」は、イメージ内の単語レイアウトに対応して生成される。例えば、「ＴＲＵＥ」の値は、１ビットまたはビット列で表すことができ、単語の存在とともに単語の幅に関するドキュメント内の位置について生成することができる。「ＴＲＵＥ」値に対応するそのような位置および幅は、ハッシュテーブル内に一時的に格納して利用することができるが、「ＴＲＵＥ」でない値は破棄することができる。さらに、許容誤差が許されている場合、単語の位置および幅毎に複数のキーを生成することができる。例えば、許容誤差±２が割り当てられ、単語の位置および幅（Ｘ，Ｙ，Ｗ）は（１０，１２，１５）である場合、（８，１４，１５）、（８，１１，１２）などに対して真であるキー値が生成される。しかし、「ＴＲＵＥ」値は本発明の実装には必要ないことが理解されるであろう。例えば、「ＮＵＬＬ」値は、単語の存在とともに単語の幅に関するドキュメント内の位置について生成することが可能である。
【００６０】
１２１０で、これらのキー値を使用して、他のハッシュテーブルと比較することができるハッシュテーブルを生成し、対応する印刷されたドキュメントの取り込まれたデジタルイメージに基づきドキュメントのオリジナルのオンライン版を容易に特定できるようにする。例えば、ハッシュテーブルは、「ＴＲＵＥ」値に関連付けられている（Ｘ，Ｙ，Ｗ）値に対応するは値を含むことができる。したがって、例えば、１００個の「ＴＲＵＥ」値が１つの特定のイメージに対して存在していた場合、ハッシュテーブルはそれら１００個の「ＴＲＵＥ」値をイメージ内のそれぞれの位置および幅を識別するキーの形で含む。さらに、位置および幅を定義する値を、３つの値すべての格納を不要にする関数内で使用することができる。
【００６１】
次に図１３を参照すると、印刷されたドキュメントの取り込まれたイメージの署名を生成する方法１３００が例示されている。１３０２で、印刷されたドキュメントのデジタルイメージが取り込まれる。例えば、デジタルカメラまたはスキャナを、ドキュメントのイメージを取り込むために使用することができる。１３０４で、イメージのグレースケールが取得される。グレースケールイメージの生成は、物理的エンティティのイメージを取得する際にカラー化問題が生じるため実行することが望ましい。例えば、特定の照明を与えた場合、イメージは黄色の背景に緑色のレタリングを持つように見えることがある。本発明では、あらかじめ定義されている色値の色（例えば、黄色）を望ましい値（例えば、白色）に変更することも考慮している。したがって、印刷されたドキュメントのイメージ内の色は、対応するキャッシュされているイメージ内に存在する色と実質的に一致する。
【００６２】
１３０６で、取り込まれたイメージ内に残っているノイズが低減される。例えば、１つまたは複数のフィルタを用意して、対応するキャッシュされているイメージ内には存在しない印刷されたドキュメント内に存在する注釈を除去することができる。より具体的には、あらかじめ定義されているしきい値幅および／または高さよりも上および／または下のマーキングを除去するフィルタを採用することができる。さらに、マーキングの頻度を検討して、それらが望ましくないノイズであるかどうかを判別することができる。そのようなフィルタは、さらに、汚れ、染み、折り目なども除去することができる。そのようなノイズ除去を行うことにより、取り込まれたイメージはキャッシュされているイメージに実質的に類似する。
【００６３】
１３０８で、イメージの解像度が望ましい解像度であるかどうかを判別する。イメージの解像度を変更して、データストア内のイメージに関してそのようなイメージを正規化しなければならない。例えば、取り込まれたイメージおよび格納されているイメージの寸法は、本発明を最適な形で稼働させるためには実質的に類似していなければならない。そのような解像度が望ましくない場合（例えば、解像度が高すぎる）、１３１０で、解像度を変更する。例えば、高解像度イメージは、変更により、異なる単語を融合することなく個々の文字を融合しやすくする必要がある場合がある。さらに、解像度を変更することにより、望ましいサイズの署名を生成できる。イメージの解像度が望ましい解像度である場合、１３１２で、そのイメージ内の単語レイアウトに関係するデータを読み込む。例えば、それぞれの単語の少なくとも一部のＸ−Ｙ座標（ピクセル単位またはイメージ内の他の適当な単位を使って）を取り出すことができ、またそれぞれの単語の幅も取り出すことができる。これらの値を使用することにより、ドキュメントの単語レイアウトを定義することができる。１３１４で、その単語レイアウトに基づいてハッシュテーブルが生成される。例えば、ハッシュテーブルは、印刷されたドキュメントのイメージ内に存在する単語の位置および幅に対応するキー値のみを含むことができる。その後、そのようなキー値をハッシュテーブルに入れ、異なるハッシングされたイメージのキー値と比較し、そのような値に対応するイメージが実質的に類似しているかどうかを判別することができる。
【００６４】
図１２および１３を参照すると分かるように、オンラインドキュメントの格納されているイメージおよび印刷されたドキュメントの取り込まれたイメージの署名を生成する方法は、実質的に類似している。イメージと実行されるノイズ低減のソースには違いが存在する。より具体的には、取り込まれるイメージは、デジタルカメラ、スキャナ、ＦＡＸカードなどを介して取得される。オンラインドキュメントのイメージは、プリントドライバに関係付けることができるキャッシングコンポーネントを出所とする。さらに、格納されているイメージに実質的に類似しているイメージを生成するためには、取り込まれたイメージからノイズを除去するのが望ましい。例えば、注釈、染み、およびその他のノイズは、取り込まれたイメージの署名を生成する際に除去することができる。
【００６５】
次に図１４を参照すると、本発明の一態様により分割されている印刷されたドキュメントのイメージ１４００の実施例が示されている。キャッシュされているイメージの多数の署名を印刷されたドキュメントのイメージの署名と比較して、キャッシュされているイメージのどれが印刷されているドキュメントに実質的に類似しているかを判別しなければならない場合に分割は有用である。例えば、キャッシュされているイメージのそれぞれの署名を印刷されているドキュメントのイメージの署名と丸ごと比較する場合にかなり時間がかかることがある。したがって、イメージ１４００を複数のセグメント１４０２、１４０４、１４０６、および１４０８に分割し、そこで、イメージ１４００の署名の一部のみとキャッシュされているイメージの署名の実質的に類似している部分とを比較する。イメージ１４００は、４つのセグメントに分割されているように示されているが、セグメントは適当な数だけ選択できることは理解されるであろう。例えば、イメージ１４００のセグメントの個数は、キャッシュされているイメージの個数の関数とすることができる（例えば、キャッシュされているイメージの数を多くする、セグメントの数を多くする、セグメントのサイズを小さくするなど）。
【００６６】
したがって、キャッシュされているイメージの複数の署名の一部のみが、セグメント１４０２〜１４０８のうちの１つと関連付けられているイメージ１４００の署名の対応する部分と比較される。その後、キャッシュされている署名の部分とイメージ１４００の署名の対応する部分との間に１つの一致があるか、またはしきい値で定められる数の一致があるキャッシュされているイメージの署名は、さらに考慮するために保持され、一致を含まない署名は破棄される。例えば、セグメント１４０２は、イメージ１４００を識別する署名の特定の部分に関連付けられている。署名のそのような部分をキャッシュされてイメージに関係付けられている署名の対応する部分と比較することができる。署名のそのような部分とイメージ１４００の対応する署名との間の１つの一致またはしきい値で定められた数の一致があるキャッシュされているイメージの署名をさらに考慮する。その後、イメージ１４００をさらに、複数の小さなセグメントに分割し、それによって、最終的に、一致していない署名を考慮から外し、イメージ１４００の署名に実質的に一致している署名を残すことができる。しかし、損傷および／またはノイズ低減における誤差のせいで、最も正しい一致する署名が特定のセグメント分割により考慮の対象から外される可能性もある。そのような違った排除は、それぞれのセグメント分割についてしきい値で定められた数のイメージを考慮することを要求し、イメージの数がしきい値よりも下がった後さらに徹底したチェックを実行することにより見つけ出すことができる。徹底的なチェックを行った結果、残りの署名がイメージ１４００の署名と実質的に一致しないと判定された場合、イメージ１４００を再分割し、異なる分割を選択することができる。高い信頼度の一致が存在している場合、署名に対応するイメージをユーザに返すことができる。
【００６７】
次に図１５を参照すると、ドキュメントの少なくとも一部のイメージの木表現１５００の実施例が示されている。この木表現は、複数の層１５０２〜１５０６を含み、それぞれの層はドキュメント内の分割のレベルを表す。より具体的には、第１の層１５０２は、イメージ全体を表す単一セグメント１５０８（例えば、ドキュメントの１ページのイメージ）を含む。イメージに１つまたは複数の単語が含まれる場合、値１（またはセグメント１５０８内に１つまたは複数の単語が存在することを識別する他の値）が木表現１５００内のセグメント１５０８に割り当てられる。そうでなくて、イメージがブランクであった場合、値「０」（またはセグメント１５０８内に単語が存在していないことを確認する他の値）が割り当てられる。その後、セグメント１５０８は複数のセグメント１５１０〜１５１６に分割されるが、その場合、セグメント１５１０〜１５１６は、木表現の第２層１５０４に関連付けられている。それぞれのセグメント１５１０〜１５１６が１つまたは複数の単語を含むかどうかを判別される。例えば、セグメント１５１０に割り当てられた１の値で示されるように、セグメント１５１０内に１つまたは複数の単語が存在する。セグメント１５１２内には単語は存在せず、このセグメントには値０が割り当てられている。
【００６８】
セグメント１５１０〜１５１６はそれぞれ、さらに、階層の第３層１５０６上で複数のセグメント１５２０に分割することができる。セグメント１５１２を検討すると分かるように、そのようなセグメントに０が割り当てられている場合、階層の下位層内のセグメント１５１２に関連付けられているセグメントもすべて、０が割り当てられる（したがって、木の中に含める必要はなく、除外すると、木構造の格納領域利用効率を改善することができる）。木表現１５００は、適切であれば層をいくつでも含むことができ、比較時に考慮すべき署名の数を減らせる。例えば、署名は、イメージ内の単語のトポロギーのプロパティに基づいて生成される。より具体的には、それぞれの単語の一部の位置およびそれぞれの単語の幅に基づいて署名を生成することができる。木表現は、署名が生成されるのと実質的に類似したタイミングで生成することができ（取り込まれたイメージとキャッシュされているイメージの両方に対して）、これを使用することにより、ドキュメントの印刷されたコピーのイメージに基づいてドキュメントのオンライン版を特定する際に比較すべきで署名の数を素早く減らすことができる。
【００６９】
例えば、木表現１５００は、ドキュメントの印刷されたページの取り込まれたイメージを表すことができる。木表現１５００の第２層１５０４は、キャッシュされているイメージの木表現の対応する第２層と比較することができる。セグメント１５１０、１５１４、および１５１６に対応するキャッシュされているイメージのセグメントすべてが１を割り当てられているわけではない場合、キャッシュされているイメージの木表現に対応する署名はそれ以上考慮されない。セグメント１５１０、１５１４、および１５１６に対応するキャッシュされているイメージのセグメントすべてが１を割り当てられている場合、キャッシュされているイメージの木表現に対応する署名はさらに考慮するため保持される。さらに、セグメント１５１０、１５１２、１５１４、および１５１６に対応するキャッシュされているイメージのセグメントは、すべて、１を割り当てることができ、木表現に対応する署名は、さらに考慮するため保持される。これは、取り込まれたイメージの木表現１５００のセグメント１５１２が０を割り当てられることを鑑みても、当てはまるが、それは、印刷されたドキュメントイメージのこのセグメントは物理的ドキュメント内に生じている可能性のある染み、破れなどのせいで空であるかのように見える場合があるからである。例えば、セグメント１５１２は汚れで覆われていることがあり、ノイズ低減の後、取り込まれたイメージのセグメント１５１２は、ドキュメントが印刷されたときにドキュメントのオンライン版に単語が存在していたとしても、単語を含まない。さらに、取り込まれたイメージに関連付けられている木表現１５００の第２階層１５０４をキャッシュされているイメージに関連付けられている木表現の対応する第２層と比較しても考慮すべき署名の数が十分に減らない場合、木表現の第３層１５０６を比較することができる。木表現には十分な数の層を入れて、残りのドキュメント数をあらかじめ定められているしきい値よりも小さくなるようにでき、それによって、署名のより徹底的な比較を素早く完了することができる。木表現は、イメージの署名がデータストア内のイメージに関連付けられているのとまったく同様にして、データストア内に配置し、イメージに関連付けることができる。
【００７０】
次に、図１６を参照すると、ドキュメントの単語レイアウトに基づいて印刷されたドキュメントのイメージの署名に実質的に類似している複数の署名のうち１つのイメージの署名を特定する方法１６００が例示されている。１６０２で、それぞれのキャッシュされているイメージに関連付けられている木表現とともに印刷されたドキュメントの取り込まれたイメージに関連付けられている木表現が生成される。木表現の実施例が図１５に示されている。木表現は、イメージ署名が生成されるのと実質的に類似したタイミングで生成することができる。署名は、ドキュメントの１ページの単語レベルのトポロギーのプロパティに基づいて生成されるが、木表現は、ドキュメントのイメージの階層表現であり、イメージは、多数のセグメントに分割され、それぞれのセグメントは、セグメント内に単語が存在するかどうかに応じてある値が割り当てられる。それらのセグメントは、さらに分割され、その結果、階層表現を作り出すことができる。
【００７１】
１６０４で、印刷されたドキュメントの取り込まれたイメージに関係付けられている木表現の１つの層をキャッシュされているイメージに関連付けられている木表現の対応する層と比較する。例えば、第１層は、イメージ全体を表しているセグメントを含み、したがって、取り込まれたイメージが１つまたは複数の単語含んでいた場合、そのセグメントは、イメージが１つまたは複数の単語を含んでいたことを示す値を関連付けられる。したがって、キャッシュされているイメージが１つまたは複数の単語を含んでいなかった場合、キャッシュされているイメージの木表現の第１層は、セグメントが１つまたは複数の単語を含んでいなかったことを示す値を関連付けられているセグメントを含む。木表現の第２層は、複数のセグメントを含み、それぞれのセグメントは、セグメントが単語を含んでいたかどうかを示す値を関連付けられる。したがって、取り込まれたイメージに関連付けられている木表現とキャッシュされているイメージに関連付けられている木表現の対応する層同士を比較することにより、ドキュメントの印刷版に最も一致するドキュメントのオンライン版を特定しようとする場合に考慮すべき署名の数を素早く減らすことができる。
【００７２】
１６０６で、望ましい層がキャッシュされているイメージに関係付けられている対応する層と実質的に一致するキャッシュされているイメージに関係付けられている木表現は、さらに考慮するため保持される。取り込まれたイメージに関係付けられている木表現の層は、印刷されたドキュメントに染み、破れ、およびその他の物理的損傷があると不整合を引き起こすことがあるため、キャッシュされているイメージに関係付けられている木表現の対応する層と完全に一致している必要はない。例えば、破れているという理由でセグメントを１つ完全に除去すると、木表現によりそのセグメントが単語を含まないことを伝達することができる。しかし、もし破れがなかった場合、セグメントは１つまたは複数の単語を含んでいることであろう。したがって、さらに考慮するために、キャッシュされているイメージに関係付けられている木表現内のセグメントは、取り込まれたイメージのセグメントが１つまたは複数の単語を含んでいる場合に、取り込まれたイメージの木表現に関係付けられている対応するセグメントと一致しなければならない。
【００７３】
１６０８で、考慮対象として残っている署名が多すぎないか（したがって、木表現が多すぎないか）に関する判定が行われる。例えば、単語レベルのトポロギーのプロパティに基づいて生成される署名の照合は、かなり時間がかかる場合がある。したがって、取り込まれたイメージに関係付けられている署名と比較すべきキャッシュされているイメージに関係付けられている署名の数を減らすと有益である。考慮対象の残っている署名の数がしきい値を超えている場合、１６１０で、木表現階層内の次の層が比較の対象に選択される。木表現の階層内の次の層を選択することにより、署名を比較するのに先立って考慮すべき署名の数を減らすことができる。考慮すべき署名の数がしきい値未満であれば、１６１２で、取り込まれたイメージに関係付けられている署名は、考慮対象として残っているキャッシュされているイメージの署名と比較される。署名は、イメージ内の単語のトポロギーのプロパティ（例えば、イメージ内の各単語の位置および幅）に少なくとも一部は基づき生成される。
【００７４】
１６１４で、最高のスコアを持つ署名がしきい値スコア要件を満たしているかどうか（署名が「高信頼度」一致であるかどうか）に関して判別される。印刷されたドキュメントのイメージの署名と最も都合よく比較されるキャッシュされているイメージに関係付けられている署名が高信頼度一致である場合、その署名に対応するイメージは、１６１６で、ユーザに返される。このような署名が高信頼度一致でない場合、１６１８で、キャッシュされているイメージに関係するすべての署名が取り込まれたイメージに関係付けられている署名と比較されたかどうかに関する判定が行われる。キャッシュされているイメージに関係する署名がすべて比較された場合、１６２０で、ユーザに対し、高信頼度の一致がなかったことが通知される。これは、印刷されたドキュメントに対応するキャッシュされているイメージが存在しない場合および印刷されたドキュメントが損傷しておりそのようなドキュメントの識別が極めて困難になっている場合に発生しうる。そうでない場合、関連付けられている木表現に基づいて考慮対象からすでに外されている署名は、１６２２で、前の層で破棄されたドキュメントの再考慮により再考慮することができる。例えば、しきい値と比較すべき署名の数を減らすために木表現の第５層の比較が必要であると仮定する。ただし、残りの木表現に関係付けられている署名で、取り込まれたイメージの署名を比較した場合に高信頼度の一致が得られる署名はなかった。したがって、本発明の一態様によれば、木表現の第４層で考慮対象に残っているすべての署名を比較することができる。
【００７５】
木表現の特定の層に基づいて廃棄された署名が再考慮された後、方法１６００は１６１２に続く。さらに、１６１２で署名を直接比較する場合、署名を複数の部分に分割し、取り込まれたイメージに関係付けられている署名の部分をキャッシュされているイメージに関係付けられている署名の対応する部分と比較することができることも理解されるであろう。これは、取り込まれたドキュメントに関係付けられている署名の部分に、取り込まれたイメージの特定の部分におけるノイズが低減されたことにより一致がなくなることが知られている場合に有用である。これは、照合手順を実質的に高速化することができる。
【００７６】
次に図１７を参照すると、本発明の一態様によるデータストア１７００の実施例およびその内容が示されている。データストア１７００は、リレーショナルデータベースとみなすことができ、オンラインドキュメントの１ページのイメージ１７０２は、データストア１７００内の「一次」エンティティである。データストア１７００の実施例は単一イメージ１７０２を含むようにしか示されていないが、データストア１７００は、通常、複数のイメージおよびそれに関連付けられたデータを含むことは理解されるであろう。関連データの実施例は、そのようなオンラインドキュメントの１ページのイメージ１７０２に対応するオンラインドキュメントの位置を識別するＵＲＬ  １７０４を含む。このＵＲＬは、後で取得される対応する印刷されたページに基づいてイメージ１７０２をデータストア１７００で検索した後、ユーザに送ることができる。より具体的には、署名１７０６は、イメージ１７０２に関連付けられ、署名１７０６は、印刷されたページのイメージに関係する署名と比較される。署名を比較し、イメージ１７０２が印刷されたドキュメントのイメージとよく一致すると判断した後、関連するＵＲＬ  １７０４をユーザに中継することができる。さらに、イメージ１７０２もユーザに中継することができる。データストア１７００がイメージ１７０２に対応するドキュメントのオンライン版を含む場合、ドキュメント自体は、署名の比較後ユーザに返すことができる。さらに、階層の木１７０８も、イメージ１７０２に関連付けることができ、上述のように検索からイメージ１７０２を速やかに除外することができる。他の関係付けられたデータ１７１０も、例えばイメージ１７０２のＯＣＲ、データストア１７００内でページイメージがアクセスされた回数に関する測定基準、顧客記録、ワークフロー情報（例えば、ワークフロー履歴）、支払い情報、およびオンラインドキュメントに関係付けることができるその他の適当なデータなどのイメージ１７０２に関連付けることもできる。しかし、イメージ１７０２の永続的格納は、主題の発明が稼働するためには不要であることは理解されるであろう。例えば、イメージ１７０２を生成して一時的に格納することができ、署名１７０６をイメージ１７０２から生成することができる。その後、イメージ１７０２を破棄して、データストア１７００内の使用可能な領域を増やすことができる。署名１７０２は、イメージ１７０２に対応するオンラインドキュメントの場所を識別するＵＲＬに関連付けることができる。データストア１７００内の他の要素も、署名１７０６に関連付けることができる。
【００７７】
図１８を参照すると、本発明のさまざまな態様を実装するための環境例１８１０はコンピュータ１８１２を含んでいる。コンピュータ１８１２は、適切であればどのようなコンピューティングデバイスであってもよい（例えば、パーソナルデジタルアシスタント、ラップトップコンピュータ、サーバ、デスクトップコンピュータなど）。コンピュータ１８１２は、処理ユニット１８１４、システムメモリ１８１６、およびシステムバス１８１８を備える。システムバス１８１８は、システムメモリ１８１６などのシステムコンポーネントを処理ユニット１８１４に結合する。処理ユニット１８１４は、さまざまな市販プロセッサがあるがそのうちどれでもよい。デュアルマイクロプロセッサおよびその他のマルチプロセッサアーキテクチャも、処理ユニット１８１４として採用することができる。
【００７８】
システムバス１８１８は、限定はしないがメモリバスまたはメモリコントローラ、周辺機器バスまたは外部バス、および／または８ビットバス、Ｉｎｄｕｓｔｒｉａｌ  Ｓｔａｎｄａｒｄ  Ａｒｃｈｉｔｅｃｔｕｒｅ（ＩＳＡ）、Ｍｉｃｒｏ−Ｃｈａｎｎｅｌ  Ａｒｃｈｉｔｅｃｔｕｒｅ（ＭＳＡ）、Ｅｘｔｅｎｄｅｄ  ＩＳＡ（ＥＩＳＡ）、Ｉｎｔｅｌｌｉｇｅｎｔ  Ｄｒｉｖｅ  Ｅｌｅｃｔｒｏｎｉｃｓ（ＩＤＥ）、ＶＥＳＡ  Ｌｏｃａｌ  Ｂｕｓ  （ＶＬＢ）、Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔ（ＰＣＩ）、Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ（ＵＳＢ）、Ａｄｖａｎｃｅｄ  Ｇｒａｐｈｉｃｓ  Ｐｏｒｔ（ＡＧＰ）、Ｐｅｒｓｏｎａｌ  Ｃｏｍｐｕｔｅｒ  Ｍｅｍｏｒｙ  Ｃａｒｄ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ａｓｓｏｃｉａｔｉｏｎ  ｂｕｓ（ＰＣＭＣＩＡ）、およびＳｍａｌｌ  Ｃｏｍｐｕｔｅｒ  Ｓｙｓｔｅｍｓ  Ｉｎｔｅｒｆａｃｅ（ＳＣＳＩ）をはじめとする利用可能な各種バスアーキテクチャを使用するローカルバスなど数種類のバス構造のうちのいずれでもよい。
【００７９】
システムメモリ１８１６は、揮発性メモリ１８２０および不揮発性メモリ１８２２を含む。起動時などにコンピュータ１８１２内の要素間の情報転送を行うための基本ルーチンを含む基本入出力システム（ＢＩＯＳ）は、不揮発性メモリ１８２２に格納される。例えば、ただしこれらに限られないが、不揮発性メモリ１８２２には、読み取り専用メモリ（ＲＯＭ）、プログラム可能ＲＯＭ（ＰＲＯＭ）、電気的プログラム可能ＲＯＭ（ＥＰＲＯＭ）、電気的消去可能ＲＯＭ（ＥＥＰＲＯＭ）、またはフラッシュメモリなどがある。揮発性メモリ１８２０には、外部キャッシュメモリとして動作するランダムアクセスメモリ（ＲＡＭ）がある。例えば、ただしこれらに限られないが、使用可能なＲＡＭには、同期ＲＡＭ（ＳＲＡＭ）、ダイナミックＲＡＭ（ＤＲＡＭ）、同期ＤＲＡＭ（ＳＤＲＡＭ）、Ｄｏｕｂｌｅ  Ｄａｔａ  Ｒａｔｅ  ＳＤＲＡＭ（ＤＤＲ  ＳＤＲＡＭ）、Ｅｎｈａｎｃｅｄ  ＳＤＲＡＭ（ＥＳＤＲＡＭ）、Ｓｙｎｃｈｌｉｎｋ  ＤＲＡＭ（ＳＬＤＲＡＭ）、およびＤｉｒｅｃｔ  Ｒａｍｂｕｓ  ＲＡＭ（ＤＲＲＡＭ）などさまざまな形態のものがある。
【００８０】
コンピュータ１８１２はさらに、取り外し可能／取り外し不可能な揮発性／不揮発性コンピュータ記憶媒体も備える。図１８は、例えばディスク記憶装置１８２４を示している。ディスク記憶装置１８２４には、磁気ディスクドライブ、フロッピディスクドライブ、テープドライブ、Ｊａｚドライブ、Ｚｉｐドライブ、ＬＳ−１００ドライブ、フラッシュメモリカード、またはメモリスティックなどがある。さらに、ディスク記憶装置１８２４は、記憶媒体を単独で備えることも、コンパクトディスクＲＯＭデバイス（ＣＤ−ＲＯＭ）、ＣＤ書き込み可能ドライブ（ＣＤ−Ｒドライブ）、ＣＤ書き換え可能ドライブ（ＣＤ−ＲＷドライブ）、またはデジタル多用途ディスクＲＯＭドライブ（ＤＶＤ−ＲＯＭ）などの光ディスクドライブをはじめとする他の記憶媒体と組み合わせて備えることもできる。ディスク記憶装置１８２４をシステムバス１８１８に接続しやすくするために、通常、インターフェース１８２６などの取り外し可能または取り外し不可能インターフェースを使用する。
【００８１】
図１８は、ユーザと適当な動作環境１８１０内の説明されている基本コンピュータ資源との媒介手段として動作するソフトウェアを説明していることは理解されるであろう。このようなソフトウェアとして、オペレーティングシステム１８２８がある。オペレーティングシステム１８２８は、ディスク記憶装置１８２４に格納することができ、コンピュータシステム１８１２の資源の制御および割り当てを行う働きをする。システムアプリケーション１８３０は、システムメモリ１８１６またはディスク記憶装置１８２４に格納されているプログラムモジュール１８３２およびプログラムデータ１８３４を通じてオペレーティングシステム１８２８により資源の管理を利用する。本発明は、さまざまなオペレーティングシステムまたはオペレーティングシステムの組み合わせで実装できることは理解されるであろう。
【００８２】
ユーザは入力デバイス１８３６を使用してコマンドまたは情報をコンピュータ１８１２に入力する。入力デバイス１８３６には、マウスなどのポインティングデバイス、トラックボール、ペン、タッチパッド、キーボード、マイク、ジョイスティック、ゲームパッド、衛星放送受信アンテナ、スキャナ、ＴＶチューナーカード、デジタルカメラ、デジタルビデオカメラ、Ｗｅｂカメラなどがある。これらの入力デバイスやその他の入力デバイスは、インターフェースポート１８３８を介してシステムバス１８１８を通じて処理ユニット１８１４に接続する。例えば、インターフェースポート１８３８には、シリアルポート、パラレルポート、ゲームポート、およびユニバーサルシリアルバス（ＵＳＢ）がある。出力デバイス１８４０は、入力デバイス１８３６と同じ種類のポートをいくつか使用する。したがって、例えば、ＵＳＢポートを使用して、コンピュータ１８１２に入力し、コンピュータ１８１２からの情報を出力デバイス１８４０に出力することができる。出力アダプタ１８４２が備えられており、特別なアダプタを必要とする他の出力デバイス１８４０のうちモニタ、スピーカ、およびプリンタなどいくつかの出力デバイス１８４０があることを示している。出力アダプタ１８４２は、例えば、これらに限られないが、出力デバイス１８４０とシステムバス１８１８とを接続する手段となるビデオおよびサウンドカードなどがある。他のデバイスおよび／またはデバイスのシステムはリモートコンピュータ１８４４などの入出力機能を備えることに留意されたい。
【００８３】
コンピュータ１８１２は、リモートコンピュータ１８４４などの１つまたは複数のリモートコンピュータへの論理接続を使用してネットワーク接続環境で動作させることができる。リモートコンピュータ１８４４は、パーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ワークステーション、マイクロプロセッサベースの機器、ピアデバイス、またはその他の共通ネットワークノードなどとすることができ、通常は、コンピュータ１８１２に関係する上述の要素の多くまたはすべてを含む。簡単のため、メモリ記憶装置１８４６のみリモートコンピュータ１８４４とともに例示してある。リモートコンピュータ１８４４は、ネットワークインターフェース１８４８を通じてコンピュータ１８１２に論理的に接続され、通信接続１８５０を介して物理的に接続される。ネットワークインターフェース１８４８は、ローカルエリアネットワーク（ＬＡＮ）およびワイドエリアネットワーク（ＷＡＮ）などの通信ネットワークを含む。ＬＡＮ技術には、Ｆｉｂｅｒ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｄａｔａ  Ｉｎｔｅｒｆａｃｅ（ＦＤＤＩ）、Ｃｏｐｐｅｒ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｄａｔａ  Ｉｎｔｅｒｆａｃｅ（ＣＤＤＩ）、Ｅｔｈｅｒｎｅｔ（登録商標）／ＩＥＥＥ  ８０２．３、Ｔｏｋｅｎ  Ｒｉｎｇ／ＩＥＥＥ  ８０２．５などがある。ＷＡＮ技術には、２地点間接続リンク、統合デジタル通信網（ＩＳＤＮ）などの回線交換ネットワークとその変種、パケット交換ネットワーク、およびデジタル加入者回線（ＤＳＬ）などがある。
【００８４】
通信接続１８５０とは、ネットワークインターフェース１８４８をバス１８１８に接続するために使用されるハードウェア／ソフトウェアのことである。通信接続１８５０は分かりやすくするためにコンピュータ１８１２内に示されているが、コンピュータ１８１２の外部にあってもかまわない。ネットワークインターフェース１８４８の接続に必要なハードウェア／ソフトウェアには、例えば、通常の電話グレードのモデム、ケーブルモデム、およびＤＳＬモデムを含むモデム、ＩＳＤＮアダプタ、およびＥｔｈｅｒｎｅｔ（登録商標）カードなどの内部および外部技術がある。
【００８５】
図１９は、本発明との相互やり取りが可能なコンピューティング環境１９００の実施例を示す概略ブロック図である。システム１９００は、１つまたは複数のクライアント１９１０を備える。クライアント１９１０は、ハードウェアおよび／またはソフトウェア（例えば、スレッド、プロセス、コンピューティングデバイス）とすることができる。システム１９００は、さらに、１つまたは複数のサーバ１９３０も備える。サーバ１９３０もまた、ハードウェアおよび／またはソフトウェア（例えば、スレッド、プロセス、コンピューティングデバイス）とすることができる。サーバ１９３０には、例えば、本発明を採用することにより変換を実行するスレッドを置くことができる。クライアント１９１０とサーバ１９３０との間で可能な通信の１つは、２つ以上のコンピュータプロセス間で伝送されるように適合されたデータパケットの形で実行できる。システム１９００は、クライアント１９１０とサーバ１９３０との間の通信を円滑にするために採用することができる通信フレームワーク１９５０を含む。クライアント１９１０は、クライアント１９１０のローカルにある情報を格納するために使用することができる１つまたは複数のクライアントデータストア１９６０に接続し動作させることができる。同様に、サーバ１９３０は、サーバ１９３０のローカルにある情報を格納するために使用することができる１つまたは複数のサーバデータストア１９４０に接続し動作させることができる。
【００８６】
上述した内容は、本発明の複数の実施例を含んでいる。もちろん、本発明を説明するためにコンポーネントまたは方法の考えられるすべての組み合わせを説明することは不可能であるが、当業者であれば、本発明の他の多くの組み合わせおよび置換が可能であることを理解できるであろう。したがって、本発明は、付属の請求項の精神と範囲内に収まるすべてのそのような変更、修正、および変更形態を包含することが意図されている。さらに、「含む、備える」という言い回しを詳細な説明または請求項で使用している範囲において、このような用語は「備える、含む」という用語と似た使い方をし、これは使用した場合に請求項の中で暫定的用語と解釈する。
【図面の簡単な説明】
【００８７】
【図１】本発明の一態様によるオンラインドキュメントのインデックス作成および／または読み込みを容易にするシステムのブロック図である。
【図２】本発明の一態様によるオンラインドキュメントのインデックス作成および／または読み込みを容易にするシステムのブロック図である。
【図３】本発明の一態様によるオンラインドキュメントのインデックス作成および／または読み込みを容易にする方法を例示する代表的な流れ図である。
【図４】本発明の一態様によるオンラインドキュメントのインデックス作成および／または読み込みを容易にするシステムのブロック図である。
【図５】本発明の一態様によるイメージの解像度を変える例を示す図である。
【図６】単語位置と幅を定義し、本発明の一態様によるそのような定義における許容誤差を定めることを例示する図である。
【図７】本発明の一態様による単語レイアウトを含むイメージ実施例の図である。
【図８】本発明に関して使用することができるハッシュテーブルの実施例の図である。
【図９】図８のハッシュテーブルの３次元図である。
【図１０】本発明の一態様による複数の注釈を含むドキュメント実施例の図である。
【図１１】本発明の一態様によるドキュメント内に存在するノイズをフィルタで除去した後の図１０のドキュメントである。
【図１２】本発明の一態様により格納されているイメージの署名を生成する方法を例示する代表的な流れ図である。
【図１３】本発明の一態様により印刷されたドキュメントのオンラインイメージの署名を生成する方法を例示する代表的な流れ図である。
【図１４】本発明の一態様によるイメージのセグメント分割を例示する図である。
【図１５】本発明の一態様によるドキュメントのイメージの木表現例を示す高水準ブロック図である。
【図１６】本発明の一態様により署名を比較する方法を例示する代表的な流れ図である。
【図１７】本発明に関して使用することができるデータストアの実施例の図である。
【図１８】本発明が機能できる動作環境例の図である。
【図１９】本発明との相互やり取りが可能なコンピューティング環境例の概略ブロック図である。
【符号の説明】
【００８８】
１８２８  オペレーティングシステム
１８３０  アプリケーション
１８３２  モジュール
１８３４  データ
１８１４  処理ユニット
１８１６  システムメモリ
１８２０  揮発性メモリ
１８２２  不揮発性メモリ
１８２６  インターフェース
１８２４  ディスク記憶装置
１８１８  バス
１８４２  出力アダプタ
１８３８  インターフェースポート
１８５０  通信接続
１８４０  出力デバイス
１８３６  入力デバイス
１８４８  ネットワークインターフェース
１８４４  リモートコンピュータ
１８４６  メモリ記憶装置
【図１】
0004718841.tif 000004
【図２】
0004718841.tif 000005
【図３】
0004718841.tif 000006
【図４】
0004718841.tif 000007
【図５】
0004718841.tif 000008
【図６】
0004718841.tif 000009
【図７】
0004718841.tif 000010
【図８】
0004718841.tif 000011
【図９】
0004718841.tif 000012
【図１０】
0004718841.tif 000013
【図１１】
0004718841.tif 000014
【図１２】
0004718841.tif 000015
【図１３】
0004718841.tif 000016
【図１４】
0004718841.tif 000017
【図１５】
0004718841.tif 000018
【図１６】
0004718841.tif 000019
【図１７】
0004718841.tif 000020
【図１８】
0004718841.tif 000021
【図１９】
0004718841.tif 000022