GLOBAL VISUAL VOCABULARY, SYSTEMS AND METHODS

• US 20150262036A1
• Filed: 02/13/2015
• Published: 09/17/2015
• 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
• Granted Patent: US 9,922,270 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 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; 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 10, wherein the representative descriptor comprises at least one of a centroid of the cell and an average descriptor from the clustered region.

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

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

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

14. 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.

15. The system of claim 14, 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.

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

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

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

19. 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.

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