略図を用いた建物用の経路案内グラフ
本明細書で開示される主題は、比較的詳細度が低い略図を含みうる建物情報に少なくとも一部基づいて、経路案内グラフを作成するための、システム、方法などに関する。いくつかの例示的な実装形態では、方法は、建物構造の少なくとも一部を表す建物情報を得るステップと、点のグリッドを建物情報に重畳するステップとを含みうる。建物情報は、重畳された点のグリッドの複数の点から複数の線を投射することによって、重畳された点のグリッドを用いて分析されうる。少なくとも1つの経路案内グラフが、分析に応じて、かつ、重畳された点のグリッドと建物情報とに少なくとも一部基づいて、作成されうる。他の例示的な実装形態が、本明細書で説明される。
【発明の詳細な説明】
【技術分野】
【０００１】
米国特許法第119条による優先権の主張
この米国特許本出願は、2009年10月1日に出願された、AUTOMATIC ROUTING TOPOLOGY EXTRACTION FROM LOW DETAIL SCHEMATICSという表題の、米国特許仮出願第61/247869号と、2009年10月1日に出願された、SYSTEM FOR INDOOR LOCATIONという表題の米国特許仮出願第61/247865号と、2009年10月1日に出願された、AUTOMATIC ROUTING TOPOLOGY EXTRACTION FROM CAD MAPSという表題の米国特許仮出願第61/247866号と、2010年1月22日に出願された、MAP ACQUISITION AND PROCESSING FOR LOCATION BASED SERVICESという表題の米国特許仮出願第61/297524号との利益を主張するものであり、これらの仮出願の各々が、本出願の譲受人に譲渡され、参照によって本明細書に明示的に組み込まれる。
【０００２】
関連出願の参照
本特許出願は、本出願と同時に出願され、代理人整理番号第100013号の、KhorashadiらによるROUTING GRAPHS FOR BUILDINGSという同時係属中の米国特許出願に関連し、上記の同時係属中の特許出願は本出願の譲受人に譲渡され、参照によって本明細書に明示的に組み込まれる。
【０００３】
本明細書で開示される主題は、比較的詳細度が低い略図を含みうる建物情報に少なくとも一部基づいて、経路案内グラフを作成することに関する。
【背景技術】
【０００４】
地図は、20世紀中に電子的形態で利用可能になり始めた。インターネットの出現により、基本的に世界中のあらゆる場所の地図に、最終的にはアクセスすることができる。ウェブ上の地図サービスは、地点「A」から地点「B」への案内を提供することもできる。これらのウェブ上での地図案内は、比較的静的である。しかし、衛星測位システム(SPS)技術およびさらに小型の電子機器の発明により、いわゆるターンバイターンの案内を、人々が自分の目的地に向かって移動するにつれて動的に提供することができる。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
残念ながら、これらの電子地図およびウェブ上の地図サービスは、ある住所から別の住所への案内のように、屋外で案内を提供することを目的としている。同様に、従来は、ターンバイターンの案内は道路上に限られている。今のところ、屋内で同様の地図および案内サービスを提供する能力が欠けている。
【課題を解決するための手段】
【０００６】
ある例示的な実装形態では、方法は、建物構造の少なくとも一部を表現する建物情報を得るステップと、点のグリッドを建物情報に重畳するステップとを含みうる。建物情報は、重畳された点のグリッドの複数の点から複数の線を投射することによって、重畳された点のグリッドを用いて分析されうる。少なくとも1つの経路案内グラフが、分析に応じて、かつ、重畳された点のグリッドと建物情報とに少なくとも一部基づいて、作成されうる。しかし、これは例示的な実装形態に過ぎず、他の実装形態が本明細書で説明され、特許請求される主題から外れることなく実装されうることを、理解されたい。
【０００７】
非限定的かつ非網羅的な態様、特徴などが、以下の図面を参照して説明され、様々な図面全体で、同様の番号は同様の部分を指す。
【図面の簡単な説明】
【０００８】
【図１】ある実装形態による、注記情報を有する例示的な建物情報の概略図である。
【図２】ある実装形態による、注記情報への関連付けを含む例示的な経路案内グラフが作成された、建物情報の概略図である。
【図３】ある実装形態による、建物情報および建物道案内ファイルの例を示すブロック図である。
【図４】ある実装形態による、例示的な建物情報の概略図である。
【図５】ある実装形態による、例示的な点のグリッドが重畳された、建物情報の概略図である。
【図６】ある実装形態による、建物情報に少なくとも一部基づいて経路案内グラフを作成するための例示的な方法を示す、流れ図である。
【図７】ある実装形態による、建物情報を分析して経路案内グラフを作成するための例示的な方法を示す、流れ図である。
【図８】建物の廊下と建物の外側を区別するのが困難な、起こりうる例を示す図である。
【図９】ある実装形態による、点のグリッドが重畳された、例示的な建物の部分の概略図である。
【図１０】ある実装形態による、建物の情報の概略図に対して線を投射するための例示的な機構を示す図である。
【図１１】ある実装形態による、点が外部の点であるか内部の点であるかを投射された線を用いて判定する例示的な手法の、概略図である。
【図１２】ある実装形態による、点が外部の点であるか内部の点であるかを投射された線を用いて判定するための例示的な方法を示す、流れ図である。
【図１３】ある実装形態による、複数の独立の領域を形成するように障害のない接続によって相互接続される隣接点の例を示す、概略図である。
【図１４】ある実装形態による、独立の領域の広がりに基づいて廊下を発見する例示的な手法の、概略図である。
【図１５】ある実装形態による、独立の領域の広がりに基づいて廊下を発見するための例示的な方法の、流れ図である。
【図１６】ある実装形態による、どの独立の領域が使用可能か、かつ使用不可能な独立の領域があるかどうかを判定する例示的な手法の概略図である。
【図１７】ある実装形態による、建物情報を分析することにより識別されうる建物構造の例示的な態様を示す、概略図である。
【図１８】ある実装形態による、使用可能な独立の領域の入口/出口の点を決定する例示的な手法の、概略図である。
【図１９】ある実装形態による、使用可能な独立の領域の入口/出口の点を決定するための例示的な方法の、流れ図である。
【図２０】略図を用いる建物用の経路案内グラフの1つまたは複数の態様を実施することができる、ある実装形態による、例示的な機器を示す概略図である。
【発明を実施するための形態】
【０００９】
本明細書全体における、「ある特徴」、「1つの特徴」、「ある例」、「一例」などへの言及は、特徴および/または例とともに説明される、具体的な特徴、構造、特性などが、特許請求される主題の少なくとも1つの特徴および/または例に関連するということを意味する。したがって、本明細書の様々な箇所における、「一例では」、「ある例」、「1つの特徴として」、「ある特徴」、「ある例示的な実装形態では」、「いくつかの例示的な実装形態では」などのような語句の使用は、全てが同じ特徴、例、および/または例示的な実装形態を指すとは限らない。さらに、具体的な特徴、例、構造、特性などは、1つまたは複数の例示的な実装形態、例示的なシステムなどに組み合わされうる。
【００１０】
上で示されたように、2点間の案内およびターンバイターンの案内は、通常屋外の環境において、特に画定された道路のある環境で利用可能である。一方、建物の内部では、通常、同様の地図または道案内の機能は提供されない。屋内での道案内を実現するために、ユーザーが現在位置している環境の地図が用いられうる。しかし、地図だけでは屋内での道案内には不十分であることがある。ユーザーを地図上のある地点から別の地点へ道案内するのを支援するために、グラフおよび関連する注記レイヤが用いられうる。そのようなグラフは、一般に経路案内グラフと呼ばれる。
【００１１】
関連する注記情報を有する経路案内グラフは、所与の地図の使用可能な領域を表すことができ、ある点から別の点への通行がどのように可能かを示すことができる。任意の所与の建物について、経路案内グラフは、使用可能な領域および建物内のある点から別の点への通行可能な経路を示す、ノードおよびエッジのセットを含みうる。残念ながら、関連付けられた注記情報を有するそのような経路案内グラフは、建物構造の略図から直接は得られない。そのような略図は、必ずしも限定はされないが、比較的詳細度が低い略図を含みうる。屋内の位置情報サービス(LBS)のエコシステムに対しては、手動で経路案内地図を描き、具体的な屋内の場所の要素を識別することは、豊富な情報を有する数百万の建物構造を追加するのにスケーラブルな方法ではない。
【００１２】
本明細書で説明されるいくつかの例示的な実装形態では、方法は、既存の建物の略図を調査するステップと、その建物の略図から抽出される情報に少なくとも一部基づいて、経路案内グラフを作成するステップとを伴いうる。例示的な経路案内グラフの作成処理は、関連するPoint of Interest(POI)情報を有する建物の略図を含む、多くの建物の略図に共通の既存の要素を用いて、自動的に実行されうる。そのような概略的な地図の分析から、関連する注記情報を有する強力な経路案内グラフが生成されうる。そのようなグラフの生成は、例えば、(i)廊下と部屋を区別するために、また(ii)部屋と廊下の間を接続するもの(例えば出入口など)の可能性の高い位置を決定するために、接続グラフの分析を含みうる。経路案内グラフを用いて、屋内での測位および/または道案内情報がユーザー(例えば、ユーザーのモバイル機器)に提供されうる。
【００１３】
図1は、ある実装形態による、注記情報102を有する例示的な建物情報の概略図100である。ある例示的な実装形態では、概略図100は、建物の少なくとも一部を表しうる。その外観は、いくつか例を挙げると、線、曲線、円弧、多角形、他の閉じた形状などを含みうる。これらの項目は、建物構造の具体的な要素を表すように定義されうる。
【００１４】
例示的な建物の要素は、限定はされないが、壁、扉、柱、部屋、仕切り、小部屋の壁などを含む。そのような建物の要素は、移動を制限する障害物を含んでもよく、その障害物は永続的なものであっても一時的なものであってもよい。示されるように、概略図100は、いくつか例を挙げると、注記情報102と、線で表される壁と、多角形で表される部屋と、これらの組み合わせなどを含みうる。図1の例に示されるように、12個の部屋が、12個の多角形および/または多くの線から形成されうる。明瞭にするために、1項目の注記情報のみが図1の参照番号「102」により明示的に示されているが、概略図100には、11項目の注記情報が比較的大きなベタの円により示されている。
【００１５】
概略図100は、外側の壁、内側の壁、部屋、廊下、内側の扉、外側の扉、柱などを含みうる。しかし、壁、廊下、扉の種類などは通常、建物地図ファイルでは明示的には識別されない。人間はそのような建物の要素を容易に識別できうるが、機械は通常そのような能力をもたない。本明細書で説明されるようないくつかの例示的な実装形態は、少なくともいくつかの建物構造を、1つまたは複数の機械的なデバイスにより識別することを可能にする。
【００１６】
さらに、建物情報ファイルは、比較的詳細度が低い略図を含んでもよい。そのような詳細度の低い略図が含む情報および/または要素は、比較的詳細度の高いコンピュータ支援設計(CAD)ファイルで見出されうる情報および/または要素よりも少ないことがある。限定ではなく例として、比較的詳細度が低い略図は、モールの画像または空港の地図、コンベンションセンターのような動的な場所の利用可能なCAD図などを含みうる。そのような略図は、いくつか例を挙げると、店、部屋、ターミナル/ゲート、展示物などのようなPoint of Interest(POI)を示す、閉じた多角形を、建物の外周に加えて有することが多い。必ずしも全てではないが、比較的詳細度が低い略図の多くが、扉の表示を欠いていることもある。言い換えると、比較的詳細度が低い略図では、内側の扉、外側の扉、または内側の扉と外側の扉の両方が明示的に示されていないことがあり、または、表されていないこともある。
【００１７】
機械が具体的な建物の要素を識別したとしても、機械が支援する道案内は必ずしも可能にはならないことがあることを理解されたい。例えば、ある人が、概略図100の地点#1(第1の比較的小さなベタの円)から地点#2(第2の比較的小さなベタの円)まで移動しようとすることがある。道案内指示を提供できるようにするために、概略図100に対応する建物構造のために経路案内グラフが作成されうる。ユーザーが、具体的な部屋番号、使用者、名付けられた場所、店、展示物、建物のサービスなどへの案内を求めることができるようにされる場合、注記情報が接続グラフと関連付けられ、そのような経路案内グラフを作成することができる。例示的な経路案内グラフおよび注記情報は、図2を特に参照して本明細書で以下でさらに説明される。
【００１８】
いくつかの例示的な実装形態では、対象の建物構造の、画像による地図、多角形による地図、または別の概略的な地図が利用可能でありうる。屋内での道案内は、地図の抽出および補間を用いて可能になりうる。地図の抽出により、概略的な地図に存在する地図情報は、いくつか例を挙げると、経路案内、位置決め、位置フィルタリング、道案内、インセンティブアプリケーション、検索などのような屋内での位置情報サービスを可能にする、よりアクセスしやすい情報に変換されうる。この変換において、略図ファイルで表されるような物理的な地図の特性が操作され、経路案内モジュールにより利用されうる構造に変換されうる。加えて、そのような抽出処理および変換処理は、自動化された方式で、および/または自動的に行われうる。実際には、地図の抽出および変換には、ユーザーは最小限しか関わらないか全く関わらない。さらに、そのような処理は、1つの地図につき数分程度で、またはさらに高速に完了しうる。
【００１９】
いくつかの例示的な実装形態の例示的な動作が、以下で説明される。以下の動作のいずれも、自動化することができる。以下の動作は、異なる順序で実行されてもよく、かつ/または完全にもしくは一部重複して実行されてもよい。さらに、所与の実装形態は、そのような動作の一部を利用することができる。第1に、点のグリッドが、建物構造に対応する概略図に重畳されうる。第2に、重畳された点のグリッドの複数の点から、線が投射されうる。第3に、投射された線に基づいて、重畳された点のグリッドの点が、内側の点または外側の点であるものと判定されうる。第4に、重畳された点のグリッドの隣接点が、障害のない接続で相互接続され、複数の独立の領域を決定しうる。したがって、全般的に地図の独立の領域が識別されうる。個々の独立の領域は、使用可能な独立の領域または使用不可能な独立の領域を含みうる。また、経路案内の仕組みが、所与の店、展示物、または他の「部屋」の境界を識別することによって、容易になりうる。
【００２０】
第5に、建物構造の外側の領域に対応する独立の領域が、確定されうる。建物の外側の領域(例えば、内側領域に対する)を識別することで、次に位置決め技術を組み込むことを容易にし、地図領域内でのユーザーの位置決めを改善することができる。第6に、独立の領域の広がりに少なくとも一部基づいて、廊下が発見されうる。第7に、POIのような建物の注記情報が、独立の領域に重ねられうる。図2に例として示されるように、部屋は、居住者または目的、さらには部屋の名前もしくは他の標識により、標識されうる。第8に、どの独立の領域が使用可能か、および使用不可能な独立の領域があるかどうかが、判定されうる。使用可能な領域は、ユーザーにより通行可能であると考えることができる。
【００２１】
第9に、対応するPOIまたは他の注記情報を有する独立の領域の、入口/出口点が識別されうる。シームレスな屋内での経路案内と、屋内から屋外への経路案内とを両方、より良く実現するために、全体の建物構造に対する入口の点および出口の点を、発見された廊下および外側の点に関して識別することもでき、経路案内グラフの一部として含んでもよく、または経路案内グラフと関連付けてもよい。加えて、緊急時行動および避難計画のためのアプリケーションは、そのような建物の入口および出口の点を利用することができる。第10に、複数の場所を一緒に結び、経路案内アプリケーションを動作させる経路案内グラフが、作成されうる。第11に、そのような決定された入口/出口の点を用いて、あるPOIから別のPOIへの道案内指示が、経路案内グラフを用いて提供されうる。
【００２２】
図2は、ある実装形態による、注記情報208への関連付けを含む例示的な経路案内グラフ206が作成された、建物情報の概略図200である。示されるように、概略図200は、少なくとも1つの使用可能な領域202、建物の外側の領域204、経路案内グラフ206、および注記情報208を含みうる。経路案内グラフ206を用いて、案内アプリケーションおよび/またはシステムは、例えば地点#1から地点#2へ移動するための道案内指示を、個人に提供することができる。
【００２３】
視覚的に明瞭にするために、いくつかの特定の例示される要素は、図2において参照番号により明示的には示されていないが、説明文が、どの特定の建物の要素がどの特定の描画上の要素により示されているかを示す。また、概略図200および経路案内グラフ206は、図2において示され本明細書で以下に示されるようないくつかの例示的な構成要素を含むが、特許請求される主題はそのようには限定されない。代わりに、所与の実装形態は、より多くの、より少ない、かつ/または異なる構成要素を含んでもよい。概略図200は、例えば、自動車産業展示会が開催中のコンベンションセンターに対応しうる。
【００２４】
いくつかの例示的な実装形態では、経路案内のトポロジーを示す経路案内グラフ206が、概略図200の建物構造に対応するように作成されうる。建物情報の例示的な分析の一部として、独立の領域が決定されうる。独立の領域は、いくつか例を挙げると、部屋、廊下、建物の外側などを含みうる。少なくとも1つの独立の領域が、建物の外側の領域204を含むものと確定されうる。1つまたは複数の別の独立の領域は、使用不可能な領域202を含むものと判定されうる。個人が立ち入ることのできる独立の領域は、使用可能な領域(例えば、入室可能な部屋、廊下など)を含むものと判定されうる。本明細書で用いられる場合、「部屋」(またはより一般的には区域)は、いくつか例を挙げると、オフィス、小部屋、休憩室、店舗、売店、フードコート、アパート/コンドミニアム、ブース、展示物、空港のゲート、アトラクション、他の定義可能な区域、およびこれらの組み合わせなどを含みうる。
【００２５】
注記情報208は、経路案内グラフ206と関連付けられ、異なる領域(例えば部屋、区域など)の間での道案内サービスまたは他の位置情報サービスをさらに実現することができる。限定ではなく例として、注記情報208は、部屋の指定(例えば部屋「A」、「1.24」など)、部屋の名前(例えば「取引部門」、「情報ブース」など)、部屋の目的(例えば「休憩室」、「食事」、「厨房」など)、部屋の居住者または使用者(例えば「ある大企業」、「工具」、「小型装置」、「空室」など)を含みうる。注記情報208は、いくつか例を挙げると、ロビー、フードコート、駐車場、ターミナルなどのような特定の区域と関連する情報を提供することもできる。経路案内グラフ206は、ある注記された領域から別の注記された領域への経路を含む、ある地点から別の地点への経路を描くのに用いることができる。単なる例として、道案内指示は、「ある大企業」の部屋「A」の近くの地点#1から「休憩室」の近くの地点#2までの案内とともに、ユーザーに(例えばモバイル機器を介して)提供されうる。
【００２６】
図3は、ある実装形態による、建物情報302および建物道案内ファイル308の例を示す、ブロック図300である。いくつかの例示的な実装形態では、建物情報302は、建物構造の少なくとも一部を表現する、任意の情報のセットを含んでもよい。建物情報302に少なくとも一部基づいて、建物道案内ファイル308が作成されうる。建物道案内ファイル308は、少なくとも1つの経路案内グラフ312、注記情報314、および/または1つもしくは複数の接続グラフ316を含みうる。経路案内グラフ312は、注記情報314に関連付けられ、かつ/または注記情報314と連携しうる。建物情報302、建物道案内ファイル308などは、電気信号(例えばデジタル信号)として実現されうる。
【００２７】
例として、建物情報302は、少なくとも1つの建物地図ファイル304を含みうる。建物地図ファイル304は、建物構造の少なくとも一部を表すデータ306(例えば、画像、CADフォーマット、DXFフォーマット、これらの何らかの組み合わせなど)を含みうる。建物情報302は、建物道案内ファイル308を作成する処理の前に、かつ/またはその間に、任意の1つまたは複数のフォーマットで表現されうる。例えば、建物道案内ファイル308の第1の部分は、建物情報302が第1のフォーマットにあるときに作成することができ、建物道案内ファイル308の第2の部分は、建物情報302が第2のフォーマットにあるときに作成することができる。建物情報302から、建物構造データ306が、建物道案内ファイル308を作成する(310)ように、抽出および/または変換されうる。
【００２８】
建物地図ファイル304および/またはそのデータ306は、注記情報も含みうる。そのような注記情報は、1つまたは複数のレイヤに編成されうる。地図ファイル中のどの注記レイヤまたは(もしあれば)複数の注記レイヤが、作製された経路案内グラフと関連付けられることになる注記レイヤであるかを識別するのに、使用者との対話が用いられうる。例えば、部屋の名前を関連付けることを望む場合、使用者が、そのようなレイヤの標識を選択または特定することができる。そのようなレイヤ(例えば「部屋レイヤ」、「Point of Interest」など)は、地図ファイルの中で別々に標識されうる。あるいは、注記レイヤの選択は、いくつか例を挙げると、自動的に行われてもよく、1つまたは複数の規則にしたがって自動化されてもよく、これらの組み合わせなどであってもよい。さらに、または代替的に、注記情報は、建物の要素の表現を含む「レイヤ」の一部を含みうる。
【００２９】
ある例示的な実装形態では、建物地図ファイル304は、1つまたは複数の建物構造の少なくとも一部に対応しうる。そのような建物構造の例は、限定はされないが、スタジアム、アリーナ、コンベンションセンター、モール、トンネルまたは橋または廊下などで接続された建物の集合体、空港、オフィスビル(壁/仕切りで再配置可能なものを含む)、これらの組み合わせなどを含む。建物地図ファイル304は、任意のフォーマットであってよい。例示的なフォーマットは、限定はされないが、CAD描画フォーマット(例えば、会場または施設の所有者により提供されるような)、Vectorフォーマット、画像フォーマット、これらの組み合わせなどを含む。画像フォーマットについては、エッジ検出処理がそのような地図画像に対して実行されうる。画像フォーマットは、いくつか例を挙げると、ウェブサイトから、(例えばモールの案内板、空港などの)表示された地図の写真を撮影するカメラ(例えばカメラ付き電話)から、印刷された地図をスキャンすることによって、インターネット上で示されている画像をコピーすることによって、または他の方法で、得ることができる。しかし、建物情報302も特許請求される主題も、これらの具体的な例には限定されない。
【００３０】
上述のように、建物の少なくとも一部の構造情報が、建物情報302から抽出されうる。そのような情報は、いくつか例を挙げると、壁、柱、障害物などに関連しうる。しかし、例えば、ある特定の壁が「POI A」の壁であることを示す情報、または所与の部屋が入口/出口の点を有することを示す情報は、存在しないことがある。それでも、建物の要素の情報を処理することができ、他の注記情報は抽出された情報から推測されうる。例えば、ある特定の部屋(例えば「部屋A」)の境界ボックスを識別するために、POI情報が建物地図ファイル304から抽出されうる。POI情報は、空間中の1つまたは複数の座標点(例えば、ドットに基づく地点、1つまたは複数の語に基づく領域、これらの組み合わせなど)が「POI A」を特定することを示しうる。そのようなPOI情報を用いて、例えば、これらの座標点に関連する最小の閉じた領域または独立の領域が、経路案内の目的で決定され、「POI A」と標識されうる。注記情報を関連付けるこの処理の例示的な手法が、図16および17を特に参照して本明細書において以下でさらに説明される。
【００３１】
図4は、ある実装形態による、例示的な建物情報400の概略図である。建物情報400は、(図3の)建物情報302の例であってよい。したがって、建物情報400は、図3を特に参照して上で説明されるフォーマットのいずれか、または他の種類のフォーマットとともに、機能することができる。いくつかの例示的な実装形態では、建物情報400は、1つまたは複数の建物の要素を表す構成要素402を含みうる。
【００３２】
示されるように、建物情報400は、(線で示されるような)壁402aおよび/または(多角形で示されるような)区域402bという、少なくとも2種類の構成要素402を含みうる。さらに、建物の要素を表す、より少ない、より多くの、かつ/または異なる構成要素402が、建物情報400の一部として代替的に含まれてもよい。建物情報400は、注記情報404も含みうる。図5から、そのような建物構造の一部を表す建物情報400を用いて例示的な概念を示す。
【００３３】
図5は、ある実装形態による、例示的な点のグリッド502が重畳された、建物情報400の概略図500である。したがって、示されるように、概略図500は、建物情報400および点のグリッド502を含みうる。いくつかの例示的な実装形態では、点のグリッド502は、建物情報400に重畳されうる。限定ではなく例として、点のグリッド502は、2つの軸(例えばx軸およびy軸)に沿って一定の間隔で位置する点のセットであってよい。点のグリッド502は、建物情報400の建物構造の、一部、実質的に全て、全て、または全てよりも広い範囲をカバーしてもよい。示されるように、点のグリッド502は、建物情報400の建物構造の外側の境界を超えて延びる。
【００３４】
点のグリッドの分解能または縮尺(例えば、2つの隣接点の間隔)は、変化してもよい。例えば、分解能は、いくつか例を挙げると、位置情報サービスで求められる正確さのレベル(例えば道案内の地図の正確さ)、建物情報の分析を分担しうるリソース(例えばメモリ、処理、および/または時間)の使用可能な量、部屋または他の独立の領域の実際のサイズもしくは予測されるサイズなどに基づいて、変化しうる。縮尺も、単一の建物構造における異なる所望の分解能のレベルに対応するように、単一の点のグリッドにおいて変化しうる。
【００３５】
点のグリッド502を重畳するための、建物構造の「グリッド化」を、任意の場所または地点で開始することができる。グリッド化は、建物または建物の階の全てを含む、建物構造の所望の部分の全体がカバーされるまで、ある地点から始めて、複数の方向に例えば(1フィート間隔のように)一定の間隔で点を追加することで、達成されうる。建物情報の建物構造の周り(例えば建物構造の北、南、東、西)の最大の領域が、(図3の)建物地図ファイル304から抽出される任意の構成要素402(例えば、(図4の)線402a、多角形402b、注記構成要素など)のx座標とy座標の両方の最小値および最大値を決めることによって、決定されうる。
【００３６】
図6は、ある実装形態による、建物情報に少なくとも一部基づいて、経路案内グラフを作成するための例示的な方法を示す、流れ図600である。示されるように、流れ図600は、4つの動作ブロック602、604、606、および608を含みうる。動作602〜608は特定の順序で示され説明されるが、特許請求される主題から逸脱することなく、方法は代替的な方式で実行されうることを理解されたい。また、流れ図600の動作は、互いに完全にまたは一部重複して実行されてもよい。加えて、以下の説明は、いくつかの他の図(例えば図3〜5)で示される具体的な態様および特徴に言及するが、方法は他の態様および/または特徴とともに実行されてもよい。
【００３７】
いくつかの例示的な実装形態では、動作602において、建物構造の少なくとも一部を表現する建物情報が取得されうる。例えば、(例えば、建物情報400として図4で示されるような)建物構造の少なくとも一部を表現する建物情報302が取得されうる。(例えばデジタル信号のような)建物情報302は、いくつか例を挙げると、メモリから取り出すことによって、無線通信リンクまたは有線通信リンクを介して受信することによって、画像の地図を(例えばカメラレンズ、センサなどを介して)得ることによって、または他の方法で、取得することができる。動作604において、点のグリッドが建物情報に重畳されうる。例えば、点のグリッド502が、建物情報400に重畳されうる。
【００３８】
動作606において、建物情報が、複数の点から線を投射することによって、重畳された点のグリッドを用いて分析されうる。例えば、建物情報400は、点のグリッド502の複数の点から線を投射することによって、重畳された点のグリッド502を用いて分析(例えば、試験、検査、研究、調査、処理など)されうる。例えば、(例えば構成要素402により表されるような)建物の要素に対する投射された線による1つまたは複数の衝突が検出されうる。例えば、そのような1つまたは複数の衝突に少なくとも一部基づいて、複数の点のうちの点が、外側の点に対応するか内側の点に対応するかが判定されうる。また、複数の独立の領域について、少なくとも1つの入口/出口の点が、そのような1つまたは複数の衝突に少なくとも一部基づいて、決定されうる。線を投射する例示的な実装形態が、図10、11、12、18、および19を特に参照して、以下でさらに説明される。
【００３９】
一般に、点のグリッド502を用いる建物情報400の分析により、いくつか例を挙げると、独立の領域を決定し、少なくとも1つの外側の領域に対する内側の領域を突き止め、使用不可能な独立の領域に対する使用可能な独立の領域を決定し、廊下を(例えば干渉を介して)発見することなどが可能になりうる。そのような分析の間、点のグリッドの隣接点が相互接続されて、接続グラフ316を形成することができる。点のグリッドを用いて建物情報を分析する例示的な手法が、図7を特に参照して本明細書において以下でさらに説明される。
【００４０】
動作608において、上記の分析に応じて経路案内グラフを作成することができ、経路案内グラフは、重畳された点のグリッドおよび建物情報に少なくとも一部基づきうる(例えば、少なくとも1つの経路案内グラフを表す電気信号(例えばデジタル信号)が生成されうる)。例えば、注記情報314への関連付けを有する経路案内グラフ312を、点のグリッド502に少なくとも一部基づき、かつ動作606の少なくとも一部に応じて、建物情報400の少なくとも一部のために作成することができる。例示的な実装形態では、経路案内グラフ312は、ある場所から別の場所への(例えば、あるPOIから別のPOIへの)経路を決定するために用いられうる。
【００４１】
そのような経路案内グラフは、同じ機器または異なる機器において次に使用するために(例えばデジタル信号を介して)保存されてもよく、かつ/または、作成された後すぐに、もしくは実質的にすぐに使用されてもよい。例えば、経路案内グラフのデータベースは、次に取り出すために、かつ位置情報サービスに対して次に適用するために、保存されうる。あるいは、機器(例えばモバイル機器)が経路案内グラフを作成し、オンデマンドで、道案内または他の位置情報アプリケーションのために経路案内グラフを使用してもよい。いずれにしても、建物構造に関連する道案内情報(例えば、方向、完全なまたは部分的な経路案内グラフなど)を、少なくとも1つの経路案内グラフを用いてモバイル機器に提供することができる。
【００４２】
図7は、ある実装形態による、建物情報を分析して経路案内グラフを作成するための、例示的な方法を示す流れ図700である。示されるように、流れ図700は、9個の動作ブロック702〜718を含みうる。動作702〜718は特定の順序で示され説明されるが、特許請求される主題から逸脱することなく、方法は代替の方式で実行されうることを理解されたい。また、流れ図700の動作は、互いに完全にまたは一部重複して実行されてもよい。加えて、以下の説明は、いくつかの他の図(例えば図3〜5および図9〜19)で示される具体的な態様および特徴に言及するが、方法は他の態様および/または特徴とともに実行されてもよい。
【００４３】
いくつかの例示的な実装形態では、動作702において、点が建物構造に対して外部の点であるか内部の点であるかが、投射された線に基づいて判定されうる。例えば、点のグリッド502の点が、建物情報400の建物構造に対して外部の点に相当するか内部の点に相当するかが、投射された線に基づいて判定されうる。線を投射するための例示的な機構が、図10を特に参照して本明細書において以下で説明される。動作702のための例示的な実装形態が、図11および12を特に参照して本明細書において以下でさらに説明される。
【００４４】
動作704において、グリッドの点の隣接点が、障害のない接続により相互接続され、少なくとも1つの接続グラフを形成することができる。例えば、接続が建物の要素と交差しない場合、点のグリッド502の所与の点から、所与の点と最大8個の近接する点との間に接続が確立されうる。(例えば閉じた形状および外側の点との接続が認められていない内側の点から)区域が形成される場合、そのような相互接続は、互いに接続されていない複数の接続グラフを形成することができる。
【００４５】
動作706において、複数の独立の領域が決定されうる。例えば、複数の独立の領域を、隣接点を障害のない接続によって相互接続することで形成される、複数の互いに接続されていない接続グラフに少なくとも一部基づいて、決定することができる。動作708において、建物構造の外側の少なくとも1つの独立の領域を、確定することができる。例えば、外側の点を含むものとして識別される少なくとも1つの点を用いて(例えば動作702で判定可能なように)、外側の独立の領域を確定することができる。動作704〜708の例示的な実装形態が、図13を特に参照して本明細書において以下でさらに説明される。
【００４６】
動作710において、1つまたは複数の廊下が、独立の領域の広がりに基づいて発見されうる。例えば、少なくとも1つの廊下は、決定された独立の領域に対応する1つまたは複数の広がりおよび少なくとも1つの所定の閾値に、少なくとも一部基づいて、建物情報400の一部として発見されうる。動作710の例示的な実装形態は、図14および15を特に参照して本明細書で以下にさらに説明される。
【００４７】
動作712において、建物の注記情報が、独立の領域に重畳されうる。例えば、注記情報404を独立の領域上に重畳することができ、独立の領域は、経路案内グラフを作成するための、障害のない接続により相互接続される点から形成される互いに接続されていない複数の接続グラフを含みうる。したがって、注記情報314は、経路案内グラフ312に関連付けられうる。動作712の例示的な実装形態は、図16および17を特に参照して、本明細書において以下でさらに説明される。
【００４８】
動作714において、どの独立の領域が使用可能か、および使用不可能な独立の領域があるかどうかが、注記情報(例えばPOI情報)に少なくとも一部基づいて判定されうる。例えば、注記情報を有するPOIに対応する独立の領域は、使用可能な独立の領域を含むと考えることができる。動作714の例示的な実装形態はまた、図16および17を特に参照して、本明細書において以下でさらに説明される。
【００４９】
動作716において、使用可能な独立の領域の入口/出口の点および、それらの対応する注記情報(例えばPoint of Interest)が、投射された線および発見された廊下に基づいて決定されうる。例えば、使用可能な独立の領域の入口/出口の1つまたは複数の点は、対応するPoint of Interestおよび、そこから投射される線がどのように廊下に到達するか(例えば、廊下に到達する前に複数の建物の要素に衝突するかどうか)に少なくとも一部基づいて、決定されうる。動作716の例示的な実装形態は、図18および19を特に参照して、本明細書において以下でさらに説明される。
【００５０】
動作718において、POIへの道案内指示および/またはPOIからの道案内指示が、少なくとも1つの経路案内グラフを用いて、入口/出口の点に少なくとも一部基づいて提供されうる。例えば、第1の地点から指定されたPOIまでの、ターンバイターンまたは他の道案内指示が、指定されたPOIに対応するように決定された1つまたは複数の入口/出口の点に少なくとも一部基づく少なくとも1つの経路案内グラフを用いて、提供されうる。
【００５１】
図8は、建物の廊下と建物の外側を区別するのが困難な、起こりうる例を示す図800である。示されるように、図800は、黒い領域802および複数の区域804を含み、明瞭にするために、これらのうちの一部のみが明示的に示されている。(図4の)建物情報400も参照すると、区域804が閉じた多角形から形成されることは明らかである。機械には、そのような閉じた多角形が全て使用不可能な領域であるように誤って見える可能性がある。廊下と建物の外側の間には、明確に画定された境界が存在しないことも、明らかである。そのような状況の結果、黒い領域802により示されるように、建物の廊下が、建物構造の外側の領域に「流出する」ことがある。
【００５２】
この可能性のある流出は、点のグリッドのうちのどの点が内側の点に相当し、点のグリッドのうちのどの点が外側の点に相当するかを判定することにより、少なくとも部分的に対処されうる。したがって、建物の内側と建物の外側の間(例えば、建物の廊下と建物の外側の領域の間)の境界が確立されうる。内側の点と外側の点を決定する例示的な手法が、図11〜13を特に参照して、本明細書において以下で説明される。
【００５３】
図9は、ある実装形態による、点のグリッド502が重畳された例示的な建物の部分900の概略図である。明瞭にするために示されているように、建物の部分900は、(図4の)建物情報400の一部(例えば断面)である。建物の部分900は、図9、ならびに図11、13、16および18において、さらに詳細に示すために拡大されている。図11、13、16および18は、全般に、建物の部分900を用いる異なる態様および/または実装形態を示す。図9において、建物の部分900は、壁402aおよび区域402bのような、構成要素402を含む。図9には示されていないが、廊下の「上側」部分をさらに画定する追加の壁の構成要素が、図18において示されている。
【００５４】
図10は、ある実装形態による、建物の情報の概略図に対して線を投射するための例示的な機構1000を示す。示されるように、機構1000は、点1004から投射される8つの線1002を含みうる。(開始点で互いに隣接する2つの線は、実質的に幾何学的な線を形成することに留意されたい。したがって、代替的におよび/または等価的に、8つの線1002を含む機構1000は、4つの幾何学的な線を含むと考えられうる。)点1004は、(例えば図5および9の)点のグリッド502の任意の所与の点に対応しうる。
【００５５】
いくつかの例示的な実装形態では、機構1000が、点のグリッドの複数の点において用いられ、建物情報を分析することができる。動作中、機構1000の少なくとも1つの線1002が、点1004から投射される。例えば、線1002は、(例えば、建物情報の外側の境界、所与の地図画像、または重畳された点のグリッドにおいて)線が1つまたは複数の建物の要素に1回または複数回衝突するまで、投射されうる。建物情報の態様を、そのような衝突および/または衝突が発生しないことに少なくとも一部基づいて、推測することができ、または判定することができる。図11を特に参照することを含めて、例が本明細書において以下でさらに説明される。
【００５６】
8つの線1002が機構1000について示されているが、これは例に過ぎない。そのような機構1000は、特許請求される主題から逸脱することなく、代替的に、より多くの線またはより少ない線1002を含んでもよい。図10で示されるように、機構1000の各線1002は、両方の最も近くの線1002から45度離れている。しかし、この45度の離隔は、例に過ぎない。より多くの線またはより少ない線1002が利用される場合、(例えば、任意の2つの近接する線1002の間の間隔を等しく保つように)最も近くの線1002との間の分離角は変更されうる。さらに、任意の2つの最も近くの線の間の分離角は、特許請求される主題から外れることなく、単一の機構1000内で異なっていてもよい(例えば、単一の機構1000において、2つの線1002が30度離れている一方で、他の2つの線が60度離れていてもよい)。
【００５７】
図11は、ある実装形態による、投射された線を用いて、点が外側の点であるか内側の点であるかを判定する、例示的な手法の概略図1100である。示されるように、概略図1100は、(図9に関して紹介されたような)建物の部分と、点1102、点1104、および点1106という3つの点とを含みうる。点1102、1104、および1106は、(図5の、しかし図11には明示的に示されていない)点のグリッド502からの点でありうる。(図10の、しかし図11には明示的に示されていない)機構1000は、各点1102、1104、および1106において利用され、そのような点が内側の点に相当するか外側の点に相当するかを判定することができる。
【００５８】
いくつかの例示的な実装形態では、ある点が内側の点に相当するか外側の点に相当するかに関する判定は、点から投射された線による衝突の回数に少なくとも一部基づきうる。例えば、衝突の回数は、所定の閾値と比較されうる。所与の点から投射された線による衝突の回数が所定の閾値を満たす(例えば、閾値以上である、閾値を超える、閾値より小さいなど)場合、そのような所与の点は、内側の点に相当すると判定されうる。例として、そのような所定の閾値は、8つの線1002を有する機構1000が用いられる場合は、またはその間は、5または6に等しくてよい。8つの投射された線を有する機構または異なる数の投射された線を有する機構を含む機構について、そのような所定の閾値の他の値を用いてもよい。代替的に、しかし等価的に、所与の点から投射される線による衝突の回数が所定の閾値を満たす(例えば、8つの投射された線との衝突が3回以下である)場合、所与の点は外部の点に相当すると判定されうる。
【００５９】
概略図1100を参照すると、所定の閾値を5に設定することができ、衝突の回数がそのような所定の閾値以上である場合に、衝突の回数が所定の閾値を満たしうる、例が示される。8つの線が、点1102から投射されうる。この例で示されるように、8つの線全てが建物の要素と衝突する。明瞭にするために、そのような衝突は実線により表される。したがって、8は5を超えるので、点1102は内側の点に相当すると判定されうる。
【００６０】
点1104から、8つの線が投射されうる。6つが実線で示され、建物の要素との衝突を表す。2つが点線で示され、建物の要素と衝突しないことを表す。6は5を超えるので、点1104は、内側の点に相当すると判定されうる。点1106から、8つの線が投射される。3つが実線で示され、建物の要素と衝突することを表す。5つが点線で示され、建物の要素と衝突しないことを表す。3は5以上ではないので、点1106は、外側の点に相当すると判定されうる。
【００６１】
図12は、ある実装形態による、点が外側の点か内側の点かを投射される線を用いて判定するための、例示的な方法を示す流れ図1200である。示されるように、流れ図1200は、7つの動作ブロック1202〜1208および1208a〜1208cを含みうる。これらの動作は特定の順序で示され説明されるが、特許請求される主題から逸脱することなく、方法は代替的な方式で実行されうることを理解されたい。また、流れ図1200の動作は、互いに完全にまたは一部重複して実行されてもよい。加えて、以下の説明は、いくつかの他の図(例えば図3〜5、10、および11)で示される具体的な態様および特徴に言及するが、方法は他の態様および/または特徴とともに実行されてもよい。
【００６２】
いくつかの例示的な実装形態では、動作1202において、点が点のグリッドから選択されうる。例えば、点1102、1104、または1106が、点のグリッド502から選択されうる。動作1204において、複数の線が、選択された点から投射されうる。例えば、複数の線1002は、選択された点1102、1104、または1106から投射されうる。
【００６３】
動作1206において、建物の要素に衝突する投射された線の数が決定されうる。例えば、1つまたは複数の構成要素402により表されるような建物の要素に衝突する投射された線1002の数が、判定されうる。動作1208において、選択された点が、例えば所定の回数の衝突に少なくとも一部基づいて、内側の点または外側の点を含むものとして識別されうる。例えば、選択された点1102、1104、または1106が、建物構造の内側の領域の一部または建物構造の外側の領域の一部である点に相当するものとして識別されうる。
【００６４】
動作1208a、1208b、および1208cは、動作1208を実施する例示的な手法を表す。動作1208aにおいて、建物構造に衝突する投射された線の数が所定の閾値を満たすかどうかが判定されうる。建物構造に衝突する線の数がそのような所定の閾値を満たさない場合、動作1208bにおいて、選択された点は、外側の点を含むものとして識別されうる。一方、建物構造に衝突する線の数が、そのような所定の閾値を満たす、またはそれを超えると判定される場合、動作1208cにおいて、選択された点は、内側の点を含むものとして識別されうる。例えば、建物構造に衝突する投射された線の数が、そのような所定の閾値を満たす、またはそれを超える場合、そのような線がそこから投射される選択された点は、内側の点に相当するものとして識別されうる。
【００６５】
図13は、ある実装形態による、複数の独立の領域を形成するように、障害のない接続により相互接続される隣接点の例を示す、概略図1300である。示されるように、概略図1300は、複数の独立の領域1302が、1つまたは複数の接続グラフを形成する相互接続された点から決定されうる、ある実装形態による例示的な建物の部分である。具体的には、11個の独立の領域1302が、概略図1300の例示的な建物の部分から決定されうる。図13では、6つのそのような独立の領域1302が明示的に示される。すなわち、独立の領域1302a、1302b、1302c、1302d、1302e、および1302fである。
【００６６】
いくつかの例示的な実装形態では、点のグリッド(例えば、図9の点のグリッド502)からの点が、障害のない接続により隣接点と相互接続され、1つまたは複数の接続グラフを形成することができる。点の相互接続は、例えば、あらゆる任意の点から開始することができる。壁または他の建物構造に直接位置する全ての点が、無視されうる。2点間の接続(例えば第1の地点から第2の地点への接続)は、例えば、そのような接続が、壁、柱などのような建物構造と衝突しない、かつ/または交差しない場合、障害がないと考えることができる。2つの点は、例えば、それらが近隣の点である(例えば、第2の点が第1の点の近くの8つの点のうちの1点である)場合、隣接していると考えることができる。例えば、点(i,j)に対して、接続は、障害がない場合、点(i,j)と、8個のすぐ周りの点(i-1,j)、(i+1,j)、(i,j-1)、(i,j+1)、(i-1,j-1)、(i+1,j+1)、(i-1,j+1)、および(i+1,j-1)の各々との間に描くことができる。さらに、外側の点および内側の点は、点線1304により示されるように、相互接続されないようにすることができる(例えば、そのような内側と外側との接続になるであろう接続は、独立の領域1302を決定するために、障害があると考えることができる)。しかし、特許請求される主題は、この特定の相互接続手法にそのように限定はされない。
【００６７】
障害のない接続で隣接点を相互接続することで、複数の接続グラフを形成することができ、複数の接続グラフは、建物情報が閉じた多角形または同様の分離された構造を含む場合には、互いに接続されていなくてもよい。そのような複数の互いに接続されていないグラフは、複数の独立の領域1302を含むものと考えることができる。具体的には、11個の独立の領域1302が示されているが、6個の独立の領域1302a、1302b、1302c、1302d、1302e、および1302fが、図13に明示的に示されている。図9および13と図4および5との比較から明らかなように、廊下の一部である独立の領域1302cが、概略図1300に部分的に示される。
【００６８】
同様の比較により、独立の領域1302eが、概略図1300に部分的に示されていることが明らかになる。図11および12を特に参照して本明細書において上で説明されたように、点1106は、外側の点に相当すると考えることができる。独立の領域1302が1つまたは複数の外側の点を含む場合、独立の領域1302は、外側の領域1302eのような外側の独立の領域を含むと確定されうる。したがって、独立の領域1302eは、建物構造に対して外側の領域を含むと考えることができる。独立の領域1302が内側の点を含む場合、独立の領域1302は、内側の領域1302a、1302b、1302c、1302d、および1302fのような内側の独立の領域を含むと確定されうる。
【００６９】
図14は、ある実装形態による、独立の領域の広がりに基づいて廊下を発見する例示的な手法の概略図1400である。示されるように、概略図1400は、独立の領域1402および広がり1404を含みうる。いくつかの例示的な実装形態では、独立の領域1402に対応する広がり1404は、建物構造の任意の廊下を発見するのに用いられうる。より具体的には、図14は、3つの独立の領域1402a、1402b、1402cを示す。示されるように、独立の領域1402aは広がり1404aに相当し、独立の領域1402bは広がり1404bに相当し、独立の領域1402cは広がり1404cに相当しうる。
【００７０】
一般に、広がり1404は、独立の領域1402を包含する、境界が最小の長方形であると考えることができる。より具体的には、広がりは以下の式を用いて決定されうる。
広がり=(Max(X)-Min(X))×(Max(Y)-Min(Y))
ここで、Xは対応する独立の領域のグリッドの点のx値の集合であり、Yは対応する独立の領域のグリッドの点のy値の集合である。しかし、特許請求される主題から逸脱することなく、広がりは異なる方式で決定されてもよい。
【００７１】
例示的な実装形態では、1つまたは複数の廊下領域が、各々の独立の領域の「広がり」を求めることにより識別されうる。廊下は、複数の計算された広がりおよび少なくとも1つの所定の閾値に少なくとも一部基づいて、推定されうる。そのような所定の閾値は、所与の建物構造の複数の計算された広がりに少なくとも一部基づいて、決定されうる。単なる例として、廊下は、広がりが複数の(最大で全ての)広がりの平均から標準偏差の3倍以上離れている、独立の領域として判定されうる。他の統計的な測定値を代わりに用いてもよい。あるいは、所定の閾値は、いくつか例を挙げると、各広がりの高さと幅の比に関して、各広がりと建物構造の全体の広がりとの比較に関して、またはその他に関して、確立されてもよい。しかし、特許請求される主題は、そのような所定の閾値の確立のされ方には限定されない。
【００７２】
図15は、ある実装形態による、独立の領域の広がりに基づいて廊下を発見するための例示的な方法を示す、流れ図1500である。示されるように、流れ図1500は、6個の動作ブロック1502、1504、および1504a〜1504dを含みうる。これらの動作は特定の順序で示され説明されるが、特許請求される主題から逸脱することなく、方法は代替的な方式で実行されうることを理解されたい。また、流れ図1500の動作は、互いに完全にまたは一部重複して実行されてもよい。加えて、以下の説明は、いくつかの他の図(例えば図3〜5、および14)で示される具体的な態様および特徴に言及するが、方法は他の態様および/または特徴とともに実行されてもよい。
【００７３】
いくつかの例示的な実装形態では、動作1502において、複数の独立の領域の広がりが計算されうる。例えば、複数の独立の領域1402の広がり1404が計算されうる。動作1504において、少なくとも1つの独立の領域が、複数の計算された広がりおよび少なくとも1つの所定の閾値に基づいて、廊下として識別されうる。例えば、独立の領域1402は、計算された広がり1404a、1404b、1404c、…および少なくとも1つの所定の閾値に基づいて、廊下として識別されうる。例えば、独立の領域1402cは、広がり1404cが、計算された広がり1404a、1404b、1404c、…の平均から、標準偏差の3倍よりも離れている場合、廊下として識別されうる。
【００７４】
動作1504a、1504b、1504c、および1504dは、動作1504を実施する例示的な手法を表す。当然、これらは単なる例示的な手法であり、特許請求される主題はこの点においては限定されない。動作1504aにおいて、ある特定の広がりが、複数の計算された広がりに依存する所定の閾値と比較されうる。例えば、ある特定の広がりは、複数の計算された広がりの平均を標準偏差の3倍分超えると反応するように設定される、所定の閾値と比較されうる。動作1504bにおいて、特定の広がりが所定の閾値を満たすかどうかが判定される。満たさない場合、次の広がりが、動作1504dで示されるように分析される。一方、(動作1504bで判定可能なように)特定の広がりが所定のしきい値を満たすと判定される場合、動作1504cにおいて、特定の広がりに対応する独立の領域が、廊下として識別されうる。
【００７５】
図16は、ある実装形態による、どの独立の領域が使用可能か、および使用不可能な独立の領域があるかどうかを判定する、例示的な手法の概略図1600である。示されるように、概略図1600は、1つまたは複数の使用可能な領域1602、1つまたは複数の使用不可能な領域1604、少なくとも1つの廊下1606、および注記情報404aの少なくとも1つの項目を含みうる。いくつかの例示的な実装形態では、注記情報に対応する独立の領域は、使用可能な領域を含むと判定することができ、注記情報に対応しない独立の領域は、使用不可能な領域を含むと判定することができる。そのような判定を実行するために、注記情報が、建物情報に対応する少なくとも1つの接続グラフに重畳されうる。そのような注記情報(例えば、図4の注記情報404)は、建物情報(例えば建物情報400)の一部として含まれうる。その場合、注記情報は、いくつか例を挙げると、情報の1つまたは複数のレイヤ、メタデータ、これらの組み合わせなどを含みうる。
【００７６】
いくつかの例示的な実装形態では、注記情報が、独立の領域に重畳されうる。例えば、注記情報404が、(図13の)独立の領域1302に重畳されうる。概略図1600に示されるように、注記情報404aの特定の項目が、建物情報302の位置と関連付けられうる。そのような位置は、建物情報の地図の一部であってよく、いくつか例を挙げると、ドットまたは矢印の座標、テキストの配置、アイコンの配置などに対応しうる。座標は、存在する場合、x座標、y座標の形態、または他の何らかの形態であってよい。限定ではなく例として、座標は、物理的な距離、計測された距離、ピクセルまたはドットの計数、これらの任意の組み合わせなどに関して提供されうる。しかし、特許請求される主題は、注記情報のそのような位置情報の形態、フォーマットなどによっては限定されない。
【００７７】
1つまたは複数の障害のない接続が、注記情報404aを独立の領域に対応する接続されていないグラフの点と接続する場合、注記情報404aは独立の領域に対応すると考えることができる。より具体的には、注記情報404の項目の所与の位置を、1つまたは複数の障害のない接続を用いて、独立の領域に対応する接続されていないグラフに接続することが可能でありうる。したがって、座標点または他の位置の点が、グリッド化された建物の地図領域に挿入されてもよく、障害のない接続が、その挿入された位置の点から点のグリッドの他の点まで描かれてもよい。これらのような例示的な方式では、抽出された注記層を、対応する独立の領域に関連付けることができる。
【００７８】
いくつかの例示的な実装形態では、独立の領域は、独立の領域が注記情報に対応するか/関連付けられているかどうかに関して、分析されうる。独立の領域が注記情報404に対応する場合、独立の領域は、使用可能な領域1602を含むと考えることができる。一方、独立の領域が注記情報(例えば、任意の注記情報、特定の関連する種類の注記情報など)に対応しない場合、独立の領域は、使用不可能な領域1604を含むと考えることができる。限定ではなく例として、図16については、注記情報404はPoint of Interest(POI)を含む。
【００７９】
POI-Aは、注記情報404aおよび独立の領域1602aに対応する。POI-BおよびPOI-Cは、2つの独立の領域1602bおよび1602cにそれぞれ対応する。示されるように、4つの他の独立の領域は、「D」、「E」、「F」、および「G」により示されるような、POI情報に対応する。POI情報に対応する独立の領域は、使用可能な独立の領域1602a、1602b、および1602cのような、使用可能な独立の領域1602であると決定されうる。(視覚的に明瞭にするために、「D」、「E」、「F」、および「G」の独立の領域は、使用可能な独立の領域に対応するものとしては別段示されていない。)廊下1606も、経路案内グラフにおいて廊下の地点と接続を移動することを許されているユーザーに関しては少なくとも、使用可能な領域であると考えることができる。
【００８０】
所与の独立の領域に対応するPOI情報がない場合、所与の独立の領域は、使用不可能な独立の領域1604であると判定されうる。示されるように、2つの使用不可能な独立の領域1604aおよび1604bが存在する。使用不可能な領域1604への経路案内は、特別に許可されたユーザーに限定されていてもよく、または防がれていてもよい。
【００８１】
図17は、ある実装形態による、建物情報を分析することにより識別されうる建物構造の例示的な態様を示す、概略図1700である。概略図1700は、(図4の)建物情報400の少なくとも部分的に分析されたバージョンの例に相当しうる。説明文1702により示されるように、外側を識別することができ、1つまたは複数の廊下を発見する(例えば推定する)ことができ、1つまたは複数の使用可能な領域を識別することができる。外側の領域は、黒く塗られている。推定される廊下は、薄い灰色に塗られている。使用可能な領域は、斜行平行模様に塗られており、POIを表すためにドットでマークされている。推定される廊下(灰色に塗られている)が外側の領域(黒く塗られている)と接する内側の点と外側の点の境界も、見ることができる。
【００８２】
経路案内は、そのような地図(例えば、扉の表示を省略した地図)では難しいことがある。廊下を発見して使用可能な領域を識別することはできるが、指定された出入口が存在しないことがある。したがって、指定されたPOIに推定された廊下のどの点からでも近づくことができるように見えうる場合、指定されたPOIにユーザーをどのように案内するかが不明確になることがある。一般に、例示的な実装形態では、各POIについて、1つまたは複数の方向(例えば、互いに45度離れている8つの方向)にある地図中の「最も近い」廊下の点が発見されうる。特定の方向にある廊下の点の分析において、2つ以上の建物の要素(略図の構成要素から知られうる)に衝突する場合、そのような特定の方向は無視されうる。2つ以上の建物の要素に衝突するということは、特定の方向は廊下に(少なくとも直接は)導かないということを示唆する。Point of Interestの独立の領域の入口/出口の点を決定するための例示的な実装形態が、図18および19を特に参照して、以下でさらに説明される。
【００８３】
図18は、ある実装形態による、使用可能な独立の領域の入口/出口の点を決定する例示的な手法の、概略図1800である。示されるように、概略図1800は、建物情報の地図上に位置する注記情報404b(例えばPOI)および少なくとも1つの廊下1606を含みうる。概略図1800は、複数の投射された線1802および1804と、入口/出口の点1806とも含みうる。
【００８４】
いくつかの例示的な実装形態では、複数の線が注記情報404bから投射されうる。1つまたは複数の、入口および/または出口(入口/出口)の点が、複数の投射された線および建物構造の少なくとも1つの廊下に少なくとも一部基づいて、所与の独立の領域に対して決定されうる。(図10の)機構1000を注記情報404bの位置で用いて、(やはり図10の)線1002を投射することができる。この例では、8つの線が投射されうる。8つの投射された線1802および1804が、図18に示される。
【００８５】
廊下に到達したかどうか、およびいくつの建物の構成要素と交差したかに基づいて、入口/出口の点は、投射された線が建物の要素と交わる点に存在すると(経路案内グラフのために)判定されうる。投射された線が廊下に達するまでに2つ以上の建物の構成要素と衝突した場合、そのような投射された線が入口/出口の点を画定すると考えることはできない。投射された光が廊下に達するまでに1つの建物の構成要素と衝突した場合、そのような投射された線は入口/出口の点を画定すると考えることができる。
【００８６】
概略図1800に示されるように、投射された線1802は入口/出口の点を画定することができるが、投射された線1804は入口/出口の点を何ら画定することができない。より具体的には、投射された線1802a、1802b、および1802cの各々は、建物の要素を表す1つの線と交わって廊下1606に到達するので、入口/出口の点1806a、1806b、および1806cをそれぞれ画定する。投射された線1804aおよび1804bは、廊下1606に到達する前に複数の建物の構成要素と交わるので、入口/出口の点を画定することができない。同様に、かつ/または類似して、投射された線1804c、1804d、および1804eは、建物の要素を表す1つの線と交わった後に廊下1606(または任意の他の廊下)に到達しないので、入口/出口の点を画定することはできない。
【００８７】
例示的な動作として、線は、廊下に到達するまで投射されてもよい。そのような投射された線が2つ以上の建物の構成要素と交わって廊下に到達する場合、入口/出口の点を画定することはできない。一方、そのような投射された線が1つのみの建物の構成要素と交わって廊下に到達する場合、入口/出口の点を画定することができる。あるいは、線は、1つの建物の構成要素と交わるまで投射されてもよい。1つの建物の構成要素と交わって廊下に到達した場合、そのような投射された線は入口/出口の点を画定することができる。一方、投射された線が、1つの建物の構成要素と交わっても廊下に到達しない場合、そのような投射された線は入口/出口の点を画定することはできない。
【００８８】
図19は、ある実装形態による、使用可能な独立の領域の入口/出口の点を決定するための、例示的な方法を示す流れ図1900である。示されるように、流れ図1900は、5つの動作ブロック1902〜1910を含みうる。動作1902〜1910は特定の順序で示され説明されるが、特許請求される主題から逸脱することなく、方法は代替的な方式で実行されうることを理解されたい。また、流れ図1900の動作は、互いに完全にまたは一部重複して実行されてもよい。加えて、以下の説明は、いくつかの他の図(例えば図3〜5、9、10、16、および18)で示される具体的な態様および特徴に言及するが、方法は他の態様および/または特徴とともに実行されてもよい。
【００８９】
いくつかの例示的な実装形態では、動作1902において、独立の領域の注記情報(例えばPOI)から、複数の線が投射されうる。例えば、所与の独立の領域の注記情報404bの位置から、複数の線1002(例えば線1802および1804)が投射されうる。動作1904において、廊下に到達するまでの、複数の投射された線の建物の要素との衝突が検出されうる。例えば、廊下1606へ到達するまでに、投射された線1802または1804が起こした衝突の回数が検出されうる。あるいは、投射された線1802または1804が、第1の建物の要素と衝突してから廊下1606に到達するかどうかが、検出されうる。
【００９０】
動作1906において、独立の領域の入口/出口の1つまたは複数の点が、そのような衝突に基づいて特定されうる。例えば、投射された線1802が廊下1606に到達するまでに1回衝突した場合、入口/出口の点1806が特定されうるが、投射された線1804が廊下1606に到達するまでに複数回衝突した場合(または投射された線1804が、廊下1606に到達する前に、少なくとも2つの建物の要素に衝突する場合)、入口/出口の点を特定することはできない。
【００９１】
動作1908において、分析すべき独立の領域がまだあるかどうかが判定されうる。分析すべき独立の領域がある場合、流れ図1900の方法を、動作1902において別の独立の領域を分析することによって継続することができる。分析すべき独立の領域がこれ以上ない場合、何らかの時点で(例えば、そのような分析が完了してからすぐに、分析が完了した後の何らかの時点で、など)、動作1910が実施されうる。動作1910において、指定されたPOIに道案内するための1つまたは複数の経路が、指定されたPOIに対応する独立の領域の特定された入口/出口の点に基づいて計算されうる。例えば、入口/出口の点1806および(図3の)経路案内グラフ312を用いて、指定された注記情報404bのPOIへ道案内するための経路が計算されうる。
【００９２】
あるいは、所与の使用可能な独立の領域の1つまたは複数の境界壁を調査して、そのような所与の独立の領域の入口/出口の点を決定してもよい。例えば、境界壁の反対側の別の独立の領域が、(廊下ではない独立の領域とは反対の)廊下を含むかどうかが確定されうる。所与の使用可能な独立の領域の境界壁の反対側にある特定の独立の領域が廊下を含む場合、その所与の使用可能な独立の領域について、少なくとも1つの入口/出口の点を特定することができる。例えば、少なくとも1つの出入口の点が、所与の利用可能な独立の領域と、廊下を含む特定の独立の領域とを分離する、境界壁に沿って(例えば境界壁の中央の近くに)位置しうる。
【００９３】
少なくとも、使用可能な領域を含む独立の領域の特定された入口/出口の点が、接続によって相互接続された後に、経路案内グラフが作成されうる。点のグリッドの点は、そのような経路案内グラフのノードを含んでもよく、点を相互接続する接続は、そのような経路案内グラフのエッジを含んでもよい。さらに、到達できない領域を使用不可能な場所として区分けするとともに、POI注記情報を、対応する独立の領域と関連付けてもよく、または接続してもよい。ある場所から別の場所への経路案内は、経路案内グラフにおいて2つの点/ノードを選択し、残りのグラフに対して最短経路アルゴリズム(例えばダイクストラ法など)を実行することによって、実施されうる。道案内指示(限定はされないが、リアルタイムの案内および/またはターンバイターンの案内を含む)は、そのような経路案内グラフを用いて提供されうる。さらに、代替的にかつ/または追加で、他の位置情報サービス(例えば位置決め、位置フィルタリングなど)を、作成された経路案内グラフに少なくとも一部基づいて、ユーザー(例えばモバイル機器のユーザー)に提供することができる。
【００９４】
図18および19を特に参照して本明細書において説明された例示的な実装形態の下では、複数の入口/出口の点が単一のPOIに対して決定されうる。したがって、所与のPOIに対して、最大でk個の入口/出口の点が存在しうる(例えば、k≦8であり、kは投射された線の数により決まる)。目的地のPOIから別の場所(例えば廊下)への経路が要求された場合、目的地のPOIの複数の特定された入口の点(例えば最大でk個の入口の点)に対して、手間が最小の経路が計算されうる。複数の経路または単一の経路(例えば手間が最小の経路)が、要求したユーザーに示されうる。ユーザーが第1のPOIから第2のPOIまでの経路を求めることを望む場合、最大でk1×k2個の経路を計算することができ(このとき第1のPOIはk1個の出口の点を有し、第2のPOIはk2個の入口の点を有する)、経路のうちの1つまたは複数(例えば最短経路または複数の経路)を選択してユーザーに提供することができる。
【００９５】
図20は、ある実装形態による、例示的な機器2000を示す概略図であり、例示的な機器2000は、略図を用いる建物用の経路案内グラフの1つまたは複数の態様を実施することができる。示されるように、機器2000は、少なくとも1つのプロセッサ2002、1つまたは複数のメモリ2004、少なくとも1つの通信インターフェース2006、少なくとも1つの電源2008、および、SPS(衛星測位システム)ユニット(SPSU)(明確には示されていない)のような他の構成要素2010を含みうる。メモリ2004は、命令2012を含むものとして示されている。しかし、代替的には、機器2000は、示されている構成要素よりも、多くの、少ない、および/または異なる構成要素を含んでもよい。
【００９６】
いくつかの例示的な実装形態では、機器2000は、電子機器を含んでもよく、かつ/または備えてもよい。機器2000は、例えば、少なくとも1つのプロセッサおよび/またはメモリを有する任意の電子機器を含んでもよい。機器2000の例は、限定はされないが、固定式の処理機器(例えば、デスクトップコンピュータ、1つまたは複数のサーバコンピュータ、少なくとも1つの遠隔通信ノード、インテリジェントルータ/スイッチ、これらの何らかの組み合わせなど)、移動式の処理機器(例えば、ノートブックコンピュータ、携帯情報端末(PDA)、ネットブック、スレートまたはタブレット型コンピュータ、持ち運び式娯楽機器、携帯電話、スマートフォン、移動局、これらの何らかの組み合わせなど)などを含む。
【００９７】
電源2008は、機器2000の構成要素および/または回路に電力を供給することができる。電源2008は、電池のような持ち運び可能な電源であってもよく、または、自動車、家、または他の建物のコンセントのような、固定式の電源であってもよい。電源2008はまた、太陽または炭素燃料を用いる発電機のような、可搬型の電源であってもよい。電源2008は、機器2000と一体であっても分離していてもよい。
【００９８】
プロセッサ2002は、任意の1つまたは複数の処理ユニットを含みうる。メモリ2004は、プロセッサ2002により実行可能でありうる命令2012(例えば、プログラム、アプリケーションなど、またはこれらの一部、使用可能なデータ構造、プロセッサ実行可能命令、コード、これらの何らかの組み合わせなど)を保存し、格納し、または命令2012へのアクセスを提供することができる。1つまたは複数のプロセッサ2002によるそのような命令2012の実行により、機器2000は、特別な用途のコンピューティング機器、装置、プラットフォーム、これらの組み合わせなどに変換されうる。
【００９９】
命令2012は、経路案内グラフ命令2012a、建物情報2012b、および/または建物道案内ファイル2012cを含みうる。建物情報2012bは、例えば、(図3の)建物情報302(例えば(図4の)建物情報400)に対応しうる。建物道案内ファイル2012cは、例えば、(図3の)建物道案内ファイル308に対応していてもよく、建物道案内ファイル308は、経路案内グラフ312、1つまたは複数の接続グラフ316、および/または関連する注記情報314を含みうる。経路案内グラフ命令2012aは、例えば、(図6、7、12、15、および19の)流れ図600、700、1200、1500、および/または1900の1つまたは複数の実施を実現することができる、命令に相当しうる。経路案内グラフ命令2012aを実行して、例えば、建物情報2012bに少なくとも一部基づいて、建物道案内ファイル2012cの少なくとも一部を生成することができる。明確には示されていないが、命令2012は、建物道案内ファイル2012cを用いて1つまたは複数の位置情報サービス(LBS)を提供するための命令も含みうる。
【０１００】
例示的な実装形態では、サーバおよび/または遠隔通信ノードのような固定式の処理機器が、経路案内グラフ命令2012aを実行して、建物情報2012bに少なくとも一部基づいて、建物道案内ファイル2012cを作成することができる。同一のまたは異なる固定式処理機器が、建物道案内ファイル2012cを用いて、例えば、SPSUを含みうるモバイル機器にLBSを提供することができる。あるいは、そのような固定式の処理機器は、建物道案内ファイル2012cをモバイル機器に提供して、いくつかのLBSを可能にする、またはいくつかのLBSのさらなる実行を可能にすることができる。さらに別の代替形態として、モバイル機器は、経路案内グラフ命令2012aを含み、取得された(例えばメモリから取り出された、オンデマンドでダウンロードされた、写真を撮影することで取得された、など)建物情報2012bから建物道案内ファイル2012cを作成することができる。他の代替形態も、特許請求される主題から逸脱することなく、代わりに実施することができる。
【０１０１】
通信インターフェース2006は、機器2000と他の機器(例えば、および/または使用する人)との間の1つまたは複数のインターフェースを提供することができる。したがって、通信インターフェース2006は、画面(例えばタッチスクリーン)、スピーカー、マイクロフォン、キーボード/キー、ノブ/ホイール、または人と機器の間の他の入力/出力機構を含んでもよい。そのような人と機器の間の入力/出力機構は、存在する場合、検索および/または道案内の補助を要求するために、または、検索結果および/または道案内情報を視覚的にかつ/または音声により受け取るために、人により用いられうる。通信インターフェース2006は、送受信機(例えば送信機および/または受信機)、無線、アンテナ、有線インターフェースコネクタまたは他のそのような装置、これらの何らかの組み合わせなどを含み、無線信号および/または有線信号を(例えば無線通信リンクまたは有線通信リンクを通じて)通信することができる。通信インターフェース2006は、機器2000の他の構成要素間の、バスまたは他の相互接続としての役割も果たしうる。他の構成要素2010は、存在する場合、1つまたは複数の他の様々なセンサ、機構などを含んでもよい。
【０１０２】
本明細書で説明された方法は、具体的な特徴および/または例にしたがって、用途に応じて様々な手段で実装されうる。例えば、そのような方法は、ハードウェア、ファームウェア、ソフトウェア、個別の/固定された論理回路、これらの任意の組み合わせなどで実装されうる。ハードウェアによる実装形態では、例えば、プロセッサ/処理ユニットは、いくつか例を挙げると、1つまたは複数の特定用途向け集積回路(ASIC)、デジタルシグナルプロセッサ(DSP)、デジタルシグナルプロセシングデバイス(DSPD)、プログラマブル論理デバイス(PLD)、フィールドプログラマブルゲートアレイ(FPGA)、プロセッサ全般、コントローラ、マイクロコントローラ、マイクロプロセッサ、電子的なデバイス、命令を実行するようにプログラムされた、かつ/もしくは本明細書で説明される機能を実行するように設計された、他のデバイスまたはユニット、および/またはこれらの組み合わせの中に、実装されうる。本明細書において、用語「制御論理回路」は、ソフトウェア/ファームウェアで実装される論理回路、ハードウェア(例えば個別の/固定された論理回路)、これらの任意の組み合わせなどを包含しうる。
【０１０３】
ファームウェアおよび/またはソフトウェアによる実装形態では、方法は、本明細書で説明される機能を実行する命令を有するモジュール(例えば、プロシージャ、関数など)により実装されうる。命令を有形に具現化する任意の機械可読媒体が、本明細書で説明される方法を実装する際に用いられうる。例えば、ソフトウェアコードをメモリに保存することができ、プロセッサにより実行することができる。メモリは、プロセッサ内に実装されてもよく、プロセッサの外側に実装されてもよい。本明細書で用いられる用語「メモリ」は、任意の種類の、長期的な、短期的な、揮発性の、非揮発性の、または他の記憶メモリ/媒体を指し、特定の種類のメモリまたは特定の数のメモリ、または記憶が保存される媒体の特定の種類に何ら限定されることはない。
【０１０４】
ファームウェアおよび/またはソフトウェアによる実装形態では、機能は、1つまたは複数の命令またはコードとして、コンピュータ可読媒体に保存されうる。例には、データ構造でエンコードされたコンピュータ可読媒体と、コンピュータプログラムによりエンコードされたコンピュータ可読媒体とを含む。コンピュータ可読媒体は、製造物品の形態であってもよい。コンピュータ可読媒体は、物理的なコンピュータ記憶媒体を含む。記憶媒体は、コンピュータによりアクセスされうる任意の利用可能な媒体であってよい。限定ではなく例として、そのようなコンピュータ可読媒体は、RAM、ROM、EEPROM、CD-ROMもしくは他の光ディスク記憶装置、磁気ディスク記憶装置、半導体記憶装置、もしくは他の記憶機器、または、命令またはデータ構造の形態で所望のプログラムコードを保存するのに用いることができ、コンピュータによりアクセスすることができる、任意の他の媒体を含みうる。本明細書で用いられる場合、ディスク(disk)およびディスク(disc)は、コンパクトディスク(CD)、レーザーディスク（登録商標）、光ディスク、デジタル多目的ディスク(DVD)、フロッピー（登録商標）ディスクおよびブルーレイディスクを含み、ディスク(disk)は通常データを磁気的に再生し、ディスク(disc)はレーザーによりデータを光学的に再生する。上記の組み合わせも、コンピュータ可読媒体の範囲に含まれるべきである。
【０１０５】
コンピュータ可読媒体への保存に加えて、命令および/またはデータは、通信装置に含まれる伝送媒体上の信号として提供されてもよい。例えば、通信装置は、命令およびデータを示す信号を有する送受信機を含んでもよい。命令およびデータは、1つまたは複数の処理ユニットに特許請求の範囲で概説される機能を実装させるように、構成される。つまり、通信装置は、開示される機能を実行するための情報を示す信号を有する、伝送媒体を含む。第1の時間では、通信装置に含まれる伝送媒体は、情報の第1の部分を含み開示される機能を実行することができるが、第2の時間では、通信装置に含まれる伝送媒体は、開示される機能を実行するための情報の第2の部分を含んでもよい。
【０１０６】
電子機器は、Wi-Fi/WLANまたは他の無線ネットワークとともに動作することもできる。例えば、位置データが、Wi-Fiまたは他の無線ネットワークを介して取得されうる。Wi-Fi/WLAN信号に加えて、無線/移動式の機器は、全地球測位システム(GPS)、Galileo、GLONASS、NAVSTAR、QZSS、これらのシステムの組み合わせの衛星を用いるシステム、または将来開発される任意のSPSからの信号でありうる、衛星からの信号を受信することもでき、上述の各システムは、本明細書では衛星測位システム(SPS)と一般に呼ばれる。さらに、本明細書で説明される実装形態は、擬似衛星または衛星と擬似衛星の組み合わせを利用する、測位システムとともに用いられうる。擬似衛星は通常、擬似ランダムノイズ(PRN)符号または、Lバンド(または他の周波数)の搬送波信号に変調された他の測距コード(例えば、GPSまたはCDMAセルラー信号に類似した)をブロードキャストする、地上の送信機であり、上記の搬送波信号はGPS時間と同期されうる。各々のそのような送信機は、遠隔の受信機による識別を可能にするために、固有のPNコードを割り当てられうる。擬似衛星は、トンネル、鉱山、建物、アーバンキャニオン、または他の囲まれた領域のような、軌道衛星からのSPS信号が利用できない状況では、特に有用でありうる。擬似衛星の別の実装形態は、無線ビーコンとして知られている。本明細書で用いられる用語「衛星」は、擬似衛星、擬似衛星の等価物、および同様のかつ/または類似の技術も含むべきである。本明細書で用いられる場合、用語「SPS信号」は、擬似衛星または擬似衛星の等価物からのSPSのような信号も含むべきである。いくつかの実装形態は、フェムトセル、またはフェムトセルを含むシステムの組み合わせにも、適用されうる。
【０１０７】
例示的な実装形態では、SPSU(存在すれば)は、1つまたは複数のSPSシステムを用いて、機器2000の位置を決定することができてもよい。したがって、本明細書で説明される例示的な実装形態は、様々なSPSとともに用いられうる。SPSは通常、エンティティが、送信機から受信された信号に少なくとも一部基づいて、地上または上空での自身の位置を決定することを可能にするように位置付けられた、送信機のシステムを含む。そのような送信機は、必須ではないが通常、一定の数のチップの繰り返し擬似ランダムノイズ(PN)符号でマークされた信号を送信し、地上の管制局、ユーザー装置、および/または宇宙船に存在しうる。具体的な例では、そのような送信機は、地球軌道宇宙機(SV)に存在しうる。例えば、全地球測位システム(GPS)、Galileo、GlonassまたはCompassのような全地球航法衛星システム(GNSS)の集合のSVは(例えば、GPSのように各衛星に対して異なるPN符号を用いて、またはGlonassのように異なる周波数に対して同一の符号を用いて)、その集合内の他のSVにより送信されたPN符号と区別可能なPN符号によりマークされる信号を送信することができる。いくつかの態様によれば、本明細書で提示される技術は、SPSのための地球規模のシステム(例えばGNSS)には限定されない。例えば、本明細書で提供される技術は、日本の準天頂衛星システム(QZSS)、インドのインド地域航法衛星システム(IRNSS)、中国の北斗など、ならびに/または、1つもしくは複数の地球規模のおよび/もしくは地域的な航法衛星システムに関連しうる、もしくはそれらとともに用いることが可能にされうる、様々な補強システム(例えば、静止衛星型衛星航法補強システム(SBAS))に、適用されてもよく、またはそれらとともに用いることが可能であってもよい。限定ではなく例として、SBASは、例えば、広域補強システム(WAAS)、European Geostationary Navigation Overlay Service(EGNOS)、多目的衛星用航法補強システム(MSAS)、GPS Aided Geo Augmented Navigation or GPS and Geo Augmented Navigation system(GAGAN)、および/または同様のもののような、統合情報、差分補正などを提供する補強システムを含みうる。したがって、本明細書で用いられる場合、SPSは、1つまたは複数の地球規模のおよび/もしくは地域的な航法衛星システムならびに/または補強システムの任意の組み合わせを含んでもよく、SPS信号は、SPS信号、SPSのような信号、および/またはそのような1つまたは複数のSPSと関連する他の信号を含んでもよい。
【０１０８】
モバイル機器/移動局は、セルラー型の、または他の無線通信機器、個人用通信システム(PCS)機器、個人用ナビゲーション機器(PND)、個人情報管理装置(PIM)、携帯情報端末(PDA)、ラップトップ、タブレット、または、無線通信および/または道案内信号を受信することができる他の適切な機器のような、機器を指す。衛星信号の受信、支援データの受信、および/または位置に関する処理が、機器で行われるかPNDで行われるかには関係なく、モバイル機器は、短距離の無線、赤外線、有線接続、または他の接続などによって、個人用ナビゲーション機器(PND)と通信する機器を含むことも意図されている。また、モバイル機器は、無線通信機器、コンピュータ、ラップトップなどを含む全ての機器を含むことが意図されており、上記の機器類は、衛星信号の受信、支援データの受信、および/または位置に関連する処理が、機器で行われるか、サーバで行われるか、ネットワークに関連する他の機器で行われるかには関係なく、インターネット、Wi-Fi、または他のネットワークを介するなどして、サーバと通信することができる。上記の任意の動作可能な組み合わせも、モバイル機器であると考えることができる。
【０１０９】
この発明を実施するための形態の一部は、特定の装置または専用のコンピューティング機器もしくはプラットフォームのメモリに保存されうるバイナリデジタル信号に対する動作の、アルゴリズムまたは記号による表現として提示されている。この特定の明細書においては、「特定の装置」などの用語は、プログラムソフトウェア/命令からの命令にしたがって特定の機能を実行するようにプログラムされた後の、汎用コンピュータを含む。アルゴリズムによる説明または記号による表現は、信号処理または関連技術の当業者が、自身の成果の本質を他の当業者に伝えるために用いられる、技法の例である。アルゴリズムとはここでは、かつ一般的に、所望の結果につながる、一貫した一連の動作または同様の信号処理であると考えることができる。これに関連して、動作または処理は、物理量の物理的な操作に関わる。必須ではないが通常、そのような物理量は、保存し、移送し、組み合わせ、比較し、送信し、受信し、または他の方法で操作することができる、電気信号および/または磁気信号の形態をとりうる。
【０１１０】
主に一般に用いられているという理由で、そのような信号を、ビット、データ、値、要素、シンボル、文字、変数、語、数、番号などと呼ぶことが便利なことがあるということがわかっている。しかし、これらの用語および類似の用語は全て、適切な物理量と関連付けられるべきであり、便宜的な呼び方に過ぎないということを理解されたい。別段特に述べられない限り、上の議論から明らかなように、「処理する」、「計算する」、「算出する」、「決定する」、「確定する」、「分析する」、「比較する」、「識別する」、「関連付ける」、「取得する」、「実行する」、「適用する」、「調査する」、「投射する」、「作成する」、「模擬する」、「相互接続する」、「重畳する」、「検出する」、「発見する」、「提供する」などのような用語を利用する、本明細書の議論の全体が、専用コンピュータまたは同様の専用の電子的なコンピューティング機器のような、特定の装置の動作または処理を指すことが、理解されよう。したがって、この明細書においては、専用のコンピュータまたは同様の専用の電子的なコンピューティング機器は、信号を操作または変換することができ、上記の信号は通常、専用のコンピュータまたは同様の専用の電子的なコンピューティング機器の、メモリ、レジスタ、もしくは他の情報記憶機器、伝送機器、または表示機器の中で、物理的な、電気的な量、電子的な量、および/または磁気的な量として表される。
【０１１１】
例示的な特徴であると現在考えられていることが、示されて説明されてきたが、特許請求される主題から逸脱することなく、様々な他の修正を行うことができ、等価物により置換できることが、当業者には理解されよう。加えて、本明細書で説明される主要な概念から逸脱することなく、多くの修正が、具体的な状況を特許請求される主題の教示に適合させるために行われうる。したがって、特許請求される主題は開示される具体的な例に限定されず、そのような特許請求される主題は、添付の特許請求の範囲およびその等価物の範囲にある、全ての態様も含みうることが、意図されている。
【符号の説明】
【０１１２】
100 建物情報の概略図
102 注記情報
200 建物情報の概略図
202 使用可能な領域
204 建物の外側の領域
206 経路案内グラフ
302 建物情報
304 建物地図ファイル
306 データ
308 建物道案内ファイル
312 経路案内グラフ
314 注記情報
316 接続グラフ
502 点のグリッド
1702 説明文
2000 機器
2002 プロセッサ
2004 メモリ
2006 通信インターフェース
2008 電源
2010 他の構成要素
2012 命令
2012a 経路案内グラフ命令
2012b 建物情報
2012c 建物道案内ファイル
【技術分野】
【０００１】
米国特許法第119条による優先権の主張
この米国特許本出願は、2009年10月1日に出願された、AUTOMATIC ROUTING TOPOLOGY EXTRACTION FROM LOW DETAIL SCHEMATICSという表題の、米国特許仮出願第61/247869号と、2009年10月1日に出願された、SYSTEM FOR INDOOR LOCATIONという表題の米国特許仮出願第61/247865号と、2009年10月1日に出願された、AUTOMATIC ROUTING TOPOLOGY EXTRACTION FROM CAD MAPSという表題の米国特許仮出願第61/247866号と、2010年1月22日に出願された、MAP ACQUISITION AND PROCESSING FOR LOCATION BASED SERVICESという表題の米国特許仮出願第61/297524号との利益を主張するものであり、これらの仮出願の各々が、本出願の譲受人に譲渡され、参照によって本明細書に明示的に組み込まれる。
【０００２】
関連出願の参照
本特許出願は、本出願と同時に出願され、代理人整理番号第100013号の、KhorashadiらによるROUTING GRAPHS FOR BUILDINGSという同時係属中の米国特許出願に関連し、上記の同時係属中の特許出願は本出願の譲受人に譲渡され、参照によって本明細書に明示的に組み込まれる。
【０００３】
本明細書で開示される主題は、比較的詳細度が低い略図を含みうる建物情報に少なくとも一部基づいて、経路案内グラフを作成することに関する。
【背景技術】
【０００４】
地図は、20世紀中に電子的形態で利用可能になり始めた。インターネットの出現により、基本的に世界中のあらゆる場所の地図に、最終的にはアクセスすることができる。ウェブ上の地図サービスは、地点「A」から地点「B」への案内を提供することもできる。これらのウェブ上での地図案内は、比較的静的である。しかし、衛星測位システム(SPS)技術およびさらに小型の電子機器の発明により、いわゆるターンバイターンの案内を、人々が自分の目的地に向かって移動するにつれて動的に提供することができる。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
残念ながら、これらの電子地図およびウェブ上の地図サービスは、ある住所から別の住所への案内のように、屋外で案内を提供することを目的としている。同様に、従来は、ターンバイターンの案内は道路上に限られている。今のところ、屋内で同様の地図および案内サービスを提供する能力が欠けている。
【課題を解決するための手段】
【０００６】
ある例示的な実装形態では、方法は、建物構造の少なくとも一部を表現する建物情報を得るステップと、点のグリッドを建物情報に重畳するステップとを含みうる。建物情報は、重畳された点のグリッドの複数の点から複数の線を投射することによって、重畳された点のグリッドを用いて分析されうる。少なくとも1つの経路案内グラフが、分析に応じて、かつ、重畳された点のグリッドと建物情報とに少なくとも一部基づいて、作成されうる。しかし、これは例示的な実装形態に過ぎず、他の実装形態が本明細書で説明され、特許請求される主題から外れることなく実装されうることを、理解されたい。
【０００７】
非限定的かつ非網羅的な態様、特徴などが、以下の図面を参照して説明され、様々な図面全体で、同様の番号は同様の部分を指す。
【図面の簡単な説明】
【０００８】
【図１】ある実装形態による、注記情報を有する例示的な建物情報の概略図である。
【図２】ある実装形態による、注記情報への関連付けを含む例示的な経路案内グラフが作成された、建物情報の概略図である。
【図３】ある実装形態による、建物情報および建物道案内ファイルの例を示すブロック図である。
【図４】ある実装形態による、例示的な建物情報の概略図である。
【図５】ある実装形態による、例示的な点のグリッドが重畳された、建物情報の概略図である。
【図６】ある実装形態による、建物情報に少なくとも一部基づいて経路案内グラフを作成するための例示的な方法を示す、流れ図である。
【図７】ある実装形態による、建物情報を分析して経路案内グラフを作成するための例示的な方法を示す、流れ図である。
【図８】建物の廊下と建物の外側を区別するのが困難な、起こりうる例を示す図である。
【図９】ある実装形態による、点のグリッドが重畳された、例示的な建物の部分の概略図である。
【図１０】ある実装形態による、建物の情報の概略図に対して線を投射するための例示的な機構を示す図である。
【図１１】ある実装形態による、点が外部の点であるか内部の点であるかを投射された線を用いて判定する例示的な手法の、概略図である。
【図１２】ある実装形態による、点が外部の点であるか内部の点であるかを投射された線を用いて判定するための例示的な方法を示す、流れ図である。
【図１３】ある実装形態による、複数の独立の領域を形成するように障害のない接続によって相互接続される隣接点の例を示す、概略図である。
【図１４】ある実装形態による、独立の領域の広がりに基づいて廊下を発見する例示的な手法の、概略図である。
【図１５】ある実装形態による、独立の領域の広がりに基づいて廊下を発見するための例示的な方法の、流れ図である。
【図１６】ある実装形態による、どの独立の領域が使用可能か、かつ使用不可能な独立の領域があるかどうかを判定する例示的な手法の概略図である。
【図１７】ある実装形態による、建物情報を分析することにより識別されうる建物構造の例示的な態様を示す、概略図である。
【図１８】ある実装形態による、使用可能な独立の領域の入口/出口の点を決定する例示的な手法の、概略図である。
【図１９】ある実装形態による、使用可能な独立の領域の入口/出口の点を決定するための例示的な方法の、流れ図である。
【図２０】略図を用いる建物用の経路案内グラフの1つまたは複数の態様を実施することができる、ある実装形態による、例示的な機器を示す概略図である。
【発明を実施するための形態】
【０００９】
本明細書全体における、「ある特徴」、「1つの特徴」、「ある例」、「一例」などへの言及は、特徴および/または例とともに説明される、具体的な特徴、構造、特性などが、特許請求される主題の少なくとも1つの特徴および/または例に関連するということを意味する。したがって、本明細書の様々な箇所における、「一例では」、「ある例」、「1つの特徴として」、「ある特徴」、「ある例示的な実装形態では」、「いくつかの例示的な実装形態では」などのような語句の使用は、全てが同じ特徴、例、および/または例示的な実装形態を指すとは限らない。さらに、具体的な特徴、例、構造、特性などは、1つまたは複数の例示的な実装形態、例示的なシステムなどに組み合わされうる。
【００１０】
上で示されたように、2点間の案内およびターンバイターンの案内は、通常屋外の環境において、特に画定された道路のある環境で利用可能である。一方、建物の内部では、通常、同様の地図または道案内の機能は提供されない。屋内での道案内を実現するために、ユーザーが現在位置している環境の地図が用いられうる。しかし、地図だけでは屋内での道案内には不十分であることがある。ユーザーを地図上のある地点から別の地点へ道案内するのを支援するために、グラフおよび関連する注記レイヤが用いられうる。そのようなグラフは、一般に経路案内グラフと呼ばれる。
【００１１】
関連する注記情報を有する経路案内グラフは、所与の地図の使用可能な領域を表すことができ、ある点から別の点への通行がどのように可能かを示すことができる。任意の所与の建物について、経路案内グラフは、使用可能な領域および建物内のある点から別の点への通行可能な経路を示す、ノードおよびエッジのセットを含みうる。残念ながら、関連付けられた注記情報を有するそのような経路案内グラフは、建物構造の略図から直接は得られない。そのような略図は、必ずしも限定はされないが、比較的詳細度が低い略図を含みうる。屋内の位置情報サービス(LBS)のエコシステムに対しては、手動で経路案内地図を描き、具体的な屋内の場所の要素を識別することは、豊富な情報を有する数百万の建物構造を追加するのにスケーラブルな方法ではない。
【００１２】
本明細書で説明されるいくつかの例示的な実装形態では、方法は、既存の建物の略図を調査するステップと、その建物の略図から抽出される情報に少なくとも一部基づいて、経路案内グラフを作成するステップとを伴いうる。例示的な経路案内グラフの作成処理は、関連するPoint of Interest(POI)情報を有する建物の略図を含む、多くの建物の略図に共通の既存の要素を用いて、自動的に実行されうる。そのような概略的な地図の分析から、関連する注記情報を有する強力な経路案内グラフが生成されうる。そのようなグラフの生成は、例えば、(i)廊下と部屋を区別するために、また(ii)部屋と廊下の間を接続するもの(例えば出入口など)の可能性の高い位置を決定するために、接続グラフの分析を含みうる。経路案内グラフを用いて、屋内での測位および/または道案内情報がユーザー(例えば、ユーザーのモバイル機器)に提供されうる。
【００１３】
図1は、ある実装形態による、注記情報102を有する例示的な建物情報の概略図100である。ある例示的な実装形態では、概略図100は、建物の少なくとも一部を表しうる。その外観は、いくつか例を挙げると、線、曲線、円弧、多角形、他の閉じた形状などを含みうる。これらの項目は、建物構造の具体的な要素を表すように定義されうる。
【００１４】
例示的な建物の要素は、限定はされないが、壁、扉、柱、部屋、仕切り、小部屋の壁などを含む。そのような建物の要素は、移動を制限する障害物を含んでもよく、その障害物は永続的なものであっても一時的なものであってもよい。示されるように、概略図100は、いくつか例を挙げると、注記情報102と、線で表される壁と、多角形で表される部屋と、これらの組み合わせなどを含みうる。図1の例に示されるように、12個の部屋が、12個の多角形および/または多くの線から形成されうる。明瞭にするために、1項目の注記情報のみが図1の参照番号「102」により明示的に示されているが、概略図100には、11項目の注記情報が比較的大きなベタの円により示されている。
【００１５】
概略図100は、外側の壁、内側の壁、部屋、廊下、内側の扉、外側の扉、柱などを含みうる。しかし、壁、廊下、扉の種類などは通常、建物地図ファイルでは明示的には識別されない。人間はそのような建物の要素を容易に識別できうるが、機械は通常そのような能力をもたない。本明細書で説明されるようないくつかの例示的な実装形態は、少なくともいくつかの建物構造を、1つまたは複数の機械的なデバイスにより識別することを可能にする。
【００１６】
さらに、建物情報ファイルは、比較的詳細度が低い略図を含んでもよい。そのような詳細度の低い略図が含む情報および/または要素は、比較的詳細度の高いコンピュータ支援設計(CAD)ファイルで見出されうる情報および/または要素よりも少ないことがある。限定ではなく例として、比較的詳細度が低い略図は、モールの画像または空港の地図、コンベンションセンターのような動的な場所の利用可能なCAD図などを含みうる。そのような略図は、いくつか例を挙げると、店、部屋、ターミナル/ゲート、展示物などのようなPoint of Interest(POI)を示す、閉じた多角形を、建物の外周に加えて有することが多い。必ずしも全てではないが、比較的詳細度が低い略図の多くが、扉の表示を欠いていることもある。言い換えると、比較的詳細度が低い略図では、内側の扉、外側の扉、または内側の扉と外側の扉の両方が明示的に示されていないことがあり、または、表されていないこともある。
【００１７】
機械が具体的な建物の要素を識別したとしても、機械が支援する道案内は必ずしも可能にはならないことがあることを理解されたい。例えば、ある人が、概略図100の地点#1(第1の比較的小さなベタの円)から地点#2(第2の比較的小さなベタの円)まで移動しようとすることがある。道案内指示を提供できるようにするために、概略図100に対応する建物構造のために経路案内グラフが作成されうる。ユーザーが、具体的な部屋番号、使用者、名付けられた場所、店、展示物、建物のサービスなどへの案内を求めることができるようにされる場合、注記情報が接続グラフと関連付けられ、そのような経路案内グラフを作成することができる。例示的な経路案内グラフおよび注記情報は、図2を特に参照して本明細書で以下でさらに説明される。
【００１８】
いくつかの例示的な実装形態では、対象の建物構造の、画像による地図、多角形による地図、または別の概略的な地図が利用可能でありうる。屋内での道案内は、地図の抽出および補間を用いて可能になりうる。地図の抽出により、概略的な地図に存在する地図情報は、いくつか例を挙げると、経路案内、位置決め、位置フィルタリング、道案内、インセンティブアプリケーション、検索などのような屋内での位置情報サービスを可能にする、よりアクセスしやすい情報に変換されうる。この変換において、略図ファイルで表されるような物理的な地図の特性が操作され、経路案内モジュールにより利用されうる構造に変換されうる。加えて、そのような抽出処理および変換処理は、自動化された方式で、および/または自動的に行われうる。実際には、地図の抽出および変換には、ユーザーは最小限しか関わらないか全く関わらない。さらに、そのような処理は、1つの地図につき数分程度で、またはさらに高速に完了しうる。
【００１９】
いくつかの例示的な実装形態の例示的な動作が、以下で説明される。以下の動作のいずれも、自動化することができる。以下の動作は、異なる順序で実行されてもよく、かつ/または完全にもしくは一部重複して実行されてもよい。さらに、所与の実装形態は、そのような動作の一部を利用することができる。第1に、点のグリッドが、建物構造に対応する概略図に重畳されうる。第2に、重畳された点のグリッドの複数の点から、線が投射されうる。第3に、投射された線に基づいて、重畳された点のグリッドの点が、内側の点または外側の点であるものと判定されうる。第4に、重畳された点のグリッドの隣接点が、障害のない接続で相互接続され、複数の独立の領域を決定しうる。したがって、全般的に地図の独立の領域が識別されうる。個々の独立の領域は、使用可能な独立の領域または使用不可能な独立の領域を含みうる。また、経路案内の仕組みが、所与の店、展示物、または他の「部屋」の境界を識別することによって、容易になりうる。
【００２０】
第5に、建物構造の外側の領域に対応する独立の領域が、確定されうる。建物の外側の領域(例えば、内側領域に対する)を識別することで、次に位置決め技術を組み込むことを容易にし、地図領域内でのユーザーの位置決めを改善することができる。第6に、独立の領域の広がりに少なくとも一部基づいて、廊下が発見されうる。第7に、POIのような建物の注記情報が、独立の領域に重ねられうる。図2に例として示されるように、部屋は、居住者または目的、さらには部屋の名前もしくは他の標識により、標識されうる。第8に、どの独立の領域が使用可能か、および使用不可能な独立の領域があるかどうかが、判定されうる。使用可能な領域は、ユーザーにより通行可能であると考えることができる。
【００２１】
第9に、対応するPOIまたは他の注記情報を有する独立の領域の、入口/出口点が識別されうる。シームレスな屋内での経路案内と、屋内から屋外への経路案内とを両方、より良く実現するために、全体の建物構造に対する入口の点および出口の点を、発見された廊下および外側の点に関して識別することもでき、経路案内グラフの一部として含んでもよく、または経路案内グラフと関連付けてもよい。加えて、緊急時行動および避難計画のためのアプリケーションは、そのような建物の入口および出口の点を利用することができる。第10に、複数の場所を一緒に結び、経路案内アプリケーションを動作させる経路案内グラフが、作成されうる。第11に、そのような決定された入口/出口の点を用いて、あるPOIから別のPOIへの道案内指示が、経路案内グラフを用いて提供されうる。
【００２２】
図2は、ある実装形態による、注記情報208への関連付けを含む例示的な経路案内グラフ206が作成された、建物情報の概略図200である。示されるように、概略図200は、少なくとも1つの使用可能な領域202、建物の外側の領域204、経路案内グラフ206、および注記情報208を含みうる。経路案内グラフ206を用いて、案内アプリケーションおよび/またはシステムは、例えば地点#1から地点#2へ移動するための道案内指示を、個人に提供することができる。
【００２３】
視覚的に明瞭にするために、いくつかの特定の例示される要素は、図2において参照番号により明示的には示されていないが、説明文が、どの特定の建物の要素がどの特定の描画上の要素により示されているかを示す。また、概略図200および経路案内グラフ206は、図2において示され本明細書で以下に示されるようないくつかの例示的な構成要素を含むが、特許請求される主題はそのようには限定されない。代わりに、所与の実装形態は、より多くの、より少ない、かつ/または異なる構成要素を含んでもよい。概略図200は、例えば、自動車産業展示会が開催中のコンベンションセンターに対応しうる。
【００２４】
いくつかの例示的な実装形態では、経路案内のトポロジーを示す経路案内グラフ206が、概略図200の建物構造に対応するように作成されうる。建物情報の例示的な分析の一部として、独立の領域が決定されうる。独立の領域は、いくつか例を挙げると、部屋、廊下、建物の外側などを含みうる。少なくとも1つの独立の領域が、建物の外側の領域204を含むものと確定されうる。1つまたは複数の別の独立の領域は、使用不可能な領域202を含むものと判定されうる。個人が立ち入ることのできる独立の領域は、使用可能な領域(例えば、入室可能な部屋、廊下など)を含むものと判定されうる。本明細書で用いられる場合、「部屋」(またはより一般的には区域)は、いくつか例を挙げると、オフィス、小部屋、休憩室、店舗、売店、フードコート、アパート/コンドミニアム、ブース、展示物、空港のゲート、アトラクション、他の定義可能な区域、およびこれらの組み合わせなどを含みうる。
【００２５】
注記情報208は、経路案内グラフ206と関連付けられ、異なる領域(例えば部屋、区域など)の間での道案内サービスまたは他の位置情報サービスをさらに実現することができる。限定ではなく例として、注記情報208は、部屋の指定(例えば部屋「A」、「1.24」など)、部屋の名前(例えば「取引部門」、「情報ブース」など)、部屋の目的(例えば「休憩室」、「食事」、「厨房」など)、部屋の居住者または使用者(例えば「ある大企業」、「工具」、「小型装置」、「空室」など)を含みうる。注記情報208は、いくつか例を挙げると、ロビー、フードコート、駐車場、ターミナルなどのような特定の区域と関連する情報を提供することもできる。経路案内グラフ206は、ある注記された領域から別の注記された領域への経路を含む、ある地点から別の地点への経路を描くのに用いることができる。単なる例として、道案内指示は、「ある大企業」の部屋「A」の近くの地点#1から「休憩室」の近くの地点#2までの案内とともに、ユーザーに(例えばモバイル機器を介して)提供されうる。
【００２６】
図3は、ある実装形態による、建物情報302および建物道案内ファイル308の例を示す、ブロック図300である。いくつかの例示的な実装形態では、建物情報302は、建物構造の少なくとも一部を表現する、任意の情報のセットを含んでもよい。建物情報302に少なくとも一部基づいて、建物道案内ファイル308が作成されうる。建物道案内ファイル308は、少なくとも1つの経路案内グラフ312、注記情報314、および/または1つもしくは複数の接続グラフ316を含みうる。経路案内グラフ312は、注記情報314に関連付けられ、かつ/または注記情報314と連携しうる。建物情報302、建物道案内ファイル308などは、電気信号(例えばデジタル信号)として実現されうる。
【００２７】
例として、建物情報302は、少なくとも1つの建物地図ファイル304を含みうる。建物地図ファイル304は、建物構造の少なくとも一部を表すデータ306(例えば、画像、CADフォーマット、DXFフォーマット、これらの何らかの組み合わせなど)を含みうる。建物情報302は、建物道案内ファイル308を作成する処理の前に、かつ/またはその間に、任意の1つまたは複数のフォーマットで表現されうる。例えば、建物道案内ファイル308の第1の部分は、建物情報302が第1のフォーマットにあるときに作成することができ、建物道案内ファイル308の第2の部分は、建物情報302が第2のフォーマットにあるときに作成することができる。建物情報302から、建物構造データ306が、建物道案内ファイル308を作成する(310)ように、抽出および/または変換されうる。
【００２８】
建物地図ファイル304および/またはそのデータ306は、注記情報も含みうる。そのような注記情報は、1つまたは複数のレイヤに編成されうる。地図ファイル中のどの注記レイヤまたは(もしあれば)複数の注記レイヤが、作製された経路案内グラフと関連付けられることになる注記レイヤであるかを識別するのに、使用者との対話が用いられうる。例えば、部屋の名前を関連付けることを望む場合、使用者が、そのようなレイヤの標識を選択または特定することができる。そのようなレイヤ(例えば「部屋レイヤ」、「Point of Interest」など)は、地図ファイルの中で別々に標識されうる。あるいは、注記レイヤの選択は、いくつか例を挙げると、自動的に行われてもよく、1つまたは複数の規則にしたがって自動化されてもよく、これらの組み合わせなどであってもよい。さらに、または代替的に、注記情報は、建物の要素の表現を含む「レイヤ」の一部を含みうる。
【００２９】
ある例示的な実装形態では、建物地図ファイル304は、1つまたは複数の建物構造の少なくとも一部に対応しうる。そのような建物構造の例は、限定はされないが、スタジアム、アリーナ、コンベンションセンター、モール、トンネルまたは橋または廊下などで接続された建物の集合体、空港、オフィスビル(壁/仕切りで再配置可能なものを含む)、これらの組み合わせなどを含む。建物地図ファイル304は、任意のフォーマットであってよい。例示的なフォーマットは、限定はされないが、CAD描画フォーマット(例えば、会場または施設の所有者により提供されるような)、Vectorフォーマット、画像フォーマット、これらの組み合わせなどを含む。画像フォーマットについては、エッジ検出処理がそのような地図画像に対して実行されうる。画像フォーマットは、いくつか例を挙げると、ウェブサイトから、(例えばモールの案内板、空港などの)表示された地図の写真を撮影するカメラ(例えばカメラ付き電話)から、印刷された地図をスキャンすることによって、インターネット上で示されている画像をコピーすることによって、または他の方法で、得ることができる。しかし、建物情報302も特許請求される主題も、これらの具体的な例には限定されない。
【００３０】
上述のように、建物の少なくとも一部の構造情報が、建物情報302から抽出されうる。そのような情報は、いくつか例を挙げると、壁、柱、障害物などに関連しうる。しかし、例えば、ある特定の壁が「POI A」の壁であることを示す情報、または所与の部屋が入口/出口の点を有することを示す情報は、存在しないことがある。それでも、建物の要素の情報を処理することができ、他の注記情報は抽出された情報から推測されうる。例えば、ある特定の部屋(例えば「部屋A」)の境界ボックスを識別するために、POI情報が建物地図ファイル304から抽出されうる。POI情報は、空間中の1つまたは複数の座標点(例えば、ドットに基づく地点、1つまたは複数の語に基づく領域、これらの組み合わせなど)が「POI A」を特定することを示しうる。そのようなPOI情報を用いて、例えば、これらの座標点に関連する最小の閉じた領域または独立の領域が、経路案内の目的で決定され、「POI A」と標識されうる。注記情報を関連付けるこの処理の例示的な手法が、図16および17を特に参照して本明細書において以下でさらに説明される。
【００３１】
図4は、ある実装形態による、例示的な建物情報400の概略図である。建物情報400は、(図3の)建物情報302の例であってよい。したがって、建物情報400は、図3を特に参照して上で説明されるフォーマットのいずれか、または他の種類のフォーマットとともに、機能することができる。いくつかの例示的な実装形態では、建物情報400は、1つまたは複数の建物の要素を表す構成要素402を含みうる。
【００３２】
示されるように、建物情報400は、(線で示されるような)壁402aおよび/または(多角形で示されるような)区域402bという、少なくとも2種類の構成要素402を含みうる。さらに、建物の要素を表す、より少ない、より多くの、かつ/または異なる構成要素402が、建物情報400の一部として代替的に含まれてもよい。建物情報400は、注記情報404も含みうる。図5から、そのような建物構造の一部を表す建物情報400を用いて例示的な概念を示す。
【００３３】
図5は、ある実装形態による、例示的な点のグリッド502が重畳された、建物情報400の概略図500である。したがって、示されるように、概略図500は、建物情報400および点のグリッド502を含みうる。いくつかの例示的な実装形態では、点のグリッド502は、建物情報400に重畳されうる。限定ではなく例として、点のグリッド502は、2つの軸(例えばx軸およびy軸)に沿って一定の間隔で位置する点のセットであってよい。点のグリッド502は、建物情報400の建物構造の、一部、実質的に全て、全て、または全てよりも広い範囲をカバーしてもよい。示されるように、点のグリッド502は、建物情報400の建物構造の外側の境界を超えて延びる。
【００３４】
点のグリッドの分解能または縮尺(例えば、2つの隣接点の間隔)は、変化してもよい。例えば、分解能は、いくつか例を挙げると、位置情報サービスで求められる正確さのレベル(例えば道案内の地図の正確さ)、建物情報の分析を分担しうるリソース(例えばメモリ、処理、および/または時間)の使用可能な量、部屋または他の独立の領域の実際のサイズもしくは予測されるサイズなどに基づいて、変化しうる。縮尺も、単一の建物構造における異なる所望の分解能のレベルに対応するように、単一の点のグリッドにおいて変化しうる。
【００３５】
点のグリッド502を重畳するための、建物構造の「グリッド化」を、任意の場所または地点で開始することができる。グリッド化は、建物または建物の階の全てを含む、建物構造の所望の部分の全体がカバーされるまで、ある地点から始めて、複数の方向に例えば(1フィート間隔のように)一定の間隔で点を追加することで、達成されうる。建物情報の建物構造の周り(例えば建物構造の北、南、東、西)の最大の領域が、(図3の)建物地図ファイル304から抽出される任意の構成要素402(例えば、(図4の)線402a、多角形402b、注記構成要素など)のx座標とy座標の両方の最小値および最大値を決めることによって、決定されうる。
【００３６】
図6は、ある実装形態による、建物情報に少なくとも一部基づいて、経路案内グラフを作成するための例示的な方法を示す、流れ図600である。示されるように、流れ図600は、4つの動作ブロック602、604、606、および608を含みうる。動作602〜608は特定の順序で示され説明されるが、特許請求される主題から逸脱することなく、方法は代替的な方式で実行されうることを理解されたい。また、流れ図600の動作は、互いに完全にまたは一部重複して実行されてもよい。加えて、以下の説明は、いくつかの他の図(例えば図3〜5)で示される具体的な態様および特徴に言及するが、方法は他の態様および/または特徴とともに実行されてもよい。
【００３７】
いくつかの例示的な実装形態では、動作602において、建物構造の少なくとも一部を表現する建物情報が取得されうる。例えば、(例えば、建物情報400として図4で示されるような)建物構造の少なくとも一部を表現する建物情報302が取得されうる。(例えばデジタル信号のような)建物情報302は、いくつか例を挙げると、メモリから取り出すことによって、無線通信リンクまたは有線通信リンクを介して受信することによって、画像の地図を(例えばカメラレンズ、センサなどを介して)得ることによって、または他の方法で、取得することができる。動作604において、点のグリッドが建物情報に重畳されうる。例えば、点のグリッド502が、建物情報400に重畳されうる。
【００３８】
動作606において、建物情報が、複数の点から線を投射することによって、重畳された点のグリッドを用いて分析されうる。例えば、建物情報400は、点のグリッド502の複数の点から線を投射することによって、重畳された点のグリッド502を用いて分析(例えば、試験、検査、研究、調査、処理など)されうる。例えば、(例えば構成要素402により表されるような)建物の要素に対する投射された線による1つまたは複数の衝突が検出されうる。例えば、そのような1つまたは複数の衝突に少なくとも一部基づいて、複数の点のうちの点が、外側の点に対応するか内側の点に対応するかが判定されうる。また、複数の独立の領域について、少なくとも1つの入口/出口の点が、そのような1つまたは複数の衝突に少なくとも一部基づいて、決定されうる。線を投射する例示的な実装形態が、図10、11、12、18、および19を特に参照して、以下でさらに説明される。
【００３９】
一般に、点のグリッド502を用いる建物情報400の分析により、いくつか例を挙げると、独立の領域を決定し、少なくとも1つの外側の領域に対する内側の領域を突き止め、使用不可能な独立の領域に対する使用可能な独立の領域を決定し、廊下を(例えば干渉を介して)発見することなどが可能になりうる。そのような分析の間、点のグリッドの隣接点が相互接続されて、接続グラフ316を形成することができる。点のグリッドを用いて建物情報を分析する例示的な手法が、図7を特に参照して本明細書において以下でさらに説明される。
【００４０】
動作608において、上記の分析に応じて経路案内グラフを作成することができ、経路案内グラフは、重畳された点のグリッドおよび建物情報に少なくとも一部基づきうる(例えば、少なくとも1つの経路案内グラフを表す電気信号(例えばデジタル信号)が生成されうる)。例えば、注記情報314への関連付けを有する経路案内グラフ312を、点のグリッド502に少なくとも一部基づき、かつ動作606の少なくとも一部に応じて、建物情報400の少なくとも一部のために作成することができる。例示的な実装形態では、経路案内グラフ312は、ある場所から別の場所への(例えば、あるPOIから別のPOIへの)経路を決定するために用いられうる。
【００４１】
そのような経路案内グラフは、同じ機器または異なる機器において次に使用するために(例えばデジタル信号を介して)保存されてもよく、かつ/または、作成された後すぐに、もしくは実質的にすぐに使用されてもよい。例えば、経路案内グラフのデータベースは、次に取り出すために、かつ位置情報サービスに対して次に適用するために、保存されうる。あるいは、機器(例えばモバイル機器)が経路案内グラフを作成し、オンデマンドで、道案内または他の位置情報アプリケーションのために経路案内グラフを使用してもよい。いずれにしても、建物構造に関連する道案内情報(例えば、方向、完全なまたは部分的な経路案内グラフなど)を、少なくとも1つの経路案内グラフを用いてモバイル機器に提供することができる。
【００４２】
図7は、ある実装形態による、建物情報を分析して経路案内グラフを作成するための、例示的な方法を示す流れ図700である。示されるように、流れ図700は、9個の動作ブロック702〜718を含みうる。動作702〜718は特定の順序で示され説明されるが、特許請求される主題から逸脱することなく、方法は代替の方式で実行されうることを理解されたい。また、流れ図700の動作は、互いに完全にまたは一部重複して実行されてもよい。加えて、以下の説明は、いくつかの他の図(例えば図3〜5および図9〜19)で示される具体的な態様および特徴に言及するが、方法は他の態様および/または特徴とともに実行されてもよい。
【００４３】
いくつかの例示的な実装形態では、動作702において、点が建物構造に対して外部の点であるか内部の点であるかが、投射された線に基づいて判定されうる。例えば、点のグリッド502の点が、建物情報400の建物構造に対して外部の点に相当するか内部の点に相当するかが、投射された線に基づいて判定されうる。線を投射するための例示的な機構が、図10を特に参照して本明細書において以下で説明される。動作702のための例示的な実装形態が、図11および12を特に参照して本明細書において以下でさらに説明される。
【００４４】
動作704において、グリッドの点の隣接点が、障害のない接続により相互接続され、少なくとも1つの接続グラフを形成することができる。例えば、接続が建物の要素と交差しない場合、点のグリッド502の所与の点から、所与の点と最大8個の近接する点との間に接続が確立されうる。(例えば閉じた形状および外側の点との接続が認められていない内側の点から)区域が形成される場合、そのような相互接続は、互いに接続されていない複数の接続グラフを形成することができる。
【００４５】
動作706において、複数の独立の領域が決定されうる。例えば、複数の独立の領域を、隣接点を障害のない接続によって相互接続することで形成される、複数の互いに接続されていない接続グラフに少なくとも一部基づいて、決定することができる。動作708において、建物構造の外側の少なくとも1つの独立の領域を、確定することができる。例えば、外側の点を含むものとして識別される少なくとも1つの点を用いて(例えば動作702で判定可能なように)、外側の独立の領域を確定することができる。動作704〜708の例示的な実装形態が、図13を特に参照して本明細書において以下でさらに説明される。
【００４６】
動作710において、1つまたは複数の廊下が、独立の領域の広がりに基づいて発見されうる。例えば、少なくとも1つの廊下は、決定された独立の領域に対応する1つまたは複数の広がりおよび少なくとも1つの所定の閾値に、少なくとも一部基づいて、建物情報400の一部として発見されうる。動作710の例示的な実装形態は、図14および15を特に参照して本明細書で以下にさらに説明される。
【００４７】
動作712において、建物の注記情報が、独立の領域に重畳されうる。例えば、注記情報404を独立の領域上に重畳することができ、独立の領域は、経路案内グラフを作成するための、障害のない接続により相互接続される点から形成される互いに接続されていない複数の接続グラフを含みうる。したがって、注記情報314は、経路案内グラフ312に関連付けられうる。動作712の例示的な実装形態は、図16および17を特に参照して、本明細書において以下でさらに説明される。
【００４８】
動作714において、どの独立の領域が使用可能か、および使用不可能な独立の領域があるかどうかが、注記情報(例えばPOI情報)に少なくとも一部基づいて判定されうる。例えば、注記情報を有するPOIに対応する独立の領域は、使用可能な独立の領域を含むと考えることができる。動作714の例示的な実装形態はまた、図16および17を特に参照して、本明細書において以下でさらに説明される。
【００４９】
動作716において、使用可能な独立の領域の入口/出口の点および、それらの対応する注記情報(例えばPoint of Interest)が、投射された線および発見された廊下に基づいて決定されうる。例えば、使用可能な独立の領域の入口/出口の1つまたは複数の点は、対応するPoint of Interestおよび、そこから投射される線がどのように廊下に到達するか(例えば、廊下に到達する前に複数の建物の要素に衝突するかどうか)に少なくとも一部基づいて、決定されうる。動作716の例示的な実装形態は、図18および19を特に参照して、本明細書において以下でさらに説明される。
【００５０】
動作718において、POIへの道案内指示および/またはPOIからの道案内指示が、少なくとも1つの経路案内グラフを用いて、入口/出口の点に少なくとも一部基づいて提供されうる。例えば、第1の地点から指定されたPOIまでの、ターンバイターンまたは他の道案内指示が、指定されたPOIに対応するように決定された1つまたは複数の入口/出口の点に少なくとも一部基づく少なくとも1つの経路案内グラフを用いて、提供されうる。
【００５１】
図8は、建物の廊下と建物の外側を区別するのが困難な、起こりうる例を示す図800である。示されるように、図800は、黒い領域802および複数の区域804を含み、明瞭にするために、これらのうちの一部のみが明示的に示されている。(図4の)建物情報400も参照すると、区域804が閉じた多角形から形成されることは明らかである。機械には、そのような閉じた多角形が全て使用不可能な領域であるように誤って見える可能性がある。廊下と建物の外側の間には、明確に画定された境界が存在しないことも、明らかである。そのような状況の結果、黒い領域802により示されるように、建物の廊下が、建物構造の外側の領域に「流出する」ことがある。
【００５２】
この可能性のある流出は、点のグリッドのうちのどの点が内側の点に相当し、点のグリッドのうちのどの点が外側の点に相当するかを判定することにより、少なくとも部分的に対処されうる。したがって、建物の内側と建物の外側の間(例えば、建物の廊下と建物の外側の領域の間)の境界が確立されうる。内側の点と外側の点を決定する例示的な手法が、図11〜13を特に参照して、本明細書において以下で説明される。
【００５３】
図9は、ある実装形態による、点のグリッド502が重畳された例示的な建物の部分900の概略図である。明瞭にするために示されているように、建物の部分900は、(図4の)建物情報400の一部(例えば断面)である。建物の部分900は、図9、ならびに図11、13、16および18において、さらに詳細に示すために拡大されている。図11、13、16および18は、全般に、建物の部分900を用いる異なる態様および/または実装形態を示す。図9において、建物の部分900は、壁402aおよび区域402bのような、構成要素402を含む。図9には示されていないが、廊下の「上側」部分をさらに画定する追加の壁の構成要素が、図18において示されている。
【００５４】
図10は、ある実装形態による、建物の情報の概略図に対して線を投射するための例示的な機構1000を示す。示されるように、機構1000は、点1004から投射される8つの線1002を含みうる。(開始点で互いに隣接する2つの線は、実質的に幾何学的な線を形成することに留意されたい。したがって、代替的におよび/または等価的に、8つの線1002を含む機構1000は、4つの幾何学的な線を含むと考えられうる。)点1004は、(例えば図5および9の)点のグリッド502の任意の所与の点に対応しうる。
【００５５】
いくつかの例示的な実装形態では、機構1000が、点のグリッドの複数の点において用いられ、建物情報を分析することができる。動作中、機構1000の少なくとも1つの線1002が、点1004から投射される。例えば、線1002は、(例えば、建物情報の外側の境界、所与の地図画像、または重畳された点のグリッドにおいて)線が1つまたは複数の建物の要素に1回または複数回衝突するまで、投射されうる。建物情報の態様を、そのような衝突および/または衝突が発生しないことに少なくとも一部基づいて、推測することができ、または判定することができる。図11を特に参照することを含めて、例が本明細書において以下でさらに説明される。
【００５６】
8つの線1002が機構1000について示されているが、これは例に過ぎない。そのような機構1000は、特許請求される主題から逸脱することなく、代替的に、より多くの線またはより少ない線1002を含んでもよい。図10で示されるように、機構1000の各線1002は、両方の最も近くの線1002から45度離れている。しかし、この45度の離隔は、例に過ぎない。より多くの線またはより少ない線1002が利用される場合、(例えば、任意の2つの近接する線1002の間の間隔を等しく保つように)最も近くの線1002との間の分離角は変更されうる。さらに、任意の2つの最も近くの線の間の分離角は、特許請求される主題から外れることなく、単一の機構1000内で異なっていてもよい(例えば、単一の機構1000において、2つの線1002が30度離れている一方で、他の2つの線が60度離れていてもよい)。
【００５７】
図11は、ある実装形態による、投射された線を用いて、点が外側の点であるか内側の点であるかを判定する、例示的な手法の概略図1100である。示されるように、概略図1100は、(図9に関して紹介されたような)建物の部分と、点1102、点1104、および点1106という3つの点とを含みうる。点1102、1104、および1106は、(図5の、しかし図11には明示的に示されていない)点のグリッド502からの点でありうる。(図10の、しかし図11には明示的に示されていない)機構1000は、各点1102、1104、および1106において利用され、そのような点が内側の点に相当するか外側の点に相当するかを判定することができる。
【００５８】
いくつかの例示的な実装形態では、ある点が内側の点に相当するか外側の点に相当するかに関する判定は、点から投射された線による衝突の回数に少なくとも一部基づきうる。例えば、衝突の回数は、所定の閾値と比較されうる。所与の点から投射された線による衝突の回数が所定の閾値を満たす(例えば、閾値以上である、閾値を超える、閾値より小さいなど)場合、そのような所与の点は、内側の点に相当すると判定されうる。例として、そのような所定の閾値は、8つの線1002を有する機構1000が用いられる場合は、またはその間は、5または6に等しくてよい。8つの投射された線を有する機構または異なる数の投射された線を有する機構を含む機構について、そのような所定の閾値の他の値を用いてもよい。代替的に、しかし等価的に、所与の点から投射される線による衝突の回数が所定の閾値を満たす(例えば、8つの投射された線との衝突が3回以下である)場合、所与の点は外部の点に相当すると判定されうる。
【００５９】
概略図1100を参照すると、所定の閾値を5に設定することができ、衝突の回数がそのような所定の閾値以上である場合に、衝突の回数が所定の閾値を満たしうる、例が示される。8つの線が、点1102から投射されうる。この例で示されるように、8つの線全てが建物の要素と衝突する。明瞭にするために、そのような衝突は実線により表される。したがって、8は5を超えるので、点1102は内側の点に相当すると判定されうる。
【００６０】
点1104から、8つの線が投射されうる。6つが実線で示され、建物の要素との衝突を表す。2つが点線で示され、建物の要素と衝突しないことを表す。6は5を超えるので、点1104は、内側の点に相当すると判定されうる。点1106から、8つの線が投射される。3つが実線で示され、建物の要素と衝突することを表す。5つが点線で示され、建物の要素と衝突しないことを表す。3は5以上ではないので、点1106は、外側の点に相当すると判定されうる。
【００６１】
図12は、ある実装形態による、点が外側の点か内側の点かを投射される線を用いて判定するための、例示的な方法を示す流れ図1200である。示されるように、流れ図1200は、7つの動作ブロック1202〜1208および1208a〜1208cを含みうる。これらの動作は特定の順序で示され説明されるが、特許請求される主題から逸脱することなく、方法は代替的な方式で実行されうることを理解されたい。また、流れ図1200の動作は、互いに完全にまたは一部重複して実行されてもよい。加えて、以下の説明は、いくつかの他の図(例えば図3〜5、10、および11)で示される具体的な態様および特徴に言及するが、方法は他の態様および/または特徴とともに実行されてもよい。
【００６２】
いくつかの例示的な実装形態では、動作1202において、点が点のグリッドから選択されうる。例えば、点1102、1104、または1106が、点のグリッド502から選択されうる。動作1204において、複数の線が、選択された点から投射されうる。例えば、複数の線1002は、選択された点1102、1104、または1106から投射されうる。
【００６３】
動作1206において、建物の要素に衝突する投射された線の数が決定されうる。例えば、1つまたは複数の構成要素402により表されるような建物の要素に衝突する投射された線1002の数が、判定されうる。動作1208において、選択された点が、例えば所定の回数の衝突に少なくとも一部基づいて、内側の点または外側の点を含むものとして識別されうる。例えば、選択された点1102、1104、または1106が、建物構造の内側の領域の一部または建物構造の外側の領域の一部である点に相当するものとして識別されうる。
【００６４】
動作1208a、1208b、および1208cは、動作1208を実施する例示的な手法を表す。動作1208aにおいて、建物構造に衝突する投射された線の数が所定の閾値を満たすかどうかが判定されうる。建物構造に衝突する線の数がそのような所定の閾値を満たさない場合、動作1208bにおいて、選択された点は、外側の点を含むものとして識別されうる。一方、建物構造に衝突する線の数が、そのような所定の閾値を満たす、またはそれを超えると判定される場合、動作1208cにおいて、選択された点は、内側の点を含むものとして識別されうる。例えば、建物構造に衝突する投射された線の数が、そのような所定の閾値を満たす、またはそれを超える場合、そのような線がそこから投射される選択された点は、内側の点に相当するものとして識別されうる。
【００６５】
図13は、ある実装形態による、複数の独立の領域を形成するように、障害のない接続により相互接続される隣接点の例を示す、概略図1300である。示されるように、概略図1300は、複数の独立の領域1302が、1つまたは複数の接続グラフを形成する相互接続された点から決定されうる、ある実装形態による例示的な建物の部分である。具体的には、11個の独立の領域1302が、概略図1300の例示的な建物の部分から決定されうる。図13では、6つのそのような独立の領域1302が明示的に示される。すなわち、独立の領域1302a、1302b、1302c、1302d、1302e、および1302fである。
【００６６】
いくつかの例示的な実装形態では、点のグリッド(例えば、図9の点のグリッド502)からの点が、障害のない接続により隣接点と相互接続され、1つまたは複数の接続グラフを形成することができる。点の相互接続は、例えば、あらゆる任意の点から開始することができる。壁または他の建物構造に直接位置する全ての点が、無視されうる。2点間の接続(例えば第1の地点から第2の地点への接続)は、例えば、そのような接続が、壁、柱などのような建物構造と衝突しない、かつ/または交差しない場合、障害がないと考えることができる。2つの点は、例えば、それらが近隣の点である(例えば、第2の点が第1の点の近くの8つの点のうちの1点である)場合、隣接していると考えることができる。例えば、点(i,j)に対して、接続は、障害がない場合、点(i,j)と、8個のすぐ周りの点(i-1,j)、(i+1,j)、(i,j-1)、(i,j+1)、(i-1,j-1)、(i+1,j+1)、(i-1,j+1)、および(i+1,j-1)の各々との間に描くことができる。さらに、外側の点および内側の点は、点線1304により示されるように、相互接続されないようにすることができる(例えば、そのような内側と外側との接続になるであろう接続は、独立の領域1302を決定するために、障害があると考えることができる)。しかし、特許請求される主題は、この特定の相互接続手法にそのように限定はされない。
【００６７】
障害のない接続で隣接点を相互接続することで、複数の接続グラフを形成することができ、複数の接続グラフは、建物情報が閉じた多角形または同様の分離された構造を含む場合には、互いに接続されていなくてもよい。そのような複数の互いに接続されていないグラフは、複数の独立の領域1302を含むものと考えることができる。具体的には、11個の独立の領域1302が示されているが、6個の独立の領域1302a、1302b、1302c、1302d、1302e、および1302fが、図13に明示的に示されている。図9および13と図4および5との比較から明らかなように、廊下の一部である独立の領域1302cが、概略図1300に部分的に示される。
【００６８】
同様の比較により、独立の領域1302eが、概略図1300に部分的に示されていることが明らかになる。図11および12を特に参照して本明細書において上で説明されたように、点1106は、外側の点に相当すると考えることができる。独立の領域1302が1つまたは複数の外側の点を含む場合、独立の領域1302は、外側の領域1302eのような外側の独立の領域を含むと確定されうる。したがって、独立の領域1302eは、建物構造に対して外側の領域を含むと考えることができる。独立の領域1302が内側の点を含む場合、独立の領域1302は、内側の領域1302a、1302b、1302c、1302d、および1302fのような内側の独立の領域を含むと確定されうる。
【００６９】
図14は、ある実装形態による、独立の領域の広がりに基づいて廊下を発見する例示的な手法の概略図1400である。示されるように、概略図1400は、独立の領域1402および広がり1404を含みうる。いくつかの例示的な実装形態では、独立の領域1402に対応する広がり1404は、建物構造の任意の廊下を発見するのに用いられうる。より具体的には、図14は、3つの独立の領域1402a、1402b、1402cを示す。示されるように、独立の領域1402aは広がり1404aに相当し、独立の領域1402bは広がり1404bに相当し、独立の領域1402cは広がり1404cに相当しうる。
【００７０】
一般に、広がり1404は、独立の領域1402を包含する、境界が最小の長方形であると考えることができる。より具体的には、広がりは以下の式を用いて決定されうる。
広がり=(Max(X)-Min(X))×(Max(Y)-Min(Y))
ここで、Xは対応する独立の領域のグリッドの点のx値の集合であり、Yは対応する独立の領域のグリッドの点のy値の集合である。しかし、特許請求される主題から逸脱することなく、広がりは異なる方式で決定されてもよい。
【００７１】
例示的な実装形態では、1つまたは複数の廊下領域が、各々の独立の領域の「広がり」を求めることにより識別されうる。廊下は、複数の計算された広がりおよび少なくとも1つの所定の閾値に少なくとも一部基づいて、推定されうる。そのような所定の閾値は、所与の建物構造の複数の計算された広がりに少なくとも一部基づいて、決定されうる。単なる例として、廊下は、広がりが複数の(最大で全ての)広がりの平均から標準偏差の3倍以上離れている、独立の領域として判定されうる。他の統計的な測定値を代わりに用いてもよい。あるいは、所定の閾値は、いくつか例を挙げると、各広がりの高さと幅の比に関して、各広がりと建物構造の全体の広がりとの比較に関して、またはその他に関して、確立されてもよい。しかし、特許請求される主題は、そのような所定の閾値の確立のされ方には限定されない。
【００７２】
図15は、ある実装形態による、独立の領域の広がりに基づいて廊下を発見するための例示的な方法を示す、流れ図1500である。示されるように、流れ図1500は、6個の動作ブロック1502、1504、および1504a〜1504dを含みうる。これらの動作は特定の順序で示され説明されるが、特許請求される主題から逸脱することなく、方法は代替的な方式で実行されうることを理解されたい。また、流れ図1500の動作は、互いに完全にまたは一部重複して実行されてもよい。加えて、以下の説明は、いくつかの他の図(例えば図3〜5、および14)で示される具体的な態様および特徴に言及するが、方法は他の態様および/または特徴とともに実行されてもよい。
【００７３】
いくつかの例示的な実装形態では、動作1502において、複数の独立の領域の広がりが計算されうる。例えば、複数の独立の領域1402の広がり1404が計算されうる。動作1504において、少なくとも1つの独立の領域が、複数の計算された広がりおよび少なくとも1つの所定の閾値に基づいて、廊下として識別されうる。例えば、独立の領域1402は、計算された広がり1404a、1404b、1404c、…および少なくとも1つの所定の閾値に基づいて、廊下として識別されうる。例えば、独立の領域1402cは、広がり1404cが、計算された広がり1404a、1404b、1404c、…の平均から、標準偏差の3倍よりも離れている場合、廊下として識別されうる。
【００７４】
動作1504a、1504b、1504c、および1504dは、動作1504を実施する例示的な手法を表す。当然、これらは単なる例示的な手法であり、特許請求される主題はこの点においては限定されない。動作1504aにおいて、ある特定の広がりが、複数の計算された広がりに依存する所定の閾値と比較されうる。例えば、ある特定の広がりは、複数の計算された広がりの平均を標準偏差の3倍分超えると反応するように設定される、所定の閾値と比較されうる。動作1504bにおいて、特定の広がりが所定の閾値を満たすかどうかが判定される。満たさない場合、次の広がりが、動作1504dで示されるように分析される。一方、(動作1504bで判定可能なように)特定の広がりが所定のしきい値を満たすと判定される場合、動作1504cにおいて、特定の広がりに対応する独立の領域が、廊下として識別されうる。
【００７５】
図16は、ある実装形態による、どの独立の領域が使用可能か、および使用不可能な独立の領域があるかどうかを判定する、例示的な手法の概略図1600である。示されるように、概略図1600は、1つまたは複数の使用可能な領域1602、1つまたは複数の使用不可能な領域1604、少なくとも1つの廊下1606、および注記情報404aの少なくとも1つの項目を含みうる。いくつかの例示的な実装形態では、注記情報に対応する独立の領域は、使用可能な領域を含むと判定することができ、注記情報に対応しない独立の領域は、使用不可能な領域を含むと判定することができる。そのような判定を実行するために、注記情報が、建物情報に対応する少なくとも1つの接続グラフに重畳されうる。そのような注記情報(例えば、図4の注記情報404)は、建物情報(例えば建物情報400)の一部として含まれうる。その場合、注記情報は、いくつか例を挙げると、情報の1つまたは複数のレイヤ、メタデータ、これらの組み合わせなどを含みうる。
【００７６】
いくつかの例示的な実装形態では、注記情報が、独立の領域に重畳されうる。例えば、注記情報404が、(図13の)独立の領域1302に重畳されうる。概略図1600に示されるように、注記情報404aの特定の項目が、建物情報302の位置と関連付けられうる。そのような位置は、建物情報の地図の一部であってよく、いくつか例を挙げると、ドットまたは矢印の座標、テキストの配置、アイコンの配置などに対応しうる。座標は、存在する場合、x座標、y座標の形態、または他の何らかの形態であってよい。限定ではなく例として、座標は、物理的な距離、計測された距離、ピクセルまたはドットの計数、これらの任意の組み合わせなどに関して提供されうる。しかし、特許請求される主題は、注記情報のそのような位置情報の形態、フォーマットなどによっては限定されない。
【００７７】
1つまたは複数の障害のない接続が、注記情報404aを独立の領域に対応する接続されていないグラフの点と接続する場合、注記情報404aは独立の領域に対応すると考えることができる。より具体的には、注記情報404の項目の所与の位置を、1つまたは複数の障害のない接続を用いて、独立の領域に対応する接続されていないグラフに接続することが可能でありうる。したがって、座標点または他の位置の点が、グリッド化された建物の地図領域に挿入されてもよく、障害のない接続が、その挿入された位置の点から点のグリッドの他の点まで描かれてもよい。これらのような例示的な方式では、抽出された注記層を、対応する独立の領域に関連付けることができる。
【００７８】
いくつかの例示的な実装形態では、独立の領域は、独立の領域が注記情報に対応するか/関連付けられているかどうかに関して、分析されうる。独立の領域が注記情報404に対応する場合、独立の領域は、使用可能な領域1602を含むと考えることができる。一方、独立の領域が注記情報(例えば、任意の注記情報、特定の関連する種類の注記情報など)に対応しない場合、独立の領域は、使用不可能な領域1604を含むと考えることができる。限定ではなく例として、図16については、注記情報404はPoint of Interest(POI)を含む。
【００７９】
POI-Aは、注記情報404aおよび独立の領域1602aに対応する。POI-BおよびPOI-Cは、2つの独立の領域1602bおよび1602cにそれぞれ対応する。示されるように、4つの他の独立の領域は、「D」、「E」、「F」、および「G」により示されるような、POI情報に対応する。POI情報に対応する独立の領域は、使用可能な独立の領域1602a、1602b、および1602cのような、使用可能な独立の領域1602であると決定されうる。(視覚的に明瞭にするために、「D」、「E」、「F」、および「G」の独立の領域は、使用可能な独立の領域に対応するものとしては別段示されていない。)廊下1606も、経路案内グラフにおいて廊下の地点と接続を移動することを許されているユーザーに関しては少なくとも、使用可能な領域であると考えることができる。
【００８０】
所与の独立の領域に対応するPOI情報がない場合、所与の独立の領域は、使用不可能な独立の領域1604であると判定されうる。示されるように、2つの使用不可能な独立の領域1604aおよび1604bが存在する。使用不可能な領域1604への経路案内は、特別に許可されたユーザーに限定されていてもよく、または防がれていてもよい。
【００８１】
図17は、ある実装形態による、建物情報を分析することにより識別されうる建物構造の例示的な態様を示す、概略図1700である。概略図1700は、(図4の)建物情報400の少なくとも部分的に分析されたバージョンの例に相当しうる。説明文1702により示されるように、外側を識別することができ、1つまたは複数の廊下を発見する(例えば推定する)ことができ、1つまたは複数の使用可能な領域を識別することができる。外側の領域は、黒く塗られている。推定される廊下は、薄い灰色に塗られている。使用可能な領域は、斜行平行模様に塗られており、POIを表すためにドットでマークされている。推定される廊下(灰色に塗られている)が外側の領域(黒く塗られている)と接する内側の点と外側の点の境界も、見ることができる。
【００８２】
経路案内は、そのような地図(例えば、扉の表示を省略した地図)では難しいことがある。廊下を発見して使用可能な領域を識別することはできるが、指定された出入口が存在しないことがある。したがって、指定されたPOIに推定された廊下のどの点からでも近づくことができるように見えうる場合、指定されたPOIにユーザーをどのように案内するかが不明確になることがある。一般に、例示的な実装形態では、各POIについて、1つまたは複数の方向(例えば、互いに45度離れている8つの方向)にある地図中の「最も近い」廊下の点が発見されうる。特定の方向にある廊下の点の分析において、2つ以上の建物の要素(略図の構成要素から知られうる)に衝突する場合、そのような特定の方向は無視されうる。2つ以上の建物の要素に衝突するということは、特定の方向は廊下に(少なくとも直接は)導かないということを示唆する。Point of Interestの独立の領域の入口/出口の点を決定するための例示的な実装形態が、図18および19を特に参照して、以下でさらに説明される。
【００８３】
図18は、ある実装形態による、使用可能な独立の領域の入口/出口の点を決定する例示的な手法の、概略図1800である。示されるように、概略図1800は、建物情報の地図上に位置する注記情報404b(例えばPOI)および少なくとも1つの廊下1606を含みうる。概略図1800は、複数の投射された線1802および1804と、入口/出口の点1806とも含みうる。
【００８４】
いくつかの例示的な実装形態では、複数の線が注記情報404bから投射されうる。1つまたは複数の、入口および/または出口(入口/出口)の点が、複数の投射された線および建物構造の少なくとも1つの廊下に少なくとも一部基づいて、所与の独立の領域に対して決定されうる。(図10の)機構1000を注記情報404bの位置で用いて、(やはり図10の)線1002を投射することができる。この例では、8つの線が投射されうる。8つの投射された線1802および1804が、図18に示される。
【００８５】
廊下に到達したかどうか、およびいくつの建物の構成要素と交差したかに基づいて、入口/出口の点は、投射された線が建物の要素と交わる点に存在すると(経路案内グラフのために)判定されうる。投射された線が廊下に達するまでに2つ以上の建物の構成要素と衝突した場合、そのような投射された線が入口/出口の点を画定すると考えることはできない。投射された光が廊下に達するまでに1つの建物の構成要素と衝突した場合、そのような投射された線は入口/出口の点を画定すると考えることができる。
【００８６】
概略図1800に示されるように、投射された線1802は入口/出口の点を画定することができるが、投射された線1804は入口/出口の点を何ら画定することができない。より具体的には、投射された線1802a、1802b、および1802cの各々は、建物の要素を表す1つの線と交わって廊下1606に到達するので、入口/出口の点1806a、1806b、および1806cをそれぞれ画定する。投射された線1804aおよび1804bは、廊下1606に到達する前に複数の建物の構成要素と交わるので、入口/出口の点を画定することができない。同様に、かつ/または類似して、投射された線1804c、1804d、および1804eは、建物の要素を表す1つの線と交わった後に廊下1606(または任意の他の廊下)に到達しないので、入口/出口の点を画定することはできない。
【００８７】
例示的な動作として、線は、廊下に到達するまで投射されてもよい。そのような投射された線が2つ以上の建物の構成要素と交わって廊下に到達する場合、入口/出口の点を画定することはできない。一方、そのような投射された線が1つのみの建物の構成要素と交わって廊下に到達する場合、入口/出口の点を画定することができる。あるいは、線は、1つの建物の構成要素と交わるまで投射されてもよい。1つの建物の構成要素と交わって廊下に到達した場合、そのような投射された線は入口/出口の点を画定することができる。一方、投射された線が、1つの建物の構成要素と交わっても廊下に到達しない場合、そのような投射された線は入口/出口の点を画定することはできない。
【００８８】
図19は、ある実装形態による、使用可能な独立の領域の入口/出口の点を決定するための、例示的な方法を示す流れ図1900である。示されるように、流れ図1900は、5つの動作ブロック1902〜1910を含みうる。動作1902〜1910は特定の順序で示され説明されるが、特許請求される主題から逸脱することなく、方法は代替的な方式で実行されうることを理解されたい。また、流れ図1900の動作は、互いに完全にまたは一部重複して実行されてもよい。加えて、以下の説明は、いくつかの他の図(例えば図3〜5、9、10、16、および18)で示される具体的な態様および特徴に言及するが、方法は他の態様および/または特徴とともに実行されてもよい。
【００８９】
いくつかの例示的な実装形態では、動作1902において、独立の領域の注記情報(例えばPOI)から、複数の線が投射されうる。例えば、所与の独立の領域の注記情報404bの位置から、複数の線1002(例えば線1802および1804)が投射されうる。動作1904において、廊下に到達するまでの、複数の投射された線の建物の要素との衝突が検出されうる。例えば、廊下1606へ到達するまでに、投射された線1802または1804が起こした衝突の回数が検出されうる。あるいは、投射された線1802または1804が、第1の建物の要素と衝突してから廊下1606に到達するかどうかが、検出されうる。
【００９０】
動作1906において、独立の領域の入口/出口の1つまたは複数の点が、そのような衝突に基づいて特定されうる。例えば、投射された線1802が廊下1606に到達するまでに1回衝突した場合、入口/出口の点1806が特定されうるが、投射された線1804が廊下1606に到達するまでに複数回衝突した場合(または投射された線1804が、廊下1606に到達する前に、少なくとも2つの建物の要素に衝突する場合)、入口/出口の点を特定することはできない。
【００９１】
動作1908において、分析すべき独立の領域がまだあるかどうかが判定されうる。分析すべき独立の領域がある場合、流れ図1900の方法を、動作1902において別の独立の領域を分析することによって継続することができる。分析すべき独立の領域がこれ以上ない場合、何らかの時点で(例えば、そのような分析が完了してからすぐに、分析が完了した後の何らかの時点で、など)、動作1910が実施されうる。動作1910において、指定されたPOIに道案内するための1つまたは複数の経路が、指定されたPOIに対応する独立の領域の特定された入口/出口の点に基づいて計算されうる。例えば、入口/出口の点1806および(図3の)経路案内グラフ312を用いて、指定された注記情報404bのPOIへ道案内するための経路が計算されうる。
【００９２】
あるいは、所与の使用可能な独立の領域の1つまたは複数の境界壁を調査して、そのような所与の独立の領域の入口/出口の点を決定してもよい。例えば、境界壁の反対側の別の独立の領域が、(廊下ではない独立の領域とは反対の)廊下を含むかどうかが確定されうる。所与の使用可能な独立の領域の境界壁の反対側にある特定の独立の領域が廊下を含む場合、その所与の使用可能な独立の領域について、少なくとも1つの入口/出口の点を特定することができる。例えば、少なくとも1つの出入口の点が、所与の利用可能な独立の領域と、廊下を含む特定の独立の領域とを分離する、境界壁に沿って(例えば境界壁の中央の近くに)位置しうる。
【００９３】
少なくとも、使用可能な領域を含む独立の領域の特定された入口/出口の点が、接続によって相互接続された後に、経路案内グラフが作成されうる。点のグリッドの点は、そのような経路案内グラフのノードを含んでもよく、点を相互接続する接続は、そのような経路案内グラフのエッジを含んでもよい。さらに、到達できない領域を使用不可能な場所として区分けするとともに、POI注記情報を、対応する独立の領域と関連付けてもよく、または接続してもよい。ある場所から別の場所への経路案内は、経路案内グラフにおいて2つの点/ノードを選択し、残りのグラフに対して最短経路アルゴリズム(例えばダイクストラ法など)を実行することによって、実施されうる。道案内指示(限定はされないが、リアルタイムの案内および/またはターンバイターンの案内を含む)は、そのような経路案内グラフを用いて提供されうる。さらに、代替的にかつ/または追加で、他の位置情報サービス(例えば位置決め、位置フィルタリングなど)を、作成された経路案内グラフに少なくとも一部基づいて、ユーザー(例えばモバイル機器のユーザー)に提供することができる。
【００９４】
図18および19を特に参照して本明細書において説明された例示的な実装形態の下では、複数の入口/出口の点が単一のPOIに対して決定されうる。したがって、所与のPOIに対して、最大でk個の入口/出口の点が存在しうる(例えば、k≦8であり、kは投射された線の数により決まる)。目的地のPOIから別の場所(例えば廊下)への経路が要求された場合、目的地のPOIの複数の特定された入口の点(例えば最大でk個の入口の点)に対して、手間が最小の経路が計算されうる。複数の経路または単一の経路(例えば手間が最小の経路)が、要求したユーザーに示されうる。ユーザーが第1のPOIから第2のPOIまでの経路を求めることを望む場合、最大でk1×k2個の経路を計算することができ(このとき第1のPOIはk1個の出口の点を有し、第2のPOIはk2個の入口の点を有する)、経路のうちの1つまたは複数(例えば最短経路または複数の経路)を選択してユーザーに提供することができる。
【００９５】
図20は、ある実装形態による、例示的な機器2000を示す概略図であり、例示的な機器2000は、略図を用いる建物用の経路案内グラフの1つまたは複数の態様を実施することができる。示されるように、機器2000は、少なくとも1つのプロセッサ2002、1つまたは複数のメモリ2004、少なくとも1つの通信インターフェース2006、少なくとも1つの電源2008、および、SPS(衛星測位システム)ユニット(SPSU)(明確には示されていない)のような他の構成要素2010を含みうる。メモリ2004は、命令2012を含むものとして示されている。しかし、代替的には、機器2000は、示されている構成要素よりも、多くの、少ない、および/または異なる構成要素を含んでもよい。
【００９６】
いくつかの例示的な実装形態では、機器2000は、電子機器を含んでもよく、かつ/または備えてもよい。機器2000は、例えば、少なくとも1つのプロセッサおよび/またはメモリを有する任意の電子機器を含んでもよい。機器2000の例は、限定はされないが、固定式の処理機器(例えば、デスクトップコンピュータ、1つまたは複数のサーバコンピュータ、少なくとも1つの遠隔通信ノード、インテリジェントルータ/スイッチ、これらの何らかの組み合わせなど)、移動式の処理機器(例えば、ノートブックコンピュータ、携帯情報端末(PDA)、ネットブック、スレートまたはタブレット型コンピュータ、持ち運び式娯楽機器、携帯電話、スマートフォン、移動局、これらの何らかの組み合わせなど)などを含む。
【００９７】
電源2008は、機器2000の構成要素および/または回路に電力を供給することができる。電源2008は、電池のような持ち運び可能な電源であってもよく、または、自動車、家、または他の建物のコンセントのような、固定式の電源であってもよい。電源2008はまた、太陽または炭素燃料を用いる発電機のような、可搬型の電源であってもよい。電源2008は、機器2000と一体であっても分離していてもよい。
【００９８】
プロセッサ2002は、任意の1つまたは複数の処理ユニットを含みうる。メモリ2004は、プロセッサ2002により実行可能でありうる命令2012(例えば、プログラム、アプリケーションなど、またはこれらの一部、使用可能なデータ構造、プロセッサ実行可能命令、コード、これらの何らかの組み合わせなど)を保存し、格納し、または命令2012へのアクセスを提供することができる。1つまたは複数のプロセッサ2002によるそのような命令2012の実行により、機器2000は、特別な用途のコンピューティング機器、装置、プラットフォーム、これらの組み合わせなどに変換されうる。
【００９９】
命令2012は、経路案内グラフ命令2012a、建物情報2012b、および/または建物道案内ファイル2012cを含みうる。建物情報2012bは、例えば、(図3の)建物情報302(例えば(図4の)建物情報400)に対応しうる。建物道案内ファイル2012cは、例えば、(図3の)建物道案内ファイル308に対応していてもよく、建物道案内ファイル308は、経路案内グラフ312、1つまたは複数の接続グラフ316、および/または関連する注記情報314を含みうる。経路案内グラフ命令2012aは、例えば、(図6、7、12、15、および19の)流れ図600、700、1200、1500、および/または1900の1つまたは複数の実施を実現することができる、命令に相当しうる。経路案内グラフ命令2012aを実行して、例えば、建物情報2012bに少なくとも一部基づいて、建物道案内ファイル2012cの少なくとも一部を生成することができる。明確には示されていないが、命令2012は、建物道案内ファイル2012cを用いて1つまたは複数の位置情報サービス(LBS)を提供するための命令も含みうる。
【０１００】
例示的な実装形態では、サーバおよび/または遠隔通信ノードのような固定式の処理機器が、経路案内グラフ命令2012aを実行して、建物情報2012bに少なくとも一部基づいて、建物道案内ファイル2012cを作成することができる。同一のまたは異なる固定式処理機器が、建物道案内ファイル2012cを用いて、例えば、SPSUを含みうるモバイル機器にLBSを提供することができる。あるいは、そのような固定式の処理機器は、建物道案内ファイル2012cをモバイル機器に提供して、いくつかのLBSを可能にする、またはいくつかのLBSのさらなる実行を可能にすることができる。さらに別の代替形態として、モバイル機器は、経路案内グラフ命令2012aを含み、取得された(例えばメモリから取り出された、オンデマンドでダウンロードされた、写真を撮影することで取得された、など)建物情報2012bから建物道案内ファイル2012cを作成することができる。他の代替形態も、特許請求される主題から逸脱することなく、代わりに実施することができる。
【０１０１】
通信インターフェース2006は、機器2000と他の機器(例えば、および/または使用する人)との間の1つまたは複数のインターフェースを提供することができる。したがって、通信インターフェース2006は、画面(例えばタッチスクリーン)、スピーカー、マイクロフォン、キーボード/キー、ノブ/ホイール、または人と機器の間の他の入力/出力機構を含んでもよい。そのような人と機器の間の入力/出力機構は、存在する場合、検索および/または道案内の補助を要求するために、または、検索結果および/または道案内情報を視覚的にかつ/または音声により受け取るために、人により用いられうる。通信インターフェース2006は、送受信機(例えば送信機および/または受信機)、無線、アンテナ、有線インターフェースコネクタまたは他のそのような装置、これらの何らかの組み合わせなどを含み、無線信号および/または有線信号を(例えば無線通信リンクまたは有線通信リンクを通じて)通信することができる。通信インターフェース2006は、機器2000の他の構成要素間の、バスまたは他の相互接続としての役割も果たしうる。他の構成要素2010は、存在する場合、1つまたは複数の他の様々なセンサ、機構などを含んでもよい。
【０１０２】
本明細書で説明された方法は、具体的な特徴および/または例にしたがって、用途に応じて様々な手段で実装されうる。例えば、そのような方法は、ハードウェア、ファームウェア、ソフトウェア、個別の/固定された論理回路、これらの任意の組み合わせなどで実装されうる。ハードウェアによる実装形態では、例えば、プロセッサ/処理ユニットは、いくつか例を挙げると、1つまたは複数の特定用途向け集積回路(ASIC)、デジタルシグナルプロセッサ(DSP)、デジタルシグナルプロセシングデバイス(DSPD)、プログラマブル論理デバイス(PLD)、フィールドプログラマブルゲートアレイ(FPGA)、プロセッサ全般、コントローラ、マイクロコントローラ、マイクロプロセッサ、電子的なデバイス、命令を実行するようにプログラムされた、かつ/もしくは本明細書で説明される機能を実行するように設計された、他のデバイスまたはユニット、および/またはこれらの組み合わせの中に、実装されうる。本明細書において、用語「制御論理回路」は、ソフトウェア/ファームウェアで実装される論理回路、ハードウェア(例えば個別の/固定された論理回路)、これらの任意の組み合わせなどを包含しうる。
【０１０３】
ファームウェアおよび/またはソフトウェアによる実装形態では、方法は、本明細書で説明される機能を実行する命令を有するモジュール(例えば、プロシージャ、関数など)により実装されうる。命令を有形に具現化する任意の機械可読媒体が、本明細書で説明される方法を実装する際に用いられうる。例えば、ソフトウェアコードをメモリに保存することができ、プロセッサにより実行することができる。メモリは、プロセッサ内に実装されてもよく、プロセッサの外側に実装されてもよい。本明細書で用いられる用語「メモリ」は、任意の種類の、長期的な、短期的な、揮発性の、非揮発性の、または他の記憶メモリ/媒体を指し、特定の種類のメモリまたは特定の数のメモリ、または記憶が保存される媒体の特定の種類に何ら限定されることはない。
【０１０４】
ファームウェアおよび/またはソフトウェアによる実装形態では、機能は、1つまたは複数の命令またはコードとして、コンピュータ可読媒体に保存されうる。例には、データ構造でエンコードされたコンピュータ可読媒体と、コンピュータプログラムによりエンコードされたコンピュータ可読媒体とを含む。コンピュータ可読媒体は、製造物品の形態であってもよい。コンピュータ可読媒体は、物理的なコンピュータ記憶媒体を含む。記憶媒体は、コンピュータによりアクセスされうる任意の利用可能な媒体であってよい。限定ではなく例として、そのようなコンピュータ可読媒体は、RAM、ROM、EEPROM、CD-ROMもしくは他の光ディスク記憶装置、磁気ディスク記憶装置、半導体記憶装置、もしくは他の記憶機器、または、命令またはデータ構造の形態で所望のプログラムコードを保存するのに用いることができ、コンピュータによりアクセスすることができる、任意の他の媒体を含みうる。本明細書で用いられる場合、ディスク(disk)およびディスク(disc)は、コンパクトディスク(CD)、レーザーディスク（登録商標）、光ディスク、デジタル多目的ディスク(DVD)、フロッピー（登録商標）ディスクおよびブルーレイディスクを含み、ディスク(disk)は通常データを磁気的に再生し、ディスク(disc)はレーザーによりデータを光学的に再生する。上記の組み合わせも、コンピュータ可読媒体の範囲に含まれるべきである。
【０１０５】
コンピュータ可読媒体への保存に加えて、命令および/またはデータは、通信装置に含まれる伝送媒体上の信号として提供されてもよい。例えば、通信装置は、命令およびデータを示す信号を有する送受信機を含んでもよい。命令およびデータは、1つまたは複数の処理ユニットに特許請求の範囲で概説される機能を実装させるように、構成される。つまり、通信装置は、開示される機能を実行するための情報を示す信号を有する、伝送媒体を含む。第1の時間では、通信装置に含まれる伝送媒体は、情報の第1の部分を含み開示される機能を実行することができるが、第2の時間では、通信装置に含まれる伝送媒体は、開示される機能を実行するための情報の第2の部分を含んでもよい。
【０１０６】
電子機器は、Wi-Fi/WLANまたは他の無線ネットワークとともに動作することもできる。例えば、位置データが、Wi-Fiまたは他の無線ネットワークを介して取得されうる。Wi-Fi/WLAN信号に加えて、無線/移動式の機器は、全地球測位システム(GPS)、Galileo、GLONASS、NAVSTAR、QZSS、これらのシステムの組み合わせの衛星を用いるシステム、または将来開発される任意のSPSからの信号でありうる、衛星からの信号を受信することもでき、上述の各システムは、本明細書では衛星測位システム(SPS)と一般に呼ばれる。さらに、本明細書で説明される実装形態は、擬似衛星または衛星と擬似衛星の組み合わせを利用する、測位システムとともに用いられうる。擬似衛星は通常、擬似ランダムノイズ(PRN)符号または、Lバンド(または他の周波数)の搬送波信号に変調された他の測距コード(例えば、GPSまたはCDMAセルラー信号に類似した)をブロードキャストする、地上の送信機であり、上記の搬送波信号はGPS時間と同期されうる。各々のそのような送信機は、遠隔の受信機による識別を可能にするために、固有のPNコードを割り当てられうる。擬似衛星は、トンネル、鉱山、建物、アーバンキャニオン、または他の囲まれた領域のような、軌道衛星からのSPS信号が利用できない状況では、特に有用でありうる。擬似衛星の別の実装形態は、無線ビーコンとして知られている。本明細書で用いられる用語「衛星」は、擬似衛星、擬似衛星の等価物、および同様のかつ/または類似の技術も含むべきである。本明細書で用いられる場合、用語「SPS信号」は、擬似衛星または擬似衛星の等価物からのSPSのような信号も含むべきである。いくつかの実装形態は、フェムトセル、またはフェムトセルを含むシステムの組み合わせにも、適用されうる。
【０１０７】
例示的な実装形態では、SPSU(存在すれば)は、1つまたは複数のSPSシステムを用いて、機器2000の位置を決定することができてもよい。したがって、本明細書で説明される例示的な実装形態は、様々なSPSとともに用いられうる。SPSは通常、エンティティが、送信機から受信された信号に少なくとも一部基づいて、地上または上空での自身の位置を決定することを可能にするように位置付けられた、送信機のシステムを含む。そのような送信機は、必須ではないが通常、一定の数のチップの繰り返し擬似ランダムノイズ(PN)符号でマークされた信号を送信し、地上の管制局、ユーザー装置、および/または宇宙船に存在しうる。具体的な例では、そのような送信機は、地球軌道宇宙機(SV)に存在しうる。例えば、全地球測位システム(GPS)、Galileo、GlonassまたはCompassのような全地球航法衛星システム(GNSS)の集合のSVは(例えば、GPSのように各衛星に対して異なるPN符号を用いて、またはGlonassのように異なる周波数に対して同一の符号を用いて)、その集合内の他のSVにより送信されたPN符号と区別可能なPN符号によりマークされる信号を送信することができる。いくつかの態様によれば、本明細書で提示される技術は、SPSのための地球規模のシステム(例えばGNSS)には限定されない。例えば、本明細書で提供される技術は、日本の準天頂衛星システム(QZSS)、インドのインド地域航法衛星システム(IRNSS)、中国の北斗など、ならびに/または、1つもしくは複数の地球規模のおよび/もしくは地域的な航法衛星システムに関連しうる、もしくはそれらとともに用いることが可能にされうる、様々な補強システム(例えば、静止衛星型衛星航法補強システム(SBAS))に、適用されてもよく、またはそれらとともに用いることが可能であってもよい。限定ではなく例として、SBASは、例えば、広域補強システム(WAAS)、European Geostationary Navigation Overlay Service(EGNOS)、多目的衛星用航法補強システム(MSAS)、GPS Aided Geo Augmented Navigation or GPS and Geo Augmented Navigation system(GAGAN)、および/または同様のもののような、統合情報、差分補正などを提供する補強システムを含みうる。したがって、本明細書で用いられる場合、SPSは、1つまたは複数の地球規模のおよび/もしくは地域的な航法衛星システムならびに/または補強システムの任意の組み合わせを含んでもよく、SPS信号は、SPS信号、SPSのような信号、および/またはそのような1つまたは複数のSPSと関連する他の信号を含んでもよい。
【０１０８】
モバイル機器/移動局は、セルラー型の、または他の無線通信機器、個人用通信システム(PCS)機器、個人用ナビゲーション機器(PND)、個人情報管理装置(PIM)、携帯情報端末(PDA)、ラップトップ、タブレット、または、無線通信および/または道案内信号を受信することができる他の適切な機器のような、機器を指す。衛星信号の受信、支援データの受信、および/または位置に関する処理が、機器で行われるかPNDで行われるかには関係なく、モバイル機器は、短距離の無線、赤外線、有線接続、または他の接続などによって、個人用ナビゲーション機器(PND)と通信する機器を含むことも意図されている。また、モバイル機器は、無線通信機器、コンピュータ、ラップトップなどを含む全ての機器を含むことが意図されており、上記の機器類は、衛星信号の受信、支援データの受信、および/または位置に関連する処理が、機器で行われるか、サーバで行われるか、ネットワークに関連する他の機器で行われるかには関係なく、インターネット、Wi-Fi、または他のネットワークを介するなどして、サーバと通信することができる。上記の任意の動作可能な組み合わせも、モバイル機器であると考えることができる。
【０１０９】
この発明を実施するための形態の一部は、特定の装置または専用のコンピューティング機器もしくはプラットフォームのメモリに保存されうるバイナリデジタル信号に対する動作の、アルゴリズムまたは記号による表現として提示されている。この特定の明細書においては、「特定の装置」などの用語は、プログラムソフトウェア/命令からの命令にしたがって特定の機能を実行するようにプログラムされた後の、汎用コンピュータを含む。アルゴリズムによる説明または記号による表現は、信号処理または関連技術の当業者が、自身の成果の本質を他の当業者に伝えるために用いられる、技法の例である。アルゴリズムとはここでは、かつ一般的に、所望の結果につながる、一貫した一連の動作または同様の信号処理であると考えることができる。これに関連して、動作または処理は、物理量の物理的な操作に関わる。必須ではないが通常、そのような物理量は、保存し、移送し、組み合わせ、比較し、送信し、受信し、または他の方法で操作することができる、電気信号および/または磁気信号の形態をとりうる。
【０１１０】
主に一般に用いられているという理由で、そのような信号を、ビット、データ、値、要素、シンボル、文字、変数、語、数、番号などと呼ぶことが便利なことがあるということがわかっている。しかし、これらの用語および類似の用語は全て、適切な物理量と関連付けられるべきであり、便宜的な呼び方に過ぎないということを理解されたい。別段特に述べられない限り、上の議論から明らかなように、「処理する」、「計算する」、「算出する」、「決定する」、「確定する」、「分析する」、「比較する」、「識別する」、「関連付ける」、「取得する」、「実行する」、「適用する」、「調査する」、「投射する」、「作成する」、「模擬する」、「相互接続する」、「重畳する」、「検出する」、「発見する」、「提供する」などのような用語を利用する、本明細書の議論の全体が、専用コンピュータまたは同様の専用の電子的なコンピューティング機器のような、特定の装置の動作または処理を指すことが、理解されよう。したがって、この明細書においては、専用のコンピュータまたは同様の専用の電子的なコンピューティング機器は、信号を操作または変換することができ、上記の信号は通常、専用のコンピュータまたは同様の専用の電子的なコンピューティング機器の、メモリ、レジスタ、もしくは他の情報記憶機器、伝送機器、または表示機器の中で、物理的な、電気的な量、電子的な量、および/または磁気的な量として表される。
【０１１１】
例示的な特徴であると現在考えられていることが、示されて説明されてきたが、特許請求される主題から逸脱することなく、様々な他の修正を行うことができ、等価物により置換できることが、当業者には理解されよう。加えて、本明細書で説明される主要な概念から逸脱することなく、多くの修正が、具体的な状況を特許請求される主題の教示に適合させるために行われうる。したがって、特許請求される主題は開示される具体的な例に限定されず、そのような特許請求される主題は、添付の特許請求の範囲およびその等価物の範囲にある、全ての態様も含みうることが、意図されている。
【符号の説明】
【０１１２】
100 建物情報の概略図
102 注記情報
200 建物情報の概略図
202 使用可能な領域
204 建物の外側の領域
206 経路案内グラフ
302 建物情報
304 建物地図ファイル
306 データ
308 建物道案内ファイル
312 経路案内グラフ
314 注記情報
316 接続グラフ
502 点のグリッド
1702 説明文
2000 機器
2002 プロセッサ
2004 メモリ
2006 通信インターフェース
2008 電源
2010 他の構成要素
2012 命令
2012a 経路案内グラフ命令
2012b 建物情報
2012c 建物道案内ファイル
【特許請求の範囲】
【請求項１】
建物構造の少なくとも一部を表現する建物情報を表す電気信号を得るステップと、
前記建物情報に点のグリッドを重畳するステップと、
前記重畳された点のグリッドの複数の点から複数の線を投射することによって、前記重畳された点のグリッドを用いて前記建物情報を分析するステップと、
前記分析に応じて、かつ、前記重畳された点のグリッドと前記建物情報とに少なくとも一部基づいて、少なくとも1つの経路案内グラフを表す電気信号を生成するステップと
を含む、方法。
【請求項２】
前記分析するステップが、
前記重畳された点のグリッドの複数の点が、前記建物構造に対して外側の点を含むか内側の点を含むかを、判定するステップ
を含む、請求項1に記載の方法。
【請求項３】
前記判定するステップが、
前記複数の点の選択された点から複数の線を投射するステップと、
前記建物構造の建物の要素に衝突する前記複数の投射された線の数を検出するステップと、
建物の要素に衝突する前記複数の投射された線の前記数に少なくとも一部基づいて、前記建物構造の内側の点または外側の点を含むものとして、前記選択された点を識別するステップと
を含む、請求項2に記載の方法。
【請求項４】
前記識別するステップが、
建物の要素に衝突する前記複数の投射された線の前記数が、少なくとも1つの所定の閾値を満たすかどうかを判定するステップと、
建物の要素に衝突する前記複数の投射された線の前記数が、前記所定の閾値を満たすと判定される場合に、内側の点を含むものとして前記選択された点を識別するステップと
を含む、請求項3に記載の方法。
【請求項５】
前記重畳された点のグリッドの隣接点の少なくとも一部を障害物のない接続で相互接続し、複数の接続されていないグラフを形成するステップと、
前記複数の接続されていないグラフに少なくとも一部基づいて、複数の独立の領域を決定するステップと
をさらに含む、請求項2に記載の方法。
【請求項６】
前記外側の点のうちの1つまたは複数に少なくとも一部基づいて、前記建物構造の外側にある前記複数の独立の領域の少なくとも1つの独立の領域を確定するステップ
をさらに含む、請求項5に記載の方法。
【請求項７】
前記建物構造の複数の独立の領域に対応する複数の広がりに少なくとも一部基づいて、前記建物構造の1つまたは複数の廊下を発見するステップ
をさらに含む、請求項1に記載の方法。
【請求項８】
前記発見するステップが、
前記建物構造の前記複数の独立の領域の複数の広がりを計算するステップと、
前記複数の計算された広がりおよび少なくとも1つの所定の閾値に基づいて、前記複数の独立の領域の少なくとも1つの独立の領域を、少なくとも1つの廊下を含むものとして識別するステップと
を含む、請求項7に記載の方法。
【請求項９】
前記識別するステップが、
前記複数の計算された広がりの特定の広がりと、前記複数の計算された広がりにより決まる前記少なくとも1つの所定の閾値とを比較するステップと、
前記特定の広がりが前記少なくとも1つの所定の閾値を満たすかどうか判定するステップと、
前記特定の広がりが前記少なくとも1つの所定の閾値を満たすと判定された場合に、前記特定の広がりに対応する特定の独立の領域を、前記建物構造の少なくとも1つの廊下を含むものとして識別するステップと
を含む、請求項8に記載の方法。
【請求項１０】
前記重畳された点のグリッドに対して定義可能な複数の独立の領域に、建物の注記情報を重畳するステップと、
前記複数の独立の領域のうちのどの1つまたは複数の独立の領域が使用可能であるか、および、前記複数の独立の領域に使用不可能な独立の領域があるかどうかを、前記重畳された建物の注記情報に少なくとも一部基づいて、判定するステップと
をさらに含む、請求項1に記載の方法。
【請求項１１】
前記分析するステップが、
前記複数の投射された線と、前記建物構造の少なくとも1つの廊下とに少なくとも一部基づいて、複数の独立の領域の1つもしくは複数の入口および/または出口の点を決定するステップ
を含む、請求項1に記載の方法。
【請求項１２】
前記決定するステップが、
前記複数の独立の領域の特定の独立の領域に関連するPoint of Interestに対応する、前記重畳された点のグリッドの点から複数の線を投射するステップと、
前記建物構造の前記少なくとも1つの廊下に到達するまでの、前記複数の投射された線の少なくとも1つの建物の要素との1つまたは複数の衝突を検出するステップと、
前記少なくとも1つの建物の要素との前記1つまたは複数の衝突に少なくとも一部基づいて、前記特定の独立の領域の前記1つもしくは複数の入口および/または出口の点を特定するステップと
を含む、請求項11に記載の方法。
【請求項１３】
関連する独立の領域に対して決定される前記1つもしくは複数の入口および/または出口の点に少なくとも一部基づいて、前記建物構造のPoint of Interestへ道案内するための1つまたは複数の経路を計算するステップ
をさらに含む、請求項11に記載の方法。
【請求項１４】
前記分析するステップが、
特定の独立の領域が境界壁の反対側にあるかどうかを判定することに少なくとも一部基づいて、複数の独立の領域の1つもしくは複数の入口および/または出口の点を決定するステップであって、前記境界壁が、前記複数の独立の領域の所与の使用可能な独立の領域と、廊下を含む前記特定の独立の領域との間に存在する、ステップ
を含む、請求項1に記載の方法。
【請求項１５】
前記建物構造に関連し前記少なくとも1つの経路案内グラフから少なくとも部分的に導出される道案内情報の、モバイル機器への送信を開始するステップ
をさらに含む、請求項1に記載の方法。
【請求項１６】
前記分析するステップが、
前記複数の投射された線の投射が、前記建物構造の1つまたは複数の建物の要素に衝突するかどうかを検出するステップ
を含む、請求項1に記載の方法。
【請求項１７】
前記分析するステップが、
前記重畳された点のグリッドの複数の点に対し、前記検出するステップに少なくとも一部基づいて、前記複数の点が前記建物構造に対して外側の点を含むか内側の点を含むかを判定するステップと、
前記建物構造の複数の独立の領域に対して、前記検出するステップに少なくとも一部基づいて、前記複数の独立の領域の少なくとも1つの入口および/または出口の点を決定するステップと
をさらに含む、請求項16に記載の方法。
【請求項１８】
専用のコンピューティング機器に前記方法を実施するように指示するための命令を、前記専用のコンピューティング機器によって実行するステップ
をさらに含む、請求項1に記載の方法。
【請求項１９】
命令を保存するための少なくとも1つのメモリと、
前記命令を実行して、
建物構造の少なくとも一部を表現する建物情報を得、
前記建物情報に点のグリッドを重畳し、
前記重畳された点のグリッドの複数の点から複数の線を投射することによって、前記重畳された点のグリッドを用いて前記建物情報を分析し、
前記分析に応じて、かつ、前記重畳された点のグリッドと前記建物情報とに少なくとも一部基づいて、少なくとも1つの経路案内グラフを作成する
ための、1つまたは複数のプロセッサと
を含む、専用のコンピューティング機器。
【請求項２０】
前記建物情報を分析するために、前記1つまたは複数のプロセッサがさらに、
前記重畳された点のグリッドの複数の点が、前記建物構造に対して外側の点を含むか内側の点を含むかを判定する
ことによって、前記重畳された点のグリッドを用いて、前記命令を実行する、請求項19に記載の機器。
【請求項２１】
前記重畳された点のグリッドの複数の点が外側の点を含むか内側の点を含むかを判定するために、前記1つまたは複数のプロセッサがさらに、
前記複数の点の選択された点から複数の線を投射し、
前記建物構造の建物の要素に衝突する前記複数の投射された線の数を検出し、
建物の要素に衝突する前記複数の投射された線の前記数に少なくとも一部基づいて、前記建物構造の内側の点または外側の点を含むものとして、前記選択された点を識別する
ことによって、前記命令を実行する、請求項20に記載の機器。
【請求項２２】
前記選択された点を識別するために、前記1つまたは複数のプロセッサがさらに、
建物の要素に衝突する前記複数の投射された線の前記数が、少なくとも1つの所定の閾値を満たすかどうかを判定し、
建物の要素に衝突する前記複数の投射された線の前記数が、前記所定の閾値を満たすと判定される場合に、内側の点を含むものとして前記選択された点を識別する
ことによって、前記命令を実行する、請求項21に記載の機器。
【請求項２３】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
前記重畳された点のグリッドの隣接点の少なくとも一部を障害物のない接続で相互接続し、複数の接続されていないグラフを形成し、
前記複数の接続されていないグラフに少なくとも一部基づいて、複数の独立の領域を決定する、請求項20の記載の機器。
【請求項２４】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
前記外側の点のうちの1つまたは複数に少なくとも一部基づいて、前記建物構造の外側にある前記複数の独立の領域の少なくとも1つの独立の領域を確定する、請求項23に記載の機器。
【請求項２５】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
前記建物構造の複数の独立の領域に対応する複数の広がりに少なくとも一部基づいて、前記建物構造の1つまたは複数の廊下を発見する、請求項19に記載の機器。
【請求項２６】
1つまたは複数の廊下を発見するために、前記1つまたは複数のプロセッサがさらに、
前記建物構造の前記複数の独立の領域の複数の広がりを計算し、
前記複数の計算された広がりおよび少なくとも1つの所定の閾値に基づいて、前記複数の独立の領域の少なくとも1つの独立の領域を、少なくとも1つの廊下を含むものとして識別する
ことによって、前記命令を実行する、請求項25に記載の機器。
【請求項２７】
少なくとも1つの独立の領域を識別するために、前記1つまたは複数のプロセッサがさらに、
前記複数の計算された広がりの特定の広がりと、前記複数の計算された広がりにより決まる前記少なくとも1つの所定の閾値とを比較し、
前記特定の広がりが前記少なくとも1つの所定の閾値を満たすかどうか判定し、
前記特定の広がりが前記少なくとも1つの所定の閾値を満たすと判定された場合に、前記特定の広がりに対応する特定の独立の領域を、前記建物構造の少なくとも1つの廊下を含むものとして識別する
ことによって、前記命令を実行する、請求項26に記載の機器。
【請求項２８】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
前記重畳された点のグリッドに対して定義可能な複数の独立の領域に、建物の注記情報を重畳し、
前記複数の独立の領域のうちのどの1つまたは複数の独立の領域が使用可能であるか、および、前記複数の独立の領域に使用不可能な独立の領域があるかどうかを、前記重畳された建物の注記情報に少なくとも一部基づいて判定する、請求項19に記載の機器。
【請求項２９】
前記建物情報を分析するために、前記1つまたは複数のプロセッサがさらに、
前記複数の投射された線と、前記建物構造の少なくとも1つの廊下とに少なくとも一部基づいて、複数の独立の領域の1つもしくは複数の入口および/または出口の点を決定する
ことによって、前記重畳された点のグリッドを用いて、前記命令を実行する、請求項19に記載の機器。
【請求項３０】
1つもしくは複数の入口および/または出口の点を決定するために、前記1つまたは複数のプロセッサがさらに、
前記複数の独立の領域の特定の独立の領域に関連するPoint of Interest(POI)に対応する、前記重畳された点のグリッドの点から複数の線を投射し、
前記建物構造の前記少なくとも1つの廊下に到達するまでの、前記複数の投射された線の少なくとも1つの建物の要素との1つまたは複数の衝突を検出し、
前記少なくとも1つの建物の要素との前記1つまたは複数の衝突に少なくとも一部基づいて、前記特定の独立の領域の前記1つもしくは複数の入口および/または出口の点を特定する
ことによって、前記命令を実行する、請求項29に記載の機器。
【請求項３１】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
関連する独立の領域に対して決定される前記1つもしくは複数の入口および/または出口の点に少なくとも一部基づいて、前記建物構造のPoint of Interestへ道案内するための1つまたは複数の経路を計算する、請求項29に記載の機器。
【請求項３２】
前記建物情報を分析するために、前記1つまたは複数のプロセッサがさらに、
特定の独立の領域が境界壁の反対側にあるかどうかを判定することに少なくとも一部基づいて、複数の独立の領域の1つもしくは複数の入口および/または出口の点を決定する
ことによって、前記重畳された点のグリッドを用いて、前記命令を実行し、前記境界壁が、前記複数の独立の領域の所与の使用可能な独立の領域と、廊下を含む前記特定の独立の領域との間に存在する、請求項19に記載の機器。
【請求項３３】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
前記建物構造に関連し前記少なくとも1つの経路案内グラフから少なくとも部分的に導出される道案内情報の、モバイル機器への送信を開始する、請求項19に記載の機器。
【請求項３４】
前記建物情報を分析するために、前記1つまたは複数のプロセッサがさらに、
前記複数の投射された線の投射が、前記建物構造の1つまたは複数の建物の要素に衝突するかどうかを検出する
ことによって、前記重畳された点のグリッドを用いて、前記命令を実行する、請求項19に記載の機器。
【請求項３５】
前記建物情報を分析するために、前記1つまたは複数のプロセッサがさらに、
前記重畳された点のグリッドの複数の点に対し、前記検出するステップに少なくとも一部基づいて、前記複数の点が前記建物構造に対して外側の点を含むか内側の点を含むかを判定し、
前記建物構造の複数の独立の領域に対して、前記検出するステップに少なくとも一部基づいて、前記複数の独立の領域の少なくとも1つの入口および/または出口の点を決定する
ことによって、前記重畳された点のグリッドを用いて、前記命令を実行する、請求項34に記載の機器。
【請求項３６】
建物構造の少なくとも一部を表現する建物情報を得、
前記建物情報に点のグリッドを重畳し、
前記重畳された点のグリッドの複数の点から複数の線を投射することによって、前記重畳された点のグリッドを用いて前記建物情報を分析し、
前記分析に応じて、かつ、前記重畳された点のグリッドと前記建物情報とに少なくとも一部基づいて、少なくとも1つの経路案内グラフを作成する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、少なくとも1つの記憶媒体を含む、物品。
【請求項３７】
前記建物情報を分析するために、前記少なくとも1つの記憶媒体がさらに、
前記重畳された点のグリッドの複数の点が、前記建物構造に対して外側の点を含むか内側の点を含むかを判定する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項36に記載の物品。
【請求項３８】
前記重畳された点のグリッドの複数の点が外側の点を含むか内側の点を含むかを判定するために、前記少なくとも1つの記憶媒体がさらに、
前記複数の点の選択された点から複数の線を投射し、
前記建物構造の建物の要素に衝突する前記複数の投射された線の数を検出し、
建物の要素に衝突する前記複数の投射された線の前記数に少なくとも一部基づいて、前記建物構造の内側の点または外側の点を含むものとして、前記選択された点を識別する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項37に記載の物品。
【請求項３９】
前記選択された点を識別するために、前記少なくとも1つの記憶媒体がさらに、
建物の要素に衝突する前記複数の投射された線の前記数が、少なくとも1つの所定の閾値を満たすかどうかを判定し、
建物の要素に衝突する前記複数の投射された線の前記数が、前記所定の閾値を満たすと判定される場合に、内側の点を含むものとして前記選択された点を識別する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項38に記載の物品。
【請求項４０】
前記少なくとも1つの記憶媒体がさらに、
前記重畳された点のグリッドの隣接点の少なくとも一部を障害物のない接続で相互接続し、複数の接続されていないグラフを形成し、
前記複数の接続されていないグラフに少なくとも一部基づいて、複数の独立の領域を決定する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項37に記載の物品。
【請求項４１】
前記少なくとも1つの記憶媒体がさらに、
前記外側の点のうちの1つまたは複数に少なくとも一部基づいて、前記建物構造の外側にある前記複数の独立の領域の少なくとも1つの独立の領域を確定する
ように1つまたは複数のプロセッサにより実行可能な命令を保存した、請求項40に記載の物品。
【請求項４２】
前記少なくとも1つの記憶媒体がさらに、
前記建物構造の複数の独立の領域に対応する複数の広がりに少なくとも一部基づいて、前記建物構造の1つまたは複数の廊下を発見する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項36に記載の物品。
【請求項４３】
1つまたは複数の廊下を発見するために、前記少なくとも1つの記憶媒体がさらに、
前記建物構造の前記複数の独立の領域の複数の広がりを計算し、
前記複数の計算された広がりおよび少なくとも1つの所定の閾値に基づいて、前記複数の独立の領域の少なくとも1つの独立の領域を、少なくとも1つの廊下を含むものとして識別する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項42に記載の物品。
【請求項４４】
少なくとも1つの独立の領域を識別するために、前記少なくとも1つの記憶媒体がさらに、
前記複数の計算された広がりの特定の広がりと、前記複数の計算された広がりにより決まる前記少なくとも1つの所定の閾値とを比較し、
前記特定の広がりが前記少なくとも1つの所定の閾値を満たすかどうか判定し、
前記特定の広がりが前記少なくとも1つの所定の閾値を満たすと判定された場合に、前記特定の広がりに対応する特定の独立の領域を、前記建物構造の少なくとも1つの廊下を含むものとして識別する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項43に記載の物品。
【請求項４５】
前記少なくとも1つの記憶媒体がさらに、
前記重畳された点のグリッドに対して定義可能な複数の独立の領域に、建物の注記情報を重畳し、
前記複数の独立の領域のうちのどの1つまたは複数の独立の領域が使用可能であるか、および、前記複数の独立の領域に使用不可能な独立の領域があるかどうかを、前記重畳された建物の注記情報に少なくとも一部基づいて判定する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項36に記載の物品。
【請求項４６】
前記建物情報を分析するために、前記少なくとも1つの記憶媒体がさらに、
前記複数の投射された線と、前記建物構造の少なくとも1つの廊下とに少なくとも一部基づいて、複数の独立の領域の1つもしくは複数の入口および/または出口の点を決定する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項36に記載の物品。
【請求項４７】
1つもしくは複数の入口および/または出口の点を決定するために、前記少なくとも1つの記憶媒体がさらに、
前記複数の独立の領域の特定の独立の領域に関連するPoint of Interestに対応する、前記重畳された点のグリッドの点から複数の線を投射し、
前記建物構造の前記少なくとも1つの廊下に到達するまでの、前記複数の投射された線の少なくとも1つの建物の要素との1つまたは複数の衝突を検出し、
前記少なくとも1つの建物の要素との前記1つまたは複数の衝突に少なくとも一部基づいて、前記特定の独立の領域の前記1つもしくは複数の入口および/または出口の点を特定する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項46に記載の物品。
【請求項４８】
前記少なくとも1つの記憶媒体がさらに、
関連する独立の領域に対して決定される前記1つもしくは複数の入口および/または出口の点に少なくとも一部基づいて、前記建物構造のPoint of Interestへ道案内するための1つまたは複数の経路を計算する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項46に記載の物品。
【請求項４９】
前記建物情報を分析するために、前記少なくとも1つの記憶媒体がさらに、
特定の独立の領域が境界壁の反対側にあるかどうかを判定することに少なくとも一部基づいて、複数の独立の領域の1つもしくは複数の入口および/または出口の点を決定する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項36に記載の物品であって、前記境界壁が、前記複数の独立の領域の所与の使用可能な独立の領域と、廊下を含む前記特定の独立の領域との間に存在する、物品。
【請求項５０】
前記少なくとも1つの記憶媒体がさらに、
前記建物構造に関連し前記少なくとも1つの経路案内グラフから少なくとも部分的に導出される道案内情報の、モバイル機器への送信を開始する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項36に記載の物品。
【請求項５１】
前記建物情報を分析するために、前記少なくとも1つの記憶媒体がさらに、
前記複数の投射された線の投射が、前記建物構造の1つまたは複数の建物の要素に衝突するかどうかを検出する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項36に記載の物品。
【請求項５２】
前記建物情報を分析するために、前記少なくとも1つの記憶媒体がさらに、
前記重畳された点のグリッドの複数の点に対し、前記検出するステップに少なくとも一部基づいて、前記複数の点が前記建物構造に対して外側の点を含むか内側の点を含むかを判定し、
前記建物構造の複数の独立の領域に対して、前記検出するステップに少なくとも一部基づいて、前記複数の独立の領域の少なくとも1つの入口および/または出口の点を決定する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項51に記載の物品。
【請求項５３】
建物構造の少なくとも一部を表現する建物情報を得るための手段と、
前記建物情報に点のグリッドを重畳するための手段と、
前記重畳された点のグリッドの複数の点から複数の線を投射することによって、前記重畳された点のグリッドを用いて前記建物情報を分析するための手段と、
前記分析に応じて、かつ、前記重畳された点のグリッドと前記建物情報とに少なくとも一部基づいて、少なくとも1つの経路案内グラフを作成するための手段と
を含む、装置。
【請求項５４】
前記分析するための手段が、
前記重畳された点のグリッドの複数の点が、前記建物構造に対して外側の点を含むか内側の点を含むかを、判定するための手段
を含む、請求項53に記載の装置。
【請求項５５】
前記判定するための手段が、
前記複数の点の選択された点から複数の線を投射するための手段と、
前記建物構造の建物の要素に衝突する前記複数の投射された線の数を検出するための手段と、
建物の要素に衝突する前記複数の投射された線の前記数に少なくとも一部基づいて、前記建物構造の内側の点または外側の点を含むものとして、前記選択された点を識別するための手段と
を含む、請求項54に記載の装置。
【請求項５６】
前記識別するための手段が、
建物の要素に衝突する前記複数の投射された線の前記数が、少なくとも1つの所定の閾値を満たすかどうかを判定するための手段と、
建物の要素に衝突する前記複数の投射された線の前記数が、前記所定の閾値を満たすと判定される場合に、内側の点を含むものとして前記選択された点を識別するための手段と
を含む、請求項55に記載の装置。
【請求項５７】
前記重畳された点のグリッドの隣接点の少なくとも一部を障害物のない接続で相互接続し、複数の接続されていないグラフを形成するための手段と、
前記複数の接続されていないグラフに少なくとも一部基づいて、複数の独立の領域を決定するための手段と
をさらに含む、請求項54に記載の装置。
【請求項５８】
前記外側の点のうちの1つまたは複数に少なくとも一部基づいて、前記建物構造の外側にある前記複数の独立の領域の少なくとも1つの独立の領域を確定するための手段
をさらに含む、請求項57に記載の装置。
【請求項５９】
前記建物構造の複数の独立の領域に対応する複数の広がりに少なくとも一部基づいて、前記建物構造の1つまたは複数の廊下を発見するための手段
をさらに含む、請求項53に記載の装置。
【請求項６０】
前記発見するための手段が、
前記建物構造の前記複数の独立の領域の複数の広がりを計算するための手段と、
前記複数の計算された広がりおよび少なくとも1つの所定の閾値に基づいて、前記複数の独立の領域の少なくとも1つの独立の領域を、少なくとも1つの廊下を含むものとして識別するための手段と
を含む、請求項59に記載の装置。
【請求項６１】
前記識別するための手段が、
前記複数の計算された広がりの特定の広がりと、前記複数の計算された広がりにより決まる前記少なくとも1つの所定の閾値とを比較するための手段と、
前記特定の広がりが前記少なくとも1つの所定の閾値を満たすかどうか判定するための手段と、
前記特定の広がりが前記少なくとも1つの所定の閾値を満たすと判定された場合に、前記特定の広がりに対応する特定の独立の領域を、前記建物構造の少なくとも1つの廊下を含むものとして識別するための手段と
を含む、請求項60に記載の装置。
【請求項６２】
前記重畳された点のグリッドに対して定義可能な複数の独立の領域に、建物の注記情報を重畳するための手段と、
前記複数の独立の領域のうちのどの1つまたは複数の独立の領域が使用可能であるか、および、前記複数の独立の領域に使用不可能な独立の領域があるかどうかを、前記重畳された建物の注記情報に少なくとも一部基づいて、判定するための手段と
をさらに含む、請求項53に記載の装置。
【請求項６３】
前記分析するための手段が、
前記複数の投射された線と、前記建物構造の少なくとも1つの廊下とに少なくとも一部基づいて、複数の独立の領域の1つもしくは複数の入口および/または出口の点を決定するための手段
を含む、請求項53に記載の装置。
【請求項６４】
前記決定するための手段が、
前記複数の独立の領域の特定の独立の領域に関連するPoint of Interestに対応する、前記重畳された点のグリッドの点から複数の線を投射するための手段と、
前記建物構造の前記少なくとも1つの廊下に到達するまでの、前記複数の投射された線の少なくとも1つの建物の要素との1つまたは複数の衝突を検出するための手段と、
前記少なくとも1つの建物の要素との前記1つまたは複数の衝突に少なくとも一部基づいて、前記特定の独立の領域の前記1つもしくは複数の入口および/または出口の点を特定するための手段と
を含む、請求項63に記載の装置。
【請求項６５】
関連する独立の領域に対して決定される前記1つもしくは複数の入口および/または出口の点に少なくとも一部基づいて、前記建物構造のPoint of Interestへ道案内するための1つまたは複数の経路を計算するための手段
をさらに含む、請求項63に記載の装置。
【請求項６６】
前記分析するための手段が、
特定の独立の領域が境界壁の反対側にあるかどうかを判定することに少なくとも一部基づいて、複数の独立の領域の1つもしくは複数の入口および/または出口の点を決定するための手段であって、前記境界壁が、前記複数の独立の領域の所与の使用可能な独立の領域と、廊下を含む前記特定の独立の領域との間に存在する、手段
を含む、請求項53に記載の装置。
【請求項６７】
前記建物構造に関連し前記少なくとも1つの経路案内グラフから少なくとも部分的に導出される道案内情報の、モバイル機器への送信を開始するための手段
をさらに含む、請求項53に記載の装置。
【請求項６８】
前記分析するための手段が、
前記複数の投射された線の投射が、前記建物構造の1つまたは複数の建物の要素に衝突するかどうかを検出するための手段
を含む、請求項53に記載の装置。
【請求項６９】
前記分析するための手段が、
前記検出するための手段に少なくとも一部基づいて、前記複数の点が前記建物構造に対して外側の点を含むか内側の点を含むかを判定するための手段であって、前記重畳された点のグリッドの複数の点について動作する、手段と、
前記検出するための手段に少なくとも一部基づいて、前記複数の独立の領域の少なくとも1つの入口および/または出口の点を決定するための手段であって、前記建物構造の複数の独立の領域に対して動作する、手段と
をさらに含む、請求項68に記載の装置。
【請求項１】
建物構造の少なくとも一部を表現する建物情報を表す電気信号を得るステップと、
前記建物情報に点のグリッドを重畳するステップと、
前記重畳された点のグリッドの複数の点から複数の線を投射することによって、前記重畳された点のグリッドを用いて前記建物情報を分析するステップと、
前記分析に応じて、かつ、前記重畳された点のグリッドと前記建物情報とに少なくとも一部基づいて、少なくとも1つの経路案内グラフを表す電気信号を生成するステップと
を含む、方法。
【請求項２】
前記分析するステップが、
前記重畳された点のグリッドの複数の点が、前記建物構造に対して外側の点を含むか内側の点を含むかを、判定するステップ
を含む、請求項1に記載の方法。
【請求項３】
前記判定するステップが、
前記複数の点の選択された点から複数の線を投射するステップと、
前記建物構造の建物の要素に衝突する前記複数の投射された線の数を検出するステップと、
建物の要素に衝突する前記複数の投射された線の前記数に少なくとも一部基づいて、前記建物構造の内側の点または外側の点を含むものとして、前記選択された点を識別するステップと
を含む、請求項2に記載の方法。
【請求項４】
前記識別するステップが、
建物の要素に衝突する前記複数の投射された線の前記数が、少なくとも1つの所定の閾値を満たすかどうかを判定するステップと、
建物の要素に衝突する前記複数の投射された線の前記数が、前記所定の閾値を満たすと判定される場合に、内側の点を含むものとして前記選択された点を識別するステップと
を含む、請求項3に記載の方法。
【請求項５】
前記重畳された点のグリッドの隣接点の少なくとも一部を障害物のない接続で相互接続し、複数の接続されていないグラフを形成するステップと、
前記複数の接続されていないグラフに少なくとも一部基づいて、複数の独立の領域を決定するステップと
をさらに含む、請求項2に記載の方法。
【請求項６】
前記外側の点のうちの1つまたは複数に少なくとも一部基づいて、前記建物構造の外側にある前記複数の独立の領域の少なくとも1つの独立の領域を確定するステップ
をさらに含む、請求項5に記載の方法。
【請求項７】
前記建物構造の複数の独立の領域に対応する複数の広がりに少なくとも一部基づいて、前記建物構造の1つまたは複数の廊下を発見するステップ
をさらに含む、請求項1に記載の方法。
【請求項８】
前記発見するステップが、
前記建物構造の前記複数の独立の領域の複数の広がりを計算するステップと、
前記複数の計算された広がりおよび少なくとも1つの所定の閾値に基づいて、前記複数の独立の領域の少なくとも1つの独立の領域を、少なくとも1つの廊下を含むものとして識別するステップと
を含む、請求項7に記載の方法。
【請求項９】
前記識別するステップが、
前記複数の計算された広がりの特定の広がりと、前記複数の計算された広がりにより決まる前記少なくとも1つの所定の閾値とを比較するステップと、
前記特定の広がりが前記少なくとも1つの所定の閾値を満たすかどうか判定するステップと、
前記特定の広がりが前記少なくとも1つの所定の閾値を満たすと判定された場合に、前記特定の広がりに対応する特定の独立の領域を、前記建物構造の少なくとも1つの廊下を含むものとして識別するステップと
を含む、請求項8に記載の方法。
【請求項１０】
前記重畳された点のグリッドに対して定義可能な複数の独立の領域に、建物の注記情報を重畳するステップと、
前記複数の独立の領域のうちのどの1つまたは複数の独立の領域が使用可能であるか、および、前記複数の独立の領域に使用不可能な独立の領域があるかどうかを、前記重畳された建物の注記情報に少なくとも一部基づいて、判定するステップと
をさらに含む、請求項1に記載の方法。
【請求項１１】
前記分析するステップが、
前記複数の投射された線と、前記建物構造の少なくとも1つの廊下とに少なくとも一部基づいて、複数の独立の領域の1つもしくは複数の入口および/または出口の点を決定するステップ
を含む、請求項1に記載の方法。
【請求項１２】
前記決定するステップが、
前記複数の独立の領域の特定の独立の領域に関連するPoint of Interestに対応する、前記重畳された点のグリッドの点から複数の線を投射するステップと、
前記建物構造の前記少なくとも1つの廊下に到達するまでの、前記複数の投射された線の少なくとも1つの建物の要素との1つまたは複数の衝突を検出するステップと、
前記少なくとも1つの建物の要素との前記1つまたは複数の衝突に少なくとも一部基づいて、前記特定の独立の領域の前記1つもしくは複数の入口および/または出口の点を特定するステップと
を含む、請求項11に記載の方法。
【請求項１３】
関連する独立の領域に対して決定される前記1つもしくは複数の入口および/または出口の点に少なくとも一部基づいて、前記建物構造のPoint of Interestへ道案内するための1つまたは複数の経路を計算するステップ
をさらに含む、請求項11に記載の方法。
【請求項１４】
前記分析するステップが、
特定の独立の領域が境界壁の反対側にあるかどうかを判定することに少なくとも一部基づいて、複数の独立の領域の1つもしくは複数の入口および/または出口の点を決定するステップであって、前記境界壁が、前記複数の独立の領域の所与の使用可能な独立の領域と、廊下を含む前記特定の独立の領域との間に存在する、ステップ
を含む、請求項1に記載の方法。
【請求項１５】
前記建物構造に関連し前記少なくとも1つの経路案内グラフから少なくとも部分的に導出される道案内情報の、モバイル機器への送信を開始するステップ
をさらに含む、請求項1に記載の方法。
【請求項１６】
前記分析するステップが、
前記複数の投射された線の投射が、前記建物構造の1つまたは複数の建物の要素に衝突するかどうかを検出するステップ
を含む、請求項1に記載の方法。
【請求項１７】
前記分析するステップが、
前記重畳された点のグリッドの複数の点に対し、前記検出するステップに少なくとも一部基づいて、前記複数の点が前記建物構造に対して外側の点を含むか内側の点を含むかを判定するステップと、
前記建物構造の複数の独立の領域に対して、前記検出するステップに少なくとも一部基づいて、前記複数の独立の領域の少なくとも1つの入口および/または出口の点を決定するステップと
をさらに含む、請求項16に記載の方法。
【請求項１８】
専用のコンピューティング機器に前記方法を実施するように指示するための命令を、前記専用のコンピューティング機器によって実行するステップ
をさらに含む、請求項1に記載の方法。
【請求項１９】
命令を保存するための少なくとも1つのメモリと、
前記命令を実行して、
建物構造の少なくとも一部を表現する建物情報を得、
前記建物情報に点のグリッドを重畳し、
前記重畳された点のグリッドの複数の点から複数の線を投射することによって、前記重畳された点のグリッドを用いて前記建物情報を分析し、
前記分析に応じて、かつ、前記重畳された点のグリッドと前記建物情報とに少なくとも一部基づいて、少なくとも1つの経路案内グラフを作成する
ための、1つまたは複数のプロセッサと
を含む、専用のコンピューティング機器。
【請求項２０】
前記建物情報を分析するために、前記1つまたは複数のプロセッサがさらに、
前記重畳された点のグリッドの複数の点が、前記建物構造に対して外側の点を含むか内側の点を含むかを判定する
ことによって、前記重畳された点のグリッドを用いて、前記命令を実行する、請求項19に記載の機器。
【請求項２１】
前記重畳された点のグリッドの複数の点が外側の点を含むか内側の点を含むかを判定するために、前記1つまたは複数のプロセッサがさらに、
前記複数の点の選択された点から複数の線を投射し、
前記建物構造の建物の要素に衝突する前記複数の投射された線の数を検出し、
建物の要素に衝突する前記複数の投射された線の前記数に少なくとも一部基づいて、前記建物構造の内側の点または外側の点を含むものとして、前記選択された点を識別する
ことによって、前記命令を実行する、請求項20に記載の機器。
【請求項２２】
前記選択された点を識別するために、前記1つまたは複数のプロセッサがさらに、
建物の要素に衝突する前記複数の投射された線の前記数が、少なくとも1つの所定の閾値を満たすかどうかを判定し、
建物の要素に衝突する前記複数の投射された線の前記数が、前記所定の閾値を満たすと判定される場合に、内側の点を含むものとして前記選択された点を識別する
ことによって、前記命令を実行する、請求項21に記載の機器。
【請求項２３】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
前記重畳された点のグリッドの隣接点の少なくとも一部を障害物のない接続で相互接続し、複数の接続されていないグラフを形成し、
前記複数の接続されていないグラフに少なくとも一部基づいて、複数の独立の領域を決定する、請求項20の記載の機器。
【請求項２４】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
前記外側の点のうちの1つまたは複数に少なくとも一部基づいて、前記建物構造の外側にある前記複数の独立の領域の少なくとも1つの独立の領域を確定する、請求項23に記載の機器。
【請求項２５】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
前記建物構造の複数の独立の領域に対応する複数の広がりに少なくとも一部基づいて、前記建物構造の1つまたは複数の廊下を発見する、請求項19に記載の機器。
【請求項２６】
1つまたは複数の廊下を発見するために、前記1つまたは複数のプロセッサがさらに、
前記建物構造の前記複数の独立の領域の複数の広がりを計算し、
前記複数の計算された広がりおよび少なくとも1つの所定の閾値に基づいて、前記複数の独立の領域の少なくとも1つの独立の領域を、少なくとも1つの廊下を含むものとして識別する
ことによって、前記命令を実行する、請求項25に記載の機器。
【請求項２７】
少なくとも1つの独立の領域を識別するために、前記1つまたは複数のプロセッサがさらに、
前記複数の計算された広がりの特定の広がりと、前記複数の計算された広がりにより決まる前記少なくとも1つの所定の閾値とを比較し、
前記特定の広がりが前記少なくとも1つの所定の閾値を満たすかどうか判定し、
前記特定の広がりが前記少なくとも1つの所定の閾値を満たすと判定された場合に、前記特定の広がりに対応する特定の独立の領域を、前記建物構造の少なくとも1つの廊下を含むものとして識別する
ことによって、前記命令を実行する、請求項26に記載の機器。
【請求項２８】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
前記重畳された点のグリッドに対して定義可能な複数の独立の領域に、建物の注記情報を重畳し、
前記複数の独立の領域のうちのどの1つまたは複数の独立の領域が使用可能であるか、および、前記複数の独立の領域に使用不可能な独立の領域があるかどうかを、前記重畳された建物の注記情報に少なくとも一部基づいて判定する、請求項19に記載の機器。
【請求項２９】
前記建物情報を分析するために、前記1つまたは複数のプロセッサがさらに、
前記複数の投射された線と、前記建物構造の少なくとも1つの廊下とに少なくとも一部基づいて、複数の独立の領域の1つもしくは複数の入口および/または出口の点を決定する
ことによって、前記重畳された点のグリッドを用いて、前記命令を実行する、請求項19に記載の機器。
【請求項３０】
1つもしくは複数の入口および/または出口の点を決定するために、前記1つまたは複数のプロセッサがさらに、
前記複数の独立の領域の特定の独立の領域に関連するPoint of Interest(POI)に対応する、前記重畳された点のグリッドの点から複数の線を投射し、
前記建物構造の前記少なくとも1つの廊下に到達するまでの、前記複数の投射された線の少なくとも1つの建物の要素との1つまたは複数の衝突を検出し、
前記少なくとも1つの建物の要素との前記1つまたは複数の衝突に少なくとも一部基づいて、前記特定の独立の領域の前記1つもしくは複数の入口および/または出口の点を特定する
ことによって、前記命令を実行する、請求項29に記載の機器。
【請求項３１】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
関連する独立の領域に対して決定される前記1つもしくは複数の入口および/または出口の点に少なくとも一部基づいて、前記建物構造のPoint of Interestへ道案内するための1つまたは複数の経路を計算する、請求項29に記載の機器。
【請求項３２】
前記建物情報を分析するために、前記1つまたは複数のプロセッサがさらに、
特定の独立の領域が境界壁の反対側にあるかどうかを判定することに少なくとも一部基づいて、複数の独立の領域の1つもしくは複数の入口および/または出口の点を決定する
ことによって、前記重畳された点のグリッドを用いて、前記命令を実行し、前記境界壁が、前記複数の独立の領域の所与の使用可能な独立の領域と、廊下を含む前記特定の独立の領域との間に存在する、請求項19に記載の機器。
【請求項３３】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
前記建物構造に関連し前記少なくとも1つの経路案内グラフから少なくとも部分的に導出される道案内情報の、モバイル機器への送信を開始する、請求項19に記載の機器。
【請求項３４】
前記建物情報を分析するために、前記1つまたは複数のプロセッサがさらに、
前記複数の投射された線の投射が、前記建物構造の1つまたは複数の建物の要素に衝突するかどうかを検出する
ことによって、前記重畳された点のグリッドを用いて、前記命令を実行する、請求項19に記載の機器。
【請求項３５】
前記建物情報を分析するために、前記1つまたは複数のプロセッサがさらに、
前記重畳された点のグリッドの複数の点に対し、前記検出するステップに少なくとも一部基づいて、前記複数の点が前記建物構造に対して外側の点を含むか内側の点を含むかを判定し、
前記建物構造の複数の独立の領域に対して、前記検出するステップに少なくとも一部基づいて、前記複数の独立の領域の少なくとも1つの入口および/または出口の点を決定する
ことによって、前記重畳された点のグリッドを用いて、前記命令を実行する、請求項34に記載の機器。
【請求項３６】
建物構造の少なくとも一部を表現する建物情報を得、
前記建物情報に点のグリッドを重畳し、
前記重畳された点のグリッドの複数の点から複数の線を投射することによって、前記重畳された点のグリッドを用いて前記建物情報を分析し、
前記分析に応じて、かつ、前記重畳された点のグリッドと前記建物情報とに少なくとも一部基づいて、少なくとも1つの経路案内グラフを作成する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、少なくとも1つの記憶媒体を含む、物品。
【請求項３７】
前記建物情報を分析するために、前記少なくとも1つの記憶媒体がさらに、
前記重畳された点のグリッドの複数の点が、前記建物構造に対して外側の点を含むか内側の点を含むかを判定する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項36に記載の物品。
【請求項３８】
前記重畳された点のグリッドの複数の点が外側の点を含むか内側の点を含むかを判定するために、前記少なくとも1つの記憶媒体がさらに、
前記複数の点の選択された点から複数の線を投射し、
前記建物構造の建物の要素に衝突する前記複数の投射された線の数を検出し、
建物の要素に衝突する前記複数の投射された線の前記数に少なくとも一部基づいて、前記建物構造の内側の点または外側の点を含むものとして、前記選択された点を識別する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項37に記載の物品。
【請求項３９】
前記選択された点を識別するために、前記少なくとも1つの記憶媒体がさらに、
建物の要素に衝突する前記複数の投射された線の前記数が、少なくとも1つの所定の閾値を満たすかどうかを判定し、
建物の要素に衝突する前記複数の投射された線の前記数が、前記所定の閾値を満たすと判定される場合に、内側の点を含むものとして前記選択された点を識別する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項38に記載の物品。
【請求項４０】
前記少なくとも1つの記憶媒体がさらに、
前記重畳された点のグリッドの隣接点の少なくとも一部を障害物のない接続で相互接続し、複数の接続されていないグラフを形成し、
前記複数の接続されていないグラフに少なくとも一部基づいて、複数の独立の領域を決定する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項37に記載の物品。
【請求項４１】
前記少なくとも1つの記憶媒体がさらに、
前記外側の点のうちの1つまたは複数に少なくとも一部基づいて、前記建物構造の外側にある前記複数の独立の領域の少なくとも1つの独立の領域を確定する
ように1つまたは複数のプロセッサにより実行可能な命令を保存した、請求項40に記載の物品。
【請求項４２】
前記少なくとも1つの記憶媒体がさらに、
前記建物構造の複数の独立の領域に対応する複数の広がりに少なくとも一部基づいて、前記建物構造の1つまたは複数の廊下を発見する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項36に記載の物品。
【請求項４３】
1つまたは複数の廊下を発見するために、前記少なくとも1つの記憶媒体がさらに、
前記建物構造の前記複数の独立の領域の複数の広がりを計算し、
前記複数の計算された広がりおよび少なくとも1つの所定の閾値に基づいて、前記複数の独立の領域の少なくとも1つの独立の領域を、少なくとも1つの廊下を含むものとして識別する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項42に記載の物品。
【請求項４４】
少なくとも1つの独立の領域を識別するために、前記少なくとも1つの記憶媒体がさらに、
前記複数の計算された広がりの特定の広がりと、前記複数の計算された広がりにより決まる前記少なくとも1つの所定の閾値とを比較し、
前記特定の広がりが前記少なくとも1つの所定の閾値を満たすかどうか判定し、
前記特定の広がりが前記少なくとも1つの所定の閾値を満たすと判定された場合に、前記特定の広がりに対応する特定の独立の領域を、前記建物構造の少なくとも1つの廊下を含むものとして識別する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項43に記載の物品。
【請求項４５】
前記少なくとも1つの記憶媒体がさらに、
前記重畳された点のグリッドに対して定義可能な複数の独立の領域に、建物の注記情報を重畳し、
前記複数の独立の領域のうちのどの1つまたは複数の独立の領域が使用可能であるか、および、前記複数の独立の領域に使用不可能な独立の領域があるかどうかを、前記重畳された建物の注記情報に少なくとも一部基づいて判定する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項36に記載の物品。
【請求項４６】
前記建物情報を分析するために、前記少なくとも1つの記憶媒体がさらに、
前記複数の投射された線と、前記建物構造の少なくとも1つの廊下とに少なくとも一部基づいて、複数の独立の領域の1つもしくは複数の入口および/または出口の点を決定する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項36に記載の物品。
【請求項４７】
1つもしくは複数の入口および/または出口の点を決定するために、前記少なくとも1つの記憶媒体がさらに、
前記複数の独立の領域の特定の独立の領域に関連するPoint of Interestに対応する、前記重畳された点のグリッドの点から複数の線を投射し、
前記建物構造の前記少なくとも1つの廊下に到達するまでの、前記複数の投射された線の少なくとも1つの建物の要素との1つまたは複数の衝突を検出し、
前記少なくとも1つの建物の要素との前記1つまたは複数の衝突に少なくとも一部基づいて、前記特定の独立の領域の前記1つもしくは複数の入口および/または出口の点を特定する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項46に記載の物品。
【請求項４８】
前記少なくとも1つの記憶媒体がさらに、
関連する独立の領域に対して決定される前記1つもしくは複数の入口および/または出口の点に少なくとも一部基づいて、前記建物構造のPoint of Interestへ道案内するための1つまたは複数の経路を計算する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項46に記載の物品。
【請求項４９】
前記建物情報を分析するために、前記少なくとも1つの記憶媒体がさらに、
特定の独立の領域が境界壁の反対側にあるかどうかを判定することに少なくとも一部基づいて、複数の独立の領域の1つもしくは複数の入口および/または出口の点を決定する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項36に記載の物品であって、前記境界壁が、前記複数の独立の領域の所与の使用可能な独立の領域と、廊下を含む前記特定の独立の領域との間に存在する、物品。
【請求項５０】
前記少なくとも1つの記憶媒体がさらに、
前記建物構造に関連し前記少なくとも1つの経路案内グラフから少なくとも部分的に導出される道案内情報の、モバイル機器への送信を開始する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項36に記載の物品。
【請求項５１】
前記建物情報を分析するために、前記少なくとも1つの記憶媒体がさらに、
前記複数の投射された線の投射が、前記建物構造の1つまたは複数の建物の要素に衝突するかどうかを検出する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項36に記載の物品。
【請求項５２】
前記建物情報を分析するために、前記少なくとも1つの記憶媒体がさらに、
前記重畳された点のグリッドの複数の点に対し、前記検出するステップに少なくとも一部基づいて、前記複数の点が前記建物構造に対して外側の点を含むか内側の点を含むかを判定し、
前記建物構造の複数の独立の領域に対して、前記検出するステップに少なくとも一部基づいて、前記複数の独立の領域の少なくとも1つの入口および/または出口の点を決定する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項51に記載の物品。
【請求項５３】
建物構造の少なくとも一部を表現する建物情報を得るための手段と、
前記建物情報に点のグリッドを重畳するための手段と、
前記重畳された点のグリッドの複数の点から複数の線を投射することによって、前記重畳された点のグリッドを用いて前記建物情報を分析するための手段と、
前記分析に応じて、かつ、前記重畳された点のグリッドと前記建物情報とに少なくとも一部基づいて、少なくとも1つの経路案内グラフを作成するための手段と
を含む、装置。
【請求項５４】
前記分析するための手段が、
前記重畳された点のグリッドの複数の点が、前記建物構造に対して外側の点を含むか内側の点を含むかを、判定するための手段
を含む、請求項53に記載の装置。
【請求項５５】
前記判定するための手段が、
前記複数の点の選択された点から複数の線を投射するための手段と、
前記建物構造の建物の要素に衝突する前記複数の投射された線の数を検出するための手段と、
建物の要素に衝突する前記複数の投射された線の前記数に少なくとも一部基づいて、前記建物構造の内側の点または外側の点を含むものとして、前記選択された点を識別するための手段と
を含む、請求項54に記載の装置。
【請求項５６】
前記識別するための手段が、
建物の要素に衝突する前記複数の投射された線の前記数が、少なくとも1つの所定の閾値を満たすかどうかを判定するための手段と、
建物の要素に衝突する前記複数の投射された線の前記数が、前記所定の閾値を満たすと判定される場合に、内側の点を含むものとして前記選択された点を識別するための手段と
を含む、請求項55に記載の装置。
【請求項５７】
前記重畳された点のグリッドの隣接点の少なくとも一部を障害物のない接続で相互接続し、複数の接続されていないグラフを形成するための手段と、
前記複数の接続されていないグラフに少なくとも一部基づいて、複数の独立の領域を決定するための手段と
をさらに含む、請求項54に記載の装置。
【請求項５８】
前記外側の点のうちの1つまたは複数に少なくとも一部基づいて、前記建物構造の外側にある前記複数の独立の領域の少なくとも1つの独立の領域を確定するための手段
をさらに含む、請求項57に記載の装置。
【請求項５９】
前記建物構造の複数の独立の領域に対応する複数の広がりに少なくとも一部基づいて、前記建物構造の1つまたは複数の廊下を発見するための手段
をさらに含む、請求項53に記載の装置。
【請求項６０】
前記発見するための手段が、
前記建物構造の前記複数の独立の領域の複数の広がりを計算するための手段と、
前記複数の計算された広がりおよび少なくとも1つの所定の閾値に基づいて、前記複数の独立の領域の少なくとも1つの独立の領域を、少なくとも1つの廊下を含むものとして識別するための手段と
を含む、請求項59に記載の装置。
【請求項６１】
前記識別するための手段が、
前記複数の計算された広がりの特定の広がりと、前記複数の計算された広がりにより決まる前記少なくとも1つの所定の閾値とを比較するための手段と、
前記特定の広がりが前記少なくとも1つの所定の閾値を満たすかどうか判定するための手段と、
前記特定の広がりが前記少なくとも1つの所定の閾値を満たすと判定された場合に、前記特定の広がりに対応する特定の独立の領域を、前記建物構造の少なくとも1つの廊下を含むものとして識別するための手段と
を含む、請求項60に記載の装置。
【請求項６２】
前記重畳された点のグリッドに対して定義可能な複数の独立の領域に、建物の注記情報を重畳するための手段と、
前記複数の独立の領域のうちのどの1つまたは複数の独立の領域が使用可能であるか、および、前記複数の独立の領域に使用不可能な独立の領域があるかどうかを、前記重畳された建物の注記情報に少なくとも一部基づいて、判定するための手段と
をさらに含む、請求項53に記載の装置。
【請求項６３】
前記分析するための手段が、
前記複数の投射された線と、前記建物構造の少なくとも1つの廊下とに少なくとも一部基づいて、複数の独立の領域の1つもしくは複数の入口および/または出口の点を決定するための手段
を含む、請求項53に記載の装置。
【請求項６４】
前記決定するための手段が、
前記複数の独立の領域の特定の独立の領域に関連するPoint of Interestに対応する、前記重畳された点のグリッドの点から複数の線を投射するための手段と、
前記建物構造の前記少なくとも1つの廊下に到達するまでの、前記複数の投射された線の少なくとも1つの建物の要素との1つまたは複数の衝突を検出するための手段と、
前記少なくとも1つの建物の要素との前記1つまたは複数の衝突に少なくとも一部基づいて、前記特定の独立の領域の前記1つもしくは複数の入口および/または出口の点を特定するための手段と
を含む、請求項63に記載の装置。
【請求項６５】
関連する独立の領域に対して決定される前記1つもしくは複数の入口および/または出口の点に少なくとも一部基づいて、前記建物構造のPoint of Interestへ道案内するための1つまたは複数の経路を計算するための手段
をさらに含む、請求項63に記載の装置。
【請求項６６】
前記分析するための手段が、
特定の独立の領域が境界壁の反対側にあるかどうかを判定することに少なくとも一部基づいて、複数の独立の領域の1つもしくは複数の入口および/または出口の点を決定するための手段であって、前記境界壁が、前記複数の独立の領域の所与の使用可能な独立の領域と、廊下を含む前記特定の独立の領域との間に存在する、手段
を含む、請求項53に記載の装置。
【請求項６７】
前記建物構造に関連し前記少なくとも1つの経路案内グラフから少なくとも部分的に導出される道案内情報の、モバイル機器への送信を開始するための手段
をさらに含む、請求項53に記載の装置。
【請求項６８】
前記分析するための手段が、
前記複数の投射された線の投射が、前記建物構造の1つまたは複数の建物の要素に衝突するかどうかを検出するための手段
を含む、請求項53に記載の装置。
【請求項６９】
前記分析するための手段が、
前記検出するための手段に少なくとも一部基づいて、前記複数の点が前記建物構造に対して外側の点を含むか内側の点を含むかを判定するための手段であって、前記重畳された点のグリッドの複数の点について動作する、手段と、
前記検出するための手段に少なくとも一部基づいて、前記複数の独立の領域の少なくとも1つの入口および/または出口の点を決定するための手段であって、前記建物構造の複数の独立の領域に対して動作する、手段と
をさらに含む、請求項68に記載の装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１８】
【図１９】
【図２０】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１８】
【図１９】
【図２０】
【図１７】
【公表番号】特表２０１３−５０６８４９（Ｐ２０１３−５０６８４９Ａ）
【公表日】平成２５年２月２８日（２０１３．２．２８）
【国際特許分類】
【出願番号】特願２０１２−５３２３７２（Ｐ２０１２−５３２３７２）
【出願日】平成２２年１０月１日（２０１０．１０．１）
【国際出願番号】ＰＣＴ／ＵＳ２０１０／０５１２１６
【国際公開番号】ＷＯ２０１１／０４１７４５
【国際公開日】平成２３年４月７日（２０１１．４．７）
【出願人】（５０７３６４８３８）クアルコム，インコーポレイテッド (446)
【Ｆターム（参考）】
【公表日】平成２５年２月２８日（２０１３．２．２８）
【国際特許分類】
【出願日】平成２２年１０月１日（２０１０．１０．１）
【国際出願番号】ＰＣＴ／ＵＳ２０１０／０５１２１６
【国際公開番号】ＷＯ２０１１／０４１７４５
【国際公開日】平成２３年４月７日（２０１１．４．７）
【出願人】（５０７３６４８３８）クアルコム，インコーポレイテッド (446)
【Ｆターム（参考）】
[ Back to top ]