Department of Electrical Engineering
Faculty Member:____________________ Dated: ____________________
Course/Section:____________________ Semester: __________________
Digital Image processing
Lab#11: Huffman image encoding
Lab Report Quiz/viva
Name Reg. No 8 Marks 7 Marks
Syed Arsal Rahman 365914
Rayyan Athar Hussain 365691
Abdul Rafay 365944
Lab#11: Huffman image encoding
Objectives
The objective of this lab is to introduce students to Huffman encoding and decoding techniques,
with a focus on their application to image compression. Students will gain an understanding of
how Huffman coding efficiently represents data, particularly in the context of image storage and
transmission.
Lab Instructions
This lab activity comprises of following parts: Lab Exercises, and Post-Lab Viva/Quiz
session.
The lab report shall be uploaded on LMS.
Only those tasks that are completed during the allocated lab time will be credited to the
students. Students are however encouraged to practice on their own in spare time for
enhancing their skills.
Lab Report Instructions
All questions should be answered precisely to get maximum credit. Lab report must ensure following
items:
Lab objectives
Python codes
Results (graphs/tables) duly commented and discussed
Conclusion
Introduction to Huffman Coding:
Huffman coding, named after David A. Huffman who introduced it in 1952, is a
variable-length prefix coding algorithm used for lossless data compression. Unlike
fixed-length codes, such as ASCII, where each symbol is represented by the same
number of bits, Huffman coding assigns shorter codes to more frequent symbols and
longer codes to less frequent symbols. This adaptive approach allows for more
efficient compression, especially in scenarios where certain symbols occur more
frequently than others.
The Need for Compression in Image Data:
Images, consisting of a vast number of pixels, can be data-intensive. Transmitting or
storing these images in their raw form can be impractical due to the large amount of
data involved. Compression techniques, such as Huffman coding, become essential
for optimizing storage and reducing transmission times. Huffman coding is
particularly well-suited for images with varying pixel intensities, making it a
fundamental component of image compression algorithms.
Key Concepts of Huffman Coding:
Frequency Tables: Huffman coding begins with a frequency analysis of the symbols
in the data. For images, these symbols are often pixel values. The more frequently a
symbol occurs, the shorter the code assigned to it.
Huffman Tree Construction: The next step involves constructing a Huffman tree
based on the frequencies of the symbols. This binary tree structure is used to generate
the variable-length codes assigned to each symbol.
Prefix Codes: Huffman coding generates prefix codes, ensuring that no code is a
prefix of another. This property simplifies the decoding process, as a code can be
unambiguously determined without the need for delimiters.
Practical Applications:
Huffman coding is widely used in various applications, including image compression,
file compression, and network communication. Understanding how to apply Huffman
coding to images is crucial for students interested in data compression, signal
processing, and image analysis.
Task 1:
Implement a Python script to encode the gray image of your choice using the
Huffman encoding.
### TASK CODE STARTS HERE ###
import cv2
from queue import PriorityQueue
from collections import Counter
import numpy as np
class Node:
def __init__(self, freq, level=None, left=None, right=None):
self.freq = freq
self.left = left
self.right = right
self.level = level
def __lt__(self, other):
return self.freq < other.freq
img = cv2.imread('test.jpg', cv2.IMREAD_GRAYSCALE)
gray_level = Counter(img.flatten().tolist())
total = sum(gray_level.values())
pq = PriorityQueue()
for level, count in gray_level.items():
pq.put(Node(freq=count, level=level))
while pq.qsize() > 1:
left = pq.get()
right = pq.get()
node = Node(freq=(left.freq + right.freq),left=left,right=right)
pq.put(node)
root = pq.get()
huffman_map = {}
def traverse_tree(curr, code=''):
if curr.level != None:
huffman_map[curr.level] = [code,curr.freq/total]
if curr.left:
traverse_tree(curr.left, code + '0')
if curr.right:
traverse_tree(curr.right, code + '1')
traverse_tree(root)
#compressed image
img_compressed = np.array([[huffman_map[img[row][col]][0] for col in
range(img.shape[1])] for row in range(img.shape[0]) ])
print(img_compressed)
### TASK CODE ENDS HERE ###
### TASK SCREENSHOT STARTS HERE ###
### TASK SCREENSHOT ENDS HERE ###
### TASK Description
In this image we used Huffman encoding algorithm to encode a grayscale image
Task 2:
Implement a Python script to decode the previously encoded image and verify the
correctness of the decoding process.
### TASK CODE STARTS HERE ###
import cv2
from queue import PriorityQueue
from collections import Counter
import numpy as np
class Node:
def __init__(self, freq, level=None, left=None, right=None):
self.freq = freq
self.left = left
self.right = right
self.level = level
def __lt__(self, other):
return self.freq < other.freq
img = cv2.imread('test.jpg', cv2.IMREAD_GRAYSCALE)
gray_level = Counter(img.flatten().tolist())
total = sum(gray_level.values())
pq = PriorityQueue()
for level, count in gray_level.items():
pq.put(Node(freq=count, level=level))
while pq.qsize() > 1:
left = pq.get()
right = pq.get()
node = Node(freq=(left.freq + right.freq),left=left,right=right)
pq.put(node)
root = pq.get()
huffman_map = {}
deconding_dict = {}
def traverse_tree(curr, code=''):
if curr.level != None:
huffman_map[curr.level] = [code,curr.freq/total]
deconding_dict[code] = curr.level
if curr.left:
traverse_tree(curr.left, code + '0')
if curr.right:
traverse_tree(curr.right, code + '1')
traverse_tree(root)
#compressed image
img_compressed = np.array([[huffman_map[img[row][col]][0] for col in
range(img.shape[1])] for row in range(img.shape[0]) ])
print(img_compressed)
#decompressed image
img_decompressed = np.array([[deconding_dict[img_compressed[row][col]]
for col in range(img.shape[1])] for row in range(img.shape[0]) ])
img_decompressed = img_decompressed.astype(np.uint8)
cv2.imshow('decompressed', img_decompressed)
cv2.imshow('original', img)
cv2.waitKey(0)
cv2.destroyAllWindows()
### TASK CODE ENDS HERE ###
### TASK SCREENSHOT STARTS HERE ###
### TASK SCREENSHOT ENDS HERE ###
### TASK Description
The image encoded is retrieved back to its original format
Task 3:
Calculate the compression ratio achieved by Huffman coding on the image.
import cv2
from queue import PriorityQueue
from collections import Counter
import numpy as np
class Node:
def __init__(self, freq, level=None, left=None, right=None):
self.freq = freq
self.left = left
self.right = right
self.level = level
def __lt__(self, other):
return self.freq < other.freq
img = cv2.imread('test.jpg', cv2.IMREAD_GRAYSCALE)
gray_level = Counter(img.flatten().tolist())
total = sum(gray_level.values())
pq = PriorityQueue()
for level, count in gray_level.items():
pq.put(Node(freq=count, level=level))
while pq.qsize() > 1:
left = pq.get()
right = pq.get()
node = Node(freq=(left.freq + right.freq),left=left,right=right)
pq.put(node)
root = pq.get()
huffman_map = {}
deconding_dict = {}
def traverse_tree(curr, code=''):
if curr.level != None:
huffman_map[curr.level] = [code,curr.freq/total]
deconding_dict[code] = curr.level
if curr.left:
traverse_tree(curr.left, code + '0')
if curr.right:
traverse_tree(curr.right, code + '1')
traverse_tree(root)
#compressed image
img_compressed = np.array([[huffman_map[img[row][col]][0] for col in
range(img.shape[1])] for row in range(img.shape[0]) ])
print(img_compressed)
#decompressed image
img_decompressed = np.array([[deconding_dict[img_compressed[row][col]]
for col in range(img.shape[1])] for row in range(img.shape[0]) ])
img_decompressed = img_decompressed.astype(np.uint8)
lavg = sum([len(huffman_map[x][0])*huffman_map[x][1] for x in
huffman_map.keys()])
compression_ratio = 8/lavg
print('compression ratio: ', compression_ratio)
cv2.imshow('decompressed', img_decompressed)
cv2.imshow('original', img)
cv2.waitKey(0)
cv2.destroyAllWindows()
image is compressed by a ratio of 1.0868
