Compact color feature vector representation

• US 7,792,887 B1
• Filed: 12/17/2007
• Issued: 09/07/2010
• 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): Wu; Yicun
• Application Number:
  US11/958,231
• Time in Patent Office: 995 Days
• Field of Search: 707/999.107, 382/165, 382/173, 382/240
• US Class Current: N/A
• 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 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, 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;

receive 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 a color index that references a location of a color in the global color table; 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.

2. The program product of claim 1 wherein the global color table is computed from the image data store.

3. The program product of claim 1 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.

4. The program product of claim 1 wherein a non-linear filter is applied to each of the images to quantize the images.

5. The program product of claim 1 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.

6. The program product of claim 1, 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.

7. A system comprising:

an image data store containing a plurality of images;

a global color table for the image data store; and

a computer program comprising instructions operable to;

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, 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;

receive 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 a color index that references a location of a color in the global color table; 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 global color table is computed from the image data store.

9. The system of claim 7 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.

10. The system of claim 7 wherein a non-linear filter is applied to each of the images to quantize the images.

11. The system of claim 7 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.

12. The system of claim 7, further comprising instructions operable 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.

13. A computer-implemented method comprising:

retrieving images from an image data store;

generating a global color table for the image data store;

for each of a plurality of original images in the image data store, estimating 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, mapping each of the quantized image colors to a resultant color in the global color table, and generating a color feature vector of color descriptors to represent the image;

receiving a query comprising a query image;

using the query image to create a query color feature vector of one or more descriptors, each descriptor comprising a color index that references a location of a color in the global color table; and

comparing 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.

14. The method of claim 13 wherein the global color table is computed from the image data store.

15. The method of claim 13 wherein estimating the estimated number of distinct colors includes:

performing a fuzzy binary search for the number of colors using an error threshold based on a peak signal-to-noise ratio.

16. The method of claim 13 wherein a non-linear filter is applied to each of the images to quantize the images.

17. The method of claim 13 wherein mapping colors includes:

generating 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

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

18. The method of claim 13, further comprising:

applying a medium-cut quantizer to the plurality of images to generate a collection of images satisfying 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.