Method and apparatus for halftone rendering of a gray scale image using a blue noise mask
Patent 5477305 Issued on December 19, 1995. Estimated Expiration Date: November 22, 2014. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.
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.
Other References
"Digital Color Reproduction," IBM Technical Disclosure Bulletin, vol. 28, No. 1, Jun. 1985, pp. 438-439
Netravali et al., "A Picture Browsing System," IFEE Transaction of Communications, vol. Com-29, No. 12, Dec. 1981
G. Goertzel, G. R. Thompson, "Digital Halftoning on the IBM 4250 Printer", I.B.M. Journal of Development, Jan. 1987
"Dithering with Blue Noise", Robert A. Ulichney, Proceedings of the IEEE, vol. 76, No. 1, Jan. 1988, pp. 56-79
Pirsch et al., "Transmission of Gray Level Images by Multilevel Dither Techniques", Computers & Graphics, vol. 7, 1983, pp. 31-44
Yoshida et al., "Pel Pattern Predictive Coding of Dithered Images" Fujitsu-Scientific and Technical Journal, Mar. 1984 pp. 99-118
Allebach, J. P. and B. Liu (1976) "Random quasi-periodic halftone process", J. Opt. Soc. Am., vol. 66, pp. 909-917
Allebach, J. P. and B. Liu (1977) "Analysis of halftone dot profile and aliasing in the discrete binary representation on images", J. Opt. Soc. Am., vol. 67, pp. 1147-1154
Allebach, J. P. (1978) "Random nucleated halftone screening", Photogr. Sci. Eng., vol. 22, No. 2, pp. 89-91
Allebach, J. P. (1980) "Binary display of images when spot size exceeds step size", Applied Optics, vol. 19, pp. 2513-2519
Allebach, J. P. (1981) "Visual model-based algorithms for halftoning images", Proc. SPIE, vol. 310, pp. 151-158
Anastassiou, D. and K. S. Pennington (1982) "Digital Halftoning of Images", IBM J. Res. Develop., vol. 26, pp. 687-697
Baldwin, M. W. (1940) "The subjective sharpness of simulated television images", Proc. IRE, Oct., pp. 458-468
Bartlett, M. S. (1955) An Introduction to Stochastic Processes with Special Reference to Methods and Applications. New York: Cambridge University Press, pp. 274-284
Bayer, B. E. (1973) "An optimum method for two level rendition of continuous-tone pictures", Proc. IEEE Int. Conf. Commun., Conference Record, pp. (26-11)-(26-15)
Billotet-Hoffman, C. and O. Bryngdahl (1983) "On the error diffusion technique for electronic halftoning", Proc. SID, vol. 24, pp. 253-258
Bracewell, R. N. (1978) The Fourier Transform and Its Application. New York: McGraw-Hill
Campbell, F. W., J. J. Kulikowski, J. Levinson (1966) "The effect of orientation on the visual resolution of gratings", J. Physiology London, vol. 187, pp. 427-436
Chao, Y. (1982) "An investigation into the coding of halftone pictures", M.I.T. Ph.D. Thesis
Clapper, F. R. and J. A. Yule (1953) "The effect of multiple internal reflections on the densities of half-tone prints on paper", J. Opt. Soc. of Am., vol. 43, No. 7, pp. 600-603
Cornsweet, T. N. (1970) Visual Perception, New York: Academic Press
Dippe, M. A. and E. H. Wold (1985) "Antialiasing through stochastic sampling", Computer Graphics (AMC SIGGRPAPH'85 Conf. Proc.), vol. 19, No. 3, pp. 69-78
Dudgeon, D. E. and R. M. Mersereau (1984) Multidimensional Digital Signal Processing, Englewood Cliffs, N.J.: Prentice-Hall, pp. 39-41
Engeldrum, P. G. (1985) "Computing color gamuts of ink-jet printing systems", SID Int. Sym. Digest of Tech. Papers, pp. 385-388
Floyd, R. W., and L. Steinberg (1975) "Adaptive algorithm for spatial grey scale", SID Int. Sym. Digest of Tech. Papers, pp. 36-37
Floyd, R. W., and L. Steinberg (1976) "An adaptive algorithm for spatial greyscale", Proc. SID, vol. 17/2, pp. 75-77
Freund, J. E. (1971) Mathematical Statistics. Englewood, N.J.: Prentice-Hall
Garcia, A. (1986) "Efficient rendering of synthetic images", M.I.T. Ph.D. Thesis
Gardner, M. (1978) "White and brown music, fractal curves and one-over-f fluctuations", Scientific Am., Apr., pp. 16-32
Goodall, W. M. (1951) "Television by pulse code modulation", Bell Sys. Tech. Journal, vol. 30, pp. 33-49
Graham, C. H., ed. (1965) Vision and Visual Perception, New York: John Wiley & Sons
Hamill, P. (1977) "Line printer modification for better grey level pictures", Computer Graphics and Image Proc., vol. 6, pp. 485-491
Hecht, E. and A. Zajac (1974) Optics. Reading, Mass.: Addison-Wesley, pp. 361-363
Heckbert, P. S. (1982) "Color image quantization for frame buffer display", Computer Graphics (AMC SIGGRPAPH'82 Conf. Proc.), vol. 16, No. 3, pp. 297-307
Higgins, G. C. and K. Stultz (1948) "Visual acuity as measured with various orientations of a parallel-line test object," J. Opt. Soc. Am., vol. 38, No. 9, pp. 756-758
Holladay, T. M. (1980) "An optimum algorithm for halftone generation for displays and hard copies", Proc. SID, vol. 21, No. 2, pp. 185-192
Jaeger, C. W., H. McManus, and D. Titterington (1984) "The influence of ink/media interactions on copy quality ink-jet printing" Prod. SID, vol. 25/1, pp. 65-70
Jarvis, J. F., and C. S. Roberts (1976) "A new technique for displaying continuous-tone images on a bilevel display", IEEE Tran. on Commun., vol. COM-24, pp. 891-898
Jarvis, J. F., C. N. Judice, and W. H. Ninke (1976) "A survey of techniques for the display of continuous-tone pictures on bilevel displays", Computer Graphics and Image Processing, vol. 5, pp. 13-40
Kermisch, D. and P. G. Roetling (1975) "Fourier Spectrum of halftone images", J. Opt. Soc. Am., vol. 65, pp. 716-723
Knowlton, K. and L. Harmon (1972) "Computer-produced greyscales", Computer Graphics and Image Proc., vol. 1, pp. 1-20
Kuhn, L. and R. A. Myers (1979) "Ink-jet printing", Scientific American, vol. 240, No. 4, pp. 162-178, Apr
Limb J. O. (1969) "Design of dither waveforms for quantized visual signals", Bell Sys. Tech. J., Sep., pp. 2555-2582
Lippel, B. and M. Kurland (1971) "The effect of dither on luminance quantization of pictures", IEEE Trans. Comm. vol. COM-19, No. 6, pp. 879-888
Lippel, B. (1976) "Two and three-dimensional ordered dither in bi-level picture displays", Proc. SID, vol. 17/2, pp. 115-121
Lippel, B. (1978) "Comments on `A new technique for displaying continuous-tone images on a bilevel display`", IEEE Trans. Commun., vol. COM-26, pp. 309-310
Mandelbrot, B. and R. Voss (1983) "Why is nature fractal and when should noises be scaling?", Noise in Physical Systems and 1/f Noise. New York: North Holland Physics Publishing, pp. 31-39
Marks, R. J. (1986) "Multidimensional-signal sample dependency at Nyquist densities", J. Opt. Soc. Am. A, vol. 3, No. 2, pp. 268-273
Mersereau, R. M. (1978) "Two-dimensional signal processing from hexagonal rasters", IEEE International Conf. on Acoustics, Speech, and Signal Processing, pp. 739, 742
Mesereau, R. M. (1979) "The processing of hexagonally sampled two-dimensional signals", Proc. IEEE, vol. 67, No. 6, pp. 930-949
Musha, T. (1981) "1/f fluctuations in biological systems", Proc. 3rd symposium on 1/f fluctuations, pp. 143-146
Papoulis, A. (1984) Probability, Random Variables, and Stochastic Processes, New York: McGraw-Hill, p. 178
Perry, B. and M. L. Mendelsohn (1964) "Picture generation with a standard line printer", Comm. of the ACM, vol. 7, No. 5, pp. 311-313
Petersen, D. P. and D. Middleton (1962) "Sampling and reconstruction of wave-number-limited functions in N-dimensional Euclidean spaces", Information and control, vol. 5, pp. 279-323
Ratzel, J. N. (1980) "The discrete representation of spatially continuous images", M.I.T. Ph.D. Thesis
Roberts, L. G. (1962) "Picture coding using pseudo-random noise", IRE Trans. Infor. Theory, vol. IT-8, pp. 145-154
Robinson, A. H. (1973) "Multidimensional Fourier transforms and image processing with finite scanning apertures", Applied Optics, vol. 12, No. 10, pp. 2344-2352
Roetling, P. G. (1976) "Halftone method for edge enhancement and moire suppression", J. Opt. Soc. Am., vol. 66, pp. 985-989
Roetling, P. G. (1976) "Visual performance and image coding", Proc. SID, vol. 17/2, pp. 111-114
Roetling, P. G. (1977) "Binary approximation of continuous-tone images", Photographic Science and Engineering, vol. 21, pp. 60-65
Roetling, P. G. and T. M. Holladay (1979) "Tone reproduction and screen design for pictorial electrographic printing", J. Applied Photographic Eng., vol. 5, No. 4, pp. 179-182
Schreiber, W. F. (1976) "Laser scanning for the graphic arts", Proc. SPIE, vol. 84, pp. 21-26
Schreiber, W. F. (1983) "An electronic process camera", Tech. Ass. of the Graphic Arts Proc., May
Schreiber, W. F. (1983) RLE Progress Report No. 125, MIT, p. 6
Schreiber, W. F. and D. E. Troxel (1985) "Transformation between continuous and discrete representation of images: a perceptual approach", IEEE Trans. PAMI, vol. PAMI-7, No. 2, pp. 178-186
Schreiber, W. F. (1986) Fundamentals of Electronic Imaging Systems: Some Aspects of Image Processing. New York: Springer-Verlag
Schroeder, M. R. (1969) "Images from computers", IEEE Spectrum, vol. 6, 66-78
Shaw, R., P. D. Burns and J. C. Dainty (1981) "Particulate model for halftone noise in electrophotography I. Theory, and II. Experimental verification", Proc. SPIE, vol. 310, pp. 137-150
Sonnenberg, H. (1982) "Laser-scanning parameters and latitudes in laser xerography", Applied Optics, vol. 21, pp. 1745-1751
Sonnenberg, H. (1983) "Designing Scanners for Laser Printers", Laser Applications, Apr., pp. 67-70
Stevenson, R. L. and G. R. Arce (1985) "Binary display of hexagonally sampled continuous-tone images", J. Opt. Soc. Am. Avol. 7, pp. 1009-1013
Stoffel, J. C. and J. F. Moreland (1981) "A survey of electronic techniques for pictorial reproduction", IEEE Tran. Commun., vol. 29, 1898-1925
Stoffel, J. C. (1982) Graphical and Binary Image Processing and Applications. Dedham, Mass.: Artech House
Stucki, P. (1979) "Image processing for document reproduction", in Advances in Digital Image Processing. New York: Plenum Press, pp. 177-218
Stucki, P. (1981) "MECCA-a multiple-error correcting computation algorithm for bilevel image hardcopy reproduction", Research Report RZ1060, IBM Research Laboratory, Zurich, Switzerland
Taylor, M. M. (1963) "Visual discrimination and orientation", J. Opt. Soc. Am., vol. 53, Jun., pp. 763-765
Ulichney, R. A. and D. Troxel (1982) "Scaling Binary Images with the Telescoping Template", IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. PAMI-4, pp. 331-335
Ulichney, R. A. (1985) "Generalized ordered dither", M.I.T., ATRP-T-51. also Digital Equipment Corporation, DEC-TR-412
Ulichney, R. A. (1987) Digital Halftoning, Cambridge, Mass.: M.I.T. Press
Voss, R. F. and J. Clark (1975) "`1/f noise` in music and speech", Nature, vol. 258, No. 5533, Nov. 27, pp. 317-318
Voss, R. F. and J. Clark (1978) "`1/f noise` in music: music from 1/f noise", J. Acoustic Soc. Am., vol. 63, No. 1, pp. 258-263
Voss, R. F. (1979) "1/f (flicker) noise: a brief review", Proc. of the 33rd Annual Symposium on Frequency Control, May 30-Jun. 1, 1979, pp. 40-46
White, J. M. (1980) "Recent advances in thresholding techniques for facsimile", J. Applied Photographic Eng., vol. 6, pp. 49-57
Witten, I. H. and M. Neal (1982) "Using peano curves for bilevel display of continuous-tone images", IEEE CG&A, May, pp. 47-52
Woo, B. (1984) "A survey of halftoning algorithms and investigation of the error diffusion technique", M.I.T. S.B. Thesis
Yule, J. A. C. (1967) Principles of Color Reproduction, New York: John Wiley & Sons
J. P. Allebach. "Aliasing and Quantization in the Efficient Display of Continuous Tone Imagery", Journal of the Optical Society of America, 69(6):869-877, Jun., 1979
J. P. Allebach and R. N. Stradling. "Computer-aided Design of Dither Signals for Binary Display of Images", Applied Optics, 18(15):2078-2713, Aug. 1979
C. Allen and R. A. Schindler. "Determining Image Quality from Electronic or Digital Signal Characteristics". In SPIE Advances in Image Transmission, vol. 249, pp. 179-184, 1980
D. Anastassiou and S. Kollias. "Digital Halftoning Using Neural Networks", In SPIE Visual Communications and Image Processing, vol. 1001, pp. 1062-1069, 1988
M. Broja, F. Wyrowski, and O. Bryngdahl. "Digital Halftoning by Iterative Procedure", Optics Communications, 69(3,4):205-210, Jan., 1989
O. Bryngdahl. "Halftone Images: Spatial Resolution and Tone Reproduction". Journal of Optical Society of America, 68(3):416-422, Mar. 1978
F. W. Campbell and D. G. Green. "Optical and Retinal Factors Affecting Visual Resolution". Journal of Physics, 181:576-593, 1965
P. Carnevali, L. Coletti, and S. Patarnello. "Image Processing by Simulated Annealing". IBM Journal of Research and Development, 29:569-579, Nov., 1985
R. Eschbach and R. Hauck. "A 2-D Pulse Density Modulation by Iteration for Halftoning". Optics Communications, 62(5):300-304, Jun. 1987
G. S. Fawcett and G. F. Schrack. "Halftoning Techniques Using Error Diffusion". In Proceedings of the SID, vol. 27(4), pp. 305-308, 1986
J. P. Guilford. Psychometric Methods. McGraw-Hill, 1954
T. A. Hentea and V. R. Algazi. "Perceptual Models and the Filtering of High Contrast Achromatic Images". IEEE Transactions on Systems, Man, and Cybernetics, SMC-14(2):230-246, Apr., 1984
J. O. Limb. "Distortion Criteria of the Human Viewer". IEEE Transactions on Systems, Man, and Cybernetics, SMC-9(12):778-793, Dec., 1979
J. L. Mannos and D. J. Sacrison. "The Effects of a Visual Fidelity Criterion on the Encoding of Images". IEEE Transactions on Information Theory, IT-20(4):525-535, Jul., 1974
S. Matsumoto and B. Liu. "Analytical Fidelity Measures in the Characterization of Halftone Processes". Journal of the Optical Society of America, 70(10):1248-1254, 1980
P. W. Melnychuck and R. Shaw. "Fourier Spectra of Digital Halftone Images containing Dot-position Errors". Journal of the Optical Society of America, 5(8):1328-1338, Aug. 1988
T. Mitsa and K. J. Parker. "Digital Halftoning Using a Blue Noise Mask". In SPIE Electronic Imaging Conference, vol. 1452, pp. 47-56, Feb., 1991
W. Naing, Y. Miyake, N. Abe, and S. Kubo. "Analysis of Tone Reproduction Characteristics for Inkjet Images by a Modified Yule-Nielsen Equation". Journal of Imaging Technology, 14(1):6-11, Feb., 1988
P. G. Roetling. "Visual Performance and Image Coding". In SPIE/OSA Image Processing, vol. 74, pp. 195-199, 1976
R. A. Schindler. "Physical Measures of Image Quality and their Relationship to Performance". In SPIE Advances in Display Technology, vol. 199, pp. 117-125, 1979
J. Sullivan, R. Miller, and G. Pios. "Image Halftoning Using Visual Error Diffusion". Journal of the Optical Society of America, 1990 in Press; [Published: 10(8):1714-1724, 1993]
J. Sullivan, L. Ray, and R. Miller. "Design of Minimum Visual Modulation Halftone Patterns". IEEE Transactions on Systems, Man, and Cybernetics, 21(1):33-38, Jan.-Feb., 1991
J. W. Wesner. "Screen Patterns Used in Reproduction of Continuous-tone Graphics". Applied Optics, 13(7):1703-1710, Jul., 197
November 22, 2014. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.
