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

Full Article  |  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.


Figures (17)

Fig. 1
Fig. 1

(a) Image data corrupted by (b) 1D or (c) 2D ISI.

Fig. 2
Fig. 2

Image-formation model.

Fig. 3
Fig. 3

VA estimation of a binary sequence corrupted by 1×3 ISI and AWGN.

Fig. 4
Fig. 4

Estimation of a binary object corrupted by 3×3 ISI: (a) row-by-row VA, (b) RCVA (row-by-row VA with decision feedback). Solid rectangles enclose the pixels of a source state. Dashed rectangles enclose the pixels of a destination state. The state transition influences the values of three signal pixels whose locations in the image are indicated by shaded circles.

Fig. 5
Fig. 5

RCVA trellis for estimation of a binary object corrupted by 3×3 ISI and noise.

Fig. 6
Fig. 6

Iterative RCVA for binary object estimation.

Fig. 7
Fig. 7

The RCVA outperforms the WF in the restoration of text: (a) 64×64 binary object consisting of 0- (white) and 1- (black) valued pixels, (b) 3×3 ISI and noise corrupted (σn2=1.2×10-3) image, (c) RCVA object estimate (four iterations; BER, 2×10-2), (d) WF object estimate (BER, 5×10-2).

Fig. 8
Fig. 8

BER performance for estimates of a random binary object corrupted by minimum-distance 3×3 ISI and AWGN.

Fig. 9
Fig. 9

BER performance for estimation of a random binary object corrupted by minimum-distance 3×3 ISI and Poisson noise.

Fig. 10
Fig. 10

The RCVA restores spatial frequency contact where the WF cannot.

Fig. 11
Fig. 11

Using a training object, the LBG algorithm, and VQ to reduce RCVA complexity for gray-scale object estimation.

Fig. 12
Fig. 12

(a) A 3×2 source state and (b) a 3×2 destination state specify pixel values in (c) a 3×3 region by averaging pixels in overlapped columns.

Fig. 13
Fig. 13

MER performance for estimation of a gray-scale object corrupted by minimum-distance ISI and AWGN: (a) 3×3 ISI, (b) 5×5 ISI.

Fig. 14
Fig. 14

Estimation of a gray-scale object corrupted by minimum-distance ISI and AWGN: (a) 128×128 object, (b) 256×384 training object, (c) 3×3 ISI and AWGN (σn2=7) corrupted image, (d) WF object estimate (3×3 ISI; MER, 12), (e) RCVA object estimate (3×3 ISI; 256 states; MER, 9), (f) 5×5 ISI and AWGN (σn2=7) corrupted image, (g) WF object estimate (5×5 ISI; MER, 14), (h) RCVA object estimate (5×5 ISI; 256 states; MER, 10).

Fig. 15
Fig. 15

Estimation of Fig. 14(a) given Fig. 14(c) and a mismatched training object: (a) the mismatched training object, (b) RCVA object estimate (256 states; training object transitions; MER, 13), (c) RCVA object estimate (256 states; all transitions; MER, 13).

Fig. 16
Fig. 16

The optical imaging system: SLF, spatial light filter.

Fig. 17
Fig. 17

Estimates of experimental optical data: (a) object, (b) image (BER, 1.6×10-1), (c) WF errors (BER, 7×10-2), (d) RCVA errors (BER, 2×10-2).

Tables (1)

Tables Icon

Table 1 CCD Specifications

Equations (22)

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

p(g|fˆ)=i,j p[g(i, j)|fˆ].
p(g|fˆ)=i, j12πσn2exp-[sˆ(i, j)-g(i, j)]22σn2,
sˆ(i, j)=k,l fˆ(i-k, j-l)h(k, l).
-ln p(g|fˆ)=i, j-ln12πσn2+[sˆ(i, j)-g(i, j)]22σn2.
λ=i,j[sˆ(i, j)-g(i, j)]2
λ(i, j)=[sˆ(i, j)-g(i, j)]2.
g=f * h+n=(1 0 1) * (0.5 0.3 0.2)+(0.1-0.1 0-0.1-0.1)
=(0.6 0.2 0.7 0.2 0.1),
k=i-1i+1 λ(k, j).
hmd=arg minh minf1,f2f1(f1 * h)-(f2 * h),
hmd=0.0860.1210.0860.1210.1720.1210.0860.1210.086.
SNR=10 log10(σs2/σn2),
Pr{g(i, j)|fˆ}=sˆ(i, j)g(i, j) exp[-sˆ(i, j)]/g(i, j)!forg(i, j)=0, 1, 2,0otherwise.
-ln Pr{g|fˆ}=i, j-g(i, j)ln sˆ(i, j)+sˆ(i, j)+ln g(i, j)!.
λ=i,j sˆ(i, j)-g(i, j)ln sˆ(i, j).
FˆWF(u, v)=G(u, v)H*(u, v)|H(u, v)|2+E[|N(u, v)|2]/E[|F(u, v)|2],
AFSM(u, v)=1100i=1100|Fˆi(u, v)|2.
dˆi=ck,k=argminjdi-cj.
MER=1Ni, j|f(i, j)-fˆ(i, j)|
g(i, j)=19(216-1)k=02l=02g(3i+k, 3j+l).
hˆ=0.0280.0900.0270.0930.2510.0910.0280.0950.0281.
11282i, j[g(i, j)-(f * hˆ)i, j]2=3.1×10-3.

Metrics