Abstract
Quadrics are a compact mathematical formulation for a range of primitive surfaces. A problem arises when there are not enough data points to compute the model but knowledge of the shape is available. This paper presents a method for fitting a quadric with a Bayesian prior. We use a matrix normal prior in order to favour ellipsoids when fitting to ambiguous data. The results show the algorithm copes well when there are few points in the point cloud, competing with contemporary techniques in the area.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Taubin, G. Estimation of planar curves, surfaces, and nonplanar space curves defined by implicit equations with applications to edge and range image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 13, No. 11, 1115–1138, 1991.
Ahn, S. J.; Rauh, W.; Cho, H. S.; Warnecke, H.-J. Orthogonal distance fitting of implicit curves and surfaces. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 24, No. 5, 620–638, 2002.
Andrews, J.; Séquin, C. H. Type-constrained direct fitting of quadric surfaces. Computer-Aided Design and Applications Vol. 11, No. 1, 107–119, 2014.
Atieg, A.; Watson, G. A. A class of methods for fitting a curve or surface to data by minimizing the sum of squares of orthogonal distances. Journal of Computational and Applied Mathematics Vol. 158, No. 2, 277–296, 2003.
Gander, W.; Golub, G. H.; Strebel, R. Leastsquares fitting of circles and ellipses. BIT Numerical Mathematics Vol. 34, No. 4, 558–578, 1994.
Lukács, G.; Martin, R.; Marshall, D. Faithful leastsquares fitting of spheres, cylinders, cones and tori for reliable segmentation. In: Lecture Notes in Computer Science, Vol. 1406. Burkhardt, H.; Neumann, B. Eds. Springer Berlin Heidelberg, 671–686, 1998.
Petitjean, S. A survey of methods for recovering quadrics in triangle meshes. ACM Computing Surveys (CSUR) Vol. 34, No. 2, 211–262, 2002.
Ruiz, O.; Arroyave, S.; Acosta, D. Fitting of analytic surfaces to noisy point clouds. American Journal of Computational Mathematics Vol. 3, No. 1A, 18–26, 2013.
Rouhani, M.; Sappa, A. D. Implicit polynomial representation through a fast fitting error estimation. IEEE Transactions on Image Processing Vol. 21, No. 4, 2089–2098, 2012.
Pratt, V. Direct least-squares fitting of algebraic surfaces. ACM SIGGRAPH Computer Graphics Vol. 21, No. 4, 145–152, 1987.
Fitzgibbon, A.; Pilu, M.; Fisher, R. B. Direct least square fitting of ellipses. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 21, No. 5, 476–480, 1999.
Li, Q.; Griffiths, J. G. Least squares ellipsoid specific fitting. In: Proceedings of Geometric Modeling and Processing, 335–340, 2004.
Halir, R.; Flusser, J. Numerically stable direct least squares fitting of ellipses. In: Proceedings of the 6th International Conference in Central Europe on Computer Graphics and Visualization, Vol. 98, 125–132, 1998.
Dai, M.; Newman, T. S.; Cao, C. Least-squares-based fitting of paraboloids. Pattern Recognition Vol. 40, No. 2, 504–515, 2007.
Subrahmonia, J.; Cooper, D. B.; Keren, D. Practical reliable Bayesian recognition of 2D and 3D objects using implicit polynomials and algebraic invariants. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 18, No. 5, 505–519, 1996.
Cohen-Steiner, D.; Alliez, P.; Desbrun, M. Variational shape approximation. ACM Transactions on Graphics Vol. 23, No. 3, 905–914, 2004.
Wu, J.; Kobbelt, L. Structure recovery via hybrid variational surface approximation. Computer Graphics Forum Vol. 24, No. 3, 277–284, 2005.
Yan, D.-M.; Liu, Y.; Wang, W. Quadric surface extraction by variational shape approximation. In: Lecture Notes in Computer Science, Vol. 4077. Kim, M.-S.; Shimada, K. Eds. Springer Berlin Heidelberg, 73–86, 2006.
Schnabel, R.; Wahl, R.; Klein, R. Efficient RANSAC for point-cloud shape detection. Computer Graphics Forum Vol. 26, No. 2, 214–226, 2007.
Li, Y.; Wu, X.; Chrysathou, Y.; Sharf, A.; Cohen-Or, D.; Mitra, N. J. GlobFit: Consistently fitting primitives by discovering global relations. ACM Transactions on Graphics Vol. 30, No. 4, Article No. 52, 2011.
Ohtake, Y.; Belyaev, A.; Alexa, M.; Turk, G.; Seidel, H.-P. Multi-level partition of unity implicits. In: Proceedings of ACM SIGGRAPH 2005 Courses, Article No. 173, 2005.
Hamann, B. Curvature approximation for triangulated surfaces. In: Computing Supplementum, Vol. 8. Farin, G.; Noltemeier, H.; Hagen, H.; Kndel, W. Eds. Springer Vienna, 139–153, 1993.
Vona, M.; Kanoulas, D. Curved surface contact patches with quantified uncertainty. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, 1439–1446, 2011.
Powell, M. W.; Bowyer, K. W.; Jiang, X.; Bunke, H. Comparing curved-surface range image segmenters. In: Proceedings of the 6th International Conference on Computer Vision, 286–291, 1998.
Petersen, K. B.; Pedersen, M. S. The Matrix Cookbook. Technical University of Denmark. Version: November 15, 2012. Available at https://www.math.uwaterloo. ca/vhwolkowi/matrixcookbook. pdf.
Lott, G. K. Direct orthogonal distance to quadratic surfaces in 3D. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 36, No. 9, 1888–1892, 2014.
Eberly, D. Distance from a point to an ellipse, an ellipsoid, or a hyperellipsoid. Geometric Tools, LLC, 2011. Available at http://www.geometrictools.com/ Documentation/DistancePointEllipseEllipsoid.pdf.
Kwatra, V.; Han, M. Fast covariance computation and dimensionality reduction for sub-window features in images. In: Lecture Notes in Computer Science, Vol. 6312. Daniilidis, K.; Maragos, P.; Paragios, N. Eds. Springer Berlin Heidelberg, 156–169, 2010.
Author information
Authors and Affiliations
Corresponding author
Additional information
Daniel Beale is a post-doctoral research officer at the University of Bath. He obtained his Ph.D. degree in computer science and master degree of mathematics (M.Math.) from the University of Bath. He has worked in industrial positions as a software and systems engineer. His interests are in the application of mathematics, statistics, and probability theory to problems in computing, particularly in the area of computer vision.
Yong-Liang Yang is a lecturer (assistant professor) in the Department of Computer Science at the University of Bath. He received his Ph.D. degree and master degree in computer science from Tsinghua University. His research interests include geometric modelling, computational design, and computer graphics in general.
Neill Campbell is a lecturer in computer vision, graphics, and machine learning in the Department of Computer Science at the University of Bath. Previously he was a research associate at University College London (where he is an honorary lecturer) working with Jan Kautz and Simon Prince. He completed his M.Eng. and Ph.D. degrees in the Department of Engineering at the University of Cambridge under the supervision of Roberto Cipolla with George Vogiatzis and Carlos Hern`andez at Toshiba Research. His main area of interest is learning models of shape and appearance in 2D and 3D.
Darren Cosker is a Royal Society Industrial Research Fellow at Double Negative Visual Effects, London, and a reader (associate professor) at the University of Bath. He is the director of the Centre for the Analysis of Motion, Entertainment Research and Applications (CAMERA), starting from September 2015. Previously, he held a Royal Academy of Engineering Research Fellowship, also at the University of Bath. His interests are in the convergence of computer vision, graphics, and psychology, with applications in movies and video games.
Peter Hall is a professor of visual computing at the University of Bath. His research interests focus around the use of computer vision for computer graphics applications. He is known for automatically processing real photographs and video into art, especially abstract styles such as Cubism, Futurism, etc. More recently he has published papers on classification and detection of objects regardless of how they are depicted such as photos, drawings, paintings, etc. He is also interested in using computer vision methods to acquire 3D dynamic models of complex natural phenomena such as trees, water, and fire for use in computer games, TV broadcast, and film special effects.
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (https://creativecommons.org/licenses/by/4.0), which permits use, duplication, adaptation, distribution, and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Beale, D., Yang, YL., Campbell, N. et al. Fitting quadrics with a Bayesian prior. Comp. Visual Media 2, 107–117 (2016). https://doi.org/10.1007/s41095-016-0041-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s41095-016-0041-9