Abstract

We apply the method of alternating projections onto convex sets to the problem of restoring a signal from the phase of its Fourier transform. A method of improving convergence by adaptively varying a set of relaxation parameters in the restoration algorithm is described. The advantages of using the method of convex projections over other iterative restoration algorithms are discussed and illustrated.

© 1983 Optical Society of America

PDF Article

References

  • View by:
  • |
  • |
  • |

  1. An image is regarded here as a signal in two variables.
  2. H. A. Ferwerda, "The phase reconstruction problem for wave amplitudes and coherence functions," in Inverse Source Problems in Optics, H. P. Bates, ed. (Springer-Verlag, Berlin, 1978), Chap. 2.
  3. R. W. Gerchberg and W. O. Saxton, "A practical algorithm for the determination of phase from image and diffraction plane pictures," Optik 35, 237–246 (1972).
  4. M. H. Hayes, J. S. Lim, and A. V. Oppenheim, "Signal reconstruction from phase or magnitude," IEEE Trans. Acoust. Speech Signal Process. ASSP-28, 672–680 (1980).
  5. M. H. Hayes, "The reconstruction of a multidimensional sequence from the phase or magnitude of its Fourier transform," IEEE Trans. Acoust. Speech Signal Process. ASSP-30,140–154 (1982).
  6. W. A. Pearlman and R. M. Gray, "Source coding of the discrete Fourier transform," IEEE Trans. Inf. Theory IT-24, 683–692 (1978).
  7. A. V. Oppenheim, "The importance of phase in signals," Proc. IEEE 69, 529–541 (1981).
  8. A Fourier transform pair is denoted by f(x) ↔ F(ω), and the Fourier transform is often abbreviated as FT. The FT operator is denoted by the operation ℱ.
  9. L. G. Gubin, B. T. Polyak, and E. V. Raik, "The method of projections for finding the common point of convex sets," USSR Comput. Math. Math. Phys. 7,1–24 (1967).
  10. D. C. Youla, "Generalized image restoration by the method of alternating orthogonal projections," IEEE Trans. Circuits Syst. CAS-25, 894–702 (1978).
  11. D. C. Youla and H. Webb, "Image restoration by the method of projections onto convex sets—Part I," IEEE Trans. Med. Imaging TMI-1, 81–94 (1982).
  12. A. Lent and H. Tuy, "An iterative method for the extrapolation of bandlimited functions," J Math. Anal. Appl. 83, 554–565 (1981).
  13. M. I. Sezan and H. Stark, "Image restoration by the method of projections onto convex sets—Part II," IEEE Trans. Med. Imaging TMI-1, 95–101 (1982).
  14. A subset ɞ of ℋ is called convex of ƒ ε ɞ, g ε ɞ implies that αƒ + (1 - α)g ε ɞ for all α in the range 0 ≤ α ≤ 1.
  15. Here is a demonstration of this: let ɞ denote the set and assume that ƒ ε ɞ. Then-ƒ ε ɞ, and if ɞ is convex so is (1/2)ƒ + 1/2(-ƒ). But the latter is the zero signal, which is not in ɞ. Hence ɞ is not convex.
  16. Weak or inner-product convergence to ƒ implies that (ƒk, g) → (ƒ, g) for any g ℋ ℋ A more-familiar notion is strong convergence, which in a normed space is ‖ƒ-ƒk‖ → 0. In some cases ƒn, in Eq. (3) converges strongly to ƒ. This point is discussed in greater detail by Youla.11
  17. To a scale factor.
  18. The error defined in Eq. (26) is consistent with that given by Youla,10 Hayes,5 and Hayes et al.4 Some authors, e.g., Fienup,19 in order to avoid using a definition involving an unknown ƒ, use other definitions.
  19. J. R. Fienup, "Phase retrieval algorithms: a comparison," Appl. Opt. 21, 2758–2769 (1982).
  20. Tisnonexpansiveiffor every x,y εℋ, ‖Ty - Tx‖ ≤ ‖x - y‖. A proof that T1 or, more generally, T as given in Eq. (4) is nonexpansive is furnished by Youla.11
  21. Re[ƒ] denotes the real part of ƒ.
  22. T. Quatieri, "Phase estimation with application to speech analysis," Sc.D. Dissertation (Massachusetts Institute of Technology, Cambridge, Mass., 1979).
  23. R. H. T. Bates, "Fourier phase problems are uniquely solvable in more than one dimension, Part I," Optik 61, 247–262 (1982).
  24. K. L. Garden and R. H. T. Bates, "Fourier phase problems are uniquely solvable in more than one dimension, Part II," Optik 62, 131–142 (1982).
  25. W. R. Fright and R. H. T. Bates, "Fourier phase problems are uniquely solvable in more than one dimension, Part III," Optik 62, 219–230 (1982).
  26. Corollary 1 of Ref. 11: Let ɞ be a closed convex subset of ℋThen, for any x εℋ, y ε ɞ, Re[(x - Pɞx,y - Pɞx)] ≤ 0.

1982 (7)

M. H. Hayes, "The reconstruction of a multidimensional sequence from the phase or magnitude of its Fourier transform," IEEE Trans. Acoust. Speech Signal Process. ASSP-30,140–154 (1982).

M. I. Sezan and H. Stark, "Image restoration by the method of projections onto convex sets—Part II," IEEE Trans. Med. Imaging TMI-1, 95–101 (1982).

J. R. Fienup, "Phase retrieval algorithms: a comparison," Appl. Opt. 21, 2758–2769 (1982).

R. H. T. Bates, "Fourier phase problems are uniquely solvable in more than one dimension, Part I," Optik 61, 247–262 (1982).

K. L. Garden and R. H. T. Bates, "Fourier phase problems are uniquely solvable in more than one dimension, Part II," Optik 62, 131–142 (1982).

W. R. Fright and R. H. T. Bates, "Fourier phase problems are uniquely solvable in more than one dimension, Part III," Optik 62, 219–230 (1982).

D. C. Youla and H. Webb, "Image restoration by the method of projections onto convex sets—Part I," IEEE Trans. Med. Imaging TMI-1, 81–94 (1982).

1981 (1)

A. Lent and H. Tuy, "An iterative method for the extrapolation of bandlimited functions," J Math. Anal. Appl. 83, 554–565 (1981).

1980 (1)

M. H. Hayes, J. S. Lim, and A. V. Oppenheim, "Signal reconstruction from phase or magnitude," IEEE Trans. Acoust. Speech Signal Process. ASSP-28, 672–680 (1980).

1978 (2)

W. A. Pearlman and R. M. Gray, "Source coding of the discrete Fourier transform," IEEE Trans. Inf. Theory IT-24, 683–692 (1978).

D. C. Youla, "Generalized image restoration by the method of alternating orthogonal projections," IEEE Trans. Circuits Syst. CAS-25, 894–702 (1978).

1972 (1)

R. W. Gerchberg and W. O. Saxton, "A practical algorithm for the determination of phase from image and diffraction plane pictures," Optik 35, 237–246 (1972).

1967 (1)

L. G. Gubin, B. T. Polyak, and E. V. Raik, "The method of projections for finding the common point of convex sets," USSR Comput. Math. Math. Phys. 7,1–24 (1967).

Bates, R. H. T.

R. H. T. Bates, "Fourier phase problems are uniquely solvable in more than one dimension, Part I," Optik 61, 247–262 (1982).

K. L. Garden and R. H. T. Bates, "Fourier phase problems are uniquely solvable in more than one dimension, Part II," Optik 62, 131–142 (1982).

W. R. Fright and R. H. T. Bates, "Fourier phase problems are uniquely solvable in more than one dimension, Part III," Optik 62, 219–230 (1982).

Ferwerda, H. A.

H. A. Ferwerda, "The phase reconstruction problem for wave amplitudes and coherence functions," in Inverse Source Problems in Optics, H. P. Bates, ed. (Springer-Verlag, Berlin, 1978), Chap. 2.

Fienup, J. R.

Fright, W. R.

W. R. Fright and R. H. T. Bates, "Fourier phase problems are uniquely solvable in more than one dimension, Part III," Optik 62, 219–230 (1982).

Garden, K. L.

K. L. Garden and R. H. T. Bates, "Fourier phase problems are uniquely solvable in more than one dimension, Part II," Optik 62, 131–142 (1982).

Gerchberg, R. W.

R. W. Gerchberg and W. O. Saxton, "A practical algorithm for the determination of phase from image and diffraction plane pictures," Optik 35, 237–246 (1972).

Gray, R. M.

W. A. Pearlman and R. M. Gray, "Source coding of the discrete Fourier transform," IEEE Trans. Inf. Theory IT-24, 683–692 (1978).

Gubin, L. G.

L. G. Gubin, B. T. Polyak, and E. V. Raik, "The method of projections for finding the common point of convex sets," USSR Comput. Math. Math. Phys. 7,1–24 (1967).

Hayes, M. H.

M. H. Hayes, "The reconstruction of a multidimensional sequence from the phase or magnitude of its Fourier transform," IEEE Trans. Acoust. Speech Signal Process. ASSP-30,140–154 (1982).

M. H. Hayes, J. S. Lim, and A. V. Oppenheim, "Signal reconstruction from phase or magnitude," IEEE Trans. Acoust. Speech Signal Process. ASSP-28, 672–680 (1980).

Lent, A.

A. Lent and H. Tuy, "An iterative method for the extrapolation of bandlimited functions," J Math. Anal. Appl. 83, 554–565 (1981).

Lim, J. S.

M. H. Hayes, J. S. Lim, and A. V. Oppenheim, "Signal reconstruction from phase or magnitude," IEEE Trans. Acoust. Speech Signal Process. ASSP-28, 672–680 (1980).

Oppenheim, A. V.

M. H. Hayes, J. S. Lim, and A. V. Oppenheim, "Signal reconstruction from phase or magnitude," IEEE Trans. Acoust. Speech Signal Process. ASSP-28, 672–680 (1980).

A. V. Oppenheim, "The importance of phase in signals," Proc. IEEE 69, 529–541 (1981).

Pearlman, W. A.

W. A. Pearlman and R. M. Gray, "Source coding of the discrete Fourier transform," IEEE Trans. Inf. Theory IT-24, 683–692 (1978).

Polyak, B. T.

L. G. Gubin, B. T. Polyak, and E. V. Raik, "The method of projections for finding the common point of convex sets," USSR Comput. Math. Math. Phys. 7,1–24 (1967).

Quatieri, T.

T. Quatieri, "Phase estimation with application to speech analysis," Sc.D. Dissertation (Massachusetts Institute of Technology, Cambridge, Mass., 1979).

Raik, E. V.

L. G. Gubin, B. T. Polyak, and E. V. Raik, "The method of projections for finding the common point of convex sets," USSR Comput. Math. Math. Phys. 7,1–24 (1967).

Saxton, W. O.

R. W. Gerchberg and W. O. Saxton, "A practical algorithm for the determination of phase from image and diffraction plane pictures," Optik 35, 237–246 (1972).

Sezan, M. I.

M. I. Sezan and H. Stark, "Image restoration by the method of projections onto convex sets—Part II," IEEE Trans. Med. Imaging TMI-1, 95–101 (1982).

Stark, H.

M. I. Sezan and H. Stark, "Image restoration by the method of projections onto convex sets—Part II," IEEE Trans. Med. Imaging TMI-1, 95–101 (1982).

Tuy, H.

A. Lent and H. Tuy, "An iterative method for the extrapolation of bandlimited functions," J Math. Anal. Appl. 83, 554–565 (1981).

Webb, H.

D. C. Youla and H. Webb, "Image restoration by the method of projections onto convex sets—Part I," IEEE Trans. Med. Imaging TMI-1, 81–94 (1982).

Youla, D. C.

D. C. Youla and H. Webb, "Image restoration by the method of projections onto convex sets—Part I," IEEE Trans. Med. Imaging TMI-1, 81–94 (1982).

D. C. Youla, "Generalized image restoration by the method of alternating orthogonal projections," IEEE Trans. Circuits Syst. CAS-25, 894–702 (1978).

Appl. Opt. (1)

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

M. H. Hayes, J. S. Lim, and A. V. Oppenheim, "Signal reconstruction from phase or magnitude," IEEE Trans. Acoust. Speech Signal Process. ASSP-28, 672–680 (1980).

M. H. Hayes, "The reconstruction of a multidimensional sequence from the phase or magnitude of its Fourier transform," IEEE Trans. Acoust. Speech Signal Process. ASSP-30,140–154 (1982).

IEEE Trans. Circuits Syst. (1)

D. C. Youla, "Generalized image restoration by the method of alternating orthogonal projections," IEEE Trans. Circuits Syst. CAS-25, 894–702 (1978).

IEEE Trans. Inf. Theory (1)

W. A. Pearlman and R. M. Gray, "Source coding of the discrete Fourier transform," IEEE Trans. Inf. Theory IT-24, 683–692 (1978).

IEEE Trans. Med. Imaging (2)

M. I. Sezan and H. Stark, "Image restoration by the method of projections onto convex sets—Part II," IEEE Trans. Med. Imaging TMI-1, 95–101 (1982).

D. C. Youla and H. Webb, "Image restoration by the method of projections onto convex sets—Part I," IEEE Trans. Med. Imaging TMI-1, 81–94 (1982).

J Math. Anal. Appl. (1)

A. Lent and H. Tuy, "An iterative method for the extrapolation of bandlimited functions," J Math. Anal. Appl. 83, 554–565 (1981).

Optik (4)

R. H. T. Bates, "Fourier phase problems are uniquely solvable in more than one dimension, Part I," Optik 61, 247–262 (1982).

K. L. Garden and R. H. T. Bates, "Fourier phase problems are uniquely solvable in more than one dimension, Part II," Optik 62, 131–142 (1982).

W. R. Fright and R. H. T. Bates, "Fourier phase problems are uniquely solvable in more than one dimension, Part III," Optik 62, 219–230 (1982).

R. W. Gerchberg and W. O. Saxton, "A practical algorithm for the determination of phase from image and diffraction plane pictures," Optik 35, 237–246 (1972).

USSR Comput. Math. Math. Phys. (1)

L. G. Gubin, B. T. Polyak, and E. V. Raik, "The method of projections for finding the common point of convex sets," USSR Comput. Math. Math. Phys. 7,1–24 (1967).

Other (13)

An image is regarded here as a signal in two variables.

H. A. Ferwerda, "The phase reconstruction problem for wave amplitudes and coherence functions," in Inverse Source Problems in Optics, H. P. Bates, ed. (Springer-Verlag, Berlin, 1978), Chap. 2.

A. V. Oppenheim, "The importance of phase in signals," Proc. IEEE 69, 529–541 (1981).

A Fourier transform pair is denoted by f(x) ↔ F(ω), and the Fourier transform is often abbreviated as FT. The FT operator is denoted by the operation ℱ.

A subset ɞ of ℋ is called convex of ƒ ε ɞ, g ε ɞ implies that αƒ + (1 - α)g ε ɞ for all α in the range 0 ≤ α ≤ 1.

Here is a demonstration of this: let ɞ denote the set and assume that ƒ ε ɞ. Then-ƒ ε ɞ, and if ɞ is convex so is (1/2)ƒ + 1/2(-ƒ). But the latter is the zero signal, which is not in ɞ. Hence ɞ is not convex.

Weak or inner-product convergence to ƒ implies that (ƒk, g) → (ƒ, g) for any g ℋ ℋ A more-familiar notion is strong convergence, which in a normed space is ‖ƒ-ƒk‖ → 0. In some cases ƒn, in Eq. (3) converges strongly to ƒ. This point is discussed in greater detail by Youla.11

To a scale factor.

The error defined in Eq. (26) is consistent with that given by Youla,10 Hayes,5 and Hayes et al.4 Some authors, e.g., Fienup,19 in order to avoid using a definition involving an unknown ƒ, use other definitions.

Tisnonexpansiveiffor every x,y εℋ, ‖Ty - Tx‖ ≤ ‖x - y‖. A proof that T1 or, more generally, T as given in Eq. (4) is nonexpansive is furnished by Youla.11

Re[ƒ] denotes the real part of ƒ.

T. Quatieri, "Phase estimation with application to speech analysis," Sc.D. Dissertation (Massachusetts Institute of Technology, Cambridge, Mass., 1979).

Corollary 1 of Ref. 11: Let ɞ be a closed convex subset of ℋThen, for any x εℋ, y ε ɞ, Re[(x - Pɞx,y - Pɞx)] ≤ 0.

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.