CS计算机代考程序代写 scheme flex information theory Excel algorithm INTRODUCTION

INTRODUCTION

Dr. – CS576 Lecture 5 Page 1

IIMMAAGGEESS –– CCOOMMPPRREESSSSIIOONN

AANNDD DDIITTHHEERRIINNGG

Dr. – CS576 Lecture 5 Page 2

TTOOPPIICCSS TTOO BBEE CCOOVVEERREEDD

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 3

TTYYPPEESS OOFF IIMMAAGGEESS

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 4

EEXXAAMMPPLLEE OOFF AALLPPHHAA CCHHAANNNNEELL

+ =

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

Foreground Final Background

α R G B

Dr. – CS576 Lecture 5 Page 5

AAPPPPLLIICCAATTIIOONNSS

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 6

NNEEEEDD FFOORR CCOOMMPPRREESSSSIIOONN

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 7

SSOOMMEE CCOOMMPPRREESSSSIIOONN FFOORRMMAATTSS

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 8

IIMMAAGGEE RREEDDUUNNDDAANNCCYY

• Spatial Redundancy

• Spectral Redundancy

Dr. – CS576 Lecture 5 Page 9

TTYYPPEESS OOFF IIMMAAGGEE CCOOMMPPRREESSSSIIOONN

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

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

Dr. – CS576 Lecture 5 Page 10

JJPPEEGG BBAACCKKGGRROOUUNNDD –– RREEQQUUIIRREEMMEENNTTSS AANNDD

SSEELLEECCTTIIOONN PPRROOCCEESSSS

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 11

JJPPEEGG IIMMAAGGEE CCOODDIINNGG

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 12

JJPPEEGG LLOOSSSSYY CCOODDEECC SSCCHHEEMMEE

Dr. – CS576 Lecture 5 Page 13

JJPPEEGG CCOOMMPPRREESSSSIIOONN AALLGGOORRIITTHHMMIICC

OOVVEERRVVIIEEWW

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 14

DDCCTT FFOORRMMUULLAA IINN 22DD

Discrete Cosine Transform

( ) ( )



 ++





= 

=

=

=

=

7

0

7

0 16

12
cos

16

12
cos),()()(

4

1
),(

x

x

y

y

vyux
yxfvCuCvuF



Inverse Discrete Cosine Transform

( ) ( )



 ++
= 

=

=

=

=

7

0

7

0 16

12
cos

16

12
cos),()()(

4

1
),(

x

u

y

v

vyux
vuFvCuCyxf



2
1)(),(: =vCuCwhere

, for u, v =0

1)(),( =vCuC otherwise

Dr. – CS576 Lecture 5 Page 15

WWHHAATT DDOO TTHHEE DDCCTT CCOOEEFFFFIICCIIEENNTTSS

RREEPPRREESSEENNTT

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 16

EEXXAAMMPPLLEESS OOFF 88XX88 DDCCTTSS

Dr. – CS576 Lecture 5 Page 17

EEXXAAMMPPLLEE OOFF 88XX88 DDCCTT BBAASSIISS FFUUNNCCTTIIOONNSS

Dr. – CS576 Lecture 5 Page 18

DDCCTT CCOOEEFFFFIICCIIEENNTT QQUUAANNTTIIZZAATTIIOONN

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 19

RRUULLEESS FFOORR DDCCTT CCOOEEFFFFIICCIIEENNTT QQUUAANNTTIIZZAATTIIOONN

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 20

EEXXAAMMPPLLEE

Dr. – CS576 Lecture 5 Page 21

EENNTTRROOPPYY CCOODDIINNGG OOFF DDCCTT CCOOEEFFSS

The quantized DCT coefficients are first processed in
zigzag order

Dr. – CS576 Lecture 5 Page 22

IINNTTEERRMMEEDDIIAATTEE RREEPPRREESSEENNTTAATTIIOONN

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 23

IINNTTEERRMMEEDDIIAATTEE RREEPPRREESSEENNTTAATTIIOONN ((22))

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 24

IINNTTEERRMMEEDDIIAATTEE RREEPPRREESSEENNTTAATTIIOONN ((33))

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 25

EENNTTRROOPPYY CCOODDIINNGG

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 26

LLOOSSSSLLEESSSS JJPPEEGG MMOODDEE

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 27

PPRROOGGRREESSSSIIVVEE EENNCCOODDIINNGG MMOODDEESS

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 28

PPRROOGGRREESSSSIIVVEE EENNCCOODDIINNGG ((22))

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 29

Dr. – CS576 Lecture 5 Page 30

PPRROOGGRREESSSSIIVVEE EENNCCOODDIINNGG ((33))

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 31

PPYYRRAAMMIIDD DDEECCOOMMPPOOSSIITTIIOONN

Dr. – CS576 Lecture 5 Page 32

PPYYRRAAMMIIDD DDEECCOOMMPPOOSSIITTIIOONN((22))

Dr. – CS576 Lecture 5 Page 33

JJPPEEGG PPEERRFFOORRMMAANNCCEESS

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

BBiittss//PPiixxeell QQuuaalliittyy CCoommpprreessssiioonn

RRaattiioo

0.25 Fair 64:1

0.5 Good 32:1

0.75 Very Good 21:1

1.5 Excellent 10:1

2 Indistinguishable 8:1

Dr. – CS576 Lecture 5 Page 34

AARRTTIIFFAACCTTSS OOFF JJPPEEGG –– OORRIIGGIINNAALL ((338800KKBB))

Dr. – CS576 Lecture 5 Page 35

AARRTTIIFFAACCTTSS OOFF JJPPEEGG –– CCOOMMPPRREESSSSEEDD ((4400KKBB))

Dr. – CS576 Lecture 5 Page 36

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 37

DDRRAAWWBBAACCKKSS OOFF DDCCTT –– SSTTAATTIIOONNAARRYY SSIIGGNNAALLSS

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

Dr. – CS576 Lecture 5 Page 38

DDRRAAWWBBAACCKKSS OOFF DDCCTT –– NNOONN SSTTAATTIIOONNAARRYY

Non stationary signals have frequencies that vary with time.

Dr. – CS576 Lecture 5 Page 39

TTIIMMEE FFRREEQQUUEENNCCYY AANNAALLYYSSIISS

Dr. – CS576 Lecture 5 Page 40

JJPPEEGG–22000000

Dr. – CS576 Lecture 5 Page 41

IINNTTRROODDUUCCTTIIOONN

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 42

JJPPEEGG–22000000 FFEEAATTUURREESS

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 43

JJPPEEGG–22000000 CCOOMMPPRREESSSSIIOONN SSTTEEPPSS

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 44

WWAAVVEELLEETT EENNCCOODDIINNGG OOFF AA SSIINNGGLLEE TTIILLEE

Dr. – CS576 Lecture 5 Page 45

SSPPAATTIIAALL AACCCCEESSSSIIBBIILLIITTYY

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 46

PPEERRFFOORRMMAANNCCEE

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 47

EEXXAAMMPPLLEESS –– OORRIIGGIINNAALL

Dr. – CS576 Lecture 5 Page 48

EEXXAAMMPPLLEESS

JPEG2000 JPEG

Dr. – CS576 Lecture 5 Page 49

CCOONNCCLLUUSSIIOONN

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 50

Dr. – CS576 Lecture 5 Page 51

DDIITTHHEERRIINNGG

Dr. – CS576 Lecture 5 Page 52

TTHHEE PPRROOBBLLEEMM

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

nD(i,j), where D(i,j) is the entry of D in the i-
th row and j-th column

Dr. – CS576 Lecture 5 Page 58

DDIITTHHEERRIINNGG ((EEXXAAMMPPLLEE))

Dr. – CS576 Lecture 5 Page 59

EERRRROORR DDIIFFFFUUSSIIOONN

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 60

EERRRROORR DDIIFFFFUUSSIIOONN AALLGGOORRIITTHHMM

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 61

EERRRROORR DDIIFFFFUUSSIIOONN –– EEXXAAMMPPLLEE