Image Coding and Compression 423
MATLAB/Octave
>> imshow(imresize(c(68-31:68+32,56-31:56+32),4))
which is shown in Figure 14.10. The same areas, with the scales of 1 and 2, are shown in
FIGURE 14.10: An image closeup
Figure 14.11. And the closeups , with the scales of 5 and 10, are shown in Figure 14.12.
FIGURE 14.11: Closeups after the scale factors of 1 and 2
Notice that “blockiness” becomes more apparent as the scale factor increases. This is due
to the working of the algorithm; that each 8 × 8 block is processed independently of the
others. This tends to pro duce discontinuities in the output, and is one of the disadvantages
of the JPEG algorithm for high levels of compression.
In Chapter 15, we shall see that some of these disadvantages can be overcome by using
wavelets for compression.
We have seen how changing the compression rate may affect the output. But the JPEG
algorithm is particularly designed for storage. For example, suppose we take the original
block from the caribou image, but divide it by double the quantization matrix. After
reordering, the output vector will be
7 -1 -10 0 2 1 0 0 2 4 0 1 0 -1 EOB
This vector is further encoded using Huffman coding. To do this, each element of the
vector (except for the first), that is, each AC value, is defined to be in a particular category
depending on its absolute value. In general, the valu e 0 is given category 0, and category k
424 A Computational Introduction to Digital Image Processing, Second Edition
FIGURE 14.12: Closeups after the scale factors of 5 and 10
contains all elements x whose absolute value satisfies
2
k
≤ |x| ≤ 2
k+1
− 1.
The categories are also used for the differences of the first (DC) value. The first few
categories are:
Range DC Category AC Category
0 0 Not applicable
−1, 1 1 1
−3, −2, 2, 3 2 2
−7, . . . , −4, 4, . . . , 7 3 3
−15, . . . , −8, 8, . . . , 15 4 4
To encode the vector, the category is used with all non-zero terms, along with the number
of preceding zeros. For example, for the vector above:
Values: 7 −1 10 0 2 1 0 0 2 4 0 1 0 −1
Category: 1 4 2 1 2 3 1 1
Preceding zeros: 0 0 1 0 2 0 1 1
For each non-zero AC value then, a binary vector is produced containing the Huffman code
for its particular category and run of preceding zeros, followed by a sign bit (0 for negative,
1 for positive), and then for category k a run of k − 1 bits indicating the position within
that category. The Huffman code table is provided as part of the JPEG baseline standard;
for the first few categories and runs, they are:
Run Category Code
0 0 1010
0 1 00
0 2 01
0 3 100
0 4 1011
1 1 1100
1 2 111001
1 3 1111001
1 4 111110110
2 1 11011
2 2 11111000
2 3 1111110111
Image Coding and Compression 425
A full table is given by Gonzalez and Woods [13]. For the non-zero AC values in the above
vector, the output binary strings will be created from:
Run Category Code Sign Position
0 1 00 0 0
0 4 1011 1 011
1 2 111001 1 0
0 1 00 1 1
2 2 11111000 1 0
0 3 100 1 00
1 1 1100 1 0
1 1 1100 0 0
The output string of bits for this block will consist of the code for the difference of the DC
coefficient, followed by:
0000/10111011/11100110/0011/1111100010/100100/110010/110000
where the lines just show the individual strings. Assuming 8 bits for the first code, the
entire block has been encoded with only 60 bits,
60/64 ≈ 0.94
bit per pixel: a compression rate of over 8.5.
For a detailed account of the JPEG algorithm, see Pennebaker [56].
14.6 Programs
Start with some programs in MATLAB/Octave for LZW compression of uppercase text:
MATLAB/Octave
% Local Variables:
% mode: Octave
% End:
function [out,dict] = LZW(data)
%
% A very simple function for LZW compression of strings of uppercase
letters.
%
L = length(data);
dict = mat2cell(char(65:90),1,ones(26,1));
buffer = "";
out = [];
n = 27;
for i = 1:L,
newbuffer = strcat(buffer, data(i));
if ~ismember(newbuffer,dict),
dict{n} = newbuffer;
disp(cstrcat(newbuffer,’
’,num2str(n)))
[x,m] = ismember(buffer,dict);
out = [out,m];
426 A Computational Introduction to Digital Image Processing, Second Edition
MATLAB/Octave
n = n+1;
buffer = data(i);
else,
buffer = newbuffer;
end
end
[x,m] = ismember(data(end),dict);
out = [out,m];
end
and for decompression of the resulting code:
MATLAB/Octave
% Local Variables:
% mode: Octave
% End:
function out = unLZW(code)
%
% A very simple function for LZW decompression of strings of uppercase
letters.
%
L = length(code);
dict = mat2cell(char(65:90),1,ones(26,1));
buffer = "";
out = dict{code(1)};
n = 27;
buffer = dict{code(1)};
for i = 2:L
c = code(i);
if c <= length(dict)
entry = dict{c};
elseif c == length(dict)+1
entry = strcat(buffer,buffer(1));
else
error(’Bad
compressed code’);
end
out = strcat(out, entry);
dict{n} = strcat(buffer,entry(1));
n = n+1;
buffer = entry;
end
end
Finally, the LZW program slightly adjusted to manage images of type unit8. Note that
this program does no error checking, so that if the image is not of type
unit8 the program
will produce rubbish.
MATLAB/Octave
function [out,dict] = imLZW(im)
%
% A very simple function for LZW compression of an image
%
data = dec2hex(im(:),2);
L = length(im(:));
Image Coding and Compression 427
MATLAB/Octave
dict = mat2cell(dec2hex([0:255],2),ones(256,1),2);
buffer = "";
out = uint16([]);
n = 257;
for i = 1:L,
newbuffer = strcat(buffer,data(i,:));
if ~ismember(newbuffer,dict),
dict{n} = newbuffer;
[x,m] = ismember(buffer,dict);
out = [out,m];
n = n+1;
buffer = data(i,:);
else,
buffer = newbuffer;
end
end
out = [out,im(end)];
end
For Python, here is the program file which contains all three functions: compression of
uppercase text and of images, and decompressing to text.
Python
# Adapted from http://rosettacode.org/wiki/LZW
_
compression#Python to be
super-simple
def LZW(data):
"""Compress
an uppercase string to a list of output code values."""
# Build the dictionary.
dictionary = [chr(i) for i in range(65,91)]
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]
print newbuffer,dictionary.index(newbuffer)
buffer = c
# Output the code for buffer.
if buffer:
result += [dictionary.index(buffer)]
return result
def unLZW(code):
"""Decompress
a list of output codes to an uppercase string."""
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.135.203.119