Facsimile and static presentation processing – Static presentation processing – Attribute control
Reexamination Certificate
1999-11-03
2004-05-04
Grant, II, Jerome (Department: 2624)
Facsimile and static presentation processing
Static presentation processing
Attribute control
C358S003030, C358S003040
Reexamination Certificate
active
06731404
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention pertains to the field of rendering grayscale data on a binary marking engine such as are found in low cost digital copiers and printers. Specifically, the present invention pertains to the field of hardware support for halftone rendering and error diffusion rendering.
2. Discussion of the Related Art
Halftoning and error diffusion are two well-known algorithms for rendering color or black and white grayscale data on a binary marking engine. Many display and hardcopy devices are bilevel—they produce just two intensity levels, either “on” or “off”.
In the technique known as halftoning, each small resolution unit of area in the rendered output is imprinted with black ink whose area is proportional to the blackness 1-I (where I is intensity) of the corresponding area in the original unrendered input. For example, a 2×2 pixel area of a bilevel display can be considered the small resolution unit. In this case, each 2×2 pixel area can be used to produce five different intensity levels at the cost of halving the spatial resolution along each axis. This result is accomplished by turning “on” either none, 1, 2, 3, or all 4 of the four pixels in the small resolution unit. In general, an n×n group of bilevel pixels can provide n
2
+1 intensity levels but lowers the spatial resolution on each axis by a factor of 1
.
In the technique known as error diffusion, the error between the rendered pixel value and the corresponding unrendered pixel value is computed. The error is added to the values of the four image-array pixels to the right of and below the pixel in question:
7
/
16
of the error to the pixel to the right,
3
/
16
to the pixel below and to the left,
5
/
16
to the pixel immediately below, and
1
/
16
to the pixel below and to the right. This has the effect of spreading, or diffusing, the error over several pixels in the image array.
Each of the halftone and error diffusion techniques has advantages in distinct situations. For example, it has been known in the art that error diffusion can have both superior tone response and detail rendition as compared to halftoning on high quality marking engines. Alternatively, for a lower quality marking engine in which dot gain and dot misregistration limit image quality, the clustered dot halftoning algorithm has been shown to somewhat mitigate the adverse effects of the lower print quality. Therefore, the specific marking engine to be used or the source material to be rendered may make one algorithm more suitable than the other.
It is therefore desirable to have the capability to perform either rendering technique. These rendering techniques are suitable for implementation in hardware, for example, on an integrated circuit. However, to implement two separate hardware renderers is expensive, especially given that one of the hardware renderers will be idle at any given time. As is apparent from the above discussion, a need exists for a lower cost hardware renderer capable of selectively performing either halftone or error diffusion rendering.
SUMMARY OF THE INVENTION
Conventional circuits for rendering color or black and white grayscale data on a binary marking engine operate either according to a halftoning algorithm or according to an error diffusion algorithm. Because each algorithm has its distinct advantages, it is desirable to implement a marking engine capable of functioning in either error diffusion mode or halftone mode. However, conventionally the duplicative hardware needed to implement both an error diffusion renderer and a halftone renderer is prohibitively expensive for many applications. An object of the present invention is to implement a circuit for rendering capable of operating in either an error diffusion mode or a halftone mode without unduly increasing the hardware cost of supporting both modes.
The present invention describes how one renderer serve as either a halftone renderer or an error diffusion renderer. Importantly, the more expensive portions of either renderer—the memory and memory bandwidth—are reused according to the present invention, so that the incremental cost of including an additional rendering algorithm is very low. According to the present invention, only one set of logic performs either halftoning or error diffusion rendering. Compared to conventional logic which performs only error diffusion, the incremental cost of implementing the combined halftoning/error diffusion renderer according to the present invention is very low.
According to the present invention, circuit implementations generate a rasterized rendered datastream from a rasterized unrendered datastream using either a halftone or error diffusion algorithm. Thus, the circuits according to the present invention are operable to function in either halftone mode or error diffusion mode.
The circuits according to the present invention include a comparator for comparing an unrendered pixel signal and a threshold signal regardless of whether or not the circuit is operating in halftone mode or error diffusion mode.
According to an aspect of the present invention, a pixel multiplexor selects between a rasterized unrendered pixel signal from an input rasterized unrendered datastream when in halftone mode and an error diffusion adjusted pixel signal generated by error diffusion hardware when in error diffusion mode. The error diffusion hardware which produces the error diffusion adjusted pixel signal includes an error diffusion adder which adds the rasterized unrendered pixel signal from the input rasterized unrendered datastream to an error diffusion feedback signal generated by an error diffusion filter. The error diffusion filter takes the unrendered pixel signal from the pixel multiplexor operating in error diffusion mode and the binary rasterized rendered output signal from the comparator as inputs. The difference between the binary rasterized rendered output signal and the unrendered pixel signal represents the total error which must be distributed to other pixels according to the error diffusion algorithm. The error diffusion filter produces the error diffusion feedback signal and a current error diffusion state signal as outputs. The error diffusion feedback signal represents error to be distributed to the subsequent pixel in the same scan line. The current error diffusion state signal represents error to be distributed to a pixel in the next scan line. Thus, the circuits according to the present invention include a memory for storing the current error diffusion state signal and for retrieving it as the previous error diffusion state signal during the processing of the appropriate pixel in the next scan line when operating in error diffusion mode. The error diffusion adder adds the previous error diffusion state signal from the memory and adds it to the rasterized unrendered pixel signal from the input rasterized unrendered datastream and the error diffusion feedback signal generated by an error diffusion filter to produce the error diffusion adjusted pixel signal.
According to another aspect of the present invention, a threshold multiplexor selects between an error diffusion threshold signal and a halftone threshold signal depending upon whether the circuit is operating in error diffusion mode or halftone mode. The threshold multiplexor passes the threshold signal which is selected to the comparator. The circuit preferably also includes an error diffusion threshold register to storing the error diffusion threshold signal.
According to yet another aspect of the present invention, an error diffusion write address generator provides an error diffusion write address signal which indicates the memory location in which to store the current error diffusion state signal computed by the error diffusion filter when the circuit is operating in error diffusion mode. When operating in halftone mode, the memory is operable to retrieve a halftone threshold signal which is supplied to the threshold multiplexor.
According to another aspect of the present inv
Fliesler & Meyer LLP
Grant II Jerome
Xerox Corporation
LandOfFree
Halftone and error diffusion rendering circuits does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Halftone and error diffusion rendering circuits, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Halftone and error diffusion rendering circuits will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3222896