三次元地図自動生成装置
【課題】 カメラで撮影した映像を解析して三次元情報を抽出し、画像処理技術により三次元地図を自動生成する。
【解決手段】 車両等に積載されたカメラにより対象物と背景の動画像を取得する動画像取得装置１と、動画像の背景と対象物に固定された静止座標系に対するカメラの三次元位置及び三軸回転姿勢を示すＣＶ値を求めて動画像の各フレームと対応させたＣＶ映像を生成するＣＶ映像生成装置２と、ＣＶ映像から画像フレームを取り出し画像中の対象物及び背景を複数の領域分割画像に分割する領域分割装置３と、領域分割画像に対応するＣＶ映像のフレーム内小領域中の複数の特徴点の三次元座標を求めるフレーム内小領域特徴点三次元化装置４と、複数の特徴点の三次元座標からフレーム内小領域の面を抽出して複数のポリゴンを自動生成する複数領域ポリゴン化装置５を備える。
【解決手段】 車両等に積載されたカメラにより対象物と背景の動画像を取得する動画像取得装置１と、動画像の背景と対象物に固定された静止座標系に対するカメラの三次元位置及び三軸回転姿勢を示すＣＶ値を求めて動画像の各フレームと対応させたＣＶ映像を生成するＣＶ映像生成装置２と、ＣＶ映像から画像フレームを取り出し画像中の対象物及び背景を複数の領域分割画像に分割する領域分割装置３と、領域分割画像に対応するＣＶ映像のフレーム内小領域中の複数の特徴点の三次元座標を求めるフレーム内小領域特徴点三次元化装置４と、複数の特徴点の三次元座標からフレーム内小領域の面を抽出して複数のポリゴンを自動生成する複数領域ポリゴン化装置５を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、機械が人に代わって位置等を判断する為の機械地図装置やカーナビゲーション装置などにおいて、対象物を三次元的に表示する三次元地図を自動生成するための三次元地図自動生成装置に関する。
【背景技術】
【０００２】
機械地図装置やカーナビゲーション装置などにおいては、対象物を三次元的に表示する三次元地図の生成技術が利用されている。
三次元地図では、例えば道路や建物などの対象物について高さ方向を含む立体的な三次元情報が表示されるため、対象物を容易かつ正確に把握することができ、二次元地図では得られない有用な地図情報が得られるようになる。
【０００３】
従来の三次元地図自動生成の技術としては、航空機からレーザーなどで地表を測量し、地表の三次元データを取得して、地上から撮影した視差による三次元データと組み合わせて詳細部分を計測し、それから３ＤＣＧ（コンピュータグラフィックス）を生成し、さらに地上から撮影した対象物のテクスチャーを切り取って３ＤＣＧに貼り付ける等の処理によって生成していた（特許文献１−３参照。）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０００−０６６５８３号公報
【特許文献２】特開２００２−０９８５３８号公報
【特許文献３】特開２００３−１１４６１４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記のような従来の三次元地図自動生成の技術では、三次元地図の生成を手動で行っており、三次元地図生成の自動化が進まないために、莫大なコストがかかるという問題があった。
すなわち、上記のような従来の三次元地図の技術では、高価な機器を必要とし、しかも、膨大な手間と費用をかけなければ三次元地図を作成できないという問題があった。特に、従来の技術では、地図や画像を人間が見ながら、手動でポリゴンを指定しなければならないので、時間と人手が係り、コストがかかることになっていた。
また、そのようにして生成される三次元地図は、点や線のみで表示される構成で、それなりの長所もあるものの、人間が見るためには適さないという欠点もあった。
【０００６】
ここで、通常の安価なカメラで撮影される映像であっても、映像は三次元情報を含んでおり、そこから三次元地図の生成に必要となる三次元情報を抽出することは可能であり、また、二台のカメラで撮影した視差から三次元情報を抽出することも可能であった。従って、通常のカメラを車両などに搭載して移動しながら対象物を撮影し、そこから三次元情報を抽出して三次元地図を生成することは、理論上は可能である。
しかしながら、単に通常のカメラで映像を撮影しただけでは、撮影するカメラが移動するために、揺れ等の外乱を受け、座標がぶれ、回転し、位置として安定な映像を取得，抽出できず、それだけでは三次元情報を高精度に抽出することはできない。
【０００７】
特に、カメラ位置とカメラ姿勢は、カメラを搭載した車両等の移動につれて刻々変化するので、その三次元位置を精度良く計測できなければならない。また、カメラの３軸方向の回転と移動を正確に抽出できなければ、精度の良い三次元地図を生成することはできない。
また、二台のカメラで撮影した、いわゆるステレオカメラによる視差からの三次元抽出では、静止カメラでは可能であっても、車載による車両移動にともなうカメラ移動には追従できないことになり、カメラからの距離は計測できても、カメラ移動にともなう画像内の三次元解析は一般には出来ない。
【０００８】
この欠点を補うための既知の技術としては、ＧＰＳやＩＭＵ、ジャイロ、レーザー等のセンサーにより、カメラ移動をこれら機械センサーで計測して、刻々移動するカメラ位置を追跡する方法があるが、この装置は高価で、大がかりで、しかも不安定で、しかも使用には様々な制限があり、実用的ではない。
ＧＰＳ、ＩＭＵ、ジャイロ等の機械センサーを用いたとしても、それはカメラ位置のデータであり、画像内に移り込んでいる対象物のデータではない。このため、結局は画像解析が必要となるため、機械センサーとカメラの同期、位置合わせ等にかなりの労力が必要となり、しかも光学系・機械系の双方を含むため、外乱に対して不安定で、振動に弱く、カメラ移動カメラ進行方向、及び遠方の対象物に対する精度に限界があった。
また、レーザーや機械センサーで一度取得したデータに誤差が含まれていれば、その後の処理での修正は原理的にほとんど不可能である。
【０００９】
また、カメラで得られた映像から三次元形状を生成する場合、三次元形状を構成するポリゴンの抽出には、どうしても手動によるポリゴン生成のプロセスは避けられず、その部分が費用増大を招き、特に大規模に三次元地図を生成することは事実上不可能であった。すなわち、従来の三次元地図の生成技術においては、人間でなければ対象物のポリゴンをうまく認識して取得することはできず、特に都市空間ほどの大規模な三次元地図等に対するポリゴン生成は現実の実施はきわめて困難であった。
【００１０】
また、レーザーによる三次元計測も行われるようになっているが、レーザーで行われるのは、対象物の面までの距離の計測であり、対象物の形状の計測ではないため、境界線を抽出できず、対象物の形状を精度良く取得することはできなかった。
さらに、従来の三次元地図の生成技術において、個々にＣＧを生成してそれを地図中に結合しても、整合が取れず、例えば大規模な都市構造をＣＧ化するようなことは困難であった。
そこで、本願発明者は、鋭意研究の結果、上記のような機械センサーを用いることなく、また、機械センサーを用いたとしても、概略値を知るために補助的に用いる程度で、本質的には画像のみから画像解析を行うことにより三次元地図の自動生成を可能とする本願発明に想到したものである。
【００１１】
すなわち、本願発明は上述したような従来の技術が有する問題を解決するために提案されたものであり、高価な機器を必要とせず、安価なカメラで、複数のカメラ（原理的には一台のカメラ）を車両に積載して周辺状況を撮影し、あるいは人がカメラを手に持って周囲を撮影し、その映像を解析して、そこから三次元情報を抽出して、画像処理技術により三次元形状を生成し、三次元地図を自動生成することができる三次元地図自動生成装置の提供を目的とする。
【課題を解決するための手段】
【００１２】
上記目的を達成するため、本発明の三次元地図自動生成装置は、動画映像の複数のフレーム画像から充分な数の特徴点を自動検出し、さらに、各フレーム間で特徴点を自動追跡し、多数の特徴点について重複演算してカメラ位置と回転角を高精度に求め、それを統計的処理により、また、三次元解析処理することにより、さらに画像を前もって領域に自動分割することによって、自動的に分割された画像から、精度の良い三次元データを抽出するものである。
しかも、領域の自動抽出から、その領域内の三次元特徴点を解析することで、ポリゴンを自動生成することにより、高精度にポリゴンを生成し、高精度な三次元地図を完全自動により生成するものである。
【００１３】
三次元地図を自動的に低コストで効率よく生成するためには、画像を自動的に三次元解析することと、画像を効率的に領域に分割し、その領域を結合し、又は統合して、自動的に効率よく目的のポリゴンを生成することが求められる。
そこで、本発明の三次元地図自動生成装置は、以下のような構成を備えるようになっている。
【００１４】
第一に、移動体に設置された動画又は連続静止画を得るカメラからの映像を取得する動画像取得装置を備えている。
また、動画像取得部で取得された動画像を自動三次元解析するために、多くの特徴点を自動発生させ、その特徴点を隣接するフレームに自動トラッキングし、そのトラッキングデータから、対象物及び背景の座標計に対するカメラの位置と姿勢を六変数で取得する所定のカメラベクトル映像（ＣＶ映像）を自動生成するＣＶ映像生成装置を備える。
さらに、このＣＶ映像又はその元となる動画映像から色又は明るさの変化するラインを境界とする領域に自動分割する領域分割装置を備える。
【００１５】
領域に分割された各領域はＣＶ映像の一部であることから、既に既知となっているＣＶ値から領域分割された個々の領域を自動三次元解析して、あるいは詳細に解析するために、新たに個々の領域に特徴点を集中的に自動発生させ、それを自動トラッキングし、そこからＣＶ値を求めるプロセスを繰り返して、各領域の三次元形状を自動的に求めることができる。
そして、各領域の三次元形状を結合する過程で、ポリゴンを取得する。このポリゴンを座標上に配列することで求める三次元地図が取得できる。
【００１６】
以上のような本発明の三次元形状生成装置によれば、機械センサーを使用せず、動画像のみから三次元解析を通して、機械地図を生成することが可能となる。機械センサーを使用するとしても、概略位置のデータとして使用する程度であり、本質的なものではない。
動画映像の複数のフレーム画像から充分な数の特徴点を自動検出し、各フレーム間で特徴点を自動トラッキング（追跡）することにより、多数の特徴点について重複演算してカメラ位置と回転角を高精度に求めることができる。従って、通常の安価なカメラであっても、人がカメラをもって移動しながら撮影し、あるいはカメラを積載した移動する車両等から周囲画像を撮影し、その映像を分析してカメラ軌跡を三次元位置と三軸姿勢の六変数で求めることができる。
【００１７】
そして、その三次元位置と三軸姿勢の六変数のカメラパラメータを基準として、カメラ映像内の複数の領域を抽出し、その領域を三次元解析して、それらの三次元解析された領域から対象物、及び背景の三次元形状を再構成することで、対象物の三次元形状を表現し、それを連続して実施することで三次元地図を自動生成することができる。
これにより、従来技術のような高価な機器や膨大な手間と費用を必要とすることなく、安価かつ高精度に三次元地図を生成することができる。
【００１８】
なお、本発明は、移動するカメラによって得られる映像のみでなく、並列に設置した二台のカメラによるＣＶ映像からの情報を併用することも勿論可能である。さらには複数台のカメラを用いて、精度を向上させることも可能である。
機械センサーのデータ取得は一度限りであるが、本発明は機械センサーによらないので、設置が簡単であること、画像から三次元データを解析するので、データ画像が有ればいつでもどこでも目的に応じた解析を何度でも繰り返すことができる、というメリットがある。例えば、精度が必要であれば、特徴点を増加させて、最演算することで、精度の高いＣＶ値を必要に応じて取得できること。カメラ位置は画像から取得されるので、カメラ位置と同時に、映像に映り込んでいる対象物及び背景を同時に三次元解析できること。これは機械センサーにはできないことである。
また、異なる日時に撮影した映像であっても、それぞれの映像のＣＶ値を座標統合することで、追加撮影された映像を複合的に扱うことが可能である。
【００１９】
機械センサーに比較して軽量である。原理的にカメラだけでも良いので、単純である。映像からデータを演算で求めるので、極端な振動に対しても、追従することから、振動にもきわめて強い。振動によってデータが狂うことはない。
映像から取得するので、広範囲に撮影された地域でバラバラに取得された映像を一気に処理して、機械センサーの場合のように、いちいちキャリブレーションする必要もない。決められた座標系で目的にあわせて表現することが可能となる。ＣＶ映像さえ取得できれば、いかなる種類の映像でも利用できるので、安価に広範囲な地域を一気に三次元化することが可能となる。
【００２０】
以上のように、本発明の三次元地図自動生成装置によれば、カメラで得られる動画又は連続静止画の映像に基づいて、対象物、及びその背景を含めて、その三次元形状を求め、必要であればそのテクスチャーを自動的に取得して、三次元地図を自動的に生成することができる。
特に、本発明では、高価な機器や膨大な手間と費用などを必要とすることなく、完全自動により、背景を含めた対象物との座標を矛盾無く整合して、簡易かつ高精度に、三次元形状を求めて、大規模に三次元地図を生成することができる。
【００２１】
このように、本発明によれば、三次元形状、及び背景との座標関係に矛盾が無いように、高精度の三次元地図を生成でき、また、人間が見るための地図としても十分な品質のものが得られる。
従って、本発明は、自動車、重機、航空機等の移動体の三次元位置を自動評定したり、移動体の進行方向や現在状況等を自動ガイドするための三次元地図と、その三次元地図自動生成装置として好適に利用することができる。
【発明の効果】
【００２２】
本発明の三次元地図自動生成装置によれば、高価な機器を必要とせず、安価なカメラで、複数のカメラ（原理的には一台のカメラ）を車両に積載して周辺状況を撮影し、あるいは人がカメラを手に持って周囲を撮影し、その映像を解析して、そこから三次元情報を抽出して、画像処理技術により三次元形状を生成し、三次元地図を自動生成することができる。
【図面の簡単な説明】
【００２３】
【図１】本発明の一実施形態に係る三次元地図自動生成装置の構成を示すブロック図である。
【図２】本発明の一実施形態に係る三次元地図自動生成装置で行われるＣＶ演算の概念を示す説明図である。
【図３】本発明の一実施形態に係る三次元地図自動生成装置で行われるＣＶ演算の概念を示す説明図である。
【図４】本発明の一実施形態に係る三次元地図自動生成装置で行われる三次元地図の生成処理を模式的に示す説明図である。
【図５】本発明の一実施形態に係る三次元地図自動生成装置で行われる三次元地図の生成処理を模式的に示す説明図である。
【図６】本発明の他の実施形態に係る三次元地図自動生成装置の構成を示すブロック図である。
【図７】本発明の三次元地図自動生成装置のＣＶ映像生成装置（ＣＶ演算装置）として機能するＣＶ演算部の一実施形態の基本構成を示すブロック図である。
【図８】図７に示すＣＶ演算部で使用する全周ビデオ映像を撮影する手段を示す概略図であり、屋根部に全周カメラを搭載した車輌の斜視図である。
【図９】図７に示すＣＶ演算部で使用する全周ビデオ映像を撮影する手段を示す概略図であり、（ａ）は屋根部に全周カメラを搭載した車輌の正面図、（ｂ）は同じく平面図である。
【図１０】全周カメラで撮影される映像から得られる変換画像を示す説明図であり、（ａ）は球面画像が貼り付けられる仮想球面を、（ｂ）は仮想球面に貼り付けられた球面画像の一例を、（ｃ）は（ｂ）に示した球面画像をメルカトール図法に従って平面展開した画像を示している。
【図１１】本発明の一実施形態に係るＣＶ演算部における具体的なカメラベクトルの検出方法を示す説明図である。
【図１２】本発明の一実施形態に係るＣＶ演算部における具体的なカメラベクトルの検出方法を示す説明図である。
【図１３】本発明の一実施形態に係るＣＶ演算部における具体的なカメラベクトルの検出方法を示す説明図である。
【図１４】本発明の一実施形態に係るＣＶ演算部によるカメラベクトルの検出方法における望ましい特徴点の指定態様を示す説明図である。
【図１５】本発明の一実施形態に係るＣＶ演算部により得られる特徴点の三次元座標とカメラベクトルの例を示すグラフである。
【図１６】本発明の一実施形態に係るＣＶ演算部により得られる特徴点の三次元座標とカメラベクトルの例を示すグラフである。
【図１７】本発明の一実施形態に係るＣＶデータ演算部により得られる特徴点の三次元座標とカメラベクトルの例を示すグラフである。
【図１８】本発明の一実施形態に係るＣＶ演算部において、カメラから特徴点の距離に応じて複数の特徴点を設定し、複数の演算を繰り返し行う場合を示す説明図である。
【図１９】本発明の一実施形態に係るＣＶデータ演算部求められたカメラベクトルの軌跡をビデオ映像中に表示した場合の図である。
【発明を実施するための形態】
【００２４】
以下、本発明に係る三次元地図自動生成装置の実施形態について、図面を参照しつつ説明する。
ここで、以下に示す本発明の三次元地図自動生成装置は、プログラム（ソフトウェア）の命令によりコンピュータで実行される処理，手段，機能によって実現される。プログラムは、コンピュータの各構成要素に指令を送り、以下に示すような所定の処理や機能、例えば、映像中からの基準点や特徴点の自動抽出，抽出した基準点の自動追跡，基準点の三次元座標の算出，ＣＶ（カメラベクトル）値の演算等を行わせる。
このように、本発明における各処理や手段は、プログラムとコンピュータとが協働した具体的手段によって実現される。なお、プログラムの全部又は一部は、例えば、磁気ディスク，光ディスク，半導体メモリ，その他任意のコンピュータで読取り可能な記録媒体により提供され、記録媒体から読み出されたプログラムがコンピュータにインストールされて実行される。また、プログラムは、記録媒体を介さず、通信回線を通じて直接にコンピュータにロードし実行することもできる。
【００２５】
［三次元地図自動生成装置］
まず、図１を参照して、本発明の一実施形態に係る三次元地図自動生成装置１００の概略構成を説明する。
図１は、本発明の一実施形態に係る三次元地図自動生成装置１００の構成を示すブロック図である。
同図に示すように、本実施形態に係る三次元地図自動生成装置１００は、動画像取得装置１、ＣＶ映像生成装置２、領域分割装置３、フレーム内小領域特徴点三次元化装置４、複数領域ポリゴン化装置５、連続処理装置６、及びテクスチャー取得装置７の各部を備えた構成となっている。
【００２６】
動画像取得装置１は、移動する撮影車両に積載された全周カメラにより（後述する図８、図９参照）、周囲の対象物及びその背景の動画像を取得する画像取得手段である。
ここで、動画像取得装置１が搭載される撮影車両としては、一般的には自動車が想定されるが、移動車両（移動体）は航空機であっても船舶であっても考え方は同じである。
また、動画像取得用のカメラは、必ずしも全周カメラでなくても良いが、誤差を少なくするためには全周カメラが望ましい。通常のカメラの場合は、得られた映像は全周カメラから得られた映像の一部の映像として扱うことで、全周カメラと同じように扱うことができる。
【００２７】
ＣＶ映像生成装置２は、動画像取得装置１によって取得された動画像から、映像に映っている背景と対象物に固定された静止座標系に対して移動しているカメラ位置とカメラ姿勢を、前記静止座標系に対する三次元位置、三軸回転姿勢を示す六変数（X,Y,Z,θx,θy,θz）、すなわちカメラベクトル値（ＣＶ値）を後述するＣＶ演算装置（図６に示すＣＶ演算装置２１参照）により自動演算で求め、そのＣＶ値を動画像取得装置１で得られた動画像の各フレームと対応させたカメラベクトル映像（ＣＶ映像）を生成する。
【００２８】
ここで、全周カメラによるＣＶ値及び全周カメラからＣＶ値を求めるＣＶ演算については、本発明者が既に特許取得している特許（特許第４４４６０４１号）に詳細に記載されているが、全周映像の中に特徴点を自動抽出し、それを隣接する複数フレームにトラッキングし、カメラ移動のベースとトラッキング点で校正する三角形を構成し、そのトラッキングデータを解析することで、特徴点の三次元座標と、カメラ位置と姿勢を持つ全周ＣＶ映像を取得することができる。ＣＶ値とは、カメラの位置と姿勢を６自由度（六変数と同義）で表現したものである。即ち、全フレームについてｘ，ｙ，ｚ，θx，θy，θz，の６自由度のそれぞれの係数を演算で決定することになる。
【００２９】
具体的には、ＣＶ（Camera Vector）値というのは、カメラの焦点の三次元位置Ｔと三次元姿勢Ｒを合わせた6自由度の量のことであり、実際にカメラで撮影した映像情報だけを用いて、２次元的な画像解析によりＣＶ値を統計的に算出する、つまりＣＶ演算することが可能である。
ＣＶ値を持った映像（ＣＶ映像）では、２次元の映像内に映っている全ての対象物について、３次元空間解析が可能となる。これにより、あたかも現実のコピーのように、３次元位置を特定したり、距離や長さを計測したりすることができるようになる。
これらＣＶ演算及びＣＶ映像を用いた３次元空間解析技術を総称してＣＶ技術といい、このＣＶ技術が本発明に係る三次元地図自動生成装置１００の基礎となるものである。
【００３０】
ＣＶ演算は、一般のカメラでも可能ではあるが、処理をシンプルにするために、通常は全周カメラを用いることが望ましい。全周カメラの場合、撮影された映像は焦点を中心に全天球を覆うことなる（全周映像：図２左側図参照）。この映像を、正距円筒図法を用い平面で展開すると図２右側のような画像となる。
これを式で表すと下記の式１のようになる。
【００３１】
【数１】
【００３２】
ＣＶ技術においては、全周映像の特徴点トラッキング処理が行われる。
具体的には、動画の各フレーム画像を２次元に解析し特徴点を抽出し、複数のフレーム間で同一の特徴点を画像比較により見つける。これを特徴点トラッキングと呼ぶ。
同一特徴点の発見には、下記の式２に示したような相互関数（畳み込み）関数の最大になるところを探すことで見つけることができる。
コンピュータ上では、離散値である画像のピクセルにこれを適用するので、下記の式３が最大になるピクセル(x, y)を見つけることになる。
【００３３】
【数２】
【００３４】
【数３】
【００３５】
ＣＶ値の計算は以下のようにして行う。
特徴点の実際の三次元位置をＰ（３次元ベクトル）として表す。また、上述した通り、ｎ番目のフレームのＣＶ値は、三次元位置Ｔｎが３次元ベクトル、三次元姿勢Ｒｎが３行３列の回転行列で表される。これらは全て未知数である。
一方、ｎ番目のフレームでのトラッキング結果を、極座標変換して３次元ベクトルで表現し、Ｐｎとおく。既知の情報はこれだけである。
ＰとＴｎ、Ｒｎから計算される画像上の投影点がＰｎに重なるという条件から方程式を立てると下記の式４のようになる。ここでは長さを除いて方向が等しいことを意味している。
【００３６】
【数４】
【００３７】
この式４が特徴点の数（通常数百個）だけ成立する。
ここで、数学の記法により、上記のように簡潔に表現できるが、コンピュータ上で扱うためには膨大な数の連立方程式となる。実際には未知数の数以上に方程式があり、さらにそれぞれが微少な誤差を持っているため、厳密にはこの方程式の解は存在しないことになる。
そこで、本発明に係るＣＶ演算処理では、コンピュータによる連立方程式の解として、誤差を統計的に処理し、誤差が最小となる解（ＰとＴｎ、Ｒｎ）を求めるようにする。
【００３８】
以上のようなＣＶ演算及びＣＶ演算装置の詳細については後で更に詳述する（図７〜図１９参照）。
なお、ＣＶ映像は、カメラ位置とカメラ姿勢の六変数を各画像フレームに対応させたものであることから、ここに示したＣＶ演算による手法以外に、ＧＰＳ、ＩＭＵ、Ｊａｙｒｏ（ジャイロ）等の機械センサーによっても上記ＣＶ値と同等の六変数を取得することができる。
【００３９】
以上のようなＣＶ映像生成装置２で得られたＣＶ映像（動画）は、一般的に連続する多数の静止画フレームから成り立っている。
領域分割装置３は、このような多数のフレームの中から、コンピュータが自動的にある（特定の）フレームを選択し、指定した画像フレーム（静止画）を取り出し、その中に写っている複数の対象物及び背景を、画像の輝度分布等から、及び／又は色相分布、及び／又は彩度分布等から分類し、密度の固まりで切り取り、指定された大きさと数の範囲で、互いに隣接する複数の小領域に分割した領域分割画像を演算によって自動取得する。
【００４０】
ここで、上記のようにして得られる小領域は一般的に目的の対象物そのものでもなく、背景そのものでもない。
ここでは、小領域が目的の対象物を構成する複数のポリゴンそのもの、又はその一部となっていることを前提とする。最終的に小領域が対象物、及び背景のポリゴンとして適切であることが望ましい。
対象物を構成するポリゴンは、その選択の仕方によって幾通りも可能であるため、小領域がポリゴンの一部となることを期待することは特に非合理的ではない。
ただし、結果として、映像の輝度が飽和している場合や、非常に暗い場合には、この小領域が対象物の境界をまたいでしまうこともある。その時は、異なるフレームから取得した分割画像で再度、小領域を求めることで問題は解消できる。
【００４１】
なお、領域分割装置３における領域分割処理そのものは、既知の技術である。
ただし、既知の技術で得られた領域分割された画像が、ＣＶ映像から得られた領域分割画像であることから、すべての領域分割画像は、上述したＣＶ映像生成装置で得られたＣＶ映像のいずれかのフレームに対応している。
従って各領域分割画像はＣＶを持っていることになる。
このように、領域画像がＣＶ値を持つことが本発明における重要な特徴となる。
【００４２】
領域分割画像得るためには、例えば、既知の技術としてのヒストグラムの閾値処理手法がある。このヒストグラムの閾値処理手法はモノクロの画像の領域分割対して広く用いられている手法の一つであるが、三原色に分離された各原色に対しても有効である。
各原色の画像は異なる階調値の幅を持った領域から構成されると仮定し、入力画像のヒストグラムを分割領域に対応する幾つかのピークすなわち、分布の最頻値に分割することができる。二つの隣接するピーク間の「谷」に対する閾値を探索することで効果的に領域に分割することができる。
【００４３】
従って、既知の技術を用いて、最も明確に分離させるピークをもつヒストグラムを選択し、閾値処理を行うなどして、領域分割を行うことが可能である。
なお、ヒストグラム手法以外にはクラスタリング手法などがある。
いずれの手法であっても、元となる画像がＣＶ値を持っていることが本発明の特徴であり、以下に示すフレーム内小領域特徴点三次元化装置４による分割領域三次元化処理で、ＣＶ値を使って小領域を三次元化することが第二番目の重要な特徴となる。
【００４４】
フレーム内小領域特徴点三次元化装置４は、フレーム内小領域特徴点発生装置４１（図１参照）において、上記のような領域分割画像の小領域に対応しているフレーム内小領域に発生させた複数の特徴点を、フレーム内小領域でトラッキングし、複数特徴点の三次元座標を演算によって求め、領域分割画像内の小領域内に対応させて移転した特徴点の三次元座標に対応させる。
図４に示すように、ＣＶ映像の中から、自動的に指定された１フレームを取り出し（図４に示すフレーム１０２、１０４参照）、それが領域分割装置３に送られ、領域分割装置３によって領域分割が行われる（図４に示す領域分割画像１０３、１０５参照）。
【００４５】
ここで取得された領域分割画像内の1単位を小領域と定義する。一般に領域分割画像は複数の小領域から成り立っている。小領域はその境界が明確で閉じていることか望ましいが、一部閉じていない場合でも、一部境界を未知として扱うことで、本質的な問題は生じない。
ここで、上述した本発明の重要特徴である対応関係にあるＣＶ映像のフレームに戻り、そのフレームのＣＶ値を小領域のＣＶ値と定義できる。
この小領域は、その領域分割画像の生成過程に戻れば、ＣＶ映像上に常に対応がとれているので、小領域ＣＶ映像はＣＶ映像に戻って対応が取れていることになる。小領域に対応するＣＶ映像の１フレームの一部分をフレーム内小領域と定義する。
【００４６】
そこで、各小領域に対応するＣＶ映像内のフレーム内小領域を、当該ＣＶ映像のフレームのＣＶ値を既知として、フレーム内小領域に複数の特徴点を発生させる。当然、これらフレーム内小領域で発生させた特徴点は、対応する領域分割画像の小領域内にあることになる。
なお、ここでの特徴点は、ＣＶ映像を生成するために既に一度発生されているで、その時に発生させてある複数の特徴点をこの特徴点に追加させることも可能である。
そして、フレーム内小領域特徴点三次元化装置４では、このように当該領域分割画像の小領域に対応しているフレーム内小領域に発生させた複数の特徴点を、既知のＣＶ値を用いてトラッキングを予想し、フレーム内小領域でトラッキングし、複数特徴点の三次元座標を演算によって求め、領域分割画像内の小領域内に対応させて移転した特徴点の三次元座標に対応させる。
【００４７】
複数領域ポリゴン化装置５は、複数のフレーム内小領域の中で取得された複数の特徴点の三次元座標から、対応する小領域の面の法線を求め、面の形状を推定し、当該小領域を隣接小領域と統合又は分割するなどして、所望のポリゴンを推定して生成することができる。
そして、その作業を次々と隣接する複数の小領域に拡大し、可能な限りのポリゴンを自動生成することができる。
【００４８】
連続処理装置６は、上記のようなポリゴン生成までの処理を繰り返し実行することで、ポリゴンを順次生成し、目的の対象物と背景からなる三次元化地図を連続的に結合して、広範囲な三次元地図を自動生成する。
ここで、領域分割画像内のすべての小領域について、そのポリゴンを求めようとしても、画像が常に最適の状態ではないことがあり、全体の一部のポリゴンしか求められない場合がある。しかしながら、そのような場合でも、次に指定されるＣＶ映像のフレームには、重複して背景及び対象物が映っているので、一枚の領域分割画像からすべてのポリゴンを決定する必要はない。
【００４９】
そして、領域分割画像に対応しているＣＶ映像のフレームに関する処理により、適切な数の領域ポリゴン生成まで済んだところで、ＣＶ映像のフレームを進行させる。
次の新たな領域分割画像を自動指定して、上述した領域分割装置３、フレーム内小領域特徴点三次元化装置４、複数領域ポリゴン化装置５における処理を繰り返すことで、先の領域分割画像では未だ生成できていないポリゴンを生成することができる。そして、次の領域分割画像に初めて現れ、しかも一部取得済みのポリゴンに連続しているポリゴンを生成することができる。
【００５０】
さらに、次々に適切な時点で指定されるＣＶ映像のフレームから得られる領域画像から、ポリゴンを次々に生成し、目的の対象物と背景からなる三次元化地図を連続的に結合し、広範囲な三次元地図を自動生成する。
以上のような領域分割画像の指定からポリゴン生成までの処理が、連続処理装置６の制御により連続して繰り返し行われて、三次元地図が生成されることになる。
【００５１】
フレーム内小領域特徴点三次元化装置４は、図１に示すように、小領域境界特徴点発生装置４３と特徴点三次元化装置４２を備えている。
小領域境界特徴点発生装置４３は、領域分割装置３によって取得された領域分割画像内の小領域に対応するフレーム内小領域の中に、多くの特徴点を発生させる場合に、特にその小領域の境界付近に多くの特徴点を発生させる。
このようにすることで、領域の形状を含めて効率よく、精度良く三次元点を取得できるようになる。
【００５２】
また、特徴点三次元化装置４２は、領域分割画像に対応しているフレーム内小領域において、発生させた複数の特徴点を、既に既知となっているＣＶ値を用いて、複数の隣接フレームへの特徴点の移動を予測しながら、トラッキングすることで、複数の特徴点の三次元座標を取得する。
隣接フレーム間で特徴点をトラッキングする際、原理的に、ＣＶ値の分かっている画像における特徴点はエビポーラ線上を移動する。さらに、ＣＶ値が分かっているフレームにおいては、隣接の特徴点がトラッキングできた時点で、それ以降のフレームのトラッキングポイントはほぼ完璧に予想できる。
【００５３】
このようにＣＶ値の既知であるＣＶ映像内のフレーム内小領域を用いることの重要で優れた長所は、ライン上又は点上（きわめて狭い範囲上）にトラッキングポイントを予測できるために、ＣＶ値がない映像では、その点を他の方法では特徴点とは識別しないような場合にでも、特徴点として利用可能となることである。その結果、対象物のライン上に高密度に有効な特徴点をとることが可能となることである。
そこで、トラッキングするすべてのフレームにおいて、予想値付近に落ちるトラッキングポイントを確認し、さらに予想地点付近により完全に一致する点を微調整して求め、その点を正確なトラッキングポイントとして決定すればよいことになる。
特徴点三次元化装置４２は、このようにして、複数の隣接フレームへの特徴点の移動を予測しながらトラッキングすることで、複数の特徴点の三次元座標を取得する。
【００５４】
また、複数領域ポリゴン化装置５１は、領域面推定装置５１を備え、小領域三次元化装置によって取得された小領域内の複数の特徴点の三次元データに基づいて、所定の平面推定・直線推定・直角推定・水平推定・鉛直推定（図１に示す符号５２参照）等の各領域面の推定処理を行う。
具体的には、領域面推定装置５１は、単一平面を推定する平面推定、及び／又は複数平面を推定する複数平面推定、及び／又は小領域境界の直線を推定する直線推定、及び／又は複数平面のなす角度を推定する平面交差角推定、及び／又は面を長方形と推定してその長方形の辺の長さを推定する長方形推定、及び／又は平面の法線の鉛直及び水平を推定する平面鉛直水平推定を行う。
そして、このような領域面推定処理により、取得された小領域面の形状を絞り込むことができるようになっている。
【００５５】
特徴点の追跡結果は誤差を含んでいるため、誤差を除去することが好ましい。このような特徴点の追跡結果の誤差を除去しながら都合の良い特徴点のみを利用するアルゴリズムとしては、例えば、RANSAC、ロバスト推定、部分空間分離法等が知られている。本実施形態では、RANSACにより行うことが効率的である。
RANSAC (RANdom SAmple Consensus)は、面を推定して、その面に都合の良い特徴点のみを用いて面を推定することで、小領域の面を推定することができる既知の手法である。
但し、以上に示すように各種面（平面）や線の推定処理が行われる限り、RANSACに限らず、どのような手法・アルゴリズム等であっても用いることができる。
【００５６】
まず、複数領域ポリゴン化装置５の領域面推定装置５１は、前記小領域三次元化装置によって取得された、小領域内の複数の特徴点の三次元データから、単一平面を推定する（平面推定装置）。実際の対象物は曲面で有ることもしばしばあるが、その曲面の一部となる小領域を平面と推定することは合理的である。既に取得されている三次元特徴点の分布から、例えばRANSAC手法により、推定平面を取得できる。
同様に、領域面推定装置５１は、小領域が比較的大きめの場合は、複数の平面から成る面と推定することができる（複数平面装置）。その場合の手法としては、例えばRANSAC手法を繰り返し処理することにより、一個ずつ平面を決めて、結果として複数の平面を推定できる。
同様に、領域面推定装置５１は、RANSAC手法を面ではなく線に対応させることで、小領域境界線を直線と推定する（直線推定装置）。同様にRANSAC手法により直線推定装置を複数回通すことで、複数の直線からなる境界線を推定することができる。
【００５７】
また、実際のビルディング等においては、複数面が直角に交差していることが多いので、領域面推定装置５１は、RANSAC手法により、複数平面のなす角度をいろいろな値を入力することで、直角に交差する平面を推定できる（平面直角公差推定装置）。
また、領域面推定装置５１は、同様にRANSAC手法により、面を長方形と推定して、その長方形の辺の長さを推定することができる（長方形推定装置）。
さらに、実際の対象物や背景においては、水平面や鉛直面で構成されていることが多いので、領域面推定装置５１は、同様にRANSAC手法により、平面の法線の鉛直、水平を推定する（平面鉛直水平推定装置）。
以上のような面の推定処理により、取得された小領域面の形状を絞り込むことができる。
【００５８】
テクスチャー取得装置７は、上述した複数領域ポリゴン化装置５及び連続処理装置６によって取得された三次元ポリゴンに関して、自動的に対応するＣＶ映像のフレームから、テクスチャーを取得する。
これにより、テクスチャー付きのポリゴンを自動生成することができる。
このテスクチャー取得装置７については、更に具体的内容を後述する。
【００５９】
さらに、本実施形態では、移動体に対応させるために、図６に示す移動体対応三次元地図自動生成装置１００ａとして、フレーム内小領域特徴点三次元化装置４にＲＶ演算装置４６を有するＲＶ映像生成装置４７を備えることができる。
なお、図６に示す移動体対応三次元地図自動生成装置１００ａは、ＲＶ演算装置４６を有するＲＶ映像生成装置４７を備える点を除いては、上述した図１に示す三次元地図自動生成装置１００と同様となっている。
従って、図６中、図１と共通部分については共通の符号及び名称を使用しており、各部の構成・作用等の説明は図１に係るものを援用する。
【００６０】
図６に示すＲＶ演算装置４６は、フレーム内小領域特徴点三次元化装置４によって得られたフレーム内小領域の中に生成した複数の特徴点に対して、上述したＣＶ値を使わず、新たにＣＶ演算と同様の処理を行うことで、映像に映っている移動体対象物に固定された移動座標系に対して、さらに移動しているカメラ位置とカメラ姿勢を、前記移動座標系に対する三次元位置、三軸回転姿勢を示す六変数（Xr,Yr,Zr,φx,φy,φz）、すなわちＲＶ値を自動演算で求める。
ＲＶ映像生成装置４７は、ＲＶ演算装置４６で求められたそのＲＶ値を動画像の各フレームと対応させたＲＶ映像を生成する。
さらに、フレーム内小領域特徴点三次元化装置４には、同時に移動体の特徴点三次元座標を求める特徴点三次元化装置４２を備えることができる（図６参照）。
【００６１】
ここで、ＲＶ値とは、領域画像のカメラベクトル値（Regional Vector値）のことである。
カメラの位置及び姿勢とＣＶ領域画像において、カメラと画像との関係は相対的であり、カメラと画像の一部分の位置と姿勢の三次元ベクトルで表すことが可能である。このように、カメラと画像の一部分の三次元ベクトルをＲＶ値といい、その６自由度（六変数）を求めることをＲＶ演算、ＲＶ値を持つ映像をＲＶ映像という。
【００６２】
ＣＶ値とは、上述したように、静止座標系とその中を移動するカメラの位置と姿勢の関係を六変数として表現したものである。
ところで、静止座標系とその中を移動する移動座標系とは、物理的には相対的であり、数学的には、両者を物理的に区別することはできない。
例えば、走行する列車の中の座標系とその外側に展開する大地の座標系を物理的に区別することできない。従って列車の中を歩いて移動しながらカメラで撮影した映像のＣＶ値とは、車両の内側か、車両の外側かで、本質的に区別されるものではない。カメラが車両の中を移動する場合、車両の中を映している映像と、車両の外を映している映像、及び両方が同時に映っている映像に分類できるが、仮に外側を写している映像をＣＶ映像とするならば、車両の内側を写している映像はＲＶ映像と呼ぶことができる。ＲＶとは「Regional Vector」の頭文字で「領域画像ベクトル」の意である。
【００６３】
ただし、ＣＶ映像とＲＶ映像との間には物理的・数学的に本質的な差はない。列車の窓から外を見て、そこに特徴点を発生させて、外側との関係でカメラ位置を求め、同時にその三次元座標を求めようとする場合はＣＶ演算となり、ＣＶ映像となる。そして、列車の内側のみに特徴点を発生させて、その列車の内側との関係でカメラ位置を求め、同時にその三次元座標を求めようとするとＲＶ演算となり、ＲＶ映像となる。
このように、数学的には全く変わらないが、座標系をどこにとるかでカメラ位置の表現方法は変わることになる。そこで、本明細書では、基準とする座標系を区別するために、従来の静止座標系に対する演算をＣＶ演算とし、移動する座標系に対する演算をＲＶ演算として、それぞれＣＶ映像、ＲＶ映像と呼ぶことにする。
【００６４】
ここで、ＣＶ値とＲＶ値との違いは、最初に特徴点として、外側をとるか、内側をとるかだけの違いであり、その演算手法はどちらも全く同じである。
そして一般的には、同じ映像の中に、外側も内側も同時に映っているので、ＣＶ値とＲＶ値が同時に存在することになる。
そこで、このような一般映像として考えた場合、ＲＶ値について、ＣＶ値を求める演算と切り離して処理・演算を行うのがＲＶ演算装置４６である。そこでの違いは特徴点が移動体の中か外かである。従って、小領域が移動体の一部ではなく、静止座標系の対象物の一部、又は背景の一部の場合は、ＲＶ値とＣＶ値は一致することになる。
特に、本実施形態におけるＲＶ演算装置４６では、特徴点が移動体の一部となっている場合である。
【００６５】
静止座標系に対して移動するカメラ位置と姿勢はＣＶ演算によって求められるＣＶ値（X,Y,Z,θx,θy,θz）で規定され、移動座標系に対するカメラ位置と姿勢はＲＶ演算よって求められるＲＶ値（Xr,Yr,Zr,φx,φy,φz）で規定される。ここでカメラが共通（同一）であることから、静止座標系に対する移動座標系の位置と姿勢との関係は単純な演算で求められる。
さらに、静止座標系に対して移動する移動座標系が複数であっても同じであり、その時は任意の移動座標系から、共通のカメラの位置と姿勢を介して、他の任意の移動座標系の位置と姿勢が単純な演算で求められる。
【００６６】
ここで、本実施形態に係るＲＶ演算装置４６とそこで得られるＲＶ値は、その意味するところが重要であるため、以下この点について説明する。
ＲＶ演算装置４６では、ＲＶ演算のために使用する映像は必ずしもＣＶ映像でなくてもよく、映像のＣＶ値によりトラッキングを予想することが、絶対条件ではなくなる。これは、移動体を含む映像のＣＶ値と移動体のＲＶ値とは原理的に異なるためである。言い換えれば、移動する対象の中の移動する小領域のＲＶ値は、背景の静止座標系の中の映像のＣＶ値とは異なる。もし、ＲＶ値がＣＶ値に一致すればそれは移動体ではなく静止物体である。
【００６７】
そこで、小領域をより一般化して扱うことが有効である。即ち、小領域を一旦すべて移動する（移動座標系の）小領域と見なして（結果的に静止座標系の小領域であっても矛盾しない）、個別に特徴点を発生し、その特徴点をトラッキングして、小領域のＲＶ値をＲＶ演算装置４６で求めるものとする。
これは見方を変えれば、小領域単位でＲＶを求めることであり、小領域は同一のＲＶ値に属する特徴点の集合であることになる。これは、特徴点を介して小領域そのものをトラッキングしていることに等しいことになる。
【００６８】
ここで、本実施形態において小領域とフレーム内小領域とは異なるものであるが、両者を区別して記載することで説明に混乱が生じることもあり、また、両者は常に対応しているものであるので、以下の説明では両者を区別しないものとする。
そこで次に、本実施形態に係るＲＶ演算装置４６を小領域トラッキング装置として捉えると、映像中の複数の小領域（例えば１０個程度）のＲＶ値を同時に求めることは、従来のように複数の特徴点からなる独立した小面積の狭い範囲の小領域のＲＶ値としての意味を大きく越えて、対象物の一部としての小領域を、隣接フレームに亘ってトラッキングする対象としての特徴ある小領域として扱うことができることになる。そこで、トラッキングの対象となるこの特徴ある小領域を「特徴小領域」と定義する。
【００６９】
ここで、上記「特徴小領域」について、本実施形態における「複数の特徴点によってＣＶ演算をしてＣＶ値を求める」という説明に対応させて、それと同じ意味で「複数の「特徴小領域」によってＲＶ演算をして対象物のＲＶ値を求める」と考えることができる。
そして、さらに複数の「特徴小領域」のＲＶ値を同時に求めることで、静止座標系に対してのＣＶ値と、移動座標系おける「複数の小領域」のＲＶ値とが、それぞれ同時に求められる。即ち、同一のＲＶ値に属する複数の特徴小領域の集合となる。
この場合の演算上の長所としては、これら複数の特徴点小領域の各ＲＶ値は、その三次元座標の接続境界線を表す三変数は共通にしたまま連続していて、当該複数の特徴小領域の属する対象が剛体の場合には回転を表す三変数も同一であるとの仮定が成り立つので、誤差を最小化できることになる点である。ここで、回転を表す三変数のみ異なる場合は、当該対象物は剛体ではなく、複数の特徴小領域が柔軟な結合をしていることになる。
なお、上記以外の場合で、ＲＶ値座標と回転のそれぞれが異なる場合は、結果として、異なる座標系に属する特徴小領域であり、その異なる数だけのＲＶ値が求められることになる。
【００７０】
特徴小領域はもともと、移動体（移動座標系）に対して成される処理として想定されるものであり、移動、回転、拡大、縮小、形状変化等に強いものである。但し、移動速度を「０」とした静止座標系に対しても特に有効であることを以下に説明する。
即ち、特徴小領域を用いることにより、ＲＶ演算装置は、カメラの向きの変更、カメラ移動による対象（小領域）の回転、拡大、縮小等の形状変化、及び表示図法による変形等に対して、対応点を見失うことなく追従し、きわめて強いトラッキング特性を示すという優れた特徴を有するトラッキング装置とすることができる。
もし、静止座標系に限定すれば、ＲＶ演算装置はＣＶ映像を元画像としてトラッキング予想をして、ＲＶ演算をすることに意味があり、しかもＣＶ映像を元として処理をすることで、特徴点、及び特徴小領域の概略位置が推定できるので、演算効率がさらによくなる。
【００７１】
またさらに、原理的には、演算時間の増加を無視すれば、図６の最初の処理のＣＶ映像生成装置のＣＶ演算装置の代わりに、ＲＶ演算装置を用いて、ＣＶ映像の代わりとして、直接ＲＶ演算を行うことはもちろん可能であり、演算の精度も向上できる。
このように、本実施形態に係るＲＶ演算装置４６は、領域分割画像装置３により得られた小領域に対応するフレーム内小領域を、その中に生成した複数の特徴点を介して、小領域そのものを隣接する複数のフレームに亘ってトラッキングする小領域トラッキング装置として機能させることができる。
【００７２】
具体的には、ＲＶ演算装置４６は、フレーム内小領域特徴点三次元化装置４によって得られたフレーム内小領域の中に生成した複数の特徴点（移動体の一部）に対して、上述した静止座標系に対して定義されていたＣＶ演算ではなく、移動座標系に対して新たに定義したＲＶ演算を行う。ただし、数学的・物理的にはこの二つの演算は同等で、区別することはできない。すなわち、ＲＶ演算装置４６では、上述したＣＶ値を使わず、新たにＣＶ演算と同様の処理を行うＲＶ演算を行うものである。
ＲＶ演算とは、映像に映っている移動体対象物に固定された移動座標系に対して、さらに移動しているカメラ位置とカメラ姿勢を、移動座標系に対する三次元位置、三軸回転姿勢を示す六変数（Xr,Yr,Zr,φx,φy,φz）を定義することができる。すなわち、ＲＶ値を自動演算で求めることができる。
【００７３】
従って、上述したＣＶ値と同じように、ＲＶ値を用いて上述した領域分割画像の指定からポリゴン生成までの処理を行うことができる。
なお、本実施形態では、ＲＶ映像生成装置４７内のＲＶ演算装置４６は、移動体の一部としての小領域に関して演算を行うようになっており、これは図６のＣＶ映像生成装置２内のＣＶ演算装置２１と基本的に同じものであり、特徴点三次元化装置４２は、ＲＶ専用とはしていない。
これは、特徴点が静止座標系にあるか、移動座標系にあるかだけの違いであり、共用も可能だからである。
【００７４】
求められた小領域で、ＲＶ値を同じくする小領域は同一の移動体座標に属するとの仮定で、ＲＶ値を同じくする小領域を一体化させることで、移動する対象物のポリゴンを生成することができる。
ここで、以上のようなＲＶ値を動画像の各フレームと対応させたＲＶ映像を生成する装置としてＲＶ映像生成装置４７を定義することができるが、これはＣＶ映像生成装置２と同等であるので、本実施形態では区別しないものとする。また、ＲＶ演算装置４６は、機能・処理の面ではＣＶ演算装置２１と全く同じものである。
【００７５】
さらに、ＲＶ映像を求める場合には、同時に移動体の移動座標系における特徴点も同時に三次元化される。
そこで、本実施形態では、ＲＶ演算と同時に移動体の特徴点三次元座標を求める特徴点三次元化装置４２を備えることができる。
このように、三次元地図として、静止座標のみならず、リアルタイムで移動体を扱うためには、このような移動体に対応する三次元地図が必要である。
ここまでが、移動体対応の三次元地図自動生成装置１００ａに関する説明である。
【００７６】
以上のような構成からなる本実施形態に係る三次元地図自動生成装置１００について、更に具体的に説明する。
本発明に係る三次元地図の自動生成技術の特徴は、ＣＶ映像を用いて、既知の技術である領域分割技術と組み合わせた分割領域三次元化によって取得された小領域に対して、複数の特徴点を発生させ、ＣＶ映像のもつＣＶ値によって三次元化することにある。
動画映像に対して、特徴点を求め、トラッキングし、ＣＶ演算を行ってＣＶ映像を生成する流れは、上記概略を示した通りであり（図２、図３参照）、また後に詳述する通りである（図７〜図１９参照）。
【００７７】
ここでは、ＣＶ映像を使って、領域分割画像を生成し、その領域分割画像から、小領域を選択して三次元化する処理が本発明の核となるので、以下に詳細に述べる。
図４に示すように、ＣＶ映像１０１の中で、自動的に指定されたフレーム１０２を選択し、このフレーム画像から領域分割画像１（１０３）を生成する。なお、画像から領域分割化像を生成すること自体は、上記の通り公知の技術により実現される。
【００７８】
ここでの特徴は、ＣＶ値が既知の「ＣＶ映像」の中の一フレーム画像１０２を領域分割する点である。
領域分割は、図４の領域分割画像１（１０３）だけでなく、適切に距離をとったフレーム１０４を指定して選択し、領域分割画像２（１０５）でも生成する。同様に、領域分割画像３、４，５、・・・・・と継続的に領域分割画像を生成し、同様の処理が行われる。
領域分割画像は最大ＣＶ映像のフレーム数まで取ることができる。領域分割画像のサンプリング数を増加させると、それだけ処理量が増加するので、作業効率が落ちることになるので、適切な領域分割のサンプリング数を選択することが望ましい。
【００７９】
また、カメラ台数が増加する欠点はあるが、通常のＣＶ映像取得のための全周カメラ以外に、領域分割画像専用のカメラをも同時に設置して、そのカメラ画角は全周ではなく、限定された画角であっても、高解像度の専用カメラを設置することで高解像度の限定画角のＣＶ映像を別に生成し、そこから領域分割画像を取得することもできる。このようにすると、小領域の精度が向上し、結果としてＲＶ値の精度が向上するので好ましい。
なお、このとき、全周カメラによるＣＶ映像も限定画角カメラによる高解像度ＣＶ映像も、どちらも同時に生成するＣＶ映像なので、それぞれは単に隣のフレームと考えることができるので、それらのＣＶ値は一連のＣＶ値であり、一方の小領域は常に他方の小領域に対応がついているというところが重要である。
【００８０】
各領域画像で行われる処理について、さらに図５を参照しつつ詳細に説明する。
図５におけるＣＶ映像内の一フレーム１１０は、図４における「指定入れたフレーム１０２」、「次に指定されたフレーム１０４」に相当するものとする。
ＣＶ映像の中の指定された一フレーム１１０を複製して取り出して、そこから領域分割画像１１１を生成する。この処理により、前記一フレーム１１０は複数の領域に領域化され、複数の領域に分割され、領域分割画像１１１となる。
なお、この最初の処理段階で画像の領域化は不完全であってもよいものとする。最終的には、領域の形状を整形したり、他の指定フレームから生成される領域分割画像と共通する対象物を比較することで、領域の形状を修正し、補正することで、より適切な領域化がなされる。
【００８１】
次に、領域分割画像１１１を構成する複数の領域の中の単位となる一領域を小領域２０１として定義する。このとき同時に、領域分割画像内１１１に対応する元画像となるＣＶ映像の中の一フレーム１１２に、小領域２０１に対応するフレーム内小領域２０２を定義することができる。
このフレーム内小領域２０２内に、複数の特徴点２０３を発生させる。この時点での特徴点群は、いずれもフレーム内にあるから、未だ二次元座標しか持たないことは明確である。
そこで次に、この特徴点群をそれぞれＣＶ映像の連続するフレームとして隣接する複数のフレームに亘ってトラッキングして、そのトラッキングデータ２０４から、ＣＶ演算によりそれぞれの特徴点の三次元座標を求める。ここで、特徴点群のトラッキングデータからＣＶ演算して、三次元特徴点を求める手法としては、再度後述するＣＶ演算についての説明で詳述する（図７〜図１９参照）
【００８２】
次に、取得された三次元特徴点はそのままで、元々フレーム１１４と対応がついている領域分割画像１１５に複製して移転することが可能である。フレーム内小領域で三次元化された特徴点は領域分割画像の小領域２０６に複製して移転され、三次元特徴点２０７となる。
三次元特徴点群から、最も誤差が少なく、三次元特徴点をその平面近くに分布させる平面を求めることができる。その平面の法線を図５に示す線分２０５とする。
なお、三次元特徴点群は必ず誤差を含むから、完全に平面に乗ることはない。最も誤差が少なく平面を推定するには、最小自乗法やRANSAC手法がある。
【００８３】
このようにして、両領域の三次元平面が推定されたことになる。
分割画像内の他の小領域を同様に次々処理していくことで、すべての小領域の三次元平面が推定される。小領域をそのままポリゴンとしても良いが、後の処理で小領域の分割や統合により、より適切なポリゴンを生成することが望ましい。
ＣＶ映像の一フレームから領域分割画像を生成して、小領域を指定し、それをＣＶ映像に戻して、特徴点発生により三次元化して、それを小領域に戻すという流れの中で、その三次元座標の精度はＣＶ映像のＣＶ値の精度に依存していることになる。
【００８４】
そして、このＣＶ映像のＣＶ値は、映像から直接求めることができることから、撮影の規模が、例えば大都市程まで大きくなっても十分に対応することができる。
従って、前もってＣＶ映像のＣＶ値を精度良く求めておけば、例えば大規模な都市モデルのような処理においても、どこから生成しても、分割して生成しても、座標として矛盾のない３ＤＣＧを生成することができる。
また、ＧＰＳデータ等の機械センサーによって取得された位置や姿勢のデータは、単独で取得した位置座標を後に精度良く統合することは不可能であるが、本実施形態に係るＣＶ映像は「映像」からデータを生成するので、データの統合がいつでも可能となる。この点も本発明の重要なポイントとなる。
【００８５】
以下、図１、図４、図５を参照して、上述した本実施形態に係る三次元地図自動生成装置１００について、より具体的な実施例を示しつつ説明する。
まず、動画像取得装置１として、車載した全周カメラ、例えばPGR社製のLadybug３を積載する（図８、図９参照）。後に有効なＣＶ演算をするためには、動画取得装置１を構成するカメラにより１５Hz程度で撮影することが望ましい。
車両の位置を示すＧＰＳは基本的に必要ないが、この後の処理のために、概略位置を記しておく必要があるため、安価なＧＰＳを使用して、撮影地点の概略位置を取得しておくことは適切である。
撮影した動画像はハードディスク等の所定の記憶媒体に記録しておくことになる。
【００８６】
全周カメラは、原理的には一台でよいが、精度向上を求める場合には複数台とすることも可能であり、ここでは資料の屋根に上下に設置した二台の全周カメラで全方向を撮影し（Dual方式撮影装置）、二台のカメラの同期を取るようにする。
なお、ここでは二台のカメラは同期をとっているが、ＣＶ演算においては原理的に同期が必要条件ではない。ＣＶ演算においては、同期が取れていても、取れていなくてもよい。ここでは、たまたまカメラ移動による時間軸方向にカメラが配列してある状況があれば良いのであり、その中にカメラ移動無しに異なる配列があっても、それは区別する必要はない。そして、同期方式の場合は、それがたまたま同時刻の映像が異なる場所にカメラが存在していると考えればよい。このようなフレキシビリティーがＣＶ演算に基づく本発明の最大の特徴といえる。
【００８７】
なお、二台のカメラで同期を取ることで、ステレオ方式と間違いを受けやすいが、これはいわゆるステレオではない。カメラの台数のことではなく、時間軸上の配列される等価的なカメラ列が重要なのであって、一台のカメラが作る時間軸上のカメラ列であろうと、二台のカメラが作る時間軸上のカメラ列であろうと、ＣＶ演算にとっては本質的に同じである。
更に言えば、それが物理的に一台であろうと複数台（例えば五台）であろうと、物理的なカメラ個数には関係なく、時間軸上に配列される等価的な各カメラが、どのように周囲の世界を移し込んでいるかのみが情報であり、その情報から、各カメラ位置と姿勢をＣＶ値として演算して解を求めることになる。
【００８８】
そして、カメラ二台による方式（Dual方式）では、ある瞬間を見れば、ステレオ方式では二台のカメラによる一対の組み合わせが演算に係わるのに比較し、この方式によれば、二台のカメラの近傍の複数のカメラの配列の組み合わせ、すなわちここでの例では、移動する二台のカメラの映像の複数フレーム分として、実質約二十数台分のカメラの配列による数百対（２０×２０）の組み合わせ映像が、その地点の一点のＣＶ値の演算に係わることになるので、精度が極めて高いことになる。
参考例として、カメラ一台で実施した場合では、時間軸上にある前後約５０台のカメラ映像がＣＶ演算に係わることになる。
【００８９】
係わるカメラ台数とその映像が多ければ多いほど、ＣＶ演算の精度が向上し、そのＣＶ値を用いた計測の精度が向上することになる。
特に本発明の三次元地図自動生成装置では、あらゆる方向に対する計測精度の向上が望まれるので、この実施例ではカメラ二台によるDual方式を採用している。つまり、二台のカメラを垂直方向に設置したことで、有効な複数のエビポーラ線が生まれることになるので、全方向に対する計測精度が向上したことがこのDual方式の長所となる。
【００９０】
ちなみに、カメラ一台の場合には、有効なエビポーラ線が一本であり、進行方向に対する計測精度は十分であったが、前方や水平線に対する計測精度に難があった。
カメラ一台でも二台でも、特にＣＶ演算の手法においては原理的に変わるものではないので、演算された結果についても、カメラ一台でのＣＶ値と同様に扱うことができる。
従って、以下に示す実施例では、カメラ台数に関わらず、カメラ一台の場合と同様に、単にＣＶ値として扱うことができる。
【００９１】
ＣＶ映像生成装置２によって、動画像取得装置１で撮影された全周映像から、ＣＶ映像が生成される。
毎秒１５Ｈｚで記録された全周映像は、ハードディスク等に記録されていったん保存される。
ハードディスクから読み出される全周映像から、ＣＶ映像が生成される。ＣＶ映像の生成の詳細は後述する通りである（図７〜図１９参照）。
また、その数学的意味は上述した通りである（図２、図３参照）。
ＣＶ映像は、本発明に係る三次元地図自動生成装置１００の根幹技術であり、このＣＶ映像を取得することで、後の処理がすべて実行されることになる。換言すれば、ＣＶ映像がなければ本発明に係る三次元地図自動生成装置は実現できないことを意味する。
【００９２】
また、ＣＶ映像を取得するためには、全周映像が絶対条件ではないが、全周ではない通常の画像よりも全周映像の方が、処理が簡単で、精度が高いという長所がある。
全周映像では、全方向に特徴点を取得できるので、誤算が分散され、打ち消し合い、演算に都合がよい。
通常カメラによる映像でのＣＶ演算では、焦点距離と光軸というデリケートな要素を扱うことになるが、全周映像では焦点距離と光軸が存在しないので、演算時の未知数の数を少なくすることができることも演算精度に貢献している。
【００９３】
次に、領域分割装置３では、１５ＨｚのＣＶ映像からサンプリングするようにして、一部のフレームをある間隔で指定し、そのフレームを自動的に取り出す。
取り出されたフレームは領域分割装置３の中の領域生成装置３１で領域分割処理される。ここでの領域分割処理は既知の技術による。
ここで、分割時のパラメータを調整して、このフレームを適切な複数の小領域に分割し、小領域指定装置３２で、一つの小領域を指定する。この小領域を最小単位として、後にポリゴンを生成していく。
【００９４】
取り出されたフレームと領域分割画像は完全に対応しており、その後の処理で特徴点が発生されるが、その位置関係は両者で完全に一致する。
領域分割された領域分割画像の最小単位が小領域であり、この小領域はフレーム内のフレーム内小領域に座標は完全に一致している。
なお、この時点では画像が二次元なので、二次元として完全に一致している。ただし、両者は三次元空間に存在する小領域であり、本来三次元としても完全に一致していることは自明である。
【００９５】
次に、フレーム内小領域特徴点三次元化装置４では、小領域とフレーム内小領域を対応させながら処理を進める。
図１に装置構成を示し、その処理内容を図４に示しつつ、フレーム内小領域特徴点三次元化装置４の詳細について以下に説明する。
まず、フレーム内小領域特徴点発生装置４１では、フレーム内小領域に複数の特徴点を発生させる。原理的にはフレーム内小領域内に三個の特徴点があり、それを三次元化できれば、平面を決定できるが、精度を考慮して、例えば２０個程度の特徴点があることが望ましい。
【００９６】
ここで、限られた範囲に２０個以上の多くの特徴点を発生させ、それをトラッキングするには、領域境界付近に集中する特徴点を効率よく抽出する必要がある。
そのために、フレーム内小領域特徴点三次元化装置４では、小領域境界特徴点発生装置４３を備えており、小領域の境界付近に集中的に特徴点を発生させるようにしてある。
特に、本実施例では、ＣＶ映像時に多数の特徴点からＣＶ値を演算するようになっているので、その多数の特徴点を有効利用することができる。
【００９７】
なお、ＣＶ演算後には、ＣＶ演算に用いられた特徴点、トラッキングデータ、及びそれから求められた三次元特徴点は破棄することができるが、ここではそれらを直ちに破棄することなく有効利用している。
すなわち、フレーム内小領域特徴点三次元化装置４は、ポイントクラウド生成装置４５を備えており、このポイントクラウド生成装置４５は、ＣＶ演算時において、より積極的に三次元特徴点を生成し、ポイントクラウドを生成し、後の処理に積極的に役立てようとするものである。
【００９８】
さらに、カメラ二台によるDual方式においては、ＣＶ演算時には一部のフレーム内小領域の水平ラインについては既に特徴点を抽出しており、しかもトラッキング処理により三次元座標も求められているので、それをそのまま小領域内の三次元点として用いることができる。
なお、これだけで十分とは言えないので、以下の方法により、さらにフレーム内特徴点を追加して、面推定に必要な数の三次元特徴点を取得することが好ましい。
【００９９】
図４では、ＣＶ映像のフレームの進行方向を示している。
その時間の流れの中の１フレーム１０２を指定して取り出し、領域分割画像１（１０３）とする。
同様に、次に指定されたフレーム１０４から領域分割画像２（１０５）を選択する。
そして、各領域分割画像中において複数の小領域を生成し、その中の一つを小領域として、複数の小領域を生成する。そして、その中の一つの小領域を取り出し、対応するフレーム内小領域内で複数の特徴点を発生させる。
複数の特徴点について、フレーム２（１０４）のＣＶ値を用いて、トラッキング予測を行い、トラッキングにより三次元座標を取得する。この三次元座標は小領域に移転することが可能である。
トラッキングデータから三次元座標を求める演算は、ＣＶ映像を生成するＣＶ演算と基本的に同じである（図７〜図１９参照）。
【０１００】
次に、複数領域ポリゴン化装置５においては、先ず対象物と背景の関係を大まかに示しているポイントクラウドの情報が有益である。
ポイントクラウドとは、三次元の特徴点を分布させたものである。
ポイントクラウド生成装置４５は、ＣＶ演算時の三次元特徴点の分布であるが、フレーム内小領域トラッキング時に生成した三次元特徴点を追加させても良い。
複数領域ポリゴン化装置５の全体構成推定装置５４は、ポイントクラウドから自動判断して、全体構成を推定する。
【０１０１】
一般に対象物や背景は、解略の大きさや方向は予想がついていることが多いので、ある程度予想して概略のモデル化が可能であることから、例えば、道路面、交差点、ビル面、街路樹面等の大枠は、ポイントクラウドから分離可能である。
道路走行という前提に立って、道路周辺を予想し、全体構成を予想することは、後の処理に大いに貢献する。
【０１０２】
ここでは、三次元特徴点によって形成されるポイントクラウドの分布状況から、道路面の概略位置を指定し、ビル面の概略位置を指定し、ビル面と街路樹面とを歩道上で前後に分離し、ビル面と街路樹の存在範囲を指定し、交差点概略位置を指定し、それらの大枠とその範囲を自動推定している。
この処理により、後の各種ポリゴン生成は上記の指定された範囲で求めることになり、効率的になる。
【０１０３】
まず、複数領域ポリゴン化装置５の各領域面推定装置５１により、フレーム内小領域で求められた複数の特徴点の三次元座標から、平面推定が行われる。
ＣＶ演算時の三次元特徴点（図１の符号４４で示す矢印）のみで、小領域内に十分な数の三次元特徴点が取得できれば、それを用いて面の推定ができるが、多くの場合これだけでは十分ではなく、フレーム内小領域特徴点発生装置による特徴点の追加が必要である。なお、ここでは、小領域は必ずしも平面ではないが、微少領域は平面であると仮定しても、大きな矛盾はないとの考え方で、平面推定をしている。
平面推定には上述したRANSAC手法等を用いて、誤差を含む複数三次元特徴点から、都合の良い特徴点のみを自動選択して平面を推定することで得られる。
【０１０４】
さらに、複数領域ポリゴン化装置５では、得られた小領域の面の推定が精度良く求められているか、誤差が大きいか否か等の判定として、トラッキング差分補正装置５３を用意してある。
推定された面の推定が済めば、その推定面にＣＶ映像から、対応位置のテクスチャー取り込むことができることは明らかである。
そこで、そのフレーム内小領域の三次元座標からＣＶ映像内での面の移動は計算で求められるから、ＣＶ映像のフレームを進めながら、各フレームでの小領域のテクスチャーの一致度を例えば相関関数で評価すればよい。
面推定が正しければ、相関関数はほぼ１００％近くで一致することになる。もし、評価が低ければ、面推定が間違っていることになるので、再分割したり、三次元特徴点を増加させるなどして、再推定することになる。
【０１０５】
そこで、次に、面の統合分離装置５５では、フレーム内小領域に関して、上記の相関関数での評価ではなく、マッチング手法でその一致度合いで評価すれば、その評価値から面推定が正しいところと間違っているところを分離することができる。
面推定が間違っている部分を新たな小領域として分離して、他の小領域と同様な処理を繰り返すことで、同様に面推定を行うことができる。
【０１０６】
また、同一平面にある二つの小領域は二つの小領域のまま保存し、ポリゴン化されることで矛盾はないが、統合することがデータ量を軽くして保持することができ、それは合理的であるので好ましい。
なお、本実施例では、データ量の増加を抑えるために、一つのポリゴンに一色を対応させており、そのポリゴンを構成する小領域の平均の色を取得することで実現している。
小領域の分離と統合が終わり、小領域が決定されれば、それがそのまま最終ポリゴンとなり、ポリゴン生成処理が終了する。
連続処理装置６が、ここまでの処理の流れを連続的に繰り返し処理するようにして、フレームを進めながら処理を行うことで、広い領域の三次元地図を自動生成することができる。
【０１０７】
最後に、テクスチャー取得装置７では、ポリゴン化された三次元地図に、対応するテクスチャーを貼り付ける。
小領域はフレーム内小領域に対応しているので、いつでもＣＶ映像のテクスチャーを貼り付けることが可能であることは言うまでもない。
また、ＣＶ値を持つことから、視点を変えたフレームからのテクスチャーを貼り付けることも可能である。
さらに、更新のために、新たに撮影した映像をＣＶ映像化して、新旧のＣＶ映像のＣＶ値を合わせることで、新たなＣＶ映像の対応するポリゴンのテクスチャーを更新することも自由である。
【０１０８】
以上説明したように、本実施形態に係る三次元地図自動生成装置１００によれば、カメラで得られる動画又は連続静止画の映像に基づいて、対象物、及びその背景を含めて、その三次元形状を求め、必要であればそのテクスチャーを自動的に取得して、三次元地図を自動的に生成することができる。
特に、本発明では、高価な機器や膨大な手間と費用などを必要とすることなく、完全自動により、背景を含めた対象物との座標を矛盾無く整合して、簡易かつ高精度に、三次元形状を求めて、大規模に三次元地図を生成することができる。
【０１０９】
また、本実施形態に係る三次元地図自動生成装置１００では、三次元地図が現実の座標及び緯度経度高度を示すＣＶ値を持つことにより、三次元地図に対して三次元データを持つＣＧ（コンピュータグラフィックス）を容易かつ高精度に、矛盾等が生じることなく結合・整合さえることが可能となる。
一般に個々にＣＧを生成して、それを結合しても、ＣＧは三次元座標と三次元姿勢を持ち、それを矛盾無く整合しようとしても、現実問題としてなかなか整合はとれない。整合をとるためにも手動で、調整する必要があった。それ故これまでは、例えば大規模な都市構造をＣＧ化することは困難であった。
【０１１０】
しかしながら、上述したような本実施形態に係る三次元地図自動生成装置１００によれば、ＣＶ値は、現実の座標、緯度経度高度を持たせることができるので、途中の三次元座標は、緯度経度高度で処理することが可能となる。当然、最終的なポリゴンにおいても緯度経度高度を持つことになる。
従って、都市等をそのまま三次元化する場合に、個々に地域別に三次元化しても、その整合性は表示に高いものとなり、当然精度が高いＣＧが得られることになる。
【０１１１】
なお、座標の精度は、一番最初の処理において、ＣＶ映像生成時にＣＶ演算した結果に、絶対座標を正しく取得しておくことが重要であるが、処理の途中でのＣＶ値の補正も自由である。
さらに、後で得られた最も精度の高い実測データをＣＶ値に反映させることも可能であり、画像の一部にでも精度の高い実測データを持つ地点が有れば、それをＣＶ値の精度に反映できること等は、ＣＶ演算の優れた長所である。
【０１１２】
また、従来の三次元地図技術では、地図等の更新のために膨大な費用が必要であったが、ＣＶ映像を用いたＣＶ技術を利用すれば、例えば大都市の一部からＣＶ映像化し、一部からポリゴン化することで、最終的に統合することが可能となる。つまり、ＣＶ値さえ全体で統合されていれば、どこから作成しても全く矛盾は生じないことになる。
さらに、一部の更新においても同様であり、更新が必要な地域のＣＶ映像を既知のＣＶ値に統合しておくことで、後は自動的に変更分だけが更新される装置とすることも可能となる。
【０１１３】
このように、本実施形態に係る三次元地図自動生成装置１００によれば、三次元形状、及び背景との座標関係に矛盾が無いように、高精度の三次元地図を生成でき、また、人間が見るための地図としても十分な品質のものが得られる。
従って、本発明は、自動車、重機、航空機等の移動体の三次元位置を評定したり、移動体の進行方向や現在状況等をガイドするための三次元地図と、その三次元地図自動生成装置として好適に利用することができる。
【０１１４】
［ＣＶ演算］
次に、以上のような本発明の三次元地図自動生成装置における三次元地図の生成処理の前提となるＣＶ演算について図７〜図１９を参照しつつ説明する。
ＣＶ演算とはＣＶ値を求める方法の一つであり、ＣＶ演算により求められた結果をＣＶ値，ＣＶデータと呼ぶ。ＣＶという表記は、カメラベクトル：CameraVectorの略記であり、カメラベクトル（ＣＶ）とは計測等のために映像を取得するビデオカメラ等のカメラの三次元位置と３軸回転姿勢を示す値である。
ＣＶ演算は、動画像（ビデオ映像）を取得し、その映像内の特徴点を検出し、それを隣接する複数のフレームに追跡し、カメラ位置と特徴点の追跡軌跡とが作る三角形を画像内に数多く生成し、その三角形を解析することで、カメラの三次元位置とカメラの３軸回転姿勢を求めるものである。
【０１１５】
ＣＶ演算では、ＣＶ値を求める過程で、同時に映像内の特徴点（基準点）についても三次元座標が同時に求まることが重要な特性である。
また、動画像から演算で求められるＣＶ値は、動画像の各フレームに対応して、三次元のカメラ位置と三次元のカメラ姿勢とが同時に求まる。しかも、原理的には一台のカメラで、映像と対応してＣＶ値が求められる特性は、ＣＶ演算でしか実現し得ない、優れた特徴である。
但し、ＣＶ値は、例えば、他の方法による計測手段（ＧＰＳとジャイロ、又はＩＭＵ等）より求めることもできる。従って、ＣＶ値の取得はＣＶ演算による場合には限られない。
なお、ＧＰＳとジャイロ、又はＩＭＵ等によりＣＶ値を取得する場合には、動画像の各フレームと、その三次元的カメラ位置と三次元的カメラ姿勢とを同時に取得するためには画像フレームと計測サンプリング時刻を高精度で、かつ完全に同期させる必要がある。
【０１１６】
動画像から演算で求められるＣＶデータは、加工しない段階では相対値であるが、短区間であれば高精度で三次元位置情報と３軸回転の角度情報を取得できる。
また、ＣＶデータを画像から取得する場合は、取得されたデータは相対値であり、絶対値に変換するには既知の地点でのキャリブレーションが必要であるが、ＣＶ値と同時に取得される特徴点三次元位置座標と姿勢により、又は新たに画像内に指定して取得した特徴点により、画像内の任意の対象物との位置関係を計測することができるという、他の方法では実現困難な優れた特性を備える。
また、画像に対応したＣＶ値が求まるので、画像との相性が良く、画像から取得したＣＶ値である限り、その画像内では矛盾が無いので、画像以外から求めるＣＶ値と比較して、画像から直接にカメラ位置とその３軸回転姿勢を求めることができるＣＶ演算は画像内計測や画像内測量に好適となる。
そして、本実施形態では、このＣＶ演算により得られたＣＶ値データに基づいて、映像のみに基づいて三次元地図を自動生成するものである。
【０１１７】
［ＣＶ演算部］
ＣＶ演算は、上述した三次元地図自動生成装置１００のＣＶ映像生成装置２（ＣＶ演算装置２１）として機能するもので（図１、図６参照）、図７に示すＣＶ演算部２で行われる。
ＣＶ演算部２は、図７に示すように、上述した図１、図６に示した三次元地図自動生成装置１００の動画像取得装置１を構成する全周ビデオ映像部１から入力されるビデオ映像について、所定のＣＶ演算処理を行うことでＣＶ値を求めるようになっている。
【０１１８】
具体的には、ＣＶ演算部２は、図７に示すように、特徴点抽出部２-１と、特徴点対応処理部２-２と、カメラベクトル演算部２-３と、誤差最小化部２-４と、三次元情報追跡部２-５と、高精度カメラベクトル演算部２-６とを備えている。
そして、このＣＶ演算部２の出力が、三次元地図自動生成装置１００にフィードバックされて上述した三次元地図の自動生成処理が行われることになる（図１、図６参照）。
【０１１９】
まず、ＣＶ演算に使用する映像としては、原理的にはどのような映像でもよいが、画角の限られた映像では視点方向を移動した場合に映像がとぎれてしまうので、実用的には全周映像（図８〜図１０参照）か、広角映像を全周映像の一部として扱うことが望ましい。なお、動画映像は連続する静止画と同様であり、複数の静止画として扱うことができる。
また、映像は、一般には予め記録した動画映像を使うことになるが、自動車等の移動体の移動に合わせてリアルタイムに取り込んだ映像を使用することも勿論可能である。
【０１２０】
そこで、本実施形態では、ＣＶ演算に使用する映像として、車輌等の移動体の３６０度の全周囲を撮影した全周映像（図８〜図１０参照）か、又は全周映像に近い広角映像を用いて、その全周映像を視点方向に平面展開することにより、全周映像の一部として扱うことができる。
全周映像の平面展開とは、全周映像を、通常の画像として遠近法的に表現するものである。ここで、「遠近法」と呼称するのは、全周画像のそのものはメルカトール図法や球面投影図法のように、遠近法とは異なる方法で表示されているので（図１０参照）、これを例えば等距離図法のように平面展開表示することで、通常の遠近法映像に変換表示できるからである。
【０１２１】
全周ビデオ映像部１において全周映像を生成するには、まず、図８及び図９に示すように、全周ビデオカメラ１-１を使用して、ＣＶ値データを取得する目的で、走行車輌等の移動体１-１ａに固定された全周ビデオカメラ１-１で、移動体１-１ａの移動とともに移動体周辺を撮影する。
なお、移動体１-１ａには、その位置座標を取得する目的で、例えば、絶対座標を取得するＧＰＳ機器単独やＩＭＵ機器を付加したもの等により構成した位置計測機器等を備えることができる。
また、移動体１-１ａに搭載される全周ビデオカメラ１-１としては、広範囲映像を撮影，取得するカメラであればどのような構成であってもよく、例えば、広角レンズや魚眼レンズ付きカメラ、移動カメラ、固定カメラ、複数のカメラを固定したカメラ、３６０度周囲に回転可能なカメラ等がある。本実施形態では、図８及び図９に示すように、車輌に複数のカメラが一体的に固定され、移動体１-１ａの移動に伴って広範囲映像を撮影する全周ビデオカメラ１-１を使用している。
【０１２２】
そして、以上のような全周ビデオカメラ１-１によれば、図９に示すように、移動体１-１ａの天井部に設置されることで、カメラの３６０度全周囲の映像を複数のカメラで同時に撮影することができ、移動体１-１ａが移動することで、広範囲映像を動画データとして取得できる。
ここで、全周ビデオカメラ１-１は、カメラの全周映像を直接取得できるビデオカメラであるが、カメラの全周囲の半分以上を映像として取得できれば全周映像として使用できる。
また、画角が制限された通常のカメラの場合でも、ＣＶ演算の精度としては低下するが、全周映像の一部分として取り扱うことが可能である。
【０１２３】
なお、全周ビデオカメラ１-１で撮影された広範囲映像は、一枚の画像として、撮影時の画角に一致する仮想球面に貼り付けることができる。
仮想球面に貼り付けられた球面画像データは、仮想球面に貼り付けた状態の球面画像（３６０度画像）データとして保存・出力される。仮想球面は、広範囲映像を取得するカメラ部を中心点とした任意の球面状に設定することができる。
図１０（ａ）は球面画像が貼り付けられる仮想球面の外観イメージであり、同図（ｂ）は仮想球面に貼り付けられた球面画像の一例である。また、同図（ｃ）は、（ｂ）の球面画像をメルカトール図法に従って平面展開した画像例を示す。
【０１２４】
そして、以上のように生成・取得された全周ビデオ映像が、ＣＶ演算部２に入力されてＣＶ値データが求められる（図７参照）。
ＣＶ演算部２では、まず、特徴点抽出部２-１が、全周ビデオ映像部１の全周ビデオカメラ１-１で撮影されて一時記録された動画像データの中から、十分な数の特徴点（基準点）を自動抽出する。
特徴点対応処理部２-２は、自動抽出された特徴点を、各フレーム間で各フレーム画像内において自動的に追跡することで、その対応関係を自動的に求める。
カメラベクトル演算部２-３は、対応関係が求められた特徴点の三次元位置座標から各フレーム画像に対応したカメラベクトルを演算で自動的に求める。
誤差最小化部２-４は、複数のカメラ位置の重複演算により、各カメラベクトルの解の分布が最小になるように統計処理し、誤差の最小化処理を施したカメラ位置方向を自動的に決定する。
【０１２５】
三次元情報追跡部２-５は、カメラベクトル演算部２-３で得られたカメラベクトルを概略のカメラベクトルと位置づけ、その後のプロセスで順次画像の一部として得られる三次元情報に基づいて、複数のフレーム画像に含まれる部分的三次元情報を隣接するフレームの画像に沿って自動追跡を行う。ここで、三次元情報（三次元形状）とは、主に特徴点の三次元分布情報であり、すなわち、三次元の点の集まりであり、この三次元の点の集まりが三次元形状を構成する。
高精度カメラベクトル演算部２-６は、三次元情報追跡部２-５で得られた追跡データに基づいて、カメラベクトル演算部２-３で得られるカメラベクトルより、さらに高精度なカメラベクトルを生成，出力する。
そして、以上のようにして得られたカメラベクトルが、後述する三次元機械地図生成装置２００に入力され、ＣＶタグの生成や貼り付け処理に利用されることになる。
【０１２６】
複数の画像（動画又は連続静止画）の特徴点からカメラベクトルを検出するにはいくつかの方法があるが、図７に示す本実施形態のＣＶ演算部２では、画像内に十分に多くの数の特徴点を自動抽出し、それを自動追跡することで、三角測量幾何学、及びエピポーラ幾何学により、カメラの三次元ベクトル及び３軸回転ベクトルを求めるようにしてある。
特徴点を充分に多くとることにより、カメラベクトル情報が重複することで、三地点の座標で構成される単位の三角形を、その十倍以上の多くの特徴点から求めることになり、重複する情報から誤差を最小化させて、より精度の高いカメラベクトルを求めることができる。
【０１２７】
カメラベクトルとは、移動するカメラの持つ六個の自由度のベクトルである。
一般に、静止した三次元物体は、位置座標（Ｘ，Ｙ，Ｚ）と、それぞれの座標軸の回転角（Φｘ，Φｙ，Φｚ）の六個の自由度を持つ。従って、カメラベクトルは、カメラの位置座標（Ｘ，Ｙ，Ｚ）とそれぞれの座標軸の回転角（Φｘ，Φｙ，Φｚ）の六個の自由度のベクトルをいう。なお、カメラが移動する場合は、自由度に移動方向も入るが、これは上記の六個の自由度から微分して導き出すことができる。
このように、本実施形態のカメラベクトルの検出とは、カメラは各フレーム毎に六個の自由度の値をとり、各フレーム毎に異なる六個の自由度を決定することである。
【０１２８】
以下、ＣＶ演算部２における具体的なカメラベクトルの検出方法について、図１１以下を参照しつつ説明する。
まず、上述した全周カメラ映像部１０の全周ビデオカメラ１-１で取得された画像データは、間接に又は直接に、ＣＶ演算部２の特徴点抽出部２-１に入力され、特徴点抽出部２-１で、適切にサンプリングされたフレーム画像中に、特徴点となるべき点又は小領域画像が自動抽出され、特徴点対応処理部２-２で、複数のフレーム画像間で特徴点の対応関係が自動的に求められる。
具体的には、カメラベクトルの検出の基準となる、十分に必要な数以上の特徴点を求める。画像間の特徴点とその対応関係の一例を、図１１〜図１３に示す。図中「＋」が自動抽出された特徴点であり、複数のフレーム画像間で対応関係が自動追跡される（図１３に示す対応点１〜４参照）。
ここで、特徴点の抽出は、図１４に示すように、各画像中に充分に多くの特徴点を指定，抽出することが望ましく（図１４の○印参照）、例えば、１００点程度の特徴点を抽出する。
【０１２９】
続いて、カメラベクトル演算部２-３で、抽出された特徴点の三次元座標が演算により求められ、その三次元座標に基づいてカメラベクトルが演算により求められる。具体的には、カメラベクトル演算部２-３は、連続する各フレーム間に存在する、十分な数の特徴の位置と、移動するカメラ間の位置ベクトル、カメラの３軸回転ベクトル、各カメラ位置と特徴点をそれぞれ結んだベクトル等、各種三次元ベクトルの相対値を演算により連続的に算出する。
本実施形態では、例えば、３６０度全周画像のエピポーラ幾何からエピポーラ方程式を解くことによりカメラ運動（カメラ位置とカメラ回転）を計算するようになっている。また、これを三角測量として説明すれば、方位と俯角仰角を測量する機器を車載して、対象となる複数の測量地点を、移動する測量機器により同一対象物を計測して取得したデータから、各対象地点の座標と測量機器の移動の軌跡を求める場合と同じである。
【０１３０】
図１３に示す画像１，２は、３６０度全周画像をメルカトール展開した画像であり、緯度φ、軽度θとすると、画像１上の点は（θ１，φ１）、画像２上の点は（θ２，φ２）となる。そして、それぞれのカメラでの空間座標は、ｚ１＝（ｃｏｓφ１ｃｏｓθ１，ｃｏｓφ１ｓｉｎθ１，ｓｉｎφ１）、ｚ２＝（ｃｏｓφ２ｃｏｓθ２，ｃｏｓφ２ｓｉｎθ２，ｓｉｎφ２）である。カメラの移動ベクトルをｔ、カメラの回転行列をＲ、とすると、ｚ１T［ｔ］×Ｒｚ２＝０がエピポーラ方程式である。
十分な数の特徴点を与えることにより、線形代数演算により最小自乗法による解としてｔ及びＲを計算することができる。この演算を対応する複数フレームに適用し演算する。
【０１３１】
ここで、カメラベクトルの演算に利用する画像としては、３６０度全周画像を用いることが好ましい。
カメラベクトル演算に用いる画像としては、原理的にはどのような画像でも良いが、全周映像は対象物の方向がそのまま緯度経度で表現されていることから、きわめて有利である。図１３に示す３６０度全周画像のような広角レンズによる画像の方が特徴点を数多く選択し、複数フレームに渡って追跡し易くなる。また、狭角レンズによる映像あっても、同一対象物の周りを移動しながら様々な方向から撮影する場合には特徴点が視界から逃げないので有効である。
そこで、本実施形態では、ＣＶ演算に３６０度全周画像を用いており、これによって、特徴点の追跡距離を長くでき、特徴点を十分に多く選択することができ、遠距離、中距離、短距離それぞれに都合の良い特徴点を選択することができるようになる。また、回転ベクトルを補正する場合には、極回転変換処理を加えることで、演算処理も容易に行えるようになる。これらのことから、より精度の高い演算結果が得られるようになる。
なお、図１３は、ＣＶ演算部２における処理を理解し易くするために、１台又は複数台のカメラで撮影した画像を合成した３６０度全周囲の球面画像を地図図法でいうメルカトール図法で展開したものを示しているが、実際のＣＶ演算では、必ずしもメルカトール図法による展開画像である必要はない。
【０１３２】
次に、誤差最小化部２-４では、各フレームに対応する複数のカメラ位置と複数の特徴点の数により、複数通り生じる演算方程式により、各特徴点に基づくベクトルを複数通り演算して求めて、各特徴点の位置及びカメラ位置の分布が最小になるように統計処理をして、最終的なベクトルを求める。例えば、複数フレームのカメラ位置、カメラ回転及び複数の特徴点について、Levenberg-Marquardt法により最小自乗法の最適解を推定し、誤差を収束してカメラ位置、カメラ回転行列、特徴点の座標を求める。
さらに、誤差の分布が大きい特徴点については削除し、他の特徴点に基づいて再演算することで、各特徴点及びカメラ位置での演算の精度を上げるようにする。
このようにして、特徴点の位置とカメラベクトルを精度良く求めることができる。
【０１３３】
図１５〜図１７に、ＣＶ演算により得られる特徴点の三次元座標とカメラベクトルの例を示す。図１５〜図１７は、本実施形態のＣＶ演算によるベクトル検出方法を示す説明図であり、移動するカメラによって取得された複数のフレーム画像によって得られるカメラ及び対象物の相対的な位置関係を示す図である。
図１５では、図１３の画像１，２に示した特徴点１〜４の三次元座標と、画像１と画像２の間で移動するカメラベクトル（Ｘ，Ｙ，Ｚ）が示されている。
図１６及び図１７は、充分に多くの特徴点とフレーム画像により得られた特徴点の位置と移動するカメラの位置が示されている。同図中、グラフ中央に直線状に連続する○印がカメラ位置であり、その周囲に位置する○印が特徴点の位置と高さを示している。
【０１３４】
ここで、ＣＶ演算部２におけるＣＶ演算は、より高精度な特徴点とカメラ位置の三次元情報を高速に得るために、図１８に示すように、カメラから特徴点の距離に応じて複数の特徴点を設定し、複数の演算を繰り返し行うようにする。
具体的には、ＣＶ演算部２では、画像内には映像的に特徴がある特徴点を自動検出し、各フレーム画像内に特徴点の対応点を求める際に、カメラベクトル演算に用いるｎ番目とｎ＋ｍ番目の二つのフレーム画像FｎとＦｎ＋ｍに着目して単位演算とし、ｎとｍを適切に設定した単位演算を繰り返すことができる。
ｍはフレーム間隔であり、カメラから画像内の特徴点までの距離によって特徴点を複数段に分類し、カメラから特徴点までの距離が遠いほどｍが大きくなるように設定し、カメラから特徴点までの距離が近いほどｍが小さくなるように設定する。このようにするのは、カメラから特徴点までの距離が遠ければ遠いほど、画像間における位置の変化が少ないからである。
【０１３５】
そして、特徴点のｍ値による分類を、十分にオーバーラップさせながら、複数段階のｍを設定し、画像の進行とともにｎが連続的に進行するのにともなって、演算を連続的に進行させる。そして、ｎの進行とｍの各段階で、同一特徴点について複数回重複演算を行う。
このようにして、フレーム画像ＦｎとＦｎ＋ｍに着目した単位演算を行うことにより、ｍ枚毎にサンプリングした各フレーム間（フレーム間は駒落ちしている）では、長時間かけて精密カメラベクトルを演算し、フレーム画像ＦｎとＦｎ＋ｍの間のｍ枚のフレーム（最小単位フレーム）では、短時間処理で行える簡易演算とすることができる。
【０１３６】
ｍ枚毎の精密カメラベクトル演算に誤差がないとすれば、ｍ枚のフレームのカメラベクトルの両端は、高精度演算をしたＦｎとＦｎ＋ｍのカメラベクトルと重なることになる。従って、ＦｎとＦｎ＋ｍの中間のｍ枚の最小単位のフレームについては簡易演算で求め、簡易演算で求めたｍ枚の最小単位フレームのカメラベクトルの両端を、高精度演算で求めたＦｎとＦｎ＋ｍのカメラベクトルに一致するように、ｍ枚の連続したカメラベクトルのスケール調整をすることができる。
このようにして、画像の進行とともにｎが連続的に進行することにより、同一特徴点について複数回演算されて得られる各カメラベクトルの誤差が最小になるようにスケール調整して統合し、最終のカメラベクトルを決定することができる。これにより、誤差のない高精度のカメラベクトルを求めつつ、簡易演算を組み合わせることにより、演算処理を高速化することができるようになる。
【０１３７】
ここで、簡易演算としては、精度に応じて種々の方法があるが、例えば、(1)高精度演算では１００個以上の多くの特徴点を用いる場合に、簡易演算では最低限の１０個程度の特徴点を用いる方法や、(2)同じ特徴点の数としても、特徴点とカメラ位置を同等に考えれば、そこには無数の三角形が成立し、その数だけの方程式が成立するため、その方程式の数を減らすことで、簡易演算とすることができる。
これによって、各特徴点及びカメラ位置の誤差が最小になるようにスケール調整する形で統合し、距離演算を行い、さらに、誤差の分布が大きい特徴点を削除し、必要に応じて他の特徴点について再演算することで、各特徴点及びカメラ位置での演算の精度を上げることができる。
【０１３８】
また、このように高速な簡易演算を行うことにより、カメラベクトルのリアルタイム処理が可能となる。カメラベクトルのリアルタイム処理は、目的の精度をとれる最低のフレーム数と、自動抽出した最低の特徴点数で演算を行い、カメラベクトルの概略値をリアルタイムで求め、表示し、次に、画像が蓄積するにつれて、フレーム数を増加させ、特徴点の数を増加させ、より精度の高いカメラベクトル演算を行い、概略値を精度の高いカメラベクトル値に置き換えて表示することができる。
【０１３９】
さらに、本実施形態では、より高精度のカメラベクトルを求めるために、三次元情報（三次元形状）の追跡を行うことができる。
具体的には、まず、三次元情報追跡部２-５で、カメラベクトル演算部２-３，誤差最小化部２-４を経て得られたカメラベクトルを概略のカメラベクトルと位置づけ、その後のプロセスで生成される画像の一部として得られる三次元情報（三次元形状）に基づいて、複数のフレーム画像に含まれる部分的三次元情報を隣接するフレーム間で連続的に追跡して三次元形状の自動追跡を行う。
そして、この三次元情報追跡部２-５で得られた三次元情報の追跡結果から、高精度カメラベクトル演算部２-６においてより高精度なカメラベクトルが求められる。
【０１４０】
上述した特徴点抽出部２-１及び特徴点対応処理部２-２では、特徴点を複数のフレーム間画像内に自動追跡するが、特徴点が消失するなどして特徴点の追跡フレーム数に制限が出てくることがある。また、画像は二次元であり、追跡途中で形状が変化するために追跡精度にも一定の限界がある。
そこで、特徴点追跡で得られるカメラベクトルを概略値と位置づけ、その後のプロセスで得られる三次元情報（三次元形状）を各フレーム画像上に追跡して、その軌跡から高精度カメラベクトルを求めることができる。
三次元形状の追跡は、マッチング及び相関の精度を得やすく、三次元形状はフレーム画像によって、その三次元形状も大きさも変化しないので、多くのフレームに亘って追跡が可能であり、そのことでカメラベクトル演算の精度を向上させることができる。これはカメラベクトル演算部２-３により概略のカメラベクトルが既知であり、三次元形状が既に分かっているから可能となるものである。
【０１４１】
カメラベクトルが概略値の場合、非常に多くのフレームに亘る三次元座標の誤差は、特徴点追跡による各フレームに関係するフレームが少ないので、誤差が累積して長距離では次第に大きな誤差になるが、画像の一部分を切り取ったときの三次元形状の誤差は相対的に少なく、形状の変化と大きさに及ぼす影響はかなり少ないものとなる。このため、三次元形状での比較や追跡は、二次元形状追跡の時よりも極めて有利となる。追跡において、二次元形状での追跡の場合、複数のフレームにおける形状の変化と大きさの変化を避けられないまま追跡することになるので、誤差が大きかったり、対応点が見つからないなどの問題があったが、三次元形状での追跡においては形状の変化が極めて少なく、しかも原理的に大きさの変化もないので、正確な追跡が可能となる。
【０１４２】
ここで、追跡の対象となる三次元形状データとしては、例えば、特徴点の三次元分布形状や、特徴点の三次元分布形状から求められるポリゴン面等がある。
また、得られた三次元形状を、カメラ位置から二次元画像に変換して、二次元画像として追跡することも可能である。カメラベクトルの概略値が既知であることから、カメラ視点からの二次元画像に投影変換が可能であり、カメラ視点の移動による対象の形状変化にも追従することが可能となる。
【０１４３】
以上のようにして求められたカメラベクトルは、全周ビデオカメラ１-１で撮影されたビデオ映像中に重ねて表示することができる。
例えば、図１９に示すように、車載カメラからの映像を平面展開して、各フレーム画像内の目的平面上の対応点を自動で探索し、対応点を一致させるように結合して目的平面の結合画像を生成し、同一の座標系に統合して表示する。
さらに、その共通座標系の中にカメラ位置とカメラ方向を次々に検出し、その位置や方向、軌跡をプロットしていくことができる。ＣＶデータは、その三次元位置と３軸回転を示しており、ビデオ映像に重ねて表示することで、ビデオ映像の各フレームでＣＶ値を同時に観察できる。ＣＶデータをビデオ映像に重ねて表示した画像例を図１９に示す。
【０１４４】
なお、ビデオ映像内にカメラ位置を正しく表示すると、ＣＶ値が示すビデオ映像内の位置は画像の中心となり、カメラ移動が直線に近い場合は、すべてのフレームのＣＶ値が重なって表示されてしまうので、例えば図１９に示すように、敢えてカメラ位置から真下に１メートルの位置を表示することが適切である。あるいは道路面までの距離を基準として、道路面の高さにＣＶ値を表示するのがより適切である。
そして、以上のようにしてＣＶ演算により得られたＣＶ値データが、本実施形態に係る三次元地図自動生成装置１００（図１、図６参照）に入力され、上述した映像のみに基づく三次元地図の自動生成が行われることになる。
【０１４５】
以上、本発明の三次元地図自動生成装置について、好ましい実施形態を示して説明したが、本発明は、上述した実施形態にのみ限定されるものではなく、本発明の範囲で種々の変更実施が可能であることは言うまでもない。
例えば、本発明の三次元地図を備えるナビゲーション装置、自動運転装置が搭載される各種の移動体に適用が可能であり、適用する移動体としては、地上を走行する車両は勿論のこと、地上車両に限らず、三次元空間を航行するものであっても良い。飛行機でも利用可能であるから、着陸時の精度の高いナビゲーションや自動運転が可能である。
【産業上の利用可能性】
【０１４６】
本発明は、例えば、自動車に搭載されるカーナビゲーション装置、飛行機に搭載されるナビゲーション装置、危険な箇所での無人自動運転重機、自動運転用のナビゲーション装置、ロボットのナビゲーション装置などに好適な三次元地図の自動生成に好適に利用することができる。
【符号の説明】
【０１４７】
１ 動画像取得装置
２ ＣＶ映像生成装置
３ 領域分割装置
４ フレーム内小領域特徴点三次元化装置
５ 複数領域ポリゴン化装置
６ 連続処理装置
７ テクスチャー取得装置
【技術分野】
【０００１】
本発明は、機械が人に代わって位置等を判断する為の機械地図装置やカーナビゲーション装置などにおいて、対象物を三次元的に表示する三次元地図を自動生成するための三次元地図自動生成装置に関する。
【背景技術】
【０００２】
機械地図装置やカーナビゲーション装置などにおいては、対象物を三次元的に表示する三次元地図の生成技術が利用されている。
三次元地図では、例えば道路や建物などの対象物について高さ方向を含む立体的な三次元情報が表示されるため、対象物を容易かつ正確に把握することができ、二次元地図では得られない有用な地図情報が得られるようになる。
【０００３】
従来の三次元地図自動生成の技術としては、航空機からレーザーなどで地表を測量し、地表の三次元データを取得して、地上から撮影した視差による三次元データと組み合わせて詳細部分を計測し、それから３ＤＣＧ（コンピュータグラフィックス）を生成し、さらに地上から撮影した対象物のテクスチャーを切り取って３ＤＣＧに貼り付ける等の処理によって生成していた（特許文献１−３参照。）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０００−０６６５８３号公報
【特許文献２】特開２００２−０９８５３８号公報
【特許文献３】特開２００３−１１４６１４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記のような従来の三次元地図自動生成の技術では、三次元地図の生成を手動で行っており、三次元地図生成の自動化が進まないために、莫大なコストがかかるという問題があった。
すなわち、上記のような従来の三次元地図の技術では、高価な機器を必要とし、しかも、膨大な手間と費用をかけなければ三次元地図を作成できないという問題があった。特に、従来の技術では、地図や画像を人間が見ながら、手動でポリゴンを指定しなければならないので、時間と人手が係り、コストがかかることになっていた。
また、そのようにして生成される三次元地図は、点や線のみで表示される構成で、それなりの長所もあるものの、人間が見るためには適さないという欠点もあった。
【０００６】
ここで、通常の安価なカメラで撮影される映像であっても、映像は三次元情報を含んでおり、そこから三次元地図の生成に必要となる三次元情報を抽出することは可能であり、また、二台のカメラで撮影した視差から三次元情報を抽出することも可能であった。従って、通常のカメラを車両などに搭載して移動しながら対象物を撮影し、そこから三次元情報を抽出して三次元地図を生成することは、理論上は可能である。
しかしながら、単に通常のカメラで映像を撮影しただけでは、撮影するカメラが移動するために、揺れ等の外乱を受け、座標がぶれ、回転し、位置として安定な映像を取得，抽出できず、それだけでは三次元情報を高精度に抽出することはできない。
【０００７】
特に、カメラ位置とカメラ姿勢は、カメラを搭載した車両等の移動につれて刻々変化するので、その三次元位置を精度良く計測できなければならない。また、カメラの３軸方向の回転と移動を正確に抽出できなければ、精度の良い三次元地図を生成することはできない。
また、二台のカメラで撮影した、いわゆるステレオカメラによる視差からの三次元抽出では、静止カメラでは可能であっても、車載による車両移動にともなうカメラ移動には追従できないことになり、カメラからの距離は計測できても、カメラ移動にともなう画像内の三次元解析は一般には出来ない。
【０００８】
この欠点を補うための既知の技術としては、ＧＰＳやＩＭＵ、ジャイロ、レーザー等のセンサーにより、カメラ移動をこれら機械センサーで計測して、刻々移動するカメラ位置を追跡する方法があるが、この装置は高価で、大がかりで、しかも不安定で、しかも使用には様々な制限があり、実用的ではない。
ＧＰＳ、ＩＭＵ、ジャイロ等の機械センサーを用いたとしても、それはカメラ位置のデータであり、画像内に移り込んでいる対象物のデータではない。このため、結局は画像解析が必要となるため、機械センサーとカメラの同期、位置合わせ等にかなりの労力が必要となり、しかも光学系・機械系の双方を含むため、外乱に対して不安定で、振動に弱く、カメラ移動カメラ進行方向、及び遠方の対象物に対する精度に限界があった。
また、レーザーや機械センサーで一度取得したデータに誤差が含まれていれば、その後の処理での修正は原理的にほとんど不可能である。
【０００９】
また、カメラで得られた映像から三次元形状を生成する場合、三次元形状を構成するポリゴンの抽出には、どうしても手動によるポリゴン生成のプロセスは避けられず、その部分が費用増大を招き、特に大規模に三次元地図を生成することは事実上不可能であった。すなわち、従来の三次元地図の生成技術においては、人間でなければ対象物のポリゴンをうまく認識して取得することはできず、特に都市空間ほどの大規模な三次元地図等に対するポリゴン生成は現実の実施はきわめて困難であった。
【００１０】
また、レーザーによる三次元計測も行われるようになっているが、レーザーで行われるのは、対象物の面までの距離の計測であり、対象物の形状の計測ではないため、境界線を抽出できず、対象物の形状を精度良く取得することはできなかった。
さらに、従来の三次元地図の生成技術において、個々にＣＧを生成してそれを地図中に結合しても、整合が取れず、例えば大規模な都市構造をＣＧ化するようなことは困難であった。
そこで、本願発明者は、鋭意研究の結果、上記のような機械センサーを用いることなく、また、機械センサーを用いたとしても、概略値を知るために補助的に用いる程度で、本質的には画像のみから画像解析を行うことにより三次元地図の自動生成を可能とする本願発明に想到したものである。
【００１１】
すなわち、本願発明は上述したような従来の技術が有する問題を解決するために提案されたものであり、高価な機器を必要とせず、安価なカメラで、複数のカメラ（原理的には一台のカメラ）を車両に積載して周辺状況を撮影し、あるいは人がカメラを手に持って周囲を撮影し、その映像を解析して、そこから三次元情報を抽出して、画像処理技術により三次元形状を生成し、三次元地図を自動生成することができる三次元地図自動生成装置の提供を目的とする。
【課題を解決するための手段】
【００１２】
上記目的を達成するため、本発明の三次元地図自動生成装置は、動画映像の複数のフレーム画像から充分な数の特徴点を自動検出し、さらに、各フレーム間で特徴点を自動追跡し、多数の特徴点について重複演算してカメラ位置と回転角を高精度に求め、それを統計的処理により、また、三次元解析処理することにより、さらに画像を前もって領域に自動分割することによって、自動的に分割された画像から、精度の良い三次元データを抽出するものである。
しかも、領域の自動抽出から、その領域内の三次元特徴点を解析することで、ポリゴンを自動生成することにより、高精度にポリゴンを生成し、高精度な三次元地図を完全自動により生成するものである。
【００１３】
三次元地図を自動的に低コストで効率よく生成するためには、画像を自動的に三次元解析することと、画像を効率的に領域に分割し、その領域を結合し、又は統合して、自動的に効率よく目的のポリゴンを生成することが求められる。
そこで、本発明の三次元地図自動生成装置は、以下のような構成を備えるようになっている。
【００１４】
第一に、移動体に設置された動画又は連続静止画を得るカメラからの映像を取得する動画像取得装置を備えている。
また、動画像取得部で取得された動画像を自動三次元解析するために、多くの特徴点を自動発生させ、その特徴点を隣接するフレームに自動トラッキングし、そのトラッキングデータから、対象物及び背景の座標計に対するカメラの位置と姿勢を六変数で取得する所定のカメラベクトル映像（ＣＶ映像）を自動生成するＣＶ映像生成装置を備える。
さらに、このＣＶ映像又はその元となる動画映像から色又は明るさの変化するラインを境界とする領域に自動分割する領域分割装置を備える。
【００１５】
領域に分割された各領域はＣＶ映像の一部であることから、既に既知となっているＣＶ値から領域分割された個々の領域を自動三次元解析して、あるいは詳細に解析するために、新たに個々の領域に特徴点を集中的に自動発生させ、それを自動トラッキングし、そこからＣＶ値を求めるプロセスを繰り返して、各領域の三次元形状を自動的に求めることができる。
そして、各領域の三次元形状を結合する過程で、ポリゴンを取得する。このポリゴンを座標上に配列することで求める三次元地図が取得できる。
【００１６】
以上のような本発明の三次元形状生成装置によれば、機械センサーを使用せず、動画像のみから三次元解析を通して、機械地図を生成することが可能となる。機械センサーを使用するとしても、概略位置のデータとして使用する程度であり、本質的なものではない。
動画映像の複数のフレーム画像から充分な数の特徴点を自動検出し、各フレーム間で特徴点を自動トラッキング（追跡）することにより、多数の特徴点について重複演算してカメラ位置と回転角を高精度に求めることができる。従って、通常の安価なカメラであっても、人がカメラをもって移動しながら撮影し、あるいはカメラを積載した移動する車両等から周囲画像を撮影し、その映像を分析してカメラ軌跡を三次元位置と三軸姿勢の六変数で求めることができる。
【００１７】
そして、その三次元位置と三軸姿勢の六変数のカメラパラメータを基準として、カメラ映像内の複数の領域を抽出し、その領域を三次元解析して、それらの三次元解析された領域から対象物、及び背景の三次元形状を再構成することで、対象物の三次元形状を表現し、それを連続して実施することで三次元地図を自動生成することができる。
これにより、従来技術のような高価な機器や膨大な手間と費用を必要とすることなく、安価かつ高精度に三次元地図を生成することができる。
【００１８】
なお、本発明は、移動するカメラによって得られる映像のみでなく、並列に設置した二台のカメラによるＣＶ映像からの情報を併用することも勿論可能である。さらには複数台のカメラを用いて、精度を向上させることも可能である。
機械センサーのデータ取得は一度限りであるが、本発明は機械センサーによらないので、設置が簡単であること、画像から三次元データを解析するので、データ画像が有ればいつでもどこでも目的に応じた解析を何度でも繰り返すことができる、というメリットがある。例えば、精度が必要であれば、特徴点を増加させて、最演算することで、精度の高いＣＶ値を必要に応じて取得できること。カメラ位置は画像から取得されるので、カメラ位置と同時に、映像に映り込んでいる対象物及び背景を同時に三次元解析できること。これは機械センサーにはできないことである。
また、異なる日時に撮影した映像であっても、それぞれの映像のＣＶ値を座標統合することで、追加撮影された映像を複合的に扱うことが可能である。
【００１９】
機械センサーに比較して軽量である。原理的にカメラだけでも良いので、単純である。映像からデータを演算で求めるので、極端な振動に対しても、追従することから、振動にもきわめて強い。振動によってデータが狂うことはない。
映像から取得するので、広範囲に撮影された地域でバラバラに取得された映像を一気に処理して、機械センサーの場合のように、いちいちキャリブレーションする必要もない。決められた座標系で目的にあわせて表現することが可能となる。ＣＶ映像さえ取得できれば、いかなる種類の映像でも利用できるので、安価に広範囲な地域を一気に三次元化することが可能となる。
【００２０】
以上のように、本発明の三次元地図自動生成装置によれば、カメラで得られる動画又は連続静止画の映像に基づいて、対象物、及びその背景を含めて、その三次元形状を求め、必要であればそのテクスチャーを自動的に取得して、三次元地図を自動的に生成することができる。
特に、本発明では、高価な機器や膨大な手間と費用などを必要とすることなく、完全自動により、背景を含めた対象物との座標を矛盾無く整合して、簡易かつ高精度に、三次元形状を求めて、大規模に三次元地図を生成することができる。
【００２１】
このように、本発明によれば、三次元形状、及び背景との座標関係に矛盾が無いように、高精度の三次元地図を生成でき、また、人間が見るための地図としても十分な品質のものが得られる。
従って、本発明は、自動車、重機、航空機等の移動体の三次元位置を自動評定したり、移動体の進行方向や現在状況等を自動ガイドするための三次元地図と、その三次元地図自動生成装置として好適に利用することができる。
【発明の効果】
【００２２】
本発明の三次元地図自動生成装置によれば、高価な機器を必要とせず、安価なカメラで、複数のカメラ（原理的には一台のカメラ）を車両に積載して周辺状況を撮影し、あるいは人がカメラを手に持って周囲を撮影し、その映像を解析して、そこから三次元情報を抽出して、画像処理技術により三次元形状を生成し、三次元地図を自動生成することができる。
【図面の簡単な説明】
【００２３】
【図１】本発明の一実施形態に係る三次元地図自動生成装置の構成を示すブロック図である。
【図２】本発明の一実施形態に係る三次元地図自動生成装置で行われるＣＶ演算の概念を示す説明図である。
【図３】本発明の一実施形態に係る三次元地図自動生成装置で行われるＣＶ演算の概念を示す説明図である。
【図４】本発明の一実施形態に係る三次元地図自動生成装置で行われる三次元地図の生成処理を模式的に示す説明図である。
【図５】本発明の一実施形態に係る三次元地図自動生成装置で行われる三次元地図の生成処理を模式的に示す説明図である。
【図６】本発明の他の実施形態に係る三次元地図自動生成装置の構成を示すブロック図である。
【図７】本発明の三次元地図自動生成装置のＣＶ映像生成装置（ＣＶ演算装置）として機能するＣＶ演算部の一実施形態の基本構成を示すブロック図である。
【図８】図７に示すＣＶ演算部で使用する全周ビデオ映像を撮影する手段を示す概略図であり、屋根部に全周カメラを搭載した車輌の斜視図である。
【図９】図７に示すＣＶ演算部で使用する全周ビデオ映像を撮影する手段を示す概略図であり、（ａ）は屋根部に全周カメラを搭載した車輌の正面図、（ｂ）は同じく平面図である。
【図１０】全周カメラで撮影される映像から得られる変換画像を示す説明図であり、（ａ）は球面画像が貼り付けられる仮想球面を、（ｂ）は仮想球面に貼り付けられた球面画像の一例を、（ｃ）は（ｂ）に示した球面画像をメルカトール図法に従って平面展開した画像を示している。
【図１１】本発明の一実施形態に係るＣＶ演算部における具体的なカメラベクトルの検出方法を示す説明図である。
【図１２】本発明の一実施形態に係るＣＶ演算部における具体的なカメラベクトルの検出方法を示す説明図である。
【図１３】本発明の一実施形態に係るＣＶ演算部における具体的なカメラベクトルの検出方法を示す説明図である。
【図１４】本発明の一実施形態に係るＣＶ演算部によるカメラベクトルの検出方法における望ましい特徴点の指定態様を示す説明図である。
【図１５】本発明の一実施形態に係るＣＶ演算部により得られる特徴点の三次元座標とカメラベクトルの例を示すグラフである。
【図１６】本発明の一実施形態に係るＣＶ演算部により得られる特徴点の三次元座標とカメラベクトルの例を示すグラフである。
【図１７】本発明の一実施形態に係るＣＶデータ演算部により得られる特徴点の三次元座標とカメラベクトルの例を示すグラフである。
【図１８】本発明の一実施形態に係るＣＶ演算部において、カメラから特徴点の距離に応じて複数の特徴点を設定し、複数の演算を繰り返し行う場合を示す説明図である。
【図１９】本発明の一実施形態に係るＣＶデータ演算部求められたカメラベクトルの軌跡をビデオ映像中に表示した場合の図である。
【発明を実施するための形態】
【００２４】
以下、本発明に係る三次元地図自動生成装置の実施形態について、図面を参照しつつ説明する。
ここで、以下に示す本発明の三次元地図自動生成装置は、プログラム（ソフトウェア）の命令によりコンピュータで実行される処理，手段，機能によって実現される。プログラムは、コンピュータの各構成要素に指令を送り、以下に示すような所定の処理や機能、例えば、映像中からの基準点や特徴点の自動抽出，抽出した基準点の自動追跡，基準点の三次元座標の算出，ＣＶ（カメラベクトル）値の演算等を行わせる。
このように、本発明における各処理や手段は、プログラムとコンピュータとが協働した具体的手段によって実現される。なお、プログラムの全部又は一部は、例えば、磁気ディスク，光ディスク，半導体メモリ，その他任意のコンピュータで読取り可能な記録媒体により提供され、記録媒体から読み出されたプログラムがコンピュータにインストールされて実行される。また、プログラムは、記録媒体を介さず、通信回線を通じて直接にコンピュータにロードし実行することもできる。
【００２５】
［三次元地図自動生成装置］
まず、図１を参照して、本発明の一実施形態に係る三次元地図自動生成装置１００の概略構成を説明する。
図１は、本発明の一実施形態に係る三次元地図自動生成装置１００の構成を示すブロック図である。
同図に示すように、本実施形態に係る三次元地図自動生成装置１００は、動画像取得装置１、ＣＶ映像生成装置２、領域分割装置３、フレーム内小領域特徴点三次元化装置４、複数領域ポリゴン化装置５、連続処理装置６、及びテクスチャー取得装置７の各部を備えた構成となっている。
【００２６】
動画像取得装置１は、移動する撮影車両に積載された全周カメラにより（後述する図８、図９参照）、周囲の対象物及びその背景の動画像を取得する画像取得手段である。
ここで、動画像取得装置１が搭載される撮影車両としては、一般的には自動車が想定されるが、移動車両（移動体）は航空機であっても船舶であっても考え方は同じである。
また、動画像取得用のカメラは、必ずしも全周カメラでなくても良いが、誤差を少なくするためには全周カメラが望ましい。通常のカメラの場合は、得られた映像は全周カメラから得られた映像の一部の映像として扱うことで、全周カメラと同じように扱うことができる。
【００２７】
ＣＶ映像生成装置２は、動画像取得装置１によって取得された動画像から、映像に映っている背景と対象物に固定された静止座標系に対して移動しているカメラ位置とカメラ姿勢を、前記静止座標系に対する三次元位置、三軸回転姿勢を示す六変数（X,Y,Z,θx,θy,θz）、すなわちカメラベクトル値（ＣＶ値）を後述するＣＶ演算装置（図６に示すＣＶ演算装置２１参照）により自動演算で求め、そのＣＶ値を動画像取得装置１で得られた動画像の各フレームと対応させたカメラベクトル映像（ＣＶ映像）を生成する。
【００２８】
ここで、全周カメラによるＣＶ値及び全周カメラからＣＶ値を求めるＣＶ演算については、本発明者が既に特許取得している特許（特許第４４４６０４１号）に詳細に記載されているが、全周映像の中に特徴点を自動抽出し、それを隣接する複数フレームにトラッキングし、カメラ移動のベースとトラッキング点で校正する三角形を構成し、そのトラッキングデータを解析することで、特徴点の三次元座標と、カメラ位置と姿勢を持つ全周ＣＶ映像を取得することができる。ＣＶ値とは、カメラの位置と姿勢を６自由度（六変数と同義）で表現したものである。即ち、全フレームについてｘ，ｙ，ｚ，θx，θy，θz，の６自由度のそれぞれの係数を演算で決定することになる。
【００２９】
具体的には、ＣＶ（Camera Vector）値というのは、カメラの焦点の三次元位置Ｔと三次元姿勢Ｒを合わせた6自由度の量のことであり、実際にカメラで撮影した映像情報だけを用いて、２次元的な画像解析によりＣＶ値を統計的に算出する、つまりＣＶ演算することが可能である。
ＣＶ値を持った映像（ＣＶ映像）では、２次元の映像内に映っている全ての対象物について、３次元空間解析が可能となる。これにより、あたかも現実のコピーのように、３次元位置を特定したり、距離や長さを計測したりすることができるようになる。
これらＣＶ演算及びＣＶ映像を用いた３次元空間解析技術を総称してＣＶ技術といい、このＣＶ技術が本発明に係る三次元地図自動生成装置１００の基礎となるものである。
【００３０】
ＣＶ演算は、一般のカメラでも可能ではあるが、処理をシンプルにするために、通常は全周カメラを用いることが望ましい。全周カメラの場合、撮影された映像は焦点を中心に全天球を覆うことなる（全周映像：図２左側図参照）。この映像を、正距円筒図法を用い平面で展開すると図２右側のような画像となる。
これを式で表すと下記の式１のようになる。
【００３１】
【数１】
【００３２】
ＣＶ技術においては、全周映像の特徴点トラッキング処理が行われる。
具体的には、動画の各フレーム画像を２次元に解析し特徴点を抽出し、複数のフレーム間で同一の特徴点を画像比較により見つける。これを特徴点トラッキングと呼ぶ。
同一特徴点の発見には、下記の式２に示したような相互関数（畳み込み）関数の最大になるところを探すことで見つけることができる。
コンピュータ上では、離散値である画像のピクセルにこれを適用するので、下記の式３が最大になるピクセル(x, y)を見つけることになる。
【００３３】
【数２】
【００３４】
【数３】
【００３５】
ＣＶ値の計算は以下のようにして行う。
特徴点の実際の三次元位置をＰ（３次元ベクトル）として表す。また、上述した通り、ｎ番目のフレームのＣＶ値は、三次元位置Ｔｎが３次元ベクトル、三次元姿勢Ｒｎが３行３列の回転行列で表される。これらは全て未知数である。
一方、ｎ番目のフレームでのトラッキング結果を、極座標変換して３次元ベクトルで表現し、Ｐｎとおく。既知の情報はこれだけである。
ＰとＴｎ、Ｒｎから計算される画像上の投影点がＰｎに重なるという条件から方程式を立てると下記の式４のようになる。ここでは長さを除いて方向が等しいことを意味している。
【００３６】
【数４】
【００３７】
この式４が特徴点の数（通常数百個）だけ成立する。
ここで、数学の記法により、上記のように簡潔に表現できるが、コンピュータ上で扱うためには膨大な数の連立方程式となる。実際には未知数の数以上に方程式があり、さらにそれぞれが微少な誤差を持っているため、厳密にはこの方程式の解は存在しないことになる。
そこで、本発明に係るＣＶ演算処理では、コンピュータによる連立方程式の解として、誤差を統計的に処理し、誤差が最小となる解（ＰとＴｎ、Ｒｎ）を求めるようにする。
【００３８】
以上のようなＣＶ演算及びＣＶ演算装置の詳細については後で更に詳述する（図７〜図１９参照）。
なお、ＣＶ映像は、カメラ位置とカメラ姿勢の六変数を各画像フレームに対応させたものであることから、ここに示したＣＶ演算による手法以外に、ＧＰＳ、ＩＭＵ、Ｊａｙｒｏ（ジャイロ）等の機械センサーによっても上記ＣＶ値と同等の六変数を取得することができる。
【００３９】
以上のようなＣＶ映像生成装置２で得られたＣＶ映像（動画）は、一般的に連続する多数の静止画フレームから成り立っている。
領域分割装置３は、このような多数のフレームの中から、コンピュータが自動的にある（特定の）フレームを選択し、指定した画像フレーム（静止画）を取り出し、その中に写っている複数の対象物及び背景を、画像の輝度分布等から、及び／又は色相分布、及び／又は彩度分布等から分類し、密度の固まりで切り取り、指定された大きさと数の範囲で、互いに隣接する複数の小領域に分割した領域分割画像を演算によって自動取得する。
【００４０】
ここで、上記のようにして得られる小領域は一般的に目的の対象物そのものでもなく、背景そのものでもない。
ここでは、小領域が目的の対象物を構成する複数のポリゴンそのもの、又はその一部となっていることを前提とする。最終的に小領域が対象物、及び背景のポリゴンとして適切であることが望ましい。
対象物を構成するポリゴンは、その選択の仕方によって幾通りも可能であるため、小領域がポリゴンの一部となることを期待することは特に非合理的ではない。
ただし、結果として、映像の輝度が飽和している場合や、非常に暗い場合には、この小領域が対象物の境界をまたいでしまうこともある。その時は、異なるフレームから取得した分割画像で再度、小領域を求めることで問題は解消できる。
【００４１】
なお、領域分割装置３における領域分割処理そのものは、既知の技術である。
ただし、既知の技術で得られた領域分割された画像が、ＣＶ映像から得られた領域分割画像であることから、すべての領域分割画像は、上述したＣＶ映像生成装置で得られたＣＶ映像のいずれかのフレームに対応している。
従って各領域分割画像はＣＶを持っていることになる。
このように、領域画像がＣＶ値を持つことが本発明における重要な特徴となる。
【００４２】
領域分割画像得るためには、例えば、既知の技術としてのヒストグラムの閾値処理手法がある。このヒストグラムの閾値処理手法はモノクロの画像の領域分割対して広く用いられている手法の一つであるが、三原色に分離された各原色に対しても有効である。
各原色の画像は異なる階調値の幅を持った領域から構成されると仮定し、入力画像のヒストグラムを分割領域に対応する幾つかのピークすなわち、分布の最頻値に分割することができる。二つの隣接するピーク間の「谷」に対する閾値を探索することで効果的に領域に分割することができる。
【００４３】
従って、既知の技術を用いて、最も明確に分離させるピークをもつヒストグラムを選択し、閾値処理を行うなどして、領域分割を行うことが可能である。
なお、ヒストグラム手法以外にはクラスタリング手法などがある。
いずれの手法であっても、元となる画像がＣＶ値を持っていることが本発明の特徴であり、以下に示すフレーム内小領域特徴点三次元化装置４による分割領域三次元化処理で、ＣＶ値を使って小領域を三次元化することが第二番目の重要な特徴となる。
【００４４】
フレーム内小領域特徴点三次元化装置４は、フレーム内小領域特徴点発生装置４１（図１参照）において、上記のような領域分割画像の小領域に対応しているフレーム内小領域に発生させた複数の特徴点を、フレーム内小領域でトラッキングし、複数特徴点の三次元座標を演算によって求め、領域分割画像内の小領域内に対応させて移転した特徴点の三次元座標に対応させる。
図４に示すように、ＣＶ映像の中から、自動的に指定された１フレームを取り出し（図４に示すフレーム１０２、１０４参照）、それが領域分割装置３に送られ、領域分割装置３によって領域分割が行われる（図４に示す領域分割画像１０３、１０５参照）。
【００４５】
ここで取得された領域分割画像内の1単位を小領域と定義する。一般に領域分割画像は複数の小領域から成り立っている。小領域はその境界が明確で閉じていることか望ましいが、一部閉じていない場合でも、一部境界を未知として扱うことで、本質的な問題は生じない。
ここで、上述した本発明の重要特徴である対応関係にあるＣＶ映像のフレームに戻り、そのフレームのＣＶ値を小領域のＣＶ値と定義できる。
この小領域は、その領域分割画像の生成過程に戻れば、ＣＶ映像上に常に対応がとれているので、小領域ＣＶ映像はＣＶ映像に戻って対応が取れていることになる。小領域に対応するＣＶ映像の１フレームの一部分をフレーム内小領域と定義する。
【００４６】
そこで、各小領域に対応するＣＶ映像内のフレーム内小領域を、当該ＣＶ映像のフレームのＣＶ値を既知として、フレーム内小領域に複数の特徴点を発生させる。当然、これらフレーム内小領域で発生させた特徴点は、対応する領域分割画像の小領域内にあることになる。
なお、ここでの特徴点は、ＣＶ映像を生成するために既に一度発生されているで、その時に発生させてある複数の特徴点をこの特徴点に追加させることも可能である。
そして、フレーム内小領域特徴点三次元化装置４では、このように当該領域分割画像の小領域に対応しているフレーム内小領域に発生させた複数の特徴点を、既知のＣＶ値を用いてトラッキングを予想し、フレーム内小領域でトラッキングし、複数特徴点の三次元座標を演算によって求め、領域分割画像内の小領域内に対応させて移転した特徴点の三次元座標に対応させる。
【００４７】
複数領域ポリゴン化装置５は、複数のフレーム内小領域の中で取得された複数の特徴点の三次元座標から、対応する小領域の面の法線を求め、面の形状を推定し、当該小領域を隣接小領域と統合又は分割するなどして、所望のポリゴンを推定して生成することができる。
そして、その作業を次々と隣接する複数の小領域に拡大し、可能な限りのポリゴンを自動生成することができる。
【００４８】
連続処理装置６は、上記のようなポリゴン生成までの処理を繰り返し実行することで、ポリゴンを順次生成し、目的の対象物と背景からなる三次元化地図を連続的に結合して、広範囲な三次元地図を自動生成する。
ここで、領域分割画像内のすべての小領域について、そのポリゴンを求めようとしても、画像が常に最適の状態ではないことがあり、全体の一部のポリゴンしか求められない場合がある。しかしながら、そのような場合でも、次に指定されるＣＶ映像のフレームには、重複して背景及び対象物が映っているので、一枚の領域分割画像からすべてのポリゴンを決定する必要はない。
【００４９】
そして、領域分割画像に対応しているＣＶ映像のフレームに関する処理により、適切な数の領域ポリゴン生成まで済んだところで、ＣＶ映像のフレームを進行させる。
次の新たな領域分割画像を自動指定して、上述した領域分割装置３、フレーム内小領域特徴点三次元化装置４、複数領域ポリゴン化装置５における処理を繰り返すことで、先の領域分割画像では未だ生成できていないポリゴンを生成することができる。そして、次の領域分割画像に初めて現れ、しかも一部取得済みのポリゴンに連続しているポリゴンを生成することができる。
【００５０】
さらに、次々に適切な時点で指定されるＣＶ映像のフレームから得られる領域画像から、ポリゴンを次々に生成し、目的の対象物と背景からなる三次元化地図を連続的に結合し、広範囲な三次元地図を自動生成する。
以上のような領域分割画像の指定からポリゴン生成までの処理が、連続処理装置６の制御により連続して繰り返し行われて、三次元地図が生成されることになる。
【００５１】
フレーム内小領域特徴点三次元化装置４は、図１に示すように、小領域境界特徴点発生装置４３と特徴点三次元化装置４２を備えている。
小領域境界特徴点発生装置４３は、領域分割装置３によって取得された領域分割画像内の小領域に対応するフレーム内小領域の中に、多くの特徴点を発生させる場合に、特にその小領域の境界付近に多くの特徴点を発生させる。
このようにすることで、領域の形状を含めて効率よく、精度良く三次元点を取得できるようになる。
【００５２】
また、特徴点三次元化装置４２は、領域分割画像に対応しているフレーム内小領域において、発生させた複数の特徴点を、既に既知となっているＣＶ値を用いて、複数の隣接フレームへの特徴点の移動を予測しながら、トラッキングすることで、複数の特徴点の三次元座標を取得する。
隣接フレーム間で特徴点をトラッキングする際、原理的に、ＣＶ値の分かっている画像における特徴点はエビポーラ線上を移動する。さらに、ＣＶ値が分かっているフレームにおいては、隣接の特徴点がトラッキングできた時点で、それ以降のフレームのトラッキングポイントはほぼ完璧に予想できる。
【００５３】
このようにＣＶ値の既知であるＣＶ映像内のフレーム内小領域を用いることの重要で優れた長所は、ライン上又は点上（きわめて狭い範囲上）にトラッキングポイントを予測できるために、ＣＶ値がない映像では、その点を他の方法では特徴点とは識別しないような場合にでも、特徴点として利用可能となることである。その結果、対象物のライン上に高密度に有効な特徴点をとることが可能となることである。
そこで、トラッキングするすべてのフレームにおいて、予想値付近に落ちるトラッキングポイントを確認し、さらに予想地点付近により完全に一致する点を微調整して求め、その点を正確なトラッキングポイントとして決定すればよいことになる。
特徴点三次元化装置４２は、このようにして、複数の隣接フレームへの特徴点の移動を予測しながらトラッキングすることで、複数の特徴点の三次元座標を取得する。
【００５４】
また、複数領域ポリゴン化装置５１は、領域面推定装置５１を備え、小領域三次元化装置によって取得された小領域内の複数の特徴点の三次元データに基づいて、所定の平面推定・直線推定・直角推定・水平推定・鉛直推定（図１に示す符号５２参照）等の各領域面の推定処理を行う。
具体的には、領域面推定装置５１は、単一平面を推定する平面推定、及び／又は複数平面を推定する複数平面推定、及び／又は小領域境界の直線を推定する直線推定、及び／又は複数平面のなす角度を推定する平面交差角推定、及び／又は面を長方形と推定してその長方形の辺の長さを推定する長方形推定、及び／又は平面の法線の鉛直及び水平を推定する平面鉛直水平推定を行う。
そして、このような領域面推定処理により、取得された小領域面の形状を絞り込むことができるようになっている。
【００５５】
特徴点の追跡結果は誤差を含んでいるため、誤差を除去することが好ましい。このような特徴点の追跡結果の誤差を除去しながら都合の良い特徴点のみを利用するアルゴリズムとしては、例えば、RANSAC、ロバスト推定、部分空間分離法等が知られている。本実施形態では、RANSACにより行うことが効率的である。
RANSAC (RANdom SAmple Consensus)は、面を推定して、その面に都合の良い特徴点のみを用いて面を推定することで、小領域の面を推定することができる既知の手法である。
但し、以上に示すように各種面（平面）や線の推定処理が行われる限り、RANSACに限らず、どのような手法・アルゴリズム等であっても用いることができる。
【００５６】
まず、複数領域ポリゴン化装置５の領域面推定装置５１は、前記小領域三次元化装置によって取得された、小領域内の複数の特徴点の三次元データから、単一平面を推定する（平面推定装置）。実際の対象物は曲面で有ることもしばしばあるが、その曲面の一部となる小領域を平面と推定することは合理的である。既に取得されている三次元特徴点の分布から、例えばRANSAC手法により、推定平面を取得できる。
同様に、領域面推定装置５１は、小領域が比較的大きめの場合は、複数の平面から成る面と推定することができる（複数平面装置）。その場合の手法としては、例えばRANSAC手法を繰り返し処理することにより、一個ずつ平面を決めて、結果として複数の平面を推定できる。
同様に、領域面推定装置５１は、RANSAC手法を面ではなく線に対応させることで、小領域境界線を直線と推定する（直線推定装置）。同様にRANSAC手法により直線推定装置を複数回通すことで、複数の直線からなる境界線を推定することができる。
【００５７】
また、実際のビルディング等においては、複数面が直角に交差していることが多いので、領域面推定装置５１は、RANSAC手法により、複数平面のなす角度をいろいろな値を入力することで、直角に交差する平面を推定できる（平面直角公差推定装置）。
また、領域面推定装置５１は、同様にRANSAC手法により、面を長方形と推定して、その長方形の辺の長さを推定することができる（長方形推定装置）。
さらに、実際の対象物や背景においては、水平面や鉛直面で構成されていることが多いので、領域面推定装置５１は、同様にRANSAC手法により、平面の法線の鉛直、水平を推定する（平面鉛直水平推定装置）。
以上のような面の推定処理により、取得された小領域面の形状を絞り込むことができる。
【００５８】
テクスチャー取得装置７は、上述した複数領域ポリゴン化装置５及び連続処理装置６によって取得された三次元ポリゴンに関して、自動的に対応するＣＶ映像のフレームから、テクスチャーを取得する。
これにより、テクスチャー付きのポリゴンを自動生成することができる。
このテスクチャー取得装置７については、更に具体的内容を後述する。
【００５９】
さらに、本実施形態では、移動体に対応させるために、図６に示す移動体対応三次元地図自動生成装置１００ａとして、フレーム内小領域特徴点三次元化装置４にＲＶ演算装置４６を有するＲＶ映像生成装置４７を備えることができる。
なお、図６に示す移動体対応三次元地図自動生成装置１００ａは、ＲＶ演算装置４６を有するＲＶ映像生成装置４７を備える点を除いては、上述した図１に示す三次元地図自動生成装置１００と同様となっている。
従って、図６中、図１と共通部分については共通の符号及び名称を使用しており、各部の構成・作用等の説明は図１に係るものを援用する。
【００６０】
図６に示すＲＶ演算装置４６は、フレーム内小領域特徴点三次元化装置４によって得られたフレーム内小領域の中に生成した複数の特徴点に対して、上述したＣＶ値を使わず、新たにＣＶ演算と同様の処理を行うことで、映像に映っている移動体対象物に固定された移動座標系に対して、さらに移動しているカメラ位置とカメラ姿勢を、前記移動座標系に対する三次元位置、三軸回転姿勢を示す六変数（Xr,Yr,Zr,φx,φy,φz）、すなわちＲＶ値を自動演算で求める。
ＲＶ映像生成装置４７は、ＲＶ演算装置４６で求められたそのＲＶ値を動画像の各フレームと対応させたＲＶ映像を生成する。
さらに、フレーム内小領域特徴点三次元化装置４には、同時に移動体の特徴点三次元座標を求める特徴点三次元化装置４２を備えることができる（図６参照）。
【００６１】
ここで、ＲＶ値とは、領域画像のカメラベクトル値（Regional Vector値）のことである。
カメラの位置及び姿勢とＣＶ領域画像において、カメラと画像との関係は相対的であり、カメラと画像の一部分の位置と姿勢の三次元ベクトルで表すことが可能である。このように、カメラと画像の一部分の三次元ベクトルをＲＶ値といい、その６自由度（六変数）を求めることをＲＶ演算、ＲＶ値を持つ映像をＲＶ映像という。
【００６２】
ＣＶ値とは、上述したように、静止座標系とその中を移動するカメラの位置と姿勢の関係を六変数として表現したものである。
ところで、静止座標系とその中を移動する移動座標系とは、物理的には相対的であり、数学的には、両者を物理的に区別することはできない。
例えば、走行する列車の中の座標系とその外側に展開する大地の座標系を物理的に区別することできない。従って列車の中を歩いて移動しながらカメラで撮影した映像のＣＶ値とは、車両の内側か、車両の外側かで、本質的に区別されるものではない。カメラが車両の中を移動する場合、車両の中を映している映像と、車両の外を映している映像、及び両方が同時に映っている映像に分類できるが、仮に外側を写している映像をＣＶ映像とするならば、車両の内側を写している映像はＲＶ映像と呼ぶことができる。ＲＶとは「Regional Vector」の頭文字で「領域画像ベクトル」の意である。
【００６３】
ただし、ＣＶ映像とＲＶ映像との間には物理的・数学的に本質的な差はない。列車の窓から外を見て、そこに特徴点を発生させて、外側との関係でカメラ位置を求め、同時にその三次元座標を求めようとする場合はＣＶ演算となり、ＣＶ映像となる。そして、列車の内側のみに特徴点を発生させて、その列車の内側との関係でカメラ位置を求め、同時にその三次元座標を求めようとするとＲＶ演算となり、ＲＶ映像となる。
このように、数学的には全く変わらないが、座標系をどこにとるかでカメラ位置の表現方法は変わることになる。そこで、本明細書では、基準とする座標系を区別するために、従来の静止座標系に対する演算をＣＶ演算とし、移動する座標系に対する演算をＲＶ演算として、それぞれＣＶ映像、ＲＶ映像と呼ぶことにする。
【００６４】
ここで、ＣＶ値とＲＶ値との違いは、最初に特徴点として、外側をとるか、内側をとるかだけの違いであり、その演算手法はどちらも全く同じである。
そして一般的には、同じ映像の中に、外側も内側も同時に映っているので、ＣＶ値とＲＶ値が同時に存在することになる。
そこで、このような一般映像として考えた場合、ＲＶ値について、ＣＶ値を求める演算と切り離して処理・演算を行うのがＲＶ演算装置４６である。そこでの違いは特徴点が移動体の中か外かである。従って、小領域が移動体の一部ではなく、静止座標系の対象物の一部、又は背景の一部の場合は、ＲＶ値とＣＶ値は一致することになる。
特に、本実施形態におけるＲＶ演算装置４６では、特徴点が移動体の一部となっている場合である。
【００６５】
静止座標系に対して移動するカメラ位置と姿勢はＣＶ演算によって求められるＣＶ値（X,Y,Z,θx,θy,θz）で規定され、移動座標系に対するカメラ位置と姿勢はＲＶ演算よって求められるＲＶ値（Xr,Yr,Zr,φx,φy,φz）で規定される。ここでカメラが共通（同一）であることから、静止座標系に対する移動座標系の位置と姿勢との関係は単純な演算で求められる。
さらに、静止座標系に対して移動する移動座標系が複数であっても同じであり、その時は任意の移動座標系から、共通のカメラの位置と姿勢を介して、他の任意の移動座標系の位置と姿勢が単純な演算で求められる。
【００６６】
ここで、本実施形態に係るＲＶ演算装置４６とそこで得られるＲＶ値は、その意味するところが重要であるため、以下この点について説明する。
ＲＶ演算装置４６では、ＲＶ演算のために使用する映像は必ずしもＣＶ映像でなくてもよく、映像のＣＶ値によりトラッキングを予想することが、絶対条件ではなくなる。これは、移動体を含む映像のＣＶ値と移動体のＲＶ値とは原理的に異なるためである。言い換えれば、移動する対象の中の移動する小領域のＲＶ値は、背景の静止座標系の中の映像のＣＶ値とは異なる。もし、ＲＶ値がＣＶ値に一致すればそれは移動体ではなく静止物体である。
【００６７】
そこで、小領域をより一般化して扱うことが有効である。即ち、小領域を一旦すべて移動する（移動座標系の）小領域と見なして（結果的に静止座標系の小領域であっても矛盾しない）、個別に特徴点を発生し、その特徴点をトラッキングして、小領域のＲＶ値をＲＶ演算装置４６で求めるものとする。
これは見方を変えれば、小領域単位でＲＶを求めることであり、小領域は同一のＲＶ値に属する特徴点の集合であることになる。これは、特徴点を介して小領域そのものをトラッキングしていることに等しいことになる。
【００６８】
ここで、本実施形態において小領域とフレーム内小領域とは異なるものであるが、両者を区別して記載することで説明に混乱が生じることもあり、また、両者は常に対応しているものであるので、以下の説明では両者を区別しないものとする。
そこで次に、本実施形態に係るＲＶ演算装置４６を小領域トラッキング装置として捉えると、映像中の複数の小領域（例えば１０個程度）のＲＶ値を同時に求めることは、従来のように複数の特徴点からなる独立した小面積の狭い範囲の小領域のＲＶ値としての意味を大きく越えて、対象物の一部としての小領域を、隣接フレームに亘ってトラッキングする対象としての特徴ある小領域として扱うことができることになる。そこで、トラッキングの対象となるこの特徴ある小領域を「特徴小領域」と定義する。
【００６９】
ここで、上記「特徴小領域」について、本実施形態における「複数の特徴点によってＣＶ演算をしてＣＶ値を求める」という説明に対応させて、それと同じ意味で「複数の「特徴小領域」によってＲＶ演算をして対象物のＲＶ値を求める」と考えることができる。
そして、さらに複数の「特徴小領域」のＲＶ値を同時に求めることで、静止座標系に対してのＣＶ値と、移動座標系おける「複数の小領域」のＲＶ値とが、それぞれ同時に求められる。即ち、同一のＲＶ値に属する複数の特徴小領域の集合となる。
この場合の演算上の長所としては、これら複数の特徴点小領域の各ＲＶ値は、その三次元座標の接続境界線を表す三変数は共通にしたまま連続していて、当該複数の特徴小領域の属する対象が剛体の場合には回転を表す三変数も同一であるとの仮定が成り立つので、誤差を最小化できることになる点である。ここで、回転を表す三変数のみ異なる場合は、当該対象物は剛体ではなく、複数の特徴小領域が柔軟な結合をしていることになる。
なお、上記以外の場合で、ＲＶ値座標と回転のそれぞれが異なる場合は、結果として、異なる座標系に属する特徴小領域であり、その異なる数だけのＲＶ値が求められることになる。
【００７０】
特徴小領域はもともと、移動体（移動座標系）に対して成される処理として想定されるものであり、移動、回転、拡大、縮小、形状変化等に強いものである。但し、移動速度を「０」とした静止座標系に対しても特に有効であることを以下に説明する。
即ち、特徴小領域を用いることにより、ＲＶ演算装置は、カメラの向きの変更、カメラ移動による対象（小領域）の回転、拡大、縮小等の形状変化、及び表示図法による変形等に対して、対応点を見失うことなく追従し、きわめて強いトラッキング特性を示すという優れた特徴を有するトラッキング装置とすることができる。
もし、静止座標系に限定すれば、ＲＶ演算装置はＣＶ映像を元画像としてトラッキング予想をして、ＲＶ演算をすることに意味があり、しかもＣＶ映像を元として処理をすることで、特徴点、及び特徴小領域の概略位置が推定できるので、演算効率がさらによくなる。
【００７１】
またさらに、原理的には、演算時間の増加を無視すれば、図６の最初の処理のＣＶ映像生成装置のＣＶ演算装置の代わりに、ＲＶ演算装置を用いて、ＣＶ映像の代わりとして、直接ＲＶ演算を行うことはもちろん可能であり、演算の精度も向上できる。
このように、本実施形態に係るＲＶ演算装置４６は、領域分割画像装置３により得られた小領域に対応するフレーム内小領域を、その中に生成した複数の特徴点を介して、小領域そのものを隣接する複数のフレームに亘ってトラッキングする小領域トラッキング装置として機能させることができる。
【００７２】
具体的には、ＲＶ演算装置４６は、フレーム内小領域特徴点三次元化装置４によって得られたフレーム内小領域の中に生成した複数の特徴点（移動体の一部）に対して、上述した静止座標系に対して定義されていたＣＶ演算ではなく、移動座標系に対して新たに定義したＲＶ演算を行う。ただし、数学的・物理的にはこの二つの演算は同等で、区別することはできない。すなわち、ＲＶ演算装置４６では、上述したＣＶ値を使わず、新たにＣＶ演算と同様の処理を行うＲＶ演算を行うものである。
ＲＶ演算とは、映像に映っている移動体対象物に固定された移動座標系に対して、さらに移動しているカメラ位置とカメラ姿勢を、移動座標系に対する三次元位置、三軸回転姿勢を示す六変数（Xr,Yr,Zr,φx,φy,φz）を定義することができる。すなわち、ＲＶ値を自動演算で求めることができる。
【００７３】
従って、上述したＣＶ値と同じように、ＲＶ値を用いて上述した領域分割画像の指定からポリゴン生成までの処理を行うことができる。
なお、本実施形態では、ＲＶ映像生成装置４７内のＲＶ演算装置４６は、移動体の一部としての小領域に関して演算を行うようになっており、これは図６のＣＶ映像生成装置２内のＣＶ演算装置２１と基本的に同じものであり、特徴点三次元化装置４２は、ＲＶ専用とはしていない。
これは、特徴点が静止座標系にあるか、移動座標系にあるかだけの違いであり、共用も可能だからである。
【００７４】
求められた小領域で、ＲＶ値を同じくする小領域は同一の移動体座標に属するとの仮定で、ＲＶ値を同じくする小領域を一体化させることで、移動する対象物のポリゴンを生成することができる。
ここで、以上のようなＲＶ値を動画像の各フレームと対応させたＲＶ映像を生成する装置としてＲＶ映像生成装置４７を定義することができるが、これはＣＶ映像生成装置２と同等であるので、本実施形態では区別しないものとする。また、ＲＶ演算装置４６は、機能・処理の面ではＣＶ演算装置２１と全く同じものである。
【００７５】
さらに、ＲＶ映像を求める場合には、同時に移動体の移動座標系における特徴点も同時に三次元化される。
そこで、本実施形態では、ＲＶ演算と同時に移動体の特徴点三次元座標を求める特徴点三次元化装置４２を備えることができる。
このように、三次元地図として、静止座標のみならず、リアルタイムで移動体を扱うためには、このような移動体に対応する三次元地図が必要である。
ここまでが、移動体対応の三次元地図自動生成装置１００ａに関する説明である。
【００７６】
以上のような構成からなる本実施形態に係る三次元地図自動生成装置１００について、更に具体的に説明する。
本発明に係る三次元地図の自動生成技術の特徴は、ＣＶ映像を用いて、既知の技術である領域分割技術と組み合わせた分割領域三次元化によって取得された小領域に対して、複数の特徴点を発生させ、ＣＶ映像のもつＣＶ値によって三次元化することにある。
動画映像に対して、特徴点を求め、トラッキングし、ＣＶ演算を行ってＣＶ映像を生成する流れは、上記概略を示した通りであり（図２、図３参照）、また後に詳述する通りである（図７〜図１９参照）。
【００７７】
ここでは、ＣＶ映像を使って、領域分割画像を生成し、その領域分割画像から、小領域を選択して三次元化する処理が本発明の核となるので、以下に詳細に述べる。
図４に示すように、ＣＶ映像１０１の中で、自動的に指定されたフレーム１０２を選択し、このフレーム画像から領域分割画像１（１０３）を生成する。なお、画像から領域分割化像を生成すること自体は、上記の通り公知の技術により実現される。
【００７８】
ここでの特徴は、ＣＶ値が既知の「ＣＶ映像」の中の一フレーム画像１０２を領域分割する点である。
領域分割は、図４の領域分割画像１（１０３）だけでなく、適切に距離をとったフレーム１０４を指定して選択し、領域分割画像２（１０５）でも生成する。同様に、領域分割画像３、４，５、・・・・・と継続的に領域分割画像を生成し、同様の処理が行われる。
領域分割画像は最大ＣＶ映像のフレーム数まで取ることができる。領域分割画像のサンプリング数を増加させると、それだけ処理量が増加するので、作業効率が落ちることになるので、適切な領域分割のサンプリング数を選択することが望ましい。
【００７９】
また、カメラ台数が増加する欠点はあるが、通常のＣＶ映像取得のための全周カメラ以外に、領域分割画像専用のカメラをも同時に設置して、そのカメラ画角は全周ではなく、限定された画角であっても、高解像度の専用カメラを設置することで高解像度の限定画角のＣＶ映像を別に生成し、そこから領域分割画像を取得することもできる。このようにすると、小領域の精度が向上し、結果としてＲＶ値の精度が向上するので好ましい。
なお、このとき、全周カメラによるＣＶ映像も限定画角カメラによる高解像度ＣＶ映像も、どちらも同時に生成するＣＶ映像なので、それぞれは単に隣のフレームと考えることができるので、それらのＣＶ値は一連のＣＶ値であり、一方の小領域は常に他方の小領域に対応がついているというところが重要である。
【００８０】
各領域画像で行われる処理について、さらに図５を参照しつつ詳細に説明する。
図５におけるＣＶ映像内の一フレーム１１０は、図４における「指定入れたフレーム１０２」、「次に指定されたフレーム１０４」に相当するものとする。
ＣＶ映像の中の指定された一フレーム１１０を複製して取り出して、そこから領域分割画像１１１を生成する。この処理により、前記一フレーム１１０は複数の領域に領域化され、複数の領域に分割され、領域分割画像１１１となる。
なお、この最初の処理段階で画像の領域化は不完全であってもよいものとする。最終的には、領域の形状を整形したり、他の指定フレームから生成される領域分割画像と共通する対象物を比較することで、領域の形状を修正し、補正することで、より適切な領域化がなされる。
【００８１】
次に、領域分割画像１１１を構成する複数の領域の中の単位となる一領域を小領域２０１として定義する。このとき同時に、領域分割画像内１１１に対応する元画像となるＣＶ映像の中の一フレーム１１２に、小領域２０１に対応するフレーム内小領域２０２を定義することができる。
このフレーム内小領域２０２内に、複数の特徴点２０３を発生させる。この時点での特徴点群は、いずれもフレーム内にあるから、未だ二次元座標しか持たないことは明確である。
そこで次に、この特徴点群をそれぞれＣＶ映像の連続するフレームとして隣接する複数のフレームに亘ってトラッキングして、そのトラッキングデータ２０４から、ＣＶ演算によりそれぞれの特徴点の三次元座標を求める。ここで、特徴点群のトラッキングデータからＣＶ演算して、三次元特徴点を求める手法としては、再度後述するＣＶ演算についての説明で詳述する（図７〜図１９参照）
【００８２】
次に、取得された三次元特徴点はそのままで、元々フレーム１１４と対応がついている領域分割画像１１５に複製して移転することが可能である。フレーム内小領域で三次元化された特徴点は領域分割画像の小領域２０６に複製して移転され、三次元特徴点２０７となる。
三次元特徴点群から、最も誤差が少なく、三次元特徴点をその平面近くに分布させる平面を求めることができる。その平面の法線を図５に示す線分２０５とする。
なお、三次元特徴点群は必ず誤差を含むから、完全に平面に乗ることはない。最も誤差が少なく平面を推定するには、最小自乗法やRANSAC手法がある。
【００８３】
このようにして、両領域の三次元平面が推定されたことになる。
分割画像内の他の小領域を同様に次々処理していくことで、すべての小領域の三次元平面が推定される。小領域をそのままポリゴンとしても良いが、後の処理で小領域の分割や統合により、より適切なポリゴンを生成することが望ましい。
ＣＶ映像の一フレームから領域分割画像を生成して、小領域を指定し、それをＣＶ映像に戻して、特徴点発生により三次元化して、それを小領域に戻すという流れの中で、その三次元座標の精度はＣＶ映像のＣＶ値の精度に依存していることになる。
【００８４】
そして、このＣＶ映像のＣＶ値は、映像から直接求めることができることから、撮影の規模が、例えば大都市程まで大きくなっても十分に対応することができる。
従って、前もってＣＶ映像のＣＶ値を精度良く求めておけば、例えば大規模な都市モデルのような処理においても、どこから生成しても、分割して生成しても、座標として矛盾のない３ＤＣＧを生成することができる。
また、ＧＰＳデータ等の機械センサーによって取得された位置や姿勢のデータは、単独で取得した位置座標を後に精度良く統合することは不可能であるが、本実施形態に係るＣＶ映像は「映像」からデータを生成するので、データの統合がいつでも可能となる。この点も本発明の重要なポイントとなる。
【００８５】
以下、図１、図４、図５を参照して、上述した本実施形態に係る三次元地図自動生成装置１００について、より具体的な実施例を示しつつ説明する。
まず、動画像取得装置１として、車載した全周カメラ、例えばPGR社製のLadybug３を積載する（図８、図９参照）。後に有効なＣＶ演算をするためには、動画取得装置１を構成するカメラにより１５Hz程度で撮影することが望ましい。
車両の位置を示すＧＰＳは基本的に必要ないが、この後の処理のために、概略位置を記しておく必要があるため、安価なＧＰＳを使用して、撮影地点の概略位置を取得しておくことは適切である。
撮影した動画像はハードディスク等の所定の記憶媒体に記録しておくことになる。
【００８６】
全周カメラは、原理的には一台でよいが、精度向上を求める場合には複数台とすることも可能であり、ここでは資料の屋根に上下に設置した二台の全周カメラで全方向を撮影し（Dual方式撮影装置）、二台のカメラの同期を取るようにする。
なお、ここでは二台のカメラは同期をとっているが、ＣＶ演算においては原理的に同期が必要条件ではない。ＣＶ演算においては、同期が取れていても、取れていなくてもよい。ここでは、たまたまカメラ移動による時間軸方向にカメラが配列してある状況があれば良いのであり、その中にカメラ移動無しに異なる配列があっても、それは区別する必要はない。そして、同期方式の場合は、それがたまたま同時刻の映像が異なる場所にカメラが存在していると考えればよい。このようなフレキシビリティーがＣＶ演算に基づく本発明の最大の特徴といえる。
【００８７】
なお、二台のカメラで同期を取ることで、ステレオ方式と間違いを受けやすいが、これはいわゆるステレオではない。カメラの台数のことではなく、時間軸上の配列される等価的なカメラ列が重要なのであって、一台のカメラが作る時間軸上のカメラ列であろうと、二台のカメラが作る時間軸上のカメラ列であろうと、ＣＶ演算にとっては本質的に同じである。
更に言えば、それが物理的に一台であろうと複数台（例えば五台）であろうと、物理的なカメラ個数には関係なく、時間軸上に配列される等価的な各カメラが、どのように周囲の世界を移し込んでいるかのみが情報であり、その情報から、各カメラ位置と姿勢をＣＶ値として演算して解を求めることになる。
【００８８】
そして、カメラ二台による方式（Dual方式）では、ある瞬間を見れば、ステレオ方式では二台のカメラによる一対の組み合わせが演算に係わるのに比較し、この方式によれば、二台のカメラの近傍の複数のカメラの配列の組み合わせ、すなわちここでの例では、移動する二台のカメラの映像の複数フレーム分として、実質約二十数台分のカメラの配列による数百対（２０×２０）の組み合わせ映像が、その地点の一点のＣＶ値の演算に係わることになるので、精度が極めて高いことになる。
参考例として、カメラ一台で実施した場合では、時間軸上にある前後約５０台のカメラ映像がＣＶ演算に係わることになる。
【００８９】
係わるカメラ台数とその映像が多ければ多いほど、ＣＶ演算の精度が向上し、そのＣＶ値を用いた計測の精度が向上することになる。
特に本発明の三次元地図自動生成装置では、あらゆる方向に対する計測精度の向上が望まれるので、この実施例ではカメラ二台によるDual方式を採用している。つまり、二台のカメラを垂直方向に設置したことで、有効な複数のエビポーラ線が生まれることになるので、全方向に対する計測精度が向上したことがこのDual方式の長所となる。
【００９０】
ちなみに、カメラ一台の場合には、有効なエビポーラ線が一本であり、進行方向に対する計測精度は十分であったが、前方や水平線に対する計測精度に難があった。
カメラ一台でも二台でも、特にＣＶ演算の手法においては原理的に変わるものではないので、演算された結果についても、カメラ一台でのＣＶ値と同様に扱うことができる。
従って、以下に示す実施例では、カメラ台数に関わらず、カメラ一台の場合と同様に、単にＣＶ値として扱うことができる。
【００９１】
ＣＶ映像生成装置２によって、動画像取得装置１で撮影された全周映像から、ＣＶ映像が生成される。
毎秒１５Ｈｚで記録された全周映像は、ハードディスク等に記録されていったん保存される。
ハードディスクから読み出される全周映像から、ＣＶ映像が生成される。ＣＶ映像の生成の詳細は後述する通りである（図７〜図１９参照）。
また、その数学的意味は上述した通りである（図２、図３参照）。
ＣＶ映像は、本発明に係る三次元地図自動生成装置１００の根幹技術であり、このＣＶ映像を取得することで、後の処理がすべて実行されることになる。換言すれば、ＣＶ映像がなければ本発明に係る三次元地図自動生成装置は実現できないことを意味する。
【００９２】
また、ＣＶ映像を取得するためには、全周映像が絶対条件ではないが、全周ではない通常の画像よりも全周映像の方が、処理が簡単で、精度が高いという長所がある。
全周映像では、全方向に特徴点を取得できるので、誤算が分散され、打ち消し合い、演算に都合がよい。
通常カメラによる映像でのＣＶ演算では、焦点距離と光軸というデリケートな要素を扱うことになるが、全周映像では焦点距離と光軸が存在しないので、演算時の未知数の数を少なくすることができることも演算精度に貢献している。
【００９３】
次に、領域分割装置３では、１５ＨｚのＣＶ映像からサンプリングするようにして、一部のフレームをある間隔で指定し、そのフレームを自動的に取り出す。
取り出されたフレームは領域分割装置３の中の領域生成装置３１で領域分割処理される。ここでの領域分割処理は既知の技術による。
ここで、分割時のパラメータを調整して、このフレームを適切な複数の小領域に分割し、小領域指定装置３２で、一つの小領域を指定する。この小領域を最小単位として、後にポリゴンを生成していく。
【００９４】
取り出されたフレームと領域分割画像は完全に対応しており、その後の処理で特徴点が発生されるが、その位置関係は両者で完全に一致する。
領域分割された領域分割画像の最小単位が小領域であり、この小領域はフレーム内のフレーム内小領域に座標は完全に一致している。
なお、この時点では画像が二次元なので、二次元として完全に一致している。ただし、両者は三次元空間に存在する小領域であり、本来三次元としても完全に一致していることは自明である。
【００９５】
次に、フレーム内小領域特徴点三次元化装置４では、小領域とフレーム内小領域を対応させながら処理を進める。
図１に装置構成を示し、その処理内容を図４に示しつつ、フレーム内小領域特徴点三次元化装置４の詳細について以下に説明する。
まず、フレーム内小領域特徴点発生装置４１では、フレーム内小領域に複数の特徴点を発生させる。原理的にはフレーム内小領域内に三個の特徴点があり、それを三次元化できれば、平面を決定できるが、精度を考慮して、例えば２０個程度の特徴点があることが望ましい。
【００９６】
ここで、限られた範囲に２０個以上の多くの特徴点を発生させ、それをトラッキングするには、領域境界付近に集中する特徴点を効率よく抽出する必要がある。
そのために、フレーム内小領域特徴点三次元化装置４では、小領域境界特徴点発生装置４３を備えており、小領域の境界付近に集中的に特徴点を発生させるようにしてある。
特に、本実施例では、ＣＶ映像時に多数の特徴点からＣＶ値を演算するようになっているので、その多数の特徴点を有効利用することができる。
【００９７】
なお、ＣＶ演算後には、ＣＶ演算に用いられた特徴点、トラッキングデータ、及びそれから求められた三次元特徴点は破棄することができるが、ここではそれらを直ちに破棄することなく有効利用している。
すなわち、フレーム内小領域特徴点三次元化装置４は、ポイントクラウド生成装置４５を備えており、このポイントクラウド生成装置４５は、ＣＶ演算時において、より積極的に三次元特徴点を生成し、ポイントクラウドを生成し、後の処理に積極的に役立てようとするものである。
【００９８】
さらに、カメラ二台によるDual方式においては、ＣＶ演算時には一部のフレーム内小領域の水平ラインについては既に特徴点を抽出しており、しかもトラッキング処理により三次元座標も求められているので、それをそのまま小領域内の三次元点として用いることができる。
なお、これだけで十分とは言えないので、以下の方法により、さらにフレーム内特徴点を追加して、面推定に必要な数の三次元特徴点を取得することが好ましい。
【００９９】
図４では、ＣＶ映像のフレームの進行方向を示している。
その時間の流れの中の１フレーム１０２を指定して取り出し、領域分割画像１（１０３）とする。
同様に、次に指定されたフレーム１０４から領域分割画像２（１０５）を選択する。
そして、各領域分割画像中において複数の小領域を生成し、その中の一つを小領域として、複数の小領域を生成する。そして、その中の一つの小領域を取り出し、対応するフレーム内小領域内で複数の特徴点を発生させる。
複数の特徴点について、フレーム２（１０４）のＣＶ値を用いて、トラッキング予測を行い、トラッキングにより三次元座標を取得する。この三次元座標は小領域に移転することが可能である。
トラッキングデータから三次元座標を求める演算は、ＣＶ映像を生成するＣＶ演算と基本的に同じである（図７〜図１９参照）。
【０１００】
次に、複数領域ポリゴン化装置５においては、先ず対象物と背景の関係を大まかに示しているポイントクラウドの情報が有益である。
ポイントクラウドとは、三次元の特徴点を分布させたものである。
ポイントクラウド生成装置４５は、ＣＶ演算時の三次元特徴点の分布であるが、フレーム内小領域トラッキング時に生成した三次元特徴点を追加させても良い。
複数領域ポリゴン化装置５の全体構成推定装置５４は、ポイントクラウドから自動判断して、全体構成を推定する。
【０１０１】
一般に対象物や背景は、解略の大きさや方向は予想がついていることが多いので、ある程度予想して概略のモデル化が可能であることから、例えば、道路面、交差点、ビル面、街路樹面等の大枠は、ポイントクラウドから分離可能である。
道路走行という前提に立って、道路周辺を予想し、全体構成を予想することは、後の処理に大いに貢献する。
【０１０２】
ここでは、三次元特徴点によって形成されるポイントクラウドの分布状況から、道路面の概略位置を指定し、ビル面の概略位置を指定し、ビル面と街路樹面とを歩道上で前後に分離し、ビル面と街路樹の存在範囲を指定し、交差点概略位置を指定し、それらの大枠とその範囲を自動推定している。
この処理により、後の各種ポリゴン生成は上記の指定された範囲で求めることになり、効率的になる。
【０１０３】
まず、複数領域ポリゴン化装置５の各領域面推定装置５１により、フレーム内小領域で求められた複数の特徴点の三次元座標から、平面推定が行われる。
ＣＶ演算時の三次元特徴点（図１の符号４４で示す矢印）のみで、小領域内に十分な数の三次元特徴点が取得できれば、それを用いて面の推定ができるが、多くの場合これだけでは十分ではなく、フレーム内小領域特徴点発生装置による特徴点の追加が必要である。なお、ここでは、小領域は必ずしも平面ではないが、微少領域は平面であると仮定しても、大きな矛盾はないとの考え方で、平面推定をしている。
平面推定には上述したRANSAC手法等を用いて、誤差を含む複数三次元特徴点から、都合の良い特徴点のみを自動選択して平面を推定することで得られる。
【０１０４】
さらに、複数領域ポリゴン化装置５では、得られた小領域の面の推定が精度良く求められているか、誤差が大きいか否か等の判定として、トラッキング差分補正装置５３を用意してある。
推定された面の推定が済めば、その推定面にＣＶ映像から、対応位置のテクスチャー取り込むことができることは明らかである。
そこで、そのフレーム内小領域の三次元座標からＣＶ映像内での面の移動は計算で求められるから、ＣＶ映像のフレームを進めながら、各フレームでの小領域のテクスチャーの一致度を例えば相関関数で評価すればよい。
面推定が正しければ、相関関数はほぼ１００％近くで一致することになる。もし、評価が低ければ、面推定が間違っていることになるので、再分割したり、三次元特徴点を増加させるなどして、再推定することになる。
【０１０５】
そこで、次に、面の統合分離装置５５では、フレーム内小領域に関して、上記の相関関数での評価ではなく、マッチング手法でその一致度合いで評価すれば、その評価値から面推定が正しいところと間違っているところを分離することができる。
面推定が間違っている部分を新たな小領域として分離して、他の小領域と同様な処理を繰り返すことで、同様に面推定を行うことができる。
【０１０６】
また、同一平面にある二つの小領域は二つの小領域のまま保存し、ポリゴン化されることで矛盾はないが、統合することがデータ量を軽くして保持することができ、それは合理的であるので好ましい。
なお、本実施例では、データ量の増加を抑えるために、一つのポリゴンに一色を対応させており、そのポリゴンを構成する小領域の平均の色を取得することで実現している。
小領域の分離と統合が終わり、小領域が決定されれば、それがそのまま最終ポリゴンとなり、ポリゴン生成処理が終了する。
連続処理装置６が、ここまでの処理の流れを連続的に繰り返し処理するようにして、フレームを進めながら処理を行うことで、広い領域の三次元地図を自動生成することができる。
【０１０７】
最後に、テクスチャー取得装置７では、ポリゴン化された三次元地図に、対応するテクスチャーを貼り付ける。
小領域はフレーム内小領域に対応しているので、いつでもＣＶ映像のテクスチャーを貼り付けることが可能であることは言うまでもない。
また、ＣＶ値を持つことから、視点を変えたフレームからのテクスチャーを貼り付けることも可能である。
さらに、更新のために、新たに撮影した映像をＣＶ映像化して、新旧のＣＶ映像のＣＶ値を合わせることで、新たなＣＶ映像の対応するポリゴンのテクスチャーを更新することも自由である。
【０１０８】
以上説明したように、本実施形態に係る三次元地図自動生成装置１００によれば、カメラで得られる動画又は連続静止画の映像に基づいて、対象物、及びその背景を含めて、その三次元形状を求め、必要であればそのテクスチャーを自動的に取得して、三次元地図を自動的に生成することができる。
特に、本発明では、高価な機器や膨大な手間と費用などを必要とすることなく、完全自動により、背景を含めた対象物との座標を矛盾無く整合して、簡易かつ高精度に、三次元形状を求めて、大規模に三次元地図を生成することができる。
【０１０９】
また、本実施形態に係る三次元地図自動生成装置１００では、三次元地図が現実の座標及び緯度経度高度を示すＣＶ値を持つことにより、三次元地図に対して三次元データを持つＣＧ（コンピュータグラフィックス）を容易かつ高精度に、矛盾等が生じることなく結合・整合さえることが可能となる。
一般に個々にＣＧを生成して、それを結合しても、ＣＧは三次元座標と三次元姿勢を持ち、それを矛盾無く整合しようとしても、現実問題としてなかなか整合はとれない。整合をとるためにも手動で、調整する必要があった。それ故これまでは、例えば大規模な都市構造をＣＧ化することは困難であった。
【０１１０】
しかしながら、上述したような本実施形態に係る三次元地図自動生成装置１００によれば、ＣＶ値は、現実の座標、緯度経度高度を持たせることができるので、途中の三次元座標は、緯度経度高度で処理することが可能となる。当然、最終的なポリゴンにおいても緯度経度高度を持つことになる。
従って、都市等をそのまま三次元化する場合に、個々に地域別に三次元化しても、その整合性は表示に高いものとなり、当然精度が高いＣＧが得られることになる。
【０１１１】
なお、座標の精度は、一番最初の処理において、ＣＶ映像生成時にＣＶ演算した結果に、絶対座標を正しく取得しておくことが重要であるが、処理の途中でのＣＶ値の補正も自由である。
さらに、後で得られた最も精度の高い実測データをＣＶ値に反映させることも可能であり、画像の一部にでも精度の高い実測データを持つ地点が有れば、それをＣＶ値の精度に反映できること等は、ＣＶ演算の優れた長所である。
【０１１２】
また、従来の三次元地図技術では、地図等の更新のために膨大な費用が必要であったが、ＣＶ映像を用いたＣＶ技術を利用すれば、例えば大都市の一部からＣＶ映像化し、一部からポリゴン化することで、最終的に統合することが可能となる。つまり、ＣＶ値さえ全体で統合されていれば、どこから作成しても全く矛盾は生じないことになる。
さらに、一部の更新においても同様であり、更新が必要な地域のＣＶ映像を既知のＣＶ値に統合しておくことで、後は自動的に変更分だけが更新される装置とすることも可能となる。
【０１１３】
このように、本実施形態に係る三次元地図自動生成装置１００によれば、三次元形状、及び背景との座標関係に矛盾が無いように、高精度の三次元地図を生成でき、また、人間が見るための地図としても十分な品質のものが得られる。
従って、本発明は、自動車、重機、航空機等の移動体の三次元位置を評定したり、移動体の進行方向や現在状況等をガイドするための三次元地図と、その三次元地図自動生成装置として好適に利用することができる。
【０１１４】
［ＣＶ演算］
次に、以上のような本発明の三次元地図自動生成装置における三次元地図の生成処理の前提となるＣＶ演算について図７〜図１９を参照しつつ説明する。
ＣＶ演算とはＣＶ値を求める方法の一つであり、ＣＶ演算により求められた結果をＣＶ値，ＣＶデータと呼ぶ。ＣＶという表記は、カメラベクトル：CameraVectorの略記であり、カメラベクトル（ＣＶ）とは計測等のために映像を取得するビデオカメラ等のカメラの三次元位置と３軸回転姿勢を示す値である。
ＣＶ演算は、動画像（ビデオ映像）を取得し、その映像内の特徴点を検出し、それを隣接する複数のフレームに追跡し、カメラ位置と特徴点の追跡軌跡とが作る三角形を画像内に数多く生成し、その三角形を解析することで、カメラの三次元位置とカメラの３軸回転姿勢を求めるものである。
【０１１５】
ＣＶ演算では、ＣＶ値を求める過程で、同時に映像内の特徴点（基準点）についても三次元座標が同時に求まることが重要な特性である。
また、動画像から演算で求められるＣＶ値は、動画像の各フレームに対応して、三次元のカメラ位置と三次元のカメラ姿勢とが同時に求まる。しかも、原理的には一台のカメラで、映像と対応してＣＶ値が求められる特性は、ＣＶ演算でしか実現し得ない、優れた特徴である。
但し、ＣＶ値は、例えば、他の方法による計測手段（ＧＰＳとジャイロ、又はＩＭＵ等）より求めることもできる。従って、ＣＶ値の取得はＣＶ演算による場合には限られない。
なお、ＧＰＳとジャイロ、又はＩＭＵ等によりＣＶ値を取得する場合には、動画像の各フレームと、その三次元的カメラ位置と三次元的カメラ姿勢とを同時に取得するためには画像フレームと計測サンプリング時刻を高精度で、かつ完全に同期させる必要がある。
【０１１６】
動画像から演算で求められるＣＶデータは、加工しない段階では相対値であるが、短区間であれば高精度で三次元位置情報と３軸回転の角度情報を取得できる。
また、ＣＶデータを画像から取得する場合は、取得されたデータは相対値であり、絶対値に変換するには既知の地点でのキャリブレーションが必要であるが、ＣＶ値と同時に取得される特徴点三次元位置座標と姿勢により、又は新たに画像内に指定して取得した特徴点により、画像内の任意の対象物との位置関係を計測することができるという、他の方法では実現困難な優れた特性を備える。
また、画像に対応したＣＶ値が求まるので、画像との相性が良く、画像から取得したＣＶ値である限り、その画像内では矛盾が無いので、画像以外から求めるＣＶ値と比較して、画像から直接にカメラ位置とその３軸回転姿勢を求めることができるＣＶ演算は画像内計測や画像内測量に好適となる。
そして、本実施形態では、このＣＶ演算により得られたＣＶ値データに基づいて、映像のみに基づいて三次元地図を自動生成するものである。
【０１１７】
［ＣＶ演算部］
ＣＶ演算は、上述した三次元地図自動生成装置１００のＣＶ映像生成装置２（ＣＶ演算装置２１）として機能するもので（図１、図６参照）、図７に示すＣＶ演算部２で行われる。
ＣＶ演算部２は、図７に示すように、上述した図１、図６に示した三次元地図自動生成装置１００の動画像取得装置１を構成する全周ビデオ映像部１から入力されるビデオ映像について、所定のＣＶ演算処理を行うことでＣＶ値を求めるようになっている。
【０１１８】
具体的には、ＣＶ演算部２は、図７に示すように、特徴点抽出部２-１と、特徴点対応処理部２-２と、カメラベクトル演算部２-３と、誤差最小化部２-４と、三次元情報追跡部２-５と、高精度カメラベクトル演算部２-６とを備えている。
そして、このＣＶ演算部２の出力が、三次元地図自動生成装置１００にフィードバックされて上述した三次元地図の自動生成処理が行われることになる（図１、図６参照）。
【０１１９】
まず、ＣＶ演算に使用する映像としては、原理的にはどのような映像でもよいが、画角の限られた映像では視点方向を移動した場合に映像がとぎれてしまうので、実用的には全周映像（図８〜図１０参照）か、広角映像を全周映像の一部として扱うことが望ましい。なお、動画映像は連続する静止画と同様であり、複数の静止画として扱うことができる。
また、映像は、一般には予め記録した動画映像を使うことになるが、自動車等の移動体の移動に合わせてリアルタイムに取り込んだ映像を使用することも勿論可能である。
【０１２０】
そこで、本実施形態では、ＣＶ演算に使用する映像として、車輌等の移動体の３６０度の全周囲を撮影した全周映像（図８〜図１０参照）か、又は全周映像に近い広角映像を用いて、その全周映像を視点方向に平面展開することにより、全周映像の一部として扱うことができる。
全周映像の平面展開とは、全周映像を、通常の画像として遠近法的に表現するものである。ここで、「遠近法」と呼称するのは、全周画像のそのものはメルカトール図法や球面投影図法のように、遠近法とは異なる方法で表示されているので（図１０参照）、これを例えば等距離図法のように平面展開表示することで、通常の遠近法映像に変換表示できるからである。
【０１２１】
全周ビデオ映像部１において全周映像を生成するには、まず、図８及び図９に示すように、全周ビデオカメラ１-１を使用して、ＣＶ値データを取得する目的で、走行車輌等の移動体１-１ａに固定された全周ビデオカメラ１-１で、移動体１-１ａの移動とともに移動体周辺を撮影する。
なお、移動体１-１ａには、その位置座標を取得する目的で、例えば、絶対座標を取得するＧＰＳ機器単独やＩＭＵ機器を付加したもの等により構成した位置計測機器等を備えることができる。
また、移動体１-１ａに搭載される全周ビデオカメラ１-１としては、広範囲映像を撮影，取得するカメラであればどのような構成であってもよく、例えば、広角レンズや魚眼レンズ付きカメラ、移動カメラ、固定カメラ、複数のカメラを固定したカメラ、３６０度周囲に回転可能なカメラ等がある。本実施形態では、図８及び図９に示すように、車輌に複数のカメラが一体的に固定され、移動体１-１ａの移動に伴って広範囲映像を撮影する全周ビデオカメラ１-１を使用している。
【０１２２】
そして、以上のような全周ビデオカメラ１-１によれば、図９に示すように、移動体１-１ａの天井部に設置されることで、カメラの３６０度全周囲の映像を複数のカメラで同時に撮影することができ、移動体１-１ａが移動することで、広範囲映像を動画データとして取得できる。
ここで、全周ビデオカメラ１-１は、カメラの全周映像を直接取得できるビデオカメラであるが、カメラの全周囲の半分以上を映像として取得できれば全周映像として使用できる。
また、画角が制限された通常のカメラの場合でも、ＣＶ演算の精度としては低下するが、全周映像の一部分として取り扱うことが可能である。
【０１２３】
なお、全周ビデオカメラ１-１で撮影された広範囲映像は、一枚の画像として、撮影時の画角に一致する仮想球面に貼り付けることができる。
仮想球面に貼り付けられた球面画像データは、仮想球面に貼り付けた状態の球面画像（３６０度画像）データとして保存・出力される。仮想球面は、広範囲映像を取得するカメラ部を中心点とした任意の球面状に設定することができる。
図１０（ａ）は球面画像が貼り付けられる仮想球面の外観イメージであり、同図（ｂ）は仮想球面に貼り付けられた球面画像の一例である。また、同図（ｃ）は、（ｂ）の球面画像をメルカトール図法に従って平面展開した画像例を示す。
【０１２４】
そして、以上のように生成・取得された全周ビデオ映像が、ＣＶ演算部２に入力されてＣＶ値データが求められる（図７参照）。
ＣＶ演算部２では、まず、特徴点抽出部２-１が、全周ビデオ映像部１の全周ビデオカメラ１-１で撮影されて一時記録された動画像データの中から、十分な数の特徴点（基準点）を自動抽出する。
特徴点対応処理部２-２は、自動抽出された特徴点を、各フレーム間で各フレーム画像内において自動的に追跡することで、その対応関係を自動的に求める。
カメラベクトル演算部２-３は、対応関係が求められた特徴点の三次元位置座標から各フレーム画像に対応したカメラベクトルを演算で自動的に求める。
誤差最小化部２-４は、複数のカメラ位置の重複演算により、各カメラベクトルの解の分布が最小になるように統計処理し、誤差の最小化処理を施したカメラ位置方向を自動的に決定する。
【０１２５】
三次元情報追跡部２-５は、カメラベクトル演算部２-３で得られたカメラベクトルを概略のカメラベクトルと位置づけ、その後のプロセスで順次画像の一部として得られる三次元情報に基づいて、複数のフレーム画像に含まれる部分的三次元情報を隣接するフレームの画像に沿って自動追跡を行う。ここで、三次元情報（三次元形状）とは、主に特徴点の三次元分布情報であり、すなわち、三次元の点の集まりであり、この三次元の点の集まりが三次元形状を構成する。
高精度カメラベクトル演算部２-６は、三次元情報追跡部２-５で得られた追跡データに基づいて、カメラベクトル演算部２-３で得られるカメラベクトルより、さらに高精度なカメラベクトルを生成，出力する。
そして、以上のようにして得られたカメラベクトルが、後述する三次元機械地図生成装置２００に入力され、ＣＶタグの生成や貼り付け処理に利用されることになる。
【０１２６】
複数の画像（動画又は連続静止画）の特徴点からカメラベクトルを検出するにはいくつかの方法があるが、図７に示す本実施形態のＣＶ演算部２では、画像内に十分に多くの数の特徴点を自動抽出し、それを自動追跡することで、三角測量幾何学、及びエピポーラ幾何学により、カメラの三次元ベクトル及び３軸回転ベクトルを求めるようにしてある。
特徴点を充分に多くとることにより、カメラベクトル情報が重複することで、三地点の座標で構成される単位の三角形を、その十倍以上の多くの特徴点から求めることになり、重複する情報から誤差を最小化させて、より精度の高いカメラベクトルを求めることができる。
【０１２７】
カメラベクトルとは、移動するカメラの持つ六個の自由度のベクトルである。
一般に、静止した三次元物体は、位置座標（Ｘ，Ｙ，Ｚ）と、それぞれの座標軸の回転角（Φｘ，Φｙ，Φｚ）の六個の自由度を持つ。従って、カメラベクトルは、カメラの位置座標（Ｘ，Ｙ，Ｚ）とそれぞれの座標軸の回転角（Φｘ，Φｙ，Φｚ）の六個の自由度のベクトルをいう。なお、カメラが移動する場合は、自由度に移動方向も入るが、これは上記の六個の自由度から微分して導き出すことができる。
このように、本実施形態のカメラベクトルの検出とは、カメラは各フレーム毎に六個の自由度の値をとり、各フレーム毎に異なる六個の自由度を決定することである。
【０１２８】
以下、ＣＶ演算部２における具体的なカメラベクトルの検出方法について、図１１以下を参照しつつ説明する。
まず、上述した全周カメラ映像部１０の全周ビデオカメラ１-１で取得された画像データは、間接に又は直接に、ＣＶ演算部２の特徴点抽出部２-１に入力され、特徴点抽出部２-１で、適切にサンプリングされたフレーム画像中に、特徴点となるべき点又は小領域画像が自動抽出され、特徴点対応処理部２-２で、複数のフレーム画像間で特徴点の対応関係が自動的に求められる。
具体的には、カメラベクトルの検出の基準となる、十分に必要な数以上の特徴点を求める。画像間の特徴点とその対応関係の一例を、図１１〜図１３に示す。図中「＋」が自動抽出された特徴点であり、複数のフレーム画像間で対応関係が自動追跡される（図１３に示す対応点１〜４参照）。
ここで、特徴点の抽出は、図１４に示すように、各画像中に充分に多くの特徴点を指定，抽出することが望ましく（図１４の○印参照）、例えば、１００点程度の特徴点を抽出する。
【０１２９】
続いて、カメラベクトル演算部２-３で、抽出された特徴点の三次元座標が演算により求められ、その三次元座標に基づいてカメラベクトルが演算により求められる。具体的には、カメラベクトル演算部２-３は、連続する各フレーム間に存在する、十分な数の特徴の位置と、移動するカメラ間の位置ベクトル、カメラの３軸回転ベクトル、各カメラ位置と特徴点をそれぞれ結んだベクトル等、各種三次元ベクトルの相対値を演算により連続的に算出する。
本実施形態では、例えば、３６０度全周画像のエピポーラ幾何からエピポーラ方程式を解くことによりカメラ運動（カメラ位置とカメラ回転）を計算するようになっている。また、これを三角測量として説明すれば、方位と俯角仰角を測量する機器を車載して、対象となる複数の測量地点を、移動する測量機器により同一対象物を計測して取得したデータから、各対象地点の座標と測量機器の移動の軌跡を求める場合と同じである。
【０１３０】
図１３に示す画像１，２は、３６０度全周画像をメルカトール展開した画像であり、緯度φ、軽度θとすると、画像１上の点は（θ１，φ１）、画像２上の点は（θ２，φ２）となる。そして、それぞれのカメラでの空間座標は、ｚ１＝（ｃｏｓφ１ｃｏｓθ１，ｃｏｓφ１ｓｉｎθ１，ｓｉｎφ１）、ｚ２＝（ｃｏｓφ２ｃｏｓθ２，ｃｏｓφ２ｓｉｎθ２，ｓｉｎφ２）である。カメラの移動ベクトルをｔ、カメラの回転行列をＲ、とすると、ｚ１T［ｔ］×Ｒｚ２＝０がエピポーラ方程式である。
十分な数の特徴点を与えることにより、線形代数演算により最小自乗法による解としてｔ及びＲを計算することができる。この演算を対応する複数フレームに適用し演算する。
【０１３１】
ここで、カメラベクトルの演算に利用する画像としては、３６０度全周画像を用いることが好ましい。
カメラベクトル演算に用いる画像としては、原理的にはどのような画像でも良いが、全周映像は対象物の方向がそのまま緯度経度で表現されていることから、きわめて有利である。図１３に示す３６０度全周画像のような広角レンズによる画像の方が特徴点を数多く選択し、複数フレームに渡って追跡し易くなる。また、狭角レンズによる映像あっても、同一対象物の周りを移動しながら様々な方向から撮影する場合には特徴点が視界から逃げないので有効である。
そこで、本実施形態では、ＣＶ演算に３６０度全周画像を用いており、これによって、特徴点の追跡距離を長くでき、特徴点を十分に多く選択することができ、遠距離、中距離、短距離それぞれに都合の良い特徴点を選択することができるようになる。また、回転ベクトルを補正する場合には、極回転変換処理を加えることで、演算処理も容易に行えるようになる。これらのことから、より精度の高い演算結果が得られるようになる。
なお、図１３は、ＣＶ演算部２における処理を理解し易くするために、１台又は複数台のカメラで撮影した画像を合成した３６０度全周囲の球面画像を地図図法でいうメルカトール図法で展開したものを示しているが、実際のＣＶ演算では、必ずしもメルカトール図法による展開画像である必要はない。
【０１３２】
次に、誤差最小化部２-４では、各フレームに対応する複数のカメラ位置と複数の特徴点の数により、複数通り生じる演算方程式により、各特徴点に基づくベクトルを複数通り演算して求めて、各特徴点の位置及びカメラ位置の分布が最小になるように統計処理をして、最終的なベクトルを求める。例えば、複数フレームのカメラ位置、カメラ回転及び複数の特徴点について、Levenberg-Marquardt法により最小自乗法の最適解を推定し、誤差を収束してカメラ位置、カメラ回転行列、特徴点の座標を求める。
さらに、誤差の分布が大きい特徴点については削除し、他の特徴点に基づいて再演算することで、各特徴点及びカメラ位置での演算の精度を上げるようにする。
このようにして、特徴点の位置とカメラベクトルを精度良く求めることができる。
【０１３３】
図１５〜図１７に、ＣＶ演算により得られる特徴点の三次元座標とカメラベクトルの例を示す。図１５〜図１７は、本実施形態のＣＶ演算によるベクトル検出方法を示す説明図であり、移動するカメラによって取得された複数のフレーム画像によって得られるカメラ及び対象物の相対的な位置関係を示す図である。
図１５では、図１３の画像１，２に示した特徴点１〜４の三次元座標と、画像１と画像２の間で移動するカメラベクトル（Ｘ，Ｙ，Ｚ）が示されている。
図１６及び図１７は、充分に多くの特徴点とフレーム画像により得られた特徴点の位置と移動するカメラの位置が示されている。同図中、グラフ中央に直線状に連続する○印がカメラ位置であり、その周囲に位置する○印が特徴点の位置と高さを示している。
【０１３４】
ここで、ＣＶ演算部２におけるＣＶ演算は、より高精度な特徴点とカメラ位置の三次元情報を高速に得るために、図１８に示すように、カメラから特徴点の距離に応じて複数の特徴点を設定し、複数の演算を繰り返し行うようにする。
具体的には、ＣＶ演算部２では、画像内には映像的に特徴がある特徴点を自動検出し、各フレーム画像内に特徴点の対応点を求める際に、カメラベクトル演算に用いるｎ番目とｎ＋ｍ番目の二つのフレーム画像FｎとＦｎ＋ｍに着目して単位演算とし、ｎとｍを適切に設定した単位演算を繰り返すことができる。
ｍはフレーム間隔であり、カメラから画像内の特徴点までの距離によって特徴点を複数段に分類し、カメラから特徴点までの距離が遠いほどｍが大きくなるように設定し、カメラから特徴点までの距離が近いほどｍが小さくなるように設定する。このようにするのは、カメラから特徴点までの距離が遠ければ遠いほど、画像間における位置の変化が少ないからである。
【０１３５】
そして、特徴点のｍ値による分類を、十分にオーバーラップさせながら、複数段階のｍを設定し、画像の進行とともにｎが連続的に進行するのにともなって、演算を連続的に進行させる。そして、ｎの進行とｍの各段階で、同一特徴点について複数回重複演算を行う。
このようにして、フレーム画像ＦｎとＦｎ＋ｍに着目した単位演算を行うことにより、ｍ枚毎にサンプリングした各フレーム間（フレーム間は駒落ちしている）では、長時間かけて精密カメラベクトルを演算し、フレーム画像ＦｎとＦｎ＋ｍの間のｍ枚のフレーム（最小単位フレーム）では、短時間処理で行える簡易演算とすることができる。
【０１３６】
ｍ枚毎の精密カメラベクトル演算に誤差がないとすれば、ｍ枚のフレームのカメラベクトルの両端は、高精度演算をしたＦｎとＦｎ＋ｍのカメラベクトルと重なることになる。従って、ＦｎとＦｎ＋ｍの中間のｍ枚の最小単位のフレームについては簡易演算で求め、簡易演算で求めたｍ枚の最小単位フレームのカメラベクトルの両端を、高精度演算で求めたＦｎとＦｎ＋ｍのカメラベクトルに一致するように、ｍ枚の連続したカメラベクトルのスケール調整をすることができる。
このようにして、画像の進行とともにｎが連続的に進行することにより、同一特徴点について複数回演算されて得られる各カメラベクトルの誤差が最小になるようにスケール調整して統合し、最終のカメラベクトルを決定することができる。これにより、誤差のない高精度のカメラベクトルを求めつつ、簡易演算を組み合わせることにより、演算処理を高速化することができるようになる。
【０１３７】
ここで、簡易演算としては、精度に応じて種々の方法があるが、例えば、(1)高精度演算では１００個以上の多くの特徴点を用いる場合に、簡易演算では最低限の１０個程度の特徴点を用いる方法や、(2)同じ特徴点の数としても、特徴点とカメラ位置を同等に考えれば、そこには無数の三角形が成立し、その数だけの方程式が成立するため、その方程式の数を減らすことで、簡易演算とすることができる。
これによって、各特徴点及びカメラ位置の誤差が最小になるようにスケール調整する形で統合し、距離演算を行い、さらに、誤差の分布が大きい特徴点を削除し、必要に応じて他の特徴点について再演算することで、各特徴点及びカメラ位置での演算の精度を上げることができる。
【０１３８】
また、このように高速な簡易演算を行うことにより、カメラベクトルのリアルタイム処理が可能となる。カメラベクトルのリアルタイム処理は、目的の精度をとれる最低のフレーム数と、自動抽出した最低の特徴点数で演算を行い、カメラベクトルの概略値をリアルタイムで求め、表示し、次に、画像が蓄積するにつれて、フレーム数を増加させ、特徴点の数を増加させ、より精度の高いカメラベクトル演算を行い、概略値を精度の高いカメラベクトル値に置き換えて表示することができる。
【０１３９】
さらに、本実施形態では、より高精度のカメラベクトルを求めるために、三次元情報（三次元形状）の追跡を行うことができる。
具体的には、まず、三次元情報追跡部２-５で、カメラベクトル演算部２-３，誤差最小化部２-４を経て得られたカメラベクトルを概略のカメラベクトルと位置づけ、その後のプロセスで生成される画像の一部として得られる三次元情報（三次元形状）に基づいて、複数のフレーム画像に含まれる部分的三次元情報を隣接するフレーム間で連続的に追跡して三次元形状の自動追跡を行う。
そして、この三次元情報追跡部２-５で得られた三次元情報の追跡結果から、高精度カメラベクトル演算部２-６においてより高精度なカメラベクトルが求められる。
【０１４０】
上述した特徴点抽出部２-１及び特徴点対応処理部２-２では、特徴点を複数のフレーム間画像内に自動追跡するが、特徴点が消失するなどして特徴点の追跡フレーム数に制限が出てくることがある。また、画像は二次元であり、追跡途中で形状が変化するために追跡精度にも一定の限界がある。
そこで、特徴点追跡で得られるカメラベクトルを概略値と位置づけ、その後のプロセスで得られる三次元情報（三次元形状）を各フレーム画像上に追跡して、その軌跡から高精度カメラベクトルを求めることができる。
三次元形状の追跡は、マッチング及び相関の精度を得やすく、三次元形状はフレーム画像によって、その三次元形状も大きさも変化しないので、多くのフレームに亘って追跡が可能であり、そのことでカメラベクトル演算の精度を向上させることができる。これはカメラベクトル演算部２-３により概略のカメラベクトルが既知であり、三次元形状が既に分かっているから可能となるものである。
【０１４１】
カメラベクトルが概略値の場合、非常に多くのフレームに亘る三次元座標の誤差は、特徴点追跡による各フレームに関係するフレームが少ないので、誤差が累積して長距離では次第に大きな誤差になるが、画像の一部分を切り取ったときの三次元形状の誤差は相対的に少なく、形状の変化と大きさに及ぼす影響はかなり少ないものとなる。このため、三次元形状での比較や追跡は、二次元形状追跡の時よりも極めて有利となる。追跡において、二次元形状での追跡の場合、複数のフレームにおける形状の変化と大きさの変化を避けられないまま追跡することになるので、誤差が大きかったり、対応点が見つからないなどの問題があったが、三次元形状での追跡においては形状の変化が極めて少なく、しかも原理的に大きさの変化もないので、正確な追跡が可能となる。
【０１４２】
ここで、追跡の対象となる三次元形状データとしては、例えば、特徴点の三次元分布形状や、特徴点の三次元分布形状から求められるポリゴン面等がある。
また、得られた三次元形状を、カメラ位置から二次元画像に変換して、二次元画像として追跡することも可能である。カメラベクトルの概略値が既知であることから、カメラ視点からの二次元画像に投影変換が可能であり、カメラ視点の移動による対象の形状変化にも追従することが可能となる。
【０１４３】
以上のようにして求められたカメラベクトルは、全周ビデオカメラ１-１で撮影されたビデオ映像中に重ねて表示することができる。
例えば、図１９に示すように、車載カメラからの映像を平面展開して、各フレーム画像内の目的平面上の対応点を自動で探索し、対応点を一致させるように結合して目的平面の結合画像を生成し、同一の座標系に統合して表示する。
さらに、その共通座標系の中にカメラ位置とカメラ方向を次々に検出し、その位置や方向、軌跡をプロットしていくことができる。ＣＶデータは、その三次元位置と３軸回転を示しており、ビデオ映像に重ねて表示することで、ビデオ映像の各フレームでＣＶ値を同時に観察できる。ＣＶデータをビデオ映像に重ねて表示した画像例を図１９に示す。
【０１４４】
なお、ビデオ映像内にカメラ位置を正しく表示すると、ＣＶ値が示すビデオ映像内の位置は画像の中心となり、カメラ移動が直線に近い場合は、すべてのフレームのＣＶ値が重なって表示されてしまうので、例えば図１９に示すように、敢えてカメラ位置から真下に１メートルの位置を表示することが適切である。あるいは道路面までの距離を基準として、道路面の高さにＣＶ値を表示するのがより適切である。
そして、以上のようにしてＣＶ演算により得られたＣＶ値データが、本実施形態に係る三次元地図自動生成装置１００（図１、図６参照）に入力され、上述した映像のみに基づく三次元地図の自動生成が行われることになる。
【０１４５】
以上、本発明の三次元地図自動生成装置について、好ましい実施形態を示して説明したが、本発明は、上述した実施形態にのみ限定されるものではなく、本発明の範囲で種々の変更実施が可能であることは言うまでもない。
例えば、本発明の三次元地図を備えるナビゲーション装置、自動運転装置が搭載される各種の移動体に適用が可能であり、適用する移動体としては、地上を走行する車両は勿論のこと、地上車両に限らず、三次元空間を航行するものであっても良い。飛行機でも利用可能であるから、着陸時の精度の高いナビゲーションや自動運転が可能である。
【産業上の利用可能性】
【０１４６】
本発明は、例えば、自動車に搭載されるカーナビゲーション装置、飛行機に搭載されるナビゲーション装置、危険な箇所での無人自動運転重機、自動運転用のナビゲーション装置、ロボットのナビゲーション装置などに好適な三次元地図の自動生成に好適に利用することができる。
【符号の説明】
【０１４７】
１ 動画像取得装置
２ ＣＶ映像生成装置
３ 領域分割装置
４ フレーム内小領域特徴点三次元化装置
５ 複数領域ポリゴン化装置
６ 連続処理装置
７ テクスチャー取得装置
【特許請求の範囲】
【請求項１】
移動する車両等に積載されたカメラにより周囲の対象物及びその背景の動画像を取得する動画像取得装置と、
前記動画像取得装置によって取得された前記動画像から、映像に映っている背景と対象物に固定された静止座標系に対して移動しているカメラ位置とカメラ姿勢を、前記静止座標系に対する三次元位置及び三軸回転姿勢を示す六変数（X,Y,Z,θx,θy,θz）からなる所定のカメラベクトル値（ＣＶ値）を演算により求め、そのＣＶ値を前記動画像の各フレームと対応させた所定のカメラベクトル映像（ＣＶ映像）を生成するＣＶ映像生成装置と、
前記ＣＶ映像生成装置で得られたＣＶ映像の動画像中から、静止画像である画像フレームを選択して取り出し、当該静止画像中に写っている複数の対象物及び背景を、画像の輝度分布、及び／又は色相分布、及び／又は彩度分布から分類して密度の固まりで切り取り、指定された大きさと数の範囲で、互いに隣接する複数の小領域に分割した領域分割画像を演算により自動取得する領域分割装置と、
前記領域分割装置によって取得された領域分割画像内の各小領域を、その領域分割画像に対応するＣＶ映像のフレームに対応させ、そのフレーム内にフレーム内小領域を定義し、フレーム内小領域の中に複数の特徴点を発生させてＣＶ映像の複数の隣接フレームに亘ってトラッキングすることにより、前記複数の特徴点の三次元座標を演算により求めるフレーム内小領域特徴点三次元化装置と、
複数の前記フレーム内小領域で取得された前記複数の特徴点の三次元座標から、フレーム内小領域の三次元座標を取得し、当該三次元座標を対応する領域分割画像内の小領域の三次元座標として所定の面を抽出して、当該小領域を隣接する小領域と統合又は分割することにより所望のポリゴンを生成し、当該ポリゴンの生成を前記領域分割画像中の分割領域に対して行うことにより複数のポリゴンを自動生成する複数領域ポリゴン化装置と、
を備えることを特徴とする三次元地図自動生成装置。
【請求項２】
前記領域分割画像に対応する前記ＣＶ映像のフレームに関する処理を所定数の領域ポリゴンが生成されるまで実行したところで、前記ＣＶ映像のフレームを進行させて、次の領域分割画像を指定して同様の処理を繰り返すことにより、先の領域分割画像では生成されていないポリゴン、及び／又は次の領域分割画像に初めて現れて取得済みのポリゴンに連続するポリゴンを生成し、順次指定される領域分割画像からポリゴンを順次生成して、目的の対象物と背景からなる三次元化地図を連続的に結合して所定範囲の三次元地図を自動生成する連続処理装置を備える請求項１記載の三次元地図自動生成装置。
【請求項３】
前記フレーム内小領域特徴点三次元化装置が、
前記領域分割装置によって取得された領域分割画像内の小領域の境界付近に複数の特徴点を発生させる小領域境界特徴点発生装置と、
前記領域分割画像に対応するフレーム内小領域において、新たに発生させた複数の特徴点を、既に取得しているＣＶ値を用いて複数の隣接フレームへの特徴点の移動を予測しつつトラッキングして、複数の特徴点の三次元座標を取得する特徴点三次元化装置と、を備える請求項１又は２記載の三次元地図自動生成装置。
【請求項４】
前記複数領域ポリゴン化装置が、
前記小領域三次元化装置によって取得された小領域内の複数の特徴点の三次元データに基づいて、単一平面を推定する平面推定、及び／又は複数平面を推定する複数平面推定、及び／又は小領域境界の直線を推定する直線推定、及び／又は複数平面のなす角度を推定する平面交差角推定、及び／又は面を長方形と推定してその長方形の辺の長さを推定する長方形推定、及び／又は平面の法線の鉛直及び水平を推定する平面鉛直水平推定を行う領域面推定装置を備え、取得された小領域面の形状を絞り込む請求項１乃至３のいずれか一項記載の三次元地図自動生成装置。
【請求項５】
前記複数領域ポリゴン化装置によって取得された三次元ポリゴンについて、対応するＣＶ映像のフレームからテクスチャーを取得して、テクスチャー付きのポリゴンを自動生成するテスクチャー取得装置を備える請求項４記載の三次元地図自動生成装置。
【請求項６】
前記フレーム内小領域特徴点三次元化装置により得られたフレーム内小領域の中に生成した複数の特徴点に対して、前記ＣＶ値を用いずに、新たにＣＶ演算と同様の処理を行うことで、映像に映っている移動体対象物に固定された移動座標系に着目し、前記移動座標系に対するカメラ位置とカメラ姿勢の三次元位置、三軸回転姿勢を示す六変数（Xr,Yr,Zr,φx,φy,φz）からなる所定のＲＶ値を自動演算で求めるＲＶ演算装置と、
そのＲＶ値を前記動画像の各フレームと対応させたＲＶ映像を生成するＲＶ映像生成装置と、
同時に移動体の特徴点三次元座標を求める特徴点三次元化装置と、を備える請求項１乃至５のいずれか一項記載の三次元地図自動生成装置。
【請求項１】
移動する車両等に積載されたカメラにより周囲の対象物及びその背景の動画像を取得する動画像取得装置と、
前記動画像取得装置によって取得された前記動画像から、映像に映っている背景と対象物に固定された静止座標系に対して移動しているカメラ位置とカメラ姿勢を、前記静止座標系に対する三次元位置及び三軸回転姿勢を示す六変数（X,Y,Z,θx,θy,θz）からなる所定のカメラベクトル値（ＣＶ値）を演算により求め、そのＣＶ値を前記動画像の各フレームと対応させた所定のカメラベクトル映像（ＣＶ映像）を生成するＣＶ映像生成装置と、
前記ＣＶ映像生成装置で得られたＣＶ映像の動画像中から、静止画像である画像フレームを選択して取り出し、当該静止画像中に写っている複数の対象物及び背景を、画像の輝度分布、及び／又は色相分布、及び／又は彩度分布から分類して密度の固まりで切り取り、指定された大きさと数の範囲で、互いに隣接する複数の小領域に分割した領域分割画像を演算により自動取得する領域分割装置と、
前記領域分割装置によって取得された領域分割画像内の各小領域を、その領域分割画像に対応するＣＶ映像のフレームに対応させ、そのフレーム内にフレーム内小領域を定義し、フレーム内小領域の中に複数の特徴点を発生させてＣＶ映像の複数の隣接フレームに亘ってトラッキングすることにより、前記複数の特徴点の三次元座標を演算により求めるフレーム内小領域特徴点三次元化装置と、
複数の前記フレーム内小領域で取得された前記複数の特徴点の三次元座標から、フレーム内小領域の三次元座標を取得し、当該三次元座標を対応する領域分割画像内の小領域の三次元座標として所定の面を抽出して、当該小領域を隣接する小領域と統合又は分割することにより所望のポリゴンを生成し、当該ポリゴンの生成を前記領域分割画像中の分割領域に対して行うことにより複数のポリゴンを自動生成する複数領域ポリゴン化装置と、
を備えることを特徴とする三次元地図自動生成装置。
【請求項２】
前記領域分割画像に対応する前記ＣＶ映像のフレームに関する処理を所定数の領域ポリゴンが生成されるまで実行したところで、前記ＣＶ映像のフレームを進行させて、次の領域分割画像を指定して同様の処理を繰り返すことにより、先の領域分割画像では生成されていないポリゴン、及び／又は次の領域分割画像に初めて現れて取得済みのポリゴンに連続するポリゴンを生成し、順次指定される領域分割画像からポリゴンを順次生成して、目的の対象物と背景からなる三次元化地図を連続的に結合して所定範囲の三次元地図を自動生成する連続処理装置を備える請求項１記載の三次元地図自動生成装置。
【請求項３】
前記フレーム内小領域特徴点三次元化装置が、
前記領域分割装置によって取得された領域分割画像内の小領域の境界付近に複数の特徴点を発生させる小領域境界特徴点発生装置と、
前記領域分割画像に対応するフレーム内小領域において、新たに発生させた複数の特徴点を、既に取得しているＣＶ値を用いて複数の隣接フレームへの特徴点の移動を予測しつつトラッキングして、複数の特徴点の三次元座標を取得する特徴点三次元化装置と、を備える請求項１又は２記載の三次元地図自動生成装置。
【請求項４】
前記複数領域ポリゴン化装置が、
前記小領域三次元化装置によって取得された小領域内の複数の特徴点の三次元データに基づいて、単一平面を推定する平面推定、及び／又は複数平面を推定する複数平面推定、及び／又は小領域境界の直線を推定する直線推定、及び／又は複数平面のなす角度を推定する平面交差角推定、及び／又は面を長方形と推定してその長方形の辺の長さを推定する長方形推定、及び／又は平面の法線の鉛直及び水平を推定する平面鉛直水平推定を行う領域面推定装置を備え、取得された小領域面の形状を絞り込む請求項１乃至３のいずれか一項記載の三次元地図自動生成装置。
【請求項５】
前記複数領域ポリゴン化装置によって取得された三次元ポリゴンについて、対応するＣＶ映像のフレームからテクスチャーを取得して、テクスチャー付きのポリゴンを自動生成するテスクチャー取得装置を備える請求項４記載の三次元地図自動生成装置。
【請求項６】
前記フレーム内小領域特徴点三次元化装置により得られたフレーム内小領域の中に生成した複数の特徴点に対して、前記ＣＶ値を用いずに、新たにＣＶ演算と同様の処理を行うことで、映像に映っている移動体対象物に固定された移動座標系に着目し、前記移動座標系に対するカメラ位置とカメラ姿勢の三次元位置、三軸回転姿勢を示す六変数（Xr,Yr,Zr,φx,φy,φz）からなる所定のＲＶ値を自動演算で求めるＲＶ演算装置と、
そのＲＶ値を前記動画像の各フレームと対応させたＲＶ映像を生成するＲＶ映像生成装置と、
同時に移動体の特徴点三次元座標を求める特徴点三次元化装置と、を備える請求項１乃至５のいずれか一項記載の三次元地図自動生成装置。
【図１】
【図４】
【図５】
【図６】
【図７】
【図９】
【図１４】
【図１８】
【図２】
【図３】
【図８】
【図１０】
【図１１】
【図１２】
【図１３】
【図１５】
【図１６】
【図１７】
【図１９】
【図４】
【図５】
【図６】
【図７】
【図９】
【図１４】
【図１８】
【図２】
【図３】
【図８】
【図１０】
【図１１】
【図１２】
【図１３】
【図１５】
【図１６】
【図１７】
【図１９】
【公開番号】特開２０１２−１１８６６６（Ｐ２０１２−１１８６６６Ａ）
【公開日】平成２４年６月２１日（２０１２．６．２１）
【国際特許分類】
【出願番号】特願２０１０−２６６４００（Ｐ２０１０−２６６４００）
【出願日】平成２２年１１月３０日（２０１０．１１．３０）
【出願人】（３９３０２１１４１）株式会社岩根研究所 (1)
【出願人】（７０９００３１２６）有限会社パワーサプライ (1)
【Ｆターム（参考）】
【公開日】平成２４年６月２１日（２０１２．６．２１）
【国際特許分類】
【出願日】平成２２年１１月３０日（２０１０．１１．３０）
【出願人】（３９３０２１１４１）株式会社岩根研究所 (1)
【出願人】（７０９００３１２６）有限会社パワーサプライ (1)
【Ｆターム（参考）】
[ Back to top ]