[DL輪読会] DeepNav: Learning to Navigate Large Cities

DEEP LEARNING JP [DL Papers] DeepNav: Learning to Navigate Large Cities (CVPR2017) Masashi Yokota, Nakayama Lab http://deeplearning.jp/

• http://deeplearning.jp/

書誌情報 • Authers: Samarth Brahmbhatt, James Hays • Conference: CVPR 2017 • 選定理由: 不動産系(BtoB)で起業しているので都市構造を学習するとい う視点がすごい好きだった。 2

コンビニがどこに多くあるか 知っていますか？ 3

概要 • コンビニどこにある？ – 主要幹線道路 – 学校、オフィス周辺 – バス停 –駅 なんで？？ 人が多いから！！ 4

名古屋駅の最寄りのUFJへの 行き方はわかりますか？ 5

概要 • 名古屋出身の自分でも分からない…. でも、ググらなくても、なんとなく探すことは可能！ – 人通りの多いところへ行ってみる – 大通りへ行ってみる • 上記の事ができるのは、なんとなく銀行がどこにありそうか 予測できるから。 – この論文で習得したい事！ 構造物の建設場所には、ある程度規則性がある。この規則性が 分かるようになれば、初めての場所でもどこに何があるのか予 測できるはず。 6

何が嬉しい？ • 地理 – GPSの届かない場所でのナビゲーション • 僻地、地下道、電波の届きにくい高層ビル群 etc • 屋内 – 家庭内ロボット • 部屋の配置傾向を知っていれば再学習無し(or少ないデータでの再学 習)で運用可能。 – 風呂場の近くにはトイレがあるetc 7

この論文において解くタスク • Street Viewで取得した複数の都市データで都市構造を学習 – 全てのデータ点で5種類の目的地(銀行、学校etc)の場所を学習 • 目的地までの距離はどれくらいか • どの方向に何があるのか • 見ず知らずの場所で指定された目的地へ行けるかテスト – 評価値 • 目的地までの到達成功率 • 目的地まで到達する最小ステップ数 8

データセット 1. Google Map Street Viewか ら道の画像データを収集 – 各交差点に対して東西南北の 画像を取得 2. 選んだ画像データからグラ フを作成(最短距離の Annotationを作るため) 3. 目的地(学校、銀行、マクド ナルド、教会、ガソリンス タンド)の場所を取得 4. 各写真の位置から目的地ま での距離で取得。 9

提案手法 10

提案手法 • 距離ベース – DeepNav-distance • 与えられた画像の位置から、最寄りのスポットまでの距離を予測 • 方向ベース – DeepNav-direction • 与えられた画像の位置から、最寄りのスポットの方角を予測 – DeepNav-pair • 画像のペアが与えられて、目的地に行くのにどちらへ行けばよいのかを予測 11

提案手法 DeepNav-distance 12

DeepNav-distance ガソリンスタンドへ行きたい。 どっちへ進めば良い？ • 東西南北のそれぞれの 方向へ進んだ時の目的 地までの距離を予測。 • 各目的地までのMSEを 最小化するように学習 • (テスト時)距離が最も 小さくなる方向へ進む。 13

DeepNav-distance ガソリンスタンドへ行きたい。 どっちへ進めば良い？ 90m • 東西南北のそれぞれの 方向へ進んだ時の目的 地までの距離を予測。 290m • 各目的地までのMSEを 最小化するように学習 340m 510m • (テスト時)距離が最も 小さくなる方向へ進む。 14

DeepNav-distance 入力画像の方向に対して進んだ時、各目的地との距離を予測。 学習時は予測値と実際の距離のMSEを最小化する。 15

提案手法 DeepNav-direction 16

DeepNav-direction ガソリンスタンドへ行きたい。 どっちの方向へ行けば良い？ 1. 入力画像(１枚)に対して、前 後左右どちらへ行けば目的地 へ到着できるのかを予測。 前 左 右 2. 各目的地に対してどちらに行 けばよいか予測する。 3. 学習時は各目的地に対して、 通常の分類問題を最小化する。 後 17

DeepNav-direction 入力画像に対して、前後左右どちらへ行けば目的地へ到着できるのかを予測。 学習時は通常の分類問題を最小化する。 18

DeepNav-direction Annotation • データ作成時に作ったグ ラフを用いる。 • 各ノードに対してA*探索 アルゴリズムを使って最 短経路を計算 • その最短経路を annotationとする。 19

提案手法 DeepNav-pair 20

DeepNav-pair ガソリンスタンドへ行くには、どっちへ行けば良い？ IDEA: 複数の方向を見て学習した方が効率が良いはず。 学習時に各画像に対してスコアを計算し、正しい方向の 画像のスコアが高くなるように学習する。 21

DeepNav-pair ガソリンスタンドへ行くには、どっちへ行けば良い？ Score 20 ５0 IDEA: 複数の方向を見て学習した方が効率が良いはず。 学習時に各画像に対してスコアを計算し、正しい方向の 画像のスコアが高くなるように学習する。 22

DeepNav-pair 画像ペアが与えられ、目的地へ到達するのに上の画像に行けば良い場合は０、 下の画像へ行けば良い場合は１として分類問題として学習させる。どちらも違う 場合はXとして学習時には無視する。 23

DeepNav-pair テスト時 ガソリンスタンドへ行きたい。 どっちへ進めば良い？ モデル Score 55 47 20 18 モデルのブランチを１つにして目的 地のスコアを出力。各方向のスコア を比較し最も大きいスコアの方向へ 進む。 24

DeepNav-pair Annotation • 各ノードに対してA*探索ア ルゴリズムを使って最短経 路を計算する。 • 最短距離のパス中の各ノー ドにおいて2方向を選び、 ラベルを付ける。 – １つ目の画像の方向が最短経 路ならラベル０ – ２つ目の画像の方向が最短経 路ならラベル１ – どれも違うならラベルX • これを最短経路を構成して いる全てのノードに対して 行う。 25

損失関数(DeepNav-direction, -pair) Lg: Geometrically Weighted Loss N: バッチサイズ λ: Geometric Weighting Factor(=0.9) Li: i番目のロス li: 目的地までの最短ステップ数 ほとんどの学習データは、現在地から目的地まで距離がある。 現在地から目的地への距離(最短ステップ数)が遠い程、影響は 小くし、近いほど影響は大きくするべき。 → li(目的地までのステップ数)を考慮することで重みを付ける。 26

実験 27

実験 • データセット – 学習データ • 6都市(Atlanta, Boston, Chicago, Houston, Los Angeles, Philadelphia) – テストデータ(平均ds[m]だけ離れた位置から各都市10回試行) • 4都市(Dallas, New York, Phoenix, San Francisco) • 目的地 – – – – – 銀行 教会 ガソリンスタンド 高校 マクドナルド • 評価値 – 目的地までの到達率 – 目的地までの到達に必要なステップ数の期待値 28

評価値 • 成功率 – 目的地まで75m以内の位置に到達できれば成功。 – 1000回移動しても、目的地に到着できなければ失敗。 • 目的地へ到達するためのステップ数の期待値 s: 成功率 L: 成功時の平均ステップ数 Lmax: 最大ステップ数(=1000) 29

結果 1/8 テストデータにおける到達ステップ数の期待値 30

結果 2/8 サンフランシスコの銀行へ行く場合の各ノードのConfidence。 青点が銀行の位置、オレンジ線がconfidenceの強さ。 DeepNav-pairは目的地周辺のconfidenceがはっきりと高くなっている。 31

結果 3/8 サンフランシスコのマクドナルドが近くにあると判定している時の画像(上カラム) 近くにマクドナルドが無いと判定している画像(下カラム) 32

結果 4/8 サンフランシスコのガソリンスタンドが近くにあると判定している時の画像(上カラム) 近くにガソリンスタンドが無いと判定している画像(下カラム) 33

結果 5/8 ニューヨークにおいて教会が目的地の場合の移動の軌跡 青：スタート地点、緑：教会の位置 34

結果 6/8 35

結果 7/8 36

結果 8/8 全体的にDeepNav-directionが良い感じ。 37

まとめ • データセットは、API使い全自動で取得 • 手法 – 距離ベース • DeepNav-distance – 方向ベース • DeepNav-direction → 最も良かった • DeepNav-pair • random walkと先行研究よりかは良い結果が出てる。 38

感想 • 正直、ナビゲーション感は少ない • 都市構造の傾向を理解するというアイディアは面白い – 道案内よりも街に何が足りないのかを判定するとかの方が面白そう。 （ex. 機械に都市計画させる etc） • 都市構造を学習させるなら時系列にして学習させた方が良さ そう。 – LSTMとかで過去の情報も保持しておくとか。 39