Method of reducing block artifacts created by block transform compression algorithms

A method of improving image quality when using block transform image compression algorithms by applying a variable lowpass filter (blur) operation on block boundaries that is based on the coefficients of the transformed data. The method of reducing block artifacts results from adaptively blurring the block boundaries based on the frequency content of the blocks. Low frequency blocks are heavily blurred, while high frequency blocks should have very little blur.

TECHNICAL FIELD 
This invention relates generally to a method of processing digital images, 
and in particular, to a method of correcting block artifacts in images 
caused by transform-based image compression. 
BACKGROUND ART 
Digital images are composed of an enormous amount of data. Storage of this 
type of data on digital media is generally expensive and transmission of 
digital images requires either a large bandwidth or a long period of time. 
Many algorithms have been developed to compress image data by removing 
redundant information from the image. The goal of these algorithms is to 
reduce the amount of data needed to represent the image while minimizing 
the amount of image degradation. 
One well known compression technique is transform coding. This method 
involves taking a transformation of the image data to provide a sequence 
of coefficients which can be encoded using, for example, a non-equal 
number of bits for each resulting coefficient. In particular, the number 
of bits employed is based upon the logarithm of the variance for a 
particular coefficient. At the receiver, the coded coefficient data is 
employed for reconstructing the coefficient values and performing the 
inverse of the original transform to obtain an image representative of the 
original data. 
One form of transform coding, block image coding is often used to 
accommodate localized variations in image characteristics. With block 
image coding, a digitized image is decomposed into small rectangular 
regions (or "blocks") which are transform coded and, for example, 
transmitted through a digital communications channel. At the receiver, the 
blocks are decoded and re-assembled in order to reconstruct the image. In 
a typical situation, an image composed of an array of 512.times.512 
picture elements (pixels) can be viewed as an array of 64.times.64 blocks, 
where each block contains 8.times.8 pixels. 
Several kinds of transformations are commonly used for this type of coding. 
Typical transforms include the Fourier transform, cosine transform, 
Hadamard transform, and Harr transform. These transformations operate on 
an M.times.N block of image data and produce a M.times.N array of 
coefficients. These coefficients have the property that they are related 
to specific spatial frequencies in the original image. Normally, the two 
dimensional array of coefficients is arranged into a one dimensional array 
that approximately orders the coefficients from lowest frequency to 
highest frequency. This one dimensional array is then encoded and 
transmitted. 
Of the possible transformations, the Discrete Cosine Transform (DCT) is the 
most commonly used. It has been proposed as a standard for lossy multibit 
image compression by the Joint Photographic Experts Group (JPEG) of the 
International Standards Organization (ISO). The DCT is popular because it 
tends to concentrate most of the information in the original image into a 
smaller group of low-frequency coefficients in the transformed image. 
These coefficients can then be efficiently encoded to provide the required 
compression. 
The major disadvantage of block image coding is that the image is degraded 
by the coding process, and the boundaries of the reconstructed blocks can 
be clearly visible in the resulting image. In particular, this occurs 
because the quantization noise is generally correlated within blocks but 
is independent between blocks, yielding mismatches at block boundaries. 
Because of these blocking artifacts, reconstructed images appear to be 
composed of "tiles". 
Several techniques have been described in the prior art for reducing the 
block artifacts. Most of these techniques involve modifying the encoder in 
some way so that when the image is decoded and reconstructed, there are no 
artifacts. One approach is to overlap the blocks slightly, by one pixel 
for example, and reconstruct the overlapping regions at the receiver by 
using the average of the reconstructed pixels from each of the overlapping 
blocks. 
Another approach is described in U.S. Pat. No. 4,754,492. In this 
technique, the image data in a block is prefiltered with image data in the 
neighboring blocks, then transformed and encoded. Decompression consists 
of performing the inverse transform and postfiltering the blocks. 
These techniques are useful if the source and destination of the images are 
both capable of performing the appropriate algorithms. However, in many 
applications, a user who receives compressed images does not have control 
over the particular technique used to encode the image. For example, the 
DCT compression algorithm proposed as a standard by the JPEG committee 
does not employ any special encoding techniques to remove block artifacts 
from the decoded images. In this case, some other method must be used to 
remove the block artifacts. 
Another common technique is to use a low-pass filter to blur the block 
boundaries in the image. This technique has the advantage of not requiring 
special processing during the compression of the image. Although this 
technique is very effective in reducing the blocking effects, it blurs 
high frequency details along the block boundaries with a perceptible loss 
of sharpness. Another way of looking at that problem is by examining the 
RMS error in the image. In low-frequency areas, blurring the image tends 
to reduce the RMS error in the image; however, in high frequency areas, 
where consecutive pixels have less correlation, blurring the image 
substantially raises the RMS error. 
The object of the present invention is to provide an improved method for 
removing block artifacts from images that have been compressed by a block 
transform compression algorithm. It is a further object of this invention 
to provide the block artifact removal as part of the decoding process 
only. 
DISCLOSURE OF THE INVENTION 
This invention is a method of adaptively processing the boundaries of an 
image to reduce the block artifacts in the image without blurring high 
frequency detail within the image. The invention operates as a part of the 
compression decoder only. 
A block transform decoder includes a means of decoding the transform 
coefficients from the compressed image data. These coefficients are then 
inverse transformed to reconstruct an image block that is representative 
of the original data. In this invention, the decoded transform 
coefficients are evaluated by a frequency analyzer. The frequency analyzer 
then decides on an appropriate amount of blur to be applied to the 
boundaries of adjacent blocks. This decision is sent to a variable 
strength lowpass filter that blurs the pixels along the boundary between 
the blocks. 
This invention applies to transformations in which the transformed image is 
representative of the frequency content of the image. The Fourier 
transform, cosine transform, Hadamard transform, and Harr transform all 
fall into this category. Using this feature, the frequency analyzer can 
easily determine the amount of high frequency detail in the image by 
simply examining the position and magnitude of the coefficients in the 
transformed data.

MODES OF CARRYING OUT THE INVENTION 
In the preferred embodiment, the invention applies to the DCT algorithm 
which has been adopted by the JPEG ISO committee. The present embodiment 
provides a method of correcting block artifacts of the DCT algorithm by 
adaptively blurring the block boundaries based on the frequency content of 
the blocks. Low frequency blocks are heavily blurred, while high frequency 
blocks receive very little blur. 
Because the DCT transforms the image into the frequency domain one can 
adaptively blur the block boundaries based on the coefficients of the DCT; 
for example, the amount of blur on the frequency of the highest non-zero 
coefficient in the transformed blocks. 
FIG. 1 illustrates the well known method of how to apply a transform to 
image data. The original M.times.N image data in block 10 can be 
transformed using any of the previously described transform algorithms 
into an array of M.times.N coefficients in block 12. The newly transformed 
image has no resemblance to the original image, the inverse transform 
operation can then be applied to the transform coefficients and an image 
is reconstructed in block 14 that is representative of the original image. 
If the transform coefficients are stored with infinite precision, the 
newly reconstructed image would be an exact duplicate of the original 
image. 
FIG. 2 illustrates a functional block diagram that demonstrates how 
transforms are commonly used in image compression. First the image data is 
tiled into a set of N.times.N blocks in block 16 to reduce the 
computational demands of the transformation. Each block is then 
transformed in block 18, and the transform coefficients are encoded with 
some loss of precision into the compressed image data in block 20. The 
compressed data may then be stored or transmitted. To reconstruct the 
image, the compressed data is decoded to N.times.N blocks of transform 
coefficients in block 22, and inverse transform is applied thereto. The 
reconstructed image blocks in block 24 are then reassembled into a new 
image that is representative of the original image. 
FIG. 3 shows a typical prior art block transform decoder. The decoder 26 
reads the compressed input image data and creates a block of decoded 
transform coefficients. The inverse transform 28 takes the coefficients 
outputted by decoder 26 and performs the inverse transform operation to 
create a reconstructed block of the image. 
The preferred embodiment of the present invention is shown in FIG. 4. The 
system shown in FIG. 3 is in box 30 and has added thereto a frequency 
analyzer 32 and a filter 34. Compressed image data enters decoder 26 which 
generates a block of decoded transform coefficients, T.sub.ij (for the 
block in the ith column and the jth row of the tiled image). These 
coefficients are then sent to inverse transform 28 and frequency analyzer 
32. Inverse transform 28 transforms the decoded coefficients into a block 
of reconstructed image data, R.sub.ij representative of the original 
image but with the block artifacts. The image data from decoder 26 is also 
passed to frequency analyzer 32 which analyzes the magnitude of the 
coefficients in block T.sub.ij so as to determine the amount of blur 
required to remove the block artifacts between adjacent blocks. A vertical 
blur factor B.sub.v, is generated to control the amount of blur applied to 
the vertical boundary between the current reconstructed image block, 
R.sub.ij and the previous block on the current line, R.sub.i-1 j. A 
horizontal blur factor is generated to control the amount of blur applied 
to the horizontal boundary between the current reconstructed image block, 
R.sub.ij, and the adjacent block on the previous line, R.sub.i j-1. These 
decisions are sent to filter 34. Filter 34 blurs the pixels along the 
block boundaries with adjacent pixels from neighboring blocks to generate 
a new image representation of the original but without block artifacts. 
The technique of ordering the coefficients in a zigzag pattern shown in 
FIG. 5 is well known. Use of this technique corresponds roughly to 
ordering the coefficients in order from those representing the lowest 
spatial frequencies to those representing the highest spatial frequencies. 
This pattern is used because it groups similar frequencies together to 
allow for more efficient encoding of the data. 
In accordance with our preferred embodiment, the amount of blur along block 
boundaries is based on the highest non-zero coefficient in the adjacent 
blocks. The 8.times.8 array of transformed values are placed in a 
1-dimensional list in approximately increasing frequency. FIG. 5 
illustrates how the 8.times.8 array of coefficients are transformed into a 
1-dimensional list in approximately increasing frequency. Because the 
value of the highest non-zero coefficient or cutoff frequency in this list 
is known as a result of the decoding procedure, this value may be stored 
for later use in the frequency analyzer (32). 
The function of the frequency analyzer 32 is to examine the one dimensional 
list for each block and determine the appropriate amount of blur to apply 
to the block boundaries. In the preferred embodiment shown in FIG. 6, the 
activity level A.sub.ij, is determined by the activity analyzer 36. The 
activity level corresponds to the position of the last coefficient in the 
list whose value is above a predetermined threshold. The activity level 
A.sub.ij, is selected in this way for efficiency. The activity level is 
then stored in storage block 38 while the activity levels for the two 
adjacent block, A.sub.i-1 j and A.sub.i j-1 are retrieved from storage. 
These three values are passed to the blur selection block 40 to determine 
the required amount of blur, B.sub.v and B.sub.h, to apply to the 
horizontal and vertical boundaries between the current reconstructed image 
block R.sub.ij, and the previous adjacent reconstructed image blocks. 
The threshold is normally set to zero which results in a very efficient 
implementation. The decoder block 26 identifies the location of the last 
non-zero coefficient in the encoded list because the standard JPEG 
algorithm requires that an End-of-Block code be transmitted after the last 
non-zero coefficient. 
In the preferred embodiment, the two blur factors, B.sub.v and B.sub.h, are 
determined within the blur selection block 40 by using the activity levels 
from the two adjacent blocks (A.sub.ij and A.sub.i-1 j for B.sub.v and 
A.sub.ij and A.sub.i j-1 for B.sub.h) as indices into a two-dimensional 
table of blur values. The blur values in the table are experimentally 
determined to minimize the RMS error in the pixel along the boundaries. As 
a result, the block artifacts are removed while reducing the RMS error in 
the reconstructed image. 
The blur values are numbers between zero and one that are used by blur 
filter 34. For each pixel along the boundary the filter uses the original 
value of the pixel P.sub.1, and the value of the adjacent pixel in the 
neighboring block P.sub.2, to determine a new value P.sub.1 ' that 
replaces the original value, P.sub.1 ' is calculated by the following 
equation: 
EQU P.sub.1 '=(P.sub.1 .times.B)+(P.sub.2 .times.(1-B)) 
FIG. 7 shows the filter design that executes the steps set forth by the 
above equation. This filter design provides good artifact removal and can 
be implemented efficiently. Larger, more complex filters could be used to 
provide more thorough artifact removal resulting in unfortunately, larger 
execution time. 
Flow Chart 
FIGS. 9A-B shows a flow chart for the invention. Block 100 initializes 
variables i and j to keep track of the row and column of the image block 
being decoded. Block 101 reads enough compressed data to decode the 
transform coefficients for the current image block. Block 102 decodes the 
compressed data to create an N.times.N block of transform coefficients, 
T.sub.ij. Block 103 performs the inverse transform on T.sub.ij to create 
an N.times.N block of reconstructed image data R.sub.ij. Block 104 
analyzes the block of transform coefficients T.sub.ij, and assigns an 
activity level A.sub.ij to the image block. Decision block 105 checks to 
see if the current image block is the first block on the line to determine 
if there is a vertical boundary with the previous reconstructed image 
block R.sub.i-1 j. Block 106 selects the amount of blur B.sub.v, that 
should be applied to the vertical boundary between the current block and 
the previous block based on the activity levels in the blocks A.sub.ij and 
A.sub.i-l j. Block 107 performs the blur on the vertical block boundary. 
Decision block 108 checks to see if the current block is in the first line 
of the image to determine if there is a block above that forms a 
horizontal boundary with the current image block. Block 109 selects the 
amount of blur B.sub.h, that should be applied to the horizontal boundary 
between the current block R.sub.ij, and the corresponding block on the 
previous line R.sub.i j-1, based on the activity levels in the blocks, 
A.sub.ij and A.sub.i j-1, block 110 performs the blur operation on the 
horizontal boundary. Block 111 increments the column counter, i, and 
decision block 112 tests to see if the end of the current image line has 
been reached. If not, the next block on the line is processed in the same 
manner. When the end of the image line is reached, the column counter is 
reset to 0 and the line counter is incremented in block 113. Decision 
block 114 checks to see if the end of the image has been reached. If not, 
the next line is processed in the same manner, otherwise the process is 
finished. 
It should be understood that more complicated algorithms can be used for 
the frequency analyzer, for example, by also examining the amplitude of 
the low frequency coefficients or alternatively, one could examine the 
highest horizontal and vertical frequencies and process horizontal and 
vertical borders differently. 
Advantages and Industrial Applicability 
An important advantage of the present invention is that the image quality 
of the images that have been processed by JPEG DCT is improved without 
modifying the compression algorithm that is being considered as a 
standard. It should be understood that while the filtering concept of the 
present invention has been described in terms of the JPEG DCT standard, it 
is equally applicable to any DCT based compression algorithm, and more 
generally to any frequency transform based algorithm. 
Another way of practicing the present invention is to modify the software 
implementation of the DCT algorithm to provide the filtering operation of 
the present invention. The filter operation is very fast and does not 
degrade the image in high frequency areas. 
The present invention will find applicability in the transmission and 
storage of digitized images that have been processed using a compression 
algorithm that incorporates a frequency transform.