Digital Image Processing (DIP)

AIML302
UNIT-2 : Concept of Image compression, lossless techniques (Huffman Coding,
Arithmetic and Lempel-Ziv Coding, Other Coding Techniques) and lossy
compression techniques (Transform Coding & K-L Transforms, Discrete Cosine
Transforms, and BTC), Enhancement in spatial and transform domain, histogram
equalization, Directional Smoothing, Median, Geometric mean, Harmonic mean,
Homo-morphic filtering

….………………………………………………………………………………………

Image Compression Questions:

1. What is the primary goal of image compression?

Image compression is a crucial technique used to reduce the size of digital images
while preserving their visual quality.

Size Reduction:

1. The primary goal of image compression is to minimize the file size of images.
Smaller files are advantageous for various reasons:
1. Faster Transmission: Smaller image files can be transmitted more
quickly over networks, making web pages load faster and improving
user experience.
2. Storage Efficiency: Reduced file sizes save storage space on devices,
servers, and cloud storage.
3. Bandwidth Conservation: In scenarios with limited bandwidth (such as
mobile networks), compressed images consume less data.

Lossless vs. Lossy Compression:

1. Image compression techniques fall into two main categories:

1. Lossless Compression: In lossless compression, the original image can
be perfectly reconstructed from the compressed version. It achieves size
reduction without sacrificing any image quality. Common lossless
formats include PNG and GIF.
2. Lossy Compression: Lossy compression sacrifices some image quality
to achieve greater compression ratios. It discards non-essential
information imperceptible to the human eye. JPEG is a popular lossy
format.

Visual Quality Preservation:

1. While reducing file size, image compression aims to maintain acceptable visual
quality. The challenge lies in finding a balance between compression and
perceptual fidelity.
2. In lossy compression, the quantization process reduces color information, but
the goal is to minimize visible artifacts (such as blockiness or blurring).
 Applications of Image Compression:

1. Web Content: Compressed images enhance website performance by loading

faster. They contribute to better SEO rankings and user engagement.
2. Streaming Services: Video streaming platforms use compressed images to
deliver high-quality content efficiently.
3. Medical Imaging: Compressed medical images (such as X-rays and MRIs)
enable efficient storage and transmission within healthcare systems.
4. Satellite Imagery: Compressed satellite images allow real-time monitoring and
analysis.

Compression Algorithms:

1. Various algorithms achieve image compression:

1. Run-Length Encoding (RLE): Simple method for lossless compression.

2. Huffman Coding: Efficient for lossless compression.
3. Discrete Cosine Transform (DCT): Used in JPEG for lossy
compression.
4. Wavelet Transform: Used in JPEG2000.
5. Predictive Coding: Explores spatial redundancy.
6. Quantization: Determines how much information to discard (lossy
compression).

Trade-offs:

1. Compression Ratio vs. Quality: Higher compression ratios often lead to lower
image quality.
2. Computational Complexity: Some compression algorithms require significant
computational resources.
3. Context: The context (web, medical, artistic, etc.) determines the acceptable
trade-offs.

In summary, image compression aims to strike a balance between reducing file size
and maintaining visual fidelity, benefiting various domains where efficient image
handling is essential.

2. Differentiate between lossless and lossy compression techniques.

The differences between lossless and lossy compression techniques:

Lossless Compression:

1. Definition: Lossless compression ensures that the original data can be perfectly
reconstructed from the compressed version without any loss of information.
2. Key Characteristics:
1. Preserves Data Integrity: No data is discarded during compression.
2. Exact Reconstruction: The decompressed data is identical to the
original.
3. Common Use Cases:
 1. Text files (e.g., documents, source code).
2. Archiving and backup purposes.
3. Scientific data (where precision matters).
4. Examples of Lossless Formats:

1. PNG (Portable Network Graphics): Used for images with

transparency support.
2. GIF (Graphics Interchange Format): Suitable for simple
animations and low-color images.
3. ZIP (compressed archive): Used for file compression.

Lossy Compression:

3. Definition: Lossy compression sacrifices some data to achieve higher

compression ratios. It intentionally discards information that is less perceptible to
the human eye.
4. Key Characteristics:
1. Irreversible: Decompressed data is not identical to the original.
2. Quality Trade-off: Image quality is reduced to achieve smaller file
sizes.
3. Common Use Cases:

1. Multimedia content (images, audio, video).

2. Streaming services (where bandwidth matters).
3. Web graphics and photos.

4. Examples of Lossy Formats:

1. JPEG (Joint Photographic Experts Group): Commonly used

for photographs and web images. It employs quantization and
chroma subsampling.
2. MP3 (MPEG Audio Layer III): For audio compression.
3. H.264 (Advanced Video Coding): Widely used for video
compression.

Compression Ratios:

5. Lossless: Achieves moderate compression ratios (typically 2:1 or 3:1).

6. Lossy: Offers higher compression ratios (e.g., 10:1 or more).

Trade-offs:

7. Lossless:

1. Pros:

1. Exact data reconstruction.

2. Suitable for critical data.
3. No visible artifacts.

2. Cons:
 1. Smaller compression gains.
2. Not ideal for multimedia content.

8. Lossy:
1. Pros:

1. High compression efficiency.

2. Acceptable quality for most applications.
3. Smaller file sizes.

2. Cons:

1. Irreversible loss of data.

2. Visible artifacts (e.g., blockiness, blurring).
3. Unsuitable for critical data.

Choosing the Right Technique:

9. Select Lossless:
1. When data integrity is paramount.
2. For text, databases, and scientific data.
10. Select Lossy:

1. When file size reduction is crucial.

2. For multimedia content where minor quality loss is acceptable.

In summary, lossless compression guarantees data fidelity but offers modest

compression gains, while lossy compression achieves higher compression ratios at
the cost of some quality degradation. The choice depends on the specific use case and
the balance between file size and quality.

3. Explain the concept of redundancy in image data.

In the context of digital images, redundancy refers to unnecessary or repetitive

information within the image. Let’s explore this concept further:

Definition:

1. Redundancy in digital images involves storing extra information that doesn’t

significantly contribute to the image’s meaning or quality.
2. It arises due to correlations, repetitions, or patterns present in the pixel data.

Types of Redundancy:

1. Spatial Redundancy:

1. Correlation between neighboring pixel values.

2. Adjacent pixels often exhibit similar intensity or color.
3. Example: Smooth gradients or uniform regions.
 2. Spectral Redundancy:
1. Correlation between different color planes (channels) or spectral bands.
2. RGB images have three color channels (red, green, blue) that often share
redundant information.
3. Example: A grayscale image where all three channels have identical
values.
3. Temporal Redundancy:

1. Correlation between adjacent frames in a sequence of images (e.g., video

frames).
2. Temporal redundancy exists when consecutive frames are similar.
3. Example: Video compression exploits this redundancy.

Exploiting Redundancy for Compression:

4. Data Compression aims to reduce the amount of data needed to represent

information.
5. Image compression techniques exploit redundancies to achieve smaller file sizes:

1. Coding Redundancy: Redundancy due to inefficient coding schemes

(e.g., using more bits than necessary to represent pixel values).
2. Interpixel Redundancy: Correlations between neighboring pixels.
3. Psychovisual Redundancy: Leveraging human visual perception to
discard imperceptible details.

Image Compression Algorithms:

6. Lossless Compression: Removes coding redundancy without loss of information

(e.g., ZIP, PNG).
7. Lossy Compression: Exploits both coding and interpixel redundancies,
sacrificing some quality (e.g., JPEG).

Benefits of Redundancy Reduction:

1. Smaller File Sizes: Compressed images occupy less storage space.

2. Faster Transmission: Reduced data size speeds up image transfer over networks.
3. Efficient Storage: Redundancy reduction optimizes storage resources.

In summary, understanding and managing redundancy in image data play a crucial

role in achieving efficient image compression and storage.

4. How does Huffman coding achieve lossless compression?

Huffman coding is a powerful technique for achieving lossless compression. Let’s

explore how it accomplishes this:

Principle of Huffman Coding:

1. The Huffman Coding algorithm replaces each character (symbol) in a piece of

text with a unique binary code.
 2. The goal is to assign shorter codes to frequently occurring symbols and longer
codes to less common symbols.

Steps in Huffman Coding:

1. Frequency Analysis:

1. The algorithm starts by analyzing the frequency of each symbol (e.g.,

characters in a text document).
2. More frequent symbols receive shorter codes.

2. Building the Huffman Tree:

1. Create a binary tree where each leaf node represents a symbol.
2. Combine the two least frequent nodes into a new internal node with a
weight equal to the sum of their frequencies.
3. Repeat this process until all nodes are combined into a single root node.
4. The path from the root to each leaf node determines the binary code for
that symbol.
3. Assigning Binary Codes:

1. Traverse the Huffman tree to assign binary codes:

1. Moving left adds a 0 to the code.

2. Moving right adds a 1 to the code.

4. Encoding the Text:

1. Replace each symbol with its corresponding Huffman code.

2. The resulting binary sequence represents the compressed data.

Example:

5. Consider the following frequency distribution for characters in a

text:

A: 5
B: 3
C: 2
D: 1

6. Build the Huffman tree:

Root
/ \
11 8
/\ /\
A B C D

7. Assign binary codes:

A: 0
B: 10
 C: 110
D: 111

8. The original text “ABACD” compresses to “01001101111.”

Advantages of Huffman Coding:

9. Achieves optimal prefix-free codes (no code is a prefix of another).

10. Guarantees lossless reconstruction.
11. Efficient for variable-length encoding.

Limitations:

1. Huffman coding works best when symbol frequencies are known in advance (e.g.,
for text files).
2. It may not be ideal for streaming data or situations where frequencies change
dynamically.

In summary, Huffman coding achieves lossless compression by assigning shorter

codes to frequently occurring symbols, resulting in efficient data representation.

5. What is the role of Lempel-Ziv coding in image compression?

Lempel-Ziv coding, specifically the LZW (Lempel–Ziv–Welch) algorithm, plays a

crucial role in lossless image compression. Let’s explore how it achieves this:

What is Lempel-Ziv-Welch (LZW) Algorithm?

1. The LZW algorithm is a widely used compression technique.

2. It is typically employed in formats like GIF (for image compression) and
optionally in PDF and TIFF.
3. Unix’s ‘compress’ command also utilizes LZW.
4. Lossless: No data is lost during compression.
5. Known for its simplicity and versatility.
6. Often used to “double the capacity of your hard drive.”

How Does LZW Work?

1. LZW compression operates as follows:

1. Reads a sequence of symbols (e.g., characters in a text or pixel values in

an image).
2. Groups symbols into strings.
3. Converts these strings into codes.
4. Because codes take up less space than the original strings, compression
is achieved.

2. Key features of LZW:

1. Uses a code table (commonly with 4096 entries).
2. Codes 0-255 represent single bytes from the input file.
 3. Codes 256-4095 represent sequences of bytes.
4. Identifies repeated sequences and adds them to the code table during
encoding.
5. Decoding involves translating codes back to characters.

Advantages of LZW:

1. Efficient Space Saving: LZW identifies recurring patterns (redundancy) to save

data space.
2. High Throughput: LZW can achieve very high throughput in hardware
implementations.
3. General-Purpose: Widely used for various data types.

Use Cases:

1. GIF Images: LZW is the basis for GIF image compression.

2. Text Files: Suitable for compressing text documents.
3. File Compression Utilities: Used by Unix’s compress command.

In summary, Lempel-Ziv coding (specifically LZW) efficiently reduces file sizes

without compromising data integrity, making it a valuable tool in lossless image
compression.

6. Name some other lossless coding techniques apart from Huffman and Lempel-
Ziv.

Apart from Huffman coding and Lempel-Ziv coding, there are several other lossless
compression techniques used in various applications:

Run-Length Encoding (RLE):

1. A simple method that replaces repeated consecutive symbols with a count and
the symbol itself.
2. Commonly used for compressing bitmap images (e.g., black-and-white images).

Shannon-Fano Elias Encoding:

1. Divides the symbol set into subsets based on probabilities.

2. Assigns shorter codes to more probable symbols.
3. Less widely used than Huffman coding.

Arithmetic Coding:

1. Represents entire sequences of symbols as fractional values in a specified range.

2. Achieves better compression ratios than Huffman coding.
3. Used in some image and video compression formats.

Adaptive Coding:

1. Adjusts the codebook dynamically based on the input data.

 2. Examples include Adaptive Huffman coding and Adaptive Arithmetic coding.
3. Suitable for streaming data or situations with changing probabilities.

Burrows-Wheeler Transform (BWT):

1. Rearranges the input data to improve redundancy.

2. Often used as a preprocessing step before applying other compression methods
(e.g., in the bzip2 algorithm).

Delta Encoding:

1. Stores the difference between consecutive symbols.

2. Useful for compressing sorted or gradually changing data.

Remember that each technique has its strengths and weaknesses, and the choice
depends on the specific use case and the trade-offs between compression efficiency
and computational complexity.

7. Which compression method is commonly used in GIF images?

GIF (Graphics Interchange Format) images commonly use the Lempel-Ziv-Welch

(LZW) compression method. LZW is a lossless compression algorithm that achieves
efficient data reduction without sacrificing image quality. Here’s how it works:

LZW Compression in GIF Images:

1. LZW is the core compression technique used in GIF files.

2. It reads sequences of symbols (such as pixel values in an image), groups these
symbols into strings, and converts the strings into codes.
3. These codes take up less space than the original strings, resulting in a smaller file
size.
4. LZW identifies recurring patterns (redundancy) within the image data.

Advantages of LZW in GIF:

1. Lossless: LZW ensures that the original image can be perfectly reconstructed
from the compressed version.
2. Efficient: It achieves significant compression ratios while preserving image
fidelity.
3. Widely Supported: GIF format with LZW compression is widely supported
across browsers and platforms.

GIF Format Details:

1. GIF images use a variant of LZW to compress graphical data.

2. The original version of GIF is known as GIF87a.
3. GIF scans the image row by row and discovers pixel correlations within rows
(not between rows).
4. It uses a growing and dynamic dictionary for compressing data.
 Limitations:

1. While LZW is effective for GIF images, it has limitations:

1. One-Dimensional: GIF compression is one-dimensional, whereas

images are two-dimensional. This inefficiency affects its overall
performance.
2. Dated Algorithm: LZW is an older compression method compared to
modern algorithms used in other formats.

In summary, LZW compression is the backbone of GIF images, allowing efficient

storage and transmission of graphical data while maintaining data integrity.

8. Why is lossy compression suitable for multimedia applications?

Lossy compression is particularly well-suited for multimedia applications due to

several key reasons:

Trade-off Between Quality and File Size:

1. Multimedia content (such as images, audio, and video) often contains large
amounts of data.
2. Lossy compression allows creators to strike a balance between file size
reduction and acceptable quality.
3. By sacrificing some quality imperceptible to human senses, multimedia files can
be significantly compressed.

Human Perception Tolerance:

1. Our senses (vision, hearing) have limited sensitivity to certain changes.

2. Lossy compression exploits this by removing details that humans won’t notice.
3. For example, slight color variations or high-frequency audio components can be
discarded without affecting perceived quality.

Efficient Streaming and Transmission:

1. Multimedia files are frequently transmitted over networks (e.g., streaming

services, video calls).
2. Smaller file sizes lead to faster transmission and reduced bandwidth usage.
3. Lossy compression ensures efficient data transfer without compromising user
experience.

Storage Constraints:

1. Multimedia files consume significant storage space.

2. Lossy compression allows creators to store more content within limited storage
resources.
3. Examples: Storing thousands of songs on a mobile device or hosting video
libraries on servers.

Formats and Standards:

 1. Many multimedia formats (e.g., JPEG for images, MP3 for audio, H.264 for
video) employ lossy compression.
2. These formats are widely supported across devices, browsers, and platforms.

Applications:

1. Images: Lossy compression reduces image file sizes for web pages, galleries,
and social media.
2. Audio: MP3, AAC, and other lossy audio formats enable efficient music
streaming.
3. Video: Lossy video codecs (e.g., H.264, VP9) deliver high-quality video content
with manageable file sizes.

Creative Control and Aesthetics:

1. Creators intentionally apply lossy compression to achieve specific artistic effects.

2. For example, adding noise or intentionally degrading an image for a vintage look.

Examples of Lossy Compression in Multimedia:

1. JPEG: Commonly used for photographs and web images.

2. MP3: Widely used for audio compression.
3. H.264: Standard for video compression (used in streaming services, video calls,
and more).

In summary, lossy compression strikes a balance between quality and efficiency,

making it essential for multimedia applications where storage, transmission, and
perceptual quality matter.

9. Describe the Discrete Cosine Transform (DCT) and its role in image
compression.

the Discrete Cosine Transform (DCT) and its significance in image compression:

What is the Discrete Cosine Transform (DCT)?

1. The DCT is a mathematical technique that converts an image (or any signal)
from its spatial domain (pixel values) into a frequency domain.
2. It represents an image as a sum of sinusoidal functions (cosines) of varying
magnitudes and frequencies.
3. Unlike the Discrete Fourier Transform (DFT), which uses complex
exponentials, the DCT employs only real-valued cosine functions.

Role of DCT in Image Compression:

1. The DCT plays a crucial role in lossy image compression. Here’s how:

1. Frequency Separation: DCT separates an image into different

frequency components.
 2. Energy Concentration: Most of the visually significant information in
an image is concentrated in just a few DCT coefficients.
3. Quantization: During compression, less important DCT coefficients are
discarded (quantized).
4. JPEG Standard: The DCT is at the heart of the widely used JPEG
(Joint Photographic Experts Group) image compression algorithm.

DCT Properties:

1. Orthogonality: The DCT basis functions are orthogonal, which simplifies the
transformation.
2. Invertibility: The DCT is invertible, allowing perfect reconstruction of the
original image from its DCT coefficients.

DCT Basis Functions:

1. The DCT represents an image as a sum of basis functions (cosines).

2. The 64 basis functions for an 8-by-8 matrix are illustrated in the image
below: !64 Basis Functions of an 8-by-8 Matrix
3. The constant-valued basis function at the upper left corner is called the DC basis
function, and its corresponding DCT coefficient is the DC coefficient.

Computing the DCT:

1. Two common methods:

1. dct2 Function: Uses an FFT-based algorithm for speedy computation

with large inputs.
2. DCT Transform Matrix: Returned by the dctmtx function and is more
efficient for small square inputs (e.g., 8-by-8 or 16-by-16).

Applications:

1. JPEG Compression: The JPEG standard employs the DCT for lossy image
compression.
2. Video Compression: DCT is used in video codecs (e.g., H.264) to compress
video frames.
3. Audio Compression: Some audio formats (e.g., MP3) use DCT for efficient
audio storage.

In summary, the DCT is a fundamental tool in image compression, allowing efficient

representation of visual content while maintaining acceptable quality.

10. What is the Bitplane Coding (BTC) technique?

Bitplane Coding (BTC) is a lossy image compression technique that operates on

individual bitplanes of an image. Let’s explore its key features and how it works:

Bitplane Coding Overview:

1. BTC focuses on compressing each bitplane (a binary representation of a single

bit position) of an image independently.
 2. It achieves compression by quantizing the pixel values within each bitplane.

How BTC Works:

1. For each bitplane, BTC performs the following steps:

1. Quantization:
1. Divide the pixel values into quantization intervals.
2. Assign a representative value (usually the midpoint of the
interval) to all pixels within that interval.
2. Coding:

1. Encode each pixel using the quantized value.

2. The number of bits required to represent the quantized value
determines the compression achieved.

3. Decoding:

1. During decompression, reverse the quantization process to

reconstruct the original pixel values.

Advantages of BTC:

2. Simplicity: BTC is straightforward to implement.

3. Low Computational Complexity: It requires minimal computation during
encoding and decoding.
4. Bitplane Independence: BTC treats each bitplane separately, allowing parallel
processing.

Limitations:

1. Lossy: BTC introduces quantization errors, leading to some loss of image quality.
2. Bitplane Order: The order in which bitplanes are processed affects the final
result.

Applications:

1. BTC is commonly used in monochrome image compression.

2. It achieves moderate compression ratios with low computational overhead.

Example:

1. Suppose we have an 8-bit grayscale image (256 levels).

2. BTC processes each bitplane (from the most significant bit to the least significant
bit) independently.
3. Quantization reduces the number of levels (e.g., from 256 to 16).
4. The compressed image consists of quantized values for each pixel in each
bitplane.
In summary, Bitplane Coding (BTC) is a simple technique that quantizes pixel values
within individual bitplanes, achieving moderate compression while sacrificing some
image quality.

Lossless Techniques Questions:

11. How does Huffman coding work, and what is its main advantage?

Huffman coding is a lossless data compression algorithm that assigns variable-

length codes to input characters based on their frequencies. Let’s break down how it
works and explore its main advantage:

Algorithm Overview:

1. Frequency-Based Encoding: Huffman coding assigns shorter codes to

characters that appear more frequently in the input data.
2. Prefix Codes: The assigned codes are prefix codes, meaning no code assigned to
one character is the prefix of another character’s code.
3. Ambiguity-Free Decoding: This ensures that there is no ambiguity when
decoding the generated bitstream.

Steps to Construct Huffman Tree:

1. Create a leaf node for each unique character and build a min heap (priority
queue) of all leaf nodes.
2. Extract two nodes with the minimum frequency from the min heap.
3. Create a new internal node with a frequency equal to the sum of the two nodes’
frequencies.
4. Make the first extracted node its left child and the other extracted node its right
child.
5. Add this new internal node back to the min heap.
6. Repeat the above steps until the heap contains only one node. The remaining
node is the root of the Huffman tree.

Example: Let’s consider the following character frequencies:

Character Frequencies:

1. (a: 5)
2. (b: 9)
3. (c: 12)
4. (d: 13)
5. (e: 16)
6. (f: 45)

Constructing the Huffman Tree:

1. Start by creating leaf nodes for each character and build a min heap (priority
queue).
 2. Extract two nodes with the minimum frequency:

1. Combine nodes for (a) and (b) (total frequency = 14).

2. Create an internal node with frequency 14.

3. Repeat:
1. Combine nodes for (c) and the previously created internal node (total
frequency = 26).
2. Create a new internal node with frequency 26.
3. Combine nodes for (d) and the previous internal node (total frequency =
39).
4. Create another internal node with frequency 39.
5. Combine nodes for (e) and the previous internal node (total frequency =
55).
6. Create yet another internal node with frequency 55.
7. Finally, combine nodes for (f) and the last internal node (total frequency
= 100).
8. The root of the Huffman tree is now formed.

Huffman Tree: !Huffman Tree

Assigning Codes:

1. Traverse the Huffman tree:

1. Left edges represent 0, and right edges represent 1.
2. Assign codes to each character based on the path from the root to the
leaf:

1. (a: 000)
2. (b: 001)
3. (c: 01)
4. (d: 10)
5. (e: 11)
6. (f: 1)

Encoded Message:

1. If we encode the string “face,” it becomes: (1 , 000 , 01 , 11).

Advantage of Huffman Coding:

1. The main advantage is efficient compression:

1. Shorter codes for frequent characters lead to smaller encoded data.

2. The resulting bitstream has a higher compression ratio.

In summary, Huffman coding optimally represents data by assigning shorter codes to

common symbols, resulting in effective compression.
11. Explain Arithmetic coding is a common algorithm used in both
lossless and lossy data compression.
It's an entropy encoding technique, where symbols that are seen more frequently are
encoded with fewer bits than symbols that are seen less frequently.

Here's a more detailed explanation:

1. Entropy Encoding: The basic idea of entropy encoding is to assign shorter codes
to more frequently occurring symbols, and longer codes to less frequently occurring
symbols. This is based on the concept of information entropy, where the entropy of a
source symbol is directly proportional to the negative logarithm of the probability of
the symbol.

2. Arithmetic Coding: Unlike Huffman coding, which assigns a specific bit pattern to
each symbol, arithmetic coding represents the entire input sequence as a single
number between 0 and 1. The more frequently a symbol appears, the larger the
portion of the number line that is assigned to that symbol. When a symbol is encoded,
the current range is divided according to the probability distribution of the symbols,
and the range corresponding to the symbol is selected.

3. Coding Process: The coding process involves maintaining a current range (initially
[0,1)) and repeatedly narrowing this range down. When a symbol is to be encoded, the
range is divided into sub-ranges, each representing a symbol in the alphabet. The sub-
range corresponding to the symbol to be encoded becomes the new current range.

4. Decoding Process: Decoding is the reverse process. Given the number and the
same probability distribution, the decoder can reconstruct the original sequence of
symbols.

5. Advantages: Arithmetic coding has some advantages over other techniques such as
Huffman coding. It can represent messages at nearly their entropy rate and handle any
probability distribution given enough data. It's also more efficient when dealing with
symbols that have non-integral bit lengths.

Arithmetic coding is widely used in image and video compression algorithms such as
JBIG, JBIG2, JPEG2000, and H.264/AVC.

12. What is the Lempel-Ziv-Welch (LZW) algorithm, and where is it

commonly used?

The Lempel-Ziv-Welch (LZW) algorithm is a universal lossless data compression

algorithm created by Abraham Lempel, Jacob Ziv, and Terry Welch. It was published
by Welch in 1984 as an improved implementation of the LZ78 algorithm published by
Lempel and Ziv in 1978. The algorithm is simple to implement and has the potential
for very high throughput in hardware implementations.

LZW works by reading a sequence of symbols, grouping the symbols into strings, and
converting the strings into codes. Because the codes take up less space than the strings
they replace, we get compression. LZW compression uses a code table, with 4096 as a
common choice for the number of table entries. Codes 0-255 in the code table are
always assigned to represent single bytes from the input file. Compression is achieved
by using codes 256 through 4095 to represent sequences of bytes. As the encoding
continues, LZW identifies repeated sequences in the data and adds them to the code
table. Decoding is achieved by taking each code from the compressed file and
translating it through the code table to find what character or characters it represents.

LZW is widely used and supported across a variety of software applications and
operating systems, making it a popular choice for compression and decompression.
This algorithm is typically used in GIF and optionally in PDF and TIFF. It’s also used
in Unix’s ‘compress’ command, among other uses. It is the algorithm of the widely
used Unix file compression utility compress and is used in the GIF image format.
Despite these limitations, the LZW algorithm remains a popular choice for data
compression, and has been widely used in applications such as image and document
compression.

13. How does Run Length Encoding (RLE) achieve lossless

compression?
Run-Length Encoding (RLE) is a simple yet effective form of lossless data
compression. Here's how it works:

1. Basic Concept: The basic idea behind RLE is to represent consecutive identical
elements, called a "run" in a data stream, by a single value and its count rather than as
the original run. This is particularly useful when dealing with repetitive sequences, as
it significantly reduces the amount of space needed to store or transmit the data.

2. How it Works: RLE works by scanning a file for data patterns that appear more
than once. These patterns are then saved in a dictionary, and references are placed
within the compressed file wherever repetitive data occurs. For example, the string
`AAAAAABBBBBCCC` could be represented as `A6B5C3`.

3. Efficiency: RLE is most efficient on data that contains many such runs, for example,
simple graphic images such as icons, line drawings, and animations. For files that do
not have many runs, RLE could increase the file size.

4. Applications: RLE may also be used to refer to an early graphics file format
supported by CompuServe for compressing black and white images, but was widely
supplanted by their later Graphics Interchange Format (GIF). RLE also refers to a
little-used image format in Windows 3.x, with the extension rle, which is a run-length
encoded bitmap, used to compress the Windows 3.x startup screen.

In summary, RLE achieves lossless compression by replacing repeated occurrences of

data with just one data value and count. This method is particularly effective when the
data contains many such runs. However, it's worth noting that RLE is not suitable for
all types of data. For data where runs are less frequent, RLE might not provide
effective compression and could even increase the file size.
15. What is string-table compression, and how does it differ from
other techniques?
String-table compression is a lossless data compression technique that works by
removing duplicate entries and tail substrings from string tables. This can
significantly reduce the size of any string tables, resulting in smaller text segments
and reduced runtime paging activity.

String-table compression is a type of dictionary-based compression, similar to the

Lempel-Ziv-Welch (LZW) algorithm. These algorithms work by identifying repeated
sequences in the data and adding them to a code table. The codes take up less space
than the strings they replace, leading to compression.

However, string-table compression differs from other techniques in its specific focus
on string tables, which are commonly used in programming and data storage. It's
particularly effective when the data contains many repeated strings or substrings.

Other compression techniques may use different strategies. For example, Huffman
coding uses a variable-length prefix code, where frequently occurring characters have
shorter codes. Run Length Encoding (RLE) replaces sequences of the same data
values within a file.

In terms of lossless compression techniques, some such as zlib, gzip, and ZIP use the
Deflate method for compression and Inflate method for decompression. These
methods encode the data into compressed data.

In contrast, lossy compression techniques, such as Vector Quantisation, DCT

(Discrete Cosine Transform), and Transform Coding, reduce file size by removing
unnecessary or less important information.

Each compression technique has its own strengths and weaknesses, and the best one
to use depends on the specific requirements of the task at hand.

Lossy Techniques Questions:

16. What is the fundamental idea behind transform coding?

The fundamental idea behind transform coding is to represent the data in a different
form that allows for more efficient compression. This is achieved by applying a
mathematical transformation to the data, converting it from the spatial or time domain
to a different domain, such as the frequency domain.

In the new domain, the data's characteristics, such as correlation between elements or
energy distribution, can be exploited to achieve better compression. For example, in
an image, neighboring pixels are often similar. By transforming the image into the
frequency domain using a method like the Discrete Cosine Transform (DCT), this
correlation can be captured more compactly.

After transformation, the transformed data is quantized, which introduces some loss
of information but significantly reduces the data size. The quantized data is then
entropy coded, typically using a method like Huffman coding or arithmetic coding, to
further compress the data.

Transform coding is widely used in various data compression applications, including

JPEG image compression, MP3 audio compression, and MPEG video compression.
These all use variants of transform coding to achieve efficient compression of
multimedia data.

It's important to note that while transform coding can significantly reduce data size, it
is typically a lossy process. That is, some information is lost during compression, and
the original data cannot be perfectly reconstructed from the compressed data.
However, the loss is often imperceptible to human senses, making transform coding a
powerful tool for multimedia data compression.

17. How does Transform Coding reduce the data size in lossy
compression?
Transform coding is a type of data compression for "natural" data like audio signals or
photographic images. The fundamental idea behind transform coding is to represent
the data in a different form that allows for more efficient compression.

The transformation is typically lossless (perfectly reversible) on its own but is used to
enable better (more targeted) quantization. Quantization is a process that reduces the
precision of the transformed data, which then results in a lower quality copy of the
original input (lossy compression).

In transform coding, knowledge of the application is used to choose information to

discard, thereby lowering its bandwidth. The remaining information can then be
compressed via a variety of methods. When the output is decoded, the result may not
be identical to the original input, but is expected to be close enough for the purpose of
the application.

For example, in an image, neighboring pixels are often similar. By transforming the
image into the frequency domain using a method like the Discrete Cosine Transform
(DCT), this correlation can be captured more compactly. After transformation, the
transformed data is quantized, which introduces some loss of information but
significantly reduces the data size.

So, in essence, transform coding reduces data size in lossy compression by

transforming the data into a domain where it can be represented more compactly, and
then discarding less important information in that domain.

18. Describe the role of K-L Transforms in image compression.

The Karhunen-Loève Transform (KLT), also known as the Hotelling transform or the
Eigen Vector transform, plays a significant role in image compression. Here's how:
1. Optimal Dimensionality Reduction: KLT is an optimal dimensionality reduction
mapping technique and is based on finding the best orthonormal basis. The goal of
this technique is to find the subspace where most of the data lies.

2. Covariance Matrix and Transformation Matrix: Given the covariance matrix

Cx, the KLT transformation matrix A is defined such that after transformation of each
vector via y = A(x - xm), the covariance matrix of the vectors y, which we denote Cy,
is diagonal. This means that each pixel of the output vector set is uncorrelated with
every other pixel¹. It can be shown that if we choose the rows of A to be the
eigenvectors of Cx, then Cy is diagonal. Hence this choice of transformation matrix
defines the Hotelling transform.

3. Geometrical Interpretation: From its definition, the transformation matrix A

corresponds to a rotation of the coordinate system. A given input vector x is
transformed to an output vector y via y = A(x - xm). For a set of 3 pixel images as in
earlier example, allocate each image in the set a point in 3D space, now find a rotated
coordinate system so that the new y(1) -axis is along the direction of maximum
variance, new y(2) -axis along an orthogonal direction with next highest variance etc.
New y(1), y(2), y(3) axes define basis vectors of KLT.

4. Optimum Compression: It can be shown theoretically that the 1D transform using

the KLT matrix A, is optimum in packing as much information (largest coefficients)
as possible into as few components as possible.

In summary, KLT is significant in image compression as it helps in transforming the

image to an optimal orthonormal basis, making the covariance matrix diagonal,
rotating the coordinate system, and enabling efficient compression.

19. What is the significance of Discrete Cosine Transforms (DCT) in

JPEG compression?
The Discrete Cosine Transform (DCT) plays a crucial role in JPEG compression.
Here's why:

1. Transformation to Frequency Domain: DCT is used to transform an image from

the spatial domain to the frequency domain. The idea behind DCT is that any function
can be represented by the summation of cosine functions.

2. Energy Compaction: DCT transformation is used due to its energy compaction

characteristics. DCT has cosine function which is easier to compute and the number
of coefficients become less⁵. Thus, DCT can result in more accurate image
reconstruction even if the JPEG is a lossy transformation.

3. Separation of Significant and Insignificant Information: As a more effective

alternative, the DCT can manipulate this data, separating information crucial to the
definition of the image from information that’s presence is not perceivable by the
human eye. The insignificant information can then be "discarded" through the
quantization phase of JPEG coding, thus achieving large-scale compression.
4. Efficient Compression: The DCT decomposes an image into a set of sinusoidal
waveforms with varying magnitudes and frequencies. The usefulness is such that it
allows one to selectively drop frequency components that are imperceptible to the
human eye. Thereby, reducing the size of the final image.

In summary, DCT is significant in JPEG compression as it helps in transforming the

image to the frequency domain, compacting the energy, separating significant and
insignificant information, and enabling efficient compression.

20. Explain the concept of quantization in lossy compression.

Quantization is a fundamental part of lossy compression. It's a process that maps input
from a large set (like an analog signal) to numerical output values in a smaller
(usually finite) set. Here's how it works:

1. Compression: Quantization is a lossy compression technique achieved by

compressing a range of values to a single quantum (discrete) value. When the number
of discrete symbols in a given stream is reduced, the stream becomes more
compressible.

2. Color Quantization: In image processing, color quantization reduces the number

of colors used in an image¹. This is important for displaying images on devices that
support a limited number of colors and for efficiently compressing certain kinds of
images.

3. Frequency Quantization: The human eye is fairly good at seeing small differences
in brightness over a relatively large area, but not so good at distinguishing the exact
strength of a high frequency (rapidly varying) brightness variation. This fact allows
one to reduce the amount of information required by ignoring the high frequency
components. This is done by simply dividing each component in the frequency
domain by a constant for that component, and then rounding to the nearest integer.
This is the main lossy operation in the whole process.

4. Quantization Matrices: A typical video codec works by breaking the picture into
discrete blocks (8×8 pixels in the case of MPEG). These blocks can then be subjected
to discrete cosine transform (DCT) to calculate the frequency components, both
horizontally and vertically. The resulting block (the same size as the original block) is
then pre-multiplied by the quantization scale code and divided element-wise by the
quantization matrix, and rounding each resultant element. The quantization matrix is
designed to provide more resolution to more perceivable frequency components over
less perceivable components (usually lower frequencies over high frequencies) in
addition to transforming as many components to 0, which can be encoded with
greatest efficiency.

In summary, quantization in lossy compression is a process that reduces the number

of distinct values to a much smaller set, enabling efficient compression. It's
particularly useful in image and video compression, where it helps to reduce the file
size while maintaining acceptable quality.
21. How does BTC (Block Truncation Coding) work?
Block Truncation Coding (BTC) is a type of lossy image compression technique for
grayscale images. Here's how it works:

1. Image Division: BTC divides the original images into blocks. Typically, the image
is divided into small sub-blocks of size 4x4 pixels.

2. Quantization: For each block, BTC uses a quantizer to reduce the number of gray
levels within each block while maintaining the same mean and standard deviation.

3. Compression: The compression is achieved by a two-level quantization on the

block. If a pixel value is greater than the mean, it is assigned the value "1", otherwise
"0". This 16-bit block is stored or transmitted along with the values of Mean and
Standard Deviation.

4. Reconstruction: Reconstruction is made with two values "a" and "b" which
preserve the mean and the standard deviation¹. To reconstruct the image, or create its
approximation, elements assigned a 0 are replaced with the "a" value and elements
assigned a 1 are replaced with the "b" value.

In summary, BTC works by dividing the image into blocks, reducing the number of
gray levels in each block, compressing the blocks, and then reconstructing the image
from the compressed blocks.

Enhancement Techniques Questions:

22. What is spatial domain enhancement, and how does it improve

image quality?
Spatial domain enhancement is a technique used in image processing to improve the
quality and visual appeal of digital images. Here's how it works:

1. Direct Manipulation of Pixels: Spatial domain methods are procedures that

operate directly on the pixels in an image. The term "spatial domain" refers to the
image plane itself, and approaches in this category are based on direct manipulation of
pixels in an image.

2. Spatial Filters and Gray Level Transformations: By manipulating pixel values,

applying spatial filters, and leveraging gray level transformations, we can highlight
important details, remove noise, and enhance the overall aesthetics of an image.

3. Improvement of Image Appearance: By the term image enhancement, we mean

improvement of the appearance of an image (in all sense including human perception
and machine perception) by increasing the dominance of some features, or by
decreasing the ambiguity between different regions of the image. In most cases, the
enhancement of certain features is achieved at the cost of suppressing few other
features.

4. Applications: Image enhancement using the spatial domain is a powerful technique

that allows us to improve the quality and visual appeal of digital images. It's a
preprocessing step, through which an original image is made suitable for a specific
application.

In summary, spatial domain enhancement improves image quality by directly

manipulating pixel values, applying spatial filters, leveraging gray level
transformations, and enhancing the overall aesthetics of an image.

23. Explain the process of histogram equalization.

Histogram equalization is a method in image processing that adjusts the contrast of an
image by modifying the intensity distribution of the histogram. Here's how it works:

1. Histogram Calculation: The first step in histogram equalization is to calculate the

histogram of the image. The histogram of an image gives the frequency of occurrence
of each intensity level in the image.

2. Cumulative Distribution Function (CDF): The next step is to calculate the

cumulative distribution function (CDF) of the histogram. The CDF gives the
cumulative probability of each intensity level in the image.

3. Transformation Function: The transformation function is then applied to each

pixel in the image. This function maps the original intensity levels in the image to
new intensity levels.

4. Equalization: The final step is the actual equalization process. The goal of this step
is to create a uniform distribution of pixel intensities in the image. This is achieved by
spreading out the most frequent intensity values, i.e., stretching out the peaks of the
histogram.

The result of histogram equalization is an image with an approximately linear

cumulative distribution function, which tends to enhance the contrast of the image. It's
widely used in various fields such as to enhance medical images, satellite images,
scanned documents, and more.

24. How can directional smoothing enhance image features?

Directional smoothing is a technique used in image processing that can enhance
image features. Here's how it works:

1. Adaptive Control: The smoothing has to be adaptively controlled with two

principles:
- Control of the amount of smoothing, i.e., less smoothing in the locations with
strong image features, and more smoothing in the locations with weak image features.
 - Control of the direction of smoothing, i.e., minimal smoothing in the directions
across the image features, and maximal smoothing in the directions along the image
features.

2. Preserving Edges: The new filter structure is able to direct a filtering operation to
act over the complete image. By directing the smoothing operation away from edges,
the filter reduces noise while sharpening edges.

3. Enhancing Fault Features: It consists of two phases: the Gaussian operator

smoothen high frequency data that would otherwise be exacerbated by the Laplacian,
while the latter sharpens the edges. A directional Laplacian of a Gaussian operator is
used to enhance the image of fault features within dissimilarity data.

In summary, directional smoothing enhances image features by adaptively controlling

the amount and direction of smoothing, preserving edges, and enhancing fault features.

25. What is the purpose of median filtering in image enhancement?

Median filtering is a non-linear method used in image processing to reduce "salt and
pepper" noise. Here's how it works:

1. Noise Reduction: The primary purpose of median filtering is noise reduction. It is

particularly effective at removing 'salt and pepper' noise.

2. Preserving Edges: Unlike linear filtering, median filtering preserves edges, as the
median is less sensitive to extreme values (outliers) compared to the mean.

3. Process: The median filter works by moving through the image pixel by pixel,
replacing each value with the median value of neighboring pixels. The pattern of
neighbors is called the "window", which slides, pixel by pixel over the entire image.

4. Application: Median filtering is widely used in image processing because, under

certain conditions, it preserves edges while removing noise. It's also used in digital
signal processing to remove noise from audio signals.

In summary, the purpose of median filtering in image enhancement is to reduce noise,

particularly 'salt and pepper' noise, while preserving the sharpness of edges.

26. Describe the geometric mean filter and its application.

The Geometric Mean Filter is a type of image filtering process that is used to smooth
and reduce the noise of an image. It is based on the mathematical geometric mean.
Here's how it works:

1. Process: The output image G(x,y) of a geometric mean filter is given by the
product of the pixels within the geometric mean mask raised to the power of 1/mn.
For example, using a mask size of 3 by 3, pixel (x,y) in the output image will be the
product of S(x,y) and all 8 of its surrounding pixels raised to the 1/9th power.

2. Application: The geometric mean filter is most widely used to filter out Gaussian
noise. In general, it will help smooth the image with less data loss than an arithmetic
mean filter. It can be applied to various fields such as real-time animation, virtual
reality applications, 3D applications, and more.

3. Advantages: The geometric mean filter can effectively remove noises that cause a
jerky motion and it can guarantee the most natural motions among various spatial
filters. This method could be applied to the various fields such as real-time animation,
virtual reality applications, 3D applications, and more.

In summary, the geometric mean filter is a type of image filtering process that is used
to smooth and reduce the noise of an image. It is particularly effective in applications
where preserving the original signal's waveform is crucial.

27. How does harmonic mean filtering affect image details?

Harmonic Mean Filtering is a type of image filtering process that is used to reduce
noise and enhance image details. Here's how it works:

1. Process: The Harmonic Mean Filter works by replacing each pixel value in an
image with the harmonic mean of the pixel values in its neighborhood. The
neighborhood is defined by a kernel, which is a small matrix that is placed over each
pixel in the image.

2. Noise Reduction: The primary purpose of the Harmonic Mean Filter is to reduce
noise. It is particularly effective at removing 'salt' noise, similar to salt and pepper
noise also known as impulse noise, without probability of impulses of lower
intensities².

3. Preserving Image Details: Unlike some other filters, the Harmonic Mean Filter is
better at preserving edge features than the arithmetic mean filter⁴. This is because the
harmonic mean is less sensitive to extreme values (outliers) compared to the
arithmetic mean.

4. Application: The Harmonic Mean Filter is used to process image data in the spatial
domain. Therefore, like with most spatial filters, it uses a kernel and convolution.
With mean filters in general, we essentially blur the image to deal with noise
corruption.

In summary, Harmonic Mean Filtering affects image details by reducing noise,

particularly 'salt' noise, while preserving the sharpness of edges.

28. What is homomorphic filtering, and when is it used?

Homomorphic filtering is a generalized technique for signal and image processing. It
involves a nonlinear mapping to a different domain in which linear filter techniques
are applied, followed by mapping back to the original domain. Here's how it works:

1. Nonlinear Mapping: Homomorphic filtering uses nonlinearities (mainly the

logarithm) to transform convolved or nonlinearly related signals to additive signals.

2. Linear Filtering: Once the signals are transformed into additive signals, they are
processed by linear filters.

3. Inverse Nonlinearity: The output of the linear filter is transformed afterwards by

the inverse nonlinearity.

4. Applications: Homomorphic filtering is sometimes used for image enhancement. It

simultaneously normalizes the brightness across an image and increases contrast. It is
also used to remove multiplicative noise. Homomorphic filtering is used in the log-
spectral domain to separate filter effects from excitation effects, for example in the
computation of the cepstrum as a sound representation. Enhancements in the log
spectral domain can improve sound intelligibility, for example in hearing aids.

In summary, homomorphic filtering is used in both signal and image processing to

apply linear filter techniques in a different domain and then map the results back to
the original domain. It is particularly useful for image enhancement and noise
reduction.

Numerical Examples:
1. Huffman Coding (Lossless):
Suppose we have the following pixel intensity probabilities:
- Intensity 0: 0.2
- Intensity 1: 0.3
- Intensity 2: 0.1
- Intensity 3: 0.4
Calculate the Huffman codes for each intensity.

Tutorial: Image Compression using Huffman Coding - GeeksforGeeks

2. LZW Compression (Lossless):

Given the input string: "ABABABAABABA"
Apply LZW compression to obtain the encoded sequence.

Tutorial: LZW (Lempel–Ziv–Welch) Compression technique - GeeksforGeeks

3. Discrete Cosine Transform (DCT) (Lossy):

Consider an 8x8 block of pixel values:

[[ 177 180 193 146 160 157 135 184]

[152 130 137 199 155 191 186 188]
[166 169 139 175 148 144 131 128]
[197 189 124 141 170 196 198 158]
[121 126 183 127 102 115 103 193]
[195 105 194 106 101 112 104 117]
[109 108 113 110 111 114 107 122]
[120 125 130 135 140 145 150 155]]

Compute the DCT coefficients for this block.

Tutorial: CSE 126 Multimedia Systems (ucsd.edu)

4. Histogram Equalization (Enhancement):

Given an image histogram, perform histogram equalization to enhance the contrast.

Intensity Value Frequency

0 1

1 6

2 3

3 2

4 3

5 2

6 1

7 2

Tutorial: How to Solve Histogram Equalization Numerical Problem in MATLAB? -

GeeksforGeeks

5. Median Filtering (Enhancement):

Apply a 3x3 median filter to the following grayscale pixel values:

Filter:
[[ 120 125 130]
[140 135 150]
[155 145 140]]
Grayscale:

6. Concept of Image Compression:

 Numerical 1: Consider an image of size 1024x1024 pixels. Each pixel is

represented using 8 bits. Calculate the size of the image in bytes and
kilobytes.

To solve this problem, we need to understand how digital images are stored and represented
using bits and bytes.

Given information:

- The image size is 1024 x 1024 pixels.

- Each pixel is represented using 8 bits.

Step 1: Calculate the total number of bits required to store the image.

Total number of bits = Number of pixels × Bits per pixel

Total number of bits = (1024 × 1024) × 8

Total number of bits = 8,388,608 bits

Step 2: Convert the total number of bits to bytes.

1 byte = 8 bits

Number of bytes = Total number of bits / 8

Number of bytes = 8,388,608 / 8

Number of bytes = 1,048,576 bytes

Step 3: Convert the number of bytes to kilobytes.

1 kilobyte (KB) = 1024 bytes

 Number of kilobytes = Number of bytes / 1024

Number of kilobytes = 1,048,576 / 1024

Number of kilobytes = 1024 kilobytes

Therefore, the size of the 1024 x 1024 pixel image, where each pixel is represented using 8
bits, is 1,048,576 bytes or 1024 kilobytes.

 Numerical 2: If we use a lossless compression technique and achieve a

compression ratio of 2:1 on the image from Numerical 1, what will be the
size of the compressed image in kilobytes?

If the original image size is 1 MB (1024 KB) and the compression ratio is 2:1, then the size of the
compressed image will be half of the original size.

So, the size of the compressed image will be:

Therefore, the size of the compressed image will be 512 KB.

7. Lossless Techniques (Huffman Coding, Arithmetic and Lempel-Ziv Coding,

Other Coding Techniques):

 Numerical 1: Given a set of symbols {A, B, C, D} with corresponding

probabilities {0.1, 0.2, 0.3, 0.4}, construct a Huffman tree and find the
Huffman code for each symbol.

let's construct the Huffman tree for the given symbols and their probabilities.

The first step in constructing a Huffman tree is to create a node for each symbol and its probability.
Then, we follow these steps:

1. Select the two nodes with the smallest probabilities.

2. Create a new node that has these two nodes as children. The new node's probability is the sum
of the probabilities of the two child nodes.

3. Remove the two original nodes from consideration and replace them with the newly created
node.

4. Repeat steps 1-3 until there is only one node left. This node is the root of the Huffman tree.

Following these steps for the given symbols and probabilities, we get:

- Step 1: Select A (0.1) and B (0.2).

- Step 2: Create a new node with A and B as children and probability 0.1 + 0.2 = 0.3.

- Step 3: We now have nodes {AB (0.3), C (0.3), D (0.4)}.

- Step 4: Repeat steps 1-3. Select AB (0.3) and C (0.3).

- Step 5: Create a new node with AB and C as children and probability 0.3 + 0.3 = 0.6.

- Step 6: We now have nodes {ABC (0.6), D (0.4)}.

- Step 7: Repeat steps 1-3. Select ABC (0.6) and D (0.4).

- Step 8: Create a new node with ABC and D as children and probability 0.6 + 0.4 = 1.0.

- Step 9: We now have one node left, which is the root of the Huffman tree.

Now, we can assign Huffman codes to each symbol by traversing the Huffman tree. We assign a
'0' to the left branch of each node and a '1' to the right branch:

- A: 00

- B: 01

- C: 10

- D: 11

So, the Huffman codes for the symbols {A, B, C, D} are {00, 01, 10, 11} respectively.

Please note that the Huffman codes can vary based on the construction of the Huffman tree. The
tree can be constructed differently based on the order in which nodes with equal probabilities are
selected. However, the length of the Huffman codes (i.e., the number of bits) will remain the same.
This is because Huffman coding is a prefix code, which means it is uniquely decodable and the
length of the code is proportional to the negative logarithm of the probability. Therefore, it
minimizes the expected code length, making it an optimal method for data compression.

 Numerical 2: Consider a string “ABRACADABRA”. Apply the Lempel-

Ziv coding algorithm to this string and find the resulting code.

let's apply the Lempel-Ziv coding algorithm (specifically, the LZ78 variant) to the string
"ABRACADABRA". The LZ78 algorithm works by reading the input string from left to right and
outputting pairs of the form (i, c), where i is an index to the dictionary and c is a character. The
dictionary is built dynamically during the encoding process.

Here's how it works:

1. Initialize the dictionary with an empty string.

2. Read the input string from left to right. For each character, check if the current string is in the
dictionary.

3. If it is, append the next character to the current string and continue.

4. If it's not, output the pair (i, c), where i is the index of the current string without the last
character, and c is the last character. Then, add the current string to the dictionary.

Applying these steps to "ABRACADABRA", we get:

1. A is not in the dictionary. Output (0, A) and add A to the dictionary.

2. B is not in the dictionary. Output (0, B) and add B to the dictionary.

3. R is not in the dictionary. Output (0, R) and add R to the dictionary.

4. A is in the dictionary, but AC is not. Output (1, C) and add AC to the dictionary.

5. A is in the dictionary, but AD is not. Output (1, D) and add AD to the dictionary.

6. A is in the dictionary, but AB is not. Output (1, B) and add AB to the dictionary.

7. R is in the dictionary. Output (3, ) and add R to the dictionary.

8. A is in the dictionary. Output (1, ) and add A to the dictionary.

So, the resulting code for "ABRACADABRA" using the LZ78 algorithm is: (0, A), (0, B), (0, R),
(1, C), (1, D), (1, B), (3, ), (1, ).

Please note that the LZ78 algorithm is a lossless data compression algorithm, and the resulting
code can be used to perfectly reconstruct the original string. The efficiency of the algorithm
depends on the repetitiveness of the string: the more repetitive the string, the higher the
compression ratio.

8. Lossy Compression Techniques (Transform Coding & K-L Transforms,

Discrete Cosine Transforms, and BTC):

 Numerical 1: Given a 2x2 image block with pixel values {140, 144, 147,
140}, calculate the DCT coefficients for this block.

The Discrete Cosine Transform (DCT) for a 2x2 image block can be calculated using
the following formula:

where:

 (F(u, v)) is the DCT coefficient at position (u, v).

 (f(x, y)) is the pixel value at position (x, y).
 The sums are over x and y, which are the row and column indices of the pixels in the
block.

Given the 2x2 image block with pixel values {140, 144, 147, 140}, we can arrange
these values in a matrix as follows:
Now, we can calculate the DCT coefficients for each position (u, v) in the block:

By calculating these expressions, we can obtain the DCT coefficients for the given
2x2 image block. Please note that the cosine values can be calculated using a
scientific calculator or a programming language that supports trigonometric functions.

 Numerical 2: Consider a 2x2 image block with pixel values {100, 101, 99,
98}. Apply the Block Truncation Coding (BTC) method to this block and
find the resulting code.

Block Truncation Coding (BTC) is a type of lossy image compression technique for grayscale
images. Here's how you can apply BTC to a 2x2 image block:

1. Calculate the mean (m) of the pixel values: The mean of {100, 101, 99, 98} is (100 + 101 +
99 + 98) / 4 = 99.5.

2. Partition the block into two sets: One set contains the pixels greater than or equal to the mean,
and the other set contains the pixels less than the mean. In this case, the sets are {100, 101} and
{99, 98}.

3. Calculate the means of the two sets: The mean of {100, 101} is (100 + 101) / 2 = 100.5, and
the mean of {99, 98} is (99 + 98) / 2 = 98.5.

4. Quantize the pixel values: Replace the pixel values in the first set with the mean of the first set,
and replace the pixel values in the second set with the mean of the second set. This gives us a new
block: {100.5, 100.5, 98.5, 98.5}.

5. Generate the bitmap: Create a bitmap that indicates whether each pixel belongs to the first set
(1) or the second set (0). In this case, the bitmap is {1, 1, 0, 0}.

So, the resulting BTC code for the block is the combination of the two means (100.5 and 98.5) and
the bitmap (1, 1, 0, 0).

Please note that BTC is a lossy compression technique, which means that some information is lost
during the compression process. The compressed block is an approximation of the original block,
and the quality of the approximation depends on the distribution of pixel values in the block.

9. Enhancement in Spatial and Transform Domain, Histogram Equalization,

Directional Smoothing, Median, Geometric Mean, Harmonic Mean,
Homomorphic Filtering:
  Numerical 1: Given a 3x3 image block with pixel values {120, 125, 130,
115, 119, 122, 110, 112, 114}, calculate the median value for this block.

The median of a set of numbers is the middle number when the numbers are arranged in ascending
order. If the set has an even number of observations, the median is the average of the two middle
numbers.

Given the 3x3 image block with pixel values {120, 125, 130, 115, 119, 122, 110, 112, 114}, let's
first arrange these values in ascending order:

{110, 112, 114, 115, 119, 120, 122, 125, 130}

Since there are 9 values (an odd number), the median is the middle value, which is the 5th value in
the sorted list.

So, the median value for this block is 119.

 Numerical 2: Given an image histogram with pixel intensities {0, 1, 2, 3, 4}

and corresponding frequencies {1000, 2000, 4000, 2000, 1000}, perform
histogram equalization on this data and find the new pixel intensities.

Histogram equalization is a method in image processing of contrast adjustment using the image's
histogram. It aims to obtain a uniform distribution of intensities (also known as the normalized
histogram).

Given an image histogram with pixel intensities {0, 1, 2, 3, 4} and corresponding frequencies
{1000, 2000, 4000, 2000, 1000}, the cumulative distribution function (CDF) can be calculated as
follows:

1. Normalize the frequencies by dividing each by the total number of pixels. The total number of
pixels is 1000 + 2000 + 4000 + 2000 + 1000 = 10000. So, the normalized frequencies are {0.1, 0.2,
0.4, 0.2, 0.1}.

2. Calculate the cumulative sum of the normalized frequencies. This gives us the CDF: {0.1, 0.3,
0.7, 0.9, 1.0}.

The new pixel intensities can be found by multiplying the CDF values by the maximum pixel
intensity (which is 4 in this case) and rounding to the nearest integer:

- New intensity for 0: round(0.1 * 4) = 0

- New intensity for 1: round(0.3 * 4) = 1

- New intensity for 2: round(0.7 * 4) = 3

- New intensity for 3: round(0.9 * 4) = 4

- New intensity for 4: round(1.0 * 4) = 4

So, after histogram equalization, the new pixel intensities are {0, 1, 3, 4, 4}.
Please note that histogram equalization can result in intensities that are not uniformly distributed,
especially for small image blocks or histograms with few bins. However, it generally improves the
contrast of the image.