a subset D of a given data set S such that a geometric primitive can be fitted to the points of D with a fitting cost below
We propose a constructive method for fitting and extracting geometric primitives. This method formalizes the merging proa given threshold. Depending on the context, additional cess of geometric primitives, which is often used in computer constraints may be imposed on the subset D. The subset vision. Constructive fitting starts from small uniform fits of the must be either connected, convex, have a minimal or maxidata, which are called elemental fits, and uses them to construct mal size, or it must satisfy certain distance constraints. larger uniform fits. We present formal results that involve the Since for a large set the number of its subsets is very calculation of the fitting cost, the way in which the elemental large, the extraction of geometric primitives is often comfits must be selected, and the way in which they must be computationally expensive. Several techniques have been inbined to construct a large fit. The rules used to combine the troduced to speed up the extraction process, and to take elemental fits are very similar to the engineering principles into account the additional constraints imposed on the used when building rigid mechanical constructions with rods subset D. Commonly used methods are the Hough transand joins. In fact, we will characterize the quality of a large form, the minimal subset principle, or a combination of fit by a rigidity parameter. Because of its bottom-up approach both methods such as the randomized Hough transform constructive fitting is particularly well suited for the extraction [1,[4][5][6]. Characteristic for these techniques is their use of of geometric primitives when there is a need for a flexible primitive parameters. The Hough transform maps each system. To illustrate the main aspects of constructive fitting point of the data set onto a manifold in the parameter we discuss the following applications: exact Least Median of Squares fitting, linear regression with a minimal number of space. A minimal subset is the smallest subset that uniquely elemental fits, the design of a flatness estimator to compute the defines a primitive; e.g., two points define a straight line. A local flatness of an image, the decomposition of a digital arc minimal subset based extraction algorithm will repeatedly into digital straight line segments, and the merging of circle choose a minimal subset, compute the corresponding primsegments.