×

Algebraic signal processing theory: Cooley-Tukey type algorithms on the 2-D hexagonal spatial lattice. (English) Zbl 1151.65104

Summary: Recently, we introduced the framework for signal processing on a nonseparable 2-D hexagonal spatial lattice including the associated notion of Fourier transform called discrete triangle transform (DTT). Spatial means that the lattice is undirected in contrast to earlier work by R. M. Mersereau [The processing of hexagonally, Proc. IEEE 67, No. 6, 930–949 (1979)] introducing hexagonal discrete Fourier transforms.
In this paper we derive a general-radix algorithm for the DTT of an \(n \times n\) 2-D signal, focusing on the radix-\(2 \times 2\) case. The runtime of the algorithm is \(O (n^{2} \log(n))\), which is the same as for commonly used separable 2-D transforms. The DTT algorithm derivation is based on the algebraic signal processing theory. This means that instead of manipulating transform coefficients, the algorithm is derived through a stepwise decomposition of its underlying polynomial algebra based on a general theorem that we introduce. The theorem shows that the obtained DTT algorithm is the precise equivalent of the well-known Cooley-Tukey fast Fourier transform [cf. J. W. Cooley and J. W. Tukey, Math. Comput. 19, 297–301 (1965; Zbl 0127.09002)], which motivates the title of this paper.

MSC:

65T50 Numerical methods for discrete and fast Fourier transforms
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory

Citations:

Zbl 0127.09002

Software:

AREP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Püschel M. and Rötteler M. (2007). Algebraic signal processing theory: 2-D hexagonal spatial lattice. IEEE Trans. Image Process. 16(6): 1506–1521 · Zbl 05453685 · doi:10.1109/TIP.2007.896626
[2] Püschel, M., Moura, J.M.F.: Algebraic signal processing theory: foundation and 1-D time. Part of [3]; IEEE Trans. Signal Process. (2008, to appear)
[3] Püschel, M., Moura, J.M.F.: Algebraic signal processing theory. Available at http://arxiv.org/abs/cs.IT/0612077 , parts of this manuscript are submitted as [2,4]
[4] Püschel, M., Moura, J.M.F.: Algebraic signal processing theory: 1-D space. Part of [3]; IEEE Trans. Signal Process. (2008, to appear)
[5] Rivlin T.J. (1974). The Chebyshev Polynomials. Wiley Interscience, New York · Zbl 0299.41015
[6] Koornwinder T. (1974). Orthogonal polynomials in two variables which are eigenfunctions of two algebraically independent partial differential operators (part III). Indag. Math. 36: 357–369 · Zbl 0291.33013
[7] Püschel, M., Moura, J.M.F.: Algebraic signal processing theory: Cooley–Tukey type algorithms for DCTs and DSTs. IEEE Trans. Signal Process. (2008, to appear); a longer version is available at http://arxiv.org/abs/cs.IT/0702025 · Zbl 1390.94059
[8] Püschel M. and Moura J.M.F. (2003). The algebraic approach to the discrete cosine and sine transforms and their fast algorithms. SIAM J. Comput. 32(5): 1280–1316 · Zbl 1046.42003 · doi:10.1137/S009753970139272X
[9] Püschel, M., Rötteler, M.: Cooley–Tukey FFT like algorithm for the discrete triangle transform. In: Proceedings of the 11th IEEE DSP Workshop, pp. 158–162 (2004)
[10] Mersereau R.M. (1979). The processing of hexagonally sampled two-dimensional signals. Proc. IEEE 67(6): 930–949 · doi:10.1109/PROC.1979.11356
[11] Dudgeon D.E. and Mersereau R.M. (1984). Multidimensional Digital Signal Processing. Prentice-Hall, Englewood Cliffs · Zbl 0643.94001
[12] Middleton L. and Sivaswamy J. (2005). Hexagonal Image Processing. Springer, Heidelberg · Zbl 1083.68632
[13] Grigoryan A.M. (2002). Hexagonal discrete cosine transform for image coding. IEEE Trans. Signal Process. 50(6): 1438–1448 · Zbl 1369.65186 · doi:10.1109/TSP.2002.1003067
[14] Nussbaumer H.J. (1982). Fast Fourier Transformation and Convolution Algorithms, 2nd edn. Springer, Heidelberg
[15] Steidl G. and Tasche M. (1991). A polynomial approach to fast algorithms for discrete Fourier-cosine and Fourier-sine transforms. Math. Comput. 56(193): 281–296 · Zbl 0725.65145 · doi:10.1090/S0025-5718-1991-1052103-1
[16] Driscoll J.R., Healy D.M. Jr. and Rockmore D. (1997). Fast discrete polynomial transforms with applications to data analysis for distance transitive graphs. SIAM J. Comput. 26: 1066–1099 · Zbl 0896.65094 · doi:10.1137/S0097539792240121
[17] Potts D., Steidl G. and Tasche M. (1998). Fast algorithms for discrete polynomial transforms. Math. Comput. 67(224): 1577–1590 · Zbl 0904.65145 · doi:10.1090/S0025-5718-98-00975-2
[18] Curtis W.C. and Reiner I. (1962). Representation Theory of Finite Groups. Interscience, New York · Zbl 0131.25601
[19] Beth, Th.: Verfahren der Schnellen Fouriertransformation [Fast Fourier Transform Methods]. Teubner (1984)
[20] Clausen, M.: Beiträge zum Entwurf schneller Spektraltransformationen (Habilitationsschrift), University of Karlsruhe (1988)
[21] Clausen M. (1989). Fast generalized Fourier transforms. Theor. Comput. Sci. 67: 55–63 · Zbl 0677.65143 · doi:10.1016/0304-3975(89)90021-2
[22] Clausen, M., Baum, U.: Fast Fourier Transforms. BI-Wiss.-Verl. (1993) · Zbl 0802.65141
[23] Maslen, D., Rockmore, D.: Generalized FFTs–a survey of some recent results. In: Proceedings of IMACS Workshop in Groups and Computation, vol. 28, pp. 182–238 (1995)
[24] Rockmore D. (1990). Fast Fourier analysis for abelian group extensions. Adv. Appl. Math. 11: 164–204 · Zbl 0709.65126 · doi:10.1016/0196-8858(90)90008-M
[25] Maslen, D., Rockmore, D.: Double coset decompositions and computational harmonic analysis on groups. J. Fourier Anal. Appl. 6(4), (2000) · Zbl 0960.43006
[26] Jacobson, N.: Basic Algebra I. W.H. Freeman and Co., San Francisco (1974) · Zbl 0284.16001
[27] Cox D., Little J. and O’Shea D. (1997). Ideals, Varieties, and Algorithms. Springer, Heidelberg
[28] Becker Th. and Weispfenning V. (1993). Gröbner Bases. Springer, Heidelberg · Zbl 0772.13010
[29] Fuhrman P.A. (1996). A Polynomial Approach to Linear Algebra. Springer, New York
[30] Ahmed N., Natarajan T. and Rao K.R. (1974). Discrete cosine transform. IEEE Trans. Comput. C-23: 90–93 · Zbl 0273.65097 · doi:10.1109/T-C.1974.223784
[31] Püschel, M., Rötteler, M.: The discrete triangle transform. Proc. Int. Conf. Acoust. Speech Process., vol. 3, pp. 45–48 (2004)
[32] Voronenko, Y., Püschel, M.: Algebraic derivation of general radix Cooley–Tukey algorithms for the real discrete Fourier transform. Proc. Int. Conf. Acoust. Speech Signal Process., vol. 3, pp. 876–879 (2006)
[33] Auslander L., Feig E. and Winograd S. (1984). Abelian semi-simple algebras and algorithms for the discrete Fourier transform. Adv. Appl. Math. 5: 31–55 · Zbl 0568.65095 · doi:10.1016/0196-8858(84)90003-4
[34] Püschel M. (2002). Decomposing monomial representations of solvable groups. J. Symbolic Comput. 34(6): 561–596 · Zbl 1033.20012 · doi:10.1006/jsco.2002.0566
[35] Egner S. and Püschel M. (2001). Automatic generation of fast discrete signal transforms. IEEE Trans. Signal Process. 49(9): 1992–2002 · Zbl 1369.65183 · doi:10.1109/78.942628
[36] Egner S. and Püschel M. (2004). Symmetry-based matrix factorization. J. Symbolic Comput. 37(2): 157–186 · Zbl 1053.65030 · doi:10.1016/j.jsc.2002.06.005
[37] Chihara T.S. (1978). An Introduction to Orthogonal Polynomials. Gordon and Breach, New York · Zbl 0389.33008
[38] Eier R. and Lidl R. (1982). A class of orthogonal polynomials in k variables. Math. Ann. 260: 93–99 · Zbl 0479.33014 · doi:10.1007/BF01475757
[39] Ricci P.E. (1986). An iterative property of Chebyshev polynomials of the first kind in several variables. Rendiconti di Matematica e delle sue Applicazioni 6(4): 555–563 · Zbl 0671.33010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.