Approximate Testing of Visual Properties

摘要

We initiate a study of property testing as applied to visual properties of images. Property testing is a rapidly developing area investigating algorithms that, with a small number of local checks, distinguish objects satisfying a given property from objects which need to be modified significantly to satisfy the property. We study visual properties of discretized images represented by n x n matrices of binary pixel values. We obtain algorithms with query complexity independent of n for several basic properties: being a half-plane, connectedness and convexity.