Inversion of Band-Limited Discrete Fourier Transforms of Binary Images: Uniqueness and Algorithms
From MaRDI portal
Publication:6168341
Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42B10) Numerical methods for discrete and fast Fourier transforms (65T50) Computing methodologies for image processing (68U10) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08)
Abstract: 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 , , and , where are prime numbers and 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 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.
Recommendations
- A new direct algorithm for image reconstruction from Fourier transform magnitude
- ON DIRECT METHODS FOR TIME-LIMITED SIGNAL AND IMAGE RECONSTRUCTION AND ENHANCEMENT
- scientific article; zbMATH DE number 2086609
- A convergent composite mapping Fourier domain iterative algorithms for 3-D discrete tomography
- scientific article; zbMATH DE number 1551782
Cites work
- A computational introduction to number theory and algebra
- A convergent composite mapping Fourier domain iterative algorithms for 3-D discrete tomography
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A generalized uncertainty principle and sparse representation in pairs of bases
- Algebraic aspects of discrete tomography
- Algorithmic Number Theory
- An uncertainty principle for cyclic groups of prime order
- Analysis of PSLQ, an integer relation finding algorithm
- Applications of integer relation algorithms
- Binary Discrete Fourier Transform and Its Inversion
- Combinatorial Properties of Matrices of Zeros and Ones
- Compressed Sensing With Nonlinear Observations and Related Nonlinear Optimization Problems
- Cutting planes in integer and mixed integer programming
- Deterministic sparse FFT for M-sparse vectors
- Deterministic sparse sublinear FFT with improved numerical stability
- Discrete tomography. Foundations, algorithms, and applications
- Discrete tomography: Determination of finite sets by X-rays
- Enumeration and simulation methods for 0-1 matrices with given marginals
- Factoring polynomials with rational coefficients
- How Small Can a Sum of Roots of Unity Be?
- scientific article; zbMATH DE number 53613 (Why is no real title available?)
- scientific article; zbMATH DE number 3637982 (Why is no real title available?)
- scientific article; zbMATH DE number 1461211 (Why is no real title available?)
- scientific article; zbMATH DE number 2086609 (Why is no real title available?)
- scientific article; zbMATH DE number 1435797 (Why is no real title available?)
- Integer Programming with a Fixed Number of Variables
- Iterative hard thresholding for compressed sensing
- Matrices of zeros and ones
- Matrices of zeros and ones with fixed row and column sum vectors
- Multiresolution Graph Fourier Transform for Compression of Piecewise Smooth Images
- Nonlinear total variation based noise removal algorithms
- On Cutting Planes
- On the computational complexity of reconstructing lattice sets from their X-rays
- On the design of deterministic matrices for fast recovery of Fourier compressible functions
- On the linear independence of spikes and sines
- On the precise number of (0, 1)-matrices in \({\mathfrak A}(R,S)\)
- On the Spectral Radius of Complementary Acyclic Matrices of Zeros and Ones
- On vanishing sums of roots of unity.
- Polynomial Time Algorithms for Finding Integer Relations among Real Numbers
- Principles of Optics
- Progressive Image Denoising Through Hybrid Graph Laplacian Regularization: A Unified Framework
- Random sampling of sparse trigonometric polynomials
- Reducibility among combinatorial problems
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
- Solving a system of linear Diophantine equations with lower and upper bounds on the variables.
- Super-resolution, extremal functions and the condition number of Vandermonde matrices
- The Distribution of Length and Components of the Sum of n Random Unit Vectors
- The Little Engine that Could: Regularization by Denoising (RED)
- The norm of Gaussian periods
- Trigonometric diophantine equations (On vanishing sums of roots of unity)
- Uncertainty Principles and Signal Recovery
- Upholding the diffraction limit in the focusing of light and sound
- Zero-one matrices with zero trace
Cited in
(2)
This page was built for publication: Inversion of Band-Limited Discrete Fourier Transforms of Binary Images: Uniqueness and Algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6168341)
