(57)【要約】【課題】  ペン先を文書にわたって移動させる間にペン先のパスを判定するシステムおよび方法を提供する。【解決手段】  文書は迷路パターンでウォーターマークが入れられ、エンコードされた位置情報がそこから判定される。画像のシーケンスは、ペンに配置されているカメラによって捕捉される。ペン先のパスは、関連の迷路パターンをデコーディングし、捕捉された画像を文書画像と照合することによって判定される。ストロークに関連付けられている任意のフレームの位置座標をｍ配列デコーディングから判定することができない場合、フレームは変換され、次いで文書画像のエリアと照合される。少なくとも１つのフレームの位置座標が判定されると、隣接するエリア内のフレームを照合することによって他のフレームの位置座表を判定することができる。【選択図】  図１５
2005235185.tif 000002
【特許請求の範囲】
【請求項１】
文書内のペン先のパスを判定する方法であって、
（Ａ）捕捉画面に関連付けられている抽出ビットをデコーディングして前記捕捉画面の位置座標を判定するステップと、
（Ｂ）（Ａ）に応答して、前記捕捉画像の前記位置座標をデコーディングによって判定することができない場合、前記捕捉画像を前記文書の画像情報と照合するステップと、
（Ｃ）前記ペン先の前記パスを前記捕捉画像の前記位置座標から前記ペンの前記ペン先の前記位置座標にマッピングするステップと
を備えることを特徴とする方法。
【請求項２】
前記画像情報は、ウォーターマーク入り文書画像情報、または前記捕捉画像に対応するデコードされた位置の隣接するエリアの画像情報から選択されることを特徴とする請求項１に記載の方法。
【請求項３】
（Ｄ）ｍ配列に対応する迷路パターンを分析して前記捕捉画像からビットを抽出するステップ
をさらに備えることを特徴とする請求項１に記載の方法。
【請求項４】
（Ｅ）前記迷路パターンを塞ぐ前記捕捉画像の障害物構成要素（ｏｂｓｔｒｕｃｔｉｏｎ  ｃｏｍｐｏｎｅｎｔ）から前記迷路パターンを分けるステップ
をさらに備えることを特徴とする請求項３に記載の方法。
【請求項５】
（Ｅ）は
（ｉ）不均一の照度を補償するために前記捕捉画像を標準化するステップ
を含むことを特徴とする請求項４に記載の方法。
【請求項６】
（Ｂ）は、
（ｉ）前記捕捉画像を前記文書の画像のエリアと照合するステップであって、前記エリアは前記文書の前記画像、または隣接する画像フレームの対応する位置を分析することによって推定され、前記対応する位置はｍ配列デコーディングまたはグローバル位置測定によって判定されるステップ
を含むことを特徴とする請求項１に記載の方法。
【請求項７】
（Ｂ）は、
（ｉｉ）（ｉ）に応答して、前記位置座標を判定できない場合、前記捕捉画像をワープさせるステップと、
（ｉｉｉ）前記捕捉画像を前記文書のエリアと照合するステップであって、ｘ−ｙ位置はｍ配列デコーディングによって一意に判定できないステップと
をさらに含むことを特徴とする請求項６に記載の方法。
【請求項８】
（Ｂ）は、
（ｉｖ）（ｉｉｉ）に応答して（ｉ）を繰り返すステップ
をさらに含むことを特徴とする請求項７に記載の方法。
【請求項９】
（Ｄ）前記エリアは前記文書の内容によって塞がれ、前記文書はウォーターマーク入りである、前記文書の前記エリアを判定するステップ
をさらに備えることを特徴とする請求項７に記載の方法。
【請求項１０】
（Ｄ）較正パラメータを取得するために前記ペン先を較正するステップをさらに備え、（Ｃ）は、前記較正パラメータ、およびローカル位置測定から取得された射影変換を使用するステップを含む
ことを特徴とする請求項１に記載の方法。
【請求項１１】
（Ｄ）は、
（ｉ）前記ペン先を前記文書上の接点に固定するステップと、
（ｉｉ）ペンのカメラの中心の位置を変更するステップと、
（ｉｉｉ）前記ペンのカメラの中心の前記位置を前記接点にマッピングするステップと
を含むことを特徴とする請求項１０に記載の方法。
【請求項１２】
前記較正パラメータは仮想ペン先位置であることを示すことを特徴とする請求項１０に記載の方法。
【請求項１３】
（Ａ）は、
（ｉ）捕捉された配列に関連付けられている前記抽出ビットを取得するステップと、
（ｉｉ）前記抽出ビットを処理して、前記抽出ビットが少なくとも１つのエラービットを含んでいるかどうかを判定し、エラービットが検出されない場合、前記位置座標を判定するステップと、
（ｉｉｉ）前記少なくとも１つのエラービットが検出された場合、前記抽出ビットをさらに処理して、前記抽出ビットの一部から前記位置座標を判定するステップと
を含み、
前記位置座標は位置の制約と一致する
ことを特徴とする請求項１に記載の方法。
【請求項１４】
（ｉｉ）は、
（１）前記抽出ビットから第１のサブセットを選択するステップと、
（２）前記第１のサブセットをデコードするステップと、
（３）（２）に応答して、エラービットが検出されない場合、前記捕捉された配列の前記位置座標を判定するステップと
を含むことを特徴とする請求項１３に記載の方法。
【請求項１５】
（ｉｉｉ）は、
（１）エラービットが検出された場合、前記抽出ビットから異なるサブセットを選択するステップであって、前記異なるサブセットのうちの少なくとも１ビットは前に正しくデコードされたビットのうちの１つではないステップと、
（２）前記異なるサブセットの関連するビットをデコードするステップと、
（３）（２）に応答して、別のデコーディングの反復を実行するべきかどうかを判定するステップと
（４）別のデコーディングの反復を実行すべきである場合、前記抽出ビットから別のサブセットを選択し、前記別のサブセットのうちの少なくとも１ビットが前の各反復の誤ってデコードされたビットの組から選択され、（２）を繰り返すステップと、
（５）別のデコーディングの反復を実行する必要がない場合、前記捕捉された配列の前記位置座標を判定するステップと
を含むことを特徴とする請求項１３に記載の方法。
【請求項１６】
（Ｄ）は、
（ｉ）前記迷路パターンのグリッド線を特徴付けるパターンパラメータを算出するステップ
を含むことを特徴とする請求項３に記載の方法。
【請求項１７】
（ｉｉ）は、
（１）迷路パターン分析から取得されたアフィン変換を適用することによって捕捉画像をスケール変更し、回転するステップと、
（２）前記捕捉された迷路パターンを検索領域の選択された点に合わせるステップと
を含むことを特徴とする請求項７に記載の方法。
【請求項１８】
（ｉｉ）は、
（３）前記ワープされたフレームを文書画像と照合するステップであって、前記ワープされたフレームは最大の相互相関値に対応するステップ
をさらに含むことを特徴とする請求項１７に記載の方法。
【請求項１９】
（Ｃ）は、
（ｉ）射影変換を使用して仮想ペン先座標からペン先位置座標を算出するステップ
を含むことを特徴とする請求項１に記載の方法。
【請求項２０】
（Ｄ）は、
（ｉ）ウォーターマーク入りである文書画像を取得するステップ
を含むことを特徴とする請求項９に記載の方法。
【請求項２１】
（Ｄ）は、
（ｉｉ）ピクセルの隣接するウィンドウが迷路パターンセルのみを含んでいるかどうかを判定するステップであって、前記文書画像は複数のサブウィンドウによって表されるステップと、
（ｉｉｉ）前記サブウィンドウが前記迷路パターンのみを含んでいるわけではない場合、可視の迷路パターンセルの測定を区別するステップと
をさらに含むことを特徴とする請求項２０に記載の方法。
【請求項２２】
（ｉｉｉ）は、
（１）前記文書画像を、実質的に迷路パターンセルと同じサイズを有する複数のブロックに分割するステップと、
（２）対応する小さいブロックが文書内容によって塞がれる場合、隣接するウィンドウ内の完全に可視のブロックの数をピクセルを前記ウィンドウの前記中心として数えるステップと、
（３）前記可視ブロックの数を示すインジケータで前記ピクセルをラベル付けするステップと、
を含むことを特徴とする請求項２１に記載の方法。
【請求項２３】
請求項１に記載の前記方法を実行するコンピュータ実行可能命令を有することを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項２４】
請求項３に記載の前記方法を実行するコンピュータ実行可能命令を有することを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項２５】
請求項６に記載の前記方法を実行するコンピュータ実行可能命令を有することを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項２６】
請求項９に記載の前記方法を実行するコンピュータ実行可能命令を有することを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項２７】
請求項１０に記載の前記方法を実行するコンピュータ実行可能命令を有することを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項２８】
文書内のペン先のパスを判定する装置であって、
捕捉画像に関連付けられている抽出ビットをデコードするデコーディングモジュールと、
前記捕捉画像の位置座標を前記デコーディングモジュールによって判定できない場合、前記捕捉画像を前記文書の画像情報と照合する照合モジュールと、
前記ペン先の前記パスを前記捕捉画像の前記位置座標からマッピングし、パス情報を提供するマッピングモジュールと
を備えたことを特徴とする装置。
【請求項２９】
前記ペン先に対するペンの移動情報から較正パラメータを判定する較正モジュールをさらに備え、前記マッピングモジュールは前記捕捉画像の前記位置座標とともに変換および前記較正パラメータを使用して前記ペン先の前記パスをマッピングする
ことを特徴とする請求項２８に記載の装置。
【請求項３０】
エリアは文書の内容によって塞がれ、前記文書はウォーターマーク入りである、前記文書の前記エリアを判定し、前記エリアに関する前記画像情報を提供するウォーターマーク入り文書アナライザ
をさらに備えたことを特徴とする請求項２８に記載の装置。
【請求項３１】
前記捕捉画像の迷路パターンに関連付けられている前記抽出ビットを抽出し、前記デコーディングモジュールに前記抽出ビットを提供する迷路パターンアナライザ
をさらに備えたことを特徴とする請求項２８に記載の装置。
【請求項３２】
前記迷路パターンを塞ぐ文書内容を含む前記捕捉画像の障害物構成要素から前記迷路パターンを分ける画像セグメント化モジュール
をさらに備えたことを特徴とする請求項３１に記載の装置。
【請求項３３】
文書内のペンのペン先のパスを判定する方法であって、
（Ａ）較正パラメータを取得するために前記ペンを較正するステップと、
（Ｂ）ｘ−ｙ位置をｍ配列デコーディングによって一意に判定できないエリアを判定するために、ウォーターマーク入り文書画像を分析するステップと、
（Ｃ）前記迷路パターンを塞ぐ文書内容を含む捕捉画像の障害物構成要素から迷路パターンを分けるステップと、
（Ｄ）前記迷路パターンを分析して捕捉画像の前記迷路パターンからビットを抽出するステップと、
（Ｅ）（Ｄ）に応答して、画像位置座標を実際の位置座標に変換する変換を判定するステップであって、前記実際の位置座標は前記文書に対する前記ペン先の位置を識別するステップと、
（Ｆ）前記捕捉画像に関連付けられている前記抽出ビットをデコードするステップと、
（Ｇ）（Ｆ）に応答して、前記捕捉画像の前記位置座標を判定することができない場合、前記捕捉画像を画像情報と照合するステップであって、
（ｉ）前記捕捉画像をワープさせるステップと、
（ｉｉ）前記ワープされた画像を前記文書のエリアと照合するステップであって、対応するｘ−ｙ位置はｍ配列デコーディングによって一意に判定できないステップと
を含むステップと、
（Ｈ）ペンストロークに関連付けられている他の画像フレームの画像位置座標を判定するステップであって、
（ｉ）対応する捕捉画像を前にデコードされた画像の前記画像位置座標の隣接するエリアと照合するステップと、
（ｉｉ）前記ペンストロークのすべての画像フレームが処理されるまで（ｉ）を繰り返すステップと
を含むステップと、
（Ｉ）前記変換、前記較正パラメータ、および前記画像位置座標から前記ペン先の前記パスをマッピングするステップと
を備えることを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタルペンを使用した媒体との対話に関する。より詳細には、本発明は、１つまたは複数の面との対話中のデジタルペンの位置の判定に関する。
【背景技術】
【０００２】
コンピュータユーザは、パーソナルコンピュータとの対話の一手段としていつもマウスおよびキーボードを使用している。パーソナルコンピュータは、手書きの文書よりいくつかの利点を提供するが、ほとんどのユーザは、印刷物を使用して引き続きいくつかの機能を実行する。こうした機能の一部は、書類を読み、それに注釈を付すことを含む。注釈を付す場合、ユーザによって注釈が付されるため、印刷文書はより大きい意味を帯びる。しかし、注釈付きの印刷文書を持つことに関する問題の１つは、注釈を後で電子形式の文書に入れ直す必要があることである。これは、元のユーザまたは別のユーザが注釈を苦労して読み取り、それらをパーソナルコンピュータに入力することを必要とする。場合によっては、ユーザは、注釈および元のテキストをスキャナで取り込み、それによって新しい文書を作成する。こうした複数のステップは、印刷文書と電子版の文書との間の相互作用を繰り返して扱うのを難しくする。さらに、スキャナで取り込まれた画像は変更できないことが多い。元のテキストから注釈を分離する方法はない。このことは注釈の使用を難しくする。したがって、注釈を処理する改良された方法が必要である。
【０００３】
手書きの情報を捕捉する１つの技術は、筆記中にその位置を判定できるペンを使用することによるものである。この機能を備える１つのペンは、Ａｎｏｔｏ  Ｉｎｃ．によるＡｎｏｔｏペンである。このペンは、カメラを使用して定義済みパターンでエンコードされた用紙の画像を捕捉することによって機能する。画像パターンの一例を図１１に示している。このパターンを（Ａｎｏｔｏ  Ｉｎｃ．による）Ａｎｏｔｏペンが使用して用紙上のペンの位置を判定する。しかし、Ａｎｏｔｏペンが使用しているシステムによる位置の判定がどの程度効率的かは不明瞭である。捕捉画像の位置の効率的な判定を提供するために、捕捉画像の効率的なデコーディングを提供するシステムが必要である。
【０００４】
文書を調べるとき、ユーザは、文書に対してペン先を移動させることによって文書に注釈を付すことができる。ペン先のパスは、複数のストロークを含み、各ストロークは、一連の捕捉画像に対応する。したがって、この業界では文書への注釈を処理するためにペンのパスを識別することが真に必要である。
【０００５】
いくつかの文献に上述のような従来の技術に関連した技術内容が開示されている（例えば、特許文献１、非特許文献１参照）。
【０００６】
【特許文献１】米国特許第６、５５１、３５７号明細書
【非特許文献１】Douglas W. Clark and 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)
【発明の開示】
【発明が解決しようとする課題】
【０００７】
従来のシステムには上述したような種々の問題があり、さらなる改善が望まれている。
【０００８】
本発明は、このような状況に鑑みてなされたもので、その目的とするところは、ｍ配列デコーディングおよび高速画像照合によるストロークの位置測定（ｌｏｃａｌｉｚａｔｉｏｎ）を実現する方法および装置を提供することにある。
【課題を解決するための手段】
【０００９】
本発明の態様は、ペン先を文書にわたって移動させる間にペン先のパスを判定するシステムおよび方法を提供する。本発明の一態様では、文書は、迷路パターンでウォーターマークが入れられ、エンコードされた位置情報がそこから判定される。
【００１０】
本発明の別の態様では、ペンに配置されているカメラによって一連の画像が捕捉される。関連の迷路パターン（ｍ配列）をデコーディングし、捕捉された画像を文書画像と照合することによってペン先のパスが判定される。
【００１１】
本発明の別の態様では、ストロークに関連付けられている任意のフレーム（捕捉画像に対応）の位置座標をｍ配列デコーディングから判定できない場合、フレームは変換され、次いで文書画像のエリアと照合される。少なくとも１つのフレームの位置座標が判定されると、隣接するエリア内のフレームを照合することによって他のフレームの位置座表を判定することができる。
【００１２】
本発明の別の態様では、射影変換および較正パラメータを使用してペン先のパス（ストロークに対応）がフレームの中心からマッピングされる。射影変換は、迷路パターン分析から、およびカメラで捕捉された画像を文書画像と照合することによって取得される。
【００１３】
本発明の上記の概要、および下記の好適実施形態の詳細な説明は、添付の図面と併せ読めばよりよく理解できる。添付の図面は、一例として含まれており、主張した本発明に関する限定のためのものではない。
【発明を実施するための最良の形態】
【００１４】
以下、図面を参照して本発明を適用できる実施形態を詳細に説明する。本発明の態様は、より大きい画像に対して捕捉画像の位置を判定することに関する。本明細書に記載した位置判定方法およびシステムを、多機能ペンとともに使用することができる。
【００１５】
下記は、読者のために副題によって区切られている。副題は、用語、汎用コンピュータ、画像捕捉ペン、配列のエンコーディング、デコーディング、エラー訂正、位置判定、ｍ配列のデコーディング、およびペンのパスを判定するためのアーキテクチャを含む。
【００１６】
用語 
ペン−何らかの筆記用具。インクを蓄える機能を含んでいても、含んでいなくてもよい。一部の例では、本発明の実施形態によるペンとしてインク機能のないスタイラスを使用することができる。
【００１７】
カメラ−用紙または他の任意の媒体から画像を捕捉し得る画像捕捉システム。
【００１８】
汎用コンピュータ 
図１は、本発明の様々な態様の実施に使用できる従来の汎用デジタルコンピューティング環境の例の機能ブロック図である。図１では、コンピュータ１００は、処理ユニット１１０、システムメモリ１２０、およびシステムメモリを含む様々なシステム構成要素を処理ユニット１１０に結合するシステムバス１３０を含む。システムバス１３０は、様々なバスアーキテクチャのうちの任意のものを使用するメモリバスまたはメモリコントローラ、周辺バス、およびローカルバスを含むいくつかのタイプのバス構造のうちどんなものでもよい。システムメモリ１２０は、読み取り専用メモリ（ＲＯＭ）１４０およびランダムアクセスメモリ（ＲＡＭ）１５０を含む。
【００１９】
ＢＩＯＳ（Basic Input/Output System）１６０は、例えば起動中など、コンピュータ１００内の要素間での情報の転送を助ける基本ルーチンを含み、ＲＯＭ１４０に格納されている。コンピュータ１００は、ハードディスク（図示せず）から読み取り、そこに書き込むハードディスクドライブ１７０、リムーバブル磁気ディスク１９０から読み取り、あるいはそこに書き込む磁気ディスクドライブ１８０、およびＣＤ−ＲＯＭや他の光媒体など、リムーバブル光ディスク１９２から読み取り、あるいはそこに書き込む光ディスクドライブ１９１も含む。ハードディスクドライブ１７０、磁気ディスクドライブ１８０、および光ディスクドライブ１９１は、それぞれハードディスクドライブインタフェース１９２、磁気ディスクドライブインタフェース１９３、および光ディスクドライブインタフェース１９４によってシステムバス１３０に接続される。ドライブおよびその関連のコンピュータ可読媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、およびパーソナルコンピュータ１００の他のデータの不揮発性記憶域を提供する。磁気カセット、フラッシュメモリカード、デジタルビデオディスク、ベルヌーイカートリッジ、ランダムアクセスメモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）など、コンピュータによってアクセス可能なデータを格納できる他のタイプのコンピュータ可読媒体を動作環境の例で使用することもできることを当業者であれば理解されよう。
【００２０】
オペレーティングシステム１９５、１つまたは複数のアプリケーションプログラム１９６、他のプログラムモジュール１９７、およびプログラムデータ１９８を含めて、いくつかのプログラムモジュールをハードディスク１７０、磁気ディスク１９０、光ディスク１９２、ＲＯＭ１４０またはＲＡＭ１５０に格納することができる。ユーザは、コマンドおよび情報をキーボード１０１およびポインティング装置１０２などの入力装置を介してコンピュータ１００に入力することができる。他の入力装置（図示せず）には、マイクロフォン、ジョイスティック、ゲームパッド、衛星放送受信アンテナ、スキャナなどがある。これらおよび他の入力装置は、しばしばシステムバスに結合されているシリアルポートインタフェース１０６を介して処理ユニット１１０に接続されるが、パラレルポート、ゲームポート、ユニバーサルシリアルバス（ＵＳＢ）など他のインタフェースで接続してもよい。さらにこれらの装置は、適切なインタフェース（図示せず）を介してシステムバス１３０に直接結合することができる。モニタ１０７または他のタイプの表示装置もまた、ビデオアダプタ１０８などのインタフェースを介してシステムバス１３０に接続される。パーソナルコンピュータは一般に、モニタに加えて、スピーカやプリンタなどの他の周辺出力装置（図示せず）を含んでいる。好適実施形態では、手書きの入力をデジタル捕捉するためにペンデジタイザ１６５および付属のペンまたはスタイラス１６６が設けられている。ペンデジタイザ１６５とシリアルポートとの間の直接接続が示されているが、実際には、ペンデジタイザ１６５は、当分野で知られているように、パラレルポート、または他のインタフェースおよびシステムバス１３０を介して処理ユニット１１０に直接結合することができる。さらに、デジタイザ１６５は、モニタ１０７から切り離して示しているが、デジタイザ１６５の使用可能な入力エリアは、モニタ１０７の表示エリアと同一の広がりを持つことが好ましい。さらにデジタイザ１６５は、モニタ１０７に一体化することができ、またはモニタ１０７に重なる、そうでない場合はモニタ１０７に取り付けられた個別の装置として存在してもよい。
【００２１】
コンピュータ１００は、リモートコンピュータ１０９など１つまたは複数のリモートコンピュータへの論理接続を使用してネットワーク式環境で動作することができる。リモートコンピュータ１０９は、サーバ、ルータ、ネットワークＰＣ（personal computer）、ピアデバイス、または他の一般のネットワークノードでよく、一般にコンピュータ１００に関連して上述した多くまたはすべての要素を含むが、図１にはメモリ記憶装置１１１のみを示している。図１に示した論理接続は、ローカルエリアネットワーク（ＬＡＮ）１１２および広域ネットワーク（ＷＡＮ）１１３を含む。こうしたネットワーキング環境は、オフィス、全社規模のコンピュータネットワーク、イントラネット、およびインターネットではごく一般的である。
【００２２】
ＬＡＮネットワーキング環境で使用する場合、コンピュータ１００は、ネットワークインタフェースまたはアダプタ１１４を介してローカルネットワーク１１２に接続される。ＷＡＮネットワーキング環境で使用する場合、パーソナルコンピュータ１００は一般に、モデム１１５、またはインターネットなど広域ネットワーク１１３を介して通信を確立する他の手段を含む。モデム１１５は、内蔵のものでも外付けのものでもよく、シリアルポートインタフェース１０６を介してシステムバス１３０に接続される。ネットワーク式環境では、パーソナルコンピュータ１００に関連して示したプログラムモジュール、またはその一部をリモートメモリ記憶装置に格納することができる。
【００２３】
図示したネットワーク接続は例であり、コンピュータ間の通信リンクを確立する他の技術を使用できることは理解されよう。ＴＣＰ／ＩＰ（Transmission Control Protocol/Internet Protocol）、Ｅｔｈｅｒｎｅｔ（登録商標）、ＦＴＰ（file transfer protocol）、ＨＴＴＰ（HyperText Transport Protocol）、Ｂｌｕｅｔｏｏｔｈ（商標）、ＩＥＥＥ（Institute of Electrical and Electronics Engineers）８０２．１１ｘなど様々なよく知られている任意のプロトコルの存在が想定され、システムは、ユーザがＷｅｂベースのサーバからＷｅｂページを取り出すことができるようにクライアント−サーバ構成で動作することができる。様々な従来のＷｅｂブラウザの任意のものを使用してＷｅｂページ上にデータを表示し、それを操作することができる。
【００２４】
画像捕捉ペン 
本発明の態様は、エンコードされたデータストリームを、エンコードされたデータストリームを表す表示形式にすることを含む（例えば図４Ｂで説明するように、エンコードされたデータストリームを使用してグラフィカルパターンを作成する）。表示形式は、印刷物（または他の物理的な媒体）、または別の画像または画像の組とともにエンコードされたデータストリームを投影する表示とすることができる。例えば、エンコードされたデータストリームは、用紙上の物理的なグラフィカル画像、（例えばドキュメントのテキストを表す）表示された画像上に重なるグラフィカル画像として表され得る、または表示画面上の物理的な（変更できない）グラフィカル画像とすることができる（そのため、ペンによって捕捉された任意の画像部分は、表示画面上で位置を突き止めることができる）。
【００２５】
捕捉画像のこの位置の判定を使用して、用紙、媒体、または表示画面とのユーザの対話の位置を判定することができる。本発明の一部の態様では、ペンは、用紙上に筆記するインクペンとすることができる。別の態様では、ペンは、ユーザがコンピュータディスプレイの表面上に書くスタイラスとすることができる。文書上のエンコードされた画像の知識を有する、またはコンピュータ画面上に表示された文書をサポートするシステムに、任意の対話を戻すことができる。ペンまたはスタイラスが文書を横切るときにペンまたはスタイラスのカメラで画像を繰り返し捕捉することによって、システムは、ユーザによって制御されているスタイラスの動きを追跡することができる。表示された、または印刷された画像は、空白の、または内容が豊富な用紙に関連付けられているウォーターマーク、または表示された画像に関連付けられているウォーターマーク、または画面上に重なる、または画面に組み込まれている固定コーディングに関連付けられているウォーターマークとすることができる。
【００２６】
図２Ａおよび図２Ｂは、カメラ２０３を備えるペン２０１の例を示している。ペン２０１は、インク筒を含む、または含まない先端２０２を含む。カメラ２０３は、面２０７から画像２０４を捕捉する。ペン２０１は、破線で示したボックス２０６で表すように追加のセンサーおよび／またはプロセッサをさらに含んでいてもよい。また、これらのセンサーおよび／またはプロセッサ２０６は、（例えばＢｌｕｅｔｏｏｔｈ（商標）または他の無線プロトコルを介して）情報を別のペン２０１および／またはパーソナルコンピュータに送信する機能を含んでいてもよい。
【００２７】
図２Ｂは、カメラ２０３から見た画像を表す。一例では、カメラ２０３の視野（すなわちカメラの画像センサーの解像度）は、（Ｎ＝３２の場合）３２×３２ピクセルである。この実施形態では、捕捉画像（３２ピクセル×３２ピクセル）は、カメラ２０３によって捕捉された平面の約５ｍｍ×５ｍｍのエリアに相当する。したがって図２Ｂは、長さ３２ピクセル×幅３２ピクセルの視野を示す。Ｎのサイズは調整可能であり、したがってＮが大きくなると、画像の解像度はより高くなる。また、カメラ２０３の視野は、ここでは例示の目的で正方形として示しているが、当分野で知られているように、他の形状を含むことができる。
【００２８】
カメラ２０３によって捕捉された画像を一連の画像フレーム｛Ｉｉ｝として定義することができる。ここではＩｉは、サンプリング時ｔｉにペン２０１によって捕捉される。サンプリングレートは、システム構成およびパフォーマンス要件に応じて高い場合も低い場合もある。捕捉画像フレームのサイズは、システム構成およびパフォーマンス要件に応じて大きい場合も小さい場合もある。
【００２９】
カメラ２０３によって捕捉された画像は、処理システムによって直接使用することもプレフィルタリングにかけることもできる。このプレフィルタリングは、ペン２０１で行うこともペン２０１の外部（パーソナルコンピュータなど）で行うこともできる。
【００３０】
図２Ｂの画像サイズは３２×３２ピクセルである。各エンコーディング単位サイズが３×３ピクセルである場合、捕捉されたエンコード済み単位の数は約１００単位となる。エンコーディング単位サイズが５×５ピクセルである場合、捕捉されたエンコード済み単位の数は約３６となる。
【００３１】
図２Ａは、位置２０４からのパターンの画像２１０が形成される画像平面２０９も示している。対象平面２０７上のパターンから受信された光は、レンズ２０８によって集束される。レンズ２０８は、単レンズでもマルチパートレンズシステム（ｍｕｌｔｉ−ｐａｒｔ  ｌｅｎｓ  ｓｙｓｔｅｍ）でもよいが、ここでは簡潔にするために単レンズとして表す。画像捕捉センサー２１１は、画像２１０を捕捉する。
【００３２】
画像センサー２１１は、画像２１０を捕捉できるほど大きいものとすることができる。あるいは画像センサー２１１は、位置２１２でペン先２０２の画像を捕捉できるほど大きいものとすることができる。参照のために、位置２１２の画像を仮想ペン先と呼ぶ。ペン先、レンズ２０８、および画像センサー２１１の間の関係が一定であるため、画像センサー２１１に対する仮想ペン先の位置は固定されることに留意されたい。
【００３３】
次の変換Ｆｓ→ｐは、カメラによって捕捉された画像における位置座標を用紙上の実画像における位置座標に変換する。
【００３４】
Ｌｐａｐｅｒ＝Ｆｓ→ｐ（Ｌｓｅｎｓｏｒ）
筆記中、ペン先および用紙は同じ平面上にある。したがって、仮想ペン先から実ペン先への変換もＦｓ→ｐであり、
Ｌｐｅｎｔｉｐ＝Ｆｓ→ｐ（Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐ）
となる。
【００３５】
変換Ｆｓ→ｐは、アフィン変換として推定することができる。これは、
【００３６】
【数１】
2005235185.tif 000003
【００３７】
としてＦｓ→ｐの推定として単純化される。式中、θｘ、θｙ、ｓｘ、およびｓｙは、位置２０４で捕捉されたパターンの２つの向きの回転およびスケールである。さらに、捕捉画像を用紙上の対応する実画像と照合することによってＦ’ｓ→ｐを精密化することができる。「精密化」とは、再帰的方法と呼ばれる一種の最適化アルゴリズムによって変換Ｆｓ→ｐのより正確な推定を得ることを意味する。再帰的方法は、行列Ｆ’ｓ→ｐを初期値として扱う。精密化された推定は、ＳとＰとの間の変換をより正確に表す。
【００３８】
次に、較正によって仮想ペン先の位置を判定することができる。
【００３９】
ペン先２０２は、用紙上の固定位置Ｌｐｅｔｉｐ上に置かれる。次にペンが傾けられ、それによってカメラ２０３は、様々なペンの姿勢の一連の画像を捕捉することができる。捕捉された画像ごとに変換Ｆｓ→ｐを取得することができる。この変換から、仮想ペン先の位置Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐを取得することができる。
【００４０】
Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐ＝Ｆｐ→ｓ（Ｌｐｅｎｔｉｐ）
式中、Ｌｐｅｎｔｉｐは（０，０）として初期設定され、
Ｆｐ→ｓ＝（Ｆｓ→ｐ）−１
である。
【００４１】
各画像から取得されたＬｖｉｒｔｕａｌ−ｐｅｎｔｉｐを平均することによって、仮想ペン先の位置Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐを判定することができる。Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐによって、Ｌｐｅｎｔｉｐのより正確な推定を得ることができる。何度かの反復の後、仮想ペン先の正確な位置Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐを判定することができる。
【００４２】
ここで仮想ペン先の位置Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐはわかった。捕捉された画像から変換Ｆｓ→ｐを取得することもできる。最後に、この情報を使用して、実ペン先の位置Ｌｐｅｎｔｉｐを判定することができる。
【００４３】
Ｌｐｅｎｔｉｐ＝Ｆｓ→ｐ（Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐ）
【００４４】
配列のエンコーディング 
２次元の配列は、１次元シーケンスを折りたたむことによって構築することができる。十分多くのビット数を含む２次元配列の任意の部分を使用して、完全な２次元配列におけるその位置を判定することはできる。しかし、捕捉された１つまたはわずかの画像から位置を判定することが必要な場合がある。捕捉画像の一部分が２次元配列における２つ以上の位置に関連付けられる可能性を最低限に抑えるように、非反復シーケンスを使用して配列を作成することができる。作成されたシーケンスの１つの特性は、シーケンスが長さ（またはウィンドウ）ｎ上で反復しないことである。下記は、１次元シーケンスの作成、次いでシーケンスの配列への折りたたみ（ｆｏｌｄｉｎｇ）を説明する。
【００４５】
シーケンスの構築 
数列をエンコーディングシステムの開始点として使用することができる。例えば、シーケンス（ｍシーケンスとも呼ぶ）を、体（ｆｉｅｌｄ）Ｆｑ内のｑ要素の組として表すことができる。ここではｑ＝ｐｎであり、式中ｎ≧１、ｐは素数である。シーケンスまたはｍシーケンスは、それだけには限定されないが、多項式除算など、様々な異なる技術によって生成することができる。多項式除算を使用して、シーケンスを次のように定義することができる。
【００４６】
【数２】
2005235185.tif 000004
【００４７】
式中Ｐｎ（ｘ）は、（ｑｎ個の要素を有する）体Ｆｑ［ｘ］における次数ｎの原始多項式である。Ｒｌ（ｘ）は、体Ｆｑ［ｘ］における次数ｌ（ｌ＜ｎ）の非ゼロの多項式である。シーケンスは、次の２つのステップで反復手順を使用して作成することができる。第１に２つの多項式を割り（その結果体Ｆｑの要素が得られる）、第２に剰余にｘを掛ける。この演算は、出力が反復を開始すると停止する。このプロセスは、線形帰還シフトレジスタを使用して実施することができる（非特許文献１参照）。この環境では、シーケンスの周期的なシフトと多項式Ｒｌ（ｘ）との間の関係が確立される。つまり、Ｒｌ（ｘ）の変更によってシーケンスの周期的シフトのみが行われ、すべての周期的シフトは多項式Ｒｌ（ｘ）に対応する。結果として得られたシーケンスの特性の１つは、シーケンスはｑｎ−１の周期を有し、ある周期内に、ある幅（または長さ）ｎにわたって、どの部分も一度だけシーケンスに存在するということである。これを「ウィンドウ特性（ｗｉｎｄｏｗ  ｐｒｏｐｅｒｔｙ）」と呼ぶ。周期ｑｎ−１はシーケンスの長さ、ｎはシーケンスの次数とも呼ばれる。
【００４８】
しかし、上記のプロセスは、ウィンドウ特性を有するシーケンスの作成に使用できる様々なプロセスのうちの１つである。
【００４９】
配列の構築 
（一部をカメラによって捕捉できる）画像の作成に使用できる配列（またはｍ配列）は、１次元シーケンスまたはｍシーケンスの拡張である。Ａを周期（ｍ１，ｍ２）の配列、すなわちＡ（ｋ＋ｍ１，ｌ）＝Ａ（ｋ，ｌ＋ｍ２）＝Ａ（ｋ，１）と仮定する。ｎ１×ｎ２ウィンドウがＡの周期をシフトするとき、Ｆｑにわたる非ゼロのｎ１×ｎ２のすべての行列がたった一度だけ現れる。この特性も各ウィンドウが一意であるという点で「ウィンドウ特性」と呼ばれる。
【００５０】
バイナリ配列（またはｍ配列）は、シーケンスを折りたたむことによって構築することができる。１つの手法は、シーケンスを取得し、次いでそれをｍ１×ｍ２のサイズに折りたたむことである。この場合、配列の長さはＬ＝ｍ１×ｍ２＝２ｎ−１である。あるいは、（例えば１枚の用紙、３０枚の用紙、またはコンピュータモニタのサイズなど）カバーしたいあらかじめ定義されているサイズのスペースで開始し、エリア（ｍ１×ｍ２）を判定し、次いでそのサイズを使用してＬ≧ｍ１×ｍ２と仮定することができる。この場合Ｌ＝２ｎ−１である。
【００５１】
異なる様々な折りたたみ技術を使用することができる。例えば、図３Ａから図３Ｃは、異なる３つのシーケンスを示している。これらのそれぞれを図３Ｄに示すような配列に折りたたむことができる。異なる３つの折りたたみ方法は、図３Ｄのオーバーレイ、および図３Ｅおよび３Ｆのラスタパスとして示されている。図３Ｄに示す折りたたみ方法を採用する。
【００５２】
図３Ｄに示すような折りたたみ方法を作成するために、長さＬおよび次数ｎのシーケンス｛ａｉ｝を作成する。次に、配列の各ビットを式１によって示すように算出すると仮定することによって、シーケンス｛ａｉ｝からサイズｍ１×ｍ２の配列｛ｂｋｌ｝が作成される。この場合、ｇｃｄ（ｍ１，ｍ２）＝１およびＬ＝ｍ１×ｍ２である。
【００５３】
ｂｋｌ＝ａｉ                      （１）
式中、ｋ＝ｉｍｏｄ（ｍ１），ｌ＝ｉｍｏｄ（ｍ２），ｉ＝０，…，Ｌ−１である。
【００５４】
この折りたたみ手法は、代わりに、配列の対角線上にシーケンスを配置し、次いで縁に到達すると反対の縁から続くものとして表すことができる。
【００５５】
図４Ａは、図３Ｄの配列のエンコードに使用できるエンコーディング技術のサンプルを示している。他のエンコーディング技術を使用できることを理解されたい。例えば、代替のコーディング技術を図１１に示している。
【００５６】
図４Ａを参照すると、第１のビット４０１（例えば「１」）は、黒インクの列によって表されている。第２のビット４０２（例えば「０」）は、黒インクの行によって表されている。任意のカラーインクを使用して様々なビットを表すことができることを理解されたい。選択されたインクの色についての唯一の必要条件は、有意のコントラストが提供され、媒体の背景が画像捕捉システムによって区別可能であることである。図４Ａのビットは、セルの３×３行列によって表される。行列のサイズは、画像捕捉システムのサイズおよび解像度に基づく任意のサイズに変更することができる。ビット０および１の代替の表現を図４Ｃ〜４Ｅに示している。図４Ａ〜４Ｅのエンコーディングのサンプルでの１またはゼロの表現は、影響無く切り替えることができることを理解されたい。図４Ｃは、交互の配列において２つの行または列を占めるビット表現を示している。図４Ｄは、破線形の行および列のピクセルの代替配列を示している。最後に図４Ｅは、（黒い点２つの後に黒い点１つなど）不規則な間隔の形式での列および行のピクセル表現を示している。
【００５７】
図４Ａに戻って、ビットが３×３行列によって表され、イメージングシステムが３×３領域において黒い行を１つ、および白い行を２つ検出すると、ゼロ（または１）が検出される。黒い列が１つ、白い列が２つの画像が検出されると、１（または０）が検出される。
【００５８】
ここでは、１より大きいピクセルまたはドットを使用して１ビットを表す。単一のピクセル（またはビット）を使用して１ビットを表すのは脆弱である。ほこり、用紙の折り目、平らではない面などは、データ単位の単一のビット表現の読み取りの問題を作り出す。しかし、異なる手法を使用してある面における配列を図示できることを理解されたい。いくつかの手法を図４Ｃから図４Ｅに示している。他の手法を使用することもできることを理解されたい。スペースシフトされたドットのみを使用する１つの手法を図１１に示している。
【００５９】
ビットストリームを使用して、図４Ｂのグラフィカルパターン４０３を作成する。グラフィカルパターン４０３は、１２個の行および１８個の列を含む。行および列は、ビット表現４０１および４０２を使用してグラフィカル表現に変換されるビットストリームによって形成される。図４Ｂは、次のビット表現を有するものとみなすことができる。
【００６０】
【数３】
2005235185.tif 000005
【００６１】
デコーディング
図２Ａのペンで筆記する、またはエンコードされたパターンの近くにペンを移動させるとき、カメラが画像を捕捉する。例えばペン２０１は、用紙に押し付けられ、用紙上の文書を横切るときに圧力センサーを使用し得る。次いで画像は、エンコードされた画像の完全な表現に対して捕捉画像の向きを判定し、捕捉画像を構成するビットを抽出するように処理される。
【００６２】
エンコードされた全エリアに対する捕捉画像の向きの判定では、図５Ａ〜５Ｄに示す考えられる４つのすべてのコーナーがグラフィッカルパターン４０３内に存在し得るとは限らないことに気づくかもしれない。実際、適切な向きでは、図５Ａに示すコーナーのタイプは、グラフィカルパターン４０３に存在しない。したがって、図５Ａに示したコーナーのタイプが欠如している向きが正しい向きである。
【００６３】
続いて図６を参照すると、カメラによって捕捉された画像６０１が分析され、画像６０１によって実際に表される位置に関して解釈可能なようにその向きが判定される。まず、画像６０１を調べて、ピクセルが水平方向および垂直方向に並ぶように画像の回転に必要な角度θが判定される。基礎を成すグリッドの非水平、非垂直方向の配列（例えば４５度）への回転を含めて、代替のグリッド配列が考えられることに留意されたい。ユーザは、他のものより前に水平方向および垂直方向のパターンに注目する傾向があるため、非水平、非垂直方向の配列の使用は、視覚的な混乱のもと（ｖｉｓｕａｌ  ｄｉｓｔｒａｃｔｉｏｎｓ）をユーザから取り除くことのメリットの可能性を提供し得る。簡潔にするために、グリッドの向き（基礎を成すグリッドの水平方向および垂直方向、および他の任意の回転）をまとめて、定義済みグリッド向きと呼ぶ。
【００６４】
次に、画像６０１が分析されて、どのコーナーが欠如しているかを判定する。画像６０１のデコーディングの用意ができている画像６０３への回転に必要な回転量οは、ο＝（θ＋回転量｛どのコーナーが欠如しているかによって定義｝）と示される。回転量は、図７の式によって示される。図６に戻って、まず、ピクセルの水平方向および垂直方向（または他の定義済みグリッド向き）の配列に達するように、ピクセルのレイアウトによって角度θが判定され、画像が６０２に示すように回転される。次いで欠如しているコーナーを判定するために分析が行われ、画像６０２が画像６０３に回転されて、画像をデコーディングのために設定する。ここでは、画像６０３が正しい向きを有し、デコーディングに使用できるように、画像は反時計回りに９０度回転される。
【００６５】
回転角度θを画像６０１の回転の前または後に適用して欠如しているコーナーを考慮に入れることができることを理解されたい。また、捕捉画像におけるノイズを考慮に入れることによって、４つすべてのタイプのコーナーが存在し得ることも理解されたい。各タイプのコーナー数を数え、最も少ない数のタイプを欠如しているコーナータイプとして選択することができる。
【００６６】
最後に、画像６０３におけるコードが読み出され、画像４０３の作成に使用された元のビットストリームと相関させる。相関は、いくつかの方法で実行することができる。例えば、復元されたビットストリームが元のビットストリーム内の他のすべてのビットストリームの断片と比較される再帰的手法によって実行することができる。第２に、例えば、復元されたビットストリームと元のビットストリームとの間のハミング距離を使用することによって２つのビットストリーム間での統計的分析を行うことができる。様々な手法を使用して、元のビットストリーム内の復元されたビットストリームの位置を判定することができることを理解されたい。
【００６７】
復元されたビットを得ると、（例えば図４Ｂに示すものなど）元の配列内の捕捉画像の位置を突き止める必要がある。配列全体内のビットのセグメントの位置を判定するプロセスは、いくつかの項目により複雑になる。まず、捕捉すべき実際のビットは、不明瞭である可能性がある（例えばカメラは文書内容を含む画像を捕捉する可能性があり、これはコードを不明瞭にする）。第２に、ほこり、折り目、反射などもまた、捕捉されたイメージのエラーを作り出す可能性がある。これらのエラーは、位置を突き止めるプロセスをより難しくする。この点で、画像捕捉システムは、画像から抽出された非連続ビットに対して機能する必要がある場合がある。次は、画像からの非連続ビットに対して動作する方法を表す。
【００６８】
ｎがｍシーケンスの次数である場合、シーケンス（またはｍシーケンス）Ｉがべき級数Ｉ（ｘ）＝１／Ｐｎ（ｘ）に対応し、Ｋ≧ｎであり、上付き文字ｔが行列またはベクトルの転置を表す場合、捕捉画像はＩのＫ個のビットｂ＝（ｂ０  ｂ１  ｂ２・・・ｂｋ−１）ｔを含むと仮定する。Ｋビットの位置ｓは、単にｂ０がシーケンスの先頭にシフトされるＩの周期シフト数である。次いでこのシフトされたシーケンスＲは、べき級数ｘｓ／Ｐｎ（ｘ）、すなわちＲ＝Ｔｓ（Ｉ）に対応する。式中、Ｔは周期シフト演算子である。このｓを間接的に見つける。多項式のモジュロＰｎ（ｘ）は体を形成する。ｘｓ≡ｒ０＋ｒ１ｘ＋・・・ｒｎ−１ｘｎ−１ｍｏｄ（Ｐｎ（ｘ））であることが保証される。したがって、（ｒ０，ｒ１，＋・・・，ｒｎ−１）であることがわかり、次いでｓについて解くことができる。
【００６９】
この関係ｘｓ≡ｒ０＋ｒ１ｘ＋・・・ｒｎ−１ｘｎ−１ｍｏｄ（Ｐｎ（ｘ））は、Ｒ＝ｒ０＋ｒ１Ｔ（Ｉ）＋・・・ｒｎ−１Ｔｎ−１（Ｉ）であることを含意している。二元一次方程式で書くと、次のようになる。
【００７０】
Ｒ＝ｒｔＡ                （２）
式中、ｒ＝（ｒ０  ｒ１  ｒ２・・・ｒｎ−１）ｔ、およびＡ＝（Ｉ  Ｔ（Ｉ）・・・Ｔｎ−１（Ｉ））ｔであり、これは０シフトから（ｎ−１）シフトまでのＩの周期シフトから成る。ここで、ｒを解くのに、Ｒにおいて疎のＫビットのみが使用可能である。Ｒにおけるｂｉとｂ０との間の指数の差がｋｉ、ｉ＝１，２，・・・，ｋ−１であると仮定すると、ｉ＝１，２，・・・，ｋ−１の場合のＲの１番目の要素および（ｋｉ＋１）番目の要素は、ちょうどｂ０，ｂ１，・・・，ｂｋ−１となる。ｉ＝１，２，・・・，ｋ−１の場合にＡの１番目の要素および（ｋｉ＋１）番目の要素を選択することによって、次の二元一次方程式が形成される。
【００７１】
ｂｔ＝ｒｔＭ                （３）
式中、ＭはＡのｎ×Ｋ部分行列である。
【００７２】
ｂがエラー無しの場合、ｒの解は次の式で表すことができる。
【００７３】
【数４】
2005235185.tif 000006
【００７４】
式中、
【００７５】
【数５】
2005235185.tif 000007
【００７６】
は、Ｍの任意の非退化のｎ×ｎ部分行列であり、
【００７７】
【数６】
2005235185.tif 000008
【００７８】
はｂの対応する部分行列である。
【００７９】
既知のｒを使用して、Ｐｏｈｌｉｇ−Ｈｅｌｌｍａｎ−Ｓｉｌｖｅｒアルゴリズムを使用して、ｘｓ≡ｒ０＋ｒ１ｘ＋・・・ｒｎ−１ｘｎ−１ｍｏｄ（Ｐｎ（ｘ））になるようなｓを見つけることができる（非特許文献１参照）。
【００８０】
（Ｌ＝２ｎ−１の場合、ｎ×Ｌのサイズの）行列Ａは非常に大きい可能性があるため、行列Ａ全体を格納することは避けるべきである。実際に、上記のプロセスでわかったように、指数差ｋｉの抽出ビットが与えられた場合、Ａの１番目の列および（ｋｉ＋１）番目の列のみが計算に関連する。捕捉画像のサイズが与えられている場合、ｋｉのこうした選択はかなり限られている。したがって、計算に関与し得るこうした列のみを保存すればよい。こうした列の合計数は、Ｌよりかなり小さい（ここではＬ＝２ｎ−１はｍシーケンスの長さである）。
【００８１】
エラー訂正 
ｂにエラーが存在する場合、ｒの解はより複雑になる。エラー訂正を用いたデコーディングの従来の方法は、容易には適用できない。というのは、捕捉画像に関連付けられている行列Ｍは、捕捉されたある画像から別の画像に変わり得るからである。
【００８２】
確率的手法を採用する。ｂでのエラービット数ｎｅがＫに比べて相対的に小さいと仮定すると、ｂのＫビットから正しいｎビットを選択し、対応するＭの部分行列
【００８３】
【数７】
2005235185.tif 000009
【００８４】
が非退化である確率は高い。
【００８５】
選択されたｎビットがすべて正しい場合、ｂｔとｒｔＭとの間のハミング距離、またはｒに関連付けられているエラービット数は最小となるはずである。この場合、ｒは式（４）によって算出される。プロセスを数回繰り返すことによって、最小のエラービットをもたらす正しいｒを識別することができそうである。
【００８６】
最小のエラービット数に関連付けられているｒがたった１つである場合、それが正しい解とみなされる。そうではなく、最小のエラービット数に関連付けられているｒが複数ある場合、ｎｅがＭによって生成されたコードのエラー訂正機能を超える確率が高く、デコーディングプロセスは失敗する。次いでシステムは、次の捕捉画像の処理に進むことができる。別の実装形態では、ペンの前の位置に関する情報を考慮に入れることができる。つまり、捕捉画像ごとに、ペンが次に予想され得る宛先エリアを識別することができる。例えば、ユーザがカメラによる２つの画像の捕捉の間でペンを持ち上げていない場合、第２の画像の捕捉によって判定されるペンの位置は、第１の位置からそれほど離れていないはずである。次いで最小のエラービット数に関連付けられている各ｒをチェックして、ｒから算出された位置ｓが位置の制約を満たしているかどうか、すなわち位置が指定された宛先エリア内にあるかどうかを調べることができる。
【００８７】
位置ｓが位置の制約を満たしている場合、配列内の抽出ビットのＸ、Ｙの位置が戻される。位置の制約を満たしていない場合、デコーディングプロセスは失敗する。
【００８８】
図８は、捕捉画像のシーケンス（またはｍシーケンス）での位置を判定するために使用できるプロセスを示している。まずステップ８０１で、捕捉画像に関連するデータストリームが受信される。ステップ８０２で、対応する列がＡから抽出され、行列Ｍが構築される。
【００８９】
ステップ８０３で、ｎ個の独立した列ベクトルが行列Ｍからランダムに選択され、式（４）を解くことによってベクトルｒが判定される。このプロセスは、ステップ８０４でＱ回（例えば１００回）行われる。ループ回数の判定については、後でループ回数の算出のセクションで説明する。
【００９０】
ステップ８０５で、ｒは、その関連のエラービット数に従ってソートされる。ソートは、当分野で知られている様々なソートアルゴリズムを使用して行うことができる。例えば、選択ソートアルゴリズムを使用することができる。選択ソートアルゴリズムは、回数Ｑが大きくない場合には有用である。しかし、Ｑが大きくなると、大きい項目数をより効率的に扱う他のソートアルゴリズム（マージソートなど）を使用することができる。
【００９１】
次いでシステムは、ステップ８０６で、複数のｒが最小のエラービット数に関連付けられているかどうかをチェックすることによってエラー訂正がうまく行われたかどうかを判定する。複数のｒが最小のエラービット数に関連付けられている場合、ステップ８０９でエラーが戻され、デコーディングプロセスが失敗したことを知らせる。そうでない場合、ステップ８０７で、例えばＰｏｈｉｇ−Ｈｅｌｌｍａｎ−Ｓｉｌｖｅｒアルゴリズムを使用することによってシーケンス（ｍシーケンス）内の抽出ビットの位置ｓが算出される。
【００９２】
次に、ステップ８０８で、配列内の（Ｘ，Ｙ）位置がｘ＝ｓ  ｍｏｄ  ｍ１およびｙ＝ｓ  ｍｏｄ  ｍ２として算出され、結果が戻される。
【００９３】
位置判定 
図９は、ペン先の位置を判定するプロセスを示している。入力は、カメラによって捕捉された画像であり、出力は、ペン先の位置座標とすることができる。また、出力は、捕捉画像の回転角度など、他の情報を含んでいても（または含んでいなくても）よい。
【００９４】
ステップ９０１で、画像がカメラから受信される。次に、明るいピクセルと暗いピクセルとの間のコントラストを調整するなど、ステップ９０２（ステップ９０２の破線の外枠によって示すように）で、受信された画像を任意選択で前処理にかけることができる。
【００９５】
次にステップ９０３で、画像が分析されて、その中のビットストリームが判定される。
【００９６】
次にステップ９０４で、ｎ個のビットがビットストリームから複数回ランダムに選択され、元のシーケンス（またはｍシーケンス）内の受信されたビットストリームの位置が判定される。
【００９７】
最後に、ステップ９０４で捕捉画像の位置が判定されると、ステップ９０５でペン先の位置を判定することができる。
【００９８】
図１０は、９０３および９０４についてより詳しく説明し、捕捉画像内のビットストリームを抽出する手法を示している。まず、ステップ１００１で、画像がカメラから受信される。次いで（ステップ１００２の破線の外枠によって示すように）ステップ１００２で、任意選択で画像を画像の前処理にかけることができる。ステップ１００３でパターンが抽出される。ここでは、様々な線上のピクセルを識別し、ピクセルを通過するパターンの向き（角度θに対応）を推定することができる。
【００９９】
次に、受信された画像は、ステップ１００４で分析されて、基礎を成すグリッド線が判定される。ステップ１００５でグリッド線が見つかると、ステップ１００６でパターンからコードが抽出される。次いでステップ１００７でコードがデコードされ、ステップ１００８でペン先の位置が判定される。ステップ１００５でグリッド線が見つからなかった場合、ステップ１００９でエラーが戻される。
【０１００】
強化されたデコーディングおよびエラー訂正アルゴリズムの概要 
図１２に示した本発明の実施形態では、捕捉画像（捕捉されたエリアに対応する）からの抽出ビット１２０１および宛先エリアが与えられている場合、ｍ配列のデコーディングおよびエラー訂正プロセスの変形は、Ｘ、Ｙの位置をデコードする。図１２は、この強化された手法のプロセス１２００のフロー図を示す。プロセス１２００は、２つの構成要素１２５１および１２５３を含む。
【０１０１】
・一度のデコード  構成要素１２５１は３つの部分を含む。
・ランダムビット選択（ｒａｎｄｏｍ  ｂｉｔ  ｓｅｌｅｃｔｉｏｎ）：抽出ビット１２０１のサブセットをランダムに選択する（ステップ１２０３）
・サブセットをデコードする（ステップ１２０５）
・位置の制約のもとでＸ、Ｙ位置を判定する（ステップ１２０９）
【０１０２】
・スマートビット選択（Ｓｍａｒｔ  Ｂｉｔ  Ｓｅｌｅｃｔｉｏｎ）によるデコーディング  構成要素１２５３は４つの部分を含む。
・スマートビット選択：抽出ビットの別のサブセットを選択する（ステップ１２１７）
・サブセットをデコードする（ステップ１２１９）
・ステップ１２１７およびステップ１２１９の反復回数（ループ回数）を調整する（ステップ１２２１）
・位置の制約のもとでＸ、Ｙ位置を判定する（ステップ１２２５）
本発明の実施形態は、慎重な戦略を使用してビットを選択し、ループ反復回数を調整し、位置の制約に従ってＸ、Ｙ位置（位置座標）を判定し、これがプロセス１２００に提供される。両方の構成要素１２５１および１２５３では、ステップ１２０５および１２１９（一度のデコード）は、式（４）を使用してｒを算出する。
【０１０３】
【数８】
2005235185.tif 000010
【０１０４】
をデコードされたビットと仮定する。すなわち
【０１０５】
【数９】
2005235185.tif 000011
【０１０６】
である。ｂと
【０１０７】
【数１０】
2005235185.tif 000012
【０１０８】
との間の差は、ｒに関連付けられているエラービットである。
【０１０９】
図１２は、本発明の実施形態による捕捉画像から抽出ビット１２０１をデコードするプロセス１２００のフロー図を示している。プロセス１２００は、構成要素１２５１および１２５３を含む。構成要素１２５１は、捕捉画像（捕捉された配列に対応する）に関連付けられている抽出ビット１２０１（Ｋビットを含む）を取得する。ステップ１２０３で、ｎビット（この場合ｎはｍ配列の次数）が抽出ビット１２０１からランダムに選択される。ステップ１２０５で、プロセス１２００は、デコードを一度行い、ｒを算出する。ステップ１２０７で、プロセス１２００は、ｂについてエラービットが検出されるかどうかを判定する。ステップ１２０７がエラービットは無いと判定した場合、ステップ１２０９で捕捉された配列の位置のＸ、Ｙの座標が判定される。ステップ１２１１で、Ｘ、Ｙの座標が位置の制約を満たしている、すなわち座標が宛先エリア内にある場合、プロセス１２００は、ステップ１２１３でＸ、Ｙの位置を（例えば別のプロセスやユーザインタフェースなどに）提供する。そうでない場合、ステップ１２１５は、失敗の表示を提供する。
【０１１０】
ステップ１２０７がｂにおいてエラービットを検出した場合、構成要素１２５３が実行されてエラービットを含めてデコードが行われる。ステップ１２１７は、抽出ビット１２０１から別のｎビットのセット（ステップ１２０３で選択されたｎビットとは少なくとも１ビットだけ異なる）を選択する。ステップ１２２１および１２２３は、抽出ビットのデコーディングに必要な反復回数（ループ回数）を判定する。ステップ１２２５は、ステップ１２１９で取得されたどの候補が位置の制約を満たすかをテストすることによって捕捉された配列の位置を判定する。ステップ１２１７〜１２２５についてより詳しく説明する。
【０１１１】
スマートビット選択 
ステップ１２０３は、（Ｋビットを有する）抽出ビット１２０１からｎビットをランダムに選択し、ｒ１について解く。式（５）を使用して、デコードされたビットを算出することができる。
【０１１２】
【数１１】
2005235185.tif 000013
【０１１３】
は
【０１１４】
【数１２】
2005235185.tif 000014
【０１１５】
のｋ番目のビットである場合、
【０１１６】
【数１３】
2005235185.tif 000015
【０１１７】
【数１４】
2005235185.tif 000016
【０１１８】
であり、Ｂ１＝｛ｂｋ｜ｋ∈Ｉ１｝および
【０１１９】
【数１５】
2005235185.tif 000017
【０１２０】
であると仮定する。すなわちＢ１はデコードされた結果が元のビットと同じビットであり、
【０１２１】
【数１６】
2005235185.tif 000018
【０１２２】
はデコードされた結果が元のビットとは異なるビットであり、Ｉ１および
【０１２３】
【数１７】
2005235185.tif 000019
【０１２４】
は、これらのビットの対応する指数である。任意のｎビットがＢ１から選択された場合、同じｒ１が取得されることを理解されたい。したがって、次のｎビットを注意深く選択しない場合、選択されたビットはＢ１のサブセットであり、したがって同じｒ１が取得される可能性がある。
【０１２５】
こうした状況を回避するために、ステップ１２１７は、次の手順に従って次のｎビットを選択する。
１．少なくとも１ビットを
【０１２６】
【数１８】
2005235185.tif 000020
【０１２７】
１３０３から選択し、残りのビットを、Ｂ１１３０１および
【０１２８】
【数１９】
2005235185.tif 000021
【０１２９】
１３０３からランダムに選択する。これは、図１３に示すように、ビット配列１３５１に対応する。次いでプロセス１２００は、ｒ２を解き、
【０１３０】
【数２０】
2005235185.tif 000022
【０１３１】
を算出することによってＢ２１３０５、１３０９、および
【０１３２】
【数２１】
2005235185.tif 000023
【０１３３】
１３０７、１３１１を見つける。
２．ステップ１を繰り返す。次のｎビットを選択するとき、
【０１３４】
【数２２】
2005235185.tif 000024
【０１３５】
（ｉ＝１，２，３・・・，ｘ−１、この場合ｘは現在のループ数）ごとに
【０１３６】
【数２３】
2005235185.tif 000025
【０１３７】
から選択された少なくとも１ビットがある。こうしたビットのサブセットを選択できない場合、またはループ回数に達した場合、反復が終了する。
【０１３８】
ループ回数の算出 
エラー訂正構成要素１２５３で、必要な反復回数（ループ回数）が各ループの後に調整される。ループ回数は、予想エラー率によって判定される。選択されたｎビットのすべてが正しいわけではない予想エラー率ｐｅは、
【０１３９】
【数２４】
2005235185.tif 000026
【０１４０】
となる。式中、ｌｔはループ回数を表し、定数によって初期設定され、Ｋは捕捉された配列から抽出されたビット数であり、ｎｅはプロセス１２００の反復中に招いたエラーの最小のエラービット数を表し、ｎはｍ配列の次数であり、
【０１４１】
【数２５】
2005235185.tif 000027
【０１４２】
はｎビットがＫビットから選択された組み合わせの数である。
【０１４３】
この実施形態では、ｐｅがｅ−５＝０．００６７未満であることを望む。（６）と組み合わせて
【０１４４】
【数２６】
2005235185.tif 000028
【０１４５】
が得られる。ループ回数の調整は、エラー訂正に必要なプロセス１２５３の反復回数を有意に低減し得る。
【０１４６】
位置の制約のもとでのＸ、Ｙ位置の判定 
ステップ１２０９および１２２５で、デコードされた位置は、宛先エリア内になければならない。宛先エリアは、アルゴリズムへの入力であり、異なるアプリケーションに応じて様々なサイズおよび場所のものでよく、または単にｍ配列全体であってもよい。これは通常、アプリケーションによって予想することができる。例えば、直前の位置が判定されている場合、筆記速度を考慮すると、現在のペン先の宛先エリアは、直前の位置の近くのはずである。しかし、ペンが持ち上げられた場合、その次の位置はどこでもよい。したがってこの場合、宛先エリアは、ｍ配列全体となるはずである。正しいＸ、Ｙ位置は、次のステップによって判定される。
【０１４７】
ステップ１２２４では、プロセス１２００は、その対応するエラービット数が
【０１４８】
【数２７】
2005235185.tif 000029
【０１４９】
より少ないｒｉを選択する。式中、ｌｔは実際のループ回数、ｌｒは次の式によって算出された位置の制約率を表す。
【０１５０】
【数２８】
2005235185.tif 000030
【０１５１】
式中、Ｌはｍ配列の長さである。
【０１５２】
ステップ１２２４は、エラービット数の昇順にｒｉをソートする。次いでステップ１２２５、１２１１、および１２１２は、対応するＸ、Ｙ位置が宛先エリア内にある最初のｒｉを見つける。ステップ１２２５、１２１１、および１２１２は、最後に結果として（ステップ１２１３を介して）Ｘ、Ｙ位置を戻す、または（ステップ１２１５を介して）デコーディング手順が失敗したという表示を戻す。
【０１５３】
ストロークのパスを判定する（ストロークの位置測定の）ためのアーキテクチャ 
図１５は、本発明の一実施形態による捕捉されたフレーム１５５１のシーケンスからペン先のパスを判定する方法を示している。ステップ１５０１で、テキストなどの文書内容が迷路パターンセルのみを含む他のエリアから分離されるようにフレームが処理される。また、画像（グレースケール）は、不均一の照度を補償するために標準化される。ステップ１５０３で、ｍ配列ビットが１フレーム（捕捉画像）内の可視の迷路パターンバーから抽出される。ステップ１５０５で、抽出ビットの数（ステップ１５０３で判定）が埋め込まれたｍ配列の次数より大きい場合、ｍ配列のデコーディングによって一意の位置座標（フレームの中心のｘ−ｙ位置に対応）を取得することができる。
【０１５４】
ステップ１５０７は、迷路パターンが文書１５５３の内容によって塞がれる文書１５５３のエリアを判定するためにデジタル文書１５５３を分析する（この実施形態では、デジタル文書１５５３はユーザによって生成された注釈は含まない）。迷路パターンセルが文書１５５３の内容によって塞がれる場合、ステップ１５０５は、フレームのｘ−ｙ位置を判定するのに十分なｍ配列ビットを抽出することができない場合がある。ウォーターマーク入りの文書１５５３全体を分析することによって、プロセス１５００は、ｘ−ｙ位置を一意に判定できない文書１５５３のエリアを確認することができる。この分析は、後述するステップ１５０９で使用され得る。
【０１５５】
ステップ１５１１で、ストロークに関連付けられている任意のフレームのｘ−ｙ位置をｍ配列のデコーディング（ステップ１５０５に対応）から判定できない場合、プロセス１５００は、フレームの位置を突き止めることができない。こうした場合、ステップ１５０９は、捕捉画像を、迷路パターン分析（ステップ１５０３）によって取得されたアフィン変換によってワープさせ、かなりの量の迷路パターンセルが文書の内容によって塞がれる文書画像１５５３のエリアと照合することができるグローバル位置測定（ｇｌｏｂａｌ  ｌｏｃａｌｉｚａｔｉｏｎ）を実行する。１つのフレームの照合が成功すると、ローカル位置測定（ｌｏｃａｌ  ｌｏｃａｌｉｚａｔｉｏｎ）（後述するステップ１５１７）を使用して、ストローク全体（一連のフレームに対応）の位置を突き止める。
【０１５６】
ステップ１５１７で、そのｘ−ｙ位置がステップ１５０５でデコードされない、またはステップ１５０９でグローバル位置測定によって判定されないフレームがさらに処理される。こうしたフレームの位置は、そのｘ−ｙ位置がｍ配列のデコーディングまたはグローバル位置測定によって判定されたフレームの位置に近いはずである。こうしたフレームの位置は、フレームをすでに判定されているｘ−ｙ位置の隣接するエリアと照合することによって判定される。捕捉画像と文書画像との間の（上述した）射影変換Ｆｓ→ｐも取得される。
【０１５７】
ｍ配列のデコーディング（ステップ１５０５に対応）およびグローバル／ローカル位置測定（それぞれステップ１５０９および１５１７）から取得されたｘ−ｙ位置は、捕捉画像の中心の位置（ｘ−ｙ位置）を表す（本発明の一実施形態は、１次元、２次元、または３次元をサポートすることができる。この実施形態では２次元がサポートされており、したがって位置はｘ−ｙ位置に対応する）。ペン先のｘ−ｙ位置を取得するために、ペン先（図２に示すペン先２０２など）と関連するカメラ（図２に示すカメラ２０３など）との間の関係は、較正を必要とし得る。ステップ１５１３は、後述するように較正をサポ―トする。
【０１５８】
ステップ１５１５で、ペン先のｘ−ｙ位置は、ローカル位置測定および較正パラメータから取得された射影変換を使用して画像の中心のｘ−ｙ位置をマッピングすることによって判定される（ペン先のパス１５５５を判定する一例を、後述するように図２６に示している）。
【０１５９】
図１６は、本発明の一実施形態による捕捉画像（フレーム）のシーケンスからペン先のパスを判定する装置１６００を示している。本発明の一実施形態では、画像セグメント化１６０１はステップ１５０１を実行し、迷路パターンアナライザ１６０３はステップ１５０３を実行し、ｍ配列デコーディングモジュール１６０５はステップ１５０５を実行し、照合モジュール１６０９はステップ１５１１、１５０９、および１５１７を実行し、ウォーターマーク入り文書アナライザ１６０７はステップ１５０７を実行し、較正モジュール１６１１はステップ１５１３を実行し、マッピングモジュール１６１３はステップ１５１５を実行する。
【０１６０】
文書画像分析および較正は、オンラインの画像捕捉および処理の前に、オフラインで、または別々に行うことができる。他の構成要素（例えば画像セグメント化モジュール１６０１、迷路パターンアナライザ１６０３、ｍ配列デコーディングモジュール１６０５、照合モジュール１６０９、およびマッピングモジュール１６１３など）は、オンラインまたはオフラインで行うことができる。構成要素の機能については以下で詳述する。
【０１６１】
画像のセグメント化 
捕捉画像は、テキストまたは図など、文書の内容を含んでいる可能性があり、これらは前処理時に内部で評価される。図１７は、本発明の一実施形態による捕捉画像１７００の一例を示している。図１８は、本発明の一実施形態による（テキスト文字１８０１および１８０３を含む）テキスト構成要素を含む捕捉画像の一例を示している。画像がテキスト／図面エリアを含んでいる場合、テキスト／図面エリアは、迷路パターンまたは空白のピクセルのみを含む他のエリアから分離される。
【０１６２】
さらに、捕捉画像（捕捉画像１７００および１８００など）は、不均一の照度を補償するために標準化される。図１９は、本発明の一実施形態による捕捉画像１７００（図１７に示す）の照度の標準化に対応する処理済み画像１９００を示している。図２０は、本発明の一実施形態による捕捉画像１８００の照度の標準化に対応する処理済み画像２０００を示している。
【０１６３】
迷路パターン分析 
迷路パターン分析のタスクは、捕捉画像内の可視の迷路パターンバー（図４Ａに示すバー４０１および４０２など）からｍ配列ビットを抽出することである。図１９は、本発明の一実施形態による捕捉画像１７００（図１７に示す）の迷路パターン分析１９００を示している。ビット１９０１（「０」のビット値１９０２に対応）およびビット１９０３（「１」のビット値１９０４に対応）は、ｍ配列ビットの２つのメンバーである。ｍ配列ビットは、迷路パターングリッド線、例えばグリッド１９０５および１９０７に従って迷路パターンで構成される。図２０は、本発明の一実施形態による捕捉画像１８００（図１８に示す）の迷路パターン分析２０００を示している（テキスト文字１８０１および１８０３の近くの迷路パターンセルの一部のｍ配列ビットは、この例では判定できないことに留意されたい）。
【０１６４】
図１９および図２０は、迷路パターンセルおよび迷路パターンバーの例を示している。まず、迷路パターングリッド線のパラメータ（各寸法に沿ったスケールおよび回転、すなわちアフィン変換）が算出され、次いで迷路パターンが埋め込まれている元の方向（または象限）が判定される。その結果、ｍ配列ビット情報がグリッド線およびバーの方向に基づいて判定される。
【０１６５】
ｍ配列デコーディング 
ステップ１５０５（図１５に示す）で取得された抽出されたビットの数が埋め込まれたｍ配列の次数より大きい場合、ｍ配列デコーディングによって一意のｘ−ｙ位置を取得することができる。
【０１６６】
ウォーターマーク入り文書画像分析 
迷路パターンは、文書の内容によって塞がれる可能性がある。これは、捕捉画像からデコーディングのために抽出できる十分なｍ配列ビットがない可能性があることを意味する。ウォーターマーク入り文書画像全体を分析することによって、プロセス１５００または装置１６００は、ｘ−ｙ位置を一意に判定できるエリア、およびｘ−ｙ位置を一意に判定できないエリアを判定することができる。分析結果は、グローバル位置測定で使用される。図２１は、本発明の一実施形態による文書画像１５５３の分析の結果２１００を示している。この実施形態では、文書画像（文書１５５３など）上のピクセルが４つのタイプのうちの１つとしてラベル付けされる。ピクセルは、次の関連に従ってラベル付けされる。
【０１６７】
タイプＩ：３２×３２ピクセルの周囲のウィンドウ（処理中のピクセルを中心として）は迷路パターンセルのみを含む
タイプＩＩ：３２×３２ピクセルの周囲のウィンドウは６０以上の迷路パターンセルを含む
タイプＩＩＩ：３２×３２ピクセルの周囲のウィンドウは３６から６０の迷路パターンセルを含む
タイプＩＶ：３２×３２ピクセルの周囲のウィンドウは３５以下の迷路パターンセルを含む
この実施形態では、捕捉画像のｘ−ｙ位置は、捕捉画像の中心がタイプＩまたはタイプＩＩのエリアに配置されている場合に判定することができ、また中心がタイプＩＩＩのエリアに配置されている場合に判定され得る。図２１では、エリア２１０１はタイプＩのピクセルエリアに対応し、エリア２１０３はタイプＩＩのピクセルエリアに対応し、エリア２１０７はタイプＩＩＩのピクセルエリアに対応し、エリア２１０５はタイプＩＶのピクセルエリアに対応する（文書全体が分析され、ラベル付けされるが、図２１には一部のみを示している）。
【０１６８】
この実施形態では、プロセス１５００は、電子文書をビットマップにレンダリングする、または用紙文書を走査して対応するビットマップを再度サンプリングして適切な解像度にすることによってデジタル文書１５５３を取得することができる。解像度の判定は、以下の考察に基づく。（１）捕捉画像の位置を判定するためにウォーターマーク入りグレースケール文書画像をカメラで捕捉された画像と照合するため、文書画像の解像度は、捕捉画像のものを下回ってはならない。（２）印刷された１つの迷路パターンセルは、照合アルゴリズムがより有効に働くことができるように、整数の文書画像ピクセルにマッピングされるべきである。例えば、カメラの解像度が０．１５ｍｍ／ピクセルであり、すなわち現実的な世界において０．１５ｍｍが１つのカメラピクセルにマッピングされ、印刷された迷路パターンセルのサイズが０．４５ｍｍ×０．４５ｍｍである、すなわち印刷された迷路パターンセルはカメラセンサー上の３×３ピクセルにマッピングされる場合、印刷された迷路パターンセルが文書画像の３×３ピクセルエリアにマッピングされるように文書画像の解像度も０．１５ｍｍ／ピクセルエリアに設定すべきである。
【０１６９】
高速画像照合によるグローバル位置測定 
ストロークの捕捉画像のｘ−ｙ位置がｍ配列デコーディングから判定されない場合、すべての画像の中心がｘ−ｙ位置を一意に判定できないエリアに配置されていることが予測できる。この場合、捕捉画像を、迷路パターン分析によって取得されたアフィン変換によってワープさせ、次いでｘ−ｙ位置を一意に判定できない文書画像のエリアと照合する。１つのフレームの照合が成功すると、ストローク全体の位置を突き止めるためにローカル位置測定アルゴリズムが使用される。
【０１７０】
文書１５５３（図１５で示す）では、３２×３２ピクセルのサブウィンドウでの可視の迷路パターンセルの数は一般に、１０から１００に及ぶ。文書内のピクセルは、ウォーターマーク入り文書分析（図１５に示すステップ１５０７）によって４つのタイプのうちの１つでラベル付けされる。検索領域がタイプＩＩＩおよびタイプＩＶのエリアの集まりとして設定される。
【０１７１】
図２２は、本発明の一実施形態によるストローク例２２０１のグローバル位置測定の結果を示している。ストローク２２０１上の点２２０３のｘ−ｙ位置は、グローバル位置測定（ステップ１５０９に対応）によって判定される。文書の一部分２２０２は、ストローク上の点２２０３をよりよく示すために、拡大部分２２０４まで拡大される（この実施形態では、グローバル位置測定によってストローク２２０１上の１つの点のみが判定され、残りの点はローカル位置測定によって判定される）。
【０１７２】
グローバル位置測定では、フレームは、検索領域の選択された点で文書画像と照合される。元のフレームは、迷路パターン分析（図１５に示すステップ１５０３に対応）からのスケールおよび回転（アフィン変換）によってワープされ（変換され）る。フレームの照合の際に選択された点を判定するのにオフセットが有用となり得る。
【０１７３】
この実施形態では、フレームの照合の成功は、捕捉画像と文書画像との間の最も大きい相互相関値に対応する（相互相関値は０から１の間にわたる）。最も大きい相互相関値は、他の相互相関値および閾値より十分大きいはずであり、すなわち、どの程度大きいかは、オフライントレーニングによって判定することができる。例えば、グローバル位置測定は、最高の相互相関値と２番目に高い相互相関値との間の差は、０．１より大きい必要がある。
【０１７４】
高速画像照合によるローカル位置測定 
ｘ−ｙ位置がｍ配列デコーディング／グローバル位置測定によってデコード／判定されないフレームでは、位置は、ｘ−ｙ位置が判定されるフレームの位置に近いはずである。その結果、対応する位置は、画像をすでに判定されているｘ−ｙ位置の隣接するエリアと照合することによって判定される。捕捉画像と文書画像との間の射影変換も取得される。
【０１７５】
図２３は、本発明の一実施形態によるストローク例２３０１のローカル位置測定の結果を示している。ストローク２３０１上の点（点２３０５ａや２３０５ｂなど）のサブセットの位置は、ｍ配列デコーディングによって判定され、残りの点の位置（点２３０３ａや２３０３ｂなど）はローカル位置測定によって判定される。
【０１７６】
この実施形態で、ローカル位置測定は、開始点、および中枢開始点（ｐｉｖｏｔａｌ  ｓｔａｒｔ  ｐｏｉｎｔ）を使用する。開始点は、ｍ配列デコーディング（図１５に示すステップ１５０５に対応）によって、またはグローバル位置測定（図１５に示すステップ１５０９に対応）によってうまく位置が突き止められたフレームの位置である。フレームシーケンスは、ローカル検索がセグメントごとに行われるセグメントにセグメント化される。１つのセグメントは、ローカル位置測定中にいくつかのセグメントに分割することができる。この実施形態では、ローカル検索は、速度および加速度のペン先の動作制限に基づく検索領域内に制限される。
【０１７７】
以下の手順は、ローカル位置測定についての一実施形態を示している。
・フレームシーケンスのセグメント化
（ａ）中枢開始点の選択
ストローク内の最初および最後の開始点が中枢開始点である。
２つの中枢開始点ｐ１とｐ２との間の開始点について、ｐ１およびｐ２を通過する線Ｌまでの最大距離Ｄｍａｘを有し、Ｄｍａｘが閾値（一般に０．５に設定）より大きいものが中枢開始点である。
（ｂ）中枢開始点での射影変換の精密化
カメラで捕捉された画像を文書画像と比較することによってより正確な射影変換を取得する。
（ｃ）中枢開始点によるフレームシーケンスのセグメント化
各セグメントは中枢開始点またはストロークの最初の点から開始し、中枢開始点またはストロークの最後の点で終了する。
・完成セグメント（ｆｉｎｉｓｈｅｄ  ｓｅｇｍｅｎｔ）の判定
セグメントは、次のときに完成セグメントと宣言される。
（ａ）このセグメント内に中枢開始点ではない少なくとも１つの開始点がある、すなわちこのセグメントでは、中枢開始点をそれ以上見つけることができない、言い換えればセグメントは直線に非常に近い。この場合、すべての点は内挿され、セグメントは完成したと宣言される。
または
（ｂ）セグメント内の点ごとに、対応するフレームが処理された。
・未完成のセグメントのフレームについての検索領域の検索
（ａ）セグメントの最初の点は開始点であり、処理する必要がない。
（ｂ）セグメントの第２の点では、検索領域の中心が最初の点となるように設定され、検索領域のサイズは、最大速度によって制限される。
（ｃ）セグメントの他の点では、処理された前の点での速度を推定することができる。検索領域の中心は、前の点の位置および速度から算出することができ、検索領域のサイズは、最大加速度によって制限される。
・検索領域におけるテンプレートの一致
このステップは、短時間にほんのわずかのペン姿勢の変化があるという想定に基づいている。これは、隣接するフレーム間の射影変換のほんのわずかの差があることを意味する。
（ａ）前に処理されたフレームの射影行列によってフレームをワープさせる。
（ｂ）検索領域の各点で、点を中心にフレームを文書画像に一致させることによって相互相関を判定する。
（ｃ）最大相互相関を有する点がこのフレームの正しい位置となるべきである。
・その点での射影変換の精密化
カメラで捕捉された画像を文書画像と比較することによって射影変換を精密化する。
・検索結果の除去
いくつかの要因によって、誤った最初の射影変換パラメータ、およびモーションブラー（ｍｏｔｉｏｎ  ｂｌｕｒ）など、エラー結果が得られる可能性がある。速度および加速度の動作制限によって、エラー結果を除去することができる。
（ａ）すべての開始点は除去すべきではない。
（ｂ）ストローク全体を最初の点から最後の点まで通過する。ある点が前の点による動作制限を満たすことができない場合、この点は誤っており、除去すべきである。
（ｃ）ストローク全体を最後の点から最初の点まで通過する。ある点が前の点による動作制限を満たすことができない場合、この点は誤っており、除去すべきである。
（ｄ）除去後、ストローク内に保持されている点は正しい点である。除去された点は、内挿から判定された点に置き換えられる。
【０１７８】
カメラ−ペン先の較正 
ｍ配列デコーディングおよびグローバル／ローカル位置測定から取得されたｘ−ｙ位置は、捕捉画像の中心の位置を表す。ペン先２０２のｘ−ｙ位置を取得するために、ペン先２０２とカメラ２０３の中心との間の関係を較正する必要がある。高速かつ正確な較正は、インクカートリッジをしばしば交換する可能性があるために重要である。
【０１７９】
固定された接点で筆記面上に異なる姿勢でペン先を接触させることによって、２、３の画像が捕捉される。正しい較正パラメータによってこれらの画像のすべてのｘ−ｙ位置を同じ点（固定された接点）にマッピングすべきであるという制約を使用することによって較正パラメータが判定される。
【０１８０】
この実施形態では、以下の手順を使用してペン先を較正する。この手順は、較正パラメータＬｖｉｒｔｕａｌ−ｐｅｎｔｉｐを推定するために使用される。
ａ）実ペン先を用紙上の固定位置Ｌｐｅｎｔｉｐに置く。
ｂ）位置Ｌｐｅｎｔｉｐでペン先を立てたまま、異なるペン姿勢での一連の画像を捕捉する。
ｃ）捕捉画像ごとに、変換Ｆｓ→ｐ（カメラで捕捉された画像での位置座標を用紙上の実画像での位置座標に変換する）、および
【０１８１】
【数２９】
2005235185.tif 000031
【０１８２】
（Ｆｓ→ｐの逆）が迷路パターン分析、ｍ配列デコーディング、および捕捉画像の文書画像への照合によって算出される。その場合、次のようになる。
【０１８３】
【数３０】
2005235185.tif 000032
【０１８４】
式中、Ｎは実験での捕捉画像の数、およびΔＰｉはｉ番目のフレームにおける実ペン先の位置とＬｐｅｎｔｉｐとの間のオフセットである。
ｄ）
【０１８５】
【数３１】
2005235185.tif 000033
【０１８６】
を（０，０）と初期設定する。式中、
【０１８７】
【数３２】
2005235185.tif 000034
【０１８８】
はＬｖｉｒｔｕａｌ−ｐｅｎｔｉｐの推定値である。
ｅ）（ｃ）の第１の式を使用して、Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐを
【０１８９】
【数３３】
2005235185.tif 000035
【０１９０】
と設定して
【０１９１】
【数３４】
2005235185.tif 000036
【０１９２】
ｉ＝１、２、・・・、Ｎを取得する。
【０１９３】
【数３５】
2005235185.tif 000037
【０１９４】
を平均することによって、Ｌｐｅｎｔｉｐは次のように推定される。
【０１９５】
【数３６】
2005235185.tif 000038
【０１９６】
ｆ）（ｃ）の第２の式を使用して、Ｌｐｅｎｔｉｐを
【０１９７】
【数３７】
2005235185.tif 000039
【０１９８】
と設定して
【０１９９】
【数３８】
2005235185.tif 000040
【０２００】
ｉ＝１、２、・・・、Ｎを取得する。
【０２０１】
【数３９】
2005235185.tif 000041
【０２０２】
を平均することによって、Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐは次のように推定される。
【０２０３】
【数４０】
2005235185.tif 000042
【０２０４】
ｇ）ステップｅを繰り返す。何度かの反復の後、Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐおよびＬｐｅｎｔｉｐは、それぞれ実質的により正確な結果に集束する。これを
【０２０５】
【数４１】
2005235185.tif 000043
【０２０６】
および
【０２０７】
【数４２】
2005235185.tif 000044
【０２０８】
と呼ぶ。
最後に、
【０２０９】
【数４３】
2005235185.tif 000045
【０２１０】
を較正パラメータＬｖｉｒｔｕａｌ−ｐｅｎｔｉｐとして取得する。
【０２１１】
画像の中心位置のペン先へのマッピング 
ペン先２０２のｘ−ｙ位置は、ローカル位置測定および較正パラメータから取得された射影変換を使用して画像の中心のｘ−ｙ位置をマッピングすることによって判定される。図２４および図２５は、一例のペン先較正の結果を示す。図２４は、本発明の一実施形態によるペン先２０２の復元されたストローク２４０１を示す。図２５は、図２４に示す復元されたストロークに関連付けられている実際のストローク２５０１を示す。図２４のストローク２４０３は、捕捉画像の中心の位置のパスを示す。つまり、較正を行わない場合、ストローク２５０１は誤って復元（ストローク２４０３として復元）される可能性があり、適切な較正を行うと、ストローク２５０１は正しく復元（ストローク２４０１として復元）される。
【０２１２】
当業者には理解できるように、コンピュータシステムを制御する命令を含む関連のコンピュータ可読媒体を備えるコンピュータシステムを使用して、本明細書に開示した実施形態の例を実施することができる。コンピュータシステムは、マイクロプロセッサ、デジタル信号プロセッサ、および関連の周辺電子回路など、少なくとも１つのコンピュータを含み得る。
【０２１３】
本発明は添付の特許請求の範囲を使用して定義されているが、本発明は、本明細書に記載した要素およびステップを任意の結合、または副結合で含むためのものであるという点で、こうした特許請求の範囲は例示的なものである。したがって、説明、特許請求の範囲、および図面を含む明細書からの１つまたは複数の要素を様々な結合または副結合に組み込む、本発明を定義する任意の数の代替の結合がある。本明細書を鑑み、本発明の態様の代替の結合を単独で、または本明細書に定義した１つまたは複数の要素またはステップとの組み合わせで、本発明の変更または代替として、または本発明の一部として使用できることは当業者であれば明らかである。本明細書に含まれる本発明の記載した説明は、こうしたすべての変更および代替をカバーするものとする。
【図面の簡単な説明】
【０２１４】
【図１】本発明の実施形態とともに使用できるコンピュータの一般的な説明を示す図である。
【図２Ａ】本発明の実施形態による画像捕捉システムおよび対応する捕捉画像を示す図である。
【図２Ｂ】本発明の実施形態による画像捕捉システムおよび対応する捕捉画像を示す図である。
【図３Ａ】本発明の実施形態による様々なシーケンスおよび折りたたみ技術を示す図である。
【図３Ｂ】本発明の実施形態による様々なシーケンスおよび折りたたみ技術を示す図である。
【図３Ｃ】本発明の実施形態による様々なシーケンスおよび折りたたみ技術を示す図である。
【図３Ｄ】本発明の実施形態による様々なシーケンスおよび折りたたみ技術を示す図である。
【図３Ｅ】本発明の実施形態による様々なシーケンスおよび折りたたみ技術を示す図である。
【図３Ｆ】本発明の実施形態による様々なシーケンスおよび折りたたみ技術を示す図である。
【図４Ａ】本発明の実施形態による様々なエンコーディングシステムを示す図である。
【図４Ｂ】本発明の実施形態による様々なエンコーディングシステムを示す図である。
【図４Ｃ】本発明の実施形態による様々なエンコーディングシステムを示す図である。
【図４Ｄ】本発明の実施形態による様々なエンコーディングシステムを示す図である。
【図４Ｅ】本発明の実施形態による様々なエンコーディングシステムを示す図である。
【図５Ａ】図４Ａおよび４Ｂによるエンコーディングシステムに関連付けられている結果として得られた４つの可能なコーナーを示す図である。
【図５Ｂ】図４Ａおよび４Ｂによるエンコーディングシステムに関連付けられている結果として得られた４つの可能なコーナーを示す図である。
【図５Ｃ】図４Ａおよび４Ｂによるエンコーディングシステムに関連付けられている結果として得られた４つの可能なコーナーを示す図である。
【図５Ｄ】図４Ａおよび４Ｂによるエンコーディングシステムに関連付けられている結果として得られた４つの可能なコーナーを示す図である。
【図６】本発明の実施形態による捕捉画像部分の回転を示す図である。
【図７】図４Ａから図４Ｅのコーディングシステムとともに使用される様々な角度の回転を示す図である。
【図８】本発明の実施形態による捕捉された配列の位置を判定するプロセスを示す図である。
【図９】本発明の実施形態による捕捉画像の位置を判定する方法を示す図である。
【図１０】本発明の実施形態による捕捉画像の位置を判定する別の方法を示す図である。
【図１１】従来技術による文書におけるエンコーディングスペースの表現を示す図である。
【図１２】本発明の実施形態による捕捉画像から抽出されたビットのデコーディングを示すフロー図である。
【図１３】本発明の実施形態による捕捉画像から抽出されたビットのビット選択を示す図である。
【図１４】本発明の実施形態による捕捉画像から抽出されたビットをデコードする装置を示す図である。
【図１５】本発明の一実施形態による捕捉されたフレームのシーケンスからペン先のパスを判定する方法を示す図である。
【図１６】本発明の一実施形態による捕捉されたフレームのシーケンスからペン先のパスを判定する装置を示す図である。
【図１７】本発明の一実施形態による捕捉画像の一例を示す図である。
【図１８】本発明の一実施形態によるテキスト構成要素を含む捕捉画像の一例を示す図である。
【図１９】本発明の一実施形態による捕捉画像の迷路パターン分析を示す図である。
【図２０】本発明の一実施形態によるテキスト構成要素を含む捕捉画像の迷路パターン分析を示す図である。
【図２１】本発明の一実施形態による文書画像の分析の結果を示す図である。
【図２２】本発明の一実施形態によるストローク例のグローバル位置測定の結果を示す図である。
【図２３】本発明の一実施形態によるストローク例のローカル位置測定の結果を示す図である。
【図２４】本発明の一実施形態によるペン先の復元されたストロークおよび捕捉画像の対応する中心のパスを示す図である。
【図２５】図２４に示す復元されたストロークに対応する実際のストロークを示す図である。
【符号の説明】
【０２１５】
２０１  ペン
２０２  先端
２０３  カメラ
２０４  画像
２０６  追加のセンサーおよび／またはプロセッサ
２０７  面
２０８  レンズ        
２０９  画像平面
２１０  画像
２１１  画像センサー
２１２  仮想ペン先
１４００  デコードする装置
１４０１  ビット選択モジュール
１４０３  デコーディングモジュール
１４０５  位置判定モジュール
１４０７  入力インタフェース
１４０９  出力インタフェース
１６００  ペン先のパスを判定する装置
１６０１  画像セグメント化
１６０３  迷路パターンアナライザ
１６０５  ｍ配列デコーディングモジュール
１６０９  照合モジュール
１６０７  ウォーターマーク入り文書アナライザ
１６１１  較正モジュール
１６１３  マッピングモジュール
【図１】
2005235185.tif 000046
【図２Ａ】
2005235185.tif 000047
【図２Ｂ】
2005235185.tif 000048
【図３Ａ】
2005235185.tif 000049
【図３Ｂ】
2005235185.tif 000050
【図３Ｃ】
2005235185.tif 000051
【図３Ｄ】
2005235185.tif 000052
【図３Ｅ】
2005235185.tif 000053
【図３Ｆ】
2005235185.tif 000054
【図４Ａ】
2005235185.tif 000055
【図４Ｂ】
2005235185.tif 000056
【図４Ｃ】
2005235185.tif 000057
【図４Ｄ】
2005235185.tif 000058
【図４Ｅ】
2005235185.tif 000059
【図５Ａ】
2005235185.tif 000060
【図５Ｂ】
2005235185.tif 000061
【図５Ｃ】
2005235185.tif 000062
【図５Ｄ】
2005235185.tif 000063
【図６】
2005235185.tif 000064
【図７】
2005235185.tif 000065
【図８】
2005235185.tif 000066
【図９】
2005235185.tif 000067
【図１０】
2005235185.tif 000068
【図１１】
2005235185.tif 000069
【図１２】
2005235185.tif 000070
【図１３】
2005235185.tif 000071
【図１４】
2005235185.tif 000072
【図１５】
2005235185.tif 000073
【図１６】
2005235185.tif 000074
【図１７】
2005235185.tif 000075
【図１８】
2005235185.tif 000076
【図１９】
2005235185.tif 000077
【図２０】
2005235185.tif 000078
【図２１】
2005235185.tif 000079
【図２２】
2005235185.tif 000080
【図２３】
2005235185.tif 000081
【図２４】
2005235185.tif 000082
【図２５】
2005235185.tif 000083
【外国語明細書】
2005235185000001.pdf