Contents

► Recall
► LZW Coding
► Introduction
► Methodology of LZW coding

Image Compression ►
► Advantages and Disadvantages of LZW Coding
Run Length Coding

Models ►

►
Introduction
Methodology of RLE Coding
LZW Coding, Run Length Coding, Bit Plane Coding ► 1D CCITT and 2D CCITT Compression
► Bit Plane Coding
► Introduction
► Decomposition Approaches
► Example

Recall
► LZW Coding
Introduction
► Lempel-Ziv-Welch (LZW) coding is the foremost technique for general purpose data
compression due to its simplicity and versatility.
► It is invented by Abraham Lempel, Jacob Ziv, and Terry Welch
► Lossless compression technique
► It is an error free compression approach and it also addresses spatial redundancies in
an image
► Key feature - Prior knowledge of probability of occurrence of symbols to be encoded is
not required.
► LZW coding is used in the GIF, TIFF, PDF formats

Basic Principles of LZW coding

Example ► LZW coding assigns fixed length code words to variable length 127 127 127 127

►
sequence of input symbols. 25 25 25 25
► The coding is based on a “dictionary” or “codebook” containing 25 25 127 127
the source symbols to be encoded. The coding starts with an
initial dictionary, which is enlarged with the arrival of new symbol 127 127 127 127
sequences.
► For 8-bit monochrome images, the first 256 words of the
dictionary are assigned to intensities 0, 1, 2, 255.
► As the encoder sequentially examines image pixels, intensity
sequences that are not in the dictionary, LZW coding allocates the
location 256 to the sequence.
► Here a 9-bit, 512-word dictionary is employed in the coding
process, the original bits that were used to represent the two
pixels are replaced by a single 9-bit code word.
► the size of the dictionary is an important system parameter.
► If dictionary is too small, the detection of matching intensity-level
sequences will be less likely; if dictionary is too large, the size of
the code words will adversely affect compression performance.
Methodology of LZW Coding with an example
Recognition Pixel Encoded output Dict. Loc.
Code word
Dict. Entry Example 2(other method)
► Use the LZW coding algorithm to encode Encoded output Index Entry
Consider the 4X4, 8 bit image 39
and decode the following sequence
39 39 39 256 39-39 1 a
39 39 126 126
39 39 126 126
39 126 39 257 39-126
“ababbabcababba” initial 2 b
126 126 126 258 126-126 entry table
39 39 126 126 3 c
126 39 126 259 126-39 Index entry
39 39 126 126 39 39 1 a 1 4 ab
39-39 126 256 260 39-39-126
2 b 2 5 ba
126 126
Encoded output : 3 c 4 6 abb
126-126 39 258 261 126-126-39
39,39,126,126,256,258,260,259,
39 39 Solution:- encoded output: 5 7 bab
257,126 39-39 126 1,2,4,5,2,3,4,6,1
2 8 bc
39-39-126 126 260 262 39-39-126-126
3 9 ca
126 39
126-39 39 259 263 126-39-39 4 10 aba
39 126 6 11 abba
39-126 126 257 264 39-126-126
1
126 126

Example 2(other method) – Decoding Part Advantages and Disadvantages of LZW coding
► Use the LZW coding algorithm to encode and Index Entry Advantages:
decode the following sequence
► Extremely effective when there are repeated patterns in the data that are widely spread
initial entry table 1 a
decoded input: 1,2,4,5,2,3,4,6,1 ► Prior knowledge of probability of occurrence of symbols to be encoded is not required.
2 b
Index entry ► Simple coding technique with high compression ratio.
3 c ► LZW compression is fast
1 a
2 b 4 ab ► Lossless compression technique
3 c 5 ba Disadvantages:
► Creates entries in the dictionary that may never be used.
Solution:- 1- a 6 abb
► LZW is a fairly old compression technique
2-ab
Applications :
4-abab
► LZW compression can be used in a variety of file formats:
5-ababba
► TIFF (tagged image file format )files
2-ababbab
► GIF (graphic interchange format ) files
3-ababbabc
► PDF(portable document format) files
4-ababbabcab
► Unix Compress, gzip.
6-ababbabcababb
► Suitable for compressing text files
1-ababbabcababba
Decoded output :- “ababbabcababba”

Run Length Coding

Introduction Example
► Uncompressed, a character run of 15 A characters would normally require 15
► Developed in 1950s bytes but after RLE encoding, it needs two bytes only.
► Designed as Facsimile(FAX) coding method AAAAAAAAAAAAAAA (15 bytes) 15A (2 bytes)
► It represent runs of identical intensities as run-length pairs (start of a new intensity AAAAAAbbbXXXXXt (15bytes) 6A3b5X1t (8 bytes)
and the number of consecutive pixels with that intensity)
Xtmprsqzntwlfb (14 bytes) 1X1t1m1p1r1s1q1z1n1t1w1l1f1b (28
× For few (or no) runs of identical pixels, run-length encoding results in data bytes)
expansion instead of compression. Concept: Coding of Binary Images
Coding of BMP File ► Run-length encoding is particularly effective when compressing binary images.
Because there are only two possible intensities (black and white), adjacent
► BMP file format uses a RLE in which image data is represented in two different pixels are more likely to be identical.
modes:
► The basic idea is to code each contiguous group (i.e., run) of or 1s encountered
► Encoded mode Absolute Mode in a left to right scan of a row by its length and to establish a convention for
determining the value of the run.
Byte 1 Byte2 Second Byte Condition ► The most common conventions are
No. of The color index value
(1) to specify the value of the first run of each row, or
Consecutive 0 End of line
pixels
(2) to assume that each row begins with a white run, whose run length may in
1 End of image fact be zero.
2 Move to a new position ► Although Run-length encoding is in itself an effective method of compressing
binary images, additional compression can be achieved by variable-length
3-255 Specify pixels individually coding the run lengths themselves.
Concept: Coding of Binary Images 1-D CCITT Group 3 Compression Standard
► ► Each line of an image is encoded as a series of variable-length Huffman code
in a left to right scan called Modified Huffman (MH) Coding
► Two types of Codewords involves Terminating Code (run length r<63) and
Makeup Code (run length r>63)
► Requires each line to begin with a white run-length code 00110101 of length
0.
► End-of-line (EOL) code 000000000001 is used to terminate each line as well as
to signal the first line of each new image.
► Six consecutive EOLs indicates the end of image.

2-D CCITT Group 4 Compression Standard

►

Bit Plane Coding

►
 Bit Plane Coding

111 100 011 001 Bit Plane Coding

7 4 3 1 001 011 110 101
► The inherent disadvantage of this decomposition approach is that small
1 3 6 5
110 011 010 001 changes in intensity can have a significant impact on the complexity of the bit
6 3 2 1 planes.
0 0 7 7 000 000 111 111 127 01111111
MSB Plane 128 10000000
LSB Plane
Centre bit
Plane

1 1 0 0 1 0 1 0 1 0 1 1 ► If a pixel of intensity 127 (01111111) is adjacent to a pixel of intensity 128

(10000000), for instance, every bit plane will contain a corresponding 0 to
0 0 1 1 0 1 1 0 1 1 0 1 1(or 1 to 0) transition
1 0 0 0 1 1 1 0 0 1 0 1
► Here all the numbers are complement each other.
0 0 1 1 0 0 1 1 0 0 1 1
► To solve the above issue we move to gray code concept

Gray Code to Binary Code

Binary to Gray Code approach 127
►
127
►
0 1 0 0 0 0 0 0
1
0 1 1 1 1 1 1
1
0 1 1 1 1 1 1
1
0 0 0 0 0 0 0

128

128 1 0 0
1 0 0 0 0
0
1 0 0 0 0 0 0
0
1 0 0 0 0 0 0
1
1 0 0 0 0 0 0

Thank You