(57)【要約】      （修正有）【課題】同じようなテクスチャが存在しても物体表面を正しく判定する。【解決手段】空間をボクセルで分割する。各々のボクセルにおける物体表面が存在する可能性を示す第一の値を、各々のボクセルに対応する各カメラの撮像素子上の点の画素値の類似性から求める（ステップ１）。一つのボクセルに注目し、注目点の周辺に複数の点を取り、該２つのカメラのレンズ中心から、それらの点を通るカメラ視線を引く。該カメラ視線同士の交点それぞれに対して、物体の存在する可能性を示す第二の値を、該交点の近傍のボクセルにおける第一の値から算出する。該全ての交点における第二の値に対して、各カメラ視線上ではそれぞれ１つの交点でのみ物体が存在するという拘束条件を用いた最適化アルゴリズムを適用し、注目するボクセルに、物体表面が存在する可能性を示す値を得る（ステップ２）。各ボクセルに対してステップ２の処理を実行する。【選択図】図８（ａ）
2008250582.tif 000002
【特許請求の範囲】
【請求項１】
複数のカメラにより同一の物体が撮影された画像の類似性から空間中のある点における物体の表面が存在する可能性を計算し、存在する可能性が高い点を該物体の表面とすることで該物体の表面の３次元形状データを生成する３次元形状データ生成装置における３次元形状データ生成方法において、
空間中のある点における物体の表面が存在する可能性を示す値の前記３次元形状データ生成装置による計算が、
空間をボクセルで分割する第一のステップと、
各々のボクセルにおける物体表面が存在する可能性を示す第一の値を、各々のボクセルに対応する各カメラの撮像素子上の点の画素値の類似性から求める第二のステップと、
前記ボクセルのうちの一つのボクセルに注目し、そのボクセル内の注目点の周辺に複数の点を取り、２つのカメラのレンズ中心から、それらの点を通るようなカメラ視線を引く第三のステップと、
前記カメラ視線同士の交点それぞれに対して、該交点における物体の存在する可能性を示す第二の値を、該交点の近傍のボクセルにおける第一の値から算出する第四のステップと、
前記交点における第二の値に対して、各カメラ視線上ではそれぞれ１つの交点でのみ物体が存在するという拘束条件を用いた最適化アルゴリズムを適用し、各交点における物体の表面の存在する可能性の値を補正した第三の値を算出し、前記注目点における第三の値を注目するボクセルに物体表面が存在する可能性を示す第四の値とする第五のステップと、
第一のステップで作成した他のボクセルに対して第三のステップから第五のステップまでの処理を実行する第六のステップと
からなることを特徴とする、３次元形状データ生成方法。
【請求項２】
請求項１記載の３次元形状データ生成方法において、
前記第一のステップにおいて、物体の表面が存在すると思われる領域の空間をボクセルで分割し、
前記第三のステップにおいて、前記注目点を注目するボクセルの中心点とし、該注目点と前記２つのカメラのレンズ中心とで成すエピポーラ面上に、該注目点の周辺に複数の点を取る
ことを特徴とする、３次元形状データ生成方法。
【請求項３】
請求項１または２記載の３次元形状データ生成方法において、
前記複数のカメラは３台以上であり、
前記第三のステップから前記第五のステップまでの処理を、前記複数のカメラから２台のカメラを、組み合わせを変えた複数の選び方で選択し、各組み合わせにおいて注目するボクセルに対する第四の値を計算して各組み合わせにおける第四の値を統合した値を、注目するボクセルに物体表面が存在する可能性を示す値とする第七のステップ
をさらに有することを特徴とする、３次元形状データ生成方法。
【請求項４】
複数のカメラにより同一の物体が撮影された画像の類似性から空間中のある点における物体の表面が存在する可能性を計算し、存在する可能性が高い点を該物体の表面とすることで該物体の表面の３次元形状データを生成する３次元形状データ生成装置における３次元形状データ生成方法において、
空間中のある点における物体の表面が存在する可能性を示す値の前記３次元形状データ生成装置による計算が、
空間をボクセル分割する第一のステップと、
前記ボクセルのうちの一つのボクセルに注目し、そのボクセル内の注目点の周辺に複数の点を取り、２つのカメラのレンズ中心から、それらの点を通るようなカメラ視線を引く第二のステップと、
前記カメラ視線同士の交点それぞれに対して、該交点における物体の存在する可能性を示す第一の値を、該交点に対応する該当２つのカメラの撮像素子上の対応点の画素値の類似性から算出する第三のステップと、
前記交点における第一の値に対して各カメラ視線上ではそれぞれ１つの交点でのみ物体が存在するという拘束条件を用いた最適化アルゴリズムを適用し、各交点における物体の表面の存在する可能性の値を補正した第二の値を算出し、注目点における第二の値を注目するボクセルに物体表面が存在する可能性を示す第三の値とする第四のステップと、
第一のステップで作成した他のボクセルに対して第二のステップから第四のステップまでの処理を実行する第五のステップと、
からなることを特徴とする、３次元形状データ生成方法。
【請求項５】
請求項４記載の３次元形状データ生成方法において、
前記第一のステップにおいて、物体の表面が存在すると思われる領域の空間をボクセルで分割し、
前記第二のステップにおいて、前記注目点を注目するボクセルの中心点とし、該注目点と前記２つのカメラのレンズ中心とで成すエピポーラ面上に、該注目点の周辺に複数の点を取る
ことを特徴とする、３次元形状データ生成方法。
【請求項６】
請求項４または５記載の３次元形状データ生成方法において、
前記複数のカメラは３台以上であり、
前記第二のステップから前記第四のステップまでの処理を、前記複数のカメラから２台のカメラを、組み合わせを変えた複数の選び方で選択し、各組み合わせにおいて注目するボクセルに対する第三の値を計算して各組み合わせにおける第三の値を統合した値を、注目するボクセルに物体表面が存在する可能性を示す値とする第六のステップ
をさらに有することを特徴とする、３次元形状データ生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数台のカメラで撮像した画像を用いて、物体の表面形状を３次元的に取得する技術に関する。
【背景技術】
【０００２】
従来の３次元形状データ生成方法について、以下に説明する。（たとえば、非特許文献１）
従来技術の代表的な全体処理の流れを図７を用いて説明する。（ａ）は物体表面を、確定した結果として得る場合の流れであり、（ｂ）は確率的な結果として得る場合の流れである。
【０００３】
まず、複数のカメラを用いて同一の物体を撮影する。
次に、３次元形状データを測定したい対象物体を含む３次元空間を、スペースカービング法で行っているように、ボクセルで分割する。
それから、撮影された画像同士の類似性から、各ボクセルにおける物体表面が存在する可能性を示す値を、全ボクセルについて算出する。
最後に、該物体表面が存在する可能性が高い点を該物体の表面とする、あるいは、該物体表面が存在する可能性から該物体の表面の存在する確率を算出する。
【０００４】
図１は、３次元空間のボクセルによる分割と複数カメラの撮像位置との関係を示す図である。図１を用いて、従来の３次元データ生成方法について説明する。この方法では、物体表面が存在する可能性の計算において、まず、測定したい３次元空間をボクセルで分割する。１０１はこの分割された１つのボクセルを示している。空間中にある物体を撮像するカメラが複数台あり、ここではｎ台あるものとする。１１１はそのうちの１つのカメラＣ１であり、便宜的に１台目のカメラとしている。１１２はカメラＣ１のレンズ、１１３はレンズ１１２のレンズ中心、１１４はカメラＣ１の撮像素子、１１５は撮像素子１１４の原点、１１６はボクセル１０１が結像している撮像素子１１４上の点、である。他のカメラＣ２〜Ｃｎも同様である。
【０００５】
カメラＣ１の１１１では、ボクセル１０１はレンズ１１２のレンズ中心１１３を通り、撮像素子１１４上の点１１６で結像する。ただし、点１１６の座標は点１１５を原点とする座標である。ボクセル１０１をｖとし、このボクセル内に物体表面があるかどうかの判定を、ボクセル１０１が結像している各カメラＣ１〜Ｃｎの撮像素子上の点の近傍の相違度の大きさで決める。ここで相違度とは、たとえば、以下のように標準偏差σｖとする。
【０００６】
【数１】
2008250582.tif 000003
【０００７】
ここで、ｍｖ，Ｃｉは３次元空間中のボクセルｖの中心をカメラＣｉで撮像したときのカメラＣｉの撮像素子上の結像位置、ａはカメラの撮像素子上のｍｖ，Ｃｉの近傍を示すベクトルの集合であり、ｍｖ，Ｃｉを原点としたベクトルの集合、ｐはａの中の１つのベクトル、Ｔ（ｋ）は撮像素子上の画素の座標ｋにおけるテクスチャであり、通常ＲＧＢの色濃度を要素とする色ベクトル、ｎＣはカメラ台数、バーＴｖ（ｐ）はｍｖ，Ｃｉの近傍内にある点の座標ｐについての全カメラのテクスチャの平均、｜ｘ｜２はｘの各要素の２乗和、を表す。なお、イメージデータの式で上部に線がある符号Ｔを、文章上では「バーＴ」と記載する。
【０００８】
物体表面のある微小領域から発した光は、各カメラの撮像素子上の対応する領域ではほぼ同一のテクスチャを持つものと考えられるため、標準偏差σｖは小さくなる。逆に標準偏差σｖが小さいほど、それに対応するボクセルｖには物体表面がある可能性が高くなる。したがって、標準偏差σｖを相違度とし、その相違度σｖに対して閾値τを設け、σｖ≧τであればそのボクセルｖには物体表面が存在せず、σｖ＜τであればそのボクセルｖには物体表面が存在する、と判定する。
【０００９】
【非特許文献１】K. N. Kutulakos and S. M. Seitz,“A theory of shape by space carving”, Int. J. Comput. Vision, Vol.38, No.3, pp.199-218, 2000
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、上記従来方法では、３次元空間上の物体表面に同じようなテクスチャが存在した場合に、物体表面が存在しないボクセルの相違度が小さくなって物体表面か否かの判断に間違いを起こす可能性がある、という欠点があった。
【００１１】
この説明を図２を用いて行う。図の上方の曲線は物体表面を示す実曲線であり、その周りの点直線はボクセル境界を示す。下方にある２１１はカメラＣ１、２１２はレンズ、２１３はレンズ中心、２１４は撮像素子、である。２０３は物体表面上の小領域ａ、２０４は物体表面上の小領域ｂ、２０３１は２０３の小領域ａをカメラＣ１で撮像した際の撮像素子上に結像した領域ａＣ１、２０３２は２０３の小領域ａをカメラＣ２で撮像した際の撮像素子上に結像した領域ａＣ２、２０４２は２０４の小領域ｂをカメラＣ２で撮像した際の撮像素子上に結像した領域ｂＣ２、２０１は２０３の物体表面小領域ａとカメラＣ１のレンズ中心とを結ぶ線と２０４の物体表面小領域ｂとカメラＣ２のレンズ中心とを結ぶ線との交点を含むボクセルｖ１、２０２は２０３の物体表面小領域ａを含むボクセルｖ２、である。
【００１２】
物体表面上の小領域ａが結像した撮像素子上の小領域ａＣ１とａＣ２では、同じ小領域ａを結像した領域であるため、テクスチャがほぼ等しく、相違度σｖが小さくなり、小領域ａを含むボクセルｖ２を物体表面と正しく判定する。しかし、もし、物体表面上の小領域ａと物体表面上の小領域ｂのテクスチャの差が小さい場合、小領域ａＣ１とｂＣ２のテクスチャがほぼ等しくなり、相違度σｖが小さくなり、物体表面を含まないボクセルｖ１を物体表面と誤って判定する。
【００１３】
以上のように、従来の方法では、物体表面に同じようなテクスチャが存在した場合に物体表面か否かの判断に間違いを起こす可能性がある、という欠点があった。
【００１４】
本発明は、上記に鑑みてなされたものであり、その目的とするところは、物体表面に同じようなテクスチャが存在した場合であっても、物体表面を正しく判定する３次元形状データ生成方法を提供することにある。
【課題を解決するための手段】
【００１５】
本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、以下の通りである。
【００１６】
第一の発明は、複数のカメラにより同一の物体が撮影された画像の類似性から空間中のある点における物体の表面が存在する可能性を計算し、存在する可能性が高い点を該物体の表面とすることで該物体の表面の３次元形状データを生成する３次元形状データ生成装置における３次元形状データ生成方法であり、空間中のある点における物体の表面が存在する可能性を示す値の前記３次元形状データ生成装置による計算が、空間をボクセル分割する第一のステップ（実施の形態１のステップ１に対応）と、各々のボクセルにおける物体表面が存在する可能性を示す第一の値を、各々のボクセルに対応する各カメラの撮像素子上の点の画素値の類似性から求める第二のステップ（実施の形態１のステップ２に対応）と、前記ボクセルのうちの一つのボクセルに注目し、そのボクセル内の注目点の周辺に複数の点を取り、２つのカメラのレンズ中心から、それらの点を通るようなカメラ視線を引く第三のステップ（実施の形態１のステップ３に対応）と、前記カメラ視線同士の交点それぞれに対して、該交点における物体の存在する可能性を示す第二の値を、該交点の近傍のボクセルにおける第一の値から算出する第四のステップ（実施の形態１のステップ４に対応）と、前記交点における第二の値に対して、各カメラ視線上ではそれぞれ１つの交点でのみ物体が存在するという拘束条件を用いた最適化アルゴリズムを適用し、各交点における物体の表面の存在する可能性の値を補正した第三の値を算出し、前記注目点における第三の値を注目するボクセルに物体表面が存在する可能性を示す第四の値とする第五のステップ（実施の形態１のステップ５−１〜５−３に対応）と、第一のステップで作成した他のボクセルに対して第三のステップから第五のステップまでの処理を実行する第六のステップ（実施の形態１のステップ６に対応）とからなることを特徴とする。
【００１７】
第二の発明は、上記第一の発明の３次元形状データ生成方法において、前記第一のステップにおいて、物体の表面が存在すると思われる領域の空間をボクセルで分割し、前記第三のステップにおいて、前記注目点を注目するボクセルの中心点とし、該注目点と前記２つのカメラのレンズ中心とで成すエピポーラ面上に、該注目点の周辺に複数の点を取ることを特徴とする。
【００１８】
第三の発明は、上記第一または第二の発明の３次元形状データ生成方法において、前記複数のカメラは３台以上であり、前記第三のステップから前記第五のステップまでの処理を、第三のステップにおける複数のカメラから２台のカメラを、組み合わせを変えた複数の選び方で選択し、各組み合わせにおいて注目するボクセルに対する第四の値を計算して各組み合わせにおける第四の値を統合した値を、注目するボクセルに物体表面が存在する可能性を示す値とする第七のステップ（実施の形態１のステップ５−４、５−５に対応）をさらに有することを特徴とする。
【００１９】
第四の発明は、複数のカメラにより同一の物体が撮影された画像の類似性から空間中のある点における物体の表面が存在する可能性を計算し、存在する可能性が高い点を該物体の表面とすることで該物体の表面の３次元形状データを生成する３次元形状データ生成装置における３次元形状データ生成方法であり、空間中のある点における物体の表面が存在する可能性を示す値の前記３次元形状データ生成装置による計算が、空間をボクセル分割する第一のステップ（実施の形態２のステップ１に対応）と、前記ボクセルのうちの一つのボクセルに注目し、そのボクセル内の注目点の周辺に複数の点を取り、２つのカメラのレンズ中心から、それらの点を通るようなカメラ視線を引く第二のステップ（実施の形態２のステップ２−１に対応）と、前記カメラ視線同士の交点それぞれに対して、該交点における物体の存在する可能性を示す第一の値を、該交点に対応する該当２つのカメラの撮像素子上の対応点の画素値の類似性から算出する第三のステップ（実施の形態２のステップ２−２に対応）と、前記交点における第一の値に対して、各カメラ視線上ではそれぞれ１つの交点でのみ物体が存在するという拘束条件を用いた最適化アルゴリズムを適用し、各交点における物体の表面の存在する可能性の値を補正した第二の値を算出し、注目点における第二の値を注目するボクセルに物体表面が存在する可能性を示す第三の値とする第四のステップ（実施の形態２のステップ２−３−１〜２−３−３に対応）と、第一のステップで作成した他のボクセルに対して第二のステップから第四のステップまでの処理を実行する第五のステップ（実施の形態２のステップ３に対応）とからなることを特徴とする。
【００２０】
第五の発明は、上記第４の発明の３次元形状データ生成方法において、前記第一のステップにおいて、物体の表面が存在すると思われる領域の空間をボクセルで分割し、前記第二のステップにおいて、前記注目点を注目するボクセルの中心点とし、該注目点と前記２つのカメラのレンズ中心とで成すエピポーラ面上に、該注目点の周辺に複数の点を取ることを特徴とする。
【００２１】
第六の発明は、上記第四または第五の発明の３次元形状データ生成方法において、前記複数のカメラは３台以上であり、前記第二のステップから前記第四のステップまでの処理を、前記複数のカメラから２台のカメラを、組み合わせを変えた複数の選び方で選択し、各組み合わせにおいて注目するボクセルに対する第三の値を計算して各組み合わせにおける第三の値を統合した値を、注目するボクセルに物体表面が存在する可能性を示す値とする第六のステップ（実施の形態２のステップ２−３−４〜２−３−５に対応）をさらに有することを特徴とする。
【発明の効果】
【００２２】
本発明は、各ボクセルの信頼度を、カメラペアから得られる３次元的な整合性を持つように、カメラペアの視線の交点上の信頼度が幾何学的な矛盾が少なくなるように最適化を行って得ているため、各ボクセルの信頼度の精度が向上し、その結果、物体表面に同じようなテクスチャが存在した場合であっても、物体表面を正しく判定できるという利点がある。
【００２３】
また、本発明は、各ボクセルの信頼度がカメラペアから得られる３次元的な整合性を持つため、信頼度の信頼性が向上するという利点がある。
【００２４】
また、本発明は、複数のカメラペアの結果を統合するため、信頼度の信頼性が向上するという利点がある。
【発明を実施するための最良の形態】
【００２５】
［実施の形態１］
実施の形態１の処理の流れを図８を用いて説明する。図８（ａ）は物体表面を、確定した結果として得る場合の流れであり、図８（ｂ）は確率的な結果として得る場合の流れである。
【００２６】
まず、複数のカメラを用いて同一の物体を撮影する。
撮影された画像データを用いて、３次元形状データ生成装置（図示していない）が以下の計算を行う。３次元形状データ生成装置は、記憶装置に記憶されたプログラムとコンピュータで構成することができ、また、そのプログラムの一部または全部に代えてハードウェアを用いることもできる。
３次元形状データを測定したい対象物体の表面が存在すると思われる３次元空間を、スペースカービング法で行っているように、ボクセルで分割する。
次に、撮影された画像同士の類似性から、各ボクセルにおける物体表面が存在する可能性を示す値を、全ボクセルについて算出する。
次に、１つのボクセルに注目して、その周辺に複数の点をとり、選んだ２つのカメラのレンズ中心から、それらの点を通るようなカメラ視線を引く。
次に、カメラ視線同士の交点それぞれに対して、物体表面の存在する可能性を示す値を算出する。
次に、最適化アルゴリズムを適用し、注目点における物体表面の存在する可能性を示す値、および、周辺の点数の点における物体表面の存在する可能性を示す値を補正した値を算出し、注目点における値を物体表面の存在確率を示す値とする。
上記を全てのカメラから２つ選ぶ全組み合わせについて、それぞれ、注目点における物体表面の存在確率を求め、これらを統合したものを、注目点における物体表面の存在確率とする。
全ボクセルにおいて物体表面が存在する可能性を示す値を計算する。
【００２７】
最後に、該物体表面が存在する可能性が高い点を該物体の表面とする、あるいは、該物体表面が存在する可能性から該物体の表面の存在する確率を算出する。
【００２８】
以下、図面を用いて本発明の実施の形態１を詳細に説明する。
図１、図３〜図６を用いて、実施の形態１の３次元データ生成方法について説明する。この方法は、複数のカメラを用いて同一の物体を撮影し、撮影された画像の類似性から空間中のある点における物体の表面が存在する可能性を計算し、存在する可能性が高い点を該物体の表面とすること、または、存在する可能性から該物体の表面の存在する確率を計算することで、該物体の表面の３次元形状データを生成する方法である。以下、物体の表面が存在する可能性を計算する方法について詳述する。
【００２９】
（ステップ１：空間のボクセル分割）
図１に示すように、３次元形状データを測定したい対象物体を含む３次元空間を、スペースカービング法で行っているように、ボクセルで分割する。１０１はこの分割された１つのボクセルを示している。空間中にある物体を撮像するカメラが複数台あり、ここではｎ台あるものとする。１１１はそのうちの１つのカメラＣ１であり、便宜的に１台目のカメラとしている。１１２はカメラＣ１のレンズ、１１３はレンズ１１２のレンズ中心、１１４はカメラＣ１の撮像素子、１１５は撮像素子１１４の原点、１１６はボクセル１０１が結像すると計算される撮像素子１１４上の対応点、である。他のカメラＣ２〜Ｃｎも同様である。
【００３０】
カメラＣ１の１１１では、ボクセル１０１はレンズ１１２のレンズ中心１１３を通り、撮像素子１１４上の点１１６で結像する。ただし、点１１６の座標は点１１５を原点とする座標系で表される。
【００３１】
（ステップ２：ボクセルにおける物体表面がある可能性の仮の算出）
ボクセル１０１をｖとし、このボクセル内に物体表面があるかどうかの可能性を示す値（＝信頼度）を、ボクセル１０１が結像している各カメラＣ１〜Ｃｎの撮像素子上の点、もしくは、その点の近傍の点の画素値の類似性で決める。たとえば、類似性を表す値とは、同一ボクセル１０１が結像していると計算される、全てのカメラの撮像素子上の対応点、および、その点の近傍点の画素値の標準偏差に類する値である。
【００３２】
以下、相違度ｄｉｓＲを用いて類似性を計算する方法を述べる。相違度ｄｉｓＲは、たとえば、以下のように計算する。
【００３３】
【数２】
2008250582.tif 000004
【００３４】
ここで、ｍｖ，Ｃｉは３次元空間中のボクセルｖの中心をカメラＣｉで撮像したときのカメラＣｉの撮像素子上の結像位置、ａはカメラの撮像素子上のｍｖ，Ｃｉの近傍を示すベクトルの集合であり、ｍｖ，Ｃｉを原点としたベクトルの集合、ｐはａの中の１つのベクトル、Ｔ（ｋ）は撮像素子上の画素の座標ｋにおけるテクスチャであり、通常ＲＧＢの色濃度を要素とする色ベクトル、ｎＣはカメラ台数、バーＴｖ（ｋ）はｍｖ，Ｃｉの近傍内にある点の座標ｐについての全カメラのテクスチャの平均、｜ｘ｜はｘの大きさを表し、たとえば、各要素の２乗和の平方根、ｍはテクスチャの分散（｜Ｔ−Ｔの平均｜で表される）に対するｄｉｓＲや信頼度の変化の仕方を変える値、である。
【００３５】
テクスチャＴ（ｍｖ，Ｃｉ＋ｐ）の求め方の一例について図５を用いて説明する。ここで、５０１はカメラＣ１、Ｃ２のカメラ視線の交点、５０２はカメラＣ１のカメラ視線、５０３はカメラＣ１のカメラ視線と撮像素子の交点、５０４はカメラＣ１のカメラ視線の近傍の撮像素子上の画素群、５０５はカメラＣ１のカメラ視線と撮像素子の交点を中心とする、撮像素子の画素と同じ大きさの四角形、５０６はカメラＣ１のカメラ視線と撮像素子の交点を中心とする、撮像素子の画素と同じ大きさの四角形の近傍の、撮像素子の画素と同じ大きさの四角形、５１２はカメラＣ２のカメラ視線、５１３はカメラＣ２のカメラ視線と撮像素子の交点、５１４はカメラＣ２のカメラ視線の近傍の撮像素子上の画素群、５１５はカメラＣ２のカメラ視線と撮像素子の交点を中心とする、撮像素子の画素と同じ大きさの四角形、である。
【００３６】
撮像素子上の画素の座標ｍｖ，Ｃｉは、撮像素子の画素の座標と一致するとは限らないので、ａが画素幅を単位とするベクトルの集合だとしても、ｍｖ，Ｃｉ＋ｐは撮像素子の画素の座標とは一致しない。この様子を図５（ａ）に示す。図５（ａ）では、カメラ視線の交点５０１を通る２本の視線がそれぞれカメラＣ１、Ｃ２の撮像素子上で、５０３と５１３で示す点で交わっており、その点がそれぞれのカメラの撮像素子上の画素の中心とはずれている様子を示している。
【００３７】
図５（ｂ）はカメラＣ１の撮像素子を真上から見た図であり、５０５のカメラ視線との交点を含む撮像素子と同じ大きさの四角形と、その周りに、同じ大きさの四角形５０６を描いている。ｍｖ，Ｃｉは５０３の座標、ａは５０５、５０６のそれぞれの四角形の中心座標に対応する。ただし、これは図５（ｂ）に図示したように、ａが交点を中心とした９つの座標となる場合のものである。
【００３８】
図５（ｃ）はカメラ視線と撮像素子の交点を中心とする、撮像素子の画素と同じ大きさの四角形と、撮像素子の画素との関係を示した図であり、ｍｖ，Ｃｉは、撮像素子の画素の座標、ｍｎ１（ｖ），Ｃｉ、ｍｎ２（ｖ），Ｃｉ、ｍｎ３（ｖ），Ｃｉ、ｍｎ４（ｖ），Ｃｉは、カメラ視線と撮像素子の交点を中心とする、撮像素子と同じ大きさの四角形と重なる、撮像素子の画素の中心の座標である。図中のｓ、ｔは重なる割合を示しており、０≦ｓ，ｔ≦１である。このとき、テクスチャＴ（ｍｖ，Ｃｉ）は以下のように、バイリニア法を使って計算することができる。
【００３９】
【数３】
2008250582.tif 000005
【００４０】
ここではバイリニア法を示したが、その他、ニアレストネイバー法、バイキュービック法等の既存の補間方法を使用しても良い。ａ内でｐを変えた場合のテクスチャＴ（ｍｖ，Ｃｉ＋ｐ）も同様に計算できる。
【００４１】
物体表面のある微小領域から発した光は、各カメラの撮像素子上の対応する領域ではほぼ同一のテクスチャを持つものと考えられるため、相違度ｄｉｓＲは小さくなる。逆に相違度ｄｉｓＲが小さいほど、それに対応するボクセルｖには物体表面がある可能性が高くなる。
【００４２】
相違度ｄｉｓＲからその逆の性質を持つ類似度Ｒを、たとえば、以下のように求める。
【００４３】
【数４】
2008250582.tif 000006
【００４４】
ここで、σは相違度ｄｉｓＲに対する類似度Ｒへの影響を調整するパラメタであり、σが小さいほど、相違度のわずかの違いで類似度の大きさが変化する。
【００４５】
この類似度が大きいボクセルほど、物体表面がそのボクセル中にある可能性が高い。この可能性を信頼度と呼ぶこととしｐであらわすこととする。ｐを以下のようにする。なお、このｐは（８．１）式等におけるベクトルのｐとは異なる。イメージデータである式においてはこれらは区別できるが、文章上では区別がつかないので、以下、文章上では「信頼度ｐ」と記載する。
【００４６】
【数５】
2008250582.tif 000007
【００４７】
全てのボクセルについて信頼度を算出する。
【００４８】
ボクセルの信頼度の精度を上げるため、下記に示すような処理により信頼度の再計算による補正を行う。
【００４９】
（ステップ３：注目ボクセルの周囲の点の決定）
複数のカメラの中から１つのカメラのペアを選び、下記に示すようなカメラ視線を引いて、その交点である注目ボクセルの近傍点を決定する。このカメラ視線の引き方について図３を用いて説明する。
【００５０】
３０１は信頼度を計算し直そうとしている注目ボクセルｖ、３０２は物体表面の有無を調べたい３次元空間上の範囲であり、ボクセルで分割する３次元空間上の範囲、である。空間中にある物体を撮像するカメラが複数台あるが、ここではその中のカメラのペアの１組Ｃ１、Ｃ２のみを示している。３１１はそのうちの１つのカメラＣ１、３１２はカメラＣ１のレンズ、３１３はレンズ３１２のレンズ中心、３１４はカメラＣ１の撮像素子、３１５は撮像素子３１４の画素、である。他のカメラＣ２も同様である。３０３は注目ボクセルｖを通り、カメラＣ１、Ｃ２のレンズ中心を通る線に平行な線Ｌ、である。
【００５１】
（ステップ３−１：エピポーラ平面の決定）
信頼度ｐの精度を上げたい注目ボクセルｖを決める。このときボクセルｖとＣ１、Ｃ２のカメラのそれぞれのカメラレンズの中心を含む平面上が決まる。この平面をエピポーラ平面という。
【００５２】
（ステップ３−２：２つのカメラ中心に平行な線Ｌの決定）
エピポーラ平面上にあって、カメラＣ１、Ｃ２のそれぞれのレンズ中心を通る線に平行であり、注目ボクセルｖの中心を通る線Ｌを引く。
【００５３】
（ステップ３−３：線Ｌ上の注目ボクセルの周囲の点の決定）
注目ボクセルｖの中心点（注目点、図３の三重丸）の周辺に、線Ｌ上のボクセルｖの中心点を起点として、一定の間隔で、線Ｌ上に点を取っていく（図３の二重丸）。なお、この点にはボクセル中心の点も含まれるものとする。また、注目点は注目ボクセルｖの中心点に限らず、注目ボクセルｖ内の任意の点であってもよい。間隔は、たとえば、ボクセルの辺の間隔でもよいが、これに限る必要はない。さらに、ここでは等間隔としたが、必ずしも等間隔である必要は無い。また、点を取る幾何学的な範囲は、特に限る必要はなく、ボクセル全体をカバーする範囲であっても良い。
【００５４】
（ステップ３−４：線Ｌ上を通るカメラ視線引きと注目ボクセルの周囲の点の決定）
カメラＣ１、Ｃ２のレンズ中心から上記各点（線Ｌ上の注目ボクセルの周囲の点）を通る線（カメラ視線）を引く。図３は線Ｌがボクセルのある１つの辺と平行な場合についての図であり、一点鎖線が、等間隔に取った上記各点とＣ１、Ｃ２のレンズ中心とを結んだ、カメラ視線である。
【００５５】
線Ｌ上の等間隔にとった各点、および、それらの点とＣ１、Ｃ２のレンズ中心とを結んだカメラ視線は、同じエピポーラ面上にあるので、カメラ視線同士はお互いに交わる。図中の白丸、二重丸、および、三重丸はそれらの交点を示している。
【００５６】
（ステップ４：カメラ視線の各交点における信頼度の算出）
各カメラ視線上の交点における信頼度を、各交点の近傍のボクセルの信頼度から求める。図４を用いてその例を示す。４０１はカメラ視線の交点、４０２はカメラ視線の交点を含む立体、４０３はカメラ視線の交点の近傍のボクセル群であり、４０２の立体と重なる部分を持つボクセル群、である。
【００５７】
４０１の交点における信頼度ｐＣ１Ｃ２ｄ（ｉ，ｊ）（ただし、（ｉ，ｊ）はカメラＣ１、Ｃ２から出ている視線を区別する番号であり、（ｉ，ｊ）＝（ｉｖ，ｊｖ）は注目ボクセルｖの中心を通るカメラ視線であることを示す）は、４０３近傍のボクセル群をｖ１〜ｖｍとし、それらの信頼度はそれぞれ信頼度ｐＣ１Ｃ２，１，（ｉ，ｊ）〜ｐＣ１Ｃ２，ｍ，（ｉ，ｊ）、それらボクセル群と４０２の立体との重なっている体積に対する４０２の立体に対する割合をｒ１〜ｒｍとすると以下のように計算する。
【００５８】
【数６】
2008250582.tif 000008
【００５９】
もし、４０２の立体が４０１の交点を中心とするボクセルと同じ大きさであれば、ｍ＝８となる。
【００６０】
（ステップ５：信頼度の補正）
各カメラ視線上においては、１点のみに物体の表面が存在するはずである。そこで、この拘束条件を用いて、各交点における信頼度の精度を上げるための信頼度の補正を行う。
【００６１】
図３のカメラＣ１の視線上に物体表面がある場合、各交点における物体表面が存在する可能性はその物体表面に近い視線の交点のみで信頼度が大きく、そのほかの交点は小さくなることが望ましい。各交点での信頼度がそのようになるように以下の処理を行う。
【００６２】
図６は本処理を説明する図である。図３のカメラ視線と視線の交点を再現したものを図６（ａ）に示す。一点鎖線はカメラ視線、白丸と三重丸はカメラ視線の交点を示す。特に、三重丸は注目ボクセルｖの中心点を示す。図６（ｂ）はカメラ視線を便宜的に平行になるように幾何学変換したものである。図６（ａ）に示すカメラ視線は交わらないものがあるが、図６（ｂ）には黒丸で示した部分がその部分である。Ｃ１側、Ｃ２側とは、カメラが置かれている側を示している。
【００６３】
（ステップ５−１：カメラ視線の交点の置き換え）
図６（ｂ）の白丸、および、三重丸で示すカメラ視線の交点には、図６（ａ）で示すもとの信頼度を割り当て、図６（ｂ）の黒丸で示す実際には交わらない点には、０を割り当てる。
【００６４】
（ステップ５−２：カメラ視線の交点の信頼度の最適化）
図６（ｂ）のカメラ視線の交点の信頼度は、各行、各列で１つだけ大きくなることが望ましいので、たとえば、以下のようなエネルギー関数Ｅをつくり、これを最小化することを考える。
【００６５】
【数７】
2008250582.tif 000009
【００６６】
ここで、信頼度ｐＣ１Ｃ２ｄ（ｉ，ｊ）は図６に表記のｉ行ｊ列の点の信頼度、ｎＣ１、ｎＣ２はそれぞれＣ１、Ｃ２側の線の数、Ａ、Ｂは適当な大きさの定数を示す。
【００６７】
この式を、クロネッカーのデルタ関数を用いて、１＝（１−δｉｊ）＋δｉｊを第１、２項のそれぞれに代入し、以下のように多重一次形式に変換する。
【００６８】
【数８】
2008250582.tif 000010
【００６９】
このエネルギー関数を用いて、下記の力学系を作る。
【００７０】
【数９】
2008250582.tif 000011
【００７１】
この力学系を用いてエネルギー関数を最小化するには、たとえば、下記のようにＥｕｌｅｒ法を用いるとよい。
【００７２】
まず、信頼度ｐＣ１Ｃ２ｄ（ｉ，ｊ）に（８．５）式で計算した信頼度で初期化し、次に、
【００７３】
【数１０】
2008250582.tif 000012
【００７４】
を計算し、次に、
【００７５】
【数１１】
2008250582.tif 000013
【００７６】
を計算する。ただし、Δは時間刻み幅の最大値であり、ユーザが決める定数である。ｗはベクトルｗ＝（ｗ１１，…，ｗＣ１Ｃ２）のノルムであり、たとえば、ベクトルの各エレメントの２乗和としてもよい。
【００７７】
次に、信頼度ｐｄ（ｉ，ｊ）を次のように更新する。
【００７８】
【数１２】
2008250582.tif 000014
【００７９】
終了条件としては、たとえば、以下の条件を用いることが考えられる。
【００８０】
【数１３】
2008250582.tif 000015
【００８１】
ここで、εはユーザが決めるしきい値である。
【００８２】
上記のような終了条件を満たすまで、繰り返して（８．９）、（８．１０）、（８．１１）式を行って（８．６）式、または、（８．７）式で示されたエネルギー関数を小さくしていきながら信頼度を更新していき、終了条件を満たしたところで繰り返しを終了する。
【００８３】
本実施例では、エネルギー関数の最小化を、Ｅｕｌｅｒ法を用いて行い、信頼度の補正を求める例を示したが、ここに示した手法に限られることなく、ニューラルネットワークを用いた組み合わせ最適化問題を解く手法等を用いても良い。
【００８４】
（ステップ５−３：最適化された信頼度の注目ボクセルの信頼度への置き換え）
ステップ５−２を使って計算した、図６（ｂ）に示す三重丸の注目ボクセルｖの中心の信頼度を、新たに図６（ａ）に示す三重丸の注目ボクセルの信頼度とする。
【００８５】
ステップ３で選んだカメラのペアを固定せず、複数のペアに対して同様の信頼度を求め、求められた信頼度を統合して、さらに信頼度の精度を上げることもできる。この場合には、以下のステップ５−４、５−５を追加する。
【００８６】
（ステップ５−４：他のカメラペアにおける信頼度の最適化）
１つのボクセルに関して、複数のカメラペアについて、ステップ３〜５−３を行う。
【００８７】
（ステップ５−５：複数カメラペアから算出された信頼度の統合）
１つのボクセルに関して、複数のカメラペアから得られた信頼度を統合する。
統合には、例えば以下のようにする。
【００８８】
【数１４】
2008250582.tif 000016
【００８９】
ここで、信頼度ｐＣｒＣｓｄ（ｉｖ，ｊｖ）はカメラペアＣｒ、Ｃｓによって得られた、調べたいボクセルｖの信頼度であり、信頼度ｐｄはそれらを統合した信頼度である。
【００９０】
信頼度は、次のように計算してもよい。
【００９１】
【数１５】
2008250582.tif 000017
【００９２】
Ｂｉａｓはユーザが決める定数である。Ｂｉａｓは、たとえば、１とすれば、信頼度ｐＣｒＣｓｄ（ｉｖ，ｊｖ）が小さいものはその影響を小さくすることができる。
【００９３】
（ステップ６：全ボクセルについての信頼度の最適化と統合）
全てのボクセルについて、ステップ３〜５を行う。
【００９４】
以上のステップにより、全ボクセルの信頼度が計算される。
【００９５】
ステップ３〜６を繰り返し実行し、全ボクセルの信頼度の信頼性をさらに上げることもできる。この場合は、以下のステップ７を追加する。
【００９６】
（ステップ７：信頼度の最計算の繰り返し実行）
ステップ３〜６を繰り返し実行する。
【００９７】
（ステップ８：３次元形状データの出力）
最後に、再計算によって算出された全ボクセルの信頼度を３次元形状データとする。
【００９８】
さらに、この全ボクセルの信頼度を用いて、表面が有るか無いかといった２値的なデータを求めることができ、この表面の有無を３次元形状データとすることもできる。この場合は、以下のステップ９を追加する。
【００９９】
（ステップ９：表面の有無の判別とそのデータの出力）
このためには、たとえば、あらかじめ決められた閾値を用いて、その閾値以上の信頼度を持つボクセルには物体表面が存在し、それ以外のボクセルには物体表面が存在しないと判断し、その判断結果を３次元形状データとする。
【０１００】
上記閾値は、上記のようにあらかじめ決めることもできるが、その他に、全ボクセルの信頼度の確率密度関数（信頼度の大きさを入力とし、その生起確率を出力とする関数）を用いて、最小２乗エラーを最小化する既存の２値化アルゴリズム（たとえば、大津の閾値選定法）や、平均誤識別率を最小にする既存の２値化アルゴリズム（たとえば、ｋｉｔｔｌｅｒの閾値選定法）を使って、閾値を決めてもよい。
【０１０１】
本実施の形態の効果としては、各ボクセルの信頼度を、カメラペアから得られる３次元的な整合性を持つように、カメラペアの視線の交点上の信頼度が幾何学的な矛盾が少なくなるように最適化を行って得ているため、各ボクセルの信頼度の精度が向上し、その結果、物体表面に同じようなテクスチャが存在した場合であっても、物体表面を正しく判定できるという利点がある。
【０１０２】
また、本実施の形態の効果としては、各ボクセルの信頼度がカメラペアから得られる３次元的な整合性を持つため、信頼度の信頼性が向上するという利点がある。
また、本実施の形態の効果としては、複数のカメラペアの結果を統合するため、信頼度の信頼性が向上するという利点がある。
【０１０３】
［実施の形態２］
実施の形態２の処理の流れを図９を用いて説明する。（ａ）は物体表面を、確定した結果として得る場合の流れであり、（ｂ）は確率的な結果として得る場合の流れである。
【０１０４】
まず、複数のカメラを用いて同一の物体を撮影する。
撮影された画像データを用いて、３次元形状データ生成装置（図示していない）が以下の計算を行う。３次元形状データ生成装置は、記憶装置に記憶されたプログラムとコンピュータで構成することができ、また、そのプログラムの一部または全部に代えてハードウェアを用いることもできる。
３次元形状データを測定したい対象物体の表面が存在すると思われる３次元空間を、スペースカービング法で行っているように、ボクセルで分割する。
次に、１つのボクセルに注目して、その周辺に複数の点をとり、選んだ２つのカメラのレンズ中心から、それらの点を通るようなカメラ視線を引く。
次に、カメラ視線同士の交点それぞれに対して、物体表面の存在する可能性を示す値を算出する。
次に、最適化アルゴリズムを適用し、注目点における物体表面の存在する可能性を示す値、および、周辺の点数の点における物体表面の存在する可能性を示す値を補正した値を算出し、注目点における値を物体表面の存在確率を示す値とする。
上記を全てのカメラから２つ選ぶ全組み合わせについて、それぞれ、注目点における物体表面の存在確率を求め、これらを統合したものを、注目点における物体表面の存在確率とする。
全ボクセルにおいて物体表面が存在する可能性を示す値を計算する。
最後に、該物体表面が存在する可能性が高い点を該物体の表面とする、あるいは、該物体表面が存在する可能性から該物体の表面の存在する確率を算出する。
【０１０５】
以下、図面を用いて本発明の実施の形態２を詳細に説明する。
【０１０６】
図１、図３、図５、図６を用いて、実施の形態２の３次元データ生成方法について説明する。この方法は、複数のカメラを用いて同一の物体を撮影し、撮影された画像の類似性から空間中のある点における物体の表面が存在する可能性を計算し、存在する可能性が高い点を該物体の表面とすること、または、存在する可能性から該物体の表面の存在する確率を計算することで、該物体の表面の３次元形状データを生成する方法である。以下、物体の表面が存在する可能性を計算する方法について詳述する。
【０１０７】
（ステップ１：空間のボクセル分割）
図１に示すように、３次元形状データを測定したい対象物体を含む３次元空間を、スペースカービング法で行っているように、ボクセルで分割する。１０１はこの分割された１つのボクセルを示している。空間中にある物体を撮像するカメラが複数台あり、ここではｎ台あるものとする。１１１はそのうちの１つのカメラＣ１であり、便宜的に１台目のカメラとしている。１１２はカメラＣ１のレンズ、１１３はレンズ１１２のレンズ中心、１１４はカメラＣ１の撮像素子、１１５は撮像素子１１４の原点、１１６はボクセル１０１が結像すると計算される撮像素子１１４上の対応点、である。他のカメラＣ２〜Ｃｎも同様である。
【０１０８】
カメラＣ１の１１１では、ボクセル１０１はレンズ１１２のレンズ中心１１３を通り、撮像素子１１４上の点１１６で結像する。ただし、点１１６の座標は点１１５を原点とする座標系で表される。
【０１０９】
（ステップ２：注目ボクセルにおける物体表面がある可能性の算出）
ボクセル１０１をｖとし、このボクセル内に物体表面があるかどうかの可能性を示す値（＝信頼度）を、ボクセル１０１が結像している各カメラＣ１〜Ｃｎの撮像素子上の点、もしくは、その点の近傍の点の画素値の類似性で仮に決め、その後、その信頼度の信頼性を上げるため、後述するような信頼度の再計算による補正を行う。
【０１１０】
（ステップ２−１：注目ボクセルの周囲の点の決定）
複数のカメラの中から１つのカメラのペアを選び、下記に示すようなカメラ視線を引いて、その交点である注目ボクセルの近傍点を決定する。このカメラ視線の引き方について図３を用いて説明する。
【０１１１】
３０１は信頼度を計算し直そうとしている注目ボクセルｖ、３０２は物体表面の有無を調べたい３次元空間上の範囲であり、ボクセルで分割する３次元空間上の範囲、である。空間中にある物体を撮像するカメラが複数台あるが、ここではその中のカメラのペアの１組Ｃ１、Ｃ２のみを示している。３１１はそのうちの１つのカメラＣ１、３１２はカメラＣ１のレンズ、３１３はレンズ３１２のレンズ中心、３１４はカメラＣ１の撮像素子、３１５は撮像素子３１４の画素、である。他のカメラＣ２も同様である。３０３は注目ボクセルｖを通り、カメラＣ１、Ｃ２のレンズ中心を通る線に平行な線Ｌである。
【０１１２】
（ステップ２−１−１：エピポーラ平面の決定）
信頼度ｐの精度を上げたい注目ボクセルｖを決める。このときボクセルｖとＣ１、Ｃ２のカメラのそれぞれのカメラレンズの中心を含む平面上が決まる。この平面をエピポーラ平面という。
【０１１３】
（ステップ２−１−２：２つのカメラ中心に平行な線Ｌの決定）
エピポーラ平面上にあって、カメラＣ１、Ｃ２のそれぞれのレンズ中心を通る線に平行であり、注目ボクセルｖの中心を通る線Ｌを引く。
【０１１４】
（ステップ２−１−３：線Ｌ上の注目ボクセルの周囲の点の決定）
注目ボクセルｖの中心点（注目点、図３の三重丸）の周辺に、線Ｌ上のボクセルｖの中心点を起点として、一定の間隔で、線Ｌ上に点を取っていく（図３の二重丸）。なお、この点にはボクセル中心の点も含まれるものとする。また、注目点は注目ボクセルｖの中心点に限らず、注目ボクセルｖ内の任意の点であってもよい。間隔は、たとえば、ボクセルの辺の間隔でもよいが、これに限る必要はない。さらに、ここでは等間隔としたが、必ずしも等間隔である必要は無い。また、点を取る幾何学的な範囲は、特に限る必要はなく、ボクセル全体をカバーする範囲であっても良い。
【０１１５】
(ステップ２−１−４：線Ｌ上を通るカメラ視線引きと注目ボクセルの周囲の点の決定)
カメラＣ１、Ｃ２のレンズ中心から上記各点（線Ｌ上の注目ボクセルの周囲の点）を通る線（カメラ視線）を引く。図３は線Ｌがボクセルのある１つの辺と平行な場合についての図であり、一点鎖線が、等間隔に取った上記各点とＣ１、Ｃ２のレンズ中心とを結んだ、カメラ視線である。
【０１１６】
線Ｌ上の等間隔にとった各点、および、それらの点とＣ１、Ｃ２のレンズ中心とを結んだカメラ視線は、同じエピポーラ面上にあるので、カメラ視線同士はお互いに交わる。図中の白丸、二重丸、および、三重丸はそれらの交点を示している。
【０１１７】
（ステップ２−２：注目ボクセルの中心点およびカメラ視線の各交点における物体表面がある可能性の仮の算出）
注目ボクセルｖの中心点、および、その周りにあるカメラ視線の各交点において、物体表面があるかどうかの可能性を示す値（＝信頼度）を、各交点が結像しているカメラペアＣ１、Ｃ２の撮像素子上の点、もしくは、その点の近傍の点の画素の類似度で決める。たとえば、類似性を表す値とは、同一点が結像していると計算されている、カメラペアＣ１、Ｃ２のカメラの撮像素子上の対応点、および、その点の近傍の画素値の標準偏差に類する値である。
【０１１８】
以下、相違度ｄｉｓＲＣ１Ｃ２（ｉ，ｊ）を用いて類似性を計算する方法を述べる。ただし、（ｉ，ｊ）はカメラＣ１、Ｃ２からでている視線を区別する番号であり、（ｉ，ｊ）＝（ｉｖ，ｊｖ）は注目ボクセルｖの中心を通るカメラ視線であることを示す。相違度ｄｉｓＲＣ１Ｃ２（ｉ，ｊ）は、たとえば、以下のように計算する。
【０１１９】
【数１６】
2008250582.tif 000018
【０１２０】
ここで、ｍ（ｉ，ｊ），Ｃｋは注目ボクセルｖの中心点、および、その周りにあるカメラ視線の各交点を、カメラＣｋで撮像したときのカメラＣｋの撮像素子上の結像位置、ａはカメラの撮像素子上のｍ（ｉ，ｊ），Ｃｋの近傍を示すベクトルの集合であり、ｍ（ｉ，ｊ），Ｃｋを原点としたベクトルの集合、ｐはａの中の１つのベクトル、Ｔ（ｋ）は撮像素子上の画素の座標ｋにおけるテクスチャであり、通常ＲＧＢの色濃度を要素とする色ベクトル、バーＴ（ｉ，ｊ）（ｋ）はｍ（ｉ，ｊ），Ｃｋの近傍内にある点の座標ｐについての全カメラのテクスチャの平均、｜ｘ｜はｘの大きさを表し、たとえば、各要素の２乗和の平方根、ｍはテクスチャの分散（｜Ｔ−Ｔの平均｜で表される）に対するｄｉｓＲや信頼度の変化の仕方を変える値、である。
【０１２１】
テクスチャＴ（ｍ（ｉ，ｊ），Ｃｋ＋ｐ）の求め方の一例について図５を用いて説明する。ここで、５０１はカメラＣ１、Ｃ２のカメラ視線の交点、５０２はカメラＣ１のカメラ視線、５０３はカメラＣ１のカメラ視線と撮像素子の交点、５０４はカメラＣ１のカメラ視線の近傍の撮像素子上の画素群、５０５はカメラＣ１のカメラ視線と撮像素子の交点を中心とする、撮像素子の画素と同じ大きさの四角形、５０６はカメラＣ１のカメラ視線と撮像素子の交点を中心とする、撮像素子の画素と同じ大きさの四角形の近傍の、撮像素子の画素と同じ大きさの四角形、５１２はカメラＣ２のカメラ視線、５１３はカメラＣ２のカメラ視線と撮像素子の交点、５１４はカメラＣ２のカメラ視線の近傍の撮像素子上の画素群、５１５はカメラＣ２のカメラ視線と撮像素子の交点を中心とする、撮像素子の画素と同じ大きさの四角形、である。
【０１２２】
撮像素子上の画素の座標ｍ（ｉ，ｊ），Ｃｋは、撮像素子の画素の座標と一致するとは限らないので、ａが画素幅を単位とするベクトルの集合だとしても、ｍ（ｉ，ｊ），Ｃｋ＋ｐは撮像素子の画素の座標とは一致しない。この様子を図５（ａ）に示す。図５（ａ）では、カメラ視線の交点５０１を通る２本の視線がそれぞれカメラＣ１、Ｃ２の撮像素子上で、５０３と５１３で示す点で交わっており、その点がそれぞれのカメラの撮像素子上の画素の中心とはずれている様子を示している。
【０１２３】
図５（ｂ）はカメラＣ１の撮像素子を真上から見た図であり、５０５のカメラ視線との交点を含む撮像素子と同じ大きさの四角形と、その周りに、同じ大きさの四角形５０６を描いている。ｍ（ｉ，ｊ），Ｃｋは５０３の座標、ａは５０５、５０６のそれぞれの四角形の中心座標に対応する。ただし、これは図５（ｂ）に図示したように、ａが交点を中心とした９つの座標となる場合のものである。
【０１２４】
図５（ｄ）はカメラ視線と撮像素子の交点を中心とする、撮像素子の画素と同じ大きさの四角形と、撮像素子の画素との関係を示した図であり、ｍ（ｉ，ｊ），Ｃｋは、撮像素子の画素の座標、ｍｎ１（ｉ，ｊ），Ｃｋ、ｍｎ２（ｉ，ｊ），Ｃｋ、ｍｎ３（ｉ，ｊ），Ｃｋ、ｍｎ４（ｉ，ｊ），Ｃｋは、カメラ視線と撮像素子の交点を中心とする、撮像素子と同じ大きさの四角形と重なる、撮像素子の画素の中心の座標である。図中のｓ、ｔは重なる割合を示しており、０≦ｓ，ｔ≦１である。このとき、テクスチャＴ（ｍ（ｉ，ｊ），Ｃｋ）は以下のように、バイリニア法を使って計算することができる。
【０１２５】
【数１７】
2008250582.tif 000019
【０１２６】
ここではバイリニア法を示したが、その他、ニアレストネイバー法、バイキュービック法等の既存の補間方法を使用しても良い。ａ内でｐを変えた場合のテクスチャＴ（ｍ（ｉ，ｊ），Ｃｋ＋ｐ）も同様に計算できる。
【０１２７】
物体表面のある微小領域から発した光は、各カメラの撮像素子上の対応する領域ではほぼ同一のテクスチャを持つものと考えられるため、相違度ｄｉｓＲＣ１Ｃ２（ｉ，ｊ）は小さくなる。逆に相違度ｄｉｓＲＣ１Ｃ２（ｉ，ｊ）が小さいほど、それに対応するボクセルｖには物体表面がある可能性が高くなる。相違度ｄｉｓＲＣ１Ｃ２（ｉ，ｊ）からその逆の性質を持つ類似度ＲＣ１Ｃ２（ｉ，ｊ）を、たとえば、以下のように求める。
【０１２８】
【数１８】
2008250582.tif 000020
【０１２９】
ここで、σは相違度ｄｉｓＲＣ１Ｃ２（ｉ，ｊ）に対する類似度ＲＣ１Ｃ２（ｉ，ｊ）への影響を調整するパラメタであり、σが小さいほど、相違度のわずかの違いで類似度の大きさが変化する。
【０１３０】
この類似度が大きいボクセルほど、物体表面がそのボクセル中にある可能性が高い。この可能性を信頼度を呼ぶこととしｐＣ１Ｃ２ｄ（ｉ，ｊ）であらわすこととする。ｐＣ１Ｃ２ｄ（ｉ，ｊ）を以下のようにする。なお、このｐは（８．１０１）式等におけるベクトルのｐとは異なる。イメージデータである式においてはこれらは区別できるが、文章上では区別がつかないので、以下、文章上では「信頼度ｐ」と記載する。
【０１３１】
【数１９】
2008250582.tif 000021
【０１３２】
ボクセルの信頼度の精度を上げるため、下記に示すような処理により信頼度の再計算による補正を行う。
【０１３３】
（ステップ２−３：信頼度の補正）
各カメラ視線上においては、１点のみに物体の表面が存在するはずである。そこで、この拘束条件を用いて、各交点における信頼度の精度を上げるための信頼度の補正を行う。
【０１３４】
図３のカメラＣ１の視線上に物体表面がある場合、各交点における物体表面が存在する可能性はその物体表面に近い視線の交点のみで信頼度が大きく、そのほかの交点は小さくなることが望ましい。各交点での信頼度が上記のような望ましい状態になるように以下の処理を行う。
【０１３５】
図６は本処理を説明する図である。図３のカメラ視線と視線の交点を再現したものを図６（ａ）に示す。一点鎖線はカメラ視線、白丸と三重丸はカメラ視線の交点を示す。特に、三重丸は注目ボクセルｖの中心点を示す。図６（ｂ）はカメラ視線を便宜的に平行になるように幾何学変換したものである。図６（ａ）に示すカメラ視線は交わらないものがあるが、図６（ｂ）には黒丸で示した部分がその部分である。Ｃ１側、Ｃ２側とは、カメラが置かれている側を示している。
【０１３６】
（ステップ２−３−１：カメラ視線の交点の置き換え）
図６（ｂ）の白丸、および、三重丸で示すカメラ視線の交点には、図６（ａ）で示すもとの信頼度を割り当て、図６（ｂ）の黒丸で示す実際には交わらない点には、０を割り当てる。
【０１３７】
（ステップ２−３−２：カメラ視線の交点の信頼度の最適化）
図６（ｂ）のカメラ視線の交点の信頼度は、各行、各列で１つだけ大きくなることが望ましいので、たとえば、以下のようなエネルギー関数Ｅをつくり、これを最小化することを考える。
【０１３８】
【数２０】
2008250582.tif 000022
【０１３９】
ここで、信頼度ｐＣ１Ｃ２ｄ（ｉ，ｊ）は図６に表記のｉ行ｊ列の点の信頼度、ｎＣ１、ｎＣ２はそれぞれＣ１、Ｃ２側の線の数、Ａ、Ｂは適当な大きさの定数を示す。
【０１４０】
この式を、クロネッカーのデルタ関数を用いて、１＝（１−δｉｊ）＋δｉｊを第１、２項のそれぞれに代入し、以下のように多重一次形式に変換する。
【０１４１】
【数２１】
2008250582.tif 000023
【０１４２】
このエネルギー関数を用いて、下記の力学系を作る。
【０１４３】
【数２２】
2008250582.tif 000024
【０１４４】
この力学系を用いてエネルギー関数を最小化するには、たとえば、下記のようにＥｕｌｅｒ法を用いるとよい。
【０１４５】
まず、信頼度ｐＣ１Ｃ２ｄ（ｉ，ｊ）に（８．１０４）式で計算した信頼度で初期化し、次に、
【０１４６】
【数２３】
2008250582.tif 000025
【０１４７】
を計算し、次に、
【０１４８】
【数２４】
2008250582.tif 000026
【０１４９】
を計算する。ただし、Δは時間刻み幅の最大値であり、ユーザが決める定数である。ｗはベクトルｗ＝（ｗ１１，…，ｗＣ１Ｃ２）のノルムであり、たとえば、ベクトルの各エレメントの２乗和としてもよい。
【０１５０】
次に、信頼度ｐＣ１Ｃ２ｄ（ｉ，ｊ）を次のように更新する。
【０１５１】
【数２５】
2008250582.tif 000027
【０１５２】
終了条件としては、たとえば、以下の条件を用いることが考えられる。
【０１５３】
【数２６】
2008250582.tif 000028
【０１５４】
ここで、εはユーザが決めるしきい値である。
【０１５５】
上記のような終了条件を満たすまで、繰り返して（８．１０９）、（８．１１０）、（８．１１１）式を行って（８．１０６）式、または、（８．１０７）式で示されたエネルギー関数を小さくしていきながら信頼度を更新していき、終了条件を満たしたところで繰り返しを終了する。
【０１５６】
本実施例では、エネルギー関数の最小化を、Ｅｕｌｅｒ法を用いて行い、信頼度の補正を求める例を示したが、ここに示した手法に限られることなく、ニューラルネットワークを用いた組み合わせ最適化問題を解く手法等を用いても良い。
【０１５７】
（ステップ２−３−３：最適化された信頼度の注目ボクセルの信頼度への置き換え）
ステップ２−３−２を使って計算した、図６（ｂ）に示す三重丸の注目ボクセルｖの中心の信頼度を、新たに図６（ａ）に示す三重丸の注目ボクセルの信頼度とする。
【０１５８】
ステップ２−１で選んだカメラのペアを固定せず、複数のペアに対して同様の信頼度を求め、求められた信頼度を統合して、さらに信頼度の精度を上げることもできる。この場合には、以下のステップ２−３−４、２−３−５を追加する。
【０１５９】
（ステップ２−３−４：他のカメラペアにおける信頼度の最適化）
１つのボクセルに関して、複数のカメラペアについて、ステップ２−１〜２−３−３を行う。
【０１６０】
（ステップ２−３−５：複数カメラペアから算出された信頼度の統合）
１つのボクセルに関して、複数のカメラペアから得られた信頼度を統合する。統合には、例えば以下のようにする。
【０１６１】
【数２７】
2008250582.tif 000029
【０１６２】
ここで、信頼度ｐＣｒＣｓｄ（ｉｖ，ｊｖ）はカメラペアＣｒ、Ｃｓによって得られた、調べたいボクセルｖの信頼度であり、信頼度ｐｄはそれらを統合した信頼度である。
【０１６３】
信頼度は、次のように計算してもよい。
【０１６４】
【数２８】
2008250582.tif 000030
【０１６５】
Ｂｉａｓはユーザが決める定数である。Ｂｉａｓは、たとえば、１とすれば、信頼度ｐＣｒＣｓｄ（ｉｖ，ｊｖ）が小さいものはその影響を小さくすることができる。
【０１６６】
（ステップ３：全ボクセルについての信頼度の最適化と統合）
全てのボクセルについて、ステップ２を行う。
【０１６７】
以上のステップにより、全ボクセルの信頼度が計算される。
【０１６８】
この後、ステップ２〜３を繰り返し実行し、全ボクセルの信頼度の信頼性をさらに上げることもできる。この場合は、以下のステップ４を追加する。
【０１６９】
（ステップ４：信頼度の最計算の繰り返し実行）
ステップ２〜３を繰り返し実行する。
【０１７０】
（ステップ５：３次元形状データの出力）
最後に、再計算によって算出された全ボクセルの信頼度を３次元形状データとする。
【０１７１】
さらに、この全ボクセルの信頼度を用いて、表面が有るか無いかといった２値的なデータを求めることができ、この表面の有無を３次元形状データとすることもできる。この場合は、以下のステップ６を追加する。
【０１７２】
（ステップ６：表面の有無の判別とそのデータの出力）
このためには、たとえば、あらかじめ決められた閾値を用いて、その閾値以上の信頼度を持つボクセルには物体表面が存在し、それ以外のボクセルには物体表面が存在しないと判断し、その判断結果を３次元形状データとする。
【０１７３】
上記閾値は、上記のようにあらかじめ決めることもできるが、その他に、全ボクセルの信頼度の確率密度関数（信頼度の大きさを入力とし、その生起確率を出力とする関数）を用いて、最小２乗エラーを最小化する既存の２値化アルゴリスム（たとえば、大津の閾値選定法）や、平均誤識別率を最小にする既存の２値化アルゴリズム（たとえば、ｋｉｔｔｌｅｒの閾値選定法）を使って、閾値を決めてもよい。
【０１７４】
本実施の形態の効果としては、各ボクセルの信頼度を、カメラペアから得られる３次元的な整合性を持つように、カメラペアの視線の交点上の信頼度が幾何学的な矛盾が少なくなるように最適化を行って得ているため、各ボクセルの信頼度の精度が向上し、その結果、物体表面に同じようなテクスチャが存在した場合であっても、物体表面を正しく判定できるという利点がある。
【０１７５】
また、本実施の形態の効果としては、各ボクセルの信頼度がカメラペアから得られる３次元的な整合性を持つため、信頼度の信頼性が向上するという利点がある。
【０１７６】
また、本実施の形態の効果としては、複数のカメラペアの結果を統合するため、信頼度の信頼性が向上するという利点がある。
【０１７７】
以上、本発明者によってなされた発明を、前記実施形態に基づき具体的に説明したが、本発明は、前記実施形態に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは勿論である。
【図面の簡単な説明】
【０１７８】
【図１】３次元空間のボクセルによる分割と複数カメラの撮像位置との関係を示す図である。
【図２】従来の方法の問題点を示す図である。
【図３】カメラペアを使った類似度の３次元位置的な整合をとるための計算に用いるカメラ視線の交点の配置を示す図である。
【図４】視線の交点とその近傍のボクセルを示す図である。
【図５（ａ）】視線の交点とその交点を通る視線近傍の撮像素子上の画素（視線同士の交点と２つのカメラ内の撮像素子の関係）を示す図である。
【図５（ｂ）】視線の交点とその交点を通る視線近傍の撮像素子上の画素（カメラ視線と撮像素子の交点とその近傍の画素）を示す図である。
【図５（ｃ）】視線の交点とその交点を通る視線近傍の撮像素子上の画素（注目点を中心とする撮像素子画素と同じ大きさの四角形と撮像素子の画素との関係）を示す図である。
【図５（ｄ）】視線の交点とその交点を通る視線近傍の撮像素子上の画素（視線ｉ，ｊの交点を中心とする撮像素子画像と同じ大きさの四角形と撮像素子の画像との関係）を示す図である。
【図６】交点の配置と視線を平行にして交点を置き換えた様子を示す図である。
【図７】従来技術の代表的な全体処理のフローを示す図である。
【図８（ａ）】実施形態１による全体処理１のフロー（物体表面を確定した結果として得る場合）を示す図である。
【図８（ｂ）】実施形態１による全体処理１のフロー（物体表面を確率的な結果として得る場合）を示す図である。
【図９（ａ）】実施形態２による全体処理２のフロー（物体表面を確定した結果として得る場合）を示す図である。
【図９（ｂ）】実施形態２による全体処理２のフロー（物体表面を確率的な結果として得る場合）を示す図である。
【符号の説明】
【０１７９】
１０１はボクセルｖ、１１１はカメラ、１１２はレンズ、１１３はレンズ中心、１１４は撮像素子、１１５は撮像素子原点、１１６はボクセルの結像点、２０１は物体表面を含まないボクセルｖ１、２０２は物体表面を含むボクセルｖ２、２０３は物体表面上の小領域ａ、２０４は物体表面上の小領域ｂ、２１１はカメラ、２１２はレンズ、２１３はカメラ中心、２１４は撮像素子、２０３１はカメラＣ１における物体表面上小領域ａの結像領域ａＣ１、２０３２はカメラＣ２における物体表面上小領域ａの結像領域ａＣ２、２０３３はカメラＣ２における物体表面上小領域ｂの結像領域ｂＣ２、３０１は注目ボクセルｖ、３０２はボクセルで分割する範囲、３０３は注目ボクセルの中心を通ってカメラＣ１、Ｃ２のレンズ中心を通る線に平行な線、３１１はカメラ、３１２はレンズ、３１３はレンズ中心、３１４は撮像素子、３１５は撮像素子画素、４０１はカメラ視線の交点、４０２はカメラ視線の交点を中心とするボクセルと同じ大きさの立体、４０３はカメラ視線の交点の近傍のボクセル群、５０１はカメラＣ１、Ｃ２のカメラ視線の交点、５０２はカメラＣ１のカメラ視線、５０３はカメラＣ１のカメラ視線と撮像素子の交点、５０４はカメラＣ１のカメラ視線の近傍の撮像素子上の画素群、５０５はカメラＣ１のカメラ視線と撮像素子の交点を中心とする、撮像素子の画素と同じ大きさの四角形、５０６はカメラＣ１のカメラ視線と撮像素子の交点を中心とする、撮像素子の画素と同じ大きさの四角形の近傍の、撮像素子の画素と同じ大きさの四角形、５１２はカメラＣ２のカメラ視線、５１３はカメラＣ２のカメラ視線と撮像素子の交点、５１４はカメラＣ２のカメラ視線の近傍の撮像素子上の画素群、５１５はカメラＣ２のカメラ視線と撮像素子の交点を中心とする、撮像素子の画素と同じ大きさの四角形、である。
【図１】
2008250582.tif 000031
【図２】
2008250582.tif 000032
【図３】
2008250582.tif 000033
【図４】
2008250582.tif 000034
【図５（ａ）】
2008250582.tif 000035
【図５（ｂ）】
2008250582.tif 000036
【図５（ｃ）】
2008250582.tif 000037
【図５（ｄ）】
2008250582.tif 000038
【図６】
2008250582.tif 000039
【図７】
2008250582.tif 000040
【図８（ａ）】
2008250582.tif 000041
【図８（ｂ）】
2008250582.tif 000042
【図９（ａ）】
2008250582.tif 000043
【図９（ｂ）】
2008250582.tif 000044