公開エリア地図
【課題】建物の各階、公園等の公開エリアを移動する際、エリアのレイアウトについての知識不足等のため、思うように移動できないことがある。
【解決手段】公開エリア地図に関連したシステム及び方法が開示される。例えば、１つの方法は、レイアウトの画像を取得する段階を含む。レイアウトは、人が動き回る現実世界のエリアを表す。グリッドが画像上に適用される。グリッドは、画像の接地エリアを満たすタイルを含む。ルーティング可能な地図が、グリッドの関数として生成される。ルーティング可能な地図は、レイアウト内でポイントツーポイントルーティングを行うように構成される。
【解決手段】公開エリア地図に関連したシステム及び方法が開示される。例えば、１つの方法は、レイアウトの画像を取得する段階を含む。レイアウトは、人が動き回る現実世界のエリアを表す。グリッドが画像上に適用される。グリッドは、画像の接地エリアを満たすタイルを含む。ルーティング可能な地図が、グリッドの関数として生成される。ルーティング可能な地図は、レイアウト内でポイントツーポイントルーティングを行うように構成される。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願の相互参照）
本特許出願は、同日に出願された名称「ＣＯＳＴ ＢＡＳＥＤ ＯＰＥＮ ＡＲＥＡ ＭＡＰＳ」の同時係属米国特許出願第 号（代理人事件簿第Ｎ０２７５ＵＳ号）、名称「ＯＰＥＮ ＡＲＥＡ ＭＡＰＳ ＷＩＴＨ ＲＥＳＴＲＩＣＴＩＯＮ ＣＯＮＴＥＮＴ」の同時係属米国特許出願第 号（代理人事件簿第Ｎ０２７６ＵＳ号）、名称「ＥＮＤ ＵＳＥＲ ＩＭＡＧＥ ＯＰＥＮ ＡＲＥＡ ＭＡＰＳ」の同時係属米国特許出願第 号（代理人事件簿第Ｎ０２７７ＵＳ号）、名称「ＰＯＳＩＴＩＯＮＩＮＧ ＯＰＥＮ ＡＲＥＡ ＭＡＰＳ」の同時係属米国特許出願第 号（代理人事件簿第Ｎ０２７８ＵＳ号）、名称「ＯＰＥＮ ＡＲＥＡ ＭＡＰＳ ＷＩＴＨ ＧＵＩＤＡＮＣＥ」の同時係属米国特許出願第 号（代理人事件簿第Ｎ０２７９ＵＳ号）、及び名称「ＯＰＥＮ ＡＲＥＡ ＭＡＰＳ ＢＡＳＥＤ ＯＮ ＶＥＣＴＯＲ ＧＲＡＰＨＩＣＳ ＦＯＲＭＡＴ ＩＭＡＧＥＳ」の同時係属米国特許出願第 号（代理人事件簿第Ｎ０２８０ＵＳ号）の関連出願であり、これら特許出願の開示内容全体は引用により本明細書に組み込まれる。
【０００２】
本発明は、ナビゲーションに関し、更に詳細には、ルーティング（経路選択）に使用することができる公開エリア地図(open area map)に関する。
【背景技術】
【０００３】
世界人口が増加するにつれて、人類の発達を支える益々多くのインフラストラクチャー、建物、外部及び内部開発及び他の地物が生成されている。既存のインフラストラクチャー、建物、公園及び他の環境もまた、より多くの人々及び往来に対応するように適応されつつある。環境の増加及び適応は、ある場所から別の場所への移動及び人々の移動方法に影響を与える。
【０００４】
ナビゲーションシステム及び／又はデバイスは、移動を支援するのに使用される。例えば、車両ナビゲーションデバイスは、人が道路網を運転するのを支援することができる。このようなデバイスは、既存の道路又は経路に基づいて所望の目的地までのルーティング及び案内を行うことができる。
【０００５】
しかしながら、道路、路線又は経路が設定されていないエリア(area)を人々が動き回るエリア、又はエリア内で１つの地点から別の地点に移動する上で、このような経路が必要ではないエリアがある。例えば、建物の各階、公園或いは他の外部又は内部エリアを日常的に歩いている。人々は、このようなエリア内で多くのパターンで動き回り、１つの場所から別の場所に到達することができる。しかしながら、これらのエリア内での一部の移動又は移動パターンは、混乱や、エリアのレイアウトについての知識不足又は他の要素により、非効率であったり不必要な場合がある。また、人は、このようなエリア内で１つの地点から所望の目的地に到達するための方法を知らない可能性がある。
【発明の概要】
【課題を解決するための手段】
【０００６】
１つの態様によれば、公開エリア地図を生成する方法が提供される。本方法は、レイアウトの画像を取得する段階を含む。レイアウトは、人が動き回る現実世界のエリアを表す。グリッドが画像上に適用される。グリッドは、画像の接地エリアを満たすタイルを含む。ルーティング可能な地図が、グリッドの関数として生成される。ルーティング可能な地図は、レイアウト内でポイントツーポイントルーティングを行うように構成される。
【０００７】
本発明は、添付の請求項により定められ、このセクションのいかなるものも上記の請求項に対する限定とするべきではない。本発明の更なる態様及び利点は、好ましい実施形態に関連して以下で説明する。
【図面の簡単な説明】
【０００８】
【図１】公開エリア地図を生成するシステムの図である。
【図２】図１のシステムにおいて使用されるレイアウトの画像である。
【図３】図１のシステムにおいて使用されるプロセスに対応する画像である。
【図４】図１のシステムにおいて使用される別のプロセスに対応する別の画像である。
【図５】図２の画像に対応する基準領域を例示する図である。
【図６】図１のシステムにより生成された公開エリア地図の画像である。
【図７】図１のシステムにより生成された別の公開エリア地図の別の画像である。
【図８】公開エリア地図を生成する方法のフローチャートである。
【図９】図８の方法の段階の例を示すフローチャートである。
【図１０】公開エリア地図内のルーティングの方法のフローチャートである。
【発明を実施するための形態】
【０００９】
図１は、１つ又はそれ以上の公開エリア地図を生成するのに使用されるシステム１００の一実施形態を示す。システム１００は、これに限定するものではないが、１つ又は複数の画像ソース１０４、ネットワーク１０８、デバイス１１２、ネットワーク又は接続部１２０、データベース１７０、ネットワーク１８０、及びユーザデバイス１１６を含む。付加的な、又はより少ない、或いは異なる構成部品を設けてもよい。例えば、プロキシサーバ、ネームサーバ、地図サーバ、キャッシュサーバもしくはキャッシュネットワーク、ルータ、スイッチもしくはインテリジェントスイッチ、地理データベース、付加的なコンピュータもしくはワークステーション、管理ワークステーションのような管理構成部品、ゲートウェイデバイス、バックボーン、ポート、ネットワーク接続部、及びネットワークインタフェースを設けることができる。図１の構成部品は互いに別個に示されているが、これらの構成部品の１つ又はそれ以上を組み合わせてもよい。
【００１０】
画像ソース１０４は、ウェブサイト、アプリケーション、プログラム、ワークステーションもしくはコンピュータ、ファイル、メモリ、サーバ、ビーコンもしくは地図ビーコン、デポジトリ、及び／又は画像又は画像に関連するデータを格納又は含むことができるあらゆる他のハードウェア及び／又はソフトウェアコンポーネント又はデータベースである。或いは、画像ソース１０４は、１つ又はそれ以上の画像である。
【００１１】
一実施形態においては、画像ソース１０４は、レイアウトの１つ又はそれ以上の画像を含む。画像は、ＪＰＥＧ、ビットマップ、ピックスマップ、Ｔｉｆｆ又は他の画素又はラスタベースのファイル形式のような、ラスタ又は画素ベースの画像である。画像は、紙又はハードレイアウトのラスタ又は画素化されたスキャンしたコピーとすることができる。或いは、画像は、ベクトルベース又はベクトル化画像とすることができる。レイアウトは、人、歩行者又は人々が歩行及び／又は動き回る現実世界のエリアに対応することができる。レイアウトはまた、未だ構築されていない将来の現実世界のエリアに対応することもできる。或いは、レイアウトは、架空の場所、設定又はエリアに対応することができる。
【００１２】
レイアウトは、未編成又は無制約の地理的エリアを表すことができる。例えば、レイアウトは、歩行者が、設定された道路網又は経路網上でのみ移動するように限定されていないエリアである。むしろ、歩行者は関連した道路又は経路網或いはパターンのない公共の広場、公園、建物、通路、ロビー又は廊下を通り抜けることができる。加えて、歩行者には、道路上の移動体として方向制約がない。更に、歩行者は、レイアウトにおいて運動の自由度がより大きく、あらゆる所与の公開領域内であり余る程の自ら決定する経路から選ぶことができる。
【００１３】
レイアウトの画像は、現実世界の建物の平面図、駐車場、公園、屋内又は屋外のレクリエーションエリア及び／又は人が歩行又は移動することができる（例えば、車椅子、自転車又は他の移動支援デバイスを介して）場所に対応する他の内部及び外部エリアの施設の画像を含むことができる。画像は、既存の画像又は公的に利用可能な画像である。例えば、画像は、本来、ルーティング可能な地図を生成すること以外の目的で形成又は作成される。既存の画像は、ルーティング可能な公開エリア地図の開発者及び／又はそのエンドユーザとは別のエンティティにより生成することができる。既存画像は、無料で或いは購入価格（例えば、オンライン）を支払うことで、一般の人々又はエンティティが利用可能である。或いは、自然発生画像、ルーティング可能な地図を作成するのに当初生成された画像、又は非公的な画像を用いることができる。
【００１４】
画像ソース１０４は、ネットワーク１０８を介してデバイス１１２と通信している。ネットワークは、インターネット、イントラネット、ローカルエリアネットワーク（「ＬＡＮ」）、広域ネットワーク（「ＷＡＮ」）、仮想プライベートネットワーク（「ＶＰＮ」）、ローカル無線又は有線接続部（例えば、ＵＳＢ接続部又は他のデバイス接続部）、及び／又は何らかの公知の又は将来のネットワーク又は接続部である。
【００１５】
デバイス１１２は、ルーティング可能な公開エリア地図を生成するためレイアウトの画像を画像ソース１０４から受信する。デバイス１１２は、ワークステーション、コンピュータ、編集デバイス、ビーコン又は地図ビーコン、及び／又は他のコンピュータ又は送信デバイスである。例えば、デバイス１１２は、編集ワークステーションである。デバイス１１２は、これに限定するものではないが、ディスプレイ１２４、プロセッサ１２８、メモリ１３２、アプリケーション１３４及び入力デバイス１３６を含む。付加的な、又はより少ない、或いは異なる構成部品を設けてもよい。オーディオコンポーネントを設けることができる。例えば、スピーカ、オーディオジャック、及び／又は可聴又は音声信号を出力又は受信する他のコンポーネントが設けられる。
【００１６】
ディスプレイ１２４は、デバイス１１２内で、又はデバイス１１２上で、或いはデバイス１１２と通信して表示にアクセス可能にするように位置決めされた何らかの機械式又は電子式ディスプレイである。例えば、ディスプレイ１２４は、タッチスクリーン、液晶ディスプレイ（ＬＣＤ）、陰極線管（「ＣＲＴ」）ディスプレイ、又はプラズマディスプレイである。ディスプレイ１２４は、レイアウト、平面図、地図又は他のエリアの画像などの画像を表示するように動作可能である。入力デバイス１３６は、ボタン、キーパッド、キーボード、マウス、トラックボール、ロッカスイッチ、タッチパッド、音声認識回路、又は、デバイス１１２でデータを制御又は入力する他のデバイス又は構成部品である。入力デバイス１３６を使用して、受信画像の修正（例えば、ドア又は開口部を追加する）、又は消去ツールを使用するなどの機能を実行することができる。
【００１７】
プロセッサ１２８は、メモリ１３２、アプリケーション１３４、ディスプレイ１２４、及び入力デバイス１３６と通信している。プロセッサ１２８は、より多くの又はより少ない構成部品と通信状態になることができる。プロセッサ１２８は、汎用プロセッサ、特定用途向け集積回路（「ＡＳＩＣ」）、デジタル信号プロセッサ、フィールドプログラマブルゲートアレイ（「ＦＰＧＡ」）、デジタル回路、アナログ回路、又はこれらの組み合わせである。プロセッサ１２８は、デバイス１１２の様々な電子部品及びロジックを制御し、及び／又はこれらと通信するように動作可能な１つ又はそれ以上のプロセッサである。プロセッサ１２８、メモリ１３２、及び他の回路は、集積回路の一部であってもよい。
【００１８】
メモリ１３２は、何らかの公知の又は将来の記憶装置である。メモリ１３２は、ランダムアクセスメモリ「ＲＡＭ」（電子部品）、読取り専用メモリ「ＲＯＭ」（電子部品）、又は消去可能プログラマブル読取り専用メモリ（ＥＰＲＯＭ又はフラッシュメモリ）など、不揮発性及び／又は揮発性メモリである。メモリネットワークを設けてもよい。メモリ１３２は、プロセッサ１２８の一部とすることもできる。メモリ１３２は、画像ソース１０４により受信されたレイアウトの画像を格納するように動作可能であり、又は構成される。メモリ１３２はまた、プロセッサ１２８により生成された画像又はデータを格納することもできる。
【００１９】
プロセッサ１２８は、アプリケーション１３４を実行するように動作可能であり、又は構成される。アプリケーション１３４は、画像ソース１０４から受信される画像など、既存画像に基づいてルーティング可能な公開エリア地図を生成するのに使用されるソフトウェアプログラムである。例えば、プロセッサ１２８は、アプリケーション１３４を実行して、入力デバイス１３６からの入力及び／又は自動コマンドからの入力を介してルーティング可能な地図を作成又は生成し、或いはその生成を支援する。アプリケーション１３４は、メモリ１３２及び／又は他のメモリ内に格納することができる。
【００２０】
デバイス１１２は、ユーザデバイス１１６に１つ又はそれ以上の生成されたルーティング可能な公開エリア地図を送信又は伝送するように動作可能であり、又はそのように構成され、或いは、ユーザデバイス１１６は、ネットワーク又は接続部１２０を介してルーティング可能な公開エリア地図をリクエストすることができる。接続部１２０は、インターネット、イントラネット、ローカルエリアネットワーク（「ＬＡＮ」）、広域ネットワーク（「ＷＡＮ」）、仮想プライベートネットワーク（「ＶＰＮ」）、ローカル無線又は有線接続部（例えば、ＵＳＢ接続部又は他のデバイス接続部）及び／又は公知の又は将来のネットワーク又は接続部である。
【００２１】
或いは、デバイス１１２は、１つ又はそれ以上の生成されたルーティング可能な公開エリア地図又はそのデータをデータベース１７０に格納、アップロード、又は送信することができる。データベース１７０は、データベース、メモリ、ウェブサイト、サーバ、ビーコン、又は、ルーティング可能な公開エリア地図に対応するデータを格納、受信、及び／又は送信するのに使用される他のデバイスとすることができる。例えば、データベース１７０は、基準領域、コスト、制約事項、グリッド又はアレイ、画像データ及び／又は他のコンテンツに対応するデータのような、公開エリア地図の異なる層を表すデータエンティティを格納することができる。ユーザデバイス１１６は、デバイス１１２との通信を行わないなど、ネットワーク１８０を介してデータベース１７０からルーティング可能な公開エリア地図又はそのデータを取得することができる。ネットワーク１８０は、インターネット、イントラネット、ローカルエリアネットワーク（「ＬＡＮ」）、広域ネットワーク（「ＷＡＮ」）、仮想プライベートネットワーク（「ＶＰＮ」）、ローカル無線又は有線接続部（例えば、ＵＳＢ接続部又は他のデバイス接続部）、及び／又は、公知の又は将来のネットワーク又は接続部である。
【００２２】
また、ルーティング可能な公開エリア地図は、ユーザデバイス１１６上に「プッシュする」ことができる。例えば、ビーコン、地図ビーコン、又は、他のデバイスは、ユーザデバイス１１６の場所又は位置に基づいて、ルーティング可能な公開エリア地図又は関係するコンテンツをユーザデバイス１１６に伝送又は送信することができる。一実施形態においては、ビーコンは、建物又は他のエリアの入口又は通路に配置することができ、ユーザデバイス１１６がビーコンの特定の範囲内に入ると、エリア及び／又は他の関係するエリアに関連付けられたルーティング可能な公開エリア地図がユーザデバイス１１６に送られる。
【００２３】
ユーザデバイス１１６を用いて、それぞれのレイアウト又はエリア内で又はその上でユーザがナビゲートできるように１つ又はそれ以上のルーティング可能な地図を操作する。ユーザデバイス１１６は、携帯電話、モバイル電話、個人用携帯情報端末（「ＰＤＡ」）、時計、個人用ナビゲーションデバイス（「ＰＮＤ」）、コンピュータ、デジタル平面図デバイス、携帯型又は非携帯型のナビゲーションデバイス、キオスク及び／又は他の固定式、着脱式、又は搬送可能なデジタルデバイスである。ユーザデバイス１１６は、これに限定するものではないが、ディスプレイ１４０、プロセッサ１４４、及びメモリ１４８を含む。付加的な、又はより少ない、或いは異なる構成部品を設けてもよい。例えば、オーディオコンポーネント及び／又はアプリケーションコンポーネントを設けてもよい。ディスプレイ１４０、プロセッサ１４４、及びメモリ１４８は、それぞれ、ディスプレイ１２４、プロセッサ１２８及びメモリ１３２とは類似したものであっても、又は異なるものであってもよい。
【００２４】
一実施形態においては、建物のフロアで働いている人などのユーザは、自分が建物フロアの周囲でルーティング又はナビゲートできることを望む可能性がある。従って、画像ソース１０４内に格納されている、ユーザのフロアのレイアウト又は平面図の画像は、デバイス１１２で送受信される。地図開発者などの別のエンティティがデバイス１１２を操作する。地図開発者は、イリノイ州シカゴに所在するＮＡＶＴＥＱ Ｎｏｒｔｈ Ａｍｅｒｉｃａ， ＬＬＣのような、ナビゲーション用の地図を開発するか或いは地図データ及び／又は地理的データベースを取得及び維持する、人、会社、又はエンティティとすることができる。地図開発者は、ディスプレイ１２４上でレイアウトの既存画像を見て、入力デバイス１３６及びソフトウェアアプリケーション１３４を介して既存画像に基づいてルーティング可能な地図を生成する。自動化されたコマンド及び／又はプロセスをルーティング可能な公開エリア地図の開発において用いることができる。或いは、ルーティング可能な公開領域の作成又は生成は、実質的に全体を自動化することができる。ユーザは、ユーザデバイス１１６上で自分のフロアのルーティング可能な地図をダウンロード又は受信することができる。例えば、ユーザは、ユーザデバイス１１６を使用して、デバイス１１２、又はデバイス１１２に関連する格納サイト又は構成部品（例えば、ＵＳＢ接続部、無線接続又は他の接続部のような接続部１２０を介して）からルーティング可能な地図又はそのデータをダウンロードする。或いは、ユーザは、ユーザデバイス１１６とは異なるデバイス（例えば、コンピュータ又はジャンプ／サムドライブ）上でルーティング可能な地図をダウンロードして、次いで、ユーザデバイス１１６又は他のユーザデバイスにルーティング可能な地図に関連したデータを転送することができる。次に、ユーザは、ユーザデバイス１１６を使用して、建物フロアに関するルーティング、案内、及び／又はナビゲートを目的としてルーティング可能な地図を表示する。
【００２５】
図２は、システム１００において使用されるレイアウトの画像２０１の一実施形態である。画像２０１は、インターネット又は他のネットワークからダウンロードすることができる既存の又は公的に利用可能な画像（例えば、画像ソース１０４又は他のソースに関連するもの）である。例えば、画像２０１は、ウェブサイト又は他のソースからダウンロード、受信、取得することができる。画像２０１は、１階又は他の階など、建物フロアの現実世界のレイアウト又は平面図を表す。画像２０１は、レイアウト内のエリア、空間、及び／又は表示のグラフィック表現又はアイコンを含む。例えば、画像２０１は、男性用トイレ２１７、女性用トイレ２２１、カフェテリア２２５、事務所２２９、会議室２３３、研究室２３７、机２４１及びエレベータ又はエレベータ列２４５など、画像基準オブジェクトを含む。ドア２４９の画像表現も提供される。ドア２４９は、それぞれの画像基準オブジェクトのギャップ又は開口部として示されている。或いは、ドアは、開口部ではなく、ドアシンボル又は画像オブジェクト２５３を使用して表すことができる。或いは、ドア又は開口部の表現がない場合がある。
【００２６】
画像２０１はまた、人々が歩行又は動き回ってそのフロアのある場所から別の場所に到達するような、広場、歩行地面、共用又は公共エリア、及び／又はホールエリア２０９の画像表現を含む。壁部又は障壁は、実質的に同じ又は類似の色の対応する、又は関連する、或いは連続する画素又は線（例えば、太線）により描かれる。入口及び／又は出口２１３は、内部エリア２０９と外部エリア２０５との間でのアクセスを可能にする壁部又は障壁の開口部又はギャップとして描かれる。外部エリア２０５は、外廊下、建物の外側（例えば、歩道、通り又は道路）、又は他の外部環境を表すことができる。
【００２７】
図３は、図１のシステム１００において使用されるプロセスに対応する又は該プロセスを受ける画像２０１の一実施形態である。例えば、画像２０１は、デバイス１１２でダウンロード又は受信される。画像２０１は、ルーティング可能な公開エリア地図を作成又は生成するのに使用される。例えば、グリッド、メッシュ又はアレイ３００は、画像２０１又は画像２０１のコピーの上又はこれを覆って適用される。グリッド、メッシュ又はアレイ３００は、タイル、断面、ブロック、先端、点、円、多角形又は他の形状など幾何学的な形状（例えば、均一な大きさの幾何学的な形状）のグリッド又はアレイとすることができる。グリッド又はメッシュ３００は、画像２０１の地上エリア全体を覆う。地上エリアとは、その上を歩行することができる表面、平面、又は床、もしくはその一部、並びにオブジェクト又は障壁をその上又はこれを覆って配置又は位置決めすることができる表面を指す。
【００２８】
グリッド又はメッシュ３００は、エリア、断面、ブロック又はタイル３０４を含む。或いは、グリッド、メッシュ又はアレイ３００は、タイル３０４に類似したエリア又は断面に対応する接続されていない点又は先端を含むことができる（例えば、点又は先端は、タイル３０４に交換するか、又はタイル３０４の代替物として機能する）。タイル３０４は、略矩形又は正方形の形状を有し、大きさがほぼ均一である。或いは、タイル３０４は、円形、三角形、又は他の幾何学的又は多角形形状を有することができ、タイル３０４は、均一ではなく異なる場所で異なるサイズとすることができる。
【００２９】
グリッド３００は、画像全体又は地上エリア全体ではなく、レイアウトの特定のエリアを覆うように適用することができる。例えば、グリッド３００は、内部エリア２０９のような廊下エリア内においてのみ適用することができる。このような場合、グリッド３００は、形状が既存画像の壁部に対応する境界線を有する現実世界のエリア内の歩行者アクセス可能な連続したサブエリアに対応する形状を有する。グリッド３００又はその一部は、画像基準オブジェクト（例えば、部屋の内部エリア）内で指定されるエリアに適用することもできる。また、タイルは、連続した公開領域に自動的に埋めることができる。例えば、廊下又は通路エリアは、グリッド又はメッシュのタイル又は断面でこのエリアを自動的に埋めるように選択することができる。
【００３０】
タイル３０４は、局所的又は大域的地図座標など、座標を割り当て又は指定することができる。例えば、タイル３０４の各中央部又はタイルの他の部分には、（ｘ,ｙ）の緯度と経度、又は他の座標指定が与えられる。画像のコーナにおけるなど、タイル３０４のうちの１つは、基準及び位置決めを目的として原点（０,０）として指定することができる。座標により、アイテム、特徴部又は領域を検索可能にすることができる。しかしながら、ルーティングの目的としては座標を用いることはできない。
【００３１】
図４は、メッシュ３００が重ね合わされた後に、別の段階又はプロセスに対応又はこれらを受けた画像の一実施形態である。上を歩くべきではないタイル又はナビゲート不能のタイルは、タイル又はエリア４０１（例えば、タイル又はエリア４０１は、ナビゲート不能のエリアを表す接続されていない点又は先端と置き換えることができる）として設けられる。画像基準オブジェクトの境界又は壁部を囲むか又はこれらの下にあるタイル、或いはこれらに関連したタイル（例えば、基準オブジェクト２１７、２２１、２２５、２２９、２３３、２３７、２４１及び２４５）は、ナビゲート不可能なタイル４０１であるように選択され又は指定される。また、内部ホールエリア２０９と外部エリア２０５との間の境界、障壁又は壁の画像表現は、ルーティングを目的としてナビゲート不可能なタイル４０１と関連けられる。タイル４０１により、現実世界の体験を表現するために、種々のルートが壁部又は障壁を通り抜けることを禁止することができる。しかしながら、ドア２４９及び２５３は、タイル４０１により囲まれる部屋又はエリアを出入りするルーティングを許可するためにナビゲート可能なタイル３０４に関連付けられる。或いは、ドア又は開口部が存在しない又は作成されない場合、基準エリアに実質的に隣接又は近接するタイルは、それぞれの基準エリアを起点及び終点としたルーティングに使用することができる。
【００３２】
ナビゲート不可能なタイル４０１は、グリッド３００から除去されたタイル（或いは、点又は先端）であるか、又はそのタイルを表すことができ、或いは、ナビゲート不可能なステータスで指定されるタイル（又は点又は先端）とすることができる。ナビゲート不可能なタイル４０１又はタイルの欠如は、空きスペースとして表現することができ、このグリッド又はタイルがないスペースは、ルーティングを目的としてナビゲート不可能である。或いは、ナビゲート不可能なタイル４０１は、ナビゲート可能なタイル３０４とは異なるように着色することができる。
【００３３】
ナビゲート可能な又はナビゲート不可能なタイル、点もしくは先端は、下位分類にすることができる。例えば、各タイル又は一部のタイルは、レイアウトに関係する特徴部又は場所に関連付けることができる。一実施形態においては、タイルは、洗面所エリア、狭いエリア、窓のあるエリア、照明が薄暗いエリア、交通量の多いエリア、交通量の少ないエリア、又は他のエリア又は特徴部にリンク付け又は対応することができる。タイルを分類又は下位分類することにより、ルーティングを目的として優先度を入力することができる。例えば、ユーザは、交通量の多いエリアを回避したい場合があり、これに従って、ユーザは、ルーティング前又はルーティング中に自分の優先度を入力することができる。
【００３４】
ラップ又は境界線特徴部は、グリッド３００に関して使用することができる。特定の場合において、人は、内部エリア２０９のある地点から内部エリア２０９の別の地点までルーティングしたい場合があるが、外部エリア２０５に出て内部エリア２０９に戻るように人をルーティングする経路が生成される。このようなルートは、外側に出て内側に戻るルーティングを行う（例えば、内部エリアと外部エリアとの間に複数の開口部を有するとき）ことが最適であるときに生じる可能性がある。しかしながら、外部エリア２０５内のタイルへのあらゆるルーティングを回避するために、エリア２０９及び関連したエリア内での全てのルーティングを境界付けるラップ又は境界線特徴部を用いることができる。例えば、境界線又は指示を内部エリアの周囲に沿って配分することができる。しかしながら、境界線特徴部は、ユーザが外部エリア２０５内に又は内部エリアの外側にある目的地点を選択したときに、外部エリア２０５へのルーティングが可能となる。或いは、外部エリア２０５のタイルは、ナビゲート不可能と指定することができ、又は、外部エリア２０５への開口部をナビゲート不可能なタイル４０１と関連付けることができる。
【００３５】
接続ポイント４０５も設けられている。接続ポイント４０５は、グリッド又はメッシュ３００から別個の空間層又はデータ層内に生成又は設けることができる。接続ポイント４０５は、エリア内のタイル３０４又はタイル３０４のサブセットとして表現される。接続ポイント４０５は、エレベータ２４５のエリア全体又はその一部を包含することができる。或いは、接続ポイント４０５は、基準画像オブジェクト又は基準領域と関連付けることはできない。接続ポイント４０５は、ルーティング及びナビゲーションを目的として、ルーティング可能であるこのような公開エリア地図を表すか、又は別の地図へのリンクとして機能する。例えば、接続ポイント４０５は、１つ又はそれ以上のエレベータ、階段の吹き抜け、エスカレータ、梯子或いは別のフロア又はエリアへ人を移動させる他の特徴部に対応することができる。複数の接続ポイント４０５は、それぞれの個々のエレベータ又は特徴部に対応することができる。一実施形態において、接続ポイント４０５は、画像２０１からのエリア又は地点と、建物の別のフロア（例えば、２階、第３階又はｎ階）を表す別の地図又は平面図のような、別の地図又は平面図上の別の点又はエリアまでの間でルーティングするのに使用される。或いは、接続ポイント４０５は、同じフロア又は地上エリア上である地点から別の地点に人を移動又は搬送させる接続部を表すことができる。例えば、接続ポイント４０５は、動く歩道又は他の輸送デバイスに対応することができる。また、接続ポイント４０５は、同じレベル又はエリアに関連付けられた別のルーティング可能な公開エリア地図への接続部を表すことができる。例えば、１つの公開エリア地図においては、ルートは、フードコートのような基準エリアを表す空白の、指定されていない、又は一般多角形又は形状により表されるエリアに対して生成することができる。接続ポイントは、一般多角形にて、一般多角形により、又は一般多角形上で配置することができ、該一般多角形は、接続ポイントが元の基準エリア（例えば、フードコート）内の詳細な特徴部及び／又は基準領域を有する別のルーティング可能な公開エリア地図に対応するか、又はナビゲーションする基準エリアを表す。一般的な又は親の公開エリア地図（フードコート基準エリア）を表示することができ、次いで、特定の又は子の公開エリア地図（フードコート内の基準領域又は基準エリア）にルーティングするか、又はこれを選択したときに、子の公開エリア地図は、別個のウィンドウ又は異なる画面内などに表示することができる。
【００３６】
図５は、画像２０１に対応する基準領域５００を示す図である。グリッド３００とは別個の空間層において、基準領域５００が生成される。例えば、画像２０１内の画像基準オブジェクト２１７、２２１、２２５、２２９、２３３、２３７、２４１及び２４５は、ラスタ画像又は画素化画像の一部である。ラスタ画像は２値化することができる（例えば、画素を白画素及び黒画素、及び／又は１及び０に変換）。デバイス１１２は、画像基準オブジェクトと関連した名前又は説明を抽出する。この分離は、ラスタ画像２０１と関連した名前又は説明に対応するテキスト５０４を生成するための光学式文字認識（「ＯＣＲ」）を容易にすることができる。テキスト５０４は、公開エリア地図の異なるエリアを検索又は関連付けるのに使用される。テキスト５０４は、画像２０１の名前又は説明に一致させることができる。或いは、付加的な又は異なるテキスト又は情報を追加することができる。例えば、テキスト「Ａ」、「Ｂ」、「Ｃ」、「Ｄ」、「Ｅ」、「Ｆ」、及び「Ｇ」は、区別するために「事務所」テキストに追加される。追加されたテキストは、エンドユーザに可視又は不可視とすることができる。
【００３７】
グラフィックスとテキストの分離後、画像基準オブジェクトは、ベクトル化を経て、多角形、基準領域又はエリア５００を形成する。基準領域５００は、画像２０１内の異なるエリア、部屋又はスペースに対応する。基準領域５００は、異なる空間層上のグリッド３００によって表されるそれぞれのナビゲート可能タイル３０４及びそれぞれのナビゲート不可能タイル４０１に関連付けられ、又はこれらに対応する。
【００３８】
グリッド又はメッシュ層は、基準領域層、接続層、及び／又は、コスト層又は制約層など他の空間層又はデータ層と共にコンパイルして、ナビゲーション及び／又はルーティングに使用できる公開エリア地図を形成又は生成することができる。
【００３９】
図６は、図１のシステム１００により生成された公開エリア地図６０１の一実施形態を示す。公開エリア地図６０１は、ユーザデバイス１１６のディスプレイ１４０又は他のディスプレイ上に表示することができる。公開エリア地図６０１は、画像２０１の基準画像オブジェクトのグラフィック表現を含む。例えば、画像２０１は、公開エリア地図６０１の背景又はベース画像として使用される。或いは、異なるグラフィックス又は画像が、画像２０１の元のレイアウトを表すのに生成される（例えば、基準領域５００の生成に基づいて）。ナビゲート可能なタイル３０４又ナビゲート不可能なタイル４０１を含むか又はこれらが欠如したグリッド３００は、基準領域５００及び接続ポイント４０５と共にコンパイルされて、ルーティング及びナビゲーションを目的とした公開エリア地図６０１の基礎をなす。例えば、グリッド３００又はコンパイルされたグリッドは、ユーザが見ることはできない。或いは、グリッド３００及び／又は特徴部は、ユーザに晒される場合もある。
【００４０】
図７は、図１のシステム１００により生成された公開エリア地図７００の一実施形態を示す。公開エリア地図７００は、公開エリア地図６０１により表されたフロアを含む建物の別のフロアを表す。公開エリア地図７００は、休憩室、会議室、エレベータ又はエレベータ列、事務所、及び体育館などの、画像基準オブジェクト、並びに、関連する基準領域、グリッド、接続ポイント７０８、及び上述の公開エリア地図６０１のそれぞれの特徴部に類似したナビゲート可能タイル及びナビゲート不可能タイルを含む。
【００４１】
一実施形態においては、ユーザは、公開エリア地図６０１及び７００を使用して、あるフロアの事務所から建物の別のフロアまでルーティングすることを望む場合がある。図６を参照すると、ユーザは、テキストサーチを使用して事務所を検索し、原点６０９を指定する。特定の事務所のテキストは、それぞれの基準領域５００と関連付けられ、該基準領域５００は、それぞれのタイル３０４及び４０１と関連付けられる。或いは、ユーザは、ディスプレイ上で原点６０９に物理的にタッチ又は選択する。或いは、原点は、全地球測位衛星（「ＧＰＳ」）システム又はデバイス、屋内位置測定システム（例えば、ＷｉＦｉベース）、又は原点の位置が固定される（例えば、キオスク又は壁部上の平面図デバイス）ことに基づいて求められる。原点６０９は、事務所の基準領域又は基準画像オブジェクト内の、又はこれらに関連付けられた１つ又はそれ以上のタイルに対応することができ、又はエリア全体に対応することができる。図７を参照すると、ユーザは次に、テキストサーチを用いて体育館について検索し、目的地点７１２を指定する。体育館のテキストは、それぞれのタイルに関連付けられた、体育館のそれぞれの基準領域と関連付けられる。或いは、ユーザは、ディスプレイ上で目的地点７１２に物理的にタッチ又はこれを選択する。ユーザは、公開エリア地図７００に切り替えることができ、又は、同じ画面又はウィンドウ上で両方の公開エリア地図６０１及び７００を表示することができる。
【００４２】
原点６０９及び目的地点７１２が選択された後、様々なルートが、基礎となるコンパイルグリッドに基づいて計算及び／又は比較される。ルートは、ダイクストラ法、Ａスターアルゴリズム又は検索、及び／又は他のルート探索又は計算アルゴリズムに基づいて計算することができる。距離、ナビゲート不可能なエリア、コスト及び／又は制約事項など様々な態様が、最適ルートを求めるために検討される。経路６０５（図６）は、計算結果に基づいて生成される。経路６０５は、ユーザが見て追従するために表示される。経路６０５は、事務所内の原点６０９から始まり、会議室を通り、接続部４０５などの接続部６１３を経由してエレベータを使用する経路を示す。その後、公開エリア地図７００は、接続ポイント７０８にてエレベータから始まり、目的地点７１２の体育館に至る経路７０４（図７）を示す。
【００４３】
ルート及び／又は経路６０５及び７０４の計算及び決定は、隣接タイル、連続タイル、又は接続タイルに基づき、又はこれらから形成される。例えば、互いに境界で接するか又は接触するナビゲート可能なタイルは、ポイントツーポイントルーティングに対して考慮され、レイアウト内の任意のエリア又は隣接タイルに関連する任意の地点が、グリッド又はメッシュ（すなわち、単に所定のルートだけでない）に関する計算結果に基づいてルーティングすることができる。ルートを形成する隣接タイルは、中心点又は他の部分により接続又はリンク付けすることができる。
【００４４】
図８は、公開エリア地図６０１又は７００などの公開エリア地図を生成する方法のフローチャートである。より少ないか又はより多いステップ又は段階を設けることができ、ステップの組み合わせも設けることができる。また、ステップ又は段階は、図示するような順番で、又は異なる順番で実行することができる。本方法は、本明細書で説明するシステム及び／又はデバイス、或いは異なるデバイス又はシステムによって実施される。
【００４５】
一実施形態においては、画像２０１のようなグラフィック表現又はレイアウト画像を取得又は受信する（ステップ８０１）。例えば、ワークステーション、コンピュータ、又はデバイス１１２など他のデバイスを使用する地図開発者は、ネットワーク１０８のようなインターネット又は他のネットワークもしくは接続部を介して、建物平面図などのレイアウトの既存画像をダウンロード又はリクエストする。画像のグラフィック表現は、ウェブサイト、サーバ、ファイル、別のコンピュータ又は他のデバイス、或いは画像ソース１０４などの任意の他の記憶装置又はエリアに格納又は位置付けることができる。レイアウトの画像は、無線により及び／又は有線接続を介して受信することができる。受信した画像は修正することができる。例えば、地図開発者が画像特徴部を追加又は除去することができるように、消去又は描画ツール或いは機能を設けることができる。場合によっては、ドア又は開口部は、ルーティングを目的として追加する必要がある可能性がある。
【００４６】
レイアウトの画像、レイアウトの画像のコピー、又はレイアウトの修正画像の上又はこれらを覆って、グリッド又はアレイ３００のようなグリッド、メッシュ又はアレイを適用又は重ね合わせる（ステップ８０５）。地図開発者は、レイアウト内の距離測定値を指定することにより、スケールを割り当てる。例えば、マウス、又は入力デバイス１３６のような他の入力デバイスを使用して、地図開発者は、廊下又はエリアの幅又は長さを表す、基準オブジェクト２１７、２２１、２２５、２２９、２３３、２３７、２４１及び２４５などの画像オブジェクト間の空間又は距離を選択する。次いで、地図開発者は、１メートル又は３メートルなどの値をその空間又は距離に割り当てる。或いは、距離測定値の指定には、「ポップアップ」画面又は記入式ボックスを介して入力することができ、又は、距離測定値は、画像内の既存距離マーカー又は所定のパラメータに基づいて自動的に実施することができる。スケールを割り当てることにより、レイアウト内のオブジェクトとエリアとの間の距離の認識が得られる。
【００４７】
次いで、グリッド又はメッシュをレイアウトの画像上に適用するか、又はスケールを割り当てる前にグリッド又はメッシュを適用する。例えば、レイアウトの実質的に画像全体を覆うグリッドを設ける。或いは、グリッドを適用するためのある部分又は特定の部分を選択する。一実施形態において、グリッドは、廊下或いは他の地上又は公開領域など、基準オブジェクト間での歩行に指定されたエリアにだけ適用することができる。従って、グリッド又はメッシュは、画像内の境界、障壁及び／又は壁部と交差しない。また、グリッド又はメッシュは、室内のエリアのような内部エリア又は画像基準オブジェクト上に適用することができる。地図開発者は、グリッド、グリッドの一部又は入力デバイスによって結合することができる複数のグリッドをどこで適用するかを選ぶことができる。例えば、地図開発者は、レイアウト内の廊下エリアをクリック又は選択して、廊下エリア全体にグリッドを適用することができる。代替の実施形態においては、グリッド又はその一部は、色／画像認識又は他のパラメータに基づいて、レイアウト又はレイアウトの一部の実質的に画像全体にわたって自動的に重ね合わされる。
【００４８】
グリッド、メッシュ又はアレイは、上述のように、タイル３０４、又は類似の或いは対応する点又は先端など、タイル、ブロック、断面又はエリアから構成されている。スケーリングに基づいて、タイルは、測定値に割り当てられ又はこれに対応する。例えば、各タイルは、約１平方メートル、１／４平方メートル又は他の値の測定値を有することができる。或いは、各タイルは、任意の他の測定値、又は、互いに異なる値を有することができる。タイル又は地点の解像度又は数は、地図開発者により又は自動的に調整することができる。例えば、解像度がより微細になると、グリッド又はメッシュは、より多くのタイル又は地点を含むように調整又は変更することができ、解像度が低くなると、グリッド又はメッシュは、より少ないタイル又は点を含むように調整することができる。タイル又は地点の数の調整は、レイアウト及び／又は他の要素内の画像基準オブジェクトの数又は位置決めに基づくことができる。例えば、タイルのサイズは、少なくとも１つのナビゲート可能なタイルが現実世界の環境内の狭い又は最も狭い通路に適することができるように、人間又は歩行者のスケールに適合するように選択することができる。ルーティングのためにナビゲート可能なタイルを最も狭い又は最も小さいエリア、ホール、又は通路に置くことができるように、最大タイルサイズ（例えば、長さ及び／又は幅又は他の長さ、幅、寸法値及び／又は面積値において、最大でも約１５インチ、２０インチ又は３０インチ）を選び又は予め設定することができる。適切なタイル又はエリアサイズを選んで、レイアウトの一部の公的なエリア内でのルーティングの欠如又は不能を回避する。また、サイズが均一ではないタイル及び／又は形状を異なるエリアに使用することができる。例えば、より大きいエリアでは、より大きいサイズのタイルを使用することができ、より小さい又は狭いエリアでは、より細かい又はより小さいサイズのタイルを使用することができる。
【００４９】
局所的又は大域的地図座標が割り当てられ、又は指定される。例えば、タイルの中央部又はタイルの他の部分（又はアレイもしくはグリッドの先端又は点）には、（ｘ，ｙ）の緯度及び経度、或いは他の座標表示が与えられる。起点は、タイルの１つ（例えば、コーナタイル）に（０，０）すなわち原点を割り当てることによって選択される。座標は、基準画像オブジェクト、基準領域、又は他の特徴部を検索又は識別するのに使用することができ、又はその逆も同様である。しかしながら、ポイントツーポイントルーティングは、隣接タイル又は連続タイルに基づくことができ、従って、座標は、ルーティング計算には不必要な場合がある。或いは、座標は、ルートを計算するときに距離及びコスト決定に使用することができる。
【００５０】
地図６０１又は７００などのルーティング可能な地図をグリッド又はメッシュの関数に基づいて又はこれらの関数として生成又は作成する（ステップ８０９）。図９は、ステップ８０９により全体的又は部分的に包含することができるステップを含むルーティング可能な地図を生成する方法の実施例を示すフローチャートである。ナビゲート不可能なエリアをグリッド又はメッシュで指定する（ステップ９００）。例えば、地図開発者は、画像のレイアウト内のエリアをクリック又は選択して、ナビゲート不可能なタイル又はエリア４０１などナビゲート不可能なタイル又はエリアに変換する。地図開発者は、ナビゲート不可能なエリアとして現実世界では歩行で通り抜けることができない壁部又は障壁の画像を選択することができる。この選択により、ナビゲート不可能なステータスでタイルを割り当てることができ、又は、タイルを除去することができる。ナビゲート不可能なエリアの指定も自動化することができる。例えば、ナビゲート不可能である画像内の複数のエリアを選択するのではなく、地図開発者は、ナビゲート不可能である壁部又は障壁をクリック又は選択することができ、選択した壁部又は障壁の同じ又は類似した色又は画素レベルを有する全ての他の特徴部又は画像オブジェクトをナビゲート不可能なエリア又はタイルと自動的に関連付けることができる。或いは、グリッドが地図開発者又は他のエンティティの介入なしに重ね合わされると、所定の色又は画素レベル或いは画像認識要素を入力し、ナビゲート不可能なタイル又はエリアが自動的に生成されるようにすることができる。このように自動化された場合、レイアウト内でのテキストのグラフィック表現又は画像オブジェクトの記述は、ナビゲート不可能なエリアの指定前に除去又は分離することができる。これは、記述がナビゲート不可能なエリアとして誤って割り当てられ可能性があることに起因する。或いは、ナビゲート不可能なエリアは、ナビゲート不可能であることを意図したエリアにグリッド又はその一部を当初は適用しないことによって指定することができる。
【００５１】
複数の基準領域又はエリアを生成する（ステップ９０４）。基準領域の生成は、グリッド又はメッシュとは異なる空間層上で行われる。グリッド又はメッシュは、複数の基準領域を作成するときに表示することができ、又は表示されなくてもよい。一実施形態においては、複数の基準領域は、自動的又は半自動式に生成される。例えば、ラスタ画像又はベクタグラフィックス画像とすることができる画像２０１のような画像内で複数の基準画像オブジェクトが識別され又は求められる。レイアウトのラスタ画像は２値化される。画像の２値化は、複数の数字１及び０を用いてレイアウトを論理的に理解できるようにする。例えば、Ｔｉｅｒ-Ｔａｘｔ２値化が用いられる。Ｔｉｅｒ-Ｔａｘｔ２値化は、エッジ保存を可能にする。或いは、他の２値化技法又は方法を用いることができる。２値化は、シグマ、アクティビティ閾値及び刈り込み要素など、３つのパラメータ又は要素に依存することができる。或いは、より多くの又はより少ない要素を考慮することができる。
【００５２】
シグマは、雑音感度に対応することができる小さいシグマよりもむしろ大きいシグマである。画素でのアクティビティは、勾配の大きさの局所的平均値に比例することができ、アクティビティ閾値よりも低いアクティビティを有する画素は、ゼロに設定することができる。刈り込み要素は、接続された小さな構成要素を除去するのに使用される。一実施形態においては、シグマは約１に設定され、アクティビティ閾値は約２に設定され、刈り込み要素は約１に設定される。或いは、要素の値は、任意の他の値に設定することができ、調整可能とすることができる。
【００５３】
基準画像オブジェクトの識別に関して、テキスト／グラフィックス分離を２値化後に行う。例えば、基準画像オブジェクトの各々に対応するグラフィックス記述又はテキストは、それぞれの画像オブジェクトから分離される。任意の将来又は過去のグラフィック−テキスト分離を用いることができる。分離されたテキストは、それぞれの画像オブジェクトにリンクされ、又はこれにより識別される。例えば、テキスト領域は、基準画像オブジェクトの各々において指定することができる。分離後、グラフィックス記述の全て又は一部に対してＯＣＲを実施し、これらをテキスト５０４のような検索可能なテキストに、又は、テキストのグラフィック表現ではなく意味又は定義を有するものとして認識することができるテキストに変換する。グラフィックス記述の分離により、ＯＣＲを容易又は改善させることができる。或いは、ＯＣＲは分離なしで行うことができる。ＯＣＲを適用する前にＬａｎｃｚｏｓ再サンプリングを用いることによるなど、レイアウトの元の画像の解像度を２倍に又は増大させることによって、テキストエイリアシングを低減することができる。代替実施形態においては、他のテキスト認識方法、機能又はアルゴリズムを用いることができる。
【００５４】
基準領域５００のような複数の基準領域は、それぞれの基準画像オブジェクトに対応する境界又は境界線を形成することにより生成される。例えば、２値化及び／又はグラフィックス記述の分離後、基準画像オブジェクトがベクトル化される。線又はベクトルがデジタル又は２値化データ点間に生成又は作成され、レイアウト内の画像オブジェクトに対応する形状を形成する。例えば、Ｒｏｓｉｎ＆Ｗｅｓｔベクトル化アルゴリズムを用いる。或いは、他の将来又は過去のベクトル化アルゴリズムを用いてもよい。
【００５５】
閉じた多角形が、元の基準画像オブジェクトに関連した基準領域を求めるために識別される。例えば、ベクトル化に基づいて、閉じた多角形又は他の形状が求められる。閉じた多角形は、平面曲線、頂点、エッジ及び／又は面技法を介して求めることができる。任意の将来又は過去のコンピュータ幾何学アルゴリズム又は方法を用いることができる。閉じた多角形は、事務所、部屋又は他のエリアに対応することができる。
【００５６】
一部の基準画像オブジェクトは、ギャップ又はシンボル２４９及び２５３など、ドアのギャップ又はシンボルを含むことができる。基準領域を求める目的で、ベクトル化で識別された全ての線分について呼び出して、閉じた多角形を形成するために閉鎖することができるギャップを特定又は識別することができる。ギャップを閉鎖して、それぞれの基準領域を識別する。ドアのシンボルに関しては、地図開発者は、シンボル２５３のような固有のシンボルをドア、開口部、入口及び／又は出口にリンク付けする情報を識別又は提供することができる。この関連付けは、メモリ又はルックアップテーブル内に格納することができる。ベクトル化の間又はその後で、ドアのシンボルがマッチングに基づいて識別され、ギャップと置き換えることができる。次いで、ギャップを閉鎖してそれぞれの基準領域を識別する。或いは、線又はベクトルは、ギャップを形成した後にギャップを閉鎖するのではなく、ドアのシンボルと置き換わって多角形を閉鎖する。所与の画像オブジェクトに対する複数のドアのギャップ又はシンボルを呼び出し又は閉鎖して、閉じた多角形を形成し、基準領域を求めるようにすることができる。ドアのギャップ又はシンボルは、基準画像オブジェクトに対して別個の空間層にあるグリッド上のナビゲート可能なタイルに対応する。ドア又は開口部は、グリッドのナビゲート可能なタイルをそれぞれの基準領域と比較することによって推測することができる。
【００５７】
基準画像オブジェクトの各々に関連付けられた名前又はテキストは、生成された基準領域に対応する名前属性で実装される。例えば、ＯＣＲから生成されたテキストは、生成された基準領域のテキスト領域に関連付けられる。ルックアップテーブル、データベース、又は他のメモリ特徴部は、テキスト記述を各それぞれの基準領域にリンク付ける。地図開発者が生成されたテスト又は基準領域とのテキストの関連付けにおけるエラーを補正することができるように、質疑応答機構又は確認機能を実施することができる。基準領域は、関連テキストに基づいて検索可能とすることができ、その逆もまた可能である。
【００５８】
基準領域はまた、基準タイプと関連付けることもできる。例えば、各基準領域は、基準領域の関連するテキスト、関数、目的及び／又は他の要素に基づいて、レストラン、事務所、デパート、食料品店、浴室又は他の表示のようなタイプに対応し、又はこのようなタイプを指定することができる。これらのタイプ又はキーワードは、データベース又はルックアップテーブル内に格納することができ、それぞれの基準領域とリンク付け又は関連付けることができる。タイプ又はタグは、生成されたテキスト又は名前とは異なる場合もあれば、同じである場合もある店又はエリアの特定の名前（例えば、ＭｃＤｏｎａｌｄ（商標）レストラン）のような、より特定のものとすることができる。また、ロゴ及び／又はそれぞれのウェブサイトは、基準領域と関連付けることができる。基準領域は、１つ又はそれ以上のタイプ又はタグと関連付けることができ、タイプ又はタグに基づいて検索可能にすることができる。
【００５９】
基準領域及び関連するテキスト及びタイプは、自動的に生成される代わりに、或いはこれに加えて手作業で生成することができる。例えば、地図開発者は、プログラム又はアプリケーションツールを用いて、レイアウトの元の画像において基準画像オブジェクトのアウトラインを描き又はこれを複製し、グリッド又はメッシュと別個の空間層において基準領域（基準領域５００など）を生成することができる。また、地図開発者は、基準画像オブジェクトの元の記述を読むか又は表示し、更に、テキスト５０４などの等価テキスト及び／又は生成された基準領域と関連付けられるタイプに記入、入力、又は打ち込むことができる。
【００６０】
グリッド又はアレイ及び基準領域のようなデジタル公開エリア地図に関連付けられる生成されたデータ又はデータ層は、データベース１７０などに格納される。別個のデータ又は空間層は、個々のＸＭＬファイル又は他のデータとして格納することができる。例えば、基礎となる画像、グリッド及び基準領域に対応するデータが保存又は格納される。位置又は場所情報、或いはグリッド又はそれぞれのタイルに対応するデータ（規則的な大きさのタイルなど）、並びに基準領域もまた、データ構造内に保存及び／又は提供される。位置情報は、異なるデータエンティティの適切な場所に関する空間的基準として使用される。位置情報は、基礎となる画像に対してなど、元のスケール、基準又は座標に基づくことができる。データベース１７０は、別個のデータ層をコンパイルして、ルーティング可能な公開エリア地図を形成することができる。従って、データベース１７０は、コンパイルされた公開エリア地図データをエンドユーザデバイスにストリーミング又は送信することができる。或いは、別個のデータ層は、エンドユーザデバイス上のコンパイルのためにエンドユーザデバイスに送信することができる。また、コンパイルされた公開領域マップファイル又はデータは、別個のデータ層を格納するのではなく、データベース１７０内に格納することができる。
【００６１】
異なる空間又はデータ層をコンパイル又は組み合わせて、ルーティング可能な公開エリア地図６０１又は７００などの公開エリア地図を形成する（ステップ９０８）。例えば、関連テキスト及びタグを含む複数の基準領域は、グリッド又はメッシュと共にコンパイルされる。コンパイルすることにより、検索、ナビゲーション、ルーティング及び他の目的のために、それぞれのタイルが生成された基準領域にリンク付けされ、又はこれと関連付けられる（基準領域内にあるべきタイル、基準領域に実質的に隣接しているタイル、及び／又は基準領域の境界に接触又は交差しているタイルなど）。また、別個の空間層上で生成することができる接続部又は接続ポイントは、グリッド及び複数の基準領域と共にコンパイルすることができる。別個の又は異なる空間層上にあるとすることができる、制約事項又はコスト特徴部などの他の構成要素又は特徴はまた、グリッド又はメッシュと共にコンパイルすることもできる。任意の将来又は過去のコンパイル技法又は方法を用いることができる。また、異なる空間層をランタイム中に組み合わせることができる。或いは、グリッド、基準領域及び／又は接続ポイント、並びに他の特徴は、生成されて、異なる層ではなく同じ空間層又はデータ層上に存在することができる。従って、最終コンパイルを必要としないことがある。また、一部の空間層は、コンパイルすることができず。又は使用することができない。例えば、ルーティングは、生成された基準領域とタイルを関連付けることなく、ナビゲート可能なタイル及びナビゲート不可能なタイルを使用して達成することができる。
【００６２】
再度図８を参照し、画像２０１に類似した画像など、レイアウトの別の又は第２のグラフィック表現又は画像を取得する（ステップ８１３）。例えば、第２の画像は、建物の別のフロアの平面図画像とすることができる（例えば、ステップ８０１にて取得した画像は、建物のあるフロアを表し、ステップ８１３で取得した画像は、建物の別のフロアを表す）。第２の画像は、ステップ８０１で第１の画像を取得したのと同様の方法で、地図開発者が取得又は受け取ることができる。
【００６３】
別のグリッド、メッシュ又はアレイが、ステップ８０５でグリッドを適用するような、第２の画像に適用される（ステップ８１７）。別の又は第２のルーティング可能な地図は、ステップ８０９にて第１のルーティング可能な地図を生成するような、第２のグリッドに基づいて又はその関数として生成される（ステップ８２１）。１つ又はそれ以上の接続部又は他の特徴部を介してなど、第１及び第２のルーティング可能な地図は、互いにリンク付けされ又は関連付けられる（ステップ８２５）。例えば、第１のルーティング可能な地図における接続ポイントは、ルーティングを目的として第２のルーティング可能な地図上の接続ポイントと関連付けられる。接続ポイントは、接続ポイント６１３及び７０８のようなエレベータ接続部に対応し、或いは建物の２つのフロア又は他のエリアをリンク付けする他の接続部に対応することができる。或いは、１つ又は同じ接続ポイントを使用して２つのルーティング可能な地図をリンク付けする。１つ又はそれ以上の接続ポイント又は他の特徴部を介して、任意の数のルーティング可能な地図を共にリンク付けすることができる（例えば、建物の異なるフロア又は他のエリアに対応する１から第ｎ番目の数のルーティング可能な地図を生成し、共にリンク付け又は関連付けることができる）。
【００６４】
図１０は、公開エリア地図６０１又は７００などの公開エリア地図内でのルーティング方法のフローチャートである。より少ないか又はより多いステップ又は段階を設けることができ、ステップの組み合わせを設けることもできる。また、ステップ又は段階は、図示の順番で又は異なる順番で実行することができる。本方法は、本明細書で説明するシステム及び／又はデバイス、或いは異なるデバイス又はシステムによって実施される。
【００６５】
一実施形態においては、歩行者などのエンドユーザは、公開領域におけるポイントツーポイントルーティング又はナビゲーションのためにデバイス１１６のようなデバイスを使用する。例えば、公開エリア地図６０１又は７００などの１つ又はそれ以上のルーティング可能な公開エリア地図又はそのデータは、接続部１２０又は他の接続部などを介して、ユーザデバイスにダウンロード又は送信される。或いは、１つ又はそれ以上のルーティング可能な公開エリア地図又はそのデータは、場所又は位置に基づいて近接ビーコン又は送信器もしくは他のデバイスを介してユーザデバイス上に「プッシュされる」。
【００６６】
ユーザは、ディスプレイ１４０などを介して１つ又はそれ以上の公開エリア地図を見る。起点又は原点６０９のような原点を選択する（ステップ１００１）。例えば、ユーザは、ルーティングの開始場所としての役割を果たすエリア又は起始点を記入又は入力する。ユーザは、基準領域を記述する名前又はテキストを入力することができ、公開エリア地図におけるそれぞれのエリアは、或いは基準領域を名前又はテキストとリンク付けするルックアップテーブルへのサーチ又はアクセスに基づいて原点として配分することができる。或いは、ユーザは、公開エリア地図上のエリアをクリック、又は選択、或いは物理的に接触して（すなわち、表示画面に接触して）原点を選ぶことができる。
【００６７】
公開エリア地図で選択された起点を識別する（ステップ１００５）。例えば、原点と関連付けられた１つ又はそれ以上のタイル、又は原点と関連付けられた基準領域が、ルート計算のために特定、検討、認識、ターゲット化、重点化、及び／又は強調表示される。
【００６８】
目的地又は目的地点７１２などの目的地点（すなわち、ユーザがルーティングを望む場所又はエリア）が、原点選択と同様の方法又は異なる方法でユーザにより選択される（ステップ１００９）。公開エリア地図において選択された目的地が、原点を識別するのと同様の方法で又は異なる方法で識別される（ステップ１０１３）。
【００６９】
公開エリア地図内において選択された起点から選択された目的地までのルートを計算する（ステップ１０１７）。例えば、タイル３０４のようなナビゲート可能な隣接又は接続タイルにアクセスし、原点から目的地点までの最適又は好適なルートを求める。タイル４０１などのナビゲート不可能なエリア又はタイルは回避又は迂回される。幾何学的及び／又は数学的関数又はアルゴリズムを用いて１つ又はそれ以上の可能なルートを計算することができる。例えば、タイルの各々の中心部又は他の場所を互いに接続又は関連付けて、可能性のあるルートを形成する。距離に基づいて、並びにコスト、制約事項、又は入力することができるユーザ優先度のような他の要素に基づいて最適ルートが選択される（例えば、ユーザは、所望のエリアを回避又は通過するルートを望むことができる）。ユーザ優先度は、タイルの分類又は下位分類に基づくことができる。例えば、各タイル又は一部のタイルは、エリアの位置、場所及び／又はタイプに関係する特徴部（例えば、主要な、中間の、又は小さい通路、廊下、経路又はエリア、交通量の多い又は少ないエリア、人気のないエリア又は人気のあるエリア、風致地区、狭いエリア、孤立したエリア、傾斜エリア、平坦エリア、絨毯敷エリア、或いはエリアのサイズ、長さ又は幅）と関連付けられる。タイルはまた、どの基準領域又は基準エリアがリンク付けされ、近接し、又は通過するかに基づいて下位分類することができる。下位分類に基づいて異なるタイルをランク付けし、又は整序することができる。一実施形態においては、ユーザは、ルーティング時に交通量の多いエリア又は主要な通路を回避するように入力又は選択することができる。
【００７０】
ダイクストラ法、Ａスターアルゴリズム又は検索、及び／又は他のルート探索又は計算アルゴリズムを用いて、接続タイルの地点間で線、曲線又はルートを形成することができる。Ｄｏｕｇｌａｓ−Ｐｅｕｃｋｅｒ法又はアルゴリズムを用いて、計算された線又はルートを平滑化又は簡素化することができる。例えば、隣接タイルの中央部を共に接続することにより、ジャギー、先鋭、又は三角形のエッジを原点から目的地点までのルート内で形成することができる。距離を最小限に抑えてルートの平滑な線又は曲線を提供するために、Ｄｏｕｇｌａｓ−Ｐｅｕｃｋｅｒアルゴリズムは、原点から目的地までの平均化ルートを発見又は提供することができる。Ｄｏｕｇｌａｓ−Ｐｅｕｃｋｅｒアルゴリズムは、ナビゲート不可能なタイルを回避するように修正され、線平滑化又は平均化のため閾値レベルを変更するように調整することができる。或いは、他の線平滑化アルゴリズム又は方法を用いることができる。
【００７１】
算出ルート及び生成経路は、将来の使用に備えて保存又は格納することができる。例えば、経路が生成されると、この経路は所定の経路として保存することができ、ユーザが同じ原点から同じ目的地までルーティングすることを望む場合に再利用することができる。全てではなく一部の経路又はルートを保存することができる。例えば、主要又は人気のある基準領域間のルート又は経路を格納することができ、他方、通行量が少ない又は小さい基準領域に関する経路は保存することができない。また、経路全体ではなく、経路の一部が保存される部分的なルート又は経路を格納することができる。加えて、接続部又は接続ポイント間のルート又は経路は、ルーティングのために予め計算し、又は予め設定し且つ格納することができる。例えば、ユーザは、ある地点から１つ又はそれ以上の接続部を使用することができる別の地点までルーティングすることを望む場合がある。この場合、ルートは、原点から接続部まで並びに他の接続部から目的地まで計算され、接続部間のルートは既に計算済みであり、これによって時間及び処理が節約される。ルートは、複数のデータ層に格納、保存、ランク付け、又は整序することができる。例えば、上位層は、主要な、大きな、又はより重要なルートを含むことができる。或いは、ルート及び経路は、常に再計算及び再生成される。
【００７２】
ルートの計算に基づいて、選択された原点から選択された目的地までの経路を生成する（ステップ１０２１）。１つ又はそれ以上のルートの計算及び選択の間又はその後で、最適又は好適なルートに関連したタイルの全てが経路として識別又は求められる。例えば、Ｄｏｕｇｌａｓ−Ｐｅｕｃｋｅｒアルゴリズム又は他のアルゴリズムは、特定のナビゲート可能なタイルを通り過ぎる線及び／又は曲線を形成することができる。次いで、これらのタイルは、ユーザが原点から目的地点まで辿り着く経路として識別、入力、格納、又は強調表示される。その後、求められた経路は、ルーティングを目的として、表示された経路６０５又は７０４のように公開エリア地図においてユーザに表示される。
【００７３】
一実施形態においては、ユーザは、ルーティング及び／又はナビゲーション用に公開エリア地図を使用するときに区分データを受信することができる。デバイス１１６などのユーザデバイスは、処理速度、メモリ又は他の特徴が他のデバイス程高く、高速で、又は大きくない場合があるリソース制約構成部品を含むことができる。従って、同時に複数の公開エリア地図に関連した全データをダウンロード又は実行するのではなく、必要に応じてデータを受信又は実行することができる。例えば、ユーザは、ナビゲーションを開始するときに、１つの公開エリア地図又はその一部をダウンロード又は開始することができる（例えば、ルーティングのために１階又は原点を含む１階の一部が、表示又は取り込まれる）。次いで、ユーザが接続部又は接続ポイントを入力し、又はルーティングされると（例えば、２階又は他のフロア又はエリアに行くために）、次いで、接続された公開エリア地図データがルーティングプロセスを続行するためにダウンロード又は開始される。また、公開エリア地図の異なる空間層又は特徴部は、区分化状態で又は異なる時間にダウンロード又は実行することができる。
【００７４】
上述の公開エリア地図は、車載ナビゲーションシステム、携帯型ナビゲーションデバイス、現実世界の車両ナビゲーション地図、及び／又は現実世界の歩行者ナビゲーション地図で使用されるような収集されて地理的データベースに編成される、ナビゲーション関係の属性又はノード及び道路又は経路セグメントを含むことができ、又は含まれない場合もある。ナビゲーション属性としては、転回制約コンテンツ、速度制限情報、最適又は一般的経路データ、歩道コンテンツ、標識情報、及び／又は、ルート計算、目的地時間計算、ルート案内及び／又は他の現実世界のナビゲーション機能などナビゲーション関係機能を実行するための他の属性を挙げることができる。
【００７５】
公開エリア地図は、収集されて編成されたナビゲーション属性及び／又はノード及びリンク又は道路／経路セグメントをベースとする又はこれらを含む現実世界の車両及び／又は歩行者地図又は地図データと接続され、又は通信することができる。例えば、建物のフロア、建物の公開エリア地図、又は他の公開エリア地図は、ルーティング及びナビゲーションを目的として道路網地図に接続することができる。ユーザは、建物フロア内でルーティングするデバイスを使用して、ユーザをエリア２０５（図２）のような外側エリアにナビゲートすることができる。ユーザが外側エリアに達すると、ユーザは、設定された道路網を使用して市街又は他の場所の別の部分にナビゲートすることを望むことができる。ユーザのデバイス又はユーザのデバイスと通信することができるデバイスは、道路網に関してナビゲート関係機能を実行する車両ナビゲート地図を実行、呼び出し、又は表示することができる。収集された属性に基づいた公開エリア地図及びナビゲーション地図又はデータのあらゆる組み合わせは、ルーティング及び／又はナビゲーションを目的として互いに接続することができる。
【００７６】
（代替形態）
上記の説明においては、ルーティングに使用される公開エリア地図は、建物フロア又は平面図を中心とするものである。しかしながら、記載の特徴は、多数の公開領域に使用することができる。例えば、公園及び屋外環境のレイアウトの画像を取得して、上述のように、ルーティング可能な地図を生成するのに使用することができる。ピクニック場、ジャングルジム、滑り台、トイレ及び他のエリアのような公園の異なるセクションは、別個の基準領域として定義することができる。従って、ルーティングは、上述の事務所間のルーティングと同様に、草で覆われたエリア全体に生成することができる。公園は、ルーティングに組み込むことができる散歩道を有する場合がある。或いは、所定の散歩道又はルートは、ルーティングにおいて回避することができる。また、ナビゲート不可能なタイルは、境界又は障壁用に使用又は実装することができる。例えば、公園内の湖、池又は他の水域は、水中を通ってルーティングされないように、ナビゲート不可能なタイルで境界付けることができる。危険エリア、列車軌道又は岩などの他の障壁又は所望の境界線をナビゲート不可能なタイルと関連付けることができる。或いは、ナビゲート可能なタイルは、これらの境界線の一部を通過する理由がある場合に使用することができる。例えば、湖の一方の側から反対の側に人を連れて行くためにボートが存在する場合、ボートエリアは、ナビゲート可能なタイルと関連付けることができる。
【００７７】
公園又は外側エリアの画像に関連したタイル又はオブジェクトは下位分類することができる。例えば、一部のタイルは、草エリアと関連付けることができ、一部のタイルは、歩道と関連付けることができる。ユーザ又は他のエンティティは、ルーティングを目的として草のみ、歩道のみ又は他の指定などの優先度を入力することができる。従って、特定の指定されたタイルタイプを回避又は使用する（例えば、草エリアのみにわたるルートを生成して歩道を回避する、又はその逆）ことによりルートを生成することができる。
【００７８】
別の実施形態においては、駐車場の既存画像を取得して、ルーティング可能な公開エリア地図を生成するのに使用することができる。個々の駐車スペースの各々は、異なる基準領域に対応することができる。駐車スペースのアウトラインは、ナビゲート不可能なタイルと関連付けることができる又は関連付けることができない障壁と考えることができる。例えば、駐車スペースのアウトラインは、ルートが駐車スペースを通って生成されるように（例えば、空間が車で満たされる可能性があるので、歩行者、自転車利用者、又は他者の安全確保のため、更に実用性が得られるように）ナビゲート不可能なエリアとして指定することができる。しかしながら、駐車スペースのアウトラインの特定のエリアは、ナビゲート可能として指定し、歩行者が駐車中の車の間を歩く又はナビゲートすることができるという概念をシミュレートすることができる。駐車場は、複数のレベルの駐車フロアを有する場合があり、複数のレベルの駐車フロアは、エレベータ、階段、又は他の接続部を表す、接続部４０５、６１３又は７０８のような接続部を介して互いに関連付けることができる。
【００７９】
他のエリア又は環境を使用して、ルーティング可能な公開エリア地図を生成することができる。例えば、遊園地、モール、博物館及び他の屋内エリア又は屋外エリアの既存画像を取得して、ルーティング可能な地図又は図面を生成するのに使用することができる。一実施形態においては、展示会エリア又は平面図又は他の一時レイアウトの画像を取得することができる。例えば、展示会のレイアウト設定は、わずか約１週間、約３ヵ月足らず、又は他の時間期間にわたって存続し又は存在する場合がある。一時レイアウトの画像を取得して、上述のようにルーティング可能な公開エリア地図を生成するのに使用することができる。従って、特定の時間期間（約３ヵ月足らず又は他の一時的な時間期間）の後、生成したルーティング可能な地図は、その場所又はエリアにはもはや適用可能ではないであろう。また、生成した公開エリア地図は、一時レイアウトの時間期間に基づいて時間期限を定めることができる。例えば、基準領域又は他の特徴部などの公開エリア地図或いはその一部は、実際のレイアウトが配分された時間期間後に変更又は削除されたときに、消失、削除、又は動作不能とすることができる。公開エリア地図又はその特徴は、デバイス内のタイマー又は外部筋からの通信又は信号に基づいて実行デバイスにより削除することができる。また、特定の基準領域に関連した事象又は特徴は、時間期限を定めるか、又は、特定の基準領域を時間期限を定めるのに使用することができる。例えば、演説、ショー又はアクティビティは、特定の時間期間にわたって指定エリア（例えば、基準領域）で行うことができる。従って、基準領域は、演説、ショー又はアクティビティに関連した特定の時間期間にわたってルーティングのみ可能であるか、又は存在することのみ可能となる。別の代替実施形態においては、基準領域は、移動トラック又は移動店舗など移動可能なものとすることができ、これによって、特定の場所において基準領域が一時的なものになる。或いは、基準領域は、所与の基準領域、店舗、又は売店において商品がどのくらいの期間販売されているかに基づいて、一時的な時間期間にわたってルーティング可能とすることができる。
【００８０】
上記説明においては、グリッド又はメッシュの適用は、これに限定するものではないが、２次元フォーマットを中心としたものである。グリッド又はメッシュは、ｘ、ｙ及びｚ方向の点又は座標を含む３次元グリッド又はメッシュとすることができる（例えば、座標は、経度、緯度、高度情報又は局所座標を含むことができる）。例えば、取得されたレイアウトの画像は、３次元特徴部を含むことができる。例えば、平面図は、フロア傾斜路、段部又は階段、２階構造エリア、又は３次元空間で表示又は指定される他の特徴部を有することができる。また、公園エリア内で丘又は最高点及び谷は、３次元空間で表示又は提供することができる。従って、３次元グリッド又はメッシュは画像上又はこれを覆って適用して、上述のようにルーティング可能な公開エリア地図を生成することができる。ｚ方向の追加は、ルート及び／又は経路を求めるための付加的な計算を必要とする可能性がある。例えば、高さは、最適又は好適なルートを求める際の要素とすることができる。方形タイルを使用する代わりに、三角形セクション又はタイルを３次元グリッド又はメッシュに使用することができる。或いは、他の幾何学的形状を利用することができる。
【００８１】
３次元グリッド又はメッシュは、ある人がオブジェクトを見つける助けとなるのに加えて、ある地点から別の地点に人をルーティングするのに使用することができる。例えば、製品及び商品の垂直方向の棚を有する食料品店又は小売店舗のレイアウトの画像を取得することができる。フロアエリアが２次元又は３次元のタイルと重ね合わされて、垂直棚エリアがグリッド又はメッシュと重ね合わされる３次元グリッドを適用することができる。棚上の異なる製品又は商品は、基準領域として指定することができる。従って、買い物客又はユーザを店内のある場所から、近接又は近隣の棚上で製品を見つけることができる別の場所にルーティングすることができる公開エリア地図を生成することができる。次いで、ルートは、指定の又は選択された製品を指し示す棚又は垂直エリアにわたるグリッドに基づいて計算することができる。買い物客又はユーザは、棚の上を歩くことができないが、ルートは、買い物客又はユーザに正確にその製品が棚の上のどこにあるかを示す際に有用とすることができる。或いは、ルートは、棚に最も近い地面又はフロアタイルで終了するように計算することができる。
【００８２】
別の実施形態においては、上述したように、グリッド、メッシュ又はアレイを使用する代わりに及び／又はこれらを使用することに加えて、色を用いてナビゲート可能なエリア及びナビゲート不可能なエリアを指定することができる。例えば、白色は、ナビゲート可能なエリアと関連付けることができ、黒色は、ナビゲート不可能なエリアと関連付けることができる。任意の数及びタイプの色を用いることができる。従って、ルートは、それぞれのナビゲート可能な色及びナビゲート不可能な色の配置に基づいて計算することができる。例えば、経路又はルートは、距離アルゴリズムに基づいて、ナビゲート可能な色が付いたエリア内で及びナビゲート不可能な色が付いたエリアの回りに生成することができる。また、ルートを計算又は生成するための要素又はコストとして、色の異なる色合い又は色のグラデーションを使用することができる。
【００８３】
更に、上述のように、地図開発者は、画像を取得して、ワークステーション、コンピュータ及び／又は、デバイス１１２などのデバイスを使用し、ルーティング可能な公開エリア地図を生成する。次いで、公開エリア地図は、エンドユーザにより、又はユーザデバイス１１６などのエンドユーザデバイスで受信される。しかしながら、地図開発者とは別個のユーザ又は他のエンティティは、レイアウトの画像を取得して（例えば、エンドユーザは、デバイス１１２又は１１６の一部であるか又は一部ではない場合があるカメラを介してレイアウトの写真を撮ることができ、或いは、エンドユーザは、画像ソース１０４を介して画像を取得することができる）、ルーティング可能な公開エリア地図を自動的に及び／又は手作業で生成することができる。例えば、エンドユーザは、地図開発者又は他のエンティティから公開エリア地図を作成するソフトウェアアプリケーションを取得及び／又は購入することができる。デバイス１１２（図１）は、パーソナルコンピュータなどのエンドユーザにより操作することができる。或いは、デバイス１１２を使用してルーティング可能な公開エリア地図を生成し、公開エリア地図を使用するためにユーザデバイス１１６に送るのではなく、ユーザデバイス１１６を使用して、ルーティング可能な公開エリア地図を生成及び使用することができ、デバイス１１２は迂回される。或いは、デバイス１１２及びデバイス１１６を１つのデバイス又はシステムに組み合わせることができる。
【００８４】
上述のプロセス、方法及び／又は技法を実施するロジック、ソフトウェア、又は命令は、キャッシュ、バッファ、ＲＡＭ、取り外し可能媒体、ハードドライブ、他のコンピュータ可読記憶媒体又はあらゆる他の有形媒体といった、コンピュータ可読記憶媒体又はメモリ、或いは他の有形媒体上で提供される。有形媒体としては、様々なタイプの揮発性及び不揮発性記憶媒体が含まれる。図中で例示され又は本明細書で説明される機能、段階、ステップ又はタスクは、コンピュータ可読記憶媒体内又はその上に格納されたロジック又は命令の１つ又はそれ以上のセットに応答して実行される。機能、段階又はタスクは、特定のタイプの命令セット、記憶媒体、プロセッサ又は処理ストラテジーから独立したものであり、単独で又は組み合わせ動作する、ソフトウェア、ハードウェア、集積回路、ファームウェア、マイクロコードなどにより実行することができる。同様に、処理ストラテジーには、多重プロセッシング、マルチタスキング、並行処理を挙げることができる。一実施形態においては、命令は、ローカル又はリモートシステムにより読み込むために取り外し可能媒体デバイス上に格納される。他の実施形態においては、ロジック又は命令は、コンピュータネットワーク又は他の電話回線を介した転送のために遠隔場所に格納される。更に他の実施形態においては、ロジック又は命令は、所与のコンピュータ、中央処理ユニット（「ＣＰＵ」）、グラフィックス処理ユニット（「ＧＰＵ」）又はシステム内に格納される。
【００８５】
上記の詳細な説明は限定ではなく例証とみなされるものとし、全ての均等物を含む添付の請求項は本発明の範囲を定めることが意図される。
【符号の説明】
【００８６】
１００ システム
１０４ 画像ソース
１０８ ネットワーク
１１２ デバイス
１１６ ユーザデバイス
１２０ ネットワーク又は接続部
１２４ ディスプレイ
１２８ プロセッサ
１３２ メモリ
１３４ アプリケーション
１３６ 入力デバイス
１４０ ディスプレイ
１４４ プロセッサ
１４８ メモリ
１７０ データベース
１８０ ネットワーク
【技術分野】
【０００１】
（関連出願の相互参照）
本特許出願は、同日に出願された名称「ＣＯＳＴ ＢＡＳＥＤ ＯＰＥＮ ＡＲＥＡ ＭＡＰＳ」の同時係属米国特許出願第 号（代理人事件簿第Ｎ０２７５ＵＳ号）、名称「ＯＰＥＮ ＡＲＥＡ ＭＡＰＳ ＷＩＴＨ ＲＥＳＴＲＩＣＴＩＯＮ ＣＯＮＴＥＮＴ」の同時係属米国特許出願第 号（代理人事件簿第Ｎ０２７６ＵＳ号）、名称「ＥＮＤ ＵＳＥＲ ＩＭＡＧＥ ＯＰＥＮ ＡＲＥＡ ＭＡＰＳ」の同時係属米国特許出願第 号（代理人事件簿第Ｎ０２７７ＵＳ号）、名称「ＰＯＳＩＴＩＯＮＩＮＧ ＯＰＥＮ ＡＲＥＡ ＭＡＰＳ」の同時係属米国特許出願第 号（代理人事件簿第Ｎ０２７８ＵＳ号）、名称「ＯＰＥＮ ＡＲＥＡ ＭＡＰＳ ＷＩＴＨ ＧＵＩＤＡＮＣＥ」の同時係属米国特許出願第 号（代理人事件簿第Ｎ０２７９ＵＳ号）、及び名称「ＯＰＥＮ ＡＲＥＡ ＭＡＰＳ ＢＡＳＥＤ ＯＮ ＶＥＣＴＯＲ ＧＲＡＰＨＩＣＳ ＦＯＲＭＡＴ ＩＭＡＧＥＳ」の同時係属米国特許出願第 号（代理人事件簿第Ｎ０２８０ＵＳ号）の関連出願であり、これら特許出願の開示内容全体は引用により本明細書に組み込まれる。
【０００２】
本発明は、ナビゲーションに関し、更に詳細には、ルーティング（経路選択）に使用することができる公開エリア地図(open area map)に関する。
【背景技術】
【０００３】
世界人口が増加するにつれて、人類の発達を支える益々多くのインフラストラクチャー、建物、外部及び内部開発及び他の地物が生成されている。既存のインフラストラクチャー、建物、公園及び他の環境もまた、より多くの人々及び往来に対応するように適応されつつある。環境の増加及び適応は、ある場所から別の場所への移動及び人々の移動方法に影響を与える。
【０００４】
ナビゲーションシステム及び／又はデバイスは、移動を支援するのに使用される。例えば、車両ナビゲーションデバイスは、人が道路網を運転するのを支援することができる。このようなデバイスは、既存の道路又は経路に基づいて所望の目的地までのルーティング及び案内を行うことができる。
【０００５】
しかしながら、道路、路線又は経路が設定されていないエリア(area)を人々が動き回るエリア、又はエリア内で１つの地点から別の地点に移動する上で、このような経路が必要ではないエリアがある。例えば、建物の各階、公園或いは他の外部又は内部エリアを日常的に歩いている。人々は、このようなエリア内で多くのパターンで動き回り、１つの場所から別の場所に到達することができる。しかしながら、これらのエリア内での一部の移動又は移動パターンは、混乱や、エリアのレイアウトについての知識不足又は他の要素により、非効率であったり不必要な場合がある。また、人は、このようなエリア内で１つの地点から所望の目的地に到達するための方法を知らない可能性がある。
【発明の概要】
【課題を解決するための手段】
【０００６】
１つの態様によれば、公開エリア地図を生成する方法が提供される。本方法は、レイアウトの画像を取得する段階を含む。レイアウトは、人が動き回る現実世界のエリアを表す。グリッドが画像上に適用される。グリッドは、画像の接地エリアを満たすタイルを含む。ルーティング可能な地図が、グリッドの関数として生成される。ルーティング可能な地図は、レイアウト内でポイントツーポイントルーティングを行うように構成される。
【０００７】
本発明は、添付の請求項により定められ、このセクションのいかなるものも上記の請求項に対する限定とするべきではない。本発明の更なる態様及び利点は、好ましい実施形態に関連して以下で説明する。
【図面の簡単な説明】
【０００８】
【図１】公開エリア地図を生成するシステムの図である。
【図２】図１のシステムにおいて使用されるレイアウトの画像である。
【図３】図１のシステムにおいて使用されるプロセスに対応する画像である。
【図４】図１のシステムにおいて使用される別のプロセスに対応する別の画像である。
【図５】図２の画像に対応する基準領域を例示する図である。
【図６】図１のシステムにより生成された公開エリア地図の画像である。
【図７】図１のシステムにより生成された別の公開エリア地図の別の画像である。
【図８】公開エリア地図を生成する方法のフローチャートである。
【図９】図８の方法の段階の例を示すフローチャートである。
【図１０】公開エリア地図内のルーティングの方法のフローチャートである。
【発明を実施するための形態】
【０００９】
図１は、１つ又はそれ以上の公開エリア地図を生成するのに使用されるシステム１００の一実施形態を示す。システム１００は、これに限定するものではないが、１つ又は複数の画像ソース１０４、ネットワーク１０８、デバイス１１２、ネットワーク又は接続部１２０、データベース１７０、ネットワーク１８０、及びユーザデバイス１１６を含む。付加的な、又はより少ない、或いは異なる構成部品を設けてもよい。例えば、プロキシサーバ、ネームサーバ、地図サーバ、キャッシュサーバもしくはキャッシュネットワーク、ルータ、スイッチもしくはインテリジェントスイッチ、地理データベース、付加的なコンピュータもしくはワークステーション、管理ワークステーションのような管理構成部品、ゲートウェイデバイス、バックボーン、ポート、ネットワーク接続部、及びネットワークインタフェースを設けることができる。図１の構成部品は互いに別個に示されているが、これらの構成部品の１つ又はそれ以上を組み合わせてもよい。
【００１０】
画像ソース１０４は、ウェブサイト、アプリケーション、プログラム、ワークステーションもしくはコンピュータ、ファイル、メモリ、サーバ、ビーコンもしくは地図ビーコン、デポジトリ、及び／又は画像又は画像に関連するデータを格納又は含むことができるあらゆる他のハードウェア及び／又はソフトウェアコンポーネント又はデータベースである。或いは、画像ソース１０４は、１つ又はそれ以上の画像である。
【００１１】
一実施形態においては、画像ソース１０４は、レイアウトの１つ又はそれ以上の画像を含む。画像は、ＪＰＥＧ、ビットマップ、ピックスマップ、Ｔｉｆｆ又は他の画素又はラスタベースのファイル形式のような、ラスタ又は画素ベースの画像である。画像は、紙又はハードレイアウトのラスタ又は画素化されたスキャンしたコピーとすることができる。或いは、画像は、ベクトルベース又はベクトル化画像とすることができる。レイアウトは、人、歩行者又は人々が歩行及び／又は動き回る現実世界のエリアに対応することができる。レイアウトはまた、未だ構築されていない将来の現実世界のエリアに対応することもできる。或いは、レイアウトは、架空の場所、設定又はエリアに対応することができる。
【００１２】
レイアウトは、未編成又は無制約の地理的エリアを表すことができる。例えば、レイアウトは、歩行者が、設定された道路網又は経路網上でのみ移動するように限定されていないエリアである。むしろ、歩行者は関連した道路又は経路網或いはパターンのない公共の広場、公園、建物、通路、ロビー又は廊下を通り抜けることができる。加えて、歩行者には、道路上の移動体として方向制約がない。更に、歩行者は、レイアウトにおいて運動の自由度がより大きく、あらゆる所与の公開領域内であり余る程の自ら決定する経路から選ぶことができる。
【００１３】
レイアウトの画像は、現実世界の建物の平面図、駐車場、公園、屋内又は屋外のレクリエーションエリア及び／又は人が歩行又は移動することができる（例えば、車椅子、自転車又は他の移動支援デバイスを介して）場所に対応する他の内部及び外部エリアの施設の画像を含むことができる。画像は、既存の画像又は公的に利用可能な画像である。例えば、画像は、本来、ルーティング可能な地図を生成すること以外の目的で形成又は作成される。既存の画像は、ルーティング可能な公開エリア地図の開発者及び／又はそのエンドユーザとは別のエンティティにより生成することができる。既存画像は、無料で或いは購入価格（例えば、オンライン）を支払うことで、一般の人々又はエンティティが利用可能である。或いは、自然発生画像、ルーティング可能な地図を作成するのに当初生成された画像、又は非公的な画像を用いることができる。
【００１４】
画像ソース１０４は、ネットワーク１０８を介してデバイス１１２と通信している。ネットワークは、インターネット、イントラネット、ローカルエリアネットワーク（「ＬＡＮ」）、広域ネットワーク（「ＷＡＮ」）、仮想プライベートネットワーク（「ＶＰＮ」）、ローカル無線又は有線接続部（例えば、ＵＳＢ接続部又は他のデバイス接続部）、及び／又は何らかの公知の又は将来のネットワーク又は接続部である。
【００１５】
デバイス１１２は、ルーティング可能な公開エリア地図を生成するためレイアウトの画像を画像ソース１０４から受信する。デバイス１１２は、ワークステーション、コンピュータ、編集デバイス、ビーコン又は地図ビーコン、及び／又は他のコンピュータ又は送信デバイスである。例えば、デバイス１１２は、編集ワークステーションである。デバイス１１２は、これに限定するものではないが、ディスプレイ１２４、プロセッサ１２８、メモリ１３２、アプリケーション１３４及び入力デバイス１３６を含む。付加的な、又はより少ない、或いは異なる構成部品を設けてもよい。オーディオコンポーネントを設けることができる。例えば、スピーカ、オーディオジャック、及び／又は可聴又は音声信号を出力又は受信する他のコンポーネントが設けられる。
【００１６】
ディスプレイ１２４は、デバイス１１２内で、又はデバイス１１２上で、或いはデバイス１１２と通信して表示にアクセス可能にするように位置決めされた何らかの機械式又は電子式ディスプレイである。例えば、ディスプレイ１２４は、タッチスクリーン、液晶ディスプレイ（ＬＣＤ）、陰極線管（「ＣＲＴ」）ディスプレイ、又はプラズマディスプレイである。ディスプレイ１２４は、レイアウト、平面図、地図又は他のエリアの画像などの画像を表示するように動作可能である。入力デバイス１３６は、ボタン、キーパッド、キーボード、マウス、トラックボール、ロッカスイッチ、タッチパッド、音声認識回路、又は、デバイス１１２でデータを制御又は入力する他のデバイス又は構成部品である。入力デバイス１３６を使用して、受信画像の修正（例えば、ドア又は開口部を追加する）、又は消去ツールを使用するなどの機能を実行することができる。
【００１７】
プロセッサ１２８は、メモリ１３２、アプリケーション１３４、ディスプレイ１２４、及び入力デバイス１３６と通信している。プロセッサ１２８は、より多くの又はより少ない構成部品と通信状態になることができる。プロセッサ１２８は、汎用プロセッサ、特定用途向け集積回路（「ＡＳＩＣ」）、デジタル信号プロセッサ、フィールドプログラマブルゲートアレイ（「ＦＰＧＡ」）、デジタル回路、アナログ回路、又はこれらの組み合わせである。プロセッサ１２８は、デバイス１１２の様々な電子部品及びロジックを制御し、及び／又はこれらと通信するように動作可能な１つ又はそれ以上のプロセッサである。プロセッサ１２８、メモリ１３２、及び他の回路は、集積回路の一部であってもよい。
【００１８】
メモリ１３２は、何らかの公知の又は将来の記憶装置である。メモリ１３２は、ランダムアクセスメモリ「ＲＡＭ」（電子部品）、読取り専用メモリ「ＲＯＭ」（電子部品）、又は消去可能プログラマブル読取り専用メモリ（ＥＰＲＯＭ又はフラッシュメモリ）など、不揮発性及び／又は揮発性メモリである。メモリネットワークを設けてもよい。メモリ１３２は、プロセッサ１２８の一部とすることもできる。メモリ１３２は、画像ソース１０４により受信されたレイアウトの画像を格納するように動作可能であり、又は構成される。メモリ１３２はまた、プロセッサ１２８により生成された画像又はデータを格納することもできる。
【００１９】
プロセッサ１２８は、アプリケーション１３４を実行するように動作可能であり、又は構成される。アプリケーション１３４は、画像ソース１０４から受信される画像など、既存画像に基づいてルーティング可能な公開エリア地図を生成するのに使用されるソフトウェアプログラムである。例えば、プロセッサ１２８は、アプリケーション１３４を実行して、入力デバイス１３６からの入力及び／又は自動コマンドからの入力を介してルーティング可能な地図を作成又は生成し、或いはその生成を支援する。アプリケーション１３４は、メモリ１３２及び／又は他のメモリ内に格納することができる。
【００２０】
デバイス１１２は、ユーザデバイス１１６に１つ又はそれ以上の生成されたルーティング可能な公開エリア地図を送信又は伝送するように動作可能であり、又はそのように構成され、或いは、ユーザデバイス１１６は、ネットワーク又は接続部１２０を介してルーティング可能な公開エリア地図をリクエストすることができる。接続部１２０は、インターネット、イントラネット、ローカルエリアネットワーク（「ＬＡＮ」）、広域ネットワーク（「ＷＡＮ」）、仮想プライベートネットワーク（「ＶＰＮ」）、ローカル無線又は有線接続部（例えば、ＵＳＢ接続部又は他のデバイス接続部）及び／又は公知の又は将来のネットワーク又は接続部である。
【００２１】
或いは、デバイス１１２は、１つ又はそれ以上の生成されたルーティング可能な公開エリア地図又はそのデータをデータベース１７０に格納、アップロード、又は送信することができる。データベース１７０は、データベース、メモリ、ウェブサイト、サーバ、ビーコン、又は、ルーティング可能な公開エリア地図に対応するデータを格納、受信、及び／又は送信するのに使用される他のデバイスとすることができる。例えば、データベース１７０は、基準領域、コスト、制約事項、グリッド又はアレイ、画像データ及び／又は他のコンテンツに対応するデータのような、公開エリア地図の異なる層を表すデータエンティティを格納することができる。ユーザデバイス１１６は、デバイス１１２との通信を行わないなど、ネットワーク１８０を介してデータベース１７０からルーティング可能な公開エリア地図又はそのデータを取得することができる。ネットワーク１８０は、インターネット、イントラネット、ローカルエリアネットワーク（「ＬＡＮ」）、広域ネットワーク（「ＷＡＮ」）、仮想プライベートネットワーク（「ＶＰＮ」）、ローカル無線又は有線接続部（例えば、ＵＳＢ接続部又は他のデバイス接続部）、及び／又は、公知の又は将来のネットワーク又は接続部である。
【００２２】
また、ルーティング可能な公開エリア地図は、ユーザデバイス１１６上に「プッシュする」ことができる。例えば、ビーコン、地図ビーコン、又は、他のデバイスは、ユーザデバイス１１６の場所又は位置に基づいて、ルーティング可能な公開エリア地図又は関係するコンテンツをユーザデバイス１１６に伝送又は送信することができる。一実施形態においては、ビーコンは、建物又は他のエリアの入口又は通路に配置することができ、ユーザデバイス１１６がビーコンの特定の範囲内に入ると、エリア及び／又は他の関係するエリアに関連付けられたルーティング可能な公開エリア地図がユーザデバイス１１６に送られる。
【００２３】
ユーザデバイス１１６を用いて、それぞれのレイアウト又はエリア内で又はその上でユーザがナビゲートできるように１つ又はそれ以上のルーティング可能な地図を操作する。ユーザデバイス１１６は、携帯電話、モバイル電話、個人用携帯情報端末（「ＰＤＡ」）、時計、個人用ナビゲーションデバイス（「ＰＮＤ」）、コンピュータ、デジタル平面図デバイス、携帯型又は非携帯型のナビゲーションデバイス、キオスク及び／又は他の固定式、着脱式、又は搬送可能なデジタルデバイスである。ユーザデバイス１１６は、これに限定するものではないが、ディスプレイ１４０、プロセッサ１４４、及びメモリ１４８を含む。付加的な、又はより少ない、或いは異なる構成部品を設けてもよい。例えば、オーディオコンポーネント及び／又はアプリケーションコンポーネントを設けてもよい。ディスプレイ１４０、プロセッサ１４４、及びメモリ１４８は、それぞれ、ディスプレイ１２４、プロセッサ１２８及びメモリ１３２とは類似したものであっても、又は異なるものであってもよい。
【００２４】
一実施形態においては、建物のフロアで働いている人などのユーザは、自分が建物フロアの周囲でルーティング又はナビゲートできることを望む可能性がある。従って、画像ソース１０４内に格納されている、ユーザのフロアのレイアウト又は平面図の画像は、デバイス１１２で送受信される。地図開発者などの別のエンティティがデバイス１１２を操作する。地図開発者は、イリノイ州シカゴに所在するＮＡＶＴＥＱ Ｎｏｒｔｈ Ａｍｅｒｉｃａ， ＬＬＣのような、ナビゲーション用の地図を開発するか或いは地図データ及び／又は地理的データベースを取得及び維持する、人、会社、又はエンティティとすることができる。地図開発者は、ディスプレイ１２４上でレイアウトの既存画像を見て、入力デバイス１３６及びソフトウェアアプリケーション１３４を介して既存画像に基づいてルーティング可能な地図を生成する。自動化されたコマンド及び／又はプロセスをルーティング可能な公開エリア地図の開発において用いることができる。或いは、ルーティング可能な公開領域の作成又は生成は、実質的に全体を自動化することができる。ユーザは、ユーザデバイス１１６上で自分のフロアのルーティング可能な地図をダウンロード又は受信することができる。例えば、ユーザは、ユーザデバイス１１６を使用して、デバイス１１２、又はデバイス１１２に関連する格納サイト又は構成部品（例えば、ＵＳＢ接続部、無線接続又は他の接続部のような接続部１２０を介して）からルーティング可能な地図又はそのデータをダウンロードする。或いは、ユーザは、ユーザデバイス１１６とは異なるデバイス（例えば、コンピュータ又はジャンプ／サムドライブ）上でルーティング可能な地図をダウンロードして、次いで、ユーザデバイス１１６又は他のユーザデバイスにルーティング可能な地図に関連したデータを転送することができる。次に、ユーザは、ユーザデバイス１１６を使用して、建物フロアに関するルーティング、案内、及び／又はナビゲートを目的としてルーティング可能な地図を表示する。
【００２５】
図２は、システム１００において使用されるレイアウトの画像２０１の一実施形態である。画像２０１は、インターネット又は他のネットワークからダウンロードすることができる既存の又は公的に利用可能な画像（例えば、画像ソース１０４又は他のソースに関連するもの）である。例えば、画像２０１は、ウェブサイト又は他のソースからダウンロード、受信、取得することができる。画像２０１は、１階又は他の階など、建物フロアの現実世界のレイアウト又は平面図を表す。画像２０１は、レイアウト内のエリア、空間、及び／又は表示のグラフィック表現又はアイコンを含む。例えば、画像２０１は、男性用トイレ２１７、女性用トイレ２２１、カフェテリア２２５、事務所２２９、会議室２３３、研究室２３７、机２４１及びエレベータ又はエレベータ列２４５など、画像基準オブジェクトを含む。ドア２４９の画像表現も提供される。ドア２４９は、それぞれの画像基準オブジェクトのギャップ又は開口部として示されている。或いは、ドアは、開口部ではなく、ドアシンボル又は画像オブジェクト２５３を使用して表すことができる。或いは、ドア又は開口部の表現がない場合がある。
【００２６】
画像２０１はまた、人々が歩行又は動き回ってそのフロアのある場所から別の場所に到達するような、広場、歩行地面、共用又は公共エリア、及び／又はホールエリア２０９の画像表現を含む。壁部又は障壁は、実質的に同じ又は類似の色の対応する、又は関連する、或いは連続する画素又は線（例えば、太線）により描かれる。入口及び／又は出口２１３は、内部エリア２０９と外部エリア２０５との間でのアクセスを可能にする壁部又は障壁の開口部又はギャップとして描かれる。外部エリア２０５は、外廊下、建物の外側（例えば、歩道、通り又は道路）、又は他の外部環境を表すことができる。
【００２７】
図３は、図１のシステム１００において使用されるプロセスに対応する又は該プロセスを受ける画像２０１の一実施形態である。例えば、画像２０１は、デバイス１１２でダウンロード又は受信される。画像２０１は、ルーティング可能な公開エリア地図を作成又は生成するのに使用される。例えば、グリッド、メッシュ又はアレイ３００は、画像２０１又は画像２０１のコピーの上又はこれを覆って適用される。グリッド、メッシュ又はアレイ３００は、タイル、断面、ブロック、先端、点、円、多角形又は他の形状など幾何学的な形状（例えば、均一な大きさの幾何学的な形状）のグリッド又はアレイとすることができる。グリッド又はメッシュ３００は、画像２０１の地上エリア全体を覆う。地上エリアとは、その上を歩行することができる表面、平面、又は床、もしくはその一部、並びにオブジェクト又は障壁をその上又はこれを覆って配置又は位置決めすることができる表面を指す。
【００２８】
グリッド又はメッシュ３００は、エリア、断面、ブロック又はタイル３０４を含む。或いは、グリッド、メッシュ又はアレイ３００は、タイル３０４に類似したエリア又は断面に対応する接続されていない点又は先端を含むことができる（例えば、点又は先端は、タイル３０４に交換するか、又はタイル３０４の代替物として機能する）。タイル３０４は、略矩形又は正方形の形状を有し、大きさがほぼ均一である。或いは、タイル３０４は、円形、三角形、又は他の幾何学的又は多角形形状を有することができ、タイル３０４は、均一ではなく異なる場所で異なるサイズとすることができる。
【００２９】
グリッド３００は、画像全体又は地上エリア全体ではなく、レイアウトの特定のエリアを覆うように適用することができる。例えば、グリッド３００は、内部エリア２０９のような廊下エリア内においてのみ適用することができる。このような場合、グリッド３００は、形状が既存画像の壁部に対応する境界線を有する現実世界のエリア内の歩行者アクセス可能な連続したサブエリアに対応する形状を有する。グリッド３００又はその一部は、画像基準オブジェクト（例えば、部屋の内部エリア）内で指定されるエリアに適用することもできる。また、タイルは、連続した公開領域に自動的に埋めることができる。例えば、廊下又は通路エリアは、グリッド又はメッシュのタイル又は断面でこのエリアを自動的に埋めるように選択することができる。
【００３０】
タイル３０４は、局所的又は大域的地図座標など、座標を割り当て又は指定することができる。例えば、タイル３０４の各中央部又はタイルの他の部分には、（ｘ,ｙ）の緯度と経度、又は他の座標指定が与えられる。画像のコーナにおけるなど、タイル３０４のうちの１つは、基準及び位置決めを目的として原点（０,０）として指定することができる。座標により、アイテム、特徴部又は領域を検索可能にすることができる。しかしながら、ルーティングの目的としては座標を用いることはできない。
【００３１】
図４は、メッシュ３００が重ね合わされた後に、別の段階又はプロセスに対応又はこれらを受けた画像の一実施形態である。上を歩くべきではないタイル又はナビゲート不能のタイルは、タイル又はエリア４０１（例えば、タイル又はエリア４０１は、ナビゲート不能のエリアを表す接続されていない点又は先端と置き換えることができる）として設けられる。画像基準オブジェクトの境界又は壁部を囲むか又はこれらの下にあるタイル、或いはこれらに関連したタイル（例えば、基準オブジェクト２１７、２２１、２２５、２２９、２３３、２３７、２４１及び２４５）は、ナビゲート不可能なタイル４０１であるように選択され又は指定される。また、内部ホールエリア２０９と外部エリア２０５との間の境界、障壁又は壁の画像表現は、ルーティングを目的としてナビゲート不可能なタイル４０１と関連けられる。タイル４０１により、現実世界の体験を表現するために、種々のルートが壁部又は障壁を通り抜けることを禁止することができる。しかしながら、ドア２４９及び２５３は、タイル４０１により囲まれる部屋又はエリアを出入りするルーティングを許可するためにナビゲート可能なタイル３０４に関連付けられる。或いは、ドア又は開口部が存在しない又は作成されない場合、基準エリアに実質的に隣接又は近接するタイルは、それぞれの基準エリアを起点及び終点としたルーティングに使用することができる。
【００３２】
ナビゲート不可能なタイル４０１は、グリッド３００から除去されたタイル（或いは、点又は先端）であるか、又はそのタイルを表すことができ、或いは、ナビゲート不可能なステータスで指定されるタイル（又は点又は先端）とすることができる。ナビゲート不可能なタイル４０１又はタイルの欠如は、空きスペースとして表現することができ、このグリッド又はタイルがないスペースは、ルーティングを目的としてナビゲート不可能である。或いは、ナビゲート不可能なタイル４０１は、ナビゲート可能なタイル３０４とは異なるように着色することができる。
【００３３】
ナビゲート可能な又はナビゲート不可能なタイル、点もしくは先端は、下位分類にすることができる。例えば、各タイル又は一部のタイルは、レイアウトに関係する特徴部又は場所に関連付けることができる。一実施形態においては、タイルは、洗面所エリア、狭いエリア、窓のあるエリア、照明が薄暗いエリア、交通量の多いエリア、交通量の少ないエリア、又は他のエリア又は特徴部にリンク付け又は対応することができる。タイルを分類又は下位分類することにより、ルーティングを目的として優先度を入力することができる。例えば、ユーザは、交通量の多いエリアを回避したい場合があり、これに従って、ユーザは、ルーティング前又はルーティング中に自分の優先度を入力することができる。
【００３４】
ラップ又は境界線特徴部は、グリッド３００に関して使用することができる。特定の場合において、人は、内部エリア２０９のある地点から内部エリア２０９の別の地点までルーティングしたい場合があるが、外部エリア２０５に出て内部エリア２０９に戻るように人をルーティングする経路が生成される。このようなルートは、外側に出て内側に戻るルーティングを行う（例えば、内部エリアと外部エリアとの間に複数の開口部を有するとき）ことが最適であるときに生じる可能性がある。しかしながら、外部エリア２０５内のタイルへのあらゆるルーティングを回避するために、エリア２０９及び関連したエリア内での全てのルーティングを境界付けるラップ又は境界線特徴部を用いることができる。例えば、境界線又は指示を内部エリアの周囲に沿って配分することができる。しかしながら、境界線特徴部は、ユーザが外部エリア２０５内に又は内部エリアの外側にある目的地点を選択したときに、外部エリア２０５へのルーティングが可能となる。或いは、外部エリア２０５のタイルは、ナビゲート不可能と指定することができ、又は、外部エリア２０５への開口部をナビゲート不可能なタイル４０１と関連付けることができる。
【００３５】
接続ポイント４０５も設けられている。接続ポイント４０５は、グリッド又はメッシュ３００から別個の空間層又はデータ層内に生成又は設けることができる。接続ポイント４０５は、エリア内のタイル３０４又はタイル３０４のサブセットとして表現される。接続ポイント４０５は、エレベータ２４５のエリア全体又はその一部を包含することができる。或いは、接続ポイント４０５は、基準画像オブジェクト又は基準領域と関連付けることはできない。接続ポイント４０５は、ルーティング及びナビゲーションを目的として、ルーティング可能であるこのような公開エリア地図を表すか、又は別の地図へのリンクとして機能する。例えば、接続ポイント４０５は、１つ又はそれ以上のエレベータ、階段の吹き抜け、エスカレータ、梯子或いは別のフロア又はエリアへ人を移動させる他の特徴部に対応することができる。複数の接続ポイント４０５は、それぞれの個々のエレベータ又は特徴部に対応することができる。一実施形態において、接続ポイント４０５は、画像２０１からのエリア又は地点と、建物の別のフロア（例えば、２階、第３階又はｎ階）を表す別の地図又は平面図のような、別の地図又は平面図上の別の点又はエリアまでの間でルーティングするのに使用される。或いは、接続ポイント４０５は、同じフロア又は地上エリア上である地点から別の地点に人を移動又は搬送させる接続部を表すことができる。例えば、接続ポイント４０５は、動く歩道又は他の輸送デバイスに対応することができる。また、接続ポイント４０５は、同じレベル又はエリアに関連付けられた別のルーティング可能な公開エリア地図への接続部を表すことができる。例えば、１つの公開エリア地図においては、ルートは、フードコートのような基準エリアを表す空白の、指定されていない、又は一般多角形又は形状により表されるエリアに対して生成することができる。接続ポイントは、一般多角形にて、一般多角形により、又は一般多角形上で配置することができ、該一般多角形は、接続ポイントが元の基準エリア（例えば、フードコート）内の詳細な特徴部及び／又は基準領域を有する別のルーティング可能な公開エリア地図に対応するか、又はナビゲーションする基準エリアを表す。一般的な又は親の公開エリア地図（フードコート基準エリア）を表示することができ、次いで、特定の又は子の公開エリア地図（フードコート内の基準領域又は基準エリア）にルーティングするか、又はこれを選択したときに、子の公開エリア地図は、別個のウィンドウ又は異なる画面内などに表示することができる。
【００３６】
図５は、画像２０１に対応する基準領域５００を示す図である。グリッド３００とは別個の空間層において、基準領域５００が生成される。例えば、画像２０１内の画像基準オブジェクト２１７、２２１、２２５、２２９、２３３、２３７、２４１及び２４５は、ラスタ画像又は画素化画像の一部である。ラスタ画像は２値化することができる（例えば、画素を白画素及び黒画素、及び／又は１及び０に変換）。デバイス１１２は、画像基準オブジェクトと関連した名前又は説明を抽出する。この分離は、ラスタ画像２０１と関連した名前又は説明に対応するテキスト５０４を生成するための光学式文字認識（「ＯＣＲ」）を容易にすることができる。テキスト５０４は、公開エリア地図の異なるエリアを検索又は関連付けるのに使用される。テキスト５０４は、画像２０１の名前又は説明に一致させることができる。或いは、付加的な又は異なるテキスト又は情報を追加することができる。例えば、テキスト「Ａ」、「Ｂ」、「Ｃ」、「Ｄ」、「Ｅ」、「Ｆ」、及び「Ｇ」は、区別するために「事務所」テキストに追加される。追加されたテキストは、エンドユーザに可視又は不可視とすることができる。
【００３７】
グラフィックスとテキストの分離後、画像基準オブジェクトは、ベクトル化を経て、多角形、基準領域又はエリア５００を形成する。基準領域５００は、画像２０１内の異なるエリア、部屋又はスペースに対応する。基準領域５００は、異なる空間層上のグリッド３００によって表されるそれぞれのナビゲート可能タイル３０４及びそれぞれのナビゲート不可能タイル４０１に関連付けられ、又はこれらに対応する。
【００３８】
グリッド又はメッシュ層は、基準領域層、接続層、及び／又は、コスト層又は制約層など他の空間層又はデータ層と共にコンパイルして、ナビゲーション及び／又はルーティングに使用できる公開エリア地図を形成又は生成することができる。
【００３９】
図６は、図１のシステム１００により生成された公開エリア地図６０１の一実施形態を示す。公開エリア地図６０１は、ユーザデバイス１１６のディスプレイ１４０又は他のディスプレイ上に表示することができる。公開エリア地図６０１は、画像２０１の基準画像オブジェクトのグラフィック表現を含む。例えば、画像２０１は、公開エリア地図６０１の背景又はベース画像として使用される。或いは、異なるグラフィックス又は画像が、画像２０１の元のレイアウトを表すのに生成される（例えば、基準領域５００の生成に基づいて）。ナビゲート可能なタイル３０４又ナビゲート不可能なタイル４０１を含むか又はこれらが欠如したグリッド３００は、基準領域５００及び接続ポイント４０５と共にコンパイルされて、ルーティング及びナビゲーションを目的とした公開エリア地図６０１の基礎をなす。例えば、グリッド３００又はコンパイルされたグリッドは、ユーザが見ることはできない。或いは、グリッド３００及び／又は特徴部は、ユーザに晒される場合もある。
【００４０】
図７は、図１のシステム１００により生成された公開エリア地図７００の一実施形態を示す。公開エリア地図７００は、公開エリア地図６０１により表されたフロアを含む建物の別のフロアを表す。公開エリア地図７００は、休憩室、会議室、エレベータ又はエレベータ列、事務所、及び体育館などの、画像基準オブジェクト、並びに、関連する基準領域、グリッド、接続ポイント７０８、及び上述の公開エリア地図６０１のそれぞれの特徴部に類似したナビゲート可能タイル及びナビゲート不可能タイルを含む。
【００４１】
一実施形態においては、ユーザは、公開エリア地図６０１及び７００を使用して、あるフロアの事務所から建物の別のフロアまでルーティングすることを望む場合がある。図６を参照すると、ユーザは、テキストサーチを使用して事務所を検索し、原点６０９を指定する。特定の事務所のテキストは、それぞれの基準領域５００と関連付けられ、該基準領域５００は、それぞれのタイル３０４及び４０１と関連付けられる。或いは、ユーザは、ディスプレイ上で原点６０９に物理的にタッチ又は選択する。或いは、原点は、全地球測位衛星（「ＧＰＳ」）システム又はデバイス、屋内位置測定システム（例えば、ＷｉＦｉベース）、又は原点の位置が固定される（例えば、キオスク又は壁部上の平面図デバイス）ことに基づいて求められる。原点６０９は、事務所の基準領域又は基準画像オブジェクト内の、又はこれらに関連付けられた１つ又はそれ以上のタイルに対応することができ、又はエリア全体に対応することができる。図７を参照すると、ユーザは次に、テキストサーチを用いて体育館について検索し、目的地点７１２を指定する。体育館のテキストは、それぞれのタイルに関連付けられた、体育館のそれぞれの基準領域と関連付けられる。或いは、ユーザは、ディスプレイ上で目的地点７１２に物理的にタッチ又はこれを選択する。ユーザは、公開エリア地図７００に切り替えることができ、又は、同じ画面又はウィンドウ上で両方の公開エリア地図６０１及び７００を表示することができる。
【００４２】
原点６０９及び目的地点７１２が選択された後、様々なルートが、基礎となるコンパイルグリッドに基づいて計算及び／又は比較される。ルートは、ダイクストラ法、Ａスターアルゴリズム又は検索、及び／又は他のルート探索又は計算アルゴリズムに基づいて計算することができる。距離、ナビゲート不可能なエリア、コスト及び／又は制約事項など様々な態様が、最適ルートを求めるために検討される。経路６０５（図６）は、計算結果に基づいて生成される。経路６０５は、ユーザが見て追従するために表示される。経路６０５は、事務所内の原点６０９から始まり、会議室を通り、接続部４０５などの接続部６１３を経由してエレベータを使用する経路を示す。その後、公開エリア地図７００は、接続ポイント７０８にてエレベータから始まり、目的地点７１２の体育館に至る経路７０４（図７）を示す。
【００４３】
ルート及び／又は経路６０５及び７０４の計算及び決定は、隣接タイル、連続タイル、又は接続タイルに基づき、又はこれらから形成される。例えば、互いに境界で接するか又は接触するナビゲート可能なタイルは、ポイントツーポイントルーティングに対して考慮され、レイアウト内の任意のエリア又は隣接タイルに関連する任意の地点が、グリッド又はメッシュ（すなわち、単に所定のルートだけでない）に関する計算結果に基づいてルーティングすることができる。ルートを形成する隣接タイルは、中心点又は他の部分により接続又はリンク付けすることができる。
【００４４】
図８は、公開エリア地図６０１又は７００などの公開エリア地図を生成する方法のフローチャートである。より少ないか又はより多いステップ又は段階を設けることができ、ステップの組み合わせも設けることができる。また、ステップ又は段階は、図示するような順番で、又は異なる順番で実行することができる。本方法は、本明細書で説明するシステム及び／又はデバイス、或いは異なるデバイス又はシステムによって実施される。
【００４５】
一実施形態においては、画像２０１のようなグラフィック表現又はレイアウト画像を取得又は受信する（ステップ８０１）。例えば、ワークステーション、コンピュータ、又はデバイス１１２など他のデバイスを使用する地図開発者は、ネットワーク１０８のようなインターネット又は他のネットワークもしくは接続部を介して、建物平面図などのレイアウトの既存画像をダウンロード又はリクエストする。画像のグラフィック表現は、ウェブサイト、サーバ、ファイル、別のコンピュータ又は他のデバイス、或いは画像ソース１０４などの任意の他の記憶装置又はエリアに格納又は位置付けることができる。レイアウトの画像は、無線により及び／又は有線接続を介して受信することができる。受信した画像は修正することができる。例えば、地図開発者が画像特徴部を追加又は除去することができるように、消去又は描画ツール或いは機能を設けることができる。場合によっては、ドア又は開口部は、ルーティングを目的として追加する必要がある可能性がある。
【００４６】
レイアウトの画像、レイアウトの画像のコピー、又はレイアウトの修正画像の上又はこれらを覆って、グリッド又はアレイ３００のようなグリッド、メッシュ又はアレイを適用又は重ね合わせる（ステップ８０５）。地図開発者は、レイアウト内の距離測定値を指定することにより、スケールを割り当てる。例えば、マウス、又は入力デバイス１３６のような他の入力デバイスを使用して、地図開発者は、廊下又はエリアの幅又は長さを表す、基準オブジェクト２１７、２２１、２２５、２２９、２３３、２３７、２４１及び２４５などの画像オブジェクト間の空間又は距離を選択する。次いで、地図開発者は、１メートル又は３メートルなどの値をその空間又は距離に割り当てる。或いは、距離測定値の指定には、「ポップアップ」画面又は記入式ボックスを介して入力することができ、又は、距離測定値は、画像内の既存距離マーカー又は所定のパラメータに基づいて自動的に実施することができる。スケールを割り当てることにより、レイアウト内のオブジェクトとエリアとの間の距離の認識が得られる。
【００４７】
次いで、グリッド又はメッシュをレイアウトの画像上に適用するか、又はスケールを割り当てる前にグリッド又はメッシュを適用する。例えば、レイアウトの実質的に画像全体を覆うグリッドを設ける。或いは、グリッドを適用するためのある部分又は特定の部分を選択する。一実施形態において、グリッドは、廊下或いは他の地上又は公開領域など、基準オブジェクト間での歩行に指定されたエリアにだけ適用することができる。従って、グリッド又はメッシュは、画像内の境界、障壁及び／又は壁部と交差しない。また、グリッド又はメッシュは、室内のエリアのような内部エリア又は画像基準オブジェクト上に適用することができる。地図開発者は、グリッド、グリッドの一部又は入力デバイスによって結合することができる複数のグリッドをどこで適用するかを選ぶことができる。例えば、地図開発者は、レイアウト内の廊下エリアをクリック又は選択して、廊下エリア全体にグリッドを適用することができる。代替の実施形態においては、グリッド又はその一部は、色／画像認識又は他のパラメータに基づいて、レイアウト又はレイアウトの一部の実質的に画像全体にわたって自動的に重ね合わされる。
【００４８】
グリッド、メッシュ又はアレイは、上述のように、タイル３０４、又は類似の或いは対応する点又は先端など、タイル、ブロック、断面又はエリアから構成されている。スケーリングに基づいて、タイルは、測定値に割り当てられ又はこれに対応する。例えば、各タイルは、約１平方メートル、１／４平方メートル又は他の値の測定値を有することができる。或いは、各タイルは、任意の他の測定値、又は、互いに異なる値を有することができる。タイル又は地点の解像度又は数は、地図開発者により又は自動的に調整することができる。例えば、解像度がより微細になると、グリッド又はメッシュは、より多くのタイル又は地点を含むように調整又は変更することができ、解像度が低くなると、グリッド又はメッシュは、より少ないタイル又は点を含むように調整することができる。タイル又は地点の数の調整は、レイアウト及び／又は他の要素内の画像基準オブジェクトの数又は位置決めに基づくことができる。例えば、タイルのサイズは、少なくとも１つのナビゲート可能なタイルが現実世界の環境内の狭い又は最も狭い通路に適することができるように、人間又は歩行者のスケールに適合するように選択することができる。ルーティングのためにナビゲート可能なタイルを最も狭い又は最も小さいエリア、ホール、又は通路に置くことができるように、最大タイルサイズ（例えば、長さ及び／又は幅又は他の長さ、幅、寸法値及び／又は面積値において、最大でも約１５インチ、２０インチ又は３０インチ）を選び又は予め設定することができる。適切なタイル又はエリアサイズを選んで、レイアウトの一部の公的なエリア内でのルーティングの欠如又は不能を回避する。また、サイズが均一ではないタイル及び／又は形状を異なるエリアに使用することができる。例えば、より大きいエリアでは、より大きいサイズのタイルを使用することができ、より小さい又は狭いエリアでは、より細かい又はより小さいサイズのタイルを使用することができる。
【００４９】
局所的又は大域的地図座標が割り当てられ、又は指定される。例えば、タイルの中央部又はタイルの他の部分（又はアレイもしくはグリッドの先端又は点）には、（ｘ，ｙ）の緯度及び経度、或いは他の座標表示が与えられる。起点は、タイルの１つ（例えば、コーナタイル）に（０，０）すなわち原点を割り当てることによって選択される。座標は、基準画像オブジェクト、基準領域、又は他の特徴部を検索又は識別するのに使用することができ、又はその逆も同様である。しかしながら、ポイントツーポイントルーティングは、隣接タイル又は連続タイルに基づくことができ、従って、座標は、ルーティング計算には不必要な場合がある。或いは、座標は、ルートを計算するときに距離及びコスト決定に使用することができる。
【００５０】
地図６０１又は７００などのルーティング可能な地図をグリッド又はメッシュの関数に基づいて又はこれらの関数として生成又は作成する（ステップ８０９）。図９は、ステップ８０９により全体的又は部分的に包含することができるステップを含むルーティング可能な地図を生成する方法の実施例を示すフローチャートである。ナビゲート不可能なエリアをグリッド又はメッシュで指定する（ステップ９００）。例えば、地図開発者は、画像のレイアウト内のエリアをクリック又は選択して、ナビゲート不可能なタイル又はエリア４０１などナビゲート不可能なタイル又はエリアに変換する。地図開発者は、ナビゲート不可能なエリアとして現実世界では歩行で通り抜けることができない壁部又は障壁の画像を選択することができる。この選択により、ナビゲート不可能なステータスでタイルを割り当てることができ、又は、タイルを除去することができる。ナビゲート不可能なエリアの指定も自動化することができる。例えば、ナビゲート不可能である画像内の複数のエリアを選択するのではなく、地図開発者は、ナビゲート不可能である壁部又は障壁をクリック又は選択することができ、選択した壁部又は障壁の同じ又は類似した色又は画素レベルを有する全ての他の特徴部又は画像オブジェクトをナビゲート不可能なエリア又はタイルと自動的に関連付けることができる。或いは、グリッドが地図開発者又は他のエンティティの介入なしに重ね合わされると、所定の色又は画素レベル或いは画像認識要素を入力し、ナビゲート不可能なタイル又はエリアが自動的に生成されるようにすることができる。このように自動化された場合、レイアウト内でのテキストのグラフィック表現又は画像オブジェクトの記述は、ナビゲート不可能なエリアの指定前に除去又は分離することができる。これは、記述がナビゲート不可能なエリアとして誤って割り当てられ可能性があることに起因する。或いは、ナビゲート不可能なエリアは、ナビゲート不可能であることを意図したエリアにグリッド又はその一部を当初は適用しないことによって指定することができる。
【００５１】
複数の基準領域又はエリアを生成する（ステップ９０４）。基準領域の生成は、グリッド又はメッシュとは異なる空間層上で行われる。グリッド又はメッシュは、複数の基準領域を作成するときに表示することができ、又は表示されなくてもよい。一実施形態においては、複数の基準領域は、自動的又は半自動式に生成される。例えば、ラスタ画像又はベクタグラフィックス画像とすることができる画像２０１のような画像内で複数の基準画像オブジェクトが識別され又は求められる。レイアウトのラスタ画像は２値化される。画像の２値化は、複数の数字１及び０を用いてレイアウトを論理的に理解できるようにする。例えば、Ｔｉｅｒ-Ｔａｘｔ２値化が用いられる。Ｔｉｅｒ-Ｔａｘｔ２値化は、エッジ保存を可能にする。或いは、他の２値化技法又は方法を用いることができる。２値化は、シグマ、アクティビティ閾値及び刈り込み要素など、３つのパラメータ又は要素に依存することができる。或いは、より多くの又はより少ない要素を考慮することができる。
【００５２】
シグマは、雑音感度に対応することができる小さいシグマよりもむしろ大きいシグマである。画素でのアクティビティは、勾配の大きさの局所的平均値に比例することができ、アクティビティ閾値よりも低いアクティビティを有する画素は、ゼロに設定することができる。刈り込み要素は、接続された小さな構成要素を除去するのに使用される。一実施形態においては、シグマは約１に設定され、アクティビティ閾値は約２に設定され、刈り込み要素は約１に設定される。或いは、要素の値は、任意の他の値に設定することができ、調整可能とすることができる。
【００５３】
基準画像オブジェクトの識別に関して、テキスト／グラフィックス分離を２値化後に行う。例えば、基準画像オブジェクトの各々に対応するグラフィックス記述又はテキストは、それぞれの画像オブジェクトから分離される。任意の将来又は過去のグラフィック−テキスト分離を用いることができる。分離されたテキストは、それぞれの画像オブジェクトにリンクされ、又はこれにより識別される。例えば、テキスト領域は、基準画像オブジェクトの各々において指定することができる。分離後、グラフィックス記述の全て又は一部に対してＯＣＲを実施し、これらをテキスト５０４のような検索可能なテキストに、又は、テキストのグラフィック表現ではなく意味又は定義を有するものとして認識することができるテキストに変換する。グラフィックス記述の分離により、ＯＣＲを容易又は改善させることができる。或いは、ＯＣＲは分離なしで行うことができる。ＯＣＲを適用する前にＬａｎｃｚｏｓ再サンプリングを用いることによるなど、レイアウトの元の画像の解像度を２倍に又は増大させることによって、テキストエイリアシングを低減することができる。代替実施形態においては、他のテキスト認識方法、機能又はアルゴリズムを用いることができる。
【００５４】
基準領域５００のような複数の基準領域は、それぞれの基準画像オブジェクトに対応する境界又は境界線を形成することにより生成される。例えば、２値化及び／又はグラフィックス記述の分離後、基準画像オブジェクトがベクトル化される。線又はベクトルがデジタル又は２値化データ点間に生成又は作成され、レイアウト内の画像オブジェクトに対応する形状を形成する。例えば、Ｒｏｓｉｎ＆Ｗｅｓｔベクトル化アルゴリズムを用いる。或いは、他の将来又は過去のベクトル化アルゴリズムを用いてもよい。
【００５５】
閉じた多角形が、元の基準画像オブジェクトに関連した基準領域を求めるために識別される。例えば、ベクトル化に基づいて、閉じた多角形又は他の形状が求められる。閉じた多角形は、平面曲線、頂点、エッジ及び／又は面技法を介して求めることができる。任意の将来又は過去のコンピュータ幾何学アルゴリズム又は方法を用いることができる。閉じた多角形は、事務所、部屋又は他のエリアに対応することができる。
【００５６】
一部の基準画像オブジェクトは、ギャップ又はシンボル２４９及び２５３など、ドアのギャップ又はシンボルを含むことができる。基準領域を求める目的で、ベクトル化で識別された全ての線分について呼び出して、閉じた多角形を形成するために閉鎖することができるギャップを特定又は識別することができる。ギャップを閉鎖して、それぞれの基準領域を識別する。ドアのシンボルに関しては、地図開発者は、シンボル２５３のような固有のシンボルをドア、開口部、入口及び／又は出口にリンク付けする情報を識別又は提供することができる。この関連付けは、メモリ又はルックアップテーブル内に格納することができる。ベクトル化の間又はその後で、ドアのシンボルがマッチングに基づいて識別され、ギャップと置き換えることができる。次いで、ギャップを閉鎖してそれぞれの基準領域を識別する。或いは、線又はベクトルは、ギャップを形成した後にギャップを閉鎖するのではなく、ドアのシンボルと置き換わって多角形を閉鎖する。所与の画像オブジェクトに対する複数のドアのギャップ又はシンボルを呼び出し又は閉鎖して、閉じた多角形を形成し、基準領域を求めるようにすることができる。ドアのギャップ又はシンボルは、基準画像オブジェクトに対して別個の空間層にあるグリッド上のナビゲート可能なタイルに対応する。ドア又は開口部は、グリッドのナビゲート可能なタイルをそれぞれの基準領域と比較することによって推測することができる。
【００５７】
基準画像オブジェクトの各々に関連付けられた名前又はテキストは、生成された基準領域に対応する名前属性で実装される。例えば、ＯＣＲから生成されたテキストは、生成された基準領域のテキスト領域に関連付けられる。ルックアップテーブル、データベース、又は他のメモリ特徴部は、テキスト記述を各それぞれの基準領域にリンク付ける。地図開発者が生成されたテスト又は基準領域とのテキストの関連付けにおけるエラーを補正することができるように、質疑応答機構又は確認機能を実施することができる。基準領域は、関連テキストに基づいて検索可能とすることができ、その逆もまた可能である。
【００５８】
基準領域はまた、基準タイプと関連付けることもできる。例えば、各基準領域は、基準領域の関連するテキスト、関数、目的及び／又は他の要素に基づいて、レストラン、事務所、デパート、食料品店、浴室又は他の表示のようなタイプに対応し、又はこのようなタイプを指定することができる。これらのタイプ又はキーワードは、データベース又はルックアップテーブル内に格納することができ、それぞれの基準領域とリンク付け又は関連付けることができる。タイプ又はタグは、生成されたテキスト又は名前とは異なる場合もあれば、同じである場合もある店又はエリアの特定の名前（例えば、ＭｃＤｏｎａｌｄ（商標）レストラン）のような、より特定のものとすることができる。また、ロゴ及び／又はそれぞれのウェブサイトは、基準領域と関連付けることができる。基準領域は、１つ又はそれ以上のタイプ又はタグと関連付けることができ、タイプ又はタグに基づいて検索可能にすることができる。
【００５９】
基準領域及び関連するテキスト及びタイプは、自動的に生成される代わりに、或いはこれに加えて手作業で生成することができる。例えば、地図開発者は、プログラム又はアプリケーションツールを用いて、レイアウトの元の画像において基準画像オブジェクトのアウトラインを描き又はこれを複製し、グリッド又はメッシュと別個の空間層において基準領域（基準領域５００など）を生成することができる。また、地図開発者は、基準画像オブジェクトの元の記述を読むか又は表示し、更に、テキスト５０４などの等価テキスト及び／又は生成された基準領域と関連付けられるタイプに記入、入力、又は打ち込むことができる。
【００６０】
グリッド又はアレイ及び基準領域のようなデジタル公開エリア地図に関連付けられる生成されたデータ又はデータ層は、データベース１７０などに格納される。別個のデータ又は空間層は、個々のＸＭＬファイル又は他のデータとして格納することができる。例えば、基礎となる画像、グリッド及び基準領域に対応するデータが保存又は格納される。位置又は場所情報、或いはグリッド又はそれぞれのタイルに対応するデータ（規則的な大きさのタイルなど）、並びに基準領域もまた、データ構造内に保存及び／又は提供される。位置情報は、異なるデータエンティティの適切な場所に関する空間的基準として使用される。位置情報は、基礎となる画像に対してなど、元のスケール、基準又は座標に基づくことができる。データベース１７０は、別個のデータ層をコンパイルして、ルーティング可能な公開エリア地図を形成することができる。従って、データベース１７０は、コンパイルされた公開エリア地図データをエンドユーザデバイスにストリーミング又は送信することができる。或いは、別個のデータ層は、エンドユーザデバイス上のコンパイルのためにエンドユーザデバイスに送信することができる。また、コンパイルされた公開領域マップファイル又はデータは、別個のデータ層を格納するのではなく、データベース１７０内に格納することができる。
【００６１】
異なる空間又はデータ層をコンパイル又は組み合わせて、ルーティング可能な公開エリア地図６０１又は７００などの公開エリア地図を形成する（ステップ９０８）。例えば、関連テキスト及びタグを含む複数の基準領域は、グリッド又はメッシュと共にコンパイルされる。コンパイルすることにより、検索、ナビゲーション、ルーティング及び他の目的のために、それぞれのタイルが生成された基準領域にリンク付けされ、又はこれと関連付けられる（基準領域内にあるべきタイル、基準領域に実質的に隣接しているタイル、及び／又は基準領域の境界に接触又は交差しているタイルなど）。また、別個の空間層上で生成することができる接続部又は接続ポイントは、グリッド及び複数の基準領域と共にコンパイルすることができる。別個の又は異なる空間層上にあるとすることができる、制約事項又はコスト特徴部などの他の構成要素又は特徴はまた、グリッド又はメッシュと共にコンパイルすることもできる。任意の将来又は過去のコンパイル技法又は方法を用いることができる。また、異なる空間層をランタイム中に組み合わせることができる。或いは、グリッド、基準領域及び／又は接続ポイント、並びに他の特徴は、生成されて、異なる層ではなく同じ空間層又はデータ層上に存在することができる。従って、最終コンパイルを必要としないことがある。また、一部の空間層は、コンパイルすることができず。又は使用することができない。例えば、ルーティングは、生成された基準領域とタイルを関連付けることなく、ナビゲート可能なタイル及びナビゲート不可能なタイルを使用して達成することができる。
【００６２】
再度図８を参照し、画像２０１に類似した画像など、レイアウトの別の又は第２のグラフィック表現又は画像を取得する（ステップ８１３）。例えば、第２の画像は、建物の別のフロアの平面図画像とすることができる（例えば、ステップ８０１にて取得した画像は、建物のあるフロアを表し、ステップ８１３で取得した画像は、建物の別のフロアを表す）。第２の画像は、ステップ８０１で第１の画像を取得したのと同様の方法で、地図開発者が取得又は受け取ることができる。
【００６３】
別のグリッド、メッシュ又はアレイが、ステップ８０５でグリッドを適用するような、第２の画像に適用される（ステップ８１７）。別の又は第２のルーティング可能な地図は、ステップ８０９にて第１のルーティング可能な地図を生成するような、第２のグリッドに基づいて又はその関数として生成される（ステップ８２１）。１つ又はそれ以上の接続部又は他の特徴部を介してなど、第１及び第２のルーティング可能な地図は、互いにリンク付けされ又は関連付けられる（ステップ８２５）。例えば、第１のルーティング可能な地図における接続ポイントは、ルーティングを目的として第２のルーティング可能な地図上の接続ポイントと関連付けられる。接続ポイントは、接続ポイント６１３及び７０８のようなエレベータ接続部に対応し、或いは建物の２つのフロア又は他のエリアをリンク付けする他の接続部に対応することができる。或いは、１つ又は同じ接続ポイントを使用して２つのルーティング可能な地図をリンク付けする。１つ又はそれ以上の接続ポイント又は他の特徴部を介して、任意の数のルーティング可能な地図を共にリンク付けすることができる（例えば、建物の異なるフロア又は他のエリアに対応する１から第ｎ番目の数のルーティング可能な地図を生成し、共にリンク付け又は関連付けることができる）。
【００６４】
図１０は、公開エリア地図６０１又は７００などの公開エリア地図内でのルーティング方法のフローチャートである。より少ないか又はより多いステップ又は段階を設けることができ、ステップの組み合わせを設けることもできる。また、ステップ又は段階は、図示の順番で又は異なる順番で実行することができる。本方法は、本明細書で説明するシステム及び／又はデバイス、或いは異なるデバイス又はシステムによって実施される。
【００６５】
一実施形態においては、歩行者などのエンドユーザは、公開領域におけるポイントツーポイントルーティング又はナビゲーションのためにデバイス１１６のようなデバイスを使用する。例えば、公開エリア地図６０１又は７００などの１つ又はそれ以上のルーティング可能な公開エリア地図又はそのデータは、接続部１２０又は他の接続部などを介して、ユーザデバイスにダウンロード又は送信される。或いは、１つ又はそれ以上のルーティング可能な公開エリア地図又はそのデータは、場所又は位置に基づいて近接ビーコン又は送信器もしくは他のデバイスを介してユーザデバイス上に「プッシュされる」。
【００６６】
ユーザは、ディスプレイ１４０などを介して１つ又はそれ以上の公開エリア地図を見る。起点又は原点６０９のような原点を選択する（ステップ１００１）。例えば、ユーザは、ルーティングの開始場所としての役割を果たすエリア又は起始点を記入又は入力する。ユーザは、基準領域を記述する名前又はテキストを入力することができ、公開エリア地図におけるそれぞれのエリアは、或いは基準領域を名前又はテキストとリンク付けするルックアップテーブルへのサーチ又はアクセスに基づいて原点として配分することができる。或いは、ユーザは、公開エリア地図上のエリアをクリック、又は選択、或いは物理的に接触して（すなわち、表示画面に接触して）原点を選ぶことができる。
【００６７】
公開エリア地図で選択された起点を識別する（ステップ１００５）。例えば、原点と関連付けられた１つ又はそれ以上のタイル、又は原点と関連付けられた基準領域が、ルート計算のために特定、検討、認識、ターゲット化、重点化、及び／又は強調表示される。
【００６８】
目的地又は目的地点７１２などの目的地点（すなわち、ユーザがルーティングを望む場所又はエリア）が、原点選択と同様の方法又は異なる方法でユーザにより選択される（ステップ１００９）。公開エリア地図において選択された目的地が、原点を識別するのと同様の方法で又は異なる方法で識別される（ステップ１０１３）。
【００６９】
公開エリア地図内において選択された起点から選択された目的地までのルートを計算する（ステップ１０１７）。例えば、タイル３０４のようなナビゲート可能な隣接又は接続タイルにアクセスし、原点から目的地点までの最適又は好適なルートを求める。タイル４０１などのナビゲート不可能なエリア又はタイルは回避又は迂回される。幾何学的及び／又は数学的関数又はアルゴリズムを用いて１つ又はそれ以上の可能なルートを計算することができる。例えば、タイルの各々の中心部又は他の場所を互いに接続又は関連付けて、可能性のあるルートを形成する。距離に基づいて、並びにコスト、制約事項、又は入力することができるユーザ優先度のような他の要素に基づいて最適ルートが選択される（例えば、ユーザは、所望のエリアを回避又は通過するルートを望むことができる）。ユーザ優先度は、タイルの分類又は下位分類に基づくことができる。例えば、各タイル又は一部のタイルは、エリアの位置、場所及び／又はタイプに関係する特徴部（例えば、主要な、中間の、又は小さい通路、廊下、経路又はエリア、交通量の多い又は少ないエリア、人気のないエリア又は人気のあるエリア、風致地区、狭いエリア、孤立したエリア、傾斜エリア、平坦エリア、絨毯敷エリア、或いはエリアのサイズ、長さ又は幅）と関連付けられる。タイルはまた、どの基準領域又は基準エリアがリンク付けされ、近接し、又は通過するかに基づいて下位分類することができる。下位分類に基づいて異なるタイルをランク付けし、又は整序することができる。一実施形態においては、ユーザは、ルーティング時に交通量の多いエリア又は主要な通路を回避するように入力又は選択することができる。
【００７０】
ダイクストラ法、Ａスターアルゴリズム又は検索、及び／又は他のルート探索又は計算アルゴリズムを用いて、接続タイルの地点間で線、曲線又はルートを形成することができる。Ｄｏｕｇｌａｓ−Ｐｅｕｃｋｅｒ法又はアルゴリズムを用いて、計算された線又はルートを平滑化又は簡素化することができる。例えば、隣接タイルの中央部を共に接続することにより、ジャギー、先鋭、又は三角形のエッジを原点から目的地点までのルート内で形成することができる。距離を最小限に抑えてルートの平滑な線又は曲線を提供するために、Ｄｏｕｇｌａｓ−Ｐｅｕｃｋｅｒアルゴリズムは、原点から目的地までの平均化ルートを発見又は提供することができる。Ｄｏｕｇｌａｓ−Ｐｅｕｃｋｅｒアルゴリズムは、ナビゲート不可能なタイルを回避するように修正され、線平滑化又は平均化のため閾値レベルを変更するように調整することができる。或いは、他の線平滑化アルゴリズム又は方法を用いることができる。
【００７１】
算出ルート及び生成経路は、将来の使用に備えて保存又は格納することができる。例えば、経路が生成されると、この経路は所定の経路として保存することができ、ユーザが同じ原点から同じ目的地までルーティングすることを望む場合に再利用することができる。全てではなく一部の経路又はルートを保存することができる。例えば、主要又は人気のある基準領域間のルート又は経路を格納することができ、他方、通行量が少ない又は小さい基準領域に関する経路は保存することができない。また、経路全体ではなく、経路の一部が保存される部分的なルート又は経路を格納することができる。加えて、接続部又は接続ポイント間のルート又は経路は、ルーティングのために予め計算し、又は予め設定し且つ格納することができる。例えば、ユーザは、ある地点から１つ又はそれ以上の接続部を使用することができる別の地点までルーティングすることを望む場合がある。この場合、ルートは、原点から接続部まで並びに他の接続部から目的地まで計算され、接続部間のルートは既に計算済みであり、これによって時間及び処理が節約される。ルートは、複数のデータ層に格納、保存、ランク付け、又は整序することができる。例えば、上位層は、主要な、大きな、又はより重要なルートを含むことができる。或いは、ルート及び経路は、常に再計算及び再生成される。
【００７２】
ルートの計算に基づいて、選択された原点から選択された目的地までの経路を生成する（ステップ１０２１）。１つ又はそれ以上のルートの計算及び選択の間又はその後で、最適又は好適なルートに関連したタイルの全てが経路として識別又は求められる。例えば、Ｄｏｕｇｌａｓ−Ｐｅｕｃｋｅｒアルゴリズム又は他のアルゴリズムは、特定のナビゲート可能なタイルを通り過ぎる線及び／又は曲線を形成することができる。次いで、これらのタイルは、ユーザが原点から目的地点まで辿り着く経路として識別、入力、格納、又は強調表示される。その後、求められた経路は、ルーティングを目的として、表示された経路６０５又は７０４のように公開エリア地図においてユーザに表示される。
【００７３】
一実施形態においては、ユーザは、ルーティング及び／又はナビゲーション用に公開エリア地図を使用するときに区分データを受信することができる。デバイス１１６などのユーザデバイスは、処理速度、メモリ又は他の特徴が他のデバイス程高く、高速で、又は大きくない場合があるリソース制約構成部品を含むことができる。従って、同時に複数の公開エリア地図に関連した全データをダウンロード又は実行するのではなく、必要に応じてデータを受信又は実行することができる。例えば、ユーザは、ナビゲーションを開始するときに、１つの公開エリア地図又はその一部をダウンロード又は開始することができる（例えば、ルーティングのために１階又は原点を含む１階の一部が、表示又は取り込まれる）。次いで、ユーザが接続部又は接続ポイントを入力し、又はルーティングされると（例えば、２階又は他のフロア又はエリアに行くために）、次いで、接続された公開エリア地図データがルーティングプロセスを続行するためにダウンロード又は開始される。また、公開エリア地図の異なる空間層又は特徴部は、区分化状態で又は異なる時間にダウンロード又は実行することができる。
【００７４】
上述の公開エリア地図は、車載ナビゲーションシステム、携帯型ナビゲーションデバイス、現実世界の車両ナビゲーション地図、及び／又は現実世界の歩行者ナビゲーション地図で使用されるような収集されて地理的データベースに編成される、ナビゲーション関係の属性又はノード及び道路又は経路セグメントを含むことができ、又は含まれない場合もある。ナビゲーション属性としては、転回制約コンテンツ、速度制限情報、最適又は一般的経路データ、歩道コンテンツ、標識情報、及び／又は、ルート計算、目的地時間計算、ルート案内及び／又は他の現実世界のナビゲーション機能などナビゲーション関係機能を実行するための他の属性を挙げることができる。
【００７５】
公開エリア地図は、収集されて編成されたナビゲーション属性及び／又はノード及びリンク又は道路／経路セグメントをベースとする又はこれらを含む現実世界の車両及び／又は歩行者地図又は地図データと接続され、又は通信することができる。例えば、建物のフロア、建物の公開エリア地図、又は他の公開エリア地図は、ルーティング及びナビゲーションを目的として道路網地図に接続することができる。ユーザは、建物フロア内でルーティングするデバイスを使用して、ユーザをエリア２０５（図２）のような外側エリアにナビゲートすることができる。ユーザが外側エリアに達すると、ユーザは、設定された道路網を使用して市街又は他の場所の別の部分にナビゲートすることを望むことができる。ユーザのデバイス又はユーザのデバイスと通信することができるデバイスは、道路網に関してナビゲート関係機能を実行する車両ナビゲート地図を実行、呼び出し、又は表示することができる。収集された属性に基づいた公開エリア地図及びナビゲーション地図又はデータのあらゆる組み合わせは、ルーティング及び／又はナビゲーションを目的として互いに接続することができる。
【００７６】
（代替形態）
上記の説明においては、ルーティングに使用される公開エリア地図は、建物フロア又は平面図を中心とするものである。しかしながら、記載の特徴は、多数の公開領域に使用することができる。例えば、公園及び屋外環境のレイアウトの画像を取得して、上述のように、ルーティング可能な地図を生成するのに使用することができる。ピクニック場、ジャングルジム、滑り台、トイレ及び他のエリアのような公園の異なるセクションは、別個の基準領域として定義することができる。従って、ルーティングは、上述の事務所間のルーティングと同様に、草で覆われたエリア全体に生成することができる。公園は、ルーティングに組み込むことができる散歩道を有する場合がある。或いは、所定の散歩道又はルートは、ルーティングにおいて回避することができる。また、ナビゲート不可能なタイルは、境界又は障壁用に使用又は実装することができる。例えば、公園内の湖、池又は他の水域は、水中を通ってルーティングされないように、ナビゲート不可能なタイルで境界付けることができる。危険エリア、列車軌道又は岩などの他の障壁又は所望の境界線をナビゲート不可能なタイルと関連付けることができる。或いは、ナビゲート可能なタイルは、これらの境界線の一部を通過する理由がある場合に使用することができる。例えば、湖の一方の側から反対の側に人を連れて行くためにボートが存在する場合、ボートエリアは、ナビゲート可能なタイルと関連付けることができる。
【００７７】
公園又は外側エリアの画像に関連したタイル又はオブジェクトは下位分類することができる。例えば、一部のタイルは、草エリアと関連付けることができ、一部のタイルは、歩道と関連付けることができる。ユーザ又は他のエンティティは、ルーティングを目的として草のみ、歩道のみ又は他の指定などの優先度を入力することができる。従って、特定の指定されたタイルタイプを回避又は使用する（例えば、草エリアのみにわたるルートを生成して歩道を回避する、又はその逆）ことによりルートを生成することができる。
【００７８】
別の実施形態においては、駐車場の既存画像を取得して、ルーティング可能な公開エリア地図を生成するのに使用することができる。個々の駐車スペースの各々は、異なる基準領域に対応することができる。駐車スペースのアウトラインは、ナビゲート不可能なタイルと関連付けることができる又は関連付けることができない障壁と考えることができる。例えば、駐車スペースのアウトラインは、ルートが駐車スペースを通って生成されるように（例えば、空間が車で満たされる可能性があるので、歩行者、自転車利用者、又は他者の安全確保のため、更に実用性が得られるように）ナビゲート不可能なエリアとして指定することができる。しかしながら、駐車スペースのアウトラインの特定のエリアは、ナビゲート可能として指定し、歩行者が駐車中の車の間を歩く又はナビゲートすることができるという概念をシミュレートすることができる。駐車場は、複数のレベルの駐車フロアを有する場合があり、複数のレベルの駐車フロアは、エレベータ、階段、又は他の接続部を表す、接続部４０５、６１３又は７０８のような接続部を介して互いに関連付けることができる。
【００７９】
他のエリア又は環境を使用して、ルーティング可能な公開エリア地図を生成することができる。例えば、遊園地、モール、博物館及び他の屋内エリア又は屋外エリアの既存画像を取得して、ルーティング可能な地図又は図面を生成するのに使用することができる。一実施形態においては、展示会エリア又は平面図又は他の一時レイアウトの画像を取得することができる。例えば、展示会のレイアウト設定は、わずか約１週間、約３ヵ月足らず、又は他の時間期間にわたって存続し又は存在する場合がある。一時レイアウトの画像を取得して、上述のようにルーティング可能な公開エリア地図を生成するのに使用することができる。従って、特定の時間期間（約３ヵ月足らず又は他の一時的な時間期間）の後、生成したルーティング可能な地図は、その場所又はエリアにはもはや適用可能ではないであろう。また、生成した公開エリア地図は、一時レイアウトの時間期間に基づいて時間期限を定めることができる。例えば、基準領域又は他の特徴部などの公開エリア地図或いはその一部は、実際のレイアウトが配分された時間期間後に変更又は削除されたときに、消失、削除、又は動作不能とすることができる。公開エリア地図又はその特徴は、デバイス内のタイマー又は外部筋からの通信又は信号に基づいて実行デバイスにより削除することができる。また、特定の基準領域に関連した事象又は特徴は、時間期限を定めるか、又は、特定の基準領域を時間期限を定めるのに使用することができる。例えば、演説、ショー又はアクティビティは、特定の時間期間にわたって指定エリア（例えば、基準領域）で行うことができる。従って、基準領域は、演説、ショー又はアクティビティに関連した特定の時間期間にわたってルーティングのみ可能であるか、又は存在することのみ可能となる。別の代替実施形態においては、基準領域は、移動トラック又は移動店舗など移動可能なものとすることができ、これによって、特定の場所において基準領域が一時的なものになる。或いは、基準領域は、所与の基準領域、店舗、又は売店において商品がどのくらいの期間販売されているかに基づいて、一時的な時間期間にわたってルーティング可能とすることができる。
【００８０】
上記説明においては、グリッド又はメッシュの適用は、これに限定するものではないが、２次元フォーマットを中心としたものである。グリッド又はメッシュは、ｘ、ｙ及びｚ方向の点又は座標を含む３次元グリッド又はメッシュとすることができる（例えば、座標は、経度、緯度、高度情報又は局所座標を含むことができる）。例えば、取得されたレイアウトの画像は、３次元特徴部を含むことができる。例えば、平面図は、フロア傾斜路、段部又は階段、２階構造エリア、又は３次元空間で表示又は指定される他の特徴部を有することができる。また、公園エリア内で丘又は最高点及び谷は、３次元空間で表示又は提供することができる。従って、３次元グリッド又はメッシュは画像上又はこれを覆って適用して、上述のようにルーティング可能な公開エリア地図を生成することができる。ｚ方向の追加は、ルート及び／又は経路を求めるための付加的な計算を必要とする可能性がある。例えば、高さは、最適又は好適なルートを求める際の要素とすることができる。方形タイルを使用する代わりに、三角形セクション又はタイルを３次元グリッド又はメッシュに使用することができる。或いは、他の幾何学的形状を利用することができる。
【００８１】
３次元グリッド又はメッシュは、ある人がオブジェクトを見つける助けとなるのに加えて、ある地点から別の地点に人をルーティングするのに使用することができる。例えば、製品及び商品の垂直方向の棚を有する食料品店又は小売店舗のレイアウトの画像を取得することができる。フロアエリアが２次元又は３次元のタイルと重ね合わされて、垂直棚エリアがグリッド又はメッシュと重ね合わされる３次元グリッドを適用することができる。棚上の異なる製品又は商品は、基準領域として指定することができる。従って、買い物客又はユーザを店内のある場所から、近接又は近隣の棚上で製品を見つけることができる別の場所にルーティングすることができる公開エリア地図を生成することができる。次いで、ルートは、指定の又は選択された製品を指し示す棚又は垂直エリアにわたるグリッドに基づいて計算することができる。買い物客又はユーザは、棚の上を歩くことができないが、ルートは、買い物客又はユーザに正確にその製品が棚の上のどこにあるかを示す際に有用とすることができる。或いは、ルートは、棚に最も近い地面又はフロアタイルで終了するように計算することができる。
【００８２】
別の実施形態においては、上述したように、グリッド、メッシュ又はアレイを使用する代わりに及び／又はこれらを使用することに加えて、色を用いてナビゲート可能なエリア及びナビゲート不可能なエリアを指定することができる。例えば、白色は、ナビゲート可能なエリアと関連付けることができ、黒色は、ナビゲート不可能なエリアと関連付けることができる。任意の数及びタイプの色を用いることができる。従って、ルートは、それぞれのナビゲート可能な色及びナビゲート不可能な色の配置に基づいて計算することができる。例えば、経路又はルートは、距離アルゴリズムに基づいて、ナビゲート可能な色が付いたエリア内で及びナビゲート不可能な色が付いたエリアの回りに生成することができる。また、ルートを計算又は生成するための要素又はコストとして、色の異なる色合い又は色のグラデーションを使用することができる。
【００８３】
更に、上述のように、地図開発者は、画像を取得して、ワークステーション、コンピュータ及び／又は、デバイス１１２などのデバイスを使用し、ルーティング可能な公開エリア地図を生成する。次いで、公開エリア地図は、エンドユーザにより、又はユーザデバイス１１６などのエンドユーザデバイスで受信される。しかしながら、地図開発者とは別個のユーザ又は他のエンティティは、レイアウトの画像を取得して（例えば、エンドユーザは、デバイス１１２又は１１６の一部であるか又は一部ではない場合があるカメラを介してレイアウトの写真を撮ることができ、或いは、エンドユーザは、画像ソース１０４を介して画像を取得することができる）、ルーティング可能な公開エリア地図を自動的に及び／又は手作業で生成することができる。例えば、エンドユーザは、地図開発者又は他のエンティティから公開エリア地図を作成するソフトウェアアプリケーションを取得及び／又は購入することができる。デバイス１１２（図１）は、パーソナルコンピュータなどのエンドユーザにより操作することができる。或いは、デバイス１１２を使用してルーティング可能な公開エリア地図を生成し、公開エリア地図を使用するためにユーザデバイス１１６に送るのではなく、ユーザデバイス１１６を使用して、ルーティング可能な公開エリア地図を生成及び使用することができ、デバイス１１２は迂回される。或いは、デバイス１１２及びデバイス１１６を１つのデバイス又はシステムに組み合わせることができる。
【００８４】
上述のプロセス、方法及び／又は技法を実施するロジック、ソフトウェア、又は命令は、キャッシュ、バッファ、ＲＡＭ、取り外し可能媒体、ハードドライブ、他のコンピュータ可読記憶媒体又はあらゆる他の有形媒体といった、コンピュータ可読記憶媒体又はメモリ、或いは他の有形媒体上で提供される。有形媒体としては、様々なタイプの揮発性及び不揮発性記憶媒体が含まれる。図中で例示され又は本明細書で説明される機能、段階、ステップ又はタスクは、コンピュータ可読記憶媒体内又はその上に格納されたロジック又は命令の１つ又はそれ以上のセットに応答して実行される。機能、段階又はタスクは、特定のタイプの命令セット、記憶媒体、プロセッサ又は処理ストラテジーから独立したものであり、単独で又は組み合わせ動作する、ソフトウェア、ハードウェア、集積回路、ファームウェア、マイクロコードなどにより実行することができる。同様に、処理ストラテジーには、多重プロセッシング、マルチタスキング、並行処理を挙げることができる。一実施形態においては、命令は、ローカル又はリモートシステムにより読み込むために取り外し可能媒体デバイス上に格納される。他の実施形態においては、ロジック又は命令は、コンピュータネットワーク又は他の電話回線を介した転送のために遠隔場所に格納される。更に他の実施形態においては、ロジック又は命令は、所与のコンピュータ、中央処理ユニット（「ＣＰＵ」）、グラフィックス処理ユニット（「ＧＰＵ」）又はシステム内に格納される。
【００８５】
上記の詳細な説明は限定ではなく例証とみなされるものとし、全ての均等物を含む添付の請求項は本発明の範囲を定めることが意図される。
【符号の説明】
【００８６】
１００ システム
１０４ 画像ソース
１０８ ネットワーク
１１２ デバイス
１１６ ユーザデバイス
１２０ ネットワーク又は接続部
１２４ ディスプレイ
１２８ プロセッサ
１３２ メモリ
１３４ アプリケーション
１３６ 入力デバイス
１４０ ディスプレイ
１４４ プロセッサ
１４８ メモリ
１７０ データベース
１８０ ネットワーク
【特許請求の範囲】
【請求項１】
公開エリア地図を生成する方法であって、
人が動き回る現実世界のエリアを表すレイアウトの画像を取得する段階と、
前記画像の地上エリアを埋めるタイルを含むグリッドを前記画像に適用する段階と、
前記グリッドの関数としてルーティング可能な地図を生成する段階と、
を含み、
前記ルーティング可能な地図が、前記レイアウト内でポイントツーポイントルーティングを行うように構成されることを特徴とする方法。
【請求項２】
前記レイアウトの画像が建物平面図の画像を含む、請求項１に記載の方法。
【請求項３】
前記ルーティング可能な地図を生成する段階が、
前記グリッドに対応するナビゲート不可能なエリアを指定する段階と、
複数の基準領域を生成する段階と、
前記複数の基準領域を前記グリッドとコンパイルする段階と、
を含む、請求項１に記載の方法。
【請求項４】
前記複数の基準領域を生成する段階が、
前記画像内に複数の基準画像オブジェクトを識別する段階と、
前記それぞれの基準画像オブジェクトに対応する境界を形成することによって、前記複数の基準領域を生成する段階と、を含む請求項３に記載の方法。
【請求項５】
前記境界を形成する段階が２値化画像の一部をベクトル化する段階を含む、請求項４に記載の方法。
【請求項６】
前記境界がナビゲート不可能なタイルと関連付けられる、請求項４に記載の方法。
【請求項７】
前記境界が、除去されたタイルと関連付けられる、請求項４に記載の方法。
【請求項８】
前記複数の基準領域内のタイルが、前記それぞれの基準領域にリンク付けされる、請求項３に記載の方法。
【請求項９】
前記グリッド及び前記複数の基準領域が、コンパイル前に別個の空間層内にある、請求項３に記載の方法。
【請求項１０】
前記タイルが実質的に均一である、請求項１に記載の方法。
【請求項１１】
前記ポイントツーポイントルーティングが、接続されたタイルを介して経路を生成する、請求項１に記載の方法。
【請求項１２】
公開エリア地図平面図を生成する方法であって、
建物のフロアについての現実世界のフロアレイアウトに対応する、第１の平面図の第１のグラフィック表現を取得する段階と、
第１のグリッドを前記第１のグラフィック表現に適用する段階と、
前記第１のグリッドの関数として第１のルーティング可能な平面図を生成する段階と、
を含み、
前記第１のルーティング可能な平面図が、ポイントツーポイントルーティングを行うように構成されることを特徴とする方法。
【請求項１３】
前記建物の別のフロアについての現実世界のフロアレイアウトに対応する、第２の平面図の第２のグラフィック表現を取得する段階と、
第２のグリッドを前記第２のグラフィック表現に適用する段階と、
前記第２のグリッドの関数として第２のルーティング可能な平面図を生成する段階と、
接続ポイントを介して前記第１のルーティング可能な平面図と前記第２のルーティング可能な平面図とをリンク付けする段階とを更に含む、請求項１２に記載の方法。
【請求項１４】
前記接続ポイントが、エレベータ、階段吹き抜け又はエスカレータを表す、請求項１３に記載の方法。
【請求項１５】
公開エリア地図においてルーティングする方法であって、
人が動き回る現実世界のエリアを表すレイアウトの画像を含む前記公開エリア地図において選択された目的地を識別する段階と、
基礎となるグリッドを更に含む前記公開エリア地図において原点から前記選択された目的地までのルートを計算する段階と、
前記計算に基づいて前記原点から前記選択された目的地までの経路を生成する段階と、
を含み、
前記経路が前記基礎となるグリッドの接続されたタイルを介して生成されることを特徴とする方法。
【請求項１６】
前記接続されたタイルの各々が、ほぼ１ｍ2の面積に対応するサイズを有する、請求項１５に記載の方法。
【請求項１７】
前記接続されたタイルが、接続ポイントを介してリンク付けされるタイルを含む、請求項１５に記載の方法。
【請求項１８】
前記ルートを計算する段階が、Ｄｏｕｇｌａｓ−Ｐｅｕｃｋｅｒ法を用いる段階を含む、請求項１５に記載の方法。
【請求項１９】
前記選択目的地が、前記レイアウトの画像においてあらゆる基準領域を含む、請求項１５に記載の方法。
【請求項２０】
公開エリア地図を生成する方法であって、
地図画像を受信する段階と、
前記地図画像上で格子図形を提供するメッシュを前記地図画像に重ね合わせる段階と、
前記地図画像において複数の基準オブジェクトを識別する段階と、
前記それぞれの基準オブジェクトのアウトラインを描く境界を形成することによって複数の基準領域を生成する段階と、
前記複数の基準領域を前記メッシュとコンパイルすることによりルーティング可能な地図を生成する段階とを含み、
前記ルーティング可能な地図が、前記コンパイルされたメッシュに基づいて前記複数の基準領域のいずれかを起点及び終点としてルーティングを行うように構成されることを特徴とする方法。
【請求項２１】
前記複数の基準領域が建築フロアの部屋を表す、請求項２０に記載の方法。
【請求項２２】
前記境界が壁部に対応する、請求項２０に記載の方法。
【請求項２３】
前記メッシュが３次元グリッドを含む、請求項２０に記載の方法。
【請求項２４】
前記地図画像が建物フロアの一時レイアウトに対応し、前記一時レイアウトが約３ヵ月未満にわたって現実世界に存在する、請求項２０に記載の方法。
【請求項２５】
公開エリア地図を生成する方法を実行するコンピュータ実行可能命令を含むコンピュータ可読記憶媒体であって、前記方法が、
人が動き回る現実世界のエリアを表すレイアウトに関する、壁部を含む既存画像を取得する段階と、
前記既存画像を使用して連続したタイルのグリッドを形成する段階とを含み、
前記グリッドが、前記現実世界のエリア内の歩行者アクセス可能な連続サブエリアに対応する形状を有し、
前記形状が、前記既存画像内の前記壁部に対応する境界線を有する、ことを特徴とする方法。
【請求項２６】
ルーティングソフトウェアアプリケーションによって使用されて第１の場所と第２の場所との間でルートを求めることができるエリアのデジタル地図を作成する方法であって、
前記エリアの画像を規則的な大きさのタイルのグリッドと重ね合わせる段階と、
前記画像のナビゲート可能な部分を重ね合わせる各タイルを、前記画像の別のナビゲート可能な部分を重ね合わせる直近の別のタイルまでの移動を可能にする特性と関連付ける段階と、
前記タイル及び対応する場所の表現を含むデータファイルを前記エリアのデジタル地図として格納する段階とを含む方法。
【請求項２７】
第１の場所と第２の場所との間でルートを求めるためにルーティングソフトウェアアプリケーションにより使用することができるエリアのデジタル地図を作成する方法であって、
前記エリアの画像を規則的な大きさのタイルのグリッドと重ね合わせる段階と、
各タイルを複数のナビゲート可能な特性から選択されたナビゲート可能な特性と関連付ける段階であって、前記タイルのナビゲート可能な特性が、重ね合わされた前記画像の当該部分から引き継がれ、且つ前記ナビゲート可能な特性が、直近の別のナビゲート可能なタイルに(i)ナビゲート不可能であること及び(ii)ナビゲート可能であることを含む当該段階と、更に、
前記タイル、対応する場所、及びこれに関連した前記ナビゲート可能な特性の表現を含むデータファイルを前記エリアのデジタル地図として格納する段階を含むことを特徴とする方法。
【請求項２８】
コンピュータ可読媒体上に格納されているエリアのデータ表現であって、
規則的な大きさのタイルのグリッドを表し、前記タイルの各々の位置を示すデータを含むデータ構造と、
前記エリアの関連画像とを備え、
前記タイルの位置が前記画像内のエリアのナビゲート可能な部分に対応することを特徴とするデータ表現。
【請求項１】
公開エリア地図を生成する方法であって、
人が動き回る現実世界のエリアを表すレイアウトの画像を取得する段階と、
前記画像の地上エリアを埋めるタイルを含むグリッドを前記画像に適用する段階と、
前記グリッドの関数としてルーティング可能な地図を生成する段階と、
を含み、
前記ルーティング可能な地図が、前記レイアウト内でポイントツーポイントルーティングを行うように構成されることを特徴とする方法。
【請求項２】
前記レイアウトの画像が建物平面図の画像を含む、請求項１に記載の方法。
【請求項３】
前記ルーティング可能な地図を生成する段階が、
前記グリッドに対応するナビゲート不可能なエリアを指定する段階と、
複数の基準領域を生成する段階と、
前記複数の基準領域を前記グリッドとコンパイルする段階と、
を含む、請求項１に記載の方法。
【請求項４】
前記複数の基準領域を生成する段階が、
前記画像内に複数の基準画像オブジェクトを識別する段階と、
前記それぞれの基準画像オブジェクトに対応する境界を形成することによって、前記複数の基準領域を生成する段階と、を含む請求項３に記載の方法。
【請求項５】
前記境界を形成する段階が２値化画像の一部をベクトル化する段階を含む、請求項４に記載の方法。
【請求項６】
前記境界がナビゲート不可能なタイルと関連付けられる、請求項４に記載の方法。
【請求項７】
前記境界が、除去されたタイルと関連付けられる、請求項４に記載の方法。
【請求項８】
前記複数の基準領域内のタイルが、前記それぞれの基準領域にリンク付けされる、請求項３に記載の方法。
【請求項９】
前記グリッド及び前記複数の基準領域が、コンパイル前に別個の空間層内にある、請求項３に記載の方法。
【請求項１０】
前記タイルが実質的に均一である、請求項１に記載の方法。
【請求項１１】
前記ポイントツーポイントルーティングが、接続されたタイルを介して経路を生成する、請求項１に記載の方法。
【請求項１２】
公開エリア地図平面図を生成する方法であって、
建物のフロアについての現実世界のフロアレイアウトに対応する、第１の平面図の第１のグラフィック表現を取得する段階と、
第１のグリッドを前記第１のグラフィック表現に適用する段階と、
前記第１のグリッドの関数として第１のルーティング可能な平面図を生成する段階と、
を含み、
前記第１のルーティング可能な平面図が、ポイントツーポイントルーティングを行うように構成されることを特徴とする方法。
【請求項１３】
前記建物の別のフロアについての現実世界のフロアレイアウトに対応する、第２の平面図の第２のグラフィック表現を取得する段階と、
第２のグリッドを前記第２のグラフィック表現に適用する段階と、
前記第２のグリッドの関数として第２のルーティング可能な平面図を生成する段階と、
接続ポイントを介して前記第１のルーティング可能な平面図と前記第２のルーティング可能な平面図とをリンク付けする段階とを更に含む、請求項１２に記載の方法。
【請求項１４】
前記接続ポイントが、エレベータ、階段吹き抜け又はエスカレータを表す、請求項１３に記載の方法。
【請求項１５】
公開エリア地図においてルーティングする方法であって、
人が動き回る現実世界のエリアを表すレイアウトの画像を含む前記公開エリア地図において選択された目的地を識別する段階と、
基礎となるグリッドを更に含む前記公開エリア地図において原点から前記選択された目的地までのルートを計算する段階と、
前記計算に基づいて前記原点から前記選択された目的地までの経路を生成する段階と、
を含み、
前記経路が前記基礎となるグリッドの接続されたタイルを介して生成されることを特徴とする方法。
【請求項１６】
前記接続されたタイルの各々が、ほぼ１ｍ2の面積に対応するサイズを有する、請求項１５に記載の方法。
【請求項１７】
前記接続されたタイルが、接続ポイントを介してリンク付けされるタイルを含む、請求項１５に記載の方法。
【請求項１８】
前記ルートを計算する段階が、Ｄｏｕｇｌａｓ−Ｐｅｕｃｋｅｒ法を用いる段階を含む、請求項１５に記載の方法。
【請求項１９】
前記選択目的地が、前記レイアウトの画像においてあらゆる基準領域を含む、請求項１５に記載の方法。
【請求項２０】
公開エリア地図を生成する方法であって、
地図画像を受信する段階と、
前記地図画像上で格子図形を提供するメッシュを前記地図画像に重ね合わせる段階と、
前記地図画像において複数の基準オブジェクトを識別する段階と、
前記それぞれの基準オブジェクトのアウトラインを描く境界を形成することによって複数の基準領域を生成する段階と、
前記複数の基準領域を前記メッシュとコンパイルすることによりルーティング可能な地図を生成する段階とを含み、
前記ルーティング可能な地図が、前記コンパイルされたメッシュに基づいて前記複数の基準領域のいずれかを起点及び終点としてルーティングを行うように構成されることを特徴とする方法。
【請求項２１】
前記複数の基準領域が建築フロアの部屋を表す、請求項２０に記載の方法。
【請求項２２】
前記境界が壁部に対応する、請求項２０に記載の方法。
【請求項２３】
前記メッシュが３次元グリッドを含む、請求項２０に記載の方法。
【請求項２４】
前記地図画像が建物フロアの一時レイアウトに対応し、前記一時レイアウトが約３ヵ月未満にわたって現実世界に存在する、請求項２０に記載の方法。
【請求項２５】
公開エリア地図を生成する方法を実行するコンピュータ実行可能命令を含むコンピュータ可読記憶媒体であって、前記方法が、
人が動き回る現実世界のエリアを表すレイアウトに関する、壁部を含む既存画像を取得する段階と、
前記既存画像を使用して連続したタイルのグリッドを形成する段階とを含み、
前記グリッドが、前記現実世界のエリア内の歩行者アクセス可能な連続サブエリアに対応する形状を有し、
前記形状が、前記既存画像内の前記壁部に対応する境界線を有する、ことを特徴とする方法。
【請求項２６】
ルーティングソフトウェアアプリケーションによって使用されて第１の場所と第２の場所との間でルートを求めることができるエリアのデジタル地図を作成する方法であって、
前記エリアの画像を規則的な大きさのタイルのグリッドと重ね合わせる段階と、
前記画像のナビゲート可能な部分を重ね合わせる各タイルを、前記画像の別のナビゲート可能な部分を重ね合わせる直近の別のタイルまでの移動を可能にする特性と関連付ける段階と、
前記タイル及び対応する場所の表現を含むデータファイルを前記エリアのデジタル地図として格納する段階とを含む方法。
【請求項２７】
第１の場所と第２の場所との間でルートを求めるためにルーティングソフトウェアアプリケーションにより使用することができるエリアのデジタル地図を作成する方法であって、
前記エリアの画像を規則的な大きさのタイルのグリッドと重ね合わせる段階と、
各タイルを複数のナビゲート可能な特性から選択されたナビゲート可能な特性と関連付ける段階であって、前記タイルのナビゲート可能な特性が、重ね合わされた前記画像の当該部分から引き継がれ、且つ前記ナビゲート可能な特性が、直近の別のナビゲート可能なタイルに(i)ナビゲート不可能であること及び(ii)ナビゲート可能であることを含む当該段階と、更に、
前記タイル、対応する場所、及びこれに関連した前記ナビゲート可能な特性の表現を含むデータファイルを前記エリアのデジタル地図として格納する段階を含むことを特徴とする方法。
【請求項２８】
コンピュータ可読媒体上に格納されているエリアのデータ表現であって、
規則的な大きさのタイルのグリッドを表し、前記タイルの各々の位置を示すデータを含むデータ構造と、
前記エリアの関連画像とを備え、
前記タイルの位置が前記画像内のエリアのナビゲート可能な部分に対応することを特徴とするデータ表現。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１０−４４３９２（Ｐ２０１０−４４３９２Ａ）
【公開日】平成２２年２月２５日（２０１０．２．２５）
【国際特許分類】
【外国語出願】
【出願番号】特願２００９−１８８１１５（Ｐ２００９−１８８１１５）
【出願日】平成２１年７月２４日（２００９．７．２４）
【出願人】（５０８３５１１１８）ナヴテック ノース アメリカ リミテッド ライアビリティ カンパニー (20)
【Ｆターム（参考）】
【公開日】平成２２年２月２５日（２０１０．２．２５）
【国際特許分類】
【出願番号】特願２００９−１８８１１５（Ｐ２００９−１８８１１５）
【出願日】平成２１年７月２４日（２００９．７．２４）
【出願人】（５０８３５１１１８）ナヴテック ノース アメリカ リミテッド ライアビリティ カンパニー (20)
【Ｆターム（参考）】
[ Back to top ]