Image analysis – Image compression or coding – Quantization
Reexamination Certificate
1998-06-03
2001-10-23
Tran, Phuoc (Department: 2621)
Image analysis
Image compression or coding
Quantization
C382S234000
Reexamination Certificate
active
06307978
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to the display of image data as a collection of picture elements (or pixels), and particularly relates to the display of color image data as a collection of picture elements wherein the variety of colors of the image data is greater than the variety of colors available for each picture element.
For example, color images may be displayed on black and white CRT displays (or flat panel displays or printers), but some information will be lost. Typically, for black and white displays, the value (or grayscale value) of each pixel of the image is compared to a threshold value, and if it is above the threshold then the pixel appears black, and if it is below the threshold then the pixel appears white. The difference between the greyscale value of an image pixel and the threshold is known as a pixel's error.
Dithering, or halftoning, refers to a variety of techniques that have been developed to distribute each pixel's error among neighboring pixels. For example, the Floyd and Steinberg method processes the input image in a linear fashion, scanning pixels from left to right and from top to bottom. See Robert W. Floyd and Louis Steinberg,
An Adaptive Algorithm for Spatial Grayscale
, Proceedings of the Society for Information Display, v.17, pp. 75-77 (1976). At each step of the Floyd and Steinberg method, the grayscale value of the current pixel (which is represented as an integer between 0 and 255), is compared to some threshold value, typically 128. Grayscale values above 128 are displayed as black, and grayscale values of 128 and below are displayed as white. The error for each pixel is distributed to four neighboring pixels that have not yet been processed. Specifically, and with reference to
FIG. 1
of the drawings, the error for a pixel in row “r” and column “c” (P
r,c
) is distributed to pixels P
r,c+1
, P
r+1,c+1
, P
r+1,c
, and P
r+1,c−1
. The pixel error is distributed with weights of {fraction (7/16)} for P
r,c+1
, {fraction (1/16)} for P
r+1,c+1
, {fraction (5/16)} for P
r+1,c
, and {fraction (3/16)} for P
r+1,c−1
.
The Floyd and Steinberg process is time consuming, and typically requires five floating-point multiplications and five memory accesses to process each pixel of the image. For an image with dimensions “n” by “m” this typically takes 10×n×m operations. The method is also, therefore, computationally expensive.
More elaborate dithering methods have further been proposed in which each pixel's error is distributed to up to 12 neighboring unprocessed pixels in accordance with various weight distributions. These algorithms produce displays of improved image quality over the Floyd and Steinberg method, but are more computationally expensive, requiring 24×n×m floating point multiplications and memory accesses for each n by m image. See J. F. Jarvis, C. N. Judice and W. H. Kinke,
A Survey of Techniques for the Display of Continuous Tome Pictures on Bi
-
Level Displays
, Computer Graphics and Image Processing, v.5, p.13-40 (1976); and P. Stucki,
MACCA—A Multiple Error Correcting Algorithm For Bi
-
Level Image Hard Copy Reproduction
, Research Report RZ1060, IBM Research Laboratory, Zurich, Switzerland (1981).
U.S. Pat. No. 5,553,165 discloses a method of parallel error diffusion. In the method of the '165 patent, the image is processed in a conventional top down, line by line left to right order. With reference to
FIG. 2
of the drawings, two or more processors (P and Q) are employed to process the image by having each processor scan the image along different rows, slightly offset from one another. Error diffusion data is written to and read from a memory unit that is shared between the processors. The method of the '165 patent, however, is still rather time consuming because the memory unit must be continuously accessed by both processors, and because each pixel must be accessed twice. Using additional processors in the method of the '165 patent in turn requires more interaction between the processors and sharing of data via common memory.
Dithering requires that a pixel be processed only after all of the pixels from which it depends have been processed. The use of multiple processors, therefore, has been of only marginal benefit because some processors will be required to wait for others. Moreover, the processors in a multiprocessor system must share memory, and each pixel may be required to be accessed at least twice. Further, the number of processors may not be easily changed in a parallel dithering system such as that of the '165 patent without reconfiguring the physical system. There is a need, therefore, for a more efficient method of dithering.
SUMMARY OF THE INVENTION
The system includes an input for receiving an input matrix representative of image data, and a plurality of processors. The plurality of processors processes the input matrix, and each of the processors is in communication with at least a portion of the input matrix. At least one processor processes a portion of the input matrix defined at least in part by a substantially diagonal edge within the image matrix. An output may also be provided in communication with each of the processors, and the output provides an output matrix representative of dithered image data.
In various embodiments of the invention, the input matrix is divided into diagonal input areas having a row width of at least three picture elements. Each processor in a linear array of processors processes a diagonal input area. In other embodiments, a matrix of processors may be used to process the input matrix, and the input matrix may be preprocessed prior to being divided into input areas.
REFERENCES:
patent: 5271070 (1993-12-01), Truong et al.
patent: 5309525 (1994-05-01), Shimomura et al.
patent: 5373455 (1994-12-01), Edgar
patent: 5519791 (1996-05-01), Webb et al.
patent: 5528384 (1996-06-01), Metcalfe et al.
patent: 5553165 (1996-09-01), Webb et al.
patent: 5592592 (1997-01-01), Shu
patent: 5604605 (1997-02-01), Moolenaar
patent: 5627659 (1997-05-01), Kakutani
patent: 5663810 (1997-09-01), Kirk
patent: 5682442 (1997-10-01), Johnston et al.
patent: 5818971 (1998-10-01), Moolenaar et al.
patent: 5870503 (1999-02-01), Kumashiro
patent: 5974228 (1999-10-01), Heitsch
Yuefeng Zhang, “Line Diffusion: a parallel error diffusion algorithm for digital halftoning”, Springer Link: The Visual Computer, vol. 12 Issue 1, pp. 40-46 (Abstract only).
Donald E. Knuth, “Digital halftones by dot diffusion”, Oct., 1987, ACM, Inc. vol. 6, No. 4, pp. 245-273.
Alavi Amir
Samuels Gauthier & Stevens
Tran Phuoc
Wellesley College
LandOfFree
System and method for parallel error diffusion dithering does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for parallel error diffusion dithering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for parallel error diffusion dithering will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2600812