(57)【要約】【課題】  あるシーンの３次元再構成を、そのシーンの複数の画像から、カラーセグメンテーションベースの手法に基づいて計算するためのシステムおよびプロセスを提供する。【解決手段】  最初に、各画像が個別にセグメント化される。次いで、初期ディスパリティー空間分布（ＤＳＤ）が、セグメント内のすべての画素が同一のディスパリティーを有するとの想定を用いて、各セグメントごとに計算される。次に、隣接セグメントと、そのセグメントの他の画像への投影とを用いて、各セグメントのＤＳＤが精緻化される。次いで、各セグメントが単一のディスパリティーを有するという想定は、ディスパリティー平滑化ステージの間に緩和される。その結果、各画像ごとにディスパリティーマップが得られ、再構成アプリケーションが要求した場合には、そのマップを順に使用して画素ごとの奥行マップが計算される。【選択図】  図２
2006012166.tif 000002
【特許請求の範囲】
【請求項１】
あるシーンの３次元再構成を、様々な視点からキャプチャされた前記シーンの複数の画像から計算するためのコンピュータ実装されたプロセスであって、コンピュータを使用して実施する、
各画像を、その領域の各画素が類似のディスパリティーを示すものと思われる、前記画像の各領域を表すセグメントに分割するプロセスアクションと、
セグメント内のすべての画素が同一のディスパリティーを有するとの想定を用いて、各画像の各セグメントごとに初期ディスパリティー空間分布（ＤＳＤ）を計算するプロセスアクションであって、あるセグメントの前記初期ＤＳＤが、一組の候補のディスパリティーの各々に対して前記セグメント内の各画素が個々のディスパリティーを示す確率の初期推定値を含むプロセスアクションと、
各画像の各セグメントごとに、前記初期ＤＳＤの前記ディスパリティー確率の前記初期推定値を、同一の画像内の隣接セグメントとの間の平滑性制約、および前記シーンの同一部分を描写する他の画像内の対応するセグメントとの間の一貫性制約を同時に実施して精緻化することによって、精緻化されたＤＳＤを生成するプロセスアクションと、
各画像の各セグメントごとに、前記セグメントの前記精緻化されたＤＳＤの最大確率値に対応するディスパリティーを、前記セグメントの各画素に割り当てるプロセスアクションと、
各画像ごとに、各画素に割り当てられた前記ディスパリティーを、前記シーンの同一部分を描写する他の画像内の対応する画素のディスパリティーに基づいて平滑化し、次いで、前記画像の同一セグメント内の隣接画素のディスパリティーに基づいて平滑化するプロセスアクションと
を含むことを特徴とするプロセス。
【請求項２】
各画像をセグメントに分割する前記プロセスアクションは、
検討中の画像の各画素を、それぞれのセグメントに割り当てるアクションと、
各画素ごとに順に所定の順序で、前記セグメントの画素の平均色が検討中の画素の色と所定の閾値未満で異なっているときはいつでも、検討中の画素に隣接する所定の数の画素を前記画素に割り当てられた前記セグメントに再割り当てするアクションと、
各セグメントごとに順に、前記セグメントが領域に関する所定の画素数未満かどうかを判定し、前記セグメントが領域に関する前記所定の画素数未満であるときはいつでも、前記セグメントの画素を、検討中のセグメントの平均色に最も近い平均色を有する隣接セグメントに再割り当てするアクションと、
各セグメントごとに順に、前記セグメントが幅方向の所定の画素数を超えているかどうかを判定し、前記セグメントが幅方向の所定の画素数を超えているときはいつでも、前記セグメントを水平方向に必要な数の均等なセグメントに分割して、前記選択されたセグメントの各画素を適切な新しいより幅の狭いセグメントに再割り当てすることによって、前記新しいより幅の狭い各セグメントが幅方向の前記所定の画素数を超えないことを保証するアクションと、
各セグメントごとに順に、前記セグメントが高さ方向の所定の画素数を超えているかどうかを判定し、前記セグメントが高さ方向の所定の画素数を超えているときはいつでも、前記セグメントを垂直方向に必要な数の均等なセグメントに分割して、前記選択されたセグメントの各画素を適切な新しいより背の低いセグメントに再割り当てすることによって、前記新しいより背の低い各セグメントが高さ方向の前記所定の画素数を超えないことを保証するアクションと
を含むことを特徴とする請求項１に記載のプロセス。
【請求項３】
各画像をセグメントに分割する前記プロセスアクションは、前記検討中の画像の各画素をそれぞれのセグメントに割り当てる前記アクションを実施する前に、前記検討中の画像の隣接画素間の色差を平滑化するアクションをさらに含むことを特徴とする請求項２に記載のプロセス。
【請求項４】
前記検討中の画像の隣接画素間の色差を平滑化する前記プロセスアクションは、
各画素ごとにラスター順に、
前記検討中の画素に隣接する所定の数の連続する画素からなる各可能なグループを順に選択するアクションと、
各選択されたグループごとに、前記選択されたグループの各画素の各色成分の光強度を、前記検討中の画素の対応する色成分の光強度から減算し、結果として得られた差の２乗値を加算して前記選択されたグループの総差を生成するアクションと、
最小の総差を示すグループを特定するアクションと、
前記特定されたグループの各画素の色と前記選択された画素の色を平均するアクションと、
結果として得られた平均色を前記選択された画素の現在の色として割り当てるアクションと
を含むことを特徴とする請求項３に記載のプロセス。
【請求項５】
前記色平滑化手順は、所定の回数繰り返されることを特徴とする請求項４に記載のプロセス。
【請求項６】
連続する隣接画素の前記所定の数は、３であることを特徴とする請求項４に記載のプロセス。
【請求項７】
前記所定の順番は、ラスター順であることを特徴とする請求項２に記載のプロセス。
【請求項８】
前記所定の数の隣接画素は、４連結隣接画素（４−ｃｏｎｎｅｃｔｅｄ  ｎｅｉｇｈｂｏｒｓ）を含むことを特徴とする請求項２に記載のプロセス。
【請求項９】
領域に関する前記所定の画素数は、１００画素であることを特徴とする請求項２に記載のプロセス。
【請求項１０】
幅方向の前記所定の画素数は４０画素であり、高さ方向の前記所定の画素数は４０画素であることを特徴とする請求項２に記載のプロセス。
【請求項１１】
前記セグメントの平均色と前記検討中の画素の色との間の前記所定の差の閾値は、８であることを特徴とする請求項２に記載のプロセス。
【請求項１２】
各画像の各セグメントごとに前記初期ＤＳＤを計算する前記プロセスアクションは、
（ａ）一組の候補のディスパリティー、および各候補に対する奥行値を確定するアクションと、
（ｂ）候補のディスパリティーを選択するアクションと、
（ｃ）前記検討中の画像の隣接画像を選択するアクションと、
（ｄ）前記検討中のセグメントの各画素ごとに、
前記選択された候補のディスパリティーに関する前記奥行値を用いて前記画素を前記選択された隣接画像に投影して、前記投影された画素に対応する前記隣接画像中の画素を特定し、
対応する画素が特定された場合は、前記投影された画素と前記隣接画像中の前記特定された画素とに関する１つまたは複数の所定の利得比を計算するアクションと、
（ｅ）画素利得比ヒストグラムを生成するアクションと、
（ｆ）前記画素利得比ヒストグラムにおける３つの連続するビンの最大の和を計算するアクションと、
（ｇ）前記計算された和を、前記検討中のセグメントの、前記選択された候補のディスパリティーにおける前記選択された隣接画像についてのマッチングスコアとして指定するアクションと、
（ｈ）前記検討中の画像の残りの各隣接画像ごとに、アクション（ｃ）から（ｇ）を繰り返すアクションと、
（ｉ）残りの各候補のディスパリティーごとに、アクション（ｂ）から（ｈ）を繰り返すアクションと、
（ｊ）あるマッチングスコアに関連する各ディスパリティーごとに、前記検討中のディスパリティーで、すべての隣接画像について計算されたマッチングスコアの積を、前記マッチングスコアに関連するあらゆるディスパリティーで、すべての隣接画像について計算されたマッチングスコアの積の和によって除算して、前記ディスパリティーについてのＤＳＤ確率を生成するアクションと
を含むことを特徴とする請求項１に記載のプロセス。
【請求項１３】
前記複数の利得比は、各投影された画素および前記特定された隣接画像の各画素ごとに計算され、前記各画素に関する各色成分の利得比を含めて比較されることを特徴とする請求項１２に記載のプロセス。
【請求項１４】
対数スケールを使用して、前記画素利得比ヒストグラムの前記各ビンの範囲を確定することを特徴とする請求項１２に記載のプロセス。
【請求項１５】
前記画素利得比ヒストグラムは２０ビンを含むことを特徴とする請求項１４に記載のプロセス。
【請求項１６】
前記１組の候補のディスパリティーと各候補ごとの奥行値を確定する前記プロセスアクションは、
（ａ）ユーザ指定の最小および最大奥行値を入力するアクションと、
（ｂ）前記ユーザによって指定された前記最小奥行値を用いて、前記複数の画像のうちの視点に関して中央の画像の中心画素を、その隣接画像の１枚に投影するアクションと、
（ｃ）前記最小奥行値を、前記投影された中心画素に対応する隣接画像中の画素に関するディスパリティーに割り当てるアクションと、
（ｄ）前記中心画素を直前の投影から１ディスパリティーの場所に位置するように投影し、前記現在の中心画素の投影に関する奥行値を確定するアクションと、
（ｅ）前記最後に確定された奥行値が前記ユーザ指定の最大奥行値を超えたかどうかを判定するアクションと、
（ｆ）前記最後に確定された奥行値が前記ユーザ指定の最大奥行値を超えていないときはいつでも、前記最後に確定された奥行値がディスパリティーに割り当てられて、ディスパリティーは直前に割り当てられていたディスパリティーから１ディスパリティーレベル分インクリメントされた値に等しくなるアクションと、
（ｇ）最後に確定された奥行値がユーザ指定の最大奥行を超えたとアクション（ｅ）で判定されるまでアクション（ｄ）から（ｆ）が繰り返され、超えたと判定された時点で、奥行値が割り当てられてきた一連のディスパリティーが候補のディスパリティーとして指定されるアクションと
を含むことを特徴とする請求項１２に記載のプロセス。
【請求項１７】
各画像の各セグメントごとに、前記初期ＤＳＤの前記ディスパリティー確率値の前記初期推定値を精緻化する前記プロセスアクションは、
（ａ）各画像の各セグメントごとに、精緻化されたディスパリティー確率値を次式を用いて計算するアクションであって、
【数１】
2006012166.tif 000026
上式で、ｐij（ｄ）はセグメントｓijのディスパリティーｄに関して精緻化されたディスパリティー確率値であり、ｌij（ｄ）は前記平滑性制約を実施する関数であり、ｃijk（ｄ）は一組の隣接画像Ｎiの各隣接画像に関する前記一貫性制約を実施する関数であり、ｄ’は関連する確率値を有するすべてのディスパリティーであるアクションと、
（ｂ）アクション（ａ）を所定の回数繰り返すアクションと
を含むことを特徴とする請求項１に記載のプロセス。
【請求項１８】
前記所定の回数は、５０から６０の範囲であることを特徴とする請求項１７に記載のプロセス。
【請求項１９】
各画像の各画素に割り当てられた前記ディスパリティーを平滑化する前記プロセスアクションは、画像間平滑化を含み、前記画像間平滑化は、各画像の各画素ごとに順に、
前記検討中の画像の各隣接画像ごとに、
前記検討中の画素を前記隣接画像に投影し、前記投影された画素に対応する前記隣接画像中の画素を特定するアクションと、
前記検討中の画素に現在割り当てられている前記ディスパリティーと前記隣接画像中の前記対応する画素に割り当てられたディスパリティーの差の絶対値が所定のディスパリティーレベル数未満のときはいつでも、前記投影された画素と前記対応する画素のディスパリティーを平均し、前記平均を、関係する隣接画像に関するディスパリティー因数として前記検討中の画素に割り当てるアクションと、
前記検討中の画素に現在割り当てられている前記ディスパリティーと前記隣接画像中の前記対応する画素に割り当てられているディスパリティーの差の絶対値が所定のディスパリティーレベル数以上のときはいつでも、前記検討中の画素の前記ディスパリティーを、関係する隣接画像に関するディスパリティー因数として割り当てるアクションと、
前記各隣接画像に関して、前記検討中の画素に割り当てられた前記各ディスパリティー因数を加算し、その和を関係する隣接画像の数によって除算し、その結果を前記画素の現在のディスパリティーとして割り当てるアクションと
を含むことを特徴とする請求項１に記載のプロセス。
【請求項２０】
各画像の各画素に割り当てられている前記ディスパリティーを平滑化する前記プロセスアクションは、画像内平滑化をさらに含み、前記画像内平滑化は、各画像の各セグメントの各画素ごとに、前記検討中の画素を中心にした所定のサイズの窓の内部の画素で、前記検討中のセグメントの外部には存在しない画素に現在割り当てられている前記ディスパリティーを平均し、前記平均を、前記検討中の画素にその最終ディスパリティーとして割り当てるアクションを含むことを特徴とする請求項１９に記載のプロセス。
【請求項２１】
前記画像間平滑化および前記画像内平滑化は、所定の回数繰り返されることを特徴とする請求項２０に記載のプロセス。
【請求項２２】
前記所定のサイズの窓は、５×５画素の窓であることを特徴とする請求項２１に記載のプロセス。
【請求項２３】
前記各画像は前記シーンのある部分を描写し、前記シーンの前記部分は、前記画像のうちの少なくとも１枚の他の画像にキャプチャされた前記シーンの前記部分と、およそ６０から１００パーセントの範囲でオーバラップすることを特徴とする請求項１に記載のプロセス。
【請求項２４】
前記複数の画像は、同時にキャプチャされた動的シーンの画像を表すことを特徴とする請求項１に記載のプロセス。
【請求項２５】
前記同時にキャプチャされた画像は、様々な視点に置かれた複数のビデオカメラによってキャプチャされたビデオフレームを含むことを特徴とする請求項２４に記載のプロセス。
【請求項２６】
前記複数の画像は、様々な視点に置かれた複数のカメラ、あるいは各画像をキャプチャするために視点から視点に移動される単一のカメラによってキャプチャされた静的なシーンの画像を表すことを特徴とする請求項１に記載のプロセス。
【請求項２７】
あるシーンの３次元再構成を、様々な視点からキャプチャされた、前記シーンの複数のオーバラップする画像から計算するシステムであって、
前記シーンの様々な部分を見るために配置された複数のカメラを含むカメラ措置であって、各カメラの視界が各隣接するカメラの視界とオーバラップするカメラ装置と、
汎用コンピュータ装置と、
前記コンピュータ装置によって実行可能なプログラムモジュールを含むコンピュータプログラムと
を含み、前記コンピュータ装置は、前記コンピュータプログラムの前記プログラムモジュールによって、
各画像を、その画素が類似のディスパリティーを示すものと思われる各セグメントに分割し、
各画像の各セグメントごとに、一組の候補のディスパリティーの各々に対して、前記セグメントを構成する前記各画素が個々のディスパリティーを示す尤度を表す確率推定値を含むディスパリティー空間分布（ＤＳＤ）を計算し、
各画像の各セグメントごとに、前記セグメントの前記ＤＳＤの最大確率値に対応するディスパリティーを前記セグメントの各画素に割り当て、
各画像ごとに、前記シーンの同一の部分を描写する隣接画像内の対応する画素のディスパリティー、および前記画像の同一セグメント内の隣接画素のディスパリティーに基づいて、各画素に割り当てられた前記ディスパリティーを平滑化する
ように指示されることを特徴とするシステム。
【請求項２８】
各画像の各セグメントごとに前記ディスパリティー空間分布（ＤＳＤ）を計算するための前記プログラムモジュールは、
各画像の各セグメントごとに初期ディスパリティー空間分布（ＤＳＤ）を計算するサブモジュールと、
各画像の各セグメントごとに前記初期ＤＳＤの前記ディスパリティー確率の前記初期推定値を、前記同一画像内の隣接セグメントとの間の平滑性制約、および前記シーンの前記同一部分を描写する、他の画像内の対応するセグメントとの間の一貫性制約を同時に実施して精緻化することによって、精緻化されたＤＳＤを生成するサブモジュールと
を含むことを特徴とする請求項２７に記載のシステム。
【請求項２９】
各画像の各セグメントごとに、前記初期ＤＳＤの前記ディスパリティー確率の前記初期推定値を精緻化するための前記サブモジュールは、
各画像の各セグメントごとに、精緻化されたディスパリティー確率を次式によって計算するサブモジュールであって、
【数２】
2006012166.tif 000027
上式で、ｐij（ｄ）はセグメントｓijのディスパリティーｄに関して精緻化されたディスパリティー確率値であり、ｌij（ｄ）は前記平滑性制約を実施する関数であり、ｃijk（ｄ）は一組の隣接画像Ｎi内の各隣接画像に関する前記一貫性制約を実施する関数であり、ｄ’は関連する確率値を有するすべてのディスパリティーであるサブモジュールと、
前記精緻化されたディスパリティー確率計算サブモジュールを所定の回数繰り返すサブモジュールと
を含むことを特徴とする請求項２８に記載のシステム。
【請求項３０】
前記平滑性制約を実施する関数は次式を含み、
【数３】
2006012166.tif 000028
上式で、Ｓijはセグメントｓijの隣接セグメントであり、
【数４】
2006012166.tif 000029
はセグメントｓij∈Ｓijの現在の最大ディスパリティー推定値であり、εはオフセットであり、また
【数５】
2006012166.tif 000030
であり、上式で、νは幅スカラであり、
【数６】
2006012166.tif 000031
は
【数７】
2006012166.tif 000032
の最後に計算された確率であり、ｂilはｓilが占めるｓijの境界の割合であり、Δjlはセグメントｓijとｓilの画素の平均色の間の差であり、σΔは色差ガウス分布の分散であることを特徴とする請求項２９に記載のシステム。
【請求項３１】
ε＝０．０１、ν＝８であり、
【数８】
2006012166.tif 000033
であることを特徴とする請求項３０に記載のシステム。
【請求項３２】
前記一貫性制約を実施する関数は次式を含み、
【数９】
2006012166.tif 000034
上式で
【数１０】
2006012166.tif 000035
であり、上式でｐijk（ｄ）は、セグメントｓijの、ディスパリティーｄで隣接画像Ｉkに関して投影されたＤＳＤであり、Ｓijはセグメントｓijの隣接セグメントであり、π（ｋ，ｘ）は画素ｘを投影する画像Ｉk内のセグメントであり、したがって
【数１１】
2006012166.tif 000036
はセグメントπ（ｋ，ｘ）のディスパリティーｄでの確率であり、Ｃijはｓijの画素数であり、ｍijk（ｄ）はセグメントｓijの画像ｋにおけるディスパリティーｄでのマッチング関数であり、また
【数１２】
2006012166.tif 000037
であり、上式でνijはセグメントｓijが画像ｋ内で遮蔽される確率を表し、さらに
【数１３】
2006012166.tif 000038
であり、上式でｏijk（ｄ）は遮蔽関数であり、前記遮蔽関数は、ディスパリティーの推定に基づくｋ番目の画像の奥行において、画像Ｉkでｓijが見えない場合でも、その推定ディスパリティーに基づくｓijの奥行が表面要素の前方には位置しないことを保証するために、セグメントｓijが画像Ｉkの他のセグメントを遮蔽する場合には値０、遮蔽しない場合には値１であり、また、Ｃijはｓijの画素の数であり、
【数１４】
2006012166.tif 000039
はヘビサイドのステップ関数であり、ｘ≧０の場合は１、それ以外の場合は０であり、λは２つの表面が同一かどうかを判定するために使用される定数であることを特徴とする請求項２９に記載のシステム。
【請求項３３】
λは、４ディスパリティーレベルに設定されることを特徴とする請求項３２に記載のシステム。
【請求項３４】
あるシーンの３次元再構成を、様々な視点からキャプチャされた、前記シーンの複数の画像から計算するコンピュータ実行可能な命令を含むコンピュータ可読媒体であって、前記コンピュータ実行可能な命令は、
各画像を、その画素が類似のディスパリティーを示すものと思われる各セグメントに分割する命令と、
各画像の各セグメントごとに、一組の候補のディスパリティーの各々に対して、前記セグメントを構成する前記各画素が個々のディスパリティーを示す尤度を表す確率推定値を含むディスパリティー空間分布（ＤＳＤ）を計算する命令と、
各画像の各セグメントごとに、前記セグメントの前記ＤＳＤの最大確率値に対応するディスパリティーを前記セグメントの各画素に割り当てる命令と、
各画像ごとに、前記シーンの同一の部分を描写する隣接画像内の対応する画素のディスパリティー、および前記画像の同一セグメント内の隣接画素のディスパリティーに基づいて、各画素に割り当てられた前記ディスパリティーを平滑化する命令と
を含むことを特徴とするコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の画像を使用した、シーン（場面、情景）の３次元再構成に関し、より詳細には、カラーセグメンテーションに基づく手法を使用して３次元再構成を計算するためのシステムおよびプロセスに関する。
【背景技術】
【０００２】
ステレオ再構成は一般に、様々な視点から取られた複数の画像を使用して画像中に描かれたシーンの３次元モデルを再構成することを含む。一般に、この再構成には、（しばしば各画像ごとに）奥行マップ（ｄｅｐｔｈ  ｍａｐ）を復元して画像間の対応する画素を特定することが必要になる。このような再構成画像は様々な目的に使用される。例えば、立体から得られた奥行マップは、バーチャルリアリティおよびバーチャルスタジオアプリケーションのための現実感のある３次元シーンおよび環境を生成するために、入力画像から抽出されたテクスチャマップ（ｔｅｘｔｕｒｅ  ｍａｐ）と一体化される。同様に、これらのマップは、ビデオ処理アプリケーションにおける動き補償予測にも使用される。さらに、復元された奥行マップおよびその相当物は、他の視点に関連する画像を使用して任意の視点からのシーンの「仮想」ビューを生成するために、ビュー補間の目的でも使用される。
【０００３】
残念なことに、今日のアルゴリズムの品質および解像度はほとんど、これらのアプリケーションで要求される品質および解像度をかなり下回っている。例えば、従来のステレオアルゴリズムは、ディスパリティー（ｄｉｓｐａｒｉｔｙ：両眼視の際、物体の左右の網膜での像の二つの対応点からのずれ）が不連続になるあたりで誤った結果を生ずる傾向がある。残念なことに、ディスパリティーの不連続は一般に輝度エッジと一致するので、このような誤りにより、補間されたシーンにおいて、最も目立つアーチファクト（ａｒｔｉｆａｃｔ：不自然な結果）のいくつかが生成される。この理由で、ビュー補間のためのステレオアルゴリズムでは、ディスパリティー不連続を含む輝度エッジのまわりで画素を正しくマッチさせる必要がある。
【０００４】
最近、セグメンテーションに基づくステレオと呼ばれる、ステレオビジョンに対する新しい方式が提案されている。これらの方法は、ステレオ計算の前に、画像を、類似したディスパリティーまたは平滑なディスパリティーを持つと思われる領域にセグメント化する。次に、各セグメントに対して、平滑性制約（ｓｍｏｏｔｈｎｅｓｓ  ｃｏｎｓｔｒａｉｎｔ）が課される。Ｔａｏ他は、非特許文献２において平面的な制約（ｐｌａｎａｒ  ｃｏｎｓｔｒａｉｎｔ）を使用したが、ＺｈａｎｇおよびＫａｍｂｕｈａｍｅｔｔｕは、非特許文献３においてローカルサポート（ｌｏｃａｌ  ｓｕｐｐｏｒｔ）のためのセグメントを使用した。これらの方法は、ディスパリティー不連続を正確に取り扱う上で、非常に望ましい結果を示すものである。
【０００５】
先行のパラグラフ、および本明細書の残りのパラグラフの記述において、一組のブラケットに囲まれた数値指示子によって特定される様々な個別の出版物を参照していることに留意されたい。このような参照は、例えば「非特許文献１」と記載することにより特定することができる。複数の参照は、例えば［非特許文献２、３］のように、複数の指示子を含む一組のブラケットによって特定される。各特定子に対応する出版物を含む各参照のリストは、「発明を実施するための最良の形態」セクションの最後に記載されている。
【０００６】
【非特許文献１】Scharstein, D., and Szeliski, R. 2002. A taxonomy and evaluation of dense two-frame stereo correspondence algorithms. International Journal of Computer Vision 47, 1 (May), 7-42
【非特許文献２】Tao, H., Sawhney, H., and Kumar, R. 2001. A global matching framework for stereo computation. In Eighth International Con-ference on Computer Vision (ICGV 2001), vol. I, 532-539
【非特許文献３】Zhang,Y., and Kambhamettu, C. 2001. On 3D scene flow and structure estimation. In Conference on Computer Vision and Pattern Recognition (CVPR'2001), vol. II, 778-785
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明は、あるシーンの３次元再構成を、様々な視点からキャプチャ（捕獲、捕捉）された複数のオーバラップする画像から計算するためのシステムおよびプロセスを提供することを目指している。
【課題を解決するための手段】
【０００８】
この３次元再構成システムおよびプロセスは、前述のセグメンテーションに基づく手法を使用するが、従来の成果を改善したものである。すなわち、セグメント内部のディスパリティーは平滑でなければならないが、平面的である必要はなく、また、各画像は同等に扱われ（すなわち、参照用画像はなく）、遮蔽（occlusion）は明示的にモデル化され、ディスパリティーマップの整合性が高められる。
【０００９】
より詳細には、本発明によって３次元再構成を計算するシステムおよびプロセスは、最初に、各画像を、その画素が類似したディスパリティーを示すと思われる各セグメントに分割することを含む。次に、各画像の各セグメントごとに、ディスパリティー空間分布（ＤＳＤ）が計算される。このＤＳＤは、あるセグメントを形成する画素が、一組の候補のディスパリティーの各々に対して個々のディスパリティーを示す尤度（likelihood）を表す一組の確率推定値である。各画像の各セグメントのＤＳＤにおける最大確率に対応するディスパリティーが各セグメントの各画素に割り当てられる。次に、各画像ごとに、各画素に割り当てられたディスパリティーは、そのシーンの同一部分を表す他の画像の対応する画素のディスパリティーに基づいて平滑化され、次いで、各画像の同一セグメント内の隣接する画素のディスパリティーに基づいて平滑化される。平滑操作の結果として得られるのは、再構成を生成するために使用される一群の画像の、各画像ごとのディスパリティーマップである（再構成アプリケーションが画素ごとの奥行マップを要求している場合は、ディスパリティーマップを順に使用して、奥行マップを計算することができる）。
【００１０】
画像の前述のセグメンテーションは、本発明の一実施形態では、最初に、検討中の画像の各画素をそれぞれのセグメントに割り当てることによって実施される。次に、各画素ごとに、順次所定の順番（例えば、ラスター順）で、セグメントの平均色と検討中の画素の色の差が所定の閾値未満である場合には、所定の数の隣接する画素（例えば、４連結隣接画素（４−ｃｏｎｎｅｃｔｅｄ  ｎｅｉｇｈｂｏｒｓ））が、検討中の画素に関連するセグメントに再割り当てされる。次に、画像中の各セグメントごとに、そのセグメントの領域が、所定の画素数（例えば、領域中に１００画素）未満であるかどうかが判定される。あるセグメントの領域が、所定の画素数未満であることが分かった場合には、そのセグメントの画素は、検討中のセグメントの平均色に近い平均色を有する隣接セグメントに再割り当てされる。その後、各セグメントの幅が所定の画素数（例えば、４０画素）より広いかどうかが判定され、広い場合には、そのセグメントを、水平方向に必要な数の均等なセグメントに分割して、新しいより幅の狭いセグメントの幅が所定の画素数を超えないことを保証する。各セグメントの幅が処理された後で、同様にして、現在の各セグメントの高さが所定の画素数（例えば、４０画素）より高いかどうかが判定され、高い場合には、そのセグメントを垂直方向に必要な数の均等なセグメントに分割して、新しい背の低い各セグメントの高さが所定の画素数を超えないことを保証する。
【００１１】
前述の画像のセグメンテーションの前に、各画像の隣接画素間の色差が平滑化されている場合には、改善された結果が得られることに留意されたい。本発明の一実施形態においては、このために、以下の平滑化技術を、各画素ごとにラスター順に使用する必要がある。すなわち、検討中の画素に隣接する、所定の数（例えば、３）の連続する画素の各可能なグループを順に選択し、選択されたグループの各画素ごとに、選択されたグループの各画素の色の光強度を、検討中の画素の色の光強度から減算する。結果として得られた差の２乗値を加算して、選択されたグループの総差を生成する。次いで、最小の総差を示す画素のグループが特定され、特定されたグループの各画素の色と検討中の画素の色が平均化される。次に、結果として得られた平均色が、現在の色として検討中の画素に割り当てられる。前述の色平滑化手順を所定の回数だけ繰り返して、セグメンテーションの結果をさらに改善することができることに留意されたい。
【００１２】
前述のＤＳＤの計算は、本発明の一実施形態では、最初に各画像の各セグメントごとの初期ディスパリティー空間分布（ＤＳＤ）を計算し、次いで、同一画像内の隣接セグメントとの間の平滑性制約と、そのシーンの同一の部分を描写する他の画像の対応するセグメントとの間の一貫性制約を同時に実施してその初期推定値を改良することによって達成される。その結果、改良されたＤＳＤが得られる。
【００１３】
ＤＳＤの計算ができるようになる前に、各々が一意のディスパリティーに対応する一組の奥行を計算する必要がある。まず、中央の視点を表す画像をキャプチャするために使用されるカメラの光学的中心が、ワールド座標系の原点に選ばれる。ｚ軸または奥行軸を、カメラの向きに合わせる。次いで、以下の方法を用いて奥行値を計算する。中央のカメラの画像の中心画素を、ユーザによって指定された最小の奥行で隣接画像に投影（project;
描出ともいう）する。次に、その同一画素の投影が、前の投影から正確に１画素または１ディスパリティーの距離に存在するように、そのセットに新しい奥行値を追加する。新しい奥行は、その奥行値が、ユーザ指定の最大奥行を越えるまで追加される。結果として得られる候補のディスパリティーの範囲におけるディスパリティーの数は、前述の方法で見つけられた奥行値の数に等しくなるように設定される。
【００１４】
奥行が計算された後で、各画像の各セグメントごとの初期ＤＳＤは、以下のように計算することができる。まず、ディスパリティーが選択される。次いで、検討中の画像の隣接画像が選択される。次に、検討中のセグメントの各画素が、選択されたディスパリティーに関する奥行を使用して、選択された隣接画像に投影され、隣接画像中の対応する画素が特定される。対応する画素が見つかった場合には、投影された画素と特定された隣接画像中の画素とに関する１つまたは複数の所定の利得（ｇａｉｎ: 相対輝度）の比が計算される。例えば、これには、濃度レベル光強度利得だけを含めることができ、その場合は、単一の比が使用される。あるいは、各色成分に関する利得を含めることができ、その場合は、複数の利得が使用される。セグメント中のすべての画素が検討された後で、画素利得比ヒストグラムが生成される。このヒストグラムは、その３つの連続するビン（ｂｉｎ）の最大の和を計算するために使用される。この和は、検討中のセグメントと選択された隣接画像との、そのセグメントの投影に関するそのディスパリティーでのマッチングスコアとして指定される。
【００１５】
次に、前述の手順は、残りの各隣接画像に対して繰り返される。次いで、各隣接画像に対する候補のディスパリティーの前述の範囲における残りの各ディスパリティーで繰り返されて、各隣接画像の各候補のディスパリティーについてのマッチングスコアが生成される。この時点で、検討中の候補のディスパリティーですべての隣接画像に関して計算されたマッチングスコアの積が、あらゆる候補のディスパリティーですべての隣接画像に関して計算されたマッチングスコアの積の総和で除算されて、各候補のディスパリティーごとに、そのディスパリティーの初期ＤＳＤ確率が生成される。
【００１６】
初期ＤＳＤ確率についての前述の精緻化は、各画像の各セグメントごとに次式を使用して計算することができる。
【００１７】
【数１】
2006012166.tif 000003
【００１８】
上式で、ｐｉｊ（ｄ）はセグメントｓｉｊのディスパリティーｄに関して精緻化されたディスパリティー確率を表し、ｌｉｊ（ｄ）は平滑性制約を実施する関数、ｃｉｊｋ（ｄ）は隣接画像のグループＮｉ中の各隣接画像との一貫性（consistency）制約を実施する関数、ｄ’は確率値が関連付けられたすべてのディスパリティーを表す。この方法は、各画像にわたる精緻化が所定の回数（例えば、５０〜６０回）繰り返されるという意味で繰り返し手法である。
【００１９】
先に述べたように、ＤＳＤ確率を使用して、各画像の各セグメントの各画素ごとのディスパリティーを確定することができる。これを実施する上で、セグメント内のすべての画素が同一のディスパリティーを有するものと想定する。しかし、より正確な結果は、この要件を緩和し、画素ごとのディスパリティーをセグメント内部で変更できるようにすることによって達成できる。ディスパリティーの変更は、そのシーンの同一の部分を描写する他の画像の対応する画素のディスパリティー、および各画像の同一セグメント内の隣接画素のディスパリティーに基づいて行う。このディスパリティー平滑化プロセスは、本発明の一実施形態においては、検討中の画像に対する各隣接画像ごとに、まず検討中の画素を隣接画像に投影し、投影された画素に対応する隣接画像中の画素を特定し、次いで投影された画素と対応する画素のディスパリティーを平均化することを含む。この平均は、検討中の画素に現在割り当てられているディスパリティーと隣接画像中の対応する画素に割り当てられているディスパリティーの差の絶対値が所定のディスパリティーレベル数（例えば、４レベル）未満の場合はいつでも、関係する隣接画像に関するディスパリティー因数として検討中の画素に割り当てられる。それ以外の場合には、検討中の画素のディスパリティーが、関係する隣接画像に関するディスパリティー因数として割り当てられる。各隣接画像に関して、検討中の画素に割り当てられたディスパリティー因数は加算され、次いで関係する隣接画像の数で除算される。次に、この計算の結果は、検討中の画素に、その現在のディスパリティーとして割り当てられる。
【００２０】
画像間平滑化が完了すると、画像内平滑化手順を実施することができる。この手順では、各画像の各セグメントの各画素ごとに、検討中の画素を中心にした所定のサイズの窓（例えば、５×５の窓）内の、検討中のセグメントの外部にはない各画素に現在割り当てられているディスパリティーを平均化することが必要になる。次に、結果として得られた平均ディスパリティーが、最終ディスパリティーとして検討中の画素に割り当てられる。
【００２１】
次に、前述の平滑化手順を所定の回数繰り返す。例えば、実験（テスト）した実施形態では、平滑化手順は１０から２０回の間で繰り返される。
【００２２】
これまでに説明した利点に加えて、以下の詳細な説明を添付の図面と併せて読むことにより、本発明の他の利点も明らかになるであろう。
【００２３】
本発明の詳細な特徴、態様、および利点は、以下の説明、添付の特許請求の範囲、および添付の図面によって、より良く理解できるようになるであろう。
【発明を実施するための最良の形態】
【００２４】
本発明の好ましい実施形態に関する以下の説明では、添付の図面を参照するが、これらの図面は本明細書の一部をなすものであり、本発明を実施することができる詳細な実施形態を例示として示すものである。他の実施形態も使用できること、および本発明の範囲を逸脱することなく構造的な変更を実施し得ることを理解されたい。
【００２５】
１．０  コンピュータ環境
本発明の好ましい実施形態についての説明を実施する前に、本発明を実装することができる適切なコンピュータ環境について一般的な説明を行う。図１は、適切なコンピュータシステム環境１００の一例を示す。コンピュータシステム環境１００は、適切なコンピュータ環境の一例に過ぎず、本発明の使用または機能の範囲に関して、いかなる制限を加えることを意図したものでもない。コンピュータ環境１００が、典型的な動作環境１００に示されたコンポーネントのいずれか、あるいはそれらの組合せに関して、どのような依存性も要件も有していないことを理解されたい。
【００２６】
本発明は、他の多くの汎用または専用コンピュータシステム環境または構成とともに使用することができる。本発明とともに使用するのに適した、周知のコンピュータシステム、環境、および／または構成の例には、これに限定されるものではないが、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドまたはラップトップ装置、マルチプロセッサシステム、マイクロプロセッサベースのシステム、セットトップボックス、プログラマブル家庭電化製品、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、上記の任意のシステムもしくは装置を含む分散コンピュータ環境などがある。
【００２７】
本発明は、コンピュータによって実行されるコンピュータ実行可能な命令、例えばプログラムモジュールなどの一般的なコンテクストで説明することができる。一般に、プログラムモジュールには、特定のタスクを実行するかまたは特定の抽象データ型を実装する、ルーチン、プログラム、オブジェクト、コンポーネント、データ構造などが含まれる。本発明は、分散コンピュータ環境でも実施することができる。その場合、各タスクは通信ネットワークによってリンクされたリモート処理装置によって実施することができる。分散コンピュータ環境においては、プログラムモジュールは、ローカルおよびリモートの両方のコンピュータ記憶媒体、例えばメモリ記憶装置に配置することができる。
【００２８】
図１を参照すると、本発明を実装するための典型的システムには、コンピュータ１１０のような形の汎用コンピュータ装置が含まれる。コンピュータ１１０の各コンポーネントには、これに限定されるものではないが、処理ユニット１２０、システムメモリ１３０、システムバス１２１などが含まれる。システムバスは、システムメモリなど様々なシステムコンポーネントを処理ユニット１２０に結合する。システムバス１２１は、メモリバスまたはメモリコントローラ、周辺バス、様々なバスアーキテクチャのいずれかを使用するローカルバスなど、いくつかの種類のバスアーキテクチャのいずれであってもよい。例として、このようなアーキテクチャには、これに限定されるものではないが、ＩＳＡ（Ｉｎｄｕｓｔｒｙ  Ｓｔａｎｄａｒｄ  Ａｒｃｈｉｔｅｃｔｕｒｅ）バス、ＭＣＡ（Ｍｉｃｒｏ  Ｃｈａｎｎｅｌ  Ａｒｃｈｉｔｅｃｔｕｒｅ）バス、ＥＩＳＡ（Ｅｎｈａｎｃｅｄ  ＩＳＡ）バス、ＶＥＳＡ（Ｖｉｄｅｏ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｓｔａｎｄａｒｄｓ  Ａｓｓｏｃｉａｔｉｏｎ）バス、メザニン（Ｍｅｚｚａｎｉｎｅ）バスとも呼ばれるＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔ）バスなどが含まれる。
【００２９】
一般に、コンピュータ１１０は、様々なコンピュータ可読媒体を含む。コンピュータ可読媒体は、コンピュータ１１０によってアクセス可能な任意の使用可能媒体であってよく、揮発性および不揮発性媒体、取外し可能および取外し不能媒体の両方を含む。限定の意味ではなく、例として、コンピュータ可読媒体は、コンピュータ記憶媒体および通信媒体を含むことができる。コンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、その他のデータなどの情報を記憶するための任意の方法または技術で実装された、揮発性および不揮発性、取外し可能および取外し不能の媒体を含む。コンピュータ記憶媒体は、これに限定されるものではないが、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリなどのメモリ技術製品、ＣＤ−ＲＯＭ、ＤＶＤ（ｄｉｇｉｔａｌ  ｖｅｒｓａｔｉｌｅ  ｄｉｓｋｓ）などの光ディスク記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置などの磁気記憶装置、その他、所望の情報の格納に使用でき、またコンピュータ１１０がアクセスできる任意の媒体を含む。一般に通信媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、その他のデータなどを、搬送波もしくは他の伝送機構など変調されたデータ信号の形で実施するとともに、いずれかの情報送達媒体を含む。「変調されたデータ信号」という用語は、信号中の情報がコード化されるような方法で設定または変更された、１つまたは複数の信号特性を有する信号を意味する。限定の意味ではなく例として、通信媒体は、有線ネットワーク、直接有線接続などの有線媒体、および、音響、ＲＦ、赤外などの無線媒体を含む。上記の媒体の任意の組合せもまた、コンピュータ可読媒体の範囲に含まれるものとする。
【００３０】
システムメモリ１３０は、ＲＯＭ（読み出し専用メモリ）１３１、ＲＡＭ（ランダムアクセスメモリ）１３２など、揮発性および／または不揮発性メモリの形のコンピュータ記憶媒体を含む。基本入／出力システム（ＢＩＯＳ）１３３は、例えば起動時などに、コンピュータ１１０内の各要素間での情報転送を支援する基本ルーチンを含み、通常はＲＯＭ１３１に格納されている。ＲＡＭ１３２は一般に、処理ユニット１２０によって即時にアクセス可能なかつ／または現在動作中の、データおよび／またはプログラムモジュールを含む。限定の意味ではなく、例として、図１には、オペレーティングシステム１３４、アプリケーションプログラム１３５、他のプログラムモジュール１３６、およびプログラムデータ１３７が示されている。
【００３１】
コンピュータ１１０は、他の取外し可能／取外し不能、揮発性／不揮発性のコンピュータ記憶媒体を含むこともできる。例示の意味で、図１には、取外し不能な不揮発性の磁気媒体に読み書きするハードディスクドライブ１４１、取外し可能な不揮発性磁気ディスク１５２に読み書きする磁気ディスクドライブ１５１、ならびにＣＤ−ＲＯＭ、その他の光媒体など、取外し可能な不揮発性光ディスク１５６に読み書きする光ディスクドライブ１５５が示されている。典型的な動作環境で使用できる、他の取外し可能／取外し不能、揮発性／不揮発性の記憶媒体には、これには限定されるものではないが、磁気テープカセット、フラッシュメモリカード、ＤＶＤ、デジタルビデオテープ、半導体ＲＡＭ、半導体ＲＯＭなどがある。ハードディスクドライブ１４１は一般に、インターフェース１４０などの取外し不能なメモリインターフェースを介してシステムバス１２１に接続され、磁気ディスクドライブ１５１および光ディスクドライブ１５５は一般に、インターフェース１５０など、取外し可能なメモリインターフェースを介してシステムバス１２１に接続される。
【００３２】
図１に示し上で説明した、各ドライブおよびそれに関連するコンピュータ記憶媒体は、コンピュータ１１０のためのコンピュータ可読命令、データ構造、プログラムモジュール、その他のデータなどを記憶する。図１において、例えば、ハードディスクドライブ１４１は、オペレーティングシステム１４４、アプリケーションプログラム１４５、他のプログラムモジュール１４６、およびプログラムデータ１４７を格納するように図示されている。これらの各コンポーネントは、オペレーティングシステム１３４、アプリケーションプログラム１３５、他のプログラムモジュール１３６、およびプログラムデータ１３７と同一であっても、異なっていてもよいことに留意されたい。オペレーティングシステム１４４、アプリケーションプログラム１４５、他のプログラムモジュール１４６、およびプログラムデータ１４７は、少なくともそれらが、異なるコピーであってもよいことを示すために、本明細書では異なる番号が付与されている。ユーザは、入力装置、例えばキーボード１６２、およびポインティング装置１６１などを介して、コンピュータ１１０に命令または情報を入力することができる。また、ポインティング装置は一般に、マウス、トラックボール、タッチパッドを意味する。他の入力装置（図示せず）には、マイクロホン、ジョイスティック、ゲームパッド、衛星放送受信アンテナ、スキャナなどがある。これらおよび他の入力装置は、システムバス１２１に結合されたユーザ入力インターフェース１６０を介して処理ユニット１２０に接続されることが多い。しかし、パラレルポート、ゲームポート、ＵＳＢ（ｕｎｉｖｅｒｓａｌ  ｓｅｒｉａｌ  ｂｕｓ）など、他のインターフェースおよびバス構造を用いて接続することもできる。モニタ１９１、または他の種類の表示装置もまた、ビデオインターフェース１９０などのインターフェースを介してシステムバス１２１に接続される。モニタの他に、コンピュータは、スピーカ１９７、プリンタ１９６など出力周辺インターフェース１９５を介して接続される他の周辺出力装置を含むこともできる。本発明に関して特に重要なのは、一連の画像１９３をキャプチャすることができるカメラ１９２（デジタル／電子スチルカメラまたはビデオカメラ、あるいはフィルム／写真スキャナなど）を、パーソナルコンピュータ１１０への入力装置として含めることができることである。さらに、カメラは１台だけしか描かれていないが、複数台のカメラをパーソナルコンピュータ１１０への入力装置として含めることもできる。１台または複数台のカメラからの画像１９３は、適切なカメラインターフェース１９４を介してコンピュータ１１０に入力することができる。このインターフェース１９４はシステムバス１２１に接続され、それにより各画像を、ＲＡＭ１３２、またはコンピュータ１１０に関連する他のデータ記憶装置の１つに送り、格納することができる。しかし、画像データは、カメラ１９２の使用を必要とせずに、前述のいずれかのコンピュータ可読媒体からも同様に、コンピュータ１１０に入力できることに留意されたい。
【００３３】
コンピュータ１１０は、リモートコンピュータ１８０など１つまたは複数のリモートコンピュータへの論理接続を使用してネットワーク環境で動作させることができる。リモートコンピュータ１８０は、パーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ピア装置、他の共用ネットワークノードなどであってもよい。また、リモートコンピュータ１８０は一般に、図１にはメモリ記憶装置１８１だけが示されているが、コンピュータ１１０に関連して上で説明した要素の多く、またはそのすべてを含むことができる。図１に示された論理接続は、ＬＡＮ（ローカルエリアネットワーク）１７１およびＷＡＮ（ワイドエリアネットワーク）１７３を含むが、他のネットワークを含むこともできる。このようなネットワーク環境は、オフィス、企業規模のコンピュータネットワーク、イントラネット、インターネットなどでは一般的なものである。
【００３４】
ＬＡＮネットワーク環境で使用されるとき、コンピュータ１１０は、ネットワークインターフェースまたはアダプタ１７０を介してＬＡＮ１７１に接続される。ＷＡＮネットワーク環境で使用されるとき、コンピュータ１１０は一般に、インターネットなどのＷＡＮ１７３を介して通信を確立するためのモデム１７２、その他の手段を含む。モデム１７２は、内蔵でも外付けでもよいが、ユーザ入力インターフェース１６０または他の適切な機構を介してシステムバス１２１に接続することができる。ネットワーク環境では、コンピュータ１１０に関連して示された各プログラムモジュール、またはその一部を、リモートのメモリ記憶装置に格納することができる。限定の意味ではなく例示として、図１には、リモートのアプリケーションプログラム１８５が、メモリ装置１８１上に常駐するように示されている。図示されたネットワーク環境が典型的なものであり、コンピュータ間の通信リンクを確立する他の手段を使用することもできることを理解されたい。
【００３５】
２．０  セグメンテーションに基づく３次元再構成システムおよびプロセス
ここまで典型的な動作環境について論じてきた。このセクションの残りの部分は、本発明を実施するプログラムモジュールの説明に充てる。一般に、本発明によるシステムおよびプロセスは、あるシーンの複数の画像からそのシーンの３次元再構成を計算することを含む。各画像は、様々な視点からキャプチャされ、各々そのシーンのある領域を描写し、少なくとも１枚の他の画像と所定の量（例えば、６０〜１００％）だけオーバラップしている。複数の画像は、それらがすべて同時にキャプチャされる場合は、動的なシーンの画像であっても良い。その目的で、異なる視点に置かれた複数のカメラを使用することができる。さらに、複数の画像は、異なる視点に置かれた一連のビデオカメラによって生成された、一群の同時にキャプチャされたフレームの形を取ることもできることに留意されたい。これらの画像は静的なシーンの画像であっても良い。その場合には、前と同様に、異なる視点に置かれた一連のカメラを使用することもできるが、シーンが変化しないので、単一のカメラを視点から視点に移動させて複数の画像をキャプチャすることもできる。
【００３６】
図２の流れ図を参照すると、一般に、本発明の３次元再構成技術は、以下のように達成される。最初に、各画像が独立にセグメント化される（プロセスアクション２００）。次に、あるセグメント内のすべての画素が同一のディスパリティーを有するという想定を使用して、各セグメントごとに初期ディスパリティー空間分布（ＤＳＤ）を計算する（プロセスアクション２０２）。次いで、各セグメントのＤＳＤが、隣接セグメントおよびそのセグメントの他の画像への投影を用いて精緻化される（プロセスアクション２０４）。次に、各セグメントが単一のディスパリティーを持つという想定が、画素ディスパリティー平滑化ステージで緩和されて、各画像ごとのディスパリティーマップが生成される（プロセスアクション２０６）。
【００３７】
次に、前述のプロセスアクションの各々を、以下のセクションで、より詳細に説明する。
【００３８】
２．１  セグメンテーション
セグメンテーションの目標は、各画像を同様のディスパリティーを含むと思われる領域に分割することである。これらの領域またはセグメントは、各セグメントが様々なディスパリティーの領域をカバーする機会を最小にしながらも、ローカルサポートを増大させるために可能な限り大きく取る必要がある。このようなセグメントを生成する際には、一般に同種の色の領域は平滑なディスパリティーを有する、すなわち、一般にディスパリティーの不連続は光強度エッジに一致することが想定される。
【００３９】
本発明のセグメンテーション手順は２つのフェーズを有する。まず、異方性拡散（ａｎｉｓｏｔｒｏｐｉｃ  ｄｉｆｆｕｓｉｏｎ）の変形を使用して、複数の各画像が平滑化される。次に、隣接する色値に基づいて、各画像がセグメント化される。
【００４０】
セグメンテーションの前に平滑化を行う目的は、可能な限り多くの画像ノイズを除去して、より一貫性のあるセグメントを生成することである。光強度エッジに沿った細いセグメントの数を減らすことも望ましい。一般に、本発明の平滑化手順では、３つの連続する隣接画素を用いて、画素が繰り返し平均化される。平均化に使用される画素の組は、色において、どの画素が、中心画素との間で最小の２乗差を有するかによって決定される。周知の異方性拡散およびバイラテラル（bilateral；二者間の）フィルタリングアルゴリズムのこの単純化された変形アルゴリズムは、本アプリケーションに良好な結果をもたらす。
【００４１】
より詳細には、図３の流れ図を参照すると、検討中の画像に対して、各画素がラスター順に選択される（プロセスアクション３００）。画素が選択された後で、（図４の黒い画素で示された）３つの隣接する画素からなる各グループが順に選択される（プロセスアクション３０２）。各グループがどの順番で選択されるか、および選択された画素が隅部または端部の画素であるかどうかには関係なく、実際に存在する隣接画素グループだけが検討される。３画素からなる選択されたグループの各色成分が、選択された画素の対応する値から減算される（プロセスアクション３０４）。次に、結果として得られた差の２乗値を加算して、選択されたグループの総差を生成する（プロセスアクション３０６）。次いで、存在するすべての３画素グループが検討されたかどうかが判定される（プロセスアクション３０８）。すべてのグループが検討されていない場合は、プロセスアクション３０２から３０８が繰り返される。すべての画素グループが検討済みの場合は、プロセスアクション３１０で、差の２乗の総和が最小になるグループが平均化のために指定される。次に、指定されたグループの各画素および選択された画素の色が平均され（プロセスアクション３１２）、その結果が、選択された画素の新しい色として割り当てられる（プロセスアクション３１４）。次いで、画像中のすべての画素が選択されたかどうかが判定される（プロセスアクション３１６）。すべての画素が選択されていない場合は、プロセスアクション３００から３１６が繰り返される。すべての画素が選択済みの場合は、平滑化手順の現在の繰り返しが終了する。
【００４２】
前述の平滑化手順は、所定の回数だけ繰り返される。任意の回数で繰り返すことができるが、本セグメンテーションプロセスについて実験した実施形態では、平滑化手順の８回の繰り返しで良好な結果が得られることが判明している。
【００４３】
前記の平滑化手順について実験した実施形態では、３つの隣接画素からなるグループ（すなわち、３×３の窓）を使用したが、より大きい窓を使用しても、同様に好ましい結果が得られることに留意されたい。例えば、５つの隣接画素からなるグループ（すなわち、５×５の窓）を使用することもできる。
【００４４】
平滑化の後で、セグメント化フェーズが始まる。本発明の一実施形態によれば、このフェーズは、関係する複数の各画像ごとに、図５Ａ〜図５Ｃの流れ図に概説されるような方法で達成される。最初に、検討中の画像の各画素がそれぞれのセグメントに割り当てられる（プロセスアクション５００）。次いで、各画素が、所定の順序で順次選択される（プロセスアクション５０２）。例えば、実験した実施形態では、ラスター順を使用した。そのセグメントの平均色と選択された画素の色が、ある所定の閾値未満で異なっている場合は、隣接する４連結セグメント（画素）が、（すでにそのセグメントに含まれていない場合は、）選択された画素に割り当てられているセグメントに併合（すなわち、再割り当て）される（プロセスアクション５０４）。隅部および端部の画素については、実際に存在する「４連結」画素だけが検討される。次に、未選択の画素が残っているかどうかが判定される（プロセスアクション５０６）。残っている場合は、すべての画素が検討されるまで、プロセスアクションの５０２から５０６が繰り返される。すべての画素が検討された後で、まだ選択されていないセグメントが選択され（プロセスアクション５０８）、プロセスアクション５１０で、選択されたセグメントの領域が所定の画素数（例えば、実験した実施形態では１００）未満かどうかが判定される。選択されたセグメントの領域が、所定の画素数以上であった場合は何のアクションも取らない。一方、所定の数未満であることが判明した場合には、そのセグメントは、最も類似した平均色を有するいずれかの隣接セグメントと併合される（プロセスアクション５１２）。言い換えると、選択されたセグメントの画素は、選択されたセグメントの平均色に最も近い平均色を有する隣接セグメントに再割り当てされる。次に、未選択のセグメントが残っているかどうかが判定される（プロセスアクション５１４）。残っている場合は、すべてのセグメントが選択され処理されるまで、プロセスアクション５０８から５１４が繰り返される。
【００４５】
同種の色の大きな領域には、様々なディスパリティーが存在する尤度があることに留意されたい。この尤度を検討するために、各セグメントは、幅と高さの両方で所定のサイズに制限される。より詳細には、図５Ｂ〜図５Ｃを参照すると、プロセスは再度セグメントの１つを選択するステップに続く（プロセスアクション５１６）。次いで、選択されたセグメントの幅が、所定の画素数を超えているかどうかが判定される（プロセスアクション５１８）。例えば、実験した実施形態では、所定の画素数は４０であった。選択されたセグメントの幅が所定の画素数以下の場合は、何のアクションも取らない。一方、選択されたセグメントの幅が、所定の画素数を超えている場合には、そのセグメントを水平方向に、必要な数の均等なセグメントに分割して、新しいより狭い幅の各セグメントが、幅方向の所定の最大画素数を超えないことを保証する（プロセスアクション５２０）。このことは、選択されたセグメントの各画素を、適切な新しい細いセグメントに再割り当てすることによって達成される。次に、幅に関してすべてのセグメントが検討されたかどうかが判定される（プロセスアクション５２２）。すべてのセグメントが検討されていない場合は、プロセスアクション５１６から５２２が繰り返される。一方、すべてのセグメントが検討済みの場合は、セグメント高さに関する分割手順が繰り返される。より詳細には、まずセグメントが選択される（プロセスアクション５２４）。この選択されるセグメントは、セグメント幅分割手順によって生成された、新しく生成されたセグメントの１つであっても良い。次に、プロセスアクション５２６で、選択されたセグメントの高さが所定の画素数を超えるかどうかが判定される。選択されたセグメントの高さが、所定の画素数以下の場合は、分割は実施されない。一方、選択されたセグメントの高さが、所定の画素数を超えている場合は、そのセグメントを垂直方向に、必要な数の均等なセグメントに分割して、新しいより背の低い各セグメントが、高さ方向の所定の最大画素数を超えないことを保証する（プロセスアクション５２８）。再度、このことは、選択されたセグメントの各画素を、適切な新しいより背の低いセグメントに再割り当てすることによって達成される。次に、高さに関してすべてのセグメントが検討されたかどうかが判定される（プロセスアクション５３０）。すべてのセグメントが検討されていない場合は、プロセスアクション５２４から５３０が繰り返される。すべてのセグメントが検討済みの場合は、プロセスは終了する。
【００４６】
本発明の実験した実施形態では、前述の併合および分割操作の結果、最終的なセグメントはすべて、サイズが１００から１６００画素の範囲となった。前述のセグメンテーション手順の一例は、図６（ａ）および図６（ｂ）に示されている。ただし、図６（ａ）は元の画像であり、図６（ｂ）はセグメンテーションしたものである。
【００４７】
２．２  初期ディスパリティー空間分布
セグメンテーションの後の、次のステップは、画像中の各セグメントの初期ディスパリティー空間分布（ＤＳＤ）を計算することである。ＤＳＤとは、画像Ｉｉのセグメントｓｉｊについての複数のディスパリティーについての一組の確率値のことである。ＤＳＤは、各ディスパリティーにおけるコストまたは尤度とすべての画素とを関連付ける従来のディスパリティー空間画像（ＤＳＩ）を変形したものである（非特許文献１）。セグメントｓｉｊがディスパリティーｄを有する確率をｐｉｊ（ｄ）で表す。ただし、Σｄｐｉｊ（ｄ）＝１である。
【００４８】
各セグメントｓｉｊの初期ＤＳＤは次式で設定される。
【００４９】
【数２】
2006012166.tif 000004
【００５０】
上式で、ｍｉｊｋ（ｄ）は、画像ｋのｓｉｊについてのディスパリティーｄでのマッチング関数であり、Ｎｉは画像ｉの隣接画像である。この説明では、Ｎｉは画像ｉの直接隣接画像、すなわち、ｉに直接隣接するカメラによってキャプチャされた画像からなるものと想定する。一列に並んだカメラの端部のカメラの場合には、片方の隣接画像だけが使用可能になる。さらに、ｄ’の全範囲にわたるすべてのマッチングスコア（得点）の和によって除算することにより、ＤＳＤの総和が１になることが保証される。ｄ’の全範囲にわたるマッチングスコアは、隣接画像中のセグメントの投影に対するマッチング関数を、そのディスパリティーに関連した奥行で計算し、次いでそのマッチング関数を再計算することによって得られる。
【００５１】
カメラ間の利得差を考えると、画素利得のヒストグラムを使用するマッチングスコアが良い結果を生むことが分かった。ただし、その代わりに、他の画素特性や、他の従来からのヒストグラムに基づかないマッチング方法を使用することもできる。セグメントｓｉｊの各画素ｘに対する、隣接画像ｋにおける投影ｘ’は、任意の適切な投影方法を用いて求めることができる。次いで、画素利得比ヒストグラムが、利得（比）、Ｉｉ（ｘ）／Ｉｋ（ｘ’）を用いて生成される。カラー画素については、各成分の利得が個別に計算され同一のヒストグラムに加算される。ヒストグラムのビンは、データのより良い間隔を保証するために対数スケールを用いて計算される。セグメント化手順について実験した実施形態では、０．８から１．２５の範囲の、ビン数２０のヒストグラムを使用して良好な結果が得られた。
【００５２】
一般に、前述のヒストグラム法を用いると、図７に示したように、マッチが良い場合には、ヒストグラムは、少数のビンが大きな値を示し、残りのビンが小さな値を示す。一方、マッチが悪い場合には、より平坦な分布となる。前述の、分布の「鋭さ（ｓｈａｒｐｎｅｓｓ）」を評価するためには、分散やエントロピーを評価するなど、いくつかの方法を使用することができる。しかし、本発明の実験した実施形態においては、次のマッチング関数が効率も良く、良好な結果が得られることが判明した。
【００５３】
【数３】
2006012166.tif 000005
【００５４】
上式で、ｈｌは、ヒストグラムのｌ（エル）番目のビンである。すなわち、マッチングスコアは、ヒストグラム中の、連続する３つのビンの和の最大値である。
【００５５】
検討中のセグメントの、隣接画像に関する初期ディスパリティーのマッチングスコアを決定した後で、ディスパリティーの全体の集合が再計算される。例えば、実験した実施形態では、マッチングスコアは、各ディスパリティーに関する奥行を使用して、セグメントを隣接画像に投影することによって再計算される。各ディスパリティーに関する奥行は、隣接画像の１つに関して、中央のカメラの中心画素の投影での１画素のシフトに相当する奥行の変化を見つけることによって計算される。したがって、前述の利得比の計算には、各ディスパリティーごとに１組の異なる隣接画像が関与することになり、その結果、ヒストグラムは異なるプロファイルとなり、異なるマッチングスコアが得られる尤度が高くなる。マッチングスコアが大きくなるほど、検討中のセグメントが、シフトに関して隣接画像のその領域とより密接にマッチする尤度が高いことを示し、また、そのインクリメントされたディスパリティーが他の候補値より正確である尤度が高いことを示す。
【００５６】
次に、処理される一群の画像の各画像における各セグメントに関して実施される、前述の初期ＤＳＤ手順について、図８Ａ〜図８Ｂに示した流れ図を参照しながら概説する。最初に、それぞれ１つのディスパリティーに対応する一組の奥行値が計算される（プロセスアクション８００）。ＤＳＤ手順の一実施形態では、一組の候補のディスパリティー、および各候補のディスパリティーに対する奥行値は以下のように確定される。最初に、ユーザ指定の最小および最大奥行値が入力される。次に、前述の複数の画像のうちの視点に関して中央の画像の中心画素が、ユーザによって指定された最小奥行を使用して、その隣接画像の１つに投影される。投影された中心画素に対応する隣接画像の画素に関連するディスパリティーに、最小奥行値が割り当てられる。次に、中心画素が、直前の投影から１ディスパリティーの所に位置するように再度投影され、現在の中心画素投影に関連する奥行が確定される。次に、最後に確定された奥行値がユーザ指定の最大奥行を超えたかどうかが判定される。超えていない場合は、最後に確定された奥行値が、直前に割り当てられていたディスパリティーを１ディスパリティーレベル分インクリメントした値のディスパリティーに対して割り当てられる。この中心画素の投影は、確定された奥行値が最大値を超えたかどうかを判定し、新しいディスパリティーおよび関連する奥行値を確定しながら、最後に確定された奥行値がユーザ指定の最大奥行値を超えたと判定されるまで続く。超えた時点で、奥行値が割り当てられてきた一連のディスパリティーが候補のディスパリティーとして指定される。次に、あるディスパリティーが、一組の候補のディスパリティーから選択される（プロセスアクション８０２）。検討中のセグメントを含む画像の隣接画像が選択される（プロセスアクション８０４）。これに続いて、検討中のセグメント内の未だ選択されていない画素が選択され（プロセスアクション８０６）、プロセスアクション８０８で、選択されたディスパリティーに関連する奥行値を使用して、その画素が、選択された隣接画像に投影され、投影された画素に対応する隣接画像中の画素が特定される。各画像は少なくとも１つの隣接画像とオーバラップするので、検討中の画像の画素の少なくともいくつかは隣接画像中の画素に対応することになる。選択された画素が、選択された隣接画像内に対応する画素を有する場合は、投影された画素と現在特定されている隣接画像中の画素とに関連する１つまたは複数の利得比が計算される（プロセスアクション８１０）。この計算に関して、複数の比が存在し得る状況は、一例として、画像がカラー画像の場合である。この場合には、適切な各色成分の利得比を計算することができる。次いで、検討中のセグメントに未選択の画素が残っているかどうかが判定される（プロセスアクション８１２）。残っている場合は、すべての画素が検討されるまで、プロセスアクション８０６から８１２が繰り返される。未選択の画素が残っていない場合は、プロセスアクション８１４で、（先に述べた）画素利得比ヒストグラムが生成される。次に、ヒストグラム中の最大の３つの連続するビンの和が計算され（プロセスアクション８１６）、この和が、選択された隣接画像に関する選択されたディスパリティーにおける、このセグメントのマッチングスコアとして指定される（プロセスアクション８１８）。
【００５７】
プロセス中のこの時点で、検討中のセグメントの各画素と選択された隣接画像中の各画素との間のマッチングスコアが、選択されたディスパリティーに関して計算されたことになる。他の隣接画像がある場合は、その画像に対して前述の手順が繰り返される。したがって、図８Ｂを参照すると、プロセスアクション８２０で、すべての隣接画像が選択されたかどうかが判定される。選択されていない場合は、プロセスアクション８０４から８２０が繰り返される。すべての隣接画像が検討済みである場合は、プロセスアクション８２２で、未選択のディスパリティー値が残っているかどうかが調査される。残っている場合は、新しいディスパリティーが選択され、プロセスアクション８０２から８２２が繰り返される。ディスパリティー値の組のすべてが選択された後で、そのセグメントの初期ＤＳＤが計算される。この計算には、マッチングスコア計算に関連して、まだ選択されていないディスパリティー値のうちの１つを選択することが必要になる（プロセスアクション８２４）。次に、選択されたディスパリティー値で、すべての隣接画像に関して計算されたマッチングスコアの積が、あらゆるディスパリティー値で、すべての隣接画像に関して計算されたマッチングスコアの積の総和で除算され、選択されたディスパリティー値のＤＳＤ確率が生成される（プロセスアクション８２６）。これに続いて、まだ選択されていないディスパリティー値が残っているかどうかが判定される（プロセスアクション８２８）。残っている場合は、プロセスアクション８２４から８２８が、すべてのディスパリティ値ーが検討されるまで繰り返される。各ディスパリティー値についてのＤＳＤ確率が計算されると、検討中のセグメントに対するプロセスは終了する。
【００５８】
２．３  ＤＳＤ精緻化
次のステップは、処理中の一群の画像の各画像における各セグメントのディスパリティー空間分布を繰り返し精緻化することである。これまでのセクションと同様に、各セグメントは単一のディスパリティーを有するものと想定する。
【００５９】
ＤＳＤを精緻化するとき、セグメント間の平滑性制約および画像間の一貫性制約を実施することが望ましい。平滑性制約は、類似の色を有する隣接セグメントは類似のディスパリティーを持つべきであることを指定する。第２の制約は、画像間のディスパリティーの一貫性を実現する。すなわち、ディスパリティーｄを有するセグメントが隣接画像に投影された場合は、それを投影しているセグメントはｄに近いディスパリティーを有する必要がある。
【００６０】
これら２つの制約は、次式を使用して繰り返し実施される。
【００６１】
【数４】
2006012166.tif 000006
【００６２】
上式で、ｌｉｊ（ｄ）は平滑性制約を実施し、ｃｉｊｋ（ｄ）は各隣接画像Ｎｉに関する一貫性制約を実施する。実験した実施形態では、各画像にわたり５０〜６０回繰り返すことによってディスパリティー確率の望ましい精緻化ができることが分かった。平滑性制約および一貫性制約の詳細を以下に示す。
【００６３】
２．３．１  平滑性制約
初期セグメントを生成するときには、類似した色を有する隣接画素は類似したディスパリティーを有するべきであるとの経験則を使用する。同じ経験則を使用して、セグメント間のＤＳＤを精緻化する。Ｓｉｊでセグメントｓｉｊの隣接セグメントを表し、
【００６４】
【数５】
2006012166.tif 000007
【００６５】
で、セグメントｓｉｊ∈Ｓｉｊの最大ディスパリティー推定値を表す。セグメントｓｉｊのディスパリティーは、平均値
【００６６】
【数６】
2006012166.tif 000008
【００６７】
の混合正規分布、
【００６８】
【数７】
2006012166.tif 000009
【００６９】
によってモデル化され、
【００７０】
【数８】
2006012166.tif 000010
【００７１】
の近くに存在するものと想定する。ただし、本発明の実験した実施形態では、
【００７２】
【数９】
2006012166.tif 000011
【００７３】
の正規分布であり、オフセットはε＝０．０１である。各隣接セグメントｓｉｊの分散
【００７４】
【数１０】
2006012166.tif 000012
【００７５】
は、３つの値、すなわち、セグメントの色の類似性、セグメント間の境界の長さ、および
【００７６】
【数１１】
2006012166.tif 000013
【００７７】
を使用して推定される。セグメントｓｉｊとｓｉｌ内の画素の平均色の差をΔｊｌとし、ｓｉｊの境界のうちｓｉｌが占める割合をｂｉｌとする。さらに、
【００７８】
【数１２】
2006012166.tif 000014
【００７９】
は次式に設定される。
【００８０】
【数１３】
2006012166.tif 000015
【００８１】
ただし、本発明の実験した実施形態では、幅スカラν＝８であり、色差の２乗分散はガウス分散
【００８２】
【数１４】
2006012166.tif 000016
【００８３】
である。
【００８４】
２．３．２  一貫性制約
一貫性制約は、異なる画像間のディスパリティーマップが一致すること、すなわち、ディスパリティーｄを有する画素が、ある画像から別の画像に投影された場合、その投影もまたディスパリティーｄを有するはずであることを保証する。ｃｉｊｋ（ｄ）の値を計算して一貫性制約を実施するとき、いくつかの制約が適用される。第１に、あるセグメントのＤＳＤは、他の画像中のそのセグメントを投影するセグメントのＤＳＤと類似している必要があること。第２に、セグメントのＤＳＤは画像間で一致していることが望ましいが、それらがマッチング関数ｍｉｊｋ（ｄ）でも一致している必要があること。第３に、セグメントによっては、遮蔽のために他の画像中に対応するセグメントが存在しない場合があることである。
【００８５】
各ディスパリティーｄおよびセグメントｓｉｊごとに、その投影されたＤＳＤ、すなわちＩｋに関するｐｉｊｋ（ｄ）が計算される。画素ｘの投影先の画像Ｉｋにおけるセグメントをπ（ｋ，ｘ）、ｓｉｊの画素の数をＣｉｊとすると、
【００８６】
【数１５】
2006012166.tif 000017
【００８７】
となる。セグメントｓｉｊが画像ｋ内で遮蔽される尤度も推定する必要がある。マッチの形跡がほとんどない場合は、投影されたＤＳＤ
【００８８】
【数１６】
2006012166.tif 000018
【００８９】
は低くなるので、可視尤度は次式で評価することができる。
【００９０】
【数１７】
2006012166.tif 000019
【００９１】
投影されたＤＳＤとともに、遮蔽関数ｏｉｊｋ（ｄ）が計算される。この関数は、画像Ｉｋにおいてセグメントｓｉｊが他のセグメントを遮蔽するときに値０となり、遮蔽しないときは１となる。この関数は、ｓｉｊが画像Ｉｋにおいて目に見えない場合でも、ｋ番目の画像の奥行推定値において、表面要素の前方にその推定された奥行が位置しないことを保証する。より詳細には、ｏｉｊｋ（ｄ）は次式で定義される。
【００９２】
【数１８】
2006012166.tif 000020
【００９３】
上式で、ｈ（ｘ）は、ｘ≧０で１、それ以外で０となるヘビサイド（Heaviside）のステップ関数であり、λは２つの表面が同一かどうかを判定するために使用される定数である。実験した実施形態では、λを４ディスパリティーレベルに設定した。最後に、遮蔽された場合と遮蔽されていない場合を一体化する。セグメントが遮蔽されていない場合は、ｃｉｊｋ（ｄ）は、投影されたＤＳＤおよびマッチング関数から直接計算することができる。
【００９４】
【数１９】
2006012166.tif 000021
【００９５】
遮蔽された領域については、遮蔽関数ｏｉｊｋ（ｄ）だけが使用される。したがって、ｃｉｊｋ（ｄ）の最終的な関数は、次式となる。
【００９６】
【数２０】
2006012166.tif 000022
【００９７】
本発明の一実施形態では、前述のＤＳＤ精緻化プロセスは、図９の流れ図に概説されるように実施される。最初に、処理される一群の画像の中から１枚の画像が選択され（プロセスアクション９００）、選択された画像の中の１つのセグメントが選択される（プロセスアクション９０２）。次に、選択されたセグメントの精緻化されたディスパリティー確率が、前述のような方法で計算される（プロセスアクション９０４）。次いで、選択された画像のすべてのセグメントが検討されたかどうかが判定される（プロセスアクション９０６）。すべてが検討されていない場合は、プロセスアクション９０２から９０６が、残された各セグメントに対して実施される。選択された画像のすべてのセグメントが検討された後で、すべての画像が処理されたかどうかが判定される（プロセスアクション９０８）。すべてが処理されていない場合は、プロセスアクション９００から９０８が，残りのすべての画像に対して繰り返される。すべての画像が検討された後で、所定の回数の精緻化繰り返しが完了したかどうかが判定される（プロセスアクション９１０）。完了していない場合は、９００から９１０の全体のプロセスアクションが、所定の繰り返し回数実施されるまで繰り返される。
【００９８】
所定のすべての繰り返しが完了した後で、各画像の各セグメントｓｉｊにおける各画素ｘに対し、その画素を含むセグメントのＤＳＤの最大確率値に対応するディスパリティー
【００９９】
【数２１】
2006012166.tif 000023
【０１００】
が、その画素のディスパリティーｄ（ｘ）として割り当てられる（プロセスアクション９１２）。数式の形で表すと、次式となる。  
∀ｘ∈ｓｉｊ，ｄ（ｘ）＝ａｒｇ  ｍａｘｄ’Ｐｉｊ（ｄ’）              （１０）
【０１０１】
２．４  ディスパリティー平滑化
この時点までは、各セグメントのディスパリティーは定数であった。この段階で、この制約が緩和され、各ディスパリティーを、隣接するセグメントおよび画像のディスパリティーに基づいて滑らかに変化させることが許されることになる。
【０１０２】
先に示したように、精緻化段階の最後で、各画像の各セグメントにおける各画素は、関連するＤＳＤの最大確率値を有するディスパリティーに設定される。ディスパリティーが画像間で一貫していることを保証するために、以下を実施する。ディスパリティーｄｉ（ｘ）を有する画像Ｉｉの各画素ｘごとに、各画素ｘは各隣接画像Ｉｋに投影されて、ｘの投影に対応するＩｋ中の画素ｙが見つけられる。次いで、ｄｉ（ｘ）は次式のように更新される。
【０１０３】
【数２２】
2006012166.tif 000024
【０１０４】
上式で、
【０１０５】
【数２３】
2006012166.tif 000025
【０１０６】
は２値関数であり、｜ｄｉ（ｘ）−ｄｋ（ｙ）｜＜λのときに１になり、｜ｄｉ（ｘ）−ｄｋ（ｙ）｜≧λのときに０になる。この関数は、ディスパリティーの類似性を実験する指示変数として動作する。また、＃Ｎｉは隣接画像の数である。実験した実施形態では、λを４ディスパリティーレベルに設定した。
【０１０７】
各画像にわたってディスパリティーを平均化した後で、各画像の各画素についての、その画素を含むセグメントの内部に制限された所定の窓内部のディスパリティーは、滑らかさを維持するために平均化される。実験した実施形態では、５×５の窓を使用して良好な結果が得られたが、要望に応じて他のサイズを使用することもできる。所定の窓が拡大されてセグメントの境界を越えた場合には、セグメント内部の画素だけが平均化されて、検討中の画素の最終ディスパリティーが確定されることに留意されたい。画像間の前述のディスパリティー平滑化は繰り返しによって達成される。実験した実施形態では、各画像を通して、式（１１）を用いて約１０〜２０回の繰り返しを行い、各セグメントの内部で平均化して各画像内のディスパリティーを順に平滑化することによって所望の効果が得られることが判明している。
【０１０８】
本発明の一実施形態では、前述の平滑化手順は、図１０Ａ〜図１０Ｃに示された流れ図で概説されるように実施される。最初に、処理される一群の画像の中の１枚の画像が選択され（プロセスアクション１０００）、次いでその画像中の１つの画素が選択される（プロセスアクション１００２）。さらに、選択された画像の隣接画像の１枚が選択される（プロセスアクション１００４）。続いて、選択された画素を選択された隣接画像に投影し、投影された画素に相当する隣接する画像中の画素を特定する（プロセスアクション１００６）。次に、選択された画素に現在割り当てられているディスパリティー値と、隣接画像の特定された対応する画素に割り当てられているディスパリティー値との差分の絶対値が、所定のディスパリティーレベル数の未満かどうかが判定される（プロセスアクション１００８）。未満の場合は、検討中の２つの画素のディスパリティー値の平均が計算され、選択された隣接画像に関連するディスパリティー因数として、選択された画素に割り当てられる（プロセスアクション１０１０）。一方、差の絶対値が所定のディスパリティーレベル数以上の場合は、選択された画素に現在割り当てられているディスパリティー値が、選択された隣接画像に関連するディスパリティー因数として選択された画素に割り当てられる（プロセスアクション１０１２）。次に、選択された画像のすべての隣接画像が検討されたかどうかが判定される（プロセスアクション１０１４）。まだ検討されていない場合は、プロセスアクション１００４から１０１４が、残りの各隣接画像に対して繰り返される。すべての隣接画像が検討された後で、プロセスアクション１０１６で、各隣接画像に関連することとして、選択された画素に割り当てられたディスパリティー因数の和を計算し、その和を隣接画像の数によって除算する。次に、その結果を、現在のディスパリティー値として、選択された画素に割り当てる（プロセスアクション１０１８）。次いで、選択された画像のすべての画素が処理されたかどうかが判定される（プロセスアクション１０２０）。処理されていない場合は、プロセスアクション１００２から１０２０が、残りの各画素に対して繰り返される。選択された画像のすべての画素が処理された場合は、次いで、すべての画像が検討されたかどうかが判定される（プロセスアクション１０２２）。すべてが検討されていない場合は、残りの各画像に対してプロセスアクション１０００から１０２２が繰り返される。画像間平滑化が完了した後で、先に説明したように、プロセスは画像内平滑化に続く。より詳細には、次いで図１０Ｃを参照すると、再度画像の１枚が選択される（プロセスアクション１０２６）。次に、選択された画像内のセグメントが選択され（プロセスアクション１０２８）、選択されたセグメントの画素が選択される（プロセスアクション１０３０）。次に、選択された画素を中心にした所定のサイズの窓内の画素で、選択されたセグメントの外側にはみ出していない画素のディスパリティー値が平均され、その結果（平均値）が、選択された画素の最終ディスパリティー値としてその選択された画素に割り当てられる（プロセスアクション１０３２）。次に、選択されたセグメント内のすべての画素が検討されたかどうかが判定される（プロセスアクション１０３４）。すべてが検討されていない場合は、プロセスアクション１０３０から１０３４が、残りの各画素に対して繰り返される。選択されたセグメント内のすべての画素が処理されたとき、選択された画像内のすべてのセグメントが検討されたかどうかが判定される（プロセスアクション１０３６）。まだすべてが検討されていない場合は、プロセスアクション１０２８から１０３６が、残りの各セグメントに対して繰り返される。選択された画像中のすべてのセグメントが処理されると、残りの画像に関して画像内平滑化が実施される。この目的で、画像内平滑化のためにすべての画像が検討されたかどうかが判定される（プロセスアクション１０３８）。すべてが検討されていない場合は、プロセスアクション１０２６から１０３８が、残りの各画像に対して実施される。すべての画像が検討されると、プロセスアクション１０４０で、所定の回数の平滑化繰り返しが完了したかどうかが判定される。完了していない場合は、アクション１０００から１０４０の全体のプロセスが、所定の回数の繰り返しが実施されるまで繰り返される。この時点で平滑化プロセスは終了する。
【０１０９】
２．５  典型的な結果
図１１（ａ）〜図１１（ｅ）は、本発明の３次元再構成処理の実験した実施形態を使用して得られたいくつかの結果のサンプルを示す。図１１（ａ）は、あるグループの人たちがブレークダンサーを見ている画像である。隣接画像が存在するが図には示されていない。図１１（ｂ）は、再構成のセグメンテーションフェーズの結果を示すもので、各斑点は、個々のセグメントを表す。図１１（ｃ）は、セグメントの初期ＤＳＤの最大確率値に関連するディスパリティーを、そのセグメントの各画素に割り当てることによって得られたディスパリティー推定値から導かれた、画素ごとの奥行を例示したものである。図１１（ｃ）〜図１１（ｅ）において、画像中の画素が明るいほど、その画素は、元の画像をキャプチャしたカメラに接近しているものと推定されることに留意されたい。図１１（ｄ）は、図１１（ｃ）と同様に得られたものであるが、本発明の再構成プロセスによりＤＳＤ確率値が精緻化された後で得られた画素ごとの奥行を表すものである。最後に、図１１（ｅ）は、前述の平滑化手順を実施した後で得られた、画素ごとの奥行を表すものである。連続する各段階で、ディスパリティー推定値が改善されていく様子を確認することができる。
【図面の簡単な説明】
【０１１０】
【図１】本発明を実装するための典型的なシステムを構成する汎用のコンピュータ装置を示す図である。
【図２】あるシーンの複数の画像、およびカラーセグメンテーションに基づく手法を用いて、そのシーンの３次元再構成を計算するための全体プロセスを示す流れ図である。
【図３】図２の３次元再構成プロセスのセグメンテーション部分の初期フェーズを表す、画像の画素色を平滑化するプロセスを示す流れ図である。
【図４】図３の画素色平滑化プロセスで使用される隣接３画素のグループを示す図である。
【図５Ａ】図２の３次元再構成プロセスの、画像をセグメント化する部分を実施するプロセスを示す流れ図である。
【図５Ｂ】図２の３次元再構成プロセスの、画像をセグメント化する部分を実施するプロセスを示す流れ図である。
【図５Ｃ】図２の３次元再構成プロセスの、画像をセグメント化する部分を実施するプロセスを示す流れ図である。
【図６ａ】図５Ａ〜図５Ｃのセグメンテーションプロセスの結果を示す典型的な画像の、元の画像を示す図である。
【図６ｂ】図５Ａ〜図５Ｃのセグメンテーションプロセスの結果を示す典型的な画像の、セグメンテーション結果を示す図である。
【図７】ディスパリティー空間分布（ＤＳＤ）に関し、良いマッチと悪いマッチを表す利得比ヒストグラムの例を示す図である。
【図８Ａ】図２の３次元再構成プロセスの、各画像の各セグメントごとに初期ＤＳＤ推定値を計算する部分を実施するプロセスを示す流れ図である。
【図８Ｂ】図２の３次元再構成プロセスの、各画像の各セグメントごとに初期ＤＳＤ推定値を計算する部分を実施するプロセスを示す流れ図である。
【図９】図２の３次元再構成プロセスの、初期ＤＳＤ推定値を精緻化する部分を実施するプロセスを示す流れ図である。
【図１０Ａ】図２の３次元再構成プロセスの、各画像の画素のディスパリティー推定値を平滑化する部分を実施するプロセスを示す流れ図である。
【図１０Ｂ】図２の３次元再構成プロセスの、各画像の画素のディスパリティー推定値を平滑化する部分を実施するプロセスを示す流れ図である。
【図１０Ｃ】図２の３次元再構成プロセスの、各画像の画素のディスパリティー推定値を平滑化する部分を実施するプロセスを示す流れ図である。
【図１１ａ】図２の３次元再構成プロセスの一実施形態を使用して得られる結果のサンプルの、ブレークダンサーを見ているあるグループ人々を示す図である。
【図１１ｂ】図２の３次元再構成プロセスの一実施形態を使用して得られる結果のサンプルの、再構成のセグメンテーションフェーズの結果を示す図である。
【図１１ｃ】図２の３次元再構成プロセスの一実施形態を使用して得られる結果のサンプルの、あるセグメントの初期ＤＳＤの最大確率値に関するディスパリティーをそのセグメントの各画素に割り当てることによって得られたディスパリティー推定値から導かれた、画素ごとの奥行を例示する図である。
【図１１ｄ】図２の３次元再構成プロセスの一実施形態を使用して得られる結果のサンプルの、ＤＳＤ確率値が精緻化された後で図１１（ｃ）と同様にして得られた、画素ごとの奥行を示す図である。
【図１１ｅ】図２の３次元再構成プロセスの一実施形態を使用して得られる結果のサンプルの、ディスパリティー推定値平滑化手順を実施した後で得られた、画素ごとの奥行を示す図である。
【符号の説明】
【０１１１】
１２０  処理ユニット
１２１  システムバス
１３０  システムメモリ
１３４  オペレーティングシステム
１３５  アプリケーションプログラム
１３６  他のプログラムモジュール
１３７  プログラムデータ
１４０  取外し不能不揮発メモリインターフェース
１４４  オペレーティングシステム
１４５  アプリケーションプログラム
１４６  他のプログラムモジュール
１４７  プログラムデータ
１５０  取外し可能不揮発メモリインターフェース
１６０  ユーザ入力インターフェース
１６１  マウス
１６２  キーボード
１７０  ネットワークインターフェース
１７１  ローカルエリアネットワーク
１７２  モデム
１７３  ワイドエリアネットワーク
１８０  リモートコンピュータ
１８５  リモートアプリケーションプログラム
１９０  ビデオインターフェース
１９１  モニタ
１９２  カメラ
１９４  カメラインターフェース
１９５  出力周辺インターフェース
１９６  プリンタ
１９７  スピーカ
【図１】
2006012166.tif 000040
【図２】
2006012166.tif 000041
【図３】
2006012166.tif 000042
【図４】
2006012166.tif 000043
【図５Ａ】
2006012166.tif 000044
【図５Ｂ】
2006012166.tif 000045
【図５Ｃ】
2006012166.tif 000046
【図６ａ】
2006012166.tif 000047
【図６ｂ】
2006012166.tif 000048
【図７】
2006012166.tif 000049
【図８Ａ】
2006012166.tif 000050
【図８Ｂ】
2006012166.tif 000051
【図９】
2006012166.tif 000052
【図１０Ａ】
2006012166.tif 000053
【図１０Ｂ】
2006012166.tif 000054
【図１０Ｃ】
2006012166.tif 000055
【図１１ａ】
2006012166.tif 000056
【図１１ｂ】
2006012166.tif 000057
【図１１ｃ】
2006012166.tif 000058
【図１１ｄ】
2006012166.tif 000059
【図１１ｅ】
2006012166.tif 000060
【外国語明細書】
2006012166000001.pdf