Square Pixel Inventor Tries to Smooth Things Out

http://www.wired.com/wiredscience/2010/06/smoothing-square-pixels


Russell Kirsch says he’s sorry.

More than 50 years ago, Kirsch took a picture of his infant son and scanned it into a computer. It was the first digital image: a grainy, black-and-white baby picture that literally changed the way we view the world. With it, the smoothness of images captured on film was shattered to bits.

The square pixel became the norm, thanks in part to Kirsch, and the world got a little bit rougher around the edges.

As a scientist at the National Bureau of Standards in the 1950s, Kirsch worked with the only programmable computer in the United States. “The only thing that constrained us was what we imagined,” he says. “So there were a lot of things we thought of doing. One of which was, what would happen if computers could see the world the way we see it?”

Kirsch and his colleagues couldn’t possibly know the answer to that question. Their work laid the foundations for satellite imagery, CT scans, virtual reality and Facebook.

Kirsch made that first digital image using an apparatus that transformed his picture into the binary language of computers, a regular grid of zeros and ones. A mere 176 by 176 pixels, that first image was built from roughly one one-thousandth the information in pictures captured with today’s digital cameras. Back then, the computer’s memory capacity limited the image’s size. But today, bits have become so cheap that a person can walk around with thousands of digital baby photos stored on a pocket-sized device that also makes phone calls, browses the Internet and even takes photos.

Yet science is still grappling with the limits set by the square pixel.

“Squares was the logical thing to do,” Kirsch says. “Of course, the logical thing was not the only possibility … but we used squares. It was something very foolish that everyone in the world has been suffering from ever since.”

Now retired and living in Portland, Oregon, Kirsch recently set out to make amends. Inspired by the mosaic builders of antiquity who constructed scenes of stunning detail with bits of tile, Kirsch has written a program that turns the chunky, clunky squares of a digital image into a smoother picture made of variably shaped pixels.

He applied the program to a more recent picture of his son, now 53 years old, which appears with Kirsch’s analysis in the May/June issue of the Journal of Research of the National Institute of Standards and Technology.

“Finally,” he says, “at my advanced age of 81, I decided that instead of just complaining about what I did, I ought to do something about it.”

Kirsch’s method assesses a square-pixel picture with masks that are 6 by 6 pixels each and looks for the best way to divide this larger pixel cleanly into two areas of the greatest contrast. The program tries two different masks over each area — in one, a seam divides the mask into two rough triangles, and in the other a seam creates two rough rectangles. Each mask is then rotated until the program finds the configuration that splits the 6-by-6 area into sections that contrast the most. Then, similar pixels on either side of the seam are fused.

Kirsch has also used the program to clean up an MRI scan of his head. The program may find a home in the medical community, he says, where it’s standard to feed images such as X-rays into a computer.

Kirsch’s approach addresses a conundrum that the field of computational photography continues to grapple with, says David Brady, head of Duke University’s imaging and spectroscopy program in Durham, N.C.

Images built from pixels can show an incredible amount of detail, Brady says. “It’s fun to talk to kids about this because they don’t know what I’m talking about anymore, but the snow on analog television — a block-based imager can reconstruct that pattern exactly.”

But images taken from real life never look like that, Brady says. Typically, they have several large uniform sections — forehead, red shirt, blue tie. This means there’s a high probability that one pixel in an image will look the same as the pixel next to it. There’s no need to send all those look-alike pixels as single pieces of information; the information that’s really important is where things are different.

“I always joke that it’s like Los Angeles weather,” Brady says. “If you were a weatherman in Los Angeles you would almost always be right if you say tomorrow is going to be the same weather as today. So one thing you can do is say, I’m going to assume the next pixel is like this one. Don’t talk to me, don’t tell me anything about the image, until you get something different. A good weatherman in Los Angeles tells you when a big storm is coming. In an image, that’s an edge. You want to assume smoothness but have a measurement system that’s capable of accurately finding where the edges are.”

Where Kirsch uses masks to accomplish that task, researchers today typically use equations far more complex than his to strike the balance between shedding unnecessary information and keeping detail. Pixels are still the starting point of digital pictures today, but math — wavelet theory in particular — is what converts the pixels into the picture. Wavelet theory takes a small number of measurements and turns them into the best representation of what’s been measured. This best estimation of a picture allows a megapixel image to be stored as mere kilobytes of data.

Images: 1) This baby picture, scanned in 1957, was the first digital image. At 176 by 176 pixels, its size was limited by the memory capacity of the computer./NIST. 2) Before transforming the square-pixel image, a close-up of one ear appears as a blocky stack. The variably shaped pixel treatment turns it back into an ear./NIST.

Read More http://www.wired.com/wiredscience/2010/06/smoothing-square-pixels#ixzz0t6GtseKf