Method for digital compression of color images

• US 6,356,588 B1
• Filed: 04/17/1998
• Issued: 03/12/2002
• Est. Priority Date: 04/17/1998
• Status: Expired due to Fees

• Current Assignee: Ayao Wada
• Original Assignee: Ayao Wada
• Inventors: Otto, Anthony H.
• Primary Examiner(s): Kelley, Chris
• Assistant Examiner(s): VO, TUNG T
• Application Number:
  US09/061,884
• Time in Patent Office: 1,425 Days
• Field of Search: H04/N.712, H04/B.166, 375/240, 375/240.01, 375/240.02, 375/240.03, 375/240.15, 348/441, 348/442, 348/443, 382/298, 382/232, 382/284, 382/251, 364/715.02, 395/154, 395/109, 358/433, 358/432
• US Class Current: 375/240.03
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H04N 1/64 Systems for the transmission or the storage of the colour picture signal; Details therefor, e.g. coding or decoding means therefor H04N19/00 takes precedence
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding

Abstract

The method for digital compression of color images digitally compresses color identification photographs into 512 to 2,048 bytes for storage of rectangular images in smart cards and databases. The method operates in the YCrCb color space and includes a novel color space conversion method for converting digital image data from a 15- or 24-bit RGB (Red-Green-Blue) color space to the YCrCb (Luminance-Chrominance) color space. The compression method uses a lookup table for color space conversion. A unique chromakey method is used to replace the background with a solid color to increase the visual quality of the compressed image, and to automate and simplify the chromakey process.

Claims

1. A method for digital compression of an image such as an identification photograph for storage of the image, said image containing image data consisting of a plurality of scan lines of pixels with scalar values, comprising the steps of:

filtering the image data by evaluating the scalar values of individual pixels in the image with respect to neighboring pixels by evaluating each said individual pixel as a target pixel in a sequence of five pixels, including two pixels on either side of the target pixel and the target pixel itself, for each said target pixel to determine an output value for the target pixel, wherein said step of filtering comprises determining an average of the data for a window of the pixels immediately surrounding the target pixel for those pixels surrounding the target pixel that are within a specified range of values, according to the following protocol;

if all five pixels are within the specified range, the output target pixel is determined to be the average of the four pixels in a raster line, two on each side of the target pixel;

if the two pixels on either side are within a specified range and both sides themselves are within the range, the filtered output target pixel data is determined to be the average of the two pixels on each side of the target pixel;

if the two pixels on either side of the target pixel and the target pixel itself are within a specified range, and the other two pixels on the other side are not within the specified range, the output target pixel is determined to be the average of the two neighboring pixels closest in value to the target pixel values and that fall within the specified range;

if the five pixels are all increasing or decreasing, or are within a specified range, the output target pixel is determined to be the average of two pixels on whichever side of the target pixel is closest in value to the target pixel; and

if the five pixels in the window do not fit into any of the prior cases, the output target pixel is unchanged; and

statistically encoding the image data by dividing the image into an array of blocks of pixels, and encoding each block of pixels into a fixed number of bits that represent the pixels in the block.

2. A method for digital compression of an image such as an identification photograph for storage of the image, said image containing image data consisting of a plurality of scan lines of pixels with scalar values, comprising the steps of:

filtering the image data by evaluating the scalar values of individual pixels in the image with respect to neighboring pixels;

replacing background in the image being compressed with a scalar value, in order to reduce noise in the image, and to increase the visual quality of the compressed image, by calibrating an initial chromakey value and background scalar value, wherein said step of calibrating comprises capturing at least one calibration image of the background prior to capturing an image without a subject of interest in place, consisting substantially of background pixels, and determining the average and standard deviation of said at least one calibration image to set at least an initial chromakey scalar value and range; and

statistically encoding the image data by dividing the image into an array of blocks of pixels, and encoding each block of pixels into a fixed number of bits that represent the pixels in the block.

3. A method for digital compression of an image such as an identification photograph for storage of the image, said image containing image data consisting of a plurality of scan lines of pixels with scalar values, comprising the steps of:

filtering the image data by evaluating the scalar values of individual pixels in the image with respect to neighboring pixels;

replacing background in the image being compressed with a scalar value, in order to reduce noise in the image, and to increase the visual quality of the compressed image, by calibrating an initial chromakey value and background scalar value, wherein said step of calibrating comprises capturing an image with a subject of interest in place, and beginning in the upper-left and upper-right comers of said at least one calibration image, collecting pixels down and towards the center of said image until an edge or image boundary is encountered, and determining the average and standard deviation of those pixels to set at least an initial chromakey value and range; and

statistically encoding the image data by dividing the image into an array of blocks of pixels, and encoding each block of pixels into a fixed number of bits that represent the pixels in the block.

4. A method for digital compression of an image such as an identification photograph for storage of the image, said image containing image data consisting of a plurality of scan lines of pixels with scalar values, comprising the steps of:

filtering the image data by evaluating the scalar values of individual pixels in the image with respect to neighboring pixels;

replacing background in the image being compressed with a scalar value, in order to reduce noise in the image, and to increase the visual quality of the compressed image, by calibrating an initial chromakey value and background scalar value, wherein said step of calibrating comprises manually specifying an initial chromakey value and range without respect to the properties of an individual image being captured prior to image capture; and

statistically encoding the image data by dividing the image into an array of blocks of pixels, and encoding each block of pixels into a fixed number of bits that represent the pixels in the block.

5. A method for digital compression of a color image such as a color identification photograph for storage of the color image, said color image containing color image data consisting of a plurality of scan lines of pixels with color values, comprising the steps of:

filtering the color image data by evaluating the color values of individual pixels in the color image with respect to neighboring pixels; and

statistically encoding the color image data by dividing the color image into an array of blocks of pixels, and encoding each block of pixels into a fixed number of bits that represent the pixels in the block, wherein said step of statistically encoding the color image data comprises classifying each said block according to a plurality of categories, quantifying each said block, and compressing each said block by codebook compression using minimum redundancy, variable-length bit codes, wherein said step of classifying each said block comprises classifying each of said the blocks in one of four categories;

null blocks exhibiting little or no change from the higher level or previous frame, uniform blocks having a standard deviation less than a predetermined threshold, uniform chroma blocks having a significant luminance component to the standard deviation, but little chrominance deviation, and pattern blocks having significant data in both luminance and chrominance standard deviations.

6. The method of claim 5, wherein said step of statistically encoding the color image data comprises determining a first sample moment of each block as the arithmetic mean of the pixels in the block, determining a second sample moment of the pixels in the block, and determining a selection map of those pixels in the block having color values darker or lighter than a quantizer set to the first sample moment, along with a count of the lighter pixels.

7. The method of claim 6, wherein said step of statistically encoding the color image data further comprises determining the sample variance and the standard deviation of the pixels in the block based upon the first and second sample moments.

8. The method of claim 5, further comprising the step of replacing background in the color image being compressed with a solid color, in order to reduce noise in the image, and to increase the visual quality of the compressed image.

9. The method of claim 8, wherein said step of replacing background in the color image being compressed with a solid color comprises calibrating an initial chromakey value and color of the background color.

10. The method of claim 9, wherein said step of calibrating comprises capturing at least one calibration image of the background prior to capturing an image without a subject of interest in place, consisting substantially of background pixels, and determining the average and standard deviation of said at least one calibration image to set at least an initial chromakey color and range.

11. The method of claim 9, wherein said step of calibrating comprises capturing an image with a subject of interest in place, and beginning in the upper-left and upper-right corners of said at least one calibration image, collecting pixels down and towards the center of said image until an edge or image boundary is encountered, and determining the average and standard deviation of those pixels to set at least an initial chomakey value and range.

12. The method of claim 9, wherein said step of calibrating comprises manually specifying an initial chromakey value and range without respect to the properties of an individual image being captured prior to image capture.

13. The method of claim 5, further comprising the step of determining the number of bits to be preserved for each component of the block after each said block is classified.

14. The method of claim 13, further comprising the step of reducing the number of bits for the Y and Cr/Cb components independently for each classification.

15. The method of claim 13, further comprising the step of matching the texture map of the block with one of a plurality of common pattern maps for uniform chroma and pattern classified blocks.

16. The method of claim 13, further comprising the step of preserving all components of each said block for pattern blocks.

17. The method of claim 13, further comprising the step of preserving the mean luminance and chrominance, standard deviation luminance, and a selection map for uniform chroma blocks.

18. The method of claim 13, further comprising the step of preserving the mean values for all three color components.

19. The method of claim 5, wherein said step of filtering comprises evaluating each said individual pixel as a target pixel and a plurality of pixels in close proximity to the target pixel to determine an output value for the target pixel.

20. The method of claim 19, wherein said step of filtering comprises evaluating a sequence of five pixels, including two pixels on either side of the target pixel and the target pixel itself, for each said target pixel.

21. The method of claim 20, wherein said step of filtering comprises determining an average of the data for a window of the pixels immediately surrounding the target pixel for those pixels surrounding the target pixel that are within a specified range of values, according to the following protocol:

if all five pixels are within the specified range, the output target pixel is determined to be the average of the four pixels in a raster line, two on each side of the target pixel;

if the two pixels on either side are within a specified range and both sides themselves are within the range, the filtered output target pixel data is determined to be the average of the two pixels on each side of the target pixel;

if the two pixels on either side of the target pixel and the target pixel itself are within a specified range, and the other two pixels on the other side are not within the specified range, the output target pixel is determined to be the average of the two neighboring pixels closest in value to the target pixel values and that fall within the specified range;

if the five pixels are all increasing or decreasing, or are within a specified range, the output target pixel is determined to be the average of two pixels on whichever side of the target pixel is closest in value to the target pixel; and

if the five pixels in the window do not fit into any of the prior cases, the output target pixel is unchanged.

22. The method of claim 5, further comprising the step of converting digital color image data to the YCrCb (Luminance-Chrominance) color space.

23. The method of claim 22, wherein said step of converting digital color image data to the YCrCb (Luminance-Chrominance) color space comprises converting the color image data from the RGB (Red-Green-Blue) color space.

24. The method of claim 22, wherein said step of converting digital color image data to the YCrCb (Luminance-Chrominance) color space comprises utilizing lookup tables of selected color values for color space conversion.

25. The method of claim 24, wherein said step of converting digital color image data to the YCrCb (Luminance-Chrominance) color space comprises utilizing nine 256-entry one-byte lookup tables containing the contribution that each R, G and B make towards the Y, Cr and Cb components.