Contour detection and image classification

• US 9,189,854 B2
• Filed: 03/24/2014
• Issued: 11/17/2015
• 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 Sanat Kumar, Ramesh, Sunil
• Primary Examiner(s): Mehta, Bhavesh
• Assistant Examiner(s): Niu, Feng
• Application Number:
  US14/223,717
• Publication Number:
  US 20140241634A1
• Time in Patent Office: 603 Days
• Field of Search: None
• US Class Current: 1/1
• 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: G06T 7/73 using feature-based methods
• 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/46 Descriptors for shape, contour or point-related descriptors, e.g. scale invariant feature transform [SIFT] or bags of words [BoW]; Salient regional features colour feature extraction G06V10/56
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]

Abstract

Systems and methods are provided for creating contour images that represent the contour of objects reflected in images, calculating contour histogram descriptors of the contour images, and classifying images based in part on the histogram descriptors of the contour images. For example, a contour image of an image is created. A radial-polar grid having a plurality of radial-polar bins is then positioned on the contour image. A contour histogram descriptor is created to include a number of bins that correspond to the radial-polar bins of the radial-polar grid, where the contents of the bins of the contour histogram descriptor represent the number of pixels of the contour image that are located in the corresponding radial-polar bins of the radial-polar grid. Images are classified at least based in part on comparisons between contour histogram descriptors of the images and contour histogram descriptors of training images.

Claims

1. A computer-implemented method comprising:

receiving, from a computing device, a query image;

defining a contour corresponding to an item represented in the query image;

generating a query contour histogram of the contour;

comparing the query contour histogram for the query image to a plurality of database contour histograms of a search index;

selecting one or more database contour histograms of the plurality of database contour histograms nearest the query contour histogram;

classifying the query image as containing one of a right-facing object or a left-facing object based at least in part on the one or more selected database contour histograms;

generating a set of query descriptors for the query image;

if the query image is classified as containing the right-facing object, comparing the set of query descriptors to a plurality of database descriptors corresponding to right-facing objects; and

if the query image is classified as containing the left-facing object, comparing the set of query descriptors to a plurality of database descriptors corresponding to left-facing objects.

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

calculating, using a distance metric, a similarity score between the query contour histogram and each of the plurality of database contour histograms, wherein the one or more database contour histograms are select based on a set of highest similarity scores.

3. The computer-implemented method of claim 1, wherein generating the query contour histogram of the contour includes:

positioning a radial-polar grid on the contour, the radial-polar grid including a plurality of radial-polar bins; and

determining a number of pixels corresponding to the contour in each of a plurality of radial-polar bins of the query image.

4. The computer-implemented method of claim 3, wherein a center of the radial grid is positioned at a center of a bounding box of the contour.

5. The computer-implemented method of claim 4, wherein the query contour histogram includes a plurality of bins corresponding to the plurality of radial-polar bins, content of the bins being at least based in part on the number of contour pixels in corresponding radial-polar bins.

6. A computing system, comprising:

a processor;

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

generate an index containing a set of contour histograms corresponding to a set of training images;

receive a query image from a computing device;

define a contour corresponding to an item represented in the query image;

generate a query contour histogram of the contour;

compare the query contour histogram to the set contour histograms from the index;

select one or more contour histograms from the index nearest the query contour histogram;

classify the query image as containing one of a right-facing object or a left-facing object based at least in part on the one or more nearest contour histograms;

generate a set of query descriptors for the query image;

if the query image is classified as containing the right-facing object, compare the set of query descriptors to a plurality of database descriptors corresponding to right-facing objects; and

if the query image is classified as containing the left-facing object, compare the set of query descriptors to a plurality of database descriptors corresponding to left-facing objects.

7. The computing system of claim 6, wherein generating the query contour histogram of the contour includes:

positioning a radial-polar grid on the contour, the radial-polar grid including a plurality of radial-polar bins; and

determining a number of pixels corresponding to the contour in each of a plurality of radial-polar bins of the query image.

8. The computing system of claim 7, wherein the instructions that, when executed by the processor, further cause the computing device to:

generate the set of contour histograms from the set of training images, the set of contour histograms having indicators that classify the set of training images as being images of left-facing items or right-facing items, the histograms each having a plurality of bins corresponding to a respective radial-polar grid, content of the bins being at least based in part on the number of contour pixels in corresponding radial-polar bins.

9. The computing system of claim 7, wherein a center of the radial grid is positioned at a center of a bounding box of the contour, the query contour histogram including a plurality of bins corresponding to the plurality of radial-polar bins, content of the bins being at least based in part on the number of contour pixels in corresponding radial-polar bins.

10. The computing system of claim 9, wherein positioning the radial-polar grid on the contour, comprises:

positioning a center of the radial-polar grid at a center of a bounding box of the contour, wherein the bounding box is defined by a left-most pixel, a right-most pixel, a bottom-most pixel, and a top-most pixel of the contour.

11. A non-transitory computer-readable storage medium storing instructions that, when executed by a processor of a computing device, cause the computing device to:

receive a query image;

define a contour corresponding to an item represented in the query image;

generate a query contour histogram of the contour;

compare the query contour histogram for the query image to a plurality of database contour histograms of a search index;

select one or more database contour histograms of the plurality of database contour histograms nearest the query contour histogram; and

classify the query image as containing one of a right-facing object or a left-facing object based at least in part on the one or more selected database contour histograms;

generate a set of query descriptors for the query image;

if the query image is classified as containing the right-facing object, compare the set of query descriptors to a plurality of database descriptors corresponding to right-facing objects; and

if the query image is classified as containing the left-facing object, compare the set of query descriptors to a plurality of database descriptors corresponding to left-facing objects.

12. The non-transitory computer-readable storage medium of claim 11, wherein the instructions that, when executed by the processor of the computing device, further cause the computing device to:

calculate, using a distance metric, a similarity score between the query contour histogram and each of the plurality of database contour histograms, wherein the one or more database contour histograms are select based on a set of highest similarity scores.

13. The non-transitory computer-readable storage medium of claim 12, wherein generating the query contour histogram of the contour includes:

positioning a radial-polar grid on the contour, the radial-polar grid including a plurality of radial-polar bins; and

determining a number of pixels corresponding to the contour in each of a plurality of radial-polar bins of the query image.

14. The non-transitory computer-readable storage medium of claim 13, wherein the instructions that, when executed by the processor of the computing device, further cause the computing device to:

generate an index containing a set of contour histograms corresponding to a set of training images, the set of contour histograms having indicators that classify the set of training images as being images of left-facing items or right-facing items, the histograms each having a plurality of bins corresponding to a respective radial-polar grid, content of the bins being at least based in part on the number of contour pixels in corresponding radial-polar bins.

15. The non-transitory computer-readable storage medium of claim 13, wherein a center of the radial-polar grid is positioned at a center of a bounding box of the contour.

16. The non-transitory computer-readable storage medium of claim 15, wherein positioning the radial-polar grid on the contour, comprises:

positioning a center of the radial-polar grid at a center of a bounding box of the contour, wherein the bounding box is defined by a left-most pixel, a right-most pixel, a bottom-most pixel, and a top-most pixel of the contour.

17. The non-transitory computer-readable storage medium of claim 11, wherein defining the contour comprises creating an edge image of the image, the edge image being defined by pixels organized in rows and columns, the edge image having a left side, a right side, a top side, and a bottom side.

18. The non-transitory computer-readable storage medium of claim 11, wherein the instructions that, when executed by at least one processor of the computing device, further cause the computing device to:

determine a plurality of feature points of the contour;

position a radial-polar grid on each of the plurality of feature points; and

create a histogram for each of the feature points, each histogram having a plurality of bins corresponding to a plurality of radial-polar bins of a respective feature point, content of the bins being at least based in part on a number of contour pixels in corresponding radial-polar bins.