In four short months, two research mathematicians used their expertise in chaos theory to help develop an algorithm that adds significant value to IBM printers.
In Brief:
The journey from arcane theory to practical products is shorter than one might guess, as Charles Tresser and Chai Wah Wu of IBM's Thomas J. Watson Research Center can attest. The mathematicians, who were merely users of laser printers in February, devised two different algorithms for determining where to place the dots in halftone images created by those printers. By September, IBM had included one of those techniques, developed in collaboration with Gerry Thompson of Watson's image applications group, in the software for its InfoPrint(TM) 4000 and
InfoPrint 60 printers.
Last March, Mathematicians Charles Tresser and Chai Wah Wu at IBM's Thomas J. Watson Research Center were studying chaos and nonlinear dynamics. By July, however, with the collaboration of Gerry Thompson of Watson's image applications group, they were showing off a technique they had invented that sharply improves the quality of halftone, or black-and-white, pictures produced by laser printers.
In four months, they had redefined themselves, morphing from theorists interested mainly in mathematical abstractions to practical inventors with a product that has already been incorporated into IBM printers. The story of that transformation illustrates just how thin the line can be, in our high-tech world, between the thinker and the doer - between knowledge for knowledge's sake and a new idea that can be worth millions of dollars.
When Wu arrived at Watson in the fall of 1996, as a postdoctoral fellow, he and Tresser began studying problems in nonlinear dynamics, or chaos theory, related to noise in the transmission of analog signals (see "Noising Out the Noise"). Eventually, they wandered into a completely different sort of issue: how best to produce halftones from a gray-scale image.
Black, White And Gray
A computer records images in shades of gray - typically 256 gradations between whitest white and darkest black. Each pixel in the digital image is one of those 256 shades. A laser printer, however, works only with black and white. At each point on a piece of paper, it can lay down a tiny dot of black toner or leave the spot blank. By interspersing dots and open area, in the process known as halftoning, it can create what appear to the eye as shades of gray. The more black dots, the darker the gray seems; the fewer dots, the lighter it appears.
Determining how to place the dots to transform a gray-scale image into a halftone that nearly matches it is not an easy task. One common approach, known as error diffusion, works roughly like this: one begins in the upper left-hand corner of the screen and examines the first pixel. Suppose it is dark gray - 0.7 on a scale of 0 (white) to 1 (black), say. Then one would put a black dot in its place. But that creates an "error," since the dot should have a value of 0.7. That error is taken into account when considering the next pixel. Printing that next pixel creates its own error, which carries over to the next pixel, and so on.
The upshot is that the printer decides whether or not to print a black dot at a certain position not just on the basis of how dark the original image is at that point, but also according to the errors introduced by the nearby dots. The quality of the halftone images produced by a laser printer in this way depends upon the algorithm, or mathematical formula, that the printer uses to position its dots.
The Error Of Their Ways
In March, after about a month of generalizing their work on nonlinear dynamics, Tresser and Wu came up with an error-diffusion algorithm much better than any that existed and looked for people within IBM to help them implement it in a product. Eventually, they found Howard Sachar, senior manager of the image applications group at Watson, and group member Gerry Thompson, who had worked on several projects with IBM's printer division in Boulder, Colorado. "Tresser and Wu called Howard and said: 'We have an error-diffusion algorithm that's the best,'" recalls Thompson. But the printer group pointed out that, rather than error diffusion, IBM printers use the other main halftoning technique, which employs a so-called dither mask. So, no matter how good the new algorithm was, it couldn't help any of the printers in the IBM line.
However, Thompson continues, "Boulder had this other problem." Because IBM bought its printing engines - the hearts of the printers - from outside suppliers, it needed some way to differentiate its products from those of its competitors. One obvious way was to improve the appearance of the halftones. The printer group at Boulder had tried various strategies without much success; so the word came back: could Tresser, Wu and Thompson help them find a better mask for making halftones?
The two mathematicians knew next to nothing about dither masks. But, encouraged by their success with the error-diffusion algorithm and the welcoming attitude and knowledge of their colleagues in the image applications group and in Boulder, and intrigued by the challenge of finding another way to improve printer quality, they said yes.
Behind The Mask
A mask produces halftones in a very different way from error diffusion. The printer breaks up an image into tiny cells and analyzes it cell by cell to decide where to place the dots. For an image with 600 picture elements, or pels, per inch, one standard cell size is 3 pels high and 6 pels wide - 0.005 inches by 0.01 inches. If the image has the standard 256 levels of gray, then the mask assigns a threshold value between 0 and 255 to each of the 18 pels in the 3-by-6 cell. In one such mask, for example, the upper left-hand pel might be assigned a value of 6; the one beside it, 19; the next one over, 33; and so on, until the pel in the lower right-hand corner is finally assigned a value.
When the printer receives a gray-scale image from a computer, it breaks up the image into thousands of 3-by-6 cells. For each cell, it compares the gray level of each picture element with the threshold value assigned by the mask to that point in the cell. If the gray level of that element is greater than the threshold value, the printer lays down a black dot at that position; if it's not, it doesn't.
Masking works by fooling the eye into seeing a uniform image made up of dots and spaces. The darker the gray a portion of the image is, the larger the percentage of dots that are blackened in the corresponding section of the printed image, which will therefore look darker to the eye. The result is a picture made of up tiny dots that closely mimic the grays of the original image.
The problem with this approach, notes Mike Stanich of IBM's Printing Systems Company, is that the images are "posterized": they offer only a limited number of shades of gray. A 3-by-6 cell offers just 19 gray shades, with zero dots being the lightest and 18 dots the darkest. Thus subtle differences visible in the original image disappear once the mask is applied. For instance, two adjacent parts of an image with gray-scale values of 121 and 131 could appear to be exactly the same shade. The masking can also create sudden jumps in shade where none appear in the original image. A region with a gray-scale value of 131 might appear noticeably lighter than an adjoining region with a value of 132, even though they differ imperceptibly in the original.
Increasing the size of the cell creates more degrees of gray, Stanich notes, but at a cost. As the cell size is increased, he says, "the image looks more dotty to you." With 6-by-12 cells, "you can really see the dots."
An alternative is to keep the same cell size but group the cells into multicell units where each cell has a different set of threshold values: 6, 19, 33, etc., in one cell; 3, 22, 30, etc., in the next cell; and so on. This allows more gray-scale levels without the image becoming dotty. But now, because the multicell units are large enough to be clearly noticeable, another problem appears. "You tend to create tiny patterns with the mask," explains Tresser. "Some grays look good, others are very ugly. Sometimes you seem to see small insectlike artifacts everywhere. It's just extremely unpleasing to the eye."
That problem arises, Wu explains, because laser printers work poorly when printing isolated dots, meaning that the masks must be designed to cluster the dots as much as possible. But certain patterns of clusters will catch the eye and mar the image.
Multicell Masks
Challenged to find a better mask, Thompson, Tresser and Wu set out to find a multicell pattern that would produce none of these annoying artifacts. They developed an algorithm to analyze large multicell masks, ferret out the combinations that could produce artifacts and replace them with more pleasing sets of threshold values. "There are certain kinds of patterns the eye doesn't see," explains Wu. By July, they had presented the team in Boulder with a method for producing multicell masks of almost any size.
Boulder was pleased with the results. "Over time," Stanich says, "we had come up with dozens and dozens of multicell masks ourselves. We condensed those down to the 19 best and did a comparison test [with a mask produced by Thompson, Tresser and Wu's algorithm]. The Research mask was the best." By September, the new mask was available in a new version of IBM's InfoPrint Manager Software, which drives the high-speed InfoPrint 4000 and InfoPrint 60 computers.
Why were two mathematicians with no prior knowledge of printing able to come up with such an improvement when others with more experience could not? "Coming in without preconceived ideas helps," Thompson says. "Maybe we fall into thinking that this has been around so long that we can't improve it. Also, they had the mathematical skills to see the problem and do something about it."
Tresser and Wu plan to keep working on printing problems in collaboration with people in image applications and in Boulder, at least for a while. "We are trying to push the envelope," Wu says. "We'd like to have the print from laser printers as good as from offset printers." Eventually, Tresser adds, they would like to get back to where they started and put their error-diffusion method to work in other areas. Who knows where they might end up next?
Robert Pool is a freelance science writer based in Arlington, Virginia.
Noising Out the Noise
It is one of those ubiquitous aspects of life. Try to send information through the airwaves and the noise will come from other transmissions. It will come from the sun emitting radio waves. It will come from your own radio waves reflecting off surfaces and clouds, generating delayed versions of your own signals; and noise will even be added by your transmitter. Noise is everywhere and it makes the efficient transmission of information an exercise in learning how to deal with noise.
Now, two IBM scientists may have figured out a way to beat the problem of noise, by adding more noise, and in particular, a kind of chaotic noise. Charles Tresser and Chai Wah Wu, both in the mathematical sciences department at the Thomas J. Watson Research Center, have developed a method to send analog signals by adding a kind of chaotic noise at the transmitter and then efficiently removing all noise at the receiver, allowing the original message itself to be received with little degradation.
Analog and Digital
The old-fashioned way of transmitting information is to send an analog signal, where the message is encoded as a continuous function changing with time. The signal itself can be blurred by the noise in the world through which it travels, and what's lost in that interference is very difficult to recover precisely. In digital signals, that continuous flow of information is represented by a sequence of zeros and ones. "The loss here," says Tresser, "is that you have less information in your signal, but the big advantage is that, even if the signal is distorted, you have a better chance to recognize it when it arrives."
To maximize that recovery, error-correcting codes are employed, which add robustness to the signal. Imagine taking blocks of your message and enfolding it in a longer sequence of zeros and ones. When that sequence arrives at the receiver, the longer sequence is easily recognized and decoded, leaving the message itself. But to do so, you have to know when the signals start and when they end, which is a problem of synchronization.
The Pros and Cons of Chaos
Chaotic systems are complex, apparently random systems that are actually deterministic in the sense that they can be modeled mathematically by a small number of equations. The good news with chaotic signals is that they have power in many frequencies simultaneously. If you put your information in many frequencies at a time, which you can do with a signal that is chaotic, then there are likely to be some frequencies whose information content escapes the effect of the noise in the transmission and from which the information can be recovered at the receiving end. The bad news is that chaotic signals suffer from a phenomenon known as sensitivity to initial conditions, which is why communications experts have shied away from using them in the past.
The Solution
In 1990, Louis Pecora and Thomas Carroll, physicists at the Naval Research Laboratory, published a method to synchronize several kinds of chaotic systems. Subsequently, Kevin Cuomo and Alan Oppenheim at the Massachusetts Institute of Technology began applying such "chaotic synchronization" to communication. But so far, no one had succeeded in using chaotic synchronization in realistic noise environments. "Our breakthrough," says Tresser, "lies in a deeper understanding of the mathematics of chaotic synchronization coupled with a way to implement the mathematics in real circuits." By doing so, the researchers have come up with a method whereby the transmitting circuit "forces" the receiving circuit, and the two end up with synchronized signals.
In chaotic synchronization, forcing is accomplished by sending a well-chosen mathematical quantity that depends on the evolution of the full system. "If this quantity is chosen properly," says Tresser, "you can put it in the receiving system and force it to behave in exactly the same way as in the transmitting one." What is lost in noisy transmissions may prevent synchronization. The new chaotic synchronization method, in conjunction with error-correcting codes, allows one to overcome noise and other disturbances associated with wireless communication channels.
Speed and Power
Because they are using analog circuits, which are simpler than digital ones, Tresser and Wu believe they might be able to get performance close to that of digital transmissions but at a much higher speed than existing technologies and with considerably less power expenditure. Moreover, although their method is basically analog, it is sufficiently digital to allow for the use of error-correcting codes.
That, in turn, extends the usefulness of mobile communications devices, which rely on batteries for power and thus need to keep power usage as low as possible. "We expect many applications here," says Wu, "ranging from pagers and personal digital assistants to cellular phones and more."
Gary Taubes is a science writer based in Boston,
Massachusetts.
