Image

compression
• Image compression, the art and science of reducing the amount of
data required to represent an image, is one of the most useful and
commercially successful technologies in the field of digital image
processing.
• The term data compression refers to the process of reducing the
amount of data required to represent a given quantity of information.
• Data are the means by which information is conveyed.
• Because various amounts of data can be used to represent the same
amount of information, representations that contain
irrelevant or repeated information are said to contain redundant data.
• If we let b and b′ denote the number of bits (or information- carrying
units) in two representations of the same information, the relative
data redundancy, R, of the representation with b bits is
If C = 10 (sometimes written 10:1), for instance, the
larger representation has 10 bits of data for every 1 bit
of data in the smaller representation. The
corresponding relative data redundancy of the larger
representation is 0.9 (R = 0.9), indicating that 90% of
its data is redundant.
• Two-dimensional intensity arrays suffer from three principal types of data
redundancies that can be identified and exploited:
• 1. Coding redundancy. A code is a system of symbols (letters, numbers, bits,
and the like) used to represent a body of information or set of events. Each
piece of information or event is assigned a sequence of code symbols, called a
code word. The number of symbols in each code word is its length.
• The 8-bit codes that are used to represent the intensities in most 2-D intensity
arrays contain more bits than are needed to represent the intensities.
• 2. Spatial and temporal redundancy. Because the pixels of most 2-D
intensity arrays are correlated spatially, information is unnecessarily replicated
in the representations of the correlated pixels.
• In a video sequence, temporally correlated pixels (i.e., those similar to or
dependent upon pixels in nearby frames) also duplicate information.
• 3. Irrelevant information. Most 2-D intensity arrays contain information that
is ignored by the human visual system and/or extraneous to the intended use of
the image. It is redundant in the sense that it is not used
CODING REDUNDANCY
A simple illustration of variable-length coding.

In the scheme designated as

code 2
Lavg=0.25(2)+0.47(1)+0.2
5(3)+0.03(3)=1.81
The total number of bits needed to
represent the entire image is

MNLavg=256*256*1.81=118,621.
The resulting compression and corresponding relative
redundancy are

Thus, 77.4% of the data in the original 8-bit 2-D intensity array is
redundant.

The compression achieved by code 2 results from assigning fewer bits to the
more probable intensity values than to the less probable ones.
 SPATIAL AND TEMPORAL REDUNDANCY
• Consider the computer-generated collection of constant
intensity lines in Fig.
In the corresponding 2-D intensity array:
• 1. All 256 intensities are equally probable. As Fig. 8.2 shows,
the histogram of the image is uniform.
• 2. Because the intensity of each line was selected randomly,
its pixels are independent of one another in the vertical
direction.
• 3. Because the pixels along each line are identical, they are
maximally correlated (completely dependent on one another)
in the horizontal direction.
• There exists a significant spatial redundancy that can be
eliminated by representing the image as a sequence of run-
length pairs, where each run-length pair specifies the start
of a new intensity and the number of consecutive pixels
that have that intensity.
• A run-length based representation compresses the original 2-D, 8-bit
intensity array by

• Or 128:1.
• In most images, pixels are correlated spatially (in both x and y) and in
time (when the image is part of a video sequence).
• Because most pixel intensities can be predicted reasonably well
from neighboring intensities, the information carried by a single pixel
is small.
• Much of its visual contribution is redundant in the sense that it can
be inferred from its neighbors.
• To reduce the redundancy associated with spatially and temporally
correlated pixels, a 2-D intensity array must be transformed into a
more efficient but usually “non-visual” representation.
• For example, run-lengths or the differences between
adjacent pixels can be used. Transformations of this type
are called mappings.

• A mapping is said to be reversible if the pixels of the

original 2-D intensity array can be reconstructed without
error from the transformed data set; otherwise, the
mapping is said to be irreversible.
 IRRELEVANT INFORMATION
• One of the simplest ways to compress a set of data is to remove
superfluous data from the set.
• In the context of digital image compression, information that is
ignored by the human visual system, or is extraneous to the
intended use of an image, are obvious candidates for omission.
• Thus, the computer-generated image in Fig. 8.1(c), because it
appears to be a homogeneous field of gray, can be represented
by its average intensity alone—a single 8-bit value.
• Of course, the original t image must be recreated to view and/or
analyze it, but there would be little or no perceived decrease in
reconstructed image quality.
• There are several intensity values (125 through 131) actually present. The
human visual system averages these intensities, perceives only the average
value, then ignores the small changes in intensity that are present in
this case.

• Figure 8.3(b), a histogram equalized version of the image in Fig. 8.1(c),

makes the intensity changes visible and reveals two previously undetected
regions of constant intensity—one oriented vertically, and the other
horizontally.
• If the image in Fig. 8.1(c) is represented by its average value alone, this
“invisible” structure (i.e., the constant intensity regions) and the random
intensity variations surrounding them (real information) is lost.
• Whether or not this information should be preserved is application
dependent.
• If the information is important, as it might be in a medical application like
digital X-ray archival, it should not be omitted; otherwise, the information is
redundant and can be excluded for the sake of compression performance.
• Because its omission results in a loss of quantitative
information, its removal is commonly referred to as
quantization.
• Because information is lost, quantization is an
irreversible operation.
 IMAGE COMPRESSION MODELS
• An image compression system is composed of two distinct
functional
components: an encoder and a decoder.
• The encoder performs compression, and the decoder
performs the complementary operation of
decompression.
• Both operations can be performed in software, as is the case
in Web browsers and many commercial image-editing
applications, or in a combination of hardware and firm ware,
as in commercial DVD players.
• A codec is a device or program that is capable of both
encoding and decoding
 The Encoding or Compression Process

In the first stage of the encoding process, a mapper transforms f (x ,y )

into a (usually nonvisual) format designed to reduce spatial and temporal
redundancy.
This operation generally is reversible, and may or may not directly reduce the
amount of data required to represent the image.
Run-length coding is an example of a mapping that normally yields
compression in the first step of the encoding process.
The mapping of an image into a set of less correlated transform
coefficients is another example (the coefficients must be further processed to
achieve compression).
In video applications, the mapper uses previous (and, in some cases,
future) video frames to facilitate the removal of temporal redundancy.
• The quantizer in Fig. 8.5 reduces the accuracy of the mapper’s
output in accor dance with a pre-established fidelity criterion.
• The goal is to keep irrelevant information out of the
compressed representation. As noted earlier, this operation is
irreversible.
• It must be omitted when error-free compression is desired. In
video applications, the bit rate of the encoded output is often
measured (in bits/second), and is used to adjust the operation
of the quantizer so a predetermined average output rate is
maintained.
• Thus, the visual quality of the output can vary from frame to
frame as a function of image content
• In the third and final stage of the encoding process, the
symbol coder , generates a fixed-length or variable-
length code to represent the quantizer output, and maps
the output in accordance with the code.

• In many cases, a variable-length code is used. The shortest

code words are assigned to the most frequently occurring
quantizer output values, thus minimizing coding redundancy.
• This operation is reversible. Upon its completion, the input
image has been processed for the removal of each of the
three redundancies
The Decoding or Decompression Process

• The decoder of Fig. 8.5 contains only two components: a

symbol decoder and an inverse mapper.
• They perform, in reverse order, the inverse operations of
the encoder’s symbol encoder and mapper.
• Because quantization results in irreversible information
loss, an inverse quantizer block is not included in the
general decoder model.
• In video applications, decoded output frames are
maintained in an internal frame store (not shown) and used
to reinsert the temporal redundancy that was removed at
the encoder.
 Some Basic Compression Methods
• 1. Lossless Compression
• Lossless compression reduces file size without losing any data. When
decompressed, the original data is perfectly restored. This is useful for text,
software, and high-quality image storage where data integrity is crucial.
• 🔹 Common Lossless Methods:
• Huffman Coding – Assigns shorter codes to frequently occurring symbols.
• Run-Length Encoding (RLE) – Replaces repeated data with a shorter
representation.
• Lempel-Ziv-Welch (LZW) – Used in GIFs and ZIP files for efficient text and
image compression.
• DEFLATE – A combination of LZ77 and Huffman coding, used in PNG and ZIP
files.
 HUFFMAN CODING
• One of the most popular techniques for removing coding
redundancy is due to Huffman (Huffman [1952]).
• When coding the symbols of an information source individually,
Huffman coding yields the smallest possible number of
code symbols per source symbol.
• The resulting code is optimal for a fixed value of n, subject to
the constraint that the source symbols be coded one at a time.
• In practice, the source symbols may be either the intensities
of an image or the output of an intensity mapping
operation (pixel differences, run lengths, and so on).
• The first step in Huffman’s approach is to create a series of
source reductions by ordering the probabilities of the
symbols under consideration, then combining the lowest
probability symbols into a single symbol that replaces
them in the next source reduction.
• The second step in Huffman’s procedure is to code each
reduced source, starting with the smallest source and
working back to the original source.
Step 1: Construct Frequency Table Example
Suppose we have the following pixel values in a small grayscale image:
[150, 150, 150, 150, 160, 160, 170, 170, 170, 180, 180, 190]

Count the frequency of each unique pixel value:

150-4 160-2 170-3 180-2 190-1
Step 2: Build Huffman Tree
Create leaf nodes for each pixel value based on frequency.
Merge the two least frequent nodes iteratively until one root node remains.
Step 1: Merge (190) + (180) → Node (3)
Step 2: Merge (160) + (3) → Node (5)
Step 3: Merge (170) + (5) → Node (8)
Step 4: Merge (150) + (8) → Root (12)
 Original Pixels: [150, 150, 150, 150, 160, 160, 170, 170, 170,
180, 180, 190]
Huffman Encoding: [ 0, 0, 0, 0, 110, 110, 10, 10, 10,
Compression Efficiency
1110, 1110, 1111]
•Original Storage: 12 pixels × 8 bits = 96 bits
•Compressed Storage: (28 bits, significantly reduced!)
• After the code has been created, coding and/or error-free
decoding is accomplished in a simple lookup table
manner.
• The code itself is an instantaneous uniquely decodable block
code.
• It is called a block code because each source symbol is
mapped into a fixed sequence of code symbols.
• It is instantaneous because each code word in a string of
code symbols can be decoded without referencing
succeeding symbols.
• It is uniquely decodable because any string of code
symbols can be decoded in only one way.
 ARITHMETIC CODING

• Arithmetic coding generates nonblock codes.

• A one-to-one correspondence between source symbols and code
words does not exist.
• Instead, an entire sequence of source symbols (or message) is
assigned a single arithmetic code word.
• The code word itself defines an interval of real numbers between 0
and 1.
• As the number of symbols in the message increases, the interval used
to represent it becomes smaller, and the number of information units
(say, bits) required to represent the interval becomes larger.
• Each symbol of the message reduces the size of the interval in
accordance with its probability of occurrence.
• it achieves (but only in theory) the bound established by Shannon’s
first theorem
• Figure 8.12 illustrates the basic arithmetic coding
process. Here, a five-symbol sequence or message,
a1a2a3a3a4, from a four-symbol source is coded. At
the start of the coding process, the message is
assumed to occupy the entire half-open interval [0,
1).
• As Table 8.7 shows, this interval is subdivided
initially into four regions based on the probabilities
of each source symbol.
• Let's perform arithmetic coding for the message
"a1a2a3a3a4" using the given probabilities:
ADAPTIVE CONTEXT DEPENDENT PROBABILITY ESTIMATES

• Inaccurate probability models can lead to non-optimal results. A simple way

to improve the accuracy of the probabilities employed is to use an
adaptive,
context dependent probability model.
• Adaptive probability models update symbol probabilities as symbols are
coded or become known. Thus, the probabilities adapt to the local statistics
of the symbols being coded.
• Context-dependent models provide probabilities that are based on a
predefined neighborhood of pixels, called the context, around the symbols
being coded.
• Q-coder (Pennebaker et al. [1988]) and MQ-coder (ISO/IEC [2000]), two
well-known arithmetic coding techniques.
 RUN-LENGTH CODING
• Images with repeating intensities along their rows (or columns)
can often be compressed by representing runs of identical
intensities as run-length pairs, where each run-length pair
specifies the start of a new intensity and the number of
consecutive pixels that have that intensity.
• The technique, referred to as run length encoding (RLE) images
with repeating intensities along their rows (or columns) can
often be compressed by representing runs of identical
intensities as run-length pairs, where each run-length pair
specifies the start of a new intensity and the number of
consecutive pixels that have that intensity.
• The technique, referred to as run length encoding (RLE)
• Run-length encoding is particularly effective when
compressing binary images. Because there are only two
possible intensities (black and white), adjacent pixels are
more likely to be identical.
• Run-length encoding (RLE) is particularly effective for
compressing binary images (black and white) due to the
high probability of consecutive identical pixels.