# CS代考 IMAGES – COMPRESSION – cscodehelp代写

IMAGES – COMPRESSION

IMAGES – COMPRESSION

AND DITHERING

AND DITHERING

Dr. – CS576 Lecture 5 Page 1

TOPICS TO BE COVERED

Introduction

• Image Types

• Image Representation

• Applications where images are used

Need for Compression and Standards

Overview of Image Compression Algorithms and Formats

JPEG

• Needs and Requirements

• Compression Algorithms for supported modes • Performance Issues

JPEG 2000

• Wavelet Compression

Drawbacks of Image Compression – Image Dithering

Dr. – CS576 Lecture 5 Page 2

TYPES OF IMAGES

TYPES OF IMAGES

We consider here still images, for example:

• Photographs (color or grayscale)

• Fax (bi-level and multilevel)

• Documents (text, handwriting, graphics and

photographs)

• Mosaics

• Stereo Images

Representation of Images –

Consists of components

Gray Images – single component

Color Images – r, g, b components

Sometimes images also have an alpha component. Each component is represented as a number of bits per pixel (application dependent).

Dr. – CS576 Lecture 5 Page 3

EXAMPLE OF ALPHA CHANNEL

EXAMPLE OF ALPHA CHANNEL

+

=

Foreground

Background

Final

RGBα

Final[i][j] = Foreground[i][j]* α [i][j] + Background[i][j]*(1-α[i][j])

Dr. – CS576 Lecture 5 Page 4

APPLICATIONS

APPLICATIONS

Application examples – variety of low/medium resolutions (usually 8 bits per component or less)

• Information – news,

• Entertainment – Slide-show on the Internet,

games

• Commerce – ecommerce (catalogs, home

shopping), real-estate viewing

Application examples – high resolution (more than 8 bits per component)

• Medical applications – (X-rays, CAT scans, etc.) • Film Applications

• Remote Sensing.

Dr. – CS576 Lecture 5 Page 5

NEED FOR COMPRESSION

NEED FOR COMPRESSION

Multimedi a Image Data

Size Of Image

Bits/Pixel or Bits/Sample

Uncompressed Size

(B for bytes)

Band Width (b for bits)

Transmission Time

56K Modem

780Kb DSL

Grayscale Image

512 x 512

8 bpp

262 KB

2.1 Mb/im age

42 seconds

3 seconds

Color Image

512 x 512

24 bpp

786 KB

6.29 Mb/im age

110 seconds

7.9 seconds

Medical Image

2048 x 1680

12 bpp

5.16 MB

41.3 Mb/im age

12 min

51.4 seconds

SHD Image

2048 x 2048

24 bpp

12.58 MB

100 Mb/im age

29 min

2 min

Dr. – CS576 Lecture 5 Page 6

SOME COMPRESSION FORMATS

SOME COMPRESSION FORMATS

There are many different uncompressed and compressed formats used in the industry! Some of commonly used compressed formats are

• RIFF – Resource Interchange File Format • GIF – Graphics Interchange File Format

• PNG – Portable Network Graphics

• JPEG – Joint Photographic Expert Groups • JPEG 2000

• MPEG4-VTC – Visual Texture Coding

Dr. – CS576 Lecture 5 Page 7

IMAGE REDUNDANCY

IMAGE REDUNDANCY

• Spatial Redundancy • Spectral Redundancy

Dr. – CS576 Lecture 5 Page 8

TYPES OF IMAGE COMPRESSION

TYPES OF IMAGE COMPRESSION

Makes use of Lossless and Lossy Schemes or a combination of both (Hybrid)

Lossless Schemes

Already discussed in Information Theory Lecture

Lossy Schemes

Frequency Domain Based

• Discrete Fourier

• Discrete Cosine

• Wavelet Transforms

Fractal Based Compression

http://pi4.informatik.uni- mannheim.de/pi4.data/content/animations

Dr. – CS576 Lecture 5 Page 9

JPEG BACKGROUND – REQUIREMENTS AND

JPEG BACKGROUND – REQUIREMENTS AND SELECTION PROCESS

Be at or near the state of art with regards to compression rate and accompanying fidelity

Make no assumptions about the type of image – should be applicable to practically any kind of continuous-tone digital source image.

Have a tractable computational complexity

Support flexibility by allowing the following modes of operation

• Lossless and Lossy Encoding • Sequential Encoding

• Progressive Encoding

• Hierarchical Encoding

Dr. – CS576 Lecture 5 Page 10

JPEG IMAGE CODING

JPEG IMAGE CODING

JPEG is the standard algorithm for compression of still images

• Started in June 1987

• Finalized and Accepted in 1991

It is of reasonably low computational complexity, is capable of producing compressed images of high quality, and can provide both lossless and lossy compression of arbitrarily sized grayscale and color images

Dr. – CS576 Lecture 5 Page 11

JPEG LOSSY CODEC SCHEME

JPEG LOSSY CODEC SCHEME

Dr. – CS576 Lecture 5 Page 12

JPEG COMPRESSION ALGORITHMIC

JPEG COMPRESSION ALGORITHMIC OVERVIEW

The RGB color vectors of the input image are converted into YCrCb values and each channel is encoded independently

Each channel image is converted into a series of 8-by-8 pixel blocks, which are then processed in a raster scan sequence from left to right and from top to bottom

Each 8×8 block of pixels is spectrally analyzed using DCT (transform coding) and coefficients are quantized

After DCT coding and quantization, coefficients are entropy coded

Dr. – CS576 Lecture 5 Page 13

Discrete Cosine Transform

DCT FORMULA IN 2D

DCT FORMULA IN 2D

1 x=7 y=7 (2x+1)u F(u,v)= C(u)C(v)f(x,y)cos

(2y+1)v cos

4 x=0y=0 16 Inverse Discrete Cosine Transform

16 (2y+1)v

1x=7 y=7 (2x+1)u f(x,y)= 4C(u)C(v)F(u,v)cos 16

1

cos 16

u=0 v=0

where :C(u),C(v) =

C(u),C(v) =1 otherwise

2 , for u, v =0

Dr. – CS576 Lecture 5 Page 14

WHAT DO THE DCT COEFFICIENTS

WHAT DO THE DCT COEFFICIENTS REPRESENT

The DCT coefficients represent the spatial frequency content within a 8×8 image block

The (0, 0) coefficient contains is called DC coefficient, and is equal to a measure of the average of the 64 image values in the block

As we move to the right of the block, the coefficients represent the energy in higher horizontal frequencies

As we move down the block, the coefficients represent the energy in higher vertical frequencies

Dr. – CS576 Lecture 5 Page 15

EXAMPLES OF 8X8 DCTS

EXAMPLES OF 8X8 DCTS

Dr. – CS576 Lecture 5 Page 16

EXAMPLE OF 8X8 DCT BASIS FUNCTIONS

EXAMPLE OF 8X8 DCT BASIS FUNCTIONS

Dr. – CS576 Lecture 5 Page 17

DCT COEFFICIENT QUANTIZATION

DCT COEFFICIENT QUANTIZATION

Each DCT coefficient is quantized independently using a uniform quantizer

The number of quantization intervals per each DCT channel is chosen independently for each coefficient

After quantization, the DC coefficient of a block is encoded as the difference from the DC term of the previous block in the processing order.

This is because there is usually strong correlation between the DC coefficients of adjacent blocks

Dr. – CS576 Lecture 5 Page 18

RULES FOR DCT COEFFICIENT QUANTIZATION

RULES FOR DCT COEFFICIENT QUANTIZATION

Low-frequency coefficients usually have more energy than high-frequency coefficients – therefore require more quantization intervals

The Human Visual System is more sensitive to low frequencies. Hence, low-frequency coefficients require more quantization intervals

The Human Visual System is more sensitive to luminance channels than to chrominance channels. Hence, luminance channels require more quantization intervals than chrominance channels

“Note: the quantization table is not standardized!”

Dr. – CS576 Lecture 5 Page 19

EXAMPLE

EXAMPLE

Dr. – CS576 Lecture 5 Page 20

ENTROPY CODING OF DCT COEFS

ENTROPY CODING OF DCT COEFS

The quantized DCT coefficients are first processed in

zigzag order

Dr. – CS576 Lecture 5 Page 21

INTERMEDIATE REPRESENTATION

INTERMEDIATE REPRESENTATION

Zigzag ordering of coefficients places low frequency coefficients before high-frequency coefficients.

• Low frequency coefficients are more likely to be non-zero

• High frequency coefficients are more likely to be null after quantization

In this way, the sequence of quantized coefficients is such that there often are long sequences of null values

AC coefficients are represented in an intermediate run- length representation, which encodes the runs of zero preceding any non-null coefficient

Dr. – CS576 Lecture 5 Page 22

INTERMEDIATE REPRESENTATION (2)

INTERMEDIATE REPRESENTATION (2)

Each non-zero AC coefficient is represented in combination with the run-length of the null coefficients before it, using a pair of symbols:

• Symbol-1 (RUNLENGTH,SIZE) • Symbol-2 (AMPLITUDE)

RUNLENGTH is the number of consecutive null coefficients before the non-zero symbol; SIZE is the size of the symbol used to encode the non-null symbol

AMPLITUDE is the actual (encoded) value

Dr. – CS576 Lecture 5 Page 23

INTERMEDIATE REPRESENTATION (3)

INTERMEDIATE REPRESENTATION (3)

RUNLENGTH must be 15. To represent a run of > 15 zeros, there can be up to 3 consecutive (15,0) symbol-1 extensions

If the last run of zeros contains the last DCT coefficient, then the special EOB (End-Of-Block) symbol-1 value (0,0) terminates the representation

DC coefficients are represented by only one pair: • Symbol-1 (SIZE)

• Symbol-2 (AMPLITUDE)

Dr. – CS576 Lecture 5 Page 24

ENTROPY CODING

ENTROPY CODING

For both DC and AC coefficients, each symbol-1 is Huffman encoded (variable length prefix code)

• Huffman tables are not specified in the standard and must be input to the encoder

Each symbol-2 is encoded with a Variable Length Integer (VLI) code

• It is different from a Huffman code because the symbol length is known in advance

• The coding table is hard-wired in the proposal

Dr. – CS576 Lecture 5 Page 25

LOSSLESS JPEG MODE

LOSSLESS JPEG MODE

It is wholly independent of DCT processing

Each sample value is predicted from a combination of nearby sample values, and the prediction residual is entropy coded (Huffman)

Prediction effectively reduces the entropy of the residual, so that small average symbol length can be achieved

Dr. – CS576 Lecture 5 Page 26

PROGRESSIVE ENCODING MODES

PROGRESSIVE ENCODING MODES

Layering or progressive encoding: an image can be transmitted at a low rate (and a low quality) and then progressively improved by subsequent transmission

Convenient for browsing applications, where a low- quality or low-resolution image is adequate browsing

Three forms of JPEG progressive encoding: • Spectral selection

• Successive bit approximation (SNR scalability) • Hierarchical (pyramidal) mode

Dr. – CS576 Lecture 5 Page 27

PROGRESSIVE ENCODING (2)

PROGRESSIVE ENCODING (2)

Spectral selection

• Initial transmission sends low-frequency DCT

coefficients, followed progressively by the higher frequency coefficients, according to the zig-zag scan

• Simple to implement but reconstructed images from the early scans are blurred

Successive approximation (SNR scalability)

• Only the most significant bits of each coefficient

are sent in the first scan, followed by the next most significant bits and so on until all bits have been transmitted

Dr. – CS576 Lecture 5 Page 28

Dr. – CS576 Lecture 5 Page 29

PROGRESSIVE ENCODING (3)

PROGRESSIVE ENCODING (3)

Hierarchical (pyramidal) mode

• Image can be sent in one of several resolution

modes to accommodate different kinds of

displays

• Different resolution modes achieved by filtering

and down sampling the image in multiples of two in each direction. The resulting image is interpolated and subtracted from the next level to create a residual

• The different resolution modes are transmitted together with the residuals

Dr. – CS576 Lecture 5 Page 30

PYRAMID DECOMPOSITION

PYRAMID DECOMPOSITION

Dr. – CS576 Lecture 5 Page 31

PYRAMID DECOMPOSITION(2)

PYRAMID DECOMPOSITION(2)

Dr. – CS576 Lecture 5 Page 32

JPEG PERFORMANCES

JPEG PERFORMANCES

Assume the pixels of an arbitrary color image are digitized to 8 bits for luminance and chrominance channels with 4:2:2 color sampling scheme.

Then effectively the source image has 16 bits/pixel

Bits/Pixel

Quality

Compression Ratio

0.25 0.5 0.75 1.5

Fair 64:1 Good 32:1 Very Good 21:1 Excellent 10:1

2

Indistinguishable

8:1

Dr. – CS576 Lecture 5 Page 33

ARTIFACTS OF JPEG – ORIGINAL (380KB)

ARTIFACTS OF JPEG – ORIGINAL (380KB)

Dr. – CS576 Lecture 5 Page 34

ARTIFACTS OF JPEG – COMPRESSED (40KB)

ARTIFACTS OF JPEG – COMPRESSED (40KB)

Dr. – CS576 Lecture 5 Page 35

Original – 24 bits per pixel Compressed – 1.0 bits per pixel

Compressed – 0.5 bit per pixel Compressed – 0.15 bits per pixel

Dr. – CS576 Lecture 5 Page 36

DRAWBACKS OF DCT – STATIONARY SIGNALS

DRAWBACKS OF DCT – STATIONARY SIGNALS

The DCT Transform is good for stationary signals – frequencies are present all the time

Dr. – CS576 Lecture 5 Page 37

DRAWBACKS OF DCT – NON STATIONARY

DRAWBACKS OF DCT – NON STATIONARY

Non stationary signals have frequencies that vary with time.

Dr. – CS576 Lecture 5 Page 38

TIME FREQUENCY ANALYSIS

TIME FREQUENCY ANALYSIS

Dr. – CS576 Lecture 5 Page 39

JPEG-2000

JPEG-2000

Dr. – CS576 Lecture 5 Page 40

INTRODUCTION

INTRODUCTION

Image compression should not only reduce storage and bandwidth requirements, but also allow extraction for editing and processing – one of the primary motives of JPEG-2000: International Standard by 12/2000

JPEG-2000 has better compression performances than JPEG; more importantly, from a single bit-stream, JPEG- 2000 allows extraction of

• Different resolution

• Different pixel fidelities

• Different regions of interest • Different color component

Dr. – CS576 Lecture 5 Page 41

JPEG-2000 FEATURES

JPEG-2000 FEATURES

State-of-the-art low bit-rate compression

Progressive transmission by quality, resolution, component, or spatial locality

Lossy and Lossless compression (with Lossless decompression available naturally through all types of progression)

Random (spatial) access to the bit stream

Pan and zoom (with decompression of only a subset of the compressed data)

Compressed domain processing (e.g., rotation and cropping)

Region of interest coding by progression

Dr. – CS576 Lecture 5 Page 42

JPEG-2000 COMPRESSION STEPS

JPEG-2000 COMPRESSION STEPS

An image is first divided into tiles

Each tile is subband-transformed and quantized

Each subband of a tile is divided into packet partitions; each packet partition is divided into code-blocks

Each code-block is entropy-coded independently (using arithmetic coding)

The image is encoded “naturally” progressively: if we decode all of the bit-stream, we obtain the Lossless version of the image

Dr. – CS576 Lecture 5 Page 43

WAVELET ENCODING OF A SINGLE TILE

Dr. – CS576 Lecture 5 Page 44

SPATIAL ACCESSIBILITY

SPATIAL ACCESSIBILITY

A client may wish to obtain compressed data for only a particular portion of the image.

If Regions of Interest (ROI) are known in advance (at encoding time) JPEG-2000 can provide greater image quality to the foreground. (exploits image tiling)

Dr. – CS576 Lecture 5 Page 45

PERFORMANCE

PERFORMANCE

Typically JPEG-2000 provides (with respect to JPEG) only a few dB improvements from 0.5 to 1.0 bits/pixel but substantial improvement below 0.25 bits/pixel and above 1.5 bits/pixel

JPEG progressive is not optimized (i.e. has worse performance than JPEG sequential) because the DCT coefficients stay the same but the entropy coding changes

• With JPEG-2000 the progressive performance is almost identical to the single layer performance (because the encoded bits do not change)

Dr. – CS576 Lecture 5 Page 46

EXAMPLES – ORIGINAL

EXAMPLES – ORIGINAL

Dr. – CS576 Lecture 5 Page 47

JPEG2000

JPEG

EXAMPLES

EXAMPLES

Dr. – CS576 Lecture 5 Page 48

CONCLUSION

CONCLUSION

JPEG-2000 is unlikely to replace JPEG in low complexity applications at bit-rates in the range where JPEG performs well

However, for applications requiring either higher quality or lower bit rates, or any of the features provided, JPEG- 2000 should be a welcome standard.

The main reasons why it will be welcomed in the future

• Better qualitative performance at same bitrate with JPEG

• Random Access of Bitstream – supports features such as Region of Interest.

• Compressed Image Domain Manipulation

• Encode once – decode depending on platform

Dr. – CS576 Lecture 5 Page 49

Dr. – CS576 Lecture 5 Page 50

DITHERING

DITHERING

Dr. – CS576 Lecture 5 Page 51

THE PROBLEM

THE PROBLEM

Suppose that an image uses N intensity levels (or uses N colors) to represent its content.

Suppose that the rendering device on which this is to be displayed can use only n colors, and

n

Dr. – CS576 Lecture 5 Page 57

DITHERING (EXAMPLE)

DITHERING (EXAMPLE)

Dr. – CS576 Lecture 5 Page 58

ERROR DIFFUSION

ERROR DIFFUSION

When trying to display an image having colors more in number than the display device (or printer device), a selection has to be made to approximate the value of the display color, which is done using

• Precomputed Lookup Tables (LUT) • Dynamic Color Quantization

Either way the difference in the selector color value and the original value results in an error

Large color errors degrade the quality of the displayed image. If the error is diffused in the neighborhood, such effects are minimized. Error Diffusion Algorithms do this by distributing the color errors among all the pixels such that the total color error for the entire image is zero (or very close to zero).

Dr. – CS576 Lecture 5 Page 59

ERROR DIFFUSION ALGORITHM

ERROR DIFFUSION ALGORITHM

Let A be the original image and B be the final image

• Pick up the palette color that is nearest the

original pixel’s color. This palette color is stored in the destination bitmap B [i,j ].

• Calculate the color error A [i,j ] – B [i,j ]for the

pixel.

• Distribute this error to four of A [i,j ]’s nearest

neighbors that haven ’t been scanned yet (the one on the right and the three ones centered below) according to a filter. Eg – Floyd- . – CS576 Lecture 5 Page 60

ERROR DIFFUSION – EXAMPLE

ERROR DIFFUSION – EXAMPLE

Dr. – CS576 Lecture 5 Page 61