Optimally pipelined error diffusion architecture for converting scanned image into four-color printed image

A method of converting digital image data representing a colored image comprising four planes of individual pixels having associated multiple-bit intensity values into printed image data representing four planes of pixels having only more limited range of intensity values in a manner that preserves the average intensity of the original image over an area containing a plurality of pixels, comprising the steps adding an accumulated error from one or more previously processed pixels to a digital representation of a current pixel to thereby obtain a corrected pixel value;

• comparing the corrected pixel values for the four planes with each other and with a threshold to determine which pixels on which planes are to be represented by a dot of ink in the printed image,
• calculating a remaining error for each plane from the respective corrected pixel value and whether it is represented by a dot of ink in the printed image obtaining a randomized error ratio;
• and
• applying the randomized error ratio to the remaining error to thereby obtain an accumulated error component to be propagated to one or more neighboring pixels that have not yet been processed,
• wherein;
• the accumulated error is derived from an error component which was stored in an addressable memory during the processing of a prior row of pixels and which is subsequently read from the addressable memory during the processing of a current row of pixels;
• the randomized error ratio is stored in the addressable memory;
• multiple values of the randomized error ratio are retrieved from the addressable memory during the processing of each current pixel, using a different address for each of the neighboring pixels to which a respective accumulated error component is to be propagated from the current pixel;
• each retrieved value of the randomized error ratio is a single byte and the remaining error comprises more than one byte;
• the accumulated error component to be propagated to a particular neighboring pixel of a particular current pixel is obtained by multiplying the corresponding retrieved value of the randomized error ratio by the remaining error for that current pixel;
• each accumulated error component to be propagated to the next row of pixels is stored in the addressable memory during the processing of the current row of pixels;
• the adding, comparing, calculating and multiplying steps are performed in parallel fashion as a plurality of pipelined processes;
• the reading of the previously stored accumulated error component, the reading of the multiple values of the randomized error ratio, and the writing of the accumulated error component to be propagated to next row are performed in sequential fashion as part of a single sequential process concurrently with the pipelined processes;
• and
• the maximum time required to perform the plurality of pipelined processes is not greater than the minimum time required to perform the single sequential process.