説明

領域情報重複判定演算装置及び方法及びプログラム

【課題】 2次元領域を表すメッシュデータを保持するメモリ量を削減し、かつ、領域に対する演算を高速に実行する。
【解決手段】 本発明は、入力された領域データのメッシュIDの集合の各メッシュIDの組をシンボルの組合せに変換し、記憶手段に格納し、領域データに対する演算命令を前記記憶手段に格納されているシンボルの組合せに適用して実行し、領域演算処理手段の実行結果を入力された領域データと同様の形式に変換して出力する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、領域情報重複判定演算装置及び方法及びプログラムに係り、特に、地理情報処理において頻出する2次元領域の重複判定演算を高速に行うための重複判定演算装置及び方法及びプログラムに関する。
【背景技術】
【0002】
地理情報処理システムとは、計算機上で地図およびそれに関連する情報を保持及び処理するシステムのことをいう。地理情報システムでは、地図上に存在する様々なオブジェクトを対象とした処理を行う。典型的なオブジェクトとして、2次元領域がある。例えば、特定の施設や県、町といった対象は、地図上では2次元領域として表すことができる。また、具体的な対象の他に、雨が降っている地域やある人の生活圏、宅配ピザ屋が配達可能な範囲といった、何らかの性質をもった場所も2次元領域として表現することができる。
【0003】
2次元領域オブジェクト群に対する代表的な処理として、領域間の集合演算がある。例えば、2つの2次元領域に対して、それらに重なりがあるかどうかを求める処理は、領域間の積集合を求めることに相当する。図1は、2つの領域AとBに対し、積集合(A∩B)を求めた例である。領域に対する集合演算を行うことによって、ある人の生活圏、かつ、これまで、このような領域に対する演算は、領域を小さな矩形領域(メッシュ)の集合として表現し、その上で演算を行う方法が主にとられてきた(例えば、非特許文献1参照)。しかし、メッシュとして保持した場合には、メッシュの個数に比例した時間で集合演算が効率的に実行でき、また、複数の多角形オブジェクトによって表現されるような領域に対しても、そうでない場合と同様の効率で処理を行うことが可能であった。
【先行技術文献】
【非特許文献】
【0004】
【非特許文献1】小林優介、「ラスターGISを用いた森林の周縁部と内部の分析手法に関する研究」,ランドスケープ研究Vol. 69 (2005) , No. 5 781-784.
【発明の概要】
【発明が解決しようとする課題】
【0005】
しかしながら、上記の従来の技術は、メッシュによる表現方法は近似的なものであり、一つ一つのメッシュのサイズを大きくとると、近似誤差が大きくなるという問題があった。一方、メッシュを小さくとると、ある領域を表すために必要なメッシュの個数が増大し、それに伴って計算回数及び記憶容量が膨大になるという問題があった。
【0006】
本発明は、上記の点に鑑みなされたもので、2次元領域を表すメッシュデータを保持するメモリ量を削減し、かつ、領域に対する演算を高速に実行することが可能な重複判定演算装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【0007】
上記の課題を解決するため、本発明は、入力された領域データの2次元領域の重複を判定するための領域情報重複判定演算装置であって、
前記入力された領域データのメッシュIDの集合の各メッシュIDの組をシンボルの組合せに変換し、記憶手段に格納するZDD変換処理手段と、
前記領域データに対する演算命令を前記記憶手段に格納されている前記シンボルの組合せに適用して実行する領域演算処理手段と、
前記領域演算処理手段の実行結果を前記入力された領域データと同様の形式に変換して出力する出力手段と、を有する。
【発明の効果】
【0008】
本発明は、ゼロサプレス型二分決定グラフ(ZDD)と呼ばれるデータ構造(メッシュIDの組をシンボルの組合せに変換した構造)を用いて領域を表現する。ZDDは組み合わせ集合を効率的に保持することが可能なデータ構造であり、メッシュの集合を既存手法よりもより少ないメモリ量で保持することができる。さらに、領域に対する集合演算を、メッシュの集合を表現するZDD間での集合演算によって効率的に実行できるため、演算に必要な計算量も削減することができる。
【0009】
これにより、2次元領域を表すメッシュデータを省メモリで保持し、かつ領域に対する演算が高速に実行できるという効果が得られる。
【図面の簡単な説明】
【0010】
【図1】従来技術における領域A,Bに対する積集合の例である。
【図2】本発明の一実施の形態における重複判定演算装置の構成図である。
【図3】本発明の一実施の形態における演算入力部に入力される演算命令である。
【図4】本発明の一実施の形態における{a,c},{b},{c}を表すZDDの例と、計算機上の表現である。
【図5】本発明の一実施の形態における処理のフローチャートである。
【図6】本発明の一実施の形態における入力データの例である。
【図7】本発明の一実施の形態におけるメッシュ化された入力データである。
【図8】本発明の一実施の形態におけるメッシュ化されたデータの座標表現である。
【図9】本発明の一実施の形態におけるZDD変換処理のフローチャートである。
【図10】本発明の一実施の形態における組合せ集合を得るためのID付与例である。
【図11】本発明の一実施の形態における組み合わせ集合によるメッシュデータの表現である。
【図12】本発明の一実施の形態におけるZDDによる表現である。
【図13】本発明の一実施の形態における領域演算処理部の演算例である。
【発明を実施するための形態】
【0011】
以下図面と共に、本発明の実施の形態を説明する。
【0012】
図2は、本発明の一実施の形態における重複判定演算装置の構成を示す。
【0013】
重複判定演算装置は、領域データ入力部1、ZDD(ゼロサプレス型二分決定グラフ)変換処理部2、ZDD記憶部3、演算入力部4、領域演算処理部5、演算結果出力部6から構成される。
【0014】
領域データ入力部1は、外部から入力データを受け取り、ZDD変換処理部2へと渡す。
【0015】
ZDD変換処理部2では、領域データ入力部1からデータを受け取り、それをZDDに変換して、ZDD記憶部3に記録する。
【0016】
ZDD記憶部3には、ZDD変換処理部2によって変換されたZDDが記録される。記録したデータは領域演算処理部5で処理される。
【0017】
演算入力部4には、領域データ入力部1から与えられる領域データに対する演算命令を入力する。演算命令の一覧を図3に示す。入力される演算は、図3の演算もしくはその組み合わせとなっている。入力された演算命令は領域演算処理部5に渡される。
【0018】
領域演算処理部5では、演算入力部4から受け取った演算命令を、ZDD記憶部3に格納されているZDDに対して実行し、その結果を演算結果出力部6に出力、もしくはZDD記憶部3に格納する。
【0019】
演算結果出力部6では、領域演算処理部5から受け取ったZDDデータを、入力データと同様の形式に変換して出力する。
【0020】
次に、ZDDについて説明する。
【0021】
ZDDは、組み合わせ集合を2分グラフの形で保持するデータ構造である。ここで、組み合わせ集合とは、あるアイテムの集合A={a1,a2,…,}に対して、e⊆Aであるようなeを要素とする集合のことである。例えば、集合B = {a,b,c}に対し、集合{ac,b,c}はBの組み合わせ集合である。ZDDによって組み合わせ集合を表した例を図4に示す。ZDDは指向性をもったグラフ構造であり、ノードは0または1のラベルをもった終端ノードと、各ノードが対応するアイテムのラベルをもった中間ノードとの2種類がある。各中間ノードは0枝、1枝と呼ばれる2つの子ノードを指すリンクを持つ。また、ひとつのZDDには先頭のノードを表すポインタがある。図4(a)は組み合わせ集合{ac,b,c}を表すZDDである。図中では、終端ノードは四角のノード、中間ノードは丸いノード、1枝は実線の矢印、0枝は点線の矢印、先頭ノードを表すポインタは実線の矢印でそれぞれ表現される。各ノード中の文字は、ノードのラベルを表す。
【0022】
ある組み合わせeが、ZDDが表す組み合わせ集合に含まれるかどうかは、以下の手続きによって知ることができる。まず、ZDDの先頭ノードを表すポインタに沿って、先頭ノードに遷移する。そこで、先頭ノードのラベルが表すアイテムがeに含まれているなら1枝が指すノードに遷移し、そうでないなら0枝が指すノードに遷移する。以上の手続きを最終的に終端ノードにたどり着くまで実行し、最終的にラベル1をもつ終端ノードに遷移し、かつeに含まれるすべてのアイテムに対応するノードを遷移してきているなら、eは組み合わせ集合に含まれる。そうでないならeは組み合わせ集合に含まれない。
【0023】
図4(a)のZDDは、計算機上では、図4(b)のように、ノードIDをインデックスとする配列として表現される。配列の一つの要素には、ノードのラベル、0枝の指すノードID、1枝の先のノードIDが格納されている。ある組み合わせ集合をZDDとして表すときには、アイテム間に予め順序を定められており、ZDD中ではあるノードのラベルであるアイテムとその子ノードのラベルであるアイテムとを比較したときに、必ず子ノードのアイテムの方が、順序が後になるという制約がある。図4のZDDでは、アイテムa,b,cの間にa,b,cの順で順序が定められているものとする。
【0024】
次に、処理の流れを説明する。
【0025】
図5は、本発明の一実施の形態における処理のフローチャートである。
【0026】
ステップ1) まず、領域データを領域データ入力部1より入力する。入力として受け取るデータは、2次元平面での領域情報をメッシュ化したものである。図6は入力データの例で、図7は図6の入力データをメッシュ化したときの概念図である。図7の図形は、図7において灰色で塗りつぶされているメッシュの集合として表される。メッシュの集合は、図8のように、メッシュを一意に識別できるIDの集合として表される。図8では、メッシュの縦方向の位置(1〜4)と横方向の位置(A〜D)の組によって、一意なIDとなっている。領域データ入力部1では、図8の形式で領域データを受け取る。なお、メッシュ化するときの縦横のメッシュの個数は予め決まっているものとする。以下では横のメッシュの個数をN、縦のメッシュの個数をMとする。
【0027】
ステップ2) 受け取った領域データをZDD変換処理部2でZDDに変換する。この処理を図9の詳細フローを用いて説明する。
【0028】
ステップ11) まず、メッシュIDの集合を受け取る。各メッシュIDは、横方向の番号i(0≦i≦N−1)と、縦方向の番号j(0≦j≦M−1)との組(i,j)によって表される。
【0029】
ステップ12) 次に、メッシュIDの集合に含まれている各メッシュIDの組を、それぞれシンボルの組み合わせに変換する。いま、NとMのそれぞれが、2の階乗、つまり正の整数p,qに対して、N=2p、M=2q、であるとする。この条件のもとで、i,jをそれぞれp桁、q桁の2進数として表し、それを連結したp+q個の0または1の列をつくる。例えばN=4,M=4だったとすると、i=2,j=3のときは、それぞれ10,11となり、長さ4の0または1の列"1011"として表現される。こうして得られた長さp+qの列を、p+q個のシンボル{s1,s2,…,sp+q}の組み合わせによって表現する。具体的には、列のうち、k番目の値が1ならばsを含む、そうでないなら含まないとして、シンボルの集合を作る。列が"1011"であったら、対応するシンボル集合は{s,s,s}となる。図10は、図8のメッシュIDの集合からシンボルの組み合わせの集合を得る例を示している。図中の灰色の各メッシュについて、メッシュの外枠の0または1に基づいてシンボル{a,b,c,d}の組み合わせが対応付けられている。最終的に得られる組み合わせ集合を図11に示す。なお、組合せ集合には、いずれのシンボルも含まない組合せが要素として含まれてもよい。そのような組合せをφとして表す。図10では左上のメッシュが含まれた場合、組合せ集合の要素としてφが含まれることになる。
【0030】
ステップ13) 組み合わせ集合が得られたら、それをZDDに変換する。組み合わせ集合からZDDを得るには、文献1「Shin-ichi Minato, "Zero-Suppressed BDDs for Set Manipulation in Combinatorial Problems", DAC'93, pp272-277」に記されているZDDの演算を適切な順序で実行すればよい。図11の組み合わせ集合については、図12のようなZDDと、そのテーブルでの表現が得られる。ここで、シンボルa,b,c,dには、順序a<b<c<dが成り立つとしている。順序は任意であり、変数順序によってZDDの性質が変化することはない。構成されたZDDのノード数は10個であり、もとのメッシュの総数よりも少なくなっている。これは、ZDDとして表現することでメッシュ集合を圧縮して表現できることを示している。構成されたZDDをZDD記憶部3に記憶し、処理を終了する。入力された各領域データは、すべてZDDとしてZDD記憶部3に蓄積される。
【0031】
ステップ3) 演算入力部4から演算命令を受け取る。演算命令は図3に示す演算のいずれかであるとする。
【0032】
ステップ4) 次に、領域演算処理部5にて、ZDD記憶部3のZDDに対して演算を実行する。各演算は、ZDDに対する典型的な演算であり、その詳細は上記の文献1に記載がある。図13は、例として2つのZDDの差集合を求めた例である。なお、ZDD同士の演算では、その出力もZDDとなる。ZDD同士の演算は、ZDDの節点数に比例する計算回数で効率的に実行することが可能であるため、メッシュ集合をコンパクトに表現することができたならば、効率的に集合演算を実行することが可能である。
【0033】
ステップ5) 領域演算処理部5は、演算の結果得られたZDDを、再度メッシュIDの集合の形に変更して、演算結果出力部6より出力する。ZDDからメッシュIDの集合を得るには、文献2「Randal E. Bryant. "Graph-Based Algorithms for Boolean Function Manipulation". IEEE Transactions on Computers, C-35(8):677-691, 1986.」にあるZDDから組み合わせ集合を得る手順によって得られたシンボル列を2進数として解釈し、メッシュIDの組に再度置き換えればよい。
【0034】
上記のように、領域データ(地図)をメッシュとして、縦横の位置を2進数で表現してシンボルに対応させ、地図領域をメッシュの集合で表現し、ZDD変換し、ZDDに対する演算処理を行うことで、高速に2次元領域の重複判定を行うことが可能となる。
【0035】
上記の図2に示す重複判定演算装置の各構成要素の動作をプログラムとして構築し、重複判定演算装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【0036】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【0037】
1 領域データ入力部
2 ZDD変換処理部
3 ZDD記憶部
4 演算入力部
5 領域演算処理部
6 演算結果出力部

【特許請求の範囲】
【請求項1】
入力された領域データの2次元領域の重複を判定するための領域情報重複判定演算装置であって、
前記入力された領域データのメッシュIDの集合の各メッシュIDの組をシンボルの組合せに変換し、記憶手段に格納するZDD変換処理手段と、
前記領域データに対する演算命令を前記記憶手段に格納されている前記シンボルの組合せに適用して実行する領域演算処理手段と、
前記領域演算処理手段の実行結果を前記入力された領域データと同様の形式に変換して出力する出力手段と、
を有することを特徴とする領域情報重複判定演算装置。
【請求項2】
入力された領域データの2次元領域の重複を判定するための装置における領域情報重複判定演算方法であって、
ZDD変換処理手段が、前記入力された領域データのメッシュIDの集合の各メッシュIDの組をシンボルの組合せに変換し、記憶手段に格納するZDD変換処理ステップと、
領域演算処理手段が、前記領域データに対する演算命令を前記記憶手段に格納されている前記シンボルの組合せに適用して実行する領域演算処理ステップと、
出力手段が、前記領域演算処理手段の実行結果を前記入力された領域データと同様の形式に変換して出力する出力ステップと、
を行うことを特徴とする領域情報重複判定演算方法。
【請求項3】
コンピュータを、
請求項1に記載の領域情報重複判定演算装置の各手段として機能させるための領域情報重複判定演算プログラム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate


【公開番号】特開2013−114581(P2013−114581A)
【公開日】平成25年6月10日(2013.6.10)
【国際特許分類】
【出願番号】特願2011−262288(P2011−262288)
【出願日】平成23年11月30日(2011.11.30)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】