Construction of photo trip patterns based on geographical information

• US 8,626,699 B2
• Filed: 09/16/2009
• Issued: 01/07/2014
• Est. Priority Date: 09/16/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Xie, Xing, Arase, Yuki
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Seck, Ababacar
• Application Number:
  US12/560,872
• Publication Number:
  US 20110066588A1
• Time in Patent Office: 1,574 Days
• Field of Search: None
• US Class Current: 706/58
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation

Abstract

Techniques for reconstructing photo trip patterns from geo-tagged photos are described. Photo trip patterns are reconstructed by mining geo-tagged photos from the Web or a data storage and segmenting the photos based on at least the geographical identification information associated with the photos. Mining semantics of each photo trip pattern may also be performed using tags associated with the photos.

Claims

1. A method comprising:

identifying a plurality of sets of metadata associated with a plurality of photos, at least one set of metadata being associated with a respective one of the plurality of photos and including at least geographical information related to a location where the respective photo was captured; and

determining, by using a processor, photo trip patterns from the plurality of photos based at least in part on the plurality of sets of metadata, at least one photo trip pattern being representative of a set of visited locations and associated transition times, in which the set of visited locations is segmented into different trips based on a calculated gap between events, the gap between events being calculated according to a function of a transition time gap between consecutive locations, a location gap between consecutive locations, and a parameter to balance an effect on the gap between events attributable to the transition time gap and an effect on the gap between events attributable to the location gap, such that;

a first value of the parameter results in a first calculated gap between events;

a second value of the parameter value, different from the first value of the parameter, results in a second calculated gap between events, different from the first calculated gap between events;

the calculated gap between events represents no change of trips when the calculated gap between events is less than a threshold value; and

the calculated gap between events represents a change of trips when the calculated gap between events is greater than a threshold value.

2. The method of claim 1, wherein the at least one set of metadata further includes:

time information related to date and time on which the respective photo was captured;

a photo identification associated with the respective photo;

a user identification associated with a photo owner by whom the respective photo was captured; and

a tag associated with the respective photo having description of the location where the photo was captured.

3. The method of claim 1, wherein determining photo trip patterns comprises:

segmenting the plurality of photos into subsets of photos based at least in part on the geographical information related to one or more of the plurality of photos.

4. The method of claim 3, wherein segmenting the plurality of photos into subsets of photos comprises:

determining a respective location gap between the location where the respective photo was captured and a reference location for one or more of the plurality of photos; and

grouping photos having the respective location gaps that fall within a respective threshold location gap range into a respective subset of photos.

6. The method of claim 1, wherein the at least one set of metadata associated with the respective one of the plurality of photos further includes time information related to date and time on which the respective photo was captured, and wherein determining photo trip patterns comprises:

determining a respective location gap between the location where the respective photo was captured and a reference location for one or more of the plurality of photos;

determining a respective transition time gap between the last photo captured at a first location and the first photo captured at a second location visited after the first location for a pair of consecutively visited locations; and

grouping the plurality of photos into subsets of photos based at least in part on the location gaps and the transition time gaps, in which one or more of the photos of the subsets of photos are related to a respective one of the plurality of locations and having a transition time gap with another subset greater than a threshold transition time gap.

7. The method of claim 6, wherein determining photo trip patterns further comprises:

identifying a sequence of locations as a photo trip pattern, at least one location having at least one subset of photos associated therewith and being separated from another location by a respective transition time gap greater than the threshold transition time gap.

8. The method of claim 1, wherein at least one set of metadata associated with a respective one of the photos further includes a tag associated with the respective photo having description of the location where the photo was captured, and wherein determining photo trip patterns further comprises:

identifying semantics associated with the at least one photo trip pattern based at least in part on the tag associated with one or more of the plurality of photos.

9. The method of claim 8, wherein identifying semantics associated with the at least one photo trip pattern comprises:

determining a term frequency for the tag as a number of times the respective tag is related to photos captured in the plurality of locations;

determining an inverse document frequency for the tag as a ratio of a number of total photos of the plurality of photos to a number of the photos having the respective tag associated therewith; and

determining a user frequency for the tag as a ratio of a number of photo owners who use the respective tag to describe at least one of the plurality of photos to a number of total photo owners of the plurality of photos.

10. The method of claim 9 further comprising:

determining a score for the tag using the respective term frequency, inverse document frequency, and user frequency.

11. The method of claim 8, wherein the location is represented by a hierarchy of geographical regions including at least a first level of geographical region and a second level of geographical region that includes the first level of geographical region, and wherein identifying semantics associated with the photo trip pattern based at least in part on the tag associated with the plurality of photos comprises identifying semantics associated with the photo trip pattern by considering tags at the first level of geographical region.

12. The method of claim 1, wherein the geographical information includes latitudinal and longitudinal information of the location where the respective photo was captured.

13. The method of claim 12 further comprising:

converting the latitudinal and longitudinal information to a hierarchical representation of the respective location, the hierarchical representation including at least a geographical region of a first level and a geographical region of a second level that encompasses the geographical region of the first level.

14. The method of claim 13, wherein the hierarchical representation of the location includes a name of a city where the respective photo was captured, a name of a state in which the city is located, and a name of a country in which the state is located.

5. The method of 1, wherein the at least one set of metadata associated with the respective one of the plurality of photos further includes time information related to date and time on which the respective photo was captured, and wherein determining photo trip patterns comprises:

segmenting the plurality of photos into subsets of photos based at least in part on the geographical information and the time information related to one or more of the plurality of photos.

15. A method comprising:

segmenting a plurality of photos into subsets of photos based at least in part on geographical information and time information related to the plurality of photos;

identifying, by using a processor, photo trip patterns, at least one photo trip pattern having a sequence of locations, a location of the sequence of locations having at least one of the subsets of photos associated therewith and being separated from another location based on a determination that a calculated event gap value is greater than a threshold event gap value, wherein the event gap value is calculated based on a transition time gap and a location gap, adjusted by a parameter to balance respective contributions to the event gap value by the transition time gap and the location gap; and

identifying semantics associated with the at least one photo trip pattern based at least in part on tags associated with the plurality of photos, one or more of the tags being associated with at least one of the plurality of photos and describing the location where the at least one of the plurality of photos was captured.

16. The method of claim 15, wherein segmenting a plurality of photos into subsets of photos based at least in part on geographical information and time information related to the plurality of photos comprises:

determining a respective location gap between the location where the respective photo was captured and a reference location for one or more of the plurality of photos;

determining a respective transition time gap between a last photo captured at a first location and a first photo captured at a second location visited after the first location for a pair of consecutively visited locations; and

grouping the plurality of photos into the subsets of photos based at least in part on the location gaps and the transition time gaps.

17. The method of claim 15, wherein identifying semantics associated with the at least one photo trip pattern based at least in part on tags associated with the plurality of photos comprises:

determining a term frequency for a tag as a number of times the tag is related to photos captured in the plurality of locations;

determining an inverse document frequency for the tag as a ratio of a number of total photos of the plurality of photos to a number of the photos having the tag associated therewith; and

determining a user frequency for the tag as a ratio of a number of photo owners who use the tag to describe at least one of the plurality of photos to a number of total photo owners of the plurality of photos.

18. The method of claim 15 further comprising:

converting latitudinal and longitudinal information included in the geographical information into a hierarchical representation of the location where the respective photo was captured, the hierarchical representation including at least a geographical region of a first level and a geographical region of a second level that encompasses the geographical region of the first level.

19. A computer storage device storing computer-executable instructions that, when executed by one or more processors, perform acts comprising:

identifying a plurality of sets of metadata associated with a plurality of photos, at least one set of metadata being associated with a respective one of the photos and including at least geographical information related to a location where the respective photo was captured; and

determining photo trip patterns from the plurality of photos based at least in part on the plurality sets of metadata, at least one photo trip pattern being representative of a set of visited locations and associated typical transition times, in which the set of visited locations is segmented into different trips by comparing an event gap value to a threshold gap value, wherein the event gap value is calculated based on a transition time gap, a location gap, and a parameter to reflect a weight given to the transition time gap and a weight given to the location gap, such that a first value of the parameter results in a first event gap value, and a second value of the parameter, different from the first value of the parameter, results in a second event gap value, different from the first event gap value.

20. The computer storage device of claim 19, wherein the act of determining photo trip patterns from the plurality of photos based at least in part on the plurality sets of metadata comprises:

segmenting the plurality of photos into subsets of photos based at least in part on the geographical information related to at least one of the plurality of photos;

identifying the photo trip patterns wherein the location has at least one of the subsets of photos associated therewith; and

identifying semantics associated with the at least one photo trip pattern based at least in part on tags associated with the plurality of photos, at least one of the tags being associated with a respective one of the plurality of photos and describing the location where the respective photo was captured.