High speed digital error diffusion process for continuous tone image-to-binary image conversion

Claim 2

An error diffusion process for converting a continuous tone image consisting of an array of n-bit pixels to a binary image consisting of an array of binary print values, said process consisting of plural repetitive computational cycles, said process processing each n-bit pixel in a respective cycle to produce a corresponding diffused pixel value and a corresponding one of said binary print values whereby a current n-bit pixel is processed in a current cycle, each cycle of said process comprising: computing a partial sum of pixel errors comprising differences between: (a) a set of diffused pixel values computed from n-bit pixels processed in preceding cycles not including the previous one of said cycles and (b) corresponding binary print values of said binary image; computing a partial pixel value by adding said partial sum to said current n-bit pixel; determining a sign of a pixel error of the previous cycle from most significant bits of the diffused pixel value computed in said previous cycle and from a binary print value determined in said previous cycle; producing the pixel error of said previous cycle by appending said sign bit to the n least significant bit of the diffused pixel value computed in the previous cycle; producing the diffused pixel value of the current cycle by adding said previous pixel error to said partial pixel value; and adding said diffused pixel value of said current cycle to the two's complement of a corresponding print decision threshold to produce a decision sign bit, and determining the binary print value of the current cycle from said decision sign bit.

Claim 3

The process of claim 1 wherein said corresponding print decision threshold is comprised in a matrix of ordered dither print decision thresholds.

Claim 4

The process of claim 1 further comprising: storing said diffused pixel value for use during the next cycle; and storing said pixel error of the previous cycle for use during subsequent cycles, whereby said partial sum of errors is computed from the previous pixel errors stored in preceding cycles.

Claim 5

The process of claim 1 wherein said partial sum of errors is comprised in a weighted total sum of errors whose coefficients are normalized to unity, and wherein said step of producing said diffused pixel value is preceded by the step of: multiplying said pixel error of the previous cycle by a corresponding coefficient of said weighted total sum.

Claim 6

The process of claim 2 wherein the most significant bit of said diffused pixel value is a sign bit, and wherein the step of determining the sign bit of the pixel error of the previous cycle comprises one of: (1) determining a positive sign bit if (a) the most significant bit of the previous cycle's diffused pixel value is positive and either (b) at least one of a second or third most significant bits of the previous cycle's diffused pixel value is one or (c) the previous cycle's binary pixel value is a minimum binary print value; and (2) determining a negative sign bit if either (a) the sign of the previous cycle's diffused pixel value is negative or (b) the sign bit of the previous cycle's diffused pixel value is positive, the second and third most significant bits of the previous cycle's diffused pixel value are both zero and the previous cycle's binary pixel value is a maximum binary print value.

Claim 7

The process of claim 5 wherein said minimum and maximum binary print values are zero and the maximum n-bit number, respectively, whereby the corresponding pixel error equals one of (a) the diffused pixel value if the binary print value is the minimum binary print value and (b) the diffused pixel value plus the two's complement of the maximum n-bit number if the corresponding binary print value is the maximum binary print value.

Claim 8

The process of claim 6 wherein the step of producing said diffused pixel value further comprises: adding said sign bit of said pixel error of the previous cycle to the least significant bit thereof.

Claim 9

In an error diffusion process for converting a continuous tone image comprising an array of n-bit pixels to a binary image comprising an array of binary pixels, in which an error comprising a difference between a diffused value of each one of said n-bit pixels and a corresponding one of said binary pixels is distributed in said continuous tone image among neighbor n-bit pixels in a local neighborhood of the one n-bit pixel to produce diffused pixel values for the neighboring n-bit pixels whereby each diffused pixel value comprises an n-bit pixel value and a total sum of the errors corresponding to neighboring pixels, each of said binary pixels being determined from the corresponding diffused pixel value and a corresponding print decision threshold, said process computing successive diffused pixel values for successive ones of said n-bit pixels in successive computational cycles of said process, said total sum of errors including a previous pixel error of one of said neighboring pixels processed in the previous cycle, a method for computing said previous pixel error and said diffused pixel value in each cycle, comprising: storing the diffused pixel value of each cycle for use during the next cycle; determining a sign bit of the previous pixel error for the current cycle from: (a) a most significant bit of the diffused pixel value of the previous cycle and (b) the binary pixel corresponding to the previous cycle; producing the previous pixel error for the current cycle by appending said sign bit to the n least significant bits of the diffused pixel value of the previous cycle; and producing the diffused pixel value of the current cycle by adding together: (a) said previous pixel error, (b) an n-bit pixel corresponding to said current cycle and (c) a partial sum of the errors of the neighboring pixels corresponding to the current cycle excluding said previous pixel error.

Claim 10

In an error diffusion process for converting a continuous tone image comprising an array of n-bit pixels to a binary image comprising an array of binary pixels, in which an error comprising a difference between a diffused value of each one of said n-bit pixels and a corresponding one of said binary pixels is distributed in said continuous tone image among neighbor n-bit pixels in a local neighborhood of the one n-bit pixel to produce diffused pixel values for the neighboring n-bit pixels whereby each diffused pixel value comprises an n-bit pixel value and a total sum of the errors corresponding to neighboring pixels, each of said binary pixels being determined from the corresponding diffused pixel value and a corresponding print decision threshold, said process computing successive diffused pixel values for successive ones of said n-bit pixels in successive computational cycles of said process, said total sum of errors including a previous pixel error of one of said neighboring pixels processed in the previous cycle, a method for computing said previous pixel error and said diffused pixel value in each cycle, comprising: storing the diffused pixel value of each cycle for use during the next cycle; determining a sign bit of the previous pixel error for the current cycle from: (a) a most significant bit of the diffused pixel value of the previous cycle and (b) the binary pixel corresponding to the previous cycle; producing the previous pixel error for the current cycle by appending said sign bit to the n least significant bits of the diffused pixel value of the previous cycle; and producing the diffused pixel value of the current cycle by adding together: (a) said previous pixel error, (b) an n-bit pixel corresponding to said current cycle and (c) a partial sum of the errors of the neighboring pixels corresponding to the current cycle excluding said previous pixel error.

Claim 11

The method of claim 8 further comprising: storing said previous pixel error computed in each cycle for use during subsequent cycles, whereby said partial sum of errors is computed from the previous pixel errors stored in preceding cycles.

Claim 12

The method of claim 8 wherein said total sum of errors comprises a weighted sum whose coefficients are normalized to unity, said partial sum corresponding to a portion of said weighted sum, and wherein said step of producing said diffused pixel value is preceded by the step of: multiplying said previous pixel error by a corresponding coefficient of said weighted sum.

Claim 13

The method of claim 8 wherein the most significant bit of said diffused pixel value is a sign bit and wherein the step of determining said sign bit of the previous pixel error comprises one of: (1) determining a positive sign bit if (a) the most significant bit of the previous cycle's diffused pixel value is positive and either (b) at least one of the second or third most significant bits of the previous cycle's diffused pixel value is one or (c) the previous cycle's binary pixel value is a minimum binary print value; and (2) determining a negative sign bit if either (a) the sign of the previous cycle's diffused pixel value is negative or (b) the sign bit of the previous cycle's diffused pixel value is positive, the second and third most significant bits of the previous cycle's diffused pixel value are both zero and the previous cycle's binary pixel is a maximum binary print value.

Claim 14

The method of claim 11 wherein said minimum and maximum binary print values are zero and the maximum n-bit number, respectively, whereby the corresponding pixel error equals (a) the diffused pixel value if the corresponding binary pixel is the minimum print value and (b) the diffused pixel value plus the two's complement of the maximum n-bit number if the corresponding binary pixel is the maximum print value.

Claim 15

The method of claim 12 wherein the step of producing said diffused pixel value further comprises: adding said sign bit of said previous pixel error to the least significant bit of said previous pixel error.

Claim 16

The method of claim 8 wherein each of said binary pixels is determined from the sign bit of the sum of the two's complement of said corresponding print decision threshold and the diffused pixel value.

Claim 17

An error diffusion processor apparatus for converting a continuous tone image consisting of an array of n-bit pixels to a binary image consisting of an array of binary print values corresponding to said n-bit pixels, said processor apparatus performing plural repetitive computational cycles, said processor apparatus processing each n-bit pixel in a respective computational cycle to produce a corresponding diffused pixel value and a corresponding one of said binary print values whereby said processor apparatus processes a current n-bit pixel in a current cycle, said processor apparatus comprising: means for computing a partial sum of errors consisting of differences between: (a) a set of diffused pixel values computed from n-bit pixels in preceding cycles not including a previous cycle and (b) corresponding binary print values of said binary image determined in said preceding cycles; means for computing a partial pixel value comprising means for adding said partial sum to said current n-bit pixel; means for determining a sign of a pixel error of the previous cycle from a most significant bit of the diffused pixel value computed in said previous cycle and the binary print value determined in said previous cycle; means for producing said pixel error of the previous cycle comprising means for appending said sign bit to the n least significant bits of the diffused pixel value computed in the previous cycle; means for producing the diffused pixel value of the current cycle comprising means for adding said pixel error of the previous cycle to said partial pixel value; and means for determining said binary pixel value of the current cycle by adding said diffused pixel value of said current cycle to the two's complement of a corresponding print decision threshold to produce a decision sign bit.

Claim 18

An error diffusion processor apparatus for converting a continuous tone image consisting of an array of n-bit pixels to a binary image consisting of an array of binary print values corresponding to said n-bit pixels, said processor apparatus performing plural repetitive computational cycles, said processor apparatus processing each n-bit pixel in a respective computational cycle to produce a corresponding diffused pixel value and a corresponding one of said binary print values whereby said processor apparatus processes a current n-bit pixel in a current cycle, said processor apparatus comprising: means for computing a partial sum of errors consisting of differences between: (a) a set of diffused pixel values computed from n-bit pixels in preceding cycles not including a previous cycle and (b) corresponding binary print values of said binary image determined in said preceding cycles; means for computing a partial pixel value comprising means for adding said partial sum to said current n-bit pixel; means for determining a sign of a pixel error of the previous cycle from a most significant bit of the diffused pixel value computed in said previous cycle and the binary print value determined in said previous cycle; means for producing said pixel error of the previous cycle comprising means for appending said sign bit to the n least significant bits of the diffused pixel value computed in the previous cycle; means for producing the diffused pixel value of the current cycle comprising means for adding said pixel error of the previous cycle to said partial pixel value; and means for determining said binary pixel value of the current cycle by adding said diffused pixel value of said current cycle to the two's complement of a corresponding print decision threshold to produce a decision sign bit.

Claim 19

The processor apparatus of claim 15 wherein said corresponding print decision threshold is comprised in an array of ordered dither print decision thresholds.

Claim 20

The processor apparatus of claim 15 further comprising: means for storing said diffused pixel value for use during a next cycle; and means for storing said pixel error of the previous cycle for use during subsequent cycles, whereby said partial sum of errors is computed from the previous pixel errors stored in preceding cycles.

Claim 21

The processor apparatus of claim 15 wherein said partial sum of errors is-comprised in a weighted sum of errors whose coefficients are normalized to unity, and wherein said means for producing said pixel error of the previous cycle further comprises: means for multiplying said pixel error of the previous cycle by a corresponding coefficient to said weighted sum.

Claim 22

The processor apparatus of claim 15 wherein the most significant bit of said diffused pixel value is a sign bit and wherein said means for determining said sign bit of the pixel error of the previous cycle comprises: means for determining a positive sign bit whenever (a) the most significant bit of the previous cycle's diffused pixel value is positive and either (b) at least one of the second or third most significant bits of the previous cycle's diffused pixel value is one or (c) the previous cycle's binary print value is a minimum binary print value; and means for determining a negative sign bit whenever either (a) the sign of the previous cycle's diffused pixel value is negative or (b) the sign bit of the previous cycle's diffused pixel value is positive, a second and third most significant bits of the previous cycle's diffused pixel value are both zero and the previous cycle's binary print value is a maximum binary print value.

Claim 23

The processor apparatus of claim 19 wherein said minimum and maximum binary print values are zero and the maximum n-bit number, respectively, whereby the corresponding pixel error equals (a) the diffused pixel value if the corresponding binary print value is the minimum print value and (b) the diffused pixel value plus the two's complement of a maximum n-bit number if the corresponding binary print value is the maximum print value.

Claim 24

The processor apparatus of claim 20 wherein said means for producing said diffused pixel value further comprises: carry means for adding said sign bit of said pixel error of the previous cycle to the least significant bit thereof.

Claim 25

Digital image processing apparatus for performing error diffusion to produce binary output pixel values from continuous tone n-bit input pixel values, comprising: means for storing previous pixel errors; means connected to the storing means for forming a first sum of previous errors excluding a previous pixel error; means for forming a second sum of a present input pixel value and the first sum of the previous errors; means responsive to the second sum and a previous pixel error for producing n-least significant bits of a present pixel error; latch means for holding the n-least significant bit of a present pixel error to be produced as the n-least significant bits of a subsequent previous pixel error during a subsequent computation cycle; means responsive to the second sum, a previous pixel error, and a previous output pixel for producing a sign bit of a subsequent previous pixel error; means responsive to the n-least significant bits of the subsequent previous pixel errors and the sign of the subsequent previous pixel error to produce a subsequent previous pixel error; and means responsive to the second sum, the previous pixel error and a two's complement of a threshold value for producing a binary output value.

Claim 26

Digital image processing apparatus for performing error diffusion to produce binary output pixel values from continuous tone n-bit input pixel values, comprising: means for storing previous pixel errors; means connected to the storing means for forming a first sum of previous errors excluding a previous pixel error; means for forming a second sum of a present input pixel value and the first sum of the previous errors; means responsive to the second sum and a previous pixel error for producing n-least significant bits of a present pixel error; latch means for holding the n-least significant bit of a present pixel error to be produced as the n-least significant bits of a subsequent previous pixel error during a subsequent computation cycle; means responsive to the second sum, a previous pixel error, and a previous output pixel for producing a sign bit of a subsequent previous pixel error; means responsive to the n-least significant bits of the subsequent previous pixel errors and the sign of the subsequent previous pixel error to produce a subsequent previous pixel error; and means responsive to the second sum, the previous pixel error and a two's complement of a threshold value for producing a binary output value.

Claim 27

The digital image processing apparatus claimed in claim 22, further including means for storing the two's compliment of a plurality of threshold values and means for periodically selecting each of said plurality of threshold values for performing dither error diffusion.