(57)【要約】オーバーサンプリング山登りおよび山下りを範囲と併せて使用して、結果の二次元集合において多数の指を検出および追跡する方法。【選択図】図７
2016503215.tif 000002
【特許請求の範囲】
【請求項１】
タッチ・センサからの測定値の二次元集合を使用して多数の物体を検出し追跡する方法であって、
１）少なくとも１本の指の存在を示すように、０よりも大きい結果を有する第１指位置を識別するために、位置の二次元アレイを走査するステップと、
２）前記第１指位置に直接隣接して、それよりも高い値を有する位置があるか否か判定するために山登り手順を実行するステップと、
３）最も高い第１指位置が発見されるまで、前記山登り手順を繰り返すステップと、
４）前記第１指位置と第２の指との間において境界を識別するために、山下りアルゴリズムを実行するステップと、
を含む、方法。
【請求項２】
請求項１記載の方法において、更に、走査するときに前記位置の二次元アレイをオーバーサンプリングすることによって、前記第１指位置に隣接する少なくとも１つの位置も少なくとも１つの指の存在を確認する結果を有することを確かめるステップを含む、方法。
【請求項３】
請求項１記載の方法において、前記山登り手順が、更に、最も値が高い前記第１指位置を発見して新たな現在の第１指位置を形成するために、エイリアシングによって生ずる極小値を迂回するステップを含む、方法。
【請求項４】
請求項３記載の方法において、前記極小値を迂回する方法が、更に、前記新たな現在の第１指位置を決定するために近直交軸結果の加重和を比較するステップを含む、方法。
【請求項５】
請求項４記載の方法において、前記山登りアルゴリズムが、更に、前記新たな現在の第１指位置を決定するために、４つの最も近い位置の４−関連比較を実行するステップを含む、方法。
【請求項６】
請求項５記載の方法において、近直交軸結果の加重和を比較するステップが、更に、前記現在の第１指位置を中心とする登り方向毎に、別個のフィルタ・データ・アレイを形成するステップを含む、方法。
【請求項７】
請求項６記載の方法において、前記加重和が、更に、ある位置により多くの重みを与え、他の位置により少ない重みを与える加重パターンを適用するステップを含む、方法。
【請求項８】
請求項６記載の方法において、前記山登りアルゴリズムが、更に、
１）前記山登り手順に最大結果を有する位置を識別させない指の実際の位置の周囲において、繰り返しループを配置するステップと、
２）前記山登り手順が現在の測定サイクルにおけるある位置を繰り返すとき、前記繰り返しループを終了するステップと、
を含む、方法。
【請求項９】
請求項６記載の方法において、前記山登り手順が、更に、
１）前記山登り手順に最大結果を有する位置を識別させない指の実際の位置周囲において、繰り返しループを配置するステップと、
２）前記山登り手順が前記現在の第１指位置をN回移動させたときに、前記繰り返しループを終了するステップと、
を含む、方法。
【請求項１０】
請求項１記載の方法において、前記山下りアルゴリズムが、更に、同じ指の一部であると見なされる結果の範囲を含ませるステップを含む、方法。
【請求項１１】
請求項１０記載の方法において、前記山下りアルゴリズムが、更に、範囲を伴う隣接結果の比較によって、隣接する指との境界を識別するステップを含む、方法。
【請求項１２】
請求項１１記載の方法において、更に、既に識別された指を除外しながら、ステップ１から４までを繰り返すステップを含む、方法。
【請求項１３】
タッチ・センサからの測定値の二次元集合を使用して１つの物体を検出および追跡する方法であって、
１）指の存在を示すように、０よりも大きい結果を有する指位置を識別するために、位置の二次元アレイを走査するステップと、
２）前記指に直接隣接して、それよりも高い値を有する位置があるか否か判定するために、山登り手順を実行するステップと、
３）最も高い指位置が発見されるまで、前記山登り手順を繰り返すステップと、
を含む、方法。
【請求項１４】
請求項１３記載の方法において、更に、走査するときに前記位置の二次元アレイをオーバーサンプリングすることによって、前記指位置に隣接する少なくとも１つの位置も、前記指の存在を確認する結果を有することを確かめるステップを含む、方法。
【請求項１５】
請求項１３記載の方法において、 前記山登り手順が、更に、最も値が高い前記指位置を発見して新たな現在の第１指位置を形成するために、エイリアシングによって乗ずる極小値を迂回するステップを含む、方法。
【請求項１６】
請求項１５記載の方法において、 前記極小値を迂回する方法が、更に、前記新たな現在の指位置を決定するために近直交軸結果の加重和を比較するステップを含む、方法。
【請求項１７】
請求項１６記載の方法において、 前記山登りアルゴリズムが、更に、前記新たな現在の指位置を決定するために、４つの最も近い位置の４−関連比較を実行するステップを含む、方法。
【請求項１８】
請求項１７記載の方法において、近直交軸結果の加重和を比較するステップが、更に、前記現在の指位置を中心とする登り方向毎に、別個のフィルタ・データ・アレイを形成するステップを含む、方法。
【請求項１９】
請求項１８記載の方法において、前記加重和が、更に、ある位置により多くの重みを与え、他の位置により少ない重みを与える加重パターンを適用するステップを含む、方法。
【請求項２０】
請求項１８記載の方法において、前記山登りアルゴリズムが、更に、
１）前記山登り手順に、最大結果を有する位置を識別させない指の実際の位置の周囲において繰り返しループを配置するステップと、
２）前記山登り手順が現在の測定サイクルにおけるある位置を繰り返すとき、前記繰り返しループを終了するステップと、
を含む、方法。
【請求項２１】
請求項１８記載の方法において、前記山登り手順が、更に、
１）前記山登り手順に、最大結果を有する位置を識別させない指の実際の位置周囲において繰り返しループを配置するステップと、
２）前記山登り手順が前記現在の指位置をＮ回移動させたときに、前記繰り返しループを終了するステップと、
を含む、方法。
【請求項２２】
請求項１３記載の方法において、前記山下りアルゴリズムが、更に、同じ指の一部であると見なされる結果の範囲を含むステップを含む、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的には、タッチ・センサに関する。更に特定すれば、本発明は、タッチ・センサからのデータを使用し、タッチ・センサからの結果の二次元集合を使用して多数の物体を検出および追跡する方法に関する。
【背景技術】
【０００２】
容量感応タッチパッドには様々な設計がある。本発明と共に動作するように変更可能な既存のタッチパッド設計の１つに、CIRQUE（登録商標）Corporation（シルク社）によって製作されるタッチパッドがある。したがって、いずれの容量感応タッチパッドであれ、どのように変更すれば本発明を用いて動作可能になるかより良く理解するためには、基礎技術を調べることが有用である。
【０００３】
CIRQUE（登録商標）Corporation製のタッチパッドは、相互容量検知デバイスであり、一例を図１にブロック図として示す。このタッチパッド１０では、Ｘ（１２）およびＹ（１４）個の電極ならびに検知電極１６の格子が、タッチパッドのタッチ感応エリア１８を規定するために用いられる。通例、タッチパッド１０は約１６×１２電極、または空間に制約があるときには８×６電極の矩形格子である。これらＸ（１２）およびＹ（１４）（または行および列）電極には、１つの検知電極１６が織りまぜられる。 全ての位置測定は検知電極１６を通じて行われる。
【０００４】
CIRQUE（登録商標）Corporation製のタッチパッド１０は、検知線１６上における電荷の不均衡を測定する。タッチパッド１０上またはその近傍に指示物体(pointing object)がない場合、タッチパッド回路２０は均衡状態にあり、検知線１６上には電荷の不均衡はない。指示物体がタッチ表面（タッチパッド１０の検知エリア１８）に接近またはタッチしたときの容量性結合のために、指示物体が不均衡を生ずると、電極１２、１４上に容量変化が生ずる。測定するのは容量変化であって、電極１２、１４上における絶対容量値ではない。タッチパッド１０は、検知ライン上において均衡を再確立するため即ち再現するために、検知ライン１６に注入しなければならない電荷量を測定することによって、容量変化を判定する。
【０００５】
以上のシステムは、タッチパッド１０上またはその近傍にある指の位置を、以下のようにして判定するために利用される。この例では、行電極１２について説明し、列電極１４についても同様に繰り返される。行および列電極の測定から得られた値が、タッチパッド１０上またはその近傍にある指示物体の重心である交点を決定する。
【０００６】
第１ステップでは、Ｐ，Ｎ発生器２２からの第１信号によって第１組の行電極１２が駆動され、Ｐ，Ｎ発生器からの第２信号によって、異なるが隣接する第２組の行電極が駆動される。タッチパッド回路２０は、どの行電極が指示物体に最も近いかを示す相互容量測定デバイス２６を用いて、検知線１６からの値を得る。
【０００７】
しかしながら、マイクロコントローラ２８の制御下にあるタッチパッド回路２０は、行電極のどちら側に指示物体が位置するか未だ判定することができず、タッチパッド回路２０は、指示物体が電極からどの位離れて位置するか判定することもできない。このため、このシステムは駆動される電極１２のグループを１電極だけずらす。言い換えると、グループの一方側に電極を追加し、グループの逆側にある電極はもはや駆動されない。次いで、新たなグループがＰ，Ｎ発生器によって駆動され、検知線１６の第２測定値が取り込まれる。
【０００８】
これら２つの測定値から、行電極のどちら側に指示物体が位置するのか、そしてどれ位離れて位置するのか判定することが可能になる。次いで、２つの測定された信号の振幅を比較する式を用いて、指示物体の位置判定を行う。
【０００９】
CIRQUE（登録商標）Corporation製タッチパッドの感度または分解能は、１６×１２格子の行および列電極が含意するよりも遥かに高い。分解能は、通例、１インチ当たり約９６０カウント以上である。正確な分解能は、コンポーネントの感度、同じ行および列上にある電極１２、１４間の間隔、そして本発明にとっては重要でないその他の要因によって決定される。
【００１０】
以上のプロセスは、Ｐ，Ｎ発生器２４を用いて、Ｙ即ち列電極１４に対して繰り返される。CIRQUE（登録商標）製タッチパッドはＸおよびＹ電極１２、１４の格子、ならびに別個の単独検知電極１６を使用するが、多重化を用いることによって、検知電極１６もＸまたはＹ電極１２、１４にすることができる。いずれの設計でも、本発明が機能することを可能にする。
【００１１】
先行技術は、タッチパッド上にある多数の物体の検出および追跡を既に可能にするタッチパッドの記載を含む。この先行技術の特許は、タッチパッドが、当該タッチパッド上であればいずれの場所でも個々の物体を検出し追跡することを教示し、特許請求する。この特許は、物体が曲線上において「最大値」として現れるシステムについて記載する。その結果、曲線における、検出がない低区分(low segment)である「最小値」もある。図２は、第１極大値３０、極小値、および第２極大値３４の概念を示す。これは、タッチパッド上における２つの物体の検出の結果である。
【発明の概要】
【発明が解決しようとする課題】
【００１２】
二次元データ集合から多数の指の動きを検出および追跡するために使用することができ、最大値および最小値を識別することには頼らない、新たな検出および追跡方法を提供できれば、従来技術に対する利点となるであろう。
【課題を解決するための手段】
【００１３】
第１実施形態では、本発明は、オーバーサンプリング山登り(hill climbing)および山下り(descent)法を範囲と併せて使用して、結果の二次元集合において多数の指を検出および追跡する方法である。
【００１４】
本発明のこれらのおよびその他の目的、特徴、利点、および代わりの態様は、添付図面と組み合わせて以下の詳細な説明を検討することによって、当業者には明白になるであろう。
【図面の簡単な説明】
【００１５】
【図１】図１は、先行技術において見られ、本発明における使用のために改造可能なタッチパッドの第１実施形態の動作のブロック図である。
【図２】図２は、検出された物体毎に最大値と、介在する最小値とを識別しなければならないことを示す、先行技術からのグラフである。
【図３】図３は、タッチ・センサからのデータの図であり、１本の指が存在するが、先行技術は１本または２本の指として示す。
【図４】図４は、タッチ・センサと、多くの位置からの６つだけの位置の図であり、６つの位置は、稜線によって表される物体の位置を示す。
【図５】図５は、タッチ・センサと、物体を検出することができる１組の異なる位置の図である。
【図６】図６は、タッチ・センサと、物体を検出することができる１組の異なる位置の図である。
【図７】図７は、結果を示す位置、および物体の最大値として識別される位置の図である。
【発明を実施するための形態】
【００１６】
これより、本発明の種々のエレメントに番号の指定(numeral designation)が与えられた図面を参照して、当業者が本発明を行い使用することを可能にするように、本発明について説明する。尚、以下の記載は、本発明の原理の説明に過ぎず、後に続く特許請求の範囲を狭めるように解釈してはならないことは言うまでない。
【００１７】
図２に示す先行技術は、多数の指を発見するために、センサ結果を１つの次元で走査して最大値、それに続く最小値、それに続く他の最大値を見つけて、第１の指、指の間の空間、次いで第２の指を識別する。これらの指は前記第１および第２最大値に対応する。しかしながら、タッチ・センサからのデータを一次元として扱うのは不適当であり、状況によっては多数の指を正しく識別し損なうおそれがあることがわかった。
【００１８】
最初に、先行技術は、タッチ・センサ上における指の一定の位置(certain position)に対して多数の指を識別し損なうおそれがある。最大値および最小値は、一定の軌道にのみ存在することができ、他では存在することができないので、使用される軌道以外の軌道にしか現れない最大値および／または最小値を有する指は発見されない。言い換えると、予め定められた走査軌道（即ち、離散位置における測定の断面）も、タッチ・センサ上において全ての指を正しく識別する１組の軌道（水平方向、垂直方向、または対角線方向の走査等）もない。
【００１９】
第２に、直交軸(cross axis)結果の合算は、他の方法では失われる最大値および最小値を「取り込む」試みにおいて使用することもできるが、これは指が隠される原因になるおそれがある。したがって、２本の指の結果が合算されて同じ結果になる場合、これらの指は事実上見えないおそれがある。２本の指があり直交方向に合算されると、どの結果が直交軸を横切る方向に対応するのか見分けることができないので、２本の指は２つの位置のいずれにもなる可能性がある。これはゴースティング(ghosting)として知られる状況であり、直交タッチ・センサによってはその性質のために、１本の指が２箇所に同時に現れることがあり得る。その結果、実際にゴースト位置にある第３および第４の指は、先行技術の検出方法を使用すると、完全に検出不能になるおそれがある。
【００２０】
第３に、二次元データが離散的に取り込まれるときには、基本的な「エイリアシング」問題があり、これは通常のサンプリング要件を超える。例えば、サンプル周波数は、測定において存在するばらつきを取り込むためには十分に高くなければならないことは周知である。一次元の測定では、一旦サンプル・レートが十分高くなれば、一次元走査で全ての最大値および最小値を正しく観察することができる。しかしながら、２次元にわたって測定のばらつきが存在し、データが離散的に取り込まれるとき、エイリアシングされる極大値および極小値は内因性となる。極大値および極小値は、１つの物体からの信号の強度のばらつきとして定めることができる。何故なら、１つの物体が様々な位置に広がるからである。
【００２１】
図３は、１本の指の先行技術の映像(view)の表現として示す。しかしながら、先行技術は、測定がどのように区分されるかに応じて、この指を任意に１本または２本の指として見る。データの水平方向に区分すると、１つの最大値、したがって１本の指を検出する可能性が高く、垂直方向の区分も同様である。しかしながら、対角線方向の区分は、十中八九、２つの最大値したがって２本の指を誤って識別するであろう。この結果は、変動するドットのサイズまたは変動する高さの表面として示すことができ、サイズまたは高さは指の存在による容量変化の大きさを表す。
【００２２】
例えば、図４に示すような、６つの位置からのサンプルのアレイについて検討する。これらの位置における測定値は、指先よりも多くと接触している親指または指（図３に示すように）の側面の表面として見えるかもしれず、おおまかに直線状であり、タッチ・センサ５０の左下（１ａ）から右上（３ｂ）に移動している。親指または指（以後指と呼ぶ）の形状は、稜線４０によって表すことができ、左上３ａから右下１ｂに移動するとき、信号強度において別個の低地-頂点-低地(lowland-peak-lowland)を有するように見ることもできる。指の実際の最大値は、これらの位置におけるこの１組の測定値の外側にある可能性がある。重要なのは、１ａおよび３ｂが稜線４０の直下にあるように、稜線４０が、識別された位置を通過することである。
【００２３】
位置２ａおよび２ｂは、稜線４０のいずれかの側にある。つまり、１ａおよび３ｂは、第１指位置の別個の最大値と関連付けられる。尚、サンプル粒度を低下させても（即ち、二次元サンプル・レートを高める）、この問題から逃れられないことを注記しておく。任意の固定サンプリング軌道（垂直方向、水平方向、対角線方向、または何らかの他の軌道）に対して、稜線が交互にこれらの位置を貫通するおよびこれらの位置の間を通過するように親指の位置が存在し、これによってタッチ・センサ５０上にエイリアスされた最大値および最小値(aliased maxima and minima)が生ずる。
【００２４】
これらの問題全てを識別することによって、本発明の第１実施形態は、一次元データを使用せず、代わりに二次元データのみを使用することによって、これらの問題を解決することができる。言い換えると、本発明は、タッチ・センサ上において多数の物体の位置を発見するために、単純な一次元データを使用しない。
【００２５】
第１実施形態の第１ステップは、タッチ・センサ５０を形成する直交タッチ・センサ格子によって定められる位置の二次元アレイ全体を走査することである。完全な走査の目的は、第１の指の存在を示すことができるように、０よりも大きな測定結果または信号強度（以後結果と呼ぶ）を有する全ての位置を識別することであってもよい。指を有する可能性があると識別された位置が、第１指位置として識別されればよいのは、１本よりも多い指が存在する可能性があるからである。
【００２６】
この位置を認定する(qualify)ためには、オーバーサンプリングすることが望ましいであろう。例えば、この位置をチェックして、この位置の周囲にあり、多数の位置を覆う少なくとも１本の指が実際に存在することを示す結果があることを確認することができる。この位置は、ステップ２の開始点として使用される。この位置は、現在の第１指位置として識別することができる。
【００２７】
第２ステップは、現在の第１指位置から山登り手順を実行することである。山登り手順とは、少なくとも１本の指の最も高い位置まで内側に移動することと説明することができる(referred to as)。言い換えると、このアルゴリズムは、現在の第１指位置に隣接し、現在の第１指位置の値よりも大きな値を有する位置があるか否か判定することを試みる。
【００２８】
既に述べた理由のために、最も高い値を有する第１指位置のみを捜すアルゴリズムは、結果を全ての二次元の周囲の結果と比較することによってでも、適当ではない。山登りアルゴリズムは、エイリアシングによって生じる極小値を飛ばさなければならない。例えば、図４から、位置１ａおよび３ｂにおいて極大値があり得る。どれが最大の極大値であるか判定するために、これらの間に極小値（信号強度における窪み）がある。極小値を迂回する能力は、例えば、近直交軸結果(near cross axis results)の加重和を比較することによって、達成することができる。           
【００２９】
近直交軸結果の加重和を比較する一例として、山登りアルゴリズムが、図５に示すような現在の第１指位置として、位置２ｂに登ったと想定する。山登りアルゴリズムは、ここで位置３ｂにおける値を検討しようとすると仮定する。
【００３０】
近直交軸結果の加重和は、次のように実行することができる。加重パターンが、隣接する直交軸値を乗算および合算することによって、適用される。この例では、山登りアルゴリズムは、１−２−１パターンを使用する。すると、方程式は、(1 * 3a + 2 * 3b + 1 * 3c)となる。つまり、 (1 * 3a + 2 * 3b + 1 * 3c > 1 * 2a + 2 * 2b + 1 * 2c)であると、３ｂは内側であると見なすことができ、あるいはより高い信号強度またはより高い結果を有し、したがって、山登りアルゴリズムは、位置３ｂに登ることができる。
【００３１】
位置３ｂに移動する前に、山登りアルゴリズムは、同じ加重平均比較を使用して、（少なくとも）位置２ａ、１ｂ、および２ｃの直接隣接値(immediately adjacent values)も検討することができる。したがって、(1 * 1 a + 2 * 2a + 1 * 3a > 1 * 1 b + 2 * 2b + 1 * 3b)である場合、２ａもより高い値を有し、内側であると考えられる。この特定の加重パターン１−２−１は、サンプル対典型的な指形状に基づく特定の実施態様には該当するとして選択することができる。他の関係については、他の加重パターン、例えば、１  ２  ４  ２  １、または二次元加重パターン、例えば、
0 1 1 1 0
1 2 4 2 1
---------
1 2 4 2 1
0 1 1 1 0
でも適すると考えられる。
【００３２】
２ｂを２ａ、３ｂ、２ｃ、および１ｂの値と比較することを選択することは、４-関連比較(4-connected comparison)と言えば分かるであろう。何故なら、中央値２ｂが４つの最も近い位置と比較されるからである。しかしながら、対角線値を含む山登りアルゴリズムは、二次元サンプリングを含む８-関連比較と見なすこともできる。したがって、Ｎ-関連比較は、現在の第１指位置に近い所望の配列におけるＮ箇所の位置の比較を行う。
【００３３】
尚、エイリアシングを低減するために二次元結果アレイをフィルタリングする（例えば、ロー・パス平均化）と、このエイリアシング問題に役立てることができるが、潜在的な上り方向毎に別個のフィルタ・データ・アレイ(filtered data array)が作られる場合にのみ有効であると考えられることを注記しておく。これは、山登りの潜在的な方向において行われるフィルタリングが、計算においてデータをぼかすからである。このアルゴリズムの主要な利点は、直交軸方向にだけ平均するので、山登り比較を明確にすることである。
【００３４】
ディジタル信号処理用語では、この分析は単純なウェーブレット変換であると考えられる。追加のウェーブレット分析から、更に他の代案を得ることができる。尚、山登りアルゴリズムは、指の最大値を識別する必要はなく、多くの場合識別しないことを注記しておく。
【００３５】
以下の例は、山登り手順が最大値を発見し損なうことがあり得る１つのシナリオを示す。図６は、少なくとも１６の位置、１ａから４ｄを有するタッチ・センサ５０を示す。
指の実際の位置が、矢印４４によって示されるように、以上の位置のほぼ中心にあると考える。したがって、第１位置集合を形成する位置２ｂ、２ｃ、３ｂ、および３ｃからの信号強度または結果は、ほぼ等しい。同様に、１ｂ、１ｃ、２ｄ、３ｄ、２ａ、３ａ、３ｂ、および４ｃもほぼ等しいが、第１位置集合よりも小さい。１ｂ＞１ｃ、３ａ＞２ａ、４ｃ＞４ｂ、および２ｄ＞３ｄであり、これらの不等式が比較を支配するのに十分であるとき、アルゴリズムは、時計回り方向に２ｃ-＞２ｂ-＞３ｂ-＞３ｃ-＞２ｃと上り、無限に繰り返すことができる。この条件に達した場合、山登りアルゴリズムを終了し、現在の第１指位置をこれらの位置のいずれに割り当てるのにも十分である。
【００３６】
山登りアルゴリズムの無限ループを終了させるには、例えば、山登りに許される最大ステップ数を制限する、または現在の測定サイクルにおいてある位置が既に占められたことを検出することによって、行うことができる。例えば、現在の測定サイクルは、位置を繰り返すことだけでなく、現在の第１指位置をＮ回移動させることによって制限されてもよい。いずれの場合でも、現在の第１指位置は、必ずしも最大値でなくてもよい。
【００３７】
また、山登りアルゴリズムがある閾値レベルにおいて実際の指位置４４の周囲における境界を辿り、この境界内における結果が、未だ知られていないあるレベルよりも上になることを観察してもよい。これは、このアルゴリズムの次のステップにおいて重要である。
【００３８】
尚、山登りアルゴリズムの山登り経路は、予め決定されるのではなく、ジグザグ、任意の曲がり角、および螺旋状でさえも含んでもよいことを注記しておく。経路長の１つの理論的限度は、サンプルの総数、即ち、２ｄアレイ全体としてもよい（これらの全てを通る種々の可能な経路がある）。実際には、一旦いくつかの内側ステップが完了すると、内側方向の範囲は大幅に限定されるので、経路は通例指の直径よりも遙かに短くなる。このようにアルゴリズムを制限すると、更に内側に向かう機会が得られて終了する結果になる可能性があるが、指の中心に近いことは一般にステップ３を開始するには適当であるので、これは通例問題にならない。
【００３９】
第１実施形態の第３ステップは、山下りアルゴリズムを実行して、位置からの結果を指の一部として取り込むことである。このステップは、最大値があるステップ２と同様に、結果にエイリアスされる偽りの最小値が生じ易いと考えられる。したがって、実際の最小値を検索することは、容認できない場合もある。
【００４０】
山下りアルゴリズムの目的は、タッチ・センサ５０上に他の指があるか否か判定することである。第１指位置の最大値の位置が判定された場合、山下りアルゴリズムの全ての繰り返しは、タッチ・センサ上には他の指の他の最大値はないことを示すことができる。何故なら、全ての後続の計算は、全ての結果が第１の指からであり、他の指からではないことを示すからである。これが示されるのは、範囲が事実上０に減少するまで、他の位置の結果が、徐々に減少する範囲に入るからである。
【００４１】
しかしながら、他の指が存在する場合、山下りアルゴリズムは、最終的に、他の指の方向における位置に対して結果が増大していくことを示す。これらの他の位置は、最終的に、他の１本または複数本の指まで山登りアルゴリズムを実行するために、第１実施形態のアルゴリズムを繰り返すためのシード(seed)になる。
【００４２】
この問題に対する１つの解決手段は、第１の指の一部であると想定されるある範囲の結果を許容することでもよい。言い換えると、第１の指の最大値を考える。この最大値は、７０００という測定結果を有するのでもよい。この値は、任意に選択され、例示の目的のために過ぎない。
【００４３】
ここで、第１の指の値に、ある範囲が追加される。この範囲は、結果が稜線とどのように並ぶかによる結果のばらつきを許容する程度には大きくなければならないが、既に突き止められた第１の指ではない近隣の指の中央エリアからの結果を取り込むのを回避する程度に小さくなければならない。
【００４４】
言い換えると、実際の事象として、隣接する位置の結果が減少していく場合、これらが特定のレートで減少することは、予め判断することができる。次いで、これはその範囲に織り込まれ、隣接位置におけるノイズも考慮して、この範囲は、隣接位置を第１の指の一部として含める程に十分大きくなる。つまり、この範囲の値が２０００（この場合も、この値は、この例のために任意に選択されたに過ぎない）に選択された場合、第１の指と隣接位置との和は、９０００未満であると仮定する。９０００という予想値を超える値のジャンプがある場合、隣接位置が近隣の指の一部である可能性がある。
【００４５】
合理的に適度なサンプルおよび感度を有するタッチ・センサでは、それが動作する範囲を選択できることは周知である。この範囲は、特定のタッチ・センサ上において多数の指を使用して経験が得られるに伴い、試行錯誤によって選択することができる。理解しなければいけないのは、第１実施形態を解釈する上で、この範囲が分かることにしているということである。
【００４６】
他の要因は、山下りアルゴリズムが、方向に関係なく、それが降りたことを覚えている必要があることであると考えられる。最初に含むのに相応しい位置からの結果は、範囲が広いときには、 隣接するときにのみ含まれる。
【００４７】
後に、第１の指の最大値から降りた低い位置からの結果が含まれた後、山を登るサンプルを、隣接性とは無関係に、除外する必要がある場合がある。何故なら、これらはいずれかの他の指の中にあることが既に計算されているからである。
【００４８】
アルゴリズムが、偽りの最小値を飛ばしながら、正しく降りることを確認するために、山からの反復する複雑な下方軌道を使用することができる。これらの下方軌道は、移動距離と下降量との間の関係を追跡することを含んでもよい。予想された範囲よりも上にある結果を除外するこの単純な方法は、このような情報の蓄積が不要であることを意味する。
【００４９】
一例として、ステップ２において発見された位置によって、山下りアルゴリズムを初期化し、その位置における値に余裕を加えたものに、前述の範囲を設定することができる。例えば、この範囲に含まれる全ての８−接続周囲サンプル(surrounding sample)を含めてもよい。尚、現在の第１指位置が偶然最大値である場合、全ての隣接サンプルの方が低いので、この繰り返しの間加算は行われないが、第１指位置が最大値でない場合もあるので、必ずしも該当しない場合もあることを注記しておく。局所的なばらつきを許容するようにこの範囲は調節されるので、このステップは、通例、第１指位置よりも大きな隣接サンプルを取り込まない。
【００５０】
一旦この範囲の現在値において隣接するサンプルがなくなったなら、この範囲を狭めるかまたは下に移動し、本プロセスを繰り返す。この範囲を増大させる量は、主に実際上の留意点である。理想的には、隣接位置からの結果を取り込むのに十分なだけ縮小するのであろうが、これは計算的に負荷が大きくなるおそれがあるので、段階的な手法が適当であろうと考えられる。言い換えると、この範囲は、当該範囲の何らかの端数である固定量だけ、縮小されるとよい。このプロセスは、この範囲が十分に０に近くなり、それ以上の結果が無関係になるまで継続する。
【００５１】
尚、この山下りアルゴリズムのステップは、通例、前述の範囲を使用して、隣接する結果の比較によって、隣接する指との境界を識別し、これはローカルに行われることを注記しておく。山下りが完了した後でないと、結果がステップ４において残るか否か調べるために結果を評価できない。この残った結果は、他の指である可能性があり、第１実施形態を使用して次に突き止めなければならない。
【００５２】
最後に、ステップ４は、ステップ３において識別された第１の指に含まれる結果を除外しながら、ステップ１において行われたことを繰り返す。これは、許容範囲よりも上にあるが、指として認定する程に十分な残りの結果によって取り囲まれていないために、ステップ３の間に取り込まれなかったいずれの位置も、潜在的な指として除外する機会となる。尚、このような位置が存在する場合、これらは極大値である可能性が高いが、本アルゴリズムは、これらを潜在的な別個の指として失格にするだけの十分な情報を既に提供したことを注記しておく。実際に、これらは、既に発見されている指の実際の最大値を含むこともあり得る。
【００５３】
逆に、潜在的な指が残っている場合、認定された位置は、現在の第１の指としてシードされ(seed)（これが第２のまたはその後の指であっても）、本アルゴリズムは、第１実施形態のステップ２から開始して、繰り返される。
【００５４】
図７は、本発明の第１実施形態のステップを適用した後における、図３において示した結果内において識別された１本の指の図である。
第１実施形態の山登りアルゴリズムの部分は、１本の指の位置のみを識別しようとする場合、１本しか指がない場合、または特定の指による結果をグループ化するために異なる方法が使用される場合には、山下りアルゴリズムなしで使用してもよい。一旦現在の第１指位置のような開始位置が識別されたなら、山下りアルゴリズムを開始することができる。
【００５５】
第１実施形態は、山下りアルゴリズムと共に使用される山登りアルゴリズムを示すが、開始位置を識別する方法に関係なく、山下りアルゴリズムを使用してもよい。
山登りアルゴリズムおよび山下りアルゴリズムの繰り返しは、存在する指の本数、および発見する必要がある指の本数、ならびに指（１本または複数）についての形状および／またはサイズ情報も望まれるか否かによって、異なる。
【００５６】
尚、以上で説明した構成は、本発明の原理の応用を例示するに過ぎないことは理解されてしかるべきである。本発明の主旨や範囲から逸脱することなく、数多くの変更および代替構成も、当業者によって考案することができる。添付する特許請求の範囲は、このような変更および構成にも当てはまることを意図している。
【図１】
2016503215.tif 000003
【図２】
2016503215.tif 000004
【図３】
2016503215.tif 000005
【図４】
2016503215.tif 000006
【図５】
2016503215.tif 000007
【図６】
2016503215.tif 000008
【図７】
2016503215.tif 000009
【国際調査報告】
2016503215.tif 000010