Abstract

A noniterative method for superresolution is presented and analyzed. By exploiting the inherent structure of the discrete signal-processing environment, this algorithm reduces the problem of superresolution to that of solving a set of linear equations that relate known frequency samples to unknown time samples. It is shown that the algorithm always produces the correct solution if the known samples are error free and if the system is exactly determined or overdetermined. A technique to reduce the effect of measurement noise on the solution is presented also. It is shown that the noniterative algorithm will produce the same result as the Gerchberg–Papoulis algorithm [ Opt. Acta 21, 709 ( 1974); IEEE Trans. Circuits Syst. CAS-22, 735 ( 1975)]. A simple, one-dimensional example is used to demonstrate the performance of both algorithms in the presence, and in the absence, of noise. The utility of the noniterative algorithm is demonstrated further with another one-dimensional example and then a two-dimensional example.

© 1994 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. D. Slepian, H. O. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty—I,” Bell Syst. Tech. J. 40, 43–64 (1961).
  2. J. L. Harris, “Diffraction and resolving power,”J. Opt. Soc. Am. 54, 931–936 (1964).
    [CrossRef]
  3. D. C. Youla, “Generalized image restoration by the method of alternating orthogonal projections,” IEEE Trans. Circuits Syst. CAS-25, 694–702 (1978).
    [CrossRef]
  4. R. W. Gerchberg, “Super-resolution through error energy reduction,” Opt. Acta 21, 709–720 (1974).
    [CrossRef]
  5. A. Papoulis, “A new algorithm in spectral analysis and band-limited extrapolation,”IEEE Trans. Circuits Syst. CAS-22, 735–742 (1975).
    [CrossRef]
  6. A. K. Jain, S. Ranganath, “Extrapolation algorithms for discrete signals with application in spectral estimation,”IEEE Trans. Acoust. Speech Signal Process. ASSP-29, 830–845 (1981).
    [CrossRef]
  7. D. O. Walsh, P. Nielsen-Delaney, “Coherent super-resolution for a discrete line array,” submitted to IEEE Trans. Antennas Propag.
  8. D. G. Dudley, C. Trantanella, A. Nabulsi, “A Born extension with super-resolution for one-dimensional profile inversion,” in Progress in Electromagnetics Research Symposium (California Institute of Technology, Pasadena, Calif., 1993).
  9. B. J. Sullivan, B. Liu, “On the use of singular value decomposition and decimation in discrete-time band-limited signal extrapolation,”IEEE Trans. Acoust. Speech Signal Process. ASSP-32, 1201–1212 (1984).
    [CrossRef]
  10. W. H. Press, B. Flannery, S. Teukolsky, W. Vetterling, Numerical Recipes (Cambridge U. Press, Cambridge, 1986).
  11. K. E. Atkinson, An Introduction to Numerical Analysis (Wiley, New York, 1978).
  12. D. O. Walsh, “New methods for super-resolution,” M.S. thesis (University of Arizona, Tucson, Ariz., 1993).
  13. M. C. Jones, “The discrete Gerchberg algorithm,” IEEETrans. Acoust. Speech Signal Process. ASSP-34, 624–626 (1986).
    [CrossRef]
  14. R. A. DeCarlo, Linear Systems, a State Variable Approach with Numerical Implementation (Prentice-Hall, Englewood Cliffs, N.J., 1989).
  15. H. S. Tharp, “A numerical algorithm for chained aggregation and modified chained aggregation,” M.S. thesis (University of Illinois, Urbana–Champaign, Ill., 1983).
  16. R. Ayres, Theory and Problems of Matrices (McGraw-Hill, New York, 1962).

1986 (1)

M. C. Jones, “The discrete Gerchberg algorithm,” IEEETrans. Acoust. Speech Signal Process. ASSP-34, 624–626 (1986).
[CrossRef]

1984 (1)

B. J. Sullivan, B. Liu, “On the use of singular value decomposition and decimation in discrete-time band-limited signal extrapolation,”IEEE Trans. Acoust. Speech Signal Process. ASSP-32, 1201–1212 (1984).
[CrossRef]

1981 (1)

A. K. Jain, S. Ranganath, “Extrapolation algorithms for discrete signals with application in spectral estimation,”IEEE Trans. Acoust. Speech Signal Process. ASSP-29, 830–845 (1981).
[CrossRef]

1978 (1)

D. C. Youla, “Generalized image restoration by the method of alternating orthogonal projections,” IEEE Trans. Circuits Syst. CAS-25, 694–702 (1978).
[CrossRef]

1975 (1)

A. Papoulis, “A new algorithm in spectral analysis and band-limited extrapolation,”IEEE Trans. Circuits Syst. CAS-22, 735–742 (1975).
[CrossRef]

1974 (1)

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

1964 (1)

1961 (1)

D. Slepian, H. O. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty—I,” Bell Syst. Tech. J. 40, 43–64 (1961).

Atkinson, K. E.

K. E. Atkinson, An Introduction to Numerical Analysis (Wiley, New York, 1978).

Ayres, R.

R. Ayres, Theory and Problems of Matrices (McGraw-Hill, New York, 1962).

DeCarlo, R. A.

R. A. DeCarlo, Linear Systems, a State Variable Approach with Numerical Implementation (Prentice-Hall, Englewood Cliffs, N.J., 1989).

Dudley, D. G.

D. G. Dudley, C. Trantanella, A. Nabulsi, “A Born extension with super-resolution for one-dimensional profile inversion,” in Progress in Electromagnetics Research Symposium (California Institute of Technology, Pasadena, Calif., 1993).

Flannery, B.

W. H. Press, B. Flannery, S. Teukolsky, W. Vetterling, Numerical Recipes (Cambridge U. Press, Cambridge, 1986).

Gerchberg, R. W.

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

Harris, J. L.

Jain, A. K.

A. K. Jain, S. Ranganath, “Extrapolation algorithms for discrete signals with application in spectral estimation,”IEEE Trans. Acoust. Speech Signal Process. ASSP-29, 830–845 (1981).
[CrossRef]

Jones, M. C.

M. C. Jones, “The discrete Gerchberg algorithm,” IEEETrans. Acoust. Speech Signal Process. ASSP-34, 624–626 (1986).
[CrossRef]

Liu, B.

B. J. Sullivan, B. Liu, “On the use of singular value decomposition and decimation in discrete-time band-limited signal extrapolation,”IEEE Trans. Acoust. Speech Signal Process. ASSP-32, 1201–1212 (1984).
[CrossRef]

Nabulsi, A.

D. G. Dudley, C. Trantanella, A. Nabulsi, “A Born extension with super-resolution for one-dimensional profile inversion,” in Progress in Electromagnetics Research Symposium (California Institute of Technology, Pasadena, Calif., 1993).

Nielsen-Delaney, P.

D. O. Walsh, P. Nielsen-Delaney, “Coherent super-resolution for a discrete line array,” submitted to IEEE Trans. Antennas Propag.

Papoulis, A.

A. Papoulis, “A new algorithm in spectral analysis and band-limited extrapolation,”IEEE Trans. Circuits Syst. CAS-22, 735–742 (1975).
[CrossRef]

Pollak, H. O.

D. Slepian, H. O. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty—I,” Bell Syst. Tech. J. 40, 43–64 (1961).

Press, W. H.

W. H. Press, B. Flannery, S. Teukolsky, W. Vetterling, Numerical Recipes (Cambridge U. Press, Cambridge, 1986).

Ranganath, S.

A. K. Jain, S. Ranganath, “Extrapolation algorithms for discrete signals with application in spectral estimation,”IEEE Trans. Acoust. Speech Signal Process. ASSP-29, 830–845 (1981).
[CrossRef]

Slepian, D.

D. Slepian, H. O. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty—I,” Bell Syst. Tech. J. 40, 43–64 (1961).

Sullivan, B. J.

B. J. Sullivan, B. Liu, “On the use of singular value decomposition and decimation in discrete-time band-limited signal extrapolation,”IEEE Trans. Acoust. Speech Signal Process. ASSP-32, 1201–1212 (1984).
[CrossRef]

Teukolsky, S.

W. H. Press, B. Flannery, S. Teukolsky, W. Vetterling, Numerical Recipes (Cambridge U. Press, Cambridge, 1986).

Tharp, H. S.

H. S. Tharp, “A numerical algorithm for chained aggregation and modified chained aggregation,” M.S. thesis (University of Illinois, Urbana–Champaign, Ill., 1983).

Trantanella, C.

D. G. Dudley, C. Trantanella, A. Nabulsi, “A Born extension with super-resolution for one-dimensional profile inversion,” in Progress in Electromagnetics Research Symposium (California Institute of Technology, Pasadena, Calif., 1993).

Vetterling, W.

W. H. Press, B. Flannery, S. Teukolsky, W. Vetterling, Numerical Recipes (Cambridge U. Press, Cambridge, 1986).

Walsh, D. O.

D. O. Walsh, “New methods for super-resolution,” M.S. thesis (University of Arizona, Tucson, Ariz., 1993).

D. O. Walsh, P. Nielsen-Delaney, “Coherent super-resolution for a discrete line array,” submitted to IEEE Trans. Antennas Propag.

Youla, D. C.

D. C. Youla, “Generalized image restoration by the method of alternating orthogonal projections,” IEEE Trans. Circuits Syst. CAS-25, 694–702 (1978).
[CrossRef]

Bell Syst. Tech. J. (1)

D. Slepian, H. O. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty—I,” Bell Syst. Tech. J. 40, 43–64 (1961).

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

A. K. Jain, S. Ranganath, “Extrapolation algorithms for discrete signals with application in spectral estimation,”IEEE Trans. Acoust. Speech Signal Process. ASSP-29, 830–845 (1981).
[CrossRef]

B. J. Sullivan, B. Liu, “On the use of singular value decomposition and decimation in discrete-time band-limited signal extrapolation,”IEEE Trans. Acoust. Speech Signal Process. ASSP-32, 1201–1212 (1984).
[CrossRef]

IEEE Trans. Circuits Syst. (2)

D. C. Youla, “Generalized image restoration by the method of alternating orthogonal projections,” IEEE Trans. Circuits Syst. CAS-25, 694–702 (1978).
[CrossRef]

A. Papoulis, “A new algorithm in spectral analysis and band-limited extrapolation,”IEEE Trans. Circuits Syst. CAS-22, 735–742 (1975).
[CrossRef]

IEEETrans. Acoust. Speech Signal Process. (1)

M. C. Jones, “The discrete Gerchberg algorithm,” IEEETrans. Acoust. Speech Signal Process. ASSP-34, 624–626 (1986).
[CrossRef]

J. Opt. Soc. Am. (1)

Opt. Acta (1)

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

Other (8)

D. O. Walsh, P. Nielsen-Delaney, “Coherent super-resolution for a discrete line array,” submitted to IEEE Trans. Antennas Propag.

D. G. Dudley, C. Trantanella, A. Nabulsi, “A Born extension with super-resolution for one-dimensional profile inversion,” in Progress in Electromagnetics Research Symposium (California Institute of Technology, Pasadena, Calif., 1993).

W. H. Press, B. Flannery, S. Teukolsky, W. Vetterling, Numerical Recipes (Cambridge U. Press, Cambridge, 1986).

K. E. Atkinson, An Introduction to Numerical Analysis (Wiley, New York, 1978).

D. O. Walsh, “New methods for super-resolution,” M.S. thesis (University of Arizona, Tucson, Ariz., 1993).

R. A. DeCarlo, Linear Systems, a State Variable Approach with Numerical Implementation (Prentice-Hall, Englewood Cliffs, N.J., 1989).

H. S. Tharp, “A numerical algorithm for chained aggregation and modified chained aggregation,” M.S. thesis (University of Illinois, Urbana–Champaign, Ill., 1983).

R. Ayres, Theory and Problems of Matrices (McGraw-Hill, New York, 1962).

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

Fig. 1
Fig. 1

Original time-limited object.

Fig. 2
Fig. 2

For a SNR of 13.75 dB, (a) known portion of diffraction-limited spectrum and (b) time-domain signal.

Fig. 3
Fig. 3

SVD algorithm: three singular vectors retained.

Fig. 4
Fig. 4

G–P algorithm reconstruction: iteration 154

Fig. 5
Fig. 5

Example 1, Case II results: (a) SVD and (b) G–P.

Fig. 6
Fig. 6

Time-domain signal for Example 2.

Fig. 7
Fig. 7

Results of the SVD algorithm for a SNR of 20.18 dB: SVD algorithm output with six right singular vectors retained (solid curve) and original time-domain object (dotted curve).

Fig. 8
Fig. 8

Results of the SVD algorithm for a SNR of 35.75 dB: SVD algorithm output with six right singular vectors retained (solid curve) and original time-domain object (dotted curve).

Fig. 9
Fig. 9

Diffraction-limited image.

Fig. 10
Fig. 10

Result of the SVD algorithm with no additive noise.

Fig. 11
Fig. 11

Result of the SVD algorithm with additive noise.

Equations (14)

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

f = [ f 1 f 2 f 3 0 0 0 0 0 ] ,             F = [ F 1 F 2 F 3 F 4 F 5 F 6 F 7 F 8 ] .
F k + 1 = n = 0 N - 1 f n + 1 W N k n ,
F 1 = f 1 W N 0 + f 2 W N 0 + f 3 W N 0 , F 2 = f 1 W N 0 + f 2 W N 1 + f 3 W N 2 , F 8 = f 1 W N 0 + f 2 W N 7 + f 3 W N 14 .
A = [ 1 1 1 1 W N W N 2 1 W N 7 W N 14 ] ,             x = ( f 1 f 2 f 3 ) ,             b = ( F 1 F 2 F 8 ) .
x = V [ diag ( 1 / w n ) ] [ U T b ] = [ V 11 V 12 V 1 n V 21 V 22 V 2 n V n 1 V n 2 V n n ] [ 1 / w 1 1 / w 2 1 / w n ] [ U 11 U 21 U m 1 U 12 U 22 U m 2 U 1 n U 2 n U m n ] ( b 1 b 2 b m ) = ( 1 / w 1 ) U 1 b ( V 11 V 21 V n 1 ) + ( 1 / w 2 ) U 2 b ( V 12 V 12 V n 2 ) + + ( 1 / w n ) U n b ( V 1 n V 2 n V n n ) ,
e x cond ( A ) r b ,
e x cond ( A ) 1 - cond ( A ) δ A A ( δ A A + r b ) ,
e = V [ diag ( 1 / w n ) ] [ U T r ] = ( 1 / w 1 ) U 1 r ( V 11 V 21 V n 1 ) + ( 1 / w 2 ) U 2 r ( V 12 V 22 V n 2 ) + + ( 1 / w n ) U n r ( V 1 n V 2 n V n n ) .
( 1 / w j ) U j r ( 1 / w j ) r .
Ω f ^ r = F ^ r ,
C f ^ r nonzero = F ^ r replace .
x r = j = 1 n ( 1 - λ j r ) α j Z j + P r x 0 ,
x = j = 1 n α j Z j
[ A ] m × n = [ U ] m × n [ w 1 w 2 w n ] n × n [ V T ] n × n .

Metrics