Global visual vocabulary, systems and methods

• US 10,521,698 B2
• Filed: 07/20/2018
• Issued: 12/31/2019
• 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 Y
• Assistant Examiner(s): Vanchy, Jr., Michael J
• Application Number:
  US16/041,695
• Publication Number:
  US 20180330195A1
• Time in Patent Office: 529 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 system configured to obtain 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 system and configured to;

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

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

assign 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 one of the assigned indices comprises a cell address string selected as a function of an amount of cells comprising the plurality of cells; and

instantiate a global vocabulary system as a function of the assigned indices and representative descriptors such that the global vocabulary system is 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 comprises image descriptors.

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

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

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

6. The system of claim 5, wherein the invariant feature identification algorithm comprises at least one of a SIFT, FREAK, BRISK, and DAISY algorithm.

7. The system of claim 1, wherein the plurality of descriptor sets has its own descriptor space.

8. The system of claim 1, wherein the vocabulary generation engine is further configured to cluster 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 configured to partition 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 system comprises a vocabulary tree.

12. The system of claim 11, wherein the vocabulary tree comprises at least one of a k-nearest neighbor tree, a spill tree, and a k-d tree.

13. The system of claim 1, wherein the vocabulary system 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 system is further configured to calculate the nearest neighbor classification using at least one of a Euclidean distance and a Mahalanobis distance.

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

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

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

18. The system of claim 1, wherein the global vocabulary system is further configured to construct a query based on the input set of descriptors.

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

20. A non-transitory computer-readable medium having computer instructions stored thereon for instantiating a global vocabulary system, which, when executed by a processor, cause the processor to perform one or more steps comprising:

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;

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 one of the assigned indices comprises a cell address string selected as a function of an amount of cells comprising the plurality of cells; and

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

21. A method of instantiating a global vocabulary system, the method comprising:

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;

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 one of the assigned indices comprises a cell address string selected as a function of an amount of cells comprising the plurality of cells; and

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