Method of Reducing Block Artifacts Created by Block Transform Compression Algorithms

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.

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.

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.

FIG. 1 illustrates the theoretical transform model known in the art using a functional block diagram;

FIG. 2 illustrates the use of transforms in block image compression as was commonly known in the art using a functional block diagram;

FIG. 3 illustrates a generalized block transform decompression known in the art using a functional block diagram;

FIG. 4 illustrates in a functional block diagram of the preferred embodiment of this invention;

FIG. 5 illustrates a method of arranging 2-dimensional transform coefficients into a 1-dimensional list;

FIG. 6 illustrates in a functional block diagram the configuration of the frequency analyzer shown in FIG. 4;

FIG. 7 illustrates a functional block diagram of the configuration of the blur filter shown in FIG. 4;

FIG. 8 shows the locations of the pixels that form a vertical boundary between two horizontally adjacent blocks; and

FIGS. 9A-B illustrate a flow chart of the preferred embodiment of the present 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:

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.

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.

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.