誤り訂正を用いる位置特定
１枚の紙又は他の表面に適用することができる符号、及びそのような符号を復号化する技法が提供される。そのような符号及び復号化技法を用いることによって、表面の小さなフィールドだけを観測することによって、紙又は他の表面上のペン（たとえば、デジタルペン）の位置を特定することができるようになる。さらに、任意の回転及び特定の誤り（たとえば、紙の上のほこり又は正規の場所から外れたマーキングに起因する）が存在する場合でも、その位置を多くの場合に特定することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ごくわずかな視野内で位置特定情報を知ることに基づいて、位置特定情報で符号化されている１枚の紙又は他の基板上での位置を特定することに関する。本発明は、たとえば、デジタルペンとの関連での位置特定に適用することができる。
【背景技術】
【０００２】
一般的にデジタルペンは、普通のペンと同じようにしてインクで紙に書くことができるのに加えて、そのようなペンによって形成された任意のマークをデジタル化し、その後、転写するか、又は内部に格納することができるペンである。そのようなデジタルペンの多くが、紙の上に予め印刷されているパターンを検出するために小型カメラを利用する。パターンが適切に予め印刷されている紙と、適切な復号化ソフトウエアとを用いることによって、そのようなデジタルペンは、その上にマークが形成される個々の紙片を一意に、又は特定のセットの構成要素として概ね特定することができ、各マークが形成される紙の上の場所を区別することができる。結果として、デジタルペンは、コンピュータ入力デバイスとして用いることができる。デジタルペンの一例は、ヒューレット・パッカード社のデジタルペンであり、このペンは、ペンストロークを内部に格納し、その後、クレードルに挿入されると、デジタル化されたマークをコンピュータにダウンロードする。
【０００３】
紙に位置特定情報をマークする１つの方法が、特許文献１において記載されており、当該特許は、本明細書においてその全体が述べられるかのように、参照により本明細書に援用される。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】米国特許第６，５４８，７６８号
【発明の概要】
【０００５】
一態様によれば、本発明は、任意の回転、オフセット及び特定の誤り（たとえば、紙の上のほこり、又は正規の場所から外れたマーキングに起因する）が存在する場合であっても、位置を特定することができるようにする特定の符号を提供することによって、既存の符号化技法を改善する。
【０００６】
上記の概要は単に、本発明の全般的な性質の簡潔な説明を与えることを意図している。添付の図面との関連において、特許請求の範囲及び好ましい実施形態の以下の詳細な説明を参照することによって、本発明をより十分に理解することができる。
【図面の簡単な説明】
【０００７】
【図１】本発明の典型的な実施形態による、符号化された紙を生成するためのシステムのブロック図である。
【図２】本発明の典型的な実施形態による、符号化された紙を使用するためのシステムのブロック図である。
【図３】本発明の典型的な実施形態による、複数の領域に分割されている１枚の紙を示す図である。
【図４】本発明の典型的な実施形態による、１つのページ上の単一の領域のための符号化パターンを示す図である。
【図５】本発明の典型的な実施形態による、符号化されたページ上の任意の位置及び向きにおける検出デバイスの視野を示す図である。
【図６】本発明の典型的な実施形態による、正しい向きに回転した後の視野を示す図である。
【図７】本発明の典型的な実施形態による、当該視野ブロックが重なっている４つの領域に関連する視野ブロックを示す図である。
【図８】本発明の典型的な実施形態による、当該視野ブロックが重なっている４つの領域に関連し、当該視野ブロック内に符号化シンボルが表示されている視野ブロックを示す図である。
【図９】本発明の典型的な実施形態による、それぞれの符号化パターンが示されており、視野ブロックによって覆われる、４つの重なった領域を示す図である。
【図１０Ａ】本発明の典型的な実施形態による、符号化シンボルが当該位置からコピーされる経過を示すために種々の位置が強調表示されている視野ブロックを示す図である。
【図１０Ｂ】本発明の典型的な実施形態による、符号化シンボルが当該位置からコピーされる経過を示すために種々の位置が強調表示されている視野ブロックを示す図である。
【図１０Ｃ】本発明の典型的な実施形態による、符号化シンボルが当該位置からコピーされる経過を示すために種々の位置が強調表示されている視野ブロックを示す図である。
【図１０Ｄ】本発明の典型的な実施形態による、符号化シンボルが当該位置からコピーされる経過を示すために種々の位置が強調表示されている視野ブロックを示す図である。
【図１１Ａ】本発明の典型的な実施形態による、再構成される領域を示しており、そのような領域内に位置がコピーされる経過を強調表示する図である。
【図１１Ｂ】本発明の典型的な実施形態による、再構成される領域を示しており、そのような領域内に位置がコピーされる経過を強調表示する図である。
【図１１Ｃ】本発明の典型的な実施形態による、再構成される領域を示しており、そのような領域内に位置がコピーされる経過を強調表示する図である。
【図１１Ｄ】本発明の典型的な実施形態による、再構成される領域を示しており、そのような領域内に位置がコピーされる経過を強調表示する図である。
【図１２】本発明の典型的な実施形態による、位置特定復号化処理のための流れ図である。
【図１３】本発明の典型的な実施形態による、正しい向きにあり、オフセットがない視野ブロックの場合のレジストレーション符号化シンボル及び非レジストレーション符号化シンボルのマップを示す図である。
【発明を実施するための形態】
【０００８】
本発明は、２次元位置特定符号化パターンを設計するという実用的な問題を対処する。そのような符号化パターンは、大きな印刷表面及び検出デバイスから構成されるナビゲーションシステムとの関連で用いられることがある。位置特定符号化パターンは、その表面上に印刷される特殊なパターンを定義する。その検出デバイスは、表面上の複数の小さな領域の適度に良好な画像を与える。検出デバイスによって捕捉される限られた領域は、本明細書において視野（ＦＯＶ）と呼ばれる。ＦＯＶパターン内で捕捉される情報を用いて、大きな表面上の絶対位置が求められる。
【０００９】
本発明は特に、デジタルペン及び紙に関する最近開発されたシステムに適用することができる。この環境において、紙の上に特殊なパターンが予め印刷される。そのペンは、書くと同時に、その紙を繰返し撮影する小型カメラを備える。これらの写真から解像される位置データによって、そのシステムは、その文書を表すデジタル画像を生成することができるようになる。
【００１０】
位置特定符号化は新しくはないが、本発明の手法は特定の利点をもたらす。本発明の典型的な実施形態では、紙に対するカメラ軸の向きは任意にすることができる。換言すると、そのような実施形態における位置特定は、ＦＯＶ向きが回転しても変化しない。さらに、特定の実施形態は、画像処理モジュールによって、いくつかの位置特定符号化シンボルが誤って検出される場合であっても、その位置を正しく特定することができる。そのような検出の誤りは、たとえば、プリントエラー、又は文書が擦り切れていること、ほこり、又はカメラアングルが難しいことに起因して生じることがある。
【００１１】
以下に説明される例示的な実施形態において、本発明人らは、９個の符号化シンボルの記号体系において定義される位置特定符号化技法を提示する。この技法は、５×５×２45個の位置から成る表面に対応し、５×５位置ＦＯＶを用いて位置を特定することができるようにする。この実施形態では、回転していても、且ついくつかの誤りが存在する場合でも、正しく位置を特定することができる。
【００１２】
好ましい実施形態は、表面を、ＦＯＶと同じ寸法を有する重なり合わない複数の領域に分割することに基づく。各領域は、位置情報を与える３つの異なる番号を割り当てられる。３つの番号は、ページ番号、行番号及び列番号を表す。これらの番号は、物理的な座標に対応する必要はないが、好ましい実施形態では、１つの行（列）内の任意の２つの隣接する領域は、同じページ番号、同じ行（列）番号、及び連続する列（行）番号を有する。しかしながら、以下に記述される技法は、さらに一般的な状況下で機能し、たとえば、１つの行（列）内の任意の２つの隣接する領域が、同じページ番号と、同じ行（列）番号と、他の領域の列（行）番号に基づいて求めることができる列（行）番号とを有する場合にも機能するであろう。
【００１３】
以下に記述される実施形態では、ページ番号、行番号及び列番号は、符号化記号体系を用いて、各領域内の所定の場所に明示的に書き込まれる。また、記述される実施形態では、各領域内の他の場所は、位置情報に対応するパリティ（又は他の誤り訂正）情報を保持する。以下にさらに詳細に検討されるように、これらのパリティ（又は他の誤り訂正符号化シンボル又は情報）によって、特定の符号化−シンボル−特定の誤りを訂正することができるようになる。
【００１４】
各領域内の残りの場所はレジストレーションパターンとしての役割を果たし、異なる領域間の境界をマークすることに加えて、パターンの向きを決定する。カメラのＦＯＶは多くの場合に、種々の領域の部分を覆うため、レジストレーションパターンは、ＦＯＶ内の種々の領域に、いずれの符号化シンボルが属するかを指示する。位置情報は、ページ、行及び列のための明示的な番号によって与えられるため、種々の領域に対応するＦＯＶ符号化シンボルから位置を復号化するのは、非常に単純である。好ましい実施形態では、そのレジストレーションパターンによって、レジストレーション符号化シンボルのうちの１つが損なわれている場合であっても、所与の回転を受けている可能性があるＦＯＶ内でレジストレーションパターンを特定することができるようになる。これは、レジストレーション符号化シンボルのための１符号化シンボル誤り訂正能力も提供する。
【００１５】
上述されたように、本発明には特に、デジタルペン及び特別に符号化された紙との関連で適用することができる。そのような紙１０を生成するためのシステム５が図１に示される。最初に、モジュール１２において、符号化パターンが生成される。このパターンは、たとえば、各領域が位置符号化シンボル、又は、特定のページ（たとえば、ページ番号）を含む、その位置を特定するのに十分な他の情報を含むように、１枚の紙全体にわたって個々の領域の場所を一意に特定する。それらの領域は連続しており、重なり合うことなく、ページ全体を覆うことが好ましい。本発明によるパターンに関するさらなる詳細は、以下に述べられる。
【００１６】
その後、紙を他の目的のために使用することを過度に妨げることのないように、すなわち、その紙を任意の他の紙と同じようにして使用することができるように、変換モジュール１３が、位置符号化シンボルの指定されたパターンを、紙の上に印刷することができるマークのパターンに変換する。一例が‘７６８特許に記載されているパターン形成であり、当該特許では、個々の符号化シンボルは、仮想ラスタに基づいて、基準名目位置からの異なる距離によって表される。仮想ラスタが十分に小さなピッチを有する場合には、そのようなパターンを形成しても、結果として、概ね均一な灰色の背景になる。
【００１７】
モジュール１３によって出力されるパターン形成データに、付加データ１５を追加して、プリンタドライバ１７において合成することができる。たとえば、そのような付加データは、或る書式を印刷するためのベクトル又はラスタデータを含むことがある。その後、プリンタドライバ１７は、合成されたデータをプリンタ１９に与え、プリンタ１９は、背景パターン形成データと共に、任意のそのような付加データ１５を印刷し、それによって、符号化された紙１０が与えられる。付加データ１５は省略されることがあり、たとえば、符号化された紙１０が白紙のメモ用紙として用いられることになる場合には省略してもよいことに留意されたい。
【００１８】
図２は、符号化されたデータ１０を用いるシステム３４を示す。この例では、紙１０に書くためにデジタルペン３５が用いられており、ペン３５のユーザによって行なわれるマーキングを記録することも意図している。しかしながら、代替的な例では、その代わりに、紙１０から画像データを捕捉する能力を有する任意の他のタイプのデバイスが用いられる。たとえば、発表者が１枚の紙の上で指している場所についての情報を捕捉することが望ましい場合があり、その場合には、画像捕捉デバイスは筆記能力を有する必要はない。
【００１９】
この実施形態では、デジタルペン３５によって捕捉される画像データは、受信機３７を介して、リアルタイムに無線で（たとえば、ブルートゥース又は８０２．１１プロトコルを用いて）転送される。他の実施形態では、その画像データは、有線接続を介してリアルタイムに転送され、さらに別の実施形態では、画像データはペン３５に格納され、たとえば、ペン３５をクレードルに挿し込むことによって、後に転送される。
【００２０】
いずれにしても、モジュール３８において、（典型的には、あらゆる必要な回転後の）画像データが位置符号化シンボルに戻され、位置符号化シンボルは、モジュール４０において、紙１０の上のペン３５の位置を特定するために用いられる。その後、そのような情報は、格納された書込み情報と共に、適切なアプリケーション４２に与えられる。たとえば、紙１０が予め印刷された書式を含み、ユーザが、その書式上のボックスをチェックした場合には、検出された位置情報に基づいて、アプリケーション４２は、いずれのボックスがチェックされたかを判断し、その行為に基づいて、任意の関連付けられる処理を実行することができる。
【００２１】
こうして、符号化された紙１０をデジタルペン３５（又は他の画像形成デバイス）と共に用いることによって、ユーザは、単に紙片の上をマークするだけで、自動化されたタスクの実行をトリガすることができるようになる。残念なことに、従来の符号化された紙及び復号化技法は、本発明によれば許される程度の小さな視野を用いるときに特に、紙１０の上のほこり又は他の正規の場所から外れたマーキングによって引き起こされることがあるような、誤りに対する十分な耐性を有していない。
【００２２】
図３は、複数の領域（たとえば、領域６１〜６４）に分割されている１枚の紙１０を示す。本発明のこの実施形態では、各領域は正方形であり、それらの領域は１つの配列内に配置され、互いに接触しており、重なり合うことなく、紙１０全体を覆う。また、この実施形態では、各領域は、符号化シンボルの配列を（たとえば、領域６４の場合に示される位置７１〜７３において）含み、ここでは、５×５符号化シンボルの配列、すなわち全部で２５個の符号化シンボルを含む。以下にさらに詳細に説明されるように、各領域内の符号化シンボルは、その領域のためのページ番号、行番号及び列番号を特定する。こうして、この例では、或る領域のための行番号は、その真上に或る領域のための行番号よりも１だけ大きく、或る領域のための列番号は、その左隣に或る領域よりも１だけ大きい。
【００２３】
以下の説明は、印刷されたパターン表現ではなく、印刷されたパターンの符号表現に主に焦点を当てていることに留意されたい。すなわち、印刷されたマークから、位置符号化シンボル及びレジストレーション符号化シンボル（以下に説明される）への変換は概ね既に完了していると見なされる。これは、本発明が、位置及びレジストレーション符号化シンボルを表すために用いられる、具体的に印刷されたマークとは概ね無関係であるためである。この例では、対応する印刷されたシンボルパターンが構成される方法に起因して、そのパターン内の各位置は、９個の異なる値｛０，１，．．．，８｝のうちのいずれか１つをとることができるものと仮定される。
【００２４】
これに関連して、図４は、本発明の代表的な実施形態による、単一の領域８０のための符号化パターン（たとえば、モジュール１２によって生成されるパターン）を示す。この実施形態では、ページ１０の上の各領域は同じように符号化されるが、位置情報はその領域に特有である。その符号化パターンに含まれるのは、多数のレジストレーション符号化シンボル（たとえば、符号化シンボル８１）、ページ位置符号化シンボル（たとえば、符号化シンボル８２）、行位置符号化シンボル（たとえば、符号化シンボル８３）及び列位置符号化シンボル（たとえば、符号化シンボル８４）であり、図４において、それらの符号化シンボルはそれぞれ文字Ｒ、Ｎ、Ｙ及びＸによって示される。
【００２５】
レジストレーションパターン（Ｒ個の符号化シンボルから成る）は領域境界をマークし、各領域内の４つの内部固定位置を占有する。本発明人らは、レジストレーションの場所の値を予約する。この値は、これらの４つの内部固定場所内に書き込まれることになり、その領域内の他のいずれの場所にも書き込まれない。残りの８個の値は、位置情報そのものを符号化するために用いられる。便宜上、本発明人らは、数字８によってレジストレーション符号化シンボルを示し、８進数｛０，１，．．．，７｝によって情報符号化シンボルを示す。
【００２６】
レジストレーション符号化シンボル値８に関連付けられる印刷されたシンボルは、回転しても変化しないことが好ましい。たとえば、符号化シンボル値が（‘７６８特許の場合のように）異なるドット変位に関連付けられる場合には、レジストレーション符号化シンボル値は、中心変位に関連付けられることが好ましい。
【００２７】
あらゆる領域内の１５個の内部の場所は、その紙の上の領域の絶対位置を符号化するために用いられる。これらの場所では、８個の値｛０，１，．．．，７｝が許され、符号化シンボル当たり３ビットを与える。したがって、位置情報のために、あらゆる領域において、４５ビットが利用可能である。この実施形態において、本発明人らは、この情報を、それぞれが５要素ベクトル、すなわち全部で１５ビットを占有する、３つの番号に分ける。この実施形態では、３つの番号は、ページ番号、行番号及び列番号に対応する。より具体的には、この実施形態において、行番号及び列番号がそれぞれ占有するのは、多くても１５ビットである。最大数が、それよりも少ないビットしか占有しない場合には、行（列）番号は、対応するベクトルの最下位ビットに書き込まれ、そのベクトルの残りのビットがページ番号の一部を保持する。
【００２８】
あらゆる領域内の残りの６個の場所（６＝２５−４−３×５）は、位置情報内の誤りに対する保護を与えるパリティ値（又は他の誤り訂正符号化シンボル）を保持することが好ましい。２つのそのような誤り訂正符号化シンボルが、各５符号化シンボルベクトルに関連付けられ、リード・ソロモン誤り訂正符号の７符号化シンボルコードワードが生成される。本発明人らは、以下に、これに関して詳細に論じる。
【００２９】
図４のインデックスは、各コードワード内の符号化シンボルの順序を定義しており、ここで、０は最下位の位置情報符号化シンボルであり、４は最上位の位置情報符号化シンボルであり、５及び６はパリティ（又は他の誤り訂正）符号化シンボルのインデックスである。行番号は、１５ビットのＹデータ値の最下位ビット（Ｙ０〜Ｙ４）を占有し、列番号は、１５ビットのＸデータ値の最下位ビット（Ｘ０〜Ｘ４）を占有する。ページ番号は、１５ビットのＮデータ値（Ｎ０〜Ｎ４）を占有し、任意選択で、１５ビットのＹデータ値（Ｙ０〜Ｙ４）及び１５ビットのＸデータ値（Ｘ０〜Ｘ４）の最上位ビットも占有する。Ｎ５及びＮ６は、Ｎ０〜Ｎ４のための誤り訂正符号化シンボルであり、Ｙ５及びＹ６はＹ０〜Ｙ４のための誤り訂正符号化シンボルであり、Ｘ５及びＸ６はＸ０〜Ｘ４のための誤り訂正符号化シンボルである。Ｎ０〜Ｎ４はページ番号情報の少なくとも一部を含むことが好ましいが、以下にさらに詳細に説明されるように、本発明の特定の実施形態では、Ｘ０〜Ｘ４及びＹ０〜Ｙ４も、行番号に関する情報を含むことに加えて、ページ番号に関する情報も含むことに留意されたい。
【００３０】
この例では、印刷されたパターンのグリッド単位（これは、単一の符号化シンボルによって占有される空間のサイズにも対応する）は０．４２３３３ｍｍであるため、その領域の幅及び長さはそれぞれ、２．１１７ｍｍである。Ａ４ページサイズは、２９６ｍｍ×２１０ｍｍであり、それゆえ、１４０×１００の重なり合わない領域を含む。行番号を符号化するために８ビットが必要とされ、列番号の場合には７ビットが必要とされる。それゆえ、ページ番号のために３０ビットが残されるため、提案されている符号は、２30個までの異なるページを一意に特定することができる。
【００３１】
好ましい実施形態では、水平方向において隣接する２つの領域内の５符号化シンボル（１５ビット）Ｘベクトル（Ｘ０〜Ｘ４）は連続する番号を表し、垂直方向において隣接する２つの領域内の５符号化シンボル（１５ビット）Ｙベクトル（Ｙ０〜Ｙ４）は連続する番号を表す。さらに、垂直方向において隣接する２つの領域内の７シンボルＸベクトル（Ｘ０〜Ｘ６）は同一であり、水平方向において隣接する２つの領域内の７シンボルＹベクトル（Ｙ０〜Ｙ６）は同一である。
【００３２】
図３及び図４を比較すると、図４に示されるパターンはページ１０全体にわたって連続して繰り返されており、適切な行番号及び列番号が各領域内に符号化されており、ページ番号はページ１０上の各領域内で同一であることは理解されよう。十分に大きなＦＯＶを考えると、ページ１０上の位置を特定することはささいなことであろう。しかしながら、物理的な制約に起因して、一般的には、ＦＯＶはできる限り小さいことが好ましい。間もなく明らかになるように、単一の５×５視野ブロックを観測することさえできれば、本発明の技法は、回転又はオフセットがあっても位置を復号化することができる。
【００３３】
そのような小さなＦＯＶの限られる物の見え方から、符号化されたページ１０は最初に、領域間に明らかな境界がない符号化シンボル値の配列であるように見える。さらに、その配列の向きは、その時々で異なることがある。その状況が図５に示されており、図５は、符号化されたページ１０上の任意の位置におけるＦＯＶ１００を示す。この実施形態では、デジタルペン３５が使用されており、位置１０２はペン３５の先端を表し、ＦＯＶ１００は位置１０２と既知の関係にある。
【００３４】
上述されたように、ＦＯＶ１００は、５×５ＦＯＶブロック１０４全体を包含するほど十分に大きい。図５に示されるように、これは、種々のオフセットに対応するために、一般的にＦＯＶ１００をわずかに大きくすべきであることを意味する。
【００３５】
この時点で、この実施形態の列及び行に対応する線を有する仮想ラスタに基づいて、ＦＯＶ１００内の画像情報を潜在的に正しい向きに回転させることができる。しかしながら、この実施形態では、仮想ラスタ線だけでは、４つの潜在的な向きしか特定することができない。任意に１つが選択され、その後、ＦＯＶブロック１０４が、その中のレジストレーション符号化シンボルと共に、簡単に特定される。
【００３６】
そのようなレジストレーション符号化シンボルは、ページ１０の上の周辺領域に対して、ＦＯＶブロック１０４の正しい向き及びオフセットを一意に特定することができる。実際には、図４の４つのレジストレーション符号化シンボル（「Ｒ」で示される）のうちの任意の３つ（さらに言うと、任意の他の３つの同一直線上にないレジストレーション符号化シンボル）であれば、そのような向き及びオフセットを一意に特定するのに十分であることに留意されたい。以下にさらに詳細に説明されるように、本発明の実施形態の付加的なレジストレーション符号化シンボルは、特定の量の誤り訂正を提供する。図６は、正しい向きに回転した後のＦＯＶブロック１０４と共に、ＦＯＶ１００を示す。
【００３７】
図７は、当該視野ブロックが重なっている４つの領域１２１〜１２４に関連するＦＯＶブロック１０４を示す。上述されたように、レジストレーション符号化シンボルによって示されるオフセット情報は、そのような相対的な位置決めを提供する。
【００３８】
領域１２１〜１２４はそれぞれ、そのページ番号、行番号及び列番号を特定するための完全な情報を含むが、図８に示されるように、ここでは、そのような領域１２１〜１２４のいずれの１つに関しても、まだ完全な情報を持っていない。この時点では、ＦＯＶブロック１０４内の符号化シンボルしかわかっていない。
【００３９】
図９は、４つの重なった領域１２１〜１２４を示し、それぞれの符号化パターンが示されている。図９と図８とを比較し、上記で示された関係を記憶しておくことによって、領域１２１のための符号化シンボルを完全に埋めることができる。それを果たすための経過は以下のとおりである。
【００４０】
最初に、図９及び図１０Ａを比較すると、ＦＯＶブロック１０４内の符号化シンボル１３１は既に領域１２１内に存在する。したがって、それらのシンボルは、ＦＯＶブロック１０４から領域１２１内の適切な場所に単にコピーされ、その結果が図１１Ａに示されている。また、領域１２１内のレジストレーション符号化シンボルの決まった場所も予めわかっている。それゆえ、図１１Ａに示されるように、それらのシンボルも領域１２１に追加される。
【００４１】
図９に示される、Ｎ０．．．Ｎ６ページ番号指示子が、図１０Ｂにおいて要素１４１及び１４２として強調表示される。ページ番号指示子は、ページ１０全体を通じて同一である。したがって、再び図９を参照すると、ページ番号指示子１４１が領域１２４から領域１２１にコピーされ、ページ番号指示子１４２が領域１２３から１２１にコピーされ、最終的な結果は図１１Ｂに示す通りである。
【００４２】
再び図９を手短に参照すると、領域１２１及び１２３内の列（Ｘ）符号化シンボルは同一である。なぜなら、これらの２つの領域は同じ列内にあるからである。それゆえ、領域１２３内のＸ符号化シンボルを、領域１２１内の対応する場所にコピーすることができる。これが図１０Ｃ及び図１１Ｃに示される。各領域の最も右にある列内の誤り訂正符号化シンボルＸ５、Ｘ６の場所、及び欠けている符号化シンボルを埋めるために左上の重なった領域を選択するという事実は、合わせると、完成している領域において誤り訂正符号化シンボルＸ５、Ｘ６を入手することができるか、又はそうでない場合それらのシンボルを単に、その真下の領域からコピーすることができることを意味することに留意されたい。
【００４３】
領域１２１又は１２３の一部でない（この例では存在しない）任意の残りのＸ符号化シンボルに関しては、本発明人らは、領域１２２及び１２４内のそれぞれのＸ符号化シンボルに基づいて、すなわち、この実施形態では、領域１２２及び１２４内の対応するＸ符号化シンボルから１を引くことによって、それらのシンボルを計算するであろう。
【００４４】
同様に、再び図９を手短に参照すると、領域１２１及び１２２内の行（Ｙ）符号化シンボルは同一である。なぜなら、これらの２つの領域は同じ行内にあるからである。それゆえ、領域１２２内のＹ符号化シンボルを、領域１２１内の対応する場所にコピーすることができる。これが図１０Ｄ及び図１１Ｄに示される。各領域の最も下にある行内の誤り訂正符号化シンボルＹ５、Ｙ６の場所、及び欠けている符号化シンボルを埋めるために左上の重なった領域を選択するという事実は、合わせると、完成している領域において誤り訂正符号化シンボルＹ５、Ｙ６を入手することができるか、又はそうでない場合、それらのシンボルを単に、その右隣の領域からコピーすることができることを意味することに留意されたい。実際には、Ｙ６は各領域の最右下隅にあるため、埋められている領域内に存在するであろう。
【００４５】
領域１２１又は１２２の一部でない（この例では存在しない）任意の残りのＹ符号化シンボルに関しては、本発明人らは、領域１２３及び１２４内のそれぞれのＹ符号化シンボルに基づいて、すなわち、この実施形態では、領域１２３及び１２４内の対応するＹ符号化シンボルから１を引くことによって、それらのシンボルを計算するであろう。
【００４６】
ここで、本発明人らは、対応する後続の位置ベクトル（すなわち、適宜、後続の列又は行内）のそれぞれの数字に基づいて、位置ベクトル内の欠けている数字を計算する方法の一般的な解法を定式化する。ＦＯＶ１０４によって重ね合わせられる左上の領域をいつでも完成させる（又は再構成する）規則が確立される場合、以下のようにして、（同じ列又は行内にそれぞれ、対応する列符号化シンボル又は行符号化シンボルが存在しないために）単にコピーすることができない任意の位置符号化シンボルを求めることができる。
【００４７】
Ｘi＝Ｘi,J．．．Ｘi,0によって、小さい方の位置ベクトル表現８進数を表し、Ｘi+1＝Ｘi+1,J．．．Ｘi+1,0によって、適用可能な連続する位置ベクトル表現８進数を表す。インデックスｊ∈｛０，．．．Ｊ｝毎に、Ｘi,j又はＸi+1,jのいずれかを入手することができる。その数字が８進数に基づく、ＸiのＪ個全ての数字を求めるための方法は、以下のように与えられる；
入力：インデックスｊ∈｛０，．．．Ｊ｝毎に、８進数に基づいて、Ｘi,j又はＸi+1,jのいずれかを入手することができる。
出力：２つの連続する８進数Ｘi＝Ｘi,J．．．Ｘi,0及びＸi+1＝Ｘi+1,J．．．Ｘi+1,0。
方法：ｊ＝０，．．．，Ｊの場合に以下の演算を繰り返す；
Ｘi,j-1．．．Ｘi,0が解像されるが、Ｘi,jが入手することができない場合：
・Ｘi,j-1．．．Ｘi,0が全て「７」である場合（詳細には、ｊ＝０である場合）、
・Ｘi+1,j＝０である場合には、Ｘi,j＝７を設定する；
・Ｘi+1,j≠０である場合には、Ｘi,j＝Ｘi+1,j−１を設定する；
・そうでない場合には、Ｘi,j＝Ｘi+1,j。
【００４８】
たとえば、Ｘi＝５□３□□及びＸi+1□０□２０である場合には、Ｘi＝５０３１７及びＸi+1＝５０３２０である。同様の方法を用いて、再構成される領域から欠けているＹ位置符号化シンボルが求められる。図４において提案される具体的な符号化パターンによれば、左上の重ね合わせられた領域をいつでも再構成するという規則と合わせて、再構成されている領域においていつでもＸ3、Ｘ4が入手可能であるか、又はその真下の領域から直にコピーすることができ（それらが、そのパターンの最も右の列にあるため）、且つ再構成されている領域においていつでもＹ2、Ｙ3、Ｙ4が入手可能であるか、又はその右隣の領域から直にコピーすることができる（それらが、そのパターンの最も下の行にあるため）ことが確実になる。それゆえ、この実施形態では、上記の方法を適用して、多くてもＸ2Ｘ1Ｘ0及びＹ1Ｙ0しか計算する必要がない。
【００４９】
領域サイズが必ずしも５×５でないか、又は取り得る符号化シンボル値の数が必ずしも９ではない、さらに一般的な場合について考える。領域設計では、行番号に対応する全ての誤り訂正符号化シンボルが単一の行内に（たとえば、その領域の最上端又は最下端に）配置され、列番号に対応する全ての誤り訂正符号化シンボルが単一の列内に（たとえば、その領域の左端又は右端に）配置されることが好ましい。このようにして、ＦＯＶブロック内の種々の誤り訂正符号化シンボルは常に、単一の行番号及び単一の列番号に対応する。ＦＯＶが種々の領域の部分を覆うときには必ず、計算されるべき行値及び列値は、誤り訂正符号化シンボルに対応する。
【００５０】
換言すると、位置情報符号化シンボル（上記の例では、コードワード毎に５つの符号化シンボル）から誤り訂正符号化シンボル（上記の例では、コードワード毎に２つの符号化シンボル）を分離し、再構成する領域を選択すると共に、符号化パターン内に誤り訂正符号化シンボルを入れる場所を選択することは、合わせて、再構成される領域のための誤り訂正符号化シンボルの全てが視野内に存在すること、すなわち必要に応じて正しい位置にコピーすることしか必要としないことを確実にする。そのような領域及び配置を適切に選択することによって、ＦＯＶブロックは、任意の単一の領域よりも大きくする必要がなくなる。
【００５１】
図４において提案される具体的な符号化パターンでは、行誤り訂正符号化シンボルは最も下の行内にあり、列誤り訂正符号化シンボルは最も右の列内にある。向きを補正されたＦＯＶでは、誤り訂正符号化シンボルは常に、左上の領域（たとえば、図７及び図８の領域１２１）の座標に対応する。これは、上記の例において、我々の復号化技法が領域１２１を完全に再構成するためである。
【００５２】
上記で与えられた例では、領域は正方形である。しかしながら、本発明は正方形の領域に限定されないことは理解されたい。上記の概念は、長方形の領域、及び他の形状の領域にも当てはまる。
【００５３】
図１２は、本発明の典型的な実施形態による、位置特定復号化処理を説明するフローチャートを示す。最初に、ステップ１６１では、デジタルペン３５又は他のセンサデバイスから、画像情報が得られる。
【００５４】
ステップ１６２では、画像情報のＦＯＶを回転して、正しい向きに向ける。上記で説明されたように、このステップは、レジストレーション符号化シンボル（それは、この実施形態では、回転しても変化しない）を特定することを含む。このために、たとえば、仮想ラスタ線に基づいて、最初に、潜在的な向きが求められることが好ましい。レジストレーション符号化シンボルとして特定されている符号化シンボルがひとたび特定されると、ＦＯＶブロックに対応する配列を生成し、たとえば、レジストレーション符号化シンボルが特定された場所を示す「１」と、残りの各位置内にある「０」で、それらの位置を指示することができる。正しい向きにあり、オフセットがないＦＯＶブロック１８０の場合に、レジストレーション符号化シンボルが１８１であり、非レジストレーション符号化シンボル１８２である例が、図１３に示される。
【００５５】
上述されたように、誤りがないものと仮定して、正しいオフセット及び向きを一意に求めるために、３つのレジストレーション符号化シンボルしか必要とされない。実際には、レジストレーション符号化シンボルとして特定される符号化シンボルのうちのいくつかは、実際にはレジストレーション符号化シンボルでないことがあるか、又は本当はレジストレーション符号化シンボルであるものが、そのように特定されないことがある。そのような誤りは、ほこり、正規の場所から外れたマーキング等に起因することがある。たとえば、図１３に示されるように、１つの余分なレジストレーション符号化シンボルを追加することによって、１つのそのような誤りがある場合であっても、向き及びオフセットを正しく特定することができるようになることがわかっている。
【００５６】
生成されたマップ（たとえば、図１３に示される）を、全ての取り得る向き及びオフセットのマップと比較することによって、向き及びオフセットが求められる。上記で与えられた例では、２５（５×５）の潜在的なオフセットがあり、仮想ラスタ線の存在に起因して、４つの潜在的な回転（０°、９０°、１８０°、２７０°）だけがあり、それは全部で１００通りの取り得る組み合わせがあることを意味する。参照される比較は、生成されたマップと１００個の異なる潜在的なマップとの間のハミング距離を計算すること（すなわち、その値が異なる、２つのマップ内の対応する位置の数をカウントすること）及び、最小ハミング距離を有する潜在的なマップ（その対応するオフセット及び回転を有する）を選択することを含むことが好ましい。適切な仮定のもとで、レジストレーションパターンのために用いられる上記の誤り訂正符号が見受けられ、レジストレーション符号の復号化誤り確率を９６．６％だけ低減することができる。
【００５７】
２つ以上の候補がある場合には、又は観測されたパターンから最も近いテンプレートまでの距離が長すぎる（たとえば、２以上）と見なされる場合には、そのデータは十分な信頼性がないため、その位置特定において誤りが宣言される。１つの候補が見つけられたものと仮定すると、ＦＯＶブロックは、上記のように単に回転し、領域境界に対して、そのオフセット（たとえば、図７及び図８において示される）が求められる。
【００５８】
上記の回転及びオフセットを特定するための技法は、ＦＯＶマップを、１００個の正当なＦＯＶマップとそれぞれ比較する。それゆえ、符号化シンボル比較の数は２５００回になることがある。実際の実施態様では、以下の方法は、さらに効率的にすることができる。所与のＦＯＶ内のレジストレーション符号化シンボルの数をカウントする。その数が５よりも大きいか、又は３よりも小さい場合には、そのレジストレーションパターン内に２つ以上の誤りが存在するため、復号化するのを避ける。
【００５９】
そうでない場合には、図３に示されるような、中央に配置されるレジストレーションパターンを回転させることによって得られる４つのレジストレーションテンプレートについて考える。ＦＯＶ内の１つのレジストレーションシンボルを選択し、それを、回転したテンプレートの１６個の取り得るレジストレーションシンボルの場所のうちの１つ（４回転×４つのレジストレーションの場所のそれぞれ）と位置合わせする。回転したテンプレートのうちの１つにおいて３つ又は４つのＦＯＶレジストレーション符号がレジストレーションの場所と重なり合う場合には、一致が得られる。ＦＯＶシンボルのうちのいずれかが５×５テンプレートブロックの外側にある場合には、それは再び、同じ回転したテンプレートの他の側にも繰返し現れる。一致が見つけられない場合には、別のＦＯＶレジストレーションシンボルを同じようにして調べる。多くても１つのシンボル読取り誤りしか生じなかった場合には、調べられた２つのシンボルのうちの一方（又は両方）が単一のテンプレートと一致する。図１３のパターンは、単一の一致しかないことを確実にする。ここで必要とされるシンボル比較の回数は、多くても２５＋２×１６×４＝１５３である。必要とされる回転は、テンプレート回転に対応する。シフトは、選択されたＦＯＶシンボルの場所を、中央に配置されるテンプレート内の対応する場所と比較することによって見つけられる。
【００６０】
図１２に戻ると、ステップ１６４では、画像情報が位置符号化シンボルに変換される。‘７６８特許の技法が用いられているものと仮定すると、印刷されたシンボル（たとえば、ドット）をＦＯＶブロックの位置符号化シンボルに変換するために必要とされるのは、名目的な場所からの距離を特定することだけである。
【００６１】
最後に、ステップ１６５では、位置符号化シンボルが復号化されて、デジタルペン３５（又は他のセンサデバイス）の位置が特定される。上述されたように、そのような位置を求めるために、好ましい技法は、最初に、１つの領域全体のための符号化パターンを再構成することである。その情報がわかると、その領域の位置を直に読み取ることができ、そこから、ＦＯＶブロックの位置（オフセット情報に基づく）、及びペン先端の位置（その先端とＦＯＶとの間の既知の関係に基づく）も容易に計算することができる。
【００６２】
１つの領域全体の再構成は上記で詳細に説明されているため、ここでは繰り返されない。いかなる検出誤りもなければ、位置符号化シンボルから位置情報を読み取ることは簡単であろう。誤りが存在することがあるものと仮定して、以下の説明は、誤り訂正符号化シンボルを構成する方法、及び一定の誤りが存在する場合であっても、正しい結果を生成するように、結果として生成される位置符号化シンボルを復号化する方法を記述する。本発明の好ましい実施形態では、リード・ソロモン符号化／復号化技法が用いられる。
【００６３】
その一般的な形式では、リード・ソロモン技法は、１つのブロックのメッセージを、有限体にわたってプロットされる多項式内の点として符号化する。その多項式の係数はブロックのデータ値である。そのプロットは係数を余分に求め、それらの係数は後に、プロットされた点のサブセットから再生することができる。間隙を補間することによって曲線を補正することができるのと同じ意味において、リード・ソロモン符号は、データブロック内の１つ又は複数の誤りを埋めて、元の曲線を描いた多項式の係数を再生することができる。
【００６４】
上記の例では、情報符号化シンボルは、サイズ８の記号体系から、その値をとる。それゆえ、本発明人らは、ＧＦ（８）で表される、サイズ８の有限体にわたって１つの誤り訂正符号化シンボルを用いて作業することにした。その体の定義が以下のように与えられる。本発明人らは、シンボル｛０，．．．，７｝を、８進数及び体要素の両方として用いるが、８進数算術と体算術とを区別する。８進数算術では、たとえば、５＋１＝６であるのに対して、ＧＦ（８）の付加的な規則は、１０１＋００１＝１００を意味する。本発明人らは、８進数算術を用いて、情報符号化シンボルＮ0，．．．，Ｎ4、Ｘ0，．．．，Ｘ4及びＹ0，．．．，Ｙ4を求める。ＧＦ（８）算術は、パリティ（又は誤り訂正）符号化シンボルＮ5、Ｎ6、Ｘ5、Ｘ6及びＹ5、Ｙ6を求めるために用いられる。それらは、以下に記述される技法に基づいて計算される。復号化するときに、本発明人らは、情報及び誤り訂正符号化シンボルを再生するために、再びＧＦ（８）算術を用いる。
【００６５】
本発明人らは、異なり、且つ独立している３つのコードワードにおいて位置データを符号化する。しかしながら、それらのコードワードは、同じ符号構造、すなわちＧＦ（８）にわたる［７，５，３］リード・ソロモン符号に属する。符号長は７であり、符号次元は５であり、最小ハミング距離は３である。したがって、各コードワードは、７つの符号化シンボル、すなわち５つの情報（又はメッセージ）符号化シンボル（Ｎ0，．．．，Ｎ4、Ｘ0，．．．，Ｘ4、Ｙ0，．．．，Ｙ4のいずれか）及び２つのパリティ（又は誤り訂正）符号化シンボル（それぞれ、Ｎ5、Ｎ6、又はＸ5、Ｘ6又はＹ5、Ｙ6）から成る。最小距離３は、符号の長さ及び次元を与えた場合に取り得る最大距離である。本発明人らは、組織的［７，５，３］リード・ソロモン符号を選択しており、その生成多項式は、以下のとおりである：
ｇ（ｘ）＝（ｘ−１）（ｘ−α）＝ｘ2＋α3ｘ＋α
ただし、αはＧＦ（８）の原始元である。
【００６６】
ページ１０上の単一の領域の全てのシンボルを解像した後に（たとえば、上記の手順を用いる）、本発明人らは、存在することがある誤りを訂正するために、リード・ソロモン復号化技法を適用する。本発明人らは、後に規定される復号化技法を個別に用いて、３つのコードワードをそれぞれ復号化する。
【００６７】
この実施形態におけるリード・ソロモン符号は、３の最小ハミング距離を有し、それゆえ、その符号によって、１つのコードワード内で任意の単一の誤りを訂正することができるようになる。それゆえ、その領域内にある訂正可能な誤りパターンは、２つの誤りが同じコードワード内に入らない限り、１つ〜３つの欠陥のある符号化シンボルを有する全てのパターンを含む。
【００６８】
重み２以上の誤りパターンが、元のコードワードを別のコードワードに変換する場合、又はコードワードからハミング距離１にあるベクトルに変換する場合があることに留意されたい。それらの場合に、復号化技法は、間違ったコードワードを生成することがある。しかしながら、そのような場合に陥る確率は、誤りがないか、又は１つの誤りを有する元のコードワードを受信する確率よりもはるかに小さい。より具体的には、適切な仮定を用いるとき、そのような誤り訂正は、ＦＯＶ内で単一の完全な領域が捕捉される場合には、９８．６９％だけ誤りの確率を低減し、さらに一般的な場合には少なくとも９５％だけ低減することがわかっている。
【００６９】
１つのフィールド（ただ１組の要素の代わりに）で機能することによって、要素間で算術演算することができるようになる。そのフィールドは加法及び乗法の下で閉じており、これらの２つの演算は可換且つ結合的である（分配法則も当てはまる）。その体は、０及び１で表される２つの特殊な要素を有する。全てのフィールド要素αは加法的な逆元を有し（α＋（−α）＝０）、０を除く全ての要素は、乗法的な逆元も有する（α×α-1＝１）。
【００７０】
８つの要素から成る全ての有限体は互いに同型である。こうして、ＧＦ（８）で表される、サイズ８のガロア体は固有であると見なされる。８つのフィールド要素の場合に２つの一般的な表記法がある。第１の表記法は、長さ３の２値ベクトルを用いる。この表記によれば、加法がＧＦ（２）に関する簡単なベクトル加法であるため（たとえば、００１＋１０１＝１００）、要素加法を計算するのが非常に容易になる。第２の表記法は、フィールドの乗法群を生成する、原始元αの累乗を使用する。したがって、フィールド要素は｛０，１＝α0、α＝α1，α2，α3，α4，α5，α6｝で表される。この表記法によれば、要素を簡単に乗算することができるようになる。すなわち、０以外の要素を乗算し、それらの累乗を足して、７を法とする和をとることができるようになる。
【００７１】
２値ベクトル表現は、フィールド要素１、α及びα2の一次結合に対応する。ここで、αは原始多項式ｘ3＋ｘ＋１＝０の根である。全てのフィールド要素を、そのような一次結合によって記述することができる。たとえば、α3＝−α−１＝α＋１である（ＧＦ（２）に関して−ｘ＝ｘであることに留意されたい）。それぞれの一次結合を記述する２値ベクトルは０１１である。別の原始多項式ｘ3＋ｘ2＋１＝０を用いて、体ＧＦ（８）を定義することができる。その際、異なる表を用いて、２つの要素表現間が結び付けられる。しかしながら、結果として生成されるフィールドは、上記で定義されたフィールドに同型である。
【００７２】
上記の符号パラメータ及び生成多項式を与えるとき、符号化規則は以下のようになる：
１．５つのメッセージシンボルをｍ4ｍ3ｍ2ｍ1ｍ0によって表す。メッセージ多項式をｍ（ｘ）＝ｍ4ｘ4＋ｍ3ｘ3＋ｍ2ｘ2＋ｍ1ｘ＋ｍ0と定義する。
【００７３】
２．ｘ2・ｍ（ｘ）を生成多項式ｇ（ｘ）で割る。ｐ（ｘ）＝ｐ1ｘ＋ｐ0を剰余多項式とする。
【００７４】
３．出力コードワードは、（ｃ6，ｃ5，ｃ4，ｃ3，ｃ2，ｃ1，ｃ0）＝（ｍ4，ｍ3，ｍ2，ｍ1，ｍ0，ｐ1，ｐ0）である。
【００７５】
上記の符号化規則は、符号が全てのベクトル
【００７６】
【数１】
【００７７】
のセットであることを意味し、その場合に、フィールド要素１及びαは対応する多項式
【００７８】
【数２】
【００７９】
の根である。
上記を満たすベクトル
【００８０】
【数３】
【００８１】
はコードワードと呼ばれる。この符号は、有限フィールドＧＦ（８）に関する線形部分空間である。部分空間次元は５である。
【００８２】
コードワード成分（すなわち、符号化シンボル）のインデックスは、上記の符号インデックスと一致しないことに留意されたい。詳細には、パリティ符号化シンボルＮ5、Ｎ6（又はＸ5、Ｘ6又はＹ5、Ｙ6）はｃ1、ｃ0に対応する。
【００８３】
その領域が訂正可能な誤りパターンを含むものと仮定する。以下のベクトルが、検出デバイスによって捕捉されるような、Ｎ、Ｘ又はＹベクトルのうちの１つに関連付けられるものとする。
【００８４】
【数４】
【００８５】
以下に規定される復号化アルゴリズムは、
【００８６】
【数５】
【００８７】
が元のコードワードであるか、又はハミング重み１の元のコードワード
【００８８】
【数６】
【００８９】
と誤りベクトル
【００９０】
【数７】
【００９１】
との一次結合
【００９２】
【数８】
【００９３】
のいずれかである場合には、元のコードワードを見つける。
入力：ＧＦ（８）に関するベクトル
【００９４】
【数９】
【００９５】
出力：そのようなコードワードが存在する場合には、
【００９６】
【数１０】
【００９７】
からのハミング距離≦１におけるコードワード
【００９８】
【数１１】
【００９９】
方法：体要素１及びαにおいて多項式
【０１００】
【数１２】
【０１０１】
を数値計算する。
１．υ（１）＝υ（ａ）＝０である場合には、
【０１０２】
【数１３】
【０１０３】
を返す。
２．υ（１）≠０且つυ（α）≠０である場合には、ｊ∈｛０，．．．，６｝を見つける。ここで、αj＝υ（α）／υ（１）である。第ｊの成分υjから値υ（１）を引くことによって、
【０１０４】
【数１４】
【０１０５】
から
【０１０６】
【数１５】
【０１０７】
を得る。
３．υ（１）＝０であるが、υ（α）≠０である場合、又はυ（１）≠０であるが、υ（α）＝０である場合には、いかなるコードワードも返さない。
【０１０８】
図６の事例１では、
【０１０９】
【数１６】
【０１１０】
がコードワードであるため、本発明人らは、その符号化シンボルのいずれも変更しない。事例２では、第ｊの成分の変更が、入力ベクトル
【０１１１】
【数１７】
【０１１２】
からハミング距離１にある唯一のコードワードを与える。事例３では、
【０１１３】
【数１８】
【０１１４】
はＣ内のいずれのコードワードからもハミング距離２以上にある。その復号化技法は、そのような事例においていかなる訂正も規定しない。それらの事例は訂正することができないと見なされる。
【０１１５】
上記の符号化パターンによれば、流動的に位置を求めることができるようになる。換言すると、任意の位置を、完全に１つの領域を含むＦＯＶだけでなく、単一の領域と同じサイズを有する任意のＦＯＶから解像することができる。同時に、そのパターンは、符号化シンボル検出誤りに対して、ある程度の保護を与える。
【０１１６】
特定の事例では、印刷されたシンボルの繰返しパターンを除去することが望ましい。この目的を果たすために、本発明の代替的な一実施形態では、種々の領域が、行（又は列）番号を保持するシンボルが２つの行（列）に集中しないように、たとえば、隣接する行（列）内に集中しないように編成される。
【０１１７】
他の実施形態は、ページ番号の繰返しを解消しようと試みる。これを果たすために、本発明人らは、Ａ9個の要素の擬似ランダムな置換に応じて、各ページ番号を置き換える。隣接する領域のために、且つ相対的に近い領域のために異なる置換が選択される場合には、領域の行又は列を分割していることが、裸眼では区別しにくくなるはずである。
【０１１８】
復号化するために、所与のＦＯＶにおいて符号化シンボル毎に用いられるマッピングを容易に決定することができるはずである。それゆえ、本発明人らは、この領域に書き込まれる行値及び列値に基づいて領域置換を選択する。復号化するとき、ページ番号を復号化する前に、行番号及び列番号を復号化する。これは、３つの異なる領域コードワードの復号化処理の間に以前にあった独立性を解消する。行番号及び列番号の復号化に誤りがあれば、典型的には、ページ番号が誤っていることを意味するであろう。
【０１１９】
本発明人らは、領域毎に置換を定義するために以下の具体的な技法を提唱する。ある一定の数ｎの置換をランダムに生成し、その置換を表に入れておく。数ｎは、行又は列当たりの領域の数に近い素数のうちの最も大きな素数であることが好ましい。Ａ４ページの場合、本発明人らは、ｎ＝２５１を使用する。行ｒ及び列ｃに或る領域を与えるとき、以下のインデックスにおいて置換が実施される。
【０１２０】
【数１９】
【０１２１】
式中、ｐ1及びｐ2は２つの小さな素数、たとえば２及び３である。ｐ1及びｐ2はｎを分割しないため、長方形グリッド効果が低減されるはずである。インデックスｉはｒ＋ｃ又はｒ−ｃの関数ではないため、対角線効果も生み出されないはずである。
【０１２２】
［システム環境］
一般的に言うと、本明細書において記述される方法及び技法の概ね全てを、汎用コンピュータシステムを使用して実施することができる。そのようなコンピュータは典型的には、たとえば、互いに、たとえば共通バスを介して相互接続される以下の構成要素のうちの少なくともいくつかを含むであろう：１つ又は複数の中央演算装置（ＣＰＵ）、リードオンリーメモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、他のデバイスとのインターフェースを構成し、且つ１つ又は複数のネットワークに接続するための入力／出力ソフトウエア又は回路（ネットワークはさらに、本発明の多くの実施形態において、インターネットに、又は任意の他のネットワークに接続する）、ディスプレイ（陰極線管ディスプレイ、液晶ディスプレイ、有機発光ディスプレイ、高分子発光ディスプレイ又は任意の他の薄膜ディスプレイ等）、他の出力デバイス（１つ又は複数のスピーカ、ヘッドホンセット又はプリンタ等）、１つ又は複数の入力デバイス（マウス、タッチパッド、タブレット、タッチセンシティブディスプレイ若しくは他のポインティングデバイス、キーボード、マイクロホン又はスキャナ等）、大容量記憶ユニット（ハードディスクドライブ等）、リアルタイムクロック、取外し可能記憶読出し／書込みデバイス（ＲＡＭ、磁気ディスク、磁気テープ、光磁気ディスク、光ディスク等からの読出し、又はそれらへの書込み用等）、及びモデム（モデムも、ダイヤルアップ接続を介して、インターネットに、又は任意の他のコンピュータネットワークに接続することが好ましい）。動作時に、そのような汎用コンピュータによって実行される限り、上記の方法を実施する処理ステップは典型的には最初に大容量記憶装置（たとえば、ハードディスク）に格納され、ＲＡＭにダウンロードされ、その後、ＲＡＭから出してＣＰＵによって実行される。
【０１２３】
本発明を実施する際に用いるのに適しているコンピュータは、種々のベンダから入手することができる。しかしながら、タスクのサイズ及び複雑さに応じて、様々なタイプのコンピュータが用いられることがある。適切なコンピュータは、メインフレームコンピュータ、マルチプロセッサコンピュータ、ワークステーション、パーソナルコンピュータ、及びＰＤＡ等のさらに小型のコンピュータ、無線電話又は任意の他の機器又はデバイスを含み、スタンドアロンで用いられるか、ネットワークに有線で接続されるか、又はネットワークに無線で接続される。さらに、上記で汎用コンピュータシステムが記述されてきたが、代替的な実施形態では、その代わりに（又は、それに加えて）専用コンピュータが用いられる。詳細には、上記の機能のいずれかを、ソフトウエア、ハードウエア、ファームウエア又はこれらの任意の組み合わせで実現することができ、既知の工学上のトレードオフに基づいて特定の実施態様が選択される。これに関連して、上記の機能は主に固定された論理的ステップを通じて実施され、それゆえ、当該技術分野においてよく知られているように、プログラミング（たとえば、ソフトウエア又はファームウエア）、論理部品の適切な構成（ハードウエア）、又は２つの任意の組み合わせを通じて果たすことができることに留意されたい。
【０１２４】
本発明は、本発明の方法を実行するためのプログラム命令が格納される機械読取り可能媒体にも関連することは理解されたい。そのような媒体は、一例として、磁気ディスク、磁気テープ、ＣＤ ＲＯＭ及びＤＶＤ ＲＯＭのような光学的に読取り可能な媒体、ＰＣＭＣＩＡカードのような半導体メモリ等を含む。いずれの場合でも、媒体は、小さなディスク、ディスケット、カセット等の持ち運びできる商品の形をとることがあるか、又は、コンピュータ内に設けられるハードディスクドライブ、ＲＯＭ又はＲＡＭのような、相対的に大きいか、又は動かすことができない商品の形をとることがある。
【０１２５】
上記の説明は主に電子コンピュータに重点を置いている。しかしながら、代わりに、電子、光学、生物又は化学処理の任意の組み合わせを利用するコンピュータのような、任意の他のタイプのコンピュータが用いられることがあることは理解されたい。
【０１２６】
[付加的な検討事項]
本発明は主に、マークされた１枚の紙の上でデジタルペンの位置を特定することとの関連で上記で説明されているが、本発明は他の位置特定問題にも適用することができることは理解されたい。たとえば、別の用途は、デジタルマウスの位置を特定することであり、本発明による位置情報で符号化されているマウスパッド上で高い分解能を有する。
【０１２７】
本発明のいくつかの異なる実施形態が上述され、そのような実施形態はそれぞれ、特定の特徴を含むように記述されている。しかしながら、任意の単一の実施形態の説明との関連で記述される特徴は、その実施形態には限定されず、他の実施形態のうちのいずれかの種々の組み合わせに含まれるか、その組み合わせで構成されることができることが意図されていることは、当業者には理解されよう。
【０１２８】
同様に、上記の説明では、機能はいくつかの場合に、特定のモジュール又は構成要素に帰する。しかしながら、機能は一般的には、所望によって、任意の異なるモジュール又は構成要素の中で分散させることができ、場合によっては、特定の構成要素又はモジュールが全く不要になるか、あるいは新たな構成要素又はモジュールを追加する必要がある。厳密な機能分散は、本発明の具体的な実施形態を参照しながら、既知の工学上のトレードオフに従って行なわれることが好ましいことは、当業者には理解されよう。
【０１２９】
こうして、本発明は、その例示的な実施形態及び添付の図面との関連で詳細に説明されてきたが、本発明の精神及び範囲から逸脱することなく、本発明の種々の改変及び変更を果たすことができることは当業者には明らかであろう。したがって、本発明は、図示され、上記で説明されたのと全く同じ実施形態には限定されない。むしろ、本発明の精神から逸脱しない全てのそのような変形は、添付の特許請求の範囲によってのみ制限されるような、本発明の範囲内にあるものと見なされることが意図されている。
【技術分野】
【０００１】
本発明は、ごくわずかな視野内で位置特定情報を知ることに基づいて、位置特定情報で符号化されている１枚の紙又は他の基板上での位置を特定することに関する。本発明は、たとえば、デジタルペンとの関連での位置特定に適用することができる。
【背景技術】
【０００２】
一般的にデジタルペンは、普通のペンと同じようにしてインクで紙に書くことができるのに加えて、そのようなペンによって形成された任意のマークをデジタル化し、その後、転写するか、又は内部に格納することができるペンである。そのようなデジタルペンの多くが、紙の上に予め印刷されているパターンを検出するために小型カメラを利用する。パターンが適切に予め印刷されている紙と、適切な復号化ソフトウエアとを用いることによって、そのようなデジタルペンは、その上にマークが形成される個々の紙片を一意に、又は特定のセットの構成要素として概ね特定することができ、各マークが形成される紙の上の場所を区別することができる。結果として、デジタルペンは、コンピュータ入力デバイスとして用いることができる。デジタルペンの一例は、ヒューレット・パッカード社のデジタルペンであり、このペンは、ペンストロークを内部に格納し、その後、クレードルに挿入されると、デジタル化されたマークをコンピュータにダウンロードする。
【０００３】
紙に位置特定情報をマークする１つの方法が、特許文献１において記載されており、当該特許は、本明細書においてその全体が述べられるかのように、参照により本明細書に援用される。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】米国特許第６，５４８，７６８号
【発明の概要】
【０００５】
一態様によれば、本発明は、任意の回転、オフセット及び特定の誤り（たとえば、紙の上のほこり、又は正規の場所から外れたマーキングに起因する）が存在する場合であっても、位置を特定することができるようにする特定の符号を提供することによって、既存の符号化技法を改善する。
【０００６】
上記の概要は単に、本発明の全般的な性質の簡潔な説明を与えることを意図している。添付の図面との関連において、特許請求の範囲及び好ましい実施形態の以下の詳細な説明を参照することによって、本発明をより十分に理解することができる。
【図面の簡単な説明】
【０００７】
【図１】本発明の典型的な実施形態による、符号化された紙を生成するためのシステムのブロック図である。
【図２】本発明の典型的な実施形態による、符号化された紙を使用するためのシステムのブロック図である。
【図３】本発明の典型的な実施形態による、複数の領域に分割されている１枚の紙を示す図である。
【図４】本発明の典型的な実施形態による、１つのページ上の単一の領域のための符号化パターンを示す図である。
【図５】本発明の典型的な実施形態による、符号化されたページ上の任意の位置及び向きにおける検出デバイスの視野を示す図である。
【図６】本発明の典型的な実施形態による、正しい向きに回転した後の視野を示す図である。
【図７】本発明の典型的な実施形態による、当該視野ブロックが重なっている４つの領域に関連する視野ブロックを示す図である。
【図８】本発明の典型的な実施形態による、当該視野ブロックが重なっている４つの領域に関連し、当該視野ブロック内に符号化シンボルが表示されている視野ブロックを示す図である。
【図９】本発明の典型的な実施形態による、それぞれの符号化パターンが示されており、視野ブロックによって覆われる、４つの重なった領域を示す図である。
【図１０Ａ】本発明の典型的な実施形態による、符号化シンボルが当該位置からコピーされる経過を示すために種々の位置が強調表示されている視野ブロックを示す図である。
【図１０Ｂ】本発明の典型的な実施形態による、符号化シンボルが当該位置からコピーされる経過を示すために種々の位置が強調表示されている視野ブロックを示す図である。
【図１０Ｃ】本発明の典型的な実施形態による、符号化シンボルが当該位置からコピーされる経過を示すために種々の位置が強調表示されている視野ブロックを示す図である。
【図１０Ｄ】本発明の典型的な実施形態による、符号化シンボルが当該位置からコピーされる経過を示すために種々の位置が強調表示されている視野ブロックを示す図である。
【図１１Ａ】本発明の典型的な実施形態による、再構成される領域を示しており、そのような領域内に位置がコピーされる経過を強調表示する図である。
【図１１Ｂ】本発明の典型的な実施形態による、再構成される領域を示しており、そのような領域内に位置がコピーされる経過を強調表示する図である。
【図１１Ｃ】本発明の典型的な実施形態による、再構成される領域を示しており、そのような領域内に位置がコピーされる経過を強調表示する図である。
【図１１Ｄ】本発明の典型的な実施形態による、再構成される領域を示しており、そのような領域内に位置がコピーされる経過を強調表示する図である。
【図１２】本発明の典型的な実施形態による、位置特定復号化処理のための流れ図である。
【図１３】本発明の典型的な実施形態による、正しい向きにあり、オフセットがない視野ブロックの場合のレジストレーション符号化シンボル及び非レジストレーション符号化シンボルのマップを示す図である。
【発明を実施するための形態】
【０００８】
本発明は、２次元位置特定符号化パターンを設計するという実用的な問題を対処する。そのような符号化パターンは、大きな印刷表面及び検出デバイスから構成されるナビゲーションシステムとの関連で用いられることがある。位置特定符号化パターンは、その表面上に印刷される特殊なパターンを定義する。その検出デバイスは、表面上の複数の小さな領域の適度に良好な画像を与える。検出デバイスによって捕捉される限られた領域は、本明細書において視野（ＦＯＶ）と呼ばれる。ＦＯＶパターン内で捕捉される情報を用いて、大きな表面上の絶対位置が求められる。
【０００９】
本発明は特に、デジタルペン及び紙に関する最近開発されたシステムに適用することができる。この環境において、紙の上に特殊なパターンが予め印刷される。そのペンは、書くと同時に、その紙を繰返し撮影する小型カメラを備える。これらの写真から解像される位置データによって、そのシステムは、その文書を表すデジタル画像を生成することができるようになる。
【００１０】
位置特定符号化は新しくはないが、本発明の手法は特定の利点をもたらす。本発明の典型的な実施形態では、紙に対するカメラ軸の向きは任意にすることができる。換言すると、そのような実施形態における位置特定は、ＦＯＶ向きが回転しても変化しない。さらに、特定の実施形態は、画像処理モジュールによって、いくつかの位置特定符号化シンボルが誤って検出される場合であっても、その位置を正しく特定することができる。そのような検出の誤りは、たとえば、プリントエラー、又は文書が擦り切れていること、ほこり、又はカメラアングルが難しいことに起因して生じることがある。
【００１１】
以下に説明される例示的な実施形態において、本発明人らは、９個の符号化シンボルの記号体系において定義される位置特定符号化技法を提示する。この技法は、５×５×２45個の位置から成る表面に対応し、５×５位置ＦＯＶを用いて位置を特定することができるようにする。この実施形態では、回転していても、且ついくつかの誤りが存在する場合でも、正しく位置を特定することができる。
【００１２】
好ましい実施形態は、表面を、ＦＯＶと同じ寸法を有する重なり合わない複数の領域に分割することに基づく。各領域は、位置情報を与える３つの異なる番号を割り当てられる。３つの番号は、ページ番号、行番号及び列番号を表す。これらの番号は、物理的な座標に対応する必要はないが、好ましい実施形態では、１つの行（列）内の任意の２つの隣接する領域は、同じページ番号、同じ行（列）番号、及び連続する列（行）番号を有する。しかしながら、以下に記述される技法は、さらに一般的な状況下で機能し、たとえば、１つの行（列）内の任意の２つの隣接する領域が、同じページ番号と、同じ行（列）番号と、他の領域の列（行）番号に基づいて求めることができる列（行）番号とを有する場合にも機能するであろう。
【００１３】
以下に記述される実施形態では、ページ番号、行番号及び列番号は、符号化記号体系を用いて、各領域内の所定の場所に明示的に書き込まれる。また、記述される実施形態では、各領域内の他の場所は、位置情報に対応するパリティ（又は他の誤り訂正）情報を保持する。以下にさらに詳細に検討されるように、これらのパリティ（又は他の誤り訂正符号化シンボル又は情報）によって、特定の符号化−シンボル−特定の誤りを訂正することができるようになる。
【００１４】
各領域内の残りの場所はレジストレーションパターンとしての役割を果たし、異なる領域間の境界をマークすることに加えて、パターンの向きを決定する。カメラのＦＯＶは多くの場合に、種々の領域の部分を覆うため、レジストレーションパターンは、ＦＯＶ内の種々の領域に、いずれの符号化シンボルが属するかを指示する。位置情報は、ページ、行及び列のための明示的な番号によって与えられるため、種々の領域に対応するＦＯＶ符号化シンボルから位置を復号化するのは、非常に単純である。好ましい実施形態では、そのレジストレーションパターンによって、レジストレーション符号化シンボルのうちの１つが損なわれている場合であっても、所与の回転を受けている可能性があるＦＯＶ内でレジストレーションパターンを特定することができるようになる。これは、レジストレーション符号化シンボルのための１符号化シンボル誤り訂正能力も提供する。
【００１５】
上述されたように、本発明には特に、デジタルペン及び特別に符号化された紙との関連で適用することができる。そのような紙１０を生成するためのシステム５が図１に示される。最初に、モジュール１２において、符号化パターンが生成される。このパターンは、たとえば、各領域が位置符号化シンボル、又は、特定のページ（たとえば、ページ番号）を含む、その位置を特定するのに十分な他の情報を含むように、１枚の紙全体にわたって個々の領域の場所を一意に特定する。それらの領域は連続しており、重なり合うことなく、ページ全体を覆うことが好ましい。本発明によるパターンに関するさらなる詳細は、以下に述べられる。
【００１６】
その後、紙を他の目的のために使用することを過度に妨げることのないように、すなわち、その紙を任意の他の紙と同じようにして使用することができるように、変換モジュール１３が、位置符号化シンボルの指定されたパターンを、紙の上に印刷することができるマークのパターンに変換する。一例が‘７６８特許に記載されているパターン形成であり、当該特許では、個々の符号化シンボルは、仮想ラスタに基づいて、基準名目位置からの異なる距離によって表される。仮想ラスタが十分に小さなピッチを有する場合には、そのようなパターンを形成しても、結果として、概ね均一な灰色の背景になる。
【００１７】
モジュール１３によって出力されるパターン形成データに、付加データ１５を追加して、プリンタドライバ１７において合成することができる。たとえば、そのような付加データは、或る書式を印刷するためのベクトル又はラスタデータを含むことがある。その後、プリンタドライバ１７は、合成されたデータをプリンタ１９に与え、プリンタ１９は、背景パターン形成データと共に、任意のそのような付加データ１５を印刷し、それによって、符号化された紙１０が与えられる。付加データ１５は省略されることがあり、たとえば、符号化された紙１０が白紙のメモ用紙として用いられることになる場合には省略してもよいことに留意されたい。
【００１８】
図２は、符号化されたデータ１０を用いるシステム３４を示す。この例では、紙１０に書くためにデジタルペン３５が用いられており、ペン３５のユーザによって行なわれるマーキングを記録することも意図している。しかしながら、代替的な例では、その代わりに、紙１０から画像データを捕捉する能力を有する任意の他のタイプのデバイスが用いられる。たとえば、発表者が１枚の紙の上で指している場所についての情報を捕捉することが望ましい場合があり、その場合には、画像捕捉デバイスは筆記能力を有する必要はない。
【００１９】
この実施形態では、デジタルペン３５によって捕捉される画像データは、受信機３７を介して、リアルタイムに無線で（たとえば、ブルートゥース又は８０２．１１プロトコルを用いて）転送される。他の実施形態では、その画像データは、有線接続を介してリアルタイムに転送され、さらに別の実施形態では、画像データはペン３５に格納され、たとえば、ペン３５をクレードルに挿し込むことによって、後に転送される。
【００２０】
いずれにしても、モジュール３８において、（典型的には、あらゆる必要な回転後の）画像データが位置符号化シンボルに戻され、位置符号化シンボルは、モジュール４０において、紙１０の上のペン３５の位置を特定するために用いられる。その後、そのような情報は、格納された書込み情報と共に、適切なアプリケーション４２に与えられる。たとえば、紙１０が予め印刷された書式を含み、ユーザが、その書式上のボックスをチェックした場合には、検出された位置情報に基づいて、アプリケーション４２は、いずれのボックスがチェックされたかを判断し、その行為に基づいて、任意の関連付けられる処理を実行することができる。
【００２１】
こうして、符号化された紙１０をデジタルペン３５（又は他の画像形成デバイス）と共に用いることによって、ユーザは、単に紙片の上をマークするだけで、自動化されたタスクの実行をトリガすることができるようになる。残念なことに、従来の符号化された紙及び復号化技法は、本発明によれば許される程度の小さな視野を用いるときに特に、紙１０の上のほこり又は他の正規の場所から外れたマーキングによって引き起こされることがあるような、誤りに対する十分な耐性を有していない。
【００２２】
図３は、複数の領域（たとえば、領域６１〜６４）に分割されている１枚の紙１０を示す。本発明のこの実施形態では、各領域は正方形であり、それらの領域は１つの配列内に配置され、互いに接触しており、重なり合うことなく、紙１０全体を覆う。また、この実施形態では、各領域は、符号化シンボルの配列を（たとえば、領域６４の場合に示される位置７１〜７３において）含み、ここでは、５×５符号化シンボルの配列、すなわち全部で２５個の符号化シンボルを含む。以下にさらに詳細に説明されるように、各領域内の符号化シンボルは、その領域のためのページ番号、行番号及び列番号を特定する。こうして、この例では、或る領域のための行番号は、その真上に或る領域のための行番号よりも１だけ大きく、或る領域のための列番号は、その左隣に或る領域よりも１だけ大きい。
【００２３】
以下の説明は、印刷されたパターン表現ではなく、印刷されたパターンの符号表現に主に焦点を当てていることに留意されたい。すなわち、印刷されたマークから、位置符号化シンボル及びレジストレーション符号化シンボル（以下に説明される）への変換は概ね既に完了していると見なされる。これは、本発明が、位置及びレジストレーション符号化シンボルを表すために用いられる、具体的に印刷されたマークとは概ね無関係であるためである。この例では、対応する印刷されたシンボルパターンが構成される方法に起因して、そのパターン内の各位置は、９個の異なる値｛０，１，．．．，８｝のうちのいずれか１つをとることができるものと仮定される。
【００２４】
これに関連して、図４は、本発明の代表的な実施形態による、単一の領域８０のための符号化パターン（たとえば、モジュール１２によって生成されるパターン）を示す。この実施形態では、ページ１０の上の各領域は同じように符号化されるが、位置情報はその領域に特有である。その符号化パターンに含まれるのは、多数のレジストレーション符号化シンボル（たとえば、符号化シンボル８１）、ページ位置符号化シンボル（たとえば、符号化シンボル８２）、行位置符号化シンボル（たとえば、符号化シンボル８３）及び列位置符号化シンボル（たとえば、符号化シンボル８４）であり、図４において、それらの符号化シンボルはそれぞれ文字Ｒ、Ｎ、Ｙ及びＸによって示される。
【００２５】
レジストレーションパターン（Ｒ個の符号化シンボルから成る）は領域境界をマークし、各領域内の４つの内部固定位置を占有する。本発明人らは、レジストレーションの場所の値を予約する。この値は、これらの４つの内部固定場所内に書き込まれることになり、その領域内の他のいずれの場所にも書き込まれない。残りの８個の値は、位置情報そのものを符号化するために用いられる。便宜上、本発明人らは、数字８によってレジストレーション符号化シンボルを示し、８進数｛０，１，．．．，７｝によって情報符号化シンボルを示す。
【００２６】
レジストレーション符号化シンボル値８に関連付けられる印刷されたシンボルは、回転しても変化しないことが好ましい。たとえば、符号化シンボル値が（‘７６８特許の場合のように）異なるドット変位に関連付けられる場合には、レジストレーション符号化シンボル値は、中心変位に関連付けられることが好ましい。
【００２７】
あらゆる領域内の１５個の内部の場所は、その紙の上の領域の絶対位置を符号化するために用いられる。これらの場所では、８個の値｛０，１，．．．，７｝が許され、符号化シンボル当たり３ビットを与える。したがって、位置情報のために、あらゆる領域において、４５ビットが利用可能である。この実施形態において、本発明人らは、この情報を、それぞれが５要素ベクトル、すなわち全部で１５ビットを占有する、３つの番号に分ける。この実施形態では、３つの番号は、ページ番号、行番号及び列番号に対応する。より具体的には、この実施形態において、行番号及び列番号がそれぞれ占有するのは、多くても１５ビットである。最大数が、それよりも少ないビットしか占有しない場合には、行（列）番号は、対応するベクトルの最下位ビットに書き込まれ、そのベクトルの残りのビットがページ番号の一部を保持する。
【００２８】
あらゆる領域内の残りの６個の場所（６＝２５−４−３×５）は、位置情報内の誤りに対する保護を与えるパリティ値（又は他の誤り訂正符号化シンボル）を保持することが好ましい。２つのそのような誤り訂正符号化シンボルが、各５符号化シンボルベクトルに関連付けられ、リード・ソロモン誤り訂正符号の７符号化シンボルコードワードが生成される。本発明人らは、以下に、これに関して詳細に論じる。
【００２９】
図４のインデックスは、各コードワード内の符号化シンボルの順序を定義しており、ここで、０は最下位の位置情報符号化シンボルであり、４は最上位の位置情報符号化シンボルであり、５及び６はパリティ（又は他の誤り訂正）符号化シンボルのインデックスである。行番号は、１５ビットのＹデータ値の最下位ビット（Ｙ０〜Ｙ４）を占有し、列番号は、１５ビットのＸデータ値の最下位ビット（Ｘ０〜Ｘ４）を占有する。ページ番号は、１５ビットのＮデータ値（Ｎ０〜Ｎ４）を占有し、任意選択で、１５ビットのＹデータ値（Ｙ０〜Ｙ４）及び１５ビットのＸデータ値（Ｘ０〜Ｘ４）の最上位ビットも占有する。Ｎ５及びＮ６は、Ｎ０〜Ｎ４のための誤り訂正符号化シンボルであり、Ｙ５及びＹ６はＹ０〜Ｙ４のための誤り訂正符号化シンボルであり、Ｘ５及びＸ６はＸ０〜Ｘ４のための誤り訂正符号化シンボルである。Ｎ０〜Ｎ４はページ番号情報の少なくとも一部を含むことが好ましいが、以下にさらに詳細に説明されるように、本発明の特定の実施形態では、Ｘ０〜Ｘ４及びＹ０〜Ｙ４も、行番号に関する情報を含むことに加えて、ページ番号に関する情報も含むことに留意されたい。
【００３０】
この例では、印刷されたパターンのグリッド単位（これは、単一の符号化シンボルによって占有される空間のサイズにも対応する）は０．４２３３３ｍｍであるため、その領域の幅及び長さはそれぞれ、２．１１７ｍｍである。Ａ４ページサイズは、２９６ｍｍ×２１０ｍｍであり、それゆえ、１４０×１００の重なり合わない領域を含む。行番号を符号化するために８ビットが必要とされ、列番号の場合には７ビットが必要とされる。それゆえ、ページ番号のために３０ビットが残されるため、提案されている符号は、２30個までの異なるページを一意に特定することができる。
【００３１】
好ましい実施形態では、水平方向において隣接する２つの領域内の５符号化シンボル（１５ビット）Ｘベクトル（Ｘ０〜Ｘ４）は連続する番号を表し、垂直方向において隣接する２つの領域内の５符号化シンボル（１５ビット）Ｙベクトル（Ｙ０〜Ｙ４）は連続する番号を表す。さらに、垂直方向において隣接する２つの領域内の７シンボルＸベクトル（Ｘ０〜Ｘ６）は同一であり、水平方向において隣接する２つの領域内の７シンボルＹベクトル（Ｙ０〜Ｙ６）は同一である。
【００３２】
図３及び図４を比較すると、図４に示されるパターンはページ１０全体にわたって連続して繰り返されており、適切な行番号及び列番号が各領域内に符号化されており、ページ番号はページ１０上の各領域内で同一であることは理解されよう。十分に大きなＦＯＶを考えると、ページ１０上の位置を特定することはささいなことであろう。しかしながら、物理的な制約に起因して、一般的には、ＦＯＶはできる限り小さいことが好ましい。間もなく明らかになるように、単一の５×５視野ブロックを観測することさえできれば、本発明の技法は、回転又はオフセットがあっても位置を復号化することができる。
【００３３】
そのような小さなＦＯＶの限られる物の見え方から、符号化されたページ１０は最初に、領域間に明らかな境界がない符号化シンボル値の配列であるように見える。さらに、その配列の向きは、その時々で異なることがある。その状況が図５に示されており、図５は、符号化されたページ１０上の任意の位置におけるＦＯＶ１００を示す。この実施形態では、デジタルペン３５が使用されており、位置１０２はペン３５の先端を表し、ＦＯＶ１００は位置１０２と既知の関係にある。
【００３４】
上述されたように、ＦＯＶ１００は、５×５ＦＯＶブロック１０４全体を包含するほど十分に大きい。図５に示されるように、これは、種々のオフセットに対応するために、一般的にＦＯＶ１００をわずかに大きくすべきであることを意味する。
【００３５】
この時点で、この実施形態の列及び行に対応する線を有する仮想ラスタに基づいて、ＦＯＶ１００内の画像情報を潜在的に正しい向きに回転させることができる。しかしながら、この実施形態では、仮想ラスタ線だけでは、４つの潜在的な向きしか特定することができない。任意に１つが選択され、その後、ＦＯＶブロック１０４が、その中のレジストレーション符号化シンボルと共に、簡単に特定される。
【００３６】
そのようなレジストレーション符号化シンボルは、ページ１０の上の周辺領域に対して、ＦＯＶブロック１０４の正しい向き及びオフセットを一意に特定することができる。実際には、図４の４つのレジストレーション符号化シンボル（「Ｒ」で示される）のうちの任意の３つ（さらに言うと、任意の他の３つの同一直線上にないレジストレーション符号化シンボル）であれば、そのような向き及びオフセットを一意に特定するのに十分であることに留意されたい。以下にさらに詳細に説明されるように、本発明の実施形態の付加的なレジストレーション符号化シンボルは、特定の量の誤り訂正を提供する。図６は、正しい向きに回転した後のＦＯＶブロック１０４と共に、ＦＯＶ１００を示す。
【００３７】
図７は、当該視野ブロックが重なっている４つの領域１２１〜１２４に関連するＦＯＶブロック１０４を示す。上述されたように、レジストレーション符号化シンボルによって示されるオフセット情報は、そのような相対的な位置決めを提供する。
【００３８】
領域１２１〜１２４はそれぞれ、そのページ番号、行番号及び列番号を特定するための完全な情報を含むが、図８に示されるように、ここでは、そのような領域１２１〜１２４のいずれの１つに関しても、まだ完全な情報を持っていない。この時点では、ＦＯＶブロック１０４内の符号化シンボルしかわかっていない。
【００３９】
図９は、４つの重なった領域１２１〜１２４を示し、それぞれの符号化パターンが示されている。図９と図８とを比較し、上記で示された関係を記憶しておくことによって、領域１２１のための符号化シンボルを完全に埋めることができる。それを果たすための経過は以下のとおりである。
【００４０】
最初に、図９及び図１０Ａを比較すると、ＦＯＶブロック１０４内の符号化シンボル１３１は既に領域１２１内に存在する。したがって、それらのシンボルは、ＦＯＶブロック１０４から領域１２１内の適切な場所に単にコピーされ、その結果が図１１Ａに示されている。また、領域１２１内のレジストレーション符号化シンボルの決まった場所も予めわかっている。それゆえ、図１１Ａに示されるように、それらのシンボルも領域１２１に追加される。
【００４１】
図９に示される、Ｎ０．．．Ｎ６ページ番号指示子が、図１０Ｂにおいて要素１４１及び１４２として強調表示される。ページ番号指示子は、ページ１０全体を通じて同一である。したがって、再び図９を参照すると、ページ番号指示子１４１が領域１２４から領域１２１にコピーされ、ページ番号指示子１４２が領域１２３から１２１にコピーされ、最終的な結果は図１１Ｂに示す通りである。
【００４２】
再び図９を手短に参照すると、領域１２１及び１２３内の列（Ｘ）符号化シンボルは同一である。なぜなら、これらの２つの領域は同じ列内にあるからである。それゆえ、領域１２３内のＸ符号化シンボルを、領域１２１内の対応する場所にコピーすることができる。これが図１０Ｃ及び図１１Ｃに示される。各領域の最も右にある列内の誤り訂正符号化シンボルＸ５、Ｘ６の場所、及び欠けている符号化シンボルを埋めるために左上の重なった領域を選択するという事実は、合わせると、完成している領域において誤り訂正符号化シンボルＸ５、Ｘ６を入手することができるか、又はそうでない場合それらのシンボルを単に、その真下の領域からコピーすることができることを意味することに留意されたい。
【００４３】
領域１２１又は１２３の一部でない（この例では存在しない）任意の残りのＸ符号化シンボルに関しては、本発明人らは、領域１２２及び１２４内のそれぞれのＸ符号化シンボルに基づいて、すなわち、この実施形態では、領域１２２及び１２４内の対応するＸ符号化シンボルから１を引くことによって、それらのシンボルを計算するであろう。
【００４４】
同様に、再び図９を手短に参照すると、領域１２１及び１２２内の行（Ｙ）符号化シンボルは同一である。なぜなら、これらの２つの領域は同じ行内にあるからである。それゆえ、領域１２２内のＹ符号化シンボルを、領域１２１内の対応する場所にコピーすることができる。これが図１０Ｄ及び図１１Ｄに示される。各領域の最も下にある行内の誤り訂正符号化シンボルＹ５、Ｙ６の場所、及び欠けている符号化シンボルを埋めるために左上の重なった領域を選択するという事実は、合わせると、完成している領域において誤り訂正符号化シンボルＹ５、Ｙ６を入手することができるか、又はそうでない場合、それらのシンボルを単に、その右隣の領域からコピーすることができることを意味することに留意されたい。実際には、Ｙ６は各領域の最右下隅にあるため、埋められている領域内に存在するであろう。
【００４５】
領域１２１又は１２２の一部でない（この例では存在しない）任意の残りのＹ符号化シンボルに関しては、本発明人らは、領域１２３及び１２４内のそれぞれのＹ符号化シンボルに基づいて、すなわち、この実施形態では、領域１２３及び１２４内の対応するＹ符号化シンボルから１を引くことによって、それらのシンボルを計算するであろう。
【００４６】
ここで、本発明人らは、対応する後続の位置ベクトル（すなわち、適宜、後続の列又は行内）のそれぞれの数字に基づいて、位置ベクトル内の欠けている数字を計算する方法の一般的な解法を定式化する。ＦＯＶ１０４によって重ね合わせられる左上の領域をいつでも完成させる（又は再構成する）規則が確立される場合、以下のようにして、（同じ列又は行内にそれぞれ、対応する列符号化シンボル又は行符号化シンボルが存在しないために）単にコピーすることができない任意の位置符号化シンボルを求めることができる。
【００４７】
Ｘi＝Ｘi,J．．．Ｘi,0によって、小さい方の位置ベクトル表現８進数を表し、Ｘi+1＝Ｘi+1,J．．．Ｘi+1,0によって、適用可能な連続する位置ベクトル表現８進数を表す。インデックスｊ∈｛０，．．．Ｊ｝毎に、Ｘi,j又はＸi+1,jのいずれかを入手することができる。その数字が８進数に基づく、ＸiのＪ個全ての数字を求めるための方法は、以下のように与えられる；
入力：インデックスｊ∈｛０，．．．Ｊ｝毎に、８進数に基づいて、Ｘi,j又はＸi+1,jのいずれかを入手することができる。
出力：２つの連続する８進数Ｘi＝Ｘi,J．．．Ｘi,0及びＸi+1＝Ｘi+1,J．．．Ｘi+1,0。
方法：ｊ＝０，．．．，Ｊの場合に以下の演算を繰り返す；
Ｘi,j-1．．．Ｘi,0が解像されるが、Ｘi,jが入手することができない場合：
・Ｘi,j-1．．．Ｘi,0が全て「７」である場合（詳細には、ｊ＝０である場合）、
・Ｘi+1,j＝０である場合には、Ｘi,j＝７を設定する；
・Ｘi+1,j≠０である場合には、Ｘi,j＝Ｘi+1,j−１を設定する；
・そうでない場合には、Ｘi,j＝Ｘi+1,j。
【００４８】
たとえば、Ｘi＝５□３□□及びＸi+1□０□２０である場合には、Ｘi＝５０３１７及びＸi+1＝５０３２０である。同様の方法を用いて、再構成される領域から欠けているＹ位置符号化シンボルが求められる。図４において提案される具体的な符号化パターンによれば、左上の重ね合わせられた領域をいつでも再構成するという規則と合わせて、再構成されている領域においていつでもＸ3、Ｘ4が入手可能であるか、又はその真下の領域から直にコピーすることができ（それらが、そのパターンの最も右の列にあるため）、且つ再構成されている領域においていつでもＹ2、Ｙ3、Ｙ4が入手可能であるか、又はその右隣の領域から直にコピーすることができる（それらが、そのパターンの最も下の行にあるため）ことが確実になる。それゆえ、この実施形態では、上記の方法を適用して、多くてもＸ2Ｘ1Ｘ0及びＹ1Ｙ0しか計算する必要がない。
【００４９】
領域サイズが必ずしも５×５でないか、又は取り得る符号化シンボル値の数が必ずしも９ではない、さらに一般的な場合について考える。領域設計では、行番号に対応する全ての誤り訂正符号化シンボルが単一の行内に（たとえば、その領域の最上端又は最下端に）配置され、列番号に対応する全ての誤り訂正符号化シンボルが単一の列内に（たとえば、その領域の左端又は右端に）配置されることが好ましい。このようにして、ＦＯＶブロック内の種々の誤り訂正符号化シンボルは常に、単一の行番号及び単一の列番号に対応する。ＦＯＶが種々の領域の部分を覆うときには必ず、計算されるべき行値及び列値は、誤り訂正符号化シンボルに対応する。
【００５０】
換言すると、位置情報符号化シンボル（上記の例では、コードワード毎に５つの符号化シンボル）から誤り訂正符号化シンボル（上記の例では、コードワード毎に２つの符号化シンボル）を分離し、再構成する領域を選択すると共に、符号化パターン内に誤り訂正符号化シンボルを入れる場所を選択することは、合わせて、再構成される領域のための誤り訂正符号化シンボルの全てが視野内に存在すること、すなわち必要に応じて正しい位置にコピーすることしか必要としないことを確実にする。そのような領域及び配置を適切に選択することによって、ＦＯＶブロックは、任意の単一の領域よりも大きくする必要がなくなる。
【００５１】
図４において提案される具体的な符号化パターンでは、行誤り訂正符号化シンボルは最も下の行内にあり、列誤り訂正符号化シンボルは最も右の列内にある。向きを補正されたＦＯＶでは、誤り訂正符号化シンボルは常に、左上の領域（たとえば、図７及び図８の領域１２１）の座標に対応する。これは、上記の例において、我々の復号化技法が領域１２１を完全に再構成するためである。
【００５２】
上記で与えられた例では、領域は正方形である。しかしながら、本発明は正方形の領域に限定されないことは理解されたい。上記の概念は、長方形の領域、及び他の形状の領域にも当てはまる。
【００５３】
図１２は、本発明の典型的な実施形態による、位置特定復号化処理を説明するフローチャートを示す。最初に、ステップ１６１では、デジタルペン３５又は他のセンサデバイスから、画像情報が得られる。
【００５４】
ステップ１６２では、画像情報のＦＯＶを回転して、正しい向きに向ける。上記で説明されたように、このステップは、レジストレーション符号化シンボル（それは、この実施形態では、回転しても変化しない）を特定することを含む。このために、たとえば、仮想ラスタ線に基づいて、最初に、潜在的な向きが求められることが好ましい。レジストレーション符号化シンボルとして特定されている符号化シンボルがひとたび特定されると、ＦＯＶブロックに対応する配列を生成し、たとえば、レジストレーション符号化シンボルが特定された場所を示す「１」と、残りの各位置内にある「０」で、それらの位置を指示することができる。正しい向きにあり、オフセットがないＦＯＶブロック１８０の場合に、レジストレーション符号化シンボルが１８１であり、非レジストレーション符号化シンボル１８２である例が、図１３に示される。
【００５５】
上述されたように、誤りがないものと仮定して、正しいオフセット及び向きを一意に求めるために、３つのレジストレーション符号化シンボルしか必要とされない。実際には、レジストレーション符号化シンボルとして特定される符号化シンボルのうちのいくつかは、実際にはレジストレーション符号化シンボルでないことがあるか、又は本当はレジストレーション符号化シンボルであるものが、そのように特定されないことがある。そのような誤りは、ほこり、正規の場所から外れたマーキング等に起因することがある。たとえば、図１３に示されるように、１つの余分なレジストレーション符号化シンボルを追加することによって、１つのそのような誤りがある場合であっても、向き及びオフセットを正しく特定することができるようになることがわかっている。
【００５６】
生成されたマップ（たとえば、図１３に示される）を、全ての取り得る向き及びオフセットのマップと比較することによって、向き及びオフセットが求められる。上記で与えられた例では、２５（５×５）の潜在的なオフセットがあり、仮想ラスタ線の存在に起因して、４つの潜在的な回転（０°、９０°、１８０°、２７０°）だけがあり、それは全部で１００通りの取り得る組み合わせがあることを意味する。参照される比較は、生成されたマップと１００個の異なる潜在的なマップとの間のハミング距離を計算すること（すなわち、その値が異なる、２つのマップ内の対応する位置の数をカウントすること）及び、最小ハミング距離を有する潜在的なマップ（その対応するオフセット及び回転を有する）を選択することを含むことが好ましい。適切な仮定のもとで、レジストレーションパターンのために用いられる上記の誤り訂正符号が見受けられ、レジストレーション符号の復号化誤り確率を９６．６％だけ低減することができる。
【００５７】
２つ以上の候補がある場合には、又は観測されたパターンから最も近いテンプレートまでの距離が長すぎる（たとえば、２以上）と見なされる場合には、そのデータは十分な信頼性がないため、その位置特定において誤りが宣言される。１つの候補が見つけられたものと仮定すると、ＦＯＶブロックは、上記のように単に回転し、領域境界に対して、そのオフセット（たとえば、図７及び図８において示される）が求められる。
【００５８】
上記の回転及びオフセットを特定するための技法は、ＦＯＶマップを、１００個の正当なＦＯＶマップとそれぞれ比較する。それゆえ、符号化シンボル比較の数は２５００回になることがある。実際の実施態様では、以下の方法は、さらに効率的にすることができる。所与のＦＯＶ内のレジストレーション符号化シンボルの数をカウントする。その数が５よりも大きいか、又は３よりも小さい場合には、そのレジストレーションパターン内に２つ以上の誤りが存在するため、復号化するのを避ける。
【００５９】
そうでない場合には、図３に示されるような、中央に配置されるレジストレーションパターンを回転させることによって得られる４つのレジストレーションテンプレートについて考える。ＦＯＶ内の１つのレジストレーションシンボルを選択し、それを、回転したテンプレートの１６個の取り得るレジストレーションシンボルの場所のうちの１つ（４回転×４つのレジストレーションの場所のそれぞれ）と位置合わせする。回転したテンプレートのうちの１つにおいて３つ又は４つのＦＯＶレジストレーション符号がレジストレーションの場所と重なり合う場合には、一致が得られる。ＦＯＶシンボルのうちのいずれかが５×５テンプレートブロックの外側にある場合には、それは再び、同じ回転したテンプレートの他の側にも繰返し現れる。一致が見つけられない場合には、別のＦＯＶレジストレーションシンボルを同じようにして調べる。多くても１つのシンボル読取り誤りしか生じなかった場合には、調べられた２つのシンボルのうちの一方（又は両方）が単一のテンプレートと一致する。図１３のパターンは、単一の一致しかないことを確実にする。ここで必要とされるシンボル比較の回数は、多くても２５＋２×１６×４＝１５３である。必要とされる回転は、テンプレート回転に対応する。シフトは、選択されたＦＯＶシンボルの場所を、中央に配置されるテンプレート内の対応する場所と比較することによって見つけられる。
【００６０】
図１２に戻ると、ステップ１６４では、画像情報が位置符号化シンボルに変換される。‘７６８特許の技法が用いられているものと仮定すると、印刷されたシンボル（たとえば、ドット）をＦＯＶブロックの位置符号化シンボルに変換するために必要とされるのは、名目的な場所からの距離を特定することだけである。
【００６１】
最後に、ステップ１６５では、位置符号化シンボルが復号化されて、デジタルペン３５（又は他のセンサデバイス）の位置が特定される。上述されたように、そのような位置を求めるために、好ましい技法は、最初に、１つの領域全体のための符号化パターンを再構成することである。その情報がわかると、その領域の位置を直に読み取ることができ、そこから、ＦＯＶブロックの位置（オフセット情報に基づく）、及びペン先端の位置（その先端とＦＯＶとの間の既知の関係に基づく）も容易に計算することができる。
【００６２】
１つの領域全体の再構成は上記で詳細に説明されているため、ここでは繰り返されない。いかなる検出誤りもなければ、位置符号化シンボルから位置情報を読み取ることは簡単であろう。誤りが存在することがあるものと仮定して、以下の説明は、誤り訂正符号化シンボルを構成する方法、及び一定の誤りが存在する場合であっても、正しい結果を生成するように、結果として生成される位置符号化シンボルを復号化する方法を記述する。本発明の好ましい実施形態では、リード・ソロモン符号化／復号化技法が用いられる。
【００６３】
その一般的な形式では、リード・ソロモン技法は、１つのブロックのメッセージを、有限体にわたってプロットされる多項式内の点として符号化する。その多項式の係数はブロックのデータ値である。そのプロットは係数を余分に求め、それらの係数は後に、プロットされた点のサブセットから再生することができる。間隙を補間することによって曲線を補正することができるのと同じ意味において、リード・ソロモン符号は、データブロック内の１つ又は複数の誤りを埋めて、元の曲線を描いた多項式の係数を再生することができる。
【００６４】
上記の例では、情報符号化シンボルは、サイズ８の記号体系から、その値をとる。それゆえ、本発明人らは、ＧＦ（８）で表される、サイズ８の有限体にわたって１つの誤り訂正符号化シンボルを用いて作業することにした。その体の定義が以下のように与えられる。本発明人らは、シンボル｛０，．．．，７｝を、８進数及び体要素の両方として用いるが、８進数算術と体算術とを区別する。８進数算術では、たとえば、５＋１＝６であるのに対して、ＧＦ（８）の付加的な規則は、１０１＋００１＝１００を意味する。本発明人らは、８進数算術を用いて、情報符号化シンボルＮ0，．．．，Ｎ4、Ｘ0，．．．，Ｘ4及びＹ0，．．．，Ｙ4を求める。ＧＦ（８）算術は、パリティ（又は誤り訂正）符号化シンボルＮ5、Ｎ6、Ｘ5、Ｘ6及びＹ5、Ｙ6を求めるために用いられる。それらは、以下に記述される技法に基づいて計算される。復号化するときに、本発明人らは、情報及び誤り訂正符号化シンボルを再生するために、再びＧＦ（８）算術を用いる。
【００６５】
本発明人らは、異なり、且つ独立している３つのコードワードにおいて位置データを符号化する。しかしながら、それらのコードワードは、同じ符号構造、すなわちＧＦ（８）にわたる［７，５，３］リード・ソロモン符号に属する。符号長は７であり、符号次元は５であり、最小ハミング距離は３である。したがって、各コードワードは、７つの符号化シンボル、すなわち５つの情報（又はメッセージ）符号化シンボル（Ｎ0，．．．，Ｎ4、Ｘ0，．．．，Ｘ4、Ｙ0，．．．，Ｙ4のいずれか）及び２つのパリティ（又は誤り訂正）符号化シンボル（それぞれ、Ｎ5、Ｎ6、又はＸ5、Ｘ6又はＹ5、Ｙ6）から成る。最小距離３は、符号の長さ及び次元を与えた場合に取り得る最大距離である。本発明人らは、組織的［７，５，３］リード・ソロモン符号を選択しており、その生成多項式は、以下のとおりである：
ｇ（ｘ）＝（ｘ−１）（ｘ−α）＝ｘ2＋α3ｘ＋α
ただし、αはＧＦ（８）の原始元である。
【００６６】
ページ１０上の単一の領域の全てのシンボルを解像した後に（たとえば、上記の手順を用いる）、本発明人らは、存在することがある誤りを訂正するために、リード・ソロモン復号化技法を適用する。本発明人らは、後に規定される復号化技法を個別に用いて、３つのコードワードをそれぞれ復号化する。
【００６７】
この実施形態におけるリード・ソロモン符号は、３の最小ハミング距離を有し、それゆえ、その符号によって、１つのコードワード内で任意の単一の誤りを訂正することができるようになる。それゆえ、その領域内にある訂正可能な誤りパターンは、２つの誤りが同じコードワード内に入らない限り、１つ〜３つの欠陥のある符号化シンボルを有する全てのパターンを含む。
【００６８】
重み２以上の誤りパターンが、元のコードワードを別のコードワードに変換する場合、又はコードワードからハミング距離１にあるベクトルに変換する場合があることに留意されたい。それらの場合に、復号化技法は、間違ったコードワードを生成することがある。しかしながら、そのような場合に陥る確率は、誤りがないか、又は１つの誤りを有する元のコードワードを受信する確率よりもはるかに小さい。より具体的には、適切な仮定を用いるとき、そのような誤り訂正は、ＦＯＶ内で単一の完全な領域が捕捉される場合には、９８．６９％だけ誤りの確率を低減し、さらに一般的な場合には少なくとも９５％だけ低減することがわかっている。
【００６９】
１つのフィールド（ただ１組の要素の代わりに）で機能することによって、要素間で算術演算することができるようになる。そのフィールドは加法及び乗法の下で閉じており、これらの２つの演算は可換且つ結合的である（分配法則も当てはまる）。その体は、０及び１で表される２つの特殊な要素を有する。全てのフィールド要素αは加法的な逆元を有し（α＋（−α）＝０）、０を除く全ての要素は、乗法的な逆元も有する（α×α-1＝１）。
【００７０】
８つの要素から成る全ての有限体は互いに同型である。こうして、ＧＦ（８）で表される、サイズ８のガロア体は固有であると見なされる。８つのフィールド要素の場合に２つの一般的な表記法がある。第１の表記法は、長さ３の２値ベクトルを用いる。この表記によれば、加法がＧＦ（２）に関する簡単なベクトル加法であるため（たとえば、００１＋１０１＝１００）、要素加法を計算するのが非常に容易になる。第２の表記法は、フィールドの乗法群を生成する、原始元αの累乗を使用する。したがって、フィールド要素は｛０，１＝α0、α＝α1，α2，α3，α4，α5，α6｝で表される。この表記法によれば、要素を簡単に乗算することができるようになる。すなわち、０以外の要素を乗算し、それらの累乗を足して、７を法とする和をとることができるようになる。
【００７１】
２値ベクトル表現は、フィールド要素１、α及びα2の一次結合に対応する。ここで、αは原始多項式ｘ3＋ｘ＋１＝０の根である。全てのフィールド要素を、そのような一次結合によって記述することができる。たとえば、α3＝−α−１＝α＋１である（ＧＦ（２）に関して−ｘ＝ｘであることに留意されたい）。それぞれの一次結合を記述する２値ベクトルは０１１である。別の原始多項式ｘ3＋ｘ2＋１＝０を用いて、体ＧＦ（８）を定義することができる。その際、異なる表を用いて、２つの要素表現間が結び付けられる。しかしながら、結果として生成されるフィールドは、上記で定義されたフィールドに同型である。
【００７２】
上記の符号パラメータ及び生成多項式を与えるとき、符号化規則は以下のようになる：
１．５つのメッセージシンボルをｍ4ｍ3ｍ2ｍ1ｍ0によって表す。メッセージ多項式をｍ（ｘ）＝ｍ4ｘ4＋ｍ3ｘ3＋ｍ2ｘ2＋ｍ1ｘ＋ｍ0と定義する。
【００７３】
２．ｘ2・ｍ（ｘ）を生成多項式ｇ（ｘ）で割る。ｐ（ｘ）＝ｐ1ｘ＋ｐ0を剰余多項式とする。
【００７４】
３．出力コードワードは、（ｃ6，ｃ5，ｃ4，ｃ3，ｃ2，ｃ1，ｃ0）＝（ｍ4，ｍ3，ｍ2，ｍ1，ｍ0，ｐ1，ｐ0）である。
【００７５】
上記の符号化規則は、符号が全てのベクトル
【００７６】
【数１】
【００７７】
のセットであることを意味し、その場合に、フィールド要素１及びαは対応する多項式
【００７８】
【数２】
【００７９】
の根である。
上記を満たすベクトル
【００８０】
【数３】
【００８１】
はコードワードと呼ばれる。この符号は、有限フィールドＧＦ（８）に関する線形部分空間である。部分空間次元は５である。
【００８２】
コードワード成分（すなわち、符号化シンボル）のインデックスは、上記の符号インデックスと一致しないことに留意されたい。詳細には、パリティ符号化シンボルＮ5、Ｎ6（又はＸ5、Ｘ6又はＹ5、Ｙ6）はｃ1、ｃ0に対応する。
【００８３】
その領域が訂正可能な誤りパターンを含むものと仮定する。以下のベクトルが、検出デバイスによって捕捉されるような、Ｎ、Ｘ又はＹベクトルのうちの１つに関連付けられるものとする。
【００８４】
【数４】
【００８５】
以下に規定される復号化アルゴリズムは、
【００８６】
【数５】
【００８７】
が元のコードワードであるか、又はハミング重み１の元のコードワード
【００８８】
【数６】
【００８９】
と誤りベクトル
【００９０】
【数７】
【００９１】
との一次結合
【００９２】
【数８】
【００９３】
のいずれかである場合には、元のコードワードを見つける。
入力：ＧＦ（８）に関するベクトル
【００９４】
【数９】
【００９５】
出力：そのようなコードワードが存在する場合には、
【００９６】
【数１０】
【００９７】
からのハミング距離≦１におけるコードワード
【００９８】
【数１１】
【００９９】
方法：体要素１及びαにおいて多項式
【０１００】
【数１２】
【０１０１】
を数値計算する。
１．υ（１）＝υ（ａ）＝０である場合には、
【０１０２】
【数１３】
【０１０３】
を返す。
２．υ（１）≠０且つυ（α）≠０である場合には、ｊ∈｛０，．．．，６｝を見つける。ここで、αj＝υ（α）／υ（１）である。第ｊの成分υjから値υ（１）を引くことによって、
【０１０４】
【数１４】
【０１０５】
から
【０１０６】
【数１５】
【０１０７】
を得る。
３．υ（１）＝０であるが、υ（α）≠０である場合、又はυ（１）≠０であるが、υ（α）＝０である場合には、いかなるコードワードも返さない。
【０１０８】
図６の事例１では、
【０１０９】
【数１６】
【０１１０】
がコードワードであるため、本発明人らは、その符号化シンボルのいずれも変更しない。事例２では、第ｊの成分の変更が、入力ベクトル
【０１１１】
【数１７】
【０１１２】
からハミング距離１にある唯一のコードワードを与える。事例３では、
【０１１３】
【数１８】
【０１１４】
はＣ内のいずれのコードワードからもハミング距離２以上にある。その復号化技法は、そのような事例においていかなる訂正も規定しない。それらの事例は訂正することができないと見なされる。
【０１１５】
上記の符号化パターンによれば、流動的に位置を求めることができるようになる。換言すると、任意の位置を、完全に１つの領域を含むＦＯＶだけでなく、単一の領域と同じサイズを有する任意のＦＯＶから解像することができる。同時に、そのパターンは、符号化シンボル検出誤りに対して、ある程度の保護を与える。
【０１１６】
特定の事例では、印刷されたシンボルの繰返しパターンを除去することが望ましい。この目的を果たすために、本発明の代替的な一実施形態では、種々の領域が、行（又は列）番号を保持するシンボルが２つの行（列）に集中しないように、たとえば、隣接する行（列）内に集中しないように編成される。
【０１１７】
他の実施形態は、ページ番号の繰返しを解消しようと試みる。これを果たすために、本発明人らは、Ａ9個の要素の擬似ランダムな置換に応じて、各ページ番号を置き換える。隣接する領域のために、且つ相対的に近い領域のために異なる置換が選択される場合には、領域の行又は列を分割していることが、裸眼では区別しにくくなるはずである。
【０１１８】
復号化するために、所与のＦＯＶにおいて符号化シンボル毎に用いられるマッピングを容易に決定することができるはずである。それゆえ、本発明人らは、この領域に書き込まれる行値及び列値に基づいて領域置換を選択する。復号化するとき、ページ番号を復号化する前に、行番号及び列番号を復号化する。これは、３つの異なる領域コードワードの復号化処理の間に以前にあった独立性を解消する。行番号及び列番号の復号化に誤りがあれば、典型的には、ページ番号が誤っていることを意味するであろう。
【０１１９】
本発明人らは、領域毎に置換を定義するために以下の具体的な技法を提唱する。ある一定の数ｎの置換をランダムに生成し、その置換を表に入れておく。数ｎは、行又は列当たりの領域の数に近い素数のうちの最も大きな素数であることが好ましい。Ａ４ページの場合、本発明人らは、ｎ＝２５１を使用する。行ｒ及び列ｃに或る領域を与えるとき、以下のインデックスにおいて置換が実施される。
【０１２０】
【数１９】
【０１２１】
式中、ｐ1及びｐ2は２つの小さな素数、たとえば２及び３である。ｐ1及びｐ2はｎを分割しないため、長方形グリッド効果が低減されるはずである。インデックスｉはｒ＋ｃ又はｒ−ｃの関数ではないため、対角線効果も生み出されないはずである。
【０１２２】
［システム環境］
一般的に言うと、本明細書において記述される方法及び技法の概ね全てを、汎用コンピュータシステムを使用して実施することができる。そのようなコンピュータは典型的には、たとえば、互いに、たとえば共通バスを介して相互接続される以下の構成要素のうちの少なくともいくつかを含むであろう：１つ又は複数の中央演算装置（ＣＰＵ）、リードオンリーメモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、他のデバイスとのインターフェースを構成し、且つ１つ又は複数のネットワークに接続するための入力／出力ソフトウエア又は回路（ネットワークはさらに、本発明の多くの実施形態において、インターネットに、又は任意の他のネットワークに接続する）、ディスプレイ（陰極線管ディスプレイ、液晶ディスプレイ、有機発光ディスプレイ、高分子発光ディスプレイ又は任意の他の薄膜ディスプレイ等）、他の出力デバイス（１つ又は複数のスピーカ、ヘッドホンセット又はプリンタ等）、１つ又は複数の入力デバイス（マウス、タッチパッド、タブレット、タッチセンシティブディスプレイ若しくは他のポインティングデバイス、キーボード、マイクロホン又はスキャナ等）、大容量記憶ユニット（ハードディスクドライブ等）、リアルタイムクロック、取外し可能記憶読出し／書込みデバイス（ＲＡＭ、磁気ディスク、磁気テープ、光磁気ディスク、光ディスク等からの読出し、又はそれらへの書込み用等）、及びモデム（モデムも、ダイヤルアップ接続を介して、インターネットに、又は任意の他のコンピュータネットワークに接続することが好ましい）。動作時に、そのような汎用コンピュータによって実行される限り、上記の方法を実施する処理ステップは典型的には最初に大容量記憶装置（たとえば、ハードディスク）に格納され、ＲＡＭにダウンロードされ、その後、ＲＡＭから出してＣＰＵによって実行される。
【０１２３】
本発明を実施する際に用いるのに適しているコンピュータは、種々のベンダから入手することができる。しかしながら、タスクのサイズ及び複雑さに応じて、様々なタイプのコンピュータが用いられることがある。適切なコンピュータは、メインフレームコンピュータ、マルチプロセッサコンピュータ、ワークステーション、パーソナルコンピュータ、及びＰＤＡ等のさらに小型のコンピュータ、無線電話又は任意の他の機器又はデバイスを含み、スタンドアロンで用いられるか、ネットワークに有線で接続されるか、又はネットワークに無線で接続される。さらに、上記で汎用コンピュータシステムが記述されてきたが、代替的な実施形態では、その代わりに（又は、それに加えて）専用コンピュータが用いられる。詳細には、上記の機能のいずれかを、ソフトウエア、ハードウエア、ファームウエア又はこれらの任意の組み合わせで実現することができ、既知の工学上のトレードオフに基づいて特定の実施態様が選択される。これに関連して、上記の機能は主に固定された論理的ステップを通じて実施され、それゆえ、当該技術分野においてよく知られているように、プログラミング（たとえば、ソフトウエア又はファームウエア）、論理部品の適切な構成（ハードウエア）、又は２つの任意の組み合わせを通じて果たすことができることに留意されたい。
【０１２４】
本発明は、本発明の方法を実行するためのプログラム命令が格納される機械読取り可能媒体にも関連することは理解されたい。そのような媒体は、一例として、磁気ディスク、磁気テープ、ＣＤ ＲＯＭ及びＤＶＤ ＲＯＭのような光学的に読取り可能な媒体、ＰＣＭＣＩＡカードのような半導体メモリ等を含む。いずれの場合でも、媒体は、小さなディスク、ディスケット、カセット等の持ち運びできる商品の形をとることがあるか、又は、コンピュータ内に設けられるハードディスクドライブ、ＲＯＭ又はＲＡＭのような、相対的に大きいか、又は動かすことができない商品の形をとることがある。
【０１２５】
上記の説明は主に電子コンピュータに重点を置いている。しかしながら、代わりに、電子、光学、生物又は化学処理の任意の組み合わせを利用するコンピュータのような、任意の他のタイプのコンピュータが用いられることがあることは理解されたい。
【０１２６】
[付加的な検討事項]
本発明は主に、マークされた１枚の紙の上でデジタルペンの位置を特定することとの関連で上記で説明されているが、本発明は他の位置特定問題にも適用することができることは理解されたい。たとえば、別の用途は、デジタルマウスの位置を特定することであり、本発明による位置情報で符号化されているマウスパッド上で高い分解能を有する。
【０１２７】
本発明のいくつかの異なる実施形態が上述され、そのような実施形態はそれぞれ、特定の特徴を含むように記述されている。しかしながら、任意の単一の実施形態の説明との関連で記述される特徴は、その実施形態には限定されず、他の実施形態のうちのいずれかの種々の組み合わせに含まれるか、その組み合わせで構成されることができることが意図されていることは、当業者には理解されよう。
【０１２８】
同様に、上記の説明では、機能はいくつかの場合に、特定のモジュール又は構成要素に帰する。しかしながら、機能は一般的には、所望によって、任意の異なるモジュール又は構成要素の中で分散させることができ、場合によっては、特定の構成要素又はモジュールが全く不要になるか、あるいは新たな構成要素又はモジュールを追加する必要がある。厳密な機能分散は、本発明の具体的な実施形態を参照しながら、既知の工学上のトレードオフに従って行なわれることが好ましいことは、当業者には理解されよう。
【０１２９】
こうして、本発明は、その例示的な実施形態及び添付の図面との関連で詳細に説明されてきたが、本発明の精神及び範囲から逸脱することなく、本発明の種々の改変及び変更を果たすことができることは当業者には明らかであろう。したがって、本発明は、図示され、上記で説明されたのと全く同じ実施形態には限定されない。むしろ、本発明の精神から逸脱しない全てのそのような変形は、添付の特許請求の範囲によってのみ制限されるような、本発明の範囲内にあるものと見なされることが意図されている。
【特許請求の範囲】
【請求項１】
表面上のデバイスの位置を一意に特定する方法であって、
位置情報で符号化されている物理的な表面の近くに配置されるセンサから画像情報を受信し、
前記画像情報を位置符号化シンボルのパターンに変換し、
誤り訂正技法を用いることによって、前記位置符号化シンボルのパターンを位置に復号化することを含むことを特徴とする方法。
【請求項２】
前記位置符号化シンボルは行番号指示子、列番号指示子、及びページ番号指示子を含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記位置符号化シンボルのパターンは、前記行番号指示子、前記列番号指示子及び前記ページ番号指示子のうちの少なくとも１つのための少なくとも１つの誤り訂正符号化シンボルを含むことを特徴とする請求項２に記載の方法。
【請求項４】
前記画像情報内のレジストレーション符号化シンボルに基づいて、前記画像情報の正しい向きを特定するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記変換するステップの前に、前記画像情報を前記正しい向きに回転させるステップをさらに含むことを特徴とする請求項４に記載の方法。
【請求項６】
前記レジストレーション符号化シンボルは、前記レジストレーション符号化シンボルのうちの１つが欠けているか、又は誤って検出される場合であっても、前記正しい向きを特定することができるようにする少なくとも１つの冗長な符号化シンボルを含むことを特徴とする請求項４に記載の方法。
【請求項７】
前記画像情報は印刷されたマークのパターンを含み、前記位置符号化シンボルは、マークから成る固定グリッド内の中間のグリッドロケーションに基づいて特定されることを特徴とする請求項１に記載の方法。
【請求項８】
前記誤り訂正技法は、リード・ソロモン符号の復号化を含むことを特徴とする請求項１に記載の方法。
【請求項９】
複数の位置符号化シンボルから、指定された距離メトリックに従って、最小距離に対応する取り得る位置指示子を見つけることによって、前記複数の位置符号化シンボルが、１組の取り得る位置指示子からの１つの位置指示子に復号化されることを特徴とすることを特徴とする請求項１に記載の方法。
【請求項１０】
前記指定された距離メトリックはハミング距離を含むことを特徴とする請求項９に記載の方法。
【請求項１１】
前記位置情報は、前記物理的な表面上の区別される領域に符号化され、前記領域はそれぞれ、前記物理的な表面上の前記領域の場所を一意に特定するのに十分な位置情報を有することを特徴とする請求項１に記載の方法。
【請求項１２】
前記画像情報内のレジストレーション符号化シンボルに基づいて、周辺領域に対して、前記画像情報の正しいオフセットを特定するステップをさらに含むことを特徴とする請求項１１に記載の方法。
【請求項１３】
前記画像情報は、前記物理的な表面上の複数の異なる領域の各領域の少なくとも一部に重なる視野に対応することを特徴とする請求項１１に記載の方法。
【請求項１４】
前記復号化するステップは、前記重ね合わせられる領域のうちの第２の領域内の位置情報に基づいて、前記重ね合わせられる領域のうちの第１の領域から欠けている位置情報を補うことを含むことを特徴とする請求項１３に記載の方法。
【請求項１５】
前記領域は連続しており、且つ重なり合わないことを特徴とする請求項１１に記載の方法。
【請求項１６】
位置情報で符号化される基板であって、
その表面がマークのパターンを刻印される基板を含み、
前記マークはそれぞれ、１つの対応する位置符号化シンボルに一対一の関係で復号化することができ、それによって、位置符号化シンボルの対応するパターンが生成され、
前記位置符号化シンボルの前記パターンは複数の領域を含み、
前記各領域内の前記位置符号化シンボルは、前記基板上の前記領域の場所を一意に特定し、
前記位置符号化シンボルは誤り訂正符号で符号化されることを特徴とする基板。
【請求項１７】
各領域は、前記各領域の正しい向きを特定するための複数のレジストレーション符号化シンボルも含むことを特徴とする請求項１６に記載の基板。
【請求項１８】
前記レジストレーション符号化シンボルは、前記レジストレーション符号化シンボルのうちの１つが誤って検出される場合であっても、前記正しい向きを特定することができるようにする少なくとも１つの冗長な符号化シンボルを含むことを特徴とする請求項１７に記載の基板。
【請求項１９】
位置情報で符号化される基板であって、
その表面がマークのパターンを刻印される基板を含み、
前記マークは、位置符号化シンボルの１つの対応するパターンに一意に復号化することができ、
前記位置符号化シンボルは誤り訂正符号で符号化されることを特徴とする基板。
【請求項２０】
前記複数の位置符号化シンボルはリード・ソロモン符号で符号化されることを特徴とする請求項１９に記載の基板。
【請求項１】
表面上のデバイスの位置を一意に特定する方法であって、
位置情報で符号化されている物理的な表面の近くに配置されるセンサから画像情報を受信し、
前記画像情報を位置符号化シンボルのパターンに変換し、
誤り訂正技法を用いることによって、前記位置符号化シンボルのパターンを位置に復号化することを含むことを特徴とする方法。
【請求項２】
前記位置符号化シンボルは行番号指示子、列番号指示子、及びページ番号指示子を含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記位置符号化シンボルのパターンは、前記行番号指示子、前記列番号指示子及び前記ページ番号指示子のうちの少なくとも１つのための少なくとも１つの誤り訂正符号化シンボルを含むことを特徴とする請求項２に記載の方法。
【請求項４】
前記画像情報内のレジストレーション符号化シンボルに基づいて、前記画像情報の正しい向きを特定するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記変換するステップの前に、前記画像情報を前記正しい向きに回転させるステップをさらに含むことを特徴とする請求項４に記載の方法。
【請求項６】
前記レジストレーション符号化シンボルは、前記レジストレーション符号化シンボルのうちの１つが欠けているか、又は誤って検出される場合であっても、前記正しい向きを特定することができるようにする少なくとも１つの冗長な符号化シンボルを含むことを特徴とする請求項４に記載の方法。
【請求項７】
前記画像情報は印刷されたマークのパターンを含み、前記位置符号化シンボルは、マークから成る固定グリッド内の中間のグリッドロケーションに基づいて特定されることを特徴とする請求項１に記載の方法。
【請求項８】
前記誤り訂正技法は、リード・ソロモン符号の復号化を含むことを特徴とする請求項１に記載の方法。
【請求項９】
複数の位置符号化シンボルから、指定された距離メトリックに従って、最小距離に対応する取り得る位置指示子を見つけることによって、前記複数の位置符号化シンボルが、１組の取り得る位置指示子からの１つの位置指示子に復号化されることを特徴とすることを特徴とする請求項１に記載の方法。
【請求項１０】
前記指定された距離メトリックはハミング距離を含むことを特徴とする請求項９に記載の方法。
【請求項１１】
前記位置情報は、前記物理的な表面上の区別される領域に符号化され、前記領域はそれぞれ、前記物理的な表面上の前記領域の場所を一意に特定するのに十分な位置情報を有することを特徴とする請求項１に記載の方法。
【請求項１２】
前記画像情報内のレジストレーション符号化シンボルに基づいて、周辺領域に対して、前記画像情報の正しいオフセットを特定するステップをさらに含むことを特徴とする請求項１１に記載の方法。
【請求項１３】
前記画像情報は、前記物理的な表面上の複数の異なる領域の各領域の少なくとも一部に重なる視野に対応することを特徴とする請求項１１に記載の方法。
【請求項１４】
前記復号化するステップは、前記重ね合わせられる領域のうちの第２の領域内の位置情報に基づいて、前記重ね合わせられる領域のうちの第１の領域から欠けている位置情報を補うことを含むことを特徴とする請求項１３に記載の方法。
【請求項１５】
前記領域は連続しており、且つ重なり合わないことを特徴とする請求項１１に記載の方法。
【請求項１６】
位置情報で符号化される基板であって、
その表面がマークのパターンを刻印される基板を含み、
前記マークはそれぞれ、１つの対応する位置符号化シンボルに一対一の関係で復号化することができ、それによって、位置符号化シンボルの対応するパターンが生成され、
前記位置符号化シンボルの前記パターンは複数の領域を含み、
前記各領域内の前記位置符号化シンボルは、前記基板上の前記領域の場所を一意に特定し、
前記位置符号化シンボルは誤り訂正符号で符号化されることを特徴とする基板。
【請求項１７】
各領域は、前記各領域の正しい向きを特定するための複数のレジストレーション符号化シンボルも含むことを特徴とする請求項１６に記載の基板。
【請求項１８】
前記レジストレーション符号化シンボルは、前記レジストレーション符号化シンボルのうちの１つが誤って検出される場合であっても、前記正しい向きを特定することができるようにする少なくとも１つの冗長な符号化シンボルを含むことを特徴とする請求項１７に記載の基板。
【請求項１９】
位置情報で符号化される基板であって、
その表面がマークのパターンを刻印される基板を含み、
前記マークは、位置符号化シンボルの１つの対応するパターンに一意に復号化することができ、
前記位置符号化シンボルは誤り訂正符号で符号化されることを特徴とする基板。
【請求項２０】
前記複数の位置符号化シンボルはリード・ソロモン符号で符号化されることを特徴とする請求項１９に記載の基板。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０Ａ】
【図１０Ｂ】
【図１０Ｃ】
【図１０Ｄ】
【図１１Ａ】
【図１１Ｂ】
【図１１Ｃ】
【図１１Ｄ】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０Ａ】
【図１０Ｂ】
【図１０Ｃ】
【図１０Ｄ】
【図１１Ａ】
【図１１Ｂ】
【図１１Ｃ】
【図１１Ｄ】
【図１２】
【図１３】
【公表番号】特表２００９−５４０４７３（Ｐ２００９−５４０４７３Ａ）
【公表日】平成２１年１１月１９日（２００９．１１．１９）
【国際特許分類】
【出願番号】特願２００９−５１５５７８（Ｐ２００９−５１５５７８）
【出願日】平成１９年６月８日（２００７．６．８）
【国際出願番号】ＰＣＴ／ＵＳ２００７／０７０７１６
【国際公開番号】ＷＯ２００７／１４６７７６
【国際公開日】平成１９年１２月２１日（２００７．１２．２１）
【出願人】（５０３００３８５４）ヒューレット−パッカード デベロップメント カンパニー エル．ピー． (1,145)
【Ｆターム（参考）】
【公表日】平成２１年１１月１９日（２００９．１１．１９）
【国際特許分類】
【出願日】平成１９年６月８日（２００７．６．８）
【国際出願番号】ＰＣＴ／ＵＳ２００７／０７０７１６
【国際公開番号】ＷＯ２００７／１４６７７６
【国際公開日】平成１９年１２月２１日（２００７．１２．２１）
【出願人】（５０３００３８５４）ヒューレット−パッカード デベロップメント カンパニー エル．ピー． (1,145)
【Ｆターム（参考）】
[ Back to top ]