(57)【要約】【課題】  ２次元実写映像から３次元モデルを生成する方法及び装置を提供する。【解決手段】  ２次元実写映像のいずれか一つの客体内の少なくとも一つ以上の消失点に収斂するエッジ延長線の直線方程式を利用して、この消失点に対応する面の平面方程式を算出し、それを利用して客体に対する３次元モデルを生成することによって、３次元モデル生成過程での３次元幾何情報の算出のための計算が簡単であり、かつ正確に３次元モデルを生成できる。【選択図】      図１
2008204458.tif 000002
【特許請求の範囲】
【請求項１】
（ａ）２次元映像のいずれか一つの客体内で、映像情報の変化が臨界値以上の地点に該当するエッジを検出するステップと、
（ｂ）前記検出されたエッジの延長線が交差する地点である少なくとも一つ以上の消失点に収斂するエッジ延長線の幾何情報を利用して、前記消失点に対応する前記客体の面の幾何情報を算出するステップと、
（ｃ）前記２次元映像のデータ及び前記算出された面の幾何情報を利用して、前記客体に対する３次元モデルを生成するステップと、を含むことを特徴とする３次元モデルの生成方法。
【請求項２】
前記エッジ延長線の幾何情報は、前記エッジ延長線の直線方程式であり、前記面の幾何情報は、前記面の平面方程式であることを特徴とする請求項１に記載の３次元モデルの生成方法。
【請求項３】
前記（ｂ）ステップは、前記エッジ延長線の直線方程式及び前記面のいずれか一地点の座標値を利用して、前記面の平面方程式を算出することを特徴とする請求項２に記載の３次元モデルの生成方法。
【請求項４】
前記（ｂ）ステップは、前記消失点に収斂するエッジ延長線のうち、前記客体内で最も中間に位置したエッジ延長線の幾何情報を利用して、前記客体の面の幾何情報を算出することを特徴とする請求項１に記載の３次元モデルの生成方法。
【請求項５】
前記消失点が複数個である場合、
前記（ｂ）ステップは、前記複数個の消失点のうち第１消失点に収斂するエッジ延長線の幾何情報を利用して、前記第１消失点に対応する前記客体の第１面の幾何情報を算出し、前記複数個の消失点のうち第２消失点に収斂するエッジ延長線の幾何情報を利用して、前記第２消失点に対応する前記客体の第２面の幾何情報を算出することを特徴とする請求項１に記載の３次元モデルの生成方法。
【請求項６】
前記検出されたエッジの形態に基づいて、前記客体の複雑度を決定するステップをさらに含み、
前記決定された客体の複雑度によって選択的に前記面の幾何情報を算出することを特徴とする請求項１に記載の３次元モデルの生成方法。
【請求項７】
前記２次元映像内の映像特性の変化及びユーザー入力情報のうち少なくとも一つ以上に基づいて、前記２次元映像を構成する少なくとも一つ以上の客体を特定するステップをさらに含み、
前記（ａ）ステップは、前記特定された客体のうちいずれか一つの客体内で、前記映像情報の変化が臨界値以上である地点に該当するエッジを検出することを特徴とする請求項１に記載の３次元モデルの生成方法。
【請求項８】
前記２次元映像のデータは、前記２次元映像を構成する画素の２次元座標値及びテクスチャーであり、前記面の幾何情報は、前記面の平面方程式であり、
前記（ｃ）ステップは、前記面の平面方程式に前記２次元座標値を代入することによって、前記面を構成する画素の３次元座標値を算出し、前記算出された画素の３次元座標値ごとに前記画素それぞれに対応するテクスチャーをマッピングすることを特徴とする請求項１に記載の３次元モデルの生成方法。
【請求項９】
前記（ｃ）ステップは、前記客体の各面を構成する画素の３次元座標値ごとに、前記現在の客体の各面に対向するカメラにより撮影されたテクスチャーをマッピングすることを特徴とする請求項８に記載の３次元モデルの生成方法。
【請求項１０】
ナビゲーションシステムでのナビゲーション方法において、
２次元映像のいずれか一つの客体内で、映像情報の変化が臨界値以上である地点に該当するエッジの延長線が交差する地点に基づいて前記客体の面の幾何情報を算出することによって、前記客体に対する３次元モデルを生成するステップと、
前記生成された３次元モデルを含む３次元モデルのうち、前記ナビゲーションシステムの現在位置情報に該当する３次元モデルを抽出し、前記抽出された３次元モデルを前記ナビゲーションシステムが装着された移動体の進行方向に該当する２次元平面上にレンダリングするステップと、を含むことを特徴とするナビゲーション方法。
【請求項１１】
映像内のエッジを検出することによって、前記映像内の客体を識別するステップと、
前記映像の所定の地面に関して前記識別された客体の検出された地点に基づいて、前記識別された客体の複雑度を決定するステップと、
前記決定された複雑度に基づいて選択的に前記識別された客体の少なくとも一つの対応面に対する少なくとも一つの消失点を識別し、前記映像の前記少なくとも一つの対応面の決定された点それぞれに関して前記識別された少なくとも一つの消失点を分析することによって、３次元モデルに対する前記少なくとも一面を生成するステップと、
３次元空間で前記少なくとも一面を組み合わせることによって、前記３次元モデルを生成するステップと、を含むことを特徴とするモデリング方法。
【請求項１２】
映像内のエッジを検出することによって、前記映像内の客体を識別するステップと、
前記識別された客体の少なくとも一つの対応面に対する少なくとも一つの消失点を識別し、前記映像の前記少なくとも一つの対応面の決定された点それぞれと、前記映像の下面に実質的に平行なラインに実質的に垂直な二つのエッジ線の間の各面を横切る中間線である各面内の各対応線に関して、前記識別された少なくとも一つの消失点とを分析することによって、３次元モデルに対する前記少なくとも一面を生成するステップと、
３次元空間で前記少なくとも一面を組み合わせることによって、前記３次元モデルを生成するステップと、を含むことを特徴とするモデリング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータビジョン分野での映像処理に係り、特に２次元実写映像から３次元モデルを生成する方法及び装置に関する。
【背景技術】
【０００２】
３次元モデリング技術は、コンピュータグラフィックス分野やコンピュータビジョン分野で多くの研究が進められている。コンピュータグラフィックス分野は、３次元空間での客体の幾何情報及び質感情報をモデリングする精巧なＣＡＤ（Ｃｏｍｐｕｔｅｒ  Ａｉｄｅｄ  Ｄｅｓｉｇｎ）システムを開発する方向に進められてきた。しかし、かかる方式は、実際の世界での客体の幾何情報が非常に複雑であり、照明効果を正確にモデリングしがたいため、写実的な映像を生成しがたいという問題点があった。
【０００３】
コンピュータビジョン分野は、２次元映像から３次元の幾何情報を算出し、実際の映像を利用して実際の世界の照明条件下で客体の質感情報を算出する方向に進められてきた。かかる２次元映像から３次元の幾何情報を算出する従来の方式としては、“Ｓｉｎｇｌｅ  ｖｉｅｗ  ｍｅｔｒｏｌｏｇｙ”（Ｃｒｉｍｉｎｉｓｉ，１９９９）、“Ｉｍａｇｅ−ｂａｓｅｄ  ｍｏｄｅｌｉｎｇ  ａｎｄ  ｐｈｏｔｏ  ｅｄｉｔｉｎｇ”（Ｂｙｏｎｇ  Ｍｏｋ  Ｏｈ，２００１）、“Ｕｓｉｎｇ  Ｇｅｏｍｅｔｒｉｃ  Ｃｏｎｓｔｒａｉｎｔｓ  Ｔｈｒｏｕｇｈ  Ｐａｒａｌｌｅｌｅｐｉｐｅｄｓ  ｆｏｒ  Ｃａｌｉｂｒａｔｉｏｎ  ａｎｄ  ３Ｄ  Ｍｏｄｅｌｌｉｎｇ”（Ｗｉｌｃｚｋｏｗｉａｋ，２００５）などがある。しかし、かかる方式は、３次元の幾何情報の算出のための計算が非常に複雑であるという問題点があった。
【０００４】
２００２年に“Ｄｅｒｅｋ  Ｈｏｅｉｍ”により発表された“ＡｕｔｏｍａｔｉｃＰｈｏｔｏ  Ｐｏｐ−ｕｐ”方式は、前記された方式よりその計算が非常に簡単なものであって、本を開けば、絵が飛び出す子供のポップアップブックに着眼したものである。すなわち、この方式は、２次元実写映像を地面、垂直及び空領域に区分し、映像内の地面と垂直との境界を推定する。次いで、この方式は、このように推定された境界を基準として２次元実写映像を構成する客体をカットして折ることによって、３次元モデルを生成する。しかし、この方式も、地面と垂直との境界が正しく設定されなければ、正確な３次元モデルが得られないという問題点があった。例えば、客体が建物であれば、建物と地面との間に自動車などが位置し、これにより、地面と垂直との境界が正しく設定されない。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明が解決しようとする課題は、３次元モデルの生成過程での３次元の幾何情報の算出のための計算が簡単であり、かつ建物と地面との間に自動車などが位置する場合にも正確に３次元モデルを生成可能にする装置及び方法を提供するところにある。
【０００６】
本発明が解決しようとする他の課題は、前記方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体を提供するところにある。
【０００７】
本発明が解決しようとする課題は、前記したような課題に限定されず、さらに他の課題が存在しうる。これは、当業者ならば、下記の記載から明確に理解される。
【課題を解決するための手段】
【０００８】
前記課題を解決するための本発明による３次元モデルの生成方法は、２次元映像のいずれか一つの客体内で、映像情報の変化が臨界値以上である地点に該当するエッジを検出するステップと、前記検出されたエッジの延長線が交差する地点である少なくとも一つ以上の消失点に収斂するエッジ延長線の幾何情報を利用して、前記消失点に対応する前記客体の面の幾何情報を算出するステップと、前記２次元映像のデータ及び前記算出された面の幾何情報を利用して、前記客体に対する３次元モデルを生成するステップとを含む。
【０００９】
前記他の課題を解決するために、本発明は、前記した３次元モデルの生成方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体を提供する。
【００１０】
前記課題を解決するための本発明による３次元モデル生成装置は、２次元映像のいずれか一つの客体内で、映像情報の変化が臨界値以上である地点に該当するエッジを検出するエッジ検出部と、前記検出されたエッジの延長線が交差する地点である少なくとも一つ以上の消失点に収斂するエッジ延長線の幾何情報を利用して、前記消失点に対応する前記客体の面の幾何情報を算出する面情報算出部と、前記２次元映像のデータ及び前記算出された面の幾何情報を利用して、前記客体に対する３次元モデルを生成する３次元モデル生成部とを備える。
【００１１】
前記さらに他の課題を解決するための本発明によるナビゲーションシステムでのナビゲーション方法は、２次元映像のいずれか一つの客体内で、映像情報の変化が臨界値以上である地点に該当するエッジの延長線が交差する地点に基づいて前記客体の面の幾何情報を算出することによって、前記客体に対する３次元モデルを生成するステップと、前記生成された３次元モデルを含む３次元モデルのうち、前記ナビゲーションシステムの現在位置情報に該当する３次元モデルを抽出し、前記抽出された３次元モデルを前記ナビゲーションシステムが装着された移動体の進行方向に該当する２次元平面上にレンダリングするステップとを含む。
【００１２】
前記さらに他の課題を解決するための本発明によるナビゲーションシステムは、２次元映像のいずれか一つの客体内で、映像情報の変化が臨界値以上である地点に該当するエッジの延長線が交差する地点に基づいて前記客体の面の幾何情報を算出することによって、前記客体に対する３次元モデルを生成する３次元モデル生成装置と、前記生成された３次元モデルを保存するメモリと、前記メモリに保存された３次元モデルのうち、前記ナビゲーションシステムの現在位置情報に該当する３次元モデルを抽出し、前記抽出された３次元モデルを前記ナビゲーションシステムが装着された移動体の進行方向に該当する２次元平面上にレンダリングするレンダリング装置とを備える。
【発明の効果】
【００１３】
本発明によれば、２次元実写映像のいずれか一つの客体内の少なくとも一つ以上の消失点に収斂するエッジ延長線の直線方程式を利用して、この消失点に対応する面の平面方程式を算出し、それを利用して客体に対する３次元モデルを生成することによって、３次元モデル生成過程での３次元幾何情報の算出のための計算が簡単である。特に、本発明によれば、消失点に収斂するエッジ延長線のうち、客体内で最も中間に位置したエッジ延長線の直線方程式を利用して、前記客体の面の平面方程式を算出することによって、建物と地面との間に自動車などが位置する場合にも正確に３次元モデルを生成できる。
【００１４】
また、本発明によれば、客体内のエッジの形態に基づいて客体の複雑度を決定し、これにより、本発明による面の幾何情報算出方式、従来の３次元モデリング方式または今後開発される３次元モデリング方式を選択的に適用可能にすることによって、最適の３次元モデリング過程をなした。また、前記したように、本発明による３次元モデリング方式は、その計算が簡単であり、かつ正確であるため、ナビゲーションシステムの内部に直接適用される場合に、３次元モデルを保存するメモリの容量を低減でき、ユーザーにさらに正確なナビゲーション画面を提供できる。
【発明を実施するための最良の形態】
【００１５】
以下、図面を参照して、本発明の望ましい実施形態を詳細に説明する。
【００１６】
図１は、本発明の望ましい一実施形態による３次元モデル生成装置の構成図である。図１に示すように、本実施形態による３次元モデル生成装置は、客体特定部１１、ユーザーインターフェース１２、エッジ検出部１３、客体分類部１４、面情報算出部１５、第１  ３次元モデル生成部１６及び第２  ３次元モデル生成部１７から構成される。
【００１７】
客体特定部１１は、２次元実写映像内の映像特性の変化及びユーザーインターフェース１２に入力されたユーザー入力情報のうち少なくとも一つ以上に基づいて、２次元実写映像を構成する少なくとも一つ以上の客体を特定する。すなわち、客体特定部１１は、２次元実写映像内の映像特性の変化に基づいて自動的に客体を特定してもよく、ユーザーインターフェース１２に入力されたユーザー入力情報に基づいて手動的に客体を特定してもよく、この両者に基づいて半自動的に客体を特定してもよい。
【００１８】
特に、本実施形態では、客体を特定するために色々な２次元実写映像特性のうちテクスチャーを使用する。本実施形態でのテクスチャーは、３次元モデルを表現するための情報のうち幾何情報を除いたあらゆる情報を意味する。以下でも同様である。すなわち、客体特定部１１は、２次元実写映像を構成する画素間のテクスチャーが異なる領域の境界に該当する客体の境界を検出し、その検出結果に基づいて客体を特定する。
【００１９】
図２は、図１に示した客体特定部が自動的に客体を特定する場合を示す図である。図２の（ａ）は、デジタルカメラを使用して撮影された都心の２次元実写映像である。この２次元実写映像は、地面、建物及び空から構成される。図２の（ａ）を参照するに、地面、建物及び空のテクスチャーは異なるということが分かる。したがって、客体特定部１１は、２次元実写映像の画素間のテクスチャーが異なる領域の境界に該当する地面の境界、建物の境界、空の境界を検出する。図２の（ｂ）は、客体特定部１１により検出された地面の境界２１、建物の境界２２、空の境界２３を示したものである。また、客体特定部１１は、このように検出された建物の境界を地面方向に延びることによって、建物の境界２４を特定できる。
【００２０】
また、客体特定部１１は、ユーザーインターフェース１２に入力されたユーザー入力情報に基づいて手動的に客体を特定できるが、この場合には、ユーザーがユーザーインターフェース１２、例えばタッチスクリーン入力装置などを利用して客体の境界いずれをも描く場合である。また、客体特定部１１は、２次元実写映像内の映像特性の変化及びユーザーインターフェース１２に入力されたユーザー入力情報に基づいて、２次元実写映像を構成する少なくとも一つ以上の客体を特定できる。自動的に客体を特定する方式は、ユーザーの立場では便利であるが、速度が遅いか、またはエラーが発生し、手動的に客体の境界を特定する方式は、ユーザーに多くの負担を与える。
【００２１】
図３は、図１に示した客体特定部が半自動的に客体を特定する場合を示す図である。図３の（ａ）に示したように、ユーザーがユーザーインターフェース１２を利用して、２次元実写映像のうち客体を特定するための検索領域３１を指定する。これにより、客体特定部１１は、ユーザーインターフェース１２に入力されたユーザー入力情報が指定する検索領域に対してのみ客体を特定することによって、完全自動方式よりさらに迅速に客体を特定できる。図３の（ｂ）には、ユーザーにより指定された検索領域に基づいて特定された客体の左右境界３２が示されている。
【００２２】
図３の（ｃ）に示したように、ユーザーがユーザーインターフェース１２を利用して、２次元実写映像のうち客体のトップライン３３を描く。これにより、客体特定部１１は、ユーザーインターフェース１２に入力されたユーザー入力情報が表す客体のトップラインと、２次元実写映像内のテクスチャーの変化とに基づいて客体を特定することによって、完全自動方式よりさらに正確に客体を特定できる。図３の（ｄ）には、ユーザーにより描かれた客体のトップラインに基づいて特定された客体の境界３４が示されている。一方、図３の（ｅ）には、ユーザーにより描かれた客体の概略的な境界３５が示されている。このように、ユーザーとの相互作用を通じて客体の境界を半自動的に特定できる。
【００２３】
エッジ検出部１３は、客体特定部１１により特定された少なくとも一つ以上の客体のうち、現在３次元モデリングしようとする客体（以下、“現在の客体”という）内で、映像情報の変化が臨界値以上である地点を表すエッジを検出する。ここで、臨界値は、本実施形態を数回実行し、その結果に基づいて、本実施形態のユーザーまたは設計者などにより適切に特定される。特に、本実施形態では、現在の客体内でエッジを検出するために色々な映像情報のうち光度を使用する。すなわち、エッジ検出部１３は、現在の客体内で光度の変化が臨界値以上である地点を表すエッジを検出する。建物を例として挙げれば、建物は、複数個の窓を備える。したがって、エッジ検出部１３は、建物内で光度の変化が臨界値以上である地点に該当する建物のコンクリート表面と窓との境界をエッジとして検出する。
【００２４】
客体分類部１４は、エッジ検出部１３により検出されたエッジの延長線の形態に基づいて現在の客体の複雑度を決定し、このように決定された現在の客体の複雑度によって、現在の客体を簡単な客体及び複雑な客体のうちいずれか一つに分類する。一般的に、３次元空間でいずれか一面は、その面に存在する三地点と定義される。二地点は、一つの直線に対応するため、３次元空間でいずれか一面は、その面に存在する一地点及び一つの直線と定義されるといえる。したがって、エッジ検出部１３により検出されたエッジの延長線の形態が直線であり、この直線を含む面に存在する一地点が決定されるならば、このエッジ延長線に対応する建物の面が定義される。すなわち、客体分類部１４は、エッジ検出部１３により検出されたエッジの延長線の形態が直線であり、かかる直線形態のエッジの延長線を含む面が２次元の実写映像の地面に垂直である場合に、現在の客体を簡単な客体に分類し、その他の場合に複雑な客体に分類する。
【００２５】
図４Ａないし図４Ｃは、図１に示した客体分類部１４での客体分類過程を示す図である。図４Ａに示すように、図４Ａの（ａ）に示した現在の客体は、２次元実写映像の地面に対して垂直な一面で構成されている。また、図４Ａの（ｂ）に示した現在の客体は、２次元実写映像の地面に対して垂直な二面で構成されている。また、図４Ａの（ｃ）に示した現在の客体は、２次元実写映像の地面に対して垂直な三面で構成されている。図４Ａに示した客体は、エッジ検出部１３により検出されたエッジの延長線の形態が直線であり、かかる直線形態のエッジの延長線を含む面が２次元実写映像の地面に垂直である場合であるため、客体分類部１４により簡単な客体に分類される。
【００２６】
図４Ｂに示すように、図４Ｂの（ａ）に示した現在の客体は、２次元実写映像の地面に対して垂直な一面と垂直でない他の面とで構成されている。図４Ｂの（ｂ）に示した現在の客体は、２次元実写映像の地面に対して垂直な面で構成されているが、エッジ検出部１３により検出されたエッジの延長線の形態が直線でない。図４Ｃに示すように、図４Ｃに示した現在の客体の面のうちいずれかは２次元実写映像の地面に対して垂直であり、その他は垂直でない。また、図４Ｃに示した現在の客体に対して、エッジ検出部１３により検出されたエッジの延長線のうち一部は、その形態が直線であり、その他は直線でない。
【００２７】
図４Ｂ及び図４Ｃに示した客体は、エッジ検出部１３により検出されたエッジの延長線の形態が直線であり、かかる直線形態のエッジの延長線を含む面が２次元実写映像の地面に垂直である場合ではないため、客体分類部１４により複雑な客体に分類される。ただし、前記したような客体分類基準は、下記される本実施形態によって建物の面方程式の算出が可能であるか否かを考慮したものである。したがって、前記した本実施形態ではない他の方式によって建物の面方程式が算出される場合には、前記した客体分類基準は変わるということを当業者ならば理解できる。
【００２８】
面情報算出部１５は、客体分類部１４により現在の客体が簡単な客体に分類された場合、エッジ検出部１３により検出されたエッジの延長線が交差する地点である少なくとも一つ以上の消失点を検出する。
【００２９】
図５は、３次元空間での正六面体に対する２点透視図である。図５に示すように、３次元空間での正六面体が２次元空間の二つの消失点を基準とする透視図法を使用して示されている。透視図は、人間の目により客体が見られる原理が適用された方式で客体の立体感が表現される。特に、３次元空間での正六面体が２次元平面上に投影されれば、正六面体の各面の境界のうち互いに平行な境界は、いずれか一つの共通点で交差する線として投影されるということが分かる。この共通点を消失点という。消失点は、２次元空間で有限点であってもよく、無限点であってもよい。図５に示したように、正六面体の各面の境界のうち互いに平行な水平境界は、有限消失点を有する。一方、正六面体の各面の境界のうち互いに平行な垂直境界は、無限消失点を有する。本実施形態での消失点とは、有限消失点を意味する。
【００３０】
図５から、一つの消失点は、客体の一面に対応するということが分かる。すなわち、面情報算出部１５は、このように検出された消失点に収斂するエッジ延長線の幾何情報を利用して、この消失点に対応する客体の面の幾何情報を算出する。本実施形態において、エッジ延長線の幾何情報は、エッジ延長線の直線方程式を意味し、客体の面の幾何情報を客体の面の平面方程式を意味する。ただし、当業者ならば、エッジ延長線の幾何情報または客体の面の幾何情報は、前記した方程式でない他の種類の幾何情報となるということを理解できる。
【００３１】
さらに詳細に説明すると、面情報算出部１５は、このように検出された消失点に収斂するエッジ延長線のうち、現在の客体の境界内で最も中間に位置したエッジ延長線（以下、“中間線”という）の直線方程式と、現在の客体と地面との境界（以下、“現在の客体の下線”という）上の任意の一地点の座標値を利用して、この消失点に対応する客体の面の平面方程式とを算出する。特に、消失点の個数が複数個である場合、面情報算出部１５は、複数個の消失点のうち第１消失点に収斂するエッジ延長線のうち中間線の直線方程式と、第１消失点に対応する第１面の下線上の任意の一地点の座標値を利用して、第１消失点に対応する第１面の平面方程式とを算出し、複数個の消失点のうち第２消失点に収斂するエッジ延長線のうち中間線の直線方程式と、第２消失点に対応する第２面の下線上の任意の一地点の座標値を利用して、第２消失点に対応する第２面の平面方程式とを算出する。複数個の消失点のうち残りに対しても同様である。
【００３２】
図６及び図７は、図１に示した面情報算出部１５での面幾何情報の算出方式を説明するための建物を示す図である。
【００３３】
図６の（ａ）には、客体特定部１１により検出された現在の客体６１の境界が示されている。前記したように、３次元空間でいずれか一面は、その面に存在する一地点及び一つの直線と定義されるため、現在の客体の下線上のいずれか一点が決定されねばならない。これにより、面情報算出部１５は、図６の（ａ）に示した現在の客体の下線上の一点６２を決定する。特に、現在の客体と地面との境界上に自動車のような障害物が存在して、正しい現在の客体の下線を検出しがたい場合には、ユーザーがこの点を指定することもできる。この場合、面情報算出部１５は、ユーザーインターフェース１２に入力されたユーザー入力情報に基づいて、図６の（ａ）に示した現在の客体の下線上の一点６２を決定する。また、図６の（ｂ）には、エッジ検出部１３により検出されたエッジの延長線が示されている。このエッジ延長線のうち、右側消失点（図示せず）に収斂するエッジ延長線６３は、前記で決定された一点６２を含む現在の客体６１の面に存在する。
【００３４】
図７の（ａ）には、エッジ検出部１３により検出されたエッジの延長線が示されている。このエッジ延長線のうち、左側消失点７１に収斂するエッジ延長線７２は、現在の客体の左側面に対応し、右側消失点（図示せず）に収斂するエッジ延長線６３は、現在の客体の右側面に対応する。図７の（ｂ）には、右側消失点に対応する現在の客体の右側面の平面方程式が算出される過程が示されている。すなわち、面情報算出部１５は、右側消失点に収斂するエッジ延長線のうち、現在の客体の境界内で中間に位置した中間線を決定し、この中間線の直線方程式と現在の客体の右側面の下線のうち任意の一地点とを決定し、このように決定された中間線の直線方程式と下線の３次元座標値とを利用して、客体の右側面の平面方程式を算出する。
【００３５】
図８及び図９は、図１に示した面情報算出部１５でのいずれか一面の平面方程式を算出する方式を示す図である。
【００３６】
図８に示すように、図８に示した建物は、三面で構成されている。この三面の境界とこの三面それぞれの中間線とが交差する地点がＡ，Ｂ，Ｃ及びＤで表示されている。この三面のうち左側面を例として挙げれば、この左側面は、線分ＡＢとこの左側面の下線のうちいずれか一点Ｇとで決定される。以下では、面情報算出部１５が線分ＡＢの直線方程式と点Ｇの３次元座標値とを利用して、左側面の平面方程式を算出する方式を説明する。
【００３７】
図９に示すように、３次元空間でのカメラの位置はＯである。ここで、３次元空間とは、２次元実写映像が撮影された実際空間を意味し、カメラの位置は、２次元実写映像を撮影したカメラの位置を意味し、２次元実写映像の中央点となる。特に、カメラは、針穴カメラであって、完壁な投影が可能なものと仮定する。実際のカメラは、かかる針穴カメラではないため、若干の誤差がありうる。線分Ａ’Ｂ’を含む建物の面は、３次元空間での実際の建物の面であるが、これは、カメラの焦点距離位置に線分ＡＢを含む建物の面、すなわち２次元実写映像の建物の面として投影される。
【００３８】
線分ＯＡと線分ＯＢとの延長線は、３次元空間の建物の面のＡ’とＢ’を通過する。線分ＣＡ’と線分ＤＢ’とは、地面に対する高さが同一であるため、ＤＢ’：ＯＯ’＝ＣＡ’：ＯＯ’及びＯＢ’：ＯＢ”＝ＯＡ’：ＯＡ”が成立する。これから、線分Ａ’Ｂ’と線分Ａ”Ｂ”とは、互いに平行であるということが分かる。建物の面Ｃ’Ａ’Ｂ’Ｄ’は、地面に垂直であるため、建物の面の法線は地面に平行である。したがって、線分Ａ”Ｂ”に垂直なベクトルが建物の面に垂直なベクトルとなるということが分かる。
【００３９】
面情報算出部１５は、カメラの位置Ｏの３次元座標値及び建物の境界と中間線との交差点Ａの３次元座標値から、直線ＯＡの方程式を算出する。また、面情報算出部１５は、カメラの位置Ｏの３次元座標値及び建物の境界と中間線との交差点Ｂの３次元座標値から、直線ＯＢの方程式を算出する。ここで、カメラの位置Ｏ、交差点Ａ及びＢの３次元座標値は、この地点に対する２次元実写映像での２次元座標値とカメラの焦点距離とから推定される。
【００４０】
また、面情報算出部１５は、このように算出された直線ＯＡの方程式を利用して、直線ＯＡと地面との交差点Ａ”の３次元座標値及び直線ＯＢと地面との交差点Ｂ”の３次元座標値を算出し、このように算出された交差点Ａ”及びＢ”の３次元座標値から、直線Ａ”Ｂ”の方程式を算出する。また、面情報算出部１５は、このように算出された直線Ａ”Ｂ”の方程式を利用して、地面に存在する直線Ａ”Ｂ”に垂直なベクトルＮを算出する。
【００４１】
また、面情報算出部１５は、カメラの位置Ｏの３次元座標値及び建物の下線のうち任意の一点Ｇの３次元座標値から、直線ＯＧの方程式を算出する。また、面情報算出部１５は、このように算出された直線ＯＧの方程式を利用して、直線ＯＧと３次元空間地面との交差点Ｇの３次元座標値を算出する。いずれか一面の方程式は、その面に存在するいずれか一点の３次元座標値及びその面に垂直ないずれか一つのベクトル値を知れば算出される。すなわち、ある面に存在する一点が（ｘ０，ｙ０，ｚ０）であり、この面に垂直なベクトルｎ＝ａｉ＋ｂｉ＋ｃｋであれば、この面の方程式は、次の数式の通りである。
【００４２】
ａ（ｘ−ｘ０）＋ｂ（ｙ−ｙ０）＋ｃ（ｚ−ｚ０）＝０
したがって、面情報算出部１５は、このように算出されたベクトルＮと交差点Ｇとの３次元座標値を利用して、中央線ＡＢを含む建物の左側面の平面方程式を算出できる。
【００４３】
第１  ３次元モデル生成部１６は、２次元実写映像のデータ及び面情報算出部１５により算出された面幾何情報を利用して、現在の客体に対する３次元モデルを生成する。ここで、２次元実写映像のデータは、２次元実写映像を構成する画素の２次元座標値及びテクスチャーを意味し、面情報算出部１５により算出された面幾何情報は、その面の平面方程式を意味する。さらに詳細に説明すれば、第１  ３次元モデル生成部１６は、面情報算出部１５により算出された各面の平面方程式に、２次元実写映像の現在の客体を構成する画素の２次元座標値、すなわちｘ座標値、ｙ座標値を代入することによって、現在の客体の各面を構成する画素の３次元座標値、すなわちｘ座標値、ｙ座標値、ｚ座標値を算出する。また、第１  ３次元モデル生成部１６は、このように算出された現在の客体の各面を構成する画素の３次元座標値ごとに、この画素それぞれに対応する２次元実写映像のテクスチャーをマッピングすることによって、３次元客体に対する３次元モデルを生成する。
【００４４】
図１０は、図１に示した第１  ３次元モデル生成部１６でのテクスチャーマッピング方式を示す図である。図１０に示すように、第１  ３次元モデル生成部１６は、現在の客体の各面を構成する画素の３次元座標値ごとに、現在の客体の各面に対向するカメラにより撮影されたテクスチャーをマッピングする。さらに詳細に説明すれば、第１  ３次元モデル生成部１６は、カメラが現在の客体１０１の左側面１０２に対しては左側面１０２に対向するようにカメラの位置を設定し、このように設定された位置のカメラにより撮影された２次元実写映像のテクスチャーを左側面１０２にマッピングし、カメラが現在の客体１０１の右側面１０３に対しては右側面１０３に対向するようにカメラの位置を設定し、このように設定された位置のカメラにより撮影された２次元実写映像のテクスチャーを右側面１０３にマッピングする。
【００４５】
第２  ３次元モデル生成部１７は、客体分類部１４により現在の客体が複雑な客体に分類された場合、前述した本実施形態による３次元モデリング方式でない従来の３次元モデリング方式を利用して、現在の客体に対する３次元モデルを生成する。例えば、第２  ３次元モデル生成部１７は、客体分類部１４により複雑な客体に分類された客体に対しては、本明細書の従来技術部分で説明されたオートポップアップアルゴリズムを利用して、この客体に対する３次元モデルを生成できる。
【００４６】
図１１は、本発明の望ましい一実施形態による３次元モデルの生成方法のフローチャートである。図１１に示すように、本実施形態による３次元モデルの生成方法は、図１に示した３次元モデル生成装置で時系列的に処理されるステップで構成される。したがって、以下で省略した内容であっても、図１に示した３次元モデル生成装置に関して前述した内容は、本実施形態による３次元モデルの生成方法にも適用される。
【００４７】
ステップ１１１で、３次元モデル生成装置は、２次元実写映像内のテクスチャーの変化及びユーザーインターフェース１２に入力されたユーザー入力情報のうち少なくとも一つ以上に基づいて、２次元実写映像を構成する少なくとも一つ以上の客体を特定する。
【００４８】
ステップ１１２で、３次元モデル生成装置は、ステップ１１１で特定された少なくとも一つ以上の客体のうち現在の客体内で、光度の変化が臨界値以上である地点を表すエッジを検出する。
【００４９】
ステップ１１３で、３次元モデル生成装置は、ステップ１１２で検出されたエッジの延長線の形態に基づいて、現在の客体の複雑度を決定し、このように決定された現在の客体の複雑度によって、現在の客体を簡単な客体及び複雑な客体のうちいずれか一つに分類する。
【００５０】
ステップ１１４で、３次元モデル生成装置は、ステップ１１３で現在の客体が簡単な客体に分類された場合には、ステップ１１５に進み、ステップ１１３で現在の客体が複雑な客体に分類された場合には、ステップ１１８に進む。
【００５１】
ステップ１１５で、３次元モデル生成装置は、ステップ１１２で検出されたエッジの延長線が交差する地点である少なくとも一つ以上の消失点を検出し、このように検出された消失点に収斂するエッジ延長線のうち中間線の直線方程式と、この消失点に対応する面の下線上の任意の一地点の座標値とを利用して、この消失点に対応する客体の面の平面方程式を算出する。
【００５２】
ステップ１１６で、３次元モデル生成装置は、ステップ１１５で算出された各面の平面方程式に、２次元実写映像の現在の客体を構成する画素の２次元座標値、すなわちｘ座標値、ｙ座標値を代入することによって、現在の客体の各面を構成する画素の３次元座標値、すなわちｘ座標値、ｙ座標値、ｚ座標値を算出する。
【００５３】
ステップ１１７で、３次元モデル生成装置は、ステップ１１６で算出された現在の客体の各面を構成する画素の３次元座標値ごとに、この画素それぞれに対応する２次元実写映像のテクスチャーをマッピングすることによって、３次元客体に対する３次元モデルを生成する。
【００５４】
ステップ１１８で、３次元モデル生成装置は、前述した本実施形態による３次元モデリング方式でない従来の３次元モデリング方式を利用して、現在の客体に対する３次元モデルを生成する。
【００５５】
図１２は、図１に示した３次元モデル生成装置を使用したナビゲーションシステムの構成図である。図１２に示すように、図１に示した３次元モデル生成装置を使用したナビゲーションシステムは、カメラ１２１、３次元モデル生成装置１２２、メモリ１２３、ＧＰＳ（Ｇｌｏｂａｌ  Ｐｏｓｉｔｉｏｎｉｎｇ  Ｓｙｓｔｅｍ）１２４、レンダリング装置１２５及びディスプレイ装置１２６から構成される。３次元モデル生成装置１２２は、図１に示した３次元モデル生成装置と同じものであり、これに関する詳細な説明は、前述したので省略する。
【００５６】
カメラ１２１は、実際の世界のいずれか一つの場面を撮影することによって、２次元実写映像を生成する。カメラ１２１は、移動体（例えば、自動車）の進行方向に該当する場面が撮影されるように、移動体の前部分に設置されねばならない。
【００５７】
３次元モデル生成装置１２２は、カメラ１２１により生成された２次元実写映像を構成する客体のうちいずれか一つの客体内で、映像情報の変化が臨界値以上である地点に該当するエッジの延長線が交差する地点に基づいて、前記客体の面の幾何情報を算出することによって、前記客体に対する３次元モデルを生成する。
【００５８】
メモリ１２３は、３次元モデル生成装置１２２により生成された３次元モデルを保存する。したがって、メモリ１２３には、カメラ１２２により撮影された２次元実写映像それぞれに対する３次元モデルが保存されている。
【００５９】
ただし、本実施形態によるナビゲーションシステムは、カメラ１２１、３次元モデル生成装置１２２を備えず、本実施形態によるナビゲーションシステムでない他の装置であらかじめ生成された３次元モデルが保存されたメモリ１２３のみを備えることもできるということを当業者ならば理解できる。しかし、本実施形態による３次元モデル生成装置１２２は、３次元幾何情報の算出のための計算が簡単であるため、移動体が移動可能なあらゆる地域の３次元モデルが保存された大容量のメモリを備えず、移動体が現在に位置した場面の２次元実写映像を直ちに３次元モデリングし、メモリ１２３に保存された３次元モデルのうち移動体から遠くなった地域の３次元モデルを削除することによって、少容量のメモリのみでも十分でありうる。
【００６０】
ＧＰＳ  １２４は、少なくとも一つ以上のＧＰＳ衛星から移動体に装着されたナビゲーションシステムの現在位置情報を受信する。
【００６１】
レンダリング装置１２５は、メモリ１２３に保存された３次元モデルのうち、ＧＰＳ  １２４により受信されたナビゲーションシステムの現在位置情報に該当する３次元モデルを抽出し、このように抽出された３次元モデルをナビゲーションシステムが装着された移動体の進行方向に該当する２次元平面上にレンダリングする。
【００６２】
ディスプレイ装置１２６は、レンダリング装置１２５によりレンダリングされた結果をディスプレイする。
【００６３】
図１３は、本発明の望ましい一実施形態によるナビゲーション方法のフローチャートである。図１３に示すように、本実施形態によるナビゲーション方法は、図１２に示したナビゲーションシステムで時系列的に処理されるステップで構成される。したがって、以下で省略した内容であっても、図１２に示したナビゲーションシステムに関して前述した内容は、本実施形態によるナビゲーション方法にも適用される。
【００６４】
ステップ１３１で、ナビゲーションシステムは、実際の世界のいずれか一つの場面を撮影することによって、２次元実写映像を生成する。
【００６５】
ステップ１３２で、ナビゲーションシステムは、ステップ１３１で生成された２次元実写映像を構成する客体のうちいずれか一つの客体内で、映像情報の変化が臨界値以上である地点に該当するエッジの延長線が交差する地点に基づいて、前記客体の面の幾何情報を算出することによって、前記客体に対する３次元モデルを生成する。
【００６６】
ステップ１３３で、ナビゲーションシステムは、ステップ１３２で生成された３次元モデルを保存する。
【００６７】
ステップ１３４で、ナビゲーションシステムは、少なくとも一つ以上のＧＰＳ衛星から移動体に装着されたナビゲーションシステムの現在位置情報を受信する。
【００６８】
ステップ１３５で、ナビゲーションシステムは、ステップ１３３で保存された３次元モデルを含む３次元モデルのうち、ステップ１３４で受信されたナビゲーションシステムの現在位置情報に該当する３次元モデルを抽出し、このように抽出された３次元モデルをナビゲーションシステムが装着された移動体の進行方向に該当する２次元平面上にレンダリングする。
【００６９】
ステップ１３６で、ナビゲーションシステムは、ステップ１３５でレンダリングされた結果をディスプレイする。
【００７０】
一方、前述した本発明の実施形態は、コンピュータで実行できるプログラムで作成可能であり、コンピュータで読み取り可能な記録媒体を利用して、前記プログラムを動作させる汎用デジタルコンピュータで具現されうる。また、前述した本発明の実施形態で使われたデータの構造は、コンピュータで読み取り可能な記録媒体に色々な手段を通じて記録される。前記コンピュータで読み取り可能な記録媒体は、磁気記録媒体（例えば、ＲＯＭ（リードオンリメモリ）、フロッピー（登録商標）ディスク、ハードディスクなど）、光学的な読み取り媒体（例えば、ＣＤ−ＲＯＭ、ＤＶＤなど）のような記録媒体を含む。
【００７１】
これまで、本発明について、その望ましい実施形態を中心に述べた。当業者は、本発明が、本発明の本質的な特性から逸脱しない範囲で変形された形態に具現可能であるということを理解できるであろう。したがって、開示された実施形態は、限定的な観点ではなく、説明的な観点で考慮されねばならない。本発明の範囲は、前述した説明ではなく、特許請求の範囲に表れており、それと同等な範囲内にあるあらゆる相違点は、本発明に含まれていると解釈されねばならない。
【産業上の利用可能性】
【００７２】
本発明は、２次元実写映像から３次元モデルを生成する装置及び方法関連の技術、例えばナビゲーションシステムなどに適用可能である。
【図面の簡単な説明】
【００７３】
【図１】本発明の望ましい一実施形態による３次元モデル生成装置の構成図である。
【図２】図１に示した客体特定部が自動的に客体を特定する場合を示す図である。
【図３】図１に示した客体特定部が半自動的に客体を特定する場合を示す図である。
【図４Ａ】図１に示した客体分類部での客体分類過程を示す図である。
【図４Ｂ】図１に示した客体分類部での客体分類過程を示す図である。
【図４Ｃ】図１に示した客体分類部での客体分類過程を示す図である。
【図５】３次元空間での正六面体に対する２点透視図である。
【図６】図１に示した面情報算出部での面幾何情報算出方式を説明するための建物を示す図である。
【図７】図１に示した面情報算出部での面幾何情報算出方式を説明するための建物を示す図である。
【図８】図１に示した面情報算出部でのいずれか一面の平面方程式を算出する方式を示す図である。
【図９】図１に示した面情報算出部でのいずれか一面の平面方程式を算出する方式を示す図である。
【図１０】図１に示した第１  ３次元モデル生成部でのテクスチャーマッピング方式を示す図である。
【図１１】本発明の望ましい一実施形態による３次元モデル生成方法のフローチャートである。
【図１２】図１に示した３次元モデル生成装置を使用したナビゲーションシステムの構成図である。
【図１３】本発明の望ましい一実施形態によるナビゲーション方法のフローチャートである。
【符号の説明】
【００７４】
１１    客体特定部
１２    ユーザーインターフェース
１３    エッジ検出部
１４    客体分類部
１５    面情報算出部
１６    第１  ３次元モデル生成部
１７    第２  ３次元モデル生成部
１２１  カメラ
１２２  ３次元モデル生成装置
１２３  メモリ
１２４  ＧＰＳ
１２５  レンダリング装置
１２６  ディスプレイ装置
【図１】
2008204458.tif 000003
【図５】
2008204458.tif 000004
【図９】
2008204458.tif 000005
【図１１】
2008204458.tif 000006
【図１２】
2008204458.tif 000007
【図１３】
2008204458.tif 000008
【図２】
2008204458.tif 000009
【図３】
2008204458.tif 000010
【図４Ａ】
2008204458.tif 000011
【図４Ｂ】
2008204458.tif 000012
【図４Ｃ】
2008204458.tif 000013
【図６】
2008204458.tif 000014
【図７】
2008204458.tif 000015
【図８】
2008204458.tif 000016
【図１０】
2008204458.tif 000017