Abstract
There exist a lot of algorithms for 2D contour reconstruction from sampling points which guarantee a correct result if certain sampling criteria are fulfilled. Nevertheless nearly none of these algorithms can deal with non-manifold boundaries of multiple regions. We discuss, which problems occur in this case and present a boundary reconstruction algorithm, which can deal with partitions of multiple regions, and non-smooth boundaries (e.g. corners or edges). In comparison to well-known contour reconstruction algorithms, our method requires a lower sampling density and the sampling points can be noisy.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Amenta, N., Bern, M., Eppstein, D.: The crust and the β-skeleton: Combinatorial curve reconstruction. Graph. Models and Image Proc. 60(2), 125–135 (1998)
Attali, D.: r-Regular shape reconstruction from unorganized points. In: Proceedings of the 13th annual ACM Symposium on Comput. Geom., pp. 248–253 (1997)
Bernardini, F., Bajaj, C.L.: Sampling and reconstructing manifolds using alpha-shapes. In: Proc. 9th Canad. Conf. Comput. Geom. (1997)
Chazal, F., Lieutier, A.: Weak feature size and persistent homology: computing homology of solids in Rn from noisy data samples. In: Proc. of the 21st annual Symposium on Computational Geometry, pp. 255–262 (2005)
Dey, T.K., Kumar, P.: A simple provable algorithm for curve reconstruction. In: Proceedings of the 10th annual ACM-SIAM Symposium on Discr. Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, pp. 893–894 (1999)
Dey, T.K., Mehlhorn, K., Ramos, E.A.: Curve reconstruction: Connecting dots with good reason. In: Proceedings of the 15th annual symposium on Computational geometry, pp. 197–206. ACM, New York (1999)
Federer, H.: Curvature measures. Transactions of the American Mathematical Society 93, 418–491 (1959)
Gabriel, K.R., Sokal, R.R.: A new statistical approach to geographic variation analysis. Systematic Zoology, 259–278 (1969)
Mukhopadhyay, A., Das, A.: An RNG-based heuristic for curve reconstruction. In: Voronoi Diagrams in Science and Engineering, 3rd International Symposium ISVD 2006, pp. 246–251 (2006)
Roerdink, J.B.T.M., Meijster, A.: The Watershed Transform: Definitions, Algorithms and Parallelization Strategies. Fundam. Inform. 41(1-2), 187–228 (2000)
Stelldinger, P., Köthe, U., Meine, H.: Topologically Correct Image Segmentation Using Alpha Shapes. In: Kuba, A., Nyúl, L.G., Palágyi, K. (eds.) DGCI 2006. LNCS, vol. 4245, pp. 542–554. Springer, Heidelberg (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Stelldinger, P., Tcherniavski, L. (2009). Contour Reconstruction for Multiple 2D Regions Based on Adaptive Boundary Samples. In: Wiederhold, P., Barneva, R.P. (eds) Combinatorial Image Analysis. IWCIA 2009. Lecture Notes in Computer Science, vol 5852. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-10210-3_21
Download citation
DOI: https://doi.org/10.1007/978-3-642-10210-3_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-10208-0
Online ISBN: 978-3-642-10210-3
eBook Packages: Computer ScienceComputer Science (R0)