Length variable coding in digital image processing.pptx

"variable length coding" refers to a data compression technique that assigns codewords of varying lengths to different symbols (e.g., pixel values, run lengths of pixels, or transform coefficients) based on their frequency of occurrence. The core principle is to achieve compression by assigning shorter codewords to more frequently occurring symbols and longer codewords to less frequent ones. This contrasts with fixed-length coding, where every symbol is represented by a codeword of the same length.

1. Variable Length Coding in Digital Image Processing NADAR SARASWATI COLLEGE OF ARTS AND SCIENCE NAME: PRATHIYATHI. M II- M. Sc CS

2. What is Variable Length Coding? Definition: A data compression technique where codes of varying lengths are used to represent source symbols. Core Principle: Assign shorter codes to more frequent symbols and longer codes to less frequent symbols. Analogy: Think of Morse code. 'E' (most frequent letter in English) is '•', while 'Q' is '--•-'. Goal: Reduce the overall average code length, leading to higher compression ratios. Relevance to Images: In digital images, certain pixel values, transform coefficients (e.g., from JPEG's DCT), or run-lengths of zeros are more common than others.

3. Why is Variable Length Coding Necessary for Images? The Problem with Fixed-Length Coding: Simple and easy to implement (e.g., 8-bit per pixel). Wastes space for frequently occurring data; every symbol gets the same amount of space. Inefficient for data with non-uniform probability distributions, typical for image data after a transform like DCT. The Solution - Variable Length Coding: Exploits the statistical redundancy of image data. After quantization (e.g., in JPEG), most transform coefficients become zero or small positive/negative numbers. VLC can represent these large runs of zeros and small numbers very efficiently.

4. Key Concepts & Terminology 1 Source Symbols The individual units of data to be coded. Quantized DCT coefficients (e.g., in JPEG) Run-length pairs (e.g., (run_of_zeros, value)) 2 Probability ($P(s)$) The likelihood of a symbol 's' occurring. This is the crucial information exploited by VLC. 3 Code Word The binary sequence assigned to a symbol. 001 , 10 , 110 4 Prefix Code A code where no code word is a prefix of another code word, essential for unambiguous decoding. Example: If '0' is a code word, then '01' cannot be another code word.

5. Common Variable Length Coding Schemes Huffman Coding: The Pioneer The most famous VLC technique. Algorithm: A greedy algorithm that builds a binary tree based on symbol frequencies. How it Works: Calculate the frequency of each symbol. Create a leaf node for each symbol with its frequency. Repeatedly merge the two nodes with the lowest frequencies. The final tree gives the code words (path from root to leaf). Properties: Generates an optimal prefix code for a given set of symbol probabilities.

6. Common Variable Length Coding Schemes (cont.) Arithmetic Coding: Beyond Huffman More advanced and generally more efficient than Huffman. How it Works: Codes the entire message as a single floating-point number within the range [0, 1) . The size of the final interval relates to the sequence's probability. Advantages: Achieves compression ratios closer to the theoretical entropy limit; does not require a lookup table of codes. Disadvantage: More computationally intensive and complex to implement compared to Huffman coding.

7. Common Variable Length Coding Schemes (cont.) Run-Length Encoding (RLE): A Simpler Approach A simpler, complementary technique. How it Works: Represents sequences of identical symbols as a single pair: (count, symbol). Example: The sequence AAAAABBBCCD becomes (5, A), (3, B), (2, C), (1, D) . Application in JPEG: After quantization and zig-zag scanning of the DCT block, there are often long runs of zeros. RLE efficiently represents these zero runs before Huffman coding.

8. VLC in a Real-World Application: JPEG Compression 01 1. Transform Image is divided into 8x8 blocks; Discrete Cosine Transform (DCT) applied. 02 2. Quantization DCT coefficients divided by a matrix, making many values zero or small; primary lossy step. 03 3. Zig-Zag Scan 8x8 block scanned in a zig-zag pattern to group low-frequency coefficients and create long zero runs. 04 4. Run-Length Coding Zig-zagged coefficients are run-length encoded (e.g., (run_of_zeros, non-zero_value)). 05 5. Huffman Coding RLE pairs and DC coefficient differences encoded using Huffman tables; final, lossless compression.

9. Advantages and Disadvantages of VLC Advantages: High Compression Ratio: Significantly reduces file size by exploiting statistical redundancy. Optimal/Near-Optimal Performance: Achieves compression close to the theoretical entropy limit. Lossless: The coding process itself does not introduce data loss (loss in JPEG is from quantization, not VLC). Disadvantages: Increased Complexity: More complex to implement than fixed-length coding. Sensitivity to Errors: A single bit error can misalign the entire decoding process, causing cascading errors. Requires Prior Knowledge: Probability distribution of data must be known or estimated to build code tables.

10. Conclusion & Summary Variable Length Coding is a fundamental and essential component of modern image compression. It works by assigning shorter codes to more frequent data and longer codes to less frequent data. Key techniques include Huffman Coding, Arithmetic Coding, and complementary techniques like Run-Length Encoding. Its primary role in digital image processing is to efficiently compress the redundant data that remains after transform and quantization steps (e.g., in JPEG). By understanding VLC, we gain insight into how digital images can be stored and transmitted so efficiently.