(57)【特許請求の範囲】
【請求項１】
移動可能なユーザ入力デバイス（６０）であって、該ユーザ入力デバイスの移動を示す出力信号を生成し、コンピュータデバイスに対する入力のためのユーザ入力デバイスにおいて、
表面（６２）に対して相対的に移動可能なハウジング（６４）と、
前記ハウジング中に配置され、前記表面のイメージ（２１０）を検出し、前記表面のイメージについてのピクセルデータに対応する信号を作成するイメージセンサ（８０）と、
バッファメモリ（１２２）と、
前記イメージセンサおよび前記バッファメモリと結合され、前記ユーザ入力デバイスが前記表面上を移動するときに基準フレーム（２１６）のピクセルデータを選択的に前記バッファメモリにロードし、比較フレーム（２１８）のピクセルデータを示す連続のピクセルデータを処理する処理回路（９２、１００）と、
前記イメージセンサにより生成された信号を受信し、前記イメージセンサからの信号をデジタル信号に変換するアナログデジタル変換器であって、前記基準フレームのピクセルデータおよび比較フレームの連続のピクセルデータは前記デジタル信号のピクセルデータであるアナログデジタル変換器（９０）と
を備え、前記処理回路は、
ａ）前記比較フレームの連続のピクセルデータを別個のバッファメモリに格納することなく当該連続のピクセルデータを処理し、当該連続のピクセルデータの処理は、
ａ１）前記デジタル信号から前記比較フレームの１つのピクセルを読み出し（１６０、１８４）、
ａ２）前記比較フレームの１つのピクセルと、前記バッファメモリに記憶されている基準フレームの内の対応ピクセル周辺のある範囲の複数のピクセル内の１ピクセル毎の相互相関の要素を計算し（１７８）、
ａ３）前記比較フレームの相関ウィンドウ内のすべてのピクセルが処理されたか否かを判定し（１８２）、
ａ４）否の判定の場合には、１つのピクセル位置だけシフトして、前記ａ１）〜ａ４のステップを前記比較フレームの次のピクセルのために繰り返す処理（１８４）を含み、
前記処理回路は、さらに、
ｂ）前記計算された相互相関の要素の総和としての相互相関に関して最大相関を生ずるピクセル位置に基づいて、前記表面上のユーザ入力デバイスの移動を判定し、前記移動を示す対応出力信号（１１４）を生成する処理回路であり、
前記処理回路に結合されたマルチプレクサ（１２０）をさらに備えており、
前記マルチプレクサは前記バッファメモリの入力（１２０ｃ）に結合された出力、前記変換器を介して前記イメージセンサに結合された第１の入力（１２０ａ）および前記バッファメモリの出力に結合された第２の入力（１２０ｂ）を備え、前記処理回路により制御されて前記バッファフレーム内の前記基準フレームのピクセルデータを前記バッファメモリに再ロードするか、又は、前記比較フレームのピクセルデータを新しい基準フレームとして前記バッファメモリにロードするかを選択的に行うことを特徴とするユーザ入力デバイス。
【請求項２】
前記ハウジング内に配置され、前記表面を照明し、前記イメージセンサに前記表面のイメージを検出せしめる光源（７８）をさらに備えたことを特徴とする請求項１に記載のユーザ入力デバイス。
【請求項３】
前記ａ１）の処理は、前記比較フレームの前記相関ウィンドウ内にある１つのピクセル（ｘ，ｙ）を読み出すことを含み、ここで、０≦ｘ≦Ｍ、０≦ｙ≦Ｎであり、ＮとＭはどちらも１１に等しく、
前記ａ２）の処理は、前記比較フレームと前記基準フレームの間の相互相関を計算するため、下の式を使用して、前記比較フレームの前記相関ウィンドウ内にある１つのピクセル（ｘ，ｙ）に対する前記基準フレームの前記範囲内にある複数のピクセル（ｘ＋ａ，ｙ＋ｂ）内のそれぞれについて差の絶対値を計算することで相互相関の要素を計算することを含み、ここで、−１≦ａ≦１、−１≦ｂ≦１であり、
前記ａ３）の処理は、前記相関ウィンドウ内の０≦ｘ≦Ｍ、０≦ｙ≦Ｎの全てについて相互相関が計算されたかどうかを判定することを含み、
前記ａ４）の処理は、０≦ｘ≦Ｍ、０≦ｙ≦Ｎの範囲内で、ｘ又はｙを１だけ増分することを含み、
【数１】
0004198399.tif 000004
前記ｂ）の処理は、相互相関の要素の総和である上の式の相互相関（ａ，ｂ）の絶対値が最小になるａとｂの値を求めることにより、最大相関のピクセル位置（ａ，ｂ）を求めて、移動を判定することを含む
ことを特徴とする請求項１に記載のユーザ入力デバイス。
【請求項４】
前記ユーザ入力デバイスの前記表面に対する相対的な移動により、前記バッファメモリに現在格納されている基準フレームと比較フレームとの重なり合いがなくなろうとする前に、前記処理回路が前記マルチプレクサに前記新しい基準フレームを前記バッファメモリにロードさせることを特徴とする請求項１に記載のユーザ入力デバイス。
【請求項５】
前記処理回路は、前記ユーザ入力デバイスが前記表面に対して相対的に移動している速度を決定して、いつ前記マルチプレクサに前記新しい基準フレームをロードさせるかを決定することを特徴とする請求項４に記載のユーザ入力デバイス。
【請求項６】
前記相互相関が前記比較フレームについて決定されている間、前記相互相関の要素を格納するメモリをさらに備えたことを特徴とする請求項３に記載のユーザ入力デバイス。
【請求項７】
前記相互相関を決定する処理において相関ウィンドウ内のピクセルデータだけが使用されることを特徴とする請求項１に記載のユーザ入力デバイス。
【請求項８】
前記ユーザ入力デバイスはポインティングデバイスであり、生成される前記出力信号は前記ポインティングデバイスの少なくとも一部分と隣接の表面との間の相対的な移動を示し、
前記バッファメモリは、シーケンシャルメモリバッファであり、該シーケンシャルメモリバッファは、格納のためにデータを入力する入力（１２０ｃ）および前記シーケンシャルメモリバッファの外にデータを転送する出力を有し、
前記シーケンシャルメモリバッファの入力が前記マルチプレクサの出力に結合され、前記シーケンシャルメモリバッファの出力が前記マルチプレクサの第２の入力に結合され、前記マルチプレクサの状態に応じて前記シーケンシャルメモリバッファの入力は、前記イメージセンサからの信号および前記シーケンシャルメモリバッファの出力のいずれかにより伝送されるデータを選択的に受信し、
前記処理回路は前記イメージに対応する信号に応答して前記シーケンシャルメモリバッファに格納されたデータを選択的に読み出し、および前記マルチプレクサに結合されて前記マルチプレクサの状態を選択に制御して選択的に第１の状態で前記シーケンシャルメモリバッファに前記イメージセンサにより生成された信号によるデータをロードし、第２の状態で前記シーケンシャルメモリバッファの出力からのデータを前記シーケンシャルメモリバッファに再ロードすることを特徴とする請求項１に記載のユーザ入力デバイス。
【請求項９】
前記マルチプレクサの出力からのデータが前記シーケンシャルメモリバッファの入力に送られたときに、前記シーケンシャルメモリバッファは複数のピクセルについてのデータを前記シーケンシャルバッファ内に含まれる連続の格納位置の間でシフトすることを特徴とする請求項８に記載のユーザ入力デバイス。
【請求項１０】
前記イメージセンサにより生成された信号を処理する高域フィルタ（１０４）をさらに有し、前記高域フィルタの出力を前記マルチプレクサの第１の入力および処理回路に結合されることを特徴とする請求項８に記載のユーザ入力デバイス。
【請求項１１】
前記シーケンシャルメモリバッファに格納されるデータは、前記処理回路によりピクセル単位で少なくとも部分的に選択的にアドレス可能でおよびアクセス可能であることを特徴とする請求項８に記載のユーザ入力デバイス。
【請求項１２】
前記シーケンシャルメモリバッファに格納される基準フレームは、前記ユーザ入力デバイスと前記隣接の表面との間の相対的な移動が、前記シーケンシャルメモリバッファに格納された基準フレームと前記イメージセンサから入力される現在の比較フレームの間の重なり合いがなくなる前に置き換えられ、該重なり合いは、前記シーケンシャルメモリバッファに格納された基準フレームと前記処理回路から現在入力される比較フレームとの間の相互相関の決定に必要な重なり合いであることを特徴とする請求項８に記載のユーザ入力デバイス。
【請求項１３】
前記バッファメモリのデータ格納容量は前記基準フレームおよび前記比較フレームの双方を格納するに要する容量よりも実質的に小さいことを特徴とする請求項１または８のユーザ入力デバイス。
【請求項１４】
ポインティングデバイス（６０）の少なくとも一部分および隣接の表面（６２）の間の相対的な移動を示す信号（１１４）を生成する方法において、
隣接の表面を撮像してイメージのピクセルデータを生成するステップと（１４２）、
前記イメージのピクセルデータをメモリバッファ（１２２）に格納するステップ（１４４）と、
なお、ここで前記メモリバッファに格納されたイメージのピクセルデータは基準フレーム（２１６）に対応しており、
前記ポインティングデバイスの少なくとも一部と前記隣接の表面との間で前記相対的な移動が生じたときに前記隣接の表面の撮像により比較フレーム（２１８）の連続のピクセルを取得するステップと（１４６、１５０、１５６）、
前記基準フレームのイメージのピクセルデータおよび前記比較フレームの連続のピクセルはアナログデジタル変換器（９０）によりデジタル信号に変換され、前記比較フレームの連続のピクセルは、前記連続のピクセルデータを別個のバッファメモリに格納することなく処理され、前記連続のピクセルの処理では、
ａ１）前記デジタル信号から前記比較フレームの１つのピクセルを読み取るステップ（１６０、１８０）、
ａ２）前記比較フレームの１つのピクセルと、前記バッファメモリに記憶されている基準フレームの内の対応ピクセル周辺のある範囲の複数のピクセル内の１ピクセル毎の相互相関の要素を計算し（１７８）、
ａ３）相関ウィンドウ内の比較フレームのすべてのピクセルが処理されたか否かを判定するステップ（１８２）と、
ａ４）否の場合、１ピクセル位置だけ前記基準フレームをシフト（１８４）し、および前記比較フレームの次のピクセルについてａ１）からａ４）のステップを繰り返すステップと
を実行し、前記相互相関の要素の総和としての相互相関に基づいて前記ポインティングデバイスの一部分と隣接の表面との間の相対的な移動の大きさを示す信号が生成されるステップ（１９０、１９２）と、
前記基準フレームについてのイメージのピクセルデータを前記バッファメモリに選択的に再ロードするステップ（１９８）と、
前記ポインティングデバイスの一部分と前記表面との間の相対的な移動により次の比較フレームが、もはや前記バッファメモリに以前に格納された基準フレームと重なり合いをしなくなる前に、新しい基準フレームとして、比較フレームをバッファメモリにローディングするステップ（１９４、１９６）とを
備えることを特徴とする方法。
【請求項１５】
前記ポインティングデバイスの一部分と前記表面との間の相対的な移動の速度を決定するステップ（１９２）をさらに有することを特徴とする請求項１４に記載の方法。
【請求項１６】
前記ポインティングデバイスの一部分と前記表面との間の相対的な移動の速度の関数として前記バッファメモリに前記新しい基準フレームをロードするか否かを判定するステップ（１９２）をさらに有することを特徴とする請求項１５に記載の方法。
【請求項１７】
前記相互相関を決定する前に前記イメージデータをフィルタリングするステップをさらに有することを特徴とする請求項１４に記載の方法。
【請求項１８】
前記バッファメモリ内に付加的に、以前の基準フレームのイメージデータの最後の部分のための記憶領域を設けるステップをさらに有し、それにより前記新しい基準フレームが前記バッファメモリにロードされたときに前記相互相関の決定のために前記以前の基準フレームのイメージデータの最後の部分を使用可能とすることを特徴とする請求項１７に記載の方法。
【請求項１９】
前記新しい基準フレームが前記バッファメモリにロードされたときに前記以前の基準フレームについての連続のピクセルのイメージデータを廃棄するステップをさらに有することを特徴とする請求項１４に記載の方法。
【請求項２０】
請求項１４乃至１９のいずれかに記載の処理手順をコンピュータに実行させる複数の機械命令を格納することを特徴とする機械可読記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般には、表面のイメージの変化に応答する光検出器回路を使用して、装置と、隣接する表面との間の相対運動を追跡する処理、より詳細には、基準イメージに関するピクセルデータだけをメモリ内に保持して、基準イメージと比較イメージとの間の相互相関と、基準イメージの自己相関との関数として、相対運動を示す信号を生成する処理に好適なポインティングデバイスに関する。
【０００２】
【従来の技術】
「機械式」マウスは、コンピュータディスプレイ上のカーソルおよび他のグラフィック構成要素を制御するために使用される、最も一般的なタイプのポインティングデバイスである。一般に、表面上のマウスの運動を検出するために、マウスの底部の空洞内に収められたボールが表面と接触し、ユーザがマウスを表面上で移動させるときにボールが回転する。空洞内のボールの回転運動は、ボールに接触する２つのローラに伝達される。ローラが装着されている軸が、回転運動符号器に結合される。各ローラは、互いに垂直に配置され、それによって符号器からの信号が、運動の直交するＸ軸およびＹ軸成分に対応する。ここで、この２つの軸はマウスの向きに対して決定される。符号器信号から導出された運動のΔＸおよびΔＹ成分は、シリアルポート、パーソナルシステム／２（ＰＳ／２）ポート、バスマウスポート、またはユニバーサルシリアルバス（ＵＳＢ）ポートを介して、パーソナルコンピュータ（ＰＣ）または他のコンピューティング装置に入力され、ディスプレイ画面上のカーソルまたは他のグラフィカルオブジェクトを制御するために使用される。マウスはまた、ユーザが始動したときに状態信号を生成する２つ以上のスイッチを通常は含み、かつディスプレイウィンドウの内容のスクロール、および／または他の機能を制御するために、別の回転符号器と状態スイッチとに結合される回転ホイールを含む場合もある。「トラックボール」と呼ばれる、関連タイプのポインティングデバイスも、ボールを利用して回転符号器を始動するが、ボールは、ユーザの指または手によって動かすことができるようにこのポインティングデバイスの上面に露出し、一方ボールが収められているハウジングは、一般に位置が固定されたままとなる。
【０００３】
上述の機械式マウスは、ボールおよび回転符号器ローラを定期的にクリーニングして、ローラがボールに接触する箇所に蓄積しやすい堆積物を除去しない場合、不規則な信号を生成する可能性がある。さらに、ボールは、すべすべした表面上では適切に回転しない可能性があり、それによってマウスの運動を追跡する際に誤差が生じる可能性がある。より最近になって、機械式マウスにおいて回転可能なボールを使用することに関連する問題の大部分を回避する「光学式」マウスが開発された。機械式マウスとは対照的に、光学式マウスはマウス内に回転可能なボールを含まず、その代わりにマウスが移動している表面を撮像することによってマウスの運動を追跡する。Ｍｏｕｓｅ  Ｓｙｓｔｅｍ，Ｉｎｃ．によって販売された光学式マウスの初期のバージョンでは、反射表面を有し、密な間隔で配置された線の直交するグリッドを含む特別なマウスパッドが利用された。この光学式マウスの初期のタイプの運動は、グリッドによって引き起こされる、特別な表面から反射された光の強さの変化を感知し、補間して、グリッド間隔よりも高い解像度で運動を分解することによって検出された。一方、ＭｉｃｒｏｓｏｆｔＣｏｒｐｏｒａｔｉｏｎによって販売されている、より最近になって開発された光学式マウスは、ほとんどの表面上で装置の移動を追跡することができ、それによって特別な表面、すなわちパッドが不要である。このタイプの光学式マウスの詳細は、本願の譲受人に譲渡された、２００１年１月９日発行の米国特許第６１７２３５４号で開示されている。運動を検出するために、この特許に記載されている光学式マウスでは赤色発光ダイオード（ＬＥＤ）源が利用され、マウスの移動する隣接する表面が照射される。光学式マウスの底部内の可変感度光検出器（すなわち人工レティナ）の２次元アレイが、表面から反射された赤色光に応答して表面の一部のピクセルイメージを生成する。光検出器からのイメージ信号は、２つの異なるイメージバッファ内にピクセルデータとして周期的に格納される。これらのデータを処理して相互相関を決定し、この相互相関から、マウス移動のΔＸ成分およびΔＹ成分をこの相互相関結果の関数として決定することができる。
【０００４】
従来技術の光学式マウスでは、一方がＮ×Ｎピクセル基準フレームイメージを格納するイメージバッファと、他方がマウスの移動する表面の一部のＭ×Ｍ比較フレームイメージを格納するイメージバッファを含む２つのイメージバッファを使用して相互相関を決定する。基準フレーム内の当該の領域内の各ピクセルを読み取り、比較フレーム内の当該の領域内のすべてのピクセルと比較して、２つのイメージバッファの相互相関を決定する。この比較の結果を相関アレイに入力する。相関アレイの各成分は、比較フレームと基準フレームとの間の異なるオフセットに関する差の和を含む。比較フレームバッファ内に格納されたピクセルを、基準フレームバッファ内に格納されたピクセルに対して処理することによってこの差を累積する。これにより、従来技術で一般に実施されているように、一般に合計Ｍ×Ｍ×Ｎ×Ｎ回の操作が必要となる。その結果、この従来技術の手法で相互相関を決定するプロセスは低速であり、かつ計算を多用する。加えて、このプロセスでは、基準イメージフレームデータおよび比較イメージフレームデータを格納するために、比較的高価で、中程度の大きさの２つのメモリアレイを提供することが必要となる。すべての処理はマウスに含まれる回路内で行われ、その結果、光学式マウスの移動に応答してディスプレイの別の部分にカーソルを制御する際に使用するためにコンピュータに送られる信号は、一般に機械式マウスによって生成される信号と同等である。この移動信号は、ＰＳ／２ポートまたはＵＳＢポートに接続するためにフォーマットされる。この従来技術の光感知システムが正確に追跡することのできるマウス移動の最大速度は、約１８インチ／秒（約４６ｃｍ／秒）である。
【０００５】
イメージ認識システムは一般に、相互相関および自己相関を使用して、背景に対する物体の配置を決定する。このようなシステムは通常、ＭｉｃｒｏｓｏｆｔＣｏｒｐｏｒａｔｉｏｎによって現在販売されている光学式マウスと同様に、一方が基準イメージフレームを格納し、他方が比較イメージフレームを格納する２つのメモリアレイも使用する。光学式マウスのコストを削減する目的で、相互相関を決定するために使用する基準フレームおよび比較フレームを格納する２つの異なるメモリアレイを必要としない、特定用途向け集積回路（ＡＳＩＣ）処理チップをマウス内で利用することが好ましい。このような光学式マウスを使用することによってより良好な追跡性能を達成することが望ましく、サブピクセル補間を使用してマウスの移動を決定することが望ましい。
【０００６】
【発明が解決しようとする課題】
したがって、現在の手法よりも処理サイクルに対する要求が少なく、かつ低コストで、所望のより効率的な追跡能力を達成することのできる、相関を決定する新しい手法を開発するという動機付けが存在することは明らかである。この新しい手法はまた、相関を計算する際に通常必要となる２つのメモリアレイを使用するのではなく、単一のバッファメモリだけを使用することによって低コストを達成すべきである。
【０００７】
【課題を解決するための手段】
本発明によれば、表面に対する移動を監視するための光撮像センサを利用するポインティングデバイスにおいて、連続するイメージフレームが比較され、移動の方向および範囲が決定される。この撮像センサは、隣接する表面に関するピクセルイメージデータに対応する信号を生成する。基準フレームに関するイメージデータは、その後で表面を撮像することによって獲得される比較フレームとの相互相関を決定する際に使用するために、特殊なメモリバッファ内に格納される。基準フレームデータがバッファメモリを介してシフトされるとき、比較フレームの連続するピクセルが処理され、相互相関の成分が決定される。相互相関の各成分は、比較フレームのピクセルと、基準フレーム内の関係するピクセルの周囲のピクセルとの間の差の絶対値を表し、これらの成分は、相対的移動が行われた可能性のある様々な異なる方向に対応する。最小値を有する相互相関の成分が、相対的移動の方向を示す。
【０００８】
物体と隣接する表面との間の相対的移動を決定するための従来の手法では、連続する比較フレームを格納し、基準フレームを格納するために別々のメモリアレイが供給された。しかし、本発明では基準フレームだけがメモリ内に格納される。その結果、比較フレームに関するメモリアレイを準備する必要がないので、ポインティングデバイスのコストが大幅に削減される。その代わりに、データが撮像センサから読み取られるときに、連続する比較フレームに関するイメージデータが一度に１ピクセルだけ処理され、したがって、普通なら新しい基準フレームを供給するために使用される、比較フレームに関するイメージデータを保持する必要がなくなる。
【０００９】
本発明はまた、メモリバッファ内に格納された基準フレームに関するイメージデータを使用して、自己相関を決定するステップも含む。次いで、相対的移動のサブピクセル補間が自己相関（および相互相関）の関数として決定される。さらに、自己相関が相互相関と平行して決定されるので、イメージデータの処理が非常に効率的となる。比較フレームに関するイメージデータ内の各ピクセルが撮像センサから読み取られるとき、以前にバッファメモリ内にロードされた基準フレームに関するイメージデータが、バッファメモリに選択的に再ロードされる。基準フレームに関するイメージデータは、比較フレームの連続するピクセルが撮像センサから読み取られるときにバッファメモリを介してシフトされる。しかし時には、撮像センサから現在読み取られている比較フレームに関するイメージデータを使用して、新しい基準フレームをバッファメモリにロードすることが必要となることになる。ポインティングデバイスと表面との間の相対的移動が経時的に監視されるので、相対的移動の速度がポインティングデバイス内で容易に計算される。次いで、必要に応じて比較フレームからのイメージデータがバッファメモリにロードされ、後続のフレームで意味のある相互相関を決定できることが保証される。新しい基準フレームをバッファメモリ内にロードする必要は、運動の速度の関数として決定される。具体的には、相対位置は、速度に対応する距離を現在位置に加えることによる補外である。例えば、１フレーム離れた位置は、速度を使用することによって近似することができ、次のフレームが現在位置に獲得されるまでの時間に移動する距離を決定することができる。この目的は、ポインティングデバイスと表面との間の相対的移動が、後続の比較フレームと、バッファメモリ中に以前に格納されていた基準フレームとが重なり合わないようにするのに十分となる前に、新しい基準フレームをバッファメモリにロードすることにある。
【００１０】
追加の一時記憶装置が、以前の基準フレームのイメージデータの最後の部分に関するバッファメモリ内に供給され、それによって、現基準フレームに関するイメージデータがバッファメモリ内にロードされて新しい基準フレームとなるときに、以前の基準フレームのイメージデータの最後の部分が相互相関を決定する際に依然として利用可能となる。以前の基準フレームに関するイメージデータは、新しい基準フレームがロードされたときに廃棄される。
【００１１】
本発明の別の態様は、上述の方法のステップを実行するための複数の機械命令を記憶する機械可読媒体に関する。
【００１２】
本発明のさらに別の態様は、ポインティングデバイスの少なくとも一部と、隣接する表面との間の相対的移動を示す出力信号を生成するポインティングデバイスに関する。このポインティングデバイスは、隣接する表面のイメージに対応する信号を生成する撮像検出器、撮像検出器から信号を受け取るための第１入力と第２入力とを有する電子スイッチ、順次メモリバッファ、ならびに一般に上述の方法のステップを実施する処理回路を含む。
【００１３】
本発明のさらに別の態様は、物体と隣接する表面との間の相対的移動のサブピクセル補間成分を決定する方法に関する。この方法では、表面のピクセルイメージ（ｐｉｘｅｌａｔｅｄ  ｉｍａｇｅ）に対応する信号が生成され、ピクセルイメージの複数のピクセルのそれぞれに関するデータを含む、表面に関する基準フレームがメモリ内に格納される。物体と隣接する表面との間で相対的移動が行われるとき、新しいピクセルイメージ内の複数のピクセルに関するデータを含む比較フレームが生成される。次いで基準フレームに関するデータと、比較フレームに関するデータとの相互相関、ならびに基準フレーム内のデータの自己相関が決定される。最後に、相対的移動のサブピクセル補間成分が、相互相関および自己相関の両方の関数として決定される。
【００１４】
本発明の上述の態様および付随する利点の多くは、添付の図面に関して行う以下の詳細な説明を参照することによってより容易に理解されよう。
【００１５】
【発明の実施の形態】
例示的動作環境
図１および以下の議論で、本発明を利用することのできる例示的なコンピューティング環境の、簡単で一般的な説明を与える。必ずしもそのような応用例に限定されないが、本発明を、ユーザ制御入力信号をＰＣに供給するための入力装置として使用することに関連して説明する。この信号は、ＰＣによって実行される、プログラムモジュールなどのコンピュータ実行可能命令によって定義されるように決定することができる。一般に、プログラムモジュールは、特定のタスクを実行し、または特定の抽象データタイプを実装するアプリケーションプログラム、ルーチン、オブジェクト、構成要素、関数、データ構造などを含む。さらに、ウェブページを表示するためのクライアント装置、ハンドヘルド装置、ポケットパーソナルコンピューティング装置、アプリケーションプログラムを実行するように適合され、かつネットワークにワイヤレスで接続するように適合されたデジタルセルフォン、他のマイクロプロセッサベースの、またはプログラマブル消費者向け電子装置、マルチプロセッサシステム、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータなどの他の処理環境に適用可能なユーザ入力装置で本発明が利用できることを当業者は理解されよう。
【００１６】
図１を参照すると、本発明が使用可能な例示的システムは、処理装置２１、システムメモリ２２、およびシステムバス２３を備える従来型のＰＣ２０の形態の汎用コンピューティング装置を含む。システムバス２３は、システムメモリを含む様々なシステム構成要素を処理装置２１に結合する。システムバス２３は、様々なバスアーキテクチャのうちのいずれかを用いたメモリバスまたはメモリコントローラ、周辺バス、およびローカルバスを含むいくつかのタイプのバス構造のいずれでもよい。システムメモリは、読取り専用メモリ（ＲＯＭ）２４およびランダムアクセスメモリ（ＲＡＭ）２５を含む。スタートアップ時などにＰＣ２０内の要素間で情報を転送する助けとなる基本ルーチンを含む基本入出力システム（ＢＩＯＳ）２６が、ＲＯＭ２４内に格納される。ＰＣ２０は、ハードディスク（図示せず）を読み書きするためのハードディスクドライブ２７と、取外し可能磁気ディスク２９を読み書きするための磁気ディスクドライブ２８と、ＣＤ−ＲＯＭまたは他の光媒体などの取外し可能光ディスク３１を読み書きするための光ディスクドライブ３０とをさらに含む。ハードディスクドライブ２７、磁気ディスクドライブ２８、および光ディスクドライブ３０は、それぞれハードディスクドライブインターフェース３２、磁気ディスクドライブインターフェース３３、および光ディスクドライブインターフェース３４によってシステムバス２３に接続される。各ドライブと、それに関連するコンピュータ可読媒体は、ＰＣ２０に対して、コンピュータ可読機械命令、データ構造、プログラムモジュール、および他のデータの不揮発性記憶を提供する。本明細書で説明する例示的環境では、ハードディスク、取外し可能磁気ディスク２９、および取外し可能光ディスク３１を利用するが、磁気カセット、フラッシュメモリカード、デジタルビデオディスク（ＤＶＤ）、ベルヌーイカートリッジ、ＲＡＭ、ＲＯＭなど、コンピュータによってアクセス可能な、データを記憶することのできる他のタイプのコンピュータ可読媒体もこの例示的動作環境で使用できることを当業者は理解されたい。
【００１７】
オペレーティングシステム３５、１つまたは複数のアプリケーションプログラム３６、他のプログラムモジュール３７、およびプログラムデータ３８を含むいくつかのプログラムモジュールを、ハードディスク、磁気ディスク２９、光ディスク３１、ＲＯＭ２４、またはＲＡＭ２５上に格納することができる。ユーザは、キーボード４０およびポインティングデバイス４２などの入力装置を介して、ＰＣ２０にコマンドおよび情報を入力することができる。ポインティングデバイス４２は、本発明の一実施形態であり、好ましくはマウスであるが、本発明は、トラックボール、ジョイスティック、またはスタイラスなど、その少なくとも一部が表面に対して移動する他のタイプのユーザ入力装置でも実施することができる。ＰＣ２０に関する他の入力装置（図示せず）には、マイクロフォン、ゲームパッド、サテライトディッシュ、スキャナなどを含めることができる。これらおよび他の入出力（Ｉ／Ｏ）装置は、しばしば、システムバス２３に結合されるＩ／Ｏ装置インターフェース４６を介して処理装置２１に接続される。用語Ｉ／Ｏ装置インターフェースは、各インターフェース、具体的にはシリアルポート、パラレルポート、ゲームポート、キーボードポート、ＰＳ／２ポート、および／またはＵＳＢポート用に使用される各インターフェースを包含するものとする。本発明を、ワイヤレスリンクを介してＰＣシステムバスに結合できることも企図される。モニタ４７または他のタイプのディスプレイ装置も、ビデオアダプタ４８などの適切なインターフェースを介してシステムバス２３に接続され、アプリケーションプログラム、ウェブページ、および／または他の情報を表示するために使用可能である。本発明は一般に、ＰＣ上で実行されるオペレーティングシステムおよび／またはアプリケーションプログラムと共に、カーソルを制御し、スクロールし、かつ／またはモニタ４７上に表示される他のグラフィックオブジェクトを制御するために使用される。モニタに加えて、ＰＣはしばしば、スピーカ（サウンドカードまたは他の音声インターフェース（図示せず）を介して）およびプリンタなどの他の周辺出力装置（図示せず）に結合される。
【００１８】
先に指摘した通り、単一のマシンに入力を供給する際に使用するために本発明を利用することができる。しかし、任意選択でＰＣ２０は、ユーザ入力制御のために本発明をやはり結合することができるリモートコンピュータ４９など、１つまたは複数のリモートコンピュータに対する論理接続を使用するネットワーク環境で動作する。リモートコンピュータ４９は、別のＰＣ、サーバ（一般にＰＣ２０とほぼ同様に構成される）、ルータ、ネットワークＰＣ、ピア装置、あるいはサテライトネットワークノードまたは他の共通ネットワークノードでよく、一般にはＰＣ２０に関して上記で説明した要素のうちの多く、またはすべてを含むが、図１には外部メモリ記憶装置５０だけを示してある。図１に示す論理接続は、ローカルエリアネットワーク（ＬＡＮ）５１およびワイドエリアネットワーク（ＷＡＮ）５２を含む。このようなネットワーキング環境は、オフィス、企業全体のコンピュータネットワーク、イントラネット、およびインターネットへの接続で一般的なものである。
【００１９】
ＬＡＮネットワーキング環境で使用されるとき、ＰＣ２０は、ネットワークインターフェースまたはアダプタ５３を介してＬＡＮ５１に接続される。ＷＡＮネットワーキング環境で使用されるとき、ＰＣ２０は一般に、ＷＡＮ  ５２を介して通信を確立するためのモデム５４または他の手段を含む。ＷＡＮ  ５２は、インターネットを含むことができる。モデム５４は内蔵でも外付けでもよく、Ｉ／Ｏ装置インターフェース４６、すなわちシリアルポートを介してシステムバス２３に接続または結合される。ネットワーク環境では、ＰＣ２０に関して示したプログラムモジュールまたはその一部は、リモートメモリ記憶装置内に格納することができる。ここで示したネットワーク接続は例示的なものであって、ワイヤレス通信および広帯域ネットワークリンクなど、コンピュータ間の通信リンクを確立する他の手段も使用できることを理解されたい。したがって本発明は、スタンドアロンまたはネットワーク構成のＰＣまたは他のコンピューティング装置にユーザ制御入力を供給する際に使用するのに適している。
【００２０】
例示的ポインティングデバイス
本発明はポインティングデバイスに限定されないが、ポインティングデバイスは、ユーザ制御物体と、他の装置での隣接する表面との間の相対的移動を検出するために使用することができるので、本発明の最初の好ましい実施形態では、マウス６０で本発明を使用する。図２に示すように、マウス６０は、下にある表面上のマウスの移動を検出するために光撮像システムを使用する光学式タイプのマウスである。マウス６０は、一般には、ユーザの手のひら（図示せず）にフィットするように凸型に作られるハウジング６４を含む。図２に示す一般的な形状および外観を有するマウスは、過去にＭｉｃｒｏｓｏｆｔ  Ｃｏｒｐｏｒａｔｉｏｎによって販売されていたが、以前に販売されていたそのマウスは本発明を含まなかった。マウス６０は、下にある表面６２上でユーザによって移動されることが意図される。下にある表面６２は、何らかの特定の設計または特徴を有する必要はない。おそらくこの表面に対する要件は、その任意の一部が任意の他の一部とほぼ同一に見えるほど均質ではないということだけである。さらに、表面６２は、ある木材（または人工木材）中の木目など、概して平行に延びる線を含まないことが好ましい。木目に沿う方向のマウスの移動の任意の成分に対して、表面のイメージの差を検出することが難しい可能性があるからである。
【００２１】
ハウジング６４は、赤色であるが一般に光透過性である底部６６を含む。図２に示すように、ハウジング６４は、マウスの正面部の頂部に左選択ボタン６８および右選択ボタン（図示せず）を含む。追加のボタン７０が左側に設けられ、この追加のボタン７０は一般に、インターネットブラウジングアプリケーションに、後退させる、すなわち以前のウェブページを表示させるようにプログラムされる。（ブラウジングプログラムで以前に表示した）次のウェブページに進み、それを表示するために、類似のボタン（図示せず）が、ハウジング６４の反対側に含まれる。加えて、ユーザ回転可能ホイール７２がハウジング６４の正面の頂部中心に取り付けられ、それを回転させてアプリケーションプログラム内でスクロールすることができ、または押し下げて別のスクロール機能を始動することができる。コード７４はハウジング６４に結合され、ＰＣ２０または別のタイプのコンピューティング装置のＩ／Ｏポートに信号を通信する複数のリード（別々には図示せず）を含む。
【００２２】
図２に示すように、ハウジング６４は、表面６２に向かって下方に配向する赤色光を放出する発光ダイオード（ＬＥＤ）７８が配設されているマウント７６を概略的に示すために切除している。ＬＥＤ７８によって放出される赤色光の表面６２に対する入射角は、比較的鋭角である。ＬＥＤからの光は、表面６２によって、マウント７６内に配置されたピクセルイメージセンサ８０に向かって上方に反射する。表面から反射された光は、ピクセルイメージセンサ上に光を収束するレンズ８２を通過する。この好ましい実施形態では、ピクセルイメージセンサ８０は、２０×２０ピクセルアレイに構成された相補型金属酸化膜半導体（ＣＭＯＳ）タイプである。あるいは、電荷結合デバイス（ＣＣＤ）アレイピクセルイメージセンサを使用することもできる。ピクセルイメージセンサ８０は、表面６２の一部のイメージフレームに対応する出力信号を生成し、このフレームに対するイメージデータが、以下に説明するように本発明に従って処理するためにイメージセンサから迅速に読み取られる。この処理が行われる速度は迅速であるので、最大１８インチ／秒（４６ｃｍ／秒）の速度でしか従来技術の光学式マウスの移動を追跡することができなかった、先に販売されていた光学式マウスとは対照的に、本発明により、３７インチ／秒（９４ｃｍ／秒）超の速度でマウス６０の移動を追跡することが可能となる。
【００２３】
マウスの移動は、マウスの方向と相対的な公称Ｘ軸およびＹ軸（すなわち、Ｘ軸が名目上一般にマウスの幅方向に位置合せされ、Ｙ軸が名目上一般にマウスの長さ方向に位置合せされる）に関して決定されるが、これらの軸の方向はユーザ調節可能である。さらにこの好ましい実施形態では、これらの直交するＸ軸およびＹ軸に対する、表面上のマウスの移動のΔｘ成分およびΔｙ成分を示す出力信号を生成するために必要なほぼすべての処理が、マウス内で実施される。コード７４を介して搬送される信号は、表面６２上のマウスの移動を、解像度約４００ピクセル／インチ（約１５７ピクセル／ｃｍ）で示す。さらに、この好ましい実施形態では、表面のイメージフレームが約９０００フレーム／秒超の速度で取り込まれる。ここに図示していない代替実施形態では、ワイヤレスリンクによってＰＣ２０または他のタイプのコンピューティング装置に結合される同様のマウスが利用される。このワイヤレスマウスは、ピクセルイメージ検出器を用いて約６０００フレーム／秒の速度でイメージフレームを取り込むと予想される。
【００２４】
図３を参照すると、ブロック図全体は、表面６２上のマウスのユーザ制御移動に応答して、移動を判定してマウス６０からの出力信号を生成するための機能ブロックを示している。ピクセルイメージセンサによって生成されたアナログ信号は、検出器から、行ごとに、かつ各行のピクセルごとに読み取られる。この信号はアナログデジタル（Ａ−Ｄ）変換器９０に入力され、アナログデジタル（Ａ−Ｄ）変換器９０は、このアナログ信号を、対応するデジタル信号に解像度８ビット／ピクセルで変換する。したがって２０×２０イメージフレーム中の各ピクセルの値は、０から２５５の範囲であり、これはイメージフレームに関するグレースケールピクセルに対応する。光源およびイメージ検出器は、２０×２０イメージフレーム中の各ピクセルに関する平均値が約１２８（すなわち、フルスケール２５５の１／２）に等しくなるように制御される。
【００２５】
次いでＡ−Ｄ変換器９０によって生成されるデジタル信号は、機能ブロック９２に示す処理回路のナビゲーションブロックに入力される。この処理回路は、比較フレームの相関ウィンドウ内の連続する各ピクセルと、バッファメモリ中に格納される基準フレームの相関ウィンドウ内の対応するピクセルの周囲のピクセル位置の範囲との相互相関を決定する。各ピクセルの周囲のピクセル位置の範囲に対して、この処理回路は、基準フレーム内の連続するピクセルに関する自己相関も決定する。次いで、このように決定された相互相関および自己相関の成分を使用して、この処理回路は、表面６２に対するマウス６０の移動を示す、それぞれの直交軸に沿った変位Δｘおよび／またはΔｙに対応する出力信号を生成する。ブロック９４に示すように、このポインティングデバイスに関する出力信号は相対的移動を示し、ＰＣ２０または他のコンピューティング装置などのコンピュータに入力される。この信号は、ＰＳ／２ポートまたはＵＳＢポートなど、信号がそのポート用に適切にフォーマットされる任意のポートを介して入力することができる。
【００２６】
ナビゲーション処理回路１００の詳細を図４に示す。この回路は（図３に示す）Ａ−Ｄ変換器９０からデジタル信号を受け取る。イメージ検出器インターフェース１０２は、デジタル信号中にイメージデータとして含まれる各ピクセルについてのデジタルデータを、連続するピクセル、行×列としてイメージ検出器から読み取るタイミングの問題を処理する。次いでイメージフレームからのピクセルデータを高域フィルタ１０４を介して処理し、結果として得られるフィルタ後データを相関器１０６に入力する。相関器１０６は、以下でさらに説明するように、基準イメージに関するピクセルデータがロードされ、一時的に格納されるバッファメモリと、以前にロードした基準フレームをバッファメモリ中に再ロードするか、それとも現比較フレームに関するピクセルデータを新しい基準フレームとしてバッファメモリ中にロードするかを決定するＭＵＸとを含む。相関器１０６の状態は、ポインティングデバイス位置計算器１１０の制御下で、相関器状態マシン１０８によって制御される。
【００２７】
相関器１０６の出力は、限定された相互相関の範囲内で、ポインティングデバイスと、隣接する表面との間の相対的移動の方向および範囲を決定するのに使用するために、ポインティングデバイス位置計算器１１０に入力される。ポインティングデバイス位置計算器１１０内には、自己相関および相互相関を使用して、ナビゲーション処理回路からの移動信号出力の一部としてサブピクセル補間を決定する一部ピクセル計算器１１２も含まれる。ポインティングデバイス位置計算器に結合される移動信号出力インターフェース１１４は、ＰＣ上の選択されたタイプの入力ポートに入力するために、移動信号を適切にフォーマットする。この移動信号は、任意のΔｘおよびΔｙ整数成分、ならびにサブピクセル成分を含む。各軸についてのサブピクセル成分は、一部ピクセル計算器１１２によって決定される。ＰＳ／２、ＵＳＢ、またはコンピューティング装置の他の適切なポートを介して入力するためにフォーマットするとき、ユーザがマウスを制御して入力したことに応答して、マウス６０からの出力信号を使用してディスプレイ上のカーソルまたは他のオブジェクトの位置を制御することができる。
【００２８】
エッジ効果を回避するために、イメージ検出器インターフェース１０２は、２０×２０ピクセルイメージフレームの最初および最後の行と、最初および最後の列とを取り除き、元の２０×２０ピクセルアレイの最も内側の１８×１８ピクセルに関するデジタルイメージデータだけを高域フィルタ１０４に供給する。したがって、（２０×２０ピクセルイメージフレーム内の中心に位置する）１８×１８ピクセルアレイに対応するイメージフレームによるピクセルデータだけが、格納される各基準フレームについての相関器１０６のバッファメモリ中にロードされる。
【００２９】
図５には、バッファメモリ１２２の細部が示されている。バッファメモリ１２２は、ピクセルイメージデータをＭＵＸの出力１２０ｃを介してバッファメモリ１２２に選択的に供給することが可能である第１入力１２０ａおよび第２入力１２０ｂを有するＭＵＸ１２０から、連続するピクセルデータを受け取る。バッファメモリ中の以前に格納された基準フレームは、相関器状態マシン１０８（図４）によって供給されるＬＯＡＤ＿ＲＥＦ信号に応答して、バッファメモリ中に再ロードされる。あるいは、新しい基準フレームとして使用するために、現比較フレームに関するピクセルデータがバッファメモリ中にロードされる。したがってＭＵＸ１２０は、バッファメモリ１２２内に以前に格納されたピクセルデータを再ロードするか（通常の場合）、それとも現比較フレームに関するフィルタ後ピクセルデータ信号を使用して新しい基準フレームをロードするかを判定するための電子スイッチとして働く。
【００３０】
本発明の主な利点は、バッファメモリ内に格納された基準フレームに関するピクセルデータと、比較フレームに関するピクセルデータとを使用して計算される相互相関に基づいて移動を決定できることに関係する。比較フレームに関するピクセルデータは、メモリアレイ内に格納する必要がない。比較フレームの連続するピクセルに関するデータが、基準フレームに関するバッファメモリ１２２中に格納されたピクセルに関する、適切な対応するデータと共に使用するために、ポインティングデバイス位置計算器に入力される。次いで基準フレームに関する格納データと、比較フレームに関する着信データを使用して、可能な移動方向に関係する複数の異なる成分のそれぞれについての相互相関の成分が計算される。
【００３１】
この好ましい実施形態では、基準フレームと比較フレームの両方に関する合計１８×１８ピクセルアレイの特定の１２×１２ピクセル部分（すなわち相関ウィンドウ）だけに関して相互相関が決定される。相互相関決定で使用される１８×１８ピクセルの基準フレームおよび比較フレームの、この特定の１２×１２ピクセル部分は、各イメージフレーム内の１２×１２相関ウィンドウ位置内のピクセルに対応する。１２×１２相関ウィンドウの位置を、基準フレーム内および比較フレーム内で決定する方法に関する詳細を以下で説明する。
【００３２】
比較フレーム内の１２×１２相関ウィンドウの各ピクセルについてのデータがピクセルイメージセンサから一度に１ピクセル読み取られるとき、そのデータを使用する相互相関アレイの成分が、比較フレームピクセルに関するデータと基準フレームの相関ウィンドウ中の関連するデータとの差の絶対値を決定することによって計算される。本発明では、比較フレームピクセルデータを一度に１ピクセル処理することによって、比較フレームを別々のメモリバッファ内に格納することを必要とせずに相互相関を決定することができる。
【００３３】
相互相関を決定することに加えて、相関器はまた、基準フレームの相関ウィンドウ内の各ピクセルについての自己相関も決定する。新しい基準フレームをバッファメモリ１２２中にロードしない限り、基準フレームの自己相関成分が変化しないことに留意されたい。しかしこの実施形態では、新しい基準フレームがバッファメモリ１２２中にロードされたかどうかの如何に関わらず、新しい相互相関が決定されるごとに自己相関が再計算される。さらに、現在基準フレーム内で処理されているピクセルの周囲のピクセルの３×３アレイに関して自己相関が決定され、自己相関に関する合計９個の成分が得られる。しかし、３×３アレイ中の中心位置に関する自己相関成分は、常にゼロに等しいのでそれを計算する必要はなく、したがって、計算する必要があるのは８個の自己相関成分だけである。自己相関の決定と、自己相関の成分の配置とに関する詳細を以下で論じる。
【００３４】
バッファメモリ１２２は、１８個の異なるピクセルのそれぞれに関するデータの１８個の行１２４を含むことに加えて、新しい基準フレームがバッファメモリ中にロードされるときに相互相関を決定する際に使用するために、以前の基準フレームに関するデータがそれを介してシフトされ、格納される３８個の一時記憶位置１２６も含む。以前の基準フレームに関するデータを使用して相互相関を計算するために新しい基準フレーム中のピクセルに関するデータの最後の２つの行がバッファメモリ１２２中にロードされるとき、以前の基準フレームの最後の２つの行のピクセルに関するデータを格納するために一時記憶装置１２６が必要であることは明らかである。新しい基準フレームに関するデータがバッファメモリ１２２にロードされるとき、各ピクセル位置についてのデータが、図５の行の最左端に達するまで左にシフトされ（少なくとも図示する例に関しては）、次いでデータは、バッファメモリ内の次に高位の行の最右端にシフトされる。同様に、バッファメモリ１２２の１８×１８ピクセルアレイ中のピクセルに関するデータが一時記憶装置１２６を介して一度に１ピクセルだけシフトされ、その結果新しい基準フレームに関するデータが１８×１８アレイの左上隅に達するときに、古い基準フレームの最後の３８ピクセルに関するデータが一時記憶装置１２６内にシフトされる。したがって、以前の基準フレームに関するデータが、新しい基準フレームとしてバッファメモリ１２２中に現在ロードされている比較フレームの最後の行に関する相関を計算するために利用可能となる。
【００３５】
連続する各ピクセルについてのデータは、一般にシフトレジスタを介してシフトされるのと同様にバッファメモリを介してシフトされるので、バッファメモリ１２２は、シフトレジスタとある点で類似の、ある独自の特徴を有する。しかし、相互相関および自己相関を計算する際に使用するための一時記憶装置１２６の準備と、バッファメモリの選択された部分からデータを読み取る能力とは、バッファメモリ１２２の設計に固有のものである。
【００３６】
図６に、バッファメモリ１２２の上部の２つの行と一時記憶装置１２６の詳細を示す。新しい基準フレームをバッファメモリ１２２内に完全にロードしたとき、１８×１８ピクセルアレイ内の各行１２４中の各セル１３０のｘ，ｙ座標は、一般にこの図に示すようなものとなる。基準フレームを完全にバッファメモリにロードしたとき、ｘ，ｙ位置０，０を有するピクセルは、一時記憶装置１２６中のＴ０と符号を付けた一時セルに隣接する、バッファメモリ１２２の左上隅に配置されることになる。次いで、次の比較フレームに関する第１ピクセルデータを相関器内にロードしたとき、ピクセル０，０に関するイメージデータは通常、現基準フレームに関するデータをバッファメモリ１２２に再ロードする際に使用するために、第２ＭＵＸ入力１２０ｂに戻される。以前の基準フレームデータのこの再ロードは、十分な移動が行われた場合には生じないことになり、その結果新しい基準フレームをバッファメモリ１２２内にロードすることが必要となる。次に入力すべき比較フレームと、現基準フレームとの間の不十分な重なり合いが存在する状況を回避するために、新しい基準フレームをロードしなければならない。
【００３７】
ユーザが表面上でポインティングデバイスを移動させるとき、その移動の速度を使用して、読み取るべき次の比較フレームが現基準フレームと重なり合わないことを予測することができ、その結果新しい比較フレームを新しい基準フレームとしてバッファメモリ１２２中にロードすることが必要となることは明らかである。新しい基準フレームをロードする必要があるとき、ＭＵＸ１２０は第２入力１２０ｂではなく第１入力１２０ａを選択して、現比較フレームをバッファメモリ内にロードする。いずれにしても、現基準フレームの各ピクセルについてのデータが一時記憶装置１２６内にシフトされ、この一時記憶セクションの３８個の位置を介してシフトされた後、このデータは単に「トス」される。
【００３８】
図７に、相関器状態マシン１０８に入出力される様々な信号を示す。相関器状態マシン１０８への入力は、入力信号に関するポインティングデバイス位置計算器１１０（図４参照）によって供給される。ＦＩＬＴＥＲ＿ＶＡＬＩＤは、相関器への高域フィルタからの出力が現イメージフレームのピクセル位置に対して有効なデータであるかどうかを示す入力信号である。入力信号ＲＥＦ＿Ｘ＿ＳＴＡＲＴおよびＲＥＦ＿Ｙ＿ＳＴＡＲＴは、それぞれ現相関器ウィンドウに関するバッファメモリ１２２内のｘおよびｙ開始アドレスを指す。同様に、ＲＥＦ＿Ｘ＿ＥＮＤおよびＲＥＦ＿Ｙ＿ＥＮＤは、それぞれ基準フレーム中の相関器ウィンドウに関する終了アドレスを指す。最後の４つの入力信号は、現在処理されている比較フレームに関するｘおよびｙ開始アドレスと、ｘおよびｙ終了アドレスである。別の入力信号ＮＥＷ＿ＦＲＡＭＥは、次の比較フレームが撮像されており、バッファメモリ中に格納された基準フレームとの相互相関を決定する目的で、一度に１ピクセルだけ入力するために利用可能であることを相関器状態マシンに示す。
【００３９】
バッファメモリに、各ピクセルについてのデータを次の位置にシフトさせるバッファメモリの制御は、相関器状態マシン１０８によって出力されるＡＤＶＡＮＣＥ＿ＲＥＦ＿ＦＲＡＭＥ信号によって供給される。同様に、信号ＡＤＶＡＮＣＥ＿ＣＯＭＰ＿ＰＩＸＥＬがイメージ検出器インターフェースに印加され、比較フレーム中の次のピクセルに関するデータの入力が可能となる。相互相関および自己相関の計算は、それぞれＣＲＯＳＳ＿ＣＯＲＲＥＬＡＴＥおよびＡＵＴＯ＿ＣＯＲＲＥＬＡＴＥ信号によって初期化され、それらは相関器状態マシンによって出力される。
【００４０】
図８および図９に、ポインティングデバイスと、その隣接する表面との間の相対的移動を相互相関および自己相関の計算に基づいて決定するために本発明で実施されるステップを示す。ステップ１４０で、例えばポインティングデバイスの初期ブートアップ時に、すべての必要なレジスタを初期化する。次に、ブロック１４２で、出力信号によってピクセルイメージセンサから搬送されるデータを使用して、新しいイメージフレームを読み取るための論理を供給する。基準フレームは当初バッファメモリ内で利用可能ではないので、ブロック１４４でイメージデータをバッファメモリ内にロードする。ステップ１４６で与えるように、この初期基準フレームをロードした後、読み取る次のイメージフレームは比較フレームイメージであり、そのデータをピクセルごとに処理する。判定ブロック１４８は、現基準フレームピクセルと比較フレームピクセルの両方が有効であるかどうかを判定する。１８×１８ピクセル比較フレームおよび１８×１８ピクセル基準フレームの特定の１２×１２ピクセル部分である相関ウィンドウ内に現ピクセルがある場合、この判定は肯定となる。当初、相関ウィンドウは、基準フレームおよび比較フレームのそれぞれの中心に位置する。有効なピクセルでない場合、ステップ１５０で、次の比較フレームピクセルを読み取り、対応する次の基準フレームピクセルを使用するように、基準フレームに関するピクセルをその次の位置にシフトすることによってサイクルする。次いで判定ステップ１４８でのテストを繰り返す。
【００４１】
上記の通り、当初相関ウィンドウは、比較フレームと基準フレームの両方の中心に位置する。すなわち、これら２つのフレームのそれぞれの１８×１８ピクセルアレイ部分内の相関ウィンドウの両側の周囲に３列および３行マージンを有する（少なくとも２行および２列のマージンが、基準フレームおよび比較フレーム内の相関ウィンドウを取り囲むことに留意されたい）。
【００４２】
ステップ１５２では、相関器は、処理されている現ピクセルに関する相互相関係数のすべてを計算する。上記の通り、通常は１ピクセルに対して９個の相互相関係数が存在する。しかし、ある環境下では、相関アレイのサイズは３×３から５×５に増加し、合計２５個の相互相関係数が供給される。相互相関アレイのサイズを増やす理由を以下で論じる。しかし、このように相互相関アレイのサイズを増加することが必要となるのは、普通ではない環境下においてのみである。９個の相互相関係数（または必要なときは２５個の係数）の計算に続いて、ステップ１５４では、基準フレーム内の現ピクセルに関する８個の自己相関係数のすべてを計算する。次に、判定ステップ１５６では、相関ウィンドウ内の有効ピクセルのすべてを処理したかどうかを判定し、処理していない場合、論理ループはステップ１５０に戻る。
【００４３】
現比較フレームに関する有効ピクセルのすべてを処理した後、ステップ１５８では、基準フレームと、処理すべき次の比較フレームの両方に関する相関ウィンドウ位置を決定する。ステップ１５８を実施する際に適用する論理の詳細を以下で論じる。
【００４４】
ステップ１６０では、相関器が、次の比較フレームを一度に１ピクセルだけ読み取ることを開始する。現在読み取っている基準フレームおよび比較フレーム内の相関ウィンドウ位置に基づいて、ステップ１６２では、基準フレームおよび比較フレームのそれぞれについての３２４ピクセル内のｘ，ｙ開始位置を決定する。同様に、ステップ１６４では、１２×１２相関ウィンドウに関するｘ，ｙ終了位置を決定する。ステップ１６６では、相対的開始位置に基づいて、基準フレームと比較フレームの関連するピクセル間でオフセットを決定する。基準フレーム内の開始位置および終了位置は、それぞれの１８×１８イメージアレイについて、比較フレーム内の開始位置および終了位置と２行および２列だけ異なる（偏位している）可能性がある。
【００４５】
判定ステップ１６８は、判定したオフセットが正であるかどうかを判定し、正である場合、この論理は判定ステップ１７０に進み、判定ステップ１７０は、比較ピクセルと、対応する基準ピクセルが整合しているかどうかを判定する。このステップは実際には、相互相関を決定するために適切な比較フレームピクセルおよび基準フレームピクセルが使用されているかどうかを判定する。そうでない場合、ステップ１７２では、判定ステップ１７０での判定を繰り返す前に、次の基準フレームピクセルにシフトする。基準フレームピクセルおよび比較フレームピクセルが整合した後、この論理は、図９のステップ１７８に進む。
【００４６】
判定ステップ１６８での結果が、オフセットが負であることを示す場合、この論理は図９の判定ステップ１７４に進む。このステップは、比較ピクセルと対応する基準ピクセルが整合しているかどうかを再度判定し、整合していない場合、ステップ１７６で、次の比較フレームピクセルを読み取る。このようにして、この論理は、相関ウィンドウ内の対応する基準フレームピクセルおよび比較フレームピクセルが相互相関を計算するために使用されることを保証する。判定ステップ１７０または１７４のどちらかの判定に続いて、ステップ１７８では、現ピクセルに関する相互相関係数または成分のすべてを計算する。同様に、ステップ１８０では、基準フレーム内の現ピクセルに関する自己相関係数または成分のすべてを計算する。判定ステップ１８２は、有効ピクセルのすべてを処理したかどうかを判定し、そうでない場合はステップ１８４で次の比較フレームピクセルを読み取り、基準フレームデータに関する位置のすべてが１つの位置だけシフトされるように基準フレームをサイクルする。次いでステップ１７８を繰り返す。
【００４７】
有効ピクセルのすべてを処理した後、ステップ１８６で、相互相関のための９個の成分の間（または、必要なときは２５個の成分の間）の最大相関ピクセルの位置を識別する。最大相関の位置は、基準フレームの相対位置と比較フレームの相対位置との間で移動が行われた方向を示す。したがって、８つの可能な方向のいずれにも移動を行うことが可能であり、あるいは、相関アレイの中心位置に最大相関がある場合、移動を行わないことも可能である。
【００４８】
次いでステップ１８８では、自己相関（および相互相関）成分に基づいてサブピクセル補間を決定する。ブロック１９０では、最大相関が生じる方向と、サブピクセル補間との組合せにより、ポインティングデバイスが接続されているコンピューティング装置で使用する目的でナビゲーション処理回路から出力されるΔｘおよびΔｙに関する成分を決定する。ブロック１９２では、表面上のポインティングデバイスの速度も、定義した時間にわたる所与の方向への累積した移動の関数として決定する。この速度に基づいて、処理される次の比較イメージを使用して新しい基準フレームをバッファメモリ内にロードすることが必要かどうかに関する判定を行う。この判定により、ポインティングデバイスの隣接する表面に対する移動方向を決定するために、十分な重なり合いが後続の比較フレームと基準フレームの間で与えられることが保証される。次の比較フレームを新しい基準フレームとして使用するためにバッファメモリ内にロードすることが必要である場合、ステップ１９６で、それを引き起こす信号をＭＵＸ１２０に供給する。そうでない場合、判定ステップ１９４からステップ１９８に進み、そこで、ポインティングデバイスの隣接する表面に対する移動の再度の判定に使用するために、基準イメージデータのバッファメモリ内への再ロードを開始する。次いでこの論理は、図８のステップ１５８に戻り、基準フレームおよび相関フレームの両方の相関ウィンドウ位置を決定する。
【００４９】
相関ウィンドウ位置を決定するステップ１５８は、単純なグラフィック例だと理解し易い。図１０および９Ｂでは、グラフィックイメージ２１０は、表面が下にあるマウス６０を表す。グラフィックイメージ２１０の部分の２０×２０イメージは、領域２１２を占有し、マウス内のイメージセンサで検出されるイメージに対応する。領域２１２は、図１１の矢印２１４で示すように、マウスが左に移動するときにグラフィックイメージ２１０上を左に移動する。
【００５０】
基準フレームおよび比較フレーム内の相関ウィンドウの位置を決定する際に適用される論理を、マウスがグラフィックイメージ上を移動するときにマウス６０内のイメージセンサによって撮像されるグラフィックイメージ２１０の部分に関して示す。図１２の第１行に、領域２１２の１８×１８ピクセルを有する基準フレーム２１６を示す。基準フレーム２１６は、グラフィックイメージ２１０を含む棒線画の顔の左側を含む。初めに、図１２の列Ａ中の比較フレーム２１８は、基準フレーム２１６と同じピクセルデータを含む。しかし、マウスが左に向かって移動するとき、列Ｂに示す１８×１８ピクセル比較フレーム２２０はわずかに左にシフトし、その結果、比較フレーム２１８の左側よりも、下にある表面のイメージをわずかに多く含み、比較フレーム２１８の右側よりも、下にある表面のイメージをわずかに少なく含む。マウスをグラフィックイメージ上でさらに左に移動するとき、比較フレーム２２２および２２４内に含まれるグラフィックイメージ２１０の部分のより一層の変化が列ＣおよびＤで生じる。
【００５１】
当初、列Ａでは、相関ウィンドウ２２６ａが基準フレーム２１６の中心部分内に配置され、この相関ウィンドウ２２６ａは、１８×１８ピクセル基準フレーム内の中心に置かれた最も内側の１２×１２ピクセル領域を含む。同様に、列Ａでは、比較フレーム２１８内の相関ウィンドウ２３０ａも、１２×１２ピクセルアレイとして１８×１８ピクセル比較フレーム２１８内の中心に置かれる。しかし、列Ｂでは、マウス６０が左に向かって移動する結果として、相関ウィンドウ２３０ｂが比較フレーム２２０の右マージンに向かってシフトされ、その結果１２×１２ピクセル比較相関ウィンドウ内のイメージの一部が一般に、列Ｂ内の１２×１２基準相関ウィンドウ内のイメージと一致する。
【００５２】
列Ｃでは、マウスの左への運動がさらに行われるので、基準相関ウィンドウ２２６ｂが基準相関ウィンドウ２２６ａに対してわずかに左にシフトしているように示されている。したがって、このような基準相関ウィンドウのシフトにより、基準相関ウィンドウ２２６ｂ内のグラフィックイメージの部分と比較相関ウィンドウ２３０ｂ内のグラフィックイメージの部分との間の比較的近い一致が得られる。この例の最後の列では、基準相関ウィンドウ２２６ｃ内のグラフィックイメージの部分と比較相関ウィンドウ２３０ｂ内のグラフィックイメージの部分との間の比較的近いマッチを維持しながら、基準相関ウィンドウ２２６ｃが基準フレーム２１６のさらに左にシフトされる。
【００５３】
先のグラフィック例より、相互相関の以前の決定と、関係する移動とに基づいて、相関ウィンドウの相対位置が、次の比較フレームがピクセルごとに処理されるときに後続の移動を決定するために、基準フレームと比較フレームの少なくとも一方でシフトされ、基準フレームおよび比較フレームの両方の相関ウィンドウ内に出現するイメージの部分が最大化されることは明らかであろう。各フレーム内の相関ウィンドウの位置の変化は、最後の相互相関を使用して決定されたばかりのポインティングデバイスの移動に基づいて決定される。
【００５４】
図１３を参照すると、１８×１８ピクセル基準フレーム（または比較フレーム）と相関ウィンドウの位置との関係を理解することが幾分容易となる。この図に示すように、１８×１８基準フレーム２４０は、基準フレーム内の１２×１２相関ウィンドウ２４４の可能な位置の限界を画定する長い破線２４２を含む。図１３に示す例では、相関ウィンドウ２４４は、限界線の上側マージンと左側マージンにシフトされている。１８×１８ピクセル比較フレーム内にも、１２×１２相関ウィンドウの可能な位置に関して類似の関係が存在する。したがって、可能な範囲で、基準フレームと比較フレームの一方または両方の中の１２×１２相関ウィンドウの位置の変化が、これらの限界内で行われ、連続する各比較フレームと比較すべき基準フレームの部分の間の重なり合いの範囲が最大化される。基準フレームおよび比較フレーム内の相関ウィンドウの配置が、以前の比較フレームに関する、基準フレームに対する最大相関のピクセルの位置によって決定される。表面上のポインティングデバイスの速度が新しい基準フレームをロードすべきであることを示すとき、以前の移動の決定を使用して、新しい基準フレーム内と、後続の比較フレーム内の１２×１２相関ウィンドウの相対位置を決定することができる。
【００５５】
図１３には、１２×１２相関ウィンドウ２４４の左上隅に「Ｐ」と示すピクセル位置２４８に対するピクセル位置の３×３アレイ２４６も示す。位置２４８の周囲の３×３ピクセルアレイは、相互相関に関する９個の成分を示し、したがって、下にある表面に対するポインティングデバイスの可能な移動方向を示す。後続のピクセルデータは、位置２４８にシフトされ、９個の係数の成分の別の決定が相関ウィンドウ内の１４４個のピクセルに関する以前の決定に加えられる。同様に、基準フレームでは、１２×１２相関ウィンドウを有する１４４個のピクセルのそれぞれに関して自己相関が決定される。この相互相関を使用して最大相関の方向が決定される（これは、比較フレームおよび基準フレーム内の関係するピクセル間の最小の差の位置または方向に対応する）。したがって、相互相関アレイ内の最大相関位置は、移動方向を示す。中心位置での最大相関は、実質的に移動が行われないことを示す。
【００５６】
表面の品質または他の条件により、基準フレームと比較フレームとの間の相互相関の９個の成分に関する最大の差が引き起こされ、事前定義した最小値より下となる場合、この論理は、表面に対するポインティングデバイスの移動を決定するために現相互相関に依拠することができないと判定することになる。したがって、次の比較フレームに関して、比較フレーム内の１４４個のピクセルのそれぞれに対して２５個の係数を決定することになる。これらの２５個の位置は、図１３の点線２５０によって囲まれる。５×５相互相関アレイは、ｘ方向の正または負のどちらかの方向に２ピクセルだけ、かつ／またはｙ方向の正または負のどちらかの方向に２ピクセルだけ、相対的移動を決定することができる。その後、３×３アレイの係数に対して再び相互相関が行われ、ｘ方向に関して−１から＋１の値、ｙ方向に関して−１から＋１の値の範囲内の移動の方向が決定される。
【００５７】
図１４に、３×３ピクセルアレイ２６０の中心の位置２６２のピクセルＰ０，０に対する自己相関を決定することに関連して使用される命名法を示す。以下に示す式に関連して、変数ａの値は−１から１の範囲であり、変数ｂの値も−１から１の範囲であり、したがって、図１４に示すように、Ｐ−１，−１からＰ１，１の９個の位置に基づいて自己相関が供給される。このケースでの自己相関は、位置２６２の周囲の８個の位置２６４のそれぞれについての位置２６２に対するものである。ピクセル位置に関する、そのピクセル自体に対する自己相関は常に１であるので、位置２６２に関する自己相関成分を計算する必要はない。
【００５８】
図１５に、４つの異なる象限の配置を示す。これらの象限のうちの１つが、ポインティングデバイスと表面との間の最後に行われた相対的移動の方向に基づいて選択され、上記で説明したように、相対的移動が相互相関から決定される。自己相関決定に関して最良の相関（最小の差）が見つかった（中心位置２８０の周囲の）位置に応じて、それぞれ点線２７２、短い破線２７４、点鎖線２７６、および鎖線２７８で示す４つの象限０、１、２、３のうちの１つが識別されることになる。したがって最大自己相関が計算された象限により、移動信号に対してサブピクセル補間成分が割り当てられたΔｘおよびΔｙを計算する際に、４つの異なる式のうちのどれを使用するかが判定される。相互相関および自己相関を計算するための式の詳細を以下で説明する。
【００５９】
相互相関および自己相関を決定するための式
ａ成分およびｂ成分に関して、比較フレームと基準フレームの間の相互相関を計算するための一般的な式は以下のように与えられる。
【００６０】
【数１】
0004198399.tif 000002
【００６１】
上式で、この好ましい実施形態では通常、−１≦ａ≦１、−１≦ｂ≦１であり、したがって各フレームに対して合計９個の相互相関成分が存在する。好ましい実施形態では、ＮとＭはどちらも１１に等しい。
【００６２】
ポインティングデバイスが移動している表面が一般に一様な性質であるために、現比較フレームに関して計算される最小相互相関成分が事前定義したしきい値未満である場合、この結果に依拠することはできず、この結果は廃棄されることになる。例えば、一般に一様なグレースケール値を有し、一般に均質なテクスチャを有する表面エリアは、移動を正確に示すことのできない相互相関を生み出す可能性がある。このような結果が相互相関に対して得られた場合、２５個の相互相関成分を有する代替５×５相互相関アレイが決定され、相関ウィンドウを比較フレームおよび基準フレームとより良好に整合するために使用される相関最小値が得られる。このより大きい相互相関アレイからの情報を使用して、相関ウィンドウの位置をより良好に決定することができる。しかし、次の比較フレームに関しては、論理は、再び９個の相互相関成分を有する３×３相互相関アレイの使用に戻ることになる。
【００６３】
基準フレームのピクセルに関する自己相関成分を計算するための一般式は、相互相関を決定するための式と類似であり、以下のようになる。
【００６４】
【数２】
0004198399.tif 000003
【００６５】
ただし、好ましい実施形態では、−１≦ａ≦１、−１≦ｂ≦１であり、したがって各フレームに対して合計９個の自己相関成分が存在する。この場合も、ＮとＭはどちらも１１に等しい。ａとｂがどちらも０に等しい場合についての自己相関成分は常に１に等しく、したがって相関ウィンドウ内の各ピクセルに対して計算する必要のある自己相関成分は８個だけである。
【００６６】
表面上のポインティングデバイスの相対的移動を示すΔｘおよびΔｙを指定する際により良好な解像度を供給するサブピクセル補間を決定するために、自己相関値および相互相関値の両方を２ステップのプロセスで利用する。まず、自己相関曲線の形状（一般に凹面形状またはすり鉢形状）を特徴付ける変数が以下のように決定される。
【００６７】
Ｂ１１＝３／２＊［（ＡＣ３＋ＡＣ７）−（ＡＣ１＋ＡＣ９）］
Ｂ２０＝２＊［（ＡＣ４＋ＡＣ１＋ＡＣ７＋ＡＣ３＋ＡＣ６＋ＡＣ９）］
Ｂ０２＝２＊［（ＡＣ１＋ＡＣ２＋ＡＣ３＋ＡＣ９＋ＡＣ８＋ＡＣ７）］
ＤＥＮＯＭ＝［Ｂ２０＊Ｂ０２−Ｂ１１＊Ｂ１１］
上式で、ＡＣ１からＡＣ９は、前述のように決定される自己相関係数に対応する。１４４個のピクセル位置に対して決定されるこの９個の自己相関成分ＡＣ１からＡＣ９は、図１４に示す３×３アレイ２６０の各隅で番号を識別することと一貫して、左上のＡＣ１から右下のＡＣ９の順に番号が付けられる。次に、図１５に示すように、ＭＩＮＩＭＵＭ＿ＱＵＡＤ＿ＬＯＣＡＴＩＯＮが、最小の自己相関成分が見つかった自己相関アレイの象限に基づいて決定される。これらの４つの象限すべては、自己相関係数ＡＣ５に対応する中心自己相関値、位置２８０上で重なり合う。ΔｘおよびΔｙに関するサブピクセル補間値が、最小相互相関値に基づいて、かつ最小相互相関差値が見つかった象限（０、１、２、または３）の関数として、上記で計算される自己相関パラメータと、選択される相互相関値とを使用し、以下の各式の１組を使用して決定される。
【００６８】
象限０
ｓｕｂ＿ｐｉｘ＿ｘ＝−１／２＋２＊［（Ｂ０２−Ｂ１１）＊（Ｃ１−Ｃ５）＋（Ｂ０２＋Ｂ１１）＊（Ｃ４−Ｃ１）］／ＤＥＮＯＭ
ｓｕｂ＿ｐｉｘ＿ｙ＝−１／２＋２＊［（Ｂ２０−Ｂ１１）＊（Ｃ１−Ｃ５）＋（Ｂ２０＋Ｂ１１）＊（Ｃ４−Ｃ１）］／ＤＥＮＯＭ
象限１
ｓｕｂ＿ｐｉｘ＿ｘ＝１／２−２＊［（Ｂ０２−Ｂ１１）＊（Ｃ３−Ｃ５）＋（Ｂ０２＋Ｂ１１）＊（Ｃ６−Ｃ２）］／ＤＥＮＯＭ
ｓｕｂ＿ｐｉｘ＿ｙ＝−１／２＋２＊［（Ｂ２０−Ｂ１１）＊（Ｃ３−Ｃ５）＋（Ｂ２０＋Ｂ１１）＊（Ｃ６−Ｃ２）］／ＤＥＮＯＭ
象限２
ｓｕｂ＿ｐｉｘ＿ｘ＝１／２−２＊［（Ｂ０２−Ｂ１１）＊（Ｃ９−Ｃ５）＋（Ｂ０２＋Ｂ１１）＊（Ｃ６−Ｃ８）］／ＤＥＮＯＭ
ｓｕｂ＿ｐｉｘ＿ｙ＝１／２−２＊［（Ｂ２０−Ｂ１１）＊（Ｃ９−Ｃ５）＋（Ｂ２０＋Ｂ１１）＊（Ｃ６−Ｃ８）］／ＤＥＮＯＭ
象限３
ｓｕｂ＿ｐｉｘ＿ｘ＝−１／２＋２＊［（Ｂ０２−Ｂ１１）＊（Ｃ７−Ｃ５）＋（Ｂ０２＋Ｂ１１）＊（Ｃ４−Ｃ８）］／ＤＥＮＯＭ
ｓｕｂ＿ｐｉｘ＿ｙ＝１／２−２＊［（Ｂ２０−Ｂ１１）＊（Ｃ７−Ｃ５）＋（Ｂ２０＋Ｂ１１）＊（Ｃ４−Ｃ８）］／ＤＥＮＯＭ
上式で、相互相関に関するＣ１成分からＣ９成分は、図１４に示したアレイ要素の各隅の番号で識別されるアレイ位置にも示されている。
【００６９】
本発明を、好ましい実施形態に関連して説明したが、頭記の特許請求の範囲内で多くの修正を行えることを当業者は理解されよう。したがって、決して本発明の範囲を上記の説明によって限定することを意図するものではなく、本発明の範囲は、もっぱら頭記の特許請求の範囲を参照することによって決定される。
【図面の簡単な説明】
【図１】従来型のパーソナルコンピュータと、本発明を実施するポインティングデバイスの形態の汎用コンピューティング装置についての例示的システムのブロック図である。
【図２】本発明を利用する光マウスの部分切除側面図である。
【図３】Ｘ軸およびＹ軸に対するポインティングデバイスの移動を決定するためにポインティングデバイス内で使用される構成要素を示す機能ブロック図である。
【図４】本発明の一実施形態によるポインティングデバイスで使用される電子処理回路のブロック図である。
【図５】自己相関を計算する際に使用し、かつ表面の比較フレームからのイメージデータの連続するピクセルに対する相互相関を決定するために、表面の基準フレームに関するイメージデータがロードされるメモリバッファに結合されたマルチプレクサ（ＭＵＸ）の概略図である。
【図６】図５のバッファメモリの一部と一時記憶装置の拡大図である。
【図７】相関器状態マシンと、それに入出力される信号を示すブロック図である。
【図８】ポインティングデバイスと隣接する表面との間の相対的移動を決定するための、本発明で実施される論理を示す流れ図である。
【図９】ポインティングデバイスと隣接する表面との間の相対的移動を決定するための、本発明で実施される論理を示す流れ図である。
【図１０】表面の一部を示す図である。
【図１１】図１０に示す表面の一部を示し、かつ光学式マウスが表面上を速度約２ピクセル／フレームで移動するときに取り込まれるイメージフレームを示す図である。
【図１２】マウスが図１１に示す表面を移動するとき、４つの連続する比較フレームのそれぞれについての基準フレーム、比較フレーム、基準フレーム内の相関ウィンドウの配置、および比較フレーム内の相関ウィンドウの配置を示す図である。
【図１３】メモリバッファ内に格納される基準フレームを概略的に示し、相関ウィンドウの１つの位置を識別し、かつ基準フレーム内の相関ウィンドウの他の可能な位置に関する制限を示す図である。
【図１４】基準フレーム内の連続する各フレームについて、自己相関の成分を決定する際に使用されるピクセル位置を識別する３×３アレイのピクセルの概略図である。
【図１５】サブピクセル補間を計算するために利用される式の決定に使用される４つの象限のそれぞれに含まれるピクセルを識別する概略図である。
【符号の説明】
２０  パーソナルコンピュータ
２１  処理装置
２２  システムメモリ
２３  システムバス
２４  読取り専用メモリ
２５  ランダムアクセスメモリ
２６  基本入出力システム
２７  ハードディスクドライブ
２８  磁気ディスクドライブ
２９  取外し可能磁気ディスク
３０  光ディスクドライブ
３１  取外し可能光ディスク
３２  ハードディスクドライブインターフェース
３３  磁気ディスクドライブインターフェース
３４  光ディスクドライブインターフェース
３５  オペレーティングシステム
３６  アプリケーションプログラム
３７  他のプログラムモジュール
３８  プログラムデータ
４０  キーボード
４２  ポインティングデバイス
４６  Ｉ／Ｏ装置インターフェース
４７  モニタ
４８  ビデオアダプタ
４９  リモートコンピュータ
５０  外部メモリ記憶装置
５１  ローカルエリアネットワーク
５２  ワイドエリアネットワーク
５３  ネットワークインターフェースまたはアダプタ
５４  モデム
６０  マウス
６２  表面
６４  ハウジング
６６  底部
６８  左選択ボタン
７０  追加のボタン
７２  ユーザ回転可能ホイール
７４  コード
７６  マウント
７８  発光ダイオード
８０  ピクセルイメージセンサ
９０  アナログデジタル変換器
９２  処理回路のナビゲーションブロック
１００  ナビゲーション処理回路
１０２  イメージ検出器インターフェース
１０４  高域フィルタ
１０６  相関器
１０８  相関器状態マシン
１１０  ポインティングデバイス位置計算器
１１２  一部ピクセル計算器
１１４  移動信号出力インターフェース
１２０  ＭＵＸ
１２２  バッファメモリ
１２４  行
１２６  一時記憶位置
１３０  セル
２１０  グラフィックイメージ
２１２  領域
２１６  基準フレーム
２１８、２２０、２２２、２２４  比較フレーム
２２６ａ、２２６ｂ、２２６ｃ  基準相関ウィンドウ
２３０ａ、２３０ｂ  比較相関ウィンドウ
２４０  １８×１８基準フレーム
２４４  相関ウィンドウ
２４６  ３×３アレイ
２６０  ３×３ピクセルアレイ
【図１】
0004198399.tif 000005
【図２】
0004198399.tif 000006
【図３】
0004198399.tif 000007
【図４】
0004198399.tif 000008
【図５】
0004198399.tif 000009
【図６】
0004198399.tif 000010
【図７】
0004198399.tif 000011
【図８】
0004198399.tif 000012
【図９】
0004198399.tif 000013
【図１０】
0004198399.tif 000014
【図１１】
0004198399.tif 000015
【図１２】
0004198399.tif 000016
【図１３】
0004198399.tif 000017
【図１４】
0004198399.tif 000018
【図１５】
0004198399.tif 000019