可視性に基づくランドマークの自動検出とこれを利用した道案内システム

DEIM Forum 2014 E9-4
可視性に基づくランドマークの自動検出と
これを利用した道案内システム
米倉梨菜†
赤木康宏†
小野
智司†
河合由紀子††
川崎
洋†
† 鹿児島大学大学院理工学研究科情報生体システム工学専攻〒 890-0065 鹿児島市郡元 1 丁目 21-40
†† 京都産業大学大学院先端情報学研究科先端情報学専攻〒 603–8555 京都府京都市北区上賀茂本山
075-705-1408
E-mail: †{sc109077,akagi,ono,kawasaki}@ibe.kagoshima-u.ac.jp, ††kawai@@cc.kyoto-su.ac.jp
あらまし
街を移動する際にスマートフォン等によるナビゲーションシステムを利用する人は多い．しかし，歩行者
や二輪車で移動している人にとっては，移動中に機器の画面で経路を再確認することは危険を伴う行為である．そこ
で，進行方向上に見えるランドマークとなる建物を事前に教示することで，経路の再確認頻度を減らすことのできる
ナビゲーションシステムを提案する．本システムを実現するためにまず，都市の GIS データを 3 次元コンピュータグ
ラフィクスにより仮想的に描画することで，各交差点からの可視性を自動判定する手法を提案する．そして，ランド
マークの可視性が高く，かつ案内に用いるランドマーク数が少数であるような，提案システムに適した経路を発見す
るための経路探索手法を遺伝的アルゴリズムに基づき構築する．実験では，実在する都市の GIS データを用いて本手
法を適用することで，案内経路の妥当性について評価する．
キーワード
ナビゲーション, ランドマーク，可視性，経路探索，遺伝的アルゴリズム
1. はじめに
路を探索することのできる，ランドマークナビゲーションシス
テムを提案する．具体的には，GIS から取得した都市の建造物
ナビゲーションシステムはスマートフォン等の携帯機器上の
の 3 次元形状および道路ネットワーク情報を用いて，各交差点
サービスとして一般化しており，多くの利用者がいる．そして，
から与えられたランドマークへの可視性を記録したデータベー
その携帯性から歩行者や 2 輪車の運転者がこれを利用する機会
スを自動生成する. そして，このデータベースを用いて，ラン
が増えているが，移動中にナビゲーション画面を注視すること
ドマークの可視性を移動のコストに加えた，新たな経路探索手
で周辺への警戒が疎かになり，事故の原因となることが問題と
法を提案する．この経路探索では特に，案内に用いられるラン
なっている．そこで，利用者が端末上で地図情報を再確認する
ドマーク数を最小限に抑えつつも，経路からランドマークが見
ことなく，安全に現在の進路の正しさを確認するための方法と
える割合を最大化するような評価関数を提案する. これにより，
して，音声ガイドによる方法，および記憶しやすい地物（ラン
記憶しやすく，かつ，多くの交差点でランドマークによる経路
ドマーク）を用いる方法が提案されている．前者の方法は，音
案内を受けられる経路の提示が可能になる．提案システムの効
声が聞き取りやすい自動車内での利用に効果を発揮しているが，
果を検証する実験では，実在する都市の GIS データからラン
歩行者および 2 輪車での利用は，周囲の音声情報を遮断するこ
ドマークを決定，およびその可視性を判定し，案内経路を生成
とになり安全性に問題がある．後者の方法は，進路上に見える
することで，経路の妥当性やランドマークの可視率等の評価を
ランドマークを事前に記憶することで，進路の確認行う方法で
行う．
ある．この方法は，古くから人間が訪問者を案内する際に用い
る方法でもあり，たとえば，郵便局やコンビニエンスストア，
2. 関連研究
高層建造物等をランドマークとして利用したものは店舗等の案
本章では，ランドマークを用いたナビゲーションシステムに
内地図等として頻繁に見られる．この方法では，利用者が周辺
関連する研究について述べる．前章でも述べたように，ランド
をよく観察し進路確認を行うので，危険回避も同時に行うこと
マークを用いた案内方法は，土地勘のある人間が訪問者に案内
ができるという利点がある．しかし，利用者はランドマークを
を行う際に用いられてきた．これを，個人の知識によらず，シ
記憶する必要があるので，案内に用いるランドマークの数およ
ステムにより自動化するための方法として，ランドマークの評
び切り替え頻度の少ないような経路を提供する必要がある．つ
価方法，およびランドマークに重点を置いた経路探索手法が
まり，ランドマークを用いた案内方法では，従来の経路の距離
提案されている．中澤らの研究では，より象徴性の高いランド
のみに着目した経路探索手法とは異なる，ランドマークの可視
マークを発見するための調査方法を提案している [11]．藤井ら
性も同時に考慮する経路探索アルゴリズムが必要となる．
の研究では，システムがランドマークの 3 次元形状を提示する
そこで，都市の建造物情報および道路ネットワーク情報等の
ことで，案内を受ける者の経路情報に関する理解を高めること
GIS データに基づき，自動的にランドマークの可視性が高い経
ができると報告しており [9], [10]，視認性の高いランドマーク
を案内に用いることの有用性が示されている．しかし，地理情
Landmark A
報から有効なランドマークを自動的に決定する方法は確立され
Landmark B
ておらず，手作業や経験的知識に基づきランドマークとなる建
造物を決定していることがほとんどである．
一方で，ランドマークの視認性を考慮した経路探索手法も提
案されている [8], [12]．しかし，本手法では，経路探索の際にあ
るランドマークに対する連続的な視認性を考慮するとともに，
複数のランドマークを切り替えながら目的地を目指すアプロー
チを取るが，そのような手法は過去に提案されてない．中澤ら
の研究では，ランドマークとして用いる店舗等の昼夜による外
観の違いにも配慮し，案内を行う際の時刻により利用するラン
ドマークを切り替える工夫を行っている [8]．また，宇戸らの研
究では，ランドマークとなる建物が継続して見えることが，歩
図 1 ランドマークの可視判定
行者の安心につながるという報告 [12] がある．これらの先行研
究では最短経路の探索を行う際に，数百の交差点からなる小規
模な道路ネットワークの情報に対して，Dijkstra 法 [2] による
経路探索を実施している．Dijkstra 法はノード間に距離のみが
与えられている経路の探索アルゴリズムとして非常に有用であ
るものの，経路が逐次的に決定していくので，経路全体におい
て案内に用いるランドマーク数を最小化することが難しいとい
う問題がある．よって，数万のノードから構成される実用的な
規模の道路ネットワーク上で，ランドマークの視認性を考慮し
た経路探索を行うためには，新たな工夫が必要となる．他に，
視認性を考慮した経路探索手法として，河野ら [7] が景観の可
視性を考慮した経路探索システムを提案している．これは，経
路からの景観の可視性を計測し，同じ景観 (例えば富士山等) が
連続的に見える経路のランク付けを行うことで，経路を決定す
るというものである．先述した中澤ら [8] の手法では，天候や
時刻などの要因により変化するランドマークの視認性を扱った
経路探索を行っているが，同じランドマークに関してどの程度
見え続けるかという連続性は考慮されていない．そこで，本研
究ではランドマークの可視マップを生成し，少数のランドマー
クが連続的に見える経路を探索する手法を提案する．
3. 提案システムの概要
3. 2 ランドマーク可視性マップに基づく経路探索
次に，同一のランドマークが長期間見え続ける経路を選択す
るための，ランドマークの可視性を移動コストとして評価す
る，最短経路探索アルゴリズムを提案する (図 2)．ここで扱う
経路探索問題が，通常の距離のみを評価値とする場合と異なる
点は，ランドマークの可視性という情報は，単純な２つのノー
ド間の距離として表現することが難しく，かつ，生成される経
路全体のランドマーク数を少なくするというような，局所的な
評価ではなく，生成された経路全体に対する評価を結果に反映
させる必要がある．この問題を，Dijkstra 法により解こうとす
る場合では，探索中に探索範囲を絞る「枝刈り」が発生しにく
く，探索時間が増大するという問題が生じる．そこで，経路全
体に渡るコスト評価に適した，遺伝的アルゴリズム（GA）[5]
を用いた経路探索を行う．GA では，まず初めに始点から終点
までの仮経路を生成し，これを改善するアプローチを取ること
ができる．よって，GA は本研究で扱うような，経路全体を最
適化する問題に適している．本手法の詳細については，4.2 節
で述べる．
Shortest route search
Landmark route search
本稿で提案するランドマークナビゲーションシステムは，ラ
ンドマーク可視性マップの生成，および，可視性マップに基づ
く経路探索の 2 種類の処理から構成される．
3. 1 ランドマーク可視性マップの生成
Start
まず，ランドマーク可視性マップの生成手法について述べる．
本稿では，高さの高い建物がランドマークとして適していると
考え [10]，都市を約 1km 四方のブロックに分割し，各ブロック
Goal
内の建物のうち高い順に N 個の建物をランドマークとして選
択する (N は都市規模に応じて決定する)．可視性マップの生成
処理では，都市を構成する全ての建物を 3 次元コンピュータグ
図 2 最短経路探索とランドマークを用いた経路探索の違い
ラフィクスにより描画し，全ての交差点からの風景をレンダリ
ングすることで可視判定を行う (図 1)．以上の処理により，各
交差点から各ランドマークが見えるのかどうかを記録した，ラ
ンドマーク可視性マップを生成する．本手法の詳細については，
4.1 節で述べる．
以上の 2 手法を組み合わせることで，ランドマークの可視性
を考慮したナビゲーションシステムを実現する．
4. ランドマークナビゲーションシステムの詳細
本章では，ランドマーク可視性マップの自動生成および，GA
に基づくランドマークの可視性を考慮した経路探索について詳
しく説明する．
4. 1 ランドマーク可視性マップの自動生成
提案システムでは，利用者が各交差点において，直進すべき
なのか，進路を変更すべきなのかを判断すると想定し，各交差
点におけるランドマークの可視性を案内地図と共に提示する．
これを実現するためには，(1) ランドマークとなる建物群を決
定する，および，(2) 全ての交差点からのランドマーク群の可
視性をデータベース化する必要がある．本研究では実用的なシ
ステムを想定し，これらの情報を GIS データから自動生成する
手法を提案する．
4. 1. 1 都市の描画
図 4 都市のブロック分割例
建物情報を 3 次元コンピュータグラフィックスにより描画す
ることで，任意の交差点位置から，任意の建物の可視性が判別
できる．建物・道路・地形等のデータは，3 次元 GIS で用いら
れる電子地図（DEM や Google Earth の建物データなど）から
入手可能である．描画するオブジェクトは以下の 2 種類である．
•
建物データの描画
提案システムでは建物の可視性のみが重要であるので，個々の
建物を 3DCG により描画する際には建物の Bounding Box の
象となる都市の矩形領域を 1km 四方のブロックに分割する (図
4)．そして，各ブロック内に含まれる建物のうち，高い順に上
位 n 件の建物をランドマークとして選択する (図 5)．各ブロッ
クからランドマークを選ぶ理由は，市街地の中心部等に偏って
ランドマークが選択されてしまわないようにするためである．
n は，作成する都市の状態に応じて，適切な数値を設定する．
みを描画することで処理の高速化を図る．
•
地形データの描画
建物の可視判定を行う際には，高低差により下側から建物が見
えてしまうことを避けるために，地形データも併せて描画する
必要がある (図 3)．
また，道路に関してはその形状を描画する必要はないが，実
験結果などを示す際には，読者の理解のために図中には表示し
ている．
4. 1. 2 ランドマークの決定方法
図5
ランドマークとなる建物の自動選択
4. 1. 3 ランドマーク可視性マップの生成処理
ランドマークの決定後，ランドマーク可視性マップを生成す
るための処理を行う．ランドマーク可視性マップを生成する際
には，全ての交差点から全周を見渡した 3DCG をレンダリン
グし，そのレンダリング画像に含まれているランドマークを発
見する．この処理のために，前節で述べた手法により決定した
各ランドマークに固有の番号を割り振り，各番号に対応する個
別の色を用いて全ランドマークをレンダリングし，それ以外
の建物をおよび背景を単色でレンダリングする．このレンダ
図 3 GIS データからの都市景観の描画（サンフランシスコ市）
リング画像中に含まれる画素値を調べることで，ある交差点
から見えるランドマークの番号検出できる．またこの時，人間
次に，ランドマークの決定方法について説明する．まず，対
の視力を考慮し，レンダリング画像を描画する際の解像度を
100 × 100pixel とすることで，視認できる領域の小さすぎるラ
ンドマークは，画面に描画されないようにする. 視点を変えた
ときのレンダリング結果の様子を図 6 と図 7 に示す．
d
goal
start
d
図8
経路探索範囲の縮小
図 7 レンダリング結果その 2
図 6 レンダリング結果その 1
4. 2. 3 ランドマークの可視性に基づく評価関数
4. 2 GA に基づくランドマークの可視性を考慮した経路
探索
次に，方法 2 による評価関数の計算方法について述べる．経
路 T 上で連続する地点 Tp ，Tp+1 の間に共有するランドマーク
道路ネットワークの情報から，目的地に向かう経路探索を行
があった場合，2 地点間の距離 Dist(Tp , Tp+1 ) を減じる処理を
う場合，Dijkstra 法や A*アルゴリズム [4] を用いた方法が広く
行えば，ランドマークが視認できる経路を利用する際の移動コ
用いられている [8], [12]．Dijkstra 法は，最短経路探索を行う
ストが下がるので，ランドマークの視認性を優先した経路が得
有効な方法ではあるが，提案システムではランドマークの可視
性という，多次元かつ経路全体を考慮する必要のある情報を必
要としているので，局所的なコストの蓄積のみで経路を評価す
られる．さらに，共有するランドマークが Tp+1 , Tp+2 , · · · と連
続する経路は，利用者にとって記憶しやすく有用であることか
ら，共有ランドマークの連続性に応じて移動コストを減じる処
る Dijkstra 法や A*アルゴリズムを直接適用することは難しい．
理を行うことで，本研究で目標とする経路を得ることが出来る．
そこで，遺伝的アルゴリズム（GA）に基づく経路探索を行う．
ただし，この処理を実現するためには，以下の問題を解決す
GA による経路探索には，Chang Wook らの提案した手法 [1]
に基づき，ランドマークの可視性を考慮した評価関数の追加を
行う．
る必要がある．その問題は，地点 Tp と Tp+1 の間にある共有ラ
ンドマークは複数存在しているが，記憶しやすい経路にするた
めに，そのうち１つだけを案内に用いようとすると，連続数が
4. 2. 1 経路探索範囲の縮小
最大となるランドマークの組を見つける処理が必要となる (図
実用的な規模の道路ネットワーク情報は膨大であり，出発地
と目的地の位置に応じて，経路探索の範囲をあらかじめ絞り込
む方法が一般的に用いられている. 特に，本研究で用いる GA
による経路探索では，経路情報の突然変異による変更を，ある
程度の範囲に限定することで，探索効率が上がるという特徴が
あり，探索範囲の絞込みが有効に働く.
9)．この処理自身もまた一種の経路探索問題であり，全体とし
て階層的な経路探索問題を構成してしまう．
本研究では，この問題を解決するために，次に説明する方法
によりランドマークを選択する方法（方法 2），および Belief
Propagation（BP) [3] を用いてランドマークの選択をを最適化
する方法（方法 3）を提案する．
そこで，出発地と目的地を結ぶ線分から距離 d 以内にある交
差点のみを経路探索に用いる (図 8). 本研究では，出発地と目
的地を結ぶ線分の長さを Length としたとき，d = Length/4
と定めた.
まず，都市全体の M 個のランドマークを L
=
{L0 , · · · , Lq , · · · , LM } と表し，経路 Tp 上での各ランドマー
クの出現頻度 H(Lq ) を求める．その準備として，地点 Tp から
ランドマーク Lq への可視性 V (Tp , Lq ) を式 (2) で表す．
4. 2. 2 経路探索に用いる経路の評価関数
経路探索では，交差点をノードとし，ノード間の距離を移動
コストとして，これを合計する評価関数を導入する．評価関数

1
V (Tp , Lq ) =
0
if Lq is visible from Tp ,
(2)
if Lq is NOT visible from Tp .
には，距離のみを考慮した従来の最短経路探索法（方法 1），お
よびランドマークの可視性を考慮した提案手法（方法 2・方法
そして，出現頻度 H(Lq ) は式 (3) で計算する．
3）の 3 種類の関数を用意する．なお，以降は探索により発見
された，地点 i から地点 j に移動するための N 地点の経由地
点リストを T = {i, · · · , Tp , · · · , j} と表現する．また，隣接す
る 2 つの地点 s,t 間の距離を Dist(s, t) と表現する．方法 1 に
N
−1
∑
p=0
N : 経由点数
N
∑
V (Tp , Lq )
(3)
p=0
この出現頻度 H(Lq ) を用いて，地点 Tp と Tp+1 の間に共
有ランドマークが複数あった場合は，その中で最も H(Lq ) の
基づく，経路 T の評価関数 C(T ) は式 (1) である．
C1 (T ) =
H(Lq ) =
大きいランドマークをその経路を案内する際に用いるランド
Dist(Tp , Tp+1 )
(1)
マークとして採用する (図 9)．ここまでの処理により得られ
た，経路 T における案内に使用するランドマークのリストを
LL = {La , · · · , Lz } とする．そして，この LL 上でランドマー
(i )
D
C
B
A
5. 実
C
B
(ii )
D
C
T1p +1
T0p
S
(
E
D
T2p + 2
本章では，提案手法により実際にランドマークの可視性を考
E
T3p +3
慮した経路探索を行い，探索された経路上でのランドマークの
使用数および視認可能な地点の割合などを評価する.
T4p + 4
提案システムが実用的な規模の都市 GIS データに対して適
用可能であることを示すために，San Francisco Data が公表
(iii )
p)
験
しているサンフランシスコ市の GIS データ [6] を用いてランド
図 9 ランドマークの選出
(i) 緑色のアルファベット：Tp から見える全てのランドマーク．
(ii) 赤色の枠：案内に用いる出現頻度の大きいランドマーク．
マーク可視性マップの作成を行った．本 GIS データには，都市
にあるほぼ全ての建物および道路ネットワークの情報が含まれ
ている．具体的には，85116 件の建物の 3 次元形状情報，およ
(iii)p 番目の地点からのランドマークの連続数 S(p)．
び 12188 件の道路情報から構成されている．また，ランドマー
D
C
B
A
v
クの決定方法において，実験で使用するサンフランシスコ市の
Belief Propagation
e
C
B
v
D
C
e
v
2
1
0
e
E
D
v
データでは高い順に上位 n = 10 件の建物をランドマークとし
て選択した．
e
3
E
経路探索は第 4.2 節で説明した 3 種類の評価方法により行う.
v
実験にあたり, 始点と終点の組みを 5 通り用意し, それぞれを経
4
路 A, 経路 B, 経路 C, 経路 D, 経路 E とする．実験に用いた経
図 10 BP アルゴリズムを使用したランドマークの選出
路探索のための交差点数は, 第 4.2.3 節に示した方法により, そ
れぞれの実験経路において決定している．
クの連続数を数え，p 番目の地点からのランドマークの連続数
5. 1 可視性の評価
を S(p) と表す．
可視判定中のレンダリング画像の例を図 11 と図 13 に示す．
方法 2 で移動コストを求める際には，経路 T 上の p 番
赤色で描かれているものがランドマークを表している．緑色部
目の地点から始まる，ランドマークの連続するサブ経路
分は地面を表している．確認のために，図 11 と図 13 のレンダ
tp = {Tp , Tp+1 , · · · , Tp+S(p) } の道のり C1 (tp ) 対して，次式
リング画像と，同様の視点から見た際の Google Street View
で与える重み係数 w(p) を乗じる．
の表示を図 12 と図 14 に示す. この結果から，都市の描画が正
S(p)
W1 (p) = w0
, 0 < w0 <
= 1.0
(4)
しく行われており，実態に即した可視性判定が行えることが確
認できた．
w0 は連続数あたりの距離の減少率であり，次章において実験
的に定める．この重み係数 W1 (p) は，ランドマークの連続数に
応じて値が小さくなるので，同一のランドマークが長期間見え
続ける経路ほど，その経路の移動コストが減少する．
最終的に，方法 2 で利用する評価関数 C2 (T ) は式 (5) となる．
∑
p+=S(p),p<N
C2 (T ) =
W1 (p)C1 (tp )
(5)
p=0
図 11
可視判定の様子その 1
図 12 Google Street View その 1
図 13
可視判定の様子その 2
図 14 Google Street View その 2
また，方法 3 では, ランドマークの選択候補をデータ項，経
路上の隣接ノードで案内に用いるランドマークの連続性を正規
化項として，BP を使用する．
BP アルゴリズムにより，例として，図 10 の赤い枠で囲んだ
ものが経路に扱われるランドマークとして選出される．このと
き，各データ項を Dv ，隣接ノードの正規化項を Re とし，隣
接ノードの正規化項の重み係数を λ とする．
また，経路の物理的な距離の重みを W2 (p) として付加し，方
法 3 で利用する評価関数 C3 (T ) は式 (6) となる．
C3 (T ) =
∑
v ∈ V
Dv + λ
∑
e∈ E
Re + W2 (p)C1 (tp )
(6)
図 18
図 15 方法 1・経路 A における探索結果
方法 1・経路 B における探索結果
内に用いられているランドマークの種類の数であり，可視率は，
ランドマークが見えている交差点数を経路全体の交差点の総数
で割ったものである. この結果から，提案手法では全ての重み
係数においてランドマークの可視率が向上しており，本研究で
目的とするランドマークを利用したナビゲーションに適した経
路が選択されていることが分かる.
また表 1 で示したランドマークの可視率，および選択された
経路の距離のバランスを考慮し，経路探索に用いる方法 2 の重
み係数は w0 = 0.6 と定めた. w0 = 0.6 とした際の経路を図 16
および図 19 に示す. 経路 A における結果（図 16，図 17）で
は，従来手法（図 15）に比べ，案内に用いられるランドマーク
図 16 方法 2・経路 A における探索結果
の切り替え頻度（経路上の色が変化する点）が減少しており，
覚えやすい経路となっている.
経路 B における結果（図 19）では，従来手法（図 18）に比
べ，同じ赤色のランドマークを案内に用いているにもかかわら
ず，可視率が大幅に向上していることが分かる.
その一方で，経路 B に見られるような，付近に最短経路があ
るにもかかわらず，遠回りをするような結果となる箇所がある．
これは，提案手法では距離とランドマークの可視性という関連
性のない情報を同時に最適化しているので，収束性が低下する
理由から，実用的な時間で経路探索を完了させるために，収束
のための条件を緩和していることが原因にある．この問題を解
決するためには，解法そのものの高速化が有効である．
図 17 方法 3・経路 A における探索結果
方法 3 では，経路 A や経路 B のように大幅に可視率が向上
しているものの，経路が長くなりすぎてしまう傾向にある．し
5. 2 経路探索
まず，経路 A および経路 B において，従来の距離のみをコ
ストとして評価した場合の探索結果を提案手法との比較のため
に求める (図 15，図 18). 結果に用いる図中にある色付きの建
物は案内に用いるランドマークを表し，経路の色は，その経路
から見えるランドマークの色と対応している．黒色の経路は，
ランドマークが見えていない経路である．これに対して，提案
かし，1 ランドマーク当たりの可視ノード数を見ても，方法 1
に比べ，向上しているものが多い．
以上の結果から，本研究で提案する，ランドマークの高い可
視性および連続性を考慮した経路探索手法により，ランドマー
クナビゲーションに適した経路を生成することができたとい
える.
6. おわりに
手法である方法 2 による経路探索を行い比較する. その際に，
提案手法ではランドマークが可視であった場合の重みパラメー
タ w0 を用いているので，複数の w0 について実験を行い，最
適な値を決定する. 実験結果を，経路ごとに表 1 に示す．
表 1 の可視ランドマークの総数は，探索された経路全体で案
本研究では，移動経路上から見えるランドマークを利用する，
歩行者や 2 輪車向けの新たなナビゲーションシステムを実現す
るための，ランドマークの可視性マップ生成手法，およびラン
ドマークの可視性を考慮した経路探索手法を提案した．提案手
表1
経路
A
B
図 19
方法 2・経路 B における探索結果
C
D
E
図 20
方法 3・経路 B における探索結果
法を用いることで，最短経路探索で求めた経路に比べ，ランド
方法
(重み w0 )
経路結果
案内用
ランドマーク実際の距離
の数
[ マイル ]
交差点
ノード数可視率 [%]
方法 1
2
3.0
15
46.7
方法 2(0.2)
7
3.5
27
81.5
方法 2(0.4)
6
3.8
32
93.8
方法 2(0.6)
4
3.9
36
86.1
方法 2(0.8)
5
4.0
32
84.4
方法 3
3
3.4
26
84.6
方法 1
3
2.5
18
38.9
方法 2(0.2)
6
3.6
47
87.2
方法 2(0.4)
4
3.4
39
82.1
方法 2(0.6)
4
3.5
26
88.5
方法 2(0.8)
6
2.5
26
73.1
方法 3
10
2.5
81
52.2
方法 1
1
3.9
14
34.1
方法 2(0.2)
6
5.0
41
71.9
方法 2(0.4)
7
6.0
47
67.1
方法 2(0.6)
4
3.9
18
43.9
方法 2(0.8)
6
4.1
20
41.7
方法 3
4
4.3
24
91.7
方法 1
3
2.3
26
26.9
方法 2(0.2)
6
3.3
28
57.1
方法 2(0.4)
5
3.2
28
53.6
方法 2(0.6)
6
2.8
33
42.4
方法 2(0.8)
5
3.3
25
32.0
方法 3
8
4.5
45
61.5
方法 1
3
2.4
31
41.9
方法 2(0.2)
6
4.1
40
85.0
方法 2(0.4)
6
3.7
39
84.6
方法 2(0.6)
6
3.7
39
76.9
方法 2(0.8)
6
3.2
36
80.6
方法 3
7
8.2
87
57.0
マークの可視率が高く，経路長の増加を最小限に抑えた案内経
路を求めることが可能となった．さらに，案内に利用するラン
ドマーク数を低減させるための評価関数を導入することで，ラ
ンドマークを用いた案内において，ユーザに負担をかけない経
路を選択することが可能となった．
今後の課題として，ランドマークの定義をユーザによって変
更することを考慮している．歩行者と二輪車使用者では，移動
スピードが異なるため，それぞれの使いやすさを考慮したラン
ドマークの定義が必要である．今回は建物の高さ情報のみを
扱ったが，建物の色やコンビニエンスストア，ガソリンスタン
ドなど，幅広い情報をランドマークとして扱うことを予定して
いる．また，経路探索においては遺伝的アルゴリズムを使用し
た．より少ないランドマークで連続的に見える，効率的なコス
ト関数を決定することも今後の課題の 1 つである．
7. 謝
辞
本研究の一部は，内閣府最先端研究 (LR030)，文科省科研費
(25870570) および総務省 SCOPE（ICT イノべーション創出
型研究開発）の助成を受けて実施された．
文
献
[1] Chang Wook Ahn and R. S. Ramakrishna. A genetic algorithm for shortest path routing problem and the sizing
of populations. In IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 6, NO. 6, 2002.
[2] E. W. Dijkstra. A note on two problems in connexion with
graphs. NUMERISCHE MATHEMATIK, Vol. 1, No. 1, pp.
269–271, 1959.
[3] P. Felzenszwalb and D. Huttenlocher. Eﬃcient belief propagation for early vision. IJCV, Vol. 70, pp. 41–54, 2006.
[4] P.E. Hart, N.J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths.
Systems Science and Cybernetics, IEEE Transactions on,
Vol. 4, No. 2, pp. 100–107, 1968.
[5] John H. Holland. Adaptation in Natural and Artificial Systems. MIT Press, Cambridge, MA, USA, 1992.
[6] SFGOV. San Francisco Data, 2014. https://data.sfgov.org/.
[7] 河野亜希, 谷村孟紀, 崔楊, 河合由起子, 川崎洋. 景観の可視性
を考慮したルート探索システムの提案. 情報科学技術レターズ,
Vol. 6, No. LK-005, pp. 351–354, 2007.
[8] 中澤啓介, 岡田謙一. ランドマークの視認性に基づいた動的な案
内地図作成. 情報処理学会論文誌 Vol.48 No.1, 2008.
[9] 藤井憲作, 東正造, 荒川賢一. 携帯端末向け案内地図生成システ
ムの開発. 情報処理学会論文誌. Vol.41, No.9, pp.2394-2403,
2000.
[10] 藤井憲作, 東正造, 荒川賢一. 経路案内情報がナビゲーションに
及ぼす影響. 電子情報通信学会論文誌. A, 基礎・境界 J87-A(1),
40-49, 2004-01-01, 2004.
[11] 中澤優一郎, 山本隆徳, 細川宜秀. 象徴性と相対的場所性に基づ
く強いランドマーク検索システムの実現方式. In DEIM Forum
2012 B2-4, 2012.
[12] 宇戸裕人, 古川宏. ランドマークの定量的評価に基づく歩行者の
不安を軽減する経路探索アルゴリズム (自動車運転/位置情報/通
信技術). シンポジウムモバイル研究論文集 2010, 27-32, 2010.

Download Report