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