Locating and correcting errors in images

Most image interpolation or extrapolation algorithms assume that the locations of the unknown pixels are known. In this paper we attempt to remove this restriction. More precisely, we propose an algorithm for locating the incorrect pixels of an image, assuming only partial knowledge of its Fourier transform. Note that this is a nonlinear problem: the unknown quantities are the positions and values of the (say) n erroneous pixels. We show that the positions can be evaluated in O(n²) or even O(n log n) flops by solving a set of n linear equations and computing an FFT. The determination of n is part of the algorithm, whose stability is also discussed. The values of the n incorrect pixels can then be estimated using any of the interpolation methods known