Facsimile and static presentation processing – Static presentation processing – Attribute control
Reexamination Certificate
1998-04-17
2002-07-23
Rogers, Scott (Department: 2624)
Facsimile and static presentation processing
Static presentation processing
Attribute control
C358S451000, C358S461000, C358S451000
Reexamination Certificate
active
06424431
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to dithering digital signals, and more particularly to dithering using one-dimensional dither values.
BACKGROUND OF THE INVENTION
When rendering an image, dithering is used to produce an illusion of continuous image intensity even though the picture elements (pixels) may have a limited granularity in amplitude. For example, a grey-scale image typically requires about eight bits per pixel to give a reasonable gradient in image intensity, e.i., 256 grey-scale levels. Dithering is a process that will produce a perceptually similar image when fewer bits are used per pixel. Indeed, dithering works when only one bit is used per pixel in a “bi-tonal image. In other words, the one bit only indicates whether the pixel is “on” or “off,” e.i., black or white.
Several methods for dithering are known in the prior art. The class of dithering which is of concern here is know as ordered dithering. Ordered dithering is a point process that uses only the current pixel of an input image to generate a corresponding pixel in an output image, no other pixels are considered. Ordered dithering can be one-dimensional, two-dimensional, and so forth. As an advantage, ordered dithering is fast and simple to implement. A key element contributing to the quality of the output image in ordered dithering is a good dither array.
One popular method that is used in two-dimensional ordered dithering is known as recursive tessellation, also known as Beyer's dither. There, a dither array is organized as a periodic and deterministic array of integers in the range 0 to 2
L
−1, where 2
L
is the number of levels in the array. In order to ensure that the process is “mean-preserving,” i.e., the average values found in the input image are maintained in the output image, the array of integers must be normalized, please see, Ulichney, “Video Rendering,” Digital Technical Journal, Vol. 5, No. 2, pp. 9-18, 1993.
An important special case exists when the number of input and output levels of the dithering system is a power of two. In this case, the values of the dither array (0 to 2
L
−1) can be used without normalization given that the other elements in the system are properly designed. In particular, the values of the “raw” input image must first be adjusted. A simple hardware implementation for adjusting raw input image values is described in U.S. Pat. No. 5,602,941, “Input Modification System for Multilevel Dithering,” issued to Ulichney et al. on Feb. 11, 1997.
There are several systems that use dither arrays to produce dithered images. For multilevel (more than two output levels) dithering, these systems include methods that use two memories, a single memory, and a bit shifter. For bi-tonal (2 output levels) dithering, a system with a comparator can be used.
One situation where dithering is used is in tandem with inverse-dithering. Inverse-dithering attempts to reconstruct the original image. One prior art inverse-dithering system uses a priori knowledge of the dither array to achieve a better reconstruction of the original image. There is a substantial implementation advantage when the inverse-dithering operates one dimensionally. That is, one-dimensional dithering only operates on a current pixel line horizontally, e.i., along the x-axis, without regard of previous or following pixel lines. For such a scheme to work best, the same dither array must be used for every image line. A one-dimensional (1-D) dither array is ideal for this application.
Other studies of 1-D dithering have focused on more complex neighborhood-operation-based schemes such as error-diffusion or model-based half-toning.
However, one-dimensional dithering has practical applications beyond image processing. In any processes where the signal is one dimensional, such as audio, and the amplitude is to be quantitized, dithering can help produce the illusion of an almost continuous output signal even though the input signal has discrete values. Therefore, it is desired to use one-dimensional dither arrays to perform dithering of digital signals.
SUMMARY OF THE INVENTION
Provided is an apparatus for sequentially generating one-dimensional dither values. The dither values can be applied to linear digital signals where each digital signal has an address and a signal value. In one embodiment, the digital signals are pixels of a video image.
A counter is incremented for each sequential address of the digital signal. A predetermined number of least significant bits from the current values of the counter are selected and connected to a reverse wire means for generating the dither values.
In an alternative embodiment, one-dimensional dither values are randomly generated. In this case, a predetermined number of least significant bits are directly selected from random addresses and connected to reverse wire means for generating dither values from the selected bits that are applied to the corresponding signal values.
REFERENCES:
patent: 5148273 (1992-09-01), Lippel
patent: 5264840 (1993-11-01), Wells et al.
patent: 5333260 (1994-07-01), Ulichney
patent: 5333262 (1994-07-01), Ulichney
patent: 5495345 (1996-02-01), Ulichney
patent: 5495346 (1996-02-01), Choi et al.
patent: 5508822 (1996-04-01), Ulichney et al.
patent: 5602941 (1997-02-01), Charles et al.
patent: 5987219 (1999-11-01), Naylor, Jr. et al.
patent: 6163629 (2000-12-01), Cheung et al.
patent: 6278530 (2001-08-01), Ulichney et al.
McNamara Robert Stephen
Ulichney Robert Alan
Cesari and McKenna LLP
Compaq Computer Corporation
Rogers Scott
LandOfFree
Apparatus for generating one-dimensional dither values does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus for generating one-dimensional dither values, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus for generating one-dimensional dither values will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2840415