Image Compression

IMAGE COMPRESSION SUBMITTED BYMAHAK MALIK 2K4/IT/931 NIKHIL AGARWAL 2K4/IT/937 SHRUTI ARORA 2K4/IT/955

AGENDA What

is Image Compression? Why Image Compression? Lossless and lossy techniques Bitmap format Graphics Interchange Format Portable Network Graphics Format Tag Image File Format JPEG JPEG 2000

Video

◦ ◦ ◦ ◦ ◦ ◦ ◦

Compression Principles

Frames Types of frames I-frames P-frames B-frames PB-frames D-frames

Standards

◦ H.261 ◦ H.263 Conclusion References

What is Image Compression? A

technique used to reduce the volume of information to be transmitted about an image Width 1 Unit M=Number of Samples 1/2

Height 1 Unit

D

M

1/2

M

D=Spacing Between Samples

Why image compression? Requirements

may outstrip the anticipated increase of storage space and bandwidth For data storage and data transmission ◦ DVD ◦ Real time applications ◦ Printer Take advantage of : ◦ Spatial redundancy ◦ Temporal redundancy (videos)

Lossless or Lossy Compression Lossless

compression

◦ There is no information loss, and the image can be reconstructed exactly the same as the original ◦ e.g RLE ◦ Applications: Medical imagery, Archiving Lossy

compression

◦ Information loss is tolerable ◦ e.g JPEG 2000 ◦ Applications: commercial distribution (DVD) and rate constrained environment where lossless methods can not provide enough compression ratio

Bitmap Format Files

with .bmp extension Each pixel is represented by a fixed number of bits (integral power of 2) A typical BMP file usually contains the following blocks of data: o o o o

BMP Header Stores general information Bitmap Information Stores detailed information Color Palette Stores the definition of the colors Bitmap Data Stores the actual image, pixel by pixel.

Advantages Simple Widely

used Relatively well documented Free of patents

Disadvantages Minimum

or zero compression

Graphics Interchange Format 256

colors out of a palette of 224 colors are indexed  Uses LZW(patented by Unisys) Amongst the oldest formats available Supports animations Supports transparency and interlacing

Portable Network Graphics Format Developed

to improve upon and

replace GIF Supports 2D interlacing, transparency and variable color depth Uses lossless data compression method called DEFLATE Type

Bits per channel

Indexed

1

2

4

8

Greyscale

1

2

4

8

Greyscale & alpha

1 6 2

32

4 3 2

64

Truecolor Truecolor & alpha

48

16

A PNG image with an 8-bit transparency channel (left). The same image is overlaid onto a checkered background (right), to highlight the transparency.

The only disadvantage of png is that it doesn’t support animations.

Tag Image File Format Developed

by Aldus and Microsoft Tags used to indicate how data is arrange and compressed e.g LZW/RLE compression Advantages : ◦ Highly flexible and platform independent ◦ Widely used by scanning,faxing, word processing, image manipulation apps ◦ allows the inclusion of an unlimited amount of private or special-purpose information

◦ capable of describing bilevel, grayscale, palette-color, and fullcolor image data Disadvantages

:

◦ TIFF image can’t have more than 4GB of data ◦ Difficult to write TIFF readers which take advantage of all its features

JPEG Joint

Photographic Expert’s Group International standard for photographs Lossless/lossy Based on the facts that : ◦ Humans are more sensitive to lower spatial frequency components ◦ A large majority of useful image contents change relatively slowly across images

JPEG Encoding Cr

Y

Cb

f(i, j)

DCT

8x8

F(u, v)

Quantization

Fq(u, v)

8x8

Quant… Tables Zig Zag Scan

Coding Tables Header Tables Data

Entropy Coding

DPCM RLC

Steps involved : Image

converted to Y,Cb,Cr format Divided into 8x8 blocks Each 8x8 block subject to DCT followed by quantization Zig-zag scan DC coefficients stored using DPCM RLE used for AC coefficients Huffman encoding Frame generation

a. Zig-zag scan b. DPCM of DC coefficients c. RLE of AC coefficients

a. 45

1x64

54

1x64

48

1x64

45 9

1x64

1x64

-6

1x64

b. ... c.

0000011000000002 ... 5,1

7,2

1x64

Decoding Same

steps as encoding are performed in reverse

Advantages • Compression ratios of 20:1 are easily attained • 24-bits per pixel can be used leading to better accuracy • Progressive JPEG(interlacing)

Disadvantages Doesn’t support transparency • Doesn’t work well with sharp edges, they tend to blur unless high resolution is used • Almost always lossy • No target bit rate •

Performance

487x414 pixels, 487x414 pixels Uncompressed, 600471 Bytes,24 bpp 41174 Bytes, 1.63 bpp, CR=14 85502 Bytes, 3.39 bpp, CR=7

Comparative analysis

a. 256 color bmp 253 KB

d. Png 6.27 K

b. gif 4.08 KB

e. tiff 16.2 KB

c. jpeg 10.1 KB

JPEG 2000 Wavelet

based image compression standard

Encoding Decompose

source image into

components Decompose image and its components into rectangular tiles Apply wavelet transform on each tile Quantize and collect subbands of coefficients into rectangular arrays of “code-blocks” Encode so that certain ROI’s can be coded in a higher quality Add markers in the bitstream to allow error resilience

Wavelet transform of an image

Advantages Lossless

and lossy compression Progressive transmission by pixel accuracy and resolution Region-of-Interest Coding Random codestream access and processing Robustness to bit-errors Content-based description Side channel spatial information (transparency)

JPEG vs. JPEG 2000

512x512 image reconstructed after compression of 0.2 bpp using JPEG and JPEG 2000 respectively

Moving Images (Videos) Frames or Pictures Any

video can be thought up of as a sequence of digitized pictures or frames.

Types of Frame Coding Intra-frame

coding – spatial

redundancy JPEG algo applied to each frame independently -> moving JPEG or MJPEG typical compression ratios bw 10:1 and 20:1 not large enough to produce the needed compression ratios

Inter-frame

coding – temporal

redundancy Only a small portion of each frame is involved with any motion, so only info related to those segments is send

Frame types Intra-coded

frames or I-frame Inter-coded frames P-frame B-frame

I-frame Each

frame is coded independently Y (luminance) and Cb, Cr (chrominance) matrices encoded separately using JPEG algo I-frames frequently used in order to tackle corruption N = GOP = no. of frames bw successive I-frames, range(3,12)

P-frame Encoded

using a combination of either a preceding I-frame or P-frame No. of P-frames limited as errors propagate from one p-frame to another M = prediction span = no. of frames bw a P-frame and the immediately preceeding I-frame or P-frame

B-frame Second

type of prediction frame Their contents are predicted using both past and future frames Allows for occasional fast moving objects Provides better motion estimation Provides highest level of compression As they are not involved in coding of other frames they do not propagate errors

Decoding Operation  I-frame:

decoded immediately to recreate original frame  P-frame: info decoded, used with preceding I- or P-frame to derive the decoded frame contents  B-frame: info decoded, used with preceding I- or P-frame contents and succeeding I- or Pframe contents to derive the decoded frame contents  To minimize time required to decode Bframe, the order of encoding (and transmission) of the frames is altered so that both the preceding and succeeding frames are available when B-frame is being

PB-frame Two

neighboring P- and B-frames are encoded as if they were a single frame It increases the frame rate without increasing the resulting bit rate required.

D-frame Used

in movie / video-on-demand applications User may wish to rewind or fastforward the video This requires the compressed video to be decompressed at much higher speeds D-frames inserted at regular intervals throughout the stream By using only the encoded DC coefficients of each block of pixels in the periodically inserted D-frames, a low resolution sequence of frames is provided at much higher speeds

Implementation Issues In case of P-frames, the encoding of each macroblock is dependent on the motion estimation unit. There are 3 possibilities If the two contents are the same, only the address of the macroblock in the reference frame is encoded If the two contents are very close, both the motion vector and the difference matrices associated with the reference frame are encoded If no close match is found, then the target macroblock is encoded in the same way as a macroblock in an I-frame

Performance Compression

ratios for I-frames is similar to that obtained with JPEG and is typically between 10:1 and 20:1 depending on the complexity of the frame contents Compression ratios for P-frames and B-frames are higher and depend on the search algorithm used. Typical figures are 30:1 for P-frames and 30:1 through 50:1 for B-frames

H.261 Designed

by ITU-T for video-telephony and video-conferencing applications The first standard in which the macroblock concept appeared. Data rate was specified in multiples of 64Kbps key element: deblocking filtering Uses CIF (352x288) and QCIF (176x144) format

H.264   

 

H.264 is the standard of both ITU-T VCEG and ISO/IEC MPEG Gains in compression efficiency of up to 50% compared to previous standards New key features are: ◦ Enhanced motion compensation ◦ Small blocks for transform coding ◦ Integer transform ◦ Improved deblocking filter ◦ Enhanced entropy coding Increased complexity relative to prior standards Five resolutions (H.261 only does QCIF and CIF): CIF: 352x288 16CIF: 1408x1152 4CIF: 704x576

QCIF: 176x144 SQCIF: 128x96

Conclusion : Every

format has its own advantages and disadvantages. Depending upon the application the appropriate format should be used. Bmp is simple but heavy Only redeeming feature of gif : supports animations Png better than the rest in overall terms Tiff is appropriate where flexibility is needed

JPEG

is good for photography JPEG 2000 is an all encompassing standard

References : www.ieee.org www.en.wikipedia.org www.ilixis.com/developer/ http://www.libpng.org/pub/png/ http://www.w3.org http://www.jpeg.org Data

compression – The complete reference by David Salomon Multimedia Communications by Fred Halsall

“The

JPEG 2000 still image coding system” Charilaos Christopoulos, IEEE Transactions on Consumer Electronics, Vol. 46,November 2000 “The JPEG Still Picture Compression Standard” Gregory K. Wallace, IEEE Transactions on Consumer Electronics, Dec 1991

THANK YOU