Quantization method for use in image compression

A novel quantization method for use in image compression techniques provides a 3-6% improvement in compression which is achieved with minimal additional hardware or software and yet which is compatible with proposed standard techniques.

BACKGROUND OF THE INVENTION 
The present invention relates to a novel quantization method for use in an 
image compression system. 
The actual data compression in image compression is achieved at the 
quantization step of the overall process. The principle behind the 
forthcoming JPEG international standard is to transform the spatial 
dimension (pixel data) to a series of 2 dimensional discrete cosine 
transform coefficients. It is these coefficients that are quantized in 
software or hardware and subsequently encoded to achieve actual 
compression. 
SUMMARY OF THE INVENTION 
It is an object of the present invention to provide an improved 
quantization method for use in image compression techniques. The improved 
quantization process yields a 3-6% improvement in compression (given a 
certain error level in the compressed file). It is important to note that 
this is achieved with minimal additional hardware and leaves the system 
still 100% compatible with the proposed standard. By using a rounding 
technique, a 3 to 6% gain in compression can be achieved with no 
additional loss of quality.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
Reference will now be made in detail to the preferred embodiments of the 
invention, examples of which are illustrated in the accompanying drawings. 
While the invention will be described in conjunction with the preferred 
embodiments, it will be understood that they are not intended to limit the 
invention to those embodiments. On the contrary, the invention is intended 
to cover alternatives, modifications and equivalents, which may be 
included within the spirit and scope of the invention as defined by the 
appended claims. 
In FIG. 1, the flow of data shows pixels being input to the front end 10 of 
the system. A typical representation of the pixel values is 0 to 255 or 
-128 to +127. These values require 8 bits of data to represent. 
The second stage is the transform 20. Even though the transform involves 
multiplication and/or additions by factors other than integers, the end 
result of the transform is 64 frequency coefficients whose range is 
typically -1024 to +1023. These can be represented by 11 bit numbers. 
These numbers are still considered to be integers. 
The third stage 24 (shown with darker boundary) is the area of real 
interest. It is the quantization that actually achieves the compression by 
reducing many of the high frequency components to zero. The quantization 
may vary depending upon the coefficient in question. Empirical 
experimentation has shown that some coefficients can be "suppressed" 
without an adverse effect on image quality. The actual numerical operation 
for the quantization is a division by a quantization factor Q. If the 
result is a number x (as shown in FIG. 3) then we would express x as: 
EQU x=C+Q 
where C is the coefficient value before quantization. 
Although allowable values for C are in the range of -1024 to +1024, and for 
Q the range is 1 to 512, typical values for both will generally be 
smaller. Much of the time the division of C by Q will result in a small 
number in the range of -5 to +5. With these small numbers, the value to 
the right of the decimal point can have a critical effect on the integer 
value chosen for x. Simple truncation to the right of the decimal point 
would not be acceptable. 
The proposed JPEG international standard proposes the following scheme for 
rounding of the value x. 
______________________________________ 
-0.5 &lt; x &lt; +0.5 
implies setting 
x = 0 
0.5 &lt; x &lt; +1.5 
implies setting 
x = 1 
1.5 &lt; x &lt; 2.5 
implies setting 
x = 2 etc. 
______________________________________ 
The present invention (referred to as "Z" quantization) uses the metric: 
______________________________________ 
-0.625 &lt; x &lt; +0.625 
implies setting 
X = 0 
0.625 &lt; x &lt; +1.625 
implies setting 
x = 1 
1.625 &lt; x &lt; +2.625 
implies setting 
x = 2e 
______________________________________ 
At first glance, the difference between the two approaches may seem very 
small. However, the net effect on compression ratio, for a given error 
level, is an improvement of 3 to 6%. A description of the encoder will 
help explain why. 
FIG. 2a shows the general arrangement for the 64 transform coefficients. 
The DC value resides in the top left-hand corner, and the remaining 63 AC 
coefficients are in order of increasing horizontal and vertical frequency 
as one moves to the bottom right hand corner. 
FIG. 2b shows some typical values that may occur for an 8.times.8 pixel 
block. The international standard calls for the encoder to "zig-zag" scan 
through the AC coefficients. The reason for this approach is to lengthen 
runs of zeros where greatest compression is achieved As shown in this 
figure, "stray" ones (highlighted in FIG. 2b) often break up otherwise 
long runs of zeros. Let's say that the value at the marked "stray" 1 was 
0.609 before rounding. Using the JPEG metric, the value is rounded up to 
1. 
The present invention rounds the 0.609 down to zero. Under the JPEG system, 
the last 18 coefficients are coded as 10 zeros, a 1, and then 7 zeros. 
With the present invention, the last 18 coefficients are coded as a run of 
18 zeros. The net result is longer runs of zeros, hence the name "Z" 
quantization. 
One of the big advantages of the improved quantization method is that it 
remains 100% compatible with the proposed standard. At the decompression 
end of the system, the decompressor does not need to know whether JPEG or 
"Z" was used during quantization. 
The choice of the value 0.625 for "Z" quantization seems optimal for 
several reasons. Even so, values other than 0.5 for the "Z" quantization 
may be acceptable. A higher value such as 0.75 would probably hurt high 
bit rate compressions where accuracy is essential. A value of less than 
0.625 would probably only yield a gain of say 1 to 2% and may not be 
worthwhile. 
Choosing 0.625 yields 3 to 6% and is easy to implement in hardware or 
software. Consider the output of the x=C/Q calculation, as shown in FIG. 
3. 
The value x, after rounding, will be an 11 bit integer. Rounding will 
involve examination of bits to the right of the decimal place (b.sup.-1 to 
b.sup.-3). The JPEG algorithm needs to look at just bit b.sup.-1 to do the 
rounding: 
if b.sup.-1 =1 and b.sup.10 =0, then add 1 to x 
The "Z" quantization approach according to the present invention requires 
only a slightly more complicated algorithm for the rounding: 
if b.sup.-1 =1 and (b.sup.-2 or b.sup.- =1) and b.sup.10 =0, then add 1 to 
x 
Similar logic can be applied to negative numbers. 
Results 
The discrete cosine transform introduces differing degrees of errors at 
various places in the 8.times.8 pixel block. For comparison purposes, we 
will consider the data at the corner pixels "A", and center pixels "B". 
FIG. 4 shows a representation of the block of pixels. 
The proposed "Z" quantization method reduces errors everywhere, but is 
particularly effective at the corner pixels "A". 
FIGS. 5 and 6 show the results for a typical test image. At given bit 
rates, the "Z" quantization approach is marginally better than JPEG on the 
center pixels (see FIG. 5 and note that higher SNR equates to less error). 
On the corner pixels "B", the difference is much more significant. This is 
where most of the win will come, as seen in FIG. 6. 
A very simple change to the quantization circuitry in a JPEG image 
compression system can yield significant gains in the compression ratio 
(3-6%) for very little added cost. The quantization method maintains full 
compatibility with the proposed standard. The choice of the value 0.625 
seems close to optimal from the standpoint of both effectiveness and ease 
of implementation. 
The foregoing descriptions of specific embodiments of the present invention 
have been presented for purposes of illustration and description. They are 
not intended to be exhaustive or to limit the invention to the precise 
forms disclosed, and itshould be clear that many modifications and 
variations are possible in light of the above teaching. The embodiments 
were chosen and described in order to best explain the principles of the 
invention and its practical application, to thereby enable others skilled 
in the art to best utilize the invention and various embodiments 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 and their equivalents.