Browse Prior Art Database

ERROR DIFFUSION ARCHITECTURE

IP.com Disclosure Number: IPCOM000027232D
Original Publication Date: 1995-Oct-31
Included in the Prior Art Database: 2004-Apr-07
Document File: 6 page(s) / 294K

Publishing Venue

Xerox Disclosure Journal

Abstract

Error Diffusion (ED) is a halftoning process which has been shown to produce good results if applied to the grey value quantization. The output of ED can then be directed to a reproduction device. Various ED methods have been written in software. Unfortunately, ED is so computationally intensive that, no matter how efficient the software implementation is, it cannot drive even a slow printer in real time. The proposed hardware architecture will drive printers in real time, and is flexible enough to implement many distinct ED algorithms.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 31% of the total text.

Page 1 of 6

XEROX DISCLOSURE JOURNAL

ERROR

ERROR DIFFUSION ARCHITECTURE Panos Papaconstantinou

Proposed Classification
U.S. C1.358/466 Int. C1. H04n 1/40

+-

GREY PIXELS

12

14

THRESHOLD ERROR GENERATION

LU t

1

-

3/16 5/16 1/16 7/16

v v v

18 \ ERROR

SYNC

*

20

22 I

BINARY PIXELS OUT

XEROX DISCLOSURE JOURNAL Vol. 20 No. 5 September/Odober 1995 473

[This page contains 1 picture or other non-text object]

Page 2 of 6

ERROR DIFFUSION ARCHITECTURE(Cont'd)

Error Diffusion (ED) is a halftoning process which has been shown to produce good results if applied to the grey value quantization. The output of ED can then be directed to a reproduction device. Various ED methods have been written in software. Unfortunately, ED is so computationally intensive that, no matter how efficient the software implementation is, it cannot drive even a slow printer in real time. The proposed hardware architecture will drive printers in real time, and is flexible enough to implement many distinct ED algorithms.

The idea behind ED is that during the thresholding operation, after the decision for a pixel has been made, the error introduced by that decision is known. For instance, if the original grey pixel is 75% black, and a black bit is printed, there is 25% too much black in the reproduction. This error value can be distributed among neighboring sample points. When too much black is printed, error is added to the neighborhood, effectively pushing the neighbors a little closer to white. When not enough black is printed, the error is subtracted from the neighborhood, pushing the neighbors closer to black.

Error is defined as:

Error = Grey value - Assigned value

In the Floyd-Steinberg method of ED, determined error is multiplied by a set of weighting factors and then distributed to the unprocessed neighboring pixels. In one example, the error added to each neighboring pixel is multiplied by a weighting factor in the set (7116, 3/16, 5/16, 1/16}, depending on the position of the neighbor with respect to the current pixel. Eight bit per pixel grey representation is assumed with white = 0, and black = 255. Black or white pixels do not generate any errors. There are many distinct sets of neighbors and weights useful in variations of this process, which combine to give somewhat different results.

Figure 1 shows the architecture of the proposed error diffuser. Gray pixels are directed to an input, and a binary image is provided at an output. Processing proceeds pixel by pixel, and scanline after scanline.

Adder 10 adds previously calculated errors to the current gre pixel received at input 12. The modified grey pixel is thresholded at thresh0

              14 r ding circuit to produce a new binary pixel, and generate the new errors. Error generation is performed by a look up table 16.

474 XEROX DISCLOSURE JOURNAL Vol. 20 No. 5 SeptemberIOctober 1995

L

[This page contains 1 picture or other non-text object]

Page 3 of 6

ERROR DIFFUSION ARCHITECTURE(Cont'd)

For example, an adder 10 output of gray va...