Abderrahim Elmoataz
email: abder.elmoataz@greyc.ensicaen.fr

Olivier Lezoray
email: olivier.lezoray@unicaen.fr@se

Sébastien Bougleux
email: bastien.bougleux@greyc.ensicaen.fr

Nonlocal Discrete Regularization on Weighted Graphs: a Framework for Image and Manifold Processing

Keywords: Nonlocal discrete regularization, Weighted graph, p-Laplacian, Image and manifold processing

We introduce a nonlocal discrete regularization framework on weighted graphs of the arbitrary topologies for image and manifold processing. The approach considers the problem as a variational one, which consists in minimizing a weighted sum of two energy terms: a regularization one that uses a discrete weighted p-Dirichlet energy, and an approximation one. This is the discrete analogue of recent continuous Euclidean nonlocal regularization functionals. The proposed formulation leads to a family of simple and fast nonlinear processing methods based on the weighted p-Laplace operator, parameterized by the degree p of regularity, the graph structure and the graph weight function. These discrete processing methods provide a graph-based version of recently proposed semi-local or nonlocal processing methods used in image and mesh processing, such as the bilateral filter, the TV digital filter or the nonlocal means filter. It works with equal ease on regular 2D-3D images, manifolds or any data. We illustrate the abilities of the approach by applying it to various types of images, meshes, manifolds and data represented as graphs.

I. INTRODUCTION

I N many computer science applications, it is necessary to process images, meshes, manifolds and more generally data. This refers to the following research fields: image processing, computer graphics and data mining. In the context of image processing, smoothing and denoising are key filtering processes. Among the existing methods, the variational ones, based on regularization, provide a general framework to design such efficient filter processes. Solutions of variational models can be obtained by minimizing appropriate energy functions. The minimization is usually performed by designing continuous Partial Differential Equations (PDE), whose solutions are discretized in order to fit with the image domain. A complete overview of these methods can be found in [START_REF] Buades | A review of image denoising algorithms, with a new one[END_REF], [START_REF] Chan | Image Processing and Analysis -variational, PDE, wavelets, and stochastic methods[END_REF], [START_REF] Tsai | Total variation and level set methods in image science[END_REF], [START_REF] Alvarez | Axioms and fundamental equations of image processing[END_REF] and references therein. In the context of mesh processing, smoothing and denoising are also key processes dedicated to noise removal causing minimal damage to geometric features. Most mesh smoothing methods are based on the discrete Laplace-Beltrami regularization or on the discrete curvature regularization [START_REF] Taubin | Geometric signal processing on polygonal meshes[END_REF], [START_REF] Ohtake | Mesh regularization and adaptive smoothing[END_REF]. Other smoothing methods, based on feature preserving were mostly inspired by anisotropic diffusion in image processing [START_REF] Desbrun | Anisotropic featurepreserving denoising of height fields and bivariate data[END_REF], [START_REF] Bajaj | Anisotropic diffusion of surfaces and functions on surfaces[END_REF], [START_REF] Hildebrandt | Anisotropic filtering of non-linear surface features[END_REF]. Geometric flows have been extensively used in mesh processing [START_REF] Eckstein | Generalized surface flows for mesh processing[END_REF]. In particular, surface flows based on functional minimization (i.e. evolving a surface so as to progressively decrease an energy functional) is a common methodology in geometric processing with applications to spanning surface diffusion [START_REF] Taubin | A signal processing approach to fair surface design[END_REF], denoising of scanned meshes [START_REF] Desbrun | Implicit fairing of irregular meshes using diffusion and curvature flow[END_REF], shape optimization and surface design [START_REF] Xu | Discrete surface modelling using partial differential equations[END_REF], minimal surfaces [START_REF] Pinkall | Computing discrete minimal surfaces and their conjugates[END_REF], etc.

In the context of manifold and data processing, dimensionality reduction [START_REF] Belkin | Laplacian eigenmaps for dimensionality reduction and data representation[END_REF], [START_REF] Lafon | Data fusion and multicue data matching by diffusion maps[END_REF], [START_REF] Lafon | Diffusion maps and coarse-graining: A unified framework for dimensionality reduction, graph partitioning and data set parameterization[END_REF] (extracting low dimensional structure from high dimensional data), clustering [START_REF] Luxburg | A tutorial on spectral clustering[END_REF], [START_REF] Shi | Normalized cuts and image segmentation[END_REF] (automatic identification of groups of similar objects) and classification [START_REF] Belkin | Regularization and semisupervised learning on large graphs[END_REF], [START_REF] Zhou | A regularization framework for learning from graph data[END_REF], [START_REF] Smola | Kernels and regularization on graphs[END_REF] (assigning labels to instances) are key processes. In particular, methods based on graph Laplacian have became increasingly popular in machine learning to perform any of the above-mentioned key processes. However, manifolds and discrete data, as images and meshes, can also contain inner noise. Therefore, regularization occurs as a natural candidate for manifold processing [START_REF] Peyré | Manifold models for signals and images[END_REF], [START_REF] Szlam | A general framework for adaptive regularization based on diffusion processes on graphs[END_REF] since e.g. noise filtering can be useful to avoid overfitting in a learning process. Manifold regularization denotes also a family of learning algorithms [START_REF] Belkin | Regularization and semisupervised learning on large graphs[END_REF] based on regularization with both labeled and unlabeled data. Transductive graph learning algorithms and standard methods like Support Vector Machines [START_REF] Smola | Kernels and regularization on graphs[END_REF] can then be considered as special cases of manifold regularization. All these methods are based on the assumption that the data lies on a submanifold. However, sampled data lies almost never exactly on the submanifold due to the noise scattered around it. Since most previous methods are sensitive to noise, it is essential to denoise the manifold data to project it onto a submanifold [START_REF] Hein | Manifold denoising[END_REF]. As we have just mentioned, regularization is a principle the interest of which concerns a wide range of computer science domains. The application of partial and variational methods to images, meshes, manifolds and any discrete data processing has shown its effectiveness allowing high quality regularization processes. However, there are some limitations to the functionals used in regularization such as total variational ones [START_REF] Chan | Image Processing and Analysis -variational, PDE, wavelets, and stochastic methods[END_REF]. Indeed, the latter are based on derivatives which consider local features of the data. Since the advent of the nonlocal means filter [START_REF] Buades | A review of image denoising algorithms, with a new one[END_REF], the use of nonlocal interactions, to capture the complex structure of the data, has received a lot of interest and has shown to be very effective. A variational understanding of the nonlocal means filter was first developed in [START_REF] Kindermann | Deblurring and denoising of images by nonlocal functionals[END_REF] as a non convex functional and later in [START_REF] Gilboa | Nonlocal linear image regularization and supervised segmentation[END_REF], [START_REF]Nonlocal operators with applications to image processing[END_REF] as a convex quadratic functional. Moreover, the use of manifolds to describe nonlocal interactions of geometric structures in signals and images has recently been explored [START_REF] Peyré | Manifold models for signals and images[END_REF]. In this latter work, diffusion over these manifolds is shown to be equivalent to nonlocal processing methods. However, most of these variational nonlocal formulations are expressed in a continuous setting and unfortunately the discretization of the underlying differential operators is difficult for high dimensional data.

Moreover, whatever the origin of the data (images or data bases), a common representation can be used to model them: graphs. For the particular case of images, pixels have a specific organization expressed by their spatial connectivity. Therefore, a typical graph used to represent images is a grid graph. For the particular case of unorganized data, a graph can also be associated with by modeling neighborhood relationships between the data elements. As a consequence, by using the same adapted underlying graph representation to model data with a given organization (images) or without any (general data bases), one can define a framework which can be used to process general data bases. We take that point of view of processing any data ranging from images to manifolds.

Inspired by continuous regularization of images and recent works on nonlocal functional for continous regularization, we propose a general framework extending our previous works [START_REF] Lezoray | Graph regularization for color image processing[END_REF], [START_REF] Bougleux | Discrete regularization on weighted graphs for image and mesh filtering[END_REF], [START_REF] Lezoray | Parameterless discrete regularization on graphs for color image filtering[END_REF], [START_REF] Ta | Graphs regularization for data sets and images: Filtering and semi-supervised classification[END_REF] based on a nonlocal discrete regularization on weighted graphs of the arbitrary topologies. This framework can also be considered as a discrete analogue of the nonlocal continuous regularization for the case of images [START_REF] Gilboa | Nonlocal convex functionals for image regularization[END_REF], [START_REF] Gilboa | Nonlocal linear image regularization and supervised segmentation[END_REF]. Furthermore, the proposed framework works on any discrete data represented by weighted graphs which enables a nonlocal regularization with equal ease on images and manifolds. Our approach starts directly with a discrete variational problem and works with data living on any general discrete domain. To take into account the nonlocal interactions in images and manifolds, we explicitly introduce discrete nonlocal derivatives and functionals on graphs of the arbitrary topologies, to transcribe the continuous regularization. This framework unifies the regularization of images, meshes, manifolds and data. The latter regularization enables local, semi-local or nonlocal regularization by using appropriate graphs topologies and edges weights. Let G = (V, E, w) be a weighted graph consisting in a set of vertices V , a set of edges E ⊂ V × V , and a similarity weight function w defined on edges. Let H(V ) be a Hilbert space defined on the vertices of G. We formalize the discrete data regularization of a function f 0 ∈ H(V ) by the following minimization problem:

min f ∈H(V ) E p w (f, f 0 , λ) = 1 p v∈V |∇ w f (v)| p + λ 2 f -f 0 2 2 ,
(1) where p ∈ (0, +∞) is the smoothness degree, λ is the fidelity parameter, and |∇ w f | represents the weighted local variation of the function f over the graph. The solution of problem (1) leads to a family of nonlinear processing methods, parameterized by the weight function, the degree of smoothness, and the fidelity parameter. There exists two main advantages of using this framework, which can be considered as a discrete analogue of continuous regularization on weighted graphs.

First, the regularization is expressed directly in a discrete setting. Involved processing methods are computed by simple and efficient iterative algorithms, without solving any PDEs. Second, the topology of graphs can be arbitrary. Since the proposed approach is general, any discrete data set can be transformed into a weighted graph, by using a similarity measure between data features. Thus, we can consider any function defined on these data as a function defined on the graph vertices.

The regularization term in problem ( 1) is obtained by defining nonlocal functionals on weighted graphs. The idea of using functionals on graphs, in a regularization process, has also been proposed in other contexts, such as semi-supervised data learning [START_REF] Zhou | Regularization on discrete spaces[END_REF], [START_REF]Discrete regularization[END_REF] and image segmentation [START_REF] Bougleux | Image smoothing and segmentation by graph regularization[END_REF]. In this paper, we introduce a large family of regularization problems based on the p-Laplacian which is the discrete analogue of the wellknown Euclidean p-Laplacian to graphs. This leads to a family of discrete linear and nonlinear filters which includes and extends several well-known models used in image processing for the classical cases of p = 2 or p = 1. The case of p < 1 is also considered in this paper. Moreover, the proposed framework naturally embeds local to nonlocal processing. To summarize, the proposed regularization framework on graphs unifies several existing discrete image filters, generalizes them and extends them to the processing of arbitrary data.

In this paper, we first define functionals on weighted graphs in Section II. Section III presents the discrete regularization problem [START_REF] Buades | A review of image denoising algorithms, with a new one[END_REF], and the associated filter family. Section IV analyzes the obtained filters and gives relations to existing methods. In Section V, we show some regularization examples, in the context of images, meshes, manifolds and data processing. Last Section concludes.

II. OPERATORS ON WEIGHTED GRAPHS

In this Section, we recall some basic definitions on graphs, and we define nonlocal functionals which can be considered as discrete versions of continuous differential operators. Analogous definitions and properties have also been used in the context of semi-supervised learning [START_REF] Zhou | Regularization on discrete spaces[END_REF], and differential calculus on graphs [START_REF] Bensoussan | Difference equations on weighted graphs[END_REF], [START_REF] Friedman | Wave equations for graphs and the edgebased laplacian[END_REF].

A. Preliminary Notations and Definitions

A weighted graph G = (V, E, w) consists in a finite set V = {v 1 , . . . , v N } of N vertices and a finite set E ⊂ V × V of weighted edges. We assume G to be undirected, with no self-loops and no multiple edges. Let (u, v) be the edge that connects vertices u and v of V , the weight of which is denoted by w(u, v). Edges weights represent similarities between vertices. They are usually computed by using a function w :

V × V → R + which satisfies, w(u, v) = w(v, u) for all (u, v) ∈ E (symmetric), and w(u, v) = 0 if (u, v) ∈ E.
We use the notation u ∼ v for two adjacent vertices. We say that G is connected whenever, for any pair of vertices (u, v) there is a finite sequence u 0 = u, u 1 , . . . , u n = v such that u i-1 is a neighbor of u i for every i ∈ {1, . . . , n}.

Let H(V ) denote the Hilbert space of real-valued functions on the vertices of a graph. A function f : V → R of H(V ) assigns a real value f (v) to each vertex v ∈ V . Clearly, the function f can be represented by a column vector of R N : f = [f (v 1 ), . . . , f (v N )] T . By analogy with functional analysis on continuous spaces, the integral of a function f ∈ H(V ), over the set of vertices V , is defined as V f = V f . The space H(V ) is endowed with the usual inner product f, h

H(V ) = v∈V f (v)h(v), where f, h : V → R.
Similarly, let H(E) be the space of real-valued functions defined on the edges of a graph G. It is endowed with the inner product F, H

H(E) = (u,v)∈E F (u, v)H(u, v) = u∈V v∼u F (u, v)H(u, v),
where F, H : E → R are two functions of H(E).

B. Difference Operator and its Adjoint

Let G = (V, E, w) be a weighted graph, and let f : V → R be a function of H(V ). The difference operator of f , noted d : H(V ) → H(E), is defined on an edge (u, v) ∈ E by:

(df )(u, v) = w(u, v)(f (v) -f (u)). (2)
The directional derivative (or edge derivative) of f , at a vertex v ∈ V , along an edge e = (u, v), is defined as:

∂f ∂e u = ∂ v f (u) = (df )(u, v). (3)
One can remark that this last definition is consistent with the continuous definition of the derivative of a function:

∂ v f (u) = -∂ u f (v), ∂ v f (v) = 0, and if f (v) = f (u) then ∂ v f (u) = 0.
The adjoint of the difference operator, noted d * : H(E) → H(V ), is a linear operator defined by:

df, H H(E) = f, d * H H(V ) , (4)
for any function H ∈ H(E) and function f ∈ H(V ). Proposition 1: The adjoint operator d * , of a function H ∈ H(E), can by expressed at a vertex u ∈ V by the following expression:

(d * H)(u) = v∼u w(u, v)(H(v, u) -H(u, v)). (5)
Proof: By using the definition of the inner product in H(E), the left term of (4) is rewritten as:

df, H H(E) = X (u,v)∈E (df )(u, v)H(u, v) (2) = X (u,v)∈E p w(u, v)(f (v) -f (u))H(u, v) = X (u,v)∈E p w(u, v)f (v)H(u, v) - X (u,v)∈E p w(u, v)f (u)H(u, v) = X u∈V X v∼u p w(u, v)f (u)H(v, u) - X u∈V X v∼u p w(u, v)f (u)H(u, v) = X u∈V f (u) X v∼u p w(u, v)(H(v, u) -H(u, v)) (4) = f, d * H = X u∈V f (u)(d * H)(u).
The proof is completed by comparing the last two last equations.

The divergence operator, defined by -d * , measures the network outflow of a function in H(E), at each vertex of the graph.

Proposition 2: Each function H ∈ H(E) has a null divergence over the entire set of vertices:

u∈V (d * H)(v) = 0. (6)
Proof: From Proposition 1, ( 6) is the sum of terms

w(v, u)(H(v, u)-H(u, v))+ w(u, v)(H(u, v)-H(v, u)).
Since w is symmetric, then this sum is null. It is worth noting that the difference operator proposed by Zhou [START_REF] Zhou | Regularization on discrete spaces[END_REF] is not zero over constant functions (also pointed out by Hein in [START_REF] Hein | Convergece of graph Laplacians on random neighborhood graphs[END_REF]); moreover, it and does not satisfy the null divergence property.

C. Gradient Operator

The weighted gradient operator of a function f ∈ H(V ), at a vertex u ∈ V , is the column vector defined by:

∇ w f (u) = (∂ v f (u) : v ∼ u) T = (∂ v1 f (u), . . . , ∂ v k f (u)) T , ∀(u, v i ) ∈ E.
The L 2 -norm of this vector represents the local variation of the function f at a vertex of the graph. It is defined by:

|∇ w f (u)| = v∼u (∂ v f (u)) 2 (3) = v∼u w(u, v)(f (v) -f (u)) 2 . ( 7
)
One can remark that the local variation is a seminorm. It can be viewed as a measure of the regularity of a function around a vertex.

D. A Family of Weighted p-Laplace Operators

Let p ∈ (0, +∞) be a real number. The weighted p-Laplace

operator of a function f ∈ H(V ), noted ∆ p w : H(V ) → H(V ), is defined by: ∆ p w f = 1 2 d * (|∇ w f | p-2 df ). (8)
Proposition 3: The p-Laplace operator of f ∈ H(V ), at a vertex u ∈ V , can be computed by:

∆ p w f (u) = 1 2 v∼u γ f w (u, v)(f (u) -f (v)), (9)
with

γ f w (u, v) = w(u, v)(| w f (v)| p-2 + | w f (u)| p-2 ). ( 10
)
Proof: From ( 8), ( 5) and ( 2), we have:

∆ p w f (u) = 1 2 v∼u w(u, v) (df )(v, u) | w f (v)| 2-p - (df )(u, v) | w f (u)| 2-p = 1 2 v∼u w(u, v) f (u) -f (v) | w f (v)| 2-p - f (v) -f (u)) | w f (u)| 2-p .
This last term is exactly [START_REF] Hildebrandt | Anisotropic filtering of non-linear surface features[END_REF]. The p-Laplace operator is nonlinear, with the exception of p = 2. In this last case, it corresponds to the combinatorial graph Laplacian, which is one of the classical second order operators defined in the context of spectral graph theory [START_REF] Chung | Spectral graph theory[END_REF]:

∆ w f (u) = v∼u w(u, v)(f (u) -f (v)). (11)
Another particular case of the p-Laplace operator is the curvature of the function f at each vertex of the graph, which is obtained with p = 1 (originally defined on unweighted graphs in [START_REF] Osher | Digitized PDE method for data restoration[END_REF], [START_REF] Chan | The digital TV filter and nonlinear denoising[END_REF]):

κ w f (u) = 1 2 v∼u 1 | w f (v)| + 1 | w f (u)| (f (u) -f (v)).
(12) This is the discrete analogue of the mean curvature of the level curve of a function defined on a continuous domain of R n . This is explained by the following general property, which is a rewriting of Proposition 3.

Corollary 1: The p-Laplace operator of a function f ∈ H(V ) can be expressed, at a vertex u ∈ V , as:

∆ p w f (u) = 1 2 v∼u e=(u,v) ∂ ∂e | w f | p-2 ∂f ∂e u . ( 13
)
Proof: We show that ( 13) is equivalent to [START_REF] Hildebrandt | Anisotropic filtering of non-linear surface features[END_REF]. From (3), the right term of ( 13) is equal to:

1 2 X v∼u e=(u,v) p w(u, v) " | w f (v)| p-2 ∂f ∂e ˛v -| w f (u)| p-2 ∂f ∂e ˛u«
By using (3) again, we obtain exactly the first equation of the proof of Proposition 3, which completes the proof. Then, the p-Laplace operator (9) can be seen as an extension of ∆ w and κ w . In practice, to avoid zero denominator in [START_REF] Desbrun | Implicit fairing of irregular meshes using diffusion and curvature flow[END_REF], the local variation ( 7) is replaced by its regularized version:

|∇ w f (v)| = |∇ w f (v)| 2 + 2
, where → 0 is a fixed small constant [START_REF] Chan | The digital TV filter and nonlinear denoising[END_REF].

III. p-LAPLACE REGULARIZATION ON WEIGHTED GRAPHS

Let f 0 : V → R be a given function defined on the vertices of a weighted graph G = (V, E, w). In a given application context, the function f 0 represents an observation of a clean set of data g : V → R corrupted by a given noise n such that f 0 = g + n. Such noise is assumed to have zero mean and variance σ 2 , which usually corresponds to measure or observation errors.

To recover the uncorrupted fonction g, a commonly used method is to seek for a function f : V → R which is smooth enough on G, and also close enough to f 0 . This inverse problem can be formalized by the minimization of an energy functional, which typically involves a regularization term plus an approximation term (also called fitting term). In this paper, we propose to consider the following variational problem:

g ≈ min f :V →R E p w (f, f 0 , λ) = R p w (f ) + λ 2 f -f 0 2 2 , ( 14
)
where the regularization functional R p w :

H(V ) → R is the discrete p-Dirichlet form of a function f ∈ H(V ), on the weighted graph G: R p w (f ) = 1 p u∈V |∇ w f (u)| p (7) = 1 p u∈V v∼u w(u, v)(f (v) -f (u)) 2 p 2 . ( 15
)
The trade-off between the two competing terms in the functional E p w , is specified by the fidelity parameter λ ≥ 0. By varying the value of λ, the variational problem [START_REF] Pinkall | Computing discrete minimal surfaces and their conjugates[END_REF] allows to describe the function f 0 at different scales (each scale corresponding to a value of λ).

The degree of regularity, which has to be preserved, is controlled by the value of p. The proposed minimizer ( 14) can be seen as an extension of the two classical cases of p = 2 or p = 1. In the sequel, we discuss the existence of its solution, then we show that the solution is based on the p-Laplace operator; and we give an iterative algorithm to approximate it.

A. Existence of the Solution and Regularization Equations

When p ≥ 1, the energy E p w of minimizer ( 14) is a convex functional of functions in H(V ). As we have E p w (f, f 0 , λ) → +∞ when f → +∞, by standard arguments in convex analysis, there exists a global minimum for the minimizer [START_REF] Pinkall | Computing discrete minimal surfaces and their conjugates[END_REF]. Then, any local minimum of

E p w is a global minimum of E p w . Let C(V ) be the set of constant functions f : V → R, such that f (u) = c for all u ∈ V , c ∈ R. So, E p
w is also a strickly convex functional of functions in H(V )\C(V ). In this is case, the minimization of E p w has a unique solution. This is also the case for the functions in C(V ). Indeed, R p w is translation invariant, e.g. R p w (f + c) = R p w (f ) for all c ∈ R, and there exists only one global minimum.

To get the solution of the minimizer ( 14), we consider the following system of equations:

∂E p w (f, f 0 , λ) ∂f (u) = 0, ∀u ∈ V, (16)
which is rewritten as:

∂R p w (f ) ∂f (u) + λ(f (u) -f 0 (u)) = 0, ∀u ∈ V. ( 17
)
If this system has a solution, then it is the solution of ( 14). When p < 1, R p w is non-convex, and the global minimization solution is not insured. However, this case is also considered in the following, in order to analyze the behavior of the associated diffusion processes beyond the usual bound p = 1.

The solution of the system ( 17) is computed by using the following property.

Proposition 4: Let f be a function in H(V ). Then,

∂R p w (f ) ∂f (u) = 2∆ p w f (u), ∀u ∈ V. (18)
Proof: Let u 1 be a vertex of V . From ( 15), the u 1 -th term of the derivative of R p w (f ) is given by:

∂R p w (f ) ∂f (u 1 ) = 1 p ∂ ∂f (u 1 )   u∈V v∼u w(u, v)(f (v) -f (u)) 2 p 2   (19)
The partial derivative depends only on the edges incident to u 1 . Let v 1 , . . . , v k be the vertices of V connected to u 1 by an edge of E. Then, using the chain rule, we have:

(19) = - v∼u1 w u1v (f (v) -f (u 1 ))| w f (u 1 )| p-2 + w v1u1 (f (u 1 ) -f (v 1 ))| w f (v 1 )| p-2 + . . . + w v k u1 (f (u 1 ) -f (v k ))| w f (v k )| p-2 ,
which is equal to:

v∼u1 w u1v (f (u 1 ) -f (v))(| w f (u 1 )| p-2 + | w f (v)| p-2 ).
From [START_REF] Hildebrandt | Anisotropic filtering of non-linear surface features[END_REF], this last term is exactly 2∆ p w f (u 1 ). By using Proposition 4, the system ( 17) is rewritten as:

2∆ p w f (u) + λ(f (u) -f 0 (u)) = 0, ∀u ∈ V, (20)
which is equivalent to the following system of algebraic equations (see Proposition 3):

λ + v∼u γ f w (u, v) f (u) - v∼u γ f w (u, v)f (v) = λf 0 (u). (21)
This can be considered as the discrete Euler-Lagrange equation associated with the minimization problem [START_REF] Pinkall | Computing discrete minimal surfaces and their conjugates[END_REF]. Contrary to the continuous case, it does not involve any PDEs. To get its solution, several methods can be used, depending on the value of the regularity parameter p. In the linear case (p = 2), iterative methods such as the Gauss-Jacobi method, or the infinitesimal steepest descent method, converge efficiently to the solution of (20).

B. A Family of Discrete Diffusion Processes

We propose to use the linearized Gauss-Jacobi iterative method to solve the regularization equation [START_REF] Zhou | A regularization framework for learning from graph data[END_REF]. Let t be an iteration step, and let f (t) be the solution at the step t. The method is given by the following algorithm:

     f (0) = f 0 f (t+1) (u) = λf 0 (u) + v∼u γ f (t) w (u, v)f (t) (v) λ + v∼u γ f (t) w (u, v)
, ∀u ∈ V.

(22) It describes a family of discrete diffusion processes, which is parameterized by the structure of the graph, the edges weights, the parameter p, and the parameter λ. A classical stopping criterion f (t+1) -f (t) < is considered where is a fixed small constant.

These processes can be interpreted as forced lowpass filters on graphs. Let ϕ f w be the filter coefficients defined by:

         ϕ f w (u, v) = γ f w (u, v) λ + v∼u γ f w (u, v) , if u = v ϕ f w (u, u) = λ λ + v∼u γ f w (u, v) , otherwise. (23)
Then, the regularization algorithm ( 22) is rewritten as:

   f (0) = f 0 f (t+1) (u) = ϕ f (t) w (u, u)f 0 (u) + v∼u ϕ f (t) w (u, v)f (t) (v).
(24) One can remark that ϕ f w satisfies the following properties:

           ϕ f w (u, u) ≥ 0, ∀u ∈ V v∼u ϕ f w (u, v) ≥ 0, ∀u ∈ V ϕ f w (u, u) + v∼u ϕ f w (u, v) = 1, ∀u ∈ V. (25)
At each iteration of the algorithm [START_REF] Szlam | A general framework for adaptive regularization based on diffusion processes on graphs[END_REF], the new value f (t+1) (u) depends on two quantities: the original value f 0 (u), and a weighted average of the filtered values of f (t) in the neighborhood of u. Proposition 5: For all p ∈ [1, +∞), if the algorithm [START_REF] Smola | Kernels and regularization on graphs[END_REF], or equivalently [START_REF] Szlam | A general framework for adaptive regularization based on diffusion processes on graphs[END_REF], converges, then it converges to the solution of the minimizer [START_REF] Pinkall | Computing discrete minimal surfaces and their conjugates[END_REF]. Moreover, when λ = 0, it converges.

Proof: From ( 25) we can observe that f (t+1) (u) is a convex combination of f 0 (u) and f (t) (v), for all t ≥ 0. Thus we have:

min v∼u {f 0 (v), f (t) (v)} ≤ f (t+1) (u) ≤ max v∼u {f 0 (v), f (t) (v)}.
Then, by recursion, an iteration step t ≥ 0 of (24) satisfies the minimum-maximum principle:

min v∈V f 0 (v) ≤ f (t) (u) ≤ max v∈V f 0 (v), ∀u ∈ V. Let M(V ) be the set of functions f : V → R such that f ∞ ≤ f 0 ∞ , where f ∞ = max v∈V f (v)
is the infinity norm. From [START_REF] Szlam | A general framework for adaptive regularization based on diffusion processes on graphs[END_REF], an iteration can be written as f (t+1) = φ(f (t) ), with φ : M(V ) → M(V ). Then the minimummaximum principle stability implies that φ(M(V )) ⊆ M(V ). By considering that λ = 0, then each component φ(u) : M(V ) → R is continuous with respect to . ∞ , for all u ∈ V . This implies that φ is a continuous mapping. As M(V ) is non-empty, compact and convex, the Schauder fixed point theorem [START_REF] Karamadian | Fixed points, algorithms and applications[END_REF] shows that there exists f ∈ M(V ) which satisfies f = φ(f ). Then, if the algorithm (24) converges, its is to the limit function f which satisfies [START_REF] Zhou | A regularization framework for learning from graph data[END_REF]. Since for p ≥ 1, (21) is the solution of the minimizer ( 14), ( 24) also converges to the solution of [START_REF] Pinkall | Computing discrete minimal surfaces and their conjugates[END_REF].

When λ = 0, we can remark that an iteration of the diffusion process ( 24) can be written in matrix form as f (t+1) = Q(f (t) )f (t) , where Q is a stochastic matrix (nonnegative, symmetric, unit row sum). Then, as demonstrated in [START_REF] Weickert | Anisotropic Diffusion in Image Processing[END_REF], this discrete diffusion process satisfies the minimum-maximum principle, and converges to a constant as t → +∞.

Remark 1: From Proposition 5, when p < 1 (non-convex case), if the algorithm (24) (or equivalently [START_REF] Smola | Kernels and regularization on graphs[END_REF]) converges to some function f ∈ H(V ), the latter is not insured to be the global minimum of the minimizer [START_REF] Pinkall | Computing discrete minimal surfaces and their conjugates[END_REF].

IV. REGULARIZATION OF FUNCTIONS ON DISCRETE DATA

The minimization problem [START_REF] Pinkall | Computing discrete minimal surfaces and their conjugates[END_REF], and the discrete diffusion processes [START_REF] Smola | Kernels and regularization on graphs[END_REF], can be used to regularize any function defined on a finite set V = {v 1 , . . . , v N } of discrete data v i ∈ R m . This is achieved by constructing a weighted graph G = (V, E, w), and by considering the function to be regularized as a function f 0 : V → R, defined on the vertices of G.

A. Construction of Graphs

There exist several popular methods that transform the set V , with a given pairwise distance measure µ : V × V → R + , into a neighborhood graph (or similarity graph). Constructing such a graph consists in modelizing neighborhood relationships between data. Among the existing graphs, the simplest of them is the δ-neighborhood graph, where two data v i , v j ∈ V are connected by an edge of E if µ(v i , v j ) ≤ , with δ > 0. We can also quote the minimum spanning tree, the k-nearest neighbors graph, the Delaunay triangulation, or the relative neighborhood graph, as other possible graph topologies (see [START_REF] O'rourke | Pattern recognition[END_REF] for a survey on neighborhood graphs used in pattern recognition problems). The choice of the graph topology enables to perform several regularization processes that can integrate local, semi-local or nonlocal interactions between the data. These interactions are said to be fully nonlocal if the constructed graph is the complete graph

G c = (V, E, w), with E = V × V \ {(v i , v i ) : v i ∈ V }.
The edges weights are computed according to a similarity measure g : V × V → R, which satisfies:

w(u, v) = g(u, v) if (u, v) ∈ E 0 otherwise (26)
This similarity measure can simply be defined as the inverse of the distance measure: g(u, v) = µ(u, v) -1 . Distances between data are estimated by comparing their features which generally depend on the initial function f 0 and on the set V . To this aim, every data u ∈ V is assigned with a feature vector denoted by F (f 0 , u) ∈ R q . Several choices can be considered for the expression of F , depending on the nature of the features to be preserved. In the simplest case, one can consider F (f 0 , u) = f 0 (u). It also can be computed from the values of f 0 , taken in the neighborhood of u, and from the data in that neighborhood. Therefore, the weight function w, associated to a given graph, can naturally incorporate local, semi-local or nonlocal features according to the topology of the graph. For instance, one can consider the three following general weight functions:

1) g 1 (u, v) = 1 ε+ F (f 0 ,u)-F (f 0 ,v) 2 2) g 2 (u, v) = exp - F (f 0 ,u)-F (f 0 ,v) 2 σ 2 3) g 3 (u, v) = exp - F (f 0 ,u)-F (f 0 ,v) 2 σ 2 exp -u-v 2 2σ 2 d
where σ d and σ are two parameters depending on the variations of uv and F (f 0 , u) -F (f 0 , v) over the graph.

The graph structure, associated with one of the above weight functions, describes a general regularizer family. By changing the graph topology and the edges weights, we naturally obtain an expression of local, semi-local or nonlocal processing methods which is embedded in the graph structure. Indeed, once edges are added between vertices, they are considered as direct neighbors and the processing is local over the graph. From these considerations, we show that with an adapted graph topology and a given appropriate weight function, our general regularizer family is linked to several filters defined in the context of image and mesh processing.

B. Related Works in Image Processing

First, we analyze the case of λ = 0. When p = 2, one iteration of the diffusion process [START_REF] Smola | Kernels and regularization on graphs[END_REF], associated with the weight function g 3 , is equivalent to the bilateral filter, introduced in the context of image denoising [START_REF] Tomasi | Bilateral filtering for gray and color images[END_REF], [START_REF] Barash | A fundamental relationship between bilateral filtering, adaptive smoothing, and the nonlinear diffusion equation[END_REF]. It is a nonlinear filter that combines geometric and range filtering. Bilateral filtering is also used to denoise meshes [START_REF] Fleishman | Bilateral mesh denoising[END_REF]. It is obtained by using the scalar feature F (f 0 , u) = f 0 (u) for all u ∈ V . Using the same parameters, one iteration of filter [START_REF] Smola | Kernels and regularization on graphs[END_REF] can also be considered as the nonlocal means filter [START_REF] Buades | A review of image denoising algorithms, with a new one[END_REF], introduced in the context of images (see also [START_REF] Peyré | Manifold models for signals and images[END_REF], [START_REF] Szlam | A general framework for adaptive regularization based on diffusion processes on graphs[END_REF]). Indeed, it is obtained by using the weight function g 2 with the feature vector

F (f 0 , v) = [f 0 (u) : u ∈ B v,s ] T where B v,s
is a bounding box of size s centered at v (called a patch of size (2s + 1) × (2s + 1)). The norm used in function g 2 is then F (f 0 , u) -F (f 0 , v) 2 2,s which is an Euclidean distance weighted by a Gaussian Kernel. Moreover, when p = 2 and λ = 0, expression (24) can be interpreted as a random walk and expressed via a stochastic matrix which relates it to spectral graph theory [START_REF] Szlam | A general framework for adaptive regularization based on diffusion processes on graphs[END_REF], [START_REF] Chung | Spectral graph theory[END_REF], [START_REF] Coifman | Geometric diffusions as a tool for harmonic analysis and structure definition of data[END_REF].

When λ = 0 and w is constant, filter ( 22) corresponds exactly to the digitized PDE filters proposed in the context of image restoration [START_REF] Osher | Digitized PDE method for data restoration[END_REF], [START_REF] Chan | The digital TV filter and nonlinear denoising[END_REF]. If p = 1, it is the TV regularization. If p = 2, it is the L 2 regularization. In general, if the weight function is not constant, filter [START_REF] Smola | Kernels and regularization on graphs[END_REF] corresponds to the weighted L 2 and the weighted TV discrete regularizations on arbitrary graphs.

Table I resumes how our framework includes and extends well-known discrete models used in image processing. Table I reads in the following way. The first three columns present four different configurations given by the parameters λ and w, and the graph topology. Once these latter parameters are fixed, one can then consider different values of p (next columns in the row of each given configuration).

λ w Graph p = 1 p = 2 p > 0 0 g 3 , semi-

C. Related Works in Local and Nonlocal Functional Continuous Regularization

The regularization of a given function f 0 : V → R, on a complete graph G c , takes into account fully nonlocal interactions between the data of V , through the local variations | w f (u)| that are involved in the discrete p-Dirichlet form:

R p w (f ) (15) = 1 p u∈V | w f (u)| p = 1 p u∈V v∈V w(u, v)(f (v) -f (u)) 2 p 2 . ( 27
)
One can observe that this last functional is exactly the same as the functional [START_REF] Belkin | Laplacian eigenmaps for dimensionality reduction and data representation[END_REF], where v∼u can be replaced by v∈V (w(u, v) = 0 if (u, v) ∈ E). This shows that local, semilocal and nonlocal regularizations on graphs have the same formulation. One can remark that the corresponding continuous analogue of the above discrete regularization functionals, which considers only local interactions, is:

J p w (f ) = 1 p Ω | f | p dx,
where f : Ω → R is a continuous function defined in a bounded domain Ω ⊂ R m . Similarly, the discrete diffusion process ( 27) can also be rewritten in a continuous setting which uses nonlocal interactions:

J p w (f ) = 1 p Ω Ω w(x, y)(f (y) -f (x)) 2 dy p 2 dx.
In particular, for p = 2 and p = 1, it corresponds to the nonlocal functionals introduced in [START_REF] Gilboa | Nonlocal linear image regularization and supervised segmentation[END_REF] and [START_REF]Nonlocal operators with applications to image processing[END_REF] in the context of image processing:

J 2 w (f ) = 1 2 Ω×Ω w(x, y)(f (y) -f (x)) 2 dxdy J 1 w (f ) = Ω Ω w(x, y)(f (y) -f (x)) 2 dy 1 2
dx Moreover, in [START_REF] Ta | Nonlocal anisotropic discrete regularization for image, data filtering and clustering[END_REF], we show that, with the same gradient operator, replacing R p w by a p-norm leads to the following expression:

R p w = 1 2p u∈V | w f (u)| p p = v∼u w(u, v) p 2 |f (v) -f (u)| p ,
which can be considered as the discrete analogue of the recently proposed continuous nonlocal anisotropic functionals [START_REF] Gilboa | Nonlocal linear image regularization and supervised segmentation[END_REF], [START_REF]Nonlocal operators with applications to image processing[END_REF].

V. APPLICATIONS The family of filters proposed in Section III can be used to regularize any function defined on the vertices of a graph, or on any discrete data set.

For any of these different applications, one wants to regularize a function

f 0 : V ⊂ R n → R m , where f 0 (u) = [f 0 1 (u), . . . , f 0 m (u)] T and f 0 i : V → R is the i-th component of f 0 (u).
When the operates on vector-valued functions, one regularization process per vector component is considered. Each component is processed independently and this comes to have m independent iterative regularization schemes:

           f (0) i = f 0 i f (t+1) i (v) = f 0 i (v) + u∼v γ (t) i (u, v)f (t) i (u) λ + u∼v γ (t) i (u, v) (28)
The p-Laplace operator is different for each component and one has

γ f (t) i w (u, v) = w(u, v)(| w f (t) i (v)| p-2 + | w f (t) i (u)| p-2 ).
(29) for the i th component. Applying the regularization in a component-wise manner is interesting to develop a computational efficient solution. However, component-wise processing of vector-valued data can have serious drawbacks contrary to vector processing solutions. To overcome this limitation, a regularization process acting on vector-valued data needs to be driven by equivalent geometric attributes, taking the coupling between vector components into account [START_REF] Tschumperlé | Vector-valued image regularization with PDEs: A common framework for different applications[END_REF], [START_REF] Weickert | Coherence-enhancing diffusion of colour images[END_REF]. Therefore, component-wise regularization does not have to use different local geometries but a vector one. In the case of p = 2 the p-Laplace operator is the same for all the components, but in the case of p = 2 it is different. As we have just mentioned, this is not interesting. Indeed, in this case, the m regularization processes can be totally independent if w(u, v) does not incorporate any inter-component information resulting in no coupling between the m independent regularizations. To overcome this limitation and in order to take into account the inner correlation aspect of vectorial data, the p-Laplace operator is considered as being the same for the m component regularizations (component coupling). This is achieved by using the same vectorial local variation defined by:

|∇ w f (t) (v)| = m i=1 |∇ w f (t) i (v)| 2 , ( 30
)
where [START_REF] Lezoray | Graph regularization for color image processing[END_REF]. The inner correlation is also considered by using vectorial weight functions, such as the ones defined in Section IV-A.

|∇ w f (t) (v)| replaces |∇ w f (t) i (v)|, for all i in
In the sequel, we provide examples of obtained results with the proposed framework for the simplification of images (scalar or vectorial), polygonal curves, meshes, manifolds, and data bases.

Scalar image smoothing: Let f 0 be a scalar image of N pixels, with f 0 : V ⊂ Z 2 → R which defines a mapping from the vertices to gray levels. We illustrate the abilities of the proposed framework for smoothing scalar images. All the results are shown at convergence. To this aim, Figure 1 shows sample results obtained with different parameters of the proposed regularization: different values of p, different values of λ and different weight functions. The first line of Figure 1 presents the initial image (first column) and the computed gradient on the initial image with constant weights (w = 1, second column), with computed weights in local (third column, σ = 20 for w = g 2 ) or nonlocal configurations (fourth column, σ = 4 for w = g 2 ). For the nonlocal configuration, we consider a 19 × 19 neighborhood window and a 11 × 11 patch as a feature vector. In the table part of Figure 1, the first two grouped columns present local regularizations with constant weights (w = 1) and with different values of λ (provided above each column). For these cases, the considered graph is a 4-adjacency grid graph and the results obtained for p = 1 or p = 2 correspond exactly to the digital TV and L 2 filters of Chan and Osher [START_REF] Osher | Digitized PDE method for data restoration[END_REF], [START_REF] Chan | The digital TV filter and nonlinear denoising[END_REF]. In the table part of Figure 1, the grouped third and fourth columns present results obtained with the proposed framework with the same parameters but with computed weights (w = g 2 ). For these cases, the considered graph is a 8-adjacency grid graph. The first thing to consider is that our approach is a direct extension of [START_REF] Osher | Digitized PDE method for data restoration[END_REF], [START_REF] Chan | The digital TV filter and nonlinear denoising[END_REF] to weighted graphs which enables to produce better visual results by using computed edges weights. The second thing to notice is that a low value of p enables to better preserve edges and fine structures. Moreover, it tends to level the image in flat zones. Changing the value of parameter λ enables to obtain solutions either close or far from the original image. All these noticed points become more evident once one uses a nonlocal configuration which enhances once again the preservation of edges and the production of flat zones. Nonlocal results are provided in last column of the table part of Figure 1. This shows how our proposed frameworks generalizes the NLmeans filter [START_REF] Buades | A review of image denoising algorithms, with a new one[END_REF].

f 0 : V → R | f 0 w=1 (u)|, | f 0 w=g 2 (u)|, | f 0 w=g 2 (u)|, F (f 0 , v) = f 0 (v) F (f 0 , v) = f 0 (v) F (f 0 , v) : 11 × 11 patch w = 1, w = g 2 , w = g 2 , F (f 0 , v) = f 0 (v) F (f 0 , v) = f 0 (v) F (f 0 ,
Vectorial image smoothing and denoising: Let f 0 be a color image of N pixels,

f 0 = [f 0 1 , . . . , f 0 N ] T with f 0 : V ⊂ Z 2 → R 3
which defines a mapping from the vertices to a vector of color channels. Figure 2 presents present results of a local processing, for p = 2, p = 1 and p = 0.7, on a 8-adjacency grid graph with edges weighted by g 2 and F (f 0 , v) = f 0 (v). This extends the vectorial digital TV filter [START_REF] Chan | The digital TV filter and nonlinear denoising[END_REF] to weighted graphs as mentioned above for scalar images. Figures 2(d), (g), (j) present results of a nonlocal processing, for p = 2, p = 1 and p = 0.7, on a 120-adjacency grid graph (a search window of size 11 × 11) with edges weighted by g 2 and F (f 0 , v) defined on a patch of size 5 × 5. Figures 2(d), (g), (j) present results with the same nonlocal parameters except that w = g 1 . Parameters λ and σ (for w = g 2 ) are automatically estimated (see in [START_REF] Lezoray | Parameterless discrete regularization on graphs for color image filtering[END_REF] for further details). A visual analysis of the results shows that values of p ≤ 1 enable to better preserve edges while increasing the graph connectivity and using patches for similarities enable to better preserve some details. Figures

F (f 0 , v) = f 0 (v) F (f 0 , v) : 5 × 5 patch w = g 2 w = g 2 w = g 1 p = 2 (c) (d) (e) p = 1 (f) (g) (h) p = 0.7 (i) (j) (k)
2(i)-(k)
show the importance of the similarity measure for computing the edges weights. Indeed, with w = g 1 , an over-smoothing effect is obtained without preserving details. This confirms that this is not a nonlocal view but the use of an appropriate similarity measure which enables to preserve fine structures. Edges of the RAG are weighted by g 1 . The graph is decimated along the iterations by merging regions the difference of which is lower than a given arbitrary threshold of 2 in our experiments. First row of Figure 3 presents the original image, its fine partition (obtained by the concept of homogeneous zones [START_REF] Meurie | A new method of morphological hierarchical segmentation[END_REF]) and the associated color median image (m = 3). When a color median image is presented in Figure 3, we provide the PSNR between the original and the color median image. When a partition is presented in Figure 3, we provide the number of vertices of the RAG. Last rows of Figure 3 present results (color median and partition images) where each row corresponds to a value of p for two different values of λ. When λ = 0, a small value of p enables to better preserve the initial image content with a lower number of vertices. When λ = 0, a small value of p also enables to have a good preservation of the initial image content but with a higher number of vertices. It is worth noting that merging similar regions to decimate the RAG during the simplification enables to accelerate the simplification process. Therefore, the use of the RAG instead of the classical grid-graph enables a faster processing [START_REF] Lezoray | Graph regularization for color image processing[END_REF], [START_REF] Lezoray | Multi-scale image segmentation in a hierarchy of partitions[END_REF] since there are less vertices as compared to the number of pixels. Similar works based on RAGs have also been proposed [START_REF] Sharon | Fast multiscale image segmentation[END_REF], [START_REF] Guigues | Scale-sets image analysis[END_REF].

Polygonal curve and surface simplification: By nature, polygonal curves and surface meshes have a graph structure. First, we consider the case of a polygonal curve represented by a graph: local regularization. First, as attended, acting on parameter λ enables to reach different levels of simplification. One important thing to note here is that the presented graphs all have the same number of vertices: simplification enables to groups similar vertices around high curvature regions. The second thing to point out is that acting on p enables to perform a denoising of the original graph but also to smooth (for p ≥ 1) or to preserve sharp angles (for p < 1).

f 0 : V ⊂ R 2 → R 2
Second, we consider the case of surface meshes. Let V be the set of mesh vertices, and let E be the set of mesh edges. If the input mesh is noisy, we can regularize vertex coordinates or any other function f 0 : V ⊂ R 3 → R 3 defined on the graph G = (V, E, w). Results of filter (28) are given in Figure 5 for triangular meshes with a local regularization for edges weighted by function g 1 . We can observe the same key points than with polygonal curves. Moreover, the shrinkage effect obtained with p = 1 or p = 2 when λ → 0 is highly reduced with low values of p which shows the benefits of our approach (see the cropped and zoomed areas in three last columns of the first row in Figure 5). As for image simplification on a RAG, one could also merge vertices along the iterations as they become similar.

Manifold smoothing: Graph-based methods have recently emerged as a powerful tool for analyzing high dimensional data that has been sampled from a low dimensional submanifold [START_REF] Lafon | Diffusion maps and coarse-graining: A unified framework for dimensionality reduction, graph partitioning and data set parameterization[END_REF], [START_REF] Belkin | Regularization and semisupervised learning on large graphs[END_REF]. These methods begin by constructing a graph in which the nodes represent input patterns and the edges represent neighborhood relations. The resulting graph (assumed connected) can be viewed as a discretized approximation of the submanifold sampled by the input patterns. Let G = (V, E, w) be a graph defined over the manifold. Typical graphs are the complete graph and the k-nearest neighbor graph. Typical manifolds being image libraries, we consider the USPS handwritten digit database for illustration. Each digit is a 16 × 16 image which is considered as a vector of 256 dimensions. Let f 0 : V → R 16×16 be a mapping from the vertices of G to the elements of the manifold. We consider the complete graph weighted by function g 2 and constructed over the manifold. To each vertex is associated a feature vector representing each digit. The filter ( 28) is considered (256 parallel coupled regularization processes are performed) with p = 2 and different amounts of data attachment. Since the complete graph is considered, the regularization is naturally nonlocal. Figure 6 presents regularization results on 200 digits from the USPS database. Without the data term, the manifold reduces to its main digit which is an artificial one since the manifold is smoothed. By increasing the data term, the regularized manifold remains closer to the original one. Such manifold regularization can be useful for classification purposes on a noiseless submanifold [START_REF] Hein | Manifold denoising[END_REF] extracted from a noisy manifold.

Data smoothing: Given any data, the latter can be associated with a graph by considering a similarity measure.

Therefore, any data base can be regularized with our method as long as it is associated with a graph structure. To show the efficiency of such processing, we consider two well-known databases: Iris and Ionosphere Therefore, this is an efficient method to map input points into a regularized space where clusters are more easily separable: the submanifold where the data lies has been recovered. This effect is illustrated by the results obtained with a standard k-means classification on the original and the regularized versions: the processing enables to increase the recognition rate.

VI. CONCLUSION We proposed a general discrete framework for regularizing real-valued or vector-valued functions on weighted graphs of arbitrary topology. The regularization, based on the p-Laplace operator, leads to a family of nonlinear iterative filters. This family includes the TV digital filter, the nonlocal means filter and the bilateral filter, widely used in image processing. Also, the family is linked to spectral graph filtering and is the discrete analogue of recent continuous nonlocal regularizations.

The choice of the graph topology and the choice of the weight function enable to regularize any discrete data set or any function on it. Indeed, the data can be structured by neighborhood graphs weighted by functions depending on data features. This can be applied in the contexts of image smoothing, denoising or simplification. We also show that mesh smoothing and denoising can be performed by the same filtering process. Similarly, manifolds can be processed by the same means to recover a noiseless submanifold from a noisy manifold.

1 Fig. 1 .

 11 Fig. 1. Scalar image simplification on a gray level image with different parameters values of p, λ and different weight functions in local or nonlocal configurations. First row presents the original image and the gradient in different configurations. Next rows present simplification results where each row corresponds to a value of p (see text for more details).

Fig. 2 .

 2 Fig. 2. Image denoising illustration on an original color image (Figure 2(a)) corrupted by Gaussian noise (Figure 2(b) with σ = 15, PSNR between original and corrupted images is 85.04db). Results are provided for different values of p for local (Figures 2(c), (f), (i) with w = g 2 and a 3 × 3 neighborhood) and nonlocal processing (Figures 2(d), (g), (j) for w = g 2 , Figures 2(e), (h), (k) for w = g 1 , both with a 11 × 11 neighborhood and 5 × 5 patch).

  Image simplification: On the contrary to classical image simplification which considers grid graphs, one can simplify an image by first considering a fine partition of this image (or over-segmentation), where the pixel values of each region of the partition are replaced by the mean or the median pixel value of this region. The partition can be associated with a Region Adjacency Graph (RAG), where vertices represent regions and where edges link adjacent regions. Let G = (V, E, w) be a RAG. Let f 0 : V ⊂ Z 2 → R m be a mapping from the vertices of G to the mean or median value of their regions. Then, the simplification is achieved by regularizing the function f 0 on G. Moreover, we can build an irregular pyramid of partitions by alternating simplification (only one iteration) and graph decimation since one iteration of the simplification brings neighbor vertices to similar models. We present the results of a local simplification performed with different values of p and λ after t = 5 iterations of sequential graph filtering and graph decimation.

Fig. 3 .

 3 Fig. 3. Image simplification illustration. From an original image, one computes a pre-segmentation and the associated color median image (images in first row). Regularization and decimation are applied on the RAG of the pre-segmentation and simplified region maps and color median images are obtained for different values of λ and p (next rows).

GFig. 4 .

 4 Fig. 4. Behavior of the regularization of a polygonal curve G (first row, first column), by using the discrete diffusion process (until convergence). First row presents the graph constructed over an initial set of points. Next rows present simplification results where each row corresponds to a value of p. For each p, the four regularizations are obtained with decreasing values of the scale parameter λ > 0. The original mesh (|V | = 24930) is from Shape Repository, Aim@Shape Project (http://shapes.aim-at-shape.net).

Fig. 5 .

 5 Fig.5. Behavior of the regularization of a triangular mesh (first row, first column), by using the discrete diffusion process (until convergence). First line presents the original mesh (first column), a zoom on a part of this mesh (the ear of the lion) before (second column) and after regularization for p = 1 and p = 0.1 with λ = 0.04. Next rows present simplification results where each row corresponds to a value of p. For each p, four regularizations are obtained with decreasing values of the scale parameter λ > 0.

  [START_REF] Hettich | UCI repository of machine learning databases[END_REF]. Iris database contains 3 classes of samples in 4 dimensions with 50 samples in each class. Ionosphere database contains 2 classes of samples in 34 dimensions with for each class 225 and 126 samples.

Figure 7 (

 7 a) presents a pairwise feature projection of the Iris database. Due to the high dimensionally of Ionosphere, only few relevant feature pairs projections are shown. With such real-worl data bases, some noise is present and data smoothing is therefore of interest. Let G = (V, E, w) be a graph defined over the data. Let f 0 : V → R m be a mapping from the vertices of G to the elements of the data base (m = 4 for Iris and m = 34 for Ionosphere). We consider a complete graph and regularization is performed with p = 2

  (a) Original USPS handwritten digit 0 database. (b) Nonlocal regularization with λ = 1. (c) Nonlocal regularization with λ = 0.01. (d) Nonlocal regularization with λ = 0.

Fig. 6 .

 6 Fig. 6. Nonlocal manifold regularization (p = 2) for different values of λ. The original manifold is the digit 0 from the USPS handwritten digit database. See text for details.

Figure 7 (

 7 b) presents the regularization result on original Iris data depicted in Figure 7(a).

Figure 7 (

 7 d) presents the regularization result on original Ionosphere data depicted in Figure7(c). One can see the benefits of the regularization: input points which belong to the same class tend to be closer than in the original data base.

  (a) Original Iris data base (Recognition rate: 85.3%). (b) Regularized Iris data base with w = g 2 (Recognition rate: 95.3%).(c) Original Ionosphere data base (Recognition rate: 71.8%).(d) Regularized Ionosphere data base with w = g 1 (Recognition rate: 75.4%).

Fig. 7 .

 7 Fig. 7. Nonlocal Data base regularization (p = 2, λ = 0.01, t = 10) with recognition rates obtained with a k-means (averaged over 50 runs).

ACKNOWLEDGEMENTS

The authors thank the reviewers for their valuable comments and suggestions to improve the quality of the paper. The authors would also like to thank Vinh Thong Ta for providing the results on manifold and data smoothing.

This research work was partially supported by the ANR foundation under grant ANR-06-MDCA-008-01/FOGRIMMI and by FEDER and FNADT funds.