Optimal blurred segments decomposition of noisy shapes in linear time

Blurred segments were introduced by Debled-Rennesson et al. [Segmentation of discrete curves into fuzzy segments. In: 9th IWCIA, Electronic notes in discrete mathematics, vol. 12; 2003; Segmentation of discrete curves into fuzzy segments, extended version. Technical Report, INRIA Report RR-4989, http://www.inria.fr/rrrt/rr-4989.html; 2003] as an extension of the arithmetical approach of Reveillès [Géométrie discrète, calculs en nombres entiers et algorithmique. Thèse d’Etat, Université Louis Pasteur; 1991] on discrete lines, to take into account noise in digital images. A subclass of blurred discrete segments was introduced in [Debled-Rennesson I, Feschet F, Rouyer J. Optimal blurred segments decomposition in linear time. In: Andres E, Damiand G, Lienhardt P, editors, 12th International conference DGCI. Lecture notes in computer science, vol. 3429. Berlin: Springer; 2005. p. 371–82] with an optimal linear time algorithm for the recognition of blurred segment in this class. This paper extends the previous algorithm to deal with very noisy curves and to propose a decomposition somewhat preserving the intuitive notion of corners.