Compact color feature vector representation

• US 7,346,631 B2
• Filed: 09/12/2005
• Issued: 03/18/2008
• Est. Priority Date: 05/31/2002
• Status: Expired due to Term

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Amirghodsi, Sohrab
• Primary Examiner(s): Wu; Yicun
• Application Number:
  US11/224,866
• Publication Number:
  US 20060077408A1
• Time in Patent Office: 918 Days
• Field of Search: 707/104.1
• US Class Current: 382/306
• 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 global color table, wherein the global color table is calculated from the image data store by quantizing images in the 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 image data store; and

a computer program comprising instructions operable to;

receive an original image having one or more colors from the image data store;

estimate a number of distinct colors in the original image;

use the estimated number to determine a quantization number for the original image;

determine a quantized image by quantizing the original image into the quantization number of quantized image colors; and

map each of the quantized image colors to a color of the global color table;

generate a color feature vector of one or more color descriptors to represent the original image, each color descriptor corresponding to quantized image color of the quantized image, each color descriptor comprising (i) a color index that references a location of the respective quantized image color in the global color table and (ii) a relative occurrence of the respective quantized image color within the quantized image.

2. The system of claim 1, wherein the original image is represented by indices into an original image color space, the system further comprising:

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

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

3. The system of claim 1, wherein the global color table is calculated by quantizing all the images in the image data store.

4. The system of claim 1, wherein the computer program estimates the number of distinct colors in the image by performing a fuzzy binary search to determine a number of colors needed to represent the image to a quality threshold.

5. The system of claim 4, wherein performing the binary search comprises quantizing the image for a given number of distinct colors using a median-cut color quantizer and comparing the quantized image to the original image.

6. The system of claim 1, wherein colors that occur with less than a threshold frequency in the quantized image are excluded from the color feature vector.

7. The system of claim 1, wherein:

the system includes a color feature vector of one or more descriptors for each of the plurality of images, each descriptor comprising (i) a color index that references a location of a color in the global color table and (ii) a relative occurrence of the color as a quantized color within the corresponding image of the plurality of images; and

the computer program further comprises instructions operable to;

receive a query from a user of the system identifying a query image;

use the query image to create a query color feature vector of one or more descriptors, each descriptor comprising (i) a color index that references a location of a color in the global color table and (ii) a relative occurrence of the color as a quantized color within the query image; and

compare the query color feature vector to the color feature vectors of the plurality of images to identify images among the plurality of images that satisfy the query.

8. The system of claim 7, wherein the query image is one of the plurality of images.

9. A computer-implemented method comprising:

generating a global color table from sample images, generating the global color table comprising quantizing the sample images to determine a set of quantized image colors, and selecting colors from the set of colors to minimize error across the sample images;

estimating an estimated number of distinct colors in an original image;

using the estimated number to determine a number N of colors to use to represent the original image as a quantized image;

quantizing the original image into a quantized image of N colors;

mapping each of the quantized image colors to a resultant color in the global color table; and

generating a color feature vector of one or more color descriptors to represent the image, each color descriptor indicating a frequency of occurrence of a resultant color in the image.

10. The method of claim 9, wherein the global color table is generated by applying a color quantizer over the image data store to determine a set of quantized image colors and computing a global codebook from the set that minimizes the mean standard error over the sample images.

11. The method of claim 10, wherein the color quantizer is a median-cut color quantizer used to quantize the sample images to meet a rate distortion criterion;

and a tree vector quantizer is used to compute the global color table codebook.

12. The method of claim 9, wherein the number of distinct colors is estimated by performing a fuzzy binary search.

13. The method of claim 9, wherein refining the estimated number comprises successively decreasing the number of colors beginning with the estimated number of colors, executing a median-cut color quantizer, and calculating the resulting error, until an error threshold is reached.

14. The method of claim 9, wherein mapping comprises defining a map from an arbitrary color in the original image to a quantized color in the quantized image and from there to a color in the global color table.

15. The method of claim 9, wherein mapping comprises using (i) an inverse table that maps indices from an original image color space to indices in a color table of the quantized image, and (2) an inverse table that maps indices from the color table of the quantized image to indices of global color table.

16. The method of claim 9, wherein a non-linear filter is applied to the original image before quantizing the original image.

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

retrieve images from an image data store;

generate a global color table for the image data store;

for each of a plurality of original images in the image data store, estimate an estimated number of distinct colors in an original image, use the estimated number to determine a number N of colors to use to represent the original image as a quantized image, quantize the original image into a quantized image of N colors, map each of the quantized image colors to a resultant color in the global color table, and generate a color feature vector of color descriptors to represent the image, each color descriptor indicating a frequency of occurrence of a resultant color in the image;

receive from a user a query comprising a query image;

use the query image to create a query color feature vector of one or more descriptors, each descriptor comprising (i) a color index that references a location of a color in the global color table and (ii) a relative occurrence of the color as a quantized color within the query image; and

compare the query color feature vector to the color feature vectors of the plurality of images to identify images among the plurality of images that satisfy the query.

18. The program of claim 17, wherein:

the global color table is computed from the image data store.

19. The product of claim 17, wherein instructions to estimate the estimated number of distinct colors include instructions to perform a fuzzy binary search for the number of colors using an error threshold based on a peak signal-to-noise ratio.

20. The product of claim 17, wherein a non-linear filter is applied to each of the images the image is quantized.

21. The product of claim 17, wherein instructions to map colors include instructions to:

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

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

22. The product of claim 17, further comprising instructions to:

apply a medium-cut quantizer to the plurality of images to generate a collection of images satisfying one or more rate distortion criteria; and

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