Silvia Biasotti
silvia@ima.ge.cnr.it
Istituto per la Matematica Applicata
Consiglio Nazionale delle Ricerche
Genova / Italy
KEYWORDS: shape graph, discrete critical point analysis.
Topology as the study of shape properties that do not change under deformation, gives a formal framework for the formalisation and solution of several problems related to shape and shape understanding. From this point of view, it is interesting to investigate the possible role of the new field of computational topology, firstly introduced in [2] and followed by [3,], for incorporating abstraction mechanisms in shape modelling.
Shape abstraction tools are necessary to catch the uniqueness properties which identify shapes independently of their particular geometry because similar shapes may occur in a variety of geometrical instances. Differential topology and geometry have been often used for surface coding: tools such as the Euler's equation, surface networks, Morse theory or the Reeb are examples of techniques and measures with an extremely high abstraction power. Applications of these tools have been studied by Nackmann, Pfaltz, Shinagawa, Kunii [5,,].
In this paper we present the description of an highlevel abstraction model for the representation and the manipulation of threedimensional surfaces. Such a model adapts and extends to the discrete domain the basic concepts related to Reeb graphs. Then the resulting representation guarantees the computational efficiency and an effective topological coding of the object allowing a qualitative quick comparison among objects. Research on the use of such a graph for terrain representation has been presented in [8,9] aimed at the definition of innovative, effective and efficient algorithms for understanding, compression and restoration purposes. The proposed extension does not distort the semantic meaning of the Reeb graph and faithfully represent the surface morphology [10]. Moreover the proposed model has been successfully extended to three dimensional closed surfaces represented by triangulation [11].
The reminder of this paper is organised as follows: first, we present some approaches to differential topology, critical points and topological graphs in the computer graphics community; then, basic results of Morse theory and Reeb graph are introduced. In section 4 the ERG representation and some examples of its application are given; in the final section conclusion and future work are drawn.
The main difficulty in the application of topologybased tools is the necessity of adapting concepts developed for smooth manifold to surface models which are only continuos as in the case of triangulated surfaces. Several authors have underlined the importance of these tools in different applications: under the assumption that critical points are nondegenerate, Nackman, [5], proposed an interesting method for coding the critical points of smooth Morse functions of two variables in a Critical Point Graph (CPG). For geographical applications Pfaltz studied a similar approach for discrete surfaces defining the socalled surface networks, [6]. Surface network, moreover, have bee, used by Bajaj, [16] for driving the simplification of meshes while preserving the topology of the shape. Falcidieno and Spagnuolo, [17], defined a curvaturebased graph corresponding to a subdivision of the surface in simpler shaped subregions.
Major research on the use of topology for surface description has been proposed by Kunii, Shinagawa et al., [7,14], where a surface coding based on Morse theory and Reeb graphs has been defined. Such a kind of model describes a manifold surface by considering the evolution of the surface sections; in practice this model is particular efficient to evidence the topological structure of the surface and to allow a better quote recognition. The resulting conceptual sketch simplifies the topological analysis, it is based on only few elements and it can be associated to reconstruction or generation rules which allow to restoring the original surface. Another method to reconstruct surfaces from contours has been defined from Giertsen et al., [18]; the topological information of this structure can be more efficiently expressed by the Reeb graph, which allows to univocally code contour connectivity and adjacency relationship among sections. Moreover, starting from the notion of Reeb graph in [8] we proposed a topological structure, called ERG, available for surface simplification and reconstruction (for details on the ERG see section 4).
Formally, let f be a real function defined on a manifold M and p = p(x, y, z) a point of M; then the relationship grad(f(p)) = 0 defines a critical point of the function f.
The topological type of the immersed portion of the manifold changes after the critical points are dunked. To define the topological type of a critical point we require it is nondegenerate, that is the Hessian matrix of f is nonsingular at that point (the Hessian matrix is the matrix of the partial second derivatives of the function f). In particular a function f is called Morse if all its critical points are nondegenerate.
An intuitively good function to study the surface shape is the height function, that is the real function which associates to each point on the surface its elevation. If the function f is Morse the type of the topological changes on the surface are determined by the type of the critical points, which is given by the number of negative eigenvalues of its Hessian. According to the number of negative eigenvalues of the Hessian the nondegenerate critical points of a surface define the 0, 1, 2cells. In this way it is possible to extract a topological graph based on points, edges and faces called in algebraic topology as the CWcomplex, [12]. An important result of Morse theory, which establishes a link between the number of critical points and the topological type of the manifold, is given by the Euler formula: # minima  # saddles + # maxima = 2(1g) = c(M) where g represents the genus of the surface. In particular, the entity c(M) is called Euler characteristic of the manifold M.
Let f:M ® R be a real valued function on a compact manifold M. The Reeb graph of M wrt f is the quotient space of MxR defined by the relation ÔÔ @ ÕÕ, given by:

The Reeb graph is a CPG graph: in fact the Morse theory guarantees that the surface topology changes only in correspondence of critical points, that is in the graph representation the nodes correspond to critical points and the arcs are given by the part of surface between two critical levels. Moreover, under the assumption that the height function is Morse, the structure of the Reeb graph is rather simple and represents the topological skeleton of the object. For its properties the Reeb graph ensure an efficient topological control in the compression and simplification problems. In figure 1 the Reeb graph of a bitorus is shown, in this image the mapping function is the natural height function.
The possible definitions of discrete critical points, however, generally suffer of instability in the sense that small perturbations of the vertex coordinates may result in rather different configurations [23,]. Regarding that, it is necessary to adapt the traditional surface shape classification to polyedral surfaces extending, where it is possible, the usual definition of critical point. This is a well known problem in the computer graphics community but it was not univocally resolved yet. Our proposal is to describe a topological graph, we called Extended Reeb Graph (ERG). Such a graph derives from the direct application of the Reeb graph to degenerate as well as nonsimple height functions and keeps the same meaningful properties. The extension proposed relates also the critical area definition and it is coherent with the common idea of critical point. In this manner the analysis of complex handmade articles is allowed even if characterised from multiple flat areas.
The ERG representation for 2.5D surfaces represented by triangular meshes, for example digital terrains, has been fully described in [10,23], and an extension of the method to closed threedimensional surfaces (i.e. without boundary) has been introduces in [11].
The innovation of our method is both the way of constructing the graph and the efficiency in dealing with degenerate situations. The proposed approach is actually not an extension of the Reeb graph itself, but rather a full application of its definition in the discrete domain, which does not require the height function to be Morse. The main idea is to consider critical areas instead of critical points and identify, starting from them, the smallest area on the mesh whose behaviour is topologically equivalent to the critical area (influence zone). Starting from a triangulated surface constrained to the contour levels generally critical areas are localized by flat regions. The classification of critical areas as maxima, minima and saddles is done by checking the number of nonconstrained edges in the boundary and analysing the ascending/descending direction of the surface across the boundary, (for details in the classification see [10]). Since we do not require the height function to be Morse we admit multiplycritical areas as volcano rims. Multiplyconnected critical areas divide the surface in an external and, at least, an internal part and are further classified as complex minima, maxima and saddles respectively. In particular, our definition of critical areas still satisfied an extended version of the Euler formula presented in 3.1, for details see [9].
The concept of critical area is not able to fully describe the topologicl behaviour of the surface around saddles, so we have introduced the notion of influence zone of a critical area (see [10,11,23]). Influence zones are the starting points to identify the portion of the mesh which defines the arcs of the ERG and are defined as the smallest areas of the surface having the same topological behaviour as the critical areas (the extended definition of influence zone can be found in [11]). In particular the influence zone of a saddle area is composed by the whole part of the surface contained in the nearest contours (generally at least 3) to the critical area itself. In figure 2(a) we depict the critical areas of a bitorus while in 2(b) the influence zones are shown, in particular the influence zones of saddle areas detect the region of the triangulation where the topology changes.
Figure 2: The critical areas (a) and the influence zones (b) of a triangulated bitorus.
The components of the ERG are defined as follows: nodes correspond to the influence zones of simple critical areas and macronodes are used to represent complex critical areas. Finally, the ERG arcs encode the topological adjacency among influence zones and are detected using an expanding process as described in [11]. In figure 3 an example of the ERG extraction for a natural surface and the simplified model built considering only the critical sections are shown. In figure 4 we show the ERG represention of a threedimensional object: a teapot, in particular in 4(a) the influence zone of the critical areas are highlighted.
(a) (b)
Figure 3: The ERG representation of a real surface (a) and the simplified triangulation: the topology of the two models is the same.
(a) (b)
Figure 4: The influence zones of a tea pot and its ERG, (a): in (b) the relations among the critical sections are depicted
Another possible application of the proposed model could be the study of the metamorphosis (morphing) of objects. This application field needs a model that gets out a rapid topological detection, classifies the common shape features and preserves the lowlevel geometrical information. Such a representation has to allow the transformation and modification directly on the model and give an effective theoretical support. In fact, morphing is a technique used for the evolution and metamorphosis analysis from one image to another. The idea is to get a sequence of intermediate configurations which when put together with the original surface would represent the change from one to the other. This technique has been developed for study both the object evolution (for instance to analyse a sequence of face expressions) and the transformation between different entities. One of the most time consuming tasks in morphing is selecting the points or lines in the initial and final image so that the metamorphosis is smooth and natural and it is not trivial problem to identify which edge should be mapped to which other edge (for details see [27,26]). The interpolation between two shapes can produce forms covering a variety of topological types, that is the topology of intermediate models can be different from the original ones. To investigate the maintenance of the topology when performing a shape transformation shape recognition tools are essential and in this context our representation model could be useful both in shape recognition and in evolution metamorphosis process.