The farthest point strategy for progressive image sampling

TLDR

The paper introduces a farthest point strategy (FPS) for progressive image acquisition that allows an approximation of the full image at each sampling stage. FPS samples irregularly spaced points that achieve Poisson‑disk‑like anti‑aliasing, can be adapted to image content, and is implemented with an efficient O(N log N) algorithm. FPS maintains uniform sampling density as resolution increases, offers deterministic min‑max uniformity versus stochastic methods, and supports efficient sparse image sampling and display.

Abstract

A new method of farthest point strategy (FPS) for progressive image acquisition-an acquisition process that enables an approximation of the whole image at each sampling stage-is presented. Its main advantage is in retaining its uniformity with the increased density, providing efficient means for sparse image sampling and display. In contrast to previously presented stochastic approaches, the FPS guarantees the uniformity in a deterministic min-max sense. Within this uniformity criterion, the sampling points are irregularly spaced, exhibiting anti-aliasing properties comparable to those characteristic of the best available method (Poisson disk). A straightforward modification of the FPS yields an image-dependent adaptive sampling scheme. An efficient O(N log N) algorithm for both versions is introduced, and several applications of the FPS are discussed.