Using ‘God’s Fingerprint’ to ID an Image Problem
Like any mathematician, Michael Barnsley adores an orderly world ruled by theorems and formulas, but for years, he kept having the same terrible nightmare. What he saw was a jumble of wires, like an old switchboard gone terribly awry. It was an expression of chaos, not order.
But today, Barnsley is turning a nightmare that haunted him for 20 years into a dream. In that mass of tangled wires he saw a practical use for a new field of mathematics--fractal geometry--that could have a profound impact on everything from the way pictures are sent over the Web to the way advertisers create billboards. The same picture could be used for both applications, without loss of resolution, and it could be sent over the Internet in a tiny fraction of the time now required to transmit visuals.
As Barnsley wrestled with his dream in the late 1970s, another mathematician, Benoit B. Mandelbrot, was laying the foundation for fractal geometry.
A fractal is a geometric shape that is complex and detailed at any level of magnification. A rugged coastline, for example, when seen from space becomes ever more complex as the viewer moves closer. Smooth coastlines become ragged, turning into boulders, then into sand, and finally into subatomic particles.
Mandelbrot called those shapes “fractals,†and he took it a step further. Fractals, he has written, are frequently “self-similar,†meaning that each portion of a fractal can be viewed as a smaller replica of the whole. If you look closely at a fern, for example, you will see the same pattern reproduced at every level. The leaves seem to be made up of miniature ferns, which in turn look like even smaller ferns--repeating the shape of the whole in ever decreasing sizes.
Some call it the “fingerprint of God.â€
Barnsley was working in the same field at the same time, and fractals finally allowed him to analyze the dream that had tormented him for so long. What he was seeing in that mass of wires were, clear and simple, fractals--the same patterns repeated over and over. He was finally able to untangle the wires by analyzing the recurrent patterns.
Barnsley realized he was visualizing something the same way the human eye does. Not by looking at tiny dots of light, called pixels, which is the way computers reproduce images, but by seeing relationships, such as “rotational invariantsâ€--a fancy way of saying that a circle still looks like a circle no matter which angle you view it from. He reduced all that into mathematical formulas, called the “fractal transform.â€
In 1987, Alan Sloan, an English-born mathematics professor at the Georgia Institute of Technology and a colleague, founded Iterated Systems (https://www.iterated.com) in Atlanta to move the discovery from the laboratory to the marketplace.
Barnsley believed then, as he does now, that fractals could revolutionize the world of digital imaging. A few formulas could reproduce a scene while using only a fraction of the memory required for pixel-based computer images. That means images could be sent much more quickly over the Web, and require far less space on a hard drive. And the same image could be used for a postage stamp or a billboard.
“It turns out, and it’s extraordinary, that you can describe almost any real-world image by recording not the thing itself, but its invariants and cross-referencing relationships. That’s the mathematical theorem that lies behind all this stuff. That’s the fractal transform,†Barnsley said.
As he sat in his office, thousands of miles away, Barnsley offered a quick demonstration.
“I’m going to try to make a picture in your mind, but I’m not going to tell you what the picture is,†he said. “The picture is exactly the same if you rotate it. So whatever it is that you have got to see in your mind is the same if you rotate it by any amount. The picture stays the same. So you start trying to generate in your mind’s eye something that is the same if you rotate it.â€
Get the picture? It’s a circle.
“It would have to be a circle,†he shouts into the phone. “It would have to be. There, I’ve done something absolutely extraordinary.â€
He has “sent†a picture without even describing the scene. Instead, he defined its rotational invariant--or its fractal transform.
That “silly†example, as he called it, shows the viability of his concept, and Barnsley has moved to capitalize on his technology. But like any academician, he has found the world of commerce a very different world indeed.
It isn’t easy to find the transforms in an image, and that means it isn’t cheap.
“When we first started doing this in 1989, it used to take hours to compress†an image through its fractal transforms, he said. “We spent many years honing the technology to make it run faster and still give satisfactory results for consumers.â€
But not fast enough for most applications. Digital imaging today is based on pixels, tiny dots of light that work like the grain in a film’s emulsion, and that is a well-established technology. A JPEG image, the most popular format used on the Internet, can be copied by a $200 desktop scanner. There isn’t much need to transmit high-resolution fractal-based images that exceed the performance of the monitors on which they will be viewed.
However, Barnsley’s company did find markets with companies such as Microsoft Corp. and RealNetworks Inc., to name a few. Microsoft’s Encarta CD-ROM uses the system to reproduce 7,000 color photographs. Iterated Systems markets the technology under the name STiNG.
The company is also working on a digital camera based on fractal imaging, but it has run into a problem there as well. Barnsley wanted to remove the data processing from digital cameras, to make the cameras simpler, but that would require the use of a personal computer for the actual processing. The industry, he soon learned, is moving in the opposite direction.
“Cheap cameras are the ones you’ve got to focus on for the consumer market,†he said. And manufacturers want to divorce the camera entirely from the personal computer.
“They want to cut the PC out,†Barnsley said. “They want to connect the camera directly to the printer and have it print the pictures. They want a consumer device that will replace your 35mm camera and you print your own pictures.â€
But, he said, it’s only a matter of time before fractal-based imaging catches on in digital photography. Computer chips are getting faster and faster, and he believes the time it now takes to compress an image into fractal transforms--instead of pixels--will soon be shortened dramatically.
“Processing will continue to accelerate. Chips will get faster. That means you can do more and more computation in a shorter and shorter time, and that means that at the end of the story, fractals have an absolutely central role to play in the handling of images,†he said.
*
Lee Dye can be reached via e-mail at [email protected].
