# - Acharya T.

ISBN 0-471-48422-9

**Download**(direct link)

**:**

**30**> 31 32 33 34 35 36 .. 100 >> Next

3.3.3 The Baseline Compression Algorithm

The baseline JPEG algorithm follows the principles of block-based transform coding. Block diagram of the baseline JPEG algorithm for a grayscale image with a single component is shown in Figure 3.3. For a color image, the same

BASELINE JPEG COMPRESSION 63

algorithm is applied in each 8x8 data block based on the source image data arrangement as described in the previous section.

Input Image Data ENCODER

(a)

Fig. 3.3 Baseline JPEG: (a) compression, (b) decompression.

The image component is first divided into non-overlapping 8x8 blocks in the raster scan order left-to-right and top-to-bottom as shown in Figure 3.3(a). Each block is then encoded separately by the ENCODER shown in the broken box in Figure 3.3(a). The first step is to level shift each pixel in the block to convert into a signed integer by subtracting 128 from each pixel. Each level-shifted pixel in the 8x8 block is then transformed into frequency domain via forward discrete cosine transform (FDCT). The FDCT of an 8 x 8 block of pixels f(x, y) for (x,y = 0,1, ■ • •, 7) is defined by:

7 7

F(u,v) = ^C(u)C(v)^2^2f(x,y)cos

x=Qy=0

for u = 0,1,..., 7 and v = 0,1,..., 7, where

tt(2x + l)u

16

cos

7r(2 y + l)u 16

C(k)

At

72 f°rfc = 0

otherwise.

We discuss discrete cosine transform in further detail in the following section.

3.3.4 Discrete Cosine Transform

Discrete Cosine Transform (DCT) is the basis for many image and video compression algorithms, especially the still image compression standard JPEG in

64 JPEG: STILL IMAGE COMPRESSION STANDARD

lossy mode and the video compression standards MPEG-1, MPEG-2, and MPEG-4. Since an image is a two-dimensional signal, the two-dimensional DCT is relevant in terms of still image and video compression. The twodimensional DCT can be computed using the one-dimensional DCT horizontally and then vertically across the signal because DCT is a separable function.

The one-dimensional forward Discrete Cosine Transform (1-D FDCT) of N samples is formulated by

F(u)

N-1

C(u) ^ f(x) cos

æ=0

tt(2x + 1 )u 2N

for u — 0,1,..., N — 1, where

for u — 0 otherwise.

The function /(x) represents the value of the xth sample of the input signal. F{u) represents a Discrete Cosine Transformed coefficient for u = 0,1, ■ ■ •, iV— 1.

The one-dimensional inverse Discrete Cosine Transform (1-D IDCT) is formulated in a similar fashion as follows,

N-1

= V ~N X] C(U)F(U)cos

u=0

n(2x + 1)u

2N

for x = 0,1,..., AT — 1.

The two-dimensional forward Discrete Cosine Transform (2-D FDCT) of a block ofMxJV samples of a two-dimensional signal F(x,y) is formulated as

F(u, v)

Vmn

for u = 0,1,..., N

N-1 M-l

C(u)C(v) X] x’y^

x=0 y—0

COS

n(2x + 1 )u

1 and v = 0,1,

C(k) = <\ f

2N

M — 1, where

■n(2y + l)u 2M

for k = 0 otherwise.

The function f(x, y) represents the value of the xth sample in the yth row of a two-dimensional signal. F(u, v) is a two-dimensional transformed coefficient for u = 0,1,..., N — 1 and v = 0,1,...,, M — 1.

The above expression for 2-D FDCT is clearly a separable function because we can express the formula as follows:

F{u'v) = v mc(v) 1 v nc(u) f{x'y)

7r(2x + l)lil 2TV I

n(2y + l)ti 2 M

v=o

BASELINE JPEG COMPRESSION 65

As a result we can accomplish the 2-D FDCT of a two-dimensional signal by applying 1-D FDCT first row-wise followed by 1-D FDCT column-wise in two steps. First, the 1-D FDCT is applied row-wise in all the rows independently to obtain F(u,y), where

F(u,y)

N- 1

f(x, у) COS

x=0

tt(2x + l)u

2N

for u = 0,1,..., N — 1.

In the second step, the same 1-D FDCT is applied column-wise in all the columns of F(u,y) to obtain the result F(u,v), where

F(u, v)

M-1

C(v) ^2 F(u,y) cos y=0

7Г(2 у + l)u

2 M

for v = 0,1,..., M — 1.

The two-dimensional inverse Discrete Cosine Transform (2-D IDCT) is computed in the similar fashion. The 2-D IDCT of F(u,v) is formulated as

JV-l M-1

EE C(u)C(v)F(u, v) cos

VMN ^

v u=0 v=0

tt(2x + l)u 2N

cos

ir(2y + l)u 2M

for x = 0,1,..., N — 1 and y = 0,1,..., M — 1.

The above function is again a separable function similar to what we have shown for the 2-D FDCT. As a result, the 2-D IDCT can be computed in exactly the opposite way of the 2-D FDCT. The 2-D IDCT is computed in two steps: by first applying 1-D IDCT column-wise followed by the 1-D IDCT row-wise. After column-wise computation of 1-D IDCT in every column of the input signal F(u,v), we obtain F(u,y), where

F(u,y) =

M-1

C(v)F(u, v) cos

v=0

7Г(2 у + 1)г>

2 M

for v = 0,1,..., M — 1.

In the second step, the same 1-D IDCT is applied row-wise in all the rows of F(u,y) to obtain the two-dimensional signal f{x,y), where

N-1

/(z, y) = J -Tj C(U)F(U’ y)cos

u=0

7r(2a; + l)u

2N

for u = 0,1,..., N — 1.

Computational complexity of the direct implementation of the above 1-D DCT algorithm is 0(N2). For DCT-based transform coding algorithms, the

66 JPEG: STILL IMAGE COMPRESSION STANDARD

**30**> 31 32 33 34 35 36 .. 100 >> Next