(57)【特許請求の範囲】
【請求項１】
携帯型装置の位置を決定する方法において、
前記携帯型装置によって検出可能な無線通信装置の識別情報を、決定されるべき特定の位置で入手し、それにより識別情報の第１の集合を入手するステップ、
１つまたは複数の調査結果を選択するために、識別情報の前記第１の集合を複数の調査結果を記憶するデータベースの内容と比較するステップであって、各調査結果は、１つの参照位置と、その位置で観測された無線通信装置の識別情報の第２の集合とを含んでいるステップ、および
前記選択された１つまたは複数の調査結果に基づいて前記携帯型装置の位置を決定するステップ
を含み、
前記位置を決定するステップは、
１つまたは複数の参照位置に基づいて位置を選択するステップを含み、
使用されるべき前記参照位置は、
前記第１の集合の識別情報に対応する調査結果に関連付けられた装置の数、    
前記第１の集合のいかなる識別情報にも対応しない調査結果に関連付けられた装置の数、および
前記データベースにおいて前記調査結果に関連付けられているものと識別されない前記第１の集合の識別情報の数
に基づいて選択される調査結果に関連付けられた位置である
方法。
【請求項２】
複数の参照位置から１つの位置を導出するステップは、それらの参照位置から１つの平均的な位置を入手するステップを含む請求項１に記載の方法。
【請求項３】
前記第１の集合の前記識別情報の１つまたは複数を無視すべきか否かを判定するステップをさらに含む請求項１または２に記載の方法。
【請求項４】
前記識別情報を入手するステップは、前記特定の位置で前記携帯型装置により実行され、前記位置を決定するステップは、別の時刻および別の位置において実行される請求項１ないし３のいずれかに記載の方法。
【請求項５】
前記無線通信装置は短距離無線アクセス・ポイントを含み、前記識別情報はＭＡＣアドレスを含む請求項１ないし４のいずれかに記載の方法。
【請求項６】
複数の参照位置で検出可能な無線通信装置の識別情報をデータベースに取り込むステップ、および
請求項１から５のいずれか１項に記載の方法を使用して携帯型装置の位置を決定するステップ
を含む位置決定方法。
【請求項７】
前記特定の位置が特定されると、前記携帯型装置によって検出可能な無線通信装置の前記入手した識別情報を使用して前記データベースの内容が更新される請求項６に記載の位置決定方法。
【請求項８】
ウォードライブを行うことにより、かつ/または他の情報源から受信した無線通信装置情報を処理することにより前記データベースへの取込みが行われる請求項６または７に記載の位置決定方法。
【請求項９】
衛星位置決定システムに基づいて位置を決定するステップ、および
前記衛星位置決定システムを使用した前記位置特定を支援または強化するために、請求項１ないし８のいずれかに記載の方法を使用して位置を決定するステップ
を含む位置決定方法。
【請求項１０】
検出可能な無線通信装置の識別情報を入手するステップは、
信号強度、
信号対雑音比、
誤り率、
ドップラー周波数
の１つまたは複数を測定するステップをさらに含む請求項１ないし９のいずれかに記載の方法。
【請求項１１】
前記データベースの内容が、所与の参照位置からの所与の通信装置の信号に関して、
信号強度、
信号対雑音比、
誤り率、
ドップラー周波数
の１つまたは複数を含む請求項１ないし１０のいずれかに記載の方法。
【請求項１２】
前記携帯型装置によって検出可能な無線通信装置の識別情報を、決定されるべき特定の位置で入手する前記ステップが、カメラを使用して実行される請求項１ないし１１のいずれかに記載の方法。
【請求項１３】
後続の解析で前記特定の位置を決定できるように画像ファイルに前記識別情報を添付するステップをさらに含む請求項１２に記載の方法。
【請求項１４】
携帯型装置の位置を決定するシステムであって、
前記携帯型装置によって検出可能な無線通信装置の識別情報を特定の位置で入手し、それに  より識別情報の第１の集合を入手するための無線受信機を含む前記携帯型装置と、
複数の調査結果を記憶するデータベースであって、前記各調査結果はそれぞれの参照位置において検出可能な無線通信装置の識別情報を含んでいる、データベースと、
識別情報の前記第１の集合を前記データベースの内容と比較するための手段と、
１つまたは複数の参照位置に基づき位置を選択することによって前記携帯型装置の位置を決定するための手段と
を含み、
使用されるべき前記１つまたは複数の参照位置は、
前記第１の集合の識別情報に対応する調査結果に関連付けられた装置の数、    
前記第１の集合のいかなる識別情報にも対応しない調査結果に関連付けられた装置の数、および
前記データベースにおいて前記調査結果に関連付けられているものと識別されない前記第１の集合の識別情報の数
に基づいて選択される調査結果に関連付けられた位置であるシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、携帯型装置用位置決定システムに関する。
【背景技術】
【０００２】
全地球位置決定システムは、ますます多くの家庭用携帯型製品に使用されるようになってきている。しかし、ＧＰＳシステムは、携帯型装置内に重要な処理機能を必要とする。さらに、立て込んだ地域では上空の見通しが悪い場合が多く、ＧＰＳ信号を常時取得できるわけではない。
【０００３】
全体的な信頼性を向上させられるように、ＧＰＳデータを他の位置決定システムのデータで補うことが知られている。例えば、上記ＧＰＳシステムをさらに堅牢にするために、正確性で僅かに劣る一時的な位置決定システムとして、移動電話基地局信号に基づく三角測量を採用することができる。
【０００４】
本発明は、スタンドアロン・システムとして使用することのできる、または衛星位置決定システムを補うために使用することのできる代替位置決定システムに関する。
【０００５】
位置決定システムとして機能する位置ビーコン・データベースを提供することが既に提案されている。そのビーコンがＷｉＦｉアクセス・ポイント（ＡＰ）である場合、そのようなデータベースは、それらのＭＡＣアドレスと、算出されたＡＰの推定位置と、場合によってはそれらの電力プロファイル、すなわちそのＡＰ周辺における様々な位置でどの程度の信号強度が期待できるかとを含む。通常、このデータベースは、観測されたＡＰの識別情報と、ＡＰ信号強度の測定値と、場合によっては他の信号データ（例えば、ドップラー、誤り率）とを既知の位置で収集して、いわゆる「ウォードライブ」を実行することにより導出される。ＡＰの観測位置は、ＧＰＳシステムによって決定できる場合がある。
【０００６】
ユーザが位置測定を要求した場合、特にＧＰＳのような代替手段が使用不可能な場合は、このようなデータベースが使用される。通常、従来技術では、位置を見つける処理は以下の通りである。
【０００７】
（ｉ）観測可能なＡＰを求めて、それらＡＰの信号強度および他の信号データにより走査する。
（ｉｉ）データベース内で、その位置と、場合によってはそれらＡＰの電力プロファイルとに関する参照データを検索する。
（ｉｉｉ）推定されたユーザ位置を導出する。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかし、この方法は多大なデータ解析を要する。
【０００９】
検出されたＡＰの推定位置を従来技術の方法で使用するには、各ＡＰの位置を推定するために十分なサンプル・データが位置測定における支援のために使用可能となる前に、その十分なサンプル・データを収集する必要がある。したがって、ＡＰ信号の検出に関するデータの小集合は、信頼をもって使用することはできない。検出された信号の互いに素な集合を１つのＡＰのモデルで処理することは、発生し得ることではあるが、例えばそのＡＰの可視性に２つの別個のパッチがある場合などは、これもまた困難な場合がある。
【課題を解決するための手段】
【００１０】
本発明によれば、携帯型装置の位置を決定する方法において、
上記携帯型装置によって検出可能な無線通信装置の識別情報を、決定されるべき特定の位置で入手し、それにより識別情報の１つの集合を入手するステップ、
１つまたは複数の調査結果を選択するために、識別情報の上記集合を複数の調査結果を記憶するデータベースの内容と比較するステップであって、各調査結果は、１つの参照位置と、その位置で観測された無線通信装置の識別情報の１つの集合とを含んでいるステップ、および
上記選択された調査結果の処理に基づいて上記携帯型装置の位置を決定するステップを含む方法が提供される。
【００１１】
本方法は、記憶された調査結果、すなわち、ある参照位置とその位置で観測された無線通信装置の識別情報の１つの集合とを使用する。このような調査結果は、参照位置でウォードライブ中などに実行される走査で収集される。観測された通信装置の推定位置に関する位置情報を処理する代わりに、本発明は、その参照位置で受信した信号の識別情報の処理に基づいて直接的に位置を発見する。これにより、より信頼性のある位置決定方法が提供され、使用するデータベースの維持管理もさらに容易になる。
【００１２】
事前に記憶してある通信装置の位置ではなく上記識別情報（考慮した追加データも任意で使用されるが）に基づいて処理することにより、追加の処理ステップが取り消されるか、またはより簡易な方法で扱われる。本発明の方法は、観測された装置の特定された位置に関するいかなる情報または推定も必要とせず、その代わり、解析は、無線通信装置が観測されたか否かだけに基づいて行われる。
【００１３】
本発明は、参照位置の走査から導出された比較可能な情報で位置測定を入手しようとする際に、走査結果のより直接的な照合を提供する。
【００１４】
したがって、使用されるべきデータベースの基礎として無線通信装置の位置が使用されることはなく、むしろ既知の位置で既に観測された装置のいくつかの集合の識別情報が使用される。
【００１５】
無線通信装置は、通常、無線ビーコンまたは基地局、すなわち信号をブロードキャストする本来静止している装置（当然ながら、家庭用ＷｉＦｉ  ＡＰで発生し得るように、それら装置がある位置から別の位置に移動する可能性がある場合も含めて）である。
【００１６】
単純な例では、位置を決定するステップは、
現在観測可能な無線通信装置の識別情報と同じ識別情報を含むので、データベースから選択された調査結果の位置を報告するステップ
を含むことができる。
【００１７】
この方法は、特定された位置と、同じ通信装置が検出可能であった（１つまたは複数の）参照位置との間の単純なマッピングを提供する。照合する調査結果が複数ある場合には、平均的な位置が使用できる。未知の位置で観測されるよりも多くの通信装置が識別された参照位置がある場合がある。位置は、最も良く一致した複数の参照位置から導出できる。
【００１８】
最も近い１つまたは複数の一致を特定するために、いくつかの異なるアルゴリズムを使用できる。
【００１９】
例えば、位置を決定するステップは、
１つまたは複数の参照位置に基づいてある位置を選択するステップを含む場合があり、
使用されるべき参照位置は、
上記集合の識別情報に対応する参照位置から検出可能な装置の数、
上記集合のいかなる識別情報にも対応しない参照位置から検出可能な装置の数、および
データベースにおいて参照位置から検出可能であると識別されない集合の識別情報の数
に基づいて選択される。
【００２０】
この方法は、参照位置から観測される装置と、現在の位置から観測される装置との一致と、それらの観測結果間の違いが導出されるベン図の演算を本来提供するものである。
【００２１】
未知の場所を推定するために使用される方法は、集合の上記識別情報の１つまたは複数を無視すべきか否かを判定するステップをさらに含むことができる。通信装置が位置を移動しており、したがって、ある参照位置でその通信装置が識別された際におけるその通信装置の位置と、未知の場所の推定を試みている最中のその通信装置の次の場所とは不一致となる。
【００２２】
識別情報を入手するステップは、特定の位置で携帯型装置により実行でき、識別情報の集合を処理するステップは、別の時刻に、特定されるべき場所と同じでない場所で実行できる。すなわち、携帯型装置には低い演算機能を備えることができ、携帯型装置はせいぜい、場所情報が求められた時点で検出可能な装置の識別情報を記憶するだけでよい。
【００２３】
無線通信装置は短距離無線アクセス・ポイントを含むことができ、上記識別情報はＭＡＣアドレスを含むことができる。
【００２４】
本発明は、
複数の参照位置で検出可能な無線通信装置の識別情報をデータベースに取り込むステップ、および
本発明の方法を使用して携帯型装置の位置を決定するステップ
を含む位置決定方法も提供する。
【００２５】
この方法は、位置決定方法でのデータベースの作成と、そのデータベースのその後の使用とを包含する。
【００２６】
特定の位置が特定されると、データベースの内容は、携帯型装置によって検出可能な無線通信装置の入手した識別情報を使用して更新することができる。したがって、この位置決定システムを使用するだけでデータベースを最新に維持することができる。
【００２７】
このデータベースは、ウォードライブを行うことにより、かつ/または他の情報源から受信した無線通信装置情報を処理することにより（最初の）取込みを行うことができる。例えば、それらの他の情報源は、それら通信装置の所有者であり、位置決定システムの加入者でもある人物（すなわち、位置決定システム管理者の顧客）であってよい。
【００２８】
本発明は、
衛星位置決定システムに基づいて位置を決定するステップ、および
上記衛星位置決定システムを使用した上記位置決定を支援または強化するために、本発明の方法を使用して位置を決定するステップ
を含む位置決定方法も提供する。
【００２９】
これは１つのシステムに２種類の位置決定システムを提供することであり、その結果、そのシステム全体の堅牢性／信頼性は向上する。
【００３０】
検出可能な無線通信装置の識別情報を入手するステップは、
信号強度、
信号対雑音比、
誤り率、
ドップラー周波数
の１つまたは複数を測定するステップをさらに含むことができる。
【００３１】
これらは次いで、さらに正確な位置測定を得られるように、照合アルゴリズムの一部として使用することができる。このデータベースの内容は次いで、所与の参照位置からの所与の通信装置の信号に関して同じ情報を含む。
【００３２】
上記携帯型装置によって検出可能な無線通信装置の識別情報を、決定されるべき特定の位置で入手するステップは、カメラを使用して実行することができる。
【００３３】
最近ではカメラにＷｉＦｉ機能が導入される傾向があるが、この機能は、写真に位置データを添付する（いわゆるジオタギング）目的で低価格の位置決定システムを実施するために使用することができる。一例では、後続の解析で特定の位置を決定できるように、識別情報（および当該照合アルゴリズムの一部を形成するいかなる他のデータ）を画像ファイルに添付することができる。これは、位置データの処理を別個の装置で実行できるシステムを提供する（例えば、位置復号サービスを提供する中央サーバ）。これは、カメラ自体の演算要件を低減する。
【００３４】
識別情報を局所的に特定するための代替形態として、ＷｉＦｉ中間周波数（ＷｉＦｉ−ＩＦ）データを後で抽出できるように、そのデータのサンプルを記憶することができる。
【００３５】
本発明は、携帯型装置の位置を決定するシステムであって、
無線通信装置の識別情報を特定の位置で入手し、それにより識別情報の１つの集合を入手するための無線受信機を含む携帯型装置と、
複数の参照位置で検出可能な無線通信装置の識別情報を記憶するデータベースと、
識別情報の上記集合を上記データベースの内容と比較するための手段と、
１つまたは複数の選択された参照位置の処理に基づいて上記携帯型装置の位置を決定するための手段と
を含むシステムも提供する。
【００３６】
次に、本発明の実施例を添付の図面を参照して詳細に説明する。
【図面の簡単な説明】
【００３７】
【図１】図１は、３つの無線通信装置が観測された走査結果を示す図である。
【図２】図２は、本発明の方法を実施するプロセッサにより使用されるデータを示す図である。
【図３】図３は、サウンディングが処理される方法を説明するベン図である。
【図４】図４は、サウンディングの解析で得られるデータ変数の集合を示す図である。
【図５】図５は、重心を使用して位置を導出できる方法を説明するために使用される図である。
【図６】図６は、本発明のシステムの一例を示す図である。
【発明を実施するための形態】
【００３８】
本発明を詳細に説明する前に、まず、いくつかの概念および用語を定義する。
【００３９】
ビーコン
別の装置の検出可能な形式でそれ自体を識別する、常態では静止していると仮定される任意の無線通信装置。一例としてはＷｉＦｉアクセス・ポイント（ＡＰ）があるが、類推によって、本発明はＡＰに限定されることなく、移動電話基地局、テレビおよびラジオの送信機、IEEE 802.15.1、IEEE 802.15.4、ＷｉＭＡＸおよびその他のマイクロ波システムを使用するシステムの構成要素など他のビーコンも含む。いかなる有用なビーコンも、一意（絶対的にそうであるわけではないが）とみなすことのできる識別子を有するもの、例えばＡＰがそのＭＡＣアドレスで確実に識別できるものと仮定する。
【００４０】
装置の位置が既知の場合に行われる測定に関して：
調査結果
潜在的に多くのビーコンを単一の既知の位置で検索して入手したビーコン・データ（観測）に、その参照位置に関するデータとデータ（時刻、方法など）の集合を伴う集合。調査結果という用語は、能動的な検索（ビーコンにそれら自体を識別するよう要求するために送信が使用される場合）にも受動的な検索（検索が、ビーコンによるそれら自体の表明を待ち受けることしか含まない場合）にも使用される。調査結果は１つの参照位置を暗示する（各観測と同様。下記参照。）。
【００４１】
観測
１件の検索の結果として１つのビーコンに関連付けられたデータであり、このデータはビーコンの識別情報であってよいが、他の特徴（例えば、信号強度）を含んでもよい。各観測は調査結果に関連付けられており、したがって、暗に参照位置にも関連付けられている。
【００４２】
参照位置
調査が実行される（したがって、ビーコン情報が収集される）既知の位置。
【００４３】
ウォードライブ
特に一連の位置で調査を実行するため、すなわちドライブ中に既知の位置で検出可能なビーコンに関するデータを取得するために車両を使用すること。
【００４４】
装置の位置が未知の場合に行われる測定に関して：
サウンディング（sounding）
ユーザが位置を知ろうとした場合に、ビーコンを求めて（能動的に、または受動的に）走査した結果。通常、いくつかのビーコンが検出され、そのような検出それぞれに関連付けられたデータをオブザベーションと称する。
【００４５】
オブザベーション
１件の走査の結果として１つのビーコンに関連付けられたデータ。位置が未知の場合、これはユーザの状況の中であり、走査された位置は含まない。
【００４６】
検索は既知の場所のビーコンの識別情報に関するが、走査は未知の場所のビーコンの識別情報に関することに留意されたい。
【００４７】
本発明は、携帯型装置の位置を決定する方法において、携帯型装置によって検出可能な無線通信装置の識別情報を特定の位置で入手し、それにより１つの識別情報の集合を入手する方法（上記で定義したように、これはサウンディングである）を提供する。
【００４８】
識別情報の集合は、複数の参照位置から検出可能な無線通信装置の識別情報を記憶するデータベースを使用して解析される。データベースはしたがって、ウォードライブの調査結果と観測結果を含む。携帯型装置の位置は、解析と、調査結果および観測結果に関連付けられた参照位置の処理とに基づいて導出される。
【００４９】
本システムが運用可能になる前に、調査結果情報を収集する必要がある。
【００５０】
調査結果情報の収集
ビーコンの観測を得るために、補助的な位置決定機能がウォードライブ中に使用される。観測の時刻および日付、緯度、経度、高度、ＭＡＣアドレス、信号強度、信号対雑音比、信号誤り率、信号ドップラー（ドップラーの大きなシフトは、通過中の携帯ルータ、例えば通過中の電車内にあるルータを示すか、あるいはユーザが電車に乗っている可能性を示す）などの様々なデータ項目が記録される。位置は、以下の項目から知ることができる。
【００５１】
（ｉ）ユーザによる装置の通常の使用中に入手される、ＧＰＳベースの位置測定、
（ｉｉ）専用ウォードライブからの、ＧＰＳベースの位置測定、
（ｉｉｉ）ユーザ入力、
（ｉｖ）既に識別されたビーコンのオブザベーションからの位置測定、
（ｖ）既知の位置からの距離および方向など、他の情報からの干渉。
【００５２】
データベースは、データの１つまたは複数の情報源、すなわち調査結果情報を収集するために上記方法のどれが使用されたかを含むことができる。任意で、推定位置の不確実性を推定し、記録してもよい。不確実性は、ＧＰＳ位置測定の場合には小さく、または位置推定の別の方法よりは大きい場合がある。
【００５３】
データベースは、上記で説明したように、ウォードライブ中に収集された情報に基づいて生成することができる。しかし、データベースを生成する他の方法も共に、または代わりに使用することができる。例えば顧客基盤は、その位置およびそのＷｉＦｉノード識別情報に関する入手可能なデータを既に有している可能性があり、そのＷｉＦｉノード自体からの所与の距離内でそのＷｉＦｉノードが検出可能であると仮定すると、参照位置データベースを構築するためにこのデータを使用することができる。次いで、参照位置を導出することができる。
【００５４】
調査結果ベースのデータベースに加えて推定ビーコン位置のデータベースも使用可能な場合は、当業者には混合アルゴリズムが明らかになろう。例えば、上記２つのデータベースから独立した位置測定を何らかの方法で平均化することができる。あるいは、調査結果ベースのデータベース内にある既存の調査結果のメンバーシップの適格性を判定するために、ビーコン範囲の推定を使用してその調査結果に疑似的な観測を追加するために、推定ビーコン位置データベースを使用することができる。これにより、新たな疑似的参照位置を作成すること（別の方法である）が回避される。
【００５５】
データベースの生成
（ウォードライブからの、または他のデータから導出された）調査結果情報からデータベースが生成されるが、ここでも任意に不確実性情報を加えることができる。このデータベースは、純粋にそれ独自の調査結果情報から、携帯装置自体の中に置いてもよく、または（より好適には）データベース情報をサーバ上のデータベースと共有してもよい。あるいは、サーバ上の共有データベースの新版を、後で使用するために携帯型装置に時折ダウンロードすることができる（例えば、サーバとの通信が不可能な場合）。同様に、ローカル・データベースへの新規追加を、サーバ上の共有データベースに、都合のよいときに時折アップロードすることができる。データベースを使用した位置の特定に必要な処理を、同様にその装置またはそのサーバ上で実行することができる。
【００５６】
データベースの圧縮
調査結果情報は、データベースを形成する前または後に任意で圧縮することができる。複製情報または複製に近い情報を回避するため、調査結果データのサイズを管理するため、また位置特定照合処理によって使用し易い方法で情報を構成するために、このような圧縮が望ましい。圧縮は、例えば以下の１つまたは複数を行うことにより達成することができる。
【００５７】
（ｉ）地理的領域に割り当てる
領域は、ビーコンが観測された地域を示す。領域は、ＷｉＦｉが複数階にわたって提供されるオフィスビルのように３次元であっても、ＷｉＦｉが提供される駅のように２次元であっても、またはビーコンが可視的な道路の１区間のように線形であってもよい。
【００５８】
（ｉｉ）クラスタを形成する
一群の観測が相互に近接して位置している場合、それらを１つの複合観測にクラスタ化することができる。
【００５９】
（ｉｉｉ）量子化によりデータベースを観念的に扱う
量子化は以下に示すものであってよい。
【００６０】
ａ）数メートルから数百メートル以上に及ぶ任意のセル・サイズの長方形のグリッド・ベースであって、一部の領域を他の領域よりも高密度にカバーするように、カバーされる地域全体にわたってセル・サイズが一定である必要はないグリッド・ベースの量子化であってよい。ある領域は全くカバーされない場合がある。この量子化は、必ずしも、観念的に扱われるオブザベーションを領域の中心に留めておくことを意味するものではない。これらのオブザベーションは、セル内で観測された位置の近く（道路上の位置に対応するものであってよい）に残しておくことができる。
【００６１】
ｂ）量子化のために他のテッセレーション中のポリゴンまたは多面体に基づく量子化であってよい。三角形と六角形は、均一な方法で（すなわち、全て同じサイズで）大きな球面の全ての緯度と経度をカバーできるという利点があるが、サイズの等しい長方形では、例えば赤道地帯の長方形や緯度の高い地帯の長方形は必然的に長方形の数が異なるなど、パターン内に必然的に不規則性が生じることになり、それにより不規則に積まれた煉瓦状になる。
【００６２】
ｃ）間隔が量子化された線形サンプルの集合に基づく量子化であってよい。これは、直線的な道路に沿って移動中に収集された調査結果のために使用するのに特に適している。
【００６３】
（ｉｖ）例えばマッピングされた道路に沿って量子化された場所のような地理的特徴、または建築物、駐車場などのような領域内の存在を使用した、より洗練された混合データ・セット。
【００６４】
圧縮は、例えば、その不確実性に相当する境界を領域の縁に追加したり、それら調査結果の報告を不確実性の推定内でクラスタ化したり、または位置推定における不確実性に関する量子化された間隔を使用したりすることにより、調査結果の位置の推定における不確実性を考慮することができる。
【００６５】
上記ステップは、照合機能を実行できるように、基本的に本発明のシステムに対する基盤を設定する。
【００６６】
ユーザは、未知または不確実な位置にいる場合、ビーコンを観測するためにサウンディングを単に実行してシステムを操作する。観測されたビーコンのデータ（「オブザベーション」）がデータベースと照合される。様々なアルゴリズムが可能である。
【００６７】
以下でアルゴリズムのいくつかの例を示すが、多くの変形形態が可能である。
【００６８】
全てのアルゴリズムは、典型的には緯度、経度および高度として位置を生成するが、任意で不確実性の推定もそれに加えられる。任意で、複数の出力が、例えば最も適した位置と共に、検索位置が特定される信頼性が高まる、より広範な領域と共に提供されてもよい。
【００６９】
第１の実施例では、アルゴリズムは、ビーコンが観測され、以前の調査結果からのデータベース内の観測データが相互に対応する、１つまたは複数の位置または位置領域を発見する。したがって、位置は、同じビーコン識別情報の集合を有する参照位置に基づいて選択される。ビーコンは常に活動中であるわけではないので、完全一致は位置特定の成功に必須ではない。例えば、サウンディングがビーコンのオブザベーション｛Ａ，Ｂ，ｘ｝を生じる場合、｛Ａ，Ｂ，Ｃ｝の調査結果を有する位置は成功した照合である。この照合の場合、ビーコンＣは調査時には活動中だったが現在は電源を切っており、ビーコンｘは以前に観測されたことはないと仮定する。この照合は、調査結果位置ポイントに不確実性を考慮することができ、また観測のデータ源を考慮することもできる。
【００７０】
一度位置が確定されると、それをユーザに提示する方法はいくつかある。位置特定はアプリケーションまたはユーザに提供することができる。サーバによる実施態様の場合、その位置特定はサーバから装置に返送されるか、または別のサービスに伝達されることになる。これは次いで、例えば地図、衛星写真、地形モデル、または他の位置情報サービス上に位置を表示することに繋がる。
【００７１】
ユーザまたはアプリケーションは、位置特定を洗練するために、または追加情報に鑑みて位置特定を変更するために位置特定と対話することができる。このような変更は、任意で、プロセッサ・データベースに返送することができる。
【００７２】
位置特定の次に（およびユーザまたはアプリケーションによる任意の更新の次に）、いかなる追加情報および観測でも任意でデータベースに追加することができるが、ここの時点では検索の位置が分かっているので、この結果は有用なビーコン調査結果とみなすことができる。例えば、以前には観測されなかったビーコンのオブザベーションを観測として扱いデータベースに追加することができる。したがって、データベースは動的に最新のものとして維持される。
【００７３】
上記実施例は調査結果ベースであり、（ウォードライブの）調査結果をユーザのオブザベーションと照合する。当然ながら、前述のように直接的な照合は発生しない。次に、より完全な方法を説明する。
【００７４】
一般に、いくつかのオブザベーションを含んだサウンディングがあるとすると、アルゴリズムは、少なくとも１つのビーコンを共通して含んでいる調査結果を識別する必要がある。オブザベーションで観測されたビーコンをまさしく含んだ複数の調査結果がある場合、それらの調査結果が選択される。しかし、その代わりに、オブザベーションで観測された全てのビーコン（と、さらにいくつかの他のビーコン）を含んだ複数の調査結果がある場合、それらの調査結果が選択される。洗練の際には、最少の外来（観測されなかった）ビーコンを含んだ調査結果だけを選択することができる。
【００７５】
全てのビーコンを含んだ調査結果がない場合、最大数の参照ビーコンを共通して含んでいる調査結果が選択され、それら調査結果から、最少の外来（観測されなかった）ビーコンを含んだ調査結果だけを選択することができる。
【００７６】
次いで、位置推定を提供するために、これらの選択された調査結果の位置の平均をとることができる。この場所における誤りの推定は、選択された参照ポイントを含んだ（１つまたは複数の）領域、またはこの領域（例えば円または長方形であってよい）のサイズと定義できる。
【００７７】
これは、それらビーコンの組合せが以前に観測された位置にできるだけ近接した存在を探す、極めて無理なアルゴリズムの一例である。
【００７８】
次に、調査結果とサウンディングとの間に直接的な一致が少ない場合に、最も近似した一致をどのようにして選択するかを示すために、第２の実施例を説明する。
【００７９】
ここで、無線通信装置が、ＭＡＣアドレスを有するＷｉＦｉ  ＡＰであると仮定する。位置特定が要求される場合、図１に示すような（一般に）いくつかのオブザベーションからなるサウンディングを得るために走査が実行される。本実施例では、サウンディングは、サウンディングの結果、ＭＡＣアドレス１、２および３を有する３つの観測された無線通信装置が得られる。
【００８０】
調査結果のデータベースに対して、上記ＭＡＣアドレスのいずれかを含み、かつ調査結果を数学的集合として扱うものはどれかが問い合わされる。調査結果はそれぞれ様々なＭＡＣアドレスからなる。図２は、様々なデータ・セットを示す。
【００８１】
本実施例では、サウンディングがＭＡＣアドレスａ、ｂ、ｃおよびｄを観測している。このデータベースは、５つの調査結果１から５を含んでいるが、それらはＭＡＣアドレスａ、ｂ、ｃおよびｅだけを含んでいる。
【００８２】
すなわち、ＭＡＣアドレスｄはサウンディングで観測されたが、データベースには含まれておらず、したがって、データベースに記憶されたどの調査結果にも含まれていない。
【００８３】
調査結果５はＭＡＣ−ｅを観測したが、ＭＡＣ−ｅはサウンディングされなかった。
【００８４】
本実施例は、起こりうる不一致を示す。例えば、ＭＡＣ  ｄは、ウォードライブ中に導入されなかった新しいＷｉＦｉ  ＡＰであってもよく、ＭＡＣ  ｅはサウンディング中に切っておいてもよく、または入れておいてもよいがサウンディングを実行している場所で圏外になってもよい。
【００８５】
共通ＭＡＣアドレス、消失ＭＡＣアドレスおよび余剰ＭＡＣアドレスを演算するために各調査結果と共にサウンディングが処理される。これは、調査結果５に関して図３に示すようなベン図とみなすことができる。本実施例では、２つのＭＡＣアドレスが共通であり、１つが消失であり（調査結果には含まれるが観測されていない）、２つが余剰である（サウンディングされたが、比較した調査結果には含まれない）。明らかに、データベースに含まれないオブザベーションはどれも、全ての調査結果に関して余剰となる。
【００８６】
調査結果ごとにスコアを算出することができる。重みづけを以下の方法で適用することができる。
−共通のＭＡＣアドレスの数をプラスの方向に重みづけする。
−余剰ＭＡＣアドレスの数を僅かにマイナス方向に数える。
−消失ＭＡＣアドレスの数を僅かにマイナス方向に数える。
【００８７】
これで、図４に示すデータ変数の集合は、ｓ１からｓ５、ｃ１からｃ５、およびｍ１からｍ５（ｓ＝余剰、ｃ＝共通、ｍ＝消失）となる。下記の括弧内の数字は、要素の数に相当する。
【００８８】
上記の実施例の最良の調査結果は、共通する２つのＭＡＣアドレス（ｃ１＝ｃ２＝２）があり、２個の余剰と０個の消失をマイナス方向に数えるので（ｃ１＝ｃ２＝２；ｓ１＝ｓ２＝２  ｍ１＝ｍ２＝０）、調査結果−１と調査結果−２である。
【００８９】
調査結果５は、同数の共通ＭＡＣアドレスと余剰ＭＡＣアドレスを有する僅差の２位だが、消失ＭＡＣアドレスを僅かにマイナス方向に数える。
【００９０】
本アルゴリズムの照合およびスコアリング工程における洗練は、信号強度の考慮と、調査結果が最新である程度の考慮と、調査結果がどのように得られたかの考慮（明示的な位置などはないが特定された調査結果に共通であることから推論された、ＧＰＳ付きウォードライブ、ＧＰＳ付きカメラ）を含むことができる。
【００９１】
原則として、下記で検討する位置特定アルゴリズムの最終段階には最高スコアの調査結果だけを使用することができる。
【００９２】
スコアの等しい調査結果の集合をとることができ、また、例えば単純な平均値または（信号強度、信号対雑音比、ファジー日付マッチ、調査結果の情報源−例えばカメラ、ウォードライブからのＧＰＳ追跡位置特定−、または重みづけに関する他の基準を使用して）重みづけされた平均値によって調査結果の場所の平均を得ることができる。これは、信号強度（その他）を最良の照合段階で使用するための異なる使用方法である。ここで、信号強度（その他）は、信号データとは関係なく、調査結果の最良の集合が得られた後でのみ使用される。ポイントの重心をとることができる。別法として、この場合、ポイントを結ぶワイヤーフレームをとることができる。さらに別法として、また、一般的によりよい方法として、位置ポイントを囲む多角形エンベロープの重心をとることができる。例えば、図５に示すように、頂点に調査結果位置ポイントのある非凹角、非凹面、囲み型の多角形の重心をとることができる。これで、非常に近接した場所にある複数の調査結果の偏りが回避される。
【００９３】
調査結果は、累積的に、またはマスター・データベースからサブ・データベースを抽出する際の、時間および／または空間で量子化することができる。
【００９４】
このアルゴリズムは、調査結果およびサウンディングがそれぞれ個々に（事実上）同じ時刻および場所で取られたいくつかのオブザベーションを含むことを必要とする。ウォードライブ／獲得ツールが一回でいくつものビーコンを検出する機能を持たない場合、時間および／または空間を量子化することでこれをシミュレーションすることができる。多くの場合、静止しているビーコンはベン図の共通地域で十分な照合を提供するので、このアルゴリズムは、移動するビーコンのほんの一部に対して堅牢性を示す。町または市街の任意の１ポイントで１ダース以上のルータを検出できる場合があるが、それらのルータは、使用中の変化を考慮するためにデータベースを最新に保てるよう比較的静的に保持される。
【００９５】
上記実施例は、観測と調査結果の照合に基づくが、場所を導出するために最良の調査結果が使用されるという点で調査結果ベースである。その代わり、アルゴリズムは、以下で説明するように観測ベースであってよい。
【００９６】
ビーコンのいくつかのオブザベーションを含むサウンディングがある場合、それらビーコンの全ての観測に対する参照ポイントを導出することができる。例えば、選択された観測の位置の平均参照位置をとることができる。換言すれば、ビーコンｘを含むいかなる調査結果でも、ビーコンｘを観測するサウンディングにその参照位置を考慮する。これはアルゴリズムを簡素化する。
【００９７】
誤りの推定は、（１つまたは複数の）領域、選択された参照ポイントを含む円もしくは長方形、またはこの領域、円もしくは長方形のサイズである。これは、観測されたビーコンのどれかが観測される地域を囲む、より広範な許容範囲領域を提供する、より堅牢なアルゴリズムの一例である。
【００９８】
離脱したビーコン（例えば、調査結果が取られた後で移動したビーコン）を拒絶するために、観測された各ビーコンを次々に拒絶することができ、次いで上記アルゴリズムを適用することができる。この場合、その結果得られた最も異常な特定位置−例えば、得られた特定位置の重心から最も遠い特定位置を決定することができる。その最も異常な特定位置が実際には全く異常でないというわけでもない限り、対応するビーコンを拒絶することができる。必要に応じて、複数のビーコンを拒絶することができる。次いで、特定位置を、拒絶したビーコンの影響を除去した演算から取ることができる。
【００９９】
信号強度、信号対雑音比、その他を重み係数として含めることにより、堅牢性が改良される。さらに、時間的なデータベースの可変性を考慮することができ、そのアルゴリズムは、移動するビーコンの認識、使用／破棄を目的とすることができる。
【０１００】
使用可能なＧＰＳ特定位置がない場合、ビーコン・ベースの特定場所をＧＰＳシステム内で使用することができる。このビーコン・ベースの特定場所は、ＧＰＳ処理を支援するために、ＧＰＳに場所推定を提供するためにも使用できる。特定位置を提供するために３または４の疑似範囲のような部分的ＧＰＳ結果を強化することができるが、ＧＰＳの部分データは、特定位置を示すには本質的に十分でない。別法として、２つの特定位置（ＧＰＳ特定位置および１つのビーコン・ベースの特定位置で）から１つの洗練された特定位置を導出することができる。
【０１０１】
写真（またはビデオ）に位置情報を関連付けるために、カメラの中で上記の位置決定方法を使用することができる。この写真のジオタギングに対する関心が高まっている。現在、多くの写真には、その撮影場所を知っている撮影者が手動でタグを付けている。他の方法は、カメラ内でローカルに、または記憶されたＩＦデータから後でＧＰＳ位置特定を実行することを伴う。
【０１０２】
画像ファイルまたは写真クリップに場所スタンプを添付するために上記の方法を使用することができるが、ＧＰＳシステムは必要としない。ＧＰＳアンテナおよびＧＰＳ  ＲＦフロントエンドを使用する代わりに、本発明の方法は（ＧＰＳ設備の使用は除外しないが）、ＷｉＦｉアクセス・ポイントおよび／または他のビーコン・ラジオ信号を検出するようカメラを装備することだけを要求する。これにより特定位置を示す別法が提供されることが理解されよう。
【０１０３】
上述のように、ＧＰＳ信号は常に十分な品質を伴うとは限らない。屋内では、壁の厚さと使用される材料（完全に不伝導性の金属）次第で、ＧＰＳ信号は弱いか、またはほとんどないに等しい。一部の信号は、位置特定の品質を低下させる反射経路を介して侵入する場合がある。
【０１０４】
市街地の環境では、上空の見通しが非常に限られている場合があり、十分な衛星が認識できない場合がある。一部の衛星からの信号は、反射により、恐らくはいくつかの経路を介して、存在する場合がある。この全てが、（信頼性のある）位置特定を得る能力を妨げている。しかし、ＧＰＳ位置特定が困難か不可能な場合、ＷｉＦｉアクセス・ポイントからのビーコン信号のようなビーコン信号は豊富にある場合がある。場合によってはＷｉＦｉインターフェースがデジタル・カメラに標準装備されており、その場合は特別なハードウェアは必要とされない。上記で説明した方法を使用すると、特にカメラまたは付属品内で位置特定が実行される場合には、ＧＰＳによる方法と比較してエネルギー消費量を低減することができる。
【０１０５】
すなわち、本発明の一態様では、画像取込み方法は、特定位置で携帯型カメラ装置を使用して画像を取り込むこと、上記特定位置で上記携帯型カメラ装置の検出可能な無線通信装置の識別情報を入手し、それにより識別情報の１つの集合を入手すること、および後続の解析で上記特定位置を決定できるように上記識別情報を画像ファイルに添付することを含む。このカメラは、この目的のためにＷｉｆｉラジオ・インターフェースを有することができる。
【０１０６】
ユーザが写真を撮影している際に、その写真を含む画像ファイルが作成される。ルータのＭＡＣアドレス（任意で他の関連データ）を求めて走査が実行されるが、それらのＭＡＣアドレスは、記憶され、関連する写真の画像ファイルにリンクされる。時刻および日付も記録することができる。
【０１０７】
上記方法は、画像ファイルに添付される位置特定を入手する。この方法は、同じように、ビデオ・クリップおよび独自の識別情報を有する代替ラジオ／マイクロ波ビーコンにも適用可能である。
【０１０８】
上記の一般的な例に関して、ＭＡＣアドレス（および／またはＧＰＳ  ＩＦデータ）の処理は、ローカル・データベースが使用可能な場合にはカメラ内で局所的に実行することができ、データベースが自宅のＰＣにローカルで使用可能な場合にはそのＰＣで実行することができ、またはサーバに接続されていれば自宅のＰＣで実行することができる。そうではなく、その処理は、例えばＷｉＦｉアクセスを使用してサーバに直接的に接続するカメラにより、そのサーバで全体的に遠隔であってもよい。
【０１０９】
ビーコンを求める走査は、ＩＦ  ＧＰＳの捕捉開始と正確に同時刻に実行することができる。一部のビーコンは、ＧＰＳ位置特定の支援として次に有用になる可能性のある、正確なタイミング情報を提供することができる。
【０１１０】
位置情報は、堅牢性を向上させるために共有される場合がある。例えば写真１は、ＧＰＳ特定の提供と、他の場合ならＭＡＣアドレス参照データベースには未知のＭＡＣアドレスの検出とを促すことができる。次の写真２がＧＰＳ特定を入手できないがそのＧＰＳ特定または写真１の同じＭＡＣアドレスの一部を確認する場合は、その処理の中で写真１の情報が支援することができる。既に説明したように、ＭＡＣアドレス参照データベースは写真１からのＭＡＣアドレスで更新できるが、この更新は別の夜間のバッチ処理であってよい。しかし、１人のユーザからの一群の写真を処理する際は、ローカル処理および提供された写真２に関する位置特定で新ＭＡＣアドレスを使用することができる。第１の通過で特定不可能な写真は、他の写真が処理された場合でも再度通過できるので、これは提示される写真の順番に関わらず実施できる。
【０１１１】
図６は、本発明のシステムを示す。携帯型装置６０は、カメラとして示されているが個人ナビゲーション装置（ＰＮＤ）またはラップトップとしても非常に適しており、無線受信機能を有し、送信地域６４ａから６４ｄの４つのＡＰに囲まれている。範囲６４ｂと６４ｄの通信装置は、その位置で携帯型装置により検出可能であり、それらは装置識別情報の１つの集合を形成している。データベースは、本実施例では遠隔サーバ６２として提供されており、参照位置から検出可能な無線通信装置の識別情報を記憶する。サーバは、参照位置の解析と処理に基づいて携帯型装置の位置を決定するために、データベースの内容を使用して識別情報の集合を解析するためのアルゴリズムを実施する。
【０１１２】
本発明は、ビーコン識別情報（および任意の追加データ）が入手され、写真またはビデオと共に記憶される場合に、カメラ（ビデオ・カメラを含めて）で使用するために、車載用ナビゲーション・システムに適用することができる。ジオタグを付けた写真は、次いで地図または衛星写真または地形／建築物モデルで提示することができる。
【０１１３】
この概念は、ユーザが屋内にいるときにそのユーザの位置を決定するために、ＰＣで使用することができる。実際に、本発明は、位置特定が要求されている状況において、ビーコンを検出できる装置であって、アクセス可能なデータベースに対してオブザベーションを処理できる装置をユーザが有するいかなる状況にも適用できる。ユーザは、歩行者、ジョギングする人物などを含むことができる。
【０１１４】
上述のように、ビーコン・ベースの位置決定システムは、衛星ビーコンではなく地上ビーコンを使用する。好適な実施態様はＷｉＦｉノード（すなわち、ＡＰ）のような短距離ビーコンを使用するが、これらのビーコンはいかなる形式であってもよい。一般的に、家庭環境では２００メートルより短い範囲のビーコンが使用され、建築物環境では通常は１００メートルより短い範囲、場合によっては５０メートルより短い範囲のビーコンが使用される。狭い地理的地域では、本発明の照合処理を支援する多くのそのようなビーコンが見つかる場合がある。
【０１１５】
好適な実施態様はそれらの短距離ビーコンを使用するが、本発明の原理は、移動電話セル（セルＩＤ形式の識別情報を有する）、ラジオ／テレビ・マスト信号、ＤＡＢ信号、ＷｉＭａｘ（Ｗｏｒｌｄｗｉｄｅ  Ｉｎｔｅｒｏｐｅｒａｂｉｌｉｔｙ  ｆｏｒ  Ｍｉｃｒｏｗａｖｅ  Ａｃｃｅｓｓ）信号、IEEE 802.15.1信号およびIEEE 802.15.4信号のような他の種類の通信装置に適用することができる。無線通信装置は通常はＲＦ装置だが、ここでも本発明の原理は、ＩＲ信号および音波信号のような他の種類の信号に適用することができる。これらは全て、送信側通信装置に物理的（すなわち、有線）接続を必要とせずに信号が携帯型装置で受信できることを単純に示す「無線」という用語に含まれることを意図している。
【０１１６】
本発明は、別の種類の装置、すなわち上記で概要を述べた別の種類の装置の混合で実施できる。
【０１１７】
当業者には、様々な変形形態が明らかになろう。
【図１】
0005746020.tif 000002
【図２】
0005746020.tif 000003
【図３】
0005746020.tif 000004
【図４】
0005746020.tif 000005
【図５】
0005746020.tif 000006
【図６】
0005746020.tif 000007