Systems and methods for image-feature-based recognition

• US 10,521,667 B2
• Filed: 03/20/2018
• Issued: 12/31/2019
• Est. Priority Date: 02/10/2014
• Status: Active Grant

• Current Assignee: Geenee GmbH
• Original Assignee: Geenee GmbH
• Inventors: Holzschneider, Philipp, Magers, Thorsten Otto Wolfgang, Priehn, Hannes
• Primary Examiner(s): Rudolph, Vincent
• Assistant Examiner(s): Schwartz, Raphael
• Application Number:
  US15/926,269
• Publication Number:
  US 20190034732A1
• Time in Patent Office: 651 Days
• 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/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 server for determining information relating to an image, the server comprising a processor for executing one or more modules comprising:

a query receiving module for receiving a query including a plurality of query image feature descriptors;

a candidate feature descriptors retrieval module for determining, within an address space associated with a plurality of first addresses determined from at least one of the query image feature descriptors, a number of duplicate reference image feature descriptors, wherein a plurality of duplicates of at least one reference image feature descriptor is mapped using a plurality of functions to at least one second address;

a candidate images retrieval module for selecting one or more reference image feature descriptors based on the determined number of duplicate reference image feature descriptors;

wherein, based on the selected reference image feature descriptors, the server is further configured to output information associated with the selected reference image feature descriptors.

2. The server of claim 1, wherein the processor is further configured to execute a hash table management module for:

providing, for each of the plurality of first addresses, one or more references to one or more of the reference image feature descriptors based on a relationship between each of the plurality of first addresses and the least one second address;

and wherein the number of duplicate reference image feature descriptors is determined based on the relationship.

3. The server of claim 2, wherein the hash table management module further comprises a collision resolving module for:

using a random function to calculate the at least one second address.

4. The server of claim 2, wherein the hash table management module further comprises an overflowing handling module for:

determining whether the at least one second address is associated with a first reference image feature descriptor when the at least one second address is calculated;

responsive to determining that the at least one second address is associated with the first reference image feature descriptor;

disassociating the at least one second address from the first reference image feature descriptor; and

associating the at least one second address with a second reference image feature descriptor.

5. The server of claim 1, wherein the processor is further configured to execute the candidate images retrieval module for:

ranking one or more sets of reference image feature descriptors, each set being associated with a combination of the determined numbers of duplicate reference image feature descriptors; and

selecting the set of reference image feature descriptors based on a result of the ranking.

6. The server of claim 1, wherein the processor is further configured to execute the candidate images retrieval module for:

excluding, from the selection of the one or more reference image feature descriptors, reference image feature descriptors associated with a calculated number of duplicate reference image feature descriptors that is below a predefined threshold.

7. The server of claim 1, wherein the reference image feature descriptors are stored based on a hash table including a plurality of hash buckets, each hash bucket being associated with an address within the address space;

wherein the plurality of functions are configured to map one or more feature descriptors to one or more hash buckets of a set of hash buckets.

8. The server of claim 1, wherein the processor is further configured to execute a replicable query cache module for:

determining whether the query image feature descriptors included in the query match with one or more prior query image feature descriptors received at a prior time;

if the query image feature descriptors included in the query do not match with the one or more prior query image feature descriptors;

storing the query image feature descriptors as part of the one or more prior query image feature descriptors, and

providing the query image feature descriptors to the candidate feature descriptors retrieval module;

and

if the query image feature descriptors included in the query match with the one or more prior query image feature descriptors, outputting information associated with the matching one or more prior query image feature descriptors.

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

receiving data associated with media material through an interface; and

outputting the data as part of the information associated with the selected reference image feature descriptors.

10. A computer-implemented method for determining information relating to an image, the method comprising:

receiving a query including a plurality of query image feature descriptors

determining, within an address space associated with a plurality of first addresses determined from at least one of the query image feature descriptors, a number of duplicate reference image feature descriptors, wherein a plurality of duplicates of at least one reference image feature descriptor is mapped using a plurality of functions to at least a second address;

selecting one or more reference image feature descriptors based on the determined number of duplicate reference image feature descriptors, and

outputting information associated with the selected reference image feature descriptors.

11. The method of claim 10, further comprising:

providing, for each of the plurality of first addresses, one or more references to one or more of the reference image feature descriptors based on a relationship between each of the plurality of first addresses and the least one second address;

and wherein the number of duplicate reference image feature descriptors is determined based on the relationship.

12. The method of claim 11, further comprising:

using a random function to calculate the at least one second address.

13. The method of claim 11, further comprising:

determining whether the at least one second address is associated with a first reference image feature descriptor when the at least one second address is calculated;

responsive to determining that the at least one first address is associated with the first reference image feature descriptor;

disassociating the at least one first address from the first reference image feature descriptor; and

associating the at least one first address with a second reference image feature descriptor.

14. The method of claim 10, further comprising:

ranking one or more sets of reference image feature descriptors, each set being associated with a combination of the determined numbers of duplicate reference image feature descriptors; and

selecting the set of reference image feature descriptors based on a result of the ranking.

15. The method of claim 10, further comprising:

excluding, from the selection of the one or more reference image feature descriptors, reference image feature descriptors associated with a calculated number of duplicate reference image feature descriptors that is below a predefined threshold.

16. The method of claim 10, wherein the reference image feature descriptors are stored based on a hash table including a plurality of hash buckets, each hash bucket being associated with an address within the address space;

wherein the plurality of functions are configured to map one or more feature descriptors to one or more hash buckets of a set of hash buckets.

17. The method of claim 10, further comprising:

determining whether the query image feature descriptors included in the query matches with one or more prior query image feature descriptors received at a prior time;

if the query image feature descriptors included in the query do not match with the one or more prior query image feature descriptors;

storing the query image feature descriptors as part of the one or more prior query image feature descriptors, and

providing the query image feature descriptors to the candidate feature descriptors retrieval module;

and

if the query image feature descriptors included in the query matches with the one or more prior query image feature descriptors, outputting information associated with the matching one or more prior query image feature descriptors.

18. The method of claim 10, further comprising:

receiving data associated with media material through an interface; and

outputting the data as part of the information associated with the selected reference image feature descriptors.

19. A non-transitory computer-readable storage medium having stored thereon a program containing instructions that, when executed by a computer, cause the computer to execute a method for determining information relating to an image, the method comprising:

receiving a query including a plurality of query image feature descriptors;

determining, within an address space associated with a plurality of first addresses determined from at least one of the query image feature descriptors, a number of duplicate reference image feature descriptors, wherein a plurality of duplicates of at least one reference image feature descriptor is mapped using a plurality of functions to at least a second address;

selecting one or more reference image feature descriptors based on the determined number of duplicate reference image feature descriptors; and

outputting information associated with the selected reference image feature descriptors.