Frédéric Chazal

David Cohen-Steiner

Quentin Mérigot

Geometric Inference for Measures based on Distance Functions

Keywords: density estimation, reconstruction, Wasserstein distance, Mean-Shift

Data often comes in the form of a point cloud sampled from an unknown compact subset of Euclidean space. The general goal of geometric inference is then to recover geometric and topological features (e.g. Betti numbers, normals) of this subset from the approximating point cloud data. In recent years, it appeared that the study of distance functions allows to address many of these questions successfully. However, one of the main limitations of this framework is that it does not cope well with outliers nor with background noise. In this paper, we show how to extend the framework of distance functions to overcome this problem. Replacing compact subsets by measures, we introduce a notion of distance function to a probability distribution in R n . These functions share many properties with classical distance functions, which makes them suitable for inference purposes. In particular, by considering appropriate level sets of these distance functions, it is possible to associate in a robust way topological and geometric features to a probability measure. Moreover, in settings where empirical measures are considered these functions can be easily evaluated, making them of particular practical interest.

Inférence géométrique pour les mesures en utilisant la fonction distance

Résumé : De nombreuses données sont souvent représentées sous forme de nuages de points échantillonnés dans des espaces Euclidiens au voisinage de sous-ensembles compacts. L'objectif général de l'inférence géométrique est de retrouver les caractéristiques topologiques et géométriques (par ex. nombres de Betti, normales) de ces sous-ensembles à partir des données. Ces dernières années, l'études des fonctions distance a permis d'aborder avec succès bon nombre de problèmes d'inférence géométrique. Cependant, une des principales limitation de ce cadre est qu'il ne permet pas de considérer des données qui sont entachées de valeurs aberrantes et/ou d'un bruit de fond. Dans cet article, nous montrons comment étendre le cadre des fonctions distance pour résoudre ce problème. En remplaçant les sous-ensembles compacts par des mesures, nous introduisons une notion de fonction distance à une probabilité dans R n . Ces fonctions partagent de nombreuses propriétés avec les fonctions distance classiques qui les rendent utiles pour l'inférence géométrique. En particulier, en considérant des niveaux appropriés de ces fonctions, il est possible d'associer de façon robuste des caractéristiques topologiques et géométriques à des mesures de probabilité.

Mots-clés : estimation de densité, reconstruction, distance de Wasserstein, Mean-Shift

Introduction

Extracting geometric and topological information from geometric data, such as 3D point clouds obtained from laser scanners, is a requirement for many geometry processing and data analysis algorithms. The need for robust estimation of geometric invariants have been recognized long time ago in geometry processing, and such invariants have found applications in fields as different as shape matching, registration, symmetry detection in 3D models or more generally structure discovery, reconstruction, meshing to name just a few. More recently, it became apparent that such geometric and topological quantities could also be used to analyze more general data sets coming from computational structural biology, large image databases, etc. It turns out that many questions in data analysis can be naturally stated as inferring the geometry of an unknown underlying geometric object. For example, the number of clusters in which a point cloud can be split is related to the number of connected components of this unknown object. Similarly, finding out the number of parameters really needed to faithfully describe a point in the cloud -which is usually much smaller than the dimension of the ambient space -is a matter of estimating the dimension of the underlying set.

Inference using offsets and distance functions

One approach to geometric inference is to try to build a reconstruction of the unknown set K and to estimate the geometric characteristics of K by the ones of the reconstruction. Perhaps the most obvious way to build such a reconstruction is to consider the r-offset of the point cloud, that is, the union of balls of a suitable radius r whose center lie in the point cloud. It has been recently proven by [START_REF] Niyogi | Finding the homology of submanifolds with high confidence from random samples[END_REF][START_REF] Chazal | Smooth manifold reconstruction from noisy and non-uniform approximation with guarantees[END_REF] that this simple idea leads to a correct estimation of the topology of a smooth manifold, under assumptions on the sampling and the choice of r. This result has been extended to a general class of non-smooth compact sets by [START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF]. An important feature of offsets of point clouds is that their topology can be computed efficiently, at least when the point cloud lies in a lowdimensional ambient space. For instance, [START_REF] Edelsbrunner | The union of balls and its dual shape[END_REF] has described an algorithm that given a point cloud C builds a simplicial complex, called the α-complex, that has the same topology as the union of balls of radius α centered at points in C. This algorithm requires to compute the Delaunay triangulation of C, and is hence impractical in higher dimensions. However, even in this case, one can resort to Vietoris-Rips complexes and the theory of topological persistence to correctly infer the Betti numbers of offsets of C [START_REF] Chazal | Towards persistence-based reconstruction in Euclidean spaces[END_REF].

A different way to look at offsets, which is equivalent but better suited to the actual proof of inference results, is through the notion of distance function. Given a compact subset K of R d , the distance function d K maps any point x in R d to the minimum distance between x and any point y in K. The r-offset of K is then nothing but the sublevel set d -1

K ([0, r]). The most important property of the distance function for geometric inference is its stability: if a compact set K ′ , e.g. a point cloud, is a good Hausdorff approximation of another compact set K, then the distance functions d K ′ and d K are close to each other. This property, and two other regularity properties that we will describe later, are the only requirements for proving the topological inference result mentioned earlier.

Offset-based topological inference is now mature and has been used in different contexts to estimate the topology and geometry of shapes sampled with a moderate amount of noise [START_REF] Chazal | Boundary measures for geometric inference[END_REF][START_REF] Chazal | Normal cone approximation and offset shape isotopy[END_REF][START_REF] Mérigot | Robust Voronoi-based Curvature and Feature Estimation[END_REF]. However, these methods obviously fail completely in the presence of outliers. Indeed, adding even a single data point that is far from the original point cloud will increase by one the number of connected components of the offsets of this point cloud, for a large range of parameters. Said otherwise, while the distance function is only slightly perturbed under Hausdorff noise, adding even a single outlier can change it dramatically.

Contributions

A possible way to solve the problem of outliers for distance-based inference is then to try to replace the usual distance function to a set K by another notion of distance function that is robust to the addition of a certain amount of outliers. To define what is this certain amount one can change the way point clouds are interpreted: they are no more purely geometric objects, but also carry a notion of mass. Formally, we replace compact subsets of R d by finite (probability) measures on the space; a k-manifold will be replaced by the uniform k-dimensional measure on it, a point cloud by a finite sum of Dirac masses, etc. The Hausdorff distance is then not meaningful any more; instead, the distance between two probability measures will be measured through Wasserstein distance, which quantifies the minimal cost of transporting one measure onto the other (cf ➜2.2).

In this article, we introduce a notion of distance function to a probability measure µ, which we denote by d µ,m 0 -where m 0 is a "smoothing" parameter in (0, 1). We show that this function retains all the required properties for extending offset-based inference results to the case where the data can be corrupted by outliers. Namely, function d µ,m 0 shares the same regularity properties as the usual distance function, and it is stable in the Wasserstein sense, meaning that if two measures are Wasserstein-close, then their distance functions are uniformly close. It can also be computed efficiently for point cloud data. This opens the way to the extension of offset-based inference methods to the case where data may be corrupted by outliers. In particular, we show that considering sublevel sets of our distance functions allows for correct inference of the homotopy type of the unknown object under fairly general assumptions. This improves over the main existing pre-INRIA vious work on the subject [START_REF] Niyogi | A Topological View of Unsupervised Learning from Noisy Data[END_REF], which assumes a much more restrictive noise model, and is limited to the smooth case.

Background: Measures and Wasserstein distances

As explained in the introduction, in order to account for outliers, we consider our objects as mass distributions instead of purely geometric compact sets. Because one of the goals of this article is to give inference results, i.e. comparison between discrete and the continuous representations, we cannot give the definitions and theorems only in the discrete case, but have to deal with the general case of probability measures.

Measure theory

A measure µ on the space R d is a mass distribution. Mathematically, it is defined as a function that maps every (Borel) subset B of R d to a non-negative number µ(B), which is countably additive in the sense that whenever

(B i ) is a countable family of disjoint Borel subsets of R d , µ (∪ i∈N B i ) = i µ(B i ).
The total mass of a measure is µ(R d ). A measure with finite total mass is called finite, while a measure with total mass one is a probability measure. The support of a measure µ is the smallest closed set K on which the mass of µ is concentrated, i.e. µ(R d \ K) = 0.

Given a set of N points C, the uniform measure on C, which we denote by µ C , can be defined by µ C (B) = 1 N |B ∩ C|. More intuitively, it is the sum of N Dirac masses of weight 1/N , centered at each point of C. When the points in C are chosen randomly and independently according to an underlying, unknown measure, the measure µ C is called an empirical measure. Formally, we are given a family of independent identically distributed random variables X 1 , . . . X N who are distributed according to a common measure µ. The uniform probability measure carried by the point cloud C N = {X 1 , . . . , X n } is known as the empirical measure, and simply denoted by µ N . The uniform law of large numbers asserts that, as N goes to infinity, the empirical measure converges to the underlying measure with probability one -in a sense that will be explained in the next paragraph.

The approach we will describe in this article applies to any measure on Euclidean space. However, to fix ideas, let us describe a family of measures with geometric content that we have in mind when thinking of the underlying measure. One starts from the probability measure µ M on a compact k-dimensional manifold M ⊆ R d given by the rescaled volume form on M , possibly with a non-uniform density. Such measures can be combined, yielding a measure supported on a union of submanifolds of R d with various intrinsic dimensions: ν = ℓ i=1 λ i µ M i . Finally, as a simple model of noise, this measure can be convolved with a Gaussian distribution: µ = ν * N (0, σ). This is the same as assuming that each sample that is drawn according to ν is known up to an independant Gaussian error term.

The empirical measure defined by the measure µ we just described could then be obtained by repeatedly (i) choosing a random integer i ∈ {0, . . . , ℓ}, (ii) picking a random sample X n uniformly distributed in M i , (iii) adding a random Gaussian vector of variance σ 2 to X n .

Wasserstein distances

The definition of Wasserstein W p (p 1) distance between probability measures rely on the notion of transport plan between measures. It is related to the theory of optimal transportation (see e.g. [START_REF] Villani | Topics in Optimal Transportation[END_REF]). The Wasserstein distance W 1 is also known as the earth-mover distance, and has been used in vision by [START_REF] Peleg | A unified approach to the change of resolution: space and gray-level[END_REF] and in image retrieval by [START_REF] Rubner | The Earth Mover's Distance as a Metric for Image Retrieval[END_REF] and others.

A transport plan between two probability measures µ and ν on R d is a probability measure π on R d ×R d such that for every A, B ⊆ R d π(A×R d ) = µ(A) and π(R d ×B) = ν(B). Intuitively π(A×B) corresponds to the amount of mass of µ contained in A that will be transported to B by the transport plan. Given p 1, the p-cost of such a transport plan π is given by

C p (π) = R d ×R d x -y p dπ(x, y) 1/p
This cost is finite if both measures µ and ν both have finite p-moments, i.e. R d x p dµ(x) < +∞ and R d x p dν(x) < +∞. The set of probability measures on R d with finite p-moment includes all probability measures with compact support, such as empirical measures.

Definition 2.1. The Wasserstein distance of order p between two probability measures µ and ν on R d with finite p-moment is the minimum p-cost C p (π) of a transport plan π between µ and ν. It is denoted by W p (µ, ν).

As a first example, consider a reference point cloud C with N points, and define a noisy version C ′ by replacing n points in C by outliers, i.e. points o such that d C (o) R. The Wasserstein distance between the uniform measures µ C and µ is at most n N (R + diam(C)). This can be seen by considering the cost of the transport plan between C ′ and C that moves the outliers back to their original position, and keeps the other points fixed. On the other hand, the Hausdorff distance between C and C ′ is at least R. Hence, if the number of outliers is small, i.e. n ≪ N , the Wasserstein distance is much smaller than the Hausdorff distance.

As mentioned earlier, the question of the convergence of the empirical measure µ N to the underlying measure µ is fundamendal in the measurebased inference approach we propose. It has been a subject of study in probability and statistics for a long time. If µ is concentrated on a compact INRIA set, then µ N converges almost surely to µ in the W p distance. More quantitative convergence statement under different assumptions can be given, as in [START_REF] Bolley | Quantitative Concentration Inequalities for Empirical Measures on Non-compact Spaces[END_REF].

If χ : R d → R + defines a probability distribution with finite p-moment σ p := R d x p χ(x)dx, the Wasserstein distance of order p between any probability measure µ and the convolved measure µ * χ can be bounded by: W p (µ, µ * χ) σ. If one considers again the example given in the end of ➜2.1 of an empirical measure µ N whose samples are drawn according to a "geometric" measure ν convolved with a Gaussian distribution N (0, σ), the combination of the two previous facts gives:

lim N →+∞ W 2 (µ N , µ) σ with probability one
Similar bounds are also possible with convolution kernels that are not translation invariant, such as the ones defining the noise model used in [START_REF] Niyogi | A Topological View of Unsupervised Learning from Noisy Data[END_REF]. This being said, we would like to stress that the stability results we obtain for the distance functions introduced below do not depend on any noise model; they just depend on the Wasserstein distance between the two probability measures being small.

Distance function to a probability measure

In this section we introduce the notion of distance function to a measure that we consider. As explained in the introduction, there are a few constraints for such a definition to be usable in geometric inference, which we now describe in more detail. Let K be a compact set, and d K be the distance function to K. Then, one can prove the two following properties:

(i) d K is 1-Lipschitz. For all x, y in R d , |d K (x) -d K (y)| x -y . (ii) d 2 K is 1-semiconcave. This property is equivalent to the concavity of the map x ∈ R d → d 2 K (x) -x 2 .
A consequence of Lipschitz regularity is that the distance function is differentiable almost everywhere; in particular, the medial axis of K, defined as the set of non-differentiability points of d K has zero d-volume. Semiconcavity is a stronger regularity property, as thanks to Alexandrov's theorem it implies that the distance function d K is not only almost C 1 , but also twice differentiable almost everywhere. The semiconcavity property plays a central role in the proof of existence of the flow of the gradient of the distance function by [START_REF] Lieutier | Any open bounded subset of R n has the same homotopy type as its medial axis[END_REF] (Lemma 5.1), which is the main technical tools used in the topological inference results obtained by [START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF]. The semiconcavity of the squared distance function also plays a crucial role in geometric inference results such as [START_REF] Chazal | Boundary measures for geometric inference[END_REF] and [START_REF] Mérigot | Robust Voronoi-based Curvature and Feature Estimation[END_REF]. This motivates the definition of a distance-like function as a non-negative function ϕ : R d → R + which is 1-Lipschitz, whose square is 1-semiconcave, and which is proper in the sense that ϕ(x) tends to infinity as x does. The following proposition gives a characterization of distance-like functions:

Proposition 3.1. Let ϕ : R d → R be a function whose square is 1-semiconcave. There exists a closed subset K of R d+1 such that ϕ 2 (x) = d 2 K (x), where a point x in R d is identified with the point (x, 0) in R d+1 . Proof. Let x ∈ R d and v be a subgradient to ϕ 2 at x, and v ′ = v/2. Define a function ψ v by ψ v (y) = ϕ 2 (x) -v ′ 2 + x -v ′ -y 2 .
The 1-semiconcavity of the function ϕ 2 yields ψ v (y) ϕ 2 (y), with equality at y = x. Hence, the function ϕ 2 is the lower envelope of all the functions ψ v as defined above.

Letting y = x -v ′ , we see that the constant part of ψ v is positive. Hence, one can define a point z of R d+1 , by (x -v ′ , (ϕ 2 (x) -v ′ 2 ) 1/2 ), such that ψ v (x)
is equal to the squared Euclidean distance between (x, 0) and z in R d+1 . Finally, ϕ 2 is the squared distance to the set K ⊆ R d+1 made of all such points z. This proposition proves in particular that a function ϕ : R d → R whose square is 1-semiconcave and proper is automatically distance-like: the Lipschitz assumption comes with 1-semiconcavity. It also follows from the proof that distance-like functions are simply generalized power distances, with non-positive weights.

Definition

The distance function to a compact set K at x ∈ R d is by definition the minimum distance between x and a point of K. Said otherwise, the distance d K (x) is the minimum radius r such that the ball centered at x of radius r contains at least a point of K. A very natural idea when trying to define the distance function to a probability measure µ on R d is to try mimick the definition above. Given a parameter 0 m < 1, define the pseudo-distance

δ µ,m by δ µ,m : x ∈ R d → inf{r > 0 ; µ(B(x, r)) > m}.
For instance for m = 0, the definition would coincide with the (usual) distance function to the support of the measure µ. For higher values of m, the function δ µ,m is 1-Lipschitz, but lacks other features of that a generalization of the usual distance function to a compact should have. For instance, the application that maps a probability measure µ to δ µ,m is not continuous in any reasonable sense. Indeed, let δ x denote the unit Dirac mass at x and

µ ε = ( 1 2 -ε)δ 0 + ( 1 2 + ε)δ 1 .
Then, for ε > 0 one has δ µε,1/2 (t) = |1 -t| for t < 0 while if ε = 0, one obtains δ µ 0 ,1/2 (t) = |t|. Said otherwise, the map ε → δ µε,1/2 is discontinuous at ε = 0.

INRIA

In order to gain both Wasserstein-stability and regularity, we define the distance function to µ as a L 2 average of the the pseudo-distances δ µ,m for a range [0, m 0 ] of parameters m: Definition 3.2. Let µ be a (positive) measure on the Euclidean space, and m 0 be a positive mass parameter m 0 > 0 smaller than the total mass of µ. We call distance function to µ with parameter m 0 the function defined by :

d 2 µ,m 0 : R n → R + , x → 1 m 0 m 0 0 δ µ,m (x) 2 dm
As an example, let C be a point cloud with N points in R d , and µ C be the uniform measure on it. The pseudo-distance function δ µ C ,m evaluated at a point x ∈ R d is by definition equal to the distance between x and its kth nearest neighbor in C, where k is the smallest integer larger than m |C|. Hence, the function m → δ µ C ,m is constant on all ranges ( k N , k+1 N ]. Using this one obtains the following formula for the squared distance d 2 µ,m 0 , where

m 0 = k 0 / |C|: d 2 µ,m 0 (x) = 1 m 0 m 0 0 δ µ,m (x) 2 = 1 m 0 k 0 k=1 1 N δ µ,k/N (x) 2 = 1 k 0 p∈NN k 0 C (x) p -x 2
where NN k 0 C (x) denote the k 0 nearest neighbors of x in C. In this case, the pointwise evaluation of d 2 µ C ,k/n (x) reduces to a k-nearest neighbor query in C.

Equivalent formulation

In this paragraph, we prove that the distance function to a measure d µ,m 0 is in fact a real distance to a compact set, but in a infinite-dimensional space. From this fact, we will deduce all of the properties needed for geometric and topological inference.

A measure ν will be called a submeasure of another measure µ if for every Borel subset B of R d , ν(B) µ(B). This is the same as requiring that µν is a measure. The set of all submeasures of a given measure is denoted by Sub(µ), while the set of submeasures of µ with a prescribed total mass m 0 is denoted by Sub m 0 (µ). Proposition 3.3. For any measure µ on R d , the distance function to µ at x is the solution of the following optimal transportation problem:

d µ,m 0 (x) = min {m -1/2 0 W 2 (m 0 δ x , ν) ; ν ∈ Sub m 0 (µ)} (1)
Then, for any measure µ x,m 0 that realizes the above minimum one has:

d µ,m 0 (x) = 1 m 1/2 0 R d x -h 2 dµ x,m 0 (h) 1/2
Said otherwise, the distance d µ,m 0 evaluated at a point x ∈ R d is the minimal Wasserstein distance between the Dirac mass m 0 δ x and the set of submeasures of µ with total mass m 0 :

d µ,m 0 (x) = 1 √ m 0 dist W 2 (m 0 δ x , Sub m 0 (µ)) (2)
The set of minimizers in the above expression corresponds to the "orthogonal" projections, or nearest neighbors, of the Dirac mass m 0 δ x on the set of submeasures Sub m 0 (µ). As we will see in the proof of the proposition, these are submeasures µ x,m 0 of total mass m 0 whose support is contained in the closed ball B(x, δ µ,m (x)), and whose restriction to the open ball B(x, δ µ,m (x)) coincides with µ. Denote these measures by R µ,m 0 (x).

In order to prove Proposition 3.3, we need a few definitions from probability theory. The cumulative function F ν : R + → R of a measure ν on R + is the non-decreasing function defined by F ν (t) = ν([0, t)). Its generalized inverse, denoted by F -1 ν and defined by F -1 ν : m → inf{t ∈ R ; F ν (t) > m} is left-continuous. Notice that if µ, ν are two measures on R + , then ν is a submeasure of µ if and only if F ν (t) F µ (t) for all t > 0.

Proof. Let first remark that if ν is any measure of total mass m 0 , there is only one transport plan between ν and the Dirac mass m 0 δ x , which maps any point of R d to x. Hence, the Wasserstein distance between ν and δ x is given by

W 2 2 (m 0 δ x , ν) = R d h -x 2 dν(h)
Let d x : R d → R denote the distance function to the point x, and let ν x be the pushforward of ν by the distance function to x, i.e. for any subset

I of R, ν x (I) = ν(d -1
x (I)). Using the change-of-variable formula, and the definition of the cumulative function gives us:

R d h -x 2 dν(h) = R + t 2 dν x (t) = m 0 0 F -1 νx (m) 2 dm
If ν is a submeasure of µ, then by the remark above, F νx (t) F µx (t) for all t > 0. From this, one deduces that

F -1 νx (m) F -1 µx (m). This gives W 2 2 (m 0 δ x , ν) = R d h -x 2 dν(h) m 0 0 F -1 µx (m) 2 dm = m 0 0 δ µ,m (x) 2 dm = m 0 d 2 µ,m 0 (x) (3)

INRIA

The second inequality is because F µx (t) = µ(B(x, t)), and thus F -1 µx (m) = δ µ,m (x). This proves that d µ,m 0 (x) is smaller than the right-hand side of (1).

To conclude the proof, we study the cases of equality in [START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF]. Such a case happens when for almost every m m 0 , F -1 νx (m) = F -1 µx (m). Since these functions are increasing and left-continuous, equality must in fact hold for every such m. By the definition of the pushforward, this implies that ν(B(x, δ µ,m 0 (x))) = m 0 , i.e. all the mass of ν is contained in the closed ball B(x, δ µ,m 0 (x)) and μ(B(x, δ µ,m 0 (x))) = µ(B(x, δ µ,m 0 (x))). Because ν is a submeasure of µ, this can be true if and only iff ν belongs in the set R µ,m 0 (x) described before the proof.

To finish the proof, we should remark that the set of minimizer R µ,m 0 (x) always contain a measure µ x,m 0 . The only difficulty is when the boundary of the ball carries too much mass. In this case, we uniformly rescale the mass contained in the bounding sphere so that the measure µ x,m 0 has total mass m 0 . More precisely, we let:

µ x,m 0 = µ| B(x,δµ,m 0 (x)) + (m 0 -µ(B(x, δ µ,m 0 (x))) µ| ∂B(x,δµ,m 0 (x))
µ(∂B(x, δ µ,m 0 (x)))

Stability of the distance function to a measure

The goal of this section is to prove that the notion of distance function to a measure that we defined earlier is stable under change of the measure. This follows rather easily from the characterization of d µ,m 0 given by Proposition 3.3.

Proposition 3.4. Let µ and µ ′ be two probability measures on R d . Then,

d H (Sub m 0 (µ), Sub m 0 (µ ′ )) W 2 (µ, µ ′ )
Proof. Let ε be the Wasserstein distance of order 2 between µ and µ ′ , and π be a corresponding optimal transport plan, i.e. a transport plan between µ and µ ′ such that R d ×R d xy 2 π(x, y)dxdy = ε 2 . Then, given a submeasure ν of µ, one can find a submeasure π ′ of π that transports ν to a submeasure ν ′ of µ ′ . Then,

W 2 (ν, ν ′ ) 2 R d ×R d x -y 2 π ′ (x, y)dxdy ε 2
This shows that dist(ν, Sub m 0 (µ ′ )) ε for every submeasure ν ∈ Sub m 0 (µ).

The same hold by exchanging the roles of µ and µ ′ , thus proving the bound on the Hausdorff distance.

-d µ ′ ,m 0 ∞ 1 √ m 0 W 2 (µ, µ ′ ).
Proof. The following sequence of equalities and inequalities, that follows from Propositions 3.3 and 3.4, proves the theorem:.

d µ,m 0 (x) = 1 √ m 0 dist W 2 (m 0 δ x , Sub m 0 (µ)) 1 √ m 0 (d H (Sub m 0 (µ), Sub m 0 (µ ′ )) + dist W 2 (m 0 δ x , Sub m 0 (µ ′ ))) 1 √ m 0 W 2 (µ, µ ′ ) + d µ ′ ,m 0 (x)
3.4 The distance to a measure is distance-like.

The subdifferential of a function f : Ω ⊆ R d → R at a point x, is the set of vectors v of R d , denoted by ∂ x f , such that for all small enough vector h, f (x + h) f (x) + h|v . This gives a characterization of convexity: a function f : R d → R is convex if and only if its subdifferential ∂ x f is nonempty for every point x. If this is the case, then f admits a derivative at a point x if and only if the subdifferential ∂ x f is a singleton, in which case the gradient ∇ x f coincides with its unique element.

Proposition 3.6. The function v µ,m 0 :

x ∈ R d → x 2 -d 2
µ,m 0 is convex, and its subdifferential at a point x ∈ R d is given by

∂ x v µ,m 0 = 2x - 2 m 0 h∈R d (x -h) dµ x,m 0 (h) ; μx,m 0 ∈ R µ,m 0 (x)
Proof. For any two points x and y of R d , let µ x,m 0 and µ y,m 0 be in R µ,m 0 (x) and R µ,m 0 (y) respectively. Thanks to Proposition 3.3 we have the following sequence of equalities and inequalities:

d 2 µ,m 0 (y) = 1 m 0 h∈R d y -h 2 dµ y,m 0 (h) 1 m 0 h∈R d y -h 2 dµ x,m 0 (h) 1 m 0 h∈R d x -h 2 + 2 x -h|y -x + y -x 2 dµ x,m 0 (h) d 2 µ,m 0 (x) + y -x 2 + v|y -x
where v is the vector defined by

v = 2 m 0 h∈R d [x -h] dµ x,m 0 (h).

INRIA

The inequality can be rewritten as:

( y 2 -d 2 µ,m 0 (y)) -( x 2 -d 2 µ,m 0 (x)) 2x -v|y -x
which shows that the vector (2xv) belongs to the subdifferential of v at x. By the characterization of convex functions by that we recalled above, one deduces that v µ,m 0 is convex. We now turn to the proof of the converse inclusion. This proof is slightly more technical, but not really needed for the remaining of the article. First, let

D µ,m 0 (x) := 2x - 2 m 0 h∈R d (x -h) dµ x,m 0 (h) ; µ x,m 0 ∈ R µ,m 0 (x) .
The sets D µ,m 0 and ∂ x v µ,m 0 are both convex, and we have shown that D µ,m 0 is contained in ∂ x v µ,m 0 . By Theorem 2.5.1 in [START_REF] Clarke | Optimization and nonsmooth analysis[END_REF], the subdifferential ∂ x v µ,m 0 can be obtained as the convex hull of the set of limits of gradients ∇ xn v µ,m 0 , where (x n ) is any sequence of points converging to x at which v µ,m 0 is differentiable. To sum up, we only need to prove that every such limit also belongs to the set D µ,m 0 (x). Let (x n ) be a sequence of points at which v µ,m 0 is differentiable, and let µ n be the unique element in R µ,m 0 (x n ). Necessarily,

∇ xn v µ,m 0 = 2x n -2/m 0 h (x n -h)dµ n (h)
where µ n is in R µ,m 0 (x n ). Since every µ n is a submeasure of µ, by compactness one can extract a subsequence of n such that µ n weakly converges to a measure µ ∞ . This measure belongs to R µ,m 0 (x), and hence the vector

D = 2x -2/m 0 h (x -h)dµ ∞ (h)
is in the set D µ,m 0 (x). Moreover, the weak convergence of µ n to µ ∞ implies that the sequence ∇ xn v µ,m 0 converges to D. This concludes the proof of this inclusion.

Corollary 3.7. The function d 2 µ,m 0 is 1-semiconcave. Moreover, (i) d 2 µ,m 0 is differentiable at a point x ∈ R d if and only if the support of the restriction of µ to the sphere ∂B(x, δ µ,m 0 (x)) contains at most one point;

(ii) d 2 µ,m 0 is differentiable almost everywhere in R d , with gradient defined by

∇ x d 2 µ,m 0 = 2 m 0 h∈R d [x -h] dµ x,m 0 (h)
where µ x,m 0 is the only measure in R µ,m 0 (x).

RR n➦ 6930

(iii) the function x ∈ R d → d µ,m 0 (x) is 1-Lipschitz.
Proof. For (i), it is enough to remark that R µ,m 0 (x) is a singleton iff the support of µ| ∂B(x,δµ,m 0 (x)) is at most a single point. (ii) This follows from the fact that a convex function is differentiable at almost every point, at which its gradient is the only element of the subdifferential at that point.

(iii) The gradient of the distance function d µ,m 0 can be written as:

∇ x d µ,m 0 = ∇ x d 2 µ,m 0 2d µ,m 0 = 1 √ m 0 h∈R d [x -h] dµ x,m 0 (h) ( h∈R d x -h 2 dµ x,m 0 (h)) 1/2
Using the Cauchy-Schwartz inequality we find the bound ∇ x d µ,m 0 1 which proves the statement.

Applications to geometric inference

Reconstruction from point clouds with outliers was the main motivation for introducing the distance function to a measure. In this section, we adapt the reconstruction theorem introduced by [START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF] to our setting. The original version of the theorem states that a regular enough compact set K can be faithfully reconstructed from another close enough compact set C. More precisely, for a suitable choice of r, the offsets C r and K η have the same homotopy type for any positive η. The regularity assumption on K is expressed as a lower bound on its so-called µ-reach, which is a generalization of the classical notion of reach [START_REF] Federer | Curvature measures[END_REF]. In particular, smooth submanifolds, convex sets and polyhedra always have positive µ-reach for suitable µ, hence the reconstruction theorem may be applied to such sets. In these section, we show that the reconstruction results of [START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF] can be easily generalized to compare the sub-level sets of two uniformly-close distance-like functions. It is also possible to adapt most of the topological and geometric inference results of [START_REF] Chazal | Stability of Curvature Measures[END_REF][START_REF] Chazal | Normal cone approximation and offset shape isotopy[END_REF][START_REF] Chazal | Boundary measures for geometric inference[END_REF] in a similar way.

Extending the sampling theory for compact sets

In this paragraph we extend the sampling theory of [START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF] for compact sets to distance-like functions. We don't include all of the results of the paper, but only those that are needed to the reconstruction theorem (Th. 4.6). We refer the interested reader to the original paper for more details.

Let ϕ : R d → R be a distance-like function. The 1-semiconcavity of ϕ 2 allows to define a notion of gradient vector field ∇ x ϕ for ϕ, defined everywhere and satisfying ∇ x ϕ 1. Although not continuous, the vector field ∇ϕ is sufficiently regular to be integrated in a continuous locally Lipschitz flow [START_REF] Petrunin | Semiconcave functions in Alexandrov's geometry[END_REF] Φ t : R d → R d . The flow Φ t integrates the gradient ∇ϕ in the sense that for every x ∈ R d , the curve γ : t → Φ t (x) is right-differentiable, and for every t > 0, dγ dε t -= ∇ γ(t) ϕ . Moreover, for any integral curve γ : [a, b] → R d parametrized by arc-length, one has:

ϕ(γ(b)) = ϕ(γ(a)) + b a ∇ γ(t) ϕ dt.
Definition 4.1. Let ϕ be a distance like function. Following the notation for offset of compact sets, we will denote by ϕ r = ϕ -1 ([0, r]) the r sublevel set of ϕ.

(i) A point x ∈ R d will be called α-critical (with α ∈ [0, 1]) if the inequality ϕ 2 (x + h) ϕ 2 (x) + 2α h ϕ(x) + h 2 is true for all h ∈ R d . A 0-critical point is simply called a critical point. It follows from the 1-semiconcavity of ϕ 2 that ∇ x ϕ is the infimum of the α 0 such that x is α-critical.

(ii) The weak feature size of ϕ at r is the minimum r ′ > 0 such that ϕ doesn't have any critical value between r and r + r ′ . We denote it by wfs ϕ (r). For any 0 < α < 1, the α-reach of ϕ is the maximum r such that ϕ -1 ((0, r]) does not contain any α-critical point. Obviously, the α-reach is always a lower bound for the weak-feature size, with r = 0.

The proof of the Reconstruction Theorem in [START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF] relies on two important observations. The first one is a consequence of a distance-like version of Grove's isotopy lemma [START_REF] Grove | Critical point theory for distance functions[END_REF]Prop. 1.8], which asserts that the topology of the sublevel sets of ϕ can only change when one passes critical values. As in [START_REF] Chazal | Stability and Computation of Topological Invariants of Solids in R n[END_REF]Theorem 3], one deduces that the offsets of two uniformly close distancelike functions with large weak feature size have the same homotopy type: Proposition 4.2 (Isotopy lemma). Let ϕ be a distance-like function and r 1 < r 2 be two positive numbers such that ϕ has no critical points in the subset ϕ -1 ([r 1 , r 2 ]). Then all the sublevel sets ϕ -1 ([0, r]) are isotopic for r ∈ [r 1 , r 2 ]. Proposition 4.3. Let ϕ and ψ be two distance-like functions, such that ϕψ ∞ ε. Suppose moreover that wfs ϕ (r) > 2ε and wfs ψ (r) > 2ε. Then, for every 0 < η 2ε, ϕ r+η and ψ r+η have the same homotopy type.

Proof. See Appendix.

The second key observation made in [START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF] is that the critical points of a distance function are stable in certain sense under small Hausdorff perturbations. This result remains true for uniform approximation by distance-like functions: Proposition 4.4. Let ϕ and ψ be two distance-like functions with ϕψ ∞ ε. For any α-critical point x of ϕ, there exists a α ′ -critical point x ′ of ψ with xx ′ 2 εϕ(x) and α ′ α + 2 ε/ϕ(x).

Proof. The proof is almost verbatim from [START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF], and postponed to the Appendix.

Corollary 4.5. Let ϕ and ψ be two ε-close distance-like functions, and suppose that reach α (ϕ) R for some α > 0. Then, ψ has no critical value in the interval 4ε/α 2 , R -3ε .

Proof. See Appendix.

Theorem 4.6 (Reconstruction). Let ϕ, ψ be two ε-close distance-like functions, with reach α (ϕ) R for some positive α. Then, for any r ∈ [4ε/α 2 , R-3ε], and for 0 < η < R, the sublevel sets ψ r and ϕ η are homotopy equivalent, as soon as ε R 5 + 4/α 2 Proof. By the isotopy lemma, all the sublevel sets ψ r have the same homotopy type, for r in the given range. Let us choose r = 4ε/α 2 . We have: wfs ϕ (r) R -4ε/α 2 and wfs ψ (r) R -3ε -4ε/α 2 By Proposition 4.3, the sublevel sets ϕ r and ψ r have the same homotopy type as soon as the uniform distance ε between ϕ and ψ is smaller than 1 2 wfs ϕ (r) and 1 2 wfs ψ (r). This is true, provided that 2ε Rε(3 + 4/α 2 ). The theorem follows.

Remark that in the above definition 4.1 the notion of α-reach could be made dependent on a parameter r, i.e. the (r, α)-reach of ϕ could be defined as the maximum r ′ such that the set ϕ -1 ((r, r + r ′ ]) does not contain any α-critical value. A reconstruction theorem similar to Theorem 4.6 would still hold under the weaker condition that the (r, α)-reach of ϕ is positive. (i) We say that a non-decreasing positive function f : R + → R + is a uniform lower bound on the growth of µ if for every point p in the support of µ and every ε > 0, µ(B(p, ε)) f (ε) ;

(ii) The measure µ has dimension at most k if there is a constant C(µ) such that f (ε) = C(µ)ε k is a uniform lower bound on the growth of µ, for ε small enough.

m 0 0 δ 2 µ,m (x)dm m 0 (d S (x) + ε) 2 .
Taking the square root of this expression proves the lemma. Corollary 4.8. (i) If the support S of µ is compact, then d S is the uniform limit of d µ,m 0 as m 0 converges to 0;

(ii) If the measure µ has dimension at most k > 0, then

d µ,m 0 -d S C(µ) -1/k m 1/k 0 Proof. (i) If S is compact, there exists a sequence x 1 , x 2 , • • • of points in S such that for any ε > 0, S ⊆ ∪ n i=1 B(x i , ε/2) for some n = n(ε)
. By definition of the support of a measure, η(ε) = min i=1•••n µ(B(x i , ε/2)) is positive. Now, for any point x ∈ S, there is a x i such that xx i ε/2. Hence, B(x i , ε/2) ⊆ B(x, ε), which means that µ(B(x, ε)) η(ε). (ii) Follows straightforwardly from the Lemma.

For example, the uniform probability measure on a k-dimensional compact submanifold S has dimension at most k. The following proposition gives a more precise convergence speed estimate based on curvature. Notice in particular that the convergence speed of d µ,m 0 to d S depends only on the intrinsic dimension k of the submanifold S, and not on the ambient dimension d. In order to prove this result, we make use of the Günther-Bishop theorem (cf [14, ➜3.101]).

Theorem 4.10 (Günther-Bishop). If the sectional curvatures of a Riemannian manifold M do not exceed δ, then for every x ∈ M , H k (B M (x, r)) β k,δ (r) where β k,δ (r) is the volume of a ball of radius r in the simply connected k-dimensional manifold with constant sectional curvature δ, provided that r is smaller than the minimum of the injectivity radius of M and π/ √ δ.

Proof of Proposition 4.9. Since the intrinsic ball B S (x, ε) is always included in the Euclidean ball B(x, ε) ∩ S, the mass µ(B(x, ε)) is always larger than H k (B S (x, ε))/H k (S). Remarking that the sectional curvature of M is upperbounded by 1/R 2 , Günter-Bishop theorem implies that for any ε smaller than the injectivity radius of S and πR, µ(B(x, ε))

β k,1/R 2 (ε) H k (S)
Hence µ has dimension at most k. Moreover, by comparing the volume of an intrinsic ball of the unit sphere and the volume of its orthogonal projection on the tangent space to its center, one has:

β k,1/R 2 (ε) = R k β k,1 (ε/R) R k [sin(ε/R)] k β k
where β k is the volume of the k-dimensional unit ball. Using sin(α) 2 π α gives the announced value for C(S).

Shape reconstruction from noisy data

The previous results lead to shape reconstruction theorems from noisy data with outliers. To fit in our framework we consider shapes that are defined as supports of probability measures. Let µ be a probability measure of dimension at most k > 0 with compact support K ⊂ R d and let d K : R d → R + be the (Euclidean) distance function to K. If µ ′ is another probability measure (eg. the empirical measure given by a point cloud sampled according to µ),

INRIA one has d K -d µ ′ ,m 0 ∞ d K -d µ,m 0 ∞ + d µ,m 0 -d µ ′ ,m 0 ∞ (4)
C(µ) -1/k m 1/k 0 + 1 √ m 0 W 2 (µ, µ ′ ) (5)
This inequality insuring the closeness of d µ ′ ,m 0 to the distance function d K for the sup-norm follows immediately from the stability theorem 3.5 and the corollary 4.8. As expected, the choice of m 0 is a trade-off: small m 0 lead to better approximation of the distance function to the support, while large m 0 make the distance functions to measures more stable. Eq. 4 leads to the following corollary of Theorem 4.6:

Corollary 4.11. Let µ be a measure and K its support. Suppose that µ has dimension at most k and that reach α (d K ) R for some R > 0. Let µ ′ be another measure, and ε be an upper bound on the uniform distance between d K and d µ ′ ,m 0 . Then, for any r ∈ [4ε/α 2 , R -3ε], the r-sublevel sets of d µ,m 0 and the offsets K η , for 0 < η < R are homotopy equivalent, as soon as:

W 2 (µ, µ ′ ) R √ m 0 5 + 4/α 2 -C(µ) -1/k m 1/k+1/2 0
Figure 1 illustrates the reconstruction Theorem 4.6 on a sampled mechanical part with 10% of outliers. In this case µ ′ is the normalized sum of the Dirac measures centered on the data points and the (unknown) measure µ is the uniform measure on the mechanical part.

Relation with non-parametric density estimation

Nearest-neighbor estimators are a family of non-parametric density estimators, that has been extensively used in nonparametric discrimination, pattern recognition and spatial analysis problems. Suppose that C is a point cloud whose points are independently drawn with respect to a probability measure µ on R d which admits a densiy f with respect to the Lebesgue measure. Nearest neighbors estimators estimate the density function by:

f (x) = k #Cω d (δ C,k (x)) (6)
where ω d (r) is the volume of the d-sphere of radius r, and δ C,k denotes the distance to the kth nearest neighbor in C. Our claim in this section is that or some of the applications where density estimators are used (such as mean shift, see below), distance to measure functions could also be used as well. The advantages of the distance function d µ,m 0 over nearest-neighbor density estimators are multiple. First of all, they are well defined even when the underlying probability measure does not have a density with respect to the Lebesgue measure, e.g. if it is concentrated on a lower-dimensional subset. Second, the distance to measure d µ,m 0 is always uniformly stable with respect to Wasserstein perturbations of the data. Third, because of its 1-semiconcavity, the distance function d µ,m 0 is much more regular than the distance δ µ,m 0 , as illustrated by Figure 5. This has consequences for gradient descent algorithms such as mean shift. As a consequence of this regularity, it is possible to prove higher order convergence properties of d µn,m 0 to d µ,m 0 as µ n converges to µ. For example, it can be shown that ∇d µn,m 0 converges to ∇d µ,m 0 as locally integrable vector fields. Pointwise convergence results can also be obtained at points where ∇d µ,m 0 is bounded away from 0.

Mean-Shift Methods using Distance Functions

Kernel-based mean-shift clustering. Mean-shift clustering [START_REF] Comaniciu | Mean shift: a robust approach toward feature space analysis[END_REF] is a non-parametric clustering method that works on point cloud drawn from an unknown probability measure with density. Specifically, one is given a point cloud C ⊆ R d and a radial kernel K. The underlying probability density is estimated by:

f (x) = 1 h d #C p∈C K p -x h
where h is a given bandwidth parameter. Starting from a point x in the space, one iteratively constructs a sequence of points (x i ), descending the gradient of the estimated density:

     x 0 = x x i+1 = p∈C K p-x h p p∈C K p-x h (7)
The clustering method works as follows: for each point x 0 in the point cloud, one iterates the sequence x i until convergence. This defines a mapping from C to the set of critical points of the kernel-based density estimate. A cluster of C is simply the set of points of C which correspond to the same critical point under this mapping.

Distance-based mean-shift. We propose a method similar to mean shift, but where the distance function replaces the estimated density. Our iterative scheme is a simple gradient descent for the squared distance function:

   x 0 = x x i+1 = x i - 1 2 ∇ x i d 2 µ,m 0 (8)
In practice, µ is the uniform probability measure on a point cloud C and m 0 = k 0 /#C. In this context, x i+1 is simply the isobarycenter of the k 0 nearest neighbor of x i in C:

x i+1 = x i - 1 k k 0 k=1 (x i -p k C (x i )) = 1 k k 0 k=1 p k C (x i ) Proposition 5.1. Let x be a point in R d and x t = x -t 2 ∇ x i d 2 µ,m 0 . Then, 1. d µ,m 0 (x t ) d µ,m 0 (x) 2. ∇ xt d 2 µ,m 0 |∇ x 0 d 2 µ,m 0 0 RR n➦ 6930
Proof. 1. This is a simple application of Prop. Both properties indicate good convergence properties for our iterative scheme: the first one prevents any infinite loop, while the second shows that trajectories are not too wiggly (more precisely, consecutive edges never make an acute angle). The first property of this proposition had been proved for classical mean-shift, when the kernel K has convex and monotonically decreasing profile (Theorem 1 in [START_REF] Comaniciu | Mean shift: a robust approach toward feature space analysis[END_REF]). On the other hand, the second property is shown to hold for mean-shift when K is Gaussian (Theorem 2 in [START_REF] Comaniciu | Mean shift: a robust approach toward feature space analysis[END_REF]), in which case it is not convex. We are not aware of any choice of kernel such that the resulting mean-shift scheme satisfies these two properties simultaneously.

Discussion

We have extended the notion of distance function to a compact subset of R d to the case of measures, and showed that this permits to reconstruct sampled shapes with the correct homotopy type even in the presence of outliers. It also seems very likely that a similar statement showing that the sublevel sets of d µ,m 0 are isotopic to the offsets of K can be proved, using the same sketch of proof as in [START_REF] Chazal | Normal cone approximation and offset shape isotopy[END_REF]. Moreover, in the case of point clouds/empirical measures (finite sums of Dirac measures), the computation of the distance function to a measure (and its gradient) at a given point boils down to a computation of nearest neighbors making it easy to use in practice. However, we note that in the important case where the unknown shape is a submanifold, our reconstructions are clearly not homeomorphic since they do not have the correct dimension. Is there a way to combine our framework with the classical techniques developped for homeomorphic surface reconstruction (see e.g. [START_REF] Amenta | A simple algorithm for homeomorphic surface reconstruction[END_REF]) to make them robust to outliers while retaining their guarantees?

INRIA

It follows from the isotopy lemma 4.2 that the inclusions a 0 , a 1 , b 0 and b 1 are homotopy equivalences. Let s 0 , s 1 , r 0 and r 1 be homotopic inverses of a 0 , a 1 , b 0 and b 1 respectively. Now a straightforward computation shows that c 1 is an homotopy equivalence with homotopic inverse r 1 • d 1 • s 1 :

c 1 • r 1 • d 1 • s 1 ∼ = c 1 • (r 1 • b 1 ) • d 0 • s 0 • s 1 ∼ = (c 1 • d 0 ) • s 0 • s 1 ∼ = a 1 • a 0 • s 0 • s 1 ∼ = id ϕ r+δ+2ε
Similarly, we get r 1 • d 1 • s 1 • c 1 ∼ = id ψ r+δ+ε proving the proposition 4.3.

Proof of Proposition 4.4 Let ρ > 0 and let γ be an integral curve of the flow defined by ∇ψ, starting at x and parametrized by arclength. If γ reaches a critical point of ψ before length ρ, we are done. Assume this is not the case. Then, with y = γ(ρ), one has ψ(y)ψ(x) = ρ 0 ∇ γ(t) ψ dt. As a consequence, there exists a point p(ρ) on the integral curve such that ∇ p(ρ) ϕ 1 ρ (ϕ(y)ϕ(x)). Now, by the assumption on the uniform distance between ϕ and ψ, ψ(y) ϕ(y) + ε and ψ(x) ϕ(x)ε. Using the fact that x is α-critical, one obtains: ϕ(y) 2 ϕ(x) 2 + 2α xy ϕ(x) + xy 2 ie. ϕ(y) ϕ(x) 1 + 2α

xy ϕ(x) + xy 2 ϕ(x) 2 1/2 ϕ(x) + α xy + 1 2

xy 2 ϕ(x)

Putting things together, we get ∇ p(ρ) ϕ α + 2ε ρ + 1 2 ρ ϕ(x) . The minimum of this upper bound is α + 2 ε/ϕ(x) and is attained for ρ = 2 εϕ(x). This concludes the proof.

Proof of Corollary 4.5 Assume that there exists a critical point x of ψ such that ψ(x) belongs to the range [4ε/α 2 , R ′ ]. Then, there would exist an α ′ -critical point y of ϕ at distance at most D of x. By the previous proposition, α ′ 2 ε/ψ(x) 2 ε/(4ε/α 2 ) = α and D 2 √ εR ′

Hence, using the fact that x is a critical point for ψ, ϕ(y) ψ(y) + ε ψ 2 (x) + xy 2 1/2

+ ε R ′ 1 + D 2 /R ′ 2 1/2 + ε R ′ + 3ε
This last term is less than R if R ′ < R -3ε. With these values, one gets the desired contradiction.

Theorem 3 . 5 (

 35 (Distance function stability)). If µ and µ ′ are two probability measures on R d and m 0 > 0, then d µ,m 0

Figure 1 :

 1 Figure 1: On the left, a point cloud sampled on a mechanical part to which 10% of outliers (uniformly sampled in a box enclosing the model) have been added. On the right, the reconstruction of an isosurface of the distance function d µ C ,m0 to the uniform probability measure on this point cloud.

INRIA

INRIA

4. 2

 2 Distance to a measure vs. distance to its support In this paragraph, we compare the distance functions d µ,m 0 to a measure µ and the distance function to its support S, and study the convergence properties as the mass parameter m 0 converges to zero. A first obvious remark is that the pseudo-distance δ µ,m 0 (and hence the distance d µ,m 0 ) is always larger than the regular distance function d S . As a consequence, to obtain a convergence result of d µ,m 0 to d S as m 0 goes to zero, it is necessary to upper bound d µ,m 0 by d S + o(m 0 ). It turns out that the convergence speed of d µ,m 0 to d S depends on the way the mass of µ contained within any ball B(p, r) centered at a point p of the support decreases with r. Let us define:

Lemma 4 . 7 .

 47 Let µ be a probability measure and f be a uniform lower bound on the growth of µ. Then d µ,m 0d S ∞ < ε as soon as m 0 < f (ε). Proof. Let ε and m 0 be such that m 0 < f (ε) and let x be a point in R d , p a projection of x on S, i.e. a point p such that xp = d(p, S). By assumption, µ(B(x, d S (x) + ε)) µ(B(p, ε)) m 0 . Hence, δ µ,m 0 (x) d S (x) + ε. The function m → δ µ,m (x) being non-decreasing, we get: m 0 d 2 S (x)

Proposition 4 . 9 .

 49 Let S be a smooth k-dimensional submanifold of R d whose curvature radii are lower bounded by R, and µ the uniform probability measure on S, then d Sd µ,m 0 C(S) -1/k m 1/k 0 for m 0 small enough and C(S) = (2/π) k β k /H k (S) where β k is the volume of the unit ball in R k .

Figure 2 :

 2 Figure 2: The distance functions to an empirical measure µ associated to a 600 points 2D data set P sampled independently according two gaussians (first figure). The second and third figures represent close-ups on the level sets of the functions d µ,1/30 and δ µ,1/30 respectively, illustrating the difference of regularity between the two distance functions.

INRIA

Figure 3 :

 3 Figure 3: Distance-based mean-shift followed by k-Means clustering on the point cloud made of LUV colors of the pixels of the picture on the right.

3 . 3 .( 1 ). 2 . 2 µ,m 0 = 2 t x -y 2 - t 2 ∇ x d 2 µ,m 0 |∇ y d 2 µ,m 0 2 µ,m 0 4 t 1 t

 33122222021 Since d 2 µ,m 0 is 1-concave, x -y|∇ x d 2 µ,m 0 (x) -∇ x d 2 µ,m 0 (y) 2 xy 2 Now, if we set y = x t , x -y|∇ x d 2 µ,m 0 -∇ y d 2 µ,m 0 = x -y|∇ x d 2 µ,m 0x -y|∇ y d This proves that ∇ x d 2 µ,m 0 |∇ xt d -1 xy 2 .

RR n➦ 6930

Appendix

Proof of Proposition 4.3 Let δ > 0 be such that wfs ϕ (r) > 2ε + δ and wfs ψ (r) > 2ε + δ. Since ϕψ ∞ ε, we have the following commutative diagram where each map is an inclusion.


Thai V Hoang
email: vanthai.hoang@loria.frtabbone@loria.fr

Salvatore Tabbone

Text Extraction From Graphical Document Images Using Sparse Representation

Keywords: I.4.6 [Image Processing and Computer Vision]: Segmentation, I.5.4 [Pattern Recognition]: Applicationstext processing, I.7.1 [Document and Text Processing]: Document Capture-document analysis, graphics recognition and interpretation Design, Documentation, Experimentation graphics separation, sparse representation, morphological component analysis, curvelet transform, redundant wavelet transform, text component grouping

A novel text extraction method from graphical document images is presented in this paper. Graphical document images containing text and graphics components are considered as two-dimensional signals by which text and graphics have different morphological characteristics. The proposed algorithm relies upon a sparse representation framework with two appropriately chosen discriminative overcomplete dictionaries, each one gives sparse representation over one type of signal and non-sparse representation over the other. Separation of text and graphics components is obtained by promoting sparse representation of input images in these two dictionaries. Some heuristic rules are used for grouping text components into text strings in post-processing steps. The proposed method overcomes the problem of touching between text and graphics. Preliminary experiments show some promising results on different types of document.

INTRODUCTION

Text extraction from graphical document images is a major problem in document image analysis in which one document input image containing both text and graphics is processed to produce two output images, one containing text and the other containing graphics. Extracting text is an important task since text has semantic meaning which could be obtained by a character recognition system. Extraction of semantic meaning from the extracted text can be done easily with the help of an OCR engine. A reliable extraction method is required to make it usable in automatic document processing systems. At present, applications of such text extraction algorithm are automatic processing of texture documents and architectural/engineering drawings, automatic reading of postal addresses and flexible forms, etc.

The remainder of this paper is organized as follows. Section 2 reviews some related works and briefly highlights the contribution of the proposed method. Some background on sparse representation of signals is given in Section 3. Section 4 presents the decomposing algorithm and dictionary selection. Post-processing steps on the text image are discussed in Section 5. Experimental results are given in Section 6, and finally conclusions are drawn in Section 7.

THE PROBLEM OF TEXT EXTRACTION FROM GRAPHICAL DOCUMENT IMAGES

A document image usually contains text and graphics components. The types of graphics component vary according to each specific application domain but generally they include lines, curves, polygons, circles. Text components consist of characters and digits which form words and phrases used to annotate the graphics. Extraction of text components is a challenging problem because:

-Graphical components like lines can be of any length, thickness, and orientation. Circles, polygons can be filled or unfilled. Text components can vary in font styles and sizes.

-There may exist touching among text components and touching, crossing between text and graphics components. Text strings are usually intermingled with graphics and are of any orientation.

-Excluding the pre-processing steps to enhance the image quality, text extraction is mostly the first step in the chain of document analysis with limited knowledge about the presence of high-level objects in the images.

Prior work

Many methods have been proposed to tackle the problem of text extraction from graphics-containing documents which can be roughly divided into three main families: morphological analysis, connected component analysis, and multiresolution analysis.

Run-Length Smoothing Algorithm (RLSA) proposed by Wahl et al. [START_REF] Wahl | Block segmentation and text extraction in mixed text/image documents[END_REF] is one of the first and best known methods based on morphological filtering to detect long vertical and horizontal text strings. It essentially consists of morphological closing operations with horizontal and vertical structuring elements of specified length. Although RLSA and its improvement [START_REF] Le | Classification of binary document images into textual or nontextual data blocks using neural network models[END_REF] are very efficient for textual documents, its use in graphics-rich documents [START_REF] Lai | 4: Experimental results on text/graphics separation (a) Image 1: Original image (b) Image 6: Original image (c) Image 7: Original image (d) Image 1: Grouped strings (e) Image 6: Grouped strings (f) Image 7: Grouped strings Figure 5: Experimental results on grouping text strings in engineering drawings[END_REF][START_REF] Lu | Detection of text regions from digital engineering drawings[END_REF] is limited as text could be wrongly labeled as graphics.

A well-known approach based on connected component analysis was proposed by Fletcher and Kasturi [START_REF] Fletcher | A robust algorithm for text string separation from mixed text/graphics images[END_REF] using some heuristic rules on area, dimension ratio and collinearity of connected components to separate text from graphics. Simplicity and scalability are the strength of this approach which make it widely used. Its weakness is the inability to directly separate text which touches graphics. Tombre et al. [START_REF] Tombre | Text/graphics separation revisited[END_REF] tried to overcome this and got some improvements for graphics-rich document images by incorporating some more heuristic rules.

Multi-resolution approach was first proposed by Deforges and Barba [START_REF] Deforges | A robust and multiscale document image segmentation for block line/text line structures extraction[END_REF] for mail pieces and then adapted to map by Tan and Ng [START_REF] Tan | Text extraction using pyramid[END_REF]. It relies on the assumption that at a certain coarse level of the image pyramid, a text line looks like a long component and at the next finer level it looks like a regular sequence of transitions. However, when text and graphics components lie closely or touch, this approach induces wrong detection results.

Some methods have been proposed dealing with the case of touching between text and graphics components. They usually separate text from graphics by detecting touching lines. Gloger [START_REF] Gloger | Use of the Hough transform to separate merged text/graphics in forms[END_REF] uses Hough transform to detect vertical and horizontal lines to recognize form structure. Lu [START_REF] Lu | Detection of text regions from digital engineering drawings[END_REF] detects slant lines in engineering drawings by first stretching the document to certain angles and then tracing black pixels horizontally and vertically. Luo and Kasturi [START_REF] Luo | Improved directional morphological operations for separation of characters from maps/graphics[END_REF] use directional morphological filtering to locate linear shapes in simple maps. Cao and Tan [START_REF] Cao | Text/graphics separation in maps[END_REF] work on a skeletonized version of a map and consider short and long skeleton segments as skeletons of text and graphics components respectively. Recently, Su et al. [START_REF] Su | A character segmentation method for engineering drawings based on holistic and contextual constraints[END_REF] rely on a vectorization method [START_REF] Song | An object-oriented progressive-simplification-based vectorization system for engineering drawings: model, algorithm, and performance[END_REF] to remove touching lines in engineering drawings.

Each of the above methods dealing with touching is initially designed for a specific application so it is not robust and inapplicable to graphical images from other applications. For example, with a graphics-rich and complex engineering document image as showed in Fig. 1(a), none of the above methods provide reliable results. Thus a novel method needs to be developed for these kinds of complex graphical document.

The proposed method

The method proposed in this paper extracts texts components in a totally different way from the above. A document image y containing text and graphics components is considered as a two-dimensional signal which is the mixture of two separate two-dimensional signals (images) of the same size:

yt containing text components and yg containing graphics components. The problem of text extraction is now seen as the problem of recovery of yt and yg from y. This is actually the blind source separation problem in multi-dimensional signal processing [START_REF] Jutten | Blind separation of sources, part 1: an adaptive algorithm based on neuromimetic architecture[END_REF].

To solve this, we employ the Morphological Component Analysis (MCA) method proposed by Starck et al. [START_REF] Starck | Image decomposition via the combination of sparse representations and a variational approach[END_REF]. MCA allows the separation of features contained in an image when these features present different morphological aspects. This is facilitated by promoting sparse representation of these features in two appropriately chosen dictionaries, each leads to sparse representation over one feature and non-sparse representation over the other.

Having done in this way, some post-processing steps could be needed to extract text strings from yt. This is done with the help of some heuristic rules based on the discriminative characteristics of text components. The proposed method is thus robust to touching between text and graphics. Furthermore, text components can be placed anywhere with any orientation in the documents. They can be in any form, have any font style and size.

SPARSE REPRESENTATION OF SIGNALS OVER AN OVERCOMPLETE DICTIONARY

The idea of sparse representation has its root in mammalian vision system. The receptive fields of simple cells in mammalian primary visual cortex can be characterized as being spatially localized, oriented, and bandpass (selective to structure at different scales), comparable to the basis functions of wavelet transforms, and having a strategy for producing a sparse distribution of output activity in response to natural images [START_REF] Olshausen | Emergence of simple-cell receptive field properties by learning a sparse code for natural images[END_REF]. Olshausen and Field [START_REF] Olshausen | Sparse coding with an overcomplete basis set: a strategy employed by V1?[END_REF] validated this theory by considering the problem of efficient coding of natural images. They showed that when the code dictionary is overcomplete (the number of code elements is greater than the dimensionality of the input) and non-orthogonal, a coding strategy maximizing sparseness (a small number of code elements are non-zero) will select only codes necessary for representing a given input. According to Barlow's principle of redundancy reduction [START_REF] Barlow | Unsupervised learning[END_REF], the resulting sparse code thus provides an efficient representation for later processing.

The above idea can be formulated mathematically. Given an input image y of size w × h which is casted as a vector b ∈ R n (n = wh) by stacking its columns, an overcomplete dictionary A ∈ R n×K with n K allowing sparse representation of b, let x be the representation of b in A satisfying b = Ax then finding the sparse representation x of b in A is equivalent to solving the following 0-optimization problem:

min x x 0 subject to Ax = b (1)
where . 0 is the 0 norm, counting the nonzero entries of a vector. The overcomplete dictionary A that leads to sparse representation of an input signal b can either be designed by adapting its content to fit a given set of signal examples [START_REF] Aharon | K-SVD: an algorithm for designing overcomplete dictionaries for sparse representation[END_REF] or chosen as a specified set of signals by means of undecimated wavelet transform, Fourier transform, shorttime Fourier transform, Gabor transform, curvelet transform, steerable wavelet transform, etc.

Finding the sparsest solution of an under-determined system of linear equations like (1) is N P -hard [START_REF] Davis | Adaptive greedy approximations[END_REF]. However, recent results [START_REF] Donoho | For most large underdetermined systems of linear equations the minimal 1-norm solution is also the sparsest solution[END_REF] show that if the solution of Eq. ( 1) is sufficiently sparse, it is equal to the solution of the following 1-optimization problem: min

x x 1 subject to Ax = b. (2)
If the condition b = Ax is relaxed by b = Ax + z, where z ∈ R n is a noise term with z 2 < ε, to account for the possible inclusion of small dense noise in the input image y or allow small error in the representation, Eq. ( 2) will be modified to be:

min x x 1 subject to Ax -b 2 ≤ ε. (3)
This is a convex optimization problem, its solution can be found by minimizing the corresponding Lagrangian function:

min x 1 2 Ax -b 2 + λ x 1, (4)
where the parameter λ is a Lagrange multiplier that balances the sparseness in x1 and the representation error, the value of λ depends on ε. This problem is known to be efficiently solved via second-order cone programming [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF].

SEPARATION OF TEXT AND GRAPH-ICS COMPONENTS USING MORPHO-LOGICAL COMPONENT ANALYSIS

MCA method is a further development of the framework represented in the previous section dealing with the problem of separating an image content into semantic parts. MCA has shown to be very useful for decomposing images into texture and piece-wise smooth (cartoon) parts or for inpainting applications [START_REF] Elad | Simultaneous cartoon and texture image inpainting using morphological component analysis (MCA)[END_REF][START_REF] Fadili | Inpainting and zooming using sparse representations[END_REF]. In document image analysis, MCA has been adopted by Pan et al. [START_REF] Pan | Text segmentation from complex background using sparse representations[END_REF] to segment text from complex background. The application of MCA to a new application domain, text/graphics separation, is presented in this paper and is followed by some post-processing steps proposed uniquely for this kind of application.

Morphological Component Analysis

Let a signal b ∈ R n be a linear combination of two parts, b = b1 + b2 where b1 and b2 represent two different types of signal. Assume that there exist two overcomplete dictionaries A1, A2 ∈ R n×K satisfying two conditions:

1. Solving (for i = 1, 2)

min x i xi 1 subject to Aixi = bi, (5)
leads to a sparse representation xi of bi in Ai.

2. Solving (for i = j)

min x i xi 1 subject to Ajxi = bi, (6)
leads to a non-sparse representation xi of bi in Aj.

In this case, two dictionaries A1, A2 are said to be discriminative in the sense of sparse representation to different content types. MCA method thus proposes to solve the following optimization problem: min

x 1 ,x 2 ( x1 0 + x2 0) subject to A1x1 + A2x2 = b, (7)
which can be converted to: min

x 1 ,x 2 ( x1 1 + x2 1 + λ b -A1x1 -A2x2 2) . (8)
Solving Eq. ( 8) gives x1 and x2, the sparse representations of b1 and b2 in A1 and A2 respectively. This also means that the original signal b has been separated into two parts A1 x1 and A2 x2 which are in turn the approximations of b1 and b2 respectively. For this problem structure, Block-Coordinate Relaxation (BCR) method by Sardy et al. [START_REF] Sardy | Block coordinate relaxation methods for nonparametric wavelet denoising[END_REF] provides fast numerical computation that requires only the use of matrixvector multiplications with the unitary transforms and their inverses. BCR was developed based on the shrinkage method of Donoho and Johnstone [START_REF] Donoho | Ideal spatial adaptation by wavelet shrinkage[END_REF].

Dictionary selection

The success of MCA is guaranteed if the two conditions stated in Eqs. ( 5) and ( 6) are satisfied. Thus, selecting two appropriate dictionaries A1 and A2 is essential in applying MCA for signal separation. For numerical reasons, A1 and A2 should also have fast forward and inverse implementations. Our approach here is to choose these dictionaries from existing transforms based on experience. Curvelet transform [START_REF] Candès | New tight frames of curvelets and optimal representations of objects with piecewise C 2 singularities[END_REF] is used as the dictionary for graphics and the undecimated wavelet transform is used as the dictionary for text.

Undecimated wavelet transform

Undecimated wavelet transform (UWT) is the undecimated version of the orthogonal wavelet transform (OWT) obtained by skipping the decimation step. It is designed to overcome the lack of shift-invariance property in OWT. UWT, not like OWT, can be represented as a transformation matrix with more columns than rows. The redundancy factor (the ratio between the number of columns to the number of rows) is 3J + 1, where J is the number of scales. UWT is expected to give sparse representation of isotropic features and nonsparse representation to highly anisotropic features. The "à trous" algorithm by Shensa [START_REF] Shensa | The discrete wavelet transform: wedding the à trous and Mallat algorithms[END_REF] provides an efficient way to implement forward and inverse UWT.

Curvelet transform

Defining two smooth, non-negative, and real-valued functions W (r) and V (t) (the radial angular windows) which are supported on [1/2, 2] and [-1, 1] respectively satisfying the admissibility conditions with r > 0 and t ∈ R:

∞ j=-∞ W 2 2 j r = 1, ∞ l=-∞ V 2 (t -l) = 1. (9)
At each scale j, define the mother curvelet ϕj as:

φj(r, θ) = 2 -3j/4 W 2 -j r V 2 j/2 θ 2π . (10)
A curvelet at scale j, orientation θ l , and position x j,l k = R -1 θ l 2 -j k1, 2 -j/2 k2 is defined as:

ϕ j,l,k (x) = ϕj R θ l x -x j,l k , (11)
where R θ l is the rotation operator by θ l = 2π2 j/2 l radians with l ∈ Z + such that 0 ≤ l < 2π. The corresponding

c j,l,k = f, ϕ j,l,k = R 2 f (x)ϕ j,l,k (x)dx. ( 12
)
Curvelets constructed in this way are multi-scale, multidirectional, and elongated. They define a tight frame in L 2 R 2 , exhibit an oscillating behavior in the direction perpendicular to their orientation, and obey the parabolic scaling relation (width = length 2 ). A curvelet frame can be used as an overcomplete dictionary with a redundancy factor of 16J +1, where J is the number of scales. It is expected to give sparse representation to anisotropic structures and smooth curves and edges of different lengths.

Text image extraction

Supposed that an input document image y can be decomposed into two images of the same size as y: yt containing text components and yg containing graphics components.

Applying MCA on y with UWT and curvelet transform as the two overcomplete dictionaries will result in ỹt and ỹg which are approximations of yt and yg respectively. Assuming that y takes the graphical image in Fig. 1(a), ỹt and ỹg are given in Figs. 1(b) and 1(c) respectively.

The obtained results in Figs. 1(b) and 1(c) show that text and graphics components are not totally separated. There are two reasons for this:

-There exists an overlap between the two dictionaries, both consider the low-frequency content as theirs and both can represent it efficiently.

-Some graphics (like arrowheads, short curve segments) have morphological characteristics that are similar to those of text components. These graphics may appear in the text image.

To minimize the effect of these ambiguities (i.e. the overlapping between the two dictionaries and the similarity between features), post-processing steps presented in the next section are proposed to combine the extracted text components into text strings.

GROUPING TEXT COMPONENTS INTO TEXT STRINGS

The text image in Fig. 1(b) is converted to binary in Fig. 1(d) by adaptive thresholding [START_REF] Gonzalez | Digital Image Processing[END_REF]. Fig. 1(e) is obtained by removing small connected components from Fig. 1(d). It is acknowledged that small text components like '•', ':' are also removed, however, as these components lie inside the enclosing rectangles of text strings, they can be retrieved later. gorithms based on Hough transform on the centroids on connected components [START_REF] Fletcher | A robust algorithm for text string separation from mixed text/graphics images[END_REF][START_REF] Tombre | Text/graphics separation revisited[END_REF] can be used in this case. However, to be robust, the grouping algorithm should be dependent on the style of text that exists in graphical document images. We propose here a new efficient method to group text components in straight fonts with a belief that a large part of text in graphical document images is typeset in straight font style. Heuristic criteria used are: neighborhood, inter-distance, orientation, and overlapping.

Connected components remaining in

Neighborhood. Text components belonging to a text string need to be neighbors continuously. The neighborhood is determined by means of an area Voronoi diagram [START_REF] Hoang | Extraction of Nom text regions from stele images using area Voronoi diagram[END_REF]. Inter-distance. The inter-distance d(gi, gj) between two text components gi, gj in one text string defined as:

d(gi, gj) = min p∈g i ,q∈g j d(p, q) (13)
should have restriction depending on their height h(gi), h(gj) as d(gi, gj) < T d max{h(gi), h(gj)}. The value of T d is determined by experience and is equal to 1.2.

Orientation. Text components belonging to one text string need to have similar orientation. As there is no universal method for the determination of the orientation of connected components, we resort to both the definition of minimumarea enclosing rectangle (MAER) [START_REF] Freeman | Determining the minimum-area encasing rectangle for an arbitrary closed curve[END_REF], and R-signature [START_REF] Tabbone | A new shape descriptor defined on the Radon transform[END_REF]. MAER (green rectangles in Fig. 2(a)) can be used to determine the orientation of most characters, however, it fails with some characters like 'A', 'r', 'J', etc.

For characters having a dominant stroke like 'r', 'J', 'l', their orientation are determined as the angle correspond-ing the maximum of their R-signature. Let [oi1, oi2, oi3] be the three orientations of a components gi determined by the three methods above. The difference in orientation between two components gi, gj is defined as:

Oij = min 1≤m,n≤3 |oim -ojn|. (14)
Thus two neighboring text components gi and gj need to satisfy Oij ≤ To to be considered as belonging to one text string. The value of To is determined by experience and is equal to 0.15 (radian).

Overlapping. Two neighboring text components gi, gj of a text string need to overlap to a certain degree along their common orientation, which is the orientation of the bisector tij of the angle formed by the two lines parallel to the orientations of gi, gj (see Fig. 3). Let [ai, bi], [aj, bj] be the orthogonal projections of gi, gj onto tij respectively, the degree of overlapping of two text components gi, gj is calculated as: Lij = max{min(bi -aj, bj -ai), 0} min(bi -ai, bj -aj) . The numerator of Eq. ( 15) is interpreted as the length of the overlapping segment. Thus two neighboring text components gi and gj need to satisfy Lij ≥ T l to be considered as belonging to one text string. The value of T l is determined by experience and is equal to 0.75.

EXPERIMENTAL RESULTS

To demonstrate the efficiency of the proposed method, experiments have been carried out on the same dataset used by Tombre et al. [START_REF] Tombre | Text/graphics separation revisited[END_REF] containing five graphical document images of different types as shown in the first column of Fig. 4. The second column of Fig. 4 provides the corresponding grayscale images containing text components obtained by using the MCA algorithm. It is clearly shown that the MCA algorithm using undecimated wavelet and curvelet transforms as the two overcomplete dictionaries cannot totally separate text and graphics components, some parts of graphics which have local morphological characteristics like those of text still remain in text images. The third column of Fig. 4 gives the binarized images of those in the second column after removing small components (composed of less than 50 pixels). The obtained results in the third column of Fig. 4 demonstrate that text/graphics separation using the MCA algorithm overcomes the touching problem between text and graphics and is invariant to different font styles, sizes, and orientations.

A quantitative evaluation of the method is also given in Table 1. The measure used for evaluation is the recall rate of text components. The column Nb. ch. indicates the number of characters existing in the input images. Results of the previous benchmark [START_REF] Tombre | Text/graphics separation revisited[END_REF] are given in the column The technique to group text components in straight fonts into text strings has also been evaluated on the three input images, one of which is from the dataset used by Tombre et al. [START_REF] Tombre | Text/graphics separation revisited[END_REF], showed in the first row of Fig. 5. The grouped text strings are given in the three corresponding images in the second row. Most of the text strings containing different characters and numbers of different orientations have been successfully grouped using heuristic rules proposed in Section 5. The only exception is the string PTT(0.60) in Image 6. The reasons for this are the connection between '6' and '0' and the embedment of ')' in a line.

It should be noted that in Fig. 5(d) the enclosing rectangles of text strings are not drawn on Fig. 1(e), but on Fig. 1(d).

The purpose of doing this is to retrieve all the small text components like '•', ':' that have been removed previously lying inside these enclosing rectangles. This guarantees a successful extraction of all text components.

CONCLUSION

A novel text extraction method from graphical document images is presented in this paper using a sparse representation framework. Two discriminative dictionaries based on undecimated wavelet transform and curvelet transform are used to represent text and graphics components. Morphological Component Analysis is employed for the promotion of sparse representation of text and graphics components in these two dictionaries. The proposed method has high recall rate of text components, overcomes the problem of text/graphics touching, and outperforms the previous benchmark. Moreover, a new technique to group text components in straight fonts into text strings has proved to be efficient.

Figure 1 :

 1 Figure 1: Processing steps to extract text strings from an image

Fig. 1 (Figure 2 :

 12 Figure 2: Determination of orientation

Fig. 1 (

 1 f) shows the area Voronoi diagram of the binary image in Fig. 1(d). Each connected component is represented by one Voronoi region containing points that are closer to that connected component than to any other. Two text components are said to be neighbors if their representing Voronoi regions are adjacent.

Fig. 2 (

 2 b) shows the R-signature of character 'r' in Fig.2(a). The enclosing rectangles having orientations determined through the maxima of R-signatures are in blue in Fig.2(a). Symmetric characters like 'A', 'x', 'V' also have symmetric R-signatures. Their orientation are determined as the angle that cuts their R-signature into two vectors of the same length having highest correlation. Fig.2(c) shows the Rsignature of character 'A' in Fig.2(a). The enclosing rectangles having orientations determined through correlation are in red in Fig.2(a).

Figure 3 :

 3 Figure 3: Determination of overlapping

Table 1 :

 1 Tombre et al. and the results of the proposed method are in the column Our method. A sharp increase in the recall rate has been achieved by using the MCA algorithm. Performance evaluation

	Image Nb. ch. Tombre et al. Our method
	1	53	49 (92.4%)	53 (100%)
	2	78	59 (75.6%)	62 (79.5%)
	3	78	68 (87.2%)	75 (96.2%)
	4	106	92 (86.8%)	104 (98.1%)
	5	21	1 (4.8%)	21 (100%)