CHAPTER 9 Image Compression Standards Recent years have seen an explosion in the availability of digital images, because of the increase in numbers of digital imaging devices, such as scanners and digital cameras. The need to efficiently process and store images in digital form has motivated the development of many image compression standards for various applications and needs. In general, standards have greater longevity than particular programs or devices and therefore warrant careful study. In this chapter, we examine some current standards and demonstrate how topics presented in Chapters 7 and 8 are applied in practice.
We first explore the standard JPEG definition, used in most images on the web, then go on to look at the wavelet-based JPEG2000 standard. Two other standards, IPEG-LS - aimed particularly at a lossless IPEG, outside the main IPEG standard - and illIG, for bilevel image compression, are included for completeness.1 THE JPEG STANDARD IPEG is an image compression standard developed by the Joint Photographic Experts Group. It was formally accepted as an international standard in 1992 [1]. IPEG consists of a number of steps, each of which contributes to compression.
We'll look at the motivation behind these steps, then take apart the algorithm piece by piece.1 Main Steps in JPEG Image Compression As we know, unlike one-dimensional audio signals, a digital image lei, j) is not defined over the time domain. Instead, it is defined over a spatial domain - that is, an image is a function of the two dimensions i and j (or, conventionally, x and y). The 2D DCT is used as one step in JPEG, to yield a frequency response that is a function F(u, v) in the spatial frequency domain, indexed by two integers II and v. JPEG is a lossy image compression method.
The effectiveness of the Dey transform coding method in JPEG relies on three major observations: Observation 1. Useful image contents change relatively slowly across the image- that is, it is unusual for intensity values to vary widely several times in a small area - for example, in an 8 x 8 image block. Spatial frequency indicates how many times pixel values change across an image block. The DCT formalizes this notion with a measure of how much the image contents change in relation to the number of cycles of a cosine wave per block.
Psychophysical experiments suggest that humans are much less likely to notice the loss of very high-spatial-frequency components than lower-frequency components. 253 254 Chapter 9 Image Compression Standards YIQor YUV fCi,j) DCT Felt, v) Quantization Feu, v) D 0 0 8x8 t :------------------~ I I. -- Quantization tables I 1- _ ~ Coding I I I tables ,, I Header I { ~ __l Tables r DPCM 1 DC Entropy J Zigzag - coding Data RLC 1 J AC FIGURE 9.1: Block diagram for JPEG encoder. JPEG's llPproach to the use of DCT is basically to reduce high-~requency_contents al!d then ~ffi9~ntlycode the-result iniOabltstri~i.~-Th~-teim-iP-;;ii~7 ;-ed;~ida;;cy i~dicatesthat much oithf;jtlt~[~~tioni~ ?~-iIJlllg~isrepeated: jf a pixel is red~ then its-;:eigh~or is likely red-also.
Because of Observation 2 above, the Dcicoefficients for the l()wlOst frequ~ncies are most Important. Therefore, as -frequency gets higher, it~becomes- J_es_sjmportant~o represent the DCT coefficient accurately. It may even be safely set to zer.o without losing much perceivable image i n f o r m a t i o n. - - --- -- Clearly, a string of zeros can be represented efficiently as the length of such a run of zeros, and compression of bits required is possible.
Since we end up using fe\ver numbers ~o represent the pixels in blocks, by removing som~locati6n~aeJ2ei1clentinf~lID_a,tion,__we have effectively removed spatial redundancy. JPEG works for both color and grayscale images. In the case ofcolor images, such as YIQ or YUV, the encoder works on each component separately, using the same routines. If the source image is in a different color format, the encoder performs a color-space conversion to YIQ or YUV.
As discussed in Chapter 5, the chrominance images (l, Q or U, V) are subsampled: r IPEG --r------- 4:~:9 usesJ!1e - ' - scheme, making use of another observation about vision: .1l1 acuity Jaccuracy in distinguishing closely _spaced_lines) is much greater for gray ("black and white;') than for color. We simply canngt see much chllnge in color if it occurs in close proximity- think of the blobby ink ;s~d in comic "6QQlcs. This works simply because our eye sees the black lines best, and our- brain just pushes the color into place. In fact, ordinary broadcast TV makes use of this phenomenon to transmit much less color information than gray information.1 The JPEG Standard 255 When the JPEG image is needed for viewing, the three compressed component images can be decoded independently and eventually combined.
For the color channels, each pixel must be first enlarged to cover a 2 x 2 block. Without loss of generality, we will simply use one of them - for example, the Y image, in the description of the compression algorithm below.1 shows a block diagram for a JPEG encoder. If we reverse the aITOWs in the figure, we basically obtain a JPEG decoder. The JPEG encoder consists of the following main steps: • Transform RGB to YIQ or YUV and subsample color e Perform DCT on image blocks • Apply Quantization e Perform Zigzag ordering and run-length encoding • PerfOlID Entropy coding DCT on Image Blocks.Each image is ~ividedjnto8x_8 bIQcl<:s.]'4e_2Q !?CT(pqua- tion 8.17)js applied to e~c:h_bI6ckTmage-i(i, i), wHh output beiDtlh~I!CTc()efficiellts F(ll,v)for ea.~bj9ck~ The choice ([a small block size in JPEG is a compromise reached by the committee: a number larger than 8 would have made accuracy at low frequencies better, put using 8 make~JI.l~DIT-iamtlR~T) c01l!2utation ver;,-fast.
Using blocks at all, however, has the effect of isolating each block from its neighboring context. This is why JPEG images look choppy ("blocky") when the user specifies a high compression ratio - we can see these blocks. (And in fact removing such "blocking artifacts" is an important concern of researchers.) To calculate a particular F(u, v), we select the basis image in Figure 8.9 that corresponds to the appropriate II and v and use it in Equation 8. 17 to derive one of the frequency responses F(u, v).
The quantization step in JPEG is aimed at reducing the total nL!.ber of bils _nee_cle~J2~~i.-ftConsistsof simply dividing;~ch entry in the frequency space block by an integer, then rounding: .1) Q(u, v) Here, F(u, v) represents a DCT coefficient,Q(u.tJ!»s_a qliallf~gtion matrixen.JPEG wilI_Us. - -Th~ default values in the 8 x 8 quantization matrix Q(u, v) are listed in Tables 9.2 for luminance and chrominance images, respectively. These numbers resulted from psychophysical studies, with the goal ofmaximizing the compression ralio while minimizing perceptual losses in JPEG images. The following should be apparent: 256 Chapter 9 Image Compression Standards TABLE 9.1: The luminance quantization table.2: The chrominance quantization table.
17 18 24 47 99 99 99 99 18 21 26 66 99 99 99 99 24 26 56 99 99 99 99 99 47 66 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 • Since the numbe. We'll seelater that Feu, v) can oe codea \vith many fewer bits. The quantization step is the mgin,sQurcefor loss in IPEG compression. -" • The entries of Q(u, v) tend to have larger values toward the lower right comer.
This tjims -to "inTroduce more loss at the higher spatial frequencies- a practice supported by Observ<:ttionsland 2. We can handily, change the compression ratio simply by multiplicatively scaling the numbers in the Q(u, v) matrix. In fact, the quality factor, a user choice offered in every JPEG implementation, is essentially linearly tied to the scaling factor. JPEG also allows custom quantization tables to be specified and put in the header; it is interesting to use low- constant or high-constant values such as Q "" 2 or Q "" 100 to observe the basic effects of Q on visual artifacts.3 show some results of JPEG image coding and decoding on the test image Lena.
Only the luminance image (Y) is shown. Also, the lossless coding steps Section 9.1 The JPEG Standard 257 An 8 X 8 block from the Y image of 'Lena' 200 202 189 188 189 175 175 175 515 65 -12 4 1 2 -8 5 200 203 198 188 189 182 178 175 -16 3 2 a 0~11 -2 3 203 200 200 195 200 187 185 175 -12 6 11 -1 3 0 1 -2 200 200 200 200 197 187 187 187 -8 3 -4 2 -2 -3 -5 -2 200 205 200 200 195 188 187 175 o -2 7 -5 4 0 -1 -4 200 200 200 200 200 190 187 175 a -3 -1 0 4 1 -1 a 205 200 199 200 191 187 187 175 3 -2 -3 3 3 -1 -1 -3 210 200 200 200 188 185 187 186 -2 5 -2 4 -2 2 -3 0 f(i,}) F(u, v) 32 6 -1 0 0 0 0 0 512 66 -10 0 0 0 0 0 -1 a 0 0 0 0 a 0 -12 0 0 0 0 a 0 0 -1 0 1 0 0 0 0 0 -14 0 16 0 a 0 0 a -I 0 0 0 0 0 0 0 -14 a 0 0 0 0 0 a 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Felt, v) F(ll, v) 199 196 191 186 182 178 177 176 1 6 -2 2 7 -3 -2 -1 201 199 196 192 188 183 180 178 -1 4 2 -4 1 -1 -2 -3 203 203 202 200 195 189 183 180 0 -3 -2 -5 5 -2 2 -5 202 203 204 203 198 191 183 179 -2 ~3 -4 -3 -1 -4 4 8 200 201 202 201 196 189 182 177 0 4 -2 -1 -1 -1 5 -2 200 200 199 197 192 186 181 177 0 0 1 3 8 4 6 -2 204 202 199 195 190 186 183 181 1 ~2 0 5 1 1 4 -6 207 204 200 194 190 187 185 184 3 -4 0 6 -2 -2 2 2 lu,}) EU,}) =f(i,)) -lu,)) FIGURE 9.2: JPEG compression for a smooth image block.