Digital image processing algorithm for output devices with discrete halftone gray scale capability

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=2.sup.i, 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 2.sup.M by 2.sup.M 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 2.sup.M by 2.sup.M 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.

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.

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.

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.