(57)【要約】【課題】ステレオ画像から比較的簡易に２枚の画像の対応点を求める３次元データ生成装置、３次元データ生成方法およびプログラムを提供する。【解決手段】画像データ入力部２は、異なる位置から所定の領域を撮影した２つの画像の画像データを取得する。位置指定部３は、２つの画像データのそれぞれの画像で、１つの構造物の領域に含まれる画像上の指定点を取得する。閉領域抽出部４は、２つの画像データのそれぞれの画像で指定点を含み、指定点との色の差が所定の範囲であって連続する画素の集合である閉領域を抽出する。外形ベクトル生成部５は、２つの画像のそれぞれで抽出した閉領域の輪郭に沿って一巡する外形ベクトルを抽出する。３次元データ計算部７は、２つの画像データのそれぞれの外形ベクトルが同じ構造物の外形に対応するとみなして、２つの画像データからその構造物の外形の３次元の位置座標を算出する。【選択図】図１
2011048507.tif 000002
【特許請求の範囲】
【請求項１】
異なる位置から所定の領域を撮影した２つの画像の画像データを取得する画像データ取得手段と、
前記２つの画像データのそれぞれの画像で、１つの構造物の領域に含まれる画像上の指定点を取得する手段と、
前記２つの画像データのそれぞれの画像で前記指定点を含み、前記指定点との色の差が所定の範囲であって連続する画素の集合である閉領域を抽出する閉領域抽出手段と、
前記２つの画像のそれぞれで抽出した前記閉領域の輪郭に沿って一巡する外形ベクトルを抽出する外形ベクトル抽出手段と、
前記２つの画像データのそれぞれの前記外形ベクトルが同じ構造物の外形に対応するとみなして、前記複数の画像データからその構造物の外形の３次元の位置座標を計算する３次元データ計算手段と、
を備える３次元データ生成装置。
【請求項２】
前記画像から前記指定点を含む領域の色が所定の値以上変化する画素の並びであるエッジを抽出するエッジ抽出手段と、
前記エッジの端点またはエッジの角点から、該エッジを延長する直線または該エッジに直交する直線に沿って、他の前記エッジまたは前記画像の境界と最初に交わる点までの線分である分割線を生成する手段と、を備え、
前記閉領域抽出手段は、前記分割線および／または前記エッジで囲まれた連続する画素の集合である分割領域のうち、前記指定点との色の差が所定の範囲である隣り合う前記分割領域を結合して１つの前記閉領域を抽出する、
ことを特徴とする請求項１に記載の３次元データ生成装置。
【請求項３】
前記画像から前記指定点を含む領域の色が変化する画素の並びであるエッジを抽出するエッジ抽出手段を備え、
前記閉領域抽出手段は、前記画像の画素の並びに対する前記エッジの傾きを算出して、前記画像の画素の並びが前記エッジに平行または垂直になるように前記画像を回転させてから、前記閉領域を抽出し、
前記外形ベクトル抽出手段は、前記閉領域の輪郭を、前記画像の画素の並びと前記エッジの角度が前記エッジの傾きになるように逆に回転させて、前記外形ベクトルを抽出する、
ことを特徴とする請求項１または２に記載の３次元データ生成装置。
【請求項４】
前記３次元データ計算手段は、前記２つの画像のそれぞれの前記指定点から前記外形ベクトルの頂点へ向かうベクトルである頂点ベクトルのうち、前記２つの画像からそれぞれ１つずつ選択した前記頂点ベクトルの差の絶対値の、すべての前記頂点ベクトルについての和が最小になる組合せで、前記２つの画像の外形ベクトルの頂点を対応づける、
ことを特徴とする請求項１ないし３のいずれか１項に記載の３次元データ生成装置。
【請求項５】
前記２つの画像からそれぞれ１つずつ選択した前記頂点ベクトルの差の絶対値の、すべての前記頂点ベクトルについての和の最小値が所定の値を超える場合に、前記指定点を含む領域から１つの構造物の外形ベクトルを生成できないことを表す情報を表示する手段を備える、
ことを特徴とする請求項４に記載の３次元データ生成装置。
【請求項６】
前記２つの画像のそれぞれにおいて、前記外形ベクトルの頂点が３以下の場合、もしくは、前記外形ベクトルで囲まれる画素の数が所定の数より少ない場合、または、前記２つの画像のそれぞれで抽出した輪郭線の頂点の数の差が所定の値を超える場合に、前記指定点を含む領域から外形ベクトルを生成できないことを表す情報を表示する手段を備える、
ことを特徴とする請求項１ないし５のいずれか１項に記載の３次元データ生成装置。
【請求項７】
異なる位置から所定の領域を撮影した２つの画像の画像データを取得する画像データ取得ステップと、
前記２つの画像データのそれぞれの画像で、１つの構造物の領域に含まれる画像上の指定点を取得するステップと、
前記２つの画像データのそれぞれの画像で前記指定点を含み、前記指定点との色の差が所定の範囲であって連続する画素の集合である閉領域を抽出する閉領域抽出ステップと、
前記２つの画像のそれぞれで抽出した前記閉領域の輪郭に沿って一巡する外形ベクトルを抽出する外形ベクトル抽出ステップと、
前記２つの画像データのそれぞれの前記外形ベクトルが同じ構造物の外形に対応するとみなして、前記複数の画像データからその構造物の外形の３次元の位置座標を計算する３次元データ計算ステップと、
を備える３次元データ生成方法。
【請求項８】
前記画像から前記指定点を含む領域の色が所定の値以上変化する画素の並びであるエッジを抽出するエッジ抽出ステップと、
前記エッジの端点またはエッジの角点から、該エッジを延長する直線または該エッジに直交する直線に沿って、他の前記エッジまたは前記画像の境界と最初に交わる点までの線分である分割線を生成するステップと、を備え、
前記閉領域抽出ステップは、前記分割線および／または前記エッジで囲まれた連続する画素の集合である分割領域のうち、前記指定点との色の差が所定の範囲である隣り合う前記分割領域を結合して１つの前記閉領域を抽出する、
ことを特徴とする請求項７に記載の３次元データ生成方法。
【請求項９】
前記画像から前記指定点を含む領域の輝度または色が変化する画素の並びであるエッジを抽出するエッジ抽出ステップを備え、
前記閉領域抽出ステップは、前記画像の画素の並びに対する前記エッジの傾きを算出して、前記画像の画素の並びが前記エッジに平行または垂直になるように前記画像を回転させてから、前記閉領域を抽出し、
前記外形ベクトル抽出ステップは、前記閉領域の輪郭を、前記画像の画素の並びと前記エッジの角度が前記エッジの傾きになるように逆に回転させて、前記外形ベクトルを抽出する、
ことを特徴とする請求項７または８に記載の３次元データ生成方法。
【請求項１０】
前記３次元データ計算ステップは、前記２つの画像のそれぞれの前記指定点から前記外形ベクトルの頂点へ向かうベクトルである頂点ベクトルのうち、前記２つの画像からそれぞれ１つずつ選択した前記頂点ベクトルの差の絶対値の、すべての前記頂点ベクトルについての和が最小になる組合せで、前記２つの画像の外形ベクトルの頂点を対応づける、
ことを特徴とする請求項７ないし９のいずれか１項に記載の３次元データ生成方法。
【請求項１１】
前記２つの画像からそれぞれ１つずつ選択した前記頂点ベクトルの差の絶対値の、すべての前記頂点ベクトルについての和の最小値が所定の値を超える場合に、前記指定点を含む領域から１つの構造物の外形ベクトルを生成できないことを表す情報を表示するステップを備える、
ことを特徴とする請求項１０に記載の３次元データ生成方法。
【請求項１２】
前記２つの画像のそれぞれにおいて、前記外形ベクトルの頂点が３以下の場合、もしくは、前記外形ベクトルで囲まれる画素の数が所定の数より少ない場合、または、前記２つの画像のそれぞれで抽出した輪郭線の頂点の数の差が所定の値を超える場合に、前記指定点を含む領域から外形ベクトルを生成できないことを表す情報を表示するステップを備える、
ことを特徴とする請求項７ないし１１のいずれか１項に記載の３次元データ生成方法。
【請求項１３】
コンピュータに、
異なる位置から所定の領域を撮影した２つの画像の画像データを取得する画像データ取得ステップと、
前記２つの画像データのそれぞれの画像で、１つの構造物の領域に含まれる画像上の指定点を取得するステップと、
前記２つの画像データのそれぞれの画像で前記指定点を含み、前記指定点との色の差が所定の範囲であって連続する画素の集合である閉領域を抽出する閉領域抽出ステップと、
前記２つの画像のそれぞれで抽出した前記閉領域の輪郭に沿って一巡する外形ベクトルを抽出する外形ベクトル抽出ステップと、
前記２つの画像データのそれぞれの前記外形ベクトルが同じ構造物の外形に対応するとみなして、前記複数の画像データからその構造物の外形の３次元の位置座標を計算する３次元データ計算ステップと、
を実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ステレオ画像から３次元データを自動生成する３次元データ生成装置、３次元データ生成方法およびプログラムに関する。
【背景技術】
【０００２】
人工衛星や航空機等から撮影された画像を基に、ステレオマッチングによって地形を示す３次元データ［ＤＳＭ（Digital Surface Model）データ］を生成する方法が広く行われている。ステレオマッチング処理とは異なる視点から撮影した２枚の画像、いわゆるステレオ画像について、同一の点を撮像している各画像中の対応点を求め、その点の２枚の画像の視差を用いて三角測量の原理によって、対象までの奥行きや形状を求めることである。
【０００３】
写真測量による地形図を作成するには、ステレオ画像を立体視して、オペレータの操作によって画像中の点の３次元座標を求める図化編集システムが用いられている。図化編集システムでは、異なる場所から同じ地域を撮影した２枚の航空写真が重なった状態で表示されていて、特殊なディスプレイと円偏光メガネを用いることで２枚の航空写真のうち片方を左目のみで、もう片方を右目のみで見ることが可能である。これにより両眼視差を再現させ、立体視ウィンドウ上で両眼視差立体視を行うことができ、任意の地点の３次元座標の取得が可能となる。
【０００４】
ステレオマッチングを自動で行う処理については既に様々な手法が提案されている。例えば、特許文献１のステレオマッチング方法では、標定要素保持部に保持されている標定要素に応じて変換係数を算出し、ステレオ画像保持部に保持されているステレオ画像をモニタに表示させ、これに応じて入力された情報に応じて不定形窓を設定する。ステレオマッチング部は、変換係数、ステレオ画像、不定形窓、拘束条件に応じて平面ステレオマッチングを行って平面のパラメータを算出して３次元モデルを生成する。
【０００５】
特許文献２のステレオマッチング方法は、ＴＬＳ（Ｔｈｒｅｅ  ｌｉｎｅ  ｓｅｎｓｏｒ）で地上面を走査して、都市地上面Ａの前方視画像Ｐｆ、直下視画像Ｐｎ、後方視画像Ｐｂを得る。それぞれの画像をテクスチャ解析して複数の領域Ｒｆｋ、Ｒｎｋ、Ｒｂｋに分割する。領域Ｒｎｋ上の特徴点を抽出し、前方視画像Ｐｆにおけるこの特徴点に対する視線ベクトルＶｆを算出する。レーザスキャナにより取得した都市地上面Ａの三次元データと視線ベクトルＶｆとの交点の有無を調査する。交点が存在しないことを確認して、領域Ｒｎｋをエピポーラライン上に投影して領域マッチングを行う。さらに、領域Ｒｆｋ、Ｒｎｋ近傍の直線エッジを抽出する。領域Ｒｆｋ、Ｒｎｋの近傍にマッチング範囲を絞って直線エッジのマッチングを行う。このとき、領域Ｒｆｋ、Ｒｎｋそれぞれと直線エッジとの位置関係に基づいて対応する直線エッジを検索する。
【０００６】
その他、ステレオマッチング方法ではないが、航空写真画像からポリゴン形成する方法が特許文献３に記載されている。特許文献３のポリゴン形成方法は、航空写真画像もしくは衛星画像からエッジ抽出による色情報の変化境界を線分化して地物線分図形を形成し、この地物線分図形に高さデータを重ね合わせて３次元地物線分図形を得る。そして、この３次元地物線分図形の複数の線分を同一高さの水準でグループ化すると共にこの複数の線分の夫々の一方の高さと他方の高さを属性として比高差によりこの複数の線分に方向を定め、このグループ化した各グループの線分の最も近い始点及び終点を結線するようにしたものである。
【０００７】
また、特許文献４には、建物の輪郭形状を抽出する地図作成装置が記載されている。特許文献４の地図作成装置は、空中写真画像中に存在する建物中の少なくとも一点の位置の指示を受け付ける画像指示部と、前記指示された位置の周囲の色を判定した結果に基づいて建物領域を抽出し、建物領域の輪郭線を抽出する輪郭抽出部と、前記建物領域の輪郭のベクトルを生成するベクトル形状生成部と、を有する。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００３−３２３６０３号公報
【特許文献２】特開２００４−３０４６１号公報
【特許文献３】特開２００４−２５２２１３号公報
【特許文献４】特開２００４−３４１４２２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
ステレオマッチング処理では、２つの画像の局所的な画像パターンの相関値を用いて、２つの画像の対応点を求めることが一般に行われている。しかし、局所的な画像パターンの相関値を用いる方法は計算量が多い。また、画像中に繰り返しパターンが存在するような場合には、一意に対応付けすることができない。相関をとる画像パターンを大きくすれば対応付けの精度は向上するが、計算量は多くなる。画像パターンを小さくすれば、計算量は少なくなるが、対応付けを誤る率が増加する。
【００１０】
本発明は上述のような事情に鑑みてなされたもので、ステレオ画像から比較的簡易に２枚の画像の対応点を求める３次元データ生成装置、３次元データ生成方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明の第１の観点に係る３次元データ生成装置は、
異なる位置から所定の領域を撮影した２つの画像の画像データを取得する画像データ取得手段と、
前記２つの画像データのそれぞれの画像で、１つの構造物の領域に含まれる画像上の指定点を取得する手段と、
前記２つの画像データのそれぞれの画像で前記指定点を含み、前記指定点との色の差が所定の範囲であって連続する画素の集合である閉領域を抽出する閉領域抽出手段と、
前記２つの画像のそれぞれで抽出した前記閉領域の輪郭に沿って一巡する外形ベクトルを抽出する外形ベクトル抽出手段と、
前記２つの画像データのそれぞれの前記外形ベクトルが同じ構造物の外形に対応するとみなして、前記複数の画像データからその構造物の外形の３次元の位置座標を計算する３次元データ計算手段と、
を備える。
【００１２】
本発明の第２の観点に係る３次元データ生成方法は、
異なる位置から所定の領域を撮影した２つの画像の画像データを取得する画像データ取得ステップと、
前記２つの画像データのそれぞれの画像で、１つの構造物の領域に含まれる画像上の指定点を取得するステップと、
前記２つの画像データのそれぞれの画像で前記指定点を含み、前記指定点との色の差が所定の範囲であって連続する画素の集合である閉領域を抽出する閉領域抽出ステップと、
前記２つの画像のそれぞれで抽出した前記閉領域の輪郭に沿って一巡する外形ベクトルを抽出する外形ベクトル抽出ステップと、
前記２つの画像データのそれぞれの前記外形ベクトルが同じ構造物の外形に対応するとみなして、前記複数の画像データからその構造物の外形の３次元の位置座標を計算する３次元データ計算ステップと、
を備える。
【００１３】
本発明の第３の観点に係るプログラムは、コンピュータに、
異なる位置から所定の領域を撮影した２つの画像の画像データを取得する画像データ取得ステップと、
前記２つの画像データのそれぞれの画像で、１つの構造物の領域に含まれる画像上の指定点を取得するステップと、
前記２つの画像データのそれぞれの画像で前記指定点を含み、前記指定点との色の差が所定の範囲であって連続する画素の集合である閉領域を抽出する閉領域抽出ステップと、
前記２つの画像のそれぞれで抽出した前記閉領域の輪郭に沿って一巡する外形ベクトルを抽出する外形ベクトル抽出ステップと、
前記２つの画像データのそれぞれの前記外形ベクトルが同じ構造物の外形に対応するとみなして、前記複数の画像データからその構造物の外形の３次元の位置座標を計算する３次元データ計算ステップと、
を実行させることを特徴とする。
【発明の効果】
【００１４】
本発明の３次元データ生成装置、３次元データ生成方法およびプログラムによれば、ステレオ画像から比較的簡易に２枚の画像の対応点を求めることができる。その対応点がステレオ画像で同じ構造物の外形に対応するとみなして、その構造物の外形の位置座標を算出することができる。
【図面の簡単な説明】
【００１５】
【図１】本発明の実施の形態１に係る３次元データ生成装置の構成例を示すブロック図である。
【図２】画像データに変換される航空写真の一例を模式的に示す図である。
【図３】２つの画像の重複部分の例を示す概念図である。
【図４】構造物の領域が画素の並びに対して傾いている画像の例を示す図である。
【図５】画素の並びが構造物の領域のエッジに平行になるように回転させた例を示す図である。
【図６】画像からエッジを抽出した状態を模式的に示す図である。
【図７】エッジの端点または角点から分割線を生成した状態を模式的に示す図である。
【図８】分割領域を結合して閉領域を生成した状態を模式的に示す図である。
【図９】２つの画像の外形ベクトルの対応を示す図である。
【図１０】２つの画像の外形ベクトルの対応づけを説明する図である。
【図１１】実施の形態１に係る３次元データ生成処理の動作の一例を示すフローチャートである。
【図１２】本発明の実施の形態２に係る３次元データ生成装置の構成例を示すブロック図である。
【図１３】実施の形態２に係る３次元データ生成処理の動作の一例を示すフローチャートである。
【図１４】実施の形態２に係る外形ベクトル生成処理の動作の一例を示すフローチャートである。
【図１５】実施の形態２に係る外形ベクトル対応処理の動作の一例を示すフローチャートである。
【図１６】本発明の実施の形態に係る３次元データ生成装置の物理的な構成の一例を示すブロック図である。
【発明を実施するための形態】
【００１６】
以下、この発明の実施の形態について図面を参照しながら詳細に説明する。なお、図中同一または相当部分には同一符号を付す。
【００１７】
（実施の形態１）
図１は、本発明の実施の形態１に係る３次元データ生成装置の構成例を示すブロック図である。３次元データ生成装置１は、異なる位置から同じ領域を含む範囲を撮影した２つの画像の画像データを入力し、その同じ領域に含まれる構造物の外形の位置を表す座標である３次元データを生成する。
【００１８】
実施の形態１に係る３次元データ生成装置１は、画像データ入力部２、位置指定部３、閉領域抽出部４、外形ベクトル生成部５、外形ベクトル対応部６および３次元データ計算部７から構成される。閉領域抽出部４は、画像回転部４１、エッジ抽出部４２、分割線生成部４３および閉領域生成部４４を含む。外形ベクトル生成部５は、画像逆回転部５１を含む。
【００１９】
画像データ入力部２は、ステレオマッチング処理に使用する異なる位置から同じ領域を含む範囲を撮影した２つの画像の画像データを入力する。画像データは、例えば、デジタル画像に変換された航空写真の画像である。画像データには、画像を撮影した位置、撮影した方向、画角などが含まれる。
【００２０】
図２は、画像データに変換される航空写真の一例を模式的に示す。図２に示される航空写真は、上空を飛行する航空機から連続撮影された、航空写真Ａと航空写真Ｂから構成される。航空写真Ａと航空写真Ｂとは、航空機の進行方向について範囲が重複して撮影されたものである。図２のハッチングを付した重複部分は、異なる位置Ｐ１、Ｐ２から同じ領域を撮影した画像である。
【００２１】
本実施の形態における画像は、航空写真Ａ、航空写真Ｂを一例とする航空写真をデジタル変換して生成した画像である。本実施の形態に用いる画像は、航空写真に限定されるものではなく、デジタル化された衛星写真による画像や、一般的なデジタルカメラで撮影したデジタル画像や、一般的なアナログカメラで撮影したアナログ写真をスキャニングでデジタル化したデジタル画像などであってもよい。
【００２２】
位置指定部３は、入力した２つの画像の重複部分を表示し、その中の３次元データ生成の対象になる構造物の範囲の１点を指定する入力を受け付ける。３次元データを生成する対象の構造物は、家屋やビルディングなどの建物、鉄塔、橋梁、高架道路または高架鉄道など、あらゆる人工的な建造物を含む。本実施の形態の構造物には、３次元データを生成する対象になれば、自然の地物なども含まれる。さらに、屋内の物体の３次元データを生成すること等を想定すれば、形状を有する任意の物体を含む。
【００２３】
図３は、２つの画像の重複部分の例を示す概念図である。図３は、見やすいように構造物の一部をハッチングで表している。図３の２つの画像は地表の同じ範囲を異なる視点から撮影したものである。左の画像は、画像の対象に向かって左の位置から撮影した画像（以下、左画像という）である。右の画像は、画像の対象に向かって右の位置から撮影した画像（以下、右画像という）である。図中の矢印は３次元データを生成する対象になる構造物の範囲の１点を指定するものである。矢印の先端が指定点である。
【００２４】
図３では理解を容易にするために、２つの画像を左右に並べて表示している。異なる場所から同じ地域を撮影した２つの画像を、画像に平行な（撮影方向に垂直な）任意の平面（例えば、撮影対象の地面の平均高さ）においてちょうど２つの画像の同じ対象の位置が一致するように重ねて表示してもよい。このように重ねて表示して、特殊なディスプレイと円偏光メガネを用いることで２つの画像のうち左画像を左目のみ、右画像を右目のみで見ることが可能である。これにより両眼視差を再現させ、立体視ウィンドウ上で両眼視差立体視を行うことができる。この状態で３次元データを生成する対象の構造物の範囲の１点にカーソルを合わせて指定点を入力する。カーソルは左画像と右画像のそれぞれに表示され、立体視で高さ（画像の奥行き）方向に移動することができるので高さも指定することができる。本実施の形態では指定点の高さは構造物に正確に合っていなくても構わない。図３の左画像の矢印と右画像の矢印は、ある高さで同じ位置(同一の緯度、経度および標高値)を指している。
【００２５】
図１の閉領域抽出部４は、入力した２つの画像データのそれぞれの画像で、位置指定部３で指定された点（指定点）を含み、指定点との色の差が所定の範囲であって連続する画素の集合である閉領域を抽出する。
【００２６】
色とは、色相、彩度および明度の３要素によって規定される。本実施の形態では、色空間をコンピュータ上のカラー画像メモリとして一般に使われるＲＧＢ系から、Ｌ*ａ*ｂ*表色系に変換する。この表色系では明度はL*の値として表現され、明度変化に対して色相や彩度(a*b*)を容易に不変とできる。その上で、画像の各画素の色と指定点の色との距離を求め、この大きさによるグレースケール画像となるように変換する。この変換画像では指定点の色と近い色ほど黒く表示される。線形空間であるＬ*ａ*ｂ*表色系を用いることで、指定点の色と近い領域を人間の知覚に近似して正しく判定できる。また、色距離の導出にあたり明度値L*に適切な重みを指定することで影による影響を適切に除外することができる。閉領域抽出部４は、指定点を含み、指定点の色との差が所定の範囲で、連続する画素の集合である閉領域を、３次元データを生成する対象の構造物の領域として抽出する。
【００２７】
閉領域抽出部４の画像回転部４１は、前述のようにグレースケールに変換した画像の各画素についてエッジ強度を求める。エッジ強度が所定の閾値を超える画素全体でのエッジ勾配の統計データから、画素の並び（水平または垂直）に対する対象の構造物の領域のエッジの傾きを求める。そして、画像の画素の並びがエッジに平行または直角になるように画像を回転する。
【００２８】
図４は、構造物の領域が画素の並びに対して傾いている画像の例を示す。図４の矢印は、指定点を示す。図４では、指定点で指定される構造物の領域が画像の画素の並び（図４の水平方向または垂直方向）に対して傾いている。
【００２９】
図５は、画素の並びが構造物の領域のエッジに平行になるように回転させた例を示す。多くの構造物は真上から見た場合に外形が直角多角形なので、対象の構造物の領域のエッジの傾きに従って画像を回転することで、切妻屋根などの一般的な勾配から検出すべきエッジの方向が画像の水平方向・垂直方向と各々の±１０°の範囲に限定される。これにより、エッジ検出の精度向上と処理時間短縮を図る。
【００３０】
なお、画像を回転させる場合、入力した画像全体について回転する処理を行う必要はない。指定点を中心に、想定される最大の構造物が収まるであろう範囲の画像に限って回転させて、以後の処理を行えばよい。
【００３１】
図１のエッジ抽出部４２は、２つの画像のそれぞれから、指定点を含む領域の色が所定の値以上変化する画素の並びであるエッジを抽出する。画像回転部によって、画素の並びが構造物の領域のエッジに平行または垂直になるように画像が回転されている場合は、画素の並びの水平方向±１０°および垂直方向±１０°の範囲のエッジを抽出する。
【００３２】
図６は、図５の画像からエッジを抽出した状態を模式的に示す。図６では、抽出したエッジを太い実線で表している。この時点では、指定点を含む構造物の領域を限定できないので、画素の色が所定の値以上変化する点を抽出し、それが連続する方向をエッジ方向とする。特に、画素の並びが構造物の領域のエッジに平行または垂直になるように画像が回転されている場合は、画素の並びの水平方向±１０°および垂直方向±１０°の範囲のエッジを抽出する。例えば、ソーベルフィルタを用いて、水平方向および垂直方向の色（グレースケール）の変化点を抽出し、水平方向±１０°および垂直方向±１０°の範囲で、所定の数以上連続する変化点の並びをエッジとして抽出する。
【００３３】
図１の分割線生成部４３は、エッジ抽出結果をもとに画像を領域分割する。領域分割はエッジに分割線を追加することで実現する。分割線は、エッジの端点または角点を起点として、エッジを延長する直線またはエッジに直交する直線に沿って、他のエッジまたは画像の境界と最初に交わる点までの線分である。
【００３４】
エッジの端点から分割線を追加する場合には、端点を起点としてエッジと反対方向および両垂直方向に向かう計３本の半直線を生成する。次にこの半直線が他のエッジと交差する場合、最初に他のエッジと交差する点と分割線の終点とする。また、この半直線が他のエッジと交差しない場合、画像の端までを分割線とする。
【００３５】
エッジの角点から分割線を追加する場合には、角点を通る全てのエッジを対象として、角点を起点としてエッジを延長する半直線を生成する。次にこの半直線が他のエッジと交差する場合、最初に他のエッジと交差する点と分割線の終点とする。また、この半直線が他のエッジと交差しない場合、画像の端までを分割線とする。
【００３６】
画素の並びが構造物の領域のエッジに平行または垂直になるように画像が回転されている場合は、角点からエッジとは逆向きに画素の並びに平行または垂直な半直線を生成する。この半直線のうち、角点を通るいずれのエッジともなす角が１０°以上あるものに対して、前述と同じように終点を定義し分割線とする。
【００３７】
図７は、エッジの端点または角点から分割線を生成した状態を模式的に示す。図７は、図６で生成されたエッジから分割線を生成した状態である。図７の太い実線はエッジを表す。エッジの端点または角点から水平または垂直に引かれた細い実線が分割線である。図７では、見やすいようにハッチングを省略している。また、生成されるすべての分割線を表示しているわけではない。
【００３８】
図１の閉領域生成部４４は、分割線とエッジを用いて、指定点を含み、指定点との色の差が所定の範囲であって連続する画素の集合である閉領域を抽出する。分割線および／またはエッジで囲まれた連続する画素の集合を分割領域という。分割領域のうち、指定点を含む分割領域に、指定点との色の差が所定の範囲である隣り合う分割領域を結合して１つの閉領域を抽出する。
【００３９】
図８は、分割領域を結合して閉領域を生成した状態を模式的に示す。矢印の先端で示される指定点を含む分割領域をまず選択する。その分割領域に隣接する分割領域で、指定点との色の差が所定の範囲であるものを結合する。色の差を判定するには、例えば、分割領域に含まれる画素の平均をその分割領域の色として、指定点の色と比較する。結合した分割領域に隣接する分割領域で、指定点との色の差が所定の範囲であるものをさらに結合する。これを繰り返して、図８のハッチングで示される閉領域を抽出する。
【００４０】
なお、図４ないし図８はそれぞれ、２つの画像の一方（左画像または右画像）を代表して示す。閉領域抽出部４は、２つの画像のそれぞれについて、図４ないし図８に示すような処理を行って閉領域を抽出する。
【００４１】
図１の外形ベクトル生成部５は、閉領域抽出部４で抽出した２つの画像のそれぞれの閉領域の外形ベクトルを生成する。外形ベクトルは、閉領域の外形の頂点を、閉領域の外周を一巡する順序で並べた座標列で表される。図８の例では、外形ベクトルは、ハッチングを付けた領域の外形線の頂点を、外周を一巡する順序で並べた座標列で表される。
【００４２】
閉領域の画像が画像回転部４１で回転されている場合、画像逆回転部５１は、生成した外形ベクトルを、画像の画素の並びとエッジの角度が画像回転部４１で抽出したエッジ強度の傾きになるように逆に回転させる。
【００４３】
外形ベクトル生成部５で生成する２つの画像それぞれの外形ベクトルを、
ｐ（（ｘｐ１，ｙｐ１）、（ｘｐ２，ｙｐ２）、．．．、（ｘｐｍ、ｙｐｍ））
ｑ（（ｘｑ１，ｙｑ１）、（ｘｑ２，ｙｑ２）、．．．、（ｘｑｎ、ｙｑｎ））
とする。座標列ｐは左画像から生成した外形ベクトル、座標列ｑは、右画像から生成した外形ベクトルである。ｍは左画像から抽出した閉領域の外形の頂点の数、ｎは右画像から抽出した閉領域の外形の頂点の数である。多くの場合、左画像の閉領域と右画像の閉領域の頂点の数は一致する。
【００４４】
図１の外形ベクトル対応部６は、外形ベクトル生成部５で生成した外形ベクトル（座標列ｐ、ｑ）について、同じ地点を示す頂点同士を対応付ける。図９は、２つの画像の外形ベクトルの対応付けの例を示す。図９は、図３の２つの画像に対応している。図９では、両端矢印の曲線で２つの画像の外形ベクトルの頂点同士の対応を表す。
【００４５】
外形ベクトルの対応付けには、指定点I と、座標列ｐ のｉ番目の点ｐｉ、座標列ｑ のｊ 番目の点ｑｊ を引数とする関数ｆ（Ｉ，ｉ，ｊ，ｐ，ｑ）を、頂点同士の対応をとるための評価関数として用いる。関数ｆ（Ｉ，ｉ，ｊ，ｐ，ｑ）は、指定点Ｉから見て点ｐｉ，ｑｊが同じ方向、同じ距離にある場合により小さい値を返す関数である。左右画像の閉領域の全ての点列を網羅するようなｉ，ｊの組み合わせｖ（ｉ，ｊ）のうち、関数ｆの総和がもっとも小さくなるものを頂点の対応付けＶとして採用する。
【００４６】
図１０は、２つの画像の外形ベクトルの対応付けを説明する図である。図１０は、左画像の外形ベクトルｐと右画像の外形ベクトルｑを、それぞれの指定点が一致するように重ねた状態を示す。図１０では、外形ベクトルｐと外形ベクトルｑのずれを誇張して描いている。指定点から外形ベクトルｐの頂点ｐｉへのベクトル（頂点ベクトル）をｓｉとする（ｉ＝１〜ｍ）。指定点から外形ベクトルｑの頂点ｑｊへの頂点ベクトルをｔｊとする（ｊ＝１〜ｎ）。
【００４７】
左画像の外形ベクトルｐと右画像の外形ベクトルｑからそれぞれ１つずつ点ｐｉ、点ｑｊを選んで対にする組み合わせについて、｜ｓｉ−ｔｊ｜の合計を評価関数とすることができる。評価関数が最小となる組み合わせを頂点の対応付けＶとして採用すればよい。
【００４８】
２つの画像の外形ベクトルｐ、ｑの頂点の数ｍ、ｎが同じであれば、簡略には以下のように対応付けを求めることができる。左画像の外形ベクトルｐのある点ｐｉについて、右画像の外形ベクトルｑのうち｜ｓｉ−ｔｊ｜が最小になる点ｑｊを対応させる。外形ベクトルｐの各点について同じ操作を行って、対応付けＶを得る。
【００４９】
図１の３次元データ計算部７は、外形ベクトル対応部６で対応付けられた頂点の組みが実空間の同一の点に対応するとみなして、外形ベクトル生成部５で生成された外形ベクトルの実空間の３次元データを計算する。実空間において、左画像を撮影した視点から外形ベクトルｐの１つの頂点を見る直線と、右画像を撮影した視点から外形ベクトルｑの対応する頂点を見る直線との交点の座標を計算する。
【００５０】
外形ベクトルｐ、ｑの頂点の数ｍ、ｎが異なる場合、外形ベクトルｐとｑの最も差の小さい頂点ベクトルｓｉとｔｊを対応させて、残った頂点を削除して３次元データを計算することができる。また、残った頂点に（立体視で）最も近い他方の外形ベクトル上の点をそれに対応付けて、３次元データを計算してもよい。
【００５１】
図１１は、実施の形態１に係る３次元データ生成処理の動作の一例を示すフローチャートである。画像データ入力部２は、異なる位置から同じ領域を含む範囲を撮影した２つの画像の画像データを入力する（ステップＳ１１）。位置指定部３は、２つの画像から３次元データ生成の対象になる構造物の範囲の１点を指定する入力を受け付ける（ステップＳ１２）。
【００５２】
閉領域抽出部４の画像回転部４１は、各画像のエッジ強度からエッジの傾きを求めて、画像の画素の並びがエッジに平行または直角になるように画像を回転する（ステップＳ１３）。エッジ抽出部４２は、２つの画像のそれぞれから、指定点を含む領域の色が所定の値以上変化する画素の並びであるエッジを抽出する（ステップＳ１４）。
【００５３】
分割線生成部４３は、エッジの端点または角点を起点として、エッジを延長する直線またはエッジに直交する直線に沿って、他のエッジまたは画像の境界と最初に交わる点までの線分である分割線を生成する（ステップＳ１５）。閉領域生成部４４は、２つの画像それぞれで、指定点を含む分割領域に、指定点との色の差が所定の範囲である隣り合う分割領域を結合して１つの閉領域を抽出する（ステップＳ１６）。
【００５４】
外形ベクトル生成部５は、閉領域抽出部４で抽出した２つの画像のそれぞれの閉領域の外形ベクトルを生成する（ステップＳ１７）。閉領域の画像が画像回転部で回転されている場合、画像逆回転部５１は、生成した外形ベクトルを、画像の画素の並びとエッジの角度が画像回転部４１で抽出したエッジ強度の傾きになるように逆に回転させる。
【００５５】
外形ベクトル対応部６は、外形ベクトル生成部５で生成した外形ベクトルについて、前述のような方法で同じ地点を示す頂点同士を対応付ける（ステップＳ１８）。３次元データ計算部７は、外形ベクトル対応部６で対応付けられた頂点の組みが実空間の同一の点に対応するとみなして、外形ベクトル生成部５で生成された外形ベクトルの実空間の３次元データを計算する（ステップＳ１９）。
【００５６】
以上説明したように、本実施の形態１の３次元データ生成装置１によれば、ステレオ画像から比較的簡易に２枚の画像の対応点を求めることができる。その対応点がステレオ画像で同じ構造物の外形に対応するとみなして、その構造物の外形の位置座標を算出することができる。
【００５７】
なお、本実施の形態１では、３次元データを生成する対象の構造物の領域の点を、オペレータの入力によって指定することを想定して説明した。３次元データを生成する対象の構造物の領域の点は、地図データの住居表示とその座標（経緯度）から与えられるようにしてもよい。
【００５８】
（実施の形態２）
図１２は、本発明の実施の形態２に係る３次元データ生成装置１の構成例を示すブロック図である。実施の形態２では、２つの画像で対応付けられるような外形ベクトルを生成できない場合に、生成不能であることを表す情報を表示する。実施の形態２の３次元データ生成装置１は、生成不能表示部８を備える。外形ベクトル生成部５は、評価部５２を備える。また外形ベクトル対応部６は、対応判定部６１を含む。
【００５９】
閉領域抽出部４は、２つの画像から必ず対応付けできる外形ベクトルを生成できるとは限らない。例えば、抽出した閉領域の外形に明確な頂点がない場合、頂点の数が少ない場合、または、２つの画像から生成した外形ベクトルの頂点の数が異なる場合がある。例えば、球形の構造物では、左右の画像から生成した外形ベクトルは同じ点に対応していない。また、尖塔のような構造物の場合、左画像から生成した外形ベクトルと、右画像から生成した外形ベクトルは、同じ点に対応していない可能性がある。このような場合に、２つの外形ベクトルが同じ構造物の外形に対応するとみなして、２つの画像データからその構造物の外形の位置座標を算出すると、３次元データの誤差が大きい。
【００６０】
そこで、そのような場合に生成不能であることを表す情報を表示して、オペレータの注意を促す。オペレータはその表示を見て、例えばステレオ画像を立体視して、操作によって画像中の点の３次元座標を求めることができる。
【００６１】
外形ベクトル生成部５の評価部５２は、２つの画像から生成した外形ベクトルのいずれかが、頂点が３以下の場合、または、外形ベクトルで囲まれる面積（画素の数）が所定の数より少ない場合に、指定点を含む領域から外形ベクトルを生成できないと判定する。これらは、構造物が球形や尖塔の場合に該当する。あるいは、２つの画像のそれぞれで抽出した輪郭線の頂点の数の差が所定の値を超える場合に、指定点を含む領域から外形ベクトルを生成できないと判定する。これは、左右いずれかの画像で構造物に遮蔽された部分が、他方の画像で対象の構造物の閉領域に含まれるような場合に該当する。
【００６２】
外形ベクトル対応部６の対応判定部６１は、２つの画像からそれぞれ１つずつ選択した頂点ベクトルの差の絶対値の、すべての頂点ベクトルについての和の最小値が所定の値を超える場合に、外形ベクトルの対応付けができないと判定する。
【００６３】
生成不能表示部８は、評価部５２で外形ベクトルを生成できないと判定した場合に、指定点を含む領域から外形ベクトルを生成できないことを表す情報をディスプレイ装置（図示せず）などに表示する。また、対応判定部６１で外形ベクトルの対応付けができないと判定した場合に、指定点を含む領域から１つの構造物の外形ベクトルを生成できないこと（対応付け不能）を表す情報をディスプレイ装置（図示せず）などに表示する。
【００６４】
外形ベクトル生成不能または対応付け不能を表す情報を表示する方法は、ディスプレイ装置またはランプなどを用いる視覚表示、スピーカまたはブザーなどを用いる聴覚表示、またはそれらの組み合わせを採用することができる。
【００６５】
図１３は、実施の形態２に係る３次元データ生成処理の動作の一例を示すフローチャートである。図１３のフローチャートのうち、ステップＳ１１からステップＳ１６は、図１１と同様である。外形ベクトル生成部５の評価部５２は、外形ベクトルを生成するときに（ステップＳ２０）、外形ベクトルを生成できるかどうか判断する。
【００６６】
図１４は、実施の形態２に係る外形ベクトル生成処理の動作の一例を示すフローチャートである。図１４のフローチャートは、図１３のステップＳ２０の内容を示す。外形ベクトル生成部５は、２つの画像それぞれで閉領域の頂点を検出する（ステップＳ３１）。評価部５２は検出した頂点の数が所定の数、例えば３を超えるかどうか判断する（ステップＳ３２）。頂点の数が３以下の場合は（ステップＳ３２；ＮＯ）、外形生成不能を設定する（ステップＳ３６）。
【００６７】
頂点の数が３を超える場合（ステップＳ３２；ＹＥＳ）、閉領域の面積が基準値を超えるかどうか判断する（ステップＳ３３）。閉領域の面積が基準値以下の場合（ステップＳ３３；ＮＯ）、外形生成不能を設定する（ステップＳ３６）。
【００６８】
閉領域の面積が基準値を超える場合（ステップＳ３３；ＹＥＳ）、２つの画像の閉領域から検出した頂点の数の差が所定の値、例えば２より小さいかどうか判断する（ステップＳ３４）。頂点の数の差が所定の値（例えば２）以上の場合（ステップＳ３４；ＮＯ）、外形生成不能を設定する（ステップＳ３６）。所定の値を１、すなわち頂点の数が一致しない場合に外形生成不能を設定することにしてもよい。
【００６９】
頂点の数の差が所定の値より小さい場合（ステップＳ３４；ＹＥＳ）、それぞれの頂点列から外形ベクトルを生成する（ステップＳ３５）。所定の値を２としたとき、頂点の数の差が１の場合は、頂点同士の対応付けから残った一方の頂点を３次元データ計算から除外するか、その点に近い他方の外形ベクトル上の点を対応付けて３次元データ計算を行うことにする。また、閉領域の画像が画像回転部で回転されている場合、画像逆回転部５１は、生成した外形ベクトルを、画像の画素の並びとエッジの角度が画像回転部で抽出したエッジ強度の傾きになるように逆に回転させる。
【００７０】
図１３のフローチャートに戻って、外形ベクトル生成部５で外形生成不能が設定された場合（ステップＳ２１；ＮＯ）、生成不能表示部８は、外形ベクトルを生成できないことを表す情報を表示する（ステップＳ２２）。評価部５２で外形ベクトルを生成できると判断して、外形ベクトルが生成された場合（ステップＳ２１；ＹＥＳ）、外形ベクトル対応部６は、外形ベクトル生成部５で生成した外形ベクトルについて、同じ地点を示す頂点同士を対応付ける（ステップＳ２３）。
【００７１】
図１５は、実施の形態２に係る外形ベクトル対応処理の動作の一例を示すフローチャートである。図１５のフローチャートは、図１３のステップＳ２３の内容を示す。外形ベクトル対応部６は、頂点ベクトルの番号を表す変数ｉに１を設定し、評価変数Ｄに０を設定する（ステップＳ４１）。
【００７２】
一方の画像（例えば左画像）の変数ｉで指定される頂点ベクトルを選択する（ステップＳ４２）。例えば、頂点の数の少ない方の外形ベクトルから選択するとしてもよい。他の画像（例えば右画像）の頂点ベクトルのうち、一方の画像から選択した頂点ベクトルとの差（の絶対値）が最小のものを選択する（ステップＳ４３）。その最小の差をｄｍとする。そして、評価変数Ｄにｄｍを加算する（ステップＳ４４）。
【００７３】
番号変数ｉに１を加えて（ステップＳ４５）、一方の画像の残りの頂点があるかどうか調べる（ステップＳ４６）。残りの頂点があれば（ステップＳ４６；ＹＥＳ）、ステップＳ４２に戻って変数ｉで指定される頂点ベクトルｉを選択して同様の処理を繰り返す。残りの頂点がなければ（ステップＳ４６；ＮＯ）、評価変数Ｄが閾値を超えるかどうか調べる（ステップＳ４７）。
【００７４】
評価変数Ｄが閾値以下であれば（ステップＳ４７；ＹＥＳ）、実施の形態１と同様に外形ベクトルの対応を生成する（ステップＳ４８）。評価変数Ｄが閾値を超えている場合は（ステップＳ４７；ＮＯ）、対応付け不能を設定する（ステップＳ４９）。
【００７５】
図１３のフローチャートに戻って、外形ベクトルの対応付けができないと判定した場合（ステップＳ２４；ＮＯ）、生成不能表示部８は、指定点を含む領域から１つの構造物の外形ベクトルを生成できないこと（対応付け不能）を表す情報を表示する（ステップＳ２５）。外形ベクトルの対応付けができると判定した場合は（ステップＳ２４；ＹＥＳ）、実施の形態１と同様に、３次元データを計算する（ステップＳ１９）。
【００７６】
以上説明したように、本実施の形態２の３次元データ生成装置１によれば、２つの画像から対応付けできる外形ベクトルを生成できない場合に、外形ベクトルが生成できないことを表示するので、誤差の大きい３次元データを生成するのを防止できる。
【００７７】
図１６は、本発明の実施の形態に係る３次元データ生成装置１の物理的な構成の一例を示すブロック図である。
【００７８】
本実施の形態に係る３次元データ生成装置１は、一般的なコンピュータ装置と同様のハードウェア構成によって実現することができる。３次元データ生成装置１は、図１６に示すように、制御部２１、主記憶部２２、外部記憶部２３、操作部２４、表示部２５および入出力部２６を備える。主記憶部２２、外部記憶部２３、操作部２４、表示部２５および入出力部２６はいずれも内部バス２０を介して制御部２１に接続されている。
【００７９】
制御部２１はＣＰＵ（Central Processing Unit）等から構成され、外部記憶部２３に記憶されている制御プログラム３０に従って、３次元データ生成処理を実行する。
【００８０】
主記憶部２２はＲＡＭ（Random-Access Memory）等から構成され、外部記憶部２３に記憶されている制御プログラム３０をロードし、制御部２１の作業領域として用いられる。
【００８１】
外部記憶部２３は、フラッシュメモリ、ハードディスク、ＤＶＤ−ＲＡＭ（Digital Versatile Disc Random-Access Memory）、ＤＶＤ−ＲＷ（Digital Versatile Disc ReWritable）等の不揮発性メモリから構成され、前記の処理を制御部２１に行わせるための制御プログラム３０を予め記憶し、また、制御部２１の指示に従って、この制御プログラム３０が記憶するデータを制御部２１に供給し、制御部２１から供給されたデータを記憶する。
【００８２】
操作部２４はキーボードおよびマウスなどのポインティングデバイス等と、キーボードおよびポインティングデバイス等を内部バス２０に接続するインターフェース装置から構成されている。操作部２４を介して、画像データの入力、送受信などの指示、３次元データを生成する対象の構造物の領域の点の指定などが入力され、制御部２１に供給される。
【００８３】
表示部２５は、ＣＲＴ（Cathode Ray Tube）またはＬＣＤ（Liquid Crystal Display）などから構成され、画像や３次元データ生成処理された結果、または外形ベクトルを生成できないことを表示する。
【００８４】
入出力部２６は、無線送受信機、無線モデムまたは網終端装置、およびそれらと接続するシリアルインターフェースまたはＬＡＮ（Local Area Network）インターフェース等から構成されている。入出力部２６を介して、画像データを受信し、また計算した結果を送信する。
【００８５】
図１または図１２に示す３次元データ生成装置１の画像データ入力部２、位置指定部３、閉領域抽出部４、外形ベクトル生成部５、外形ベクトル対応部６および３次元データ計算部７の処理は、制御プログラム３０が、制御部２１、主記憶部２２、外部記憶部２３、操作部２４、表示部２５および入出力部２６などを資源として用いて処理することによって実行する。
【００８６】
その他、本発明の好適な変形として、以下の構成が含まれる。
【００８７】
本発明の第１の観点に係る３次元データ生成装置について、
好ましくは、前記画像から前記指定点を含む領域の色が所定の値以上変化する画素の並びであるエッジを抽出するエッジ抽出手段と、
前記エッジの端点またはエッジの角点から、該エッジを延長する直線または該エッジに直交する直線に沿って、他の前記エッジまたは前記画像の境界と最初に交わる点までの線分である分割線を生成する手段と、を備え、
前記閉領域抽出手段は、前記分割線および／または前記エッジで囲まれた連続する画素の集合である分割領域のうち、前記指定点との色の差が所定の範囲である隣り合う前記分割領域を結合して１つの前記閉領域を抽出する。
【００８８】
好ましくは、前記画像から前記指定点を含む領域の色が変化する画素の並びであるエッジを抽出するエッジ抽出手段を備え、
前記閉領域抽出手段は、前記画像の画素の並びに対する前記エッジの傾きを算出して、前記画像の画素の並びが前記エッジに平行または垂直になるように前記画像を回転させてから、前記閉領域を抽出し、
前記外形ベクトル抽出手段は、前記閉領域の輪郭を、前記画像の画素の並びと前記エッジの角度が前記エッジの傾きになるように逆に回転させて、前記外形ベクトルを抽出する。
【００８９】
好ましくは、前記３次元データ計算手段は、前記２つの画像のそれぞれの前記指定点から前記外形ベクトルの頂点へ向かうベクトルである頂点ベクトルのうち、前記２つの画像からそれぞれ１つずつ選択した前記頂点ベクトルの差の絶対値の、すべての前記頂点ベクトルについての和が最小になる組合せで、前記２つの画像の外形ベクトルの頂点を対応づける。
【００９０】
好ましくは、前記２つの画像からそれぞれ１つずつ選択した前記頂点ベクトルの差の絶対値の、すべての前記頂点ベクトルについての和の最小値が所定の値を超える場合に、前記指定点を含む領域から１つの構造物の外形ベクトルを生成できないことを表す情報を表示する手段を備える。
【００９１】
好ましくは、前記２つの画像のそれぞれにおいて、前記外形ベクトルの頂点が３以下の場合、もしくは、前記外形ベクトルで囲まれる画素の数が所定の数より少ない場合、または、前記２つの画像のそれぞれで抽出した輪郭線の頂点の数の差が所定の値を超える場合に、前記指定点を含む領域から外形ベクトルを生成できないことを表す情報を表示する手段を備える。
【００９２】
本発明の第２の観点に係る３次元データ生成方法について、
好ましくは、前記画像から前記指定点を含む領域の色が所定の値以上変化する画素の並びであるエッジを抽出するエッジ抽出ステップと、
前記エッジの端点またはエッジの角点から、該エッジを延長する直線または該エッジに直交する直線に沿って、他の前記エッジまたは前記画像の境界と最初に交わる点までの線分である分割線を生成するステップと、を備え、
前記閉領域抽出ステップは、前記分割線および／または前記エッジで囲まれた連続する画素の集合である分割領域のうち、前記指定点との色の差が所定の範囲である隣り合う前記分割領域を結合して１つの前記閉領域を抽出する。
【００９３】
好ましくは、前記画像から前記指定点を含む領域の輝度または色が変化する画素の並びであるエッジを抽出するエッジ抽出ステップを備え、
前記閉領域抽出ステップは、前記画像の画素の並びに対する前記エッジの傾きを算出して、前記画像の画素の並びが前記エッジに平行または垂直になるように前記画像を回転させてから、前記閉領域を抽出し、
前記外形ベクトル抽出ステップは、前記閉領域の輪郭を、前記画像の画素の並びと前記エッジの角度が前記エッジの傾きになるように逆に回転させて、前記外形ベクトルを抽出する。
【００９４】
好ましくは、前記３次元データ計算ステップは、前記２つの画像のそれぞれの前記指定点から前記外形ベクトルの頂点へ向かうベクトルである頂点ベクトルのうち、前記２つの画像からそれぞれ１つずつ選択した前記頂点ベクトルの差の絶対値の、すべての前記頂点ベクトルについての和が最小になる組合せで、前記２つの画像の外形ベクトルの頂点を対応づける。
【００９５】
好ましくは、前記２つの画像からそれぞれ１つずつ選択した前記頂点ベクトルの差の絶対値の、すべての前記頂点ベクトルについての和の最小値が所定の値を超える場合に、前記指定点を含む領域から１つの構造物の外形ベクトルを生成できないことを表す情報を表示する。
【００９６】
好ましくは、前記２つの画像のそれぞれにおいて、前記外形ベクトルの頂点が３以下の場合、もしくは、前記外形ベクトルで囲まれる画素の数が所定の数より少ない場合、または、前記２つの画像のそれぞれで抽出した輪郭線の頂点の数の差が所定の値を超える場合に、前記指定点を含む領域から外形ベクトルを生成できないことを表す情報を表示する。
【００９７】
その他、前記のハードウエェア構成やフローチャートは一例であり、任意に変更および修正が可能である。
【００９８】
制御部２１、主記憶部２２、外部記憶部２３、操作部２４、入出力部２６および内部バス２０などから構成される３次元データ生成装置１の処理を行う中心となる部分は、専用のシステムによらず、通常のコンピュータシステムを用いて実現可能である。たとえば、前記の動作を実行するためのコンピュータプログラムを、コンピュータが読み取り可能な記録媒体（フレキシブルディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ等）に格納して配布し、当該コンピュータプログラムをコンピュータにインストールすることにより、前記の処理を実行する３次元データ生成装置１を構成してもよい。また、インターネット等の通信ネットワーク上のサーバ装置が有する記憶装置に当該コンピュータプログラムを格納しておき、通常のコンピュータシステムがダウンロード等することで３次元データ生成装置１を構成してもよい。
【００９９】
また、３次元データ生成装置１の機能を、ＯＳ（オペレーティングシステム）とアプリケーションプログラムの分担、またはＯＳとアプリケーションプログラムとの協働により実現する場合などには、アプリケーションプログラム部分のみを記録媒体や記憶装置に格納してもよい。
【０１００】
また、搬送波にコンピュータプログラムを重畳し、通信ネットワークを介して配信することも可能である。たとえば、通信ネットワーク上の掲示板(BBS, Bulletin Board System)に前記コンピュータプログラムを掲示し、ネットワークを介して前記コンピュータプログラムを配信してもよい。そして、このコンピュータプログラムを起動し、ＯＳの制御下で、他のアプリケーションプログラムと同様に実行することにより、前記の処理を実行できるように構成してもよい。
【符号の説明】
【０１０１】
１  ３次元データ生成装置
２  画像データ入力部
３  位置指定部
４  閉領域抽出部
５  外形ベクトル生成部
６  外形ベクトル対応部
７  ３次元データ計算部
８  生成不能表示部
２１  制御部
２２  主記憶部
２３  外部記憶部
２４  操作部
２５  表示部
２６  入出力部
３０  制御プログラム
３１  画像回転部
３２  エッジ抽出部
３３  分割線生成部
３４  閉領域生成部
５１  画像逆回転部
５２  評価部
６１  対応判定部
【図１】
2011048507.tif 000003
【図２】
2011048507.tif 000004
【図６】
2011048507.tif 000005
【図７】
2011048507.tif 000006
【図８】
2011048507.tif 000007
【図９】
2011048507.tif 000008
【図１０】
2011048507.tif 000009
【図１１】
2011048507.tif 000010
【図１２】
2011048507.tif 000011
【図１３】
2011048507.tif 000012
【図１４】
2011048507.tif 000013
【図１５】
2011048507.tif 000014
【図１６】
2011048507.tif 000015
【図３】
2011048507.tif 000016
【図４】
2011048507.tif 000017
【図５】
2011048507.tif 000018