Abstract
Efficient direct solutions for the determination of a cylinder from points are presented. The solutions range from the well known direct solution of a quadric to the minimal solution of a cylinder with five points. In contrast to the approach of G. Roth and M. D. Levine (1990), who used polynomial bases for representing the geometric entities, we use algebraic constraints on the quadric representing the cylinder. The solutions for six to eight points directly determine all the cylinder parameters in one step: (1) The eight-point-solution, similar to the estimation of the fundamental matrix, requires to solve for the roots of a 3rd-order-polynomial. (2) The seven-point-solution, similar to the six-point-solution for the relative orientation by J. Philip (1996), yields a linear equation system. (3) The six-point-solution, similar to the five-point-solution for the relative orientation by D. Nister (2003), yields a ten-by-ten eigenvalue problem. The new minimal five-point-solution first determines the direction and then the position and the radius of the cylinder. The search for the zeros of the resulting 6th order polynomials is efficiently realized using 2D-Bernstein polynomials. Also direct solutions for the special cases with the axes of the cylinder parallel to a coordinate plane or axis are given. The method is used to find cylinders in range data of an industrial site.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bookstein, F.L.: Fitting conic sections to scattered data. CGIP 9(1), 56–71 (1979)
Chaperon, T., Goulette, F.: Extracting cylinders in full 3d data using a random sampling method and the gaussian image. In: Proceedings of the Vision Modeling and Visualization Conference, pp. 35–42 (2001)
Faugeras, O.: Three-Dimensional Computer Vision: A Geometric Viewpoint. MIT Press, Cambridge (1993)
Fischler, M.A., Bolles, R.C.: Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM 24(6), 381–395 (1981)
Fischler, M.A., Bolles, R.C.: A RANSAC-based approach to model fitting and its application to finding cylinders in range data. In: IJCAI 1981, pp. 637–643 (1981)
Garloff, J., Smith, A.P.: Solution of systems of polynomial equations by using bernstein expansion. In: Alefeld, G., Rump, S., Rohn, J., Yamamoto, T. (eds.) Symbolic Algebraic Methods and Verification Methods, Springer, Heidelberg (2001)
Hartley, R., Zisserman, A.: Multiple View Geometry in Computer Vision. Cambridge University Press, Cambridge (2000)
Hoppe, H., DeRose, T., Duchamp, T., Halstead, M., Jin, H., McDonald, J., Schweitzer, J., Stuetzle, W.: Piecewise smooth surface reconstruction. In: SIGGRAPH 1994: Proceedings of the 21st annual conference on Computer graphics and interactive techniques, pp. 295–302. ACM Press, New York (1994)
Martin, R., Shou, H., Voiculescu, I., Bowyer, A., Wang, G.: Comparison of interval methods for plotting algebraic curves. Comput. Aided Geom. Des. 19(7), 553–587 (2002)
Nistér, D.: An efficient solution to the five-point relative pose problem. IEEE Trans. Pattern Anal. Mach. Intell. 26(6), 756–777 (2004)
Peternell, M., Pottmann, H., Steiner, T.: Hough transform and Laguerre geometry for the recognition and reconstruction of special 3D shapes. Technical Report 100, Institute of Geometry (April 2003)
Petitjean, S.: A survey of methods for recovering quadrics in triangle meshes. ACM Comput. Surv. 34(2), 211–262 (2002)
Philip, J.: A non-iterative algorithm for determining all essential matrices corresponding to five point pairs. Photogrammetric Record 15(88), 589–599 (1996)
Roth, G., Levine, M.D.: Segmentation of geometric signals using robust fitting. In: Int. Conference on Pattern Recognition, pp. 826–831 (1990)
Stewenius, H., Engels, C., Nister, D.: Recent developments on direct relative orientation. ISPRS Journal (to appear, 2006)
Tang, C.K., Medioni, G.: Curvature-augmented tensor voting for shape inference from noisy 3d data. PAMI 24(6), 858–864 (2002)
Vosselman, G., Gorte, B.G.H., Sithole, G., Rabbani, T.: Recognising structure in laser scanner point clouds. In: International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, vol. 46, pp. 33–38 (2004)
Werghi, N., Fisher, R.B., Robertson, C., Ashbrook, A.P.: Faithful recovering of quadric surfaces from 3d range data. In: Second International Conference on 3-D Imaging and Modeling3DIM99, pp. 280–289 (1999)
Winkelbach, S., Westphal, R., Goesling, T.: Pose Estimation of Cylindrical Fragments for Semi-automatic Bone Fracture Reduction. In: Michaelis, B., Krell, G. (eds.) DAGM 2003. LNCS, vol. 2781, pp. 566–573. Springer, Heidelberg (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Beder, C., Förstner, W. (2006). Direct Solutions for Computing Cylinders from Minimal Sets of 3D Points. In: Leonardis, A., Bischof, H., Pinz, A. (eds) Computer Vision – ECCV 2006. ECCV 2006. Lecture Notes in Computer Science, vol 3951. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11744023_11
Download citation
DOI: https://doi.org/10.1007/11744023_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33832-1
Online ISBN: 978-3-540-33833-8
eBook Packages: Computer ScienceComputer Science (R0)