Abstract

Algorithms are investigated for the printing or display of color images at near-original image quality with a minimum number of output colors. Each algorithm consists of a quantizer that is used possibly in conjunction with halftoning. We consider both image-independent and image-dependent quantizers implemented in RGB or in the uniform color space L*u*υ*. The halftoning techniques that we use are multilevel extensions of error diffusion and ordered dither. Image quality resulting from the use of these algorithms is measured by subjective evaluation.

© 1990 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. G. Wyszecki, W. S. Stiles, Color Science, 2nd ed. (Wiley, New York, 1982).
  2. R. S. Gentile, J. P. Allebach, E. Walowit, “Quantization of color images based on uniform color spaces,” J. Imag. Tech. 16, 11–21 (1990).
  3. R. Ulichney, Digital Halftoning (MIT Press, Cambridge, Mass., 1987).
  4. J. D. Stoffel, J. F. Moreland, “A survey of electronic techniques for pictorial image reproduction,” IEEE Trans. Commun. COM-29, 1898–1925 (1981).
    [CrossRef]
  5. R. W. Floyd, L. Steinberg, “An adaptive algorithm for spatial greyscale,” Proc. Soc. Inf. Disp. 17, 75–77 (1976).
  6. B. E. Bayer, “An optimum method for two-level rendition of continuous-tone pictures,” IEEE Int. Conf. Commun. Conf. Rec. 26, 11–15 (1973).
  7. A. L. Edwards, Experimental Design in Psychological Research, 4th ed. (Rinehart, New York, 1960).
  8. S. S. Stevens, “Mathematics, measurement, and psychophysics,” in Handbook of Experimental Psychology, S. S. Stevens, ed. (Wiley, New York, 1951), pp. 1–49.
  9. W. T. Hartmann, T. E. Madden, “Prediction of display colorimetry from digital video signals,” J. Imag. Tech. 13, 103–108 (1987).
  10. W. K. Pratt, Digital Image Processing (Wiley, New York, 1978).
  11. G. W. Braudaway, “A procedure for optimum choice of a small number of colors from a large color palette for color imaging,” presented at Electronic Imaging’87, San Francisco, Calif., 1987.
  12. J. C. Dalton, “Color composite error diffusion,” in SPSE—Advances in Non-Impact Printing Technologies (Society for Imaging Science and Technology, Springfield, Va., 1984).
  13. P. Heckbert, “Color image quantization for frame buffer display,” Comput. Graphics 16, 297–307 (1982).
    [CrossRef]
  14. D. E. Pearson, Transmission and Display of Pictorial Information (Wiley, New York, 1975), pp. 31–50.

1990 (1)

R. S. Gentile, J. P. Allebach, E. Walowit, “Quantization of color images based on uniform color spaces,” J. Imag. Tech. 16, 11–21 (1990).

1987 (1)

W. T. Hartmann, T. E. Madden, “Prediction of display colorimetry from digital video signals,” J. Imag. Tech. 13, 103–108 (1987).

1982 (1)

P. Heckbert, “Color image quantization for frame buffer display,” Comput. Graphics 16, 297–307 (1982).
[CrossRef]

1981 (1)

J. D. Stoffel, J. F. Moreland, “A survey of electronic techniques for pictorial image reproduction,” IEEE Trans. Commun. COM-29, 1898–1925 (1981).
[CrossRef]

1976 (1)

R. W. Floyd, L. Steinberg, “An adaptive algorithm for spatial greyscale,” Proc. Soc. Inf. Disp. 17, 75–77 (1976).

1973 (1)

B. E. Bayer, “An optimum method for two-level rendition of continuous-tone pictures,” IEEE Int. Conf. Commun. Conf. Rec. 26, 11–15 (1973).

Allebach, J. P.

R. S. Gentile, J. P. Allebach, E. Walowit, “Quantization of color images based on uniform color spaces,” J. Imag. Tech. 16, 11–21 (1990).

Bayer, B. E.

B. E. Bayer, “An optimum method for two-level rendition of continuous-tone pictures,” IEEE Int. Conf. Commun. Conf. Rec. 26, 11–15 (1973).

Braudaway, G. W.

G. W. Braudaway, “A procedure for optimum choice of a small number of colors from a large color palette for color imaging,” presented at Electronic Imaging’87, San Francisco, Calif., 1987.

Dalton, J. C.

J. C. Dalton, “Color composite error diffusion,” in SPSE—Advances in Non-Impact Printing Technologies (Society for Imaging Science and Technology, Springfield, Va., 1984).

Edwards, A. L.

A. L. Edwards, Experimental Design in Psychological Research, 4th ed. (Rinehart, New York, 1960).

Floyd, R. W.

R. W. Floyd, L. Steinberg, “An adaptive algorithm for spatial greyscale,” Proc. Soc. Inf. Disp. 17, 75–77 (1976).

Gentile, R. S.

R. S. Gentile, J. P. Allebach, E. Walowit, “Quantization of color images based on uniform color spaces,” J. Imag. Tech. 16, 11–21 (1990).

Hartmann, W. T.

W. T. Hartmann, T. E. Madden, “Prediction of display colorimetry from digital video signals,” J. Imag. Tech. 13, 103–108 (1987).

Heckbert, P.

P. Heckbert, “Color image quantization for frame buffer display,” Comput. Graphics 16, 297–307 (1982).
[CrossRef]

Madden, T. E.

W. T. Hartmann, T. E. Madden, “Prediction of display colorimetry from digital video signals,” J. Imag. Tech. 13, 103–108 (1987).

Moreland, J. F.

J. D. Stoffel, J. F. Moreland, “A survey of electronic techniques for pictorial image reproduction,” IEEE Trans. Commun. COM-29, 1898–1925 (1981).
[CrossRef]

Pearson, D. E.

D. E. Pearson, Transmission and Display of Pictorial Information (Wiley, New York, 1975), pp. 31–50.

Pratt, W. K.

W. K. Pratt, Digital Image Processing (Wiley, New York, 1978).

Steinberg, L.

R. W. Floyd, L. Steinberg, “An adaptive algorithm for spatial greyscale,” Proc. Soc. Inf. Disp. 17, 75–77 (1976).

Stevens, S. S.

S. S. Stevens, “Mathematics, measurement, and psychophysics,” in Handbook of Experimental Psychology, S. S. Stevens, ed. (Wiley, New York, 1951), pp. 1–49.

Stiles, W. S.

G. Wyszecki, W. S. Stiles, Color Science, 2nd ed. (Wiley, New York, 1982).

Stoffel, J. D.

J. D. Stoffel, J. F. Moreland, “A survey of electronic techniques for pictorial image reproduction,” IEEE Trans. Commun. COM-29, 1898–1925 (1981).
[CrossRef]

Ulichney, R.

R. Ulichney, Digital Halftoning (MIT Press, Cambridge, Mass., 1987).

Walowit, E.

R. S. Gentile, J. P. Allebach, E. Walowit, “Quantization of color images based on uniform color spaces,” J. Imag. Tech. 16, 11–21 (1990).

Wyszecki, G.

G. Wyszecki, W. S. Stiles, Color Science, 2nd ed. (Wiley, New York, 1982).

Comput. Graphics (1)

P. Heckbert, “Color image quantization for frame buffer display,” Comput. Graphics 16, 297–307 (1982).
[CrossRef]

IEEE Int. Conf. Commun. Conf. Rec. (1)

B. E. Bayer, “An optimum method for two-level rendition of continuous-tone pictures,” IEEE Int. Conf. Commun. Conf. Rec. 26, 11–15 (1973).

IEEE Trans. Commun. (1)

J. D. Stoffel, J. F. Moreland, “A survey of electronic techniques for pictorial image reproduction,” IEEE Trans. Commun. COM-29, 1898–1925 (1981).
[CrossRef]

J. Imag. Tech. (2)

R. S. Gentile, J. P. Allebach, E. Walowit, “Quantization of color images based on uniform color spaces,” J. Imag. Tech. 16, 11–21 (1990).

W. T. Hartmann, T. E. Madden, “Prediction of display colorimetry from digital video signals,” J. Imag. Tech. 13, 103–108 (1987).

Proc. Soc. Inf. Disp. (1)

R. W. Floyd, L. Steinberg, “An adaptive algorithm for spatial greyscale,” Proc. Soc. Inf. Disp. 17, 75–77 (1976).

Other (8)

R. Ulichney, Digital Halftoning (MIT Press, Cambridge, Mass., 1987).

W. K. Pratt, Digital Image Processing (Wiley, New York, 1978).

G. W. Braudaway, “A procedure for optimum choice of a small number of colors from a large color palette for color imaging,” presented at Electronic Imaging’87, San Francisco, Calif., 1987.

J. C. Dalton, “Color composite error diffusion,” in SPSE—Advances in Non-Impact Printing Technologies (Society for Imaging Science and Technology, Springfield, Va., 1984).

A. L. Edwards, Experimental Design in Psychological Research, 4th ed. (Rinehart, New York, 1960).

S. S. Stevens, “Mathematics, measurement, and psychophysics,” in Handbook of Experimental Psychology, S. S. Stevens, ed. (Wiley, New York, 1951), pp. 1–49.

D. E. Pearson, Transmission and Display of Pictorial Information (Wiley, New York, 1975), pp. 31–50.

G. Wyszecki, W. S. Stiles, Color Science, 2nd ed. (Wiley, New York, 1982).

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (4)

Fig. 1
Fig. 1

Error-distribution weights wk,l. P denotes the pixel that has just been quantized. The image is scanned from left to right and then from top to bottom.

Fig. 2
Fig. 2

Dither matrix dk,l for ordered dither.

Fig. 3
Fig. 3

Monochrome versions of the original images used for the investigation.

Fig. 4
Fig. 4

Number of bits required by the quantization and halftoning algorithms to produce near-original image quality for the color original images corresponding to Figs. 3a and 3b.

Tables (8)

Tables Icon

Table 1 Number of Colors and Bits

Tables Icon

Table 2 Summary of Quantization and Halftoning Algorithms

Tables Icon

Table 3 Differences between Mean Scores for Fig. 3a

Tables Icon

Table 4 Differences between Mean Scores for Fig. 3b

Tables Icon

Table 5 Shortest Significant Ranges for Fig. 3a

Tables Icon

Table 6 Shortest Significant Ranges for Fig. 3b

Tables Icon

Table 7 Significance Ranges for Fig. 3a

Tables Icon

Table 8 Significance Ranges for Fig. 3b

Equations (15)

Equations on this page are rendered with MathJax. Learn more.

C 0 = Q ( C i ) ,
c j o = q ( c j i ) j = R , G , B ,
C o = T o { Q [ T i ( C i ) ] } ,
C i ( m , n ) = C i ( m , n ) for all ( m , n ) .
C o ( m , n ) = Q [ C i ( m , n ) ] ,
E ( m , n ) = C o ( m , n ) C i ( m , n ) ,
C i ( m + k , n + l ) = C i ( m + k , n + l ) w k , l E ( m , n )
c o ( m , n ) = q [ c i ( m , n ) + d ( m , n ) ] ,
d ( m , n ) = ( 2 δ m mod D 1 , n mod D 2 D 1 D 2 + 1 2 D 1 D 2 ) Δ .
F S F α ; ( s 1 ) , ( n 1 ) ( s 1 ) ,
F C F α ; ( c 1 ) , ( n 1 ) ( c 1 ) ,
F S x C F α ; ( s 1 ) ( c 1 ) , ( n 1 ) ( s 1 ) ( c 1 ) ,
C x ¯ = ( O x C * n s ) 1 / 2 ,
R i = SSR i × C x ¯ ,
N o 1 / 3

Metrics