Geocoding by image matching

• US 8,189,925 B2
• Filed: 06/04/2009
• Issued: 05/29/2012
• Est. Priority Date: 06/04/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kroepfl, Michael, Ofek, Eyal, Wexler, Yonatan, Wysocki, Donald, Kimchi, Gur
• Primary Examiner(s): Repko, Jason M
• Assistant Examiner(s): Thomas, Mia M
• Application Number:
  US12/478,569
• Publication Number:
  US 20100310182A1
• Time in Patent Office: 1,090 Days
• Field of Search: 382/113, 382/190, 382/195, 382/209, 382/216, 382284-289, 702/14, 702/16
• US Class Current: 382/216
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]
• CPC Class Codes: G06V 10/757 Matching configurations of points or features
• CPC Class Codes: G06V 20/00 Scenes; Scene-specific elements control of digital cameras H04N23/60

Abstract

Embodiments of the present invention relate to systems, methods and computer storage media for associating a known geographic location with a known identity. Feature matching, of at least two images, is performed in at least two iterations. The iterations are based on an orientation of feature vectors associated with points of interest in each image. A geometric model is applied to the matched points of interest to improve the matched pairs. Two images are identified as being related. As a result, the known geographic location is associated with the known identity. Additional embodiments include augmenting feature vectors with a coordinate location of a related point of interest based on a geometric model. Further, an exemplary embodiment includes an additional matching iteration based on the augmented feature vectors. In an exemplary embodiment, the feature matching utilizes a Scale-Invariant Feature Transform (SIFT).

Claims

1. A method of utilizing a computing device having a processor and computer-readable memory to associate a known geographic location with a known identity, the method comprising:

matching one or more points of interest defined by feature vectors from a first image with one or more points of interest defined by feature vectors from a second image to result in a first set of matched points of interest, wherein two or more matching iterations are performed, and wherein the number of matching iterations is determined based on a predefined orientation increment;

identifying one or more points of interest that are outliers in the first set of matched points of interest;

removing the outliers from the first set of matched points of interest to result in a second set of matched points of interest;

augmenting each feature vector from the first image that is associated with a point of interest included with the second set of matched points of interest, wherein the augmenting of the feature vector includes adding a dimensional location associated with a point of interest from the second image to which the feature vector is matched;

augmenting each feature vector from the second image that is associated with a point of interest included with the second set of matched points of interest, wherein the augmenting of the feature vector includes adding a dimensional location associated with underlying points of interest;

matching one or more points of interest defined by augmented feature vectors from a first image with one or more points of interest defined by augmented feature vectors from a second image to result in a second set of matched points of interest, wherein two or more matching iterations are performed based on a predefined range of orientations associated with augmented feature vectors;

calculating a first confidence value based, in part, on the second set of matched points;

determining the first image and the second image are related based on the first confidence value; and

correlating a known identity that is associated with one of the first image or the second image with a known geographic location that is associated with the other of the first image or the second image.

2. The method of claim 1, wherein the feature vectors are Scaled-Invariant Feature Transform (SIFT) feature vectors.

3. The method of claim 2, wherein the SIFT feature vectors are defined by 128 dimensions.

4. The method of claim 1, wherein one of the first image or the second image includes metadata describing a geographic location from which the image was captured.

5. The method of claim 1, wherein a roll angle between the first image and the second image is less than 30 degrees.

6. The method of claim 1, wherein the predefined orientation increment is defined as 5 degrees.

7. The method of claim 1, wherein identifying one or more points of interest that are outliers is further comprised of applying a homography model to the matched one or more points of interest.

8. The method of claim 7, wherein the dimensional location is defined by an x-axis and a y-axis coordinate of the homography model as applied to the second image.

9. The method of claim 7, wherein the homography model is selected to fit the matched one or more points of interest utilizing a Random Sample Consensus (RANSAC) algorithm.

10. The method of claim 1, wherein the augmented feature vectors of the first image and the augmenting feature vectors of the second image are defined by 130 dimensions.

11. The method of claim 1, wherein the first confidence value is proportional to a number of inliers less a constant value, and the first confidence value is inversely proportional to an average Euclidean distance of the matched points of the second set of matched points.

12. The method of claim 1 further comprises determining a second confidence value associated with the first image and a third image, wherein the third image is captured from a different perspective than the second image.

13. The method of claim 1 further comprises updating a searchable data store with the correlation between the known identity and the known geographic location.

14. The method of claim 1, wherein the known identity is an entity name.

15. One or more computer storage media having computer-executable instructions embodied thereon for performing a method of associating a known geographic location with a known identity, the method comprising:

determining an orientation of each of a plurality of feature vectors defining points of interest in a first image and a second image, wherein one of the first image or the second image is associated with a known identity and the other of the first image or the second image is associated with a known geographic location;

identifying feature vectors of the second image with an orientation within a predefined angular range of incrementally changing feature vectors of the first image, wherein the feature vectors of the first image are incrementally changed based on a predefined orientation increment;

matching at least one point of interest from the first image with at least one point of interest from the second image based, in part, on a feature vector of the second image identified with a feature vector of the first image to result in matched points of interest; and

associating the known identity with the known geographic location.

16. The computer readable storage media having computer-executable instructions embodied thereon for performing the method of claim 15, further comprising:

identifying a number of inliers for the matched points of interest;

calculating a correlation coefficient for each of the matched points of interest; and

calculating a confidence value, wherein the confidence value is based, at least in part, on the number of inliers and the correlation coefficient for each of the matched points of interest.

17. The computer readable storage media having computer-executable instructions embodied thereon for performing the method of claim 15, further comprising:

wherein the predefined angular range is approximately 45 degrees and the predefined orientation increment is approximately 5-degrees.

18. The computer readable storage media having computer-executable instructions embodied thereon for performing the method of claim 15, further comprising:

wherein the identifying the feature vector of the second image with an orientation within a first predefined angular range of incrementally changing feature vectors of the first image further comprises;

identifying feature vectors of the second image with an orientation within 45 degrees of incrementally changing feature vectors of the first image, wherein the feature vectors of the first image are incrementally changed at a 5 degree increment.

19. The computer readable storage media having computer-executable instructions embodied thereon for performing the method of claim 15, further comprising:

wherein the plurality of feature vectors defining points of interest in a first image and a second image are defined by at least 128 dimensions.

20. One or more computer storage media having computer-executable instructions embodied thereon for performing a method of associating a known geographic location with a known identity, the method comprising:

receiving a first image and a second image, wherein one of the first image or the second image has a known identity and the other has a known geographic location;

identifying points of interest, wherein identifying points of interest comprises;

identifying a first plurality of interest points of the first image, and identifying a second plurality of interest points of the second image;

determining feature vectors associated with each of the points of interest, wherein determining feature vectors comprises;

determining a feature vector for each of the first plurality of interest points resulting in a first plurality of feature vectors, and determining a feature vector for each of the second plurality of interest points resulting in a second plurality of feature vectors;

identifying related points of interest based on an orientation of the feature vectors, wherein identifying the orientation of the feature vectors comprises;

identifying a first orientation selection comprised of one or more of the second plurality of feature vectors having an orientation within a predefined angular range of a first selection of the first plurality of interest points, and

identifying a second orientation selection comprised of one or more of the second plurality of feature vectors having an orientation within the predefined angular range of a second selection of the first plurality of interest points;

identifying matching point of interest in the first image and the second image, wherein identifying matching points of interest comprises;

matching one or more of the first selection of the first plurality of interest points with one or more of the first orientation selection, and

matching one or more of the second selection of the first plurality of interest points with one or more of the second orientation selection;

applying a homography model to the matched points of interest to identify one or more points of interest that are outliers of the matching points of interest;

removing the one or more points of interest that are outliers to result in a first selection of matched points of interest;

augmenting each feature vector associated with the first selection of matched points of interest, wherein a feature vector of a point of interest associated with the first image is augmented with a location of a corresponding matched point of interest of the second image, and wherein a feature vector of a point of interest associated with the second image is augmented with a location of the point of interest associated with the second image;

identifying matching points of interest in the first image and the second image utilizing the augmented feature vectors;

determining the first image and the second image are related, wherein the first image and the second image are related when a confidence value is above a predefined threshold; and

associating the known identity with the known geographic location.