Recovery of missing segments and lines in images

H.G. Feichtinger and T.Strohmer

The so-called irregular sampling problem is concerned with the problem of reconstruction of an image from irregularly located samples. In a series of papers (many of them together with K. Gröchenig) the authors have developed new algorithms for efficient reconstruction of signals from arbitrary sampling sets, which are guaranteed to converge as long as the image is band-limited and the sampling set does not have too big holes. It is however experimental evidence that for a typical real world image very satisfactory reconstructions can be obtained even if it is not band-limited in the strict sense.

In the present paper only a certain type of irregularities is considered, i.e. missing lines or missing rectangles in a given image. This problem occurs in practical situations where such parts may be lost during the transmission of an image or badly recorded by a camera. The basic idea is to solve the problem by iterative solution of one-dimensional subproblems, i.e. by interpolation along horizontal and then vertical lines or vice versa. The use of fast and efficient 1-D reconstruction methods is the basis for very fast and highly parallelizable algorithm. We demonstrate the efficiency of the product ACT algorithm by typical applications.

Keywords: algorithms, irregular sampling, numerical work

Download the paper as a GNU-zipped postscript file (847243 bytes).