2019/08/07 by Sheng Shi, Shi, Sheng, Runkai Yang +3
Computer Science · Engineering · #Advanced Fiber Optic Sensors #FOS: Electrical engineering #Image and Signal Denoising Methods #Image and Video Processing (eess.IV) #Optical Coherence Tomography Applications #Signal Processing (eess.SP) #eess.IV #eess.SP #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.1908.02461
openalex publication_date 2019/08/07 · openalex created_date 2019/08/13 · arxiv created 2020/02/24 · arxiv updated 2020/02/25 · openalex updated_date 2026/07/28
The Fast Fourier Transform(FFT) is a classic signal processing algorithm that is utilized in a wide range of applications. For image processing, FFT computes on every pixel's value of an image, regardless of their properties in frequency domain. The Sparse Fast Fourier Transform (SFFT) is an innovative algorithm for discrete Fourier transforms on signals that possess characteristics of the sparsity in frequency domain. A reference implementation of the algorithm has been proven to be efficient than modern FFT library in cases of sufficient sparsity. However, the SFFT implementation has a critical drawback that it only works reliably for very specific input parameters, especially signal sparsity k, which hinders the extensive application of SFFT. In this paper, we propose an Adaptive Tuning Sparse Fast Fourier Transform (ATSFFT), which is a novel sparse fast fourier transform enabled with sparsity detection. In the case of unknown sparsity k, ATSFFT is capable of probing the sparsity k via adaptive dynamic tuning and completing the sparse Fourier transform. Experimental results show that ATSFFT outperforms SFFT while it is able to control the computation error better than SFFT. Furthermore, ATSFFT achieves an order of magnitude of performance improvement than the state-of-the-art FFT library, FFTW.