Systems and methods for image-feature-based recognition

• US 9,230,172 B2
• Filed: 04/21/2015
• Issued: 01/05/2016
• Est. Priority Date: 02/10/2014
• Status: Active Grant

• Current Assignee: Geenee GmbH
• Original Assignee: Geenee Ug
• Inventors: Holzschneider, Philipp, Magers, Thorsten Otto Wolfgang, Priehn, Hannes
• Primary Examiner(s): Mehta, Bhavesh
• Assistant Examiner(s): SCHWARTZ, RAPHAEL M
• Application Number:
  US14/692,234
• Publication Number:
  US 20150227796A1
• Time in Patent Office: 259 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/51 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 18/213 Feature extraction, e.g. by transforming the feature space; Summarisation; Mappings, e.g. subspace methods
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G06V 10/7715 Feature extraction, e.g. by transforming the feature space, e.g. multi-dimensional scaling [MDS]; Mappings, e.g. subspace methods
• CPC Class Codes: G06V 20/20 in augmented reality scenes

Abstract

Methods and systems are described herein that allow a user to capture a single image snapshot from video, print, or the world around him or her, and obtain additional information relating to the media itself or items of interest displayed in the snapshot. A fingerprint of the snapshot is used as a query and transmitted to the server. Image Feature-Based Recognition, as described herein, uses a feature index to identify a smaller set of candidate matches from a larger database of images based on the fingerprint. Novel methods and systems using a distance metric and a radical hash table design exploit probabilistic effects and allow distinct image features to be preferred over redundant ones, allowing only the more distinctive data points to remain resident within the index, yielding a lean index that can be quickly used in the identification process.

Claims

1. A device for identifying and displaying additional information relating to an item of interest, the device comprising a processor for executing one or more modules comprising:

an image acquisition module for acquiring a first query image including the item of interest;

a feature descriptor generation module for extracting a plurality of first query image feature descriptors associated with the first query image;

a fingerprint generation module for;

generating a first query fingerprint based on the extracted first query image feature descriptors; and

transmitting the first query fingerprint to a server, wherein the first query fingerprint enables the server to perform, based on the first query fingerprint, a similarity search in a database storing a plurality of reference image feature descriptors and to acquire one or more candidate images associated with at least one of the reference image feature descriptors retrieved from the database by mapping the query feature descriptors to addresses, or adjacent addresses, to which reference image feature descriptors are most frequently mapped; and

an image matching module for determining whether the first query image matches with at least one of the one or more candidate images;

wherein the determination at the image matching module enables acquisition of additional information associated with at least one of the one or more candidate images for displaying as additional information relating to the at least one item of interest to the user.

2. The device of claim 1, wherein the processor is further configured to execute the image matching module for:

estimating a first set of relative positions between the first query image feature descriptors;

for at least one of the one or more candidate images;

determining a set of corresponding reference image feature descriptors that correspond to the first query image feature descriptors;

calculating a second set of relative positions between the set of corresponding feature descriptors; and

determining a degree of fit between the first query image and the candidate image based on a relationship between the first set of relative positions and the second set of relative positions;

wherein the determination of whether the first query image matches with at least one of the one or more candidate images is based on the determined degree of fit.

3. The device of claim 2, wherein the determining of the set of corresponding feature descriptors that correspond to the first query image feature descriptors comprises calculating one or more feature distances between one or more reference image feature descriptors and the first query image feature descriptors.

4. The device of claim 2, wherein the device is further configured to perform the steps of:

determining a first pose of the first query image based on the first set of relative positions;

comparing the first pose with a second pose associated with a previously acquired query image;

based on a result of the comparison, determining whether a tracking is lost; and

when it is determined that a tracking is lost;

causing the image acquisition module to acquire a second query image;

causing the feature descriptor generation module to extract a plurality of second query image feature descriptors associated with the second query image; and

causing the fingerprint generation module to;

generate a second query fingerprint based on the extracted second query image feature descriptors; and

transmit the second query fingerprint to the server.

5. The device of claim 1, wherein the processor is further configured to execute the image acquisition module for:

acquiring a plurality of images;

associating each of the acquired plurality of images with each of a plurality of first timestamps;

detecting an initiation to take a snapshot;

associating the initiation with a second timestamp; and

selecting an image out of the plurality of images as the first query image based on a relationship between each of the plurality of first timestamps and the second timestamp.

6. The device of claim 5, wherein the processor is further configured to execute the image acquisition module for detecting a motion of the device;

wherein the selection of the image out of the plurality of images as the first query image is also based on the detected motion.

7. The device of claim 1, further comprising:

a query cache for storing a mapping between one or more previously-received query fingerprints and one or more previously-acquired candidate images; and

a query cache management module for determining whether the first query fingerprint matches with any of the one or more previously-received query fingerprints stored in the query cache;

wherein, if the query cache management module determines that the first query fingerprint matches with at least one of the one or more previously-received query fingerprints stored in the query cache, the device is further configured to perform the steps of;

determining not to transmit the first query fingerprint to the server; and

causing the image matching module to determine whether the first query image matches with any of the previously-acquired candidate images.

8. The device of claim 7, wherein, if the query cache management module determines that the first query fingerprint matches with none of the one or more previously-receive query fingerprints stored in the query cache, the device is further configured to perform the step of:

after the image matching module determines that the first query image matches with at least one of the one or more candidate images, adding a mapping between the first query fingerprint and the one or more candidate images to the query cache.

9. The device of claim 1, wherein the device is further configured to perform the steps of:

providing an interface to receive a selection of a portion of the first query image; and

causing the feature descriptor generation module to extract the first query image feature descriptors associated with the selected portion of the first query image.

10. The device of claim 1, wherein the device is further configured to perform the steps of:

providing an interface to receive a selection of a portion of the first query image; and

causing the additional database module to acquire the additional information based on the selection.

11. The device of claim 1, wherein at least one reference image feature descriptor is mapped, with a plurality of functions, to a plurality of addresses within an address space in the database;

and wherein the plurality of functions is configured to map one or more feature descriptors to the same address space.

12. The device of claim 11, wherein the similarity search includes determining a number of duplicate reference image feature descriptors within a pre-defined region of the database, wherein the pre-defined region of the database is associated with one or more addresses calculated from the first query image feature descriptors included in the first query fingerprint using the plurality of functions.

13. A computer-implemented method for identifying and displaying additional information relating to an image obtained by a user with a mobile device, the method being implemented by the mobile device and comprising:

acquiring a first query image comprising at least one item of interest to the user about which additional information is to be displayed;

extracting a plurality of first features from the first query image, wherein the first features correspond to the at least one item of interest;

generating a first query, wherein the first query includes the extracted first features;

transmitting the first query to a server, wherein the first query enables the server to acquire one or more reference images by mapping the query feature descriptors to addresses, or adjacent addresses, to which reference image feature descriptors are most frequently mapped and to determine, based on the one or more reference images acquired based on the first query, that the server stores additional information about the at least one item of interest; and

receiving, from the server, the additional information about the at least one item of interest; and

displaying the additional information about the at least one item of interest to the user.

14. The computer-implemented method of claim 13, further comprising:

receiving, via an interface on the mobile device, a user'"'"'s selection of a portion of the first query image;

wherein extracting a plurality of first features from the first query image comprises extracting a plurality of first features corresponding to the selected portion; and

wherein generating a first query comprises generating a first query representing the extracted first features corresponding to the selected portion.

15. The computer-implemented method of claim 13, further comprising:

storing the extracted first features;

acquiring a second query image;

extracting a plurality of second features from the second query image;

determining a relationship between the stored first features and the extracted second features; and

based on the relationship, determining not to transmit a second query including information representing the extracted second features to the server.

16. The computer-implemented method of claim 13, wherein the acquired one or more reference images are associated with a plurality of second features;

wherein duplicates of at least one of the second features are stored within a pre-defined region associated with an address calculated from the first features.