Method and system for matching an image using image patches

• US 8,958,629 B2
• Filed: 04/22/2014
• Issued: 02/17/2015
• Est. Priority Date: 01/14/2009
• Status: Expired due to Fees

• 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/259,002
• Publication Number:
  US 20140226913A1
• Time in Patent Office: 301 Days
• US Class Current: 382/154
• 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 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;

generate at least one Gaussian pyramid image for the query image;

identify a plurality of features for the at least one Gaussian pyramid image;

for each feature of the plurality of features for the at least one Gaussian pyramid image,

determine one or more orientations for the feature based on a plurality of orientation calculating algorithms;

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

determine a 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 respective feature vectors of each database image to one or more feature vectors of the query image; and

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

2. The system of claim 1, wherein the instructions, upon being executed by the at least one processor, further cause the system to:

for each database image of the plurality of database images,

generate at least one respective Gaussian pyramid image for the database image;

identify a respective plurality of features for the at least one respective Gaussian pyramid image; and

for each respective feature of the respective plurality of features for the at least one respective Gaussian pyramid image,

determine one or more respective orientations for the respective feature based on the plurality of orientation calculating algorithms;

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

determine a respective feature vector for the patch; and

store the respective feature vector for the database image.

3. The system of claim 1, wherein the instructions, that cause the system to determine each respective feature vector for each database image, are executed prior to obtaining the request to match the at least one portion of the query image and the instructions, that cause the system to determine each feature vector for the query image, are executed in response to obtaining the request to match the at least one portion of the query image.

5. The computer-implemented method of claim 1, wherein generating the at least one Gaussian pyramid image includes:

down-sampling the query image to generate a down-sampled image; and

blurring the down-sampled image by a Gaussian function, the Gaussian function corresponding to a scale parameter.

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

under control of one or more computer systems configured with executable instructions,

generating at least one Gaussian pyramid image for the query image;

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

for each feature of the plurality of features for the at least one Gaussian pyramid image,

determining one or more orientations for the feature based on a plurality of orientation calculating algorithms;

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

determining a feature vector for the patch; and

determining at least one matching image from among a plurality of database images based at least in part upon comparing respective feature vectors of each database image to one or more feature vectors of the query image.

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

determining a Harris corner measure at one or more pixels of the at least one Gaussian pyramid image; and

identifying each feature of the plurality of features based upon the Harris corner measure at a pixel being a local maxima.

7. The computer-implemented method of claim 6, further comprising:

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

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

determining a position of each feature of the plurality of features based at least in part upon fitting an elliptic paraboloid to a region encompassing the feature.

9. The computer-implemented method of claim 4, wherein determining the one or more orientations for the feature includes:

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

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

10. The computer-implemented method of claim 4, wherein determining the patch encompassing the feature present on a boundary of the at least one Gaussian pyramid image is based at least in part upon padding the at least one Gaussian pyramid image with extra pixels.

11. The computer-implemented method of claim 4, 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.

12. The computer-implemented method of claim 4, wherein determining the feature vector for the patch includes:

dividing the patch into a plurality of mini-patches; and

determining components of the feature vector corresponding to a mini-patch of the plurality of mini-patches.

13. The computer-implemented method of claim 12, wherein the components of the feature vector corresponding to the mini-patch comprise:

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

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

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

a fourth component corresponding to a negative of a sum of all negative y-derivatives of the at least one Gaussian pyramid image present in the mini-patch.

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

for each database image of the plurality of database images,

generating at least one respective Gaussian pyramid image for the database image;

identifying a respective plurality of features for the at least one respective Gaussian pyramid image; and

for each respective feature of the respective plurality of features for the at least one respective Gaussian pyramid image,

determining one or more respective orientations for the respective feature based on the plurality of orientation calculating algorithms;

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

determining a respective feature vector for the patch; and

storing the respective feature vector for the database image.

15. The computer-implemented method of claim 14, further 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; and

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

wherein determining each respective feature vector for each database image is performed prior to obtaining the request to match the at least one portion of the query image and determining each feature vector for the query image is performed in response to obtaining the request to match the at least one portion of the query image.

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

generate at least one Gaussian pyramid image for the query image;

identify a plurality of features for the at least one Gaussian pyramid image;

for each feature of the plurality of features for the at least one Gaussian pyramid image,

determine one or more orientations for the feature based on a plurality of orientation calculating algorithms;

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

determine a feature vector for the patch; and

determine at least one matching image from among a plurality of database images based at least in part upon comparing respective feature vectors of each database image to one or more feature vectors of the query image.

17. The non-transitory computer-readable storage medium of claim 16, wherein the instructions, that cause the computing device to determine the one or more orientations for the feature includes:

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

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

18. The non-transitory computer-readable storage medium of claim 16, wherein the instructions, that cause the computing device to determine the patch encompassing the feature includes:

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 Gaussian pyramid image; and

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

19. The non-transitory computer-readable storage medium of claim 16, wherein the instructions, that cause the computing device to determine the feature vector for the patch includes:

divide the patch into a plurality of mini-patches; and

determine components of the feature vector corresponding to a mini-patch of the plurality of mini-patches.

20. The non-transitory computer-readable storage medium of claim 19, wherein the components of the feature vector corresponding to the mini-patch comprise:

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

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

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

a fourth component corresponding to a negative of a sum of all negative y-derivatives of the at least one Gaussian pyramid image present in the mini-patch.