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