Upload
others
View
1
Download
0
Embed Size (px)
Citation preview
Image Coding and CompressionImage Coding and Compression
Magnus Gedda Magnus Gedda [email protected]@cb.uu.se2005051920050519
GW Chapter 8.18.3.1, 8.48.4.3, 8.5.1GW Chapter 8.18.3.1, 8.48.4.3, 8.5.18.5.2, 8.68.5.2, 8.6
11
Lecture 17,Lecture 17,
Suggested problem: Own problemSuggested problem: Own problemCalculate the Huffman code of this image >Calculate the Huffman code of this image >Show all steps in the coding procedure, andShow all steps in the coding procedure, andcalculate calculate LL
avgavg..
•DataData is is notnot the same thing as the same thing as informationinformation..•Data is the means with which information is Data is the means with which information is expressed. The amount of data can be much larger expressed. The amount of data can be much larger than the amount of information. than the amount of information. •Data that provide no relevant information = Data that provide no relevant information = redundant dataredundant data or or redundancyredundancy. .
Image codning or compression has as a goal to Image codning or compression has as a goal to reduce the amount of data by reducing the amount reduce the amount of data by reducing the amount of redundancy. of redundancy.
Data and informationData and information
22
DefinitionsDefinitions
nn1 1 = data= datann2 2 = data redundancy (i.e. data after compression)= data redundancy (i.e. data after compression)
Compression ratioCompression ratio = C = CR R ==
Relative redundancy Relative redundancy = R= RD D ==
33
Images can contain three types of redundancyImages can contain three types of redundancy
1. Coding Redundancy1. Coding Redundancy2. Interpixel Redundancy2. Interpixel Redundancy3. PsychoVisual Redundancy3. PsychoVisual Redundancy
CR: some graylevels are CR: some graylevels are more common than othersmore common than others
IR: the same graylevel IR: the same graylevel covers large areas covers large areas
PVR: the eye can only resolve PVR: the eye can only resolve 32 graylevels locally32 graylevels locally
44
Image compression and decompressionImage compression and decompression
original imageoriginal image
compressioncompression 10290091023155 10290091023155 70291787418029 70291787418029 8095787591875828095787591875827451875984751987451875984751987518787584571097518787584571095850790575090558507905750905
””compact information”compact information”(for storage or transmission)(for storage or transmission)
decompressiondecompression
approximation of the original imageapproximation of the original image
(loss less compression)(loss less compression)
(lossy compression)(lossy compression)
55
Image compression can beImage compression can be •ReversibleReversible (loss less) no loss of information. (loss less) no loss of information.
•New image is identical to original image (after decoding). •Neccessary in most image analysis. •Compression ratio typically 210x.
•Non reversibelNon reversibel (lossy) loss of some information (lossy) loss of some information•Often used in image communication, video, www. •Important: that the image visually ”nice”. •Compression ratio typically 1030x.
66
Objective measures of image qualityObjective measures of image quality
error error e(x,y) = fe(x,y) = fapproxapprox(x,y) f(x,y) foriginaloriginal(x,y)(x,y)
total etotal etot tot ==
rootmensquare erootmensquare eRMSRMS==
signaltonoice ratio SNRsignaltonoice ratio SNRMSMS==
Subjective measures of image qualitySubjective measures of image qualityLet a number of test persons grade the images as bad/OK/good etc.Let a number of test persons grade the images as bad/OK/good etc.
∑x=0
M−1
∑y=0
N−1
f approx− f original
1MN ∑x=0
M−1
∑y=0
N−1
f approx− f original 2
∑x=0
M−1
∑y=0
N−1
f approx 2
∑x=0
M−1
∑y=0
N−1
f approx− f original 2
77
How much information is present in the image?How much information is present in the image?
If p(E) is the probability of an event, then I(E)=logp(E) is a If p(E) is the probability of an event, then I(E)=logp(E) is a measure of the information that the event provides. measure of the information that the event provides.
The average information is called entropy (Shannon entropy)The average information is called entropy (Shannon entropy)
88
Basic idea: different gray levels occur with different probability (non Basic idea: different gray levels occur with different probability (non uniform histogram). Use shorter code words for the more common uniform histogram). Use shorter code words for the more common gray levels and longer code words for the less common gray levels. gray levels and longer code words for the less common gray levels. This is called This is called Variable Length Coding.Variable Length Coding.
The amount of data in an MxN image with L gray levels =MxNxLThe amount of data in an MxN image with L gray levels =MxNxLavgavg
where Lwhere Lavgavg==
l(rl(rkk)) is the number of bits used to represent gray level r is the number of bits used to represent gray level rk k
p(rp(rkk)) is the probability of gray level r is the probability of gray level rkk in the image in the image
1. Coding redundancy1. Coding redundancy
99
This will however This will however NOTNOT work since the code is not unambiguous. work since the code is not unambiguous. What does for example the code 010 mean? Use Huffman coding!What does for example the code 010 mean? Use Huffman coding!
Example 3bit image:Example 3bit image:gray level rgray level rkk probability p(rprobability p(rkk)) source source codecode
00 0.10.1 000000 010111 0.40.4 001001 0022 0.030.03 010010 111133 0.050.05 011011 101044 0.30.3 100100 1155 0.10.1 101101 000066 0.010.01 110110 11111177 0.010.01 111111 000000
source : Lsource : Lavgavg=(constant l(r=(constant l(rkk)=3)=3*1=3)=3)=3*1=3code: Lcode: Lavgavg=0.1*2+0.4*1+…=1.32=0.1*2+0.4*1+…=1.32
∑k=0
L−1
l r k pr k LLavgavg==
1010
The Huffman codeThe Huffman code::yields the smallest possible number of unique code symbols per yields the smallest possible number of unique code symbols per source symbol.source symbol.
Step 1Step 11. sort the gray levels by decreasing probability 1. sort the gray levels by decreasing probability 2. add the two smallest probabilities2. add the two smallest probabilities3. sort the new value into the list3. sort the new value into the list3. repeat until only two probabilities remain3. repeat until only two probabilities remain
Step 2Step 21. give the code 0 to the highest probability, and the code 1 to the 1. give the code 0 to the highest probability, and the code 1 to the lowest probability in the present nodelowest probability in the present node2. go backwards through the tree and add 0 to the highest and 1 to 2. go backwards through the tree and add 0 to the highest and 1 to the lowest probability in each node until all gray levels have a the lowest probability in each node until all gray levels have a unique codeunique code
1111
Example of Huffman codingExample of Huffman coding
graylevel rk p(rk) node 1 node 2 node 3 node 4 node 5 node 61 0.44 0.30 0.15 0.13 0.052 0.036 0.017 0.01
Lavg=3graylevel rk code node 1 node 2 node 3 node 4 node 5 node 6
140532
CCRR=n=n11/n/n22== RRDD=11/C=11/CRR=(n=(n11nn22)/n)/n11== 1212
The Huffman code (continued)The Huffman code (continued)
•The Huffman code results in an unambiguous code, i.e. The Huffman code results in an unambiguous code, i.e. no code can be created by combining other codes.no code can be created by combining other codes.
•The code is reversible without loss.The code is reversible without loss.
•The table for the translation of the code has to be stored The table for the translation of the code has to be stored together with the coded image. together with the coded image.
•The Huffman code does not take correlation between The Huffman code does not take correlation between adejacent pixels into consideration.adejacent pixels into consideration.
1313
(also called spatial or geometric redundancy)(also called spatial or geometric redundancy)There is often correlation between adjacent pixels, i.e. There is often correlation between adjacent pixels, i.e. the value of the neighbours of an observed pixel can the value of the neighbours of an observed pixel can often be predicted from the value of the observed often be predicted from the value of the observed pixel. pixel.
Coding methodsCoding methods: : •Runlength coding Runlength coding •Difference coding.Difference coding.
2. Interpixel Redundancy2. Interpixel Redundancy
1414
Runlength codingRunlength coding
Every code word is made upp of a pair Every code word is made upp of a pair (g,l)(g,l) where where gg is the is the graylevel and graylevel and ll is the number of pixels with that graylevel (length, is the number of pixels with that graylevel (length, or ”run”).or ”run”).
Ex Ex 56 56 56 82 82 82 83 80 56 56 56 82 82 82 83 80 56 56 56 56 56 80 80 8056 56 56 56 56 80 80 80
creates the runlength code (56,3) (82,3) (83,1) (80,4) (56,5)creates the runlength code (56,3) (82,3) (83,1) (80,4) (56,5)
The code is calculated row by row.The code is calculated row by row.Very efficient coding for binary data.Very efficient coding for binary data.Important to know position, and the image dimensions must be Important to know position, and the image dimensions must be stored with the coded image.stored with the coded image.Used in most fax machinesUsed in most fax machines
1515
Difference codingDifference coding
f(xf(xii)= x)= xii if i=0, if i=0, xxiixxi1 i1 if i>0if i>0
Ex original:Ex original: 56 56 56 82 82 82 83 80 80 80 8056 56 56 82 82 82 83 80 80 80 80code f(xcode f(xii) :) : 56 0 0 26 0 0 1 3 0 0 056 0 0 26 0 0 1 3 0 0 0
The code is calculated row by row. The code is calculated row by row.
Both Runlength coding och Difference coding are reversible and Both Runlength coding och Difference coding are reversible and can be combined with for example Huffman coding.can be combined with for example Huffman coding.
{{
1616
Example of combined Difference and Example of combined Difference and Huffman codingHuffman coding
original imageoriginal image difference imagedifference image
1717
LLavgavg=3.1=3.1
Huffman code of original imageHuffman code of original image
1818
LLavgavg=2=2
Huffman code of difference imageHuffman code of difference image
1919
Bitplane codingBitplane coding
Divide the grayscale/color image into a series Divide the grayscale/color image into a series of binary images (one image per bit). Code of binary images (one image per bit). Code each image separately using the above each image separately using the above described methods. An 8bit image will be described methods. An 8bit image will be represented by 8 coded binary images. represented by 8 coded binary images.
2020
If the image will only be used for visual observation (i.e. If the image will only be used for visual observation (i.e. illustrations on the web etc), a lot of the information is illustrations on the web etc), a lot of the information is usually psychovisually redundant. It can be removed usually psychovisually redundant. It can be removed without changing the visual quality of the image. This kind without changing the visual quality of the image. This kind of compression is usually irreversible. of compression is usually irreversible.
0.5kB0.5kB 0.05kB0.05kB
2. PsychoVisual Redundancy2. PsychoVisual Redundancy
2121
Psychovisual redundancy is often reduced by quantifiacation:Psychovisual redundancy is often reduced by quantifiacation:
Example:Example:
Uniform quantification of graylevelsUniform quantification of graylevels remove the least significant bits of the data remove the least significant bits of the data causes edge effects causes edge effects
The edge effects can be reduced by The edge effects can be reduced by
""Improved Gray ScaleImproved Gray Scale", IGS", IGS Remove the least significant bits and add a ”random number” based Remove the least significant bits and add a ”random number” based on the sum of the least significant bits of the present and the previous on the sum of the least significant bits of the present and the previous pixel. pixel. special case if the graylevel of a pixel in an 8bit image is special case if the graylevel of a pixel in an 8bit image is 1111 xxxx, add 0000.1111 xxxx, add 0000.IGS reduces edge effects but will at the same time unsharpen true IGS reduces edge effects but will at the same time unsharpen true edges.edges.
2222
IGSIGS
2323
Motion picturesMotion picturesmethod 1: method 1: 1. transfere the first image to the observer1. transfere the first image to the observer2. find the changes from the previous image2. find the changes from the previous image3. transfere only the changes3. transfere only the changes
method 2: method 2: 1. transfere the most important information (e.g. the 1. transfere the most important information (e.g. the lowest frequencies) firstlowest frequencies) first2. send the less important information later2. send the less important information later
More quantification methods: More quantification methods:
2424
Transform codingTransform coding
1. Divide the image into nxn subimages1. Divide the image into nxn subimages2. Transform each subimage using a reversible transform (e.g. the 2. Transform each subimage using a reversible transform (e.g. the Hotellingtransform, the Discrete Fourier Transform (DFT), the Hotellingtransform, the Discrete Fourier Transform (DFT), the Discrete Cosine Transform (DCT)).Discrete Cosine Transform (DCT)).3. Quantify, i.e. truncate the transformed image, (for example with 3. Quantify, i.e. truncate the transformed image, (for example with DFT and DCT frequencies with small amplitude can be removed DFT and DCT frequencies with small amplitude can be removed without much information loss).The quantification can be either without much information loss).The quantification can be either image dependent (IDP) or image independent (IIP). image dependent (IDP) or image independent (IIP). 4. Code the resulting data, normally using some kind of "variable 4. Code the resulting data, normally using some kind of "variable length coding", for example Huffman code.length coding", for example Huffman code.
The coding is not reversible (unless step 3 is skipped) The coding is not reversible (unless step 3 is skipped)
2525
JPEG (Joint Photographic Experts Group)JPEG (Joint Photographic Experts Group)exists in many different versions but is always exists in many different versions but is always some kind of transform coding. JPEG is not some kind of transform coding. JPEG is not reversible due to quantification.reversible due to quantification.
MPEG (Motion Pictures Experts Group) MPEG (Motion Pictures Experts Group) Similar to JPEG, but the motion in comparison to Similar to JPEG, but the motion in comparison to the previous image is calculated and used in the the previous image is calculated and used in the compression. compression.
|Some common image formats|Some common image formats
2626
Example: JPEG compressionExample: JPEG compression
27 kB27 kB 17 kB17 kB
11 kB11 kB 6 kB6 kB
75%75% 50%50%
25%25% 10%10% 2727
LZWkodningLZWkodning (LempelZivWelch) (LempelZivWelch) A "wordbased" code. The data is represented by pointers to a library A "wordbased" code. The data is represented by pointers to a library of symbols (see Huffman code). LZW compression is loss less and of symbols (see Huffman code). LZW compression is loss less and can often be choosen when can often be choosen when TIFFTIFF (Tagged Image File Format) images (Tagged Image File Format) images are stored. The result is a smaller file which usually takes a bit longer are stored. The result is a smaller file which usually takes a bit longer to decode. An Image File Directory (set of symbols) is included in the to decode. An Image File Directory (set of symbols) is included in the header.header.
GIFGIF (Graphics Interchange Format) (Graphics Interchange Format) Creates a coding for color images where each color is coded by only a Creates a coding for color images where each color is coded by only a few bits (usually 3). GIF also uses LZW compression for storage and few bits (usually 3). GIF also uses LZW compression for storage and transfers. GIF is fully reversible (lossless) if less than 256 colors are transfers. GIF is fully reversible (lossless) if less than 256 colors are present in the original image.present in the original image.
Remember that the TIME used for coding and decoding is important Remember that the TIME used for coding and decoding is important when choosing coding method!when choosing coding method!
|Some more common image formats|Some more common image formats
2828
Choice of image formatChoice of image format•Images to be used for image analysis should always be saved in a Images to be used for image analysis should always be saved in a loss less format! loss less format!
•Images for the WWW have to be either GIF, JPEG or PNG (due to Images for the WWW have to be either GIF, JPEG or PNG (due to the license issues of GIF)the license issues of GIF)
Chose Chose GIFGIF for for graphsgraphs and hand drawn figures with few color and hand drawn figures with few color shades (JPEG transform coding and truncation can cause artefacts shades (JPEG transform coding and truncation can cause artefacts around sharp edges)around sharp edges)
Chose Chose JPEGJPEG for for photosphotos and figures with many colors and smooth and figures with many colors and smooth transitions between colors (GIF reduces the number of colors to transitions between colors (GIF reduces the number of colors to 256).256).
2929
3030