(57)【特許請求の範囲】
【請求項１】
３次元形状から抽出した特徴点のデータと撮影された３次元形状の外表面の２次元画像データとを基にコンピュータ画面上に３次元形状を復元生成する３次元形状生成装置であって、
撮影方向と当該撮影方向から可視であり撮影画像中に写り込んだ特徴点との関係を可視情報として、
撮影方向と当該撮影方向から見た３次元形状の外縁を表わす投影影絵の範囲をマスク画像情報として、
前記特徴点情報と撮影方向情報と可視情報とマスク画像情報とを入力する入力部と、
前記特徴点情報に基づいて仮想空間上に特徴点を展開配置する特徴点展開処理部と、
基本小立体を構成単位として仮想空間を埋める集合体を想定し、前記撮影方向情報とマスク情報に基づいて、撮影方向から見て前記マスク画像情報の示す外周縁の外にある基本小立体を前記集合体から削除する３次元マスク処理部と、
前記撮影方向情報と可視情報に基づいて、撮影方向から可視となる特徴点を覆い隠している基本小立体を削除する遮視基本小立体削除部と、
前記遮視基本小立体削除部により削除処理済みの残存した基本小立体の集合体を３次元形状として出力表示する３次元形状出力部とを備えたことを特徴とする３次元形状生成装置。
【請求項２】
前記遮視基本小立体削除部による基本小立体を削除する処理において、特徴点と当該特徴点が可視である撮影方向とを結ぶ線分を引き、前記線分が前記基本小立体集合体と交差する場合には当該交差する基本小立体を削除し、交差しない面のみを残して前記遮視基本小立体削除部の出力とする請求項１に記載の３次元形状生成装置。
【請求項３】
前記基本小立体として、３次元特徴点のドロネー図から形成される４面体を用いることを特徴とする請求項１または２に記載の３次元形状生成装置。
【請求項４】
３次元形状から抽出した特徴点のデータと撮影された３次元形状の外表面の２次元画像データとを基にコンピュータ画面上に３次元形状を復元生成する３次元形状生成装置を実現する処理プログラムを記録したコンピュータ読み取り可能な記録媒体であって、
前記処理プログラムは、撮影方向と当該撮影方向から可視であり撮影画像中に写り込んだ特徴点との関係を可視情報として、撮影方向と当該撮影方向から見た３次元形状の外縁を表わす投影影絵の範囲をマスク画像情報として、コンピュータに、
前記特徴点情報と撮影方向情報と可視情報とマスク画像情報とを入力する処理ステップと、
前記特徴点情報に基づいて仮想空間上に特徴点を展開配置する特徴点展開処理ステップと、
基本小立体を構成単位として仮想空間を埋める集合体を想定し、前記撮影方向情報とマスク情報に基づいて、撮影方向から見て前記マスク画像情報の示す外周縁の外にある基本小立体を前記集合体から削除する３次元マスク処理ステップと、
前記撮影方向情報と可視情報に基づいて、撮影方向から可視となる特徴点を覆い隠している基本小立体を削除する遮視基本小立体削除処理ステップと、
前記遮視基本小立体削除部により削除処理済みの残存した基本小立体の集合体を３次元形状として出力表示する３次元形状出力処理ステップとを実行させることを特徴とする記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、３次元形状生成装置に関する。特に、複数の方向から撮影して得られるカメラ撮影画像に基づいて当該撮影対象をディスプレイ上の３次元形状として生成する装置に関する。
【０００２】
【従来の技術】
近年のコンピュータシステムの高性能化、マルチメディア処理技術の発達により、パーソナルコンピュータ等においても高度な３次元コンピュータグラフィックス（以下、ＣＧと略記する）が処理できる環境が整いつつある。３次元ＣＧ技術を利用した電子ショッピング、電子博物館など、物体をコンピュータ画面上に現実感をもって再現するシステムの構築において、実在する物体を如何に効率良くコンピュータ上の３次元画像データとして取り込むかが重要な課題となっている。
【０００３】
３次元物体をコンピュータに取り込むためのデータ生成の手法として最も簡単な方式は、３次元物体を幾つかの方向から撮影した２次元画像データを生成して用意しておき、再現時には利用者の方向に応じて最も近い方向から撮影した２次元画像をディスプレイに表示する方式である。しかし、この方式によれば、撮影した方向以外からの方向による３次元物体の画像を表示できないという問題があった。また、あくまでも２次元画像であるので、３次元ＣＧデータとして生成されている他の３次元物体との画像合成が実行しにくいという問題もあった。そこで、取り込んだ３次元物体を任意の方向から表示可能とするためには、物体を複数の方向から撮影した２次元画像データに基づいて物体の３次元形状を３次元画像データとして復元し、任意方向に対する３次元形状の投影画像を生成して表示することが必要となる。
【０００４】
ここで、撮影した２次元画像データから物体の３次元形状を３次元画像データとして復元する方式として幾つか提案されているが、代表的な方式として、特徴点に基づく方式がある。この方式による３次元画像データの生成処理は、図１４のフローチャートに示すように以下の処理ステップから構成される。また、図１５に従来の特徴点に基づく３次元画像データ生成の概念を示す。
【０００５】
まず、撮影画像を読み込み、特徴点を抽出する（ステップＳ１４０１）。この特徴点の抽出にあたり、撮影した２次元画像の中で明度が変化している箇所を選んで特徴点とすることが好ましい。この抽出処理は、明度の変化を調べることによりコンピュータで自動的に特徴点を抽出することにより実行しても良く、人手で指定することにより実行しても良い。この様子を図１５に示す。この例では、図１５（ａ）の撮影画像から図１５（ｂ）に示した４つの特徴点が抽出された。
【０００６】
次に、撮影画像間で、抽出した特徴点同士の対応付けを行う（ステップＳ１４０２）。この特徴点同士の対応付けにあたっては、撮影画像の撮影位置関係、画像の類似性、抽出特徴点間の位置関係を利用すれば、コンピュータで自動的に処理することが可能である。また、人手で指定することにより実行しても良い。図１５の例では、図１５（ｃ）のように各特徴点１〜特徴点４の対応付けが行われた。
【０００７】
次に、特徴点の対応関係からステレオ計測の原理により各特徴点の３次元座標を求める（ステップＳ１４０３）。この処理により、各特徴点は３次元空間内の一点として表現される。
【０００８】
次に、３次元空間内に表現された各特徴点間に対して面を割り当て、多面体を形成する（ステップＳ１４０４）。ここで、面を形成する特徴点の組み合わせは任意の組み合わせではなく、再生物体の外表面を形成するように選択されなければならない。図１５の例では、図１５（ｄ）のように面が割り当てられ、４面体が形成された。
【０００９】
次に、各面のテクスチャを生成する（ステップＳ１４０５）。テクスチャの生成にあたっては、撮影画像の模様を参照すれば各面に貼るテクスチャが計算できる。
【００１０】
以上のステップＳ１４０１〜ステップＳ１４０５に示した処理により、撮影画像から３次元画像データが生成できる。図１５の例では、図１５（ｅ）に示すように元の３次元物体の３次元画像データが生成できる。
【００１１】
一方、生成した３次元画像データを用いた３次元物体のコンピュータ画面上での再生処理は、図１６のフローチャートに示すように以下の処理ステップから構成される。
【００１２】
まず、利用者の物体に対する位置を指定する。つまり、物体に対する方向と距離が指定される（ステップＳ１６０１）。
【００１３】
次に、指定された物体に対する視点の方向と距離に応じた投影面に対する各特徴点の投影面上の位置を計算し、投影画像を得る（ステップＳ１６０２）。この段階では、まだテクスチャマッピング処理は行われていない。
【００１４】
次に、投影画像の各面に対してテクスチャを貼り込む（ステップＳ１６０３）。ここで、テクスチャの貼り込みにあたっては、投影された各面の大きさ、形、方向を計算してテクスチャを調整して貼り込む。
【００１５】
最後に、ライティング、トレーシング、シェーディングなど必要な特殊効果処理を施した後、コンピュータ画面上への表示が行われる（ステップＳ１６０４）。
【００１６】
以上のステップＳ１６０１〜ステップＳ１６０４に示した処理により、生成した３次元画像データを用いてコンピュータ画面上へ３次元物体の任意の方向における画像が表示できる。
【００１７】
【発明が解決しようとする課題】
従来の３次元形状生成処理ステップのうち、図１４のステップＳ１４０４として示した特徴点対応に基づく３次元形状復元における面の当てはめ処理として以下の方法が知られ、それぞれ以下の問題があった。
【００１８】
従来の面の当てはめ処理の第１の方法は、３次元特徴点を既知形状面に投影する方法がある。この処理方法は、３次元特徴点を球面や円筒面などの形状が既知である可展面に投影し、あらかじめ定めた頂点の接続関係を利用するものである。この処理方法は、簡便な処理方法であり有効な技術と言える。
【００１９】
しかし、この第１の処理方法は、３次元形状が既知であり、可展面への投影中心の決定にあたり、当該中心点から可展面への投影処理において投影が重なる面が存在しないように決定する必要がある。つまり、未知形状で窪みがあるような複雑な３次元形状である場合には利用できないという問題がある。
【００２０】
従来の面の当てはめ処理の第２の処理方法は、明度情報を用いて面の法線方向を定め、当該方向を法線とするように面を当てはめる処理方法である。撮影時の光源方向からの照射により、３次元形状面上の特徴点における明度とその面の法線方向には相関があるので、明度情報を利用して各３次元特徴点での面の法線方向を定めて面の当てはめ処理を行なうものである。
【００２１】
しかし、この第２の処理方法は、３次元形状が比較的複雑ではなく、突起点や窪みなどのない場合にしか適用できない。つまり、突起点や窪み部分の周辺において明度情報は急激に変化するので法線方向が決定できない場合や誤った法線方向の決定がなされる場合があり、当該処理方法を用いることができないという問題がある。
【００２２】
従来の面当てはめ処理の第３の処理方法は、抽出された特徴点をディスプレイ上に表示し、それら特徴点を基に、操作者が人手により特徴点を指定して３次元形状面を決定する方法である。操作者による指定が適切であれば間違いなく３次元形状を復元・生成することができる。
【００２３】
しかし、この第３の処理方法は、複雑な形状で面数、特徴点数が大きくなると操作者による指定が煩雑となり、また処理時間が非常に長くなり、現実的な処理方法とはならない場合がある。また、操作者が復元すべき３次元形状を知らない場合には特徴点のみでは指定できない場合があり、当該場合には撮影画像を見比べつつ指定することとなり操作が煩雑となる問題がある。
【００２４】
本発明は、上記従来の３次元形状生成処理方式の問題点に鑑み、特徴点が多く、複雑な形状であっても、特徴点対応に基づいて３次元形状の復元処理において高精度かつ高効率に実行できる３次元形状生成装置を提供することを目的とする。
【００２５】
【課題を解決するための手段】
本発明の第１の３次元形状生成装置は、撮影方向と当該撮影方向から可視であり撮影画像中に写り込んだ特徴点との関係を可視情報として、前記特徴点情報と撮影方向情報と可視情報とを入力する入力部と、前記特徴点情報に基づいて仮想空間上に特徴点を展開配置する特徴点展開処理部と、前記撮影方向情報と可視情報に基づいて、撮影方向から可視となっている特徴点間にそれら特徴点が可視となるように面を当てはめる可視面当てはめ部と、前記可視面当てはめ部により当てはめられた面を外形面とする３次元形状を出力表示する３次元形状出力部とを備えたことを特徴とする。
【００２６】
上記構成により、特徴点数が多く、凹凸のある複雑な３次元形状であっても、特徴点間に面を当てはめる処理において、特徴点と撮影視点との可視情報を満たす面の当てはめ処理を簡便かつ適切に実行することができる。ここで可視情報を満たす面の当てはめ処理としては、撮影方向から可視である特徴点間に当てはめた面に対して、特徴点と当該特徴点が可視である撮影方向とを結ぶ線分を引き、前記線分が前記当てはめた面と交差する場合には当該交差する面を削除し、交差しない面のみを残して可視面当てはめ部の出力とする。また、当てはめる面を特徴点のドロネー図の面とするとアルゴリズムが簡便で高速処理が可能となる。ここでいうドロネー図とは、凸包をある４面体の集合に分割したものである。
【００２７】
本発明の第２の３次元形状生成装置は、撮影方向と当該撮影方向から可視であり撮影画像中に写り込んだ特徴点との関係を可視情報として、前記特徴点情報と撮影方向情報と可視情報とを入力する入力部と、前記特徴点情報に基づいて仮想空間上に特徴点を展開配置する特徴点展開処理部と、前記特徴点を用いて凸包立体を形成する凸包立体形成部と、前記撮影方向情報と可視情報に基づいて、撮影方向から可視となる特徴点を覆い隠している立体部分を削除する遮視立体部分削除部と、前記遮視立体部分削除部により削除処理済みの残存した立体を３次元形状として出力表示する３次元形状出力部とを備えたことを特徴とする。
【００２８】
上記構成により、特徴点を基に３次元形状の復元処理において、特徴点の凸包を用いてまず簡便・高速に３次元形状の大枠を形成しておき、続いて、可視情報を基にして特徴点を覆い隠している立体部分を削除することにより凹部分など詳細な形状の復元処理を実行でき、高速かつ精度の高い３次元形状の生成ができる。
【００２９】
本発明の第３の３次元形状生成装置は、撮影方向と当該撮影方向から見た３次元形状の外縁を表わす投影影絵の範囲をマスク画像情報として、前記特徴点情報と撮影方向情報とマスク画像情報とを入力する入力部と、基本小立体を構成単位として仮想空間を埋める集合体を想定し、前記撮影方向情報とマスク情報に基づいて、撮影方向から見て前記マスク画像情報の示す外周縁の外にある基本小立体を前記集合体から削除する３次元マスク処理部と、前記３次元マスク処理部により削除処理済みの残存した基本小立体の集合体を３次元形状として出力表示する３次元形状出力部とを備えたことを特徴とする。
【００３０】
上記構成により、特徴点を基に３次元形状の復元処理において、マスク画像情報を用いて基本小立体の集合体により３次元形状の外形状の大枠を形成しておき、続いて、可視情報を基にして特徴点を覆い隠している立体部分を削除することにより凹部分など詳細な形状の復元処理を実行でき、高速かつ精度の高い３次元形状の生成ができる。ここで基本小立体の削除処理としては、特徴点と当該特徴点が可視である撮影方向とを結ぶ線分を引き、前記線分が前記基本小立体集合体と交差する場合には当該交差する基本小立体を削除することが好ましく、また、基本小立体は３次元特徴点のドロネー図の４面体を用いることが好ましい。
【００３１】
本発明の第１の３次元形状生成装置を実現する処理プログラムを記録したコンピュータ読み取り可能な記録媒体は、撮影方向と当該撮影方向から可視であり撮影画像中に写り込んだ特徴点との関係を可視情報として、前記特徴点情報と撮影方向情報と可視情報とを入力する処理ステップと、前記特徴点情報に基づいて仮想空間上に特徴点を展開配置する特徴点展開処理ステップと、前記撮影方向情報と可視情報に基づいて、撮影方向から可視となっている特徴点間にそれら特徴点が可視となるように面を当てはめる可視面当てはめ処理ステップと、前記可視面当てはめ処理ステップにより当てはめられた面を外形面とする３次元形状を出力表示する３次元形状出力表示処理ステップとを備えた３次元形状を生成する処理プログラムを記録したことを特徴とする。
【００３２】
本発明の第２の３次元形状生成装置を実現する処理プログラムを記録したコンピュータ読み取り可能な記録媒体は、撮影方向と当該撮影方向から見た３次元形状の外縁を表わす投影影絵の範囲をマスク画像情報として、前記特徴点情報と撮影方向情報とマスク画像情報とを入力する処理ステップと、基本小立体を構成単位として仮想空間を埋める集合体を想定し、前記撮影方向情報とマスク情報に基づいて、撮影方向から見て前記マスク画像情報の示す外周縁の外にある基本小立体を前記集合体から削除する３次元マスク処理ステップと、前記３次元マスク処理ステップにより削除処理済みの残存した基本小立体の集合体を３次元形状として出力表示する３次元形状出力処理ステップとを備えた３次元形状を生成する処理プログラムを記録したことを特徴とする。
【００３３】
上記処理プログラムをコンピュータに読み取らせることより、コンピュータを利用して、３次元形状の特徴点と撮影視点との可視情報を用いて高速かつ復元精度の良い３次元形状生成装置を構成することができる。
【００３４】
【発明の実施の形態】
本発明の３次元形状生成装置の実施形態について図面を参照しつつ説明する。
【００３５】
まず始めに、本発明の３次元形状生成装置の可視情報に基づく３次元形状生成処理の基本的な考え方を以下に説明する。
【００３６】
本発明の３次元形状生成装置は、下記に示すように得られている３次元形状の３次元特徴点を基に簡便に初期形状を形成し、可視情報を満足しない初期形状の不用部分を削除して３次元形状の精度を向上してゆく装置である。
【００３７】
まず、可視情報について述べる。一般的に、撮影画像から抽出した特徴点を基に３次元形状をディスプレイ上で再現する処理において、特徴点抽出の誤差や特徴点対応付けの誤りの影響を減少させるため多視点からの２次元撮影画像データを相互参照しつつ３次元特徴点を決める場合が多い。本発明の３次元形状生成装置においても多視点からの２次元撮影画像データそれぞれから抽出した２次元特徴点および当該２次元特徴点の対応付けにより得た３次元特徴点を用いる。いま、多視点間で特徴点の対応づけが実行され、３次元特徴点が得られたとする。ある視点Ａからの撮影画像中にある３次元特徴点１に対応する２次元特徴点が存在しているとすると、この視点Ａから３次元形状を見た場合、当該３次元特徴点１が見えていることとなる。つまり、撮影対象の不透明性を仮定すれば、視点Ａと３次元特徴点１の間には遮視対象物が存在しないと言える。
【００３８】
図１（ａ）は、３次元特徴点を持つ３次元形状と各視点から得られる２次元画像中の特徴点の関係を概念的に示す図である。説明を簡単にするため、３次元空間をある高さで輪切りにした２次元平面としている。３次元形状は当該平面に７つの特徴点１〜７を持っている。各視点Ａ〜Ｃから得られる２次元撮影画像は、図１（ａ）に示すような各視点上に張られた平面への投影と捉えることができる。例えば、視点Ａからは特徴点２，１，７，６，５が見えていることを意味し、逆に特徴点１から見れば視点Ａのみが見えており、特徴点７から見れば視点Ａと視点Ｂが見えている。本発明ではこの特徴点と視点との間の可視関係を可視情報と呼ぶ。当該可視情報は図１（ａ）の例であれば、図１（ｂ）に示す可視情報テーブルにまとめることができる。
【００３９】
次に、初期形状の形成処理について述べる。
【００４０】
本発明における、３次元特徴点列を用いた初期形状の例および可視情報を用いた不用部分の削除処理の例について説明する。
【００４１】
第１の初期形状の例としては、３次元特徴点列の凸包が挙げられる。３次元特徴点列の凸包とは、３次元特徴点を空間に配置して、それらすべてを内側に含む巨大なゴムの風船をできる限り縮小して得られる凸多面体である。凸包を形成する様子を２次元的に表わしたものが図２である。この凸包形成によれば、実際の３次元形状が複雑で入り組んでいる場合や窪みがある場合には内側に存在する特徴点は凸包の内部に隠されてしまうが、３次元形状の大枠外形を簡便に形成することができる。この凸包を初期形状し、凸包では表現できない複雑な部分や窪み部分を覆う不要部分を後述する可視情報を用いて削除してゆく。
【００４２】
３次元特徴点列の凸包を初期形状とする場合の不用部分の削除処理は次のように行なう。説明の簡便のため、図３に示すように特徴点１１、１２、１３、１４を頂点に持つ四面体を例として説明する。いま、凸包の頂点ではない特徴点１５が可視情報として視点Ａを持つ場合、図３（ａ）のように特徴点１５は四面体の内部に隠れていることになる。この特徴点１５と視点Ａとの間に線分を引く。この線分上には本来遮視物はないはずであり、線分と交わる面１１−１２−１３は本来形成されない面であることが分かる。そこで、四面体小立体１１−１２−１３−１５を削除して図３（ｂ）のように窪みを持った３次元形状を得る。
【００４３】
３次元形状が複雑な場合でもこの不要な立体部分を削除する基本処理を各特徴点について繰り返し実施して、撮影画像から抽出した３次元特徴点列間を結んだ近似３次元形状を得ることができる。
【００４４】
第２の初期形状と不要部分削除処理の例としては、基本小立体の組み合わせにより初期形状の大枠を形成しておき、可視情報を用いて不要の基本小立体を順次削除してゆくものが挙げられる。ここで、基本小立体の組み合わせによる初期形状の構成方法には様々なものがある。
【００４５】
基本小立体の組み合わせの第１の例としては、３次元特徴点列のドロネー図を利用して小４面体を形成し、当該小４面体を基本小立体とするものがある。ここでいうドロネー図とは、凸包をある４面体の集合に分割したものである。図４にドロネー図の例を示す。図４の例は５つの特徴点のドロネー図を表わしている。つまり、４つの基本小四面体、１−２−３−５、１−３−４−５、１−２−４−５、２−３−４−５により構成される。この後、不要部分の削除処理は可視情報を用いて特徴点と視点の間に存在する小四面体を削除して行く。
【００４６】
上記のドロネー図による基本小立体のモデルは、通常ソリッドモデルとして把握される。ここに復元結果には物体の内部と外部が定義できる。しかし、実際の３次元形状の復元処理では、撮影対象の境界面だけで定義されるサーフィスモデルで十分である場合が多い。したがって上記ドロネー図を利用した初期形状はソリッドモデルと扱う必要は必ずしもなく、図４をドロネー図を利用した面の集合と考えることも可能である。このように上記の初期形状という概念にはソリッドモデルのみならず、サーフィスモデルも包含するものとする。なお、サーフィスモデルとして扱う場合も、不要部分（不要面）の削除処理は、可視情報を用いて特徴点と視点の間に張られている面を削除して行く処理となる。サーフィスモデルとしての出力においては、内部に存在する面は必要ないので外部から観察できる外表面を形成する面のみを選択して出力とする。外表面を形成する面であるか否かの一つの判断手法としては、面が２つの４面体により共有されていれば内部の面、面が１つの４面体のみにより保持されている場合は外表面と判断できる。
【００４７】
基本小立体の組み合わせの第２の例としては、所定の単位長による基本小立体である立方体、正４面体、正８面体、正２０面体を用いるものである。これら基本小立体から初期形状を得る方法として、マスク画像を用いた近似３次元形状の生成を行なう。本発明ではマスク画像とは、各視点から撮影した画像のうち３次元形状部分に対する画素の値を“１”、背景に対応する画素の値を“０”とした画像をいう。マスク画像の自動生成処理方法としては、３次元形状の輪郭線（エッジ）を検出する方法や、３次元形状の写り込んだ撮影画像と３次元形状を除去して撮影した２つの画像を用意し、画素ごとに比較して差分が大きく表れている部分を抽出する方法などがある。このマスク画像は、特徴点抽出処理に先行して行なうことが好ましい。特徴点は３次元形状のみならず背景部分にも存在するので、未処理の撮影画像から抽出処理を行なうと背景部分の特徴点も抽出してしまうが、先立ってマスク画像の領域外の撮影画像部分を除去しておけば、背景部分の特徴点抽出処理が省略することができる。撮影した３次元形状の例を図５（ａ）に示す。図５（ａ）の例では説明の便宜上、ワイヤーフレームモデルとしてコンピュータグラフィックスにより描いている。また、説明の便宜上、一方向から見た図のみを示している。この図５（ａ）の３次元形状に対するマスク形状の例を図５（ｂ）に示す。本来複数の視点のマスク画像を得ることが好ましいが、説明の便宜上、一視点からのマスク画像のみ示した。
【００４８】
基本小立体から初期形状を得る手順は図７に示すものである。
【００４９】
まず、基本小立体を構成単位として仮想空間を埋める集合体を想定する（ステップＳ７０１）。次に、各基本小立体の重心を各視点方向に投影する（ステップＳ７０２）。この投影点と当該視点から得られているマスク画像とを重ね合わせ、各重心点がマスク画像の領域内にあるか領域外にあるかを判断する（ステップＳ７０３）。ステップＳ７０３の判定で少なくとも１つの視点においてマスク画像の領域外にあると判断された重心を持つ基本小立体はすべて初期形状から削除する（ステップＳ７０４）。ステップＳ７０４の削除処理済みの残された基本小立体の組み合わせを初期形状として出力する（ステップＳ７０５）。つまり、この基本小立体から初期形状を得る手順をまとめると、マスク画像前記撮影方向情報とマスク情報に基づいて、撮影方向から見て前記マスク画像情報の示す外周縁の外にある基本小立体を前記集合体から削除するものであると言える。本発明ではこの処理を３次元マスク処理と呼ぶ。この３次元マスク処理により、３次元形状を基本小立体の集合で近似的に構成した３次元集合体が得られる。図５（ｂ）の３次元マスク画像を用いて３次元マスク処理により生成した初期形状となる近似３次元形状は図６（ａ）のようになる。
【００５０】
このマスク処理により得た３次元形状の初期形状の不要部分を削除する処理手順は図８のフローチャートに示すものである。まず、撮影画像から得た３次元特徴点を、３次元マスク処理により生成した３次元形状の初期形状に重ねて表示する（ステップＳ８０１）。次に、可視情報を用い、各視点と特徴点とを結ぶ線分を引く（ステップＳ８０２）。次に、この線分と交差する基本小立体をすべて削除して行く（ステップＳ８０３）。残された基本小立体の集合体を３次元形状の近似形状として出力する（ステップＳ８０４）。
【００５１】
図６（ａ）に示した初期形状である近似３次元集合体に対して可視情報を用いて不要部分の削除処理を施した結果は図６（ｂ）のようになる。図６（ｂ）の不要部分削除処理後の近似３次元形状は、図６（ａ）の初期形状である近似３次元形状よりも精度が向上していることが分かる。
【００５２】
なお、復元すべき３次元形状が窪みのない単純な形状であれば、３次元マスク処理により生成した初期形状をもって３次元形状の近似形状としても良いことは言うまでもない。
【００５３】
以下に、上記の３次元形状生成処理の基本概念を適用した実施形態について述べる。
【００５４】
（実施形態１）
実施形態１の３次元形状生成装置は、撮影画像から得た３次元特徴点情報と可視情報を用い、３次元特徴点を仮想３次元空間上に展開配置し、可視情報を満たすように３次元特徴点間に面を当てはめ、当該面を近似３次元形状面として出力する装置である。
【００５５】
図９は、実施形態１の３次元形状生成装置の一構成例を示す図である。図９において、１０は入力部、２０は特徴点展開処理部、３０は可視面当てはめ部、４０は３次元形状出力部である。なお、本実施形態１では、入力部１０の前段部分として撮影画像入力部５０、特徴点抽出部６０、可視情報抽出部７０が設けられている。
【００５６】
入力部１０からは、３次元特徴点情報と可視情報が入力される。可視情報とともに撮影方向の情報も併せて入力されるものとする。当初から３次元形状の３次元特徴点と可視情報が得られている場合には入力部１０の前段の要素は必要はないが、本実施形態１では当該情報を抽出する要素を持っている。
【００５７】
撮影画像入力部５０は３次元形状を撮影した２次元撮影画像が入力される部分である。
【００５８】
特徴点抽出部６０は、入力された２次元撮影画像から写り込んだ３次元形状の特徴点を抽出する部分である。特徴点抽出方法は基本原理で説明したように、２次元撮影画像の中で明度が変化している箇所を計算処理で選択し、複数の撮影画像間で対応付けを行ない、ステレオ計測の原理により３次元座標を求める。画像のエッジや頂点などを人手で選び、対応付けを行なう方法でも良い。
【００５９】
可視情報抽出部７０は、各特徴点の対応付けを基に可視情報を抽出する部分であり、可視情報の抽出方法は、基本原理の図１で説明したように、各３次元特徴点と対応する２次元特徴点が存在する撮影方向（図１（ａ））から可視情報テーブル（図１（ｂ））を抽出する。
【００６０】
特徴点抽出部６０および可視情報抽出部７０により抽出された３次元特徴点と可視情報および撮影方向の情報が入力部１０に渡される。
【００６１】
特徴点展開処理部２０は、特徴点情報に基づいて仮想空間上に３次元特徴点を展開配置する部分である。この仮想空間上に展開配置した３次元特徴点間に面を当てはめることにより３次元形状を近似的に復元する。
【００６２】
可視面当てはめ部３０は、撮影方向情報と可視情報に基づいて、撮影方向から可視となっている特徴点間にそれら特徴点が可視となるように面を当てはめる部分である。可視情報と矛盾のないように特徴点間に面を当てはめれば良いが、ここではその可視面当てはめ部３０による面当てはめ処理手順の一例を挙げると、まず、３次元特徴点間に当てはめられる面をすべて当てはめる。面としては基本原理で説明した図４に示したような特徴点間のドロネー図の面とすることができる。次に、可視情報に基づき、特徴点と当該特徴点が可視である撮影方向とを結ぶ線分を引き、前記線分が前記当てはめた面と交差する場合には当該交差する面を削除し、交差しない面のみを残こす。この手順をすべての可視情報について実行する。
【００６３】
なお、入力された撮影画像では３次元形状の周囲すべてをカバーできずに一部に死角がある場合には、可視情報によりすべての面の適否を判断できない場合があるが、この場合は当該部分を人手により後処理するか、面積の大きい面を優先して残すなどの一定の基準を導入しても良い。
【００６４】
３次元形状出力部４０は、可視面当てはめ部３０により当てはめられた面を外形面とする３次元形状を出力表示する部分である。
【００６５】
以上、本実施形態１の３次元形状生成装置によれば、撮影画像から得た３次元特徴点情報と可視情報を用い、可視情報を満たすように３次元特徴点間に面を当てはめ、近似３次元形状面を得ることができる。
【００６６】
（実施形態２）
実施形態２の３次元形状生成装置は、撮影画像から得た３次元特徴点情報と可視情報を用い、３次元特徴点の凸包を初期形状として生成し、初期形状である凸包では表現できない複雑な部分や窪み部分を覆う不要部分を可視情報を用いて削除して近似３次元形状立体を生成する装置である。
【００６７】
図１０は、実施形態２の３次元形状生成装置の一構成例を示す図である。図１０において、１１０は入力部、１２０は特徴点展開処理部、１３０は凸包立体形成部、１４０は遮視立体部分削除部、１５０は３次元形状出力部である。なお、本実施形態２においても実施形態１と同様、入力部１１０の前段部分として撮影画像入力部５０、特徴点抽出部６０、可視情報抽出部７０を設けても良い。
【００６８】
入力部１１０からは、３次元特徴点情報と可視情報が入力される。入力される３次元特徴点情報、可視情報、撮影方向情報は実施形態１と同様である。本実施形態２においても実施形態１と同様、当初から３次元形状の３次元特徴点、可視情報が得られていない場合に当該情報を抽出する要素として、撮影画像入力部５０、特徴点抽出部６０、可視情報抽出部７０を備えることが好ましい。
【００６９】
特徴点展開処理部１２０は、特徴点情報に基づいて仮想空間上に３次元特徴点を展開配置する部分である。
【００７０】
凸包立体形成部１３０は、展開配置された３次元特徴点列から凸包を形成し、初期形状を生成する部分である。凸包の形成は基本原理で説明した図２のように形成される。図１１（ａ）（正面画像）および図１１（ｂ）（斜め上から見下ろした画像）は、図５（ａ）に示した３次元形状の特徴点から凸包を形成した例を示す図である。
【００７１】
遮視立体部分削除部１４０は、可視情報を用いて初期形状の凸包から不要部分を削除する部分である。削除処理は基本原理の図３を用いて説明した手順をすべての可視情報について実行することにより行なう。図１１（ａ）の凸包から可視情報に基づいて不要部分である遮視立体部分を削除した場合も実施形態１と同様、図６（ｂ）の画像が得られる。
【００７２】
３次元形状出力部１５０は、初期形状である凸包から可視情報を用いて不要な立体部分を削除した近似３次元形状を出力する部分である。
【００７３】
なお、入力された撮影画像では３次元形状の周囲すべてをカバーできずに一部に死角がある場合には、可視情報により凸包上にある一部の不要部分の判断ができない場合があるが、この場合は人手により後処理するか、当該凸包形状のまま残すなどの一定の基準を導入しても良い。
【００７４】
以上、実施形態２の３次元形状生成装置によれば、撮影画像から得た３次元特徴点情報と可視情報を用い、３次元特徴点列から形成した凸包を初期形状とし、可視情報を用いて凸包上の不要立体部分を削除して近似３次元形状立体を生成することができる。
【００７５】
（実施形態３）
実施形態３の３次元形状生成装置は、撮影画像から得た３次元特徴点情報と可視情報とマスク画像情報とを用い、マスク画像情報を利用して基本小立体により初期形状を生成し、初期形状と重ねて表示した３次元特徴点と可視情報を用いて初期形状の不要小立体部分を削除して近似３次元形状立体を生成する装置である。
【００７６】
図１２は、実施形態３の３次元形状生成装置の一構成例を示す図である。図１２において、２１０は入力部、２２０は特徴点展開処理部、２３０は３次元マスク処理部、２４０は遮視基本小立体削除部、２５０は３次元形状出力部である。なお、本実施形態３では、入力部２１０の前段部分として撮影画像入力部５０、マスク画像抽出部８０、特徴点抽出部６０、可視情報抽出部７０を設けても良い。
【００７７】
入力部２１０からは、３次元特徴点情報と可視情報とマスク画像情報が入力される。３次元特徴点情報、可視情報、撮影方向情報は実施形態１と同様である。マスク画像情報は、上記基本原理の説明において説明したものであり、図５（ｂ）に示したようなものである。本実施形態３においても当初から３次元形状の３次元特徴点、可視情報、マスク画像情報が得られていない場合に当該情報を抽出する要素として、撮影画像入力部５０、特徴点抽出部６０、可視情報抽出部７０に加え、マスク画像抽出部８０を備えている。マスク画像抽出部８０は、上記基本原理で説明したように、３次元形状の輪郭線（エッジ）を検出する方法や、３次元形状の写り込んだ撮影画像と３次元形状を除去して撮影した２つの画像から差分の大きい部分を抽出する方法などによりマスク画像を抽出する。マスク画像抽出部８０、特徴点抽出部６０、可視情報抽出部７０により抽出された３次元特徴点、可視情報、撮影方向情報、マスク画像が入力部２１０に渡される。
【００７８】
特徴点展開処理部２２０は、特徴点情報に基づいて仮想空間上に３次元特徴点を展開配置する部分である。
【００７９】
３次元マスク処理部２３０は、基本小立体を組み合わせた初期形状を生成する部分であり、基本小立体展開部２３１、基本小立体投影部２３２、３次元マスク外基本小立体判定部２３３、３次元マスク外基本小立体削除部２３４を備えている。３次元マスク処理部２３０の初期形状形成処理手順は、基本原理で図７を用いて説明したものと同様である。基本小立体展開部２３１により基本小立体を構成単位として仮想空間を埋める集合体を想定し、基本小立体投影部２３２により各基本小立体の重心を各視点方向に投影する。３次元マスク外基本小立体判定部２３３により投影した各重心点のうちマスク画像の領域外にある基本小立体を不要部分と判断する。３次元マスク外基本小立体削除部２３４は前記不要部分と判断された基本小立体を削除して初期形状を得る。なお基本小立体としては、正４面体、正６面体、正８面体、正２０面体、ドロネー図の４面体などがある。
【００８０】
遮視基本小立体削除部２４０は、可視情報を用いて初期形状の基本小立体集合体から不要基本小立体を削除する部分である。削除処理は基本原理の図８を用いて説明した手順をすべての可視情報について実行することにより行なう。結局可視である特徴点を隠すように覆っている基本小立体が削除される。
【００８１】
３次元形状出力部２５０は、初期形状から不要な基本小立体を削除した近似３次元形状を出力する部分である。
【００８２】
なお、入力された撮影画像では３次元形状の周囲すべてをカバーできずに一部に死角がある場合には、可視情報によりすべての面の適否を判断できない場合があるが、この場合は当該部分を人手により後処理するか、初期形状のまま残すなどの一定の基準を導入しても良い。
【００８３】
以上、実施形態３の３次元形状生成装置によれば、撮影画像から得た３次元特徴点情報と可視情報とマスク画像情報とを用い、マスク画像情報を利用して基本小立体により初期形状を生成し、初期形状と重ねて表示した３次元特徴点と可視情報を用いて初期形状の不要小立体部分を削除して近似３次元形状立体を生成することができる。
【００８４】
（実施形態４）
本発明の３次元形状生成装置は、上記に説明した構成を実現する処理ステップを記述したプログラムをコンピュータ読み取り可能な記録媒体に記録して提供することにより、各種コンピュータを用いて構築することができる。本発明の３次元形状生成装置を実現する処理ステップを備えたプログラムを記録した記録媒体は、図１３に図示した記録媒体の例に示すように、ＣＤ−ＲＯＭ１３０２やフレキシブルディスク１３０３等の可搬型記録媒体１３０１だけでなく、ネットワーク上にある記録装置内の記録媒体１３００や、コンピュータのハードディスクやＲＡＭ等の記録媒体１３０５のいずれであっても良く、プログラム実行時には、プログラムはコンピュータ１３０４上にローディングされ、主メモリ上で実行される。
【００８５】
【発明の効果】
本発明の３次元形状生成装置によれば、撮影画像から得た３次元特徴点情報と可視情報を用い、可視情報を満たすように３次元特徴点間に面を当てはめ、近似３次元形状面を得ることができる。
【００８６】
また、本発明の３次元形状生成装置によれば、撮影画像から得た３次元特徴点情報と可視情報を用い、３次元特徴点列から形成した凸包を初期形状とし、可視情報を用いて凸包上の不要立体部分を削除して近似３次元形状立体を生成することができる。
【００８７】
また、本発明の３次元形状生成装置によれば、撮影画像から得た３次元特徴点情報と可視情報とマスク画像情報とを用い、マスク画像情報を利用して基本小立体により初期形状を生成し、初期形状と重ねて表示した３次元特徴点と可視情報を用いて初期形状の不要小立体部分を削除して近似３次元形状立体を生成することができる。
【００８８】
また、本発明の３次元形状生成装置を実現する処理プログラム記録した記録媒体をコンピュータに読み取らせることより、コンピュータを利用して、３次元形状の特徴点と撮影視点との可視情報を用いて高速かつ復元精度の良い３次元形状生成装置を構成することができる。
【図面の簡単な説明】
【図１】  本発明にかかる３次元特徴点を持つ３次元形状と各視点から得られる２次元画像中の特徴点の関係を概念的に示す図
【図２】  本発明にかかる凸包を形成する様子を２次元的に表わした図
【図３】  本発明にかかる３次元特徴点列の凸包を初期形状とする場合の不用部分の削除処理を説明する図
【図４】  本発明にかかる３次元特徴点列のドロネー図を利用して小４面体を形成し、当該小４面体を基本小立体とする概念を表わす図
【図５】  ３次元形状の例（ａ）と３次元マスク形状の例（ｂ）を示す図
【図６】  ３次元マスク処理により生成した初期形状の例（ａ）と初期形状に対して可視情報を用いて不要部分の削除処理を施した結果（ｂ）を示す図
【図７】  基本小立体から初期形状を得る手順を示すフローチャート
【図８】  マスク処理により得た３次元形状の初期形状の不要部分を削除する処理手順を示すフローチャート
【図９】  本発明の実施形態１の３次元形状生成装置の一構成例を示す図
【図１０】  本発明の実施形態２の３次元形状生成装置の一構成例を示す図
【図１１】  図５（ａ）の３次元形状から抽出した特徴点を用いて凸包作成した例の正面画像（ａ）と例の斜め上から見下ろした画像（ｂ）を示す図
【図１２】  本発明の実施形態３の３次元形状生成装置の一構成例を示す図
【図１３】  記録媒体の例および当該記録媒体の処理プログラムを用いたシステム構成の例を示す図
【図１４】  従来のテクスチャ画像生成処理ステップを示したフローチャート
【図１５】  従来の特徴点に基づく３次元画像データ生成の概念を示す図
【図１６】  コンピュータ画面上での３次元画像再生処理ステップを示したフローチャート
【符号の説明】
１０，１１０，２１０  入力部
２０，１２０，２２０  特徴点展開処理部
３０  可視面当てはめ部
４０，１５０，２５０  ３次元形状出力部
５０  撮影画像入力部
６０  特徴点抽出部
７０  可視情報抽出部
８０  マスク画像抽出部
１３０  凸包立体形成部
１４０  遮視立体部分削除部
２３０  ３次元マスク処理部
２３１  基本小立体展開部
２３２  基本小立体投影部
２３３  ３次元マスク外基本小立体判定部
２３４  ３次元マスク外基本小立体削除部
２４０  遮視基本小立体削除部
１３００  回線先のハードディスク等の記録媒体
１３０１  ＣＤ−ＲＯＭやフレキシブルディスク等の可搬型記録媒体
１３０２  ＣＤ−ＲＯＭ
１３０３  フレキシブルディスク
１３０４  コンピュータ
１３０５  コンピュータ上のＲＡＭ／ハードディスク等の記録媒体
【図１】
0003751770.tif 000002
【図２】
0003751770.tif 000003
【図３】
0003751770.tif 000004
【図４】
0003751770.tif 000005
【図５】
0003751770.tif 000006
【図６】
0003751770.tif 000007
【図７】
0003751770.tif 000008
【図８】
0003751770.tif 000009
【図９】
0003751770.tif 000010
【図１０】
0003751770.tif 000011
【図１１】
0003751770.tif 000012
【図１２】
0003751770.tif 000013
【図１３】
0003751770.tif 000014
【図１４】
0003751770.tif 000015
【図１５】
0003751770.tif 000016
【図１６】
0003751770.tif 000017