انت هنا الان : شبكة جامعة بابل > موقع الكلية > نظام التعليم الالكتروني > مشاهدة المحاضرة

DCT

Two-dimensional image transforms are extremely important areas of study in

image processing. The image output in the transformed space may be

analyzed, interpreted, and further processed for implementing diverse image

processing tasks. These transformations are widely used, since by using these

transformations, it is possible to express an image as a combination of a set

of basic signals, known as the basis functions. In case of Fourier transform

of an image these basis signals are sinusoidal signals with different periods

which describe the spatial frequencies in an image. Thus such transforms, such as the Fourier transform, reveal spectral structures embedded in the image that may be used to characterize the image.

The term Image transform are usually refers to a class of unitary matrices used for representing images.

large class of image processing transformations is linear in nature; an output image is formed from linear combinations of pixels of an input image. Such transforms include convolutions, correlations, and unitary transforms. Linear transforms have been utilized to enhance images and to extract various features from images. For example, the Fourier transform is used in  highpass and lowpass filtering as well as in texture analysis. Another application is image  coding in which bandwidth reduction is achieved by deleting low-magnitude transform coefficients.

Fourier Transform

Fourier transform is one of the most important tools which have been extensively used not only for understanding the nature of an image and its formation but also for processing the image.

Using Fourier transform, it has been possible to analyze an image as a set of spatial sinusoids in various directions, each sinusoid having a precise frequency.

Discrete Fourier Transform (DFT)

Since the signal is discretized, the operation of integration in continuous Fourier trunsfomn (CFT) is replaced by summation operations in DFT. We present the one-dimensional DFT and also the two-dimensional DFT in the following subsections.

One-Dimensional DFT

The one-dimensional discrete Fourier transform of a function f(x) of size N with integer index x running from 0 to N - 1,

is represented by

[error : replace y in summation by x]

The corresponding one-dimensional inverse DFT is

[replace M by N]

Two-Dimensional DFT

The two-dimensional discrete Fourier transform of a two-dimensional signal f ( x , y ) of dimension M x N with integer indices x and y running from 0 to M - 1 and 0 to N - 1, is represented by

The equivalent two-dimensional inverse DFT is

The Discrete Cosine Transform ( DCT )

This important transform (DCT for short) has originated by [Ahmed et al. 74].

The DCT in one dimension is given by

The input is a set of n data values pt (pixels, audio samples, or other data), and the output is a set of n DCT transform coefficients (or weights) Gf . The first coefficient

G0 is called the DC coefficient, and the rest are referred to as the AC coefficients. Notice that the coefficients are real numbers even if the input data consists of integers. Similarly, the coefficients may be positive or negative even if the input data consists of nonnegative numbers only. This computation is

The IDCT in one dimension is given by

the most of the n transform coefficients produced by the DCT are zeros or small

numbers, and only a few are large (normally the first ones). We will see that the

early coefficients contain the important (low-frequency) image information and the later coefficients contain the less-important (high-frequency) image information. Compressing data with the DCT is therefore done by quantizing the coefficients. Experience indicates that n = 8 is a good value, and most data compression methods that employ the DCT use this value of n.

The following example illustrates the difference in performance between the DCT and the DFT. We start with the simple, highly correlated sequence of eight numbers (8, 16, 24, 32,  40, 48, 56, 64). It is displayed graphically in following Figure

Applying the DCT to it yields (100,?52, 0,?5, 0,?2, 0, 0.4). When this is quantized to

(100,?52, 0,?5, 0, 0, 0, 0) and transformed back, it produces (8,15,24, 32, 40, 48,57, 63),

a sequence almost identical to the original input. Applying the DFT to the same input, on the other hand, yields (36, 10, 10, 6, 6, 4, 4, 4). When this is quantized to

(36, 10, 10, 6, 0, 0, 0, 0) and is transformed back, it produces (24, 2, 20, 32 ,40 ,51, 59, 48).

This output is shown in the following Figure, and it illustrates the tendency of the Fourier

Transform to produce a periodic result.

The DCT in two dimension is given by

for 0 ? i ? n?1 and 0 ? j ? m?1 and for Ci and Cj defined by Equation (4.13). The

first coefficient G00 is again termed the “DC coefficient,” and the remaining coefficients

are called the “AC coefficients.” The IDCT in two dimension is given by

We now show one way to compress an entire image with the DCT in several steps as follows:

1. The image is divided into k blocks of 8×8 pixels each. The pixels are denoted by pxy. If the number of image rows (columns) is not divisible by 8, the bottom row (rightmost column) is duplicated as many times as needed.

2. The DCT in two dimensions [Equation (4.15)] is applied to each block Bi. The result is a block (we’ll call it a vector) W(i) of 64 transform coefficients

3. Each block is quantized separately to produce quantized coefficients

We illustrate the performance of the DCT in two dimensions by applying it to two blocks of 8×8 values. The first block (Table 4.23a) has highly correlated integer values in the range [8, 12], and the second block has random values in the same range(table 4.24)

The first block results in a large DC coefficient, followed by small AC coefficients (including 20  zeros, Table 4.23b, where negative numbers are underlined).  When the coefficients are quantized (Table 4.23c),

The result, shown in Table 4.23d, is very similar to the original values. In contrast, the coefficients for the second block (Table 4.24b) include just one zero. When quantized (Table 4.24c) and transformed back, many of the 64 results are very different from the original values (Table 4.24d).

The next example illustrates the difference in the performance of the DCT when applied to a continuous-tone image and to a discrete-tone image. We start with the highly correlated pattern of Table 4.25.

 This is an idealized example of a continuous-tone image, since adjacent pixels differ by a constant amount except the pixel (underlined) at row 7, column 7. The 64 DCT coefficients of this pattern are listed in Table 4.26. It is clear that there are only a few dominant coefficients. Table 4.27 lists the coefficients after they have been coarsely quantized, so that only four nonzero coefficients remain! The results of performing the IDCT on these quantized coefficients are shown in Table 4.28.

It is obvious that the four nonzero coefficients have reconstructed the original pattern to a high degree. The only visible difference is in row 7, column 7, which has changed from

12 to 17.55 (marked in both figures).

Quantization

After each 8×8 data unit of DCT coefficients Gij is computed, it is quantized. This is the step where information is lost (except for some unavoidable loss because of finite precision calculations in other steps). Each number in the DCT coefficients matrix is divided by the corresponding number from the particular “quantization table” used, and the result is rounded to the nearest integer. In principle, they can all be specified and fine-tuned by the user for maximum compression.

JPEG software normally uses the following two approaches:

1. Default quantization tables. Two such tables, for the luminance (grayscale) and

the chrominance components, are the result of many experiments performed by the JPEG committee. They are included in the JPEG standard and are reproduced here as Table 4.61.

It is easy to see how the QCs in the table generally grow as we move from the upper left corner to the bottom right corner. This is how JPEG reduces the DCT coefficients with high spatial frequencies.

2. A simple quantization table Q is computed, based on one parameter R specified by the user. A simple expression such as Qij = (1+(i + j) × R)-1 guarantees that QCs start small at the upper-left corner and get bigger toward the lower-right corner. Table 4.62 shows an example of such a table with R = 2.

If the quantization is done correctly, very few nonzero numbers will be left in the DCT coefficients matrix, and they will typically be concentrated in the upper-left region.