(57)【要約】【課題】  観測対象を複数方向から撮影して複数の距離画像の位置合わせをより少ないメモリ容量でより迅速に行なう。【解決手段】  シーン画像の各メッシュに重複しないインデックス値を割り当て、このインデックス値を重複しない色に変換してそれぞれのメッシュの色とし、この色を用いてシーン画像像の視線方向から透視変換で割り当てた色によってメッシュを描画してインデックス画像を生成する。そして、モデル画像上の各頂点を、シーン画像の視線方向から透視変換によってインデックス画像に投影し、インデックス画像上に投影された各頂点の座標値から対応するインデックス画像上の色を取得し、この色をシーン画像の対応するインデックス値に逆変換することによって対応点を得る。この結果、位置合わせにおける対応点探索を迅速に行なうことができる。【選択図】        図７
2006202152.tif 000002
【特許請求の範囲】
【請求項１】
観測対象を複数の方向から撮影して得られる複数の距離画像の同一座標系における相対位置を演算することにより前記観測対象の三次元モデルを調整する画像処理装置であって、
前記複数の距離画像を記憶する画像記憶手段と、
該画像記憶手段に記憶した複数の距離画像のうちの任意の二つの画像に対し、該任意の二つの画像のうちの一方の画像の撮影方向から重複しないインデックス値を伴った描画要素を用いて前記観測対象を描画してなるインデックス画像を形成すると共に該形成したインデックス画像における前記任意の二つの画像のうちの他方の画像上の頂点に対応する描画要素に基づいて該頂点に対応する前記一方の画像上の対応点を特定することにより該任意の二つの画像に対する対応点を探索する対応点探索処理と、前記探索された前記複数の距離画像におけるすべての対応点間距離が最小化するよう前記複数の距離画像の前記同一座標系への変換行列を演算する変換行列演算処理と、を所定の終了条件が成立するまで繰り返し実行する位置合わせ処理手段と、
を備える画像処理装置。
【請求項２】
前記対応点探索処理は、前記任意の二つの画像のうちの他方の画像上の頂点を前記インデックス画像を描画したときの視線方向で見たときに該インデックス画像に投影される点に対応する描画要素に基づいて該頂点に対応する前記一方の画像上の対応点を特定することにより前記任意の二つの画像に対する対応点を探索する処理である請求項１記載の画像処理装置。
【請求項３】
前記対応点探索処理は、重複しない色のデータをもった微小区分を前記描画要素として前記観測対象を描画することによりインデックス画像を形成すると共に該形成したインデックス画像における前記他方の画像上の頂点に対応する微小区分の色のデータに基づいて該頂点に対応する前記一方の画像上の対応点を特定することにより前記任意の二つの画像に対する対応点を探索する処理である請求項１または２記載の画像処理装置。
【請求項４】
前記対応点探索処理は、重複しない色のデータをもった点を前記描画要素として前記観測対象を描画することによりインデックス画像を形成すると共に該形成したインデックス画像における前記他方の画像上の頂点に対応する微小領域に含まれる点の色のデータに基づいて該頂点に対応する前記一方の画像上の対応点を特定することにより前記任意の二つの画像に対する対応点を探索する処理である請求項１または２記載の画像処理装置。
【請求項５】
前記色のデータはＲＧＢデータである請求項３または４記載の画像処理装置。
【請求項６】
請求項３ないし５いずれか記載の画像処理装置であって、
グラフィックスを処理するグラフィックス用処理回路を備え、
前記位置合わせ処理手段は、前記インデックス画像の作成を前記グラフィックス用処理回路を用いて行なう手段である
画像処理装置。
【請求項７】
観測対象を複数の方向から撮影して得られる複数の距離画像の同一座標系における相対位置を演算することにより前記観測対象の三次元モデルを調整する画像処理方法であって、
（ａ）前記複数の距離画像のうちの任意の二つの画像に対し、該任意の二つの画像のうちの一方の画像の撮影方向から重複しないインデックス値を伴った描画要素を用いて前記観測対象を描画してなるインデックス画像を形成すると共に該形成したインデックス画像における前記任意の二つの画像のうちの他方の画像上の頂点に対応する描画要素に基づいて該頂点に対応する前記一方の画像上の対応点を特定することにより該任意の二つの画像に対する対応点を探索するステップと、
（ｂ）前記探索された前記複数の距離画像におけるすべての対応点間距離が最小化するよう前記複数の距離画像の前記同一座標系への変換行列を演算するステップと、
を有し、所定の終了条件が成立するまで前記ステップ（ａ）およびステップ（ｂ）を繰り返し実行することを特徴とする画像処理方法。
【請求項８】
前記ステップ（ａ）は、重複しない色のデータをもった微小区分を前記描画要素として前記観測対象を描画することによりインデックス画像を形成すると共に該形成したインデックス画像における前記他方の画像上の頂点に対応する微小区分の色のデータに基づいて該頂点に対応する前記一方の画像上の対応点を特定することにより前記任意の二つの画像に対する対応点を探索するステップである請求項７記載の画像処理方法。
【請求項９】
観測対象を複数の方向から撮影して得られる複数の距離画像を記憶する画像記憶装置を備えるコンピュータを前記複数の距離画像の同一座標系における相対位置を演算することにより前記観測対象の三次元モデルを調整する画像処理装置として機能させる画像処理用プログラムであって、
前記画像記憶装置に記憶している前記複数の距離画像のうちの任意の二つの画像に対し、該任意の二つの画像のうちの一方の画像の撮影方向から重複しないインデックス値を伴った描画要素を用いて前記観測対象を描画してなるインデックス画像を形成すると共に該形成したインデックス画像における前記任意の二つの画像のうちの他方の画像上の頂点に対応する描画要素に基づいて該頂点に対応する前記一方の画像上の対応点を特定することにより該任意の二つの画像に対する対応点を探索する対応点探索モジュールと、
前記探索された前記複数の距離画像におけるすべての対応点間距離が最小化するよう前記複数の距離画像の前記同一座標系への変換行列を演算する変換行列演算モジュールと、
所定の終了条件が成立するまで対応点探索モジュールによる対応点の探索と前記変換行列演算モジュールによる変換行列の演算を繰り返し実行することを特徴とする画像処理用プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置および画像処理方法並びにこれらに用いるプログラムに関し、詳しくは、観測対象を複数の方向から撮影して得られる複数の距離画像の同一座標系における相対位置を演算することにより前記観測対象の三次元モデルを調整する画像処理装置およびこうした装置における画像処理方法並びに観測対象を複数の方向から撮影して得られる複数の距離画像を記憶する画像記憶装置を備えるコンピュータを前記複数の距離画像の同一座標系における相対位置を演算することにより前記観測対象の三次元モデルを調整する画像処理装置として機能させる画像処理用プログラムに関する。
【背景技術】
【０００２】
近年，レーザレンジセンサとModeling from reality技術の発達により、文化遺産や美術品の形状を３次元モデルとして保存する試みが世界各地で行われている。観測対象の３次元モデル化は、観測対象を複数方向から撮影して複数の距離画像を取得し、この複数の距離画像を同一座標系に位置合わせすることにより行なわれる。複数の距離画像の同一座標系における相対位置を求めるいわゆる位置合わせ処理としては、ＩＣＰ  （Iterative Closest Point  非特許文献１参照）法がよく知られている。ＩＣＰ法では、２つの距離画像中の最近傍点を対応点として、この対応点間距離を最小化するような各距離画像の変換行列を求め、繰返し計算によって相対位置を求めていく。
【非特許文献１】P. J. Besl and N. D. McKay, A method for registration of 3-D shapes, IEEE Transactions on Pattern Analysis and Machine Intelligence, 14(2) 1992, 239-256.
【発明の開示】
【発明が解決しようとする課題】
【０００３】
上述のＩＣＰ法では、最近傍点を全ての頂点に対して計算するため、対応する２枚の距離画像の頂点数を等しくＮとした場合、対応点探索の計算量はＯ（Ｎ2）となり、対応点探索に時間を要する。こうした対応点探索をより高速に行なうために、探索木（kd-tree）を用いる手法やkd-treeに加えて近傍点をキャッシュしておくことにより探索範囲を狭める手法，多重解像度と近傍探索を組合せた手法などが提案されているが、若干の計算量を低減できるものの、飛躍的に計算量を少なくすることができなかったり、計算量は少ないものの収束が遅いために対応点探索に時間を要してしまう。
【０００４】
本発明の画像処理装置および画像処理方法並びにこれらに用いるプログラムは、観測対象を複数方向から撮影して複数の距離画像の位置合わせをより迅速に行なうことを目的の一つとする。また、本発明の画像処理装置および画像処理方法並びにこれらに用いるプログラムは、観測対象を複数方向から撮影して複数の距離画像の位置合わせをより少ないメモリ容量で行なうことを目的の一つとする。
【課題を解決するための手段】
【０００５】
本発明の画像処理装置および画像処理方法並びにこれらに用いるプログラムは、上述の目的の少なくとも一部を達成するために以下の手段を採った。
【０００６】
本発明の画像処理装置は、
観測対象を複数の方向から撮影して得られる複数の距離画像の同一座標系における相対位置を演算することにより前記観測対象の三次元モデルを調整する画像処理装置であって、
前記複数の距離画像を記憶する画像記憶手段と、
該画像記憶手段に記憶した複数の距離画像のうちの任意の二つの画像に対し、該任意の二つの画像のうちの一方の画像の撮影方向から重複しないインデックス値を伴った描画要素を用いて前記観測対象を描画してなるインデックス画像を形成すると共に該形成したインデックス画像における前記任意の二つの画像のうちの他方の画像上の頂点に対応する描画要素に基づいて該頂点に対応する前記一方の画像上の対応点を特定することにより該任意の二つの画像に対する対応点を探索する対応点探索処理と、前記探索された前記複数の距離画像におけるすべての対応点間距離が最小化するよう前記複数の距離画像の前記同一座標系への変換行列を演算する変換行列演算処理と、を所定の終了条件が成立するまで繰り返し実行する位置合わせ処理手段と、
を備えることを要旨とする。
【０００７】
この本発明の画像処理装置では、画像記憶手段に記憶した複数の距離画像のうちの任意の二つの画像に対し、任意の二つの画像のうちの一方の画像の撮影方向から重複しないインデックス値を伴った描画要素を用いて観測対象を描画してなるインデックス画像を形成すると共にこの形成したインデックス画像における任意の二つの画像のうちの他方の画像上の頂点に対応する描画要素に基づいて頂点に対応する一方の画像上の対応点を特定することにより任意の二つの画像に対する対応点を探索する対応点探索処理と、こうして探索された複数の距離画像におけるすべての対応点間距離が最小化するよう複数の距離画像の同一座標系への変換行列を演算する変換行列演算処理と、を所定の終了条件が成立するまで繰り返し実行する。インデックス画像を用いて対応点を探索するから、対応する２枚の距離画像の頂点数を等しくＮとしたときには対応点探索の計算量をＯ（Ｎ）とすることができる。この結果、ＩＣＰ法の対応点探索の計算量であるＯ（Ｎ2）に比して計算量を著しく小さくすることができ、より少ないメモリ容量で同時位置合わせをより迅速に行なうことができる。
【０００８】
こうした本発明の画像処理装置において、前記対応点探索処理は、前記任意の二つの画像のうちの他方の画像上の頂点を前記インデックス画像を描画したときの視線方向で見たときに該インデックス画像に投影される点に対応する描画要素に基づいて該頂点に対応する前記一方の画像上の対応点を特定することにより前記任意の二つの画像に対する対応点を探索する処理であるものとすることもできる。
【０００９】
また、本発明の画像処理装置において、前記対応点探索処理は、重複しない色のデータをもった微小区分を前記描画要素として前記観測対象を描画することによりインデックス画像を形成すると共に該形成したインデックス画像における前記他方の画像上の頂点に対応する微小区分の色のデータに基づいて該頂点に対応する前記一方の画像上の対応点を特定することにより前記任意の二つの画像に対する対応点を探索する処理であるものとすることもできる。こうすれば、色のデータを持った微小区分を用いて観測対象を描画するから、頂点に対応する微小区分の色のデータからインデックス値を取得し、このインデックス値から対応点を特定することができる。ここで、色のデータとしては２４ビットのＲＧＢデータとすることもできる。
【００１０】
さらに、本発明の画像処理装置において、前記対応点探索処理は、重複しない色のデータをもった点を前記描画要素として前記観測対象を描画することによりインデックス画像を形成すると共に該形成したインデックス画像における前記他方の画像上の頂点に対応する微小領域に含まれる点の色のデータに基づいて該頂点に対応する前記一方の画像上の対応点を特定することにより前記任意の二つの画像に対する対応点を探索する処理であるものとすることもできる。こうすれば、頂点に対応する微小領域に属する色のデータをもった点の色のデータからインデックス値を取得し、このインデックス値から対応点を特定することができる。ここで、色のデータとしては２４ビットのＲＧＢデータとすることもできる。
【００１１】
このように色のデータをもった描画要素を用いてインデックス画像を作成する態様の本発明の画像処理装置において、グラフィックスを処理するグラフィックス用処理回路を備え、前記位置合わせ処理手段は前記インデックス画像の作成を前記グラフィックス用処理回路を用いて行なう手段であるものとすることもできる。こうすれば、グラフィックスの処理をグラフィックス用処理回路で行なうことができるから、同時位置合わせをより迅速に行なうことができる。
【００１２】
本発明の画像処理方法は、
観測対象を複数の方向から撮影して得られる複数の距離画像の同一座標系における相対位置を演算することにより前記観測対象の三次元モデルを調整する画像処理方法であって、
（ａ）前記複数の距離画像のうちの任意の二つの画像に対し、該任意の二つの画像のうちの一方の画像の撮影方向から重複しないインデックス値を伴った描画要素を用いて前記観測対象を描画してなるインデックス画像を形成すると共に該形成したインデックス画像における前記任意の二つの画像のうちの他方の画像上の頂点に対応する描画要素に基づいて該頂点に対応する前記一方の画像上の対応点を特定することにより該任意の二つの画像に対する対応点を探索するステップと、
（ｂ）前記探索された前記複数の距離画像におけるすべての対応点間距離が最小化するよう前記複数の距離画像の前記同一座標系への変換行列を演算するステップと、
を有し、所定の終了条件が成立するまで前記ステップ（ａ）およびステップ（ｂ）を繰り返し実行することを特徴とする。
【００１３】
この本発明の画像処理方法では、（ａ）複数の距離画像のうちの任意の二つの画像に対し、任意の二つの画像のうちの一方の画像の撮影方向から重複しないインデックス値を伴った描画要素を用いて観測対象を描画してなるインデックス画像を形成すると共にこの形成したインデックス画像における任意の二つの画像のうちの他方の画像上の頂点に対応する描画要素に基づいて頂点に対応する一方の画像上の対応点を特定することにより任意の二つの画像に対する対応点を探索するステップと、（ｂ）こうして探索された複数の距離画像におけるすべての対応点間距離が最小化するよう複数の距離画像の同一座標系への変換行列を演算するステップと、を有し、所定の終了条件が成立するまで繰り返し実行する即ち、対応する２枚の距離画像の頂点数を等しくＮとしたときには対応点探索の計算量をＯ（Ｎ）とすることができる。この結果、ＩＣＰ法の対応点探索の計算量であるＯ（Ｎ2）に比して計算量を著しく小さくすることができ、より少ないメモリ容量で同時位置合わせをより迅速に行なうことができる。
【００１４】
こうした本発明の画像処理方法において、前記ステップ（ａ）は、重複しない色のデータをもった微小区分を前記描画要素として前記観測対象を描画することによりインデックス画像を形成すると共に該形成したインデックス画像における前記他方の画像上の頂点に対応する微小区分の色のデータに基づいて該頂点に対応する前記一方の画像上の対応点を特定することにより前記任意の二つの画像に対する対応点を探索するステップであるものとすることもできる。こうすれば、ここで、色のデータとしてはＲＧＢデータ、例えば、２４ビットのＲＧＢデータとすることもできる。
【００１５】
本発明の画像処理用プログラムは、
観測対象を複数の方向から撮影して得られる複数の距離画像を記憶する画像記憶装置を備えるコンピュータを前記複数の距離画像の同一座標系における相対位置を演算することにより前記観測対象の三次元モデルを調整する画像処理装置として機能させる画像処理用プログラムであって、
前記画像記憶装置に記憶している前記複数の距離画像のうちの任意の二つの画像に対し、該任意の二つの画像のうちの一方の画像の撮影方向から重複しないインデックス値を伴った描画要素を用いて前記観測対象を描画してなるインデックス画像を形成すると共に該形成したインデックス画像における前記任意の二つの画像のうちの他方の画像上の頂点に対応する描画要素に基づいて該頂点に対応する前記一方の画像上の対応点を特定することにより該任意の二つの画像に対する対応点を探索する対応点探索モジュールと、
前記探索された前記複数の距離画像におけるすべての対応点間距離が最小化するよう前記複数の距離画像の前記同一座標系への変換行列を演算する変換行列演算モジュールと、
所定の終了条件が成立するまで対応点探索モジュールによる対応点の探索と前記変換行列演算モジュールによる変換行列の演算を繰り返し実行することを特徴とする。
【００１６】
この本発明の画像処理用プログラムでは、このプログラムをコンピュータにインストールすると共に起動することにより、コンピュータを上述した本発明の画像処理装置として機能させることができる。即ち、画像記憶装置に記憶した複数の距離画像のうちの任意の二つの画像に対し、任意の二つの画像のうちの一方の画像の撮影方向から重複しないインデックス値を伴った描画要素を用いて観測対象を描画してなるインデックス画像を形成すると共にこの形成したインデックス画像における任意の二つの画像のうちの他方の画像上の頂点に対応する描画要素に基づいて頂点に対応する一方の画像上の対応点を特定することにより任意の二つの画像に対する対応点を探索する対応点探索処理と、こうして探索された複数の距離画像におけるすべての対応点間距離が最小化するよう複数の距離画像の同一座標系への変換行列を演算する変換行列演算処理と、を所定の終了条件が成立するまで繰り返し実行する。インデックス画像を用いて対応点を探索するから、対応する２枚の距離画像の頂点数を等しくＮとしたときには対応点探索の計算量をＯ（Ｎ）とすることができる。この結果、ＩＣＰ法の対応点探索の計算量であるＯ（Ｎ2）に比して計算量を著しく小さくすることができ、より少ないメモリ容量で同時位置合わせをより迅速に行なうことができる。
【発明を実施するための最良の形態】
【００１７】
次に、本発明を実施するための最良の形態を実施例を用いて説明する。
【実施例】
【００１８】
図１は、本発明の一実施例としての画像処理装置２０の構成の概略を示す構成図である。実施例の画像処理装置２０は、図示するように、汎用のコンピュータに画像処理用のプログラムをインストールして起動したものとして構成されており、図示しないＣＰＵやＲＯＭ，ＲＡＭ，入出力ポートなどのハードウエアとインストールされたプログラムとにより機能ブロックとして、観測対象を複数の方向から撮影して得られた複数の距離画像の入出力を処理する画像入出力処理部２２と、観測対象の幾何形状を近似するメッシュ（例えばポリゴン）を設定する前処理部２３と、入力した複数の距離画像を同一の座標系で表現するための対応付け（アライメント）を行なうアライメント処理部２４と、距離画像の測定において発生した測定誤差の補正処理（リファイメント）を行なうリファイメント処理部２５と、位置合わせされ誤差補正された複数の距離画像を統合して単一面から構成される観測対象の三次元モデルを生成するマージング処理部２６と、観測対象を複数の方向から撮影して得られた複数の距離画像を記憶する画像機億部２７と、グラフィックスの処理を迅速に行なうグラフィックス処理回路２８と、を備える。こうした各機能ブロックはハードウエアとソフトウエアとが一体となって機能する。なお、実施例の画像処理装置２０は、汎用のコンピュータとして構成されているから、上述した各部の他に、ディスプレイなどの表示部やキーボードやマウスなどの入力部なども備えるがそれらの詳細については省略した。
【００１９】
次に、こうして構成された実施例の画像処理装置２０の動作について説明する。図２は、観測対象の三次元モデルを生成する際に実施例の画像処理装置２０により実行される三次元モデル化処理の一例を示すフローチャートである。三次元モデル化処理では、まず、レンジセンサを用いて複数の方向から撮影された複数の距離画像を入力して画像機億部２７に記憶する処理を実行する（ステップＳ１００）。そして、観測対象の幾何形状を近似するメッシュ（例えばポリゴンなどの微小面）を設定する前処理を行なう（ステップＳ１１０）。ここで、メッシュの形状としては三角形やその他の多角形，楕円などを用いることができる。続いて、画像記憶部２７に記憶した複数の距離画像を同一の座標系で表現するための対応付け（アライメント）を行なう（ステップＳ１２０）。このアライメントは、実施例では同時位置合わせにより行なわれるが、これについては後述する。次に、距離画像の測定において発生した測定誤差の補正処理（リファイメント）を行ない（ステップＳ１３０）、位置合わせされ測定誤差の補正処理がなされた複数の距離画像を統合して単一面から構成される観測対象の三次元モデルを生成する（ステップＳ１４０）。
【００２０】
ステップＳ１２０のアライメントは、実施例では、図３に例示する同時位置合わせ処理により実行される。実施例の同時位置合わせ処理は、画像記憶部２７に記憶された複数の距離画像の各頂点に各画像の対応点を探索する対応点探索処理と（ステップＳ２００）、得られた全ての対応点間の誤差を計算する誤差計算処理と（ステップＳ２１０）、計算された全ての誤差を最小化するように各距離画像の変換行列を演算する変換行列演算処理と（ステップＳ２２０）、を終了条件が成立するまで（ステップＳ２３０）、繰り返し実行することにより行なわれる。
【００２１】
対応点探索処理は、図４に示すように、まず、画像記憶部２７に記憶された複数の距離画像のうち任意の２つの距離画像を選択し（ステップＳ３００）、一方の距離画像（以下、シーン画像と呼ぶ）に対応するインデックス画像を作成する（ステップＳ３１０）。インデックス画像は、シーン画像の各メッシュに重複しないインデックス値を割り当て、このインデックス値を重複しない色に変換してそれぞれのメッシュの色とし、この色を用いてシーン画像像の視線方向から透視変換で割り当てた色によってメッシュを描画することにより作成する。実施例では、２４ビットのＲＧＢ値として色を表現し、インデックス値に対してカウントアップするＲＧＢ値を割り当てるものとした。また、このメッシュの描画処理についてはグラフィックス処理回路２８を用いて行なうものとした。このように、ハードウエアを用いて描画することにより、迅速にインデックス画像を得ることができる。図５に観測対象としての仏像の陰影画像の一例を示し、図６に陰影画像に対応するインデックス画像の一例を示す。図６の例では、仏像は各メッシュに割り当てられた色によるグラデーションとして描画されている。ここで、インデックス値に対応する色とインデックス値とが同じ精度で表わされるならば、インデックス値から色への変換は行なわないものとしてもかまわない。また、角度等間隔で距離画像を撮影したときには、直交座標から極座標に変換して投影するものとしてもよい。次に、インデックス画像を用いて選択した任意の２つの距離画像のうちの他方の距離画像（以下、モデル画像と呼ぶ）上の頂点に対応するシーン画像上の対応点を探索する（ステップＳ３２０）。この対応点の探索は、モデル画像上の各頂点を、シーン画像の視線方向から透視変換によってインデックス画像に投影し、インデックス画像上に投影された各頂点の座標値から対応するインデックス画像上の色（ＲＧＢ値）を取得し、この色（ＲＧＢ値）をシーン画像の対応するインデックス値に逆変換することによって行なうことができる。図７にインデックス画像を用いてモデル画像上の頂点に対応するシーン画像上の対応点を探索する様子について示す。なお、メッシュ描画の際にエイリアシングが生じることもあり、この場合、正しい対応が得られない場合も生じる。この場合、得られた座標を中心とした周囲３×３画素を探索し、対応するシーン画像のメッシュが張る平面上にモデル画像上の頂点を投影することにより正しい対応メッシュを判定するものとしてもよい。こうしたインデックス画像を用いた対応点の探索を画像記憶部２７に記憶された複数の距離画像のすべてに対して繰り返し行なって（ステップＳ３３０）、複数の距離画像のすべてに対して対応点探索を終了すると、この対応点探索処理を終了する。
【００２２】
図３のアライメント処理のステップＳ２１０における誤差計算は、以下の誤差評価式を用いて行なわれる。誤差評価式は、対応する２点間の距離には頂点法線を考慮した点と面の距離を用い、モデル画像上の頂点ｘとそれに対応するシーン画像メッシュ上の点ｙとし、ｎを頂点ｘの法線ｎxと対応点ｙの法線ｎyの平均とすると、次式（１）および式（２）のようになる。ここでＲM，ｔMはモデル画像の回転，平行移動行列であり、ＲS，ｔSはシーン画像の回転，平行移動行列である。なお、簡単化のためにｎに掛かる回転行列はＲMとした。
【数１】
2006202152.tif 000003
【００２３】
これを全ての距離画像の組合せ（ｉ，ｊ）が含む全頂点ｋに対して計算し、次式（３）で定義される二乗誤差ε2を求める。式（３）に示した誤差評価式は、このままでは非線形であり、最小化計算が難しいため、これを線形化する。即ち、求める変換の回転角を微小角と仮定すると、回転行列Ｒは次式（４）のように示すことができる。
【数２】
2006202152.tif 000004
【００２４】
また，平行移動行列を次式（５）とすると、全ての距離画像枚数をｎとして式（２）は式（６）〜式（１１）のように変形することができる。
【数３】
2006202152.tif 000005
【００２５】
図３のアライメント処理のステップＳ２２０における変換行列の演算は、以下のように行なわれる。各距離画像の変換行列は，上述の式（６）より最小二乗法によってδを求めることにより行なうことができる。変換行列とδとの関係を次式（１２）に示す。
【数４】
2006202152.tif 000006
【００２６】
実際には０番目の距離画像を移動させないことで一意な解を求めるため、δは((n-1)×6)個の変数をもつ連立一次方程式の解として得られる。全ての距離画像が少なくとも一つ以上の他の距離画像と重なりを持つとき、この連立一次方程式の係数行列は((n-1)×6) ×((n-1)×6)の正値対称行列となる。この係数行列は距離画像枚数が多くなるにつれて非常に大規模な行列となると共に重なり枚数は相対的に少なくなるので疎な行列となる。また、この行列は６×６の非零パターンを持つことも分かる。係数行列の一例を図８に示す。ここで、係数行列が正値対称行列である場合、連立一次方程式の直接解法としてはCholesky分解を用いる方法が一般的である。しかし、Cholesky分解の計算量はＯ(ｎ3)であるため，大規模行列の扱いには適していない。そこで、実施例では、反復法の前処理付き共役勾配法（ＰＣＧ）を用いた。特に、この係数行列は６×６の非零パターンを持つ疎行列であることが分かっているため、これに特化した不完全Cholesky分解共役勾配法（ＩＣＣＧ）を用いることにより高速に計算することが可能となる。
【００２７】
実施例では、画像処理装置２０のＣＰＵとしてArhlonMP2400+プロセッサ、ＲＡＭとして2GByteメモリ、グラフィックス処理回路２８としてGeForceTi4600グラフィックカードを用いて図９に示す「デーヴァ尊顔」をモデル１として、図１０に示す「奈良大仏」の距離画像をモデル２として用いて位置合わせを行なった。なお、デーヴァ尊顔の距離画像に対する緒言を図１１に、奈良大仏の距離画像に対する緒言を図１２に示す。ここで、VIVID900は近距離用のセンサであり、ＣＣＤカメラとレーザを用いた光切断法によって形状を測定する。測定解像度はＣＣＤの画素数によって定められている。Cyrax2500はtime-of-flight方式のスキャニング機構を持つ長距離用レンジセンサであり、モーター制御により測定間隔（角度）や測定解像度を自由に変えることができる。また、測定範囲内でも測定されなかったデータ点は用いないため、これらの距離画像は異なった測定解像度をもっている。実施例では、実際に測定された距離画像のデータ量が非常に多く、メモリ空間の制約から１／４に間引いたデータを使用して位置合わせを行なった。
【００２８】
まず、探索に用いるインデックス画像と実施例の手法によって得られる対応点数の関係について検証する。前述したように、インデックス画像の描画の際には、エイリアシングが起こる場合や解像度が低いために全てのメッシュが描画されない場合がある。つまり、十分な対応点数を得るためには、インデックス画像に十分な解像度を割当てる必要がある。図１３にモデル１，２の各最小，最大メッシュ数を持つ距離画像をシーン画像とした場合のインデックス画像の解像度と得られる対応点数との関係を示す。これらのシーン画像に対するモデル画像は任意である。図中の対応点数は、実際の対応点数ｖcと本手法を用いて得られた対応点数ｖ’cの比で表されている。この図から分かるように、インデックス画像がある一定以上の解像度であれば、ほぼ全ての対応点が得られる。また、メッシュ数によって必ずしも画像解像度が定まるわけではないが、他の距離画像の結果もほぼこれらの範囲に収まる。この場合では、800×800程度の解像度があれば十分な数の対応点が得られることが分かる。実際に十分な対応点を得るために必要なインデックス画像の解像度は、センサの測定解像度によって決まる。ただし、ある程度以上の解像度が割当てられていれば十分な対応点が得られるため、最も解像度を必要とするデータに合わせて解像度を決めれば良い。つまり、全ての距離画像に対して同じ大きさの画像を用いることができる。そこで実施例では、経験的に十分であると思われる値（12002〜16002）を用いて位置合わせ処理を行なった。
【００２９】
次に，距離画像に含まれる頂点数に対する計算時間を評価する。この評価のために、モデル１及びモデル２の全ての距離画像を用いて同じ距離画像同士の１対１の位置合わせを行った。計算時間は対応点数にも影響されるので、互いの位置は移動させず頂点数と対応点数がほぼ等しくなるようにした。計算時間は１回の反復計算に要する時間とし、複数回の反復計算を行ったときの平均時間を評価した。頂点数の計算時間との関係の一例を図１４に示す。この例から分かるように、頂点数に対する計算時間はほぼ線形に増加する。また、モデル１とモデル２の実験では、それぞれ距離閾値ｌth以外のパラメータは変更していない。つまり、本手法の効率はセンサや測定状況には依存しないと言える。
【００３０】
続いて、変換行列の計算時間について評価する。前述のように、行列計算の時間は距離画像の枚数に大きく影響される。そこで、距離画像枚数と行列計算時間の関係について検証する。実験では、距離画像枚数を変えて同時位置合わせを行い、変換行列の計算時間のみを測定した。この実験にはモデル２の距離画像を使用した。図１５に距離画像枚数と行列計算時間の関係を示す。比較のために本手法とCholesky分解を用いた場合の二つの結果を示す。このときのＩＣＣＧの誤差閾値は10-6とした。この実験から、距離画像枚数が６０枚以下の場合は Cholesky分解を用いた方が計算時間は短いことが分かる。しかし、Cholesky分解の計算量はＯ(ｎ3)であり急激に計算時間が増加するため、距離画像枚数が７０枚以上になるとＩＣＣＧを用いた場合の方が計算時間は短くなる。ただし、ＩＣＣＧを用いた場合の行列計算の計算量はCholesky分解を用いた場合よりも少ないが、計算量はＯ(ｎ)以下にはならない。そのため，距離画像枚数が更に増加した場合は大きな問題になると考えられる。
【００３１】
実施例における同時位置合わせに要する時間は、モデル１の同時位置合わせを２０回の反復計算で行なった場合には１７３８秒であり、モデル２の同時位置合わせを２０回の反復計算で行なった場合には７８３２秒であった。インデックス画像を用いない従来の手法による場合に比して１／１００〜１／５０００程度の時間で行なうことができた。
【００３２】
以上説明した実施例の画像処理装置２０によれば、シーン画像に対応するインデックス画像を用いてモデル画像上の頂点に対応するシーン画像上の対応点を探索するから、対応点探索に要する計算量を少なくすることができる。この結果、距離画像の同時位置合わせをより少ないメモリ容量でより迅速に行なうことができる。しかも、インデックス画像をグラフィックス処理回路２８を用いて作成するから、ソフト上で作成する場合に比してその処理を迅速に行なうことができる。この結果、対応点探索に要する時間を短くすることができる。
【００３３】
実施例の画像処理装置２０では、シーン画像に対応するインデックス画像を作成し、このインデックス画像を用いてモデル画像上の頂点に対応するシーン画像上の対応点を探索するものとしたが、モデル画像の各頂点に重複しないインデックス値を割当て、それを重複しない色に変換し、モデル画像の視線方向に投影して頂点インデックス画像を作成し、この頂点インデックス画像を用いて対応点を探索するものとしてもよい。この場合、対応点探索は、シーン画像のメッシュに含まれる頂点を、モデル画像の視線方向から画像面に投影して矩形領域を得、この矩形領域に含まれる頂点にシーン画像のメッシュ番号を登録することにより行なうことができる。この場合、一つの頂点に複数のメッシュが対応する場合もあるが、対応メッシュとの距離を記録しておき、投影されたメッシュとの距離が既に記録されたメッシュの距離より小さい場合のみ更新すればよい。頂点インデックス画像を用いて対応点探索している様子を図１６に示す。
【００３４】
実施例の画像処理装置２０では、ＣＰＵとしてArhlonMP2400+プロセッサ、ＲＡＭとして2GByteメモリ、グラフィックス処理回路２８としてGeForceTi4600グラフィックカードを用いるものとしたが、こうしたスペックに限定されるものではなく、如何なるプロセッサやグラフィックカードを用いるものとしてもかまわない。
【００３５】
以上、本発明を実施するための最良の形態について実施例を用いて説明したが、本発明はこうした実施例に何等限定されるものではなく、本発明の要旨を逸脱しない範囲内において、種々なる形態で実施し得ることは勿論である。
【産業上の利用可能性】
【００３６】
本発明は、画像処理装置の製造産業などに利用可能である。
【図面の簡単な説明】
【００３７】
【図１】本発明の一実施例としての画像処理装置２０の構成の概略を示す構成図である。
【図２】実施例の画像処理装置２０により実行される三次元モデル化処理の一例を示すフローチャートである。
【図３】同時位置合わせ処理の一例を示すフローチャートである。
【図４】対応点探索処理の一例を示すフローチャートである。
【図５】観測対象としての仏像の陰影画像の一例を示す説明図である。
【図６】陰影画像に対応するインデックス画像の一例を示す説明図である。
【図７】インデックス画像を用いてモデル画像上の頂点に対応するシーン画像上の対応点を探索する様子を示す説明図である。
【図８】係数行列の一例を示す説明図である。
【図９】モデル１のデーヴァ尊顔の距離画像の一例を示す説明図である。
【図１０】モデル２の奈良大仏の距離画像の一例を示す説明図である。
【図１１】モデル１のデーヴァ尊顔の距離画像に対する緒言を一覧表示する説明図である。
【図１２】モデル２の奈良大仏の距離画像に対する緒言を一覧表示する説明図である。
【図１３】モデル１，２の各最小，最大メッシュ数を持つ距離画像をシーン画像とした場合のインデックス画像の解像度と得られる対応点数との関係の一例を示す説明図である。
【図１４】頂点数の計算時間との関係の一例を示す説明図である。
【図１５】距離画像枚数と行列計算時間の関係の一例を示す説明図である。
【図１６】頂点インデックス画像を用いて対応点探索している様子を示す説明図である。
【符号の説明】
【００３８】
２０  画像処理装置、２２  画像入出力処理部、２３  前処理部、２４  アライメント処理部、２５  リファイメント処理部、２６マージング処理部、２７  画像記億部、２８グラフィックス処理回路。
【図１】
2006202152.tif 000007
【図３】
2006202152.tif 000008
【図４】
2006202152.tif 000009
【図１１】
2006202152.tif 000010
【図１２】
2006202152.tif 000011
【図２】
2006202152.tif 000012
【図５】
2006202152.tif 000013
【図６】
2006202152.tif 000014
【図７】
2006202152.tif 000015
【図８】
2006202152.tif 000016
【図９】
2006202152.tif 000017
【図１０】
2006202152.tif 000018
【図１３】
2006202152.tif 000019
【図１４】
2006202152.tif 000020
【図１５】
2006202152.tif 000021
【図１６】
2006202152.tif 000022