notes_Image Compression_edited.ppt

Compression Algorithms

1. Digital Image Processing
Image Compression
Dr. Haris Masood

2. 2
Background
Principal objective:
To minimize the number of bits required to represent an image.
Applications
Transmission:
Broadcast TV via satellite, military communications via aircraft,
teleconferencing, computer communications etc.
Storage:
Educational and business documents, medical images (CT, MRI and
digital radiology), motion pictures, satellite images, weather maps,
geological surveys, ...

3. 3
Overview
Image data compression methods fall into two common
categories:
I. Information preserving compression
Especial for image archiving (storage of legal or medical records)
Compress and decompress images without losing information
II. Lossy image compression
Provide higher levels of data reduction
Result in a less than perfect reproduction of the original image
Applications: –broadcast television, videoconferencing

4. 4

5. 5
Data vs. information
•Dataisnotthesamethingasinformation
•Dataarethemeanstoconveyinformation;various
amountsofdatamaybeusedtorepresentthesame
amountofinformationPartofdatamayprovideno
relevantinformation:dataredundancy
•Theamountofdatacanbemuchlargerexpressed
thantheamountofinformation.

6. 6
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.

7. 7
Data Redundancy

8. 8
Data Redundancy
Three basic data redundancies
Coding Redundancy
Interpixel Redundancy
Psychovisual Redundancy

9. 9
Coding Redundancy
Anaturalm-bitcodingmethodassignsm-bittoeachgray
levelwithoutconsideringtheprobabilitythatgrayleveloccurs
with:Verylikelytocontaincodingredundancy
Basicconcept:
Utilizetheprobabilityofoccurrenceofeachgraylevel
(histogram)todeterminelengthofcoderepresentingthat
particulargraylevel:variable-lengthcoding.
Assignshortercodewordstothegraylevelsthatoccurmost
frequentlyorviceversa.

10. 10
Coding Redundancy

11. 11
Coding Redundancy (Example)

12. 12
Coding Redundancy (Example)

13. 13
Coding Redundancy (Example)

14. 14
Interpixel Redundancy
Caused by High Interpixel Correlationswithin an image, i.e.,
gray level of any given pixel can be reasonably predicted from
the value of its neighbors (information carried by individual
pixels is relatively small) spatial redundancy, geometric
redundancy, interframe redundancy (in general, interpixel
redundancy)
To reduce the interpixel redundancy, mappingis used. The
mapping schemecan be selected according to the properties of
redundancy.
An example of mapping can be to map pixels of an image: f(x,y)
to a sequence of pairs: (g
1,r
1), (g
2,r
2), ..., (g
i,r
i),..
g
i: ith gray level r
i: run length of the ith run

15. 15
Interpixel Redundancy (Example)

16. 16
Psychovisual Redundancy
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 calledquantization) are
usually applied to commercial broadcast TV and similar
applications for human visualization.

17. 17
Psychovisual Redundancy

18. 18
Psychovisual Redundancy

19. 19
Psychovisual Redundancy

20. 20
Fidelity Criteria

21. 21
Fidelity Criteria

22. 22
Fidelity Criteria

23. 23
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.

24. 24
Source Encoder and Decoder

25. 25
Types of Compression
•Lossless compression
–Huffman coding
–Bit-plane coding
–Run length coding
•Lossy compression
–Lossy predictive coding
–Transform coding
–JPEG

26. Error-Free Compression
26

27. Variable-length Coding Methods: Huffman Coding
27

28. Variable-length Coding Methods: Huffman Coding
28

29. 29

30. Mapping
30
•There is often correlation between adjacent pixels, i.e. the value
of the neighbors of an observed pixel can often be predicted from
the value of the observed pixel. (Interpixel Redundancy).
•Mapping is used to remove Interpixel Redundancy.
•Two mapping techniques are:
Run length coding
Difference coding.

31. 31

32. 32

33. 33

34. 34

35. 35

36. Other Variable-length Coding Methods

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

38. Example
38

39. 40
Bitplane Coding (1/2)
•Itreducestheimagesinterpixelredundanciesby
processingtheimage’sbitplanesindividually.
•Themultilevelimagesaredecomposedintoaseriesof
binaryimagesandthencompressingthebinary
imagesusingoneoftheseveralwell-knownbinary
compressionmethods.
•Theimagesareoftenfirstgraycodedbeforethebit
planedecompositioniscarriedouttoavoidtoomany
0to1transitionsacrossbitplanesforpixelvaluesthat
areclosetoeachother.

40. Bit-Plane Coding

41. Bit-Plane Decomposition (Example)

42. Bit-Plane Decomposition (Example)

43. Bit-Plane Decomposition (Example)

44. ArithmeticCoding
45
•Thereisnoonetoonecorrespondencebetweensource
symbolsandcodewords.
•Anentiresequenceofsourcesymbolsisassignedasingle
codeword.
•Eachsourcesymbolisrepresentedbyanintervalin[0,1).
Asthenumberofsymbolsincreasesthesizeofthe
intervalreducesinaccordancewiththeprobabilityof
occurrenceofsymbols.

45. Arithmetic
Coding
a10.2[0,0.20
a20.2[0.2,0.4)
a30.4[0.4,0.8)
a40.2[0.8,1.0)
Sequence to becoded a1 a2 a3 a3 a4
46

46. ArithmeticCoding
•Inaccurate probability models can lead to non-optimal results
•Solution: use an adaptive, context dependent probability model
•Adaptive: symbols probabilities are updated as the symbols are
coded.
•Context dependent: probabilities are based on a predefined
neighbourhood of pixels around the symbol being coded.
47

47. 48
Constant Area Coding(1/2)
•Asimplemethodtocompressbinaryorbit
planeimagesistousespecialcodewordsto
denotelargeareasofcontinuous0’sor1’s.
•Theimageisdividedintoblocksofpxqpixels,
whichareclassifiedasallblack,allwhiteor
mixed.
•Themostprobableorfrequentlyoccurring
categoryisassignedthe1-bitcodeword0,and
theothertwocategoriesareassigned2bitcode
words10and11.

48. CAC-Algorithm
•Special codeword's are used to identify large areas of contiguous 1's or 0's
•The whole image (M*N Pixels) is divided into blocks of size (P*Q Pixels)
•Blocks are classified as
•White (W) Blocks: having only white pixels
•Black (B) Blocks: having only black pixels
•Mixed (M) Blocks: having mixed intensity.
•The most frequent occurring category is assigned with 1-bit codeword 0
•If image contain only two categories, the other category is assigned with 1-bit
codeword 1
•Else the remaining other two categories are assigned with 2-bit codes 10 and 11
•The codeword assigned to the Mixed (M) Block category is used as a prefix,
which is followed by the P*Q-bit pattern of the block.
•Compression is achieved because the P*Q bits that are normally used to represent
each constant area (block) are replaced by a 1-bit or 2-bit codeword for White and
Black Blocks
•Compression Ratio (CR) = (N1 / N2)
49

49. Binary Image Compression: 1-D Run-Length Coding
(1D RLC): Lossless Technique

50. Binary Image Compression: 1-D Run-
Length Coding
51

51. Lossy Compression
•A lossy compressionmethod is one where compressing dataand
then decompressing it retrieves data that may well be different
from the original, but is close enough to be useful in some way.
•Lossy compression is most commonly used to compress
multimediadata (audio, video, still images), especially in
applications such as streaming mediaand internet telephony.

53. JPEG
•Lossy Compression Technique based on use
of Discrete Cosine Transform (DCT)
•A DCT is similar to a Fourier transformin
the sense that it produces a kind of spatial
frequency spectrum

54. STEPS IN JPEG COMPRESSION
•DivideEachplaneinto8x8sizeblocks.
•Transformthepixelinformationfromthespatialdomain
tothefrequencydomainwiththeDiscreteCosine
Transform.(ComputeDCTofeachblock)
•Quantizetheresultingvaluesbydividingeachcoefficient
byanintegervalueandroundingofftothenearestinteger.
•Arrangetheresultingcoefficientsinazigzagorder.so
thatthecoefficientsareinorderofincreasingfrequency.
Thehigherfrequencycoefficientsaremorelikelytobe0
afterquantization.Thisimprovesthecompressionofrun-
lengthencoding.
•Doarun-lengthencodingofthecoefficientsorderedin
thismanner.FollowbyHuffmancoding.(Separately
encodeDCcomponentsandtransmitdata.)

55. JPEG COMPRESSION

56. JPEG COMPRESSION
•The most importantvalues to our eyes will be placed in the
upper left cornerof the matrix.
•The least importantvalues will be mostly in the lower right
cornerof the matrix.
Semi-
Important
Most
Important
Least
Important

57. JPEG COMPRESSION
The example image 8*8matrix
before DCTtransformation.

58. JPEG COMPRESSION
Gray-Scale Example:
Value Range 0 (black) ---255
(white)
63 33 36 28 63 81 86 98
27 18 17 11 22 48 104 108
72 52 28 15 17 16 47 77
132 100 56 19 10 9 21 55
187 186 166 88 13 34 43 51
184 203 199 177 82 44 97 73
211 214 208 198 134 52 78 83
211 210 203 191 133 79 74 86

59. JPEG COMPRESSION
2D-DCT of matrix
Value Range 0 (Gray) ----355
(Black)
-304 210 104 -69 10 20 -12 7
-327 -260 67 70 -10 -15 21 8
93 -84 -66 16 24 -2 -5 9
89 33 -19 -20 -26 21 -3 0
-9 42 18 27 -7 -17 29 -7
-5 15 -10 17 32 -15 -4 7
10 3 -12 -1 2 3 -2 -3
12 30 0 -3 -3 -6 12 -1

60. JPEG COMPRESSION
Cut the least significant
components
Value Range 0 (Gray) ----355
(Black)
-304 210 104 -69 10 20 -12 0
-327 -260 67 70 -10 -15 0 0
93 -84 -66 16 24 0 0 0
89 33 -19 -20 0 0 0 0
-9 42 18 0 0 0 0 0
-5 15 0 0 0 0 0 0
10 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

61. JPEG COMPRESSION
Original Compressed
Results…

63. Some Common Image Formats

64. Some Common Image Formats