Efficient boundary extraction from orthogonal pseudo-polytopes: an approach based on the \(n\)D-EVM. (English) Zbl 1221.68276

Pérez-Aguila, Ricardo

J. Appl. Math. 2011, Article ID 937263, 29 p. (2011).

Summary: This work contributes with two algorithms for performing, in an efficient way, connected components labeling and boundary extraction from orthogonal pseudo-polytopes. The proposals are specified in terms of the extreme vertices model in the \(n\)-dimensional space (\(n\)D-EVM). An overview of the model is presented, considering aspects such as its fundamentals and basic algorithms. The temporal efficiency of the two proposed algorithms is sustained in an empirical way and by taking into account both lower dimensional cases (2D and 3D) and higher-dimensional cases (4D and 5D).

MSC:

68U05

Computer graphics; computational geometry (digital and algorithmic aspects)

Keywords:

extreme vertices model in the \(n\)-dimensional space (\(n\)D-EVM); connected components labeling; boundary extraction

References:

[1]	A. Aguilera, Orthogonal polyhedra: study and application, Ph.D. thesis, Universitat Politècnica de Catalunya, 1998.
[2]	A. Aguilera and D. Ayala, “Orthogonal polyhedra as geometric bounds in constructive solid geometry,” in Proceedings of the 4th ACM Siggraph Symposium on Solid Modeling and Applications (SM ’97), pp. 56-67, ACM, Atlanta, Ga, USA, 1997.
[3]	R. Pérez-Aguila, Orthogonal polytopes: study and application, Ph.D. thesis, Universidad de las Américas-Puebla (UDLAP), 2006.
[4]	R. Pérez-Aguila, “Modeling and manipulating 3D datasets through the extreme vertices model in the n-dimensional space (nD-EVM),” Research in Computer Science, vol. 31, pp. 15-24, 2007.
[5]	R. Pérez-Aguila, “Computing the discrete compactness of orthogonal pseudo-polytopes via their n-EVM representation,” Mathematical Problems in Engineering, vol. 2010, Article ID 598910, 28 pages, 2010. · Zbl 1202.68453
[6]	J. Rodríguez and D. Ayala, “Erosion and dilation on 2D and 3D digital images: a new size-independent approach,” Vision Modeling and Visualization, pp. 143-150, 2001.
[7]	J. Rodríguez and D. Ayala, “Fast neighborhood operations for images and volume data sets,” Computers and Graphics, vol. 27, no. 6, pp. 931-942, 2003.
[8]	A. Rosenfeld and J. L. Pfaltz, “Sequential operations in digital picture processing,” Journal of the ACM, vol. 13, no. 4, pp. 471-494, 1966. · Zbl 0143.41803
[9]	S. Marchand-Maillet and Y. M. Sharaiha, Binary Digital Image Processing, Academic Press Inc., San Diego, Calif, USA, 2000. · Zbl 0998.94500
[10]	H. Samet and M. Tamminen, “efficient component labeling of images of arbitrary dimension represented by linear bintrees,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 10, no. 4, pp. 579-586, 1988. · Zbl 05111138
[11]	K. Sandfort and J. Ohser, “Labeling of n-dimensional images with choosable adjacency of the pixels,” Image Analysis & Stereology, vol. 28, no. 1, pp. 45-61, 2009. · Zbl 1356.94024
[12]	K. Wu, E. Otoo, and A. Shoshani, “Optimizing connected component labeling algorithms,” in Progress in Biomedical Optics and Imaging, vol. 5747 of Proceedings of SPIE, no. 3, pp. 1965-1976, 2005.
[13]	K. Suzuki, I. Horiba, and N. Sugie, “Linear-time connected-component labeling based on sequential local operations,” Computer Vision and Image Understanding, vol. 89, no. 1, pp. 1-23, 2003. · Zbl 1038.68107
[14]	H. Samet, “Connected component labeling using quadtrees,” Journal of the Association for Computing Machinery, vol. 28, no. 3, pp. 487-501, 1981. · Zbl 0462.68070
[15]	A. A. Requicha, “Representations for rigid solids: theory, methods, and systems,” Computing Surveys, vol. 12, no. 4, pp. 437-464, 1980.
[16]	H. Hansen and N. Christensen, “A model for n-dimensional boundary topology,” in Proceedings of the 2th Symposium on Solid Modeling and Applications, pp. 65-73, Montreal, Canada, 1993.
[17]	L. K. Putnam and P. A. Subrahmanyam, “Boolean operations on n-dimensional objects,” IEEE Computer Graphics and Applications, vol. 6, no. 6, pp. 43-51, 1986.
[18]	M. Spivak, Calculus on Manifolds. A Modern Approach to Classical Theorems of Advanced Calculus, W. A. Benjamin, Inc., New York, NY, USA, 1965. · Zbl 0141.05403
[19]	G. McCarty and G. S. Yound, Topology, Dover Publications Inc., New York, NY, USA, 2nd edition, 1988. · Zbl 0724.03034
[20]	G. L. Naber, Topological Methods in Euclidean Spaces, Dover Publications Inc., Mineola, NY, USA, 2000. · Zbl 0985.53019
[21]	A. Kolcun, “Visibility criterion for planar faces in 4D,” in Proceedings of Spring Conference on Computer Graphics (SCCG ’04), pp. 216-219, Budmerice, Slovakia, 2004.
[22]	T. Takala, “A taxonomy on geometric and topological models,” Computer Graphics and Mathematics, pp. 146-171, 1992.
[23]	R. Pérez-Aguila, “Representing and visualizing vectorized videos through the extreme vertices model in the n-dimensional Sspace (nD-EVM),” Journal Research in Computer Science, vol. 29, pp. 65-80, 2007.