Efficient frequency-domain sample selection for recovering limited-support images

An image whose region of support is smaller than its bounding rectangle can, in principle, be reconstructed from a subset of the Nyquist samples. However, determining such a sampling set that gives a stable reconstruction is a difficult and computationally intensive problem. An algorithm is developed for determining periodic nonuniform sampling patterns that is orders of magnitude faster than existing algorithms. The speedup is achieved by using a sequential selection algorithm and heuristic metrics for the quality of sampling sets that are fast to compute, as opposed to the more rigorous linear algebraic metrics that have been used previously. Simulations show that the sampling sets determined using the new algorithm give image reconstructions that are of accuracy comparable with those determined by other slower algorithms.