Describing shapes by geometrical-topological properties of real functions

Abstract

Differential topology, and specifically Morse theory, provide a suitable setting for formalizing and solving several problems related to shape analysis. The fundamental idea behind Morse theory is that of combining the topological exploration of a shape with quantitative measurement of geometrical properties provided by a real function defined on the shape. The added value of approaches based on Morse theory is in the possibility of adopting different functions as shape descriptors according to the properties and invariants that one wishes to analyze. In this sense, Morse theory allows one to construct a general framework for shape characterization, parametrized with respect to the mapping function used, and possibly the space associated with the shape. The mapping function plays the role of a lens through which we look at the properties of the shape, and different functions provide different insights.

In the last decade, an increasing number of methods that are rooted in Morse theory and make use of properties of real-valued functions for describing shapes have been proposed in the literature. The methods proposed range from approaches which use the configuration of contours for encoding topographic surfaces to more recent work on size theory and persistent homology. All these have been developed over the years with a specific target domain and it is not trivial to systematize this work and understand the links, similarities, and differences among the different methods. Moreover, different terms have been used to denote the same mathematical constructs, which often overwhelm the understanding of the underlying common framework.

The aim of this survey is to provide a clear vision of what has been developed so far, focusing on methods that make use of theoretical frameworks that are developed for classes of real functions rather than for a single function, even if they are applied in a restricted manner. The term geometrical-topological used in the title is meant to underline that both levels of information content are relevant for the applications of shape descriptions: geometrical, or metrical, properties and attributes are crucial for characterizing specific instances of features, while topological properties are necessary to abstract and classify shapes according to invariant aspects of their geometry. The approaches surveyed will be discussed in detail, with respect to theory, computation, and application. Several properties of the shape descriptors will be analyzed and compared. We believe this is a crucial step to exploit fully the potential of such approaches in many applications, as well as to identify important areas of future research.

References

1. Ackermann, W. 1928. Zum hilbertschen aufbau der reellen zahlen. Math. Ann. 99, 118--133.
2. Agarwal, P. K., Edelsbrunner, H., Harer, J., and Wang, Y. 2004. Extreme elevation on a 2-manifold. In SCG '04: Proceedings of the 20th Annual Symposium on Computational Geometry. ACM Press, New York, NY, 357--265.
3. Allili, M. and Corriveau, D. 2007. Topological analysis of shapes using Morse theory. Comput. Vis. Image Understand. 105, 3, 188--199.
4. Allili, M., Corriveau, D., and Ziou, D. 2004. Morse homology descriptor for shape characterization. In ICPR2004: Proceedings of the 17th International Conference on Pattern Recognition. Vol. 4. 27--30.
5. Allili, M., Mischaikow, K., and Tannenbaum, A. 2001. Cubical homology and the topological classification of 2D and 3D imagery. In ICIP 2001: Proceedings of the IEEE International Conference on Image Processing. Vol. 2. 173--176.
6. Allili, M. and Ziou, D. 2003. Computational homology approach for topology descriptors and shape representation. In ICISP'2003: Proceedings of the International Conference on Image and Signal Processing. Vol. 2. 508--516.
7. Attene, M., Biasotti, S., and Spagnuolo, M. 2001. Re-meshing techniques for topological analysis. In SMI '01: Proceedings of the International Conference on Shape Modeling and Applications 2001. IEEE Computer Society Press, Los Alamitos, CA, 142--152.
8. Attene, M., Biasotti, S., and Spagnuolo, M. 2003. Shape understanding by contour-driven retiling. Vis. Comput. 19, 2-3, 127--138.
9. Aurenhammer, F. 1991. Voronoi diagrams—a survey of a fundamental geometric data structure. ACM Comput. Surv. 23, 3, 345--405.
10. Axen, U. 1999. Computing Morse functions on triangulated manifolds. In SODA '99: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM Press, New York, NY, 850--851.
11. Axen, U. and Edelsbrunner, H. 1998. Auditory Morse analysis of triangulated manifolds. In Mathematical Visualization, H. C. Hege and K. Polthier, Eds. Springer-Verlag, Berlin, Germany, 223--236.
12. Bajaj, C. L., Gillette, A., and Goswami, S. 2007. Topology based selection and curation of level sets. In TopoInVis 2007: Proceedings of the Workshop on Topology-based Methods in Visualization 2007.
13. Bajaj, C. L. and Goswami, S. 2006. Automatic fold and structural motif elucidation from 3D EM maps of macromolecules. In ICVGIP 2006: Proceedings of the 5th Indian Conference on Computer Vision, Graphics and Image Processing. 264--275.
14. Bajaj, C. L., Pascucci, V., and Schikore, D. R. 1997. The contour spectrum. In VIS '97: Proceedings of the IEEE Visualization 1997. IEEE Computer Society Press, Los Alamitos, CA, 167--173.
15. Bajaj, C. L., Pascucci, V., and Schikore, D. R. 1998. Visualization of scalar topology for structural enhancement. In VIS '98: Proceedings of the IEEE Visualization Conference 1998. IEEE Computer Society Press, Los Alamitos, CA, 51--58.
16. Bajaj, C. L. and Schikore, D. R. 1998. Topology preserving data simplification with error bounds. Comput. Graph. 22, 1, 3--12.
17. Banchoff, T. F. 1967. Critical points and curvature for embedded polyhedra. J. Different. Geom. 1, 245--256.
18. Banchoff, T. F. 1970. Critical points and curvature for embedded polyhedral surfaces. Amer. Math. Month. 77, 475--485.
19. Bangham, J. A., Hidalgo, J. R., and Harvey, R. 1998b. Robust morphological scale-space trees. In Proceedings of the Noblesse Workshop on Non-Linear Model Based Image Analysis (Glasgow, U.K.), S. Marshall, N. Harvey, and D. Shah, Eds. 133--139.
20. Bangham, J. A., Hidalgo, J. R., Harvey, R., and Cawley, G. 1998a. The segmentation of images via scale-space trees. In Proceedings of the 9th British Machine Vision Conference. 33--43.
21. Baumgart, B. G. 1975. A polyhedron representation for computer vision. In Proceedings of the AFIPS National Computer Conference. Vol. 44. 589--596.
22. Berglund, N. and Szymczak, A. 2004. Making contour trees subdomain-aware. In Abstracts of the 16th Canadian Conference on Computational Geometry. 188--191.
23. Bern, M. W., Eppstein, D., Agarwal, P. K., Amenta, N., Chew, L. P., Dey, T. K., Dobkin, D. P., Edelsbrunner, H., Grimm, C., Guibas, L. J., Harer, J., Hass, J., Hicks, A., Johnson, C. K., Lerman, G., Letscher, D., Plassmann, P. E., Sedgwick, E., Snoeyink, J., Weeks, J., Yap, C.-K., and Zorin, D. 1999. Emerging challenges in computational topology. ArXiv Computer Science e-prints, cs/9909001.
24. Berretti, S., Del Bimbo, A., and Pala, P. 2006. Partitioning of 3D meshes using Reeb graphs. In ICPR '06: Proceedings of the 18th International Conference on Pattern Recognition. IEEE Computer Society Press, Los Alamitos, CA, 19--22.
25. Besl, P. and Jain, R. 1985. Three-dimensional object recognition. ACM Comput. Surv. 17, 1, 75--145.
26. Bespalov, D., Regli, W., and Shokoufandeh, A. 2003. Reeb graph based shape retrieval for CAD. In DETC'03: Proceedings of the ASME Design Engineering Technical Conferences 2003. ASME, New York, NY.
27. Beucher, S. and Lantuejoul, C. 1979. Use of watersheds in contour detection. In Proceedings of the International Workshop on Image Processing: Real-Time Edge and Motion Detection/Estimation (Rennes, France).
28. Biasotti, S. 2004a. Computational topology methods for shape modelling applications. Ph.D. dissertation. Università degli Studi di Genova, Genoa, Italy.
29. Biasotti, S. 2004b. Reeb graph representation of surfaces with boundary. In SMI '04: Proceedings of the International Conference on Shape Modeling and Applications 2004. IEEE Computer Society Press, Los Alamitos, CA, 371--374.
30. Biasotti, S. 2005. Topological coding of surfaces with boundary using Reeb graphs. Comput. Graph. Geom. 7, 1, 31--45.
31. Biasotti, S., Attali, D., Boissonnat, J.-D., Edelsbrunner, H., Elber, G., Mortara, M., di Baja, G. S., Spagnuolo, M., and Tanase, M. 2007. Skeletal structures. In Shape Analysis and Structuring, L. De Floriani and M. Spagnuolo, Eds. Springer, Berlin, Germany.
32. Biasotti, S., Cerri, A., Frosini, P., Giorgi, D., and Landi, C. 2008. Multidimensional size functions for shape comparison. J. Math. Imag. Vis. 32, 2, 161--179.
33. Biasotti, S., Falcidieno, B., and Spagnuolo, M. 2000a. Extended Reeb Graphs for surface understanding and description. In DGCI 2000: Proceedings of the 9th Discrete Geometry for Computer Imagery Conference, G. Borgefors and G. S. di Baja, Eds. Lecture Notes in Computer Science, vol. 1953. Springer Verlag, Berlin, Germany, 185--197.
34. Biasotti, S., Falcidieno, B., and Spagnuolo, M. 2002. Shape abstraction using computational topology techniques. In From Geometric Modeling to Shape Modeling, U. Cugini and M. Wozny, Eds. Kluwer Academic Publishers, Dordrecht, The Netherlands, 209--222.
35. Biasotti, S., Falcidieno, B., and Spagnuolo, M. 2004. Surface shape understanding based on extended Reeb graphs. In Topological Data Structures for Surfaces: An Introduction for Geographical Information Science, S. Rana, Ed. John Wiley & Sons, New York, NY, 87--103.
36. Biasotti, S., Giorgi, D., Spagnuolo, M., and Falcidieno, B. 2006a. Computing size functions for 3D models. Tech. rep. 3-2006, IMATI-CNR, Genoa, Italy.
37. Biasotti, S., Giorgi, D., Spagnuolo, M., and Falcidieno, B. 2006b. Size functions for 3D shape retrieval. In SGP'06: Proceedings of the 2006 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing. 239--242.
38. Biasotti, S., Marini, M., Spagnuolo, M., and Falcidieno, B. 2006c. Sub-part correspondence by structural descriptors of 3D shapes. Comput. Aid. Des. 38, 9 (Sept.), 1002--1019.
39. Biasotti, S. and Marini, S. 2005. 3D object comparison based on shape descriptors. Internat. J. Comput. Applicat. Tech. 23, 2/3/4, 57--69.
40. Biasotti, S., Marini, S., Mortara, M., Patané, G., Spagnuolo, M., and Falcidieno, B. 2003. 3D shape matching through topological structures. In Discrete Geometry for Computer Imagery. Lecture Notes in Computer Science, vol. 2886. 194--203.
41. Biasotti, S., Mortara, M., and Spagnuolo, M. 2000b. Surface compression and reconstruction using Reeb graphs and shape analysis. In SCCG 2000: Proceedings of the 16th Spring Conference on Computer Graphics. ACM Press, New York, NY, 174--185.
42. Biasotti, S., Patané, G., Spagnuolo, M., and Falcidieno, B. 2007c. Analysis and comparison of real functions on triangulated surfaces, curves and surface. In Curve and Surface Fitting, A. Cohen, J.-L. Merrien, and L. L. Schumaker, Eds. Nashboro Press, Brentwood, TN, 41--50.
43. Bieniek, A. and Moga, A. 1998. A connected component approach to the watershed segmentation. In Mathematical Morphology and its Application to Image and Signal Processing, H. Heijmans and J. Roerdink, Eds. Kluwer Academic Publishers, Dordrecht, The Netherlands, 215--222.
44. Bieniek, A. and Moga, A. 2000. An efficient watershed algorithm based on connected components. Patt. Recog. 33, 907--916.
45. Boyell, R. L. and Ruston, H. 1963. Hybrid techniques for real-time radar simulation. In Proceedings of the 1963 Fall Joint Computer Conference.
46. Breen, E. and Jones, R. 1996. Attribute openings, thinnings, and granulometries. Comput. Vis. Image Understand. 64, 377--389.
47. Bremer, P.-T., Edelsbrunner, H., Hamann, B., and Pascucci, V. 2003. A multi-resolution data structure for two-dimensional Morse functions. In VIS '03: Proceedings of the IEEE Visualization 2003, G. Turk, J. van Wijk, and R. Moorhead, Eds. IEEE Computer Society Press, Los Alamitos, CA, 139--146.
48. Bremer, P.-T., Edelsbrunner, H., Hamann, B., and Pascucci, V. 2004. A topological hierarchy for functions on triangulated surfaces. IEEE Trans. Visual. Comput. Graph. 10, 4 (July/Aug.), 385--396.
49. Bremer, P. T. and Pascucci, V. 2007. A practical approach to two-dimensional scalar topology. In Topology-Based Methods in Visualization, H. Hauser, H. Hagen, and H. Theisel, Eds. Springer, Berlin Heidelberg, Germany, 151--169.
50. Bremer, P.-T., Pascucci, V., and Hamann, B. 2005. Maximizing adaptivity in hierarchical topological models. In SMI '05: Proceedings of the International Conference on Shape Modeling and Applications 2005. IEEE Computer Society Press, Los Alamitos, CA, 300--309.
51. Buchin, K., Dey, T. K., Giesen, J., and John, M. 2008. Recursive geometry of the flow complex and topology of the flow complex filtration. Computat. Geom. Theor. Appl. 40, 2, 115--137.
52. Bustos, B., Keim, D. A., Saupe, D., Schreck, T., and Vranić, D. V. 2005. Feature-based similarity search in 3D object databases. ACM Comput. Surv. 37, 4 (Dec.), 345--387.
53. Cagliari, F., Di Fabio, B., and Ferri, M. 2007. One-dimensional reduction of multidimensional persistent homology. arXiv:math.A/0702713.
54. Cagliari, F., Ferri, M., and Pozzi, P. 2001a. Size functions from the categorical viewpoint. Acta Applicand. Math. 67, 225--235.
55. Cagliari, F., Landi, C., and Grasselli, L. 2001b. Presentations of Morse homology for studying shape of manifolds. Tech. rep. 10. DISMI, Università di Modena e Reggio Emilia, Modena and Reggio Emilia, Italy.
56. Cairns, S. S., 1934. On the triangulation of regular loci. Ann. Math. 2nd Series 35, 3, 579--587.
57. Carlsson, G. and Zomorodian, A. 2007. The theory of multidimensional persistence. In SCG '07: Proceedings of the 23rd Annual Symposium on Computational Geometry. ACM Press, New York, NY, 184--193.
58. Carlsson, G., Zomorodian, A., Collins, A., and Guibas, L. 2004. Persistence barcodes for shapes. In SGP '04: Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing. ACM Press, New York, NY, 127--138.
59. Carlsson, G., Zomorodian, A., Collins, A., and Guibas, L. 2005. Persistence barcodes for shapes. Int. J. Shape Model. 11, 2, 149--187.
60. Carr, H. 2004. Topological manipulation of isosurfaces. Ph.D. dissertation. The University of British Columbia, Vancouver, B.C., Canada.
61. Carr, H. and Snoeyink, J. 2003. Path seeds and flexible isosurfaces using topology for exploratory visualization. In VISSYM '03: Proceedings of the Symposium on Data Visualisation 2003. Eurographics Association, Aire-la-Ville, Switzerland, 49--58.
62. Carr, H. and Snoeyink, J. 2007. Representing interpolant topology for contour tree computation. In TopoInVis 2007: Workshop on Topology-Based Methods in Visualization 2007.
63. Carr, H., Snoeyink, J., and Axen, U. 2000. Computing contour trees in all dimensions. In SODA '00: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM Press, New York, NY, 918--926.
64. Carr, H., Snoeyink, J., and Axen, U. 2003. Computing contour trees in all dimensions. Computat. Geom. Theor. Applicat. 24, 2, 75--94.
65. Carr, H., Snoeyink, J., and van de Panne, M. 2004. Simplifying flexible isosurfaces using local geometric measures. In VIS '04: Proceedings of the IEEE Visualization Conference 2004. 497--504.
66. Cayley, A. 1859. On contour and slope lines. London, Edinburgh and Dublin Philosoph. Mag. J. Sci. XVIII, 264--268.
67. Cazals, F., Chazal, F., and Lewiner, T. 2003. Molecular shape analysis based upon the Morse-Smale complex and the Connolly function. In SCG '03: Proceedings of the 19th Annual Symposium on Computational Geometry. ACM Press, New York, NY, 351--360.
68. Cerri, A., Biasotti, S., and Giorgi, D. 2007. k-dimensional size functions for shape description and comparison. In ICIAP 2007: Proceedings of the 14th International Conference on Image Analysis and Processing. IEEE Computer Society Press, Los Alamitos, CA.
69. Cerri, A., Ferri, M., and Giorgi, D. 2005. A complete keypics experiment with size functions. In CIVR 2005: Proceedings of the International Conference on Image and Video Retrieval. Lecture Notes in Computer Science, vol. 3568. Springer, Berlin, Germany, 357--366.
70. Cerri, A., Ferri, M., and Giorgi, D. 2006. Retrieval of trademark images by means of size functions. Graph. Model. 68, 5, 451--471.
71. Chiang, Y.-J., Lenz, T., Lu, X., and Rote, G. 2005. Simple and optimal output-sensitive construction of contour trees using monotone paths. Computat. Geom. Theor. Applicat. 30, 165--195.
72. Chiang, Y.-J. and Lu, X. 2003. Progressive simplification of tetrahedral meshes preserving all isosurface topologies. Comput. Graph. For. 22, 3, 493--504.
73. Cohen-Steiner, D., edelsbrunner, H., and Harer, J. 2005. Stability of persistence diagrams. In SCG '05: Proceedings of the 21st Annual Symposium on Computational Geometry. ACM Press, New York, NY, 263--271.
74. Cohen-Steiner, D., Edelsbrunner, H., and Harer, J. 2007a. Extending persistence using Poincaré and Lefschetz duality. Found. Computat. Math. To appear.
75. Cohen-Steiner, D., Edelsbrunner, H., and Harer, J. 2007b. Stability of persistence diagrams. Discrete Computat. Geom. 37, 1, 103--120.
76. Cohen-Steiner, D., Edelsbrunner, H., and Morozov, D. 2006. Vines and vineyards by updating persistence in linear time. In SCG '06: Proceedings of the 22nd Annual Symposium on Computational Geometry. ACM Press, New York, NY, 119--126.
77. Cole-McLaughlin, K., Edelsbrunner, H., Harer, J., Natarajan, V., and Pascucci, V. 2003. Loops in Reeb graphs of 2-manifolds. In SCG '03: Proceedings of the 19th Annual Symposium on Computational Geometry. ACM Press, New York, NY, 344--350.
78. Collins, A., Zomorodian, A., Carlsson, G., and Guibas, L. 2004a. A barcode shape descriptor for curve point cloud data. Comput. Graph. 28, 6, 881--894.
79. Collins, A., Zomorodian, A., Carlsson, G., and Guibas, L. 2004b. A barcode shape descriptor for curve point cloud data. In SPBG'04: Proceedings of the Symposium on Point-Based Graphics 2004. Eurographics Association, Aire-la-Ville, Switzerland, 181--191.
80. Cornea, N., Silver, D., and Min, P. 2005. Curve-skeleton applications. VIS '05: Proceedings of the IEEE Visualization Conference 2005, 95--102.
81. Couprie, M. and Bertrand, G. 1997. Topological grayscale watershed transformation. In Vision Geometry V, Proceedings of SPIE. Vol. 3168. 136--146.
82. Cox, J., Karron, D. B., and Ferdous, N. 2003. Topological zone organization of scalar volume data. J. Math. Imag. Vis. 18, 95--117.
83. d'Amico, M. 2000. A new optimal algorithm for computing size function of shapes. In CVPRIP Algorithms III: Proceedings of the International Conference on Computer Vision, Pattern Recognition and Image Processing. 107--110.
84. d'Amico, M., Ferri, M., and Stanganelli, I. 2004. Qualitative asymmetry measure for melanoma detection. In ISBI2004: Proceedings of the IEEE International Symposium on Biomedical Images (Arlington, VA). 1155--1158.
85. d'Amico, M., Frosini, P., and Landi, C. 2003. Optimal matching between reduced size functions. Tech. rep. 35. DISMI, Università di Modena e Reggio Emilia, Modena and Reggio Emilia, Italy.
86. d'Amico, M., Frosini, P., and Landi, C. 2005. Natural pseudo-distance and optimal matching between reduced size functions. Tech. rep. 66. DISMI, Università di Modena e Reggio Emilia, Modena and Reggio Emilia, Italy. (Acta Appl. Math. To appear.)
87. d'Amico, M., Frosini, P., and Landi, C. 2006. Using matching distance in size theory: A survey. Int. J. Imag. Syst. Techn. 16, 5, 154--161.
88. Danovaro, E., De Floriani, L., Magillo, P., Mesmoudi, M. M., and Puppo, E. 2003a. Morphology-driven simplification and multi-resolution modeling of terrains. In ACM-GIS 2003: Proceedings of the 11th International Symposium on Advances in Geographic Information Systems, E. Hoel and P. Rigaux, Eds. ACM Press, New York, NY, 63--70.
89. Danovaro, E., De Floriani, L., and Mesmoudi, M. M. 2003b. Topological analysis and characterization of discrete scalar fields. In Theoretical Foundations of Computer Vision, Geometry, Morphology, and Computational Imaging, T. Asano, R. Klette, and C. Ronse, Eds. Lecture Notes in Computer Science, vol. 2616. Springer Verlag, Berlin, Germany, 386--402.
90. Danovaro, E., De Floriani, L., and Vitali, M. 2007. Multi-resolution Morse-Smale complexes for terrain modeling. In ICIAP 2007: Proceedings of the 14th International Conference on Image Analysis and Processing. IEEE Computer Society Press, Los Alamitos, CA.
91. Danovaro, E., De Floriani, L., Papaleo, L., and Vitali, M. 2006. A multi-resolution representation of terrain morphology. In Geographic, Information Science, M. Raubal, H. Miller, A. Frank, and M. Goodchild, Eds. Lecture Notes in Computer Science, vol. 4197. Springer, Berlin, Germany.
92. de Berg, M., Cheong, O., Haverkort, H., Lim, J., and Toma, L. 2007. I/O-efficient flow modeling on fat terrains. In WADS 2007: Proceedings of the 10th International Workshop on Algorithms and Data Structures, F. Dehne, I. Munro, J.-R. Sack, and R. Tamassia, Eds. Lecture Notes in Computer Science. Springer Verlag, Berlin, Germany, 1--14.
93. de Berg, M. and van Kreveld, M. 1997. Trekking in the Alps without freezing or getting tired. Algorithmica 19, 306--323.
94. De Floriani, L., Magillo, P., and Puppo, E. 1999. Multi-resolution representation of shapes based on cell complexes. In Discrete Geometry for Computer Imagery, G. Bertrand, M. Couprie, and L. Perroton, Eds. Lecture Notes in Computer Science, vol. 1568. Springer Verlag, New York, NY, 3--18.
95. de Leeuw, W. and van Liere, R. 1999. Collapsing flow topology using area metrics. In VIS '99: Proceedings of the IEEE Visualization 1999. IEEE Computer Society Press, Los Alamitos, CA, 349--354.
96. de Silva, V. and Carlsson, G. 2004. Topological estimation using witness complexes. In PBG 2004: Proceedings of the Symposium on Point-Based Graphics 2004. Eurographics Association, Aire-la-Ville, Switzerland, 157--166.
97. de Silva, V. and Ghrist, R. 2007. Coverage in sensor networks via persistent homology. Alg. Geom. Topol. 7, 339--358.
98. Del Bimbo, A. and Pala, P. 2006. Content-based retrieval of 3D models. ACM Trans. Multimed. Comput. Commun. Applicat. 2, 1, 20--43.
99. Delfinado, C. J. A. and Edelsbrunner, H. 1995. An incremental algorithm for Betti numbers of simplicial complexes on the 3-sphere. Comput. Aid. Geom. Des. 12, 771--784.
100. Dey, T. and Wenger, R. 2007. Stability of critical points with interval persistence. Discr. Computat. Geom. 38, 479--512.
101. Dey, T. K., Edelsbrunner, H., and Guha, S. 1999. Computational topology. In Advances in Discrete and Computational Geometry, B. Chazelle, J. E. Goodman, and R. Pollack, Eds. Contemporary Mathematics, vol. 223. AMS, Providence, RI, 109--143.
102. Dey, T. K., Giesen, J., and Goswami, S. 2003. Shape segmentation and matching with flow discretization. In Algorithms and Data Structures. Lecture Notes in Computer Science, vol. 2748. Springer, Berlin, Germany, 25--36.
103. Dey, T. K. and Sun, J. 2006. Defining and computing curve-skeletons with medial geodesic function. In SGP'06: Proceedings of the 2006 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing. 143--152.
104. di Battista, G., Eades, P., Tamassia, R., and Tollis, I. G. 1999. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, Englewood Cliffs, NJ.
105. Dibos, F., Frosini, P., and Pasquignon, D. 2004. The use of size functions for comparison of shapes through differential invariants. J. Math. Imag. Vis. 21, 107--118.
106. Donatini, P. and Frosini, P. 2004a. Lower bounds for natural pseudodistances via size functions. Arch. Inequal. Applicat. 2, 1--12.
107. Donatini, P. and Frosini, P. 2004b. Natural pseudodistances between closed manifolds. For. Mathematic. 16, 5, 695--715.
108. Donatini, P. and Frosini, P. 2007. Natural pseudodistances between closed surfaces. J. Europ. Math. Soc. 9, 2, 231--253.
109. Donatini, P., Frosini, P., and Landi, C. 1999. Deformation energy for size functions. In EMMCVPR'99: Proceedings of the 2nd International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition, E. R. Hancock and M. Pelillo, Eds. Lecture Notes in Computer Science, vol. 1654. Springer, Berlin, Germany, 44--53.
110. Dong, S., Bremer, P.-T., Garland, M., Pascucci, V., and Hart, J. 2006. Spectral surface quadrangulation. ACM Trans. Graph. 25, 3 (Aug.). Proceedings SIGGRAPH 2006.
111. Dryden, I. and Mardia, K. 1998. Statistical Shape Analysis. John Wiley & Sons New York, NY.
112. Edelsbrunner, H., Facello, M., and Liang, J. 1998. On the definition and the construction of pockets in macromolecules. Discr. Appl. Math. 88, 1-3, 83--102.
113. Edelsbrunner, H. and Harer, J. 2002. Jacobi sets of multiple Morse functions. In Foundations in Computational Mathematics, F. Cucker, R. DeVore, P. Olver, and E. Sueli, Eds. Cambridge University Press, Cambridge, U.K. 37--57.
114. Edelsbrunner, H. and Harer, J. 2007. Persistent homology—a survey. Contemp. Math. 453, 257--282.
115. Edelsbrunner, H., Harer, J., Mascarenhas, A., and Pascucci, V. 2004. Time-varying Reeb graphs for continuous space-time data. In SCG '04: Proceedings of the 20th Annual Symposium on Computational Geometry. ACM Press, New York, NY, 366--372.
116. Edelsbrunner, H., Harer, J., Natarajan, V., and Pascucci, V. 2003a. Morse-Smale complexes for piecewise linear 3-manifolds. In SCG '03: Proceedings of the 19th Annual Symposium on Computational Geometry. ACM Press, New York, NY, 361--370.
117. Edelsbrunner, H., Harer, J., and Zomorodian, A. 2001. Hierarchical Morse complexes for piecewise linear 2-manifolds. In SCG '01: Proceedings of the 17th Annual Symposium on Computational Geometry. ACM Press, New York, NY, 70--79.
118. Edelsbrunner, H., Harer, J., and Zomorodian, A. 2003b. Hierarchical Morse-Smale complexes for piecewise linear 2-manifolds. Discr. Computat. Geom. 30, 87--107.
119. Edelsbrunner, H., Letscher, D., and Zomorodian, A. 2000. Topological persistence and simplification. In IEEE Foundations of Computer Science, Proceedings of the 41st Annual Symposium. 454--463.
120. Edelsbrunner, H., Letscher, D., and Zomorodian, A. 2002. Topological persistence and simplification. Discr. Computat. Geom. 28, 511--533.
121. Edelsbrunner, H., Morozov, D., and Pascucci, V. 2006. Persistence-sensitive simplification of functions on 2-manifolds. In SCG '06: Proceedings of the 22nd Annual Symposium on Computational Geometry. ACM Press, New York, NY, 127--134.
122. Edelsbrunner, H. and Mücke, E. P. 1990. Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms. ACM Trans. Graph. 9, 1, 66--104.
123. Ehresmann, C. and Reeb, G. 1944. Sur les champs d'éléments de contact de dimension p complètement intégrable dans une variété continuèment differentiable v_n. Compt. Rend. Hebdomad. Séances l'Académ. Sci. 218, 955--957.
124. Ferri, M. and Frosini, P. 2005. A proposal for image indexing: Keypics, plastic graphical metadata. In Internet Imaging VI, Proceedings of SPIE (San Jose, CA). Vol. 5670. 225--231.
125. Ferri, M., Lombardini, S., and Pallotti, C. 1994. Leukocyte classification by size functions. In Proceedings of the 2nd IEEE Workshop on Applications of Computer Vision, IEEE Computer Society Press, Los Alamitos, CA, 223--229.
126. Forman, R. 1998. Morse theory for cell complexes. Adv. Math. 134, 90--145.
127. Forman, R. 2002. A user's guide to discrete Morse theory. Seminaire Lotharingien de Combinatoire 48.
128. Freeman, H. and Morse, S. P. 1967. On searching a contour map for a given terrain profile. J. Franklin Inst. 248, 1--25.
129. Frosini, P. 1990. A distance for similarity classes of submanifolds of a Euclidean space. Bull. Australian Math. Soc. 42, 407--416.
130. Frosini, P. 1991. Measuring shapes by size functions. In Intelligent Robots and Computer Vision X: Algorithms and Techniques, Proceedings of SPIE, D. P. Casasent, Ed. Vol. 1607. 122--133.
131. Frosini, P. 1992. Discrete computation of size functions. J. Combin. Inform. System Sci. 17, 232--250.
132. Frosini, P. 1996. Connections between size functions and critical points. Math. Meth. Appl. Sci. 19, 555--596.
133. Frosini, P. and Landi, C. 1997. New pseudo-distances for the size function space. In Vision Geometry VI, Proceedings of SPIE, R. A. Melter, A. Y. Wu, and L. J. Latecki, Eds. Vol. 3168. 52--60.
134. Frosini, P. and Landi, C. 1999. Size theory as a topological tool for computer vision. Patt. Recog. Image Anal. 9, 596--603.
135. Frosini, P. and Landi, C. 2001. Size functions and formal series. Applic. Alg. Eng. Commun. Comput. 12, 327--349.
136. Frosini, P. and Mulazzani, M. 1999. Size homotopy groups for computation of natural size distances. Bull. Belgian Math. Soc. 6, 455--464.
137. Frosini, P. and Pittore, M. 1999. New methods for reducing size graphs. Int. J. Comput. Math. 70, 505--517.
138. Fuchs, H., Kedem, Z., and Uselton, S. 1977. Optimal surface reconstruction from planar contours. Commun. ACM 20, 693--702.
139. Fujishiro, I., Azuma, T., and Takeshima, Y. 1999. Automating transfer function design for comprehensible volume rendering based on 3D field topology analysis. In VIS '99: Proceedings of the IEEE Visualization Conference 1999. 467--470.
140. Fujishiro, I., Takeshima, Y., Azuma, T., and Takahashi, S. 2000. Volume data mining using 3D field topology analysis. IEEE Comput. Graph. Applicat. 20, 5 (Sept./Oct.), 46--51.
141. Gerstner, T. and Pajarola, R. 2000. Topology preserving and controlled topology simplifying multiresolution isosurface extraction. In VIS '00: Proceedings of the IEEE Visualization Conference 2000. IEEE Computer Society Press, Los Alamitos, CA, 259--266.
142. Giblin, P. and Kimia, B. 2004. A formal classification of 3D medial axis points and their local geometry. IEEE Trans. Patt. Anal. Mach. Intell. 26, 2, 238--251.
143. Giertsen, C., Halvorsen, A., and Flood, P. 1990. Graph-directed modelling from serial sections. Vis. Comput. 6, 284--290.
144. Giesen, J. and John, M. 2003. The flow complex: A data structure for geometric modeling. In SODA '03: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, Philadelphia, PA, 285--294.
145. Goresky, M. and MacPherson, R. 1988. Stratified Morse Theory. Springer-Verlag, New York, NY.
146. Gramain, A. 1971. Topologie des surfaces. Presses Universitaires de France. Paris, France.
147. Grandis, M. 2003. Ordinary and directed combinatorial homotopy, applied to image analysis and concurrency. Homol. Homot. Appl. 5, 211--231.
148. Greenberg, M. and Harper, J. R. 1981. Algebraic Topology: A First Course. Addison-Wesley, Reading, MA.
149. Griffiths, H. B. 1976. Surfaces. Cambridge University Press, Cambridge, U.K.
150. Guibas, L. and Stolfi, J. 1985. Primitives for the manipulation of general subdivisions and computation of Voronoi diagrams. ACM Trans. Graph. 4, 2 (Apr.), 74--123.
151. Gyulassy, A., Natarajan, V., Pascucci, V., Bremer, P.-T., and Hamann, B. 2005. Topology-based simplification for feature extraction from 3D scalar fields. In VIS '05: Proceedings of the IEEE Visualization Conference 2005. IEEE Computer Society Press, Los Alamitos, CA, 275--280.
152. Gyulassy, A., Natarajan, V., Pascucci, V., Bremer, P.-T., and Haman, B. 2006. A topological approach to simplification of three-dimensional scalar functions. IEEE Trans. Visual. Comput. Graph. 12, 4, 474--484.
153. Halley, E. 1702. A new and correct sea chart of the whole world shewing the variations of the compass as they were found in the year M.D.CC. (Cartographic map). Mount & Page, London, U.K.
154. Handouyaya, M., Ziou, D., and Wang, S. 1999. Sign language recognition using moment-based size functions. In Proceedings of the Conference on Vision Interface 99, Trois-Rivières. 210--216.
155. Harrison, J. 2005. Lecture notes on chainlet geometry—new topological methods in geometric measure theory. ArXiv Mathematical Physics e-prints, math-ph/0505063.
156. Helman, J. and Hesselink, L. 1989. Representation and display of vector field topology in fluid flow data sets. Comput. 27--36.
157. Hetroy, F. and Attali, D. 2003. Topological quadrangulations of closed triangulated surfaces using the Reeb graph. Graphic. Mod. 65, 1-3, 131--148.
158. Hilaga, M., Shinagawa, Y., Kohmura, T., and Kunii, T. L. 2001. Topology matching for fully automatic similarity estimation of 3D shapes. In SIGGRAPH '01: Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques. ACM Press, New York, NY, 203--212.
159. Hirani, A. N. 2003. Discrete exterior calculus. Ph.D. dissertation. California Institute of Technology, Pasadena, CA.
160. Hirsch, M. W. 1997. Differential Topology. Springer, Berlin, Germany.
161. Huang, X., Fisher, M., and Smith, D. 2003. An efficient implementation of Max Tree with linked list and Hash table. In Proceedings of the VII Digital Image Computing: Techniques and Applications (Sidney, Australia), C. Sun, H. Talbot, S. Ourselin, and T. Adriansen, Eds. 299--308.
162. Itoh, T. and Koyamada, K. 1994. Isosurface extraction by using extrema graphs. In VIS '94: Proceedings of Visualization '94. IEEE Computer Society Press, Los Alamitos, CA, 77--83.
163. Itoh, T. and Koyamada, K. 1995. Automatic isosurface propagation using extrema graph and sorted boundary cell lists. IEEE Trans. Visualiz. Comput. Graph. 1, 4, 319--327.
164. Itoh, T., Yamaguchi, Y., and Koyamada, K. 2001. Fast isosurface generation using the volume thinning algorithm. IEEE Trans. Visualiz. Comput. Graph. 7, 1, 32--46.
165. Iyer, N., Jayanti, S., Lou, K., Kalyanaraman, Y., and Ramani, K. 2005. Three-dimensional shape searching: state-of-the-art review and future trends. Comput.-Aid. Des. 37, 5, 509--530.
166. Jones, M. W., Baerentzen, J. A., and Sramek, M. 2006. 3D distance fields: A survey of techniques and applications. IEEE Trans. Visualiz. Comput. Graph. 12, 4, 581--599.
167. Jones, R. 1999. Connected filtering and segmentation using component trees. Comput. Vis. Image Understand. 75, 215--228.
168. Kaczynski, T., Mischaikow, K., and Mrozek, M. 2004. Computational Homology. Applied Mathematical Sciences, vol. 157. Springer-Verlag, Berlin, Germany.
169. Kanongchaiyos, P. and Shinagawa, Y. 2000. Articulated Reeb graphs for interactive skeleton animation. In Multimedia Modeling: Modeling Multimedia Information and System. World Scientific, Singapore, 451--467.
170. Kelley, J. and Pitcher, E. 1947. Exact homomorphism sequences in homology theory. Ann. Math. 2nd Series. 48, 3, 682--709.
171. Kettner, L., Rossignac, J., and Snoeyink, J. 2003. The Safari interface for visualizing time-dependent volume data using iso-surfaces and contour spectra. Computat. Geom. Theor. Appl. 25, 1-2, 97--116.
172. Klette, R. and Rosenfeld, A. 2004. Digital Geometry: Geometric Methods for Digital Picture Analysis. Morgan Kaufmann Series in Computer Graphics and Geometric Modeling. Morgan Kaufmann, San Francisco, CA.
173. Koenderink, J. J. 1990. Solid Shape. MIT Press, Cambridge, MA.
174. Lam, L., Lee, S., and Suen, C. 1992. Thinning methodologies—a comprehensive survey. IEEE Trans. Patt. Anal. Mach. Intell. 14, 9, 869--885.
175. Landi, C. and Frosini, P. 2002. Size functions as complete invariants for image recognition. In Vision Geometry XI, Proceedings of SPIE, L. J. Latecki, D. M. Mount, and A. Y. Wu, Eds. Vol. 4794. 101--109.
176. Laney, D., Bremer, P. T., Mascarenhas, A., Miller, P., and Pascucci, V. 2006. Understanding the structure of the turbulent mixing layer in hydrodynamic instabilities. IEEE Trans. Visualiz. Comput. Graph. 12, 5, 1053--1060.
177. Lazarus, F. and Verroust, A. 1999. Level set diagrams of polyhedral objects. In SMA '99: Proceedings of the 5th ACM Symposium on Solid Modeling and Applications 1999, W. Bronsvoort and D. Anderson, Eds. ACM Press, New York, NY, 130--140.
178. Lévy, B. 2006. Laplace-Beltrami eigenfunctions: Towards an algorithm that understands geometry. In SMI '06: Proceedings of the IEEE International Conference on Shape Modeling and Applications 2006. IEEE Computer Society Press, Los Alamitos, CA. 13--20.
179. Lewiner, T., Lopes, H., and Tavares, G. 2003. Towards optimality in discrete Morse theory. Exper. Math. 12, 3, 271--285.
180. Lewiner, T., Lopes, H., and Tavares, G. 2004. Applications of Forman's discrete Morse theory to topology visualization and mesh compression. IEEE Trans. Visualiz. Comput. Graph. 10, 5, 499--508.
181. Loncaric, S. 1998. A survey of shape analysis techniques-from automata to hardware. Patt. Recog. 31, 8, 983--1001.
182. Magillo, P., Danovaro, E., De Floriani, L., Papaleo, L., and Vitali, M. 2007. Extracting terrain morphology: A new algorithm and a comparative evaluation. In Proceedings of the 2nd International Conference on Computer Graphics Theory and Applications (Barcelona, Spain).
183. Mangan, A. and Whitaker, R. 1999. Partitioning 3D surface meshes using watershed segmentation. IEEE Trans. Visualiz. Comput. Graph. 5, 4, 308--321.
184. Mäntylä, M. 1988. Introduction to Solid Modeling. WH Freeman & Co. New York, NY.
185. Marini, S., Spagnuolo, M., and Falcidieno, B. 2007. Structural shape prototypes for the automatic classification of 3D objects. IEEE Comput. Graph. Appl. 27, 4, 28--37.
186. Mattes, J. G. and Demongeot, J. 2000. Efficient algorithms to implement the confinement tree. In DGCI 2000: Proceedings of the 9th Discrete Geometry for Computer Imagery Conference, G. Borgefors and G. S. di Baja, Eds. Lecture Notes in Computer Science, vol. 1953. Springer Verlag, Berlin, Germany, 392--405.
187. Maxwell, J. C. 1870. On hills and dales. London, Edinburgh and Dublin Philosoph. Mag. J. Sci. 40, 269, 421--425.
188. McAllister, M. 1999. A watershed algorithm for triangulated terrains. In CCCG99: Proceedings of the 11th Canadian Conference on Computational Geometry (Vancouver, BC). vol. VIII--A. 1--8.
189. Meijster, A. and Roerdink, J. 1996. Computation of watersheds based on parallel graph algorithms. In Mathematical Morphology and its Application to Image Segmentation, P. Maragos, R. W. Shafer, and M. A. Butt, Eds. Kluwer, Dordrecht, The Netherlands, 305--312.
190. Merrill, R. D. 1973. Representation of contours and regions for efficient computer search. Commun. ACM 16, 2, 69--82.
191. Mesmoudi, M. and De Floriani, L. 2007. Morphology-based representations of discrete scalar fields. In GRAPP 2007: Proceedings of the International Conference on Computer Graphics Theory (Barcelona, Spain). 137--144.
192. Mesmoudi, M. M., Danovaro, E., De Floriani, L., and Port, U. 2007. Surface segmentation through concentrated curvature. In ICIAP 2007: Proceedings of the 14th International Conference on Image Analysis and Processing. IEEE Computer Society Press, Los Alamitos, CA.
193. Meyer, F. 1994. Topographic distance and watershed lines. Signal Process. 38, 113--125.
194. Meyers, D., Skinner, S., and Sloan, K. 1992. Surfaces from contours. ACM Trans. Graph. 11, 228--258.
195. Milnor, J. 1963. Morse Theory. Princeton University Press, Princeton, NJ.
196. Milnor, J. 1965. Lectures on h-Cobordism. Princeton University Press, Princeton, NJ.
197. Mizuta, S. and Matsuda, T. 2005. Description of digital images by region-based contour trees. In Proceedings of the International Conference on Image Analysis and Recognition. Lecture Notes in Computer Science, vol. 3656. Springer, Berlin, Germany, 549--558.
198. Monasse, P. and Guichard, F. 2000. Fast computation of a contrast-invariant image representation. IEEE Trans. Image Process. 9, 5, 860--872.
199. Mortara, M. and Patané, G. 2002. Shape-covering for skeleton extraction. Int. J. Shape Model. 8, 245--252.
200. Mortara, M., Patané, G., Spagnuolo, M., Falcidieno, B., and Rossignac, J. 2004. Blowing bubbles for multi-scale analysis and decomposition of triangle meshes. Algorithmica 38, 1, 227--248.
201. Mortenson, M. E. 1986. Geometric Modeling. John Wiley & Sons, New York, NY.
202. Munkres, J. 2000. Topology. Prentice Hall, Englewood Cliffs, NJ.
203. Nackman, L. 1984. Two-dimensional critical point configuration graphs. IEEE Trans. Patt. Anal. Mach. Intell. 6, 4, 442--450.
204. Nackman, L. R. and Pizer, S. M. 1985. Three-dimensional shape description using the symmetric axis transform. I: Theory. IEEE Trans. Patt. Anal. Mach. Intell. 7, 2, 187--2002.
205. Najman, L. and Couprie, M. 2003. Watershed algorithms and contrast preservation. In DGCI 2003: Proceedings of the 11th Discrete Geometry for Computer Imagery, I. Nyström, G. Sanniti di Baja, and S. Svensson, Eds. Lecture Notes in Computer Science, vol. 2886. Springer, Berlin, Germany, 62--71.
206. Najman, L. and Schmitt, M. 1996. Geodesic saliency of watershed contours and hierarchical segmentation. IEEE Trans. Patt. Anal. Mach. Intell. 18, 12, 1163--1173.
207. Natarajan, V., Wang, Y., Bremer, P.-T., Pascucci, V., and Hamann, B. 2006. Segmenting molecular surfaces. Comput. Aid. Geom. Des. 23, 6, 495--509.
208. Natarajan, V. J. and Pascucci, V. 2005. Volumetric data analysis using Morse-Smale complexes. In SMI '05: Proceedings of the International Conference on Shape Modeling and Applications 2005. 320--325.
209. Ni, X., Garland, M., and Hart, J. C. 2004. Fair Morse functions for extracting the topological structure of a surface mesh. ACM Trans. Graph. 23, 3, 613--622.
210. Niyogi, P., Smale, S., and Weinberger, S. 2006. Finding the homology of submanifolds with high confidence from random samples. Discr. Computat. Geom. 39, 1--3, 419--441.
211. Oliva, J. M., Perrin, M., and Coquillart., S. 1996. 3D reconstruction of complex polyhedral shapes from contours using a simplified generalised Voronoi diagram. Comput. Graph. For. 15, 307--318.
212. Page, D. L. 2003. Part decomposition of 3D surfaces. Ph.D. dissertation. University of Tennessee, Knoxville, TN.
213. Palis, J. and Melo, W. D. 1982. Geometric Theory of Dynamical Systems: An Introduction. Springer-Verlag, Berlin, Germany.
214. Papaleo, L. 2004. Surface reconstruction: online mosaicing and modeling with uncertainty. Ph.D. dissertation. University of Genova, Genoa, Italy.
215. Paraboschi, L., Biasotti, S., and Falcidieno, B. 2007. Comparing sets of 3D digital shapes through topological structures. In GbR'07: Proceedings of the 6th IARP-TC-15 Workshop on Graphbased Representations in Pattern Recognition, F. Escolano and M. Vento, Eds. Lecture Notes in Computer Science, vol. 4538. Springer, Berlin, Germany, 114--125.
216. Pascucci, V. 2004. Topology diagrams of scalar fields in scientific visualization. In Topological Data Structures for Surfaces, S. Rana, Ed. John Wiley & Sons London, U.K., 121--129.
217. Pascucci, V. and Cole-McLaughin, K. 2002. Efficient computation of the topology of the level sets. In VIS '02: Proceedings of the IEEE Visualization Conference 2002. IEEE Press, Los Alamitos, CA, 187--194.
218. Pascucci, V. and Cole-McLaughlin, K. 2003. Parallel computation of the topology of level sets. Algorithmica 38, 1, 249--268.
219. Pascucci, V., Cole-McLaughin, K., and Scorzelli, G. 2004. Multi-resolution computation and presentation of contour trees. LLNL Tech. rep. number UCRL-PROC-208680. Lawrence Livermore National Laboratory, Livermore, CA.
220. Pascucci, V., Scorzelli, G., Bremer, P.-T., and Mascarenhas, A. 2007. Robust on-line computation of Reeb graphs: Simplicity and speed. ACM Trans. Graph. 26, 3 (Aug.), 58.1--58.9.
221. Patané, G., Spagnuolo, M., and Falcidieno, B. 2004. Graph-based parameterization of triangle meshes with arbitrary genus. Comput. Graph. For. 23, 4, 783--797.
222. Pavlidis, T. 1995. A review of algorithms for shape analysis. In Document Image Analysis. IEEE Computer Society Press, Los Alamitos, CA, 145--160.
223. Peucker, T. K. and Douglas, D. H. 1975. Detection of surface-specific points by local parallel processing of discrete terrain elevation data. Comput. Graph. Image Process. 4, 375--387.
224. Pfaltz, J. L. 1976. Surface networks. Geograph. Anal. 8, 77--93.
225. Press, W., Teukolsky, S., Vetterling, W., and Flannery, B. 1992. Numerical Recipes in C, 2nd ed. Cambridge University Press, Cambridge, U.K.
226. Rana, S., Ed. 2004. Topological Data Structures for Surfaces: An Introduction for Geographical Information Science. John Wiley & Sons, London, U.K.
227. Reeb, G. 1946. Sur les points singuliers d'une forme de Pfaff complètement intégrable ou d'une fonction numérique. Compt. Rend. Hebdomad. Séances l'Académ. Sci. 222, 847--849.
228. Requicha, A. 1980. Representations of rigid solids: Theory, methods and systems. ACM Comput. Surv. 12, 4, 437--464.
229. Robins, V. 1999. Towards computing homology from finite approximations. In Proceedings of the 14th Summer Conference on General Topology and its Applications, W. Comfort, R. Heckmann, R. Kopperman, and L. Narici, Eds. Topology Proceedings, vol. 24. 503--532.
230. Robins, V. 2002. Computational topology for point data: Betti numbers of α-shapes. In Morphology of Condensed Matter: Physics and Geometry of Spatially Complex Systems, K. Mecke and D. Stoyan, Eds. Lecture Notes in Physics, vol. 600. Springer, Berlin, Germany, 261--274.
231. Roerdink, J. and Meijster, A. 2000. The watershed transform: Definitions, algorithms, and parallelization strategies. Fundamenta Informaticae 41, 187--228.
232. Salembier, P., Oliveras, A., and Garrido, L. 1998. Antiextensive connected operators for image and sequence processing. IEEE Trans. Image Process. 7, 555--570.
233. Schneider, B. 2005. Extraction of hierarchical surface networks from bilinear surface patches. Geograph. Anal. 37, 244--263.
234. Schneider, B. and Wood, J. 2004. Construction of metric surface networks from raster-based DEMs. In Topological Data Structures for Surfaces: An Introduction for Geographical Information Science, S. Rana, Ed. John Wiley & Sons Ltd, London, U.K., 53--70.
235. Serra, J. 1983. Image Analysis and Mathematical Morphology. Academic Press, Inc., Orlando, FL.
236. Shamir, A. 2006. Segmentation and shape extraction of 3D boundary meshes. In Proceedings of Eurographics STAR 2006, B. Wyvill and A. Wilkie, Eds. Eurographics Association, Aire-la-Ville, Switzerland, 137--149.
237. Shattuck, D. and Leahy, R. 2001. Automated graph based analysis and correction of cortical volume topology. IEEE Trans. Med. Imag. 20, 1167--1177.
238. Shinagawa, Y. and Kunii, T. 1991. Constructing a Reeb graph automatically from cross sections. IEEE Comput. Graph. Applicat. 11, 44--51.
239. Shinagawa, Y., Kunii, T. L., and Kergosien, Y. L. 1991. Surface coding based on Morse theory. IEEE Comput. Graph. Applicat. 11, 66--78.
240. Siddiqi, K. and Pizer, S. M., Eds. 2007. Medial Representations: Mathematics, Algorithms and Applications. Springer, Berlin, Germany.
241. Smale, S. 1960. Morse inequalities for a dynamical system. Bull. Amer. Math. Soc. 66, 43--49.
242. Sohn, B.-S. and Bajaj, C. L. 2006. Time-varying contour topology. IEEE Trans. Visual. Comput. Graph. 12, 1, 14--25.
243. Soille, P. 2004. Morphological Image Analysis: Principles and Applications. Springer-Verlag, Berlin, Germany, and New York, NY.
244. Spanier, E. H. 1966. Algebraic Topology. McGraw-Hill, New York, NY.
245. Stanganelli, I., Brucale, A., Calori, L., Gori, R., Lovato, A., Magi, S., Kopf, B., Bacchilega, R., Rapisarda, V., Testori, A., Ascierto, P. A., Simeone, E., and Ferri, M. 2005. Computer-aided diagnosis of melanocytic lesions. Anticanc. Res. 25, 6C, 4577--4582.
246. Steiner, D. and Fischer, A. 2001. Topology recognition of 3D closed freeform objects based on topological graphs. In Proceedings of the Pacific Conference on Computer Graphics and Applications, 82--88.
247. Stoev, S. L. and Strasser, W. 2000. Extracting regions of interest applying a local watershed transformation. In VIS 2000: Proceedings of the IEEE Visualization Conference 2000. IEEE Computer Society Press, Los Alamitos, CA, 21--28.
248. Sutton, P. and Hansen, C. D. 1999. Isosurface extraction in time-varying fields using a temporal branch-on-need tree (TBON). In VIS '99: Proceedings of the IEEE Visualization Conference 1999. 147--154.
249. Szymczak, A. 2005. Subdomain aware contour trees and contour evolution in time-dependent scalar fields. In SMI '05: Proceedings of the International Conference on Shape Modeling and Applications 2005. IEEE Computer Society Press, Los Alamitos, CA, 136--144.
250. Takahashi, S. 2004. Algorithms for Extracting Surface Topology from Digital Elevation Models. John Wiley & Sons Ltd, London, U.K., 31--51.
251. Takahashi, S., Fujishiro, I., and Takeshima, Y. 2005. Interval volume decomposer: A topological approach to volume traversal. In Visualization and Data Analysis 2005, Proceedings of SPIE, R. F. Erbacher, K. Börner, M. Gröhn, and J. C. Roberts, Eds. Vol. 5669. 103--114.
252. Takahashi, S., Ikeda, T., Shinagawa, Y., Kunii, T. L., and Ueda, M. 1995. Algorithms for extracting correct critical points and constructing topological graphs from discrete geographic elevation data. Comput. Graph. For. 14, 3, 181--192.
253. Takahashi, S., Nielson, G. M., Takeshima, Y., and Fujishiro, I. 2004a. Topological volume skeletonization using adaptive tetrahedralization. In Proceedings of Geometric Modelling and Processing 2004. 227--236.
254. Takahashi, S., Takeshima, Y., and Fujishiro, I. 2004b. Topological volume skeletonization and its application to transfer function design. Graph. Mod. 66, 1, 24--49.
255. Tangelder, J. and Veltkamp, R. 2004. A survey of content based 3D shape retrieval methods. In SMI '04: Proceedings of the IEEE International Conference on Shape Modeling and Applications 2004. 145--156.
256. Tarasov, S. P. and Vyalyi, M. N. 1998. Construction of contour trees in 3D in O(n log n) steps. In SCG '98: Proceedings of the 14th Annual Symposium on Computational Geometry. ACM Press, New York, NY, 68--75.
257. Tarjan, R. E. and von Leeuwen, J. 1984. Worst-case analysis of set union algorithms. J. 31, 2, 245--281.
258. Theisel, H., Roessl, C., and Weinkau, T. 2007. Morphological representations of vector fields. In Shape Analysis and Structuring, L. De Floriani and M. Spagnuolo, Eds. Springer, Berlin, Germany.
259. Thom, R. 1949. Sur une partition en cellules associée à une fonction sur une variété. Compt. Rend. Hebdomad. Séances l'Académ. Sci. 228, 973--975.
260. Toriwaki, J. and Fukumura, T. 1978. Extraction of structural information from gray pictures. Comput. Graph. Image Process. 7, 30--51.
261. Tricoche, X., Scheuermann, G., and Hagen, H. 2001. Continuous topology simplification of planar vector fields. In VIS '01: Proceedings of the IEEE Visualization Conference 2001. IEEE Computer Society Press, Los Alamitos, CA, 159--166.
262. Tung, T. and Schmitt, F. 2004. Augmented Reeb graphs for content-based retrieval of 3D mesh models. In SMI '04: Proceedings of the International Conference on Shape Modeling and Applications 2004. IEEE Computer Society Press, Los Alamitos, CA, 157--166.
263. Tung, T. and Schmitt, F. 2005. The augmented multiresolution Reeb graph approach for content-based retrieval of 3D shapes. Int. J. Shape Modell. 11, 1 (June), 91--120.
264. Turner, M. J. 1998. Design of entropy conscious and constrained image operations using a contour tree image definition. In 2nd IMA Conference on Image Processing: Mathematical Methods, Algorithms and Applications (Sept. 22--25, 1998).
265. Uras, C. and Verri, A. 1994. On the recognition of the alphabet of the sign language through size functions. In Proceedings of the 12th IAPR International Conference on Pattern Recognition. Jerusalem (Israel). Vol. II. IEEE Computer Society Press, Los Alamitos, CA, 334--338.
266. Uras, C. and Verri, A. 1997. Computing size functions from edge maps. Int. J. Comput. Vis. 23, 2, 169--183.
267. van Kreveld, M., van Oostrum, R., Bajaj, C. L., Pascucci, V., and Schikore, D. 1997. Contour trees and small seed sets for isosurface traversal. In SCG '97: Proceedings of the 13th Annual Symposium on Computational Geometry. ACM Press, New York, NY, 212--220.
268. van Kreveld, M., van Oostrum, R., Bajaj, C. L., Pascucci, V., and Schikore, D. 2004. Contour trees and small seed sets for isosurface generation. In Topological Data Structures for Surfaces: An Introduction for Geographical Information Science, S. Rana, Ed. John Wiley & Sons, London, U.K., 71--86.
269. Vegter, G. 1997. Computational topology. In Handbook of Discrete and Computational Geometry, J. E. Goodman and J. O'Rourke, Eds. CRC Press, Boca Raton, FL, 517--536.
270. Vegter, G. and Yap, C. K. 1990. Computational complexity of combinatorial surfaces. In SCG '90: Proceedings of the 6th Annual Symposium on Computational Geometry. ACM Press, New York, NY, 102--111.
271. Veltkamp, R. C. and Hagendoorn, M. 2001. State-of-the-art in shape matching. In Principles of Visual Information Retrieval, M. Lew, Ed. Springer-Verlag, Berlin, Germany, 87--119.
272. Verri, A. and Uras, C. 1994. Invariant size functions. In Applications of Invariance in Computer Vision, J. L. Mundy, A. Zisserman, and D. Forsyth, Eds. Lecture Notes in Computer Science, vol. 825. Springer, Berlin, Germany, 215--234.
273. Verri, A. and Uras, C. 1996. Metric-topological approach to shape representation and recognition. Image Vis. Comput. 14, 189--207.
274. Verri, A., Uras, C., Frosini, P., and Ferri, M. 1993. On the use of size functions for shape analysis. Biolog. Cybernet. 70, 99--107.
275. Verroust, A. and Lazarus, F. 2000. Extracting skeletal curves from 3D scattered data. Vis. Comput. 16, 15--25.
276. Vincent, L. and Soille, P. 1991. Watershed in digital spaces: An efficient algorithm based on immersion simulation. IEEE Trans. Patt. Anal. Mach. Intell. 13, 6, 583--598.
277. Wang, Y., Agarwal, P., Brown, P., Edelsbrunner, H., and Rudolph, J. 2005. Coarse and reliable geometric alignment for protein docking. In Proceedings of the Pacific Symposium on Biocomputing 2005.
278. Watson, L. T., Laffey, T. J., and Haralick, R. M. 1985. Topographic classification of digital image intensity surfaces using generalized splines and the discrete cosine transformation. Comput. Vis. Graph. Image Process. 29, 143--167.
279. Weber, G. H., Dillard, S. E., Carr, H., Pascucci, V., and hamann, B. 2007. Topology-controlled volume rendering. IEEE Trans. Visualiz. Comput. Graph. 13, 2, 330--341.
280. Weber, G. H. and Scheuermann, G. 2004. Automating transfer function design based on topology analysis. In Geometric Modeling for Scientific Visualization, G. Brunnett, B. Hamann, H. Mueller, and L. Linsen, Eds. Springer, Berlin, Germany.
281. Weber, G. H., Scheuermann, G., and Hamann, B. 2003. Detecting critical regions in scalar fields. In VISSYM '03: Proceedings of the Symposium on Data Visualisation 2003, G.-P. Bonneau, S. Hahmann, and C. D. Hansen, Eds. Association for Computing Machinery, New York, NY, 85--94.
282. Weber, G. H., Schueuermann, G., Hagen, H., and Hamann, B. 2002. Exploring scalar fields using critical isovalues. In VIS '02: Proceedings of the IEEE Visualization Conference 2002. IEEE Computer Society Press, Los Alamitos, CA, 171--178.
283. Werghi, N., Xiao, Y., and Siebert, J. P. 2006. A functional-based segmentation of human body scans in arbitrary postures. IEEE Trans. Syst. Man Cybernet.—Part B: Cybernet. 36, 1, 153--165.
284. Willard, S. 1970. General Topology. Addison-Wesley, Reading, MA.
285. Wolf, G. W. 2004. Topographic surfaces and surface networks. In Topological Data Structures for Surfaces, S. Rana, Ed. John Wiley & Sons Ltd, London, U.K., 15--29.
286. Wolter, F. 1992. Cut locus and medial axis in global shape interrogation and representation. Tech. rep. 92-2. MIT, Combridge, MA.
287. Wood, Z., Hoppe, H., Desbrun, M., and Schroeder, P. 2004. Removing excess topology from isosurfaces. ACM Trans. Graph. 23, 190--208.
288. Wood, Z. J., Desbrun, M., Schroeder, P., and Breen, D. 2000. Semi-regular mesh extraction from volumes. In VIS '02: Proceedings of the IEEE Visualization Conference 2002. IEEE Computer Society Press, Los Alamitos, CA, 275--282.
289. Xiao, Y., Siebert, P., and Werghi, N. 2003. A discrete Reeb graph approach for the segmentation of human body scans. In 3DIM 2003: Proceedings of the 4th International Conference on 3-D Digital Imaging and Modeling. IEEE Computer Society Press, Los Alamitos, CA, 378--385.
290. Yu, S., Van, M., and Snoeyink, J. 1996. Drainage queries in TINs: From local to global and back again. In Advances in GIS Research II: Proceedings of the 7th International Symposium on Spatial Data Handling. 1--14.
291. Zhang, E., Mischaikow, K., and Turk, G. 2005. Feature-based surface parameterization and texture mapping. ACM Trans. Graph. 24, 1, 1--27.
292. Zhang, X., Bajaj, C. L., and Baker, N. 2004. Fast matching of volumetric functions using multi-resolution dual contour trees. Tech. rep., Texas Institute for Computational and Applied Mathematics, Austin, TX.
293. Ziou, D. and Allili, M. 2002. Generating cubical complexes from image data and computation of the Euler number. Patt. Recog. 35, 2833--2839.
294. Zomorodian, A. 2005. Topology for Computing. Cambridge University Press, New York, NY.
295. Zomorodian, A. and Carlsson, G. 2004. Computing persistent homology. In SCG '04: Proceedings of the 20th Annual Symposium on Computational Geometry. ACM Press, New York, NY, 255--262.
296. Zomorodian, A. and Carlsson, G. 2005. Computing persistent homology. Discr. Computat. Geom. 33, 2, 249--274.
297. Zomorodian, A. and Carlsson, G. 2007. Localized homology. In SMI '07: Proceedings of the IEEE International Conference on Shape Modeling and Applications 2007. IEEE Computer Society Press, Los Alamitos, CA, 189--198.

Index Terms

• Computing methodologies

  • Computer graphics

    • Shape modeling

      • Parametric curve and surface models

      • Volumetric models