Insight into Huffman Coding Technique
Discover the intricacies of Huffman Coding, a popular lossless data compression method used in various compression standards like JPEG and MPEG. Learn about constructing Huffman trees, encoding images efficiently, and reducing redundancy in data. Check out step-by-step explanations with visual aids for a comprehensive understanding.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Huffman coding (Gonzalez et al. 2008, A.Wong Lecture 16b 2011) Popular lossless data compression technique Removes coding redundancy (or in context of image processing, redundant image data) Often used in compression standards: JPEG MPEG-1, 2, 4 Uses variable-length coding Encoding a source symbol using a table that considers the estimated occurrence probability of that symbol Resulting data size depends on underlying image characteristics
Steps 1.) Determine histogram of image 2.) Construct Huffman tree 3.) Encode the image using codes generated from the Huffman tree
1.) Histogram 8 7 7 3 3 3 6 Frequency 5 3 3 3 3 4 3 2 1 1 9 9 1 0 5 6 9 9 1 3 5 6 7 9 Intensity http://courses.cs.washington.edu/courses/cse373/02wi/slides/ImageADT/sld0 12.htm
2) Huffman tree Sorted from lowest to highest frequency Intensity 5 6 7 1 9 3 Frequency 1 1 1 2 4 7 Intensity 1 3 5 6 7 9 Frequency 2 7 1 1 1 4 10 Frequency 5 0 1 3 5 6 7 9 Intensity
Intensity 5 6 7 1 9 3 Frequency 1 1 1 2 4 7 2 1 1 5 6 Lower frequency becomes left child node Higher frequency becomes right child node Sum of the two children nodes becomes the parent node
3 Intensity 5 6 7 1 9 3 Frequency 1 1 1 2 4 7 1 2 7 1 1 5 6
5 Intensity 5 6 7 1 9 3 Frequency 1 1 1 2 4 7 3 2 1 1 2 7 1 1 5 6
16 9 7 3 4 5 9 3 2 1 1 2 7 1 1 5 6
3) Encoding If traversing the left branch Label 1 If traversing the right branch Label 0 Follow this procedure from the root to the child of interest adding a 1 or 0 depending on the traversal 1 0
0 1 3 1 0 9 0 1 Intensity 3 9 1 5 6 7 Encoding 1 01 001 00001 00000 0001 1 1 0 7 0 1 5 6
Whats awesome here? 8 Intensity 1 3 5 6 7 9 Encoding 001 1 00001 00000 0001 01 7 6 Frequency 5 4 3 2 1 0 1 3 5 6 7 9 Intensity
Real Example Which values are going to have the shortest code?
Q8.8 in textbook How many unique Huffman codes are there for a three-symbol source? Construct them. Let s assume the three symbols are: A, B and C where the probability of A, B and C are in order from lowest to highest.
What would the Huffman tree look like? 9 1 0 4 5 C A B C 11 10 0 0 1 3 1 A B
What would happen if the probability of C was less than the sum of A and B? 7 1 3 4 0 A B C 01 00 1 C 0 1 3 1 A B
Therefore there are two unique codes for a three-symbol source Notice the codes are complements of each other A B C 11 10 0 A B C 01 00 1
Q8.10 in textbook Using the Huffman code in Fig. 8.8, decode the encoded string: 0101000001010111110100
0101000001010111110100 0101000001010111110100
Another example 010100111100 010100111100
