Algorithms for projecting points onto conics. (English) Zbl 1288.65016
Summary: We study the problem of projecting 2D points onto quadratic curves (ellipses, hyperbolas, parabolas). We investigate various projection algorithms focusing on those that are mathematically proven to produce (or converge to) correct results in all cases. Our tests demonstrate that those may be still unfit for practical use due to large computational errors. We present two new algorithms that are not only theoretically proven to converge, but achieve nearly perfect accuracy.
MSC:
| 65D10 | Numerical smoothing, curve fitting |
Keywords:
least squares fitting; orthogonal projection; ellipses; conics; cubic equations; quartic equationsReferences:
| [1] | Duda, R. O.; Hart, P. E., The use of Hough transform to detect lines and curves in pictures, Commun. ACM, 15, 11-15 (1972) · Zbl 1296.94027 |
| [2] | Hastie, T.; Stuetzle, W., Principal curves, J. Amer. Statist. Assoc., 84, 502-516 (1989) · Zbl 0679.62048 |
| [3] | Dreznera, Z.; Steinerb, S.; Wesolowsky, G. O., On the circle closest to a set of points, Comput. Oper. Res., 29, 637-650 (2002) · Zbl 0994.90088 |
| [4] | Adcock, R. J., Note on the method of least squares, Analyst, 4, 183-184 (1877) · JFM 09.0154.04 |
| [5] | Kummell, C. H., Reduction of observation equations which contain more than one observed quantity, Analyst, 6, 97-105 (1879) · JFM 11.0159.02 |
| [6] | Chernov, N., (Circular and Linear Regression: Fitting Circles and Lines by Least Squares. Circular and Linear Regression: Fitting Circles and Lines by Least Squares, Chapman & Hall/CRC Monographs on Statistics and Applied Probability, vol. 117 (2010)) |
| [7] | Robinson, S. M., Fitting spheres by the method of least squares, Commun. ACM, 4, 491 (1961) · Zbl 0099.33901 |
| [8] | Thom, A., A statistical examination of the megalithic sites in Britain, J. Roy. Statist. Soc. Ser. A, 118, 275-295 (1955) |
| [9] | Albano, A., Representation of digitized contours in terms of conic arcs and straight-line segments, Comput. Graph. Image Process., 3, 23-33 (1974) |
| [10] | Biggerstaff, R. H., Three variations in dental arch form estimated by a quadratic equation, J. Dent. Res., 51, 1509 (1972) |
| [11] | Bookstein, F. L., Fitting conic sections to scattered data, Comput. Graph. Image Process., 9, 56-71 (1979) |
| [12] | Paton, K., Conic sections in chromosome analysis, Pattern Recognit., 2, 39-51 (1970) |
| [13] | Pratt, V., Direct least-squares fitting of algebraic surfaces, Comput. Graph., 21, 145-152 (1987) |
| [14] | Sampson, P. D., Fitting conic sections to very scattered data: an iterative refinement of the Bookstein algorithm, Comput. Graph. Image Process., 18, 97-108 (1982) |
| [15] | Taubin, G., Estimation of planar curves, surfaces and nonplanar space curves defined by implicit equations, with applications to edge and range image segmentation, IEEE Trans. Pattern Anal. Mach. Intell., 13, 1115-1138 (1991) |
| [16] | Ahn, S. J., (Least Squares Orthogonal Distance Fitting of Curves and Surfaces in Space. Least Squares Orthogonal Distance Fitting of Curves and Surfaces in Space, LNCS, vol. 3151 (2004), Springer: Springer Berlin) · Zbl 1067.65019 |
| [17] | Gander, W.; Golub, G. H.; Strebel, R., Least squares fitting of circles and ellipses, BIT, 34, 558-578 (1994) · Zbl 0817.65008 |
| [18] | Zhang, Z., Parameter estimation techniques: a tutorial with application to conic fitting, Int. J. Image Vis. Comput., 15, 59-76 (1997) |
| [19] | Kanatani, K.; Rangarajan, P., Hyper least squares fitting of circles and ellipses, Comput. Statist. Data Anal., 55, 2197-2208 (2011) · Zbl 1328.62399 |
| [20] | Ahn, S. J.; Rauh, W.; Warnecke, H. J., Least-squares orthogonal distances fitting of circle, sphere, ellipse, hyperbola, and parabola, Pattern Recognit., 34, 2283-2303 (2001) · Zbl 0991.68127 |
| [21] | Ahn, S. J.; Rauh, W.; Recknagel, M., Least squares orthogonal distances fitting of implicit curves and surfaces, (LNCS, vol. 2191 (2001)), 398-405 · Zbl 1038.68613 |
| [22] | Ahn, S. J.; Rauh, W.; Cho, H. S., Orthogonal distances fitting of implicit curves and surfaces, IEEE Trans. Pattern Anal. Mach. Intell., 24, 620-638 (2002) |
| [23] | Chernov, N.; Ma, H., Least squares fitting of quadratic curves and surfaces, (Yoshida, S. R., Computer Vision (2011), Nova Science Publishers), 285-302 |
| [24] | Aigner, M.; Jüttler, B., Gauss-Newton type techniques for robustly fitting implicitly defined curves and surfaces to unorganized data points, (Shape Modeling International (2008)), 121-130 |
| [26] | Wijewickrema, S.; Esson, C.; Papliński, A., Orthogonal distance least squares fitting: a novel approach, (Proc. CVICGTA (Lisboa, Portugal, Feb. 5-8, 2009). Proc. CVICGTA (Lisboa, Portugal, Feb. 5-8, 2009), Commun. Comp. Inf. Sci., vol. 68 (2010)), 255-268 · Zbl 1205.68472 |
| [27] | Chernov, N.; Huang, Q.; Ma, H., Does the best fitting curve always exist?, ISRN Probab. Statist. (2012), Article ID 895178 · Zbl 1398.62178 |
| [28] | 3D Game Engine Design (2007), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers San Francisco, CA, See also Internet article Distance from a point to an ellipse in 2D, Geometric Tools, LLC. www.geometrictools.com |
| [29] | Aigner, M.; Jüttler, B., Robust computation of foot points on implicitly defined curves, (Daehlen, M.; etal., Mathematical Methods for Curves and Surfaces, Tromso 2004 (2005), Nashboro Press), 1-10 · Zbl 1080.65523 |
| [30] | Trefethen, L.; Bau, D., Numerical Linear Algebra (1997), SIAM · Zbl 0874.65013 |
| [31] | Strong, T., Elementary and Higher Algebra (1859), Pratt and Oakley |
| [32] | Christianson, B., Solving Quartics using Palindromes, Math. Gaz., 75, 327-328 (1991) |
| [33] | Turnbull, H. W., Theory of Equations (1947), Oliver and Boyd: Oliver and Boyd London · Zbl 0036.00401 |
| [34] | Neumark, S., Solution of Cubic and Quartic Equations (1965), Pergamon Press: Pergamon Press Oxford · Zbl 0125.35902 |
| [37] | Shmakov, S., A universal method of solving quartic equations, Int. J. Pure Appl. Math., 71, 251-259 (2011) · Zbl 1247.12004 |
| [38] | Semple, J. G.; Kneebone, G. T., Algebraic Projective Geometry (1956), Oxford U. Press: Oxford U. Press Oxford · Zbl 0932.51008 |
| [40] | Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P., Numerical Recipes. The Art of Scientific Computing (2007), Cambridge University Press, Earlier editions available free on-line · Zbl 1132.65001 |
| [42] | Nievergelt, Y., Fitting conics of specific types to data, Linear Algebra Appl., 378, 1-30 (2004) · Zbl 1053.65010 |
| [43] | Moré, J. J., Generalizations of the trust region problem, Optim. Methods Softw., 2, 189-209 (1993) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
