JP4428766B2 - ナビゲーション位置取得方法 - Google Patents

Description

【０００１】
【発明の属する技術分野】
本発明は、一般的には、センサ・アレイに基づくナビゲーション手法に関するもので、特に、走査装置において使用されるナビゲーション技法に関するものである。
【０００２】
【従来の技術】
センサ・アレイの位置を決定するナビゲーション方式は種々のアプリケーションにおいて使用されている。例えば、走査装置によって捕捉されるイメージを相関させるため、あるいは、マウスのようなカーソル制御デバイスの位置を決定するため、ナビゲーション方式が利用される。
【０００３】
オリジナルのイメージを電子的に形成するスキャナはよく知られている。典型的に、スキャナによって提供される捕捉イメージは、メモリにデジタル形式で記憶されるピクセル・データのアレイである。ひずみのないイメージは、ピクセル・データのアレイへのオリジナルのイメージの忠実なマッピングを必要とする。スキャナは、典型的には、イメージ捕捉プロセスの間、忠実なマッピングの可能性を最大にするため、機械的制約を課す少なくとも１つの手段を含む。
【０００４】
ドラム・スキャナ、フラットベッド・スキャナ、２次元アレイ・スキャナおよびハンド・スキャナは当業界において知られているスキャナの４つのタイプである。ドラム・スキャナは、固定速度で回転する円筒ドラムの表面にオリジナルを付着させる。ドラムの回転の間、ドラムの回転軸と平行する方向にイメージ・センサが動かされる。イメージ・センサの線形変位とドラム上のオリジナルの回転の組み合わせが、オリジナル全体の走査を可能にする。イメージ処理の間のいかなる瞬間においても、オリジナルに対するピクセル・データ・アレイの範囲内の現在位置は、ドラムの角度位置とセンサの並進位置を測定することによって、決定される。オリジナルが正しくドラムに付着される限り、そして、ドラム回転が正しく制御され、センサが線形パスに沿ったその変位において正しく制御される限り、オリジナルに対するピクセル・データ・アレイの位置は固定的である。
【０００５】
フラットベッド・スキャナは、アレーの軸に対して垂直な軸に沿ってオリジナルに対して移動される線形アレイ・センサを含む。従って、１次元におけるセンサの位置は、センサの相対的移動を追跡することによって、把握することができる。垂直方向におけるセンサの位置は、輝度が測定されるべき特定アレイ・エレメントのアドレスを特定することによって暗黙的に決定される。フラットベッド・スキャナの１つの実施形態において、オリジナルが透明なプラテン上に置かれ、センサが、イメージ照射光源と共に、オリジナルに対して反対側のプラテン上に置かれる。オリジナルがプラテンに対して相対的に動かされない限り、ピクセル・データ・アレイは、捕捉されるべきイメージに対して固定される。別の１つの実施形態においては、センサではなくオリジナルが動かされる。この第２の形態の典型はファクシミリ機である。高精度の用紙送りがイメージ捕捉プロセスの間の高度な位置的正確性を提供する。
【０００６】
ドラムおよびフラットベッド・スキャナの利点には、少なくともＡ４の大きさのドキュメントに適応する能力が含まれる。更に、このようなスキャナの中には１回の設定でＡ１用紙を取り扱うことができるものもある。しかしながら、このようなスキャナは、制御、データ記憶およびイメージ操作のためホスト・コンピュータを必要とするので、一般に可搬性はない。
【０００７】
２次元アレイ・スキャナは、機械的符号化制約なしに使用することが可能で、アレイとオリジナルが照射の間静止した状態に保たれることだけを必要とする。感光性エレメントの２次元アレイが、ピクセル・データ・アレイへのオリジナル・イメージのマッピングを直接実行する。しかし、8.5"×11"オリジナルの３００ｄｐｉへの１回でのマッピングは、2500x3300エレメントすなわち8,250,000ピクセルのアレイを持つイメージ・サンサを必要とするので、このようなスキャナはほとんどのアプリケーションにおいてコスト高である。
【０００８】
従来型のハンド・スキャナは、オリジナル上に電子光学センサ・エレメントの線形アレイを移動させることをユーザに求める。移動は手操作による。コンピュータ"マウス"の操作において利用されるようなナビゲーション方法を使用して、アレイ位置情報が決定される。線形センサ・アレイが移動されるにつれて、オリジナルと接触している車輪、ボールおよびローラの回転が検知され、回転の機械的細部に基づいて位置情報が決定される。一般的には、オリジナルと接触する機械的エレメントの表面は、滑らないように、(例えばゴムのような)高い摩擦係数を持つ。走査プロセスの間単一の並進運動自由度を補強するため、堅固な軸によって接続された円筒ローラまたは２つの車輪が使用される場合もある。オリジナルに対する走査方向を固定するため、また、２つの車輪またはローラによって提供される並進運動制約を更に補強するため、直線エッジまたはその他の固定治具がたびたび使用される。それにもかかわらず、位置符号化という技法がスリップおよびスキップの影響を受けやすいものであるので、ピクセル・データ・アレイがオリジナル上のイメージに対応する情報を含まないことが多い。
【０００９】
ハンド・スキャナは、イメージ・データの記憶、処理ならびに使用のため、典型的には、パーソナル・コンピュータに直接接続される。イメージ・センサからのデータ率が走査速度を制限する傾向がある。スキャナは、所望の解像度に対する適切な速度を維持するため、緑または赤の発光ダイオードという手段によって、ユーザにフィードバックを提供する。一部のハンド・スキャナは、ユーザがスキャナをイメージ上であまりに速く移動することを防止するため、速度の上昇と共に機械的抵抗を増加させる電磁ブレーキを使用する。
【００１０】
ハンド・スキャナは、比較的小さいイメージ形成アレイを利用するので、１回の走査でＡ６より大きいドキュメントを扱うことは一般にできない。これは、比較的大きいドキュメントについて複数の走査帯を結合させる縫合アルゴリズムを必要とする。帯縫合はパーソナル・コンピュータによる独立した動作で行われる。ハンド・スキャナを用いて複数ページのビジネス・ドキュメントまたはレポートを走査することは、退屈なプロセスであり、しばしば低品質を生成する。
【００１１】
前述のように、ハンド・スキャナには典型的に何らかのタイプの固定治具が使用される。そのような固定治具がない場合、ハンド・スキャナがオリジナル上を移動するにつれ、多少の回転を伴う傾向がある。スキャナの移動の間ユーザの肘が平らな表面にとどまっていると、回転は、スキャナとユーザの肘の間の距離によって定まる半径を持つ可能性がある。結果として、走査された電子的イメージはゆがめられる。スキャナの走査帯の間のその他の曲線の運動もまたひずみを生成する原因となる。
【００１２】
【発明が解決しようとする課題】
このように、走査プロセスの間にたとえ曲線運動があっても、ハンド・スキャナがオリジナル・イメージと走査結果の間に高度な対応性を持つことを可能にするナビゲーション方式が必要とされている。
【００１３】
【課題を解決するための手段】
発明の課題を解決するため、連続的時間間隔でセンサ・アレイによって捕捉される複数イメージの間の相関に基づいて、センサ・アレイのナビゲーション位置を効率的に取得する方法および装置が提供される。
【００１４】
これは、上記センサ・アレイを介して基準フレームを先ず取得し、上記センサ・アレイを介してサンプル・フレームを連続的に取得することによって達成される。次に、サンプル・フレームと基準フレームの間の関係を表わす相関データが生成され、その相関データに基づいて、基準フレームおよびサンプル・フレームに含まれる基準特徴の変位が決定される。相関データの相関表面は、一般的２次元テーラー級数展開式としてモデル化される。
【００１５】
本発明の方法および装置を走査装置において使用することによって、連続的時間間隔において走査装置のセンサ・アレイによって捕捉されるイメージ・フレーム間の比較に基づいたナビゲーション情報を取得する効率的方式が提供される。
【００１６】
【発明の実施の形態】
走査装置に関するナビゲーション方法が提供される。該ナビゲーション方法は、走査されているオリジナルの固有の構造関連特性を検出する少なくとも１つのナビゲーション・センサという手段によって基準フレームおよびサンプル・フレームを取得することを必要とする。イメージ・センサがオリジナルに対して相対的に移動する際の固有の構造関連特性の変化を監視することによって、オリジナルに沿ったイメージ・センサの運動を追跡することができる。好ましくは、監視される固有の構造関連特性は、オリジナルの用紙繊維またはその他の構成要素のような固有の構造的特徴である。ナビゲーションは、また、スペックル(すなわち、細かい斑点状の干渉模様)に基づいて実施することもできる。この場合、オリジナルに沿ったイメージ・センサの運動は、ナビゲーション情報を得るためコヒーレント照明を使用して生成されるスペックル・パターンの変化を監視することによって、追跡される。
【００１７】
本明細書において、"固有の構造関連特性"は、オリジナル上のイメージ・データならびに体系的位置決めデータを形成することからは独立している因子に帰属するオリジナルの特性として定義される。ナビゲーション情報は、スペックル情報の位置信号または個々の固有の構造的特徴の追跡を可能にする位置信号のような、固有の構造関連特性の検出に応答する位置信号を生成することによって形成される。本明細書において、"固有の構造の特徴"とは、オリジナルを形成するプロセスから派生する特徴であるが、オリジナル上のイメージ・データならびに体系的位置決めデータを形成することからは独立しているオリジナルの特徴として定義される。例えばオリジナルが記録される媒体が紙製品であれば、対象とされる固有の構造的特徴を紙の繊維とすることができる。別の例をあげれば、光沢のあるオリジナルまたはオーバーヘッド透過フィルムを走査するイメージ・センサのナビゲーションは、鏡面フィールドに影響を及ぼす表面テクスチャの変化を追跡することによって決定することができる。この場合、典型的には、固有の構造的特徴は、顕微鏡で見える程度の、例えば１０乃至２０μｍの表面模様である。
【００１８】
このように、ナビゲーション情報を得るための手段はいろいろある。最も広義の手段では、走査経路に沿った走査装置の曲線的に回転する運動のひずみを除去するために使用されるべきナビゲーション情報源に限度は存在しない。従って、ナビゲーション信号は、オリジナル上のイメージ・データの検出に応答する位置信号(例えばテキスト文字のエッジの識別)という形式も可能である。この場合、位置信号は後続のイメージ信号の操作において使用される。比較的狭義の手段としては、位置信号がスペックル・パターンを決定する特性のような固有の構造関連特性の検出に応答する。
【００１９】
別の、第３の手段は、個々の固有の構造的特徴(例えば用紙の繊維)の位置を時間の経過と共に監視することによって、走査装置のナビゲーションを追跡するものである。この第３の手法は、実際第２の手法のサブカテゴリであるので、最も狭義のものである。
【００２０】
本発明の好ましい実施形態において、イメージ・センサは電子工学的エレメントの線形アレイであり、一方、ナビゲーション手法はナビゲーション・センサ・エレメントの少なくとも１つの２次元アレイを利用する。イメージ・センサの両端に独立した２次元ナビゲーション・アレーを配置することによって、スキャナは３つの運動自由度を与えられる。オリジナルが平面であれば、自由度のうちの２つは移動可能でありオリジナルの範囲内で相互に垂直を形成するが、第３の自由度はオリジナルの平面に対する垂線の周囲を回転する。回転追跡の正確度は２つのナビゲーション・アレイの使用によって強化される。これらアレイの各々は、単一のナビゲーション・アレイだけが使用された場合に必要となるものより小さいアレイ範囲を持つ。好ましい実施形態のナビゲーション・センサは２次元アレイではあるが、線形アレイを使用することも可能である。
【００２１】
更に、詳細は後述されるが、走査装置にその他の位置追跡手段を固定することによって、イメージ・データを調整するためのナビゲーション情報が容易に取得される。それら位置追跡手段には、符号化車輪ならびにボール、コンピュータ・マウス・トラックボール、位置決めグリッド検出加速度計、機械的リンク機構、非接触電磁気ならびに静電気リンク機構、および遅延統合センサ・アレイが含まれる。これら多数の代替的実施形態において、イメージ・データを調整するためのナビゲーション情報は、位置追跡がイメージ捕捉を含まないので、オリジナルのどのような固有の構造関連特性とも無関係な方法で取得される。
【００２２】
ナビゲーション・センサは、イメージ・センサに対して既知の位置にある。ナビゲーション・センサは、イメージ・アレイが移動するにつれてオリジナルのエッジを越えることがないように、可能な限りイメージ・センサの端点に近い位置に置かれることが好ましい。イメージ・センサは、処理対象のイメージを表す信号を形成する。同時に、各ナビゲーション・センサは、オリジナルの固有構造関連特性を表す信号を形成する。走査装置は、手で描いた曲がりくねったパターンに沿って移動されるかもしれない。例えば、走査装置はオリジナルに接触しながら、オリジナルに沿って下方向に左から右および右から左へと交互に動かされる。走査帯の各々は、前の帯の一部とオーバーラップしなければならない。イメージは、走査プロセスの間またはその後の段階のいずれかにおいて、位置に関して処理が行われ、縫合される。イメージ信号の処理はイメージ・データの調整である。イメージ・データの調整は、ナビゲーション・センサとナビゲーション・センサによって検出された固有の構造関連特性の間の相対的運動に基づく。処理はイメージ信号の調整、すなわち、オリジナルと出力イメージの間の整合性を保つため、取得したイメージ・データをナビゲーション・データに基づいて配置および調整する操作である。連続した走査帯の間に取得されたイメージ・データを結合するため縫合が使用される。
【００２３】
好ましくは、各ナビゲーション・センサは、オリジナルの固有構造関連特性に従属するコントラストを与えるように設計される１つまたは複数の光源を含む。放射光線は可視域にあるが、必ずしもそうである必要はない。例えば、表面垂線に対して大きい入射角を持つ"かすめ"光は、オリジナルが繊維質の間にコントラストを強調する陰影を形成する紙製品である場合オリジナルの表面近傍の紙繊維に対して作用する。一方、オリジナルが例えば写真プリント、粘土皮膜紙またはオーバーヘッド透明フィルムのような光沢紙の場合、垂直な入射光が、ナビゲーションの目的にとって十分なイメージ・コントラスト特徴を持つイメージを鏡面フィールドに生成する。フィルタおよび１つまたは複数のイメージ形成レンズのような光学エレメントが更に固有構造関連特性の検出を向上させる。
【００２４】
図１には、オリジナル１４に沿って曲がりくねった経路１２をたどる手持ち式走査装置１０が示されている。好ましい実施形態において、オリジナルは、紙、オーバーヘッド透明フィルムまたはイメージを保持する表面を持つその他のいかなる媒体でもあり得る。ナビゲーションの間、曲がりくねった経路に沿った位置情報を提供するため必要とされるコントラストをオリジナルの固有構造関連特性がそれらオリジナルの表面上に生成する。典型的には、イメージ・データの調整のため、固有構造特徴の位置が追跡され、その位置情報が使用されるが、その他の形態を使用することもできる。走査装置は、自己完結型であり、電源はバッテリであることが望ましいが、外部電源またはコンピュータあるいはネットワークのデータ・ポートへの接続端子を含むこともできる。図１の走査装置１０は画像表示機構１６を含む。表示機構は、捕捉したイメージをほとんど即時に表示することができる。しかし、表示機構は走査装置の使用にとって必須ではない。
【００２５】
走査装置１０は３つの自由度を許容する。２つの自由度は並進運動であり、１つは回転である。第１の自由度は、オリジナル１４に沿った側面から側面への運動(すなわちx軸運動)である。第２の自由度は、オリジナル１４に沿った上方および下方への運動(すなわちｙ軸運動)である。第３の自由度は、装置の操作の結果イメージ・センサ・エレメントの線形アレイの位置がオリジナル１４のエッジに対して不適切に回転(θ軸運動)することである。すなわち、イメージ形成エレメントの線形アレイは、装置並進運動の方向に直角でない接着角度を持つ。
【００２６】
図１乃至図３を参照すれば、走査装置１０の前側１８は、オリジナル１４とイメージ形成センサ２２の間の適切な接触の維持に役立つ軸回転部材２０を含む。ナビゲーション・センサ２４および２６は、イメージ形成センサ２２の両端に位置する。ナビゲーション・センサは、軸回転部材上に装着されるので、イメージ形成センサに対して固定的位置にある。
【００２７】
物理的にコンパクトであるようにするため、イメージ形成センサ・アレイ２２は、好ましくは、接触イメージ装置であるが、コンパクトさが重要でないアプリケーションまたは比較的小さいイメージが要求されるアプリケーションにおいては、倍率が１単位より小さい投影光学機構を利用するセンサを使用することもできる。そのようなアプリケーションでは、イメージ形成センサ２２のエレメントは比較的小さくなければならず、また、すべてコンパクトに実装されなければならない。接触イメージ形成装置は、典型的には、Nippon Sheet Glass Company Limitedの米国における登録商標であるSELFOCという商標の下で販売されているレンズを使用する。さほど一般的ではないが、レンズを使用せず、光源のアレイ・エレメントと隣接センサの交互配置を使用して接触イメージ形成を実施することもできる。走査アプリケーションに関する従来型のイメージ形成センサを使用することもできる。また、イメージ形成センサを、照光光源、照光光学部品およびイメージ伝達光学部品を含む装置の一部とすることもできる。
【００２８】
イメージ形成センサは、離散的光学反応エレメントの線形アレイとして示されている。エレメントの間隔は、スキャナ１０の空間的解像度を決定する役割を果たす。例えば、１０１.６mmの長さを持つ線形アレイは、３００dpiの解像度を達成するには１２００のセンサ・エレメントを必要とする。センサは、ＣＣＤ、アモーファスSiホトダイオード・アレイ、あるいは、当業界において既知のいかなるタイプの線形アレイ・センサでもよい。
【００２９】
イメージ形成センサ装置の設計における重要因子は速度である。イメージ形成センサ２２は、好ましくは、秒あたり約１０Ｋというサンプル率で各ピクセルのイメージを形成することができる。線形イメージ形成アレイは、一般に、直列データストリームを生成する。直列データストリームにおいては、ピクセル値すなわち電荷がシフト・レジスタに置かれ、次にシフト送りされる。所望の速度の達成は、ピクセル値が比較的少ないセルを通してシフト送りされるように、全体のイメージ・アレイからの非常に高速な直列伝達速度または論理タップのいずれかを必要とする。これが、デジタル処理の利点である並列性につながる。
【００３０】
速度要件の別の帰結は、オリジナルの表面におけるピクセル領域の生成および各アレイ・エレメントに収集ならびに搬送される放射光線の立体角度が、１００マイクロ秒というオーダーの集積時間において検出可能な信号を生成することができる十分な大きさでなければならないという点である。補強オプションとして、各検出エレメントが反応するセンサ・ピッチの有効小数部を増加させるため、光学エレメントをセンサに追加することができる。典型的にはアレイ・マトリックスに未使用領域が存在するので、そのような光収集光学部品は感度を増加させる。
【００３１】
イメージ形成センサ２２の単純な修正によってカラー・イメージの検出を可能にすることができる。カラー・イメージ形成のため、相互に平行な３つの線形アレイを配置し、それらアレイの各々は、入射光の赤、緑および青成分をそれぞれ選択的に通過させる少なくとも１つの組み込みフィルタを備え持つ。代替的には、広帯域の感度を持つ単一アレイが赤、緑および青の光源によって順次照光される配置も可能である。
【００３２】
イメージ形成センサ２２の動作を改良する照明に関する限り、琥珀色波長の高強度発光ダイオードの直線アレイを使用することができる。しかしながら、好ましい照光光源およびどのような光学エレメントの選択も、オリジナルの媒体に依存する。不必要な信号を無視しながら、オリジナル１４の所与の領域の走査の間に取得されるコントラスト・イメージ・データを最大にするように光の波長が選択される。照光光学部品は、ＬＥＤドーム・レンズから構成されるか、あるいは、高精度に成形された光学エレメントから成る光パイプを含む。後者は、最小限度の光量損失で照射光をオリジナル上へ通過させる。そのような設計は、広範囲にわたる角度でオリジナルの目標領域の相対的に均一な照光を可能にするが、鏡面反射を避けるため法線入射光線をブロックする。
【００３３】
図１において、曲がりくねった経路１２は４回と端数の走査帯(すなわちオリジナル１４に対する端から端への走査)を持つものとして示されている。最も一般的アプリケーションに役立つイメージ形成センサ２２は、２５.４mmと１０１.６mmの範囲内の長さを持つ。センサ２２が６３.５mmの長さを持つとすれ、Ａ４用紙は４回または５回の走査帯で走査される。帯は、縫合プロセスを使用してオリジナル・イメージの忠実な複製を生成することができるように、オーバーラップの領域を含まなければならない。
【００３４】
走査装置１０は、典型的には、少なくとも１つのナビゲーション・センサ２４または２６を含む。好ましい実施形態においては、走査装置は、イメージ形成センサ２２の両端に配置されるペアのナビゲーション・センサを含む。１次元アレイの光電子工学エレメントを使用することも可能ではあるが、好ましい実施形態においては、各ナビゲーション・センサは、２次元アレイ・エレメントである。オリジナル１４に対する走査装置１０の動きを追跡するためナビゲーション・センサ２４ならびに２６が使用される。
【００３５】
好ましい実施形態において、各ナビゲーション・センサ２４ならびに２６は、走査装置１０の位置に関連する情報を生成するため、オリジナルの固有の構造関連特性に関連したイメージを捕捉する。大部分の従来技術の走査装置に関する限り、固有の構造的特徴はノイズとみなされる。図１乃至図３の走査装置１０に関して、そのような特徴は、イメージ形成センサ２２にとってノイズであるが、ナビゲーション・センサ２４ならびに２６が位置情報を生成する基礎を提供するため使用されることができる。媒体に固有であるか媒体上に形成される構造的変化を検出することによって表面模様の役立つ高コントラスト・イメージを生成することができる。例えば、イメージは、固有の構造的特徴の谷の陰影と頂上の輝点の間のコントラストに基づいて形成される。そのような特徴は、典型的には、顕微鏡で見ることができるほどの大きさで、一般的印刷媒体では１０乃至４０μｍの範囲の大きさである。代替的には、コヒーレントビームの正反射が明ならびに暗の領域のコントラスト・パターンを生成するので、スペックルを使用することもできる。コントラスト情報の第３のソースはカラーである。カラー・コントラストは表面模様と無関係である。可視域の光で模様と無関係な表面を光で照光する時でさえ、異なるカラー(例えば異なる濃淡レベル)の領域の間にカラー・コントラストが存在する。
【００３６】
しかしながら、ナビゲーション情報がオリジナルの固有構造関連特性と無関係であるようなアプリケーションに本発明を使用することは意図されている。例えば、図２のナビゲーション・センサ２４ならび２６の一方または両方を使用して、連続的イメージを開発してオリジナル１４に沿ったイメージ・センサ２２の位置および方向を決定することができる。この実施形態において、３つのセンサ２２、２４および２６のすべてがオリジナル上のテキストのイメージを形成するが、センサ２２からの信号だけがイメージ・データを取得するため使用される。 ナビゲーション・センサ２４ならびに２６からの信号は、イメージに基づくナビゲーション情報を取得するため使用される。
【００３７】
Ｘ、Ｙおよびθ位置情報を取得および処理するため非イメージ形成技法を使用することもできる。あいにく、代替手段の多くは、コンパクトさ、使用上の便宜性、速度、運動の自由度、電力消費、正確性、精度ならびにコストに関する制約を持つ。位置情報を取得するため利用できる代替的非イメージ形成技法の１つは、ナビゲーション・センサの代わりに１つまたは複数の符号化車輪を利用する。符号化車輪は走査される表面上をスリップせずに転がり、走査装置が直線または曲線の軌跡に沿って移動することを可能にする。符号化車輪が共通の軸の上にあることは重要ではない。車輪はスイベル(すなわち回り継手)に装着することができる。回転を監視するため接続される符号器が、開始位置ならび方向に対するイメージ形成センサの位置ならびに方向を計算するための入力データを作成する。
【００３８】
ナビゲーション情報を取得するため利用できる代替的非イメージ形成技法の別の１つは、コンピュータ・マウスに対する場合と同様なトラックボールを使用するものである。上述された各符号車輪の代わりにトラックボールが使用される。各トラックボールから２次元の変位情報を取得するため符号器が使用される。別の手法において、タブレットに構築される協調的(能動的あるい受動的)グリッドまたはその他の基準に対する位置および方向を検出するため、図２のナビゲーション・センサの代わりに光学的あるいは電子的(容量性、抵抗性あるいは誘導性)センサが使用される。このタブレットは走査されるオリジナルに対する支持の役をする。
【００３９】
位置ならびに方向情報を取得する非イメージ形成技法の更に別の１つは、加速度計を利用するものである。ボード搭載慣性航法プラットホームが使用され、加速度が検出され、速度を取得するため１度、位置を取得するため２度積分される。または、ばね吊り質量の速度が検出され、位置を取得するため１度積分される。方向を直接検出するためジャイロスコープを使用することもできる。
【００４０】
更に別の技法は、種々の機械的リンク機構のいずれかを使用するもので、それらを用いて、走査されている媒体に対して固定的な基準座標に対する位置ならびに方向が追跡される。機械的部材の相対的運動を測定するため接続されるセンサ手段によって位置ならびに方向情報が取得される。これらのセンサは、相対的あるいは絶対的タイプのいずれかであり、検出する直接的位置ならび方向に基づくか、あるいは、加速度または速度を検出してそれを１度または２度積分して位置情報を取得する。
【００４１】
更に、非接触遠隔検出を使用して、走査されているオリジナルに対して固定的な基準座標に対する走査装置の位置ならびに方向を測定することができる。そのような非接触検出の例には、(例えば光学的またはラジオ周波数での)電磁場波またはビーム、電気的効果(例えば容量性効果)および磁性効果(例えば誘導性効果)の使用が含まれる。これらの技法は、標準的または微分大域位置づけ技術を利用し、潜在的には衛星を使用することができる。これらの技法は、また、伝統的なナビゲーション/測量方法(例えば三角測量方式)を含むこともできる。これらは、また、形状光線を使用してこれらのビームが移動オブジェクトを妨げる場所のイメージに基づいて位置を推定するような、ロボット工学技術で使われる手法を含めることもできる。
【００４２】
図２のナビゲーション・センサ２４ならびに２６は、オリジナル１４の移動イメージを効果的に観測して、連続的観測の間の２次元変位を標示する情報を生成する。詳細は後述されるが、イメージ形成センサ２２からのイメージ・データの適切なマッピング(対応付け)を決定するように諸エレメントを処理することによってナビゲーション・センサからのピクセル値が取り扱われる。処理エレメントが特定ピクセルおよびその最隣接ピクセルにはたらきかけて、各ピクセル位置における相関値アレイを生成する。相関値は、表面構造の現在時イメージと固有の構造上の特徴の既知の位置を表す記憶されたイメージの間の比較に基づく。この場合、記憶されたイメージは位置基準の役目を果たす。しかしながら、出力イメージを形成するため入力イメージ・データを処理する際に相関プロセス以外の操作を利用することもできる。
【００４３】
図４および図５には、照光光学部品と連動するナビゲーション・センサ２４が示されている。オリジナル１４が、ナビゲーション・センサ２４によって紙繊維が検出されることができるような紙製品であれば、かすめ入射角での光の導入が望ましい。必須ではないが、１つまたは複数の発光ダイオード(ＬＥＤ)が使用される。入射角の補角であるかすめ角３０は、ゼロ度から１５度の範囲であることが望ましいが、これはオリジナル１４の特性に従って変わり得る。図５において、光源２８は照光光学部品３４を持つように示されている。光学部品は、レンズ、フィルタ、またはホログラフィック素子の単一エレメントまたはそれらの組み合わせであり、目標表面の適切な、視準されたおおむね一様な照明を達成するためのものである。光源２８によって発せられる光の波長は、ナビゲーションに利用できる空間周波数情報を強化するように選択される。照光フィールドにおける固定的パターン・ノイズは最小限にされなければならない。走査装置がインクまたはその他のマーキング材を吸収または反射しながら印刷物上を進む間に、媒体の反射率の広いダイナミックレンジを実現するため、光源２８の出力は調整を必要とする場合がある。
【００４４】
図４において、光源２５からの光は、照光光学部品３６において視準され、振幅分割ビーム分波器３７によって方向を向け直される。ビーム分波器を直接通過するＬＥＤからの光エネルギー部分は図４に示されていない。ビームス分波器からの光エネルギーは表面に対する法線に沿ってオリジナル１４を照光する。
【００４５】
図４に示されている光エネルギーは、オリジナル１４から反射または拡散され、エレメント３８におけるフィルタリングおよびエレメント３９におけるイメージへの集束のためビーム分波器３７を通過する光エネルギー部分である。オリジナルからビーム分波器へ通過しビーム分波器から反射する光エネルギーの部分は示されていない。ナビゲーション・イメージ形成光学部品の拡大倍率は、集束される光を検出する２次元センサ・アレイ２４の視界フィールドにわたって一定でなければならない。
【００４６】
多くのアプリケーションにおいて、ナビゲーション光学部品の変調伝達機能すなわち光学的周波数反応の振幅測定は、ナビゲーション・センサのセンサ・エレメントのピッチおよび光学エレメントの拡大倍率によって決定されるナイキスト周波数の前に減衰を提供するようなものでなければならない。光学的エレメントは、また、背景照光がノイズを発生しないように設計されなければならない(注：波面分割ビーム分波器を使用することもできる)。
【００４７】
入射角の選択はオリジナルの材料特性に依存する。オリジナルの表面が光沢のあるものでなければ、照光のかすめ角度は、比較的長い陰影と比較的明確なコントラストまたはＡＣ信号を生成する。しかしながら、照明角度がオリジナルに対する法線に接近するにつれて、ＤＣ信号レベルは増加する。
【００４８】
オリジナルの表面が顕微鏡視覚レベルで高度な不均等を持つようなアプリケーションの場合、かすめ角度３０でのオリジナル１４の目標領域の照光はうまくはたらく。例えば、オリジナルが印字用紙、ボール紙、繊維または人間の皮膚である場合、かすめ角度での光源２８からの光の導入は固有の構造的特徴に関連した高いＳＮ比のデータを提供する。一方、写真、光沢のある雑誌ページまたはオーバーヘッド透明フィルムのようなオリジナルに沿って走査装置の運動を追跡するため位置情報が必要とされるアプリケーションにおいては、直角の入射角でのインコヒーレント光の使用がむしろ好ましい。インコヒーレント光を使用する直角照明によって鏡面反射されたフィールドでオリジナルを見ることによって、イメージならびに相関に基づくナビゲーションを可能にする上でテクスチャ・コンテントの点で十分豊富なイメージが提供される。オリジナルの表面は顕微鏡可視的起伏を持つので、表面があたかもタイルまたはファセットのモザイクであるかのように表面は光を反射する。オリジナルの"タイル"の多数は、法線からわずかに拡散する方向に光を反射する。散乱光を含む視界および鏡面反射された光は、あたかも表面が多くのそのようなタイルから構成され、タイルの各々が法線から若干ずれているように組み立てられているかのようにモデル化される。このモデル化は、W.W. Barkas著"Light Scattered from a Surface of Low Gloss Into Its Specular and Diffuse Components"(Proc Ph s. Soc., Vol. 51, pages 274-292 (1939))に記載されているものと同様のものである。
【００４９】
図４は、オリジナル１４の表面の法線に沿って方向付けられる、インコヒーレント光源３５による照光を示す。図５は、かすめ角度３０での照光を示している。第３の実施形態においては、照光は提供されない。その代わりに、背景光すなわち周囲環境からの光を使用してナビゲーション情報が蓄積される。
【００５０】
第４の実施形態においては、コヒーレント照明が直角入射で導入され、スペックルに基づくナビゲーションを可能にする。ナビゲーション・センサに対するスペックルの運動を監視することによって、走査装置とオリジナルの間の相対運動が追跡される。イメージ形成光学部品を使用することなくコヒーレント照明が使用されるならば、照明の小さい領域を選択して、オリジナルの表面とナビゲーション・センサ２４の光検出器アレイの間に比較的大きい間隔を持つことによって、コヒーレント照明による良好なスペックル・セル・サイズがナイキスト・サンプリング基準を満たすことのできる大きさとなる。ビーム分波器の使用によって、入射照光および検出される拡散光の両者の方向が、図４の場合に達成されたように、オリジナル表面の法線に近接させることが可能となる。
【００５１】
図６には、オリジナルの表面上に印刷されているブロック４６を有するオリジナル４４を横切って動かされるスキャナ１０が示されている。スキャナ１０はオリジナルの平面におけるいかなる運動上の制約も受けないので、ユーザがスキャナを操作する際ユーザの前腕が肘を支点に回転するのでスキャナがオリジナル上で曲線の経路をたどる傾向がある。図６において、走査装置がブロック４６を横切って曲がった経路４８をたどるように示されている。走査装置の下側のエッジが、回転軸を画定する肘に近い側のエッジであるとすれば、この下側エッジは上方に比較して短い半径を持つ。従って、イメージ形成センサのイメージ形成エレメントはブロック４６を通過するために必要な時間ならびに距離の点で変動する。走査装置が点線で示されている第２の位置５２に動かされると、ゆがめられたブロック・イメージ５０が捕捉される。
【００５２】
捕捉されたイメージ５０は、以下に記述される処理が行われずに記憶されるイメージである。しかし、イメージ形成センサがブロック４６に関連したデータを捕捉する時、ナビゲーション情報が取得される。好ましい実施形態において、１つまたは複数のナビゲーション・センサが、オリジナル４４の固有の構造的特徴に関連したデータを捕捉する。ブロック４６に対するイメージ形成センサの変位を決定するため、走査装置１０に対する固有の構造的特徴の運動が追跡される。その後、忠実な捕捉イメージ５４が形成される。イメージ５４は"調整された"イメージと定義される。
【００５３】
図７には、ナビゲーション処理の１つの実施形態が示されている。固有の構造的特徴に関連したデータのような、ナビゲーション情報の連続したフレームを相関させることによってナビゲーション処理が実行される。特定の時間におけるナビゲーション・センサの位置に関連する情報を提供するため、相関関係は連続したフレームにおける固有の構造的特徴の位置を比較する。次に、ナビゲーション情報を使用して、イメージ・データが修正される。図７の処理は、典型的には、ナビゲーション・センサの各々毎に実行される。
【００５４】
第１のステップ５６において、基準フレームが取得される。基準フレームは、実際には、開始位置である。その後、ナビゲーション・センサから位置データのサンプル・フレームを取得して、基準フレームと取得したサンプル・フレームの間の相関を計算することによって、ナビゲーション・センサの位置が決定される。
【００５５】
初期基準フレーム５６の取得は、イメージ形成プロセスの開始時に実行される。例えば、走査装置のオリジナルへの単なる接触によってそれは起動される。または、走査装置がイメージ・プロセスならびナビゲーション・プロセスを始動させる起動ボタンを含むこともできる。また、各ナビゲーション機構の照光系の定期的パルスによってプロセスを始動させることもできる。事前指定された反射しきい値を超える反射信号、または、運動を示す相関信号があれば、基準フレームが取得される。
【００５６】
ナビゲーション処理はコンピュータで実行されるが、この実施形態の概念が図７および図８を参照して記述される。基準フレーム６２はＴ形の固有の構造的特徴６４のイメージを持つものとして示されている。基準フレームのサイズは、走査装置の最大走査速度、構造的特徴のイメージ形成における支配的空間周波数およびセンサの解像度のような因子に依存する。３２ピクセル(N)×６４ピクセル(M)のナビゲーション・センサに関する基準フレームの実際的サイズは２４×５６ピクセルである。
【００５７】
その後の時間(dt)にナビゲーション・センサはサンプル・フレーム６６を取得する。サンプル・フレーム６６は、基準フレーム６２に対して相対的に変位されるが、実質的に同じ固有の構造的特徴を示す。Ｔ形特徴６４の相対的変位が走査装置の並進運動の速度においてナビゲーション・センサの１ピクセル未満であるように、時間間隔dtがセットされる。許容可能な時間間隔は、６００dpiにおいて速度０.４５メートル/秒に対して５０μｓである。この相対的変位を本明細書においては"マイクロステップ"と呼ぶ。
【００５８】
走査装置が基準フレーム６２を取得するステップ５６とサンプル・フレーム６６を取得するステップ５８の間の時間間隔の間に移動したとすれば、Ｔ形特徴の第１および第２のイメージは特徴がシフトしたイメージである。好ましい実施形態においてはdtは１ピクセルの運動を可能にする時間より小さいが、図８の表現は、特徴６４が上方および右方へ１ピクセルだけシフトすることが許容されているるものである。完全な１ピクセルのシフトは表現を単純化するためにのみ仮定されている。
【００５９】
図８におけるエレメント７０は、フレーム６８のピクセル値の８つの最近傍ピクセルへの順次シフトを表している。すなわち、例えば、ステップ"０"はシフトを含まず、ステップ"１"は左斜め上へのシフトであり、ステップ"２"は上方シフトである。このようにして、ピクセル単位シフトされたフレームがサンプル・フレーム６６と組み合わせられ、位置フレーム・アレイ７２を生成する。"位置０"に指定された位置フレームはシフトを含まず、その結果はフレーム６６と６８の単なる結合である。"位置３"は、影をつけられたピクセルの数が最小であり、最も高い相関を持つフレームである。相関結果に基づいて、サンプル・フレーム６６におけるＴ形特徴６４の位置が以前に取得された基準フレーム６２における同じ特徴の位置に対して斜め右上へシフトしていると決定される。これは、走査装置が時間dtの間に左下方向へ移動したことを意味する。
【００６０】
その他の相関手法を利用することはできるが、許容可能な手法は、"差の平方の和"相関である。図８の実施形態の場合、９つの相関係数(C_k=C₀,C₁,...,C₈)がある。）これらはエレメント７０における９つのオフセットから作成され、相関係数は次の式(数１)によって定義される。
【００６１】
【数１】

但し、S_ijはサンプル・フレーム６６の位置ijにおいてナビゲーション・センサが測定した値を示し、R_ijは、エレメント７０においてk方向にシフトしたフレーム６８におけるナビゲーション・センサが測定した値を示す(kはエレメント７０におけるシフトの識別子である)。図８において、k=3が相関係数に最も低い値を与える。
【００６２】
フレームからフレームへの特徴の変位を決定するため連続したフレームにおける全く同じ特徴の位置を見つけるため相関が使用される。このような変位の総和および関連光学部品の設計を通して導入されるスケール・ファクタの補正が走査処理の進行に伴うイメージ形成センサの変位を決定する。
【００６３】
前述のように、変位が１ピクセルの次元を超えないことを保証するようにフレーム率が十分高く選択されるので、フレーム対フレーム相関は"マイクロステップ"と呼ばれる。サンプリング過剰はサブピクセル変位精度を提供する。図７を参照すれば、相関の各計算６４の後にマイクロステップを進めるか否か判断される(ステップ７４)。マイクロステップが必要であれば、基準フレームがシフトされる(ステップ７６)。このステップにおいて、図８のサンプル・フレーム６６が基準フレームとなり、新しいサンプル・フレームが取得される。次に相関計算が繰り返される。
【００６４】
このプロセスは高い度合いの相関一致を提供するが、基準フレームに対して発生する誤差が、サンプル・フレーム６６の各連続したシフト(ステップ７６)毎に累算される。"ランダムな運動"の誤差の増加率に対して制限を設けるため、サンプル・フレームは独立したバッファ・メモリに保存される。この別に保存されたサンプル・フレームは、相関計算の後続のシリーズに関して新しい基準フレームになる。後者の相関は"マクロステップ"と呼ばれる。
【００６５】
マクロステップを使用することによって、ｍ個のイメージ・フレーム変位すなわちｍ回のマイクロステップの距離にわたるスキャナ変位が一層正確に決定される。１つのマクロステップにおける誤差は単一の相関計算の結果であるが、ｍ回のマイクロステップの同等の誤差は単一マクロステップの誤差のｍ^1/2倍に相当する。ｍマイクロステップにおける誤差の平均はｍが増加するほどゼロに近づくが、誤差の平均における標準偏差はｍ^l/2として成長する。このように、マクロステップを定義する２つのフレームが大きな共通イメージ領域を持たない程度に相互に間隔をあけていない限り、実際的大きさｍを持つマクロステップを使用することによって累積誤差の標準偏差を減少させることには利益がある。
【００６６】
サンプリング間隔dtは定数である必要はない。サンプリング間隔は先行した測定値の関数として決定することもできる。可変dtを使用する１つの方法は、連続基準フレームの間の相対的変位を一定の限度内に保つことによって変位計算の正確度を向上させるためのもである。例えば、上限は１ピクセル変位であり、一方、下限は、ナビゲーション・データを処理する際の数字の丸めによって決定される。
【００６７】
図９を参照すれば、イメージ形成センサ２２において生成されたイメージ信号は、次に、ナビゲーション・データに基づいて"位置タグ"を付けられる。１つの実施形態において、２つのナビゲーション・センサ２４ならびに２６からのピクセル値は、図７および図８の動作を実行するためナビゲーション・プロセッサ８０によって受け取られる。計算された相関に基づいて、第１のナビゲーション・センサ２４の現在位置に関する座標(X₁,Y₁)および第２のナビゲーション・センサ２６の現在位置に関する座標(X₂,Y₂)が決定される。ナビゲーション・プロセッサ８０は、また、ピクセル増幅器８２およびＡ／Ｄ変換器８４を経由してイメージ形成センサ２２のピクセル値を受け取る。図９の変換器８４がイメージ・センサ２２およびそれ自身からの単一タップだけを持つ単一の変換器として示されているが、各々がそれぞれのタップを持つ複数変換器を使用することもできる。
【００６８】
ナビゲーション・センサの現在位置座標にはイメージ形成センサの範囲内のピクセルの数に対応するデータ線の最後にタグが付けられる。従って、ナビゲーション・プロセッサ８０の出力８６は位置タグ付きデータストリームである。図１０において、Nピクセル・セルの両端に位置座標セル９０、９２ ９４および９６を持つようにデータストリームの増分８８が示されている。この場合セルの順序は必須ではない。
【００６９】
用紙繊維位置トランスデューサに関して完全に解析的ナビゲーション・アルゴリズムを使用することによって並進運動のｘおよびｙコンポーネントが計算される。このアルゴリズムは、一般的２次２次元テーラー級数展開式
f(x,y)=a₀₀+a₀₁y+a₂₀x²+a₁₁xy+a₀₂y²
として任意の相関表面をモデル化する。{x,y}平面における(回転、せん断および反射の任意の合成のような)一般的アフィン変換およびそれに続く３次元空間に埋め込まれた楕円放物面への３次元変換の適用を調べることによってこの選択は動機付けされる。３×３相関グリッドに記憶されたデータを２次６パラメータ・モデルを使用して計算される期待値と比較することによって、一般的線形最小２乗問題が公式化される。これら６つのパラメータの最適値の計算は、２乗誤差の対応する総和を分析的に最小化し、相関データ値の単純な線形結合から成る解のセットを取得することによって、行われる。このような最適モデル・パラメータの既知のセットを所与とすれば、{x,y}平面における相関表面の２次元変換が計算される。このアルゴリズムは効率的であり、変位解に対する妥当性検査は無視できるほどの計算コストで実行できる。現在時ナビゲーション機構非ゼロ平均差検出相関表面が重要な関心事ではあるけれども、このアルゴリズムは、並進運動ポイントにおいて大域極値を持ついかなる２次表面にも適用することができる。
【００７０】
原理的には、紙繊維イメージが捕捉され比較フレームへロードされた後このアルゴリズムは実行することができる。しかしながら、実際問題として２次元並進運動が大きい場合、相関表面の２次近似が失敗し、計算された変位が不正確となる可能性がある。新しい基準紙繊維イメージの各々の自動相関の直後に表面の形状を固定することによってナビゲーション誤差を線形にすることができる。このような誤差の大きさを減少させる３つの方法が記述される。それらは、立方体相関関数の使用、相関表面再形成および事後線形補正である。また、３×３相関グリッドの形態で記憶されたデータの４セルおよび６セル・サブセットだけを必要とする修正アルゴリズムの集合がピクセル・エッジならびにコーナの近傍で使用される。
【００７１】
基本的ナビゲーション・アルゴリズムの実行より前の正確な位置予測に対する必要性が、数値的に効果的な位置予測値のクラスを使用することを望ましくさせる。起点の中心におかれた１ピクセル四方のピクセル境界に実験的ドメインが制約されることを保証するため、この位置予測はナビゲーション・マイクロステップ・アルゴリズムによって使用される。"平滑化"アルゴリズムのクラスを適用して、記憶されたマクロステップ座標の統計的誤差を更に減らすことができる。
【００７２】
相関表面のモデルとしての楕円放物面
紙繊維イメージ相関
超小型軽量スキャナ・ナビゲーション・トランスデューサ(ナビゲーション機構)が、光センサ・アレイの下の照光された用紙繊維の(図１４に示されているような)イメージを直接初期的に捕捉する。ナビゲーション機構は、引き続いて、次式(1)の非ゼロ平均差検出関数を使用して、リアルタイム相関処理を実行する。
【００７３】
【数２】

但し、r_m,n(C_m,n)はピクセル{m,n}における基準(比較)イメージのデジタル化された値であり、i,j∈Zはピクセル単位で測定された、基準フレームに対する比較フレームのシフトを表す。原理的にはk∈R>1も可能であるが、典型的にはk∈Nである。
【００７４】
用紙繊維の同じ領域の相対的に変位されたイメージに上式(1)を適用することによって、図１５に示されるような"ボウル形の"相関表面が生成される。いかなるナビゲーション方式も、先ず、この相関表面の正確な数値モデルを構築しなければならない。モデルの複雑さはリアルタイム・ナビゲーション・システムの要件によって制約されなければならないが、モデル自身の範囲が、ナビゲーション機構がセンサの相対的位置を推定することができる最大の正確度を制限する。この点を考慮して、相関ボウルを楕円放物面で表示することが試みられる。そのような２次式モデルによって、ナビゲーション問題を強固な数理的基礎の上に置くことが可能となる。
【００７５】
図１５の(A)および(B)は、式(１)によって定義される"平方差の総和"相関関数C² _0,0を図１４のマゼラン用紙繊維イメージ・データセットに適用することによって計算される相関表面を示す。
【００７６】
アフィン変換および楕円放物面
z'=f'(x',y')によって記述される単純な楕円放物面を考慮することによってナビゲーション機構相関表面の初期的デジタル化３次元モデル表現としてxおよびyの２次関数が選択される。但し、
z'=f'(x',y')=q₂₀x'²+q₀₂y'²である。
【００７７】
q₂₀,q₀₂>Oであれば、表面は、{x',y'}={0,0}においてユニークな最小値z'=0を持つ。このケースにおいて、f'(x',y')の特定輪郭平面定数z'=z₀との交点によって形成される楕円の縦および横軸は、(Z₀/q₂₀)^1/2および(Z₀/q₀₂)^1/2によってそれぞれ与えられる。
【００７８】
{x,y}平面における一般的２次元アフィン変換を表面z'=f'(x',y')に適用することによって、変換の逆元が次の式(3)のマトリックスによってデカルト座標で表現される。
【００７９】
【数３】

【００８０】
z'軸の周囲を角度φ回転するケースではCは次式(4)という形式を持つ。
【００８１】
【数４】

【００８２】
しかしながら、式(3)は、また、後続の回転、せん断および反射の任意の合成と共に、せん断および反射のような２次元変換を表す点に注意する必要がある。
【００８３】
２次元アフィン変換の適用に続いて、ベクトル{x₀,y₀,z₀}による３次元変換が実行される。このベクトルは座標{x,y,z}によって指定される実験室基準フレームの範囲内に収まる。並進運動およびアフィン変換の両者を(順に)反転させることによって、ノイズのない相関表面のオリジナルの座標が次のように実験室座標で表現される。
x'=c₁₁(x-x₀)+c₁₂(y-y₀) (5a)
y'=c₂₁(x-x₀)+c₂₂(y-y₀) (5b)
z'=z-z₀ (5c)
【００８４】
図１６は、軸z'の周囲の角度φの回転および引き続くベクトル(x₀,y₀)の並進運動という特別のケースにおいて式(5a)および式(5b)によって与えられる２次元アフィン変換の概要図である。実験室座標系{x,y,z}における変換されたモデル表面のための関数形式は、式(5a)−式(5c)を式(1)に代入することによって得られる。すなわちz=f(x,y)である。但し、
f(x,y)=a₀₀+a₁₀x+a₀₁y+a₂₀x²+a₁₁xy+a₀₂y² (6)
a₂₀=q₂₀c² ₁₁+q₀₂c² ₂₁ (7a)
a₀₂=q₂₀c² ₁₂+q₀₂c² ₂₂ (7b)
a₁₁=2(q₀₂c₁₁c₁₂+q₀₂c₂₁c₂₂) (7c)
a₁₀=-(a₁₁y₀+2a₂₀x₀) (7d)
a₀₁=1(a₁₁x₀+2a₀₂y₀) (7e)
a₀₀=z₀+a₁₁x₀y₀+a₂₀x² ₀+a₀₂y² ₀ (7f)
注：実験室座標系における変換された表面は、a_mnxmy_nという形式の６つの項を持つ(但し、{m,n}∈{0,1,2}および0<=m+n<=2)。更に、２つの係数a₁₀およびa₀₁は、変位{x₀,y₀}で表され、これによって、上式(7d)および(7e)を反転して次式が得られる；
x₀=(a₀₁a₁₁-2a₁₀a₀₂)/(4a₂₀a₀₂-a² ₁₁) (8a)
y₀=(a₁₀a₁₁-2a₁₀a₀₂)/(4a₂₀a₀₂-a² ₁₁) (8b)
【００８５】
言い換えると、５つの係数a₁₀、a₀₁、a₂₀、a₁₁および{x₀,y₀}が数値的に一旦決定されれば、逆元変換行列cのエレメントまたは２つの係数q_2,0ならびにq_0,2のいずれかを明示的に見出すことなく、変換ベクトル{x₀,y₀}のコンポーネントは計算することができる。
【００８６】
図１７の(Ａ)および(Ｂ)は、モデル関数
f(x,y)=a₀₀+a₁₀x+a₀₁y+a₂₀x²+a₁₁xy+a₀₂y²
を図１５の(Ａ)および(Ｂ)に示されたデータに適用することによって得られる最良の最小自乗法表面を表す。但し、
a₀₀=132、a₁₀=8、a₀₁=12、a₂₀=526、a₁₁=24、a₀₂=934である。
【００８７】
図１８は、３×３ナビゲーション機構ピクセル−シフト相関グリッドと式(6)によって定義されたf(x,y)の対応する値の間のマッピングを示している。注：相関値は元々のマゼラン方式に従ってラベルをつけられている；
(すなわちC₀≡C^k _0,0、C₁≡C^k _-1,0など)。
【００８８】
ナビゲーション問題への効率的解析解
一般的線形最小２乗法による解法
実際問題として、高解像度の相関表面への数値的最小２乗法の適用はリアルタイムで実行することはできない。その代わりに、各用紙繊維比較イメージがナビゲーション機構によって捕捉された後、相関ボウルは、規則正しく定義されたグリッドに関して(以前に捕捉された基準イメージに対して)相関関数C^k _i,jを計算することによってサンプリングされる。例えば、i,j∈{-1,0,1}は９つの相関数を含む３×３正方形のグリッドを生成する。この場合C^k _0,0が中央のセルに位置する。次に、ナビゲーション機構によって生成されるピクセル−シフト相関データのこの限られたセットを表現することができる"最善の"２次モデルを見つけ出すという一般的問題を考察する。元々のマゼラン方式に従って(但しC₀≡C^k _0,0、C₁≡C^k _-1,0等々の)３×３相関グリッドのケースに関して、このモデルが図１８によって表されている。f(x,y)が差の自乗和相関データを可能な限り正確にモデル化することを可能にするように係数{a_mn}に対する値が見出されなければならない。
【００８９】
６つの係数および９つの相関値が存在するので、ナビゲーション問題に対する純粋に代数的手法は、解を得るため、グリッドにおける９つのデータ・ポイントからの選択を必要とする。本発明は、最小２乗法適用という既知の方法を使用する。これは、相関データにおける装置上および統計的誤差の両方が独立していて正規分布に従うとすれば適用されるパラメータの最大同一性推定の方法に等しい。原理的には、較正されたピクセル輝度測定値だけが使用されることを保証し、従って相関数の計算に及ぼす体系的誤差の影響を最小にするするように注意が払われていれば、相関データ値はこれらの仮定を満たす。
【００９０】
実際問題として、(各相関セルについて平均として同じものでなければならない)そのような誤差を測定することは難しく、いかなるケースにおいても、ナビゲーション・システムにおいて位置決定のため割り当てられる短い時間にそれらが役立つか否かは明らかではない。従って、本発明は、相関値の間の差の平方の総和を単に表すようにx²を変えることによって、そのような誤差を無視する。従って、対応するモデルの推定はf(x,y)を使用して次式(9)のようになる。
【００９１】
【数５】

【００９２】
f(x,y)は係数{a_mn}の線形関数であるので、x²はこれら変数パラメータの非線形関数である。
【００９３】
f(x,y)の９つの相関値{C₀...C₈}への数値的適合は、また、リアルタイム・システムにおいて実際的ではない。x²の最小値において、パラメータ・セット{a_mn}のメンバに関する勾配は同等に消滅しなければならない；
(δ/δa_mn)x²=0 (10)
【００９４】
それゆえ、６つの未知のパラメータにおける６つの独立した方程式が得られる。このプロシージャは、Mathematicaのようなコンピュータ代数パッケージを使用して容易に実施できる。３×３相関グリッドのケースに関して次のような値が得られる；
a₀₀=1/9[5c₀+2(c₁+c₃+c₅+c₇)-(c₂+c₄+c₆+c₈)] (11a)
a₁₀=1/6[(c₄+c₅+c₆)-(c₁+c₂+c₃)] (11b)
a₀₁=1/6[(c₂+c₃+c₄)-(c₆+c₇+c₈)] (11c)
a₁₁=1/4[(c₄+c₈)-(c₂+c₆)] (11d)
a₂₀=1/6[(c₁+c₂+c₃+c₄+c₅+c₆)-2(c₀+c₃+c₇)] (11e)
a₀₂=1/6[(c₂+c₃+c₄+c₆+c₇+c₈)-2(c₀+c₁+c₅)] (11f)
【００９５】
注意すべきは、各係数は、９つの相関値{C₀...C₈}の単純でユニークな線形結合として表わされている。x²が定義によって正の限定された値であるので、この解はユニークな最小値を表すにちがいない。検証すれば、ヘッシアン・マトリックスの固有値は{2,4,8,12,12,36}であり、これらはすべて正の定数であるので、得られる値はまさにユニークな最小値であることが判明する。
【００９６】
既述のように、式(11b)−式(11f)を使用して計算された係数を式(8a)−式(8b)に代入して、並進運動x0およびy₀を取得することができる。しかしながら、なにがしか一層公式的に処理することによって、有用な妥当性テストを展開することができる。前述のように、次式(12)の通り直角座標{x,y}に関する勾配が{x₀,y₀}において消滅することを保証することによってf(x,y)の最小値が求められる；
【数６】

【００９７】
ここにおいて、候補最小値の位置として直接式(8a)および式(8b)を生成する、２つの未知の{x₀,y₀}における２つの式が得られている。楕円放物面モデルにおいて、f'(x',y')の最小値は起点において発生するので、f(x,y)の最小値は{x₀,y₀}に位置する。この点は、次式(13)としてヘッシアン・マトリックスのエレメントを計算することによって更に調べられることができる。
【００９８】
【数７】

但し、Hの固有値は;
λ_±=a₂₀+a₀₂±[(a₂₀-a₀₂)²+a² ₁₁]^1/2 (14)
である。両方の固有値が正(負)であれば、f(x₀,y₀)は最小(最大)である。固有値が対立する符号を持つならば、表面はサドル型である。従って、最小値は次式(15a)、最大値は次式(15b)となる；
a₂₀+a₀₂>[(a₂₀-a₀₂)²+a² ₁₁]^1/2 (最小値の場合) (15a)
a₂₀+a₀₂>-[(a₂₀-a₀₂)²+a² ₁₁]^1/2 (最大値の場合) (15b)
しかし、これらの制約は次式(16)、(17a)、(17b)のような計算処理可能な一層単純な条件と同等である；
Det(H)=λ₊λ_-=(a₂₀+a₀₂)²-[a₂₀-a₀₂)²+a² ₁₁]=4a₂₀a₀₂=a² ₁₁>0 (16)
a₂₀+a₀₂>0 (最小値の場合) (17a)
a₂₀+a₀₂>0 (最大値の場合) (17b)
【００９９】
f(x,y)が{x₀,y₀}において最小であることが要求されるので、診断条件(16)および(17)は実行時ナビゲーション・システムに組み込まれる。この条件が満たされなければ、相関表面は理想的な楕円放物面形状から大きく乖離し、位置測定を行うため、以下に記述される予測値クラスのメンバが使用される。
【０１００】
図１９の(Ａ)は、２次式相関関数および図１４の用紙サンプルを使用して各データ座標について得られる相関数{C₀,...C₈}に式(8a)、(8b)および式(11b)−(11f)(以下アルゴリズム"9A"と呼ぶ)を適用した結果得られるナビゲーション誤差を表す。各誤差ベクトルは、既知の真の位置からアルゴリズムを使用して計算された位置を指し示す。起点の近くのアルゴリズムの性能は全く良好であるが、ナビゲーション誤差は、起点からの距離と共に非線形に増加し、距離が１ピクセルに接近すると誤差は数百のピクセルの長さにまで及ぶ。この問題の原因は、数値的には、式(8a)および(8b)における分母4A₂₀A₀₂-A² ₁₁にある。この分母は、起点からの距離とともに著しく減少し、最後に、１ピクセルを越える距離において妥当性条件(16)を充足しなくなる。この性能の低下は部分的に次のようにして克服することができる。先ず、i,j∈{-2,1,0,1,2}によって定義される正方２５セルグリッドに対してC^k _i,jを計算する。次に、以下に既述されるように導出される予測値のクラスの適切なメンバを使用して、表面最小値を含むセルを特定し、このセルを中心とする９つの相関数をアルゴリズムに入力として渡す。
【０１０１】
図１９の(Ｂ)は、この手法の使用を仮定した場合の改善を示している。この結果は好ましいものではあるが、異なる用紙サンプルが中心の平方ピクセルの範囲内でアルゴリズムを使用して有限ナビゲーション誤差を生成するか否かは依然として不明であり、非線形誤差が後述されるような効果的リアルタイム補正を可能にするか否か明らかでない。加えて、このような誤差の線形化を可能にするアルゴリズム"9A"への修正が考察される。
【０１０２】
図１９の(Ａ)および(Ｂ)は、２次式相関関数および図１４の紙サンプルを使用して各データ座標について得られる相関数{C₀,...C₈}にアルゴリズム"9A"を適用した結果得られるナビゲーション誤差を表す。各誤差ベクトルは、既知の真の位置からアルゴリズムを使用して計算された位置を指し示す。図１９の(Ａ)において、誤差ベクトルは、起点からの距離が１ピクセルに接近すると、数百ピクセルの大きさに成長する。図１９の(Ｂ)においては、以下に既述される予測手法の使用が仮定されている。
【０１０３】
相関表面のテーラー級数表現
楕円放物面に対するアフィン変換の効果を考慮することによってf(x,y)という２次形式の選択が動機を与えられたけれども、同じ手法を一般化して、近傍の最小値(または最大値)の相関関数に応用することが可能である。{ポイントr₀≡{x₀,y₀}において値g(x₀,y₀)を持つ任意の２次元関数を考察する。このポイントの近傍において、値g(x₀,y₀)の小さい変位ベクトル
【数８】

の効果が、次式(18)のテーラー級数展開式によって、公式として、与えられる。
【０１０４】
【数９】

【０１０５】
このようにして、２次モデル関数(6)の選択は、対象領域において"真の"相関表面がテーラー級数展開式によって正確に表示されることができるという仮定と同一である。大きい変位によってこの仮定が満たされない場合、上記アルゴリズムによって計算される並進運動ベクトルは信頼できない。従って、f(x,y)≡g(x₀+x,y₀+y)によって記述される２次表面から相関表面が大幅に乖離し始めるため、図１９の(Ａ)および(Ｂ)に示される起点からの距離にともなうナビゲーション誤差の非線形増加の原因が発生する。実際、図２０の(Ａ)および(Ｂ)に示されているように、起点の近くの合致は合理的ではあるが、距離が離れると真の表面は式(18)によって与えられる２次近似から大幅に乖離し始める。
【０１０６】
基本的２次ナビゲーション・アルゴリズム
しかしながら、楕円放物面としての相関表面のモデルは長所がないわけではない。基本ナビゲーション・アルゴリズムに対する修正を考慮すれば、大きい変位の場合にもその正確度を改良することが可能である。例えば、方程式(7a)および(7b)を分析すれば次の点が判明する。楕円放物面の場合、相関表面(a₁₁、a₂₀およびa₀₂)の２次形状を決定する係数は並進運動ベクトル{x₀,y₀}のコンポーネントに依存しない。従って、並進運動に先立ち相関表面の形状を先ず決定し、次に、並進運動の発生の後その形状を保持することによってアルゴリズムの妥当性範囲が拡張される。公式化すれば、この方法は次のステップからなる。
１. 基準フレームが取得された直後に得られる自己相関データに式(11d)−(11f)を適用することによって(a₁₁、a₂₀およびa₀₂)を計算する；
２. 後続の用紙繊維イメージの各々が、捕捉された比較フレームへロードされた後、比較および基準フレームを交差相関させることによって得られるデータに式(11b)および(11c)を適用することによってa₁₀ならびにa₀₁を計算する；
３. 値a₁₀ならびにa₀₁および自己相関データから計算される値(a₁₁、a₂₀およびa₀₂)を式(8a)および(8b)に代入して現在時イメージの並進運動座標を取得する；
４. 各基準フレームが取得された後このプロセスを繰り返す。
【０１０７】
数値的に便利なように、以下の変換式によって式(6)の係数に関連づけられるパラメータ{b_mn}が使用される；
b₁₀≡6a₁₀ (19a)
b₀₁≡6a₀₁ (19b)
b₁₁≡6a₁₁ (19c)
b₂₀≡12a₂₀ (19d)
b₀₂≡12a₀₂ (19d)
【０１０８】
図２０の(Ａ)および(Ｂ)は、最適合致２次表面と２次式相関関数(k=2)および図１４のデータセットを使用して計算される真の相関表面の間の相違を示している。相違は、データセットにおける相関表面の最大値によって尺度を縮小されている。ほとんどのケースにおいて、{a_mn}ではなく{b_mn}の使用が比較的少ない外部的定数を持つ比較的単純な表現を生む。
【０１０９】
図２１の(Ａ)および(Ｂ)は、２次式相関関数ならびに用紙サンプルを使用して得られる相関数{C₀,..,C₈}へのアルゴリズム"9B"の適用によって発生するナビゲーション誤差を示している。図１９の(Ａ)および(Ｂ)の場合と同様に、各誤差ベクトルは既知の真の位置から計算された位置を指し示し、予測手法の使用が以下に既述されるように仮定されている。この場合もまた、起点の近くのアルゴリズムの性能は極めて良好であり、また、方程式(8a)および(8b)の分母は固定されているので、誤差は起点からの距離に対して非線形に増大しない。それにもかかわらず、アルゴリズム"9B"は、真の位置ベクトルのデカルト座標コンポーネントをナビゲーション機構が起点から離れるように動く際徐々に増加する量だけ明らかに低く推定する。この誤差の徐々に増大する性質のため、アルゴリズム"9B"の３つの修正がアルゴリズムの性能の劇的改善を提供する。
【０１１０】
ナビゲーション性能改善の方法
基本的ナビゲーション・アルゴリズムの性能の改善方法には２つのクラスがある。第１の比較的一般的の方法として、相関表面、すなわち９つの相関数
{C₀,...C₈})が最適合致係数{b_mn}およびその後の変位{x₀,y₀}の計算に先立って修正される。このケースでは、新しい相関関数が相関データのリアルタイム計算のため選択され、また、データは、相関器によって生成された後、作り直される。目標は、２次テーラー級数近似が一層効果的表現の役目を果たすことができるように相関表面の形状を直接修正することである。第２の、一層具体的な方法としては、ナビゲーション・システムへの報告に先立って誤差の大部分が取り除かれることを可能にする補正関数(または照合テーブル)を構築するため、実行時にアルゴリズムによって生成される位置推定が使用される。この手法は、補正関数/テーブルのリアルタイム構築のための方法を必要とする。
【０１１１】
立方体相関関数
最初に、一層接近した２次表面を生成する相関関数が必要である。例えば、(k=1である式(1)によって与えられる)線形相関関数がパスファインダ(Pathfinder)ＲＯＭに組み込まれる。しかしながら、図２２の(Ａ)および(Ｂ)に示されるように、実際に、線形相関関数は、図２０の(Ａ)および(Ｂ)において示される２次式相関関数の場合に比較して２次近似で表現するのが一層困難な表面を生成する。従って、この相関表面へのアルゴリズム"9B"の適用から生じるナビゲーション誤差は、図２３の(Ａ)および(Ｂ)に示されているように、図２１の(Ａ)および(Ｂ)に表されている誤差より大きい。今や、ナビゲーション機構は、起点からの真の距離を、２次式相関関数の場合より大幅に大きい量低く推定している。
【０１１２】
かくして、立方体相関関数は２次関数によって生成されるものより小さい誤差を生成する。図２５を図２１と詳細に比較すれば、図１４のデータセットに関してテーラー級数近似(18)によって立方体を一層正確に表現することができることがわかる。実際、図２５の(Ａ)および(Ｂ)におけるナビゲーション誤差の対応する低減は劇的である。顕著な残存誤差がピクセル間の境界に発生しているだけである。この傾向は４次多項式相関関数では続かない。この場合、ナビゲーション・アルゴリズムは、位置のデカルト座標コンポーネントを過大評価し始める。kの正確な値をわずかに調整することによって、ピクセル境界での誤差ベクトルの長さにおけるわずかな低減を得ることができるが、このようにして得られるkの最終値は、３から大幅に異なることはなく、テスト中の特定の用紙サンプルに非常に依存する可能性が高い。このようにして、組み込まれる立方体相関関数は、リアルタイム・ナビゲーションの性能の大幅な改善を提供する。
【０１１３】
相関表面の再作成
実行時に相関器によって出力される２５(または９)の相関数の集合を所与とすれば、座標従属非線形マッピング関数をこれらデータに適用して、２次テーラー級数近似(18)によって一層正確に表示されるように表面形状を変更することができる。この手法の選択は、起点からの距離が増加すると共に２次式から大幅に乖離する１次元関数を非線形マッピングが持つような効果を検証することによって動機を与えられる。図２６の(Ａ)および(Ｂ)において、相関ボウルを通過する１平面スライスが関数C(x)=1-exp(-3x²/2)によって近似されている。
【０１１４】
関数C(x)は、起点からの距離と共に２次式より遅く増加するという点において、２次式相関関数によって生成される真の表面と同様に動作する。図２７の(Ａ)に示されるように、このシミュレートされた"データ"への最適合致２次関数はC(x)のむしろ貧弱な表現であり、図２０の(Ａ)および(Ｂ)において示される２次モデル関数の特定の数値的欠陥を共有する。すなわち、それは起点の近くで大きすぎ、特に、xの増加と共にデータの非対称動作を模倣することができない。しかしながら、図２６の(Ｂ)において、単純な非線形マッピングC'(x)=C(x)^3/2を使用してデータの形状を変更することによって、シミュレートされたデータと２次モデルの間の一致(-1<x<1の範囲内において)は大幅に改善される。(注：起点近くの最適合致２次式の小さい負の偏差は、k=3のケースに関して図２４の(Ａ)および(Ｂ)において示される２次モデル関数に類似している)。
【０１１５】
次式(20)によって与えられる単純な実際非線形マッピングは、相関表面の形状を変更して、２次テーラー級数近似(18)が一層正確にデータを表現することを可能にする。
【０１１６】
【数１０】

【０１１７】
立方体相関関数の使用から生じる偏差への図２７(Ａ)の類似性は図１１の(Ａ)に示されている点注意する必要がある。当然のことながら、図２９の(Ａ)および(Ｂ)において示されている対応するナビゲーション誤差は、図２５の(Ａ)および(Ｂ)に示されている立方体相関関数の場合と同様な劇的改善を表している。この場合もまた、ピクセル境界においてのみ一致は例外的である。このような境界において、残存誤差ベクトルの長さは分調整をkの値に対して行うことによって減少させることができるが、その結果のkの最終的値は多種多様な用紙サンプルにあてはまる可能性は少ない。
【０１１８】
原理的には、立方体相関関数から発生する表面さえも形状変更することができる。しかしながら、実際には、Kはこの場合１単位の大きさも乖離しないので、性能改善はほとんど認識できない。従って、k≡3/2として単純な実非線形マッピング(20)を使用するボウル形状変更は、立方体相関関数の使用に対する許容可能な代替方法である。ただし、この方法は、後刻ナビゲーション・プロセスに適用され、従って、テスト中の用紙繊維サンプルに一層依存するので、あまり一般的ではない。
【０１１９】
事後処理線形補正
アルゴリズム"9B"において、基準フレームが最初に取得され次に後続の比較フレームに対して固定された後、３つの係数b₂₀、b₀₂およびb₁₁によって表されるボウル形状が決定される。この場合、分母b₂₀b₀₂-b² ₁₁は一定に保たれ、{x₀,y₀}はb₁₀からb₀₁までの９つの相関数に線形に依存する。従って、アルゴリズム"9B"の使用から起こるナビゲーション誤差は、図２１の(Ａ)および(Ｂ)において示されるように{x₀,y₀}の計算された値において線形である。従って、位置がアルゴリズム"9B"を使用して計算された後{x₀,y₀}において線形である相関関数が見出されて適用される。定義によって、これらの線形関数は次式(21a)および(21b)という形式を持つ；
Δx(x₀,y₀=p₀₀+p₁₀x₀+p₀₁y₀ (21a)
Δy(x₀,y₀=q₀₀+q₁₀x₀+q₀₁y₀ (21b)
図２１の(Ｂ)に表示される中心ナビゲーション誤差に対するデル関数(2la)ならびに(21b)の線形最小２乗適合を実行することによって、次式(22a)および(22b)が得られる；
Δx(x₀,y₀=-0.021-0.322x₀-0.080y₀ (22a)
Δy(x₀,y₀=0.004-0.028x₀-0.348y₀ (22b)
【０１２０】
図２８の(Ａ)および(Ｂ)は、
x₀→x₀+Δx(x₀,y₀)および
y₀→y₀+Δy(x₀,y₀)
というマッピングを使用して図２１(Ａ)に示されている各対応する位置推定値{x₀,y₀}へのこのような補正関数の適用の結果を示している。注：平方根−平均−平方および最大ナビゲーション誤差の両方に顕著な減少がみられる。
【０１２１】
有用な線形補正関数が構築されることを可能にする相関関数{C₀,,,,C₈}におけるアルゴリズム"9B"の線形性が、この手法をアルゴリズム"9A"の出力に適用して{x₀,y₀}を計算する時可変分母b₂₀b₀₂-b² ₁₁を使用することによって、更に検証される。図３０の(Ａ)および(Ｂ)に示される結果と図１９の(Ａ)および(Ｂ)び示される元々のナビゲーション誤差の比較が、この補正がこの場合効果的でないことを説明する。
【０１２２】
完全性のため、立方体相関関数および形状変更された相関表面の両者を使用するアルゴリズム"9B"によって事後処理線形補正がナビゲーション誤差出力に適用されるが、その結果は、図２９の(Ａ)および(Ｂ)に示されるものよりさほど改善されていない。一見、このようなその他の性能改善手法は不必要であるようにみえるが、図１４の用紙サンプルに関して得られる特定の補正関数(22a)および(22b)はその他の用紙サンプルに対して同様に使用できることはほとんどあり得ない。補正係数{p_mn}および{q_mn}は、うまく定義される関数形式を通して２次ボウル形係数b₂₀、b₁₁およびb₂₀に依存する。ナビゲーション問題に対する最も一般的解決策は、アルゴリズム"9B"を立方体相関関または形状変更ボウルのいずれかに適用し、基準フレームが取得された後計算される２次表面形状係数を使用して実行時に決定される係数を用いて線形補正関数を適用することである。
【０１２３】
減少されたデータセットを使用する並進運動計算
上述の修正に対する減少された範囲の代替方法セットの詳細な導出は、図３１に示される並進運動の検証を必要とする。最も最近のマイクロステップの起点を中心とする平方ピクセルの境界内に変位は制限されるが、変位は２次テーラー級数近似(18)が有効でなくなるほど大きい。セル０、３、４および５の相関データは式(18)による正確な表現を可能にするかもしれないが、３×３アレイにおけるその他の５つのセルはそうではない。アルゴリズム"9B"に対する２つの拡張ファミリが存在する。すなわち、x軸ならびにy軸に近い大きい変位に対する使用のための６セル・アルゴリズム、および、平方ピクセル境界のコーナーへの偏位運動のための４セル方法という２つである。
【０１２４】
６セル・ナビゲーション・アルゴリズム
減少範囲データセットを使用する並進運動計算に対する本発明の手法は、それが最小二乗法に基づいているという点において全９セル・アルゴリズムに関するものと本質的に同じである。しかしながら、正のｘ軸に近い中心セルの範囲内の大きい並進運動の６セル・ケースに関して図３２の(Ａ)に示されているように、２次近似を最も満たしそうな相関セルに対してのみ平方偏差を総和することによってx²が得られる。
【０１２５】
更に、ボウルの形状は一定であり、最も最近のマイクロステップの直後に収集される自己相関データから計算されるb₁₁、b₂₀およびb₀₂という値が保持され、値b₁₀およびb₀₁のみの変化が許容される。図３２の(Ａ)に示されるケースにおいて、b₁₀およびb₀₁は次式(23a)および(23b)の通りである；
b₁₀=2[(C₄+C₅+C₆)-(C₀+C₃+C₇)]-1/2*b₂₀ (23a)
b₀₁=3/2*[(C₃+C₅)-(C₆+C₇)]-1/2*b₁₁ (23b)
これらの係数は、次に、式(8a)ならびに(8b)へ直接代入され、変位ベクトル{X₀,Y₀}が得られる。その他の３つの６セル・データ・サブセットに関する計算は、図４２の(Ａ)ならびに(Ｂ)、および図４３の(Ａ)ならびに(Ｂ)にリストされている。
【０１２６】
４セル・ナビゲーション・アルゴリズム
図３２の(Ｂ)に示されているような、右上象限に近い中心セルの範囲内で大きい並進運動が発生する４セル・ケースに関する同様の計算が次式(24a)なびに(24b)の線形係数を生成する；
b₁₀=+3[(C₄+C₀)+(C₅-C₃)]-1/2*(b₂₀+b₁₁) (24a)
b₀₁=+3[(C₄+C₀)-(C₅-C₃)]-1/2*(b₀₂+b₁₁) (24b)
図３２の(Ａ)ならびに(Ｂ)は、減少されたデータセット・セルのマッピングの例を示す。図３２(Ａ)は、正のx軸の近くの中心セルの範囲内の大きい並進運動に関する図１８において示された９セル・マッピングの６セル減少を示す。X²は、図示されている６つの右側セルだけの合計によって計算される。図３２の(Ｂ)は、図３１に示されるような右上象限の近くの中心セルの範囲内の大きい並進運動に関する図１８において示された９セル・マッピングの４セル減少を示す。X²は、図示されている４つの右上セルだけの合計によって計算される。
【０１２７】
式(8a)ならびに(8b)に代入すれば、次式(25a)ならびに(25b)のような並進運動コンポーネントを得る；
x₀=1/2-3[(b₀₂-b₁₁)(C₄-C₀)+(b₀₂+b₁₁)(C₅-C₃)]/(b₂₀b₀₂-b₁₁ ²) (25a)
y₀=+1/2-3[(b₂₀-b₁₁)(C₄-C₀)+(b₂₀+b₁₁)(C₅-C₃)]/(b₂₀b₀₂-b₁₁ ²) (25b)
その他の３つの象限に関する計算は、図４２の(Ａ)ならびに(Ｂ)、および図４３の(Ａ)ならびに(Ｂ)にリストされている。
【０１２８】
効果的位置予測値のクラス
図１９の(Ａ)ならびに(Ｂ)に示されているように、上述示されたナビゲーション・アルゴリズムは、特定マイクロステップの起点を中心とする１平方ピクセルの範囲内に変位が限定される場合に、最も正確である。言い換えると、(５×５セル・グリッドにおいて)その最小値を含むセルが識別されることができる十分な正確性を持つ相関表面の最小値の位置を前もって予測して、次に、このセルを中心とする９つの相関数をナビゲーション・アルゴリズムへの入力として選択することが望ましい。原理的には、２５セル・グリッドにおいて最小相関値を含むセルが識別され、表面極小がこのセルに位置していると推定される。図３３の(Ａ)および(Ｂ)は、２次式相関関数(k=2)ならびに図１４の用紙サンプルを使用して得られる相関数およびこの"極小セル"予測値へのアルゴリズム"9B"の適用の結果生まれるナビゲーション誤差を表している。注：ピクセル境界の近くには、電子回路ノイズに起因する相関値の変動によって生じる偽の位置計算が頻繁に発生する。
【０１２９】
線形最小２乗法による解決手法
上記の代わりに、上記導入された最小二乗法に基づく単純な線形予測アルゴリズムのクラスが、以前のフレームの既知の座標を使用して次のフレームの変位座標を推定するように設計される。共通の空間上の起点を共有し時間的に一様にサンプルされる(すなわちt_k=kΔt、kε{-m,...,-1}である)m個の位置測定値
{r(t_-m),...,r(t_-1)}を所与として、時間t₀=0における推定値が求められる。xならびにｙ座標の時間に対する関数依存性は、次の式(26)の多項式としてモデル化される。
【０１３０】
【数１１】

但し、n<mである。多項式の次数nは、ナビゲーション機構の真の運動が予測される正確度を決定する。例えば、n=2の選択は、次式[数１２]という仮定と同義語である。
【０１３１】
【数１２】

ノイズがなければ、nの増加は、式(26)がr(0)を予測する忠実性を常に増加させる。各位置測定は、同じ標準偏差σ₀によって特徴づけられる統計的誤差によって制限され、x₂は、mならびにnの各選択毎に次式(27)として定義される。
【０１３２】
【数１３】

式(27)の最小値において、パラメータ・セット{α_j}のメンバに関する勾配は、次式(28)に従って同等に消滅しなければならない。
【０１３３】
【数１４】

従って、n+1の独立の方程式がn+1の未知のパラメータにおいて得られる。それらはp_n(0)=α₀を得るように代数的に解を得ることができる。そのような解p_n(0)=α₀の各々は、m個の過去の位置測定の線形結合であり、そのため、時間t₀=0における予測される位置は、次式(29)の形式を持つ。但し、定数{β_k}はα₀に対する解から単純に読み取られる。
【０１３４】
【数１５】

【０１３５】
シミュレーション結果および精度／正確性妥協
４つの過去の位置測定値(すなわちタップ)を使用して、次式(30)の多項式によって予測される位置とこれらの測定値の間の平方偏差の総和を最小にする２次多項式が導出される；
r_4,2=(1/4)*(3r_-4-5_r-3-3_r-2+9_r-1) (30)
図３４の(Ａ)および(Ｂ)は、シミュレーションされた位置データと
予測値x_4,2≡x・r_4,2の対応する出力の比較を示している。ゼロ平均を持つガウス・ノイズおよび0.05という標準偏差を関数cos(πt)に加算し、次にその関数を(間隔あたり４０のサンプル・ポイントを所与として)時間間隔Δt=0.05でサンプリングすることによって、シミュレーションされたデータが生成される。図３４の(Ａ)は、ノイズのあるサンプルにおける変動をx_4,2がどのように追跡することを試みるかを示し、図３４の(Ｂ)は、このノイズが予測値の出力とその基礎をなす"真の"位置の間の相違に及ぼす影響を示す。図３５の(Ａ)に示されているように、８タップ予測値x_8,2によってかなり良好な性能が提供される。モデル多項式の次数を２から４へ増加させることによって予測値の精度がさらに強化されると考えられるが、図３５の(Ｂ)は、８タップ予測値X_8,2に関してそのようなことはないことを示している。
【０１３６】
予測値出力の標準偏差を計算することによって、この直観に反した結果を定量化することができる。式(29)によって予測されるx_m,nまたはy_m,nいずれかの値の精度は、過去の測定における統計的誤差に起因する不確実性によって制限される。連続的測定における統計的誤差は相互に相関しないと仮定されるので、標準誤差伝播式(31)を使用して予測における不確実性wの計算が可能となる。
【０１３７】
【数１６】

【０１３８】
式(30)によって与えられる予測値に関して、σ_4,2=31^1/2σ₀/2=2.8σ₀である。図３５の(Ａ)によって暗に示されるように、一層多数の前の位置測定値を使用することによってこの不確実性を減少せせることができる。例えば、
σ_8,2=(109/5)^1/2σ₀=1.4σ₀である。しかしながら多項式の次数をn=4に増加させると、図３５の(Ｂ)に示されているように、不確実性が
σ_8,4=(1231/56)^1/2σ₀=4.7σ₀
と増加する。
【０１３９】
この結果は、一層高い次数のモデル多項式が急速に変化するデータの一層正確な表現のために選択されるという事実によって説明される。従って、多項式は、電子的ノイズに起因する偽の位置変動に対して一層敏感でなければならない。これらの傾向のすべてが図３６に明確に示されている。
【０１４０】
線形モデル多項式を使用して一層低い不確実性を達成することも可能であるが、低い次数の多項式は低ノイズ環境においてさえ真の位置変更を正確に予測することができない可能性のあることを認識することは重要である。図３７の(Ａ)は、予測値x_8,1の出力を"真"の位置と比較している。この予測値によって生成される正確度は図３５の(Ａ)において示されたx_8,2の不確実性より劣っている点は明らかである。これは、線形モデル多項式が、８つの先行測定によってカバーされる長い時間間隔の間x(t)に関する近似が貧弱なことによる。従って、シミュレーションに対して選択される特定のx(t)およびノイズ・モデルに関して図３７(Ｂ)に示されるような比較的短い時間間隔をカバーするように以前の測定値の数を減少させることによって正確性を増加させることができる。
【０１４１】
従って、精度増加(すなわち一層低いノイズ反応性)と正確性の間の複雑な妥協は次のように要約される：
＊精度は、過去のデータ・ポイント(タップ)mの数の増加と共に、増加し、モデル多項式次数nの増加と共に、減少する；
＊正確度は、モデル多項式次数nの増加と共に、増加し、過去のデータ・ポイント(タップ)mの数の増加と共に、減少する。
【０１４２】
マクロステップ座標に関する平滑化アルゴリズムのクラス
線形最小２乗法による解法
マクロステップの保存された座標が既知である場合、８０マイクロ秒捕捉間隔の倍数で一様にサンプルされた隣接ポイントの座標を体系的に使用してマクロステップの座標を円滑化することによって、正確性を顕著に増加させることができる。円滑化の手法は上述の予測手法に類似している。共通の空間上の起点を共有し時間的に一様にサンプルされる(すなわちt_k=kΔt、kε{-m,...,0,...,m}である)2m+i位置測定値{r(t,m),...,r(0),...,r(t,m)}からなるセット、r(0)に対する値を所与とすれば、時間t₀=0における位置が求められる。この場合も、xならびにy座標の時間に対する関数依存性は式(26)によるn<2m+1次の多項式としてモデル化され、各位置測定値は、同じ標準偏差σ₀によって特徴づけられる統計的誤差によって制限されると仮定される。mならびにnの選択の各々に関するx²は次式(32)として定義される。
【０１４３】
【数１７】

【０１４４】
多項式係数{α_j}に関する上式(32)の勾配は同等に消滅する必要がある。この場合もまた、n+1の未知のパラメータにおけるn+1の独立した方程式が得られ、それらは、代数的にp_n(0)=α₀を得るように解かれる。そのような解の各々は、2m+1の記録された位置測定値の線形組み合わせであるので、時間t=0における位置の平滑化された値は、次式(33)という形式を持つ。
【０１４５】
【数１８】

【０１４６】
実際には、t=0に関する過去の測定値の対称配置が、奇数べき乗を持つ式(26)の項によって作成されるr_m,n(すなわちα₀)に対する貢献を削減する。それゆえ、例えば、l∈Z>0として、r_m,2l+1=r_m,21である。しかし、ｊ∈Z>0の場合、一層高次の係数α_jは一般にユニークである。
【０１４７】
シミュレーション結果および精度／正確度の妥協
例えば、特定のケースにおいて、９つの位置測定値を使用して、これらの測定値と次の多項式(34)を使用して計算される平滑化された位置の間の平方偏差の和を最小にする２次多項式が導出される：
r_4,2=(1/231)[59r₀+54(r₁+r_-1)+39(r₂+r_-2)+14(r₃+r_-3)-21(r₄+r_-1)] (34)
図３８の(Ａ)および(Ｂ)は、シミュレートされた位置情報と平滑式
x_4,2≡x・ｒ_4,2の対応する出力を比較している。シミュレートされたデータは、ゼロ平均を持つガウス・ノイズならびに0.05という標準偏差を関数cos(πt)に加算して、次に、(間隔あたり40サンプル・ポイントを所与として)時間間隔Δt=0.05でその関数をサンプリングすることによって、生成される。
【０１４８】
図３８の(Ａ)は、x_4,2の９タップがノイズのあるサンプルにおける変動の典型的サイズをどのようにした大幅に減少させたかを示し、図３８の(Ｂ)は、基礎をなす"真の"位置が合理的に復元されたことを示している。１７タップ平滑式x_8,2によってなおも性能改善が得られることが図３９の(Ａ)に示されている。対応する予測値に関するケースと相違して、モデル多項式の次数の２から４への増加が、４次モデル多項式の正確度の増加のため、性能のなんらかの改善を生むことを図３９の(Ｂ)は示している。
【０１４９】
最後に、統計的誤差に対する感度に起因する_Xm,nまたはY_m,nいずれかの平滑化された値における不確実性が隣接測定において測定される。連続測定における統計的誤差は相互に相関しないと仮定されるので、次式(35)の標準誤差伝播式を使用することが可能とされる。
【０１５０】
【数１９】

【０１５１】
式(34)によって与えられる平滑式の場合、σ_4,2=(59/231)^1/2σ₀＝0.51σ₀である。図４０は、この計算をより広範囲の例に広げている。注：統計的不確実性への最小の感度は、β_k=1/(2m+1)、k∈{-m,...,0,...,m}として、単純平均n=0によって与えられる。しかしながら、１つの測定から次の測定への位置変更を無視することができるほどナビゲーション機構の速度が遅いという極端なケースにおいてのみこの平滑式の正確度は満足できる。例えば、図４１の(Ａ)は、１７タップ平均(すなわち次数ゼロ)の円滑計算から生じる正確度の大幅な悪化を示す。図４１の(Ｂ)は、９までタップ数を減らすことによって正確性の改善が達成されることを示しているが、(図４０に示されているような)ノイズに対する感度の増加という犠牲を払わなければならない。精度の向上(すなわちノイズ感度の減少)と正確性の改善の間の妥協は、本発明によって導出される円滑化アルゴリズムに同等にうまく適合する。
【０１５２】
ナビゲーション経路再構築
基準フレームの説明
ナビゲーション機構／スキャナ・システムにおいて、３つの別々のタイプの４つの主要基準フレームが存在する：
(1)ナビゲーション機構基準フレーム
各々がそれ自身の座標を持つ２つのナビゲーション光検出器アレイが存在する。ナビゲーション機構の各々の座標系の起点は、対応する光検出器アレイの中心に位置する。図４５の(Ａ)および(Ｂ)は較正基準フレームに埋め込まれるナビゲーション機構の座標系を示す；
(2)較正基準フレーム。較正基準フレームは本質的にはスキャナ基準フレームである。このフレームにおいて、ナビゲーション機構ならびにＣＩＳアレの両者は特定の方向を持つ指定された座標に固定される。較正座標空間は２つの左手単位ベクトル{u v}によって張られる。これら２つのベクトルは、ナビゲーション機構１の起点をナビゲーション機構２の起点へ結ぶベクトルに対してそれぞれ垂直および平行である。従って、いかなるベクトルも、較正フレームにおいてr=uu+vvによって表現されることができる。ナビゲーション機構１の基準フレームの起点はr=0(較正フレームの起点)に位置し、一方、ナビゲーション機構２の基準フレームの起点はr=Dvに位置する。ナビゲーション機構１の座標系の軸は、較正フレームの軸に対して角度θ₁傾き、ナビゲーション機構２の座標系の軸は、較正フレームの軸に対して角度θ₂傾いている。注：図４５において回転角度θ₁ならびにθ₂は正として示されているが、図４６においては負として示されている。
【０１５３】
用紙基準フレーム
超小型軽量スキャナが最初に紙の上に置かれ始動される時、較正フレームは走査されるべき表面の基準フレームと一致する。この時、第１ならびに第２のナビゲーション光検出器アレイの起点の座標は、較正ならびに紙基準フレームの両方においてそれぞれ{0,0}および{0,D}である。しかしながら、図４６の(Ｂ)に示されるように、走査の間の後の時間に、較正フレームは用紙フレームに対して平行移動および回転する。これは２つの定数左手単位ベクトル{x _p y _p}によって張られる。ナビゲーション機構１ならびにナビゲーション機構２のフレーム起点は、一般に、{x_p1,y_p1}ならびに{x_p2,y_p2}に位置する。それゆえ、図４７に示されるように、紙基準フレームにおける較正単位ベクトルu vのコンポーネントは、次のように計算される。
【０１５４】
(a)ベクトル差Δr≡r_p2-r_p1を計算し、次にその結果をDによって除算してvを求める;
(b)x_p2=x_p1およびy_p2-y_p1=Dであるとして、vに直角でx _pに等しい単位ベクトルuを発見する；
かくして、次の(36a)ならびに(36b)の変換式が得られる；
u=[(y_p2-y_p1)/D]x _p-[(x_p2-x_p1)/D]y _p (36a)
v=[(x_p2-x_p1)/D]x _p-[(y_p2-y_p1)/D]y _p (36b)
【０１５５】
従って、単にナビゲーション・アレイの既知の位置および式(36a)ならびに(36b)を使用して用紙フレームにおけるuならびにvの両者を表すことによって、較正フレームにおいてr=uu+vvによって表現されるいかなるベクトルも用紙座標において三角法を用いずに書き直すことができる。
【０１５６】
ナビゲーション機構→フレーム較正フレーム
較正フレーム座標に関して２つのナビゲーション機構の各々によって記録される変位を表す変換を決定する際に、２つの光検出器アレイの両方のそれぞれの倍率、およびナビゲーション機構２の右手座標系を考慮しなければならない。最初に、図４５の(Ａ)を参照すれば、較正フレームにおけるナビゲーション機構１の変換ベクトル{Δu₁,Δv₁}のコンポーネントが、計算されたナビゲーション機構変位ベクトル{Δx₁,Δy₁}という観点から計算される。回転角度θ₁は製造の時点で固定される定数であり、従って、ナビゲーション１から較正フレームへ座標変換は、一定の２次元回転マトリックスを使用して実行することができる。次に、その結果がナビゲーション１の無次元の一定の拡大率m₁によって拡大され、次式(37a)ならびに(37b)が得られる。但し、c1≡cosθ₁、s₁≡θ₁である：
Δu₁=m₁(c₁Δx₁+s₁Δy₁) (37a)
Δv₁=m₁(-s₁Δx₁+c₂Δy₁) (37b)
同様に、ナビゲーション機構２に関して、次式(38a)ならびに(38b)が得られる。但し、m₂はナビゲーション２の無次元の一定の拡大率、c₂≡cosθ₂である：
Δu₂=m₂(c₂Δx₂+s₂Δy₂) (38a)
Δv₂=m₂(s₂Δx₂+c₂Δy₂) (38b)
注：ナビゲーション機構２の極性反転がΔy₂の符号の変更によって暗黙裡に考慮されている。
【０１５７】
m₁、m2、c₁、s₁、c₂およびs₂は製造時に較正(例えば固定または測定)することが可能であり、それらの適切にデジタル化された値をＲＯＭに組み込むことは可能である。式(37a)−(38b)は、拡大倍率定数を３角法定数に吸収することによって、また、式(36a)ならびに(36b)の明示的除算を削除するためこれらの定数の中に1/Dという別の因子を吸収することによって、更に単純化することができる。
【０１５８】
較正フレーム→用紙フレーム
較正フレーム座標で表されるナビゲーション変換ベクトルを所与とすれば、用紙基準フレームにおける各ナビゲーション機構の起点の位置は、上述の手法を使用して更新される。最初に、較正フレームにおけるナビゲーション機構起点の計算された位置に動的に適用することができる有用な制約式が開発される。
【０１５９】
図４８に示される較正フレームにおいて、ナビゲーション機構１ならびに２の並進運動した起点の座標は、それぞれ{Δu₁,Δv₁}{Δu₂,D+Δv₂}である。２つのナビゲーション機構の間の距離は一定のままであるので、次式(39)が成り立つ：
D²=(Δu₂-Δu₁)²+(D+Δv₂-Δv₁)² すなわち
(Δv₂-Δv₁)²+2D(Δv₂-Δv₁)+(Δu₂-Δu₁)²=0 (39)
(Δu₂-Δu₁)²<<D²であるケースにおいてΔv₂-Δv₁に関して式(39)を解けば、次式(40)が得られる。
【０１６０】
【数２０】

【０１６１】
急速な相対的回転という極端なケースにおいては、1/200inほどの大きさの|Δu₂-Δu₁|を得ることが可能である。次に、D=3inの場合、次式が成り立つ。
【０１６２】
【数２１】

【０１６３】
従って、ナビゲーション機構を分離する距離は一定のままであるという制約は、Δv₁=Δv₂という条件にほぼ等しい。１つの実施形態において、各ナビゲーション機構の並進運動は、ナビゲーション・アルゴリズムの位置予測値モジュールと比較され、次に、予測値に最も近いΔvの値が選択される。代替的には、各ナビゲーション機構の運動(例えば速度と加速度をリアルタイムで計算する)を調べ、次に、(フルモーションの実績に基づいて)正しい変位を与える可能性の高いナビゲーション機構を特定して、対応するΔvを両方のナビゲーション機構に適用することもできる。
【０１６４】
このような調整が行われ、式(40)の基準が満たされた後、次式(41a)ならびに(41b)を使用して用紙フレームにおけるナビゲーション機構変位が計算される：
Δr_p1≡{Δx_p1,Δy_p1}=Δu₁ u+Δv₁ v (41a)
Δr_p2≡{Δx_p1,Δy_p2}=Δu₂ u+Δv₂ v (41b)
但し、用紙基準フレームにおける単位ベクトルuならびにvは、式(36a)−(36b)によって定義される。換言すれば、用紙フレームにおけるナビゲーション機構変位を与える方程式は、較正フレームにおける対応する公式と同じように見える。しかし、式(41a)ならびに(41b)においては、単位ベクトルuならびにvは定数単位ベクトルではなく、用紙基準フレームにおいてそれらは式(36a)−(36b)に従ってスキャナ・ヘッドと共に並進およびび回転する。
【０１６５】
次に、ナビゲーション機構の起点座標は、Δr_p1ならびにΔr_p2に前のナビゲーション機構位置r_p1ならびにr_p2をそれぞれ加算することによって次式(42a)−(42d)のように更新される：
x'_p1=x_p1+(Δu₁/D)(y_p2-y_p1)+(Δv₁/D)(x_p2-x_p1) (42a)
y'_p1=y_p1+(Δu₁/D)(x_p2-x_p1)+(Δv₁/D)(y_p2-y_p1) (42b)
x'_p2=x_p2+(Δu₂/D)(y_p2-y_p1)+(Δv₂/D)(x_p2-x_p1) (42c)
y'_p2=y_p2+(Δu₂/D)(x_p2-x_p1)+(Δv₂/D)(y_p2-y_p1) (42d)
1/Dという因子を式(37a)において使用される三角法定数に吸収することによって、式(42a)−(42d)は更に簡略化される。
【０１６６】
ＣＩＳ終端点座標の更新
図４６の(Ａ)から、ナビゲーション機構位置が更新された後、ＣＩＳ終端点の座標は容易に決定することができる。(ナビゲーション機構の位置がＣＩＳアレイの終端点に依存しないので、このプロセスは必要に応じてオフラインで実施すことができる)。較正フレームにおいて、ＣＩＳ終端点１ならびに２は、符号付きベクトル{a₁,b₁}ならびに{a₂,b₂}だけナビゲーション機構１ならびにナビゲーション機構２からそれぞれ変位される。用紙フレームにおいて、ＣＩＳ終端点の位置は次式(43a)ならびに(43b)によって与えられる：
r'_c1=r'_p1+a₁ u+b₁ v (43a)
r'_c2=r'_p2+a₂ u+b₂ v (43b)
但し、r'_p1≡{x'_p1}、r'_p2≡{x'_p2,y'_p2}であり、uならびにvは、式(42a)ならびに(42b)を使用して以前に計算されたナビゲーション起点の更新された座標軸を使用して式(36a)ならびに(36b)によってそれぞれ与えられる。従って、
x'_c1=x'_p1+(a₁/D)(y'_p2-y'_p1)+(b₁/D)(x'_p2-x'_p1) (44a)
y'_c1=y'_p1+(a₁/D)(x'_p2-x'_p1)+(b₁/D)(y'_p2-y'_p1) (44b)
x'_c2=x'_p2+(a₂/D)(y'_p2-y'_p1)+(b₂/D)(x'_p2-x'_p1) (44c)
y'_c2=y'_p2+(a₂/D)(x'_p2-x'_p1)+(b₂/D)(y'_p2-y'_p1) (44d)
上式(44a)−(44d)は、ＣＩＳ変位定数a1、b1、a2およびb2に1/Dという共通因子を吸収することによって更に簡略化することができる。
【０１６７】
計算アルゴリズム
最初に、製造時に固定または正確に計測される数量から全体を構成され、明示的除算演算子に関する必要性(または同様であるが1/Dによる除算の必要性)を排除する(ＲＯＭに記憶される)定数の最適化されたセットが定義される：
C₁=(m₁/D)cosθ₁ C₂=(m₂/D)cosθ₂
S₁=(m₁/D)sinθ₁ S₂=(m₂/D)sinθ₂
A₁=a₁/D B₁=b₁/D
A₂=a₂/D B₂=b₂/D
加えて、必要とされる算術演算の数を減らすことによって計算を単純化する４つの一時的変数が図４９によって定義される。
【０１６８】
最良のケースにおいては、S₁=S₂=0およびA₁=A₂=0であるように、従って、ＣＩＳアレイが較正フレームにおけるナビゲーション機構起点に対してu方向に並進運動しないように、ナビゲーション機構光検出器アレイが完全に配列される。図４９に示されるステップのシーケンスの検証および各ステップのために必要とされる２進算術演算の数の推定が、最悪および最良の両方のケースにおいて、以下の表１に示される結果を生む。これらの結果は、不良位置合せと並進運動を最小にするように製造プロセスを注意深く制御することによって、２進算術演算を３０%以上減らすことができることを示している。いずれのケースにおいても、除算も乗算も必要とされず、(ＣＩＳ終端点座標を計算する)第４のステップはオフラインで実施することができるので、リアルタイム・ナビゲーション経路再構築の計算コストは比較的小さい。
【０１６９】
【表１】

【０１７０】
ナビゲーション・プロセッサ８０の出力８６における位置タグ付きデータストリームは、先ず、XなびにY両軸における連続性を与えるメモリ位置をイメージがうめることを可能にするイメージ空間に記憶される。従って、イメージの取得は、オリジナルの左上隅から右下隅への走査に制限されない。各イメージ・ピクセルが任意の開始位置からの相対的(X,Y)変位に関連づけられるので、イメージは、XおよびYにおいてイメージ・メモリの最大サイズに展開することができる。
【０１７１】
イメージ形成センサ２２は、走査装置がオリジナル上を移動するにつれ、刻時(クロック)される。刻時(クロック)動作は、センサの最も速く移動するエレメントがピクセル変位あたり少なくとも１回サンプルをとることを保証する。図６に関連して注記されたように、イメージ捕捉の間走査装置１０が大きく曲がる場合、イメージ形成アレイの一方の端は他方の端より急速に並進運動し、そのため、相対的に速度の遅い方の端ではピクセルのサンプリングが過大となる。この状況は、イメージ空間における特定のピクセル位置において、(グレイスケールの場合)最も最近の読み取りを記録することによるか、あるいは、(バイナリ・イメージの場合)論理ＯＲモードで記録することによって、処理される。
【０１７２】
次の動作は、位置タグを付けられた増分をマップする。１つの実施形態において、増分の端点は１つの線分によって結ばれる。イメージ形成センサ２２の各ピクセルの距離は固定的であるので、その線分に対するピクセルの物理的位置を計算することができる。各ピクセルの物理的位置を決定する１つの手法は、Bresenhamラスタ線手法の修正である。この修正において、イメージ形成センサにおけるピクセルのアレイは固定的であるので、線分ループも同じように固定的である。すなわち、通常のBresenhamアルゴリズムにおいては、線ループにおける繰返し数は、delta_xならびにdelta_Yのいずれか大きい方、すなわち、max(delta_x,delta_y)であるが、修正アルゴリズムの場合、ループがN回繰り返されるように、max(delta_x,delta_y)が習慣的に使用される場合には、アレイに沿ったピクセルの数(N)が使用される。以下のプログラムはこのアルゴリズムを記述する。
【０１７３】
【表２】

【０１７４】
このようにして、Nピクセルからなるイメージ形成センサの終端点であるラスタ上の２つの点(xa,ya)ならびに(xb,yb)を所与として、各ピクセルが読み取られるべき場所のラスタ上の点(x,y)を連続的に検出することがこのプログラムの目的である。これらの点は、終端点aならびにbを結ぶ直線に対する最良の近似を形成する。xとyの差を取り出す。aとbの間の距離の符号から、直線が横切る時xおよびyは増分または減分されるか決定する。２つのレジスタx_errならびにy_errをゼロにセットした上、x=xaならびにy=yaから始めて、ループを開始する。次に、(x,y)における値を読み取って、get_pixel()を使用してそれを出力ラスタに書く。線形イメージ・センサがナビゲーションの半分の解像度を持つとすれば、センサにおけるピクセル数および出力ラスタにおける位置に関してi/2、x/2、y/2を使用する。delta_xならびにdelt_yをそれぞれの誤差レジスタに加算して、次に、誤差レジスタがNを越えていないかどうか両方のレジスタを調べる。越えていれば、レジスタからNを減算して、その増分だけxまたはyを変更する。誤差レジスタがNを超えていなければ、引き続きxまたはyの現在値を使用する。ループはN回実行されるまでプロセスは続く。
【０１７５】
次のステップは、オーバーラップしている領域の範囲内で連続イメージ走査帯を縫合することである。これは、累算されたナビゲーション誤差を識別および修正し、残存する誤差があればそれをマスクするように実行される。このマスク動作は白い背景上の黒い印刷の領域において実行できる。例えば、白い空間領域すなわち所与のしきい値以上の強度を持つ領域においてのみ縫合を行うことによって実行できる。(破棄されるべき)オーバーラップ領域の重複データの識別の方法およびナビゲーション誤差の測定および補正の方法を以下に記述する。
【０１７６】
イメージ走査帯の縫合技法は、走査に関連する業界において既知のものである。これらの技法は、典型的には、一対の完全なイメージ帯を必要とし、２つの帯の位置を定める単一の大域変換を実行する。しかし、この場合、連続的ナビゲーション・データが縫合に必要な位置決め情報を提供する。ナビゲーション信号が誤差を累算する傾向があるので、特徴オフセットの分析から導出される補正信号をフィードバックすることによってナビゲーション信号は連続的に修正される。
【０１７７】
領域の範囲内の特徴を相関させることによってナビゲーション補正が計算されるので、２つのイメージ帯を縫合するためにはなんらかのオーバーラップ領域が必要である。図１１に示されている状況を考察する。ここでは、走査帯＃１が戻りの帯＃２のパスによって再サンプルされている。時間Tにおいて、部分的帯が走査されている。図１２は、このオーバーラップ領域１０８を強調表示している。図１２に示されているように、帯＃１の収集の間、帯の下側エッジに沿って、タグ１１０、１１２、１１４という位置の四辺形イメージ・セグメント(以下"位置決めタイル"と呼ぶ)が周期的にラベル付けされる。後のパス(帯＃２)において、帯＃１のタグ付き領域の上の余分なオーバーラップ領域１０８は、どこを刈り取るべきかを決定するナビゲーション情報を使用して刈り取られる。帯＃２において各セグメント長が取得される毎に、"余分"が刈り取られた後、帯＃１の位置決めタイルが、帯＃２の残るべき領域の上部に配置される。
【０１７８】
ナビゲーション・データが完全であれば、タグ＃１の位置と帯＃２の再走査されたタイルの位置の間にオフセットは存在しない。実際には、最後の位置決めが実行された以後なんらかのナビゲーション誤差が累算している。これら２つのタイルの間のオフセットは、総累算誤差を最小限にとどめるため、そのデータに関連する将来のナビゲーション位置−タグを更新するため使用される補正因子を生成する。このように、ナビゲーション・データにおける総累算誤差は、走査帯のオーバーラップ領域における明白なゆがみを派生させるような大きさに増大することを防止される。
【０１７９】
帯＃１および帯＃２は単一のイメージを生成するように結合されるので、帯＃２がオリジナルの位置合わせタイルの位置に来るまで、オリジナルの位置合わせタイルのコピーはバッファに一時的に保存される。この相関のため位置決めタイル全体を使用することができるが、階調イメージの長方形タイル(例えば１５×１５ピクセル)から成る高周波数コントラストの小さい領域(すなわち"特徴")が、帯＃１の位置合わせの範囲内に配置され、バッファに保存される。この特徴の位置が２度目に交差される場合、保存された特徴の位置と帯＃２における同じ特徴の間のオフセットが、２つの特徴を一致させるために必要なナビゲーション補正信号を生成する。その他の相関手法を利用することもできるが、許容可能な手法は、"平方差の総和"相関である。特徴のオリジナルの位置の周囲に小さい検索領域が定義され、相関係数が次の式によって決定される。
【０１８０】
【数２２】

【０１８１】
但し、T_i,jは帯＃１からの特徴の階調値を示し、I_i+k,j+1は帯＃２から新しく取得される特徴の階調値を示す。インデックスiなびにjは特徴の範囲内の位置を指定し、一方、インデックスkならびにiは、(検索領域の範囲内に残るように制約される)並進運動オフセットの大きさを指定する。結果として得られる相関アレイの中の最小エレメントが２つの特徴の間のオフセットを示す。このボウル形結果の最小値を見出すため補間を使用してサブピクセルの位置的正確度が得られる。
【０１８２】
自己相関法の正確度を改善するので、位置決めタイルの範囲内の特徴がイメージ分散を最大にするように選択される。１つの可能な実施形態において、領域の範囲内の位置のサブセットだけが考慮される。そのような位置１１６、１１８、１２０、１２２および１２４は、位置決めタイルの主軸１２６ならびに１２８(領域を定義する線分の対向する中点を結ぶ線分)に沿って位置するように、図１３に示されている。これらの位置は、交点、および、交点と軸の中点の半分の位置、においてサンプルされている。位置１１６、１１８、１２０、１２２および１２４の各々に関して、次式を使用して偏差VAR_k,iが計算される。
【０１８３】
【数２３】

【０１８４】
最終的代表イメージにおける明らかなひずみを防ぐため、誤差推定が徐々に適用される。すなわち、線形センサ・データの新しい行がメモリへロードされる毎に、誤差全体の精算が行われるまで、小さい固定的大きさのステップで"位置タグ"が修正される。
【０１８５】
好ましい実施形態において、イメージ再構築、縫合ならびにイメージ管理に関する処理エレクトロニクスが、図１の走査装置１０を定義する格納容器の範囲内に収納される。このように、走査されたイメージはイメージ・ディスプレイ１６に即刻提示されることができる。走査装置は、位置タグを付けられたイメージ・データを記憶するメモリを含むが、処理ならびにファイル管理エレクトロニクスおよびファームウェアを必ずしも必要としない。
【０１８６】
図３を参照して注記したように、ナビゲーションならびにイメージ形成センサ２２、２４および２６は、好ましくは、軸回転部材２０上に装着される。１つの実施形態において、軸回転部材は、少なくとも１つの弾性材によって格納容器の剰余部分に接続される。この場合、弾性材の一端は格納容器の静止部に接続され、他方の端は軸回転部材に接続される。弾性材はちょうつがいのはたらきをする。このように、軸回転部分は、摩擦エレメントを使用せずに、"浮く"ことを可能にされる。電力制御およびデータ信号は、電磁干渉を最小にするようにシールドされた屈曲ケーブルを介してセンサへ導くことができる。軸回転部材を軸回転するように接続するその他の方法を使用することは可能である。軸回転部材が削除され、センサが格納容器の固定位置に取り付けられる場合、イメージ捕捉の間、走査装置を過度に傾けない配慮が必要である。この実施形態においては、照光ならびに光学エレメントの設計には十分な注意が払われなければならない。
【０１８７】
以上本発明の特定の実施形態が提示および記述されたが、本発明の一層広範囲な局面において本発明の理念を逸脱することなく上記実施形態に種々の変更ならびに修正を加えることができる点は当業者に明らかであろう。例えば、手持ち型スキャナが記述されているが、本発明のナビゲーション方法は、手持ち型スキャナにあるいはスキャナにさえ制限されない。実際、本発明のナビゲーション方式は、ナビゲーション・ツールとしてセンサまたはその他の検出器を利用するいかなる装置にも適用することができる。
【０１８８】
本発明には、例として次のような実施様態が含まれる。
(1)センサ・アレイのナビゲーション位置を取得する方法であって、上記センサ・アレイを介して基準フレームを取得するステップと、上記センサ・アレイを介してサンプル・フレームを取得するステップと、上記サンプル・フレームおよび上記基準フレーム両方の基準特徴の間の関係を表す相関データを生成するステップと、上記相関データに基づいて上記基準フレームに対する上記サンプル・フレームの基準特徴の相対的変位を決定するステップと、を含み、上記相対的変位を決定するため、一般的２次元テーラー級数展開式としてモデル化される相関データの相関表面の大域極値が使用される、ナビゲーション位置取得方法。
【０１８９】
(2)上記一般的２次元テーラー級数展開式が２次式である、上記(1)に記載のナビゲーション位置取得方法。
(3)上記相関データが、更に、相関関数を使用して生成される複数の相関係数を含む、上記(1)に記載のナビゲーション位置取得方法。
(4)上記相関係数と上記２次元テーラー級数展開式の間の線形マッピングを適用するステップを更に含む、上記(3)に記載のナビゲーション位置取得方法。
(5)上記相関関数が１次関数である、上記(3)に記載のナビゲーション位置取得方法。
(6)上記相関関数が２次関数である、上記(3)に記載のナビゲーション位置取得方法。
(7)上記相関関数が３次関数である、上記(3)に記載のナビゲーション位置取得方法。
(8)基準特徴の相対的変位を決定する上記ステップが、上記２次元テーラー級数展開式の係数の値を決定するステップを含む、上記(1)に記載のナビゲーション位置取得方法。
【０１９０】
(9)上記２次元テーラー級数展開式の係数を取得するため、相関データの統計的適合を計算するステップを含む、上記(8)に記載のナビゲーション位置取得方法。
(10)上記２次元テーラー級数展開式の係数の少なくとも１つが上記基準フレームを上記サンプル・フレームとして使用することによって生成される、上記(8)に記載のナビゲーション位置取得方法。
(11)基準特徴の相対的変位を決定する上記ステップが、２次元のテーラー級数展開式の係数の値に基づく変位のコンポーネントを決定するステップを含む、上記(1)に記載のナビゲーション位置取得方法。
(12)基準特徴の変位の精度推定が予測値の定義済みセットの範囲内にあるか否かを判断するステップを更に含む、上記(10)に記載のナビゲーション位置取得方法。
(13)サンプル・フレームと基準フレームの間の変位の生成された値に補正関数を適用するステップを更に含む、上記(10)に記載のナビゲーション位置取得方法。
【０１９１】
(14)少なくとも１つのセンサ・アレイと、プロセッサと、該プロセッサを制御するコンピュータ・プログラムと、を備えるスキャナであって、該コンピュータ・プログラムが、上記センサ・アレイを介して基準フレームを取得するステップと、上記センサ・アレイを介してサンプル・フレームを取得するステップと、上記サンプル・フレームならびに上記基準フレーム両方の基準特徴の間の関係を表す相関データを生成するステップと、上記相関データに基づいて上記基準フレームに対する上記サンプル・フレームの基準特徴の相対的変位を決定するステップとを実行する複数の命令を含み、上記相対的変位を決定するため、一般的２次元テーラー級数展開式としてモデル化される相関データの相関表面の大域極値が使用される、スキャナ。
【０１９２】
(15)上記一般的２次元テーラー級数展開式が２次式である、上記(14)に記載のスキャナ。
(16)上記相関データが、更に、相関関数を使用して生成される複数の相関係数を含む、上記(14)に記載のスキャナ。
(17)上記コンピュータ・プログラムが、上記相関係数と上記２次元テーラー級数展開式の間の線形マッピングを適用するステップを実行する命令を更に含む、上記(16)に記載のスキャナ。
(18)上記相関関数が１次関数である、上記(16)に記載のスキャナ。
(19)上記相関関数が２次関数である、上記(16)に記載のスキャナ。
(20)上記相関関数が３次関数である、上記(16)に記載のスキャナ。
(21)基準特徴の相対的変位を決定する上記ステップが、上記２次元テーラー級数展開式の係数の値を決定するステップを含む、上記(14)に記載のスキャナ。
【０１９３】
(22)上記２次元テーラー級数展開式の係数を取得するため、相関データの統計的適合を計算するステップを実行する命令を上記コンピュータ・プログラムが更に含む、上記(21)に記載のスキャナ。
(23)上記２次元テーラー級数展開式の係数の少なくとも１つが上記基準フレームを上記サンプル・フレームとして使用することによって生成される、上記(21)に記載のスキャナ。
(24)基準特徴の相対的変位を決定する上記ステップが、２次元のテーラー級数展開式の係数の値に基づく変位のコンポーネントを決定するステップを含む、上記(14)に記載のスキャナ。
(25)基準特徴の変位の精度推定が予測値の定義済みセットの範囲内にあるか否かを判断するステップを実行する命令を上記コンピュータ・プログラムが更に含む、上記(24)に記載のスキャナ。
(26)サンプル・フレームと基準フレームの間の変位の生成された値に補正関数を適用するステップを実行する命令を上記コンピュータ・プログラムが更に含む、上記(24)に記載のスキャナ。
【０１９４】
【発明の効果】
本発明を走査装置に適用することによって、連続的時間間隔で走査装置のセンサ・アレイによって捕捉されるイメージ・フレームの間の比較に基づいてナビゲーション情報を得る効率的方式が提供される。
【図面の簡単な説明】
【図１】オリジナル上のくねった経路をたどる手持ち型走査装置の外観図である。
【図２】図１の走査装置のイメー形成ならびにナビゲーション・センサの裏面図である。
【図３】図１の走査装置をイメージ形成ならびにナビゲーション・センサを露出させて示した外観図である。
【図４】図３のナビゲーション・センサのうちの１つに関する照光システムのブロック図である。
【図５】図４の照光システムにおいて照光を行う発光ダイオードならびに光学エレメントを示すブロック図である。
【図６】図１の走査装置のイメージ捕捉の概念を示すブロック図である。
【図７】図１の走査装置のナビゲーション処理の１つの実施形態の動作の流れ図である。
【図８】図７の動作の一部の詳細を示すブロック図である。
【図９】図８のステップを実施するコンポーネントのブロック図である。
【図１０】図９における出力を表す位置タグ付きデータストリームのブロック図である。
【図１１】図１２と共に、図１の走査装置による走査帯を表すブロック図である。
【図１２】図１１と共に、図１の走査装置による走査帯を表すブロック図である。
【図１３】隣接走査帯を縫合するために利用される位置決めタイルを表すブロック図である。
【図１４】センサ・アレイを通してイメージ形成された用紙繊維イメージ・セットを表わすブロック図である。
【図１５】図１４の用紙繊維イメージ・セットに"差の平方の和"相関関数を適用して計算された相関表面を表すブロック図である。
【図１６】z'軸の周囲を角度θ回転し次にベクトル{x0,y0}並進するという特別ケースにおける２Ｄアフィン変換を示すブロック図である。
【図１７】最適最小２乗を図１５において示されるデータに適合させた場合の相関表面を表すブロック図である。
【図１８】３×３ナビゲーション機構ピクセル−シフト相関グリッドと関数f(x,y)の対応する値の間のマッピングを示すブロック図である。
【図１９】２次式相関関数ならびに図１４の用紙サンプルを使用して取得される相関数へのアルゴリズム"9A"の適用によって生じるナビゲーション誤差を表すブロック図である。
【図２０】２次式相関関数ならびに図１４のデータセットを使用して計算される真の相関表面と最適合致２次表面の間の相違を示すブロック図である。
【図２１】２次式相関関数ならびに図１４の用紙サンプルを使用して取得される相関数へのアルゴリズム"9B"の適用によって生じるナビゲーション誤差を表すブロック図である。
【図２２】線形相関関数ならびに図１４のデータセットを使用して計算される真の相関表面と最適合致２次表面の間の相違を示すブロック図である。
【図２３】線形相関関数ならびに図１４の用紙サンプルを使用して取得される相関数へのアルゴリズム"9B"の適用によって生じるナビゲーション誤差を表すブロック図である。
【図２４】立方体相関関数ならびに図１４のデータセットを使用して計算される真の相関表面と最適合致２次表面の間の相違を示すブロック図である。
【図２５】立方体相関関数ならびに図１４の用紙サンプルを使用して取得される相関数へのアルゴリズム"9B"の適用によって生じるナビゲーション誤差を表すブロック図である。
【図２６】CC→3/2というマッピングの適用によって人為的に生成された相関データを再形成することによって改善された線形最小２乗法の２次関数へ適合を示すブロック図である。
【図２７】最適合致２次モデル関数と真の相関表面の間の差を示すブロック図である。
【図２８】相関関数を図２１に示された対応する位置推定値{x0,y0}各々に適用した結果を表すブロック図である。
【図２９】最適線形補正の後の図２１のナビゲーション誤差を表すブロック図である。
【図３０】最適線形補正の後の図１９のナビゲーション誤差を表すブロック図である。
【図３１】ほぼ{0.5ピクセル,0.5ピクセル}変位した相関表面の輪郭を示すブロック図である。
【図３２】６セルならびに４セルそれぞれのケースに関する関数値への相関係数のマッピングを示すブロック図である。
【図３３】２５セル・グリッドにおける"最小セル"予測値を使用した場合の、２次式相関関数ならびに図１４の用紙サンプルを使用して取得される相関数へのアルゴリズム"9B"の適用によって生じるナビゲーション誤差を表すブロック図である。
【図３４】シミュレートされた位置情報と予測値x4,2の対応する出力の比較を示すブロック図である。
【図３５】シミュレートされた位置情報と２つの８タップ予測値の対応する出力の比較を示すブロック図である。
【図３６】単一ナビゲーション位置測定における統計誤差の標準偏差に対する予測値Xm,nまたはYm,nにおける統計的不確実性の比率を示すブロック図である。
【図３７】シミュレートされた位置情報と２つの１予測値の対応する出力の比較を示すブロック図である。
【図３８】シミュレートされた位置情報と円滑子X4,2の対応する出力の比較を示すブロック図である。
【図３９】シミュレートされた位置情報と２つの１７タップ円滑子の対応する出力の比較を示すブロック図である。
【図４０】単一ナビゲーション位置測定における統計誤差の標準偏差に対する円滑化された値における不確実性の比率を示すブロック図である。
【図４１】シミュレートされた位置情報と２つの定数円滑子の対応する出力の比較を示すブロック図である。
【図４２】図４３と共に、関数値に対する相関係数の６セル・マッピングを示すブロック図である。
【図４３】図４４と共に、関数値に対する相関係数の６セル・マッピングを示すブロック図である。
【図４４】４つの６セル・サブアレイに関する減少された２次ナビゲーション・アルゴリズムを実施する公式を示すブロック図である。
【図４５】較正基準フレームに組み込まれた２つのナビゲーション機構座標系のブロック図である。
【図４６】較正ならびに用紙座標系の比較を示すブロック図である。
【図４７】ナビゲーション機構光検出器アレイ起点の座標を使用する用紙繊維における較正基準ベクトル・コンポーネントの幾何学計算を示すブロック図である。
【図４８】較正フレームにおける２つのナビゲーション機構の並進運動を示すブロック図である。
【図４９】最悪ケース・ナビゲーション経路再構築アルゴリズムの実施に必要な公式のシーケンスの流れ図である。
【符号の説明】
２２ イメージ形成センサ
２４ ナビゲーション・センサ
６２ 基準フレーム
６６ サンプル・フレーム
６４ 固有の構造的特徴

Claims (22)

1. センサ・アレイのナビゲーション位置を取得する方法であって、
   前記センサ・アレイを介して基準フレームを取得するステップと、
   前記センサ・アレイを介してサンプル・フレームを取得するステップと、
   前記サンプル・フレームおよび前記基準フレーム両方の基準特徴の間の関係を表す相関データを生成するステップであって、前記相関データは、相関関数を使用して生成される複数の相関係数を含む、ステップと、
   前記相関データに基づいて前記基準フレームに対する前記サンプル・フレームの基準特徴の相対的変位を決定するステップであって、前記相対的変位を決定するため、一般的２次元テーラー級数展開式としてモデル化される相関データの相関表面の大域極値が使用される、ステップと、
   前記相関係数と前記２次元テーラー級数展開式の間の線形マッピングを適用するステップと
   を含む、ナビゲーション位置取得方法。
2. 前記一般的２次元テーラー級数展開式が２次式である、請求項１に記載のナビゲーション位置取得方法。
3. 前記相関関数が１次関数である、請求項１に記載のナビゲーション位置取得方法。
4. 前記相関関数が２次関数である、請求項１に記載のナビゲーション位置取得方法。
5. 前記相関関数が３次関数である、請求項１に記載のナビゲーション位置取得方法。
6. 基準特徴の相対的変位を決定する前記ステップが、前記２次元テーラー級数展開式の係数の値を決定するステップを含む、請求項１に記載のナビゲーション位置取得方法。
7. 前記２次元テーラー級数展開式の係数を取得するため、相関データの統計的適合を計算するステップを含む、請求項６に記載のナビゲーション位置取得方法。
8. 前記２次元テーラー級数展開式の係数の少なくとも１つが前記基準フレームを前記サンプル・フレームとして使用することによって生成される、請求項６に記載のナビゲーション位置取得方法。
9. 基準特徴の相対的変位を決定する前記ステップが、２次元のテーラー級数展開式の係数の値に基づく変位のコンポーネントを決定するステップを含む、請求項１に記載のナビゲーション位置取得方法。
10. 基準特徴の変位の精度推定が予測値の定義済みセットの範囲内にあるか否かを判断するステップを更に含む、請求項８に記載のナビゲーション位置取得方法。
11. サンプル・フレームと基準フレームの間の変位の生成された値に補正関数を適用するステップを更に含む、請求項８に記載のナビゲーション位置取得方法。
12. 少なくとも１つのセンサ・アレイと、
    プロセッサと、
    該プロセッサを制御するコンピュータ・プログラムと
    を備えるスキャナであって、
    該コンピュータ・プログラムが、
    前記センサ・アレイを介して基準フレームを取得するステップと、
    前記センサ・アレイを介してサンプル・フレームを取得するステップと、
    前記サンプル・フレームならびに前記基準フレーム両方の基準特徴の間の関係を表す相関データを生成するステップであって、前記相関データは、相関関数を使用して生成される複数の相関係数を含む、ステップと、
    前記相関データに基づいて前記基準フレームに対する前記サンプル・フレームの基準特徴の相対的変位を決定するステップであって、前記相対的変位を決定するため、一般的２次元テーラー級数展開式としてモデル化される相関データの相関表面の大域極値が使用される、ステップと、
    前記相関係数と前記２次元テーラー級数展開式の間の線形マッピングを適用するステップと
    を実行する複数の命令を含む、スキャナ。
13. 前記一般的２次元テーラー級数展開式が２次式である、請求項１２に記載のスキャナ。
14. 前記相関関数が１次関数である、請求項１２に記載のスキャナ。
15. 前記相関関数が２次関数である、請求項１２に記載のスキャナ。
16. 前記相関関数が３次関数である、請求項１２に記載のスキャナ。
17. 基準特徴の相対的変位を決定する前記ステップが、前記２次元テーラー級数展開式の係数の値を決定するステップを含む、請求項１２に記載のスキャナ。
18. 前記２次元テーラー級数展開式の係数を取得するため、相関データの統計的適合を計算するステップを実行する命令を前記コンピュータ・プログラムが更に含む、請求項１７に記載のスキャナ。
19. 前記２次元テーラー級数展開式の係数の少なくとも１つが前記基準フレームを前記サンプル・フレームとして使用することによって生成される、請求項１７に記載のスキャナ。
20. 基準特徴の相対的変位を決定する前記ステップが、２次元のテーラー級数展開式の係数の値に基づく変位のコンポーネントを決定するステップを含む、請求項１２に記載のスキャナ。
21. 基準特徴の変位の精度推定が予測値の定義済みセットの範囲内にあるか否かを判断するステップを実行する命令を前記コンピュータ・プログラムが更に含む、請求項２０に記載のスキャナ。
22. サンプル・フレームと基準フレームの間の変位の生成された値に補正関数を適用するステップを実行する命令を前記コンピュータ・プログラムが更に含む、請求項２０に記載のスキャナ。

Images