JPEG - Idea and Practice/Program for drawing a grey scale picture

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Now to the program that can read a grey scale JPEG file and draw the picture. It is not required that the segments are written in a specific order (except that APP0 must come just after SOI), therefore the program that reads the file must seek after markers, and when such a marker is found (which is different from SOI and EOI), the program must read the following pair of bytes stating the length of the segment. During this reading we must continuously count the number of bytes read by adding 1 to a number r starting with 0, and when all the segments are read (and the information is worked up for the arrays we make use of), go to the place r = rhead where the data begin (just after the SOS segment - rhead is the number of the last byte in SOS).

The coded data are used bit by bit, but they lie in the file as bytes, as each 8-block of bits is converted to a byte when the file is written. Therefore we must have a procedure which gives us the next bit and reads the next byte every time 8 bits are used. We call this procedure nbit, and the program for it is shown at the end in this section.

The program is arranged so that an 8x8-square is drawn (via a "setpixel" procedure) every time the necessary bytes are read to form a 64-array w[l], l = 1, ..., 64. The reading is controlled by the number l, successively increased by 1 every time a number is inserted in w[l]. When l = 64 w is converted to an 8x8-matrix via the zigzag function, and this 8x8-matrix (g(u, v)) is submitted to de-quantization and the inverse cosine transform giving the 8x8-matrix f[i, j] (i, j = 0, ..., 7) of colour values (signed bytes made to bytes by adding 128 to them). If the 8x8-square has the coordinate set (i0, j0) (i0 = 0, ..., wid8-1, j0 = 0, ..., hei8-1), the point to be coloured with the value f[i, j] has the coordinate set (i0*8 + i, j0*8 + j). When the 8x8-square is drawn, l is again set to 1 and the coordinate set (i0, j0) of the 8x8-square is altered to the coordinate set of the next square, namely i0 = i0 + 1 for i0 < wid8, and i0 = 0 and j0 = j0 + 1 for i0 = wid8.

The procedures that decode the DC and the AC codes are called decoded and decodea, respectively. They give a number val used by the procedure num to calculate a number m. The programs for these procedures are shown after the main program.

For l = 1 decoded is applied. It gives a number val stating the number of bits to be read next, and these make up the digit expression of a number m calculated by num, and m added to the preceding DC number (stored in the variable dc0) is the DC term of w: dc = m + dc0, w[1] = dc.

For l > 1 decodea is applied. It gives two half-bytes nz and val. The first half-byte nz states a number of zeros, and the second half-byte val states the number of bits to be read next if val > 0. In this case (val > 0), l is increased by 1 nz times (if nz > 0), and for each of these l's w[l] is set to zero. Then l is again increased by 1, and the next val bits make up the digit expression of a number m calculated by num and this is w[l]. If val = 0, nz is either 15 or 0. If nz = 15, l is increased by 1 16 times and for each of these l's w[l] is set to zero. If nz = 0, this indicates that all of the following AC terms are zero, that is, l is increased by 1 until l = 64 and for each of these l's w[l] is set to zero.

When l = 64 the array w[l] is completed and we can draw the 8x8-square. In order to draw to picture faster, we will restrict the calculations (for each (i, j)) in the inverse cosine transform to u, v = 0, ..., 5, so that we only use the first 36 of the 64 terms. Because of the uncertainty of the calculations, the colour values (after the addition of 128) can be smaller than 0 or larger than 255, and may therefore have to be clambered.

The reading of the data part of the file and the drawing of each 8x8-square take place in a loop (drawloop) that is set to stop when the end of the file is reached. The (global) variable r, increased by 1 for each time a byte is read from the file, starts with r = rhead (the last byte of the header section):

r = rhead
i0 = 0
j0 = 0
l = 1
s = 8
b = 0
dc = 0
dc0 = 0

drawloop

if l = 1 then
begin
dc0 = dc
decoded
num
dc = m + dc0
w[1] =dc
end
decodea
if val > 0 then
begin
if nz > 0 then
for i = 1 to nz do
begin
l = l + 1
w[l] = 0
end
num
l = l + 1
w[l] = m
end
if (nz = 15) and (val = 0) then
for i = 1 to 16 do
begin
l = l + 1
w[l] = 0
end
if (nz = 0) and (val = 0) then
while l < 64 do
begin
l = l + 1
w[l] = 0
end
if l = 64 then
begin
l = 1
for j = 0 to 7 do
for i = 0 to 7 do
begin
t = w[1] * cq[0, 0] / sqrt(2)
for v = 1 to 5 do
t = t + cs[j, v] * cq[0, v] * w[iz(0, v)]
s = t / sqrt(2)
for u = 1 to 5 do
begin
cq[u, 0] * w[iz(u, 0)] / sqrt(2)
for v = 1 to 5 do
t = t + cs[j, v] * cq[u, v] * w[iz(u, v)]
s = s + cs[i, u] * t
end
k = round(s + 128)
if k < 0 then
k = 0
if k > 255 then
k = 255
setpixel(i0 * 8 + i, j0 * 8 + j, k, k, k)
end
i0 = i0 + 1
if i0 = wid8 then
begin
i0 = 0
j0 = j0 + 1
end
end
goto drawloop

The procedure decoded decodes the Huffman codes for the DC numbers (l = 1) and the procedure decodea decodes the Huffman codes for the AC numbers (l > 1). They use the arrays mincode[k], maxcode[k], valptr[k] and huffval[k], constructed from the Huffman tables. For the Huffman tables for the DC numbers these arrays are called mincoded[k], maxcoded[k], valptrd[k] and huffvald[k], and for the Huffman tables for the AC numbers they are called mincodea[k], maxcodea[k], valptra[k] and huffvala[k]. The procedures decoded and decodea contain the procedure nbit that reads the next bit. The program for decoded can look like this:

c = 0
j = 0
while c > maxcoded[j] do
begin
nbit
c = 2 * c + bit
j = j + 1
end
val = huffvald[valptrd[j] + c - mincoded[j]]

The program for decodea is analogues, except that the number val (byte) now is divided up in two half-bytes: nz = val div 16 and val = val - nz * 16 - the first half-byte nz stating a number of zeros.

The number val produced by decoded and decodea states the number of bits to be read next, and these bits form the digit expression of the number m. m is calculated via the procedure num, which also makes use of the next bit procedure nbit. However, if the first bit read is zero, this indicates that the number m is negative and its numerical value is then the binary complement of the calculated m, that is, m = -(q0-1 - m), where q0 = 2val (the reading of the first bit bit1 is controlled by the number z):

procedure num
begin
q0 = round(exp(val * ln(2)))
q = q0
z = 0
m = 0
while q > 1 do
begin
q = q div 2
nbit
if z = 0 then
begin
bit1 = bit
z = 1
end
m = m + bit * q
end
if bit1 = 0 then
m = -(q0 - 1 - m)
end

Now to the procedure nbit, which produces the next bit, called bit, in the bit stream, and which is used in the procedures decoded, decodea and num. The next bit is taken from an array c[i] from 1 to 8, which is produced every time 8 bits are used: then a new byte b is read, and c is the digit expression of b: c = digit(b) - the program for digit is shown below. The reading of the bits is managed by a (global) variable s, which starts with 0, and in each application of nbit is increased by 1, and then set to 0 again when s = 8 (we must start with s = 8, so that the first byte can be read). However, since in the writing of the file we have written a zero byte after each byte that is 255, when reading we must skip the next byte when a byte is 255. An exception is when the byte after 255 is 217, because then we have reached the pair (255, 217), which is the marker EOI (end of image), and then the file must be closed and the drawing procedure set to stop (by altering a variable z from 0 to 1 and going to mainloop, the "getmessage" loop of the window). The program for nbit could look like this:

procedure nbit;
begin
if s = 8 then
begin
r = r + 1
read(fu, b)
if b = 255 then
begin
r = r + 1
read(fu, b1)
if b1 = 217 then
begin
close(fu)
z = 1
goto mainloop
end
end
c = digit(b)
s = 0
end
s = s + 1
bit = c[s]
end

Finally, the program for function digit(b), giving the digit expression of the byte b. This function is the same as the function of the same name used in the writing procedure, apart from the fact that it now applies only to bytes and that its array of bits go from 1 to 8, so that it can start with zeros:

q = 128
i = 0
while i < 8 do
begin

i = i + 1
j = b div q
b = b - j * q
q = q div 2
digit[i] = j
end
Retrieved from "https://en.wikibooks.org/w/index.php?title=JPEG_-_Idea_and_Practice/Program_for_drawing_a_grey_scale_picture&oldid=2009531"