(57)【要約】【課題】３次元情報のデータ量を削減する。【解決手段】複数のノード２２、及びノード２２間のリンク２６により表される３次元情報２０を処理する３次元情報処理装置１０であって、複数のノード２２のうち、同一の平面に属するノード群により構成されるリンク列の端点に相当するアンカーノード２６の３次元位置情報を保持するアンカーノード情報保持部１２と、アンカーノード２６を用いて平面を特定するためのパラメータ（α，β）、及び平面ＩＤを含む平面情報を保持する平面情報保持部１４と、複数のノード２２の各々が属する平面の平面ＩＤ、平面上での各ノード２２の２次元位置情報、及びリンク情報を含むノード情報を保持するノード情報保持部１６と、アンカーノード情報と、平面情報と、ノード情報とに基づいて、各ノード２２の３次元位置を復元する復元部１８とを含む。【選択図】図２
2020077232.tif 000002
【特許請求の範囲】
【請求項１】
複数のノード、及び前記ノード間の接続関係により表される３次元情報を処理する３次元情報処理装置であって、
前記複数のノードのうち、同一の平面に属するノード群により構成されるリンク列の端点に相当するノードの３次元位置情報、前記端点に相当するノードを用いて前記平面を特定するためのパラメータ、及び前記平面の識別情報を含む平面情報を保持する平面情報保持部と、
前記複数のノードの各々が属する平面の識別情報、前記平面上での各ノードの２次元位置情報、及び前記ノード間の接続関係を示す情報を含むノード情報を保持するノード情報保持部と、
前記平面情報保持部に保持された前記平面情報と、前記ノード情報保持部に保持された前記ノード情報とに基づいて、前記各ノードの３次元位置を復元する復元部と、
を含む３次元情報処理装置。
【請求項２】
前記パラメータは、前記端点に相当する第１のノードと第２のノードからなるベクトルに直交する単位ベクトルであって、前記第１のノードを始点、及び前記ノード群が属する平面上の前記第１のノード及び前記第２のノード以外の点を終点とする単位ベクトルの３次元成分を特定する２つの値である請求項１に記載の３次元情報処理装置。
【請求項３】
前記復元部は、前記第１のノードの３次元位置情報と、前記第２のノードの３次元位置情報と、前記第１のノード、前記第２のノード、及び前記パラメータにより特定される前記単位ベクトルの終点に相当する点の３次元位置情報とに基づいて特定される平面と、前記平面上での各ノードの２次元位置情報とに基づいて、前記各ノードの３次元位置情報を復元する請求項２に記載の３次元情報処理装置。
【請求項４】
複数のノード、及び前記ノード間の接続関係により表される３次元情報のデータ構造であって、
前記複数のノードのうち、同一の平面に属するノード群により構成されるリンク列の端点に相当するノードの３次元位置情報、前記端点に相当するノードを用いて前記平面を特定するためのパラメータ、及び前記平面の識別情報を含む平面情報と、
前記複数のノードの各々が属する平面の識別情報、前記平面上での各ノードの２次元位置情報、及び前記ノード間の接続関係を示す情報を含むノード情報と、
を含む３次元情報のデータ構造。
【請求項５】
コンピュータを、請求項１〜請求項３のいずれか１項に記載の３次元情報処理装置を構成する各部として機能させるための３次元情報処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３次元情報処理装置、３次元情報のデータ構造、及び３次元情報処理プログラムに係り、特に、ノードとリンクとで表される３次元情報についての３次元情報処理装置、３次元情報のデータ構造、及び３次元情報処理プログラムに関する。
【背景技術】
【０００２】
従来、例えば、道路地図データやＣＡＤデータなどのように、３次元点群に相当するノードと、ノード間を接続するリンクとで３次元情報を表すことが行われている。
【０００３】
例えば、道路地図を見栄え良く表示したり、マップマッチングを見栄え良くかつ精度良く行ったりすることを可能とする地図データの構造が提案されている（特許文献１参照）。この地図データでは、道路をノード及びリンクの概念で管理してデータを有する地図データにおいて、各リンクに対して道路の形状を表すポリゴンデータを持つ。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００４−２７１８１４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、特許文献１に記載の技術において、ポリゴンデータは、３次元座標を持つ点群で構成されるため、地図のデータ量が膨大となる恐れがある。
【０００６】
本発明は、上記事情を鑑みて成されたものであり、３次元情報のデータ量を削減することができる３次元情報処理装置、データ構造、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するために、本発明に係る３次元情報処理装置は、複数のノード、及び前記ノード間の接続関係により表される３次元情報を処理する３次元情報処理装置であって、前記複数のノードのうち、同一の平面に属するノード群により構成されるリンク列の端点に相当するノードの３次元位置情報、前記端点に相当するノードを用いて前記平面を特定するためのパラメータ、及び前記平面の識別情報を含む平面情報を保持する平面情報保持部と、前記複数のノードの各々が属する平面の識別情報、前記平面上での各ノードの２次元位置情報、及び前記ノード間の接続関係を示す情報を含むノード情報を保持するノード情報保持部と、前記平面情報保持部に保持された前記平面情報と、前記ノード情報保持部に保持された前記ノード情報とに基づいて、前記各ノードの３次元位置を復元する復元部と、を含んで構成されている。
【０００８】
本発明に係る３次元情報処理装置によれば、複数のノード、及びノード間の接続関係により表される３次元情報を処理する３次元情報処理装置において、平面情報保持部には、複数のノードのうち、同一の平面に属するノード群により構成されるリンク列の端点に相当するノードの３次元位置情報、端点に相当するノードを用いて平面を特定するためのパラメータ、及び平面の識別情報を含む平面情報が保持されている。また、ノード情報保持部には、複数のノードの各々が属する平面の識別情報、平面上での各ノードの２次元位置情報、及びノード間の接続関係を示す情報を含むノード情報が保持されている。そして、復元部が、平面情報保持部に保持された平面情報と、ノード情報保持部に保持されたノード情報とに基づいて、各ノードの３次元位置を復元する。これにより、所定数以上のノードを含む３次元情報において、各ノードの３次元位置情報を保持する場合に比べ、各ノードの３次元情報のデータ量を削減することができる。
【０００９】
また、本発明に係る３次元情報処理装置において、前記パラメータは、前記端点に相当する第１のノードと第２のノードからなるベクトルに直交する単位ベクトルであって、前記第１のノードを始点、及び前記ノード群が属する平面上の前記第１のノード及び前記第２のノード以外の点を終点とする単位ベクトルの３次元成分を特定する２つの値とすることができる。これにより、平面を特定するためのパラメータの情報量を抑制することができ、３次元情報のデータ量を削減することができる。
【００１０】
また、本発明に係る３次元情報処理装置において、前記復元部は、前記第１のノードの３次元位置情報と、前記第２のノードの３次元位置情報と、前記第１のノード、前記第２のノード、及び前記パラメータにより特定される前記単位ベクトルの終点に相当する点の３次元位置情報とに基づいて特定される平面と、前記平面上での各ノードの２次元位置情報とに基づいて、前記各ノードの３次元位置情報を復元することができる。
【００１１】
また、本発明に係る３次元情報のデータ構造は、複数のノード、及び前記ノード間の接続関係により表される３次元情報のデータ構造であって、前記複数のノードのうち、同一の平面に属するノード群により構成されるリンク列の端点に相当するノードの３次元位置情報、前記端点に相当するノードを用いて前記平面を特定するためのパラメータ、及び前記平面の識別情報を含む平面情報と、前記複数のノードの各々が属する平面の識別情報、前記平面上での各ノードの２次元位置情報、及び前記ノード間の接続関係を示す情報を含むノード情報と、を含むデータ構造である。
【００１２】
また、本発明に係る３次元情報処理プログラムは、コンピュータを、上記の３次元情報処理装置を構成する各部として機能させるためのプログラムである。
【発明の効果】
【００１３】
本発明の３次元情報処理装置、データ構造、及びプログラムによれば、同一平面に属するノードについて、各ノードが属する平面を特定するための情報と、平面上での２次元位置情報とを保持しておくことにより、３次元情報のデータ量を削減することができる。
【図面の簡単な説明】
【００１４】
【図１】本実施形態において処理の対象となる３次元情報を説明するための図である。
【図２】本実施形態に係る３次元情報処理装置の機能ブロック図である。
【図３】アンカーノード情報保持部の一例を示す図である。
【図４】平面情報保持部の一例を示す図である。
【図５】パラメータ（α，β）を説明するための図である。
【図６】ノード情報保持部の一例を示す図である。
【図７】本実施形態における３次元情報処理の一例を示すフローチャートである。
【図８】サンプルケースの３次元情報を示す図である。
【発明を実施するための形態】
【００１５】
以下、図面を参照して本発明の実施形態を詳細に説明する。
【００１６】
まず、本実施形態で対象とする３次元情報について説明する。
【００１７】
図１に示すように、本実施形態では、例えば、３次元の線分地図データのように、複数のノード２２と、ノード２２間を接続するリンク２４とにより表される３次元情報２０を処理の対象とする。また、３次元情報２０において、複数のノード２２のうち、同一の平面に属するノード群により構成されるリンク列の端点に相当するノードをアンカーノード２６という。すなわち、２つのアンカーノード２６間のリンク列で接続されたノード２２と、その２つのアンカーノード２６とは、同一の平面に属する。図１では、アンカーノード２６を斜線の丸で、アンカーノード２６以外のノード２２を白丸で表している。
【００１８】
３次元情報処理装置１０は、ＣＰＵと、ＲＡＭと、後述する３次元情報処理を実行するための３次元情報処理プログラムを記憶したＲＯＭとを備えたコンピュータで実現することができる。ＣＰＵが３次元情報処理プログラムを実行することで、コンピュータが３次元情報処理装置１０として機能する。
【００１９】
３次元情報処理装置１０は、機能的には、図２に示すように、アンカーノード情報保持部１２と、平面情報保持部１４と、ノード情報保持部１６と、復元部１８とを含む。なお、アンカーノード情報保持部１２及び平面情報保持部１４は、本発明の平面情報保持部の一例である。
【００２０】
アンカーノード情報保持部１２は、アンカーノード２６に関するアンカーノード情報を保持する。具体的には、アンカーノード情報保持部１２は、図３に示すように、アンカーノード情報として、アンカーノード２６の識別情報である「ノードＩＤ」と、アンカーノード２６の「３次元位置情報」とを保持する。
【００２１】
平面情報保持部１４は、アンカーノード２６間に存在するリンク列で接続されたノード群が属する平面を、アンカーノード情報を用いて特定するためのパラメータ、及びその平面の識別情報を含む平面情報を保持する。具体的には、平面情報保持部１４は、図４に示すように、平面情報として、平面の識別情報である「平面ＩＤ」と、その平面に含まれるノード群により構成されるリンク列の端点である２つのアンカーノード２６の「ノードＩＤ」と、「パラメータ（α，β）」とを保持する。
【００２２】
ここで、パラメータα及びβの定義について説明する。図５に示すように、平面に含まれるノード群により構成されるリンク列の端点である２つのアンカーノード２６を、それぞれアンカーノードＡ及びＢとする。また、アンカーノードＡとＢとの間に存在するノード群が属する平面をＨ、平面Ｈ上に存在するアンカーノードＡ及びＢ以外の点をＣと定義する。この場合において、ベクトルＡＣが単位ベクトル、かつベクトルＡＢと直交するように点Ｃを定めると、ベクトルＡＣの３次元成分は、パラメータα及びβを用いて、以下のように定義される。
【００２３】
【数１】
2020077232.tif 000003
【００２４】
ノード情報保持部１６は、複数のノード２２の各々が属する平面の識別情報、平面上での各ノード２２の２次元位置情報、及びノード２２間の接続関係を示す情報を含むノード情報を保持する。具体的には、ノード情報保持部１６は、図６に示すように、ノード情報として、各ノード２２の「ノードＩＤ」と、該当のノード２２とリンク２４で接続されているノード２２のノードＩＤで示される「リンク情報」と、該当のノード２２が属する平面の「平面ＩＤ」と、その平面上における該当のノード２２の「２次元位置情報」とを保持する。すなわち、同一平面に属するノード２２は、全て同じ平面ＩＤを含むノード情報を有する。
【００２５】
なお、アンカーノード情報保持部１２、平面情報保持部１４、及びノード情報保持部１６に保持される情報のデータ構造は、本発明の３次元情報のデータ構造の一例である。
【００２６】
復元部１８は、アンカーノード情報保持部１２に保持されたアンカーノード情報と、平面情報保持部１４に保持された平面情報と、ノード情報保持部１６に保持されたノード情報とに基づいて、各ノード２２の３次元位置を復元する。具体的には、復元部１８は、２つのアンカーノード２６の３次元位置情報と、２つのアンカーノード２６及びパラメータ（α，β）により特定される単位ベクトルの終点に相当する点の３次元位置情報とに基づいて特定される平面と、平面上での各ノード２２の２次元位置情報とに基づいて、各ノードの３次元位置情報を復元する。
【００２７】
図５の例を用いて、より具体的に説明する。復元部１８は、各平面の平面情報を平面情報保持部１４から読み出し、平面情報から、その平面のアンカーノードＡ及びＢのノードＩＤを特定すると共に、パラメータ（α，β）を取得する。復元部１８は、特定したアンカーノードＡ及びＢのノードＩＤに基づいて、アンカーノード情報保持部１２から、アンカーノードＡ及びＢの３次元位置情報を取得する。復元部１８は、取得したパラメータ（α，β）からベクトルＡＣを得て、アンカーノードＡの３次元位置情報＋ベクトルＡＣにより、平面Ｈ上の点Ｃの３次元位置情報を算出する。そして、復元部１８は、取得したアンカーノードＡ及びＢの３次元位置情報と、算出した点Ｃの３次元位置情報とに基づいて、３点Ａ、Ｂ、及びＣを通る平面の方程式を求めることにより、平面Ｈを復元する。なお、復元する平面Ｈの座標系は、原点はアンカーノードＡ（ノードＩＤが若い方のアンカーノード２６）とし、軸方向はそれぞれベクトルＡＣ、及びベクトルＡＢの向きと同じとする。
【００２８】
また、復元部１８は、ノード情報保持部１６に保持されているノード情報から、該当の平面ＩＤに対応付けられたノード２２の２次元位置情報を取得し、復元した平面Ｈを示す方程式と、２次元位置情報とに基づいて、該当の平面に属するノード２２の３次元位置情報を復元する。さらに、復元部１８は、ノード情報のリンク情報に基づいて、ノード２２間を接続する。これにより、図１に示すような３次元情報２０が復元される。
【００２９】
次に、本実施形態に係る３次元情報処理装置１０の作用について説明する。
【００３０】
３次元情報２０について、アンカーノード情報保持部１２にアンカーノード情報が保持され、平面情報保持部１４に平面情報が保持され、ノード情報保持部１６にノード情報が保持されている状態において、３次元情報２０の復元が指示されると、３次元情報処理装置において、図７に示す３次元情報処理が実行される。
【００３１】
ステップＳ１２で、復元部１８が、平面情報保持部１４に保持されている平面情報の平面ＩＤから、以下のステップの処理が未処理の平面ＩＤを１つ選択する。
【００３２】
次に、ステップＳ１４で、復元部１８が、選択した平面ＩＤを含む平面情報を、平面情報保持部１４から読み出す。
【００３３】
次に、ステップＳ１６で、復元部１８が、上記ステップＳ１４で読み出した平面情報から、その平面のアンカーノード２６のノードＩＤを特定し、特定したアンカーノードＡ及びＢのノードＩＤに基づいて、アンカーノード情報保持部１２から、アンカーノードＡ及びＢの３次元位置情報を取得する。
【００３４】
次に、ステップＳ１８で、復元部１８が、上記ステップＳ１４で読み出した平面情報から、パラメータ（α，β）を取得する。そして、復元部１８は、取得したパラメータ（α，β）と、上記ステップＳ１６で取得したアンカーノード２６の３次元位置情報とに基づいて平面の方程式を求めることにより、上記ステップＳ１２で選択した平面ＩＤが示す平面を復元する。
【００３５】
次に、ステップＳ２０で、復元部１８が、ノード情報保持部１６に保持されているノード情報から、上記ステップＳ１２で選択した平面ＩＤに対応付けられたノード２２の２次元位置情報を取得する。
【００３６】
次に、ステップＳ２２で、復元部１８が、復元した平面を示す方程式と、取得した２次元位置情報とに基づいて、平面に属するノード２２の３次元位置情報を復元する。さらに、復元部１８は、ノード情報のリンク情報に基づいて、ノード２２間を接続する。
【００３７】
次に、ステップＳ２４で、復元部１８が、平面情報保持部１４に保持されている平面情報の平面ＩＤのうち、未選択の平面ＩＤが存在するか否かを判定することにより、全ての平面について復元処理が終了したか否かを判定する。未選択の平面ＩＤが存在する場合には、ステップＳ１２に戻り、全ての平面ＩＤを選択済みの場合には、３次元情報処理は終了する。
【００３８】
以上説明したように、本実施形態に係る３次元情報処理装置によれば、アンカーノードの３次元位置情報をアンカーノード情報保持部に保持しておく。また、アンカーノードを用いて平面を特定するためのパラメータ（α，β）、及び平面ＩＤを含む平面情報を平面情報保持部に保持しておく。さらに、平面ＩＤ、平面上での各ノードの２次元位置情報、及びリンク情報を含むノード情報をノード情報保持部に保持しておく。そして、復元部が、アンカーノードの３次元位置情報と、パラメータとに基づいて平面を復元し、復元した平面と平面上での各ノードの２次元位置情報とに基づいて、各ノードの３次元位置情報を復元する。これにより、３次元情報のデータ量を削減することができる。
【００３９】
具体的には、同一平面に属するノード群につき、従来ではノード数×３次元であった位置情報のデータ量が、ノード数×２次元＋平面情報となるため、同一平面に属するノード群に含まれるノード数が一定以上である場合、３次元情報のデータ量の削減効果が得られる。
【００４０】
より具体的に、図８に示すサンプルケースの例で、各ノードの３次元位置情報を保持する場合と、本実施形態の場合とを比較する。
【００４１】
（１）各ノードの３次元位置情報を保持する場合
Ｎ［ノード数］×（３［３次元位置］×８［ｄｏｕｂｌｅ型ｂｙｔｅ数］＋１［リンク情報］×２［ｉｎｔ型ｂｙｔｅ数］）＝２６Ｎ
【００４２】
（２）本実施形態の場合
（Ｎ−２）［ノード数］×（２［２次元位置］×８［ｄｏｕｂｌｅ型ｂｙｔｅ数］＋１［リンク情報］×２［ｉｎｔ型ｂｙｔｅ数］）＋１［平面情報の数］×（２［α，β］×２［ｄｏｕｂｌｅ型ｂｙｔｅ数］＋２［アンカーノード数］×２［ｉｎｔ型ｂｙｔｅ数］＋１［平面ＩＤ］×２［ｉｎｔ型ｂｙｔｅ数］）＋２［アンカーノード数］×（３［３次元位置］×８［ｄｏｕｂｌｅ型ｂｙｔｅ数］＋１［ノードＩＤ］×２［ｉｎｔ型ｂｙｔｅ数］）＝１８（Ｎ−２）＋８＋５２＝１８Ｎ＋２６
【００４３】
Ｎ＝１０の場合、上記（１）では、２６０ｂｙｔｅ、上記（２）では、２０６ｂｙｔｅとなる。また、Ｎ＝１００の場合、上記（１）では、２６００ｂｙｔｅ、上記（２）では、１８２６ｂｙｔｅとなる。
【００４４】
このように、３次元情報に含まれるノード数が多くなるほど、本実施形態におけるデータ削減の効果が得られることが分かる。
【００４５】
なお、上記実施形態では、３次元情報の一例として、線分地図データを例示しているが、本発明は、ＣＡＤデータ、ゲームデータ等、ノードとリンクとで表される３次元情報であれば、適用可能である。
【００４６】
また、本発明のプログラムを記憶媒体に格納して提供してもよい。
【符号の説明】
【００４７】
１０   ３次元情報処理装置
１２   アンカーノード情報保持部
１４   平面情報保持部
１６   ノード情報保持部
１８   復元部
２０   ３次元情報
２２   ノード
２４   リンク
２６   アンカーノード
【図１】
2020077232.tif 000004
【図２】
2020077232.tif 000005
【図３】
2020077232.tif 000006
【図４】
2020077232.tif 000007
【図５】
2020077232.tif 000008
【図６】
2020077232.tif 000009
【図７】
2020077232.tif 000010
【図８】
2020077232.tif 000011