(57)【要約】【課題】３次元地図情報における所定の属性によって表される部分を、属性毎に精度よく分離できる３次元地図分離装置および３次元地図分離プログラム提供する。【解決手段】本発明の一態様によれば、ポリゴンデータによって表現される３次元地図情報を構成している複数の面を、各面の属性毎に分離する３次元地図分離装置であって、前記３次元地図情報を用いて前記複数の面の隣接関係を示すグラフ構造を生成するグラフ構造生成部と、隣接する２つの面が向く角度を用いて、一方の面の属性と、他方の面の属性とが異なる可能性を示す第１の重みを求める第１重み設定部と、ある面の高さと、該面の地点における地面の高さと、から該面がどの程度特定の属性らしいかを示す第２の重みを求める第２重み設定部と、前記第１の重みおよび前記第２の重みを用いて前記グラフ構造に対してグラフカット処理を行って、各面を属性毎に分離するセグメンテーション部と、を備える３次元地図分離装置が提供される。【選択図】図１
2018173705.tif 000002
【特許請求の範囲】
【請求項１】
ポリゴンデータによって表現される３次元地図情報を構成している複数の面を、各面の属性毎に分離する３次元地図分離装置であって、
前記３次元地図情報を用いて前記複数の面の隣接関係を示すグラフ構造を生成するグラフ構造生成部と、
隣接する２つの面が向く角度を用いて、一方の面の属性と、他方の面の属性とが異なる可能性を示す第１の重みを求める第１重み設定部と、
ある面の高さと、該面の地点における地面の高さと、から該面がどの程度特定の属性らしいかを示す第２の重みを求める第２重み設定部と、
前記第１の重みおよび前記第２の重みを用いて前記グラフ構造に対してグラフカット処理を行って、各面を属性毎に分離するセグメンテーション部と、を備える３次元地図分離装置。
【請求項２】
前記グラフ構造生成部は、前記３次元地図情報を用いて、
前記各面を表す面ノードと、
互いに異なる属性に対応する仮想的なノードである第１仮想ノード及び第２仮想ノードと、
隣接する前記面の面ノードどうしを接続する第１エッジと、
前記第１仮想ノードと前記面ノードのそれぞれ、および、前記第２仮想ノードと前記面ノードのそれぞれを接続する第２エッジと、から構成される前記グラフ構造を生成し、
前記第１重み設定部は、前記第１エッジのそれぞれに対して前記第１の重みを設定し、
前記第２重み設定部は、前記第２エッジのそれぞれに対して前記第２の重みを設定し、
前記セグメンテーション部は、前記第１仮想ノードに接続される面ノードと、前記第２仮想ノードに接続される面ノードと、に分離する、請求項１に記載の３次元地図分離装置。
【請求項３】
前記第２重み設定部は、前記面の高さと該面の地点における前記地面の高さとの差を求め、
該差が小さいほど該面の属性が地面らしいとする前記第２の重みを前記第１仮想ノードと接続される前記第２エッジに設定し、
該差が大きいほど該面の属性が非地面らしいとする前記第２の重みを前記第２仮想ノードと接続される前記第２エッジに設定し、
前記セグメンテーション部は、前記グラフ構造に対してグラフカット処理を行い、前記第１仮想ノードに接続される面ノードによって表される面の属性を地面とし、前記第２仮想ノードに接続される面ノードによって表される面の属性を非地面として分離する、請求項２に記載の３次元地図分離装置。
【請求項４】
２次元地図データによって表される建物の外周線がなす領域を所定量縮小した縮小外周線の内側の領域に相当する前記面の属性が建物とする正解ラベルを求め、前記外周線がなす領域を所定量拡大した拡大外周線の外側の領域に相当する前記面の属性が非建物とする正解ラベルを求める正解ラベル設定部を備え、
前記第２重み設定部は、前記建物とする正解ラベルを用いて前記面の属性が建物らしいとする前記第２の重みを前記第１仮想ノードと接続される前記第２エッジに設定し、前記非建物とする正解ラベルを用いて前記面の属性が非建物らしいとする前記第２の重みを前記第２仮想ノードと接続される前記第２エッジに設定し、
前記セグメンテーション部は、前記グラフ構造に対してグラフカット処理を行い、前記第１仮想ノードに接続される面ノードによって表される面の属性を建物とし、前記第２仮想ノードに接続される面ノードによって表される面の属性を非建物として分離する、請求項２に記載の３次元地図分離装置。
【請求項５】
前記正解ラベル設定部は、ある前記外周線の拡大外周線のなす領域と、他の前記外周線の拡大外周線のなす領域とが重複する場合、前記重複する領域のうち、前記ある外周線がなす領域前記所定量より小さい第２所定量拡大した第２拡大外周線の外側かつ前記他の外周線がなす領域を前記第２所定量拡大した他の第２拡大外周線の外側の領域に前記非建物の正解ラベルを設定する、請求項４に記載の３次元地図分離装置。
【請求項６】
前記第２重み設定部は、予め記憶された地面の高さを示す標高データを用いて前記地面の高さを求める、請求項１乃至５のいずれかに記載の３次元地図分離装置。
【請求項７】
前記第２重み設定部は、地面に相当する領域を表す２次元地図データおよび前記３次元地図情報を用いて前記地面の高さを求める、請求項１乃至６のいずれかに記載の３次元地図分離装置。
【請求項８】
ポリゴンデータによって表現される３次元地図情報を構成している複数の面を、各面の属性毎に分離する３次元地図分離プログラムであって、コンピュータを、
前記３次元地図情報を用いて前記複数の面の隣接関係を示すグラフ構造を生成するグラフ構造生成部と、
隣接する２つの面が向く角度を用いて、一方の面の属性と、他方の面の属性とが異なる可能性を示す第１の重みを求める第１重み設定部と、
ある面の高さと、該面の地点における地面の高さと、から該面がどの程度特定の属性らしいかを示す第２の重みを求める第２重み設定部と、
前記第１の重みおよび前記第２の重みを用いて前記グラフ構造に対してグラフカット処理を行って、各面を属性毎に分離するセグメンテーション部と、として機能させる３次元地図分離プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３次元地図情報における所定の属性によって表される部分（例えば、建物と非建物）を属性毎に分離する３次元地図分離装置および３次元地図分離プログラムに関する。
【背景技術】
【０００２】
近年、災害対応やセキュリティプランニングなどの様々な用途において、航空機からステレオ撮影やレーザ測距を行うることによって作成された高さ情報も含む地図であって、立体形状をポリゴンデータによって表した３次元地図情報が利用されている。しかし、３次元地図情報は、ポリゴンによって表される各部分がどのような属性を持つのかについて定義されていないため、応用範囲が限定されており、必ずしも使い勝手がよいものとは言えなかった。３次元地図情報における建物に相当する部分、地面に相当する部分、植栽・道路構造物などに相当する部分といったような、所定の属性によって表される部分からなるポリゴンの集合を分離することができれば、それぞれに利用用途に応じた属性ラベルを付与することができる。これにより、例えば、人が移動可能な部分が明確となって警備員の配置計画などのセキュリティプランニングに利用することができ、より使い勝手がよくなると考えられる。
【０００３】
特許文献１には、上空からレーザスキャンすることによって得られた高精度な標高モデル（地上位置情報）に対してフィルタリング技術を適用することにより、標高モデルから地物が取り除かれ、測定された実際の地表面の標高に整合して、全体としてスムースな地表面を表した地表面標高モデルを作成する技術が開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００２−２３６０１９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、上記従来技術は、地表面標高モデルを作成するものであっても、３次元地図情報における所定の属性によって表される部分を分離することについて、全く念頭に置いていない。したがって、３次元地図情報における所定の属性によって表される部分（ポリゴンの集合）に対して、属性ラベルを付与することに用いることはできなかった。
【０００６】
本発明はこのような問題点に鑑みてなされたものであり、３次元地図情報における所定の属性によって表される部分を、属性毎に精度よく分離できる３次元地図分離装置および３次元地図分離プログラム提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の一態様によれば、ポリゴンデータによって表現される３次元地図情報を構成している複数の面を、各面の属性毎に分離する３次元地図分離装置であって、前記３次元地図情報を用いて前記複数の面の隣接関係を示すグラフ構造を生成するグラフ構造生成部と、隣接する２つの面が向く角度を用いて、一方の面の属性と、他方の面の属性とが異なる可能性を示す第１の重みを求める第１重み設定部と、ある面の高さと、該面の地点における地面の高さと、から該面がどの程度特定の属性らしいかを示す第２の重みを求める第２重み設定部と、前記第１の重みおよび前記第２の重みを用いて前記グラフ構造に対してグラフカット処理を行って、各面を属性毎に分離するセグメンテーション部と、を備える３次元地図分離装置が提供される。
【０００８】
前記グラフ構造生成部は、前記３次元地図情報を用いて、前記各面を表す面ノードと、互いに異なる属性に対応する仮想的なノードである第１仮想ノード及び第２仮想ノードと、隣接する前記面の面ノードどうしを接続する第１エッジと、前記第１仮想ノードと前記面ノードのそれぞれ、および、前記第２仮想ノードと前記面ノードのそれぞれを接続する第２エッジと、から構成される前記グラフ構造を生成し、前記第１重み設定部は、前記第１エッジのそれぞれに対して前記第１の重みを設定し、前記第２重み設定部は、前記第２エッジのそれぞれに対して前記第２の重みを設定し、前記セグメンテーション部は、前記第１仮想ノードに接続される面ノードと、前記第２仮想ノードに接続される面ノードと、に分離してもよい。
【０００９】
前記第２重み設定部は、前記面の高さと該面の地点における前記地面の高さとの差を求め、該差が小さいほど該面の属性が地面らしいとする前記第２の重みを前記第１仮想ノードと接続される前記第２エッジに設定し、該差が大きいほど該面の属性が非地面らしいとする前記第２の重みを前記第２仮想ノードと接続される前記第２エッジに設定し、前記セグメンテーション部は、前記グラフ構造に対してグラフカット処理を行い、前記第１仮想ノードに接続される面ノードによって表される面の属性を地面とし、前記第２仮想ノードに接続される面ノードによって表される面の属性を非地面として分離してもよい。
【００１０】
２次元地図データによって表される建物の外周線がなす領域を所定量縮小した縮小外周線の内側の領域に相当する前記面の属性が建物とする正解ラベルを求め、前記外周線がなす領域を所定量拡大した拡大外周線の外側の領域に相当する前記面の属性が非建物とする正解ラベルを求める正解ラベル設定部を備え、前記第２重み設定部は、前記建物とする正解ラベルを用いて前記面の属性が建物らしいとする前記第２の重みを前記第１仮想ノードと接続される前記第２エッジに設定し、前記非建物とする正解ラベルを用いて前記面の属性が非建物らしいとする前記第２の重みを前記第２仮想ノードと接続される前記第２エッジに設定し、前記セグメンテーション部は、前記グラフ構造に対してグラフカット処理を行い、前記第１仮想ノードに接続される面ノードによって表される面の属性を建物とし、前記第２仮想ノードに接続される面ノードによって表される面の属性を非建物として分離してもよい。
【００１１】
前記正解ラベル設定部は、ある前記外周線の拡大外周線のなす領域と、他の前記外周線の拡大外周線のなす領域とが重複する場合、前記重複する領域のうち、前記ある外周線がなす領域前記所定量より小さい第２所定量拡大した第２拡大外周線の外側かつ前記他の外周線がなす領域を前記第２所定量拡大した他の第２拡大外周線の外側の領域に前記非建物の正解ラベルを設定してもよい。
【００１２】
前記第２重み設定部は、予め記憶された地面の高さを示す標高データを用いて前記標高を求めてもよい。
【００１３】
前記第２重み設定部は、地面に相当する領域を表す２次元地図データおよび前記３次元地図情報を用いて前記地面の高さを求めてもよい。
【００１４】
本発明の別の態様によれば、ポリゴンデータによって表現される３次元地図情報を構成している複数の面を、各面の属性毎に分離する３次元地図分離プログラムであって、コンピュータを、前記３次元地図情報を用いて前記複数の面の隣接関係を示すグラフ構造を生成するグラフ構造生成部と、隣接する２つの面が向く角度を用いて、一方の面の属性と、他方の面の属性とが異なる可能性を示す第１の重みを求める第１重み設定部と、ある面の高さと、該面の地点における地面の高さと、から該面がどの程度特定の属性らしいかを示す第２の重みを求める第２重み設定部と、前記第１の重みおよび前記第２の重みを用いて前記グラフ構造に対してグラフカット処理を行って、各面を属性毎に分離するセグメンテーション部と、として機能させる３次元地図分離プログラムが提供される。
【発明の効果】
【００１５】
３次元地図情報で表現される、所定の属性を持つ領域を、属性毎に精度よく分離できる。
【図面の簡単な説明】
【００１６】
【図１】一実施形態に係る３次元地図分離装置１００の概略構成を示すブロック図。
【図２】３次元地図分離装置１００の処理動作を示すフローチャート。
【図３】グラフ構造生成部４１によって生成されたグラフ構造を模式的に示す図。
【図４】スムース項Ｓを説明する図。
【図５】建物の正解ラベル領域を設定する手法を説明する図。
【図６Ａ】非建物の正解ラベル領域を設定する手法を説明する図。
【図６Ｂ】非建物の正解ラベル領域を設定する手法を説明する図。
【図７】各第２エッジに設定されるデータ項をまとめた図。
【図８】グラフカットを模式的に説明する図。
【図９Ａ】３次元地図情報３１におけるポリゴンデータを示す図。
【図９Ｂ】３次元地図情報３１に対してセグメンテーションを施して得られた図。
【発明を実施するための形態】
【００１７】
以下、本発明に係る実施形態について、図面を参照しながら具体的に説明する。
【００１８】
（第１の実施形態）
図１は、一実施形態に係る３次元地図分離装置１００の概略構成を示すブロック図である。３次元地図分離装置１００は、入力装置１と、出力装置２と、記憶部３と、制御部４とを備えている。なお、３次元地図分離装置１００は１台の装置から構成されてもよいし、複数台の装置から構成されてもよい。
【００１９】
３次元地図分離装置１００は後述するポリゴンデータによって表現される３次元地図情報を構成している複数の面（ポリゴン）を、各面の属性毎に分離するものである。属性とは、例えば建物、地面、植栽、道路構造物などであり、本実施形態では各面を建物とそれ以外（以下、非建物という）とに分離する例を示す。
【００２０】
入力装置１は記憶部３や制御部４への入力を行うためのユーザインターフェースであり、キーボード、マウス、タッチパネルなどである。出力装置２は制御部４での処理結果を出力するためのユーザインターフェースであり、ディスプレイ、プリンタ、記憶媒体への情報記憶デバイス、ネットワークを介して情報送信可能な通信デバイスなどである。
【００２１】
記憶部３は、例えばハードディスクであって、種々の情報やプログラムを記憶する。具体的には、記憶部３は、予め入力装置１を介して入力された３次元地図情報３１、２次元地図データ３２および標高データ３３などを記憶している。また、記憶部３は、後述する制御部４が生成し、かつ、その後の処理に用いられるグラフデータ３４を一時的に記憶する。
【００２２】
ここで、３次元地図情報３１は地表の形状を表したポリゴンデータであり、建物、植栽、道路構造物（標識や歩道橋など）を含み得る（図９Ａ参照）。３次元地図情報３１は例えば以下の処理によって作成される。まず、撮影角度が互いに異なる複数のカメラで上空から地上を撮影する。続いて、ステレオ視の原理により高さ方向の位置を算出し、３次元座標を持つ点群を得る。その後、点群にポリゴン化処理および簡素化処理を行う。そして、撮影データから作成したテクスチャのマッピングを行う。以上によって３次元地図情報を作成できる。
【００２３】
なお、３次元地図情報３１は単なる大きなテクスチャ付きのポリゴンデータであり、特定の場所が何であるのかといった情報は含まない。例えば、どの場所が建物であり、どの場所が道路であるか、といったことは３次元地図情報３１からは分からない。
【００２４】
２次元地図データ３２は建物の存在領域を表す建物の外周線（言い換えると、地面に相当する領域）を表すポリゴン群で構成されるデータであり、例えば国土地理院の基盤地図情報に含まれる「建築物の外周線」を利用可能である。なお、ポリゴン化されていない地図情報を使用し、制御部４がポリゴン化を行って２次元地図データ３２を生成してもよい。
【００２５】
標高データ３３は地点ごとの標高を示すデータであり、例えば国土地理院の基盤地図情報に含まれる「数値標高データ」を利用可能である。この数値標高データは航空レーザ測量によって作成されたデータであり、地表にレーザ光を射出してから反射して戻ってくるまでの時間を計測することによって高度を計測したものである。この数値標高データの場合、約５ｍ間隔でデータが整備されており、誤差は０．３ｍ程度である。
【００２６】
制御部４は、グラフ作成部４０およびセグメンテーション部４５を有し、グラフ作成部４０は、グラフ構造生成部４１、スムース項算出部４２、正解ラベル設定部４３およびデータ項算出部４４から構成される。これら各部は、例えば記憶部３に記憶された所定のプログラムをプロセッサが実行することによって実現されてもよい。
【００２７】
グラフ作成部４０は、３次元地図情報３１における建物部とそれ以外の部分のセグメンテーションするために、３次元地図情報３１のポリゴンデータを利用してグラフ構造を作成する。具体的には次の通りである。
【００２８】
グラフ作成部４０におけるグラフ構造生成部４１はポリゴンデータによって表現される３次元地図情報３１からグラフ構造を生成する。グラフ構造は、３次元地図情報３１を構成している複数の面の隣接関係を示す。より詳しくは、グラフ構造は、各ポリゴンデータに定義された面（ポリゴン）のそれぞれを表すノード（以下、面ノードという）と、当該面に隣接する他の面を表す面ノードどうしを接続するエッジ（以下、第１エッジという）とを含む。また、グラフ構造は、建物（Building）を表す仮想的なノードである建物ノードＢ（第１仮想ノード）と、それ以外（Other）を表す仮想的なノードである非建物ノードＯ（第２仮想ノード）とを含む。さらに、グラフ構造は建物ノードＢと面ノードのそれぞれとを接続するエッジおよび非建物ノードＯと面ノードのそれぞれとを接続するエッジ（以下、建物ノードＢ及び非建物ノードＯと面ノードのそれぞれと接続するエッジを第２エッジという）を含む。生成されたグラフ構造はグラフデータ３４として記憶部３に記憶される。なお、２つの仮想ノードは互いに異なる属性に対応する。
【００２９】
スムース項算出部４２（第１重み設定部）は、３次元地図情報３１およびグラフデータ３４を参照し、隣接する２つの面が向く角度を用いて、一方の面が建物であり、他方の面が非建物である可能性を示す重み（以下、「スムース項Ｓ」または「第１の重み」という）を求める。スムース項Ｓは第１エッジのそれぞれに対して設定することができる。スムース項Ｓは、第１エッジがどの程度建物と非建物との境界らしいかを示すとも言え、境界である可能性が高いほど小さい値となる。
【００３０】
正解ラベル設定部４３は、２次元地図データ３２を参照し、ポリゴンデータの一部の領域において、確実に建物であるとする建物の正解ラベルを求め、確実に非建物であるとする非建物の正解ラベルを求める。なお、本実施形態では求めた正解ラベルは、面ノードに設定されるものとする。しかし、これに限らず、３次元地図情報３１の各面に対して設定するようにしてもよい。
【００３１】
データ項算出部４４（第２重み設定部）は、標高データ３３を参照し、ある面の高さと、この面の地点における地面の標高（高さ）と、から重み（以下、「データ項Ｄ」または「第２の重み」という）を求める。データ項Ｄは第２エッジのそれぞれに対して設定することができる。データ項Ｄは、第２エッジに接続される面ノードによって表される面がどの程度建物らしいか、あるいは、非建物らしいかを示す。
【００３２】
より具体的には、データ項算出部４４は、ある面の高さと、この面の地点における地面の標高との差を求める。そして、データ項算出部４４は、この差が小さいほどこの面が地面らしい（つまり非建物らしい）とし、差が大きいほどこの面が建物らしいとする。建物ノードＢと面ノードとを接続する第２エッジに関しては、建物である可能性が高いほどデータ項Ｄが大きな値となる。一方、非建物ノードＯと面ノードとを接続する第２エッジに関しては、非建物である可能性が高いほどデータ項Ｄが大きな値となる。なお、データ項算出部４４は、正解ラベル設定部４３によって設定された正解ラベルを参照して、各面ノードのデータ項Ｄを更に求める。より具体的には、建物の正解ラベルが設定されている面ノードの面は、建物である可能性がかなり高いことから、当該面ノードと建物ノードＢとを接続する第２エッジに十分に大きな値のデータ項Ｄが設定される。また、非建物の正解ラベルが設定されている面ノードの面は、非建物である可能性がかなり高いことから、当該面ノードと非建物ノードＯとを接続する第２エッジに十分に大きな値のデータ項Ｄが設定される。
【００３３】
セグメンテーション部４５は、スムース項Ｓが設定された第１エッジおよびデータ項Ｄが設定された第２エッジを含むグラフ構造に対してグラフカット処理を行い、各面を建物ノードＢに接続される面ノード群と非建物ノードＯに接続される面ノード群とに分離する。
【００３４】
図２は、３次元地図分離装置１００の処理動作を示すフローチャートである。
まず、グラフ構造生成部４１は３次元地図情報におけるポリゴンデータからグラフ構造を生成し、グラフデータ３４として記憶部３に記憶する（ステップＳ１）。具体的には次のようにする。
【００３５】
グラフ構造生成部４１は、３次元地図情報３１の各ポリゴンデータに定義された面のそれぞれに、１つの面ノードを設定する。例えば、グラフ構造生成部４１は各面の重心を面ノードとしてよい。続いて、グラフ構造生成部４１は隣接する面を表す面ノードどうしを接続して第１エッジを形成する。さらに、グラフ構造生成部４１は、建物を表す仮想的な建物ノードＢおよびそれ以外を表す仮想的な非建物ノードＯと全ての面ノードのそれぞれとを接続して第２エッジを形成する。以上によりグラフ構造が生成される。なお、建物ノードＢ，非建物ノードＯは位置の情報を持つ必要はない。
【００３６】
図３は、グラフ構造生成部４１によって生成されたグラフ構造を模式的に示す図である。同図において、１つの黒丸が１つの面ノード、すなわち、１つの面を表している。また、面ノードどうしを接続する実線が第１エッジを示している。また、各面ノードと建物ノードＢを結ぶ破線および各面ノードと非建物ノードＯとを結ぶ破線が第２エッジを示している。後述するように、第１エッジにはスムース項Ｓが設定され、第２エッジにはデータ項Ｄが設定される。
【００３７】
図２に戻り、グラフ構造が生成された後、スムース項算出部４２はグラフ構造における第１エッジのそれぞれに対してスムース項Ｓを設定する（ステップＳ２）。スムース項Ｓは建物と非建物との境界らしさを示す値であり、例えば各第１エッジに接続された１つの面が向く角度φ１と、他の面が向く角度φ２との差が小さいほど（境界でない可能性が高いほど）大きな値となるものとする。
図４は、スムース項Ｓの概要を説明する図である。
【００３８】
図４（ａ）では、２つの面Ｆ１，Ｆ２がほぼ同じ方向を向いている。この場合、２つの面Ｆ１，Ｆ２がともに同一の建物に属しているか、ともに同一の非建物に属している可能性が高いことを意味する。言い換えると、面Ｆ１と面Ｆ２との間は建物と非建物との境界でない可能性が高い。したがって、面Ｆ１を表す面ノードと面Ｆ２を表す面ノードとを接続する第１エッジに設定されるスムース項Ｓは大きい値となる。
【００３９】
一方、図４（ｂ）では、２つの面Ｆ１，Ｆ２は大きく異なる方向を向いている。この場合、２つの面Ｆ１，Ｆ２の一方がある建物に属しており、他方が非建物に属している可能性が高いことを意味する。言い換えると、面Ｆ１と面Ｆ２との間は建物と非建物との境界である可能性が高い。したがって、面Ｆ１を表す面ノードと面Ｆ２を表す面ノードとを接続する第１エッジに設定されるスムース項Ｓは小さい値となる。
【００４０】
本実施形態におけるスムース項Ｓの具体例として、ある面（例えば図４（ａ），（ｂ）の面Ｆ１）の法線ベクトルと、他の面（例えば図４（ａ），（ｂ）の面Ｆ２）の法線ベクトルとがなす角度をφとするとき、スムース項算出部４２は下式に基づいてスムース項Ｓを算出するものとする。
Ｓ＝（１＋ｃｏｓ２｜φ｜）／２
この場合、スムース項Ｓは０以上１以下の値を取り得る。
【００４１】
図２に戻り、正解ラベル設定部４３は、２次元地図データ３２が表す建物の外周線に基づいて、確実に建物である領域に建物の正解ラベル領域を設定し、確実に非建物である領域に非建物の正解ラベル領域を設定する。そして、建物の正解ラベル領域に相当する位置にある面ノードに建物の正解ラベルを設定し、非建物の正解ラベル領域に相当する位置にある面ノードに非建物の正解ラベルを設定する（ステップＳ３）。なお、正解ラベル領域の設定にはグラフ構造を用いないため、グラフ構造の生成に先立って正解ラベル領域の設定する処理を行ってもよい。
【００４２】
ここで、正解ラベル設定部４３は２次元地図データ３２における建物の外周線の内側の領域に建物の正解ラベル領域を設定し、外側の領域に非建物の正解ラベル領域を設定してもよい。しかしながら、２次元地図データ３２が表す建物の外周線が必ずしも正確であるとは限らないため、次のようにするのがより望ましい。
【００４３】
図５は、建物の正解ラベル領域を設定する手法を説明する図である。正解ラベル設定部４３は２次元地図データ３２が表す各建物の外周線（同図の実線）がなす領域を所定距離ｄ１（例えば２ｍ）だけ縮小して縮小外周線（同図の破線）を形成する。そして、正解ラベル設定部４３は縮小外周線の内側の領域に建物の正解ラベル領域を設定する。これにより、２次元地図データ３２が多少の誤差を含んでいる場合でも、確実に建物である領域にのみ建物の正解ラベル領域を設定できる。
【００４４】
図６Ａおよび図６Ｂは、非建物の正解ラベル領域を設定する手法を説明する図である。図６Ａに示すように、正解ラベル設定部４３は２次元地図データ３２が表す各建物の外周線（同図の実線）がなす領域を所定距離ｄ２（例えば２ｍ）だけ拡大して拡大外周線（同図の破線）を形成する。そして、正解ラベル設定部４３はいずれの建物の拡大外周線にも含まれない領域に非建物の正解ラベル領域を設定する。
【００４５】
ただし、図６Ｂ（ａ）に示すように、ある建物Ｂ１の外周線がなす領域を拡大した拡大外周線Ａ１のなす領域の一部と、他の建物Ｂ２の外周線がなす領域を拡大した拡大外周線Ａ２のなす領域の一部とが重なることもある（図６Ｂ（ａ）の斜線部）。このような場合であっても、２つの建物Ｂ１，Ｂ２を分離するためには、重なった領域（の少なくとも一部）を非建物の正解ラベル領域を設定するのが望ましい。
【００４６】
そこで、このような場合、正解ラベル設定部４３は建物Ｂ１，Ｂ２の外周線がなす領域をｋ＊ｄ２（０＜ｋ＜１、すなわち、ｋ＊ｄ２＜ｄ２）だけ拡大して拡大外周線Ａ１’，Ａ２’（同図の一点鎖線）を形成する。そして、正解ラベル設定部４３は、拡大外周線Ａ１，Ａ２のなす領域が重なった部分の内側、かつ、拡大外周線領域Ａ１’，Ａ２’の外側の領域に非建物の正解ラベル領域を設定すればよい。
【００４７】
なお、ｋの値が大きすぎると、建物Ｂ１，Ｂ２間に非建物の正解ラベル領域を設定できない。一方、ｋの値が小さすぎると、誤って非建物の領域に建物の正解ラベル領域が設定されてしまいかねない。そこで、使用する２次元地図データ３２や同データ上の建物の密集度などに応じてｋの値を調整するのが望ましい。一例として、建物の密集度が大きいほどｋの値を小さくするのが好適である。
【００４８】
なお、建物の外周線を拡大したり縮小したりする場合、距離ｄ１，ｄ２を基準とするのではなく、所定の縮小率や拡大率を適用してもよい。
【００４９】
図２に戻り、データ項算出部４４は、一部の第２エッジについては正解ラベル領域に基づいて、他の第２エッジについては標高データ３３に基づいて、データ項Ｄを算出する（ステップＳ４）。より具体的には、ある面ノード（又はある面ノードに相当する面）の水平座標が建物の正解ラベル領域に含まれる場合、当該面ノードに対して建物の正解ラベルを設定する。また、ある面ノード（又はある面ノードに相当する面）の水平座標が非建物の正解ラベル領域に含まれる場合、当該面ノードに対して非建物の正解ラベルを設定する。そして、建物あるいは非建物の正解ラベルが設定された面ノードと仮想ノード（建物ノードＢ、非建物ノードＯ）とを接続する第２エッジに対してデータ項算出部４４は正解ラベルに基づくデータ項Ｄを算出する。その他の第２エッジに対してデータ項算出部４４は標高データ３３に基づくデータ項Ｄを算出する。
【００５０】
正解ラベルに基づくデータ項Ｄは次の通りである。データ項算出部４４はデータ項Ｋを次の（１）式のように定義する。
【数１】
2018173705.tif 000003
【００５１】
ここで、Ｐは面ノードの集合、Ｅは面ノードと面ノードとを接続する第１エッジの集合を表す。また、｛ｐ，ｑ｝は面ノードｐと面ノードｑとを接続する第１エッジを表す。Ｓ[p,q]は面ノードｐと面ノードｑとを接続する第１エッジに設定されたスムース項Ｓを表す。このデータ項Ｋは全面ノードのうち、結合しているスムース項のエッジの重みの和が最大である面ノードに対して、接続しているスムース項の重みの和の値よりも大きな値となる。
【００５２】
一方、標高データ３３に基づくデータ項は次の通りである。データ項算出部４４は、第２エッジに接続された面ノードによって表される面の高さ（３次元地図情報３１から得られる）と、その面の地点における地面の標高（標高データ３３から得られる）と、の差と所定の閾値δとを比較して、データ項を設定する。
【００５３】
より具体的には、標高データ３３から得られる地面からの標高に対して閾値δ（例えば０．５ｍ）以上高い点を建物らしいとし、そうでない点を非建物らしいとする。さらに具体的には、３次元地図情報３１のポリゴンデータにおけるある座標（ｘ，ｙ）におけるｚ座標の値をＺ（ｘ，ｙ）とし、標高データ３３におけるある同座標（ｘ，ｙ）における標高をＺ0（ｘ，ｙ）とする。このとき、建物らしさを表すデータ項ＤB（ｘ，ｙ）を地面からの標高差に応じて定める。すなわち、閾値δを用いて値ＤB（ｘ，ｙ）を次の（２）式のように定義する。
【数２】
2018173705.tif 000004
【００５４】
一方、非建物らしさを表すデータ項ＤO（ｘ，ｙ）を次の（３）式のように定義する。
ＤO（ｘ，ｙ）＝１−Ｄ（ｘ，ｙ）  ・・・（３）
【００５５】
標高データ３３に基づくデータ項ＤB（ｘ，ｙ），ＤO（ｘ，ｙ）は０または１を取り得る。すなわち、データ項ＤB（ｘ，ｙ），ＤO（ｘ，ｙ）の最大値および最小値は、スムース項Ｓの最大値および最小値と等しくすることができる。
【００５６】
図７は、各第２エッジに設定されるデータ項をまとめた図である。
任意の面ノードｐと建物ノードＢとを接続する第２エッジ｛ｐ，Ｂ｝のうち、面ノードｐに建物の正解ラベルが設定されている場合、上記（１）式のＫの値が、当該当該第２エッジのデータ項Ｄとなり、１より十分大きな値となる。一方、第２エッジ｛ｐ，Ｂ｝のうち、面ノードｐに非建物の正解ラベルが設定されている場合、当該第２エッジのデータ項Ｄは０となる。そして、第２エッジ｛ｐ，Ｂ｝のうち、面ノードｐにいずれの正解ラベルも設定されていない場合、上記（２）式のＤB（ｘ，ｙ）の値が、当該第２エッジのデータ項Ｄとなり、その値は０または１となる。
【００５７】
任意の面ノードｐと非建物ノードＯとを接続する第２エッジ｛ｐ，Ｏ｝のうち、面ノードｐに非建物の正解ラベルが設定されている場合、上記（１）式のＫの値が、当該当該第２エッジのデータ項Ｄとなり、１より十分大きな値となる。一方、第２エッジ｛ｐ，Ｏ｝のうち、面ノードｐに建物の正解ラベルが設定されている場合、当該第２エッジのデータ項Ｄは０となる。そして、第２エッジ｛ｐ，Ｏ｝のうち、面ノードｐにいずれの正解ラベルも設定されていない場合、上記（３）式のＤO（ｘ，ｙ）の値が、当該第２エッジのデータ項Ｄとなり、その値は０または１となる。
【００５８】
なお、以上の説明では、データ項算出部４４は、正解ラベルおよび標高データ３３の両方を用いて第２エッジにデータ項Ｄを設定することとした。しかしながら、別の手法によってデータ項算出部４４はデータ項Ｄを設定してもよい。例えば、データ項算出部４４は、記憶部３に予め記憶された標高データ３３を用いることなく、正解ラベルから標高を生成してデータ項Ｄを設定することもできる。具体的には、非建物の正解ラベル領域で示された地面高を標高として利用することができ、さらに具体的には以下の通りである。
【００５９】
３次元地図情報３１を構成する面は全て３次元座標を持っている。これらの面の重心位置の水平座標が非建物の正解ラベル領域に含まれている場合、当該重心位置の高さがおよその標高を表しているとする。ある位置における標高を得る場合、その位置の周囲に存在する標高を表している重心位置の高さの中央値を地面の高さとする。探索範囲は標高を表している点が一定数以上（例えば３００点以上）発見されるまで拡大する。
【００６０】
この場合、正解ラベルは２次元地図データ３２及び３次元地図情報３１に基づいて生成されるため、データ項Ｄが２次元地図データ３２及び３次元地図情報３１に基づいて生成されるとも言える。
【００６１】
図２に戻り、第１エッジに対するスムース項Ｓの算出および第２エッジに対するデータ項Ｄの算出が完了すると、セグメンテーション部４５は、グラフ構造を、建物を表す建物ノードＢを含むグラフおよび非建物を表す非建物ノードＯを含むグラフの２つに分割するよう、エッジの切断を行う（ステップＳ５）。この際、切断するエッジの重み（第１エッジにおいてはスムース項Ｓ、第２エッジにおいてはデータ項Ｄ）の和が最小となるようにするのが望ましく、具体例として、Ｍｉｎｃｕｔアルゴリズム（Andrew V Goldberg and Robert E Tarjan. A New Approach to the Maximum-flow Problem. J.ACM, 35(4):921-940, 1988.）を適用できる。
【００６２】
図８は、グラフカットを模式的に説明する図である。図示のように、全ての面ノードが、建物ノードＢを含む側のグラフ（同図の右側）および非建物ノードＯを含む側のグラフ（同図の左側）の一方に属するよう、エッジが切断される。建物ノードＢを含む側のグラフに属する面ノード群に対し、各面ノードが表す面が建物であるという属性ラベル付けを行う。一方、非建物ノードＯを含む側のグラフに属する面ノード群に対し、各面ノードが表す面が非建物であるという属性ラベル付けを行う。
【００６３】
これによって、３次元地図情報３１の建物部分をセグメンテーションすることができる。また、建物部分の属性ラベルは個々の建物ごとに非建物部分の属性ラベルによって区切られるため、個々の建物を区別することもできる。
【００６４】
図８の例では、一点鎖線で囲まれた領域Ｃ１に含まれる３つの面ノードが表す３つの面は第１エッジを介して互いに直接（すなわち、建物ノードＢを介さずに）接続されている（グラフカット処理で第１エッジが切断されていない）ので、単一の建物に属する。同様に、領域Ｃ２に含まれる３つの面ノードが表す３つの面も単一の建物に属する。
【００６５】
しかしながら、領域Ｃ１に含まれる面ノードと、領域Ｃ２に含まれる面ノードとは直接は接続されていない（建物ノードＢを介して間接的に接続されるのみである）。よって、領域Ｃ１における３つの面が属する建物と、領域Ｃ２に属する３つの面が属する建物は異なることが分かる。
【００６６】
図９Ａは、３次元地図情報３１におけるポリゴンデータを示す図である。図９Ｂは、図９Ａの３次元地図情報３１に対して上述した処理を施して得られた図である。図９Ｂでは、図９Ａに表れていた地面や道路などが除かれ、建物のみが抽出されていることが分かる。
【００６７】
このように、本実施形態では、３次元地図情報３１から面ノード、建物ノード、非建物ノードおよびエッジから構成されるグラフ構造を生成する。さらに、隣接する面を表す面ノードどうしを接続するエッジに対して、建物と非建物との境界らしさを示すスムース項Ｓを重みとして設定する。また、各面を表す面ノードと建物ノードとを接続するエッジ、および、各面を表す面ノードと非建物ノードとを接続するエッジに対して、建物らしさを示すデータ項Ｄを重みとして設定する。そして、切断するエッジの重みの和が最小となるよう、グラフ構造を建物側と非建物側とに分離する。これにより、３次元地図情報３１に植栽や道路構造物などが含まれていても精度よく建物を抽出できるし、隣接する建物を区別することもできる。
【００６８】
このように建物を分離することで、建物部分に建物の名称や住所といった属性ラベルを関連付けたり、非建物（典型的には、地面部分）だけを別のデータに置き換えて利用したりする応用が可能である。
【００６９】
（第２の実施形態）
上述した第１の実施形態は、各面を建物と非建物との分離するものであった。この場合、植栽や道路構造物（以下、植栽等という）は非建物として分離される。これに対し、次に説明する第２の実施形態は、各面を地面とそれ以外（以下、非地面という）とに分離するものである。この場合、植栽等は非地面とされる。
【００７０】
このような分離を行う場合、図２のステップＳ３における２次元地図データ３２を用いた正解ラベル設定処理を省略すればよい。すなわち、データ項算出部４４が全ての第２エッジについて、標高データ３３に基づいてデータ項Ｄを算出する。標高データ３３を用いるため、地面と非地面とは区別される。一方、２次元地図データ３２を用いないため、植栽等と建物とで区別されない。なお、第２の実施形態では、第１の実施形態における建物ノードＢ及び非建物ノードＯは、それぞれ非地面及び地面に相当する仮想ノードとなる。
【００７１】
その結果、図２のステップＳ５におけるグラフカット処理によって、各面が地面と非地面とに分離される。
【００７２】
（第３の実施形態）
次に説明する第３の実施形態は、各面を、建物と、地面と、植栽等とに分離するものである。
【００７３】
第１の実施形態で説明した手法によれば、各面を建物と非建物とに分離でき、非建物には地面と植栽等が含まれる。一方、第２の実施形態で説明した手法によれば、各面を地面と非地面とに分離でき、非地面には建物と植栽等とが含まれる。
【００７４】
そこで、３次元地図情報３１に対して、第１の実施形態の手法を適用した結果と、第２の実施形態の手法を適用した結果との差分から、植栽等を分離できる。より具体的には、第１の実施形態の手法を適用した結果において非建物として分離され、かつ、第２の実施形態の手法を適用した結果において非地面として分離された面が植栽等である。このようにして、３次元地図情報３１における各面を、建物と、地面と、植栽等とに分離できる。
【００７５】
上述した実施形態は、本発明が属する技術分野における通常の知識を有する者が本発明を実施できることを目的として記載されたものである。上記実施形態の種々の変形例は、当業者であれば当然になしうることであり、本発明の技術的思想は他の実施形態にも適用しうることである。したがって、本発明は、記載された実施形態に限定されることはなく、特許請求の範囲によって定義される技術的思想に従った最も広い範囲とすべきである。
【符号の説明】
【００７６】
１  入力装置
２  出力装置
３  記憶部
３１  ３次元地図情報
３２  ２次元地図データ
３３  標高データ
３４  グラフデータ
４  制御部
４１  グラフ構造生成部
４２  スムース項算出部
４３  正解ラベル設定部
４４  データ項算出部
４５  セグメンテーション部
１００  ３次元地図分離装置
【図１】
2018173705.tif 000005
【図２】
2018173705.tif 000006
【図３】
2018173705.tif 000007
【図４】
2018173705.tif 000008
【図５】
2018173705.tif 000009
【図６Ａ】
2018173705.tif 000010
【図６Ｂ】
2018173705.tif 000011
【図７】
2018173705.tif 000012
【図８】
2018173705.tif 000013
【図９Ａ】
2018173705.tif 000014
【図９Ｂ】
2018173705.tif 000015