Abstract

The development of a new error-free digital image compression algorithm is discussed. Without the help of any statistics information of the images being processed, this algorithm achieves average bits-per-word ratios near the entropy of the neighboring pixel differences. Because this algorithm does not involve statistical modeling, generation of a code book, or long integer–floating point arithmetics, it is simpler and, therefore, faster than the studied statistics codes, such as the Huffman code or the arithmetic code.

© 1992 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. W. K. Pratt, Digital Image Processing (Wiley, New York, 1978), Part 6.
  2. R. C. Gonzalez, P. Wintz, Digital Image Processing (Addison-Wesley, London, 1977), Chap. 6.
  3. J. A. Stoser, J. H. Reif, ed., presented at the Data Compression Conference, Snowbird, Utah, 8–11 April 1991.
  4. W. M. Goodall, “Television transmission by pulse code modulation,” Bell Syst. Tech. J. 30, 33–49 (1951).
  5. F. Kretz, “Subjectively optimal quantization of pictures,” IEEE Trans. Commun. COM-23, 1288–1292 (1975).
    [CrossRef]
  6. H. R. Schindler, “Delta modulation,” IEEE Spectrum 7, 69–78 (1970).
    [CrossRef]
  7. J. F. O’Neal, “Predictive quantizing systems (differential pulse code modulation) for the transmission of television signals,” Bell Syst. Tech. J. 45, 689–721 (1966).
  8. H. H. Bauch, H. Häberle, H. G. Musmann, H. Ohnsonge, G. A. Wengenroth, H. J. Woite, “Picture coding,” IEEE Trans. Commun. COM-22, 1158–1167 (1974).
    [CrossRef]
  9. R. J. Clarke, Transform Coding of Images (Academic, London, 1985).
  10. A. E. Laemmel, “Coding processes for bandwidth reduction in picture transmission,” Rep. R (Microwave Research Institute, Polytechnic Institute of Brooklyn, Brooklyn, N.Y., 1951), pp. 246–251.
  11. D. A. Huffman, “A method for the construction of minimum redundancy codes,” Proc. IRE 40, 1098–1101 (1952).
    [CrossRef]
  12. J. Ziv, A. Lempel, “A universal algorithm for sequential data compression,” IEEE Trans. Inf. Theory IT-23, 337–343 (1977).
    [CrossRef]
  13. T. A. Welch, “A technique for high-performance data compression,” Computer 17, 8–9 (1984).
    [CrossRef]
  14. J. Rissanen, “Arithmetic coding as number representations,” Acta Polytech. Scand. Math. Comput. Math. Ser. 31, 44–51 (1979).
  15. I. W. Witten, R. M. Neal, J. G. Cleary, “Arithmetic coding for data compression,” Commun. ACM, 30, 520–540 (1987).
    [CrossRef]
  16. D. He, “An error-free image compression algorithm using classifying-sequencing techniques,” Ph.D. dissertation (University of Arizona, Tucson, Arizona, 1991).

1987 (1)

I. W. Witten, R. M. Neal, J. G. Cleary, “Arithmetic coding for data compression,” Commun. ACM, 30, 520–540 (1987).
[CrossRef]

1984 (1)

T. A. Welch, “A technique for high-performance data compression,” Computer 17, 8–9 (1984).
[CrossRef]

1979 (1)

J. Rissanen, “Arithmetic coding as number representations,” Acta Polytech. Scand. Math. Comput. Math. Ser. 31, 44–51 (1979).

1977 (1)

J. Ziv, A. Lempel, “A universal algorithm for sequential data compression,” IEEE Trans. Inf. Theory IT-23, 337–343 (1977).
[CrossRef]

1975 (1)

F. Kretz, “Subjectively optimal quantization of pictures,” IEEE Trans. Commun. COM-23, 1288–1292 (1975).
[CrossRef]

1974 (1)

H. H. Bauch, H. Häberle, H. G. Musmann, H. Ohnsonge, G. A. Wengenroth, H. J. Woite, “Picture coding,” IEEE Trans. Commun. COM-22, 1158–1167 (1974).
[CrossRef]

1970 (1)

H. R. Schindler, “Delta modulation,” IEEE Spectrum 7, 69–78 (1970).
[CrossRef]

1966 (1)

J. F. O’Neal, “Predictive quantizing systems (differential pulse code modulation) for the transmission of television signals,” Bell Syst. Tech. J. 45, 689–721 (1966).

1952 (1)

D. A. Huffman, “A method for the construction of minimum redundancy codes,” Proc. IRE 40, 1098–1101 (1952).
[CrossRef]

1951 (1)

W. M. Goodall, “Television transmission by pulse code modulation,” Bell Syst. Tech. J. 30, 33–49 (1951).

Bauch, H. H.

H. H. Bauch, H. Häberle, H. G. Musmann, H. Ohnsonge, G. A. Wengenroth, H. J. Woite, “Picture coding,” IEEE Trans. Commun. COM-22, 1158–1167 (1974).
[CrossRef]

Clarke, R. J.

R. J. Clarke, Transform Coding of Images (Academic, London, 1985).

Cleary, J. G.

I. W. Witten, R. M. Neal, J. G. Cleary, “Arithmetic coding for data compression,” Commun. ACM, 30, 520–540 (1987).
[CrossRef]

Gonzalez, R. C.

R. C. Gonzalez, P. Wintz, Digital Image Processing (Addison-Wesley, London, 1977), Chap. 6.

Goodall, W. M.

W. M. Goodall, “Television transmission by pulse code modulation,” Bell Syst. Tech. J. 30, 33–49 (1951).

Häberle, H.

H. H. Bauch, H. Häberle, H. G. Musmann, H. Ohnsonge, G. A. Wengenroth, H. J. Woite, “Picture coding,” IEEE Trans. Commun. COM-22, 1158–1167 (1974).
[CrossRef]

He, D.

D. He, “An error-free image compression algorithm using classifying-sequencing techniques,” Ph.D. dissertation (University of Arizona, Tucson, Arizona, 1991).

Huffman, D. A.

D. A. Huffman, “A method for the construction of minimum redundancy codes,” Proc. IRE 40, 1098–1101 (1952).
[CrossRef]

Kretz, F.

F. Kretz, “Subjectively optimal quantization of pictures,” IEEE Trans. Commun. COM-23, 1288–1292 (1975).
[CrossRef]

Laemmel, A. E.

A. E. Laemmel, “Coding processes for bandwidth reduction in picture transmission,” Rep. R (Microwave Research Institute, Polytechnic Institute of Brooklyn, Brooklyn, N.Y., 1951), pp. 246–251.

Lempel, A.

J. Ziv, A. Lempel, “A universal algorithm for sequential data compression,” IEEE Trans. Inf. Theory IT-23, 337–343 (1977).
[CrossRef]

Musmann, H. G.

H. H. Bauch, H. Häberle, H. G. Musmann, H. Ohnsonge, G. A. Wengenroth, H. J. Woite, “Picture coding,” IEEE Trans. Commun. COM-22, 1158–1167 (1974).
[CrossRef]

Neal, R. M.

I. W. Witten, R. M. Neal, J. G. Cleary, “Arithmetic coding for data compression,” Commun. ACM, 30, 520–540 (1987).
[CrossRef]

O’Neal, J. F.

J. F. O’Neal, “Predictive quantizing systems (differential pulse code modulation) for the transmission of television signals,” Bell Syst. Tech. J. 45, 689–721 (1966).

Ohnsonge, H.

H. H. Bauch, H. Häberle, H. G. Musmann, H. Ohnsonge, G. A. Wengenroth, H. J. Woite, “Picture coding,” IEEE Trans. Commun. COM-22, 1158–1167 (1974).
[CrossRef]

Pratt, W. K.

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

Rissanen, J.

J. Rissanen, “Arithmetic coding as number representations,” Acta Polytech. Scand. Math. Comput. Math. Ser. 31, 44–51 (1979).

Schindler, H. R.

H. R. Schindler, “Delta modulation,” IEEE Spectrum 7, 69–78 (1970).
[CrossRef]

Welch, T. A.

T. A. Welch, “A technique for high-performance data compression,” Computer 17, 8–9 (1984).
[CrossRef]

Wengenroth, G. A.

H. H. Bauch, H. Häberle, H. G. Musmann, H. Ohnsonge, G. A. Wengenroth, H. J. Woite, “Picture coding,” IEEE Trans. Commun. COM-22, 1158–1167 (1974).
[CrossRef]

Wintz, P.

R. C. Gonzalez, P. Wintz, Digital Image Processing (Addison-Wesley, London, 1977), Chap. 6.

Witten, I. W.

I. W. Witten, R. M. Neal, J. G. Cleary, “Arithmetic coding for data compression,” Commun. ACM, 30, 520–540 (1987).
[CrossRef]

Woite, H. J.

H. H. Bauch, H. Häberle, H. G. Musmann, H. Ohnsonge, G. A. Wengenroth, H. J. Woite, “Picture coding,” IEEE Trans. Commun. COM-22, 1158–1167 (1974).
[CrossRef]

Ziv, J.

J. Ziv, A. Lempel, “A universal algorithm for sequential data compression,” IEEE Trans. Inf. Theory IT-23, 337–343 (1977).
[CrossRef]

Acta Polytech. Scand. Math. Comput. Math. Ser. (1)

J. Rissanen, “Arithmetic coding as number representations,” Acta Polytech. Scand. Math. Comput. Math. Ser. 31, 44–51 (1979).

Bell Syst. Tech. J. (2)

W. M. Goodall, “Television transmission by pulse code modulation,” Bell Syst. Tech. J. 30, 33–49 (1951).

J. F. O’Neal, “Predictive quantizing systems (differential pulse code modulation) for the transmission of television signals,” Bell Syst. Tech. J. 45, 689–721 (1966).

Commun. ACM (1)

I. W. Witten, R. M. Neal, J. G. Cleary, “Arithmetic coding for data compression,” Commun. ACM, 30, 520–540 (1987).
[CrossRef]

Computer (1)

T. A. Welch, “A technique for high-performance data compression,” Computer 17, 8–9 (1984).
[CrossRef]

IEEE Spectrum (1)

H. R. Schindler, “Delta modulation,” IEEE Spectrum 7, 69–78 (1970).
[CrossRef]

IEEE Trans. Commun. (2)

H. H. Bauch, H. Häberle, H. G. Musmann, H. Ohnsonge, G. A. Wengenroth, H. J. Woite, “Picture coding,” IEEE Trans. Commun. COM-22, 1158–1167 (1974).
[CrossRef]

F. Kretz, “Subjectively optimal quantization of pictures,” IEEE Trans. Commun. COM-23, 1288–1292 (1975).
[CrossRef]

IEEE Trans. Inf. Theory (1)

J. Ziv, A. Lempel, “A universal algorithm for sequential data compression,” IEEE Trans. Inf. Theory IT-23, 337–343 (1977).
[CrossRef]

Proc. IRE (1)

D. A. Huffman, “A method for the construction of minimum redundancy codes,” Proc. IRE 40, 1098–1101 (1952).
[CrossRef]

Other (6)

D. He, “An error-free image compression algorithm using classifying-sequencing techniques,” Ph.D. dissertation (University of Arizona, Tucson, Arizona, 1991).

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

R. C. Gonzalez, P. Wintz, Digital Image Processing (Addison-Wesley, London, 1977), Chap. 6.

J. A. Stoser, J. H. Reif, ed., presented at the Data Compression Conference, Snowbird, Utah, 8–11 April 1991.

R. J. Clarke, Transform Coding of Images (Academic, London, 1985).

A. E. Laemmel, “Coding processes for bandwidth reduction in picture transmission,” Rep. R (Microwave Research Institute, Polytechnic Institute of Brooklyn, Brooklyn, N.Y., 1951), pp. 246–251.

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.


Tables (3)

Tables Icon

Table I Classes of 8-Bit Images

Tables Icon

TABLE II Examples of Mergers of Two Sequences

Tables Icon

TABLE III Results of 8-Bit Image Coding–Intraframe Mode

Equations (16)

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

δ < 2 c - 1 ,
L = { 3 + c · ( S + 1 ) c 0 11 , c = 0 ,
c = max ( c 1 , c 2 ) ,
S = S 1 + S 2 ,
Δ L = L 1 + L 2 - L .
Δ L = { c j + 3 - Δ c · S j , c j 0 11 - Δ c · S j , c j = 0
Δ L 0.
L = ( 3 + 8 ) · [ trunc ( S / 256 ) + 1 ] .
H Δ 1 Δ 2 Δ 3 Δ s E ,
Δ i = δ i + 2 c - 1 ,
L = 3 + c · ( S + 1 ) .
H S d 1 d 2 d s ,
L = ( 3 + 8 ) · [ trunc ( S / 256 ) + 1 ] + 8 S .
H d = - p i · log p i ,
H δ = - p j · log p j ,
H δ δ = - p k · log p k ,

Metrics