Abstract

The Viterbi algorithm (VA) is known to given an optimal solution to the problem of estimating one-dimensional sequences of discrete-valued pixels corrupted by finite-support blur and memoryless noise. A row-by-row estimation along with decision feedback and vector quantization is used to reduce the computational complexity of the VA and allow the estimation of two-dimensional images. This reduced-complexity VA (RCVA) is shown to produce near-optimal estimation of random binary images. In addition, simulated restorations of gray-scale images show the RCVA estimates to be an improvement over the estimates obtained by the conventional Wiener filter (WF). Unlike the WF, the RCVA is capable of superresolution and is adaptable for use in restoring data from signal-dependent Poisson noise corruption. Experimental restorations of random binary data gathered from an optical imaging system support the simulations and show that the RCVA estimate has fewer than one third of the errors of the WF estimate.

© 2000 Optical Society of America

PDF Article

References

  • View by:
  • |
  • |
  • |

  1. H. C. Andrews, B. R. Hunt, Digital Image Restoration (Prentice-Hall, Englewood Cliffs, N.J., 1977).
  2. A. K. Jain, Fundamentals of Digital Image Processing (Prentice-Hall, Englewood Cliffs, N.J., 1989).
  3. T. J. Holmes, “Maximum likelihood image restoration adapted for noncoherent optical imaging,” J. Opt. Soc. Am. A 5, 666–673 (1988).
    [CrossRef]
  4. G. Forney, “The Viterbi algorithm,” Proc. IEEE 61, 268–278 (1973).
    [CrossRef]
  5. G. Forney, “Maximum likelihood sequence estimation of digital sequences in the presence of intersymbol interference,” IEEE Trans. Inf. Theory IT-18, 363–378 (1972).
    [CrossRef]
  6. J. Heanue, K. Gürkan, L. Hesselink, “Signal detection for page-access optical memories with inter-symbol interference,” Appl. Opt. 35, 2431–2438 (1996).
    [CrossRef] [PubMed]
  7. K. M. Chugg, “Performance of optimal digital page detection in a two-dimensional ISI/AWGN channel,” presented at the Asilomar Conference on Signals, Systems and Computers, November 5, 1996, Pacific Grove, Calif.
  8. C. Miller, B. R. Hunt, M. A. Neifeld, M. W. Marcellin, “Binary image reconstruction via 2-D Viterbi search,” in Proceedings of the IEEE International Conference on Image Processing (Institute of Electrical and Electronics Engineers, New York, N.Y., 1997), pp. 181–184.
  9. J. G. Proakis, Digital Communications, 3rd ed. (McGraw Hill, New York, 1995).
  10. K. M. Chugg, X. P. Chen, M. A. Neifeld, “Two-dimensional equalization in coherent and incoherent page-oriented optical memory,” J. Opt. Soc. Am. A 16, 549–562 (1999).
    [CrossRef]
  11. H. Press, S. Teukolsky, W. Vetterling, B. Flannery, Numerical Recipes in C (Cambridge U. Press, New York, 1992).
  12. R. W. Gerchberg, “Super-resolution through error energy reduction,” Opt. Acta 21, 709–720 (1974).
    [CrossRef]
  13. A. Gersho, R. M. Gray, Vector Quantization and Signal Compression (Kluwer Academic, Boston, Mass., 1992).
  14. Y. Linde, A. Buzo, R. M. Gray, “An algorithm for vector quantization design,” IEEE Trans. Commun. COM-28, 84–95 (1980).
    [CrossRef]
  15. D. G. Sheppard, A. Bilgin, M. S. Nadar, B. R. Hunt, M. W. Marcellin, “A vector quantizer for image restoration,” IEEE Trans. Image Process. 7, 119–124 (1998).
    [CrossRef]
  16. L. R. Bahl, J. Cocke, F. Jelinek, J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate,” IEEE Trans. Inf. Theory IT-20, 284–287 (1974).
    [CrossRef]
  17. X. P. Chen, K. M. Chugg, “Near-optimal data detection for two-dimensional ISI/AWGN channels using concatenated modeling and iterative algorithms,” presented at the International Conference on Communications, June 7–11, Atlanta, Georgia.

1999 (1)

1998 (1)

D. G. Sheppard, A. Bilgin, M. S. Nadar, B. R. Hunt, M. W. Marcellin, “A vector quantizer for image restoration,” IEEE Trans. Image Process. 7, 119–124 (1998).
[CrossRef]

1996 (1)

1988 (1)

1980 (1)

Y. Linde, A. Buzo, R. M. Gray, “An algorithm for vector quantization design,” IEEE Trans. Commun. COM-28, 84–95 (1980).
[CrossRef]

1974 (2)

R. W. Gerchberg, “Super-resolution through error energy reduction,” Opt. Acta 21, 709–720 (1974).
[CrossRef]

L. R. Bahl, J. Cocke, F. Jelinek, J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate,” IEEE Trans. Inf. Theory IT-20, 284–287 (1974).
[CrossRef]

1973 (1)

G. Forney, “The Viterbi algorithm,” Proc. IEEE 61, 268–278 (1973).
[CrossRef]

1972 (1)

G. Forney, “Maximum likelihood sequence estimation of digital sequences in the presence of intersymbol interference,” IEEE Trans. Inf. Theory IT-18, 363–378 (1972).
[CrossRef]

Andrews, H. C.

H. C. Andrews, B. R. Hunt, Digital Image Restoration (Prentice-Hall, Englewood Cliffs, N.J., 1977).

Bahl, L. R.

L. R. Bahl, J. Cocke, F. Jelinek, J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate,” IEEE Trans. Inf. Theory IT-20, 284–287 (1974).
[CrossRef]

Bilgin, A.

D. G. Sheppard, A. Bilgin, M. S. Nadar, B. R. Hunt, M. W. Marcellin, “A vector quantizer for image restoration,” IEEE Trans. Image Process. 7, 119–124 (1998).
[CrossRef]

Buzo, A.

Y. Linde, A. Buzo, R. M. Gray, “An algorithm for vector quantization design,” IEEE Trans. Commun. COM-28, 84–95 (1980).
[CrossRef]

Chen, X. P.

K. M. Chugg, X. P. Chen, M. A. Neifeld, “Two-dimensional equalization in coherent and incoherent page-oriented optical memory,” J. Opt. Soc. Am. A 16, 549–562 (1999).
[CrossRef]

X. P. Chen, K. M. Chugg, “Near-optimal data detection for two-dimensional ISI/AWGN channels using concatenated modeling and iterative algorithms,” presented at the International Conference on Communications, June 7–11, Atlanta, Georgia.

Chugg, K. M.

K. M. Chugg, X. P. Chen, M. A. Neifeld, “Two-dimensional equalization in coherent and incoherent page-oriented optical memory,” J. Opt. Soc. Am. A 16, 549–562 (1999).
[CrossRef]

K. M. Chugg, “Performance of optimal digital page detection in a two-dimensional ISI/AWGN channel,” presented at the Asilomar Conference on Signals, Systems and Computers, November 5, 1996, Pacific Grove, Calif.

X. P. Chen, K. M. Chugg, “Near-optimal data detection for two-dimensional ISI/AWGN channels using concatenated modeling and iterative algorithms,” presented at the International Conference on Communications, June 7–11, Atlanta, Georgia.

Cocke, J.

L. R. Bahl, J. Cocke, F. Jelinek, J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate,” IEEE Trans. Inf. Theory IT-20, 284–287 (1974).
[CrossRef]

Flannery, B.

H. Press, S. Teukolsky, W. Vetterling, B. Flannery, Numerical Recipes in C (Cambridge U. Press, New York, 1992).

Forney, G.

G. Forney, “The Viterbi algorithm,” Proc. IEEE 61, 268–278 (1973).
[CrossRef]

G. Forney, “Maximum likelihood sequence estimation of digital sequences in the presence of intersymbol interference,” IEEE Trans. Inf. Theory IT-18, 363–378 (1972).
[CrossRef]

Gerchberg, R. W.

R. W. Gerchberg, “Super-resolution through error energy reduction,” Opt. Acta 21, 709–720 (1974).
[CrossRef]

Gersho, A.

A. Gersho, R. M. Gray, Vector Quantization and Signal Compression (Kluwer Academic, Boston, Mass., 1992).

Gray, R. M.

Y. Linde, A. Buzo, R. M. Gray, “An algorithm for vector quantization design,” IEEE Trans. Commun. COM-28, 84–95 (1980).
[CrossRef]

A. Gersho, R. M. Gray, Vector Quantization and Signal Compression (Kluwer Academic, Boston, Mass., 1992).

Gürkan, K.

Heanue, J.

Hesselink, L.

Holmes, T. J.

Hunt, B. R.

D. G. Sheppard, A. Bilgin, M. S. Nadar, B. R. Hunt, M. W. Marcellin, “A vector quantizer for image restoration,” IEEE Trans. Image Process. 7, 119–124 (1998).
[CrossRef]

C. Miller, B. R. Hunt, M. A. Neifeld, M. W. Marcellin, “Binary image reconstruction via 2-D Viterbi search,” in Proceedings of the IEEE International Conference on Image Processing (Institute of Electrical and Electronics Engineers, New York, N.Y., 1997), pp. 181–184.

H. C. Andrews, B. R. Hunt, Digital Image Restoration (Prentice-Hall, Englewood Cliffs, N.J., 1977).

Jain, A. K.

A. K. Jain, Fundamentals of Digital Image Processing (Prentice-Hall, Englewood Cliffs, N.J., 1989).

Jelinek, F.

L. R. Bahl, J. Cocke, F. Jelinek, J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate,” IEEE Trans. Inf. Theory IT-20, 284–287 (1974).
[CrossRef]

Linde, Y.

Y. Linde, A. Buzo, R. M. Gray, “An algorithm for vector quantization design,” IEEE Trans. Commun. COM-28, 84–95 (1980).
[CrossRef]

Marcellin, M. W.

D. G. Sheppard, A. Bilgin, M. S. Nadar, B. R. Hunt, M. W. Marcellin, “A vector quantizer for image restoration,” IEEE Trans. Image Process. 7, 119–124 (1998).
[CrossRef]

C. Miller, B. R. Hunt, M. A. Neifeld, M. W. Marcellin, “Binary image reconstruction via 2-D Viterbi search,” in Proceedings of the IEEE International Conference on Image Processing (Institute of Electrical and Electronics Engineers, New York, N.Y., 1997), pp. 181–184.

Miller, C.

C. Miller, B. R. Hunt, M. A. Neifeld, M. W. Marcellin, “Binary image reconstruction via 2-D Viterbi search,” in Proceedings of the IEEE International Conference on Image Processing (Institute of Electrical and Electronics Engineers, New York, N.Y., 1997), pp. 181–184.

Nadar, M. S.

D. G. Sheppard, A. Bilgin, M. S. Nadar, B. R. Hunt, M. W. Marcellin, “A vector quantizer for image restoration,” IEEE Trans. Image Process. 7, 119–124 (1998).
[CrossRef]

Neifeld, M. A.

K. M. Chugg, X. P. Chen, M. A. Neifeld, “Two-dimensional equalization in coherent and incoherent page-oriented optical memory,” J. Opt. Soc. Am. A 16, 549–562 (1999).
[CrossRef]

C. Miller, B. R. Hunt, M. A. Neifeld, M. W. Marcellin, “Binary image reconstruction via 2-D Viterbi search,” in Proceedings of the IEEE International Conference on Image Processing (Institute of Electrical and Electronics Engineers, New York, N.Y., 1997), pp. 181–184.

Press, H.

H. Press, S. Teukolsky, W. Vetterling, B. Flannery, Numerical Recipes in C (Cambridge U. Press, New York, 1992).

Proakis, J. G.

J. G. Proakis, Digital Communications, 3rd ed. (McGraw Hill, New York, 1995).

Raviv, J.

L. R. Bahl, J. Cocke, F. Jelinek, J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate,” IEEE Trans. Inf. Theory IT-20, 284–287 (1974).
[CrossRef]

Sheppard, D. G.

D. G. Sheppard, A. Bilgin, M. S. Nadar, B. R. Hunt, M. W. Marcellin, “A vector quantizer for image restoration,” IEEE Trans. Image Process. 7, 119–124 (1998).
[CrossRef]

Teukolsky, S.

H. Press, S. Teukolsky, W. Vetterling, B. Flannery, Numerical Recipes in C (Cambridge U. Press, New York, 1992).

Vetterling, W.

H. Press, S. Teukolsky, W. Vetterling, B. Flannery, Numerical Recipes in C (Cambridge U. Press, New York, 1992).

Appl. Opt. (1)

IEEE Trans. Commun. (1)

Y. Linde, A. Buzo, R. M. Gray, “An algorithm for vector quantization design,” IEEE Trans. Commun. COM-28, 84–95 (1980).
[CrossRef]

IEEE Trans. Image Process. (1)

D. G. Sheppard, A. Bilgin, M. S. Nadar, B. R. Hunt, M. W. Marcellin, “A vector quantizer for image restoration,” IEEE Trans. Image Process. 7, 119–124 (1998).
[CrossRef]

IEEE Trans. Inf. Theory (2)

L. R. Bahl, J. Cocke, F. Jelinek, J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate,” IEEE Trans. Inf. Theory IT-20, 284–287 (1974).
[CrossRef]

G. Forney, “Maximum likelihood sequence estimation of digital sequences in the presence of intersymbol interference,” IEEE Trans. Inf. Theory IT-18, 363–378 (1972).
[CrossRef]

J. Opt. Soc. Am. A (2)

Opt. Acta (1)

R. W. Gerchberg, “Super-resolution through error energy reduction,” Opt. Acta 21, 709–720 (1974).
[CrossRef]

Proc. IEEE (1)

G. Forney, “The Viterbi algorithm,” Proc. IEEE 61, 268–278 (1973).
[CrossRef]

Other (8)

X. P. Chen, K. M. Chugg, “Near-optimal data detection for two-dimensional ISI/AWGN channels using concatenated modeling and iterative algorithms,” presented at the International Conference on Communications, June 7–11, Atlanta, Georgia.

A. Gersho, R. M. Gray, Vector Quantization and Signal Compression (Kluwer Academic, Boston, Mass., 1992).

H. C. Andrews, B. R. Hunt, Digital Image Restoration (Prentice-Hall, Englewood Cliffs, N.J., 1977).

A. K. Jain, Fundamentals of Digital Image Processing (Prentice-Hall, Englewood Cliffs, N.J., 1989).

K. M. Chugg, “Performance of optimal digital page detection in a two-dimensional ISI/AWGN channel,” presented at the Asilomar Conference on Signals, Systems and Computers, November 5, 1996, Pacific Grove, Calif.

C. Miller, B. R. Hunt, M. A. Neifeld, M. W. Marcellin, “Binary image reconstruction via 2-D Viterbi search,” in Proceedings of the IEEE International Conference on Image Processing (Institute of Electrical and Electronics Engineers, New York, N.Y., 1997), pp. 181–184.

J. G. Proakis, Digital Communications, 3rd ed. (McGraw Hill, New York, 1995).

H. Press, S. Teukolsky, W. Vetterling, B. Flannery, Numerical Recipes in C (Cambridge U. Press, New York, 1992).

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.


Metrics