Double-step incremental generation of lines and circles

An explicit discussion of the possible speed-up of curve generation due to an increase in the size of increment has not appeared in literature. This paper proposes a methodology and its rationale for scan-converting lines and circles two pixels per iteration. The double-step line and circle algorithms require the same amount of integer arithmetic per iteration as the single-step algorithms but only half the number of iterations. The algorithms take advantage of some simple properties of discrete loci of mathematical curves in the raster plane.     

双步圆的反走样生成算法

首先介绍了圆生成算法的发展及现状,接着对绘制圆的Bresenham算法及Kuzmin单点生成算法进行了实验分析及总结,并指出了其存在的优缺点。基于Wu和Rokne双步圆算法提出了新的双步反走样生成算法,使其成为一种反走样效果更佳的方法。该算法的灰度级数是原来Wu和Rokne算法的3倍,且最大灰度误差也比原来的减少了1/4;另外该算法由于只用整数运算,避免了除法,因此便于硬件实现。     

Packing circles within ellipses

The problem of packing circles within ellipses is considered in the present paper. A new ellipse‐based system of coordinates is introduced by means of which a closed formula to compute the distance of an arbitrary point to the boundary of an ellipse exists. Nonlinear programming models for some variants of 2D and 3D packing problems involving circular items and elliptical objects are given. The resulting models are medium‐sized highly challenging nonlinear programming problems for which a global solution is sought. For this purpose, multistart strategies are carefully and thoroughly explored. Numerical experiments are exhibited.     

Clustering ellipses for anomaly detection

Comparing, clustering and merging ellipsoids are problems that arise in various applications, e.g., anomaly detection in wireless sensor networks and motif-based patterned fabrics. We develop a theory underlying three measures of similarity that can be used to find groups of similar ellipsoids in p-space. Clusters of ellipsoids are suggested by dark blocks along the diagonal of a reordered dissimilarity image (RDI). The RDI is built with the recursive iVAT algorithm using any of the three (dis) similarity measures as input and performs two functions: (i) it is used to visually assess and estimate the number of possible clusters in the data; and (ii) it offers a means for comparing the three similarity measures. Finally, we apply the single linkage and CLODD clustering algorithms to three two-dimensional data sets using each of the three dissimilarity matrices as input. Two data sets are synthetic, and the third is a set of real WSN data that has one known second order node anomaly. We conclude that focal distance is the best measure of elliptical similarity, iVAT images are a reliable basis for estimating cluster structures in sets of ellipsoids, and single linkage can successfully extract the indicated clusters.     

曲线的像素级双步绘制算法

现有的绘制曲线的算法都是单步的。提出了一个双步绘制曲线的通用算法,算法的每一步可以绘制两个像素点。以三次Bezier曲线的绘制为例给出了具体实现过程。给出了算法的伪代码过程。给出了算法的计算量比较结果。结果表明提出的双步算法与单步算法相比,计算量有了较大幅度的减少。     

Unbiased estimation of ellipses by bootstrapping

A general method for eliminating the bias of nonlinear estimators using bootstrap is presented. Instead of the traditional mean bias we consider the definition of bias based on the median. The method is applied to the problem of fitting ellipse segments to noisy data. No assumption beyond being independent identically distributed is made about the error distribution and experiments with both synthetic and real data prove the effectiveness of the technique     

Arc-based evaluation and detection of ellipses

We propose the use of elliptic arcs as a reliable criterion for ellipse evaluation and reconstruction. A technique based on pixel connectivity is developed for detecting the endpoints and subtended angles of elliptic arcs. Model-based distance and angular connectivity are introduced for quick and meaningful estimation of elliptic arcs. An iterative algorithm for multiple-ellipse fitting based on arc detection is presented. Experimental results confirm the robustness and accuracy of the algorithm for the fitting of multiple overlapping ellipses.     

Direct least square fitting of ellipses

This work presents a new efficient method for fitting ellipses to scattered data. Previous algorithms either fitted general conics or were computationally expensive. By minimizing the algebraic distance subject to the constraint 4ac-b²=1, the new method incorporates the ellipticity constraint into the normalization factor. The proposed method combines several advantages: It is ellipse-specific, so that even bad data will always return an ellipse. It can be solved naturally by a generalized eigensystem. It is extremely robust, efficient, and easy to implement     

Projective reconstruction of ellipses from multiple images

This paper presents a new approach for reconstructing 3D ellipses (including circles) from a sequence of 2D images taken by uncalibrated cameras. Our strategy is to estimate an ellipse in 3D space by reconstructing N(≥5) 3D points (called representative points) on it, where the representative points are reconstructed by minimizing the distances from their projections to the measured 2D ellipses on different images (i.e., 2D reprojection error). This minimization problem is transformed into a sequence of minimization sub-problems that can be readily solved by an algorithm which is guaranteed to converge to a (local) minimum of the 2D reprojection error. Our method can reconstruct multiple 3D ellipses simultaneously from multiple images and it readily handles images with missing and/or partially occluded ellipses. The proposed method is evaluated using both synthetic and real data.     

Algorithms for drawing anti-aliased circles and ellipses

Fast algorithms for pre-filtered anti-aliasing previously operated solely on straight line objects; this work extends the class of objects to include circles and ellipses. The new algorithms do not require floating point, square root, or division operations in the inner loops. When rendering against a constant background, a single inner loop multiapplication operation may also be eliminated. We describe in detail how the technique is applied to rendering an octant of a filled circle using a square area integration filter. We briefly describe the extensions necessary for different types of anti-aliased circles and ellipses. We show how pre-computed filters stored in a lookup table may be implemented.     

Analysing error of fit functions for ellipses

We describe several established error of fit (EOF) functions for use in the least square fitting of ellipses, and introduce a further four new EOFs. Four measures are used for assessing the suitability of such EOFs, quantifying their linearity, curvature bias, asymmetry, and overall goodness. These measures enable a better understanding to be gained of the individual merits of the EOF functions.     

用两步Hough变换检测圆

Hough变换在图像处理中占有重要地位,是一种检测曲线的有效方法。但使用传统的Hough变换来检测圆,具有存储空间大计算时间长的缺点。为此提出了采用两步Hough变换的圆检测方法,利用圆的斜率特性,降低了Hough参数空间的维度,提高了运算效率,并推广到椭圆的检测之中。     

Least eccentric ellipses for geometric Hermite interpolation

We present a rational Bézier solution to the geometric Hermite interpolation problem. Given two points and respective unit tangent vectors, we provide an interpolant that can reproduce a circle if possible. When the tangents permit an ellipse, we produce one that deviates least from a circle. We cast the problem as a theorem and provide its proof, and a method for determining the weights of the control points of a rational curve. Our approach targets ellipses, but we also present a cubic interpolant that can find curves with inflection points and space curves when an ellipse cannot satisfy the tangent constraints.     

Efficiency of characterizing ellipses and ellipsoids by discretemoments

In this paper, our studies are focused on ellipses and problems related to their representation and reconstruction from the data resulting from their digitization. The main result of the paper is that a finite number of discrete moments, corresponded to digital ellipses, is in one-to-one correspondence with digital ellipses, which enables coding of digital ellipses with an asymptotically optimal amount of memory. In addition, the problem of reconstruction, based on the same parameters, is considered. Since the digitization of real shapes causes an inherent loss of information about the original objects, the precision of the original shape estimation from the corresponding digital data is limited. We derive a sharp upper bound for the errors in reconstruction of the center position and half-axes of the ellipse, in function of the applied picture resolution (i.e., the number of pixels per unit). An extension of these results to the 3D case is also given     

Hyper least squares fitting of circles and ellipses

This work extends the circle fitting method of Rangarajan and Kanatani (2009) to accommodate ellipse fitting. Our method, which we call HyperLS, relies on algebraic distance minimization with a carefully chosen scale normalization. The normalization is derived using a rigorous error analysis of least squares (LS) estimators so that statistical bias is eliminated up to second order noise terms. Numerical evidence suggests that the proposed HyperLS estimator is far superior to the standard LS and is slightly better than the Taubin estimator. Although suboptimal in comparison to maximum likelihood (ML), our HyperLS does not require iterations. Hence, it does not suffer from convergence issues due to poor initialization, which is inherent in ML estimators. In this sense, the proposed HyperLS is a perfect candidate for initializing the ML iterations.     

A decomposable parameter space for the detection of ellipses

Hough transform is a well-known method for detecting parametric curves in binary images. One major drawback of the method is that the transform requires time and memory space exponential in the number of parameters of the curves. An effective approach to reduce both the time and space requirement is the parameter space decomposition. In this paper, we present two methods for the detection of ellipses based on the straight line Hough transform (SLHT).

The SLHT of a curve in the θ-π space can be expressed as the sum of two terms, namely, the translation term, and the intrinsic term. One useful property of this representation is that it allows the translation, rotation and intrinsic parametersof the curve be separated easily. Timing performance of the proposed methods compares favorably with the other Hough-based methods.     

Four-arc approximation to ellipses: The best in general

So far, the four-arc approximations to an ellipse E are made under the condition that the major and minor axes keep strictly unchanged. In general, however, this condition is unnecessary. Then the fitting can be further improved. Considering a representative quadrant of E, we first draw two auxiliary circular arcs tangent to E at the axes but having a gap ε at their boundary, such that the small arc S lies outside the large arc L. Meanwhile the extreme errors of S and L w.r.t. E are ε and −ε respectively. Giving the radii of S and L a decrement −ε/2 and an increment ε/2 brings them to join smoothly. Thus, reducing the overall error to minimum, an analytic solution in implicit form is derived.     

Asymptotically efficient estimators for the fittings of coupled circles and ellipses

Fitting a pair of coupled geometric objects to a number of coordinate points is a challenging and important problem in many applications including coordinate metrology, petroleum engineering and image processing. This paper derives two asymptotically efficient estimators, one for concentric circles fitting and the other for concentric ellipses fitting, based on the weighted equation error formulation and non-linear parameter transformation. The Kanatani–Cramér–Rao (KCR) lower bounds for the parameter estimates of the concentric circles and concentric ellipses under zero-mean Gaussian noise are provided to serve as the performance benchmark. Small-noise analysis shows that the proposed estimators reach the KCR lower bound performance asymptotically. The accuracy of the proposed estimators is corroborated by experiments with synthetic data and realistic images.     

基于边界曲线弧分割的多椭圆检测

不同于传统的Hough变换算法,提出一种基于边界弧分割的椭圆检测方法。首先将边界从交点处分割成弧段,将得到弧段划分为长弧和短弧两组并按长度降序排序,然后从两组中找出属于某个椭圆的若干弧段,利用最小二乘法拟合得到候选椭圆并验证是否为真正椭圆。实验表明该算法能快速检测出图中椭圆,运行时间远小于采用随机Hough变换算法,在具有噪声、椭圆残缺的情况下仍能有较好的检测结果。     

Robust detection and ordering of ellipses on a calibration pattern

The aim of this work is to accurately estimate from an image the parameters of some ellipses and their relative positions with respect to a given pattern. The process is characterized because it is fully automated and is robust against image noise and occlusions. We have built a calibrator pattern with two planes each containing several ordered circles in known 3D positions. Our method is able to estimate the position of every ellipse and to put them into correspondence with the original calibrator circles. The text was submitted by the authors in English. Luis álvarez received an MS in applied mathematics in 1985 and a PhD in mathematics in 1988, both from CompIntense University (Madrid, Spain). Between 1991 and 1992, he worked as a postdoctoral researcher at CEREMADE, Université Paris IX—Dauphine (France). Currently, he is with the Computer Science Department of the University of Las Palmas de Gran Canaria. His research interests are computer vision and partial differential equations. He is the scientific leader of computer vision group of the University of Las Palmas named AMI. Agustín Salgado received an MS in computer science in from the University of Las Palmas de Gran Canaria (Las Palmas, Spain). Currently, he holds a grant from the Computer Science Department of the University of Las Palmas de Gran Canaria, where he is working on his doctoral thesis under the direction of Javier Sánchez. Javier Sánchez received an MS in computer science in 1997 and a PhD in computer science in 2001, both from the University of Las Palmas de Gran Canaria (Las Palmas, Spain). Between 1997 and 1998, he attended some courses of the DBA 127 “Informatique: Systemes Intelligentes” at the Université Paris IX—Dauphine (France). Currently, he is a lecturer at the Computer Science Department of the University of Las Palmas de Gran Canaria. His research interests are computer vision and partial differential equations, specially applied to stereoscopic vision and optical flow estimation.