An efficient PAC algorithm for reconstructing a mixture of lines

Sanjoy Dasgupta, Elan Pavlov, Yoram Singer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper we study the learnability of a mixture of lines model which is of great importance in machine vision, computer graphics, and computer aided design applications. The mixture of lines is a partially-probabilistic model for an image composed of line-segments. Observations are generated by choosing one of the lines at random and picking a point at random from the chosen line. Each point is contaminated with some noise whose distribution is unknown, but which is bounded in magnitude. Our goal is to discover efficiently and rather accurately the line-segments that generated the noisy observations. We describe and analyze an efficient probably approximately correct (PAC) algorithm for solving the problem. Our algorithm combines techniques from planar geometry with simple large deviation tools and is simple to implement.

Original languageEnglish (US)
Title of host publicationAlgorithmic Learning Theory - 13th International Conference, ALT 2002, Proceedings
EditorsNicolò Cesa-Bianchi, Masayuki Numao, Rüdiger Reischuk
PublisherSpringer Verlag
Pages351-364
Number of pages14
ISBN (Print)3540001700, 9783540001706
StatePublished - Jan 1 2002
Externally publishedYes
Event13th International Conference on Algorithmic Learning Theory, ALT 2002 - Lübeck, Germany
Duration: Nov 24 2002Nov 26 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2533
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other13th International Conference on Algorithmic Learning Theory, ALT 2002
CountryGermany
CityLübeck
Period11/24/0211/26/02

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'An efficient PAC algorithm for reconstructing a mixture of lines'. Together they form a unique fingerprint.

  • Cite this

    Dasgupta, S., Pavlov, E., & Singer, Y. (2002). An efficient PAC algorithm for reconstructing a mixture of lines. In N. Cesa-Bianchi, M. Numao, & R. Reischuk (Eds.), Algorithmic Learning Theory - 13th International Conference, ALT 2002, Proceedings (pp. 351-364). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2533). Springer Verlag.