Contour detection and image classification

• US 8,422,782 B1
• Filed: 09/30/2010
• Issued: 04/16/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: Ramesh, Sunil, Dhua, Arnab
• Primary Examiner(s): Chen, Wenpeng
• Assistant Examiner(s): Niu, Feng
• Application Number:
  US12/895,506
• Time in Patent Office: 929 Days
• Field of Search: None
• US Class Current: 382/170
• 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 of classifying an image as being of a left-facing item or a right-facing item, comprising:

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

creating an edge image of the image of an item of interest, the edge image being defined by pixels organized in rows and columns and having a left side, a right side, a top side, and a bottom side;

creating a contour image that represents an outline of the edge image, the contour image including a left contour of the left side of the edge image, a right contour of the right side of the edge image, a top contour of the top side of the edge image, and a bottom contour of the bottom side of the edge image, the contour image being created by;

creating the left and right contours by;

traversing a first window having a height along each of a subset of the rows, the first window traverses from a left position toward the left side of the edge image and from a right position toward the right side of the edge image;

stopping the traversing of the first window at a location on the row where the first window covers a threshold amount of pixels; and

activating at least one pixel at the location of the row;

creating the top and bottom contours by;

traversing a second window having a width along each of a subset of the columns, the second window traverses from a top position toward the top side of the edge image and from a bottom position toward the bottom side of the edge image;

stopping the traversing of the second window at a location of the column where the second window covers the threshold amount of pixels; and

activating at least one pixel at the location of the column;

positioning a center of the radial grid having a plurality of radial-polar bins at a center of a bounding box of the contour image, the bounding box being defined by a left-most pixel, a right-most pixel, a bottom-most pixel, and a top-most pixel of the contour image;

determining the number of pixels of the contour image that are located in the radial-polar bins of the radial-polar grid;

creating a histogram for the image, the histogram having a plurality of bins that correspond to the radial-polar bins of the radial-polar grid, the contents of the bins represent the number of pixels in the corresponding radial-polar bins; and

classifying the image of the item of interest as being of a left-facing item or a right-facing item based at least in part on the histogram of the image.

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

obtaining a plurality of training images having indicators that classify the training images as being images of left-facing items or right-facing items;

creating contour images of the training images;

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

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

creating histograms of the training images, the histogram having a plurality of bins that correspond to the radial-polar bins of the radial-polar grids, the contents of the bins represent the number of pixels in the corresponding radial-polar bins.

3. The computer-implement method of claim 2, further comprising:

comparing the histogram of the image of the item of interest to the histograms of the training images;

identifying one of the training images that is similar to the image of the item of interest based at least in part on distances between the histogram of the image of the item of interest and the histograms of the training images;

classifying the image of the item of interest as being of a right-facing item or a left-facing item based at least in part on the classification of the similar one of the training images.

4. A computer-implemented method of classifying an image based upon an orientation of an item reflected in the image, comprising:

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

creating a contour image that represents an outline of the image, the image being defined by pixels organized in rows and columns, creating the contour image comprises;

for each of a subset of the rows,

traversing a first window having a height along the row;

stopping the traversing of the first window at a location on the row where the first window covers a threshold amount of pixels; and

activating at least one pixel at the location of the row;

for each of a subset of the columns,

traversing a second window having a width along the column;

stopping the traversing of the second window at a location of the column where the second window covers the threshold amount of pixels; and

activating at least one pixel at the location of the column;

positioning a radial-polar grid on the contour image, the radial-polar grid having a plurality of radial-polar bins;

determining the number of pixels of the contour image that are located in the radial-polar bins of the radial-polar grid;

creating a histogram for the image, the histogram having a plurality of bins that correspond to the radial-polar bins of the radial-polar grid, the contents of the bins represent the number of pixels in the corresponding radial-polar bins;

determining an orientation of an item of the image based at least in part on the histogram of the image; and

classifying the image based at least in part on the orientation of the item.

5. The computer-implement method of claim 4, wherein the image is of an item of interest.

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

obtaining a plurality of training images having indicators that classify the training images as being images of left-facing items or right-facing items;

creating contour images of the training images;

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

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

creating histograms of the training images, the histogram having a plurality of bins that correspond to the radial-polar bins of the radial-polar grids, the contents of the bins represent the number of pixels in the corresponding radial-polar bins.

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

comparing the histogram of the image of the item of interest to the histograms of the training images;

identifying at least one of the training images that is similar to the image of the item of interest based at least in part on distances between the histogram of the image of the item of interest and the histograms of the training images;

classifying the image of the item of interest as being of a right-facing item or a left-facing item based at least in part on the classification of the at least one of the training images that is similar to the image of the item of interest.

8. A computer-implemented method of classifying an image based upon an orientation of an item reflected in the item, comprising:

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

creating a contour image that represents an outline of image;

positioning a radial-polar grid on the contour image, the radial-polar grid having a plurality of radial-polar bins;

determining the number of pixels of the contour image that are located in the radial-polar bins of the radial-polar grid;

creating a histogram of the image, the histogram having a plurality of bins that correspond to the radial-polar bins of the radial-polar grid, the contents of the bins represent the number of pixels in the corresponding radial-polar bins;

determining an orientation of an item of the image based at least in part on the histogram of the image; and

classifying the image based at least in part on the orientation of the item.

9. The computer-implemented method of claim 8, wherein the image is of a item of interest.

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

obtaining a plurality of training images having indicators that classify the training images as being images of left-facing items or right-facing items;

creating contour images of the training images;

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

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

creating histograms of the training images, the histogram having a plurality of bins that correspond to the radial-polar bins of the radial-polar grids, the contents of the bins represent the number of pixels in the corresponding radial-polar bins.

11. The computer-implement method of claim 10, further comprising:

comparing the histogram of the image of the item of interest to the histograms of the training images;

identifying at least one of the training images that is similar to the image of the item of interest based at least in part on distances between the histogram of the image of the item of interest and the histograms of the training images;

classifying the image of the item of interest as being of a right-facing item or a left-facing item based at least in part on the classification of the at least one of the training images that is similar to the image of the item of interest.

12. The computer-implemented method of claim 8, wherein positioning the radial-polar grid on the contour image, comprises:

positioning a center of the radial grid at a center of a bounding box of the contour image, 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 image.

13. The computer-implemented method of claim 8, wherein creating the contour image comprises:

creating an edge image of the image, the edge image being defined by pixels organized in rows and columns;

for each of a subset of the rows,

traversing a first window having a height along the row;

stopping the traversing of the first window at a location on the row where the first window covers a threshold amount of pixels; and

activating at least one pixel at the location of the row;

for each of a subset of the columns,

traversing a second window having a width along the column;

stopping the traversing of the second window at a location of the column where the second window covers the threshold amount of pixels; and

activating at least one pixel at the location of the column.

14. The computer-implemented method of claim 13, wherein the height of the first window for traversing rows is between two and five percent of a height of the edge image.

15. The computer-implemented method of claim 13, wherein the width of the second window for traversing columns is between two and five percent of a width of the edge image.

16. The computer-implemented method of claim 13, wherein the threshold amount of pixels is sixty percent of the height of the first window.

17. The computer-implemented method of claim 13, wherein the threshold amount of pixels is sixty percent of the width of the second window.

18. The computer-implemented method of claim 8, wherein creating the contour image 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.

19. The computer-implemented method of claim 18, wherein the contour image comprising a contour of the left side of the edge image, a contour of the right side of the edge image, a contour of the top side of the edge image, and a contour of the bottom side of the edge image.

20. The computer-implemented method of claim 19, wherein creating the contour image that represents the outline of the edge image comprises:

defining the contour of the left and right sides of the edge image by;

traversing a first window having a height along each of a subset of the rows, the first window traverses from a left position toward the left side of the edge image and from a right position toward the right side of the edge image;

stopping the traversing of the first window at a location on the row where the first window covers a threshold amount of pixels; and

activating at least one pixel at the location of the row;

defining the contour of the top and bottom sides of the edge image by;

traversing a second window having a width along each of a subset of the columns, the second window traverses from a top position toward the top side of the edge image and from a bottom position toward the bottom side of the edge image;

stopping the traversing of the second window at a location of the column where the second window covers the threshold amount of pixels; and

activating at least one pixel at the location of the column.

21. A computer-implemented method of classifying a query image as being of a left-facing item or a right-facing item, comprising:

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

obtaining a plurality of training images having indicators that classify the training images as being images of left-facing items or right-facing items;

creating contour images of the training images;

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

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

creating histograms of the training images, the histogram having a plurality of bins that correspond to the radial-polar bins of the radial-polar grids, the contents of the bins represent the number of pixels in the corresponding radial-polar bins; and

classifying the query image as being of a left-facing item or a right-facing item based at least in part on the histograms of the training images.

22. The computer-implement method of claim 21, further comprising:

creating a contour image of the query image;

positioning a radial-polar grid on the contour image, the radial-polar grid having a plurality of radial-polar bins;

determining the number of pixels of the contour image that are located in the radial-polar bins of the radial-polar grid; and

creating a histogram of the query image, the histogram of the query image having a plurality of bins that correspond to the radial-polar bins of the radial-polar grid, the contents of the bins represent the number of pixels in the corresponding radial-polar bins.

23. The computer-implement method of claim 22, further comprising:

comparing the histogram of the query image to the histograms of the training mages;

identifying at least one of the training images that is similar to the query image based at least in part on distances between the histogram of the query image and the histograms of the training images; and

classifying the image of the item of interest as being of a right-facing item or a left-facing item based at least in part on the classification of the at least one of the training images that is similar to the query image.

24. A computer program product embedded in a non-transitory computer-readable medium, comprising:

program code for creating a contour image that represents an outline of an image;

program code for positioning a radial-polar grid on the contour image, the radial-polar grid having a plurality of radial-polar bins;

program code for determining the number of pixels of the contour image that are located in the radial-polar bins of the radial-polar grid;

program code for creating a histogram of the image, the histogram having a plurality of bins that correspond to the radial-polar bins of the radial-polar grid, the contents of the bins represent the number of pixels in the corresponding radial-polar bins; and

program code for classifying the image as being of a left-facing item or a right-facing item based at least in part on the histogram of the image.

25. The computer-program product embedded in the non-transitory computer-readable medium item of claim 24, wherein program code for creating the contour image comprises:

program code for creating an edge image of the image, the edge image being defined by pixels organized in rows and columns;

for each of a subset of the rows,

program code for traversing a first window having a height along the row;

program code for stopping the traversing of the first window at a location on the row where the first window covers a threshold amount of pixels; and

program code for activating at least one pixel at the location of the row;

for each of a subset of the columns,

program code for traversing a second window having a width along the column;

program code for stopping the traversing of the second window at a location of the column where the second window covers the threshold amount of pixels; and

program code for activating at least one pixel at the location of the column.

26. A system comprising:

a processor; and

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

create a contour image that represents an outline of an image;

position a radial-polar grid on the contour image, the radial-polar grid having a plurality of radial-polar bins;

determine the number of pixels of the contour image that are located in the radial-polar bins of the radial-polar grid;

create a histogram of the image, the histogram having a plurality of bins that correspond to the radial-polar bins of the radial-polar grid, the contents of the bins represent the number of pixels in the corresponding radial-polar bins; and

classify the image as being of a left-facing item or a right-facing item based at least in part on the histogram of the image.

27. The system of claim 26, wherein the memory device further includes instructions for creating the contour image that, when executed by the processor, cause the processor to:

create an edge image of the image, the edge image being defined by pixels organized in rows and columns;

for each of a subset of the rows,

traverse a first window having a height along the row;

stop the traverse of the first window at a location on the row where the first window covers a threshold amount of pixels; and

activate at least one pixel at the location of the row;

for each of a subset of the columns,

traverse a second window having a width along the column;

stop the traverse of the second window at a location of the column where the second window covers the threshold amount of pixels; and

activate at least one pixel at the location of the column.