LOCATION RECOGNITION USING INFORMATIVE FEATURE VOCABULARY TREES

• US 20080301133A1
• Filed: 05/29/2007
• Published: 12/04/2008
• Est. Priority Date: 05/29/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Brown, Matthew, Schindler, Grant
• Granted Patent: US 7,945,576 B2
• Time in Patent Office: Days
• US Class Current: 707/6
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06V 20/10 Terrestrial scenes scenes under surveillance with static cameras G06V20/52; scenes perceived from the exterior of a vehicle G06V20/56; scenes perceived from the interior of a vehicle G06V20/59

Abstract

A location recognition technique that involves using a query image to identify a depicted location is presented. In addition to the query image, there is also a pre-constructed database of features which are associated with images of known locations. The technique matches features derived from the query image to the database features using a specialized vocabulary tree, which is referred to as an informative feature vocabulary tree. The informative feature vocabulary tree is specialized because it was generated using just those database features that have been deemed informative of known locations. The aforementioned matching features are used to identify a known location image that matches the query image. The location associated with that known location image is then deemed to be the location depicted in the query image.

Claims

1. A computer-implemented process for location recognition using a query image depicting a location it is desired to identify and a database of features associated with images of known locations, comprising using a computer to perform the following process actions:

generating query image features representative of the query image using the same technique as used to generate the database features resident in the database from the known location images;

for each feature associated with the query image, inputting the query image feature into an informative feature vocabulary tree and identifying a visual word output by the vocabulary tree for that query image feature, wherein the informative feature vocabulary tree was generated using just those database features that have been deemed informative of the known locations and was used to assign visual words to each known location image that are output from the tree whenever a database feature associated with that image is input into the tree;

identifying the known location image having the most visual words in common with the query image; and

designating the location associated with the identified known location image as the location depicted in the query image.

2. The process of claim 1, further comprising the actions of:

prior to generating the query image features,

generating an informative feature vocabulary tree using just those database features that have been deemed informative of the known locations,

for each database feature associated with each known location image, inputting the database feature into the informative feature vocabulary tree and identifying a visual word output by the tree for that database feature, and

for each known location image, assigning the visual words identified from the database features associated with that image to that image.

3. The process of claim 2, wherein the known location images comprise for each location a group of images depicting that location captured from different viewpoints, and wherein the process action of generating the informative feature vocabulary tree using just those database features that have been deemed informative of the known locations, comprises the actions of:

generating a precursory vocabulary tree using a group of database features that are not necessarily most indicative of the known locations;

inputting all the database features into the precursory vocabulary tree and identifying a visual word output for each database feature;

assigning each identified visual word output from the precursory vocabulary tree to the known location image from which the database feature producing the visual word was derived;

identifying how many times each visual word output from the precursory vocabulary tree was assigned to each group of known location images depicting a same location;

determining for each group of known location images depicting the same location and each visual word assigned to a known location image in that group if the visual word is indicative of the location depicted in the group of images based on the number of times the visual word was assigned to an image in the group in view of the number of times the visual word was assigned to an image not in the group;

designating the database feature associated with each visual word determined to be indicative of the location depicted in a group of images depicting the same location to be informative of that location; and

using only those database features designated as being informative of a location to generating the informative feature vocabulary tree.

4. The process of claim 3, wherein the group of database features that are not necessarily most indicative of the known locations represent all the features in the database.

5. The process of claim 3, wherein the database of features associated with images of known locations is too large to effectively generate a single precursory vocabulary tree, and wherein the group of database features represents database features associated with a prescribed-sized portion of the known location images, and wherein the process action of generating the precursory vocabulary tree and the subsequent actions of inputting, assigning, identifying, determining and designating, are repeated for multiple groups of the database features each representing a different portion of the known location images until all the known location images have been processed, and then the database features designated as being informative of a location from all the precursory vocabulary trees are used to generate the informative feature vocabulary tree.

6. The process of claim 3, wherein the process actions of generating a precursory vocabulary tree using a group of database features that are not necessarily most indicative of the known locations and generating the informative feature vocabulary tree, comprise an action of employing a hierarchical k-means technique wherein the cluster centers are initialized so as to be as far apart from each other as possible.

7. The process of claim 3, wherein the process action of determining if a visual word is indicative of a location depicted in a group of images, comprises the actions of:

respectively computing the conditional entropy for each visual word assigned to a known location in the group of images under consideration;

ordering the visual words assigned to the known location in the group of images under consideration by their conditional entropies and identifying a prescribed percentage of them having the smallest conditional entropies; and

designating the prescribed percentage of the visual words producing the smallest conditional entropies to be indicative of the location depicted in the group of images under consideration.

8. The process of claim 7, wherein the process action of computing the conditional entropy of a visual word assigned to a known location image in a group of known location images, comprises an action of computing the equation,

9. The process of claim 1, wherein the process action of identifying the known location image having the most visual words in common with the query image, comprises the actions of:

employing a voting scheme wherein, for each feature of the query image which causes a visual word to be output from the informative feature vocabulary tree that matches a visual word assigned to a known location image, a count associated with that known location image is increased;

designating the known location image having the highest count as the known location image having the most visual words in common with the query image.

10. The process of claim 1, wherein the process action of identifying the known location image having the most visual words in common with the query image, comprises the actions of:

for each known location image i, computing the equation,

11. The process of claim 1, wherein the features are Scale Invariant Feature Transform (SIFT) feature descriptors.

12. A system for location recognition using a query image depicting a location it is desired to identify and a database of features associated with images of known locations, comprising:

a general purpose computing device;

a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to,

generate query image features representative of the query image using the same technique as used to generate the database features resident in the database from the known location images;

for each feature associated with the query image, input the query image feature into an informative feature vocabulary tree and identify two or more visual words output by the vocabulary tree for that query image feature, wherein the informative feature vocabulary tree was generated using just those database features that have been deemed informative of the known locations and was used to assign visual words to each known location image that are output from the tree whenever a database feature associated with that image is input into the tree;

identify the known location image having the most visual words in common with the query image; and

designate the location associated with the identified known location image as the location depicted in the query image.

13. The system of claim 12, wherein the program module for inputting a query image feature into the informative feature vocabulary tree and identifying two or more visual words output by the tree for that query image feature, comprises sub-modules for:

(a) establishing a number of search paths N, wherein N is greater than 1;

(b) inputting the query feature into the root node of the informative feature vocabulary tree;

(c) computing the distance between the query feature and each child node of the root node;

(d) designating N child nodes having the closest computed distances to the query feature as candidate nodes for the next level of the informative feature vocabulary tree;

(e) designating the next level of the informative feature vocabulary tree to be the current level;

(f) computing the distance between the query feature and each child node of just the candidate nodes of the current level;

(g) repeating sub-modules (d) through (f) until the next level of the informative feature vocabulary tree in relation to the current level is the last level of the tree; and

(h) designating the visual words associated with the N child nodes having the closest computed distances to the query feature as the output of the informative feature vocabulary tree.

14. The system of claim 12, further comprising program modules for:

prior to generating the query image features,

generating an informative feature vocabulary tree using just those database features that have been deemed informative of the known locations,

for each database feature associated with each known location image, inputting the database feature into the informative feature vocabulary tree and identifying a single visual word output by the tree for that database feature, and

for each known location image, assigning the visual words identified from the database features associated with that image to that image.

15. The system of claim 14, wherein the program module for inputting the database feature into the informative feature vocabulary tree and identifying the single visual word output by the tree for that database feature, comprises sub-modules for:

(a) establishing a number of search paths N, wherein N is greater than 1;

(b) inputting the database feature into the root node of the informative feature vocabulary tree;

(c) computing the distance between the database feature and each child node of the root node;

(d) designating N child nodes having the closest computed distances to the database feature as candidate nodes for the next level of the informative feature vocabulary tree;

(e) designating the next level of the informative feature vocabulary tree to be the current level;

(f) computing the distance between the database feature and each child node of just the candidate nodes of the current level;

(g) repeating sub-modules (d) through (f) until the next level of the informative feature vocabulary tree in relation to the current level is the last level of the tree; and

(h) designating the visual word associated with the child node having the closest computed distance to the database feature as the output of the informative feature vocabulary tree.

16. The system of claim 12, wherein the program module for identifying the known location image having the most visual words in common with the query image, comprises sub-modules for:

employing a voting scheme wherein, for each feature of the query image which causes a visual word to be output from the informative feature vocabulary tree that matches a visual word assigned to a known location image, a count associated with that known location image is increased;

designating the known location image having the highest count as the known location image having the most visual words in common with the query image.

17. The system of claim 16, wherein the sub-module for employing a voting scheme, comprises, for each known location image, sub-modules for:

(a) establishing a count and initializing it with a value of zero;

(b) establishing a prescribed-sized neighborhood of known location images including the known location image under consideration;

(c) selecting a previously unselected known location image in the prescribed-sized neighborhood;

(d) selecting a previously unselected database feature associated with the selected known location image;

(e) selecting a previously unselected query image feature;

(f) determining if the selected query image feature causes a visual word to be output from the informative feature vocabulary tree which matches a visual word assigned to the selected known location image that was output from the informative feature vocabulary tree when the selected database feature was input;

(g) whenever the selected query image feature causes a visual word to be output from the informative feature vocabulary tree which matches a visual word assigned to the selected known location image that was output from the informative feature vocabulary tree when the selected database feature was input, incrementing the count by one divided by the sum of the number of times the visual word output by the informative feature vocabulary tree when the selected query feature is input is also output when a database feature is input, for every database feature of every known location image;

(h) repeating actions (e) through (g) until all the query image features have been selected;

(i) repeating actions (d) through (h) until all the database features associated with the selected known location image have been selected;

(j) dividing the count by the number of database features that are associated with the selected known location image;

(k) repeating actions (c) through (j) until all the known location images in the prescribed-sized neighborhood have been selected; and

(l) dividing the count by the number of known location images in the prescribed-sized neighborhood.

18. A system for searching a metric tree, comprising:

a general purpose computing device;

a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to,

(a) establish a number of search paths N, wherein N is greater than 1,

(b) input a query into the root node of the metric tree,

(c) computing the distance between the query and each child node of the root node,

(d) designating N child nodes having the closest computed distances to the query as candidate nodes for the next level of the metric tree,

(e) designating the next level of the metric tree to be the current level,

(f) computing the distance between the query and each child node of just the candidate nodes of the current level,

(g) repeating sub-modules (d) through (f) until the next level of the metric tree in relation to the current level is the last level of the tree, and

(h) designating the N child nodes having the closest computed distances to the query as the output of the metric tree.

19. The system of claim 18, wherein the number of search paths N is selected to maximize performance by minimizing the number of queries that result in an output from the metric tree that does not represent the closest last level node to a query.

20. The system of claim 18, wherein the metric tree is a vocabulary tree.