(57)【要約】【課題】ポリゴンメッシュに対して画像の境界と一致するポリラインを容易に設定すること【解決手段】ポリゴンメッシュで構成される３次元データへのポリラインの設定方法であって、ポリゴンメッシュとの位置情報の対応が既知の画像ＦＴを準備するステップと、画像ＦＴ上に２次元のポリラインＰＬＳを設定するステップと、設定された２次元のポリラインＰＬＳに対応した位置にポリゴンメッシュＰＭを構成するポリゴンのエッジが存在するように、ポリゴンメッシュＰＭを編集して３次元のポリラインＰＬＴを設定するステップとを有する。【選択図】　　　図２
2004062637.tif 000002
【特許請求の範囲】
【請求項１】
ポリゴンメッシュで構成される３次元データへのポリラインの設定方法であって、
前記ポリゴンメッシュとの位置情報の対応が既知の画像を準備するステップと、
前記画像上に２次元のポリラインを設定するステップと、
設定された２次元のポリラインに対応した位置に前記ポリゴンメッシュを構成するポリゴンのエッジが存在するように、前記ポリゴンメッシュを編集して３次元のポリラインを設定するステップと、
を有することを特徴とする３次元データへのポリラインの設定方法。
【請求項２】
前記画像が複数準備されており、
前記ポリゴンメッシュに対応する同じ位置に対して複数の前記画像上にそれぞれ２次元のポリラインが設定された場合に、それぞれの２次元のポリラインから導かれる複数の３次元のポリラインを１つに統合するステップを有する、
請求項１記載の３次元データへのポリラインの設定方法。
【請求項３】
ポリゴンメッシュで構成される３次元データへのポリラインの設定装置であって、
前記ポリゴンメッシュとの位置情報の対応が既知の画像上に２次元のポリラインを設定する第１の手段と、
設定された２次元のポリラインに対応した位置に前記ポリゴンメッシュを構成するポリゴンのエッジが存在するように、前記ポリゴンメッシュを編集して３次元のポリラインを設定する第２の手段と、
を有することを特徴とする３次元データへのポリラインの設定装置。
【請求項４】
前記第２の手段は、
前記画像上に前記ポリゴンメッシュを投影する手段と、
前記画像上において、投影されたポリゴンのエッジと前記ポリラインとの交点を求める手段と、
前記交点がポリゴンの頂点となるように、新たなポリゴンを生成しまたは元のポリゴンを移動する手段と、
を有することを特徴とする請求項３記載の３次元データへのポリラインの設定装置。
【請求項５】
ポリゴンメッシュで構成される３次元データへのポリラインの設定のためのコンピュータプログラムであって、
前記ポリゴンメッシュとの位置情報の対応が既知の画像上に２次元のポリラインを設定する処理と、
設定された２次元のポリラインに対応した位置に前記ポリゴンメッシュを構成するポリゴンのエッジが存在するように、前記ポリゴンメッシュを編集して３次元のポリラインを設定する処理と、
をコンピュータに実行させるためのコンピュータプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、３次元データへのポリラインの設定方法および装置ならびにコンピュータプログラムに関する。
【０００２】
【従来の技術】
従来より、対象物の３次元モデルを生成するために、対象物の３次元計測がしばしば行われる。つまり、３次元計測によって、例えば３次元上の点群からなる３次元データが得られ、これに基づいてポリゴンメッシュからなる３次元データが生成される。その３次元データに、対象物を撮影して得られた画像をマッピング（テクスチャマッピング）することによって３次元モデルが生成される。
【０００３】
テクスチャマッピングを行うに当たって、画像上における模様や明暗などの境界と３次元データのポリゴン間の境界（つまりエッジ）とが一致することが好ましい。しかし、通常、それらは一致しないため、何らかの補正処理が必要である。
【０００４】
従来においては、テクスチャとして用いる画像を見ながら、３次元データ上の適当な位置にライン（ポリライン）を引き、そのラインに基づいてポリゴンを分割し、そのラインをエッジとする新たなポリゴンを生成していた。
【０００５】
【発明が解決しようとする課題】
しかし、上に述べた従来の方法によると、画像と見比べながら、３次元データのどの辺りにラインを引けばよいかを考える必要がある。したがって、ラインを引くのに時間を要し、時間をかけても完全に一致させることは困難である。その上、処理対象のポリゴンをユーザが逐一選択する必要があり、ユーザの負担が大きい。
【０００６】
画像上の境界とポリゴンメッシュの境界（ポリライン）とが一致しない場合には、１つのポリゴンに２種類の色または模様が乗ってしまい、画像の境界部分で色がぼやけてしまう。そのため、できあがった３次元モデルの全体を見たときの印象が悪くなる。また、境界を挟む両側の面において互いに異なる処理を行うことがあるが、ポリラインが真っ直ぐでない場合には、例えば片側の面で平滑化処理を行うとエッジが丸くなってしまうという問題もある。
【０００７】
本発明は、上述の問題に鑑みてなされたもので、ポリゴンメッシュに対して画像の境界と一致するポリラインを容易に設定する方法および装置ならびにコンピュータプログラムを提供することを目的とする。
【０００８】
【課題を解決するための手段】
本発明に係る方法によると、ポリゴンメッシュで構成される３次元データへのポリラインの設定方法であって、前記ポリゴンメッシュとの位置情報の対応が既知の画像を準備するステップと、前記画像上に２次元のポリラインを設定するステップと、設定された２次元のポリラインに対応した位置に前記ポリゴンメッシュを構成するポリゴンのエッジが存在するように、前記ポリゴンメッシュを編集して３次元のポリラインを設定するステップとを有する。
【０００９】
また、前記画像が複数準備されており、前記ポリゴンメッシュに対応する同じ位置に対して複数の前記画像上にそれぞれ２次元のポリラインが設定された場合に、それぞれの２次元のポリラインから導かれる複数の３次元のポリラインを１つに統合するステップを有する。
【００１０】
本発明に係る装置によると、前記ポリゴンメッシュとの位置情報の対応が既知の画像上に２次元のポリラインを設定する第１の手段と、設定された２次元のポリラインに対応した位置に前記ポリゴンメッシュを構成するポリゴンのエッジが存在するように、前記ポリゴンメッシュを編集して３次元のポリラインを設定する第２の手段とを有する。
【００１１】
【発明の実施の形態】
図１は本発明の実施形態に係る３次元モデルの編集装置１のブロック図である。
【００１２】
図１において、編集装置１は、装置本体１０、磁気ディスク装置１１、媒体ドライブ装置１２、ディスプレイ装置１３、キーボード１４、およびマウス１５などからなる。
【００１３】
装置本体１０は、ＣＰＵ、ＲＡＭ、ＲＯＭ、ビデオＲＡＭ、入出力ポート、各種コントローラ、各種インタフェースなどからなる。ＲＡＭおよびＲＯＭなどに記憶されたプログラムをＣＰＵが実行することにより、以下に説明する種々の機能が実現される。
【００１４】
磁気ディスク装置１１には、ＯＳ（Ｏｐｅｒａｔｉｎｇ　Ｓｙｓｔｅｍ）　、３次元モデル（３次元形状モデル）ＭＬを生成しまたはテクスチャマッピングを行うためのモデリングプログラムＰＲ、その他のプログラム、入力されまたは生成された３次元データ（３次元形状データ）ＤＴ、画像（２次元画像データ）ＦＴ、生成された３次元モデルＭＬ、その他のデータなどが格納されている。これらのプログラムおよびデータは、適時、装置本体１０のＲＡＭにローディングされる。
【００１５】
なお、モデリングプログラムＰＲには、初期化処理、ポリライン設定処理、投影処理、ポリゴンメッシュ編集処理（位相編集処理）、ポリライン統合処理、マッピング処理、およびその他の処理のためのプログラムが含まれる。
【００１６】
媒体ドライブ装置１２は、ＣＤ−ＲＯＭ（ＣＤ）、フロッピィディスクＦＤ、光磁気ディスク、コンパクトフラッシュ（登録商標）などの半導体メモリＨＭ、その他の記録媒体にアクセスし、データまたはプログラムの読み書きを行う。記録媒体の種類に応じて適切なドライブ装置が用いられる。上に述べたモデリングプログラムＰＲは、これら記録媒体からインストールすることも可能である。３次元データＤＴおよび画像ＦＴなども記録媒体を介して入力することが可能である。
【００１７】
ディスプレイ装置１３の表示面ＨＧには、上に述べた種々のデータ、３次元データＤＴ、画像ＦＴ、モデリングプログラムＰＲによる処理過程の画像、生成された３次元モデルＭＬ、その他の画像またはデータが表示される。
【００１８】
キーボード１４およびマウス１５は、ディスプレイ装置１３に表示された画像ＦＴおよび３次元データＤＴに対して、ユーザが種々の指定を行うために用いられる他、装置本体１０に種々のデータを入力しまたは指令を与えるために用いられる。
【００１９】
装置本体１０には、対象物をその周囲の種々の位置から撮影して画像ＦＴを得るためのデジタルカメラを接続することが可能である。また、対象物を撮影してその３次元データＤＴを入力するための３次元計測装置を接続することも可能である。このような３次元計測装置は、例えば光切断法によって対象物の３次元データＤＴを非接触で計測する。また、３次元計測装置から、３次元データＤＴではなく、３次元データＤＴを生成するための元となるデータを出力し、装置本体１０によって３次元データＤＴを演算によって求めるようにしてもよい。このような３次元データＤＴまたはこれを加工したデータも、本発明における初期状態の３次元データとして用いることが可能である。
【００２０】
なお、デジタルカメラで得られた画像ＦＴ上の各画素の座標と、３次元計測によって得られた３次元データＤＴに基づくポリゴンメッシュＰＭ上の各頂点の位置情報との対応がとれるようになっている。そのために、デジタルカメラおよび３次元計測装置には、その位置および姿勢を検出して位置姿勢情報を出力する位置姿勢センサが設けられる。また、３次元計測装置それ自体によって、３次元データＤＴと画像ＦＴとを取得することも可能である。その場合には、３次元計測装置の内部パラメータによって、３次元データＤＴと画像ＦＴとの位置関係が規定され、または射影行列が生成される。
〔位相編集の概要〕
図２は編集装置１における位相編集の概念を示す図である。
【００２１】
位相編集においては、３次元データＤＴのポリゴンメッシュＰＭとの対応が既知である画像ＦＴ上で、　２次元のポリラインＰＬＳを設定し、　設定したポリラインＰＬＳをポリゴンメッシュＰＭに反映させる。
【００２２】
すなわち、図２において、対象物Ｑを撮影した画像ＦＴと３次元データＤＴのポリゴンメッシュＰＭとは互いの位置関係が既知である。そのためには、例えば、画像ＦＴについて射影行列からなるデータセットのようなものが得られていればよい。画像ＦＴにおいて、対象物Ｑの手前の矩形の面上で対角線を境界とする濃淡模様が表示されている。その対角線を２次元のポリラインＰＬＳとして設定する。ポリラインＰＬＳの設定は、コンピュータが模様などを認識するようにして自動的に行ってもよく、ユーザが画面上で指定することにより手動で行ってもよい。そして、２次元のポリラインＰＬＳを、ポリゴンメッシュＰＭに反映させる。ポリゴンメッシュＰＭ上のポリラインＰＬＴに対して、ポリゴンのエッジが一致するように、ポリゴンメッシュＰＭを編集する。その際の編集方法として、元のポリゴンをポリラインＰＬＴにより分割して新たなエッジを生成する方法、元のポリゴンの頂点を移動してエッジを移動する方法、それらを混合した方法などがある。これによって、ポリゴンメッシュＰＭ上に３次元のポリラインＰＬＴが設定される。
【００２３】
なお、画像ＦＴとして、１枚の画像ＦＴを用いる場合、２枚以上の複数の画像ＦＴを用いる場合がある。複数の画像ＦＴを用いる場合には、それらの境界部分においてそれぞれの画像ＦＴ上で設定されたポリラインＰＬＳをポリゴンメッシュＰＭ上で統一する処理を行う。
【００２４】
編集装置１の位相編集方法によると、ユーザは、画像情報を用いてポリゴンメッシュの位相の編集を行うことができる。また、発生させたポリラインＰＬＳは、　種々の後処理において有用な情報として扱うことが可能である。なお、本明細書において、「ポリライン」の語句は、単に線分のみを指すのではなく、当該ポリラインの属性を含む種々の情報、つまりポリライン情報を指すものとして使用する。但し、図面の説明などにおいて、線分を指して「ポリライン」と記載することがある。以下において更に詳しく説明する。
〔ポリゴンの分割によるポリラインの設定〕
まず、ポリゴンＰＧを分割することによってポリラインを設定する方法を説明する。
【００２５】
ここでは、ポリゴンメッシュＰＭとして、３角形（３角パッチ）のみで構成されているものを想定する。画像ＦＴは１枚だけ存在すると仮定する。
図３はポリラインＰＬＳの例を示す図、図４は画像ＦＴ上に投影されたポリゴンメッシュＰＭの例を示す図、図５はポリゴンの分割方法を説明するための図、図６は分割されたポリゴンＰＧの連結関係を説明するための図である。
【００２６】
まず、画像ＦＴ上に２次元のポリラインＰＬＳを設定する。
図３に示すように、ポリラインＰＬＳは、始点ＰＳ、節点ＰＮ、および終点ＰＥを決定することにより設定される。始点ＰＳおよび終点ＰＥは、ポリラインＰＬＳの端点を示す。節点ＰＮは、始点ＰＳと終点ＰＥとの間の折れ線を決定する各線分の端点である。−方の端転として始点ＰＳを設定し、始点ＰＳから順に節点ＰＮを設定し、他方の端点として終点ＰＥを設定することにより、ポリラインＰＬＳが定義される。ポリラインＰＬＳの設定動作を複数回繰り返すことにより、複数のポリラインＰＬＳを１つの画像ＦＴ上に設定することができる。始点ＰＳおよび終点ＰＥの設定方法によっては、分岐を有するポリラインＰＬＳ、または閉ループを構成するポリラインＰＬＳを設定することも可能である。
【００２７】
次に、図４に示すように、ポリラインＰＬＳを設定した画像ＦＴ上に、ポリゴンメッシュＰＭを投影する。ポリゴンメッシュＰＭの投影に際して、画像ＦＴ上で陰面に当たる部分は投影しない。
【００２８】
そして、画像ＦＴ上における、投影されたポリゴンメッシュＰＭを構成する各ポリゴンＰＧのエッジと、ポリラインＰＬＳを構成する各線分と、の交点の座標を算出する。
【００２９】
図５において、ポリゴンメッシュＰＭのポリゴンＰＧ１は、３つの頂点（構成点）Ｖ１，Ｖ２，Ｖ３から構成される。ポリゴンＰＧ１を画像ＦＴに投影することによって、頂点Ｖ１〜３に対応する画像ＦＴ上の座標位置が、画像ＦＴにおける頂点Ｖ１〜３として求まる。
【００３０】
画像ＦＴ上において、投影されたポリゴンＰＧのエッジＥＳ１，ＥＳ２が、交点ＣＳ１，ＣＳ２において、ポリラインＰＬＳ１と交差する。ポリラインＰＬＳ１は、その端点の座標がＰ１，Ｐ２である。そこで、交点ＣＳ１，ＣＳ２の座標を求める。
【００３１】
まず交点ＣＳ１の求め方について説明する。画像ＦＴ上におけるエッジＥＳ１は、その両端の頂点Ｖ１〜２によって定義される。交点ＣＳ１の座標は、次の（１）式によって示される。
【００３２】
2004062637.tif 000003
但し、ｔはエッジＥＳ１を内分する割合
ｓはポリラインＰＬＳ１を内分する割合
そして、（１）式から得られる次の関係、
ｔ・Ｖ１＋（１−ｔ）・Ｖ２＝ｓ・Ｐ１＋（１−ｓ）・Ｐ２
から、ｔ、ｓを求める。
【００３３】
求められたｔの値を、ポリゴンメッシュＰＭのポリゴンＰＧのエッジＥＴ１に適用することにより、ポリラインＰＬＳをポリゴンメッシュＰＭに投影した場合におけるエッジＥＴ１との交点ＣＴ１を、次の（２）式により求める。
【００３４】
ＣＴ１＝ｔ・Ｖ１＋（１−ｔ）・Ｖ２　　　……（２）
同様に、交点ＣＳ２を求め、それに対応する交点ＣＴ２を求める。
なお、ここで求められる交点ＣＴは近似解である。より厳密に求めるには、　視点位置から点Ｐ１，Ｐ２を通る２つの３次元ベクトルで決定される平面とポリゴンメッシュＰＭとの交点を計算するのがよい。
【００３５】
ここで、　２次元のポリライン情報を構成する各節点ＰＮについては、ポリゴンメッシュＰＭと画像ＦＴとに対応する射影行列を元に、２次元から３次元に変換するための変換マップを作成しておき、ポリゴンメッシュＰＭ上の３次元座標に変換する。その際に、投影先のポリゴンＰＧのＩＤ（ポリゴンＩＤ）も得るようにしておく。
【００３６】
さて、投影されたポリゴンメッシュＰＭの全てのエッジＥＳについて交点ＣＳの計算を行った後、画像ＦＴ上のポリラインＰＬＳと交点ＣＳをもつエッジＥＳを構成要素とするポリゴンＰＧ、および、節点ＰＮが投影されるポリゴンＰＧについて、それらポリゴンＰＧの分割に必要な情報を整理し、ポリゴンメッシュＰＭにおけるポリゴンＰＧ上での交点ＣＴと節点ＰＮとの間の連結関係を定義する。
【００３７】
交点ＣＴおよび節点ＰＮの連結関係を定義した後で、ポリゴンＰＧのエッジＥＴの情報のうち、交点ＣＴが存在するエッジＥＴについて、　頂点Ｖの連結関係を更新する。その場合に、分割後のポリゴンメッシュＰＭが３角形のみで構成される必要があれば、既存の連結関係と交差しないように新たな連結関係を定義することもできる。このようにして連結関係を更新した後で、最新の連結関係に基づいてポリゴンＰＧを分割する。
【００３８】
図６に示されるポリゴンＰＧ１について、その連結関係を具体的に説明する。図６に示す元の１つのポリゴンＰＧ１の連結関係は、３つの頂点の関係、つまり、Ｖ１−Ｖ２、Ｖ２−Ｖ３、Ｖ３−Ｖ１によって示される。
【００３９】
ポリゴンＰＧ１は、折れ曲がったポリラインＰＬＳの各線分ＰＬＳ２，３によって分割される。その連結関係は、ポリラインＰＬＳとポリゴンＰＧ１のエッジＥＴとの交点ＣＴ、およびポリラインＰＬＴの節点ＰＮとの関係、つまり、Ｖ１−ＣＴ１、ＣＴ１−Ｖ２、Ｖ２−Ｖ３、Ｖ３−ＣＴ２、ＣＴ２−Ｖ１、ＣＴ１−ＰＮ、ＰＮ−ＣＴ２によって示される。
【００４０】
さらに、ポリゴンメッシュＰＭが３角形のみで構成される場合には、次の連結関係が追加される。つまり、図６に破線で示されるように、ＰＮ−Ｖ１、ＰＮ−Ｖ２、ＰＮ−Ｖ３の連結関係が追加される。これによって、元の１つのポリゴンＰＧ１は、５つの小さなポリゴンＰＧ１１〜１５に分割されることとなる。なお、節点ＰＮがポリゴンＰＧ内にない場合には、通常、３つのポリゴンに分割される。
【００４１】
このような処理によって、ポリラインＰＬＴは、分割されたポリゴンＰＧのいずれかのエッジＥＴと一致することとなる。つまり、２次元のポリラインＰＬＳと投影面（画像面）上で一致するポリラインＰＬＴを、ポリゴンメッシュＰＭ上に生成し設定することができる。
【００４２】
ところで、ポリラインＰＬＴによってポリゴンＰＧを分割していくと、微小なポリゴンＰＧが多数発生する。解像度が一様なポリゴンメッシュ内で微小なポリゴンが発生すると、解像度の−様性が崩れてしまう。さらには、ポリラインＰＬＴを生成した後の処理においても、扱い難いポリゴンメッシュとなってしまうおそれがある。
【００４３】
そこで、そのような微小なポリゴンを削除するための微小エッジの縮退処理について、次に説明する。
〔微小エッジの縮退方法〕
図７はポリゴンメッシュＰＭの縮退処理を説明するための図である。
【００４４】
まず、微小エッジであるか否かの判定のための閾値δｅを設定する。閾値δｅの値としては解像度に依存する値が考えられる。
閾値δｅを用いて、　分割によって発生した全てのポリゴンＰＧのエッジＥＴ（Ｖａ，Ｖｂ）について、その長さ｜Ｖａ−Ｖｂ｜を求め、それが閾値δｅ以下である場合には微小エッジであると判断する。つまり、次の（３）式、
δｅ＞｜Ｖａ−Ｖｂ｜　……（３）
を満たすエッジＥＴを微小エッジとして検出する。
【００４５】
そして、検出された微小エッジについては、エッジの縮退処理を行う。縮退処理は、エッジＥＴの状況によって２種類に分けられる。
縮退処理の１つは、エッジＥＴを構成する２つの頂点がポリラインＰＬＴ上の点であった場合である。この場合には、２つの頂点がポリラインＰＬＴを構成する線分のうち同一の線分上に存在する場合にのみ、縮退処理を行う。それ以外の場合は、２つの頂点を縮退することによってポリラインＰＬＳを設定した画像ＦＴ上でのポリラインＰＬＳの直線性が失われてしまうおそれがあるため、縮退処理を行わない。
【００４６】
縮退方法としては、　一方の頂点の座標を他方の頂点の座標に置き換える、または、２つの頂点の中点を計算し、両方の頂点の座標を中点の座標に置き換える、といった方法が考えられる。
【００４７】
縮退処理の他の１つは、一方の頂点のみがポリライン上に存在し、他の頂点はポリライン上に存在しない場合である。この場合には、ポリライン上の頂点の座標を変更するような縮退処理は、ポリラインを設定した画像ＦＴ上でのポリラインＰＬＳの直線性を失ってしまうおそれがあるため、避けねばならない。したがってこの場合には、ポリライン上に存在しない他方の頂点の座標をポリライン上に存在する頂点の座標で置き換えてしまうような縮退方法を取る必要がある。
【００４８】
このような縮退処理の例が図７に示されている。ちなみに、２つの頂点ともポリライン上に存在しない場合も考えられるが、　この場合は、　ポリラインの設定前のポリゴンメッシュのエッジであり、　縮退の必要はないと考えられる。
【００４９】
図８は分割によるポリラインの設定処理を示すフローチャートである。
図８において、画像ＦＴ上に２次元のポリラインＰＬＳを設定する（＃１１）。画像ＦＴ上に投影されたポリゴンメッシュＰＭに対して、ポリラインＰＬＳとの交点を算出する（＃１２）。ポリゴンＰＧのエッジＥＴに関連した連結関係を定義する（＃１３）。連結関係に基づいてポリゴンＰＧを分割する（＃１４）。微小エッジの縮退を行う（＃１５）。
【００５０】
次に、ポリゴンＰＧの分割によらず、ポリゴンＰＧの頂点の選択によってポリラインを設定する方法について説明する。
〔ポリゴン頂点の選択によるポリラインの設定〕
図９はポリゴン頂点の選択により設定されたポリラインＰＬＴを示す図である。
【００５１】
ここでは、　画像ＦＴ上に設定した２次元のポリラインＰＬＳを元に、ポリゴンメッシュＰＭ中のポリゴンＰＧの頂点を選択し、３次元のポリラインＰＬＴとして設定する方法について述べる。
【００５２】
上に述べたポリゴンの分割によるポリライン設定の場合と同様に、ポリゴンメッシュＰＭを画像ＦＴ上に投影するところまでの処理を行う。これによって、図４に示すような状態となる。
【００５３】
その後、ポリライン構成点の検出を行う。すなわち、投影されたポリゴンメッシュＰＭのエッジと、２次元のポリラインＰＬＳの各線分との間で、交差があるか否かの交差判定を行う。交差判定の結果、交差していると判定されたエッジの構成点のうち、投影点がポリラインＰＬＳの線分に近い方の点をポリラインＰＬＴの構成点として検出する。
【００５４】
この処理を、投影されたポリゴンメッシュＰＭの全てのエッジについて行い、２次元ポリライン情報に対応するポリゴン頂点を検出し、　ポリライン構成点とする。次に、ポリライン構成点の移動を行う。
【００５５】
すなわち、上のように検出されたポリライン構成点は、ポリゴンの頂点であり、画像ＦＴ上に投影しても、２次元のポリラインＰＬＳの近傍には投影されるがポリラインＰＬＳと一致することは少ない。そこで、ポリライン構成点の投影結果が２次元のポリラインＰＬＳと一致するよう、ポリライン構成点を移動させる。
【００５６】
まず、ポリライン構成点を画像ＦＴ上に投影する。投影前のポリライン構成点をｐとし、投影されたポリライン構成点をＰとする。ポリライン構成点が関連付けられている２次元のポリラインＰＬＳを構成する線分Ｌとの距離Ｄを計算する。そして、画像ＦＴの平面上で、線分Ｌと垂直な方向の単位ベクトルｅ計算する。ポリライン構成点Ｐに、ベクトル（Ｄ・ｅ）を加えて移動し、線分Ｌ上にポリライン構成点Ｐを移動する。これにより、ポリライン構成点Ｐは、線分Ｌに対して垂直な方向つまり最短距離の位置に移動する。移動後のポリライン構成点をＰ’とする。ポリライン構成点Ｐ’は線分Ｌ上にある。そして、ポリライン構成点Ｐ’の位置に相当するポリゴン上の座標を計算し、ポリライン構成点ｐの座標値を書き換える。
【００５７】
この処理を全てのポリライン構成点について行うことにより、図９に示すように、ポリライン構成点の投影結果を２次元のポリラインＰＬＳと一致させることができる。
【００５８】
図１０はポリゴン頂点の選択によるポリラインの設定処理を示すフローチャートである。
図１０において、画像ＦＴ上に２次元のポリラインＰＬＳを設定する（＃２１）。ポリライン構成点の検出を行う（＃２２）。検出したポリライン構成点を移動する（＃２３）。
【００５９】
次に、属性を持ったポリラインＰＬＳを設定する方法について説明する。
〔属性を用いたポリラインの設定〕
画像ＦＴにポリラインＰＬＳを設定する際に、ポリラインＰＬＳに属性を持たせることにより、属性に応じた処理を実行することができる。ここでは、ポリゴンメッシュＰＭのポリラインに設定することによって効果が得られると考えられる２つの属性について、その効果を説明する。
【００６０】
その１つは、例えば６面体の稜線のようなジオメトリエッジである。ジオメトリエッジは、ポリゴンメッシュＰＭのうちで、　幾何形状特徴が顕著な部分に設定されるポリラインの属性として使用する。ポリラインにこの属性を付加することにより、ユーザが画像ＦＴ上で設定した２次元のポリラインＰＬＳと、ポリゴンメッシュＰＭの幾何特徴情報とを併用し、より望ましい位置にポリラインＰＬＳを設定することができる。
【００６１】
他の１つは、テクスチャエッジである。テクスチャエッジは、画像ＦＴ上の色境界にあたるポリラインであることを示す属性として使用する。ポリラインにこの属性を付加することにより、ユーザが画像ＦＴ上で設定した２次元のポリラインＰＬＳと、画像ＦＴに対するエッジ抽出処理の結果を併用し、より望ましい位置にポリラインを設定することができる。
〔複数の画像を使用するポリラインの設定〕
次に、複数の画像ＦＴにポリラインＰＬＳを設定し、これらに基づいてポリゴンメッシュＰＭにポリラインＰＬＴを設定する場合について説明する。
【００６２】
ここでは、ポリゴンメッシュＰＭに複数の画像ＦＴが対応付けられている場合に、各画像ＦＴに設定された２次元のポリラインＰＬＳを用いて、ポリゴンメッシュＰＭにポリラインＰＬＴを設定する方法について説明する。
【００６３】
２次元のポリラインＰＬＳをポリゴンメッシュＰＭに反映させる基本的なアルゴリズムは、上に述べたとほぼ同じである。ここでは、複数の画像ＦＴを用いてポリラインＰＬＴを設定する際の特有の問題として、異なる画像ＦＴ上に設定された、同一個所を示す２次元のポリラインＰＬＳの管理方法、および、　複数の画像ＦＴ間での設定位置のずれを防止する方法について説明する。
【００６４】
まず、同一個所を示すポリラインの管理方法について説明する。
複数の画像ＦＴを用いてポリラインを設定する際、別々の画像ＦＴでポリゴンメッシュＰＭの同一個所を示す２次元のポリラインＰＬＳを設定することがある。このように、画像ＦＴの異なる各ポリラインＰＬＳが同一個所についてのものであることを示すため、例えば、ポリラインＰＬＳにＩＤを付加し、同一のＩＤを持つポリライン同士はポリゴンメッシュＰＭの同一個所を示すものとみなす、という管理方法をとることが考えられる。
【００６５】
次に、ポリライン統合処理について説明する。
図１１は複数の画像ＦＴに設定されたポリラインＰＬＳに基づくポリラインＰＬＴの統合処理を示す図である。
【００６６】
複数のポリラインＰＬＳをポリゴンメッシュＰＭに投影した結果、同一個所に複数のポリラインＰＬＴが設定される場合がある。もし、これらのポリラインＰＬＴが同一個所のポリラインＰＬＴであると認識できる場合には、それらを統合して１つのポリラインＰＬＴに纏める。例えば、２つのポリラインＰＬＴが、同一のＩＤを持つ場合、ポリライン間の距離が十分小さい場合などである。
【００６７】
ポリライン統合の処理としては、例えば、２つの同一個所に設定されたポリラインＰＬＴについて、それらの構成点を結ぶようなポリゴンエッジが存在する場合に、一方の構成点の座標を他方の構成点の座標で置き換えるエッジ縮退処理を行う。
【００６８】
図１１（Ａ）においては、同一箇所に２つのポリラインＰＬＴ１，２が設定されている。これら２つのポリラインＰＬＴ１，２間に、それぞれの構成点を結ぶエッジＥＴ３，４…が存在する。それらのエッジＥＴについて、それぞれの一方の構成点ｐｋを移動して他方の構成点ｐｗの位置に合わせる。図１１（Ｂ）に示すように、黒丸の構成点ｐｋが白丸の構成点ｐｗの位置に移動して合わせられている。これによって、１つのポリラインＰＬＴ０に統合され、且つ微小ポリゴンが削減されている。
【００６９】
なお、複数のポリラインＰＬＴのうち、いずれを優先させるかについて、例えば次のような方法がある。
（１）　構成点数の多いポリラインＰＬＴを優先する。
（２）　先に設定されたポリラインＰＬＴを優先する。
〔設定のずれの減少方法〕
次に、複数のポリラインＰＬＳを設定することにともなうずれを減少させる機能について説明する。
【００７０】
複数枚の画像ＦＴを用いて２次元のポリラインＰＬＳを設定する際に、ユーザが同一個所にポリラインＰＬＳを設定したつもりでも、結果として、ポリライン間の相対位置がずれてしまうことがある。これは、ユーザの意図を反映していない結果であるし、また、ポリラインの統合処理の際にも不具合を招きかねない。そこで、ユーザが複数の画像ＦＴにまたがるポリラインＰＬＳを同一個所に設定できるようにし、ポリライン間のずれを減少させるのが望ましい。そのために、適当なユーザインターフェイスが準備されている。
【００７１】
そのようなユーザインターフェイスとして、設定済みのポリラインを表示する機能、カメラパラメータの誤差を修正する機能、３次元モデルを修正する機能などがある。
【００７２】
まず、設定済みのポリラインの表示について説明する。ユーザが、ある個所についての２次元のポリラインＰＬＳをある画像ＦＴで設定したとする。その場合に、２次元のポリラインＰＬＳと同一個所を示すポリラインＰＬＳを他の画像ＦＴで設定する際に、先に設定したポリラインＰＬＳが、現在設定対象となっている画像ＦＴ中でどの位置にくるかを表示する。これによって、ユーザが同一個所に２次元のポリラインＰＬＳを設定することが可能となる。
【００７３】
設定済みのポリラインＰＬＳを表示する手段としては、例えば、先に設定したポリラインＰＬＳの節点ＰＮをポリゴンメッシュＰＭ上に投影し、求められた節点ＰＮの３次元座標を現在設定対象となっている画像ＦＴ上に投影し、投影された節点ＰＮ間を結び、設定済みのポリラインＰＬＳを表示するものを用いる。
【００７４】
図１２は設定済みの２次元ポリラインの表示例を示す。
図１２において、画像ＦＴ３にポリラインＰＬＳ３が設定され、これに基づいてポリゴンメッシュＰＭ１にポリラインＰＬＴ３が設定されている。次に、画像ＦＴ４に新たなポリラインＰＬＳを設定する際に、ポリゴンメッシュＰＭに既に設定されたポリラインＰＬＴについての情報（ポリラインＰＬＳ３）を画像ＦＴ４上に表示する。ポリラインＰＬＳ３を画像ＦＴ４に表示する方法として、例えば、ポリゴンメッシュＰＭ１を画像ＦＴ４上に投影し、画像ＦＴ４上でポリラインＰＬＴ３に対応するポリラインＰＬＳを設定する。
【００７５】
これによって、画像ＦＴ４においてポリラインＰＬＳ３に連続する新しいポリラインＰＬＳ４を設定する際に、ポリゴンメッシュＰＭ上の同一個所に対してずれのないポリラインＰＬＳを容易に設定することができる。
【００７６】
次に、カメラパラメータの誤差の修正について説明する。
ユーザが、複数の画像ＦＴにおいて、同一個所を示す２次元のポリラインＰＬＳをそれぞれ設定したとする。その時点で、　これらのポリラインＰＬＳのポリゴンメッシュＰＭへの投影結果が異なる（つまり投影場所がずれている）　と判明したとする。そうすると、その原因として、画像ＦＴの持っている射影行列の値に誤差が含まれる場合、および、対象物の実際の形状とそれを計測して得られたポリゴンメッシュＰＭの形状とが異なる場合が考えられる。
【００７７】
次に、射影行列に誤差が含まれる場合の対策について説明する。
そのための１つの方法として、ユーザの設定した２次元のポリラインＰＬＳを元に、　キャリブレーションの微調整を行う。微調整の方法として、複数のポリラインＰＬＳのうちから１つを選び、その投影結果の位置に他のポリラインＰＬＳの投影結果が−致するよう、他の画像ＦＴの射影行列を調整する。
【００７８】
例えば、同一個所を指す２つのポリラインＰＬＳが、　それぞれ別の画像ＦＴ上で設定されている場合に、一方のポリラインＰＬＳを基準とし、このポリラインＰＬＳの節点ＰＮをポリゴンメッシュＰＭ上に投影し、節点ＰＮの３次元情報を取得する。そして他方のポリラインＰＬＳをポリゴンメッシュＰＭ上に投影し、先の３次元の節点ＰＮが投影された他方のポリラインＰＬＳ上に存在するように他方のポリラインＰＬＳが設定された画像ＦＴのカメラパラメータを調整する。
【００７９】
この方法の他に、線分の対応を用いたキャリブレーションの方法として、Ｚｈａｎｇ　の「Ｅｓｔｉｍａｔｉｎｇ　Ｍｏｔｉｏｎ　ａｎｄ　Ｓｔｒｕｃｔｕｒｅ　ｆｒｏｍ　Ｃｏｒｒｅｓｐｏｎｄｅｎｃｅｓ　ｏｆ　Ｌｉｎｅ　Ｓｅｇｍｅｎｔｓ　ｂｅｔｗｅｅｎ　Ｔｗｏ　Ｐｅｒｓｐｅｃｔｉｖｅ　Ｉｍａｇｅｓ」（ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｐａｔｔｅｒｎ　Ａｎａｌｙｓｉｓ　ａｎｄ　Ｍａｃｈｉｎｅ　Ｉｎｔｅｌｌｉｇｅｎｃｅ，　１７，　１２，　１９９５．　）　のような方法がある。
【００８０】
さらに他の１つの方法としては、射影行列から得られるカメラパラメータをユーザが修正する方法がある。例えば、画像ＦＴに関連付けられているカメラパラメータを修正するため、各パラメータに対応するスライドバーをもつダイアログをユーザに提供する。ユーザは、そのダイアログを用いてカメラパラメータを修正する。パラメータの修正結果を、例えば上の図１２で説明したように画面上に表示する。また、他の画像ＦＴで設定されたポリラインＰＬＳの表示結果を用いて、その修正の是非を判別できるようにする方法でもよい。これらの方法により、各ポリラインＰＬＳを投影した結果生じるそれらの間のずれを減少させることができる。
【００８１】
次に、３次元モデルの修正について説明する。
複数のポリラインＰＬＳの投影結果が一致しない他の１つの原因として、ポリゴンメッシュＰＭの形状が、対象物の実形状と異なっている場合が挙げられる。これは、通常の３次元デジタイザなどを用いて得られたポリゴンメッシュＰＭでは起こり難いが、ＳＦＳ法（Ｓｈａｐｅ　Ｆｒｏｍ　Ｓｉｌｈｏｕｅｔｔｅ　法）を用いて得られた計測データ、またはＳｕｂｓａｍｐｌｉｎｇ　処理などによって解像度を低くしたポリゴンメッシュＰＭでは起こり得る。このような場合に、ポリゴンメッシュＰＭを修正することにより、投影結果の一致を導くことができる。
【００８２】
ポリゴンメッシュＰＭの修正方法として、ユーザによる手動修正の方法以外に次の方法がある。つまり、ユーザが設定した、同一個所を示す複数のポリラインＰＬＳと、射影行列を用いて線分ベースのステレオ法（例えば上に述べたＺｈａｎｇ　の方法）によるポリラインＰＬＳの３次元位置推定を行い、その結果得られる３次元のポリラインＰＬＴに対し、ポリゴンＰＧの近傍にあたるポリゴンメッシュＰＭをフィッティング（Ｆｉｔｔｉｎｇ　）するという方法である。
〔設定画像教示方法〕
次に、複数の画像ＦＴを用いて同一個所の２次元のポリラインＰＬＳを設定する際に、一番最後に設定したポリラインＰＬＳに続く、他の画像ＦＴ上でポリラインＰＬＳを設定したいという状況が生じる。その場合に、ポリゴンメッシュＰＭに割り当てられている画像ＦＴの枚数が増加すると、ユーザが逐一画像ＦＴを見て、次にどの画像ＦＴにポリラインＰＬＳを設定すればよいのかを判断する必要があり、その判断に時間を要することとなる。
【００８３】
そこで、続きを設定したい、設定済みのポリラインＰＬＳをヒントにして、そのポリラインＰＬＳに続くポリラインＰＬＳを設定するのに適している画像ＦＴをユーザに提示する。これによってユーザの負担の軽減が図られる。
【００８４】
また、複数の画像ＦＴを合成して一枚の画像ＦＴに変換し、その画像ＦＴをポリラインＰＬＳの設定対象画像としてユーザに提示する。
このような画像の教示のための処理を行うに当たり、ユーザがポリラインＰＬＳを設定するのに好ましいと思われる画像ＦＴの評価方法について説明する。
【００８５】
まず、ユーザは、続きを設定したいポリラインＰＬＳの端点（始点ＰＳ、終点ＰＥ、または節点ＰＮ）を選択する。この選択された端点をポリゴンメッシュＰＭに投影し、投影された点の周辺のポリゴンＰＧを検索する。そして、ポリゴンメッシュＰＭと対応付けられている複数の画像ＦＴの内、先に検索されたポリゴンＰＧを画像ＦＴ上に投影するものをピックアップし、教示画像候補とする。教示画像候補の各画像について、ポリゴンメッシュＰＭを投影し、セルフオクルージョンが生じている領域の面積Ｓｏ、および、　先に検索された周辺のポリゴンＰＧの投影面上での面積Ｓｐを計算する。面積の計算が終了したら、面積Ｓｏが小さく面積Ｓｐが大きい画像を優先するような評価関数を作成する。そのような評価関数として、例えば次の（４）式を用いる。
【００８６】
ｆ（Ｓｐ，Ｓｏ）＝Ｓｐ／（Ｓｏ＋ε）　……（４）
但し、εは正の整数である。
上の（４）式による評価関数の値の大きい順に、教示画像候補をユーザに提示する。ユーザは、提示された画像のうちで最も設定し易そうな画像を選択してポリラインＰＬＳを設定する。
【００８７】
上に説明した画像教示によるポリラインの設定は、整理すると次のようなステップで行われることとなる。
（１）　任意の画像ＦＴを選択する。
（２）　選択した画像ＦＴに対し、２次元のポリラインＰＬＳを設定する。
（３）　続きを設定したいポリラインＰＬＳの端点を選択する。
（４）　画像教示機能により、教示画像候補について評価値が計算され、設定対象となる画像ＦＴが評価値にしたがって順次教示される。
（５）　教示された画像ＦＴから、ユーザが設定対象画像を選択する。
（６）　全ての画像ＦＴについてポリラインＰＬＳの設定が完了するまで、上の各ステップを繰り返す。
【００８８】
次に、合成画像を用いたポリラインの設定について説明する。
これは、ポリゴンＰＧに対応付けられている複数の画像ＦＴを合成して１つの画像にまとめ、ユーザが選択し易いい画像を設定対象画像として提示する方法である。
【００８９】
図１３は合成画像を生成する方法を説明するための図、図１４は合成画像の例を示す図である。
複数の画像ＦＴを１枚の画像に合成する方法としては、例えば図１３に示すように、ポリゴンメッシュＰＭを取り囲むような円筒ＣＬを想定し、この円筒ＣＬに、ポリゴンメッシュＰＭを構成するポリゴンＰＧを投影する。そして、投影したポリゴンＰＧに対応する画像領域について、それぞれに対応する画像ＦＴを用いて円筒面にマッピングする。その後、円筒ＣＬを平面に展開する。これによって、図１４に示すように、ポリゴンメッシュＰＭの全周から見た画像を展開した１枚の合成画像ＧＦが得られる。
【００９０】
このような合成画像をＧＦ用いることにより、ユーザは、画像間の連結関係を気にすることなく、複数のポリラインＰＬＳを設定することができる。また、円筒ＣＬへの投影時に、円筒ＣＬの各位置に対応する３次元座標を同時にマッピングすることにより、ポリゴンメッシュＰＭと合成画像ＧＦとの間における座標関係の対応も構築できるため、ポリラインＰＬＳの設定が容易に正確に行える。
【００９１】
上に述べた実施形態によると、ポリゴンメッシュＰＭに対して、画像の境界と一致するポリラインＰＬＴを容易に設定することができる。
上の実施形態において、対象物の種類、編集装置１の全体または各部の構成、形状、個数、処理の内容および順序などは、本発明の趣旨に沿って適宜変更することができる。
【００９２】
【発明の効果】
本発明によると、ポリゴンメッシュに対して、画像の境界と一致するポリラインを容易に設定することができる。
【図面の簡単な説明】
【図１】本発明の実施形態に係る３次元モデルの編集装置のブロック図である。
【図２】編集装置における位相編集の概念を示す図である。
【図３】ポリラインの例を示す図である。
【図４】画像上に投影されたポリゴンメッシュの例を示す図である。
【図５】ポリゴンの分割方法を説明するための図である。
【図６】分割されたポリゴンの連結関係を説明するための図である。
【図７】ポリゴンメッシュの縮退処理を説明するための図である。
【図８】分割によるポリラインの設定処理を示すフローチャートである。
【図９】ポリゴン頂点の選択により設定されたポリラインを示す図である。
【図１０】ポリゴン頂点の選択によるポリラインの設定処理を示すフローチャートである。
【図１１】複数の画像に設定されたポリラインに基づくポリラインの統合処理を示す図である。
【図１２】設定済みの２次元ポリラインの表示例を示す。
【図１３】合成画像を生成する方法を説明するための図である。
【図１４】合成画像の例を示す図である。
【符号の説明】
１　編集装置（３次元データへのポリラインの設定装置）
１０　装置本体（第１の手段、第２の手段）
ＰＬＳ　ポリライン（２次元のポリライン）
ＰＬＴ　ポリライン（３次元のポリライン）
ＰＭ　ポリゴンメッシュ（３次元データ）
ＰＧ　ポリゴン
ＥＴ　エッジ
ＦＴ　画像
【図１】
2004062637.tif 000004
【図２】
2004062637.tif 000005
【図３】
2004062637.tif 000006
【図４】
2004062637.tif 000007
【図５】
2004062637.tif 000008
【図６】
2004062637.tif 000009
【図７】
2004062637.tif 000010
【図８】
2004062637.tif 000011
【図９】
2004062637.tif 000012
【図１０】
2004062637.tif 000013
【図１１】
2004062637.tif 000014
【図１２】
2004062637.tif 000015
【図１３】
2004062637.tif 000016
【図１４】
2004062637.tif 000017