  We initiate a systematic study of tolerant testers of image properties or,
equivalently, algorithms that approximate the distance from a given image to
the desired property (that is, the smallest fraction of pixels that need to
change in the image to ensure that the image satisfies the desired property).
Image processing is a particularly compelling area of applications for
sublinear-time algorithms and, specifically, property testing. However, for
testing algorithms to reach their full potential in image processing, they have
to be tolerant, which allows them to be resilient to noise. Prior to this work,
only one tolerant testing algorithm for an image property (image partitioning)
has been published.
  We design efficient approximation algorithms for the following fundamental
questions: What fraction of pixels have to be changed in an image so that it
becomes a half-plane? a representation of a convex object? a representation of
a connected object? More precisely, our algorithms approximate the distance to
three basic properties (being a half-plane, convexity, and connectedness)
within a small additive error $\epsilon$, after reading a number of pixels
polynomial in $1/\epsilon$ and independent of the size of the image. The
running time of the testers for half-plane and convexity is also polynomial in
$1/\epsilon$. Tolerant testers for these three properties were not investigated
previously. For convexity and connectedness, even the existence of distance
approximation algorithms with query complexity independent of the input size is
not implied by previous work. (It does not follow from the VC-dimension bounds,
since VC dimension of convexity and connectedness, even in two dimensions,
depends on the input size. It also does not follow from the existence of
non-tolerant testers.)
