(57)【要約】    【課題】  実際には対象物上に面が存在しない領域において無効なポリゴンを生成することなく，高品質な３次元モデルを自動的に生成する。    【解決手段】  点群データ取得部３１は，第１撮像カメラ１０および第２撮像カメラ２０の撮像画像中における画素位置，すなわち２次元の座標値を基にして三角測量法に従って３次元座標を算出する。仮接続情報生成部３２は，この２次元の座標値を用いて三角形網を生成し，仮のポリゴン生成用接続情報とする。最終接続情報生成部３３は，ポリゴンの大きさに基づいて無効とみなすポリゴンをポリゴン生成用接続情報から除去し，最終ポリゴン生成用接続情報を生成する。これにより，ノイズ点および本来対象物上にはないポリゴンの除去を行い，最終的な３次元モデルの品質の低下を防ぐことができる。【選択図】  図２
2006065472.tif 000002
【特許請求の範囲】
【請求項１】
対象物の撮像画像から三角測量の原理で得られた３次元座標を有する点群を基にして前記対象物の３次元モデルを生成する３次元モデル生成装置であって，
前記３次元座標を算出する際に用いられた２次元座標を基に三角形網を生成して仮のポリゴン生成用接続情報を生成する仮接続情報生成手段と，
前記仮のポリゴン生成用接続情報および前記３次元座標を基にして，無効なポリゴンを判定してその接続情報を前記仮のポリゴン生成用接続情報から除去することにより，最終ポリゴン生成用接続情報を生成する最終接続情報生成手段と，
最終ポリゴン生成用接続情報を基にして前記点群を三角形ポリゴン化するポリゴン化手段とを有し，
前記最終接続情報生成手段が，
（ａ）前記仮のポリゴン生成用接続情報を用いて前記点群を三角形ポリゴン化する仮ポリゴン化手段と，
（ｂ）前記点群のおのおのの点について無効データであるかどうかを判定する無効点群判定手段と，
（ｃ）無効点群判定手段（ｂ）により無効データと判定された点に対して，近傍の無効ではない点群が有する３次元座標から補間された座標値を新たな座標値として設定する補間手段と，
（ｄ）各ポリゴンが有する頂点の，補間手段（ｃ）により補間した後の３次元座標値を基に，各ポリゴンが無効なポリゴンであるかどうかを判定する無効ポリゴン判定手段と，
（ｅ）無効ポリゴン判定手段（ｄ）において無効と判定されたポリゴンを発生させたポリゴン生成用接続情報を前記仮のポリゴン生成用接続情報から削除して新たな仮のポリゴン生成用接続情報とする無効接続情報削除手段とを有し，
前記（ａ）−（ｅ）の各手段が繰り返し実行するように制御して，無効点群および無効ポリゴンが発生しなくなった時点でのポリゴン生成用接続情報を最終ポリゴン生成用接続情報とすることを特徴とする３次元モデル生成装置。
【請求項２】
前記無効点群判定手段は，判定対象となっている点が所定の座標範囲外の座標値を有する場合に無効であると判定する請求項１記載の３次元モデル生成装置。
【請求項３】
前記無効点群判定手段は，判定対象となっている点の近傍に存在する点群について座標の平均値を算出し，該点の座標との差が所定の閾値以上である場合に無効であると判定する請求項１または２記載の３次元モデル生成装置。
【請求項４】
前記無効点群判定手段は，判定対象となっている点を頂点として共有するポリゴンの法線成分の和が所定の閾値以下である場合に無効であると判定する請求項１，２または３記載の３次元モデル生成装置。
【請求項５】
前記無効ポリゴン判定手段は，判定対象となっているポリゴンの大きさが所定の閾値以上である場合に無効であると判定する請求項１〜４のいずれかに記載の３次元モデル生成装置。
【請求項６】
上記ポリゴンの大きさは面積で表される請求項５記載の３次元モデル生成装置。
【請求項７】
上記ポリゴンの大きさはポリゴンの最長の一辺での長さで表される請求項５記載の３次元モデル生成装置。
【請求項８】
上記ポリゴンの大きさはポリゴンの三辺の和の長さで表される請求項５記載の３次元モデル生成装置。
【請求項９】
上記ポリゴンの大きさはポリゴンを囲む長方形のアスペクト比で表される請求項５記載の３次元モデル生成装置。
【請求項１０】
対象物の撮像画像から三角測量の原理で得られた３次元座標を有する点群を基にして前記対象物の３次元モデルを生成する方法であって，
前記３次元座標を算出する際に用いられた２次元座標を基に三角形網を生成して仮のポリゴン生成用接続情報を生成する工程と，
前記仮のポリゴン生成用接続情報および前記３次元座標を基にして，無効なポリゴンを判定してその接続情報を前記仮のポリゴン生成用接続情報から除去することにより，最終ポリゴン生成用接続情報を生成する工程と，
最終ポリゴン生成用接続情報を基にして前記点群を三角形ポリゴン化するポリゴン化工程とを有し，
前記最終ポリゴン生成用接続情報を生成する工程が，
（ａ）前記仮のポリゴン生成用接続情報を用いて前記点群を三角形ポリゴン化するポリゴン化工程と，
（ｂ）前記点群のおのおのの点について無効データであるかどうかを判定する無効点群判定工程と，
（ｃ）工程（ｂ）において無効データと判定された点に対して，近傍の無効ではない点群が有する３次元座標から補間された座標値を新たな座標値として設定する無効点群座標補間工程と，
（ｄ）各ポリゴンが有する頂点の，工程（ｃ）を経た後の３次元座標値を基に，各ポリゴンが無効なポリゴンであるかどうかを判定する無効ポリゴン判定工程と，
（ｅ）工程（ｄ）において無効と判定されたポリゴンを発生させたポリゴン生成用接続情報を前記仮のポリゴン生成用接続情報から削除して新たな仮のポリゴン生成用接続情報とする工程と，
前記（ａ）−（ｅ）の工程を繰り返し行い，無効点群および無効ポリゴンが発生しなくなった時点でのポリゴン生成用接続情報を最終ポリゴン生成用接続情報とする工程とから構成されることを特徴とする３次元モデル生成方法。
【請求項１１】
対象物の撮像画像から三角測量の原理で得られた３次元座標を有する点群を基にして前記対象物の３次元モデルを生成する３次元モデル生成装置であって，
前記３次元座標を算出する際に用いられた２次元座標を基に三角形網を生成してポリゴン生成用接続情報を生成する仮接続情報生成手段と，
前記仮のポリゴン生成用接続情報および前記３次元座標を基にして，ポリゴンの大きさが所定値より大きいときい無効と判定されたときに，その接続情報を無効と判定して前記ポリゴン生成用接続情報から除去する無効接続情報除去手段と，
無効と判定された接続情報を除去したポリゴン生成用接続情報を基にして前記点群を三角形ポリゴン化するポリゴン化手段とを有することを特徴とする３次元モデル生成装置。
【請求項１２】
上記ポリゴンの大きさは面積で表される請求項１１記載の３次元モデル生成装置。
【請求項１３】
上記ポリゴンの大きさはポリゴンの最長の一辺での長さで表される請求項１１記載の３次元モデル生成装置。
【請求項１４】
上記ポリゴンの大きさはポリゴンの三辺の和の長さで表される請求項１１記載の３次元モデル生成装置。
【請求項１５】
上記ポリゴンの大きさはポリゴンを囲む長方形のアスペクト比で表される請求項１１記載の３次元モデル生成装置。
【請求項１６】
対象物の撮像画像から三角測量の原理で得られた３次元座標を有する点群を基にして前記対象物の３次元モデルを生成する３次元モデル生成方法であって，
前記３次元座標を算出する際に用いられた２次元座標を基に三角形網を生成してポリゴン生成用接続情報を生成する仮接続情報生成工程と，
前記仮のポリゴン生成用接続情報および前記３次元座標を基にして，ポリゴンの大きさが所定値より大きいときい無効と判定されたときに，その接続情報を無効と判定して前記ポリゴン生成用接続情報から除去する無効接続情報除去工程と，
無効と判定された接続情報を除去したポリゴン生成用接続情報を基にして前記点群を三角形ポリゴン化するポリゴン化工程とを有することを特徴とする３次元モデル生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，物体の３次元モデル生成技術に関し，特に，対象物の撮像画像から三角測量の原理で得られた離散的な距離データから，高品質なポリゴンデータを自動的に生成する３次元モデル生成技術に関する。
【背景技術】
【０００２】
従来，２次元画像を基に距離データを取得し，３次元のモデルを生成する手法が数多く提案されている。２次元画像を基に距離データ（３次元座標データ）を取得する手法には，アクティブ手法と呼ばれる，スリット光などの特殊なパターン光源を用いて，対象表面パターンの幾何学的変形等の画像情報より対象形状を推定するパターン投影方法や，パッシブ手法と呼ばれる，対象物の見え方，光源，照明，影情報等に関する知識を利用して，一枚の画像から３次元情報を推定する単眼立体視，三角測量原理で各画素の奥行き情報を推定するステレオ法等がある。上述の手法を適用して得られる計測対象の距離情報は，計測対象の表面形状を表すデータであり，レンジデータと呼ばれる。レンジデータは，測定対象の表面上においてサンプリングされた３次元座標データの集合データである。
【０００３】
一方，一般に三次元モデルとして扱う際には，対象物の表面をポリゴンと呼ばれる多角形形式で近似することが多い。レンジデータは上述の通り点の単なる集合であり，各点をどの点と接続して多角形とするかという構造をもっていない。そこで，レンジデータから多角形を構成するための手法が必要となる。２次元画像を基にしたレンジデータの場合，元の２次元画像での画素位置を利用して三角形網に分割することがよく用いられている。その中でも，ドロネー（Ｄｅｌａｕｎａｙ）法は生成される三角形が正三角形に近くなり，３次元モデルとしてレンダリングを行うに好適であるという性質があるため特によく知られた手法である。
【０００４】
しかしＤｅｌａｕｎａｙ法は原理的に凸多角形を三角形に分割する手法である。したがって，図５に示すように実際の対象物上に面が存在しない凹部領域に対しても三角形網が生成されてしまう。このような現象は，物体の境界情報がレンジデータには含まれないため，三角形分割の手法によらず発生する可能性がある。この現象が発生したまま三次元モデルを作成すると偽の形状情報が含まれてしまい，モデルとしての品質が低下してしまう。この問題を解決するため，例えば特許文献１に開示されるようにユーザが凹部に対応する領域を指定し，その領域における三角形網を除去してモデルを生成する方法が知られている。
【０００５】
なお，Ｄｅｌａｕｎａｙ法については，非特許文献１を参照されたい。
【特許文献１】特開平８−１２２０３０号公報
【非特許文献１】今井  浩，今井  桂子，「計算幾何学」，情報数学講座第１２巻，第５章
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら，特許文献１に開示される方法においては凹部をユーザが指定する必要があることから，近年の３次元座標データ取得装置が出力するような大量の距離データの場合にはモデル作成の工数が非常に大きくなってしまう。
【０００７】
そこで，本発明においては，実際には対象物上に面が存在しない領域において無効なポリゴンを生成することなく，高品質な３次元モデルを自動的に生成することを目的とする。さらに，本発明においては，ポリゴン生成の基となる３次元座標にノイズデータが含まれていたとしても，安定して上述のような高品質な３次元モデルを自動的に生成することを目的とする。
【課題を解決するための手段】
【０００８】
本発明によれば，上述の目的を達成するために，特許請求の範囲に記載のとおりの構成を採用している。ここでは，発明を詳細に説明するのに先だって，特許請求の範囲の記載について補充的に説明を行なっておく。
【０００９】
すなわち，本発明の一側面によれば，上述の目的を達成するために，対象物の撮像画像から三角測量の原理で得られた３次元座標を有する点群を基にして前記対象物の３次元モデルを生成する３次元モデル生成装置に：前記３次元座標を算出する際に用いられた２次元座標を基に三角形網を生成して仮のポリゴン生成用接続情報を生成する仮接続情報生成手段と；前記仮のポリゴン生成用接続情報および前記３次元座標を基にして，無効なポリゴンを判定してその接続情報を前記仮のポリゴン生成用接続情報から除去することにより，最終ポリゴン生成用接続情報を生成する最終接続情報生成手段と；最終ポリゴン生成用接続情報を基にして前記点群を三角形ポリゴン化するポリゴン化手段とを設け，さらに，前記最終接続情報生成手段が：（ａ）前記仮のポリゴン生成用接続情報を用いて前記点群を三角形ポリゴン化する仮ポリゴン化手段と；（ｂ）前記点群のおのおのの点について無効データであるかどうかを判定する無効点群判定手段と；（ｃ）無効点群判定手段（ｂ）により無効データと判定された点に対して，近傍の無効ではない点群が有する３次元座標から補間された座標値を新たな座標値として設定する補間手段と；（ｄ）各ポリゴンが有する頂点の，補間手段（ｃ）により補間した後の３次元座標値を基に，各ポリゴンが無効なポリゴンであるかどうかを判定する無効ポリゴン判定手段と；（ｅ）無効ポリゴン判定手段（ｄ）において無効と判定されたポリゴンを発生させたポリゴン生成用接続情報を前記仮のポリゴン生成用接続情報から削除して新たな仮のポリゴン生成用接続情報とする無効接続情報削除手段とを有するようになし；前記（ａ）−（ｅ）の各手段が繰り返し実行するように制御して，無効点群および無効ポリゴンが発生しなくなった時点でのポリゴン生成用接続情報を最終ポリゴン生成用接続情報とするようにしている。
【００１０】
この構成においては，実際には対象物上に面が存在しない領域においてポリゴンを生成することなく，高品質な３次元モデルを自動的に生成することができる。とくに，ポリゴン生成の基となる３次元座標にノイズデータが含まれていたとしても，安定して高品質な３次元モデルを生成することができる。
【００１１】
この構成において，前記無効点群判定手段は，判定対象となっている点が所定の座標範囲外の座標値を有する場合に無効であると判定してもよく，判定対象となっている点の近傍に存在する点群について座標の平均値を算出し，該点の座標との差が所定の閾値以上である場合に無効であると判定してもよく，また，判定対象となっている点を頂点として共有するポリゴンの法線成分の和が所定の閾値以下である場合に無効でしてもよく，さらにこれらを組み合わせていずれの場合でも無効であると判断してもよいし，すべてが満たされたときに無効であると判断しても良い。
【００１２】
また，前記無効ポリゴン判定手段は，判定対象となっているポリゴンの大きさが所定の閾値以上である場合に無効であると判定しても良い。上記ポリゴンの大きさは面積で表されてもよいし，上記ポリゴンの大きさはポリゴンの最長の一辺での長さで表されてもよいし，ポリゴンの三辺の和の長さで表されてもよいし，ポリゴンを囲む長方形のアスペクト比で表されてもよい。この場合アスペクト比は長辺を短辺で割ったものである。
【００１３】
また，本発明の他の側面によれば，上述の目的を達成するために，対象物の撮像画像から三角測量の原理で得られた３次元座標を有する点群を基にして前記対象物の３次元モデルを生成する３次元モデル生成装置に：前記３次元座標を算出する際に用いられた２次元座標を基に三角形網を生成してポリゴン生成用接続情報を生成する仮接続情報生成手段と；前記仮のポリゴン生成用接続情報および前記３次元座標を基にして，ポリゴンの大きさが所定値より大きいときい無効と判定されたときに，その接続情報を無効と判定して前記ポリゴン生成用接続情報から除去する無効接続情報除去手段と；無効と判定された接続情報を除去したポリゴン生成用接続情報を基にして前記点群を三角形ポリゴン化するポリゴン化手段とを設けるようにしている。
【００１４】
この構成においては，実際には対象物上に面が存在しない領域においてポリゴンを生成することなく，高品質な３次元モデルを自動的に生成することができる。
【００１５】
上記ポリゴンの大きさは面積で表されてもよいし，ポリゴンの最長の一辺での長さで表されてもよいし，ポリゴンの三辺の和の長さで表されてもよいし，さらに，ポリゴンを囲む長方形のアスペクト比で表されてもよい。この場合アスペクト比は長辺を短辺で割ったものである。
【００１６】
なお，本発明は装置またはシステムとして実現できるのみでなく，方法としても実現可能である。また，そのような発明の一部をソフトウェアとして構成することができることはもちろんである。またそのようなソフトウェアをコンピュータに実行させるために用いるソフトウェア製品も本発明の技術的な範囲に含まれることも当然である。
【００１７】
本発明の上述の側面および他の側面は特許請求の範囲に記載され以下実施例を用いて詳述される。
【発明の効果】
【００１８】
本発明によれば，実際には対象物上に面が存在しない領域においてポリゴンを生成することなく，高品質な３次元モデルを自動的に生成することができる。さらに，ポリゴン生成の基となる３次元座標にノイズデータが含まれていたとしても，安定して上述のような高品質な３次元モデルを自動的に生成することができる。
【発明を実施するための最良の形態】
【００１９】
以下，図面を参照しながら実施例に基づいて，本発明を具体的に説明する。この実施例ではパッシブ法によりレンジデータ（距離情報。点群データともいう）を説明するが，任意の距離測定手法を採用でき，例えば，本件出願人が特許第３４８２９９０号において提案している，投光器と同主点のカメラの画像によりパターンを再コード化するパターン投影法を採用することもできる。この手法によれば，被写体のテクスチャや光学条件にさほど影響を受けずに高精度に点群データを取得できる。
【００２０】
図１は，本発明の実施例の３次元モデル生成装置の構成を示しており，図２は，図１の最終接続情報生成部３３の詳細構成例を示している。図３は，本実施例における３次元モデル生成の全体的なフローチャートを示しており，図４は，主に，無効ポリゴン除去に関する動作のフローチャートを示している。
【００２１】
図１において，本実施例の３次元モデル生成装置は，第１撮像カメラ１０，第２撮像カメラ２０，パーソナルコンピュータ３０等により構成されている。第１撮像カメラ１０および第２撮像カメラ２０により被写体４０を撮影し，それらの撮像画像に三角測量法を適用して被写体４０上の点群の三次元座標を取得する。パーソナルコンピュータ３０は，第１撮像カメラ１０，第２撮像カメラ２０，被写体４０を載置するテーブル（図示しない）等を制御するとともに，そのハードウェア資源およびソフトウェア資源を協同させて，点群データ取得部３１，仮接続情報生成部３２，最終接続情報生成部３３，ポリゴン化部３４等の機能部を実現する。
【００２２】
点群データ取得部３１は，上述したとおり，第１撮像カメラ１０および第２撮像カメラ２０の撮像画像中における画素位置，すなわち２次元の座標値を基にして三角測量法に従って３次元座標を算出している。
【００２３】
仮接続情報生成部３２は，この２次元の座標値を用いて三角形網を生成し，仮のポリゴン生成用接続情報とする。ポリゴン生成用接続情報とは，どの３つの３次元座標点を接続してポリゴンを構築すればよいかという情報である。例えば図５に示されたように画素位置に番号を振られているとする。このとき，１番，２番，１５番の画素位置に対応する３次元座標を結ぶことで１つのポリゴンを生成すればよいということになる。具体的な三角形網の生成手法としては，例えば前述のＤｅｌａｕｎａｙ法を用いることができる。
【００２４】
最終接続情報生成部３３は，無効とみなすポリゴンをポリゴン生成用接続情報から除去し，最終ポリゴン生成用接続情報を生成する。これにより，ノイズ点および本来対象物上にはないポリゴンの除去を行い，最終的な３次元モデルの品質の低下を防ぐことができる。
【００２５】
ポリゴン化部３４は，最終ポリゴン生成用接続情報を基にして前記点群を三角形ポリゴン化して最終的な３次元モデルとする。具体的には，ポリゴン生成用接続情報から，その画素位置に対応する３次元座標をポリゴンの各頂点と設定する。
【００２６】
つぎに，最終接続情報生成部３３の詳細を図２を参照して説明する。図２において，最終接続情報生成部３３は，ポリゴン化部３２１，無効点群判定部３２２，座標補間部３２３，無効ポリゴン判定部３２４，無効接続情報削除部３２５等の各機能部により実現される。各機能部は上述のとおりパーソナルコンピュータ３０のハードウェア資源およびソフトウェア資源を協同させて実現する。
【００２７】
ポリゴン化部３２１はポリゴン化部３４（図１）と同様であり，同一のプロセスを用いて実現できる。ポリゴン化部３２１は，仮接続情報生成部３２（図１）で生成した仮のポリゴン生成用接続情報を基に３次元座標点群を接続し，ポリゴンを生成する。すなわち，ポリゴン生成用接続情報から，その画素位置に対応する３次元座標をポリゴンの各頂点と設定する。無効点群判定部３２２は，与えられた３次元座標点群のおのおのに対して無効であるかどうかを判定する。対象物の撮像画像から三角測量を原理として３次元座標を取得した際，対応点の誤りからノイズ点が発生する場合がある。このようなノイズ点は対象物の実際の３次元座標ではない上，後述する無効ポリゴン判定部３２４による無効ポリゴンの判定に対しても悪影響を及ぼす。したがって，最終的な３次元モデルには反映されないように無効点群として無効ポリゴン判定部３２４の判定の前に処理する必要がある。
【００２８】
無効点群の判定方法の第一としては，３次元座標取得用の装置（第１撮像カメラ１０，第２撮像カメラ２０）が有する測定範囲のワーキングエリアを利用する。一般に３次元座標取得用の装置においては，測定できるワーキングエリアがあらかじめ設定されているため，その範囲外にある点の座標が存在する場合にその点は無効であると判定する。
【００２９】
さらに別の第二，第三の判定方法においては，図６（Ｂ）に示すように無効点であるノイズ点は，周囲の無効ではない点群と比較すると孤立点となっていることが多いという性質を利用する。
【００３０】
判定方法の第二においては，判定対象である点の近傍に存在する点群の座標値の平均値を用いて判定を行う。ノイズ点の座標値は，それら周囲の点群の座標値との平均値とは著しく異なっているため，平均値との差分がある所定の閾値以上である場合に無効であると判定する。近傍として用いる点は，ポリゴン生成用接続情報における２次元座標を用いてもよいし，３次元座標を用いてもよい。
【００３１】
判定方法の第三においては，判定対象である点を頂点として共有するポリゴンの法線成分を用いる。孤立点に関して，その点を頂点として共有するポリゴンの法線はそろっていないため，そのベクトル和は小さくなってしまう。したがって，判定すべき点を頂点として共有するポリゴンの法線のベクトル和がある所定の閾値以下の場合，その点を無効であると判定する。
【００３２】
座標補間部３２３は，無効と判定された点群に対して近傍の無効と判定されていない点群の座標値を用いて補間された座標値を新たに設定する。この処理が必要となるのは，無効と判定された点を単に削除した後にポリゴンを生成すると，図７に示すようにその点近傍において生成されるポリゴンが大きくなってしまうためである。ポリゴンが大きいままであると，後に無効ポリゴン判定部３２４が誤って無効ポリゴンと判定してしまう可能性がある。無効と判定された点は，撮像画像中においては実際に観測されている点であるため，本来は面が存在する可能性が高い。それにもかかわらずその点近傍のポリゴンを無効と判定してポリゴンを生成しないと３次元モデルにおいて穴が発生してしまう。これを防ぐため，無効ポリゴン判定部３２４の処理の前に，無効と判定された点に新たな座標値を設定するものである。
【００３３】
新たな座標値の設定に関しては，周囲に存在する点の３次元座標値を用いて補間を行い，その座標を無効と判定された点の３次元座標として設定する。補間の方法については２次元座標における最近接点の座標を用いる，複数の近接点から内挿，外挿を行うことによる，などの手法を用いることができる。
【００３４】
無効ポリゴン判定部３２４は，点群データ取得部（３次元座標取得装置）３１から得られた３次元座標値および座標補間部３２３により新たに設定された座標値を基に，ポリゴン化部３２１により生成された各ポリゴンの無効判定を行う。
【００３５】
対象物上に実際には面が存在しない場合，３次元座標値はまったく測定されないか，あるいは２次元座標において近傍に存在する点群とはその座標値が著しく異なる座標値を有することが多い。前者は，先の特許第３４８２９９０号公報に開示されているようなアクティブ手法において，背景に暗幕を配置して測定を行ったような場合である。また後者に関しては，複数の物体を測定対象とした場合である。
【００３６】
その一方で対象物上に面が存在する場合，その周辺においては測定される三次元座標は密に存在し，したがってその座標値も大きくは変化しない。この性質を利用すると，対象物上に実際に面が存在する領域のポリゴンはある所定の閾値以下の大きさを有しているとすることができる。したがって，ポリゴンの１辺の長さ（最小の辺の長さ）あるいは面積を用いて，そのポリゴンが実際には対象物が存在しない領域に相当する，すなわち無効なポリゴンであると判定することができる。ポリゴンの三辺の和や，ポリゴンを含む長方形のアスペクト比等（長辺を短辺で割ったもの）を用いても良い。
【００３７】
無効接続情報削除部３２５は，無効と判定されたポリゴンを発生させた接続情報を仮のポリゴン生成用接続情報から削除して，新たな仮のポリゴン生成用接続情報とする。
【００３８】
点群およびポリゴンの無効の判断は，無効と判定される点群およびポリゴンが存在しなくなるまで，繰り返し行なわれる。場合によっては，上限の繰り返し回数を設定したり，収束条件を判断したりして，繰り返しを終了させても良い。
【００３９】
典型的には，無効と判定される点群およびポリゴンが存在しなくなった時点でのポリゴン生成用接続情報を最終ポリゴン生成用接続情報とする。繰り返しの作業が必要となるのは，無効な点群あるいはポリゴンが存在する場合，その座標値がその近辺の点群あるいはポリゴンに対する判定値に影響を及ぼすためである。すなわち，本来は無効な点群あるいはポリゴンであるにもかかわらず繰り返しの途中においては無効と判定できなかった可能性があるためである。したがって，いったん無効と判定される点群およびポリゴンを処理した後に繰り返し無効判定を行う必要がある。
【００４０】
つぎに，図３および図４のフローチャートを参照して本実施例の３次元モデル生成装置の動作について説明する。なお，点群データ取得部３１が，第１撮像カメラ１０および第２撮像カメラ２０の撮像画像中における画素位置，すなわち２次元の座標値を基にして三角測量法に従って３次元座標をすでに算出しているものとする。
【００４１】
図３において，この２次元の座標値を用いて三角形網を生成し，仮のポリゴン生成用接続情報とする（Ｓ１１）。先に述べたようにポリゴン生成用接続情報とは，どの３つの３次元座標点を接続してポリゴンを構築すればよいかという情報であり，具体的な三角形網の生成手法としては，例えば前述のＤｅｌａｕｎａｙ法を用いる。
【００４２】
つぎに，無効とみなすポリゴンをポリゴン生成用接続情報から除去し，最終ポリゴン生成用接続情報を生成する（Ｓ１２）。このステップにおいてノイズ点および本来対象物上にはないポリゴンの除去を行い，最終的な３次元モデルの品質の低下を防ぐことができる。
【００４３】
ここでステップＳ１２の詳細を図４を参照して説明する。なお，この処理により，図１に示す物体（対象物）４０におけるポリゴンの変化を図６に模式的に示す。
【００４４】
図４において，まず，仮のポリゴン生成用接続情報を基に３次元座標点群を接続し，ポリゴンを生成する（Ｓ２１）。前述した通り，ポリゴン生成用接続情報から，その画素位置に対応する３次元座標をポリゴンの各頂点と設定することでこのステップを行うことができる。
【００４５】
つぎに，与えられた３次元座標点群のおのおのに対して無効であるかどうかを判定する（Ｓ２２）。対象物の撮像画像から三角測量を原理として３次元座標を取得した際，対応点の誤りからノイズ点が発生する場合がある。このようなノイズ点は対象物の実際の３次元座標ではない上，後述する処理ステップＳ２４での無効ポリゴンの判定に対しても悪影響を及ぼす。したがって，最終的な３次元モデルには反映されないように無効点群として処理ステップＳ２４を行う前に処理する必要がある。
【００４６】
判定方法については，すでに説明したように，３次元座標取得用の装置の測定範囲のワーキングエリアを基準にしたり，孤立点の弁別を用いたりすることができる。
【００４７】
つぎに，無効と判定された点群に対して近傍の無効と判定されていない点群の座標値を用いて補間された座標値を新たに設定する（Ｓ２３）。すでに述べたように，無効と判定された点を単に削除した後にポリゴンを生成すると，図７に示すようにその点近傍において生成されるポリゴンが大きくなってしまい，後続のステップＳ２４で誤って無効ポリゴンと判定してしまい，３次元モデルに偽の穴が発生してしまうおそれがあるからである。これを防ぐため，処理ステップＳ２４を行う前に無効と判定された点に新たな座標値を設定する。
【００４８】
新たな座標値の設定には記述のとおり種々の補間を採用できる。
【００４９】
つぎに，点群データ取得部３１から得られた３次元座標値およびステップＳ２３において新たに設定された座標値を基に，ステップＳ２１で生成された各ポリゴンの無効判定を行う（Ｓ２４）。
【００５０】
上述のとおり，この例では，対象物上に面が存在する場合，その周辺においては測定される三次元座標は密に存在し，したがってその座標値も大きくは変化しないという性質を利用して，対象物上に実際に面が存在する領域のポリゴンはある所定の閾値以下の大きさを有していると仮定して，ポリゴンの有効・無効を判定する。
【００５１】
つぎに，無効と判定されたポリゴンを発生させた接続情報を仮のポリゴン生成用接続情報から削除して，新たな仮のポリゴン生成用接続情報とする（Ｓ２５）。
【００５２】
判断ステップＳ２６においては，無効と判定される点群およびポリゴンが存在しなくなるまで処理ステップＳ２１〜Ｓ２５を繰り返す。無効と判定される点群およびポリゴンが存在しなくなった時点でのポリゴン生成用接続情報を最終ポリゴン生成用接続情報とする。
【００５３】
繰り返しの作業が必要となるのは，上述のとおり，無効な点群あるいはポリゴンが存在する場合，その座標値がその近辺の点群あるいはポリゴンに対する判定値に影響を及ぼすためである。誤差を共用すれば，上述のとおり，繰り返し回数の上限等を設定して終了条件としても良い。
【００５４】
ステップＳ２６で繰り返しの終了が判別されると，図３のステップＳ１３に進み，最終ポリゴン生成用接続情報を基にして前記点群を三角形ポリゴン化して最終的な３次元モデルとする。
【００５５】
以上で実施例の説明を終了する。
【図面の簡単な説明】
【００５６】
【図１】本発明の実施例の３次元モデル生成装置の構成を説明する図である。
【図２】上述実施例の要部の構成例を説明するブロック図である。
【図３】上述実施例の全体の動作を説明するフローチャートである。
【図４】図３の一部の処理ステップ（無効ポリゴン除去）の詳細を説明するフローチャートである。
【図５】三角形分割にＤｅｌａｕｎａｙ法を用いた場合の分割模式図である。
【図６（Ａ）】無効ポリゴン除去ステップにおける生成ポリゴン（ポリゴン化）の模式図である。
【図６（Ｂ）】無効ポリゴン除去ステップにおける生成ポリゴン（無効点群判定）の模式図である。
【図６（Ｃ）】無効ポリゴン除去ステップにおける生成ポリゴン（座標補間）の模式図である。
【図６（Ｄ）】無効ポリゴン除去ステップにおける生成ポリゴン（無効ポリゴン判定）の模式図である。
【図６（Ｅ）】無効ポリゴン除去ステップにおける生成ポリゴン（無効ポリゴンの接続情報除去）の模式図である。
【図７】上述実施例により無効点を除去した場合のポリゴン生成模式図である。
【符号の説明】
【００５７】
１０      第１撮像カメラ
２０      第２撮像カメラ
３０      パーソナルコンピュータ
３１      点群データ取得部
３２      仮接続情報生成部
３３      最終接続情報生成部
３４      ポリゴン化部
４０      被写体
３２１      ポリゴン化部
３２２      無効点群判定部
３２３      座標補間部
３２４      無効ポリゴン判定部
３２５      無効接続情報削除部
【図２】
2006065472.tif 000003
【図３】
2006065472.tif 000004
【図４】
2006065472.tif 000005
【図１】
2006065472.tif 000006
【図５】
2006065472.tif 000007
【図６（Ａ）】
2006065472.tif 000008
【図６（Ｂ）】
2006065472.tif 000009
【図６（Ｃ）】
2006065472.tif 000010
【図６（Ｄ）】
2006065472.tif 000011
【図６（Ｅ）】
2006065472.tif 000012
【図７】
2006065472.tif 000013