マップマッチングのアルゴリズム - PDF 無料ダウンロード

マップマッチングのアルゴリズム羽藤英二伊藤創太伊藤篤志編 : ネットワーク行動学 ( BinN studies シリーズ ), pp.84-106,2014. 2015/05/29 理論勉強会 #7 M1 山本萌美

もくじマップマッチングとは? マップマッチングのバリエーション Point to Point map-matching Point to Curve map-matching Curve to Curve map-matching 幾何解析マップマッチング位相幾何解析マップマッチングさまざまなマップマッチング 2

マップマッチングとは? GPS やデッドレコグニング技術で得られた位置データを用いてある時点で移動者がどの経路を利用しているのかあるいはその経路上のどこにいるのかを特定する技術 GPS (+ DR) 等による位置データどの経路か? その経路上のどこか? 道路ネットワーク 3

マップマッチングとは? 道路ネットワーク基本的なアルゴリズム STEP1 道路ネットワークを準備 STEP2 道路ネットワーク上に測位位置データをプロット STEP3 位置データとネットワーク上のリンクやノードとの関係を定量化通過リンクの特定凡例リンクノード STEP4 リンクごとのパフォーマンス指標 ( 所要時間や走行速度 ) の算定 4

マップマッチングとは? 道路ネットワーク基本的なアルゴリズム STEP1 道路ネットワークを準備 STEP2 道路ネットワーク上に測位位置データをプロット STEP3 位置データとネットワーク上のリンクやノードとの関係を定量化通過リンクの特定凡例測位点 STEP4 リンクごとのパフォーマンス指標 ( 所要時間や走行速度 ) の算定 5

マップマッチングとは? 道路ネットワーク基本的なアルゴリズム STEP1 道路ネットワークを準備 STEP2 道路ネットワーク上に測位位置データをプロット STEP3 位置データとネットワーク上のリンクやノードとの関係を定量化通過リンクの特定凡例通過リンク STEP4 リンクごとのパフォーマンス指標 ( 所要時間や走行速度 ) の算定 6

マップマッチングとは? 基本的なアルゴリズム定量化方法や測位補正の方法などによってさまざま手法がある STEP1 STEP2 STEP3 STEP4 道路ネットワークを準備道路ネットワーク上に測位位置データをプロット位置データとネットワーク上のリンクやノードとの関係を定量化通過リンクの特定リンクごとのパフォーマンス指標 ( 所要時間や走行速度 ) の算定 7

マップマッチングのバリエーション [1] 幾何解析 (Geometric) マップマッチング Point to Point Point to Curve Curve to Curve Road Reduction Filter(RRF) 位相幾何 (Topological) 解析マップマッチング Weighted topological algorithm Simplified algorithm by Meng (2006) Algorithm based Various Similarity Criteria by Quddus et at.(2003) 確率的 (Probabilistic) マップマッチング Elliptical/rectangular confidence region 高度な技術を利用したマップマッチング Kalman filter Dempster-Shafer s mathematical theory of evidence Flexible state-space model and particle filter Interacting multiple model Fuzzy logic model 8

マップマッチングのバリエーション幾何解析 (Geometric) マップマッチング Point to Point Point to Curve Curve to Curve Road Reduction Filter(RRF) 位相幾何 (Topological) 解析マップマッチング確率的 (Probabilistic) マップマッチング Weighted topological algorithm Simplified algorithm by Meng (2006) Algorithm based Various Similarity Criteria by Quddus et at.(2003) Elliptical/rectangular confidence region 位置データ取得技術の発達と普及とともにたくさんの手法が提案されているまずは幾何解析マップマッチングを勉強します高度な技術を利用したマップマッチング Kalman filter Dempster-Shafer s mathematical theory of evidence Flexible state-space model and particle filter Interacting multiple model Fuzzy logic model 9

Point to Point map-matching 測位点をネットワーク上の最も近いノードにマッチングするアルゴリズム STEP1 STEP2 STEP3 測位点とネットワーク上のすべてのノードとの距離を計算測位点を最も距離の小さかったノードにマッチングすべての測位点で STEP1, STEP2 をおこなうすべて終われば終了凡例測位点ノード 10

Point to Point map-matching もしもここに測位点があったら 13

Point to Point map-matching もしもここに測位点があったらノードが少ないネットワークは誤ってマッチングされやすいノードが多いネットワークほど正確にマッチングできる 14

Point to Curve map-matching 測位点をネットワーク上の最も近いリンクにマッチングするアルゴリズム STEP1 STEP2 STEP3 測位点とネットワーク上のすべてのリンクとの距離を計算測位点を最も距離の小さかったリンクにマッチングすべての測位点で STEP1, STEP2 をおこなうすべて終われば終了 15

Curve to Curve map-matching アルゴリズム STEP1 STEP2 STEP3 STEP4 STEP5 Point to point matching により候補となるノードを探索候補ノードから候補リンク探索候補ノードから候補経路を作成測位点を結びその線分の距離の和を算出すべての候補経路のうち最も測位点の経路距離と近いものを真の経路とする 17

Curve to Curve map-matching 候補経路 1 STEP1 STEP2 STEP3 STEP4 STEP5 アルゴリズム Point to point matching により候補となるノードを探索候補ノードから候補リンク探索候補ノードから候補経路を作成測位点を結びその線分の距離の和を算出すべての候補経路のうち最も測位点の経路距離と近いものを真の経路とする 19

Curve to Curve map-matching 候補経路 2 STEP1 STEP2 STEP3 STEP4 STEP5 アルゴリズム Point to point matching により候補となるノードを探索候補ノードから候補リンク探索候補ノードから候補経路を作成測位点を結びその線分の距離の和を算出すべての候補経路のうち最も測位点の経路距離と近いものを真の経路とする 20

Curve to Curve map-matching アルゴリズム Point to Point matching に依存 STEP1 STEP2 STEP3 STEP4 STEP5 Point to point matching により候補となるノードを探索候補ノードから候補リンク探索候補ノードから候補経路を作成測位点を結びその線分の距離の和を算出すべての候補経路のうち最も測位点の経路距離と近いものを真の経路とする 22

幾何解析マップマッチング強みシンプル簡単はやい弱みネットワーク形状に依存それまでの点のつながりを考慮しない 23

位相幾何解析マップマッチング STEP1 STEP2 STEP3 アルゴリズム最初の測位点と最も近いノードを探索 ( 初期点 ) 次の点が外れ値 * か否か判定そうでないならばそのノードを通るリンクを探索そうならばこの点を初期点として STEP1 へ重み付けの式を用いて正しいリンクを選択初期点と次の点はこのリンクにマッチングされる STEP5 STEP6 次の点が外れ値か否か判定外れ値ならばこの点を初期点として STEP1 へそうでないならば β < 45 and α 90 を満たすかどうか判定満たすならばこの点を同じリンクにマッチングし式 (?) を用いてそのリンク上の位置を決定するこれを繰り返す満たさないならば STEP1 へ STEP5 をすべての点について繰り返す STEP4 式 (?) を用いてリンク上の移動者の位置を決定外れ値 : 大きく逸脱した観測データ [2] 25

位相幾何解析マップマッチング STEP1 STEP2 STEP3 アルゴリズム最初の測位点と最も近いノードを探索 ( 初期点 ) 次の点が外れ値 * か否か判定そうでないならばそのノー初期点の設定ドを通るリンクを探索そうならばこの点を初期点としてSTEP1へ重み付けの式を用いて正しいリンクを選択初期点と次の点はこのリンクリンクを決定にマッチングされる STEP5 STEP6 次の点が外れ値か否か判定外れ値ならばこの点を初期点としてSTEP1へそうでないならば β < 45 and α 90 を満た現在の点がそのリンクにありすかどうか判定満たすならばこの点を同じ続けるかチェックリンクにマッチングし式 (?) を用いてそのリンク上の位置を決定するこれを繰り返す満たさないならば STEP1へ STEP5 をすべての点について繰り返す STEP4 式 (?) を用いてリンク上の移動者の位置を決定リンク上の位置の決定 26

位相幾何解析マップマッチングリンクの決定 : 進路方向 (heading) を使うリンク 2 鉛直上向きを正とする角度の基準線 β i は基準線とリンク i との角度とするたとえば β 1 = 90 点 1 点 2 点 4 点 3 リンク1 リンク3 点 5 リンク 4 β 点 5 の進行方向定義 β = β β i β = β ( 180 β 180 ) 360 β ( β > 180 ) 360 + β ( β < 180 ) WS H = AHcos( β ) A H は重み付けパラメータ WS H は進行方向とリンク方位角の重み付けスコア差が小さいほど WS H の値は大きくなるそのリンクにマッチングされる可能性が高い 27

位相幾何解析マップマッチングリンクの決定 : 近接性のチェック (1) D 測位点とリンクの距離を D とする WS pd = A p /D WS pd は点とリンクの近接性の重み付けスコア A p は重み付けパラメータ各点の位置座標は既知距離 D が小さいほどスコアは大きくなる測位点がリンクに近いほどスコアは大きくなる 28

位相幾何解析マップマッチングリンクの決定 : 近接性のチェック (2) 測位点と交差点の角度が最も小さいものがより大きな近接性を示すリンク 2 α2 α1 測位点 α4 (= θ) リンク 1 リンク 4 リンク 3 α3 もっとも大きな近接性を示す角度を θ とする ( この場合は α4) WS PI = Apcos(θ) WS PI は測位点と候補リンクの重み付けスコア A p は重み付けパラメータ交差点がない場合は 0 とする θ が小さいほどスコアは大きくなる測位点と交差点の線分がそのリンクに重なりそうほどスコアは大きくなる 29

位相幾何解析マップマッチングリンクの決定 : 近接性のチェック (3) 進行方向を使うリンク 2 α1 α3 α2 測位点 2 測位点 1 α4 リンク 1 リンク 4 リンク 3 αi はリンク i と測位点との相対位置を表す α を測位データと最も近いノードと結んだ線と候補リンクがなす角とする WS RP = ARP cos (α) WS RP は測位点と候補リンクに関する重み付けスコア A RP は重み付けパラメータ 30

位相幾何解析マップマッチング重み付けの総和 :TWS TWS = W SH + (WSPD + WS PI ) + WS RP 進行方向近接性相対位置 WS H : 進行方向とリンク方位角の重み付けスコア WS PD : 点とリンクの近接性の重み付けスコア WS PI : 測位点と候補リンクの重み付けスコア WS RP : 測位点と候補リンクに関する重み付けスコア 31

位相幾何解析マップマッチング重み付けの総和 :TWS TWS = W SH + (WSPD + WS PI ) + WS RP 1 進行方向 3 近接性 2 相対位置進行方向の方が相対位置より重要相対位置の方が近接性より重要 WS H : 進行方向とリンク方位角の重み付けスコア WS PD : 点とリンクの近接性の重み付けスコア WS PI : 測位点と候補リンクの重み付けスコア WS RP : 測位点と候補リンクに関する重み付けスコア 32

位相幾何解析マップマッチング重み付けの総和 :TWS TWS = W SH + (WSPD + WS PI ) + WS RP 1 進行方向 3 近接性 2 相対位置進行方向の方が相対位置より重要相対位置の方が近接性より重要この重要度にもとづいて重み付けパラメータの値を決めていく 33

位相幾何解析マップマッチング重み付けパラメータの決定 WS H A H : 進行方向とリンク方位角の重み付けパラメータ WS PD A p: 点とリンクの近接性の重み付けパラメータ WS PI A p: 測位点と候補リンクの重み付けパラメータ WS RP A RP: 測位点と候補リンクに関する重み付けパラメータ A p はアプリオリに決まる重み付けスコアの重要度によって A H と A RP が決定される A H = aap A RP = bap b > a > 1 a,b が決まったらすべての候補リンクに対して TWS が求まるもっとも高いスコアのリンクを選ぶ 34

位相幾何解析マップマッチング進行方向と速度を用いるリンク上の位置の決定 GPS/DR による位置センサーとデジタルロードマップ上の位置データを用いる 36

位相幾何解析マップマッチングリンク上の位置の決定進行方向と速度を用いる v 1 sinθ リンク1 P t+1 (E i+1, N i+1 ) 速度 v θ P t (E i, N i ) v 1 cosθ リンク 2 P t (E i, N i ) や P t+1 (E i+1, N i+1 ) は STEP3 でどのリンクにのっかるかは決定済み * この場合はリンク 1 を仮定 P t+1 (E i+1, N i+1 ) がリンク 1 のどこにのっかるか P t (E i, N i ) は時刻 t のリンク上の位置 37

位相幾何解析マップマッチングリンク上の位置の決定 GPS/DR による位置センサーとデジタルロードマップ上の位置データを用いる位置センサー P s E s, N s デジタルロードマップ P map (E map, N map ) C p をノード A,B と P s の座標で表現 C p と P map は独立なので P s C p と P map は独立なので推定位置 P(E, N) は位置センサーとデジタルロードマップがもつ誤差分散の式であらわせるノード A P map C p P(E, N) ノード B リンク 38

位相幾何解析マップマッチング現在の点がそのリンクにあり続けるかチェック 2 つの評価基準二つの連続する線の交差角が 45 より大きいかどうか P(x i+2, y i+2 ) 二つの連続する測位点の進行方向角度が 45 より大きいかどうか測位点と最も近いノードを結んだ線とリンクのなす角度 (α) が 90 より大きいか P(x i+1, y i+1 ) P(x i, y i ) 40

さまざまなマップマッチング幾何解析マッチングと位相幾何解析マッチングの例をそれぞれみてきたがそれぞれのアルゴリズムが独立してあるわけではなく組み合わせて使われているたとえば point to curve 位相幾何情報 curve to curve 42

参考文献 [1] Mohammed A., Quddus, Washington Y. Ochieng, Robert B., Noland: Current map-matching algorithms for transport applications: State-of- the art and future research directions, Transportation Research Part C, Vol.15, pp.312-328, 2007 [2] 歩行者 GPS 観測データのオフラインマップマッチングのオフラインマップマッチングオフラインマップマッチングオフラインマップマッチング手法 <http://shiba.iis.u-tokyo.ac.jp/research/poster/pdf/nakamura.pdf> (2015/05/28アクセス) [3] Christopher E. White, David Bernstein, Alain L. Kornhauser, Some map matching algorithms for personal navigation assistants, Transportation Research Part C, Vol.8, pp.91-108, 2000 [4] Mohammed A., Quddus, Lin Zhao, Robert B. Noland, A general map matching algorithm for transport telematics applications, GPS solutions, Vol.7, pp. 157-167 43