(57)【要約】      （修正有）【課題】カメラによって取り込まれた各画像につき候補のリストを受け取り、カメラによって取り込まれた前の画像からの最小限の動きに基づいて、ペンの最も可能性の高い経路を決定する。【解決手段】  ペン２０１は、インク筒を含む場合とそうでない場合のあるチップ２０２を含む。カメラは、表面２０７から画像２０４を取り込む。ペン２０１はさらに、破線ボックス２０６中に表すように追加のセンサおよび／またはプロセッサも備えることができる。これらのセンサおよび／またはプロセッサ２０６はまた、別のペン２０１および／またはパーソナルコンピュータに情報を送信する機能（例えばブルートゥースや他の無線プロトコルを介して）を備えることができる。【選択図】  図２Ａ
2004152272.tif 000002
【特許請求の範囲】
【請求項１】
ペンの位置の候補を決定するのに使用される情報を取り込むカメラを有するペンの経路を決定する方法であって、
前記カメラによって取り込まれた各画像につき候補のリストを受け取るステップと、
前記カメラによって取り込まれた前の画像からの最小限の動きに基づいて、前記ペンの最も可能性の高い経路を決定するステップと
を含むことを特徴とする方法。
【請求項２】
前記最も可能性の高い経路を決定する際に、画像についての少なくとも１つのリスト候補をスキップすることを特徴とする請求項１に記載の方法。
【請求項３】
前記決定するステップはバイグラムモデルを使用することを特徴とする請求項１に記載の方法。
【請求項４】
前記決定するステップはトライグラムモデルを使用することを特徴とする請求項１に記載の方法。
【請求項５】
前記候補のリストは能動符号に関連することを特徴とする請求項１に記載の方法。
【請求項６】
前記候補のリストは受動符号に関連することを特徴とする請求項１に記載の方法。
【請求項７】
コンピュータによって実施可能な命令が記憶されたコンピュータ可読媒体であって、前記命令は、ペンの位置の候補を決定するのに使用される情報を取り込むカメラを有するペンの経路を決定するための命令であり、前記命令は、
前記カメラによって取り込まれた各画像につき候補のリストを受け取るステップと、
前記カメラによって取り込まれた前の画像からの最小限の動きに基づいて、前記ペンの最も可能性の高い経路を決定するステップと
を含むことを特徴とするコンピュータ可読媒体。
【請求項８】
前記方法は、前記最も可能性の高い経路を決定する際に、画像についての少なくとも１つのリスト候補をスキップすることを特徴とする請求項７に記載のコンピュータ可読媒体。
【請求項９】
前記決定するステップはバイグラムモデルを使用することを特徴とする請求項７に記載のコンピュータ可読媒体。
【請求項１０】
前記決定するステップはトライグラムモデルを使用することを特徴とする請求項７に記載のコンピュータ可読媒体。
【請求項１１】
前記候補のリストは能動符号に関連することを特徴とする請求項７に記載のコンピュータ可読媒体。
【請求項１２】
前記候補のリストは受動符号に関連することを特徴とする請求項７に記載のコンピュータ可読媒体。
【請求項１３】
ペンの経路を決定するためのシステムであって、
前記ペンに付属するカメラからの画像に関係する情報を受け取るための入力と、
前記情報を処理し、各画像からのいくつかの潜在的な候補に基づいて前記ペンの経路を決定するプロセッサと
を備えたことを特徴とするシステム。
【請求項１４】
前記プロセッサは、前記カメラからの少なくとも１つ前の画像から得られる少なくとも候補の位置を、少なくとも部分的に前記ペンの位置の根拠とすることを特徴とする請求項１３に記載のシステム。
【請求項１５】
ペンの経路を決定するためのシステムであって、
符号化済み画像を含む符号化済み媒体と、
前記符号化済み画像を取り込むカメラと、
前記符号化済み画像の少なくとも１つのあり得る位置を決定し、前記カメラに関連するペンの最も可能性の高い経路を提供するためのプロセッサと
を備えたことを特徴とするシステム。
【請求項１６】
前記符号化済み媒体は白紙であることを特徴とする請求項１５に記載のシステム。
【請求項１７】
前記符号化済み媒体は、グラフィカルな内容を有する紙であることを特徴とする請求項１５に記載のシステム。
【請求項１８】
前記符号化済み媒体は、符号化済み画像と組み合わせて画像を表示するコンピュータ表示装置であることを特徴とする請求項１５に記載のシステム。
【請求項１９】
前記符号化済み媒体は、画像を表示するコンピュータ表示装置であり、前記コンピュータ表示装置は、前記コンピュータ表示に関連する符号化済み画像を含むことを特徴とする請求項１５に記載のシステム。
【請求項２０】
前記符号化済み画像は前記コンピュータ表示装置の一部であることを特徴とする請求項１９に記載のシステム。
【請求項２１】
前記符号化済み画像は前記コンピュータ表示装置の上に配置された透過オーバーレイであることを特徴とする請求項１９に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタルペンを使用して媒体と対話することに関する。より詳細には、本発明は、１つまたは複数の表面との対話中にデジタルペンの位置を決定することに関する。
【背景技術】
【０００２】
コンピュータユーザは、パーソナルコンピュータと対話する方法としてマウスおよびキーボードを使用することを習慣としている。パーソナルコンピュータは、書かれた文書に勝るいくつかの利点をもたらすが、ほとんどのユーザは、引き続き印刷された紙を使用して、いくつかの仕事をしている。これらの仕事のいくつかには、書かれた文書を読むことや書かれた文書に注釈を付けることが含まれる。注釈の場合、印刷文書は、ユーザによって注釈が付けられたことでより一層重要な意味を帯びる。
【０００３】
【非特許文献１】Douglas W. Clark, Lih-Jyh Weng, "Maximal and Near-Maximal Shift Register Sequences: Efficient Event Counters and Easy Discrete Logarithms", IEEE Transactions on Computers 43.5 (May 1994, pp.560-568)
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、注釈付きの印刷文書を有することに伴う難点の１つは、後で電子形式のこの文書の中に注釈を再入力する必要があることである。これには、元のユーザまたは別のユーザが注釈に目を通し、それらをパーソナルコンピュータに入力することが必要とされる。場合によっては、ユーザは注釈および元のテキストをスキャンして読み込み、それによって新しい文書を作成することになる。これらの複数のステップのために、印刷文書とこの文書の電子バージョンとの間の対話を繰り返すのが困難になる。さらに、読み込んだ画像は修正できないことが多い。元のテキストから注釈を分離する方法がない場合もある。これにより、注釈を使用するのが困難になる。したがって、注釈を処理するための改良された方法が必要とされている。
【０００５】
ユーザは、白紙と、すでに内容がある紙との両方に書くことに慣れている。これらの各表面からの注釈を電子的に表すには、これらの異なる環境についてペンの位置を決定する必要がある。
【課題を解決するための手段】
【０００６】
本発明の態様は、前述の問題の少なくとも１つに対する解決法を提供し、それにより、表面上で１つまたは複数の位置を突き止めることを可能にする。表面は、印刷された画像（または表示されたコンピュータ画像上の画像）を含むことができる。本発明の態様には、取り込まれた画像を効率的に局所化できるようにして、画像位置の効率的な決定を可能にする種々の局所化プロセスが含まれる。本発明のこれらおよび他の態様は、後続の図面および関連する記述を通してわかるであろう。
【０００７】
以上の本発明の概要、ならびに以下の好ましい実施形態の詳細な説明は、添付の図面と併せて読めばよりよく理解される。図面は、特許請求する本発明に関する限定としてではなく、例として含める。
【発明を実施するための最良の形態】
【０００８】
本発明の態様は、取り込まれた画像の位置を、より大きな画像との関係で決定することに関する。本発明の態様は、探索する必要のある画像セットの数を最小限に抑えることに関する。この探索サイズの縮小により、ペンの経路を決定できる速度が向上する。本明細書で述べる位置決定方法およびシステムは、多機能ペンと共に使用することができる。
【０００９】
以下は、読者のために小見出しで分けてある。小見出しには、用語、汎用コンピュータ、画像取込みペン、能動符号、受動符号、経路決定、符合のグループ化および経路決定が含まれる。
【００１０】
用語
ペン  −  インクを蓄積する能力を含むことも含まないこともある任意の筆記具。いくつかの例では、インク機能なしのスタイラスを本発明の実施形態によるペンとして使用することができる。
【００１１】
カメラ  −  紙、コンピュータ表示装置、または他の任意の媒体から画像を取り込むことのできる画像取込みシステム。
【００１２】
汎用コンピュータ
図１は、本発明の様々な態様を実現するのに使用できる従来型の汎用デジタルコンピューティング環境の例に関する機能ブロック図である。図１で、コンピュータ１００は、処理ユニット１１０と、システムメモリ１２０と、システムメモリを含めた様々なシステム構成要素を処理ユニット１１０に結合するシステムバス１３０とを備える。システムバス１３０は、様々なバスアーキテクチャのいずれかを用いたメモリバスまたはメモリコントローラ、周辺バス、およびローカルバスを含めた、いくつかのタイプのバス構造のいずれかとすることができる。システムメモリ１２０は、読取り専用メモリ（ＲＯＭ）１４０およびランダムアクセスメモリ（ＲＡＭ）１５０を含む。
【００１３】
ＲＯＭ１４０には、起動中などにコンピュータ１００内の要素間の情報転送を助ける基本ルーチンを含むＢＩＯＳ（ｂａｓｉｃ  ｉｎｐｕｔ／ｏｕｔｐｕｔ  ｓｙｓｔｅｍ）１６０が記憶されている。コンピュータ１００はまた、ハードディスク（図示せず）に対して読み書きするためのハードディスクドライブ１７０と、取外し可能磁気ディスク１９０に対して読み書きするための磁気ディスクドライブ１８０と、ＣＤ  ＲＯＭやその他の光媒体などの取外し可能光ディスク１９２に対して読み書きするための光ディスクドライブ１９１も含む。ハードディスクドライブ１７０、磁気ディスクドライブ１８０、および光ディスクドライブ１９１は、それぞれハードディスクドライブインタフェース１９２、磁気ディスクドライブインタフェース１９３、および光ドライブインタフェース１９４によってシステムバス１３０に接続される。ドライブおよびそれらに関連するコンピュータ可読媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、およびその他のデータなどの情報の不揮発性記憶域をパーソナルコンピュータ１００に提供する。この例示的な動作環境では、磁気カセット、フラッシュメモリカード、デジタルビデオディスク、ベルヌーイカートリッジ、ランダムアクセスメモリ（ＲＡＭ）、読取り専用メモリ（ＲＯＭ）など、コンピュータからアクセス可能なデータを記憶することのできる他のタイプのコンピュータ可読媒体も使用できることは、当業者には理解されるであろう。
【００１４】
ハードディスクドライブ１７０、磁気ディスク１９０、光ディスク１９２、ＲＯＭ１４０、またはＲＡＭ１５０には、オペレーティングシステム１９５、１つまたは複数のアプリケーションプログラム１９６、その他のプログラムモジュール１９７、およびプログラムデータ１９８を含めて、いくつかのプログラムモジュールを記憶することができる。ユーザは、キーボード１０１やポインティングデバイス１０２などの入力デバイスを介して、コンピュータ１００にコマンドおよび情報を入力することができる。その他の入力デバイス（図示せず）には、マイクロホン、ジョイスティック、ゲームパッド、衛生受信アンテナ、スキャナなどを含めることができる。これらおよび他の入力デバイスは、システムバスに結合されたシリアルポートインタフェース１０６を介して処理ユニット１１０に接続されることが多いが、パラレルポート、ゲームポート、ユニバーサルシリアルバス（「ＵＳＢ」）など、他のインタフェースによって接続されてもよい。さらに、これらのデバイスは、適切なインタフェース（図示せず）を介してシステムバス１３０に直接に接続されてもよい。モニタ１０７または他のタイプの表示デバイスもまた、ビデオアダプタ１０８などのインタフェースを介してシステムバス１３０に接続される。モニタに加えて、パーソナルコンピュータは通常、スピーカやプリンタなど他の周辺出力デバイス（図示せず）も備える。好ましい一実施形態では、フリーハンド入力をデジタルで取り込むために、ペンディジタイザ１６５および付属のペンまたはスタイラス１６６が備わる。ペンディジタイザ１６５とシリアルポートの間に直接接続が示してあるが、実際には、ペンディジタイザ１６５は、当技術分野で周知のようにパラレルポートまたは他のインタフェースおよびシステムバス１３０を介して処理ユニット１１０に直接に結合してもよい。さらに、図ではディジタイザ１６５がモニタ１０７から離れているが、ディジタイザ１６５の使用可能入力領域がモニタ１０７の表示領域と共存することが好ましい。さらに、ディジタイザ１６５は、モニタ１０７に一体化させてもよく、モニタ１０７に重なるか他の方法でモニタ１０７に付属する別個のデバイスとして存在してもよい。
【００１５】
コンピュータ１００は、リモートコンピュータ１０９など１つまたは複数のリモートコンピュータへの論理接続を用いて、ネットワーク化された環境で動作することができる。リモートコンピュータ１０９は、サーバ、ルータ、ネットワークＰＣ、ピアデバイス、またはその他の一般的なネットワークノードとすることができ、図１にはメモリ記憶デバイス１１１しか示していないが、通常はコンピュータ１００に関して上述した要素の多くまたはすべてを含む。図１に示す論理接続は、ローカルエリアネットワーク（ＬＡＮ）１１２および広域ネットワーク（ＷＡＮ）１１３を含む。このようなネットワーキング環境は、オフィス、企業全体のコンピュータネットワーク、イントラネット、およびインターネットでよく見られる。
【００１６】
コンピュータ１００は、ＬＡＮネットワーキング環境で使用される場合は、ネットワークインタフェースまたはアダプタ１１４を介してローカルネットワーク１１２に接続される。ＷＡＮネットワーキング環境で使用される場合は通常、インターネットなどの広域ネットワーク１１３を介して通信を確立するためのモデム１１５または他の手段を備える。モデム１１５は内蔵でも外付けでもよく、シリアルポートインタフェース１０６を介してシステムバス１３０に接続される。ネットワーク化された環境では、コンピュータ１００に関して示したプログラムモジュールまたはその一部を、リモートのメモリ記憶デバイスに記憶することができる。
【００１７】
図示のネットワーク接続は例示であり、コンピュータ間の通信リンクを確立する他の手段も使用できることは理解されるであろう。ＴＣＰ／ＩＰ、イーサネット（登録商標）、ＦＴＰ、ＨＴＴＰ、ブルートゥース、ＩＥＥＥ８０２．１１ｘなど、様々な周知のプロトコルのいずれかが存在することを想定しており、システムは、ユーザがウェブベースのサーバからウェブページを取り出すことができるようにクライアント−サーバ構成で操作することができる。様々な従来型のウェブブラウザのいずれかを使用して、ウェブページ上のデータを表示および操作することができる。
【００１８】
画像取込みペン
本発明の態様には、符号化済みデータストリームを表示形式中で位置付けることが含まれる。表示形式は、印刷された紙（または他の物理媒体）でもよく、符号化済みデータストリームを別の画像または画像セットと共に投影する表示装置でもよい。例えば、符号化済みデータストリームは、紙の上の物理的な符号化済み画像として、または表示画像に重なる符号化済み画像として表すこともでき、あるいは表示画面上の物理的な符号化済み画像とすることもできる（したがって、ペンで取り込んだどんな画像部分も表示画面上で位置決めすることが可能である）。
【００１９】
取り込んだ画像の位置をこのように決定することを用いて、紙、媒体、または表示画面とのユーザの対話の位置を決定することができる。本発明のいくつかの態様では、ペンは、紙の上に筆記するインクペンとすることができる。他の態様では、ペンは、ユーザがコンピュータ表示装置の表面上に筆記するスタイラスとすることができる。どんな対話も、文書上の符号化済み画像に関する知識、またはコンピュータ画面上に表示された文書をサポートする知識と共に、システムに返すことができる。カメラの位置を繰り返し取り込むことにより、システムは、ユーザによって制御されているスタイラスの動きを追跡することができる。
【００２０】
図２Ａおよび２Ｂに、カメラ２０３を有するペン２０１を説明する例を示す。ペン２０１は、インク筒を含む場合とそうでない場合のあるチップ２０２を含む。カメラ２０３は、表面２０７から画像２０４を取り込む。ペン２０１はさらに、破線ボックス２０６中に表すように追加のセンサおよび／またはプロセッサも備えることができる。これらのセンサおよび／またはプロセッサ２０６はまた、別のペン２０１および／またはパーソナルコンピュータに情報を送信する機能（例えばブルートゥースや他の無線プロトコルを介して）を備えることができる。
【００２１】
図２Ｂは、カメラ２０３によって見た画像を表す。説明的な一例では、カメラ２０３の視野は３２×３２ピクセルである（Ｎ＝３２）。したがって図２Ｂは、縦３２ピクセル×横３２ピクセルの視野を示す。Ｎのサイズは、所望の画像解像度の程度に基づいて調節可能である。また、ここでは説明のためにカメラ２０３の視野を正方形として示しているが、視野には、当技術分野で知られている他の形状を含めることができる。
【００２２】
カメラ２０３からペン２０１への入力は、画像フレームの系列｛Ｉｉ｝、ｉ＝１，２，．．．，Ａと定義することができ、Ｉｉはサンプリング時間ｔｉでペン２０１によって取り込まれる。サンプリングレートの選択はペンチップの最大運動周波数に従い、この最大運動周波数は、筆記中の手の周波数と同じとすることができる。この周波数は、０から２０Ｈｚまでであることが知られている。ナイキスト−シャノンサンプリング定理によれば、最低サンプリングレートは４０Ｈｚであるべきであり、典型的には１００Ｈｚである。一例では、サンプリングレートは１１０Ｈｚである。サンプリングレートは、固定でもよく、文書のサイズに基づいて可変としてもよい。取り込まれる画像フレームのサイズは、文書のサイズおよび必要とされる正確さの程度に応じて大きくても小さくてもよい。また、カメラ画像サイズも、探索される文書のサイズに基づいて決定することができる。
【００２３】
カメラ２０３で取り込んだ画像は、処理システムによって直接に使用することもでき、事前フィルタリングを施すこともできる。この事前フィルタリングは、ペン２０１中で行ってもよく、ペン２０１の外部（例えばパーソナルコンピュータ）で行ってもよい。
【００２４】
図２Ｂの画像サイズは３２×３２ピクセルである。各符号化ユニットサイズが３×３ピクセルの場合は、取り込まれる符号化ユニットの数は約１００ユニットになる。符号化ユニットサイズが５×５の場合は、取り込まれる符号化ユニットの数は約３６になる。
【００２５】
図２Ａには、位置２０４からのパターンの画像２１０が形成される画像面２０９も示してある。対象面２０７上のパターンから受け取られた光が、レンズ２０８によって集束される。レンズ２０８は単一レンズでも複部構成レンズシステムでもよいが、ここでは、わかりやすくするために単一レンズとして表してある。画像取込みセンサ２１１が画像２１０を取り込む。
【００２６】
画像センサ２１１は、画像２１０を取り込めるよう十分に大きい物とすることができる。代替として画像センサ２１１は、位置２１２でペンチップ２０２の画像を取り込めるよう十分に大きい物とすることができる。参照のために、位置２１２における画像を仮想ペンチップと呼ぶ。ペンチップとレンズ２０８と画像センサ２１１との関係は一定なので、画像センサ２１１に対する仮想ペンチップの位置は固定されていることに留意されたい。仮想ペンチップ２１２の位置（Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐで表す）から実際のペンチップ２０２の位置（Ｌｐｅｎｔｉｐで表す）への変換により、取り込まれた画像２１０との関係で実際のペンチップの位置を決定することができる。
【００２７】
以下の変換ＦＳ→Ｐが、カメラで取り込んだ画像を紙の上における実際の画像に変換する。  
Ｌｐａｐｅｒ＝ＦＳ→Ｐ（ＬＳｅｎｓｏｒ）
【００２８】
筆記中、ペンチップと紙は同じ面上にある。したがって、仮想ペンチップから実際のペンチップへの変換もまたＦＳ→Ｐであり、以下のとおりである。  
Ｌｐｅｎｔｉｐ＝ＦＳ→Ｐ（Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐ）
【００２９】
変換ＦＳ→Ｐは、透視変換と呼ぶことができる。これは、ＦＳ→Ｐの推定として以下のように単純化される。
【００３０】
【数１】
2004152272.tif 000003
【００３１】
上式で、θ、ｓｘ、ｓｙは、位置２０４で取り込まれたパターンの２つの配向の回転およびスケールである。さらに、取り込まれた画像を紙の上の対応する背景画像と照合することにより、Ｆ’Ｓ→Ｐをさらに正確にしてＦＳ→Ｐにすることができる。「さらに正確にする」とは、再帰法と呼ばれる一種の最適化アルゴリズムによって、より正確な透視行列ＦＳ→Ｐ（８つのパラメータ）を得ることを意味する。再帰法では、行列Ｆ’Ｓ→Ｐを初期値として扱う。ＦＳ→Ｐは、ＳとＰの間の変換をＦ’Ｓ→Ｐよりも正確に表す。
【００３２】
次に、仮想ペンチップの位置を較正によって決定することができる。  
ペンチップ２０２を、紙の上の既知の位置Ｌｐｅｎｔｉｐに配置する。次に、ペンを傾けて、カメラ２０３が種々のペン姿勢で一連の画像を取り込めるようにする。各画像を取り込むごとに、変換ＦＳ→Ｐを受け取ることができる。この変換から、以下のようにペンチップの仮想画像の位置Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐを得ることができる。  
Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐ＝ＦＰ→Ｓ（Ｌｐｅｎｔｉｐ）
および
ＦＰ→Ｓ＝１／ＦＳ→Ｐ
【００３３】
画像ごとに受け取ったＬｖｉｒｔｕａｌ−ｐｅｎｔｉｐを平均することにより、仮想ペンチップの正確な位置Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐを決定することができる。
【００３４】
仮想ペンチップの位置Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐがすでにわかった。また、取り込まれた画像から変換ＦＳ→Ｐも得ることができる。最後に、この情報を用いて、以下のように実際のペンチップの位置Ｌｐｅｎｔｉｐを決定することができる。  
Ｌｐｅｎｔｉｐ＝ＦＳ→Ｐ（Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐ）
【００３５】
能動符号
文書に情報を挿入して（または画像として追加するかコンピュータの表示上に追加して）、ペン位置の決定に役立てることができる。この情報は２次元配列とすることができ、配列中では、所与のサイズの各サブ配列が固有である。
【００３６】
１次元系列を折り畳むことにより、２次元配列を構築することができる。２次元配列の任意の部分を使用して、全２次元配列中におけるその位置を決定することができる。懸念の１つは、カメラで取り込まれる画像部分のサイズが限られていることである。したがって、取り込まれた１つまたは少数の画像から位置を決定できることが必要である。取り込まれた画像中にあるエラーが、取り込まれた画像中のいくつかの箇所を利用不可能にする場合があることから、厄介な問題がさらに生じる。取り込まれた画像部分が２次元配列中の２つ以上の位置に関連する可能性を最小限に抑えるために、非反復的な系列を使用して配列を生み出すことができる。生み出される系列の特性の１つは、系列が長さ（またはウィンドウ）ｎにわたって反復しないことである。以下に、１次元系列の生成について述べ、次いで系列を配列に折り畳むことについて述べる。
【００３７】
系列の構築
符号化システムの開始点として、数の系列を使用することができる。例えば、系列（ｍ系列とも呼ぶ）は、体Ｆｑ中のｑ個の要素の集合として表すことができる。ここで、ｑ＝ｐｎであり、ｎ≧１で、ｐは素数である。系列またはｍ系列は、異なる様々な技法によって生成することができ、限定しないがこれらの技法には多項式除法が含まれる。多項式除法を用いると、系列は次のように定義することができる。
【００３８】
【数２】
2004152272.tif 000004
【００３９】
上式で、Ｐｎ（ｘ）は、体Ｆｑ［ｘ］（ｑ個の要素を有する）中のｎ次の原始多項式である。Ｒｌ（ｘ）は、体Ｆｑ［ｘ］中のｌ次（ｌ＜ｎ）の０でない多項式である。系列は、２つのステップを用いた反復的な手順によって生み出すことができる。第１に、２つの多項式を割り（体Ｆｑの要素が得られる）、第２に、残りにｘを掛ける。出力が繰り返し始めた時点で計算を停止する。このプロセスは、論文に述べられているように線形帰還シフトレジスタを使用して実施することができる（例えば、非特許文献１参照）。この環境では、系列の周期的シフトと多項式Ｒｌ（ｘ）との間に関係が確立される。すなわち、Ｒｌ（ｘ）を変更しても系列が周期的にシフトされるだけであり、あらゆる周期的シフトは多項式Ｒｌ（ｘ）に対応する。得られる系列の特性の１つは、幅（または長さ）ｎにわたってどんな部分も系列中で１度存在することである。
【００４０】
前述のプロセスは、非反復的な系列を生み出すのに使用することのできる様々なプロセスの１つにすぎない。
【００４１】
配列の構築
画像（その一部をカメラで取り込むことができる）を生み出すのに使用できる配列（またはｍ配列）は、１次元系列またはｍ系列の拡大である。周期（ｍ１，ｍ２）の配列をＡとする。すなわちＡ（ｋ＋ｍ１，ｌ）＝Ａ（ｋ，ｌ＋ｍ２）＝Ａ（ｋ，ｌ）とする。ｎ１×ｎ２ウィンドウがＡの周期を通してシフトする場合、Ｆｑにわたる０でないすべてのｎ１×ｎ２行列は、１度だけ現れる。この特性は、各ウィンドウが固有であるという点で「ウィンドウ特性」と呼ぶことができる。この場合、Ａは周期（ｍ１，ｍ２）および次数（ｎ１，ｎ２）の配列として表現することができる（ｍ１およびｍ２は、配列中にある水平および垂直のビット数）。
【００４２】
系列を折り畳むことによって、２進数配列（またはｍ配列）を構築することができる。ある手法は、系列を得てからこれをサイズｍ１×ｍ２に折り畳み、配列の長さはＬ＝ｍ１×ｍ２＝２ｎ−１である。代替として、カバーしたい所定サイズの空間から開始し（例えば１枚の紙、３０枚の紙、またはコンピュータモニタのサイズ）、領域を決定し（ｍ１×ｍ２）、次いでＬ≧ｍ１ｍ２を可能にするサイズを使用する（Ｌ＝２ｎ−１）。
【００４３】
異なる様々な折畳み技法を用いることができる。例えば図３Ａから３Ｃに、異なる３つの系列を示す。これらはそれぞれ、図３Ｄとして示す配列に折り畳むことができる。この異なる３つの折畳み方法は、図３Ｄではオーバーレイとして示されており、図３Ｅおよび３Ｆではラスタパスとして示されている。図３Ｄに示す折畳み方法は、ｇｃｄ（ｍ１，ｍ２）＝１の場合として表現することができる（Ｌ＝２ｎ−１）。
【００４４】
図３Ｄに示すような折畳み方法を生み出すには、長さＬおよび次数ｎの系列｛ａｉ｝を生み出す。次に、以下の式２で示すように配列の各ビットが計算されるようにすることによって、系列｛ａｉ｝からサイズｍ１×ｍ２の配列｛ｂｋｌ｝を生み出す。  
ｂｋｌ＝ａｉ  この式で、ｋ＝ｉ  ｍｏｄ（ｍ１）であり、ｌ＝ｉ  ｍｏｄ（ｍ２）であり、ｉ＝０，．．．，Ｌ−１である。                                    （２）
【００４５】
この折畳み手法は、代替として、配列の対角線上に系列を置き、次いで端に達したら反対側から継続することとして表現することもできる。
【００４６】
能動符号の場合の候補探索
カメラ２０３で取り込んだ画像中の符号を得て、画像を生み出すのに使用された元のビットストリームと相関させることができる。相関はいくつかの方法で行うことができる。例えば再帰的手法で行うことができ、その場合、回復されたビットストリームを、元のビットストリーム内にある他のすべてのビットストリームフラグメントと比較する。第２に、回復されたビットストリームと元のビットストリームとの間で、例えばこの２つのビットストリーム間のハミング距離を用いて統計分析を行うこともできる。様々な手法を用いて、回復されたビットストリームの位置を元のビットストリーム内で決定できることを理解されたい。
【００４７】
回復されたビットが得られた後は、取り込んだ画像を元の配列（例えば図３Ｄに示した配列）内で位置決めする必要がある。ビットのセグメントの位置を配列全体のうちで決定するプロセスは、いくつかの事項によって複雑になる。第１に、取り込むべき実際のビットが、カメラによる理想の取込みからみて不明瞭な場合がある（例えば、カメラは元の符号を不明瞭にする手書きの画像を取り込む場合がある）。第２に、埃、折り目、反射なども、取り込まれた画像中にエラーを生じることがある。これらのエラーにより、局所化プロセスはより困難になる。これに関し、画像取込みシステムは、画像から抽出された非連続的なビットと共に機能することが必要な場合がある。以下に、画像からの非連続的なビットと共に動作する方法を提示する。
【００４８】
まず系列だけを見るが、系列（またはｍ系列）Ｉが冪級数Ｉ（ｘ）＝１／Ｐｎ（ｘ）に対応するものとする。また、Ｒ（ｘ）＝ｒ０＋ｒ１ｘ＋ｒ２ｘ２＋．．．＋ｒｎ−１ｘｎ−１は、次数がｎ未満である任意の０でない多項式である。系列Ｒは、Ｒ（ｘ）／Ｐｎ（ｘ）に対応する。前述のように、Ｒは、Ｉをシフトしたバージョンである。ＩとＲの間の距離を、距離Ｄと定義する。ＲがＩのｓ番目のシフトである場合、これは、Ｄ（Ｒ）＝ｓと表すことができる。この距離Ｄは、いくつかの様々な技法を用いて計算することができる。ある技法は、２つの間のハミング距離を決定することによる技法である。別の方法は、言及されているように、Ｐｏｈｌｉｇ−Ｈｅｌｌｍａｎ−Ｓｉｌｖｅｒアルゴリズムを使用することによる方法である（例えば、非特許文献１参照）。当技術分野で知られているその他の距離決定技法を用いることもできる。Ｐｏｈｌｉｇ−Ｈｅｌｌｍａｎ−Ｓｉｌｖｅｒアルゴリズムを使用すると、Ｒ（ｘ）≡ｘｓｍｏｄ（Ｐｎ（ｘ））である。
【００４９】
しかし、折り畳まれた系列を使用して距離を計算しようとすることは、より複雑である。というのは、抽出された符号が非連続的でエラーをさらに含む場合があるからである。以上の系列分析から開始して、画像から位置を決定することができる。以下の関係から開始することができる。  
Ｒ＝ｒｔＡ                                                            （３）
上式で、ｒ＝（ｒ０  ｒ１  ｒ２  ．．．ｒｎ−１）ｔであり、Ａ＝（Ｉ  Ｔ（Ｉ）．．．Ｔｎ−１（Ｉ））ｔは、Ｉの周期的シフトからなる。したがって、Ｉのどんな周期的シフトも、ｒｔとＡの積である。ペンがＩのｋ個のビットを読み取る場合（ｂ＝（ｂ０  ｂ１  ｂ２  ．．．ｂｋ−１）ｔ（ｋ≧ｎ））、Ｒ（ｘ）を用いてｂ０を系列（またはｍ系列）の始まりに周期的にシフトすることができる。このシフトは、次いでＡの列を調節して、Ａのｎ×ｋのサブ行列Ｍを生み出す。したがって以下のとおりである。  
ｒｔＭ＝ｂｔ                                                          （４）
【００５０】
Ｍのすべての行が独立している場合、ｒを決定することができ、式（１）の１次元位置を調整することによって、Ｄ（Ｒ）の結果としてＩにおけるｂ０の絶対位置が得られる。このことは、ｂ０ビットの２次元位置を決定できることを意味する。この位置情報により、ペンチップの位置を決定することができる。
【００５１】
次に、Ａのすべての調整を決定してチェックすることができる。  
代替としては、行列Ａが大きいので、Ａのすべての調整を保持する必要はない。実際、実装形態によっては、関係があるのは列の間の相対位置だけである。したがって、保存できる列（ｂ０を系列（またはｍ系列）の始まりにシフトした後で）は、ペン（したがってカメラ）が回転する場合に対応する２次元位置がカメラの受像視野内にある列である。このような列の総数は、Ｌよりもずっと少ない（Ｌ＝２ｎ−１）。ｂにエラーがない場合、ｒの解は以下のように表現することができる。
【００５２】
【数３】
2004152272.tif 000005
【００５３】
上式で、
【００５４】
【数４】
2004152272.tif 000006
【００５５】
はＭの任意の非退化ｎ×ｎサブ行列であり、
【００５６】
【数５】
2004152272.tif 000007
【００５７】
はｂの対応するサブベクトルである。
【００５８】
受動符号
もう１つのタイプの符号化は、本明細書で受動符号化と呼ぶ。受動符号化は、より大きい画像からの画像部分を使用してペンの位置を決定することに関する。異なるいくつかの受動符号化技法が可能であり、これらの技法には、画像のすべて（またはほとんど）の部分を記憶し、カメラで取り込んだ画像をこれらの記憶済み部分と相関させることが含まれる。他の技法には、記憶済み部分のサイズを縮小し、縮小サイズのバージョンを使用してペンの位置を決定することが含まれる。以下の記述は、画像を中心点の周りで符号化することに関し、これを図４に関して示す。この符号化プロセスは、半径符号化と呼ぶこともできる。
【００５９】
受動符号の場合の画像符号化
図４に示すように、画像４０１を受け取り、ステップ４０２でサブ画像に解析する。４０３で、サブ画像の中心の周りでサブ画像を回転ベクトルＴで方向Ｓにサンプリングする。４０３のサブ画像中にみられる情報を、ラップされない画像４０４で表す。言い換えれば、４０３のサブ画像ブロックを極座標でサンプリングする。
【００６０】
４０３におけるサブ画像の中心ピクセル（または領域）を原点として扱い、サンプリング角度をＳとし、サンプリングベクトルの大きさをＴとする。３２×３２ピクセル領域の場合、Ｓ＝３２およびＴ＝１６である。
【００６１】
各サンプリング点（ｔ，ｓ）につき（ｔ＝０，１，．．．，Ｔ−１、ｓ＝０，１，．．．，Ｓ−１）、デカルト座標におけるその位置は（ｘｔ，ｓ，ｙｔ，ｓ）であり、ｘｔ，ｓおよびｙｔ，ｓはそれぞれ式６および７によって表される。
【００６２】
【数６】
2004152272.tif 000008
【００６３】
点（ｔ，ｓ）のグレーレベル値は、式８によって表される。  
Ｇｔ，ｓ＝Ｆ（ｘｔ，ｓ，ｙｔ，ｓ）                                    （８）
上式で、Ｆは、式９によって表される２次元ガウスフィルタである。
【００６４】
【数７】
2004152272.tif 000009
【００６５】
上式で、Ｐ（ｘ，ｙ）は、位置（ｘ，ｙ）におけるピクセルのグレーレベル値を意味する。括弧［］は、実際の値に最も近い整数を意味する。σおよびｑはフィルタパラメータである。
【００６６】
様々な画像を相互に比較するコードブックを記憶しておくことができる。これらの比較を用いて、新しい画像を事前記憶済みの画像に対して配置することができる。
【００６７】
極座標を使用して４０３に示すようなサブ画像ブロックを分析するので、得られる分析は、カメラフレームとサブ画像との間における回転の違いを処理する際のロバスト性がより高い。取り込まれたカメラ画像の回転は４０４の画像のシフトに変わるので、コードブック中の情報と比較されることになるカメラ画像の回転は、複雑な問題ではない。
【００６８】
４０４の画像は、表４０５に示すように、ベクトルＴにわたる各角度Ｓごとにその二進数表現に変換することができる。ｓが０からＳ−１までの範囲で変化するのに伴い、角度は２π・ｓ／Ｓの値をとる。画像またはサブ画像（４０１、４０２、４０３、４０４）は、最初の走査、受取り、または取込みの際に前もって２進数画像に変換されなかった場合、いくつかの位置で２進数（白黒）画像に変換することができる。
【００６９】
グレーレベル値行列｛Ｇｔ，ｓ｝（ｔ＝０，１，．．．，Ｔ−１、ｓ＝０，１，．．．，Ｓ−１）は、しきい値をグレーレベル行列中の値に適用することにより、２進数行列
【００７０】
【数８】
2004152272.tif 000010
【００７１】
に変換することができる（式１０に示すように）。
【００７２】
【数９】
2004152272.tif 000011
【００７３】
次いで、この符号を、より大きい画像におけるサブ画像の位置に関係する情報と共にコードブックにまとめることができる。
【００７４】
カメラ画像の位置をコードブック中の種々の符合によって決定するには、カメラ画像と他の符号表現との間の距離を決定すればよい。候補への最短の距離、または最短の距離のセットが、様々な位置の最良の選択を表すことができる。この距離は、カメラ画像と現在のサブ画像との間のハミング距離によって計算することができる。
【００７５】
前述のように、カメラから取り込まれた画像からの距離を、コードブックからの１つまたは複数の符号セグメントと比較することができる。半径符号の場合、少なくとも２つのタイプの距離を使用することができる。すなわち、一般的なハミング距離および回転不変距離である。その他の距離決定を用いてもよい。
【００７６】
一般的なハミング距離を式１１に表すように使用して、コードブックの符号とカメラ画像に関連する符号との間の距離を決定することができる。  
Ｄｉｓｔｈａｍ（Ｃ１，Ｃ２）＝Ｈａｍ（Ｃ１，Ｃ２）                  （１１）
【００７７】
使用できる別のタイプの距離は、回転不変距離を含む。回転不変距離を使用することの利点は、式１２に示すようにカメラの回転に対処できることである。
【００７８】
【数１０】
2004152272.tif 000012
【００７９】
上式で、
【００８０】
【数１１】
2004152272.tif 000013
【００８１】
は、式１３に示すように定義される。
【００８２】
【数１２】
2004152272.tif 000014
【００８３】
受動符号の場合のコードブック生成
コードブックは、画像からとられたサブ画像に関係する符号であって、画像中におけるサブ画像の位置に関連する符号を記憶する。コードブックは、カメラ２０３で画像を取り込む前に生成することができる。代替として、コードブックは、使用中に生成するか少なくとも増補することができる。例えば、カメラは動作中に画像を収集することができる。ユーザが既存の情報の上に書き込むだけの場合は、コードブックを今述べたように使用して、カメラによって取り込まれた画像の位置を決定することができる。しかし、ユーザが新しい注釈を上書きする場合は、コードブックは、本来正しくなり得たほどには正しくなくなる。したがって、ペン２０１で新しい注釈を追加する場合、これらの注釈をコードブック中に再び組み込むことができ、それにより、以後の注釈は、それらのオンスクリーン表現とより正確に相関されることになる。
【００８４】
コードブック生成は次のように行うことができる。サブ画像（例えば４０３）を所定の符号化方法によって符号化する。次に、位置と符号の対を構成して、コードブックを生成する。コードブックの生成には、少なくとも２つのタイプの構成方法を用いることができる。当然、他の方法を用いてコードブックを生成してもよい。この２つの方法は、例示として提供するにすぎない。
【００８５】
第１の方法は、位置と符号の対を線形リストに配置する方法であり、線形リスト中では、各ノードが符号および位置系列を含み、すべての位置はその符号にマッピングされる。この場合、コードブックは式１４のように表すことができる。  
Ω＝｛Ψｉ，ｉ＝１，２，．．．，ＮΩ｝                              （１４）
【００８６】
上式で、Ψは、Ψ＝｛ＣΨ，ＰΨ｝として定義され、ＰΨは、文書ビットマップ中のすべての位置の集合であり、その符号Ｃを式１５に示す。  
ＰΨ＝｛ｐｉ｜位置ｐｉにおける符号はＣΨ、ｉ＝１，２，．．．｝      （１５）
【００８７】
次に、集合Ωを、各要素Ψの符号でアルファベット順にソートすることができ、次いで線形リストタイプのコードブックが得られる。
【００８８】
第２の方法は、符号を、それらに対応する位置と共に二分木に配置する方法である。２分木は、図８Ａ、８Ｂ、９によって表すように、符号間のハミング距離に基づくことができる。
【００８９】
すべての符号について、符号ＣＯを符号ＣＡと比較する。ＣＡの所与の距離内にあるすべての符号を、ＣＡを中心とする符号集合にグループ化する。図８Ａに示すように、この距離は半径ｒ１である。ここで、符号ＣＸは半径内にあるが、ＣＯはそうではない。しかし、いくつかの小さいエラーを補償するため、あるいはすべての符号がきれいに符号グループＣＡ（または図８Ｂに示すようにグループＣＢ）に収まるようにするために、短い距離ｄをｒ１に足すことができる。
【００９０】
図８Ｂに、ＣＡおよびＣＢをそれぞれ中心とする２つの符号集合を示す。第１の例では、グループＣＡを中心とするいくつかの符号を、ＣＢを中心とするグループによって追加でグループ化することができる。代替として、一方のグループだけが優勢とすることもできる（一方のグループは、どの符号がそのグループに入るかを決定する際に追加の距離ｄを含まないという点で）。
【００９１】
図９を参照するが、まず、全符号集合Ωの重心Ｃｃ０を見つける。次に、重心Ｃｃ０へのハミング距離が最長である符号Ｃ０を見つける。次に、符号Ｃ０への距離が最長である符号Ｃ１を見つける。
【００９２】
次いで、符号集合ＣをΩ０とΩ１の２つの部分集合に分割する。Ω０の内容は式１６によって表すことができ、Ω１の内容は式１７によって表すことができる。
【００９３】
【数１３】
2004152272.tif 000015
【００９４】
次に、部分集合Ω０およびΩ１について、重心を見つけるステップと、重心への距離が最長である符号を見つけるステップと、重心から最も離れている符合への距離が最長である符号を見つけるステップと、次いで部分集合を分割するステップとを、部分集合の要素数が１になるまで繰り返す。
【００９５】
受動符号の場合の候補探索
コードブックを探索することにより、カメラから取り込まれたフレームについて位置候補を決定することができる。カメラによって取り込まれた各フレームＩｉにつき、ペンチップ４０２の候補位置を次のように決定することができる。  
・カメラからのフレームＩｉを、コードブックの生成に使用されたのと同じ符号化方法で符号化する。  
・符号化済みフレームＥＩｉをコードブック中の情報と比較する。符号化済みＥＩｉとコードブック中の符号化済み情報との間の距離を決定する。符号化済みフレームＥＩｉへの距離が最短であるコードブック中の符号化済み情報を、位置候補として、または位置候補のうちの１つとして使用する。これらの候補のうち、最も合致する候補を選択する。
【００９６】
最良の候補の選択には、異なるいくつかの分析を含めることができる。第１に、最も近く合致する候補（符号ＥＩｉへの距離が最短）を選択することができる。代替として、一番最近の候補セットを最近の候補系列と比較し、ある期間にわたってフレームを比較することもできる。結果として得られる比較により、相互に最も近い一連の位置が突き止められるはずである。この比較は時間の経過につれてペンチップが可能な限りほとんど動かなかったことを示すので、この結果が予想される。他の結果は、ペンチップがごく短時間にページの周りでジャンプしたことを示す場合がある（この確率はより低い）。
【００９７】
コードブックを探索するために、以下を用いることができる。符号ＣＩを有する取り込まれた各画像Ｉにつき、最も合致する符号集合Ｓ（ＣＩ）は、式１８のように定義される。  
Ｓ（ＣＩ）＝｛Ψ１｜Ｄｉｓｔ（ＣＩ，ＣΨｉ）＜ｄｔｈｒｅｓｈ，Ψｉ∈Ω，ｉ＝１，．．．，ＮＳ｝                                                      （１８）
【００９８】
半径符号を使用する場合、距離関数はＤｉｓｔｒ−ｉ（・，・）とすべきである。
【００９９】
ＮＳ＞Ｎｔｈｒｅｓｈ・ｄｔｈｒｅｓｈであって、Ｎｔｈｒｅｓｈがカメラ性能に基づいて選択される場合、Ｓ（ＣＩ）中でより短い距離を有するＮｔｈｒｅｓｈ符号だけが保持される。
【０１００】
画像Ｉについての位置候補の集合は、式（１９）によって表すことができる。
【０１０１】
【数１４】
2004152272.tif 000016
【０１０２】
経路決定
取り込んだ画像をより大きい画像と照合するための最も単純な方法は、各画像をより大きい画像中のその他すべてのサブ画像と比較することである。ただしこれには、各画像ごとに極めて多数の探索を実施する必要が生じる。本発明の態様は、実施する必要のある比較の数を最小限に抑えることに対処する。
【０１０３】
また、すべての位置候補を使用して経路の位置を決定することができる。代替として、位置候補のいくつかだけを使用して経路を決定することもできる。図５にこの手法を示す。３つの候補セットが示してある。点５０１Ａ〜５０１Ｃは第１の画像からの候補であり、点５０２Ａ〜５０２Ｃは第２の画像からの候補であり、点５０３Ａ〜５０３Ｃは第３の画像からの候補である。各セットの第１の点が選択された場合（５０１Ａ、５０２Ａ、５０３Ａ）、経路は点線の経路５０１Ａ−５０２Ａ−５０３Ａとして表されることになる。しかし、点５０２Ａは誤っているかもしれない。ペンが短い距離を移動しただけであって、経路が５０１Ａ−５０２Ｂ−５０３Ａであった確率がより高い。ペンがより短い距離を移動した確率の方が高いので、選択される経路は５０１Ａ−５０２Ｂ−５０３Ａになる。
【０１０４】
図６に、点６０１、６０２、６０３、６０４を結ぶ線分を示す。これらの点を結合させて、ペンの経路を表す曲線にすることができる（直線の線分の上に重ねて示してある）。
【０１０５】
本発明の態様は、２部構成のプロセスとして探索候補の数を削減することに関する。第１に、より大きい画像（または文書）を小さいＫ＊Ｋブロックにセグメント化する。第２に、これらのブロック間の関係を表す統計モデルを構築する。したがって、これらのブロックの組合せは、提案する統計モデルによって制約される。この探索可能性の数の削減により、探索システムのスループットが向上する。このことは、より多くの画像がカメラによって取り込まれるので重要である。
【０１０６】
次に、能動符号分析および受動符号分析の結果から生成された候補を組み合わせて、結果を分析してペンの経路を決定することができる。２つのモデルを生み出して適用し、ペンの経路を決定することができる。２つのモデルには、「取込みエラーモデル」および「手書きモデル」が含まれる。これらのモデルは、訓練データ（決定され修正された変数）から訓練することができる。例えば、類似度測定手法を用いてＰｒ（ｉｋ｜ｌｋ）を表し、取込みエラーモデルのための訓練データを提供することができる。例えば、ｉｋとｉｆ（ｌｋ）の間の相関係数を使用することができる。最後に、ベイズ分析技法を用いて結果的なペン経路を決定することができる。
【０１０７】
手書きモデルは、統計言語モデル化の作業に基づく。この場合、統計的なｎグラムモデルを使用して、ユーザをモニタすることによって学習した連続的なブロック間における空間と動きの関係をモデル化する。２つのアルゴリズムを使用することができる。第１に、バイグラムモデルを使用することができ、このモデルは、連続的なブロック間の距離を使用してブロック間の空間関係をモデル化する。次に、トライグラムモデルを使用することができ、このモデルは、ユーザから生成された手書きモデルに基づく。これらのモデルを組み合わせて使用して、取り込まれた画像の位置を見つけることができる。
【０１０８】
画像取込みシステムおよび経路配置の入力および出力は、次のように表すことができる。  
・入力：Ｉ＝（ｉ１，ｉ２，．．．，ｉｎ）。この式で、
【０１０９】
【数１５】
2004152272.tif 000017
【０１１０】
は、カメラによって取り込まれたｋ番目の画像である。
【０１１１】
・出力：Ｌ＝（ｌ１，ｌ２，．．．，ｌｎ）。この式で、ｌｋは、画像ｉｋについての２次元位置である。
【０１１２】
・目標：
【０１１３】
【数１６】
2004152272.tif 000018
【０１１４】
すなわち、Ｐｒ（Ｌ｜Ｉ）を最大にする、最も可能性のある２次元の点の系列
【０１１５】
【数１７】
2004152272.tif 000019
【０１１６】
を見つけることである。
【０１１７】
この関係は、ベイズの法則によって式（２０）として書き直すことができる。
【０１１８】
【数１８】
2004152272.tif 000020
【０１１９】
次に、取込みエラーモデルＰｒ（Ｉ｜Ｌ）と手書きモデルＰｒ（Ｌ）の２つの部分に問題を分ける。概念上は、すべてのＬを列挙し、最大のＰｒ（Ｌ／Ｉ）をもたらすＬを最良の系列として選択する。実際には、ビタビ探索など、いくつかの効率的な方法を用いることができる。一例では、ビタビビーム探索を用いて探索速度を向上させることができる。
【０１２０】
式（２０）に見られる手書きモデルＰｒ（Ｌ）は、２次元位置系列のアプリオリ確率を測定する。一般に、Ｐｒ（Ｌ）は、統計言語モデル（ＳＬＭ）（前述のバイグラムやトライグラム手法など）によって決定することができる。取込みエラーモデルＰｒ（Ｉ｜Ｌ）は、位置Ｌにおける画像ブロックが画像Ｉとして取り込まれる確率を測定する。
【０１２１】
ペンのカメラによって取り込まれる画像は、相対的に小さい。一般に、セグメント化されるブロックＫ＊Ｋのサイズは、カメラの取込みサイズと同様になるように制約することができる。代替として、カメラの画像取込みサイズは、より大きい画像のＫ＊Ｋ分割サイズにほぼ調節することもできる。この分析を用いて、元の文書をＫ＊Ｋサイズの小ブロックに分割することができる。次に、取り込まれた画像系列Ｉを、小さい画像ブロックの組合せ、すなわちｉ１，ｉ２，．．．，ｉｎとして表すことができる。取込みエラーが独立していると仮定すると、エラー取込みモデルは式（２１）として表すことができる。
【０１２２】
【数１９】
2004152272.tif 000021
【０１２３】
上式で、Ｉｆ（ｌｋ）は、位置ｌｋにおける元の画像ブロックである。
【０１２４】
画像ブロックは、実際に効率的に記憶して使用するには大きすぎる場合がある。したがって、いくつかの特徴を抽出して画像ブロックを表すことができる。これは２つの利点をもたらす。第１に、表現を記憶することで、情報量が大きく削減される。第２に、特徴だけを表すことによって雑音がある程度減少するので、ペン位置決めシステムはより強くなる。この特徴抽出は、前述の受動符号化手法を反映することができる。
【０１２５】
ブロックについての特徴セットを得るには、文書全体を白黒画像に変換し、画像をＫ＊Ｋの小ブロックに分割する。小ブロックごとに、画像をＸとＹ軸方向に投影する。ＸとＹ軸方向への投影がすべて０の場合は、この点を０として符号化し、そうでない場合は、この点（中心点）が０として符号化することができる点である。そうでない場合は、この点を１として符号化する。次いで、ＸとＹ軸についての符号を組み合わせてブロックを表す。例えば、白黒画像ブロックを式（２２）のように表し、次いで、このブロックについての符号を式（２３）のように表す。
【０１２６】
【数２０】
2004152272.tif 000022
【０１２７】
上式で、ｉｊｋは画像ブロックｉの点（ｊ，ｋ）における１ピクセルである。ｉｊｋについての可能な２つの値は０または１であり、０は白、１は黒を意味する。
【０１２８】
【数２１】
2004152272.tif 000023
【０１２９】
上式で、ｃｊｘはｘ軸上の符号投影であり、ｃｊｙはｙ軸上の符号投影である。
【０１３０】
符号化の後、取込みエラーモデルは式（２４）のように書き換えられる。
【０１３１】
【数２２】
2004152272.tif 000024
【０１３２】
すべてのブロックについて比較を行うことができる。代替として、計算を加速するために、混乱をきたす可能性のあるすべての符号を事前計算して、以後に使用できるようにテーブルに記憶しておくこともできる。
【０１３３】
式（２０）に見られる手書きモデルＰｒ（Ｌ）は、以下のように、バイグラムやトライグラム言語モデルなどの統計言語モデル（ＳＬＭ）によって決定することができる。
【０１３４】
Ｌは、２次元の点の系列ｌ１，ｌ２，．．．，ｌｎで表すことができる。この場合、手書きモデルは式（２５）によって表すことができる。
【０１３５】
【数２３】
2004152272.tif 000025
【０１３６】
バイグラムモデルでは、ある位置ｌｋが前の位置ｌｋ−１によってのみ制約されると仮定することができる。この仮定に基づくと、手書きモデルは式（２６）のように書き換えることができる。
【０１３７】
【数２４】
2004152272.tif 000026
【０１３８】
さらに、カメラのサンプリングレートがペンの動きに比べて相対的に速いことから、ペンの速度を実質上０と近似することができ、前の位置からのペンの転置はガウス分布を受ける。
【０１３９】
したがって、ページ手書きモデルは、ペンの位置の確率を前の位置に基づいて推定するための堅固なツールを提供する。言い換えれば、移動した距離が短いほど、ペンの位置が新しい位置で決定される確率は高い。この場合、手書きモデルは式（２７）のように書き換えることができる。このモデルは、取り込まれた隣接する画像が小さい円の中に含まれると仮定する。
【０１４０】
【数２５】
2004152272.tif 000027
【０１４１】
さらに、筆記中のペンの加速度を考慮するために、トライグラムモデルを使用することができる。トライグラムモデルを使用すると、ページ手書きモデルは式（２８）のように書き換えることができる。
【０１４２】
【数２６】
2004152272.tif 000028
【０１４３】
このモデルのパラメータ（μｘ１、σｘ１、μｙ１、σｙ１、μｘ２、σｘ２、μｙ２、σｙ２）は、訓練データから得ることができる。訓練データは、例えばワコム（Ｗａｃｏｍ）タブレットによって取り込まれた５０００００ストロークとすることができる。その場合、カメラはアクティブなペンに関連付けられ、それにより、カメラによって取り込まれた画像を、ワコムタブレット上のディジタイザによって取り込まれた画像に関連付けることができる。
【０１４４】
いくつかの初期値を変数に使用することができる。例えば、モデルのパラメータ（μｘ１、σｘ１、μｙ１、σｙ１、μｘ２、σｘ２、μｙ２、σｙ２）は紙のサイズから独立しているとすることができ、モデルの初期値は（０、１．３９０５、０、１．７２９、０、０．５８５７３、０、０．７１５４７）とすることができる。
【０１４５】
カメラ２０３に関して比較的高いサンプリングレート（毎秒６２フレーム超）を有することにより、新しい位置はよりガウス分布に整合する。ただしこれにより、処理すべき画像の数もより多くなる。
【０１４６】
上の（式２７および２８の）モデルは、前述の能動および受動の符号化システムによって提供されビタビ探索アルゴリズムと比較された候補を処理することにより、経路を提供する。しかし実際には、正しい候補がない場合、基本的なビタビ探索アルゴリズムは失敗することになる。この困難に対応するために、スキップ機能を有するビタビ探索システムを使用してこの問題に対処することができる。
【０１４７】
新しいフレームｉについて、候補をＣｉで表す。スキップ機能がない場合は、新しいフレームｉを、前のフレームの候補、すなわち（ｉ−１）番目のフレームの候補であるＣｉ−１にリンクして、確率ｐｉを得る。しかしスキップ機能がある場合は、新しいフレームｉを、前のフレーム（ｉ−１）だけでなく前のフレーム（ｉ−２、ｉ−３．．．、ｉ−ｎ）にもリンクする。ｎはスキップ範囲である。
【０１４８】
図７に、作動中のスキップ機能を示す。７０６から７０１までのペン経路（７０６−７０５−７０４−７０３−７０２−７０１として表す）は、ペンが各点を通過することを含む。取り込まれた画像フレーム間でペンが過度に大きくは動かなかった確率の方が高いので、点７０２は誤っているかもしれない。点７０２を分析から除外するために、スキップ機能を用いることができる。図７には、スキップする点の数の増加に伴った線分（点線）が示されている。この結果、線分７０６−７０５−７０４−７０３−７０１（ｎ＝１の場合）、７０６−７０５−７０４−７０１（ｎ＝２の場合）、７０６−７０５−７０１（ｎ＝３の場合）が得られる。
【０１４９】
バイグラムモデルは、Ｐｒ（Ｌ）＝Ｐｒ（ｌｋ−１）×Ｐｒ（ｌｋ｜ｌｋ−１）として表すことができる。スキップ機能がある場合、バイグラムモデルは
【０１５０】
【数２７】
2004152272.tif 000029
【０１５１】
として表すことができる。トライグラムモデル（手書きモデルに基づく）は、スキップ機能がある場合、式（２９）のように表すことができる。
【０１５２】
【数２８】
2004152272.tif 000030
【０１５３】
以上のスキップ機能の適合に基づいて、いくつかの経路をリンクすることができる。これらの経路のうち、最大の確率を有する経路をペンの経路として選択することができる。
【０１５４】
図１０に、ペンの経路を決定するプロセスを示す。ステップ１００１でプロセスが開始する。点線ボックス中には、ステップ１００２で受動符号を使用してステップ１００３で受動符号候補を得る任意選択のステップと、ステップ１００４で能動符号を使用してステップ１００５で能動符号候補を得る任意選択のステップが示してある。ステップ１００６で、１つまたは複数の候補セットを共にグループ化する。ステップ１００７で、ステップ１００６からの様々な候補に対してビタビ探索を行う。ステップ１００８で、選択された点のグループを進むペン経路の最大確率に基づいてペン経路を選択する。最後にステップ１００９で、ペンの経路を出力する。この出力は、結果をコンピュータ画面上に表示することを含んでもよく、あるいは電子インクの注釈を文書と共に記憶するようにしてもよい。
【０１５５】
添付の特許請求の範囲を用いて本発明を定義したが、本発明は、本明細書で述べた要素およびステップの任意の組合せまたは下位の組合せを含み、したがってこれらの特許請求の範囲は例示である。したがって、本発明を定義するための代替の組合せには任意の数があり、これらの組合せは、説明と特許請求の範囲と図面とを含めた本明細書からの１つまたは複数の要素の、様々な組合せまたは下位の組合せを組み込む。本発明の態様の代替の組合せを、単独で、あるいは本明細書に定義した１つまたは複数の要素またはステップとの組合せで、本発明の修正または改変としてあるいは本発明の一部として利用できることは、本明細書に鑑みて関連技術の当業者には明らかであろう。本明細書に含まれる本発明についての書面記述は、このような修正および改変をすべてカバーする。
【図面の簡単な説明】
【０１５６】
【図１】本発明の実施形態と共に使用することのできるコンピュータの一般的な記述を示す図である。
【図２Ａ】本発明の実施形態による画像取込みシステムを示す図である。
【図２Ｂ】本発明の実施形態による、画像取込みシステムに対応する取り込まれた画像を示す図である。
【図３Ａ】本発明の実施形態に従って情報を符号化する様々な系列の１つを示す図である。
【図３Ｂ】本発明の実施形態に従って情報を符号化する様々な系列の１つを示す図である。
【図３Ｃ】本発明の実施形態に従って情報を符号化する様々な系列の１つを示す図である。
【図３Ｄ】本発明の実施形態に従って情報を符号化する様々な折畳み技法の１つを示す図である。
【図３Ｅ】本発明の実施形態に従って情報を符号化する様々な折畳み技法の１つを示す図である。
【図３Ｆ】本発明の実施形態に従って情報を符号化する様々な折畳み技法の１つを示す図である。
【図４】本発明の実施形態に従って画像を符号化する方法を示す図である。
【図５】本発明の実施形態による、あり得るペン移動経路の選択肢を示す図である。
【図６】本発明の実施形態による、あり得るペン移動経路の選択肢を示す図である。
【図７】本発明の実施形態による、あり得るペン移動経路の選択肢を示す図である。
【図８Ａ】本発明の実施形態による、符号グループの決定を示す図である。
【図８Ｂ】本発明の実施形態による、符号グループの決定を示す図である。
【図９】本発明の実施形態による、符号をグループに分割することを示す図である。
【図１０】本発明の実施形態による、ペンの経路を決定するプロセスを示す図である。
【符号の説明】
【０１５７】
１００  コンピュータ
１０１  キーボード
１０２  マウス
１０６  シリアルポートインタフェース
１０７  モニタ
１０８  ビデオアダプタ
１０９  リモートコンピュータ
１１０  処理ユニット
１１１  メモリ記憶デバイス
１１２  ローカルエリアネットワーク
１１３  広域ネットワーク
１１４  ネットワークインタフェース
１１５  モデム
１２０  システムメモリ
１３０  システムバス
１４０  ＲＯＭ
１５０  ＲＡＭ
１６０  ＢＩＯＳ
１６５  ディジタイザ
１６６  ペンまたはスタイラス
１７０  ハードディスクドライブ
１８０  磁気ディスクドライブ
１９０  取外し可能磁気ディスク
１９１  光ディスクドライブ
１９２  取外し可能光ディスク
１９２  ハードディスクインタフェース
１９３  磁気ディスクドライブインタフェース
１９４  光ドライブインタフェース
１９５  オペレーティングシステム
１９６  アプリケーションプログラム
１９７  その他のプログラムモジュール
１９８  プログラムデータ
２０１  ペン
２０２  ペンチップ
２０３  カメラ
２０４  画像
２０６  センサおよび／またはプロセッサ
２０７  対象面
２０８  レンズ
２０９  画像面
２１０  画像
２１１  画像取込みセンサ
２１２  仮想ペンチップ
【図１】
2004152272.tif 000031
【図２Ａ】
2004152272.tif 000032
【図２Ｂ】
2004152272.tif 000033
【図３Ａ】
2004152272.tif 000034
【図３Ｂ】
2004152272.tif 000035
【図３Ｃ】
2004152272.tif 000036
【図３Ｄ】
2004152272.tif 000037
【図３Ｅ】
2004152272.tif 000038
【図３Ｆ】
2004152272.tif 000039
【図４】
2004152272.tif 000040
【図５】
2004152272.tif 000041
【図６】
2004152272.tif 000042
【図７】
2004152272.tif 000043
【図８Ａ】
2004152272.tif 000044
【図８Ｂ】
2004152272.tif 000045
【図９】
2004152272.tif 000046
【図１０】
2004152272.tif 000047