Abstract

An image whose region of support is smaller than its bounding rectangle can, in principle, be reconstructed from a subset of the Nyquist samples. However, determining such a sampling set that gives a stable reconstruction is a difficult and computationally intensive problem. An algorithm is developed for determining periodic nonuniform sampling patterns that is orders of magnitude faster than existing algorithms. The speedup is achieved by using a sequential selection algorithm and heuristic metrics for the quality of sampling sets that are fast to compute, as opposed to the more rigorous linear algebraic metrics that have been used previously. Simulations show that the sampling sets determined using the new algorithm give image reconstructions that are of accuracy comparable with those determined by other slower algorithms.

© 2003 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. A. J. Jerri, “The Shannon sampling theorem—its various extensions and applications: a tutorial review,” Proc. IEEE 65, 1565–1597 (1977).
    [CrossRef]
  2. M. Unser, “Sampling—50 years after Shannon,” Proc. IEEE 88, 569–587 (2000).
    [CrossRef]
  3. K. F. Cheung, R. J. Marks, “Imaging sampling below the Nyquist density without aliasing,” J. Opt. Soc. Am. A 7, 92–105 (1990).
    [CrossRef]
  4. H. J. Landau, “Necessary density conditions for sampling and interpolation of certain entire functions,” Acta Math. 117, 37–52 (1967).
    [CrossRef]
  5. Z. P. Liang, P. C. Lauterbur, Principles of Magnetic Resonance Imaging: A Signal Processing Perspective (IEEE Press, Piscataway, N.J., 2000).
  6. W. N. Brouw, “Aperture synthesis,” in Methods in Computational Physics, B. Alder, S. Fernbach, M. Rotenberg, eds., 14 (Academic, New York, 1975), pp. 131–175.
  7. J. I. Jackson, C. H. Meyer, D. G. Nishimura, A. Macovski, “Selection of a convolution function for Fourier inversion using gridding,” IEEE Trans. Med. Imaging 10, 473–478 (1991).
    [CrossRef]
  8. D. W. Chakeres, P. Schmalbrock, Fundamentals of Magnetic Resonance Imaging (Williams and Wilkins, Baltimore, Md., 1992).
  9. S. J. Reeves, L. P. Heck, “Selection of observations in signal reconstruction,” IEEE Trans. Signal Process. 43, 788–791 (1995).
    [CrossRef]
  10. Y. Gao, S. J. Reeves, “Optimal k-space sampling in MRSI for images with a limited region of support,” IEEE Trans. Med. Imaging 19, 1168–1178 (2000).
    [CrossRef]
  11. P. Feng, Y. Bresler, “Spectrum-blind minimum-rate sampling and reconstruction of multiband signals,” in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (Institute of Electrical and Electronics Engineers, New York, 1996), pp. 1688–1691.
  12. Y. Bresler, P. Feng, “Spectrum-blind minimum rate sampling and reconstruction of 2-D multiband signals,” in Proceedings of the IEEE International Conference on Image Processing (Institute of Electrical and Electronics Engineers, New York, 1996), pp. 701–704.
  13. R. Venkataramani, Y. Bresler, “Further results on spectrum blind sampling of 2D signals,” in Proceedings of the IEEE International Conference on Image Processing (Institute of Electrical and Electronics Engineers, New York, 1998), pp. 752–756.
  14. R. Venkataramani, Y. Bresler, “Optimal sub-Nyquist nonuniform sampling and reconstruction for multiband signals,” IEEE Trans. Signal Process. 49, 2301–2313 (2001).
    [CrossRef]
  15. Y. Gao, S. J. Reeves, “Fast k-space sample selection in MRSI with a limited region of support,” IEEE Trans. Med. Imaging 20, 868–876 (2001).
    [CrossRef] [PubMed]
  16. P. J. Bones, N. Alwesh, T. J. Connolly, N. D. Blakeley, “Recovery of limited-extent images aliased because of spectral undersampling,” J. Opt. Soc. Am. A 18, 2079–2088 (2001).
    [CrossRef]
  17. S. K. Nagle, D. N. Levin, “Multiple region MRI,” Mag. Reson. Med. 41, 774–786 (1999).
    [CrossRef]
  18. N. G. de Bruijn, “Pólya’s theory of counting,” in Applied Combinatorial Mathematics, E. F. Beckenbach, ed. (Wiley, New York, 1964), pp. 144–184.
  19. G. H. Hardy, E. M. Wright, An Introduction to the Theory of Numbers, 3rd ed. (Clarendon, Oxford, UK, 1956).
  20. E. Ayanoǧlu, C.-L. I, R. D. Gitlin, I. Bar-David, “Analog diversity coding to provide transparent self-healing communication networks,” IEEE Trans. Commun. 42, 110–118 (1994).
    [CrossRef]
  21. R. A. Horn, C. R. Johnson, Matrix Analysis (Cambridge University, Cambridge, UK, 1985).
  22. D. O. Walsh, P. A. Nielsen-Delaney, “Direct method for superresolution,” J. Opt. Soc. Am. A 11, 572–579 (1994).
    [CrossRef]
  23. L. A. Shepp, B. F. Logan, “The Fourier reconstruction of a head section,” IEEE Trans. Nucl. Sci. 21, 21–43 (1974).
    [CrossRef]
  24. R. Van de Walle, H. H. Barrett, K. J. Myers, M. I. Altbach, B. Desplanques, A. F. Gmitro, J. Cornelis, I. Lemahieu, “Reconstruction of MR images from data acquired on a general nonregular grid by pseudoinverse calculation,” IEEE Trans. Med. Imaging 19, 1160–1167 (2000).
    [CrossRef]

2001 (3)

R. Venkataramani, Y. Bresler, “Optimal sub-Nyquist nonuniform sampling and reconstruction for multiband signals,” IEEE Trans. Signal Process. 49, 2301–2313 (2001).
[CrossRef]

Y. Gao, S. J. Reeves, “Fast k-space sample selection in MRSI with a limited region of support,” IEEE Trans. Med. Imaging 20, 868–876 (2001).
[CrossRef] [PubMed]

P. J. Bones, N. Alwesh, T. J. Connolly, N. D. Blakeley, “Recovery of limited-extent images aliased because of spectral undersampling,” J. Opt. Soc. Am. A 18, 2079–2088 (2001).
[CrossRef]

2000 (3)

R. Van de Walle, H. H. Barrett, K. J. Myers, M. I. Altbach, B. Desplanques, A. F. Gmitro, J. Cornelis, I. Lemahieu, “Reconstruction of MR images from data acquired on a general nonregular grid by pseudoinverse calculation,” IEEE Trans. Med. Imaging 19, 1160–1167 (2000).
[CrossRef]

Y. Gao, S. J. Reeves, “Optimal k-space sampling in MRSI for images with a limited region of support,” IEEE Trans. Med. Imaging 19, 1168–1178 (2000).
[CrossRef]

M. Unser, “Sampling—50 years after Shannon,” Proc. IEEE 88, 569–587 (2000).
[CrossRef]

1999 (1)

S. K. Nagle, D. N. Levin, “Multiple region MRI,” Mag. Reson. Med. 41, 774–786 (1999).
[CrossRef]

1995 (1)

S. J. Reeves, L. P. Heck, “Selection of observations in signal reconstruction,” IEEE Trans. Signal Process. 43, 788–791 (1995).
[CrossRef]

1994 (2)

E. Ayanoǧlu, C.-L. I, R. D. Gitlin, I. Bar-David, “Analog diversity coding to provide transparent self-healing communication networks,” IEEE Trans. Commun. 42, 110–118 (1994).
[CrossRef]

D. O. Walsh, P. A. Nielsen-Delaney, “Direct method for superresolution,” J. Opt. Soc. Am. A 11, 572–579 (1994).
[CrossRef]

1991 (1)

J. I. Jackson, C. H. Meyer, D. G. Nishimura, A. Macovski, “Selection of a convolution function for Fourier inversion using gridding,” IEEE Trans. Med. Imaging 10, 473–478 (1991).
[CrossRef]

1990 (1)

1977 (1)

A. J. Jerri, “The Shannon sampling theorem—its various extensions and applications: a tutorial review,” Proc. IEEE 65, 1565–1597 (1977).
[CrossRef]

1974 (1)

L. A. Shepp, B. F. Logan, “The Fourier reconstruction of a head section,” IEEE Trans. Nucl. Sci. 21, 21–43 (1974).
[CrossRef]

1967 (1)

H. J. Landau, “Necessary density conditions for sampling and interpolation of certain entire functions,” Acta Math. 117, 37–52 (1967).
[CrossRef]

Altbach, M. I.

R. Van de Walle, H. H. Barrett, K. J. Myers, M. I. Altbach, B. Desplanques, A. F. Gmitro, J. Cornelis, I. Lemahieu, “Reconstruction of MR images from data acquired on a general nonregular grid by pseudoinverse calculation,” IEEE Trans. Med. Imaging 19, 1160–1167 (2000).
[CrossRef]

Alwesh, N.

Ayanoglu, E.

E. Ayanoǧlu, C.-L. I, R. D. Gitlin, I. Bar-David, “Analog diversity coding to provide transparent self-healing communication networks,” IEEE Trans. Commun. 42, 110–118 (1994).
[CrossRef]

Bar-David, I.

E. Ayanoǧlu, C.-L. I, R. D. Gitlin, I. Bar-David, “Analog diversity coding to provide transparent self-healing communication networks,” IEEE Trans. Commun. 42, 110–118 (1994).
[CrossRef]

Barrett, H. H.

R. Van de Walle, H. H. Barrett, K. J. Myers, M. I. Altbach, B. Desplanques, A. F. Gmitro, J. Cornelis, I. Lemahieu, “Reconstruction of MR images from data acquired on a general nonregular grid by pseudoinverse calculation,” IEEE Trans. Med. Imaging 19, 1160–1167 (2000).
[CrossRef]

Blakeley, N. D.

Bones, P. J.

Bresler, Y.

R. Venkataramani, Y. Bresler, “Optimal sub-Nyquist nonuniform sampling and reconstruction for multiband signals,” IEEE Trans. Signal Process. 49, 2301–2313 (2001).
[CrossRef]

R. Venkataramani, Y. Bresler, “Further results on spectrum blind sampling of 2D signals,” in Proceedings of the IEEE International Conference on Image Processing (Institute of Electrical and Electronics Engineers, New York, 1998), pp. 752–756.

P. Feng, Y. Bresler, “Spectrum-blind minimum-rate sampling and reconstruction of multiband signals,” in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (Institute of Electrical and Electronics Engineers, New York, 1996), pp. 1688–1691.

Y. Bresler, P. Feng, “Spectrum-blind minimum rate sampling and reconstruction of 2-D multiband signals,” in Proceedings of the IEEE International Conference on Image Processing (Institute of Electrical and Electronics Engineers, New York, 1996), pp. 701–704.

Brouw, W. N.

W. N. Brouw, “Aperture synthesis,” in Methods in Computational Physics, B. Alder, S. Fernbach, M. Rotenberg, eds., 14 (Academic, New York, 1975), pp. 131–175.

Chakeres, D. W.

D. W. Chakeres, P. Schmalbrock, Fundamentals of Magnetic Resonance Imaging (Williams and Wilkins, Baltimore, Md., 1992).

Cheung, K. F.

Connolly, T. J.

Cornelis, J.

R. Van de Walle, H. H. Barrett, K. J. Myers, M. I. Altbach, B. Desplanques, A. F. Gmitro, J. Cornelis, I. Lemahieu, “Reconstruction of MR images from data acquired on a general nonregular grid by pseudoinverse calculation,” IEEE Trans. Med. Imaging 19, 1160–1167 (2000).
[CrossRef]

de Bruijn, N. G.

N. G. de Bruijn, “Pólya’s theory of counting,” in Applied Combinatorial Mathematics, E. F. Beckenbach, ed. (Wiley, New York, 1964), pp. 144–184.

Desplanques, B.

R. Van de Walle, H. H. Barrett, K. J. Myers, M. I. Altbach, B. Desplanques, A. F. Gmitro, J. Cornelis, I. Lemahieu, “Reconstruction of MR images from data acquired on a general nonregular grid by pseudoinverse calculation,” IEEE Trans. Med. Imaging 19, 1160–1167 (2000).
[CrossRef]

Feng, P.

P. Feng, Y. Bresler, “Spectrum-blind minimum-rate sampling and reconstruction of multiband signals,” in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (Institute of Electrical and Electronics Engineers, New York, 1996), pp. 1688–1691.

Y. Bresler, P. Feng, “Spectrum-blind minimum rate sampling and reconstruction of 2-D multiband signals,” in Proceedings of the IEEE International Conference on Image Processing (Institute of Electrical and Electronics Engineers, New York, 1996), pp. 701–704.

Gao, Y.

Y. Gao, S. J. Reeves, “Fast k-space sample selection in MRSI with a limited region of support,” IEEE Trans. Med. Imaging 20, 868–876 (2001).
[CrossRef] [PubMed]

Y. Gao, S. J. Reeves, “Optimal k-space sampling in MRSI for images with a limited region of support,” IEEE Trans. Med. Imaging 19, 1168–1178 (2000).
[CrossRef]

Gitlin, R. D.

E. Ayanoǧlu, C.-L. I, R. D. Gitlin, I. Bar-David, “Analog diversity coding to provide transparent self-healing communication networks,” IEEE Trans. Commun. 42, 110–118 (1994).
[CrossRef]

Gmitro, A. F.

R. Van de Walle, H. H. Barrett, K. J. Myers, M. I. Altbach, B. Desplanques, A. F. Gmitro, J. Cornelis, I. Lemahieu, “Reconstruction of MR images from data acquired on a general nonregular grid by pseudoinverse calculation,” IEEE Trans. Med. Imaging 19, 1160–1167 (2000).
[CrossRef]

Hardy, G. H.

G. H. Hardy, E. M. Wright, An Introduction to the Theory of Numbers, 3rd ed. (Clarendon, Oxford, UK, 1956).

Heck, L. P.

S. J. Reeves, L. P. Heck, “Selection of observations in signal reconstruction,” IEEE Trans. Signal Process. 43, 788–791 (1995).
[CrossRef]

Horn, R. A.

R. A. Horn, C. R. Johnson, Matrix Analysis (Cambridge University, Cambridge, UK, 1985).

I, C.-L.

E. Ayanoǧlu, C.-L. I, R. D. Gitlin, I. Bar-David, “Analog diversity coding to provide transparent self-healing communication networks,” IEEE Trans. Commun. 42, 110–118 (1994).
[CrossRef]

Jackson, J. I.

J. I. Jackson, C. H. Meyer, D. G. Nishimura, A. Macovski, “Selection of a convolution function for Fourier inversion using gridding,” IEEE Trans. Med. Imaging 10, 473–478 (1991).
[CrossRef]

Jerri, A. J.

A. J. Jerri, “The Shannon sampling theorem—its various extensions and applications: a tutorial review,” Proc. IEEE 65, 1565–1597 (1977).
[CrossRef]

Johnson, C. R.

R. A. Horn, C. R. Johnson, Matrix Analysis (Cambridge University, Cambridge, UK, 1985).

Landau, H. J.

H. J. Landau, “Necessary density conditions for sampling and interpolation of certain entire functions,” Acta Math. 117, 37–52 (1967).
[CrossRef]

Lauterbur, P. C.

Z. P. Liang, P. C. Lauterbur, Principles of Magnetic Resonance Imaging: A Signal Processing Perspective (IEEE Press, Piscataway, N.J., 2000).

Lemahieu, I.

R. Van de Walle, H. H. Barrett, K. J. Myers, M. I. Altbach, B. Desplanques, A. F. Gmitro, J. Cornelis, I. Lemahieu, “Reconstruction of MR images from data acquired on a general nonregular grid by pseudoinverse calculation,” IEEE Trans. Med. Imaging 19, 1160–1167 (2000).
[CrossRef]

Levin, D. N.

S. K. Nagle, D. N. Levin, “Multiple region MRI,” Mag. Reson. Med. 41, 774–786 (1999).
[CrossRef]

Liang, Z. P.

Z. P. Liang, P. C. Lauterbur, Principles of Magnetic Resonance Imaging: A Signal Processing Perspective (IEEE Press, Piscataway, N.J., 2000).

Logan, B. F.

L. A. Shepp, B. F. Logan, “The Fourier reconstruction of a head section,” IEEE Trans. Nucl. Sci. 21, 21–43 (1974).
[CrossRef]

Macovski, A.

J. I. Jackson, C. H. Meyer, D. G. Nishimura, A. Macovski, “Selection of a convolution function for Fourier inversion using gridding,” IEEE Trans. Med. Imaging 10, 473–478 (1991).
[CrossRef]

Marks, R. J.

Meyer, C. H.

J. I. Jackson, C. H. Meyer, D. G. Nishimura, A. Macovski, “Selection of a convolution function for Fourier inversion using gridding,” IEEE Trans. Med. Imaging 10, 473–478 (1991).
[CrossRef]

Myers, K. J.

R. Van de Walle, H. H. Barrett, K. J. Myers, M. I. Altbach, B. Desplanques, A. F. Gmitro, J. Cornelis, I. Lemahieu, “Reconstruction of MR images from data acquired on a general nonregular grid by pseudoinverse calculation,” IEEE Trans. Med. Imaging 19, 1160–1167 (2000).
[CrossRef]

Nagle, S. K.

S. K. Nagle, D. N. Levin, “Multiple region MRI,” Mag. Reson. Med. 41, 774–786 (1999).
[CrossRef]

Nielsen-Delaney, P. A.

Nishimura, D. G.

J. I. Jackson, C. H. Meyer, D. G. Nishimura, A. Macovski, “Selection of a convolution function for Fourier inversion using gridding,” IEEE Trans. Med. Imaging 10, 473–478 (1991).
[CrossRef]

Reeves, S. J.

Y. Gao, S. J. Reeves, “Fast k-space sample selection in MRSI with a limited region of support,” IEEE Trans. Med. Imaging 20, 868–876 (2001).
[CrossRef] [PubMed]

Y. Gao, S. J. Reeves, “Optimal k-space sampling in MRSI for images with a limited region of support,” IEEE Trans. Med. Imaging 19, 1168–1178 (2000).
[CrossRef]

S. J. Reeves, L. P. Heck, “Selection of observations in signal reconstruction,” IEEE Trans. Signal Process. 43, 788–791 (1995).
[CrossRef]

Schmalbrock, P.

D. W. Chakeres, P. Schmalbrock, Fundamentals of Magnetic Resonance Imaging (Williams and Wilkins, Baltimore, Md., 1992).

Shepp, L. A.

L. A. Shepp, B. F. Logan, “The Fourier reconstruction of a head section,” IEEE Trans. Nucl. Sci. 21, 21–43 (1974).
[CrossRef]

Unser, M.

M. Unser, “Sampling—50 years after Shannon,” Proc. IEEE 88, 569–587 (2000).
[CrossRef]

Van de Walle, R.

R. Van de Walle, H. H. Barrett, K. J. Myers, M. I. Altbach, B. Desplanques, A. F. Gmitro, J. Cornelis, I. Lemahieu, “Reconstruction of MR images from data acquired on a general nonregular grid by pseudoinverse calculation,” IEEE Trans. Med. Imaging 19, 1160–1167 (2000).
[CrossRef]

Venkataramani, R.

R. Venkataramani, Y. Bresler, “Optimal sub-Nyquist nonuniform sampling and reconstruction for multiband signals,” IEEE Trans. Signal Process. 49, 2301–2313 (2001).
[CrossRef]

R. Venkataramani, Y. Bresler, “Further results on spectrum blind sampling of 2D signals,” in Proceedings of the IEEE International Conference on Image Processing (Institute of Electrical and Electronics Engineers, New York, 1998), pp. 752–756.

Walsh, D. O.

Wright, E. M.

G. H. Hardy, E. M. Wright, An Introduction to the Theory of Numbers, 3rd ed. (Clarendon, Oxford, UK, 1956).

Acta Math. (1)

H. J. Landau, “Necessary density conditions for sampling and interpolation of certain entire functions,” Acta Math. 117, 37–52 (1967).
[CrossRef]

IEEE Trans. Commun. (1)

E. Ayanoǧlu, C.-L. I, R. D. Gitlin, I. Bar-David, “Analog diversity coding to provide transparent self-healing communication networks,” IEEE Trans. Commun. 42, 110–118 (1994).
[CrossRef]

IEEE Trans. Med. Imaging (4)

Y. Gao, S. J. Reeves, “Fast k-space sample selection in MRSI with a limited region of support,” IEEE Trans. Med. Imaging 20, 868–876 (2001).
[CrossRef] [PubMed]

J. I. Jackson, C. H. Meyer, D. G. Nishimura, A. Macovski, “Selection of a convolution function for Fourier inversion using gridding,” IEEE Trans. Med. Imaging 10, 473–478 (1991).
[CrossRef]

Y. Gao, S. J. Reeves, “Optimal k-space sampling in MRSI for images with a limited region of support,” IEEE Trans. Med. Imaging 19, 1168–1178 (2000).
[CrossRef]

R. Van de Walle, H. H. Barrett, K. J. Myers, M. I. Altbach, B. Desplanques, A. F. Gmitro, J. Cornelis, I. Lemahieu, “Reconstruction of MR images from data acquired on a general nonregular grid by pseudoinverse calculation,” IEEE Trans. Med. Imaging 19, 1160–1167 (2000).
[CrossRef]

IEEE Trans. Nucl. Sci. (1)

L. A. Shepp, B. F. Logan, “The Fourier reconstruction of a head section,” IEEE Trans. Nucl. Sci. 21, 21–43 (1974).
[CrossRef]

IEEE Trans. Signal Process. (2)

S. J. Reeves, L. P. Heck, “Selection of observations in signal reconstruction,” IEEE Trans. Signal Process. 43, 788–791 (1995).
[CrossRef]

R. Venkataramani, Y. Bresler, “Optimal sub-Nyquist nonuniform sampling and reconstruction for multiband signals,” IEEE Trans. Signal Process. 49, 2301–2313 (2001).
[CrossRef]

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

Mag. Reson. Med. (1)

S. K. Nagle, D. N. Levin, “Multiple region MRI,” Mag. Reson. Med. 41, 774–786 (1999).
[CrossRef]

Proc. IEEE (2)

A. J. Jerri, “The Shannon sampling theorem—its various extensions and applications: a tutorial review,” Proc. IEEE 65, 1565–1597 (1977).
[CrossRef]

M. Unser, “Sampling—50 years after Shannon,” Proc. IEEE 88, 569–587 (2000).
[CrossRef]

Other (9)

N. G. de Bruijn, “Pólya’s theory of counting,” in Applied Combinatorial Mathematics, E. F. Beckenbach, ed. (Wiley, New York, 1964), pp. 144–184.

G. H. Hardy, E. M. Wright, An Introduction to the Theory of Numbers, 3rd ed. (Clarendon, Oxford, UK, 1956).

R. A. Horn, C. R. Johnson, Matrix Analysis (Cambridge University, Cambridge, UK, 1985).

P. Feng, Y. Bresler, “Spectrum-blind minimum-rate sampling and reconstruction of multiband signals,” in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (Institute of Electrical and Electronics Engineers, New York, 1996), pp. 1688–1691.

Y. Bresler, P. Feng, “Spectrum-blind minimum rate sampling and reconstruction of 2-D multiband signals,” in Proceedings of the IEEE International Conference on Image Processing (Institute of Electrical and Electronics Engineers, New York, 1996), pp. 701–704.

R. Venkataramani, Y. Bresler, “Further results on spectrum blind sampling of 2D signals,” in Proceedings of the IEEE International Conference on Image Processing (Institute of Electrical and Electronics Engineers, New York, 1998), pp. 752–756.

D. W. Chakeres, P. Schmalbrock, Fundamentals of Magnetic Resonance Imaging (Williams and Wilkins, Baltimore, Md., 1992).

Z. P. Liang, P. C. Lauterbur, Principles of Magnetic Resonance Imaging: A Signal Processing Perspective (IEEE Press, Piscataway, N.J., 2000).

W. N. Brouw, “Aperture synthesis,” in Methods in Computational Physics, B. Alder, S. Fernbach, M. Rotenberg, eds., 14 (Academic, New York, 1975), pp. 131–175.

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

Fig. 1
Fig. 1

Sampling sets involved in the example of 1D to mD conversion in the text.

Fig. 2
Fig. 2

Pseudo-code for the sample selection algorithm. The argmin operator returns the set of arguments that produce the function’s minimum value.

Fig. 3
Fig. 3

Venn diagram showing the success of μF(α). The numbers indicate fractions of Qˆ, the set of unique patterns for small problem sizes.

Fig. 4
Fig. 4

Venn diagram showing the success of μR(α). The numbers indicate fractions of Uˆ, the set of unique universal patterns for small problem sizes.

Fig. 5
Fig. 5

The Shepp–Logan head phantom. The dashed oval indicates the region of support that was used.

Fig. 6
Fig. 6

Recovery of the head phantom test object using sampling patterns selected by our algorithm [(a) and (c)] and Gao and Reeves’ method [(b) and (d)]. In (a)–(d) a 16×16 central portion of the frequency domain illustrates samples measured (●) and not measured (○), and the box indicates the repeated block of 5×4 or 15×8 samples. The spectral samples were corrupted with noise and the images recovered from pattern (a)–(d) are shown in (e) and (g) (our algorithm) and (f) and (h) (Gao and Reeves’ method), respectively.

Tables (2)

Tables Icon

Table 1 Results of Our Algorithm for 1D Small Problem Sizes

Tables Icon

Table 2 Mean Square Errors in the Recoveries

Equations (26)

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

f˜=fmP,
(Dkf˜)=(Dkf)(D0mP),k=0, 1, , L-1,
WNf=F,
α={e|e=(αi+2)modN,i=0, 1, , p-1}.
WN[α|β]f[β]=F[α],
tmetric(WN[α|β])=trace(WN[α|β]HWN[α|β])-1
tmetric(WN[α|β])=i=1min(p,q) 1σi2,
α=α1modN,
βˆ=β[N2N3  Nm+N1N3  Nm++N1N2  Nm-1]modN.
α=00, 22, 21, 32,β=00, 41, 21,
βˆ={0, 2, 11}.
WN[α|β]=1N wN-α0β0wN-α0β1wN-α1β0wN-α1β1,
tmetric(WN[α|β])=2N1-cos2π(α0-α1)(β0-β1)N-1,
(α0-α1)(β0-β1)0(modN).
μF(α)=xFi=1N/2xDixα,
Mp,NF=α|α=argminαQp,N μF(α).
μR(α)=max1δN/2Dδα,
Mp,NR=α|α=argminαUp,N μR(α),
Γ(α)=maxβQp,Ntmetric(WN[α|β])minαUp,NmaxβQp,Ntmetric(WN[α|β]).
Bp,NηdB={α|αUp,N, 10 log Γ(α)η}.
(AHA)ij=1N k=0p-1wNαk(βi-βj),
(BHB)ij=1N k=0p-1wN[(aαk+0)modN]{[(bβi+d)modN]-[(bβj+d)modN]}=1N k=0p-1wN(ab)αk(βi-βj)(byLemma1)=1N k=0p-1wN±αk(βi-βj)=(AHA)ijor (AHA)ij¯.
(A)ij=exp-j2παiβˆjN=exp-j2παiβj(N2N3Nm+N1N3Nm++N1N2Nm-1)N.
(B)ij=exp-j2π(αimodN1)(βjmodN1)N1++(αimodNm)(βjmodNm)Nm,
(B)ij=exp-j2παiβjN1++αiβjNm=exp-j2παiβj(N2N3Nm+N1N3Nm++N1N2Nm-1)N=(A)ij.
A=A11A12A21A22=WN[α|β]WN[α|βc]WN[αc|β]WN[αc|βc].

Metrics