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

� 2.3 Region and super region classification

**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

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

*(P, f(p) )**~**(Q, f(Q) )**, P,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

The quotient space ** G** can be effectively coded as a graph (see figure 1), where nodes correspond to critical points of the function

����� �(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

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**£**#{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

����������������� ������

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

Figure 2. If ** S** is a surface with boundary, the number of loops of

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.

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

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

The contour levels decompose the surface into a set ** R(S)** of regions; then, each region is classified either as

Let *B _{S}(R)= B_{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.

To obtain a Reeb graph representation of an orientable surface ** S** such that

The Bolzano-Weierstrass theorem implies that, when the mapping function ** f** is at least continuous,

������������������������������� ���������������������������������������������������

�(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_{1}=m_{2}. In (c) the edge E of the polyline is classified as maximum.

Let ** M_{g}** be a maximum of

First, there are no maxima ** M_{k}** of

Second, we denote *M _{f} = max{ f(M_{k}) | f(M_{k})*

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_{1} lies between ** m�_{1}** and

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_{1}, m_{2}=AdjacentMinima(B_{i(S)}, M_{g});�� /*extraction of minima adjacent to M_{g} on B_{i(S)}*/

���������������������� /*the minima m_{1} and m_{2} satisfy the inequality f(m_{1})£f(m_{2})*/

if (m_{1}== m_{2})

�� CollapseArcs((M_{g}-m_{1}),(M_{g}-m_{2}));

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

else

�� {

�� m=VertexOnArc(M_{g}-m_{1},f(m_{2}));���� /*vertex on the arc M_{g}-m_{1} such that f(m)=f(m_{2})*/

�� Set(M_{f})=MaximaInInterval(f(M_{g})-f(m));���� /*maxima whose f value is bounded by

���������������������������������������������������������������� f(M_{g}) and f(m)*/

�� m�_{1}=VertexOnArc(M_{g}-m,f(Set(M_{f})))

�� m�_{2}=VertexOnArc(M_{g}-m_{2},f(Set(M_{f})))

�� dist=EuclideanDistance(m�_{1},m�_{2});

�� dist_sets=MaxMinDistance(m�_{1},m�_{2},Set(M_{f}))������� /*minimum distance between m�_{1},

�������������������������� m�_{2} and set of maxima Set(M_{f})*/

�� if (dist £ dist_set)

����� {

����� CollapseArcs((M_{g}-m),(M_{g}-m_{2}));

����� GeneralizeContours(B_{i(s)});��������� /* repetition on other subparts of B_{i(S)}*/

����� }������������������������������������������������������������� /* end if */

�� else

����� {

����� CollapseArcs((M_{g}-m�_{1}),(M_{g}-m�_{2}));

����� GeneralizeContours(subpart of B_{i(s)} containing m_{2});

����� GeneralizeContours(subpart of B_{i(s)} containing m_{1});

����� }������������������������������������������������������������ /*end else */

�� }��������������������������������������������������������������� /*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

In figure 5(a) an example of the pipeline of our gluing algorithm is shown. First, the maximum ** M_{g}** and the minima

����

(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_{4}** and

���

(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

- ** R** is a

- ** R** is a

- ** R** is a

- finally, ** R** is called

*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

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

Let *f:**S**�*** Â** be the a real function defined on

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