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