Scalable image matching

• US 9,582,735 B2
• Filed: 03/07/2016
• Issued: 02/28/2017
• Est. Priority Date: 12/18/2013
• Status: Expired due to Fees

• 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 JUNG
• Application Number:
  US15/063,050
• Publication Number:
  US 20160189000A1
• Time in Patent Office: 358 Days
• Field of Search: 382/160
• US Class Current: 1/1
• 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 computer-implemented method, comprising:

matching a plurality of training images against a database of images using one or more training features associated with the plurality of training images;

receiving one or more matching images from the database of images, wherein each matching image includes a plurality of correspondences with the one or more training features from the plurality of training images;

labeling a first subset of the plurality of correspondences as inlier correspondences and a second subset of the plurality of correspondences as outlier correspondences;

determining a first set of characteristics of the first subset of the plurality of correspondences;

determining a second set of characteristics of the second subset of the plurality of correspondences;

training one or more classifiers using the first set of characteristics and the second set of characteristics to generate a prediction model, wherein the prediction model is used at runtime to determine matching scores for the database of images in response to a query image;

ranking the database of images by comparing features from the query image to a set of compressed cluster centers corresponding to a set of closest matching database images; and

adjusting the ranking of the set of closest matching database images using the prediction model, wherein adjusting the ranking of the set of closest matching database images includes determining whether a respective compressed cluster center is an inlier or an outlier using the one or more classifiers.

2. The computer-implemented method of claim 1, wherein the prediction model includes a support vector machine model which represents the one or more training features as points in space, and wherein features extracted from the query image are mapped into the space to predict whether a subset of images from the database of images match the query image.

3. The computer-implemented method of claim 1, wherein the one or more training features are extracted using an Accumulated Signed Gradient (ASG) algorithm.

4. The computer-implemented method of claim 3, wherein training the one or more classifiers includes computing one or more parameters based on the first set of characteristics and the second set of characteristics, the one or more parameters including weight values applied to the one or more training features extracted using the ASG algorithm.

5. The computer-implemented method of claim 4, wherein a linear combination of the weight values and feature values corresponding to the one or more training features is determined and compared to a threshold value.

6. The computer-implemented method of claim 1, wherein the one or more classifiers use at least one of a scale difference or consistent orientation as an additional input for reranking the set of closest matching inventory images.

7. A computing system, comprising:

a processor; and

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

match a plurality of training images against a database of images using one or more training features associated with the plurality of training images;

receive one or more matching images from the database of images, wherein each matching image includes a plurality of correspondences with the one or more training features from the plurality of training images;

label a first subset of the plurality of correspondences as inlier correspondences and a second subset of the plurality of correspondences as outlier correspondences;

determine a first set of characteristics of the first subset of the plurality of correspondences;

determine a second set of characteristics of the second subset of the plurality of correspondences; and

train one or more classifiers using the first set of characteristics and the second set of characteristics to generate a prediction model, wherein the prediction model is used at runtime to determine matching scores for the database of images in response to a query image;

rank the database of images by comparing features from the query image to a set of compressed cluster centers corresponding to a set of closest matching database images; and

adjust the ranking of the set of closest matching database images using the prediction model, wherein adjusting the ranking of the set of closest matching database images includes determining whether a respective compressed cluster center is an inlier or an outlier using the one or more classifiers.

8. The computing system of claim 7, wherein the prediction model includes a support vector machine model which represents the one or more training features as points in space, and wherein features extracted from the query image are mapped into the space to predict whether a subset of images from the database of images match the query image.

9. The computing system of claim 7, wherein the one or more training features are extracted using an Accumulated Signed Gradient (ASG) algorithm.

10. The computing system of claim 9, wherein training the one or more classifiers includes computing one or more parameters based on the first set of characteristics and the second set of characteristics, the one or more parameters including weight values applied to the one or more training features extracted using the ASG algorithm.

11. The computing system of claim 10, wherein a linear combination of the weight values and feature values corresponding to the one or more training features is determined and compared to a threshold value.

12. The computing system of claim 7, wherein the one or more classifiers use at least one of a scale difference or consistent orientation as an additional input for reranking the set of closest matching inventory images.

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

match a plurality of training images against a database of images using one or more training features associated with the plurality of training images;

receive one or more matching images from the database of images, wherein each matching image includes a plurality of correspondences with the one or more training features from the plurality of training images;

label a first subset of the plurality of correspondences as inlier correspondences and a second subset of the plurality of correspondences as outlier correspondences;

determine a first set of characteristics of the first subset of the plurality of correspondences;

determine a second set of characteristics of the second subset of the plurality of correspondences; and

train one or more classifiers using the first set of characteristics and the second set of characteristics to generate a prediction model, wherein the prediction model is used at runtime to determine matching scores for the database of images in response to a query image;

rank the database of images by comparing features from the query image to a set of compressed cluster centers corresponding to a set of closest matching database images; and

adjust the ranking of the set of closest matching database images using the prediction model, wherein adjusting the ranking of the set of closest matching database images includes determining whether a respective compressed cluster center is an inlier or an outlier using the one or more classifiers.

14. The non-transitory computer readable storage medium of claim 13, wherein the prediction model includes a support vector machine model which represents the one or more training features as points in space, and wherein features extracted from the query image are mapped into the space to predict whether a subset of images from the database of images match the query image.

15. The non-transitory computer readable storage medium of claim 13, wherein the one or more training features are extracted using an Accumulated Signed Gradient (ASG) algorithm.

16. The non-transitory computer readable storage medium of claim 15, wherein training the one or more classifiers includes computing one or more parameters based on the first set of characteristics and the second set of characteristics, the one or more parameters including weight values applied to the one or more training features extracted using the ASG algorithm.

17. The non-transitory computer readable storage medium of claim 13, wherein the one or more classifiers use at least one of a scale difference or consistent orientation as an additional input for reranking the set of closest matching inventory images.