Visual search utilizing color descriptors

• US 9,064,149 B1
• Filed: 03/15/2013
• Issued: 06/23/2015
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Original Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Inventors: Dhua, Arnab Sanat Kumar, Arora, Himanshu, Ramesh, Sunil
• Primary Examiner(s): Ahmed, Samir
• Assistant Examiner(s): YOUSSEF, MENATOLLAH M
• Application Number:
  US13/842,328
• Time in Patent Office: 830 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 2218/12 Classification; Matching
• CPC Class Codes: G06V 10/56 relating to colour

Abstract

Various embodiments provide a method for computing color descriptors of product images. For example, a number of fine color representatives can be determined to describe color variation in an image as a histogram by assigning a saturation value and a brightness value to a plurality of color hues. For each pixel of the image, the closest color among a defined fine color representative set is computed. In this example, each of the pixels is assigned a color ID corresponding to their closest matching fine color representative and at least one family color ID corresponding one or more pure color families. In this example, a histogram of the color representatives and a histogram for the color families are computed. A single color vector descriptor for the image is then determined by combining the family histogram with the color representative histogram.

Claims

1. A computer-implemented method, comprising:

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

assigning a saturation value and a brightness value to a plurality of color hues for each of a plurality of colors;

determining a number of fine color representatives from the plurality of colors to describe color variation in an image as a histogram;

assigning each of the number of fine color representatives to at least one pure color family of a plurality of pure color families;

obtaining a first image including a plurality of pixels;

determining a closest matching fine color representative from the number of fine color representatives for each pixel from at least a portion of the plurality of pixels of the first image, the closest matching fine color representative of the each pixel comprising a respective color included in a color space that is within a distance threshold of a second color in the color space corresponding to the each pixel;

computing a global histogram based at least in part on each of the closest matching fine color representatives of each pixel from at least the portion of the plurality of pixels and a family histogram of at least the one pure color family for each pixel of at least the portion of the plurality of pixels; and

computing a color vector descriptor from a combination of the global histogram and the family histogram, the color vector descriptor used to determine color similarity between the image and a second image.

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

obtaining the second image;

determining a closest matching fine color representative for each pixel of a plurality of pixels of the second image, the closest matching fine color representative of the each pixel comprising a second respective color included in the color space that is within a second distance threshold of a third color in the color space corresponding to the each pixel;

computing a second global histogram based at least in part on each of the closest matching fine color representatives of each pixel from the at least a portion of the plurality of pixels for the second image and a second family histogram of at least one pure color family for each pixel of at least the portion of the plurality of pixels of the second image;

computing a second color vector descriptor from a combination of the second global histogram and the second family histogram; and

determining a similarity measure between the first vector descriptor and the second vector descriptor.

3. The computer-implemented method of claim 2, wherein the similarity measure is determined by computing a dot product of the first vector descriptor and the second vector descriptor.

4. The computer-implemented method of claim 1, wherein the number of fine color representatives includes at least one grayscale representative.

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

normalizing the color vector descriptor to have a unit Euclidean norm.

6. A computer-implemented method, comprising:

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

determining a closest color for each pixel of at least a portion of pixels of an image from a set of representative colors, each representative color being assigned to at least one color family, the closest color of the each pixel of at least the portion of pixels comprising a respective color included in a color space that is within a distance threshold of a second color in the color space corresponding to the each pixel;

computing a global color histogram of color representatives corresponding to closest color counts and a color family histogram corresponding to color family counts for at least the portion of pixels; and

computing a color vector descriptor from a combination of the global color histogram and the color family histogram for determining color similarity between the image and at least a second image.

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

defining a hue, saturation, and value (HSV) space;

dividing a hue space portion of the HSV space uniformly into a plurality of colors; and

determining the set of color representatives by assigning a saturation value and a brightness value pair to a plurality of hues of the hue space portion.

8. The computer-implemented method of claim 7, wherein more color representatives are assigned to more saturation values for high brightness values relative to color representatives assigned saturation values for low brightness values.

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

defining a number of color families, each color family including a plurality of red, green, blue (RGB) color values;

determining a closest RGB color value of the plurality of RGB color values for each of the set of representative colors, the closest RGB color value comprising a respective color included in an RGB color space that is within a distance threshold of a second color in the RGB color space corresponding to the plurality of RGB color values for each of the set of representative colors; and

assigning each of the set of representative colors to one or more color families of the number of defined color families associated with the determined closest RGB color value.

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

normalizing the color vector descriptor to have a unit Euclidean norm.

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

obtaining the second image;

determining a closest color for each pixel of at least a portion of pixels of the second image, the closest color of the each pixel comprising a second respective color included in the color space that is within a distance threshold of a third color in the color space corresponding to the each pixel;

computing a second global histogram and a second family histogram for the second image;

computing a second color vector descriptor from a combination of the second global histogram and the second family histogram; and

determining a similarity measure between the first vector descriptor and the second vector descriptor.

12. The computer-implemented method of claim 11, wherein the similarity measure is determined by computing a dot product of the first vector descriptor and the second vector descriptor.

13. A computing device, comprising:

a processor;

a display screen; and

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

determine a closest color for each pixel of at least a portion of pixels of an image from a set of representative colors, each representative color being assigned to at least one color family, the closest color of the each pixel comprising a respective color included in a color space that is within a distance threshold of a second color in the color space corresponding to the each pixel;

compute a global color histogram of color representatives corresponding to closest color counts and a color family histogram corresponding to color family counts for the at least a portion of pixels; and

compute a color vector descriptor from a combination of the global color histogram and the color family histogram, the color vector descriptor used to determine color similarity between the image and a second image.

14. The computing device of claim 13, wherein the instructions, when executed by the processor, further cause the computing device to:

define a hue, saturation, and value (HSV) space;

divide a hue space portion of the HSV space uniformly into a plurality of colors; and

determine the set of color representatives by assigning a saturation value and a brightness value pair to a plurality of hues of the hue space portion.

15. The computing device of claim 13, wherein the instructions, when executed by the processor, further cause the computing device to:

define a number of color families, each color family including a plurality of red, green, blue (RGB) color values;

determine a closest RGB color value of the plurality of RGB color values for each of the set of representative colors, the closest RGB color value comprising a respective color included in an RGB color space that is within a distance threshold of a second color in the RGB color space corresponding to the plurality of RGB color values for each of the set of representative colors; and

assign each of the set of representative colors to one or more color families of the number of defined color families associated with the determined closest RGB color value.

16. The computing device of claim 13, wherein the instructions, when executed by the processor, further cause the computing device to:

obtain a second image;

determine a closest color for each pixel of at least a portion of pixels of the second image, the closest color of the each pixel comprising a second respective color included in the color space that is within a second distance threshold of a third color in the color space corresponding to the each pixel;

compute a second global histogram and a second family histogram for the second image;

compute a second color vector descriptor from a combination of the second global histogram and the second family histogram; and

determine a similarity measure between the first vector descriptor and the second vector descriptor.

17. The computing device of claim 13, wherein the instructions, when executed by the processor, further cause the computing device to:

normalize the color vector descriptor to have a unit Euclidean norm.

18. The computing device of claim 13, wherein at least one of the set of representative colors includes at least one grayscale representative.

19. A non-transitory computer-readable storage medium storing instructions that, when executed by at least one processor, cause a computing device to:

determine a closest color for each pixel of at least a portion of pixels of an image from a set of representative colors, each representative color being assigned to at least one color family, the closest color of the each pixel comprising a respective color included in a color space that is within a distance threshold of a second color in the color space corresponding to the each pixel;

compute a global color histogram of color representatives corresponding to closest color counts and a color family histogram corresponding to color family counts for the at least a portion of pixels; and

compute a color vector descriptor from a combination of the global color histogram and the color family histogram, the color vector descriptor used to determine color similarity between the image and a second image.

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

obtain a second image;

determine a closest color for each pixel of at least a portion of pixels of the second image, the closest color of the each pixel comprising a second respective color included in the color space that is within a second distance threshold of a third color in the color space corresponding to the each pixel;

compute a second global histogram and a second family histogram for the second image;

compute a second color vector descriptor from a combination of the second global histogram and the second family histogram; and

determine a similarity measure between the first vector descriptor and the second vector descriptor.

21. The non-transitory computer-readable storage medium of claim 19, wherein at least one of the set of representative colors includes at least one grayscale representative.

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

normalize the color vector descriptor to have a unit Euclidean norm.

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

define a number of color families, each color family including a plurality of red, green, blue (RGB) color values;

determine a closest RGB color value of the plurality of RGB color values for each of the set of representative colors, the closest RGB color value comprising a respective color included in an RGB color space that is within a distance threshold of a second color in the RGB color space corresponding to the plurality of RGB color values for each of the set of representative colors; and

assign each of the set of representative colors to one or more color families of the number of defined color families associated with the determined closest RGB color value.

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

define a hue, saturation, and value (HSV) space;

divide a hue space portion of the HSV space uniformly into a plurality of colors; and

determine the set of color representatives by assigning a saturation value and a brightness value pair to a plurality of hues of the hue space portion.