Fast algorithms of multidimensional discrete nonseparable κ-wave transforms / Rundblad E., Labunets V., Astola J., Egiazarian K. // IEEE Transactions on Signal Processing. - 2002. - V. 50, l. 6. - P. 1496-1507.

ISSN:
1053587X
Type:
Article
Abstract:
Fast algorithms for a wide class of nonseparable n-dimensional (n-D) discrete unitary κ transforms (DKTs) are introduced. They need fewer 1-D DKTs than in the case of the classical radix-2 FFT-type approach. The method utilizes a decomposition of the n-D κ transform into the product of a new n-D discrete Radon transform and of a set of parallel/independ 1-D K transforms. If the n-D κ transform has a separable kernel (e.g., the case of the discrete Fourier transform), our approach leads to decrease of multiplicative complexity by the factor of n, compared with the classical row/column separable approach.
Author keywords:
Fast algorithms; Fourier; Hartley transforms; Multidimensional radon; Nussbaumer transform
Index keywords:
Discrete unitary K transforms; Hartley transforms; Multidimensional Radon; Nussbaumer transform; Radon transform; Algorithms; Computational complexity; Inverse problems; Mathematical operators; Mathem
DOI:
10.1109/TSP.2002.1003072
Смотреть в Scopus:
https://www.scopus.com/inward/record.uri?eid=2-s2.0-0036612469&doi=10.1109%2fTSP.2002.1003072&partnerID=40&md5=bd272e2e9f720c34050fc01a85b989d6
Соавторы в МНС:
Другие поля
Поле Значение
Link https://www.scopus.com/inward/record.uri?eid=2-s2.0-0036612469&doi=10.1109%2fTSP.2002.1003072&partnerID=40&md5=bd272e2e9f720c34050fc01a85b989d6
Affiliations IEEE, Finland; Information Technologies Department, Ural State Technical University, Ekaterinburg, Russian Federation; Institute of Signal Processing, Tampere University of Technology, Tampere, Finland; Signal Processing Laboratory, Tampere University of Technology, Tampere, Finland
Author Keywords Fast algorithms; Fourier; Hartley transforms; Multidimensional radon; Nussbaumer transform
References Auslender, L., Feig, E., Winograd, S., New algorithms for the multi-dimensional discrete Fourier transform (1983) IEEE Trans. Acoust., Speech, Signal Processing, ASSP-31, pp. 388-403. , Apr; Vulis, M., Ring structures and the discrete Fourier transform I (1985) Adv. Appl. Math., 6, pp. 350-372; Winograd, S., Arithmetic complexity of computations (1980) Proc. CBMS-NSF Conf. Series Appl. Math., (33); Nussbaumer, H.J., (1982) Fast Fourier Transform and Convolution Algorithms, , Berlin/New York: Springer-Verlag; Gertner, I., A new efficient algorithm to compute the two-dimensional discrete Fourier transform (1988) IEEE Trans. IEEE Trans. Acoust., Speech, Signal Processing, 36, pp. 1036-1050. , July; Gertner, I., Refheart, M., A parallel algorithm for 2-D DFT computation with no interprocessor communication (1990) IEEE Trans. Paral. Distrib. Syst., 1, pp. 377-382. , Mar; Yang, D., New fast algorithm to compute two-dimensional discrete Hartley transform (1989) Electron. Lett., 25 (25), pp. 1705-1706; Yang, D., Fast discrete radon transform and 2-D discrete Fourier transform (1990) Electron. Lett., 26 (8), pp. 550-551. , Apr. 14; Yang, D., Fast computation of two-dimensional discrete Fourier transform using fast discrete radon transform Proc. IEEE Reg. 10 Conf. Comput. Commun. Syst., Hong Kong, 1990, pp. 207-210; Ta, N., Attikiouzel, Y., Crebbin, G., An efficient algorithm for computing two-dimensional discrete cosine transform (1991) Proc. IEEE ISCAS, 1, pp. 396-399; Napolitano, L.M., Redinbo, G.R., On the efficiency of 'A new efficient algorithm to compute the two-dimensional discrete Fourier transform (1992) IEEE Trans. Signal Processing, 40, pp. 469-470. , Feb; Kelley, B.T., Madesetti, V.K., The fast discrete radon transform (1992) Proc. ICASSP, 3, pp. 409-412; Lun, D.P.K., Siu, W.C., An improved fast radon transform algorithm for two-dimensional discrete Fourier and Hartley transforms Proc. IEEE ISCAS, San Diego, CA, 1992, pp. 160-163; Lun, D.P.K., Siu, W.C., An improved fast radon transform algorithm for two-dimensional discrete Fourier and Hartley transforms Proc. IEEE ISCAS, 1992, pp. 726-729; Hu, N.C., Lu, F.F., Fast computation of the two-dimensional generalized Hartley transforms (1995) Proc. Inst. Elect. Eng., Vis. Image Signal Process., 142 (1), pp. 35-39; Lun, D.P.K., Hsung, T.C., Siu, W.C., On the convolution property of a new discrete radon transform and its efficient inversion algorithm Proc. ISCAS, 1995, pp. 1892-1895; Hsung, T.C., Lun, D.P.K., Siu, W.C., The discrete periodic radon transform (1996) IEEE Trans. Signal Processing, 44, pp. 2651-2657. , Oct; Shen, T.W., Hsung, T.C., Lun, D.P.K., Inversion algorithm for discrete periodic radon transform and application on image restoration Proc. IEEE Int. Symp. Circuits Syst., Hong Kong, 1997, pp. 2665-2668; Radon, J., Uber die Bestimung von Functionen durch ihre integralwerte langs gewisser Mannigfaltigkeiten (1917) Berichte Sachsische Academie der Wissenschaften: Leipzig, Math.-Phys. Kl., 69, pp. 262-267; Beylkin, G., Generalized radon transform and its application (1982), Ph.D. dissertation, Columbia Univ., New York; Deans, S.R., (1983) The Radon Transform and Some of Its Applications, p. 383. , New York: Wiley; Schultz, P.S., Claerbout, J.F., Velocity estimation and downward continuation by wavefront synthesis (1978) Geophys., 43, pp. 691-714; Bessonova, E.N., Fishman, V.M., Ryaboyan, V.Z., Sitnikova, G.A., The tau method for the inversion of travel times-I: Deep seismic sounding data (1974) J. R. Astron. Soc., 36, pp. 377-398; Bessonova, E.N., Fishman, V.M., Ryaboyan, V.Z., Sitnikova, G.A., The tau method for the inversion of travel times-II: Earth quake data (1976) J. R. Astron. Soc., 46, pp. 87-108; Tatham, R.H., Keeney, J., Noponen, I., Application of the tau-P transform (slant stack) in processing seismic reflection data Proc. 52nd Annu. Meet. SEG, Dallas, TX, 1982; Nakhamkin, S.A., Fan filtration (1969) Izv., Earth Phys., 11, pp. 24-35; Dudgeon, D.E., Mersereau, R.M., (1984) Multidimensional Digital Signal Processing, , Englewood Cliffs, NJ: Prentice-Hall; Chapman, C.H., A new method for computing synthetic seismograms (1978) Geophys. J. R. Astron. Soc., 54, pp. 481-518; Chapman, C.H., Generalized radon transforms and slant stacks (1981) Geophys. J. R. Astron. Soc., 66, pp. 445-453; Phinney, R.A., Chowdhury, K.R., Frazer, L.N., Transformation and analysis of record sections (1981) J. Geophys. Res., 86 (B1), pp. 359-377; Stoffa, P.L., Buhl, P., Diebold, J.B., Freidemann, W., Direct mapping of seismic data to the domain of intercept time and ray parameters, a plane wave decomposition (1981) Geophys., 46, pp. 255-267; Beylkin, G., Discrete radon transform (1987) IEEE Trans. Acoust., Speech, Signal Processing, ASSP-35, pp. 162-172. , Feb; Bolker, E.D., The finite radon transform (1987) Contemp. Math., 63, pp. 27-50; Kung, J.P.S., Reconstructing finite radon transforms (1988) Nuclear Phys. B (Proc. Supl.), 5 A, pp. 44-49; Diaconis, P., Graham, L., Radon transform on Z 2 k (1985) Pacific J. Math., 118, pp. 323-345; Kelley, B.T., Madisetti, V.K., The fast discrete radon transform-I: Theory (1993) IEEE Trans. Image Processing, 2. , May; Matuc, F., Independence and radon projections on compact groups (1988), Ph.D. dissertation (in Slovak), UTIA CSAV, Prague, Czechoslovakia; Labunets, V.G., Application of superfast radon transform for calculation of multidimensional Fourier transforms and cyclic convolutions. P.1 Methods and Microelectronical Devices of Digital Transform and Processing. All-Union Scientific Conference, Moscow, USSR, 1985, pp. 102-110. , (in Russian); Labunets, V.G., The radon transforms: Application for multidimensional Fourier transforms and cyclic convolutions calculation. P.2 (1985) Automatization of Production Technical Preparation, pp. 56-70. , (in Russian); Minsk, USSR: Inst. Techn. Cybern. Belaruss. Acad. Sci. Press; Labunets, V.G., Fast radon transform application for multidimensional Fourier transforms and cyclic convolutions calculation. P.3 Proc. Statist. Methods Signal Process.: Practical Appl., Rep. Conf., Char'kov, USSR, 1985, pp. 37-42. , (in Russian); Labunets, V.G., Superfast multidimensional Fourier-radon transforms and multidimensional convolutions. P.4 Proc. Statist. Methods Signal Process., IX All-Union Seminar "Inform. Theory", Char'kov, USSR, 1985, pp. 140-142. , (in Russian); Labunets, V.G., Fast Mersereau-radon transform. P.1 (1986) Numerical Methods in Control, Radar and Communication, pp. 152-163. , (in Russian); Sverdlovsk USSR; Ural Polytechn. Inst. Press; Labunets, V.G., Fast Mersereau-radon transform. P.2 (1986) Radioelectronics, pp. 16-28. , (in Russian); Char'kov, USSR: High-School; Labunets, V.G., (1984) Algebraic Theory of Signals and Systems, P.1, p. 244. , (in Russian); Krasnoyarsk, USSR: Krasnoyarsk State Univ. Press; Labunets, V.G., (1989) Algebraic Theory of Signals and Systems, Part 2, p. 196. , (in Russian); Sverdlovsk, Russia: Ural State Univ. Press; Labunets, E.V., Labunets, V.G., New fast algorithms of multidimensional Fourier and radon discrete transforms Proc. First Int. Workshop Transform Filter Banks, Ser. TICSP 1 Tampere, Finland Feb. 23-25, 1998, pp. 147-178; Rundblad, E., Labunets, V., Egiazarian, K., Astola, J., A superfast convolution technique for Volterra filtering Proc. IEEE-EURASIP Workshop Nonlinear Signal Image Process., Antalya, Turkey, June 20-23, 1999, pp. 399-403; Rundblad-Labunets, E., Labunets, V., Astola, L., Astola, J., Egiazarian, K., Fast algorithms of multidimensional discrete nonseparable Κ-wave transformations and Volterra filtering Proc. Second Int. Workshop Transform Filter Banks, Ser. TICSP 4 Brandenburg an der Havel, Germany, Mar. 5-7, 1999, pp. 337-376; Labunets, E.V., Labunets, V.G., Egiazarian, K., Astola, J., New fast algorithms of multidimensional Fourier and radon discrete transforms Proc. IEEE Int. Conf. Acoust., Speech, Signal Process., Phoenix, AZ, Mar. 15-19, 1999, pp. 3193-3196
Correspondence Address Rundblad, E.; Information Technologies Department, Ural State Technical University, Ekaterinburg, Russian Federation
CODEN ITPRE
Language of Original Document English
Abbreviated Source Title IEEE Trans Signal Process
Source Scopus