Visual Localization Method

• US 20130288702A1
• Filed: 05/16/2011
• Published: 10/31/2013
• Est. Priority Date: 08/10/2010
• Status: Active Grant

• Current Assignee: NavVis GmbH
• Original Assignee: Technische Universitat Munchen
• Inventors: Schroth, Georg, Schweiger, Florian, Steinbach, Eckehard, Abu-Alqumsan, Mohammad, Al-Nuaimi, Anas, Huitl, Robert
• Granted Patent: US 9,641,981 B2
• Time in Patent Office: Days
• US Class Current: 455/456.1
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/51 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06Q 30/0623 Item investigation
• CPC Class Codes: H04W 4/025 using location based information parameters

Abstract

There is provided a visual localization method comprising: (a) transmitting data representative of one or more detected visual features from a mobile device to a server; (b) estimating the location of the mobile device at the server based on the visual features 5 received from the mobile device; (c) transmitting reference data associated with the estimated location from the server to the mobile device; and (d) the mobile device determining its location based on the reference data received from the server.

Claims

1. A visual localization method comprising:

(a) a server maintaining reference data that can be associated with a plurality of possible locations of a mobile device;

(b) determining a subset of the reference data;

(c) transmitting the subset of the reference data from the server to the mobile device; and

(d) the mobile device determining its location based on the reference data received from the server.

2. The method of claim 1, wherein step (b) is performed on the basis of at least one of data received from the mobile device representative of one or more visual features and information indicative of an approximate position of the mobile device, in order to carry out at least one of the steps of:

enabling the server to estimate one or more locations of the mobile device and to select the subset of the reference data associated with the estimated locations of the mobile device, and;

quantizing the visual features into visual words.

3. The method claim 2, wherein said reference data includes at least one of visual words corresponding to the nodes of a binary search tree and quantizers to obtain said visual words, and at least one inverted file associated with the at least one of the visual words and quantizers, wherein at least one of the following conditions is met:

visual words represent visual words into which said visual features from the mobile device have been quantized, and visual words are selected from a visual vocabulary based on an estimated location of the mobile device such that the visual words represent visual features in a vicinity of the estimated location.

4. The method of claim 1, further comprising repeating steps (b), (c) and (d) periodically, and in particular repeating step (d) more frequently than steps (b) and (c).

5. The method of claim 4, further comprising updating a priority queue of visual words when new information relating to the location of the mobile device has become available to the server, in particular when a new detected visual feature is received by the server, the priority queue reflecting a probability that features of a following query frame are quantized to the visual words in the priority queue.

6. The method of claim 5, further comprising successively transmitting at least one of visual words and quantizers to the mobile device in accordance with their order in the priority queue.

7. The method of claim 5, further comprising adding visual words associated with locations adjacent to estimated locations of the mobile device to the priority queue.

8. The method of claim 1, further comprising:

electronically storing a plurality of images in a database, wherein each of the stored images is associated with a location, and wherein each of the stored images is representable by a reference vector indicative of a frequency of visual words in the respective image;

determining descriptors corresponding to visual features in the plurality of stored images;

generating a quantizer for generating visual words from visual features, said quantizer comprising a binary search tree generated by quantizing the descriptors to obtain a plurality of visual words corresponding to nodes of the binary search tree, comprising;

determining a hyperplane for each node to separate the child nodes of the respective node; and

storing descriptors that are within a distance from the hyperplane of a node in an overlapping buffer associated with that node;

for a given node, terminating the quantization when reaching a predetermined quantization threshold.

9. The method of claim 8, further comprising:

the mobile device providing one or more video frames including visual features representing a query image of a location to be recognized;

determining descriptors corresponding to said visual features in the query image;

quantizing said descriptors to obtain a plurality of visual words using said binary search tree; and

using an inverted file index to determine an image in the database that contains said visual words and the location associated with that image.

10. The method of claim 8, wherein the predetermined quantization threshold is reached when there is only a single cluster of descriptors in the given node defined by a predetermined portion of descriptors that has been stored in the overlapping buffer associated with the given node.

11. The method of claim 8, further comprising:

segmenting a region in which visual localization is to be performed into a plurality of overlapping sub-regions;

generating a respective quantizer for generating visual words from visual features, said respective quantizer comprising a binary sub-tree, for each of the sub-regions, thereby providing a plurality of respective quantizers;

generating a respective inverted file index for each of the sub-regions;

performing an approximation of the location of the mobile device;

identifying one or more sub-regions based on the approximation;

performing the visual localization in each of the identified sub-regions to obtain respective similarity measures;

fusing the results of the visual localization results in each of the sub-regions to determine the location of the mobile device.

12. The method of claim 11, comprising:

pre-selecting a predetermined number of best similarity measures obtained through each of the sub-trees;

from the pre-selected similarity measures, selecting the similarity measures corresponding to locations that have been obtained through at least two sub-trees;

for the selected similarity measures, determining a mean of the similarity measures based on the two or more most similar measures;

dividing the mean similarity measure of every location by the number of sub-trees pointing to this or adjacent locations; and

returning a number of locations with the best corresponding scores, wherein said reference data is associated with each of those locations.

13. The method of claim 8, comprising:

smoothing the results of the visual localization by applying a fraction of a similarity measure of a location to nearby locations, wherein the fraction of the similarity measure applied depends on a geographic distance between the location and a respective nearby location; and

computing a smoothed similarity measure for each location by accumulating the fractions.

14. The method of claim 8, comprising:

determining a distance between a query vector representative of the frequency of visual words in the query image and said reference vectors;

weighting a contribution of visual words to a difference between said query vector and said reference vector, wherein the weighting is performed in accordance with at least one of the following;

the probability that a query descriptor is allocated to the same visual word as a corresponding descriptor in the database, and

the reliability of a query descriptor,

wherein said probability can be determined based on a distribution of said distance between the query vector and the reference vectors.

15. A non-transitory computer readable medium configured to cause a processor-based system to perform the method of claim 1.

16. The method of claim 2, wherein the information indicative of an approximate position of the mobile device is a cell ID.

17. The method of claim 6, further comprising:

not transmitting visual words or quantizers that have previously been transmitted.

18. The method of claim 14, wherein the distribution is a Laplacian distribution.