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