Patterns and Pictures
Copyright (c) Susan Laflin. August 1999.
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.
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 2and so on. Since there are usually several adjacent pixels with the same value as you search along the scan line, this method of coding saves space overall. For a chequerboard pattern changing colour at every pixel, this method would actually use more storage than the array, but such a pattern occurs very very rarely in practice. There are many ways of storing the numbers to give this encoding, but the underlying idea is the same. The following simple example gives a good idea of this method.
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 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
Do attempt to decode at least some of this picture. When you are sure you can understand this method of run-length coding, you may look at the solution to check that you have the right idea.
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. The figure shows a screen and its corresponding quad tree for a very simple example using two colours.
Simple Quad-Tree
In a real case, the tree would be very much larger and go to much lower levels. For an array of 1024 x 1024 pixels, to go to the level where individual pixels were of different colours would require 10 levels.
1st division into 4 gives squares 512 x 512.Again there are a wide variety of methods of storing the tree structure within the program and the order in which the quadrants are numbered may vary in different software packages. 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 or A A W A
A W
112 --- A A or A A W W
W W
113 --- A W or A W W A
A W
W
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
Once again I urge you to try and decode at least some of this image before looking at the solution to check your work.
These are all fairly crude pictures, with low-resolution and a limited number of colours, so you can imagine the amount of data required to code a colour photograph, even using compression techniques.
