GB2240448A - "High quality color image compression system" - Google Patents

Abstract

A color image compression system and method provides an improved technique for combining various image processing techniques to obtain high quality color image compression. The present invention provides color image compression, especially for high quality original images that require up to 24 bits of data per pixel. The present invention utilizes a delta quantizing technique between an array of pixels to provide improved color image compression. <IMAGE>

Description

2:2.4 C) el -El a 1 "HIGH QUALITY COLOR IMAGE COMPRESSION SYSTEM" The

present invention relates to a color image compression system and method. More particularly, the present invention relates to color image compression techniques for high quality original color images that require up to 24 bits of data per pixel. The original color images can contain up to 16 million different colors.

Various color compression algorithms for original color images are known in the art. Although 24-bit per pixel color images (hereinafter referred to as "true color") are not yet in widespread use, it is expected that there will be a need for such true color images for color facsimile, color copiers, color printers, and color scanners. Most work regarding color image transmission done up to the present time has been related to color image transmission.

Because of the amount of data contained in a "true color" image, it is very important to be able to compress the data before transmission in order to save the expense of using a telecommunications bandwidth. Algorithms suitable for adoption by the CCITT (Consulting Committee on International 1 Telephone and Telegraph have been developed). At the present time it is believed that an adaptive discrete cosine transform (ADCT) will be the algorithm adopted by the CCITT.

It would be highly desirable to provide an improved high quality color image compression system and method which is suitable for color image compression transmission techniques.

It is an object of the present invention to provide an improved high quality color image compression system and method.

According to one aspect of the present invention, there is provided a color image compression method comprising the steps of acquiring first color image data representative of a color image in a first format having a plurality of first color planes, converting the acquired-color image data to a second, different format having a plurality of second color planes, spatially reducing the color image data in said second format to form spatially reduced data, and delta quantizing one or more color planes of said spatially reduced data to form compressed color image data representative of said color image.

According to another aspect of the present z 1 is invention, there is provided a color image compression method comprising the steps of spatially reducing color image data having a plurality of color planes to form spatially reduced color image data, and delta quantizing said spatially reduced data to form a compressed color image.

According to still another aspect of the present invention, there is provided a color image compression system comprising means for acquiring first color image data representative of a color image in a first format having a plurality of first color planes, means for converting the acquired color image to a second, different format having a plurality of second color planes, means for spatially reducing the color image data in said second format to form spatially reduced data, and means for delta quantizing one or more color planes of said spatially reduced data to form compressed color image data representative of said color image.

other objects, features and advantages of the present invention will become apparent from the following detailed description when taken in conjunction with the accompanying drawings.

The accompanying drawings which are incorporated in and form a part of this specification - 4 illustrate an embodiment of the invention and, together with the description, serve to explain the principles of the invention.

Fig.1 depicts a color image compression flow chart according to the present invention.

Fig.2 depicts a color image decompression flow chart according to the present invention.

Fig.3 depicts a sample image illustrating the acquisition of a true color image.

Fig.4 depicts a kernel representation utilized in the present invention.

Fig.5 depicts a conversion from RGB to YIQ color space.

Figs.6A, 6B, 6C and 6D depict spatial reduction of the YIQ color planes.

Fig.7 depicts a series of pixels after spatial reduction.

Fig.8 depicts an illustration of a particular set of pixel values about to be delta quantized.

Fig.9 depicts a delta quantized table.

Figs.10 and IOA depict typical values of a delta quantized table used for Y, I and Q data.

Fig.11 depicts an apparatus for a color compression system.

1 The present invention provides a novel means and method of combining various image processing techniques to obtain high quality color image compression. The present invention recognizes how the human eye perceives color and frequency information in a quality color image. It is desired that the color image should degrade "gracefully" at high compression ratios by becoming "softer" and geometric shapes not appear.

Briefly, the improved color image compression system and method according to the present invention includes the steps of acquiring a true color image, usually in an RGB (Red, Green, Blue) format. The next step includes the conversion of the RGB acquired data from RGB color space to YIQ color space. The present invention next provides for spatial reduction of the YIQ planes. The next step of the color image compression system provides for the delta quantizing of each of the color planes followed by run length limited (RLL)/entropy encoding of the reduced image data and, finally, storing and transmitting the compressed color images.

Reference will now be made in detail to the preferred embodiment of the invention, an example of which is illustrated in the accompanying drawings.

- 6 1 While the invention will be described in conjunction with the preferred embodiment, it will be understood that it is not intended to limit the invention to that enbodiment. on the contrary, it is intended to cover alternatives, modifications and equivalents as may be included within the spirit and scope of the invention as defined by the appended claims.

Referring now to Fig.1, a color image compression flow chart according to the present invention is depicted. The color image compression flow chart of Fig.1 illustrates the sequence of steps from acquiring the color image to the,storing and transmission of the compressed color image.

In Fig.1, the first step 11 includes the acquisition of a "true" color image, usually in a RGB (red, green, blue) format. The acquisition of color image data in an RGB format is a well known technique.

The next step 12 includes precompression processing.

The next step 13 provides for the conversion from RGB color space to YIQ color space, which is also a known technique.

The next step 14 provides for spatial reduction on the YIQ color space (on the YIQ planes).

Step 15 provides for a delta quantizing of each of the YIQ color planes, as will be described in further detail below.

Step 16 provides the run length limited (RLL) and entropy encoding of the reduced image data.

Finally, step 17 provides for the storing and transmitting of the high quality color compression image data according to the present invention.

Further details and aspects of the color image compression flow chart of Fig.1 will be described in more detail in connection with the remaining Figures.

Similarly, Fig.2 depicts a color image decompression flow chart according to the present invention.

In Step 21, the decompression algorithm accesses the compressed color image file.

In Step 22, the decompression algorithm decodes the run length limited/entropy code of the compression algorithm.

In Step 23, the decompression algorithm rebuilds the YIQ color planes from the delta quantized table.

In Step 24, the decompression algorithm reverses (expands) the spatial reduction to restore a 1 full resolution color image of the compressed color images.

In Step 25, the decompression algorithm converts the YIQ color space to RGB color space.

Step 26 provides post decompression color image processing according to the decompression algorithm.

Finally, at Step 27, the final image which is decompressed is displayed on a CRT or output on another color device.

Referring now to Figs.3-10, aspects of the decompression algorithm of Fig. 1 will now be described in more detail.

Fig.3 shows a sample color image with parameters to describe a sample image representation. Fig.3 depicts the acquisition of a true color image, usually in RGB format, which is Step 11 in Fig.l. In Filg.3, the total number of pixels in a color image is given in R rows and C columns. Each pixel is typically represented by 24 bits of data ("true" color). The 24 bits of data are typically broken down to eight bits each for red, green and blue (RGB). The color image can be from a plurality of input sources such as a color scanner, mass storage device, video capture device, and the like. Some prior art approaches require the whole image to be buffered before color processing may start. Other types require eight lines or sixteen lines to be buffered. The present invention provides for color image compression on a minimum of just two lines of pixel data, e.g., R1, R2 from Fig.3. This minimizes the buffer requirements in contrast with other prior art approaches.

The pre-compression processing step 12 of Fig.1 will now be described in more detail. Before any compression takes place, it is often desirable to pass a convolution across the color image. The present high quality color compression technique according to the present invention is improved if the image is pre-filtered by a convolution that performs both edge enhancement and a certain degree of smoothing. An example of such a kernel is illustrated in Fig.4. It should be noted that 3 X 3 or 5 X 5 convolutions can be applied. The number illustrated in Fig.4 serves only as an example. Kernels are normally, but not necessarily, symmetric.

The Step 13 conversion from RGB color space to YIQ color space will now be described in more detail.

The standard RGB format is desirably i - 10 1 converted to YIQ color space. Standard linear transformatins are used, one of which is depicted in Fig.5. The transformation may be accomplished through the use of lookup tables as opposed to matrix multiplication. The transformation to YIQ color space provides the ability to perform spatial resolution reduction on each plane (each YIQ plane) individually. Typically, the Q plane can be more spatially reduced than the I plane, while the I plane can be reduced more than the Y plane.

The Step 14 of spatial reduction on the YIQ planes of Fig.1 will now be described in more detail.

Spatial reduction is applied to each of the three planes (YIQ planes), depending upon the compression ratio required or desired. For very high quality results, but a relatively low compression ratio (about eight bits per pixel), no spatial reduction need be used. For around three to four bits per pixel, the scheme depicted in Figs.6A, 6B and 6C might be utilized.

In Fig.6A, no spatial reduction is used on the Y plane. In Fig.6B, a 2:1 spatial reduction is utilized on the I plane. In Fig.6C, a 4:1 reduction is utilized on the Q plane.

The method used to get the average value Z i i - 11 1 is may be varied. For example, the average of the I plane pixel may be depicted, as in Fig.6D, and what I avg is should be determined. It is possible to use the following calculations:

1) 1 avg " 1 11 2) 1 avg (1 11 + 1 12 + 1 21 + 1 22)/4 3) Some other weighted average of surrounding pixels The delta quantizing Step 15 of each color plane (YIQ planes) will now be described in more detail. Reference is made to the example depicted in Fig.7, which shows a series of pixels, after spatial reduction. The illustration represents one of the three color planes (YIQ). It should be assumed that the data in Fig.7 is from the Y plane, where the ABC pixels are previously processed pixels, the "?" is the current pixel under examination, where the 11/11 are yet unprocessed pixels, and where the indicates that error diffusion will be applied. In Fig.7, the "All pixel is proximate to the "?" pixel, being within the scan line above and left of the 117.11 pixel. similarly, the "B" pixel is directly or immediately above the "?" pixel, and the "C" pixel is proximate (directly to the left of) to the 111111 pixel.

is In order to understand the above aspects of the present invention, one particular set of values should be to considered to be delta quantized as depicted in Fig.8. Focus in on one of the eight pixels of most interest in Fig.7 and hypothetical values as illustrated in Fig.8 should be assigned.

In Fig.8, the numbers 125, 130 and 102 have already been quantized. It should,be assumed that the prequantization value for 117?11 is 147. The first task is to decide from which pixel to "delta quantize the 11?11 pixel". The present invention utilizes a method which calculates the absolute difference of (B - A) and (C -A). Whichever absolute difference is greater, the I?" pixel is quantized from that one pixel. In the example of Fig.8, 102 is Clearly further from 125 that 130. Thus, the 111"I pixel is quantized from 102.

Fig.9 depicts a representation of a delta quantized table. The delta quantized table is an asymmetric nonlinear quantized table which varies depending on the YIQ plane. A quantized table can be made up of various delta quantized values, say 12, in one preferred embodiment. These delta quantized values are represented in Fig.9.

In Fig.9, the N stands for a negative 1 is value, the P stands for a positive value. Note that any number of values can be used, although the value 12 is the one used in the preferred embodiment.

In Fig.9, the table is asymmetric, i.e., ABS(N3-N2) is not necessarily equal to ABS(P3-P2). The reason for this is that the human eye perceives small decreases in intensity more easily than small increases.

The table in Fig.9 is also non-linear, i.e., (NX-N X_ 1) greater than symbol (N X_ I-Nx-2). Again, this is attributed to the human eye characteristic that large intensity charges are easily perceived, but the magnitude of such changes is hard to judge. Thus, more values can be assigned to the more critical "small" steps.

Figs.10 and 10A depict typical tables used for Y, I and Q data.

Another feature of the present invention is that delta quantize tables that change between odd and even pixel numbers are used. For example, for the first pixel to be delta quantized in a line, the table in Fig.10 is used. Then, when the second pixel in the line is delta quantized, the values are slightly changed, as shown in Fig.10A.

The I and Q data can be delta quantized in 1 a similar way. This improves the compression considerably. The main reason is that the value of the Z token now stretches from +1 to -1 from pixel to pixel. This provides a so-called "wide zero" effect, resulting in longer runs of Z tokens and subsequently greater compression ratios.

For pixels 1, 3, 5, 7, etc., the table in Fig.10 is used as the delta quantize table. For pixels 2, 4, 6, 8, etc., the table in Fig.10A is used. Given the delta quantized table example in Fig.10, it is now possible to complete the example of Fig.8.

Using the fact that 102 is a greater distance from 125 than 130, the I"?" pixel's prequantized value is 147 as a delta of +45. Looking at Fig.10, + 45 is closest to the P3 value which is assigned +37. Thus, the delta quantized value of becomes 102 + 37, i.e., 139.

When an error on the IIVI pixel of negative eight is introduced, it is possible to limit the effect of this quantization error by error diffusing the difference to neighboring unquantized pixels. The four 11/11 pixels are, for example, increased by two (if the error is to be fully distributed).

Some special cases should be addressed at 1 this time.

1) Border conditions are set so that the pixels have values 128, so that there is always something to quantize from.

2) If a 111.2111 pixel data is exactly halfway between two table values, one of two actions may be taken. The first is to randomly round the value to the next higher or lower value, but never in the same direction at all times as this could lead to chromatic distortions. Secondly, the delta quantized table can be set so that the above scenario cannot occur. This is achieved by making all (P X-P x- 1) and (Nx-Nx-1) even.

The RLL/entropy encoding Step 16 of Fig.1 will now be described in more detail below.

The value in the tables shown in Figs.10 and 10A tend to lead to occurrences of the zero value. Many of these occur in runs. significant gains in coding result because of this phenomenon.

P1 and N1 are considered the value most likely to occur. They receive the most privileged tokens Al and B1. A decision has to be made which of these two values received the 00 code and which the 01 code. A good method for making this decision seems to be to choose the value that is closest to 16 1 zero.

is A sample RLL/entropy table is shown below in Table I:

where: f W 11) TABLE I

00 000 001 01 lof 11of illoof = N4/P4 11101of = N5/P5 11101100 = PN6 1110111[1]0W = N16 + 9 + W consecutive zeros 1111[1]0 = N+2 consecutive Zeros = Bl (if after Z) = Isolated Z = Bl (if not after Z) = Al = N2/P2 = N3/P3 = a single bit (O=N;1=P) = 4 bits, evaluated as number w=0-15 = N consecutive l's The store and transmit compression image Step 17 of Fig.1 will now be described in more detail.

Fig.2 shows the decompression sequence. It follows the reverse sequence of the compression 1 - 17 1 algorithm of Fig.l.

The raw compressed file is taken and the RLL/entropy table is used to generate the values Z, N1, PI, etc., for the entire image.

Color planes are rebuilt using the reverse process that the delta quantizer used. For example:

Y data 137 132 169 131 P1 N1 P2 Considering the Pi value above, because 137 is "further" from 130 than 131, it must have been delta quantized from 137. Thus, the P1 with 137 + 7 (taken from P1 in Fig.10) = 144 should be replaced.

137 132 169 131 144 N1 P2 Now the N1 uses the 144 due to the fact that 144 is further from 137 than 132. Thus, replace N1 by 144-7 = 137 (taken from N1 in Fig.10A) should be replaced, and so on.

once finished, this process leaves a full image that is complete except for any spatial "reverse 1 spatial reduction" that might be needed.

"Reverse spatial reduction" will depend upon the method that was used to do the original reduction. Referring to Step 24, if I avg = I,,, then all missing pixels with 1 11 should be replaced. If I avg was the average of four pixels, then the average is used to replace all missing pixels. More sophisticated schemes may be used to limit error sizes.

With all color planes restored to full resolution, YIQ can be converted back to RGB color space.

Smoothing/sharpening filters may be applied to the new image to remove unwanted characteristics of the compression/decompression stages.

Fig.11 shows an apparatus 50 for a color compression system utilizing aspects of the present invention. In Fig.11, the system 50 includes a color image scanner 52 that typically produces 24 bits per pixel at 300 dots per inch. A typical image size is approximately 30 Mbytes of data for an 8.5 x 11 original document. The scanner 52 is connected via cable 54 to a PC interface. The cable 54 is typically SCSI, GPIB or the like.

-..

1 could be a on a single Fig. 11. Fol The PC 56 includes a color monitor 60 to view scanned images. PC 56 either runs an algorithm in software or, as an alternative, hardware performs compression on a.scanned image. The hardware can be designed and implemented by one of ordinary skill in the art when utilizing aspects of the present invention.

The output of the compression algorithm compressed image file small enough to fit 1.4 Mbyte floppy disk 64, as depicted in example, by using 2:1 spatial compression on the Y plane, 4:1 on the I and Q planes, and then delta quantizing, the typical reduction is about 25:1. Thus, the original 30 Mbyte file becomes about 1.2 megabytes.

The foregoing description of a preferred embodiment of the invention has been presented for purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed, and obviously many modifications and variations are possible in light of the above teaching. The present embodiment was chosen and described in order to best explain the principles of the invention and its practical application to thereby enable others skilled in the

1 - 20 1 I art to best utilize the invention in various embodiments and with various modifications as are suited to the particular use contemplated. It is intended that the scope of the invention be defined by the claims appended hereto.

..r- T111 - 21

Claims (25)

1 WHAT IS CLAIMED IS

1. A color image compression method comprising the steps of acquiring first color image data representative of a color image in a first format having a plurality of first color planes, converting the acquired color image data to a second, different format having a plurality of second color planes, spatially reducing the color image data in said second format to form spatially reduced data, and delta quantizing one or more color planes of said spatially reduced data to form compressed color image data representative of said color image.

2. A method as in Claim 1, including the step of encoding said compressed image data.

3. A method as in claim 2, including the step of storing said encoded compressed image data.

is

4. The method as in Claim 3, including the step of transmitting said encoded compressed image data.

5. A color image compression method comprising the steps of spatially reducing color image data having a plurality of color planes to form spatially reduced color image data, and delta quantizing said spatially reduced data to form a compressed color image.

6. A color image compression system as in c 1 1 Claim 5, wherein said delta quantizing step includes the step of delta quantizing each color plane of said spatially reduced data.

7. A color image compression system comprising means for acquiring first color image data representative of a color image in a first format having a plurality of first color planes, means for converting the acquired color image to a second, different format having a plurality of second color planes, means for spatially reducing the color image data in said second format to form spatially reduced data, and means for delta quantizing one or more color planes of said spatially reduced data to form compressed color image data representative of said color image.

1

8. A system as in Claim 7, including means for encoding said compressed image data.

9. A system as in Claim 8, including means for storing said encoded compressed image data.

10. A system as in Claim 9, including means for transmitting said encoded compressed image data.

11. A color image compression system as in Claim 10, wherein said delta quantizing means includes means for delta quantizing each color plane of said spatially reduced data.

4 1

12. The system as in claim 11, wherein said first format is a red-green-blue (RGB) format.

13. The system as in Claim 12, wherein said second format is a YIQ format.

14. A system as in Claim 13, wherein said means for delta quantizing include a delta quantized table for storing delta quantized values for each of said planes.

15. A system as in Claim 14, wherein said image includes at least two lines of pixel data and wherein each pixel is represented by a certain number of bits of data.

4 1 - 26

16. A system as in Claim 15, wherein a value of a certain pixel to be delta quantized is determined by calculating the difference between first and second pixels most proximate to said certain pixel and between said first pixel and a third pixel most proximate to said certain pixel within said first and second scan lines, whichever is greater.

17. A system as in Claim 16 wherein said first pixel is a pixel within a scan line and immediately above and left of said certain pixel.

1

18. A system as in Claim 17 wherein said second pixel is within the scan line and immediately above said certain pixel.

1

19. A system as in Claim 18, wherein said third pixel is within the same scan line and immediately left of said certain pixel.

20. A system as in claim 14, wherein said delta quantizing table is linear.

21. A system as in Claim 14, wherein said delta quantizing table is non-linear.

22. A system as in Claim 14, wherein said delta quantizing table is asymmetric.

1

23. A color image compression system comprising means for spatially reducing color image data having a plurality of color planes to form spatially reduced color image data, and means for delta quantizitg said spatially reduced data to form a compressed color image.

24. A color image comprission method substantially as hereinbefore described with reference to the accompanying drawings.

25. A color image compression system substantially as hereinbefore described with reference to the accompanying drawings.

Published 1991 at7br Patent Offlee. State House, 66/71 High Holborn. Loondon WCIR 47P. Further copies Tnay be obtained from Sales Branch, Unit 6. Nine Mile Point. Cvmre"ch. Cross Keys, Newport. NPI 7HZ. Printed by Multiplex techniques lid. St Mary Cray. Kent.

1