(57)【要約】【課題】屋内における空間の構造を有する入力データから、屋内地図の適切なネットワークデータを効率的に生成することができるようにする。【解決手段】少なくとも屋内空間の構造と、当該屋内空間の構造に基づく性質を示す情報と、を有する入力データから、地図上の移動可能である空間を表すリンクおよびリンクの起点若しくは終点となるノードからなるネットワークデータを生成するネットワークデータ生成装置１０であって、リンク・ノード生成部１４２が、入力データからリンクの集合及びノードの集合を生成する。【選択図】図１
2019139097.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも屋内空間の構造と、前記屋内空間の構造に基づく性質を示す情報と、を有する入力データから、地図上の移動可能である空間を表すリンクおよび前記リンクの起点若しくは終点となるノードからなるネットワークデータを生成するネットワークデータ生成装置であって、
前記屋内空間の一部領域である対象空間が部屋であるか通路であるか否かを判定する判定部と、
前記判定部による判定結果に基づいて、リンクの集合及びノードの集合を生成するリンク・ノード生成部と、
を有するネットワークデータ生成装置。
【請求項２】
前記リンク・ノード生成部は、
前記屋内空間の構造に基づき定義される、かつ、前記対象空間の特性に基づき、前記対象空間がノードのみで構成可能か、リンクとノードとで構成する必要があるかを生成する請求項１記載のネットワークデータ生成装置。
【請求項３】
前記特性は、
出入口の数、及び前記対象空間内の任意の位置から前記対象空間内のほぼすべての領域を可視できるか否かのうちの少なくとも一方である請求項２記載のネットワークデータ生成装置。
【請求項４】
前記リンク・ノード生成部は、
前記対象空間の形状が凸多角形である場合、前記対象空間内の任意の位置から前記対象空間内のほぼすべての領域を可視できると判定し、前記対象空間をノードのみで構成可能であると判定する請求項３記載のネットワークデータ生成装置。
【請求項５】
前記リンク・ノード生成部は、
前記対象空間の形状を、頂点数が少なくなるように単純化し、単純化された対象空間の形状に基づき、前記対象空間の形状が凸多角形であるかを判定する請求項４記載のネットワークデータ生成装置。
【請求項６】
少なくとも生成されたノードの集合とリンクの集合とを、出入口に対応する情報に基づき接続する接続部を更に有する請求項１〜請求項５の何れか１項記載のネットワークデータ生成装置。
【請求項７】
前記性質を示す情報は、前記対象空間がリンクで表わされるかノードで表わされるかを直接判定することができる直接性質情報と、分析することにより前記対象空間がリンクで表わされるかノードで表わされるかが得られる間接性質情報と、を含む請求項１〜請求項６の何れか１項記載のネットワークデータ生成装置。
【請求項８】
少なくとも屋内空間の構造と、前記屋内空間の構造に基づく性質を示す情報と、を有する入力データから、地図上の移動可能である空間を表すリンクおよび前記リンクの起点若しくは終点となるノードからなるネットワークデータを生成するネットワークデータ生成装置におけるネットワークデータ生成方法であって、
判定部が、前記屋内空間の一部領域である対象空間が部屋であるか通路であるか否かを判定し、
リンク・ノード生成部が、前記判定部による判定結果に基づいて、リンクの集合及びノードの集合を生成する
ネットワークデータ生成方法。
【請求項９】
コンピュータを、請求項１〜請求項７の何れか１項記載のネットワークデータ生成装置を構成する各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークデータ生成装置、ネットワークデータ生成方法、およびプログラムに関し、特に、経路検索に十分なネットワークデータを自動生成するためのネットワークデータ生成装置、ネットワークデータ生成方法、およびプログラムに関する。
【背景技術】
【０００２】
従来より、屋内ナビゲーションのために、屋内の３Ｄデジタルモデルから、２Ｄや３Ｄのネットワークデータを自動生成する技術が知られている（非特許文献１）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】"Automatic Extraction of Improved Geometrical Network Model from CityGML for Indoor navigation"＜インターネット検索：https://3d.bk.tudelft.nl/pdfs/FilippoMortari_thesis.pdf  検索日：2017/11/14＞
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、非特許文献１では、出入口などにより閉塞となった屋内空間の形状（例えば、部屋やトイレなど）が存在する場合、生成したネットワークデータ間を接続するためにデータを追加、補正する必要がある。
【０００５】
また、経路探索や誘導を行う際、空間（幅、奥行き、高さ、床の素材など）や出入口（幅、高さ、段差など）や階段（段数、段差、手すり有無）などの属性情報が有益な情報となるが、ネットワークデータを生成する際に割り当てない限り、後から、それらの属性情報を関連付ける必要がある。
【０００６】
更に、屋内空間は、通常、階層を持っており、上下階の接続についてのネットワークデータの関連付けも別途実施する必要がある。
【０００７】
また、屋内の歩行可能域の形状をドロネー三角形分割する場合、屋内空間の形状が複雑になるほど、移動体が移動することができることを示すデータとしては不要なノードを過剰に生成してしまう傾向にあり、そのネットワークデータの生成時間も課題となる。
【０００８】
本発明は上記の点に鑑みてなされたものであり、屋内における空間の構造を有する入力データから、屋内地図の適切なネットワークデータを効率的に生成することができるネットワークデータ生成装置、ネットワークデータ生成方法、およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明に係るネットワークデータ生成装置は、少なくとも屋内空間の構造と、前記屋内空間の構造に基づく性質を示す情報と、を有する入力データから、地図上の移動可能である空間を表すリンクおよび前記リンクの起点若しくは終点となるノードからなるネットワークデータを生成するネットワークデータ生成装置であって、前記屋内空間の一部領域である対象空間が部屋であるか通路であるか否かを判定する判定部と、前記判定部による判定結果に基づいて、リンクの集合及びノードの集合を生成するリンク・ノード生成部と、を備えて構成される。
【００１０】
また、本発明に係るネットワークデータ生成方法は、少なくとも屋内空間の構造と、前記屋内空間の構造に基づく性質を示す情報と、を有する入力データから、地図上の移動可能である空間を表すリンクおよび前記リンクの起点若しくは終点となるノードからなるネットワークデータを生成するネットワークデータ生成装置におけるネットワークデータ生成方法であって、判定部が、前記屋内空間の一部領域である対象空間が部屋であるか通路であるか否かを判定し、リンク・ノード生成部が、前記判定部による判定結果に基づいて、リンクの集合及びノードの集合を生成する。
【００１１】
本発明に係るネットワークデータ生成装置及びネットワークデータ生成方法によれば、判定部が、少なくとも屋内空間の構造と、屋内空間の構造に基づく性質を示す情報と、を有する入力データから、屋内空間の一部領域である対象空間が部屋であるか通路であるか否かを判定し、リンク・ノード生成部が、判定部による判定結果に基づいて、リンクの集合及びノードの集合を生成して、地図上の移動可能である空間を表すリンクおよびリンクの起点若しくは終点となるノードからなるネットワークデータを生成する。
【００１２】
このように、少なくとも屋内空間の構造と、屋内空間の構造に基づく性質を示す情報と、を有する入力データに対し屋内空間の一部領域である対象空間が部屋であるか通路であるか否かを判定し、判定結果に基づいて、リンクの集合及びノードの集合を生成することにより、屋内空間の構造を有する入力データから、屋内地図の適切なネットワークデータを効率的に生成することができる。
【００１３】
また、本発明に係るネットワークデータ生成装置のリンク・ノード生成部は、前記屋内空間の構造に基づき定義される、かつ、前記対象空間の特性に基づき、前記対象空間がノードのみで構成可能か、リンクとノードとで構成する必要があるかを生成することができる。
【００１４】
また、本発明に係るネットワークデータ生成装置の前記特性は、出入口の数、及び前記対象空間内の任意の位置から前記対象空間内のほぼすべての領域を可視できるか否かのうちの少なくとも一方であるとすることができる。
【００１５】
また、本発明に係るネットワークデータ生成装置のリンク・ノード生成部は、前記対象空間の形状が凸多角形である場合、前記対象空間内の任意の位置から前記対象空間内のほぼすべての領域を可視できると判定し、前記対象空間をノードのみで構成可能であると判定することができる。
【００１６】
また、本発明に係るネットワークデータ生成装置のリンク・ノード生成部は、前記対象空間の形状を、頂点数が少なくなるように単純化し、単純化された対象空間の形状に基づき、前記対象空間の形状が凸多角形であるかを判定することができる。
【００１７】
また、本発明に係るネットワークデータ生成装置は、少なくとも生成されたノードの集合とリンクの集合とを、出入口に対応する情報に基づき接続する接続部を更に有することができる。
【００１８】
また、本発明に係るネットワークデータ生成装置の性質を示す情報は、前記対象空間がリンクで表わされるかノードで表わされるかを直接判定することができる直接性質情報と、分析することにより前記対象空間がリンクで表わされるかノードで表わされるかが得られる間接性質情報と、を含むことができる。
【００１９】
本発明に係るプログラムは、上記のネットワークデータ生成装置の各部として機能させるためのプログラムである。
【発明の効果】
【００２０】
本発明のネットワークデータ生成装置、ネットワークデータ生成方法、およびプログラムによれば、屋内における空間の構造を有する入力データから、屋内地図の適切なネットワークデータを効率的に生成することができる。
【図面の簡単な説明】
【００２１】
【図１】本発明の実施の形態に係るネットワークデータ生成装置の構成を示すブロック図である。
【図２】本発明の実施の形態に係る「空間」の振り分け例（出入口の数に着目）を示すイメージ図である。
【図３】本発明の実施の形態に係る「空間」の振り分け例（形状に着目）を示すイメージ図である。
【図４】本発明の実施の形態に係る空間形状の単純化の例（グリッド単純化）を示すイメージ図である。
【図５】本発明の実施の形態に係る空間形状の単純化の例（バッファ単純化）を示すイメージ図である。
【図６】本発明の実施の形態に係る出入口の例を示すイメージ図である。
【図７】本発明の実施の形態に係る部屋内のネットワークデータ生成の例を示すイメージ図である。
【図８】本発明の実施の形態に係る通路内のネットワークデータ生成の例を示すイメージ図である。
【図９】本発明の実施の形態に係る空間間のネットワークデータ生成の例を示すイメージ図である。
【図１０】本発明の実施の形態に係る階層間のネットワークデータ生成の例を示すイメージ図である。
【図１１】本発明の実施の形態に係るネットワークデータ生成処理ルーチンを示すフローチャートである。
【図１２】本発明の実施の形態に係る振分処理ルーチンを示すフローチャートである。
【図１３】本発明の実施の形態に係る特徴・形状振分処理ルーチンを示すフローチャートである。
【図１４】本発明の実施の形態に係る空間形状単純化処理ルーチンを示すフローチャートである。
【図１５】本発明の実施の形態に係る生成処理ルーチンを示すフローチャートである。
【発明を実施するための形態】
【００２２】
以下、本発明の実施の形態について図面を用いて説明する。
【００２３】
＜本発明の実施の形態に係るネットワークデータ生成装置の概要＞
まず、本発明の実施形態の概要について説明する。
【００２４】
本実施形態では、入力データから「階層」毎に、屋内空間の一部である対象空間の各々を、「部屋」、「通路」、「出入口」、「階の接続」に振り分け、屋内空間のネットワークデータを自動生成する。
【００２５】
＜＜振り分け＞＞
対象空間を、入力データが持つクラスやレイヤ定義、形状に付けられた名称や属性情報により振り分け可能な場合は、「階層」毎に「部屋」、「通路」、「出入口」、「階の接続」に振り分ける。
【００２６】
ここで、「部屋」は、ナビゲーションポイントの目的地となり得る「空間」であり、「通路」は、「部屋」と「部屋」とを移動するための「空間」である。
【００２７】
また、「出入口」は、「空間」と「空間」とを接続する場所（ドア、壁無し）であり、「階の接続」は、屋内空間の階層間を接続する場所（階段、エレベータ、エスカレータ等）である。
【００２８】
次に、クラス等により振り分けられなかった対象空間のうち、「空間」（部屋と通路が判定できない場合）は、その「空間」と接続する「出入口」数が１つ、もしくは、対象空間内の所定の位置から対象空間全体を可視できるような形状であれば「部屋」として振り分ける。当該形状は、例えば凸多角形が挙げられる。「空間」とは、屋内空間のうち移動可能な領域を構成する最小の単位であり、例えば、「部屋」や「通路」が含まれる。
【００２９】
対象空間のうち、「空間」は、その「空間」と接続する「出入口」数が２つ以上、かつ、対象空間内の所定の位置から対象空間全体を可視できないような形状であれば「通路」として振り分ける。当該形状は、例えば凹もしくは回（穴あき）多角形が挙げられる。なお、「空間」に接続する「出入口」の数を絶対値の２を境界としている意図は、一方の「出入口」から他方の「出入口」が可視できなくなる可能性が２つ以上から生じるためである。例えば、屋内空間内の「出入口」の総数と、対象の「空間」に接続する「出入口」の数との割合で相対的に「通路」であると判定すると、総数が非常に多い場合、上記例の（「出入口」が２つあり「出入口」間を互いに可視できない）場合、「部屋」と判定されてしまい、互いの「出入口」を接続することができなくなる。
【００３０】
また、上記の場合において、「空間」の形状が複雑であった場合に、形状を単純化（頂点座標数を削減）したうえで、その形状の特性から、「部屋」と「通路」を振り分け、屋内空間のネットワークデータを自動生成する。
【００３１】
また、上記の場合において、入力データがＢＩＭデータのような３Ｄモデルの場合は、形状は正確な高さや位置情報を持つため、「空間」の形状内に存在する移動体が通れる宙吊りされた壁のような移動を阻害しない形状を事前に取り除いてから、屋内空間ネットワークデータを自動生成する。
【００３２】
＜＜ネットワークデータ生成＞＞
「部屋」内のネットワークデータは、「部屋」に接続している「出入口」の近傍にノードを生成し、そのノードが２つ以上の場合は、それらをリンクで接続することで自動生成する。
【００３３】
ここで、リンクは、移動体（人、車いす、ベビーカー、ロボット、ドローン等）がリンク上を移動可能であることを示す建物の廊下等の移動可能な領域に引かれる線である。リンクの両端は必ずノードであり、リンクは、向き、長さという属性情報を一組だけ持つ。従って、リンクの途中で分岐がある場合や、リンクの向きを変える場合には、その起点となる点にノードを打ち、リンクを分割する。
【００３４】
ノードは、リンクの起点、もしくは終点となる点である。リンクの向きを変える（カーブを作成する）、リンクを分岐させる、などの場合にノードが生成されるほか、店舗などの地物の最寄りにナビゲーションポイントを設けたい場合などには、意図的にリンクの途中にノードを打って、リンクを分割する場合がある。
【００３５】
「通路」内のネットワークデータは、通路の形状に中心線を生成し、その頂点、交点にノードを生成し、そのノード間をリンクで接続することで自動生成する。
【００３６】
「空間」間と、「階層」間のノードを相互に接続することにより、屋内空間ネットワークとして完成度の高いデータを自動生成する。
【００３７】
ネットワークデータを生成する際に、入力データがもつ属性情報を付加することで、より、利用価値が高いデータを効率的に自動生成することができる。
【００３８】
ここで、入力データがもつ属性情報には、「部屋」、「通路」、「出入口」、「階の接続」に直接属性情報として含まれる情報や、直接的に含まれていないがそれらの形状の近傍や内部に含まれる形状（例えば、階段における手すりや、トイレにおける便器の数など）や、その形状がもつ属性情報（例えば、空間における床面の素材など）を自動的に抽出することで得られる情報も含まれる。
【００３９】
属性情報を付加する際、同一の属性情報を複数のネットワークデータに付加する場合は、別途、ＰＯＩを生成して、そのＩＤを属性情報に付加することで、データ量を削減することもできる。ここで、ＰＯＩはＰｏｉｎｔ  ｏｆ  Ｉｎｔｅｒｅｓｔの略であり、空間（店舗、部屋、トイレ等）が持つ形状に対する代表点と、その属性とを管理するものである。ここで、代表点とは、空間が持つ形状上で理解しやすい任意の点であり、例えば、重心点を採用することができる。
【００４０】
従って、従来の手法と比べ、経路検索を行う上で有用かつ完成度の高い屋内空間ネットワークデータを、自動生成後の補正や手修正を極限まで抑えつつ、空間内を移動するために必要最小限のデータを自動生成できる。
【００４１】
＜本発明の実施の形態に係るネットワークデータ生成装置の構成＞
図１を参照して、本発明の実施の形態に係るネットワークデータ生成装置１０の構成について説明する。図１は、本発明の実施の形態に係るネットワークデータ生成装置１０の構成を示すブロック図である。
【００４２】
ネットワークデータ生成装置１０は、ＣＰＵと、ＲＡＭと、後述する形状振分処理ルーチン、およびネットワークデータ生成処理ルーチンを実行するためのプログラムを記憶したＲＯＭとを備えたコンピュータで構成され、機能的には次に示すように構成されている。
【００４３】
ネットワークデータ生成装置１０は、入力部１００と、屋内空間データ記憶部１１０と、形状振分部１２０と、振分結果記憶部１３０と、ネットワークデータ生成部１４０と、ネットワークデータ記憶部１５０と、出力部１６０とを備えて構成されている。
【００４４】
入力部１００は、少なくとも屋内空間の構造と、当該屋内空間の構造に基づく性質を示す情報と、を有する入力データの入力を受け付ける。性質を示す情報は、空間がリンクで表わされるかノードで表わされるかを直接判定することができる直接性質情報と、分析することにより空間がリンクで表わされるかノードで表わされるかが得られる間接性質情報と、を含む。
【００４５】
入力データとしては、建築する際に用いるデジタル設計図、例えば、建築設計時に作成する２Ｄの建築用ＣＡＤデータや、ＢＩＭデータに含まれる３Ｄモデルといったデジタルベクトルデータ等を利用する。ＢＩＭを利用する際は、階層毎に水平投射することで、２Ｄのベクトルデータとして扱える。
【００４６】
また、入力データには、部屋や通路や、出入口、階段、エレベータなどの形状が、あらかじめレイヤやクラス定義等が意味付けされて含まれている。
【００４７】
屋内空間データ記憶部１１０は、入力部１００が受け付けた入力データを格納している。
【００４８】
形状振分部１２０は、入力データから、各対象空間の形状種別を、「部屋」、「通路」、「出入口」、または「階の接続」に振り分ける。これらを振り分ける方法は、例えば、以下の判定方法のうち、少なくとも１つを適用する。
【００４９】
＜＜判定方法１＞＞
入力データがもつレイヤやクラス定義情報から各対象空間の形状種別を判定する。例えば、建築用ＣＡＤでは、一般的に、壁や廊下のほか、柱、店舗、トイレ、エスカレータなどをレイヤで分けて管理することができるため、これらのレイヤ定義に基づいて各対象空間の形状種別を判定する。また、例えば、ＢＩＭデータの一つのフォーマットであるＩＦＣ（Ｉｎｄｕｓｔｒｙ  Ｆｏｕｎｄａｔｉｏｎ  Ｃｌａｓｓｅｓ）では、階層、空間、階段、ドア、柱などの構造物毎にクラスが定義付けられているため、これらのクラス定義に基づいて各対象空間の形状種別を判定する。なお、入力データが持つレイヤやクラス定義情報は、空間がリンクで表わされるかノードで表わされるかを直接判定することができる直接性質情報の一例である。
【００５０】
＜＜判定方法２＞＞
入力データのそれぞれの形状に付けられた名前から各対象空間の形状種別を判定する。例えば、「〜部屋」、「〜通路」、「〜非常口」、「〜階段」等という名前から判定する。なお、入力データのそれぞれの形状に付けられた名前は、空間がリンクで表わされるかノードで表わされるかを直接判定することができる直接性質情報の一例である。
【００５１】
＜＜判定方法３＞＞
入力データのそれぞれの形状が持つ属性情報から各対象空間の形状種別を判定する。例えば、段数、開口部等の属性情報から判定する。なお、入力データのそれぞれの形状が持つ属性情報は、分析することにより空間がリンクで表わされるかノードで表わされるかが得られる間接性質情報の一例である。
【００５２】
＜＜判定方法４＞＞
事前に入力データに対して、「部屋」、「通路」、「出入口」、および「階の接続」の情報を付加しておくことにより、これらの情報から判定する。なお、「部屋」、「通路」、「出入口」、および「階の接続」の情報は、空間がリンクで表わされるかノードで表わされるかを直接判定することができる直接性質情報の一例である。
【００５３】
ここで、例えば、入力データがＢＩＭであった場合、「部屋」と「通路」は同じクラス定義情報「空間」で管理されており、判定方法１では判断することができない。また、判定方法２や判定方法３においても、命名規則が定められていない場合は（データ作成（設計）者によって異なるため）、「部屋」と「通路」とを判断することができない。また、判定方法４は、入力データ内の「空間」の数が少ない場合に有効であるが、その数が多くなるにつれ効率が下がってしまう。
【００５４】
そこで、形状振分部１２０は、空間の構造に基づき定義される、空間の一部領域である対象空間の特性に基づき、各対象空間の形状種別を「部屋」、「通路」、「出入口」、または「階の接続」に振り分ける。ここで、特性は、出入口の数、及び対象空間内の任意の位置から対象空間内のほぼすべての領域を可視できるか否かのうちの少なくとも一方である。
【００５５】
具体的には、形状振分部１２０は、対象空間の形状が凸多角形である場合、対象空間を「部屋」と判定し、凹または回多角形の場合「通路」と判定して、振り分ける。
【００５６】
例えば、形状振分部１２０は、下記判定方法５を用いる。
【００５７】
＜＜判定方法５＞＞
各対象空間の形状種別が、「部屋」と「通路」のいずれであるか判定できない場合は、判定できない「空間」をそれぞれの形状がもつ特徴から「部屋」と「通路」を判断する。
【００５８】
まず、形状振分部１２０は、「空間」が接続している「出入口」の数（特性）に着目し、「出入口」数が１の場合（出入口数＝１）、当該「空間」の形状種別を「部屋」として判定する。
【００５９】
一方、「出入口」数が１よりも大きい場合（出入口数＞１）、当該「空間」の形状、幅、奥行の情報から「部屋」か「通路」であるかを判定する。
【００６０】
入力データの形状等の情報から判定する方法としては、例えば、その「空間」の形状に着目し、その形状が凸多角形の場合、「部屋」と判定し、凹または回（穴あき）多角形の場合「通路」と判定する。
【００６１】
その理由は、「空間」の形状により、「空間」内の地点から全体を可視できない（例えば、ある出入口から他方の出入口が見えない）場合、移動したい目的地点もしくは中継地点が視界に入らない可能性がある。例えば、図３に示す凹多角形や回多角形の例があげられる。
【００６２】
凸多角形の場合は、その「空間」のあらゆる地点からその重心に向かう方向に壁などの障害はないため、「出入口」に到達した時点で、移動したい目的地点もしくは中継地点は明確（「空間そのものが目的地」であるか、「空間」内に存在する他の「出入口」が経由地点）である。従って、この時点で、ネットワークデータが生成可能な状態となる。
【００６３】
凹または回多角形の場合は、壁などに阻まれ、「空間」内に存在する他の「出入口」（中継地点）が視界に入らない場合がある。従って、そのままでは、ネットワークデータが生成できない。このため、「通路」と判定しておく。
【００６４】
また、形状振分部１２０は、対象空間の形状が凸多角形、凹または回多角形であるかを判定する際に、対象空間の形状を、頂点数が少なくなるように単純化し、単純化された対象空間の形状に基づき、対象空間の形状が凸多角形、凹または回多角形であるかを判定してもよい。
【００６５】
形状振分部１２０が、形状に着目した形状種別の判定を行う際に、入力データが持つ空間の形状が複雑で（外枠ある小さな隙間や空間内の小さな穴などが）ある場合、そのままでは、単純に凹凸回多角形の判定はできないため、複雑な形状を単純化（頂点座標点数の削減）した後に、凹凸回多角形の判定を行うことが好ましい。
【００６６】
空間形状の単純化の方法には、様々な方法が考えられるが、その単純化の一例として、グリッドやバッファを用いた単純化を用いれば良い。図４、図５に単純化の例を示す。
【００６７】
グリッドによる単純化（図４）では、入力データの特性を踏まえて単純化を考える。入力データは、建築時に用いる設計データであるため、空間の形状は、基本的には、水平かつ垂直である。従って、空間の形状に対する外接矩形を水平かつ垂直な小さなグリッド（目安としてグリッドの高さと幅は、移動体が移動する際に十分な大きさで、建物内の最小通路幅の１／２に設定する）に分割し、それらのグリッドと空間の形状が重なっているグリッドの集合を、単純化後の空間の形状として採用することで空間の形状を単純化できる。
【００６８】
しかし、グリッドによる単純化により、逆の効果を生じてしまう可能性がある。その場合は、バッファによる単純化を検討する。
【００６９】
バッファによる単純化（図５）では、空間の形状に対し形状を広げるバッファ（目安としてグリッドの高さと幅は、移動体が移動する際に十分な大きさで、建物内の最小通路幅の１／２に設定する）を生成した後に、その形状を狭めるバッファ（広げるバッファと同値）を生成することで空間形状を単純化できる。
【００７０】
なお、入力データがＢＩＭデータのような３Ｄモデルの場合には、形状は正確な高さ情報をもつため、例えば、部屋の中に存在する移動体が通れる宙吊りされた壁のような移動を阻害しない形状（図６）を事前に取り除いておくことも単純化を行う際には有効である。
【００７１】
そして、形状振分部１２０は、各対象空間の形状種別を振り分けた結果である振分結果を、振分結果記憶部１３０に格納する。
【００７２】
振分結果記憶部１３０は、形状振分部１２０により得られた振分結果を格納する。
【００７３】
ネットワークデータ生成部１４０は、形状振分部１２０にて振り分けた「部屋」と「通路」と「出入口」と「階の接続」の情報からリンクの集合及びノードの集合からなるネットワークデータを生成する。
【００７４】
具体的には、ネットワークデータ生成部１４０は、リンク・ノード生成部１４２と、接続部１４４とを備えて構成される。
【００７５】
リンク・ノード生成部１４２は、振分結果記憶部１３０に格納されている振分結果と、空間の構造に基づき定義される、かつ、当該空間の一部領域である対象空間の特性とに基づき、対象空間がノードのみで構成可能か、リンクとノードとで構成する必要があるかを判定して、リンクとノードとを生成する。
【００７６】
具体的には、リンク・ノード生成部１４２は、まず、「部屋」と「通路」と「階の接続」に接続する「出入口」ノードを、「出入口」と振り分けられた空間に対して生成する。
【００７７】
その際、入力データの該当する形状には直接的に属性情報（例えば、「空間」の属性には、幅、奥行き、高さなどをもつ）が含まれている場合がある。
【００７８】
また、その形状自体には直接的に属性情報が含まれていないが、入力データの中にはそれらの形状の近傍や内部に含まれる別の形状（例えば、トイレにおける便器の数など）や、属性情報（例えば、空間における床面の素材など）を自動的に抽出することで得られる場合もある。
【００７９】
そのような場合には、生成する「出入口」ノードに、上記で自動的に得られた属性情報を付加しておくことで、経路探索や誘導を行う際に、付加した属性情報を踏まえたナビゲーションを実現でき、かつ、有益な情報を得ることができる。
【００８０】
また、２つ以上の「出入口」と接続している「部屋」や、「通路」の場合などは、生成する「出入口」ノード数が複数存在するため、その場合、各ノードに冗長な「空間」に関連する属性情報を付与することになる。このため、その場合は、「空間」に対するＰＯＩを別途生成し、そのＩＤを「出入口」ノードの属性情報に付与することで、データ量を削減することもできる。
【００８１】
具体的には、リンク・ノード生成部１４２は、対象空間が、「部屋」であるか「通路」であるかに基づいて、ノードとするか、リンクとノードとで構成するかを判定し、これに基づいてリンクとノードとを生成する。
【００８２】
例えば、リンク・ノード生成部１４２は、対象空間が、「部屋」に振り分けられている場合、当該「部屋」に「出入口」ノードが複数存在した場合は、ノード間を接続するようにリンクを生成する（図７）。
【００８３】
ここで、出入口数が３よりも大きい（出入口数＞３）の場合（図７右部）は、ノード間のリンクが交差してしまう。この場合、ネットワークデータ量を削減する目的として交差するリンクを除去する構成としても良い。
【００８４】
リンク・ノード生成部１４２は、対象空間が、「通路」に振り分けられている場合、「通路」の形状に対する中心線を生成し、その中心線の頂点・交点に「通路」ノードを生成する。「通路」であった場合は、壁などにより「出入口」のノードを単純にリンクで接続してしまうと、そのリンクが壁や回多角形の内枠に衝突してしまう可能性があるためである。
【００８５】
次に、リンク・ノード生成部１４２は、「通路」ノード間に「通路」リンクを生成する（図８）。これにより、「出入口」ノードと、「通路」ノードもしくは「通路」リンクと接続することで、壁や内枠との衝突は起きなくなる。
【００８６】
そして、リンク・ノード生成部１４２は、「出入口」ノードの近傍が、「通路」ノードであるか、「通路」リンクであるかを判定する。
【００８７】
「出入口」ノードの近傍が、「通路」ノードであった場合、リンク・ノード生成部１４２は、「出入口」ノードと「通路」ノードを接続するリンクを生成する。
【００８８】
一方、「出入口」ノードの近傍が、「通路」リンクであった場合、リンク・ノード生成部１４２は、「出入口」ノードから「通路」リンクに対し垂線を引き、その交点にノードを生成する。そして、「出入口」ノードと交点ノード間にリンクを生成する。
【００８９】
このように、リンク・ノード生成部１４２は、全ての対象空間について、リンク又はノードを生成することにより、リンクの集合とノードの集合を生成する。
【００９０】
なお、リンク・ノード生成部１４２は、「通路」におけるネットワークデータを生成する際に「通路」が持つ形状に対する中心線を生成するが、中心線を生成する際の形状に、形状振分部１２０にて実施した単純化した形状を用いても良い。単純化した形状を用いることで、生成する中心線も単純化した結果を得ることができる。
【００９１】
中心線を生成する手法として、非特許文献１の中央軸変換や、ボロノイ図の特性などを利用すれば良い（参考文献１）
［参考文献１］特開２００３−１３２３５３号公報
【００９２】
また、ここで得られた中心線は、「空間」の形状次第では通行には過剰な形状（頂点数が多く複雑な線）となる可能性がある。その場合は、Ｒａｍｅｒ−Ｄｏｕｇｌａｓ−Ｐｅｕｃｋｅｒ（点の間引き）アルゴリズムや、生成したネットワークでのノードを間引く処理（参考文献２）などを用いて、線を単純化すれば良い。
［参考文献２］特開２０１５−２１０６２６号公報
【００９３】
接続部１４４は、生成されたノードの集合とリンクの集合と、出入口に対応する情報とに基づき、ノード間をリンクで接続する。
【００９４】
具体的には、接続部１４４は、「階層」毎に、「空間」間を接続するために、同一の「出入口」に対する「出入口」ノード間を接続する「出入口」リンクを生成する。その際、入力データの「出入口」の形状や属性情報から、その幅、高さ、段差などの情報を得ることができる場合には、「出入口」リンクの属性情報に設定することで、経路探索や誘導を行う際に、有益な情報を得ることができる。
【００９５】
接続部１４４は、階層間を接続するために、同一の「階の接続」に対する「階の接続」ノード間を接続する「階の接続」リンクを生成する。その際、入力データの該当する形状には直接的に属性情報（例えば、「階段」の属性には、段数、段差などをもつ）が含まれている場合がある。また、その形状自体には直接的に属性情報が含まれていないが、入力データの中にはそれらの形状の近傍や内部に含まれる別の形状（例えば、階段における手すり有無など）や、属性情報（例えば、階段が存在する「空間」の高さなど）を自動的に抽出することで得られる場合もある。
【００９６】
そのような場合には、生成する「出入口」ノードに、上記で自動的に得られた属性情報を付加しておくことで、経路探索や誘導を行う際に、付加した属性情報を踏まえたナビゲーションを実現でき、かつ、有益な情報を得ることができる。
【００９７】
また、接続部１４４は、ノードまたはリンクが、屋外のネットワークデータと接続する場合に、当該ノードまたはリンクと、屋外のネットワークデータとを接続することもできる。
【００９８】
そして、接続部１４４は、生成した全てのノード及び全てのリンクをネットワークデータとして、ネットワークデータ記憶部１５０に格納する。
【００９９】
ネットワークデータ記憶部１５０は、ネットワークデータ生成部１４０により生成されたネットワークデータを格納する。
【０１００】
出力部１６０は、ネットワークデータ記憶部１５０に格納されたネットワークデータを出力する。
【０１０１】
＜本発明の実施の形態に係るネットワークデータ生成装置の作用＞
図１１は、本発明の実施の形態に係るネットワークデータ生成処理ルーチンを示すフローチャートである。
【０１０２】
入力部１００に入力データが入力されると、ネットワークデータ生成装置１０において、図１１に示すネットワークデータ生成処理ルーチンが実行される。
【０１０３】
まず、ステップＳ１００において、入力部１００が、少なくとも屋内空間の構造と、当該屋内空間の構造に基づく性質を示す情報と、を有する入力データの入力を受け付ける。
【０１０４】
ステップＳ１１０において、上記ステップＳ１００により受け付けた入力データが、屋内空間データ記憶部１１０に格納される。
【０１０５】
ステップＳ１２０において、形状振分部１２０は、入力データから、各対象空間の形状種別を、「部屋」、「通路」、「出入口」、または「階の接続」に振り分ける。
【０１０６】
ステップＳ１３０において、上記ステップＳ１２０により得られた振分結果が、振分結果記憶部１３０に格納される。
【０１０７】
ステップＳ１４０において、ネットワークデータ生成部１４０は、屋内空間データ、および、振分結果からリンクの集合及びノードの集合を生成し、ネットワークデータを生成する。
【０１０８】
ステップＳ１５０において、上記ステップＳ１４０により生成されたネットワークデータが、ネットワークデータ記憶部１５０に格納される。
【０１０９】
ステップＳ１６０において、出力部１６０は、ネットワークデータ記憶部１５０に格納されたネットワークデータを出力する。
【０１１０】
ここで、ステップＳ１２０における振分処理について、図１２を用いて説明する。図１２は、振分処理ルーチンを示すフローチャートである。
【０１１１】
ステップＳ２００において、形状振分部１２０は、クラス定義、レイヤ等により各対象空間の形状種別を「階の接続」、「出入口」、「空間」に振り分ける（判定方法１）。
【０１１２】
ステップＳ２１０において、形状振分部１２０は、入力データのそれぞれの形状に付けられた名前、属性等から、各対象空間の形状種別を、「階の接続」、「空間」に振り分ける（判定方法２）。
【０１１３】
ステップＳ２２０において、形状振分部１２０は、空間の構造に基づき定義される対象空間の特性に基づき、各対象空間の形状種別を「部屋」、「通路」に振り分ける。
【０１１４】
ここで、ステップＳ２２０における特徴・形状振分について、図１３を用いて説明する。図１３は、処理特徴・形状振分処理ルーチンを示すフローチャートである。
【０１１５】
ステップＳ２２２において、形状振分部１２０は、「空間」に振り分けられた対象空間が有する「出入口」の数に着目し、「出入口」の数が１の場合（ステップＳ２２２の＝１）、当該「空間」の形状種別を「部屋」として判定して振り分ける。一方、「出入口」の数が１よりも大きい場合（ステップＳ２２２の＞１）、当該「空間」の形状、幅、奥行の情報から「部屋」か「通路」であるかを判定し、ステップＳ２２４に進む。
【０１１６】
ステップＳ２２４において、形状振分部１２０は、その「空間」の形状に着目し、その形状が凸多角形の場合（ステップＳ２２４の凸）、当該「空間」の形状種別を「部屋」と判定して振り分け、凹または回（穴あき）多角形の場合（ステップＳ２２４の凹ｏｒ回）、当該「空間」の形状種別を「通路」と判定して振り分ける。
【０１１７】
ここで、ステップＳ２２２を行う前に、「空間」に振り分けられた対象空間の形状が複雑であるか判定し、複雑である場合には、複雑な形状を単純化した後に、凹凸回多角形の判定を行うことが好ましい。そこで、「空間」に振り分けられた対象空間の形状が複雑である場合には、図１４に示す空間形状単純化処理を行う。図１４は、空間形状単純化処理を示すフローチャートである。
【０１１８】
ステップＳ３００において、形状振分部１２０は、当該「空間」に振り分けられた対象空間の形状を、その形状に対する外接矩形を水平かつ垂直な小さな（移動体が移動する際に十分な大きさ）グリッドに分割し、それらのグリッドと元の形状が重なっているグリッドの集合を、単純化後の空間の形状として採用することで単純化する。
【０１１９】
ステップＳ３１０において、形状振分部１２０は、上記ステップＳ３００による単純化後の当該「空間」の形状の頂点の数が、元の形状の頂点の数よりも大きいか否かを判定する。
【０１２０】
単純化後の当該「空間」の形状の頂点の数が、元の形状の頂点の数よりも大きい場合（ステップＳ３１０の＞元形状の頂点数）、ステップＳ３２０において、形状振分部１２０は、当該「空間」の形状に対し形状を広げる（移動体が移動する際に十分な大きさの）バッファを生成した後に、その形状を狭める（広げた際の大きさと同値の）バッファを生成して単純化する。
【０１２１】
また、ここで、ステップＳ１４０における生成処理について、図１５を用いて説明する。図１５は、生成処理ルーチンを示すフローチャートである。
【０１２２】
ステップＳ４００において、リンク・ノード生成部１４２は、「部屋」と「通路」と「階の接続」に接続する「出入口」ノードを、「出入口」と振り分けられた対象空間の手前に対して生成する。
【０１２３】
ステップＳ４１０において、リンク・ノード生成部１４２は、対象の「空間」が「部屋」であるか、「通路」であるか、「階の接続」であるかを判定する。
【０１２４】
「空間」が「部屋」の場合（ステップＳ４１０の部屋）、ステップＳ４２０において、リンク・ノード生成部１４２は、当該「部屋」に「出入口」ノードが複数存在すれば、「出入口」ノード間を接続するように「出入口」リンクを生成する。
【０１２５】
ステップＳ４３０において、リンク・ノード生成部１４２は、出入口の数が３よりも大きい場合に、交差するリンクを除去し、ステップＳ５１０に進む。
【０１２６】
また、対象の「空間」が「通路」の場合（ステップＳ４１０の通路）、ステップＳ４４０において、リンク・ノード生成部１４２は、「通路」の形状に対する中心線を生成する。
【０１２７】
ステップＳ４５０において、リンク・ノード生成部１４２は、上記ステップＳ４４０により生成した中心線の頂点・交点に「通路」ノードを生成する。
【０１２８】
ステップＳ４６０において、リンク・ノード生成部１４２は、「通路」ノード間に「通路」リンクを生成する。
【０１２９】
ステップＳ４７０において、リンク・ノード生成部１４２は、「出入口」ノードの近傍が、「通路」ノードであるか、「通路」リンクであるかを判定する。
【０１３０】
「出入口」ノードの近傍が、「通路」ノードである場合（ステップＳ４７０の通路ノード）、ステップＳ４８０において、リンク・ノード生成部１４２は、「出入口」ノードと「通路」ノードを接続するリンクを生成し、ステップＳ５１０に進む。
【０１３１】
一方、「出入口」ノードの近傍が、「通路」リンクである場合（ステップＳ４７０の通路リンク）、ステップＳ４９０において、リンク・ノード生成部１４２は、「出入口」ノードから「通路」リンクに対し垂線を引き、その交点にノードを生成する。
【０１３２】
ステップＳ５００において、リンク・ノード生成部１４２は、「出入口」ノードと交点ノード間にリンクを生成し、ステップＳ５１０に進む。
【０１３３】
また、対象の「空間」が「階の接続」の場合（ステップＳ４１０の階の接続）、ステップＳ５１０に進む。
【０１３４】
ステップＳ５１０において、接続部１４４は、同一の出入口に対する「出入口」ノード間を「出入口」リンクで接続する。
【０１３５】
ステップＳ５２０において、接続部１４４は、階層間を接続するために、同一の「階の接続」に対する「階の接続」ノード間を接続する「階の接続」リンクを生成する。
【０１３６】
以上説明したように、本発明の実施の形態に係るネットワークデータ生成装置によれば、少なくとも屋内空間の構造と、屋内空間の構造に基づく性質を示す情報と、を有する入力データに対し屋内空間の一部領域である対象空間が部屋であるか通路であるか否かを判定し、判定結果に基づいて、リンクの集合及びノードの集合を生成することにより、屋内空間の構造を有する入力データから、屋内地図の適切なネットワークデータを効率的に生成することができる。
【０１３７】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０１３８】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【符号の説明】
【０１３９】
１０   ネットワークデータ生成装置
１００ 入力部
１１０ 屋内空間データ記憶部
１２０ 形状振分部
１３０ 振分結果記憶部
１４０ ネットワークデータ生成部
１４２ リンク・ノード生成部
１４４ 接続部
１５０ ネットワークデータ記憶部
１６０ 出力部
【図１】
2019139097.tif 000003
【図２】
2019139097.tif 000004
【図３】
2019139097.tif 000005
【図４】
2019139097.tif 000006
【図５】
2019139097.tif 000007
【図６】
2019139097.tif 000008
【図７】
2019139097.tif 000009
【図８】
2019139097.tif 000010
【図９】
2019139097.tif 000011
【図１０】
2019139097.tif 000012
【図１１】
2019139097.tif 000013
【図１２】
2019139097.tif 000014
【図１３】
2019139097.tif 000015
【図１４】
2019139097.tif 000016
【図１５】
2019139097.tif 000017