A new two-dimensional Fourier transform algorithm based on image sparsity

Abstract

With the coming age of big data, the image signals play more and more important role in our life due to the extraordinary advance of network communication technology, and the corresponding high efficiency image processing techniques are demanded urgently. The Fourier transform is an important image processing tool which is used in a wide range of applications. Traditional Fourier transform algorithm computes on the value of each point of image, regardless of their properties in frequency domain. However, most image signals possess sparsity in frequency domain. In this paper, we present a new fast two-dimensional Fourier transform based on image sparsity. With hash function including a series of procedures such as random spectrum permutation, filtering and subsampling in frequency domain, the algorithm could identify and estimate the k largest coefficients quickly. In most sparse cases, the resulting algorithm performs faster than state-of-the-art fast Fourier transform algorithm, FFTW.