Scalable image matching

• US 10,140,549 B2
• Filed: 02/27/2017
• Issued: 11/27/2018
• Est. Priority Date: 12/18/2013
• Status: Active Grant

• Current Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Original Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Inventors: Dube, Simant, Ramesh, Sunil, Lin, Xiaofan, Dhua, Arnab Sanat Kumar, Taylor, Colin Jon, Pillai, Jaishanker K.
• Primary Examiner(s): Couso, Yon
• Application Number:
  US15/443,730
• Publication Number:
  US 20170177976A1
• Time in Patent Office: 638 Days
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• 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/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06F 18/24 Classification techniques
• CPC Class Codes: G06F 18/2411 based on the proximity to a decision surface, e.g. support vector machines
• CPC Class Codes: G06F 18/24147 Distances to closest patterns, e.g. nearest neighbour classification
• CPC Class Codes: G06F 18/2415 based on parametric or probabilistic models, e.g. based on likelihood ratio or false acceptance rate versus a false rejection rate
• CPC Class Codes: G06F 18/2433 Single-class perspective, e.g. one-against-all classification; Novelty detection; Outlier detection
• CPC Class Codes: G06F 2218/08 Feature extraction
• CPC Class Codes: G06V 10/464 using a plurality of salient features, e.g. bag-of-words [BoW] representations
• CPC Class Codes: G06V 10/757 Matching configurations of points or features
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects
• CPC Class Codes: G06V 2201/06 Recognition of objects for industrial automation
• CPC Class Codes: H04N 19/426 using memory downsizing methods
• CPC Class Codes: H04N 19/90 using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals

Abstract

Various embodiments may increase scalability of image representations stored in a database for use in image matching and retrieval. For example, a system providing image matching can obtain images of a number of inventory items, extract features from each image using a feature extraction algorithm, and transform the same into their feature descriptor representations. These feature descriptor representations can be subsequently stored and used to compare against query images submitted by users. Though the size of each feature descriptor representation isn'"'"'t particularly large, the total number of these descriptors requires a substantial amount of storage space. Accordingly, feature descriptor representations are compressed to minimize storage and, in one example, machine learning can be used to compensate for information lost as a result of the compression.

Claims

1. A computing system, comprising:

a processor; and

memory including instructions that, when executed by the processor, cause the computing system to;

receive a query image from a client computing device;

extract feature descriptors from the query image;

compare at least a portion of the extracted feature descriptors to a set of compressed cluster centers corresponding to a set of database images to determine a matching score, the compressed cluster centers at least partially formed by a set of compressed descriptors storing identifying information for at least one associated feature, the identifying information corresponding to identifying information including at least one of a position, a scale, or an orientation, and the identifying information occupying a majority of a file size of the compressed descriptor, wherein each of the compressed cluster centers is assigned at least one visual word corresponding to at least one feature descriptor;

rank the set of database images based on the matching score; and

select a highest ranking database image of the set of closest matching database images as a match for the query image.

2. The computing system of claim 1, wherein the instructions, when executed by the processor, further cause the computing system to:

assign a plurality of visual words to each of the compressed cluster centers, the plurality of visual words corresponding to a plurality of feature descriptors associated with a respective compressed cluster center.

3. The computing system of claim 1, wherein the instructions, when executed by the processor, further cause the computing system to:

determine at least one compressed cluster center by clustering database feature descriptors for each of the set of database images into clusters, assigning a cluster center to represent each respective cluster, and compressing data of each cluster center.

4. The computing system of claim 3, wherein the matching score is determined using parameters from a machine learned process, the parameters produced by the machine learning process using one or more training images to at least partially compensate for inaccuracy caused by compressing the cluster center.

5. The computing system of claim 1, wherein the instructions, when executed by the processor, further cause the computing system to:

assign visual words to the feature descriptors of the query image; and

search, using the visual words assigned to the query image, a plurality of database visual words to identify a set of closest matching database images that at least partially match the query image.

6. The computing system of claim 5, wherein the plurality of visual words are organized in an index comprising each visual word and corresponding database images.

7. The computing system of claim 6, wherein the index is a Lucene index and the visual words of the plurality of database images are searched using a term frequency-inverse document frequency (tf-idf) weighting.

8. A computer-implemented method, comprising:

receiving a query image from a client computing device;

extracting feature descriptors from the query image;

comparing at least a portion of the extracted feature descriptors to a set of compressed cluster centers corresponding to a set of database images to determine a matching score, wherein each of the compressed cluster centers is assigned at least one visual word corresponding to at least one feature descriptor, and the compressed cluster center is at least partially formed by a set of compressed descriptors storing identifying information for at least one associated feature of the compressed cluster center, the identifying information including at least one of a position, a scale, or an orientation, and the identifying information occupying a majority of a file size of the compressed descriptor;

ranking the set of database images based on the matching score; and

selecting a highest ranking database image of the set of closest matching database images as a match for the query image.

9. The computer-implemented method of claim 8, further comprising:

assigning a plurality of visual words to each of the compressed cluster centers, the plurality of visual words corresponding to a plurality of feature descriptors associated with a respective compressed cluster center.

10. The computer-implemented method of claim 8, further comprising:

determining at least one compressed cluster center by clustering database feature descriptors for each of the set of database images into clusters, assigning a cluster center to represent each respective cluster, and compressing data of each cluster center.

11. The computer-implemented method of claim 10, wherein the matching score is determined using parameters from a machine learned process, the parameters produced by the machine learning process using one or more training images to at least partially compensate for inaccuracy caused by compressing the cluster center.

12. The computer-implemented method of claim 8, further comprising:

assigning visual words to the feature descriptors of the query image; and

searching, using the visual words assigned to the query image, a plurality of database visual words to identify a set of closest matching database images that at least partially match the query image.

13. The computer-implemented method of claim 12, wherein the plurality of visual words are organized in an index comprising each visual word and corresponding database images.

14. The computer-implemented method of claim 13, wherein the index is a Lucene index and the visual words of the plurality of database images are searched using a term frequency-inverse document frequency (tf-idf) weighting.

15. A non-transitory computer readable storage medium including instructions stored thereon which, when executed by a processor, cause the processor to:

receive a query image from a client computing device;

extract feature descriptors from the query image;

compare at least a portion of the extracted feature descriptors to a set of compressed cluster centers corresponding to a set of database images to determine a matching score, wherein each of the compressed cluster centers is assigned at least one visual word corresponding to at least one feature descriptor, and the compressed cluster center is at least partially formed by a set of compressed descriptors storing identifying information for at least one associated feature of the compressed cluster center, the identifying information occupying a majority of a file size of the compressed descriptor;

rank the set of database images based on the matching score; and

select a highest ranking database image of the set of closest matching database images as a match for the query image.

16. The non-transitory computer readable storage medium of claim 15, wherein the instructions, when executed by the processor, further cause the processor to:

assign a plurality of visual words to each of the compressed cluster centers, the plurality of visual words corresponding to a plurality of feature descriptors associated with a respective compressed cluster center.

17. The non-transitory computer readable storage medium of claim 15, wherein the instructions, when executed by the processor, further cause the processor to:

determine at least one compressed cluster center by clustering database feature descriptors for each of the set of database images into clusters, assigning a cluster center to represent each respective cluster, and compressing data of each cluster center.

18. The non-transitory computer readable storage medium of claim 17, wherein the matching score is determined using parameters from a machine learned process, the parameters produced by the machine learning process using one or more training images to at least partially compensate for inaccuracy caused by compressing the cluster center.

19. The non-transitory computer readable storage medium of claim 15, wherein the instructions, when executed by the processor, further cause the processor to:

assign visual words to the feature descriptors of the query image; and

search, using the visual words assigned to the query image, a plurality of database visual words to identify a set of closest matching database images that at least partially match the query image.

20. The non-transitory computer readable storage medium of claim 19, wherein the plurality of visual words are organized in an index comprising each visual word and corresponding database images, wherein the index is a Lucene index and the visual words of the plurality of database images are searched using a term frequency-inverse document frequency (tf-idf) weighting.