428 A Computational Introduction to Digital Image Processing, Second Edition
Python
# Build the dictionary.
dictionary = [chr(i) for i in range(65,91)]
buffer = dictionary[code.pop(0)]
result = buffer
for n in code:
if
n <
len(dictionary):
entry = dictionary[n]
elif n == len(dictionary):
entry = buffer + buffer[0]
else:
raise
ValueError(’Bad
compressed code: %s’ % n)
result += entry
# Add buffer+entry[0] to the dictionary.
print buffer+entry[0],len(dictionary)
dictionary += [buffer + entry[0]]
buffer = entry
return result
def imLZW(im):
"""Compress an uppercase string to a list of output code values."""
data = [format(i,’02x’) for i in im.flatten().tolist()]
# Build the dictionary.
dictionary = [format(i,’02x’) for i in range(256)]
buffer = ""
result = []
for c in data:
newbuffer = buffer + c
if newbuffer in dictionary:
buffer = newbuffer
else:
result += [dictionary.index(buffer)]
# Add newbuffer to the dictionary.
dictionary += [newbuffer]
buffer = c
# Output the code for buffer.
if buffer:
result += [dictionary.index(buffer)]
return result
Image Coding and Compression 429
Exercises
1. Construct a Huffman code f or each of the probability tables given:
Grayscale
0 1 2 3 4 5 6 7
Probability (a) .07 .11 .08 .04 .5 .05 .06 .09
(b)
.13 .12 .13 .13 .12 .12 .12 .13
(c)
.09 .13 .15 .1 .14 .12 .11 .16
In each case, determine the average bits/pixel given by your code.
2. From your results of the previous question, what do you think are the conditions of
the probability distribution which give rise to a high compression rate using Huffman
coding?
3. Download a Huffman code program (or write one of your own), and test it on the
examples given.
Then try it on different images. What sort of compres sion rates do you obtain? What
sorts of images seem to have the best compression rates?
Note: Both Octave and MATLAB have Huffman routines in their Communications
toolboxes; a Python routine can be found at
http://rosettacode.org/wiki/Huffman
_
coding#Python
.
4. Encode each of the following binary images using run length encoding:
(a)
1 0 0 1 1 1
0 1 0 1 1 1
1 0 0 1 1 1
0 1 1 1 0 1
1 0 1 0 1 1
0 1 1 1 1 0
(b)
1 0 1 0 0 0
0 0 1 1 0 1
1 1 0 0 0 0
0 0 0 0 1 1
1 1 1 1 0 0
1 1 1 0 0 0
5. Using run length encoding, encode each of the following 4-bit images:
(a)
1 1 3 3 1 1
1 7 10 10 7 1
6 13 15 15 13 6
6 13 15 15 13 6
1 7 10 10 7 1
1 1 3 3 1 1
(b)
0 0 0 6 12 12 1 9
1 1 1 6 12 11 9 13
2 2 2 6 11 9 13 13
8 10 15 15 7 5 5 5
14 8 10 15 7 4 4 4
14 14 5 10 7 3 3 3
6. Check your answers to the previous two questions with the techniques discussed in this
chapter. You can isolate the bit planes by using the technique discussed in Section 3.3.
7. Encode the preceding images using the 4-bit Gray code, and apply run length encoding
to the bit planes of the result.
Compare the results obtained using Gray codes, and standard binary codes.
8. Write a func tion for restoring a binary image from a run length code. Test it on the
images and codes from the previous questions.
9. The following are the run-length encodings for a 4 ×4 4-bit image from most to least
important bit-planes:
430 A Computational Introduction to Digital Image Processing, Second Edition
3 1 2 2 1 4 1 2
1 2 1 2 1 2 1 2 1 3
2 1 2 1 2 2 1 5
0 3 1 3 2 3 1 2 1
Construct the image.
10. (a) G iven the following 4-bit image:
0 4 4 4 4 4 6 7
0 4 5 5 5 4 6 7
1 4 5 5 5 4 6 7
1 4 5 5 5 4 6 7
1 4 4 4 4 4 6 7
2 2 8 8 8 10 10 11
2 2 9 9 9 12 13 13
3 3 9 9 9 15 14 14
transform it to a 3-bit image by removing the least most significant bit plane.
Construct a Huffman code on the result and determine the average number of
bits/pixel used by the code.
(b) Now apply Huffman coding to the original image and determine the average
number of bits/pixel used by the code.
(c) Which of the two codes gives the best rate of compression?
11. By hand, apply LZW encoding to the phrases
(a) HOWNOWBROWNCOW
(b) REALLYREALCEREALDEAL
and decode the results.
12. Experiment with LZW coding of images. Which image has the best compression rate
and which image has the worst?
13. Write a program to perform LZW uncompression of an image code, and apply it to
the codes from the previous question.
14. Apply JPEG compression to an 8×8 block consisting of (a) all the same value, (b) the
left half one value, and the right half another, (c) random values uniformly distributed
in the 0–255 range.
Compare the length of the code vector in each case, and the results of decompression.
15. Open the image
engineer.png.
Using the JPEG compression commands described above, attempt to compress this
image using greater and greater compression rates. What is the largest quantization
scale factor for which the image is still recognizable? How many zeros are in the DCT
block matrix?
16. Apply the given JPEG Huffman codes to the vector:
-14 -3 -7 0 4 2 0 0 4 3 0 1 0 -1 -1 0 0 0-1 0 -1 EOB
and determine the compression rate.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.