Image Representation and Compression

Module 3
 Image
• Spatial representation of an object (2d or 3 d)
• Continuous function defining a rectangular region of a plane –
resulting values of light intensity at each point on planar region.
• For multimedia systems – digital image.
• Function need to be sampled at discrete intervals.

Pushpavathi.K.P, BMSCE
 Types of Images
• Graphics.
• Digitized documents.
• Digitized pictures.
• Two dimensional matrix of picture elements-Pixels.
• Type is represented differently – computer file/memory.

Pushpavathi.K.P, BMSCE
 Graphics
• Backbone of multimedia.
• Form - pictures, clip art, photography, line art..
• Created using - Software packages and programs, scanners, cameras.
• Composed of Visual objects – lines, arcs, circles, stars, hand drawn
objects.
• Drawing desired shape on the screen, edit the objects, store in files.
• Gallery of images with packages- Clip-art.

Pushpavathi.K.P, BMSCE
Graphics (Cntd.)
• Also include - textual information, tables, graphs.
• Fill or add shadows to the object-3D Effect.
• Display screen- two dimensional matrix of pixel.
• Each pixel have range of colors.

Pushpavathi.K.P, BMSCE
 Graphics principles (screen format)
Eg. VGA- Video graphics array – 640 X 480 pixels,
each pixel -8 bits
256 different colors.

Pushpavathi.K.P, BMSCE
Graphics (Cntd.)
• Objects and freeform objects- series of lines connected to each other.
• Number of attributes
-Shape-line, circle, square
-Size- pixel position of border
coordinates,
-Color
• Editing an object- changing the selected attributes
associated with the object.

Pushpavathi.K.P, BMSCE
Graphics (Cntd.)
• Object shape- open or closed.
• Open object- start of first line and end of last line at the border are not
connected - Do not start and end on the same pixel.
• Closed object- connected.
• Pixel assigned with the same color- color fill - Create the solid object-
process is called rendering.

Pushpavathi.K.P, BMSCE
Graphics (Cntd.)
• Graphics is analogous to the structure of program in an high level
language.
• Program- main body- procedures/ functions- parameters- specific
function.
• Graphics- set of commands(Attributes)- draw the different objects.
• Graphics- created by author/ set of standard objects/gallery.
• Different object commands in the correct sequence- desired graphics.

Pushpavathi.K.P, BMSCE
Two forms of representation - graphics
1. High level version – (similar to high level programming).
2. Actual pixel image - Bit map format (similar to low level machine
code of program).
• High level version is compact- less memory and bandwidth but
destination - must interpret various high level commands.
• Often bitmap format – used
• Standardized forms- GIF(graphical interchange format), TIFF( tagged
image file format).
• Software- SRGP(simple raster graphics package)- convert-high level
to pixel image.

Pushpavathi.K.P, BMSCE
 Digitized documents
• Scanner with a fax machine.
• Vertical resolution-3.85 or 7.7 lines/mm.
• Output of scanner- resolution of 8 pels
• 0 for white pixel and 1 for black pixel.
• Printer part reproduces the original image.

Pushpavathi.K.P, BMSCE
 Digitized Pictures
• scanners - digitize the monochromatic images (eg. printed picture).
• More than single bit to digitize.
• Eg. Black and white picture - 8 bits per picture element.
• 256 different levels of gray per element.
• Between white and black.
• 8 bit – grey level images.

Pushpavathi.K.P, BMSCE
 Color principles
• Whole spectrum of colors - color gamut.
• Three primary colors – Red(R), green(G), Blue(B).
• Spectrum of colors- different proportion of 3 primary colors.
• Additive color mixing –fig a – used - color image on black surface –
display applications.
• Complementary subtractive color mixing – fig b - used - color image
on white surface – printing applications.
• Picture tubes use this principle.
• Picture tubes are same in television and personal computers.

Pushpavathi.K.P, BMSCE
Pushpavathi.K.P, BMSCE
 Raster scan principles
• Picture tube operate- raster scan.
• Finely focused electron beam.
• Complete scan comprises- number of discrete horizontal lines.
• Progressive scanning.
• Complete set of N, horizontal scan lines- frames.
• N=525 or 625 lines

Pushpavathi.K.P, BMSCE
Raster scan principles (cntd.)

Pushpavathi.K.P, BMSCE
 Raster scan principles (cntd.)

• Inside display screen – light sensitive phosphor.

• Emits light when energized by electron beam.
• Brightness – power of electron beam.
• During retrace – electron beam is off.
• Black and white picture- single electron beam- white sensitive
phosphor.
• Separate beams, closely located for color tubes.

Pushpavathi.K.P, BMSCE
 Raster scan principles (cntd.)
• Set of 3 phosphors with each pixel- phosphor triad.
• Pixel has the shape of spot.
• Spot size – 0.025 inches.

Pushpavathi.K.P, BMSCE
 Raster scan principles (cntd.)
• Television picture tubes – display moving images
• Persistence of color decays quickly.
• Continuously refresh the screen.
• Moving image- light signals with each frame changes.
• Still image- same set of light signals.
• Frame refresh rate must be high.
• Low refresh rate- flicker.
• Frame Refresh Rate- 50 times per second.

Pushpavathi.K.P, BMSCE
 Raster scan principles (cntd.)
• Picture tube operate- analog mode.
• Digital television- digital pictures stored in memory
• color signals are in digital form.
• Fixed number of pixels per scan line.
• Pixels from each line are read from memory in time synchronism with
the scanning process.
• Digital to Analog convertor.
• Pixel image must be accessed continuously.
• Separate block of memory- RAM.

Pushpavathi.K.P, BMSCE
Pushpavathi.K.P, BMSCE
 Pixel Depth
• It is the number of bits per pixel.
• Determines - range of different colors.
• 12 bits- 4 bit per primary color- 4096 different colors.
• 24 bits- 8 bit per primary color- 16 million different colors.
• Eye cannot discriminate this range- hence, selected subset.
• Stored in table – each pixel value is used as address to a location.
• CLUT( color look up table).
• Pixel- 8 bit, CLUT- 24 bit, subset of 256 (28) colors from palette of
16 million (224).
• Reduced storage space.
Pushpavathi.K.P, BMSCE
Color look-up-table
Eg.:8-bit color image
• Store only the index (code value) for each pixel.
• Row-column order as long series of values.

Pushpavathi.K.P, BMSCE
 Aspect Ratio
• Number of pixels/ scanned line and the number of lines/frame vary.
• Ratio of screen width to screen height – aspect ratio.
• Aspect ratio – 4/3(older tubes), PC monitors, 16/9 (wide screen)
• American countries - 525 scan lines- National Television Standards
Committee (NTSC)
• European countries – 625 scan lines – Phase Alternating Line (PAL )
• Few lines - Carry control and other information.
• Hence , no. of visible lines/frame = vertical resolution in pixels

Pushpavathi.K.P, BMSCE
 Aspect Ratio (cntd.)
Visible lines per frame

Pushpavathi.K.P, BMSCE
 Aspect Ratio (cntd.)
Digitization spatial resolution

Pushpavathi.K.P, BMSCE
Digital Cameras and scanners
• Image captured- using image sensors in camera/scanner.
• Two dimensional grid- light sensitive cell- photo sites.
• Photo sites-stores - level of intensity of light.
• Charged coupled device( CCD) –widely used image sensor.
• Array of photo sites.
• Light intensity into equivalent electric charge.
• ADC.

Pushpavathi.K.P, BMSCE
Digital Cameras and scanners (cntd.)
Color image capture – schematic

Pushpavathi.K.P, BMSCE
Three methods for color images
• First method: surface of photo site- R,B,G filter.
• Charge determination- level of light.
• Coatings arranged – 3X3 grid structure.
• Color associated with each photo sites- output of photo sites together
with 8 immediate neighbors.
• Level of other two colors in each pixel- interpolation procedure.
• Consumer quality cameras.

Pushpavathi.K.P, BMSCE
Pushpavathi.K.P, BMSCE
Second method
• Single image sensors- three exposures.
• R,G,B filters.
• Color associated with each pixel- charge obtained with these three
filters.
• Drawback: Three separate exposures- each image.
• Cannot be used with video cameras.
• High resolution- still image cameras- photographic studios.

Pushpavathi.K.P, BMSCE
Third method
• Three separate image sensors.
• Photo sites coated- R,G,B filters.
• Single exposure-split the incoming light into 3 beams.
• Each exposes a separate image sensors.
• High resolution still and moving images.

Pushpavathi.K.P, BMSCE
Cntd.

• Image captured- stored in image sensor.

• Charge stored in photo site- read and digitized.
• CCD- set of charges- matrix- single row at a time.
• Transferred to readout register.
• Amplified and digitized- ADC.
• Store the image- number of file formats.
• TIFF.

Pushpavathi.K.P, BMSCE
Digital Image Representation
• Digital image – represented by the matrix of numerical values –
quantized intensity value
• Points at which image is sampled – pixel
• Pixel values of intensity images – grey scale levels
• Intensity at each pixel – determined from continuous image - by
averaging over a small neighbourhood around the pixel location.

Pushpavathi.K.P, BMSCE
Digital image representation (cntd.)
• 1-bit image representation (binary valued image) – black and white
• Bits required to represent the image = no. of pixel X no. of bits/pixel
= (8 x 8) x 1 = 64 bits

Pushpavathi.K.P, BMSCE
Digital image representation (cntd.)
2- bit image :
• Bits/pixel = 2, total no. of shades = 4
• Shades represented as {0,1,2,3} or {00,01,10,11}
• Size of image = (8 x 8) x 2 = 128 bits

Pushpavathi.K.P, BMSCE
Image format
• Captured image format (capture image)– 2 parameters
1. Spatial resolution – pixel x pixel
2. Colour encoding – bits/pixel – commonly 1- bit, 8- bit, 24- bit
• Stored image format (store image) – 2D array of values that represent
the data associated with pixel in image.
• File formats for storing images - GIFF, TIFF, JPEG

Pushpavathi.K.P, BMSCE
Graphics format
• Not represented by pixel matrix
• Specified by primitives and attributes
• Primitives –lines, rectangles, circles, ellipse
• Attributes – line width, line style…
• This is high level representation - need to be converted to low level
representation
• Advantage – reduction of data to be stored per image and can be
manipulated.

Pushpavathi.K.P, BMSCE
Image compression
• Basic types of image: computer generated (graphics)
and digitized images (documents & pictures).
• Graphical image representation - differently in file system.
• Typically – in form of program in graphical programming language-
less memory & transmission bandwidth .
• Transfer of graphical images- lossless compression algorithm.
• Different compression algorithms and file formats.

Pushpavathi.K.P, BMSCE
Image compression (cntd.)

• Digitized images- two schemes are used.

• Combination of run length and statistical encoding.
• Transform, differential and run length encoding.

Pushpavathi.K.P, BMSCE
Graphics interchange format(GIF)
• Used for representation and compression of graphical images.
• Supports color images- 24 bit pixels.
• Choose 256 colors from 224 original set.
• Only 8-bit index to table entry that contain closest match to original is
sent – compression ratio of 3:1
• Global color table – color table that relate to whole image.
• Local color table - color table that relate to portion of image.
• Contents of table, compressed image data, screen size and aspect ratio
–sent across network – standardized format

Pushpavathi.K.P, BMSCE
Graphics interchange format(cntd.)
Principle of the scheme – basic operational mode

Pushpavathi.K.P, BMSCE
Graphics interchange format(cntd.)
LZW coding algorithm- further levels of compression – by extending
the color table dynamically.

Pushpavathi.K.P, BMSCE
Graphics interchange format(cntd.)
• Long strings of same color- detected-entered into color table after 256
selected colors
• 8-bit indices - used to represent basic color table.
• Image stored and transferred- interlaced mode.
• Transfer image- over lower bit rate channel or the internet.
• Compressed image data- organized.
• Decompressed image- progressive way as data arrives.
• Compressed data- four groups - 1/8, 1/8, 1/4, 1/2.

Pushpavathi.K.P, BMSCE
GIF interlaced mode

Pushpavathi.K.P, BMSCE
GIF file format
• Signature – 6 Bytes
• Screen descriptor – 7 byte set of flags
• Mapping 8 bits to 24 bits RGB values
• If local table is absent,
Global table is used

Pushpavathi.K.P, BMSCE
GIF screen descriptor

• Screen width – 2 bytes

• Screen height – 2 bytes
• Background color – 1 byte
• m is ‘0’ – if no global color map
• Cr – color resolution -3 bits
• Pixel – 3 bits – no. of bits/pixel in
image as stored in file

Pushpavathi.K.P, BMSCE
GIF image descriptor
1 byte – image separator character (comma)
2, 3 byte – start of image (from left side of screen)
4,5 - start of image (from top of screen)
6,7 – width of image
8,9 – height of image
(In pixels, LSB first)

Pushpavathi.K.P, BMSCE
Tagged image file format (TIFF)
• Supports pixel resolution upto 48 bits -16 bits each- R,G ,and B.
• Transfer both images and digitized documents.
• Format used is indicted by code number
• range from code number 1 (uncompressed format) to code no. 5
(LZW compressed).
• Code number 2,3,4 – used with digitized documents.
• Same compression algorithm as in Fax m/c.
• LZW algorithm – same as in GIF
• Starts with basic color table – 256 colors and extended upto 4096
entries
Pushpavathi.K.P, BMSCE
Digitised documents
• ITU –T standards
group 3 (T4) – use with PSTN (with modems)
group 4 (T5) – add digital - ISDN
• Both use data compression, compression ratio > 10:1
• Time taken to transmit a document page is < 1 minute (T4) and < sec
(T5)

Pushpavathi.K.P, BMSCE
Modified Modified READ (MMR) coding
• 2D coding as it identifies black and white run-lengths
• By comparing adjacent scan lines.
• READ – Relative Element Address Designate.
• Fact – scanned lines differ from previous line by only a few pels.
• Run-lengths associated with the line – identified by comparing the line
contents – coding Line (CL) relative to immediately preceeding line –
reference line (RL)
• Assume – first reference line –all white line.

Pushpavathi.K.P, BMSCE
codes

Pushpavathi.K.P, BMSCE
Run-length possibilities (modes)
• Relative to reference line (RL)
• Identified by position of next run-length in RL (b1b2) relative to start
and end of the next pair of run-length in CL (aoa1 and a1a2)
• Three possibilities or modes.

Pushpavathi.K.P, BMSCE
Pass mode
Run-length in RL , b1b2 is to left of run-length in CL , a1a2.

Pushpavathi.K.P, BMSCE
Vertical mode
• Run-length in RL ,b1b2 overlaps the next run-length in CL, a1a2 – 3
pels
• Difference run-length a1b1 is coded

Pushpavathi.K.P, BMSCE
Horizontal mode
• Run-length in RL , b1b2 overlaps the next run-length in CL,a1a2 –
> 3 pels
• Two run-length, a0a1 and a1a2 are coded.

Pushpavathi.K.P, BMSCE
MMR coding procedure

Pushpavathi.K.P, BMSCE
JPEG
• Joint Photographic Expert Group –compression standard
• Compression ratio ranging from 15:1 to 25:1
• Defines a range of compression modes, each used in particular
application domain.
• Lossy sequential mode or baseline mode.
• Used for both monochromatic and color digitized image

Pushpavathi.K.P, BMSCE
5 main stages associated with baseline mode
• Image / block preparation
• Forward DCT
• Quantization
• Entropy encoding
• Frame building.

Pushpavathi.K.P, BMSCE
JPEG encoder schematic

Pushpavathi.K.P, BMSCE
Image/block preparation
Two steps –1) image preparation

Pushpavathi.K.P, BMSCE
Image/block preparation (cntd.)
2)block preparation

Pushpavathi.K.P, BMSCE
Forward DCT
• Mathematical technique – transform a 2D matrix of pixel values into
an equivalent matrix of spatial frequency components (coefficients) –
lossless
• Any frequency components (coefficients) in matrix with amplitude
< defined threshold is dropped – lossy
• To compute forward DCT, 1) all the values are centered around zero-
by subtracting 128 from each intensity /luminance value.
2) Compute the DCT of each 8 x 8 block of values using the expression.

Pushpavathi.K.P, BMSCE
Forward DCT (cntd.)
P[x,y] – input 2D matrix, F[i,j] – transformed matrix

Pushpavathi.K.P, BMSCE
DCT computation features

Pushpavathi.K.P, BMSCE
quantization
• Aims to reduce the size of DC and AC coefficients
• Reduce transmission bandwidth
• Instead of comparing each coefficient with threshold value, division is
performed using defined threshold value as divisor.
• If resulting quotient (rounded) = 0 , coefficient is < threshold.
• If non-zero, indicated the no. of times the coefficient is > threshold.
• Ex if divisor =16, will save 4 bits over the use of absolute value
• At decoder , multiply the received value by corresponding threshold
value.

Pushpavathi.K.P, BMSCE
Computation of a set of quantized DCT coefficients ,
an example

Pushpavathi.K.P, BMSCE
Quantization (cntd)
• Choice of threshold value – important – compromise between level of
compression needed and amount of information loss accepted.
• Rounding the quotient to nearest integer value
• Threshold value increase in magnitude with increase in spatial
frequency
• DC coefficients in transformed matrix is largest
• Most of higher frequency coefficients are zero

Pushpavathi.K.P, BMSCE
Quantization (cntd)

Pushpavathi.K.P, BMSCE
Entropy encoding
• 4 steps
Vectoring - process of representing the values in matrix - in the form of
single dimensional vector.
Differential encoding
Runlength encoding
Huffman encoding

Pushpavathi.K.P, BMSCE
Vectoring
Zig-zag scan – make it suitable for compression

Pushpavathi.K.P, BMSCE
Differential encoding
• Applied to DC coefficient
• It Is the largest coefficient
• Resolution is as high as possible during the quantization phase.
• Small physical area in each block – vary slowly from block to block.
• The difference in magnitude of DC coefficient in a quantised block
relative to the value in preceding block is encoded.
• Reduction in no. of bits required to encode.

Pushpavathi.K.P, BMSCE
Runlength encoding
• Applied to AC coefficients of the vector (63)
• Encoded in the form of a string of pairs of values
• Each pair is made of (skip , value)
• Skip – no. of zeroes in the run
• Value – next non-zero coefficient
• Ez. (0,6)(0,7)(0,3)(0,3)(0,3)(0,2)(0,2)(0,2)(0,2)(0,0)
• (0,0) – indicate the end of the string for the block and all the remaining
coefficients in the block are zeroes.

Pushpavathi.K.P, BMSCE
Huffman encoding
• Used to encode the output of both differential and runlength encoders
• Variable length coding stage

Pushpavathi.K.P, BMSCE
Frame building
To encapsulate all the information relating to an encoded image /picture
in this format

Pushpavathi.K.P, BMSCE
JPEG decoder

Pushpavathi.K.P, BMSCE
JPEG 2000 standard
• To provide improved image quality, better rate-distortion trade-off and
additional functionalities
• Wavelet based standard for still image compression.
• High compression efficiency
• Handles large images
• Compress once, decompress many ways approach.

Pushpavathi.K.P, BMSCE
Reference
Multimedia communications Applications, Networks, Protocols and
standards - Fred Halsall
Multimedia communication components, techniques, standards -
Krishna Kumar D N

Pushpavathi.K.P, BMSCE