(57)【要約】位置コーディングのための方法においては、第一の所定の長さの各部分列の一次数列における場所が明確に決定される性質を有する一次数列に従って表面上の第一次元に位置がコード化される。第一次元における各位置は、部分列の一によってコード化される。一次数列は、一次数列のベース（基底）よりも小さなベースを有し且つ第一次元における位置に対応する一次数列の部分列の決定のために用いられる少なくとも二つの二次数列によって作られる。このことは、数ある中で、限定されたメモリ容量を有する装置における、二次数列が一次数列よりも合計でより少ないメモリを必要とする方法の実現を可能とする。この二次数列は位置コードのデコードのためにも使用され得る。
2004535011.tif 000002
【特許請求の範囲】
【請求項１】
位置コーディングのための方法であって、
第一の所定の長さの各部分列の一次数列における場所が明確に決定される性質を有する一次数列に従って面上の第一次元に位置をコーディングするステップであって、該第一次元における各位置は、前記部分列の一によってコード化されるステップを有し、
前記一次数列は、該一次数列のベースよりも小さなベースを有し且つ前記第一次元における位置に対応する一次数列の部分列の決定のために用いられる少なくとも二つの二次数列によって作られる方法。
【請求項２】
前記位置コーディングのために使用され得る前記一次数列における異なる数の総数を、該総数が少なくとも二つの因数に因数分解され得るようにさせるステップと、
因数の総数として前記二次数列の同様の数を使用するステップと、
前記因数の各々がそれぞれ二次数列におけるベースを形成するようにさせるステップと
をさらに有する請求項１に従った方法。
【請求項３】
前記二次数列の長さが二つ一組で相対的に素（一以外に公約数を持たない）となるようにさせるステップをさらに有する請求項１または請求項２に従った方法。
【請求項４】
前記二次数列の各々は、前記第一の所定長さを有する各部分列が、前記それぞれの二次数列において明確に決定された場所を有する先行する請求項の内のいずれか１項に従った方法。
【請求項５】
前記二次数列のベースは、多くとも５、望ましくは多くとも３、である先行する請求項の内のいずれか１項に従った方法。
【請求項６】
前記一次数列の前記部分列は、前記二次数列の各々からの部分列の組み合わせに全単射的に写像され得る先行する請求項の内のいずれか１項に従った方法。
【請求項７】
第二の所定長さの各部分列の循環主数列における場所が、明確に決定される性質を有する前記循環主数列の第二の所定長さの部分列を用いて、前記一次数列における数がコード化され、前記循環主数列は、差分の数が、前記一次数列における数を形成するように定義されるようにして、面上に配列される先行する請求項の内のいずれか１項に従った方法。
【請求項８】
前記循環主数列の前記部分列は、各部分列が第二次元内に延びるようにして、面上に配列される請求項７に従った方法。
【請求項９】
理論的に、前記主数列の部分列を用いて定義され得る差分の数の部分集合のみが利用され、該部分集合は、そのような理論的に定義可能な、ゼロに等しいかまたはそれに近い、差分の数を除外する、請求項７または請求項８に従った方法。
【請求項１０】
前記主数列は、二進数であり、且つ前記第二の所定長さよりも長い所定長さの部分列が、後方に生じないようにして選択されるか、または前記主数列における反転形態である請求項７〜９のうちのいずれか１項に従った方法。
【請求項１１】
前記主数列は、二進数であり、且つ前記第二の所定長さよりも長い所定長さの部分列が、前記主数列において反転された一ビットと共に生じないようにして選択される請求項７〜１０のうちのいずれか１項に従った方法。
【請求項１２】
前記主数列の前記部分列であって、前記第二の所定長さの部分列は、六つの数からなり、且つ前記一次数列の前記部分列であって、前記第一の所定長さの部分列は、五つの差分の数からなる請求項７〜１１のうちのいずれか１項に従った方法。
【請求項１３】
前記循環主数列Ｍは、次の通り：
Ｍ＝０，０，０，０，０，０，１，０，０，１，１，１，１，１，０，１，０，０，１，０，０，０，０，１，１，１，０，１，１，１，０，０，１，０，１，０，１，０，０，０，１，０，１，１，０，１，１，０，０，１，１，０，１，０，１，１，１，１，０，０，０，１，１
である請求項７〜１２のうちのいずれか１項に従った方法。
【請求項１４】
前記一次数列は、５４の異なる数を含み、且つ前記二次数列は、四つの数であって、それらのうちの三つがベース３を有しそしてそれらのうちの一がベース２を有する先行する請求項の内のいずれか１項に従った方法。
【請求項１５】
前記二次数列は、次の通り：
Ａ１＝０，０，０，０，０，１，０，０，０，０，２，０，１，０，０，１，０，１，０，０，２，０，０，０，１，１，０，０，０，１，２，０，０，１，０，２，０，０，２，０，２，０，１，１，０，１，０，１，１，０，２，０，１，２，０，１，０，１，２，０，２，１，０，０，１，１，１，０，１，１，１，１，０，２，１，０，１，０，２，１，１，０，０，１，２，１，０，１，１，２，０，０，０，２，１，０，２，０，２，１，１，１，０，０，２，１，２，０，１，１，１，２，０，２，０，０，１，１，２，１，０，０，０，２，２，０，１，０，２，２，０，０，１，２，２，０，２，０，２，２，１，０，１，２，１，２，１，０，２，１，２，１，１，０，２，２，１，２，１，２，０，２，２，０，２，２，２，０，１，１，２，２，１，１，０，１，２，２，２，２，１，２，０，０，２，２，１，１，２，１，２，２，１，０，２，２，２，２，２，０，２，１，２，２，２，１，１，１，２，１，１，２，０，１，２，２，１，２，２，０，１，２，１，１，１，１，２，２，２，０，０，２，１，１，２，２
Ａ２＝０，０，０，０，０，１，０，０，０，０，２，０，１，０，０，１，０，１，０，１，１，０，０，０，１，１，１，１，０，０，１，１，０，１，０，０，２，０，０，０，１，２，０，１，０，１，２，１，０，０，０，２，１，１，１，０，１，１，１，０，２，１，０，０，１，２，１，２，１，０，１，０，２，０，１，１，０，２，０，０，１，０，２，１，２，０，０，０，２，２，０，０，１，１，２，０，２，０，０，２，０，２，０，１，２，０，０，２，２，１，１，０，０，２，１，０，１，１，２，１，０，２，０，２，２，１，０，０，２，２，２，１，０，１，２，２，０，０，２，１，２，２，１，１，１，１，１，２，０，０，１，２，２，１，２，０，１，１，１，２，１，１，２，０，１，２，１，１，１，２，２，０，２，２，０，１，１，２，２，２，２，１，２，１，２，２，０，１，２，２，２，０，２，０，２，１，１，２，２，１，０，２，２，０，２，１，０，２，１，１，０，２，２，２，２，０，１，０，２，２，１，２，２，２，１，１，２，１，２，０，２，２，２，
Ａ３＝０，０，０，０，０，１，０，０，１，１，０，０，０，１，１，１，１，０，０，１，０，１，０，１，１，０，１，１，１，０，１，
Ａ４＝０，０，０，０，０，１，０，２，０，０，０，０，２，０，０，２，０，１，０，０，０，１，１，２，０，０，０，１，２，０，０，２，１，０，０，０，２，１，１，２，０，１，０，１，０，０，１，２，１，０，０，１，０，０，２，２，０，０，０，２，２，１，０，２，０，１，１，０，０，１，１，１，０，１，０，１，１，０，１，２，０，１，１，１，１，０，０，２，０，２，０，１，２，０，２，２，０，１，０，２，１，０，１，２，１，１，０，１，１，１，２，２，０，０，１，０，１，２，２，２，０，０，２，２，２，０，１，２，１，２，０，２，０，０，１，２，２，０，１，１，２，１，０，２，１，１，０，２，０，２，１，２，０，０，１，１，０，２，１，２，１，０，１，０，２，２，０，２，１，０，２，２，１，１，１，２，０，２，１，１，１，０，２，２，２，２，０，２，０，２，２，１，２，１，１，１，１，２，１，２，１，２，２，２，１，０，０，２，１，２，２，１，０，１，１，２，２，１，１，２，１，２，２，２，２，１，２，０，１，２，２，１，２，２，０，２，２，２，１，１
である先行する請求項の内のいずれか１項に従った方法。
【請求項１６】
第三の所定の長さの各部分列の第二の一次数列における場所が明確に決定される性質を有する前記第二の一次数列に従って面上の第二次元に位置をコード化するステップであって、前記第二次元における各位置は、前記第二の一次部分列における部分列の一によってコード化され、且つ前記第二の一次数列は、前記第二の一次数列のベースよりも小さなベースを有し且つ前記第二次元における位置に対応する前記第二の一次数列の部分列の決定のために用いられる少なくとも二つの第二の二次数列によって作られるステップをさらに有する先行する請求項の内のいずれか１項に従った方法。
【請求項１７】
第一次元および第二次元における位置コーディングのための一次数列および二次数列は、同一である請求項１６に従った方法。
【請求項１８】
前記位置コードを面上のグラフィックなコーディングによってプリントアウトするステップをさらに有する先行する請求項の内のいずれか１項に従った方法。
【請求項１９】
コンピュータに位置コーディングを実行させるための命令群を有するコンピュータプログラムであって、該コンピュータプログラムは、第一の所定の長さの各部分列の一次数列における場所が明確に決定される性質を有する一次数列に従って面上の第一次元に位置をコーディングするための命令であって、該第一次元における各位置は、前記部分列の一によってコード化される命令群を有し、
前記一次数列は、該一次数列のベースよりも小さなベースを有し且つ前記第一次元における位置に対応する一次数列の部分列の決定のためのコンピュータプログラムによって用いられる少なくとも二つの二次数列によって作られるものであるコンピュータプログラム。
【請求項２０】
位置をコーディングするためのデバイスであって、該デバイスは、プロセッサと、請求項１９に従ったコンピュータプログラムを格納するメモリとを具備するデバイス。
【請求項２１】
面上の第一の点のためおよび第一次元のための少なくとも第一の座標ｘをコード化する位置コードを決定するコーディングデバイスにおける方法であって、
前記コーディングデバイスに対する入力信号として少なくとも前記第一の座標ｘを受信するステップと、
受信された座標ｘに基づいて、前記第一次元における位置のコーディングのために使用される一次数列の部分列を決定し、該部分列は、前記受信された座標ｘに対応して、第一の所定長さを有し且つ前記位置字数列において明確に決定された場所を有するステップとを有し、
前記一次数列は、前記一次数列よりも小さなベースを有し且つ前記座標ｘに対応する前記一次数列の部分列の決定のために前記コーディングデバイスによって用いられる少なくとも二つの二次数列によって作られるものである方法。
【請求項２２】
前記一次数列の部分列を決定するステップは、前記一次数列における前記場所を前記二次数列の各々における場所に変換するステップを有する請求項２１に従った方法。
【請求項２３】
前記一次数列の部分列を決定するステップは、前記二次数列における前記決定された場所に対応し且つ前記二次数列の前記そのようにして決定された部分列に基づいて前記一次数列の前記部分列を決定する前記部分列を、前記二次数列の各々について決定するステップをさらに有する請求項２２に従った方法。
【請求項２４】
第二の所定長さの各部分列の循環主数列における場所が明確に決定される性質を有する、前記循環主数列の前記第二の所定長さの部分列を用いて前記一次数列の部分列における数をコーディングするステップであって、前記一次数列の前記部分列における前記数が前記循環主数列の前記部分列の差分としてコード化されるステップをさらに有する請求項２１〜２３のうちのいずれか１項に従った方法。
【請求項２５】
前記コーディングデバイスからの出力信号として前記循環主数列の部分数列の指摘を含む位置コードを出力するステップをさらに有する請求項２４に従った方法。
【請求項２６】
これらが第二次元に広がるようにし且つ前記一次数列の部分列における数が前記第一次元に広がるようにして、デバイスが前記主数列の部分列を面上に適用するようにさせる請求項２４または請求項２５に従った方法。
【請求項２７】
前記循環主数列の部分列のうちの第一の部分列を、周期的に繰り返される前記二次数列の各々におけるｘ−１第一数を合計することによって計算するステップをさらに有する請求項２４〜２６のうちのいずれか１項に従った方法。
【請求項２８】
前記二次数列における数は、前記二次数列の完全なおよび不完全な周期の従前に計算された合計の使用により合計される請求項２７に従った方法。
【請求項２９】
前記コーディングデバイスは前記座標ｘ＝０についての前記部分列の循環主数列における場所を入力信号としてさらに受信すべく構成され、且つ前記主数列の前記部分列の間の前記第一の部分列の計算のために座標ｘ＝０の場所を用いるステップをさらに有する請求項２７または請求項２８に従った方法。
【請求項３０】
前記主数列の前記第一および前記第二の部分列によってコード化される前記一次数列の前記部分列において数ｄ（ｘ）を決定することによって、前記主数列の前記部分列の間で第二の部分列を決定するステップをさらに有する請求項２７〜２９のうちのいずれか１項に従った方法。
【請求項３１】
前記主数列の前記第一および第二の部分列によってコード化される前記数ｄ（ｘ）は、
ｄ（ｘ）＝ｄｃ（１，ｘ）＋ｂ１＊ｄｃ（２，ｘ）
＋…＋ｂ１＊…＊ｂｎ−１＊ｄｃ（ｎ，ｘ）
但し、ｎは、二次数列の数、ｂｉは、二次数列ｉにおけるベース、そしてｄｃ（ｉ，ｘ）は、長さｌｉのそれぞれの二次数列におけるｌｉを法とした場所ｘにおける数、
として計算される請求項３０に従った方法。
【請求項３２】
前記コーディングデバイスへの入力信号として第一の点についてのそして前記面上の第二次元についての第二の座標ｙを受信するステップと、
前記第二次元における位置のコーディングのために用いられる第二の一次数列の部分列であって、第三の所定長さを有し且つ明確に決定された場所を有する前記部分列を、前記受信された座標ｙに基づいて、前記第二の一次数列において、受信された座標ｙに対応して、決定するステップとをさらに有し、
前記第二の一次数列は、前記第二の一次数列よりも小さなベースを有し且つ前記座標ｙに対応する前記第二の一次数列の部分列の決定のために前記コーディングデバイスによって用いられる少なくとも二つの二次数列によって作られるものである請求項２１〜３１の内のいずれか１項に従った方法。
【請求項３３】
請求項２１〜３２のうちのいずれか１項に従った方法を、コンピュータに実行させるための命令群を有するコンピュータプログラム。
【請求項３４】
位置をコーディングするためのデバイスであって、該デバイスは、プロセッサと、請求項３３に従ったコンピュータプログラムを格納するメモリとを具備するデバイス。
【請求項３５】
第一の点および面上の第一次元についての少なくとも第一座標（ｘ；ｙ）をコード化する位置コードのデコーディングのための方法であって、該方法は、
前記位置コードのディジタル表現に基づいて一次数列の部分列であって、該部分列は前記一次数列において明確に決定された場所であって前記第一座標に対応する場所Ｐを有する部分列を形成する数の第一の所定数を識別するステップと、
前記一次数列を作り且つそれらの各々が前記一次数列のベースよりも小さいベースを有する少なくとも二つの二次数列を用いるステップを含む前記一次数列における前記部分列の前記場所Ｐを決定するステップと
を有する方法。
【請求項３６】
前記一次数列における前記部分列の場所Ｐを決定するステップは、前記一次数列の前記部分列を前記二次数列の各々の部分列の組み合わせに変換するステップを含む請求項３５に従った方法。
【請求項３７】
前記組み合わせにおける前記部分列の各々の前記二次数列それぞれにおける場所を決定するステップと、前記二次数列における前記場所の前記組み合わせに基づいて前記一次差分数列における場所Ｐを決定するステップとをさらに有する請求項３５または請求項３６に従った方法。
【請求項３８】
前記一次数列の前記部分列を前記二次数列の各々の部分列に変換するステップは、前記一次数列の前記部分列における各数ｄを、次の：
ｄ＝ｄ１＋ｂｉ＊ｄ２＋…ｂ１＊ｂ２…＊ｂｎ−１＊ｄｎ，
但し、ｎは、前記二次数列の数であり、そしてｂｉは、前記二次数列ｉにおけるベースである、
に従って数ｄ１，…ｄｎ，の組に変換するステップを含む請求項３５または請求項３６に従った方法。
【請求項３９】
前記一次数列における場所Ｐは、中国の余剰定理を用いて、
Ｐ＝（ｓｕｍ（ｉ＝１，ｎ）（（Ｌ／ｌｉ））＊ｐｉ＊ｑｉ）（ｍｏｄ  Ｌ）
但し、Ｌ＝ｐｒｏｄ（ｉ＝１，ｎ）ｌｉ、ｐｉは、前記二次数列ｉにおける場所、ｌｉは、前記二次数列ｉの長さ、そしてｍは、二次数列の前記数、ならびにｑｉ＊（Ｌ／ｌｉ）＝１（ｍｏｄ  ｌｉ）である、
として決定される
請求項３６〜３８のうちのいずれか１項に従った方法。
【請求項４０】
座標０についての部分列の主数列における場所を決定することによって、第一の点および第一次元について付加的な座標（ｘｓ；ｙｓ）を決定するステップをさらに有する請求項３５〜３９のうちのいずれか１項に従った方法。
【請求項４１】
前記位置コードが、第一の位置についておよび第二次元について第二の座標（ｙ；ｘ）をさらにコード化し、且つ位置コードのディジタル表現に基づいて、第二の一次数列の部分列を形成する第三の所定数の数を識別するとともに、前記部分列は前記第二の一次数列内に明確に決定された場所を有し、該場所は前記第二の座標に対応するステップであって、且つ少なくとも二つの第二の二次数列を用いて前記第二の一次数列における部分列の場所を決定するとともに、それらの各々が前記第二の一次数列のベースよりも小さなベースを有するステップをさらに有する請求項３５〜４０のうちのいずれか１項に従った方法。
【請求項４２】
当該方法は、入力信号として前記位置コードのディジタル表現を受信し且つ出力信号として少なくとも前記第一の点についての前記第一の座標を与えるデコーディングデバイスにおいて実行される請求項３５〜４１の内のいずれか１項に従った方法。
【請求項４３】
請求項３５〜４２の内のいずれか１項に従った方法を、コンピュータに実行させるための命令群を有するコンピュータプログラム。
【請求項４４】
位置コードをデコーディングするためのデバイスであって、該デバイスは、プロセッサと、請求項４３に従った位置コードをデコーディングするためのコンピュータプログラムを格納するメモリとを具備するデバイス。
【請求項４５】
少なくとも面上の第一の点および第一次元についての第一の座標をコード化する、位置コードのデコーディングのためのデバイスであって、該デバイスは、デコードされるべき前記位置コードのディジタル表現を提供するためのセンサーと、前記二次数列のベースよりも大きなベースを有して一次数列を作り上げる少なくとも二つの二次数列を格納するためのメモリと、前記位置コードのディジタル表現に基づいて、前記一次数列の部分列を形成する第一の所定数の数を識別すべく構成され、前記部分列は、前記一次数列における明確に決定された場所Ｐを有し、前記場所は前記第一の座標に対応し、且つ前記二次数列によって前記一次数列における場所Ｐを決定すべく構成されたプロセッサとを具備するデバイス。
【請求項４６】
前記プロセッサは、前記一次数列における前記部分列の場所Ｐを決定するために、前記一次数列の前記部分列を前記二次数列の各々の部分列の組み合わせに変換すべくさらに構成されている請求項４５に従ったデバイス。
【請求項４７】
前記組み合わせにおける前記部分列の各々の前記二次数列それぞれにおける場所を決定し且つ前記二次数列における場所の組み合わせに基づいて前記一次差分数列における場所Ｐを決定すべくさらに構成されている請求項４６に従ったデバイス。
【請求項４８】
少なくとも第一の点についておよび第一次元についての第一の座標をコード化する位置コードが提供され、前記第一の点についての第一座標は一次数列の部分列によってコード化され、前記部分列は、第一の所定長さを有し、前記一次数列は、前記所定長さの各部分列の前記一次数列における前記場所が明確に決定される特性を有し且つ前記一次数列は、加えて、前記一次数列のベースよりも小さなベースを有する少なくとも二つの二次数列から作られる製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、位置コードを達成するための方法、位置コードをデコーディングするための方法、これらの目的のためのコンピュータプログラム、位置コードが提供される製品ならびに位置コーディングのためおよび位置コードのデコーディングのためのデバイスに関する。
【背景技術】
【０００２】
面上に書き込まれまたは描画される情報を電子的形態で記録するための道具として面上の位置コードの使用は既に知られている。
【０００３】
米国特許ＵＳ５，４７７，０１２号において、面上の種々のシンボルからなる位置コードを光学的に検出するペンが記述されている。前記ペンは前記位置コードをデコードし、前記面を横切るペンの動きを記述する座標の対を複数生成する。各位置は特定のシンボルによってコード化される。もしも位置コードが多数の位置をコード化するものであれば、このことは、結果として前記シンボルは複雑になり且つそれ故正確に検出することが困難であるという不都合を生ずる。これに反して、もしもシンボルがより大きく作られれば、分解能は低下する。
【０００４】
国際特許出願ＷＯ  ９２／１７８５９号においては、各位置は複数のシンボルによってコード化され、且つ各シンボルは一よりも多くの位置のコーディングを与える位置コードが記述されている。近傍の位置は、それ故部分的に共有されるシンボルによってコード化される。
【０００５】
国際特許出願ＷＯ  ９２／１７８５９号の付録Ａにおいては、前記位置コードがどのようにして作られ得るかおよび位置がどのようにしてデコードされ得るかの次の例が与えられる。
【０００６】
次のｍ−列：ｓ＝（０，０，１，０，１，１，１）およびｔ＝（０，１，１）からスタートせよ。パターンにおける第一列を列Ｓと同じにさせることによって位置コーディングパターンを作れ。次の列を作るために、ｔ−列を考察せよ。もしも、ｔ−列における第一の要素が、０であるとすれば、そのときは第二列はｓ−列からなる。その代わりに、もしも、ｔ−列における第一の要素が、１であるとすれば、そのときは第二列は一ステップだけ循環移動されたｓ−列からなる。後続の列は、ｔ−列における前記要素の値に従って対応する方法で作られる。それ故、次のパターンが得られる：
０  ０  １  １
０  ０  ０  １
１  １  ０  ０
０  ０  １  ０
１  １  ０  １
１  １  １  ０
１  １  １  １
さて、我々が前記パターンの次のサブセットを有する部分面の位置を見つけることを望んでいると仮定する。
【０００７】
１  ０  ０
０  １  ０
１  ０  １
サブセットにおける第一列は、（１，０，１）である。このサブ列は、ｓ−列における位置２にあらわれる。サブセットにおける循環移動は、（１，１）である。このサブ列は、ｔ−列における位置１にあらわれる。前記パターンにおける累積された移動は、（０，０，１，２）であり、そしてそれ故前記サブセットの垂直位置は、２＋０＝２である。前記部分面上のサブセットの位置は、それ故（１，２）である。
【０００８】
このパターンは、それが、例えばゼロについての第一のシンボルおよび一についての第二のシンボル等の単純なシンボルを用いてベース上にコード化され得るという利点を有している。
【０００９】
しかしながら、このタイプの位置コーディングパターンの興味深い性質は、位置決定が可能な限り大きな面の上で実行され得るように、大きなパターンを多数の特有の位置によってコード化する能力である。上述の例において、垂直方向のサイズは、ｓ−列の長さによって制限され且つ水平方向のサイズは、ｔ−列の長さによって制限される。もしもサブ列がｋビットからなるものを採用すれば、このサブ列は、前記列におけるある単一の場所に生じるのみでなければならないという性質を、前記列が持たなければならないので、これらの列の長さは、制限なく増大されることはできない。前記列の長さにおける増大は、このようにして前記サブ列の長さにおける増大を、そしてそれによって、位置を決定することができるようにするために記録されることが必要である部分面の増大を成し遂げることができる。
【００１０】
本出願の出願人に譲渡されている国際特許出願ＷＯ  ０１／２６０３２号、ＷＯ  ０１／２６０３３号およびＷＯ  ０１／２６０３４号においては、国際特許出願ＷＯ  ９２／１７８５９におけるそれらと同様の基本原理に基づいているが、より多数の位置のコーディングを可能とする、他の位置コーディングパターンが、記述されている。
【００１１】
このパターンの一つの実施の形態においては、所定長さの各サブ列すなわち部分列の数列における場所が明確に決定される性質を有する第一の数列が使用され且つこの数列が種々の回転すなわち循環移動によって面全体にわたって列毎にプリントアウトされる。しかしながら、二進第二列（国際特許出願ＷＯ  ９２／１７８５９におけるｔ−列）を使用する代わりに、隣接する列の間のさらに大きな循環移動が許容される。
【００１２】
前記面は、コード窓にさらに分割される。各コード窓は、少なくとも三つの列からなり、且つ隣接するコード窓を一の数列だけオーバラップさせている。隣接する列の間の移動を用いて、ｘ−軸に沿うコード窓の位置がコード化される。コード窓における前記数列の間のこの移動は、そのようにして位置を定義し、第一のコード窓は位置０、次は１、等々を有する。
【００１３】
しかしながら、前記位置コードを読み取るとき、読み取りデバイスは、しばしば二つのコード窓の部分を記録するであろう。前記位置コードの読み取りイメージに関連するコード窓の位置が決定され得るようにするために、第一の範囲における移動は、位置についての少なくとも意味のある移動を指摘するために用いられ、そして第二の範囲における移動は、位置における他の移動のために用いられる。
【００１４】
ｙ−座標のコーディングは、対応する方法にて実行される。
【００１５】
この位置コードは、非常に良好に働くことが見出されており、且つ非常に多数の位置のコーディングを許容する。しかしながら、位置コードのエラー訂正特性を改善することの要請がある。
【００１６】
例えば、ｘ−方向における位置を明確にコード化する最小のサブセットが、五つの移動を有していると仮定されたい。これらの五つの移動から、コード窓の位置が決定され得る。二つの隣接するコード窓の位置は、そのように通常は最終桁（最終移動）において異なっているのみである。三つの連続的なコード窓について、前記移動は、例えば、次の通りとなり得る：
２５，１５，３４，１８，３；２５，１５，３４，１８，４；２５，１５，３４，１８，５；
エラーを検出する通常の方法は、関連するタスクのために必要とされるものよりも多くの情報を読み取ることに基づいている。上述されたコーディングによって、エラー検出のために使用するのに適する余分の情報を読み取ることは困難である。例えば、読み取りデバイスが、最初の上述の三つのコード窓から二つの最後の移動、および次のコード窓からの最初の三つの移動、すなわち１８，３，２５，１５，３４を記録すると仮定されたい。１８，４，２５，１５，３４が記録されるという結果を生ずるエラーが生じるとさらに仮定されたい。例えば、さらに、前記五つの両側に一ずつの、二つの移動の読み取りでは、エラーを検出することを可能とさせる余分の情報を提供することはない。
【００１７】
もしも、ｘ−方向におけるコーディングときに、所定長さの各部分列（サブ列）が、数列内に明確に決定された場所を持つ性質と共に数列が使用されるならば、エラー訂正は容易化される。他方では、もしも多くの位置をコード化することが可能となるようにするならば、この数列は大きなベースを持たなければならない、すなわち大きな移動を許容しなければならない、という実際的な問題が発生する。それから、非常に大きなテーブルが、読み取り部分列が対応する数列における場所を見つけるために、要求され、そしてそれは今度は非常に多量のメモリを必要とする。しかしながら、それは、例えば、限定されたメモリおよびプロセッサ容量を有するハンドヘルドの読み取りデバイスにおいてデコーディングが実行されることが可能となるために望ましい。また、限定されたメモリおよびプロセッサ容量を有するデバイスにおいてコーディングが実行されることが可能でなければならないことも望ましい。
【発明の開示】
【発明が解決しようとする課題】
【００１８】
それ故、本発明の目的は、非常に多数の位置をコード化することを可能とさせ、エラー訂正を可能とするが、しかしコーディングおよびデコーディングのために大きなテーブルの記憶部を必要としない、そしてそれは、それ故、限定された量のメモリおよび／または限定されたプロセッサ容量を有するデバイスにおいて実現され得る位置コードを提供することによって、上述された問題を低減することである。
【００１９】
他の目的は、非常に多数の位置をコード化する位置コードの効果的で且つ正確なデコーディングを可能とさせることである。
【課題を解決するための手段】
【００２０】
これらの目的は、請求項１に従った位置コーディングのための方法、請求項１９に従ったコンピュータプログラム、請求項２０に従ったコーディングデバイスにおける方法、請求項３２に従ったコンピュータプログラム、請求項３３に従った位置コードをデコーディングするための方法、請求項４１に従ったコンピュータプログラム、請求項４２に従った製品、および請求項４３〜４５に従ったデバイスによって完全にまたは部分的に達成される。
【００２１】
したがって、本発明の第一の局面は、位置コーディングのための方法であって、第一の所定の長さの各部分列の一次数列における場所が明確に決定される性質を有する一次数列に従って面上の第一次元に位置をコーディングするステップであって、該第一次元における各位置は、前記部分列のいずれか一によってコード化されるステップを有し、前記一次数列は、該一次数列のベースよりも小さなベースを有し且つ前記第一次元における位置に対応する一次数列の部分列の決定のために用いられる少なくとも二つの二次数列によって作られる方法に関する。
【発明の効果】
【００２２】
前記一次数列が、より小さなベース、望ましくは多くともベース５、を有する二次数列から作られるので、前記一次数列における場所をこれの部分列に変換するために必要とされるテーブルは、合わせてより少ないメモリを必要とするいくつかのより小さなテーブルによって置き換えることができる。したがって、非常に多数の位置のための座標をコード化することが、実際に実行可能となる。
【００２３】
少なくとも第一次元における位置をコーディングするための一次数列の使用は、非常に良好なエラー検出およびエラー訂正特性を持って位置コードを達成することをも可能とさせる。さらに詳細には、前記一次数列における各数は、循環主数列の部分列を用いてコード化される。もしも、位置決定のために必要とされるものよりも長い前記主数列の部分列が今記録されるならば、エラー検出およびエラー訂正が、より長い部分列が、ある不適正なバージョンにおいて、例えば一の不適正な図について、生じないような方法で設計された前記主数列によって達成され得る。
【００２４】
デコーディングについても、また、前記一次数列が、より小さなベースを有する二次数列から作られるという事実が用いられ、前記デコーディングは、いくつかのより小さなテーブルを用い且つ中国の余剰定理を用いて実行され得る。その結果、前記デコーディングは、例えば限定されたメモリおよびプロセッサ容量を有するハンドヘルドデバイスにおいて実現され得る。
【００２５】
位置コーディングは、一次元および二次元の両方において位置をコーディングするために利用され得る。前記第二次元におけるコーディングは、第一次元におけるコーディングのために、または同一の数列を用いて利用されるものに対して、同様の原理を用い且つ異なる数列を伴って実行され得る。
【発明を実施するための最良の形態】
【００２６】
さて、本発明は、例示的な実施の形態を用いてそして添付された図面を参照して、説明されるであろう。
【００２７】
〔実施の形態の記述〕
以下においては、本発明に従った位置コーディングのための全般的な原理が特定の例を用いて説明されるであろう。その後は、コーディングおよびデコーディングが実際にどのようにして実施され得るかが説明される。その後は、位置コードのデコーディングのために使用され得る読み取りデバイスの例が説明される。最後に、代替的な実施の形態が説明される。
【００２８】
〔位置コーディングのための全般的な原理〕
位置コードは、一またはそれより多くの次元における位置をコード化するために用いられる。説明を単純化するために、位置コーディングは、まず、この例においてはｘ−方向における、第一次元においてのみ考慮される。循環主数列が、この方向におけるコーディングのために用いられ、該循環主数列は、所定長さの各部分列の前記循環主数列における場所が、明確に決定される性質を有している。この例においては、前記所定長さは６である。したがって、もしも六つの連続する数が、前記循環主数列におけるいずれかの場所からとられたら、これら六つの数が、この順序で前記循環主数列においてただ一度だけ生ずるであろう。該性質は、もしも前記主数列の末端が該主数列の始端に連結されている場合にも適用される。前記主数列は、それ故に循環と呼ばれる。この例においては、二進主数列が使用される。もしも、六つの数を有する部分列の場所が、明確に決定されるならば、前記主数列は、したがって、２６＝６４の最大長さを持つことができ且つ長さ６の前記部分列は、前記主数列における場所０〜６３を持つことができる。しかしながら、もしも、長さ６３の主数列が選択されると、以下に説明されるであろうように、改善されたエラー訂正特性が得られる。以下においては、したがって、主数列の長さは６３で且つそれ故それが０〜６２の範囲におけるただ一つの場所を定義すると仮定される。前記主数列のこの長さによれば、各部分列を前記主数列における場所に変換し且つその逆にするテーブルを持つことが実際に可能である。
【００２９】
前記主数列の開始が次の通りであると仮定されたい：
０，０，０，０，０，０，１，０，０，１，１，１，１，１，０，１，０…
そのとき、例えば、前記主数列において、部分列０，０，０，０，０，０は、明確な場所０を有し、部分列１，１，１，１，１，０は、明確な場所９を有し、そして部分列１，１，１，０，１，０は、明確な場所１１を有する。
【００３０】
前記位置コーディングは、前記循環主数列の異なる循環または循環移動を利用することに基づいている。ｘ−方向における位置をコード化するために、前記主数列が、プリントアウトされまたは何か他の方法で配列され、面を横切る、すなわち位置がコード化されるべき方向に直交するｙ−方向における、列について種々の方法で循環されまたは循環的に移動される。前記主数列は、もしもｙ−方向において、前記主数列の前記長さに対応するものよりも多くの位置がコード化されようとする場合に必要とされる、同一の列について繰り返しプリントアウトされ得る。それから、前記主数列の同様の循環が、すべての繰り返しに使用される。しかしながら、異なる循環は異なる列に使用され得る。
【００３１】
図１は、七つの列ｘ〜ｘ＋６を有する一枚の紙１を概略的に示している。前記主数列の異なる循環における最初の数のみがプリントアウトされる。全体の主数列は、ボックスＢによって概略的にマークされている。加えて、図１においては、六つの数の第一の部分列Ｓが、破線を用いて描かれたボックスによって各列においてマークされている。上述されたように、前記部分列Ｓの各々は、前記主数列における明確に決定された場所を有する。
【００３２】
隣接する列の各対は、差分数ｄを定義する。差分数ｄは、それぞれの列における第一の部分列の主数列における場所の間の差分によって与えられる。もしも、その代わりに、各列における一ステップ下の部分列の場所の間の差分がとられたら、結果は、場所が同様の方法で転置されるので、同様となるであろう。したがって、差分数ｄは、列におけるどの「高さ」において、前記主数列における部分列の場所が比較されるかにかかわりなく、同様となるであろう。したがって、各対の列について、差分数ｄは、ｙ−方向において一定である。
【００３３】
列ｘ＋５における主数列の第一の部分列は、０，０，０，０，０，０であり、それは前記主数列における場所０に対応する。列ｘ＋６における主数列の第一の部分列は、１，０，０，０，１，１であり、それは前記主数列における場所５７に対応する。これらの列の間の差分または循環移動は、したがって５７であり、それ故ｄ（ｘ＋５）＝５７である。前記差分数が前記主数列の長さを法として決定されることが指摘されるべきである。
【００３４】
このような方法でコード化され得る差分数は、０〜Ｋ−１の範囲内にあり、ここでＫは前記主数列の長さで、この場合Ｋ＝６３であり、したがって、それによって０〜６２の範囲内における差分数をコード化することが可能となる。前記主数列の異なる循環を選択することによって、以下において一次数列または一次差分数列と呼ばれる、差分数の列を作ることができ、それは、所定長さの各部分列は、一次数列において明確に決定される場所を有する。この例においては、前記所定長さは５である。五つの差分数からなる各部分列は、前記一次差分数列における明確に決定する場所を有し、このことはｘ−方向における位置をコード化するのに用いられ得る。図１において、部分列Ｓ（ｘ）〜Ｓ（ｘ＋５）は、前記一次数列の部分列を与える五つの差分数ｄ（ｘ）〜ｄ（ｘ＋４）をこのようにしてコード化するであろう。
【００３５】
実際に前記部分列は、それらの明示的な値によっては正常にプリントアウトされないが、グラフィカルなコード化によって正常にプリントアウトされることも指摘されるべきである。前記主数列の二進数の列は行列を形成し、それは以下においてはｘ−行列と呼ばれるであろう。
【００３６】
もしも、前記主数列の長さがＫであるならば、前記一次差分数列におけるベースはＫに等しくなり且つその最大長さは、Ｋ５、すなわちこの場合６３５になるであろう。しかしながら、部分列を前記一次差分数列における場所に変換するためのテーブルを使用すること、そして非常に大きいベースについてその逆をすることは、実際には可能ではない。しかしながら、もしも、前記ベースが管理可能なテーブルを使用できるようにするために縮小されれば、コード化可能な位置の数が減小されるであろう。
【００３７】
この問題は、特定のｘ−座標に対応する一次差分数列における部分列およびその逆を決定するために、前記位置コードをコーディングし且つデコーディングするときに、以下においては、二次差分数列または二次数列と呼ばれる、より短い差分数列の一次差分数列を作ることによって、そして、そのために前記部分列およびそれらの場所が小さなテーブル内に配置され得る、前記二次差分数列を用いることによって、解決される。
【００３８】
前記二次差分数列は、次のようにして決定され得る：
第一に、差分数は、異なる差分数の個数が少なくとも二つの要素に因数分解され得るような範囲内にのみ許可される。長さ６３の主数列を有する例においては、差分数は、長さ５４の範囲内でのみ許可される。数５４は、実際には、２＊３＊３＊３として因数分解され得る。その代わりに、６０の差分数、すなわち５＊３＊２＊２の差分数が、選択され得るが、テーブルが可能な限り小さくなるようにするために、可能な限り小さな要素を与える数を選択することが好都合であるかもしれない。
【００３９】
第二に、二次差分数列の同一の数は異なる差分数の数が因数分解され得る要素の数として形成される。この例においては、それ故、二次差分数列の数は、４に等しい。
【００４０】
加えて、我々は、各要素に、それぞれの二次差分数列においてベースを形成させる。この例においては、それ故、我々は、ベース２を有する一の二次差分数列およびベース３を有する三つの二次差分数列を得る。
【００４１】
したがって、前記二次差分数列の差大長さは、もしも前記二次差分数列が長さ５の部分列が該二次差分数列において特有の場所を有するはずであるという特性をも有するとするならば、それぞれ３２および２４３である。前記二次差分数列のそのような長さによれば、部分列を場所およびその逆に変換することが、実際に可能である。もしも、その代わりとして、我々が６０の異なる数を使用すべく選択したならば、我々はベース５を有する二次差分数列を持つであろうし、そしてそれ故、かなりより多くのメモリを使用するテーブルを与える、３１２５の最大長さが、しかしながら、なお管理できる。
【００４２】
最後に、前記二次差分数列の長さは、該長さが対をなして相対的に素であるように選択される。このことは、各対をなす二次差分数列について、一の差分数列の長さが、前記第二の差分数列の長さと共通のどのような要素も持たないようにすることを意味する。このことは、加えて、もしも前記差分数列の各々が繰り返されるならば、各二次差分数列からの部分列の同一の組み合わせは、Ｌ＝ｌ１＊１２＊…＊ｌｍの場所の後まで生じないであろうことを意味し、そこでは、ｌ１は、二次差分数列１の長さであり、ｌ２は、二次差分数列２の長さであり、そして最後の二次差分数列１の長さであるｌｍまで、同様である。もしも、二つの二次数列だけしかなければ、もちろん、Ｌ＝１１＊１２である。
【００４３】
このことは、図２に概略的に図解されている。最上部には、ここでは単にＸによって示されている差分数による一つの長い列において延びる一次数列ＰＤが示されている。下部には、二次数列Ａ１〜Ａ４が概略的に示されている。垂直線は数列が再開する場所を示している。一次数列の部分列および対応する二次数列の部分列は、破線によって示されている。部分列は、二次数列における異なる場所に対応することがわかる。
【００４４】
二次差分数列の部分列の組み合わせによる一次差分数列の部分列の表現は、この例においては、全単射である。これは、しかしながら、必要なことではない。
【００４５】
第二次元における、例えばこの場合ｙ−方向における、位置コーディングは、第一次元における位置コーディングと同様の原理に従って実行され得る。前記主数列は、それから、面上の行についての、すなわち図１におけるｘ−方向についての、異なる循環移動によって配列される。差分数は、隣接する行の間で定義され且つこれら差分数は、二次差分数列から作られ得る一次差分数列を形成する。第二次元における他の主数列、他の一次差分数列および他の二次差分数列を使用することが可能である。前記種々の数列におけるベースも、前記第一次元においてコーディングのために使用されたそれらのもの以外とすることもできる。この例においては、しかしながら、同一の列が、ｘ−方向とｙ−方向との両方に使用される。ｘ−方向におけるコーディングに対応する方法において、ｙ−方向におけるコーディングは、結果として、行の値が主数列の二進値からなる行列を得る。
【００４６】
もしも、ｘ−行列およびｙ−行列が重ね合わされたならば、結果として得られるＸＹ−行列における各点について、ｘ−行列からの１ビットとｙ−行列からの１ビットとが存在するであろう。それ故、各点において、次の四つのビット組合せが、取得され得る：０，０；０，１；１，０；および１，１。これらの異なる組み合わせは、例えばドット３０が、ラスタにおける公称点３１からの四つの方向のいずれか一つの方向に変位され、各公称点は、ラスタにおける線３２間の交差に対応する、図３ａ〜図３ｄに示された方法によって、面上にグラフィカルにコード化され得る。このタイプのグラフィカルなコーディングは、国際特許出願ＷＯ  ０１／２６０３２号に非常に詳細に説明されており、そこでは、しかしながら、実際に潜在する位置コーディングが異なる方法にて実行される。この例において使用されるコーディングは次の通りである：
2004535011.tif 000003
ラスタは、仮想的であり得て、その場合、それ故、位置コードにて面上を明示的にプリントアウトしない。
【００４７】
図４は、位置コード４１０を有する一枚の紙４００の形態における製品の一部を概略的に示している。図４における位置コードは、例えばディジタル化された手書きに適するバージョンに関連して非常に大きく拡大されていることは、強調されるべきである。加えて、ラスタ４２０は、図４にマークされている。しかしながら、これは、通常はプリントアウトされない。
【００４８】
もちろん、他のタイプのグラフィカルなコーディングが、異なるサイズの４ドット、異なる形状を有する四つのマーク、または異なる回転を有する四つのマークのような、四対のビットについて選択され得る。
【００４９】
位置コーディングが、主数列における異なる部分列の場所の間の差分に基づいており、且つ同様の差分が、部分列の異なる対を用いて得られ得るので、一次差分数列が、種々の方法において達成され得る。より詳細には、一次差分数列の６３の異なる「バージョン」が、その部分列、すなわち主数列のどの回転が、ｘ−行列における非常に最初の列（ｘ＝０）およびｙ−行列における非常に最初の行（ｙ＝０）を始めるべく選択されたか、に依存して、達成され得る。したがって、ｘ−方向およびｙ−方向へのコーディングのために同一の一次差分数列を利用する位置コードのＫ＊Ｋ（この例では６３＊６３＝３９６９）個の異なる「バージョン」を生成することが可能である。位置コードのこれらの異なるバージョンは以下においてセクションと呼ばれる。ｘ−方向における位置コードについてのセクション数ｘｓおよびｙ−方向における位置コードについてのセクション数ｙｓは、それぞれｘ−方向およびｙ−方向についての付加的な座標として示され得る。
【００５０】
上の例においては、主数列を用いて理論的にコード化され得る差分数のサブセットのみが、より詳細には、６３の可能性のある差分数から５４のみが、使用されている。理論的に可能性のある差分数の部分範囲は、種々の方法で選択され得る。この例においては、（前記主数列の長さを法とした）ゼロに近い差分数が、位置コードにおける所望されていない規則性を作り得る。それ故、この例においては、差分数は、範囲（５，５８）内に選択される。このことは、一次数列における部分列と二次数列における部分列との間の変換に関して考慮されなければならず、そしてそれは以下において説明されるであろう。今、位置コードが面上に配置されていると仮定されたい。読み取りデバイスは、少なくとも６＊６ドットに対応する位置コードのサブセットを検出するエリアセンサを持ち得る。読み取りのとき、前記読み取りデバイスは、前記位置コードに関連して種々の方法で回転されて保持され得る。理論上で位置コードはそれが０，９０，１８０または２７０度にわたって回転されようとされまいと同様に見えるので、位置コードのイメージは、位置コードと読み取りデバイスとの間の回転をそれ自体で明らかにすることはない。位置コードが回転されるとき、各ドットの変位の方向は、しかしながら、変化され、それが、今度は、変化されるドットの変位によってコード化されたビットの対に導く。どのように変化が生ずるかは、変位とビットの対の間の変換に依存する。以下においては、上述されたように変換が実施されると仮定されている。三つの異なるケースが存在する。
【００５１】
１）位置コードのイメージの１８０度の回転によって、非回転位置コードにおけるｘ−およびｙ−位置をコード化する循環主列は、イメージに基づく位置をデコードする試みがなされるとき、後方を読み取るであろう。上述された変位の組み合わせおよびビットの対によって、デコードされたビットは、位置コードが上下逆に読み取られることから、反転されるであろう。
【００５２】
２）時計回り方向における９０度の回転によって、非回転行列におけるｘ−位置をコード化するビット列は、回転行列におけるｙ−位置をデコードする試みがなされるとき、後方を読み取るであろう、そして前記ビットは反転されるであろう。
【００５３】
３）時計回り方向における２７０度の回転によって、非回転行列におけるｙ−位置をコード化するビット列は、回転行列におけるｘ−位置をデコードする試みがなされるとき、後方を読み取るであろう、そして前記ビットは反転されるであろう。
【００５４】
このことは、もしも、正しい向きで正立状態にある非回転行列における部分列が、反転されることがなく且つ循環主数列において後方にあるならば、９０，１８０および２７０度の回転が検出され得ることを意味する。もしもそのような条件が前記主数列について満たされるならば、このことは、その長さがずいぶん減小され、今度はより少ない位置がコード化され得る。
【００５５】
この問題を解決するため、我々は、その代わりに、前記循環主数列のより長い部分列について、条件が満たされるようにさせる。このことは、実際の位置決定のために要求されるよりも長い部分列が、読み取られなければならないことを意味する。ある場合においては、そのようなより長い部分列は、読み取りの間に既に利用できる。もしも、位置についての座標をコード化する位置コードの最小のサブセットが二次式であるならば、この例における場合にそうであるように、読み取りデバイスが、位置コードに関係して４５度にわたって回転されたときでさえも、それが最小のサブセット全体をも含むように大きな位置コードの一部がいつも読み取られなければならない。それ故、位置決定のために要求されるものよりも長い少なくとも一つの部分列がいつも含まれる。このことは、図５に図解されており、そこでは、ドットに対応する各正方形５０およびグレーに影付けされた正方形が、二つの余分のドットと共に少なくとも一つの行および一つの列を常に読み取ることができることを図解している。
【００５６】
現在の例において、そこでは位置決定のための主数列の部分列は、長さ６を有し、長さ８の部分列が回転の検出のために使用され得る。これら８ビット長の部分列は、したがって、主数列内において後戻りおよび反転を生じることがないという特性を有する。この特性は、６４ビット長の主数列について達成され得ず、それが前記長さがその代わりに６３として選択される理由である。
【００５７】
上述された回転のうちの二つ、すなわち９０および２７０度において、正しい方向に回転する一列、そして誤った方向に回転する一列が読み取られるであろう。回転検出のための上述された方法によれば、第一の二つの読み取り方向（ｘおよびｙ）だけによって、回転エラーが検出されるであろう。該第二の読み取り方向において、正しく回転されたイメージの第一の読み取り方向における位置をコード化する循環移動がみられるであろう。
【００５８】
時計回り方向における９０度回転の場合において、正確に回転されたイメージのｙ−座標をコード化する循環移動は、ｘ−方向についてデコーディングするときにみられるであろう。したがって、それは、みられるｙ−方向の一次差分数列の部分列であるが、誤った方向に回転される（左から右への代わりに右から左へ移動する、そしてそれはｘ−方向の一次差分数列の部分列の場合である）。
【００５９】
対応する方法において、ｘ−方向の一次差分数列の部分列は、２７０度回転の場合にｙ−方向にデコーディングするときに、誤った方向に回転するであろうことがわかる。
【００６０】
なぜ部分列が誤った方向に回転するように見えるかという理由は、ｘ−およびｙ−方向の一次差分数列の相対的な方向性である。全体の位置コーディングパターンの縁部から始まり、ｙ−方向の一次差分数列が、反時計回り方向に移動する間に、ｘ−方向の一次差分数列が、時計回り方向に移動する。もしもそれらが同一の方向に走っていたら、それらは誤った方向には回転しないが、上述のケースにおいて正しい方向に回転する。
【００６１】
一次差分数列を反対方向に走らせることには多数の利点がある。一次差分数列の部分列が正しい回転をしているケースにおいては、「正しい」座標がデコードされるが、誤った方向においてである。この座標は、デコーディングに要求される一次差分数列からの六つの循環移動に対応するだけでなく、周囲の移動がデコードされる座標が正しいことを確認するであろう。一次差分数列が互いに反対方向に走っているケースにおいては、一次差分数列からの六つの循環移動もデコードされるが、誤った順序で、結果として誤って回転された一次差分数列の周囲部分に統計的に対応しないであろう座標を生ずる。この事実は、結果としてエラー検出についてより良い可能性を生ずる。
【００６２】
他の利点は、もしも一次差分数列が、互いに反対の方向に走っていれば、連続的なエラー、すなわち複数の連続するイメージが隣接する位置にデコードされるエラー、の危険が少ないことである。より詳細には、誤った方法で回転される一次差分数列における六つの循環移動の異なる隣接する組は、隣接する座標をコード化しない傾向がある。連続的なエラーは、そこでは正しくない座標の広がりが大きく、他のエラーよりも検出することが一層困難である。
【００６３】
回転の検出のために使用されるのと同一の基本原理が、エラー訂正のために使用され得る。主数列は、例えば、位置決定のために要求されるよりも長いいくつかの所定長さの部分列が、主数列内でビット反転されて生じないようにして選択され得る。もしも、そのようにより長い部分列における一を除く全てのビットが確実性をもって検出され得るならば、不正なビットは、訂正され得る。
【００６４】
位置コードのそのようなエラー検出およびエラー訂正特性は、主数列の理性的な選択によってかなり改善され得る。さらなる改善が、二次差分数列の選択によって達成され得る。
【００６５】
上述の例においては、主数列および二次差分数列が、付録Ａに示される方法で選択されている。
【００６６】
二次差分数列は、以下に述べる特別なエラー訂正特性を有している：
主数列の部分列の一つが、正しくなくデコードされ、そしてそれはデコードされた主数列における正しくない場所に導くと仮定されたい。各場所は二つの隣接する差分数を計算するために使用されるので、これらは、両方とも正しくないデコーディングによって影響されるであろう。もしも、差分数のいずれか一方が、使用される差分数範囲（５，５８）の外側にあれば、エラーは直ちに検出されるであろう。もしも、これがそのようなケースでなければ、しかしながら、一次差分数列の部分列が結果として生ずる四つの二次差分数列の部分列の組合せにおける少なくもと一つの部分列が、二つの隣接する位置にゆがめられるであろう。二つの第一の二次差分数列Ａ１およびＡ２の両方がベース３を有し、且つ使用されない差分数の数は、９＝３＊３であるので、これら二つの列のいずれか一つにおけるゆがみは、二つの影響された数の合計は、３を法としたいつも同一の値を有するという特性を有している。
【００６７】
二つの二次数列Ａ１およびＡ２は、単一の不適正な場所のデコーディングによって引き起こされる部分列の１４の可能性のある歪の多くとも一つにおける長さ７の各部分列について二次数列内に見出されるであろうという特性を有している。第三の二次数列Ａ３は、加えて、単一の不適正な場所のデコーディングによって引き起こされる部分列の１３の可能性のある歪の多くとも一つにおける長さ７の各部分列について、二次数列の中に見出されるであろうという特性を有している。第四の二次数列Ａ４は、２８の可能性のある歪の多くとも七つについての同一の特性を有している。検出される主数列の部分列の単一の正しくないデコーディングの可能性は大きい。
【００６８】
選択された列によれば、４１０８１５３４８の異なる位置の合計が、セクションの各次元にコード化され得る。コード化され得る異なるセクションの数は、上述された通り６３２である。したがって、コード化され得る位置の合計数は、６３２＊４１０８１５３４８２＝６．７＊１０２０位置である。
【００６９】
もしも、各位置が、０．３＊０．３ｍｍ２の面に対応するならば、これは６０００万ｋｍ２の面上にコード化され得る特有の位置に対応する。位置コードによって理論的にコード化され得る全ての特有の点によって作られるこの面は、仮想面と呼ばれ得る。位置コードがコード化される座標は、それ故仮想面上の点についての絶対座標である。位置コードの部分は物理的ベースまたは面上に適用され得る。それから、位置コードは、このベース上で位置をコード化する。しかしながら、座標は、通常、物理ベース上の位置についての絶対座標に関連しないが、仮想面上の点について関連している。
【００７０】
〔位置コーディングの実際的な例〕
以下において、実際に位置コーディングがどのようにして実現されるかが説明されるであろう。標準的には、ユーザは、座標０からそして上方向きに全ての位置コードをプリントすることには関心がないが、ユーザは、むしろ特定の座標エリアが割り当てられており、それは特定のアプリケーションのために使用され得る。そこで実際的な問題は、この特定の座標エリアについてどのように位置コードが決定されるかである。
【００７１】
位置コードは、いくつかの適切なタイプのプロセッサユニットから構成し得るコーディングデバイスにおいて決定されまたは生成され得る。それから、前記プロセッサユニットは、実際のプロセッサ、作業メモリおよび位置コードを決定するための命令群を有するコンピュータプログラムが格納されるプログラムメモリを具備している。前記プロセッサユニットは、典型的なパーソナルコンピュータに、プリンターにまたは何らかの他の適切なデバイスに組み込まれ得る。前記コーディングデバイスは、その代わりに、ＡＳＩＣ（アプリケーション特定集積回路）またはＦＰＧＡ（フィールドプログラマブルゲートアレイ）またはこの特定のタスクのために適するように適用され得る同様のユニット、またはディジタルおよび／またはアナログ回路またはそれらの何らかの適切な組み合わせからなるような特定目的のハードウェアからなることもできる。
【００７２】
有意的に生成する位置コードの最小の部分は、単一の点についての座標をコード化した部分である。この例においては、これは６＊６変位値による行列を生成することに対応し、それは通常のラスタにおけるそれらのそれぞれのラスタ点から６＊６ドットの変位で記述する。
【００７３】
しかしながら、しばしば、複数の点についての座標をコード化する位置コードのサブセットの生成、すなわちより大きな行列、が要求される。
【００７４】
前記コーディングデバイスへの入力信号は、通常のケースでは六つのパラメータからなることができる：
ｘ：位置コードにおける左に最も遠い列についてのｘ−座標である。
【００７５】
ｙ：最上部の行についてのｙ−座標である。
【００７６】
ｘｓ：ｘ−位置コードについて使用される位置コードのセクションを示す。
【００７７】
ｙｓ：ｙ−位置コードについて使用される位置コードのセクションを示す。
【００７８】
幅：それは、位置コードにおける列の数、すなわちｘ−方向における座標エリアのサイズを示す。
【００７９】
高さ：それは、位置コードにおける行の数、すなわちｙ−方向における座標エリアのサイズを示す。
【００８０】
これらのパラメータは、ユーザによってまたは外部ユニットからコーディングデバイスに入力される。オプション的に、変位値によって満たされることとなる行列に対するポインタも含まれ得る。さもなければ、行列についてメモリが割り当てられる。
【００８１】
コーディングデバイスのタスクは、行列における各点を、ベース上にプリントされるべき位置コードにおける変位されるべきドットの方位を示す変位値Ｏに関連付けることにある。
【００８２】
この例においては０〜３であり得る変位値Ｏが、上述において説明してきたように、第一のビットは、現在点についてのｘ−位置コードの値からなるとともに、第二のビットは、現在点についてのｙ−位置コードの値ｍｘからなる、一対のビットにおけるビットによって、決定される。もしも、一対のビットが既知であれば、変位値は、ビットの対を変位値に変換するテーブルＯ内において検索され得る。
【００８３】
ｘ−位置コードの値ｍｘは、もちろん、ｘおよびｙ上であって、我々が位置を定められる点に依存するが、位置コードの現在セクション上である。したがって、ｍｘ＝ｍｘ（ｘ，ｘｓ，ｙ）である。対応する方法にて、ｙ−位置コードの値ｍは、ｘおよびｙ上であって、我々が位置を定められる点に依存し、そしてｙ−位置コードの現在セクション上である。したがって、ｍｙ＝ｍｙ（ｙ，ｙｓ，ｘ）である。
【００８４】
もしも我々が、どの場所ｓにおいて前記循環主数列が、セクションｘｓにおける列ｘにおいて始まるかを決定し、且つ我々がｙ（ここで結果は主数列の長さを法としてとられる）を付加すれば、我々は、そこで我々がｘ−コーディングについて点ｘ、ｙに位置を定められた前記主数列における場所を得る。我々は、それからこの場所を有し且つそれ故点ｘ、ｙにおけるｘ−コーディングの値からなる主数列における数（ビット）を主数列のテーブルＭにおいて検索し得る。このことは、ｍｘ（ｘ，ｙ，ｘｓ）＝Ｍ［（ｓ（ｘ，ｘｓ）＋ｙ）（ｍｏｄ  ６３）］として表現され得る。
【００８５】
対応する操作を実行することによって、ｙ−コーディングの値が点ｘ，ｙにおいて見出され得る。このようにして、我々は、それから行列における点ｘ，ｙにおいて格納されるべき変位Ｏが決定されるべき、対をなすビットをアクセスする。
【００８６】
コーディングデバイスが計算する必要があるのは、したがって、まずその場所ｓにおいて主数列が列ｘについて始め、該列ｘは、点ｘ，ｙについての座標をコード化する位置コードのサブセットにおける左に最も遠い列である。他の言葉で言えば、列ｘにおける主数列について循環移動が計算されるといわれ得る。
【００８７】
このことは次のようにして実行され得る。
【００８８】
差分数ｄ（ｘ）が、列ｘにおける第一の部分列の主数列における場所によって、先に示されたように、そして隣接する列ｘ＋１における第一の部分列が定義される。より詳細には、それは、次のようなケースである：
ｄ（ｘ）＝（ｓ（ｘ＋１，ｘｓ）−ｓ（ｘ，ｘｓ））（主数列の長さを法とする）
ここで、ｓ（ｘ，ｘｓ）は、それ故、位置コードのセクションｘｓにおける列ｘにおける主数列または主数列についての循環移動における場所である。
【００８９】
定義として、さらに、ｓ（０，ｘｓ）＝ｘｓなるケースであり、ｘ−位置コードにおける特に最初の列における主数列についての循環移動である。
【００９０】
これに基づいて、ｓ（ｘ，ｘｓ）が、それ故、ｓ（ｘ，ｘｓ）＝（ｘｓ＋ｓｕｍ（ｊ＝０…ｘ−ｌ）ｄ（ｊ））（主数列の長さを法とする）として決定される。
【００９１】
実際には、多くの点についての座標をコード化する位置コードのための全てのｘについて座分数の値ｄ（ｘ）を定義する一次差分数列を格納することができないので、今一次差分数列における各差分数が、二次差分数列の各々から一つの数の組み合わせ上にマップ可能であるという事実が利用される。ここに、一般的なケースは次のようになる：
ｄ（ｘ）＝ｄｃ（１，ｘ）＋ｂ１＊ｄｃ（２，ｘ）
＋…＋ｂ１＊…＊ｂｎ−１＊ｄｃ（ｎ，ｘ）
ここで、ｎは、二次差分数列の数であり、そして、ｂｉは、ｉ＝１〜ｎ−１についての差分数列ｉにおけるベースであり、ｄｃ（ｉ，ｘ）は、差分数列ｉにおける数によってテーブルＤＣｉにおいて検索されることによって決定され得て、したがってｄｃ（ｉ，ｘ）＝ＤＣｉ［差分数列の長さｉを法とするｘ］である。もしもたった二つの二次差分数列しかなければ、もちろん上述における最初の２項のみが用いられることは、指摘されるべきである。
【００９２】
問題のケースにおいては、それ故我々は、次を得る：
ｄ（ｘ）＝５＋ｄｃ（１，ｘ）＋３＊ｄｃ（２，ｘ）
＋９＊ｄｃ（２，ｘ）＋１８＊ｄｃ（３，ｘ）
但し、定数５は、範囲５〜５８における差分数が用いられているという事実に由来している。
【００９３】
種々の二次差分数列からの寄与は独立であるので、各二次差分数列について分離された差分ｘまでの全ての差分数の合計が計算され得る。図２において、まるでそれが場所ｘまでの全ての差分数が各列について分離されて合計されたように見られ得る。
【００９４】
実際には、この合計は、定数およびテーブルの使用によって容易に決定され得る。前記二次差分数列の全ての循環期からの寄与は、実際に一定であり且つそれ故、あらかじめ決定されそして定数として格納され得る。これらの定数はここではＤＣＣＳｉとしてあらわされる。差分数列の不完全な循環からの寄与は、あらかじめ決定されそしてテーブルに格納されることもでき、該テーブルは、それぞれ二次差分数列における各場所について、この場所までそしてこの場所を含めて差分数の合計を与える。このテーブルは、ここにＤＣＩＣＳｉとあらわされる。定数項５からの寄与は、５＊ｘである。
【００９５】
ｓｕｍ（ｊ＝０…ｘ−ｌ）ｄ（ｊ）の項は、それ故、各二次差分数列について次のようにして決定され得る。
【００９６】
ＤＣＣＳｉ＊（ｘ  ｄｉｖ  ｌ（ｉ））＋ＤＣＩＣＳｉ［ｘ（ｍｏｄ  ｌ（ｉ））］
ここで、ｌ（ｉ）は、二次差分数列ｉの長さである。
【００９７】
ｓ（ｘ，ｘｓ）が決定されたとき、点ｘ，ｙにおけるｘ−位置コードは、それ故、上述されたように、ｙの既知の値の使用およびテーブル参照によって決定され得る。
【００９８】
ｘ−位置コードにおける後続の列について、もちろん、ｓ（ｘ，ｘｓ）は、上述されたように決定される必要がないが、代わりにｓ（ｘ，ｘｓ）が既知であり、次の関係を用いてｓ（ｘ＋ｌ，ｘｓ）が計算されるという事実が利用される。
【００９９】
ｄ（ｘ）＝（ｓ（ｘ＋１，ｘｓ）−ｓ（ｘ，ｘｓ））（主数列の長さを法とする）
ｄ（ｘ）＝５＋ｄｃ（１，ｘ）＋ｂ１＊ｄｃ（２，ｘ）
＋…＋ｂ１＊ｂ２…＊ｂｍ−１＊ｄｃ（ｍ，ｘ）
ｄｃ（ｉ，ｘ）＝ＤＣｉ［差分数列ｉの長さを法とするｘ］
この手順が、それから、入力パラメータ「幅」に従って所要の列について繰り返される。
【０１００】
ｓ（ｙ，ｙｓ）は、ｓ（ｘ，ｘｓ）についてと対応する方法で決定され、そして入力パラメータｘを用いて、点ｘ，ｙにおけるｙ−位置コードの値も決定され得る。
【０１０１】
これら両方の値が得られたとき、点ｘ，ｙにおける変位が、テーブルＯ内が参照されることによって決定され得る。
【０１０２】
位置をコード化するために、コーディングデバイスが、それ故、次のテーブルおよび定数を使用し得る：
Ｍ：列内の異なる場所での主数列における数。
【０１０３】
Ｏ：異なるビットの対についての変位（０〜３）。
【０１０４】
ＤＣｉ：列内の異なる場所での二次差分数列ｉにおける数。
【０１０５】
ＤＣＩＣＳｉ：二次差分数列ｉの不完全な循環期の各々における数の合計。
【０１０６】
加えて、次の定数が格納され得る：
ＤＣＣＳｉ：二次差分数列ｉにおける全ての数の合計。
【０１０７】
ｌ（ｉ）：二次差分数列ｉの長さ。
【０１０８】
Ｋ：主数列の長さ。
【０１０９】
位置コーディングのための単純なフローチャートが図６に示されている。最初に、ステップ６００において、入力信号が、ｘ，ｙ，ｘｓ，ｙｓ，幅，高さの形態で受信される。その後に、ｘ−行列およびｙ−行列がｘよりはむしろｙまたはその逆のいずれかによって並列的にまたは逐次的に決定され得る。このことは、並列フローによってフローチャートに示されている。ステップ６０５において、循環移動ｓ（ｘ，ｓｘ）が、ｘ−位置コーディングにおける第１列について最初に決定される。その後に、ステップ６１０において、循環移動ｓ（ｘ＋ｌ，ｘｓ）が、第２列について決定される。その後、ステップ６１５においておよびステップ６２０においてｘ＝ｘ＋ｌが適用され、全ての幅について、すなわち全ての列について、循環移動が決定されたか否かが調べられる。もしも、それがそのケースでなければ、フローはステップ６１０に戻り、そしてこのステップおよびステップ６１５が繰り返される。もしも、それがそのケースならば、ステップ６２５において、テーブル参照によってｘ−行列におけるビット値が決定される。対応する方法においては、ステップ６３０〜ステップ６５０においてｙ−行列についてのビット値が決定される。最後にｘｙ−行列についての変位がステップ６５５においてテーブル参照によって決定される。
【０１１０】
これは、もちろん、位置コーディングがどのように実行され得るかの、まさに粗く概略的な例であり、そして実際には、それは多くのやり方に変更され得る。例えば、点についてのビットの対および対応する変位が、点について循環移動が決定されると直ちに継続的に決定される。結果として、ｘ−およびｙ−行列をバッファする必要はない。
【０１１１】
該方法は、コンピュータプログラムとして実行されることが可能である。コンピュータプログラムからの出力信号は、変位値を伴うｘｙ−行列が正確である必要はないが、しかしその代わりに位置コードを作成する主数列の部分列の何らかの他の指示からなることが可能である。
【０１１２】
〔位置デコーディングの実際の例〕
位置コードは、位置コードを読み取るためのセンサ、および何らかの適切なタイプのプロセッサユニットを有し得るデコーディングデバイスにおいてデコードされ得る。プロセッサユニットは、実際のプロセッサ、作業メモリおよび、位置コードをデコーディングするための命令群を有するコンピュータプログラムがそこに格納される、プログラムメモリを備えている。前記プロセッサユニットは、典型的なパーソナルコンピュータに、手持ち読み取りデバイスにまたは何らかの他の適切なデバイスに組み込まれ得る。前記デコーディングデバイスは、その代わりに、ＡＳＩＣまたはＦＰＧＡまたはこの特定のタスクのために適するように適用され得る同様のユニット、またはディジタルおよび／またはアナログ回路またはそれらの何らかの適切な組み合わせからなるような特定目的のハードウェアからなることもできる。
【０１１３】
デコーディングデバイスの特定の例が以下において説明されるであろう。
【０１１４】
以下の記述は図７のフローチャートに言及している。
【０１１５】
デコーディングデバイスへの入力信号は、位置コードの検出されたサブセットのイメージまたは他の何らかのディジタル表現からなっており、そのサブセットは、少なくとも一点についての座標をコード化している、ステップ７００。この例においては、位置コードは、上述されたように、ラスタにおけるラスタ点に関連する所定の方法にて変位された、ドットによりグラフィカルに表現される。
【０１１６】
デコーディングの最初のステップにおいては、デコーディングデバイスが、例えば閾値弁別を用いることによって、イメージにおけるドットを識別し、ラスタをドットに合わせる、ステップ７０５。ラスタは、例えば、異なるドットの対の間における距離の利用によって、本出願人の国際特許出願ＷＯ  ０１／２６０３４に記述された方法によって、または代わりにフーリエ変換の利用による国際特許出願ＷＯ  ０１／７５７８３に記述された方法で決定され得る。各ラスタ点について、関連付けられたドットの変位が決定され、変位に依存する値０〜３が与えられる。少なくともサイズが（ｎｌ＋１）＊（ｎｌ＋ｌ）の行列が選択され、ここで、ｎｌは、位置決めのために使用される主数列の部分列の長さであり、その場所は、主数列内に明確に決定される。当該例に関連して、８＊８行列が選択される（（ｎｌ＋２））＊（ｎｌ＋２））。この行列は、変位値をビットの対に変換するテーブルＯＩにおいて検索されることによって、ビットの対に変換される変位値によって、ｘ−行列（ｘ−位置コードとも呼ばれる）およびｙ−行列（ｙ−位置コードとも呼ばれる）に分離される、ステップ７１０。各ビット対における最初のビットはｘ−行列を形成し、且つ各ビット対における第二のビットは、ｙ−行列を形成する。
【０１１７】
次のステップにおいて、ｘ−およびｙ−行列の回転の四つの可能性のあるタイプ（０，９０，１８０および２７０度）は、調査され且つ現在の回転が決定される、ステップ７１５。主数列において失われた長さ８の部分列が生じ、行列の不完全な回転の場合には、先に述べられた事実が用いられる。
【０１１８】
同時に、ある度合いのエラー訂正が長さ８の部分列に基づいて実行される。
【０１１９】
正しい回転が決定されたとき、次のステップにおいて、中間にあり且つ正しい方法で回転されそしてｎｌ＊ｎｌなるサイズ、すなわちこの例においては二つの６＊６行列、を有する、ｘ−およびｙ−行列のみが使用される。ｘ−行列およびｙ−行列が、図７における並列フローによって示される、ｘに先だってｙまたはその逆を用いて並列的にまたは逐次的にデコードされる。
【０１２０】
ｘ−行列のデコーディングの第一のステップ７２０において、一次差分数列の部分列が決定され、それは図７において、一次部分列と呼ばれる。より詳細には、ｘ−行列において、行列内の列におけるビットが、主数列の部分列を構成する。主数列における対応する場所は、部分列を場所に変換するテーブルＭＩ内が参照されることにより決定される。その後に、差分数は、主数列の部分列によってコード化された差分数が決定される。この例においては、それらは数において５である。より詳細には、隣接する部分列の場所の間の差分ｄとして差分数が決定され、前記差分は主数列の長さを法として決定される。
【０１２１】
そのようにして取得される差分数の列は、一次差分数列の部分列であり、それはｘ−方向についてのコーディングのために使用されるが、そのサイズのために、デコーディングデバイスには格納されない。その代わりに、各部分列が二次差分数列の各々からの部分列の組み合わせに変換され得る一次差分数列の特性の使用がなされる。ステップ７２５において、一次差分数列が、そのように二次部分列に変換される。より詳細には、各差分数は次のように書き換える：
ｄ＝ｄｌ  ＋ｂ１＊ｄ２＋…＋ｂ１＊ｂ２…＊ｂｎ−１＊ｄｎ
ここで、ｎは二次差分数列の数であり、そしてｂｉは、二次差分数列ｉ内におけるベースである。これに関する例は、次のようになる：
ｄ＝５＋ｄ１＋３＊ｄ２＋９＊ｄ３＋１８＊ｄ４
ここで、ｄ１〜ｄ４は、整数除算またはテーブル参照によって決定され得る。
【０１２２】
一次差分数列のデコードされた部分列における五つの数の各々は、それ故結果として四つの数ｄ１，ｄ２，ｄ３，ｄ４となる。したがって、第一の二次差分数列の部分列を形成する五つのｄ１数が得られ、第二の二次差分数列の部分列を形成する五つのｄ２数が得られ、第三の二次差分数列の部分列を形成する五つのｄ３数が得られ、そして第四の二次差分数列の部分列を形成する五つのｄ４数が得られる。例が、下に与えられる：
ｄ    ２３  ４５  ５１  ９  ３７
ｄｌ    ２    ０    ０  ０    １
ｄ２    １    ０    ２  ０    ０
ｄ３    ０    １    １  １    ０
ｄ４    １    ２    ２  ０    ２
二次差分数列の部分列のそれぞれの場所は、それぞれの二次差分数列の部分数列をそれぞれの二次差分数列における場所に変換する四つのテーブルＤＣＩｉを参照することによって決定される、ステップ７３０。
【０１２３】
各部分列について、場所ｐｉがそのように得られる。これらの場所について、次のような場合がある：
Ｐ＝ｐ１  （ｍｏｄ  １１）
Ｐ＝ｐ２  （ｍｏｄ  １２）
Ｐ＝ｐｍ  （ｍｏｄ  １ｍ）
但し、Ｐは、座標ｘに対応する一次差分数列における場所、ｐｉは、二次差分数列における場所、ｌｉは、二次差分数列ｉの長さ、そしてｍは、二次差分数列の数である。
【０１２４】
この式のシステムは、よく知られた中国の余剰定理を用いて解決され得る、それについては、例えばＮｉｖｅｎ，Ｓｕｃｋｅｒｍａｎに非常に詳細に説明されており、数の理論への導入はＳｐｒｉｎｇｅｒ  Ｖｅｒｌａｇに説明されている。こうして、ステップ７３５において、ｘが決定される。
【０１２５】
定義Ｌ＝ｐｒｏｄ（ｉ＝１，ｍ）ｌｉおよびｑｉ＊（Ｌ／ｌｉ）＝ｌ（ｍｏｄ  ｌｉ）
一次差分数列における場所Ｐは、次のようにして得られる：
Ｐ＝（ｓｕｍ（ｉ＝１，ｎ）（（Ｌ／ｌｉ））＊ｐｉ＊ｑｉ））（ｍｏｄ  Ｌ）
関連する例において
Ｌ＝１１＊１２＊１３＊１４＝２３６＊２３３＊３１＊２４１＝４１０８１５３４８    および
ｑ１＝１３５
ｑ２＝１４５
ｑ３＝１７
ｑ４＝６２
が得られる。
【０１２６】
もしも、二次差分数列の部分列について例えば、場所ｐ１＝９７；ｐ２＝１７６；ｐ３＝３およびｐ４＝２１１が得られるならば、一次差分数列における対応する場所は、中国の余剰定理に従って１７０３２６９６１となるであろう。
【０１２７】
Ｐが決定されているとき、次のステップは、場所が属するｘ−セクションを決定することである。これは、最初にｙ＝０という仮定のもとに、そしてｓ（ｘ，０）の計算によって実行され、それはｘｓ＝０についての列ｘのための部分数列の主数列における場所である。
【０１２８】
ｓ（ｘ，０）は、位置ｘについての位置コードの決定に関連して上述されたのと同様に二次差分数列を用いて計算される。もしも、ｓ（ｘ，０）が、Ｘ方向についての位置決めのために使用される六つの部分数列の第一の部分数列の場所から引かれると、ｙ＝０についてｘｓ  が得られる。
【０１２９】
ｙ−行列は、ｘ−行列に先だって、それと並列的にあるいはそのデコードの後にデコードされ、一次差分数列における場所は、ｘ−方向についての上述された対応する方法にて、図７におけるステップ７４０〜７５５に従って、ｙ−方向について決定される。加えて、関連するｙ−セクションｙｓがｘ−セクションについて上述されたのに対応する方法で計算されるが、ｘ＝０の仮定のもとである。最後に、ステップ７６０において、ｘｓは、ｙを考慮して決定され、且つｙｓは、ｘを考慮してｙ（主数列の長さを法として）を減算することによって、ｘｓからｙ＝０について決定され、そしてｘ（主数列の長さを法として）を減算することによってｙｓからｘ＝０について決定される。
【０１３０】
次のテーブルは、したがって、位置コードをデコードするために使用され得る：
ＭＩ：それは、主数列の部分列を主数列の場所に変換する、
ＤＣＩｉ：それはｎの二次差分数列の各々の部分列を、ｎの二次差分数列における場所に変換する、そして
ＯＩ：それは変位値をビット対に変換する。
【０１３１】
図７におけるフローチャートは位置デコーディングが、例えばコンピュータプログラムにおいて、どのように実現され得るかの粗い概略的な例であることは強調されるべきである。
【０１３２】
〔ハンドヘルド読み取りデバイスの例〕
位置コードは、種々のタイプの読み取りデバイスによって読み取られ且つデコードされ得る。そのようなデバイスは、位置コードのディジタル表現を達成するためのセンサ、およびディジタル表現における位置コードを識別し且つこれをデコードするための手段を有し得る。これらの手段は、上述されたように、メモリを有するプロセッサ、および適切なプログラムまたは特別な目的のためのハードウェアまたは、ディジタルおよび／またはアナログ回路、または何らかのそれらの組み合わせから構成することができる。
【０１３３】
読み取りデバイスの例が図８に示されている。それは、ペンとほぼ同様の形状をなすケーシング１１を備えている。ケーシングの短寸側部には、開口１２がある。短寸側部は、位置決定が実行されるべき面に対して接触させまたはそこから短い距離で保持することを意図している。
【０１３４】
ケーシングは、主として光学部分、電子的回路構成部分および電源を収容している。
【０１３５】
光学部分は、イメージングされるべき面を照明するための少なくとも一つの発光ダイオード１３および二次元イメージを記録するための例えばＣＣＤまたはＣＭＯＳセンサ等の光感応性エリアセンサ１４を備えている。付加的に、デバイスは、ミラーおよび／またはレンズ系のような光学系を含んでいてもよい。発光ダイオードは、赤外発光ダイオードであってもよく、そしてセンサが赤外光に感応性を有していてもよい。
【０１３６】
デバイスのための電源は、ケーシングにおける分離された区画室内に搭載されたバッテリ１５から得る。外部電源からケーブルを介して電力供給を得ることも可能である（図示せず）。
【０１３７】
電子的回路構成部は、センサからイメージを記録し且つこれらのイメージに基づいて位置決定を実行するようにプログラムされたプロセッサ、ならびに作業メモリおよびプログラムメモリも有するプロセッサユニットを含んでいる。
【０１３８】
この実施の形態において、デバイスは、その上で位置決定が実行されるべき面上にその助けを借りて通常の顔料ベースの筆記が描出され得るペンポイント１７も具備している。ペンポイント１７は、ユーザがそれが使用されるか否かをコントロールできるように延長および折りたたみ収納が可能である。すべてのアプリケーションにおいて、デバイスはペンポイントを有する必要はない。
【０１３９】
顔料ベースの描出は赤外光に対して透過性があるタイプが適しており、マークが赤外光を吸収することが適している。赤外光を射出する発光ダイオードを用い且つ赤外光に感応性を有するセンサを用いることにより、パターンの検出が、上述されたパターンとの描出干渉なしに実行され得る。
【０１４０】
デバイスは、それによってデバイスが起動され且つ制御され得るボタン１８も備えることもできる。例えば赤外光、ラジオ波または超音波を用いてデバイスへおよびデバイスからの情報のワイヤレス通信のためのトランシーバ１９も持っている。デバイスは、位置または記録された情報を表示するためのディスプレイ２０を備えることもできる。
【０１４１】
デバイスは、異なる物理的ケーシングに分割されることもでき、第一のケーシングは、位置コーディングパターンのイメージの記録に必要な構成要素およびこれらを第二のケーシングに収容されおよび記録されたイメージ／イメージ群に基づいて位置決定を実行する構成要素に送信するための構成要素を収容する。
【０１４２】
〔代替的実施の形態〕
上述の実施の形態においては、位置コードが二次元において位置をコード化するものとして説明された。しかしながら、位置コードは、一次元の位置をコード化するために使用されるようにすることもできる。上述の例においては、例えば、位置コードの「ストリップ」は、ｙ＝０によってｘ−軸に沿って使用されるようにすることもできる。代わりに、ｘ−コーディング行列のみが使用されるようにすることもできる。このケースにおいては、二進主数列によれば我々はグラフィカルに０または１のコードのみが必要であるという理由のために、行列における各点が、たった一つの値を持つであろう。
【０１４３】
一次元位置コーディングの使用は、バーコードと等価とすることができる。
【０１４４】
上述の実施の形態において、二進主数列が使用される。それは、しかしながら、主数列のための異なるベースの使用も可能である。そこで、このことは、結果として、位置コーディング行列における各点においてコード化されることが必要ないくつかの異なる値を生じ得る。
【０１４５】
上述の実施の形態においては、同一の主数列および同一の二次差分数列が、ｘ−方向およびｙ−方向におけるコーディングのために使用される。これは、必要ではない。異なる次元におけるコーディングのために異なる列が使用され得る。列のためのテーブルの格納のためのメモリスペースの必要を予想して、しかしながら、全ての方向についてのコーディングのために同一の列を使用することは利点とすることができる。
【０１４６】
上述の実施の形態において、６＊６ドットまたはシンボルが位置のコーディングのために使用される。当然、より少ないまたは多いシンボルを使用され得る。両次元に同一数のシンボルが使用される必要はない。
【０１４７】
上述の実施の形態において、一次差分数列の部分列が、部分数列の組み合わせ上に、全単射的にマップされ、且つ二次差分数列の部分数列の組み合わせが、一次差分数列の部分列上に、全単射的にマップされる。これは、必要ではない。一次差分数列の異なる部分列は、二次差分数列の部分列の同一の組み合わせ上にマップされることができる。部分列の組み合わせ上にマップされない一次差分数列の部分列が存在し得る。一次差分数列よりも多い部分列の組み合わせも存在し得る。上述の実施の形態において、ラスタは直交グリッドである。それは、ロンビックグリッドのような、例えば６０度角度グリッド、三角グリッドまたは六角形グリッド等の他の形態を持っていてもよい。
【０１４８】
例えば六角形仮想ラスタに沿う３方向における変位についての、四つの方向より少ないまたはより多い方向の変位によるグラフィカルなコーディングが使用され得る。六角形ラスタにおいては、ラスタの再形成を容易にするためにただ二つの変位が使用され得る。
【０１４９】
上述の実施の形態において、差分数がゼロに近づくのを回避するために（５，５８）の範囲の差分数が使用される。しかしながら、例えば、差分数３および４を含む他の範囲も使用され得る。
【０１５０】
上述の実施の形態において、パターンは光学的に読み取り可能であり、そしてセンサも光学的である。しかしながら、パターンは、光学パラメータとは異なるパラメータに基づくこともできる。そのような場合において、センサはもちろんそれに関するパラメータを読み取ることができるタイプからなっていなければならない。そのようなパラメータの例は、化学的、音響的または電磁的パラメータである。容量性または誘導性パラメータも使用され得る。
【０１５１】
製品は、一枚の紙によって上述に例示されている。しかしながら、それは上述のパラメータのいずれかを用いて位置コードが適用され得るいかなる製品であってもよい。もしも、位置コードが光学的であれば、それは、例えば、プリンタによってプリントアウトされまたは通常のプリント技術を用いて製品上にプリントされることもできる。
【０１５２】
〔付録Ａ〕
主数列Ｍ：
０，０，０，０，０，０，１，０，０，１，１，１，１，１，０，１，０，０，１，０，０，０，０，１，１，１，０，１，１，１，０，０，１，０，１，０，１，０，０，０，１，０，１，１，０，１，１，０，０，１，１，０，１，０，１，１，１，１，０，０，０，１，１
二次差分数列：
Ａ１＝０，０，０，０，０，１，０，０，０，０，２，０，１，０，０，１，０，１，０，０，２，０，０，０，１，１，０，０，０，１，２，０，０，１，０，２，０，０，２，０，２，０，１，１，０，１，０，１，１，０，２，０，１，２，０，１，０，１，２，０，２，１，０，０，１，１，１，０，１，１，１，１，０，２，１，０，１，０，２，１，１，０，０，１，２，１，０，１，１，２，０，０，０，２，１，０，２，０，２，１，１，１，０，０，２，１，２，０，１，１，１，２，０，２，０，０，１，１，２，１，０，０，０，２，２，０，１，０，２，２，０，０，１，２，２，０，２，０，２，２，１，０，１，２，１，２，１，０，２，１，２，１，１，０，２，２，１，２，１，２，０，２，２，０，２，２，２，０，１，１，２，２，１，１，０，１，２，２，２，２，１，２，０，０，２，２，１，１，２，１，２，２，１，０，２，２，２，２，２，０，２，１，２，２，２，１，１，１，２，１，１，２，０，１，２，２，１，２，２，０，１，２，１，１，１，１，２，２，２，０，０，２，１，１，２，２
Ａ２＝０，０，０，０，０，１，０，０，０，０，２，０，１，０，０，１，０，１，０，１，１，０，０，０，１，１，１，１，０，０，１，１，０，１，０，０，２，０，０，０，１，２，０，１，０，１，２，１，０，０，０，２，１，１，１，０，１，１，１，０，２，１，０，０，１，２，１，２，１，０，１，０，２，０，１，１，０，２，０，０，１，０，２，１，２，０，０，０，２，２，０，０，１，１，２，０，２，０，０，２，０，２，０，１，２，０，０，２，２，１，１，０，０，２，１，０，１，１，２，１，０，２，０，２，２，１，０，０，２，２，２，１，０，１，２，２，０，０，２，１，２，２，１，１，１，１，１，２，０，０，１，２，２，１，２，０，１，１，１，２，１，１，２，０，１，２，１，１，１，２，２，０，２，２，０，１，１，２，２，２，２，１，２，１，２，２，０，１，２，２，２，０，２，０，２，１，１，２，２，１，０，２，２，０，２，１，０，２，１，１，０，２，２，２，２，０，１，０，２，２，１，２，２，２，１，１，２，１，２，０，２，２，２，
Ａ３＝０，０，０，０，０，１，０，０，１，１，０，０，０，１，１，１，１，０，０，１，０，１，０，１，１，０，１，１，１，０，１，
Ａ４＝０，０，０，０，０，１，０，２，０，０，０，０，２，０，０，２，０，１，０，０，０，１，１，２，０，０，０，１，２，０，０，２，１，０，０，０，２，１，１，２，０，１，０，１，０，０，１，２，１，０，０，１，０，０，２，２，０，０，０，２，２，１，０，２，０，１，１，０，０，１，１，１，０，１，０，１，１，０，１，２，０，１，１，１，１，０，０，２，０，２，０，１，２，０，２，２，０，１，０，２，１，０，１，２，１，１，０，１，１，１，２，２，０，０，１，０，１，２，２，２，０，０，２，２，２，０，１，２，１，２，０，２，０，０，１，２，２，０，１，１，２，１，０，２，１，１，０，２，０，２，１，２，０，０，１，１，０，２，１，２，１，０，１，０，２，２，０，２，１，０，２，２，１，１，１，２，０，２，１，１，１，０，２，２，２，２，０，２，０，２，２，１，２，１，１，１，１，２，１，２，１，２，２，２，１，０，０，２，１，２，２，１，０，１，１，２，２，１，１，２，１，２，２，２，２，１，２，０，１，２，２，１，２，２，０，２，２，２，１，１．
【図面の簡単な説明】
【０１５３】
【図１】図１は、第一の方向におけるｘ−方向の位置についてのコーディングがどのようにして実行されるかを概略的に示している。
【図２】図２は、一次数列ＰＤが四つの二次数列Ａ１〜Ａ４によってどのようにして作られるかを概略的に示している。
【図３】図３は、位置コードのグラフィカルコーディングの例を示している。
【図４】図４は、拡張された位置コードによる製品を示している。
【図５】図５は、余分なシンボルが、エラー訂正の目的のために、どのように記録され得るかを示している。
【図６】図６は、フローチャートであり且つ位置コードがどのようにして決定され得るかの実施例を示している。
【図７】図７は、フローチャートであり且つ位置コードがどのようにしてデコードされ得るかの実施例を示している。
【図８】図８は、位置コードの読み取りおよびデコーディングのために使用され得るデバイスを概略的に示している。
【図１】
2004535011.tif 000004
【図２】
2004535011.tif 000005
【図３】
2004535011.tif 000006
【図４】
2004535011.tif 000007
【図５】
2004535011.tif 000008
【図６】
2004535011.tif 000009
【図７】
2004535011.tif 000010
【図８】
2004535011.tif 000011
【国際公開パンフレット】
2004535011.tif 000012
2004535011.tif 000013
2004535011.tif 000014
2004535011.tif 000015
2004535011.tif 000016
2004535011.tif 000017
2004535011.tif 000018
2004535011.tif 000019
2004535011.tif 000020
2004535011.tif 000021
2004535011.tif 000022
2004535011.tif 000023
2004535011.tif 000024
2004535011.tif 000025
2004535011.tif 000026
2004535011.tif 000027
2004535011.tif 000028
2004535011.tif 000029
2004535011.tif 000030
2004535011.tif 000031
2004535011.tif 000032
2004535011.tif 000033
2004535011.tif 000034
2004535011.tif 000035
2004535011.tif 000036
2004535011.tif 000037
2004535011.tif 000038
2004535011.tif 000039
2004535011.tif 000040
2004535011.tif 000041
2004535011.tif 000042
2004535011.tif 000043
2004535011.tif 000044
2004535011.tif 000045
2004535011.tif 000046
2004535011.tif 000047
2004535011.tif 000048
2004535011.tif 000049
2004535011.tif 000050
2004535011.tif 000051
2004535011.tif 000052
2004535011.tif 000053
2004535011.tif 000054
2004535011.tif 000055
2004535011.tif 000056
2004535011.tif 000057
2004535011.tif 000058
2004535011.tif 000059
2004535011.tif 000060
2004535011.tif 000061
2004535011.tif 000062
2004535011.tif 000063
2004535011.tif 000064
2004535011.tif 000065
2004535011.tif 000066
2004535011.tif 000067
2004535011.tif 000068
2004535011.tif 000069
2004535011.tif 000070
2004535011.tif 000071
2004535011.tif 000072
2004535011.tif 000073
【国際調査報告】
2004535011.tif 000074
2004535011.tif 000075
2004535011.tif 000076