【手続補正書】
【提出日】平成20年6月23日(2008.6.23)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
あるシーンの３次元再構成を、様々な視点からキャプチャされた前記シーンの複数の画像から計算するためのコンピュータに実装された方法であって、コンピュータを使用して実施する、
各画像を、その領域の各画素が類似のディスパリティーを示すものと思われる、前記画像の各領域を表すセグメントに分割するプロセスアクションと、
セグメント内のすべての画素が同一のディスパリティーを有するとの想定を用いて、各画像の各セグメントごとに初期ディスパリティー空間分布（ＤＳＤ）を計算するプロセスアクションであって、あるセグメントの前記初期ＤＳＤが、一組の候補のディスパリティーの各々に対して前記セグメント内の各画素が個々のディスパリティーを示す確率の初期推定値を含むプロセスアクションと、
各画像の各セグメントごとに、前記初期ＤＳＤの前記ディスパリティー確率の前記初期推定値を、同一の画像内の隣接セグメントとの間の平滑性制約、および前記シーンの同一部分を描写する他の画像内の対応するセグメントとの間の一貫性制約を同時に実施して精緻化することによって、精緻化されたＤＳＤを生成するプロセスアクションと、
各画像の各セグメントごとに、前記セグメントの前記精緻化されたＤＳＤの最大確率値に対応するディスパリティーを、前記セグメントの各画素に割り当てるプロセスアクションと、
各画像ごとに、各画素に割り当てられた前記ディスパリティーを、前記シーンの同一部分を描写する他の画像内の対応する画素のディスパリティーに基づいて平滑化し、次いで、前記画像の同一セグメント内の隣接画素のディスパリティーに基づいて平滑化するプロセスアクションと
を含むことを特徴とする方法。
【請求項２】
各画像をセグメントに分割する前記プロセスアクションは、
検討中の画像の各画素を、それぞれのセグメントに割り当てるアクションと、
各画素ごとに順に所定の順序で、前記セグメントの画素の平均色が検討中の画素の色と所定の閾値未満で異なっているときはいつでも、検討中の画素に隣接する所定の数の画素を前記画素に割り当てられた前記セグメントに再割り当てするアクションと、
各セグメントごとに順に、前記セグメントが領域に関する所定の画素数未満かどうかを判定し、前記セグメントが領域に関する前記所定の画素数未満であるときはいつでも、前記セグメントの画素を、検討中のセグメントの平均色に最も近い平均色を有する隣接セグメントに再割り当てするアクションと、
各セグメントごとに順に、前記セグメントが幅方向の所定の画素数を超えているかどうかを判定し、前記セグメントが幅方向の所定の画素数を超えているときはいつでも、前記セグメントを水平方向に必要な数の均等なセグメントに分割して、前記選択されたセグメントの各画素を適切な新しいより幅の狭いセグメントに再割り当てすることによって、前記新しいより幅の狭い各セグメントが幅方向の前記所定の画素数を超えないことを保証するアクションと、
各セグメントごとに順に、前記セグメントが高さ方向の所定の画素数を超えているかどうかを判定し、前記セグメントが高さ方向の所定の画素数を超えているときはいつでも、前記セグメントを垂直方向に必要な数の均等なセグメントに分割して、前記選択されたセグメントの各画素を適切な新しいより背の低いセグメントに再割り当てすることによって、前記新しいより背の低い各セグメントが高さ方向の前記所定の画素数を超えないことを保証するアクションと
を含むことを特徴とする請求項１に記載の方法。
【請求項３】
各画像をセグメントに分割する前記プロセスアクションは、前記検討中の画像の各画素をそれぞれのセグメントに割り当てる前記アクションを実施する前に、前記検討中の画像の隣接画素間の色差を平滑化するアクションをさらに含むことを特徴とする請求項２に記載の方法。
【請求項４】
前記検討中の画像の隣接画素間の色差を平滑化する前記プロセスアクションは、
各画素ごとにラスター順に、
前記検討中の画素に隣接する所定の数の連続する画素からなる各可能なグループを順に選択するアクションと、
各選択されたグループごとに、前記選択されたグループの各画素の各色成分の光強度を、前記検討中の画素の対応する色成分の光強度から減算し、結果として得られた差の２乗値を加算して前記選択されたグループの総差を生成するアクションと、
最小の総差を示すグループを特定するアクションと、
前記特定されたグループの各画素の色と前記選択された画素の色を平均するアクションと、
結果として得られた平均色を前記選択された画素の現在の色として割り当てるアクションと
を含むことを特徴とする請求項３に記載の方法。
【請求項５】
前記色平滑化手順は、所定の回数繰り返されることを特徴とする請求項４に記載の方法。
【請求項６】
連続する隣接画素の前記所定の数は、３であることを特徴とする請求項４に記載の方法。
【請求項７】
前記所定の順番は、ラスター順であることを特徴とする請求項２に記載の方法。
【請求項８】
前記所定の数の隣接画素は、４連結隣接画素（４−ｃｏｎｎｅｃｔｅｄ  ｎｅｉｇｈｂｏｒｓ）を含むことを特徴とする請求項２に記載の方法。
【請求項９】
領域に関する前記所定の画素数は、１００画素であることを特徴とする請求項２に記載の方法。
【請求項１０】
幅方向の前記所定の画素数は４０画素であり、高さ方向の前記所定の画素数は４０画素であることを特徴とする請求項２に記載の方法。
【請求項１１】
前記セグメントの平均色と前記検討中の画素の色との間の前記所定の差の閾値は、８であることを特徴とする請求項２に記載の方法。
【請求項１２】
各画像の各セグメントごとに前記初期ＤＳＤを計算する前記プロセスアクションは、
（ａ）一組の候補のディスパリティー、および各候補に対する奥行値を確定するアクションと、
（ｂ）候補のディスパリティーを選択するアクションと、
（ｃ）前記検討中の画像の隣接画像を選択するアクションと、
（ｄ）前記検討中のセグメントの各画素ごとに、
前記選択された候補のディスパリティーに関する前記奥行値を用いて前記画素を前記選択された隣接画像に投影して、前記投影された画素に対応する前記隣接画像中の画素を特定し、
対応する画素が特定された場合は、前記投影された画素と前記隣接画像中の前記特定された画素とに関する１つまたは複数の所定の利得比を計算するアクションと、
（ｅ）画素利得比ヒストグラムを生成するアクションと、
（ｆ）前記画素利得比ヒストグラムにおける３つの連続するビンの最大の和を計算するアクションと、
（ｇ）前記計算された和を、前記検討中のセグメントの、前記選択された候補のディスパリティーにおける前記選択された隣接画像についてのマッチングスコアとして指定するアクションと、
（ｈ）前記検討中の画像の残りの各隣接画像ごとに、アクション（ｃ）から（ｇ）を繰り返すアクションと、
（ｉ）残りの各候補のディスパリティーごとに、アクション（ｂ）から（ｈ）を繰り返すアクションと、
（ｊ）あるマッチングスコアに関連する各ディスパリティーごとに、前記検討中のディスパリティーで、すべての隣接画像について計算されたマッチングスコアの積を、前記マッチングスコアに関連するあらゆるディスパリティーで、すべての隣接画像について計算されたマッチングスコアの積の和によって除算して、前記ディスパリティーについてのＤＳＤ確率を生成するアクションと
を含むことを特徴とする請求項１に記載の方法。
【請求項１３】
前記複数の利得比は、各投影された画素および前記特定された隣接画像の各画素ごとに計算され、前記各画素に関する各色成分の利得比を含めて比較されることを特徴とする請求項１２に記載の方法。
【請求項１４】
対数スケールを使用して、前記画素利得比ヒストグラムの前記各ビンの範囲を確定することを特徴とする請求項１２に記載の方法。
【請求項１５】
前記画素利得比ヒストグラムは２０ビンを含むことを特徴とする請求項１４に記載の方法。
【請求項１６】
前記１組の候補のディスパリティーと各候補ごとの奥行値を確定する前記プロセスアク
ションは、
（ａ）ユーザ指定の最小および最大奥行値を入力するアクションと、
（ｂ）前記ユーザによって指定された前記最小奥行値を用いて、前記複数の画像のうちの視点に関して中央の画像の中心画素を、その隣接画像の１枚に投影するアクションと、
（ｃ）前記最小奥行値を、前記投影された中心画素に対応する隣接画像中の画素に関するディスパリティーに割り当てるアクションと、
（ｄ）前記中心画素を直前の投影から１ディスパリティーの場所に位置するように投影し、前記現在の中心画素の投影に関する奥行値を確定するアクションと、
（ｅ）前記最後に確定された奥行値が前記ユーザ指定の最大奥行値を超えたかどうかを判定するアクションと、
（ｆ）前記最後に確定された奥行値が前記ユーザ指定の最大奥行値を超えていないときはいつでも、前記最後に確定された奥行値がディスパリティーに割り当てられて、ディスパリティーは直前に割り当てられていたディスパリティーから１ディスパリティーレベル分インクリメントされた値に等しくなるアクションと、
（ｇ）最後に確定された奥行値がユーザ指定の最大奥行を超えたとアクション（ｅ）で判定されるまでアクション（ｄ）から（ｆ）が繰り返され、超えたと判定された時点で、奥行値が割り当てられてきた一連のディスパリティーが候補のディスパリティーとして指定されるアクションと
を含むことを特徴とする請求項１２に記載の方法。
【請求項１７】
各画像の各セグメントごとに、前記初期ＤＳＤの前記ディスパリティー確率値の前記初期推定値を精緻化する前記プロセスアクションは、
（ａ）各画像の各セグメントごとに、精緻化されたディスパリティー確率値を次式を用いて計算するアクションであって、
【数１】
2006012166.tif 000001
上式で、ｐij（ｄ）はセグメントｓijのディスパリティーｄに関して精緻化されたディスパリティー確率値であり、ｌij（ｄ）は前記平滑性制約を実施する関数であり、ｃijk（ｄ）は一組の隣接画像Ｎiの各隣接画像に関する前記一貫性制約を実施する関数であり、ｄ’は関連する確率値を有するすべてのディスパリティーであるアクションと、
（ｂ）アクション（ａ）を所定の回数繰り返すアクションと
を含むことを特徴とする請求項１に記載の方法。
【請求項１８】
前記所定の回数は、５０から６０の範囲であることを特徴とする請求項１７に記載の方法。
【請求項１９】
各画像の各画素に割り当てられた前記ディスパリティーを平滑化する前記プロセスアクションは、画像間平滑化を含み、前記画像間平滑化は、各画像の各画素ごとに順に、
前記検討中の画像の各隣接画像ごとに、
前記検討中の画素を前記隣接画像に投影し、前記投影された画素に対応する前記隣接画像中の画素を特定するアクションと、
前記検討中の画素に現在割り当てられている前記ディスパリティーと前記隣接画像中の前記対応する画素に割り当てられたディスパリティーの差の絶対値が所定のディスパリティーレベル数未満のときはいつでも、前記投影された画素と前記対応する画素のディスパリティーを平均し、前記平均を、関係する隣接画像に関するディスパリティー因数として前記検討中の画素に割り当てるアクションと、
前記検討中の画素に現在割り当てられている前記ディスパリティーと前記隣接画像中の前記対応する画素に割り当てられているディスパリティーの差の絶対値が所定のディスパリティーレベル数以上のときはいつでも、前記検討中の画素の前記ディスパリティーを、関係する隣接画像に関するディスパリティー因数として割り当てるアクションと、
前記各隣接画像に関して、前記検討中の画素に割り当てられた前記各ディスパリティー因数を加算し、その和を関係する隣接画像の数によって除算し、その結果を前記画素の現在のディスパリティーとして割り当てるアクションと
を含むことを特徴とする請求項１に記載の方法。
【請求項２０】
各画像の各画素に割り当てられている前記ディスパリティーを平滑化する前記プロセスアクションは、画像内平滑化をさらに含み、前記画像内平滑化は、各画像の各セグメントの各画素ごとに、前記検討中の画素を中心にした所定のサイズの窓の内部の画素で、前記検討中のセグメントの外部には存在しない画素に現在割り当てられている前記ディスパリティーを平均し、前記平均を、前記検討中の画素にその最終ディスパリティーとして割り当てるアクションを含むことを特徴とする請求項１９に記載の方法。
【請求項２１】
前記画像間平滑化および前記画像内平滑化は、所定の回数繰り返されることを特徴とする請求項２０に記載の方法。
【請求項２２】
前記所定のサイズの窓は、５×５画素の窓であることを特徴とする請求項２１に記載の方法。
【請求項２３】
前記各画像は前記シーンのある部分を描写し、前記シーンの前記部分は、前記画像のうちの少なくとも１枚の他の画像にキャプチャされた前記シーンの前記部分と、およそ６０から１００パーセントの範囲でオーバラップすることを特徴とする請求項１に記載の方法。
【請求項２４】
前記複数の画像は、同時にキャプチャされた動的シーンの画像を表すことを特徴とする請求項１に記載の方法。
【請求項２５】
前記同時にキャプチャされた画像は、様々な視点に置かれた複数のビデオカメラによってキャプチャされたビデオフレームを含むことを特徴とする請求項２４に記載の方法。
【請求項２６】
前記複数の画像は、様々な視点に置かれた複数のカメラ、あるいは各画像をキャプチャするために視点から視点に移動される単一のカメラによってキャプチャされた静的なシーンの画像を表すことを特徴とする請求項１に記載の方法。
【請求項２７】
あるシーンの３次元再構成を、様々な視点からキャプチャされた、前記シーンの複数のオーバラップする画像から計算するシステムであって、
前記シーンの様々な部分を見るために配置された複数のカメラを含むカメラ措置であって、各カメラの視界が各隣接するカメラの視界とオーバラップするカメラ装置と、
汎用コンピュータ装置と、
前記コンピュータ装置によって実行可能なプログラムモジュールを含むコンピュータプログラムと
を含み、前記コンピュータ装置は、前記コンピュータプログラムの前記プログラムモジュールによって、
各画像を、その画素が類似のディスパリティーを示すものと思われる各セグメントに分割し、
各画像の各セグメントごとに、一組の候補のディスパリティーの各々に対して、前記セグメントを構成する前記各画素が個々のディスパリティーを示す尤度を表す確率推定値を含むディスパリティー空間分布（ＤＳＤ）を計算し、
各画像の各セグメントごとに、前記セグメントの前記ＤＳＤの最大確率値に対応するディスパリティーを前記セグメントの各画素に割り当て、
各画像ごとに、前記シーンの同一の部分を描写する隣接画像内の対応する画素のディスパリティー、および前記画像の同一セグメント内の隣接画素のディスパリティーに基づいて、各画素に割り当てられた前記ディスパリティーを平滑化する
ように指示されることを特徴とするシステム。
【請求項２８】
各画像の各セグメントごとに前記ディスパリティー空間分布（ＤＳＤ）を計算するための前記プログラムモジュールは、
各画像の各セグメントごとに初期ディスパリティー空間分布（ＤＳＤ）を計算するサブモジュールと、
各画像の各セグメントごとに前記初期ＤＳＤの前記ディスパリティー確率の前記初期推定値を、前記同一画像内の隣接セグメントとの間の平滑性制約、および前記シーンの前記同一部分を描写する、他の画像内の対応するセグメントとの間の一貫性制約を同時に実施して精緻化することによって、精緻化されたＤＳＤを生成するサブモジュールと
を含むことを特徴とする請求項２７に記載のシステム。
【請求項２９】
各画像の各セグメントごとに、前記初期ＤＳＤの前記ディスパリティー確率の前記初期推定値を精緻化するための前記サブモジュールは、
各画像の各セグメントごとに、精緻化されたディスパリティー確率を次式によって計算するサブモジュールであって、
【数２】
2006012166.tif 000002
上式で、ｐij（ｄ）はセグメントｓijのディスパリティーｄに関して精緻化されたディスパリティー確率値であり、ｌij（ｄ）は前記平滑性制約を実施する関数であり、ｃijk（ｄ）は一組の隣接画像Ｎi内の各隣接画像に関する前記一貫性制約を実施する関数であり、ｄ’は関連する確率値を有するすべてのディスパリティーであるサブモジュールと、
前記精緻化されたディスパリティー確率計算サブモジュールを所定の回数繰り返すサブモジュールと
を含むことを特徴とする請求項２８に記載のシステム。
【請求項３０】
前記平滑性制約を実施する関数は次式を含み、
【数３】
2006012166.tif 000003
上式で、Ｓijはセグメントｓijの隣接セグメントであり、
【数４】
2006012166.tif 000004
はセグメントｓij∈Ｓijの現在の最大ディスパリティー推定値であり、εはオフセットであり、また
【数５】
2006012166.tif 000005
であり、上式で、νは幅スカラであり、
【数６】
2006012166.tif 000006
は
【数７】
2006012166.tif 000007
の最後に計算された確率であり、ｂilはｓilが占めるｓijの境界の割合であり、Δjlはセグメントｓijとｓilの画素の平均色の間の差であり、σΔは色差ガウス分布の分散であることを特徴とする請求項２９に記載のシステム。
【請求項３１】
ε＝０．０１、ν＝８であり、
【数８】
2006012166.tif 000008
であることを特徴とする請求項３０に記載のシステム。
【請求項３２】
前記一貫性制約を実施する関数は次式を含み、
【数９】
2006012166.tif 000009
上式で
【数１０】
2006012166.tif 000010
であり、上式でｐijk（ｄ）は、セグメントｓijの、ディスパリティーｄで隣接画像Ｉkに関して投影されたＤＳＤであり、Ｓijはセグメントｓijの隣接セグメントであり、π（ｋ，ｘ）は画素ｘを投影する画像Ｉk内のセグメントであり、したがって
【数１１】
2006012166.tif 000011
はセグメントπ（ｋ，ｘ）のディスパリティーｄでの確率であり、Ｃijはｓijの画素数であり、ｍijk（ｄ）はセグメントｓijの画像ｋにおけるディスパリティーｄでのマッチング関数であり、また
【数１２】
2006012166.tif 000012
であり、上式でνijはセグメントｓijが画像ｋ内で遮蔽される確率を表し、さらに
【数１３】
2006012166.tif 000013
であり、上式でｏijk（ｄ）は遮蔽関数であり、前記遮蔽関数は、ディスパリティーの推定に基づくｋ番目の画像の奥行において、画像Ｉkでｓijが見えない場合でも、その推定ディスパリティーに基づくｓijの奥行が表面要素の前方には位置しないことを保証するために、セグメントｓijが画像Ｉkの他のセグメントを遮蔽する場合には値０、遮蔽しない場合には値１であり、また、Ｃijはｓijの画素の数であり、
【数１４】
2006012166.tif 000014
はヘビサイドのステップ関数であり、ｘ≧０の場合は１、それ以外の場合は０であり、λは２つの表面が同一かどうかを判定するために使用される定数であることを特徴とする請求項２９に記載のシステム。
【請求項３３】
λは、４ディスパリティーレベルに設定されることを特徴とする請求項３２に記載のシステム。
【請求項３４】
あるシーンの３次元再構成を、様々な視点からキャプチャされた、前記シーンの複数の画像から計算するコンピュータ実行可能な命令を含むコンピュータ可読記録媒体であって、前記コンピュータ実行可能な命令は、
各画像を、その画素が類似のディスパリティーを示すものと思われる各セグメントに分割する命令と、
各画像の各セグメントごとに、一組の候補のディスパリティーの各々に対して、前記セグメントを構成する前記各画素が個々のディスパリティーを示す尤度を表す確率推定値を含むディスパリティー空間分布（ＤＳＤ）を計算する命令と、
各画像の各セグメントごとに、前記セグメントの前記ＤＳＤの最大確率値に対応するディスパリティーを前記セグメントの各画素に割り当てる命令と、
各画像ごとに、前記シーンの同一の部分を描写する隣接画像内の対応する画素のディスパリティー、および前記画像の同一セグメント内の隣接画素のディスパリティーに基づいて、各画素に割り当てられた前記ディスパリティーを平滑化する命令と
を含むことを特徴とするコンピュータ可読記録媒体。
ィスパリティーを前記セグメントの各画素に割り当てる命令と、
各画像ごとに、前記シーンの同一の部分を描写する隣接画像内の対応する画素のディスパリティー、および前記画像の同一セグメント内の隣接画素のディスパリティーに基づいて、各画素に割り当てられた前記ディスパリティーを平滑化する命令と
を含むことを特徴とするコンピュータ可読記録媒体。