Superfast algorithms of multidimensional discrete κ-wave transforms and Volterra filtering based on superfast Radon transform / Labunets V.G., Labunets-Rundblad E.V., Astola J. // Proceedings of SPIE - The International Society for Optical Engineering. - 2001. - V. 4472, l. . - P. 53-64.

ISSN:
0277786X
Type:
Conference Paper
Abstract:
Fast algorithms for a wide class of non-separable n-dimensional (nD) discrete unitary κ-transforms (DKT) are introduced. They need less 1D DKTs than in the case of the classical radix-2 FFT-type approach. The method utilizes a decomposition of the nD κ-transform into the product of a new nD discrete Radon transform and of a set of parallel/independ 1D κ-transforms. If the nD κ-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 comparing to the classical row/column separable approach. It is well known that an nth order Volterra filter of one dimensional signal can be evaluated by an appropriate nD linear convolution. This work describes new superfast algorithm for Volterra filtering. New approach is based on the superfast discrete Radon and Nussbaumer Polynomial Transforms.
Author keywords:
Fast algorithms; Fourier and Nussbaumer transforms; Multidimensional Radon; Volterra filtering
Index keywords:
Algorithms; Digital filters; Fourier transforms; Wavelet transforms; Volterra filtering; Digital signal processing
DOI:
10.1117/12.449740
Смотреть в Scopus:
https://www.scopus.com/inward/record.uri?eid=2-s2.0-0035763162&doi=10.1117%2f12.449740&partnerID=40&md5=789d2cadd56aeb2d760ebbcab88864b5
Соавторы в МНС:
Другие поля
Поле Значение
Link https://www.scopus.com/inward/record.uri?eid=2-s2.0-0035763162&doi=10.1117%2f12.449740&partnerID=40&md5=789d2cadd56aeb2d760ebbcab88864b5
Affiliations Dept. of Automat. and Info. Technol., Urals State Technical University, Ekaterinburg, Russian Federation
Author Keywords Fast algorithms; Fourier and Nussbaumer transforms; Multidimensional Radon; Volterra filtering
References Auslender, L., Feig, E., Winograd, S., New algorithms for the multidimensional discrete Fourier transform (1983) IEEE Trans. Acoust., Spech, Signal Processing, ASSP-31, pp. 388-403. , Apr; Winograd, S., Arithmetic complexity of computations (1980) CBMS-NSF Conf. Series Appl. Math., 33. , SIAM; Nussbaumer, H.J., (1982) Fast Fourier transform and Convolution Algorithms, , Springer- Verlag, Berlin and New York; Yang, D., New fast algorithm to compute two-dimensional discrete Hartley transform (1989) Electronics Letters, 25 (25), pp. 1705-1706; Yang, D., Fast discrete Radon transform and 2D discrete Fourier transform (1990) Electronics Letters, 26 (8), pp. 550-551. , 14 april; Ta, N., Attikiouzel, Y., Crebbin, G., An efficient algorithm for computing two-dimensional discrete cosine transform (1991) Proc. of IEEE ISCAS'91, 1, pp. 396-399; Kelley, B.T., Madesetti, V.K., The fast discrete Radon transform (1992) ICASSP'92, 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 (1992) Proc. of IEEE ISCAS, pp. 160-163. , San Diego. USA; Lun, D.P.K., Siu, W.C., An improved fast Radon transform algorithm for two-dimensional discrete Fourier and Hartley transforms (1992) Proc. of IEEE ISCAS92, pp. 726-729; Hu, N.C., Lu, F.F., Fast computation of the two-dimensional generalized Hartley transforms (1995) IEEE Proc.-Vis. Image Signal Process., 142 (1), pp. 35-39; Shen, T.W., Hsung, T.C., Lun, D.P.K., Inversion algorithm for discrete periodic Radon transform and application on image restoration (1997) IEEE International Symposium on circuits and Systems, pp. 2665-2668. , Hong Kong; Radon, J., Uber die bestimung von functionen durch ihre integralwerte langs gewisser mannigfaltigkeiten (1917) Math.-Phys. Kl., 69, pp. 262-267. , Berichte Sachsische Academie der Wissenschaften, Leipzig; Deans, S.R., (1983) The Radon transform and some of its applications, p. 283. , Wiley; New York; Labunets, V.G., Application of superfast Radon transform for calcucation of multidimensional Fourier transforms and cyclic convolutions. P.1 (1985) All-Union Scientific Conference, pp. 102-110. , in Russian. Methods and Microelectronical Devices of Digital Transform and Processing, Moscow; 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, Institute of Technical Cybernetics of Belarussian Academy of Sciences Press, Minsk; Labunets, V.G., Fast Mersereau-Radon transform. P.1 (1986) Numerical Methods in Control, Radar and Communication, pp. 152-163. , in Russian, Ural Polytechnical Institute Press, Sverdlovsk; Labunets, V.G., Fast Mersereau-Radon transform. P. 2 (1986) Radioelectronics, pp. 16-28. , in Russian, High-Shool Press, Char'kov; Kelley, B.T., Madisetti, V.K., The fast discrete Radon transform - I: Theory (1993) IEEE Trans. IP, 2 (3); Labunets, V.G., (1984) Algebraic Theory of Signals and Systems, P. 1, p. 244. , in Russian, Krasnoyarsk State University Press, Krasnoyarsk; Labunets, V.G., (1989) Algebraic Theory of Signals and Systems. Part 2, p. 196. , in Russia, Ural State University Press, Sverdlovsk; Labunets, E.V., Labunets, V.G., New fast algorithms of multidimensional Fourier and Radon discrete transforms (1998) First International Workshop on Transform and Filter Banks, 1, pp. 14-178. , Tampere, Finland, TICSP Series; Rundblad, E., Labunets, V., Egiazarian, K., Astola, J., A superfast convolution technique for Volterra filtering (1999) Proc. of IEEE-EURASIP Workshop on Nonlinear Signal and Image Processing, pp. 399-403. , Antalya, Turkey, June 20-23; Rundblad-Labunets, E., Labunets, V., Astola, L., Astola, J., Egiazarian, K., Fast algorithms of multidimensional discrete nonseparable κ-wave transformations and volterra filtering (1999) Second International Workshop on Transform and Filter Banks, 3, pp. 337-376. , Tampere, Finland, TICSP Series; Labunets, E.V., Labunets, V.G., Egiazarian, K., Astola, K.J., New fast algorithms of multidimensional fourier and Radon discrete transforms (1999) IEEE Int. Conf. on ASSP, pp. 3193-3196. , Arizona, USA, March 15-19
Correspondence Address Labunets, V.G.; Dept. of Automat. and Info. Technol., Urals State Technical University, Ekaterinburg, Russian Federation; email: lab@cs.tut.fi
Editors Tescher A.G.
Sponsors SPIE
Conference name Applications for Digital Image Processing XXIV
Conference date 31 July 2001 through 3 August 2001
Conference location San Diego, CA
Conference code 59980
CODEN PSISD
Language of Original Document English
Abbreviated Source Title Proc SPIE Int Soc Opt Eng
Source Scopus