スライド 1

道路画像からのネットワーク構造の抽出
指導教官
宮本裕一郎 助教
上智大学理工学部機械工学科
管理工学講座
学籍番号A0571148 宇垣 承宏
目次
1 序論
2 提案手法
3 細線化
4 MAT(Medial Axis Transform)
5 まとめ
研究背景;道路ネットワークの作成
近年、高度道路交通システムへの関心が高まっている.
例)カーナビetc
現在、カーナビの道路ネットワークは手作業で作成
非常に手間がかかる
多額の人件費が必要
つまり!!!!
計算機を用いた道路ネットワーク作成の
自動化が望まれる
1.2
目的
既存の道路画像からの
ネットワーク構造抽出の半自動化
2 提案手法:細線化とMAT近似法
2種類の手法を用いて道路ネットワーク作成を行う
細線化の利用
・4連結性の細線化
・Hilditchの細線化(8連結性)
MAT近似法の利用
・MAT近似法(CDT)
3 細線化とは
画像を幅1pixelの線画像に変換する
処理である.
8連結性
4連結性
細線化の例
次は、
今回の実験に使用するHilditchの細線
化と4連結性の細線化のアルゴリズム
3.1 8連結の細線化法(Hilditchの細線化)
①背景画素を0、図形画素を1とする.
②条件を満たす画素を探す。
条件
図形画素(1)である
境界点である
端点を削除しない
孤立点を保存する
連結性を保存する
③条件を満たした画素を消す
④消せる画素がなくなるまで①~③を繰り返す
3.2 4連結の細線化
Hilditchの細線化法とほぼ同様のやりかた
ただし,条件が違う!!!
画素の探索方向によって条件が変わる.
左上から右下に向かって探索する場合に消去できる条件
以下の3パターンのうちいずれかを満たせば消去できる
S
G
1;図形画素
0;背景画素
X;どっちも画素でもよい
3.2 4連結の細線化
Hilditchの細線化法とほぼ同様のやりかた
ただし,条件が違う!!!
画素の探索方向によって条件が変わる.
右下から左上に向かって探索する場合に消去できる条件
以下の3パターンのうちいずれかを満たせば消去できる
G
S
1;図形画素
0;背景画素
X;どっちも画素でもよい
3.2 4連結の細線化
Hilditchの細線化法とほぼ同様のやりかた
ただし,条件が違う!!!
画素の探索方向によって条件が変わる.
右上から左下に向かって探索する場合に消去できる条件
以下の3パターンのうちいずれかを満たせば消去できる
S
G
1;図形画素
0;背景画素
X;どっちも画素でもよい
3.2 4連結の細線化
Hilditchの細線化法とほぼ同様のやりかた
ただし,条件が違う!!!
画素の探索方向によって条件が変わる.
次に
左下から右上に向かって探索する場合に消去できる条件
以下の3パターンのうちいずれかを満たせば消去できる
細線化(4連結,8連結)の実験結果,
G考察を示す.
S
1;図形画素
0;背景画素
X;どっちも画素でもよい
細線化(8連結,4連結)の実験結果と考察
今回は一例として国土地理院のベクトルデータを利用.
このデータの道路領域に細線化を行った.
8連結の細線化を試行した結果
8連結の細線化によって生じた
歪み部分を枠で囲んだ。
枠で囲まれた部分を拡大すると!
ビットマップデータ
ベクトルデータ
8連結の細線化によって生じた歪み部分の拡大図
次に
4連結性の細線化の
実験結果を示す
交差点に歪みがある
道路を正確に抽出できていない
4連結性の細線化を試行した結果
歪みを抑制する方法を提案する.
道路を正確に抽出している
8連結の細線化同様に交差点付近では歪みがある.
3.3
歪みの抑制
本研究で提案する歪みの抑制のアルゴリズム
歪みのある交差点を発見
歪みのある交差点候補をP1,P2とおく
P1,P2の中心点を理想の交差点をP3とする
(一定範囲内に複数交差点候補がある)
歪みのある交差点画素左からP1,P2
理想の交差点位置P3((P1+P2)/2)
3.3
歪みの抑制
本研究で提案する歪みの抑制のアルゴリズム
一定の範囲上にある道路画素からP3を結ぶ
歪みのある交差点画素付近の一定の範囲の画素を0にする.
歪みを抑制
この歪み抑制アルゴリズムを元に実験を行う
抑制アルゴリズムを適用すると
交差点候補
一定範囲内に複数交差点候補がある所
この歪み抑制アルゴリズムを元に実験を行う
歪みを抑制できた
4
MAT(Medial Axis Transform)
MATは図形の中心軸を表している.
MATの定義
① 最大内接円(2点以上で接する)を埋め込む
② 内接円の中心点を結ぶ
③ 中心軸が抽出できる
次にMAT近似法について説明を行う.
MAT近似法は以下の①から④の手順で計算する
①Delaunay Triangulation
②CDT(Constrained Delaunay Triangulation)
③Delaunay Edgeの内外判定
④中心軸抽出
①Delaunay Triangulation
三角形分割の一つ
最小角最大化
三角形の内接円の中に点がない.
最小角を最大化
MAT近似法は以下の①から④の手順で計算する
①Delaunay Triangulation
②CDT(Constrained Delaunay Triangulation)
③Delaunay Edgeの内外判定
④中心軸抽出
②CDT(Constrained Delaunay Triangulation)
Constrained Line
Delaunay Triangulation
Constrained Line(制約の線)をいれる
Constrained Lineを残したまま
再三角形分割
Constrained Line
今回の実験で提案する
再三角形分割の方法を次に示す
Constrained Line
Constrained Line
再三角形分割法
P2
P1
P3
P
P4
Delete Line
① Constrained Lineと交わったDelaunay EdgeをDelete Line
とする.
②Constrained Lineの中点をPとする
③各々のDelete Lineの端点をP1,P2・・・Pnとする
④Delete Lineを消去し,P点とPmを線で結ぶ(m=1.2・・・n)
MAT近似法は以下の①から④の手順で計算する
①Delaunay Triangulation
②CDT(Constrained Delaunay Triangulation)
③Delaunay Edgeの内外判定
④中心軸抽出
③Delaunay Edgeの内外判定
角度の総和による内外判定.アルゴリズムと例を下に示す.
①内外判定を行う対象の点をPとおく
②図形の点を順にP1,P2・・・Pnとおく
③PとP1,P2・・・Pnの角度の和を計算
P1
P2
P3
P8
P5
P6
P1
P4
凹図形の内判定
角度の和が360
P2
P3
P7
P8
P5
P6
P4
凹図形の外判定
角度の和が0
P7
MAT近似法は以下の①から④の手順で計算する
①Delaunay Triangulation
②CDT(Constrained Delaunay Triangulation)
③Delaunay Edgeの内外判定
④中心軸抽出
④中心軸抽出
内外判定後のCDTから中心軸を抽出する.
アルゴリズムと例を下に示す
R=1
R=2
R=3
CDT
内外判定
R=1
R=2
R=3
①それぞれ三角形の共有している辺の数Rをだす.
②R=1;なにもしない
R=2;共有している辺のそれぞれの中点を結ぶ
R=3;三角形の重心と,三角形の辺のそれぞれの中点を結ぶ
MAT近似法
①Delaunay Triangulation
②CDT(Constrained Delaunay Triangulation)
③Delaunay Edgeの内外判定
④中心軸抽出
MAT近似法を仮想の
地図データで実験する
仮想の地図データでのMAT近似法
①仮想の地図データを作る
②MAT近似法を行う
R=1
R=2
R=3
MAT近似法の結果から考察を行う
仮想の地図データ
MAT近似法
仮想の地図データでのMAT近似法
考察
交差点に歪み
直線部分は中心
よって
歪みを抑制できれば
正確なネットワークを抽出できる
まとめ
2種類の手法を用いて道路ネットワーク作成を行った
細線化の利用
・4連結性の細線化
・Hilditchの細線化(8連結性)
・歪み抑制
MAT近似法の利用
・MAT近似法
・CDTにおける再三角形分割