A Travel Planning System
Based on Travel Trajectories
Extracted from a Large Number ofGeotagged Photos on the Web	
Kohya Okuyama and Keiji Yanai
The University ofElectro-Communications, Tokyo, JapanThe University of Electro-Communications, Tokyo, Japan	

1	

Background	• Geotagging photos became common
1. Camera with GPS (e.g. iPhone, Android phones)
2. Photo sharing sites (e.g. Flickr, Panoramio)
3. Applications showing gettagged photos on themap

so	  many	  	  geotagged	  Photos	  on	  the	  Web	The University of Electro-Communications, Tokyo, Japan	

2	

So many geotagged photos !	

The University of Electro-Communications, Tokyo, Japan	3	Background: geotagged photos 	
• The number of geotagged photos on theWeb grows rapidly: Flickr, panoramio– Flickr has 100,000,000 geotagged photos.
(Feb. 2009)	

A “geo-tag”
represents thecoordinates(latitude,longitude)of a location wherea photo are taken. 	
The University of Electro-Communications, Tokyo, Japan	Sequences of geotagged
photos = travel paths	
• People using photo sharing Web sites such as
Flickr and Panoramio usually upload not just one
photos but sequences of geotagged photos.

• By tracing user IDs,
we can obtain traveltrajectories as well as
photo locations.
The University of Electro-Communications, Tokyo, Japan	5	thMy travel path (Dec . 20 )	

Sequence of geotagged photos ⇒ Travel path 6		

The University of Electro-Communications, Tokyo, Japan	Objective	
• We propose a Travel Planning Systemusing geotagged photos and travel trajectories
extracted from the Web.
The system uses collective knowledge on the Web.
It has two functions:(1) Travel route recommendation of both
places and routes before traveling(2) Travel reviewing of your travel after traveling• You should have visited OOO places in addition toOOO. (e.g. botanical garden, Operahouse)
The University of Electro-Communications, Tokyo, Japan	

7	

(1) Travel Route Recommendation
for using
beforetraveling		  User	  	  inputs	

User	  selects	  landmark	  photos	  he	  want	  to	  visit	  イメージを表示できません。メモ
リ不足のためにイメージを開くことができないか、イメージが破損している可能性があります。コン
ピューターを再起動して再度ファイルを開いてください。それでも赤い x が表示される場合は、イメージを削除して挿入してください。	  	  	  	  	  	  イメージを表示できません。メモリ不足のためにイメージを開くことができないか、イメージが破損している可能性があります。コンピューターを再起動して再度ファイルを開いてください。それでも赤い x が表示される場合は、イメージを削除して挿入してください。

The	  system	  outputs	
The	  system	  shows	  several	  routes	  and	  popular	  places	  along	  the	  route	  	  	  	  	  	イメージを表示できません。メモリ不足のためにイメージを開くことができないか、イメージが破損している可能性があります。コンピューターを再起動して再度ファイルを開いてください。それでも赤い x が表示される場合は、イメージを削除して挿入してください。

The University of Electro-Communications, Tokyo, Japan	

8	

(2) Travel Reviewing
for using after traveling	• Automatic organizing travel recoreds––––

Upload geotagged photos after trip
(optional) Upload GPS traces
Summarize route and show photos on map
Show not-visited but popular places.
Re-­‐organize	

The University of Electro-Communications, Tokyo, Japan	

9	Related work	• So many works on geotagged photos• Focus on works with travel paths– Travel route recommendation [X. Lu et al.ACM MM2010]• Combine travel paths of several people into travel routes• No clustering regarding places• No information on landmarks and sightseeing spots– Broad area route recommendation [Y. Arase et al.ACM
MM2010]• No route combination• Not within a city, but among cities e.g. Sydney->Brisbane->Caens

The University of Electro-Communications, Tokyo, Japan	10	Related work: travel places	• Travel place recommendation system[L. Cao et al.ACM MIR2010]– Recommend travel places– No route recommendation

The University of Electro-Communications, Tokyo, Japan	

11	

Related work: travel route (1)	• Travel route recommendation[X. Lu et al. ACM MM2010]– Combine travel paths of several people into travelroutes– No clustering regarding places– No information on landmarks andsightseeing spots

The University of Electro-Communications, Tokyo, Japan	

12	

Related work: Travel route (2)	• Broad area recommendation [Y. Arase etal.ACM MM2010]– Recommend the order of visiting cities andsome places within each city
– Travel plan of wide area
e.g. Sydney->Brisbane->Cairns

The University of Electro-Communications, Tokyo, Japan	

13	

Features of our system	• Offline processing : data preparation– Detect popular places automatically– Extract many travel trajectories
and generate many travel path candidates• Two kinds of online systems– Travel planning before traveling• Recommend both places and routes– Travel reviewing after travelling• Teach places you should have visited for the next trip

– (Realtime travel suggestion system for future work)
The University of Electro-Communications, Tokyo, Japan	

14	

Overview ofthe offine processings	
• Gather	  geotagged	  photos	  from	  Flickr	  	Data	  • Select	  “good”	  data	  	Gathering	• Hierarchical	  clustering	
Place	  • Detect	  popular	  places	  	Clustering	• Extract	  tags	  for	  each	  place	Analyzing	  Place	  • Select	  representa>ve	  photos	  	Clusters	• Extract	  travel	  paths	
ExtracDon	  of	  travel	  	   • Generate	  travel	  route	  candidates	
paths	The University of Electro-Communications, Tokyo, Japan	

15	

Overview ofthe offine processings	
• Gather	  geotagged	  photos	  from	  Flickr	  	Data	  Gathering	 • Select	  “good”	  data	  	• Hierarchical	  clustering	
Place	  • Detect	  popular	  places	  	Clustering	
Analyzing	  Place	  Clusters	
ExtracDon	  of	  travel	  	  paths	

• Extract	  tags	  for	  each	  place	• Select	  representa>ve	  photos	  	• Extract	  travel	  paths	
• Generate	  travel	  route	  candidates	

The University of Electro-Communications, Tokyo, Japan	16	1) Data gathering	• Collect geotagged photos via FlickrAPI• Select geotagged photos– Remove unreliable photos in terms of latitude
and longitude• Geotagged on the large-scale map without GPS• Many photos have exactly the same location– Remove single photos (not in sequences)
Original	  #	  photos	

AHer	  noise	  removal	

User	  A	25189	

192	

User	  B	4793	

4766	

The University of Electro-Communications, Tokyo, Japan	

17	

Metadata obtained via FlickrAPI	• Flickr API provides various information onFlickr photos.
– Geotag (latitude and logitude)– Accuracy of geotag (only use more than 8)– UserID (owner ID) (we can track user’s trace)– Text tags (add text tags to each places)<photo	  id="5017594322"	  owner="75008966@N00"	  secret="f8d231e2cd"	  server="4154"
farm="5"	  >tle="The	  Kyoto	  Tower	  from	  Kyoto	  Sta>on"	  ispublic="1"	  isfriend="0”	  	  isfamily="0“	  	  laDtude=“34.9864095434377”	  longitude=“135.75977325439453”	  	  accuracy=“16”	  datetaken=“2009-­‐10-­‐01	  10:23:45”	  tags=“kyoto	  japan	  kyoto	  tower	  “	  …/>The University of Electro-Communications, Tokyo, Japan	18	Overview ofthe offine processings	
• Gather	  geotagged	  photos	  from	  Flickr	  	Data	  Gathering	 • Select	  “good”	  data	  	• Hierarchical	  clustering	
Place	  • Detect	  popular	  places	  	Clustering	
Analyzing	  Place	  Clusters	
ExtracDon	  of	  travel	  	  paths	

• Extract	  tags	  for	  each	  place	• Select	  representa>ve	  photos	  	• Extract	  travel	  paths	
• Generate	  travel	  route	  candidates	

The University of Electro-Communications, Tokyo, Japan	19	2) Place Clustering	To	  detect	  popular	  places,	  hierarchical	  	  clustering	  is	  carried	  out.	  	  Cluster	  centers	  =	  	  	  popular	  tourist	  places	  The University of Electro-Communications, Tokyo, Japan	

20	

Overview ofthe offine processings	
• Gather	  geotagged	  photos	  from	  Flickr	  	Data	  Gathering	 • Select	  “good”	  data	  	• Hierarchical	  clustering	
Place	  • Detect	  popular	  places	  	Clustering	
Analyzing	  Place	  Clusters	
ExtracDon	  of	  travel	  	  paths	

• Extract	  tags	  for	  each	  place	• Select	  representa>ve	  photos	  	• Extract	  travel	  paths	
• Generate	  travel	  route	  candidates	

The University of Electro-Communications, Tokyo, Japan	21	3-1) Add tags to each place	• Extract tags to explain the places– Extract all the tags within a place cluster– Remove stop words (e.g. Canon, Nikon,..)– Select only the tags where the following scoreis more than the pre-defined threshold.

score =

Number of the tag within the clutesr
Total number of the tag over all the photos

Text	  tags	  associated	  with	  “Kiuomizu	  temple”	  cluster	
Before	october	  japan	  oktober	  kyoto	  kiyomizudera	  2009	  kiyomizutemple	

AHer	

kiyomizudera	  kiyomizutemple	

The University of Electro-Communications, Tokyo, Japan	

22	3-2) Select representative
photos	• Based on the number of matching points withSURF features.
• The photo gathering the most number ofmatching is regarded as a representative one.
The University of Electro-Communications, Tokyo, Japan	

23	Overview ofthe offine processings	
• Gather	  geotagged	  photos	  from	  Flickr	  	Data	  Gathering	 • Select	  “good”	  data	  	• Hierarchical	  clustering	
Place	  • Detect	  popular	  places	  	Clustering	
Analyzing	  Place	  Clusters	
ExtracDon	  of	  travel	  	  paths	

• Extract	  tags	  for	  each	  place	• Select	  representa>ve	  photos	  	• Extract	  travel	  paths	
• Generate	  travel	  route	  candidates	

The University of Electro-Communications, Tokyo, Japan	

24	

Extract traces based on
userID, and simplify them	• Summarize gettag sequences intosequences of place clusters– Associate extracted geotags with place clusters
TRIP	  34.9864095434377	  ,135.7597732543	  34.9878159325440	  ,135.7596874237	  	  34.9894332501478	  ,135.762305259	  	  34.9893629326552,135.7638072993	  	  TRIP	  MODEL	  A-­‐>B-­‐>C-­‐>D-­‐>E-­‐>F	:	  The University of Electro-Communications, Tokyo, Japan	

25	

Combine “Trip models” 	
Trip	  Model	  A	
１０	１６	９	The	  same	  place	  was	  found	  !	

Trip	  Model	  B	
３１	２４	８	

２２	５１	８	４９	３２	

Concatenate	  the	  ﬁrst	  part	  of	  Trip	  model	  A	  and	  the	  lafer	  part	  of	  Trip	  model	  B	
１０	１６	  ８	５１	４９	３２	Newly	  generated	  trip	  model	
The University of Electro-Communications, Tokyo, Japan	

26	Experiments	
• 2million geotaggged photos from Flickr– To extract paths, a lot ofgetagged photos areneeded.

• We focus on “Kyoto” area in Japan.
– 162 unique userIDs.
– 1805 geotag places– 154 place clusters– 18,752 routes
The University of Electro-Communications, Tokyo, Japan	

27	

Online system(1): route
recommendation system	

Select	  landmark	  photos	  the	  user	  is	  interested	  in	Show	  travel	  route	  candidates	

The University of Electro-Communications, Tokyo, Japan	Showing	  the	  selected	  route	  on	  the	  map	  28	

Select landmarks to visit	

The University of Electro-Communications, Tokyo, Japan	

29	

Recommended routes 1	

The University of Electro-Communications, Tokyo, Japan	

30	

Recommended 3 routes	

The University of Electro-Communications, Tokyo, Japan	

31	

Online system(2): Travel
reviewing system 	Upload	  geotagged	  photos	  and	  GPS	  traces	  	  aHer	  coming	  back	  home	
Detect	  visited	  popular	  places	  and	  	  not-­‐visited	  popular	  places	  The University of Electro-Communications, Tokyo, Japan	

The	  system	  says	  	  “You	  missed	  the	  famous	  places,	  OOO.	  Please	  visit	  there	  at	  the	  next	  Dme	  !	  “	32	Conclusions	• We proposed a Travel Planning Systemusing both geotagged photos and travel
trajectories extracted from the Web.

The system has two functions:(1) Travel route recommendation of both
places and routes before traveling(2) Travel reviewing of your travel after traveling

The University of Electro-Communications, Tokyo, Japan	

33	

Future work	• Evaluation by user studies• Experiments with other areas• Detailed search option for routes– Duration, total distance of the route– Ranking of recommended routes• Improvement of UI• Implement a mobile-version real-time route
recommendation system which can be usedfrom smartphones while traveling
The University of Electro-Communications, Tokyo, Japan	

34	

The University of Electro-Communications, Tokyo, Japan	

35	

旅行記録の整理	
1. ユーザの移動経路を読み込む
a. GPSの軌跡
b. 廻った観光地のマッピング

2. 観光地クラスタ間の移動に置き換える– 移動を要約する

3. そのルートで他にも行けた観光地を提示– 他ユーザの観光ルート情報を利用	

The University of Electro-Communications, Tokyo, Japan	

36	

まとめ	• 位置情報付き写真を利用した観光旅行支援のシステムを開発した
1. 仮想観光アルバム– 順序を意識した観光ルートの提案

2. 旅行アルバム補完– 旅行記録の要約と付加情報の追加	

The University of Electro-Communications, Tokyo, Japan	

37	

観光ルート推薦	
1. ユーザの入力– クラスタのテキストタグ，代表画像を表示– いくつかの観光地を選択

2. 候補トリップモデルの検索– 選択されたものを含むトリップモデルを表示

3. 候補経路表示– Google maps APIを利用しルートを表示	

The University of Electro-Communications, Tokyo, Japan	

38	

候補の選択	The University of Electro-Communications, Tokyo, Japan	

39	

ランダムとの比較	

The University of Electro-Communications, Tokyo, Japan	

40	

The University of Electro-Communications, Tokyo, Japan	

41	

予備実験	
• 軌跡の取り方
1. 大量に画像情報を収集
2. Geo-tag画像を選抜
3. ユーザ毎のIDで時間順にソート
4. 撮影位置をつなぎ移動の軌跡を求める

The University of Electro-Communications, Tokyo, Japan	

42	

予備実験	
• 約２００万枚の画像の情報を利用• 位置情報が正確でなくてはならない– 重複した位置のものを除く（下表）• ユーザＡのデータは位置情報が信用できない
対象	

元のデータ数	

除外後のデータ数	

ユーザA	

25189	

192	

ユーザB	

4793	

4766	

• ７０万枚ほどに選抜された
The University of Electro-Communications, Tokyo, Japan	

43	

予備実験	
• あるユーザの撮影位置から軌跡を求めた– マーカが撮影位置– ラインが軌跡• 同じ日に撮影していったものを結んだ	

The University of Electro-Communications, Tokyo, Japan	

44	

予備実験	
ある地域間の比較• 地域で画像数に偏りがある– 観光地としての人気– 軌跡がとれない• 地域の中でも偏りがある– 人気の観光スポットの範囲– 観光スポット内での移動は考慮する必要がある	
The University of Electro-Communications, Tokyo, Japan	

45