Amael Delaunoy

Ketut Fundana

Emmanuel Prados

Anders Heyden

Amaël Delaunoy

Convex Multi-Region Segmentation on Manifolds

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Image segmentation aims to partition a given image into several meaningful regions based on certain attributes such as intensity, texture, color, etc. This problem is one of the most challenging and important problems in computer vision. We address the problem of segmenting data defined on manifolds (typically a 2-surface in R 3 ) into multiple regions of piecewise constant attributes. The ability to solve such a problem offers significant new possibilities in a number of applications. For example, in 3D reconstruction (see Jin et al. [START_REF] Jin | 3-d reconstruction of shaded objects from multiple images under unknown illumination[END_REF]), a segmentation into piecewise constant data of the reconstructed surface allows to naturally introduce constraints on the material of the scene.

Global Multi-Region Segmentation

Many approaches have been proposed to solve image segmentation problems. In particular, via gradient descents, variational methods for image segmentation have had a great success, such as snakes [START_REF] Kass | Snakes: Active contour models[END_REF], geodesic active contours [START_REF] Caselles | Geodesic active contours[END_REF], geodesic active region [START_REF] Paragios | Geodesic active regions and level set methods for motion estimation and tracking[END_REF] and the Chan-Vese models [START_REF] Chan | Active contour without edges[END_REF]. Yet, the main drawback of those methods is the existence of local minima due to the non-convexity of the energy functionals. Minimizing those functionals by gradient descent methods makes the initialization critical.

To obtain global minima, some previous image segmentation works have used different optimization techniques: For example the graph-cuts in a fully discrete setting, see [START_REF] Boykov | Interactive graph cuts for optimal boundary & region segmentation of objects in n-d images[END_REF][START_REF] Kohli | Dynamic graph cuts for efficient inference in markov random fields[END_REF][START_REF] Kolmogorov | What energy functions can be minimized via graph cuts[END_REF] and the references therein. Nevertheless, while binary segmentation methods based on graph-cuts assure to get a global minima, multi-region segmentation algorithms are based on sequences of graph-cuts which cannot guarantee a global optimization.

Recently, some authors have tried to handle the problem in another direction. Instead of working on the optimization techniques in order to compute the minima of non-convex problems, they have reformulated the energy in order to get a fully convex problem [START_REF] Appleton | Globally minimal surfaces by continuous maximal flows[END_REF][START_REF] Bresson | Fast global minimization of the active contour/snake model[END_REF][START_REF] Chambolle | A convex approach for computing minimal partitions[END_REF][START_REF] Chan | Algorithms for finding global minimizers of image segmentation and denoising models[END_REF][START_REF] Lellmann | Convex multi-class image labeling by simplex-constrained total variation[END_REF][START_REF] Pock | A convex formulation of continuous multi-label problems[END_REF][START_REF] Zach | Fast global labeling for real-time stereo using multiple plane sweeps[END_REF]. These segmentation techniques are based on TV-regularizers and aim at finding characteristic functions that minimize the objective functions. Obtaining global minima becomes easy and can be done by simply performing a gradient descent. Also the initialization problem vanishes: the algorithm can start from any initialization and obtains the same result. The multi-region segmentation models proposed by [START_REF] Chambolle | A convex approach for computing minimal partitions[END_REF][START_REF] Lellmann | Convex multi-class image labeling by simplex-constrained total variation[END_REF][START_REF] Zach | Fast global labeling for real-time stereo using multiple plane sweeps[END_REF] are rather similar, the work of Pock et al. [START_REF] Pock | A convex formulation of continuous multi-label problems[END_REF] (inspired form Ishikawa's [START_REF] Ishikawa | Exact optimization for markov random fields with convex priors[END_REF]) differs from the fact that it deals with ordered labels and uses a regularization term which favors transitions between nearby labels. This makes sense in their stereo application where the ordering is due to depth, but it is not the case when we deal with independent labels. Here, we adopt the model of [START_REF] Chambolle | A convex approach for computing minimal partitions[END_REF][START_REF] Lellmann | Convex multi-class image labeling by simplex-constrained total variation[END_REF][START_REF] Zach | Fast global labeling for real-time stereo using multiple plane sweeps[END_REF] which is more appropriate to the applications we have in mind (the fact that real-life scenes are made by a finite number of independent materials, in 3D reconstruction problems) and we adapt this image labeling model to manifolds.

Data Segmentation on Manifolds

Manifolds such as surfaces are common in computer graphics as well as computer vision. Although data segmentation on surfaces has been recently used on implicit representations (see for example [START_REF] Jin | 3-d reconstruction of shaded objects from multiple images under unknown illumination[END_REF][START_REF] Krueger | Active contour based segmentation of 3d surfaces[END_REF]), explicit representations such as triangular meshes are natural and intuitive representations. Mesh representations have been widely used in 3D reconstruction, see for example [START_REF] Aganj | Spatiotemporal shape from silhouette using four-dimensional delaunay meshing[END_REF][START_REF] Delaunoy | Minimizing the multi-view stereo reprojection error for triangular surface meshes[END_REF][START_REF] Starck | Surface capture for performance based animation[END_REF], and recently in [START_REF] Aganj | Spatiotemporal shape from silhouette using four-dimensional delaunay meshing[END_REF][START_REF] Pons | Delaunay deformable models: Topology-adaptive meshes based on the restricted delaunay triangulation[END_REF][START_REF] Zaharescu | Transformesh: a topology-adaptive mesh-based approach to surface evolution[END_REF], which takes advantage of various recent evolution methods. These allow us to naturally deal with topological changes (necessary property e.g. in 3D shape estimation problems formulated within a variational framework). In a number of applications, particularly in graphics, this is the only representation one has at ones disposal. In this paper, after adapting the image segmentation model to manifolds, we show how to implement the proposed method on triangular meshes.

Mesh segmentation has been used in computer graphics to decompose meshes into significant parts, but previous work mainly focus on the geometric aspects, the choice and the representations of features to use (like the curvature). We refer to [START_REF] Attene | Mesh segmentation -a comparative study[END_REF] for a recent survey of those techniques, as in this work we focus in segmenting data on the mesh.

However, the problem of segmenting data like texture on manifolds has not received much attention until now, and is quite different from the geometric decomposition of a mesh. In [START_REF] Peyre | Surface segmentation using geodesic centroidal tesselation[END_REF], authors take into account both texture information and curvature, but their approach is based on a fast marching algorithm, which needs to be initialized using initial points. Moreover as their segmentation method is not convex, different regions sharing the same properties may result in different labels. The same problem also occurs in [START_REF] Page | Perceptionbased 3d triangle mesh segmentation using fast marching watersheds[END_REF], where watershed filtering was used. Contrary to those methods, the approach we propose is global and robust to initialization.

Finally, let us note that the segmentation model we consider is based on a total variation regularization. Although this regularization has been previously used on implicit sur-faces (see [START_REF] Bertalmio | Variational problems and pdes on implicit surfaces[END_REF] with applications to texture synthesis), it has not received much attention in Lagrangian methods. In the finite elements literature, one can find some papers dealing with the Laplace-Beltrami operator ∇ S • ∇ S u which corresponds to the gradient of the squared regularization term S |∇ S u| 2 dσ (see for example [START_REF] Demlow | An adaptive finite element method for the laplace-beltrami operator on implicitly defined surfaces[END_REF][START_REF] Dziuk | Finite elements for the beltrami operator on arbitrary surfaces[END_REF]). To our knowledge there does not exist work dealing with the gradient of the total variation in this framework. Let us note here that the Laplace-Beltrami operator is linear while the term associated with the gradient of the total variation ∇ S • ∇ S u |∇ S u| is nonlinear. Moreover, the theoretical analysis and the numerical algorithms of [START_REF] Demlow | An adaptive finite element method for the laplace-beltrami operator on implicitly defined surfaces[END_REF][START_REF] Dziuk | Finite elements for the beltrami operator on arbitrary surfaces[END_REF] are completely based on this linearity property.

Contributions

First, we adapt the image convex model of [START_REF] Bresson | Fast global minimization of the active contour/snake model[END_REF][START_REF] Chambolle | A convex approach for computing minimal partitions[END_REF][START_REF] Chan | Algorithms for finding global minimizers of image segmentation and denoising models[END_REF][START_REF] Lellmann | Convex multi-class image labeling by simplex-constrained total variation[END_REF][START_REF] Zach | Fast global labeling for real-time stereo using multiple plane sweeps[END_REF] to manifolds. Then we show how to implement the method when the manifold is represented by a triangular mesh. Finally, we explain how our multi-region segmentation method could be incorporated into potential computer vision applications such as 3D reconstruction.

Multi-Region Segmentation Model

In this section, we describe the convex image segmentation model we propose. To make this model comprehensible and intuitive, let us first remind of the region-based active contour model of Chan and Vese [START_REF] Chan | Active contour without edges[END_REF]. Here we show that the energy functional of Chan and Vese, which is the piecewise constant case of the Mumford-Shah model ( [START_REF] Mumford | Optimal approximations by piecewise smooth functions and variational problems[END_REF]), can be recast as a convex functional in order to find the global minimizer of the original energy functional.

Convex Two-Phases Model

The Chan-Vese model [START_REF] Chan | Active contour without edges[END_REF], which is formulated in the level set framework, partition a given image into two subregions. For a given image I, the idea is to find a subset Σ of a bounded domain Ω ⊂ R N , whose boundary ∂Σ is represented by the zero level set of function φ : Ω → R N . This is done by minimizing the energy functional

min φ,c1,c2 Ω H ǫ (φ)(I(w) -c 1 ) 2 + (1 -H ǫ (φ))(I(w) -c 2 ) 2 + λ |∇H ǫ (φ)| dω , (1)
where λ ∈ R, c 1 , c 2 ∈ R and H ǫ is a regularized Heaviside function, which models a characteristic function (see [START_REF] Chan | Active contour without edges[END_REF]).

Since the energy functional (1) is not convex, minimizing it by gradient descent methods can get stuck in local minima. By relaxing the characteristic function H ǫ (φ) by an arbitrary function u bounded between 0 and 1, Chan et al. [START_REF] Chan | Algorithms for finding global minimizers of image segmentation and denoising models[END_REF] showed that minimizing (1) can be rewritten as the following convex minimization problem:

min 0≤u≤1 Ω u(w)(I(w) -c 1 ) 2 + (1 -u(w))(I(w) -c 2 ) 2 dω + λ Ω |∇u| dω , (2)
c 1 and c 2 being fixed, in R. As proved in [START_REF] Bresson | Fast global minimization of the active contour/snake model[END_REF][START_REF] Chan | Algorithms for finding global minimizers of image segmentation and denoising models[END_REF], if u(x) is a minimizer of (2), then for a.e. µ ∈ [0, 1], the set Σ(µ) = {x ∈ Ω, u(x) > µ} is a minimizer of the Mumford-Shah functional [START_REF] Mumford | Optimal approximations by piecewise smooth functions and variational problems[END_REF], implying that the solution to ( 1) can be obtained by thresholding u at any arbitrary threshold between 0 and 1.

Extension to Multi-Region Segmentation

Recently, several authors [START_REF] Chambolle | A convex approach for computing minimal partitions[END_REF][START_REF] Lellmann | Convex multi-class image labeling by simplex-constrained total variation[END_REF][START_REF] Zach | Fast global labeling for real-time stereo using multiple plane sweeps[END_REF] have extended the convex formulation (2) to multi-region segmentation:

min u∈K Ω < u(w), s(w) > + λ |∇u(w)| dω , (3)

Multi-Region Segmentation on Manifolds

In this section we extend the multi-region convex model (3) on a manifold, and we show how to optimize the associated energy for a manifold represented by a mesh. To our best knowledge, these convex formulations (2,3) have been defined only on open subsets of R N which correspond to image domains, as described in the previous section.

Let S be a Riemannian manifold. Typically, S could be a smooth 2D surface of R 3 . Energy (3) is adapted as follows:

min u∈K S < u(x), s(x) > + λ|∇ S u(x)| dσ , (4)
where now the functions u are defined on S instead of Ω, |.| is the Riemannian norm, ∇ S is the intrinsic gradient on S and dσ is the manifold's element measure (surface's area measure for 2D manifolds). Now, let us consider a manifold represented by a mesh. The following results apply to manifolds with any topology. Let X be a (piecewise linear) polyhedron representation of the surface S, defined by a set of vertices x k : X = {x k } and let l be the cardinality of X (the number of vertices). As in the finite elements literature, we define φ k : S → R as the piecewise affine, interpolating basis function such that φ k (x k ) = 1 and φ k (x i ) = 0 if i = k. The vector valued field U = {u k } is defined on all vertices x of the polyhedron X. U can be naturally extended on S by a piecewise affine vector valued field on S. We denote this extension u(x) = k u k φ k (x). To make the paper easier to read and because of space limitations, we assume that the manifold is a 2D surface of R 3 . However, the following method applies to any dimension. Let S j be the j th triangle of the mesh. The multi-region segmentation energy can then be rewritten as

j k u k , Sj φ k (x)s(x)dσ + λ Sj |∇ S u(x)|dσ, ( 5
)
where u is constrained to be in K. The first term of ( 5) is explicitly written with respect to U. In order to make the total variation term explicit with respect to U, we first consider a local paramtrization (α, β) on the manifold. Following [START_REF] Do | Differential Geometry of Curves and Surfaces[END_REF][START_REF] Jin | Estimation of 3d surface shape and smooth radiance from 2d images: A level set approach[END_REF], we rewrite the right term of Equation ( 5) using fundamental forms:

∇ S u = ∂x ∂α ∂x ∂β E F F G -1 u α u β
, and then

|∇ S u| = u α u β E F F G -1 u α u β , where E = ∂x ∂α • ∂x ∂α , F = ∂x ∂α • ∂x ∂β and G = ∂x ∂β
• ∂x ∂β are coefficients of the first fundamental form (see [START_REF] Do | Differential Geometry of Curves and Surfaces[END_REF][START_REF] Jin | Estimation of 3d surface shape and smooth radiance from 2d images: A level set approach[END_REF]). u α and u β are partial derivatives of u with respects to α and β respectively. Considering the mesh representation, we parametrize the triangle S j by x(α, β) = x j,1 + α -----→

x j,1 x j,2 + β -----→ x j,1 x j,3 where x j,1 , x j,2 and x j,3 are the three vertices associated with the triangle S j and where

(α, β) ∈ T = {(α, β)|α ∈ [0, 1] and β ∈ [0, 1 -α]}. We then have Sj |∇ S u(x)|dσ = T p u p 2 α G -2u p α • u p β F + u p 2 β E dαdβ . ( 6
)
u p α and u p β are partial derivatives of u p with respects to α and β respectively. Here the reader will easily verify that E, F, G, u p α and u p β are constant functions on S j and that their respective values are equal to

E j = |x j,2 -x j,1 | 2 , F j =< x j,2 -x j,1 , x j,3 -x j,1 >, G j = |x j,3 -x j,1 | 2 , u p j α = u j, 2
pu j,1 p and u p j β = u j,3 pu j,1 p , where u j,1 , u j,2 and u j,3 are the values of u at vertices x j,1 , x j,2 and x j,3 respectively. Now the term inside the integral of (6) does not depend on α and β. The convex multi-region segmentation energy on the meshed manifold becomes:

E(U) = j k u k , Sj φ k (x)s(x)dσ + λ 2 j p u p j α 2 G j -2u p j α • u p j β F j + u p j β 2 E j . (7)

Optimization Method

When the (surface) manifold is represented by a mesh, the convex multi-region segmentation model then leads to optimizing the convex energy [START_REF] Bresson | Fast global minimization of the active contour/snake model[END_REF] with respect to U ∈ R l×m , with the convex constraint U ∈ K; K being the set {U s.t. ∀k, p u kp = 1 and ∀p, u kp ≥ 0}. This convex constrained optimization problem on R l×m can be solved by the projected gradient method [START_REF] Boyd | Convex Optimization[END_REF], which consists in generating the sequence U t via

U t+1 = P roj K (U t -τ ∇E(U t )) , (8)
for a fixed time step τ > 0, until |U t -U t-1 | ∞ ≤ δ, a small constant. P roj K is the projection on the convex set K. In other words, we iteratively process gradient descent steps and projections of the u k on the set K. These projections can be done via Michelot's algorithm [START_REF] Michelot | A finite algorithm for finding the projection of a point onto the canonical simplex of rn[END_REF]. From energy [START_REF] Bresson | Fast global minimization of the active contour/snake model[END_REF] we easily obtain

∂E ∂u k p (U) = X j∈N (k) " Z S j φ k (x)s(x)dσ # p - λ 2 Q (ξ+ǫ) -1 2 , (9)
where Q = (u j,2 p -u kp )(G j -F j )+(u j,3 p -u kp )(E j -F j ), ξ is the term in the squared root of (7), and N (k) is the 1ring neighborhood of vertex k. As in [START_REF] Chan | Algorithms for finding global minimizers of image segmentation and denoising models[END_REF], we regularize the term ξ by incorporating a small value ǫ inside the squared root to avoid instabilities when the gradient of u is 0.

Let us remind now that, as underlined by [START_REF] Eckstein | Generalized surface flows for mesh processing[END_REF], the notion of gradient depends on the underlying scalar product. If we chose the pointwise scalar product < U, V > pw = k < u k , v k >, then the components of ∇E(U t ) directly coincide with ∂E ∂u k p (U). Nevertheless the associate pointwise metric is not efficient for minimizing energies of the form S f (u(x)) dσ since the distance between two discrete fields U and V does not take into account the area of the triangle. On the other hand, the L 2 scalar product < U, V > L 2 = S < u(x), v(x) > dσ is much more relevant. Also in this case the gradient becomes

∇E(U) = M -1 ∂E ∂U (U) , (10)
where the matrix M is the mass matrix defined by M ij = Id m S φ i (x)φ j (x) dσ. Moreover one classically approximates M by the diagonal mass lumping M , where Mii is the area of the Voronoi dual cell of x i times the identity matrix Id m , see e.g. [START_REF] Eckstein | Generalized surface flows for mesh processing[END_REF].

Applications

In the previous sections the data term of the segmentation model s is assumed to be known (Equation 4). In the applications, this term also depends on some parameters that have to be optimized. The convex problem can be solved by alternating optimization of the parameters in a bi-convex way. For fixed parameters of s we update u and vice-versa. u is updated according to the method presented in section 3.1. In practice we update the parameters of s every r update iterations of u (r is chosen arbitrary; we fix r = 10 in our experiments).

Piecewise Constant Data Segmentation

Let us consider the case where the data we want to segment are assumed to be piecewise constant. Here a natural expression for s p (x) is to use the squared error between the scalar or vector-valued data C(x) at the point x and the value µ p associated with the label p (µ p having the same dimension as the data):

s p (x) = (C(x) -µ p ) T (C(x) -µ p ) .
The optimization of the energy (4) with respect to µ p gives:

µ p = S u p (x) C(x)dσ S u p (x)dσ
, which corresponds to the mean value of the data of the associated region. Note that the previous model can be easily extended to any probablility density function D p . For example, D p can be a multivariate gaussian density function of mean µ p and covariance Σ p , and then we would have:

s p (x) = -ln(D p (x, µ p , Σ p )) , with D p (x, µ p , Σ p ) = 1 m √ 2π|Σ| e -1 2 (C(x)-µp) T Σ -1 p (C(x)-µp) .
Segmentation in 3D Reconstruction Problems Such segmentation framework can be incorporated in 3D Reconstruction applications. In such applications, it can be interesting to segment a particular region, or all parts of the surface sharing the same reflectance properties. In 3D reconstruction, most of the variational methods yield to minimizing an energy of the form

E(S) = i S g(x) x i • n x 3 i,z ν S (x) dσ , ( 11
)
see for example [START_REF] Delaunoy | Minimizing the multi-view stereo reprojection error for triangular surface meshes[END_REF][START_REF] Jin | 3-d reconstruction of shaded objects from multiple images under unknown illumination[END_REF][START_REF] Jin | Estimation of 3d surface shape and smooth radiance from 2d images: A level set approach[END_REF]. Moreover, if we choose

g(x) = m p=1 u p (x)(I i (π i (x)) -µ p ) T (I i (π i (x)) -µ p ) ,
where π i (x) is the projection of the surface point x into the i th image and I i : w → I i (w) is the function which associates to each pixel w, its color on the i th image. We then get an extension of the stereoscopic segmentation method proposed by [START_REF] Yezzi | Stereoscopic segmentation[END_REF] to the case where the surface is composed of more than two regions of piecewise constant radiance. Also, contrary to our method, the segmentation approach proposed in [START_REF] Yezzi | Stereoscopic segmentation[END_REF] is subject to local minima. Finally, the optimization of the energy (4) with respect to µ p gives:

µp = R S up(x) P i Ii(πi(x)) x • n x 3 z νS,i(x)dσ R S up(x) P i x • n x 3 z νS,i(x)dσ . If we chose g(x) = m X p=1 up(x)(Ii(πi(x)) -ρpN(x) • L) T (Ii(πi(x)) -ρpN(x) • L),
where N(x) is the normal to the surface at the point x and L is the vector corresponding to the light source illuminating the scene, then we get an extension of the (Lambertian) multi-view shape from shading method proposed by [START_REF] Jin | 3-d reconstruction of shaded objects from multiple images under unknown illumination[END_REF] for surfaces with piecewise constant albedo. In the same way, contrary to our approach, the method proposed by [START_REF] Jin | 3-d reconstruction of shaded objects from multiple images under unknown illumination[END_REF] is limited to two regions segmentation and is strongly subject to local minima. The optimization of energy ( 4) with respect to the albedo gives:

ρp = R S up(x) P i Ii(πi(x))N(x) • L x • n x 3 z νS,i(x)dσ R S up(x)(N(x) • L) 2 P i x • n x 3 z νS,i(x)dσ
.

The theoretical and experimental study of these algorithms will be the topic a forthcoming paper.

Experiments

In order to validate the proposed multi-region segmentation approach on meshes, we present different experiments on synthetic as well as realistic data. In practice as explained in previous section, the segmentation is solved by alternating between region parameters and the segmentation variable U, with a known number of regions. The algorithm complexity is linearly dependent on the number of facets and the number of classes. Experiments have been runned on a 2.66GHz linux machine and take about 20 seconds on a mesh of 200,000 facets and for a 4 regions segmentation. The values of λ have been manually chosen in each example but a value of 0.01 gives reasonnable results in most cases.

The Two Region Case

Figures 2 and3 show examples of our algorithm using a synthetic image mapped onto a mesh for the Stanford bunny model. Noise has been added to the image. Here, we show that our algorithm performs well on the given example and that the final solution is binary. Moreover it is and µ 2 are inverted and the solution u as well. In this example, geodesic active contours or level sets methods would tend to the closest local minima from the initialization as the texture is not clearly binary. Nevertheless, as the method is global here, segmenting a particular region should be done using additional cues. timated during the process as described before, and the parameters λ can be adjusted to add more smoothness to the segmentation. As shown by experiments, even though the initialization is random and the parameters of each region are computed during the evolution, the algorithm still converges to the desired solution as a binary solution.

Dealing with Multiple Regions

Here we show the efficiency of the proposed method when dealing with multiple regions. Different examples are shown, first with synthetic textures on which noise has been added, and then on meshes textured by real-world images like previous examples. Note that the number of regions is initially given and is not automatically estimated. In Figure 5, the experiment shows noisy texture on meshes, the segmentation result using K-Means, and the result of our TV-based algorithm on meshes. Because the K-Means algorithm does not take into account the spatial coherence of points, the result is noisy. On the other hand, the TV regularization allows coherence in the scene and the segmentation is close to the expected solution. In addition to be robust to initialization, our approach is robust to noise.

We then tested our multi-region segmentation approach on various data from real-world images [START_REF] Martin | A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics[END_REF], see Figure 6. Let us emphasize here that the initialization was random and the number of regions was initially given.

As an example, we applied our approach to segment mean curvature on a mesh using three different regions. Figure 7 shows that we are able to segment some concave and convex parts of the mesh.

Finally, in Figure 8, we show the examples of a 3D mesh obtained by 3D reconstruction algorithms, as the one in [START_REF] Starck | Surface capture for performance based animation[END_REF][START_REF] Zaharescu | Transformesh: a topology-adaptive mesh-based approach to surface evolution[END_REF]. The last row shows the obtained color-based labeling (into three regions). Even though the texture is far from being binary, the segmentation is the expected one. For instance in the result, we nicely recover the skin, the pant and the shirt. Here again, initialization was random.

For comparison of the convex image multi-region segmentation model (3) with other methods, we refer to [START_REF] Lellmann | Convex multi-class image labeling by simplex-constrained total variation[END_REF] which shows quantitative and qualitative comparisons with belief propagation, sequential belief propagation, graph cuts with alpha-expansion, graph cuts with alpha-beta swap and sequential tree reweighted belief propagation methods. The experiments show that the generated labeling is comparable to state-of-the-art discrete optimization methods.

Conclusions

In this paper we propose a variational method for segmenting data on manifolds into regions of constant properties. The convex formulation makes the proposed model robust to initialization. Moreover, the total variation regularizer makes the method robust to noise. We show how to implement the method, in particular how to compute the gradient of the total variation term, when the surface has a discrete representation as triangular meshes. We have demonstrated the efficiency of our method by testing it on various synthetic and realistic data from computer vision applications.

Figure 1 :

 1 Figure 1: Example of segmentation on a manifold. (a) The Input textured surface. (b) The triangular representation of the surface with the retrieved contour (in red). (c) Surface colored with the mean values of the segmented regions (and surface shading).

  where K is the set of function u : Ω → R m such that for all w ∈ Ω and p ∈ [1..m], u p (w) ≥ 0 and m p=1 u p (w) = 1. |∇u(w)| corresponds to p |∇u p (w)| 2 , where |.| denotes the L 2 norm. m denotes the number of labels and s(w) is an m-dimensional vector; s p (w) indicates the affinity of the data at point w with class p. The convex domain naturally allow direct competition between the labeling.

Figure 2 :

 2 Figure 2: Segmentation result on the synthesized Stanford bunny surface. (a) Input shaded object. (b) Input mesh with synthetic texture mapping. (c) Input textured mesh (shaded visualization) and final contour (in red).

Figure 3 :

 3 Figure 3: The evolution on the synthesized bunny surface. Different initialization of U (first row); Intermediate values of U (second row); The obtained solution U (third row); The obtained mean values (fourth row) with shading.

Figure 4 Figure 4 :

 44 Figure 4 present segmented surfaces from real-world textures that have been mapped onto a mesh, in the case of the two-phases segmentation. We show different examples from classical images used in segmentation. Note that the segmentation is done on the mesh using the method described in this paper and not on an image. The experiments show three different non binary images and their segmentation into two different regions. As expected the results are binary even though the initial values of the segments are random values. The mean values of each region is es-

Figure 5 :

 5 Figure 5: Segmentation results on meshes in the multi-region case on synthesized examples inspired from [24]. (a) Input textured mesh (same shape as previous Butterfly and Horses data). (b) Clustering using K-Means algorithm. (c) Recovered mean values of each region obtained by our approach.

Figure 8 :

 8 Figure 8: Segmentation result on a colored mesh obtained by multiview stereo algorithm. Front view (top row) and back view (bottom row). Original input colored mesh and the associated 3D shape (left). Result of the segmentation into three regions obtained by our algorithm (middle). Recovered mean values displayed for each region (right).

Figure 6 :

 6 Figure 6: Segmentation results on meshes in the multi-region case. Top row: Horse data set and its segmentation for three regions. Bottom row: Four regions labeling of the Butterfly data. (a) Input textured mesh; (b) Recovered mean values of each region obtained by our approach; (c) One of the segmented regions.

Figure 7 :

 7 Figure 7: Segmentation results on mesh curvature in 3 regions. (a) Input mesh. (b) Mean Curvature visualization. (c) Simple thresholding of the mean curvature. (d) Segmentation result of the mean curvature into three regions with our approach.

Acknowledgements

Amaël Delaunoy and Emmanuel Prados were supported by the Flamenco project ANR-06-MDCA-007, and Ketut Fundana and Anders Heyden were funded by the VISION-TRAIN RTN CT-2004-005439 Marie Curie Action within the EC's Sixth Framework Programme. We thank Andrei Zaharescu and Adrian Hilton for sharing the dancer data with the Perception group.