Tolerant Testers of Image Properties
Berman P. Murzabulatov M. Raskhodnikova S.
10 October 2022Association for Computing Machinery
ACM Transactions on Algorithms
2022#18Issue 4
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. 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.We design efficient approximation algorithms for the following fundamental questions: What fraction of pixels have to be changed in an image so 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 ϵ, after reading poly(1/ϵ) pixels, independent of the image size. We also design an efficient agnostic proper PAC learner of convex sets (continuous and discrete) in two dimensions under the uniform distribution.Our algorithms require very simple access to the input: uniform random samples for the half-plane property and convexity, and samples from uniformly random blocks for connectedness. However, the analysis of the algorithms, especially for convexity, requires many geometric and combinatorial insights. For example, in the analysis of the algorithm for convexity, we define a set of reference polygons Pϵ such that (1) every convex image has a nearby polygon in Pϵ and (2) one can use dynamic programming to quickly compute the smallest empirical distance to a polygon in Pϵ.
Computational geometry , connectedness , convexity , half-plane , property testing , tolerant property testing
Text of the article Перейти на текст статьи
Department of Computer Science and Engineering, The Pennsylvania State University Westgate Building, University Park, 16802, PA, United States
Computer Science Department Nazarbayev University, 53 Kabanbay Batyr Avenue, Block 7, room 7e436, Nur-Sultan city, 010000, Kazakhstan
Department of Computer Science Boston University, 111 Cummington Mall, Boston, 02215, MA, United States
Department of Computer Science and Engineering
Computer Science Department Nazarbayev University
Department of Computer Science Boston University
10 лет помогаем публиковать статьи Международный издатель
Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026