向きを示す巡回位置符号
あるレイアウトに従って基板上または基板内に配設された機械可読の符号化データ。このレイアウトは、少なくともn次の回転対称性を有する。ただし、nは少なくとも2である。このレイアウトにより、n個のシンボルが整数m回繰り返されるシーケンスを含む向きの符号語が符号化される。ただし、mは、1またはそれ以上である。符号化されたシンボルはそれぞれ、このレイアウトの回転対称中心の周りでn個の位置に分配されて、このレイアウトのn個の向きのそれぞれにおいてこれらのシンボルを復号することにより、向きの符号語のn個の表現が生成される。各表現は、向きの符号語の異なる巡回シフトを含み、このレイアウトの回転の程度を示す。この向きの符号語は、誤り許容型である。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、向きを示す巡回位置符号、および表面の位置符号化における当該巡回位置符号の使用法に関する。
【背景技術】
【0002】
本発明に関係する様々な方法、システム、および装置が、本発明の出願人または譲受人によって出願された以下の米国出願に開示されている。
「Symmetric Tags」という名称の米国特許出願第10/410484号
「Methods and Systems for Object Identification and Interaction」という名称の米国特許出願第10/409876号
「Methods and Systems for Object Identification and Interaction」という名称の米国特許出願第10/409848号
「Methods and Systems for Object Identification and Interaction」という名称の米国特許出願第10/409845号
これらの出願された出願の開示を相互参照により本明細書に組み込む。
【0003】
本発明に関係する様々な方法、システム、および装置が、本発明の出願人または譲受人によって2003年4月7日に出願された「Methods and Systems for Object Identification and Interaction」という名称のオーストラリア国仮出願第2003901617号の出願に開示されている。この同時係属出願の開示を相互参照により本明細書に組み込む。
【0004】
本発明に関係する様々な方法、システム、および装置が、本発明の出願人または譲受人によって2002年12月4日に出願された「Rotationally Symmetric Tags」という名称の同時係属PCT出願である米国特許出願第10/309358号に開示されている。この同時係属出願の開示を相互参照により本明細書に組み込む。
【0005】
本発明に関係する様々な方法、システム、および装置が、本発明の出願人または譲受人によって2002年11月22日に出願された同時係属PCT出願PCT/AU02/01572号およびPCT/AU/02/01573号に開示されている。これらの同時係属出願の開示を相互参照により本明細書に組み込む。
【0006】
本発明に関係する様々な方法、システム、および装置が、本発明の出願人または譲受人によって2002年10月15日に出願された同時係属PCT出願PCT/AU02/01391号、PCT/AU02/01392号、PCT/AU02/01393号、PCT/AU02/01394号、およびPCT/AU02/01395号に開示されている。これらの同時係属出願の開示を相互参照により本明細書に組み込む。
【0007】
本発明に関係する様々な方法、システム、および装置が、本発明の出願人または譲受人によって2001年11月26日に出願された同時係属PCT出願PCT/AU01/01527号、PCT/AU01/01528号、PCT/AU01/01529号、PCT/AU01/01530号、およびPCT/AU01/01531号に開示されている。これらの同時係属出願の開示を相互参照により本明細書に組み込む。
【0008】
本発明に関係する様々な方法、システム、および装置が、本発明の出願人または譲受人によって2001年10月11日に出願された同時係属PCT出願PCT/AU01/01274号に開示されている。この同時係属出願の開示を相互参照により本明細書に組み込む。
【0009】
本発明に関係する様々な方法、システム、および装置が、本発明の出願人または譲受人によって2001年8月14日に出願された同時係属PCT出願PCT/AU01/00996号に開示されている。この同時係属出願の開示を相互参照により本明細書に組み込む。
【0010】
本発明に関係する様々な方法、システム、および装置が、本発明の出願人または譲受人によって2000年11月27日に出願された同時係属米国出願第09/721895号、第09/721894号、第09/722174号、第09/721896号、第09/722148号、第09/722146号、第09/721861号、第09/721892号、第09/722171号、第09/721858号、第09/722142号、第09/722087号、第09/722141号、第09/722175号、第09/722147号、第09/722172号、第09/721893号、第09/722088号、第09/721862号、第09/721856号、第09/721857号、第09/721859号、第09/721860号に開示されている。これらの同時係属出願の開示を相互参照により本明細書に組み込む。
【0011】
本発明に関係する様々な方法、システム、および装置が、本発明の出願人または譲受人によって2000年10月20日に出願された同時係属米国出願第09/693415号、第09/693219号、第09/693280号、第09/693515号、第09/693705号、第09/693647号、第09/693690号、第09/693593号、第09/693216号、第09/693341号、第09/696473号、第09/696514号、第09/693301号、第09/693388号、第09/693704号、第09/693510号、第09/693336号、第09/693335号に開示されている。これらの同時係属米国出願の開示を相互参照により本明細書に組み込む。
【0012】
本発明に関係する様々な方法、システム、および装置が、本発明の出願人または譲受人によって2000年9月15日に出願された同時係属米国出願第09/663579号、第09/669599号、第09/663701号、第09/663640号に開示されている。これらの同時係属出願の開示を相互参照により本明細書に組み込む。
【0013】
本発明に関係する様々な方法、システム、および装置が、本発明の出願人または譲受人によって2000年6月30日に出願された同時係属米国出願第09/609139号、第09/608970号、第09/609039号、第09/607852号、第09/607656号、第09/609132号、第09/609303号、第09/610095号、第09/609596号、第09/607843号、第09/607605号、第09/608178号、第09/609553号、第09/609233号、第09/609149号、第09/608022号、第09/609232号、第09/607844号、第09/607657号、第09/608920号、第09/607985号、第09/607990号、第09/607196号、第09/606999号に開示されている。これらの同時係属出願の開示を相互参照により本明細書に組み込む。
【0014】
本発明に関係する様々な方法、システム、および装置が、本発明の出願人または譲受人によって2000年5月23日に出願された同時係属米国出願第09/575197号、第09/575195号、第09/575159号、第09/575132号、第09/575123号、第09/575148号、第09/575130号、第09/575165号、第09/575153号、第09/575118号、第09/575131号、第09/575116号、第09/575144号、第09/575139号、第09/575186号、第09/575185号、第09/575191号、第09/575145号、第09/575192号、第09/575181号、第09/575193号、第09/575156号、第09/575183号、第09/575160号、第09/575150号、第09/575169号、第09/575184号、第09/575128号、第09/575180号、第09/575149号、第09/575179号、第09/575187号、第09/575155号、第09/575133号、第09/575143号、第09/575196号、第09/575198号、第09/57578号、第09/575164号、第09/575146号、第09/575174号、第09/575163号、第09/575168号、第09/575154号、第09/575129号、第09/575124号、第09/575188号、第09/575189号、第09/575162号、第09/575172号、第09/575170号、第09/575171号、第09/575161号、第09/575141号、第09/575125号、第09/575142号、第09/575140号、第09/575190号、第09/575138号、第09/575126号、第09/575127号、第09/575158号、第09/575117号、第09/575147号、第09/575152号、第09/575176号、第09/575115号、第09/575114号、第09/575113号、第09/575112号、第09/575111号、第09/575108号、第09/575109号、第09/575110号に開示されている。これらの同時係属出願の開示を相互参照により本明細書に組み込む。
【0015】
表面上に1つまたは複数の符号化データ構造を設けて、この符号化データ構造を適切な感知装置によって読み取り、復号し得ることが知られている。光学センサを組み込んだこのような装置の様々な実施形態が、相互参照により本出願に組み込む文献の多くに記載されている。
【0016】
これらの文献に開示されている符号化データ構造はターゲットフィーチャを含み、これらのターゲットフィーチャにより、感知装置が各構造の位置を識別することができる。各構造内のフィーチャの相対位置を解釈して、感知されたときの構造の遠近歪みを求めることもでき、それによって、感知データの遠近補正を実施し得る。ただし、感知装置がこの構造内のデータを復号し得るには、この構造の回転方向の向きを求めることが必要である。これは一般に、なんらかの方法で少なくとも1つの回転対称なフィーチャを設けることによって実現される。例えば、一実施形態では、他のフィーチャに関連して配置し得る鍵穴形状のフィーチャを設け、次いでそれを認識して、感知装置に関して構造の回転方向の向きを見つける。こうすると、構造の位置および回転方向の向きから、データ構造内での実際のデータの位置を推測し得るので、データ構造内で符号化データを復号することができる。
【発明の開示】
【発明が解決しようとする課題】
【0017】
この配置の欠点は、1つまたは複数の向きのフィーチャ専用のスペースを設ける必要があることと、これらのフィーチャに損傷が存在しても回転方向の向きを求めることができるように、このようなフィーチャに冗長性を含めることが難しいことである。したがって、スペースがより効率的に使用され、誤り検出および/または誤り訂正が可能なように、向きの情報を符号化することが望ましい。
【課題を解決するための手段】
【0018】
本発明の第1態様によれば、あるレイアウトに従って基板上または基板内に配設された機械可読の符号化データが開示される。このレイアウトは、少なくともn次の回転対称性を有する。ただし、nは少なくとも2である。このレイアウトにより、n個のシンボルが整数m回繰り返されるシーケンスを含む向きの符号語が符号化される。ただし、mは、1またはそれ以上である。符号化されたシンボルはそれぞれ、このレイアウトの回転対称中心の周りでn個の位置に分配されて、このレイアウトのn個の向きのそれぞれにおいてこれらのシンボルを復号することにより、向きの符号語のn個の表現が生成される。各表現は、向きの符号語の異なる巡回シフトを含み、このレイアウトの回転の程度を示す。この向きの符号語は、誤り許容型である。
【0019】
好ましくは、向きの符号語は、向きの符号語の各表現を、向きの符号語のシンボルの1つが破損していても正確に復号し得るのに十分に誤りを許容するものである。
【0020】
好ましくは、向きの符号語は、向きの符号語の各表現を、向きの符号語のシンボルの2つ以上が破損していても正確に復号し得るのに十分に誤りを許容するものである。
【0021】
好ましくは、レイアウトは、レイアウト領域内の基板上で繰り返される。
【0022】
好ましくは、このレイアウト領域は、2つ以上のレイアウトのタイプからなる複数のレイアウトを含み、各レイアウトは、そのレイアウトのタイプを符号化する。
【0023】
好ましくは、機械可読の符号化データは、分配された符号語を符号化する。この分配された符号語の断片は、この分配された符号語が、異なるタイプの複数の隣接するレイアウトに配置された断片から再構築され得る所定のやり方で、2つ以上のレイアウトのタイプの間に分配される。より好ましくは、レイアウトのタイプの数は、2、3、4、および6の1つである。
【0024】
好ましくは、このレイアウトは、局所符号語を符号化する。この局所符号語の断片は、この局所符号語がこれらの断片から再構築され得る所定のやり方でレイアウト内に分配される。
【0025】
一形態では、これらのレイアウトは、基板上で合わせて束ねられる。
【0026】
好ましくは、このレイアウトは、直線、正方形、長方形、三角形、または六角形のいずれかの形状とする。
【0027】
好ましくは、nは、2、3、4、および6の1つである。
【0028】
好ましくは、機械可読の符号化データは、この符号化データを読み取るのに使用する機械によって、レイアウトの暫定位置および回転を求めることができる1つまたは複数のターゲットフィーチャを含む。
【0029】
好ましくは、これらのターゲットフィーチャは、機械によって読み取られた後で、このレイアウトの、または各レイアウトの符号化データを遠近補正し得るように構成される。より好ましくは、この機械可読の符号化データは、少なくとも4つのターゲットフィーチャを含む。
【0030】
好ましくは、機械可読の符号化データは複数のレイアウトを含む。ターゲットフィーチャの少なくとも一部は、これらのレイアウトの少なくとも2つによって共有される。
【0031】
好ましくは、符号化データは、基板上に印刷される。
【0032】
好ましくは、符号化データは、人間の平均的な裸眼に対して可視性が低い、または不可視のインクで表面上に印刷される。より好ましくは、このインクは、人間の平均的な裸眼には実質的に不可視である赤外インクである。
【0033】
好ましくは、各レイアウトの符号化データにより、ユーザのデータが定義される。
【0034】
好ましくは、このユーザのデータは、表面のある領域に対する相対的なレイアウトパターンの位置を示す位置データを含む。
【0035】
好ましくは、このユーザのデータは、レイアウトが配設される表面のある領域を識別する識別データを含む。
【0036】
好ましくは、このユーザのデータは、機械がレイアウトのパターンまたはサブパターンを読み取った後で実施される関数を識別する関数データを含む。
【0037】
本発明の第2態様によれば、上記段落で開示した機械可読の符号化データを担持する表面が開示される。
【0038】
好ましくは、この表面は、平面または曲面である。
【0039】
好ましくは、この表面はさらに、目に見える標識を含む。より好ましくは、この目に見える標識は、文字列、図形、画像、フォーム、フィールド、およびボタンのいずれか1つまたは複数を含む。
【0040】
好ましくは、この目に見える標識は、符号化データの少なくとも一部に隣接して、あるいはそれと同じ場所に配設される。
【0041】
好ましくは、この表面は、基板によって画定されるものである。より好ましくは、この基板は、紙、カード、または別の薄層媒体である。
【0042】
好ましくは、この表面は、使用者とコンピュータの対話を可能にするインターフェース表面として使用されるように構成される。
【0043】
本発明の第3態様によれば、インターフェース表面を生成する方法が開示される。この方法は、
プリンタでユーザのデータを受け取るステップと、
上記段落で開示した、このユーザデータを組み込んだ機械可読の符号化データを生成するステップと、
この符号化データを基板上に印刷するステップとを含む。
【0044】
好ましくは、この方法はさらに、この基板上に目に見える標識を印刷するステップを含む。
【0045】
好ましくは、これら符号化データおよび目に見える標識は、実質的に同時に基板上に印刷される。
【0046】
本発明の第4態様によれば、感知装置を使用して、上記段落で開示した機械可読の符号化データを読み取る方法が開示される。この方法は、
(a)感知装置を使用して、レイアウトの符号化データを読み取るステップと、
(b)このレイアウトの符号化データを復号して、少なくとも向きの符号語の表現を求めるステップと、
(c)この向きの符号語の表現を用いて、レイアウトの回転の程度を求めるステップとを含む。
【0047】
好ましくは、ステップ(a)は、
基板を画像化して、基板の画像を生成するサブステップと、
この画像を処理して、符号化データの1つまたは複数のターゲットフィーチャを位置決定するサブステップと、
これら位置決定されたターゲットフィーチャに基づいて、向きの符号語の符号化されたシンボルの少なくとも1つの位置を求めるサブステップとを含む。
【発明を実施するための最良の形態】
【0048】
次に、単なる非限定的な例として、添付の図面を参照して本発明の好ましい実施形態および他の実施形態を説明する。
【0049】
本明細書では、(参照により内容を本明細書に組み込む、本出願人の同時係属PCT出願公開WO 01/22207号(Method and System for Instruction of a Computer)に開示されている)ネットページ(netpage)システムが使用する表面符号化を定義して、(参照により内容を本明細書に組み込む、本出願人の同時係属PCT出願公開WO 00/72230号(Sensing Device)に開示されている)ネットページペンなどのネットページ感知装置、および(参照により内容を本明細書に組み込む、本出願人の同時係属PCT出願公開WO 01/41046号(Viewer with Code Sensor)に開示されている)ネットページビューワと組み合わせて、普通なら受動的な表面に双方向性を付与する。
【0050】
ネットページの符号化表面と相互作用すると、ネットページ感知装置は、この感知装置が相対的に移動する表面領域の識別情報およびこの領域内での感知装置の絶対経路をともに示すデジタルインクストリームを生成する。
【0051】
1.表面符号化
ネットページの表面符号化は、タグを密にかつ平らにタイル状に並べることからなる。各タグは、この面内でそれ自体の位置を符号化する。各タグは、隣接するタグとあいまってこのタグを含む領域の識別子も符号化する。ネットページシステムでは、この領域は一般に、1枚の紙の片面など、タグ化された表面の範囲全体に相当する。
【0052】
各タグは、2種類の要素を含むパターンによって表される。第1の種類の要素は、ターゲットである。ターゲットにより、符号化された表面の画像内でタグを位置決定することができ、このタグの遠近歪みを推測することができる。第2の種類の要素は、マクロドットである。各マクロドットは、それが存在するか否かで、ビット値を符号化する。
【0053】
このパターンは、光学式画像システム、特に、近赤外域で狭帯域応答する光学システムによってこのパターンを取得し得るように、符号化された表面上で表現される。このパターンは典型的には、狭帯域赤外インクを使用してこの表面上に印刷される。
【0054】
1.1 タグ構造
図1に、完全なタグ700の構造を示す。6つの黒丸702はそれぞれ、ターゲットである。このタグおよび全体的パターンは、物理的なレベルで6方向に対称である。
【0055】
ダイヤモンド形状の領域704はそれぞれシンボルを表し、各シンボルは4ビットの情報を表す。
【0056】
図2に、シンボルの構造を示す。この構造は、4つのマクロドット706を含む。各マクロドットは、それが存在するか否かによって、1ビットの値を表し、存在する場合には1、存在しない場合には0である。
【0057】
本明細書を通じて、マクロドットの間隔は、パラメータsによって指定される。この間隔の公称値は、1インチ当たり1600ドットのピッチで印刷した9個のドットに基づき、143μmである。ただし、この間隔は、パターンを生成するのに使用する装置の能力に従って、規定範囲内で変化し得る。
【0058】
一般に、本明細書で指定した「理想的な」パターンから、例えば装置の制限のために逸脱したパターンで表面が符号化される場合、この偏差は、この表面を介して取得されたデジタルインクが、この偏差について適切に補正され得るように記録されなければならない。
【0059】
図3に、5つの隣接したシンボルのアレイを示す。マクロドットの間隔は、シンボル内およびシンボル間でともに均一である。
【0060】
図4に、シンボル内でのビットの順序付けを示す。シンボル内で、ビット0は最下位ビットであり、ビット3は最上位ビットである。この順序付けは、シンボルの向きに対して相対的なものであることに留意されたい。タグ内の個々のシンボルの向きは、タグの図(例えば、図1参照)で、シンボルの標示の向きによって示す。一般に、タグの個々のセグメント内のすべてのシンボルの向きは同じであり、タグの中心に最も近い基部のシンボルに一致する。
【0061】
好ましい実施形態では、マクロドットだけが、パターン中のシンボルの表現の部分である。本明細書では、シンボルのダイヤモンド形状の輪郭は、タグの構造をより明瞭にするために用いる。例として、図5に、タグの実際のパターンを、すべてのビットの組とともに示す。好ましい実施形態では、実際には、タグのビットをすべて設定することはできないことに留意されたい。
【0062】
公称上、マクロドットは、公称直径が(5/9)sの円形である。ただし、この直径は、パターンを生成するのに使用する装置の能力に従って、規定範囲内で変化し得る。
【0063】
公称上、ターゲットは、公称直径が(17/9)sの円形である。ただし、この直径は、パターンを生成するのに使用する装置の能力に従って、規定範囲内で変化し得る。
【0064】
図1のタグ構造で示す各シンボルは、一意の標示を有する。各標示は、英字の接頭辞および数字の接尾辞からなる。
【0065】
1.2 誤りの検出および訂正
符号化するデータが、ガロア体GF(q)から得られたq元シンボルを有するkシンボルブロックに分割されると仮定する。すべての可能なk個の要素からなる集合m=(m0,m1,...,mk−1)は、GF(q)上でベクトル空間を形成し、qk個の可能なベクトルを含む。長さがnの、対応するブロック訂正符号Cは、1組のM個のnシンボル符号語{c0,c1,...,cM−1}からなる。ただし、M=qk、n>kであり、各符号語の形式は、c=(c0,c1,...,cn−1)である。あるデータブロックを符号化する場合、符号器は、このデータブロックをCの符号語上にマッピングする。GF(q)上のすべての可能なn個の要素からなる集合は、qn個のベクトルを含むが、符号語はM=qk個しかないので、この符号は冗長性を有する。この冗長性は、r=n−logqM=n−kによって対数的に、または符号化率R=k/nによって表される。符号Cは、それがGF(q)上でベクトル副空間を形成する場合、すなわち、スカラーとの加算および乗算において閉じている(そのため、ゼロベクトルを含む)場合には、線形符号である。この場合、この符号は、次元kを有するといい、(n,k)符号と称する。
【0066】
2つの符号語のハミング距離は、これら2つの符号語で値が異なるシンボルの数である。ブロック符号の最小距離dminは、この符号中の任意の別個の符号語対の最小ハミング距離である。最大距離dmaxは、この符号中の任意の別個の符号語対の最大ハミング距離である。
【0067】
誤りパターンにより、符号語にシンボル誤りが導入される。この誤りパターンは、その重み、すなわちこの誤りパターンが破損するシンボルの数によって特徴づけられる。誤りパターンが検出不可能な場合、この誤りパターンにより、ある符号語が別の符号語と同じに見えるはずである。そのため、最小距離がdminの符号は、重みがdmin−1以下のすべての誤りパターンを検出し得る。所与の符号は、重みが大きいほど多くの誤りパターンを検出し得るが、上記のことから、符号がすべての誤りパターンを検出し得る重みを制限する。
【0068】
サンプリングされた語が誤りパターンによって破損した可能性がある場合、復号器はこのサンプリングされた語を、Cの符号語上に、この符号語が、最初に書き込まれた符号語と異なる確率を最小限に抑えるようにマッピングし、次いで、この符号語をデータブロック上にマッピングする。より具体的な特徴付けが存在しない場合には、重みが小さい誤りパターンのほうが、重みが大きい誤りパターンよりも可能性が高く、重みが等しい誤りパターンはすべて、可能性が等しいと仮定する。そのため、最大尤度で書き込まれた符号語は、サンプリングされた語にハミング距離が最も近い符号語になる。サンプリングされた語が、正しい(書き込まれた)符号語よりも、誤った符号語に近い場合、復号器は誤りを犯したことになる。定義により符号語は、少なくとも距離dminは離れているので、復号器の誤りは、誤りパターンの重みが、dmin/2以上の場合にのみ起こり得る。そのため、最大尤度復号器は、重みが[(dmin−1)/2]以下のすべての誤りパターンを訂正し得る。同等に、この復号器は、2t<dminである限り、t個の誤りを訂正し得る。
【0069】
線形符号の最小距離は、シングルトン(Singleton)の限界式dmin≦n−k+1によって制限される。このシングルトンの限界式を等号で満足する符号を、MDS(最大距離分離可能)と呼ぶ。リードソロモン符号(Wicker,S.B.、V.K.Bhargava監修、Reed−Solomon Codes and Their Applications、IEEE Press、1994年を参照されたい。この内容を参照により本明細書に組み込む)は、最も一般に用いられるMDS符号である。2進符号はMDSではない。
【0070】
消失は、破損したとみなされるサンプリング語のシンボルである。符号語中で消失位置は既知なので、消失は、誤りとして処理するのではなく、復号を行うために無視することができる。例えば、サンプリングされた語の中の消失シンボルと、それに対応する符号語中のシンボルとの距離は、最大尤度復号法の基礎として用いるハミング距離には含まれない。そのため、1つの消失ごとに、最小距離は事実上1だけ短くなる。すなわち、消失がf個存在すると、最大で[(dmin−f−1)/2]個の誤りを訂正することができる。同等に、この復号器は、2t+f<dminである限り、t個の誤りおよびf個の消失を訂正し得る。MDS符号では、これは、2t+f<n−k+1になる。
【0071】
符号が組織的であるのは、その符号語がそれぞれ、それに対応するデータブロックを、改変されずに固定位置で含む場合である。この場合、この符号のデータ(またはメッセージ)座標と、この符号の冗長性(またはパリティ)座標を区別することが可能である。
【0072】
線形符号化率は、この符号のパンクチャによって、すなわち、その冗長性座標の1つまたは複数を消去することによって増加させることができる。g個の座標を消去することによって、(n,k)符号は、(n−g,k)符号に変換される。パンクチャされた符号の最小距離は、dmin−gになる。明らかに、dmin−g<2の場合、パンクチャにより、この符号は1つの誤りさえ訂正し得なくなり、dmin−g<1の場合、パンクチャにより、この符号は1つの誤りさえ検出し得なくなる。同等に、パンクチャされた符号の長さw=n−gは、誤りを検出するためにはw≧n−dmin+1に従わなければならず、誤りを訂正するためにはw≧n−dmin+2に従わなければならない。パンクチャされた符号に対して復号器は単に、消去された座標を、元の符号に関する消失として処理することができる。
【0073】
ブロック符号Cが巡回符号になるのは、符号語c=(c0,c1,..,cn−2,cn−1)がCに含まれ、且つ、cの右巡回シフトである符号語c’=(cn−1,c0,c1,...,cn−2)がCに含まれる場合である。その結果、cのn個の巡回シフトもすべて、Cで符号語になる。符号語の数qkが、符号の長さnよりも大きい場合、この符号は、複数の別個の巡回を含み、各巡回iはsi個の固有の符号語を含む。ただし、nはsiで割り切れる。この符号がゼロベクトルを含む場合、このゼロベクトルはそれ自体の巡回を形成する。
【0074】
1.3 向きを示す巡回位置符号
タグは、(参照により内容を本明細書に組み込む、本出願人の同時係属PCT出願公開WO 02/084473号(Cyclic Position Codes)に開示されている)24元(6,1)巡回位置符号語を含む。この巡回位置符号語を、このタグの6つの可能な向きのいずれかで復号して、このタグの実際の向きを求めることができる。この巡回位置符号語の一部であるシンボルは、「R」の接頭辞を有し、下位から上位に向かう順に0〜5に番号が付けられる。
【0075】
この巡回位置符号語は、(0,5,6,9,A16,F16)である。この巡回位置符号語は、4ビットシンボルが16個の可能な値を有するにもかかわらず、6つの別個のシンボル値しか用いないことに留意されたい。復号中に検出される未使用シンボル値はいずれも、消失として処理される。符号語中の実際のシンボルの順序も、実際に使用するシンボル値のサブセットの構成も重要ではないことに留意されたい。ただし、シンボル間最小距離を最大にするサブセットを選択することが有利である。というのは、こうすると、ビット誤りが、シンボル誤りよりも消失を引き起こす可能性が高くなるようにする助けになるからである。これが有利なのは、(以下で論じるように)符号の消失訂正能力が、符号の誤り訂正能力のほぼ2倍だからである。
【0076】
図6に、向きを示す巡回位置符号語のレイアウトを示す。図では、この符号語に陰影を付けて示す。
【0077】
巡回位置符号語の最小距離は6であり、したがって、巡回位置符号語は、消失が最大で1つの場合、2つのシンボルの誤りを訂正することができ、2つまたは3つの消失がある場合には、1つのシンボルの誤りを訂正することができ、消失が4つ以上あると、シンボルの誤りを訂正することができない。
【0078】
表1に、巡回位置符号の第1符号語と、この符号の各符号語とのハミング距離を示す。このハミング距離は、単一のシンボル誤りが、符号語中の6つの可能な位置のそれぞれに順にある状態で計算したものである。破損したシンボルは、いずれの場合も◆で示す。最悪の場合を想定して、このシンボルは他の各符号語の対応するシンボルにまで破損したと仮定する。破損した符号語とその破損していない元の符号語の距離は、いずれの場合にも1であり、破損した符号語と他の各符号語の距離は、いずれの場合にも5である。どの符号語も第1符号語のなんらかの巡回シフトであるので、この表は、この符号が、任意の符号語中の任意の単一のシンボル誤りを訂正し得ることを示している。
【0079】
その延長で、任意の2つのシンボル誤りが存在する場合、破損した符号語とその破損していない元の符号語の距離は、いずれの場合にも2に増加し、破損した符号語と他の各符号語の距離は、いずれの場合にも4に減少することがわかる。したがって、この表は、この符号が、任意の符号語中の任意の2つのシンボル誤りを訂正し得ることを示している。これを表2に示す。
【表1】
【表2】
【0080】
1つまたは複数の消失が存在する場合に、単に消失した1つ(または複数)の座標を無視することによって同じ距離計算を実施し得る。これを表3に示す。表3では、1つの消失を−で示す。
【表3】
【0081】
サンプリングした巡回位置符号語を復号することは、消失を検出することと、次いで、残りの(消失していない)シンボルと、それに対応する、元の巡回位置符号語の6つの巡回シフト中のシンボルとの距離を計算することからなる。その後、このサンプリングした符号語を、このサンプリングした符号語から距離が最も近いシフトした符号語として復号する。サンプリングした符号語に同じ距離で最も近いシフトした符号語が2つ以上ある場合には、復号することはできない。サンプリングした符号語をシフトした符号語に復号すると、この符号語のシフトは既知なので、サンプリングの向きに対するタグの回転がわかる。
【0082】
巡回位置符号語を形成する6つのシンボルに加えて、隣接するタグの巡回位置符号語の少なくとも6つの追加のシンボルも視野内に見える。これら余分なシンボルを追加して復号する手間をかければ、12個のシンボルを使用して巡回位置符号語を復号することができる。これは2つの方法で実施し得る。第1の手法では、消失したシンボルをどれも、単にそれに対応する、他のタグの巡回位置符号語の1つからのシンボルで置き換える。ただし、これは、この対応するシンボル自体が消失していない場合である。第2の手法では、12個のシンボルすべてを、12シンボル符号語として処理する。
【0083】
この巡回位置符号を用いて、このタグが鏡面反射で、例えば、このタグが、このタグを配設した透明な基板の裏面によって写像されて取得されたかどうかを検出することもできる。
【0084】
1.4 局所符号語
このタグは、このタグに固有な情報を符号化するのに使用する3つの完全な符号語を局所的に含む。各符号語は、パンクチャされた24元(9,5)リードソロモン符号のものである。したがって、このタグは、このタグに固有な情報を60ビットまで符号化する。
【0085】
図7に、これら3つの局所符号語のレイアウトを示す。図7では、符号語Aに陰影を付けて示す。
【0086】
1.5 分配した符号語
このタグは、3つの隣接するタグ全体にわたって分配され、かつ、1組の連続したタグに共通する情報を符号化するのに用いる3つの符号語の断片も含む。各符号語は、パンクチャされた24元(9,5)リードソロモン符号のものである。したがって、3つの隣接するタグはどれもともに、1組の連続したタグに共通する情報を60ビットまで符号化する。
【0087】
図8に、これら3つの符号語の断片のレイアウトを示す。
【0088】
図9に、これら3つの完全な符号語のレイアウトを、3つの隣接するタグ全体にわたって分配した状態で示す。これら分配した符号語に関して、タグのタイプは3つある。これらを、下位から上位に向かう順にP、Q、およびRと称する。
【0089】
図10に、これらP、Q、およびRのタグがどのように、連続してタイル状に並べられたタグの形で繰り返されるかを示す。このようにタイル状に並べることによって、3つの隣接するタグの組がどれも、各タイプのタグを1つ含み、したがって、1組の完全な分配した符号語を確実に含むようにする。隣接するタグの個々の組に対する、分配した符号語の位置合わせを決定するために用いるタグのタイプは、各タグの局所符号語の1つの形で符号化される。
【0090】
図11に、3つの隣接するタグの完全な構造を、これらのタグの向きの巡回位置符号語、局所符号語、および分配した符号語を含めて示す。
【0091】
図12に、タグのセグメント708の幾何形状を示す。
【0092】
図13に、マクロドットの間隔を同一に維持するために必要とされるタグのセグメントの間隔d=(1−30.5/2)sを示す。30.5は、3の0.5乗、即ち、3の正の平方根を意味する。
【0093】
図14に、ターゲット位置に対するセグメント間隔dの影響を示す。緊密に(すなわち、d=0で)充填されたセグメントに関するターゲット位置の公称位置と比較して、対角ターゲットは(Δx,Δy)=(±1/30.5,±1)dだけ変位させなければならず、水平ターゲットは(Δx,Δy)=(±2/30.5,0)dだけ変位させなければならない。
【0094】
1.6 リードソロモン符号化
【0095】
局所符号語および分配した符号語はともに、パンクチャされた24元(9,5)リードソロモン符号を用いて符号化される。
【0096】
24元(9,5)リードソロモン符号は、各符号語において、20個のデータビット(すなわち、5つの4ビットシンボル)および16個の冗長ビット(すなわち、4つの4ビットシンボル)を符号化する。このリードソロモン符号は、4つのシンボルの誤りを検出することができ、2つのシンボルの誤りを訂正することができる。
【0097】
パンクチャされた24元(9,5)リードソロモン符号は、6つの冗長座標を取り除いた24元(15,5)リードソロモン符号である。
【0098】
この符号は、以下の原始多項式を有する。
【0099】
p(x)=x4+x+1
【0100】
この符号は、以下の生成多項式を有する。
【0101】
g(x)=(x+α)×(x+α2)×...×(x+α10)
【0102】
リードソロモン符号の詳細な説明については、Wicker,S.B.、V.K.Bhargava監修、Reed−Solomon Codes and Their Applications、IEEE Press、1994年を参照されたい。
【0103】
2.タグ座標空間
タグ座標空間710は、1対の半直交座標aおよびbによって定義する。図15に、このタグ座標空間と表面x−y座標空間の公称上の関係を示す。
【0104】
この座標は、(以下の「符号化および印刷の考察」という見出しの節で論じるように)意図する印刷装置によるタグパターンの再現性が確保されるためには必然的に半直交にしかならない。
【0105】
意図する印刷装置のさらなる助けとするために、表面符号化、したがって、a−b座標空間を、x−y座標空間に対して90度の任意の倍数だけ回転することができる。
【0106】
x−y座標空間に対してa−b座標空間を反時計回りにRだけ回転させると、これら2つの座標空間の関係は、以下のようになる。
x=acos(30°−R)−bsin(60°−R) (式1)
y=asin(30°−R)+bcos(60°−R) (式2)
【数1】
【数2】
【0107】
図16に示すように、整数aおよびbの座標は、タグPの中心で交わるように定義する。この図では、整数aおよびbの座標の等値線をそれぞれ表す線714と712を示す。
【0108】
表面符号化では、個々のタグ化した表面上でのx−y(またはa−b)の原点位置、あるいは、この表面に対するx−y(またはa−b)座標空間の向きを指定しないことに留意されたい。表面符号化では、これら2つの座標空間の関係しか定義しない。この関係は、ネットページのタグ化した表面と相互作用させるのに使用するネットページ感知装置によって生成されるデジタルインクに埋め込まれたx−y座標に現れる。
【0109】
3.タグ情報の内容
表4では、表面符号化の際に埋め込まれる情報フィールドを定義する。表5では、これらのフィールドを、局所符号語および分配された符号語にマッピングする方法を定義する。
【表4】
【0110】
図17に、タグおよびその6つの最近接タグを示す。これらのタグはそれぞれ、活動区域マップおよび入力区域マップにおいてこれらタグに対応するビット指標で標示する。
【0111】
領域IDの上位55ビットは、分配した符号語の形で符号化されるので、それらは、連続してタイル状に並べられたタグ全体について必ず一定である。ただし、下位41ビットは、局所符号語の形で符号化され、そのため、タグ間で任意に変化し得る。
【0112】
個々の表面符号化に対して、aおよびbの座標に専用のビット数は、座標精度フィールドを介して構成可能である。このようにして、タグ化される表面のサイズに合わせて精度を調整することができ、それによって、より精度の高い領域ID空間を効率的に使用し得る。領域IDは、全精度95ビット空間から割り当てることができるが、個々の座標精度wについての制約により、割り当てられた各領域IDの下位2wビットはゼロにならなければならない。ほぼ同等に、精度に固有のプールから、異なる精度の領域IDを割り当てることができ、割り当てられた各領域IDに指標を付け、プールに固有の方法で参照し得る。
【表5】
【0113】
活動区域マップは、対応するタグが活動区域のメンバであるかどうかを示す。活動区域は、そこで取得された入力はいずれも直ちに、解釈を行うために対応するネットページサーバに転送すべき区域である。この活動区域により、ネットページ感知装置は、この入力が直ちに実施されることを使用者に知らせることもできる。
【0114】
入力区域マップは、対応するタグが入力区域のメンバであるかどうか、すなわち、ある形式の範囲に存在するかどうかを示す。この入力区域により、ネットページ感知装置は、この入力がアプリケーションに提示されることを使用者に知らせることができる。
【0115】
4.符号化および印刷の考察
(参照によりともに内容を本明細書に組み込む、本出願人の同時係属PCT出願公開WO 01/89851号(Print Engine/Controller and Printhead Interface Chip Incorporating the Print Engine/Controller)およびWO 01/89838号(Printed Page Tag Encoder)に開示されている)PEC(印刷エンジンコントローラ)は、(1ページ当たり)2つの固定された24元(15,5)リードソロモン符号語および(1つのタグ当たり)6つの可変の24元(15,5)リードソロモン符号語の符号化に対応する。さらに、PECは、矩形ユニットセルによるタグの解釈に対応する。この矩形ユニットセルのレイアウトは(1ページ当たり)一定であるが、その可変符号語データは、ユニットセル間で変化し得る。PECでは、ページの移動方向にユニットセルが重なり合うことができない。
【0116】
図18に、この表面符号化に適合するPECユニットセル718の好ましい実施形態を、タイル状に並べたタグに重ね合わせて示す。図19に、ここで提案するPECユニットセルを、実際のP、Q、およびRのタイプのタグ構造に重ね合わせて示す。ここで提案するユニットセルは、Pタイプのタグを中心にして水平に置かれていることに留意されたい。このタグ構造およびユニットセルは、ユニットセルが正確に、6つの可変符号語(すなわち、列nについて、Rn:A、Pn:A、Qn:A、{R,P,Q}n:B、{R,P,Q}n:C、および{R,P,Q}n+1:B)、ならびに3つの固定された符号語D、E、およびFを含むように設計される。
【0117】
符号語D、E、およびFの少なくとも1つは、PECに渡されるTFS(タグフォーマット構造)の形であらかじめ符号化しなければならない。というのは、PECは、2つの固定された符号語の符号化にしか対応しないからである。符号語D、E、およびFのいずれか、または全部をTFSの形であらかじめ符号化することができるはずである。
【0118】
PECは、1つのTFSの列当たりの固有ビットアドレスを32個に制限する。D、E、およびFの符号語があらかじめ符号化されていると仮定すると、ユニットセルの内容は、この制限に沿ったものになる。
【0119】
PECは、TFSの幅も384に制限する。ユニットセルの内容は、この制限に沿ったものにする。
【0120】
ページサイズが適度な場合、BおよびCの符号語中の可変座標ビット数を控えめにして、ルックアップテーブルによる符号化を扱いやすくすることに留意されたい。ルックアップテーブルによる符号語Aの符号化も可能とし得る。リードソロモン符号は組織符号なので、ルックアップテーブルに表示されるのは冗長データだけでよいことに留意されたい。
【0121】
5.画像化および復号の考察
図20に、タグ全体を確実に取得するために必要とされる、すなわち、表面符号化と視野の位置合わせが任意である場合の好ましい最小画像化視野720を示す。最小限の視野の直径は36sである。
【0122】
タグ構造をこのように仮定すると、対応する復号シーケンスは以下のとおりである。
・ 完全なタグのターゲットを位置決定する
・ ターゲットから遠近変換を推測する
・ 巡回位置符号をサンプリングする
・ 巡回位置符号を復号する
・ 巡回位置符号から向きを求める
・ 局所リードソロモン符号語をサンプリングする
・ 局所リードソロモン符号語を復号する
・ タグのタイプを求める
・ タグの回転を求める
・ 分配されたリードソロモン符号語をサンプリングする(タグのタイプを参照して、ウィンドウを法として位置合わせする)
・ 分配されたリードソロモン符号語を復号する
・ 座標の精度を求める
・ 領域IDを求める
・ タグのa−bの位置を求める
・ タグの回転を参照して、タグのa−b位置をx−y位置に変換する
・ 方向づけられたターゲットから3D変換を推測する
・ タグのx−y位置および3D変換からペン先のx−y位置を求める
・ ペン先の位置の活動区域/入力区域のステータスを求める
・ ペン先の活動区域/入力区域のステータスに基づいて、ローカルフィードバックを生成する
・ デジタルインクの形で、領域ID、ペン先のx−y位置、ペン先の活動区域/入力区域のステータスを符号化する
【0123】
図21に、タグの画像処理および復号プロセスの流れを示す。(800で)タグパターンの生画像802を、例えば、CCD画像センサ、CMOS画像センサ、またはレーザ走査型フォトダイオード画像センサなどの画像センサによって取得する。次いで、典型的には(804で)この生画像を強調して、コントラストが改善され、かつ画素の強度がより均一になった強調画像806を生成する。画像強調は、グローバルな、またはローカルな範囲の伸張、均等化などを含み得る。次いで、典型的には(808で)強調画像806をフィルタリングして、フィルタリングされた画像810を生成する。画像のフィルタリングは、ローパスフィルタリングからなり得る。ローパスフィルタ用のカーネルサイズは、マクロドットは不明瞭になるが、ターゲットは保存されるように調整する。フィルタリングステップ808は、ターゲットフィーチャを強調するために、(エッジ検出などの)追加のフィルタリングを含み得る。次いで、(812で)フィルタリングされた画像810を処理してターゲットフィーチャを位置決定し、それによって1組のターゲットポイントが得られる。これは、空間相互関係がタグの既知の幾何形状と一致するターゲットフィーチャを探索することからなり得る。ターゲット候補は、フィルタリングされた画像810の最大値から直接識別することもできるし、あるいは、米国特許出願第09/575154号に記載されているように、(典型的には、フィルタリングされた画像810中の極大値に基づいて、強調画像806の画素から計算する)ターゲットの(2値またはグレースケールの)形状モーメントなどによって、別の特徴付けおよびマッチングの対象とすることもできる。この探索は典型的には、視野の中心から開始する。探索ステップ812によって見つけられたターゲットポイント814から、画像センサおよびその関連する光学系が占める3次元空間におけるタグの位置が間接的に明らかになる。ターゲットポイント814は、(2値またはグレースケールの)ターゲットの重心から導出されるので、これらは一般に、画素未満の精度で定義される。
【0124】
(816で)タグの実際の3D変換、その延長で、タグに対する相対的な感知装置の3D変換(または姿勢)818を求めることが有用である。これは、米国特許出願第09/575154号に記載されているように解析的に、あるいは、(参照により内容を本明細書に組み込む、P.R.Wolf、B.A.Dewitt、Elements of Photogrammetry with Applications in GIS、3rd Edition、McGraw Hill、2000年2月に記載されているように)遠近歪みのあるターゲットポイントが観測された場合、最大尤度推定量(最小自乗法による調整など)を用いてパラメータ値を3D変換に合わせることによって実施し得る。3D変換は、タグの3D並進移動、タグの3D方向づけ(回転)、ならびに感知装置の焦点距離および表示域尺度を含み、そのため、適合すべき8つのパラメータ、あるいは、(例えば、設計によって、または較正ステップから)焦点距離および表示域尺度が既知の場合には、6つのパラメータが与えられる。各ターゲットポイントから、観測された座標を既知の座標に関係づける1対の観測方程式が得られる。8つのパラメータを適合させる場合、最大尤度推定を可能にするのに十分な冗長性を提供するために、5つ以上のターゲットポイントが必要とされる。6つのパラメータを適合させる場合には、4つ以上のターゲットポイントが必要とされる。タグの設計が、最大尤度推定を可能にするのに最低限必要とされるよりも多くのターゲットを含む場合、最大で、最低限必要とされるターゲットが認識できないほど損傷している場合でも、タグを認識し、復号することができる。
【0125】
マクロドットの値を正確にサンプリングし得るように、タグの遠近変換を推測しなければならない。ターゲットポイントのうち4つを取り出して、タグ空間内で既知のサイズの矩形の遠近歪みをもつコーナとし、タグ空間と像空間の4つのポイント対を関係づける周知の方程式を解くことに基づいて(参照により内容を本明細書に組み込む、Heckbert,P.、Fundamentals of Texture Mapping and Image Warping、修士論文、Dept.of EECS、カリフォルニア大学バークレー校、Technical Report UCB/CSD 89/516号、1989年6月参照)、(820で)8自由度の遠近変換822を推測する。あるいは、この遠近変換は、3D変換818が利用可能な場合には、それから導出することができる。
【0126】
タグ空間から像空間への推測された遠近変換822を用いて、(824で)向きを示す巡回位置符号語の各データビットの既知の位置を、タグ空間から像空間に投影し、そこで、実数値位置を用いて、(824で)4つ(またはそれ以上)の該当する隣接画素を強調入力画像806内で双一次(または高次)内挿する。得られたマクロドットの値と適切な閾値を比較して、それが0ビットまたは1ビットを表すかどうかを判定する。サンプリングを行うために、向きを示す巡回位置符号語の空間レイアウトを固定し、向きに関して不変にする。
【0127】
完全な向きを示す巡回位置符号語のビットがサンプリングされた後で、(830で)前に説明したように向きを示す符号語を復号して、サンプリングの向きに対するタグの向き832が得られる。
【0128】
タグ空間から像空間への推測された遠近変換822を用いて、(834で)局所符号語および分配された符号語の各データビットの既知の位置を、タグ空間から像空間に投影し、そこで、実数値位置を用いて、(834で)4つ(またはそれ以上)の該当する隣接画素を強調入力画像806内で双一次(または高次)内挿する。得られたマクロドットの値と適切な閾値を比較して、それが0ビットまたは1ビットを表すかどうかを判定する。サンプリングを行うために、局所符号語および分配された符号語の空間レイアウトを固定するが、向きに関しては不変にする。したがって、レイアウトの実際の向きを求めるには、向き832を用いる。
【0129】
1つまたは複数の完全な符号語のビットがサンプリングされた後で、(838で)これらの符号語を復号して、タグ内で符号化された所望のデータ840が得られる。符号語の冗長性を利用して、サンプリングされたデータ中の誤りを検出するか、あるいは、サンプリングされたデータ中の誤りを訂正することができる。
【0130】
米国特許出願第09/575154号で論じているように、得られたタグデータ840により、直接または間接に、タグを含む表面領域およびこの領域内のタグの位置を識別し得る。したがって、この表面領域に対する相対的な感知装置の正確な位置は、タグデータ840およびタグに対する感知装置の3D変換818から導出し得る。
【0131】
結論
いくつかの特定の実施例を参照して本発明を説明してきたが、当業者なら、他の多くの形態で本発明を実施し得ることが理解されよう。
【図面の簡単な説明】
【0132】
【図1】本発明によるタグ構造の第1実施形態を示す図である。
【図2】図1のタグ構造のシンボルユニットセルを示す図である。
【図3】シンボルユニットセルアレイを示す図である。
【図4】シンボルのビット順序付けを示す概略図である。
【図5】タグパターンをすべてのビットの組とともに示す図である。
【図6】向きを示す巡回位置符号語のレイアウトを示す図である。
【図7】3つの局所符号語のレイアウトを示す図である。
【図8】分配された符号語D、E、およびFの交互に配置された断片を示す図であり、符号語Dの断片に陰影を付けて示す。
【図9】分配された符号語D、E、およびFの完全な組を含む3つの隣接するタグP、Q、およびRを示す図であり、符号語Dの断片に陰影を付けて示す。
【図10】タグP、Q、およびRを連続的にタイル状に並べたところを示す図である。
【図11】3つの隣接するタグの完全な構造を、これらのタグの向きの巡回位置符号語、局所符号語、および分配された符号語を含めて示す図である。
【図12】タグのセグメントの幾何形状を示す図である。
【図13】マクロドット間の間隔を同一に維持するために必要とされる、タグのセグメントの好ましい間隔d=(1−30.5/2)sを示す図である。
【図14】ターゲット位置に対するセグメント間隔dの影響を示す図である。
【図15】タグ座標空間と表面x−y座標空間の公称上の関係を示す図である。
【図16】タイル状に並べられたタグ上に重ね合わされたタグ座標グリッドを示す図である。
【図17】タグおよびその6つの最近接タグを示す図であり、各タグは、活動区域マップおよび入力区域マップ内で、各タグに対応するビット指標で標示されている。
【図18】この表面符号化に適合するPECユニットセルの好ましい実施形態を、タイル状に並べたタグ上に重ね合わせて示す図である。
【図19】実際のP、Q、およびRのタイプのタグ構造に重ね合わせたPECユニットセルの好ましい実施形態を示す図である。
【図20】タグ全体を確実に取得するのに必要とされる好ましい最小画像視野を示す図である。
【図21】タグの画像処理および復号プロセスの流れを示す図である。
【技術分野】
【0001】
本発明は、向きを示す巡回位置符号、および表面の位置符号化における当該巡回位置符号の使用法に関する。
【背景技術】
【0002】
本発明に関係する様々な方法、システム、および装置が、本発明の出願人または譲受人によって出願された以下の米国出願に開示されている。
「Symmetric Tags」という名称の米国特許出願第10/410484号
「Methods and Systems for Object Identification and Interaction」という名称の米国特許出願第10/409876号
「Methods and Systems for Object Identification and Interaction」という名称の米国特許出願第10/409848号
「Methods and Systems for Object Identification and Interaction」という名称の米国特許出願第10/409845号
これらの出願された出願の開示を相互参照により本明細書に組み込む。
【0003】
本発明に関係する様々な方法、システム、および装置が、本発明の出願人または譲受人によって2003年4月7日に出願された「Methods and Systems for Object Identification and Interaction」という名称のオーストラリア国仮出願第2003901617号の出願に開示されている。この同時係属出願の開示を相互参照により本明細書に組み込む。
【0004】
本発明に関係する様々な方法、システム、および装置が、本発明の出願人または譲受人によって2002年12月4日に出願された「Rotationally Symmetric Tags」という名称の同時係属PCT出願である米国特許出願第10/309358号に開示されている。この同時係属出願の開示を相互参照により本明細書に組み込む。
【0005】
本発明に関係する様々な方法、システム、および装置が、本発明の出願人または譲受人によって2002年11月22日に出願された同時係属PCT出願PCT/AU02/01572号およびPCT/AU/02/01573号に開示されている。これらの同時係属出願の開示を相互参照により本明細書に組み込む。
【0006】
本発明に関係する様々な方法、システム、および装置が、本発明の出願人または譲受人によって2002年10月15日に出願された同時係属PCT出願PCT/AU02/01391号、PCT/AU02/01392号、PCT/AU02/01393号、PCT/AU02/01394号、およびPCT/AU02/01395号に開示されている。これらの同時係属出願の開示を相互参照により本明細書に組み込む。
【0007】
本発明に関係する様々な方法、システム、および装置が、本発明の出願人または譲受人によって2001年11月26日に出願された同時係属PCT出願PCT/AU01/01527号、PCT/AU01/01528号、PCT/AU01/01529号、PCT/AU01/01530号、およびPCT/AU01/01531号に開示されている。これらの同時係属出願の開示を相互参照により本明細書に組み込む。
【0008】
本発明に関係する様々な方法、システム、および装置が、本発明の出願人または譲受人によって2001年10月11日に出願された同時係属PCT出願PCT/AU01/01274号に開示されている。この同時係属出願の開示を相互参照により本明細書に組み込む。
【0009】
本発明に関係する様々な方法、システム、および装置が、本発明の出願人または譲受人によって2001年8月14日に出願された同時係属PCT出願PCT/AU01/00996号に開示されている。この同時係属出願の開示を相互参照により本明細書に組み込む。
【0010】
本発明に関係する様々な方法、システム、および装置が、本発明の出願人または譲受人によって2000年11月27日に出願された同時係属米国出願第09/721895号、第09/721894号、第09/722174号、第09/721896号、第09/722148号、第09/722146号、第09/721861号、第09/721892号、第09/722171号、第09/721858号、第09/722142号、第09/722087号、第09/722141号、第09/722175号、第09/722147号、第09/722172号、第09/721893号、第09/722088号、第09/721862号、第09/721856号、第09/721857号、第09/721859号、第09/721860号に開示されている。これらの同時係属出願の開示を相互参照により本明細書に組み込む。
【0011】
本発明に関係する様々な方法、システム、および装置が、本発明の出願人または譲受人によって2000年10月20日に出願された同時係属米国出願第09/693415号、第09/693219号、第09/693280号、第09/693515号、第09/693705号、第09/693647号、第09/693690号、第09/693593号、第09/693216号、第09/693341号、第09/696473号、第09/696514号、第09/693301号、第09/693388号、第09/693704号、第09/693510号、第09/693336号、第09/693335号に開示されている。これらの同時係属米国出願の開示を相互参照により本明細書に組み込む。
【0012】
本発明に関係する様々な方法、システム、および装置が、本発明の出願人または譲受人によって2000年9月15日に出願された同時係属米国出願第09/663579号、第09/669599号、第09/663701号、第09/663640号に開示されている。これらの同時係属出願の開示を相互参照により本明細書に組み込む。
【0013】
本発明に関係する様々な方法、システム、および装置が、本発明の出願人または譲受人によって2000年6月30日に出願された同時係属米国出願第09/609139号、第09/608970号、第09/609039号、第09/607852号、第09/607656号、第09/609132号、第09/609303号、第09/610095号、第09/609596号、第09/607843号、第09/607605号、第09/608178号、第09/609553号、第09/609233号、第09/609149号、第09/608022号、第09/609232号、第09/607844号、第09/607657号、第09/608920号、第09/607985号、第09/607990号、第09/607196号、第09/606999号に開示されている。これらの同時係属出願の開示を相互参照により本明細書に組み込む。
【0014】
本発明に関係する様々な方法、システム、および装置が、本発明の出願人または譲受人によって2000年5月23日に出願された同時係属米国出願第09/575197号、第09/575195号、第09/575159号、第09/575132号、第09/575123号、第09/575148号、第09/575130号、第09/575165号、第09/575153号、第09/575118号、第09/575131号、第09/575116号、第09/575144号、第09/575139号、第09/575186号、第09/575185号、第09/575191号、第09/575145号、第09/575192号、第09/575181号、第09/575193号、第09/575156号、第09/575183号、第09/575160号、第09/575150号、第09/575169号、第09/575184号、第09/575128号、第09/575180号、第09/575149号、第09/575179号、第09/575187号、第09/575155号、第09/575133号、第09/575143号、第09/575196号、第09/575198号、第09/57578号、第09/575164号、第09/575146号、第09/575174号、第09/575163号、第09/575168号、第09/575154号、第09/575129号、第09/575124号、第09/575188号、第09/575189号、第09/575162号、第09/575172号、第09/575170号、第09/575171号、第09/575161号、第09/575141号、第09/575125号、第09/575142号、第09/575140号、第09/575190号、第09/575138号、第09/575126号、第09/575127号、第09/575158号、第09/575117号、第09/575147号、第09/575152号、第09/575176号、第09/575115号、第09/575114号、第09/575113号、第09/575112号、第09/575111号、第09/575108号、第09/575109号、第09/575110号に開示されている。これらの同時係属出願の開示を相互参照により本明細書に組み込む。
【0015】
表面上に1つまたは複数の符号化データ構造を設けて、この符号化データ構造を適切な感知装置によって読み取り、復号し得ることが知られている。光学センサを組み込んだこのような装置の様々な実施形態が、相互参照により本出願に組み込む文献の多くに記載されている。
【0016】
これらの文献に開示されている符号化データ構造はターゲットフィーチャを含み、これらのターゲットフィーチャにより、感知装置が各構造の位置を識別することができる。各構造内のフィーチャの相対位置を解釈して、感知されたときの構造の遠近歪みを求めることもでき、それによって、感知データの遠近補正を実施し得る。ただし、感知装置がこの構造内のデータを復号し得るには、この構造の回転方向の向きを求めることが必要である。これは一般に、なんらかの方法で少なくとも1つの回転対称なフィーチャを設けることによって実現される。例えば、一実施形態では、他のフィーチャに関連して配置し得る鍵穴形状のフィーチャを設け、次いでそれを認識して、感知装置に関して構造の回転方向の向きを見つける。こうすると、構造の位置および回転方向の向きから、データ構造内での実際のデータの位置を推測し得るので、データ構造内で符号化データを復号することができる。
【発明の開示】
【発明が解決しようとする課題】
【0017】
この配置の欠点は、1つまたは複数の向きのフィーチャ専用のスペースを設ける必要があることと、これらのフィーチャに損傷が存在しても回転方向の向きを求めることができるように、このようなフィーチャに冗長性を含めることが難しいことである。したがって、スペースがより効率的に使用され、誤り検出および/または誤り訂正が可能なように、向きの情報を符号化することが望ましい。
【課題を解決するための手段】
【0018】
本発明の第1態様によれば、あるレイアウトに従って基板上または基板内に配設された機械可読の符号化データが開示される。このレイアウトは、少なくともn次の回転対称性を有する。ただし、nは少なくとも2である。このレイアウトにより、n個のシンボルが整数m回繰り返されるシーケンスを含む向きの符号語が符号化される。ただし、mは、1またはそれ以上である。符号化されたシンボルはそれぞれ、このレイアウトの回転対称中心の周りでn個の位置に分配されて、このレイアウトのn個の向きのそれぞれにおいてこれらのシンボルを復号することにより、向きの符号語のn個の表現が生成される。各表現は、向きの符号語の異なる巡回シフトを含み、このレイアウトの回転の程度を示す。この向きの符号語は、誤り許容型である。
【0019】
好ましくは、向きの符号語は、向きの符号語の各表現を、向きの符号語のシンボルの1つが破損していても正確に復号し得るのに十分に誤りを許容するものである。
【0020】
好ましくは、向きの符号語は、向きの符号語の各表現を、向きの符号語のシンボルの2つ以上が破損していても正確に復号し得るのに十分に誤りを許容するものである。
【0021】
好ましくは、レイアウトは、レイアウト領域内の基板上で繰り返される。
【0022】
好ましくは、このレイアウト領域は、2つ以上のレイアウトのタイプからなる複数のレイアウトを含み、各レイアウトは、そのレイアウトのタイプを符号化する。
【0023】
好ましくは、機械可読の符号化データは、分配された符号語を符号化する。この分配された符号語の断片は、この分配された符号語が、異なるタイプの複数の隣接するレイアウトに配置された断片から再構築され得る所定のやり方で、2つ以上のレイアウトのタイプの間に分配される。より好ましくは、レイアウトのタイプの数は、2、3、4、および6の1つである。
【0024】
好ましくは、このレイアウトは、局所符号語を符号化する。この局所符号語の断片は、この局所符号語がこれらの断片から再構築され得る所定のやり方でレイアウト内に分配される。
【0025】
一形態では、これらのレイアウトは、基板上で合わせて束ねられる。
【0026】
好ましくは、このレイアウトは、直線、正方形、長方形、三角形、または六角形のいずれかの形状とする。
【0027】
好ましくは、nは、2、3、4、および6の1つである。
【0028】
好ましくは、機械可読の符号化データは、この符号化データを読み取るのに使用する機械によって、レイアウトの暫定位置および回転を求めることができる1つまたは複数のターゲットフィーチャを含む。
【0029】
好ましくは、これらのターゲットフィーチャは、機械によって読み取られた後で、このレイアウトの、または各レイアウトの符号化データを遠近補正し得るように構成される。より好ましくは、この機械可読の符号化データは、少なくとも4つのターゲットフィーチャを含む。
【0030】
好ましくは、機械可読の符号化データは複数のレイアウトを含む。ターゲットフィーチャの少なくとも一部は、これらのレイアウトの少なくとも2つによって共有される。
【0031】
好ましくは、符号化データは、基板上に印刷される。
【0032】
好ましくは、符号化データは、人間の平均的な裸眼に対して可視性が低い、または不可視のインクで表面上に印刷される。より好ましくは、このインクは、人間の平均的な裸眼には実質的に不可視である赤外インクである。
【0033】
好ましくは、各レイアウトの符号化データにより、ユーザのデータが定義される。
【0034】
好ましくは、このユーザのデータは、表面のある領域に対する相対的なレイアウトパターンの位置を示す位置データを含む。
【0035】
好ましくは、このユーザのデータは、レイアウトが配設される表面のある領域を識別する識別データを含む。
【0036】
好ましくは、このユーザのデータは、機械がレイアウトのパターンまたはサブパターンを読み取った後で実施される関数を識別する関数データを含む。
【0037】
本発明の第2態様によれば、上記段落で開示した機械可読の符号化データを担持する表面が開示される。
【0038】
好ましくは、この表面は、平面または曲面である。
【0039】
好ましくは、この表面はさらに、目に見える標識を含む。より好ましくは、この目に見える標識は、文字列、図形、画像、フォーム、フィールド、およびボタンのいずれか1つまたは複数を含む。
【0040】
好ましくは、この目に見える標識は、符号化データの少なくとも一部に隣接して、あるいはそれと同じ場所に配設される。
【0041】
好ましくは、この表面は、基板によって画定されるものである。より好ましくは、この基板は、紙、カード、または別の薄層媒体である。
【0042】
好ましくは、この表面は、使用者とコンピュータの対話を可能にするインターフェース表面として使用されるように構成される。
【0043】
本発明の第3態様によれば、インターフェース表面を生成する方法が開示される。この方法は、
プリンタでユーザのデータを受け取るステップと、
上記段落で開示した、このユーザデータを組み込んだ機械可読の符号化データを生成するステップと、
この符号化データを基板上に印刷するステップとを含む。
【0044】
好ましくは、この方法はさらに、この基板上に目に見える標識を印刷するステップを含む。
【0045】
好ましくは、これら符号化データおよび目に見える標識は、実質的に同時に基板上に印刷される。
【0046】
本発明の第4態様によれば、感知装置を使用して、上記段落で開示した機械可読の符号化データを読み取る方法が開示される。この方法は、
(a)感知装置を使用して、レイアウトの符号化データを読み取るステップと、
(b)このレイアウトの符号化データを復号して、少なくとも向きの符号語の表現を求めるステップと、
(c)この向きの符号語の表現を用いて、レイアウトの回転の程度を求めるステップとを含む。
【0047】
好ましくは、ステップ(a)は、
基板を画像化して、基板の画像を生成するサブステップと、
この画像を処理して、符号化データの1つまたは複数のターゲットフィーチャを位置決定するサブステップと、
これら位置決定されたターゲットフィーチャに基づいて、向きの符号語の符号化されたシンボルの少なくとも1つの位置を求めるサブステップとを含む。
【発明を実施するための最良の形態】
【0048】
次に、単なる非限定的な例として、添付の図面を参照して本発明の好ましい実施形態および他の実施形態を説明する。
【0049】
本明細書では、(参照により内容を本明細書に組み込む、本出願人の同時係属PCT出願公開WO 01/22207号(Method and System for Instruction of a Computer)に開示されている)ネットページ(netpage)システムが使用する表面符号化を定義して、(参照により内容を本明細書に組み込む、本出願人の同時係属PCT出願公開WO 00/72230号(Sensing Device)に開示されている)ネットページペンなどのネットページ感知装置、および(参照により内容を本明細書に組み込む、本出願人の同時係属PCT出願公開WO 01/41046号(Viewer with Code Sensor)に開示されている)ネットページビューワと組み合わせて、普通なら受動的な表面に双方向性を付与する。
【0050】
ネットページの符号化表面と相互作用すると、ネットページ感知装置は、この感知装置が相対的に移動する表面領域の識別情報およびこの領域内での感知装置の絶対経路をともに示すデジタルインクストリームを生成する。
【0051】
1.表面符号化
ネットページの表面符号化は、タグを密にかつ平らにタイル状に並べることからなる。各タグは、この面内でそれ自体の位置を符号化する。各タグは、隣接するタグとあいまってこのタグを含む領域の識別子も符号化する。ネットページシステムでは、この領域は一般に、1枚の紙の片面など、タグ化された表面の範囲全体に相当する。
【0052】
各タグは、2種類の要素を含むパターンによって表される。第1の種類の要素は、ターゲットである。ターゲットにより、符号化された表面の画像内でタグを位置決定することができ、このタグの遠近歪みを推測することができる。第2の種類の要素は、マクロドットである。各マクロドットは、それが存在するか否かで、ビット値を符号化する。
【0053】
このパターンは、光学式画像システム、特に、近赤外域で狭帯域応答する光学システムによってこのパターンを取得し得るように、符号化された表面上で表現される。このパターンは典型的には、狭帯域赤外インクを使用してこの表面上に印刷される。
【0054】
1.1 タグ構造
図1に、完全なタグ700の構造を示す。6つの黒丸702はそれぞれ、ターゲットである。このタグおよび全体的パターンは、物理的なレベルで6方向に対称である。
【0055】
ダイヤモンド形状の領域704はそれぞれシンボルを表し、各シンボルは4ビットの情報を表す。
【0056】
図2に、シンボルの構造を示す。この構造は、4つのマクロドット706を含む。各マクロドットは、それが存在するか否かによって、1ビットの値を表し、存在する場合には1、存在しない場合には0である。
【0057】
本明細書を通じて、マクロドットの間隔は、パラメータsによって指定される。この間隔の公称値は、1インチ当たり1600ドットのピッチで印刷した9個のドットに基づき、143μmである。ただし、この間隔は、パターンを生成するのに使用する装置の能力に従って、規定範囲内で変化し得る。
【0058】
一般に、本明細書で指定した「理想的な」パターンから、例えば装置の制限のために逸脱したパターンで表面が符号化される場合、この偏差は、この表面を介して取得されたデジタルインクが、この偏差について適切に補正され得るように記録されなければならない。
【0059】
図3に、5つの隣接したシンボルのアレイを示す。マクロドットの間隔は、シンボル内およびシンボル間でともに均一である。
【0060】
図4に、シンボル内でのビットの順序付けを示す。シンボル内で、ビット0は最下位ビットであり、ビット3は最上位ビットである。この順序付けは、シンボルの向きに対して相対的なものであることに留意されたい。タグ内の個々のシンボルの向きは、タグの図(例えば、図1参照)で、シンボルの標示の向きによって示す。一般に、タグの個々のセグメント内のすべてのシンボルの向きは同じであり、タグの中心に最も近い基部のシンボルに一致する。
【0061】
好ましい実施形態では、マクロドットだけが、パターン中のシンボルの表現の部分である。本明細書では、シンボルのダイヤモンド形状の輪郭は、タグの構造をより明瞭にするために用いる。例として、図5に、タグの実際のパターンを、すべてのビットの組とともに示す。好ましい実施形態では、実際には、タグのビットをすべて設定することはできないことに留意されたい。
【0062】
公称上、マクロドットは、公称直径が(5/9)sの円形である。ただし、この直径は、パターンを生成するのに使用する装置の能力に従って、規定範囲内で変化し得る。
【0063】
公称上、ターゲットは、公称直径が(17/9)sの円形である。ただし、この直径は、パターンを生成するのに使用する装置の能力に従って、規定範囲内で変化し得る。
【0064】
図1のタグ構造で示す各シンボルは、一意の標示を有する。各標示は、英字の接頭辞および数字の接尾辞からなる。
【0065】
1.2 誤りの検出および訂正
符号化するデータが、ガロア体GF(q)から得られたq元シンボルを有するkシンボルブロックに分割されると仮定する。すべての可能なk個の要素からなる集合m=(m0,m1,...,mk−1)は、GF(q)上でベクトル空間を形成し、qk個の可能なベクトルを含む。長さがnの、対応するブロック訂正符号Cは、1組のM個のnシンボル符号語{c0,c1,...,cM−1}からなる。ただし、M=qk、n>kであり、各符号語の形式は、c=(c0,c1,...,cn−1)である。あるデータブロックを符号化する場合、符号器は、このデータブロックをCの符号語上にマッピングする。GF(q)上のすべての可能なn個の要素からなる集合は、qn個のベクトルを含むが、符号語はM=qk個しかないので、この符号は冗長性を有する。この冗長性は、r=n−logqM=n−kによって対数的に、または符号化率R=k/nによって表される。符号Cは、それがGF(q)上でベクトル副空間を形成する場合、すなわち、スカラーとの加算および乗算において閉じている(そのため、ゼロベクトルを含む)場合には、線形符号である。この場合、この符号は、次元kを有するといい、(n,k)符号と称する。
【0066】
2つの符号語のハミング距離は、これら2つの符号語で値が異なるシンボルの数である。ブロック符号の最小距離dminは、この符号中の任意の別個の符号語対の最小ハミング距離である。最大距離dmaxは、この符号中の任意の別個の符号語対の最大ハミング距離である。
【0067】
誤りパターンにより、符号語にシンボル誤りが導入される。この誤りパターンは、その重み、すなわちこの誤りパターンが破損するシンボルの数によって特徴づけられる。誤りパターンが検出不可能な場合、この誤りパターンにより、ある符号語が別の符号語と同じに見えるはずである。そのため、最小距離がdminの符号は、重みがdmin−1以下のすべての誤りパターンを検出し得る。所与の符号は、重みが大きいほど多くの誤りパターンを検出し得るが、上記のことから、符号がすべての誤りパターンを検出し得る重みを制限する。
【0068】
サンプリングされた語が誤りパターンによって破損した可能性がある場合、復号器はこのサンプリングされた語を、Cの符号語上に、この符号語が、最初に書き込まれた符号語と異なる確率を最小限に抑えるようにマッピングし、次いで、この符号語をデータブロック上にマッピングする。より具体的な特徴付けが存在しない場合には、重みが小さい誤りパターンのほうが、重みが大きい誤りパターンよりも可能性が高く、重みが等しい誤りパターンはすべて、可能性が等しいと仮定する。そのため、最大尤度で書き込まれた符号語は、サンプリングされた語にハミング距離が最も近い符号語になる。サンプリングされた語が、正しい(書き込まれた)符号語よりも、誤った符号語に近い場合、復号器は誤りを犯したことになる。定義により符号語は、少なくとも距離dminは離れているので、復号器の誤りは、誤りパターンの重みが、dmin/2以上の場合にのみ起こり得る。そのため、最大尤度復号器は、重みが[(dmin−1)/2]以下のすべての誤りパターンを訂正し得る。同等に、この復号器は、2t<dminである限り、t個の誤りを訂正し得る。
【0069】
線形符号の最小距離は、シングルトン(Singleton)の限界式dmin≦n−k+1によって制限される。このシングルトンの限界式を等号で満足する符号を、MDS(最大距離分離可能)と呼ぶ。リードソロモン符号(Wicker,S.B.、V.K.Bhargava監修、Reed−Solomon Codes and Their Applications、IEEE Press、1994年を参照されたい。この内容を参照により本明細書に組み込む)は、最も一般に用いられるMDS符号である。2進符号はMDSではない。
【0070】
消失は、破損したとみなされるサンプリング語のシンボルである。符号語中で消失位置は既知なので、消失は、誤りとして処理するのではなく、復号を行うために無視することができる。例えば、サンプリングされた語の中の消失シンボルと、それに対応する符号語中のシンボルとの距離は、最大尤度復号法の基礎として用いるハミング距離には含まれない。そのため、1つの消失ごとに、最小距離は事実上1だけ短くなる。すなわち、消失がf個存在すると、最大で[(dmin−f−1)/2]個の誤りを訂正することができる。同等に、この復号器は、2t+f<dminである限り、t個の誤りおよびf個の消失を訂正し得る。MDS符号では、これは、2t+f<n−k+1になる。
【0071】
符号が組織的であるのは、その符号語がそれぞれ、それに対応するデータブロックを、改変されずに固定位置で含む場合である。この場合、この符号のデータ(またはメッセージ)座標と、この符号の冗長性(またはパリティ)座標を区別することが可能である。
【0072】
線形符号化率は、この符号のパンクチャによって、すなわち、その冗長性座標の1つまたは複数を消去することによって増加させることができる。g個の座標を消去することによって、(n,k)符号は、(n−g,k)符号に変換される。パンクチャされた符号の最小距離は、dmin−gになる。明らかに、dmin−g<2の場合、パンクチャにより、この符号は1つの誤りさえ訂正し得なくなり、dmin−g<1の場合、パンクチャにより、この符号は1つの誤りさえ検出し得なくなる。同等に、パンクチャされた符号の長さw=n−gは、誤りを検出するためにはw≧n−dmin+1に従わなければならず、誤りを訂正するためにはw≧n−dmin+2に従わなければならない。パンクチャされた符号に対して復号器は単に、消去された座標を、元の符号に関する消失として処理することができる。
【0073】
ブロック符号Cが巡回符号になるのは、符号語c=(c0,c1,..,cn−2,cn−1)がCに含まれ、且つ、cの右巡回シフトである符号語c’=(cn−1,c0,c1,...,cn−2)がCに含まれる場合である。その結果、cのn個の巡回シフトもすべて、Cで符号語になる。符号語の数qkが、符号の長さnよりも大きい場合、この符号は、複数の別個の巡回を含み、各巡回iはsi個の固有の符号語を含む。ただし、nはsiで割り切れる。この符号がゼロベクトルを含む場合、このゼロベクトルはそれ自体の巡回を形成する。
【0074】
1.3 向きを示す巡回位置符号
タグは、(参照により内容を本明細書に組み込む、本出願人の同時係属PCT出願公開WO 02/084473号(Cyclic Position Codes)に開示されている)24元(6,1)巡回位置符号語を含む。この巡回位置符号語を、このタグの6つの可能な向きのいずれかで復号して、このタグの実際の向きを求めることができる。この巡回位置符号語の一部であるシンボルは、「R」の接頭辞を有し、下位から上位に向かう順に0〜5に番号が付けられる。
【0075】
この巡回位置符号語は、(0,5,6,9,A16,F16)である。この巡回位置符号語は、4ビットシンボルが16個の可能な値を有するにもかかわらず、6つの別個のシンボル値しか用いないことに留意されたい。復号中に検出される未使用シンボル値はいずれも、消失として処理される。符号語中の実際のシンボルの順序も、実際に使用するシンボル値のサブセットの構成も重要ではないことに留意されたい。ただし、シンボル間最小距離を最大にするサブセットを選択することが有利である。というのは、こうすると、ビット誤りが、シンボル誤りよりも消失を引き起こす可能性が高くなるようにする助けになるからである。これが有利なのは、(以下で論じるように)符号の消失訂正能力が、符号の誤り訂正能力のほぼ2倍だからである。
【0076】
図6に、向きを示す巡回位置符号語のレイアウトを示す。図では、この符号語に陰影を付けて示す。
【0077】
巡回位置符号語の最小距離は6であり、したがって、巡回位置符号語は、消失が最大で1つの場合、2つのシンボルの誤りを訂正することができ、2つまたは3つの消失がある場合には、1つのシンボルの誤りを訂正することができ、消失が4つ以上あると、シンボルの誤りを訂正することができない。
【0078】
表1に、巡回位置符号の第1符号語と、この符号の各符号語とのハミング距離を示す。このハミング距離は、単一のシンボル誤りが、符号語中の6つの可能な位置のそれぞれに順にある状態で計算したものである。破損したシンボルは、いずれの場合も◆で示す。最悪の場合を想定して、このシンボルは他の各符号語の対応するシンボルにまで破損したと仮定する。破損した符号語とその破損していない元の符号語の距離は、いずれの場合にも1であり、破損した符号語と他の各符号語の距離は、いずれの場合にも5である。どの符号語も第1符号語のなんらかの巡回シフトであるので、この表は、この符号が、任意の符号語中の任意の単一のシンボル誤りを訂正し得ることを示している。
【0079】
その延長で、任意の2つのシンボル誤りが存在する場合、破損した符号語とその破損していない元の符号語の距離は、いずれの場合にも2に増加し、破損した符号語と他の各符号語の距離は、いずれの場合にも4に減少することがわかる。したがって、この表は、この符号が、任意の符号語中の任意の2つのシンボル誤りを訂正し得ることを示している。これを表2に示す。
【表1】
【表2】
【0080】
1つまたは複数の消失が存在する場合に、単に消失した1つ(または複数)の座標を無視することによって同じ距離計算を実施し得る。これを表3に示す。表3では、1つの消失を−で示す。
【表3】
【0081】
サンプリングした巡回位置符号語を復号することは、消失を検出することと、次いで、残りの(消失していない)シンボルと、それに対応する、元の巡回位置符号語の6つの巡回シフト中のシンボルとの距離を計算することからなる。その後、このサンプリングした符号語を、このサンプリングした符号語から距離が最も近いシフトした符号語として復号する。サンプリングした符号語に同じ距離で最も近いシフトした符号語が2つ以上ある場合には、復号することはできない。サンプリングした符号語をシフトした符号語に復号すると、この符号語のシフトは既知なので、サンプリングの向きに対するタグの回転がわかる。
【0082】
巡回位置符号語を形成する6つのシンボルに加えて、隣接するタグの巡回位置符号語の少なくとも6つの追加のシンボルも視野内に見える。これら余分なシンボルを追加して復号する手間をかければ、12個のシンボルを使用して巡回位置符号語を復号することができる。これは2つの方法で実施し得る。第1の手法では、消失したシンボルをどれも、単にそれに対応する、他のタグの巡回位置符号語の1つからのシンボルで置き換える。ただし、これは、この対応するシンボル自体が消失していない場合である。第2の手法では、12個のシンボルすべてを、12シンボル符号語として処理する。
【0083】
この巡回位置符号を用いて、このタグが鏡面反射で、例えば、このタグが、このタグを配設した透明な基板の裏面によって写像されて取得されたかどうかを検出することもできる。
【0084】
1.4 局所符号語
このタグは、このタグに固有な情報を符号化するのに使用する3つの完全な符号語を局所的に含む。各符号語は、パンクチャされた24元(9,5)リードソロモン符号のものである。したがって、このタグは、このタグに固有な情報を60ビットまで符号化する。
【0085】
図7に、これら3つの局所符号語のレイアウトを示す。図7では、符号語Aに陰影を付けて示す。
【0086】
1.5 分配した符号語
このタグは、3つの隣接するタグ全体にわたって分配され、かつ、1組の連続したタグに共通する情報を符号化するのに用いる3つの符号語の断片も含む。各符号語は、パンクチャされた24元(9,5)リードソロモン符号のものである。したがって、3つの隣接するタグはどれもともに、1組の連続したタグに共通する情報を60ビットまで符号化する。
【0087】
図8に、これら3つの符号語の断片のレイアウトを示す。
【0088】
図9に、これら3つの完全な符号語のレイアウトを、3つの隣接するタグ全体にわたって分配した状態で示す。これら分配した符号語に関して、タグのタイプは3つある。これらを、下位から上位に向かう順にP、Q、およびRと称する。
【0089】
図10に、これらP、Q、およびRのタグがどのように、連続してタイル状に並べられたタグの形で繰り返されるかを示す。このようにタイル状に並べることによって、3つの隣接するタグの組がどれも、各タイプのタグを1つ含み、したがって、1組の完全な分配した符号語を確実に含むようにする。隣接するタグの個々の組に対する、分配した符号語の位置合わせを決定するために用いるタグのタイプは、各タグの局所符号語の1つの形で符号化される。
【0090】
図11に、3つの隣接するタグの完全な構造を、これらのタグの向きの巡回位置符号語、局所符号語、および分配した符号語を含めて示す。
【0091】
図12に、タグのセグメント708の幾何形状を示す。
【0092】
図13に、マクロドットの間隔を同一に維持するために必要とされるタグのセグメントの間隔d=(1−30.5/2)sを示す。30.5は、3の0.5乗、即ち、3の正の平方根を意味する。
【0093】
図14に、ターゲット位置に対するセグメント間隔dの影響を示す。緊密に(すなわち、d=0で)充填されたセグメントに関するターゲット位置の公称位置と比較して、対角ターゲットは(Δx,Δy)=(±1/30.5,±1)dだけ変位させなければならず、水平ターゲットは(Δx,Δy)=(±2/30.5,0)dだけ変位させなければならない。
【0094】
1.6 リードソロモン符号化
【0095】
局所符号語および分配した符号語はともに、パンクチャされた24元(9,5)リードソロモン符号を用いて符号化される。
【0096】
24元(9,5)リードソロモン符号は、各符号語において、20個のデータビット(すなわち、5つの4ビットシンボル)および16個の冗長ビット(すなわち、4つの4ビットシンボル)を符号化する。このリードソロモン符号は、4つのシンボルの誤りを検出することができ、2つのシンボルの誤りを訂正することができる。
【0097】
パンクチャされた24元(9,5)リードソロモン符号は、6つの冗長座標を取り除いた24元(15,5)リードソロモン符号である。
【0098】
この符号は、以下の原始多項式を有する。
【0099】
p(x)=x4+x+1
【0100】
この符号は、以下の生成多項式を有する。
【0101】
g(x)=(x+α)×(x+α2)×...×(x+α10)
【0102】
リードソロモン符号の詳細な説明については、Wicker,S.B.、V.K.Bhargava監修、Reed−Solomon Codes and Their Applications、IEEE Press、1994年を参照されたい。
【0103】
2.タグ座標空間
タグ座標空間710は、1対の半直交座標aおよびbによって定義する。図15に、このタグ座標空間と表面x−y座標空間の公称上の関係を示す。
【0104】
この座標は、(以下の「符号化および印刷の考察」という見出しの節で論じるように)意図する印刷装置によるタグパターンの再現性が確保されるためには必然的に半直交にしかならない。
【0105】
意図する印刷装置のさらなる助けとするために、表面符号化、したがって、a−b座標空間を、x−y座標空間に対して90度の任意の倍数だけ回転することができる。
【0106】
x−y座標空間に対してa−b座標空間を反時計回りにRだけ回転させると、これら2つの座標空間の関係は、以下のようになる。
x=acos(30°−R)−bsin(60°−R) (式1)
y=asin(30°−R)+bcos(60°−R) (式2)
【数1】
【数2】
【0107】
図16に示すように、整数aおよびbの座標は、タグPの中心で交わるように定義する。この図では、整数aおよびbの座標の等値線をそれぞれ表す線714と712を示す。
【0108】
表面符号化では、個々のタグ化した表面上でのx−y(またはa−b)の原点位置、あるいは、この表面に対するx−y(またはa−b)座標空間の向きを指定しないことに留意されたい。表面符号化では、これら2つの座標空間の関係しか定義しない。この関係は、ネットページのタグ化した表面と相互作用させるのに使用するネットページ感知装置によって生成されるデジタルインクに埋め込まれたx−y座標に現れる。
【0109】
3.タグ情報の内容
表4では、表面符号化の際に埋め込まれる情報フィールドを定義する。表5では、これらのフィールドを、局所符号語および分配された符号語にマッピングする方法を定義する。
【表4】
【0110】
図17に、タグおよびその6つの最近接タグを示す。これらのタグはそれぞれ、活動区域マップおよび入力区域マップにおいてこれらタグに対応するビット指標で標示する。
【0111】
領域IDの上位55ビットは、分配した符号語の形で符号化されるので、それらは、連続してタイル状に並べられたタグ全体について必ず一定である。ただし、下位41ビットは、局所符号語の形で符号化され、そのため、タグ間で任意に変化し得る。
【0112】
個々の表面符号化に対して、aおよびbの座標に専用のビット数は、座標精度フィールドを介して構成可能である。このようにして、タグ化される表面のサイズに合わせて精度を調整することができ、それによって、より精度の高い領域ID空間を効率的に使用し得る。領域IDは、全精度95ビット空間から割り当てることができるが、個々の座標精度wについての制約により、割り当てられた各領域IDの下位2wビットはゼロにならなければならない。ほぼ同等に、精度に固有のプールから、異なる精度の領域IDを割り当てることができ、割り当てられた各領域IDに指標を付け、プールに固有の方法で参照し得る。
【表5】
【0113】
活動区域マップは、対応するタグが活動区域のメンバであるかどうかを示す。活動区域は、そこで取得された入力はいずれも直ちに、解釈を行うために対応するネットページサーバに転送すべき区域である。この活動区域により、ネットページ感知装置は、この入力が直ちに実施されることを使用者に知らせることもできる。
【0114】
入力区域マップは、対応するタグが入力区域のメンバであるかどうか、すなわち、ある形式の範囲に存在するかどうかを示す。この入力区域により、ネットページ感知装置は、この入力がアプリケーションに提示されることを使用者に知らせることができる。
【0115】
4.符号化および印刷の考察
(参照によりともに内容を本明細書に組み込む、本出願人の同時係属PCT出願公開WO 01/89851号(Print Engine/Controller and Printhead Interface Chip Incorporating the Print Engine/Controller)およびWO 01/89838号(Printed Page Tag Encoder)に開示されている)PEC(印刷エンジンコントローラ)は、(1ページ当たり)2つの固定された24元(15,5)リードソロモン符号語および(1つのタグ当たり)6つの可変の24元(15,5)リードソロモン符号語の符号化に対応する。さらに、PECは、矩形ユニットセルによるタグの解釈に対応する。この矩形ユニットセルのレイアウトは(1ページ当たり)一定であるが、その可変符号語データは、ユニットセル間で変化し得る。PECでは、ページの移動方向にユニットセルが重なり合うことができない。
【0116】
図18に、この表面符号化に適合するPECユニットセル718の好ましい実施形態を、タイル状に並べたタグに重ね合わせて示す。図19に、ここで提案するPECユニットセルを、実際のP、Q、およびRのタイプのタグ構造に重ね合わせて示す。ここで提案するユニットセルは、Pタイプのタグを中心にして水平に置かれていることに留意されたい。このタグ構造およびユニットセルは、ユニットセルが正確に、6つの可変符号語(すなわち、列nについて、Rn:A、Pn:A、Qn:A、{R,P,Q}n:B、{R,P,Q}n:C、および{R,P,Q}n+1:B)、ならびに3つの固定された符号語D、E、およびFを含むように設計される。
【0117】
符号語D、E、およびFの少なくとも1つは、PECに渡されるTFS(タグフォーマット構造)の形であらかじめ符号化しなければならない。というのは、PECは、2つの固定された符号語の符号化にしか対応しないからである。符号語D、E、およびFのいずれか、または全部をTFSの形であらかじめ符号化することができるはずである。
【0118】
PECは、1つのTFSの列当たりの固有ビットアドレスを32個に制限する。D、E、およびFの符号語があらかじめ符号化されていると仮定すると、ユニットセルの内容は、この制限に沿ったものになる。
【0119】
PECは、TFSの幅も384に制限する。ユニットセルの内容は、この制限に沿ったものにする。
【0120】
ページサイズが適度な場合、BおよびCの符号語中の可変座標ビット数を控えめにして、ルックアップテーブルによる符号化を扱いやすくすることに留意されたい。ルックアップテーブルによる符号語Aの符号化も可能とし得る。リードソロモン符号は組織符号なので、ルックアップテーブルに表示されるのは冗長データだけでよいことに留意されたい。
【0121】
5.画像化および復号の考察
図20に、タグ全体を確実に取得するために必要とされる、すなわち、表面符号化と視野の位置合わせが任意である場合の好ましい最小画像化視野720を示す。最小限の視野の直径は36sである。
【0122】
タグ構造をこのように仮定すると、対応する復号シーケンスは以下のとおりである。
・ 完全なタグのターゲットを位置決定する
・ ターゲットから遠近変換を推測する
・ 巡回位置符号をサンプリングする
・ 巡回位置符号を復号する
・ 巡回位置符号から向きを求める
・ 局所リードソロモン符号語をサンプリングする
・ 局所リードソロモン符号語を復号する
・ タグのタイプを求める
・ タグの回転を求める
・ 分配されたリードソロモン符号語をサンプリングする(タグのタイプを参照して、ウィンドウを法として位置合わせする)
・ 分配されたリードソロモン符号語を復号する
・ 座標の精度を求める
・ 領域IDを求める
・ タグのa−bの位置を求める
・ タグの回転を参照して、タグのa−b位置をx−y位置に変換する
・ 方向づけられたターゲットから3D変換を推測する
・ タグのx−y位置および3D変換からペン先のx−y位置を求める
・ ペン先の位置の活動区域/入力区域のステータスを求める
・ ペン先の活動区域/入力区域のステータスに基づいて、ローカルフィードバックを生成する
・ デジタルインクの形で、領域ID、ペン先のx−y位置、ペン先の活動区域/入力区域のステータスを符号化する
【0123】
図21に、タグの画像処理および復号プロセスの流れを示す。(800で)タグパターンの生画像802を、例えば、CCD画像センサ、CMOS画像センサ、またはレーザ走査型フォトダイオード画像センサなどの画像センサによって取得する。次いで、典型的には(804で)この生画像を強調して、コントラストが改善され、かつ画素の強度がより均一になった強調画像806を生成する。画像強調は、グローバルな、またはローカルな範囲の伸張、均等化などを含み得る。次いで、典型的には(808で)強調画像806をフィルタリングして、フィルタリングされた画像810を生成する。画像のフィルタリングは、ローパスフィルタリングからなり得る。ローパスフィルタ用のカーネルサイズは、マクロドットは不明瞭になるが、ターゲットは保存されるように調整する。フィルタリングステップ808は、ターゲットフィーチャを強調するために、(エッジ検出などの)追加のフィルタリングを含み得る。次いで、(812で)フィルタリングされた画像810を処理してターゲットフィーチャを位置決定し、それによって1組のターゲットポイントが得られる。これは、空間相互関係がタグの既知の幾何形状と一致するターゲットフィーチャを探索することからなり得る。ターゲット候補は、フィルタリングされた画像810の最大値から直接識別することもできるし、あるいは、米国特許出願第09/575154号に記載されているように、(典型的には、フィルタリングされた画像810中の極大値に基づいて、強調画像806の画素から計算する)ターゲットの(2値またはグレースケールの)形状モーメントなどによって、別の特徴付けおよびマッチングの対象とすることもできる。この探索は典型的には、視野の中心から開始する。探索ステップ812によって見つけられたターゲットポイント814から、画像センサおよびその関連する光学系が占める3次元空間におけるタグの位置が間接的に明らかになる。ターゲットポイント814は、(2値またはグレースケールの)ターゲットの重心から導出されるので、これらは一般に、画素未満の精度で定義される。
【0124】
(816で)タグの実際の3D変換、その延長で、タグに対する相対的な感知装置の3D変換(または姿勢)818を求めることが有用である。これは、米国特許出願第09/575154号に記載されているように解析的に、あるいは、(参照により内容を本明細書に組み込む、P.R.Wolf、B.A.Dewitt、Elements of Photogrammetry with Applications in GIS、3rd Edition、McGraw Hill、2000年2月に記載されているように)遠近歪みのあるターゲットポイントが観測された場合、最大尤度推定量(最小自乗法による調整など)を用いてパラメータ値を3D変換に合わせることによって実施し得る。3D変換は、タグの3D並進移動、タグの3D方向づけ(回転)、ならびに感知装置の焦点距離および表示域尺度を含み、そのため、適合すべき8つのパラメータ、あるいは、(例えば、設計によって、または較正ステップから)焦点距離および表示域尺度が既知の場合には、6つのパラメータが与えられる。各ターゲットポイントから、観測された座標を既知の座標に関係づける1対の観測方程式が得られる。8つのパラメータを適合させる場合、最大尤度推定を可能にするのに十分な冗長性を提供するために、5つ以上のターゲットポイントが必要とされる。6つのパラメータを適合させる場合には、4つ以上のターゲットポイントが必要とされる。タグの設計が、最大尤度推定を可能にするのに最低限必要とされるよりも多くのターゲットを含む場合、最大で、最低限必要とされるターゲットが認識できないほど損傷している場合でも、タグを認識し、復号することができる。
【0125】
マクロドットの値を正確にサンプリングし得るように、タグの遠近変換を推測しなければならない。ターゲットポイントのうち4つを取り出して、タグ空間内で既知のサイズの矩形の遠近歪みをもつコーナとし、タグ空間と像空間の4つのポイント対を関係づける周知の方程式を解くことに基づいて(参照により内容を本明細書に組み込む、Heckbert,P.、Fundamentals of Texture Mapping and Image Warping、修士論文、Dept.of EECS、カリフォルニア大学バークレー校、Technical Report UCB/CSD 89/516号、1989年6月参照)、(820で)8自由度の遠近変換822を推測する。あるいは、この遠近変換は、3D変換818が利用可能な場合には、それから導出することができる。
【0126】
タグ空間から像空間への推測された遠近変換822を用いて、(824で)向きを示す巡回位置符号語の各データビットの既知の位置を、タグ空間から像空間に投影し、そこで、実数値位置を用いて、(824で)4つ(またはそれ以上)の該当する隣接画素を強調入力画像806内で双一次(または高次)内挿する。得られたマクロドットの値と適切な閾値を比較して、それが0ビットまたは1ビットを表すかどうかを判定する。サンプリングを行うために、向きを示す巡回位置符号語の空間レイアウトを固定し、向きに関して不変にする。
【0127】
完全な向きを示す巡回位置符号語のビットがサンプリングされた後で、(830で)前に説明したように向きを示す符号語を復号して、サンプリングの向きに対するタグの向き832が得られる。
【0128】
タグ空間から像空間への推測された遠近変換822を用いて、(834で)局所符号語および分配された符号語の各データビットの既知の位置を、タグ空間から像空間に投影し、そこで、実数値位置を用いて、(834で)4つ(またはそれ以上)の該当する隣接画素を強調入力画像806内で双一次(または高次)内挿する。得られたマクロドットの値と適切な閾値を比較して、それが0ビットまたは1ビットを表すかどうかを判定する。サンプリングを行うために、局所符号語および分配された符号語の空間レイアウトを固定するが、向きに関しては不変にする。したがって、レイアウトの実際の向きを求めるには、向き832を用いる。
【0129】
1つまたは複数の完全な符号語のビットがサンプリングされた後で、(838で)これらの符号語を復号して、タグ内で符号化された所望のデータ840が得られる。符号語の冗長性を利用して、サンプリングされたデータ中の誤りを検出するか、あるいは、サンプリングされたデータ中の誤りを訂正することができる。
【0130】
米国特許出願第09/575154号で論じているように、得られたタグデータ840により、直接または間接に、タグを含む表面領域およびこの領域内のタグの位置を識別し得る。したがって、この表面領域に対する相対的な感知装置の正確な位置は、タグデータ840およびタグに対する感知装置の3D変換818から導出し得る。
【0131】
結論
いくつかの特定の実施例を参照して本発明を説明してきたが、当業者なら、他の多くの形態で本発明を実施し得ることが理解されよう。
【図面の簡単な説明】
【0132】
【図1】本発明によるタグ構造の第1実施形態を示す図である。
【図2】図1のタグ構造のシンボルユニットセルを示す図である。
【図3】シンボルユニットセルアレイを示す図である。
【図4】シンボルのビット順序付けを示す概略図である。
【図5】タグパターンをすべてのビットの組とともに示す図である。
【図6】向きを示す巡回位置符号語のレイアウトを示す図である。
【図7】3つの局所符号語のレイアウトを示す図である。
【図8】分配された符号語D、E、およびFの交互に配置された断片を示す図であり、符号語Dの断片に陰影を付けて示す。
【図9】分配された符号語D、E、およびFの完全な組を含む3つの隣接するタグP、Q、およびRを示す図であり、符号語Dの断片に陰影を付けて示す。
【図10】タグP、Q、およびRを連続的にタイル状に並べたところを示す図である。
【図11】3つの隣接するタグの完全な構造を、これらのタグの向きの巡回位置符号語、局所符号語、および分配された符号語を含めて示す図である。
【図12】タグのセグメントの幾何形状を示す図である。
【図13】マクロドット間の間隔を同一に維持するために必要とされる、タグのセグメントの好ましい間隔d=(1−30.5/2)sを示す図である。
【図14】ターゲット位置に対するセグメント間隔dの影響を示す図である。
【図15】タグ座標空間と表面x−y座標空間の公称上の関係を示す図である。
【図16】タイル状に並べられたタグ上に重ね合わされたタグ座標グリッドを示す図である。
【図17】タグおよびその6つの最近接タグを示す図であり、各タグは、活動区域マップおよび入力区域マップ内で、各タグに対応するビット指標で標示されている。
【図18】この表面符号化に適合するPECユニットセルの好ましい実施形態を、タイル状に並べたタグ上に重ね合わせて示す図である。
【図19】実際のP、Q、およびRのタイプのタグ構造に重ね合わせたPECユニットセルの好ましい実施形態を示す図である。
【図20】タグ全体を確実に取得するのに必要とされる好ましい最小画像視野を示す図である。
【図21】タグの画像処理および復号プロセスの流れを示す図である。
【特許請求の範囲】
【請求項1】
あるレイアウトに従って基板上または基板内に配設された機械可読の符号化データであって、
前記レイアウトは、少なくともn次の回転対称性を有し、nは少なくとも2であり、前記レイアウトによって、n個のシンボルが整数m回繰り返されるシーケンスを含んだ向きの符号語が符号化され、mは1またはそれ以上であり、
符号化されたシンボルはそれぞれ、前記レイアウトの回転対称中心の周りでn個の位置に分配され、前記レイアウトのn個の向きのそれぞれにおいて前記シンボルが復号されることにより、前記向きの符号語のn個の表現が生成され、
各表現は、前記向きの符号語の異なる巡回シフトを含みかつ前記レイアウトの回転の程度を示し、当該向きの符号語は誤り許容型である、機械可読の符号化データ。
【請求項2】
前記向きの符号語は、前記向きの符号語の各表現を、前記向きの符号語のシンボルの1つが破損していても正確に復号し得るのに十分に誤りを許容するものである、請求項1に記載の機械可読の符号化データ。
【請求項3】
前記向きの符号語は、前記向きの符号語の各表現を、前記向きの符号語のシンボルの2つ以上が破損していても正確に復号し得るのに十分に誤りを許容するものである、請求項1に記載の機械可読の符号化データ。
【請求項4】
前記レイアウトは、レイアウト領域内の前記基板上で繰り返される、請求項1に記載の機械可読の符号化データ。
【請求項5】
前記レイアウト領域は、2つ以上のレイアウトのタイプからなる複数のレイアウトを含み、各レイアウトは、そのレイアウトのタイプを符号化する、請求項4に記載の機械可読の符号化データ。
【請求項6】
前記機械可読の符号化データは、分配された符号語が符号化されたものであり、前記分配された符号語の断片は、前記分配された符号語が、異なるタイプの複数の隣接するレイアウトに配置された断片から再構築され得る所定のやり方で、2つ以上のレイアウトのタイプの間に分配される、請求項5に記載の機械可読の符号化データ。
【請求項7】
レイアウトのタイプの数は、2、3、4、および6のうち1つである、請求項5に記載の機械可読の符号化データ。
【請求項8】
前記レイアウトは、局所符号語を符号化し、前記局所符号語の断片は、前記局所符号語が前記断片から再構築され得る所定のやり方で前記レイアウト内に分配される、請求項1に記載の機械可読の符号化データ。
【請求項9】
前記レイアウトは、前記基板上で合わせて束ねられる、請求項4に記載の機械可読の符号化データ。
【請求項10】
前記レイアウトは、直線、正方形、長方形、三角形、または六角形のいずれかの形状とする、請求項1に記載の機械可読の符号化データ。
【請求項11】
nは、2、3、4、および6のうち1つである、請求項1に記載の機械可読の符号化データ。
【請求項12】
1つまたは複数のターゲットフィーチャを含み、それによって、前記符号化データを読み取るのに使用する機械が、前記レイアウトの暫定位置および回転を求めることができる、請求項1に記載の機械可読の符号化データ。
【請求項13】
前記ターゲットフィーチャは、前記機械によって読み取られた後で、前記レイアウトの、または各レイアウトの前記符号化データを遠近補正し得るように構成される、請求項12に記載の機械可読の符号化データ。
【請求項14】
少なくとも4つの前記ターゲットフィーチャを含む、請求項13に記載の機械可読の符号化データ。
【請求項15】
複数の前記レイアウトを含み、前記ターゲットフィーチャの少なくとも一部は、前記レイアウトの少なくとも2つによって共有される、請求項12から14のいずれか一項に記載の機械可読の符号化データ。
【請求項16】
前記符号化データは、前記基板上に印刷される、請求項1に記載の機械可読の符号化データ。
【請求項17】
前記符号化データは、人間の平均的な裸眼に対して可視性が低い、または不可視のインクで表面上に印刷される、請求項16に記載の機械可読の符号化データ。
【請求項18】
前記インクは、人間の平均的な裸眼には実質的に不可視である赤外インクである、請求項17に記載の機械可読の符号化データ。
【請求項19】
各レイアウトの前記符号化データは、ユーザのデータを定義する、請求項1に記載の機械可読の符号化データ。
【請求項20】
前記ユーザデータは、前記表面のある領域に対する相対的な前記レイアウトパターンの位置を示す位置データを含む、請求項19に記載の機械可読の符号化データ。
【請求項21】
前記ユーザデータは、前記レイアウトが配設される前記表面のある領域を識別する識別データを含む、請求項19に記載の機械可読の符号化データ。
【請求項22】
前記ユーザデータは、前記機械が前記レイアウトのパターンまたはサブパターンを読み取った後で実施される関数を識別する関数データを含む、請求項19から21のいずれか一項に記載の機械可読の符号化データ。
【請求項23】
請求項1に記載の機械可読の符号化データを担持する表面。
【請求項24】
前記表面は、平面または曲面である、請求項23に記載の表面。
【請求項25】
目に見える標識をさらに含む、請求項23に記載の表面。
【請求項26】
前記目に見える標識は、文字列、図形、画像、フォーム、フィールド、およびボタンのいずれか1つまたは複数を含む、請求項25に記載の表面。
【請求項27】
前記目に見える標識は、前記符号化データの少なくとも一部に隣接して、あるいは前記符号化データの少なくとも一部と同じ場所に配設される、請求項25に記載の表面。
【請求項28】
前記表面は、基板によって画定される、請求項23に記載の表面。
【請求項29】
前記基板は、紙、カード、または別の薄層媒体である、請求項28に記載の表面。
【請求項30】
使用者とコンピュータの対話を可能にするインターフェース表面として使用されるように構成される、請求項23に記載の表面。
【請求項31】
インターフェース表面を生成する方法であって、
プリンタでユーザのデータを受け取るステップと、
請求項19に記載の、前記ユーザデータを組み込んだ機械可読の符号化データを生成するステップと、
前記符号化データを基板上に印刷するステップとを含む、方法。
【請求項32】
前記基板上に目に見える標識を印刷するステップをさらに含む、請求項31に記載の方法。
【請求項33】
前記符号化データおよび目に見える標識は、実質的に同時に前記基板上に印刷される、請求項32に記載の方法。
【請求項34】
感知装置を使用して、請求項1に記載の機械可読の符号化データを読み取る方法であって、
(a)前記感知装置を使用して、前記レイアウトの前記符号化データを読み取るステップと、
(b)前記レイアウトの前記符号化データを復号して、少なくとも前記向きの符号語の前記表現を求めるステップと、
(c)前記向きの符号語の前記表現を用いて、前記レイアウトの回転の程度を求めるステップとを含む、方法。
【請求項35】
ステップ(a)は、
前記基板を画像化して、前記基板の画像を生成するサブステップと、
前記画像を処理して、前記符号化データの1つまたは複数のターゲットフィーチャを位置決定するサブステップと、
前記位置決定されたターゲットフィーチャに基づいて、前記向きの符号語の前記符号化シンボルの少なくとも1つの位置を求めるサブステップとを含む、請求項34に記載の方法。
【請求項1】
あるレイアウトに従って基板上または基板内に配設された機械可読の符号化データであって、
前記レイアウトは、少なくともn次の回転対称性を有し、nは少なくとも2であり、前記レイアウトによって、n個のシンボルが整数m回繰り返されるシーケンスを含んだ向きの符号語が符号化され、mは1またはそれ以上であり、
符号化されたシンボルはそれぞれ、前記レイアウトの回転対称中心の周りでn個の位置に分配され、前記レイアウトのn個の向きのそれぞれにおいて前記シンボルが復号されることにより、前記向きの符号語のn個の表現が生成され、
各表現は、前記向きの符号語の異なる巡回シフトを含みかつ前記レイアウトの回転の程度を示し、当該向きの符号語は誤り許容型である、機械可読の符号化データ。
【請求項2】
前記向きの符号語は、前記向きの符号語の各表現を、前記向きの符号語のシンボルの1つが破損していても正確に復号し得るのに十分に誤りを許容するものである、請求項1に記載の機械可読の符号化データ。
【請求項3】
前記向きの符号語は、前記向きの符号語の各表現を、前記向きの符号語のシンボルの2つ以上が破損していても正確に復号し得るのに十分に誤りを許容するものである、請求項1に記載の機械可読の符号化データ。
【請求項4】
前記レイアウトは、レイアウト領域内の前記基板上で繰り返される、請求項1に記載の機械可読の符号化データ。
【請求項5】
前記レイアウト領域は、2つ以上のレイアウトのタイプからなる複数のレイアウトを含み、各レイアウトは、そのレイアウトのタイプを符号化する、請求項4に記載の機械可読の符号化データ。
【請求項6】
前記機械可読の符号化データは、分配された符号語が符号化されたものであり、前記分配された符号語の断片は、前記分配された符号語が、異なるタイプの複数の隣接するレイアウトに配置された断片から再構築され得る所定のやり方で、2つ以上のレイアウトのタイプの間に分配される、請求項5に記載の機械可読の符号化データ。
【請求項7】
レイアウトのタイプの数は、2、3、4、および6のうち1つである、請求項5に記載の機械可読の符号化データ。
【請求項8】
前記レイアウトは、局所符号語を符号化し、前記局所符号語の断片は、前記局所符号語が前記断片から再構築され得る所定のやり方で前記レイアウト内に分配される、請求項1に記載の機械可読の符号化データ。
【請求項9】
前記レイアウトは、前記基板上で合わせて束ねられる、請求項4に記載の機械可読の符号化データ。
【請求項10】
前記レイアウトは、直線、正方形、長方形、三角形、または六角形のいずれかの形状とする、請求項1に記載の機械可読の符号化データ。
【請求項11】
nは、2、3、4、および6のうち1つである、請求項1に記載の機械可読の符号化データ。
【請求項12】
1つまたは複数のターゲットフィーチャを含み、それによって、前記符号化データを読み取るのに使用する機械が、前記レイアウトの暫定位置および回転を求めることができる、請求項1に記載の機械可読の符号化データ。
【請求項13】
前記ターゲットフィーチャは、前記機械によって読み取られた後で、前記レイアウトの、または各レイアウトの前記符号化データを遠近補正し得るように構成される、請求項12に記載の機械可読の符号化データ。
【請求項14】
少なくとも4つの前記ターゲットフィーチャを含む、請求項13に記載の機械可読の符号化データ。
【請求項15】
複数の前記レイアウトを含み、前記ターゲットフィーチャの少なくとも一部は、前記レイアウトの少なくとも2つによって共有される、請求項12から14のいずれか一項に記載の機械可読の符号化データ。
【請求項16】
前記符号化データは、前記基板上に印刷される、請求項1に記載の機械可読の符号化データ。
【請求項17】
前記符号化データは、人間の平均的な裸眼に対して可視性が低い、または不可視のインクで表面上に印刷される、請求項16に記載の機械可読の符号化データ。
【請求項18】
前記インクは、人間の平均的な裸眼には実質的に不可視である赤外インクである、請求項17に記載の機械可読の符号化データ。
【請求項19】
各レイアウトの前記符号化データは、ユーザのデータを定義する、請求項1に記載の機械可読の符号化データ。
【請求項20】
前記ユーザデータは、前記表面のある領域に対する相対的な前記レイアウトパターンの位置を示す位置データを含む、請求項19に記載の機械可読の符号化データ。
【請求項21】
前記ユーザデータは、前記レイアウトが配設される前記表面のある領域を識別する識別データを含む、請求項19に記載の機械可読の符号化データ。
【請求項22】
前記ユーザデータは、前記機械が前記レイアウトのパターンまたはサブパターンを読み取った後で実施される関数を識別する関数データを含む、請求項19から21のいずれか一項に記載の機械可読の符号化データ。
【請求項23】
請求項1に記載の機械可読の符号化データを担持する表面。
【請求項24】
前記表面は、平面または曲面である、請求項23に記載の表面。
【請求項25】
目に見える標識をさらに含む、請求項23に記載の表面。
【請求項26】
前記目に見える標識は、文字列、図形、画像、フォーム、フィールド、およびボタンのいずれか1つまたは複数を含む、請求項25に記載の表面。
【請求項27】
前記目に見える標識は、前記符号化データの少なくとも一部に隣接して、あるいは前記符号化データの少なくとも一部と同じ場所に配設される、請求項25に記載の表面。
【請求項28】
前記表面は、基板によって画定される、請求項23に記載の表面。
【請求項29】
前記基板は、紙、カード、または別の薄層媒体である、請求項28に記載の表面。
【請求項30】
使用者とコンピュータの対話を可能にするインターフェース表面として使用されるように構成される、請求項23に記載の表面。
【請求項31】
インターフェース表面を生成する方法であって、
プリンタでユーザのデータを受け取るステップと、
請求項19に記載の、前記ユーザデータを組み込んだ機械可読の符号化データを生成するステップと、
前記符号化データを基板上に印刷するステップとを含む、方法。
【請求項32】
前記基板上に目に見える標識を印刷するステップをさらに含む、請求項31に記載の方法。
【請求項33】
前記符号化データおよび目に見える標識は、実質的に同時に前記基板上に印刷される、請求項32に記載の方法。
【請求項34】
感知装置を使用して、請求項1に記載の機械可読の符号化データを読み取る方法であって、
(a)前記感知装置を使用して、前記レイアウトの前記符号化データを読み取るステップと、
(b)前記レイアウトの前記符号化データを復号して、少なくとも前記向きの符号語の前記表現を求めるステップと、
(c)前記向きの符号語の前記表現を用いて、前記レイアウトの回転の程度を求めるステップとを含む、方法。
【請求項35】
ステップ(a)は、
前記基板を画像化して、前記基板の画像を生成するサブステップと、
前記画像を処理して、前記符号化データの1つまたは複数のターゲットフィーチャを位置決定するサブステップと、
前記位置決定されたターゲットフィーチャに基づいて、前記向きの符号語の前記符号化シンボルの少なくとも1つの位置を求めるサブステップとを含む、請求項34に記載の方法。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【公表番号】特表2006−504360(P2006−504360A)
【公表日】平成18年2月2日(2006.2.2)
【国際特許分類】
【出願番号】特願2005−501485(P2005−501485)
【出願日】平成15年10月10日(2003.10.10)
【国際出願番号】PCT/AU2003/001343
【国際公開番号】WO2004/038650
【国際公開日】平成16年5月6日(2004.5.6)
【出願人】(303024600)シルバーブルック リサーチ ピーティワイ リミテッド (150)
【Fターム(参考)】
【公表日】平成18年2月2日(2006.2.2)
【国際特許分類】
【出願日】平成15年10月10日(2003.10.10)
【国際出願番号】PCT/AU2003/001343
【国際公開番号】WO2004/038650
【国際公開日】平成16年5月6日(2004.5.6)
【出願人】(303024600)シルバーブルック リサーチ ピーティワイ リミテッド (150)
【Fターム(参考)】
[ Back to top ]