Global visual vocabulary, systems and methods

• US 9,922,270 B2
• Filed: 02/13/2015
• Issued: 03/20/2018
• Est. Priority Date: 02/13/2014
• Status: Active Grant

• Current Assignee: Nant Holdings IP, LLC (NantWorks, LLC)
• Original Assignee: Nant Holdings IP, LLC (NantWorks, LLC)
• Inventors: Song, Bing, McKinnon, David
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): VANCHY JR, MICHAEL J
• Application Number:
  US14/622,621
• Publication Number:
  US 20150262036A1
• Time in Patent Office: 1,131 Days
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/41 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06F 18/2163 Partitioning the feature space
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06F 18/2413 based on distances to training or reference patterns
• CPC Class Codes: G06F 18/24147 Distances to closest patterns, e.g. nearest neighbour classification
• CPC Class Codes: G06F 18/28 Determining representative reference patterns, e.g. by averaging or distorting; Generating dictionaries
• CPC Class Codes: G06F 40/242 Dictionaries
• CPC Class Codes: G06V 10/774 Generating sets of training patterns; Bootstrap methods, e.g. bagging or boosting

Abstract

Systems and methods of generating a compact visual vocabulary are provided. Descriptor sets related to digital representations of objects are obtained, clustered and partitioned into cells of a descriptor space, and a representative descriptor and index are associated with each cell. Generated visual vocabularies could be stored in client-side devices and used to obtain content information related to objects of interest that are captured.

Claims

1. A global descriptor vocabulary system comprising:

a recognition module programmed to perform the step of obtaining a plurality of descriptor sets including descriptors associated with a plurality of digital representations of objects, each descriptor set existing within a descriptor space; and

a vocabulary generation engine coupled with the recognition module and programmed to perform the steps of;

obtaining the plurality of descriptor sets;

clustering the plurality of descriptor sets into regions within the descriptor space;

partitioning the descriptor space into a plurality of cells as a function of the clustered regions;

assigning an index to each cell of the plurality of cells as a function of a representative descriptor in each cell of the plurality of cells, the representative descriptor being derived from a selected actual descriptor from the plurality of descriptor sets that is closest to an average of all descriptors in a corresponding cell of the descriptor space, wherein each of the assigned indices is of a number of bytes selected based on the amount of cells comprising the plurality of cells; and

instantiating a global vocabulary module as a function of the assigned indices and representative descriptors and configured to generate a set of content indices that reference corresponding cells in the descriptor space based on an input set of descriptors.

2. The system of claim 1, wherein the plurality of descriptor sets comprise image descriptors.

3. The system of claim 1, wherein the plurality of descriptor sets comprise multi-modal descriptors.

4. The system of claim 1, wherein the plurality of descriptor sets comprise a homogenous mix of descriptors.

5. The system of claim 1, wherein the recognition module further comprises an invariant feature identification algorithm.

6. The system of claim 5, wherein the invariant feature identification algorithm comprises one of the following algorithms:

SIFT, FREAK, BRISK, and DAISY.

7. The system of claim 1, wherein the plurality of descriptor sets have their own descriptor space.

8. The system of claim 1, wherein the vocabulary generation engine is further programmed to perform the step of clustering the plurality of descriptor sets using at least one of hierarchal k-mean, approximate k-mean, k-means clustering, and histogram binning.

9. The system of claim 1, wherein the vocabulary generation engine is further programmed to perform the step of partitioning the descriptor space based on Voronoi decomposition.

10. The system of claim 1, wherein the representative descriptor is in the cell.

11. The system of claim 1, wherein the global vocabulary module comprises a vocabulary tree.

12. The system of claim 11, wherein the vocabulary tree comprises at least one of the following:

a k-nearest neighbor tree, a spill tree, and a k-d tree.

13. The system of claim 1, wherein the vocabulary module is further programmed to perform the step of generating the set of content indices using a nearest neighbor classification.

14. The system of claim 13, wherein the vocabulary module is further programmed to perform the step of calculating the nearest neighbor classification using at least one of a Euclidean distance and a Mahalanobis distance.

15. The system of claim 1, wherein each of the assigned indices is no more than six bytes.

16. The system of claim 15, wherein each of the assigned indices is no more than four bytes.

17. The system of claim 16, wherein each of the assigned indices is no more than three bytes.

18. The system of claim 1, wherein the global vocabulary module is further programmed to perform the step of constructing a query based on the input set of descriptors.

19. The system of claim 1, wherein the input set of descriptors comprise image descriptors.