(57)【要約】【課題】二次元における絶対位置を効率良く求める。【解決手段】二次元における絶対位置を感知するシステムは、二次元のターゲットパターン(106)を有するターゲットを含む。センサ(102)は、該ターゲットパターンの第１のサブセットの画像(312)を捕捉する。コントローラ(101)は、該画像からピクセル値の行の合計を表す第１の画像ベクトル(314)およびピクセル値の列の合計を表す第２の画像ベクトル(318)を生成する。コントローラは、該第１および第２の画像ベクトルと、該ターゲットパターンを表すターゲットベクトルとに基づいて、ターゲットパターンの原点に対する第１のサブセットの二次元絶対位置を求める。【選択図】図６
2006300939.tif 000002
【特許請求の範囲】
【請求項１】
二次元における絶対位置を感知するためのシステム（１００）であって、
二次元ターゲットパターン（１０６）を有するターゲットと、
前記ターゲットパターンの第１のサブセットの画像（３１２）を捕捉するセンサ（１０２）と、
前記画像からピクセル値の行の合計を表す第１の画像ベクトル（３１４）、および、前記画像からピクセル値の列の合計を表す第２の画像ベクトル（３１８）を生成するコントローラ（１０１）であって、前記第１および第２の画像ベクトルと、前記ターゲットパターンを表す複数のターゲットベクトル（６０１Ｂ、６０１Ｃ、６０１Ｄ、６０１Ｅ）とに基づいて、前記ターゲットパターンの原点に対する前記第１のサブセットの二次元の絶対位置（６１１Ｅ、６１１Ｆ、６１３Ａ、６１３Ｂ）を求めるよう構成されたコントローラと、
を備えるシステム。
【請求項２】
前記ターゲットパターンは、４つ未満のグレーレベルを有する、
請求項１に記載のシステム。
【請求項３】
前記ターゲットパターンは、第１のグレーレベルを有する第１の複数の平行線（３０２）と、第２のグレーレベルを有する第２の複数の平行線（３０４）とを有し、該第１の複数の線は、該第２の複数の線に対して平行である、
請求項１に記載のシステム。
【請求項４】
前記ターゲットパターンは、第１のグレーレベルを有する第３の複数の平行線（３０６）と、第２のグレーレベルを有する第４の複数の平行線（３０８）とを有し、該第３の複数の線は、該記第４の複数の線に対して平行であり、前記第１および第２の複数の線は、該第３および第４の複数の線に対して直交である、
請求項３に記載のシステム。
【請求項５】
前記第１、第２、第３、および第４の複数の線は、第３のグレーレベルを有するバックグラウンド（３１０）上に形成される、
請求項４に記載のシステム。
【請求項６】
前記ターゲットパターン内の前記平行線の間隔は、変化している、
請求項４に記載のシステム。
【請求項７】
前記ターゲットパターンは、該ターゲットパターンの中心に対して２次元対称である、
請求項６に記載のシステム。
【請求項８】
前記コントローラは、  前記第１の画像ベクトルおよび前記第２の画像ベクトルの要素を選択的に累積することによって、複数の合計（１３０２、１３０４、１３０６、１３５８、１３６０）を生成する複数のアキュムレータ（１３１４、１３１６、１３１８、１３５０、１３５２）と、複数の数（１３０８、１３１０、１３１２、１３６２、１３６４）を生成する複数のカウンタ（１３２０、１３２２、１３２４、１３５４、１３５６）とを含む、
請求項１に記載のシステム。
【請求項９】
前記アキュムレータおよび前記カウンタは、前記ターゲットベクトルの選択された部分によって制御され、
該選択された部分は、前記原点に対する前記第１のサブセットの粗い二次元絶対位置（６１１Ｅと６１１Ｆ）に対応し、
前記コントローラは、前記複数の合計および前記複数の数に基づいて、前記原点に対する前記第１のサブセットの細かい二次元絶対位置（６１３Ａと６１３Ｂ）を求めるよう構成される、
請求項８に記載のシステム。
【請求項１０】
対象物（１０８）の位置を求めるための方法であって、
前記対象物上に、二次元のターゲットパターン（１０６）を設けるステップと、
前記ターゲットパターンの第１の部分の画像（３１２）を捕捉するステップと、
前記画像から、ピクセル値の行の合計を表す第１の画像ベクトル（３１４）を生成するステップと、
前記画像から、ピクセル値の列の合計を表す第２の画像ベクトル（３１８）を生成するステップと、
前記第１の部分の二次元絶対位置（６１１Ｅ、６１１Ｆ、６１３Ａ、６１３Ｂ）を表す第１組の位置データ（６１１Ｅ、６１１Ｆ、６１３Ａ、６１３Ｂ）を生成するステップであって、該第１組の位置データは、前記第１および第２の画像ベクトルと、前記ターゲットパターンを表す複数のターゲットシーケンス（６０１Ｂ、６０１Ｃ、６０１Ｄ、６０１Ｅ）とに基づいて生成される、ステップと、
前記対象物の二次元の絶対位置を表す第２組の位置データを生成するステップであって、該生成される第２組の位置データは、前記第１組の位置データに基づいて生成される、ステップと、
を含む、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、二次元の絶対位置を感知する技術に関する。
【背景技術】
【０００２】
多くの用途で、対象物の位置を正確に測定するニーズがある。例えば多数の製造工程では、可動するステージ（台）の正確な位置付けを必要とする。動いている対象物の位置を求めるためにいくつかの手法が開発されている。次にこれらの手法のうち一部を説明する。
【０００３】
一部の従来技術の光学式マウスデバイスでは、マウスパッドの表面の不規則性(irregularity)を含むランダムな二次元のパターンが、デジタルカメラによって連続的なＮ×Ｎピクセルアレイに捕捉される。メモリ深さ(memory depth)は、現在のアレイを少なくとも１超える。９つの二次元の相関性（例えば、各方向へ１ステップ：左、右、上、下、２本の対角線の両方向、および、「変更なし」）が計算される。９つの相関性のうちの最大値を観察することにより、マウスの移動方向を求めることができる。相関値を補間することにより、移動の長さは、センサピクセルの何分の一(fraction)で推定することができる。位置を求めるこの方法は、インクリメンタル的(incremental(なものであって絶対的なものではなく、フレーム間の移動は、典型的には１ピクセルを超えることができないか、またはエラーが生じる可能性がある。
【０００４】
他の一部の従来技術の用途では、ランダムターゲットの代わりに特定のターゲットを使用する。たとえば一部の一次元インクリメンタルエンコーダは、一次元正弦波の直交した２つの格子を使用して、２つの連続する画像のグレースケールを生成する。スケールの既知の強度プロファイルの較正により、１サイクル未満の補間が可能になり、直交した２つの信号によって可能になった適切な移動方向でのサイクル数をカウントすることにより、粗い位置と細かい位置の両方を求めることができる。この手法は、業界内で非常によく使用されているが、マウスの場合と同様にインクリメンタルな測定技術であり、同じ限界がある。
【０００５】
二次元用途に一次元エンコーダ技術を使用するためには、一般に、厄介な機械的なステージの積み重ねが必要である。
【０００６】
他の一部の従来技術の用途では、二次元の絶対位置のコード化（符号化）のために、ターゲット全体にわたって、各Ｎ×Ｎパターンの二次元相関を作る必要性を低減するために、位置をラベリングしたコードが使用されている。該コードは、ランダムまたは周期的な細かいグレースケールのバックグラウンドに周期的にインタリーブされる。（未知の）該位置コード（複数可）が、画像からまず識別されて抽出され、内容が解読される。ついで該画像内の該コードの位置を、より正確に見つけ、推定によって、該画像の位置を確立する。
【０００７】
いくつかの従来技術の方法は、アナログ形式の相関関数を観察することによって、別個の相関の間で補間する。ターゲットパターンの相互相関によりこの方法の精度が低下するので、慎重に制御しなければならない。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
上記のような従来技術の位置決定システムは、通常はあまり効率的ではなく、比較的大量のメモリが必要になり、これらのシステムの一部で使用されるターゲットは、作成するのも使用するのも複雑である。
【課題を解決するための手段】
【０００９】
本発明の一つの側面によると、二次元の絶対位置(absolute position)を感知するシステムが提供される。該システムは、二次元ターゲットパターンを有するターゲットを含む。センサは、ターゲットパターンの第１のサブセットの画像を捕捉する。コントローラは、該画像から、ピクセル値の行の合計を表す第１の画像ベクトルと、ピクセル値の列の合計を表す第２の画像ベクトルとを生成する。コントローラは、該第１および第２の画像ベクトルと、ターゲットパターンを表す複数のターゲットベクトルとに基づいて、該ターゲットパターンの原点に対する該第１のサブセットの二次元の絶対位置を求めるよう構成される。
【発明を実施するための最良の形態】
【００１０】
以下の詳述では、本明細書の一部を形成すると共に、本発明を実行する或る特定の実施形態を例示的に示す図面を参照する。本発明の範囲から離れることなく、他の実施形態をも使用することができ、また、構造的または論理的な変更も可能であることを理解されたい。したがって、以下の詳述は限定的な意味で理解すべきではなく、本発明の範囲は、特許請求の範囲によって定義されるものである。
【００１１】
本発明の一形態は、対象物上に形成された２値（バイナリ）または３値（ターナリ(ternary)）のターゲットのデジタル画像に基づいて、該対象物の二次元の絶対位置を求める方法および装置を提供する。一実施形態では、センサは、ターゲットの一部の画像を捕捉し、該ターゲット内の画像の二次元の位置を、ピクセル未満の解像度で求める。本発明の一形態では、ブロック回帰(block regression)技術を使用して、位置を求める。一実施形態では、第１のプロセスを、粗い位置(coarse position)を求めるよう（たとえば１つのピクセル内）に行い、次に第２のプロセスを、細かい位置(fine position)を求める（たとえば１ピクセルの何分の一内）よう行う。一実施形態では、第２のプロセスは、一組の冗長データおよび数式に対して数学的に解を最良にフィッティングさせることによって、絶対位置の決定を、ピクセルの何分の一にまで細かくするブロック回帰プロセスである。
【００１２】
Ｉ．  システム
図１は、本発明の一実施形態による、対象物１０８の二次元の絶対位置を見つけるためのシステム１００を示す、簡略化された図である。図に示される実施形態では、対象物１０８は製造工程における可動ステージ（可動台）であり、６自由度の高い精度で、「ホーム(home)」ポジションを探す。対象物１０８は、本明細書ではステージ１０８と呼ばれる。当業者であれば、本発明の実施形態は、二次元絶対位置の感知が望ましい他のタイプのシステムおよびプロセスにも適用可能であることが理解されるであろう。
【００１３】
システム１００は、位置データ生成装置１０１（コントローラとも呼ばれる）およびセンサ１０２を含む。ステージ１０８は、ステージ１０８の１つの角（コーナー）に位置するターゲット面すなわちターゲット表面１０４を含む。ターゲット面１０４の簡単に見られるように、ターゲット面１０４の領域は誇張されて示されている。ターゲット面１０４は、第１の軸Ｖ０（エレべーション（elevation、上下方向））と、第１の軸Ｖ０に対して直交する第２の軸Ｗ０（ウィンデージ（windage、左右方向））とによって、二次元で定義される。ターゲットパターン１０６は、ターゲット面１０４上に形成される。ターゲットパターン１０６の種々の形態を、図３から図５に示し、これについては、後述される。
【００１４】
一実施形態による動作においては、センサ１０２は、照明し、ターゲット１０６の一部の画像を捕捉する。本発明の一形態では、捕捉された画像は、センサ１０２から、位置データ生成装置１０１に出力される。位置データ生成装置１０１は、ターゲット１０６の捕捉された画像を処理し、捕捉された画像に基づいて二次元の絶対ターゲット位置データを生成する。ターゲット位置データは、ターゲット１０６の原点に対するターゲット１０６の撮像された部分の絶対位置を、ウィンデージ次元とエレベーション次元で表す。本発明の一形態では、位置データ生成装置１０１は、二次元のターゲット位置データに基づいて、ターゲット面領域の二次元の水平方向の絶対位置を求める。
【００１５】
他の実施形態では、他のセンサ１０２およびターゲット１０６を使用し、３つのターゲット面位置の二次元の水平方向位置を測定し、合計で６つの、３組のウィンデージデータおよびエレベーションデータを生成する。該６つの数の線形処理により、６自由度（すなわち、３つの直交する軸（Ｘ軸、Ｙ軸、Ｚ軸）に沿った平行移動と、３本の直交する軸を中心とした回転（ロール(roll)、ピッチ(pitch)、ヨー(yaw)））で、ステージ１０８の位置を求める。
【００１６】
本発明のさらに他の実施形態では、単一ターゲット１０６を、たとえばステージ１０８の底面に配置し、システム１００はこれを使用して、ステージ１０８の二次元の絶対位置を識別する。
【００１７】
図２は、本発明の一実施形態によるセンサ１０２を示す簡略化した図である。図に示される実施形態では、センサ１０２は、光源２０２、イメージセンサチップ２０４、光学素子２０６を含む。一実施形態では、光源２０２は、発光ダイオード（ＬＥＤ）である。他の実施形態では、センサ１０２は、光源２０２を含まない。本発明の一形態では、イメージセンサチップ２０４は、相補型金属酸化膜半導体（ＣＭＯＳ）イメージセンサである。一実施形態では、光学素子２０６は、１つまたは複数の光学レンズを含む。本発明の一形態では、光源２０２は、ターゲット１０６を照明する光２０８を出力する。ターゲット１０６からの反射光２１０は、光学素子２０６によって、イメージセンサチップ２０４上に方向変換される。イメージセンサチップ２０４は、受光した光に基づいて、ターゲット１０６の一部を表すデジタル画像を生成し、このデジタル画像を、位置データ生成装置１０１に提供し、センサ１０２または他の基準点に対するターゲット１０６（及びこれに対応してステージ１０８）の現在位置を求める。
【００１８】
ＩＩ．ターゲット
図３は、本発明の一実施形態による、５５×５５ピクセル、３グレースケール（３値）のターゲット１０６Ａを示す図である。ターゲット１０６Ａは、図１で示したターゲット１０６の第１の実施形態を表す。図示された実施形態では、ターゲット１０６Ａは３つだけのグレーレベルを有する。本明細書ではこれらのレベルを白、灰色、黒と呼ぶ。二次元ターゲット１０６Ａは、複数の白い垂直線３０２、複数の黒い垂直線３０４、複数の白い水平線３０６、複数の黒い水平線３０８を含む。線３０２、３０４、３０６、３０８は、ターゲット１０６Ａ全体にわたって伸び、同様にターゲット１０６Ａ全体にわたって伸びる灰色のバックグラウンド３１０上に形成されている（点描の影で表している）。図示された実施形態では、線３０２と３０４は、線３０６と３０８に直交する。本発明の一形態では、補間を含むデジタルコード化処理を容易にするために、平行な黒線と白線は、直接隣接しない。一実施形態では、線の交差におけるターゲット１０６Ａのピクセルは、次のように指定される。（１）黒と灰色の交差におけるピクセルは黒にする、（２）白と灰色の交差におけるピクセルは白にする、（３）黒と白の交差におけるピクセルは灰色にする。
【００１９】
図３では、ターゲット１０６Ａは、ウィンデージすなわち水平方向を表す水平軸（Ｗ０）と、エレベーションすなわち垂直方向を表す垂直軸（Ｖ０）とを伴うグリッド上で示されている。軸Ｗ０とＶ０は、ターゲット１０６Ａの左上角の原点で始まり、直角に外向きに伸びる。図示された実施形態では、ターゲット１０６Ａは、ターゲット１０６Ａの中心に対してＷ０とＶ０の両方の次元で対称であり、両方の次元の線の設計は同一である。これにより、両方の次元に対して共通のコード化アルゴリズムを使用することができる。図３に示すような直交する直線の設計パターンにより、２つの次元について別個の独立した一次元位置処理が可能になる。
【００２０】
一実施形態では、線の空間的分離は、１３の連続したピクセルにわたる一次元シーケンスが重複しないように、数学的に合成される。この結果、ターゲット１０６Ａの任意の１３×１３ピクセル（またはより大きな）画像は一意的である。言い方を換えれば、所与の任意の１３×１３ピクセル（またはより大きな）画像については、ターゲット１０６Ａ内の該画像の位置は、直線のパターンから一意的に求めることができる。センサ１０２（図１）が捕捉した１６×１６画像の例３１２が、図３に示されている。画像３１２は、１３×１３ピクセルより大きいので、ターゲット１０６Ａ内の画像３１２の位置は、線のパターンから求めることができる。画像３１２のピクセルは、ターゲット１０６Ａのピクセルと垂直方向でも水平方向でもアライメント（位置合わせ）されている。画像３１２の左上のピクセルは、グリッドの第４の行と第３５の列に位置する。したがって、一実施形態によるターゲット１０６Ａの原点に対する画像３１２の位置は（４，３５）と指定される。画像３１２のピクセルは、ターゲット１０６Ａのピクセルから垂直または水平にオフセットされている場合がある。たとえば、図３に示す位置から、ピクセルの何分の一かだけ左または右にシフトされている、または、ピクセルの何分の一かだけ上または下にシフトされている。このような場合、画像３１２の位置の指定は、小数点の値（例えば４．３５、３５．６０）を含むこととなる。
【００２１】
ターゲット１０６Ａの中心は、３つの垂直列３１６Ａを含む。これらは、グリッド上で「ｃｃｃ」とラベリングされている。列３１６Ａは、ここでは、水平の白線または黒線との交差箇所を除き、灰色−黒−灰色である。列３１６Ａのすぐ右隣に５つの列３１６Ｂがある。これらはグリッド上で、「２２２２２」とラベリングされている。列３１６Ｂは、ここでは、中心から外側にカウントして、白−灰色−黒−灰色−灰色である。列３１６Ｂは、「２周期(2-period)」と定義され、白−灰色−黒の列のプリアンブル(preamble,前段)とこれに続く２本の灰色の列を含む。プリアンブルに続く灰色の列の数は、周期を指定する（すなわち、プリアンブルに続く２つの灰色の列は、２周期を構成する）。列３１６Ｂのすぐ右隣に、２組の８列３１６Ｃおよび３１６Ｄがあり、これらはグリッド上では両方とも、「５５５５５５５５」とラベリングされている。列３１６Ｃおよび３１６Ｄは、両方とも、ここでは、中心から外側にカウントして、白−灰色−黒−灰色−灰色−灰色−灰色−灰色である。列３１６Ｃおよび３１６Ｄは両方とも、「５周期」と定義され、白−灰色−黒の列のプリアンブルとこれに続く５本の灰色の列を含む。列３１６Ｄのすぐ右隣に、５つの列３１６Ｅがあり、グリッド上では２２２２２とラベリングされている。列３１６Ｅは、ここでは、中心から外側にカウントして、白−灰色−黒−灰色−灰色である。列３１６Ｅは「２周期」と定義され、白−灰色−黒の列のプリアンブルとこれに続く２本の灰色の列を含む。
【００２２】
このように、上記の表記法を使用すると、ターゲット１０６Ａは、周期シーケンス２、５、５、２を有する。線のパターンがターゲット１０６Ａの中心に対して対称で、二次元が同じパターンを共有するので、ターゲット１０６Ａの５５列すべてと５５行すべてが、周期シーケンスによって完璧に指定される。こうして、５５×５５のターゲット１０６Ａ全体の各ピクセルは、簡潔な表記法２、５、５、２によって完璧に指定される。
【００２３】
さらに図３には、エレベーションベクトル（Ｖ）３１４およびウィンデージベクトル（Ｗ）３１８が示されている。これらは両方とも画像３１２に対応する。ベクトル３１４および３１８は、画像３１２の位置を決定する際に使用される。これに関しては、図６を参照して後述される。
【００２４】
図４Ａは、本発明の一実施形態による、７１１×７１１ピクセル、３グレースケール（３値）のターゲット１０６Ｂを示す図である。ターゲット１０６Ｂは、図１に示したターゲット１０６の第２の実施形態を表す。図示された実施形態では、ターゲット１０６Ｂは、図３に示すターゲット１０６Ａの拡張バージョンであり、ターゲット１０６Ｂの５５×５５ピクセルの中心部分は、ターゲット１０６Ａと同一である。こうして、ターゲット１０６Ａは、ターゲット１０６Ｂの中心部分をズームインした表示を表す。ターゲット１０６Ｂの解像度が高く、このターゲット１０６Ｂをページ上に表示するスペースが限られているので、図４Ａでは、このターゲットの水平線と垂直線の完全なパターンは示されていない。図４Ｂは、ターゲット１０６Ｂの円で囲んだ部分を拡大したものであり、以下に、線の完全なパターンについて説明する。
【００２５】
本発明の一形態では、ターゲット１０６Ｂは、ターゲット１０６Ａと同様に３つだけのグレーレベルを有する。本明細書ではこれらを白、灰色、黒と呼ぶ。二次元ターゲット１０６Ｂは、白の垂直線と黒の垂直線、白の水平線と黒の水平線を含む。垂直線と水平線はターゲット１０６Ｂ全体にわたって伸び、やはりターゲット１０６Ｂ全体にわたって伸びる灰色のバックグラウンド上に形成されている（図４Ｂでは点描の影で示す）。
【００２６】
ターゲット１０６Ｂは、ターゲット１０６Ａよりはるかに長い周期シーケンスを有する。図３に関して上述した簡潔な表記法では、一実施形態によるターゲット１０６Ｂは、次の周期シーケンスによって完全に指定される。すなわち、2,5,5,2,2,  5,4,3,2,5,  3,4,2,4,4,  4,2,3,5,4,  2,2,4,5,3,  2,3,4,5,2,  3,3,4,3,5,  2,4,3,4,4,  3,3,3,5,3,  3,2,2,2,3,  2,4,2,5,2, 5。
【００２７】
ターゲット１０６Ｂのシーケンスが２、５、５、２で開始し、これが、小さな５５×５５ターゲット１０６Ａのシーケンスであることに注意されたい。これにより、小さなターゲット１０６Ａが、実際には、大きな７１１×７１１ターゲット１０６Ｂの中心部分と同じであることが確認される。
【００２８】
確実に一意的にするために、２周期、３周期、４周期、５周期は、３つの連続期間を繰り返さすことなくシーケンスされる。言い換えれば、ターゲット１０６Ｂの周期シーケンス内で３つの連続する２周期と３つの連続する３周期があるが、３つの連続する２周期のインスタンスは１つだけ、３つの連続する３周期のインスタンスは１つだけである。同様に、ターゲット１０６Ｂの周期シーケンスにおいて、３つの連続番号の他のすべてのシーケンスも一度しか生じない。（５,５,５）、（５,５,４）、（５,５,３）、およびこれらの並べ換え（permutation）などの、いくつかのより大きなシーケンスは、ターゲット１０６Ｂの周期シーケンスから除外される。異なる開始値（２,５,５以外）および異なる分類基準により、他の有効なシーケンスを生成し、異なるターゲット設計を製作することができる。６以上の周期が含まれれば、はるかに長いシーケンス（たとえばはるかに大きなターゲット１０６）も可能である。
【００２９】
図示された実施形態では、ターゲット１０６Ｂの任意の２３×２３ピクセル（またはより大きな）画像が一意的である。言い方を換えれば、所与の任意の２３×２３ピクセル（またはより大きな）画像では、ターゲット１０６Ｂ内の該画像の位置は、線のパターンから一意的に求めることができる。実際には、ノイズ外乱により、別個のシーケンス間の差が侵されることがある。類似のシーケンス間の差を増やす任意の手段により、誤差限界(error margin)が広がり、システムのロバスト性が増加する。一実施形態では、類似のシーケンス間の差を、複数の慎重に選択された周期についてプリアンブル内で黒の要素と白の要素を反転（すなわちフリッピング(flipping)）することにより増やす。一実施形態では、フリッピングは、ターゲットの中心に対して対称的な方法で対(pair)で行なわれ、これによって、ターゲット全体の対称性を維持する。たとえば、「３周期」シーケンスをフリッピングすると、白−灰色−黒−灰色−灰色−灰色は、黒−灰色−白−灰色−灰色−灰色になる。一実施形態によれば、ターゲット１０６Ｂ全体で２４個のフリッピングされた周期を伴うターゲット１０６Ｂは、次の周期シーケンスで指定される（フリッピングされた周期は、ボールド体かつ下線で示されている）。
【数１】
2006300939.tif 000003
【００３０】
図５は、本発明の一実施形態による、５５×５５ピクセル、２グレースケール（２値）のターゲット１０６Ｃを示す図である。ターゲット１０６Ｃは、図１に示すターゲット１０６の第３の実施形態を表す。ターゲット１０６Ｃは、本質的に、図３に示す３値のグレースケールターゲット１０６Ａの２値グレースケールバージョンであり、図３の灰色のバックグラウンド領域３１０は、２ピクセルピッチの黒白ピクセルの市松模様デザインで置き換えられている。白線と黒線の各交点では、該交点のピクセルは白と定義される。
【００３１】
３グレーレベルターゲット１０６Ａおよび１０６Ｂは、２グレーレベルのターゲット１０６Ｃより良好な性能を提供する傾向がある。黒ピクセルおよび白ピクセルの市松模様デザインを、２ピクセルではなく１ピクセルのピッチであれば、ターゲット１０６Ｃの性能を向上させることができる。
【００３２】
一実施形態では、ターゲット１０６Ａから１０６Ｃは、完全に決定論的(deterministic)である。例えば、解析およびシミュレーションにより、７１１×７１１ターゲット１０６Ｂ内の任意の２３×２３画像が、絶対的に一意的であることが示された。したがって本発明の一形態では、ターゲット１０６Ａから１０６Ｃ内では、位置をラベリングするのに、埋め込まれた位置コードを使用しない。最小よりは大きい画像（たとえば３２×３２ピクセル）は、回帰アルゴリズム（後述される）が「ベストフィット(best fit)」のやり方で効果的に動作するよう、冗長データを提供する。
【００３３】
本発明の一形態では、ターゲット１０６Ａから１０６Ｃは、ガラス基板上に半反射性(semi-reflective)および高反射性のクロムを堆積させて、灰色のピクセルおよび白いピクセルをそれぞれ形成することによって構成される。反射防止コーティングをガラス基板上に形成し、黒ピクセルを形成する。３つの反射値は、別個で比較的均一であればよい。一実施形態では、厳密な量的関係（たとえば正弦波特性(sinusoidal profile)）は使用されない。透過性のターゲットでは、超微粒子フィルム上のデジタル印刷は、一部の用途では便利かつ経済的であることが示されている。
【００３４】
ＩＩＩ  位置データ生成装置
図６は、本発明の一実施形態による、図１に示す位置データ生成装置１０１の主要構成要素を示すブロック図である。位置データ生成装置１０１は、ウィンデージ用の粗いメインロケータ６０２、ウィンデージ用の粗いデミロケータ６０４、エレベーション用の粗いメインロケータ６０６、エレベーション用の粗いデミロケータ６０８、粗い位置データ生成装置６１０、細かい位置データ生成装置６１２、ウィンデージ及びエレベーションベクトル生成装置６１４、メモリ６１６、シフトレジスタ６１８、カウンタ６２０を含む。本発明の一形態では、位置データ生成装置１０１はまず、２つの独立した一次元回帰プロセスを使用して、センサ１０２が捕捉した画像の粗い位置を求め、その後、第２の回帰プロセスを行って、該捕捉された画像の細かい位置を求める。
【００３５】
以下の説明では、センサ１０２は、図３に示す画像３１２などの、５５×５５ピクセルのターゲット１０６Ａ（図３）の画像を捕捉すると仮定する。図示されている画像３１２のピクセルは、ターゲット１０６Ａのピクセルと完全にアライメントされている。実際には、画像３１２のピクセルは、通常、両方の次元で、完全なアライメントからはオフセットされる。該オフセットの量は、細かい位置データ生成装置６１２によって正確に算出されることができる。これに関しては、図１３から図１５を参照して後述される。
【００３６】
Ａ  粗い位置(COARSE POSITION)
画像３１２の粗い位置の目的は、ウィンデージ（Ｌｗ）およびエレベーション（Ｌｖ）の両方で、ターゲット１０６Ａの座標を１ピクセル内に識別することである。粗い位置プロセスを説明するために、ターゲット１０６Ａのピクセルは、次の強度を有すると仮定する。すなわち、黒いピクセルは光強度０、灰色のピクセルは光強度０．５、白いピクセルは光強度１を有する。実際には、光強度はピクセルごとに変化し、同じターゲットからの同じタイプ内でも変化し、灰色の強度がちょうど０．５である場合はほとんどない。しかしながら、回帰アルゴリズムの冗長性により、ピクセル間の変動およびグレーの偏り（バイアス,bias)の影響が最小化される。しかし説明を簡単にするために、強度は理想的に０、０．５、１と仮定する。
【００３７】
粗い位置プロセス中、ベクトル生成装置６１４は画像３１２を受信し、ゼロ平均(zero-mean)ウィンデージベクトル６０１Ａ（Ｗｚ）およびゼロ平均エレベーションベクトル６０１Ｆ（Ｖｚ）を生成する。これらは両方とも画像３１２に対応する。次に、一実施形態によるこれらのゼロ平均ベクトル６０１Ａおよび６０１Ｆの生成について、詳細に説明する。
【００３８】
ベクトル生成装置６１４は、画像３１２の１６個の列をすべて合計し、１６要素のウィンデージベクトル３１８（Ｗ）を形成する。これを図３に示す。図３に示すように、画像３１２の第１の列は、１４個の白いピクセルと２つの灰色のピクセルを含む。したがって、ウィンデージベクトル３１８（Ｗ）の第１要素は「１５」（すなわち、１４×１＋２×０．５＝１５）となる。ベクトル生成装置６１４は、１６個の列のそれぞれについて、この合計を行い、この結果、１６要素のウィンデージベクトル３１８（Ｗ）が得られる。これは次式Ｉで与えられる。
【００３９】
式  Ｉ
Ｗ＝（15, 8, 1, 8, 8, 8, 8, 8, 15, 8, 1, 8, 8, 8, 8, 8）
ここで、Ｗは、ウィンデージベクトル３１８である。
【００４０】
ベクトル生成装置６１４はまた、画像３１２の１６個の行をすべて合計し、１６要素のエレベーションベクトル３１４（Ｖ）を形成する。これを図３に示す。図３に示すように、画像３１２の第１の行は２つの白いピクセル、１２個の灰色ピクセル、２つの黒いピクセルを含む。したがって、エレベーションベクトル３１４（Ｖ）の第１要素は「８」（すなわち、２×１＋１２×０．５＋２×０＝８）となる。ベクトル生成装置６１４は、１６個の行のそれぞれについてこれを行い、この結果、１６要素のエレベーションベクトル３１４（Ｖ）が得られる。これは式ＩＩによって与えられる。
【００４１】
式  ＩＩ
Ｖ＝（8, 15, 8, 8, 8, 8, 8, 1, 8, 15, 8, 8, 8, 8, 8, 1）
ここで、Ｖは、エレベーションベクトル３１４である。
【００４２】
ベクトル生成装置６１４は、ウィンデージベクトル３１８（Ｗ）（または等価的にＶ）の１６要素すべてを合計し、該合計を１６で除算して、全体のベクトル平均（Ｖａｖｇ）を生成する。これを、次の式ＩＩＩで示す（１６で除算することは、バイナリ表記法では４ビットのシフトに過ぎないことに注意されたい）。
【００４３】
式  ＩＩＩ
Ｖａｖｇ＝（15＋8＋１＋8＋8＋8＋8＋8＋15＋8＋１＋8＋8＋8＋8＋8）／１６＝８
ベクトル生成装置６１４は、ベクトル平均（Ｖａｖｇ）を、すべてのＷ要素およびＶ要素から引き、ゼロ平均ベクトル６０１Ａおよび６０１Ｆ（ＷｚとＶｚ）を生成する。これを、次の式ＩＶおよびＶにそれぞれ示す。
【００４４】
式  ＩＶ
Ｗｚ＝（7, 0, -7, 0, 0, 0, 0, 0, 7, 0, -7, 0, 0, 0, 0, 0）
ここで、Ｗｚは、ゼロ平均ウィンデージベクトル６０１Ａである。
【００４５】
式  Ｖ
Ｖｚ＝（0, 7, 0, 0, 0, 0, 0, -7, 0, 7, 0, 0, 0, 0, 0, -7）
ここで、Ｖｚは、ゼロ平均エレベーションベクトル６０１Ｆである。
【００４６】
ゼロ平均ベクトル６０１Ａおよび６０１Ｆ（ＷｚおよびＶｚ）は、元の１６×１６ピクセル画像３１２の回帰抽出バージョン(regression-distilled version)を表し、２つのターゲット画像座標ＬｗおよびＬｖの位置を突き止めるのに使用される。一実施形態では、画像３１２の元の画素は８ビットの精度を有し、上記の合計で２ビットの精度が追加される。ゼロ平均ウィンデージベクトル６０１Ａ（Ｗｚ）は、ベクトル生成装置６１４によって、ウィンデージ用の粗いメインロケータ６０２およびウィンデージ用の粗いデミロケータ６０４に出力される。ゼロ平均エレベーションベクトル６０１Ｆ（Ｖｚ）は、ベクトル生成装置６１４によって、エレベーション用の粗いメインロケータ６０６およびエレベーション用の粗いデミロケータ６０８に出力される。ウィンデージベクトル３１８（Ｗ）およびエレベーションベクトル３１４（Ｖ）は、ベクトル生成装置６１４によって、細かい位置データ生成装置６１２に出力される。位置データ生成装置１０１の図を簡単にするために、図６の一部の要素間の接続は示されていない。
【００４７】
本発明の一形態では、複数のシーケンスすなわちベクトルを、ターゲット１０６Ａの特徴に基づいて決定し、メモリ６１６内に記憶する。一実施形態では、これらのシーケンスは、第１のメインシーケンス６０１Ｂ（Ｍ１）、第２のメインシーケンス６０１Ｃ（Ｍ２）、第１のｄｅｍｉシーケンス６０１Ｄ（ｄｅｍｉ１）、第２のｄｅｍｉシーケンス６０１Ｅ（ｄｅｍｉ２）を含む。
【００４８】
本発明の一形態では、ゼロ平均ベクトル６０１Ａおよび６０１Ｆ（ＷｚとＶｚ）は、ターゲット１０６Ａ内の画像３１２の位置に依存して画像３１２ごとに異なるが、シーケンス６０１Ｂ、６０１Ｃ、６０１Ｄ、６０１Ｅは、メモリ６１６内に記憶されていて画像３１２によって変わらない予め計算される一定のシーケンスすなわちベクトルである。図６に示すように、シーケンス６０１Ｂ、６０１Ｃ、６０１Ｄ、６０１Ｅは、メモリ６１６からシフトレジスタ６１８に出力される。シフトレジスタ６１８は、カウンタ６２０によってアドレスされ、４つのシーケンス６０１Ｂ、６０１Ｃ、６０１Ｄ、６０１Ｅを同期的に、ロケータ(locator)６０２、６０４、６０６、６０８のうちの適切なロケータへシフトする。メインシーケンス６０１Ｂおよび６０１Ｃ（ＭｌおよびＭ２）は、ウィンデージ用の粗いメインロケータ６０２およびエレベーション用の粗いメインロケータ６０６へシフトされ、ｄｅｍｉシーケンス６０１Ｄおよび６０１Ｅ（ｄｅｍｉ１とｄｅｍｉ２）は、ウィンデージ用の粗いデミロケータ６０４およびエレベーション用の粗いデミロケータ６０８へシフトされる。次に、シーケンス６０１Ｂ、６０１Ｃ、６０１Ｄ、６０１Ｅの値の決定については、後述される。
【００４９】
図３を参照して上述したように、ターゲット１０６Ａは、２、５、５、２周期シーケンスを有する。２、５、５、２周期シーケンスを符号で完全にスペルアウトすると、次の式ＶＩに示すように、５５要素の３値のシーケンスＭ３のように見える（読みやすくするためにスペースを追加している）。
【００５０】
式  ＶＩ
Ｍ３＝
（0,0,-1,0,1,  0,0,0,0,0,-1,0,1,  0,0,0,0,0,-1,0,1,  0,0,-1,0,1,  0,-1,0,  
1,0,-1,0,0,  1,0,-1,0,0,0,0,0,  1,0,-1,0,0,0,0,0,  1,0,-1,0,0）
【００５１】
シーケンスｄｅｍｉ３は、次の式ＶＩＩが示すように、２つの連続するＭ３要素を加えることによって（代数的に）生成される。
【００５２】
式  ＶＩＩ
ｄｅｍｉ３（ｉ）＝Ｍ３（ｉ）＋Ｍ３（ｉ＋１）for  ｉ  from−２７≦ｉ≦＋２６
ｄｅｍｉ３（２７）は、１として定義される。
【００５３】
この結果得られるシーケンスｄｅｍｉ３もまた、３値であることに注意されたい。この結果得られるｄｅｍｉ３シーケンスは、次の式ＶＩＩＩによって与えられる。
【００５４】
式  ＶＩＩＩ
ｄｅｍｉ３＝
（0,-1,-1,1,1,  0,0,0,0,-1,-1,1,1,  0,0,0,0,-1,-1,1,1,  0,-1,-1,1,1,  -1,-1,1,  1,-1,-1,0,1,  1,-1,-1,0,0,0,0,1,  1,-1,-1,0,0,0,0,1,  1,-1,-1,0,1）
【００５５】
３値のロジックは、当業界で一般的ではない。より一般的なバイナリのロジックに変換すると、容易に入手できるデジタルバイナリ論理回路での実装が容易になる。変換のための論理式は、次の表１により与えられる。
【表１】
2006300939.tif 000004
【００５６】
式ＶＩで定義された３値シーケンスＭ３は、表１に与えられた変換を使用して２つのバイナリシーケンス６０１Ｂおよび６０１Ｃ（Ｍ１およびＭ２）に変換されることができる。これを、次の式ＩＸおよびＸにそれぞれ示す。
【００５７】
式  ＩＸ
Ｍ１＝
（0,0,1,0,1,  0,0,0,0,0,1,0,1,  0,0,0,0,0,1,0,1,  0,0,1,0,1,  0,1,0,  
1,0,1,0,0,  1,0,1,0,0,0,0,0,  1,0,1,0,0,0,0,0,  1,0,1,0,0）
式  Ｘ
Ｍ２＝
（0,0,1,0,0,  0,0,0,0,0,1,0,0,  0,0,0,0,0,1,0,0,   0,0,1,0,0,  0,1,0,  
0,0,1,0,0,  0,0,1,0,0,0,0,0,  0,0,1,0,0,0,0,0,  0,0,1,0,0）
【００５８】
式ＶＩＩＩに定義された３値シーケンスｄｅｍｉ３も同様に、２つのバイナリシーケンス６０１Ｄおよび６０１Ｅ（ｄｅｍｉ１とｄｅｍｉ２）に変換されることができる。これは、次の式ＸＩおよびＸＩＩにそれぞれ示される。
【００５９】
式  ＸＩ
ｄｅｍｉ１＝
（0,1,1,1,1,  0,0,0,0,1,1,1,1,  0,0,0,0,1,1,1,1,  0,1,1,1,1,  1,1,1,  
1,1,1,0,1,  1,1,1,0,0,0,0,1,  1,1,1,0,0,0,0,1,  1,1,1,0,1）
式  ＸＩＩ
ｄｅｍｉ２＝
（0,1,1,0,0,  0,0,0,0,1,1,0,0,  0,0,0,0,1,1,0,0,  0,1,1,0,0,  1,1,0,  
0,1,1,0,0,  0,1,1,0,0,0,0,0,  0,1,1,0,0,0,0,0,  0,1,1,0,0）
【００６０】
一実施形態では、４つの固定シーケンス６０１Ｂ（Ｍ１）、６０１Ｃ（Ｍ２）、６０１Ｄ（ｄｅｍｉ１）、および６０１Ｅ（ｄｅｍｉ２）を、ベクトル６０１Ａ（Ｗｚ）および６０１Ｆ（Ｖｚ）と共に使用し、ウィンデージ（水平）およびエレベーション（垂直）の両方向で画像３１２の粗い位置を求める（たとえば１ピクセル内）。一実施形態では、ターゲットパターンはいずれの次元でも同じであるので、両方の次元に共通のアルゴリズムを使用することができる。本発明の一形態では、ハードウェア要件は少なめであり、図７から図１０を参照して後述する４つの動作を、並列に行うことができる。
【００６１】
ｄｅｍｉシーケンス６０１Ｄおよび６０１Ｅは、２つの隣接するターゲットピクセルの間の中間近くにある画像３１２の位置を特定するのに最良である。ｄｅｍｉシーケンス６０１Ｄおよび６０１Ｅはまた、各次元で、画像３１２を囲む(メインベクトル６０１Ｂおよび６０１Ｃの正しい２つの連続した１６要素のサブセット（最も近いメインベクトルの１サブセットだけでない）を求める際の助けになる。
【００６２】
また図６に示すように、ウィンデージ用の粗いメインロケータ６０２は、複数のメインウィンデージセレクタ値６０３Ａ（ＳＭＷ（ｊ））を生成し、セレクタ値６０３Ａを粗い位置データ生成装置６１０に出力する。ここで、「ｊ」は、個別のセレクタ値を識別するインデックスである。ウィンデージ用の粗いデミロケータ６０４は、複数のデミウィンデージセレクタ値６０３Ｂ（ＳＤＷ（ｊ））を生成し、セレクタ値６０３Ｂを、粗い位置データ生成装置６１０に出力する。エレベーション用の粗いメインロケータ６０６は、複数のメインエレベーションセレクタ値６０３Ｃ（ＳＭＶ（ｊ））を生成し、セレクタ値６０３Ｃを、粗い位置データ生成装置６１０に出力する。エレベーション用の粗いデミロケータ６０８は、複数のデミエレベーションセレクタ値６０３Ｄ（ＳＤＶ（ｊ））を生成し、セレクタ値６０３Ｄを、粗い位置データ生成装置６１０に出力する。次に、図７から図１０を参照して、ロケータ６０２、６０４、６０６、６０８によるセレクタ値６０３Ａ、６０３Ｂ、６０３Ｃ、６０３Ｄのそれぞれの生成を詳述する。
【００６３】
図７は、本発明の一実施形態による、図６のブロックで示されるウィンデージ用の粗いメインロケータ６０２の主要構成要素を示す概略図である。ウィンデージ用の粗いメインロケータ６０２は、水平ターゲットグリッドから水平方向に大幅にオフセットされていない画像の位置を効果的に突き止める。図７に示すように、ウィンデージ用メインロケータ６０２は、加算器７０２、加算器の行７０４、加算器の行７０６、ＯＲゲートの行７０８、ＡＮＤゲートの行７１０、遅延素子（Ｄ）の行７１２、ＸＮＯＲゲートの行７１４、遅延素子の行７１６を含む。
【００６４】
図７では、ゼロ平均ウィンデージベクトル６０１Ａ（Ｗｚ）の１６個の要素は、ＷＺ（１６）、ＷＺ（１５）、…ＷＺ（１）として示されている。一実施形態では、ベクトル６０１Ａの各要素は、最上位ビットに等しい４つの最下位ビットで埋められる。シーケンス６０１Ｂおよび６０１Ｃ（Ｍ１およびＭ２）の最初の１６ビットは、ロケータ６０２へ同時にシフトされる。これによって、ロケータ６０２に、第１のメインウィンデージセレクタ６０３Ａ（ＳＭＷ（１））を生成させる。シーケンス６０１Ｂおよび６０１Ｃ（Ｍ１およびＭ２）は続いて、すべての３９個（すなわち、５５−１６）の遅延について、パイプラインにされた遅延素子７１２および７１６を介してそれぞれシフトし続ける。
【００６５】
ＡＮＤゲートの行７１０を使用することにより、シーケンス６０１Ｂ（Ｍ１）は、累積(accumulation)するのにベクトル６０１Ａの適切な要素（ＷＺ）だけを活性化する。シーケンス６０１Ｃ（Ｍ２）は、ＸＮＯＲゲートの行７１４を介して、累積の極性(accumulation polarity)を決定する。ベクトル６０１Ａ（ＷＺ）の各要素のすべてのビットを補う(complement)だけでは、２の補数の符号が変わらないことは理解されよう（最下位ビットにおいて１つ足りない）。しかしながら、上記のように、これらの要素を、いくつかの最下位ビットで埋める(pad)ことにより、このエラーが最小にされる。
【００６６】
シーケンス６０１Ｂ（Ｍ１）には、隣接する「１」がないことに注意されたい（式ＩＸを参照）。こうして、図示された実施形態では、第１のレベルの合計は、ＯＲゲートの行７０８が示す簡単なＯＲ機能で行われる。４つのレベルの合計のカスケード（ＯＲゲートの行７０８、および、加算器７０６、７０４、７０２の３つの行によって表される）は結局、各遅延ｊについて１つずつ、メインウィンデージセレクタ６０３Ａ（ＳＭＷ（ｊ））の３９個の値を生成する。
【００６７】
ウィンデージ用の粗いメインロケータ６０２は、メインウィンデージセレクタ値６０３Ａ（ＳＭＷ（ｊ））を、粗い位置データ生成装置６１０に出力する（図６）。粗い位置データ生成装置６１０は、メインウィンデージセレクタ値６０３Ａ（ＳＭＷ（ｊＭＷ））の現在の最大値を、最大が生じたときの値ｊＭＷと共に、追跡して記録する。
【００６８】
図８は、本発明の一実施形態による、図６のブロック図で示すウィンデージ用の粗いデミロケータ６０４の主要構成要素を示す概略図である。ウィンデージ用の粗いデミロケータ６０４は、水平ターゲットグリッド（格子）間の中間の近くに存在する画像の位置を効果的に突き止める。図８に示すように、ウィンデージ用の粗いデミロケータ６０４は、加算器８０２、加算器の行８０４、加算器の行８０６、加算器の行８０８、ＡＮＤゲートの行８１０、遅延素子（Ｄ）の行８１２、ＸＮＯＲゲートの行８１４、遅延素子の行８１６を含む。
【００６９】
ウィンデージ用の粗いデミロケータ６０４は、図７を参照して上述したウィンデージ用の粗いメインロケータ６０２と同じ様に動作するが、ロケータ６０２のようにメインシーケンス６０１Ｂおよび６０１Ｃ（Ｍ１とＭ２）を使用するのではなく、２つのｄｅｍｉシーケンス６０１Ｄおよび６０１Ｅ（ｄｅｍｉ１とｄｅｍｉ２）を使用して、合計するのにゼロ平均ウィンデージベクトル６０１Ａ（ＷＺ）の適切な要素をイネーブルし、該合計の符号を制御する。第１のメインシーケンス６０１Ｂ（Ｍ１）と異なり、第１のｄｅｍｉシーケンス６０１Ｄ（ｄｅｍｉ１）の２つの隣接した値は、両方とも非ゼロでありうる（式ＸＩを参照）。したがって、第１の合計レベルは、図７に示すＯＲゲートの行７０８ではなく、加算器の行８０８として示される。
【００７０】
新しいデミウィンデージセレクタ値６０３Ｂ（ＳＤＷ（ｊ））は、図７に関して上述した方法と同じ方法で、各遅延シフトと共に生成され、各遅延ｊについて１つずつ、合計で３９個のデミウィンデージセレクタ値６０３Ｂ（ＳＤＷ（ｊ））が生成される。ウィンデージ用の粗いデミロケータ６０４はデミウィンデージセレクタ値６０３Ｂ（ＳＤＷ（ｊ））を、粗い位置データ生成装置６１０に出力する（図６）。粗い位置データ生成装置６１０は、デミウィンデージセレクタ値６０３Ｂ（ＳＤＷ（ｊＤＷ））の現在の最大値を、最大が生じた時の値ｊＤＷと共に、追跡して記録する。
【００７１】
図９は、本発明の一実施形態による、図６のブロック図で示したエレベーション用の粗いメインロケータ６０６の主要構成要素を示す概略図である。エレベーション用の粗いメインロケータ６０６は、垂直ターゲットグリッド（格子）から垂直に大幅にオフセットされていない画像の位置を効果的に突き止めることができる。図９に示すように、エレベーション用の粗いメインロケータ６０６は、加算器９０２、加算器の行９０４、加算器の行９０６、ＯＲゲートの行９０８、ＡＮＤゲートの行９１０、遅延（Ｄ）素子の行９１２、ＸＮＯＲゲートの行９１４、遅延素子の行９１６を含む。
【００７２】
エレベーション用の粗いメインロケータ６０６は、図７に示すウィンデージ用の粗いメインロケータ６０２と同じ様に構成されるが、ウィンデージ用の粗いメインロケータ６０２が、ゼロ平均ウィンデージベクトル６０１Ａ（ＷＺ）に対して作用するのに対し、エレベーション用の粗いメインロケータ６０６は、ゼロ平均エレベーションベクトル６０１Ｆ（ＶＺ）に作用する。
【００７３】
新しいメインエレベーションセレクタ値６０３Ｃ（ＳＭＶ（ｊ））は、各遅延シフトと共に生成され、各遅延ｊについて１つずつ、合計で３９個のメインエレベーションセレクタ値６０３Ｃ（ＳＭＶ（ｊ））が生成される。エレベーション用の粗いメインロケータ６０６は、メインエレベーションセレクタ値６０３Ｃ（ＳＭＶ（ｊ）を、粗い位置データ生成装置６１０に出力する（図６）。粗い位置データ生成装置６１０は、メインエレベーションセレクタ値６０３Ｃ（ＳＭＶ（ｊＭＶ））の現在の最大値を、最大が生じた時の値ｊＭＶと共に、追跡して記録する。
【００７４】
図１０は、本発明の一実施形態による、図６のブロック図で示されたエレベーション用の粗いデミロケータ６０８の主要構成要素を示す概略図である。エレベーション用の粗いデミロケータ６０８は、垂直ターゲットグリッド（格子）間の中間近くにある画像の位置を効果的に突き止める。図１０に示すように、エレベーション用の粗いデミロケータ６０８は、加算器１００２、加算器の行１００４、加算器の行１００６、加算器の行１００８、ＡＮＤゲートの行１０１０、遅延（Ｄ）素子の行１０１２、ＸＮＯＲゲートの行１０１４、遅延素子の行１０１６を含む。
【００７５】
エレベーション用の粗いデミロケータ６０８は、図８に示すウィンデージ用の粗いデミロケータ６０４と同じ様に構成されるが、ウィンデージ用の粗いデミロケータ６０４は、ゼロ平均ウィンデージベクトル６０１Ａ（ＷＺ）に作用するのに対し、エレベーション用の粗いデミロケータ６０８は、ゼロ平均エレベーションベクトル６０１Ｆ（ＶＺ）に作用する。
【００７６】
新しいデミエレベーションセレクタ値６０３Ｄ（ＳＤＶ（ｊ））は、遅延シフトと共に生成され、各遅延ｊについて１つずつ、合計で３９個のデミエレベーションセレクタ値６０３Ｄ（ＳＤＶ（ｊ））を生成する。エレベーション用の粗いデミロケータ６０８は、デミエレベーションセレクタ値６０３Ｄ（（ＳＤＶ（ｊ））を、粗い位置データ生成装置６１０に出力する（図６）。粗い位置データ生成装置６１０は、デミエレベーションセレクタ値６０３Ｄ（ＳＤＶ（ｊＤＶ））の現在の最大値を、最大が生じたときの値ｊＤＶと共に、追跡して記録する。
【００７７】
一実施形態では、粗い位置特定処理は、非ゼロ平均ウィンデージベクトルおよびエレベーションベクトルを使用して達成される。このプロセスでは、ベクトル全体の平均Ｖａｖｇ（式ＩＩＩ）と各遅延内のサブセットコードの合計との積に等しい項を、セレクタ値から引く。該積は、Ｍ１ベクトルおよびＭ２ベクトル（またはｄｅｍｉ１およびｄｅｍｉ２）がすべての遅延を介してシフトする際に、Ｍ１ベクトルおよびＭ２ベクトルによってダイナミックに制御されるアキュムレータによって生成され、こうして、ウィンデージ値（またはエレベーション）Ｖａｖｇを累積する。
【００７８】
一実施形態では、図７から図１０に示される４つのロケータ６０２、６０４、６０６、６０８は、同時に動作してセレクタ値６０３Ａ、６０３Ｂ、６０３Ｃ、６０３Ｄをそれぞれ生成する。ロケータ６０２、６０４、６０６、６０８がすべてのセレクタ値６０３Ａ、６０３Ｂ、６０３Ｃ、６０３Ｄを生成すると、粗い位置生成装置６１０は、セレクタ値６０３Ａ（ＳＭＷ（ｊＭＷ））の最大値、セレクタ値６０３Ｂ（ＳＤＷ（ｊＤＷ））の最大値、セレクタ値６０３Ｃ（ＳＭＶ（ｊＭＶ））の最大値、セレクタ値６０３Ｄ（ＳＤＶ（ｊＤＶ））の最大値を識別したことになる。本発明の一形態では、粗い位置データ生成装置６１０は、セレクタ値６０３Ａ（ＳＭＷ（ｊＭＷ））の最大値およびセレクタ値６０３Ｂ（ＳＤＷ（ｊＤＷ））の最大値×０．７０７１の比較に基づいて、粗いウィンデージ位置を決定し、セレクタ値６０３Ｃ（ＳＭＶ（ｊＭＶ））の最大値およびセレクタ値６０３Ｄ（ＳＤＶ（ｊＤＶ））の最大値×０．７０７１の比較に基いて、粗いエレベーション位置を決定する。
【００７９】
ウィンデージセレクタ値６０３Ａ（ＳＭＷ（ｊＭＷ））および６０３Ｂ（ＳＤＷ（ｊＤＷ））の最大値に加えて、粗いウィンデージ位置を決定するために使用されるもう１つの情報ビット（ＱＷ）がある。一実施形態では、粗い位置データ生成装置６１０は、ウィンデージセレクタ値６０３Ｂ（ＳＤＷ（ｊＭＷ））の最大値を、該最大値の直前のウィンデージセレクタ値６０３Ｂ（すなわちＳＤＷ（ｊＭＷ−１））と比較する。ＳＤＷ（ｊＭＷ）がＳＤＷ（ｊＭＷ−１）より大きい場合、粗い位置データ生成装置６１０は、変数ＱＷに「０」の値を割り当てる。ＳＤＷ（ｊＭＶ）がＳＤＷ（ｊＭＷ−１）より小さい場合、粗い位置データ生成装置６１０は、変数ＱＷに「−１」の値を割り当てる。
【００８０】
粗い位置データ生成装置６１０は、最終的な粗いウィンデージ位置ＬＷを、以下のように確立する。すなわち、（１）最大値ＳＤＷ（ｊＤＷ）／√２が最大値ＳＭＷ（ｊＭＷ）より大きい場合、ｊＤＷ＜ＬＷ＜ｊＤＷ＋１、（２）最大値ＳＭＷ（ｊＭＷ）が最大値ＳＤＷ（ｊＤＷ）／√２より大きい場合、ｊＭＷ＋ＱＷ＜ＬＷ＜ｊＭＷ＋ＱＷ＋１。
【００８１】
エレベーションセレクタ値６０３Ｃ（ＳＭＶ（ｊＭＶ））および６０３Ｄ（ＳＤＶ（ｊＤＶ））の最大値に加えて、粗いエレベーション位置を決定するために使用されるもう１つの情報ビット（ＱＶ）がある。一実施形態では、粗い位置データ生成装置６１０は、エレベーションセレクタ値６０３Ｄ（ＳＤＶ（ｊＭＶ））の最大値を、該最大値の直前（すなわちＳＤＶ（ｊＭＶ−１））のウィンデージセレクタ値６０３Ｄと比較する。ＳＤＶ（ｊＭＶ）がＳＤＶ（ｊＭＶ−１）より大きい場合、粗い位置データ生成装置６１０は、変数ＱＶに「０」の値を割り当てる。ＳＤＶ（ｊＭＶ）がＳＤＶ（ｊＭＶ−１）より小さい場合、粗い位置データ生成装置６１０は、変数ＱＶに「−１」の値を割り当てる。
【００８２】
粗い位置データ生成装置６１０は、最終的な粗いエレベーション位置（Ｌｖ）を、以下のように確立する。（１）最大値ＳＤＶ（ｊＤＶ）／√２が最大値ＳＭＶ（ｊＭＶ）より大きい場合、ｊＤＶ＜ＬＶ＜ｊＤＶ＋１、（２）最大値ＳＭＶ（ｊＭＶ）が最大値ＳＤＶ（ｊＤＶ）／√２より大きい場合、ｊＭＶ＋ＱＶ＜ＬＶ＜ｊＭＶ＋ＱＶ＋１。
【００８３】
デミセレクタＳＤＷ（ｊＤＷ）およびＳＤＶ（ｊＤＶ）が、係数「１／√２」により乗算された後で、メインセレクタＳＭＷ（ｊＭＷ）およびＭＶ（ｊＭＶ）とそれぞれ比較されることに注意されたい。この理由は、デミセレクタは、２つの直交ベクトルの和を表すので、デミセレクタは、メインセレクタよりも２の平方根大きいためである。
【００８４】
上に定義された粗い位置特定プロセスを使用して、粗い位置データ生成装置６１０により、粗いウィンデージＬＷおよび粗いエレベーションＬＶの両方の位置が、１ピクセル内で特定される。座標ＬＷおよびＬＶは、ターゲット１０６Ａの原点に対するターゲット１０６Ａの撮像された部分の粗い絶対位置の下限を、１ピクセル内に提供する。本発明の一形態では、細かい位置データ生成装置６１２はさらに、位置を、ピクセルの何分の一の精度まで狭めることができる。生成装置６１２が算出するλｗおよびλｖと呼ばれるピクセルの小数部分（ピクセルの何分の一の部分）を、ＬＷおよびＬＶにそれぞれ加算し、２次元で細かい絶対位置を生成する。
【００８５】
図１に示すサンプル画像３１２の粗い位置特定プロセスを、図１１と図１２に示す。図１１は、本発明の一実施形態による、画像３１２のエレベーション用の粗いセレクタ６０３Ｃおよび６０３Ｄ（ＳＭＶ（ｊ）とＳＤＶ（ｊ））のグラフを示す図である。図１１の縦軸はセレクタの値を表わし、水平軸は遅延数ｊを表す。グラフ１１０２は、４０個の遅延ｊすべてについてのメインエレベーションセレクタ値６０３Ｃ（ＳＭＶ（ｊ））のグラフである。グラフ１１０４は、４０個の遅延ｊのすべてについて２の平方根で除算した、デミエレベーションセレクタ値６０３Ｄ（ＳＤＶ（ｊ））のグラフである。図１１に示すグラフに現れる最大値は、メインエレベーションセレクタの第４の遅延ＳＭＶ（４）である。これは、参照番号１１０６で示されている。画像３１２は、ターゲットグリッドからまったくオフセットされておらず、ターゲットグリッドとアライメントされているため、デミエレベーションセレクタ値６０３Ｄ（ＳＤＶ（ｊ））は位置特定に寄与しておらず、よって粗いエレベーションＬＶは「４」に等しい。
【００８６】
図１２は、本発明の一実施形態によるウィンデージ用の粗いセレクタ６０３Ａおよび６０３Ｂ（ＳＭＷ（ｊ）とＳＤＷ（ｊ））を示すグラフである。図１２の縦軸は、セレクタの値を表わし、水平軸は遅延数ｊを表す。グラフ１２０２は、４０個の遅延ｊのすべてについてのメインウィンデージセレクタ値６０３Ａ（ＳＭＷ（ｊ））のグラフである。グラフ１２０４は、４０個の遅延ｊのすべてについての、２の平方根で除算したデミウィンデージセレクタ値６０３Ｂ（ＳＤＷ（ｊ））のグラフである。
【００８７】
図１２のグラフに現れる最大値は、メインウィンデージセレクタの第３５番目の遅延ＳＭＷ（３５）である。これは、参照番号１２０６によって示されている。画像３１２は、ターゲットグリッドからまったくオフセットされず、ターゲットグリッドとアライメントされているので、デミウィンデージセレクタ値６０３Ｂ（ＳＤＷ（ｊ））は位置特定に寄与しておらず、よって、粗いウィンデージＬＷは「３５」に等しい。こうして、画像３１２が絶対位置（４、３５）に位置することが、突き止められる。
【００８８】
Ｂ  細かい位置 (FINE POSITION)
下記は、本発明の一実施形態による、細かい位置データ生成装置６１２（図６）が行う細かい位置決定プロセスの説明である。一実施形態では、ウィンデージおよびエレベーションについて同じプロセスを使用するので、細かいウィンデージ決定についてだけ説明する。上記の粗い位置決定の後、画像位置を、Ｍ３（式ＶＩ）の２つの連続したオーバーラップする１６要素ベクトルの間に入れ(bracketed)、合計で１７個の（３値）要素を作成する。Ｍ３の１７個の選択された要素は、Ｍ１（式ＩＸ）およびＭ２（式Ｘ）内の２つの１７要素のバイナリベクトルに対応する。Ｍ１およびＭ２の選択されたサブセットは、ＭＳ１およびＭＳ２とそれぞれラベリングされ、ここで、「Ｓ」は「選択された」の意味である。ウィンデージについて選択されたサブセットは、ＭＳ１ＷおよびＭＳ２Ｗであり、エレベーションについて選択されたサブセットは、ＭＳ１ＶおよびＭＳ２Ｖである。本発明の一形態では、粗い位置データ生成装置６１０が、ＭＳ１Ｗ  ６１１Ａ（図６）、ＭＳ２Ｗ  ６１１Ｂ、ＭＳ１Ｖ  ６１１Ｃ、ＭＳ２Ｖ  ６１１Ｄを求め、これらの４つのベクトルを、細かい位置データ生成装置６１２に出力する。図６に示すように、細かい位置データ生成装置６１２はまた、ウィンデージベクトル３１８（Ｗ）およびエレベーションベクトル３１４（Ｖ）を受け取る。
【００８９】
図３に示すように、一般に、捕捉された画像３１２は、通常、ターゲットピクセル線に正確に沿った位置にはない。このような場合、ウィンデージ次元における画像３１２の位置はさらに、１ターゲットピクセルをフラクション(fraction, 該ピクセルの何分かの一)６１３Ａ（λＷ）に細かくすると共に（すなわち０≦λＷ＜１）、エレベーション次元の１ターゲットピクセルをフラクション６１３Ｂ（λＶ）に細かくすることができる。粗い位置プロセスから、ウィンデージ位置が、第３５番目の遅延と第３６番目の遅延の間に位置すると判断された、と仮定する（すなわち、画像３１２は、図３に示された位置から、ピクセルの何分の一（フラクション）だけ右にオフセットされている）。このフラクションλＷは、第３５番目の遅延と第３６番目の遅延にそれぞれ対応する既知の選択されたベクトルＭＳ１ＷおよびＭＳ２Ｗを使用して、線形回帰(linear regression)によって推定されることができる。
【００９０】
一実施形態では、細かい位置決定プロセスは、ウィンデージ次元およびエレベーション次元で同じである。したがって、以下の説明では、選択したベクトルＭＳ１およびＭＳ２、および、ピクセルのフラクション位置λについては、下付き文字Ｗおよび下付き文字Ｖは使用しない。以下の説明および式は、ウィンデージ次元およびエレベーション次元の両方に適用可能であることが理解されよう。
【００９１】
計算されたウィンデージベクトル（Ｗ）と、白ピクセル、灰色ピクセル、黒ピクセルについての未知のセンサ記録値との間の関係は、次の式ＸＩＩＩによって与えられる。
【００９２】
式  ＸＩＩＩ
［ｗ１，ｗ２，ｗ３，ｗ４，ｗ５，ｗ６，ｗ７，ｗ８，ｗ９，ｗ１０，ｗ１１，ｗ１２，ｗ１３，ｗ１４，ｗ１５，ｗ１６］＝（１−λ）・［ｗ，ｇ，ｂ，ｇ，ｇ，ｇ，ｇ，ｇ，ｗ，ｇ，ｂ，ｇ，ｇ，ｇ，ｇ，ｇ］＋λ・［ｇ，ｂ，ｇ，ｇ，ｇ，ｇ，ｇ，ｗ，ｇ，ｂ，ｇ，ｇ，ｇ，ｇ，ｇ，ｗ］
【００９３】
ここで、ｗ１、ｗ２、…ｗ１６は、ウィンデージベクトル（Ｗ）の計算された値である。λは、ピクセルのフラクション位置である。ｗは、白ピクセルについての未知のセンサ記録値である。ｇは、灰色ピクセルについての未知のセンサ記録値である。ｂは、黒ピクセルについての未知のセンサ記録値である。
【００９４】
一実施形態では、ウィンデージベクトルＷではなくゼロ平均ウィンデージベクトルＷＺを、式ＸＩＩＩで使用する。細かい位置回帰プロセスは、平均値の影響を受けない。
【００９５】
式ＸＩＩＩに定義された関係は、４つの未知数を伴う１６個の式に拡張されることができる。本発明の一形態では、ベストフィット（最良にフィットする）解は、線形回帰によって提供される。本発明の一実施形態は、ほとんど計算を使用しないブロック回帰(Block Regression)と呼ばれる線形回帰の特殊な形式を使う。大部分の計算は、高速デジタルハードウェアアキュムレータとカウンタで実現されることができる。
【００９６】
ブロック回帰プロセスの一形態では、まず１６個の式のうち同じタイプの式を合計することにより５つの式に低減する。この方法で式を合計すると、プロセスの複雑さが低減され、データノイズが平均化される。したがって、同じタイプの式を合計することによって、式ＸＩＩＩは、次の式ＸＩＶによって与えられる形式に書き直されることができる。
【００９７】
式  ＸＩＶ
［ｗ８＋ｗ１６，ｗ１＋ｗ９，ｗ２＋ｗ１０，ｗ３＋ｗ１１，ｗ４＋ｗ５＋ｗ６＋ｗ７＋ｗ１２＋ｗ１３＋ｗ１４＋ｗ１５］＝（１−λ）・［２ｇ，２ｗ，２ｇ，２ｂ，８ｇ］＋λ・［２ｗ，２ｇ，２ｂ，２ｇ，８ｇ］
ここで、ｗ１、ｗ２、…ｗ１６は、計算されたウィンデージベクトルの値（Ｗ）である。λは、ピクセルのフラクションの位置である。ｗは、白ピクセルについての未知のセンサ記録値である。ｇは、灰色ピクセルについての未知のセンサ記録値である。ｂは、黒ピクセルについての未知のセンサ記録値である。
【００９８】
本発明の一形態では、式の合計は、図１３に示す回路によって自動的に達成される。図１３は、本発明の一実施形態による、ＳＵＭおよびＮＵＭパラメータ生成装置１３００を示すブロック図である。一実施形態では、パラメータ生成装置１３００は、細かい位置データ生成装置６１２（図６）の一部である。パラメータ生成装置１３００は、５つのアキュムレータ１３１４、１３１６、１３１８、１３５０、１３５２、５つのカウンタ１３２０、１３２２、１３２４、１３５４、１３５６、３つのＡＮＤゲート１３２８、１３３０、１３３２、ＡＮＤゲートの入力における４つのインバータ１３３４、１３３６、１３３８、１３４０、および、２つの遅延（Ｄ）素子１３４４、１３４８を含む。
【００９９】
パラメータ生成装置１３００への入力は、非ゼロ平均ウィンデージベクトル１３２６（Ｗ）と、２つの１７ビットの選択されたバイナリターゲットベクトル１３４２および１３４６（ＭＳ１およびＭＳ２）を含む。パラメータ生成装置１３００の出力は、５つの合計１３０２、１３０４、１３０６、１３５８、１３６０（本明細書ではそれぞれ、ＳＵＭＩ、ＳＵＭＶ、ＳＵＭＩＩ、ＳＵＭＩＩＩ、ＳＵＭＩＶとも呼ぶ）、および、５つの数、すなわち「ｎｕｍｓ」１３０８、１３１０、１３１２、１３６２、１３６４（本明細書ではそれぞれ、ＮＵＭＩＩ、ＮＵＭＶ、ＮＵＭＩ、ＮＵＭＩＶ、ＮＵＭＩＩＩとも呼ぶ）を含む。
【０１００】
ウィンデージベクトル１３２６（Ｗ）は、５つのアキュムレータ１３１４、１３１６、１３１８、１３５０、１３５２のそれぞれにシフトされる。選択されたバイナリターゲットベクトル１３４２および１３４６（ＭＳ１およびＭＳ２）のそれぞれの１７ビットは、パラメータ生成装置１３００に同時にシフトされる。任意の所与の時に、各ベクトル１３４２および１３４６の２つのシーケンシャルな要素が、遅延素子１３４４および１３４８によってそれぞれ分離される。各クロックサイクルの間、ベクトル１３４２および１３４６（ＭＳ１およびＭＳ２）の４つのビット、すなわちＭＳ１（ｊ）、ＭＳ１（ｊ−１）、ＭＳ２（ｊ）、ＭＳ２（ｊ−１）が現れる。ここで、ｊは、選択されたバイナリターゲットベクトル１３４２および１３４６（ＭＳ１およびＭＳ２）のビットを識別するインデックスである。インデックスｊは、粗い位置データ生成装置６１０によって決定される値から開始して、１６クロック長にわたる。現れる４ビットの論理組み合わせは、遷移タイプ（たとえば、灰色から白、白から灰色、灰色から黒、黒から灰色、灰色から灰色）を識別し、５つのアキュムレータ１３１４、１３１６、１３１８、１３５０、１３５２および５つのカウンタ１３２０、１３２２、１３２４、１３５４、１３５６のクロックを選択的にイネーブルまたはディスエーブルし、合計で１０の値１３０２、１３０４、１３０６、１３５８、１３６０、１３０８、１３１０、１３１２、１３６２、１３６４を生成する。
【０１０１】
ＡＮＤゲート１３２８は、ＭＳ１（ｊ）および反転（インバート）されたＭＳ２（ｊ）を受け取り、ＡＮＤゲート１３２８の出力が「高」のとき（第１の遷移タイプに対応する）、アキュムレータ１３１４およびカウンタ１３２４をイネーブルする。ＡＮＤゲート１３３０は、反転されたＭＳ１（ｊ）および反転されたＭＳ１（ｊ−１）を受け取り、ＡＮＤゲート１３３０の出力が「高」のとき（第５の遷移タイプに対応する）、アキュムレータ１３１６およびカウンタ１３２２をイネーブルする。ＡＮＤゲート１３３２は、ＭＳ１（ｊ−１）および反転されたＭＳ２（ｊ−１）を受け取り、ＡＮＤゲート１３３２の出力が「高」のとき（第２の遷移タイプに対応する）、アキュムレータ１３１８およびカウンタ１３２０をイネーブルする。ＭＳ２（ｊ−１）が「高」のとき（第４の遷移タイプに対応する）、アキュムレータ１３５２およびカウンタ１３５４がイネーブルされる。ＭＳ２（ｊ）が「高」のとき（第３の遷移タイプに対応する）、アキュムレータ１３５０およびカウンタ１３５６がイネーブルされる。
【０１０２】
次の表２は、左から右のピクセル遷移の５つの可能なタイプＩからＶと、これに対応する遷移に関する論理イネーブル式を示す。
【０１０３】
（表２）
タイプ 遷移 論理イネーブル式
I          gからw      Type I Enable = MS1(j) AND NOT MS2(j)
II         wからg      Type II Enable = MS1(j-1) AND NOT MS2(j-1)
III        gからb      Type III Enable = MS2(j)
IV         bからg      Type IV Enable = MS2(j-1)
V          gからg      Type V Enable = NOT MS1(j) AND NOT MS1(j-1)
【０１０４】
表２に示す５つのタイプの遷移は、５つのカウンタ１３２０、１３２２、１３２４、１３５４、１３５６のクロックをイネーブルし、５つの数１３０８、１３１０、１３１２、１３６２、１３６４をそれぞれ生成する。同じ遷移は、５つのアキュムレータ１３１４、１３１６、１３１８、１３５０、１３５２のクロックをイネーブルし、ウィンデージベクトル１３２６（Ｗ）の要素を累積し、これによって、５つの合計１３０２、１３０４、１３０６、１３５８、１３６０をそれぞれ生成する。
【０１０５】
生成装置１３００では、ウィンデージベクトル（Ｗ）の代わりにゼロ平均ウィンデージベクトル（ＷＺ）を使用することもできる。エレベーションについてのＮＵＭおよびＳＵＭパラメータ１３０８、１３１０、１３１２、１３６２、１３６４、１３０２、１３０４、１３０６、１３５８、１３６０を生成するために、ウィンデージベクトル１３２６（Ｗ）を、エレベーションベクトル（Ｖ）またはゼロ平均エレベーションベクトル（ＶＺ）で置き換える。上記の説明は、５５×５５ピクセルのターゲット１０６Ａ（図３）が使用されていると仮定している。７１１×７１１ピクセルのターゲット１０６Ｂ（図４Ａ）についても同じ回路１３００が使用できるが、現在のインデックスｊが３２個の値に及んで、ウィンデージベクトル１３２６（Ｗ）の３２要素を全部使う点が異なる。本発明の一形態による、５つのＳＵＭパラメータ１３０２、１３０４、１３０６、１３５８、１３６０、および、５つのＮＵＭパラメータ１３０８、１３１０、１３１２、１３６２、１３６４を生成するパラメータ生成装置１３００の動作は、次の擬似コード例Ｉによってコンピュータ擬似コードで表わされる。
【０１０６】
擬似コード例Ｉ
Ｆｏｒ  ｉ＝１  ｔｏ  ３２
ｉｆ  Ｔｙｐｅ（ｉ）＝Ｉ，ＳｕｍＩ＝ＳｕｍＩ＋Ｗ（ｉ）
ＮｕｍＩ＝ＮｕｍＩ＋１
ｉｆ  Ｔｙｐｅ（ｉ）＝ＩＩ，ＳｕｍＩＩ＝ＳｕｍＩＩ＋Ｗ（ｉ）
ＮｕｍＩＩ＝ＮｕｍＩＩ＋１
ｉｆ  Ｔｙｐｅ（ｉ）＝ＩＩＩ，ＳｕｍＩＩＩ＝ＳｕｍＩＩＩ＋Ｗ（ｉ）
ＮｕｍＩＩＩ＝ＮｕｍＩＩＩ＋１
ｉｆ  Ｔｙｐｅ（ｉ）＝ＩＶ，ＳｕｍＩＶ＝ＳｕｍＩＶ＋Ｗ（ｉ）
ＮｕｍＩＶ＝ＮｕｍＩＶ＋１
ｉｆ  Ｔｙｐｅ（ｉ）＝Ｖ，ＳｕｍＶ＝ＳｕｍＶ＋Ｗ（ｉ）
ＮｕｍＶ＝ＮｕｍＶ＋１
Ｅｎｄ  ｌｏｏｐ  ｉ
【０１０７】
本発明の一形態では、細かい位置データ生成装置６１２は、パラメータ生成装置１３００により生成された５つのＮＵＭおよび５つのＳＵＭパラメータ１３０８、１３１０、１３１２、１３６２、１３６４、１３０２、１３０４、１３０６、１３５８、１３６０から、ピクセルのフラクション位置（λ）を求める。図１４は、本発明の一実施形態による、ピクセルのフラクション位置（λ）を求める方法１４００を示すフロー図である。一実施形態では、細かい位置データ生成装置６１２は、方法１４００を実行するように構成される。
【０１０８】
方法１４００の１４０１において、上記の式ＸＩＩＩにより定義される１６個の式のうち、同じタイプの式を合計することにより、５つの等式（式ＸＩＶ）に低減する。本発明の一形態では、１４０１での式の低減は、図１３に示すパラメータ生成回路１３００が行う（すなわち、一実施形態では、式は、ハードウェアの「タイピング(typing)」によって低減される）。
【０１０９】
方法１４００の１４０２は、「灰色(GREY)」ステップと呼ばれ、細かい位置データ生成装置６１２は、式ＸＩＶの未知のグレーレベルｇを求める。一実施形態では、生成装置６１２は、次の式ＸＶに基づいて、未知のグレーレベルｇを確立する。
【０１１０】
式  ＸＶ
ｇ＝ＳＵＭＶ／ＮＵＭＶ
一実施形態によれば、式ＸＶ中の除数は、２、３、４、５、６、７、または８である。
【０１１１】
１４０４は、「均等（EVEN-UP）」ステップと呼ばれ、細かい位置データ生成装置６１２は、１４０２で求めたグレーレベルの値ｇを使用して、上記の式ＸＩＶで定義された５つの式を、４つの式に低減する。一実施形態では、４つの式は、次の式ＸＶＩ−ＸＩＸによって与えられる。
【０１１２】
式  ＸＶＩ
ＳＵＭＩ＝ＳＵＭＩ−ｇ・ＮＵＭ１
式  ＸＶＩＩ
ＳＵＭＩＩ＝ＳＵＭＩＩ−ｇ・ＮＵＭＩＩ
式  ＸＶＩＩＩ
ＳＵＭＩＩＩ＝ＳＵＭＩＩＩ−ｇ・ＮＵＭＩＩＩ
式  ＸＩＸ
ＳＵＭＩＶ＝ＳＵＭＩＩ−ｇ・ＮＵＭＩＶ
【０１１３】
１４０６は、「一致（MATCHING）」ステップと呼ばれ、細かい位置データ生成装置６１２は、ＮＵＭＩをＮＵＭＩＩに、ＮＵＭＩＩＩをＮＵＭＩＶに等しくする。この擬似コード例ＩＩを示す。
【０１１４】
擬似コード例ＩＩ
【数２】
2006300939.tif 000005
【０１１５】
１４０８は、「分離（ISOLATING）」ステップと呼ばれ、細かい位置データ生成装置６１２は、次の式ＸＸおよびＸＸＩに基づいて、式ＸＩＶに対応する行列中の不要の係数を消去する。
【０１１６】
式  ＸＸ
ＳＵＭＩＩ＝ＳＵＭＩ＋ＳＵＭＩＩ
式  ＸＸＩ
ＳＵＭＩＶ＝ＳＵＭＩＩＩ＋ＳＵＭＩＶ
１４１０は、「ラムダ（LAMBDA）」ステップと呼ばれ、細かい位置データ生成装置６１２は、ピクセルのフラクション位置λを計算する。これを、次の式ＸＸＩＩに示す。
【０１１７】
式  ＸＸＩＩ
λ＝（ＳＵＭＩ−ＳＵＭＩＩＩ）／（ＳＵＭＩＩ−ＳＵＭＩＶ）
１４１２は「光強度（LIGHT INTENSITIES）」ステップと呼ばれ、細かい位置データ生成装置６１２は、式ＸＩＶにおいて、残りの未知の光レベルｗおよびｂを計算する。これらの光レベルの算出は、位置補間に必要ではないが、次の式ＸＸＩＩＩとＸＸＩＶに示すように、明らかになったピクセルのフラクション位置λ（式ＸＸＩＩから求まる）と最新に更新された数を使用して、達成されることができる。
【０１１８】
式  ＸＸＩＩＩ
【数３】
2006300939.tif 000006
【０１１９】
式  ＸＸＩＶ
【数４】
2006300939.tif 000007
【０１２０】
まとめると、本発明の一形態では、それぞれの捕捉された画像３１２を低減して、次の式ＸＸＶ（１０の既知の数ＳＵＭＩ〜ＳＵＭＶおよびＮＵＭＩ〜ＮＵＭＶを伴う）および４つの未知数（λ、ｇ、ｗ、ｂ）で与えられた形式にすることができる。
【０１２１】
式  ＸＸＶ
［ＳＵＭＩ，ＳＵＭＩＩ，ＳＵＭＩＩＩ，ＳＵＭＩＶ，ＳＵＭＶ］＝（１−λ）・［ＮＵＭＩ・ｇ，ＮＵＭＩＩ・ｗ，ＮＵＭＩＩＩ・ｇ，ＮＵＭＩＶ・ｂ，ＮＵＭＶ・ｇ］＋λ・［ＮＵＭＩ・ｗ，ＮＵＭＩＩ・ｇ，ＮＵＭＩＩＩ・ｂ，ＮＵＭＩＶ・ｇ，ＮＵＭＶ・ｇ］
ここで、
ＳＵＭＩは、パラメータ生成装置１３００により生成されたパラメータ１３０２の値。
ＳＵＭＩＩは、パラメータ生成装置１３００により生成されたパラメータ１３０６の値。ＳＵＭＩＩＩは、パラメータ生成装置１３００により生成されたパラメータ１３５８の値。
ＳＵＭＩＶはパラメータ生成装置１３００により生成されたパラメータ１３６０の値。
ＳＵＭＶは、パラメータ生成装置１３００により生成されたパラメータ１３０４の値。
ＮＵＭＩは、パラメータ生成装置１３００により生成したパラメータ１３１２の値。
ＮＵＭＩＩは、パラメータ生成装置１３００により生成されたパラメータ１３０８の値。ＮＵＭＩＩＩは、パラメータ生成装置１３００により生成されたパラメータ１３６４の値。
ＮＵＭＩＶは、パラメータ生成装置１３００により生成されたパラメータ１３６２の値。ＮＵＭＶは、パラメータ生成装置１３００により生成されたパラメータ１３１０の値。
λは、ピクセルのフラクション位置。
ｗは、白ピクセルについての未知のセンサ記録値。ｇは、灰色ピクセルについての未知のセンサ記録値。ｂは、黒ピクセルについての未知のセンサ記録値。
【０１２２】
式ＸＸＶは、ウィンデージ次元およびエレベーション次元のどちらにも適用可能である。行列表記では、式ＸＸＶに対応する式セットは、次の式ＸＸＶＩに与えられる。
【０１２３】
式  ＸＸＶI
【数５】
2006300939.tif 000008
【０１２４】
一実施形態では、細かい位置データ生成装置６１２は、方法１４００を実行し、式ＸＸＶＩで定義された５つの式の組から４つの未知数すべてを解く。
【０１２５】
図１５は、本発明の一実施形態による、図１４に示す方法１４００を使用して、例としてのウィンデージベクトル（Ｗ）についてのピクセルのフラクション位置λを求める方法を示す図である。例としてのウィンデージベクトル（Ｗ）は、ターゲット１０６Ａの中央部分３１６Ａ（ｃｃｃ）の右側の第１の白ピクセルで始まり、小さなオフセット０．０５を伴う、と仮定する。例としてのウィンデージベクトル（Ｗ）には、０．２５ＲＭＳのノイズ項も追加される。ウィンデージベクトル（Ｗ）は、次の式ＸＸＶＩＩによって与えられる。
【０１２６】
式  ＸＸＶＩＩ
Ｗ＝０．９５・［１５，８，１，８，８，１５，８，１，８，８，８，８，８，１５，８，１］＋０．０５・［８，１，８，８，１５，８，１，８，８，８，８，８，１５，８，１，８］＋ｎｏｉｓｅ
【０１２７】
パラメータ生成装置１３００は、上記の式ＸＸＶＩＩに与えられたウィンデージベクトル（Ｗ）に基づいて、図１５のテーブル１５０２Ａの最初の２つの列に与えられた５つのＳＵＭ値および５つのＮＵＭ値を生成する。テーブル１５０２Ａの第３の列から第８の列は、上記の式ＸＸＶＩに与えられた行列に対応する。こうして、テーブル１５０２Ａの第２の列のＮＵＭ値を使用して、式ＸＸＶＩの行列によって定義されるように、テーブル１５０２Ａの第３の列から第８の列を完成させる。「一致しない(UNMATCHED)」という言葉は、テーブル１５０２Ａの右側の行ＩおよびＩＩに現れる。これは、ＮＵＭＩがＮＵＭＩＩに一致しない（すなわち等しくない）ことを示す。「一致した(MATCHED)」という言葉は、テーブル１５０２Ａの右側の行ＩＩＩとＩＶに現れる。これは、ＮＵＭＩＩＩがＮＵＭＩＶに一致していることを示す。一実施形態では、一致していないＮＵＭ値を修正してＮＵＭ値を一致させる。これは、以下に後述される。
【０１２８】
方法１４００を実行している最中、テーブル１５０２Ａの一部の値は変わるが、テーブル１５０２Ａの他の値は同じままである。テーブル１５０２Ａに対する変更は、テーブル１５０２Ｂ、１５０２Ｃ、および１５０２Ｄに示す（本明細書では、テーブル１５０２Ａ〜１５０２Ｄを、集合的にテーブル１５０２と呼ぶ）。図１５に示すように、テーブル１５０２のうち、或るテーブルから次のテーブルの間で変わる値は円で囲み、前のテーブルの値から変わらない値は、円で囲んでいない。
【０１２９】
方法１４００の１４０２では、細かい位置データ生成装置６１２は、式ＸＩＶで未知の灰色（グレー）レベルｇを求める。図１５の１５０４に示すように、上記の式ＸＶを使用して、グレーレベルｇは「８．０１」と算出される。
【０１３０】
方法１４００の１４０４は、「均等(EVEN UP)」ステップと呼ばれ、細かい位置データ生成装置６１２は、１４０２で算出されたグレーレベルの値ｇを使用して、上記の式ＸＩＶで定義された５つの式を４つに低減する。４つの式は、上記の式ＸＶＩからＸＩＸによって与えられる。ＳＵＭ値は、式ＸＶＩからＸＩＸに基づいて、テーブル１５０２Ｂの第１の列に示される値に修正され、テーブルの第５の行は除去される。テーブル１５０２Ｂの第４の列の値も、前のテーブル１５０２Ａの値から変更される。単語「等しい(even)」が、テーブル１５０２Ｂの右側行ＩからＩＶに現れ、これは、「均等」ステップ１４０４が行われたことを示す。
【０１３１】
方法１４００の１４０６は、「一致(MATCHING)」ステップと呼ばれ、細かい位置データ生成装置６１２は、ＮＵＭＩがＮＵＭＩＩに等しく、ＮＵＭＩＩＩがＮＵＭＩＶに等しくなるようにする。これは、上記の擬似コード例ＩＩに示される。一致ステップの後、ＳＵＭＩおよびＮＵＭＩの値は、テーブル１５０２Ｃに示すように変更され、第１の行の第６と第７の列の値も変更される。テーブル１５０２Ｃの行Ｉの右側の「一致した(MATCHED)」という言葉は、ＮＵＭＩが今やＮＵＮＩＩと一致する、ことを示す。
【０１３２】
方法１４００の１４０８は、「分離(ISOLATING)」ステップと呼ばれ、細かい位置データ生成装置６１２は、上記の式ＸＸとＸＸＩに基づいて、式ＸＸＶＩに与えられた行列内の不要な係数を消去する。分離ステップの後に、テーブル１５０２Ｄに示すように、ＳＵＭＩＩおよびＳＵＭＩＶの値は変更される。第２行の第６と第７の列の値、および第４の行の第７と第８の列の値も変更される。テーブル１５０２Ｄの行ＩＩおよびＩＶの右側の「分離された」という言葉は、これらの２つの行が分離され、不要な係数がこれらの２つの行から消去されたことを示す。
【０１３３】
方法１４００の１４１０は、「ラムダ(LAMBDA)」ステップと呼ばれ、細かい位置データ生成装置６１２は、上記の式ＸＸＩＩを使用して、ピクセルのフラクション位置λを計算する。ピクセルのフラクション位置λは、上記の式ＸＸＩＩを使用して「０．０５４」と算出される。これは図１５の１５０６に示される。ピクセルのフラクション位置λを、粗い位置ＬＷに加え、最終的なウィンデージ位置を生成する。
【０１３４】
方法１４００の１４１２は、「光強度(LIGHT INTENSITIES)」ステップと呼ばれ、細かい位置データ生成装置６１２は、上記の式ＸＸＩＩＩおよびＸＸＩＶを使用して、残りの未知の光レベルｗおよびｂを計算する。上記の式ＸＸＩＩＩおよびＸＸＩＶを使用すると、未知の光レベルｗおよびｂは、それぞれ「１５．０７」および「１．２２」と算出される。これは図１５の１５０８に示される。ゼロ平均ベクトルＷＺを使用する場合、λは影響を受けないが、ｇがゼロに近くなりｂが負になるよう、光の値が反映されることとなる。
【０１３５】
こうして、上記のブロック回帰プロセスに基づき、細かい位置データ生成装置６１２は、式ＸＸＶＩの４つの未知の値（λ、ｇ、ｗ、ｂ）を解く。ピクセルのフラクション位置λに対して計算された値（０．０５４）は、仮定されたオフセットの値（０．０５）に非常に近いが、追加されたノイズのために、これらの値は同一ではない。
【０１３６】
本発明の一形態では、捕捉した画像の位置を識別するために埋め込まれた位置コードを使用する従来技術とは異なり、ターゲット全体にわたる各Ｎ×Ｎ画像（たとえば７１１×７１１ピクセルターゲットについて、Ｎ＞２２）が、設計により一意的であるので、このような埋め込まれた位置コードは必要ではなく、よって、画像内でこれらを探索して解読する必要はない。
【０１３７】
本発明の一実施形態で実施されるブロック回帰処理は、十分に冗長なデータに対するベストフィット解を抽出し、残りの相互相関効果を効果的に相殺(neutralize)させることができる。本発明の一実施形態による２ビットバイナリ形態の３レベル（たとえば−１、０、１）ターゲットグレースケールにより、共通のデジタル論理ゲート、カウンタ、アキュムレータを使用した高速の、粗い位置決定およびほとんどの細かい位置決定が可能になる。本発明の実施形態の適度なハードウェア要件により、高スループットで経済的な並列１次元動作が可能になる。本発明の一形態では、二次元の相関を行わずに二次元の絶対位置を求めることができる。
【０１３８】
本発明の一形態では、位置コード化は、各フレームに一体的に含まれている。しかしながら、副産物として、回帰プロセス測定は、平均の灰色−白−黒の強度を測定する。さらに簡単で迅速なコード化のために、これらの値を、あるフレームから別のフレームに使用してもよい。本発明の実施形態で行った回帰処理は、インテリジェントに許容誤差を広げる共に、結果の精度を高め、少数のプロセッサ介入の数学的演算が遅めでも、これを達成することができる。
【０１３９】
本明細書では特定の実施形態を図示し説明したが、当業者であれば、本発明の範囲から離れることなく、本明細書に示し説明した特定の実施形態を種々の代替の実装および／または等価の実装に置き換えられることが理解されるであろう。本出願は本明細書に論じた特定の実施形態の、任意の適応例および変形例もカバーすることを目的としている。したがって、本発明は請求項および請求項の等価物によってのみ制限されることが意図される。
【図面の簡単な説明】
【０１４０】
【図１】本発明の一実施形態による、６自由度に対するステージの「ホーム」ポジションを見つけるためのシステムを示す簡略化した図。
【図２】本発明の一実施形態による、センサを示す簡略化した図。
【図３】本発明の一実施形態による、５５×５５ピクセルの３グレースケール（３値）のターゲットを示す図。
【図４Ａ】本発明の一実施形態による、７１１×７１１ピクセルの３グレースケール（３値）ターゲットを示す図である。
【図４Ｂ】本発明の一実施形態による、図４に示すターゲットの円で囲まれた部分の拡大図を示す図。
【図５】本発明の一実施形態による、５５×５５ピクセルの２グレースケール（２値）のターゲットを示す図である。
【図６】本発明の一実施形態による、図１に示す位置データ生成装置の主要構成要素を示すブロック図。
【図７】本発明の一実施形態による、図６の構成図で示したウィンデージ用の粗いメインロケータの主要構成要素を示すブロック図。
【図８】本発明の一実施形態による、図６の構成図で示したウィンデージ用の粗いデミロケータの主要構成要素を示すブロック図。
【図９】本発明の一実施形態による、図６の構成図で示したエレベーション用の粗いメインロケータの主要構成要素を示すブロック図。
【図１０】本発明の一実施形態による、図６の構成図で示したエレベーション用の粗いデミロケータの主要構成要素を示すブロック図。
【図１１】本発明の一実施形態による、エレベーション用の粗いセレクタのグラフを示す図。
【図１２】本発明の一実施形態による、ウィンデージ用の粗いセレクタのグラフを示す図。
【図１３】本発明の一実施形態による、ＳＵＭおよびＮＵＭのパラメータ生成装置を示すブロック図。
【図１４】本発明の一実施形態による、ピクセルのフラクション位置を求める方法を示すフロー図。
【図１５】本発明の一実施形態による、図１４に示す方法を使用して、たとえばウィンデージベクトルに関するピクセルのフラクション位置の決定を説明する図。
【符号の説明】
【０１４１】
１００  システム
１０１  位置データ生成装置
１０２  センサ
１０６  ターゲットパターン
１０８  対象物
２０２  光源
２０４  イメージセンサチップ
２０６  光学素子
【図１】
2006300939.tif 000009
【図２】
2006300939.tif 000010
【図３】
2006300939.tif 000011
【図４Ａ】
2006300939.tif 000012
【図４Ｂ】
2006300939.tif 000013
【図５】
2006300939.tif 000014
【図６】
2006300939.tif 000015
【図７】
2006300939.tif 000016
【図８】
2006300939.tif 000017
【図９】
2006300939.tif 000018
【図１０】
2006300939.tif 000019
【図１１】
2006300939.tif 000020
【図１２】
2006300939.tif 000021
【図１３】
2006300939.tif 000022
【図１４】
2006300939.tif 000023
【図１５】
2006300939.tif 000024