Fast adaptive algorithm for two-dimensional Fourier transform

• Autorzy: Puchala D. , Yatsymirskyy M.

Warianty tytułu

PL

Szybki algorytm adaptacyjnego obliczania dwuwymiarowego przekształcenia Fouriera

• Języki publikacji: EN

Abstrakty

EN

Fast adaptive algorithm for two-dimensional Fourier transform is presented. It enables automatic selection of time domain discretisation steps depending on the required accuracy of numerical calculation of signal spectrum. Errors of spectrum calculation can be estimated with help of the proposed formulas constructed in relative and absolute: maximum difference, mean square error and peak signal to noise ratio metrics. All calculations are performed in accordance with the structures of fast time decimated algorithms.

PL

Przedstawiono szybki algorytm adaptacyjnego obliczania dwuwymiarowego przekształcenia Fouriera, umożliwiający dobór kroków dyskretyzacji w zależności od żądanej dokładności numerycznego obliczenia widma, przy czym obliczenia realizowane są w oparciu o struktury szybkich algorytmów z przerzedzeniem w czasie. Ponadto zaproponowano wyrażenia oceny błędu obliczenia widma we względnych i bezwzględnych metrykach: maksymalnego odchylenia, błędu średniokwadratowego oraz szczytowego stosunku sygnału do szumu.

Słowa kluczowe

EN

Fourier transform; adaptive numerical quadratures; fast algorithms

PL

przekształcenie Fouriera; numeryczne kwadratury adaptacyjne; szybkie algorytmy

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2007
• Tom: R. 83, nr 10
• Strony: 43--46
• Opis fizyczny: Bibliogr. 15 poz., rys., tab., wykr.

Twórcy

autor

Puchala D.

autor

Yatsymirskyy M.

• Technical of University, Institute of Computer Science,

Bibliografia

• [1] Diaz De Leon R., Sucar L. E., Human silhouette recognition with Fourier descriptors., Proc. of 15th International Confe-rence on Pattern Recognition, vol. 3, pp. 709-712, IEEE, 2000.
• [2] Harding P.R.G., Ellis T., Recognizing hand gesture using Fourier descriptors., Proc. of 17th International Conference on Pattern Recognition, vol. 3, pp. 286-289, IEEE, 2004.
• [3] Shiqi Yu, Liang Wang, Weiming Hu, Tieniu Tan, Gait analysis for human identification in frequency domain., Proc. of 3rd International Conference on Image and Graphics, pp. 282-285. IEEE, 2004.
• [4] Kunttu I., Lepisto L., Rauhamaa J., Visa A., Multiscale Fourier descriptor for shape classification., Proc. of 12th International Conference on Image Analysis and Processing, pp. 536-541, IEEE, 2003.
• [5] Bartolini I. Ciaccia P. Patella M., WARP: accurate retrieval of shapes using phase of Fourier descriptors and time warping distance., IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 27, issue 1, pp. 142-147, January 2005.
• [6] Puchala D., Yatsymirskyy M., Fast Adaptive Algorithm for Fourier Transform., Proc. of International Conference on Signals and Electronic Systems, pp. 183-185, Łódź, 2006.
• [7] Bracewell R., The Fourier Transform and Its Applications., WNT, Warsaw 1968.
• [8] Allen III M. B., Isaacson E. L., Numerical Analysis for Applied Science., John Wiley and Sons Inc., Nowy Jork 1998.
• [9] Zadiraka W. K., Theory of Calculation of Fourier Transform., Kiev 1983 (in russian).
• [10] Cooley J. W., Lewis P. A., Welch P. D., Application of the Fast Fourier Transform to Computation of Fourier Integrals, Fourier Series, and Convolution Integrals., IEEE Trans. On Audio and Electroacoustics, vol. AU-15, no. 2, pp. 79-84, June 1967.
• [11] Yaroslavsky L. P., Digital Picture Processing. Springer Series in Information Sciences, Berlin Heidelberg 1985.
• [12] Forsyth G., Malcolm M., Moler C., Computer Methods for Mathematical Computations. Prentice Hall, 1977.
• [13] Cooley J.W., Tukey J.W., An Algorithm for the Machine Calculation of Complex Fourier Series., Mathematics of Computation, vol. 19, pp. 297-301, April 1965.
• [14] Duhamel P., Implementation of "Split-Radix" FFT Algorithms for Complex, Real, and Real-Symmetric Data., IEEE Trans. On Acoustics. Speech, and Signal Process. vol. ASSP-34. no. 2, pp. 285-295, April 1986.
• [15] Skarbek W. et al, MULTIMEDIA. Algorytmy i standardy kompresji., PLJ, Warsaw 1998.