(57)【要約】【課題】正しい形状を獲得可能とし、形状精度、及び物体の分離精度を向上させる形状獲得技術を提供する。【解決手段】レイヤ生成装置２は、３次元の点集合をレイヤにグループ分けする。連結検出装置３は、各レイヤに対し、画像上で同一の線分に乗っている点集合（連結点集合）を見つけ出す。クラスタ生成装置４は、同じ連結点集合に含まれる点同士が同一クラスに含まれるようにグループ分けしてクラスタを生成する。３次元モデル生成装置５は、クラスタ生成装置４で生成されたクラスタから凸包を形成し、それぞれの凸包を上面形状とする柱状形状として３次元形状を生成する。【選択図】  図１
2004240599.tif 000002
【特許請求の範囲】
【請求項１】
画像から得た３次元の点集合と２次元の線分集合から、元の形状を復元する方法であって、
３次元の点集合を層状に第１のグループ分けをする手順と、
該層状の各グループに対し、画像上で同一の線分に乗る点集合を見つける手順と、
該点集合に含まれる点が同じグループに属するように第２のグループ分けをする手順と、
該第２のグループ分けをする手順で得られたグループ集合から形状モデルを生成するモデル生成手順と、を備えることを特徴とする形状獲得方法。
【請求項２】
画像から得た３次元の点集合と２次元の色別領域から、元の形状を復元する方法であって、
３次元の点集合を層状に第１のグループ分けをする手順と、
該層状の各グループに対し、画像上で同一の色別領域に含まれる点集合を見つける手順と、
該点集合に含まれる点が同じグループに属するように第２のグループ分けをする手順と、
該第２のグループ分けをする手順で得られたグループ集合から形状モデルを生成するモデル生成手順と、を備えることを特徴とする形状獲得方法。
【請求項３】
画像から得た３次元の点集合と２次元の線分集合から、元の形状を復元する方法であって、
３次元の点集合を層状に第１のグループ分けをする手順と、
該層状の各グループに対し、画像上で同一の線分に乗る点集合Ａを見つけるとともに、画像上で同一の色別領域に含まれる点集合Ｂを見つける手順と、
該点集合Ａと該点集合Ｂの加集合（Ａ∪Ｂ）に含まれる点が同じグループに属するように第２のグループ分けをする手順と、
該第２のグループ分けをする手順で得られたグループ集合から形状モデルを生成するモデル生成手順と、を備えることを特徴とする形状獲得方法。
【請求項４】
画像から得た３次元の点集合と２次元の線分集合から、元の形状を復元する方法であって、
３次元の点集合を層状に第１のグループ分けをする手順と、
該層状の各グループに対し、画像上で同一の線分に乗る点集合Ａを見つけるとともに、画像上で同一の色別領域に含まれる点集合Ｂを見つける手順と、
該点集合Ａと該点集合Ｂの積集合（Ａ∩Ｂ）に含まれる点が同じグループに属するように第２のグループ分けをする手順と、
該第２のグループ分けをする手順で得られたグループ集合から形状モデルを生成するモデル生成手順と、を備えることを特徴とする形状獲得方法。
【請求項５】
請求項２ないし４に記載の形状獲得方法において、
第２のグループ分けをする手順は、
複数のセンサから得られた複数の画像情報を、それぞれ異なる色情報と見なして色別領域を抽出する手順を備えることを特徴とする形状獲得方法。
【請求項６】
画像から得た３次元の点集合と２次元の線分集合から、元の形状を復元する装置であって、
３次元の点集合を層状に第１のグループ分けをする手段と、
該層状の各グループに対し、画像上で同一の線分に乗る点集合を見つける手段と、
該点集合に含まれる点が同じグループに属するように第２のグループ分けをする手段と、
該第２のグループ分けをする手段で得られたグループ集合から形状モデルを生成するモデル生成手段と、を備えることを特徴とする形状獲得装置。
【請求項７】
画像から得た３次元の点集合と２次元の色別領域から、元の形状を復元する装置であって、
３次元の点集合を層状に第１のグループ分けをする手段と、
該層状の各グループに対し、画像上で同一の色別領域に含まれる点集合を見つける手段と、
該点集合に含まれる点が同じグループに属するように第２のグループ分けをする手段と、
該第２のグループ分けをする手段で得られたグループ集合から形状モデルを生成するモデル生成手段と、を備えることを特徴とする形状獲得装置。
【請求項８】
画像から得た３次元の点集合と２次元の線分集合から、元の形状を復元する装置であって、
３次元の点集合を層状に第１のグループ分けをする手段と、
該層状の各グループに対し、画像上で同一の線分に乗る点集合Ａを見つけるとともに、画像上で同一の色別領域に含まれる点集合Ｂを見つける手段と、
該点集合Ａと該点集合Ｂの加集合（Ａ∪Ｂ）に含まれる点が同じグループに属するように第２のグループ分けをする手段と、
該第２のグループ分けをする手段で得られたグループ集合から形状モデルを生成するモデル生成手段と、を備えることを特徴とする形状獲得装置。
【請求項９】
画像から得た３次元の点集合と２次元の線分集合から、元の形状を復元する装置であって、
３次元の点集合を層状に第１のグループ分けをする手段と、
該層状の各グループに対し、画像上で同一の線分に乗る点集合Ａを見つけるとともに、画像上で同一の色別領域に含まれる点集合Ｂを見つける手段と、
該点集合Ａと該点集合Ｂの積集合（Ａ∩Ｂ）に含まれる点が同じグループに属するように第２のグループ分けをする手段と、
該第２のグループ分けをする手段で得られたグループ集合から形状モデルを生成するモデル生成手段と、を備えることを特徴とする形状獲得装置。
【請求項１０】
請求項７ないし９に記載の形状獲得装置において、
第２のグループ分けをする手段は、
複数のセンサから得られた複数の画像情報を、それぞれ異なる色情報と見なして色別領域を抽出する手段を備えることを特徴とする形状獲得装置。
【請求項１１】
請求項１乃至５のいずれかに記載の形状獲得方法における手順を、コンピュータに実行させるためのプログラムとしたことを特徴とする形状獲得プログラム。
【請求項１２】
請求項１乃至５のいずれかに記載の形状獲得方法における手順を、コンピュータに実行させるためのプログラムとし、
該プログラムを、該コンピュータが読み取りできる記録媒体に記録したことを特徴とする形状獲得プログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、２次元の線分情報もしくは色情報を使うことで、３次元の点の間に連結関係を見つけ出し、３次元形状を獲得する方法、及び装置に関するものである。
【０００２】
【従来の技術】
実在する多くの３次元物体は複雑な形状をしているが、３次元物体を水平及び垂直の面から構成されると見なし、形状モデルを作成することは、実世界を単純化し、計算機（コンピュータ）によって実世界をより簡単に扱う方法として、広く利用されている。画像から水平及び垂直の面により構成される３次元形状を獲得し、利用する例としては、具体的には以下のようなものが挙げられる。
・上空から撮影された航空写真から建物の形状を獲得して行う地図の作成（図１３）、
・監視カメラに移った物体の認識、
・工業用ロボットが対象物を加工する際の位置決め。
【０００３】
ここで述べる「画像」とは一般的なＣＣＤカメラによって撮像されたものだけではなく、レーザープロファイラによるＤＳＭ（Ｄｉｇｉｔａｌ  Ｓｕｒｆａｃｅ  Ｍｏｄｅｌ）や超音波の診断結果など、対象を観測することによって得られた数値情報が「画素値」として２次元平面上に広がっているデータであれば「画像」として扱うことができる。
【０００４】
物体表面の点の３次元位置を得るには、撮影方向の異なる複数枚の画像や一連の映像シーケンスから、人間の知覚・認識手法と同様の方法により３次元形状を得る方法が知られている。つまり、人間が両眼の視差から物体形状を得ることに相当するステレオ画像法や、運動している物体を撮影した映像から、物体の各部分がどのように移動しているかで物体形状を得る、オプティカルフロー、といった手法がある。
【０００５】
以下の説明では、３次元位置を持つ点の集合を３次元点集合と呼ぶことにする。本発明の説明にあたって、３次元点集合は以下に説明する３軸の直交座標系ｘｙｚに対して、位置が定められているとする（図１４）。３次元点集合の計測時の方向と平行にｚ軸を設定する。向きは計測方向とは逆とし、手前にある点や面ほどｚ値が大きくなるものとする．ｘ軸及びｙ軸は互いに直交していれば、任意の向きでよい。ｘｙ平面と平行な面を水平、ｘｙ平面と垂直な面を垂直と呼ぶことにする。
【０００６】
３次元点集合から、垂直及び水平面からなる形状モデルを作成する手法は、参考文献［１］（「特願２００２−５５２１１「形状モデル生成方法及び装置、並びにこの方法の実行プログラムとこの実行プログラムを記録した記録媒体」  日本電信電話株式会社）や非特許文献１にあるレイヤ及びクラスタと呼ばれる集合を用いるものがある。この手法の流れを図１５に示す。レイヤとはほぼ同じ高さの点を集めた集合であり、クラスタとはもとのモデル形状において同一の面に属すると考えられる点の集合である。クラスタの生成方法については後述する。
【０００７】
この従来手法のブロック図を図１６に示す。従来手法では、３次元点集合データベース１０１の３次元の点集合全体を、まずレイヤ生成装置１０２によって、ほぼ同じ高さを持つ点の集合、レイヤ、に分割する（ステップ１）。次に、クラスタ生成装置１０３によって各レイヤを平面上で分割し、クラスタを構成する（ステップ２）。３次元モデル生成装置１０４は、各クラスタを包含する水平面上の２次元図形を上面形状とし、その図形の各辺に垂直面を付加することで、個々のクラスタに対し、柱状の３次元モデルを作成し（ステップ３）、出力装置１０５から出力する。
【０００８】
上記の手法において、形状を正しく生成するにはクラスタの生成方法が重要となる。参考文献［１］や非特許文献１では、同一のレイヤの中で距離が近い点を集めていき、集めた点の２次元形状がより低いレイヤの点を含まないようにするという制約を加えることで、点の上下関係に矛盾のない上面形状を見つける方法が提案されている。例えば、図１７では同一のレイヤに二つのクラスタＡ，Ｂが生成されている。そのとき、そのＡ，Ｂを包含する凸包が、より低いレイヤの点を包含するので、Ａ，Ｂは別の面であると認識できる。
【０００９】
また、別のクラスタ生成方法としては、画像から線分を抽出し、線分が連結されることによって形成される輪郭を見つけ出し、上面形状とする方法がある（図１８、非特許文献２）。また、別のクラスタ生成方法としては、カラー画像に対して、色に基づく領域分割を行い（非特許文献３）、同一の色別領域を上面形状とする方法が考えられる（非特許文献４）。
【００１０】
【非特許文献１】
「３次元特徴点集合に基づく建物モデル復元手法の一検討」石川裕治、宮川熟、若林佳織、有川知彦  電子情報通信学会  ２００２年度総合大会  情報・システム講演論文集２，２２９ページ
【００１１】
【非特許文献２】
“Ｍｕｌｔｉ−Ｉｍａｇｅ  Ｍａｔｃｈｉｎｇ  Ｕｓｉｎｇ  Ｓｅｇｍｅｎｔ  Ｆｅａｔｕｒｅｓ”，  Ｊｕｌｉａｎｇ  Ｓｈａｏ，  Ｒｏｇｅｒ  Ｍｏｈｒ，  ａｎｄ  Ｃｌｉｖｅ  Ｆｒａｓｅｒ，  ＩＡＰＲＳ，  Ｖｏｌ．  ＸＸＸＩＩＩ，  Ｐａｒｔ  Ｂ３．  ｐｐ．８３７−８４４，  ２０００
【００１２】
【非特許文献３】
「コンピュータビジョン：技術評論と将来展望」第５章、富永昌治、新技術コミュニケーションズ、１９９８
【００１３】
【非特許文献４】
“Ｔｈｅ  Ｒｏｌｅ  ｏｆ  Ｃｏｌｏｒ  Ａｔｔｒｉｂｕｔｅｓ  ａｎｄ  Ｓｉｍｉｌａｒｉｔｙ  Ｇｒｏｕｐｉｎｇ  ｉｎ  ３−Ｄ  ＢｕｉｌｄｉｎｇＲｅｃｏｎｓｔｒｕｃｔｉｏｎ”，  Ｏｌｏｆ  Ｈｅｎｒｉｃｓｓｏｎ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ  ａｎｄ  Ｉｍａｇｅ  Ｕｎｄｅｒｓｔａｎｄｉｎｇ，  Ｖｏｌ．  ７２，  Ｎ０．２，  ｐｐ．１６３−１８４，  １９９８
【００１４】
【発明が解決しようとする課題】
上記で述べた以下の３つの上面形状の生成方法
１．距離が近い点を集めていき、集めた点の２次元形状がより低いレイヤの点を含まないように上面形状を見つける方法
２．画像から線分を抽出し、線分の連結によって輪郭を生成し、上面形状とする方法
３．画像から同一の色を持つ領域を抽出し、その領域の形状を上面形状とする方法
には、それぞれ以下のような問題点がある。
【００１５】
まず第一の方法では、距離が近い点から順に同一クラスタに属するようにグループ分けを行う。そのため、対象物が隣接して距離が非常に近い場合、点ｐ，ｑが違う対象物に属する点であっても、ｐ，ｑは同一のクラスタに集められる。結果として、対象物の形状を正しく抽出することができなくなる（図１９）。
【００１６】
次に第二の方法では、対象物のコントラストが明瞭でない場合に、輪郭に含まれる線分を部分的にしか抽出できず、輪郭を形成できない。また、上面形状の内部に、模様、あるいは線状の設置物が写っていた場合、それらからも線分が抽出され、線分を連結して輪郭を生成することが難しくなる（図２０）。
【００１７】
最後に第三の方法では、対象物全体が同じ色をしていないと利用できないという問題点があり、さらに同じ色をしている場合でも、他の物体の影などが物体表面にある場合には、同一の面が過剰に多くの領域に分割される（図２１）。この場合、機械的に領域を統合し、同一の面を見つけ出すことが難しくなる。
【００１８】
本発明は、上記従来技術の問題点を解決するためになされたものであり、形状を表すのに部分的な線分集合や色情報しか得られない場合であっても、正しい形状を獲得可能とし、形状精度、及び物体の分離精度を向上させる形状獲得の技術を提供することを課題とする。
【００１９】
【課題を解決するための手段】
上記の課題を解決するために本発明は、画像から得た３次元の点集合と２次元の線分集合から、元の形状を復元する方法であって、３次元の点集合を層状に第１のグループ分けをする手順と、該層状の各グループに対し、画像上で同一の線分に乗る点集合を見つける手順と、該点集合に含まれる点が同じグループに属するように第２のグループ分けをする手順と、該第２のグループ分けをする手順で得られたグループ集合から形状モデルを生成するモデル生成手順と、を備えることを特徴とする形状獲得方法を、その解決の手段とする。
【００２０】
あるいは、画像から得た３次元の点集合と２次元の色別領域から、元の形状を復元する方法であって、３次元の点集合を層状に第１のグループ分けをする手順と、該層状の各グループに対し、画像上で同一の色別領域に含まれる点集合を見つける手順と、該点集合に含まれる点が同じグループに属するように第２のグループ分けをする手順と、該第２のグループ分けをする手順で得られたグループ集合から形状モデルを生成するモデル生成手順と、を備えることを特徴とする形状獲得方法を、その解決の手段とする。
【００２１】
あるいは、画像から得た３次元の点集合と２次元の線分集合から、元の形状を復元する方法であって、３次元の点集合を層状に第１のグループ分けをする手順と、該層状の各グループに対し、画像上で同一の線分に乗る点集合Ａを見つけるとともに、画像上で同一の色別領域に含まれる点集合Ｂを見つける手順と、該点集合Ａと該点集合Ｂの加集合（Ａ∪Ｂ）に含まれる点が同じグループに属するように第２のグループ分けをする手順と、該第２のグループ分けをする手順で得られたグループ集合から形状モデルを生成するモデル生成手順と、を備えることを特徴とする形状獲得方法を、その解決の手段とする。
【００２２】
あるいは、画像から得た３次元の点集合と２次元の線分集合から、元の形状を復元する方法であって、３次元の点集合を層状に第１のグループ分けをする手順と、該層状の各グループに対し、画像上で同一の線分に乗る点集合Ａを見つけるとともに、画像上で同一の色別領域に含まれる点集合Ｂを見つける手順と、該点集合Ａと該点集合Ｂの積集合（Ａ∩Ｂ）に含まれる点が同じグループに属するように第２のグループ分けをする手順と、該第２のグループ分けをする手順で得られたグループ集合から形状モデルを生成するモデル生成手順と、を備えることを特徴とする形状獲得方法を、その解決の手段とする。
【００２３】
あるいは、上記の形状獲得方法において、第２のグループ分けをする手順は、複数のセンサから得られた複数の画像情報を、それぞれ異なる色情報と見なして色別領域を抽出する手順を備えることを特徴とする形状獲得方法を、その解決の手段とする。
【００２４】
あるいは、画像から得た３次元の点集合と２次元の線分集合から、元の形状を復元する装置であって、３次元の点集合を層状に第１のグループ分けをする手段と、該層状の各グループに対し、画像上で同一の線分に乗る点集合を見つける手段と、該点集合に含まれる点が同じグループに属するように第２のグループ分けをする手段と、該第２のグループ分けをする手段で得られたグループ集合から形状モデルを生成するモデル生成手段と、を備えることを特徴とする形状獲得装置を、その解決の手段とする。
【００２５】
あるいは、画像から得た３次元の点集合と２次元の色別領域から、元の形状を復元する装置であって、３次元の点集合を層状に第１のグループ分けをする手段と、該層状の各グループに対し、画像上で同一の色別領域に含まれる点集合を見つける手段と、該点集合に含まれる点が同じグループに属するように第２のグループ分けをする手段と、該第２のグループ分けをする手段で得られたグループ集合から形状モデルを生成するモデル生成手段と、を備えることを特徴とする形状獲得装置を、その解決の手段とする。
【００２６】
あるいは、画像から得た３次元の点集合と２次元の線分集合から、元の形状を復元する装置であって、３次元の点集合を層状に第１のグループ分けをする手段と、該層状の各グループに対し、画像上で同一の線分に乗る点集合Ａを見つけるとともに、画像上で同一の色別領域に含まれる点集合Ｂを見つける手段と、該点集合Ａと該点集合Ｂの加集合（Ａ∪Ｂ）に含まれる点が同じグループに属するように第２のグループ分けをする手段と、該第２のグループ分けをする手段で得られたグループ集合から形状モデルを生成するモデル生成手段と、を備えることを特徴とする形状獲得装置を、その解決の手段とする。
【００２７】
あるいは、画像から得た３次元の点集合と２次元の線分集合から、元の形状を復元する装置であって、３次元の点集合を層状に第１のグループ分けをする手段と、該層状の各グループに対し、画像上で同一の線分に乗る点集合Ａを見つけるとともに、画像上で同一の色別領域に含まれる点集合Ｂを見つける手段と、該点集合Ａと該点集合Ｂの積集合（Ａ∩Ｂ）に含まれる点が同じグループに属するように第２のグループ分けをする手段と、該第２のグループ分けをする手段で得られたグループ集合から形状モデルを生成するモデル生成手段と、を備えることを特徴とする形状獲得装置を、その解決の手段とする。
【００２８】
あるいは、上記の形状獲得装置において、第２のグループ分けをする手段は、複数のセンサから得られた複数の画像情報を、それぞれ異なる色情報と見なして色別領域を抽出する手段を備えることを特徴とする形状獲得装置を、その解決の手段とする。
【００２９】
あるいは、上記の形状獲得方法における手順を、コンピュータに実行させるためのプログラムとしたことを特徴とする形状獲得プログラムを、その解決の手段とする。
【００３０】
あるいは、上記の形状獲得方法における手順を、コンピュータに実行させるためのプログラムとし、該プログラムを、該コンピュータが読み取りできる記録媒体に記録したことを特徴とする形状獲得プログラムを記録した記録媒体を、その解決の手段とする。
【００３１】
本発明では、画像から線分や色別領域を抽出し、同一のレイヤ内に含まれる点の間で、同じ線分上にある点の集合（連結点集合）や色別領域内にある点の集合（連結点集合）を見つけ出し、同じ連結点集合に含まれる点同士が、同一のクラスタに含まれるように優先的にグルーピングを行い、情報を統合してクラスタを生成することにより、形状を表すのに部分的な線分集合や色情報しか得られない場合であっても、正しい形状の獲得を可能とする。また、線分集合、色別領域、３次元点集合のどれかしか利用しない場合に比べて、形状精度、及び物体の分離精度を向上させる。
【００３２】
【発明の実施の形態】
以下、本発明の実施の形態について図を用いて詳細に説明する。
【００３３】
本発明の一実施形態による構成を図１に示す。本実施形態は、３次元点集合データベース１、レイヤ生成装置２、連結検出装置３、クラスタ生成装置４、３次元モデル生成装置５、出力装置６、から構成される。このうち、本発明によって追加または変更された装置は連結検出装置３、クラスタ生成装置４、である。よって、以下、この２つの装置について説明する。それ以外の装置の機能や動作は図１７の従来技術での同じ名称の装置と同じであるとする。
【００３４】
連結検出装置３は、画像から線分を抽出し、同一のレイヤ内に含まれる点の間で、同じ線分上にある点の集合（連結点集合）を見つけ出す。なお、線分は直線状のものとは限らず、連続する曲線であっても良い。また、同じ一色が連続する領域を抽出し、領域内にある点の集合を見つけ出すことで、連結点集合を生成しても良い。さらに、線分と色別領域の両方を用いて連結点集合を生成しても良い。ここで、色情報とは可視光の色に限らず、複数のセンサから得られた異なる輝度値情報を組み合わせた画像情報であっても良い。
【００３５】
クラスタ生成装置４では、同じ連結点集合に含まれる点同士が、同一のクラスタに含まれるように優先的にグルーピングを行って、クラスタを生成する。線分を用いた連結点集合Ａと色別領域を用いた連結点集合Ｂが生成された場合には、両者の加集合（Ａ∪Ｂ）や積集合（Ａ∩Ｂ）に含まれる点同士が、同一のクラスタに含まれるように優先的にグルーピングを行う。
【００３６】
以上の工夫により、線分集合や色別領域の情報またはその両方の情報を３次元点集合の情報に加えることで、それぞれの情報を単独で利用した場合より、正しい上面形状を生成することができる。
【００３７】
本実施形態では既存の技術（非特許文献１等）を使って、異なる方向から対象物を撮影した複数枚の画像から、３次元点集合が既に抽出されているものとし、高さ別のグルーピングにより、レイヤが既に生成されているものとする。
【００３８】
連結検出装置３の処理の流れを図２に示す。
【００３９】
連結検出装置３ではレイヤ生成装置２からレイヤ集合｛Ｌｉ｝を入力として受け取る。最初に３次元点集合の各点に対し、画像Ｉ上での２次元座標を求める。
元々の３次元点集合｛ｐ｝はＩを含む複数枚の画像から獲得されているため、各点ｐに対して各画像において写っている位置（つまり画像上の２次元座標）を求めることができる。次に、３次元点集合を生成する際に用いた画像Ｉから線分を抽出し、保存しておく。すべてのレイヤに対して同じ線分集合｛ｅｉ｝を繰り返し使うため、最初に線分を抽出し、保存しておくことで処理の効率を向上させることができる。線分を抽出する既存技術は多数提案されており、例えば、参考文献［２］（「局所領域内のＨｏｕｇｈ変換を用いた高速な直線検出法」、村上和人、成瀬正、電子情報通信学会論文誌、Ｄ−ＩＩ，Ｖｏｌ．Ｊ８３−Ｄ−ＩＩ，Ｎｏ．３，ｐｐ．９１８−９２６．２０００）などがある。
【００４０】
次に各レイヤＬｉについて、線分ｅｉ上に乗っている点の集合（連結点集合）を見つけ出し、保存する。この処理中、連結点集合は見つかり次第、順次Ｌｉから取り除くこととし、連結点集合同士に重複した要素を持たないようにする。連結点集合の生成を各レイヤに対して行った後、レイヤ毎に保存されているすべての連結点集合を出力し、処理を終了する。
【００４１】
ここでは連結点集合を線分集合に基づいて生成したが、色情報を用いる場合には、線分を抽出する処理で、同一の色を持つ領域を画像Ｉから生成しておき、線分上に乗っている点の集合を見つける処理で、同一の色別領域に含まれる点の集合を見つけるようにすればよい。なお、連結点集合は線分を利用した結果と色情報を利用した結果を合わせて生成しても良い。例えば、同一の線分に乗り、かつ同一の色別領域にある点集合だけを連結点集合とする、といった方法により同一の面にある点集合かどうかをより厳密に判定することも考えられる。
【００４２】
色情報は、可視光によるＲＧＢ情報を用いても良く、また、例えば、人工衛星から得られたマルチスペクトル情報を利用しても良い。
【００４３】
連結検出装置３の処理結果の例を示す。まず、図３に抽出された線分集合｛ｅｉ｝と、３次元点集合の各点の画像Ｉにおける２次元座標を示す。これら二つの処理結果から、連結点集合を求めた結果を図４に示す。各線分ｅｉから得られた連結点集合がＣｉとなっている。図３の各線分は画像中の上の方から順に処理を行い、その結果、線分ｅ１とｅ２に共通して乗っている点はｅ１に優先して含まれている。
【００４４】
クラスタ生成装置４の処理の流れを図５、図６に示す。クラスタの生成処理は、従来技術の非特許文献１に示された処理に対し、初期クラスタの生成ステップを変更したものとして実現されている。つまり、連結点集合が同一のクラスタとなるように、各連結点集合を初期のクラスタとし、その後、連結点集合に含まれない各点をそれぞれ一つのクラスタとして、クラスタ集合に加えるようにしている（図５）。その後のクラスタ生成処理は、距離が近い点同士で、それぞれの点が所属するクラスタの併合を順次試みる処理である（図６）。
【００４５】
なお、各クラスタに対して生成される上面形状は凸包と限るものではなく、例えば工業用部品や建物などの撮影対象が決まっており、形状が例えば長方形だと分かっているような場合は、そうした知識を利用して、外接最小長方形を凸包の代わりに利用することも考えられる。
【００４６】
クラスタ生成装置４の処理の例を示す。クラスタ生成装置４は各レイヤに対して同じ処理を行うため、本実施形態では図３のレイヤＬ１に属する点への処理だけを詳細に説明する。
【００４７】
まず、初期のクラスタ集合を図７に示す。図４の連結点集合の生成結果｛Ｃ１，…，Ｃ７｝に、連結点集合に含まれない各点をクラスタとした｛Ｃ８，…，Ｃ１２｝を加えた｛Ｃ１，…，Ｃ１２｝を初期のクラスタ集合とする。引き続いて行われるクラスタの併合処理では、異なるクラスタに属する点の組としては、Ｃ４の左端の点とＣ５の上の点がもっとも近い距離にあるため、この二つのクラスタが最初に併合され、クラスタＣ４５が生成される（図８）。Ｃ２の下の点とＣ３の右端の点が次に近い距離にあるため、この二つのクラスタが続いて併合され、クラスタＣ２３が生成される。
【００４８】
同様の規則により次にＣ２３とＣ４５が併合されるが、併合後に生成される凸包が下位レイヤの点を包含しているため、このクラスタは正しい形状ではないと判断され、併合は取りやめられる（図９）。つづいてＣ２３とＣ１が併合され、Ｃ１２３が生成される。以下同様にして、クラスタが順次併合され、最終的に２つのクラスタに併合される（図１０）。
【００４９】
３次元モデル生成装置５は、それぞれのクラスタから凸包を生成し、それぞれの凸包を上面形状とする柱状形状として３次元形状を生成する。
【００５０】
［応用分野］
本発明は、例えば以下のような利用が考えられる。
・複数枚の航空写真や上空からの空撮映像から、建物の３次元形状を高精度かつ自動で獲得し、広域の３次元都市モデルを構築することができる。生成結果の一例として、図１１に示す地域をモデル生成対象領域とした場合に、線分情報を利用した場合（ｂ）と、しない場合（ａ）の両方を図１２に示す。元の空撮画像と比較して、線分情報を利用した場合の方が正しい建物形状を生成できていることが分かる。
・工業用ロボットのカメラから得られる画像に対して適用し、加工対象となる部品に対してく他の物体と区別し、正しく形状をとらえ、位置決めをすることができる。
【００５１】
なお、図１で示した各部の一部もしくは全部の機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータを用いて実行して本発明を実現することができること、あるいは、図１、図２、図５、及び図６等を用いて示した処理の手順をコンピュータのプログラムで構成し、そのプログラムをコンピュータに実行させることができることは言うまでもなく、コンピュータでその機能を実現するためのプログラム、あるいは、コンピュータにその処理の手順を実行させるためのプログラムを、そのコンピュータが読み取り可能な記録媒体、例えば、フレキシブルディスクや、ＭＯ、ＲＯＭ、メモリカード、ＣＤ、ＤＶＤ、リムーバブルディスクなどに記録して、保存したり、配布したりすることが可能である。また、上記のプログラムをインターネットや電子メールなど、ネットワークを通して提供することも可能である。このように、記録媒体やネットワークにより提供されたプログラムをコンピュータにインストールすることで、本発明が実施可能となる。
【００５２】
【発明の効果】
本発明によれば、形状を表すのに部分的な線分集合や色情報しか得られない場合であっても、正しい形状を獲得することができる。また、線分集合、色別領域、３次元点集合のどれかしか利用しない場合に比べて、情報を統合してクラスタの生成を行うため、形状精度の向上、物体の分離精度の向上が可能である。
【図面の簡単な説明】
【図１】本発明の一実施形態を示すブロック図
【図２】上記実施形態における連結検出装置の処理の流れ図
【図３】（ａ），（ｂ），（ｃ），（ｄ）は、上記実施形態における連結検出装置の処理結果の例（線分集合と点の２次元位置）を示す図
【図４】上記連結検出装置の処理結果の例（連結点集合の生成結果）を示す図
【図５】上記クラスタ生成装置の処理の流れ図（初期クラスタ集合の生成）
【図６】上記クラスタ生成装置の処理の流れ図（クラスタの段階的併合）
【図７】初期クラスタ集合の例を示す図
【図８】クラスタ併合処理の例（１）を示す図
【図９】クラスタ併合処理の例（２）を示す図
【図１０】（ａ），（ｂ）は、クラスタ及び３次元形状生成結果を示す図
【図１１】空撮画像の例を示す図
【図１２】（ａ），（ｂ）は、空撮映像からの３次元建物形状復元例を示す図
【図１３】３次元形状獲得技術の利用例を示す図
【図１４】３次元点集合の座標系を示す図
【図１５】従来の点集合に基づく３次元形状獲得手法の説明図
【図１６】従来の点集合に基づく３次元形状獲得手法のブロック図
【図１７】（ａ），（ｂ）は、上下関係の制約導入に関する説明図
【図１８】従来の線分に基づく３次元形状獲得手法の説明図
【図１９】点集合に基づくクラスタリングの失敗例を示す図
【図２０】（ａ），（ｂ），（ｃ）は、線分集合に基づくクラスタリングの失敗例を示す図
【図２１】（ａ），（ｂ），（ｃ）は、色別領域に基づくクラスタリングの失敗例を示す図
【符号の説明】
１…３次元点集合データベース
２…レイヤ生成装置
３…連結検出装置
４…クラスタ生成装置
５…３次元モデル生成装置
６…出力装置
【図１】
2004240599.tif 000003
【図２】
2004240599.tif 000004
【図３】
2004240599.tif 000005
【図４】
2004240599.tif 000006
【図５】
2004240599.tif 000007
【図６】
2004240599.tif 000008
【図７】
2004240599.tif 000009
【図８】
2004240599.tif 000010
【図９】
2004240599.tif 000011
【図１０】
2004240599.tif 000012
【図１１】
2004240599.tif 000013
【図１２】
2004240599.tif 000014
【図１３】
2004240599.tif 000015
【図１４】
2004240599.tif 000016
【図１５】
2004240599.tif 000017
【図１６】
2004240599.tif 000018
【図１７】
2004240599.tif 000019
【図１８】
2004240599.tif 000020
【図１９】
2004240599.tif 000021
【図２０】
2004240599.tif 000022
【図２１】
2004240599.tif 000023