CSIS Discussion Paper SeriesNo. 11

二つの領域分割図の位相的適合状態を評価する方法と統合化する方法

岡部篤行

貞広幸雄

April 7, 1999

東京大学 空間情報科学研究センター113-8656

東京都 文京区

本郷7-3-1

1 はじめにある地域における属性分布のデータは、その地域を分割した地区ごとの属性データとして与えられる場合が多い。例えば 、小金井市の人口分布が 、町丁目単位の人口で与えられるといった場合である。このような地域分割した地区の集まりを「領域分割図」と呼ぼ う。
領域分割図は、いろいろな主体によって作られることが多い。例えば 、小金井市の町丁目単位の領域分割図は、統計局でも国土地理院でも作成している。小金井市の町丁目属性データを分析する時、統計局作成の属性データを統計局の作成した領域分割図で分析し 、一方で国土地理院作成の属性データを国土地理院の作成した領域分割図で分析する限り、二つの領域分割図をつき合わせる必要がないので、問題は生じない。問題は、統計局の属性データと国土地理院の属性データを複合的に利用して分析をしたい場合に生じてくる。同じ地域の同じ領域分割図であるから、ど ちらも同じであるのが期待されるが 、作成した主体が違うので、それは保証の限りでない。むしろ違う方が多いと言えよう。
このことを考えると、地域の分析を複数の主体がそれぞれに作った領域分割図単位のデータで行おうとすると、まずは分析に入る前に、複数の領域分割図がどの程度一致しているかを調べる必要が出てくる。もしも一致の度合いが悪いとなると、いくら精緻な分析をしても意味がないと言える。そこ
で、一致していない場合には、複数の領域分割図を一つに統合することが必要となってくる。これらの問題は、今までに、いくつかの研究がなされている。しかし 、汎用的な方法を提案している研究は少ない。そこで、この論文
では、この二つの問題に関し 、「位相的問題」と「計量的問題」に分けて、前者の問題について汎用的な方法を提案しよう。

1

Figure 1: 二つの領域分割図

S1 ; S2

Table 1: 名称リスト M1 ; M212345の名称
桜町
緑町
本町
貫井町
梶野町
前原町
M2の名称
緑町
桜町
本町
貫井町
梶野町
M11234562 問題
以上の問題を、もう少し明確に述べておこう。いまある地域 S があるとし 、その地域を領域分割し た領域分割図が二つ、S1 = fS11 ; : : : ; S1n1 g, S1 =fS21 ; : : : ; S2n1 gがあるとしよう。すなわち領域分割図 S1 は地区 S11 ; : : : ; S1n1より成り立ち、領域分割図 S2 は地区 S21 ; : : : ; S2n2 より成り立っているとする（図 1 参照）。また同時にこれらの地区の名称のリスト M1 = fm11 ; : : : ; m1k1 gと M2 = fm21 ; : : : ; m2k2 g が与えられているとしよう（表 1 ）。(Si ; Mi ) の対を「名称付き領域分割図」と呼ぶことにする。

2そうすると、問題は以下のようになる。
問題１ 名称付き領域分割図 (S1 ; M1 ) と (S2 ; M2 ) の適合度合いを評価する方法を考案せよ。
問題２ 名称付き領域分割図 (S1 ; M1 ) と (S2 ; M2 ) を統合して一つの領域分割図にする方法を考案せよ。
当論文では、問題１、中でも特に位相的な適合度合いについて検討することにする。

3 二つの名称付き領域分割図の適合度合いの評価方法
3.1

名称リスト の対応評価

まず、最初に行うべき評価は、名称リストの対応についてである。表１のようにそもそも町の数が合わないことは、現実には往々にしてあることである。
そこで、最初のチェックは名称リスト M1 と M2 に関して、mk1 = mk2 を確かめることである。
もし 、これが成り立てば 、次の作業に進む。そうでない場合は、入力の過ちが疑われ 、修正を行うことになる。例えば表 1 の場合、mk1 = 5; mk2 = 6であるから、表 2 のように修正する。
二つの名称リストに含まれる地区の数が一致しても、異なる地区があがっているかもしれない。そこで次は、名称リストの名称が１対１に対応しているかのチェックが必要である。表 2 の場合、M1 には梶野町があり M2 にはない。一方、M2 には前原町があり M1 にはない。これはそもそも入力のミスが疑われ 、修正を行うことになる。例えば表 3 のような修正を行う。
二つの名称リストの地区の名称が１対１に対応して、初めてつぎの作業に進むことができる。
3Table 2: 名称リスト M1 ; M2 の修正１の名称
緑町
桜町
本町
貫井町
梶野町
M112345の名称
桜町
緑町
本町
貫井町
前原町
M212345

Table 3: 名称リスト M1 ; M2 の修正２の名称
緑町
桜町
本町
貫井町
前原町
M112345の名称
桜町
緑町
本町
貫井町
前原町
M2123454

Figure 2: データベースの領域分割の修正

以上、述べてきた名称リストの一致は 、当然、満たされていると期待することではあるが 、地区の数が多いと、往々にして起きる不一致で、最初に行うべき作業であろう。なお、この作業は地図を使わずに出来る簡単な作業である。
3.2

領域分割図データが分割図となっていることの検定

領域分割図とは数学的に言うと、
S = Si1 [    [ Sini ; jSij \ Sil j = 0; j 6= l; j; l = 1; : : : ; ni (i = 1; 2)(1)が成り立つことである。一方、領域分割をコンピュータで扱うには、それを数値データで表現しなければならない。その場合、数値データで表現された領域分割図が 、数学的に領域分割となっているという保証はない。例えば 、図 2(a) などは、よく見ると、線分がつながっていなくて領域分割とはなっていない。そこで図 2(a) のように修正を行う。この作業は、もっぱら領域分割をどのようなデータ構造で扱うかによる（ GIS ソフトによる）。winged-edgeのデータ構造であれば 、領域分割をチェックする算法が提案されている。

5

Figure 3: 名称の地区と領域分割図の地区が１対１でない場合（１）3.3

地区名称と領域分割図の地区との対応付け

領域分割データが領域分割となっているとなると、次には、地区名称と地区の対応付けを行う必要がある。まず、名称リスト Mi にある地区の数 mk と領域分割図 Si にある地区の数 ni が合致していなければならない（ i = 1; 2 ）。
ni = mkであれば次の作業に進むが 、そうでない場合は、間違いが生じているので修正を行う必要がある。
次に 、地区名称と領域分割図の地区との対応が１対１になっているかのチェックを行う。まず ni = mk であっても、図 3(a) のような場合がありうる。
この場合は１対１になるように修正を行う図 3(b)。
次に ni 6= mk の場合、二つの場合に分ける必要がある。まず ni < mk の場合である。これは例えば図 4(a) のように、同じ名称の地区が飛び地している場合におこることである。このように地区が分かれてしまっている場合には、図 4(b) のように新たに地区の名称を付け、名称リストを表 4 のように修正する。
次に ni > mk の場合である。これは例えば図 5(a) のように、地区の区分分けが十分でなかった場合である。この場合は、図 5(b) のように地区を細分する修正を行う。

6

Figure 4: 名称の地区と領域分割図の地区が１対１でない場合（ ２）Table 4: 名称リストの修正３の名称緑町
桜町
本町 1
貫井町
本町 2前原町
M11234567Figure 5: 名称の地区と領域分割図の地区が１対１でない場合（ ３）以上の作業が済むと名称リストの地区と領域分割図の地区が１対１に対応することになり、ここで初めて、二つの領域分割図の適合性を検討することができる。このような状態になった名称付き領域分割図 (S1 ; M1 ) と (S2 ; M2 )を「相互比較可能な領域分割図」と呼ぶことにする。
3.4

相互比較可能な領域分割図の位相構造化

もちろんのことながら、二つの名称付き領域分割図 (S1 ; M1 ) と (S2 ; M2 ) が相互比較可能な領域分割図であるというこは、二つの領域分割図が同じであるということではない。例えば 、図 6 の二つの領域分割図は相互比較可能であるが 、領域分割図として同じでないのは明らかである。
相互比較可能な領域分割図が同じというためには、まず、地区の「並び 」が同じである必要がある。ここで「並び 」とは、緑町の隣には桜町、貫井町、本町がある、といった位相関係が同じということである。この位相関係を捉えるために、領域分割図をグラフで表すことにする。その手順はまず、領域分割図 Si の孤立ループを抽出し 、それぞれのループを１つのノード と一つのリンクで表す（図 7 ）。次に、孤立ループ以外は、度数が３以上の頂点（黒丸）をノード とし 、それらのノードと連結するノード をリンクとして表す（図 7 ）。

8

Figure 6: 相互比較可能な領域分割図

Figure 7: 領域分割図のグラフ化

その結果できるノード とリンクの集合の対は地図グラフとなり、この地図グラフを Gi で表して、Si の「領域分割地図グラフ」と呼ぶことにする。
一般に地図グラフ Gi は双対グラフをもっている。そのグラフを Gi で表すことにし 、「領域分割双対地図グラフ」と呼ぶことにしよう（ 図 8 参照）。
なお領域分割双対地図グラフでリンクは、地区の隣接関係を示している。
3.5

領域分割地図グラフの位相適合度の評価

地図グラフができると、位相関係が合っているのかを調べることができる。
図 6 の場合でそれを見てみよう。図 6 の領域分割双対グラフはそれぞれ図 99Figure 8: 領域分割グラフと領域分割双対グラフ

Figure 9: 二つの領域分割双対グラフ

10の (a)(b) のようになる。二つの地区ど うしの隣接関係だけを見て行くと、破線の部分で二つの隣接関係が異なっていることが分かる。全体的に評価するには、例えば隣接関係の同じ リンクの数全てのリンクの数

T1 =(2)なる指標が考えられる。図 9 の場合 T1 = 0:75 となる。
もう少し複雑な関係を考慮する二つの評価方法を示そう。まず二つの地区の位相的な関係は 、図 10 に示したような関係に分けることができる。領域分割 Si における二つの地区の間の距離 d(fS１ j ; S1k g; fS2j ; S2k g) を図 10 のように定める。すなわち S1j と S1k の関係を示す図から S2j と S2k の関係を示す図までの最短経路で幾つ位相関係が変わるかで、距離を測る。そうすると
領域分割図 S1 と S2 における全体の平均的な位相的ずれ D (S1 ; S2 ) は ,P
D (S1 ; S2 ) =i;j=1;:::;n d(fS1j ; S1k g; fS2j ; S2k g)

全てのリンク数(3)で評価することができる。
以上二つの指標は 、地図グラフである性質を無視している。それを考慮した指標を示そう。領域分割 Si の地区 j の隣接関係を反時計回りの輪環リスト Lij をつくる。例えば 、図 9(a) の桜町の場合、L1j =（ 緑町、貫井町、前原町、本町）となり、(b) の場合 L2j =（貫井町、緑町、前原町）となる。これらの輪環リストは局所近傍的位相を示したものである。この二つの輪環リストが一致すると、局所近傍位相は同相であると言うことができる。この概念を使って二つの領域分割図の局所近傍位相適合性 N を

N=L1j = L2jであるノード の数全てのノード の数
11(4)Figure 10: 二つの地区の位相関係とその間の位相距離12と指標化することができる。
3.6

無名称化した位相の適合性

さて以上での位相チェックで位相構造が一致していないことが分かった場合、次の手続きは 、二つの方針がある。一つは 、位相構造のずれはずれとしておき、計量的に二つの領域分割図のずれを評価する方法である。もう一つの方
針は、あくまでも位相構造を修正してから、計量的なずれの評価をする方法である。前者を「計量優先型」、後者を「位相優先型」と呼ぶことにする。
以下では、位相優先型について、手続きを検討してゆくことにしよう。まず位相構造の不一致である理由は二つが考えられる。まず、そもそも（ 無名称化した）位相構造が異なっている場合である。次に位相構造が同じにもかかわらず、単純に名称を振り間違えたという場合である。いずれにせよ、位相構造が同じかど うかを調べる必要がある。
図 9 で示した二つの領域分割図の場合、ノード 名称付きの地図グラフが一致しなかった。しかしノード の名称を取ると、二つの地図グラフは同相である。名称をとった地図グラフを「無名称地図グラフ」と呼ぶことにしよう。
さて問題は問題３

二つの無名称地図グラフが同相であるかど うかを調べる方法を考案せよ。となる。一般に平面グラフの同相問題は 、多項式オーダの計算時間で解く
coding 法が提案されている。ここではグラフが地図グラフでかつ領域分割図であるという特殊性を利用して、それに変わる新たな方法を提案しよう。
まず、S1 の双対領域分割グラフの外部境界に接する地区を抽出する（ 図11(a) の細線の部分）。この抽出した部分は、環状 R11 になっている。同様にして、S2 の双対領域分割グラフの外部境界に接する環状地区 R12 を抽出する。

13

Figure 11: 皮むき法

次に、R11 を固定して R12 を回転させ、R11 と R12 が一致するかど うかを調べる。もし一致するところがなかったら、同相ではありえない。
一致した場合、R11 と R12 を除去する（ 図 11(b) ）。それに対して上と同じ作業を行い R21 と R22 を求める（ 図 11(c) の細線の部分）。R21 と R22 が一致するかど うかを調べる。もし一致するところがなかったら、同相ではありえない。
以下、同様にして「 皮」をむくようにして、全てが同相であれば 、無名
称領域分割地図グラフは同相である。

14

Figure 12: 位相の違いが起きやすい場合
3.7

無名称地図グラフが同相である場合の名称振り間違いの検出

無名称地図グラフが同相であるとなると、名称の振り間違えである可能性がある。例えば図 9 の場合、その可能性がある。この場合、ど ちらかが正しいものであるというのが分かっていれば 、修正は簡単で、正しい方の名称リストと地区対応表に合わせればすむ。
ど ちらが正しいか分からない場合は、所詮、この段階で直しようがない。
再度、最初に戻ってどこが違っているかを再検討するしかない。この段階でできることは、輪環リストが違うところを図示して、修正を容易にすることであろう。
3.8

局所近傍位相の修正

無名称地図グラフが同相でないとなると、位相構造が異なっていることになる。この場合、問題は複雑である。名称の振り間違えに加え、位相構造の違いが重なるからである。であるから方法は、ヒューリスティックとならざ るをえない。その一つを以下に示そう。
位相構造の違いは、二つのノードが近い場合に起きやすい。例えば図 1215

Figure 13: 図 12 の双対領域分割グラフを参照されたい。このような領域分割図の場合、デジタイズの具合によって、両方、ありえることである。しかし位相的には図 13 のようになり、同相ではない。であるが 、ノード の付け替えで、同相になりうる状態である。このような場合は、修正してど ちらかに統一するのがよいであろう。
この修正を行う手順は次のようにすればよい。
Step 0

入力データ：ノード の輪環リスト、領域分割データ、閾値距離

Step 1

領域分割地図グラフのノード 間距離が閾値距離より小さいリンクを選ぶ。

Step 2

そのリンク lj に対応する双対領域分割地図グラフのリンク lj0 を定める（ 図 14(a) 参照）。

Step 3

リンク lj0 を共有する双対領域分割図グラフの地区をなすノード の内、リンク lj0 の端点ノード 以外の二つのノード を求める（ 図 14(b) の太線の円）。

Step 4

リンク lj0 をその二つのノード 間のリンク lj00 にフリップする（図 14(c) ）。

16

Figure 14: 局所位相の修正
Step 5

リンク lj00 に対応するように領域分割地図グラフの位相を修正する（図12(b) の領域分割となる）。

4 おわりに以上の位相修正によって最終的に位相構造が一致する場合もあれば 、そうでない場合もある。ない場合には、最初に戻って出直すこととなる。一致した場合を「相互計量比較可能な領域分割」と呼ぶことにし 、その評価方法は 、稿をあらためて考案することにする。
謝辞この研究は、科学技術事業団「空間情報科学研究のためのデータベース開発研究」で行われている研究の一部である。研究会の方々の貴重なコメント、特に奥貫圭一氏のコメントに感謝する。

17