Binary Image Fast Perfect Recovery From Sparse 2D-DFT Coefficients

We investigate how to reconstruct a binary image from its sparse 2D discrete Fourier transform (2D-DFT) coefficients. In particular, we only consider the case that image height is equal to its width and is a prime number. We derive the lower bound on the number of coefficients needed to perfectly recover the image. A reconstruction algorithm is also proposed. In our experiment, the lower bound can be achieved when the height is less than 20. As a result, we can efficiently reconstruct a 19×19 binary image using 21 out of the total 361 2D-DFT coefficients, which is about 5.81%