Inversion of band-limited discrete Fourier transforms of binary images: Uniqueness and algorithms

Conventional inversion of the discrete Fourier transform (DFT) requires all DFT coefficients to be known. When the DFT coefficients of a rasterized image (represented as a matrix) are known only within a pass band, the original matrix cannot be uniquely recovered. In many cases of practical importance, the matrix is binary and its elements can be reduced to one of the two values, either 0 or 1. This is the case, for example, for the commonly used QR codes. The a priori information that the matrix is binary can compensate for the missing high-frequency DFT coefficients and restore uniqueness of image recovery. In this paper, we theoretically investigate the smallest band limit for which unique recovery of a generic binary matrix is still possible. The results depend on the dimensions of the matrix. Uniqueness results are proven for the dimensions $p \times q$, $p \times p$, and $p^\alpha\times p^\alpha$, where $p \neq q$ are prime numbers and $\alpha>1$ an integer. Inversion algorithms are proposed for uniquely recovering the matrix from its band-limited (blurred) version. The algorithms combine integer linear programming methods with lattice basis reduction techniques and significantly outperform naive implementations. The algorithm efficiently and reliably reconstructs severely blurred $29 \times 29$ binary matrices with only 121 out of the total of 841 DFT coefficients using only the binarity assumption and no other constraint on the image.