Multi-dimensional dithering using one-dimensional dither arrays

Details Multi-dimensional dithering using one-dimensional dither arrays Multi-dimensional dithering using one-dimensional dither arrays

1998-04-17

2001-08-21

Rogers, Scott (Department: 2724)

Facsimile and static presentation processing

Static presentation processing

Attribute control

C358S451000, C358S461000

Reexamination Certificate

active

06278530

ABSTRACT:

FIELD OF THE INVENTION
This invention relates generally to dithering digital signals, and more particularly to dithering pixels having addresses in multiple dimensions.
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 multi-dimensional dithering so that memory storage can be reduced.
SUMMARY OF THE INVENTION
Provided is an apparatus for dithering a digital signal having a plurality of address dimensions. In one aspect of the invention, the digital signal is made of image pixels, and each pixel has a vertical and horizontal address dimension.
The apparatus includes component sections for each dimension. The component sections are serially connected so that the output of a previous section can be part of the input of the next section. The output of the last section includes final dither values can that be applied to the digital signal.
In one implementation for producing sequentially accessed dither values, a first counter is incremented for each sequentially accessed first address of the first dimension such as a vertical dimension. The current values of the first counter are used to index a first dither array to produce the first dither values.
A second counter is initialized to the first dither value, and incremented for each sequentially accessed second address of the second dimension such as a horizontal dimension. The current values of the second counter are used to index a second dither array to produce final dither values that can be applied to the digital signal.


REFERENCES:
patent: 5333260 (1994-07-01), Ulichney
patent: 5333262 (1994-07-01), Ulichney
patent: 5495345 (1996-02-01), Ulichney
patent: 5508822 (1996-04-01), Ulichney et al.
patent: 5602941 (1997-02-01), Charles et al.
Cheung et al.; Pending Application Serial No. 09/016,316; “Method for Low Complexity, Low Memory Inverse Dithering”; Date filed Jan. 30, 1998.

Affiliated with

Also associated with

Rating

Multi-dimensional dithering using one-dimensional dither arrays does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Multi-dimensional dithering using one-dimensional dither arrays, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-dimensional dithering using one-dimensional dither arrays will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2482664