３次元位置情報復元装置およびその方法
【課題】透視投影カメラモデルに基づいた擬似的でない正確な３次元位置を復元する。
【解決手段】各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する手段と、連続する所定数の二次元画像を各特徴点毎に分配する手段と、各特徴点毎の連続する所定数の二次元画像について各特徴点毎の３次元位置Ｘα′とカメラの位置Πκ′を射影復元する射影復元部と、前記射影復元部により射影復元した３次元位置Ｘα′とカメラの位置Πκ′とを射影変換行列Ｈおよびカメラパラメータ行列により正しい３次元位置Ｘαとカメラの位置Πκとを求める自己校正部とを有する。
【解決手段】各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する手段と、連続する所定数の二次元画像を各特徴点毎に分配する手段と、各特徴点毎の連続する所定数の二次元画像について各特徴点毎の３次元位置Ｘα′とカメラの位置Πκ′を射影復元する射影復元部と、前記射影復元部により射影復元した３次元位置Ｘα′とカメラの位置Πκ′とを射影変換行列Ｈおよびカメラパラメータ行列により正しい３次元位置Ｘαとカメラの位置Πκとを求める自己校正部とを有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の二次元画像から注目する特徴点の３次元位置を高速に復元してコンピュータグラフィックスにおけるポリゴンデータの自動生成や複合現実感などの分野に応用可能とする装置およびその方法に関するものである。
【背景技術】
【０００２】
図９は従来の３次元位置情報復元処理の概要構成を示す機能ブロック図である。９０１は撮像部、９０２は対応点検出部、９０３は疑似透視投影による因子分解部であり、対応点検出部９０２と因子分解部９０３とにおける処理ステップにより、擬似的に３次元点を得る。具体的には、撮像部９０１で撮像した複数の画像の対応点をとり、その対応点から３次元点を復元する。このとき、撮像部９０１を構成するカメラの内部パラメータが前もって分かっていることが必要である。
また、３次元復元処理は、カメラモデルを平行投影や弱透視投影（図１０（ｂ）に示す。）に限り、擬似的に３次元復元する手法である因子分解法あるいはこの改良型が主流である。このため復元精度が低い。
さらに、従来法は、画像数と特徴点数が増加した場合、因子分解法の処理に必要な画像中の特徴点列から作るモーメント行列の次数が急激に増加するので、処理メモリが急激に増加する手法である。
【０００３】
以下、画像をκ、その中の対応点をαとして従来技術の作用および動作を説明する。
特徴点ｘκαを元に特徴点ベクトルＰκαを以下のように作る。
Ｐκα＝（ｘ１αＴ，…ｘＭαＴ）Ｔ （１）
重心ベクトルＰＣを以下のように作成する。
【数１】
以下の計算を行いモーメント行列Ｗ（２Ｍ×Ｎ行列）を作る。
Ｐα′＝Ｐα−ＰＣ
Ｗ＝（Ｐ１′，…，ＰＮ′） （３）
Ｗを用い低下のように特異値分解を行い行列ＵとＶを求める。
Ｗ＝ＵＤＶＴ （４）
このＶを用いて、以下の式により擬似的な３次元位置Ｘαが求まる。
（Ｘ１Ｘ２…ＸＮ）＝（ｖ１ｖ２ｖ３）Ｔ （５）
但し、
Ｖ＝（ｖ１ｖ２ｖ３ｖ４） （６）
である。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
解決しようとする課題は、透視投影カメラモデル（図１０（ｂ））に基づいた擬似的でない正確な３次元位置情報復元装置および方法を提供することである。
また、従来法においては、平行投影のカメラモデルでも画像数Ｍと特徴点をＮとしたとき、このＭ×Ｎの値が増加することにより、速度低下および使用メモリの増加をきたしている。本発明が解決しようとする他の課題は、画像数や点数によらず一定のメモリで３次元復元問題が解けるような計算手法を実現する装置および方法を提供することにある。
すなわち、従来法は、カメラモデルを平行投影することによる計算法であるため３次元復元の精度が悪い。また、従来の因子分解法による計算処理法は、画像数Ｍと対象点Ｎに依存する。このため実用的なサイズでは計算が遅くなりメモリサイズの制限から実用的なサイズの点数の復元が行えなかった。このため、復元をビデオレートで行うためには処理装置の規模が大きくなり経済的な制約から実用的なものができていない。
因子分解法は、基本的に特異値分解を行うことに結びつくため、画像数Ｍと一画像当たりの特徴点数Ｎの積である２Ｍ×Ｎ行列の特異値問題を解く必要がある。点数が少ない場合は実用に耐えるが、１０枚の画像と１０００点の特徴点数を例に考えた場合、１０５要素数の行列を扱う必要がある。
また、復元データが疑似透視投影に基づくため、復元した３次元データの精度が悪い。特に、カメラモデルとして疑似透視投影を用いるため近距離での復元精度に問題がある。
従って、本発明は、カメラモデルとして平行投影を仮定して複数の連続する画像から３次元位置を得る従来の擬似的な３次元復元でなく、カメラモデルとして透視投影を仮定して正確な３次元復元を高速で行う装置および手法を提供することである。
【課題を解決するための手段】
【０００５】
以下の式（７）は、３次元位置Ｘαがκ画像の対応する２次元の点ｘκαに、カメラ投影行列（プロジェクションマトリクス）Πκを用いて変換される関係を示したものである。図１０に対応の模式図を示す。
【数２】
また、カメラ投影行列Πκは、カメラパラメータＫκカメラの位置ｔκおよびＲκを用いて以下のように表される。
Πκ＝Ｋκ（Ｒκｔκ） （８）
また、カメラパラメータＫκは以下である。
【数３】
この式（７）を満足する、未知のＸα，Πκを既知のｘκαを用いて求めることが３次元復元である。
このためには、まずこの式（７）を仮に満たすΠκ′とＸα′を求める。これを射影復元と呼ぶ。これには複数の画像間で対応する点ｘκαを縦に積んで作成した特徴点ベクトルＰ＝（ｘ１αＴ，…，ｘＭαＴ）Ｔがランク４の制約を持つことを利用して、実施例の射影復元に示す方法で射影復元する。
次に、これを正しいΠκとＸαに変換する。自己構成と呼ぶ。両者の間にはΠκ′＝ΠκＨ，Ｘα′＝Ｈ−１Ｘαの関係があり、このＨが射影復元の不定性である。これには、
Πκ＝Ｋκ（Ｒκｔκ） （１０）
が
Πκｄｉａｇ（１，１，１，０）ΠκＴ＝ＫκＫκＴ （１１）
となる性質を拘束条件に利用して、実施例の自己校正処理に示す方法でＨおよびＫκを得ることにより、正しい３次元復元を行う。
【０００６】
すなわち、上記課題を解決するため請求項１に係る３次元位置情報復元装置は、カメラにより撮像した複数の連続する二次元画像を元にして、撮像対象となる情景中の３次元位置を復元する装置であって、各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する手段と、連続する所定数の二次元画像を各特徴点毎に分配する手段と、各特徴点毎の連続する所定数の二次元画像について各特徴点毎の３次元位置Ｘα′とカメラの位置Πκ′を射影復元する射影復元部と、前記射影復元部により射影復元した３次元位置Ｘα′とカメラの位置Πκ′とを射影変換行列Ｈおよびカメラパラメータ行列により正しい３次元位置Ｘαとカメラの位置Πκとを求める自己校正部とを有することを特徴とするものである。
【０００７】
請求項２に係る３次元位置情報復元装置は、請求項１に記載のものにおいて、射影計算部において３次元位置Ｘα′を計算するに際して、画像番号κ（κ＝１，…，Ｍ）、特徴点番号α（α＝１，…，Ｎ）の画素点ｘκα、その単位ベクトルへの正規化をＮ［ｘκα］として
（１）射影的奥行をｚκα＝１と初期化し、
（２）ｚ１αｘ１α，ｚ２αｘ２α，…，ｚＭαｘＭαを縦に並べて３Ｍ次元ベクトルｐαとして以下の単位ベクトルに正規化し、
ｐαＴ＝Ｎ［（ｚ１αｘ１αＴ，ｚ２αｘ２αＴ，…，ｚＭαｘＭαＴ）］
（３）特徴点α＝１〜Ｎに対してＰαを求め、次の３Ｍ×Ｎ行列Ｐを作り、
Ｐ＝（ｐ１ｐ２…ｐＮ）
（４）行列Ｐを以下のように特異値分解し、
Ｐ＝Ｕｄｉａｇ（σ１，σ２，…）ＶＴ
行列Ｕの最初の４列ｕ１，ｕ２，ｕ３，ｕ４を求め、
（５）３×４の投影行列Πκを次のように計算し、
（ただし、ｕ１κはｕｉの、３（κ−１）＋１，３（κ−１）＋２，３（κ−１）＋３成分を第１，２，３成分とする３次元ベクトルである。）
（６）次の計算をα＝１，…，Ｎに渡って計算し、３次元位置Ｘαを計算する。
（ａ） 次のＣｋｉαを（κｉ）要素とするＭ×４行列Ｃαを計算し、
Ｃｋｉα＝（Ｎ［ｘκα］，ｕｉｋ）
（ｂ）次の４×４行列Ｄα＝（Ｄｉｊα）を計算し、
【数４】
（ただし、計算は行列が対称であるのでｉ＜ｊの（ｉ，ｊ）要素のみ計算し、ｉ＞ｊの（ｉ，ｊ）要素は（ｊ，ｉ）要素の値をコピーする。）
（ｃ）行列Ｄαの固有値問題を解き、この最大固有値に対応する単位固有ベクトルμαを求め、これを用いて次の計算によりξαを計算し、
ξα＝±Ｎ［Ｃαμα］
（このとき、固有値の符号は次のようにする。
【数５】
（ｄ）得られたξαから射影的奥行きｚκαを次のように計算し、
ｚκα＝ξκα／‖ｘκα‖
（ｅ）得られたｚκαを用いてベクトルＰαを再計算し、さらに正規化し前記（３）の行列Ｐを再計算し、
（ｆ）３次元位置Ｘα＝（Ｘκα）を以下のように計算する
Ｘκα＝（ｐα，ｕκ）， ｋ＝１〜４
ことを特徴とするものである。
【０００８】
請求項３に係る３次元位置情報復元装置は、請求項１に記載のものにおいて、自己校正部において正しい３次元位置Ｘαとカメラの位置Πκとを求めるに際して、射影復元部により射影復元した３次元位置Ｘα′とカメラの位置Πκ′とを射影変換行列Ｈおよびカメラパラメータ行列により正しい３次元位置Ｘαとカメラの位置Πκとを
Πκ′＝ΠκＨ
Ｘα′＝Ｈ−１Ｘα
より求めることを特徴とするものである。
【０００９】
請求項４に係る３次元位置情報復元装置は、請求項１に記載のものにおいて、射影計算部において３次元位置Ｘα′を計算するに際して、画像番号κ（κ＝１，…，Ｍ）、特徴点番号α（α＝１，…，Ｎ）の画素点ｘκα、その単位ベクトルへの正規化をＮ［ｘκα］として
（１）射影的奥行をｚκα＝１と初期化し、
（２）ｚ１αｘ１α，ｚ２αｘ２α，…，ｚＭαｘＭαを縦に並べて３Ｍ次元ベクトルｐαとして以下の単位ベクトルに正規化し、
ｐαＴ＝Ｎ［（ｚ１αｘ１αＴ，ｚ２αｘ２αＴ，…，ｚＭαｘＭαＴ）］
（３）特徴点α＝１〜Ｎに対してＰαを求め、次の３Ｍ×Ｎ行列Ｐを作り、
Ｐ＝（ｐ１ｐ２…ｐＮ）
（４）行列Ｐを以下のように特異値分解し、
Ｐ＝Ｕｄｉａｇ（σ１，σ２，…）ＶＴ
行列Ｕの最初の４列ｕ１，ｕ２，ｕ３，ｕ４を求め、
（５）３×４の投影行列Πκを次のように計算し、
（ただし、ｕ１κはｕｉの、３（κ−１）＋１，３（κ−１）＋２，３（κ−１）＋３成分を第１，２，３成分とする３次元ベクトルである。）
（６）次の計算をα＝１，…，Ｎに渡って計算し、３次元位置Ｘαを計算する。
（ａ） 次のＣｋｉαを（κｉ）要素とするＭ×４行列Ｃαを計算し、
Ｃｋｉα＝（Ｎ［ｘκα］，ｕｉｋ）
（ｂ）次の４×４行列Ｄα＝（Ｄｉｊα）を計算し、
【数６】
（ただし、計算は行列が対称であるのでｉ＜ｊの（ｉ，ｊ）要素のみ計算し、ｉ＞ｊの（ｉ，ｊ）要素は（ｊ，ｉ）要素の値をコピーする。）
（ｃ）行列Ｄαの固有値問題を解き、この最大固有値に対応する単位固有ベクトルμαを求め、これを用いて次の計算によりξαを計算し、
ξα＝±Ｎ［Ｃαμα］
（このとき、固有値の符号は次のようにする。
【数７】
（ｄ）得られたξαから射影的奥行きｚκαを次のように計算し、
ｚκα＝ξκα／‖ｘκα‖
（ｅ）得られたｚκαを用いてベクトルＰαを再計算し、さらに正規化し前記（３）の行列Ｐを再計算し、
（ｆ）３次元位置Ｘα＝（Ｘκα）を以下のように計算し、
Ｘκα＝（ｐα，ｕκ）， ｋ＝１〜４
自己校正部において正しい３次元位置Ｘαとカメラの位置Πκとを求めるに際して、
射影復元部により射影復元した３次元位置Ｘα′とカメラの位置Πκ′とを射影変換行列Ｈおよびカメラパラメータ行列により正しい３次元位置Ｘαとカメラの位置Πκとを
Πκ′＝ΠκＨ
Ｘα′＝Ｈ−１Ｘα
より求めることを特徴とするものである。
【００１０】
請求項５に係る３次元位置情報復元装置は、請求項１〜請求項４のいずれかに記載のものであって、射影復元部により求めた３次元位置Ｘα′について自己校正部において求めた数学的に正しいが物理的に偽の３次元位置情報を判定して除去する補正部とを有することを特徴とするものである。
【００１１】
請求項６に係る３次元位置情報復元装置は、請求項１に記載のものにおいて、各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する手段が、特徴点の追跡の誤対応の可能性に重み係数を用いて、所定の重み係数が所定数以下の場合に連続する所定数の二次元画像を各特徴点毎に分配することを特徴とするものである。
【００１２】
請求項７に係る３次元位置情報復元装置は、請求項１に記載のものにおいて、各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する手段が、時刻ｔ＋Δｔと時刻ｔの画像Ｉ（ｘ，ｔ＋Δｔ），Ｉ（ｘ，ｔ）を用いて所定数の段階の詳細度ｄを持つ画像Ｉｄ（ｘｄ，ｔ），Ｉｄ（ｘｄ，ｔ＋Δｔ）を作成し、詳細度が粗い順に、特徴点の追跡の誤対応の可能性に重み係数を計算し、当該重み係数を用いて、所定の重み係数が所定数以下の場合に連続する所定数の二次元画像を各特徴点毎に分配することを特徴とするものである。
【００１３】
請求項８に係る３次元位置情報復元装置は、請求項５に記載のものにおいて、射影復元部の射影復元処理と、自己校正部の自己校正処理と、補正部の判定除去処理とをパイプライン化することを特徴とするものである。
【００１４】
請求項９に係る３次元位置情報復元装置は、請求項１〜請求項８のいずれかに記載のものにおいて、各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する手段が、復元可能な特徴点数と画像数の数理的関係に基づき特徴点数の変化に対応して画像数を増減することを特徴とするものである。
【００１５】
請求項１０に係る３次元位置情報復元装置は、請求項１〜請求項９のいずれかに記載のものにおいて、射影復元部の射影復元処理と、自己校正部の自己校正処理と、補正部の判定除去処理とを複数の並列度により構成したことを特徴とするものである。
【００１６】
請求項１１に係る３次元位置情報復元装置は、カメラにより撮像した複数の連続する二次元画像を元にして、撮像対象となる情景中の３次元位置を復元する方法であって、各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する過程と、連続する所定数の二次元画像を各特徴点毎に分配する過程と、各特徴点毎の連続する所定数の二次元画像について各特徴点毎の３次元位置Ｘα′とカメラの位置Πκ′を射影復元する射影復元過程と、前記射影復元過程により射影復元した３次元位置Ｘα′とカメラの位置Πκ′とを射影変換行列Ｈおよびカメラパラメータ行列により正しい３次元位置Ｘαとカメラの位置Πκとを求める自己校正過程とを有することを特徴とするものである。
【００１７】
請求項１２に係る３次元位置情報復元方法は、請求項１１に記載のものにおいて、射影復元過程において３次元位置Ｘα′を計算するに際して、
画像番号κ（κ＝１，…，Ｍ）、特徴点番号α（α＝１，…，Ｎ）の画素点ｘκα、その単位ベクトルへの正規化をＮ［ｘκα］として
（１）射影的奥行をｚκα＝１と初期化し、
（２）ｚ１αｘ１α，ｚ２αｘ２α，…，ｚＭαｘＭαを縦に並べて３Ｍ次元ベクトルｐαとして以下の単位ベクトルに正規化し、
ｐαＴ＝Ｎ［（ｚ１αｘ１αＴ，ｚ２αｘ２αＴ，…，ｚＭαｘＭαＴ）］
（３）特徴点α＝１〜Ｎに対してＰαを求め、次の３Ｍ×Ｎ行列Ｐを作り、
Ｐ＝（ｐ１ｐ２…ｐＮ）
（４）行列Ｐを以下のように特異値分解し、
Ｐ＝Ｕｄｉａｇ（σ１，σ２，…）ＶＴ
行列Ｕの最初の４列ｕ１，ｕ２，ｕ３，ｕ４を求め、
（５）３×４の投影行列Πκを次のように計算し、
（ただし、ｕ１κはｕｉの、３（κ−１）＋１，３（κ−１）＋２，３（κ−１）＋３成分を第１，２，３成分とする３次元ベクトルである。）
（６）次の計算をα＝１，…，Ｎに渡って計算し、３次元位置Ｘαを計算する。
（ａ） 次のＣｋｉαを（κｉ）要素とするＭ×４行列Ｃαを計算し、
Ｃｋｉα＝（Ｎ［ｘκα］，ｕｉｋ）
（ｂ）次の４×４行列Ｄα＝（Ｄｉｊα）を計算し、
【数８】
（ただし、計算は行列が対称であるのでｉ＜ｊの（ｉ，ｊ）要素のみ計算し、ｉ＞ｊの（ｉ，ｊ）要素は（ｊ，ｉ）要素の値をコピーする。）
（ｃ）行列Ｄαの固有値問題を解き、この最大固有値に対応する単位固有ベクトルμαを求め、これを用いて次の計算によりξαを計算し、
ξα＝±Ｎ［Ｃαμα］
（このとき、固有値の符号は次のようにする。
【数９】
（ｄ）得られたξαから射影的奥行きｚκαを次のように計算し、
ｚκα＝ξκα／‖ｘκα‖
（ｅ）得られたｚκαを用いてベクトルＰαを再計算し、さらに正規化し前記（３）の行列Ｐを再計算し、
（ｆ）３次元位置Ｘα＝（Ｘκα）を以下のように計算する
Ｘκα＝（ｐα，ｕκ）， ｋ＝１〜４
ことを特徴とするものである。
【００１８】
請求項１３に係る３次元位置情報復元方法は、請求項１１に記載のものにおいて、自己校正過程において正しい３次元位置Ｘαとカメラの位置Πκとを求めるに際して、射影復元過程により射影復元した３次元位置Ｘα′とカメラの位置Πκ′とを射影変換行列Ｈおよびカメラパラメータ行列により正しい３次元位置Ｘαとカメラの位置Πκとを
Πκ′＝ΠκＨ
Ｘα′＝Ｈ−１Ｘα
より求めることを特徴とするものである。
【００１９】
請求項１４に係る３次元位置情報復元方法は、請求項１１に記載のものにおいて、射影復元過程において３次元位置Ｘα′を計算するに際して、
像番号κ（κ＝１，…，Ｍ）、特徴点番号α（α＝１，…，Ｎ）の画素点ｘκα、その単位ベクトルへの正規化をＮ［ｘκα］として
（１）射影的奥行をｚκα＝１と初期化し、
（２）ｚ１αｘ１α，ｚ２αｘ２α，…，ｚＭαｘＭαを縦に並べて３Ｍ次元ベクトルｐαとして以下の単位ベクトルに正規化し、
ｐαＴ＝Ｎ［（ｚ１αｘ１αＴ，ｚ２αｘ２αＴ，…，ｚＭαｘＭαＴ）］
（３）特徴点α＝１〜Ｎに対してＰαを求め、次の３Ｍ×Ｎ行列Ｐを作り、
Ｐ＝（ｐ１ｐ２…ｐＮ）
（４）行列Ｐを以下のように特異値分解し、
Ｐ＝Ｕｄｉａｇ（σ１，σ２，…）ＶＴ
行列Ｕの最初の４列ｕ１，ｕ２，ｕ３，ｕ４を求め、
（５）３×４の投影行列Πκを次のように計算し、
（ただし、ｕ１κはｕｉの、３（κ−１）＋１，３（κ−１）＋２，３（κ−１）＋３成分を第１，２，３成分とする３次元ベクトルである。）
（６）次の計算をα＝１，…，Ｎに渡って計算し、３次元位置Ｘαを計算する。
（ａ） 次のＣｋｉαを（κｉ）要素とするＭ×４行列Ｃαを計算し、
Ｃｋｉα＝（Ｎ［ｘκα］，ｕｉｋ）
（ｂ）次の４×４行列Ｄα＝（Ｄｉｊα）を計算し、
【数１０】
（ただし、計算は行列が対称であるのでｉ＜ｊの（ｉ，ｊ）要素のみ計算し、ｉ＞ｊの（ｉ，ｊ）要素は（ｊ，ｉ）要素の値をコピーする。）
（ｃ）行列Ｄαの固有値問題を解き、この最大固有値に対応する単位固有ベクトルμαを求め、これを用いて次の計算によりξαを計算し、
ξα＝±Ｎ［Ｃαμα］
（このとき、固有値の符号は次のようにする。
【数１１】
（ｄ）得られたξαから射影的奥行きｚκαを次のように計算し、
ｚκα＝ξκα／‖ｘκα‖
（ｅ）得られたｚκαを用いてベクトルＰαを再計算し、さらに正規化し前記（３）の行列Ｐを再計算し、
（ｆ）３次元位置Ｘα＝（Ｘκα）を以下のように計算し、
Ｘκα＝（ｐα，ｕκ）， ｋ＝１〜４
自己校正過程において正しい３次元位置Ｘαとカメラの位置Πκとを求めるに際して、
射影復元過程により射影復元した３次元位置Ｘα′とカメラの位置Πκ′とを射影変換行列Ｈおよびカメラパラメータ行列により正しい３次元位置Ｘαとカメラの位置Πκとを
Πκ′＝ΠκＨ
Ｘα′＝Ｈ−１Ｘα
より求めることを特徴とするものである。
【００２０】
請求項１５に係る３次元位置情報復元方法は、請求項１１〜請求項１４のいずれかに記載のものであって、射影復元過程により求めた３次元位置Ｘα′について自己校正過程において求めた数学的に正しいが物理的に偽の３次元位置情報を判定して除去する補正過程とを有することを特徴とするものである。
【００２１】
請求項１６に係る３次元位置情報復元方法は、請求項１１に記載のものにおいて、各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する過程が、特徴点の追跡の誤対応の可能性に重み係数を用いて、所定の重み係数が所定数以下の場合に連続する所定数の二次元画像を各特徴点毎に分配することを特徴とするものである。
【００２２】
請求項１７に係る３次元位置情報復元方法は、請求項１１に記載のものにおいて、各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する過程が、時刻ｔ＋Δｔと時刻ｔの画像Ｉ（ｘ，ｔ＋Δｔ），Ｉ（ｘ，ｔ）を用いて所定数の段階の詳細度ｄを持つ画像Ｉｄ（ｘｄ，ｔ），Ｉｄ（ｘｄ，ｔ＋Δｔ）を作成し、詳細度が粗い順に、特徴点の追跡の誤対応の可能性に重み係数を計算し、当該重み係数を用いて、所定の重み係数が所定数以下の場合に連続する所定数の二次元画像を各特徴点毎に分配することを特徴とするものである。
【００２３】
請求項１８に係る３次元位置情報復元方法は、請求項１５に記載のものにおいて、射影復元過程の射影復元処理と、自己校正過程の自己校正処理と、補正過程の判定除去処理とをパイプライン化することを特徴とするものである。
【００２４】
請求項１９に係る３次元位置情報復元方法は、請求項１１〜請求項１８のいずれかに記載のものにおいて、各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する過程が、復元可能な特徴点数と画像数の数理的関係に基づき特徴点数の変化に対応して画像数を増減することを特徴とするものである。
【００２５】
請求項２０に係る３次元位置情報復元方法は、射影復元過程の射影復元処理と、自己校正過程の自己校正処理と、補正過程の判定除去処理とを複数の並列度により構成することを特徴とするものである。
【発明の効果】
【００２６】
請求項１に係る３次元位置情報復元装置によると、複数の連続する二次元画像を元にして、撮像対象となる情景中の３次元位置情報を復元するに際し、３次元復元処理を「射影復元処理」と「自己校正処理」に分解して処理することにより、計算量の削減を図り３次元座標位置を高速かつ正確に復元することができる。
【００２７】
請求項２に係る３次元位置情報復元装置によると、射影復元において、特徴点数Ｎと画像の枚数Ｍが増大したとき、計算量および使用メモリ量がＮ×Ｍに依存して増加せず一定とすることができる。
【００２８】
請求項３に係る３次元位置情報復元装置によると、複数の対象とする画像を撮像したときのカメラの焦点距離や光軸のズレ等の光学的な特性が不明であり、また各々の画像で異なっていても３次元情報の復元が可能とすることができる。
【００２９】
請求項４に係る３次元位置情報復元装置によると、復元計算の過程において各々の撮像画像に対応したカメラの焦点距離や光軸のズレ量や、撮像カメラの空間的な位置および姿勢を、正確に推定できる。
【００３０】
請求項５に係る３次元位置情報復元装置によると、３次元復元処理が数学的に正しいが実際の３次元情報と異なる偽の３次元復元情報を除去することができる。
【００３１】
請求項６に係る３次元位置情報復元装置によると、誤対応の可能性に重み係数を用いて、誤対応の判定誤差を低減することができる。
【００３２】
請求項７に係る３次元位置情報復元装置によると、特徴点の追跡処理において詳細度を用いて誤対応の発生を低減することができる。
【００３３】
請求項８に係る３次元位置情報復元装置によると、各処理をパイプライン化して行うことができる。
【００３４】
請求項９に係る３次元位置情報復元装置によると、復元可能特徴点数と画像数の数理的関係に基づき特徴点数の変化に対応して画像数を増減可能にすることができる。
【００３５】
請求項１０に係る３次元位置情報復元装置によると、特徴点の増加に対する処理速度の低下を、同一の処理の並列度を増やすことで、対応可能とすることができる。
【００３６】
請求項１１に係る３次元位置情報復元方法によると、複数の連続する二次元画像を元にして、撮像対象となる情景中の３次元位置情報を復元するに際し、３次元復元処理を「射影復元処理」と「自己校正処理」に分解して処理することにより、計算量の削減を図り３次元座標位置を高速かつ正確に復元することができる。
【００３７】
請求項１２に係る３次元位置情報復元方法によると、射影復元において、特徴点数Ｎと画像の枚数Ｍが増大したとき、計算量および使用メモリ量がＮ×Ｍに依存して増加せず一定とすることができる。
【００３８】
請求項１３に係る３次元位置情報復元方法によると、複数の対象とする画像を撮像したときのカメラの焦点距離や光軸のズレ等の光学的な特性が不明であり、また各々の画像で異なっていても３次元情報の復元が可能とすることができる。
【００３９】
請求項１４に係る３次元位置情報復元方法によると、復元計算の過程において各々の撮像画像に対応したカメラの焦点距離や光軸のズレ量や、撮像カメラの空間的な位置および姿勢を、正確に推定できる。
【００４０】
請求項１５に係る３次元位置情報復元方法によると、３次元復元処理が数学的に正しいが実際の３次元情報と異なる偽の３次元復元情報を除去することができる。
【００４１】
請求項１６に係る３次元位置情報復元方法によると、誤対応の可能性に重み係数を用いて、誤対応の判定誤差を低減することができる。
【００４２】
請求項１７に係る３次元位置情報復元方法によると、特徴点の追跡処理において詳細度を用いて誤対応の発生を低減することができる。
【００４３】
請求項１８に係る３次元位置情報復元方法によると、各処理をパイプライン化して行うことができる。
【００４４】
請求項１９に係る３次元位置情報復元方法によると、復元可能特徴点数と画像数の数理的関係に基づき特徴点数の変化に対応して画像数を増減可能にすることができる。
【００４５】
請求項２０に係る３次元位置情報復元方法によると、特徴点の増加に対する処理速度の低下を、同一の処理の並列度を増やすことで、対応可能とすることができる。
【実施例１】
【００４６】
本発明の実施例を説明する全体の機能ブロック図を図１に、その構成各部の詳細および情報受け渡しを説明する図を図２〜図８に示す。また、そのフロー図を図１１〜図２０に示す。以下、この図に基づき、作用実施例の詳細な説明を行う。
図１は、本発明の一実施例の構成を示したものである。連続するビデオ画像を入力として検出した特徴点の３次元復元およびカメラ位置の推定を行う実施例を示す。実施例では、特徴点を１０００点、追跡画像数を１０枚として、対応する画像中の特徴点（二次元）を３次元に復元処理する例を示す。処理対象の特徴点数は、並列処理する処理に応じて増加可能であり、画像数は要求精度が高い場合に対応して増加可能である。
図２は、図１の実施例における処理の詳細を示し、撮像データと特徴点列との対応を表したものである。Ｉ（ｘ，ｔ＋Δｔ）に撮像した画像と一フレーム前の画像Ｉ（ｘ，ｔ）間で特徴点に対応がとれる可能性があるもので図示されている。Ｗκα＝０が６個以上ある特徴点データ列は、無効として
とされることを示す。
図３は、図１の実施例における処理の詳細を示し、並列処理におけるフレーム数と特徴点の関係を示したものである。
図４は、図１の実施例における処理の詳細を示し、画像蓄積部における輝度計算と画像イメージを示したものである。
図５は、図１の実施例における処理詳細を示し、画像データから特徴点の検出法を示したものである。
図６は、図１の実施例における処理の詳細を示し、対応点の検出および判定を示したものであり、二枚の画像間の想定対応点を比較して誤対応か否かを判定する。
図７は、図１の実施例における処理の詳細を示し、画像分配部の処理を示したものであり、図の処理例では、１０画像追跡した１０００点の特徴点を１００点ずつ並列処理部へ分配することを示す。
図８は、図１の実施例における処理の詳細を示し、並列処理した復元点およびカメラ位置姿勢をシーケンシャルに整理して出力する処理を示す。
図１において、１０１は撮像装置、１０２は画像蓄積部、１０３は特徴点追跡部、１０４は分配部、１０５は３次元復元部、１０６は統合部である。
特徴点追跡部１０３は、特徴点検出部１０３１、対応点計算／追跡部１０３２を備える。
また、３次元復元部１０５は、射影復元部１０５１ｉ（ｉ＝１〜Ｐ）、自己校正部１０５２ｉ（ｉ＝１〜Ｐ）、補正部１０５３ｉ（ｉ＝１〜Ｐ）に細分され、並列処理の対象として一つの処理部となる。
取り扱う特徴点数が増加した場合、この同一の並列処理部（３次元復元部１０５）を増やすことにより復元性能の増加を図る。
処理の概要を図１に従い説明する。
撮像部１０１で連続したフレームの画像が取られ、画像蓄積部１０２においてグレースケールに変換される。
特徴点検出部１０３１において、例えば１０フレーム間隔で、特徴点として最も良好な性質を持つ複数の画素を特徴点として選択する。以後この特徴点が１０枚の画像にわたり追跡点として追跡される。
この複数の追跡ベクトルが、分配部１０４において並列処理の単位に分解され、３次元復元部１０５の入力となる特徴点の３次元位置Ｘα、フレームκにおけるカメラパラメータＫκおよびカメラの位置姿勢（Ｒκｔκ）を得る。
統合部１０６において複数の３次元復元部１０５からの出力を、一連の順序に従い再配置する。
以下に各機能ブロックの作用、動作の詳細な説明を行う。
【００４７】
［１． 画像蓄積の動作の説明：図４］
カメラで得た画像を輝度値によるモノクロ画像に変換する。このときフレーム番号κを連番で割り当てる。
【００４８】
［２． 特徴点追跡部１０３の動作の説明：図５，６］
３次元復元を行うために必要な複数の画像間で特定の特徴点がどのように移動したかの対応付けを行う処理を行う。
この特徴点追跡部１０３は、追跡点を決める「特徴点の検出」処理を行う特徴点検出部１０３１と、この特徴点を開始点として二枚の連続する画像間の該当特徴点の追跡を行う「対応点計算および追跡」処理を行う対応点計算／追跡部１０３２からなる。
（１）特徴点検出：図５ 追跡を開始する元となる追跡開始点（画素位置）は手動あるいは自動で発生する。図５の例では、この処理の実行される間隔は、画像枚数例えば１０枚毎としている。自動で特徴点を検出する場合は、「特徴量計算」、「特徴量ソート」を経て、「対応点メモリ」に開始点が登録される。以後のフレームからは、この特徴点を追跡の開始点として連続した１０枚の画像（例）を追跡する。
（１−１）特徴量計算： 全画素位置ｘ＝（ｘ，ｙ）Ｔに対して、輝度Ｉ（ｘ，ｙ）を用いて以下の処理（ａ）−（ｂ）を行う。
（ａ）特徴量Ｃ（ｘ，ｙ）の計算
Ｉｘ＝（Ｉ（ｘ＋１，ｙ）−Ｉ（ｘ，ｙ）））／Δｘ
Ｉｙ＝（Ｉ（ｘ，ｙ＋１）−Ｉ（ｘ，ｙ）））／Δｙ
Ｍ（ｘ，ｙ）＝Σ（Ｉｘ，Ｉｙ）Ｔ（Ｉｘ，Ｉｙ）
ＭＷ＝ΣＷＭ（ｘ，ｙ）
Ｃ（ｘ，ｙ）＝Ｍｉｎ（Ｅｉｇｅｎ＿ｖａｌｕｅ（ＭＷ）） （１２）
ここにＭｉｎ（＊）は最小値を得ること、（Ｅｉｇｅｎ＿ｖａｌｕｅ（＊））は固有地を得ることをそれぞれ示す。また、Ｗは対象画像ｘを中心とした３×３画素の領域を示す。
（ｂ）推測画素が対応するかの判定
最小固有値が閾値λ以下か否かを判断し、閾値以上であれば、Ｃ（ｘ，ｙ）と、この値に対応する位置ｘを後段の処理に出力する。
（１−２）ソート： 送られて来る特徴量Ｃ（ｘ，ｙ）をパイプラインソート処理部に入れることによりＣ（ｘ，ｙ）の大きい順に対応する画像位置ｘαが「ソート済みメモリ」に格納される。
全画素の処理が終了したとき開始（ＥＮＢ，ｘα）がソート順（実施例ではα＝１，…，１０００）に対応点メモリに格納される。これにより次の画像から、この位置ｘαを起点として対応点の候補が計算できる。
（２）対応点計算および追跡：図６ 「対応点メモリ」にすでに登録されている時刻ｔの画像における特徴点位置ｘαを起点として、時刻ｔ＋Δｔの画像を対象に以下に示す特徴点候補の位置を計算し、特徴量を用いて対応する点か否かを判定する。以下に詳細を示す。
（２−１）勾配計算： 時刻ｔ＋Δｔと時刻ｔの画像Ｉ（ｘ，ｔ＋Δｔ），Ｉ（ｘ，ｔ）を用いて４段階（実施例の場合）の詳細度を持つ画像Ｉｄ（ｘｄ，ｔ），Ｉｄ（ｘｄ，ｔ＋Δｔ）を作成する。ここに添え字ｄは詳細度を示す。
詳細度ｄに対応した画像の画素位置ｘｄにおける勾配Ｇｘｄは、計算式（１３）に示す計算を行うことにより得られる。
Ｉｄ（ｘｄ，ｔ）＋Ｉｄ（ｘｄ，ｔ＋Δｔ））／Δｘ＝Ｇｘｄ
Ｉｄ（ｘｄ，ｔ）＋Ｉｄ（ｘｄ，ｔ＋Δｔ））／Δｙ＝Ｇｙｄ
（Ｇｘｄ，Ｇｙｄ）Ｔ＝Ｇｘｄ
Ｉｄ（ｘｄ，ｔ＋Δｔ）−Ｉｄ（ｘｄ，ｔ））／Δｔ＝ΔＩｄ （１３）
これを全ての画素および全ての詳細度に対して行い、結果を「勾配メモリ」に格納する。
（２−２）追跡： κ、ＦＴ＝０を処理ループのカウンタおよび「対応点メモリ」のアドレスとして以下の処理を、ＦＴ≦９９９，κ≦１０まで繰り返す。
「対応点メモリ」に格納されているκおよびＦＴで指定されたメモリ内の特徴点のＥＮＢ値が無効
であればＦＴ＝ＦＴ＋１としてメモリ内の次の特徴点を処理の対象とする。
有効であれば、以下の（ａ）から（ｂ）の処理を行う。
（ａ）移動ベクトル計算 ｄ＝１から４まで以下の計算を行い、各詳細度に対応する移動ベクトルｄｄを求める。
【数１２】
但し、Ｗｄは３×３の画素領域を示す。
（ｂ）誤対応検出／重み計算 以下の処理を詳細度が粗い順番（ｄ＝４，…，１）に行う。
【数１３】
ここにω（Ｗｄ）は
となる重みである。
計算結果Ｅｒｒｄと予め指定されている誤対応判定の閾値Ｅｒｒ＿Ｌｖｄとの比較を行う。
Ｅｒｒｄ＜Ｅｒｒ＿Ｌｖｄ （１６）
大きければ、ＥＮＢ＝０として詳細度の繰り返しを抜ける。
小さければ、以下の位置ｘκαｄを計算する。
ｘκαｄ ＝ｘκαｄ＋ｄｄ （１７）
詳細度ｄ＝ｄ−１として再度、式（１５）計算を行う。このとき、ｄ＝０であれば、ＥＮＢ＝１として以下の重みを計算する。
Ｗκα ＝ｃｏｓ（（Ｅｒｒ１／２Ｅｒｒ＿ＬＶ１）＊π／２＊ＥＮＢ （１８）
特徴点番号ＦＴ，κを「対応点メモリ」のアドレスとして、特徴点データ（ＥＮＢ，κ，Ｗκα，ｄκｄ，ｘκαｄ：ｄ＝１…４）を書き込む。
【００４９】
［３． 分配部１０４の動作の説明： 図７］
特徴点追跡部１０３の処理が終わった時点で作成される「対応点メモリ」に作成された特徴点追跡データ列から必要なデータを取り出し後段の処理に与える「追跡ベクトルメモリ」（図２，７）を作成する。このときＷκα＝１の個数が６以下の場合は、追跡ベクトルのＥＮＢ＝０とする。作成された「追跡ベクトルメモリ」の特徴ベクトルを１００点単位に分割して、３次元復元部１０５へ送る。全てを送り終えるとともにトグルスイッチを切り替え、書き込みと読み出しのメモリを反転する。
【００５０】
［４． 射影復元部１０５１の動作の説明］
以下に、本発明による射影復元の手順を示す。以下の説明では座標点は同次座標系を用いている。添え字κは画像番号１〜Ｍを示し、αは特徴点番号１〜Ｎを示す。また、表記Ｎ［・］は単位ベクトルへの正規化を表し、ｍａｘ［・］は最大値を選択することを示す。
入力：ｘκα，κ＝１，…，Ｍ， α＝１，…，Ｎ
収束判定の最投影誤差Ｅｍｉｎ
部分空間当てはめの収束判定定数ε
出力：Πκ，κ＝１，…，Ｍ， Ｘα，α＝１，…，Ｎ
［処理手順］
（１）射影的奥行をｚκα＝１と初期化する。
（２）ｚ１αｘ１α，ｚ２αｘ２α，…，ｚＭαｘＭαを縦に並べて３Ｍ次元ベクトルｐαとして単位ベクトルに正規化する。
ｐαＴ＝Ｎ［（ｚ１αｘ１αＴ，ｚ２αｘ２αＴ，…，ｚＭαｘＭαＴ）］ （１９）
（３）特徴点α＝１〜Ｎに対してｐαを求め、次の３Ｍ×Ｎ行列Ｐを作る。
Ｐ＝（ｐ１ｐ２…ｐＮ） （２０）
（４）行列Ｐを以下のように特異値分解する。
Ｐ＝Ｕｄｉａｇ（σ１，σ２，…）ＶＴ （２０）
行列Ｕの最初の４列ｕ１，ｕ２，ｕ３，ｕ４を求める。
（５）３×４の投影行列Πκを次のように計算する。
Πκ ＝ （ｕ１κ ｕ２κ ｕ３κ ｕ４κ）
（ただし、ｕ１κはｕｉの、３（κ−１）＋１，３（κ−１）＋２，３（κ−１）＋３成分を第１，２，３成分とする３次元ベクトルである。）
（６）次の計算をα＝１，…，Ｎに渡って計算する。
（ａ） 次のＣｋｉαを（κｉ）要素とするＭ×４行列Ｃαを計算する。
Ｃｋｉα＝（Ｎ［ｘκα］，ｕｉｋ） （２３）
（ｂ）次の４×４行列Ｄα＝（Ｄｉｊα）を計算する。
【数１４】
ただし、計算は行列が対称であるのでｉ＜ｊの（ｉ，ｊ）要素のみ計算し、ｉ＞ｊの（ｉ，ｊ）要素は（ｊ，ｉ）要素の値をコピーする。
（ｃ）行列Ｄαの固有値問題を解き、この最大固有値に対応する単位固有ベクトルμαを求め、これを用いて次の計算によりξαを計算し、
ξα＝±Ｎ［Ｃαμα］ （２５）
このとき、固有値の符号は次のようにする。
【数１５】
（ｄ）得られたξαから射影的奥行きｚκαを次のように計算する。
ｚκα＝ξκα／‖ｘκα‖
（ｅ）得られたｚκαを用いてベクトルＰαを再計算し、さらに正規化し前記処理手順（３）の行列Ｐを再計算する。
（ｆ）３次元位置Ｘα＝（Ｘκα）を以下のように計算する。
Ｘκα＝（ｐα，ｕκ）， ｋ＝１〜４ （２８）
（７）次のように最投影誤差Ｅを計算する。
【数１６】
ただし、Ｚ［・］は第４成分で他の成分を割ることを示す。
誤差の許容基準Ｅｍｉｎを用いてＥ＜Ｅｍｉｎであれば手続を終了。
（８）次の３Ｍ次元ベクトル
を計算する。（κ＝１〜４）。
【数１７】
（９）
にシュミットの直交化を施したものを
とする。
（１０）
を判定する。
条件が成立の場合は、
として前記処理手順（５）
不成立の場合は、
として前記処理手順（８）
【００５１】
［５． 自己校正部１０５２の動作の説明］
射影復元により得られる３次元形状は、元の３次元形状になんらかの射影変換が加わったものであり、真の形状とは異なる。以下の式は、任意のＨについて恒等的に成立する。
ΠκＸα＝ΠκＨＨ−１Ｘα （３１）
従って、前記の射影復元では、カメラモデルΠκとΠκＨの差異、およびＸαとＨ−１Ｘαとの差異がなく任意の値が得られる。射影復元した座標を元に、以下の処理により、正しいカメラモデルΠκと３次元点Ｘαを得るための射影変換Ｈを求める。
以下に本発明が示す自己校正部１０５２の処理手順を示す。
入力：各フレームの光軸点と焦点距離の近似
（ｕκ０，ｖκ０），ｆκ，κ＝１，…，Ｍ
投影行列Πκ，κ＝１，…，Ｍ．
出力：射影変換行列Ｈ
内部パラメータ行列Ｋκ，κ＝１，…，Ｍ．
［処理手順］
（１）次のように初期化する。
【数１８】
（２）カメラ内部パラメータＫκを以下として、Ｗκ＝１，γκ＝１と置く。
【数１９】
（３）次のようにＱκを定義する。
【数２０】
（４）以下の４×４×４×４テンソルＡ＝（Ａｉｊｋｌ）を計算する。
【数２１】
（５）テンソルＡは対称であるので、次の１０×１０の対称行列Ａｓｙｍに変換する。
（６）行列Ａｓｙｍの固有値問題を解き、最小固有値に対応する１０次元の単位固有ベクトルω＝（ω１ ω２…ω１０）Ｔを計算する。
（７）以下により仮のωを計算する。
【数２２】
（８）Ωの固有値問題を解き、固有値σ１≧σ２≧σ３≧σ４と、それに対応する単位固有ベクトルｕ１，ｕ２，ｕ３，ｕ４を計算する。
（９）数値的不確かさを排除すればΩがランク３の半正定値である必要があるので以下の計算によりつじつまのあったΩを再計算する。
（１０）射影変換Ｈを以下のように計算する。
（１１）次の計算をκ＝１，…，Ｍに渡って行う。
（ａ）以下からｅκ（ｉｊ）を計算し、それを用いたＦκを計算する。
【数２３】
【数２４】
（ｂ）ｃκ（３３）＞０かつＦκ＞０であれば以下によりσを計算する。
さらにＪκを次のように計算する。
そして、Ｋκ，γκを次のように更新する。
（ｃ）条件が不成立であればＪκ＝∞
（１２）メジアンを計算する。
（１３）Ｊｍｅｄ〜０であればＨ，Ｋκを返して終了。
（１４）
ならば以下を返して終了。
（１５）上記条件が成立しない場合は、次のように更新して処理手順（３）に戻る。
【００５２】
［６． ３次元点の補正部１０５３の動作の説明］
以下に、本発明が示す補正部１０５３による３次元点の補正を示す。
入力：射影復元座標Ｘα，α＝１，…，Ｎ
投影行列Πκ，κ＝１，…，Ｍ
射影変換行列Ｈ、内部パラメータ行列Ｋκ
出力：３次元座標（Ｘα，Ｙα，Ｚα）Ｔ，α＝１，…，Ｎ．
カメラ相対回転Ｒκ、カメラ相対位置ｔκ
内部パラメータ行列Ｋκ
［処理手順］
（１）次の計算によりＲκおよびｔκを求める。
（ａ）（Ｒκ′ｔκ）の計算
（ｂ）Ｒκ′の正規化Ｒ′の各列のベクトルを単位ベクトルとする。また、ｄｅｔＲ′＞０となるように各ベクトルの符号をあわせる。
（ｃ）Ｒκの計算
以下のように特異値分解を行う。
Ｒκ′＝ｄｉａｇ（λ１，λ２，λ３）ＶＴ
以下のように補正する。
Ｒ＝ＵＶＴ
（２）射影変換Ｈと射影復元座標Ｘα，α＝１，…，Ｎを用いて３次元復元値
を次の計算で得る。
（ａ）３次元点の暫定計算
【数２５】
（ｂ）補正：カメラ後方点の補正
【数２６】
以下の関係成立の可否判定
関係が不成立の場合は以下の計算を行う。
ｔκ←−ｔκ κ＝１，…，Ｍ
Ｘα＝−Ｘα，Ｙα＝−Ｙα，Ｚα＝−Ｚα．
【００５３】
［７． 統合部１０６の動作の説明］
並列処理されて前段の補正部１０５３から複数同時に出力される３次元復元点Ｘα、カメラパラメータＫκ、姿勢（Ｒκｔκ）の系列をカテゴリに分ける。またこのとき、３次元復元データに関しては特徴点の番号に従い一列に順序化する。カメラパラメータ、姿勢に関してはフレームの順に並べる。
【００５４】
本発明は、画像上の対象点を高速に（ビデオの撮像と同じ速さ）３次元復元できるため、コンピュータグラフィックにおけるモデルデータの自動作成、地図情報の自動作成、形状を認識できるので任意の形状のスクリーンへの投影に伴う歪み補正に適用可能となる。また、撮像カメラの位置姿勢が計測可能であるため、視角誘導や星を用いたナビゲーションなどにも応用することができる。
【００５５】
［他の用途への転用例の説明］
（ａ）複数カメラから撮像した映像の単一映像への高速な連続合成。
（ｂ）カメラ位置が得られることにより、複数の相対位置姿勢の検出（姿勢制御への応用）
【図面の簡単な説明】
【００５６】
【図１】３次元位置情報復元装置の一実施例の機能ブロック図である。（実施例１）
【図２】撮像データと特徴点列との対応を示す図である。
【図３】並列処理における時刻と特徴点の関係を示す図である。
【図４】画像蓄積部における輝度計算と画像イメージを示した図である。
【図５】画像データから特徴点の検出法を示した図である。
【図６】特徴点追跡部の対応点計算および追跡を説明する図である。
【図７】画像分配部の処理を説明する図である。
【図８】統合部の処理を説明する図である。
【図９】従来の３次元位置情報復元を説明する機能ブロックである。
【図１０】３次元点と撮像点との対応を説明する図である。
【図１１】３次元位置情報復元方法の一実施例を説明するフロー図である。
【図１２】３次元位置情報復元方法の一実施例を説明するフロー図である。
【図１３】３次元位置情報復元方法の一実施例を説明するフロー図である。
【図１４】３次元位置情報復元方法の一実施例を説明するフロー図である。
【図１５】３次元位置情報復元方法の一実施例を説明するフロー図である。
【図１６】３次元位置情報復元方法の一実施例を説明するフロー図である。
【図１７】３次元位置情報復元方法の一実施例を説明するフロー図である。
【図１８】３次元位置情報復元方法の一実施例を説明するフロー図である。
【図１９】３次元位置情報復元方法の一実施例を説明するフロー図である。
【図２０】３次元位置情報復元方法の一実施例を説明するフロー図である。
【符号の説明】
【００５７】
１０１…撮像装置、１０２…画像蓄積部、１０３…特徴点追跡部、１０３１…特徴点検出部、１０３２…対応点計算／追跡部、１０４…分配部、１０５…３次元復元部、１０５１…射影復元部、１０５２…自己校正部、１０５３…補正部、１０６…統合部。
【技術分野】
【０００１】
本発明は、複数の二次元画像から注目する特徴点の３次元位置を高速に復元してコンピュータグラフィックスにおけるポリゴンデータの自動生成や複合現実感などの分野に応用可能とする装置およびその方法に関するものである。
【背景技術】
【０００２】
図９は従来の３次元位置情報復元処理の概要構成を示す機能ブロック図である。９０１は撮像部、９０２は対応点検出部、９０３は疑似透視投影による因子分解部であり、対応点検出部９０２と因子分解部９０３とにおける処理ステップにより、擬似的に３次元点を得る。具体的には、撮像部９０１で撮像した複数の画像の対応点をとり、その対応点から３次元点を復元する。このとき、撮像部９０１を構成するカメラの内部パラメータが前もって分かっていることが必要である。
また、３次元復元処理は、カメラモデルを平行投影や弱透視投影（図１０（ｂ）に示す。）に限り、擬似的に３次元復元する手法である因子分解法あるいはこの改良型が主流である。このため復元精度が低い。
さらに、従来法は、画像数と特徴点数が増加した場合、因子分解法の処理に必要な画像中の特徴点列から作るモーメント行列の次数が急激に増加するので、処理メモリが急激に増加する手法である。
【０００３】
以下、画像をκ、その中の対応点をαとして従来技術の作用および動作を説明する。
特徴点ｘκαを元に特徴点ベクトルＰκαを以下のように作る。
Ｐκα＝（ｘ１αＴ，…ｘＭαＴ）Ｔ （１）
重心ベクトルＰＣを以下のように作成する。
【数１】
以下の計算を行いモーメント行列Ｗ（２Ｍ×Ｎ行列）を作る。
Ｐα′＝Ｐα−ＰＣ
Ｗ＝（Ｐ１′，…，ＰＮ′） （３）
Ｗを用い低下のように特異値分解を行い行列ＵとＶを求める。
Ｗ＝ＵＤＶＴ （４）
このＶを用いて、以下の式により擬似的な３次元位置Ｘαが求まる。
（Ｘ１Ｘ２…ＸＮ）＝（ｖ１ｖ２ｖ３）Ｔ （５）
但し、
Ｖ＝（ｖ１ｖ２ｖ３ｖ４） （６）
である。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
解決しようとする課題は、透視投影カメラモデル（図１０（ｂ））に基づいた擬似的でない正確な３次元位置情報復元装置および方法を提供することである。
また、従来法においては、平行投影のカメラモデルでも画像数Ｍと特徴点をＮとしたとき、このＭ×Ｎの値が増加することにより、速度低下および使用メモリの増加をきたしている。本発明が解決しようとする他の課題は、画像数や点数によらず一定のメモリで３次元復元問題が解けるような計算手法を実現する装置および方法を提供することにある。
すなわち、従来法は、カメラモデルを平行投影することによる計算法であるため３次元復元の精度が悪い。また、従来の因子分解法による計算処理法は、画像数Ｍと対象点Ｎに依存する。このため実用的なサイズでは計算が遅くなりメモリサイズの制限から実用的なサイズの点数の復元が行えなかった。このため、復元をビデオレートで行うためには処理装置の規模が大きくなり経済的な制約から実用的なものができていない。
因子分解法は、基本的に特異値分解を行うことに結びつくため、画像数Ｍと一画像当たりの特徴点数Ｎの積である２Ｍ×Ｎ行列の特異値問題を解く必要がある。点数が少ない場合は実用に耐えるが、１０枚の画像と１０００点の特徴点数を例に考えた場合、１０５要素数の行列を扱う必要がある。
また、復元データが疑似透視投影に基づくため、復元した３次元データの精度が悪い。特に、カメラモデルとして疑似透視投影を用いるため近距離での復元精度に問題がある。
従って、本発明は、カメラモデルとして平行投影を仮定して複数の連続する画像から３次元位置を得る従来の擬似的な３次元復元でなく、カメラモデルとして透視投影を仮定して正確な３次元復元を高速で行う装置および手法を提供することである。
【課題を解決するための手段】
【０００５】
以下の式（７）は、３次元位置Ｘαがκ画像の対応する２次元の点ｘκαに、カメラ投影行列（プロジェクションマトリクス）Πκを用いて変換される関係を示したものである。図１０に対応の模式図を示す。
【数２】
また、カメラ投影行列Πκは、カメラパラメータＫκカメラの位置ｔκおよびＲκを用いて以下のように表される。
Πκ＝Ｋκ（Ｒκｔκ） （８）
また、カメラパラメータＫκは以下である。
【数３】
この式（７）を満足する、未知のＸα，Πκを既知のｘκαを用いて求めることが３次元復元である。
このためには、まずこの式（７）を仮に満たすΠκ′とＸα′を求める。これを射影復元と呼ぶ。これには複数の画像間で対応する点ｘκαを縦に積んで作成した特徴点ベクトルＰ＝（ｘ１αＴ，…，ｘＭαＴ）Ｔがランク４の制約を持つことを利用して、実施例の射影復元に示す方法で射影復元する。
次に、これを正しいΠκとＸαに変換する。自己構成と呼ぶ。両者の間にはΠκ′＝ΠκＨ，Ｘα′＝Ｈ−１Ｘαの関係があり、このＨが射影復元の不定性である。これには、
Πκ＝Ｋκ（Ｒκｔκ） （１０）
が
Πκｄｉａｇ（１，１，１，０）ΠκＴ＝ＫκＫκＴ （１１）
となる性質を拘束条件に利用して、実施例の自己校正処理に示す方法でＨおよびＫκを得ることにより、正しい３次元復元を行う。
【０００６】
すなわち、上記課題を解決するため請求項１に係る３次元位置情報復元装置は、カメラにより撮像した複数の連続する二次元画像を元にして、撮像対象となる情景中の３次元位置を復元する装置であって、各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する手段と、連続する所定数の二次元画像を各特徴点毎に分配する手段と、各特徴点毎の連続する所定数の二次元画像について各特徴点毎の３次元位置Ｘα′とカメラの位置Πκ′を射影復元する射影復元部と、前記射影復元部により射影復元した３次元位置Ｘα′とカメラの位置Πκ′とを射影変換行列Ｈおよびカメラパラメータ行列により正しい３次元位置Ｘαとカメラの位置Πκとを求める自己校正部とを有することを特徴とするものである。
【０００７】
請求項２に係る３次元位置情報復元装置は、請求項１に記載のものにおいて、射影計算部において３次元位置Ｘα′を計算するに際して、画像番号κ（κ＝１，…，Ｍ）、特徴点番号α（α＝１，…，Ｎ）の画素点ｘκα、その単位ベクトルへの正規化をＮ［ｘκα］として
（１）射影的奥行をｚκα＝１と初期化し、
（２）ｚ１αｘ１α，ｚ２αｘ２α，…，ｚＭαｘＭαを縦に並べて３Ｍ次元ベクトルｐαとして以下の単位ベクトルに正規化し、
ｐαＴ＝Ｎ［（ｚ１αｘ１αＴ，ｚ２αｘ２αＴ，…，ｚＭαｘＭαＴ）］
（３）特徴点α＝１〜Ｎに対してＰαを求め、次の３Ｍ×Ｎ行列Ｐを作り、
Ｐ＝（ｐ１ｐ２…ｐＮ）
（４）行列Ｐを以下のように特異値分解し、
Ｐ＝Ｕｄｉａｇ（σ１，σ２，…）ＶＴ
行列Ｕの最初の４列ｕ１，ｕ２，ｕ３，ｕ４を求め、
（５）３×４の投影行列Πκを次のように計算し、
（ただし、ｕ１κはｕｉの、３（κ−１）＋１，３（κ−１）＋２，３（κ−１）＋３成分を第１，２，３成分とする３次元ベクトルである。）
（６）次の計算をα＝１，…，Ｎに渡って計算し、３次元位置Ｘαを計算する。
（ａ） 次のＣｋｉαを（κｉ）要素とするＭ×４行列Ｃαを計算し、
Ｃｋｉα＝（Ｎ［ｘκα］，ｕｉｋ）
（ｂ）次の４×４行列Ｄα＝（Ｄｉｊα）を計算し、
【数４】
（ただし、計算は行列が対称であるのでｉ＜ｊの（ｉ，ｊ）要素のみ計算し、ｉ＞ｊの（ｉ，ｊ）要素は（ｊ，ｉ）要素の値をコピーする。）
（ｃ）行列Ｄαの固有値問題を解き、この最大固有値に対応する単位固有ベクトルμαを求め、これを用いて次の計算によりξαを計算し、
ξα＝±Ｎ［Ｃαμα］
（このとき、固有値の符号は次のようにする。
【数５】
（ｄ）得られたξαから射影的奥行きｚκαを次のように計算し、
ｚκα＝ξκα／‖ｘκα‖
（ｅ）得られたｚκαを用いてベクトルＰαを再計算し、さらに正規化し前記（３）の行列Ｐを再計算し、
（ｆ）３次元位置Ｘα＝（Ｘκα）を以下のように計算する
Ｘκα＝（ｐα，ｕκ）， ｋ＝１〜４
ことを特徴とするものである。
【０００８】
請求項３に係る３次元位置情報復元装置は、請求項１に記載のものにおいて、自己校正部において正しい３次元位置Ｘαとカメラの位置Πκとを求めるに際して、射影復元部により射影復元した３次元位置Ｘα′とカメラの位置Πκ′とを射影変換行列Ｈおよびカメラパラメータ行列により正しい３次元位置Ｘαとカメラの位置Πκとを
Πκ′＝ΠκＨ
Ｘα′＝Ｈ−１Ｘα
より求めることを特徴とするものである。
【０００９】
請求項４に係る３次元位置情報復元装置は、請求項１に記載のものにおいて、射影計算部において３次元位置Ｘα′を計算するに際して、画像番号κ（κ＝１，…，Ｍ）、特徴点番号α（α＝１，…，Ｎ）の画素点ｘκα、その単位ベクトルへの正規化をＮ［ｘκα］として
（１）射影的奥行をｚκα＝１と初期化し、
（２）ｚ１αｘ１α，ｚ２αｘ２α，…，ｚＭαｘＭαを縦に並べて３Ｍ次元ベクトルｐαとして以下の単位ベクトルに正規化し、
ｐαＴ＝Ｎ［（ｚ１αｘ１αＴ，ｚ２αｘ２αＴ，…，ｚＭαｘＭαＴ）］
（３）特徴点α＝１〜Ｎに対してＰαを求め、次の３Ｍ×Ｎ行列Ｐを作り、
Ｐ＝（ｐ１ｐ２…ｐＮ）
（４）行列Ｐを以下のように特異値分解し、
Ｐ＝Ｕｄｉａｇ（σ１，σ２，…）ＶＴ
行列Ｕの最初の４列ｕ１，ｕ２，ｕ３，ｕ４を求め、
（５）３×４の投影行列Πκを次のように計算し、
（ただし、ｕ１κはｕｉの、３（κ−１）＋１，３（κ−１）＋２，３（κ−１）＋３成分を第１，２，３成分とする３次元ベクトルである。）
（６）次の計算をα＝１，…，Ｎに渡って計算し、３次元位置Ｘαを計算する。
（ａ） 次のＣｋｉαを（κｉ）要素とするＭ×４行列Ｃαを計算し、
Ｃｋｉα＝（Ｎ［ｘκα］，ｕｉｋ）
（ｂ）次の４×４行列Ｄα＝（Ｄｉｊα）を計算し、
【数６】
（ただし、計算は行列が対称であるのでｉ＜ｊの（ｉ，ｊ）要素のみ計算し、ｉ＞ｊの（ｉ，ｊ）要素は（ｊ，ｉ）要素の値をコピーする。）
（ｃ）行列Ｄαの固有値問題を解き、この最大固有値に対応する単位固有ベクトルμαを求め、これを用いて次の計算によりξαを計算し、
ξα＝±Ｎ［Ｃαμα］
（このとき、固有値の符号は次のようにする。
【数７】
（ｄ）得られたξαから射影的奥行きｚκαを次のように計算し、
ｚκα＝ξκα／‖ｘκα‖
（ｅ）得られたｚκαを用いてベクトルＰαを再計算し、さらに正規化し前記（３）の行列Ｐを再計算し、
（ｆ）３次元位置Ｘα＝（Ｘκα）を以下のように計算し、
Ｘκα＝（ｐα，ｕκ）， ｋ＝１〜４
自己校正部において正しい３次元位置Ｘαとカメラの位置Πκとを求めるに際して、
射影復元部により射影復元した３次元位置Ｘα′とカメラの位置Πκ′とを射影変換行列Ｈおよびカメラパラメータ行列により正しい３次元位置Ｘαとカメラの位置Πκとを
Πκ′＝ΠκＨ
Ｘα′＝Ｈ−１Ｘα
より求めることを特徴とするものである。
【００１０】
請求項５に係る３次元位置情報復元装置は、請求項１〜請求項４のいずれかに記載のものであって、射影復元部により求めた３次元位置Ｘα′について自己校正部において求めた数学的に正しいが物理的に偽の３次元位置情報を判定して除去する補正部とを有することを特徴とするものである。
【００１１】
請求項６に係る３次元位置情報復元装置は、請求項１に記載のものにおいて、各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する手段が、特徴点の追跡の誤対応の可能性に重み係数を用いて、所定の重み係数が所定数以下の場合に連続する所定数の二次元画像を各特徴点毎に分配することを特徴とするものである。
【００１２】
請求項７に係る３次元位置情報復元装置は、請求項１に記載のものにおいて、各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する手段が、時刻ｔ＋Δｔと時刻ｔの画像Ｉ（ｘ，ｔ＋Δｔ），Ｉ（ｘ，ｔ）を用いて所定数の段階の詳細度ｄを持つ画像Ｉｄ（ｘｄ，ｔ），Ｉｄ（ｘｄ，ｔ＋Δｔ）を作成し、詳細度が粗い順に、特徴点の追跡の誤対応の可能性に重み係数を計算し、当該重み係数を用いて、所定の重み係数が所定数以下の場合に連続する所定数の二次元画像を各特徴点毎に分配することを特徴とするものである。
【００１３】
請求項８に係る３次元位置情報復元装置は、請求項５に記載のものにおいて、射影復元部の射影復元処理と、自己校正部の自己校正処理と、補正部の判定除去処理とをパイプライン化することを特徴とするものである。
【００１４】
請求項９に係る３次元位置情報復元装置は、請求項１〜請求項８のいずれかに記載のものにおいて、各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する手段が、復元可能な特徴点数と画像数の数理的関係に基づき特徴点数の変化に対応して画像数を増減することを特徴とするものである。
【００１５】
請求項１０に係る３次元位置情報復元装置は、請求項１〜請求項９のいずれかに記載のものにおいて、射影復元部の射影復元処理と、自己校正部の自己校正処理と、補正部の判定除去処理とを複数の並列度により構成したことを特徴とするものである。
【００１６】
請求項１１に係る３次元位置情報復元装置は、カメラにより撮像した複数の連続する二次元画像を元にして、撮像対象となる情景中の３次元位置を復元する方法であって、各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する過程と、連続する所定数の二次元画像を各特徴点毎に分配する過程と、各特徴点毎の連続する所定数の二次元画像について各特徴点毎の３次元位置Ｘα′とカメラの位置Πκ′を射影復元する射影復元過程と、前記射影復元過程により射影復元した３次元位置Ｘα′とカメラの位置Πκ′とを射影変換行列Ｈおよびカメラパラメータ行列により正しい３次元位置Ｘαとカメラの位置Πκとを求める自己校正過程とを有することを特徴とするものである。
【００１７】
請求項１２に係る３次元位置情報復元方法は、請求項１１に記載のものにおいて、射影復元過程において３次元位置Ｘα′を計算するに際して、
画像番号κ（κ＝１，…，Ｍ）、特徴点番号α（α＝１，…，Ｎ）の画素点ｘκα、その単位ベクトルへの正規化をＮ［ｘκα］として
（１）射影的奥行をｚκα＝１と初期化し、
（２）ｚ１αｘ１α，ｚ２αｘ２α，…，ｚＭαｘＭαを縦に並べて３Ｍ次元ベクトルｐαとして以下の単位ベクトルに正規化し、
ｐαＴ＝Ｎ［（ｚ１αｘ１αＴ，ｚ２αｘ２αＴ，…，ｚＭαｘＭαＴ）］
（３）特徴点α＝１〜Ｎに対してＰαを求め、次の３Ｍ×Ｎ行列Ｐを作り、
Ｐ＝（ｐ１ｐ２…ｐＮ）
（４）行列Ｐを以下のように特異値分解し、
Ｐ＝Ｕｄｉａｇ（σ１，σ２，…）ＶＴ
行列Ｕの最初の４列ｕ１，ｕ２，ｕ３，ｕ４を求め、
（５）３×４の投影行列Πκを次のように計算し、
（ただし、ｕ１κはｕｉの、３（κ−１）＋１，３（κ−１）＋２，３（κ−１）＋３成分を第１，２，３成分とする３次元ベクトルである。）
（６）次の計算をα＝１，…，Ｎに渡って計算し、３次元位置Ｘαを計算する。
（ａ） 次のＣｋｉαを（κｉ）要素とするＭ×４行列Ｃαを計算し、
Ｃｋｉα＝（Ｎ［ｘκα］，ｕｉｋ）
（ｂ）次の４×４行列Ｄα＝（Ｄｉｊα）を計算し、
【数８】
（ただし、計算は行列が対称であるのでｉ＜ｊの（ｉ，ｊ）要素のみ計算し、ｉ＞ｊの（ｉ，ｊ）要素は（ｊ，ｉ）要素の値をコピーする。）
（ｃ）行列Ｄαの固有値問題を解き、この最大固有値に対応する単位固有ベクトルμαを求め、これを用いて次の計算によりξαを計算し、
ξα＝±Ｎ［Ｃαμα］
（このとき、固有値の符号は次のようにする。
【数９】
（ｄ）得られたξαから射影的奥行きｚκαを次のように計算し、
ｚκα＝ξκα／‖ｘκα‖
（ｅ）得られたｚκαを用いてベクトルＰαを再計算し、さらに正規化し前記（３）の行列Ｐを再計算し、
（ｆ）３次元位置Ｘα＝（Ｘκα）を以下のように計算する
Ｘκα＝（ｐα，ｕκ）， ｋ＝１〜４
ことを特徴とするものである。
【００１８】
請求項１３に係る３次元位置情報復元方法は、請求項１１に記載のものにおいて、自己校正過程において正しい３次元位置Ｘαとカメラの位置Πκとを求めるに際して、射影復元過程により射影復元した３次元位置Ｘα′とカメラの位置Πκ′とを射影変換行列Ｈおよびカメラパラメータ行列により正しい３次元位置Ｘαとカメラの位置Πκとを
Πκ′＝ΠκＨ
Ｘα′＝Ｈ−１Ｘα
より求めることを特徴とするものである。
【００１９】
請求項１４に係る３次元位置情報復元方法は、請求項１１に記載のものにおいて、射影復元過程において３次元位置Ｘα′を計算するに際して、
像番号κ（κ＝１，…，Ｍ）、特徴点番号α（α＝１，…，Ｎ）の画素点ｘκα、その単位ベクトルへの正規化をＮ［ｘκα］として
（１）射影的奥行をｚκα＝１と初期化し、
（２）ｚ１αｘ１α，ｚ２αｘ２α，…，ｚＭαｘＭαを縦に並べて３Ｍ次元ベクトルｐαとして以下の単位ベクトルに正規化し、
ｐαＴ＝Ｎ［（ｚ１αｘ１αＴ，ｚ２αｘ２αＴ，…，ｚＭαｘＭαＴ）］
（３）特徴点α＝１〜Ｎに対してＰαを求め、次の３Ｍ×Ｎ行列Ｐを作り、
Ｐ＝（ｐ１ｐ２…ｐＮ）
（４）行列Ｐを以下のように特異値分解し、
Ｐ＝Ｕｄｉａｇ（σ１，σ２，…）ＶＴ
行列Ｕの最初の４列ｕ１，ｕ２，ｕ３，ｕ４を求め、
（５）３×４の投影行列Πκを次のように計算し、
（ただし、ｕ１κはｕｉの、３（κ−１）＋１，３（κ−１）＋２，３（κ−１）＋３成分を第１，２，３成分とする３次元ベクトルである。）
（６）次の計算をα＝１，…，Ｎに渡って計算し、３次元位置Ｘαを計算する。
（ａ） 次のＣｋｉαを（κｉ）要素とするＭ×４行列Ｃαを計算し、
Ｃｋｉα＝（Ｎ［ｘκα］，ｕｉｋ）
（ｂ）次の４×４行列Ｄα＝（Ｄｉｊα）を計算し、
【数１０】
（ただし、計算は行列が対称であるのでｉ＜ｊの（ｉ，ｊ）要素のみ計算し、ｉ＞ｊの（ｉ，ｊ）要素は（ｊ，ｉ）要素の値をコピーする。）
（ｃ）行列Ｄαの固有値問題を解き、この最大固有値に対応する単位固有ベクトルμαを求め、これを用いて次の計算によりξαを計算し、
ξα＝±Ｎ［Ｃαμα］
（このとき、固有値の符号は次のようにする。
【数１１】
（ｄ）得られたξαから射影的奥行きｚκαを次のように計算し、
ｚκα＝ξκα／‖ｘκα‖
（ｅ）得られたｚκαを用いてベクトルＰαを再計算し、さらに正規化し前記（３）の行列Ｐを再計算し、
（ｆ）３次元位置Ｘα＝（Ｘκα）を以下のように計算し、
Ｘκα＝（ｐα，ｕκ）， ｋ＝１〜４
自己校正過程において正しい３次元位置Ｘαとカメラの位置Πκとを求めるに際して、
射影復元過程により射影復元した３次元位置Ｘα′とカメラの位置Πκ′とを射影変換行列Ｈおよびカメラパラメータ行列により正しい３次元位置Ｘαとカメラの位置Πκとを
Πκ′＝ΠκＨ
Ｘα′＝Ｈ−１Ｘα
より求めることを特徴とするものである。
【００２０】
請求項１５に係る３次元位置情報復元方法は、請求項１１〜請求項１４のいずれかに記載のものであって、射影復元過程により求めた３次元位置Ｘα′について自己校正過程において求めた数学的に正しいが物理的に偽の３次元位置情報を判定して除去する補正過程とを有することを特徴とするものである。
【００２１】
請求項１６に係る３次元位置情報復元方法は、請求項１１に記載のものにおいて、各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する過程が、特徴点の追跡の誤対応の可能性に重み係数を用いて、所定の重み係数が所定数以下の場合に連続する所定数の二次元画像を各特徴点毎に分配することを特徴とするものである。
【００２２】
請求項１７に係る３次元位置情報復元方法は、請求項１１に記載のものにおいて、各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する過程が、時刻ｔ＋Δｔと時刻ｔの画像Ｉ（ｘ，ｔ＋Δｔ），Ｉ（ｘ，ｔ）を用いて所定数の段階の詳細度ｄを持つ画像Ｉｄ（ｘｄ，ｔ），Ｉｄ（ｘｄ，ｔ＋Δｔ）を作成し、詳細度が粗い順に、特徴点の追跡の誤対応の可能性に重み係数を計算し、当該重み係数を用いて、所定の重み係数が所定数以下の場合に連続する所定数の二次元画像を各特徴点毎に分配することを特徴とするものである。
【００２３】
請求項１８に係る３次元位置情報復元方法は、請求項１５に記載のものにおいて、射影復元過程の射影復元処理と、自己校正過程の自己校正処理と、補正過程の判定除去処理とをパイプライン化することを特徴とするものである。
【００２４】
請求項１９に係る３次元位置情報復元方法は、請求項１１〜請求項１８のいずれかに記載のものにおいて、各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する過程が、復元可能な特徴点数と画像数の数理的関係に基づき特徴点数の変化に対応して画像数を増減することを特徴とするものである。
【００２５】
請求項２０に係る３次元位置情報復元方法は、射影復元過程の射影復元処理と、自己校正過程の自己校正処理と、補正過程の判定除去処理とを複数の並列度により構成することを特徴とするものである。
【発明の効果】
【００２６】
請求項１に係る３次元位置情報復元装置によると、複数の連続する二次元画像を元にして、撮像対象となる情景中の３次元位置情報を復元するに際し、３次元復元処理を「射影復元処理」と「自己校正処理」に分解して処理することにより、計算量の削減を図り３次元座標位置を高速かつ正確に復元することができる。
【００２７】
請求項２に係る３次元位置情報復元装置によると、射影復元において、特徴点数Ｎと画像の枚数Ｍが増大したとき、計算量および使用メモリ量がＮ×Ｍに依存して増加せず一定とすることができる。
【００２８】
請求項３に係る３次元位置情報復元装置によると、複数の対象とする画像を撮像したときのカメラの焦点距離や光軸のズレ等の光学的な特性が不明であり、また各々の画像で異なっていても３次元情報の復元が可能とすることができる。
【００２９】
請求項４に係る３次元位置情報復元装置によると、復元計算の過程において各々の撮像画像に対応したカメラの焦点距離や光軸のズレ量や、撮像カメラの空間的な位置および姿勢を、正確に推定できる。
【００３０】
請求項５に係る３次元位置情報復元装置によると、３次元復元処理が数学的に正しいが実際の３次元情報と異なる偽の３次元復元情報を除去することができる。
【００３１】
請求項６に係る３次元位置情報復元装置によると、誤対応の可能性に重み係数を用いて、誤対応の判定誤差を低減することができる。
【００３２】
請求項７に係る３次元位置情報復元装置によると、特徴点の追跡処理において詳細度を用いて誤対応の発生を低減することができる。
【００３３】
請求項８に係る３次元位置情報復元装置によると、各処理をパイプライン化して行うことができる。
【００３４】
請求項９に係る３次元位置情報復元装置によると、復元可能特徴点数と画像数の数理的関係に基づき特徴点数の変化に対応して画像数を増減可能にすることができる。
【００３５】
請求項１０に係る３次元位置情報復元装置によると、特徴点の増加に対する処理速度の低下を、同一の処理の並列度を増やすことで、対応可能とすることができる。
【００３６】
請求項１１に係る３次元位置情報復元方法によると、複数の連続する二次元画像を元にして、撮像対象となる情景中の３次元位置情報を復元するに際し、３次元復元処理を「射影復元処理」と「自己校正処理」に分解して処理することにより、計算量の削減を図り３次元座標位置を高速かつ正確に復元することができる。
【００３７】
請求項１２に係る３次元位置情報復元方法によると、射影復元において、特徴点数Ｎと画像の枚数Ｍが増大したとき、計算量および使用メモリ量がＮ×Ｍに依存して増加せず一定とすることができる。
【００３８】
請求項１３に係る３次元位置情報復元方法によると、複数の対象とする画像を撮像したときのカメラの焦点距離や光軸のズレ等の光学的な特性が不明であり、また各々の画像で異なっていても３次元情報の復元が可能とすることができる。
【００３９】
請求項１４に係る３次元位置情報復元方法によると、復元計算の過程において各々の撮像画像に対応したカメラの焦点距離や光軸のズレ量や、撮像カメラの空間的な位置および姿勢を、正確に推定できる。
【００４０】
請求項１５に係る３次元位置情報復元方法によると、３次元復元処理が数学的に正しいが実際の３次元情報と異なる偽の３次元復元情報を除去することができる。
【００４１】
請求項１６に係る３次元位置情報復元方法によると、誤対応の可能性に重み係数を用いて、誤対応の判定誤差を低減することができる。
【００４２】
請求項１７に係る３次元位置情報復元方法によると、特徴点の追跡処理において詳細度を用いて誤対応の発生を低減することができる。
【００４３】
請求項１８に係る３次元位置情報復元方法によると、各処理をパイプライン化して行うことができる。
【００４４】
請求項１９に係る３次元位置情報復元方法によると、復元可能特徴点数と画像数の数理的関係に基づき特徴点数の変化に対応して画像数を増減可能にすることができる。
【００４５】
請求項２０に係る３次元位置情報復元方法によると、特徴点の増加に対する処理速度の低下を、同一の処理の並列度を増やすことで、対応可能とすることができる。
【実施例１】
【００４６】
本発明の実施例を説明する全体の機能ブロック図を図１に、その構成各部の詳細および情報受け渡しを説明する図を図２〜図８に示す。また、そのフロー図を図１１〜図２０に示す。以下、この図に基づき、作用実施例の詳細な説明を行う。
図１は、本発明の一実施例の構成を示したものである。連続するビデオ画像を入力として検出した特徴点の３次元復元およびカメラ位置の推定を行う実施例を示す。実施例では、特徴点を１０００点、追跡画像数を１０枚として、対応する画像中の特徴点（二次元）を３次元に復元処理する例を示す。処理対象の特徴点数は、並列処理する処理に応じて増加可能であり、画像数は要求精度が高い場合に対応して増加可能である。
図２は、図１の実施例における処理の詳細を示し、撮像データと特徴点列との対応を表したものである。Ｉ（ｘ，ｔ＋Δｔ）に撮像した画像と一フレーム前の画像Ｉ（ｘ，ｔ）間で特徴点に対応がとれる可能性があるもので図示されている。Ｗκα＝０が６個以上ある特徴点データ列は、無効として
とされることを示す。
図３は、図１の実施例における処理の詳細を示し、並列処理におけるフレーム数と特徴点の関係を示したものである。
図４は、図１の実施例における処理の詳細を示し、画像蓄積部における輝度計算と画像イメージを示したものである。
図５は、図１の実施例における処理詳細を示し、画像データから特徴点の検出法を示したものである。
図６は、図１の実施例における処理の詳細を示し、対応点の検出および判定を示したものであり、二枚の画像間の想定対応点を比較して誤対応か否かを判定する。
図７は、図１の実施例における処理の詳細を示し、画像分配部の処理を示したものであり、図の処理例では、１０画像追跡した１０００点の特徴点を１００点ずつ並列処理部へ分配することを示す。
図８は、図１の実施例における処理の詳細を示し、並列処理した復元点およびカメラ位置姿勢をシーケンシャルに整理して出力する処理を示す。
図１において、１０１は撮像装置、１０２は画像蓄積部、１０３は特徴点追跡部、１０４は分配部、１０５は３次元復元部、１０６は統合部である。
特徴点追跡部１０３は、特徴点検出部１０３１、対応点計算／追跡部１０３２を備える。
また、３次元復元部１０５は、射影復元部１０５１ｉ（ｉ＝１〜Ｐ）、自己校正部１０５２ｉ（ｉ＝１〜Ｐ）、補正部１０５３ｉ（ｉ＝１〜Ｐ）に細分され、並列処理の対象として一つの処理部となる。
取り扱う特徴点数が増加した場合、この同一の並列処理部（３次元復元部１０５）を増やすことにより復元性能の増加を図る。
処理の概要を図１に従い説明する。
撮像部１０１で連続したフレームの画像が取られ、画像蓄積部１０２においてグレースケールに変換される。
特徴点検出部１０３１において、例えば１０フレーム間隔で、特徴点として最も良好な性質を持つ複数の画素を特徴点として選択する。以後この特徴点が１０枚の画像にわたり追跡点として追跡される。
この複数の追跡ベクトルが、分配部１０４において並列処理の単位に分解され、３次元復元部１０５の入力となる特徴点の３次元位置Ｘα、フレームκにおけるカメラパラメータＫκおよびカメラの位置姿勢（Ｒκｔκ）を得る。
統合部１０６において複数の３次元復元部１０５からの出力を、一連の順序に従い再配置する。
以下に各機能ブロックの作用、動作の詳細な説明を行う。
【００４７】
［１． 画像蓄積の動作の説明：図４］
カメラで得た画像を輝度値によるモノクロ画像に変換する。このときフレーム番号κを連番で割り当てる。
【００４８】
［２． 特徴点追跡部１０３の動作の説明：図５，６］
３次元復元を行うために必要な複数の画像間で特定の特徴点がどのように移動したかの対応付けを行う処理を行う。
この特徴点追跡部１０３は、追跡点を決める「特徴点の検出」処理を行う特徴点検出部１０３１と、この特徴点を開始点として二枚の連続する画像間の該当特徴点の追跡を行う「対応点計算および追跡」処理を行う対応点計算／追跡部１０３２からなる。
（１）特徴点検出：図５ 追跡を開始する元となる追跡開始点（画素位置）は手動あるいは自動で発生する。図５の例では、この処理の実行される間隔は、画像枚数例えば１０枚毎としている。自動で特徴点を検出する場合は、「特徴量計算」、「特徴量ソート」を経て、「対応点メモリ」に開始点が登録される。以後のフレームからは、この特徴点を追跡の開始点として連続した１０枚の画像（例）を追跡する。
（１−１）特徴量計算： 全画素位置ｘ＝（ｘ，ｙ）Ｔに対して、輝度Ｉ（ｘ，ｙ）を用いて以下の処理（ａ）−（ｂ）を行う。
（ａ）特徴量Ｃ（ｘ，ｙ）の計算
Ｉｘ＝（Ｉ（ｘ＋１，ｙ）−Ｉ（ｘ，ｙ）））／Δｘ
Ｉｙ＝（Ｉ（ｘ，ｙ＋１）−Ｉ（ｘ，ｙ）））／Δｙ
Ｍ（ｘ，ｙ）＝Σ（Ｉｘ，Ｉｙ）Ｔ（Ｉｘ，Ｉｙ）
ＭＷ＝ΣＷＭ（ｘ，ｙ）
Ｃ（ｘ，ｙ）＝Ｍｉｎ（Ｅｉｇｅｎ＿ｖａｌｕｅ（ＭＷ）） （１２）
ここにＭｉｎ（＊）は最小値を得ること、（Ｅｉｇｅｎ＿ｖａｌｕｅ（＊））は固有地を得ることをそれぞれ示す。また、Ｗは対象画像ｘを中心とした３×３画素の領域を示す。
（ｂ）推測画素が対応するかの判定
最小固有値が閾値λ以下か否かを判断し、閾値以上であれば、Ｃ（ｘ，ｙ）と、この値に対応する位置ｘを後段の処理に出力する。
（１−２）ソート： 送られて来る特徴量Ｃ（ｘ，ｙ）をパイプラインソート処理部に入れることによりＣ（ｘ，ｙ）の大きい順に対応する画像位置ｘαが「ソート済みメモリ」に格納される。
全画素の処理が終了したとき開始（ＥＮＢ，ｘα）がソート順（実施例ではα＝１，…，１０００）に対応点メモリに格納される。これにより次の画像から、この位置ｘαを起点として対応点の候補が計算できる。
（２）対応点計算および追跡：図６ 「対応点メモリ」にすでに登録されている時刻ｔの画像における特徴点位置ｘαを起点として、時刻ｔ＋Δｔの画像を対象に以下に示す特徴点候補の位置を計算し、特徴量を用いて対応する点か否かを判定する。以下に詳細を示す。
（２−１）勾配計算： 時刻ｔ＋Δｔと時刻ｔの画像Ｉ（ｘ，ｔ＋Δｔ），Ｉ（ｘ，ｔ）を用いて４段階（実施例の場合）の詳細度を持つ画像Ｉｄ（ｘｄ，ｔ），Ｉｄ（ｘｄ，ｔ＋Δｔ）を作成する。ここに添え字ｄは詳細度を示す。
詳細度ｄに対応した画像の画素位置ｘｄにおける勾配Ｇｘｄは、計算式（１３）に示す計算を行うことにより得られる。
Ｉｄ（ｘｄ，ｔ）＋Ｉｄ（ｘｄ，ｔ＋Δｔ））／Δｘ＝Ｇｘｄ
Ｉｄ（ｘｄ，ｔ）＋Ｉｄ（ｘｄ，ｔ＋Δｔ））／Δｙ＝Ｇｙｄ
（Ｇｘｄ，Ｇｙｄ）Ｔ＝Ｇｘｄ
Ｉｄ（ｘｄ，ｔ＋Δｔ）−Ｉｄ（ｘｄ，ｔ））／Δｔ＝ΔＩｄ （１３）
これを全ての画素および全ての詳細度に対して行い、結果を「勾配メモリ」に格納する。
（２−２）追跡： κ、ＦＴ＝０を処理ループのカウンタおよび「対応点メモリ」のアドレスとして以下の処理を、ＦＴ≦９９９，κ≦１０まで繰り返す。
「対応点メモリ」に格納されているκおよびＦＴで指定されたメモリ内の特徴点のＥＮＢ値が無効
であればＦＴ＝ＦＴ＋１としてメモリ内の次の特徴点を処理の対象とする。
有効であれば、以下の（ａ）から（ｂ）の処理を行う。
（ａ）移動ベクトル計算 ｄ＝１から４まで以下の計算を行い、各詳細度に対応する移動ベクトルｄｄを求める。
【数１２】
但し、Ｗｄは３×３の画素領域を示す。
（ｂ）誤対応検出／重み計算 以下の処理を詳細度が粗い順番（ｄ＝４，…，１）に行う。
【数１３】
ここにω（Ｗｄ）は
となる重みである。
計算結果Ｅｒｒｄと予め指定されている誤対応判定の閾値Ｅｒｒ＿Ｌｖｄとの比較を行う。
Ｅｒｒｄ＜Ｅｒｒ＿Ｌｖｄ （１６）
大きければ、ＥＮＢ＝０として詳細度の繰り返しを抜ける。
小さければ、以下の位置ｘκαｄを計算する。
ｘκαｄ ＝ｘκαｄ＋ｄｄ （１７）
詳細度ｄ＝ｄ−１として再度、式（１５）計算を行う。このとき、ｄ＝０であれば、ＥＮＢ＝１として以下の重みを計算する。
Ｗκα ＝ｃｏｓ（（Ｅｒｒ１／２Ｅｒｒ＿ＬＶ１）＊π／２＊ＥＮＢ （１８）
特徴点番号ＦＴ，κを「対応点メモリ」のアドレスとして、特徴点データ（ＥＮＢ，κ，Ｗκα，ｄκｄ，ｘκαｄ：ｄ＝１…４）を書き込む。
【００４９】
［３． 分配部１０４の動作の説明： 図７］
特徴点追跡部１０３の処理が終わった時点で作成される「対応点メモリ」に作成された特徴点追跡データ列から必要なデータを取り出し後段の処理に与える「追跡ベクトルメモリ」（図２，７）を作成する。このときＷκα＝１の個数が６以下の場合は、追跡ベクトルのＥＮＢ＝０とする。作成された「追跡ベクトルメモリ」の特徴ベクトルを１００点単位に分割して、３次元復元部１０５へ送る。全てを送り終えるとともにトグルスイッチを切り替え、書き込みと読み出しのメモリを反転する。
【００５０】
［４． 射影復元部１０５１の動作の説明］
以下に、本発明による射影復元の手順を示す。以下の説明では座標点は同次座標系を用いている。添え字κは画像番号１〜Ｍを示し、αは特徴点番号１〜Ｎを示す。また、表記Ｎ［・］は単位ベクトルへの正規化を表し、ｍａｘ［・］は最大値を選択することを示す。
入力：ｘκα，κ＝１，…，Ｍ， α＝１，…，Ｎ
収束判定の最投影誤差Ｅｍｉｎ
部分空間当てはめの収束判定定数ε
出力：Πκ，κ＝１，…，Ｍ， Ｘα，α＝１，…，Ｎ
［処理手順］
（１）射影的奥行をｚκα＝１と初期化する。
（２）ｚ１αｘ１α，ｚ２αｘ２α，…，ｚＭαｘＭαを縦に並べて３Ｍ次元ベクトルｐαとして単位ベクトルに正規化する。
ｐαＴ＝Ｎ［（ｚ１αｘ１αＴ，ｚ２αｘ２αＴ，…，ｚＭαｘＭαＴ）］ （１９）
（３）特徴点α＝１〜Ｎに対してｐαを求め、次の３Ｍ×Ｎ行列Ｐを作る。
Ｐ＝（ｐ１ｐ２…ｐＮ） （２０）
（４）行列Ｐを以下のように特異値分解する。
Ｐ＝Ｕｄｉａｇ（σ１，σ２，…）ＶＴ （２０）
行列Ｕの最初の４列ｕ１，ｕ２，ｕ３，ｕ４を求める。
（５）３×４の投影行列Πκを次のように計算する。
Πκ ＝ （ｕ１κ ｕ２κ ｕ３κ ｕ４κ）
（ただし、ｕ１κはｕｉの、３（κ−１）＋１，３（κ−１）＋２，３（κ−１）＋３成分を第１，２，３成分とする３次元ベクトルである。）
（６）次の計算をα＝１，…，Ｎに渡って計算する。
（ａ） 次のＣｋｉαを（κｉ）要素とするＭ×４行列Ｃαを計算する。
Ｃｋｉα＝（Ｎ［ｘκα］，ｕｉｋ） （２３）
（ｂ）次の４×４行列Ｄα＝（Ｄｉｊα）を計算する。
【数１４】
ただし、計算は行列が対称であるのでｉ＜ｊの（ｉ，ｊ）要素のみ計算し、ｉ＞ｊの（ｉ，ｊ）要素は（ｊ，ｉ）要素の値をコピーする。
（ｃ）行列Ｄαの固有値問題を解き、この最大固有値に対応する単位固有ベクトルμαを求め、これを用いて次の計算によりξαを計算し、
ξα＝±Ｎ［Ｃαμα］ （２５）
このとき、固有値の符号は次のようにする。
【数１５】
（ｄ）得られたξαから射影的奥行きｚκαを次のように計算する。
ｚκα＝ξκα／‖ｘκα‖
（ｅ）得られたｚκαを用いてベクトルＰαを再計算し、さらに正規化し前記処理手順（３）の行列Ｐを再計算する。
（ｆ）３次元位置Ｘα＝（Ｘκα）を以下のように計算する。
Ｘκα＝（ｐα，ｕκ）， ｋ＝１〜４ （２８）
（７）次のように最投影誤差Ｅを計算する。
【数１６】
ただし、Ｚ［・］は第４成分で他の成分を割ることを示す。
誤差の許容基準Ｅｍｉｎを用いてＥ＜Ｅｍｉｎであれば手続を終了。
（８）次の３Ｍ次元ベクトル
を計算する。（κ＝１〜４）。
【数１７】
（９）
にシュミットの直交化を施したものを
とする。
（１０）
を判定する。
条件が成立の場合は、
として前記処理手順（５）
不成立の場合は、
として前記処理手順（８）
【００５１】
［５． 自己校正部１０５２の動作の説明］
射影復元により得られる３次元形状は、元の３次元形状になんらかの射影変換が加わったものであり、真の形状とは異なる。以下の式は、任意のＨについて恒等的に成立する。
ΠκＸα＝ΠκＨＨ−１Ｘα （３１）
従って、前記の射影復元では、カメラモデルΠκとΠκＨの差異、およびＸαとＨ−１Ｘαとの差異がなく任意の値が得られる。射影復元した座標を元に、以下の処理により、正しいカメラモデルΠκと３次元点Ｘαを得るための射影変換Ｈを求める。
以下に本発明が示す自己校正部１０５２の処理手順を示す。
入力：各フレームの光軸点と焦点距離の近似
（ｕκ０，ｖκ０），ｆκ，κ＝１，…，Ｍ
投影行列Πκ，κ＝１，…，Ｍ．
出力：射影変換行列Ｈ
内部パラメータ行列Ｋκ，κ＝１，…，Ｍ．
［処理手順］
（１）次のように初期化する。
【数１８】
（２）カメラ内部パラメータＫκを以下として、Ｗκ＝１，γκ＝１と置く。
【数１９】
（３）次のようにＱκを定義する。
【数２０】
（４）以下の４×４×４×４テンソルＡ＝（Ａｉｊｋｌ）を計算する。
【数２１】
（５）テンソルＡは対称であるので、次の１０×１０の対称行列Ａｓｙｍに変換する。
（６）行列Ａｓｙｍの固有値問題を解き、最小固有値に対応する１０次元の単位固有ベクトルω＝（ω１ ω２…ω１０）Ｔを計算する。
（７）以下により仮のωを計算する。
【数２２】
（８）Ωの固有値問題を解き、固有値σ１≧σ２≧σ３≧σ４と、それに対応する単位固有ベクトルｕ１，ｕ２，ｕ３，ｕ４を計算する。
（９）数値的不確かさを排除すればΩがランク３の半正定値である必要があるので以下の計算によりつじつまのあったΩを再計算する。
（１０）射影変換Ｈを以下のように計算する。
（１１）次の計算をκ＝１，…，Ｍに渡って行う。
（ａ）以下からｅκ（ｉｊ）を計算し、それを用いたＦκを計算する。
【数２３】
【数２４】
（ｂ）ｃκ（３３）＞０かつＦκ＞０であれば以下によりσを計算する。
さらにＪκを次のように計算する。
そして、Ｋκ，γκを次のように更新する。
（ｃ）条件が不成立であればＪκ＝∞
（１２）メジアンを計算する。
（１３）Ｊｍｅｄ〜０であればＨ，Ｋκを返して終了。
（１４）
ならば以下を返して終了。
（１５）上記条件が成立しない場合は、次のように更新して処理手順（３）に戻る。
【００５２】
［６． ３次元点の補正部１０５３の動作の説明］
以下に、本発明が示す補正部１０５３による３次元点の補正を示す。
入力：射影復元座標Ｘα，α＝１，…，Ｎ
投影行列Πκ，κ＝１，…，Ｍ
射影変換行列Ｈ、内部パラメータ行列Ｋκ
出力：３次元座標（Ｘα，Ｙα，Ｚα）Ｔ，α＝１，…，Ｎ．
カメラ相対回転Ｒκ、カメラ相対位置ｔκ
内部パラメータ行列Ｋκ
［処理手順］
（１）次の計算によりＲκおよびｔκを求める。
（ａ）（Ｒκ′ｔκ）の計算
（ｂ）Ｒκ′の正規化Ｒ′の各列のベクトルを単位ベクトルとする。また、ｄｅｔＲ′＞０となるように各ベクトルの符号をあわせる。
（ｃ）Ｒκの計算
以下のように特異値分解を行う。
Ｒκ′＝ｄｉａｇ（λ１，λ２，λ３）ＶＴ
以下のように補正する。
Ｒ＝ＵＶＴ
（２）射影変換Ｈと射影復元座標Ｘα，α＝１，…，Ｎを用いて３次元復元値
を次の計算で得る。
（ａ）３次元点の暫定計算
【数２５】
（ｂ）補正：カメラ後方点の補正
【数２６】
以下の関係成立の可否判定
関係が不成立の場合は以下の計算を行う。
ｔκ←−ｔκ κ＝１，…，Ｍ
Ｘα＝−Ｘα，Ｙα＝−Ｙα，Ｚα＝−Ｚα．
【００５３】
［７． 統合部１０６の動作の説明］
並列処理されて前段の補正部１０５３から複数同時に出力される３次元復元点Ｘα、カメラパラメータＫκ、姿勢（Ｒκｔκ）の系列をカテゴリに分ける。またこのとき、３次元復元データに関しては特徴点の番号に従い一列に順序化する。カメラパラメータ、姿勢に関してはフレームの順に並べる。
【００５４】
本発明は、画像上の対象点を高速に（ビデオの撮像と同じ速さ）３次元復元できるため、コンピュータグラフィックにおけるモデルデータの自動作成、地図情報の自動作成、形状を認識できるので任意の形状のスクリーンへの投影に伴う歪み補正に適用可能となる。また、撮像カメラの位置姿勢が計測可能であるため、視角誘導や星を用いたナビゲーションなどにも応用することができる。
【００５５】
［他の用途への転用例の説明］
（ａ）複数カメラから撮像した映像の単一映像への高速な連続合成。
（ｂ）カメラ位置が得られることにより、複数の相対位置姿勢の検出（姿勢制御への応用）
【図面の簡単な説明】
【００５６】
【図１】３次元位置情報復元装置の一実施例の機能ブロック図である。（実施例１）
【図２】撮像データと特徴点列との対応を示す図である。
【図３】並列処理における時刻と特徴点の関係を示す図である。
【図４】画像蓄積部における輝度計算と画像イメージを示した図である。
【図５】画像データから特徴点の検出法を示した図である。
【図６】特徴点追跡部の対応点計算および追跡を説明する図である。
【図７】画像分配部の処理を説明する図である。
【図８】統合部の処理を説明する図である。
【図９】従来の３次元位置情報復元を説明する機能ブロックである。
【図１０】３次元点と撮像点との対応を説明する図である。
【図１１】３次元位置情報復元方法の一実施例を説明するフロー図である。
【図１２】３次元位置情報復元方法の一実施例を説明するフロー図である。
【図１３】３次元位置情報復元方法の一実施例を説明するフロー図である。
【図１４】３次元位置情報復元方法の一実施例を説明するフロー図である。
【図１５】３次元位置情報復元方法の一実施例を説明するフロー図である。
【図１６】３次元位置情報復元方法の一実施例を説明するフロー図である。
【図１７】３次元位置情報復元方法の一実施例を説明するフロー図である。
【図１８】３次元位置情報復元方法の一実施例を説明するフロー図である。
【図１９】３次元位置情報復元方法の一実施例を説明するフロー図である。
【図２０】３次元位置情報復元方法の一実施例を説明するフロー図である。
【符号の説明】
【００５７】
１０１…撮像装置、１０２…画像蓄積部、１０３…特徴点追跡部、１０３１…特徴点検出部、１０３２…対応点計算／追跡部、１０４…分配部、１０５…３次元復元部、１０５１…射影復元部、１０５２…自己校正部、１０５３…補正部、１０６…統合部。
【特許請求の範囲】
【請求項１】
カメラにより撮像した複数の連続する二次元画像を元にして、撮像対象となる情景中の３次元位置を復元する装置であって、
各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する手段と、
連続する所定数の二次元画像を各特徴点毎に分配する手段と、
各特徴点毎の連続する所定数の二次元画像について各特徴点毎の３次元位置Ｘα′とカメラの位置Πκ′を射影復元する射影復元部と、
前記射影復元部により射影復元した３次元位置Ｘα′とカメラの位置Πκ′とを射影変換行列Ｈおよびカメラパラメータ行列により正しい３次元位置Ｘαとカメラの位置Πκとを求める自己校正部とを有することを特徴とする３次元位置情報復元装置。
【請求項２】
射影復元部において３次元位置Ｘα′を計算するに際して、
画像番号κ（κ＝１，…，Ｍ）、特徴点番号α（α＝１，…，Ｎ）の画素点ｘκα、その単位ベクトルへの正規化をＮ［ｘκα］として
（１）射影的奥行をｚκα＝１と初期化し、
（２）ｚ１αｘ１α，ｚ２αｘ２α，…，ｚＭαｘＭαを縦に並べて３Ｍ次元ベクトルｐαとして以下の単位ベクトルに正規化し、
ｐαＴ＝Ｎ［（ｚ１αｘ１αＴ，ｚ２αｘ２αＴ，…，ｚＭαｘＭαＴ）］
（３）特徴点α＝１〜Ｎに対してＰαを求め、次の３Ｍ×Ｎ行列Ｐを作り、
Ｐ＝（ｐ１ｐ２…ｐＮ）
（４）行列Ｐを以下のように特異値分解し、
Ｐ＝Ｕｄｉａｇ（σ１，σ２，…）ＶＴ
行列Ｕの最初の４列ｕ１，ｕ２，ｕ３，ｕ４を求め、
（５）３×４の投影行列Πκを次のように計算し、
Πκ ＝ （ｕ１κ ｕ２κ ｕ３κ ｕ４κ）
（ただし、ｕ１κはｕｉの、３（κ−１）＋１，３（κ−１）＋２，３（κ−１）＋３成分を第１，２，３成分とする３次元ベクトルである。）
（６）次の計算をα＝１，…，Ｎに渡って計算し、３次元位置Ｘαを計算する。
（ａ） 次のＣｋｉαを（κｉ）要素とするＭ×４行列Ｃαを計算し、
Ｃｋｉα＝（Ｎ［ｘκα］，ｕｉｋ）
（ｂ）次の４×４行列Ｄα＝（Ｄｉｊα）を計算し、
【数１】
（ただし、計算は行列が対称であるのでｉ＜ｊの（ｉ，ｊ）要素のみ計算し、ｉ＞ｊの（ｉ，ｊ）要素は（ｊ，ｉ）要素の値をコピーする。）
（ｃ）行列Ｄαの固有値問題を解き、この最大固有値に対応する単位固有ベクトルμαを求め、これを用いて次の計算によりξαを計算し、
ξα＝±Ｎ［Ｃαμα］
（このとき、固有値の符号は次のようにする。
【数２】
（ｄ）得られたξαから射影的奥行きｚκαを次のように計算し、
ｚκα＝ξκα／‖ｘκα‖
（ｅ）得られたｚκαを用いてベクトルＰαを再計算し、さらに正規化し前記（３）の行列Ｐを再計算し、
（ｆ）３次元位置Ｘα＝（Ｘκα）を以下のように計算する
Ｘκα＝（ｐα，ｕκ）， ｋ＝１〜４
ことを特徴とする請求項１に記載の３次元位置情報復元装置。
【請求項３】
自己校正部において正しい３次元位置Ｘαとカメラの位置Πκとを求めるに際して、
射影復元部により射影復元した３次元位置Ｘα′とカメラの位置Πκ′とを射影変換行列Ｈおよびカメラパラメータ行列により正しい３次元位置Ｘαとカメラの位置Πκとを
Πκ′＝ΠκＨ
Ｘα′＝Ｈ−１Ｘα
より求めることを特徴とする請求項１に記載の３次元位置情報復元装置。
【請求項４】
射影復元部において３次元位置Ｘα′を計算するに際して、
画像番号κ（κ＝１，…，Ｍ）、特徴点番号α（α＝１，…，Ｎ）の画素点ｘκα、その単位ベクトルへの正規化をＮ［ｘκα］として
（１）射影的奥行をｚκα＝１と初期化し、
（２）ｚ１αｘ１α，ｚ２αｘ２α，…，ｚＭαｘＭαを縦に並べて３Ｍ次元ベクトルｐαとして以下の単位ベクトルに正規化し、
ｐαＴ＝Ｎ［（ｚ１αｘ１αＴ，ｚ２αｘ２αＴ，…，ｚＭαｘＭαＴ）］
（３）特徴点α＝１〜Ｎに対してＰαを求め、次の３Ｍ×Ｎ行列Ｐを作り、
Ｐ＝（ｐ１ｐ２…ｐＮ）
（４）行列Ｐを以下のように特異値分解し、
Ｐ＝Ｕｄｉａｇ（σ１，σ２，…）ＶＴ
行列Ｕの最初の４列ｕ１，ｕ２，ｕ３，ｕ４を求め、
（５）３×４の投影行列Πκを次のように計算し、
（ただし、ｕ１κはｕｉの、３（κ−１）＋１，３（κ−１）＋２，３（κ−１）＋３成分を第１，２，３成分とする３次元ベクトルである。）
（６）次の計算をα＝１，…，Ｎに渡って計算し、３次元位置Ｘαを計算する。
（ａ） 次のＣｋｉαを（κｉ）要素とするＭ×４行列Ｃαを計算し、
Ｃｋｉα＝（Ｎ［ｘκα］，ｕｉｋ）
（ｂ）次の４×４行列Ｄα＝（Ｄｉｊα）を計算し、
【数３】
（ただし、計算は行列が対称であるのでｉ＜ｊの（ｉ，ｊ）要素のみ計算し、ｉ＞ｊの（ｉ，ｊ）要素は（ｊ，ｉ）要素の値をコピーする。）
（ｃ）行列Ｄαの固有値問題を解き、この最大固有値に対応する単位固有ベクトルμαを求め、これを用いて次の計算によりξαを計算し、
ξα＝±Ｎ［Ｃαμα］
（このとき、固有値の符号は次のようにする。
【数４】
（ｄ）得られたξαから射影的奥行きｚκαを次のように計算し、
ｚκα＝ξκα／‖ｘκα‖
（ｅ）得られたｚκαを用いてベクトルＰαを再計算し、さらに正規化し前記（３）の行列Ｐを再計算し、
（ｆ）３次元位置Ｘα＝（Ｘκα）を以下のように計算し、
Ｘκα＝（ｐα，ｕκ）， ｋ＝１〜４
自己校正部において正しい３次元位置Ｘαとカメラの位置Πκとを求めるに際して、
射影復元部により射影復元した３次元位置Ｘα′とカメラの位置Πκ′とを射影変換行列Ｈおよびカメラパラメータ行列により正しい３次元位置Ｘαとカメラの位置Πκとを
Πκ′＝ΠκＨ
Ｘα′＝Ｈ−１Ｘα
より求めることを特徴とする請求項１に記載の３次元位置情報復元装置。
【請求項５】
射影復元部により求めた３次元位置Ｘα′について自己校正部において求めた数学的に正しいが物理的に偽の３次元位置情報を判定して除去する補正部と
を有することを特徴とする請求項１〜請求項４のいずれかに記載の３次元位置情報復元装置。
【請求項６】
各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する手段が、特徴点の追跡の誤対応の可能性に重み係数を用いて、所定の重み係数が所定数以下の場合に連続する所定数の二次元画像を各特徴点毎に分配することを特徴とする請求項１記載の３次元位置情報復元装置。
【請求項７】
各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する手段が、時刻ｔ＋Δｔと時刻ｔの画像Ｉ（ｘ，ｔ＋Δｔ），Ｉ（ｘ，ｔ）を用いて所定数の段階の詳細度ｄを持つ画像Ｉｄ（ｘｄ，ｔ），Ｉｄ（ｘｄ，ｔ＋Δｔ）を作成し、詳細度が粗い順に、特徴点の追跡の誤対応の可能性に重み係数を計算し、当該重み係数を用いて、所定の重み係数が所定数以下の場合に連続する所定数の二次元画像を各特徴点毎に分配することを特徴とする請求項１記載の３次元位置情報復元装置。
【請求項８】
射影復元部の射影復元処理と、自己校正部の自己校正処理と、補正部の判定除去処理とをパイプライン化することを特徴とする請求項５に記載の３次元位置情報復元装置。
【請求項９】
各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する手段が、復元可能な特徴点数と画像数の数理的関係に基づき特徴点数の変化に対応して画像数を増減することを特徴とする請求項１〜請求項８のいずれかに記載の３次元位置情報復元装置。
【請求項１０】
射影復元部の射影復元処理と、自己校正部の自己校正処理と、補正部の判定除去処理とを複数の並列度により構成したことを特徴とする請求項１〜請求項９のいずれかに記載の３次元位置情報復元装置。
【請求項１１】
カメラにより撮像した複数の連続する二次元画像を元にして、撮像対象となる情景中の３次元位置を復元する方法であって、
各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する過程と、
連続する所定数の二次元画像を各特徴点毎に分配する過程と、
各特徴点毎の連続する所定数の二次元画像について各特徴点毎の３次元位置Ｘα′とカメラの位置Πκ′を射影復元する射影復元過程と、
前記射影復元過程により射影復元した３次元位置Ｘα′とカメラの位置Πκ′とを射影変換行列Ｈおよびカメラパラメータ行列により正しい３次元位置Ｘαとカメラの位置Πκとを求める自己校正過程とを有することを特徴とする３次元位置情報復元方法。
【請求項１２】
射影復元過程において３次元位置Ｘα′を計算するに際して、
画像番号κ（κ＝１，…，Ｍ）、特徴点番号α（α＝１，…，Ｎ）の画素点ｘκα、その単位ベクトルへの正規化をＮ［ｘκα］として
（１）射影的奥行をｚκα＝１と初期化し、
（２）ｚ１αｘ１α，ｚ２αｘ２α，…，ｚＭαｘＭαを縦に並べて３Ｍ次元ベクトルｐαとして以下の単位ベクトルに正規化し、
ｐαＴ＝Ｎ［（ｚ１αｘ１αＴ，ｚ２αｘ２αＴ，…，ｚＭαｘＭαＴ）］
（３）特徴点α＝１〜Ｎに対してＰαを求め、次の３Ｍ×Ｎ行列Ｐを作り、
Ｐ＝（ｐ１ｐ２…ｐＮ）
（４）行列Ｐを以下のように特異値分解し、
Ｐ＝Ｕｄｉａｇ（σ１，σ２，…）ＶＴ
行列Ｕの最初の４列ｕ１，ｕ２，ｕ３，ｕ４を求め、
（５）３×４の投影行列Πκを次のように計算し、
（ただし、ｕ１κはｕｉの、３（κ−１）＋１，３（κ−１）＋２，３（κ−１）＋３成分を第１，２，３成分とする３次元ベクトルである。）
（６）次の計算をα＝１，…，Ｎに渡って計算し、３次元位置Ｘαを計算する。
（ａ） 次のＣｋｉαを（κｉ）要素とするＭ×４行列Ｃαを計算し、
Ｃｋｉα＝（Ｎ［ｘκα］，ｕｉｋ）
（ｂ）次の４×４行列Ｄα＝（Ｄｉｊα）を計算し、
【数５】
（ただし、計算は行列が対称であるのでｉ＜ｊの（ｉ，ｊ）要素のみ計算し、ｉ＞ｊの（ｉ，ｊ）要素は（ｊ，ｉ）要素の値をコピーする。）
（ｃ）行列Ｄαの固有値問題を解き、この最大固有値に対応する単位固有ベクトルμαを求め、これを用いて次の計算によりξαを計算し、
ξα＝±Ｎ［Ｃαμα］
（このとき、固有値の符号は次のようにする。
【数６】
（ｄ）得られたξαから射影的奥行きｚκαを次のように計算し、
ｚκα＝ξκα／‖ｘκα‖
（ｅ）得られたｚκαを用いてベクトルＰαを再計算し、さらに正規化し前記（３）の行列Ｐを再計算し、
（ｆ）３次元位置Ｘα＝（Ｘκα）を以下のように計算する
Ｘκα＝（ｐα，ｕκ）， ｋ＝１〜４
ことを特徴とする請求項１１に記載の３次元位置情報復元方法。
【請求項１３】
自己校正過程において正しい３次元位置Ｘαとカメラの位置Πκとを求めるに際して、
射影復元過程により射影復元した３次元位置Ｘα′とカメラの位置Πκ′とを射影変換行列Ｈおよびカメラパラメータ行列により正しい３次元位置Ｘαとカメラの位置Πκとを
Πκ′＝ΠκＨ
Ｘα′＝Ｈ−１Ｘα
より求めることを特徴とする請求項１１に記載の３次元位置情報復元方法。
【請求項１４】
射影復元過程において３次元位置Ｘα′を計算するに際して、
画像番号κ（κ＝１，…，Ｍ）、特徴点番号α（α＝１，…，Ｎ）の画素点ｘκα、その単位ベクトルへの正規化をＮ［ｘκα］として
（１）射影的奥行をｚκα＝１と初期化し、
（２）ｚ１αｘ１α，ｚ２αｘ２α，…，ｚＭαｘＭαを縦に並べて３Ｍ次元ベクトルｐαとして以下の単位ベクトルに正規化し、
ｐαＴ＝Ｎ［（ｚ１αｘ１αＴ，ｚ２αｘ２αＴ，…，ｚＭαｘＭαＴ）］
（３）特徴点α＝１〜Ｎに対してＰαを求め、次の３Ｍ×Ｎ行列Ｐを作り、
Ｐ＝（ｐ１ｐ２…ｐＮ）
（４）行列Ｐを以下のように特異値分解し、
Ｐ＝Ｕｄｉａｇ（σ１，σ２，…）ＶＴ
行列Ｕの最初の４列ｕ１，ｕ２，ｕ３，ｕ４を求め、
（５）３×４の投影行列Πκを次のように計算し、
（ただし、ｕ１κはｕｉの、３（κ−１）＋１，３（κ−１）＋２，３（κ−１）＋３成分を第１，２，３成分とする３次元ベクトルである。）
（６）次の計算をα＝１，…，Ｎに渡って計算し、３次元位置Ｘαを計算する。
（ａ） 次のＣｋｉαを（κｉ）要素とするＭ×４行列Ｃαを計算し、
Ｃｋｉα＝（Ｎ［ｘκα］，ｕｉｋ）
（ｂ）次の４×４行列Ｄα＝（Ｄｉｊα）を計算し、
【数７】
（ただし、計算は行列が対称であるのでｉ＜ｊの（ｉ，ｊ）要素のみ計算し、ｉ＞ｊの（ｉ，ｊ）要素は（ｊ，ｉ）要素の値をコピーする。）
（ｃ）行列Ｄαの固有値問題を解き、この最大固有値に対応する単位固有ベクトルμαを求め、これを用いて次の計算によりξαを計算し、
ξα＝±Ｎ［Ｃαμα］
（このとき、固有値の符号は次のようにする。
【数８】
（ｄ）得られたξαから射影的奥行きｚκαを次のように計算し、
ｚκα＝ξκα／‖ｘκα‖
（ｅ）得られたｚκαを用いてベクトルＰαを再計算し、さらに正規化し前記（３）の行列Ｐを再計算し、
（ｆ）３次元位置Ｘα＝（Ｘκα）を以下のように計算し、
Ｘκα＝（ｐα，ｕκ）， ｋ＝１〜４
自己校正過程において正しい３次元位置Ｘαとカメラの位置Πκとを求めるに際して、
射影復元過程により射影復元した３次元位置Ｘα′とカメラの位置Πκ′とを射影変換行列Ｈおよびカメラパラメータ行列により正しい３次元位置Ｘαとカメラの位置Πκとを
Πκ′＝ΠκＨ
Ｘα′＝Ｈ−１Ｘα
より求めることを特徴とする請求項１１に記載の３次元位置情報復元方法。
【請求項１５】
射影復元過程により求めた３次元位置Ｘα′について自己校正過程において求めた数学的に正しいが物理的に偽の３次元位置情報を判定して除去する補正過程とを有することを特徴とする請求項１１〜請求項１４のいずれかに記載の３次元位置情報復元方法。
【請求項１６】
各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する過程が、特徴点の追跡の誤対応の可能性に重み係数を用いて、所定の重み係数が所定数以下の場合に連続する所定数の二次元画像を各特徴点毎に分配することを特徴とする請求項１１記載の３次元位置情報復元方法。
【請求項１７】
各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する過程が、時刻ｔ＋Δｔと時刻ｔの画像Ｉ（ｘ，ｔ＋Δｔ），Ｉ（ｘ，ｔ）を用いて所定数の段階の詳細度ｄを持つ画像Ｉｄ（ｘｄ，ｔ），Ｉｄ（ｘｄ，ｔ＋Δｔ）を作成し、詳細度が粗い順に、特徴点の追跡の誤対応の可能性に重み係数を計算し、当該重み係数を用いて、所定の重み係数が所定数以下の場合に連続する所定数の二次元画像を各特徴点毎に分配することを特徴とする請求項１１記載の３次元位置情報復元方法。
【請求項１８】
射影復元過程の射影復元処理と、自己校正過程の自己校正処理と、補正過程の判定除去処理とをパイプライン化することを特徴とする請求項１５に記載の３次元位置情報復元方法。
【請求項１９】
各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する過程が、復元可能な特徴点数と画像数の数理的関係に基づき特徴点数の変化に対応して画像数を増減することを特徴とする請求項１１〜請求項１８のいずれかに記載の３次元位置情報復元方法。
【請求項２０】
射影復元過程の射影復元処理と、自己校正過程の自己校正処理と、補正過程の判定除去処理とを複数の並列度により構成することを特徴とする請求項１１〜請求項１９のいずれかに記載の３次元位置情報復元方法。
【請求項１】
カメラにより撮像した複数の連続する二次元画像を元にして、撮像対象となる情景中の３次元位置を復元する装置であって、
各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する手段と、
連続する所定数の二次元画像を各特徴点毎に分配する手段と、
各特徴点毎の連続する所定数の二次元画像について各特徴点毎の３次元位置Ｘα′とカメラの位置Πκ′を射影復元する射影復元部と、
前記射影復元部により射影復元した３次元位置Ｘα′とカメラの位置Πκ′とを射影変換行列Ｈおよびカメラパラメータ行列により正しい３次元位置Ｘαとカメラの位置Πκとを求める自己校正部とを有することを特徴とする３次元位置情報復元装置。
【請求項２】
射影復元部において３次元位置Ｘα′を計算するに際して、
画像番号κ（κ＝１，…，Ｍ）、特徴点番号α（α＝１，…，Ｎ）の画素点ｘκα、その単位ベクトルへの正規化をＮ［ｘκα］として
（１）射影的奥行をｚκα＝１と初期化し、
（２）ｚ１αｘ１α，ｚ２αｘ２α，…，ｚＭαｘＭαを縦に並べて３Ｍ次元ベクトルｐαとして以下の単位ベクトルに正規化し、
ｐαＴ＝Ｎ［（ｚ１αｘ１αＴ，ｚ２αｘ２αＴ，…，ｚＭαｘＭαＴ）］
（３）特徴点α＝１〜Ｎに対してＰαを求め、次の３Ｍ×Ｎ行列Ｐを作り、
Ｐ＝（ｐ１ｐ２…ｐＮ）
（４）行列Ｐを以下のように特異値分解し、
Ｐ＝Ｕｄｉａｇ（σ１，σ２，…）ＶＴ
行列Ｕの最初の４列ｕ１，ｕ２，ｕ３，ｕ４を求め、
（５）３×４の投影行列Πκを次のように計算し、
Πκ ＝ （ｕ１κ ｕ２κ ｕ３κ ｕ４κ）
（ただし、ｕ１κはｕｉの、３（κ−１）＋１，３（κ−１）＋２，３（κ−１）＋３成分を第１，２，３成分とする３次元ベクトルである。）
（６）次の計算をα＝１，…，Ｎに渡って計算し、３次元位置Ｘαを計算する。
（ａ） 次のＣｋｉαを（κｉ）要素とするＭ×４行列Ｃαを計算し、
Ｃｋｉα＝（Ｎ［ｘκα］，ｕｉｋ）
（ｂ）次の４×４行列Ｄα＝（Ｄｉｊα）を計算し、
【数１】
（ただし、計算は行列が対称であるのでｉ＜ｊの（ｉ，ｊ）要素のみ計算し、ｉ＞ｊの（ｉ，ｊ）要素は（ｊ，ｉ）要素の値をコピーする。）
（ｃ）行列Ｄαの固有値問題を解き、この最大固有値に対応する単位固有ベクトルμαを求め、これを用いて次の計算によりξαを計算し、
ξα＝±Ｎ［Ｃαμα］
（このとき、固有値の符号は次のようにする。
【数２】
（ｄ）得られたξαから射影的奥行きｚκαを次のように計算し、
ｚκα＝ξκα／‖ｘκα‖
（ｅ）得られたｚκαを用いてベクトルＰαを再計算し、さらに正規化し前記（３）の行列Ｐを再計算し、
（ｆ）３次元位置Ｘα＝（Ｘκα）を以下のように計算する
Ｘκα＝（ｐα，ｕκ）， ｋ＝１〜４
ことを特徴とする請求項１に記載の３次元位置情報復元装置。
【請求項３】
自己校正部において正しい３次元位置Ｘαとカメラの位置Πκとを求めるに際して、
射影復元部により射影復元した３次元位置Ｘα′とカメラの位置Πκ′とを射影変換行列Ｈおよびカメラパラメータ行列により正しい３次元位置Ｘαとカメラの位置Πκとを
Πκ′＝ΠκＨ
Ｘα′＝Ｈ−１Ｘα
より求めることを特徴とする請求項１に記載の３次元位置情報復元装置。
【請求項４】
射影復元部において３次元位置Ｘα′を計算するに際して、
画像番号κ（κ＝１，…，Ｍ）、特徴点番号α（α＝１，…，Ｎ）の画素点ｘκα、その単位ベクトルへの正規化をＮ［ｘκα］として
（１）射影的奥行をｚκα＝１と初期化し、
（２）ｚ１αｘ１α，ｚ２αｘ２α，…，ｚＭαｘＭαを縦に並べて３Ｍ次元ベクトルｐαとして以下の単位ベクトルに正規化し、
ｐαＴ＝Ｎ［（ｚ１αｘ１αＴ，ｚ２αｘ２αＴ，…，ｚＭαｘＭαＴ）］
（３）特徴点α＝１〜Ｎに対してＰαを求め、次の３Ｍ×Ｎ行列Ｐを作り、
Ｐ＝（ｐ１ｐ２…ｐＮ）
（４）行列Ｐを以下のように特異値分解し、
Ｐ＝Ｕｄｉａｇ（σ１，σ２，…）ＶＴ
行列Ｕの最初の４列ｕ１，ｕ２，ｕ３，ｕ４を求め、
（５）３×４の投影行列Πκを次のように計算し、
（ただし、ｕ１κはｕｉの、３（κ−１）＋１，３（κ−１）＋２，３（κ−１）＋３成分を第１，２，３成分とする３次元ベクトルである。）
（６）次の計算をα＝１，…，Ｎに渡って計算し、３次元位置Ｘαを計算する。
（ａ） 次のＣｋｉαを（κｉ）要素とするＭ×４行列Ｃαを計算し、
Ｃｋｉα＝（Ｎ［ｘκα］，ｕｉｋ）
（ｂ）次の４×４行列Ｄα＝（Ｄｉｊα）を計算し、
【数３】
（ただし、計算は行列が対称であるのでｉ＜ｊの（ｉ，ｊ）要素のみ計算し、ｉ＞ｊの（ｉ，ｊ）要素は（ｊ，ｉ）要素の値をコピーする。）
（ｃ）行列Ｄαの固有値問題を解き、この最大固有値に対応する単位固有ベクトルμαを求め、これを用いて次の計算によりξαを計算し、
ξα＝±Ｎ［Ｃαμα］
（このとき、固有値の符号は次のようにする。
【数４】
（ｄ）得られたξαから射影的奥行きｚκαを次のように計算し、
ｚκα＝ξκα／‖ｘκα‖
（ｅ）得られたｚκαを用いてベクトルＰαを再計算し、さらに正規化し前記（３）の行列Ｐを再計算し、
（ｆ）３次元位置Ｘα＝（Ｘκα）を以下のように計算し、
Ｘκα＝（ｐα，ｕκ）， ｋ＝１〜４
自己校正部において正しい３次元位置Ｘαとカメラの位置Πκとを求めるに際して、
射影復元部により射影復元した３次元位置Ｘα′とカメラの位置Πκ′とを射影変換行列Ｈおよびカメラパラメータ行列により正しい３次元位置Ｘαとカメラの位置Πκとを
Πκ′＝ΠκＨ
Ｘα′＝Ｈ−１Ｘα
より求めることを特徴とする請求項１に記載の３次元位置情報復元装置。
【請求項５】
射影復元部により求めた３次元位置Ｘα′について自己校正部において求めた数学的に正しいが物理的に偽の３次元位置情報を判定して除去する補正部と
を有することを特徴とする請求項１〜請求項４のいずれかに記載の３次元位置情報復元装置。
【請求項６】
各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する手段が、特徴点の追跡の誤対応の可能性に重み係数を用いて、所定の重み係数が所定数以下の場合に連続する所定数の二次元画像を各特徴点毎に分配することを特徴とする請求項１記載の３次元位置情報復元装置。
【請求項７】
各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する手段が、時刻ｔ＋Δｔと時刻ｔの画像Ｉ（ｘ，ｔ＋Δｔ），Ｉ（ｘ，ｔ）を用いて所定数の段階の詳細度ｄを持つ画像Ｉｄ（ｘｄ，ｔ），Ｉｄ（ｘｄ，ｔ＋Δｔ）を作成し、詳細度が粗い順に、特徴点の追跡の誤対応の可能性に重み係数を計算し、当該重み係数を用いて、所定の重み係数が所定数以下の場合に連続する所定数の二次元画像を各特徴点毎に分配することを特徴とする請求項１記載の３次元位置情報復元装置。
【請求項８】
射影復元部の射影復元処理と、自己校正部の自己校正処理と、補正部の判定除去処理とをパイプライン化することを特徴とする請求項５に記載の３次元位置情報復元装置。
【請求項９】
各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する手段が、復元可能な特徴点数と画像数の数理的関係に基づき特徴点数の変化に対応して画像数を増減することを特徴とする請求項１〜請求項８のいずれかに記載の３次元位置情報復元装置。
【請求項１０】
射影復元部の射影復元処理と、自己校正部の自己校正処理と、補正部の判定除去処理とを複数の並列度により構成したことを特徴とする請求項１〜請求項９のいずれかに記載の３次元位置情報復元装置。
【請求項１１】
カメラにより撮像した複数の連続する二次元画像を元にして、撮像対象となる情景中の３次元位置を復元する方法であって、
各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する過程と、
連続する所定数の二次元画像を各特徴点毎に分配する過程と、
各特徴点毎の連続する所定数の二次元画像について各特徴点毎の３次元位置Ｘα′とカメラの位置Πκ′を射影復元する射影復元過程と、
前記射影復元過程により射影復元した３次元位置Ｘα′とカメラの位置Πκ′とを射影変換行列Ｈおよびカメラパラメータ行列により正しい３次元位置Ｘαとカメラの位置Πκとを求める自己校正過程とを有することを特徴とする３次元位置情報復元方法。
【請求項１２】
射影復元過程において３次元位置Ｘα′を計算するに際して、
画像番号κ（κ＝１，…，Ｍ）、特徴点番号α（α＝１，…，Ｎ）の画素点ｘκα、その単位ベクトルへの正規化をＮ［ｘκα］として
（１）射影的奥行をｚκα＝１と初期化し、
（２）ｚ１αｘ１α，ｚ２αｘ２α，…，ｚＭαｘＭαを縦に並べて３Ｍ次元ベクトルｐαとして以下の単位ベクトルに正規化し、
ｐαＴ＝Ｎ［（ｚ１αｘ１αＴ，ｚ２αｘ２αＴ，…，ｚＭαｘＭαＴ）］
（３）特徴点α＝１〜Ｎに対してＰαを求め、次の３Ｍ×Ｎ行列Ｐを作り、
Ｐ＝（ｐ１ｐ２…ｐＮ）
（４）行列Ｐを以下のように特異値分解し、
Ｐ＝Ｕｄｉａｇ（σ１，σ２，…）ＶＴ
行列Ｕの最初の４列ｕ１，ｕ２，ｕ３，ｕ４を求め、
（５）３×４の投影行列Πκを次のように計算し、
（ただし、ｕ１κはｕｉの、３（κ−１）＋１，３（κ−１）＋２，３（κ−１）＋３成分を第１，２，３成分とする３次元ベクトルである。）
（６）次の計算をα＝１，…，Ｎに渡って計算し、３次元位置Ｘαを計算する。
（ａ） 次のＣｋｉαを（κｉ）要素とするＭ×４行列Ｃαを計算し、
Ｃｋｉα＝（Ｎ［ｘκα］，ｕｉｋ）
（ｂ）次の４×４行列Ｄα＝（Ｄｉｊα）を計算し、
【数５】
（ただし、計算は行列が対称であるのでｉ＜ｊの（ｉ，ｊ）要素のみ計算し、ｉ＞ｊの（ｉ，ｊ）要素は（ｊ，ｉ）要素の値をコピーする。）
（ｃ）行列Ｄαの固有値問題を解き、この最大固有値に対応する単位固有ベクトルμαを求め、これを用いて次の計算によりξαを計算し、
ξα＝±Ｎ［Ｃαμα］
（このとき、固有値の符号は次のようにする。
【数６】
（ｄ）得られたξαから射影的奥行きｚκαを次のように計算し、
ｚκα＝ξκα／‖ｘκα‖
（ｅ）得られたｚκαを用いてベクトルＰαを再計算し、さらに正規化し前記（３）の行列Ｐを再計算し、
（ｆ）３次元位置Ｘα＝（Ｘκα）を以下のように計算する
Ｘκα＝（ｐα，ｕκ）， ｋ＝１〜４
ことを特徴とする請求項１１に記載の３次元位置情報復元方法。
【請求項１３】
自己校正過程において正しい３次元位置Ｘαとカメラの位置Πκとを求めるに際して、
射影復元過程により射影復元した３次元位置Ｘα′とカメラの位置Πκ′とを射影変換行列Ｈおよびカメラパラメータ行列により正しい３次元位置Ｘαとカメラの位置Πκとを
Πκ′＝ΠκＨ
Ｘα′＝Ｈ−１Ｘα
より求めることを特徴とする請求項１１に記載の３次元位置情報復元方法。
【請求項１４】
射影復元過程において３次元位置Ｘα′を計算するに際して、
画像番号κ（κ＝１，…，Ｍ）、特徴点番号α（α＝１，…，Ｎ）の画素点ｘκα、その単位ベクトルへの正規化をＮ［ｘκα］として
（１）射影的奥行をｚκα＝１と初期化し、
（２）ｚ１αｘ１α，ｚ２αｘ２α，…，ｚＭαｘＭαを縦に並べて３Ｍ次元ベクトルｐαとして以下の単位ベクトルに正規化し、
ｐαＴ＝Ｎ［（ｚ１αｘ１αＴ，ｚ２αｘ２αＴ，…，ｚＭαｘＭαＴ）］
（３）特徴点α＝１〜Ｎに対してＰαを求め、次の３Ｍ×Ｎ行列Ｐを作り、
Ｐ＝（ｐ１ｐ２…ｐＮ）
（４）行列Ｐを以下のように特異値分解し、
Ｐ＝Ｕｄｉａｇ（σ１，σ２，…）ＶＴ
行列Ｕの最初の４列ｕ１，ｕ２，ｕ３，ｕ４を求め、
（５）３×４の投影行列Πκを次のように計算し、
（ただし、ｕ１κはｕｉの、３（κ−１）＋１，３（κ−１）＋２，３（κ−１）＋３成分を第１，２，３成分とする３次元ベクトルである。）
（６）次の計算をα＝１，…，Ｎに渡って計算し、３次元位置Ｘαを計算する。
（ａ） 次のＣｋｉαを（κｉ）要素とするＭ×４行列Ｃαを計算し、
Ｃｋｉα＝（Ｎ［ｘκα］，ｕｉｋ）
（ｂ）次の４×４行列Ｄα＝（Ｄｉｊα）を計算し、
【数７】
（ただし、計算は行列が対称であるのでｉ＜ｊの（ｉ，ｊ）要素のみ計算し、ｉ＞ｊの（ｉ，ｊ）要素は（ｊ，ｉ）要素の値をコピーする。）
（ｃ）行列Ｄαの固有値問題を解き、この最大固有値に対応する単位固有ベクトルμαを求め、これを用いて次の計算によりξαを計算し、
ξα＝±Ｎ［Ｃαμα］
（このとき、固有値の符号は次のようにする。
【数８】
（ｄ）得られたξαから射影的奥行きｚκαを次のように計算し、
ｚκα＝ξκα／‖ｘκα‖
（ｅ）得られたｚκαを用いてベクトルＰαを再計算し、さらに正規化し前記（３）の行列Ｐを再計算し、
（ｆ）３次元位置Ｘα＝（Ｘκα）を以下のように計算し、
Ｘκα＝（ｐα，ｕκ）， ｋ＝１〜４
自己校正過程において正しい３次元位置Ｘαとカメラの位置Πκとを求めるに際して、
射影復元過程により射影復元した３次元位置Ｘα′とカメラの位置Πκ′とを射影変換行列Ｈおよびカメラパラメータ行列により正しい３次元位置Ｘαとカメラの位置Πκとを
Πκ′＝ΠκＨ
Ｘα′＝Ｈ−１Ｘα
より求めることを特徴とする請求項１１に記載の３次元位置情報復元方法。
【請求項１５】
射影復元過程により求めた３次元位置Ｘα′について自己校正過程において求めた数学的に正しいが物理的に偽の３次元位置情報を判定して除去する補正過程とを有することを特徴とする請求項１１〜請求項１４のいずれかに記載の３次元位置情報復元方法。
【請求項１６】
各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する過程が、特徴点の追跡の誤対応の可能性に重み係数を用いて、所定の重み係数が所定数以下の場合に連続する所定数の二次元画像を各特徴点毎に分配することを特徴とする請求項１１記載の３次元位置情報復元方法。
【請求項１７】
各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する過程が、時刻ｔ＋Δｔと時刻ｔの画像Ｉ（ｘ，ｔ＋Δｔ），Ｉ（ｘ，ｔ）を用いて所定数の段階の詳細度ｄを持つ画像Ｉｄ（ｘｄ，ｔ），Ｉｄ（ｘｄ，ｔ＋Δｔ）を作成し、詳細度が粗い順に、特徴点の追跡の誤対応の可能性に重み係数を計算し、当該重み係数を用いて、所定の重み係数が所定数以下の場合に連続する所定数の二次元画像を各特徴点毎に分配することを特徴とする請求項１１記載の３次元位置情報復元方法。
【請求項１８】
射影復元過程の射影復元処理と、自己校正過程の自己校正処理と、補正過程の判定除去処理とをパイプライン化することを特徴とする請求項１５に記載の３次元位置情報復元方法。
【請求項１９】
各二次元画像から複数の特徴点を検出し各二次元画像について当該特徴点を追跡する過程が、復元可能な特徴点数と画像数の数理的関係に基づき特徴点数の変化に対応して画像数を増減することを特徴とする請求項１１〜請求項１８のいずれかに記載の３次元位置情報復元方法。
【請求項２０】
射影復元過程の射影復元処理と、自己校正過程の自己校正処理と、補正過程の判定除去処理とを複数の並列度により構成することを特徴とする請求項１１〜請求項１９のいずれかに記載の３次元位置情報復元方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【公開番号】特開２００９−５３０８０（Ｐ２００９−５３０８０Ａ）
【公開日】平成２１年３月１２日（２００９．３．１２）
【国際特許分類】
【出願番号】特願２００７−２２０８６６（Ｐ２００７−２２０８６６）
【出願日】平成１９年８月２８日（２００７．８．２８）
【出願人】（０００１７６７３０）三菱プレシジョン株式会社 (97)
【出願人】（５０４１４７２４３）国立大学法人 岡山大学 (444)
【Ｆターム（参考）】
【公開日】平成２１年３月１２日（２００９．３．１２）
【国際特許分類】
【出願日】平成１９年８月２８日（２００７．８．２８）
【出願人】（０００１７６７３０）三菱プレシジョン株式会社 (97)
【出願人】（５０４１４７２４３）国立大学法人 岡山大学 (444)
【Ｆターム（参考）】
[ Back to top ]