Title of Your Paper

Topological coding of surfaces with boundary using Reeb graphs

Silvia Biasotti
Istituto di Matematica Applicata e Tecnologie Informatiche � Sez. di Genova
Consiglio Nazionale delle Ricerche - Italy

This paper is supposed to be viewed, using Internet Explorer version 5.0 (or any later version). Other browsers may give incorrect representations of the content.

Contents

� Abstract

� 1. Introduction

� 2. Shape representation

� 2.1 Region extraction

� 2.2 Super region extraction

� 2.3 Region and super region classification

� 3. Graph representation

� 4. Examples and discussion

� 5. Conclusions

� Acknowledgements

� References

Abstract

Morse theory provides the theoretical framework for defining several shape descriptors related to the evolution on the surface of its contour levels. For example, the Reeb graph gives a conceptual sketch of the surface, which can be used to transmit/code abstract descriptions of the whole data set and to compose the object signatures instead of the whole models. In this paper, the basic concepts related to Reeb graphs are adapted and extended to generic surfaces with boundary.

Keywords: Reeb graph, surface characterisation, shape analysis

1. Introduction

Due to the conciseness of the Reeb graph description, such a representation has been extensively applied to several application contexts such as shape understanding [1,6], similarity estimation [4], database retrieval [7,15] and model representation [8,9,16]. An overview on the effectiveness of Reeb graph representations in shape modelling has been proposed in [10].

Definition 1 (Reeb quotient space): Let S be a surface and f:S�Â be a real mapping function associated to S, the quotient space G=S/~ defined by the equivalence relation �~�:

(P, f(p) ) ~ (Q, f(Q) ), P,Q Î S iff� f(P)=f(Q)

P,Q are in the same connected component of f ^�1(f(P))

is called the Reeb graph of S with respect to the mapping function f.

The quotient space G can be effectively coded as a graph (see figure 1), where nodes correspond to critical points of the function f, while arcs represent the connections between them, for details see [1,4,5]. In particular, the Reeb graph is topologically equivalent to the original shape and the flexibility of the choice of the function f makes the Reeb graph adaptable to different application contents. Details on its implementation and the computational complexity can be found in [10].

�� (a)�� (b)

Figure 1. Dotted ellipses in (a) are contour levels of f, while the continuous lines show a possible representation of the quotient space G. The Reeb graph representation of a bitorus is shown in (b).

Until now, most of methods for representing the Reeb graph structure mainly focused on the representation of closed surfaces [1,4,8,9,] or terrain-like models [2,11], where the Reeb graph is also referred as contour tree [11,12]. Furthermore, since terrain surfaces have only one boundary component that may be flattened, the Reeb graph can be always defined by adding a global minimum that virtually closes the surface and makes that homeomorphic to a sphere.

Things are slightly different when generic surfaces with boundary are considered. From a mathematical point of view it is known that, when f is a continuous map, the number of loops of G is an upper bound of the number of loops of S. In fact, the projection prj_R:S �G is also continuous and the fundamental group pushes forward; that is, there is a map prj*_R:p₁(S) � p₁(G) defined by taking the image of loops from S. Moreover, denoting g the genus of an orientable surface S having b_S boundary components and #{loops} the number of loops of G, when the function f is Morse, the following relations hold:

g £ #{loops} £ 2g + b_S - 1

see [5] for details.

This fact implies that the number of loops of G may change by varying the function f, for example mapping a surface along different height directions like in figure 2; therefore, when surfaces with boundary are considered, the characteristic of the Reeb graph of representing the genus of the surface independently of the mapping function is not any longer satisfied. The Reeb graph representation of generic 2-manifold surfaces with boundary has been firstly proposed in [5]. Such an approach substantially extended the construction of the contour tree presented in [11]; therefore it required that the function f is Morse and no critical points and vertices on the boundary may assume the same value of f, [13]. These hypotheses may become a limit when the Reeb graph representation is applied to discrete models affected by noise and/or uncertainty.

��

(a)�� (b)�� (c)�� (d)

Figure 2. If S is a surface with boundary, the number of loops of G wrt the height function f may depend on the object position. In case of a torus with two boundaries, the Reeb graph representation admits two cycles, at most.

In our previous work [1,2] we described a method for computing a discrete representation of the Reeb graph of triangle meshes representing either a 2D scalar field or a closed manifold. In this paper we detail the approach introduced in [16] for representing the Reeb graph structure of triangle meshes with boundary, providing also the pseudo-code of the key points of our method. In particular, our approach is able to characterize mapping functions that are continuous but not differentiable and admits also boundary components that are polygonal curves. In addition, this paper describes a two level representation that codes both an extension of the classical Reeb graph structure (ERG) and a so-called Extended Reeb Super-graph (ERS) that highlights the genus of the surface.

The reminder of the paper is organized as follows. First, our characterisation method is adapted to a generic surface with boundary. Second, our two level graph representation is detailed. Then, results are presented and possible choices of the function f are discussed. Conclusive remarks and suggestions on future work end the paper.

2. Shape representation

In this section, we briefly discuss how to extend the representation method proposed in [1,2,17] to generic surfaces with boundary both in terms of characterisation and extraction algorithm.

Our idea is to organize the Reeb graph representation on two levels: first, the evolution of the level sets is stored obtaining a description analogous to [5]. Second, another representation, which is topologically coherent with the genus of the surface S, is obtained by virtually closing the boundary components. The second phase of the algorithm is based on the classification theorem of surfaces that claims that the topological type of an orientable, compact, connected surface with boundary depends on the number of its boundary components and on the genus of the surface S* obtained by gluing a disc onto each boundary component, [14]. Thus, the most intuitive idea for highlighting the topological type of S is to construct a closed model by physically filling each boundary component. Unfortunately, even if the operation of closing the boundary components is theoretically always possible, there are surfaces, such as the Seifert's surfaces, that do not admit such a filling without any self-intersection in the usual three dimensional space. Furthermore, since there are several ways of closing a boundary component, several artefacts could be introduced in the model during the filling phase. Founding upon these considerations, our approach virtually closes S without physically altering the model.

2.1 Region extraction

Our approach to surface characterization analyses the evolution of a set of contour levels C(S) as proposed in [1,2], where a region-oriented rather than a point-oriented classification of the behaviour of S was considered.

The contour levels decompose the surface into a set R(S) of regions; then, each region is classified either as regular or critical, the latter being a maximum, a minimum or a saddle. In case of surfaces with boundary the classification is achieved in two steps: first, all regions are detected and classified. Second, regions that belong to the same boundary component and assume the same value of f are virtually grouped in the so-called super-regions.

Let B_S(R)= B₁ È B₂ È � È B_n be the border of a region R Î R(S) and n the number of its connected components, where a connected component of B_S(R) is either a closed contour or a polygonal line, that is a line whose end-points belong to the surface boundary. Each region R of S is classified according to the number of its border components and outgoing directions, which are classified as ascending or descending according to the behaviour of f across the corresponding border component as explained in [1].

In our implementation, the contour levels C(S) are inserted as constraints in the triangle mesh and the edges belonging to them are defined constrained. The following C pseudo-code describes the extraction of a surface region:

ExtractRegion(TIN,R)

�{�� /* input: TIN, a triangle mesh; output R, a region*/

R=InitRegion(t);�� /*the region is initialised with a generic triangle*/

while(there are non-visited triangles adjacent to R through a non-constrained edge)

� {

� AddTriangle(R,t)�� /* add a new triangle to the region R */

� MarkTriangle(R,t);�� /* mark the triangle t as visited */

� }

� DetectBoundaryRegion(R);�� /* detection of the boundary components of R */

� ClassifyRegion(R);�� /*the region is classified regular or critical*/

�� /*according to criteria described in section 2.3 */

� if (!critical)

�� RemoveFromList(R);�� /* triangles of R are still marked as visited*/

}

Therefore, the region extraction procedure is repeated until there are triangles that have not been visited, yet. With reference to figure 3(a,b) surface regions correspond to model portions bounded by contours and boundary components, if any.

2.2 Super-region extraction

To obtain a Reeb graph representation of an orientable surface S such that #{loops of G}=g=#{handles of S}, a further region classification that simulates the virtual closing of each boundary component, is accomplished. Our algorithm for the closure of a boundary component modifies the approach proposed in [5]. Main step of such an extension is the virtual union of the contour end points belonging on same boundary component. Analogously to [5], maxima and minima of f along each boundary component are detected and end-points of contour levels that belong to the different portions of the same boundary component are collapsed. In figure 3 the contour levels with respect to f are depicted on a sphere with one boundary component; while circles highlight the end points of contours and dashed lines represent its virtual closure.

The Bolzano-Weierstrass theorem implies that, when the mapping function f is at least continuous, f assumes on each boundary component B_i(S) of S at least a maximum and a minimum value, both on the surface S and its boundary. Moreover, if the restriction of f to B_S is Morse, the boundary sequentially alternates a maximum and a minimum point; therefore each maximum is adjacent to two minima at most and vice-versa. Nevertheless a similar behaviour is verified also when a boundary component is a polyline, that is a piece-wise linear curve composed by a sequence of edges that are joined along their end points. In fact, in this case, non isolated maxima and minima like in figure 3(c) may be considered as a single point and classified according to the behaviour of f around them.

��

�(a)�� (b)�� (c)

Figure 3 Virtual closure of a boundary component (a,b). Black circles indicate the critical points with respect to the height function. In (b) m₁=m₂. In (c) the edge E of the polyline is classified as maximum.

Let M_g be a maximum of f assumed on a boundary component B_i(S) of S and m₁, m₂ the two minima adjacent to M_g on B_i(S) such that f(m₁) £ f(m₂), m₁ and m₂ may also overlap. Denoting m the point on the arc (M_g,m₁) such that f(m)=f(m₂) two cases are distinguished.

First, there are no maxima M_k of B_i(S) such that f(M_k) Î [f(m), f(M)]. This implies that m₁ and m₂ coincide because m₂ is a minimum and, on B_i(S), maxima and minima are sequentially alternated. In this case we virtually connect all end-points on the arcs (M_g ,m) and (M_g, m₂) that belong on the opposite side of B_i(S) and have same value of f, as shown in figure 3(b).

Second, we denote M_f = max{ f(M_k) | f(M_k) Î [f(m),f(M_g)] }; in particular, we observe that the set Set(M_f) of the maxima having value M_f may consist of several points and, if m₁¹ m₂, Set(M_f) is not empty. Let m'₁ and m'₂ be the points on the arcs (M_g, m) and (M_g,m₂), respectively, such that f(m'₁)=f(m'₂)=M_f. If the Euclidean distance between m'₁ and m'₂� (Euclid(m�₁,m�₂)) is less than that between the same points and the Set(M_f), the arcs (M_g ,m) and (M_g, m₂) are collapsed; in practice such a control should determine if the critical points of the boundary behave like in figure 4(b). Otherwise (see figure 4(a)), we connect the end-points that belong to the arcs (M_g,m'₁) and (M_g,m'₂) with same value of f; while the remaining part of B_i(S) that does not contain M_g is split into the sub-parts induced by the points of Set(M_f).

Finally, such a gluing process is repeated separately for the other sub-parts of B_i(S), until the virtual correspondence among all contour end-points has been established.

(a)�� (b)

Figure 4. Possible configurations of two boundary components. In (a) the maximum M₁ lies between m�₁ and m�₂, therefore Euclid(m�₁,m�₂)³{Euclid(m�₁,M₁),Euclid(M₁,m�₂)}. Then, the arcs (M,m�₁) and (M,m�₂) will be connected and the reminder of the boundary splits. On the contrary, when the Euclidean distance between m�₁ and m�₂ is less that the other, like in the case (b), the arcs (M,m) and (M,m₂) may be collapsed.

An example of the pseudo-code for the detection of the generalized contours is proposed in the following:

GeneralizeContours(B_i(s))

�� /* input: B_i(s), a boundary component of S; output: virtual closure of B_i(s)*/

{

CharacterizeBoundary(B_i(S));�� /* maximum and minimum detection on B_i(S)*/

M_g=MaximumVertex(B_i(S));�� /* vertex having the highest value of f */

m₁, m₂=AdjacentMinima(B_i(S), M_g);�� /*extraction of minima adjacent to M_g on B_i(S)*/

�� /*the minima m₁ and m₂ satisfy the inequality f(m₁)£f(m₂)*/

if (m₁== m₂)

�� CollapseArcs((M_g-m₁),(M_g-m₂));

�� /* the contour end points lying on the two arcs are identified */

else

�� {

�� m=VertexOnArc(M_g-m₁,f(m₂));�� /*vertex on the arc M_g-m₁ such that f(m)=f(m₂)*/

�� Set(M_f)=MaximaInInterval(f(M_g)-f(m));�� /*maxima whose f value is bounded by

�� f(M_g) and f(m)*/

�� m�₁=VertexOnArc(M_g-m,f(Set(M_f)))

�� m�₂=VertexOnArc(M_g-m₂,f(Set(M_f)))

�� dist=EuclideanDistance(m�₁,m�₂);

�� dist_sets=MaxMinDistance(m�₁,m�₂,Set(M_f))�� /*minimum distance between m�₁,

�� m�₂ and set of maxima Set(M_f)*/

�� if (dist £ dist_set)

�� {

�� CollapseArcs((M_g-m),(M_g-m₂));

�� GeneralizeContours(B_i(s));�� /* repetition on other subparts of B_i(S)*/

�� }�� /* end if */

�� else

�� {

�� CollapseArcs((M_g-m�₁),(M_g-m�₂));

�� GeneralizeContours(subpart of B_i(s) containing m₂);

�� GeneralizeContours(subpart of B_i(s) containing m₁);

�� }�� /*end else */

� }

Once two arcs have been collapsed, the function �GeneralizeContours� is recursively applied to the remaining subparts of B_i(S). Finally, the extraction of the generalized contours ends when such a procedure is applied to each boundary component B_i(S) of S.

In figure 5(a) an example of the pipeline of our gluing algorithm is shown. First, the maximum M_g and the minima m₁ and m₂ of B_S are considered. Since f(M₁) ³ f(m₂) the points m'₁ and m'₂ are detected. Since the distance between m'₁ and m'₂ is less than the distance between m'₁ and M_1, the arcs (M_g,m) and (M_g,m₂) are glued (see figure 5(c)). Once the points m and m₂ have been identified, the maximum M₁ is selected. Then, the maximum M₂ generates a further split of the arcs (M₁,m₄) and (M₁,m₇) introducing the points m₅ and m₆ (figure 4(d)). Analogously, M₂ lies between m₅ and m₆. In this case the two arcs (M₁,m₅) and (M₁,m₆) glue together and the remainder portion of B_S is split in two subparts. Finally, the arcs (m₅,m₁) and (m₁,M2) are connected; similarly, (M₂,m₇) and (m₇,m₆) do (see figure 4(e)). The correspondence between the boundary portions is shown associating the same colour to arcs that are glued together; in particular, in figure 5(c,d) the line between m₁ and m₂ denotes that these vertices have been identified and (M₁,m₅) will become an arc.

��

(a)�� (b)�� (c)�� (d)�� (e)

Figure 5 Sequence of steps for virtually closing a boundary component using our method.

In figure 6(d) we show a possible boundary decomposition induced by the method proposed in [5]. There, arcs between minima and maxima of a boundary component are connected without considering if other critical values lie on the interval of values they span. In particular, once the points m₄ and m₅ have been identified, the arcs (M_g,m₄) and (M_g,m₃) are glued; similarly (m₃,M₁) and (M₁,m₅) do; finally, the pair (m₄,m₁) and (m₅,m₂) is connected and, analogously, the arcs (M₂,m₁) and (M₂,m₂) do.

��

(a)�� (b)�� (c)�� (d)

Figure 6. Virtual correspondence using the criteria in [5].

As a result of our gluing algorithm, contours with end points on same boundary component are virtually closed and we refer to them as generalized contours.

2.3 Region and super region classification

In this section it is described our surface regions classification. Such a classification mainly depends on the number of border components of a region and the behaviour locally around its border. Given a region R, we will denote B_S(R) its border and n the number of its border components; then, the following classification scheme is adopted:

- R is a maximum area iff all the outgoing directions from B_S(R) are descending;

- R is a minimum area iff all the outgoing directions from B_S(R) are ascending;

- R is a saddle area iff n>2 and there are both ascending and descending outgoing directions from B_S(R);

- finally, R is called regular iff does not belong to the previous categories.

Super regions are extracted gluing the regions whose image is in the same interval of values of f and share at least one generalized contour. Considering the generalized contours instead of the contour levels, the resulting super regions are further classified using the criteria proposed for regions. Therefore the algorithm for the extraction of the super regions works analogously to the method proposed in section 2.1.To what the outgoing directions of a generalized contour are concerned, they are still classified ascending or descending according to the behaviour of the function f of along its contour levels. The set of super regions is denoted by SR(S) and, analogously to R(S), they provide a full partition of the surface S.

3. Graph representation

The generalized characterization just described may be coded in a graph simply extending the equivalence relation used in the Reeb graph. The equivalence notion we are introducing may be applied not only to the region decomposition R(S), but to the super region segmentation SR(S) too.

Let f: S � Â be the a real function defined on S, and let [f_min,f_max] be an interval containing the domain of f on the surface S, and f_min < f₁ < � < f_np < f_max the distribution of the values of the contour levels C(S) of S as proposed in [2]. In addition, let I={(f_min, f₁), (f_i, f_i+1), i=1, � , np-1, (f_np, f_max)} È {f_min, f₁, � ,f_np, f_max} be the partition of the interval [f_min, f_max] provided by the function values of the contour levels and its np+1 interior parts.

Definition 2: An extended Reeb equivalence between two points P, Q