Document Open Access Logo

Tolerant Testers of Image Properties

Authors Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.90.pdf
  • Filesize: 1.13 MB
  • 14 pages

Document Identifiers

Author Details

Piotr Berman
Meiram Murzabulatov
Sofya Raskhodnikova

Cite As Get BibTex

Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova. Tolerant Testers of Image Properties. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 90:1-90:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.90

Abstract

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.)

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_{epsilon} such that (1) every convex image has a nearby polygon in P_{epsilon} and (2) one can use dynamic programming to quickly compute the smallest empirical distance to a polygon in P_{epsilon}. This construction might be of independent interest.

Subject Classification

Keywords
  • Computational geometry
  • convexity
  • half-plane
  • connectedness
  • propertytesting
  • tolerant property testing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Imre Barany. Extremal problems for convex lattice polytopes: a survey. Contemporary Mathematics, 2000. Google Scholar
  2. Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova. Testing convexity of figures under the uniform distribution. In SoCG, 2016. Google Scholar
  3. Piotr Berman, Sofya Raskhodnikova, and Grigory Yaroslavtsev. L_p-testing. In STOC, pages 164-173, 2014. URL: http://dx.doi.org/10.1145/2591796.2591887.
  4. Avrim Blum. Machine learning theory. Lecture notes. URL: http://www.cs.cmu.edu/~avrim/ML12/lect0201.pdf.
  5. Andrea Campagna, Alan Guo, and Ronitt Rubinfeld. Local reconstructors and tolerant testers for connectivity and diameter. In APPROX-RANDOM, pages 411-424, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40328-6_29.
  6. Artur Czumaj and Christian Sohler. Property testing with geometric queries. In Algorithms - ESA 2001, 9th Annual European Symposium, Aarhus, Denmark, August 28-31, 2001, Proceedings, pages 266-277, 2001. URL: http://dx.doi.org/10.1007/3-540-44676-1_22.
  7. Artur Czumaj, Christian Sohler, and Martin Ziegler. Property testing in computational geometry. In Algorithms - ESA 2000, 8th Annual European Symposium, Saarbrücken, Germany, September 5-8, 2000, Proceedings, pages 155-166, 2000. URL: http://dx.doi.org/10.1007/3-540-45253-2_15.
  8. Andrzej Ehrenfeucht, David Haussler, Michael J. Kearns, and Leslie G. Valiant. A general lower bound on the number of examples needed for learning. Inf. Comput., 82(3):247-261, 1989. Google Scholar
  9. Eldar Fischer and Lance Fortnow. Tolerant versus intolerant testing for boolean properties. Theory of Computing, 2(1):173-183, 2006. URL: http://dx.doi.org/10.4086/toc.2006.v002a009.
  10. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. J. ACM, 45(4):653-750, 1998. URL: http://dx.doi.org/10.1145/285055.285060.
  11. Oded Goldreich and Dana Ron. Property testing in bounded degree graphs. Algorithmica, 32(2):302-343, 2002. URL: http://dx.doi.org/10.1007/s00453-001-0078-7.
  12. David Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Inf. Comput., 100(1):78-150, 1992. URL: http://dx.doi.org/10.1016/0890-5401(92)90010-D.
  13. Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, and Rocco A. Servedio. Agnostically learning halfspaces. SIAM J. Comput., 37(6):1777-1805, 2008. Google Scholar
  14. Michael J. Kearns, Robert E. Schapire, and Linda Sellie. Toward efficient agnostic learning. Machine Learning, 17(2-3):115-141, 1994. URL: http://dx.doi.org/10.1007/BF00993468.
  15. Igor Kleiner, Daniel Keren, Ilan Newman, and Oren Ben-Zwi. Applying property testing to an image partitioning problem. IEEE Trans. Pattern Anal. Mach. Intell., 33(2):256-265, 2011. URL: http://dx.doi.org/10.1109/TPAMI.2010.165.
  16. Simon Korman, Daniel Reichman, and Gilad Tsur. Tight approximation of image matching. CoRR, abs/1111.1713, 2011. URL: http://arxiv.org/abs/1111.1713.
  17. Simon Korman, Daniel Reichman, Gilad Tsur, and Shai Avidan. Fast-match: Fast affine template matching. In CVPR, pages 2331-2338, 2013. URL: http://dx.doi.org/10.1109/CVPR.2013.302.
  18. Michal Parnas, Dana Ron, and Ronitt Rubinfeld. Tolerant property testing and distance approximation. J. Comput. Syst. Sci., 72(6):1012-1042, 2006. URL: http://dx.doi.org/10.1016/j.jcss.2006.03.002.
  19. Sofya Raskhodnikova. Approximate testing of visual properties. In RANDOM-APPROX, pages 370-381, 2003. URL: http://dx.doi.org/10.1007/978-3-540-45198-3_31.
  20. Dana Ron and Gilad Tsur. Testing properties of sparse images. ACM Trans. Algorithms, 10(4):17:1-17:52, 2014. URL: http://dx.doi.org/10.1145/2635806.
  21. Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM J. Comput., 25(2):252-271, 1996. Google Scholar
  22. Bernd Schmeltz. Learning convex sets under uniform distribution. In Data Structures and Efficient Algorithms, Final Report on the DFG Special Joint Initiative, pages 204-213, 1992. Google Scholar
  23. Leslie G. Valiant. A theory of the learnable. Commun. ACM, 27(11):1134-1142, 1984. URL: http://dx.doi.org/10.1145/1968.1972.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact