Error Diffusion Using Linear Pixel Shuffling

Peter G. Anderson
Department of Computer Science
Rochester Institute of Technology


Linear pixel shuffling error diffusion is a digital halftoning algorithm that combines the linear pixel shuffling (LPS) order of visiting pixels in an image with diffusion of quantization errors in all directions.

LPS uses a simple linear rule to produce a pixel ordering giving a smooth, uniform probing of the image. This paper elucidates that algorithm.

Like the Floyd-Steinberg algorithm, LPS error diffusion enhances edges and retains high-frequency image information. LPS error diffusion avoids some of the artifacts (``worms,'' ``tears,'' and ``checkerboarding'') often associated with the Floyd-Steinberg algorithm. LPS error diffusion requires the entire image be available in memory; the Floyd-Steinberg algorithm requires storage proportional only to a single scan line.

The full paper is available in postscript and html.


Peter G. Anderson, Ph.D., is a Computer Science Professor at RIT. His teaching assignments are in the areas of Neural Networks, Genetic Algorithms, Computer Graphics, and Computing Theory. He is the coordinator of the C.S. M.S. program, and runs the M.S. Projects-Theses seminar. Peter is one of the external faculty members in RIT's Center for Imaging Science. He is actively pursuing research in digital halftoning and character recognition.

Before joining RIT in 1980, he held academic positions at Seton Hall University, the New Jersey Institute of Technology, and Princeton University. He worked for RCA's Computer Division in its Spectra/70 years. Since re-joining academia in 1971, he has been an active consultant at the RIT Research Corporation, Kodak, Xerox, and RCA. His degrees are in Mathematics (Algebraic Topology) from MIT. Because of these math roots, Peter has developed his theory of Linear Pixel Shuffling and applied it to everything.

Colloquia Series page.