情報処理学会 インタラクション 2015
IPSJ Interaction 2015

15INT001
2015/3/5

点と線と面のランドマークによる
道路地図に頼らないナビゲーション・システム
米倉 梨菜1,a)

森永 寛紀1,b)
若宮 翔子2,c)
赤木 康宏3,d)
河合 由起子2,f)
川崎 洋1,g)

小野 智司1,e)

概要：見知らぬ街で移動する際，スマートフォン等によるルート・ナビゲーション・システムを利用する
ユーザは多い．しかし，移動中に小さな画面で経路を確認することは危険を伴う．このため，人が記憶しやすく視認性の高いランドマークを用いたナビゲーション・システムが提案されてきた．それらシステム
で用いられてきたランドマークは主に，1) 郵便局やコンビニエンス・ストアのような，近くまでいかないと視認できないが，確認することでユーザの現在位置を高い精度で同定できるものか，2) 電波塔や高層ビ
ルなど，遠方からでも視認できるが，現在位置をおおまかにしか同定できないもの，の 2 種類であった．
本論文では，これらランドマークを，その視認可能な範囲や位置同定能力から，それぞれ，1) 点および，

2) 面のランドマークと区別して呼ぶ．これら，点と面のランドマークは，その性質の違いから，同時に使用することが難しく，これまでのシステムでは，いずれか一方のみを用いていた．そこで，我々は，3) 電
車通りや河川のように，すぐ近くまで行かないと視認できないが，その範囲が線状に広がりを持つものを新たに，3) 線のランドマークとして定義し，これを用いて従来難しかった，複数種類のランドマークを同時に利用可能なシステムを提案する．本システムを用いれば，少ない数のランドマークを利用して目的地に到達することができるため，スマートフォンなどで地図を確認する回数を減らすことができる．

Navigation System without Explicit Route Presentation
using Point, Line and Area based Landmarks
Yonekura Rina1,a) Morinaga Hiroki1,b) Wakamiya Syoko2,c) Akagi Yasuhiro3,d)Ono Satoshi1,e) Kawai Yukiko2,f) Kawasaki Hiroshi1,g)

Abstract: Recently, the number of people who use navigation systems with handy devices, such as smart
phones on the streets, is rapidly increasing. As the increase of the number of the user of the systems, concerns on safety is arisen because it makes people to reconfirm the route frequently by the small windows on
devise and it is dangerous. Therefore, the navigation systems using highly visible and recognizable landmarks
have been proposed. The landmarks mainly used for the systems are 1)the buildings which can help users
identify own location accurately but not be recognized from far, such as post oﬃces, convenience stores, 2)High buildings which are highly visible from a long distance but give users only rough information, such asradio transmitter towers, high-rise buildings, etc.In this paper, we categorize landmarks according to theirproperties as follows, ”point landmarks” for the above 1), ”area landmarks” for the above 2) and ”linear
landmarks” which are not visible from far but users can easily follow along, such as streets and rivers. Thenour propsed system can utilize several types of landmarks at the same time, which was diﬃcult by otherconventional methods. By our navigation system, users can reach the destination using a small number oflandmarks, which means users need to check screens less than other systems.

12

鹿児島大学大学院 理工学研究科 情報生体システム工学専攻,
Department of information Science and Biomedical Engineering,Kagoshima University
京都産業大学大学院 先端情報学研究科 先端情報学専攻,
College of Science and Technology, Royal Kyoto Sangyo Uni-

© 2015 Information Processing Society of Japan

3

a)
b)
c)

versity
東京農工大学大学院 工学府 機械システム工学専攻,
Tokyo University of Agriculture and Technology
sc109077@ibe.kagoshima-u.ac.jp
sc110080@ibe.kagoshima-u.ac.jp
shokow@cc.kyoto-su.ac.jp

11. はじめに㕙䈱䊤䊮䊄䊙䊷䉪
㕙䈱䊤䊮䊄䊙䊷䉪
䈱นⷞ䉣䊥䉝

ナビゲーション・システムはスマートフォン等の携帯機
器上のサービスとして一般化しており，多くの利用者がいる．さらに，その携帯性から車の運転者だけでなく，歩行者や 2 輪車の運転者がこれを利用する機会が増えている
が，移動中にナビゲーション画面を注視することで周辺への警戒が疎かになり，事故の原因となることが問題となっている．そこで，利用者が端末上から確認可能な地図情報✢䈱䊤䊮䊄䊙䊷䉪

を参照することなく，安全に現在の進路の正しさを確認するための方法として，音声ガイドによる方法や，記憶しやすい地物（ランドマーク）を用いる方法が提案されている．
前者の方法は，音声が聞き取りやすい自動車内等での利用に効果を発揮するが，歩行者および 2 輪車での利用は，周囲の音声情報を遮断することになり安全性に問題があὐ䈱䊤䊮䊄䊙䊷䉪

る．後者の方法は，記憶しやすく視認性の高い地物をラン
図 1

ドマークとして記憶することで，経路案内を行う方法であ3 種類のランドマーク

り，太古より人が地図を使わずに道案内をする際に用いられてきた．現在でも，郵便局やコンビニエンスストア，神ている途中で，スカイツリーが見えたらそちらに進む」と社等をランドマークとして利用したものが店舗等の案内地

いった案内しかできないため，使用するランドマークをい図として頻繁に見うけられる．この方法では，利用者は基つ切り替えるのかをユーザが判断する必要があり，実用上本的には地図を見る必要が無く，さらに周辺を観察しながの問題がある．

ら進路確認を行うので，危険回避にも役立つ．しかし，利このような問題に対して，我々は，3) 電車通りや河川と用者はランドマークを記憶する必要があるため，その数をいった，すぐ近くまで行かないと視認できないが，その範できるだけ減らす必要がある．そこで，本論文では，ラン囲が線状に広がりを持つものを新たに，3) 線のランドマー

ドマークを用いる経路案内において，少ないランドマーク

クとして定義し，これを用いることで，上記問題を解消すで効率よくこれを実現する手法を提案する．

る．点と線と面のランドマークを図 1 に示す．線のランド

従来のランドマークを用いたナビゲーション・システム

マークを導入すれば，例えばユーザが，面のランドマーク

で用いられてきたランドマークとしては主に，1) 郵便局やである，東京タワーを目指すためにどの経路を選択したとコンビニエンス・ストアのような，近くまでいかないと視しても，スタート地点と東京タワーを横切る線のランド

認できないが，確認することでユーザの現在位置を高い精マークである「山手線の線路」にぶつかったら左に曲がる，度で同定できるものか，2) 電波塔や高層ビルなどのようと案内しておけば，ユーザは見失うことなくランドマークに，遠方からでも視認できるが，現在位置をおおまかにしを切り替えられる．線のランドマークとしては，国道など

か同定できないもの，の 2 種類であった．本論文では，この大通りや，並木道と言った幅は狭いが視認性の高い道路

れらランドマークを，その視認可能な範囲や位置同定能力も含められる．また，以降の説明では直感的に理解しやすから，それぞれ，1) 点 (局所的)，および，2) 面 (広域) のいように，点と面のランドマークのことをそれぞれ，局所

ランドマークと呼ぶ．これら，点と面のランドマークは，的ランドマーク，および広域ランドマークとも記述する．

その性質の違いから，同時に使用することが難しい．例え

具体的なシステム構築では，点と線のランドマークに関ば，「東京タワーに向かって直進する」という面のランド

しては，Google API や GIS データから情報を取得できる．

マークを用いた経路案内があった場合，ユーザが選択可能

さらに，ツイッターなど SNS の発信位置を地図上にプロッなルートは複数あるため，続く案内で，「途中でコンビニトし，その頻度が高いルートも線のランドマークとして利エンスストアにぶつかったら左に曲がる」，と言った点の用できる．面のランドマークに関しては，視認性の高い高ランドマークを用いた経路案内ができない．また，面のラ層構造物を利用できる．経路探索に際しては，実際の道路

ンドマークのみを用いる場合でも，「東京タワーに向かっネットワークとは独立した，点と線と面のランドマークを用いた新たな経路グラフを生成し計算する．これにより，

d)
e)
f)
g)

akagi-y@cc.tuat.ac.jp
ono@ibe.kagoshima-u.ac.jp
kawai@cc.kyoto-su.ac.jp
kawasaki@ibe.kagoshima-u.ac.jp© 2015 Information Processing Society of Japan

もとの道路ネットワークを用いた場合よりも大幅に探索時間を短縮できる．また，経路長を短くしながら，利用する
ランドマーク数を減らし，かつ可視率の高いランドマーク

2

を選択するといった複数の目的を満たすため，通常の経路
探索エンジンを用いることが難しいことから，本論文では，
遺伝アルゴリズム (GA) を用いて計算した．
提案システムの効果を検証するため，実在する都市の

GIS データからランドマークを決定し，提案手法の経路と既存の道路ネットワークを使用した最短経路を比較してアルゴリズムの妥当性を評価する実験を行った．さらに，被験者に実際に経路を辿ってもらう実験を行い，所要時間や地図の参照回数等の評価を行った．その結果，提案手法により，少ない地図の参照回数で目的地に到達可能な道案内を作成できることが確認できた．

2. 関連研究
ランドマークを定義・発見するための手法がこれまで提案されてきた．中澤らの研究では，より象徴性の高いラン
ドマークを発見するための調査方法を提案している [13]．

図 2

᭱▷⤒㊰

経路グラフの生成ᥦ᱌ᡭἲ

藤井らの研究では，システムがランドマークの 3 次元形状を提示することで，案内を受ける者の経路情報に関する理解を高めることができると報告しており [10], [11]，視認性の高いランドマークを案内に用いることの有用性が示されている．しかし，ランドマークを，その視認範囲や位置同定能力から区別した例はなく，その特性を利用した経路案
内手法も提案されていない．
局所的（点の）ランドマークを用いた経路案内システム
は数多く提案され，車載ナビゲーション・システムには多く導入されている．しかし，音声の補助がなければ何度も

図 3 最短経路探索とランドマークを用いた経路探索の違い

画面を見直すことになり，危険を伴う．Drager らは，スマートフォンに，ランドマーク画像を表示しながら，その覚えやすい経路を案内し，ユーザが携帯端末を確認する回

画像と実際のシーンとをユーザが比較・確認しながら目的数を減らすことに成功している．しかし，ランドマークの地にたどり着くためのシステムを提案している [3]．しか切り替え方法が考慮がされないという，実用上の問題があし，これも常に携帯端末を見直す必要がある．

る．他にも，視認性を考慮した経路探索手法として，河野

一方で，広域（面の）ランドマークにのみ注目した手法

らが景観の可視性を考慮した経路探索システムを提案しても数多く提案されている．例えば，中澤らの研究では，ラいる [8]．同様の考え方による経路案内をクラウド・ソーシ

ンドマークとして用いる店舗等の昼夜による外観の違いにングで実現した例も提案されている [5].

も配慮し，案内を行う際の時刻により利用するランドマー
クを切り替える工夫を行っている [9]．また，多賀らは，広3. 提案システムの概要

域ランドマークによる経路案内において問題となる，ラン本論文で生成する経路案内方法の概要について，図 2 をドマークの切り替えを，携帯端末の GPS 機能を用いて音用いて説明する．まずシステムは，点・線・面のランドマーを出して知らせることで解消する手法を提案している [12]．

クを抽出しておく．桃色の小円はスタート (左上) とゴー

しかし，GPS 付きの携帯端末といったデバイスが必要なこル (中央下) を，黄色の小円は局所的（点の）ランドマークとと，音が聞き取りにくい環境では使用しにくいという課を，赤色の折れ線は線のランドマークを，紫と緑の建物は題がある．また，宇戸らの研究では，ランドマークとなる

広域（面の）ランドマークを，大円は広域ランドマークの建物が継続して見えることが，歩行者の安心につながると可視領域を表している．この可視領域は，あらかじめ道路

いう報告がある [14]．これに基づき，広域ランドマークのネットワークと 3 次元地図情報を用いて計算しておく．

視認性が連続するよう考慮しながら，経路案内に必要なラユーザは最初に，スタートから紫色の建物を目指して進ンドマーク数を少なくすることを目指した研究が行われてむことにより，1 つ目の大通りにぶつかる．その大通りでいる [6], [15]．このシステムでは，ランドマークの可視率

右に曲がり，大通り上にあるコンビニを目指して進み，ぶが高く，かつ案内に使用するランドマークを減らすことで，つかったらそこで緑色の建物に向かって進み始める．する© 2015 Information Processing Society of Japan3

表 1 ランドマークの定義
幾何的
意味的
点
線
面

郵便局，コンビニ，

人気のカフェ，ガソリンスタンド

待ち合わせスポット

大通り，電車通り，その土地で有名なめ，幾何的ランドマークと意味的ランドマークの両方が含まれていると言える．

4.1.2 線のランドマーク
線のランドマークは，電車や河川，高速道路や海岸沿い

河川沿いの道路

店舗が並ぶ通りの道路などのいわゆる”大通り”を指す．経路案内では，線電波塔や高層ビルなど

寺社など，地域内で存在のランドマークに一度ぶつかれば，その後はその通りに可視範囲の広い建築物

位置が容易に分かるもの

沿って進むことになるため，道に迷いにくいというメリットがある．これら大通りの情報に関しても，GIS データかと，別の大通りにぶつかるため，そこで右に曲がり，通り

ら取得可能である．本論文では，河川や電車通り沿いの道沿いに進むと目的地に到達する．このような経路は，最短路や，GoogleMap で太く表示される道路等を線のランド

経路 (図 3 左) と比べて，経路長は長くなるが，迷いにくマークとした．しかし，これだけでは利用できる線のラン

く，記憶しやすい経路となる.

ドマークが少なくなるため，Tweet された位置を地図上に

このような経路案内を実現するためには，既存の道路

プロットし，その頻度の高い交差点が続くルートも線のラ

ネットワークを使うよりも，ランドマークを基本にした新ンドマークとした．今回はそのルート選択は人手で行っしい経路グラフを生成する方が効率が良い．特に，広域ラた．この自動化は今後の研究テーマである．

ンドマークに関しては，経路が複数考えられるため，それ4.1.3 広域（面の）ランドマーク

らを集約した抽象的なパスを 1 つ生成すると都合が良い．

広域ランドマークとは，広範囲から認識可能な構造物をそのような抽象的なパスと，実際の線のランドマークとの指す．広域ランドマークとしては，「東京タワー」のよう交点も，経路グラフのノードとなる．このような経路グラに視認性に基づくものもあれば（幾何的ランドマーク），フの具体的な生成方法および経路探索手法については，そ「浅草浅草寺」といったように，見えなくてもその近隣かられぞれ 4.3 節および 4.4 節で説明する．

存在する方向が知覚できるもの（意味的ランドマーク）も4. ランドマーク・ナビゲーション・システム
本章では，ランドマークの決定方法，ランドマーク可視

考えられる．本論文では，前者のみを対象とし，自動的な面のランドマークの抽出と，その可視領域マップの生成を行った．詳細を次節で述べる．

性マップの自動生成，およびランドマークを利用した経路
グラフの生成と経路探索について具体的に説明する．

4.2 広域（面の）ランドマークの抽出と可視領域マップの自動生成

4.1 ランドマークの決定方法

4.2.1 広域（面の）ランドマーク候補の選定

一般に，ランドマークは，記憶しやすく，視認性が高い構

広い範囲から視認される構造物として，背の高い建物や，造物であると定義される [13]．そのようなランドマークは高い地点に立つ建物などが考えられる．その際に，街全体

具体的には，幾何的なランドマークと意味的なランドマー

から建物の高さ上位 100 件などを選んでしまうと，街の中クに分類できる (表 1)．幾何的なランドマークとは，文字

心部にばかりランドマークが集中してしまう．そこで，ま通りその形や色などが特異的であるものをさし，画像処理ず，対象となる都市の矩形領域を 1km 四方のブロックになどで検出可能である．一方で，意味的なランドマークと分割する (図 5)．そして，各ブロック内に含まれる建物のは，形や色合いなどに特に目立つ特徴は無いものの，人気

うち，高い順に上位 n 件の建物を広域ランドマーク候補とのカフェなど，人間にはすぐに発見できるものを指し，例

して選択する (図 6)．n は，作成する都市の状態に応じて，

えば，Twitter や Flicker などの情報から取得可能である．

適切な数値を設定する．

意味的なランドマークは，特にその地域のユーザーにとっ4.2.2 広域（面の）ランドマーク可視領域マップの生成ては有効な情報となる．以下，本論文におけるそれぞれの次に，広域ランドマークの可視領域マップを生成する．

ランドマークのに抽出方法について説明する．

これは，全ての交差点から全周を見渡した景観画像を 3 次

4.1.1 局所的（点の）ランドマーク

元コンピュータグラフィクスにより描画し，その画像に含局所的ランドマークは，郵便局やコンビニエンス・スト

まれているランドマークを発見することで実現する．建物

ア，やガソリン・スタンドなどの曲がり角に存在するよう情報を実際に描画することで，任意の交差点位置から，任な，既存のカーナビゲーションシステムなどで利用され意の建物の可視性が正しく判別でき，さらに，その可視率

るランドマークのことを指す．これらの情報は，GIS や，も計算できる．建物・道路・地形等のデータは，3 次元 GIS

Google API・Yahoo API 等で取得することが可能である．

で用いられる電子地図（DEM や Google Earth の建物デー

本論文では，GoogleAPI で，上記キーワードで検索し，見タなど）から入手可能である．描画するオブジェクトは以つかったものを点のランドマークとして利用した．このた

下の 2 種類である．

© 2015 Information Processing Society of Japan4

図 7 レンダリング結果その 1

図 4

図 8 レンダリング結果その 2

GIS データからの都市景観の描画（サンフランシスコ市）

図 9 面のランドマークの可視領域マップの例 1．可視率が高い程赤色に近く，低いほど青い．

• 地形データ
建物の可視判定を行う際には，高低差により下側から建物が見えてしまうことを避けるために，地形データも併せて描画する．
具体的な処理は以下の通りである．まず，前節で述べた手
図 5

都市のブロック分割例

法により選択した面のランドマーク候補に固有の番号を割り振り，各番号に対応する個別の色をそのランドマークの建物の色とする．また，候補以外の建物をおよび地形デー
タ（背景）はそれ以外の色をアサインする．こうすること
により，レンダリングされた全周画像中に含まれる画素の色とその数を調べることで，交差点から見えるランドマー
クの ID と，その可視率を計算できる．視点を変えたときのレンダリング結果の様子を図 7，8 に示す．得られた可視領域マップの例を図 9，10 に示す．ここで，黒丸はランドマークとなる建物の位置である．可視率が高い程赤色に近く，低いほど青く示されており，緑色はその中間程度の可視率を示す．

4.3 ランドマークに基づく経路探索用グラフの生成
図 6面のランドマークとなる建物の自動選択結果．

経路グラフの生成アルゴリズムを，図 11，および図 12，
図 13，図 14 を用いて説明する．経路グラフの生成は，主• 建物データに 4 つの工程に分けることができる．まず，出発地と目的提案システムでは建物の可視性のみが重要となるた地を設定し（図 12 では S および G で示す），この 2 地点

め，個々の建物を 3DCG により描画する．(図 4)．

を含む Bounding Box を生成する．2 つ目の工程として，© 2015 Information Processing Society of Japan

5

^

䝇䝍䞊䝖

'

䝂䞊䝹

^

'

⥺䛾䝷䞁䝗䝬䞊䜽
図 12
図 10面のランドマークの可視領域マップの例 2．可視率が高い程㠃䛾䝷䞁䝗䝬䞊䜽

Ⅼ䛾䝷䞁䝗䝬䞊䜽

スタートとゴールを含む，Bounding Box 範囲内にある点と線と面のランドマーク．

赤色に近く，低いほど青い．
^

Bounding Box䛾⏕ᡂⅬ䞉⥺䞉㠃䛾䝷䞁䝗䝬䞊䜽䛾ᢳฟⅬ䠉㠃䛾ྍどᛶ䛛䜙᪂䛧䛔Ⅼ䞉⥺䛾䝷䞁䝗䝬䞊䜽䜢⏕ᡂ
஺ᕪⅬ䜢䝜䞊䝗䠈
䛭䛾㛫䜢䜶䝑䝆䛸䛧䛶෌ᐃ⩏
図 11 経路グラフ作成のフローチャート

Bounding Box に含まれる点のランドマーク (橙色四角)・

図 13

点と面のランドマークをつないで，新しい線のランドマークを生成し（破線），それと既存の線のランドマークとの交点に新しいノードを作成．

^

線のランドマーク (太い実線)・面のランドマーク (青色の小円) を，システムがデータベースより抽出する (図 12)．
この時，出発地・目的地も点のランドマークに含めておく．
また，ここで示される水色の大円は，面のランドマークの可視領域であり，実際には前節で得られるような複雑な形状をしている．3 つ目の工程として，点と面のランドマー'

クから新しい経路探索用のノードとエッジを生成する．新しい経路探索用のエッジとは，ユーザが選択する可能性のある複数の経路を一本にまとめた仮想的なパスであり，広域ランドマークと，その可視領域内に存在する点のランドマークとを線で繋ぐことで生成される（太い破線）．新し

図 14

経路探索結果（太い実線矢印）．

い経路探索用のエッジと，既存の線のランドマークが交わ最初のグラフと統合することで最終的な経路グラフを生成る時，これを新たな経路探索用のノードとする (図では三する（図 14）．

角)(図 13)．この新しい経路探索用のノードは，既存の点のランドマークと異なり，目印としては使用できないが，

4.4 ランドマーク数を最小化する最適経路探索

経路探索では使用される．最後の工程として，経路探索用

このようにして生成されたランドマークのみからなるのノードとエッジを，点と線と面のランドマークからなる

経路グラフを使用して，経路探索を行う．経路探索は，© 2015 Information Processing Society of Japan6

Dijkstra 法 [2] や遺伝的アルゴリズム（GA）[4] を用いて解くことができる．本論文では，経路を短くしながら，利用するランドマーク数を減らし，かつ面のランドマークの可視率を考慮するため，Chang Wook らの提案した遺伝アルゴリズム (GA) を用いた [1]．具体的には，次のような評価関数を用いた．地点 i から地点 j に移動するための経由点数を N +1 とし，N 地点の経由地点リストを

T = {i, · · · , Tp , · · · , j} と表現する．また，隣接する 2 つの地点 s,t 間の距離を Dist(s, t) と表現する．また，V (p) は
ノード p の可視率である．これを用いて，本論文で用いる，
経路 T の評価関数 Cost(T ) を以下のように定義する．

Cost(T ) =N−1∑

Dist(Tp , Tp+1 ) + w × V (p) × N

(1)

p=0

図 15

使用した局所的ランドマーク

5.1 経路探索
この評価関数により，経路長を短くするだけでなく，経サンフランシスコの経路グラフを生成するにあたって実路案内に用いられるランドマーク数を小さく抑えつつ，経際に使用した各ランドマークを (図 15，図 16，図 6) に示す．

路からランドマークが見える割合を大きくすることができ

局所的ランドマークは Google Map より検索し，検索ワーる. 重み w を変更することで，経路長とランドマーク数のドを gas station，police oﬃce，hospital，departmentstore，

いずれを重視するか，バランスを調整することができる．

church，station として，交差点にあるもののみを採用した

GA における経路の表現方法としては，ノード数 × ノー

(図 15)．線のランドマークは，GoogleMap 上で太く示さ

ド数の行列を作成し，GA が持つ変数として，各ノード間れる，高速道路やメインストリートに加えて，Twitter のの経路の使用の有無を 1 · 0 で表現した．また，付加情報

位置情報をプロットした地図から，頻度の高いルートを人として，ノード間の距離情報と接続情報を GA に与えた．

手により選択した (図 16)．広域ランドマークは本論文で

距離情報は，式 (1) における 2 地点間の距離に用いるもの

提案した手法により，全て計算により求めた（図 6）．図 9，として，ノード間のユークリッド距離を計算した．また，

図 10 は，求めた 171 個の面のランドマークのうち，2 つに

接続情報は，GA が経路を変更する際の制約条件として用関して可視領域マップを示した例である．

いた．

これらのランドマークを使用して，新しい経路グラフを

Dijkstra 法などに対して，GA を用いた経路探索は計算生成した．広域ランドマークと，その可視領域マップ上にコストが高いが，線や点のランドマークを導入することで，ある局所的ランドマークとの間をつないで，新しい線のラ

既存の道路ネットワークよりも大幅にコンパクトな経路グ

ンドマークをを引いた様子を図 17 に示す．水色の線が線ラフが生成できるため，複雑な評価コストを用いても，短のランドマーク，青色の点が局所的ランドマーク，そして時間に最適経路を見つけることができる (図 14)．

桃色の点が広域ランドマークの位置を表している．赤色の5. 実験

線が，新たに生成された経路探索用エッジである．さらに，
本実験では，経路探索の効率化のために，実際に経路案内

本章では，提案手法により実際に生成した経路グラフでで利用されることのないノードやエッジを予め除去するこ

経路探索を行い，探索された経路を評価する. 提案システとで，最終的な経路グラフ図 18 を得た．ここで，除去さムが実用的な規模の都市 GIS データに対して適用可能でれた要素例としては，必ず U ターンすることになる，広域あることを示すために，San Francisco Data が公表していランドマークに接続された線のランドマークなどである．

るサンフランシスコ市の全域の GIS データ [7] を用いてラこの生成されたサンフランシスコの経路グラフを使用しンドマーク可視性マップの作成を行った．本 GIS データて，GA による経路探索を行った．今回，可視率 V (p) に関には，都市にあるほぼ全ての建物および経路グラフの情報

しては，閾値を決めて可視率の低いものはカットするものが含まれている．具体的には，85,116 件の建物の 3 次元形とし，評価関数には加えなかった．これは，経路の評価実状情報，および 12,188 件の道路情報から構成されている．

験を Google Street View を使用して行ったため，解像度なまた，ランドマークの決定方法において，実験で使用する

どの問題で可視率を正当に扱うことができないと判断した

サンフランシスコ市のデータでは高い順に上位 n = 10 件ためである．既存のサンフランシスコの道路ネットワークの建物をランドマークとして選択した．

を使用した最短経路探索結果と，生成した経路グラフを使© 2015 Information Processing Society of Japan

7

図 16

使用した線のランドマーク

図 18

図 17

生成した経路グラフ結果

経路グラフ生成の様子

用した経路探索結果の例をそれぞれ図 19 と図 20 に示す．
赤い太線が経路探索の結果である．図 20 には，新たに生図 19

サンフランシスコの道路ネットワークを使用した最短経路
探索

成した経路グラフも青線で重ねて示している．探索されたは難しい．一方で，実際にユーザに道案内を提示し，その経路の実際の長さは，サンフランシスコの道路ネットワー

経路を使ってゴールに到達してもらい，かかった時間や地クを使用した最短経路探索が約 11.9km であったのに対し

図の参照回数等を調べる方法は評価としては有効ではあるて，生成した経路グラフを使用した経路探索では約 15.4km

ものの，実際に，多くの被験者に，長距離を異なる経路で歩となった（仮想パスでは，実際の道路ネットワークを用いいてもらうことは困難である．さらに，一度使用したルーて最短経路探索を行った）．提案手法のほうが，総距離は長

トは，被験者が学習してしまうため，似たような経路で同くなったが，最初に大通りに沿って進み（左下の線のラン

じ被験者に何度もテストすることも避ける必要がある．こドマーク），次に遠くに見える高層ビルを目指して進み（中のため，実地によるテストを行うことは現実的には難しい．

央の広域ランドマーク），最後に再びぶつかる大通り（線のそこで，本論文では，Google Street View を使用し，実際

ランドマーク）に沿って進む，といったイメージがしやすにスタートからゴールまで被験者にブラウザ上で辿り着い

く，記憶し易い経路となっていることが分かる．

てもらい，擬似的な道案内を体験してもらうことで評価することとした．実際の実験の手順は以下の通りである．

5.2 Google ストリートビューを用いた道案内の評価

被験者には，最初に，1．スタートの位置情報，2．ゴー

本手法の有効性を評価する手法として，最短経路探索に

ルの位置情報，3．ランドマークを含めた経路情報の記載

おける経路長のような，客観的な評価基準を設定することされた案内地図と，4. 経路案内に使用されるそれぞれのラ© 2015 Information Processing Society of Japan8

図 21 実験に使用した経路例 2．赤線が提案手法，青色が経路グラ
図 20

フ，緑線が最短経路である．(広域ランドマークを目指す経

生成した経路グラフを使用した最短経路探索

路を直線で表示している)

ンドマークの写真，といった情報を印刷した資料を与える．
ユーザとしては，歩行者や二輪車を想定し，被験者には，スタートする前に出来るだけ地図やランドマークの情報を覚えるよう指示し，スタート後は，配布した情報や Google
ストリートビュー上の自己位置は出来るだけ確認しないものとした．しかし，そうすると，途中で自己位置が分からなくなったり，経路を失念したりして，ゴールまで辿りつけなくなる恐れがあるため，必要に応じて被験者は，自己位置の確認や，最初に渡した情報を参照できるものとし，その回数を記録した．
評価の基準は，スタートからゴールに到達するまでの時
間，地図を見直した回数，Google Street View で自己位置確認した回数の 3 つとした．また，個人の方向認知能力やGoogle Street View の扱いの熟練度によって，被験者ごとの結果が大きく異なるため，同じ人物に異なる経路を複数

図 22 実験に使用した経路例 3．赤線が提案手法，青色が経路グラ与え，それぞれを最短経路と提案手法の 2 つの手法で試行

フ，緑線が最短経路である．(面のランドマークを目指す経させた．その際，同じ被験者が同じ経路を歩くことは無い

路を直線で表示している)ようにした．これは，経路にも難易度の差はあるものの，⿕㦂⪅䛻䜘䜛ホ౯⤖ᯝ

全て同じ市内にある経路での実験のため，その差は個人差に対して著しく小さいと考えられるためである．実験にあたり図 19，図 20，および図 21, 図 22 に示す合計 3 種類の

㻝㻚㻞

ルートを用意した．なお，経路 2 や 3 においては提案手法

㻝の経路の方が短く見えるが，これは，面のランドマークを㻜㻚㻤

目指す経路を直線で表示しているためであり，実際にこのような直線ルートが存在している訳ではない．被験者 10
名にそれぞれ 2 経路，合計 20 回の試行を行った．結果を
図 23 に示す．縦軸は最短経路手法の結果が 1 となるように，それぞれ正規化したものであり，エラーバーは分散の1σ を表している．
結果を見ると，提案手法のほうがスタートからゴールに᭱▷⤒㊰᥈⣴
ᥦ᱌ᡭἲ

㻜㻚㻢
㻜㻚㻠
㻜㻚㻞
㻜

⤒㐣᫬㛫

⮬ᕫ఩⨨ཧ↷ᅇᩘ ᱌ෆ⤒㊰ཧ↷ᅇᩘ
図 23

評価実験の結果辿りつくための時間が短くなり，さらに地図の見直し回数と自己位置確認回数のそれぞれが大幅に減少していること© 2015 Information Processing Society of Japan

9

が分かる．ただし，それぞれの評価要素ごとに，最短経路

参考文献

探索と提案手法の両群の値を，t 検定により検証したとこ[1]

ろ，地図の見直し回数と自己位置確認回数に関しては，有意差が得られた (p<0.05) が，経過時間に関しては有意差は得られなかった．これは，今回の評価実験では，Google[2]

Street View を用いて評価実験を行っているため，システ
ムの特性（後述）や個人の操作能力の違いによる可能性が[3]ある．総じて，提案手法は，シミュレーション実験においては，より少ない地図の確認回数でゴールまで辿り着くことができたといえる．しかし，最短経路探索では，ランドマークを提示していないため，今回の実験を通して使用し

[4]
[5]

たランドマークの数が，経路探索に与える効果までは評価できていない．同じくらいの距離で，ランドマーク数を変えた場合の被験者実験を今後行う必要があると思われる．
また，出発地から目的地までの経路を実際の道路を歩き，[6]

経過時間の比較を検討する必要がある．
被験者の中には，ランドマークがない最短経路でも早い
時間で目的地まで辿り着く者もいた．その被験者は，最初に見た画像上で目的方向に現れる特徴的な建物を，自らラ

[7]
[8]

ンドマークに設定していた．また，Google Street View による道案内のシミュレーションについては，画像の解像度[9]により広域ランドマークを視認することが難いといった意
見や，Google Street View の仕様により急に隣の道路に移[10]

動してしまうなどして方向感覚が鈍くなってしまい時間がかかったなどの意見があった．正確な評価のためには，より現実に近いシミュレーションシステムの構築が必要と思

[11]

われる．
[12]

6. おわりに[13]

本研究では，点・線・面の 3 種類のランドマークを定義し，そのランドマークを扱って経路探索を行うことで，経[14]路の再確認頻度を減らすことのできるナビゲーションシス
テムを実現した．システムの構築にあたり，建物の可視領域マップの生成手法，経路グラフの生成手法を提案した．
提案手法を用いることで，実在する道路ネットワークでの最短経路探索で求めた経路に比べ，地図や自己位置の参照[15]

Chang Wook Ahn and R.S. Ramakrishna. A genetic algorithm for shortest path routing problem and the sizing of
populations. Evolutionary Computation, IEEE Transactions on, Vol. 6, No. 6, pp. 566–579, Dec 2002.
E. W. Dijkstra. A note on two problems in connexion
with graphs. NUMERISCHE MATHEMATIK, Vol. 1,
No. 1, pp. 269–271, 1959.
M. Drager and A. Koller. Generation of landmark-basednavigation instructions from open-source data. In EACL
’12 Pages 757-766, 2012.
John H. Holland. Adaptation in Natural and Artificial
Systems. MIT Press, Cambridge, MA, USA, 1992.
Daniele Quercia, Rossano Schifanella, and Luca Maria
Aiello. The shortest path to happiness: Recommending beautiful, quiet, and happy routes in the city. In 11
pages, 7 figures, Proceedings of ACM Hypertext 2014,
2014.
YONEKURA Rina, AKAGI Yasuhiro, ONO Satoshi,
KAWAI Yukiko, and KAWASAKI Hitoshi. Navigation
system which uses visibility map of landmarks to reducereference count of the map. In IEVC2014 4B-o6, 2006.
SFGOV.
San
Francisco
Data,
2014.
https://data.sfgov.org/.
河野亜希, 谷村孟紀, 崔楊, 河合由起子, 川崎洋. 景観の可視性を考慮したルート探索システムの提案. 情報科学技術
レターズ, Vol. 6, No. LK-005, pp. 351–354, 2007.
中澤啓介, 岡田謙一. ランドマークの視認性に基づいた
動的な案内地図作成. 情報処理学会論文誌 Vol.48 No.1,
2008.
藤井憲作, 東正造, 荒川賢一. 経路案内情報がナビゲーショ
ンに及ぼす影響. 電子情報通信学会論文誌. A, 基礎・境界
J87-A(1), 40-49, 2004-01-01, 2004.
藤井憲作, 杉山和弘. 携帯端末向け案内地図生成システムの開発. 情報処理学会論文誌. Vol.41, No.9, pp.2394-2403,
2000.
多賀大泰, 高橋直久. ランドマーク視認マップを用いた位置特定システムの実現. In DEWS2006 4B-3, 2014.
中澤優一郎, 山本隆徳, 細川宜秀. 象徴性と相対的場所性に基づく強いランドマーク検索システムの実現方式. In
DEIM Forum 2012 B2-4, 2012.
宇戸裕人, 古川宏. ランドマークの定量的評価に基づく歩行者の不安を軽減する経路探索アルゴリズム (自動車運転/位置情報/通信技術). シンポジウムモバイル研究論文
集 2010, 27-32, 2010.
米倉梨菜, 赤木康宏, 小野智司, 河合由紀子, 川崎洋. 可視性に基づくランドマークの自動検出とこれを利用した道
案内システム. In DEIM Forum 2014 E9-4, 2014.

回数を減らす道案内システムを実現することができた．これは，例えば二輪車での移動など，ゴールまで辿り着くまでの間に，自己位置を確認することが困難な場合に特に有効である．今後の課題としては，他の都市でも実験を行い，提案するランドマーク・ナビが有効な都市とそうでない都市の区別や，SNS による意味的ランドマークの自動取得などが挙げられる．

7. 謝辞
本研究の一部は，内閣府最先端研究 (LR030)，文科省科
研費 (25870570,24500120) の助成を受けて実施された．

© 2015 Information Processing Society of Japan

10