Method and system for matching an image using normalized feature vectors

• US 9,530,076 B2
• Filed: 02/16/2015
• Issued: 12/27/2016
• Est. Priority Date: 01/14/2009
• Status: Active Grant

• Current Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Original Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Inventors: Ruzon, Mark A., Manmatha, Raghavan, Tanguay, Donald
• Primary Examiner(s): Allison, Andrae S
• Application Number:
  US14/623,367
• Publication Number:
  US 20150161480A1
• Time in Patent Office: 680 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00
• CPC Class Codes: G06V 10/443 by matching or filtering
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]
• CPC Class Codes: G06V 10/758 Involving statistics of pixels or of feature values, e.g. histogram matching

Abstract

A method, system and computer program product for encoding an image is provided. The image that needs to be represented is represented in the form of a Gaussian pyramid which is a scale-space representation of the image and includes several pyramid images. The feature points in the pyramid images are identified and a specified number of feature points are selected. The orientations of the selected feature points are obtained by using a set of orientation calculating algorithms. A patch is extracted around the feature point in the pyramid images based on the orientations of the feature point and the sampling factor of the pyramid image. The boundary patches in the pyramid images are extracted by padding the pyramid images with extra pixels. The feature vectors of the extracted patches are defined. These feature vectors are normalized so that the components in the feature vectors are less than a threshold.

Claims

1. A computer-implemented method for matching a query image, comprising:

obtaining a request to match at least one portion of the query image to at least one respective portion of one or more of a plurality of database images;

identifying a plurality of features for at least one Gaussian pyramid image generated for the query image;

for each feature,

determining a patch encompassing the feature based at least in part upon one or more orientations for the feature and a sampling factor of the at least one Gaussian pyramid image;

determining components of a feature vector corresponding to a mini-patch obtained from dividing the patch, wherein the components comprise one or more of;

a sum of all positive x-derivatives of the at least one Gaussian pyramid image present in the mini-patch;

a negative of a sum of all negative x-derivatives of the at least one Gaussian pyramid image present in the mini-patch;

a sum of all positive y-derivatives of the at least one Gaussian pyramid image present in the mini-patch; and

a negative of a sum of all negative y-derivatives of the at least one Gaussian pyramid image present in the mini-patch;

normalizing the feature vector for the patch;

determining at least one matching image from among the plurality of database images based at least in part upon comparing feature vectors of each database image to one or more normalized feature vectors of the query image, each of the plurality of features corresponding to one of the normalized feature vectors; and

providing information relating to the at least one matching image in response to the request.

2. The computer-implemented method of claim 1, wherein the at least one Gaussian pyramid image is formed by down sampling the query image and blurring the query image by a Gaussian function, the Gaussian function being characterized by a scale parameter.

3. The computer-implemented method of claim 1, wherein identifying the plurality of features of the at least one Gaussian pyramid image includes:

determining a Harris corner measure for at least one pixel of the at least one Gaussian pyramid image having a local maxima.

4. The computer-implemented method of claim 3, further comprising:

selecting a subset of the plurality of features based at least in part upon a combination of the Harris corner measure and a scale parameter of the at least one Gaussian pyramid image.

5. The computer-implemented method of claim 3, further comprising:

determining a position of at least one feature of the plurality of feature by fitting an elliptic paraboloid to a region encompassing the at least one feature.

6. The computer-implemented method of claim 3, wherein the one or more orientations is determined from:

a plurality of orientations using a plurality of orientation calculating algorithms; and

using a subset of the plurality of orientations within an angular distance of each other with a mean of the plurality of orientations.

7. The computer-implemented method of claim 1, wherein the patch for at least one feature of the plurality of features present on a boundary of the at least one Gaussian pyramid image is extracted by padding the at least one Gaussian pyramid image with extra pixels.

8. The computer-implemented method of claim 1, wherein determining the patch encompassing the feature includes:

determining a plurality of positions based at least in part on the one or more orientations and the sampling factor of the at least one Gaussian pyramid image; and

sampling gradients of the at least one Gaussian pyramid image at the plurality of positions.

9. A system for matching a query image, comprising:

at least one processor; and

memory including instructions that, upon being executed by the at least one processor, cause the system to;

obtain a request to match at least one portion of the query image to at least one respective portion of one or more of a plurality of database images;

identify a plurality of features for at least one scaled image generated for the query image;

for each feature,

determine a patch encompassing the feature based at least in part upon one or more orientations for the feature and a sampling factor of the at least one scaled image;

determining components of a feature vector corresponding to a mini-patch obtained from dividing the patch, wherein the components comprise one or more of;

a sum of all positive x-derivatives of the at least one Gaussian pyramid image present in the mini-patch;

a negative of a sum of all negative x-derivatives of the at least one Gaussian pyramid image present in the mini-patch;

a sum of all positive y-derivatives of the at least one Gaussian pyramid image present in the mini-patch; and

a negative of a sum of all negative y-derivatives of the at least one Gaussian pyramid image present in the mini-patch;

normalize the feature vector for the patch;

determine at least one matching image from among the plurality of database images based at least in part upon comparing feature vectors of each database image to one or more normalized feature vectors of the query image, each of the plurality of features corresponding to one of the normalized feature vectors; and

provide information relating to the at least one matching image in response to the request.

10. The system of claim 9, wherein the instructions upon being executed that cause the system to normalize the feature vector for the patch includes causing the system to:

reduce each component of the feature vector having a value greater than a threshold to the threshold; and

normalize each component of the feature vector having a value less than the threshold to a calculated length, the calculated length being based at least in part upon the threshold and a number of components having values exceeding the threshold.

11. A non-transitory computer-readable storage medium matching a query image including instructions that, upon being executed by at least one processor of a computing device, cause the computing device to:

obtain a request to match at least one portion of the query image to at least one respective portion of one or more of a plurality of database images;

identify a plurality of features for the at least one scaled image generated for the query image;

for each feature,

determine a patch encompassing the feature based at least in part upon one or more orientations for the feature and a sampling factor of the at least one scaled image;

determining components of a feature vector corresponding to a mini-patch obtained from dividing the patch, wherein the components comprise one or more of;

a sum of all positive x-derivatives of the at least one Gaussian pyramid image present in the mini-patch;

a negative of a sum of all negative x-derivatives of the at least one Gaussian pyramid image present in the mini-patch;

a sum of all positive y-derivatives of the at least one Gaussian pyramid image present in the mini-patch; and

a negative of a sum of all negative y-derivatives of the at least one Gaussian pyramid image present in the mini-patch;

normalize the feature vector for the patch;

determine at least one matching image from among the plurality of database images based at least in part upon comparing feature vectors of each database image to one or more normalized feature vectors of the query image, each of the plurality of features corresponding to one of the normalized feature vectors; and

provide information relating to the at least one matching image in response to the request.

12. The non-transitory computer-readable storage medium of claim 11, wherein the instructions upon being executed that cause the computing device to identify the plurality of features of the at least one scaled image include causing the computing device to:

determine a Harris corner measure for at least one pixel of the at least one scaled image having a local maxima.

13. The non-transitory computer-readable storage medium of claim 12, wherein the instructions upon being executed further cause the computing device to:

select a subset of the plurality of features based at least in part upon a combination of the Harris corner measure and a scale parameter of the at least one scaled image.

14. The non-transitory computer-readable storage medium of claim 12, wherein the instructions upon being executed further cause the computing device to:

determine a position of each feature of the plurality of features by fitting an elliptic paraboloid to a region encompassing the feature.

15. The non-transitory computer-readable storage medium of claim 11, wherein the instructions upon being executed that cause the computing device to:

determine the one or more orientations from a plurality of orientations using a plurality of orientation calculating algorithms; and

using a subset of the plurality orientations within an angular distance of each other with a mean of the plurality of orientations.

16. The non-transitory computer-readable storage medium of claim 11, wherein the instructions upon being executed that cause the computing device to determine the patch encompassing the feature include causing the computing device to:

determine a plurality of positions based at least in part on the one or more orientations and the sampling factor of the at least one scaled image; and

sample gradients of the at least one scaled image at the plurality of positions.