Abstract
Hexagonal aggregates are hierarchical arrangements of hexagonal cells. These hexagonal cells may be efficiently addressed using a scheme known as generalized balanced ternary for dimension 2, or GBT2. The objects of interest in this paper are digital images whose domains are hexagonal aggregates. We define a discrete Fourier transform (DFT) for such images. The main result of this paper is a radix-7, decimation-in-space fast Fourier transform (FFT) for images defined on hexagonal aggregates. The algorithm has complexity N log7 N. It is expressed in terms of the p-product, a generalization of matrix multiplication. Data reordering (also known as shuffle permutations) is generally associated with FFT algorithms. However, use of the p-product makes data reordering unnecessary.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
D.E. Dudgeon and R.M. Mersereau, Multidimensional Digital Signal Processing, Prentice Hall: Englewood Cliffs, NJ, 1984.
L. Gibson and D. Lucas, “Spatial data processing using generalized balanced ternary,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, June 1982, pp. 566-571.
L. Gibson and D. Lucas, “Vectorization of raster images using hierarchical methods,” Computer Graphics and Image Processing, Vol. 20, pp. 82-89, 1982.
L. Gibson and D. Lucas, “Pyramidal algorithms for automated target recognition,” in Proceedings of the IEEE National Aerospace and Electronics Conference-NAE-CON, Dayton, Ohio, 1986, pp. 215-219.
R.C. Gonzalez and R.E. Woods, Digital Image Processing, Addison-Wesley: Reading, MA, 1992.
D. Lucas and L. Gibson, “Image pyramid partitions,” in Seventh International Conference on Pattern Recognition, Montreal, Canada, July 1984, pp. 230-233.
D. Lucas and L. Gibson, “Techniques to exploit the relation between polynomial representations and moments of pictures,” in Proceedings IEEE Conference on Computer Vision and Pattern Recognition, San Francisco, CA, July 1985, pp. 138-143.
R.M. Mersereau and T.S. Speake, “The processing of periodically sampled multidimensional signals,” IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol. ASSP-31, No. 1, pp. 188-194, 1983.
D.P. Petersen and D. Middleton, “Sampling and reconstruction of wave-number limited functions in n-dimensional euclidean spaces,” Information and Control, Vol. 5, pp. 279-323, 1962.
G.X. Ritter and J.N. Wilson, Handbook of Computer Vision Algorithms in Image Algebra, CRC Press: Boca Raton, 1996.
A. Vince, W. Zhang-Kitto, and D.C. Wilson, “An isomorphism theorem between the p-adic integers and a ring associated with a tiling of n-space by permutohedra,” Discrete and Applied Mathematics, Vol. 52, pp. 39-51, 1994.
A.B. Watson and A.J. Ahmuda, Jr., “A hexagonal orthogonaloriented pyramid as a model of image representation in the visual cortex,” IEEE Transaction on Biomedical Engineering, Vol. 36, No. 1, pp. 97-106, 1989.
W. Zhang-Kitto, “An Isomorphism Theorem between the Extended Generalized Balanced Ternary Numbers and the p-adic Integers,” Ph.D. dissertation, University of Florida, Gainesville, FL, 1991.
W. Zhang-Kitto and D.C.Wilson, “An isomorphism theorem between the 7-adic integers and the ring associated with a hexagonal lattice,” Journal of Applicable Algebra in Engineering, Communication, and Computation, Vol. 2, pp. 105-118, 1991.
H. Zhu and G.X. Ritter, “The generalized matrix product and the wavelet transform,” Journal of Mathematical Imaging and Vision, Vol. 3, No. 1, pp. 95-104, 1993.
H. Zhu and G.X. Ritter, “The p-product and its applications in signal processing,” SIAM Journal of Matrix Analysis and Applications, Vol. 16, No. 2, pp. 579-601, 1995.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Zapata, J.L., Ritter, G.X. Fast Fourier Transform for Hexagonal Aggregates. Journal of Mathematical Imaging and Vision 12, 183–197 (2000). https://doi.org/10.1023/A:1008370531376
Issue Date:
DOI: https://doi.org/10.1023/A:1008370531376