IMAGE MATHEMATICS

Victor Duvanenko

Computer scientists and users have been jealous of photographers, movie makers, and television producers for some years because computer monochrome images, or even ones with 256 colors, just didn't compare with photographic-quality (true color) images. Consequently, computer users have been forced to use cartoon-like animation and imaging. This may have been sufficient for adventure games, spreadsheets, and low-end word-processing programs, but it just wasn't good enough for image processing and photography. In short, without true color capabilities, the dream of advanced applications, such as on-line encyclopedias that provide images and movie clips, will never materialize.

In this article I'll discuss some basic functions of image processing and demonstrate one possible implementation of arithmetic functions through logical operations. Then I will use these arithmetic functions to combine and enhance images.

When we use a camera to take a picture, the light reflected from an object passes through a reducing lens and exposes the film. We take this film to a photo lab which, using a series of chemical processing steps, develops the film. Next, photographic paper is exposed by shining light through the developed film and an enlarging lens. Chemical processing is then used again to develop the photograph.

In the electronic version of photography, we can use an electronic "camera" connected to image-capture (frame grabber) hardware to take a picture, and we can use a color printer to get a paper copy of the picture. In this process, the electronic camera serves as a reducing lens and organizes the light intensity and color information, reflected from an object, into a serial stream. The image capture hardware converts this stream into numbers, which are then stored in the computer's memory. A monitor or a printer serves as an enlarging lens, and some form of magnetic memory medium, such as disk or tape, is used to store the captured image for later recall.

But a computer is much more than a mere storage medium. It can also be used as a processing lab because, once an image has been captured and stored as numbers, that image can be enhanced or changed using mathematical manipulations to achieve some of the same tricks of the trade photographers have used for years. These techniques include the use of filters to get rid of glare, create special effects, or enrich certain colors. Other techniques include the use of black and white to create a mood, the use of zoom lenses to capture only the interesting sections of images, and the use of double exposure to superimpose several images. What's significant is that each of these techniques can be accomplished mathematically, rather than chemically.

Graphics and image manipulations have traditionally been limited to logical (Boolean) operations -- XOR, NOT, OR, AND, and so on -- mostly because of inexperience, simplicity, and the dominance of monochrome hardware. Because our goal is to modify an image or combine two images, we must understand fully how picture elements (pixels) can be manipulated or combined. The simplest case is monochrome graphics, 1 bit per pixel, where 1 bit in memory corresponds to 1 dot on the screen.

  X  Y     Output
  ------------------

  0  0   output [0]
  0  1   output [1]
  1  0   output [2]
  1  1   output [3]

  --------------------------------------------------------
  |X  Y | 0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F |
  |------------------------------------------------------|
  |     |                                                |
  |0  0 | 0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1 |
  |0  1 | 0  0  1  1  0  0  1  1  0  0  1  1  0  0  1  1 |
  |1  0 | 0  0  0  0  1  1  1  1  0  0  0  0  1  1  1  1 |
  |1  1 | 0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1 |
  -------------------------------------------------------
          G  N     N     N  X  N  A  X (Y)   (X)    O  P
          R  O     O     O  O  A  N  N              R  O
          O  R     T     T  R  N  D  O                 W
          U       (X)   (Y)    D     R                 E
          N                                            R
          D

Many graphics software packages allow programmers to set a "logical operation attribute" and then draw in that mode. This means that in XOR mode, as a white line is drawn over an image, all the bits along the path of that line are reversed. This is a useful technique for cursors and is used in many CAD packages.

In the monochrome world, we can emulate arithmetic operations with logic operations. If you look at the AND operation you can quickly recognize a multiply, and the OR is an add with saturate (explained later). At 1 bit per pixel, logical operations do the job perfectly. For larger pixel depths (multiple bits per pixel), however, logical operations can no longer serve as substitutes for actual arithmetic operations.

Arithmetic operations on two operands have a nasty habit of producing a result of length unequal to the length of either operand. Maybe that is the reason why we make a distinction between logical and arithmetic operations. In the case of addition, if the first operand is N bits long and the second is M bits long, the result can be up to (max(N, M) + 1) bits. For example, when we add the binary numbers 1 and 1 the result is 10. In other words, for addition we may require one more bit than the longest of the two operands to store the result. Some textbooks call the generation of this extra bit a "carryout" or an overflow condition. Multiplication is even worse -- we require up to (N + M) bits to store the result. For example, multiplying binary 11 (decimal 3) by 11 (3) results in 1001 (9), which requires 4 bits of storage.

By this time you are probably wondering why we are going through this nonsense. Well, the reason is, if we add two pixels that are each 8 bits long and get a 9-bit result, how do we display this result? If we have only 8-bit numbers, how do we represent a 9-bit number?

The fact that the result uses more bits than either of the operands is irritating even in microprocessors. It is not pleasant to get a 33-bit result when adding two 32-bit numbers. How do you put the result back into a 32-bit register? Most microprocessors don't have a "crowbar" instruction. And how do you deal with the result of multiplication?

The microprocessor world has come up with a simple solution -- let the software deal with it! So most microprocessors just inform the software that an overflow condition has occurred by raising a flag. The software must then look at the flag and do something about the overflow. In the case of multiplication, the microprocessor simply stores the result in two registers and, once again, leaves it to the software to figure out how to fit the result, which now occupies twice as many bits, into a single register.

Most programmers don't concern themselves with overflow conditions. If they have even a small inkling that a data type might encounter an overflow condition, they simply go to the next larger data type. For example, if there was a possibility that an array would grow beyond 64K elements, a long (32-bit) data type would simply be used for the array index. The only reasonable aid that most high-level-language compilers give us is that if two operands of different size are being combined, the result is of the larger size. (I hope this is sufficient warning to computer scientists to make sure that results don't overflow.)

But what are graphics programmers to do when they've got only a single data type that we'll call pixel. They have no other data types to fall back on. The result must fit into the pixel data type, and the resulting display must make sense (the greens are not allowed to spill over into the reds and so on).

The solution is actually quite simple. We represent all pixels that take more bits to represent than the pixel data type can hold by the largest number that a pixel data type will hold. For example, suppose we have a 24-bit-per-pixel system in which three primary colors (red, green, and blue) are used to make up each pixel, and we use 8 bits for red, 8 bits for green, and 8 bits for blue. Any intensities of blue that take more than 8 bits to represent are represented by the largest value that does fit into 8 bits (255 decimal). In other words, when adding two pixels, if the blues are added together and the result is greater than 255, then the result is forced to be equal to 255. Some books call this technique saturation. The key point is that the resultant color is always brighter (or of equal brightness) than either of the operand pixels. If saturation isn't used, it is possible for the resultant pixel to be dimmer than either of the operand pixels -- and this makes no visual sense.

For subtraction, the result is never allowed to go negative. If subtraction of two pixels results in a negative number, the resultant pixel is forced equal to zero. This is called starvation. Thus, the resultant color for subtraction is always dimmer (or of equal brightness) than the brightest operand pixel. Multiplication is handled in the same way as addition, and division doesn't cause problems (except for generating a non-integer result).

A Bit Block Transfer, referred to as Bit_blt, is probably the most useful graphical operation. It is used to move a rectangular block of pixels from one position within an image to another position but is really nothing more than a fancy DMA (direct memory access). Bit_blt is a bit trickier than a DMA on two counts, however:

1. DMA treats memory as linear, one-dimensional space and moves contiguous memory regions. Bit_blt treats memory as a two-dimensional array and moves an arbitrary-size rectangle from one spot to another.

2. DMA always treats memory as a linear array of bytes, words, or other byte-divisible elements. Bit_blt treats memory as a two-dimensional array of pixels, usually of 1, 2, 4, 8, 16, 24, 32, or even 48 bits in size. This implies that Bit_blt handles boundary conditions very carefully, as it may need to modify a part of a byte or a word because several pixels may fit into a byte or a word.

Bit_blt is used extensively for scrolling and windowing because it is efficient at handling rectangular regions of pixels.

After a while, merely moving pixels from one place in the image to another becomes dreadfully boring. So, graphics programmers decided to make Bit_blt perform logical operations as it moves pixels of a rectangular area. For example, an XOR Bit_blt would move a rectangular region of pixels from one location, called the source, to another, called the destination. As it moves each pixel, Bit_blt would read both the source and the destination pixel and combine every bit of the two pixels using an XOR logical operation. The result would be placed in the destination pixel. This would be done on all pixels of the source and destination rectangle. Obviously, the source and the destination have to be of the same size for this to work properly. In any case, with an XOR logical operation, the result is more exhilarating than a mere movement of a rectangular region.

Because a Bit_blt operation is a popular way of manipulating bit-map graphics, many graphics processors and coprocessors handle it with great efficiency, moving pixels at rates of millions per second. But, because most graphics programmers are satisfied with logical operations, most devices limit their repertoire to logical operations only.

Being able to manipulate images with only logical operations is fine for windowing and scrolling but is not enough for image processing and photography. Somehow, we must get from logical operations to arithmetic operations.

Now that we have these functions, how can we use them to perform simple image-processing and photography tasks? Simple! By adding two images together, with saturation, a double exposure effect is created. Another technique might be to make color adjustments by setting the second image to a constant color and then adding or subtracting it to/from the first image. You can create the effect of underexposure by subtracting some constant value from all reds, greens, and blues, which will make an image appear darker or underexposed. For overexposure, just add a constant value.

Subtraction of two images can be useful for data compression. For example, when compressing a movie, frame-to-frame differences are quite small most of the time. Thus, if you compress only the differences between the frames, you will avoid compressing the data that has not changed. Of course, you can do just about anything by directly manipulating the image in the graphics memory (bit map).

By now you are probably wondering why we are going through so much pain. The reason is performance! Because Bit_blt with logical operations is available, why not use it? All we have to do is combine several Bit_blts with different logic operations to give us an arithmetic function. Of course, we could also write our own Bit_blt routine that would perform arithmetic. But, you shall see that this is not as efficient, even when using a 20-MHz 80386.

I used a 20-MHz 80386 IDR PC AT for software development and benchmarking. I also used Digihurst image-capture and display-board, along with a Sony Multiscan monitor. The Digihurst board is a true color (24 bits/pixel) graphics board capable of image capture from an NTSC source (TV). You can hook it up to a VCR, watch a movie on the monitor, and capture any frame. This board uses three Intel 82786 graphics coprocessors, one for each primary color. The board also has 3 Mbytes of graphics memory -- 1 Mbyte for each color -- and is capable of storing three full images. After the images have been captured, they can be stored on disk.

                       80386      82786     Ratio
  ------------------------------------------------

  Addition             10.7 sec.  4.4 sec.  2.4:1
  Subtraction          10.7 sec.  4.4 sec.  2.4:1
  Addition             12.7 sec.  5.5 sec.  2.3:1
    (with saturation)
  Subtraction          12.7 sec.  5.5 sec.  2.3:1
    (with starvation)

The benchmarks, as usual, don't tell the whole story. The 80386 performed poorly mainly because of graphics memory bandwidth limitations. In a PC AT, the graphics board connects to the 80386 through the PC AT bus, which runs at 1OMHz at best and is only 16 bits wide. Thus, the PC AT bus presents a bottleneck to a 20-MHz 80386. The 82786 accesses graphics memory directly, without bottlenecks, plus DRAM tricks such as "page mode" accesses are used to improve graphics memory bandwidth even further. The 82786 graphics memory bandwidth peaks at 40 Mbytes/sec.

Using a graphics coprocessor can have many other benefits. Because the graphics coprocessor possesses smarts, it can share the processing load. The key here is parallelism. While the graphics coprocessor is performing a task, the CPU can be doing something else in parallel. This is not possible with pure display devices such as VGA, EGA, CGA, and so on, where the CPU must do all the work. This leads me to the conclusion that even if the algorithm runs slower on the coprocessor, it may still be advantageous to use the coprocessor for that task because of parallelism.

In any case, the algorithm discussed here used logical operations to perform simple arithmetic functions that can be used to add and subtract images with and without saturation. The performance of these functions executed by graphics coprocessors was dramatically superior to that of the CPU.

All source code for articles in this issue is available on a single disk. To order, send $14.95 (Calif. residents add sales tax) to Dr. Dobb's Journal, 501 Galveston Dr., Redwood City, CA 94063; or call 800-356-2002 (from inside Calif.) or 800-533-4372 (from outside Calif.). Please specify the issue number and format (MS-DOS, Macintosh, Kaypro).

Intel Corp., Intel 82786 Graphics Coprocessor User's Manual. 1987.

Kohavi, Zvi. Switching and Finite Automata Theory. New York: McGraw-Hill, 1978: 138 - 144.

McCluskey, Edward J. Logic Design Principles. Englewood Cliffs, N.J.: Prentice-Hall, 1986.

How Things Work, Volume I. New York: Simon & Schuster: 202 - 203.

_IMAGE MATHEMATICS_ by Victor Duvanenko

Copyright © 1989, Dr. Dobb's Journal