Method and apparatus for halftone rendering of a gray scale image using a blue noise mask

• US 5,726,772 A
• Filed: 10/06/1995
• Issued: 03/10/1998
• Est. Priority Date: 12/04/1990
• Status: Expired due to Term

• Current Assignee: Research Corporation Technologies
• Original Assignee: Research Corporation Technologies
• Inventors: Mitsa, Theophano, Parker, Kevin J.
• Primary Examiner(s): Coles, Sr., Edward L.
• Assistant Examiner(s): LEE, CHEUKFAN
• Application Number:
  US08/540,038
• Time in Patent Office: 886 Days
• Field of Search: 358/456, 358/465, 358/466, 358/455, 358/457, 358/460, 358/444, 358/534, 358/535, 358/523, 358/524, 358/533, 395/112, 395/117
• US Class Current: 358/3.19
• CPC Class Codes: G06T 3/40 Scaling of whole images or parts thereof, e.g. expanding or contracting
• CPC Class Codes: G06T 3/4084 in the transform domain, e.g. fast Fourier transform [FFT] domain scaling
• CPC Class Codes: H04N 1/40075 Descreening, i.e. converting a halftone signal into a corresponding continuous-tone signal; Rescreening, i.e. combined descreening and halftoning
• CPC Class Codes: H04N 1/4051 producing a dispersed dots halftone pattern, the dots having substantially the same size different sizes H04N1/4057
• CPC Class Codes: H04N 1/4105 for halftone screened pictures

Abstract

A method of and system for rendering a halftone image of a gray scale image by utilizing a pixel-by-pixel comparison of the gray scale image against a blue noise mask is disclosed in which the gray scale image is scanned on a pixel-by-pixel basis and compared on a pixel-by-pixel basis to an array of corresponding data points contained in a blue noise mask stored in a PROM or computer memory in order to produce the desired halftoned image. Both digital and optically implemented halftone methods are disclosed. Application specific modifications of the blue noise mask as well as its use for producing halftoned color images are also disclosed.

Claims

1. A machine comprising a computer readable storage device which stores a dither matrix for use in halftoning image information and a comparator responsive to said computer readable storage device, said dither matrix comprising at least one array, said at least one array, when thresholded at a number of levels produces a number of dot profiles, a plurality of said number of dot profiles each having a power spectrum substantially characteristic of a blue noise power spectrum for the level at which such dot profile is produced.

2. The machine of claim 1, wherein said computer readable storage device comprises a computer memory.

3. The machine of claim 1, wherein a majority of said number of dot profiles have a power spectrum substantially characteristic of a blue noise power spectrum for the level at which such dot profile is produced.

4. The machine of claim 1, wherein substantially all of said number of dot profiles have a power spectrum substantially characteristic of a blue noise power spectrum for the level at which such dot profile is produced.

5. The machine of claim 1, wherein the power spectra are modified by human visual response.

6. A machine comprising a computer readable storage device which stores a dither matrix for use in halftoning image information and comparator responsive to said dither matrix, said dither matrix comprising at least one thresholdable array designed to produce a plurality of locally aperiodic dot profiles with wraparound properties.

7. The machine of claim 6, wherein said array comprises a multibit array.

8. The machine of claim 6, wherein each of said dot profiles is associated with a respective threshold level.

9. The machine of claim 6, wherein said array comprises a cumulative array.

10. The machine of claim 6, wherein each of said dot profiles is visually pleasing.

11. The machine of claim 6, wherein said comparator is further responsive to information derived from said image information.

12. The machine of claim 6, wherein said image comprises a color image.

13. The machine of claim 6, wherein said computer readable storage device comprises a computer memory.

14. The machine of claim 6, wherein each dot profile is matched to a blue noise power spectrum modified by human visual response.

15. A machine comprising a computer readable storage device which stores a dither matrix for a halftoning process and a comparator responsive to said computer readable storage device, said dither matrix comprising a thresholdable multibit array, said multibit array, when thresholded at a number of levels, producing a plurality of substantially blue noise dot profiles, each dot profile appropriate for the respective level.

16. The machine of claim 15, wherein said multibit array comprises a two-dimensional array.

17. The machine of claim 15, wherein said computer readable storage device comprises a computer memory.

18. The machine of claim 17, wherein said computer memory comprises a read only memory.

19. The machine of claim 15, wherein said computer readable storage device is incorporated into a digital computer.

20. The machine of claim 15, wherein the dot profiles are matched to respective blue noise power spectra modified by human visual response.

21. The machine of claim 15, wherein said multibit array, when thresholded at a number of levels, produces a majority of substantially blue noise dot profiles.

22. The machine of claim 15, wherein said multibit array, when thresholded at a number of levels, produces substantially all substantially blue noise dot profiles.

23. A machine comprising a computer readable storage device which stores a dither matrix for a halftoning process and a comparator responsive to said computer readable storage device, said dither matrix comprising a thresholdable array that, when thresholded at a number of levels, produces a number of dot profiles, a plurality of said dot profiles being visually pleasing.

24. The machine of claim 23, wherein a plurality of said number of dot profiles are respectively locally aperiodic and substantially isotropic dot profiles having small low-frequency components.

25. The machine of claim 24, wherein said dot profiles each have a power spectrum characterized by a respective principal frequency, said small low-frequency components being below the principal frequency, and at least a plurality of said dot profiles each having high-frequency components above the respective principal frequency, at least some of said high-frequency components being larger than said low-frequency components.

26. The machine of claim 25, wherein each of said plurality of levels is associated with a respective level, and said principal frequency varies with said level.

27. The machine of claim 26, wherein said principal frequency varies with said level according to a nonlinear function.

28. The machine of claim 23, wherein said computer readable storage device comprises a computer memory.

29. The machine of claim 23, wherein the dot profiles are matched to respective power spectra modified by human visual response.

30. The machine of claim 23, wherein a plurality of said number of dot profiles are substantially isotropic.

31. The machine of claim 23, wherein a majority of said number of dot profiles are visually pleasing.

32. The machine of claim 31, wherein said majority of said number of said dot profiles are respectively locally aperiodic and substantially isotropic dot profiles having small low-frequency components.

33. The machine of claim 23, wherein substantially all of said number of dot profiles are visually pleasing.

34. The machine of claim 33, wherein substantially all of said number of said dot profiles are respectively locally aperiodic and substantially isotropic dot profiles having small low-frequency components.

35. An apparatus for use in halftoning an image, said apparatus comprising a dither matrix stored in a computer readable storage device and a comparator responsive to said computer readable storage device, said dither matrix comprising a multibit array that can be thresholded, said multibit array, when thresholded at a plurality of respective levels, producing a plurality of substantially blue noise dot profiles, each dot profile appropriate for the respective level.

36. The apparatus of claim 35, further comprising a display device responsive to said comparator, said display device receiving a halftoned array output from said comparator and producing a halftoned output image.

37. The apparatus of claim 35, wherein said computer readable storage device comprises a computer memory.

38. The apparatus of claim 35, wherein the dot profiles are matched to respective power spectra modified by human visual response.

39. A computer readable memory device comprising a thresholdable halftoning mask, said halftoning mask producing a plurality of dot profiles when thresholded at respective levels, and at least a plurality of said dot profiles having a substantially blue noise power spectrum appropriate for the respective level and a comparator responsive to said computer readable memory device.

40. The computer readable memory device of claim 39, wherein said mask is stored as an array.

41. The computer readable memory device of claim 40, wherein said array comprises a plurality of storage elements, each storage element containing a respective multibit data value.

42. A combination of a printing device and the computer readable memory device of claim 41.

43. The combination of claim 42, wherein said printing device comprises at least one of a laser printer, an ink jet printer, a thermal printer, a thermal wax printer, a dye-sublimation printer and a bubble jet printer.

44. A combination of a comparator and the computer readable memory device of claim 43, said comparator having a first input, a second input, and an output, said first input responsive to said memory device.

45. The combination of claim 44, further comprising a scanner for digitizing an input image and generating an image array, said image array comprising a plurality of values, and wherein said second input is responsive to said scanner.

46. The combination of claim 45, wherein said comparator performs a comparison between signals appearing on said first and second inputs.

47. The combination of claim 46, further comprising a display responsive to said comparator.

48. The combination of claim 47, wherein said display comprises a binary display.

49. A combination of a recording device and the computer readable memory device of claim 41.

50. In combination, a facsimile machine and the computer readable memory device of claim 39.

51. The memory device of claim 39, wherein the power spectra are modified by human visual response.

52. A machine comprising a computer readable storage device which stores a dither matrix for use in halftoning image information and a comparator responsive to said computer readable storage device, said dither matrix comprising at least one thresholdable array designed to produce a plurality of locally aperiodic, non-white noise dot profiles when thresholded at respective levels.

53. The machine of claim 52, wherein the dot profiles are substantially blue noise dot profiles.

55. The machine of claim 52, wherein the dot profiles have small low-frequency components.

56. The machine of claim 52, wherein the dot profiles have smaller low-frequency components than mid-range or high-frequency components.

54. The machine of 52, wherein each of the dot profiles has a respective power spectrum substantially characteristic of a blue noise power spectrum.

57. A computer readable memory device comprising a thresholdable halftoning mask, said halftoning mask designed to produce a plurality of visually pleasing dot profiles when thresholded at a number of levels and a comparator responsive to said computer readable memory device.

58. The memory device of claim 57, wherein the dot profiles are substantially blue noise dot profiles.

59. The memory device of claim 57, wherein each of the dot profiles has a respective power spectrum substantially characteristic of a blue noise power spectrum.

60. The memory device of claim 57, wherein the dot profiles have small low-frequency components.

61. The computer readable memory device of claim 57, wherein said visually pleasing dot profiles are locally aperiodic, non-white noise dot profiles.

62. The computer readable memory device of claim 57, wherein said halftoning mask is designed to produce a majority of visually pleasing dot profiles when thresholded at a number of levels.

63. The computer readable memory device of claim 57, wherein said halftoning mask is designed to produce substantially all visually pleasing dot profiles when thresholded at a number of levels.

64. The computer readable memory device of claim 63, wherein said visually pleasing dot profiles are locally aperiodic, non-white noise dot profiles.

65. The computer readable memory device of claim 64, wherein said visually pleasing dot profiles are locally aperiodic, non-white noise dot profiles.

66. A machine comprising a computer readable storage device which stores an array for use in halftoning image information, said array comprising a non-white noise, locally aperiodic, thresholdable dither matrix and a comparator responsive to said dither matrix.

67. The machine of claim 66, wherein said array comprises a blue-noise, locally aperiodic thresholdable matrix.

68. The machine of claim 66, wherein said array comprises a multibit array.

69. The machine of claim 66, wherein said array produces a plurality of locally aperiodic dot profiles with wraparound properties, each of said dot profiles being associated with a respective threshold level.

70. The machine of claim 66, wherein said array comprises a cumulative array.

71. The machine of claim 66, wherein said dither matrix is designed to produce a plurality of locally aperiodic dot profiles, and wherein each of said dot profiles is visually pleasing.

72. The machine of claim 66, wherein said comparator is further responsive to information derived from an image.

73. The machine of claim 72, wherein said image comprises a color image.

74. The machine of claim 66, wherein said computer readable storage device comprises a computer memory.

75. A machine comprising a computer readable storage device which stores an array for use in halftoning image information, said array comprising a non-white noise, non-ordered thresholdable dither matrix and a comparator responsive to said dither matrix.

76. The machine of claim 75, wherein said array comprises a blue noise, non-ordered thresholdable dither matrix.

77. Apparatus for generating a modified blue noise mask array in which said modified blue noise mask array may be used to generate a more pleasing halftoned image than a non-modified blue noise mask array, comprising:

a) a reading device for reading each of the values of the blue noise mask array to be modified;

b) a receiving device for receiving maximum and minimum predetermined values input by a user;

c) a modifying device for modifying each value of said blue noise mask array using at least one of said maximum and minimum predetermined values and a direct value mapping function;

d) a first comparing device for comparing each of said values of said modified blue noise mask array to said maximum predetermined value and replacing said value if it exceeds said maximum predetermined value; and

e) a second comparing device for comparing each of said values of said modified blue noise mask array to said minimum predetermined value and replacing said value if it is less than said minimum predetermined value;

wherein said maximum and minimum predetermined values input by said user and said direct value mapping function are selected to compensate for characteristics of at least one of printer and display devices used by said user so as to form a more pleasing halftoned image.

78. The apparatus of claim 77, further including a memory for storing said modified blue noise mask array.