(57)【特許請求の範囲】
【請求項１】
物理媒体上の文書中の複数の画像の位置を決定する方法であって、前記物理媒体上の位置を識別するためのパターンが前記物理媒体上に表示され、ペンまたはスタイラスが前記文書上で動かされている間に前記複数の画像が前記ペンまたはスタイラスに搭載されたカメラによって取り込まれ、前記文書中でストロークを生み出す間に前記複数の画像が前記ペンまたはスタイラスの動きを追跡する前記方法は、
前記複数の画像のうちの少なくとも２つの画像の位置を決定するステップであって、
前記少なくとも２つの画像のそれぞれに取り込まれた前記パターンの一部を検出するステップと、
前記パターンの前記検出された部分を分析して、前記少なくとも２つの画像の前記文書中の位置を決定するステップと
によって、前記少なくとも２つの画像の位置を決定するステップと、
前記位置決定済み画像に基いて前記ストロークを複数のセグメントにセグメント化するステップであって、
前記位置決定済み画像の最初の位置の画像の開始点と前記位置決定済み画像の最後の位置の画像の開始点とを結ぶ線から最も遠い開始点を選択するステップと、
前記最初の位置の画像の開始点と前記選択された開始点との間の部分、及び前記選択された開始点と前記最後の位置の画像の開始点との間の部分をそれぞれ別のセグメントとして指定するステップと
によって、前記複数のセグメントにセグメント化するステップと、
前記複数の画像を、前記ストロークの前記複数のセグメントのうちの１つに対応するグループにグループ化するステップであって、各グループが、
前記対応するセグメントの最初の位置および最後の位置にそれぞれが対応する２つの前記位置決定済み画像、および、
前記対応するセグメントの少なくとも１つの中間の位置に対応する前記複数の画像のうちの少なくとも１つの画像
を含むようにするステップと、
前記各グループについて、前記ストロークの前記対応するセグメントが未完了かどうかを判定するステップであって、前記少なくとも１つの中間の位置が、前記文書中の位置がまだ決定されていない少なくとも１つの画像に対応するかどうかを判定することによって、前記対応するセグメントが未完了かどうかを判定するステップと、
未完了の前記各セグメントについて、少なくとも１つの前記最初の位置および前記最後の位置に対応する前記決定された位置を使用して、前記文書中の位置がまだ決定されていない前記少なくとも１つの画像の前記文書中の位置を決定するステップと
を含み、
前記ペンまたはスタイラスが前記文書上で動かされる前に、前記文書は、前記パターンの一部を不明瞭にするテキストを含み、前記パターンの前記不明瞭な一部は、前記未完了のセグメントの、前記文書中の位置がまだ決定されていない前記少なくとも１つの画像内で取り込まれることを特徴とする方法。
【請求項２】
前記複数の画像はそれぞれ、複数ピクセルの画像であることを特徴とする請求項１に記載の方法。
【請求項３】
物理媒体上の文書中の画像のシーケンスの位置を決定する方法であって、前記物理媒体上の位置を識別するためのパターンが前記物理媒体上に表示され、ペンまたはスタイラスが前記文書上で動かされている間に前記画像のシーケンスが前記ペンまたはスタイラスに搭載されたカメラによって取り込まれる前記方法は、
前記画像のシーケンス中の少なくとも２つの画像に取り込まれた文書部分の位置を、前記少なくとも２つの画像のそれぞれの中の前記パターンの検出された部分に基いて決定するステップと、
前記決定ステップによって位置が決定されている前記文書部分を取り込んだ前記少なくとも２つの画像に基いて、前記画像のシーケンスを複数のセグメントにセグメント化するステップであって、各セグメントが、
前記決定ステップによって位置が決定されている前記文書部分を取り込んだ画像のうちの１つである最初の位置の画像、
前記決定ステップによって位置が決定されている前記文書部分を取り込んだ画像のうちの別の１つである最後の位置の画像、および、
前記画像のシーケンス中の前記最初の位置の画像と前記最後の位置の画像との間で取り込まれている少なくとも１つの中間の位置の画像
を含み、
前記画像のシーケンスは、
前記セグメントの前記最初の位置の画像および前記最後の位置の画像をそれぞれ見つけるステップと、
前記中間の位置の画像について、前記最初の位置の画像および前記最後の位置の画像に取り込まれた前記文書部分の決定された位置とそれぞれ交わるラインから最も遠い前記決定された位置にある前記画像を選択するステップと、
前記最初の位置の画像および前記選択された画像を、第１のセグメントの前記最初の位置の画像および前記最後の位置の画像としてそれぞれ指定し、前記選択された画像および前記最後の位置の画像を、第２のセグメントの前記最初の位置の画像および前記最後の位置の画像としてそれぞれ指定するステップと
によってセグメント化されるステップと、
前記決定ステップによって位置を決定することができなかった前記文書部分を取り込んだ前記中間の位置の画像を有する、前記複数のセグメント中のセグメントを識別するステップと、
前記識別された各セグメントについて、前記決定ステップによって決定された前記最初の位置の画像および前記最後の位置の画像のうちの少なくとも１つに取り込まれた前記文書部分の位置を使用して、前記決定ステップによって位置を決定することができなかった前記中間の位置の画像に取り込まれた前記文書部分の位置を見つけるステップとを備え、
前記画像のシーケンス中の各画像は、複数ピクセルの画像であることを特徴とする方法。
【請求項４】
前記決定ステップによって前記文書中の位置を決定することができなかった複数の中間の位置の画像に取り込まれた前記文書部分の位置を決定するために、少なくとも１つの識別されたセグメントについて、前記最初の位置の画像および前記最後の位置の画像のうちの少なくとも１つに取り込まれた前記文書部分の前記位置を使用するステップ
をさらに含むことを特徴とする請求項３に記載の方法。
【請求項５】
特定の前記識別されたセグメントについて、
ストロークを形成する前記ペンまたはスタイラスの動き、および、
前記特定の識別されたセグメントの前記最初の位置の画像、前記特定の識別されたセグメントの前記最後の位置の画像、および、位置が既に決定され、見つけられた前記文書部分を取り込んだ前記特定の識別されたセグメント中の中間の位置の画像のうちの少なくとも１つに取り込まれた、前記文書部分の位置
に基いて、前記文書中の探索領域を決定するステップと、
前記特定の識別されたセグメント中の別の中間の位置の画像によって取り込まれた前記文書部分の位置を、前記別の中間の位置の画像を前記文書中の前記探索領域と比較することによって見つけるステップと
をさらに備えることを特徴とする請求項４に記載の方法。
【請求項６】
前記探索領域は、前記ペンの決定された最大速度に基いて決定されることを特徴とする請求項５に記載の方法。
【請求項７】
前記探索領域は、既に決定され、見つけられた前記特定の識別されたセグメント中の２つ以上の中間の位置の画像の前記文書部分の位置から計算された、前記ペンの実際の速度に基いて決定されることを特徴とする請求項５に記載の方法。
【請求項８】
前記探索領域は、前記ペンの決定された最大加速度に基いて決定されることを特徴とする請求項５に記載の方法。
【請求項９】
前記決定され、見つけられた、前記画像のシーケンスに取り込まれた前記文書部分の位置を分析するステップと、
前記文書中の画像のシーケンスの位置が決定された結果から、１つまたは複数の誤った位置を切り捨てるステップであって、前記誤った位置は、前記ペンの計算された速度または加速度が所定の閾値を超えた前記文書部分の位置であるステップと
をさらに含むことを特徴とする請求項３に記載の方法。
【請求項１０】
前記分析ステップは、前記決定ステップの結果として誤っていないと決定された前記文書部分の位置を指定することを含むことを特徴とする請求項９に記載の方法。
【請求項１１】
前記識別されたセグメントのそれぞれについて、
前記最初の位置の画像および前記最後の位置の画像のうちの少なくとも１つの前記文書中の前記位置は、前記決定ステップによって決定することができなかった前記文書中の位置にある前記中間の位置の画像とピクセル単位で比較する目的で、前記文書中の探索領域を決定するために使用され、
前記ピクセル単位の比較の結果を使用して、前記決定ステップによって決定することができなかった前記文書中の位置にある前記中間の位置にある画像の前記文書中の位置を見つける
ことを特徴とする請求項３に記載の方法。
【請求項１２】
前記ペンまたはスタイラスが前記文書上で動かされる前に、前記文書は、前記パターンの一部を不明瞭にするテキストを含み、前記パターンの前記不明瞭な一部は、前記決定ステップによって決定することができない前記文書中の位置にある中間の位置の画像中で取り込まれることを特徴とする請求項３に記載の方法。
【請求項１３】
紙の上の位置を識別するための迷路パターンが形成された前記紙の上に印刷された文書中の複数の画像の位置を決定する方法であって、前記複数の画像はペンまたはスタイラスが前記文書上で動かされる間に前記ペンまたはスタイラスに搭載されたカメラによって取り込まれ、前記文書中のストロークを生み出す間に前記画像のシーケンスが前記ペンまたはスタイラスの動きを追跡する前記方法は、
前記画像のシーケンスにおいて少なくとも３つの画像の位置を決定するステップであって、
少なくとも２つの画像のそれぞれに取り込まれた前記迷路パターンの部分を復号するステップと、
前記迷路パターンの前記復号された部分を分析して、前記少なくとも３つの画像の前記文書中の前記位置を決定するステップと
によって、前記少なくとも３つの画像の位置を決定するステップと、
複数のピボット点に従って、前記ストロークを複数のセグメントにセグメント化するステップであって、各セグメントの始点および終点がそれぞれ２つの前記ピボット点によって定義され、前記複数のピボット点は、
前記ストロークが開始する場所、
前記ストロークが終了する場所、および、
前記ストロークが方向を大きく変える少なくとも１つの場所
に対応する位置決定済み画像の決定された位置であり、
前記ストロークは、
前記始点と前記終点との間の前記ピボット点について、前記始点および前記終点に交わる線から最も遠い点を選択するステップと、
前記始点および前記選択されたピボット点をそれぞれ、第１のセグメントの前記始点および前記終点として指定し、前記選択されたピボット点および前記終点をそれぞれ、第２のセグメントの前記始点および前記終点として指定するステップと
によってセグメント化されるステップと、
前記画像のシーケンスを、前記ストロークの前記複数のセグメントの１つに対応するグループにグループ化するステップであって、各グループは、
前記ピボット点に対応する２つの前記位置決定済み画像、および、
前記対応するセグメントの少なくとも１つの中間の位置に対応する前記画像のシーケンス中の少なくとも１つの画像
を含むステップと、
各グループについて、前記対応するセグメントの前記少なくとも１つ中間の位置が、前記文書中でまだ決定されていない位置にある少なくとも１つの画像に対応するかどうかを判定することによって、前記対応するセグメントが未完了かどうかを判定するステップと、
未完了の各セグメントについて、前記最初の位置および前記最後の位置のうちの少なくとも１つに対応する前記決定された位置を使用して、前記文書中でまだ決定されていない位置にある前記少なくとも１つの画像の前記文書中の前記位置を決定するステップとを備え、
前記ペンまたはスタイラスが前記文書上で動かされる前に、前記文書は、前記迷路パターンの一部を不明瞭にするテキストを含み、前記迷路パターンの前記不明瞭な一部は、未完了のセグメントの、まだ決定されていない前記文書中の位置にある前記少なくとも１つの画像内で取り込まれることを特徴とする方法。
【請求項１４】
前記複数の画像はそれぞれ、複数ピクセルの画像であることを特徴とする請求項１３に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像中に取り込まれた文書の一部の位置を決定することに関する。本発明の様々な態様は特に、文書の画像を取り込むことによって文書上のマークの位置を識別することに適用可能である。
【背景技術】
【０００２】
コンピュータに記憶された電子文書は、書面による文書に勝るいくつかの利点をもたらすが、多くのユーザは、電子文書の印刷バージョンを使用していくつかの作業を実施し続けている。これらの作業には、例えば文書を読むことや文書に注釈を付けることが含まれる。通常、注釈はユーザによって印刷文書に直接書き込まれるので、注釈が付けられると文書の紙バージョンは特に重要性を帯びる。しかし、文書の印刷バージョンに直接注釈を付けることに伴う問題の１つは、後で注釈を電子形式に変換するのが難しいことである。理想的には、手書きの注釈が文書の紙バージョンに対応するのと同様にして、電子的に記憶された注釈が文書の電子バージョンに対応すべきである。
【０００３】
この対応付けは通常、元のユーザまたは別のユーザが注釈に目を通し、それらを自分でコンピュータに入力することを必要とする。場合によっては、ユーザは、紙の文書に書き込まれた注釈を電子的にスキャンし、それによって新しい電子文書を作成することもある。これらの複数のステップのせいで、文書の印刷バージョンと文書の電子バージョンとの間で一致を図ることは、繰り返し処理するために困難なものになる。さらに、スキャンされた画像は編集できないことが多い。そのため、文書の元のテキストから注釈を分離する方法がない場合がある。これにより、注釈の使用は困難になる。
【０００４】
この問題に対処するために、印刷文書にペンで書き込まれた注釈を取り込むためのペンが開発された。このタイプのペンはカメラを備えており、カメラは、ユーザが注釈を書き込むのに伴って印刷文書の画像を取り込む。しかし、このタイプのペンのいくつかの例では、カメラに見えないインクを採用する場合がある。例えばペンは、カメラに対してノンカーボンインクおよび赤外線照明を採用する場合があり、それによりカメラは、このインクで書き込まれた注釈を「見る」ことができない。このタイプのペンでは、ペンは、注釈が書き込まれる間にペンが取り込んだ画像から、文書上に注釈を形成するペンチップの動きを推測することになる。しかし、画像を元の電子文書に関連付けるには、文書に対して相対的な画像の位置を決定しなければならない。そのため、このタイプのペンはしばしば、紙の上の様々な位置を一意に識別するパターンを含む紙と共に利用される。画像を受け取ったコンピュータは、このパターンを分析することによって、紙のどの部分が（したがって印刷文書のどの部分が）画像中に取り込まれたかを決定することができる。
【０００５】
【非特許文献１】Heung-Yeung Shun and Richard Szeliski, "Panoramic Image Mosaics," Microsoft Research Technical Report MSR-TR-97-23, 1997年9月1日発行、2001年10月更新
【発明の開示】
【発明が解決しようとする課題】
【０００６】
このようなパターン付きの紙またはその他の媒体を使用することにより、紙の文書上の書き込まれた注釈を電子形式に変換して、文書の電子バージョンに正しく関連付けることができるが、この技法は常に信頼できるとは限らない。例えば、紙の上のテキストを含む文書は、パターンの領域を不明瞭にすることがある。これらの領域のうちの１つの画像をペンが取り込んだ場合、コンピュータはこのパターンを使用しても、画像によって取り込まれた文書部分の位置を正確に決定できないことがある。そうではなくコンピュータは、画像中に取り込まれた文書部分の位置を識別するための代替技法を採用しなければならない。例えばコンピュータは、取り込まれた画像を電子文書とピクセル単位で比較する。
【０００７】
ピクセル単位の比較によって通常、取り込まれた画像中の文書部分が識別されるが、この技法は処理オーバーヘッドが大きい。例えば、この技法を実施するには通常、取り込まれた画像を歪ませて（ｗａｒｐ）文書画像とピクセル単位でマッチさせることができるように、取り込まれた画像と文書画像との間の変形（例えば回転）およびスケールを最初に推定しなければならない。変形が未知である場合は、可能なすべての回転およびスケールを考慮しなければならない。さらに、画像中の基準ピクセルを選択する。次いで、画像基準ピクセルが電子文書中の第１の位置と比較されるように、歪ませた画像中のあらゆるピクセルを電子文書中の対応するピクセルと比較する。次いで、この比較を繰り返し、最終的に基準ピクセルを電子文書中の各位置と比較しなければならない。画像ピクセルと電子文書とが最高の対応を有する比較によって、電子文書に対して相対的な基準ピクセルの位置が識別され、それにより、画像中に取り込まれた文書部分が識別される。したがって、画像を文書全体とピクセル単位で比較する必要なしに、取り込まれた画像中の文書部分の位置をコンピュータが決定できるようにする技法を提供することが望ましいであろう。
【課題を解決するための手段】
【０００８】
有利なことに、本発明の様々な実施形態は、取り込まれた画像に対応する文書部分を決定するための効率的な技法を提供する。
【０００９】
本発明の様々な実施形態によれば、ユーザがペンを利用して文書中にストロークを生み出すとき、ペンに搭載されたカメラが一連の画像を取り込む。いくつかの画像の位置は、例えば、画像によって取り込まれた文書上のパターンを分析することから、または画像を文書とピクセル単位で比較することから決定される。しかし、他の画像の位置は、他の技法を使用して決定する必要がある。
【００１０】
これらの位置未決定の画像の位置を効率的に決定するために、画像のシーケンス全体を、ストロークの形状に対応するグループにセグメント化する。このようにすることで、ストロークの相対的に線形のセクションに対応する画像が共にグループ化されることになる。また、１つのセグメント中の画像はすべて通常は近接しているので、セグメント中の位置決定済みの画像に関する情報を利用して、そのセグメント中の位置未決定の画像の位置を決定することができる。例えば、前の位置決定済み画像の位置と、ペンの最大速度または実際速度とに基づいて、位置未決定の画像に対する文書探索領域を確立することができる。さらに、ペンの姿勢は短時間で大きく変化するとは予想されないので、位置決定済み画像の回転およびスケール（アフィン変換。これは透視変換として精緻にすることができる）を、位置未決定の画像の回転およびスケールの推定値として使用することができる。この推定された回転およびスケールを使用して、位置未決定の画像を歪ませて文書画像の配向およびスケールにマッチさせることができる。次いで、歪ませた位置未決定の画像と文書探索領域との間でピクセル単位の比較を実施することができる。
【発明を実施するための最良の形態】
【００１１】
動作環境  
図１に、本発明の様々な態様を実施するのに使用できる従来型の汎用ディジタルコンピューティング環境の機能ブロック図の一例を示す。図１で、コンピュータ１００は、処理ユニット１１０と、システムメモリ１２０と、システムメモリを含めた様々なシステムコンポーネントを処理ユニット１１０に結合するシステムバス１３０とを備える。システムバス１３０は、様々なバスアーキテクチャのいずれかを用いた、メモリバスまたはメモリコントローラ、周辺バス、ローカルバスを含めて、いくつかのタイプのバス構造のいずれかとすることができる。システムメモリ１２０は、読取り専用メモリ（ＲＯＭ）１４０およびランダムアクセスメモリ（ＲＡＭ）１５０を含む。
【００１２】
ＲＯＭ１４０には、起動中などにコンピュータ１００内の要素間で情報を転送するのを助ける基本ルーチンを含むＢＩＯＳ（ｂａｓｉｃ  ｉｎｐｕｔ／ｏｕｔｐｕｔ  ｓｙｓｔｅｍ）１６０が記憶されている。コンピュータ１００はまた、ハードディスク（図示せず）に対して読み書きするためのハードディスクドライブ１７０と、取外し可能な磁気ディスク１９０に対して読み書きするための磁気ディスクドライブ１８０と、ＣＤ  ＲＯＭやその他の光媒体など取外し可能な光ディスク１９２に対して読み書きするための光ディスクドライブ１９１も備える。ハードディスクドライブ１７０、磁気ディスクドライブ１８０、光ディスクドライブ１９１は、それぞれハードディスクドライブインタフェース１９２、磁気ディスクドライブインタフェース１９３、光ディスクドライブインタフェース１９４によってシステムバス１３０に接続される。これらのドライブおよび関連するコンピュータ可読媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、その他のデータの不揮発性記憶域をパーソナルコンピュータ１００に提供する。磁気カセット、フラッシュメモリカード、ディジタルビデオディスク、ベルヌーイカートリッジ、ランダムアクセスメモリ（ＲＡＭ）、読取り専用メモリ（ＲＯＭ）など、コンピュータからアクセス可能なデータを記憶することのできるその他のタイプのコンピュータ可読媒体をこの例示的な動作環境で使用することもできることは、当業者には理解されるであろう。
【００１３】
ハードディスクドライブ１７０、磁気ディスク１９０、光ディスク１９２、ＲＯＭ１４０、またはＲＡＭ１５０には、いくつかのプログラムモジュールを記憶することができる。これらには、オペレーティングシステム１９５、１つまたは複数のアプリケーションプログラム１９６、その他のプログラムモジュール１９７、プログラムデータ１９８が含まれる。ユーザは、キーボード１０１やポインティングデバイス１０２などの入力デバイスを介して、コンピュータ１００にコマンドおよび情報を入力することができる。その他の入力デバイス（図示せず）には、マイクロホン、ジョイスティック、ゲームパッド、衛星受信アンテナ、スキャナなどを含めることができる。これらおよび他の入力デバイスは、システムバスに結合されたシリアルポートインタフェース１０６を介して処理ユニット１１０に接続されることが多いが、パラレルポート、ゲームポート、ユニバーサルシリアルバス（ＵＳＢ）など、その他のインタフェースで接続されてもよい。さらに、これらのデバイスは、適したインタフェース（図示せず）を介してシステムバス１３０に直接に結合することもできる。モニタ１０７または他のタイプの表示デバイスも、ビデオアダプタ１０８などのインタフェースを介してシステムバス１３０に接続される。モニタに加えて、パーソナルコンピュータは通常、スピーカやプリンタなど、その他の周辺出力デバイス（図示せず）も備える。好ましい一実施形態では、フリーハンド入力をディジタルに取り込むために、ペンディジタイザ１６５および付属のペンまたはスタイラス１６６が提供される。ペンディジタイザ１６５とシリアルポートとの間の直接接続が示されているが、実際には、ペンディジタイザ１６５は、当技術分野で知られているようにパラレルポートまたは他のインタフェースとシステムバス１３０とを介して、処理ユニット１１０に直接に結合されてもよい。さらに、ディジタイザ１６５はモニタ１０７とは別に示されているが、ディジタイザ１６５の使用可能な入力領域がモニタ１０７の表示領域と同じ領域を占めることが好ましい。さらに、ディジタイザ１６５はモニタ１０７に統合されてもよく、あるいはモニタ１０７の上に置かれるかそうでなければ付加される別個のデバイスとして存在してもよい。
【００１４】
コンピュータ１００は、リモートコンピュータ１０９など１つまたは複数のリモートコンピュータへの論理接続を用いて、ネットワーク化された環境で動作することができる。リモートコンピュータ１０９は、サーバ、ルータ、ネットワークＰＣ、ピアデバイス、またはその他の一般的なネットワークノードとすることができ、通常はコンピュータ１００に関して上述した要素の多くまたはすべてを備える。ただし図１にはメモリ記憶デバイス１１１だけが示してある。図１に示す論理接続は、ローカルエリアネットワーク（ＬＡＮ）１１２およびワイドエリアネットワーク（ＷＡＮ）１１３を含む。このようなネットワーキング環境は、オフィス、企業全体のコンピュータネットワーク、イントラネット、インターネットでよくみられる。
【００１５】
ＬＡＮネットワーキング環境で使用されるときは、コンピュータ１００は、ネットワークインタフェースまたはアダプタ１１４を介してローカルエリアネットワーク１１２に接続される。ＷＡＮネットワーキング環境で使用されるときは、パーソナルコンピュータ１００は通常、インターネットなどのワイドエリアネットワーク１１３を介した通信を確立するためのモデム１１５または他の手段を備える。モデム１１５は内蔵でも外付けでもよく、シリアルポートインタフェース１０６を介してシステムバス１３０に接続される。ネットワーク化された環境では、パーソナルコンピュータ１００に関して示したプログラムモジュールまたはその一部をリモートのメモリ記憶デバイスに記憶することができる。
【００１６】
図示のネットワーク接続は例示的なものであり、コンピュータ間で通信リンクを確立するためのその他の技法を使用することもできることは理解されるであろう。ＴＣＰ／ＩＰ、Ｅｔｈｅｒｎｅｔ（登録商標）、ＦＴＰ、ＨＴＴＰ、Ｂｌｕｅｔｏｏｔｈ、ＩＥＥＥ８０２．１１ｘなど、様々な周知のプロトコルのいずれかがあることが想定され、システムをクライアント‐サーバ構成で動作させて、ユーザがウェブベースのサーバからウェブページを取り出せるようにすることができる。様々な従来型のウェブブラウザのいずれかを使用して、ウェブページ上でデータを表示および操作することができる。
【００１７】
画像取込みデバイス  
本発明の様々な実施形態を利用して、一連の画像によって取り込まれた文書部分の位置を決定することができる。前述のように、画像中に取り込まれた文書部分の位置の決定を用いて、紙、表示画面、または文書を表示しているその他の媒体とのユーザ対話の位置を突き止めることができる。本発明のいくつかの実施形態によれば、画像は、紙の上にインクで書くのに使用されるインクペンによって得ることができる。本発明の他の実施形態では、ペンは、文書を表示しているディジタイザの表面に電子インクで「書く」のに使用されるスタイラスとすることができる。
【００１８】
図２Ａおよび２Ｂに、本発明の様々な実施形態により採用することのできるペン２０１の説明となる例を示す。ペン２０１は、チップ２０２およびカメラ２０３を備える。チップ２０２は、インク筒を備えるものでもよく、そうでなくてもよい。カメラ２０３は、表面２０７から画像２０４を取り込む。ペン２０１はさらに、破線のボックス２０６中に表すように追加のセンサおよび／またはプロセッサを備えてもよい。これらのセンサおよび／またはプロセッサ２０６はまた、別のペン２０１および／またはパーソナルコンピュータに（例えばＢｌｕｅｔｏｏｔｈや他の無線プロトコルを介して）情報を送信する機能を備えることができる。
【００１９】
図２Ｂは、カメラ２０３によって見られる画像を表す。例示的な一例では、カメラ２０３によって取り込まれる画像の解像度はＮ×Ｎピクセルである（Ｎ＝３２）。したがって図２Ｂは、縦３２ピクセル×横３２ピクセルの例示的な画像を示す。Ｎのサイズは調整可能であり、Ｎの値が高いほど画像解像度は高い。また、ここでは例示のために、カメラ２０３によって取り込まれる画像を正方形として示しているが、カメラの視野には、当技術分野で知られている他の形状を含めることもできる。
【００２０】
カメラ２０３によって取り込まれる画像は、画像フレームのシーケンス｛Ｉｉ｝として定義することができ、Ｉｉはサンプリング時間ｔｉでペン２０１によって取り込まれる。サンプリングレートは、システム構成および性能要件に応じて高くすることも低くすることもできる。取り込まれる画像フレームのサイズは、システム構成および性能用件に応じて大きくすることも小さくすることもできる。また、カメラ２０３によって取り込まれた画像は、処理システムが直接使用してもよく、あるいは事前フィルタリング（ｐｒｅ−ｆｉｌｔｅｒｉｎｇ）にかけてもよいことを理解されたい。事前フィルタリングは、ペン２０１中で行ってもよく、ペン２０１の外（例えばパーソナルコンピュータ中）で行ってもよい。
【００２１】
図２Ａには、位置２０４からのパターンの画像２１０が形成される画像面２０９も示してある。対象面２０７上のパターンから受け取られた光が、レンズ２０８によって集束される。本発明の様々な実施形態によれば、レンズ２０８は単一レンズでもマルチパートレンズシステムでもよいが、ここではわかりやすくするために単一レンズとして表してある。画像取込みセンサ２１１が画像２１０を取り込む。
【００２２】
画像センサ２１１は、画像２１０を取り込むのに十分な大きさとすることができる。あるいは画像センサ２１１は、位置２１２でペンチップ２０２の画像を取り込むのに十分な大きさとすることができる。参照のために、位置２１２における画像を仮想ペンチップ（ｖｉｒｔｕａｌ  ｐｅｎ  ｔｉｐ）と呼ぶ。ペンチップとレンズ２０８と画像センサ２１１との関係は一定なので、画像センサ２１１に対する仮想ペンチップの位置は固定であることに留意されたい。
【００２３】
前述のように、ペン２０１は通常、紙に印刷された文書など、媒体上の位置を識別するためのパターンを表示する媒体と共に使用される。有利にも、このパターンを使用して、カメラ２０３によって取り込まれた画像２１０を媒体の体裁に対応する形式に変換することができる。例えば、以下の変換ＦＳ→Ｐは、カメラ２０３によって取り込まれた画像２１０を紙上の実際の画像に変換する。
【００２４】
Ｌｐａｐｅｒ＝ＦＳ→Ｐ（ＬＳｅｎｓｏｒ）  
筆記中、ペンチップと紙は同じ面上にある。したがって、仮想ペンチップから実際のペンチップへの変換もまたＦＳ→Ｐであり、以下のとおりである。  
Ｌｐｅｎｔｉｐ＝ＦＳ→Ｐ（Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐ）  
変換ＦＳ→Ｐは、アフィン変換として推定することができる。これは、以下のようにＦＳ→Ｐの推定値として単純化される。
【００２５】
【数１】
0004652823.tif 000002
【００２６】
上式で、θｘ、θｙ、ｓｘ、ｓｙは、位置２０４で取り込まれたパターンの２つの配向の回転およびスケールである。さらに、取り込まれた画像を紙上の対応する実際の画像とマッチさせることによって、Ｆ’Ｓ→Ｐを精緻にすることができる。「精緻にする」とは、再帰法（ｒｅｃｕｒｓｉｖｅ  ｍｅｔｈｏｄ）と呼ばれる一種の最適化アルゴリズムによって、変換ＦＳ→Ｐのより正確な推定値を得ることを意味する。再帰法では、行列Ｆ’Ｓ→Ｐを初期値として扱う。精緻にされた推定値は、ＳとＰの間の変換をより正確に表す。
【００２７】
較正によって、仮想ペンチップの位置をさらに正確に決定することができる。仮想ペンチップの位置を較正するために、ユーザは、ペンチップ２０２を紙上の既知の位置Ｌｐｅｎｔｉｐに配置する。次に、ユーザはペンを傾けて、カメラ２０３が種々のペン姿勢で一連の画像を取り込めるようにする。取り込まれた各画像につき、変換ＦＳ→Ｐが得られる。この変換から、以下のように仮想ペンチップの位置Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐを得ることができる。  
Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐ＝ＦＰ→Ｓ（Ｌｐｅｎｔｉｐ）
Ｌｐｅｎｔｉｐは（０，０）に初期化され、以下のようになる。  
ＦＰ→Ｓ＝（ＦＳ→Ｐ）−１ 
各画像につき得られたＬｖｉｒｔｕａｌ−ｐｅｎｔｉｐを平均することによって、仮想ペンチップの位置Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐを決定することができる。Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐを使用して、Ｌｐｅｎｔｉｐのより正確な推定値を得ることができる。何回か繰り返した後、正確な仮想ペンチップの位置Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐを決定することができる。
【００２８】
媒体上の位置を識別するためのパターン  
前述のように、本発明の様々な実施形態を利用して、取り込まれた画像に対応する文書部分が決定されるが、文書を表示する媒体はまた、媒体上の様々な位置を識別するためのパターンを備える。したがってこのパターンは、表示された形の符号化済みデータストリームと考えることができる。パターンを表示する媒体は、印刷された紙（またはその他の物理媒体）でもよく、あるいは、符号化済みデータストリームを別の画像または画像セットと共に投影する表示装置でもよい。例えば、符号化済みデータストリームは、紙の上の物理的画像として、または表示画像の上に重なる画像として表されてもよく、あるいは、表示画面と結合しているかまたは表示画面の上に重なる物理的な符号化済みパターン（すなわち修正不可能なパターン）でもよい（したがって、ペンによって取り込まれたどんな画像部分も表示画面上で位置決定可能である）。
【００２９】
図３Ａに、媒体上の位置を識別するためのパターン中に第１ビットおよび第２ビットを符号化する符号化技法の一例を示す。第１ビット３０１（例えば値「１」）が、黒いインクの列で表されている。第２ビット３０２（例えば値「０」）が、黒いインクの行で表されている。ただし、任意の色のインクを使用して様々なビットを表すことができることを理解されたい。選択されるインク色の要件は、画像取込みシステムによって区別可能なように媒体の背景と強い対比をなすことだけである。この例では、図３Ａのビットは３×３のドット行列で表されている。行列のサイズは、媒体の画像を取り込むのに使用される画像取込みシステムのサイズおよび解像度に基づいて、望ましい任意のサイズに修正することができる。
【００３０】
図３Ｃ〜３Ｅに、値０と１のビットの代替表現を示す。図３Ａ〜３Ｅのサンプル符号化に関する１または０の表現は、影響なく交換できることを理解されたい。図３Ｃには、インタリーブ構成で２つの行または列を占めるビット表現を示す。図３Ｄには、断続形式の行および列の代替ピクセル構成を示す。最後に図３Ｅには、不規則な間隔のフォーマットの列および行のピクセル表現を示す（例えば２つの黒いドットの後に１つの空白ドットが続く）。
【００３１】
基礎をなすグリッドを水平および垂直でない構成に回転させること（例えば正しいパターン配向が４５度である場合）を含めて、代替のグリッド整列も可能であることに留意されたい。ユーザは他のパターンよりも先に水平および垂直のパターンに気付く傾向があるので、水平および垂直でない構成を用いることで、ユーザの視覚的混乱をなくすという利点をおそらくもたらすことができる。ただし話を簡単にするために、グリッドの配向（基礎をなすグリッドの水平と垂直の配向、ならびにその他の望ましい任意の回転）を、事前定義済みのグリッド配向と総称する。
【００３２】
再び図３Ａを参照するが、１ビットが３×３の要素行列で表される場合であって、撮像システムが３×３領域で１つの黒い行と２つの白い行を検出した場合は、この領域は値０（または値１）として検出される。１つの黒い列と２つの白い列を含む３×３領域が検出された場合は、この領域は値１（または値０）として検出される。したがって、図２Ｂ中の画像２１０のサイズが３２×３２ピクセルであって、各符号化ユニットサイズが３×３ピクセルである場合は、取り込まれる符号化済みユニットの数は約１００ユニットになるはずである。符号化ユニットサイズが５×５である場合は、取り込まれる符号化済みユニットの数は約３６個になるはずである。
【００３３】
図３Ａに示すように、複数のピクセルまたはドットを使用して１ビットを表すことができる。単一のピクセル（またはドット）を使用して１ビットを表すのは脆弱である。埃、紙の折り目、平らでない表面などにより、データユニットの単一要素表現を読み取る際に困難が生じる。ただし、複数の要素を使用してビットを表す場合でも、文書中のタイプ入力テキストなど、パターン付き媒体上に表示された他のテキストが、やはりパターン中の１つまたは複数のビットを不明瞭にすることもある。
【００３４】
ビットストリームを使用して、図３Ｂのグラフィカルパターン３０３が生み出される。グラフィカルパターン３０３は、１２行と１８列を含む。より具体的には、これらの行と列は、ビット表現３０１および３０２を使用してビットストリームをグラフィカルパターン３０３に変換することによって形成される。したがって、図３Ｂのパターン３０３は、以下のビット表現を有するものと見なすことができる。
【００３５】
【数２】
0004652823.tif 000003
【００３６】
様々なビットストリームを使用して、図３Ｂに示す画像３０３を生み出すことができる。例えば、１と０のランダムシーケンスまたは擬似ランダムシーケンスを使用することができる。ビットシーケンスは、行、列、対角線で構成することができ、あるいはその他の任意の定式的な順序付けに従うこともできる。例えば、上記の行列は、左から右に進んで下に移る場合、以下のビットストリームによって形成することができる。
【００３７】
０１０００１１１０１１００１００１０００１１１００１１１０１００１１００  
上から下に進んで右に移る場合、上記の行列は、以下のビットストリームによって形成することができる。  
０１０１１１００００１１００１００１１０１００１１００１１１１０００１０
斜めに進んで折り返す場合、上記の行列は、以下のビットストリームを表することができる。  
０１１００００００１０１０１０１１０００００１１１１１１１０１０１０１０
図３Ｂは、画像３０３からのピクセルブロックの拡大も含む。拡大３０４〜２１１は、５×５のピクセルブロックを示す。ピクセルブロック３０４は、白い行の間の１つの黒い行を示す。ピクセルブロック３０５は、白い列の間の１つの黒い列を示す。ピクセルブロック３０６は左下のコーナを示す。ピクセルブロック３０７は右上のコーナを示す。ピクセルブロック３０８は、左側に半分の黒い行が付いた黒い列を示す。ピクセルブロック３０９は、上に半分の黒い列が付いた黒い行を示す。ピクセルブロック３１０は半分の黒い行を示す。ピクセルブロック３１１は半分の黒い列を示す。ピクセルブロックの組合せを分析すると、ピクセルの組合せはすべて、ピクセルブロック３０４〜３１１にみられる画像セグメントで形成できることが理解されるはずである。図３Ｂに示すパターンタイプは、四方すべてが完全に囲まれる領域のない迷路を線セグメントが形成するように見えるので、「迷路」パターンと呼ぶことができる。
【００３８】
さらに、図３Ｆ〜３Ｉに示すピクセルの４つの「コーナ」の組合せもそれぞれ、画像３０３中に示す迷路パターンに見出されることが予想されるであろう。しかし、図３Ｂからわかるように、８つのピクセルブロック３０４〜３１１には、実際には３つのタイプのコーナしかない。この例では、図３Ｆに示すピクセルの組合せのコーナはない。このようにして特定のタイプのコーナを除去するように画像セグメント３０１および３０２を選択することにより、不足しているコーナタイプに基づいて、取り込まれた画像の配向を決定することができる。
【００３９】
例えば図４に示すように、カメラ２０３によって取り込まれた画像４０１を分析し、その配向を、画像４０１で実際に表される位置に対して解釈可能なように決定することができる。まず、画像４０１をよく調べ、画像４０１のどのピクセルが迷路パターンを形成するか、ならびに、パターンのピクセルが水平および垂直に整列するよう画像を回転させるのに必要な角度θを決定する。前に論じたように、本発明の様々な実施形態では、基礎をなすグリッドを水平および垂直でない構成に回転させること（例えば正しいパターンの配向が４５度の場合）を含めて、代替のグリッド整列も可能であることに留意されたい。
【００４０】
次に、画像４０１を分析して、どのコーナが不足しているかを決定する。画像４０１を復号準備のできた画像４０３まで回転させるのに必要な回転量ｏは、ｏ＝（θ＋回転量｛どの角が不足しているかによって定義される｝）として示される。この回転量を図５の式で示す。再び図４を参照するが、まず、水平および垂直（または他の事前定義済みグリッド配向）の構成のピクセルに達するように角度θをピクセルレイアウトによって決定し、画像を４０２に示すように回転させる。次いで、分析を行って不足のコーナを決定し、画像６０２を画像６０３まで回転させ、画像を復号に向けて準備する。ここでは、画像を反時計回りに９０度回転させており、それにより画像６０３は正しい配向を有し、これを復号に使用することができる。
【００４１】
回転角度θは、不足のコーナを反映するよう画像６０１を回転させる前に適用しても後に適用してもよいことを理解されたい。また、取り込まれた画像中の雑音を考慮して、すべての４つのコーナタイプがあるものとしてもよいことを理解されたい。したがって、本発明の様々な実施形態では、各タイプのコーナの数を数えることができ、最も少ないコーナの数を有するタイプを不足のコーナタイプとして決定することができる。
【００４２】
最後に、画像４０３中の符号を読み出し、画像３０３を生み出すのに使用された元のビットストリームと相関させる。相関はいくつかの方法で実施することができる。例えば再帰的手法で行うことができ、その場合、回復されたビットストリームを、元のビットストリーム内にある他のすべてのビットストリームフラグメントと比較する。第２に、回復されたビットストリームと元のビットストリームとの間で、例えばこの２つのビットストリーム間のハミング距離を使用して統計分析を行うことができる。様々な手法を使用して、回復されたビットストリームの位置を元のビットストリーム内で決定できることを理解されたい。
【００４３】
以上のことから、前述の迷路パターンを使用して、紙やディジタイザ表示装置などの媒体の表面に情報を符号化することができることが理解されるであろう。次いでこの情報を、ペン２０１のカメラ２０３で１つまたは複数の画像中に取り込み、復号することができる。媒体の表面上に符号化することのできる情報のうち、特に有用なタイプの情報は、位置情報である。ビットストリームの各部分が媒体上で繰り返されない場合、コンピュータ１０１は、特定のビットストリームを含む文書部分を決定することができる。
【００４４】
パターンの完全な部分が画像中に取り込まれた場合、コンピュータ１０１は、前述のように、画像中に取り込まれた文書部分を決定することができる。しかし場合によっては、パターンの一部が不明瞭なことがある。例えば、媒体が例えばタイプ入力テキストを含む文書である場合、このテキストはパターン中の１つまたは複数のビットを部分的に不明瞭にすることがある。前の例（各ビットが３×３のピクセル行列で構成され、カメラ２０３の解像度が３２×３２ピクセルの例）では、コンピュータ１０１は、６０個以上のビットを画像から識別することができる場合、画像中に取り込まれた文書部分の位置を決定できる可能性が非常に高い。しかし、３６から６０個のビットしか画像中で識別できない場合、コンピュータ１０１はなお、画像中に取り込まれた文書部分の位置を決定することができる。さらに、画像から識別できるビットが３５個以下である場合、コンピュータ１０１は、画像中に取り込まれた文書部分を決定することはできない。
【００４５】
ストロークで取り込まれる画像  
例示した本発明の実施形態では、前に詳細に述べたように、文書上でストロークを形成するインクはカメラ２０３に見えない。そうではなくカメラ２０３は、ペンが動いてストロークを形成するのに伴って、文書の画像を取り込むだけである。実際のペンチップの位置、したがってストロークの位置は、較正パラメータを使用して画像の中心の位置をずらすことによって推測される。例えば図６に、ペン２０１を使用して文書上に形成することのできるストロークに対応するストロークパス６０１の例を示す。ストロークパス６０１は、ストロークの形状を辿ってはいるが、ストロークからずれている。ユーザがペン２０１を動かしてストロークを形成するのに伴って、カメラ２０３は、ストロークパス６０１に沿って文書の画像を周期的に取り込む。それにより、図７に示すように、カメラ２０３は文書の一連の画像７０１Ａ〜７０１Ｘを取り込むことになり、各画像の中心はストロークパス６０１上にくる。そのため、各画像７０１Ａ〜７０１Ｘの中心は、実際のストロークパス６０１上にくる。例えば図８に、それぞれ画像７０１Ａ〜７０１Ｘの中心である一連の点８０１Ａ〜８０１Ｘを示す。ただし、本発明の他の実施形態では、異なる構成を採用してもよいことを理解されたい。例えば、本発明の代替実施形態では、取り込まれる画像の中心はペン２０１の実際のチップ２０２に対応するものとすることもできる。
【００４６】
前述のように、文書は、文書の様々な位置を識別するビット情報を含むパターンを備えることになる。したがって、各画像７０１Ａ〜７０１Ｘは、このパターンの一部を含むことができる。場合によっては、取り込まれた画像は、コンピュータ１０１などのコンピュータが画像の位置を決定するのに（すなわち画像中に取り込まれた文書部分の位置を決定するのに）十分なパターンを含む。あるいは、１つまたは複数の画像の位置は、例えば画像を文書とまたは文書の選択部分とピクセル単位で比較することによって得ることができる。
【００４７】
一方、前述のように、画像から識別されるビットの数が不十分な場合は、コンピュータ１０１は、どの文書部分が画像中に取り込まれたかを決定することができない。そうではなくコンピュータ１０１は、代替技法を利用して、どの文書部分が画像中に取り込まれたかを決定しなければならない。文書が電子形式で記憶されており、この文書画像に対する取り込まれた画像の回転およびスケールを推定することができる場合、コンピュータ１０１は、回転されスケールされた画像中のあらゆるピクセルを電子文書中のあらゆる位置とピクセル単位で比較することができる。この技法は、非常に多くの比較プロセスを必要とすることがある。例えば、電子文書のページ１つが１４１０×２０１９ピクセルを含む場合があり、したがって２８８９０９０（１４１０×２０１９）回の比較が必要である。加えて、各比較プロセスでは非常に多くのピクセルを比較する。例えば、取り込まれた画像が３２×３２ピクセルを含む場合があり、したがって各比較では１０２４（３２×３２）個のピクセルを比較する。さらに、取り込まれた画像の回転およびスケールを推定することができない場合は、すべての可能な回転およびスケールを考慮しなければならない。したがってこの技法は、非常に大きなプロセッサオーバーヘッドを要し、また時間がかかる。そうではなくコンピュータ１０１は、後でより詳細に論じるように、本発明の様々な実施形態により局所的な高速画像マッチを実施することによって、画像の位置をより効率的に素早く決定することができる。
【００４８】
図９に、本発明の様々な実施形態により高速画像マッチを実施するために利用できるツール９０１を示す。ツール９０１は、画像受領モジュール９０３、セグメント化モジュール９０５、セグメント完了モジュール９０７、結果切捨てモジュール９０９を備える。後でより詳細に論じるように、画像受領モジュール９０３が、物理媒体上に表示された文書の一部の画像を受け取る。各画像の中心は、実際のインクストロークからずれてストロークパス６０１上にくる。次いで、セグメント化モジュール９０５が各画像を分析して、ストロークの形状に対応する画像のシーケンスをセグメント化する。セグメントが決定されると、セグメント完了モジュール９０７が、各セグメント中の各画像の位置を決定することによって、各セグメントを「完了」させる。次いで、結果切捨てモジュール９０９が、セグメント完了モジュール９０７によって誤って決定された位置結果を切り捨てる。位置未決定の画像に対応する文書部分を決定する方法の１つを、図１０Ａ〜１０Ｃに示すフローチャートに述べるが、これについても後でより詳細に述べる。
【００４９】
画像のセグメント化  
ストロークパスに沿って取り込まれた画像を分析するとき、コンピュータ２０１はまず、例えば前に詳細に述べた迷路パターンなど、文書中に提供されたパターンを使用して、各画像を位置決定することを試みる。パターンを復号することによって画像をうまく位置決定することができない場合は、第１の画像と文書とをピクセル単位で比較する（または、文書中で公算の高い対応領域を識別することができれば、それらの公算の高い対応領域と比較する）。このような比較によって第１の画像をうまく位置決定することができた場合は、後でより詳細に論じる局所的な位置特定プロセスを使用して、残りのフレームを分析する。第１の画像をうまく位置決定することができない場合は、ピクセル単位の比較を用いて次のフレームを分析する。このプロセスを、画像がうまく位置決定できるまで、またはどの画像も位置決定できないと判定されるまで継続する。どの画像も位置決定できない場合は、このストロークは失われる（すなわちこのストロークの位置を決定することはできない）。位置決定された画像の中心を、以下では「開始」点と呼ぶ。というのは、これらの点は、ストロークパス６０１に沿った位置未決定の画像の位置を決定するためのベースラインとして使用されることになるからである。したがって、パターンの使用によって、またはピクセル単位の比較によってうまく位置決定された各フレームの中心は、開始点である。
【００５０】
再び図８を参照すると、この図には様々な点８０１Ａ〜８０１Ｘが示してあり、各点はそれぞれ画像７０１Ａ〜７０１Ｘの中心である。この図では、円で表された点は開始点である。したがって、点８０１Ａ、８０１Ｃ、８０１Ｆ、８０１Ｉ、８０１Ｋ、８０１Ｏ、８０１Ｑ、８０１Ｔ、８０１Ｘは開始点である。星で表された点は、まだ位置決定されていない画像（すなわち識別されない文書部分を取り込んだ画像）の中心である。したがって、点８０１Ｂ、８０１Ｄ、８０１Ｅ、８０１Ｇ、８０１Ｈ、８０１Ｊ、８０１Ｌ、８０１Ｍ、８０１Ｎ、８０１Ｐ、８０１Ｒ、８０１Ｓ、８０１Ｕ、８０１Ｖ、８０１Ｗ、８０１Ｘは、位置未決定の点である。
【００５１】
次に図１０Ａに移るが、ステップ１００１で、画像（またはフレーム）のシーケンスをセグメント化する。より具体的には、各グループがストロークパス６０１の相対的に線形の部分に対応するように、画像のシーケンスをグループに分割する。後でより詳細に述べるように、このセグメント化により、セグメント中の位置決定済み画像の位置から、そのセグメント中の位置未決定の画像の位置を正確に補間することができる。ストロークのセグメントを決定するために、セグメント化モジュール９０３は、ストロークのピボット開始点を識別する。ピボット開始点は、ストロークが方向を変える位置に、またはその近くに生じる点である。さらに、ストローク中の最初と最後の開始点はピボット開始点と考える。
【００５２】
図１１および１２に、ストロークパス６０１の画像７０１Ａ〜７０１Ｘのシーケンスをセグメント化するプロセスの１つを図式的に示す。前述のように、最初の開始点８０１Ａと最後の開始点８０１Ｘは両方とも、ピボット開始点と考える。したがって、ピボット開始点８０１Ａと８０１Ｘは、それらの間でストロークパス６０１の単一セグメントを定義する。ストロークパス６０１の追加のピボット開始点を定義するために、セグメント化モジュール９０５は、図１１に示すように最初のピボット開始点８０１Ａと最後の開始点８０１Ｘとの間に線１１０１を生成する。次いで、線１１０１から最も遠い開始点８０１Ｏ（後述するように０．５ピクセルなどのしきい値よりも遠い距離にある）をピボット開始点として識別する。それにより、セグメント化モジュール９０３は、線１１０１から距離ｄ１に位置する開始点８０１Ｏをピボット開始点として指定する。開始点８０１Ｏを定義すると、画像７０１Ａ〜７０１Ｘのシーケンスは２つのセグメントに分割される。第１のセグメントＳＥＧ１は、ストロークパス６０１のピボット開始点８０１Ａとピボット開始点８０１Ｏとの間の部分に対応し、第２のセグメントＳＥＧ２は、ストロークパス６０１のピボット開始点８０１Ｏとピボット開始点８０１Ｘとの間の部分に対応する。
【００５３】
セグメント化モジュール９０３は、各セグメントが相対的に直線のストローク部分に対応するようになるまで、各セグメントをより小さいセグメントに分割し続ける。例えば、ストロークパス６０１で、セグメント化モジュール９０３は、第１のセグメントＳＥＧ１をより小さいセグメントに分割する。より具体的には、セグメント化モジュールは、セグメントＳＥＧ１の端点間（すなわちピボット開始点８０１Ａとピボット開始点８０１Ｏとの間）にライン１２０１を生成する。次いでセグメント化モジュール９０３は、線１２０１から最も遠い開始点を識別する。それにより、セグメント化モジュール９０３は、線１２０１から距離ｄ２に位置する開始点８０１Ｆをピボット開始点として指定する。開始点８０１Ｆを定義すると、画像７０１Ａ〜７０１Ｏのセグメントは２つのセグメントに分割される。第１のセグメントＳＥＧ１Ａは、ストロークパス６０１のピボット開始点８０１Ａとピボット開始点８０１Ｆとの間の部分に対応し、第２のセグメントＳＥＧ１Ｂは、ストロークパス６０１のピボット開始点８０１Ｆとピボット開始点８０１Ｏとの間の部分に対応する。
【００５４】
セグメント化モジュール９０３は、画像の各セグメントがほぼ線形のストローク部分に対応するようになるまで、画像の各セグメントを分割し続ける。例えば、セグメント化モジュール９０３が、セグメントを形成する２つの開始点の間で線を生成し、この線からしきい値距離よりも遠い開始点がない場合は、セグメント化モジュールはそれ以上セグメントを分割しない。本発明のいくつかの実施形態では、しきい値は、文書中の個々の位置を（例えばデカルト座標系を使用して）定義するために採用される例えば０．５ユニット（例えばピクセル）の距離とすることができる。当然、より高いしきい値を使用することもでき、それにより、画像のセグメントがより線形でないストローク部分に対応できるようにしてもよい。より低いしきい値を使用することもでき、それにより、画像のセグメントがより線形なストローク部分に対応する必要があるようにしてもよい。
【００５５】
セグメント化モジュール９０３は、ストローク中のすべてのピボット開始点を識別すると、ピボット開始点の位置および透視変換（ｐｅｒｓｐｅｃｔｉｖｅ  ｔｒａｎｓｆｏｒｍ）を精緻にする。より具体的には、セグメント化モジュール９０３は、ピボット開始点８０１の位置および透視変換をより正確に決定するために、ピボット開始点８０１に対応する各画像７０１を文書の電子バージョンと比較する。この比較プロセスは、知られている所望の技法を用いて利用することができる（例えば、非特許文献１参照。）ピボット開始点を精緻にすると、画像のシーケンスをセグメントに分割するプロセスが完了する。
【００５６】
ピボット開始点８０１（および関連する画像７０１）の位置をより正確に決定することに加えて、ピボット開始点８０１を精緻にすることにより、セグメント化モジュール９０３は、画像をそれに対応する文書部分とマッチさせるのに使用される変換パラメータの精度を高めることができる。前に詳細に論じたように、ペン２０１を傾斜および回転させるせいで、カメラによって撮られる画像は、文書の実際の体裁に対して相対的に回転およびスケールされている。画像を文書の一部と正確に比較するために、画像を歪ませて、ペン２０１の傾斜および回転によって生じた回転およびスケールの変化を補償しなければならない。例えば図１３に、元の画像１３０１を示す。次いで図１４に、歪み変換パラメータに従って歪ませた後の同じ画像１４０１を示す。
【００５７】
ピボット開始点を文書の電子バージョンとより正確に比較することによって、セグメント化モジュール９０３は、画像をより正確に歪ませて文書とマッチさせるために、変換パラメータを修正することができる。本発明の様々な実施形態では、セグメント化モジュール９０３は、シーケンス中の取り込まれた画像すべてに適用される単一の変換パラメータセットを修正することができる。しかし、本発明の他の実施形態では、セグメント化モジュール９０３は、各ピボット開始点ごとの特定の変換パラメータセットを生み出す。後でより詳細に論じるが、各ピボット開始点ごとに特定の変換パラメータセットがある場合、隣接する位置未決定の点をより正確に補間することができる。ペン２０１の傾斜および回転は、ストローク全体の距離にわたって大きく変動することはあるが、通常、ストロークの単一セグメントの短い距離ではそれほど変動しない。そのため、各ピボット開始点ごとの変換パラメータを使用して、そのピボット開始点に対応する画像の直前または直後に取り込まれた画像をより正確に歪ませることができる。
【００５８】
セグメント化モジュール９０３が画像７０１Ａ〜７０１Ｘをセグメント化した後、セグメント完了モジュール９０５は、各画像セグメントを処理して、各セグメント中の位置未決定の画像の位置を決定する。したがってステップ１００５で、セグメント完了モジュール９０５は、第１のセグメント中の画像を受け取る。次にステップ１００５で、セグメント完了モジュール９０５は、このセグメントが完了しているかどうかを判定する。セグメント完了モジュール９０５は、ピボット開始点でない少なくとも１つの開始点をセグメントが含む場合に、セグメントが完了していると判定する。すなわち、セグメント中のピボット開始点以外の少なくとも１つの点の位置が、画像中に取り込まれたパターンからまたは別の技法によってすでに決定されている場合は、セグメントは完了している。この状況で、セグメントは、セグメント中のすべての画像を線形補間によって決定できるほど十分に線形である。加えて、セグメント完了モジュール９０５は、セグメント中のあらゆる位置未決定画像が文書の対応部分とマッチされた後にも、セグメントが完了していると判定する。
【００５９】
セグメントが完了していない場合は、ステップ１００７で、セグメント完了モジュール９０５は、セグメント中の第１の未処理（すなわち位置未決定）の画像を受け取る。（各セグメント中の第１の画像は、既知の位置のピボット開始点である。）ステップ１００８で、セグメント完了モジュールは、後でより詳細に論じるように、文書と比較するために画像を歪ませる。次いでステップ１００９で、セグメント完了モジュール９０５は、未処理画像に対する探索領域を決定する。セグメント中の第１の未処理画像に対する探索領域は、ペン２０１の最大推定速度に基づいて決定する。当業者には理解されるであろうが、ペン２０１を使用して筆記しているユーザは、文書を表示している物理媒体に応じた最大速度でしかペン２０１を動かすことはできない。特定のタイプのペン２０１および物理媒体の場合の最大速度は、例えば実験によって決定することができる。
【００６０】
したがって、第１の未処理画像に対する探索領域の中心は、セグメント中の第１のピボット開始点とすることができ、探索領域の半径は、ペン２０１の最大速度に、セグメント中の第１のピボット開始点に対応する画像の取込みと、セグメント中の第１の未処理画像の取込みとの間の時間間隔を掛けた値に制限される。本発明の様々な実施形態では、未処理画像を、前述のようにセグメント中の第１のピボット開始点の変換パラメータを使用して比較のために歪ませる。しかし、本発明の他の実施形態では、未処理画像は、前の画像がピボット開始点であるかどうかにかかわらず、セグメント中のすでに位置決定された画像の変換パラメータを使用して比較のために歪ませることができる。未処理画像を歪ませた後、次いでセグメント完了モジュール９０５は、歪ませた第１の未処理画像を文書の探索領域とピクセル単位で比較して、第１の未処理画像中に取り込まれた文書部分を決定する。ピクセル単位の比較は、例えば、第１の未処理画像と探索領域中の各文書部分との間の相関値を決定する。
【００６１】
セグメント完了モジュール９０５は、未処理画像が、最高の相関値を生み出す文書部分に対応すると決定する。未処理画像をこのようにして正確に位置決定することにより、セグメント完了モジュール９０５はまた、未処理画像に対応する点の位置も決定する。第１の未処理画像について位置決定された点と、第１のピボット開始点との間の距離は、ペン２０１が実際に動かされた速度を示す。決定された未処理画像の位置に基づき、セグメント完了モジュール９０５はまた、取り込まれた画像を精緻にすることによって（すなわち取り込まれた画像を文書画像とマッチさせて透視変換を得ることによって）変換パラメータを更新して、前述のように次の未処理画像を歪ませる際に使用することができる。ペン２０１の実際の動く速度が決定され、変換パラメータが更新されると、未処理画像は処理されたと見なされる。
【００６２】
ステップ１０１５で、セグメント完了モジュール９０５は、セグメント中に未処理画像が他にもあるかどうかを判定する。他にもある場合は、セグメント完了モジュール９０５は、現在未処理画像を受け取ってステップ１００７を繰り返す。次いでステップ１００９で、セグメント完了モジュール９０５は、現在未処理画像に対する探索領域を決定する。セグメント中の第２の未処理画像および後続の各未処理画像で、前の未処理画像を位置決定することから決定されたペン２０１の実際速度に基づいて、探索領域を決定する。例えば、探索領域の中心は、前の未処理画像に対応する中心点とすることができる。次いでセグメント完了モジュール９０５は、前の未処理画像に対する点の位置から計算した実際のペン速度に基づいて、探索領域の半径を決定することができる。より具体的には、探索領域の半径は、前の未処理画像の位置から計算された実際のペン速度に、取り込まれた画像間の時間間隔を掛けることによって決定することができる。
【００６３】
当業者には理解されるであろうが、ペン２０１を使用して筆記しているユーザは、ペン２０１の速度を最大加速値で変更することしかできない。この最大加速値は、例えば実験によって計算することもでき、あるいは前に位置決定された画像間の実際の加速度に基づくこともできる。したがって、本発明のいくつかの実施形態では、第２および後続の未処理画像に対する探索領域の半径は、最大加速値によって修正することができる。例えば、時間ｔ１、ｔ２、ｔ３で取り込まれ、点ｐ１、ｐ２、ｐ３を中心とする３つの画像ｆ１、ｆ２、ｆ３が、ストローク中にあるとする。点ｐ１およびｐ２の位置を決定することができれば、これらの画像の取込みと取込みの間のペン速度Ｖは、Ｖ＝（ｐ２−ｐ１）／（ｔ２−ｔ１）である。加速値が−ＡとＡの間の値であるとすると、点ｐ３に対する探索領域は、位置Ｐ＝ｐ２＋Ｖ＊（ｔ３−ｔ２）の辺りを中心とし、探索領域の範囲は［Ｐ−Ａ＊（ｔ３−ｔ２）＊（ｔ３−ｔ２）／２，Ｐ＋Ａ＊（ｔ３−ｔ２）＊（ｔ３−ｔ２）／２］である。
【００６４】
セグメント完了モジュール９０５は、現在未処理画像に対する探索領域を決定すると、ステップ１０１１で、未処理画像を前の処理済み画像からの透視変換で歪ませ、歪ませた未処理画像を文書の探索領域とピクセル単位で比較する。この場合もやはり、最高の相関値を生み出す文書部分を現在未処理画像の位置として選択する。次いでセグメント完了モジュール９０５は、現在未処理画像の点と、前の未処理画像の点との間の距離に基づいて、ペン２０１の新しい速度を計算する。また、識別された現在未処理画像の位置に基づいて変換パラメータも更新し、それにより画像を処理する。次いでセグメント完了モジュール９０５は、ステップ１０１５を繰り返して、現在セグメント中に位置未決定の画像が残っているかどうかを判定する。
【００６５】
セグメント完了モジュール９０５は、位置未決定の画像が現在セグメント中になくなるまで、ステップ１００７および１０１５を繰り返す。次にステップ１０１７で、セグメント完了モジュール９０５は、画像シーケンス中にセグメントが他にもあるかどうかを判定する。セグメントが他にもある場合は、セグメント完了モジュール９０５は、画像シーケンス中のすべてのセグメントが完了するまで、ステップ１００３から１０１５を繰り返す。
【００６６】
すべてのセグメントが完了した後、ストローク中の各画像を文書中で位置決定する。いくつかの要因、例えば誤った初期変換パラメータやモーションブラーなどは、１つまたは複数の位置決定済み画像についての誤った位置結果につながる恐れがある。そのため、本発明の様々な実施形態では、ステップ１０１９で、結果切捨てモジュール６０９を利用して、誤った位置を結果から切り捨てる。
【００６７】
結果切捨てモジュール６０９は、例えば、画像シーケンスの各開始点の位置を維持することができる。次に、結果切捨てモジュール６０９は、ストロークパス全体にわたる各点を進み、最初の点から最後の点への順に各点を分析することができる。より具体的には、前の点から現在点まで、および現在点から次の点までの速度を計算する。この２つの速度値から、加速度も計算する。速度値と加速度のどちらかが最大値を超える場合は、現在点の位置を誤りと見なし、結果から切り捨てる。
【００６８】
本発明の様々な実施形態では、結果切捨てモジュール６０９は各点の分析を繰り返すことができるが、そうではなく最後の点から最初の点へ逆の順に各点を分析することもできる。したがって、次の点から現在点まで、および現在点から前の点への速度を計算する。この２つの速度値から、加速度も計算する。速度値と加速度のどちらかが最大値を超える場合は、現在点の位置を誤りと見なし、結果から切り捨てる。すべての誤った点を切り捨てた後、補間を用いて、切り捨てた点の位置を決定することができる。
【００６９】
結び
現時点で好ましい本発明の実施モードを含めて特定の例に関して本発明を述べたが、前述のシステムおよび技法には、添付の特許請求の範囲に示す本発明の趣旨および範囲に含まれる多くの変形および置換があることは、当業者なら理解するであろう。
【図面の簡単な説明】
【００７０】
【図１】本発明の実施形態に関して使用することのできるコンピュータの一般的な記述を示す図である。
【図２Ａ】本発明の様々な実施形態によるペンの例を示す図である。
【図２Ｂ】本発明の様々な実施形態によって得られる画像の解像度を示す図である。
【図３Ａ】本発明の実施形態による符号化システムの例を示す図である。
【図３Ｂ】本発明の実施形態による符号化システムの例を示す図である。
【図３Ｃ】本発明の実施形態による符号化システムの例を示す図である。
【図３Ｄ】本発明の実施形態による符号化システムの例を示す図である。
【図３Ｅ】本発明の実施形態による符号化システムの例を示す図である。
【図３Ｆ】本発明の実施形態による符号化システムの例を示す図である。
【図３Ｇ】本発明の実施形態による符号化システムの例を示す図である。
【図３Ｈ】本発明の実施形態による符号化システムの例を示す図である。
【図３Ｉ】本発明の実施形態による符号化システムの例を示す図である。
【図４】どのように符号化パターンを利用して、文書の一部から取り込まれた画像の回転を決定することができるかを図式的に示す図である。
【図５】文書の一部から取り込まれた画像の回転を決定するのに使用することのできる式を示す図である。
【図６】文書中に生み出されたストロークを示す図である。
【図７】図６に示す文書中にストロークが生み出されたときの、取り込まれた画像を示す図である。
【図８】図７に示す取り込まれた画像それぞれの基準点を示す図である。
【図９】本発明の様々な実施形態による、取り込まれた画像を文書の一部とマッチさせるのに使用することのできるツールを示す図である。
【図１０Ａ】本発明の様々な実施形態による、取り込まれた画像を文書の一部とマッチさせる方法を記述するフローチャートを示す図である。
【図１０Ｂ】本発明の様々な実施形態による、取り込まれた画像を文書の一部とマッチさせる方法を記述するフローチャートを示す図である。
【図１０Ｃ】本発明の様々な実施形態による、取り込まれた画像を文書の一部とマッチさせる方法を記述するフローチャートを示す図である。
【図１１】図６に示すストロークのピボット基準点の決定を示す図である。
【図１２】図６に示すストロークのピボット基準点の決定を示す図である。
【図１３】取り込まれた画像をどのようにして歪ませることができるかについての例を示す図である。
【図１４】取り込まれた画像をどのようにして歪ませることができるかについての例を示す図である。
【符号の説明】
【００７１】
１０１  キーボード
１０２  マウス
１０６  シリアルポートインタフェース
１０７  モニタ
１０８  ビデオアダプタ
１０９  リモートコンピュータ
１１０  処理ユニット
１１１  メモリ
１１２  ローカルエリアネットワーク
１１３  ワイドエリアネットワーク
１１４  ネットワークインタフェース
１１５  モデム
１２０  システムメモリ
１３０  システムバス
１６５  ディジタイザ
１９２  ハードディスクインタフェース
１９３  磁気ディスクドライブインタフェース
１９４  光学ドライブインタフェース
１９５  オペレーティングシステム
１９６  アプリケーションプログラム
１９７  その他のプログラムモジュール
１９８  プログラムデータ
９０３  画像受領モジュール
９０５  セグメント化モジュール
９０７  セグメント完了モジュール
９０９  結果切捨てモジュール
【図１】
0004652823.tif 000004
【図２Ａ】
0004652823.tif 000005
【図２Ｂ】
0004652823.tif 000006
【図３Ａ】
0004652823.tif 000007
【図３Ｂ】
0004652823.tif 000008
【図３Ｃ】
0004652823.tif 000009
【図３Ｄ】
0004652823.tif 000010
【図３Ｅ】
0004652823.tif 000011
【図３Ｆ】
0004652823.tif 000012
【図３Ｇ】
0004652823.tif 000013
【図３Ｈ】
0004652823.tif 000014
【図３Ｉ】
0004652823.tif 000015
【図４】
0004652823.tif 000016
【図５】
0004652823.tif 000017
【図６】
0004652823.tif 000018
【図７】
0004652823.tif 000019
【図８】
0004652823.tif 000020
【図９】
0004652823.tif 000021
【図１０Ａ】
0004652823.tif 000022
【図１０Ｂ】
0004652823.tif 000023
【図１０Ｃ】
0004652823.tif 000024
【図１１】
0004652823.tif 000025
【図１２】
0004652823.tif 000026
【図１３】
0004652823.tif 000027
【図１４】
0004652823.tif 000028