Digital image processing algorithm for output devices with discrete halftone gray scale capability
First Claim
1. A method of processing image data wherein each data is to be printed or displayed as a pixel, each pixel programmable to one of a plurality of discrete gray scale values, said method comprising the steps of:
- (a) partitioning said image data into an array;
(b) computing a print array of print values each being a closest pixel gray scale value of a correspondingly located image datum of the image data array;
(c) computing an error array of value differences between the print values and the correspondingly located image data;
(d) adjusting print values in accordance with said gray scale values to reduce sums of error values, each within a plurality of unique error subarrays formed within the error array; and
(e) outputting the adjusted pixel print values for printing or display.
0 Assignments
0 Petitions
Accused Products
Abstract
A method and apparatus relating to image reproduction by displays and printers capable of different dot size or different spot intensity generations. The reproduction is based upon scanned image data including gray scale values individually representing the image intensity at each picture element location (pixel). The display and printing devices generate either different size dots or spots of different intensities at each pixel location. The image processing algorithm assigns to each pixel location an appropriate printing or display dot size (or spot intensity as the case may be) to reproduce an image closely resembling the original. The resulting print dot selection represents both a good approximation of the original gray scale value at that pixel location, and an accurate gray scale reproduction of the image collectively. Additionally, this algorithm is suitable for image reproduction including line copy imagery, halftone and continuous tone pictorials.
84 Citations
25 Claims
-
1. A method of processing image data wherein each data is to be printed or displayed as a pixel, each pixel programmable to one of a plurality of discrete gray scale values, said method comprising the steps of:
-
(a) partitioning said image data into an array; (b) computing a print array of print values each being a closest pixel gray scale value of a correspondingly located image datum of the image data array; (c) computing an error array of value differences between the print values and the correspondingly located image data; (d) adjusting print values in accordance with said gray scale values to reduce sums of error values, each within a plurality of unique error subarrays formed within the error array; and (e) outputting the adjusted pixel print values for printing or display. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. A method of processing image data including a plurality of data points, each representing a gray scale value of an element area of an image document to be printed or displayed by a device printing or displaying pixels corresponding to said data points, each pixel programmable to one of a plurality of discrete gray scale values, said method comprising the steps of:
-
(a) partitioning said image data into an N column by N row image data matrix (where N=2i, where i is an integer); (b) computing a print matrix of print values wherein each print value is the closest pixel gray scale value corresponding to a correspondingly located image value of said image data matrix; (c) computing an error matrix of error values wherein each error value is computed by subtracting a correspondingly located image value from a correspondingly located print value; (d) partitioning said error matrix into a first plurality of submatrices of 2M by 2M elements each (where initially M=1); (e) for each submatrix; (1) computing a first submatrix error sum by adding each of the error values of the submatrix; (2) determining an altered print value by changing the correspondingly located print value of the largest magnitude submatrix error value to the next discrete gray scale value to reduce the magnitude of this submatrix error value; (3) computing an altered submatrix error sum by subtracting the correspondingly located image value from the altered print value; and (4) replacing the point value with the altered point value if the altered submatrix error sum magnitude is less than the first submatrix error sum magnitude; (5) repeating steps (e) (1) through (e) (4) until the altered submatrix error sum is greater than the first submatrix error sum magnitude; (f) repartitioning said error matrix into a second plurality of submatrices of 2M by 2M elements each (where M=M+1); (g) repeating step (e); (h) repeating steps (f) and (g) until M=i; and (i) outputting the M=i data by pixel for printing or display.
-
-
13. An image reproduction system comprising:
-
an image data input means for scanning an original image and providing an array of image input data corresponding to gray scale levels of picture element locations of said original image; a processing means for receiving said image input array and computing a print array of print values, each print value corresponding to one of a fixed number of gray scale values, said print array representing a minimum total difference between the image input array values and the possible print array values for the fixed number of gray scale values; and a printing means capable of printing picture elements each having a dot size corresponding to one of the fixed number of gray scale values, for printing a plurality of picture elements, each corresponding to one value of the print array, upon a medium at locations corresponding to the locations of the corresponding image data from the original image for printing a reproduction of the original image. - View Dependent Claims (14, 15, 16)
-
-
17. An image reproduction system comprising:
-
an image data input means for scanning an original image and providing an array of image input data corresponding to gray scale levels of picture element locations of said original image; a processing means for receiving said image input array and computing a print array of print values, each print value corresponding to one of a fixed number of gray scale values, said print array representing a minimum total difference between the image input array values and the possible print array values for the fixed number of gray scale values; and a display means capable of displaying picture elements, each having an intensity level corresponding to one of the fixed number of gray scale values, for displaying a plurality of picture elements, each corresponding to one value of the print array, visually at the locations of the corresponding image data from the original image for displaying a reproduction of the original image. - View Dependent Claims (18, 19)
-
-
20. An image reproduction system comprising:
a processing means for processing data representing an image and computing a print array of print values, each print value corresponding to one of a fixed number of gray scale values, said print array representing a minimum total difference between the image data and the possible print array values for the fixed number of gray scale values and a display means capable of displaying picture elements, each having an intensity level corresponding to one of the fixed number of gray scale values, for displaying a plurality of picture elements, each corresponding to one value of the print array, visually at the locations of the corresponding image data. - View Dependent Claims (21, 22)
-
23. An image reproduction apparatus comprising:
-
(a) a data image means for producing a gray scale pixel value for each pixel of a data image of a scene, and (b) a data processing means responsive to the gray scale pixel value for producing a printing dot for each pixel of the image having a size which approximates the gray scale value, whereby a gray scale image having enhanced resolution is producible. - View Dependent Claims (24)
-
-
25. An image reproduction apparatus comprising:
-
(a) a means for producing an image of a scene; (b) an image data producing means responsive to the image for producing a data image pixel by pixel having gray scale values corresponding to the scene; and (c) data processing means operatively connected to the image producing means for;
(i) comparing the gray scale pixel values of the data image to a set of preselected gray scale values representative of the computers signal producing capability and generating an assigned data image with pixels having assigned gray scale values most closely approximating the data image;
(ii) partitioning the assigned data image into a plurality of arrays and subarrays;
(iii) performing a pixel error determining cycle including differencing the data image and the assigned data image for producing a pixel error image, combining the pixel errors for each subarray of the error image, generating an error value for each subarray, combining the subarray error values into a composite array error value indicating whether the array is too dark or too light, determining the subarray having the greatest applicable error, the pixel of the subarray having the highest worst case value and the next best value therefor from the set of preselected gray scale values, and substituting the next best value therefor;
(iv) repeating the error determining cycle with the substituted value for obtaining a minimized error value for the array; and
(v) controlling responsive to the pixel gray scale values as finally determined the size of the printing dot in proportion to the corresponding pixel value.
-
Specification