System to compile landmark image search results

• US 8,086,048 B2
• Filed: 05/23/2008
• Issued: 12/27/2011
• Est. Priority Date: 05/23/2008
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Naaman, Mor, Kennedy, Lyndon
• Primary Examiner(s): TUCKER, WESLEY J
• Application Number:
  US12/126,387
• Publication Number:
  US 20090290812A1
• Time in Patent Office: 1,313 Days
• Field of Search: 382/155, 382/181, 382224-228, 382/305, 382/306
• US Class Current: 382/225
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries
• CPC Class Codes: G06F 18/232 Non-hierarchical techniques
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]
• CPC Class Codes: G06V 10/763 Non-hierarchical techniques, e.g. based on statistics of modelling distributions

Abstract

This patent discloses a system to compile a landmark image search result. The system may determine a rank of each image within a visual cluster according to at least one of a low-level self-similarity score, a low-level discriminative modeling score, and a point wise linking score. The landmark image search result may be compiled as a function of the rank of each image.

Claims

1. A method to compile a landmark image search result, the method comprising:

receiving, using a computer, a plurality of images and data for each of the images, the data comprising a location corresponding to each image;

grouping the images into a plurality of location clusters based on the location corresponding to each image, each location cluster comprising at least one image;

grouping images of each location cluster into a plurality of visual clusters based on visual features of each image;

determining a rank of each image within each visual cluster according to at least one of a low-level self-similarity score, a low-level discriminative modeling score, and a point wise linking score; and

compiling the landmark image search result as a function of the rank of each image.

2. The method of claim 1, further comprising:

determining a rank of each visual cluster of a set of visual cluster utilizing at least one of a number of users score, a visual coherence score, a cluster connectivity score, and a variability in dates score,

where determining a rank of each image includes determining a rank of each image within a visual cluster for each visual cluster, and

where compiling the landmark image search result includes compiling the landmark image search result as a function of both the rank of each visual cluster and the rank of each image.

3. The method of claim 2, where the visual coherence score is based on the ratio of an inter-cluster distance to an intra-cluster distance.

4. The method of claim 2, where the cluster connectivity score is obtained in part by determining a forward Euclidean distance between a descriptor in a first image and a descriptor in a second image and determining a reverse Euclidean distance between a descriptor in the second image and a descriptor in the first image.

5. The method of claim 2, where the cluster connectivity score is obtained in part by determining whether a forward Euclidean distance plus a predetermined threshold is less than a forward distance between a descriptor in a first image and all other points in a second image.

6. The method of claim 2, where the cluster connectivity score is obtained in part by determining an average number of links per photo for all the photos in a visual cluster.

7. The method of claim 1, where the low-level self-similarity score is obtained in part by determining the Euclidean distance that an image resides from a centroid, where the centroid is based on local geometric descriptors.

8. The method of claim 1, where the low-level discriminative modeling score is obtained in part by assigning a set of candidate photos as pseudo-positives and assigning randomly sampled images as pseudo-negatives.

9. The method of claim 1, where the low-level discriminative modeling score is obtained in part by producing a support vector machine decision boundary, where the support vector machine decision boundary is produced by applying a first model from a first support vector machine to the contents of a second fold and applying a second model from a second support vector machine to the contents of a first fold.

10. A system, comprising at least one processor and memory., to compile landmark image search results, the system comprising:

a module for receiving a plurality of images and data for each of the images, the data comprising a location corresponding to each image;

a module for grouping the images into a plurality of location clusters based on the location corresponding to each image, each location cluster comprising at least one image;

a module for grouping images of each location cluster into a plurality of visual clusters based on visual features of each image;

a module for ranking images in each visual cluster to determine a rank of each image within the visual cluster according to at least one of a low-level self-similarity score, a low-level discriminative modeling score, and a point wise linking score; and

a ranked list generator module to compile the landmark image search result as a function of the rank of each image.

11. The system of claim 10, further comprising:

a module for ranking visual clusters to determine a rank of each visual cluster utilizing at least one of a number of users score, a visual coherence score, a cluster connectivity score, and a variability in dates score,

where the ranking images in a visual cluster includes determining a rank of each image within a visual cluster for each visual cluster, and

where the ranked list generator to compile the landmark image search result further is to compile the landmark image search result as a function of both the rank of each visual cluster and the rank of each image.

12. The system of claim 11, where the visual coherence score is based on the ratio of an inter-cluster distance to an intra-cluster distance.

13. The system of claim 11, where the cluster connectivity score is obtained in part by determining a forward Euclidean distance between a descriptor in a first image and a descriptor in a second image and determining a reverse Euclidean distance between a descriptor in the second image and a descriptor in the first image.

14. The system of claim 11, where the cluster connectivity score is obtained in part by determining whether a forward Euclidean distance plus a predetermined threshold is less than a forward distance between a descriptor in a first image and all other points in a second image.

15. The system of claim 11, where the cluster connectivity score is obtained in part by determining an average number of links per photo for all the photos in a visual cluster.

16. The system of claim 10, where the low-level self-similarity score is obtained in part by determining the Euclidean distance that an image resides from a centroid, where the centroid is based on local geometric descriptors.

17. The system of claim 10, where the low-level discriminative modeling score is obtained in part by assigning a set of candidate photos as pseudo-positives and assigning randomly sampled images as pseudo-negatives.

18. The system of claim 10, where the low-level discriminative modeling score is obtained in part by producing a support vector machine decision boundary, where the support vector machine decision boundary is produced by applying a first model from a first support vector machine to the contents of a second fold and applying a second model from a second support vector machine to the contents of a first fold.

19. A non-transitory computer readable medium comprising a set of instructions which, when executed by a computer, cause the computer to compile landmark image search results, the instructions for:

receiving a plurality of images and data for each of the images, the data comprising a location corresponding to each image;

grouping the images into a plurality of location clusters based on the location corresponding to each image, each location cluster comprising at least one image;

grouping images of each location cluster into a plurality of visual clusters based on visual features of each image;

determining a rank of each image within each visual cluster according to at least one of a low-level self-similarity score, a low-level discriminative modeling score, and a point wise linking score; and

compiling the landmark image search result as a function of the rank of each image.

20. The computer readable medium of claim 19, further comprising instructions for:

determining a rank of each visual cluster of a set of visual cluster utilizing at least one of a number of users score, a visual coherence score, a cluster connectivity score, and a variability in dates score,

where determining a rank of each image includes determining a rank of each image within a visual cluster for each visual cluster, and

where compiling the landmark image search result includes compiling the landmark image search result as a function of both the rank of each visual cluster and the rank of each image.

21. The computer readable medium of claim 20, where the cluster connectivity score is obtained in part by determining a forward Euclidean distance between a descriptor in a first image and a descriptor in a second image and determining a reverse Euclidean distance between a descriptor in the second image and a descriptor in the first image.

22. The computer readable medium of claim 20, where the cluster connectivity score is obtained in part by determining whether a forward Euclidean distance plus a predetermined threshold is less than a forward distance between a descriptor in a first image and all other points in a second image.

23. The computer readable medium of claim 19, where the low-level discriminative modeling score is obtained in part by assigning a set of candidate photos as pseudo-positives and assigning randomly sampled images as pseudo-negatives.

24. The computer readable medium of claim 19, where the low-level discriminative modeling score is obtained in part by producing a support vector machine decision boundary, where the support vector machine decision boundary is produced by applying a first model from a first support vector machine to the contents of a second fold and applying a second model from a second support vector machine to the contents of a first fold.