(57)【要約】  環境内のモバイル電子デバイスの位置特定を提供するためのシステムおよび方法が、そのモバイル電子デバイスと通信状態にある少なくとも１つのサーバを含む。その少なくとも１つのサーバは、そのモバイル電子デバイスから少なくとも１つのピクチャおよび少なくとも１つの加速度計測定を受信するように構成される。その少なくとも１つのサーバは、その少なくとも１つのピクチャ、その少なくとも１つの加速度計測定、およびその環境の少なくとも１つの３次元マップに基づいて、そのモバイル電子デバイスに位置特定を提供する位置特定モジュールを含む。
2016524128.tif 000002
【特許請求の範囲】
【請求項１】
環境内のモバイル電子デバイスの位置特定を提供するためのシステムであって、
前記モバイル電子デバイスと通信状態にある少なくとも１つのサーバであって、前記モバイル電子デバイスから少なくとも１つのピクチャおよび少なくとも１つの加速度計測定からの入力データを受信するように構成されたサーバと、
前記少なくとも１つのサーバと通信状態にあるメモリ・データベースであって、前記環境の少なくとも１つの３次元マップを記憶するメモリ・データベースと、
前記少なくとも１つのサーバによって実行されるように構成された位置特定モジュールであって、前記少なくとも１つのピクチャからの前記入力データ、前記少なくとも１つの加速度計測定、および前記屋内環境の前記少なくとも１つの３次元マップに基づいて、前記モバイル電子デバイスに位置特定を提供する位置特定モジュールと、
を備える、システム。
【請求項２】
前記３次元マップは、３次元特徴ポイントのデータベースを含む、請求項１に記載のシステム。
【請求項３】
前記位置特定モジュールは、前記少なくとも１つのピクチャからの２次元特徴ポイントを前記３次元マップの前記３次元特徴ポイントと照合することによって位置特定を提供する、請求項２に記載のシステム。
【請求項４】
前記位置特定モジュールは、剛体運動を想定して、一致した特徴ポイント・ペアの間の並進ベクトルおよび回転行列を算出するように構成される、請求項３に記載のシステム。
【請求項５】
前記位置特定モジュールを実行するためのクラウド・コンピューティング・サービスを含む、請求項１に記載のシステム。
【請求項６】
前記少なくとも１つの加速度計測定は、３軸加速度計からの３軸加速度測定を含む、請求項１に記載のシステム。
【請求項７】
前記モバイル電子デバイスは、ウェアラブル・スマート・ガジェットである、請求項１に記載のシステム。
【請求項８】
前記位置特定モジュールは、前記３次元マップの検索空間を、前記少なくとも１つのピクチャおよび前記少なくとも１つの加速度計測定を前記３次元マップと比較するためのサブセットに制限するように構成される、請求項１に記載のシステム。
【請求項９】
前記位置特定モジュールは、前記加速度計測定から前記モバイル電子デバイスのピッチおよびロールを計算することによって前記３次元マップの前記検索空間を制限する、請求項８に記載のシステム。
【請求項１０】
前記位置特定モジュールは、ＷｉＦｉジオロケーション、前記モバイル電子デバイスに入力された２次元バーコードまたは位置特定情報のうちの少なくとも１つを使用して前記環境内の前記モバイル電子デバイスの位置を近似することによって、前記３次元マップの前記検索空間をさらに制限する、請求項９に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、位置特定に関する。
【背景技術】
【０００２】
通常ではＧＰＳ信号が到達することができない屋内環境において、全地球測位システム（ＧＰＳ）などの車両ナビゲーション・システムによって提供される屋外位置特定を再現する屋内位置特定を提供する必要性が高まっている。屋内位置特定を提供するためのアプローチには、ＷｉＦｉ信号測定またはセルラー信号測定が、関心対象の場所のＲＦマップと照合されて、その場所におけるユーザの現在の位置が推定される無線周波数（ＲＦ）フィンガプリンティング（ｆｉｎｇｅｒｐｒｉｎｔｉｎｇ）、および知られていない環境のマップが映像によってインクリメンタルに構築され、見る人の現在の位置および経路がそのプロセスに沿って推測される視覚ベースの同時位置特定／マッピング（Ｓｉｍｕｌｔａｎｅｏｕｓ  Ｌｏｃａｌｉｚａｔｉｏｎ ａｎｄ  Ｍａｐｐｉｎｇ（ＳＬＡＭ））が含まれる。しかし、これらの屋内位置特定システムは、通常、３Ｄ空間における位置特定の精度を欠く、または過度にリソースを多用する計算および／または特化されたハードウェアを要求する。
【発明の概要】
【課題を解決するための手段】
【０００３】
実施形態によれば、環境内のモバイル電子デバイスの位置特定を提供するためのシステムが、そのモバイル電子デバイスと通信状態にある少なくとも１つのサーバを含む。その少なくとも１つのサーバは、そのモバイル電子デバイスから、少なくとも１つのピクチャからの入力データ、および少なくとも１つの加速度計測定を受信するように構成される。その少なくとも１つのサーバは、その少なくとも１つのピクチャからの入力データ、その少なくとも１つの加速度計測定、およびその屋内環境の少なくとも１つの３次元マップに基づいて、そのモバイル電子デバイスに位置特定を提供する位置特定モジュールを含む。
【０００４】
実施形態によれば、その３次元マップは、３次元特徴ポイントのデータベースを含む。
【０００５】
実施形態によれば、その位置特定モジュールは、その少なくとも１つのピクチャからの２次元特徴ポイントを、その３次元マップのそれらの３次元特徴ポイントと照合することによって位置特定を提供する。
【０００６】
実施形態によれば、このシステムは、その位置特定モジュールを実行するためのクラウド・コンピューティング・サービスを含む。
【０００７】
実施形態によれば、その少なくとも１つの加速度計測定は、３軸加速度計からの３軸加速度測定を含む。
【０００８】
実施形態によれば、そのモバイル電子デバイスは、ウェアラブル・スマート・ガジェットである。
【０００９】
実施形態によれば、コンピュータ化された方法は、少なくとも１つのサーバにおいて、モバイル電子デバイスから少なくとも１つのピクチャおよび少なくとも１つの加速度計測定からの入力データを受信することを含む。その少なくとも１つのサーバが、その少なくとも１つのピクチャおよびその少なくとも１つの加速度計測定からの入力データを環境の３次元マップと比較して、その環境内のそのモバイル電子デバイスの３次元位置および向きを示す位置特定をそのモバイル電子デバイスに送信する。
【００１０】
実施形態によれば、この方法は、その少なくとも１つのサーバにおいて、その３次元マップの検索空間を、その少なくとも１つのピクチャおよびその少なくとも１つの加速度計測定をその３次元マップと比較するためのサブセットに制限することをさらに備える。
【００１１】
実施形態によれば、その少なくとも１つのサーバにおいて、その３次元マップの検索空間を制限することは、その加速度計測定からそのモバイル電子デバイスのピッチ（ｐｉｔｃｈ）およびロール（ｒｏｌｌ）を計算することを含む。
【００１２】
実施形態によれば、その少なくとも１つのサーバにおいて、その３次元マップの検索空間を制限することは、ＷｉＦｉジオロケーション（ｇｅｏｌｏｃａｔｉｏｎ）、モバイル電子デバイスに入力された２次元バーコード、または位置特定情報のうちの少なくとも１つを使用して環境内のそのモバイル電子デバイスの位置を近似することをさらに含む。
【００１３】
実施形態によれば、そのモバイル電子デバイスの近似の位置は、そのモバイル電子デバイスの実際の位置から２０メートルの範囲内であり得る。
【００１４】
実施形態によれば、この方法は、その少なくとも１つのサーバにおいて、その少なくとも１つのピクチャからの２次元特徴ポイントを、その３次元マップの３次元特徴ポイントと照合することをさらに備える。
【００１５】
実施形態によれば、この方法は、その少なくとも１つのサーバにおいて、剛体運動を想定して、照合される特徴ポイント・ペアの間で並進ベクトルおよび回転行列を算出することをさらに備える。
【００１６】
実施形態によれば、方法を実行するように少なくとも１つのサーバによって実行されるように構成された命令を記憶する非一時的な有形のコンピュータ可読媒体が、モバイル電子デバイスから少なくとも１つのピクチャおよび少なくとも１つの加速度計測定からの入力データを受信するステップと、その少なくとも１つのピクチャおよびその少なくとも１つの加速度計測定からの入力データを、メモリの中に記憶された環境の３次元マップと比較するステップと、その環境内のそのモバイル電子デバイスの３次元の位置および向きを示す位置特定を、そのモバイル電子デバイスに送信するステップとを備えることが可能である。
【００１７】
実施形態によれば、この方法は、その３次元マップの検索空間を、その少なくとも１つのピクチャおよびその少なくとも１つの加速度計測定をその３次元マップと比較するためのサブセットに制限することをさらに備える。
【００１８】
実施形態によれば、その３次元マップの検索空間を制限することは、その加速度計測定からそのモバイル電子デバイスのピッチおよびロールを計算することを含む。
【００１９】
実施形態によれば、その３次元マップの検索空間を制限することは、ＷｉＦｉジオロケーションを使用してその環境内のそのモバイル電子デバイスの位置を近似することをさらに含む。
【００２０】
実施形態によれば、そのモバイル電子デバイスの近似の位置は、そのモバイル電子デバイスの実際の位置から２０メートルの範囲内であり得る。
【００２１】
実施形態によれば、この方法は、その少なくとも１つのピクチャからの２次元特徴ポイントを、その３次元マップの３次元特徴ポイントと照合することをさらに備え得る。
【００２２】
実施形態によれば、この方法は、剛体運動を想定して、照合される特徴ポイント・ペアの間で並進ベクトルおよび回転行列を算出することをさらに備える。
【００２３】
これら、およびその他の実施形態は、添付の図面を参照しながら、本明細書内の後段の詳細な説明に鑑みて明白となろう。
【図面の簡単な説明】
【００２４】
【図１】実施形態によるシステムを示す概略図である。
【図２】図１のシステムの座標系を示す概略図である。
【図３】クラウド・コンピューティング・サービスを実施する図１のシステムを示す概略図である。
【図４】図１のシステムで屋内位置特定を提供するための実施形態を示す流れ図である。
【図５】図１のシステムで屋内位置特定を提供するための実施形態を示す流れ図である。
【発明を実施するための形態】
【００２５】
様々な実施形態をさらに詳細に説明する前に、本発明は、説明される特定の実施形態に限定されないことを理解されたい。本明細書で説明されるシステムおよび方法は、対象とされる用途に適切なように構成され、変形され得ること、および本明細書で説明されるシステムおよび方法が、他の適切な用途で使用されてもよいこと、および他のそのような追加および変形が本発明の範囲から逸脱しないことが、当業者には理解されよう。
【００２６】
図面において、同様の参照符号は、本出願のシステムおよび方法の同様の特徴を指す。したがって、いくつかの説明は、いくつかの図および参照符号にしか参照しないものの、そのような説明は、他の図における同様の参照符号にも同様に当てはまり得ることを理解されたい。
【００２７】
図１を参照すると、屋内位置特定のためのシステム１０が示されている。システム１０は、屋内環境１６内でユーザ１４によって操作されるように構成されたモバイル電子デバイス１２と、位置特定モジュール１８と、屋内環境１６のあらかじめ構築された屋内３次元（３Ｄ）マップ２０とを含む。
【００２８】
モバイル電子デバイス１２は、カラー・カメラと、３軸加速度計と、少なくとも１つの通信ネットワーク接続（たとえば、モバイル・データ・ネットワーク、ＷｉＦｉワイヤレス・コンピュータ・ネットワークなどに対する接続）とを含む任意の通常のモバイル・デバイスであり得る。たとえば、モバイル電子デバイス１２は、セルラー電話、スマートフォン、タブレット、ＧＯＯＧＬＥ  ＧＬＡＳＳ、あるいは屋内環境１６内でユーザ１４によって装着され、かつ／または携帯され、操作されることが可能な任意の類似したポータブル・デバイスであり得る。
【００２９】
屋内環境１６のあらかじめ構築された３Ｄ屋内マップ２０は、システム１０が屋内位置特定を実行できる前にオフラインで構築されて、関心対象の屋内環境１６の形状をキャプチャする。あらかじめ構築された３Ｄ屋内マップ２０は、後段でより詳細に説明されるとおり、位置特定モジュール１８がアクセス可能なロケーションに記憶される。３Ｄ屋内マップ２０は、屋内環境１６においてサンプリングされた３Ｄ特徴ポイント２１のコレクションまたはデータベースであり得る。あらかじめ構築された３Ｄ屋内マップ２０は、たとえば、ＭＩＣＲＯＳＯＦＴ社によって開発されたＫＩＮＥＣＴ動き感知入力デバイスなどのカラー−デプス（ｃｏｌｏｒ  ａｎｄ  ｄｅｐｔｈ）（ＲＧＢ−Ｄ）カメラを使用して関心対象の特定の建造物の屋内環境１６をマッピングして、構築され得る。ＫＩＮＥＣＴ動き感知入力デバイスは、赤外線（ＩＲ）パターン源と、ＩＲカメラとを有する。ＩＲカメラが、ＩＲパターン源によって投影され、被写体上で反射されるＩＲパターンを検出し、このことにより、オンボード・チップが、立体映像（ｓｔｅｒｅｏｓｃｏｐｙ）を使用してその被写体のデプス・マップを推定することが可能になる。ＲＧＢカメラによってもたらされるこのデプス・マップおよび対応するＲＧＢ画像が、図２に示される屋内マップ座標系（ｘ，ｙ，ｚ）において３Ｄ特徴ポイント２１を定義するのに使用され得る。各３Ｄ特徴ポイント２１は、たとえば、３Ｄ屋内マップ２０における３Ｄ座標と、特徴ポイント照合を可能にするように３Ｄ特徴ポイント２１の周囲の小さな区域の外観を特徴付けるＳｃａｌｅ  Ｉｎｖａｒｉａｎｔ  Ｆｅａｔｕｒｅ  Ｔｒａｎｓｆｏｒｍ（ＳＩＦＴ）記述子（たとえば、１２８次元ベクトル）とを含むことが可能である。３Ｄ屋内マップ２０は、ＲＧＢ−Ｄカメラが屋内環境１６のまわりを移動するにつれ、連続的なＲＧＢ−Ｄ画像からの３Ｄ特徴ポイント２１を反復的に関連付けて、屋内環境１６のあらかじめ構築された３Ｄ屋内マップ２０を、これらの３Ｄ特徴ポイント２１のコレクションまたはデータベースとして定義することによって構築され得る。
【００３０】
位置特定モジュール１８は、サーバ２２上に配置されることが可能であり、モバイル電子デバイス１２と通信して、モバイル電子デバイス１２からの入力を受信し、その入力に応答して電子デバイス１２に位置特定を提供するように構成される。サーバ２２は、当業者には理解されるとおり、図３に示されるように、スタンドアロンのサーバ・ユニットであっても、クラウド・コンピューティング・サービス２４であってもよい。サーバ２２は、必要なエレクトロニクス、ソフトウェア、メモリ、ストレージ、データベース、ファームウェア、論理／状態マシン、マイクロプロセッサ、通信リンク、ならびに本明細書で説明される機能を実行し、かつ／または本明細書で説明される結果を実現する他の任意の入力／出力インターフェースを含む。たとえば、サーバ２２は、プロセッサ２６と、メモリ２８とを含むことが可能であり、メモリ２８は、ランダム・アクセス・メモリ（ＲＡＭ）と、読取り専用メモリ（ＲＯＭ）とを含むシステム・メモリを含み得る。サーバ２２は、当業者には理解されるとおり、後段で説明される屋内位置特定のためのシステム１０の動作を円滑にするように通信インターフェース・ユニット３０を介してモバイル電子デバイス１２および／または他の１つまたは複数のモバイル・デバイスと通信状態にあることが可能である。位置特定モジュール１８に関連して後段で説明される機能を含め、多数の機能を実行するための適切なコンピュータ・プログラム・コードが、サーバ２２に供給され得る。
【００３１】
プロセッサ２６は、１つまたは複数の従来のマイクロプロセッサと、数値演算コプロセッサなどの１つまたは複数の補助的なコプロセッサとを含み得る。プロセッサ２６は、通信インターフェース・ユニット３０と通信状態にあることが可能であり、通信インターフェース・ユニット３０を介してプロセッサ２６は、他のサーバ、他のプロセッサ、コンピュータ、セルラー電話、タブレットなどの他のネットワークおよび／またはデバイスと通信することが可能である。通信インターフェース・ユニット３０は、たとえば、他のモバイル電子デバイス１２、プロセッサ、サーバ、コンピュータ、セルラー電話、タブレットなどと同時に通信するための複数の通信チャネルを含み得る。互いに通信状態にあるデバイスは、互いに絶えず伝送している必要はない。互いに通信状態にあるデバイスは、それらのデバイスの間で通信リンクを確立するのにいくつかのステップが実行されることを要求する可能性がある。
【００３２】
プロセッサ２６は、メモリ２８と通信状態にあり、メモリ２８は、磁気メモリ、光メモリ、および／または半導体メモリの適切な組合せを備えることが可能であり、たとえば、ＲＡＭと、ＲＯＭと、フラッシュ・ドライブと、コンパクト・ディスクおよび／またはハードディスクもしくはハードドライブなどの光ディスクとを含み得る。プロセッサ２６およびメモリ２８はそれぞれ、たとえば、完全に、単一のコンピュータもしくは他のデバイスの内部に配置されること、あるいはＵＳＢポート、シリアル・ポート・ケーブル、同軸ケーブル、イーサネット・タイプのケーブル、電話線、無線周波数トランシーバもしくは他の類似したワイヤレス媒体もしくは有線媒体、または以上の組合せなどの通信媒体によって互いに接続されることが可能である。たとえば、プロセッサ２６は、通信インターフェース・ユニット３０を介してメモリ２８に接続され得る。
【００３３】
メモリ２８は、あらかじめ構築された３Ｄ屋内マップ２０を記憶し、たとえば、位置特定モジュール１８によって要求される１つまたは複数のデータベースおよび／または他の情報、サーバ２２のためのオペレーティング・システム、ならびに／あるいは本明細書で説明される様々な実施形態によりモバイル電子デバイス１２に位置特定を提供するように位置特定モジュール１８を導くように構成された他の１つまたは複数のプログラム（たとえば、コンピュータ・プログラム・コードおよび／またはコンピュータ・プログラム製品）を記憶することも可能である。たとえば、メモリ２８は、後段でさらに詳細に説明されるとおり、屋内環境１６のＷｉＦｉフィンガプリント・マップ（図示せず）を記憶することも可能である。あらかじめ構築された３Ｄ屋内マップ２０、オペレーティング・システム、位置特定モジュール１８、および／または他のプログラムは、たとえば、圧縮されたフォーマット、コンパイルされていないフォーマット、および／または暗号化されたフォーマットで記憶されることが可能であり、プロセッサ２６によって実行可能なコンピュータ・プログラム・コードを含み得る。コンピュータ・プログラム・コードの命令は、メモリ２８、またはメモリ２８以外のコンピュータ可読媒体からプロセッサ２６のメイン・メモリに読み込まれ得る。プログラムの中の命令の系列の実行が、プロセッサ２６に本明細書で説明されるプロセス・ステップを実行させる一方で、本発明のプロセスの実施のために、ソフトウェア命令の代わりに、またはソフトウェア命令と組み合わせて、結線による回路が使用されてもよい。このため、本発明の実施形態は、ハードウェアとソフトウェアのいずれの特定の組合せにも限定されない。
【００３４】
また、本明細書で説明されるプログラムは、フィールド・プログラマブル・ゲート・アレイ、プログラマブル・アレイ・ロジック、プログラマブル論理デバイスなどのプログラマブル・ハードウェア・デバイスとして実装されることも可能である。また、プログラムは、様々なタイプのコンピュータ・プロセッサによって実行されるようにソフトウェアとして実装されることも可能である。実行可能コードのプログラムは、たとえば、コンピュータ命令の１つまたは複数の物理ブロックまたは論理ブロックを備えることが可能であり、これらの物理ブロックまたは論理ブロックは、たとえば、オブジェクト、手続き、プロセス、または関数として編成され得る。それでも、識別されたプログラムの実行ファイルは、物理的に一緒に配置されていなくてもよく、論理的に一緒に結合されると、プログラムを構成して、モバイル電子デバイス１２の屋内位置特定を提供することなどのプログラムのための記載される目的を実現する、異なるロケーションに記憶された別々の命令を備えることも可能である。実施形態において、実行可能コードのアプリケーションは、多くの命令をコンパイルしたものであることが可能であり、異なるいくつかのコード・パーティションまたはコード・セグメントにわたって、異なるプログラムの間で、およびいくつかのデバイスにわたって分散させられることさえ可能である。
【００３５】
本明細書で使用される「コンピュータ可読媒体」という用語は、実行のためにサーバ２２のプロセッサ２６（または本明細書で説明されるデバイスの他の任意のプロセッサ）に命令および／またはデータを供給する、または供給することに加担する任意の媒体を指す。そのような媒体は、不揮発性媒体および揮発性媒体を含むが、以上には限定されない多くの形態をとることが可能である。不揮発性媒体は、たとえば、記憶装置としての、光ディスク、磁気ディスク、または光磁気ディスクを含む。揮発性媒体は、メイン・メモリを通常、構成するダイナミック・ランダム・アクセス・メモリ（ＤＲＡＭ）を含む。コンピュータ可読媒体の一般的な形態には、たとえば、フロッピー・ディスク、フレキシブル・ディスク、ハードディスク、磁気テープ、他の任意の磁気媒体、ＣＤ−ＲＯＭ、ＤＶＤ、他の任意の光媒体、パンチ・カード、紙テープ、穴のパターンを有する他の任意の物理媒体、ＲＡＭ、ＰＲＯＭ、ＥＰＲＯＭもしくはＥＥＰＲＯＭ（電子的に消去可能なプログラマブル読取り専用メモリ）、ＦＬＡＳＨ−ＥＥＰＲＯＭ、他の任意のメモリ・チップもしくはメモリ・カートリッジ、またはコンピュータが読み取ることができる他の任意の媒体が含まれる。
【００３６】
様々な形態のコンピュータ可読媒体が、実行のためにプロセッサ２６（または本明細書で説明されるデバイスの他の任意のプロセッサ）に１つまたは複数の命令の１つまたは複数の系列を伝送することに関与していることが可能である。たとえば、それらの命令が、最初、遠隔コンピュータ（図示せず）の磁気ディスク上に記憶されていることが可能である。その遠隔コンピュータが、それらの命令をその遠隔コンピュータのダイナミック・メモリにロードして、イーサネット接続、ケーブル線、モデムを使用する電話線、ワイヤレスで、または別の適切な接続を介してそれらの命令を送信することが可能である。コンピューティング・デバイスにローカルの通信デバイス（たとえば、サーバ２２）が、それぞれの通信線上でデータを受信して、そのデータを、プロセッサ２６のためのシステム・バスに乗せることが可能である。そのシステム・バスが、そのデータをメイン・メモリに伝送し、そのメイン・メモリからプロセッサ２６が、それらの命令を取り出して、実行する。メイン・メモリによって受け取られる命令は、オプションとして、プロセッサ２６による実行の前に、または後にメモリ２８の中に記憶されてもよい。さらに、命令は、様々なタイプの情報を伝送するワイヤレス通信またはワイヤレス・データ・ストリームの例示的な形態である、電気信号、電磁信号、または光信号として通信ポート経由で受信され得る。
【００３７】
動作の際、屋内位置特定のためのシステム１０は、サーバ２２上で実行されている位置特定モジュール１８が、モバイル電子デバイス１２のカメラによってキャプチャされた２次元（２Ｄ）ピクチャ、およびモバイル電子デバイス１２の３軸加速度計によって行われた加速度測定だけを使用して、モバイル電子デバイス１２の３次元の位置および向きを計算することを可能にする。図２を再び参照すると、カメラによってキャプチャされた２Ｄピクチャ、およびモバイル電子デバイス１２からの加速度測定が、デバイス座標系（ｕ，ｖ，ｓ）に入っている。モバイル・デバイス１２に関する位置特定を算出するのに、位置特定モジュールが、２Ｄピクチャにおける２Ｄ特徴ポイント２１を、図１に示される３Ｄ屋内マップ２０における３Ｄ特徴ポイント２１と照合することを、剛体回転を想定して、照合される特徴ポイント２１の間の並進ベクトル（Ｔｘ，Ｔｙ，Ｔｚ）および回転行列（Ｒｘ（γ），Ｒｙ（β），Ｒｚ（α））を算出することによって行い、ここで、β、γ、およびαは、それぞれ、モバイル電子デバイス１２のピッチ、ロール、およびヨーである。
【００３８】
図４を参照すると、モバイル電子デバイス１２の屋内位置特定を算出するのに、サーバ２２がまず、３２で、モバイル電子デバイス１２から、実質的に同時にキャプチャされた２Ｄピクチャと加速度測定からの入力データを受信する。たとえば、実施形態において、ユーザが、セルラー電話、スマートフォン、タブレット、ＧＯＯＧＬＥ  ＧＬＡＳＳ、または任意の類似したモバイル電子デバイス１２を使用して、その２Ｄ写真を撮影し、加速度測定を行うことが可能である。加速度測定は、たとえば、３軸加速度計からの３軸加速度測定であり得る。次に、そのユーザが、その２Ｄ写真および加速度測定を、サーバ２２上の位置特定モジュール１８に送信する。このため、実施形態において、その入力データは、モバイル電子デバイス１２によってキャプチャされた２Ｄ写真および加速度測定であり得る。
【００３９】
他の実施形態において、モバイル電子デバイス１２が、その２Ｄ写真および／またはそれらの加速度測定から情報を抽出することが可能であり、その抽出情報を、その２Ｄ写真および／またはそれらの加速度測定の代わりに、またはその２Ｄ写真および／またはそれらの加速度測定に加えて、送信することが可能である。たとえば、モバイル電子デバイス１２が、加速度計測定からピッチβ角およびロールγ角を計算することが可能であり、それらの計算された角度を、２Ｄピクチャと一緒に入力データとして位置特定システム１８に送信することが可能である。モバイル電子デバイス１２は、当業者には理解されるとおり、後段で説明される角度計算を実行することが可能である。
【００４０】
また、モバイル電子デバイス１２は、２Ｄピクチャから特徴ポイント２１を抽出することも可能であり、それらの特徴ポイント２１を、２Ｄピクチャ自体を送信する代わりに、位置特定システム１８に送信することが可能である。モバイル電子デバイス１２においてローカルで特徴ポイント２１を抽出することは、特徴ポイント２１抽出の効率、モバイル電子デバイス１２とサーバ２２の間のネットワーク条件の品質などに依存して、電力効率および／または帯域幅効率がより良い可能性があり、位置特定モジュール１８およびサーバ２２におけるコンピューティング・リソースを節約することが可能である。
【００４１】
３４で、サーバ２２が、モバイル電子デバイス１２から受信された加速度測定に基づいて、３Ｄ屋内マップ２０の検索空間を、マップ全体から３Ｄ屋内マップ２０のサブセットに制限する。モバイル電子デバイス１２から受信されたピッチβ角およびロールγ角が入力データの一部として受信されている場合、または３軸加速度計測定に基づいてモバイル電子デバイス１２のピッチ角βおよびロール角γをまず計算することによって、位置特定モジュール１８が、モバイル電子デバイス１２から受信されたピッチβ角およびロールγ角を使用して、検索空間を制限することが可能である。位置特定モジュール１８（またはモバイル電子デバイス１２）は、測定が行われた際のモバイル電子デバイス１２の加速が重力による加速であるものと想定することによって（すなわち、ノイズ・バイアスおよび／または調整不良バイアスは無視される）、ピッチβ角およびロールγ角を計算する。たとえば、ピッチ角（β）およびロール角（γ）は、以下の式に従ってモバイル電子デバイス１２の３軸加速度計測定から計算され得る。すなわち、
【００４２】
【数１】
2016524128.tif 000003
ここで、Ｇｕ、Ｇｖ、およびＧｓは、図２に示されるデバイス座標系（ｕ，ｖ，ｓ）における３軸加速度計によって検出された重力の成分である。
【００４３】
次に、位置特定モジュール１８は、計算されたピッチβ角およびロールγ角を使用して３Ｄ屋内マップ２０の検索空間を制限することが可能である。たとえば、位置特定モジュール１８は、加速度測定が、モバイル電子デバイス１２の傾きが直立であることを示す場合、水平方向の３０（三十）度の範囲内の向きだけを含めるように検索空間を制限することが可能である。位置特定モジュール１８は、計算されたピッチβ角およびロールγ角を使用して、モバイル電子デバイス１２によってもたらされた２Ｄピクチャからの特徴ポイントを、メモリ２８の中に記憶された３Ｄ屋内マップ２０からの特徴ポイントと照合して、３Ｄ屋内マップ２０のサブセットの範囲内でモバイル電子デバイス１２の並進ベクトル（Ｔｘ，Ｔｙ，Ｔｚ）およびヨー角αによって表現される３Ｄ位置の大まかな推定を得ることが可能である。たとえば、位置特定モジュール１８は、二次制約最小二乗推定（ｑｕａｄｒａｔｉｃ  ｃｏｎｓｔｒａｉｎｔ  ｌｅａｓｔ−ｓｑｕａｒｅ  ｅｓｔｉｍａｔｉｏｎ）または類似した計算を使用して、モバイル電子デバイス１２の並進ベクトル（Ｔｘ，Ｔｙ，Ｔｚ）およびヨー角αによって表現される３Ｄ位置の大まかな推定を得ることが可能である。また、位置特定モジュール１８は、Ｒａｎｄｏｍ  Ｓａｍｐｌｅ  Ｃｏｎｓｅｎｓｕｓ（ＲＡＮＳＡＣ）アルゴリズムなどを適用して、不一致の特徴ポイント・ペアに起因する異常値を除去することも可能である。たとえば、実施形態において、位置特定モジュール１８は、以下の式に従って変換誤差の二乗の合計であるＪを最小にすることによって、並進ベクトル（Ｔｘ，Ｔｙ，Ｔｚ）およびヨー角αを計算することが可能である。すなわち、
【００４４】
【数２】
2016524128.tif 000004
ここで、
Ｏは、一致した特徴ペア２１の数であり、
Ｒ＝Ｒｘ（γ）・Ｒｙ（β）・Ｒｚ（α）であり、
ｕｌ，ｖｌは、図２に示される、デバイス座標系（ｕ，ｖ，ｓ）における第ｌ番の特徴ポイント２１の２Ｄ座標であり、
ｘｌ，ｙｌ，ｚｌは、図２に示される、マップ座標系（ｘ，ｙ，ｚ）における第ｌ番の特徴ポイント２１の３Ｄ座標であり、
Ａは、３×３カメラ内部行列であり、
【００４５】
【数３】
2016524128.tif 000005
である。
所与のヨー角αに関して、Ｊを最小にすることは、Ｊをヨー角αのスカラー関数とした最小二乗推定問題であり得る。αの関数としての計算されたＪ（すなわち、Ｊ（α））が大域的最小値であることを確実にするのに、Ｊ（α）は、０°から３６０°までの範囲内で１０°ごとに位置特定モジュール１８によって計算されることが可能である（すなわち、この計算は、３６回、繰り返されることが可能である）。次に、位置特定モジュール１８は、ヨー角αの大まかな推定としてＪ（α）の最小値をもたらすαを選択し、この推定は、並進ベクトル（Ｔｘ，Ｔｙ，Ｔｚ）によって表現される、３Ｄ位置の対応する大まかな推定をもたらす。
【００４６】
３６で、サーバ２２上の位置特定モジュール１８が、３Ｄ位置およびヨー角αの大まかな推定を使用して、１メートル以内（ｓｕｂ−ｍｅｔｅｒ）の精度でモバイル電子デバイス１２の３Ｄ位置および向き（すなわち、モバイル電子デバイス１２の、デバイスの実際の位置から１メートル範囲内の位置および向き）を算出する。この完全な最適化は、たとえば、測定ノイズ、小さい加速からのバイアス、カメラもしくは加速度計の機械的な調整不良などに起因する加速度計測定誤差によって生じるいかなる誤差も小さくする。モバイル電子デバイス１２の３Ｄ位置および向きを算出するのに、位置特定モジュール１８は、開始点として、３Ｄ位置およびヨー角αの大まかな推定、ならびに計算されたピッチβ角およびロールγ角を使用して、メモリ２８の中に記憶された３Ｄ屋内マップ２０と２Ｄピクチャの間の一致した特徴ポイント・ペアを使用する。位置特定モジュール１８は、剛体運動を想定して、一致した特徴ポイント・ペアの間の並進ベクトル（Ｔｘ，Ｔｙ，Ｔｚ）および回転行列（Ｒｘ（γ），Ｒｙ（β），Ｒｚ（α））を算出することによって、６パラメータ最適化（すなわち、３Ｄ位置パラメータおよび３つの向きパラメータ）を行って、モバイル電子デバイス１２の３Ｄ位置および姿勢角を計算する。この完全な最適化は、ＭＡＴＬＡＢ、ＧＮＵ  ＯＣＴＡＶＥなどの知られている数値最適化ツールを使用して実行され得る。この完全な最適化は、位置特定モジュール１８が、１メートル以内の精度でモバイル電子デバイス１２の３Ｄ位置および向きを算出することを可能にする。
【００４７】
実施形態において、ヨー角αの大まかな推定を使用して、位置特定モジュール１８は、ニュートン・ラフソン法の反復を実行して、１メートル以内の精度でヨー角αを算出することが可能である。この反復において、ヨー角αは、以下の式に従って更新され得る。すなわち、
【００４８】
【数４】
2016524128.tif 000006
ここで、
【００４９】
【数５】
2016524128.tif 000007
ヨー角αが算出されると、図２に示される並進ベクトル（Ｔｘ，Ｔｙ，Ｔｚ）が、以下の式に従って位置特定モジュール１８によって計算され得る。すなわち、
【００５０】
【数６】
2016524128.tif 000008
【００５１】
３８で、次に、サーバ２２が、計算された３Ｄ位置および向き算出を、モバイル電子デバイス１２に送り返して、モバイル電子デバイス１２に１メートル以内の精度で屋内位置特定を提供する。モバイル電子デバイス１２は、位置特定モジュール１８によって提供された屋内位置特定を様々な用途で使用することが可能である。たとえば、屋内位置特定は、拡張現実アプリケーションのために、対話型屋内ツアーを強化するように、屋内環境内（たとえば、ショッピング・センター、空港などにおける）行き先案内のために、目の見えない人々のための移動補助のために、ワイヤレス緊急応答のために、または他の類似した用途で使用され得る。
【００５２】
図５を参照すると、実施形態において、図１に示されるシステム１０が、モバイル電子デバイス１２の位置特定の大まかな推定を近似するためにモバイル電子デバイス１２からのさらなる入力を使用することも可能である。たとえば、１４０で、サーバ２２が、ＷｉＦｉジオロケーション、モバイル電子デバイス１２からの明示的な入力（たとえば、ＱＵＩＣＫ  ＲＥＳＰＯＮＳＥ（ＱＲ）コードなどの２次元バーコードの読取り、部屋番号もしくは他の類似した位置特定情報の入力）などを使用して、図１に示される屋内構造１６内のモバイル電子デバイス１２の位置を近似することが可能である。１４０でＷｉＦｉジオロケーションを実行するのに、サーバ２２は、モバイル電子デバイス１２上で受信されたＷｉＦｉ信号を、サーバ２２上に記憶され得る、図１に示される屋内構造１６のＷｉＦｉフィンガプリント・マップと比較することが可能である。ＷｉＦｉジオロケーションは、数十メートルの大きさの半径内で、図１に示される屋内構造１６におけるモバイル電子デバイス１２の近似の位置をもたらす。ＷｉＦｉジオロケーションを実行するための様々な技法は、当業者によって容易に理解されよう。さらに、図１に示される屋内構造１６のＷｉＦｉフィンガプリント・マップは、たとえば、図１に示される屋内構造１６の既存のマップであることが、そのようなマップが利用できる場合、可能であることが、当業者には理解されよう。代替として、ＷｉＦｉフィンガプリント・マップは、ＷｉＦｉフィンガプリント・マッピングのための知られている技法に従ってオフライン段階で（たとえば、３Ｄ屋内マップ２０が構築されるのと同時に）あらかじめ構築されてもよい。ＷｉＦｉジオロケーションを介して検出された近似の位置は、後段で説明されるとおり、位置特定モジュール１８によって、３Ｄ屋内マップ２０の検索空間をさらに制限するのに使用される。前述したとおり、１４０で、サーバ２２は、モバイル電子デバイス１２からの明示的な入力を使用して、モバイル電子デバイス１２の位置特定を近似することも可能である。たとえば、図１に示されるユーザ１４が、モバイル電子デバイス１２で、ＱＲコードなどの２次元バーコードを読み取ることが可能であり、または部屋番号、階数（ｆｌｏｏｒ  ｎｕｍｂｅｒ）などの他の位置特定情報をモバイル電子デバイス１２に直接に入力することが可能である。
【００５３】
１３２で、サーバ２２が、図４に関連して説明されるのと実質的に同一の様態でモバイル電子デバイス１２から、実質的に同時にキャプチャされ得る２Ｄピクチャと加速度測定からの入力データを受信する。たとえば、実施形態において、ユーザが、セルラー電話、スマートフォン、タブレット、ＧＯＯＧＬＥ  ＧＬＡＳＳ、または任意の同様なモバイル電子デバイス１２を使用して、その２Ｄ写真を撮影し、それらの加速度測定を行うことが可能である。それらの加速度測定は、たとえば、３軸加速度計からの３軸加速度測定であり得る。次に、モバイル電子デバイス１２が、その２Ｄ写真およびそれらの加速度測定を、サーバ２２上の位置特定モジュール１８に送信する。このため、実施形態において、その入力データは、モバイル電子デバイス１２によってキャプチャされた２Ｄ写真および加速度測定であり得る。
【００５４】
前述したとおり、他の実施形態において、モバイル電子デバイス１２が、その２Ｄ写真および／またはそれらの加速度測定から情報を抽出することが可能であり、その２Ｄ写真および／またはそれらの加速度測定の代わりに、または２Ｄ写真および／またはそれらの加速度測定に加えてその抽出情報を送信することが可能である。たとえば、モバイル電子デバイス１２が、加速度計測定からピッチβ角およびロールγ角を計算することが可能であり、それらの計算された角度を、２Ｄピクチャと一緒に入力データとして位置特定システム１８に送信することが可能である。モバイル電子デバイス１２は、当業者には理解されるとおり、後段で説明される角度計算を実行することが可能である。
【００５５】
また、モバイル電子デバイス１２は、２Ｄピクチャから特徴ポイント２１を抽出することも可能であり、それらの特徴ポイント２１を、２Ｄピクチャ自体を送信する代わりに、位置特定システム１８に送信することが可能である。モバイル電子デバイス１２においてローカルで特徴ポイント２１を抽出することは、特徴ポイント２１抽出の効率、モバイル電子デバイス１２とサーバ２２の間のネットワーク条件の品質などに依存して、電力効率および／または帯域幅効率がより良い可能性があり、位置特定モジュール１８およびサーバ２２におけるコンピューティング・リソースを節約することが可能である。
【００５６】
１３４で、サーバ２２が、１４０で（たとえば、ＷｉＦｉジオロケーションを介して）検出された近似の位置、およびモバイル電子デバイス１２から受信された加速度測定に基づいて、３Ｄ屋内マップ２０の検索空間を、マップ全体から３Ｄ屋内マップ２０のサブセットに制限する。位置特定モジュール１８が、１４０で（たとえば、ＷｉＦｉジオロケーションを介して）検出された近似の位置を使用して、検索空間を、屋内空間の３Ｄ屋内マップ２０全体から、より小さいサブセット（たとえば、ＷｉＦｉジオロケーションを介して検出された近似の位置の周囲の２０（二十）メートルの半径内の）に制限する。検索空間をさらに制限するのに、位置特定モジュール１８は、モバイル電子デバイス１２から受信されたピッチβ角およびロールγ角を、それらの角度が入力データの一部として受信されている場合、使用することが可能であり、あるいは図４に関連して説明されたのと実質的に同一の様態で、測定が行われた際のモバイル電子デバイス１２の加速が重力による加速に限られるものと想定することによって（すなわち、ノイズ・バイアスおよび／または調整不良バイアスは無視される）、３軸加速度計測定からモバイル電子デバイス１２のピッチ角およびロール角を計算することが可能である。次に、位置特定モジュール１８は、計算されたピッチ角およびロール角を使用して、３Ｄ屋内マップ２０の検索空間を制約することが可能である。たとえば、位置特定モジュール１８は、加速度測定が、モバイル電子デバイス１２の傾きが直立であることを示す場合、水平方向の３０（三十）度の範囲内の向きだけを含めるように検索空間を制限することが可能である。次に、位置特定モジュール１８は、計算されたピッチ角およびロール角を使用して、モバイル電子デバイス１２によってもたらされた２Ｄピクチャからの特徴ポイントを、メモリ２８の中に記憶された３Ｄ屋内マップ２０の制限されたサブセットからの特徴ポイントと照合して、３Ｄ屋内マップ２０のサブセットの範囲内でモバイル電子デバイス１２の３Ｄ位置およびヨー角の大まかな推定を得る。たとえば、位置特定モジュール１８は、二次制約最小二乗推定または類似した計算を使用して、モバイル電子デバイス１２の３Ｄ位置およびヨー角の大まかな推定を得ることが可能である。また、位置特定モジュール１８は、Ｒａｎｄｏｍ  Ｓａｍｐｌｅ  Ｃｏｎｓｅｎｓｕｓ（ＲＡＮＳＡＣ）アルゴリズムなどを適用して、不一致の特徴ポイント・ペアに起因する異常値を除去することも可能である。
【００５７】
１３６で、図４に関連して説明されるのと実質的に同一の様態で、サーバ２２上の位置特定モジュール１８が、３Ｄ位置およびヨー角の大まかな推定を使用して、１メートル以内の精度でモバイル電子デバイス１２の３Ｄ位置および向き（すなわち、モバイル電子デバイス１２の、デバイスの実際の位置から１メートル範囲内の位置および向き）を算出する。この完全な最適化は、たとえば、測定ノイズ、小さい加速からのバイアス、カメラもしくは加速度計の機械的な調整不良などに起因する加速度計測定誤差によって生じるいかなる誤差も小さくする。モバイル電子デバイス１２の３Ｄ位置および向きを算出するのに、位置特定モジュール１８は、開始点として、３Ｄ位置およびヨー角の大まかな推定、ならびに計算されたピッチ角およびロール角を使用して、メモリ２８の中に記憶された３Ｄ屋内マップ２０と２Ｄピクチャの間の一致した特徴ポイント・ペアを使用する。位置特定モジュール１８は、剛体運動を想定して、一致した特徴ポイント・ペアの間の並進ベクトルおよび回転行列を算出することによって、６パラメータ最適化（すなわち、３Ｄ位置パラメータおよび３つの向きパラメータ）を行って、モバイル電子デバイス１２の３Ｄ位置および姿勢角を計算する。この完全な最適化は、ＭＡＴＬＡＢ、ＧＮＵ  ＯＣＴＡＶＥなどの知られている数値最適化ツールを使用して実行され得る。この完全な最適化は、位置特定モジュール１８が、１メートル以内の精度でモバイル電子デバイス１２の３Ｄ位置および向きを算出することを可能にする。
【００５８】
１３８で、次に、サーバ２２が、計算された３Ｄ位置および向き算出を、モバイル電子デバイス１２に送り返して、モバイル電子デバイス１２に１メートル以内の精度（すなわち、センチメートル・レベルの３Ｄ位置特定）で屋内位置特定を提供する。モバイル電子デバイス１２は、位置特定モジュール１８によって提供された屋内位置特定を様々な用途で使用することが可能である。たとえば、屋内位置特定は、拡張現実アプリケーションのために、対話型屋内ツアーを強化するように、屋内環境内（たとえば、ショッピング・センター、空港などにおける）行き先案内のために、目の見えない人々のための移動補助のために、ワイヤレス緊急応答のために、または他の類似した用途で使用され得る。
【００５９】
図１に示されるシステム１０は、電子デバイス１２からのキャプチャされた２Ｄ写真および加速度計測定からの入力データを、図１に示される屋内構造１６の既存の３Ｄ屋内マップ２０と一緒に使用して、モバイル電子デバイス１２の３Ｄ位置および向きの計算を有利に可能にする。別の実施形態においてはモバイル電子デバイス１２からのＷｉＦｉ測定および位置特定情報、ある実施形態においては、１つまたは複数の遠隔サーバ２２上に記憶された既存のＷｉＦｉフィンガプリント・マップもまた、モバイル電子デバイス１２の位置を特定するのに、その２Ｄ写真、およびそれらの加速度計測定に加えて使用される。有利なことに、図１に示される屋内環境１６の３Ｄ屋内マップ２０（および、実施形態において、ＷｉＦｉフィンガプリント・マップ）の他には、モバイル・デバイス上にデプス・カメラなどの特殊なハードウェアは必要とされず、無線周波数ビーコンなどの専用の機器の設置も必要とされない。
【００６０】
図１に示されるシステム１０は、１メートル以内（たとえば、センチメートル・レベル）の精度でモバイル電子デバイス１２の正確な屋内位置特定（すなわち、位置および姿勢角）を有利に提供する。
【００６１】
図１に示されるシステム１０は、ネットワーク最適化、正確な屋内ナビゲーション、広告（ユーザ・エンゲージメント）アプリケーションもしくはレジャー・アプリケーション（たとえば、ゲームもしくは博物館見学）などの拡張現実用途、または図１に示される屋内環境１６内のユーザの体験を向上させるための任意の類似したアプリケーションを含む、商業位置情報サービス（ＬＢＳ）と非商業ＬＢＳの両方のために実施され得る。さらに、システム１０は、ＧＯＯＧＬＥ  ＧＬＡＳＳなどのウェアラブル・スマート・ガジェットを使用する拡張現実ベースのアプリケーションのために有利であり得る高忠実度３Ｄ位置特定（単純な２Ｄナビゲーションではなく）を提供する。
【００６２】
特徴ポイント照合に関する計算オーバヘッドは、屋内環境のサイズに依存して（たとえば、図１に示される屋内環境１６に関する計算オーバヘッドは、３Ｄ屋内マップ２０のサイズと直線関係を有し得るので）、現実世界の屋内環境において高くなり得る。図３に示されるクラウド・コンピューティング・サービス２４は、クラウドにおける複数のサーバ２２にスケールアウト様態で計算を肩代わりさせることによって、この問題に有利に対処して、図３に示されるクラウド・コンピューティング・サービス２４が、モバイル電子デバイス１２の３Ｄ位置および向きの角度を計算することを可能にすることができる。図３に示されるクラウド・コンピューティング・サービス２４は、図１に示されるシステム１０が、数秒内に１０（十）センチメートル精度で位置特定結果をもたらすことを有利に可能にすることができる。
【００６３】
本発明を、本発明の詳細な実施形態に関連して図示し、説明してきたが、本発明の趣旨および範囲を逸脱することなく、その形態および詳細の様々な変更が行われ得ることが、当業者には理解されよう。たとえば、図１に示されるシステム１０は、屋内環境における位置特定を提供することに関連して説明されるが、システム１０は、屋外環境を含む様々な環境における位置特定を提供してもよい。
【図１】
2016524128.tif 000009
【図２】
2016524128.tif 000010
【図３】
2016524128.tif 000011
【図４】
2016524128.tif 000012
【図５】
2016524128.tif 000013
【国際調査報告】
2016524128.tif 000014
2016524128.tif 000015
2016524128.tif 000016