Abstract
We consider a new problem of recognition of digital primitives – digital hyperplanes or level layers – arising in a new practical application of surface segmentation. Such problems are usually driven by a maximal thickness criterion which is not satisfactory for applications as soon as the dimension of the primitives becomes greater than 1. It is a good reason to introduce a more flexible approach where the set to recognize (whose points are called inliers) is given along with two other sets of outliers that should each remain on his own side of the primitive. We reduce this problem of recognition with outliers to the separation of three point clouds of ℝ d by two parallel hyperplanes and we provide a geometrical algorithm derived from the well-known GJK algorithm to solve the problem.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Brimkov, V.E., Coeurjolly, D., Klette, R.: Digital planarity – A review. Discrete Applied Mathematics 155(4), 468–495 (2007)
Brimkov, V.E., Dantchev, S.S.: Digital hyperplane recognition in arbitrary fixed dimension within an algebraic computation model. Image and Vision Computing 25(10), 1631–1643 (2007)
Buzer, L.: An incremental linear time algorithm for digital line and plane recognition using a linear incremental feasibility problem. In: Braquelaire, A., Lachaud, J.-O., Vialard, A. (eds.) DGCI 2002. LNCS, vol. 2301, pp. 372–381. Springer, Heidelberg (2002)
Charrier, E., Buzer, L.: An efficient and quasi linear worst-case time algorithm for digital plane recognition. In: Coeurjolly, D., Sivignon, I., Tougne, L., Dupont, F. (eds.) DGCI 2008. LNCS, vol. 4992, pp. 346–357. Springer, Heidelberg (2008)
Coeurjolly, D., Gerard, Y., Reveillès, J.P., Tougne, L.: An elementary algorithm for digital arc segmentation. Discrete Applied Mathematics 139(1-3), 31–50 (2004)
Debled-Rennesson, I., Reveillès, J.P.: A linear algorithm for segmentation of digital curves. International Journal of Pattern Recognition and Artificial Intelligence 9(4), 635–662 (1995)
Gerard, Y., Debled-Rennesson, I., Zimmermann, P.: An elementary digital plane recognition algorithm. Discrete Applied Mathematics 151, 169–183 (2005)
Gérard, Y., Provot, L., Feschet, F.: Introduction to digital level layers. In: Domenjoud, E. (ed.) DGCI 2011. LNCS, vol. 6607, pp. 83–94. Springer, Heidelberg (2011)
Gilbert, E.G., Johnson, D.W., Keerthi, S.S.: A fast procedure for computing the distance between complex objects in three-dimensional space. IEEE Journal of Robotics and Automation 4, 193–203 (1988)
Megiddo, N.: Linear programming in linear time when the dimension is fixed. Journal of the ACM 31(1), 114–127 (1984)
Provot, L., Debled-Rennesson, I.: 3D noisy discrete objects: Segmentation and application to smoothing. Pattern Recognition 42(8), 1626–1636 (2009)
Sivignon, I., Coeurjolly, D.: From digital plane segmentation to polyhedral representation. In: Asano, T., Klette, R., Ronse, C. (eds.) Geometry, Morphology, and Computational Imaging. LNCS, vol. 2616, pp. 356–367. Springer, Heidelberg (2003)
Zrour, R., Kenmochi, Y., Talbot, H., Buzer, L., Haman, Y., Shimizu, I., Sugimoto, A.: Optimal consensus set for digital line and plane fitting. International Journal of Imaging Systems and Technology (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Provot, L., Gerard, Y. (2011). Recognition of Digital Hyperplanes and Level Layers with Forbidden Points. In: Aggarwal, J.K., Barneva, R.P., Brimkov, V.E., Koroutchev, K.N., Korutcheva, E.R. (eds) Combinatorial Image Analysis. IWCIA 2011. Lecture Notes in Computer Science, vol 6636. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21073-0_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-21073-0_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21072-3
Online ISBN: 978-3-642-21073-0
eBook Packages: Computer ScienceComputer Science (R0)