System and method for high addressable binary image generation using rank ordered error diffusion on pixels within a neighborhood

• US 7,663,782 B2
• Filed: 01/26/2006
• Issued: 02/16/2010
• Est. Priority Date: 01/26/2006
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Nagarajan, Ramesh, Cuciurean-Zapan, Clara
• Primary Examiner(s): Williams; Kimberly A
• Application Number:
  US11/340,380
• Publication Number:
  US 20070171475A1
• Time in Patent Office: 1,482 Days
• Field of Search: 358 303- 305, 358/1.9, 358/3.01, 358/3.06, 382/252, 382/232, 382/237
• US Class Current: 358/3.03
• CPC Class Codes: H04N 1/4052 by error diffusion, i.e. transferring the binarising error to neighbouring dot decisions

Abstract

The disclosed system and method provide a binary image generation method. Used, for example, in a digital reprographic system, the method is suitable for eliminating printing artifacts for high addressable binary digital output, such as digital copies, using an optimized ordered error diffusion method with dynamically computable quantization error and dynamic binary output calculation.

Claims

1. A method, operating on an image processor, for processing a multi-quantization level input image, comprising:

creating binary output by thresholding a current grayscale input image pixel and an associated intermediate predicted pixel value, wherein the associated intermediate predicted pixel value is calculated before thresholding;

calculating a pixel quantization error based upon the current image pixel value and the intermediate predicted pixel value;

ordering a plurality of neighboring pixels of the current pixel located in a predefined processing window according to their gray values;

diffusing a maximum possible amount of quantization error for the current image pixel sequentially to a subset of the plurality of neighboring pixels of the current pixel, where the subset of the plurality of neighbors are selected in accordance with the sign of quantization error; and

repeating the steps above for each input pixel in the image to produce an error-diffused output image for output by image processor.

2. The method of claim 1, wherein the subset size is N, where N>

1 and where the subset includes the N biggest pixel values in the plurality of neighboring pixels when the sign of the quantization error is positive.

3. The method of claim 1, wherein the subset size is N, where N>

1 and where the subset includes the N smallest pixel values in the plurality of neighboring pixels when the sign of the quantization error is negative.

4. The method of claim 1, wherein creating binary output by thresholding the current grayscale input image pixel produces a high addressable binary representation of the grayscale input image pixel, and where the pixel error is a function of the high addressable binary representation.

5. The method of claim 1, further comprising resetting the pixel quantization error to zero upon detecting a region of the input image having pixel values consistently near one extreme of the gray scale.

6. The method of claim 5, further including detecting continuous tone regions within the input image by collecting gray value statistics from a processing window before error diffusion, and in such continuous tone regions, performing only standard error diffusion.

7. The method of claim 5, further including retrieving stored knowledge relating to the input image and, based upon such knowledge, processing portions of the image using only standard error diffusion.

8. The method of claim 1, wherein a subset of N neighbors are picked from M neighboring pixels in an order corresponding to the sign of the quantization error, where if the quantization error is positive, the N biggest pixel values of the M neighboring pixels are selected, and when the quantization error is negative, the N smallest pixel values of the M neighboring pixels are selected.

9. The method according to claim 1, wherein the intermediate predicted pixel value (predval) is determined as a function of the current pixel and a next adjacent pixel in accordance with the function

predval=wa·

a+wp·

p,

where wa and wp are weighting variables.

10. A method creating a halftoned image, comprising:

receiving a pixel value from an input image;

selecting an processing window encompassing M neighboring pixels;

selecting a threshold;

thresholding the pixel value with the selected threshold to determine an intermediate predicted pixel value, wherein thresholding the input pixel value produces a high addressability binary representation of the grayscale input image pixel, and where the pixel error is a function of the high addressable binary representation;

calculating a quantization error value based on the pixel value and the intermediate predicted pixel value; and

diffusing quantization error to at least one selected neighboring pixel(s) N within the diffusion mask M, based on a sign of the calculated error value, the selection being based on pixel values of a plurality of neighboring pixels within the diffusion window.

11. The method of claim 10, further comprising resetting the pixel error value to zero upon detecting a region of the input image having pixel values consistently within a range of values near an extreme end of the gray scale.

12. The method of claim 11, further including detecting continuous tone regions within the input image by collecting gray value statistics from a processing window before error diffusion, and in such continuous tone regions, performing only standard error diffusion.

13. The method of claim 11, further including retrieving stored knowledge relating to the input image and based upon such knowledge, processing portions of the image using only standard error diffusion.

14. The method of claim 13, wherein the stored knowledge includes segmentation tags.

15. A digital reprographic system, comprising:

an image source;

an image processor, for processing each input pixel of an input image from said image source to produce an error-diffused output image, said image processor including

a thresholder for creating binary output and an associated intermediate predicted pixel value as a function of a current image pixel;

a pixel error calculator for calculating pixel quantization error based upon the current image pixel value and the intermediate predicted pixel value;

a pixel ordering circuit for ordering the current input image pixel'"'"'s M neighboring pixels located in a predefined processing window according to their gray values, said ordering circuit further diffusing the quantization error for the current image pixel sequentially to N out of the M neighbors of the current pixel, where N is not greater than M;

where the N neighbors are selected depending on the sign of quantization error, and

an image output terminal for outputting the error-diffused output image.

16. The system of claim 15, wherein the input image includes multi-bit grayscale data and where the thresholder operates on the current image pixel to produce a high addressability binary representation of the grayscale input image pixel.

17. The system of claim 16, wherein the pixel error calculator uses an error calculation function that is dynamically responsive to a combination of at least one of the group consisting of:

the current image pixel value, the intermediate predicted pixel value, and the values of the current pixel'"'"'s neighbors located in the processing window.

18. The digital reprographic system of claim 15, wherein the pixel ordering circuit includes an array for storing pixel values for M neighboring pixels and where N pixel values are picked from said array in the order corresponding to the sign of the quantization error, where if the quantization error is positive, the N biggest pixel values of the M neighboring pixels are selected, and when the quantization error is negative, the N smallest pixel values of the M neighboring pixels are selected.

19. The digital reprographic system of claim 18, further including an address buffer, wherein the addresses stored in the address buffer point to the N pixel values in the array in the order determined by the sign of the quantization error.