Methods and apparatus for providing digital halftone images with random error diffusion dithering

• US 5,835,687 A
• Filed: 10/21/1996
• Issued: 11/10/1998
• Est. Priority Date: 10/21/1996
• Status: Expired due to Fees

• Current Assignee: 3D Systems, Inc. (3D Systems Corporation)
• Original Assignee: Vidar Systems Corporation (3D Systems Corporation)
• Inventors: Brown, Joseph, Loch, Brian
• Primary Examiner(s): Vu, Kim Yen
• Assistant Examiner(s): Popovici, Dov
• Application Number:
  US08/734,080
• Time in Patent Office: 750 Days
• Field of Search: 395/109, 395/101, 382/252, 382/274, 382/275, 382/232, 382/251, 382/169, 358/456, 358/457, 358/458, 358/534, 358/298, 358/455, 358/459, 358/463, 358/447, 358/535, 358/536
• US Class Current: 358/1.9
• CPC Class Codes: H04N 1/4052 by error diffusion, i.e. transferring the binarising error to neighbouring dot decisions

Abstract

A process for performing error diffusion to print an image with reduced visually apparent artifacts. The process involves a step of encoding selected pixels as binary values, and calculating error values corresponding to differences between modified intensity values of the pixels and predetermined threshold values. The calculated error values are diffused among four neighbors of each pixel in accordance with a predetermined ordered set of weighting factors. The set of weighting values dictates that 4/8 of the error is diffused to one of the pixel neighbors, 1/8 of the error is diffused to a second pixel neighbor, 2/8 of the error is diffused to a third pixel neighbor, and 1/8 of the error is diffused to a fourth pixel neighbor. A random selection is made of one of the predetermined set of weight values as a starting weight value. The starting weight value is assigned to a predetermined one of the pixel neighbors. Based on the starting weight value, the process then involves selecting in an ordered fashion weight values of the predetermined set of weight values until all the predetermined weight values have been selected, and assigning each selected weight value to a predetermined one of the pixel neighbors. This process continues for all pixels of an input image.

Claims

1. A process for performing error diffusion to print an image with reduced visually apparent artifacts, wherein the process is performed by a processor connected to a scanner that scans the image and detect intensity values at selected pixel locations, the process comprising the steps of:

encoding selected ones of the pixel locations as binary values, and calculating error values corresponding to differences between modified intensity values for such pixel locations and predetermined threshold values;

for selected pixel neighbors of an i^th pixel location in the scanned image, diffusing the calculated error value, E_i, of the i^th pixel location to its selected neighbors as follows;

space="preserve" listing-type="equation">e.sub.j =w.sub.j *E.sub.i

where e_j is the error value diffused to the j^th pixel neighbor from the i^th pixel location, where the j^th pixel neighbor is a second-adjacent pixel location to the right of the i^th pixel location and on the same scan line as the i^th pixel location, and where w_j is a weighting factor randomly selected for the j^th pixel location from a predetermined ordered set of weighting factors;

continuing the error diffusion process for other pixel neighbors of the i^th pixel location, wherein the other pixel neighbors are located on a scan line following the scan line of the i^th pixel location and are adjacent or diagonally-adjacent to the i^th or j^th pixel location, and wherein the weighting factors applied to the other pixel neighbors are selected from the ordered set of weighting factors in accordance with the weighting factor selected for the j^th pixel location; and

continuing the error diffusion process for the (i+1)^th pixel location and so forth, such that coding errors are diffused from substantially all of the pixel locations in the image.

2. The process of claim 1 wherein an inverse value of each of the weighting factors in the ordered set of weighting factors is a power of two.

3. The process of claim 2 wherein the weighting factors include 1/2, 1/8, 1/4, 1/8.

4. A digital halftoning process with random error diffusion for reducing visually apparent artifacts in images that are produced by digital halftone printing, comprising the steps of:

scanning an image to detect intensity values at selected pixel locations;

encoding selected ones of the pixel locations as one binary value when the detected intensity value at a location is less than a predetermined threshold value, and calculating error values for such pixel locations that equal the detected intensity values;

encoding selected other ones of the pixel locations as a second binary value when the detected intensity values at those locations are greater than the predetermined threshold value, and calculating error values for those locations that equal the detected intensity values less the upper limit of an intensity scale;

for selected pixel neighbors of an i^th pixel location in the scanned image, diffusing the calculated error value, E_i, of the i^th pixel location to its selected neighbors as follows;

space="preserve" listing-type="equation">e.sub.j =w.sub.j *E.sub.i

where e_j is the error value diffused to the j^th pixel neighbor from the i^th pixel location, where the j^th pixel neighbor is a second-adjacent pixel location to the right of the i^th pixel location and on the same scan line as the i^th pixel location, and where w_j is a weighting factor randomly selected for the j^th pixel location from a predetermined ordered set of weighting factors;

continuing the error diffusion process for other pixel neighbors of the i^th pixel location, wherein the other pixel neighbors are located on a scan line following the scan line of the i^th pixel location and are adjacent or diagonally-adjacent to the i^th or j^th pixel location, and wherein the weighting factors applied to the other pixel neighbors are selected from the ordered set of weighting factors in accordance with the weighting factor selected for the j^th pixel location;

continuing the error diffusion process for the (i+1)^th pixel location and so forth, such that coding errors are diffused from substantially all of the pixel locations in the image; and

printing images by digital halftone printing based upon intensity values of pixel locations that have been modified by error diffusion.

5. The process of claim 4 wherein the predetermined threshold value is a number about midway along the intensity scale.

6. The process of claim 4 wherein the predetermined threshold value is a constant.

7. The process of claim 4 wherein an inverse value of each of the weighting factors in the ordered set of weighting factors is a power of two.

8. The process of claim 4 wherein the weighting factors include 1/2, 1/8, 1/4, 1/8.

9. A digital halftoning process with random error diffusion for reducing visually apparent artifacts in images that are produced by digital halftone printing, comprising the steps of:

scanning an image to detect intensity values at selected pixel locations;

encoding selected ones of the pixel locations as one binary value when the detected intensity value at a location is less than a predetermined threshold value, and calculating error values for such pixel locations that equal the detected intensity values;

encoding selected other ones of the pixel locations as a second binary value when the detected intensity values at those locations are greater than the predetermined threshold value, and calculating error values for those locations that equal the detected intensity values less the upper limit of an intensity scale;

for selected pixel neighbors of an i^th pixel location in the scanned image, diffusing the calculated error value, E_i, of the i^th pixel location to its selected neighbors as follows;

space="preserve" listing-type="equation">e(P(i+2,j))=E.sub.i *W.sub.1

space="preserve" listing-type="equation">e(P(i-1,j+1))=E.sub.i *W.sub.2

space="preserve" listing-type="equation">e(P(i,j+1))=E.sub.i *W.sub.3

space="preserve" listing-type="equation">e(P(i+1,j+1))=E.sub.i *W.sub.4

where i represents a row of the scanned image and j represents a column of the scanned image, where the selected neighbors include P(i+2,j), P(i-1,j+1), P(i,j+1), and P(i+1,j+1) so that e(P(i+2,j)) is an amount of the error value E_i to be assigned to pixel neighbor P(i+2,j), e(P(i-1,j+1)) is an amount of the error value E_i to be assigned to pixel neighbor P(i-1j+1), e(P(i,j+1)) is an amount of the error value E_i to be assigned to pixel neighbor P(i,j+1), and e(P(i+1,j+1)) is an amount of the error value E_i to be assigned to pixel neighbor P(i+1j+1), and where W₁, W₂, W₃, and W₄ are selected from an ordered set of weight values; and

continuing the error diffusion process for the (i+1)^th pixel location and so forth, such that coding errors are diffused from substantially all of the pixel locations in the image.

10. The process of claim 9, wherein the ordered set of weight values is 4/8, 1/8, 2/8, 1/8.

11. A digital halftoning process with random error diffusion for reducing visually apparent artifacts in images that are produced by digital halftone printing, comprising the steps of:

scanning an image to detect intensity values at selected pixel locations;

encoding selected ones of the pixel locations as one binary value when the detected intensity value at a location is less than a predetermined threshold value, and calculating error values for such pixel locations that equal the detected intensity values;

encoding selected other ones of the pixel locations as a second binary value when the detected intensity values at those locations are greater than the predetermined threshold value, and calculating error values for those locations that equal the detected intensity values less the upper limit of an intensity scale;

for selected pixel neighbors of an i^th pixel location in the scanned image, diffusing the calculated error value, E_i, of the i^th pixel location to its selected neighbors as follows;

space="preserve" listing-type="equation">e(P(i+2,j))=E.sub.i *W.sub.1

space="preserve" listing-type="equation">e(P(i-1,j+1))=E.sub.i *W.sub.2

space="preserve" listing-type="equation">e(P(i,j+1))=E.sub.i *W.sub.3

space="preserve" listing-type="equation">e(P(i+1,j+1))=E.sub.i *W.sub.4

where i represents a row of the scanned image and j represents a column of the scanned image, where the selected neighbors include P(i+2,j), P(i-1i+1), P(i,j+1), and P(i+1,j+1) so that e(P(i+2,j)) is an amount of the error value E_i to be assigned to pixel neighbor P(i+2,j), e(P(i-1,i+1)) is an amount of the error value E_i to be assigned to pixel neighbor P(i-1j+1), e(P(i,j+1)) is an amount of the error value E_i to be assigned to pixel neighbor P(i,j+1), and e(P(i+1j+1)) is an amount of the error value E_i to be assigned to pixel neighbor P(i+1j+1), and where W₁, W₂, W₃, and W₄ are selected from an ordered set of weight values; and

continuing the error diffusion process for the (i+1)^th pixel location and so forth, such that coding errors are diffused from substantially all of the pixel locations in the image.

12. The process of claim 11, wherein the ordered set of weight values is 4/8, 1/8, 2/8, 1/8.

13. Apparatus for performing error diffusion to print an image with reduced visually apparent artifacts, wherein a scanner scans the image and detects intensity values at selected pixel locations, the apparatus comprising:

an encoder configured to encode selected ones of the pixel locations as binary values, and calculate error values corresponding to differences between modified intensity values for such pixel locations and predetermined threshold values;

a diffuser, coupled to said encoder, configured to diffuse the calculated error value, E_i, for selected pixel neighbors of an i^th pixel location in the scanned image as follows;

space="preserve" listing-type="equation">e.sub.j =w.sub.j *E.sub.i

where e_j is the error value diffused to the j^th pixel neighbor from the i^th pixel location, where the j^th pixel neighbor is a second-adjacent pixel location of the i^th pixel location and on the same scan line as the i^th pixel location, and where w_j is a weighting factor randomly selected for the j^th pixel location from a predetermined ordered set of weighting factors;

said diffuser continuing to diffuse the error E_i to other pixel neighbors of the i^th pixel location, wherein the other pixel neighbors are located on a scan line following the scan line of the i^th pixel location and are adjacent or diagonally-adjacent to the i^th or j^th pixel location, and wherein the weighting factors applied to the other pixel neighbors are selected from the ordered set of weighting factors in accordance with the weighting factor selected for the j^th pixel location.

14. The apparatus of claim 13 wherein an inverse value of each of the weighting factors in the ordered set of weighting factors is a power of two.

15. The apparatus of claim 13 wherein the weighting factors include 1/2, 1/8, 1/4, 1/8.

16. A system for reducing visually apparent artifacts in images that are produced by digital halftone printing, comprising:

a scanner configured to scan an image to detect intensity values at selected pixel locations;

an encoder, coupled to the scanner, configured to encode selected ones of the pixel locations as one binary value when the detected intensity value at a location is less than a predetermined threshold value, and to calculate error values for such pixel locations that equal the detected intensity values;

said encoder configured to encode selected other ones of the pixel locations as a second binary value when the detected intensity values at those locations are greater than the predetermined threshold value, and calculate error values for those locations that equal the detected intensity values less the upper limit of an intensity scale;

a diffuser, coupled to said encoder, configured to diffuse the calculated error value, E_i, of an i^th pixel location to its selected neighbors as follows;

space="preserve" listing-type="equation">e.sub.j =w.sub.j *E.sub.i

where e_j is the error value diffused to the j^th pixel neighbor from the i^th pixel location, where the j^th pixel neighbor is a second-adjacent pixel location to the right of the i^th pixel location and on the same scan line as the i^th pixel location, and where w_j is a weighting factor randomly selected for the j^th pixel location from a predetermined ordered set of weighting factors;

said diffuser continuing to diffuse the error E_i to other pixel neighbors of the i^th pixel location, wherein the other pixel neighbors are located on a scan line following the scan line of the i^th pixel location and are adjacent or diagonally-adjacent to the i^th or j^th pixel location, and wherein the weighting factors applied to the other pixel neighbors are selected from the ordered set of weighting factors in accordance with the weighting factor selected for the j^th pixel location; and

a printer, coupled to said scanner, configured to print images by digital halftone printing based upon intensity values of pixel locations that have been modified by error diffusion.

17. The system of claim 16 wherein the predetermined threshold value is a number about midway along the intensity scale.

18. The system of claim 16 wherein the predetermined threshold value is a constant.

19. The system of claim 16 wherein an inverse value of each of the weighting factors in the ordered set of weighting factors is a power of two.

20. The system of claim 16 wherein the weighting factors include 1/2, 1/8, 1/4, 1/8.

21. A digital halftoning apparatus for reducing visually apparent artifacts in images that are produced by digital halftone printing, comprising:

a scanner configured to scan an image to detect intensity values at selected pixel locations;

an encoder configured to encode selected ones of the pixel locations as one binary value when the detected intensity value at a location is less than a predetermined threshold value, and to calculate error values for such pixel locations that equal the detected intensity values;

said encoder configured to encode selected other ones of the pixel locations as a second binary value when the detected intensity values at those locations are greater than the predetermined threshold value, and calculate error values for those locations that equal the detected intensity values less the upper limit of an intensity scale;

a diffuser configured to diffuse the calculated error value, E_i, of an i^th pixel location to its selected neighbors as follows;

space="preserve" listing-type="equation">e(P(i+2,j))=E.sub.i *W.sub.1

space="preserve" listing-type="equation">e(P(i-1,j+1))=E.sub.i *W.sub.2

space="preserve" listing-type="equation">e(P(i,j+1))=E.sub.i *W.sub.3

space="preserve" listing-type="equation">e(P(i+1,j+1))=E.sub.i *W.sub.4

where i represents a row of the scanned image and j represents a column of the scanned image, where the selected neighbors include P(i+2,j), P(i-1,j+1), P(i,j+1), and P(i+1,j+1) so that e(P(i+2,j)) is an amount of the error value E_i to be assigned to pixel neighbor P(i+2,j), e(P(i-1,j+1)) is an amount of the error value E_i to be assigned to pixel neighbor P(i-1,j+1), e(P(i,j+1)) is an amount of the error value E_i to be assigned to pixel neighbor P(i,j+1), and e(P(i+1,j+1)) is an amount of the error value E_i to be assigned to pixel neighbor P(i+1j+1), and where W₁, W₂, W₃, and W₄ are selected from an ordered set of weight values; and

said encoder and said diffuser configured to continue to diffuse an error for the (i+1)^th pixel location and so forth, such that coding errors are diffused from substantially all of the pixel locations in the image.

22. A digital halftoning processor for reducing visually apparent artifacts in images that are produced by digital halftone printing, comprising:

a scanner configured to scan an image to detect intensity values at selected pixel locations;

an encoder configured to encode selected ones of the pixel locations as one binary value when the detected intensity value at a location is less than a predetermined threshold value, and calculate error values for such pixel locations that equal the detected intensity values;

said encoder configured to encode selected other ones of the pixel locations as a second binary value when the detected intensity values at those locations are greater than the predetermined threshold value, and calculate error values for those locations that equal the detected intensity values less the upper limit of an intensity scale;

a diffuser configured to diffuse the calculated error value, E_i, of an i^th pixel location to its selected neighbors as follows;

space="preserve" listing-type="equation">e(P(i+2,j))=E.sub.i *W.sub.1

space="preserve" listing-type="equation">e(P(i-1,j+1))=E.sub.i *W.sub.2

space="preserve" listing-type="equation">e(P(i,j+1))=E.sub.i *W.sub.3

space="preserve" listing-type="equation">e(P(i+1,j+1))=E.sub.i *W.sub.4

where i represents a row of the scanned image and j represents a column of the scanned image, where the selected neighbors include P(i+2,j), P(i-1,i+1), P(i,j+1), and P(i+1j+1) so that e(P(i+2,j)) is an amount of the error value E_i to be assigned to pixel neighbor P(i+2,j), e(P(i-1,j+1)) is an amount of the error value E_i to be assigned to pixel neighbor P(i-1,i+1) e(P(i,j+1)) is an amount of the error value E_i to be assigned to pixel neighbor P(i,j+1), and e(P(i+1,j+1)) is an amount of the error value E_i to be assigned to pixel neighbor P(i+1,j+1), and where W₁, W₂, W₃, and W₄ are selected from an ordered set of weight values; and

said encoder and said diffuser configured to continue to diffuse an error for the (i+1)^th pixel location and so forth, such that coding errors are diffused from substantially all of the pixel locations in the image.