道案内用略地図のモデル化と自動同定に関する研究
06124

倉田陽平

東京大学工学系研究科都市工学専攻
住宅・都市解析研究室修士 2 年

1. 研究の背景
人間は，日常生活の中で，都市空間における「場所」の情報をやりとりする際に，あいまいな地図的表現（略地図）を多用している

略地図をコンピュータ上で扱えるようにすることは，日常生活に略地図のメリット
・ 記述が容易・ 視認性に優れる
・ 省スペース
・ データ量が少ない

身近な情報システムを構築するうえで有意義

既に事例多数（略地図の自動生成）[5]

具体的には次の 2 技術から構成
・ 略地図の出力（計算機 → 人）・ 略地図の入力（人 → 計算機）

既存研究は精確な地図に関するものが主[9]で，人間が描くような曖昧な地図 の 認 識 に 関 す る 研 究 は 少 な い [7]2. 研究の目的
日常生活でよく利用される道案内用の略地図を対象に，その中に描かれた各要素を計算機上で自動的に正確な地図データ上へ対応づける手法を開発する
これを実現させることで，略地図を正確な空間データへと変換することが可能になり，日常生活で使用される大量の略地図を情報資源として活用することが可能になる

3. 略地図データモデルの構築
まず前提として，計算機上で略地図を扱うための適切な手法（データモデル）が必要である．
しかし，既存のデータモデル[1][2]は，日常で使われるような略地図 [6]を十分に表現できていない．
そこで本研究では，実験的に得た手書きの道案内図 91 件を分析し，そこから把握した道案内用の略地図の性質にしたがって，道案内用の略地図の表現にふさわしいデータモデルを構築した[3]
主要な特徴
・

ネットワーク （道路・鉄道・河川），目印，地物名称，到達先注記 （至〜）から構成

・

ネットワークをノード＋リンクで表現 （道の繋がり方，交差点が何差路などの情報が重要になる）

・

目印は代表点で表現 （目印の 96%は建物・区画形状に関係ない記号で表現される）・目印とノード・リンクとの位置関係を明示 （目印には道角，沿道，遠方目標の三種類が存在）-1-道案内用略地図のモデル化と自動同定に関する研究
2002/2/13 修士論文ジュリー レジュメ
06124 倉田陽平

例略地図

略地図データ
目的地
東急

クロアゼしぶや

井の頭線

１０９※本研究の段階では，略地図データは，紙媒体の略地図から手動で変換し作成している
将来的には以下を想定

センター街
西武

ハチ公
渋谷駅

① ペンデバイスによる直接データ入力が可能になる② 略地図データ自体が web 上で流通するようになる③ 紙媒体の略地図をパターン認識により略地図データへ自動変換できるようになる

4. 略地図自動同定アルゴリズムの開発
略地図には描画ルールがない．そのため，作成者の空間イメージを反映して，ひどく歪んだり，必要な情報に欠いたり，間違いを含んでいたりする．しかしながら人間は，略地図の内容を自分の知識や他の地図に照らし，直ちに目的地までの経路を判別することができる．そこで，ここでは人間が略地図を同定する際に行っている推論過程について考察し，そのモデル化を試みた[4]．

素朴な発想: 出発点から目的地へと，順に略地図の経路をたどりながら同定していく

そもそも道案内のための略地図なのだから，現地を・目印が正確な地図にない場合は迷う

歩くようにして地図をたどれば目的地まで到るはず

・目印は現在位置確認目的にしか利用されず非効率

・複数の目印から略地図のスケール・向きなどを把握する
・次の目印に向かって経路を類推する・逆からたどって推論する

では，目印は他に何に使えるのか？

地図を面的に利用すること・わかりやすいところから優先して推定を進めるで発揮されるメリット

人間の推論過程: 与えられた略地図に対し，まず知っているものはないか概観し，これを手がかりとして描画対象地域・方位・スケールなどの大雑把な空間イメージをつかむ．そして，経路の順にはあまりとらわれず，わかりやすいところから同時進行的にネットワークの個々の要素を対応づけていく．

そこで本研究ではこのような人間の推論過程を模倣し，次の 4 段階の手順で同定を行うものとした．

Step 1: 略地図の目印を，正確な地図上の地物に対応づける
Step 2: Step 1 をもとに略地図の向き・スケールを大雑把に正確な地図に揃える
Step 3: Step 1 で同定した目印に隣接する道路や交差点も，正確な地図上に対応づける
Step 4: 残りの道路や交差点について，分かりやすい箇所から，順次，同定を行っていく-2-道案内用略地図のモデル化と自動同定に関する研究
2002/2/13 修士論文ジュリー レジュメ
06124 倉田陽平

Step1 目印の同定

Step2 略地図の回転・拡大縮小

略地図同定

回転・拡大縮小の流れ

略地図

実地図

略地図

Step3 隣接交差点・道路の同定

略地図

Step 1. 目印の同定

実地図

Step4 ネットワークの同定

実地図

略地図

DP matching

実地図

Euclid 回帰の決定係数

略地図の目印に名称が類似した位相的な位置関係からありえ幾何的な位置関係が最地物を正確な地図から探し出すない対応候補の組合せを削除

も似た組合せを採用

西武B館■
西武A館■
■
渋谷１０９■
１０９-②109
渋谷 109渋谷 109
109-②109-②

109
渋谷 109渋谷 109西武
西武 A 館
西武 B 館
西武 A 館
西武 B 館××

西武
西武 A 館
西武 B 館採用

略地図では道なりでないのに，実地図では道なりなので矛盾

Step 2. 略地図の回転・拡大縮小
対応点の座標で Euclid 回帰 [8]を行い，変換式の係数を求める

Step 1 で得た対応点を参考に，略地図の向き・方向・位置が実地図に揃うよう回転・拡大縮小・平行移動変換を行う

x' i = kR ? x i + b + e i

Step 3. 目印の隣接交差点・隣接道路の同定
略地図上で目印に隣接する交差点・道路を，対応す

東急

る実地図の地物からから見て同じ向きにあり，かつ形状の似た交差点・道路に対応づける．

Step 4. ネットワークの同定
わかりやすい箇所から逐次的に同定確信度が最も高いものから同定することで実現

確信度 略地図リンクと，その実地図上の対応候補(候補パス)との，対応の信頼性を示す指標．
その初期値はリンクと候補パスとの形や方向の類似性から算出
略地図のリンク

実地図の候補パス…
確信度=0.4-3-

確信度=0.7

道案内用略地図のモデル化と自動同定に関する研究
2002/2/13 修士論文ジュリー レジュメ
06124 倉田陽平
略地図
実地図

さらに 推定が進むにつれ，対応の正しさを示す証拠（右図のような候補パスどうしの整合性）が現れたら，確信度を向上させる
整合性がとれる候補パス「逆からたどって経路を類推する」ことを可能にする

５. 評価と課題以上のアルゴリズムの有効性と問題点を検討するため，銀座・渋谷の略地図各 89 例に対し評価実験を行った．なお，銀座はグリッド状，渋谷は放射環状と，街路パターンに違った特色がある．
同定成功率
Step 1

銀座

渋谷

目印

99%

85%

目印に隣接する交差点

93%

85%

目印に隣接する道路

90%

80%

起点・目的地間の経路

73%

69%

Step 3
Step 4

渋谷だけ目印の同定がうまくいかない（問題 1）
銀座は，目印は精確に同定できたものの，それに隣接する交差点や道路の同定がうまくいかない（問題 2）
経路の同定の段階では，どちらも大きく成功率を落とす（問題 3）

原因

課題点

問

渋谷は，同一系列百貨店が集中立地している「道をはさんで反対側にある」といった，目印

題ため，近接する類似名称の建物への対応ミス同士の位相的位置関係の情報をさらに熟慮し，1がきわめて発生しやすい現実に成立しえる対応か否かをチェックする．

問

銀座の略地図では目印の情報があまり用い 目印の代わりによく描かれている街路名の情

題られない．この結果， Step 2 で正しく略地報を積極的に利用し，地図の向きを推定する手

2

図の向きの把握（回転）ができなかった法を取り入れる．

問

本手法は，分かりやすいところから一方的に途中で間違いが発覚した場合，人間のように間題同定を行うため，ささいな対応ミスが連鎖的違ったと思しき時点まで戻ってやり直せる手

3に経路の同定ミスをもたらす．

法（バックトラック）を取り入れる．

６. まとめ本研究では，道案内用の略地図を計算機上で表現するためのデータモデルを構築し，そのもとで略地図データを正確な地図データ上へと対応づける略地図自動同定アルゴリズムを開発した．
さらに開発したアルゴリズムの評価を行い，今後の技術的課題を明らかにした．
主要参考文献[1] 有川正俊・久保田光一 (2000) G-XML の概要―GIS コンテンツの相互流通の実現に向けて―. 「電子情報通信学会技術報告書」,
AI2000-36, 33-40[2] 久保田光一 (1999) G-XML について―白地図・略地図表現の試み.「第 4 回統合型地理情報システムシンポジウム予稿集」, 67-75[3] 倉田陽平・岡部篤行 (2002) 道案内用略地図の自動同定アルゴリズム. 「GIS 理論と応用」, forthcoming[4] 倉田陽平・岡部篤行 (2001) 手書き道案内図の分析とモデル化―略地図自動同定に向けて―. 「地理情報システム学会講演論文集」, 10, 177-180[5] 馬場口登・堀江政彦・上田俊弘・淡誠一郎・北橋忠宏 (1997) 経路理解支援のための略地図とその案内文の生成システム. 「電子情報通信学会論文誌」, J80- D- II(3), 791-800[6] 若林芳樹 (1998) 電話帳広告の道案内図に関する記号論的分析の試み. 「地図」, 36(2),1-11[7] Egenhofer, M. J. (1997) Query Processing in Spatial-Query-by-Sketch. Journal of Visual Languages and Computing, 8(4), 403-424[8] Tobler, W. R. (1994) Bidimensional Regression, Geographical Analysis. 26(3), 187-212[9] Walter, V. and Fritsch, D. (1999) Matching spatial data sets: a statistical approach. International Journal of Geographical InformationScience, 13(5), 445-473-4-