A large portion of image contours is characterized by local properties such as sharp variations of the image intensity across the contour. The integration of local image descriptors estimated by using these local properties into curvilinear descriptors is a difficult problem from a theoretical viewpoint because of the combinatorially large number of possible curvilinear descriptors. To deal with this difficulty, the notion of compressible graphs is introduced and a contour data model is defined leading to an efficient linear-time algorithm which provably recovers contours with an upper bound on the approximation error.

Efficient edge detection algorithms such as Canny's (1986) fail near curve singularities. Moreover, the standard linking algorithms used on top of these detectors often fail because of instabilities in the tracking process (due to multiple responses to the same edge and interference of nearby edges). We propose a hierarchical approach to edge detection based on a graph stabilization method that allows bifurcation resolution in stages. Curve singularities are recovered at the last stage by using "top-down" feedback to select the best curve connections.