JP2012159506A - 符号化されたマーカーを用いたナビゲーションシステム及び方法 - Google Patents

Abstract

【課題】広範囲に及ぶデータベースや大きな計算資源を必要とせず、容易に実現可能なナビゲーションシステム及び方法へのニーズが存在する。
【解決手段】ナビゲーション環境の中に配置される、符号化されたマーカーを用いた、ナビゲーション環境の中のナビゲータの位置を決定するためのナビゲーションシステム及び方法が開示される。ナビゲーションシステムは：ナビゲーション環境の中の少なくとも一つの符号化されたマーカーの画像を含む場面の画像を取得するよう構成されるカメラ装置と；前記少なくとも一つの符号化されたマーカーを読み取るよう構成されるビデオ分析手段と；前記ビデオ分析手段と接続され、前記少なくとも一つの符号化されたマーカーの既知の場所に基づいてナビゲータの位置を決定するよう構成されるプロセッサと；を有する。
【選択図】図２

Description

本発明は、符号化されたマーカーを用いたナビゲーションシステム及び方法に関する。

よく知られているナビゲーションシステムの例は、衛星を利用したシステムであるGPS（global positioning system）である。GPSは、ナビゲーション環境の範囲内のナビゲータの位置を決定するために、GPS衛星から位置決定（location fixes）するためのGPS受信機を用いる。GPS受信機は、送信GPS衛星から情報を周期的に受信し、ナビゲータの位置を三角法で測るためにその情報を用いる。しかしながら、ある環境において、GPSシステムは、GPS信号の利用が制限され、望まれたとおりに機能しない。例えば、都市環境において、高層ビルがGPS衛星の受信を妨害し、又は悪化させることがある。空の視界の制限、又は、信号のマルチパス若しくは反射による、GPSの受信の妨害又は悪化により、GPS受信機がGPS衛星から位置決定することができない「GPS障害（GPS denied）」環境を生ずることがある。

GPS信号の散発的な損失に対処するためのいくつかの試みがなされた。しかしながら、都市環境における交通システムのための、正確で絶対的な位置調整へのニーズに対して、実用的で、技術的に実行可能な解決策はほとんどない。いくつかの解決策は、画像処理又はビデオ分析による「場面マッチング（scene matching）」を用いることを試みた。いくつかの解決策では、センサにより取得された場面（scene）の画像に基づいて、センサの位置を決定する。しかしながら、これらの解決策の欠点は、場面マッチングの処理を実行するために、広範囲に及ぶ場面のデータベースと、膨大な計算資源を必要とすることである。場面のデータベースは、さらに、最新の状態に保たれなければならない。物理環境への季節ごとの変化又は永続的な変化は、場面マッチングの正確性に著しい影響を与え得るためである。別の解説策は、GPS受信が損なわれるか、あるいは利用不可である場合に、ナビゲータを位置づけるために高度な「推測位置（dead reckoning）」の計算を用いる。しかしながら、そのようなシステムは、時間と共に積み重なるずれと方向誤差（ドリフト又はバイアス）や、商業的に実行可能な車両のシステムにおいて、ナビゲータの速度又は方向の急速かつ頻繁な変化へ適応できないことを含む、著しい欠点を有する。

従って、特にGPS障害環境において、ナビゲータの連続的な位置情報を提供可能であって、広範囲に及ぶデータベースや大きな計算資源を必要とせず、容易に実現可能なナビゲーションシステム及び方法へのニーズが存在する。本発明の実施形態及び実施例は、ナビゲータの位置（position fix）を決定するために、ナビゲーション環境の範囲内に設置された、符号化されたマーカー（coded markers）から取得される位置情報を用いる、ナビゲーションシステム及び方法を対象にする。ナビゲータの連続的な位置情報を取得するために、位置決定の合間に、推測位置計算を用いることができる。この位置情報は、以下で説明されるように、地図データベースへ関連付けられ、地図を利用したディスプレイを用いて表示され得る。システムは、さらにGPS装置を含み、符号化されたマーカーからの位置情報は、前記GPS装置から取得される位置情報を補完するために用いられ得る。

一実施形態によれば、ナビゲータの位置を決定する方法は：少なくとも一つの符号化されたマーカーを含む場面の画像を取得する段階と；前記画像の中の前記少なくとも一つの符号化されたマーカーを読み取る段階と；前記少なくとも一つの符号化されたマーカーの既知の場所に基づいて、前記ナビゲータの場所に関する位置を決定する段階と；を有する。

前記方法の一つの実施例において、前記読み取る段階は：前記場面の前記画像から、前記少なくとも一つの符号化されたマーカーの一つの画像を抽出する段階と；前記少なくとも一つの符号化されたマーカーの一つの前記画像をデータベースの値へ復号化する段階と；前記データベースの値に基づいて前記少なくとも一つの符号化されたマーカーの一つの前記既知の場所を読み出すためにデータベースにアクセスする段階と；をさらに有する。別の実施例において、前記読み取る段階は：前記場面の前記画像から、前記少なくとも一つの符号化されたマーカーの一つの画像を抽出する段階と；前記少なくとも一つの符号化されたマーカーの一つの前記画像を前記少なくとも一つの符号化されたマーカーの一つの前記既知の場所へと復号化する段階と；をさらに有する。前記決定する段階は：前記ナビゲータと前記場面の前記画像の中の前記少なくとも一つの符号化されたマーカーとの間の相対的な方位角のオフセットを決定する段階と；前記相対的な方位角のオフセットから前記ナビゲータの前記位置を幾何学的に計算する段階と；を有し得る。別の実施例において、前記決定する段階は：前記場面の前記画像の中の前記少なくとも一つの符号化されたマーカーの寸法を決定することにより前記ナビゲータから前記符号化されたマーカーまでの距離を決定する段階；を有する。別の実施例において、前記取得する段階は、前記ナビゲータの移動している最中の異なる時間における前記場面の複数の画像を取得する段階を有し、前記決定する段階は：前記場面の前記複数の画像から、前記ナビゲータと前記少なくとも一つの符号化されたマーカーとの間の、対応する複数の相対的な方位角のオフセットを決定する段階と；前記マーカーへの前記複数の相対的な方位角のオフセットに基づいて前記ナビゲータから前記少なくとも一つの符号化されたマーカーまでの距離を決定する段階と；をさらに有する。前記方法は、前記ナビゲータの場所に関する前記位置を地図データへ関連付ける段階を有し得る。

一つの実施例において、前記取得する段階は、３６０度カメラを用いて前記画像を取得する段階をさらに有する。一つの実施例において、前記符号化されたマーカーは、バーコードを含む。別の実施例において、前記決定する段階は：GPS装置を用いて前記ナビゲータの位置情報を取得する段階と；GPS障害環境において、前記GPS装置からの前記位置情報を前記少なくとも一つの符号化されたマーカーから取得される前記位置を用いて補完する段階と；をさらに有する。前記決定する段階は：複数の位置を決定する段階と；前記ナビゲータの連続的な位置を提供するために、前記複数の位置の間の推測位置計算を実行する段階と；をさらに有し得る。一つの実施例において、前記複数の位置の間の推測位置計算を実行する段階は：前記ナビゲータの速度を監視する段階と；前記ナビゲータの方向を決定する段階と；前記複数の位置の一つと車両の前記速度と前記方向とに基づいて前記ナビゲータの前記位置を推定する段階と；
を有する。

別の実施形態によれば、ナビゲーションシステムは：ナビゲーション環境の中の少なくとも一つの符号化されたマーカーの画像を含む場面の画像を取得するよう構成されるカメラ装置と；前記少なくとも一つの符号化されたマーカーを読み取るよう構成されるビデオ分析手段と；前記ビデオ分析手段と接続され、前記少なくとも一つの符号化されたマーカーの既知の場所に基づいてナビゲータの位置を決定するよう構成されるプロセッサと；を有する。

一つの実施例において、前記ナビゲーションシステムは：前記少なくとも一つの符号化されたマーカーの少なくとも一つの既知の場所と；前記少なくとも一つの符号化されたマーカーの少なくとも一つの前記既知の場所に関連する少なくとも一つのデータベースの値と；を有するデータベースをさらに含む。この実施例において、前記ビデオ分析手段は、前記場面の前記画像から前記少なくとも一つの符号化されたマーカーの画像を抽出し、前記少なくとも一つの符号化されたマーカーの前記画像を前記少なくとも一つのデータベースの値へと変換するようさらに構成される。別の実施例において、前記プロセッサは、前記ナビゲータと前記場面の前記画像の中の前記少なくとも一つの符号化されたマーカーとの間の相対的な方位角のオフセットを決定し、前記相対的な方位角のオフセットから前記ナビゲータの前記位置を幾何学的に計算することにより、前記ナビゲータの場所に関する前記位置を決定するようさらに構成される。前記プロセッサは、前記少なくとも一つの符号化されたマーカーへの前記ナビゲータの距離を決定することにより、前記ナビゲータの場所に関する前記位置を決定するようさらに構成され得る。

別の実施例において、前記ナビゲーションシステムは、地図データベースであって、前記プロセッサが前記ナビゲータの前記位置を当該地図データベースに関連付けるよう構成される、地図データベースと、前記地図データベースの視覚表示を表示し、該視覚表示の中に前記ナビゲータの前記位置を配置するよう構成されるディスプレイと、をさらに有する。前記ナビゲーションシステムは、前記ナビゲータの位置情報を取得するよう構成されるGPS装置をさらに有し、前記プロセッサは、前記GPS装置から取得される前記ナビゲータの前記位置情報を前記少なくとも一つの符号化されたマーカーの前記既知の場所に基づく位置を用いて補完するよう構成される。一つの実施例において、前記プロセッサは、前記少なくとも一つの符号化されたマーカーの前記既知の場所に基づいて複数の位置を取得し、前記ナビゲータの連続的な位置を提供するために、前記複数の位置の間の推測位置計算を実行するようさらに構成される。
前記カメラ装置は３６０度カメラを含み得る。一つの実施例において、前記少なくとも一つの符号化されたマーカーは、少なくとも一つのバーコードを有する。

さらに、これらの実施例、実施形態についての他の実施例、実施形態及び利点が、以下で詳細に説明される。ここで開示されるあらゆる実施形態は、ここで開示される複数の目的、目標及びニーズのうち少なくとも一つと一致するあらゆる方法で、他のあらゆる実施形態と組み合わされ得る。「ある実施形態」、「いくつかの実施形態」、「一つの代わりの実施形態」、「様々な実施形態」、「一つの実施形態」等への言及は、必ずしも相互に排他的なものではなく、前記実施形態に関連して記載される、ある特定の特徴、構造又は特性が、少なくとも一つの実施形態に含まれ得ることを示すことを意図している。そのような用語の出現は、必ずしも全てが同一の実施形態を指しているとは限らない。添付される図面は、説明並びに様々な実施例及び実施形態のさらなる理解を提供するために含まれる。さらに、添付される図面は、本明細書の一部に組み込まれ、かつ、本明細書の一部を構成する。明細書の記載と共に、図面は、説明され、クレームされる実施例及び実施形態の原理と働きを説明するのに役立つ。

少なくとも一つの実施形態についてのいくつかの実施例は、添付の図面を参照して以下に説明される。図面は、縮尺通りに描かれることを意図されていない。図面、詳細な説明又はあらゆるクレームの中の技術的な特徴は参照符号を伴うが、該参照符号は、図面、詳細な説明及びクレームの明瞭度を高める唯一の目的のために含まれている。従って、参照符号もその欠落も、あらゆるクレームの要素の範囲の、あらゆる限定する効果を有することを意図されていない。図面において、いくつかの図面の中で示される、それぞれ同一又はほぼ同一の要素は、同様の番号によって表される明確にする目的のために、全ての部品が、全ての図面の中でラベル付けされるとは限らない。図面は、実例と説明の目的で提供され、本発明の限定を意図されているものではない。

本発明の一実施例に従う、符号化されたマーカーを含むナビゲーション環境の一つの例についての概略図。 本発明の一実施例に従うナビゲーションシステムの一例についてのブロック図。 本発明の一実施例に従う、ナビゲータの位置を決定する方法の一例を表すフロー図。 本発明の一実施例に従う、符号化されたマーカーの既知の配置位置を用いたナビゲータの位置の決定の一例についての概略図。 本発明の一実施例に従う、ナビゲータの位置の決定の別の例についての概略図。 本発明の一実施例に従う、ナビゲータの位置の決定の別の例についての概略図。 本発明の一実施例に従う、ナビゲータの位置の決定の別の例についての概略図。 本発明のいくつかの実施例に従う、ナビゲータと符号化されたマーカーとの間の相対的な方位角と距離とを用いた、ナビゲータの位置の決定の別の例についての概略図。 本発明の一実施例に従う、推測位置計算の実行のステップを含む、ナビゲータの位置の決定の方法の一例についてのフロー図。 本発明のいくつかの実施例に従う、GPSユニットにより取得される位置情報の補完を含む、ナビゲータの位置の決定の方法の一例についてのフロー図。

上述したように、「GPS障害」環境においてナビゲータの位置情報を取得するための従来の解決策は、計算上高価であること、並びに／又は正確さ及び／若しくは順応性に欠くことのような、いくつかの欠点を有する。ここで用いられる「ナビゲータ」の語は、ナビゲーション環境の中で移動する、車両、人又はあらゆる物体を指し得る。それに応じて、これらの環境の中で、複雑なシステムを使用せずに、ナビゲータの連続的かつ正確な位置情報を提供することによってナビゲーションするための方法に対するニーズが存在する。実施例及び実施形態は、従来の解決策の制限と欠点を克服し、機能的に複雑でなく、実装が容易なナビゲーションのシステム及び方法を対象とする。

一つの実施形態によれば、ナビゲーションシステムは、ナビゲーション環境の中に配置された、位置（position fix）を提供するための符号化されたマーカー（coded marker）を用いる。これらの符号化されたマーカーは、例えば、道路沿いの街灯若しくは電柱、ビル又は他のインフラの物体のような、ナビゲーション環境の中に既に存在するインフラに設置され得る。一つの実施形態において、ナビゲーションの場面の画像を取得するためにカメラが用いられる。次に、前記場面の前記画像の中の符号化されたマーカーを識別するために、ビデオ分析（video analytics）のシステムが画像処理を用いることができる。ビデオ分析の一部分又は別個の要素である、プロセッサは、さらに以下で説明されるように、ナビゲーション環境の中に配置された、符号化されたマーカーの既知の場所を取得するために、符号化されたマーカーを読み取ることができる。一度、符号化されたマーカーの場所が決定されると、プロセッサは、ナビゲータから、配置済みの、符号化されたマーカーの既知の場所までの距離を決定することにより、ナビゲータの位置を決定することができる。別の実施形態において、ナビゲータの絶対位置についての正確性が重要でない場合には、ナビゲータの位置は、符号化されたマーカーの場所に基づいて推測することができる。ナビゲータの位置は、次に、地図データと関連付けられ得る。そして、ナビゲーションシステムディスプレイ上に表示され、ナビゲーション環境の視覚表示を示すことができる。

本発明の一実施例に従うナビゲーションのシステム及び方法は、スタンドアロンのシステムとして実装されることができ、あるいは、以下でさらに説明されるように、GPSを利用したシステムを補完するために用いられることができる。従来の場面マッチングによる解決策で用いられるような、高価で巨大になる可能性のある、場面のデータベースを必要とする代わりに、符号化されたマーカーのデータベースに対する記憶装置の要求は相当に小さい。さらに、ナビゲーション環境から、符号化されたマーカーの画像を抽出し、位置情報を取得することは、従来の場面マッチング技術より少ない計算資源を必要とする。システム上の計算負荷は低減される。符号化されたマーカーのシンプルな視覚特性により、その画像の容易な読込みと処理が可能になるためである。さらに、システムは、既存のGPSシステムによって提供される特徴及び恩恵と統合され、活用され得る。GPS装置は市場で広く利用可能であり、多くの構成又はオプションと共に利用可能である。以下でさらに説明されるように、システムは、既存の地図データベースと、既にGPS装置へと統合された、地図を利用したディスプレイをも用いることができる。

ここで説明される方法及び装置の実施形態は、以下の説明又は添付される図面で説明される、構成要素の構造及び配置の詳細な応用において制限されない。当該方法及び装置は、他の実施形態における実装が可能であり、様々な方法における実践又は実行が可能である。ここでの特定の実装の例は、説明の目的のためだけに提供され、限定することを意図されていない。特に、あらゆる一つ以上の実施形態に関連して説明される、動作、要素及び特徴は、あらゆる他の実施形態における同様の役割から除外されることを意図されていない。

さらに、ここで用いられる表現や専門用語は、説明を目的とするものであり、制限とみなされるべきではない。単数形で参照される、実施形態又は要素又はシステム若しくは方法の動作へのあらゆる言及は、複数のこれらの要素を含む実施形態を包含する。そして、あらゆる実施形態又は要素又は動作への複数形でのあらゆる言及は、単に一つの要素のみを含む実施形態をも包含する。単数形又は複数形での言及は、目下開示されるシステム又は方法、それらの部品、動作又は要素を限定することを意図されていない。「含む（including）」、「有する（comprising）」、「有する（having）」、「含む（containing）」、「含む（involving）」及びそれらの変化形は、以後、記載された項目や、その均等物及び追加の項目を包含することを意味する。「又は（or）」への言及は、「又は」を用いて記述されるあらゆる用語が、単独、一つ以上及び述べられる用語の全てを示すよう、包括的に解釈され得る。前方と後方、左と右、上部と底部、上方と下方、及び垂直と水平へのあらゆる言及は、説明の利便性を意図されるものであり、本システム及び方法又はそれらの構成要素を、あらゆる一つの位置の向き又は空間の向きに限定することを意図されていない。

図１は、符号化されたマーカーを用いるナビゲーションシステム及び方法が実装された、ナビゲーション環境１００の一実施例を表す。示される例において、符号化されたマーカー１０２は、道路沿いのインフラ１０４に配置される。例えば、そのような道路沿いのインフラは、街頭、電柱、道路標識、ビル等を含み得る。ナビゲータ１０６の可視範囲の中にあり、車道に最も近い、あらゆるインフラが用いられ得る。符号化されたマーカー１０２は、「バーコード」のような、一連の垂直の線又は水平の線として実装され得る。バーコードは、光学的に機械可読のデータ表現である。一次元バーコード及び二次元バーコードを含む、多くの種類のバーコードが、符号化されたマーカー１０２のために用いられ得る。一つの例において、符号化されたマーカー１０２は、従来のUPC（Universal Price Code）と同様の、一次元バーコードである。この例では、バーコードは、データのバイナリビット（１と０）を表す、一連の交互のバーとスペースを含む。一連のバイナリビットは、当業者によって知られるように、数値、文字、記号等を表すことができる。バーコードは、一連のグループを区切るガードバー（guard bar）と、バーコードの開始と終了を示す開始バー（starting bar）と終了バー（ending bar）をも含み得る。以下の説明と例は、主としてバーコードの利用について言及することがあるが、例えば、ブロックパターン、色分け又は英数字コードのような、他の種類の符号化されたマーカーを用い得ることが理解されるべきである。

図２は、ナビゲーションシステム２００の一実施例についてのブロック図である。ナビゲーションシステム２００は、カメラ装置２０４のような撮像装置とともに、ビデオ分析手段（video analytics）２０６、プロセッサ２０８、符号化されたマーカーのデータベース２１２及びディスプレイ２１４を含む。ナビゲーションシステムは、以下でさらに説明するように、GPS装置２１０と地図データベース２１６を任意で含み得る。ナビゲーションシステム２００は、旅行者又はハイカーの個人のナビゲーション及び／又は車両のナビゲーションのような、あらゆるナビゲーションのアプリケーションで用いられ得る。それに応じて、以下の実施例は、ナビゲーション環境を通じた車両の移動に関連して用いられるナビゲーションシステムに主として言及し、符号化されたマーカーは道路沿いのインフラに設置され得るが、ナビゲーションシステムは車両での使用に制限されず、また、符号化されたマーカーは道路沿いのインフラに制限されず、関連するナビゲーション環境の中のあらゆる場所に設置され得ることが理解されるべきである。ナビゲーションシステムは、例えば、携帯用装置、又は車両上若しくは車両内に取り付けられるよう構成された装置、又は車両内に統合され得る装置のような、内蔵型装置として実装され得る。さらに、ナビゲーションシステムは、スタンドアロンシステムであり得る。そして、専らナビゲータの位置を決定するために用いられ得るか、あるいは、以下でさらに説明されるように、GPS障害環境においてGPS衛星データを補完するために、GPS装置と連動して用いられ得る。

一つの実施形態によれば、カメラ装置２０４は、ナビゲーション環境の、視界の中の画像を取得するよう構成される。それに応じて、カメラ装置２０４の様々な機能を管理する制御装置とともに、一つ以上の撮像センサを含み得る。カメラ装置２０４は、画像、及びカメラに関する様々な機能を管理し制御するために用いられる、実行可能なプログラムを保管するためのメモリをさらに含み得る。例えば、デジタル一眼レフ（DSLR）カメラ又はデジタルコンパクトカメラ（point-and-shoot camera）のような、静止画像デジタル写真カメラを含む、異なる様々なカメラが用いられ得る。該カメラは、パノラマ式又は３６０度の場面の画像を撮影するために配置され得る。一つの実施形態において、前記カメラは、カメラに統合され得るか、又は取り付けられ得る、パノラマレンズを用いる。そのようなカメラレンズの一例は、デジタルカメラに取り付けられ、www.0-360.comにより提供される、0-360 PANORAMIC OPTIC（登録商標）である。0-360 PANORAMIC OPTIC（登録商標）及び関連するソフトウェアは、完全な３６０度の水平な視界と、１１５度の垂直な視界の周りの、単一の継ぎ目のないパノラマ画像を生成する。0-360 PANORAMIC OPTIC（登録商標）と組み合わされるカメラは、水平より上の５２．５度から、水平より下の６２．５度の画像を取得することができる。

一つの実施例において、カメラ装置２０４は、場面の連続的な写真を撮影し、その画像をビデオ分析手段２０６に渡す。該画像は、例えば、一秒ごと、数秒ごと、又はほんの一瞬ごとに、周期的な間隔で撮影され得る。カメラが画像を取得する速度は、変動し、あるいは調節され得る。符号化されたマーカーの十分な数の画像が取得されることを保証するために、例えば、ナビゲータが移動する速度に依存して、取得の割合を増加させることが望まれ得る。別の実施例において、カメラ装置２０４はビデオカメラである。ビデオカメラは、ナビゲーション環境の連続したビデオ記録を取得することができ、該ビデオ記録を、エンコーダを用いて、より小さなサイズへ圧縮することができる。圧縮されたビデオ記録のサイズは、符号化されたマーカーの画像を抽出するために必要な、記録の品質に依存し得る。一つの実施例において、カメラは、符号化されたマーカーに対する環境を監視する。符号化されたマーカーが場面の中で検出されると、ビデオカメラは、ビデオ記録に加えて、静止画像を取得し得る。

さらに図２を参照すると、カメラによって取得された画像は、ビデオ分析手段２０６へ提供される。ビデオ分析手段２０６は、ナビゲーションの場面１００の画像から、符号化されたマーカー１０２の画像を検出し、抽出し、処理するために、画像処理を用いる。ビデオ分析手段２０６は、ソフトウェア部品とハードウェア部品との両方を含んでもよく、FPGA（field-programmable gate arrays）、ASIC（application-specific integrated circuits）、マイクロコントローラ、PLD（programmable logic devices）又は他のそのような既知の装置のようなハードウェア装置を用いて実装され得る。一つの実施形態において、ビデオ分析手段２０６は、カメラ装置２０４に組み込まれる。カメラ装置２０４は、あらゆる照明及び／又は天候条件の下で、符号化されたマーカーの検出を改善するために、他のセンサ／装備をさらに用いることができる。例えば、高ダイナミックレンジ（HDR）カメラが、微光又は日陰の条件を補うために用いられ得る。バーコードは、微光の条件における検出を改善するために、反射性又は発光性であってもよい。

本開示書の利益を得て、当業者により理解されるように、ピクセルイメージデコーディング又は他のカメラのオブジェクト検出技術を用いる、あらゆるビデオ分析方法又はシステムが用いられ得る。一つの実施例において、ビデオ分析手段２０６は、符号化されたマーカーの画像と関連する性質に一致するピクセルを特定するために、画像の中の全てのピクセルを分析する。ビデオ分析手段２０６は、次のピクセルへ進む前に、設定パラメータに従って一致したピクセルを処理し得る。別の実施例において、ビデオ分析手段２０６は、例えば、符号化されたマーカーの画像の中に含まれる特性のような、ある特性に一致するピクセルの束を識別して抽出することによる、よりインテリジェントなピクセル処理を用いる。これらのピクセルは、場面の画像からフィルタされ、個別に処理され得る。そのようなフィルタリング技術は、例えば、連続する場面の画像を比較することにより、画像の前景と背景との間とを区別することができる。フィルタは、符号化されたマーカーの画像の中に含まれる色の値の範囲と一致する特定の範囲で、特定の色の値を区別することもできる。符号化されたマーカーの画像は、周囲の環境の画像から視覚的に区別できるため、符号化されたマーカーを識別して一致させるために必要となるビデオ処理は迅速に実行されることができ、完全な「場面マッチング」のために必要なビデオ処理よりも、一般的に、はるかに単純であり得る。

図３は、一実施形態に従う、ナビゲータの位置を決定する方法３００を示す。カメラ装置２０４は、一つ以上の符号化されたマーカー１０２を含む、ナビゲーションの場面１００の画像を取得することができる（ステップ３０２）。ステップ３０４において、ビデオ分析手段２０６は、場面の画像から、符号化されたマーカーの画像を抽出するために、場面の画像を処理し、前記マーカーを復号化することにより、符号化されたマーカーを読み取る。ステップ３０６は、符号化されたマーカーの位置を決定する段階を含む。上述したように、符号化されたマーカー１０２は、UPCバーコードのような、一連の水平のバー又は垂直のバーであってもよい。バーとスペースの群は、いくつかの数字を表し得る。一連の数字は、符号化されたマーカーの識別値又はデータベースの値であり得る。それらの値は、プロセッサ２０８によって、符号化されたマーカーのデータベース２１２の中の、符号化されたマーカーの既知の配置位置に対して比較され得る。代わりに、一連の数字は、経度と緯度のような、符号化されたマーカー１０２の位置情報を表す地理座標へと変換されてもよい。一度、符号化されたマーカーの位置がわかると、ナビゲータの位置が決定される（ステップ３０８）。一つの実施例において、以下でさらに説明されるように、このことは、ナビゲータの、符号化されたマーカーへの相対的な方位角及び／又は距離を決定することにより達成される。方法３００は、ナビゲータの場所に関する複数の位置を決定するために、連続的か、あるいは所定の間隔で繰り返され得る。

図４は、符号化されたマーカーからナビゲータの位置を決定する例を表す。図４は、場面の画像４００、道路インフラ１０４、及びX1とX2とラベル付けされた、符号化されたマーカー１０２を含む。上述したように、符号化されたマーカー１０２は、ナビゲーション環境１００の中の道路インフラ１０４上に設置されたバーコードであり得る。場面４００の画像は、上述したように、カメラ装置２０４により取得される。一つの実施形態において、プロセッサ２０８は、画像４００を処理することにより、ナビゲータの位置を決定する。プロセッサ２０８は、FPGA、ASIC、マイクロコントローラ、PLD又は当該技術分野で既知の、他のそのような装置のような、ハードウェア装置を用いて実装され得る。上述したように、プロセッサ２０８は、ビデオ分析手段２０６の一部又は別個の要素であり得る。一つの実施形態において、プロセッサ２０８は、符号化されたマーカーの画像の相対的な方位角のオフセット（azimuth offset）を決定し、該オフセットに基づいてナビゲータの位置を幾何学的に決定することにより、ナビゲータの位置を決定する。道路のインフラ１０４と符号化されたマーカーへの方位角のオフセットは、相対的な方位角の値がゼロであるところ（当然に、一般的にナビゲータの前方向と一致する）からの偏差４０２である、正の値又は負の値を決定することにより見出される。いくつかの実施例において、符号化されたマーカー１０２とナビゲータとの間の距離がさらに決定され、以下で説明されるように、ナビゲータの絶対位置を決定するために、偏差４０２とともに用いられる。

図５Ａは、（X1のラベルが付された）ある符号化されたマーカー１０２に基づいてナビゲータ１０６の位置を決定する、一つの実施例である。この実施例では、ナビゲータは、道路５０２上に位置すると仮定し、矢印５０４によって表されるナビゲータの向きは、道路の向きと一致すると仮定する。この実施例では、一つの符号化されたマーカーX1の検出及び読み取りにより、ナビゲータと符号化されたマーカーX1との間の視線（line-of-sight）５０６上のどこかに、ナビゲータ１０６があることが認識される。しかしながら、ナビゲータと符号化されたマーカーとの間の距離のような、追加的な情報がないため、ナビゲータの正確な位置を決定することができない。この実施例は、ナビゲータ１０６の位置のおおまかな見積もりを提供し、いくつかのアプリケーションにとってはそれが十分であり得る。しかしながら、図５Ｂに示されるように、上で示した仮定を前提として、ナビゲータと符号化されたマーカーとの間の距離に関するあらゆる情報を必要とすることなく、二つの符号化されたマーカー１０２の検出と読み取りによってナビゲータ１０６の正確な位置を決定することができる。具体的に言うと、同時に二つの異なる符号化されたマーカー１０２への相対的な方位角を取得することにより（すなわち、二つの符号化されたマーカーを含む同一の画像を処理することにより）、決定された方位角のオフセットにおいて、カメラ２０４の位置、すなわちナビゲータ１０６の位置で交差する、二つの直線を二つの符号化されたマーカーから引くことができる。そうして、画像４００が取得された時点のナビゲータの位置を提供する。この三角測量の方法は、二つの符号化されたマーカー１０２が、ナビゲータからマーカーまでの距離に関わらず画像４００の中で読み取ることができるという条件で、用いることができる。図５Ｃにおいて示されるように、ナビゲータ１０６の場所及び／又は向きに関して何ら仮定がなされず、あらゆるマーカーまでの距離の情報がない場合には、二つのマーカーの検出と読み取りは、ナビゲータの位置の大まかな見積もりを提供するが、ある特定の位置のナビゲータを認識することができない。従って、ナビゲータ１０６と、検出された、符号化されたマーカー１０２との間の相対的な方位角のオフセットの決定は、ナビゲータの大まかな位置、あるいはいくつかの環境においては正確な位置を取得するために用いることができる。

図４を再度参照すると、別の実施形態において、プロセッサ２０８は、符号化されたマーカーの画像の寸法（dimension）を決定し、符号化されたマーカーからのナビゲータの距離を決定することにより、ナビゲータの絶対位置を決定する。図４で示されるように、バーコードは、高さ４０４と幅４０６の寸法を有する。符号化されたマーカーの画像の高さは、カメラから一定の距離離れた地点における画像の中のピクセル数によって数値化され得る。例えば、５ピクセルは、カメラから一定の距離離れた地点における1ミリメートルの高さを表し得る。符号化されたマーカーの高さ４０４を用いて、符号化されたマーカーからのナビゲータの距離が推定され得る。その関係は、正比例し得る。言い換えれば、画像４００の中に現れる符号化されたマーカーの高さが高いほど、符号化されたマーカーはナビゲータに近い。プロセッサ２０８は、カメラから一定距離離れた地点における、符号化されたマーカーの所定の高さに基づいて、ナビゲータの位置を決定することができる。

ナビゲーションシステムは、上述した、ナビゲータの位置を決定する方法のいずれか、あるいは両方を用いることができる。一つの実施形態において、二つの符号化されたマーカーがカメラで確認できる場合には、ナビゲータの絶対位置を決定するために、相対的な方位角を用いる幾何学的な決定方法のみが用いられる。ナビゲーション環境において、一つの符号化されたマーカーのみが可視である場合には、ナビゲータの絶対位置は、幾何学的な決定方法によって取得されないことがある。従って、絶対位置が望まれる場合には、マーカーの寸法による方法が代わりに用いられ得る。別の実施形態において、プロセッサ２０８は、ナビゲータの絶対位置を決定するために、幾何学的な決定方法と、マーカーの寸法の方法とを組み合わせるよう構成される。

図６は、例えば、相対的な方位角の決定を用いて、場面４００の連続する画像から、マーカーまでの距離の情報と、ナビゲータの絶対位置との両方を幾何学的に決定する一つの例を表す。計算のために、道路の方向は、ナビゲータの向き及び相対的な方位角がゼロの向きと一致すると仮定する。画像は、ナビゲータP1及びP2の位置で取得され、その画像の間に移動した距離であるΔdは、以下の式で計算される。
Δd = V Δt;
ここで、Vはナビゲータの速度であり、Δtは、P1とP2とが画像が取得される間の時間である。符号化されたマーカーX1とそれぞれの位置P1及びP2におけるナビゲータ１０６との間の相対的な変位角Az1及びAz2が、二つの画像から決定される。三角形６０２は、符号化されたマーカーX1からナビゲータの位置P1及びP2へ直線を引き、さらに位置P1とP2との間に直線を引くことにより、形成される。それぞれの位置における、符号化されたマーカーX1からのナビゲータの距離d1及びd2は、それぞれ、余弦の法則に従って、以下の式から決定され得る。
d1² = d2² + Δd² - 2 Δd d2 cos(180 - Az2);
d2² = d1² + Δd² - 2 Δd d1 cos(Az1)
二つの符号化されたマーカーX1及びX2が、両方ともに画像４００の中で可視である場合には、ナビゲータのそれぞれの位置P1及びP2と、第二の符号化されたマーカーX2との間の相対的な方位角と距離は、同様に決定され得る。本開示書の利益を得て、当業者によって理解されるように、一つの符号化されたマーカー１０２のみが可視であり、ナビゲータの向きが道路の向きと一致しない場合には、ナビゲータ１０６の正確な位置を決定することはできない。一方で、複数の符号化されたマーカーが、十分に離れたΔdとなるナビゲータの位置P1とP2とにおいて、取得された連続する画像で可視であれば、それらの位置の間のナビゲータの正確な位置及び正確な向きは、明確に計算することができる。

上述した方法及びシステムは、ナビゲータの連続的な位置情報を提供し、符号化されたマーカーから取得される位置データを補完するために、位置決定の間（in-between）に推測位置（dead reckoning）計算を実行することができる。そのような推測位置計算は、従来のGPSを利用したシステムにおいて、GPS装置によって受信された衛星データの実現値（instance）の合間に度々実行される。それに応じて、図７は、位置決定の間の推測位置の使用を含む、ナビゲータの位置の決定方法の別の例のフロー図を表す。上述したように、方法７００は、符号化されたマーカーを含む、場面の画像を取得する段階（ステップ３０２）と、該画像の中の符号化されたマーカーを読み取る段階と、該符号化されたマーカーの位置を決定する段階（ステップ３０４とステップ３０６）とを含む。該ステップは、前記符号化されたマーカーの配置位置を決定するために、データベースの中の前記符号化されたマーカーの識別値を探索する段階（ステップ７０２）を含み得る。あるいは、該ステップは、前記符号化されたマーカーの位置を取得するために、例えば、上述したように、緯度と経度へ直接に復号化する段階（ステップ７０４）を含み得る。方法７００は、前記ナビゲータの位置を取得する段階（ステップ３０８）をさらに含む。該段階は、前記ナビゲータからの前記符号化されたマーカーの距離を決定する段階（ステップ７０６）、及び／又は、上述したように、前記ナビゲータの向きと前記符号化されたマーカーとの間の相対的な方位角を決定する段階（ステップ７０８）を含み得る。一つの実施形態において、方法７００は、前記ナビゲータの連続的な位置を提供するために、推測位置計算を実行する段階（ステップ７１０）をさらに含み、任意で、地図を利用したディスプレイ上に前記ナビゲータの位置を表示する段階（ステップ７１２）を含む。ステップ３０８において前記ナビゲータの位置が取得された後に、推測位置計算が実行され（ステップ７１０）、その結果、前記ナビゲータの連続した位置が提供される。

一つの実施例において、推測位置計算は、ナビゲータの開始位置に注目し、ナビゲータの速度及び／又は加速／減速、並びにナビゲータの経路又は向きを監視することにより、ナビゲータの位置を推定する。推測位置計算は、ナビゲータが同一の向きに同一の速度／加速で移動した場合に、ナビゲータの位置を推定する。推測位置計算を用いて取得される位置の正確さは、センサデータの正確さと利用可能性に依存することが理解され得る。このデータを得るために、異なる技術が用いられてもよい。例えば、システムは、車両と関連し得る、差分若しくは数字の速度情報、オドメータのパルス、加速度計、レーダ、光学若しくは音響センサ、タコメータ及び／又はジャイロスコープのような、様々なセンサを用いることができる。システムの他の実施形態は、道路のカーブ及び曲がり角に沿ってナビゲータのコースをより正確にプロットするために、センサからのデータを地図データと組み合わせ得る。

一般的なGPSナビゲーションシステムは、道路網を表す地図データベース、及び道路網の視覚表示を表す、地図を利用したディスプレイと統合される。これらのナビゲーションシステムは、GPSを利用した位置を地図データベースと関連付け、地図を利用したディスプレイ上にナビゲータの位置を表示する。一つの実施形態によれば、当該ナビゲーションシステムは、そのような地図データベース２１６と地図を利用したディスプレイ２１４とを含む。あるいは、当該ナビゲーションシステムは、地図データベースと地図を利用したディスプレイを含むGPSを利用したシステムへと統合される。一つの実施例において、位置情報を取得するGPSは、符号化されたマーカーから取得される位置と置き換えられるか、あるいは補完される。一つの実施形態において、ステップ７１０において取得される連続的な位置情報は、地図データベース２１６と関連付けられ、ディスプレイ２１４上に表示される（ステップ７１２）。地図データベース２１６は、道路のネットワークを表し、基本要素及びその特性を含む。基本要素は、ノード、リンク及び領域から構成され得る。基本要素の特性は、それらの要素の地理座標、領域の形状、ノードのアドレス及び／又はリンクの道路区分を表す。道路網は、さらにPOI（points of interest）を含んでもよい。符号化されたマーカーの既知の位置は、地図データベース２１６の中の参照のノード又は点として符号化され得る。

一つの実施例において、ナビゲーションシステム２００のディスプレイ２１４は、道路網の視覚表示（visual representation）を表示する。視覚表示は、インタラクティブな三次元（3D）の地図の形式であり得る。視覚表示は、基本要素及びナビゲータの付近における道路網のPOIを表し得る。ナビゲータ１０２がナビゲーション環境１００を通じて移動するにつれ、3D地図はナビゲータとともに移動し、変化する要素に適応し得る。3D地図は、既知の、符号化されたマーカー１０２の位置及びナビゲータの位置をさらに表示する。液晶ディスプレイ（LCD）、プラズマディスプレイ又は発光ダイオード（LED）ディスプレイを含む、あらゆる種類のディスプレイが利用され得る。

上述したように、一つの実施形態において、ナビゲーションシステム２００は、GPS装置２１０と統合される。GPS信号が利用可能である場合には、GPS装置２１０は送信GPS衛星から情報を受信し、ナビゲータの位置を決定するためにそのデータを利用する。例えば、GPS装置２１０は、ナビゲータの位置を決定するために、一つのGPS衛星からのデータを、他のGPS衛星から受信したデータとを比較することにより、三角測量の計算を実行することができる。しかしながら、上述したように、「GPS障害」環境において、GPS装置２１０は、GPS衛星への視線がブロックされることにより、GPS衛星からの情報を受信することができないことがある。例えば、ナビゲータが、都市の谷間、駐車場ビル、木の近く、若しくはトンネル内にある場合、あるいは信号の反射又はマルチパス伝搬による場合である。ナビゲータが「GPS障害」環境を出た後であっても、GPS装置は、ナビゲータの位置をすぐに決定できないことがある。これらの状況、あるいは同様の状況及びこれらのGPS障害環境において、ナビゲータの位置は、上述したように、符号化されたマーカーを用いて決定することができる。

例えば、図８のステップ８０２において、方法８００は、GPS受信がGPS装置２１０を用いて可能かどうかを決定する段階を含む。GPS受信が利用可能である場合には、GPS装置は、一般的なGPS位置による方法を用いてナビゲータの位置を取得する（ステップ８０４）。GPS受信が利用手可能である場合には、当該方法は、上述したように、符号化されたマーカーによる方法３００又は方法７００を用いてナビゲータの位置を取得する。この位置は、GPS障害環境においてGPS装置により決定された位置情報を補完するか、あるいは置換し得る。別の位置が後続の符号化されたマーカーから取得されるまで、あるいは代わりに、受信がGPS装置に保管されるまで、上述したような、推測位置計算が実行される。この結果は、ナビゲータの連続的な位置情報であり、任意で地図データベース２１６へ関連付けられ、ディスプレイ２１４上に表示され得る。

少なくとも一つの実施形態の複数の実施例について説明したが、当業者が様々な代替、修正及び改良に容易に気がつき得ることを理解すべきである。そのような代替、修正及び改良は、この開示書の部分であることが意図され、さらに本発明の範囲内であることが意図される。従って、先述の説明及び図面は例示する目的のみによって存在し、本発明の範囲は、添付されるクレームの適切な構成及びそれらの均等物から決定されるべきである。

２０６ ビデオ分析手段
２０８ プロセッサ
２１０ ＧＰＳ装置
２１２ 符号化されたマーカーのデータベース
２１４ ディスプレイ
２１６ 地図データベース

Claims (21)

1. ナビゲータの位置を決定する方法であって：
   少なくとも一つの符号化されたマーカーを含む場面の画像を取得する段階と；
   前記画像の中の前記少なくとも一つの符号化されたマーカーを読み取る段階と；
   前記少なくとも一つの符号化されたマーカーの既知の場所に基づいて、前記ナビゲータの場所に関する位置を決定する段階と；
   を有する、方法。
2. 前記読み取る段階は：
   前記場面の前記画像から、前記少なくとも一つの符号化されたマーカーの一つの画像を抽出する段階と；
   前記少なくとも一つの符号化されたマーカーの一つの前記画像をデータベースの値へ復号化する段階と；
   前記データベースの値に基づいて前記少なくとも一つの符号化されたマーカーの一つの前記既知の場所を読み出すためにデータベースにアクセスする段階と；
   をさらに有する、請求項１に記載の方法。
3. 前記読み取る段階は：
   前記場面の前記画像から、前記少なくとも一つの符号化されたマーカーの一つの画像を抽出する段階と；
   前記少なくとも一つの符号化されたマーカーの一つの前記画像を前記少なくとも一つの符号化されたマーカーの一つの前記既知の場所へと復号化する段階と；
   をさらに有する、請求項１に記載の方法。
4. 前記決定する段階は：
   前記ナビゲータと前記場面の前記画像の中の前記少なくとも一つの符号化されたマーカーとの間の相対的な方位角のオフセットを決定する段階と；
   前記相対的な方位角のオフセットから前記ナビゲータの前記位置を幾何学的に計算する段階と；
   をさらに有する、請求項１に記載の方法。
5. 前記決定する段階は：
   前記場面の前記画像の中の前記少なくとも一つの符号化されたマーカーの寸法を決定することにより前記ナビゲータから前記符号化されたマーカーまでの距離を決定する段階；
   をさらに有する、請求項１に記載の方法。
6. 前記取得する段階は、前記ナビゲータが移動している最中の異なる時間における前記場面の複数の画像を取得する段階を有し、
   前記決定する段階は：
   前記場面の前記複数の画像から、前記ナビゲータと前記少なくとも一つの符号化されたマーカーとの間の、対応する複数の相対的な方位角のオフセットを決定する段階と；
   前記マーカーへの前記複数の相対的な方位オフセットに基づいて前記ナビゲータから前記少なくとも一つの符号化されたマーカーまでの距離を決定する段階と；
   をさらに有する、請求項１に記載の方法。
7. 前記ナビゲータの場所に関する前記位置を地図データへ関連付ける段階
   をさらに有する、請求項１に記載の方法。
8. 前記取得する段階は、
   ３６０度カメラを用いて前記画像を取得する段階
   をさらに有する。請求項１に記載の方法。
9. 前記決定する段階は：
   GPS装置を用いて前記ナビゲータの位置情報を取得する段階と；
   GPS障害環境において、前記GPS装置からの前記位置情報を前記少なくとも一つの符号化されたマーカーから取得される前記位置を用いて補完する段階と；
   をさらに有する、請求項１に記載の方法。
10. 前記決定する段階は：
    複数の位置を決定する段階と；
    前記ナビゲータの連続的な位置を提供するために、前記複数の位置の間の推測位置計算を実行する段階と；
    をさらに有する、請求項１に記載の方法。
11. 前記複数の位置の間の推測位置計算を実行する前記段階は：
    前記ナビゲータの速度を監視する段階と；
    前記ナビゲータの方向を決定する段階と；
    前記複数の位置の一つと車両の前記速度と前記方向とに基づいて前記ナビゲータの前記位置を推定する段階と；
    を有する、請求項１０に記載の方法。
12. 前記取得する段階は、
    少なくとも一つのバーコードを含む前記場面の前記画像を取得する段階をさらに含む、
    請求項１に記載の方法。
13. ナビゲーションシステムであって：
    ナビゲーション環境の中の少なくとも一つの符号化されたマーカーの画像を含む場面の画像を取得するよう構成されるカメラ装置と；
    前記少なくとも一つの符号化されたマーカーを読み取るよう構成されるビデオ分析手段と；
    前記ビデオ分析手段と接続され、前記少なくとも一つの符号化されたマーカーの既知の場所に基づいてナビゲータの位置を決定するよう構成されるプロセッサと；
    を有する、ナビゲーションシステム。
14. 前記少なくとも一つの符号化されたマーカーの少なくとも一つの既知の場所と；
    前記少なくとも一つの符号化されたマーカーの少なくとも一つの前記既知の場所に関連する少なくとも一つのデータベースの値と；
    を有するデータベースをさらに含み、
    前記ビデオ分析手段は、前記場面の前記画像から前記少なくとも一つの符号化されたマーカーの前記画像を抽出し、前記少なくとも一つの符号化されたマーカーの前記画像を前記少なくとも一つのデータベースの値へと変換するようさらに構成される、
    請求項１３に記載のナビゲーションシステム。
15. 前記プロセッサは、前記ナビゲータと前記場面の前記画像の中の前記少なくとも一つの符号化されたマーカーとの間の相対的な方位角のオフセットを決定し、前記相対的な方位角のオフセットから前記ナビゲータの前記位置を幾何学的に計算することにより、前記ナビゲータの場所に関する前記位置を決定するようさらに構成される、
    請求項１３に記載のナビゲーションシステム。
16. 前記プロセッサは、
    前記ナビゲータの、前記少なくとも一つの符号化されたマーカーの一つまでの距離を決定することにより、前記ナビゲータの場所に関する前記位置を決定するようさらに構成される、
    請求項１３に記載のナビゲーションシステム。
17. 地図データベースであって、前記プロセッサが前記ナビゲータの前記位置を当該地図データベースに関連付けるよう構成される、地図データベースと、
    前記地図データベースの視覚表示を表示し、該視覚表示の中に前記ナビゲータの前記位置を配置するよう構成されるディスプレイと、
    をさらに有する、請求項１３に記載のナビゲーションシステム。
18. 前記ナビゲータの位置情報を取得するよう構成されるGPS装置をさらに有し、
    前記プロセッサは、前記GPS装置から取得される前記ナビゲータの前記位置情報を前記少なくとも一つの符号化されたマーカーの前記既知の場所に基づく位置を用いて補完するよう構成される、
    請求項１３に記載のナビゲーションシステム。
19. 前記プロセッサは、
    前記少なくとも一つの符号化されたマーカーの前記既知の場所に基づいて複数の位置を取得し、
    前記ナビゲータの連続的な位置を提供するために、前記複数の位置の間の推測位置計算を実行する
    ようさらに構成される、請求項１３に記載のナビゲーションシステム。
20. 前記少なくとも一つの符号化されたマーカーは、少なくとも一つのバーコードを有する、
    請求項１３に記載のナビゲーションシステム。
21. 前記カメラ装置は、３６０度カメラを有する、
    請求項１３に記載のナビゲーションシステム。

Images