Image analysis – Image compression or coding – Quantization
Reexamination Certificate
1998-04-17
2001-12-11
Boudreau, Leo (Department: 2621)
Image analysis
Image compression or coding
Quantization
C382S252000, C358S001900, C358S451000, C345S596000
Reexamination Certificate
active
06330368
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to dithering signals, and more particularly to a generating arrays of 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 so that memory storage can be reduced.
SUMMARY OF THE INVENTION
Provided is a method that generates a one-dimensional dither array having a predetermined number of dither values at addresses of the array. The method includes the following steps. Generating a choice size vector and a choice vector. Initializing an address, a dither value, and a counter for indexing the choice size vector and the choice vector to zero.
Determining if the dither value is equal to the size of the dither array, and terminating if true, otherwise if false continuing with the following steps.
Assigning a step variable a value that is equal to the size of the dither array divided by a current value of the indexed choice size vector, and assigning an offset a value that is equal to the rounded-down integer value of the step divided by two. Assigning the address, modulus the step, equal to the address, plus the offset, plus the current value of the indexed choice vector multiplied by the step.
Placing the dither value in the dither array at the address, and incrementing the dither value. Placing the dither value in the dither array at the address plus the step size divided by two, all modulus the step size, and incrementing the dither value.
Incrementing the counter for indexing the choice size vector and the choice vector, and continuing with the determining step above.
The choice size vector for dither arrays with eight, sixteen, thirty-two, and sixty eight dither values respectively are: [4, 2], [4, 2, 8, 2, 4, 2], [4, 2, 8, 2, 4, 2, 16, 2, 4, 2, 8, 2, 4, 2], and [4, 2, 8, 2, 4, 2, 16, 2, 4, 2, 8, 2, 4, 2, 32, 2, 4, 2, 8, 2, 4, 2, 16, 2, 4, 2, 8, 2, 4, 2].
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: 5508822 (1996-04-01), Ulichney et al.
patent: 5602941 (1997-02-01), Charles et al.
patent: 5987219 (1999-11-01), Naylor, Jr. et al.
U.S. Application No. 09/016,316, Cheung et al.; filed Jan. 30, 1998. “Method for Low Complexity, Low Memory Inverse Dithering”.
Boudreau Leo
Cesari and McKenna LLP
Compaq Computer Corporation
Sherali Ishrat
LandOfFree
Method for generating dither values for one-dimensional... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for generating dither values for one-dimensional..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for generating dither values for one-dimensional... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2570678