(57)【要約】  本明細書に開示する対象物は、電子地図の特徴を自動的に特定するためのシステムおよび方法に関する。
2013507717.tif 000002
【特許請求の範囲】
【請求項１】
構造物の特徴を示す1つまたは複数の電子地図にアクセスするステップと、
前記1つまたは複数の電子地図から特徴を電子的に抽出するステップと、
前記特徴に少なくとも部分的に基づいて少なくとも1つの電子的に抽出された入口通路と1つまたは複数の電子的に抽出された構造要素あるいは1つまたは複数の他の入口通路との間に延びる1つまたは複数の線分に少なくとも部分的に基づいて前記1つまたは複数の電子地図上の1つまたは複数の回廊を特定するステップと、
前記1つまたは複数の回廊を特定する1つまたは複数の注釈を付けて前記1つまたは複数の電子地図を更新するステップと
を含む、方法。
【請求項２】
前記1つまたは複数の構造要素が、第1の電子的に抽出された入口通路と少なくとも1つの第2の電子的に抽出された入口通路との間に延びる少なくとも1つの構造上の仕切りを含む、請求項1に記載の方法。
【請求項３】
少なくとも部分的に前記特徴に基づいて前記少なくとも1つの電子的に抽出された入口通路を特定するステップをさらに含む、請求項1に記載の方法。
【請求項４】
前記1つまたは複数の電子地図がメモリ装置からアクセス可能である、請求項1に記載の方法。
【請求項５】
前記1つまたは複数の回廊を前記特定するステップが、前記1つまたは複数の入口通路のうちの少なくとも1つと少なくとも2つの他の入口通路との間に第1の線分を延ばすステップと、前記第1の線分のそれぞれの中間点を特定するステップと、前記第1の線分の前記それぞれの中間点を通る第2の線分を延ばすステップとを含む、請求項1に記載の方法。
【請求項６】
前記1つまたは複数の回廊を特定するステップが、少なくとも3つの入口通路から前記電子的に抽出された構造要素まで実質的に垂直な第1の線分を延ばすステップと、前記実質的に垂直な第1の線分を通る第2の線分を延ばすステップとを含む、請求項1に記載の方法。
【請求項７】
回廊の共通の側に位置する少なくとも2つの入口通路を通って延びる第1の線分を決定し、前記構造物の第1のそれぞれの端部の間で前記線分を延ばすステップと、
前記第1の線分の実質的に垂直な二等分線を決定し、前記構造物の第2のそれぞれの端部の間で前記第1の線分に実質的に垂直な方向に第2の線分を延ばすステップと、
前記少なくとも2つの入口通路と前記構造物の前記第2のそれぞれの端部との間に延びる第3の線分の組を決定するステップと、
前記入口通路が前記第3の線分のそれぞれの端部と関連する共有点に直接アクセスできることに少なくとも部分的に基づいて前記回廊を特定するステップと
をさらに含む、請求項1に記載の方法。
【請求項８】
前記1つまたは複数の更新された電子地図の少なくとも1つをモバイル装置に送信するステップをさらに含む、請求項1に記載の方法。
【請求項９】
前記1つまたは複数の更新された電子地図の少なくとも1つをモバイル装置のディスプレイに提示するステップをさらに含む、請求項8に記載の方法。
【請求項１０】
構造物の特徴を示す1つまたは複数の電子地図を受信するための受信機と、
前記1つまたは複数の電子地図から特徴を電子的に抽出し、
前記特徴に少なくとも部分的に基づいて少なくとも1つの電子的に抽出された入口通路と1つまたは複数の電子的に抽出された構造要素あるいは1つまたは複数の他の入口通路との間に延びる1つまたは複数の線分に少なくとも部分的に基づいて、前記1つまたは複数の電子地図上の1つまたは複数の回廊を特定し、
前記1つまたは複数の回廊を特定する1つまたは複数の注釈を付けて前記1つまたは複数の電子地図を更新する
ように構成された処理ユニットと
を含む、装置。
【請求項１１】
前記1つまたは複数の構造要素が、第1の電子的に抽出された入口通路と少なくとも1つの第2の電子的に抽出された入口通路との間に延びる少なくとも1つの構造上の仕切りを含む、請求項10に記載の装置。
【請求項１２】
前記処理ユニットがさらに、少なくとも部分的に前記特徴に基づいて前記少なくとも1つの電子的に抽出された入口通路を特定するように構成された、請求項10に記載の装置。
【請求項１３】
前記処理ユニットがさらに、前記1つまたは複数の入口通路のうちの少なくとも1つと少なくとも2つの他の入口通路との間に第1の線分を延ばし、前記第1の線分のそれぞれの中間点を特定し、前記第1の線分の前記それぞれの中間点を通る第2の線分を延ばすこととによって、前記1つまたは複数の回廊を特定するように構成された、請求項10に記載の装置。
【請求項１４】
前記処理ユニットがさらに、少なくとも3つの入口通路から前記電子的に抽出された構造要素まで実質的に垂直な第1の線分を延ばし、前記実質的に垂直な第1の線分を通る第2の線分を延ばすことによって、前記1つまたは複数の回廊を特定するように構成された、請求項10に記載の装置。
【請求項１５】
前記処理ユニットがさらに、
回廊の共通の側に位置する少なくとも2つの入口通路を通って延びる第1の線分を決定し、前記構造物の第1のそれぞれの端部の間に前記線分を延ばし、
前記第1の線分の実質的に垂直な二等分線を決定し、前記構造物の第2のそれぞれの端部の間で前記第1の線分に実質的に垂直な方向に第2の線分を延ばし、
前記少なくとも2つの入口通路と前記構造物の前記第2のそれぞれの端部との間に延びる第3の線分の組を決定し、
前記入口通路が前記第3の線分のそれぞれの端部と関連する共有点に直接アクセスできることに少なくとも部分的に基づいて前記回廊を特定する
ように構成された、請求項10に記載の装置。
【請求項１６】
前記1つまたは複数の更新された電子地図の少なくとも1つをモバイル装置に送信するための送信機をさらに含む、請求項10に記載の装置。
【請求項１７】
構造物の特徴を示す1つまたは複数の電子地図にアクセスするための手段と、
前記1つまたは複数の電子地図から特徴を電子的に抽出するための手段と、
前記特徴に少なくとも部分的に基づいて少なくとも1つの電子的に抽出された入口通路と1つまたは複数の電子的に抽出された構造要素もしくは1つまたは複数の他の入口通路との間に延びる1つまたは複数の線分に少なくとも部分的に基づいて、前記1つまたは複数の電子地図上の1つまたは複数の回廊を特定するための手段と、
前記1つまたは複数の回廊を特定する1つまたは複数の注釈を付けて前記1つまたは複数の電子地図を更新するための手段と
を含む、装置。
【請求項１８】
前記1つまたは複数の構造要素が、第1の電子的に抽出された入口通路と少なくとも1つの第2の電子的に抽出された入口通路との間に延びる少なくとも1つの構造上の仕切りを含む、請求項17に記載の装置。
【請求項１９】
少なくとも部分的に前記特徴に基づいて前記少なくとも1つの電子的に抽出された入口通路を特定するための手段をさらに含む、請求項17に記載の装置。
【請求項２０】
前記1つまたは複数の入口通路のうちの少なくとも1つと少なくとも2つの他の入口通路との間に第1の線分を延ばし、前記第1の線分のそれぞれの中間点を特定し、前記第1の線分の前記それぞれの中間点を通る第2の線分を延ばすことによって、前記1つまたは複数の回廊を特定するための手段をさらに含む、請求項17に記載の装置。
【請求項２１】
少なくとも3つの入口通路から前記電子的に抽出された構造要素まで実質的に垂直な第1の線分を延ばし、前記実質的に垂直な第1の線分を通る第2の線分を延ばすことによって、前記1つまたは複数の回廊を特定するための手段をさらに含む、請求項17に記載の装置。
【請求項２２】
回廊の共通の側に位置する少なくとも2つの入口通路を通って延びる第1の線分を特定し、前記構造物の第1のそれぞれの端部の間で前記の線分を延ばすための手段と、
前記第1の線分の実質的に垂直な二等分線を決定し、前記構造物の第2のそれぞれの端部の間で前記第1の線分に実質的に垂直な方向に第2の線分を延ばすための手段と、
前記少なくとも2つの入口通路と前記構造物の前記第2のそれぞれの端部との間に延びる第3の線分の組を決定するための手段と、
前記入口通路が前記第3の線分のそれぞれの端部と関連する共有点に直接アクセスできることに少なくとも部分的に基づいて、前記回廊を特定するための手段と
をさらに含む、請求項17に記載の装置。
【請求項２３】
前記1つまたは複数の更新された電子地図の少なくとも1つをモバイル装置に送信するための手段をさらに含む、請求項17に記載の装置。
【請求項２４】
構造物の特徴を示す1つまたは複数の電子地図にアクセスし、
前記1つまたは複数の電子地図から特徴を電子的に抽出し、
前記特徴に少なくとも部分的に基づいて少なくとも1つの電子的に抽出された入口通路と1つまたは複数の電子的に抽出された構造要素もしくは1つまたは複数の他の入口通路との間に延びる1つまたは複数の線分に少なくとも部分的に基づいて、前記1つまたは複数の電子地図上の1つまたは複数の回廊を特定し、
前記1つまたは複数の回廊を特定する1つまたは複数の注釈を付けて前記1つまたは複数の電子地図を更新する
ための、
特殊用途装置によって実行できる機械可読命令を含むコンピュータプログラム。
【請求項２５】
前記1つまたは複数の構造要素が、第1の電子的に抽出された入口通路と少なくとも1つの第2の電子的に抽出された入口通路との間に延びる少なくとも1つの構造上の仕切りを含む、請求項24に記載のコンピュータプログラム。
【請求項２６】
前記機械可読命令がさらに、前記特徴に少なくとも部分的に基づいて前記少なくとも1つの電子的に抽出された入口通路を特定するために前記特殊用途装置によって実行可能である、請求項24に記載のコンピュータプログラム。
【請求項２７】
前記機械可読命令がさらに、前記1つまたは複数の入口通路のうちの少なくとも1つと少なくとも2つの他の入口通路との間に第1の線分を延ばし、前記第1の線分のそれぞれの中間点を特定し、前記第1の線分の前記それぞれの中間点を通る第2の線分を延ばすこととによって、前記1つまたは複数の回廊を特定するために前記特殊用途装置によって実行可能である、請求項24に記載のコンピュータプログラム。
【請求項２８】
前記機械可読命令がさらに、少なくとも3つの入口通路から前記電子的に抽出された構造要素まで実質的に垂直な第1の線分を延ばし、前記実質的に垂直な第1の線分を通る第2の線分を延ばすことによって、前記1つまたは複数の回廊を特定するために、前記特殊用途装置によって実行可能である、請求項24に記載のコンピュータプログラム。
【請求項２９】
前記機械可読命令がさらに、
回廊の共通の側に位置する少なくとも2つの入口通路を通って延びる第1の線分を特定し、前記構造物の第1のそれぞれの端部の間で前記線分を延ばし、
前記第1の線分の実質的に垂直な二等分線を決定し、前記構造物の第2のそれぞれの端部の間で前記第1の線分に実質的に垂直な方向に第2の線分を延ばし、
前記少なくとも2つの入口通路と前記構造物の前記第2のそれぞれの端部との間に延びる第3の線分の組を決定し、
前記入口通路が前記第3の線分のそれぞれの端部と関連する共有点に直接アクセスできることに少なくとも部分的に基づいて、前記回廊を特定する
ために、前記特殊用途装置によって実行可能である、請求項24に記載のコンピュータプログラム。
【請求項３０】
前記機械可読命令がさらに、前記1つまたは複数の更新された電子地図の少なくとも1つをモバイル装置に送信することを起動するために前記特殊用途装置によって実行可能である、請求項24に記載のコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本出願は、2009年10月12日に出願され、本譲受人に譲渡され、本明細書に参照によりその全体が明確に組み込まれる、「Deriving Corridors in a Map」という名称の仮特許出願第61/250,837号に基づく優先権を主張する。
【０００２】
本明細書に開示する対象物は、電子地図の特徴を自動的に判断することに関する。
【背景技術】
【０００３】
ナビゲーションシステムは、今日の市場にますます普及しつつある。ナビゲーションシステムは、第1の位置から目的地までのルートを決定するために使用することができる。一部のナビゲーションシステムでは、Mapquest.comのようなウェブサイトで一般に使用される様々な地図アプリケーションのうちの1つなどの地図アプリケーションに、ユーザが出発位置および目的地を入力することができる。
【０００４】
ナビゲーションシステムは、例えばデパートまたはフードコードなどの目的地へユーザを案内するために、ショッピングモールなどの屋内環境で利用することができる。一定の距離の間、またはベンチもしくは回廊など目印となるものに到達するまで特定の方向に歩き、その後方向を変えるようユーザに知らせるナビゲーションの指示をユーザに提供することができる。例えば、ベンチに到達すると左に曲がって歩き続けるようユーザに指示することができる。出発位置から目的地までユーザを案内するナビゲーションの指示は、例えばいくつかのセグメントまたは分岐(branch)を含むことができる。例えば、「50フィート直進する」ためのナビゲーションの指示は、第1の分岐を含むことができ、「左に曲がって60フィート直進する」は第2の分岐を含むことができる。屋内環境では、出発位置から目的位置または目的地までの特定の通路に沿って数多くの分岐が存在する可能性がある。
【０００５】
例えば店舗の寸法、店舗への入口通路、または回廊の位置など、屋内環境の配置に関する情報は、適切なナビゲーションの指示を決定するために利用することができる。例えば、入口通路または回廊の位置がわかる場合、特定の通路に沿って目的地の店舗の入口通路までユーザを導くことができる。しかしながら、一部のシステムでは、対応する地図上で屋内環境の一定の特徴を人間オペレータが特定するまでに時間がかかる場合がある。
【発明の概要】
【課題を解決するための手段】
【０００６】
1つの特定の実装形態において、電子地図の特徴を自動的に判断するためのシステムおよび方法を提供する。電子地図から特徴を抽出することができる。少なくとも1つの入口通路と1つまたは複数の構造要素もしくは1つまたは複数の他の入口通路との間に延びる1つまたは複数の線分に少なくとも部分的に基づいて、電子地図の中で1つまたは複数の回廊を特定することができる。電子地図は、1つまたは複数の回廊を特定する1つまたは複数の注釈を付けて更新することができる。しかしながら、これは一例の実装形態にすぎず、請求される対象物はこの点において限定されないことを理解すべきである。
【０００７】
様々な図を通して同様の参照符号が同様の部分を指す次の図を参照して、非限定的および非網羅的な特徴について説明する。
【図面の簡単な説明】
【０００８】
【図１Ａ】1つまたは複数の実装形態により囲われたエリアの入口通路を示すための所定のマーキングを有する電子地図の断片の図である。
【図１Ｂ】1つまたは複数の実装形態により囲われたエリアの入口通路を示すための所定のマーキングを有する電子地図の断片の図である。
【図２】1つまたは複数の実装形態によるナビゲーションシステムの概略図である。
【図３】1つの実装形態による電子地図の図である。
【図４】1つの実装形態による電子地図の断片の図である。
【図５】1つまたは複数の実装形態による入口通路の視線内の入口通路を示す電子地図の図である。
【図６】1つまたは複数の実装形態により特定される回廊を示す電子地図の図である。
【図７】1つまたは複数の実装形態による電子地図の図である。
【図８】1つまたは複数の実装形態による電子地図の図である。
【図９】1つまたは複数の実装形態により湾曲した回廊を示す電子地図の図である。
【図１０】1つまたは複数の実装形態により電子地図上の1つまたは複数の回廊を特定するためのプロセスの流れ図である。
【図１１】1つの実装形態による地図サーバの特定の実装の概略的なブロック図である。
【発明を実施するための形態】
【０００９】
この明細書を通して「1つの例」、「1つの特徴」、「例」、または「特徴」への言及は、この特徴および/または例に関連して説明する特定の特徴、構造、または特性が、特許請求の範囲に記載する対象物の少なくとも1つの特徴および/または例に含まれることを意味する。したがって、「1つの例では」、「例」、「1つの特徴では」、または「特徴」という語句が本明細書にわたって様々な箇所で登場するが、必ずしもすべて同じ特徴および/または例を指しているとは限らない。さらには、特定の特徴、構造、または特性は、1つまたは複数の例および/または特徴に結合される場合がある。
【００１０】
一部のナビゲーションシステムは、屋内環境で出発位置から目的位置までユーザを案内する方法を決定するために電子地図を使用する。一部の電子地図は、オフィスまたは建物の設計図をスキャンして、例えばオフィス、トイレ、または関心のある他の項目の位置を示すことによって生成することができる。ユーザを案内するのに役立つ指示を決定するために、最初に電子地図上の一定の通路または回廊を確認することができる。出発位置から終点の目的地まで1つまたは複数の通路または回廊を通してユーザを案内することができる。
【００１１】
ナビゲーションシステムの一部の実装形態では、例えばユーザのモバイル装置上に、またはコンピュータのディスプレイ画面に、表示するための電子地図を送信する。一部のナビゲーションシステムは、出発位置から1つまたは複数の目的地までユーザを案内するための指示を決定することができる。ナビゲーションアプリケーションが、例えば基本電子地図を分析して、出発位置から目的位置までユーザを案内する方法を決定することができる。本明細書で使用する「基本電子地図」とは、線分を含むが、例えば壁、回廊、入口通路、または他のタイプの構造上の仕切りなど一定の構造物の位置を直接特定することはできない電子地図を指すことができる。一部の実装形態では、基本電子地図は、壁などの構造上の仕切りを示す様々な線を含むことができ、この構造上の仕切りは囲われた空間として部屋を形成する。しかしながら、一部の実装形態では基本電子地図は、基本電子地図上に回廊または部屋の位置を示すための注釈を含んでいない場合がある。
【００１２】
一部の実装形態では、人間オペレータが基本電子地図を調べ、電子地図上の回廊、オフィス、入口通路などの項目に手作業で注釈を付ける、あるいは別の方法でこれらを特定することができる。しかしながら、人間オペレータを使用すると一部の実装形態では法外な費用がかかり、また時間がかかる(time-intensive)可能性もある。さらに、構造のレイアウトが、その後の建設段階の間に変更される場合、人間オペレータがその後時間をかけて手作業で基本電子地図を更新しなければならない。
【００１３】
一部の実装形態では、以下に説明するように、自動化された処理が実行されて、電子地図の特徴を電子的に抽出する、あるいは別の方法で判断する。例えば、基本電子地図は、最初は壁など、構造上の仕切りを示す線のみを含む場合があり、回廊、オフィス、または入口通路の位置を示さない場合がある。1つまたは複数の実装形態では、基本電子地図を分析して、基本電子地図に示される構造物内の入口通路を特定することができる。一部の実装形態では、基本電子地図が、構造物内の囲われたエリアの入口通路を特定するための1つまたは複数の注釈を含む場合がある。しかしながら、他の実装形態では、構造物内の入口通路を特定するためのこのような注釈がない場合がある。
【００１４】
1つまたは複数の実装形態では、入口通路を特定するために、画像処理法を実行することができる。本明細書で使用する「入口通路」とは、人がそこからオフィスまたは部屋など別のエリアまたは空間に入るまたは出ることができるエリアまたは空間を指すことができる。例えば入口通路は、そこからドアを開けるおよび/または閉めることができる出入口を含むことができる。例えばビルのような構造物は、1つまたは複数の入口通路を含む場合がある。1つの特定の実装形態では、ビルは1つまたは複数の入口通路を有するいくつかのオフィスまたは部屋を含む場合がある。入口通路は、2つの構造上の仕切りの間に延びることができる。
【００１５】
本明細書で使用する「構造上の仕切り」は、構造物の中の2つのエリアを物理的に分けることができる要素を指すことができる。例えば、床から天井に延びるビル内の壁、または床と天井との間の一方向の部分を構造上の仕切りとみなすことができる。構造上の仕切りは、例えば2つの入口通路の間に延びる場合がある。
【００１６】
例えば、一部の基本電子地図は、特定の構造上の仕切りに結合して、そこから斜めに延びている線分を含むことができる。このような線分を配置することによって、入口通路を特定することができる。一部の実装形態では、垂直の線分に湾曲した線分/弧を付けることができ、入口通路の位置がこのような弧内となるように決定することができる。例えば弧が、壁など構造上の仕切りに一端を取り付けられたドアの動く範囲を示すことができる。他の実装形態では、入口通路は、例えば点線を使用すること、または入口通路を示す文字「d」など指定文字を含めることによってなどの異なる方法で示すことができる。
【００１７】
図1Aおよび1Bは、1つまたは複数の実装形態により囲われたエリアへの入口通路を示すためのあらかじめ定義されたマーキングを有する電子地図の断片を示す。図1Aは、入口通路15を有する囲われたエリア10を示す。この例では構造上の仕切りまたは囲われたエリア10の壁から斜めに延びる線分20が、入口通路15の位置を示す。例えば線分20は、誰かが入口通路15から出入りできるようにドアを開閉することができるエリアを示すことができる。
【００１８】
図1Bは、入口通路55を有する囲われたエリア50を示す。この例では囲われたエリア50の隅に弧60を表示して入口通路55の位置を示す。弧60は、誰かが入口通路55から出入りできるようにドアが開閉可能である可動域またはエリアを示すことができる。
【００１９】
例えば一定のあらかじめ定義されたマーキングのような電子的に抽出される特徴に少なくとも部分的に基づいて、1つまたは複数の入口通路を特定した後に、図3〜9に関して以下に説明するように、このような入口通路を利用して、構造物内の1つまたは複数の回廊または廊下の位置を特定することができる。本明細書で使用する「回廊」、または「廊下」は、相対する構造上の仕切りおよび/または入口通路の間の空間またはエリアに沿って延びる通路を指すことができる。例えば人は、第1の入口通路を移動して回廊へ出ると第2の入口通路へ到達することができる。人が例えばオフィスビルのような構造物において第1の位置から第2の位置へ移動する場合、ユーザは1つまたは複数の回廊を通って移動する可能性がある。
【００２０】
1つまたは複数の電子地図上で回廊が特定された後、例えば地図アプリケーションが回廊の位置を利用して、電子地図に示されたビルまたは他の構造物の1つまたは複数のフロアのある位置から別の位置へのユーザのルートを決めることができる。
【００２１】
図2は、1つまたは複数の実装形態によるナビゲーションシステム100の概略図である。図のように、ナビゲーションシステム100は、地図サーバ105と、ネットワーク110と、基本地図ソース115と、モバイル装置120とを含むことができる。基本地図ソース115は、メモリを含むことができ、例えば入口通路または回廊/廊下の位置を示す注釈または他の情報を含む場合がある、または含まない場合がある基本電子地図を格納することができる。基本電子地図は、1つまたは複数の入口通路または回廊を表すものとして特定することができる線分または弧の図を含むことができる。
【００２２】
1つの実装形態では、上述のように基本地図ソース115が、建造物の紙の設計図をスキャンして注釈を含まない電子フォーマットにすることによって、基本電子地図を作成することができる。あるいは、基本地図ソース115は、例えばビルを設計した建築事務所から、または公文書から、基本電子地図を取得することができる。
【００２３】
基本電子地図は、基本地図ソース115によってネットワーク110を介して地図サーバ105へ送信することができる。基本地図ソース115は、例えばデータベースまたはサーバを含むことができる。1つの実装形態では、地図サーバ105は、基本地図ソース115に特定の基本電子地図の要求を送信することができ、それに応じて特定の基本電子地図が地図サーバ105に送信されることが可能である。基本地図ソース115の中の1つまたは複数の基本地図は、例えば設計図または他の文書からスキャンすることができる。
【００２４】
地図サーバ105は、1つまたは複数の基本電子地図を分析して、入口通路、回廊、または基本電子地図上の他の項目を特定することができる。このような分析は、基本電子地図のデジタル画像処理の分析によって行うことができる。例えば、地図サーバ105は、このような画像処理を行うことができる。入口通路または回廊が特定される場合、このような入口通路または回廊に関する情報を、例えば注釈として基本電子地図に追加することができる。
【００２５】
特定の電子地図について回廊および/または入口通路が特定された場合、この電子地図はその後ナビゲーションシステムによって、地図上に示された出発位置からオフィス、ショッピングモール、スタジアム、または他の屋内環境まで人を案内するためのルート指定の指令または指示を提供するために使用される。上述のように、人は1つまたは複数の回廊によって案内され、目的地に到着することが可能である。電子地図および/またはルート指定の指令は、ユーザのモバイル装置120に送信することができる。例えば、このような電子地図および/またはルート指定の指令は、ディスプレイ画面に提示することができる。またルート指定の指令は、モバイル装置120のスピーカを通じて、またはモバイル装置120と通信してユーザに聞こえるように提示されることも可能である。地図サーバ105、基本地図ソース115、およびモバイル装置120は別個の装置とする、または様々な組合せで結合される(例えば、すべてがモバイル装置120に結合される、基本地図ソース115が地図サーバ105に結合されるなど)ことも可能である。
【００２６】
図3は、1つの実装形態による電子地図200の図である。図のように、電子地図200は、人間が見て容易に特定することができる様々な要素を含んでいる。しかしながらこのような要素は、例えば自動化された処理によって同じように簡単に特定されない可能性がある。電子地図200は、壁、および入口通路など、構造上の仕切りを最初に特定するように分析することができる。図1Aおよび1Bについて上述したように、あらかじめ定義された名称またはあらかじめ定義されたマーキングを使用して、電子地図の中の入口通路を表すことができる。
【００２７】
図4は、1つの実装形態による電子地図の断片300の図である。最初に基本地図ソースから電子地図が受信された後、電子地図は地図サーバによって分析/処理されて、電子地図上に表示される入口通路および構造上の仕切りを特定することが可能である。地図サーバが断片300を処理する場合、構造上の仕切り305、310、315、および320を特定することができる。例えば、少なくとも閾値距離延びる線分があることが、構造上の仕切りを表すものとすることができる。例えばコンピュータ支援設計(computer aided drafting、CAD)では、レイヤ内に示される線分は壁を含むことを、注釈レイヤが指定することができる。しかしながら、長い線分(例えば、ビットマップ画像中の線分など)もまた壁を特定することができる。
【００２８】
断片300は、1つまたは複数の入口通路を特定するように処理されることも可能である。この例では、2つの構造上の仕切りの間に延びる弧線の存在を見つけることができる。図のように弧線325は、構造上の仕切り320と315との間に延びている。図4に示す例では、構造上の仕切りは、入口通路の上方に延びることができる。したがって、入口通路および構造上の仕切りの位置は、一部の電子地図では部分的に重なる可能性がある。入口通路は、構造上の仕切り320の一部と重なっている位置A330、または構造上の仕切り315の一部と重なっている位置B335にある可能性がある。入口通路が位置A330にあるか、位置B335にあるか、または場合によっては両方にあるかを判断するために、電子地図の隣接部分を処理して入口通路の可能性が最も高い位置を判断することができる。例えば、電子地図の一部に互いに隣接して配置された部屋の列がある場合、部屋に至る入口通路は、例えば回廊に面した、同じ側にある可能性が高い。この例では、構造上の仕切り340が構造上の仕切り320に結合され、構造上の仕切り315と平行に、ここから離れる方向に延びていると特定される場合、入口通路は位置B335にあると判断することができる。
【００２９】
図3に戻ると、電子地図200の入口通路および構造上の仕切りは、図4に関して上述したものと同様のプロセスによって判断することができる。図のように、入口通路205、210、215、220、225、230、235、240、および245を特定することができる。入口通路が特定された後、このような入口通路の位置を利用して電子地図内の回廊の位置を特定することができる。
【００３０】
電子地図上に示された1つまたは複数の回廊を特定するための1つの方法は、特定の入口通路を選択し、この入口通路から電子地図に示す他の入口通路の一部または全部に直線分(straight line segment)を描くことである。特定の入口通路から別の入口通路へ描かれた線分が、どの構造上の仕切りとも交差することなく、同じ部屋、オフィス、または囲まれたエリア内の入口通路間に延びていない場合、2つの入口通路は視線内にある。
【００３１】
図5は、1つまたは複数の実装形態により入口通路405の視線内の入口通路を示す電子地図400の図を示す。図のように、入口通路410、415、420、および425は、それぞれ入口通路405の視線内にある。一方で、入口通路430、435、440、および445は、入口通路405の視線内にはない。線分450、445、460、および465は、入口通路405からそれぞれ入口通路410、415、420、および425へ延びている。その後、線分450、445、460、および465の中間点が決定される。このような中間点の3つ以上を通って実質的な直線を描くことができる場合、この実質的な直線は、直線に沿って延びる回廊の存在を示すことができる。このようなプロセスは、例えば湾曲していない、実質的に直線である回廊または回廊の一部を特定することができる。しかしながら、回廊または回廊の一部が湾曲している場合、このようなプロセスは、直線部分があれば回廊の様々な直線部分を個々に特定するために利用することができる。
【００３２】
図5は、入口通路405の視線内に4つの入口通路があり、このような視線内の入口通路間に延びる線分の中間点に基づいて、回廊を判断することができる方法を示す。上述のように、このようなプロセスは、同じ部屋、オフィス、または他の囲われたエリア内にない視線内の入口通路に利用することができる。特定の入口通路の視線内に1つまたは2つの入口通路しかない場合、2つ以上の入口通路から視線内の他の入口通路へ線分を描くことができる。このような線分を描いた後に、このような線分のそれぞれの中間点を通って線が描かれて、回廊の位置を特定することができる。
【００３３】
図6は、1つまたは複数の実装形態により特定される回廊505を示す電子地図500の図である。図6には、入口通路405とそれぞれ入口通路410、415、420、および425との間に延びる線分450、455、460、および465のそれぞれの中間点を通って描かれる線505を示す。回廊が直線であって、回廊の反対側にある構造上の仕切りおよび入口通路が回廊と平行である場合、線分450、455、460、および465のそれぞれの中間点は回廊の中間に位置しており、したがってこのような中間点を通る線505を描くことができる。線505は、任意の構造上の仕切りに到達するまで延ばすことができる。線505が描かれた後、線505に沿って延びる回廊510を特定することができる。
【００３４】
回廊505を特定したが、図6に示す第2の回廊515があって、これを特定することができる。図のように、回廊515に沿って位置する2つの入口通路440および445がある。しかしながら、入口通路440または445のいずれの視線内にも入口通路がない。したがって、図5および6に関して上述した方法は、回廊515を特定するために利用することができない可能性がある。代わりに、図7に関して以下に記載する方法を利用して、回廊515を特定することができる。
【００３５】
図7は、1つまたは複数の実装形態による電子地図600の図である。図7は、回廊515または片側、例えば回廊の共通した側にのみ入口通路が配置された任意の回廊を特定するための方法の実装形態を示している。まず、2つの入口通路間に線が描かれる。この例では、入口通路440と入口通路445との間に線605を描き、線605の両端が構造上の仕切りに到達するまで延ばす。次に、線605の実質的に垂直な二等分線を定め、線605の中間点から垂直二等分線610を描き、線610の両端が構造上の仕切りに到達するまで線605に実質的に垂直な方向に延ばす。次に、線610の両端と入口通路440および445のそれぞれの中間点との間で線分615、620、625、および630を描く。2つの隣接した線分がいかなる構造上の仕切りも交差しない場合、入口通路440と入口通路445との間に延びる直接路があると推論することができる。この例では、線分620および630が遮られていない。したがって、回廊515は、線分620および630が位置する空間を通って延びる可能性があると推定することができる。言い換えれば、図7に示すように、線分630は、入口通路445から垂直二等分線610の一端まで延び、線分620は、入口通路440から垂直二等分線610の同じ端まで延びる。したがって、回廊515は、線分620および630が位置する空間を通って延びる可能性がある。
【００３６】
回廊515は、したがって入口通路440および445が線分620および630のそれぞれの端部と関連する共有点に直接アクセスしやすいことに少なくとも部分的に基づいて特定することができる。このような共有点は、図7に示すように線分620および630が線610の一端で合流する点を含むことができる。
【００３７】
図8は、1つまたは複数の実装形態による電子地図700の図を示す。図8は、入口通路と反対側の構造上の仕切りまたは他の入口通路との間に延びる線分の中間点に少なくとも部分的に基づいて回廊を特定するための方法の実装形態を示す。図8では、垂直の線分が通路から出て、反対側の構造上の仕切りまたは入口通路に到達するまで延びる。線が実質的にこのような線分のそれぞれの中間点を通って出て、線の各端部が構造上の仕切りに到達するまで延びる場合、このような線は回廊の中央を示す可能性がある。
【００３８】
図8では、線分705、710、715、720、725、730、740、745、および750が、入口通路から反対側の構造上の仕切りまたは入口通路まで延びて描かれる。第1の線755が、線分705、710、715、720、725、730、および740の中間点を通って描かれる可能性があり、第2の線760は、線分745および750の中間点を通って描かれる可能性がある。第1の回廊510が第1の線755に沿って延びる可能性があり、第2の回廊515が第2の線760に沿って延びる可能性がある。
【００３９】
湾曲した回廊を特定するには、垂直線分を使用して回廊を特定する方法が役立つ可能性がある。図9は、1つまたは複数の実装形態による湾曲した回廊を示す電子地図800の図を示す。入口通路802、804、806、808、810、812、814、816、818、820、822、および824を図9に示す。入口通路から反対側の構造上の仕切りまたは入口通路へ向かって、垂直線分を描くことができる。例えば線分826、828、830、832、834、836、838、840、842、844、および846について説明する。このような線分の中間点を決定することができ、次いでこのような中間点を通して直線を描くことができる。この例では、線分826、828、830、832、834、836、および838の中間点を通って延びる線848を描くことができる。線848は、両端が構造上の仕切りに到達するまで延びることができる。線850は、線分840、842、844、および846を通して描くことができる。線850は、両端が構造上の仕切りに到達するまで延びることができる。
【００４０】
図9は、湾曲した回廊を示している。線850および848は、点852で交差する。点852の位置に基づいて、第1の回廊が線848に沿って延び、第2の回廊が線850に沿って延びると判断することができる。したがってこのような線を利用して、1つまたは複数の回廊のそれぞれの位置を判断することができる。
【００４１】
図1〜9に関して上述した様々な実装形態は、したがって入口通路および回廊の位置を判断するために利用することができる。電子地図を分析するとき、例えば構造上の仕切りまたは入口を示す様々な線分またはあらかじめ定義されたマーキングを特定し、対応するデカルト格子に関連付けることができる。デカルト格子上の様々な構造要素の位置を利用して、電子地図上の回廊の位置を判断することができる。例えば、電子計算プラットフォーム上で線形方程式および/または非線形方程式の組を使用して、電子地図をモデル化することができる。例えば、入口通路から線分が出ることおよび/または延びることを、電子計算プラットフォーム上で線形方程式および非線形方程式の組を使用してモデル化することができる。
【００４２】
図10は、1つまたは複数の実装形態により電子地図上で1つまたは複数の回廊を特定するためのプロセス900の流れ図である。例えばプロセス900は、地図サーバによって実行されることが可能である。まず工程905において、構造物の特徴を示す1つまたは複数の電子地図が、例えば電子地図のデータベースからアクセスされる、または受信されることが可能である。次に工程910において、1つまたは複数の電子地図からの特徴を電子的に抽出することができる。例えば、画像処理アプリケーションプログラムを利用して、このような特徴を電子的に抽出することができる。工程915において、1つまたは複数の電子地図上の1つまたは複数の回廊を特定することができる。例えば、特徴に少なくとも部分的に基づいて、少なくとも1つの電子的に抽出された入口通路と1つまたは複数の電子的に抽出された構造要素あるいは1つまたは複数の他の入口通路との間に延びる1つまたは複数の線分に少なくとも部分的に基づいて、このような回廊を特定することができる。工程920において、1つまたは複数の電子地図は、1つまたは複数の回廊を特定する1つまたは複数の注釈を付けて更新することができる。
【００４３】
図11は、1つの実装形態による地図サーバ1000の特定の実装の概略ブロック図である。地図サーバ1000は、例えば処理ユニット1005と、メモリ1010と、送信機1015と、受信機1020とを含むことができる。メモリ1010は、機械可読命令を含むように構成することができ、機械可読命令は、説明もしくは提案した処理、実行、またはその例のうちの1つまたは複数を行うように実行可能である。処理ユニット1005は、このような機械可読命令にアクセスしてこれを実行するように構成することができる。こうした機械可読媒体の命令を実行することにより、処理ユニット1005は、1つまたは複数の機能を行うよう地図サーバ1000の様々な要素に指示することができる。
【００４４】
メモリ1010はまた、基本電子地図を格納して処理ユニット1005によって分析され、入口通路および回廊の位置を判断し、このような電子地図を1つまたは複数の注釈を付けて更新することができる。送信機1015は、1つまたは複数の電子地図を、ユーザのモバイル装置など別の装置に送信することができる。このような電子地図を受信すると、ユーザのモバイル装置は例えばディスプレイ装置によって更新された電子地図を提示することができる。受信機1020は、例えば基本電子地図ソースから分析するための1つまたは複数の基本電子地図を受信することができる。
【００４５】
上記の詳細な説明のいくつかの部分は、特定の装置または特殊用途の計算装置もしくはプラットフォームのメモリ内に格納された2値デジタル信号上の動作のアルゴリズムまたは記号表現(symbolic representations)に関して提示されている。この特定の明細書の文脈では、特定の装置または同様のものという用語は、汎用コンピュータがプログラムソフトウェアからの命令に従って特定の機能を行うようにプログラムされると汎用コンピュータを含む。アルゴリズムの記述または記号表現は、信号処理または関連技術において当業者がその研究の内容を他の当業者に伝えるために使用する技術の例である。本明細書では、また一般的に、アルゴリズムは、所望の結果につながる自己矛盾のない一連の動作、または同様の信号処理であるとみなされる。この文脈では、動作および処理は、物理量の物理的操作を伴う。必ずしもそうではないが一般にはこのような量は、格納、転送、合成、比較、またはその他の操作が可能である電気信号、または磁気信号の形態をとることができる。
【００４６】
主として一般的に使用するという理由により、これらの信号をビット、データ、値、要素、記号、文字、用語、数字などと呼ぶことが、時には好都合であることがわかっている。しかしながら、これらの用語または同様の用語のすべては、適切な物理量と関連付けられなければならず、便利なラベルにすぎないことを理解すべきである。上記の記述から明らかのように、特に記載のない限り、本明細書を通して「処理する」、「計算する」、「算出する」、「決定する」などの用語を使用すると、特殊用途コンピュータまたは同様の特殊用途電子コンピュータ装置など特定の装置の動作または処理を指すことが理解されよう。したがって本明細書の文脈では、特殊用途コンピュータまたは同様の特殊用途電子計算装置は、メモリ、レジスタ、もしくは他の情報記憶装置、送信装置、あるいは特殊用途コンピュータまたは同様の特殊用途電子計算装置のディスプレイ装置内の物理的電子量または磁気量として一般に表される、信号を操作または変換することができる。例えば、特定の計算装置は、1つまたは複数の特殊機能を行うための命令でプログラムされた1つまたは複数の処理ユニットを含むことができる。
【００４７】
本明細書で使用するモバイル装置とは、セルラ式または他の無線通信装置(携帯電話など)、パーソナルコミュニケーションシステム(PCS)装置、パーソナルナビゲーション装置(PND)、パーソナルインフォメーションマネージャ(PIM)、携帯情報端末(PDA)、ラップトップ、タブレット、ネットブック、スマートブック、あるいは無線通信および/またはナビゲーション信号を受信することができる他の好適な装置などの装置を指す。また「モバイル装置」という用語は、装置またはパーソナルナビゲーション装置(PND)で、衛星信号の受信、支援データの受信、および/または位置関連の処理が行われるかどうかに関わらず、例えば短距離無線、赤外線、有線接続、または他の接続によって、パーソナルナビゲーション装置(PDN)と通信する装置を含むよう意図されている。また「モバイル装置」は、無線通信装置、コンピュータ、ラップトップなどを含む、インターネット、Wi-Fi、または他のネットワークを介してサーバと通信することができるすべての装置を含むよう意図されており、衛星信号の受信、支援データの受信、および/または位置関連処理が装置で、サーバで、またはネットワークと関連する別の装置で行われるかどうかに無関係である。上記のいかなる動作可能な組合せも、同様に「モバイル装置」とみなされる。
【００４８】
本明細書に記載する方法は、特定の特徴および/または例に従った用途によって決まる様々な手段によって実施することができる。例えばこのような方法は、ハードウェア、ファームウェア、ソフトウェア、および/またはその組合せで実施することができる。例えばハードウェアを伴う実施では、1つまたは複数の特定用途向け集積回路(ASIC)、デジタル信号プロセッサ(DSP)、デジタル信号処理デバイス(DSPD)、プログラマブルロジックデバイス(PLD)、フィールドプログラマブルゲートアレイ(FPGA)、プロセッサ、コントローラ、マイクロコントローラ、マイクロプロセッサ、電子デバイス、本明細書に記載した機能を実行するように設計されたその他のユニット、および/またはその組合せの中に、処理ユニットを実装することができる。
【００４９】
ファームウェアおよび/またはソフトウェアを伴う実施については、いくつかの方法は、本明細書に記載する機能を実行するモジュール(例えばプロシージャ、関数など)で実装することができる。本明細書に記載する方法を実施する際に、命令を具体的に取り入れるいかなる機械可読媒体も使用することができる。例えばソフトウェアコードは、モバイル装置のメモリ、アクセスポイント/フェムトセル、サーバなどに格納され、装置の処理ユニットによって実行することができる。処理ユニット内におよび/または処理ユニット外に、メモリを実装することができる。本明細書で使用する「メモリ」という用語は、いかなるタイプの長期、短期、揮発性、不揮発性、または他のメモリを指し、メモリまたはいくつかのメモリの特定のタイプ、あるいはメモリが格納される媒体のタイプに限定されないものとする。
【００５０】
実施がファームウェアおよび/またはソフトウェアを伴う場合、機能は、コンピュータ可読媒体上に1つもしくは複数の命令またはコードとして格納されることが可能である。例には、データ構造でコード化されたコンピュータ可読媒体、およびコンピュータプログラムでコード化されたコンピュータ可読媒体が含まれる。コンピュータ可読媒体は、製造品の形態をとることができる。コンピュータ可読媒体は、物理的なコンピュータ記憶媒体を含む。記憶媒体は、コンピュータによってアクセスすることができるいかなる入手可能な媒体であってもよい。例としては、このようなコンピュータ可読媒体は、RAM、ROM、EEPROM、CD-ROMもしくは他の光ディスク記憶装置、磁気ディスク記憶装置、半導体記憶装置、または他の記憶装置、または命令もしくはデータ構造の形式で所望のプログラムコードを格納するために使用することができる他のいかなる媒体も含むことができるが、これらに限定ではなく、本明細書で使用するディスク(disk)およびディスク(disc)には、コンパクトディスク(compact disc、CD)、レーザディスク（登録商標）(laser disc)、光ディスク(optical disc)、デジタル多用途ディスク(digital versatile disc、DVD)、フレキシブルディスク(floppy disk)、およびBlu-ray discが含まれるが、ディスク(disk)は通常磁気的にデータを再生し、ディスク(disc)はレーザを使用して光学的にデータを再生する。上記のものの組合せもまた、コンピュータ可読媒体の範囲内に含まれるべきである。
【００５１】
コンピュータ可読媒体上に記憶することに加えて、命令および/またはデータを通信装置に含まれる伝送媒体上の信号として提供することができる。例えば、通信装置は、命令およびデータを示す信号を有するトランシーバを含むことができる。命令およびデータは、1つまたは複数の処理ユニットに特許請求の範囲に要点を述べる機能を実施させるように構成される。すなわち、通信装置は、開示の機能を実行するための情報を示す信号を有する送信媒体を含む。第1に、通信装置に含まれる送信媒体は、開示の機能を行うための情報の第1の部分を含むことができ、第2に、通信装置に含まれる送信媒体は、開示の機能を行うための情報の第2の部分を含むことができる。
【００５２】
本明細書で呼ぶ「命令」は、1つまたは複数の論理演算を表す式と関連する。例えば命令は、1つまたは複数のデータオブジェクト上で1つまたは複数の演算を実行するために機械によって解釈できることにより「機械可読」とすることができる。しかしながら、これは命令の一例にすぎず、特許請求の範囲に記載される対象物はこの点において限定されない。別の例では、本明細書で呼ばれる命令は、コード化されたコマンドを含むコマンドセットを有する処理ユニットによって実行可能であるコード化されたコマンドに関連する場合がある。このような命令は、処理ユニットによって理解される機械言語の形式でコード化することができる。やはりこれらは命令の例であるにすぎず、特許請求の範囲に記載する対象物はこの点において限定されない。
【００５３】
現在例示的特徴であるとみなされるものを示して説明したが、特許請求の範囲に記載する対象物から逸脱することなく、様々な他の変更形態を作成できること、および等価物を代用できることは、当業者には理解されるであろう。さらに、本明細書に記載する主要な概念から逸脱することなく、特定の状況を特許請求の範囲に記載する対象物の教示に適合させるために、多くの変更形態を作成することができる。したがって、特許請求の範囲に記載する対象物は、開示する特定の例に限定されず、このような特許請求の範囲に記載する対象物は、添付の特許請求の範囲の範囲内に入るあらゆる態様、およびその等価物もまた含むことができるように意図されている。
【符号の説明】
【００５４】
10  囲われたエリア
15  入口通路
20  線分
50  囲われたエリア
55  入口通路
60  弧
100  ナビゲーションシステム
105  地図サーバ
110  ネットワーク
115  基本地図ソース
120  モバイル装置
200  電子地図
【図１Ａ】
2013507717.tif 000003
【図１Ｂ】
2013507717.tif 000004
【図２】
2013507717.tif 000005
【図３】
2013507717.tif 000006
【図４】
2013507717.tif 000007
【図５】
2013507717.tif 000008
【図６】
2013507717.tif 000009
【図７】
2013507717.tif 000010
【図８】
2013507717.tif 000011
【図９】
2013507717.tif 000012
【図１０】
2013507717.tif 000013
【図１１】
2013507717.tif 000014
【国際調査報告】
2013507717.tif 000015
2013507717.tif 000016