Fast Fourier Transform on FCC and BCC Lattices with Outputs on FCC and BCC Lattices Respectively | Journal of Mathematical Imaging and Vision Skip to main content
Springer Nature Link
Log in

Fast Fourier Transform on FCC and BCC Lattices with Outputs on FCC and BCC Lattices Respectively

  • Published:
Journal of Mathematical Imaging and Vision Aims and scope Submit manuscript

Abstract

In this paper, we show fast Fourier transform (FFT) algorithms for efficient, non-redundant evaluations of discrete Fourier transforms (DFTs) on face-centered cubic (FCC) and body-centered cubic (BCC) lattices such that the corresponding DFT outputs are on FCC and BCC lattices, respectively. Furthermore, for each of those FFTs, we deduce the structures of its spatial (frequency respectively) domains that are contained in the Voronoi cell centered at 0 with respect to the DFT (inverse DFT respectively) associated sublattice.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

References

  1. Alim, U.R., Möller, T.: A fast Fourier transform with rectangular output on the BCC and FCC lattices. In: Proceedings of 8th International Conference on Sampling Theory and Applications (SampTA2009), Marseille, France (2009)

    Google Scholar 

  2. Averbuch, A., Coifman, R.R., Donoho, D.L., Elad, M., Israeli, M.: Fast and accurate Polar Fourier transform. Appl. Comput. Harmon. Anal. 21, 145–167 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  3. Cassels, T.W.S.: An Introduction to the Geometry of Numbers. Springer, Berlin (1959)

    Book  MATH  Google Scholar 

  4. Conway, J.H., Sloane, N.J.A.: Sphere Packings, Lattices and Groups. Springer, New York (1998)

    Google Scholar 

  5. Csébfalvi, B., Domonkos, B.: Pass-band optimal reconstruction on the body-centered cubic lattice. In: Proceedings of the Vision, Modeling, and Visualization Conference (VMV 2008), Konstanz, Germany, pp. 71–80 (2008)

    Google Scholar 

  6. De Francesco, S., Silva, A.: Fourier Methods in CT Projection and Reconstruction Algorithms, 7th Portuguese Conf. on Biomed. Eng., Libson (2003)

    Google Scholar 

  7. Dudgeon, D., Mersereau, R.M.: Multidimensional Digital Signal Processing. Prentice Hall, Englewood Cliffs (1984)

    MATH  Google Scholar 

  8. Ehrhardt, J.C.: Hexagonal fast Fourier transform with rectangular output. IEEE Trans. Signal Process. 41, 1469–1472 (1993)

    Article  MATH  Google Scholar 

  9. Entezari, A., Möller, T., Vaisey, J.: Subsampling matrices for wavelet decompositions on body centered cubic lattices. IEEE Signal Process. Lett. 11(9), 733–735 (2004)

    Article  Google Scholar 

  10. Guessoum, A., Mersereau, R.M.: Fast algorithms for the multidimensional discrete Fourier transform. IEEE Trans. Acoust. Speech Signal Process. 34(4), 937–943 (1986)

    Article  MathSciNet  Google Scholar 

  11. Knaup, M., Steckmann, S., Bockenbach, O., Kachelriess, M.: Image reconstruction using hexagonal grids. In: IEEE Nuclear Science Symposium Conf. Record, pp. 3074–3076 (2007)

    Google Scholar 

  12. Lanzavecchia, S., Bellon, P.L.: Fast computation of 3D radon transform via a direct Fourier method. Bioinformatics 14(2), 212–216 (1998)

    Article  Google Scholar 

  13. Li, Y., Kummert, A., Boschen, F., Herzog, H.: Interpolation-based reconstruction methods for tomographic imaging in 3D positron emission tomography. Int. J. Appl. Math. Comput. Sci. 18(1), 63–73 (2008)

    Article  Google Scholar 

  14. Mersereau, R.M.: Direct Fourier transform techniques in 3-D image reconstruction. Comput. Biol. Med. 6(4), 247–258 (1976)

    Article  Google Scholar 

  15. Mersereau, R.M., Speake, T.C.: A unified treatment of Cooley-Tukey algorithms for the evaluation of the multidimensional DFT. IEEE Trans. Acoust. Speech Signal Process. 29(5), 1011–1018 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  16. Middleton, L., Sivaswamy, J.: The FFT in a hexagonal-image processing framework. In: Proceedings of Image and Vision Computing, New Zealand, pp. 231–236 (2001)

    Google Scholar 

  17. Vince, A., Zheng, X.: Computing the discrete Fourier transform on a lattice. J. Math. Imaging Vis. 28(2), 125–133 (2007)

    Article  MathSciNet  Google Scholar 

  18. Vince, A., Zheng, X.: Arithmetic and Fourier transform for the PYXIS multi-resolution digital Earth model. Int. J. Digit. Earth 2(1), 59–79 (2009)

    Article  Google Scholar 

  19. Zapata, J.L., Ritter, G.X.: Fast Fourier transform for hexagonal aggregates. J. Math. Imaging Vis. 12(3), 183–197 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  20. Zheng, X.: Efficient Fourier transforms on hexagonal arrays. PhD Dissertation, University of Florida (2007)

Download references

Acknowledgements

This material is based upon work supported by the National Science Foundation/EPSCoR under Cooperative Agreement No. (EPS-0903795), and GEAR project. We would also like to acknowledge the reviewers for their valuable suggestions on the previous versions of this paper.

Author information

Authors and Affiliations

  1. Division of Natural Sciences and Mathematics, Voorhees College, Denmark, SC, 29042, USA

    Xiqiang Zheng

  2. Department of Computer Science, College of Staten Island, Staten Island, NY, 10314, USA

    Feng Gu

Authors
  1. Xiqiang Zheng
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Feng Gu
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Xiqiang Zheng.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Zheng, X., Gu, F. Fast Fourier Transform on FCC and BCC Lattices with Outputs on FCC and BCC Lattices Respectively. J Math Imaging Vis 49, 530–550 (2014). https://doi.org/10.1007/s10851-013-0485-9

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10851-013-0485-9

Keywords