卒業論文 道路画像からのネットワーク構造の抽出 平成 21 年 1 月 指導教官 宮本裕一郎 助教 上智大学理工学部機械工学科 管理工学講座 学籍番号Ａ0571148 宇垣 承宏 1
目次 1 序論 ... 3 1.1 背景 ... 3 1.2 目的 ... 5 1.3 構成 ... 5 2 基礎事項 ... 6 3 道路画像からのネットワーク構造の抽出 ... 10 3.1 提案手法 ... 10 3.1.1 細線化の利用 ... 10 3.1.2 MAT近似法の利用 ... 10 4 細線化の有効性の検証 ... 11 4.1 Hilditchの細線化法(８連結の細線化) ... 12 4.2 ４連結の細線化 ... 14 4.3 細線化(4 連結，8 連結)の実験結果 ... 17 4.4 歪みの抑制 ... 21
5 MAT(Medial Axis Transform) ... 25
5.1 CDT(Constrained Delaunay Triangulation) ... 27
5.2 内外判定 ... 29 5.3 CDTとMAT ... 32 5.5 考察 ... 33 5 まとめ ... 34 謝辞 ... 35 参考文献 ... 36 2
1 序論
1.1 背景
近年, 道路交通における安全性, 利便性の向上を目的としたITS(Inteligent Transport System: 高度道路交通システム) への関心が高まっている. 中でも カーナビゲーションシステムは, 実用性や市場規模の点から注目されているア プリケーションの一つである. カーナビゲーションシステムで重要となるのは, 地図データベースと道路ネッ トワークである.地図データは領域や線で表された情報をベクトルデータとし て保存されているものである(図1.1.1). この地図データは画像データとして の性格を持つ.道路ネットワークは交差点, 曲り角, 行き止まり等の道路の特 徴点を表すノードとそれらを結び道路の形状を表すリンクによって構成される (図1.1.2). この道路ネットワークは経路の探索, 誘導等に使用されるもので ある[1]. 高精度なナビゲーションをするためには, 交差点付近における道路ネットワー クの形状が実際の道路の接続関係や進入角度を忠実に表し, また各リンクが地 図上の道路の中心を通っている必要がある. これらの条件を満たすため現行の カーナビゲーションシステムでは, 主に紙媒体の地形図を入力として, 手作業 で抽出された道路ネットワーク情報が使用されている. しかし, 年々変化する 道路状況に迅速に対処するとともに, より詳細な地図情報を利用した高度なナ ビゲーション機能を実現するためには, 地図データベースの整備に要する人的 コストの削減が必要であり, 計算機を利用した作業の自動化が望まれている. 今日まで，道路ネットワークの自動抽出に関する様々な手法が提案されてい る．文献[2][3][4]では，道路と背景を分割する道路境界が局所的に２本の平行 線分とみなせることに着目し，地図画像から並行かつ近接する線分対を抽出し て，その中心線を連結することにより道路ネットワークを抽出している．しか しこれらの手法では，交差点，曲がり角，さらに道路幅が変化する場合などに 並行線分対の検出が難しくなり正確に道路ネットワークを抽出できないことが ある．文献[5]では周囲の道路の位置関係や道路境界線以外の情報を利用した協 調的な推定法を提案して，道路領域が文字や記号によって隠蔽されているよう な複雑な地図画像においても，並行線分対が検出できなかった道路の接続関係 をロバストかつ正確に修復することに成功している． 一方文献[5]では，地図画像を道路領域とそれ以外の背景領域に分類し，道路領 3域に ク情 状の 交差 路ネ また 要素 を持 認識 に対して細線 情報を抽出し の道路につい 差点近傍にお ネットワーク た，道路領域 素ごとに与え 持たない一般 識するアルゴ 線化処理折 している． いても，比 おける細線 クの抽出が 域の判定に えられてい 般の地図画 ゴリズムの 折れ線近似処 この方法は 比較的安定に 線化図形の歪 が困難になる に際して，カ いる固有の色 画像を利用す の開発が必要 図1.1 図1.1.2 処理を施し は，並行線 にネットワ 歪みの影響 る． カラー地図 色属性を利 する場合は 要になる． 1.1 地図デ 道路ネッ した結果に基 線分対の検出 ワーク情報を 響により，道 図画像上で道 利用している は，前処理と データ ットワーク 基づいて道 出が困難と を抽出でき 道路に正確 道路，建物 るため，こ として道路 道路ネットワ となる複雑な きる．しかし 確に対応した 物，背景の構 これらの色属 路領域を正確 ワー な形 し， た道 構成 属性 確に 4
1.2 目的
地図データから道路ネットワーク抽出の半自動化を目的とする.提案手法は2 つ.手法①として細線化を利用して既存のデジタル地図画像から道路ネットワ ークを自動抽出する. 手法②としてMAT(Medial Axis Transform)近似法を使い デジタル地図画像から道路ネットワークを自動抽出を行う. 地図情報のデジタルデータは近年入手が容易であり，例えば各自治体が作成 している都市計画図などがある．
1.3 構成
本論文の構成は次の通りである. 2 章では道路ネットワークの構築に当たって の概要と本研究で提案する手法(細線化及び MAT 近似法)の概要を示す. 3 章では 細線化の有効性の検証，実験の結果とその評価を行なう. 4 章では 3 章で行った 細線化と結果を比べるために MAT 近似法を使った実験を行い，有効性の検証も 行う．最後にまとめと今後の課題を示す. 52 基礎事項
実験環境を以下に示す.
Machine name: SOPHIA-001E5526
Operating System: Windows XP Professional (5.1, Build 2600) Service Pack 2 (2600.xpsp.050329-1536)
System Manufacturer: Dell Inc. System Model: OptiPlex 745
BIOS: Phoenix ROM BIOS PLUS Version 1.10 2.3.1
Processor: Intel(R) Core(TM)2 CPU 6600 @ 2.40GHz (2 CPUs) Memory: 3GB RAM
Page File: 597MB used, 4350MB available Windows Dir: C:\WINDOWS
DirectX Version: DirectX 9.0c (4.09.0000.0904) DX Setup Parameters: None
DxDiag Version: 5.03.2600.2180 32bit Unicode Program Language: java
Compiler: javac
以下に一般的に知られている事項を示す.
ベクトルデータ
２次元の画像データである.画像データは大きく分けて２種類で，ベクトルデ ータはそのひとつである.ベクトルデータとは，計算によって描かれているグ ラフィックデータで，「点」「線」「多角形」等の情報を座標値と属性情報で保 持し表現している.拡大縮小を行っても絵が粗くなることはない特徴をもつ. もうひとつの画像データがビットマップデータである.ビットマップデータ は格子状に配置された画素の集まりであり，各画素の位置情報は「列」「行」 で表します.図 2.1 にベクトルデータの線の例を，図 2.2 にビットマップデー タの線の例を示す. 図 2.1ベクトルデータ 図 2.2 ビットマップデータラスタ走査
ラスタ走査は各画素値をスキャンする方法.列と行の端からピクセル毎に探 索し列(行)の反対の端まで探索する.端まで探索し終わったら行(列)を１つ ずらしまた列(行)の端から探索し列(行)の反対の端まで探索する.これを繰 り返し最初に探索を開始したピクセルから行，列ともに反対の端に至るまで 繰り返す.例の図 2.3 に示す. 図2.3 ラスタ捜査 7Voro
Vo Di 点 以 図 9 つ 各 さ V( で Voonoi Dia
oronoi Dia iagram とは 点集合 P = 以下の式のよ 図 2.4 に Vo つの点をラ 各点を Voro れた領域を ( pi ) は， であることを oronoi Edgagram
agram は De は，ある n { p1, p2 ように各点 oronoi Dia ランダムに配 onoi Gener を Voronoi 領域内の を示してい ge の各交点 elaunay Tr 次元の距離 , ... , p 点の領域とそ agram の例 配置してい rator と呼 i Region と の任意の地点 いる．また 点を Voron 図 2.4 riangle を 離空間内に pm } が与え その境界に 例を示す．こ いる．Vorono 呼ぶ．また と呼ぶ．点 点において Voronoi R noi Vertex Voronoi 作成の際に において，m えられた時 に空間を分割 この例では oi Diagram Voronoi G 点 pi によっ て，pi が最 Region の境 x と呼ぶ． Diagram に必要とす m 個の点か 時，距離関数 割したもの は，2 次元の m を構成す Generator って分割さ 最も近接する 境界を Vor る．Voron から構成さ 数 d を用い のを指す． の距離空間 する点集合 によって分 された領域 る点集合の ronoi Edge oi れる いて 内に P の 分割 の要素 e， 8Dela
を Tr 各 De Deaunay Tr
Voronoi D を Delaunay riangulati 各三角形を D elaunay Ed elaunay Trriangulat
iagram にお y Triangul ion を示す Delaunay T dge と呼ぶ riangulati 図tion
おいて，隣 lation とい す．ここで Triangle と ．Delaunay ion）に利用 図 2.5 Del 隣接する Vo いう．図 2 n + 1 個の と呼ぶ．ま y Triangu 用する. aunay Tri ronoi Gene .5 に，図 の Voronoi また Delaun lation は angulatio erator 同士 2.4 に対応 Generator ay Triang 5 章の CDT on 士をつない 応する Dela r で構成さ le の境界を （Constra いだ図 unay れる を ined 93 道路画像からのネットワーク構造の抽出
3.1 提案手法
道路画像からのネットワーク構造の抽出を解く算法を２つ提案する．3.1.1 細線化の利用
画像処理の分野でよく使われている細線化処理を利用する．細線化処理の結 果は計算過程で起きる細線化処理特有の歪みが生じるので必ずしも正確なネッ トワーク構造を表していない．そこで，歪みを抑制する手法を提案し正確なネ ットワーク構造の抽出を試みる．3.1.2 MAT近似法の利用
MAT近似法を利用しネットワーク構造の抽出を試みる．有効性の検証も行う． 104 細線化の有効性の検証
細線化はThinningやSkeletonizationと呼ばれ，二値画像(白と黒の色だけで 表現された2階調の画像)を幅1ピクセルの線画像に変換する処理である．線が途 中で切れてはいけない(連結を保つ).４連結性と８連結性の細線化がある． 4連結：ある黒画素の縦方向または横方向に黒画素が存在する(ただし，孤立点 の場合を含む) 8連結：ある黒画素の縦・横方向，または斜め方向に黒画素が存在する(ただし， 孤立点の場合を含む).4連結との違いの例を図4.1，図4.2に示す. 図4.1 ８連結性 図4.2 ４連結性 また細線化の例として細線化の実行前を図4.3に細線化後を図4.4に示す． 図4.3 細線化実行前 図4.4 細線化実行後 114.1
背 る. の点 N8 No と 注 B(P0) の全 素)に -1に 以Hildit
背景画素の諧 対象となる 点をP0として 8≡{P1,P2,P odd≡{P1,P する． 注目画素P0が )=-1とする 全図形画素に にした後， に変更される 以下に6つのtchの細線
諧調値を0， るファイル て8近傍の画 P3,P4,P5,P P3,P5,P7} が次の6つの る．それ以外 について行 図形画素の る画素がな の条件を示す線化法(８連
図形画素 ルの左上から 画素P1～P8 図4.1.1 P6,P7,P8} の条件を満 外の場合は 行った後，諧 の条件を調 なくなった時 す.連結の細
素の諧調値を らラスタ走 8を図4.1.1 1 近傍画素 満たしたとき は階調値を変 諧調値が-1 調べる段階に 時点で，す細線化)
を1として細 走査により1 1に示すよ 素P1～P8 き，画素P0の 変化させな 1の全ての画 に戻って処 すべての処理 細線化を行 1を探し, 発 うに定義す の階調値を ない．この処 画素の諧調 処理を繰り返 理を終了す 行なうものと 発見したら する． を-1，すなわ 処理を原画 調値を0(背景 返す．諧調 する． とす らそ わち， 画像中 景画 調値が 12条件
条件１：図形画素である. B(P0)=1 条件２：境界点である 1 |B P | 1 N 条件３：端点を削除しない. |B P | 2 N 条件４：孤立点を保存する. C 1, N C 1 for B P0 for B P 11 条件５：連結性を保存する. N P 1 N P D P D P D P D P N D P 1 for |B P |0 for |B P | 1 n1 n NN 条件６：線幅２の線分の片側だけを削除する. すべてのn(n∈N8)に対して，次のいずれかが成り立つ． i B ii B P 0としたときのN 1 P 1 Hilditchの細線化の手順を簡潔に以下に示す． ①画像をラスタ走査する ②6 つの条件を満たす画素を発見 ③条件を見たした画素の諧調値を-1 にする ④①～③をラスタ捜査が終了するまで続ける． ⑤ラスタ捜査が終了したら諧調値が-1 の全て画素の諧調値を０にする． ⑥-1 の諧調値の画素がある場合①に戻る．ない場合終了する． 134.2 ４連結の細線化
Hilditchの細線化と同様に背景画素の諧調値を0，図形画素の諧調値を1とし て細線化を行なうものとする. 対象となるファイルの４方向(左上から右下， 右下から左上，右上から左下，左下から右上)からラスタ走査により1を探し, 発 見したらその点をcenter(黒画素)とし，近傍画素は，反時計回りに，p[0]から p[7]とする(図4.2.1). 4種類の条件のうち，少なくとも一つを満たせば，centerの諧調値を0に変更し て消去する．これを，消去が生じなくなるまで繰り返す. 図 4.2.1 近傍画素の名称 14① 画面左上から右下に向かってラスタ走査 画面左上から右下に向かって探索する場合には，左上が白(０)に，右下が黒(１) になっている場合を探し，下記のような状態の場合は中央のピクセル(丸で囲ま れている)を１から０に変更する．X は 0 か１どちらでも良い． 図 4.2.2 左上から右下に向かって探索する場合に消去できる条件 この条件を表す式は，左から p[2]*p[3]*p[4]=1 で，かつ p[6]+p[7]+p[0]=0 p[3]*p[4]*p[5]=1 で，かつ p[7]+p[0]+p[1]=0 p[4]*p[5]*p[6]=1 で，かつ p[0]+p[1]+p[2]=0 である． ②画面右下から左上に向かってラスタ走査 図 4.2.3 右下から左上に向かって探索する場合に消去できる条件 この条件を表す式は，左から p[6]*p[7]*p[0]=1 で，かつ p[2]+p[3]+p[4]=0 p[7]*p[0]*p[1]=1 で，かつ p[3]+p[4]+p[5]=0 p[0]*p[1]*p[2]=1 で，かつ p[4]+p[5]+p[6]=0 である． 15
③ 画面右上から左下に向かってラスタ走査 図 4.2.4 右上から左下に向かって探索する場合に消去できる条件 この条件を表す式は，左から p[0]*p[1]*p[2]=1 で，かつ p[4]+p[5]+p[6]=0 p[1]*p[2]*p[3]=1 で，かつ p[5]+p[6]+p[7]=0 p[2]*p[3]*p[4]=1 で，かつ p[6]+p[7]+p[0]=0 である． ④画面左下から右上に向かってラスタ走査 図 4.2.5 左下から右上に向かって探索する場合に消去できる条件 この条件を表す式は，左から p[4]*p[5]*p[6]=1 で，かつ p[0]+p[1]+p[2]=0 p[5]*p[6]*p[7]=1 で，かつ p[1]+p[2]+p[3]=0 p[6]*p[7]*p[0]=1 で，かつ p[2]+p[3]+p[4]=0 である． この①～④のパターンを消去が生じなくなるまで繰り返す. 16
4.3 細線化(4 連結，8 連結)の実験結果
今回は一例として国土地理院から刊行されているベクトルデータ(図4.3.1) を利用する．このベクトルデータをビットマップデータに変換し道路領域に細 線化を行う．Hilditchの細線化を試行した結果を図4.3.2に示す．
図4.3.1 国土地理院から刊行されているベクトルデータ 図4.3.2 Hilditchの細線化後 17計算結果は約６秒． Hilditchの細線化を実行することにより，次のことがわかる. ①交差点候補画素の座標 細線化処理後に交差点候補画素の周囲のピクセルの合計値が３以上の画素を ラスタ走査で探索することにより抽出できる. ②交差点画素同士の関係 どの交差点候補と交差点候補が接続関係があるかが計算によりわかる.計算 方法を下に示す. 1)①で抽出した交差点候補画素を1からｍまで順に数字を割り当てる(mは交 差点候補の総数) 2)1）で割り当てた交差点候補画素ｎ（n=1,2,,,m）の周囲にあるピクセルの 道路画素にnの数字を割り当てる。 3）nを割り当てられた道路画素nをラスタ探索しみつけたら周囲ピクセルの道 路画素にnを割り当てる。みつけられた道路画素は次から探索にひっかから ないように制限する。 4) 3)を繰り返し、道路画素nの周囲ピクセルに交差点画素s(s≠n)があったら sはｎと接続関係がある.nに+1をして2)に戻る。 5) 2)から4)を繰り返しすべての交差点画素が探索にひっかからないようにな ったら終了する。 1）～5)を工程を計算すると接続関係が抽出できる。 ② 交差点候補画素間の距離 ③ 判明した接続関係のある交差点候補画素と交差点候補画素の間にある道路 画素の総数が距離. 18
図 であ つも れた これ しま 図4.3.2の四 あるはずが， のの行き止 た範囲の拡大 れは本来は十 っている． 四角に囲まれ 枝がでて 止まりの道 大図（図4. 十字路であ 図4. 図4 れた範囲の てきてしまっ 道路があると 3.4）を見 あって交差点 3.3 四角 4.3.4 丸で の拡大図（図 っている． と認識して 見ると交差 点が1つであ 角で囲まれた で囲まれた 図4.3.3）を この結果か てしまう．さ 点画素付近 あるはずが た範囲の拡 た範囲の拡大 を見ると本 からだと， さらに図4. 近でも歪み が，2つある 拡大図 大図 本来は1本の 道路からい 3.2の丸で みが生じてい る結果になっ の道路 いく で囲ま いる． って 19
４連結性の細線化を図4.3.1に試行した結果を図4.3.5に示す．
計算時間は約２秒． ４連結性の細線化もHilditchの細線化同様に ①交差点画素の座標 ②交差点画素同士の関係 ③交差点画素間の距離 が得られる． 図4.3.5 ４連結性の細線化後 ４連結性の細線化とHilditchの細線化を比べると４連結性の細線化が枝が少な く道路を正確に抽出しているのがわかる．交差点画素付近の歪みの程度はほぼ 同等である． 計算時間も４連結性の細線化のほうが約 3 倍早い.これは川崎市（142.70 平方 km）の約 1/64 の面積で実験した.日本全国規模（377,835.00 平方 km）にカスタ マイズしたとしたら単純計算 1.47 時間の計算時間である（Hilditch の細線化は 4.43 時間かかる）.以上の点から４連結性の細線化がネットワーク構造抽出に有 効だと言える．次に 4 連結の細線化の際に生じる歪みの抑制について述べる. 204.4 歪みの抑制
細線化の際に交差点画素付近に歪みが生じる．つまり細線化を行うだけでは 正確な道路ネットワークを抽出できないことがわかる．しかし交差点画素以外 の道路はほぼ正確な道路ネットワークを抽出できている．よって交差点画素付 近の歪みを修正できれば道路デジタル地図データから正確な道路ネットワーク の抽出ができると言える． 細線化の処理の際に修正すべき交差点画素を抽出できる．青丸が歪みのある交 差点画素付近を示して赤丸が交差点候補の画素を示している(図4.4.1)．その修 正すべき歪みの抑制の手法を次に提案する． 図4.4.1 修正すべき歪み(交差点画素付近の歪み) 21本研
① ② ③ ④ 一定研究で提案
歪みのある 抽出方法は った場合Ｐ 理想の交差 Ｐ１，Ｐ２ 注目してい 歪みのある 道路画素か 歪みを直す 定の範囲上に案する歪み
る交差点画 は交差点画 Ｐ１，Ｐ２ 差点画素を ２の中心点 いる交差点 る交差点画 から２で計 す にある道路 図4.4.2 図4.4.4みの抑制
画素を抽出 画素Ｐ１付近 を歪みのあ を計算する． 点を理想の交 点画素付近の 画素付近の一 計算したＰ３ 路画素から② 工程① 工程③のアルゴ
近のある一 ある交差点 交差点Ｐ３ の道路画素 一定の範囲 ３を結ぶ(図 ②で計算し 図4 図ゴリズム
一定の範囲内 点画素とする とする(図 素を消す． 囲の画素を０ 図3.4.4)． したＰ３を結 4.4.3 工程 図4.4.5 工 内に交差点 る(図3.4.2 図3.4.3)． ０にする． 結ぶ(図3.4 程② 工程④ 点画素Ｐ２が 2)． 範囲上にあ 4.5)． があ ある 22この 細線 す． の歪み抑制ア 線化のみ行っ これは図4 図4.4.6 アルゴリズ った時の交 4.3.4と同じ 6 歪み抑制 ズムを元に実 図4.4 交差点画素付 じ場所であ 制前 実験を行っ 4.5 歪み抑 付近と比べ ある．抑制後 った結果が図 抑制後 べてみる．歪 後を図4.4. 図4.4. 図 4.4.5 で 歪み抑制前 7に示す． 7 歪み抑 である． 前の図4.4.6 抑制後 6に示 23
3.5 考察
歪みは修正できている．これ以外の交差点画素付近においても同様に歪みを抑 制できている．よって提案した歪み抑制は有効だったと言える．目的としてい るネットワーク構造の抽出もほぼ道路領域の中心である.よって細線化を利用 したネットワーク構造の抽出は有効性が高いと言える． 245 MAT(Medial Axis Transform)
平面上の図形はそれに最大に内接する多数の円の集合により表現され，再構 成されることができる．このときこのような最大内接円(maximal inscribed circle)の中心点の集まりを形状の中心軸(medial axis) といい，中心軸上の各 点を中心とする最大内接円の半径の情報を追加して考慮することを中心軸変換 (medial axis transform 以下 MAT) という[5]．中心軸変換は Blum が最初に 提案している．
MAT の近似法として Constrained Delaunay Triangulation(以下 CDT)を利用した 中心軸抽出方法がある．CDT は Delaunay Triangulation に制約をいれたもの． 5 章では，CDT を使った MAT 近似法でネットワーク構造の抽出の有効性を検討す る．
MA
① ② ③ 例と に最 4.3） 次にAT の定義
① 図形に内 ② 最大内接 ③ 中心軸が してＹ字の 最大内接円を 中心軸が 図 に MAT 近似法義
内接する最 接円の中心 が抽出でき の図形を用 を埋め込む が抽出できる 図 5.1 Y 図 5.3 中 法に使う CD 最大内接円( 心点を結ぶ きる 用意する（図 む（図 5.2） る（図 5.4） Y 字の図形 心軸を抽出 DT の説明を (2 点以上で 図 5.1）.用 .最大内接 ）. 形 図 出 を行う. で接する)を 用意した図 接円の中心 5.2 最大 図 5.4 を計算する 形に 2 点以 を結ぶこと 内接円の埋 4 MAT 以上接する とによって 埋め込み よう （図 265.1
Dela った いう Dela りな 今回 ①Co ②De ③De これ 図 5.CDT(
aunay Tria た Delaunay ．CDT は D aunay Tria なく Delauna 回提案する onstrained elete Line elete Line れは Delauna .1.1，図 5Constrai
angulation Edge(Dele Delaunay T angulation ay Triangu 再三角形 d Line の中 e の端点を e を消去し ay Triangu 5.1.2 に， 図ined Dela
n において ete Line) Triangulat n の性質を完 ulation の 形分割のアル 中点を P とす P1,P2・・ ，Ｐ点とＰ ulation の 図 2.5 に対 図 2.5 Delaunay Tr
，Constra を消去して tion の性質 完全に満た の性質を満た ルゴリズム する ・Pn とす Ｐｍを線で の性質を満た 対応する CD aunay Tririangulat
ined Line て再三角形分 質を満たし たしている たすような ムは る 結ぶ(ｍ＝ たさないが DT を示す． angulatiotion)
(制約の線 分割を行っ てはいない 必要はない な近似でよい 1.2・・・ が三角形分割 on )を入力し った図を CD い.MAT 近似 いので CDT い. n) 割を保って 交わ DT と 似法は も限 ている． 27次に 図 5 に CDT を使っ 5.1.1 De った中心軸 elaunay Tr 図 軸を抽出する riangulati 図 5.1.2 C る方法を段 ion と Cons CDT 段階をおって strained L て説明する Line る． 28
5.2
CD の中 よっ まず 図 5. 図形 和に内外判
DT を使った 中にあるか外 てこの節で ず図 5.1 の図 .2.1 に示す 形の外側の D による内外判判定
た中心軸を抽 外にあるか では内外判 図形を仮想 す．今回制 Delaunay E 判定を行う 抽出する方 かを判定しな 判定について 想して適当な 制約にいれた 図 5.2 Edge を消去 ． 方法は CDT なければな て説明する な点を打っ た線は Y 字 .1 Y 字図 去するのに を行ったあ ならない． る． って作った図 字の外枠の線 図の CDT にすべての D あとに Dela 図に CDT を 線． Delaunay aunay Edge を行った結果 Edge に角度 が図 果を 度の 29角度度の和によるる内外判定定のアルゴリリズム ① 内 ② 図 ③ A A この 凸図 内外判定を 図形の点を A 360 or A 0 の手法は凸な 図形と凹図形 （青）とす 図 5 図 5 を行う対象の を順に P1,P2 ∠PkPP k 360 内判 外判定 な図形でな 形の内外判 する.黒と青 5.2.2 凸図 5.2.4 凹図 の点を P と 2・・・Pn k 1 ∠ 判定 定 なくても使え 判定の例を下 青の和で内外 図形の内判定 図形の内判定 おく とおく ∠PnPP1 えてアルゴ 下に示す． 外判定. 定 図 5 定 図 5 ゴリズムもわ 反時計周り .2.3 凸図形 .2.5 凹図形 わかりやす りを+（黒） 形の外判定 形の外判定 すい． ）とし時計 定 定 計回り 30
次に下の手順で図 5.2.1 に使用する．
①すべての Delaunay Edge の中点を計算し Pn とおく(n=1,2・・m ．m は Delaunay Edge の本数) ②すべての Pm を内外判定を行う ③角度の計算には座標から逆正接(Arctangent)を使い角度 θ(ラジアン)を求め る ④ラジアンが 2πor-2πで内判定，0 で外判定. ⑤外判定ならば Pn をもつ Delaunay Edge を消去する すべての Delaunay Edge を内外判定した結果を図 5.2.6 示す． 図 5.2.6 内外判定後の CDT 31
5.3
CD アル 内外 ①三 いて ②中 Rt Rt Rt つま ①CD ②De ③中 5. 5.3. 図 5.CDTと
DT を行い， ルゴリズムを 外判定後の C 三角形分割さ て他の三角形 中心軸の抽出 1 なにも 2 共有し 3 三角形 り以下の 3 DT elaunay Ed 中心軸の抽出 2 節で用意 1，図 5.3. 3.1 CDT(内MAT
さらに内外 を以下に示 CDT から中 された図形 形との辺の 出 もしない している辺 形の外接円 3 つの手順 dge の内外判 出 意した図（Y .2，図 5.3 内外判定後) 外判定を行 示す. 中心軸を抽出 形のそれぞれ の共有してい の中点同士 の中心から 順が MAT 近似 判定 Y 字図形）に 3.3) 図 5. 行った結果 出. れの三角形 いる本数 R 士を線で結 ら各辺の中 似法である に MAT 近似 3.2 中心軸の から中心軸 形 T(T=分割 t(t=1,2・ ぶ 点に線を結 る. 似法を行った の抽出 軸の抽出を された三角 ・T)をだす 結ぶ た結果を下 図 5.5.3 M 行う． 角形の数)に す 下の図に示す MAT 近似法の にお す(図 の結果 325.4
仮 5.4. 5.5 実験 るネ 点付 抑制 MAT 近 数の 近似 られ 考えMAT 近似
仮想に用意し 1，図 5.4. 図 5. 考察 験結果からわ ネットワーク 付近に歪みが 制できるアル 近似法では の図形の集合 似法を行えば れる．よって えられる．似法の実
した地図デ .2，図 5.4 4.2 CDT(内 わかるよう ク構造が大 が生じる． ルゴリズム はデジタル地 合と考えら ばデジタル て歪みを抑験結果
データに MAT 4.3)． 図 5 内外判定後 に MAT 近似 大きく変化す 直線部分は ムの考案が必 地図データ られる．無数 ル地図データ 抑制できれば 33 T 近似法を 5.4.1 仮想 ) 似法は図形 することが はほぼ正確 必要である タを図形と 数ある図形 タから道路 ば道路ネッ を行った結果 の図 図 5.4 形の点のとり がわかる．ま 確に抽出でき る． して使う． 形のそれぞれ 路ネットワー ットワークの 果を下の図 4..3 MAT 近 りかたによ また細線化 きている． デジタル地 れの辺に制 ークを抽出 の抽出に有 図に示す(図 近似法 よって抽出で 化と同様に交 よって歪み 地図データ 制限をかけ 出できると考 有効性はある 図 でき 交差 みを タは無 MAT 考え ると5 まとめ
本論文では道路画像からのネットワーク構造の抽出を解く算法を 2 つ紹介し た．また 1 つの算法では実際に計算機上で動かして，その結果について考察し た．第 1 章では，この問題の背景および本論文の目的について述べた．第 2 章 では手法を提案し，第 3 章，第 4 章では 2 つの算法を紹介し実験を行い考察を 述べた．4 章では細線化のネットワーク構造の抽出を確認できた．第 5 章では MAT 近似法も歪みを抑制すアルゴリズムを考案すれば，歪みを修正し正確なネッ トワーク構造の抽出に有効性があると言えた． 34謝辞
末筆ながら，管理工学研究グループ配属以来，終始変わらぬ暖かいご指導で 小論を導いて下さいました宮本裕一郎助教に深謝いたします． その他お世話になりました上智大学管理工学研究室の皆々様に心からお礼を 申し上げ，ここに厚く感謝の意を表し，結びの言葉にかえさせて頂きたいと思 います． 3536
参考文献
[1] 馬場口登，“図面・地図をコンピュータで処理する” 情報メディア工学第9 章, 1999. [2] 中島正之，渡辺院猛，飯塚久登，“市街化地図に対するパラレル・ベクトル・トレー サーを用いたグラフ構造解析，”信学論(D),vol.J67-D,no.12,pp.1419-1426,Dec.1984. [3] 堀江政彦，上田俊弘，淡誠一郎，馬場口登，北橋忠宏，“ベクトル地図からの道路ネ ットワーク生成の一手法，”信技報，PRU94-134,March1995. [4] 早川卓哉，渡辺豊英，杉江昇，“仮説の生成・検証パラダイムに基づいた市街地地図 からの道路情報抽出，”情処学論，vol35,no.1,pp.62-78,Jan.1994.[5]Katz RA , Pizer SM,“Untangling the Blum Medial Axis Transform,” INTERNATIONAL JOURNAL OF COMPUTER VISION,55,139-153(2003).
