(57)【要約】  受信装置は、複数の音波信号源からの音波信号（例えば、超音波）を捕捉し、対応する音波信号源に対する受信装置の当初位置を決定するのに使用される信頼性条件を満足する音波信号を選択し、選択された音波信号のマルチラテレーションを用いて受信装置の当初位置を決定し、且つ、動的に変化する環境干渉、マルチパシング、及び受信装置と音波信号源との間の移動の存在下で個々の音波信号の信頼性が変化するときに受信装置の現在位置を更新する。
2014531597.tif 000002
【特許請求の範囲】
【請求項１】
第１の位置にある受信装置により、音波信号源のセットの各音波信号源から音波信号を受信するステップであり、各音波信号源から発信される前記音波信号は、別の音波信号源から発信される前記音波信号とは異なり、各音波信号源は、前記音波信号内で提供される情報に基づいて、前記セット内で一意に識別可能である、ステップと、
前記音波信号源のサブセットから受信された音波信号を選択するステップであり、選択される音波信号は、反射した音波信号を除外する信頼性条件を満足し、選択された音波信号を提供した各音波信号源の位置は前記受信装置に既知である、ステップと、
差分到着時間測定値と相互相関とを用いて、前記音波信号源の前記サブセットの前記既知の位置に対する前記受信装置の前記第１の位置を決定するステップと、
前記サブセットより少数の音波信号源から受信された音波信号に基づいて前記受信装置の第２の位置を決定するステップであり、前記第１の位置と、当該第２の位置で受信された前記音波信号の非差分の到着時間測定値とに基づいて、当該第２の位置を決定するステップと、
を有する方法。
【請求項２】
前記第２の位置を決定する処理は、
前記第１の位置と前記サブセット内の前記音波信号源の各々の位置との間で計算された距離に基づいて、捕捉された各音波信号のタイミング基準を決定すること
を有する、請求項１に記載の方法。
【請求項３】
前記第２の位置を決定する処理は、
前記受信装置の進行方向を決定することと、
前記第２の位置を決定するために、前記第１の位置及び前記非差分の到着時間測定値を前記進行方向に対して評価することと
を有する、請求項１に記載の方法。
【請求項４】
前記進行方向を決定する処理は、前記受信装置の、複数の以前に決定された位置を評価することを有し、前記以前に決定された位置は、音波ベースの位置特定に基づいて決定されている、請求項３に記載の方法。
【請求項５】
前記進行方向を決定する処理は、前記受信装置の、複数の以前に決定された位置を評価することを有し、前記以前に決定された位置は、音波ベースの位置特定に基づいて決定されている、請求項３に記載の方法。
【請求項６】
前記第２の位置を決定する処理は、
前記受信装置の進行速度を決定することと、
前記第２の位置を決定するために、前記第１の位置及び前記非差分の到着時間測定値を前記進行速度に対して評価することと
を有する、請求項１に記載の方法。
【請求項７】
前記進行速度を決定する処理は、
前記第１の位置で受信された音波信号の周波数におけるドップラーシフトを決定して、前記受信装置の前記進行速度を決定すること
を有する、請求項６に記載の方法。
【請求項８】
前記受信装置はモバイル装置であり、前記音波信号源は静止している、請求項１に記載の方法。
【請求項９】
第１の位置で、音波信号源のセットの各音波信号源からの音波信号を捕捉する、ように構成された受信装置の記録部であり、各音波信号源から発信される前記音波信号は、別の音波信号源から発信される前記音波信号とは異なり、各音波信号源は、前記音波信号内で提供される情報に基づいて、前記セット内で一意に識別可能である、記録部と、
前記音波信号源のサブセットから受信された音波信号を選択する、ように構成された前記受信装置の信号源プロセッサであり、選択される音波信号は、反射した音波信号を除外する信頼性条件を満足し、選択された音波信号を提供した各音波信号源の位置は前記受信装置に既知である、信号源プロセッサと、
差分到着時間測定値と相互相関とを用いて、前記音波信号源の前記サブセットの前記既知の位置に対する前記受信装置の前記第１の位置を決定する、ように構成された前記受信装置の音波ロケータと、
を有するシステム。
【請求項１０】
電子装置上でプロセッサ実行可能プロセスを実行するためのプロセッサ実行可能命令をエンコードした１つ以上のプロセッサ読み取り可能記憶媒体であり、前記プロセスは、
第１の位置にある受信装置により、音波信号源のセットの各音波信号源から音波信号を受信するステップであり、各音波信号源から発信される前記音波信号は、別の音波信号源から発信される前記音波信号とは異なり、各音波信号源は、前記音波信号内で提供される情報に基づいて、前記セット内で一意に識別可能である、ステップと、
前記音波信号源のサブセットから受信された音波信号を選択するステップであり、選択される音波信号は、反射した音波信号を除外する信頼性条件を満足し、選択された音波信号を提供した各音波信号源の位置は前記受信装置に既知である、ステップと、
差分到着時間測定値と相互相関とを用いて、前記音波信号源の前記サブセットの前記既知の位置に対する前記受信装置の前記第１の位置を決定するステップと、
を有する、プロセッサ読み取り可能記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、音波に基づく位置特定（ポジショニング）に関する。
【背景技術】
【０００２】
屋内環境内のユーザ又はモバイル（移動式）装置の位置を正確に決定することは、様々な難題を呈する。例えば、グローバルポジショニングシステム（ＧＰＳ）衛星とのモバイル装置の通信が周囲の構造物によって妨げられてしまい得る包囲された建物内では、ＧＰＳ技術がうまく機能しない。また、市販の消費者装置は、その通信能力、センシング能力（例えば、モバイル装置マイク）、その内部クロックの精度、利用可能な電力などにおいて限界がある。従って、包囲された建物内（又は、別の理由でＧＰＳ位置特定が利用可能でないところ）のモバイルユーザについて、高度に正確でリアルタイムの位置情報を取得することは、市販のモバイル装置のハードウェアへの重大な変更なくしては困難である。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
音波に基づく位置特定方法及びシステムを提供する。
【課題を解決するための手段】
【０００４】
ここに記載される実施形態及び請求項に記載される実施形態は、受信装置を使用して、複数の音波信号源からの音波信号（例えば、超音波）を捕捉し、対応する音波信号源に対する受信装置の当初位置を決定するのに使用される信頼性条件を満足する音波信号を選択し、選択された音波信号のマルチラテレーションを用いて受信装置の当初位置を決定し、且つ、動的に変化する環境干渉、マルチパシング、及び受信装置と音波信号源との間の移動の存在下で個々の音波信号の信頼性が変化するときに受信装置の現在位置を更新する、ことによって上述の問題を解決する。
【０００５】
この概要は、以下の詳細な説明に更に記載される複数の概念の一部を簡略化した形態で紹介するために提示されるものである。この概要は、請求項に係る事項の主要な特徴や本質的な特徴を特定することを意図したものではないし、請求項に係る事項の範囲を限定するために使用されることを意図したものでもない。
【０００６】
他の実施形態もここに記載される。
【図面の簡単な説明】
【０００７】
【図１】音波ベースの位置特定を使用する状況の一例を示す図である。
【図２】音波ベースの位置特定を使用する状況の他の一例を示す図である。
【図３】音波ベースの位置特定のデータフロー図の一例を示す図である。
【図４】音波ベースの位置特定の処理の例を示す図である。
【図５】差分到着時間と非差分の到着時間とを用いる音波ベースの位置特定の処理の例を示す図である。
【図６】記載の技術を使用するのに有用であり得るシステムの他の一例を示す図である。
【発明を実施するための形態】
【０００８】
例えばスマートフォンなどの一部の最近のモバイル装置は、超音波信号を検出することが可能なマイクを含んでおり、これはコンシューマグレードのモバイル装置が超音波ベースの位置特定を実行する好機を示すものである。そのような装置によって検出可能な超音波帯域幅は、今現在はかなり狭いものである（例えば、２０ｋＨｚと２２ｋＨｚとの間）。とはいうものの、この限られた帯域幅内で超音波信号を再生して、超音波信号源に対する受信装置の位置を決定することを可能にするのに十分な情報を提供することができる。
【０００９】
一実装例は、例えば、所与のエリア全体に分散された音波信号源（例えば、スピーカ）を含む。複数の音波信号源から発せられた音波信号が、１つ以上の受信装置（例えば、超音波信号を正確に捕捉することが可能なマイクを有するモバイル装置）によって受信され、該１つ以上の受信装置が、受信した音波信号を用いて所与のエリア内での位置を決定する。受信装置は、受信した音波信号から、マルチラテレーションを用いて、当初位置を決定することができる。マルチラテレーションとは、既知の位置を有する複数の音波信号源から送信された信号の到着時間の差（time  difference  of  arrival；ＴＤＯＡ）を正確に計算することに基づいて受信装置の位置を決定するプロセスである。このように、マルチラテレーションを用いて、多数の音波信号源に対する受信装置の位置を決定することができる。その後、受信装置の上記当初位置を所与として、複数の音波信号の各々に関する時間基準を取得することができ、故に、特には（例えば、信号源と受信装置との間の変化する障害及び干渉により）信頼できる音波信号の数が減少するときに、非差分の到着時間（time  of  arrival；ＴＯＡ）測定を用いて受信装置の位置を更新し続けることができる。
【００１０】
概して、マルチラテレーションの一実装例は、既知の位置にある複数の音波信号源からの音波信号を受信する受信装置を含む。各音波信号の到着時間の差（これは、既知の送信タイムスロットに基づいて正規化され得る）を用いて、受信装置と各音波信号源との間の距離の差が決定される。２つの音波信号源を用いて、受信装置を双曲面上で位置特定することができる。３つの音波信号源を用いて、受信装置を第２の双曲面上で位置特定することができ、これら２つの双曲面の交差部が、その上に受信装置が位置する曲線を描く。４つめの音波信号源を追加することにより、受信装置を第３の双曲面上で位置特定することができ、これら３つの双曲面の交差部が３次元空間における一意的な点を定める。
【００１１】
しかしながら、理解されるように、音波信号の到着時間の測定における誤差が、位置計算の精度を低下させ得る（例えば、受信音波信号に基づいて計算される双曲面が空間内の正確な点で交差することは稀である）。従って、計算される位置特定結果の精度を向上させるために、更なる音波信号源及び／又は最適化技術（例えば、最小二乗法又は拡張カルマンフィルタ）が適用され得る。
【００１２】
図１は、音波ベースの位置特定を使用する一状況例１００を示している。買い物客１０２（ユーザの一例）が、位置特定アプリケーションを実行する携帯電話を担持しながら、店舗１０４（環境の一例）内を移動する。買い物客１０２の体は、店舗１０４の北東を向いている。複数の音波信号源（例えば、スピーカ１０６）が店舗１０４のあちこちに位置付けられ、各音波信号源がそれ自身のタイムスロット内で（例えば、ラウンドロビン（総当たり）的に）音波信号を発する。各音波信号は、それが受信装置によって捕捉されるのに十分な強さであるとすると、受信装置（例えば、携帯電話）のオーディオ入力（例えば、マイク）によって受信されることができる。例えば、スピーカ１１０によって発せられた超音波信号は受信装置によって受信されるが、スピーカ１１６によって発せられる音波信号は、受信装置からのスピーカの距離のために、受信装置によって捕捉されるのに十分な強さではない。また、一部の音波信号は受信装置によって直接受信されない。例えば、買い物客１０２の体が、スピーカ１１４と受信装置との間の直接的な音波信号経路を遮っている。とはいうものの、受信装置は、例えば店舗の棚、天井及び床などの周囲の構造物から反射したスピーカ１１４からの音波信号を受信することがある。反射した信号は、音波信号経路に沿った追加の距離を導入するものであり、故に、（何らかの種類の正規化なしでは）正確な到着時間の測定を提供しない。一実装例において、受信装置は、反射音波信号を位置特定計算から除外するために、直接的な音波信号と反射した音波信号とを判別するが、他の実装例は、一定種類の反射を考慮するように使用されてもよい。例えば、一実装例において、音波信号源と反射表面との間、及び受信装置と反射表面との間の幾何学的な関係を用いて、音波信号源と受信装置との間の反射経路に沿った物理的な距離、ひいては、音波信号源と受信装置との間に直接物理距離を計算し得る。
【００１３】
他の一実装例において、音波ベース位置特定システムは、反射信号又は直接信号の何れであろうと、多数の捕捉された音波信号によって指し示される複数の可能な交差（位置）の組（セット）を計算することができる。一部の状況において、複数の捕捉信号によって可能とされた位置セットは、最も正確な位置特定に使用されるべき最も信頼できる信号源を提言する他の制約によって狭められることができる。
【００１４】
図１に示されるように、買い物客１０２によって担持される受信装置上で実行される音波ベース位置特定アプリケーションは、スピーカ１０６、１０８、１１０及び１１２から直接音波信号を受信する。受信装置が例えばスピーカ１１８及び１２０などの他のスピーカから直接音波信号を受信することも可能であり、それは、位置特定計算の精度及び／又は信頼性を向上させ得る。とはいうものの、４つの信頼できる直接音波信号を受信することにより、受信装置は、差分到着時間（differential  time  of  arrival；ＤＴＯＡ）測定及びマルチラテレーションを用いて、その他の情報なしで、３次元空間内での信号源に対する自身の位置を計算することができる。他の例では、受信装置は、３つの信頼できる直接音声源に基づいて、その他の情報なしで、２次元空間内での信号源に対する自身の位置を計算することができる。例えば位置的な制約（すなわち、買い物客１０２は棚の上や店舗１０４の外側には位置し得ない）又は位置的な近似（例えば、買い物客１０２は通路の中央に位置していると仮定される）などの追加情報の存在下では、位置特定計算の信頼性及び精度を高めることができ、且つ／或いは（以前に使用されていた音波信号源のサブセット（部分集合）が使用されるように）位置特定計算に必要な信号源の数を削減することができる。
【００１５】
ＤＴＯＡ測定及びマルチラテレーションを用いて買い物客１０２の当初位置が決定されると、音波ベース位置特定アプリケーションは、各音波信号のタイミング基準を計算することができる（例えば、音波信号源と受信装置との間の知られた距離に基づいて、対応する音波信号源が送信及び／又は送信停止した時間を計算することができる）。これらの基準を所与として、音波ベース位置特定アプリケーションは、非差分ＴＯＡ測定に切り換わり、マルチラテレーション段階で使用される音波信号源より少ない音波信号源を用いて正確な位置特定を可能にすることができる。従って、買い物客１０２が店舗を動き回るとき、一部の以前の直接音波信号は、その買い物客の体、他の買い物客、棚、看板などによって遮られることになる。とはいうものの、音波ベース位置特定アプリケーションは、環境全体で様々な音波信号源から音波信号を捕捉し続けることができ、信頼できる音波信号の数が変化するときであっても、買い物客の位置を正確に決定することができる。
【００１６】
図２は、店舗２０４のあちこちに分散された複数の信号源（例えば、スピーカ２０６）に対して買い物客２０２が異なる位置及び向きにある、音波ベースの位置特定を使用する他の一状況例２００を示している。各信号源が、受信装置（例えば、携帯電話）のオーディオ入力（例えば、マイク）によって受信されることが可能な音波信号を発する。図１に示した状況１００と同様に、状況２００においても信号強度が、何れの音波信号が受信装置によって捕捉されるかに影響を及ぼし得る。さらに、一部の音波信号は受信装置によって直接受信されない。例えば、図１とは異なり、買い物客２０２の体は、店舗２０４の南東を向いている。従って、買い物客の体が、受信装置とスピーカ２０６及び２０８との間の直接的な音波信号経路を遮っている。とはいうものの、受信装置は、例えば店舗内の棚、天井及び床などの周囲の構造物から反射した音波信号を受信することがある。故に、受信装置は、反射音波信号を位置特定計算から除外するために、直接的な音波信号と反射した音波信号とを判別し、あるいは、音波信号源と反射表面と受信装置との間の知られた幾何学的な関係に基づいて、信号が進行した距離を正しく考慮に入れる。
【００１７】
図２に示されるように、買い物客２０２によって担持される受信装置は、スピーカ２１０、２１２、２１４及び２１６から、それらの割り当てタイムスロット内で直接音波信号を受信する。受信装置が例えばスピーカ２１８及び２２０などの他のスピーカから直接音波信号を受信することも可能であり、それは、位置特定計算の精度及び／又は信頼性を向上させ得る。
【００１８】
図１及び２に関して示されるように、所与のエリアにわたる受信装置の移動は、受信装置が位置特定計算の基礎とすることができる信号源をリアルタイムに変更させ得る。また、環境内での反射音波信号の存在は、位置特定計算での使用に適した信頼できる信号源の選択を更に複雑にする。従って、受信装置及び／又はそれが頼る位置特定システムは、環境内の信用できない音波信号を除外し、それらの信号源を位置特定計算から排除する。
【００１９】
図３は、音波ベースの位置特定のデータフロー図の一例３００を示している。例えば携帯電話などの受信装置は、オペレーティング３０２を実行することで、そのリソースを管理するとともに、音波ベース位置特定アプリケーションがその上で実行されることが可能なプラットフォームを提供する。例えば、一実装例において、モバイル装置が、例えばマイク３０３及び１つ以上のスピーカ（図示せず）などの当該モバイル装置のオーディオリソースを管理するオーディオインタフェースを備えたオペレーティングシステムを実行するとともに、或るエリア（例えば、店舗、倉庫、製造現場、オフィスビルなど）のあちこちに位置付けられた複数の音波信号源に関して音波信号を受信することが可能なモバイル位置特定アプリケーションを実行する。理解されるように、記載の技術は、包囲する構造物によって標準的なＧＰＳ信号が遮られてしまう屋内での使用に好適であるが、記載の技術は、屋外エリアで使用されてもよいし、ＧＰＳ技術及びＷｉ−Ｆｉ技術と組み合わされて使用されてもよい。
【００２０】
音波ベース位置特定アプリケーションが実行中であるとき、例えばプロセッサ実行可能なソフトウェア手段などの記録部（レコーダ）３０４が、マイク３０３によって捕捉された音波信号３０５の記録及びデジタル化を行う。記録部３０４は、デジタル化した音波信号をレコーダプロセスキュー（待ち行列）３０６に格納し、このとき、記録された音波信号は、高速フーリエ変換（ＦＦＴ）処理をストリーム化するために複数の音波信号ブロックに分割される。一実装例においてブロックサイズは２０４８オーディオサンプル長さ程度であるが、他のブロックサイズが使用されてもよい。
【００２１】
レコーダプロセスキュー３０６は、非同期処理のためにレコーダプロセスキュー３０６から取り出された音波信号ブロックを処理するワーカースレッド３０８を生成する。ワーカースレッド３０８は、ワーカースレッド３０８によって処理された各音波信号ブロックを処理するものであるピーク発見部３１０を実行する。ピーク発見部３１０は、相互相関管理部３１２及び相互相関部３１４を使用して各音波信号ブロックと既知の送信信号との相互相関をとることで、相関性ある出力における強いピークを特定する。相互相関は、２つの波形間の類似度の指標を表す。例えば、一実装例は、それらの波形の一方を遅延させて、それらの波形を掛け合わせる。他の相関結果と比較したときに、特定の形状を有し且つ所定の閾値（例えば、信頼性条件）を上回る相関ピークを発見することにより、位置特定システムは、反射（例えば、音速で検出可能な、より長い経路を生じさせる）によって過度に遅延された信号を除外する。相互相関管理部３１２は、相互相関部３１４に対する維持管理機能を提供し、相互相関部３１４は、相互相関演算を実行し、且つ処理された（例えば、相互相関付けされた）音波信号（例えば、相関ピーク）のキューとして相互相関データ３１６を出力する。
【００２２】
相互相関データ３１６は信号源プロセッサ３１８によって処理され、信号源プロセッサ３１８が、受信された音波信号の発信源（ソース）である音波信号源（例えば、スピーカ）と該音波信号源の位置とを特定する。信号源プロセッサ３１８のソース発見部３２０が、各相関ピークの識別番号を決定し、それにより相関ピークを既知の信号源と関連付ける。一実装例において、信号源は信号源グループに結び付けられる（例えば、１つの信号源グループに８個と１６個との間のスピーカ）。グループ識別子３２２により、特定された信号源がメンバーとなっている信号源グループが特定される。位置記録部３２４が、発見された信号源識別子を、対応する音波信号のオーディオタイミングと関連付ける（例えば、音波信号ブロックの開始に対する、音波信号が開始した時）。
【００２３】
マルチラテレーションプロセッサ３２６が、特定された信号源の組（セット）及びそれらそれぞれのタイミング、既知の信号源位置の組、並びに何らかの幾何学的な制約（例えば、店舗内の通路）を受信し、そして、マルチラテレーション演算を用いてこのデータから受信装置の位置を推定する。呼び出し手段３２８が音波ロケータ３３０を非同期的に呼び出す。音波ロケータ３３０は、ユーザ位置及び相対的なＸ／Ｙ／Ｚ座標を、ユーザインタフェース３３２（これは、例えば、フロアプランマップ（見取り図）及びユーザ位置をディスプレイ上に表示することができる）を介したユーザへの提示のためのアプリケーション見取り図の座標系に変換するものである。
【００２４】
環境の規模（例えば、信号源の個数、同時に対応される受信装置の個数、及びその他の環境要因）に応じて多様な信号源特定方式が使用され得るが、ここに開示される以外の他の方式も考えられる。例えば、小規模環境（例えば、８−１６個の信号源）においては、個々の信号源を識別するためにトーン（発信音）を使用することができる。一実装例において、各信号源は、局所的に唯一無二のトーンであり且つ２０．１ｋＨｚから２１．６ｋＨｚまで１００Ｈｚ間隔で離隔された一組のトーンによって識別される。一例において、各信号源は、チャープとトーンとを含む波形を発し、例えば：
波形（ｉ）＝チャープ＋トーン（ｉ）
となるようにする。ここで、ｉは信号源識別子を表し、チャープは２０４８オーディオサンプル長を有し、且つ２０ｋＨｚから２１．６ｋＨｚまで線形に増大する周波数（“アップチャープ”の例）によって変調され、トーンは、２０．１＋ｉ×０．１ｋＨｚなる局所的に唯一無二の周波数を有する正弦波形を表す。代替的に、線形に低減する周波数を用いる“ダウンチャープ”が使用されてもよい。その他の規模に関して記載されるように、その他の波形が使用されてもよい。
【００２５】
例えば、中規模環境（例えば、１６−６４個の信号源）において、他の手法も使用され得るが、以下では３つの手法を説明する。１つの手法において、個々の信号源を識別するために１６個のトーンが使用される。信号源は、２つの信号源グループに分割されて最大３２個の信号源まで拡張され、例えば：
波形（ｉ，ｊ）＝チャープ（ｊ）＋トーン（ｉ）
となるようにする。ここで、ｊはグループ識別子を表し（ｊ＝０では２０ｋＨｚから２１．６ｋＨｚまでのアップチャープ、ｊ＝１では２１．６ｋＨｚから２０．０ｋＨｚまでのダウンチャープ）、チャープ間の相互相関が閾値＜０．２（信頼性条件）に基づいて決定され、チャープ長は２０４８オーディオサンプル長であり、ｉは信号源識別子を表し、トーンは、２０．１＋ｉ×０．１ｋＨｚなる局所的に唯一無二の周波数を有する正弦波形を表す。
【００２６】
中規模環境に関する別の一手法において、信号源を識別するためにやはり１６個のトーンが使用される。信号源は、４つの信号源グループに分割されて最大６４個の信号源まで拡張され、例えば：
波形（ｉ，ｊ）＝チャープ（ｊ）＋トーン（ｉ）
となるようにする。ここで、ｊはグループ識別子を表し（ｊ＝０では２０ｋＨｚから２０．８ｋＨｚまでのアップチャープ、ｊ＝１では２０．８ｋＨｚから２１．６ｋＨｚまでのアップチャープ、ｊ＝３では２１．６ｋＨｚから２０．８ｋＨｚまでのダウンチャープ、ｊ＝４では２０．８ｋＨｚから２０．０ｋＨｚまでのダウンチャープ）、チャープ間の相互相関が閾値＜０．３（信頼性条件）に基づいて決定され、チャープ長は２０４８オーディオサンプル長であり、ｉは信号源識別子を表し、トーンは、２０．１＋ｉ×０．１ｋＨｚなる局所的に唯一無二の周波数を有する正弦波形を表す。
【００２７】
中規模環境に関する第３の手法において、やはり、使用帯域幅を２つの周波数範囲（例えば、双方ともに１００Ｈｚ間隔で、２０ｋＨｚから２０．８ｋＨｚと２０．８ｋＨｚから２１．６ｋＨｚ）に分割することで、６４個の信号源まで拡張される。１つのトーンが、８個の信号源のうちの１つを指し示すように第１の周波数範囲内でエンコードされ、別の１つのトーンが、８個のグループのうちの１つを指し示すように第２の周波数範囲内でエンコードされ、例えば：
波形（ｉ，ｊ）＝チャープ＋トーン（ｉ）＋トーン（ｊ）
となるようにする。ここで、ｊはグループ識別子を表し、ｉは信号源識別子を表し、トーン（ｉ）は、周波数２０．１＋ｉ×０．１ｋＨｚの正弦波信号であり、トーン（ｊ）は、周波数２０．９＋ｊ×０．１ｋＨｚの正弦波信号であり、チャープ間の相互相関が閾値＜０．３（信頼性条件）に基づいて決定され、チャープ長は２０４８オーディオサンプル長である。
【００２８】
例えば、大規模環境（例えば、６４−２５６個の信号源）について、他の手法も使用され得るが、以下では３つの手法を説明する。１つの手法において、１６個の信号源識別子をエンコードするために、各波形が或る周波数範囲（例えば、２０．０ｋＨｚ−２１．６ｋＨｚ）にわたる１６個の疑似雑音コード化（pseudo-noise  coded；ＰＮＣ）波形が使用される。さらに、１６個のグループ識別子をエンコードするために、或る周波数範囲（例えば、２０．０ｋＨｚ−２１．６ｋＨｚ）にわたって分布される１６個のトーンが使用され、例えば：
波形（ｉ，ｊ）＝ＰＮＣ（ｉ）＋トーン（ｊ）
となるようにする。ここで、ｊはグループ識別子を表し、ｉは信号源識別子を表し、トーン（ｊ）は、周波数２０．１＋ｊ×０．１ｋＨｚの正弦波信号であり、ＰＮＣ波形間の相互相関は〜０．２−０．４の閾値に基づき、ＰＮＣ波形長は２０４８オーディオサンプルである。
【００２９】
大規模環境に関する別の一手法において、使用帯域幅が２つの周波数範囲（例えば、中心周波数（ｆｃ）を１９．７ｋＨｚに有する１９．０ｋＨｚから２０．４ｋＨｚと、中心周波数（ｆｃ）を２１．１ｋＨｚに有する２０．４ｋＨｚから２１．８ｋＨｚ）に分割される。第１の帯域において、１６個のグループ識別子をエンコードするために１６個のＰＮＣ波形が使用される。第２の帯域において、１６個のグループ識別子をエンコードするために、１６個のＰＮＣ波形が使用され、例えば：
波形（ｉ，ｊ）＝ＰＮＣ（ｉ，ｆｃ＝１９．７ｋＨｚ）＋ＰＮＣ（ｊ，ｆｃ＝２１．１ｋＨｚ）
となるようにする。ここで、ｊはグループ識別子を表し、ｉは信号源識別子を表し、ＰＮＣ波形間の相互相関は〜０．２−０．４の閾値に基づき、ＰＮＣ波形長は２０４８オーディオサンプルである。
【００３０】
大規模環境に関する更なる別の一手法において、やはり使用帯域幅を２つの周波数範囲（例えば、双方ともに１００Ｈｚ間隔で、２０ｋＨｚから２０．８ｋＨｚと２０．８ｋＨｚから２１．６ｋＨｚ）に分割することで、２５６個の信号源まで拡張される。１つのトーンが、８個の信号源のうちの１つを指し示すように第１の周波数範囲内でエンコードされ、別の１つのトーンが、８個のグループのうちの１つを指し示すように第２の周波数範囲内でエンコードされる。さらに、信号源が４つのスーパーグループに分割され、例えば：
波形（ｉ，ｊ，ｋ）＝チャープ（ｋ）＋トーン（ｉ）＋トーン（ｊ）
となるようにする。ここで、ｋはスーパーグループ識別子を表し（ｋ＝０では２０ｋＨｚから２０．８ｋＨｚまでのアップチャープ、ｋ＝１では２０．８ｋＨｚから２１．６ｋＨｚまでのアップチャープ、ｋ＝３では２１．６ｋＨｚから２０．８ｋＨｚまでのダウンチャープ、ｋ＝４では２０．８ｋＨｚから２０．０ｋＨｚまでのダウンチャープ）、チャープ間の相互相関が閾値＜０．３（信頼性条件）に基づいて決定され、チャープ長は２０４８オーディオサンプルであり、ｉは信号源識別子を表し、トーン（ｉ）は、２０．１＋ｉ×０．１ｋＨｚなる局所的に唯一無二の周波数を有する正弦波形を表し、ｊはグループ識別子を表し、トーン（ｊ）は、２０．９＋ｊ×０．１ｋＨｚなる局所的に唯一無二の周波数を有する正弦波形を表す。
【００３１】
巨大規模環境（例えば、２５６−１０２４個の信号源）では、１６個の信号源識別子をエンコードするために、各波形が或る周波数範囲（例えば、２０．０ｋＨｚ−２１．６ｋＨｚ）にわたる１６個の疑似雑音コード化（pseudo-noise  coded；ＰＮＣ）波形が使用される。さらに、１６個のグループ識別子をエンコードするために、或る周波数範囲（例えば、２０．０ｋＨｚ−２１．６ｋＨｚ）にわたって分布される１６個のトーンが使用され、例えば：
波形（ｉ，ｊ，ｋ）＝ＰＮＣ（ｉ）＋トーン（ｊ）＋トーン（ｋ）
となるようにする。ここで、ｋはスーパーグループ識別子を表し、ｊはグループ識別子を表し、ｉは信号源識別子を表し、トーン（ｊ）は、周波数２０．１＋ｊ×０．１ｋＨｚの正弦波信号であり、トーン（ｋ）は、周波数２０．９＋ｋ×０．１ｋＨｚの正弦波信号である。
【００３２】
サポートされる環境の範囲を拡張するための他の選択肢は、所与のエリア内の各音波信号源に唯一無二の識別子を指定することを含む。各音波信号源はそのグループ識別子を発し、その後、個々の信号源は、そのグループの信号源とラウンドロビンシーケンスにて自身の信号源識別子を発する。例えば、１階の信号源が２階の信号源とは異なるグループに属する２階建ての建物を考える。従って、最初のグループ識別子信号は、その受信装置が位置する階を指し示し、その後の一連の信号源識別子は、その信号源からの信号が捕捉されているその階の信号源を指し示す。斯くして、指し示されるグループ識別子によって区別される異なる階の間で、信号源識別子を共有することができる。
【００３３】
これら又はその他のエンコーディング方式を使用することで、多様な検出方法を用いて信号源を識別することができる。一手法において、総当たり法により、捕捉された音波信号の、Ｎ個の波形の各々との全面的な相互相関が取得され、最大の相関ピークを有する波形が選択される。他の一手法において、１６００Ｈｚの帯域幅内に波形が維持され、スペクトルドメインにおける約１５０個の周波数瓶（例えば、部分範囲）が提供される。相互相関付けを実行することには２５６ポイントの高速フーリエ変換（ＦＦＴ）で十分であり得る。ＦＦＴ相互相関付けから最大の相関ピークを有する波形を特定した後、特定された波形の基準関数との全長さでの相互相関付けが実行され、それにより、受信された音波信号に基づいて音波信号源が特定され得る。
【００３４】
トーンが組み込まれた波形の場合、ドップラー抽出を用いて、受信装置及び／又は該受信装置を保持しているユーザの進行方法及び／又は進行速度を決定することができる。一実装例において、ドップラー抽出は、組み込まれたトーンの周波数位置と比較した、周波数ドメイン内でのトーンの位置のシフトを測定することを含む。
【００３５】
疑似雑音コード（ＰＮＣ）波形を伴う他の一実装例においては、ＰＮＣ波形のスペクトルを１つ又は複数の周波数瓶だけシフトさせ、記録された音波信号のスペクトルと掛け合わせ、短い長さ（例えば、２５６）の逆高速フーリエ変換（ＩＦＦＴ）を実行し、そして、得られた相互相関信号のピークに注目することによって、ドップラーシフトを繰り返し決定することができる。相互相関ピークを最大にする周波数瓶シフトの値が、記録された音波信号におけるドップラーシフトを表す。
【００３６】
複数のＰＮＣ波形を伴う更なる他の一実装例においては、ＰＮＣ波形識別子及び瓶シフトという２つの次元にて手順が反復される。相互相関ピークを最大にするＰＮＣ波形識別子と瓶シフトとの対が、音波信号源によって送信されたＰＮＣ波形と、記録された音波信号におけるドップラーシフトとの双方を生じさせる。
【００３７】
その他のドップラー抽出技術も使用され得る。上述のように、ドップラーシフトを、漸進的な位置特定と組み合わせて使用することで、受信装置（及び／又はユーザ）の進行方向及び／又は進行速度を決定し、ユーザの移動に関する制約を設定することができる。従って、ドップラー抽出は、その後に音波信号が検出される時点での受信装置が取り得る位置の予測を可能にする。このような位置の予測は、制約として使用されることができる。このような制約を用いることで、位置特定精度を高め、且つ／或いは位置を正確に決定するために必要な信頼できる音波信号の数を削減することができる。
【００３８】
図４は、音波ベースの位置特定の処理の例４００を示している。受信処理４０２が、例えば店舗などの環境を特定するとともに、信号源の位置、それらの識別子、それらのグループ識別子、及びその他の環境制約（例えば、受信装置が現実的に位置することができる所）を含んだ、その環境のマップを受信する。一実装例において、受信処理４０２は、音波ベース位置特定アプリケーションが受信装置上で始動されるときに実行される。他の一実装例において、受信処理４０２は、（例えば、最新にわかったＧＰＳ位置に基づいて、認識されたＷｉ−ＦｉルータのＭＡＣアドレスに基づいて、ユーザ入力に基づいて）受信装置が既知の環境に入ったことを検出し、受信装置自身の記憶装置から、あるいは外部のデータ源（例えば、Ｗｉ−Ｆｉ接続されたサービス）からマップを取り出す。
【００３９】
捕捉処理４０４が、識別可能な信号源に関連付けられた音波信号を捕捉する。各信号源は、例えば上述の小規模、中規模、大規模及び巨大規模の環境に関して説明したものなどのシグナリングプロトコルに従って、それ自身のタイムスロットにて音波信号を発する。受信された信号が処理され、信号源が特定されるとともに、その信頼性が評価される。例えば、環境内でサポートされる波形の各々との、捕捉された信号の相互相関を用いて、捕捉処理４０４は、最大の相関ピークを生み出す波形を選択して、この捕捉音波信号の音波信号源を特定することができる。
【００４０】
判定処理４０６が、この捕捉音波信号が信頼できるもの（例えば、正確にデコードされるのに十分な強度の直接的な音波信号）であるかを決定する。そうでない場合、この捕捉信号は無視され、捕捉処理４０４にて新たな音波信号が捕捉される。それ以外の場合、決定処理４０８が、相互相関結果を用いて、捕捉タイムスタンプ及び関連付けられた音波信号源の識別子を決定する。
【００４１】
更なる判定処理４１０が、十分な数の新しい信頼できる音波信号が捕捉されたかを決定する。捕捉された音波信号に対して、１つ以上の要素を有する信頼性条件が適用される。例えば、１つの要素は、捕捉音波信号が直接的なものであるのか、反射したものであるのか評価することを支援するよう、音波信号波形の形状を考慮し得る。直接音波信号は、反射した音波信号とは異なる特徴を有する傾向にある。そのような特徴は、相互相関付けやドップラー抽出などを非限定的に含む様々な技術を用いて区別されることができる。また、この要素は、音波信号の各サイクル内で同じタイムスロット中に捕捉された音波信号を評価し得る。同一タイムスロット中に捕捉された複数の音波信号は互いに十分に相互相関せず、そして、該タイムスロットにて捕捉された音波信号のうちの１つ以上は反射したものであるので信頼できないという決定が為され得る。更なる他の一要素は、マルチラテレーションが単一の点又はそれの非常に近くに収束するかを考慮し得る。マルチラテレーション解法における発散は、成分音波信号のうちの１つが直接的なものでなく、故に信頼できないものであることを指し示し得る。信頼性条件には他の要素も採用され得る。
【００４２】
他の一観点において、最初の音波信号と最後の音波信号との間の追跡時間が所定の閾値（例えば、秒単位）より大きい場合、音波信号は“古い”又は“十分に新しくない”と見なされてもよい。例えば、様々な音波信号源からタイムスロットシーケンスで音波信号が受信されるとき、マルチラテレーションを行うのに十分な数の信頼できる音波信号を収集することは、多数のタイムスロットの期間（例えば、最初の信頼できる音波信号と最後の信頼できる音波信号との間に、受信装置が無視できない距離だけ移動しているのに十分な期間）にわたって行われることがあり得る。従って、受信装置がこの“追跡”時間中に過度に遠くまで移動する場合、位置計算の精度が損なわれ得る。一実装例において、判定処理４１０は、音波信号ブロックが古い（例えば、正確な位置計算に寄与することができないほど古い）が故に信頼できないものであるかを決定する。古い音波信号ブロックは無視され得る。
【００４３】
また、音波信号が古いかについての決定は、多様なファクタ（例えば、ささいでない位置変化を生じさせる移動を指し示すドップラーシフトをユーザが追跡時間中に示したかどうか、直接的な信号源及び遮られた信号源の特定が変化したかどうか、買い物客の移動に関する経験則、等々）によって知らされ得る。例えば、反射した音波信号のドップラーシフト測定に基づき、ユーザが有意な速度を示していない場合、追跡時間中に直接的な信号源及び遮られた信号源が不変のままである場合、及び／又は、追跡時間が追跡閾値を超えないとして、買い物客の位置が許容可能な程度に正確であることが統計的にわかっている場合、音波信号は十分に“新しい”と見なされ得る。
【００４４】
さらに、ＤＴＯＡに基づいて位置を正確に計算するのに必要な新しい信頼できる音波信号の数を削減するために、環境制約も適用され得る。例えば、３つの新しい信頼できる音波信号が捕捉される場合（３次元マルチラテレーションが典型的に４つの信頼できる音波信号を要求するときに）、受信装置は所定の高さ範囲内にあることが想定されるという仮定が為すことで、２次元での位置特定で十分とすることができ、４つめの新しくて信頼できる音波信号は必要とされない。同様に、買い物客が許容可能な公差内で通路の中央にいると仮定される場合、正確な位置特定に必要な新しくて信頼できる音波信号の数が削減され得る。他の環境制約も同様に、必要な新しくて信頼できる音波信号の数を削減させ、且つ／或いは、音波ベース位置特定の結果の精度及び信頼性を向上させ得る。
【００４５】
新しい信頼できる音波信号の必要数を削減させるために採用され得る更なる他の環境制約は、或る期間にわたる一連の位置結果に関する。受信装置がその最近の位置（及び場合により、その速度）のリストを維持管理する場合、その進行方向（及び／又は速度）は位置計算同士の間に所定量より大きくは変化していないと仮定し得る。例えば、直前の幾つかのサイクルにおいて受信装置が毎時１マイルで北に移動していることを指し示す幾つかの位置結果を受信装置が有する場合、受信装置の次の位置が先行する位置結果からの先行範囲の外側にあることを防止する制約が仮定され得る。
【００４６】
更なる他の環境制約は、ユーザが達成可能な最高速度又は環境（例えば、店舗）内での平然としたユーザの典型的な最高速度の何れかを仮定した、所与の期間内にユーザがどれだけ遠くに進み得るかという知識とし得る。進む距離は、例えば棚を飛び越えるのではなくユーザ通路に沿ってなどの、実際の物理的環境内を歩く上での制約を更に考慮に入れてもよい。
【００４７】
位置特定処理４１２が、受信装置によって捕捉された新しい信頼できる音波信号、捕捉された信号のＤＴＯＡ、受信したマップ、並びに音波信号源の位置及び識別子に基づいて、マルチラテレーションを用いて、既知の位置にある音波信号源に対する受信装置の位置を決定する。提示処理４１４が、計算された位置を指し示すものを、ユーザインタフェース上のマップ内に提示する。
【００４８】
図５は、差分到着時間と非差分の到着時間とを用いる音波ベース位置特定の処理の例５００を示している。決定処理５０２が、図４に関して説明したのと同様のプロセスにて、ｘ個の音波信号源からの差分到着時間を用いて受信装置の当初位置を決定する。タイミング処理５０４が、上記当初位置と、捕捉された信頼できる音波信号を発している音波信号源の各々と上記当初位置との間の距離と、に基づいて、時間基準を決定する。これらの距離を所与として、各音波信号の伝送時間を計算し、それにより各音波信号に関するタイミング基準生成することができる。
【００４９】
判定処理５０６が、非差分の到着時間による位置特定に十分な数の新しい信頼できる音波信号が捕捉されているかを決定する。この処理において、各音波信号のタイミング基準が非差分ＴＯＡ測定を実行することを可能にし、それにより、発信している音波信号源に対する受信装置の位置を正確に決定するのに必要な信頼できる音波信号の数が削減される。更なる決定処理５０８が、非差分ＴＯＡ測定とタイミング基準とに基づいて、その後の位置を決定する。更なる判定処理５１０が、後続サイクルにおいて補足された新しい信頼できる音波信号の数を再検査して、非差分到着時間による位置特定が依然として正確に計算され得るかを決定し、そうである場合、プロセスは決定処理５０８へと進む。そうでない場合、ＤＴＯＡを用いて新たな位置を決定するために、プロセスは決定処理５０２へと進む。
【００５０】
図６は、記載の技術を実装するのに有用であり得る他の一例に係るシステム（モバイル装置６００としてラベルを付している）を示している。モバイル装置６００は、プロセッサ６０２、メモリ６０４、ディスプレイ６０６（例えば、タッチスクリーンディスプレイ）、及びその他のインタフェース６０８（例えば、キーボード）を含んでいる。メモリ６０４は概して、揮発性メモリ（例えば、ＲＡＭ）及び不揮発性メモリ（例えば、フラッシュメモリ）の双方を含む。例えばＭｉｃｒｏｓｏｆｔ  Ｗｉｎｄｏｗｓ（登録商標）Ｐｈｏｎｅ７オペレーティングシステムなどのオペレーティングシステム６１０が、メモリ６０４内に常駐し、プロセッサ６０２によって実行される。しかしながら、理解されるように、他のオペレーティングシステムが使用されてもよい。
【００５１】
１つ以上のアプリケーションプログラム６１２が、メモリ６０４にロードされて、プロセッサ６０２によってオペレーティングシステム６１０上で実行される。アプリケーション６１２の例は、非限定的に、電子メールプログラム、スケジューリングプログラム、個人情報マネジャ、インターネット閲覧プログラム、マルチメディアプレーヤプログラムなどを含む。通知マネジャ６１４もメモリ６０４にロードされ且つプロセッサ６０２によって実行されて、通知をユーザに提示する。例えば、販売促進がトリガーされて買い物客に提示されるとき、通知マネジャ６１４がモバイル装置６００をして、ビープ音を鳴らさせ、あるいは（バイブレーション装置６１８を介して）振動させ、且つディスプレイ６０６上に宣伝を表示させる。
【００５２】
モバイル装置６００は電源６１６を含んでいる。電源６１６は、１つ以上の電池又はその他の電源によって給電されて、モバイル装置６００の他のコンポーネントに電力を供給する。電源６１６はまた、内臓電池又はその他の電源にとって代わるかそれらを再充電するかする外部電源に接続されてもよい。
【００５３】
モバイル装置６００は、ネットワーク接続（例えば、携帯電話ネットワーク、Ｗｉ−Ｆｉ（登録商標）、Ｂｌｕｅｔｏｏｔｈ（登録商標）など）を提供するよう、１つ以上の通信トランシーバ６３０を含んでいる。モバイル装置６００はまた、例えば、位置特定システム６２０（例えば、グローバルポジショニング衛星トランシーバ）、１つ以上の加速度計６２２、１つ以上のカメラ６２４、オーディオインタフェース６２６（例えば、マイク、オーディオアンプ、スピーカ及び／又はオーディオジャック）、及び更なるストレージ６２８など、様々なその他コンポーネントを含んでいる。他の構成も使用され得る。
【００５４】
一実装例において、音波ベース位置特定アプリケーション、ピーク発見部、相互相関管理部、相互相関部、ワーカースレッド、音波ロケータ、ユーザインタフェース、マルチラテレーションプロセッサ、並びにその他のモジュール及びサービスは、メモリ６０４及び／又はストレージ装置６２８に格納された命令によって具現化されて、処理ユニット６０２によって処理され得る。音波信号ブロック、位置、見取り図、それぞれのタイミング、及びその他のデータは、永続的なデータ保管としてメモリ６０４及び／又はストレージ装置６２８に格納され得る。理解されるように、ストレージ装置は、ローカル（例えば、フラッシュメモリ又は磁気記憶装置）であってもよいし、リモート（例えば、例えばＤＶＤ、ＣＤ又は磁気記憶装置などのネットワーク接続記憶装置を介する）であってもよい。
【００５５】
一部の実施形態は製品を有し得る。製品は、ロジックを記憶する記憶媒体を有し得る。記憶媒体の例は、揮発性メモリ若しくは不揮発性メモリ、脱着可能メモリ若しくは非脱着可能メモリ、消去可能メモリ若しくは非消去可能メモリ、書換可能メモリ若しくは追記可能メモリなどを含め、電子データを格納することが可能な一種類以上のコンピュータ読み取り可能記憶媒体を含み得る。ロジックの例は、例えば、ソフトウェアコンポーネント、プログラム、アプリケーション、コンピュータプログラム、アプリケーションプログラム、システムプログラム、マシンプログラム、オペレーティングシステムソフトウェア、ミドルウェア、ファームウェア、ソフトウェアモジュール、ルーチン、サブルーチン、関数、メソッド、プロシージャ、ソフトウェアインタフェース、アプリケーションプログラムインタフェース（ＡＰＩ）、命令セット、コンピューティングコード、コンピュータコード、コードセグメント、コンピュータコードセグメント、ワード、値、シンボル、又はこれらの組み合わせなど、様々なソフトウェア要素を含み得る。一実施形態において、例えば、製品は、コンピュータによって実行されるときに、記載の実施形態に従った方法及び／又は処理を該コンピュータに実行させる実行可能コンピュータプログラム命令を格納し得る。この実行可能コンピュータプログラム命令は、例えば、ソースコード、コンパイル済みコード、インタープリット済みコード、実行可能コード、静的コード、動的コード、及びこれらに類するものなど、如何なる好適種類のコードを含んでいてもよい。この実行可能コンピュータプログラム命令は、特定の機能の実行をコンピュータに命令するように、予め定められたコンピュータ言語、様式又は構文に従って実装され得る。これらの命令は、如何なる好適な高水準プログラミング言語、低水準プログラミング言語、オブジェクト指向プログラミング言語、ビジュアルプログラミング言語、コンパイル済みプログラミング言語、及び／又はインタープリット済みプログラミング言語を用いて実装されてもよい。
【００５６】
ここに記載の本発明の実施形態は、１つ以上のコンピュータシステムにおいて論理ステップとして実装される。本発明に係る論理演算は、（１）１つ以上のコンピュータシステムで実行されるプロセッサ実行ステップとして、そして、（２）１つ以上のコンピュータシステム内の相互接続マシン若しくは回路モジュールとして実装され得る。この実装は、本発明を実行するコンピュータシステムの性能要求に応じた選択事項である。従って、ここに記載の本発明の実施形態を構成する論理演算は、処理、ステップ、オブジェクト、又はモジュールとして、様々に参照される。また、理解されるように、論理演算は、明示的に特段に断っていたりクレームの言葉によって特定の順序が生来的に必要とされたりしない限り、如何なる順序で実行されてもよい。
【００５７】
以上の明細、例及びデータは、本発明の例示的な実施形態の構成及び使用法の完全なる説明を提供するものである。本発明の精神及び範囲を逸脱することなく本発明の数多くの実施形態を作り出すことができるのであり、故に、本発明は、以下に添付される請求項に属する。また、様々な実施形態の構成的特徴は、記載される請求項を逸脱することなく、更なる他の実施形態と組み合わされ得る。
【図１】
2014531597.tif 000003
【図２】
2014531597.tif 000004
【図３】
2014531597.tif 000005
【図４】
2014531597.tif 000006
【図５】
2014531597.tif 000007
【図６】
2014531597.tif 000008
【国際調査報告】
2014531597.tif 000009
2014531597.tif 000010