Image compression in digital image processing

Image compression Techniques Huffman coding, Arithmetic coding,Bitplane coding etc. In Digital Image Processing

1. Digital Image Processing Image Compression

2. Data vs. information Data is not the same thing as information Data are the means to convey information ; various amounts of data may be used to represent the same amount of information Part of data may provide no relevant information: data redundancy The amount of data can be much larger expressed than the amount of information.

3. Data Redundancy Data that provide no relevant information= redundant data or redundancy . Image compression techniques can be designed by reducing or eliminating the Data Redundancy Image coding or compression has a goal to reduce the amount of data by reducing the amount of redundancy.

4. Data Redundancy

5. Data Redundancy Three basic data redundancies Coding Redundancy Interpixel Redundancy Psychovisual Redundancy

6. Coding Redundancy A natural m-bit coding method assigns m-bit to each gray level without considering the probability that gray level occurs with: Very likely to contain coding redundancy Basic concept: Utilize the probability of occurrence of each gray level (histogram) to determine length of code representing that particular gray level: variable-length coding . Assign shorter code words to the gray levels that occur most frequently or vice versa.

7. Coding Redundancy

8. Coding Redundancy (Example)

9. Coding Redundancy (Example)

10. Coding Redundancy (Example)

11. Spatial and Temporal Redundancy Interpixel Spatial redundancy is due to the correlation between the neighboring pixels in an image. That means neighboring pixels are not statistically independent. The gray levels are not equally probable. The value of any given pixel can be predicated from the value of its neighbors that is they are highly correlated. The information carried by individual pixel is relatively small. To reduce the interpixel Spatial redundancy the difference between adjacent pixels can be used to represent an image.

12. Spatial and Temporal Redundancy I nterpixel temporal redundancy is the statistical correlation between pixels from successive frames in video sequence. Temporal redundancy is also called interframe redundancy. Temporal redundancy can be exploited using motion compensated predictive coding. Removing a large amount of redundancy leads to efficient video compression.

13. Irrelevant Information Information that is not used by the human visual system are psychovisually redundant. The eye does not respond with equal sensitivity to all visual information. Certain information has less relative importance than other information in normal visual processing psychovisually redundant (which can be eliminated without significantly impairing the quality of image perception). The elimination of psychovisually redundant data results in a loss of quantitative information lossy data compression method . Image compression methods based on the elimination of psychovisually redundant data (usually called quantization ) are usually applied to commercial broadcast TV and similar applications for human visualization.

14. Irrelevant Information

15. Fidelity Criteria

16. Fidelity Criteria

17. Fidelity Criteria

18. Image Compression Models The encoder creates a set of symbols (compressed) from the input data. The data is transmitted over the channel and is fed to decoder. The decoder reconstructs the output signal from the coded symbols. The source encoder removes the input redundancies, and the channel encoder increases the noise immunity.

19. Source Encoder and Decoder

20. Some Basic Compression Methods

21. Variable-length Coding Method: Huffman Coding

22. Variable-length Coding Method: Huffman Coding Huffman coding: give the smallest possible number of code symbols per source symbols. Step 1: Source reduction

23. Variable-length Coding Method: Huffman Coding Step 2: Code assignment procedure The code is instantaneous uniquely decodable without referencing succeeding symbols.

24. Variable-length Coding Method: Huffman Coding

25. (Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2 nd Edition. Nonblock code: one-to-one correspondence between source symbols And code words does not exist. Concept: The entire sequences of source symbols is assigned a single arithmetic code word in the form of a number in an interval of real number between 0 and 1. Arithmetic Coding

26. Arithmetic Coding Example (Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2 nd Edition. 0.2x0.4 0.04+0.8x0.04 0.056+0.8x0.016 0.2x0.2 0.04+0.4x0.04 0.056+0.4 x0.016 The number between 0.0688 and 0.06752 can be used to represent the sequence a 1 a 2 a 3 a 3 a 4

27. In this type of arithmetic coding, symbol probabilites that are based on predefined neighborhood of pixels called context are updated as symbols are coded or become known. Example : Q-Coder and MQ-Coder in JBIG,JPEG 2000 Adaptive Context Dependent Probability Estimates

28. LZW Coding Lempel-Ziv -Welch (LZW) coding assigns fixed length code words to variable length sequences of source symbols.

29. LZW Coding Algorithm 0. Initialize a dictionary by all possible gray values (0-255) 1. Input current pixel 2. If the current pixel combined with previous pixels form one of existing dictionary entries Then 2.1 Move to the next pixel and repeat Step 1 Else 2.2 Output the dictionary location of the currently recognized sequence ( which is not include the current pixel ) 2.3 Create a new dictionary entry by appending the currently recognized sequence in 2.2 with the current pixel 2.4 Move to the next pixel and repeat Step 1

30. LZW Coding (Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2 nd Edition. Lempel - Ziv -Welch coding : assign fixed length code words to variable length sequences of source symbols. 24 Bits 9 Bits

31. LZW Coding Example Input pixel 39 39 126 126 39 39 126 126 39 39 126 126 Dictionary Location Entry 0 0 1 1 … … 255 255 256 39 - 39 257 39 - 126 258 126 -126 259 126- 39 260 39 - 39 - 126 261 126 -126- 39 262 39 - 39 - 126 -126 Encoded Output (9 bits) 39 39 126 126 256 258 260 Currently recognized Sequences 39 39 126 126 39 39 - 39 126 126 -126 39 39 - 39 39 - 39 - 126 126

32. LZW Coding

33. Bit-Plane Coding

34. Bit-Plane Coding

35. Bit-Plane Decomposition (Example)

36. Bit-Plane Decomposition (Example)