Search

Abstract: We propose two fast methods for dominant point detection and polygonal representation of noisy and possibly disconnected curves based on a study of the decomposition of the curve into the sequence of maximal blurred segments . Starting from results of discrete geometry , the notion of maximal blurred segment of width has been proposed, well adapted to possibly noisy curves. The first method uses a fixed parameter that is the width of considered maximal blurred segments. The second method is deduced from the first one based on a multi-width approach to obtain a non-parametric method that uses no threshold for working with noisy curves. Comparisons with other methods in the literature prove the efficiency of our approach. Thanks to a recent result concerning the construction of the sequence of maximal blurred segments, the complexity of the proposed methods is O(n log n). An application of vectorization is also given in this paper. [Copyright &y& Elsevier]

Abstract: The concept of blurred segment is introduced, it allows the flexible segmentation of discrete curves, taking into account noise. Relying on an arithmetic definition of discrete lines [J.-P. Reveillès, Géométrie discrète, calculs en nombre entiers et algorithmique, Thèse d’état, Université Louis Pasteur, Strasbourg, 1991], it generalizes such lines, admitting that some points are missing. Thus, a larger class of objects is considered. A very efficient linear detection algorithm for blurred segments and its application to curve segmentation are presented. [Copyright &y& Elsevier]

The convexity of a discrete region is a property used in numerous domains of computational imagery. We study its detection in the particular case of polyominoes. We present a first method, directly relying on its definition. A second method, which is based on techniques for segmentation of curves in discrete lines, leads to a very simple, linear, algorithm whose correctness is proven. Correlatively, we obtain a characterisation of lower and upper frontiers of the convex hull of a discrete line segment. Finally, we evoke some applications of these results to the problem of discrete tomography. [Copyright &y& Elsevier]