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