【誤訳訂正書】
【提出日】平成20年8月18日(2008.8.18)
【誤訳訂正１】
【訂正対象書類名】特許請求の範囲
【訂正対象項目名】全文
【訂正方法】変更
【訂正の内容】
【特許請求の範囲】
【請求項１】
表面上に設けられたコーディングパターンの部分領域にコーディングされたデータを、読み取った前記部分領域の画像に基づいてデコーディングするデータデコーディングの方法であって、
前記コーディングパターンは、複数の要素を含んでおり、前記複数の要素の各々がとり得るデコーディング値は、少なくとも二つあり、
前記方法は、
前記画像内において、複数の要素を特定し、
特定した要素の各々について、その要素が前記少なくとも二つのとり得るデコーディング値のうちのそれぞれをとる確率を、各々のデコーディング値についての値確率として計算し、
前記デコーディング値および前記デコーディング値に対応する値確率に基づいて、データのデコーディングを実行することを特徴とする方法。
【請求項２】
前記データのデコーディングは、表面上の一つのポイントについて、座標を求めることを含む請求項１に記載の方法。
【請求項３】
前記データのデコーディングは、表面上の一つのポイントについて、二つの座標を求めることを含む請求項１に記載の方法。
【請求項４】
前記データのデコーディングは、前記特定した所定数の要素について、少なくとも第一組のデコーディング値を求めることを含む請求項１〜３のいずれか１項に記載の方法。
【請求項５】
複数のデコーディング値の組み合わせとして許容される組み合わせが、複数あり、
前記方法は、
読み取った画像の部分領域における複数の要素の並びが前記デコーディング値の許容される組み合わせをとる確率を、各々の組み合わせについての数列確率として計算することを含み、
前記計算は、前記第一組のデコーディング値についての値確率を用いて行われる請求項４に記載の方法。
【請求項６】
前記第一組のデコーディング値に対応する複数の要素の各々について、最も高い確率を値確率として有するデコーディング値を選択することと、
前記選択したデコーディング値に基づいて、前記データのデコーディングを実行することと、
を含む請求項４に記載の方法。
【請求項７】
前記第一組のデコーディング値に対応する複数の要素の各々について、前記コーディングパターンにより与えられた前記複数の要素のデコーディング値の間の関係についての条件に基づき、とり得るデコーディング値のうちの一つを選択することを含む請求項４に記載の方法。
【請求項８】
前記条件は、前記第一組に対応する複数の要素についての前記デコーディング値の許容される組み合わせを表す請求項７に記載の方法。
【請求項９】
前記許容される組み合わせは、循環主数列によって決定され、前記循環主数列は、所定の長さの相互に固有の部分数列のみを含んでおり、各部分数列は、前記許容される組み合わせの一つに対応している請求項５または８に記載の方法。
【請求項１０】
前記部分数列は、前記循環主数列において反転および逆転された形で表れることがない請求項９に記載の方法。
【請求項１１】
前記方法は、複数の要素の並びについての数列確率に基づいてデータのデコーディングを実行することを含み、
前記数列確率は、前記許容される組み合わせの一つに対応する並びの前記デコーディング値についての値確率に基づいて定められる請求項８に記載の方法。
【請求項１２】
最も高い確率を数列確率として与える前記並びの前記デコーディング値に基づいて、前記データのデコーディングを実行することを含む請求項１１に記載の方法。
【請求項１３】
各要素は、データの個別にデコーディング可能な二つの次元の各々について、少なくとも二つのとり得るデコーディング値を有しており、
前記第一組のデコーディング値は、前記データの第一の次元についての前記とり得るデコーディング値で構成されている請求項４〜１２のいずれか１項に記載の方法。
【請求項１４】
各要素は、少なくとも四つのとり得る要素値を有しており、前記要素値は、前記第一の次元のとり得るデコーディング値と、前記第二の次元のとり得るデコーディング値との異なる組み合わせに対応しており、
前記方法は、特定された要素の各々について、その要素が前記少なくとも四つのとり得る要素値のうちのそれぞれをとる確率を、各々の要素値についての値確率として計算することを含む請求項１３に記載の方法。
【請求項１５】
前記方法は、
前記第一組に対応する要素についてのとり得る要素値の各々を、前記第一の次元についてとり得る第一のデコーディング値と、前記第二の次元についてとり得る第二のデコーディング値とに分割することと、
前記第一と第二のデコーディング値の各々に、前記要素値の値確率を関連付けすることと、
を含む請求項１４に記載の方法。
【請求項１６】
前記とり得る要素値の分割は、前記要素値がとる基数よりも小さい基数をとる二つの数字として前記要素値を表現することによって実行される請求項１５に記載の方法。
【請求項１７】
一つの要素について前記とり得る要素値のうちの二つの要素値の分割を行うと、データの一つの次元につき、同一のとり得るデコーディング値が二つできる場合に、これらの要素値について計算された値確率のうち最も高い確率を、前記とり得るデコーディング値に割り当てる請求項１５または１６に記載の方法。
【請求項１８】
前記データのデコーディングは、さらに、前記特定した所定数の要素について、第二組のデコーディング値を求めることを含む請求項４〜１７のいずれか１項に記載の方法。
【請求項１９】
前記第二組のデコーディング値が、前記データの第二の次元についての前記とり得るデコーディング値で構成されており、
前記方法は、さらに、前記第二組の各デコーディング値に、対応する要素がこのデコーディング値を有する確率を示す値確率を割り当てることを含む請求項１８に記載の方法。
【請求項２０】
前記第二組のデコーディング値および前記第二組のデコーディング値に対応する値確率が、前記第一組のデコーディング値について行われるのと同じ方法で求められ、前記第二組のデコーディング値が、前記第一組のデコーディング値と同じ方法で求められる請求項１８または１９に記載の方法。
【請求項２１】
前記読み取った画像の複数の異なる回転に対応しかつ前記数列確率に基づいて定められる回転確率に基づいて、データのデコーディングを実行することを含む請求項５または１１に記載の方法。
【請求項２２】
前記読み取った画像の複数の異なる回転に対応しかつ前記特定された要素のデコーディング値に関する値確率に基づいて定められる回転確率に基づいて、データのデコーディングを実行することを含む請求項１〜３のいずれか１項に記載の方法。
【請求項２３】
前記最も高い回転確率に対応する前記画像の回転に基づいて、データのデコーディングを実行する請求項２１または２２に記載の方法。
【請求項２４】
各要素は、前記要素のとり得るデコーディング値と同一の少なくとも二つのとり得る要素値を有し、各要素値は、前記デコーディング値の値確率と同一の値確率を有する請求項１〜１２のいずれか１項に記載の方法。
【請求項２５】
前記特定した要素の各々は、少なくとも一つのマークを有し、前記要素値の値確率は、前記マークの理想的なサイズＲｉに対する前記マークのサイズに基づいて、計算される請求項１４または２４に記載の方法。
【請求項２６】
前記要素値の値確率は、理想サイズＲｉの各々について、ｅｘｐ（−（Ｒｉ−ｒ）２／ｖ）の関数であり、ここで、ｒは前記マークのサイズであり、ｖは定数である請求項２５に記載の方法。
【請求項２７】
前記特定された要素の各々は、少なくとも一つのマークを有し、前記マークは、基準システムにおける複数の基準ポイントのうち一つの基準ポイントに関連付けが可能であり、前記要素値の値確率は、前記マークが関連付けられている前記基準ポイントに対する位置に基づいて計算される請求項１４または２４に記載の方法。
【請求項２８】
前記値確率は、前記基準ポイントに属する前記関連付けられた複数の理想的な位置の各
々までの前記マークの距離によって定められる請求項２７に記載の方法。
【請求項２９】
各マークの前記値確率は、前記距離ｄｉの各々について、ｅｘｐ（−（ｄｉ）２／ｖ）の関数であり、ここで、ｖは定数である請求項２８に記載の方法。
【請求項３０】
前記基準システムは、ラスターであり、該基準ポイントは、前記ラスターにおける交差点として構成されたラスターポイントである請求項２７〜２９のいずれか１項に記載の方法。
【請求項３１】
前記データのデコーディングは、前記特定した所定数の要素について、少なくとも第一組のデコーディング値を求めることを含み、
前記第一組に対応する要素は、前記第一組についての情報分量を最大化するように選択され、前記情報分量は、前記第一組に対応する要素の前記要素値についての値確率に基づいて定められる請求項１４または２４に記載の方法。
【請求項３２】
表面上に設けられたコーディングパターンの部分領域にコーディングされたデータを、読み取った前記部分領域の画像に基づいてデコーディングするための処理手段を備えたデータデコーディングのためのデバイスであって、
前記コーディングパターンは、複数の要素を含んでおり、前記複数の要素の各々がとり得るデコーディング値は、少なくとも二つあり、
前記デバイスは、
前記画像内において、前記複数の要素を特定する手段と、
特定された要素の各々について、その要素が前記少なくとも二つのとり得るデコーディング値のうちのそれぞれをとる確率を、各々のデコーディングについての値確率として計算する手段と、
前記デコーディング値および前記デコーディング値に対応する値確率に基づいて、データのデコーディングを実行する手段と、
を備えることを特徴とするデバイス。
【請求項３３】
前記特定された所定数の要素について、少なくとも一組のデコーディング値を求める手段を備える請求項３２に記載のデバイス。
【請求項３４】
複数のデコーディング値の組み合わせとして許容される組み合わせが、複数あり、
前記デバイスは、
読み取った画像の部分領域における複数の要素の並びが前記デコーディング値の許容される組み合わせをとる確率を、各々の組み合わせについての数列確率として計算する手段を備え、
前記計算は、前記一組のデコーディング値についての値確率を用いて行われる請求項３３に記載のデバイス。
【請求項３５】
前記一組のデコーディング値に対応する複数の要素の各々について、前記コーディングパターンによって与えられた前記複数の要素のデコーディング値の間の関係についての条件に基づき、とり得るデコーディング値の一つを選択する手段を備える請求項３３または３４に記載のデバイス。
【請求項３６】
前記読み取った画像の複数の異なる回転に対応しかつ前記特定された要素のデコーディング値に関する値確率に基づいて定められる回転確率に基づいて、データのデコーディングを実行する手段を備える請求項３２に記載のデバイス。
【請求項３７】
請求項１〜３１のいずれか１項に記載の方法を用いて画像に基づいたデータデコーディ
ングを実行するための命令を備えるコンピュータプログラムが保存されたメモリ媒体。
【誤訳訂正２】
【訂正対象書類名】明細書
【訂正対象項目名】全文
【訂正方法】変更
【訂正の内容】
【発明の詳細な説明】
【発明の名称】データデコーディングの方法およびデバイス
【技術分野】
【０００１】
本発明は、表面上のコーディングパターンの部分領域にコーディングされたデータを、該部分領域の記録された画像に基づいてデコーディングするデータデコーディング方法に関する。該コーディングパターンは、複数の要素を含んでおり、複数の要素の各々がとり得るデコーディング値は、少なくとも二つある。本発明はさらに、表面上のコーディングパターンの部分領域に記録されたデータをデコーディングするための処理手段を備えたデータデコーディングデバイスに関する。さらに、本発明は、画像に基づいてデータをデコーディングする命令を備えたコンピュータプログラムが保存されているメモリ媒体に関する。本発明はさらに、画像のコーディングパターンに基づいたデータデコーディングに確率計算の使用に関する。
【背景技術】
【０００２】
製品上にコーディング形式で記録されているデータをデコーディングすることが望ましい状況が多くある。このようなデータデコーディングの一例は、コーディングパターンが設けられた表面上における位置を求めることである。このようにして位置を求めることは、例えば書き込み面上で読み取りペンを使用する際に有用である。
【０００３】
本願明細書中で参照により援用している本出願者の国際公開ＷＯ０１／２６０３２号公報には、位置を求めるためのデバイスと、表面にコーディングパターンを施した製品とについての記述がなされている。このデバイスは、表面の画像を記録し、画像内の所定数の記号を見つけ出し、各記号の値を決定し、これらの値に基づいてその表面上での位置を求めるように構成されている。
【０００４】
これ以外にも、例えば、特別な外観の複雑な記号によって各位置をコーディングする、様々なタイプの位置コード形式のコーディングパターンがある。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従来タイプのコーディングパターンをデコーディングする上で生じる問題の一つは、常に完全な正確性をもって記号の値を決定できないことである。コーディングパターンを表面上に印刷する際に、プリンタの制限された解像度により、記号が完全に正確には印刷されないということがある。例えば、記号が幾分変形されるか、またはその「正常な」位置から幾分変位してしまうことがあり得る。その記号の値を決定するのが記号の形状または位置である場合には、この変形および変位は、それぞれ記号の値を明確に決定することが困難になるかもしれないことを意味する。
【０００６】
さらに、時には、記号が全く印刷されないということも起こる。
【０００７】
記録される画像内における記号の位置と干渉する構造を自らが有する表面上にコーディングパターンを印刷する場合には、別の問題が生じる可能性がある。表面上の構造は、データデコーディングのためのデバイスによって、記号として認識され得る。また、コーデ
ィングパターンを印刷した表面上に、例えば埃のような形態の不純物が乗ってしまう場合もある。これらの不純物により、記録した画像内にノイズ記号が生じ、これが誤って画像内の記号として識別されてしまう可能性がある。さらに、画像を記録するためのセンサからのセンサノイズにより、画像内のノイズ記号が生じてしまうこともある。画像内のノイズ記号は、デバイスの構成要素の一つ、たとえばセンサ内の損傷した画素から発生する場合もある。したがって、上述した理由を考慮すると、記録した画像において、データがコーディングパターンからデコーディングできないおそれがある。
【課題を解決するための手段】
【０００８】
本発明の目的は、従来技術に関連した上述の問題を全体的または部分的に克服することである。
【０００９】
本発明によれば、この目的は、独立請求項に記述されている特徴を備えた方法、デバイス、メモリ媒体、使用の手段によって達成できる。従属請求項には好ましい実施形態が記載されている。
【００１０】
本発明の基本概念は、表面上のコーディングパターンに記録されているデータのデコーディングに確率計算を使用するというものである。
【００１１】
第一の態様によれば、本発明はデータデコーディングの方法に関する。この方法は、表面上にあるコーディングパターンの部分領域にコーディングされたデータを、記録した該部分領域の画像に基づいてデコーディングする。コーディングパターンは、複数の要素を含んでおり、複数の要素の各々がとり得るデコーディング値は、少なくとも二つある。この方法はさらに、画像内において複数の要素を特定することと、特定した要素の各々について、その要素がこのデコーディング値をとる確率を、各々のデコーディング値についての値確率として計算することと、デコーディング値および対応する値確率に基づいて、データのデコーディングを実行することと、を含む。
【００１２】
上述した理由のために、通常、表面上のコーディングパターン、および／または表面上の画像は完全に完璧ではない。要素は別のとり得るデコーディング値を有する確率があるため、通常、一つの要素につき一つのデコーディング値を１００％確実に決定することはできない。本発明によれば、各要素および各デコーディング値について、要素がそのデコーディング値をとる確率として、それぞれ値確率が計算される。一つの要素が明確に決定されれば、その明確に決定されたデコーディング値についてその要素の値確率が最大になり、一方、その要素の他の値確率が０になる。要素のデコーディング値が不明確であればあるほど、その要素のこれらの値確率間の差は小さくなる。そのため、コーディングパターン内の或る位置において一つの要素が欠けていれば、その要素についてのこれらの値確率は同等の高さになる。本発明は、コーディングパターンのエラーに比較的強いデコーディングを可能にする。
【００１３】
記録された画像内で、データのデコーディングに必要である所定数より多くの要素が特定されてもよい。そうすれば、デコーディングにおいて最も多くの情報が得られる所定数の要素を選択することができる。上述のとおり、これらの要素は、デコーディング値の一つについて支配的な値確率をとる要素である。その結果、殆ど情報が得られない要素を除外でき、記録された画像に基づいてデータをデコーディングできる確率が高くなる。
【００１４】
この方法はさらに、所定数の特定された要素について少なくとも第一組のデコーディング値をデコーディングする。
【００１５】
この方法はさらに、記録した画像内の部分領域における要素の並びについて数列確率を
計算することを含む。例えば、特定された所定数の要素が行列である場合、要素の並びは、その行列における縦列の要素または横行の要素であり得る。数列確率は、その並んだ要素に対応する第一組のデコーディング値についての値確率に基づいて計算することができる。値確率は、デコーディング値の複数の許容される組み合わせの各々について計算することができる。各要素について、複数のとり得るデコーディング値の各々が値確率に対応している。一つの組み合わせについての数列確率は、この組み合わせを構成するデコーディング値についての値確率に基づいて決定されてもよい。要素についての値確率が、対応している要素値を有する要素に対応するのと同様に、要素の並びについての数列確率が、対応している組み合わせで構成された数列に対応する。当然ながら、上述した方法以外にも数列確率を計算できる方法はある。
【００１６】
この方法は、第一組のデコーディング値についてとり得るデコーディング値の一つを選択することを含む。この選択は、コーディングパターンにより与えられた条件であって、要素のデコーディング値間の関係についての条件に基づいて、行うことができる。この条件は、好ましくは、記録した画像におけるコーディングパターン内の要素間にどのデコーディング値の組み合わせが存在するかを示すものである。換言すれば、この条件は、使用されるコーディングパターンがどのように構成されたかにより与えられる。既存の組み合わせについての条件は、全体的な（グローバルな）レベルで、つまり画像内の全ての要素を見て与えられる。または、局所的な（ローカルな）レベルで、つまり画像内の要素の集合（すなわち縦列および／または横行）を見て与えられる。この条件に対応して画像内の情報を組み合わせるために確率計算が使用されるため、要素のデコーディング値が、この条件の範囲内で確率計算に基づいて選択されることが可能である。
【００１７】
条件は、上述したデコーディング値の許容される組み合わせを表してもよい。
【００１８】
本発明と共に使用するコーディングパターンは、「二つ以上の方向から」記録することができる。これは、記録した画像内のコーディングパターンが異なる方向に回転され得ることを意味する。データデコーディングの結果は、コーディングパターンの回転によって異なる。この理由のために、本発明による方法は、回転確率に基づいてデコーディングを実行してもよい。回転確率は、記録された画像の回転または方位付け、すなわちコーディングパターンの異なる回転に対応している。画像の異なる回転の各々について、一つの回転確率を算出することが可能である。この回転確率の算出は、特定した要素についてのデコーディング値の値確率または数列確率に基づいて実行できる。データは、最も高い回転確率を示すコーディングパターンの回転に基づいて、デコーディングされてよい。このステップは、位置を求めるときに本発明のデバイスが表面に対して回転されていることによってデータのデコーディングが影響を受けることがないことを意味している。
【００１９】
第二の態様によれば、本発明はデータデコーディングのためのデバイスに関し、該デバイスは、表面上におけるコーディングパターンの部分領域にコーディングされたデータを、記録した部分領域の画像に基づいてデコーディングするための処理手段を備える。コーディングパターンは、複数の要素を含んでおり、複数の要素の各々がとり得るデコーディング値は、少なくとも二つある。このデバイスは、画像内において複数の要素を特定し、特定された要素の各々について、その要素がこのデコーディング値をとる確率を、各々のデコーディングについての値確率として計算し、デコーディング値および対応する値確率に基づいて、データのデコーディングを実行するように構成されている。
【００２０】
画像は、センサによって記録することができる。センサは、データデコーディングのためのデバイスと一体形成する、または、記録した画像をデバイスから受信する別個のユニット内に配置することが可能である。
【００２１】
第三の態様によれば、本発明は、画像に基づいたデータデコーディングのための命令を備えたコンピュータプログラムが記録されているメモリ媒体に関する。
【００２２】
第四の態様によれば、本発明は、コーディングパターンの画像に基づいたデータデコーディングにおける確率計算の使用に関する。
【００２３】
この方法は、デバイスのメモリ内に記録されたコンピュータプログラムとして実現し、プロセッサまたは外部デバイスにおいて実行することができる。
【００２４】
あるいは、この方法は、ＡＳＩＣのような用途指向型回路の形式で、または、ディジタル、アナログ回路、もしくはこれらの適切な組み合わせの形式で、完全にまたは部分的に実現することができる。
【００２５】
上述の方法と共に説明した特徴は、当然ながら本発明によるデバイス、メモリ媒体および使用に応用可能である。
【００２６】
当然ながら、上述の特徴を実施形態と組み合わせることができる。
【００２７】
次に、本発明を、添付の図面を参照しながら、実施形態の方法によってさらに詳細に説明する。
【発明を実施するための最良の形態】
【００２８】
図１は、データデコーディングのためのデバイス１を示している。この例では、デバイス１は位置のデコーディングまたは位置を求めるために使用される。この場合、より詳細には、データは、位置を定義する二つの座標である。デバイスは、ペンとほぼ同形のケーシング２を備えている。ケーシングの短い側部には開口部３が設けられている。この短い側部は、デコーディングするべきデータがコーディングされたコーディングパターン（図示せず）が設けられている表面４と接触するか、または該表面４から短い距離の位置に維持される。デバイス１は、表面４を照射する少なくとも一つの発光ダイオード５と、表面４上のコーディングパターンの部分領域の二次元ディジタル画像を記録するための、例えばＣＣＤまたはＣＭＯＳ画像センサのような感光型エリアセンサ６とを具備している。デバイス１は、レンズシステム７を任意で備えることも可能である。
【００２９】
デバイス１用の電源は、ケーシング２内の別個の区画に取り付けられた電池８より得られる。
【００３０】
デバイス１はさらに、センサ６によって記録された画像に基づいて位置を求めるための画像処理手段９を備えている。この画像処理手段は、より詳細には、センサ６からの画像を記録し、これらの画像に基づいて位置を求める処理を実行するべくプログラムされたプロセッサユニット１０である。
【００３１】
この例では、デバイス１はペン先１１をさらに備えており、このペン先を用いることにより、表面４上に通常の顔料ベースの書き込みを行うことができる。ペン先１１は、引き出し可能および引き込み可能になっているため、ユーザはペン先を使用するかどうかをコントロールすることができる。ある特定の用途では、デバイスにペン先を設ける必要が全くない。
【００３２】
さらにデバイス１はボタン１２を備えることができる。このボタンを用いることによって、デバイスの起動および制御が可能である。また、例えば赤外線または無線波を使用して、デバイスへまたはデバイスからの情報の無線送信を行うための送信機１３と、デコー
ディングしたデータに基づいて情報を表示するためのディスプレイ１４とを設けることができる。
【００３３】
次に、図２のフローチャートを参照して、確率計算の手段によりコーディングパターンをデコーディングする方法の例について説明する。デコーディングするコーディングパターンは、本出願者によるＷＯ０１／２６０３２に記載されているタイプのものである。
【００３４】
図３ａは、光学的に読み出し可能な位置コード１７の形式のコーディングパターンを含んだ表面１６を備える一枚の紙１５を示す。位置コードはマーク１８で構成されているが、図３ａでは明瞭性のために大幅に拡大してある。図３ｂは、図３ａの位置コード１７をさらに拡大した部分１９を示す。デバイスは、位置コードの部分領域の画像を記録し（ステップＡ）、画像中の複数のマーク１８を特定し（ステップＢ）、また、ラスターポイント２２にて交差しているラスターライン２１を備えたラスター形式の基準システムを画像にフィッティングさせる（ステップＣ）ように構成されている。このフィッティングは、各マーク１８をラスターポイント２２と関連付ける方法で行われる。例えば、マーク２３はラスターポイント２４と関連付けられる。その結果、ラスターのフィッティングにより、各マークがどのラスターポイントに属するかの決定が可能となる。この例では、ラスターは四角格子の形態を有するが、これ以外の形態を使用することも可能である。本願明細書中で参照により援用している、本出願人の明細書ＷＯ０１／７５７８３、ＷＯ ０１／２６０３４、ＳＥ ０１０４０８８−０は、画像中におけるラスターのマークへのフィッティングをより詳細に開示している。
【００３５】
「理想的」なコーディングパターンにおいて、各々のラスターポイントと関連付けられるマークは唯一つである。コーディングパターンの画像における変形および不完全性により、コーディングパターンの画像中で、どのマークがコーディングパターンに属するか、並びに、複数のマークのどれが特定のラスターポイントと関連するべきものかを決定することが困難になるかもしれない。そのため、この例では、データのデコーディングにおいて一つの同じラスターポイントに、複数のマークを関連付けすることが可能である。あるラスターポイントに関連付けられた複数のマークは、共にこのラスターポイントに属する要素を形成する。
【００３６】
この例におけるコーディングパターンでは、マーク１８の値が、関連付けされたラスターポイント２２に対するその変位によって定義される。より詳細には、マークの値を定義するのは、ラスターポイントに対するマークのポイントの位置である。一般に、このポイントはマークの主要点である。この例におけるコーディングパターンでは、各マークにつき四つの理想的な位置が存在する。これらの位置は、一つのマークに関連付けられたラスターポイント２２から延びている四本のラスターライン２１の各々の上にある。また、これらの位置は、ラスターポイントから等距離で離れた所に位置している。図４ａ〜図４ｄに、或るマークについての理想的な位置２５が拡大図にて示されている。マークがとる値は、図４ａでは値“０”であり、図４ｂでは値“１”であり、図４ｃでは値“２”であり、図４ｄでは値“３”である。このように、各マークは四つの異なる値“０〜３”を表すことができる。
【００３７】
様々な理由から、記録した画像中で特定されたマークは、理想的な位置を有していないことが多い。そのため、多くの場合、一つのマークについて一つの値を明確に決定することが困難なことがある。このために、デバイスは、特定した各マークについて、そのマークが定義する各値“０〜３”についての値確率を計算するよう構成されている（ステップＤ）。各マークについての値確率は、図５に見られるようにマーク２７からその理想的な位置２５までの距離の減少関数であり、より詳細には、マーク２７の主要点から理想的な位置までの距離２６の減少関数である。通常、複数のマークは理想的な位置の周辺に分布
していると予想できる。これはつまり、値確率Ｐ（ｄｉ）が、
式Ｐ（ｄｉ）＝ｋ ｅｘｐ（−（ｄｉ）２／Ｖ）により計算することができることを意味する。ここで、ｋ＝定数、ｄｉ＝或るマークから理想的な位置までの距離、ｖ＝定数（この例では距離の変数）である。この変数は経験的に計算される。したがって、各マークについて四つの値確率を計算することができる。時には、ラスターポイントの中心にマークが見つかることもある。その場合には、マークから各々の理想的な位置までの距離の大きさが等しいため、一つのマークについての四つの値確率は等しくなる。ラスターポイントに関連付けられるマークが存在しない場合、つまり、その要素がマークを含んでいない場合には、ラスターポイントの中心にマークが存在する、すなわち四つの値確率が等しいものとして扱われる。
【００３８】
一つのラスターポイントに関連付けられるマークが二つ以上、例えば三つある場合、つまり、その要素に三つのマークがある場合には、そのラスターポイントまたは要素について合計で３×４の値確率があることになる。本デバイスは、各ラスターポイントまたは各要素について、各値についての値確率を求めるように構成されている（ステップＥ）。この値確率は、そのラスターポイントに関連付けられた複数のマークによって定められる。ラスターポイントについてのこれらの値確率は、ラスターポイント確率とも呼ばれる。ラスターポイントについて値確率を計算することで、記録した画像内の全てのマークを、位置を求めるときに考慮に入れることができ、また、情報損失のおそれを最小化することができる。上述の内容は、各要素について、その要素が各々の値を定義する値確率が計算されることを意味しているため、これ以降の説明では、値“０”〜“３”を要素値と呼ぶ。
【００３９】
或る要素についての値確率は、要素における複数のマークについての値確率を比較して、最も高い値確率をとり得る要素値の各々について選択することにより、決定することができる。あるいは、要素についての値確率は、その要素におけるマークのとり得る各要素値についての値確率の加重和とすることができる。当然ながら、要素についての値確率は、上述した方法以外の方法によっても決定することができる。
【００４０】
この例における、一つの要素についての値確率の計算を、図６の数字による例で示す。図６ａは、ラスターポイント２２を、二つの関連するマーク２８、２９と共に示す。マーク２８、２９は共に、ラスターポイント２２に属する要素を構成している。図６ｂ中の表３０、３１は、各々のマークのとり得る値についての値確率Ｐ１を含んでいる。図６ｃ中の表３２は、この要素のとり得る要素値について結果として得られた値確率Ｐ２を含んでいる。この例では、要素についての値確率は相対的である。あるいは、代わりに、これらの値確率を適切な方法で正規化することができる。ラスターポイントに関連するマークが一つしかない場合、つまり、関連する要素内にマークが一つしかない場合には、そのマークについての値確率とその要素についての値確率は明らかに同一である。
【００４１】
画像の記録時に、デバイスから表面までの距離は、記録する位置コードの大きさに影響を及ぼし、さらに、これにより、画像にフィッティングさせられるラスターの大きさに影響を及ぼす。画像を位置に変換するためには、所定数の要素、この例では８×８の要素を使用する。８×８よりも多くのラスターポイントが画像にフィッティングさせられた場合には、過剰な要素が特定される。したがって、本デバイスは 全ての特定した要素から、表面上での位置に関する最も多くの情報を提供する一組の要素を選択するようにさらに構成される（ステップＦ）。この一組の要素は連続的なものであるが、必ずしも連続していなくてもよい。この一組の要素に含まれる要素は、この例においては、画像にフィッティングされるラスターポイントを有するラスターポイント行列に対応するが、これは必須条件ではない。換言すれば、目的は、記録した画像の情報分量を最大化するような、各要素についての値確率を有する要素を選択することである。この目的のために、特定した要素の各々についてエントロピーが計算される。その後、エントロピーの和が最小の８×８の
要素が選択される。このエントロピーの和が最少であることは、記録した画像についての情報分量が最大であることに対応している。要素についての値確率が以下の式のように正規化されると、
2004536392.tif 000001
要素のエントロピーＨは、以下の式で計算される。
【００４２】
2004536392.tif 000002
ここで、Ｐ２，ｉは、要素値ｉ（ｉ＝０、１、２、３）についての要素の値確率であり、ｌｏｇ２は、２の対数である。そのため、これらの値確率がいずれも等しい大きさである場合に、この要素についてのエントロピーは最大となり、ある一つの値確率を除くすべての値確率がゼロである場合に、この要素についてのエントロピーは最小となる。エントロピー計算を用いて８×８要素を選択する代わりに、各要素についての最も高い値確率を情報値として使用することもできる。この場合、８×８の要素についての情報値の和からなる情報分量を最大化するような、連続的な８×８の要素が選択される。
【００４３】
この例で用いられるコーディングパターンは、上述のように、表面４上の一つのマークについて二つの座標をコーディングする。これらの座標は個別にデコーディングすることができる。そのため、これらの座標を、二つの次元におけるデータと呼ぶことができる。コーディングパターンにおける各マークは、より詳細には、第一座標のデコーディングに使用される第一ビットと、第二座標のデコーディングに使用される第二ビットをコーディングする。
【００４４】
記録した画像内のコーディングパターンのデコーディングにおいて、一つの要素についてとり得る要素値“０”〜“３”の各々が、第一および第二デコーディング値に変換される。この第一および第二デコーディング値は、この例では二進数である。そのため、本デバイスは、一組の要素内の８×８の要素について、要素値“０”〜“３”を四つの異なるビットの組み合わせ（０、１）、（０、０）、（１、０）、（１、１）に変換するように構成されている。これらのビットの組み合わせは、各要素について、要素値に属する値確率を有する。図７ａ中の表における上記の数字による例を参照されたい。このビットの組み合わせにおいて、第一ビット（つまり第一デコーディング値）が第一の次元に関連し、第二ビット（つまり第二デコーディング値）が第二の次元に関連している。対応する要素値についての値確率Ｐ２が、第一および第二デコーディングに関連付けられている。そのため、この一組の要素を使用して、第一の次元についての関連する値確率を有する第一デコーディング値の組である第一組と、第二の次元についての関連する値確率を有する第二デコーディング値の組である第二組とを作成することができる（ステップＧ）。表３３は、この一組の要素内の一つの要素を示している。表３３’および表３３’’は、関連する値確率を有する第一組内における第一デコーディング値と、関連する値確率を有する第二組内における第二デコーディング値とを含んでいる。第一および第二デコーディング値の各々は、上述の説明から明白であるように、０または１のいずれかである。
【００４５】
本デバイスは、一組の要素内の各要素について、第一組内の異なる複数のとり得る第一デコーディング値の各々を一つの値確率と関連付け、また、第二組内の異なる複数のとり得る第二デコーディング値の各々を一つの値確率と関連付けるように構成されている。こ
の例では、とり得る第一および第二デコーディング値が０および１であるため、上述のような構成とした結果、一組の要素内の各要素につき、第一組および第二組において、デコーディング値０について一つの値確率、また、デコーディング値１について一つの値確率が得られる。これ以降、デコーディング値０についての値確率を０確率、デコーディング値１についての値確率を１確率と呼ぶ。
【００４６】
表３３’を参照すると、この例では、第一デコーディング値が０であるものに対応する第一組内の値確率を比較することにより、一組の要素内の各要素について上述の処理が実行される。そして、最も高い値確率が０確率として選択され、第１行列３４内に保存される。同様にして、第一デコーディング値が１であるものに対応する第一組内の値確率が比較される。そして、最も高い値確率が１確率として選択され、やはり第１行列３４内に保存される。表３３”を参照すると、上述の方法が、その後、第二組内の値確率、第二デコーディング値、第２行列３５についても繰り返される。このようにして、第一組および第二組を使用して、０確率と１確率を含んだ第１および第２行列を作成する（ステップＨ）。その結果を、続く図７ｂ中の数字による例に示す。代替方法として、第一デコーディング値が０であるものに対応する第一組内の値確率が加算され、その和が０確率として保存され、また、第一デコーディング値が１であるものに対応する第一組内の値確率が加算され、その和が１確率として保存されることによって、一組の要素内における８×８要素について、０確率と１確率を有する第１および第２行列が作成されてもよい。この処理は、第二組内の値確率、第二デコーディング値についても繰り返される。
【００４７】
このようにして、一組の要素内における８×８の要素が、各々が８×８の行列要素を有する二つの行列３４、３５に対応する。この行列要素の各々は、一つの０確率と一つの１確率を含んでいる。これらの第１および第２行列を用いることにより、その位置について座標を求めることができる。
【００４８】
記録した画像内の全ての要素について値確率を決定した後に一組の要素を選択する代わりに、特定された全ての要素について、行列３４、３５に対応する行列が決定されるまで待つこともできる。この場合には、各行列内における８×８の行列要素は、対応する０確率と１確率に基づいて選択することができる。これを行うための一つの方法は、０確率および１確率のうち一方が高く、他方が低い８×８の行列要素を選択することである。この場合、二つの座標を求めるために、同一の要素に対応する行列要素を選択する必要はなく、二つの行列について対応する異なる要素の計算が進められる。
【００４９】
この例では、位置コードは、第一の循環主数列に基づいた第一次元におけるものである。これにより、要素の要素値間における関係についての条件が与えられる。第一の循環主数列は、この数列内において、所定の長さの各部分数列についての位置が明確に決定されるという特性を有する。この例では、所定の長さは６である。そのため、第一の循環主数列内の任意の位置において六個の連続した数字を取った場合、これら六個の数字は、この第一の循環主数列において一度だけ現れる。この特性は、第一の主数列の最後が第一の主数列の最初と連結している場合にも適応される。したがって、第一の主数列は循環と呼ばれる。この例では、二進数の主数列が用いられる。六個の数字を有する部分数列についての位置を明確に決定する場合には、第一の主数列は最大で２６＝６４の長さを有することができ、長さ６の部分数列は、第一の循環主数列内の０〜６３の位置を有することができる。しかし、長さ６３の第一の主数列を選択した場合には、以降の説明から明白になるように、改善されたエラー修正特性を設けることが可能である。したがって、以降の説明では、第一の主数列の長さは６３であり、そのため０〜６２の範囲内において固有の位置が定義される。
【００５０】
図８は、位置コーディングに関連して使用できる第一の循環主数列の例を示す。部分数
列０、０、０、０、０、０は、第一の主数列内に、例えば、明確な位置０を有し、部分数列１、１、１、１、１、０は、明確な位置９を有し、部分数列１、１、１、０、１、０は、明確な位置１１を有する。表面上の位置を求めるために、記録した画像内で６×６要素を特定する必要がある。しかし、上述のように、位置を求めるには８×８の要素を使用する。その理由は以降の説明より明らかになる。また、上述したように、第一次元において位置コードが基づく第一の循環主数列は、長さ６の相互的に固有な部分数列のみを含むという特性を有する。その結果、さらに、長さ８の各部分数列についての、第一の循環主数列内における位置が明確に求められる。この事実は、表面上の位置についての座標を求めるときにも用いられる。
【００５１】
本デバイスは、第一の循環主数列内における長さ８の固有の部分的数列の各々に、第１行列３４内における縦列の各々をマッチングさせるように構成されている（ステップＩ）。この方法を図９に示す。この図は、長さ８の二進数の部分数列３６と、第１行列３４内における縦列３７（図７ｂ）の一例を示している。この縦列は、複数の行列要素を備えており、この複数の行列要素の各々は、それぞれ０および１である第一デコーディング値に対応する０確率と１確率を含んでいる。各行列要素について、部分数列３６内の対応する数に基づき、０確率と１確率のうち一つが選択される。部分数列３６内の１番目の数は例えば０であり、これはつまり、縦列３７内の１番目の行列要素について０確率が選択されることを意味する。部分数列内の２番目の数は１であり、これはつまり、縦列３７内の２番目の行列要素について１確率が選択されることを意味する。第一の主数列における各部分数列につき、第１行列３４内の各縦列について、本デバイスはさらに、行列要素について対応するように選択された０確率と１確率を乗算することによって、第一数列確率を計算するように構成されている（ステップＪ）。図９では、部分数列３６および縦列３７に対応する第一数列確率３８が算出されている。この動作後には、第１行列３４内の各縦列について、それぞれ関連する固有の数列値を有する６３個の第一数列確率が存在することになる。これらの数列値は、第一の循環主数列内における対応する部分数列の位置によって定義される。デバイスは、各縦列について、最も高い第一数列確率とそれに対応する数列値を選択し、これらを保存するように構成されている。
【００５２】
ここでは、第二の次元における位置コードは、第二の循環主数列に基づいており、この第二の循環主数列は、この例では第一の循環主数列と同一の特性を有している。
【００５３】
これに対応するように、デバイスはさらに、第二の循環主数列内における長さ８の固有の部分数列の各々を、第２行列３５内の横行とマッチングさせるように構成されている。行列３５内の横行は、行列３４内の縦列と全く同様に、それぞれ０である第二デコーディング値と１である第二デコーディング値に対応する０確率と１確率を含んでいる。各行列要素について、第二の循環主数列における部分数列内の対応する数に基づき、０確率および１確率のうちの一つが選択される。第二の主数列における各部分数列につき、第２行列３５内の各横行について、デバイスはさらに、行列要素について対応するように選択された０確率および１確率を乗算することによって、第二数列確率を計算するように構成されている（ステップＪ）。この動作後には、第２行列３５内の各縦列につき、それぞれ関連する固有の数列値を有する６３個の第二数列確率が存在することになる。これらの数列値は、第二の循環主数列内における対応する部分数列の位置によって定義される。デバイスはさらに、各横行について、最も高い第二数列確率とそれに対応する数列値とを選択し、これらを保存するように構成されている。
【００５４】
この例で使用している位置コードは、循環主数列の異なる循環ないし循環的シフトの使用に基づいている。例えば、ｘ方向において位置をコーディングするためには、第一の主数列を、表面上の複数の縦列に、すなわち、位置がコーディングされる方向に対して直行するｙ方向において、上から下に向かって種々の方法で循環ないし循環的シフトさせて、
印刷または他の方法によって配置する。主数列は同一の縦列内で繰り返し印刷されてもよい。これは、主数列の長さに対応する位置よりも多くの位置をｙ方向にコーディングする場合に必要である。主数列の同一の循環が全ての繰り返しに使用される。これはつまり、異なる循環が異なる縦列に使用できることを意味する。
【００５５】
隣接した縦列の各対が差分数Ｄを定義する。差分数Ｄは、各縦列内における第一部分数列についての主数列内における位置間の差によって得られる。部分数列についての位置間の差を縦列内で一段階下げて取った場合にも、これらの位置が同じ様にオフセットされるため、同一の結果が得られる。したがって、差分数Ｄは、縦列内のどの「高さ」で主数列内の部分数列の位置と比較されるかに関係なく、常に同じである。そのため、各対の縦列について、差分数Ｄはｙ方向において一定である。隣接した縦列間の差分数は、第一の次元において表面上の位置の座標を得るために使用できる一組の差分数を形成する。
【００５６】
第二の次元（この場合は例えばｙ方向）における位置コードは、第一の次元における位置コードと同じ原理に基づくことができる。したがって、第二の主数列は、表面上の複数の横行において、つまりｘ方向において、左から右に向かって、異なる循環的シフトで配置される。隣接した横行間で差分数が定義され、これらの差分数が、第二の次元における表面上の位置の座標を得るために使用できる一組の差分数を形成する。
【００５７】
このようにして、位置コードは、第一方向についての一つの部分位置コードと、第二方向についての一つの部分位置コードとで構成されている。
【００５８】
上述から明白であるように、部分数列は、明示的な値で書かれたものではなく、図形コーディングで書かれたものである。図形コーディングでは、マークが、部分位置コードの重ね合わせを定義する。
【００５９】
位置コードは、表面上の所定の方向に配置された主数列に基づいているため、位置決定を修正するためには、これらの方向にマークをデコーディングしなくてはならない。適正なデコーディング方向は、上述したように、上から下、および左から右へ向かう。
【００６０】
デバイス１は、画像の記録時に、異なる位置で、表面および位置コードに対して回転した状態に維持することができる。図１０中で矢印４０として示すように、四つの記録時の回転があり得る。位置コードは、０度、９０度、１８０度または２７０度の角度で回転した場合、その外観が本質的に同一となるため、記録した位置コードの画像自体が位置コードとデバイス間の相対回転を示すことはない。しかし、位置コードを回転すると、関連付けられるラスターポイントに対する各マークの変位の方向が変更される。その結果、マークの変位をコーディングするビットの組み合わせ（第一デコーディング値、第二デコーディング値）が変更されることとなる。位置コードの「適正な」回転の状態では、マークは、縦列内で上から下、また横行内で左から右に向かう適正なデコーディング方向に配置される。位置の適正な回転が０度である場合、不適正な回転に以下が適用される：
● 右回りに９０度： 上から下へ向かって配置された「適正な」回転のマークを有する縦列が、右から左へ向かって、つまり不適正なデコーディング方向に配置されたマークを有する横行となり、また、左から右へ向かって配置された「適正な」回転のマーク有する横行が、上から下へ向かって、つまり適正なデコーディング方向において配置されたマークを有する縦列となる。
【００６１】
● １８０度： 「適正な」回転のマークを有する縦列が、下から上へむかって、つまり不適正なデコーディング方向に配置されたマークを有する縦列となり、また、「適正な」回転のマークを有する横行が、右から左へ向かって配置された、つまり不適正なデコーディング方向において配置されたマークを有する横行となる。
【００６２】
● 右回りに２７０度： 「適正な」回転のマークを有する縦列が、左から右方向へ向かう、つまり適正なデコーディング方向において配置されたマークを有する横行となり、また、「適正な」回転されているマークを有する横行が、下から上へ向かって、つまり不適正な方向において配置されたマークを有する縦列となる。
【００６３】
縦列および横行内のマークが不適正なデコーディング方向において配置されている場合には、デコーディング時に、各要素について０確率および１確率が逆転される。
【００６４】
したがって、デバイスは、以下に説明するように、記録した画像内における位置コードの部分領域の異なる回転をテストするように構成されている。第１行列３４および第２行列３５において実行された各々の動作（つまり、循環主数列内の部分数列の行列内における縦列および横行の各々へのマッチング（ステップＩ）、数列確率の計算（ステップＪ）、縦列および横行の各々について、対応する数列値を有する最も高い数列確率の選択）が、１８０度回転されて「逆転」された第１行列３４、第２行列３５上でも実行される（図７ｃでは、これらの行列にそれぞれ参照符号３４’、３５’を付している）。回転されて逆転されたこれらの行列３４’、３５’は、記録した画像における位置コードの部分領域の逆転バージョンに対応している。この理由が、記録した画像における位置コードの部分領域の一例を示す図１１にて説明されている。この図では、明瞭性のために九個のマークのみが使用されており、説明のために、これらのマークはそれぞれ一つのラスターポイントに関連付けられている。位置コード４５は、画像において記録されたものである。位置コード４５’は、同じ位置コードを逆転したものである。行列４６、４７は、正しい方向に回転した位置コード４５についての行列３４、３５にそれぞれ対応しており、また、行列４８、４９は、逆転した位置コード４５’についての行列３４’、３５’にそれぞれ対応している。逆転した位置コードについての行列４８、４９を１８０度回転させて反転させた場合、正しい方向に回転した位置コードについての行列４６、４７が得られる。この例において、反転とは、各行列要素内の０確率および１確率が位置を変更することを意味する。
【００６５】
上述の手順の実行後には、行列３４、３４’内の各縦列について、また、行列３５、３５’内の各横行について、対応する数列値を有する最も高い数列確率が存在することになる。そこで、本デバイスは、行列３４、３４’および３５、３５’の各々について、対応する最も高い数列確率を乗算することより、回転確率を計算する（ステップＫ）ように構成されている。最も高い回転確率に対応する行列３４、３４’の数列値についての最も高い数列確率に対応する数列値、および、最も高い回転確率に対応する行列３５、３５’の数列値についての最も高い数列確率に対応する数列値に基づいて、位置についての座標を計算することができる。
【００６６】
上述したように、四つの回転全てを調べる必要はない。これは、一つの例を用いて単純に説明される。図１１に示すように、記録した画像における位置コードの部分領域が１つ（４５）であると仮定する。さらに、位置コードの「適正な」回転が、記録されたものに対して、右方向に９０度回転していると仮定する。上述の説明によれば、適正な回転は０度の回転に対応すると仮定される。これはつまり、記録した画像内の位置コード４５が、「適正な」回転に対して右方向に２７０度回転していることを意味する。その結果、位置コード４５’が、「適正な」回転に対して右方向に９０度回転している。上述した方法で、図１１に示すように位置コード４５、４５’がデコーディングされる。０度の「適正な」回転におけるマークを有する縦列が、上述したように、位置コード４５内において、適正なデコーディング方向において配置される。適正な方向によって、これらの横行に対応する数列確率と、如いては回転確率とが上昇する。適正な回転におけるマークを有する横行は、上述のように、位置コード４５内に不適正なデコーディング方向において配置され
た縦列である。不適正な方向と反転を組み合わせると、これらの縦列に対応する値確率と、如いては回転確率とが低下する。この関係は、位置コード４５’についての関係とは逆のものである。０度の適正な回転におけるマークを有する縦列は、上述したように、位置コード４５’内に不適正なデコーディング方向において配置された横行である。不適正な方向により、これらの横行に対応する数列確率と、如いては回転確率とが低下する。適正な回転におけるマークを有する横行は、上述したように、位置コード４５’内に適正なデコーディング方向において配置された縦列である。この適正な方向により、これらの縦列に対応する数列確率と、如いては回転確率とが上昇する。
【００６７】
位置コードの「適正な」回転を記録するときには、縦列および横行が、上述したように画像内の「適正な」方向へと延びている。これはつまり、図７における例について、行列３４、３５の両方についての回転確率が、行列３４’、３５’についての回転確率よりも高くなることを意味する。これは、位置コードの「適正な」回転が記録されたことを表す。これにより、行列３４についての最も高い数列確率に対応する数列値に基づいて、第一座標を計算することができ、また、行列３５についての最も高い数列確率に対応する数列値に基づいて、第二座標を計算することができる。
【００６８】
「適正な」回転に対して１８０度回転した位置コードを記録するときには、縦列および横行が、画像内で「不適正な」方向に延びている。これはつまり、例えば図７では、行列３４’、３５’の両方についての回転確率が、行列３４、３５についての回転確率よりも高くなることを意味する。これは、位置コードが、「適正な」回転に対して１８０度の回転において記録されたことを表す。これにより、行列３４’についての最も高い数列確率に対応する数列値に基づいて、第一座標を計算することができ、また、行列３５’最も高い数列確率に対応する数列値に基づいて、第二座標を計算することができる。
【００６９】
「適正な」回転に対して右方向に９０度または２７０度回転した位置コードの記録は、同一の回転に属していない最も高い回転確率によって表される。図７における行列３４、３５が、適正な方向に対して右方向に９０度される位置コードより生じていると仮定した場合、行列３４についての回転確率が、行列３４’についての回転確率よりも高くなり、行列３５についての回転確率が、行列３５’についての回転確率よりも低くなる。この場合、行列３４についての最も高い数列確率に対応する数列値に基づいて第二座標が計算され、また、行列３５’についての最も高い数列確率に対応する数列値に基づいて第一座標が計算される。図６における行列３４、３５が、適正な方向に対して右方向に２７０度回転する位置コードから生じていると仮定すると、第二座標は、行列３４’についての最も高い数列確率に対応する数列値に基づいて計算され、第一座標が、行列３５についての最も高い数列確率に対応する数列値に基づいて計算される。
【００７０】
記録した画像内における位置コーディングの回転方向が検出できるのは、或る行列についての回転確率が、その行列が９０度、１８０度、または２７０度の角度で回転した際に変更されるという事実があるからである。位置コードの回転が０度ではない場合、つまり、記録した画像内における位置コードの回転が不適正である場合には、上述したように回転確率が低下する。これは、循環主数列内における長さ８の固有の部分数列が、主数列内では反転または逆転しないという事実に依存する。このような条件が、長さ６の部分数列の主数列について満たされなければならないとすると、これはつまり、主数列が大幅に小さくなることを意味し、如いては、コーディングできる位置がより少なくなることを意味する。したがって、これが、理論的に必要なのは６×６の要素だけであるが、位置を求めるために８×８の要素を使用する一つの理由である。
【００７１】
回転検出に使用されるものと同一の基本原理を、エラー修正に用いることができる。例えば、位置を求めるのに必要なものよりも長い所定の長さの部分数列が、主数列内で一つ
のビットが反転した状態で生じないように、主数列を選択することが可能である。そして、このようなより長い部分数列内において、一つを除く全てのビットを適正に検出できる場合には、不適正なビットを修正することが可能である。これは、理論的には６×６の要素しか必要でないのに、位置を求めるために８×８の要素が使用される別の理由である。
【００７２】
そのため、主数列を賢く選択することで、コーディングパターンのエラー検出特性およびエラー修正特性を相当に向上させることが可能である。
【００７３】
しかし、長さ８の部分数列が反転または逆転しない循環主数列の特性は、６４ビット長の主数列には与えられない。これが、主数列の長さが６３に選択されている理由である。
【００７４】
デコーディングでは、エラー修正特性を得るべく冗長情報が使用される。上述した例では、６×６のラスターポイントに基づいて位置情報を抽出することができるにも関わらず、デコーディングに８×８の要素を使用している。これはつまり、位置を求めるために５６ビットの冗長情報［（８２−６２）×２］があることを意味する。デコーディングでは、現在の画像に属する値確率を使用しながら、縦列および横行ごとに、現在の画像内の情報が、位置コード内で生じ得る異なる部分数列とマッチングされる。要素の値間の関係についての既知の条件と確率と冗長情報とを組み合わせることで、現在の画像における干渉に対する優れた無感応性が得られる。個々のマークの各々の値は最も高い数列確率を与える部分数列における他の値に対応すべきであるので、個々のマークの各々の値の重要性は減少する。
【００７５】
エラー修正の必要性がさらに制限されると、デバイスは、第一行列内の各縦列について、また、第二行列内の各横行について、各要素ついての０確率および１確率のうち最も高い確率に対応して、数列、如いては数列値を直接選択するように構成することができる。
【００７６】
記録した位置コードの、「適正な」回転に関連した回転４０’が確立されている場合には、位置の第一座標と第二座標を求めることができる（ステップＬ）。これは、上述したように、図１０において、第一座標についてＳｘ１〜Ｓｘ８（４１）、第二座標についてＳｙ１〜Ｓｙ８（４２）と示される数列値に基づいて実行される。
【００７７】
デバイスは、数列値Ｓｘ１〜Ｓｘ８およびＳｙ１〜Ｓｙ８について、隣接した数列値間の差分を計算するように構成されており、その結果、符号４３、４４で示す二組の七個の差分数Ｄｘ１〜Ｄｘ７、Ｄｙ１〜Ｄｙ７がそれぞれ得られる。そして、これらの差分数を用いて、第一座標と第二座標を生成する。
【００７８】
しかし、第一座標を計算するためには、上述のように、数列値Ｓｘ１〜Ｓｘ８のうち六個のみ、すなわち差分数Ｄｘ１〜Ｄｘ７のうち五個のみが必要である。この例によれば、数列値Ｓｘ２〜Ｓｘ７と、如いては差分数Ｄｘ２〜Ｄｘ６が使用される。これは、数列値Ｓｙ２〜Ｓｙ７、如いては差分数Ｄｙ２〜Ｄｙ６から算出される第二座標についても同様である。代わりに、各方向について、六個の数列値Ｓｘ２〜Ｓｘ７、Ｓｙ２〜Ｓｙ７のみを求めてもよい。
【００７９】
差分数から座標への変換は多くの方法で実行することができるが、これには例えば、本願明細書中で援用により参照している本出願人による明細書ＷＯ０１／２６０３３、ＳＥ
０１０３５８９−８に記述されている方法が含まれる。
【００８０】
上述した例では、記録した画像内において、データデコーディングのために８×８の要素が特定されている。しかし、時には、これほど多くの要素を特定できない場合が生じる可能性もある。そこで、８×８要素を得るために画像内で特定できる要素に「空白」の追
加的要素が加えられる。先に述べたように、「空白」要素についての値確率は全て等しい。
【００８１】
図１２は、表面５０を備えた一枚の紙を示している。この表面にはマーク５２で構成された別の位置コード５１が設けられており、このマークは明瞭性の目的で大幅に拡大されている。この場合、マーク５２の値はそのサイズによって定義される。このタイプの位置コードは、本願明細書中で援用により参照している特許公報ＷＯ００／７９３８３に記載されている。
【００８２】
この場合、デバイスは、上述したように、位置コードの部分領域の画像を記録し、画像中の複数のマークを特定し、ラスターを画像にフィッティングさせて、各マークが一つのラスターポイントと関連付けられるように構成されている。上述の位置コードを用いた場合と同様に、ラスターポイントに関連したマークは、このラスターポイントに属する要素を構成する。ここでは、各マークについてのとり得る二つの値が示される。小さいマーク５３は値０に対応し、大きいマーク５４は値１に対応する。そして、小さいマークと大きいマークにとっての理想的なサイズが存在する。
【００８３】
通常、特定されたマークは理想的なサイズのものではない。そのため、多くの場合、各マーク５２について明確に値を決定することが困難である。そこで本デバイスは、上述したように、マークが定義する各値“０”および“１”について関連する値確率を、特定された各々のマークについて計算するように構成されている。
【００８４】
マーク５２のサイズは、通常、理想的なサイズの近くに分布していると仮定できる。これはつまり、公式Ｐ（ｒ）＝ｋｅｘｐ（−（Ｒｉ−ｒ）２／ｖ）を用いて、値確率Ｐ（ｒ）を計算できることを意味する。ここで、ｋ＝定数、Ｒｉ＝理想サイズ、ｒ＝マークのサイズ、ｖ＝定数、この例ではサイズの変数である。Ｒｉとｒは、例えば、範囲または半径であり得る。この変数は、経験的に決定することができる。
【００８５】
このように、各マークについて、二つの値確率を計算できる。ラスターポイントに関連付けられるマークが存在しない場合、つまり、関連する要素が０マークを含んでいる場合には、このラスターポイントに関連して、理想サイズの二つのマーク（すなわち、値“０”を有するマークと値“１”を有するマーク）が存在するかのように扱われる。
【００８６】
一つのラスターポイントに関連付けられるマークが二つ以上、例えば三つ存在する場合、つまり、その要素に三つのマークがある場合には、そのラスターポイントまたは要素について合計で３×２の値確率が存在する。したがって、本デバイスは、上述のとおり、各ラスターポイントまたは各要素について、各値についての値確率を決定するように構成されている。この値確率は、そのラスターポイントに関連付けられた複数のマークによって定められる。このようにして、各要素について値確率が計算され、要素が各々の値を定義する。したがって、この場合には、値“０”および値“１”を要素値と呼ぶこともできる。
【００８７】
一つの要素についての値確率は、上述したように、比較している要素内のマークについての値確率によって決定することができ、最も高い値確率が各要素値について選択される。その代わりに、要素についての値確率は、要素内のマークの要素値についての値確率の加重和であってよい。この位置コードの場合、当然ながら、要素についての値確率も、上述した以外の方法で決定することが可能である。
【００８８】
さらにこの場合、マークについての値確率と要素についての値確率は、その要素がそのマークのみを含んでいれば、同一である。
【００８９】
そして、導入部分の形で説明した位置コードと同様に、要素についての値確率を用いて、上記の詳細に記述した対応する方法で、表面上の位置が求められる。
【００９０】
後者の位置コードの代替例は、値確率を、ラスターポイントに対応する暗い範囲の合計の関数とするものである。この代替例は、各ラスターポイントに関連付けられたマークが一つしか存在しない場合に有用である。時には、何らかの理由から、位置コードの記録した画像内にある一つのマークが、完全に連続した範囲でない場合が実際に起こり得る。その場合、このマークが分裂したものとして現れるため、デバイスが数個のマークと認識してしまうおそれがある。
【００９１】
上述した例では、確率がいくつかの異なる場合において乗算され、様々な結果が得られている。乗算すべき確率が指数関数によって記述される場合には対数を使用することができ、これにより、以下に示す公式に従って指数を加算することで結果を得ることができる。
ｌｎ（ｅｘｐ（ａ）・ｅｘｐ（ｂ））
＝ｌｎ（ｅｘｐ（ａ））＋ｌｎ（ｅｘｐ（ｂ））＝ａ＋ｂ
【００９２】
図１３ａ、図１３ｂは、本発明と共に使用できる追加タイプの二つのコードを示す。図１３ａ中のコード５５は、短い線の形態のマーク５６で構成される。マーク５６の値は、線の傾斜によって異なる。マーク５７は値０に対応し、マーク５８は値１に対応している。このタイプのコードは、本願明細書中で援用により参照している特許明細書ＵＳ−Ａ−５，２４５，１６５に記載されている。図１３ｂ中のコード５９は、四角格子６０で構成され、この四角格子の中に三角６１が配置されている。四角６２は値０であり、四角６３は値１である。
【００９３】
本発明と共に使用できる別のコードは、第一および第二の理想形状である二つの異なる理想形状を有するマークで構成されており、表面上におけるマークの密度によって位置に関する情報が提供される。この場合、密度は二つの次元において変化し、第一理想形状のマークの密度は第一次元において変化し、第二理想形状のマークの密度は第二次元において変化する。
【００９４】
本発明と共に使用できるコードはこれ以外にも複数あり、上述した応用形は例証のみとして考慮される。
【００９５】
位置コードの部分領域の画像を記録すると、探索中の画像内における連続した暗い範囲によってマークが特定される。しかし、画像中の連続した暗い範囲は、位置コード内のマークであるとは限らない。時として、例えば埃のような形態の不純物が、位置コードを印刷した表面上に存在することがある。これらの不純物は、記録した画像内にノイズマークを引き起こし、このノイズマークが位置コード内で間違ってマークとして識別されてしまうことがある。さらに、センサノイズが、記録した画像内にノイズマークを生じさせることがある。記録した画像内のノイズマークは、デバイス内の構成要素の一つに発生した欠陥、例えばセンサ内の損傷した画素から生じる可能性もある。
【００９６】
しかし、理想の位置からの距離に基づいてマークの値が決定される第一の場合には、任意のノイズマークが位置決定の結果に影響を与えることを阻止する要因がある。記録した画像についてラスターのフィッティングが良好であると、ノイズマークが、位置コードのマークよりも、理想の位置からより長い距離にて配置される。第二の場合には、ノイズマーク結果に影響を及ぼすことを阻止する別の要因が存在する。通常、ノイズマークは、位置コードのマークよりも遥かに小型である。一つの要素について値確率を決定する場合に
は、ノイズマークについての値確率が位置コードのマークについての値確率よりも遥かに低いため、ノイズマークについての値確率の重要性は減少する。
【００９７】
当業者は、本発明の概念から逸脱しない限り、上述の例を多数の方法で変更できることを理解するであろう。
【００９８】
本願明細書中で説明した位置コード内のマークについて二つの異なるパラメータ（すなわちマークの位置、および、その形状／サイズ）がある。どの位置コードを使用するかにによって、パラメータの一つがマークの値を表すことになる。そして、別のパラメータを適切に使用して、位置コード内の特定されたマークの確率を計算ことができる。
【００９９】
例えば、マークの値がそのラスターに対する位置によって定義されている位置コードの場合には、これらのマークの範囲が、現在のマークが実際に位置コード内のマークである確率を示すマーク確率に対応することができる。ラスターポイント確率を計算する以前に、各マークについての値確率に、そのマーク確率を乗算することが可能である。この方法の代替例は、ノイズマークを早い段階において完全に除去するために、デバイスにエリアフィルタを使用する形態である。このフィルタは、位置コード内の二つの境界値の間に位置するエリアを有する全てのマークが位置コード内のマークとして特定される一方で、境界値の外にある全てのマークが拒否される方法で機能する。
【０１００】
例えば、マークの値がその形状／サイズによって定義される位置コードの場合には、ラスターに関連するマークの位置は、マークが位置コード内のマークである確率を表すことができる。
【０１０１】
当然ながら、本発明を、単一の次元における位置決定と共に使用することができる。導入部分の形により説明した位置コードの場合には、これは、上述した方法で第一座標または第二座標を求めるために、第一組と第二組のうち一つを使用することを意味する。
【０１０２】
本発明は、二進数の基数に基づいた位置コードに関連した使用に限定されるものではない。当然ながら、さらに、これ以外の基数を使用して、第一および第二デコーディング値における要素値と同様に、循環主数例を表すことも可能である。
【０１０３】
さらに、本発明は、要素が二個または四個の要素値を仮定する位置コードの使用に限定されるものではない。或る代替例では、要素は八個の要素値を仮定することができる。そして、三つの次元の各々について、各要素値を第一、第二、第三デコーディング値に変換することができる。その結果、さらに、第３組と第３行列を第三の次元について作成できるようになる。これは、例えば、三つの次元での位置を求めるために使用することが可能である。
【０１０４】
本発明によるデバイスおよび方法は、位置のコーディングに関する使用に限定されるものではなく、別の状況、例えば、本願明細書中で援用により採用している、本出願者に譲渡された特許明細書ＷＯ０１／７１６５３に記載されている、ベース上にコード形式で記録されたデータをデコーディングする場合にも使用できる。
【図面の簡単な説明】
【０１０５】
【図１】データデコーディングのためのデバイスを示す。
【図２】デコーディングの一例を説明したフローチャートを示す。
【図３ａ】第一タイプのコーディングパターンを備えた一枚の紙を示す。
【図３ｂ】図３ａ中のコーディングパターンの部分を拡大した拡大図を示す。
【図４】コーディングパターン内におけるマークの四つ理想的な位置を示す。
【図５】一つのマークについての値確率を計算する様を示す。
【図６】要素のための値確率を計算する様を示す。
【図７】第一、第二行列の作成を示す。
【図８】循環主数列を示す。
【図９】数列確率の計算を示す。
【図１０】データデコーディングのステップを示す。
【図１１】コーディングパターンの回転を示す。
【図１２】第二タイプのコーディングパターンを示す。
【図１３】コーディングパターンの更なる二つの例を示す。
【誤訳訂正３】
【訂正対象書類名】図面
【訂正対象項目名】図２
【訂正方法】変更
【訂正の内容】
【図２】
2004536392.tif 000003