被写体を多視点で撮影して得られた複数の画像から、該被写体の表面形状を示すパッチ群を作成する画像処理装置であって、前記画像のそれぞれにおける特徴点を抽出する特徴点抽出手段と、前記多視点の位置情報に基づき、前記画像のそれぞれにおける特徴点に対応する、前記被写体の表面形状を示す特徴点パッチを作成する特徴点パッチ作成手段と、前記多視点の位置情報と前記複数の画像、および前記特徴点パッチに基づき、前記被写体の表面形状を示す、該特徴点パッチ周辺に位置する追加パッチを作成するパッチ追加手段と、を有し、前記特徴点パッチおよび前記追加パッチは、三次元空間における中心座標、該中心座標におけるパッチの向きを表わす法線ベクトル、およびパッチの曲率によって表現され、前記中心座標および前記法線ベクトルに従い、前記特徴点パッチおよび前記追加パッチを前記三次元空間上に配置した前記パッチ群が、前記被写体の表面形状を示すことを特徴とする画像処理装置。前記特徴点パッチ作成手段は、前記画像のそれぞれにおいて、該画像間で互いに対応する前記特徴点を中心とした特徴点二次元パッチを作成する特徴点二次元パッチの作成手段と、前記画像のそれぞれにおける前記特徴点二次元パッチと前記多視点の位置情報に基づいて、前記特徴点パッチの中心座標を算出する中心座標算出手段と、前記中心座標と前記多視点の位置情報に基づいて、前記特徴点パッチの法線ベクトルの初期値を設定する法線ベクトル初期値設定手段と、前記特徴点パッチの曲率の初期値を設定する曲率初期値設定手段と、前記中心座標と前記法線ベクトル、および前記曲率が設定された前記特徴点パッチを前記複数の画像に射影して得られる射影パッチ間の類似度が所定の度合い以上となるように、前記法線ベクトルおよび前記曲率を最適化する特徴点パッチ最適化手段と、を有することを特徴とする請求項1に記載の画像処理装置。前記特徴点二次元パッチの作成手段は、前記複数の画像における1枚の画像上の基準特徴点に対応する、他の画像上のエピポーララインを算出するエピポーラライン算出手段と、前記基準特徴点を中心とする二次元パッチと、前記他の画像において前記エピポーラライン上で探索される特徴点を中心とする二次元パッチからなる特徴点二次元パッチ集合を設定する特徴点二次元パッチ収集手段と、を有し、前記特徴点パッチ作成手段は、前記中心座標算出手段、前記法線ベクトル初期値設定手段、前記曲率初期値設定手段、および特徴点パッチ最適化手段を前記特徴点二次元パッチ集合ごとに実行して、前記特徴点パッチを作成することを特徴とする請求項2に記載の画像処理装置。前記パッチ追加手段は、前記追加パッチの中心座標、法線ベクトル、および曲率のそれぞれの初期値として、前記特徴点パッチの中心座標、法線ベクトル、および曲率のそれぞれの値を設定する追加パッチの初期化手段と、前記初期値が設定された前記追加パッチを前記複数の画像に射影して得られる射影パッチ間の類似度に応じて、該追加パッチにおける中心座標、法線ベクトルおよび曲率を最適化する追加パッチ最適化手段、を有することを特徴とする請求項1乃至3のいずれか1項に記載の画像処理装置。前記パッチ追加手段はさらに、前記特徴点パッチ、および前記追加パッチ最適化手段で最適化された前記追加パッチを既存パッチとして保持する保持手段と、前記画像のそれぞれを等分割した複数のセルのうち、前記既存パッチが射影された射影パッチが存在するセルに隣接し、かつ該射影パッチが存在しないセルを、追加パッチ位置として特定する追加パッチ位置特定手段を有し、前記追加パッチの初期化手段は、前記追加パッチ位置であるセルに隣接したセルに存在する射影パッチに対応する、前記既存パッチの中心座標、法線ベクトル、および曲率を、前記追加パッチの初期値として設定することを特徴とする請求項4に記載の画像処理装置。前記パッチ追加手段は、前記画像のそれぞれにおける全てのセルに、前記既存パッチに対応する前記射影パッチが存在するまで、前記追加パッチの作成を繰り返すことを特徴とする請求項5に記載の画像処理装置。特徴点抽出手段、特徴点パッチ作成手段、およびパッチ追加手段を有し、被写体を多視点で撮影して得られた複数の画像から、該被写体の表面形状を示すパッチ群を作成する画像処理装置における画像処理方法であって、前記特徴点抽出手段が、前記画像のそれぞれにおける特徴点を抽出し、前記特徴点パッチ作成手段が、前記多視点の位置情報に基づき、前記画像のそれぞれにおける特徴点に対応する、前記被写体の表面形状を示す特徴点パッチを作成し、前記パッチ追加手段が、前記多視点の位置情報と前記複数の画像、および前記特徴点パッチに基づき、前記被写体の表面形状を示す、該特徴点パッチ周辺に位置する追加パッチを作成し、前記特徴点パッチおよび前記追加パッチは、三次元空間における中心座標、該中心座標におけるパッチの向きを表わす法線ベクトル、およびパッチの曲率によって表現され、前記中心座標および前記法線ベクトルに従い、前記特徴点パッチおよび前記追加パッチを前記三次元空間上に配置した前記パッチ群が、前記被写体の表面形状を示すことを特徴とする画像処理方法。コンピュータ装置で実行されることにより、該コンピュータ装置を請求項1乃至7のいずれか1項に記載の画像処理装置の各手段として機能させるためのプログラム。しかしながら、上記PMVSは、平面パッチを用いた三次元被写体の形状復元に関する技術である。三次元被写体の表面形状は連続であるから、三次元表面形状を推定する場合、PMVSでは平面パッチによる近似的な表現しかできないという問題がある。すなわちPMVSでは平面パッチを用いて三次元表面形状を推定しているために、三次元表面形状の曲面部分については推定精度が低下してしまう。本発明は上記問題を解決するためになされたものであり、被写体の表面形状を推定する際に、該表面形状の曲面部分についても高精度な推定を行う画像処理装置および画像処理方法を提供することを目的とする。上記目的を達成するための一手段として、本発明の画像処理装置は以下の構成を備える。すなわち、被写体を多視点で撮影して得られた複数の画像から、該被写体の表面形状を示すパッチ群を作成する画像処理装置であって、前記画像のそれぞれにおける特徴点を抽出する特徴点抽出手段と、前記多視点の位置情報に基づき、前記画像のそれぞれにおける特徴点に対応する、前記被写体の表面形状を示す特徴点パッチを作成する特徴点パッチ作成手段と、前記多視点の位置情報と前記複数の画像、および前記特徴点パッチに基づき、前記被写体の表面形状を示す、該特徴点パッチ周辺に位置する追加パッチを作成するパッチ追加手段と、を有し、前記特徴点パッチおよび前記追加パッチは、三次元空間における中心座標、該中心座標におけるパッチの向きを表わす法線ベクトル、およびパッチの曲率によって表現され、前記中心座標および前記法線ベクトルに従い、前記特徴点パッチおよび前記追加パッチを前記三次元空間上に配置した前記パッチ群が、前記被写体の表面形状を示すことを特徴とする。本発明によれば、被写体の表面形状を推定する際に、該表面形状の曲面部分についても高精度な推定を行うことが可能となる。以下、本発明の実施形態について、図面を参照して説明する。なお、以下の実施の形態は特許請求の範囲に関る本発明を限定するものではなく、また、本実施の形態で説明されている特徴の組み合わせの全てが本発明の解決手段に必須のものとは限らない。本発明においては、従来のPMVSと同様に、被写体を多視点で撮影して得られた複数の画像から、該被写体の表面形状を示すパッチ群を作成する例を示すが、パッチが曲面をなすことを特徴とする。具体的にはまず、画像のそれぞれにおける特徴点を抽出する特徴点抽出手段と、多視点の位置情報に基づき、画像のそれぞれにおける特徴点に対応する、被写体の表面形状を示す特徴点パッチを作成する特徴点パッチ作成手段を有する。そしてさらに、多視点の位置情報と複数の画像、および特徴点パッチに基づき、被写体の表面形状を示す、特徴点パッチ周辺に位置する追加パッチを作成するパッチ追加手段を有する。この特徴点パッチおよび追加パッチは、三次元空間における中心座標、該中心座標におけるパッチの向きを表わす法線ベクトル、およびパッチの曲率によって表現される。すなわち、中心座標および法線ベクトルに従い、特徴点パッチおよび追加パッチを三次元空間上に配置したパッチ群が、被写体の表面形状を示すことになる。<第1実施形態>●カメラシステム構成本実施形態では、本発明を適用可能な画像処理装置として、25個の撮像部を内蔵した所謂多眼カメラを想定している。図1は、本実施形態における多眼カメラの構成を示すブロック図であり、該多眼カメラが25個の撮像部100~124を有している。撮像部100~124のそれぞれは、被写体の光情報をセンサで受光してAD変換を施し、得られたデジタルデータをデータ転送経路であるバス138に出力する。撮像部100~124のそれぞれは図2に示す構成からなる。図2に示すように各撮像部は、ズームレンズ200、フォーカスレンズ201、ぶれ補正レンズ202、絞り203、シャッター204、光学ローパスフィルタ205、iRカットフィルタ206、カラーフィルタ207等を有する。そして、CMOSやCCDなどのセンサ208によって被写体の光量を検知し、AD変換部209で、該被写体の光量をデジタル値に変換する。図1に戻り、フラッシュ139は、被写体に光を照射する。デジタル信号処理部134は、撮像部100~124から出力されたデジタル値に対し、ホワイトバランス処理やガンマ処理、ノイズ低減処理等を施して、デジタル画像を生成する。圧縮伸張部135は、該生成されたデジタル画像をJPEGやMPEG等のファイルフォーマットに変換する。外部メモリ制御部136は、本実施形態の多眼カメラを、PCその他メディア137ハードディスク、メモリーカード、CFカード、SDカード、USBメモリ等に接続するためのインターフェースである。CPU128は、多眼カメラにおける各構成の処理全てに関わり、ROM126やRAM127に格納された命令を順次読み込んで解釈し、その結果に従って処理を実行する。またROM126とRAM127は、実行する処理に必要なプログラム、データ、作業領域等を、CPU128に提供する。撮像系制御部1000は、各撮像部100~124に対し、フォーカスを合わせる、シャッターを開く、絞りを調節する等、CPU128から指示された撮像系の制御を行う。操作部130は、主に装置外部に設けられたボタンやモードダイヤル等であり、ユーザによる操作入力を受ける。CG生成部131は、文字やグラフィック等を生成する。表示部133は例えば液晶ディスプレイであり、CG生成部131やデジタル信号処理部134、後述する画像処理部2000から受け取った撮影画像や文字等の表示を行う。また、タッチスクリーン機能を有していても良く、その場合は、該タッチにより入力されたユーザ指示を、操作部130の入力として扱うことも可能である。画像処理部2000は、撮像部100~124から得られたデジタル画像、或いはデジタル信号処理部134から出力されるデジタル画像群を利用して新たな画像を生成し、その結果をバス138へ出力する。なお、多眼カメラにおける構成要素としては上記以外にも存在するが、本願発明の主眼ではないため説明を省略する。●PMVSの原理とアルゴリズム以下、三次元被写体を撮影して得られる多視点画像を用いて被写体の三次元形状データを生成する、PMVSの基本的なアルゴリズムについて説明する。PMVSでは三次元空間上にパッチを配置して三次元形状データを表現する。一般的なPMVSでは、三次元パッチとして、三次元空間上にある小さい平面領域を用いており、以下ではこの三次元パッチとしての平面領域を平面パッチと称する。PMVSで用いられる平面パッチは、そのパッチサイズおよびパッチ間サイズが一定である。ここで図3に、平面パッチの例を示す。同図に示す平面パッチ301は、その中心座標がC、該中心座標Cにおけるパッチの向きを表わす法線ベクトルがNである。三次元空間における平面パッチの配置は、各パッチの中心座標Cと法線ベクトルNによって決定される。このように、三次元被写体の表面形状は、有限の小領域に分割して近似することができる。該小領域として、所謂ポリゴンパッチ等の平面パッチが用いられる。すなわちPMVSでは、平面パッチを用いて三次元被写体の表面を近似的に表現可能であることに注目し、平面パッチを用いて三次元被写体の形状復元を行う方法を実現した。次に、三次元被写体の表面である三次元形状に対応する三次元パッチと、該三次元被写体を撮影した多視点画像における二次元パッチとの関係について、図4を用いて簡単に説明する。同図は、多眼カメラを構成する各撮像部に対応するカメラ403、404、405のそれぞれが三次元被写体401を撮影することで、それぞれの撮影画像406、407、408が得られた例を示している。撮影画像406、407、408のそれぞれにおいて、三次元被写体401の表面に位置する三次元パッチ402に対応する二次元パッチ409、410、411が示されている。これら二次元パッチ409、410、411は同じ三次元パッチ402を撮影した結果であるため、それぞれの撮影画像内での位置が異なるものの、その画素値の構成は互いに類似している。ここで図5を用いて、一般的なPMVSの原理について説明する。三次元被写体に対するカメラの位置が分かれば、そのカメラの射影行列を算出することができるため、該射影行列を用いて、三次元被写体の射影画像を作成することができる。図5に示すカメラ403、404、405は、以下の式に示すカメラモデルを実現する射影カメラであるとする。図5は、図4と同様の系において、各カメラ403、404、405の撮影画像406407408上に、三次元被写体401上の三次元パッチ402に対応する二次元パッチ以下、射影パッチ409、410、411が存在する例を示している。なお、412、413は射影パッチ409に対するエピポーララインであり、すなわち、撮影画像406上の射影パッチ409に対応する、他の撮影画像407、408上の射影パッチ410、411は、それぞれエピポーラライン上で探索される。ここでは、複数の射影画像上の射影パッチ409、410、411の類似度評価を、以下の式に示すように、パッチ間における各画素の差分の2乗和を示すSSDを用いて行うとする。式においてはパッチサイズをm×mとし、pはカメラpの撮影画像上にある射影パッチにおいてi行j列目に位置する画素の画素値を示す。同様にqは、カメラqの撮影画像にある射影パッチにおいてi行j列目に位置する画素の画素値を示す。なお、類似度評価として、上記式とは異なる方法を適用することも可能である。射影パッチ409、410、411は同一の三次元パッチ402の射影結果であるから、どのような評価方法を用いたとしても、その類似度は極めて高いものと評価される。例えば上記式であれば、評価値SSDが極めて小さくなることで、高い類似度が示される。PMVSは、三次元パッチと、それを多眼カメラで撮影して得られる二次元パッチ射影パッチとにおける上記関係を利用して、三次元被写体の形状を推定する。以下、PMVSによる三次元被写体形状の推定アルゴリズムについて説明する。PMVSでは、多眼カメラで三次元被写体を撮影して得られた多視点の射影画像と、各カメラ位置の情報を入力として、主に以下の2つのステップを経ることによって、該三次元被写体の表面形状を表わす全ての三次元パッチを作成する。まず第1のステップで、射影画像においてその特徴点を中心とする二次元パッチに対応する三次元パッチを作成する、特徴点三次元パッチ作成処理を行う。そして第2のステップで、該作成された特徴点三次元パッチの周辺に位置する三次元パッチを作成する、三次元パッチ追加処理を行う。以下、上記第1のステップにおける特徴点三次元パッチの生成処理について、詳細に説明する。まず、入力された複数枚の射影画像のそれぞれにおいて特徴点を全て抽出し、該特徴点を中心とする特徴点二次元パッチを作成する。その後、エピポーララインを用いて、特徴点ごとに、特徴点二次元パッチの対応する特徴点三次元パッチの中心座標Cを計算する。ここで、第2のカメラの撮影画像におけるエピポーララインは、第1および第2のカメラの位置と第1のカメラの画像点を用いて、以下の式により算出される。エピポーララインの算出後、以下の式より特徴点三次元パッチの中心座標Cを算出する。尚、式におけるXが中心座標Cに相当する。そして最後に、全ての特徴点三次元パッチの法線ベクトルNを、最適化処理により求める。詳細にはまず、特徴点三次元パッチにおける中心座標Cと法線ベクトルNを、最適化のパラメータとする。そして、該パラメータによって表わされる特徴点三次元パッチを多眼カメラで撮影して得られる複数の射影画像上の二次元パッチを求める。そして、これら複数の射影パッチの類似度を算出し、その評価値が高い類似度を示すように、上記パラメータを変更して最適化を行う。具体的には、上記式に示すパッチ類似度の評価値SSDが所定の閾値より小さくなるように、三次元パッチの中心座標Cと法線ベクトルNを修正する。次に、上記第2のステップにおける三次元パッチの追加処理について、図6を用いて詳細に説明する。本処理においては、上記第1のステップで算出された特徴点三次元パッチに基づき、その周囲の三次元パッチを追加する。まず図6に示すように、各射影画像を均等な小領域に等分割する。なお、セル611の大きさは任意である。図6において、604が上記第1のステップで求められた特徴点三次元パッチであり、射影画像601、602、603における二次元の射影パッチ606、607、608が対応する。PMVSでは、三次元空間上において特徴点三次元パッチ604に隣接する三次元パッチ605が、射影画像601、602、603上の射影パッチ606、607、608が属するセルの隣のセルに射影されると仮定する。したがって、三次元パッチ605を作成するにあたり、まずその中心座標および法線ベクトルの初期値を、既に算出された特徴点三次元パッチ604の値を用いて算出する。その後、上記第1のステップと同様の最適化手法により、三次元パッチ605の中心座標と法線ベクトルを最適化する。このような三次元パッチの追加処理を、さらに隣接する三次元パッチについて順次行っていき、射影画像601、602、603上の全てのセルに、該三次元パッチに対応する射影パッチが存在するまで繰り返す。以上のようにPMVSによれば、多眼カメラによる射影画像群を入力し、その画像特徴点から三次元被写体の表面形状を示す三次元パッチを作成し、その周辺に三次元パッチを追加して順次拡張していく。これにより、三次元被写体の形状をより近似的に表現することができる。●本実施形態におけるパッチ定義上述したようにPMVSでは、三次元被写体の表面形状を示す三次元パッチとして平面パッチを用いている。このように平面パッチを用いるPMVSでは、三次元被写体の表面形状が曲面である場合には、該表面形状を近似的にしか算出できない。そこで本実施形態においては、三次元パッチとして曲面パッチを用いることで、三次元被写体の表面形状をより高精度に算出可能する。ここで、本実施形態において用いられる、曲面からなる三次元パッチについて詳細に説明する。図7は、本実施形態における曲面パッチの概要を示す図である。同図に示すように本実施形態の曲面パッチ701を定義するパラメータとしては、その中心座標Cと法線ベクトルNに加えて、パッチ曲面の曲率βが必要である。なお、曲面パッチのパッチサイズおよびパッチ間サイズは一定である。●本実施形態における三次元被写体形状の生成処理以下、本実施形態における三次元被写体の表面形状の生成処理について、詳細に説明する。本実施形態における画像処理部2000の基本動作としては、入力画像と、該入力画像を撮影したカメラに関するパラメータを、バス138を介して順次取得し、所定の画像処理が終了次第、該処理結果を出力する。以下、画像処理部2000において特に三次元被写体の表面形状を作成する処理について、図8のブロック図、および図10のフローチャートを用いて説明する。まずS1001で多視点画像取得部803が入力端子801を介して、多視点画像に対応する複数枚の撮影画像を取得する。そしてS1002でカメラ位置取得部804が、バス138を介して入力端子802より入力された、複数カメラの位置パラメータに基づき、該複数カメラの位置情報を取得する。次にS1003では特徴点抽出部805において、入力された各撮影画像から特徴点を抽出する。詳細には、複数枚の撮影画像に対し、DoGとHarrisオペレータによって全ての特徴点を抽出する。次にS1004では特徴点三次元パッチ作成部806において、特徴点三次元パッチを作成する。すなわち特徴点三次元パッチ作成部806では、特徴点抽出部805で抽出された特徴点と、カメラ位置取得部804で取得されたカメラ位置の情報を入力して、三次元被写体に対する全ての特徴点三次元パッチを作成する。この特徴点三次元パッチ生成処理の詳細については後述する。そしてS1005ではパッチ追加部807において、既に生成されている特徴点三次元パッチに基づいて、それに隣接する三次元パッチの作成、すなわち三次元パッチの追加を行う。すなわちパッチ追加部807が、特徴点三次元パッチとカメラ位置、および多視点画像に基づいて、追加する三次元パッチを算出する。この三次元パッチ追加処理の詳細については後述する。この三次元パッチ追加処理により、多視点画像内の全画素に対応する三次元パッチが生成される。最後にS1006で、以上のように生成された、特徴点三次元パッチおよび追加三次元パッチからなる全ての三次元パッチが、三次元被写体の表面形状の推定結果として出力端子808より出力される。●特徴点三次元パッチ作成処理以下、上記S1004における特徴点三次元パッチの作成処理について、詳細に説明する。図9に特徴点三次元パッチ作成部806の詳細ブロック構成を示す。特徴点三次元パッチ作成部806においては、多視点画像と特徴点、およびカメラ位置の情報を取得して、特徴点三次元パッチの中心座標と法線ベクトル、および曲率を最適化により算出する。図11に、特徴点三次元パッチ作成部806における特徴点三次元パッチ作成処理のフローチャートを示し、以下に詳細に説明する。まずS1101で多視点画像取得部904、特徴点取得部905、およびカメラ位置取得部906のそれぞれが、入力端子901、902、および903から、多視点画像、特徴点、およびカメラ位置の情報を取得する。するとS1002でエピポーラライン算出部907が、特徴点と各カメラの位置情報を用いて、多視点画像における1枚の画像上の基準特徴点に対応する、他の画像上のエピポーララインを算出する。ここで図12を用いて、特徴点とエピポーララインの関係を説明する。図12は、三次元被写体1201をカメラ403と404で撮影して得られた、それぞれの撮影画像1202、1203において、撮影画像1203上のエピポーララインを算出する例を示している。撮影画像1202、1203では、S1003の特徴点抽出処理によって得られた、それぞれの特徴点を中心とする特徴点二次元パッチが四角形で示されている。撮影画像1202の特徴点二次元パッチ1207と、カメラ403、404の位置情報から、撮影画像1203上のエピポーラライン1204が算出される。カメラ403によって撮影された特徴点二次元パッチ1207が対応する三次元被写体の特徴点は、カメラ404ではこのエピポーラライン1204上に存在するように撮影される。したがって、撮影画像1203においてエピポーラライン1204上で探索される特徴点二次元パッチ1210、1211が、撮影画像1202の特徴点二次元パッチ1207に対応するものである。同様に、撮影画像1202の特徴点二次元パッチ1208とカメラ403、404の位置情報から、撮影画像1203上のエピポーラライン1205が算出される。すなわち、エピポーラライン1205上にある特徴点二次元パッチ1212、1215が、特徴点二次元パッチ1208に対応する。また、特徴点二次元パッチ1209とカメラ403、404の位置情報から、撮影画像1203上のエピポーラライン1206が算出され、該ライン上にある特徴点二次元パッチ1213、1214が、特徴点二次元パッチ1209に対応する。次にS1103で特徴点二次元パッチ収集部908が、ある特徴点二次元パッチについて、それに対応するエピポーラライン上にある特徴点二次元パッチを収集して、特徴点二次元パッチの集合を生成する。ここで図13に、図12に示した特徴点二次元パッチ1207、1208、1209に対応する特徴点二次元パッチの収集例を示す。図12に示す撮影画像1203においては、特徴点二次元パッチ1207から算出された撮影画像1203上のエピポーラライン1204上に、特徴点二次元パッチ1210、1211が存在している。そこで特徴点二次元パッチ収集部908では、エピポーラライン1204に対応する、特徴点二次元パッチ1207と特徴点二次元パッチ1210、1211を収集して、図13に示すような特徴点二次元パッチの集合を生成する。同様に、エピポーラライン1205に対応する特徴点二次元パッチ1208と特徴点二次元パッチ1212、1215を収集して、図13に示すような特徴点二次元パッチの集合を生成する。また、エピポーラライン1206に対応する特徴点二次元パッチ1209と特徴点二次元パッチ1213、1214を収集して、図13に示すような特徴点二次元パッチの集合を生成する。S1103では以上のようにエピポーララインを利用することで、複数の撮影画像間で互いに対応する特徴点を中心とした特徴点二次元パッチの集合を生成する。なお、S1103では全ての撮影画像にある全ての特徴点に対して、特徴点二次元パッチ集合を作成する。以上のようにS1103にて生成された全ての特徴点二次元パッチ集合に対し、S1104~S1113までのループ処理を行う。このループ処理により、全ての特徴点二次元パッチに対応する特徴点三次元パッチが生成される。以下、このループ処理について説明する。まずS1105でパッチ中心座標設定部909が、ある特徴点二次元パッチ集合について、該集合内にあり、撮影したカメラが互いに異なる2つの特徴点二次元パッチを選択する。そして、該選択された特徴点二次元パッチと、それぞれが対応するカメラの位置情報を用いて、これら特徴点二次元パッチに応じた特徴点三次元パッチの中心座標を求める。例えば図13の集合に対し、特徴点二次元パッチ1207、1210とそれぞれに対応するカメラの位置情報を用いて、1つの特徴点三次元パッチの中心座標をステレオ計算により算出する。本実施形態では、特徴点二次元パッチ集合内において、エピポーララインの作成基準となった基準パッチを撮影したカメラを基準カメラと呼ぶ。図13に示す例であれば、特徴点二次元パッチ1207、1210、1211からなる特徴点二次元パッチ集合に対する基準カメラは、基準パッチ1207を撮影したカメラ403である。中心座標算出に関与する2台のカメラの位置情報のうち、1台は基準カメラを用いることが望ましい。次にS1106で法線ベクトル初期値設定部910が、S1105で設定した特徴点三次元パッチの中心座標と、基準カメラの位置座標を用いて、特徴点三次元パッチの法線ベクトルの初期値を設定する。なお、法線ベクトルの初期値は任意に設定可能である。次にS1107で曲率初期値設定部911が、特徴点三次元パッチの曲率の初期値を設定する。例えば、曲率の初期値として10を設定することにより、特徴点三次元パッチが平面パッチとして初期化され、以降の最適化ループ処理において該パッチが徐々に曲がっていくように補正される。以上、S1105~S1107の処理により、特徴点三次元パッチが初期化される。このように初期化された特徴点三次元パッチは、特徴点パッチ最適化部912において最適化される。以下、特徴点パッチ最適化部912におけるS1108~S1112の最適化ループ処理について説明する。まずS1108では、中心座標、法線ベクトルおよび曲率が設定された特徴点三次元パッチに対し、複数視点のカメラの射影行列を用いて二次元パッチ以下、射影パッチを作成し、さらに、該射影パッチ内の全ての画素値を求める。ここで図14を用いて、射影パッチにおける画素値の算出方法を説明する。図14は、三次元被写体上にある5×5の三次元パッチが、i番目のカメラで撮影した画像1401に射影された射影パッチ1402の例を示している。同様に図14は、5×5の三次元パッチが、j番目のカメラで撮影した画像1408に射影された射影パッチ1409の例を示している。本実施形態では、各射影パッチ内の画素値を、その元画像の画素値を用いたバイリニア補間により求める。例えば、射影パッチ1402、1409の右上角にある画素1407、1410の値を求めるために、元画像1401、1408における周辺画素を利用する。すなわち図14において、射影パッチ1402の画素1403の値は、元画像1401の画素1404、1405、1406および1407を用いたバイリニア補間により求められる。同様に図14において、射影パッチ1409の画素1410の値は、元画像1408の画素1411、1412、1413および1414を用いて求められる。次にS1109では、S1108で作成された射影パッチ間における類似度の評価値を算出する。具体的には、基準カメラの射影パッチと非基準カメラの射影パッチ間における類似度の評価値を全ての非基準カメラについて取得し、該評価値の和を類似度評価値とする。本実施形態では類似度評価値として、射影パッチ間の各画素値の差分の2乗和を示すSSDを用いるとするが、もちろん他の類似度評価方法も適用可能である。そしてS1110で、S1109で算出した類似度評価値SSDを所定の閾値と比較する。図5を用いて説明したように、1つの特徴点三次元パッチに基づく各カメラの射影パッチの類似度は極めて高くなるはずである。したがって、類似度評価値SSDが小さいほど、当該特徴点三次元パッチに対応する射影パッチが類似している、すなわち現在設定されている特徴点三次元パッチの法線ベクトルと曲率が適正であると判断される。したがって、S1110で類似度評価値SSDが閾値より小さければ、射影パッチ間の類似度が所定の度合い以上であるとみなし、特徴点三次元パッチについて現在設定されている法線ベクトルと曲率をそのまま出力する。一方、類似度評価値SSDが閾値以上であれば、特徴点三次元パッチについて現在設定されているの法線ベクトルと曲率は未だ適正な範囲内でないと判断される。したがってこの場合、S1111で曲率を所定量修正し、さらにS1112で法線ベクトルを所定量修正した後、S1108に戻って射影パッチを再生成し、再度評価を行う。なお、S1111、S1112における曲率および法線ベクトルの修正量は任意である。ここで、S1111における特徴点三次元パッチの曲率の補正について、図17を用いて説明する。同図に示すように特徴点三次元パッチ1702の曲率は、該特徴点三次元パッチ1702を法線方向に射影した平面パッチ1701を用いて定義される。本実施形態では特徴点三次元パッチ1702がその中心から両端へ均等に曲がり、その際に描く曲線は放物線形状を呈し、該放物線の頂点0が特徴点三次元パッチ1702の中心点であるとする。すると、特徴点三次元パッチ1702におけるA点とB点の座標は、平面パッチ1701と特徴点三次元パッチ1702間の距離dと、平面パッチ1701のパッチサイズに基づいて算出される。このO点およびA点とB点の3点を通る放物線が特徴点三次元パッチとなり、この放物線は以下の式によって表わされる。式において、Lは平面パッチ1701のパッチサイズの半分であり、曲率を決定するパラメータはdである。すなわち、特徴点三次元パッチ1702の曲率の修正を行う際には、距離パラメータΔdを修正すれば良い。そしてS1113で、上記S1103にて生成された全ての特徴点二次元パッチ集合に対するループ処理が終了するとすなわち、全ての特徴点二次元パッチ集合に対する特徴点三次元パッチの生成が完了する。そしてS1114で、該生成された全ての特徴点三次元パッチについて、その中心座標と法線ベクトル、および曲率を出力する。●三次元パッチ追加処理以下、上記S1005における三次元パッチの追加処理について、詳細に説明する。図15に、パッチ追加部807の詳細ブロック構成を示す。パッチ追加部807における処理の概要としては、多視点画像、カメラ位置と特徴点三次元パッチを取得し、特徴点三次元パッチを中心として、全ての撮影画像が三次元パッチの射影パッチで埋まるように、三次元パッチを追加する。図16に、パッチ追加部807における三次元パッチ追加処理のフローチャートを示し、以下に詳細に説明する。まずS1601で多視点画像取得部1504、カメラ位置取得部1505、および特徴点三次元パッチ取得部1506のそれぞれが、入力端子1501、1502、および1503から、多視点画像、カメラ位置情報、および特徴点三次元パッチを取得する。そして、追加パッチ位置特定部1507において追加パッチ位置を特定するための前処理として、まずS1602で、入力された多視点画像における全ての撮影画像を任意サイズのセルに分割する。次にS1603で、入力された特徴点三次元パッチを既存パッチバッファに格納する。ここで既存パッチバッファは、既に作成された三次元パッチを保持するバッファであり、以下の処理によって新たな三次元パッチが作成されるたびに更新される。以下、既存パッチバッファに保持された三次元パッチを既存三次元パッチと称する。この既存三次元パッチの射影パッチが撮影画像の全セルを埋めたか否かによって、追加処理の終了が判断される。そしてS1604~S1616のループ処理により、現在の既存パッチバッファに保持された全ての既存三次元パッチに対する、それぞれを中心としたパッチ追加処理を行う。まずS1605~S1606で追加パッチ位置特定部1507において、三次元パッチの追加位置を特定する。すなわち、まずS1605で、既存パッチバッファに現在保持されている全ての既存三次元パッチについて、全ての撮影画像に対する射影パッチを生成する。上記図6に示したように、特徴点三次元パッチすなわち既存三次元パッチの射影パッチは、複数の撮影画像上に分布している。そしてS1606で、ある既存三次元パッチの射影パッチが存在するセルに隣接したセルに、他の既存三次元パッチの射影パッチが存在するか否かを判定することで、三次元パッチの追加位置を特定する。すなわち、隣接セルに射影パッチが存在しなければ、該隣接セルに射影パッチが来るように、三次元パッチの追加位置を特定する。例えば図6に示す各射影画像において、既存三次元パッチ604の射影パッチ606、607、608が属するセルの右隣のセルには射影パッチが存在しない。したがってこの場合、射影パッチ606、607、608が属するセルの右隣のセルに射影パッチが来るような位置に、三次元パッチを追加する。このように本実施形態では、例えば射影パッチ606と射影パッチ609が隣接していれば、既存三次元パッチ604と追加したい三次元パッチ605も隣接しているものと仮定する。したがって本実施形態では該仮定に基づき、追加三次元パッチを以下のS1607~S1615の処理によって生成する。すなわち、既存三次元パッチの中心座標、法線ベクトルと曲率を用いて、追加三次元パッチの中心座標、法線ベクトルと曲率の初期値を算出する。まずS1607でパッチ中心座標設定部1508が、追加三次元パッチの中心座標を初期化する。ここで、既存三次元パッチと追加三次元パッチは同一平面で互いに隣接するパッチであると仮定し、追加三次元パッチの中心座標の初期値として、該追加三次元パッチに隣接する既存三次元パッチの中心座標を設定する。同様にS1608で法線ベクトル初期値設定部1509が、追加三次元パッチの法線ベクトルを、該追加三次元パッチに隣接する既存三次元パッチの法線ベクトルで初期化する。そしてS1609で曲率初期値設定部1510が、追加三次元パッチの曲率を、該追加三次元パッチに隣接する既存三次元パッチの曲率で初期化する。上記S1607~S1609で設定した各初期値は近似的に求めた値であるため、最適化する必要がある。そこでS1610~S1615で追加パッチ最適化部1511において、追加三次元パッチの最適化処理を行う。ここで、S1610~S1612、およびS1614、S1615の各処理は、上記図11のS1108~S1110、およびS1111、S1112と同様であるため、詳細な説明を省略する。すなわちここでは、追加三次元パッチの射影パッチ間における類似度に応じて、該追加パッチの曲率および法線ベクトルの最適化を行う。本実施形態では、射影パッチ間の類似度が十分でないと判定された場合に、追加三次元パッチの曲率、法線ベクトルに加えて、その中心座標も最適化する。すなわち、S1613で追加三次元パッチの中心座標を補正した後、S1614、S1615で曲率および法線ベクトルを任意量補正する。なお、中心座標の補正量も任意である。以上説明したS1604~S1616の最適化ループ処理が終了するとすなわち、既存パッチバッファに保持された全ての既存三次元パッチに隣接する追加三次元パッチの作成が終了する。その後S1617で、作成された追加三次元パッチを既存パッチバッファに追加する。続いてS1618において、全ての撮影画像上の全てのセルに射影パッチが存在すると判定されるまで、上記S1604~S1617までの処理を繰り返す。そしてS1618で全てのセルに射影パッチが存在すると判定されるとS1619に進み、既存パッチバッファに保持された全ての三次元パッチを出力する。すなわち、全ての特徴点三次元パッチと追加三次元パッチについて、その中心座標、法線ベクトルおよび曲率を、出力端子913を介して出力する。以上説明したように本実施形態によれば、三次元被写体の表面形状を表す三次元パッチ群として、いずれも曲面パッチである特徴点三次元パッチおよび追加三次元パッチを得ることができる。したがって、三次元表面形状の復元を平面パッチを用いて行う場合に比べて、特に該表面形状の曲面部分についての推定精度が向上する。<その他の実施形態>また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェアプログラムを、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータまたはCPUやMPU等がプログラムを読み出して実行する処理である。