Processing and comparing images

• US 8,447,107 B1
• Filed: 09/30/2010
• Issued: 05/21/2013
• Est. Priority Date: 09/30/2010
• Status: Active Grant

• Current Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Original Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Inventors: Dhua, Arnab, Ramesh, Sunil
• Primary Examiner(s): Chen, Wenpeng
• Assistant Examiner(s): Niu, Feng
• Application Number:
  US12/895,527
• Time in Patent Office: 964 Days
• Field of Search: None
• US Class Current: 382/170
• CPC Class Codes: G06F 18/23211 with adaptive number of clusters
• CPC Class Codes: G06V 10/44 Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components
• CPC Class Codes: G06V 10/507 Summing image-intensity values; Histogram projection analysis
• CPC Class Codes: G06V 10/763 Non-hierarchical techniques, e.g. based on statistics of modelling distributions

Abstract

Systems and methods are provided for calculating and using histogram descriptors to compare images and to identify visually similar content. According to at least one embodiment, multiple histograms descriptors are calculated for individual images of a collection of content. These histogram descriptors may be used to identify two or more visually similar images in the collection of content. For example, if a user identifies an image of an item of interest, then embodiments search across the collection of content to identify other images of items that are visually similar to the selected item of interest. To do so, embodiments search across the histogram descriptors of the images in the collection of content to identify one or more images that have histograms descriptors that are similar to the histograms descriptors of the image of the selected item of interest.

Claims

1. A computer-implemented method comprising:

under the control of one or more computer systems configured with executable instructions, calculating a cluster descriptor for each of a plurality of clusters of feature vectors, the feature vectors being calculated based at least in part on a plurality of feature points of a subset of a collection of images;

creating a first histogram for at least one image of the subset of the collection of images, the first histogram having a plurality of bins that correspond to the clusters of feature vectors, the contents of the bins are based at least in part on the number of the feature vectors of the image that were mapped to the corresponding clusters, wherein the features vectors are mapped the nearest one of the clusters based at least in part on the cluster descriptors;

creating a second histogram for at least one image of the subset of the collection of images, the second histogram having a plurality of bins that correspond to a plurality of radial-polar bins of a radial-polar grid positioned on an edge image of the image, the contents of the bins of the second histogram are based at least in part on a number of pixels of the edge image that are located in the corresponding radial-polar bins of the radial-polar grid;

creating edge histograms for the images of the subset of the collection of images based on a plurality of feature associated with the edge images of the images, the edge histograms having a plurality of bins that correspond to a plurality of radial-polar bins of radial-polar grids that are positioned on the feature points associated with the edge images, the contents of the bins of the edge histograms are based at least in part on the number of pixels of the edge images that are located in the radial-polar bins of the radial-polar grids;

creating a third histogram for at least one image of the subset of the collection of images, the third histogram having a plurality of bins that correspond to a plurality of edge-histogram clusters, the contents of each of the bins of the third histogram are based at least in part on the number of the edge histograms that were mapped to the corresponding edge-histogram cluster, wherein the edge histograms are mapped to the nearest one of the edge-histogram clusters based at least in part on a plurality of edge-histogram cluster descriptors that were calculated for each of the edge-histogram clusters; and

identifying at least one image of the subset of the collection of images that is visually similar to a query image based at least in part on a comparison of first, second, and third histograms that characterize the query image and the first, second, and third histograms of the images of the subset of the collection of images.

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

assigning visual words to the clusters of feature vectors such that the bins of the first histogram correspond to the visual words and such that the contents of the bins of the first histogram are based at least in part on the number of the feature vectors mapped to the corresponding visual words.

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

assigning visual words to the edge-histogram clusters such that the bins of the third histogram correspond to the visual words and such that the contents of the bins of the third histogram are based at least in part on the number of the edge histograms mapped to the corresponding visual words.

4. A computer-implemented method comprising:

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

identifying a plurality of feature points in each of a plurality of images of a subset of a collection of images, each feature point corresponding to a specific point in one of the images;

calculating feature vectors based at least in part on the feature points;

clustering the feature vectors into a plurality of areas;

determining a cluster descriptor for each of the areas;

mapping ones of the features vectors to the nearest one of the areas based at least in part on the cluster descriptors, wherein the cluster descriptors represent geometric centers of the features vectors;

creating a first descriptor for at least one image of the subset of the collection of images, the first descriptor having a plurality of bins that correspond to the areas, the contents of the bins are based at least in part on the number of the feature vectors of the image that were mapped to the corresponding areas; and

identifying at least one image of the subset of the collection of images that is visually similar to a query image based at least in part on a comparison of a first descriptor that characterizes the query image and the first descriptors of the images of the subset of the collection of images by;

creating a first histogram for the at least one image according to a plurality of radial-polar bins;

creating edge histograms for the subset of the collection of images, wherein the edge histograms corresponds to the plurality of radial-polar bins;

creating a second histogram for at least one image of the subset of the collection of images according to a plurality of edge-histogram clusters, wherein the second histogram is based at least in part on a quantity of edge histograms mapped to a corresponding edge-histogram cluster; and

identifying the at least one image based on the first histogram, the edge histograms, and the second histogram.

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

creating edge images for the subset of the collection of images, the edge images having a plurality of pixels;

positioning radial-polar grids on the edge images, the radial-polar grids having a plurality of radial-polar bins;

determining the number of pixels of the edge images that are located in the radial-polar bins of the radial-polar grids; and

creating a second descriptor for at least one image of the subset of the collection of images, the second descriptor having a plurality of bins that correspond to the radial-polar bins of the radial-polar grid positioned on the edge image of the image, the contents of the bins are based at least in part on the number of pixels in the corresponding radial-polar bins,

wherein the query image is characterized by the first descriptor and a second descriptor and wherein attempting to identify at least one image of the subset of the collection of images that is visually similar to the query image is based at least in part on a comparison of the first and second descriptors of the query image and the first and second descriptors of the images of the subset of the collection of images.

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

positioning radial-polar grids on feature points associated with the edge images, the radial-polar grids having a plurality of radial-polar bins;

determining the number of pixels that are located in the radial-polar bins of the radial-polar grids that are positioned on the feature points associated with the edge images;

creating edge descriptors for the feature points associated with the edge images, the edge descriptors having a plurality of bins that correspond to the radial-polar bins of the radial-polar grids that are positioned on the feature points associated with the edge images, the contents of the bins are based at least in part on the number of pixels in the corresponding radial-polar bins;

clustering the edge descriptors into a plurality of edge-descriptor areas;

determining edge-descriptor area descriptors for the edge-descriptor areas;

mapping ones of the edge descriptors to the nearest one of a plurality of edge-descriptor areas based at least in part on the edge-descriptor area descriptors; and

creating a third descriptor for at least one image of the subset of the collection of images, the third descriptor having a plurality of bins that correspond to the edge-descriptor areas, the contents of the bins are based at least in part on the number of the edge descriptors that were mapped to the corresponding edge-descriptor areas,

wherein the query image is characterized by the first and second descriptors and a third descriptor and wherein identifying the least one image of the subset of the collection of images that is visually similar to the query image is based at least in part on a comparison of the first, second, and third descriptors of the query image and the first, second, and third descriptors of the images of the subset of the collection of images.

7. The computer-implemented method of claim 6, wherein a first descriptor, a second descriptor, and a third descriptor are created for each image in the subset of the collection of images.

8. The computer-implemented method of claim 7, wherein the comparison of the first, second, and third descriptors of the query image and the first, second, and third descriptors of the images of the subset of the collection of images comprises:

calculating a similarity score between;

the first descriptor of the query image and the first descriptor of each of the images in the subset of the collection of images;

the second descriptor of the query image and the second descriptor of each of the images in the subset of the collection of images; and

the third descriptor of the query image and the third descriptor of each of the images in the subset of the collection of images.

9. The computer-implemented method of claim 8, wherein the similarity scores represent the distance between at least one of the first, second, and third descriptors of the query image and at least one of the first, second, and third descriptors of at least one image of the subset of the collection of images.

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

for each image in the subset of the collection of images, calculating a combined similarity score, which represents the similarity between the image and the query image, by combining;

the similarity score between the first descriptor of the image and the first descriptor of the query image;

the similarity score between the second descriptor of the image and the second descriptor of the query image; and

the similarity score between the third descriptor of the image and the third descriptor of the query image.

11. The computer-implemented method of claim 10, wherein the similarity scores are combined using a linear combination.

12. The computer-implemented method of claim 11, wherein the similarity scores are combined using a tree-based comparison.

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

in response to the search request, providing for presentation at least a reference to images each having a combined similarity score that exceeds a threshold score.

14. A non-transitory computer-readable medium storing a computer program product for determining visual similar of images, comprising:

program code for identifying feature points of a subset of a collection of images;

program code for calculating feature vectors based at least in part on the feature points;

program code for clustering the feature vectors into a plurality of areas;

program code for determining cluster descriptors for the areas;

program code for mapping ones of the features vectors to the nearest one of the areas based at least in part on the cluster descriptors, wherein the cluster descriptors represent geometric centers of the features vectors;

program code for creating a first descriptor for at least one image of the subset of the collection of images, the first descriptor having a plurality of bins that correspond to the areas, the contents of the bins are based at least in part on the number of the feature vectors of the image that were mapped to the corresponding areas; and

program code for identifying at least one image of the subset of the collection of images that is visually similar to a query image based at least in part on a comparison of a first descriptor that characterizes the query image and the first descriptors of the images of the subset of the collection of images by;

creating a first histogram for the at least one image according to a plurality of radial-polar bins;

creating edge histograms for the subset of the collection of images, wherein the edge histograms corresponds to the plurality of radial-polar bins;

creating a second histogram for at least one image of the subset of the collection of images according to a plurality of edge-histogram clusters, wherein the second histogram is based at least in part on a quantity of edge histograms mapped to a corresponding edge-histogram cluster; and

identifying the at least one image based on the first histogram, the edge histograms, and the second histogram.

15. The non-transitory computer-readable medium storing the computer-program product of claim 14, further comprising:

program code for creating edge images for the subset of the collection of images, the edge images having a plurality of pixels;

program code for positioning radial-polar grids on the edge images, the radial-polar grids having a plurality of radial-polar bins;

program code for determining the number of pixels of the edge images that are located in the radial-polar bins of the radial-polar grids; and

program code for creating a second descriptor for at least one image of the subset of the collection of images, the second descriptor having a plurality of bins that correspond to the radial-polar bins of the radial-polar grid positioned on the edge image of the image, the contents of the bins are based at least in part on the number of pixels in the corresponding radial-polar bins,

wherein the query image is characterized by the first descriptor and a second descriptor and wherein identifying the least one image of the subset of the collection of images that is visually similar to the query image is based at least in part on a comparison of the first and second descriptors of the query image and the first and second descriptors of the images of the subset of the collection of images.

16. The non-transitory computer-readable medium storing the computer-program product of claim 15, further comprising:

program code for obtaining feature points for the edge images;

program code for positioning radial-polar grids on the feature points, the radial-polar grids having a plurality of radial-polar bins;

program code for determining the number of pixels that are located in the radial-polar bins of the radial-polar grids that are positioned on the feature points;

program code for creating edge descriptors for the feature points, the edge descriptors having a plurality of bins that correspond to the radial-polar bins of the radial-polar grids that are positioned on the feature points, the contents of the bins are based at least in part on the number of pixels in the corresponding radial-polar bins;

program code for clustering the edge descriptors into a plurality of edge-descriptor areas;

program code for determining edge-histogram cluster descriptors for the edge-descriptor areas;

program code for mapping ones of the edge descriptors to the nearest one of a plurality of edge-descriptor areas based at least in part on the edge-histogram cluster descriptors; and

program code for creating a third descriptor for at least one image of the subset of the collection of images, the third descriptor having a plurality of bins that correspond to the edge-descriptor areas, the contents of the bins are based at least in part on the number of the edge descriptors that were mapped to the corresponding edge-descriptor areas,

wherein the query image is characterized by the first and second descriptors and a third descriptor and wherein identifying the least one image of the subset of the collection of images that is visually similar to the query image is based at least in part on a comparison of the first, second, and third descriptors of the query image and the first, second, and third descriptors of the images of the subset of the collection of images.

17. A system comprising:

a processor; and

a memory device including instructions that, when executed by the processor, cause the processor to;

identify feature points of a subset of a collection of images;

calculate feature vectors based at least in part on the feature points;

cluster the feature vectors into a plurality of areas;

determine cluster descriptors for the areas;

map ones of the features vectors to the nearest one of the areas based at least in part on the cluster descriptors, wherein the cluster descriptors represent geometric centers of the features vectors;

create a first descriptor for at least one image of the subset of the collection of images, the first descriptor having a plurality of bins that correspond to the areas, the contents of the bins are based at least in part on the number of the feature vectors of the image that were mapped to the corresponding areas; and

identify at least one image of the subset of the collection of images that is visually similar to a query image based at least in part on a comparison of a first descriptor that characterizes the query image and the first descriptors of the images of the subset of the collection of images by;

creating a first histogram for the at least one image according to a plurality of radial-polar bins;

creating edge histograms for the subset of the collection of images, wherein the edge histograms corresponds to the plurality of radial-polar bins;

creating a second histogram for at least one image of the subset of the collection of images according to a plurality of edge-histogram clusters, wherein the second histogram is based at least in part on a quantity of edge histograms mapped to a corresponding edge-histogram cluster; and

identifying the at least one image based on the first histogram, the edge histograms, and the second histogram.

18. The system of claim 17, wherein the memory device further includes instructions that, when executed by the processor, cause the processor to:

create edge images for the subset of the collection of images, the edge images having a plurality of pixels;

position radial-polar grids on the edge images, the radial-polar grids having a plurality of radial-polar bins;

determine the number of pixels of the edge images that are located in the radial-polar bins of the radial-polar grids; and

create a second descriptor for at least one image of the subset of the collection of images, the second descriptor having a plurality of bins that correspond to the radial-polar bins of the radial-polar grid positioned on the edge image of the image, the contents of the bins are based at least in part on the number of pixels in the corresponding radial-polar bins,

wherein the query image is characterized by the first descriptor and a second descriptor and wherein identifying the least one image of the subset of the collection of images that is visually similar to the query image is based at least in part on a comparison of the first and second descriptors of the query image and the first and second descriptors of the images of the subset of the collection of images.

19. The system of claim 18, wherein the memory device further includes instructions that, when executed by the processor, cause the processor to:

obtain feature points for the edge images;

position radial-polar grids on the feature points, the radial-polar grids having a plurality of radial-polar bins;

determine the number of pixels that are located in the radial-polar bins of the radial-polar grids that are positioned on the feature points;

create edge descriptors for the feature points, the edge descriptors having a plurality of bins that correspond to the radial-polar bins of the radial-polar grids that are positioned on the feature points, the contents of the bins are based at least in part on the number of pixels in the corresponding radial-polar bins;

cluster the edge descriptors into a plurality of edge-descriptor areas;

determine edge-histogram cluster descriptors for the edge-descriptor areas;

map ones of the edge descriptors to the nearest one of a plurality of edge-descriptor areas based at least in part on the edge-histogram cluster descriptors; and

create a third descriptor for at least one image of the subset of the collection of images, the third descriptor having a plurality of bins that correspond to the edge-descriptor areas, the contents of the bins are based at least in part on the number of the edge descriptors that were mapped to the corresponding edge-descriptor areas,

wherein the query image is characterized by the first and second descriptors and a third descriptor and wherein identifying the least one image of the subset of the collection of images that is visually similar to the query image is based at least in part on a comparison of the first, second, and third descriptors of the query image and the first, second, and third descriptors of the images of the subset of the collection of images.

20. The system of claim 19, wherein the memory device further includes instructions that, when executed by the processor, cause the processor to perform the comparison of the first, second, and third descriptors of the query image and the first, second, and third descriptors of the images of the subset of the collection of images by:

calculating a similarity score between;

the first descriptor of the query image and the first descriptor of each of the images in the subset of the collection of images;

the second descriptor of the query image and the second descriptor of each of the images in the subset of the collection of images; and

the third descriptor of the query image and the third descriptor of each of the images in the subset of the collection of images;

for each image in the subset of the collection of images, calculating a combined similarity score, which represents the similarity between the image and the query image, by combining;

the similarity score between the first descriptor of the image and the first descriptor of the query image;

the similarity score between the second descriptor of the image and the second descriptor of the query image; and

the similarity score between the third descriptor of the image and the third descriptor of the query image.