Image analysis – Image compression or coding
Reexamination Certificate
1999-03-15
2002-06-11
Grant, II, Jerome (Department: 2624)
Image analysis
Image compression or coding
C382S245000, C358S539000
Reexamination Certificate
active
06404927
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to compression of color image data, and in particular to compression using control point generation for run length encoding.
Image data coming out of one-chip area sensing imagers, such as one-chip Charged Coupled Device (CCD) or Complementary Metal Oxide Silicon (CMOS) Focal Plane Array (FPA) image sensors, are inherently sub-sampled in spatial domain. Most of the commercial imager products use a pattern of either three or four colors to construct a mosaic Color Filter Array (CFA), which performs the sub-sampling in each color plane. This results in the interlaced output data of the color components in each line from the imagers.
FIG. 1
illustrates a portion of an image sensor
10
(a Bayer CFA on FPA CCD/CMOS sensor). Each physical location corresponds to a single color which is generated either by a filter for that color, or by reflecting off of a document from a Light Emitting Diode (LED) of that color at that position. For example, shown is a Red, Green, Blue (RGB) mosaic which shows in line
1
alternating blue and red positions, line
2
alternating red and green positions, then in line
3
blue and red again, etc. To-establish all three color values at a particular pixel location, such as location
12
, the green value can be used directly since it is on position
12
. Since no red value is exactly on that position, the red value can be interpolated from the surrounding red values. Similarly, the blue value can be interpolating from the surrounding blue values. Similarly, all three color values can be either read or interpolated for each pixel position.
Variable length image compression algorithms will record a color value, and then indicate a length along the line to a change in that color value. Thus, the color value need not be recorded and transmitted at every location, but only when it changes. Two typical algorithms are used for such variable length image compression.
(1) A first method recovers the sub-sample color planes by interpolation to obtain luminance information. In other words, the RGB is converted into a YUV format. Alternately, another color scheme rather than RGB may be used, such as Cy, Ye, G, Mg. The luminance value in this version is then used to generate a single set of control points for all interpolated components. A “control point” identifies where a change in the luminance occurs which is more than a change threshold. A disadvantage of this approach is that it requires data interpolation, which can costly, and it actually boosts the data volume prior to subsequently compressing it. In addition, generating control points based only on luminance information can cause color distortion. After the control points are generated, the run length and color change information is provided to a Huffman Look-Up Table (LUT) which provides a compressed output. One example of a compression technique using a Huffman lookup table was set forth in U.S. Pat. 5,675,382. Typically, the prior art will use multiple Huffman encoding tables as in the above patent, or will use a single, large Huffman encoding table.
(2) A second approach is to generate control point sets separately for each color component in a line. Thus, for example, control points may be generated separately for red, then separately for green, and separately for blue. A disadvantage to this approach is that the run length information between the control points contains some redundant length information, especially in image areas with high frequency content. The separate control point sets also make it difficult to apply parallel processing techniques to realize fast software decompression.
SUMMARY OF THE INVENTION
The present invention provides a simple, cost-effective compression circuit which compresses raw color data without interpolation. Color points common to all the colors in a line are generated each time the change in any one of the colors exceeds the color change threshold. The change in the other color is recorded at the same time even though it doesn't exceed the minimum change threshold.
Providing a common run length for multiple colors allows efficient, parallel decompression in a processor which has parallel processing capability for multiple pixel values. This parallel processing capability offsets the extra computation needed since raw color data is sent, rather than interpolated color data. However, even without the offset, the processing power of a typical host computer allows the interpolation to be done at the host.
In a preferred embodiment, the amount of circuitry required for data compression is further reduced by using a single, small Huffman look-up table (LUT). this is done by providing each color value and then the run length in sequence as inputs to the same, small LUT. In one embodiment, a data packer circuit converts the uneven bit length of these three items into a common bit length. In particular, the color value changes may be encoded as 8 bits plus a sign bit, for a total of 9 bits. The run length may be encoded as 6 bits. The data packer takes one bit from each of the color values and adds it to the run length data group, to give three groups of 8 bits.
In a further aspect of the invention, the data packing is done by using the sign bit from each of the color bits to add to the run length bit field. By using the sign bits, the encoding efficiency of the Huffman LUT is maximized, by not breaking up the color difference values. By using the sign bits as the least significant bits of the run length data block, it minimizes the impact on variations of the run length.
For further understanding of the nature and advantages of the invention, reference should be made to the following description taken in conjunction with the accompanying drawings.
REFERENCES:
patent: 4847677 (1989-07-01), Music
patent: 4914508 (1990-04-01), Music
patent: 4968135 (1990-11-01), Wallace et al.
patent: 341272 (1993-09-01), None
Agi Iskender
Li Jun
Exar Corporation
Grant II Jerome
Townsend and Townsend / and Crew LLP
LandOfFree
Control point generation and data packing for variable... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Control point generation and data packing for variable..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Control point generation and data packing for variable... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2941267