Abstract

A multiple convolution (e.g., an image formed by convolving several individual components) is automatically deconvolvable, provided that its dimension (i.e., the number of variables of which it is a function) is greater than unity. This follows because the Fourier transform of a K-dimensional function (having compact support) is zero on continuous surfaces (here called zero sheets) of dimension (2K − 2) in a space that effectively has 2K dimensions. A number of important practical applications are transfigured by the concept of the zero sheet. Image restoration can be effected without prior knowledge of the point-spread function, i.e., blind deconvolution is possible even when only a single blurred image is given. It is in principle possible to remove some of the additive noise when the form of the point-spread function is known. Fourier phase can be retrieved directly, and, unlike for readily implementable iterative techniques, complex images can be handled as straightforwardly as real images.

© 1987 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. A. Rosenfeld, A. C. Kak, Digital Picture Processing, 2nd ed. (Academic, New York, 1982), Chap. 7.
  2. D. Izraelevitz, J. S. Lim, “A new algorithm for closed form image reconstruction from Fourier transform magnitude,” in Digest of Topical Meeting on Signal Recovery and Synthesis II (Optical Society of America, Washington, D.C., 1986); I. S. Stefanescu, “On the phase retrieval problem in two dimensions,” J. Math. Phys. 26, 2141–2160 (1985); M. S. Scivier, M. A. Fiddy, “Phase ambiguities and the zeros of multidimensional band-limited functions,” J. Opt. Soc. Am. A 2, 693–697 (1985).
    [CrossRef]
  3. R. G. Lane, W. R. Fright, R. H. T. Bates, “Direct phase retrieval,” IEEE Trans. Acoust. Speech Signal Process. (to be published).
  4. A. V. Oppenheim, R. W. Schafer, T. G. Stockham, “Nonlinear filtering of multiplied and convolved signals,” Proc. IEEE 56, 1264–1291 (1968).
    [CrossRef]
  5. T. G. Stockham, T. M. Cannon, R. B. Ingebretson, “Blind deconvolution through digital signal processing,” Proc. IEEE 63, 678–692 (1975).
    [CrossRef]
  6. R. H. T. Bates, M. J. McDonnell, Image Restoration and Reconstruction (Clarendon, Oxford, 1986).
  7. R. H. T. Bates, P. J. Napier, A. E. McKinnon, M. J. McDonnell, “Self-consistent deconvolution. I. Theory; II. Applications,” Optik 44, 183–201, 253–272 (1976).
  8. M. C. Won, D. Mnyama, R. H. T. Bates, “Improving initial phase estimates for phase retrieval algorithms,” Opt. Acta, 32, 377–396 (1985).
    [CrossRef]
  9. L. S. Taylor, “The phase retrieval problem,”IEEE Trans. Antennas Propag. AP-29, 386–391 (1981).
    [CrossRef]
  10. R. H. T. Bates, “On phase problems. II,” Optik 51, 223–234 (1978).
  11. R. H. T. Bates, A. M. Sinton, R. A. Minard, “Generalization of shift-and-add imaging,” in International Conference on Speckle, H. Arsenault, ed., Proc. Soc. Photo-Opt. Instrum. Eng.556, 263–269 (1985).
    [CrossRef]
  12. E. C. Titchmarsh, The Theory of Functions (Clarendon, Oxford, 1986).
  13. M. A. Jenkins, J. F. Traub, “Algorithm 419: zeros of a complex polnomial [C2],” Commun. ACM 15, 97–99 (1972).
    [CrossRef]
  14. J. W. Wood, T. J. Hall, M. A. Fiddy, “A comparison study of some computational methods for locating the zeros of entire functions,” Opt. Acta 30, 511–527 (1983).
    [CrossRef]
  15. S. R. Curtis, A. V. Oppenheim, J. S. Lim, “Signal reconstruction. from Fourier transform signal information,”IEEE Trans. Acoust. Speech and Signal Process. ASSP-33, 643–657 (1985).
    [CrossRef]
  16. J. L. C. Sanz, “Mathematical considerations for the problem of Fourier transform phase retrieval from magnitude,” SIAM J. Appl. Math. 45, 651–664 (1985).
    [CrossRef]
  17. J. L. C. Sanz, T. S. Huang, “Polynomial system of equations and its applications to the study of the effect of noise on multidimensional Fourier transform phase retrieval,”IEEE Trans. Acoust. Speech Signal Process. ASSP-33, 997–1004 (1985).
    [CrossRef]
  18. J. R. Fienup, “Reconstruction of a complex-valued object from the modulus of its Fourier transform using a support constraint,” J. Opt. Soc. Am. A 4, 118–123 (1987).
    [CrossRef]

1987 (1)

1985 (4)

S. R. Curtis, A. V. Oppenheim, J. S. Lim, “Signal reconstruction. from Fourier transform signal information,”IEEE Trans. Acoust. Speech and Signal Process. ASSP-33, 643–657 (1985).
[CrossRef]

J. L. C. Sanz, “Mathematical considerations for the problem of Fourier transform phase retrieval from magnitude,” SIAM J. Appl. Math. 45, 651–664 (1985).
[CrossRef]

J. L. C. Sanz, T. S. Huang, “Polynomial system of equations and its applications to the study of the effect of noise on multidimensional Fourier transform phase retrieval,”IEEE Trans. Acoust. Speech Signal Process. ASSP-33, 997–1004 (1985).
[CrossRef]

M. C. Won, D. Mnyama, R. H. T. Bates, “Improving initial phase estimates for phase retrieval algorithms,” Opt. Acta, 32, 377–396 (1985).
[CrossRef]

1983 (1)

J. W. Wood, T. J. Hall, M. A. Fiddy, “A comparison study of some computational methods for locating the zeros of entire functions,” Opt. Acta 30, 511–527 (1983).
[CrossRef]

1981 (1)

L. S. Taylor, “The phase retrieval problem,”IEEE Trans. Antennas Propag. AP-29, 386–391 (1981).
[CrossRef]

1978 (1)

R. H. T. Bates, “On phase problems. II,” Optik 51, 223–234 (1978).

1976 (1)

R. H. T. Bates, P. J. Napier, A. E. McKinnon, M. J. McDonnell, “Self-consistent deconvolution. I. Theory; II. Applications,” Optik 44, 183–201, 253–272 (1976).

1975 (1)

T. G. Stockham, T. M. Cannon, R. B. Ingebretson, “Blind deconvolution through digital signal processing,” Proc. IEEE 63, 678–692 (1975).
[CrossRef]

1972 (1)

M. A. Jenkins, J. F. Traub, “Algorithm 419: zeros of a complex polnomial [C2],” Commun. ACM 15, 97–99 (1972).
[CrossRef]

1968 (1)

A. V. Oppenheim, R. W. Schafer, T. G. Stockham, “Nonlinear filtering of multiplied and convolved signals,” Proc. IEEE 56, 1264–1291 (1968).
[CrossRef]

Bates, R. H. T.

M. C. Won, D. Mnyama, R. H. T. Bates, “Improving initial phase estimates for phase retrieval algorithms,” Opt. Acta, 32, 377–396 (1985).
[CrossRef]

R. H. T. Bates, “On phase problems. II,” Optik 51, 223–234 (1978).

R. H. T. Bates, P. J. Napier, A. E. McKinnon, M. J. McDonnell, “Self-consistent deconvolution. I. Theory; II. Applications,” Optik 44, 183–201, 253–272 (1976).

R. G. Lane, W. R. Fright, R. H. T. Bates, “Direct phase retrieval,” IEEE Trans. Acoust. Speech Signal Process. (to be published).

R. H. T. Bates, M. J. McDonnell, Image Restoration and Reconstruction (Clarendon, Oxford, 1986).

R. H. T. Bates, A. M. Sinton, R. A. Minard, “Generalization of shift-and-add imaging,” in International Conference on Speckle, H. Arsenault, ed., Proc. Soc. Photo-Opt. Instrum. Eng.556, 263–269 (1985).
[CrossRef]

Cannon, T. M.

T. G. Stockham, T. M. Cannon, R. B. Ingebretson, “Blind deconvolution through digital signal processing,” Proc. IEEE 63, 678–692 (1975).
[CrossRef]

Curtis, S. R.

S. R. Curtis, A. V. Oppenheim, J. S. Lim, “Signal reconstruction. from Fourier transform signal information,”IEEE Trans. Acoust. Speech and Signal Process. ASSP-33, 643–657 (1985).
[CrossRef]

Fiddy, M. A.

J. W. Wood, T. J. Hall, M. A. Fiddy, “A comparison study of some computational methods for locating the zeros of entire functions,” Opt. Acta 30, 511–527 (1983).
[CrossRef]

Fienup, J. R.

Fright, W. R.

R. G. Lane, W. R. Fright, R. H. T. Bates, “Direct phase retrieval,” IEEE Trans. Acoust. Speech Signal Process. (to be published).

Hall, T. J.

J. W. Wood, T. J. Hall, M. A. Fiddy, “A comparison study of some computational methods for locating the zeros of entire functions,” Opt. Acta 30, 511–527 (1983).
[CrossRef]

Huang, T. S.

J. L. C. Sanz, T. S. Huang, “Polynomial system of equations and its applications to the study of the effect of noise on multidimensional Fourier transform phase retrieval,”IEEE Trans. Acoust. Speech Signal Process. ASSP-33, 997–1004 (1985).
[CrossRef]

Ingebretson, R. B.

T. G. Stockham, T. M. Cannon, R. B. Ingebretson, “Blind deconvolution through digital signal processing,” Proc. IEEE 63, 678–692 (1975).
[CrossRef]

Izraelevitz, D.

D. Izraelevitz, J. S. Lim, “A new algorithm for closed form image reconstruction from Fourier transform magnitude,” in Digest of Topical Meeting on Signal Recovery and Synthesis II (Optical Society of America, Washington, D.C., 1986); I. S. Stefanescu, “On the phase retrieval problem in two dimensions,” J. Math. Phys. 26, 2141–2160 (1985); M. S. Scivier, M. A. Fiddy, “Phase ambiguities and the zeros of multidimensional band-limited functions,” J. Opt. Soc. Am. A 2, 693–697 (1985).
[CrossRef]

Jenkins, M. A.

M. A. Jenkins, J. F. Traub, “Algorithm 419: zeros of a complex polnomial [C2],” Commun. ACM 15, 97–99 (1972).
[CrossRef]

Kak, A. C.

A. Rosenfeld, A. C. Kak, Digital Picture Processing, 2nd ed. (Academic, New York, 1982), Chap. 7.

Lane, R. G.

R. G. Lane, W. R. Fright, R. H. T. Bates, “Direct phase retrieval,” IEEE Trans. Acoust. Speech Signal Process. (to be published).

Lim, J. S.

S. R. Curtis, A. V. Oppenheim, J. S. Lim, “Signal reconstruction. from Fourier transform signal information,”IEEE Trans. Acoust. Speech and Signal Process. ASSP-33, 643–657 (1985).
[CrossRef]

D. Izraelevitz, J. S. Lim, “A new algorithm for closed form image reconstruction from Fourier transform magnitude,” in Digest of Topical Meeting on Signal Recovery and Synthesis II (Optical Society of America, Washington, D.C., 1986); I. S. Stefanescu, “On the phase retrieval problem in two dimensions,” J. Math. Phys. 26, 2141–2160 (1985); M. S. Scivier, M. A. Fiddy, “Phase ambiguities and the zeros of multidimensional band-limited functions,” J. Opt. Soc. Am. A 2, 693–697 (1985).
[CrossRef]

McDonnell, M. J.

R. H. T. Bates, P. J. Napier, A. E. McKinnon, M. J. McDonnell, “Self-consistent deconvolution. I. Theory; II. Applications,” Optik 44, 183–201, 253–272 (1976).

R. H. T. Bates, M. J. McDonnell, Image Restoration and Reconstruction (Clarendon, Oxford, 1986).

McKinnon, A. E.

R. H. T. Bates, P. J. Napier, A. E. McKinnon, M. J. McDonnell, “Self-consistent deconvolution. I. Theory; II. Applications,” Optik 44, 183–201, 253–272 (1976).

Minard, R. A.

R. H. T. Bates, A. M. Sinton, R. A. Minard, “Generalization of shift-and-add imaging,” in International Conference on Speckle, H. Arsenault, ed., Proc. Soc. Photo-Opt. Instrum. Eng.556, 263–269 (1985).
[CrossRef]

Mnyama, D.

M. C. Won, D. Mnyama, R. H. T. Bates, “Improving initial phase estimates for phase retrieval algorithms,” Opt. Acta, 32, 377–396 (1985).
[CrossRef]

Napier, P. J.

R. H. T. Bates, P. J. Napier, A. E. McKinnon, M. J. McDonnell, “Self-consistent deconvolution. I. Theory; II. Applications,” Optik 44, 183–201, 253–272 (1976).

Oppenheim, A. V.

S. R. Curtis, A. V. Oppenheim, J. S. Lim, “Signal reconstruction. from Fourier transform signal information,”IEEE Trans. Acoust. Speech and Signal Process. ASSP-33, 643–657 (1985).
[CrossRef]

A. V. Oppenheim, R. W. Schafer, T. G. Stockham, “Nonlinear filtering of multiplied and convolved signals,” Proc. IEEE 56, 1264–1291 (1968).
[CrossRef]

Rosenfeld, A.

A. Rosenfeld, A. C. Kak, Digital Picture Processing, 2nd ed. (Academic, New York, 1982), Chap. 7.

Sanz, J. L. C.

J. L. C. Sanz, T. S. Huang, “Polynomial system of equations and its applications to the study of the effect of noise on multidimensional Fourier transform phase retrieval,”IEEE Trans. Acoust. Speech Signal Process. ASSP-33, 997–1004 (1985).
[CrossRef]

J. L. C. Sanz, “Mathematical considerations for the problem of Fourier transform phase retrieval from magnitude,” SIAM J. Appl. Math. 45, 651–664 (1985).
[CrossRef]

Schafer, R. W.

A. V. Oppenheim, R. W. Schafer, T. G. Stockham, “Nonlinear filtering of multiplied and convolved signals,” Proc. IEEE 56, 1264–1291 (1968).
[CrossRef]

Sinton, A. M.

R. H. T. Bates, A. M. Sinton, R. A. Minard, “Generalization of shift-and-add imaging,” in International Conference on Speckle, H. Arsenault, ed., Proc. Soc. Photo-Opt. Instrum. Eng.556, 263–269 (1985).
[CrossRef]

Stockham, T. G.

T. G. Stockham, T. M. Cannon, R. B. Ingebretson, “Blind deconvolution through digital signal processing,” Proc. IEEE 63, 678–692 (1975).
[CrossRef]

A. V. Oppenheim, R. W. Schafer, T. G. Stockham, “Nonlinear filtering of multiplied and convolved signals,” Proc. IEEE 56, 1264–1291 (1968).
[CrossRef]

Taylor, L. S.

L. S. Taylor, “The phase retrieval problem,”IEEE Trans. Antennas Propag. AP-29, 386–391 (1981).
[CrossRef]

Titchmarsh, E. C.

E. C. Titchmarsh, The Theory of Functions (Clarendon, Oxford, 1986).

Traub, J. F.

M. A. Jenkins, J. F. Traub, “Algorithm 419: zeros of a complex polnomial [C2],” Commun. ACM 15, 97–99 (1972).
[CrossRef]

Won, M. C.

M. C. Won, D. Mnyama, R. H. T. Bates, “Improving initial phase estimates for phase retrieval algorithms,” Opt. Acta, 32, 377–396 (1985).
[CrossRef]

Wood, J. W.

J. W. Wood, T. J. Hall, M. A. Fiddy, “A comparison study of some computational methods for locating the zeros of entire functions,” Opt. Acta 30, 511–527 (1983).
[CrossRef]

Commun. ACM (1)

M. A. Jenkins, J. F. Traub, “Algorithm 419: zeros of a complex polnomial [C2],” Commun. ACM 15, 97–99 (1972).
[CrossRef]

IEEE Trans. Acoust. Speech and Signal Process. (1)

S. R. Curtis, A. V. Oppenheim, J. S. Lim, “Signal reconstruction. from Fourier transform signal information,”IEEE Trans. Acoust. Speech and Signal Process. ASSP-33, 643–657 (1985).
[CrossRef]

IEEE Trans. Acoust. Speech Signal Process. (1)

J. L. C. Sanz, T. S. Huang, “Polynomial system of equations and its applications to the study of the effect of noise on multidimensional Fourier transform phase retrieval,”IEEE Trans. Acoust. Speech Signal Process. ASSP-33, 997–1004 (1985).
[CrossRef]

IEEE Trans. Antennas Propag. (1)

L. S. Taylor, “The phase retrieval problem,”IEEE Trans. Antennas Propag. AP-29, 386–391 (1981).
[CrossRef]

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

Opt. Acta (2)

J. W. Wood, T. J. Hall, M. A. Fiddy, “A comparison study of some computational methods for locating the zeros of entire functions,” Opt. Acta 30, 511–527 (1983).
[CrossRef]

M. C. Won, D. Mnyama, R. H. T. Bates, “Improving initial phase estimates for phase retrieval algorithms,” Opt. Acta, 32, 377–396 (1985).
[CrossRef]

Optik (2)

R. H. T. Bates, P. J. Napier, A. E. McKinnon, M. J. McDonnell, “Self-consistent deconvolution. I. Theory; II. Applications,” Optik 44, 183–201, 253–272 (1976).

R. H. T. Bates, “On phase problems. II,” Optik 51, 223–234 (1978).

Proc. IEEE (2)

A. V. Oppenheim, R. W. Schafer, T. G. Stockham, “Nonlinear filtering of multiplied and convolved signals,” Proc. IEEE 56, 1264–1291 (1968).
[CrossRef]

T. G. Stockham, T. M. Cannon, R. B. Ingebretson, “Blind deconvolution through digital signal processing,” Proc. IEEE 63, 678–692 (1975).
[CrossRef]

SIAM J. Appl. Math. (1)

J. L. C. Sanz, “Mathematical considerations for the problem of Fourier transform phase retrieval from magnitude,” SIAM J. Appl. Math. 45, 651–664 (1985).
[CrossRef]

Other (6)

R. H. T. Bates, M. J. McDonnell, Image Restoration and Reconstruction (Clarendon, Oxford, 1986).

A. Rosenfeld, A. C. Kak, Digital Picture Processing, 2nd ed. (Academic, New York, 1982), Chap. 7.

D. Izraelevitz, J. S. Lim, “A new algorithm for closed form image reconstruction from Fourier transform magnitude,” in Digest of Topical Meeting on Signal Recovery and Synthesis II (Optical Society of America, Washington, D.C., 1986); I. S. Stefanescu, “On the phase retrieval problem in two dimensions,” J. Math. Phys. 26, 2141–2160 (1985); M. S. Scivier, M. A. Fiddy, “Phase ambiguities and the zeros of multidimensional band-limited functions,” J. Opt. Soc. Am. A 2, 693–697 (1985).
[CrossRef]

R. G. Lane, W. R. Fright, R. H. T. Bates, “Direct phase retrieval,” IEEE Trans. Acoust. Speech Signal Process. (to be published).

R. H. T. Bates, A. M. Sinton, R. A. Minard, “Generalization of shift-and-add imaging,” in International Conference on Speckle, H. Arsenault, ed., Proc. Soc. Photo-Opt. Instrum. Eng.556, 263–269 (1985).
[CrossRef]

E. C. Titchmarsh, The Theory of Functions (Clarendon, Oxford, 1986).

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 (9)

Fig. 1
Fig. 1

One-dimensional complex image, normalized to unit maximum magnitude and having the following values for 0 ≤ x ≤ 1. (a) f(x): solid lines, |f(x)| dashed lines, phase {f(x)}. (b) Point zeros of F(u), each identified by *. (c) Point zeros of (ζ), each identified by ⊕; closed dashed curve is the unit circle in the complex ζ plane.

Fig. 2
Fig. 2

One of the closed curves (superimposed upon α, β, ρ space) composing a pseudoperspective display of a zero sheet (of the Z transform of a particular 16 × 16 pixel complex image). Note that Figs. 5 and 9 are to the same scale as this figure.

Fig. 3
Fig. 3

The convolution of two one-dimensional complex images shown in Figs. 1(a) and 4(a). (a) f(x): solid lines, |f(x)|; dashed lines, phase {f(x)}. (b) Point zeros of (ζ) each identified by ⊕; closed dashed curve is the unit circle in the complex ζ plane.

Fig. 4
Fig. 4

One-dimensional complex image, normalized to unit maximum magnitude and having value for 0 ≤ x ≤ 1. (a) f(x), solid lines, |f(x)|; dashed lines, phase {f(x)}. (b) Point zeros of (ζ), each identified by ⊕; closed dashed curve is the unit circle in the complex ζ plane.

Fig. 5
Fig. 5

Zero sheets computed from the pixel data listed in Tables 1 and 2. Axes (α, β, and ρ) are not shown (unlike in Fig. 2) to avoid cluttering the display. (a) Zero sheet computed from the image defined in Table 1. (b) Zero sheet computed from the image defined in Table 2. (c) Zero sheet computed from the convolution of the above two images.

Fig. 6
Fig. 6

Magnitude, quantized to 256 equispaced levels from black to white of 63 × 63 pixel complex convolution of images shown in Figs. 7 and 8.

Fig. 7
Fig. 7

First 32 × 32 pixel complex image. (a) Magnitude, quantized as for Fig. 6. (b) Phase, quantized to 256 equispaced levels from −π (black) to π (white).

Fig. 8
Fig. 8

Second 32 × 32 pixel complex image. (a) Magnitude, quantized as for Figs. 6 and 7. (b) Phase, quantized as for Fig. 7.

Fig. 9
Fig. 9

The effects of noise on the zero sheet corresponding to the convolution of the pair of complex images defined in Tables 1 and 2. (a) = 10−4, (b) = 10−3, (C) = 10−2, (d) = 10−1.

Tables (2)

Tables Icon

Table 1 Complex Amplitudes and x, y Coordinates of Pixels Defining a Particular 2 × 2 Pixel Complex Image

Tables Icon

Table 2 Complex Amplitudes and x, y Coordinates of Pixels Defining Another 2 × 2 Pixel Complex Image

Equations (18)

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

f ( x ) = 0             for x S f ( x ) B f ( x ) .
f ( x ) K F ( u ) = - ( K ) f ( x ) exp ( i 2 u · x ) d σ ( x ) ,
u · x = k = 1 K u k x k .
f ( 1 ) ( x ) f ( 2 ) ( x ) f ( M ) ( x ) K m = 1 M F ( m ) ( u ) ,
f f ( x ) = f * ( - x ) f ( x ) ,
f f ( x ) K F ( u ) 2 .
f p ( x ) = k = 1 K l ( k ) = L k 1 L k 2 f l ( 1 ) , , l ( k ) j = 1 K δ [ x j - l ( j ) a j ] ,
f l ( 1 ) , , l ( k ) = f [ l ( 1 ) a 1 , , l ( k ) a k ] ,
f p ( x ) K F ( ζ ) = k = 1 K l ( k ) = L k 1 L k 2 f l ( 1 ) , , l ( k ) j = 1 K ζ j l ( j ) ,
ζ k = exp ( i 2 π a k u k ) ,
ζ k = α k + i β k ,
K = 1 :             x 1 = x ,             u 1 = u ,             ζ 1 = ζ = ξ + i η ,             F ( ζ ) = F ( ζ ) , K = 2 :             x 1 = x ,             x 2 = y ,             u 1 = u ,             u 2 = v ,
ζ 1 = ζ = ρ exp ( i ϕ ) ,             ζ 2 = γ = α + i β ,             F ( ζ ) = F ( ζ , γ ) .
f ( x ) = f ( 1 ) ( x ) f ( 2 ) ( x ) f ( M ) ( x ) .
f ( x ) K k = 1 M F ( m ) ( u ) ,
f ( x ) K F ( ζ ) = m = 1 M F ( m ) ( ζ ) ,
f ( x ) = c ( x ) + f ( 1 ) ( x ) f ( 2 ) ( x ) f ( M ) ( x ) ,
= S c ( x ) ( K ) c ( x ) 2 d σ ( x ) / S f ( x ) ( K ) f ( x ) 2 d σ ( x ) .

Metrics