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

Claim 2

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: 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.

Claim 3

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.

Claim 4

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

Claim 5

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: 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.

Claim 6

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: 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.

Claim 7

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

Claim 8

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

Claim 9

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.

Claim 10

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

Claim 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: e(P(i+2,j))=E.sub.i *W.sub.1 e(P(i-1,j+1))=E.sub.i *W.sub.2 e(P(i,j+1))=E.sub.i *W.sub.3 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 1 , W 2 , W 3 , and W 4 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.

Claim 12

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: e(P(i+2,j))=E.sub.i *W.sub.1 e(P(i-1,j+1))=E.sub.i *W.sub.2 e(P(i,j+1))=E.sub.i *W.sub.3 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 1 , W 2 , W 3 , and W 4 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.

Claim 13

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

Claim 14

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: e(P(i+2,j))=E.sub.i *W.sub.1 e(P(i-1,j+1))=E.sub.i *W.sub.2 e(P(i,j+1))=E.sub.i *W.sub.3 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 1 , W 2 , W 3 , and W 4 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.

Claim 15

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: e(P(i+2,j))=E.sub.i *W.sub.1 e(P(i-1,j+1))=E.sub.i *W.sub.2 e(P(i,j+1))=E.sub.i *W.sub.3 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 1 , W 2 , W 3 , and W 4 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.

Claim 16

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

Claim 17

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: 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.

Claim 18

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: 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.

Claim 19

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.

Claim 20

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

Claim 23

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

Claim 24

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

Claim 25

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.

Claim 26

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

Claim 27

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: e(P(i+2,j))=E.sub.i *W.sub.1 e(P(i-1,j+1))=E.sub.i *W.sub.2 e(P(i,j+1))=E.sub.i *W.sub.3 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 1 , W 2 , W 3 , and W 4 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.

Claim 28

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: e(P(i+2,j))=E.sub.i *W.sub.1 e(P(i-1,j+1))=E.sub.i *W.sub.2 e(P(i,j+1))=E.sub.i *W.sub.3 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 1 , W 2 , W 3 , and W 4 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.

Claim 29

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: e(P(i+2,j))=E.sub.i *W.sub.1 e(P(i-1,j+1))=E.sub.i *W.sub.2 e(P(i,j+1))=E.sub.i *W.sub.3 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 1 , W 2 , W 3 , and W 4 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.

Claim 30

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: e(P(i+2,j))=E.sub.i *W.sub.1 e(P(i-1,j+1))=E.sub.i *W.sub.2 e(P(i,j+1))=E.sub.i *W.sub.3 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 1 , W 2 , W 3 , and W 4 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.