SEM540b. Graphics and HCI
Class Exercise for Week 2. Compression Techniques.
Since an array of 1024 x 1024 for each screenful of graphic
data involves very large amounts of storage, much thought and ingenuity has
gone into methods of compressing the data for long term storage or transmission
between installations. The methods used vary greatly in their details but are
basically of two main types.
Run-length Coding
This stores the information, scan line by scan line down the screen. Instead
of having a value for each pixel, it codes the information in the form
pixels 0 to 20 have value 0
pixels 21 to 25 have value 6
pixels 26 to 80 have value 2
and so on. Assume that the letter w stands for the colour white, p for purple,
o for orange, y for yellow, g for green, r for red, b for brown and a for
azure (instead of blue since b has already been assigned. In the same way,
black would have to be represented by s for sable). Then each row, starting
from the top of the picture and moving from left to right, is coded as the
number of pixels followed by the letter denoting the colour. See what you
get for the following 32x32 picture.
Row 1: 32w (top of page) Row 2: 24w 3p 5w Row 3: 5w 4r 8w 2o 4w 5p 4w Row 4: 4w 6r 6w 4o 2w 7p 3w Row 5: 3w 3r 1y 3r 5w 6o 1w 3p 1y 3p 3w Row 6: 4w 6r 1g 3w 3o 2y 2o 1w 7p 3w Row 7: 5w 5r 2g 2w 7o 1w 2g 4p 4w Row 8: 7w 2r 2w 2g 2w 5o 2w 2g 3p 5w Row 9: 12w 1g 3w 1g 2o 2w 1g 10w Row 10: 12w 1g 2w 2g 3w 1g 11w Row 11: 12w 1g 1w 2g 3w 1g 12w Row 12: 12w 1g 1w 1g 3w 1g 3w 2g 8w Row 13: 8w 3g 1w 1g 1w 1g 2w 11g 4w Row 14: 7w 2g 1w 1g 1w 1g 1w 1g 1w 2g 1w 10g 3w Row 15: 7w 2g 2w 2g 1w 2g 1w 1g 3w 9g 2w Row 16: 6w 3g 1w 10b 5w 6g 1w Row 17: 6w 3g 2w 8b 9w 4g Row 18: 5w 4g 3w 6b 14w Row 19: 5w 3g 4w 6b 14w Row 20: 4w 4g 4w 6b 14w Row 21: 4w 4g 3w 8b 13w Row 22: 4w 3g 3w 10b 12w Row 23: 3w 4g 2w 12b 11w Row 24: 3w 3g 2w 14b 10w Row 25: 3w 2g 3w 14b 10w Row 26: 8w 14b 10w Row 27: 8w 14b 10w Row 28: 8w 14b 10w Row 29: 9w 12b 11w Row 30: 10a 10b 12a Row 31: 11a 8b 13a Row 32: 10a 10b 12a
Quad-trees
This stores information in the form of a tree structure and each level has
either a node pointing to lower levels or a leaf indicating the value of
all pixels in the square area of the screen. Consider a simple example
in which the quadrants are numbered in a clockwise direction from the top
left-hand corner and build up a 16x16 square picture. Again the letters
for the different colours are as described in the previous section.
1 --- 11 --- 111 --- A A W A
112 --- A A W W
W
114 --- A W W A
12 --- A
A
123 --- A A W W
W
13 --- W
W
133 --- W W W A
W
14 = A
2 --- 21 = A
22 = A
23 = A
24 --- W
A
243 --- W A A W
244 --- W W W A
3 --- 31 --- A
312 --- R A A R
S
S
32 --- A
A
323 --- S A A A
S
33 --- 331 --- S G G G
G
G
G
34 --- S S G G
4 --- 41 --- A A S A
42 --- A
422 --- A R R A
S
S
43 --- S S G G
44 --- G S G G
Note: Solutions to these examples may be found below.
Please do try and solve them yourself before looking at the solution.
Run-length-coding
Quad tree encoding