An efficient and provably correct algorithm for the multiscale estimation of image contours by means of polygonal lines

A large portion of image contours is characterized by local properties such as sharp variations of the image intensity across the contour, The integra tion of local image descriptors estimated by using these local properties i nto curvilinear descriptors is a difficult problem from a theoretical viewp oint because of the combinatorially large number of possible curvilinear de scriptors. To deal with this difficulty, the notion of compressible graphs is introduced and a contour data model is defined leading to an efficient l inear-time algorithm which provably recovers contours with an upper bound o n the approximation error.