Nonlinear approximation based image recovery using adaptive sparse reconstructions and iterated denoising-part I: theory

• Published in: IEEE transactions on image processing 2006-03, Vol.15 (3), p.539-554
• Main Author: Guleryuz, O.G.
• Format: Article
• Language: English
• Subjects: Adaptive algorithm; Algorithms; Applied sciences; Artificial Intelligence; Computer Graphics; Computer Simulation; Detection, estimation, filtering, equalization, prediction; Error concealment; Estimates; Exact sciences and technology; Image edge detection; Image Enhancement - methods; Image Interpretation, Computer-Assisted - methods; Image processing; Image reconstruction; image recovery; Image segmentation; Image storage; Imaging, Three-Dimensional - methods; Information Storage and Retrieval - methods; Information, signal and communications theory; inpainting; iterated denoising; Iterative decoding; Mathematical analysis; Miscellaneous; Models, Statistical; Noise reduction; nonlinear approximation; Nonlinear Dynamics; Nonlinearity; Pattern recognition; Pattern Recognition, Automated - methods; Pixel; Reconstruction; Reproducibility of Results; Robustness; Sensitivity and Specificity; Signal and communications theory; Signal processing; Signal Processing, Computer-Assisted; Signal, noise; sparse recovery; sparse representations; Sparsity; Studies; Telecommunications and information theory; Texture; Transforms; Video compression
• ISSN: 1057-7149; 1941-0042
• DOI: 10.1109/TIP.2005.863057

We study the robust estimation of missing regions in images and video using adaptive, sparse reconstructions. Our primary application is on missing regions of pixels containing textures, edges, and other image features that are not readily handled by prevalent estimation and recovery algorithms. We assume that we are given a linear transform that is expected to provide sparse decompositions over missing regions such that a portion of the transform coefficients over missing regions are zero or close to zero. We adaptively determine these small magnitude coefficients through thresholding, establish sparsity constraints, and estimate missing regions in images using information surrounding these regions. Unlike prevalent algorithms, our approach does not necessitate any complex preconditioning, segmentation, or edge detection steps, and it can be written as a sequence of denoising operations. We show that the region types we can effectively estimate in a mean-squared error sense are those for which the given transform provides a close approximation using sparse nonlinear approximants. We show the nature of the constructed estimators and how these estimators relate to the utilized transform and its sparsity over regions of interest. The developed estimation framework is general, and can readily be applied to other nonstationary signals with a suitable choice of linear transforms. Part I discusses fundamental issues, and Part II is devoted to adaptive algorithms with extensive simulation examples that demonstrate the power of the proposed techniques.