Method and system for matching an image using normalized feature vectors

• US 9,721,182 B2
• Filed: 12/21/2016
• Issued: 08/01/2017
• 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:
  US15/387,314
• Publication Number:
  US 20170103282A1
• Time in Patent Office: 223 Days
• Field of Search: None
• 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, comprising:

obtaining a request to match a query image to at least one of a plurality of database images;

generating a Gaussian pyramid image for the query image;

analyzing the Gaussian pyramid image to identity a feature represented in the Gaussian pyramid image;

determining an orientation of the feature;

determining a patch encompassing the feature based at least in part upon the orientation and a sampling factor associated with the Gaussian pyramid image;

determining a feature vector for the patch;

dividing the patch into a plurality of sub patches;

determining components of the feature vector corresponding to a sub patch of the plurality of sub patches;

reducing the components associated with a value greater than a threshold to determine a reduced set of components;

normalizing components of the reduced set of components associated with respective values less than the threshold to a calculated length to generate a normalized feature vector, the calculated length being based at least in part upon the threshold and a number of components having values exceeding the threshold; and

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 the normalized feature vector.

2. The computer-implemented method of claim 1, wherein the Gaussian pyramid image is formed by downsampling 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, further comprising:

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

identifying the feature of a plurality of features.

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 respective Harris corner measures of the plurality of features and a scale parameter of the Gaussian pyramid image.

5. The computer-implemented method of claim 1, wherein determining the orientation includes:

determining a plurality of orientations for the feature by using a plurality of orientation calculating algorithms; and

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

6. The computer-implemented method of claim 1, wherein the patch encompassing the feature present on a boundary of the Gaussian pyramid image is extracted by padding the Gaussian pyramid image with extra pixels.

7. 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 orientation and the sampling factor of the Gaussian pyramid image; and

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

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

determining a position of the feature by fitting an elliptic paraboloid to a region encompassing the feature.

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

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

10. The computer-implemented method of claim 1, wherein components of the feature vector corresponding to the sub patch comprise:

a first component comprising a sum of all positive x-derivatives of the Gaussian pyramid image present in the sub patch;

a second component comprising a negative of a sum of all negative x-derivatives of the Gaussian pyramid image present in the sub patch;

a third component comprising a sum of all positive y-derivatives of the Gaussian pyramid image present in the sub patch; and

a fourth component comprising a negative of a sum of all negative y-derivatives of the Gaussian pyramid image present in the sub patch.

11. A system, 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 a query image to at least one of a plurality of database images;

generate a Gaussian pyramid image for the query image;

analyze the Gaussian pyramid image to identity a feature represented in the Gaussian pyramid image;

determine an orientation of the feature;

determine a patch encompassing the feature based at least in part upon the orientation and a sampling factor associated with the Gaussian pyramid image;

determine a feature vector for the patch;

divide the patch into a plurality of sub patches;

determine components of the feature vector corresponding to a sub patch of the plurality of sub patches;

reduce the components associated with a value greater than a threshold to determine a reduced set of components;

normalize components of the reduced set of components associated with respective values less than the threshold to a calculated length to generate a normalized feature vector, the calculated length being based at least in part upon the threshold and a number of components having values exceeding the threshold; and

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 the normalized feature vector.

12. The system of claim 11, wherein the instructions when executed further enable the system to:

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

identifying the feature of a plurality of features.

13. The system of claim 12, wherein the instructions when executed further enable the system to:

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

14. The system of claim 11, wherein components of the feature vector corresponding to the sub patch comprise:

a first component comprising a sum of all positive x-derivatives of a scaled image present in the sub patch;

a second component comprising a negative of a sum of all negative x-derivatives of the scaled image present in the sub patch;

a third component comprising a sum of all positive y-derivatives of the scaled image present in the sub patch; and

a fourth component comprising a negative of a sum of all negative y-derivatives of the scaled image present in the sub patch.

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

generate a Gaussian pyramid image for the query image;

analyze the Gaussian pyramid image to identity a feature represented in the Gaussian pyramid image;

determine an orientation of the feature;

determine a patch encompassing the feature based at least in part upon the orientation and a sampling factor associated with the Gaussian pyramid image;

determine a feature vector for the patch;

divide the patch into a plurality of sub patches;

determine components of the feature vector corresponding to a sub patch of the plurality of sub patches;

reduce the components associated with a value greater than a threshold to determine a reduced set of components;

normalize components of the reduced set of components associated with respective values less than the threshold to a calculated length to generate a normalized feature vector, the calculated length being based at least in part upon the threshold and a number of components having values exceeding the threshold; and

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 the normalized feature vector.

16. The non-transitory computer-readable storage medium of claim 15, wherein the instructions when executed further enable the computing device to:

determine a Harris corner measure for at least one pixel of the Gaussian pyramid image having a local maxima; and

identify the feature of a plurality of features.

17. The non-transitory computer-readable storage medium of claim 16, wherein the instructions when executed further enable the computing device to:

select a subset of the plurality of features based at least in part upon a combination of respective Harris corner measures of the plurality of features and a scale parameter of the Gaussian pyramid image.

18. The non-transitory computer-readable storage medium of claim 16, wherein the instructions when executed further enable the computing device to:

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

19. The non-transitory computer-readable storage medium of claim 15, wherein the instructions when executed further enable the computing device to:

determine a plurality of orientations for the feature by using a plurality of orientation calculating algorithms; and

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

20. The non-transitory computer-readable storage medium of claim 15, wherein the instructions when executed further enable 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 Gaussian pyramid image; and

sample gradients of the Gaussian pyramid image at the plurality of positions.