Electronic high-fidelity screenless conversion system

• US 5,331,430 A
• Filed: 10/11/1991
• Issued: 07/19/1994
• Est. Priority Date: 10/11/1991
• Status: Expired due to Fees

• Current Assignee: Graphic Arts Technical Foundation Incorporated A Not-For-Profit Corporation of The State of Delaware
• Original Assignee: RR Donnelley & Sons Company
• Inventors: Rodriguez, Michael A., Xie, Zhenhua
• Primary Examiner(s): Coles, Sr., Edward L.
• Assistant Examiner(s): Rogers, Scott A.
• Application Number:
  US07/775,334
• Time in Patent Office: 1,012 Days
• Field of Search: 358/456, 358/458, 358/298, 358/296, 358/455, 358/448, 358/80, 358/75, 358/445, 358/447, 101/450.1, 101/453
• US Class Current: 358/3.1
• CPC Class Codes: H04N 1/4052 by error diffusion, i.e. transferring the binarising error to neighbouring dot decisions

Abstract

A system is disclosed for converting a continuous tone value to an output value having a first level or a second level. A first error magnitude is generated based upon continuous tone values already converted, continuous tone values not yet converted and an output value having the first level assumed for the continuous tone value undergoing conversion. A second error magnitude is similarly generated except that an output value having the second level is assumed for the continuous tone value undergoing conversion. If the first error magnitude is less than the second error magnitude, then the continuous tone value undergoing conversion is converted to the output value having the first level and, otherwise, the continuous tone value undergoing conversion is converted to the output value having the second level. The error corresponding to the converted lineary value is diffused in a predetermined manner to neighboring continuous tone values which have not yet been converted.

Claims

1. A system for converting input values into output values, each of said input values having one of at least M possible levels and each of said output values having one of N possible levels, where M is greater than N, said system converting, in turn, each of said input values into a corresponding output value so that, at a given instant in time, an input value undergoing conversion has before it previously converted input values and after it input values yet to be converted, said system comprising:

error generating means for generating at least first and second errors for said input value undergoing conversion, said first error being based upon an output value corresponding to a previously converted input value, based upon an output value estimated from a corresponding input value yet to be converted, and based upon an output value having a first level assumed for said input value undergoing conversion, and said second error being based upon an output value corresponding to a previously converted input value, based upon an output value estimated from a corresponding input value yet to be converted, and based upon an output value having a second level assumed for said input value undergoing conversion;

output value setting means for setting said input value undergoing conversion to an output value having said first level if the absolute value of said first error is less than the absolute value of said second error or to an output value having said second level if the absolute value of said first error is greater than the absolute value of said second error; and

,

diffusing means for diffusing, to a selected number of said input values yet to be converted, said first error if said input value undergoing conversion is set to said output value having said first level or said second error if said input value undergoing conversion is set to said output value having said second level.

2. The system of claim 1 wherein said error generating means predicts an output value for said input value yet to be converted by comparing said input value yet to be converted to a threshold, by converting said input value yet to be converted to a predicted output value having said first level or to a predicted output value having said second level depending upon whether said input value yet to be converted is below or above said threshold, and by diffusing the difference between said input value yet to be converted and said corresponding predicted output value to a subsequent predetermined number of input values yet to be converted.

3. The system of claim 2 wherein said threshold is a random threshold.

4. The system of claim 2 wherein said error generating means diffuses said difference between said input value yet to be converted and said corresponding predicted output value in a serpentine manner.

5. The system of claim 2 wherein said error generating means comprises digital resampling means for increasing said number of input values.

6. The system of claim 1 wherein said error generating means comprises digital resampling means for increasing said number of input values.

7. A system for converting continuous tone values into corresponding output values, said system converting, in turn, each of said continuous tone values to a corresponding output value so that, at a given instant in time, a continuous tone value undergoing conversion has before it previously converted continuous tone values and after it continuous tone values yet to be converted, said system comprising:

error generating means for generating first and second errors for said continuous tone value undergoing conversion, said first error being based upon a first set of output values multiplied by a first set of corresponding filter values wherein each output value of said first set of output values corresponds to a continuous tone value in a first set of previously converted continuous tone values, (b) a second set of output values multiplied by a second set of corresponding filter values wherein each output value of said second set of output values is predicted from a corresponding continuous tone value in a second set of continuous tone values yet to be converted, and (c) an output value having an assumed first level multiplied by a corresponding filter value, and said second error being based upon (a) said first set of output values multiplied by said first set of corresponding filter values, (b) said second set of output values multiplied by said second set of corresponding filter values, and (c) an output value having an assumed second level multiplied by said corresponding filter value;

output value setting means for setting said continuous tone value undergoing conversion to said output value having said first level if the absolute value of said first error is less than the absolute value of said second error or to said output value having said second level if the absolute value of said first error is greater than the absolute value of said second error; and

,

diffusing means for diffusing, to a predetermined number of said continuous tone values yet to be converted, said first error if said continuous tone value undergoing conversion is set to said output value having said first level or said second error if said continuous tone value undergoing conversion is set to said output value having said second level.

8. The system of claim 7 wherein said error generating means predicts, one at a time, each output value of said second set of output values (a) by comparing a continuous tone value in said second set of continuous tone values, to a threshold, (b) by converting said continuous tone value in said second set of continuous tone values, to a predicted output value having said first level or to a predicted output value having said second level depending upon whether said continuous tone value in said second set of continuous tone values, is below or above said threshold, and (c) by diffusing the difference between said continuous tone value in said second set of continuous tone values, and said corresponding predicted output value to a selected number of subsequent continuous tone values in said second set of continuous tone values.

9. The system of claim 8 wherein said threshold is a random threshold.

10. The system of claim 8 wherein said error generating means diffuses, in a serpentine manner, said difference between said continuous tone value in said second set of continuous tone values and said corresponding predicted output value to a selected number of subsequent continuous tone values in said second set of continuous tone values.

11. The system of claim 8 wherein said error generating means generates said first error for said continuous tone value undergoing conversion by subtracting, from said continuous tone value undergoing conversion, (a) each product resulting from multiplying each output value of said first set of output values by a corresponding filter value from said first set of filter values, (b) each product resulting from multiplying each output value of said second set of output values by a corresponding filter value from said second set of filter values, and (c) said output value having said assumed first level multiplied by a corresponding filter value, and wherein said error generating means generates said second error for said continuous tone value undergoing conversion by subtracting, from said continuous tone value undergoing conversion, (a) said each product resulting from multiplying each output value of said first set of output values by a corresponding filter value from said first set of filter values, (b) said each product resulting from multiplying each output value of said second set of output values by a corresponding filter value from said second set of filter values, and (c) said output value having said assumed second level multiplied by a corresponding filter value.

12. The system of claim 8 wherein said error generating means comprises digital resampling means for increasing said number of continuous tone values.

13. The system of claim 7 wherein said error generating means generates said first error for said continuous tone value undergoing conversion by subtracting, from said continuous tone value undergoing conversion, (a) each product resulting from multiplying each output value of said first set of output values by a corresponding filter value from said first set of filter values, (b) each product resulting from multiplying each output value of said second set of output values by a corresponding filter value from said second set of filter values, and (c) said output value having said assumed first level multiplied by a corresponding filter value, and wherein said error generating means generates said second error for said continuous tone value undergoing conversion by subtracting, from said continuous tone value undergoing conversion, (a) said each product resulting from multiplying each output value of said first set of output values by a corresponding filter value from said first set of filter values, (b) said each product resulting from multiplying each output value of said second set of output values by a corresponding filter value from said second set of filter values, and (c) said output value having said assumed second level multiplied by a corresponding filter value.

14. The system of claim 7 wherein said error generating means comprises digital resampling means for increasing said number of continuous tone values.

15. A method of converting input values to corresponding output values, each of said input values having one of at least M possible levels and each of said output values having one of N possible levels, where M is greater than N, said method comprising the following steps:

(a) multiplying each output value of a first set of output values by a corresponding filter value from a first set of filter values wherein each output value of said first set of output values corresponds to an input value in a first set of previously converted input values;

(b) predicting a second set of output values wherein each output value of said second set of output values corresponds to an input value in a second set of input values yet to be converted;

(c) multiplying each output value of said predicted second set of said output values by a corresponding filter value from a second set of filter values;

(d) multiplying a filter value corresponding to an input value undergoing conversion by an output value having an assumed first level;

(e) multiplying said filter value corresponding to said input value undergoing conversion by an output value having an assumed second level;

(f) providing a first error by subtracting the results of steps (a), (c) and (d) from said input value undergoing conversion;

(g) providing a second error by subtracting the results of steps (a), (c) and (e) from said input value undergoing conversion;

(h) converting said input value undergoing conversion to an output value having said first level if the absolute value of said first error is smaller than the absolute value of said second error;

(i) converting said input value undergoing conversion to an output value having said second level if the absolute value of said first error is greater than the absolute value of said second error;

(j) diffusing, to a predetermined number of said input values yet to be converted, said first error if said input value undergoing conversion is converted to said output value having said first level or said second error if said input value undergoing conversion is converted to said output value having said second level; and

(k) repeating steps (a)-(j) for each of the input values yet to be converted.

16. The method of claim 15 wherein said step of predicting said second set of output values comprises the step of predicting, one at a time, each output value of said second set of output values by (i) comparing a corresponding input value in said second set of input values to a threshold, (ii) converting said corresponding input value in said second set of input values to a predicted output value having said first level or to a predicted output value having said second level depending upon whether said corresponding input value in said second set of input values is below or above said threshold, and (iii) diffusing the difference between said corresponding input value in said second set of input values and the resulting predicted output value to a subsequent predetermined number of input values in said second set of input values.

17. The method of claim 16 wherein said step of comparing said corresponding input value in said second set of input values to a threshold comprises the step of comparing said corresponding input value in said second set of input values to a random threshold.

18. The method of claim 16 wherein said step of diffusing the difference between said corresponding input value in said second set of input values and said resulting predicted output value to a subsequent predetermined number of said input values in said second set of input values comprises the step of diffusing, in a serpentine manner, the difference between said corresponding input value in said second set of input values and said resulting predicted output value to a subsequent predetermined number of said input values in said second set of input values.

19. The method of claim 16 further comprising the step of increasing said number of input values.

20. The method of claim 15 further comprising the step of increasing said number of input values.

21. A method of converting continuous tone values to corresponding output values such tat, at a given time during conversion, said continuous tone values include continuous tone values already converted, a continuous tone value undergoing conversion, and continuous tone values yet to be converted, said method comprising the following steps:

(a) deriving a first error based upon an output value corresponding to a continuous tone value already converted, based upon an output value predicted rom a continuous toe value yet to be converted, and based upon an output value having a first level assumed for said continuous tone value undergoing conversion;

(b) deriving a second error based upon said output value corresponding to said continuous tone value already converted, based upon said output value predicted form said at least on continuous tone value yet to be converted, and based upon an output value having a second level assumed for said continuous tone value undergoing conversion;

(c) converting said continuous tone value undergoing conversion to said output value having said first level if the absolute value of said first error is smaller than the absolute value of said second error or to said output value having said second level if the absolute value of said first error is greater than the absolute value of said second error.

(d) diffusing, to a predetermined number of said continuous tone values yet to be converted, said first error if said continuous tone value undergoing conversion is converted to said output value having said first level or said second error if said continuous tone value undergoing conversion is converted to said output value having said second level;

(e) repeating steps (a)-(d) for each of said continuous tone values yet to be converted.

22. The method of claim 21 wherein said step of deriving said first error and said step of deriving said second error include the step of predicting said output value predicted from said continuous tone value yet to be converted by comparing said continuous tone value yet to be converted to a threshold, by converting said continuous tone value yet to be converted to a predicted output value having a first level or to a predicted output value having a second level depending upon whether said continuous tone value yet to be converted is below or above said threshold, and by diffusing the difference between said continuous tone value yet to be converted and said corresponding predicted output value to a predetermined, subsequent number of continuous tone values yet to be converted.

23. The method of claim 22 wherein said step of predicting said output value predicted from said continuous tone value yet to be converted includes the step of comparing each of said continuous tone values yet to be converted to a random threshold.

24. The method of claim 22 wherein said step of predicting said output value predicted from said continuous tone value yet to be converted comprises the step of diffusing, in a serpentine manner, the difference between said continuous tone value yet to be converted and said corresponding predicted output value to a predetermined, subsequent number of continuous tone values yet to be converted.

25. The method of claim 22 further comprising the step of increasing said number of continuous tone values.

26. The method of claim 21 further comprising the step of increasing said number of continuous tone values.

27. A system for plotting dots on a film in response to continuous tone values generated by scanning an image to be reproduced, said system comprising:

screenless conversion means for converting, said continuous tone values to corresponding output values wherein a continuous tone value undergoing conversion is converted by the use of predicted output values and converted output values in a symmetrical region surrounding said continuous tone value undergoing conversion; and

,

film plotting means for plotting dots onto a film in response to said output values, said dots representing an image to be reproduced.

28. The system of claim 27 wherein said screenless conversion means comprises value conversion means for converting each continuous tone value to a corresponding output value by (a) determining first and second errors based upon output values having corresponding first and second levels assumed for a continuous tone value undergoing conversion, (b) converting said continuous tone value undergoing conversion, (b) converting said continuous tone value undergoing conversion to an output value having said first level if the absolute value of said first error is less than the absolute value of said second error or to an output value having said second level f the absolute value of said first error is greater than the absolute value of said second error, and (c) diffusing , to a predetermined number of continuous tone values yet to be converted, said first error if said continuous tone value undergoing conversion is converted to said output value having said first level or said second error if said continuous tone value undergoing conversion is converted to said output value having said second level.

29. The system of claim 28 wherein said screenless conversion means comprises digital resampling means for increasing said number of continuous tone values.

30. The system of claim 27 wherein said screenless conversion means comprises (a) error generating means for generating a first error based upon output values corresponding to a selected number of previously converted continuous tone values, based upon output values predicted from a selected number of continuous tone values yet to be converted, and based upon an output value having a first level assumed for a continuous tone value undergoing conversion and for generating a second error based upon said output values corresponding to said selected number of previously converted continuous tone values, based said upon output values predicted from said selected number of continuous tone values yet to be converted, and based upon an output value having a second level assumed for said continuous tone value undergoing conversion, (b) output value setting means for setting said continuous tone value undergoing conversion to said output value having said first level if the absolute value of said first error is less than the absolute value of said second error or to said output value having said second level if the absolute value of said first error is greater than the absolute value of said second error, and (c) diffusing means for diffusing, to a predetermined number of continuous tone values yet to be converted, said first error if said continuous tone value undergoing conversion is set to said output value having said first level or said second error if said continuous tone value undergoing conversion is set to said output value having said second level.

31. The system of claim 30 wherein said error generating means predicts, one at a time, output values form said selected number of continuous tone values yet to be converted by comparing a continuous tone value of said selected number of continuous tone values yet to be converted to a threshold, by converting said continuous tone value of said selected number of continuous tone values yet to be converted to a predicted output value having said first level or to a predicted output value having said second level depending upon whether said corresponding continuous tone value of said selected number of continuous tone values yet to be converted is below or above said threshold, and by diffusing the difference between said continuous tone value of said selected number of continuous tone values yet to be converted and the corresponding predicted output value to which it is converted to a subsequent predetermined number of said continuous tone values in said selected number of continuous tone values yet to be converted.

32. The system of claim 31 wherein said threshold is a random threshold.

33. The system of claim 31 wherein said error generating means diffuses said difference in a serpentine manner.

34. The system of claim 31 wherein said screenless conversion means comprises digital resampling means for increasing said number of continuous tone values.

35. The system of claim 27 wherein said screenless conversion means comprises digital resampling means for increasing said number of continuous tone values.

36. A system for forming printing plates directly from output values converted from continuous tone values generated by scanning an image to be reproduced, said system comprising:

screenless conversion means for converting each of said continuous tone values to a corresponding output value by (a) determining first and second errors based upon output values having first and second levels respectively assumed for a continuous tone value undergoing conversion, (b) converting said continuous tone value undergoing conversion to an output value having said first level fi the absolute value of said first error is less than the absolute value of said second error or to an output value having said second level if the absolute value of said first error is greater than the absolute value of said second error, and (c) diffusing, to a predetermined number of continuous tone values yet to be converted, said first error if said continuous tone value undergoing conversion is converted to said output value having said first level or said second error if said continuous tone value undergoing conversion is converted to said output value having said second level; and

plate forming means for forming said printing plates directly from said output values.

37. The system of claim 36 wherein said screenless conversion means comprises digital resampling means for increasing said number of continuous tone values.

38. The system of claim 36 wherein said screenless conversion means comprises error generating means for generating said first error based upon output values corresponding to a selected number of previously converted continuous tone values, based upon output values estimated from a selected number of continuous tone values yet to be converted, and based upon an output value having said first level assumed for said continuous tone value undergoing conversion and for generating said second error based upon said output values corresponding to said selected number of previously converted continuous tone values, based upon said output values estimated from said selected number of continuous tone values yet to be converted, and based upon an output value having said second level assumed for said continuous tone value undergoing conversion.

39. The system of claim 38 wherein said error generating means predicts, one at a time, output values from said selected number of continuous tone values yet to be converted by comparing a continuous tone value of said selected number of continuous tone values yet to be converted to a threshold, by converting said continuous tone value of said selected number of continuous tone values yet to be converted to a predicted output value having said first level or to a predicted output value having said second level depending upon whether continuous tone value of said selected number of continuous tone values yet to be converted is below or above said threshold, and by diffusing the difference between said continuous tone value of said selected number of continuous tone values yet to be converted and the corresponding predicted output value to which it is converted to a subsequent predetermined number of said selected number of continuous tone values yet to be converted.

40. The system of claim 39 wherein said threshold is a random threshold.

41. The system of claim 39 wherein said error generating means diffuses said difference in a serpentine manner.

42. The system of claim 39 wherein said random screening means comprises digital resampling means for increasing said number of continuous tone values.

43. The system of claim 36 wherein said random screening means comprises digital resampling means for increasing said number of continuous tone values.

44. A screenless conversion method of converting regularly scanned data into output values comprising the following steps:

(a) descreening said regularly screened data into continuous tone values;

(b) determining, for a continuous tone value undergoing conversion, first and second errors based upon output values having corresponding first and second levels assumed for said continuous tone value undergoing conversion;

(c) converting said continuous tone value undergoing conversion to an output value having said first level if the absolute value of said first error is less than the absolute value of said second error or to an output value having said second level if the absolute value of said first error is greater than the absolute value of said second error; and

,

(d) diffusing, to a predetermined number of continuous tone values yet to be converted, said first error if said continuous tone value undergoing conversion is converted to said output value having said first level or said second error if said continuous tone value undergoing conversion is converted to said output value having said second level.

45. The method of claim 44 wherein said step of converting said plurality of continuous tone values to output values by the use of error diffusion comprises the step of increasing said number of continuous tone values.

46. The method of claim 44 wherein said step of determining first and second errors comprises the steps of (a) generating said first error based upon output values corresponding to a selected number of previously converted continuous tone values, based upon output vales predicted from a selected number of continuous tone values yet to be converted, and based upon an output value having said first level assumed for said continuous tone value undergoing conversion, and (b) generating said second error based upon said output values corresponding to said selected number of previously converted continuous tone values, based upon said output values predicted from said selected number of continuous tone values yet to be converted, and based upon an output value having said second level assumed for said continuous tone value undergoing conversion.

47. The method of claim 46 wherein said step of converting said continuous tone value undergoing conversion comprises the step of predicting, one at a time, output values for said selected number of continuous tone values yet to be converted by comparing continuous tone value of said selected number of continuous tone values yet to be converted to a threshold, by converting said continuous tone value of said selected number of continuous tone values yet to be converted to a predicted output value having said first level or to a predicted output value having said second level depending upon whether said continuous tone value of said selected number of continuous tone values yet to be converted is below or above said threshold, and by diffusing the difference between said continuous tone value of said selected number of continuous tone values yet to be converted and the corresponding predicted output value to which it is converted to a subsequent predetermined number of said selected number of continuous tone values yet to be converted.

48. The method of claim 47 wherein said step of predicting, one at a time, output values for said selected number of continuous tone values yet to be converted comprises the step of comparing said continuous tone value of said selected number of continuous tone values yet to be converted to a random threshold.

49. The method of claim 47 wherein said step of predicting, one at a time, output values for said selected number of continuous tone values yet to be converted comprises the step of diffusing said difference in a serpentine manner.

50. The method of claim 46 wherein said step of converting said plurality of continuous tone values to output values by the use of error diffusion comprises the step of increasing said number of continuous tone values.

51. The method of claim 46 wherein said step of descreening said regularly screened data into a plurality of continuous tone values comprises the step of scanning said regularly screened data and integrating said regularly screened data to produce said plurality of continuous tone values.

52. A reproduction system comprising:

input means for providing continuous tone values based upon an original to be reproduced;

screenless conversion means for converting each of said continuous tone values into a corresponding output value by (a) determining first and second errors based upon output values having corresponding first and second levels assumed for a continuous tone value undergoing conversion, (b) converting said continuous tone value undergoing conversion to an output value having said first level if the absolute value of said first error is less than the absolute value of said second error or to an output value having said second level if the absolute value of said first error is greater than the absolute value of said second error, and (c) diffusing, to a predetermined number of continuous tone values yet to be converted, said first error if said continuous tone value undergoing conversion is converted to said output value having said first level or said second error if said continuous tone value undergoing conversion is converted to said output value having said second level; and

proofing means for proofing said output values to ensure that said output values represent a desired reproduction of said original.

53. The system of claim 52 wherein said output values have a resolution selected to match a resolution at which said proofing means operates.

54. The system of claim 52 wherein said screenless conversion means comprises digital resampling means for increasing said number of continuous tone values.

55. The system of claim 52 wherein said screenless conversion means comprises error generating means for generating said first error based upon output values corresponding to a selected number of previously converted continuous tone values, based upon output values predicted from a selected number of continuous tone values yet to be converted, and based upon an output value having said first level assumed for said continuous tone value undergoing conversion and for generating said second error based upon said output values corresponding to said selected number of previously converted continuous tone values, based upon said output values predicted from said selected number of continuous tone values yet to be converted, and based upon an output value having said second level assumed for said continuous tone value undergoing conversion.

56. The system of claim 55 wherein said error generating means predicts, one at a time, output values for said selected number of continuous tone values yet to be converted by comparing a continuous tone value of said selected number of continuous tone values yet to be converted to a threshold, by converting said continuous tone value of said selected number of continuous tone values yet to be converted to a predicted output value having said first level or to a predicted output value having said second level depending upon whether said continuous tone value of said selected number of continuous tone values yet to be converted is below or above said threshold, and by diffusing the difference between said continuous tone value of said selected number of continuous tone values yet to be converted and the corresponding predicted output value to which it is converted to a subsequent predetermined number of said selected number of continuous tone values yet to be converted.

57. The system of claim 56 wherein said threshold is a random threshold.

58. The system of claim 56 wherein said error generating means diffuses said difference in a serpentine manner.

59. The system of claim 56 wherein said screenless conversion means comprises digital resampling means for increasing said number of continuous tone values.

60. The system of claim 55 wherein said output values have a resolution selected to match a resolution at which said proofing means operates.