(57)【要約】【課題】線形演算処理の範囲内で，多数の２次元画像から，対象点の３次元空間内の位置をできるだけ正確に計算する反復的計算法の提供。【解決手段】上記の課題の解決のために，線形なアフィンカメラモデルの行列と加重行列から構成された一連の一般逆行列を用いる反復的３次元位置の計算方法を発明した。そのアフィンカメラモデルは実際の撮影カメラによる画像に対して最小誤差を与えるように精密に調節されている。また加重行列には，従来から利用されていた個々の対象点座標の信頼度に限らず，それらの間の相関も同時に計算することにより，実際の撮影画像に現れる非線形な歪成分の空間的な相関関係も考慮に入れた計算精度の改善を実現することが可能になった。【選択図】  「図２」
2005062147.tif 000002
【特許請求の範囲】
【請求項１】
複数のカメラ又はビデオカメラで撮影された多数枚の２次元画像中の対象点について，これら対象点の３次元空間中における位置（座標）と上記カメラの相対的な３次元位置を反復的手順により計算する方法であって，反復の各段階で計算された３次元位置のアフィンカメラモデルによる投影画像と上記撮影画像の間で最小２乗誤差を与えるような上記アフィンカメラモデルを使用することを特徴とし，更に一連の一般逆行列の系列を利用することを特徴とする，最小誤差カメラと一般逆行列による３次元位置の反復的計算方法。
【請求項２】
請求項１記載の最小２乗誤差を与えるようなアフィンカメラモデルは，前記の反復の各段階において計算された対象点の３次元座標および撮影画像上の前記対象点の２次元座標を用いて構成される連立１次方程式を解いて求められ，しかも反復の各段階において修正を受けることを特徴とする，請求項１に記載の最小誤差カメラと一般逆行列による３次元位置の反復的計算方法。
【請求項３】
請求項１に記載の一般逆行列の系列は，反復の各段階において修正を受けて生成されることを特徴として，更にその修正は請求項２に記載のアフィンカメラモデルの写像を表す行列，及び前記対象点の３次元座標の上記アフィンカメラモデルによる画像と前記の撮影画像との間に生じる誤差の分散共分散行列に基づき実行されることを特徴とする，請求項１または２に記載の最小誤差カメラと一般逆行列による３次元位置の反復的計算方法。
【発明の詳細な説明】
【技術分野】
【０００１】本発明は，多数の２次元画像から対象点の３次元位置を計算するための線形な手法の中で，観測画像における多様な誤差から生じる計算結果の誤差を最小化するための，アフィン変換に基づく最小２乗誤差カメラモデルと加重行列を組み込んだ一般逆行列の系列を使用する特徴を有する，対象点の３次元位置の反復的計算方法に関する。
【背景技術】
【０００２】３次元（以降は３Ｄと省略）空間内の点（対象点）を撮影した２次元（以降は２Ｄと省略）画像から，それら対象点の３Ｄ位置を計算する問題は，コンピュータビジョンの中心的課題の一つである。この問題の解決手法の中でも，多数（３枚以上）の画像を撮影したカメラの相対的な回転角度を推定した後，弱透視投影（拡大縮小された並行投影）のカメラモデルとムーア・ペンローズの一般逆行列を用いて，これらの画像から計算する方法（非特許文献１参照）は，個々の観測画像に含まれる無相関の観測誤差の相殺効果によって計算結果の誤差を低減できるという利点を持つ反面，カメラモデルの投影法が実際の撮影に使用するカメラの投影法と異なることから計算結果の誤差を生じるという欠点が知られている。【０００３】一方，特異値分解法を応用した線形代数的な処理の過程の中で，上記カメラの相対的回転角度の推定および対象点の３Ｄ空間内位置の計算を同時に行う巧妙な方法は，因子分解法と呼ばれている（非特許文献２参照）。因子分解法において利用されるカメラモデルは，初期の弱透視投影から平行透視投影へ拡張されており（非特許文献３参照），これらの方法は段落［０００２］に述べたものと同一の利点と欠点を持っている。また，上記因子分解法におけるカメラモデルは透視投影モデルへも拡張された（非特許文献４参照）。しかし，この拡張は上記欠点を補うことと引き換えに上記利点を失う結果をもたらし，さらに非線形方程式の最適化という複雑な操作が必要となった。【０００４】上記利点をなるべく保持しながら上記欠点を補うために，特許文献１では，第１ステップにおいて３Ｄ位置の既知な複数の参照点の画像をもとにアフィンカメラの線形写像の係数をあらかじめ求めておき，第２ステップでそのカメラモデルを用いて撮影画像の座標の誤差を補正する方法が採用されている。しかし，参照点を用いる特許文献１のアフィンカメラモデルの決定法に比べ，撮影画像をより正確に近似可能であって参照点を用いないアフィンカメラモデルの決定法がある（非特許文献５参照）。【０００５】上と同様に，上記利点を保持しつつ上記欠点を補うために，特許文献２では，アフィンカメラモデルを用い，そのカメラパラメータの決定と対象点の３Ｄ位置決定を加重係数付きの最小２乗法により反復的に実行する方法を採用し，これらの２つの決定における共通の加重係数として，画像フレー厶中心からの距離の単調減少関数に従う加重係数を採用している。この加重係数は，撮影画像の座標値の信頼度（アフィンカメラモデルの正確さ）を評価する働きを持つが，特許文献２の方法は，この信頼度を近似的に表す手法に過ぎないので，非特許文献５の加重係数と比較すれば，一般に精度が低い。なぜなら，非特許文献５では，２つの決定において異なる加重係数を用いるとともに，現実のカメラの投影法に従って評価した個々の２Ｄ対象点の精密な信頼度に加え，それらの相関も含めた信頼度を評価して利用するからである。【０００６】上記の３種類の線形なカメラモデル（弱透視，平行透視，又はアフィン）とは異なり，実際の撮影に用いるカメラには，透視投影の非線形写像の成分と共に，レンズの加工精度や光の性質による各種の収差や歪による非線形成分も存在することが広く知られており，その定式化も既に研究されている（非特許文献６参照）。このうち，前者（透視投影の非線形成分）を避けることは原理的に難しい。他方，後者（各種の収差や歪）は性能の良いレンズの選択的使用により相当程度まで低減できるが，無視できない状況においては，非特許文献６の手法を用いて後者を含む画像をシミュレートすることにより，本発明における上記の信頼度の評価に利用することが可能である。
【特許文献１】特開平１１−３７７２１号公報
【特許文献２】特開２０００−３４４７号公報
【非特許文献１】Ｇ．Ｘｕ  ａｎｄ  Ｎ．Ｓｕｇｉｍｏｔｏ：  “Ａ  Ｌｉｎｅａｒ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ｍｏｔｉｏｎ  ｆｒｏｍ  Ｔｈｒｅｅ  Ｗｅａｋ  Ｐｅｒｓｐｅｃｔｉｖｅ  Ｉｍａｇｅｓ  Ｕｓｉｎｇ  Ｅｕｌｅｒ  Ａｎｇｌｅｓ，″ＩＥＥＥ  Ｔｒａｎｓ．Ｐａｔｔｅｒｎ  Ａｎａｌｙｓｉｓ  ａｎｄ  Ｍａｃｈｉｎｅ  Ｉｎｔｅｌｌｉｇｅｎｃｅ，ｖｏｌ．２１，ｎｏ．１，ｐｐ．５４−５７，１９９９．
【非特許文献２】Ｃ．Ｔｏｍａｓｉ  ａｎｄ  Ｔ．Ｋａｎａｄｅ，“Ｓｈａｐｅ  ａｎｄ  Ｍｏｔｉｏｎ  ｆｒｏｍ  Ｉｍａｇｅ  Ｓｔｒｅａｍ  ｕｎｄｅｒ  Ｏｒｔｈｏｇｒａｐｈｙ：Ａ  ｆａｃｔｏｒｉｚａｔｉｏｎ  ｍｅｔｈｏｄ，″Ｉｎｔ．Ｊ．ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ，ｖｏｌ．９，ｐｐ．１３７−１５４，１９９２．
【非特許文献３】金出武雄，コンラッド  ポールマン，森田俊彦，″因子分解法による物体形状とカメラ運動の復元，″電子情報通信学会論文誌，ｖｏｌ．Ｊ７６−Ｄ−ＩＩ，ｎｏ．８，ｐｐ．１４９７−１５０５，１９９３．
【非特許文献４】Ｓ．Ｃｈｒｉｓｔｙ  ａｎｄ  Ｒ．Ｈｏｒａｕｄ，“Ｅｕｃｌｉｄｉａｎ  Ｓｈａｐｅ  ａｎｄ  Ｍｏｔｉｏｎ  ｆｒｏｍ  Ｍｕｌｔｉｐｌｅ  Ｐｅｒｓｐｅｃｔｉｖｅ  Ｖｉｅｗｓ  ｂｙ  Ａｆｆｉｎｅ  Ｉｔｅｒａｔｉｏｎｓ，”ＩＥＥＥ  Ｔｒａｎｓ．Ｐａｔｔｅｒｎ  Ａｎａｌｙｓｉｓ  ａｎｄ  Ｍａｃｈｉｎｅ  Ｉｎｔｅｌｌｉｇｅｎｃｅ，ｖｏｌ．１８，ｎｏ．１１，ｐｐ．１０９８−１１０４，１９９６．
【非特許文献５】坂本博康，桑原梓，“最小誤差の線形カメラモデルとそれを用いる３Ｄ形状復元法，”電子情報通信学会技術研究報告．ＰＲＭＵ２００２−２１９，ｖｏｌ．１０２，ｎｏ．６５２，ｐｐ．４９−５４，２００３年２月２１日発表．
【非特許文献６】Ｇ−Ｑ．Ｗｅｉ  ａｎｄ  Ｓ．Ｄ．Ｍａ，“Ｉｍｐｌｉｃｉｔ  ａｎｄ  Ｅｘｐｌｉｃｉｔ  Ｃａｍｅｒａ  Ｃａｌｉｂｒａｔｉｏｎ  ：  Ｔｈｅｏｒｙ  ａｎｄ  Ｅｘ−ｐｅｒｉｍｅｎｔｓ，”ＩＥＥＥ  Ｔｒａｎｓ．Ｐａｔｔｅｒｎ  Ａｎａｌｙｓｉｓ  ａｎｄ  Ｍａｃｈｉｎｅ  Ｉｎｔｅｌｌｉｇｅｎｃｅ，ｖｏｌ，１６，ｎｏ．５，ｐｐ．４６９−４８０，１９９４．
【発明の開示】
【発明が解決しようとする課題】
【０００７】解決しようとする課題は，線形演算処理の範囲内において，上記の段落［０００２］に述べた利点と欠点に関して，この利点を生かしながら，できるだけこの欠点を緩和させる方法を実現することである。そのために，この発明の主な目的は，なるべく多数の撮影画像を用い，それら撮影画像を最良近似する線形なアフィンカメラモデルを構成し，さらにこのカメラモデルと撮影画像との間の誤差を補正可能な加重係数付き一般逆行列の系列を構成することによって，線形演算処理の範囲内において，できるだけ精度の高い３次元位置の反復的計算法を提供することである。【０００８】本発明と類似した方法として上の特許文献１又は２を示した。しかし，特許文献１又は２は，共にアフィンカメラモデルの決定法と加重係数の設定法の精度が低く，そのために正確な計算結果を期待しにくいという問題があった。
【課題を解決するための手段】
【０００９】上記課題を解決するための手段には，上記利点を生かすために，なるべく多くの撮影画像を用いた一般逆行列による最小２乗解法を採用するとともに，上記欠点を緩和するために撮影画像を最良近似する線形なアフィンカメラモデルを決定して利用する。また，このカメラモデルによっても表現不可能な撮影画像の誤差成分（非線形写像などの成分）の影響を補正するために，加重係数付き最小２乗法を与える一般逆行列を構成し利用する。更に，本手段は反復的方法として実行され，非特許文献１又は２などの従来方法による対象点の３Ｄ位置を第１回目の開始データとして利用し，反復を経るごとにアフィンカメラモデルと一般逆行列を修正することによって３Ｄ位置データの補正を繰り返し，補正量が許容量以下となったとき，対象点の３Ｄ位置の計算結果とする。
【発明の効果】
【００１０】上記段落［０００４］，［０００５］に述べたように，特許文献１または２で採用された近似法に比べて，本発明のアフィンカメラモデルと加重係数の決定法はより高い精度を持つので，より正確な３次元位置の計算結果を与えることができる。特に，加重係数の決定に際して，データの個々の信頼性に加えて互いの関連性（相関）も考慮に入れることにより，実際の撮影用カメラの透視投影の非線形歪あるいはレンズの収差や歪によって撮影画像に導入される対象点の観測誤差（つまり信頼性）の強さと相関の両方を低減でき，その結果，従来法よりも精度の高い計算結果を得ることが可能となった。図１には上記の観測誤差の向きと大きさを矢印で記し，ある３次元空間内の対象点の見え方においては，その誤差の強さと相関にそれぞれ特有の傾向があることを示している。
【発明を実施するための最良の形態】
【００１１】本発明による計算方法の反復処理の流れを図２に示す。複数台のカメラまたはビデオカメラからコンピュータに入力された多数の画像に対して，一般的に知られている画像処理の手法により複数の対象点座標が抽出され，更にこれら対象点の複数画像間の対応付けが行われる。以上のデータと対応付け情報を以降の反復的計算法で使用することとし，図２の以降の部分については後で説明する。【００１２】上の段落［０００９］に述べた撮影画像を最良近似するアフィンカメラモデルは，反復の各段階における対象点の３Ｄ位置の計算結果と撮影画像の対象点の２Ｄ位置から作られる連立１次方程式（正規方程式）を解いて求められる。この方程式は，各反復段階の３Ｄ位置をこのカメラで投影した画像を，実際の撮影画像に最小２乗誤差で当てはめる条件式を意味する。但し，特許文献２とは異なり，ここでは全部の対象点に等価な加重係数を用いる。つまり本方法で得られるアフィンカメラモデルは，撮影画像の全体に渡り，対象点の３Ｄ位置とそれを撮影したカメラの両方の性質に最も良く適合する線形モデルである。【００１３】次の数式［数１］，［数２］，［数３］にはそれぞれ，上述のアフィンカメラモデルの式，このモデルの誤差評価基準を表す式，及びこのモデルの計算式（連立１次方程式の解）を示す。ただし，３Ｄ空間内の第ｋ対象点の同次座標をＶｋ＝［Ｘｋ，Ｙｋ，Ｚｋ，１］Ｔ，（ｋ＝１，２，…，Ｋ）（Ｔは転置），アフィンカメラ行列Ｃの要素をＣｉ，ｊ，ＶｋのカメラＣによる画像の２Ｄ座標をｕｋ，実際の撮影画像における第ｋ対象点の２Ｄ座標をｑｋ＝［ｘｋ，ｙｋ］Ｔする。また，［数３］の式の右辺における各要素の上の横棒は，ｋ＝１，２，…，Ｋに関する加算平均値を表す。【００１４】
【数１】
2005062147.tif 000003
【００１５】
【数２】
2005062147.tif 000004
【００１６】
【数３】
2005062147.tif 000005
【００１７】説明の便宜のために，従来のムーア・ペンローズ一般逆行列による３Ｄ位置の計算法（非特許文献１参照）を説明する。合計Ｍ枚の撮影画像に対してそれぞれ，上記方法でカメラ行列Ｃｍ（ｍ＝１，２，…，Ｍ）を計算し，それを全部縦に積み上げた２Ｍ×４行列を次のように改めてＣとおけば，Ｃのムーア・ペンローズ一般逆行列Ｃ＋は次式のように計算される。【００１８】
【数４】
2005062147.tif 000006
【００１９】従来のＣ＋による計算法では，撮影画像の第ｋ対象点座標ｑｋも同様に全Ｍ枚分を縦に積み上げてｖｋとおき，元の３Ｄ同次座標の最小２乗誤差推定を次式で計算する。ただし，同次座標Ｖｋの第１，２，３要素だけを結果として用いる。この方法により，流れ図２の第１段階における対象点の初期３Ｄ位置の計算を実行できる。【００２０】
【数５】
2005062147.tif 000007
【００２１】次に，上記段落［０００９］における加重係数付き最小２乗解を与える一般逆行列は，上記最良アフィンカメラによって投影した反復のある段階における３Ｄ対象点の２Ｄ座標を，その座標のアフィンカメラに関する信頼性を表す加重係数および相関係数を考慮しながら，実際の撮影画像の対象点に最小誤差となるように当てはめるための条件式から，以下に示すように求められる。【００２２】従来法における加重係数に加えて信頼性の相関を組み込むために，２Ｄ撮影画像と３Ｄ空間内の全対象点を縦方向に積み上げ，次の２ＭＫ次元ベクトルｖ及び４Ｋ次元ベクトルＶとおく。【００２３】
【数６】
2005062147.tif 000008
【００２４】段落［００１７］の２Ｍ×４のカメラ行列Ｃを，主対角上にＫ回繰返し並べた２ＭＫ×４Ｋのブロック対角行列をＢとおけば，このカメラモデルによる画像と実際の撮影画像の誤差ｅを，信頼性（それらの間の相関を含む）を表す加重行列Ｗによって評価する基準Ｊ（Ｖ）及び，この評価基準を対象点の３Ｄ位置Ｖに関して最小化する必要条件（Ｊ（Ｖ）のＶに関する偏微分係数を０としたもの）は，それぞれ次の［数７］，［数８］の式で与えられる。ただし，加重行列Ｗを単位行列とすれば，［数８］の解は［数５］の解と一致する。また，特許文献２は，このＷを対角行列に制限する方法に等価である。【００２５】
【数７】
2005062147.tif 000009
【００２６】
【数８】
2005062147.tif 000010
【００２７】加重行列Ｗとして，アフィンカメラモデルによる画像と実際の撮影画像の誤差ｅに関する分散共分散行列Ｒの逆行列を用いれば，信頼性の低い（又は高い）観測データには小さい（又は大きい）加重係数を割り当てると共に，誤差の無相関化を図ることが可能になり，従来法より正確な３Ｄ位置の計算結果を得ることができる。【００２８】ここで，実際の撮影画像の誤差ｅの主要な成分は，線形アフィンカメラでは表現不可能な非線形成分やランダム誤差成分である。この非線形成分には，実際のカメラの透視投影による非線形歪成分およびレンズの収差や加工歪による成分が含まれる。これらの成分は，３Ｄ空間内の対象点の相対的位置関係に従って，大きな強度の差異と相関成分を持つことがしばしば観察される。【００２９】しかし，［数７］のｅ＝ｖ−ＢＶを単純に標本平均する演算によっては，本方法で使用可能なＲやＷの良い推定は絶対に得られない。なぜならば，上の単純な引算では上記の線形成分だけを正確に取り去ることは不可能だからである。これらの良い推定を求める方法を以下に示す。【００３０】加重行列Ｗとして利用可能なＲやＷの良い推定を得るには，実際の撮影画像の非線形成分を精密に取り出す必要がある。このために，平行移動を含む３Ｄ空間（物体）の自由度は４であり，この３Ｄ空間を線形なカメラで撮影した２Ｄ画像の階数（ランク）は４である性質を用いて，次のようにして直交射影行列Ｌｘｙを構成する。まず，現在の反復の段階における３Ｄ位置Ｖを任意の異なる３方向から平行投影カメラで画像化し，そのＫ個の対象点２Ｄ座標ベクトルを求め，更にそれをグラム・シュミット法で正規直交化したものをｘｉ，ｙｉとおく（ｉ＝１，２，３）。また，ｘ４，ｙ４は全要素が等しくノルム１のＫ×１ベクトル，０をＫ×１の零ベクトル，Ｏを２Ｋ×８の零行列として，式［数９］を作り，式［数１０］と変形する。ただし，２Ｋ−８本の２Ｋ×１ベクトルであるｗ９，…，ｗ２Ｋは，お互いに正規直交であり，同時に［ｘｋＴ  ０Ｔ］Ｔと［０Ｔ  ｙｋＴ］Ｔにも直交となるように任意に選ばれている。【００３１】
【数９】
2005062147.tif 000011
【００３２】
【数１０】
2005062147.tif 000012
【００３３】ここで，行列Ｌｘｙは［数９］式から，任意のｘｉ，ｙｉ（ｉ＝１〜４）の線形結合を零ベクトルへ写像するので，任意の線形カメラによる画像から線形写像の成分を完全に取り去る作用を持つことがわかる。また，線形代数の言葉を使えば，行列Ｌｘｙは対称性とベキ等性を持つ直交射影行列であり，従って，３Ｄ位置Ｖに対する線形カメラ画像が張る４次元部分空間に対する直交補空間への直交射影行列となっている。【００３４】本発明において利用可能なＲやＷの良い推定を得るには，反復の現段階の３Ｄ位置Ｖを，第１段階で用いた線形カメラの視線方向を軸に１回転させたＮ通りの３Ｄ位置を透視投影カメラで画像化する。更にもし必要であるなら，非特許文献６に従い，レンズ収差や歪を含む画像を作成し，対象点座標のベクトルを生成する。これに上の直交射影行列Ｌｘｙを掛けて非線形写像成分ｅを正確に抽出し，１回転（Ｎ枚）の画像に対する標本平均をとってｅの分散共分散行列Ｒを求める。これにランダム誤差成分を表す対角行列を加算した後，その逆行列を求め，加重行列Ｗとして利用する。【００３５】以上の計算処理のうち反復を繰返す部分について，図２の流れ図中の各変数を表す符号の肩に，反復の段階［ｊ］等を書き加えて示している。
【図面の簡単な説明】
【００３６】
【図１】透視投影およびレンズの収差や加工歪による非線形歪（矢印）の成分は，空間的な強度の相違とお互いの相関を持つことを示す図である。
【図２】本発明における画像の入力から３次元位置の計算結果を得るまでの流れ図である。
【符号の説明】
【００３７】１０１（黒い点線）    ：不等辺平行５角柱の平行投影画像
１０２（陰影面と白線）：同じ物体の透視投影画像
１０３（全部の矢印）  ：対象点の２次元座標の透視投影等による非線形歪成分ベクトル
ｖ  ：実際のカメラにより撮影されたＭ枚の２次元画像の対象点の座標。
Ｖ［ｊ］：反復の第ｊ段階における対象点の３次元位置の計算結果。
Ｃ［ｊ］：Ｍ枚の画像を撮影したカメラを最良近似するアフィンカメラ行列を縦に積み上げた行列。
Ｂ［ｊ］：Ｃ［ｊ］をＫ個主対角上に並べたブロック対角行列。
Ｌｘｙ［ｊ］：Ｖ［ｊ−１］の線形カメラによる画像が張る４次元部分空間の直行補空間への直交射影行列。
Ｒ［ｊ］：Ｖ［ｊ−１］を実際のカメラで撮影した画像に含まれる非線形成分などの誤差ｅの分散共分散行列。
Ｗ［ｊ］：Ｒ［ｊ］の逆行列として得られる加重行列。
【図１】
2005062147.tif 000013
【図２】
2005062147.tif 000014