Compact color feature vector representation

• US 6,961,736 B1
• Filed: 05/31/2002
• Issued: 11/01/2005
• Est. Priority Date: 05/31/2002
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Amirghodsi, Sohrab
• Primary Examiner(s): Channavajjala, Srirama
• Assistant Examiner(s): Wu, Yicun
• Application Number:
  US10/157,954
• Time in Patent Office: 1,250 Days
• Field of Search: 707/104.1, 707/101, 707/102, 707/103, 707/6, 707/100, 382/240, 382/180, 382/162, 382/181, 382/232
• US Class Current: 1/1
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06V 10/56 relating to colour
• CPC Class Codes: Y10S 707/915 Image
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

Methods and apparatus for representing images using a compact color feature vector. A color feature vector includes a color element for each color in an image-specific set of colors. A color element includes a color identifier and a relative color occurrence. A compact color feature vector may be used in a content-based image retrieval (CBIR) system. The CBIR system includes an image data store containing multiple images. A color feature vector data store includes a variable-length color feature vector for each image in the image data store. A computer program receives a query and uses the variable-length color feature vectors in the color feature vector data store to identify which images satisfy the query.

Claims

1. A system comprising:

an image data store containing a plurality of images;

a color feature vector data store including a variable-length color feature vector for each of the plurality of images in the image data store; and

a computer program operable to

receive an image having one or more colors;

estimate a number of colors that can be used to represent the received image so that one or more fuzzy error criteria are satisfied;

set a value of a variable to be the estimated number of colors and until a length of the color feature vector is determined;

apply a medium-cut quantizer to the received image to produce a quantized image having a number of colors that is equal to the current value of the variable;

calculate an error between the quantized image and the received image; and

if the calculated error satisfies an error threshold, determine the length of color feature vector based on the current value of the variable; and

if the calculated error does not satisfy the error threshold, increment the value of the variable; and

generate a color feature vector that is representative of and specific to the received image, the color feature vector having the determined length.

2. The system of claim 1 wherein the color feature vectors are compact.

3. The system of claim 1 wherein the length of each of the variable-length color feature vectors is determined by the color complexity of the represented image.

4. The system of claim 1 wherein each variable-length color feature vector includes a color descriptor, the color descriptor comprising:

a color identifier; and

a relative color occurrence.

5. The system of claim 4 further comprising a global color table, wherein the color identifier references a color in the global color table.

6. The system of claim 5 wherein the global color table is calculated from a sample image data store by quantizing images in the sample image data store to determine a set of quantized image colors, and selecting colors for the global color table using the set of quantized image colors to minimize error across the sample image data store.

7. The system of claim 6 wherein the sample image data store is the image data store and the multiple images are all the images in the image data store.

8. The system of claim 5 wherein the global color table is a generic global color table that is not specific to the image data store.

9. The system of claim 4 wherein the color occurrence identifies the relative occurrence of colors in the image similar to the color represented by the color identifier.

10. The system of claim 9 wherein color similarities are determined by computing vector distances.

11. The system of claim 4 wherein colors in the image correspond to selected colors in the color feature vector.

12. The system of claim 4 wherein the color identifier is stored in a 9-bit field.

13. The system of claim 4 wherein the relative color occurrence is stored in a 7-bit field.

14. A computer-implemented method comprising:

receiving an image having one or more colors;

estimating a number of colors that can be used to represent the received image;

setting a value of a variable to be the estimated number of colors and until a length of the color feature vector is determined;

applying a medium-cut quantizer to the received image to produce a quantized image having a number of colors that is equal to the current value of the variable;

calculating an error between the quantized image and the received image; and

if the calculated error satisfies an error threshold, determining the length of color feature vector based on the current value of the variable, and if the calculated error does not satisfy the error threshold incrementing the value of the variable; and

generating a color feature vector that is representative of and specific to the received image, the color feature vector having the determined length.

15. The method of claim 14 wherein the color feature vector includes:

for each of the colors in the quantized image, a color element comprising;

a color identifier; and

the relative occurrence of colors in the quantized image corresponding to the color identifier.

16. The method of claim 14 wherein estimating the number of colors includes performing a logarithmic search for the number of colors.

17. The method of claim 16 wherein performing a logarithmic search for the number of colors includes performing a fuzzy binary search for the number of colors, the fuzzy binary search being based on one or more fuzzy error criteria.

18. The method of claim 17 wherein each of the one or more fizzy error criteria and the error threshold is based on a peak signal-to-noise ratio.

19. The method of claim 14, wherein generating the color feature vector includes:

quantizing the received image to a number of colors that is the current value of the variable; and

mapping colors of the quantized image to colors in a global color table.

20. The method of claim 19, wherein:

a non-linear filter is applied to the received image before the received image is quantized to the number of colors on which the determination of the length of the color feature vector is based.

21. The method of claim 19, wherein mapping colors includes:

generating an inverse color table that maps indices from an original color space of the received image to a color space of the quantized image; and

generating an inverse color table that maps indices from the color space of the quantized image to indices of a global color table.

22. The method of claim 19, further comprising:

dropping a color that occurs in less than a threshold number of pixels of the quantized image.

23. The method of claim 19, wherein the global color table is generated by:

applying a medium-cut quantizer to a collection of images to quantize images of the collection, the quantizer being subject to one or more rate distortion criteria; and

using a vector quantizer to generate the global color table, the global color table minimizing a mean standard error over the collection of images.

24. The method of claim 23, wherein:

the collection of images is stored in a data store of images.

25. The method of claim 14, further comprising:

comparing the received image to another image, the comparing being based on the feature color vector generated for the received image.

26. The method of claim 14, further comprising:

associating the generated color feature vector with the quantized image.

27. A computer-program product, tangibly stored on machine-readable medium, the product comprising instructions to cause a processor to:

receive an image having one or more colors;

estimate a number of colors that can be used to represent the received image so that one or more fuzzy error criteria are satisfied;

set a value of a variable to be the estimated number of colors and until a length of the color feature vector is determined;

apply a medium-cut quantizer to the received image to produce a quantized image having a number of colors that is equal to the current value of the variable;

calculate an error between the quantized image and the received image; and

if the calculated error satisfies an error threshold, determine the length of color feature vector based on the current value of the variable, and if the calculated error does not satisfy the error threshold, increment the value of the variable; and

generate a color feature vector that is representative of and specific to the received image, the color feature vector having the determined length.

28. The product of claim 27 wherein instructions to estimate the number of colors include instructions to perform a logarithmic search for the number of colors.

29. The product of claim 28 wherein instructions to perform a logarithmic search for the number of colors include instructions to perform a fuzzy binary search for the number of colors, the fuzzy search being based on one or more fuzzy error criteria.

30. The product of claim 29 wherein each of the one or more fuzzy error criteria and the error threshold is based on a peak signal-to-noise ratio.

31. The product of claim 27, wherein instructions to generate the color feature vector include instructions to:

quantize the received image to a number of colors that is the current value of the variable; and

map colors of the quantized image to colors in a global color table.

32. The product of claim 31, wherein:

a non-linear filter is applied to the received image before the received image is quantized to the number of colors on which the determination of the length of the color feature vector is based.

33. The product of claim 31, wherein instructions to map colors include instructions to:

generate an inverse color table that maps indices from an original color space of the received image to a color space of the quantized image; and

generate an inverse color table that maps indices from the color space of the quantized image to indices of a global color table.

34. The product of claim 31, further comprising instructions to:

drop a color that occurs in less than a threshold number of pixels of the quantized image.

35. The product of claim 31, further comprising instructions to:

applying a medium-cut quantizer to a collection of images to quantize images of the collection, the quantizer being subject to one or more rate distortion criteria; and

using a vector quantizer to generate the global color table, the global color table minimizing a mean standard error over the collection of images.

36. The product of claim 35, wherein;

the collection of images is stored in a data store of images.

37. The product of claim 27, further comprising instructions to:

compare the received image to another image, the comparing being based on the feature color vector generated for the received image.

38. The product of claim 27, further comprising instructions to:

associate the generated color feature vector with the quantized image.