Pixel averaging smooths graphics effects.

Pixel averaging smooths graphics effects. David Cook.

Pixel Averaging Smooths Graphics Effects

Have you ever looked at NASA's computer enhanced space photographs or any of the computer graphic effects on television and said to yourself, "Someday, I'll own a system with that much resolution'? Have you ever wondered how they achieve such smooth graphic effects?

Chances are, if you already own a computer capable of color or black and white shaded graphics, you can produce smooth graphics and effects without high-resolution and at relatively low cost.

Background

Digital Image Corporation of Grand Rapids, MI was founded in 1981 to create computer graphics and a computer graphics system for advertising, slide shows, TV, and other media presentations. One of our goals has been to design a system which produces very clean, low cost graphics.

One of the problems we encountered has been resolution. For example, 35mm slide film has a resolution of about 4000 lines, while few inexpensive computers offer more than 512 lines. A second problem is the fact that 35mm slides are usually projected onto a large screen, increasing the resolution problem.

At Digital Image, we have designed software which produces very clean, full color graphics without matching the 4000 line film resolution requirement. This article attempts to explain just one of the many methods we employ to achieve even graphics.

The ideas presented here should give you a good start. Some of our techniques are not new. However, the ways in which we use some of them are completely new and have provided a great deal of insight into the secrets of computer graphics.

Our computer system includes: a Cromemco Z-2D System Two (Z80 CPU, 64K); Two 5 floppy disks (386K each); Cromemco SDI graphics board; Two 48K image memory planes; a Houston Instruments bitpad; a Via Video digitizer; an Aydin Controls RGB monitor (Mitsubishi in disguise); and a matrix camera (produces 35mm slide from RGB signal from computer).

Resolution in the system is 378 x 241 in lo-res mode (16 colors out of 4096) and 756 x 482 in hi-res mode (two colors out of 4096).

The Basic Algorithm

Though everyone reading this article who currently owns a computer with graphics capabilities will benefit from these techniques, the basic algorithm is geared to computers with a color or black-to-white shaded map display, such as Atari, Cromemco, and Cromatics. The basic algorithm, and the one from which all other techniques described in this article are derived is called pixel averaging.

In pixel averaging for any given pixel on the screen, an average can be calculated by adding the values of all neighboring pixels and then dividing by the number of neighbors and plotting the result. For ecample, below we see a pixel (center pixel with a color map value of 2 surrounded by pixels of different map values:

3 4 15

7 2 10 (2 is the center pixel)

1 9 5

In calculating the average of the center pixel:

P" = (P1 + P2 + P3 + P4 + P5 + P6 + P7 + P8)/8

P" = (3 + 4 + 15 + 7 + 10 + 1 + 9 +5)/8

P" = 6 (drop the fraction)

To apply this algorithm correctly, scan the area containing the image and apply the algorithm to each pixel within that area. The result from each calculation may be immediately plotted back onto the display over the original pixel. However, much cleaner results are obtained if the averaged information is plotted somewhere other than on top of the original image-- another image plane, disk, core, or even somewhere else on the same image plane.

If the results are plotted over the original, you will obtain a similar result, with a slowly accumulating degree of error. The error occurs because the pixel you just changed is a neighbor to pixels you are about to change. If you plot the new pixel on top of the old pixel, you will be changing future results for the neighboring pixels. (Later on however, I will explain how plotting the new pixel over the old one can be useful).

Once an image has been averaged, the color map must be adjusted to provide the smoothest display possible. This is probably the most important and difficult (depending on your hardware) step in pixel averaging.

To explain how to arrange the color map, let me describe the way it is done on our system and then offer examples to make it work on other systems.

On the Cromemco, in low resolution mode (378 X 241) up to 16 colors out of a possible 4096 may exist on the screen at the same time. The colors are numbered 0-15, the actual numbers written when a pixel is placed on the screen, and thus the actual numbers being averaged.

Each color number (0-15) on the Cromemco may be assigned a red, green and blue gun value between 0 and 15. This allows any color (0-15) to be any one of the 4096 colors available (16 X 16 X 16). The map must be arranged so that the lower the color number, the darker the color. Therefore, if I want my image to glow a smooth blue, I shade my color map as shown in Table 1.

In effect what averaging together with proper color map manipulation does, is take a particular neighborhood and modify the color of the center pixel to make it "more like' its neighbors. If half of the neighbors of a center pixel are zeros (0) and half are fifteens (15), the center pixel will become a seven (7).

As the neighborhood moves through the area containing the image, each of the center pixels becomes more like the neighbors. (Remember, all neighbors get a chance to become center pixels.) This has the effect of fuzzing the image, or making it glow. Therefore, if the map is shaded from dark to light, the image will appear smooth.

This method should work on machines such as the Atari, but users of machines with fixed color maps such as the Apple and TRS-80 will find it more difficult to obtain smooth images. For these machines, assign a lookup table of colors arranged so the darkest color value is first and the brightest color last. When you read a pixel from the screen, average the index to the color in the table, not the actual color value. When writing the new pixel out, write the color at the index in the array corresponding to the result from the calculation. This method will pseudo-shade on fixed map machines. To understand this method better, try the following example:

Let us imagine that your computer only has the following eight colors:

0 = Black

1 = White

2 = Light blue

3 = Red

4 = Dark blue

5 = Yellow

6 = Dark green

7 = Dark purple

You would create an array, arranging the colors from darkest to lightest (you may have to experiment to see what order works best as follows:

(1) = 0 (Black)

(2) = 7 (Dark purple)

(3) = 6 (Dark green)

(4) = 4 (Dark blue)

(5) = 3 (Red)

(6) = 5 (Yellow)

(7) = 2 (Light blue)

(8) = 1 (White)

Let us then imagine that in reading a neighborhood, you find the following colors:

0 1 2

0 7 5

6 0 4

Before (or during) averaging, convert the colors using the table. The results will be:

1 8 7

1 2 6

3 1 4

At this point, the lower the number, the darker the color. The higher the number, the brighter the color.

Now average all pixels except the center pixel:

(1 + 8 + 7 + 1 + 6 + 3 + 1 + 4)/8

The result is 3. Now determine which pixel is to be plotted:

NEW PIXEL = ARRAY (RESULT)

NEW PIXEL = ARRAY (3)

NEW PIXEL = 6

It is very important to note that when doing pixel averaging, the smoothest results are obtained if the background is black. Bright backgrounds cause jaggies, so keep the background to the darker colors if not completely black.

You may be wondering why we don't average the center pixel. The reason for this is that our routines are in assembly language which makes dividing by 8 much faster than dividing by 9. The center pixel does not weight the algorithm too much, but if you do decide to include it, make sure to divide by 9, not 8.

Uses Of Pixel Averaging

I call the type of pixel averaging mentioned above Replace Averaging as the result is replaced directly on the screen. Replace averaging is best used for one of the following functions:

Clean noise from a digitized image. Replace averaging reduces (by averaging) all noise inherent in digitizing. Continued averaging will slowly reduce all random grey scale elements, causing the digitized image to appear computed as opposed to digitized.

Clean up jagged lines in computed drawings. Replace averaging only once on a line drawing (or solid shape) has the effect of blurring all borders and edges. This reduces the jagged edges inherent in low resolution drawings. Continued pixel averaging causes the image to glow more and to become less jagged with every pass. You will obtain cleaner graphics if before averaging, every color except background in he image is converted to the lightest color. This places the entire image at the top of the color map with the background at the bottom. Averaging at this point slowly and smoothly pulls the color of the outer edges of the image toward the color of the background.

Variations On A Theme

Once you understand basic Replace averaging, variations are simple to implement. From here on we will deal with very simple variations on Replace averaging which provide many different results. Some of these variations are dependent on the color map being shaded, others are not. Therefore, some of them will be useful to anyone who has a computer with graphics capabilities whether it has color or color maps or not.

Edge Detection

Sometimes it is useful to be able to detect just the edges (boundaries between colors or grey shades) of images. Uses range from art, to being able to detect, identify and track a fast moving missile via computer (and I don't mean video games).

Normally, edge detection is accomplished by taking a copy of the image, shifting the copy one pixel up and one pixel to the right and then xoring the copy back over the original. This method leaves most edges with the exception of corners and overlapping lines.

A much faster and smoother algorithm is one I call Subtract averaging. Subtract averaging is identical to Replace averaging with the exception that when the result is obtained from averaging the neighbors, it is subtracted from the original center pixel before being plotted to another page or area on the screen.

Note that you must plot the result somewhere other than on top of the original image or the effect you get will not be edge detection.

If Subtract averaging is handled properly, what you should end up with is an image consisting of only borders and edges from the original image. Xoring the result and the original center pixel (Xor averaging) instead of subtracting also performs edge detection with the exception that the detected edge is not quite as clean as it is with Subtract averaging.

The following is an example showing exactly where the subtract should appear (this holds true for all other types of fuzzing mentioned below):

P = Color assignment of original center pixel before averaging

P1 = Color assignment of new center pixel after averaging but before plotting.

Before plotting the pixel, perform this calculation:

P2 = P1 - P

And plot P2.

Edge detection is best to use on solid shapes or digitized images. If you are using it on a digitized image, it may help to reduce the noise in the picture first by Replace averaging the image before Subtract averaging. Remember, all noise in an image will show up as edges during edge detection.

Texture And Pattern Generation

Other forms of pixel averaging fit themselves to unusual forms of texture and pattern generation. Two good examples of this are Subtract and Xor averaging on top of the existing image. If the user Subtract averages twice in succession, replacing each pixel on top of the original, and then applies a grey scale to the image, the image will appear pitted and very three diemensional (much like the surface of the moon). The image can then be Replace averaged to make the features blend in and soften the image.

Xor averaging on top of the existing image also causes unusual patterns to appear. Xor averaging again does not cause the picture to revert back to normal but instead modifies it further.

Intensity Modifications

And averaging on top of the original image causes only the brightest shades to remain and all darker shades to be lowered in intensity. This also provides more depth (encoded via shade) to an image and is useful in intensity control.

Color Map Wraparound

Add averaging on top of the original image or to another area of memory causes the shades to begin to wrap around the color map. This effect causes bright shades to become darker and darker shades to become lighter. It differs from simply inverting the color map (or the image) by keeping the association between the color scales the same.

High Lighting

A very useful feature is Or averaging to another area of memory. If applied to a computed image (words or shapes) it causes highlights (brightest color map values) to be added to edges and corners making the image appear to gleam as if from reflected light.

If several Or averages follow each other on the same image (each time reverting to another place), and the final result is Replace averaged, the very brightest highlights will be reduced to stars.

Conclusion

While there are many other techniques which must be employed to obtain the smoothest graphics possible, pixel averaging and all of its variations provide a good stepping stone into the world of smooth graphics. The following is a list of ideas to try once your have forms of pixel averaging working:

This
remember
becaome2.
formula
graphicimagefrom

In conclusion, the basic ideas presented in this article do not deal as much with pixel averaging as they deal with modifying a basic algorithm over and over again to provide new and diversified effects. In graphics where memory is a consideration, if the same routine can be used in many different effects, the routine becomes a valuable tool and a basis for the design of other routines using the same concepts.

Table:

Table: Listing 1.

Photo: Figure 1. This photo was made by taking the word CREATIVE COMPUTING, and Replace averaging it to the alternate page. After each average, all colors are converted to 15 (the brightest) and the result is again averaged. This is done in order to make the glow appear larger then the actual wording. After the desired glow size is obtained, the words CREATIVE COMPUTING were copied over the glow and then Xor copied, leaving the inside black. Then the outline of the word was copied into the glow using color 15 which was converted to orange while the glow was shaded between black and red.

Photo: Figure 2. This photo was made by taking the word GLOW and Replace averaging it to the alternate page until the desired glow was obtained; this became the first exposure (in cyan). The second and third exposures were obtained by taking a sphere, inverting it (via Xor) and fuzzing it until the desired glow was obtained. These were then shot in red and green respectively.

Photo: Figure 3. This photo was made by taking a sphere, inverting it, Replace averaging it, and shading it between black and yellow. This became exposure one. The second exposure was created by taking the inside of the sphere and keying it onto the rest of the frame on color zero (background) which has the effect of placing the image behind the center sphere. This image was them shaded from black to red and then from red to blue and shot. Notice the outside edge of the center sphere is not smooth. This is because the outside edge does not sit next to a complementary color, thus jagged edges show up.

Photo: Figure 4. This photo was created by taking three different versions of the background created in Figure 3 and shooting the first shaded between black and red, the second shaded between black and green, and the third shaded between black and blue. This causes much color interference on film which shows up as beautiful hues. All of the exposures were Replace fuzzed to enhance the interference.

Photo: Figure 5. This photo was created by taking a straight two-dimensional grid, tilting it in the horizontal direction with a skew added (this makes it disappear to a horizon) and then tilting it in the vertical direction (this made the grid curve). The grid was then Replace fuzzed and shot as exposure one, the road. The next exposure was created by digitizing pieces of tissue paper and REPLACE fuzzing them to add softness. These became the clouds. The final exposure was created by taking the same tissue paper used for the clouds and repeatedly Or fuzzing it to create the rock and roadside images.

Photo: Figure 6. This photo was created by taking a two dimensional bar chart, Replace averaging it to the alternate page and tilting it to a horizon. The second and third exposure are composed of the word copy (the first in green, the second in white) and are done in high resolution (756 X 482 X 1 color). Figure 7 is Figure 6 without any averaging to show how averaging smoothed out the jaggies.

Photo: Figure 8. This photo was created by taking various computed images, and manipulating them with Replace, Xor, Or, Subtract, Add and And averaging until they created the earth (notice the thin atmosphere surrounding the earth done with Replace and Add averaging). This became exposure one. The second exposure consisted of the stars which have no averaging. This is a good example of the results obtainable by combining all forms of averaging.

Photo: Figure 9. This is a fun photo, and a good commercial effect. (Note that the text is from the article.) The photo was created by taking the text and Replace fuzzing only words existing outside of the glasses. This became exposure one in low resolution, shaded between black and red. The second exposure was the text existing inside the glasses which was shot white in high resolution. The third exposure was the glasses which were shot cyan in high resolution.

Photo: Figure 10. This photo is an example of our Odd language in action. The first two exposures were the red and green rotating and flipping stars. The last exposure was the center blue star which was Replace averaged.

Photo: Figure 11. This photo is identical to Figure 10 except that all components were Replace averaged.

Photo: Figure 12. This photo was created by taking a high-resolution sphere (the same one used to make the Earth slide) and manipulating it using Subtract, Replace, Or and And averaging until a somewhat smooth image resulted. Replace averaging is responsible for the three-dimensional look.

Photo: Figure 13. This photo is similar to Figure 12 in that the basic image was created in much the same way. However, the shading and three-dimensional look were added by many repeated Replace averages.

Photo: Figure 14. This photo is similar to Figures 12 and 13 in that the basic image was created from a high-resolution sphere. After the initial shape was created, it was And Copied onto bars which had been Or averaged to produce the effect of light shining from an angle. The bars were then And Copied onto another image which placed the dark and light shapes onto the bars. The result was then Replace Copy Averaged onto Replace averaged bars to give the edges a very smooth and three-dimensional look.

Photo: Figures 15 and 16. This photo was created in two steps. The first was to take shaded bars and to Or average them to create the effect of light shining from an angle. The second step was to take a picture of the Wag (Douglas Wagley) and Replace average out some of his facial features. Next, various objects in the background (such as a light switch on the wall) were edited out of the image. Finally, the bars were Copied over Doug and then Xored to erase them.

The bars were then shot as one exposure and Doug as the second exposure.

Photo: Figure 17. This photo was created by taking in a picture via the video camera and tilting it through software. This was then Copied on top of the grids and then Xored to cut the picture out leaving the shadow. The picture was then moved up and Copied back in. Finally the picture was Replace averaged and randomly colored to provide linked shading.

Photo: Figure 18. This photo is the original. No averaging or manipulation was performed on the image. The image is shown as it came into the computer.

Photo: Figure 19. This photo shows Figure 18 Replace averaged on top of itself once. Notice that noise is slightly reduced. Continued averaging would reduce the noise more. Also notice the patchy coloring. This is due to the accumulating error caused by replacing the averaged information on top of the original.

Photo: Figure 20. This photo shows Figure 18 Replace averaged to the alternate page. Notice the noise is reduced and very clean. Continued averaging would reduce the noise more and begin to make the image glow. Notice that no patchy coloring is found as there is no accumulating error.

Photo: Figure 21. This photo shows Figure 18 Xor averaged to the alternate page. The effect performed is basically edge detection with shading added. This effect is almost identical to the results obtained if the image is shifted one pixel up and one pixel to the right and then Xor copied back on top of the original (as discussed in the article). This type of edge detection differs from Subtract averaging to the alternate page in that it is not as clean as Subtract averaging and produces a shaded output.

Photo: Figure 22. This photo shows Figure 18 Xor averaged on top of itself once. This manipulation is useful for introducing patterns into images.

Photo: Figure 23. This photo shows Figure 18 Or averaged to the alternate page. The effect here is to add highlights to edges at angles giving the effect of light shining from an angle (more apparent on computed images than on digitized images).

Photo: Figure 24. This photo shows Figure 18 Or averaged on top of itself once. The effect here is basically identical to Figure 23 with the added accumulating error which is greatly evident. This effect is nice for a "washed out' look.

Photo: Figure 25. This photo shows Figure 18 And averaged to the alternate page. The effect here is basically the opposite of Or averaging to the alternate page. Places where Or would highlight, And will deaden.

Photo: Figure 26. This photo shows Figure 18 And averaged on top of itself once. This is very useful for non-linear intensity reduction. The intensity reduction is non-linear because of the accumulated error. This method may also be used to introduce shadows into an image.

Photo: Figure 27. This photo shows Figure 18 Subtract averaged to the alternate page. The effect here is Edge Detection. Because the image contains so much noise, there are many edges detected. To reduce the number of edges, Replace average first. Figure 32 is an example of Figure 18 which has been Replace averaged before Subtract averaging.

Photo: Figure 28. This photo shows Figure 18 Subtract averaged on top of itself once. This effect is useful in pattern generation and masking.

Photo: Figure 29. This photo shows Figure 18 Subtract averaged on top of itself twice. If Subtract averaging on top of the original is used an even number of times, it produces more and more three-dimensional textures. These textures appear as tiny bumps and valleys with shadows. This is a very good method of producing highaltitude type images of ground features.

Photo: Figure 30. This photo shows Figure 18 Add averaged to the alternate page. The effect here is to wrap the pixels around the color map without adjusting it.

Photo: Figure 31. This photo shows Figure 18 Add averaged on top of itself once. This effect is very beautiful due mostly to the accumulated error. It is a very good effect to combine with other forms of averaging.

Photo: Figure 32. This last photo is an example of Figure 18 Replace averaged to the alternate page to reduce noise, and then Subtract averaged to the altrnate page to edge detect. The detection here is very clean and can be made cleaner by Replace averaging serveral times before Subtract averaging.