Charles-Alban Deledalle

Nicolas Papadakis

Joseph Salmon
email: joseph.salmon@telecom-paristech.fr

Characterizing the maximum parameter of the total-variation denoising through the pseudo-inverse of the divergence

Samuel Vaiter

IMB, CNRS Université de Bourgogne, Dijon, France Email: samuel.vaiter@u-bourgogne.fr

Abstract-We focus on the maximum regularization parameter for anisotropic total-variation denoising. It corresponds to the minimum value of the regularization parameter above which the solution remains constant. While this value is well know for the Lasso, such a critical value has not been investigated in details for the total-variation. Though, it is of importance when tuning the regularization parameter as it allows fixing an upper-bound on the grid for which the optimal parameter is sought. We establish a closed form expression for the one-dimensional case, as well as an upper-bound for the two-dimensional case, that appears reasonably tight in practice. This problem is directly linked to the computation of the pseudo-inverse of the divergence, which can be quickly obtained by performing convolutions in the Fourier domain.

I. INTRODUCTION

We consider the reconstruction of a d-dimensional signal (in this study d = 1 or 2) from its noisy observation y = x + w ∈ R n with w ∈ R n . Anisotropic TV regularization writes, for λ > 0, as [START_REF] Rudin | Nonlinear total variation based noise removal algorithms[END_REF] x ⋆ = argmin

x∈R n 1 2 ||y -x|| 2 2 + λ||∇x||1 (1)
with ∇x ∈ R dn being the concatenation of the d components of the discrete periodical gradient vector field of x, and ||∇x||1 = i |(∇x)i| being a sparsity promoting term. The operator ∇ acts as a convolution which writes in the one dimensional case (d = 1)

∇ = F + diag(K→)F and div = F + diag(K←)F (2)
where div = -∇ ⊤ (where ⊤ denotes the adjoint), F : R n → C n is the Fourier transform,

F + = Re[F -1
] is its pseudo-inverse and K→ ∈ C n and K← ∈ C n are the Fourier transforms of the kernel functions performing forward and backward finite differences respectively. Similarly, we define in the two dimensional case (d = 2)

∇ = F + 0 0 F + diag(K ↓ ) diag(K→) F (3)
and

div = F + diag(K ↑ ) diag(K←) F 0 0 F (4)
where

K→ ∈ C n and K← ∈ C n (resp. K ↓ ∈ C n and K ↑ ∈ C n )
perform forward and backward finite difference in the horizontal (resp. vertical) direction.

II. GENERAL CASE

For the general case, the following proposition provides an expression of the maximum regularization parameter λmax as the solution of a convex but non-trivial optimization problem (direct consequence of the Karush-Khun-Tucker condition).

Proposition 1. Define for y ∈ R n , λmax = min ζ∈Ker[div] div + y + ζ ∞ (5)
where div + is the Moore-Penrose pseudo-inverse of div and Ker[div] its null space. Then, x ⋆ = 1 n 1n1 ⊤ n y if and only if λ λmax.

III. ONE DIMENSIONAL CASE

In the 1d case, Ker[div] = Span(1n) and thus the optimization problem can be solved by computing div + in the Fourier domain, in O(n log n) operations, as shown in the next corollary.

Corollary 1. For d = 1, λmax = 1 2 [max(div + y) -min(div + y)], where div + = F + diag(K + ↑ )F (6)
and

(K + ↑ )i = (K ↑ ) * i |(K ↑ ) i | 2 if |(K ↑ )i| 2 > 0 0
otherwise , and * denotes the complex conjugate.

Note that the condition |(K ↑ )i| 2 > 0 is satisfied everywhere except for the zero frequency. In the non-periodical case, div is the incidence matrix of a tree whose pseudo-inverse can be obtained following [START_REF] Bapat | Moore-penrose inverse of the incidence matrix of a tree[END_REF].

IV. TWO DIMENSIONAL CASE

In the 2d case, Ker[div] is the orthogonal of the vector space of signals satisfying Kirchhoff's voltage law on all cycles of the periodical grid. Its dimension is n+1. It follows that the optimization problem becomes much harder. Since our motivation is only to provide an approximation of λmax, we propose to compute an upperbound in O(n log n) operations thanks to the following corollary.

Corollary 2. For d = 2, λmax 1 2 [max(div + y)-min(div + y)] λ bnd , where div + = F + 0 0 F + diag( K+ ↑ ) diag( K+ ← )
F, and (7)

( K+ ↑ )i = (K ↑ ) * i |(K ↑ ) i | 2 +|(K←) i | 2 if |(K ↑ )i| 2 + |(K←)i| 2 > 0 0 otherwise , ( K+ ← )i = (K←) * i |(K ↑ ) i | 2 +|(K←) i | 2 if |(K ↑ )i| 2 + |(K←)i| 2 > 0 0 otherwise .
Note that the condition |(K ↑ )i| 2 + |(K←)i| 2 > 0 is again satisfied everywhere except for the zero frequency. Remark also that this result can be straightforwardly extended to the case where d > 2.

V. RESULTS AND DISCUSSION

Figure 1 and 2 provide illustrations of the computation of λmax and λ bnd on a 1d signal and a 2d image respectively. The convolution kernel is a simple triangle wave in the 1d case but is more complex in the 2d case. The operator div div + is in fact the projector onto the space of zero-mean signals, i.e., Im[div]. Figure 3 illustrates the evolution of x ⋆ with respect to λ (computed with the algorithm of [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF]). Our upper-bound λ bnd (computed in ∼5ms) appears to be reasonably tight (λmax computed in ∼25s with [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF] on Problem (5)).

Future work will concern the generalization of these results to other ℓ1 analysis regularization and to ill-posed inverse problems.

Fig. 1 .

 1 Fig. 1. (a) A 1d signal y. (b) The convolution kernel F + K + ↑ that realizes the pseudo inversion of the divergence. (c) The signal div + y on which we can read the value of λmax. (d) The signal div div + y showing that one can reconstruct y from div + y up to its mean component.

Fig. 3 .

 3 Fig. 3. (a) Evolution of ||∇x ⋆ ||∞ as a function of λ. (b), (c), (d) Results x ⋆ of the periodical anisotropic total-variation for three different values of λ.


Gaelle Largeteau-Skapin

Rita Zrour

Eric Andres

O(n 3 log n) time complexity for the Optimal Consensus Set computation for 4-connected Digital circles

Keywords: Shape fitting, consensus set, inliers, outliers, digital circle, 4-connected digital circle, 0-Flake digital circle

This paper presents a method for fitting 4-connected digital circles to a given set of points in 2D images in the presence of noise by maximizing the number of inliers, namely the optimal consensus set, while fixing the thickness. Our approach has a O(n 3 log n) time complexity and O(n) space complexity, n being the number of points, which is lower than previous known methods while still guaranteeing optimal solution(s).

Introduction

In the present paper, we are considering the fitting problem of a set of points in a noisy 2D image by a 4-connected digital circle. Such a 4-connected digital circle (see Fig. 1(c)) can be obtained by a morphological based digitization scheme. The 0-Flake in Fig. 1(a) is the structuring element. Such circles can be characterized analytically [START_REF] Fiorio | Arithmetic Discrete Hyperspheres and Separatingness[END_REF][START_REF] Toutant | Digital Circles, Spheres and Hyperspheres: From Morphological Models to Analytical Characterizations and Topological Properties[END_REF]. The 0-Flake digital circle is defined as all the digital points (see Fig. 1(c)) inside a sort of Annuli (see Fig. 1(b)), called 0-Flake Annuli, composed of four circles (see Fig. 1(a)). These circles are called boundary circles. It is important to note that the thickness of the digital 0-Flake circles is fixed. Most annuli fitting methods consider only classical annuli defined by two concentric circles and try to find annuli with minimal or maximal thicknesses given some other parameters. This is not adequate for digital circle fitting.

The set of points (inliers) which fits a model is called a consensus set. The idea of using such consensus sets was proposed for the RANdom Sample Consensus (RANSAC) method [START_REF] Fischler | Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography[END_REF], which is widely used in the field of computer vision. However RANSAC is inherently probabilistic in its approach and does not guarantee optimality. This paper aims at proposing a new lower time complexity for the computation of the optimal consensus set. This means that our goal is to maximize the number of inliers. In our case, an inlier is simply defined as a point inside the 0-Flake annulus. Non Probablistic methods that detect annuli have been proposed (for example [START_REF] Diaz-Banez | The largest empty annulus problem[END_REF]). Most of these algorithms minimize or maximize the thickness of the annuli [START_REF] Rivlin | Approximation by circles[END_REF] which is not adequate when considering digital circles where the thickness is fixed. Only few algorithms deal with outliers [START_REF] Dunagan | Optimal outlier removal in high-dimensional spaces[END_REF][START_REF] Har-Peled | Shape Fitting with Outliers[END_REF][START_REF] Matousek | On enclosing k points by a circle[END_REF] but the number of outliers is usually predefined [START_REF] Har-Peled | Shape Fitting with Outliers[END_REF][START_REF] Matousek | On enclosing k points by a circle[END_REF] and the problem consists again in minimizing the thickness. The method proposed by O'Rourke et al. [START_REF] O'rourke | Computing circular separability[END_REF][START_REF] Roussillon | On three constrained versions of the digital circular arc recognition problem[END_REF] that transforms a circle separation problem into a plane separability problem, is also not well suited because the fixed thickness of the digital circles translates into non fixed vertical thicknesses for the planes. In this case, the problem is complicated (See [START_REF] Phan | Efficient robust digital annulus Fitting with bounded error[END_REF] for some solutions on how to handle this difficulty).

So our problem is finding the optimal consensus set (maximal number of inliers) of digital points inside a 0-Flake annulus which has a fixed thickness where the center and the radius are unknowns. In [START_REF] Zrour | Optimal consensus set for annulus fitting[END_REF] and [START_REF] Andres | Optimal Consensus Set and Preimage of 4-connected circles in a noisy environment[END_REF], brute force algorithms were proposed to compute the optimal consensus set respectively for Andres digital circle (defined as digital points inside a classical annulus of fixed thickness) and 0-Flake digital circles. It was shown that if an optimal solution exists then there exists a finite number of equivalent optimal solutions (with the same set of inliers) with three points on the boundary (internal and/or external) of the annulus. Testing all the configurations of three points and counting the inliers leads therefore to all the possible optimal solution sets with a time complexity of O(n 4 ) where n is the number of points.

A new method is proposed in this paper for fitting 0-Flake digital circles. This method requires just two points to be located on the boundary circles. This method is inspired by the dual space proposed by [START_REF] Diaz-Banez | The largest empty annulus problem[END_REF]: the centers of all the circles with two specific points on the boundary correspond to a straight line. A dual space where the x axis represents the center locations and the y axis represents the distance to this center allows to find the largest empty annulus using an interval sorting.

We adapt this idea to our problem but there are several major differences: in our case, the thickness is fixed and we look for a maximal number of inliers. Moreover, since we deal with Flake annuli, there are more than only one straight line for the center locations (see section 2.2). The idea is the following: given a set S and given two specific points on the boundary of a Flake annuli, we consider the center locations straight lines as parametric axis. We then determine when a point enters and leaves the flake annuli while the center moves along the axis. This allows us to compute the intervals where the number of inliers is maximized (Section 3). By considering all the combinations of two points, we are able to compute the exhaustive set of all optimal consensus sets in O(n 3 log n).

The paper is organized as follows: in Section 2 we expose some properties and characterizations of the 0-Flake digital circles and its analytical annulus definition. Section 3 provides the general idea and the detailed algorithm for finding the optimal consensus sets. Section 4 presents some results. Finally Section 5 proposes a conclusion and some perspectives.

2 The 0-Flake annulus : definitions and properties

In [START_REF] Zrour | Optimal consensus set for annulus fitting[END_REF] and [START_REF] Andres | Optimal Consensus Set and Preimage of 4-connected circles in a noisy environment[END_REF], we proposed a brute force algorithm with O(n 4 ) time complexity for fitting Andres circle and 0-Flake circle of fixed thickness, with n the number of points to fit. We have shown that if an optimal solution (set of inliers) exists then there exists an equivalent optimal solution (with the same set of inliers) with three points on the boundary (internal and/or external). In this section we are considering the problem of characterizing the 0-Flake annulus that are equivalent (same inliers, same thickness) to some optimal solution with only two points on the boundary circles of the Flake annuli. Let us first introduce some basic notations as well as the analytical definition of the 0-Flake digital circles. In a second part of this section, we will look at the annulus characterization for 0-Flake circles with thickness 1.

Notations and basic definitions

In this section, we present 0-Flake digital circles with the associated notations and definitions. See [START_REF] Andres | A: The Discrete analytical hyperspheres[END_REF][START_REF] Fiorio | Arithmetic Discrete Hyperspheres and Separatingness[END_REF][START_REF] Andres | Analytical Description of Digital Circles[END_REF][START_REF] Toutant | Digital Circles, Spheres and Hyperspheres: From Morphological Models to Analytical Characterizations and Topological Properties[END_REF] for more details on the digitization models and properties of the different types of digital circles. The digitization scheme we are considering is an Adjacency Flake Digitization [START_REF] Fiorio | Arithmetic Discrete Hyperspheres and Separatingness[END_REF][START_REF] Andres | Analytical Description of Digital Circles[END_REF][START_REF] Toutant | Digital Circles, Spheres and Hyperspheres: From Morphological Models to Analytical Characterizations and Topological Properties[END_REF]. It is based on a morphological digitization scheme with a structuring element called an Adjacency Flake. In this paper we are limiting our self to 0-adjacency Flake (or simply 0-Flake) circles for the sake of simplicity. The 2D 0-Flake corresponds to the diagonals of a unit cube. The figure 1.a shows the 0-Flake and a corresponding Flake annulus.This corresponds to 4-connected digital circles when the size of the Flake and thus the thickness of the Flake annulus is equal to one. However, the proposed fitting method works as well for 2D 1-adjacency Flake circles (8connected circles) and for other thicknesses [START_REF] Andres | Analytical Description of Digital Circles[END_REF][START_REF] Toutant | Digital Circles, Spheres and Hyperspheres: From Morphological Models to Analytical Characterizations and Topological Properties[END_REF]. The 0-Flake digitization D F0 of the Euclidean circle C(C, R) of center C and radius R is defined as follows:

D F0 (C(C, R)) = (X ⊗ C(C, R)) Z 2
Where X is the 0-Flake corresponding to the diagonals of a unit square. Proof that such a digital circle is 4-connected can be found in [START_REF] Fiorio | Arithmetic Discrete Hyperspheres and Separatingness[END_REF][START_REF] Toutant | Digital Circles, Spheres and Hyperspheres: From Morphological Models to Analytical Characterizations and Topological Properties[END_REF].

The 0-Flake annulus A F0 of the Euclidean circle C(C, R) of center C and radius R is analytically defined as follows [START_REF] Toutant | Digital Circles, Spheres and Hyperspheres: From Morphological Models to Analytical Characterizations and Topological Properties[END_REF]:

A F0 (C(C, R)) = (X ⊗ C(C, R)) = x ∈ R 2 : -|x -C x | -|y -C y | -1 2 ≤ (x -C x ) 2 + (y -C y ) 2 -R 2 ≤ |x -C x | + |y -C y | + 1 2
The smallest possible 0-Flake circle is of radius √ 2/2. With a Flake structuring element, the analytical characterization of circles of smaller radii are not correct. This is one of the limitations of the Flake model. It is however not a big constraint as it corresponds to a circle that spans only a couple of pixels [START_REF] Toutant | Digital Circles, Spheres and Hyperspheres: From Morphological Models to Analytical Characterizations and Topological Properties[END_REF].

We call boundary circles the 4 circles that form the boundary of the 0-Flake annulus, i.e. the circles centered on (C x ± 1 2 , C y ± 1 2 ). On figure 1.a, we can see the four boundary circles C 00 , C 01 , C 10 and C 11 :

Definition 1. Let C ij be a boundary circle of the 0-Flake circle C(C x , C y ) of radius R. C ij is defined as the circle of center (C x , C y ) + (1/2, 1/2) -(i, j) and radius R.
The actual boundaries of the 0-Flake annulus are only parts of those boundary circles (see fig. 1). We call internal (resp. external) boundary of the 0-Flake annulus, the parts of the boundary circles that are closest (resp. farthest) to the center of the 0-Flake annulus. We define the 0-Flake digital circle as the set of digital points in the 0-Flake annulus. Definition 2. Let us consider a set of points S. Two Flake annuli are said to be equivalent with regard to S if the points of S belong to both annuli.

0-Flake annulus characterization

In [START_REF] Andres | Optimal Consensus Set and Preimage of 4-connected circles in a noisy environment[END_REF], it has been proven that given a 0-Flake annulus covering a set of points there exists an equivalent 0-Flake annulus (same inliers, same thickness) which has at least three points of the set on its boundary circles, not necessarily on the actual internal or external boundary of the annulus. For the fitting method we are going to present here, we need to show that if a Flake annulus covers a set of points then there exists an equivalent Flake annulus with two points on the boundary circles. Again, we do not require the points to be on the actual internal or external boundary as simply being on the boundary circles is sufficient to provide a straight line of possible center locations. The proof in [START_REF] Andres | Optimal Consensus Set and Preimage of 4-connected circles in a noisy environment[END_REF] is obviously sufficient for our purpose. Now we have two points of the set on the boundary circles, we are going to check all the possible 0-Flake annuli that have those two points on their boundary circles. The following proposition provides the characterization of the center locations for those annuli.

Proposition 1. Let us suppose that we have a set of points S and two points p and q ∈ S.

-The centers of all the Flake annuli having p and q on their boundary circles belong to a maximum of 16 straight lines. We call these straight lines, center axes. -The set of all the centers of the annuli covering the consensus set S with p and q on the boundary circles is a set of straight line segments, half lines or straight lines belonging to the center axes.

Proof. Let us suppose that we have a consensus set S in a 0-Flake annulus F of center C (C(C x , C y ), R, ) with two points p and q of S on its boundary circles. First, let us note that if we consider Flake annuli with two points p and q on some of its boundary circles, we have several possibilities since p and q may belong to the boundary circles C 00 , C 01 , C 10 or C 11 . There are 16 possible different configurations.

-If p and q belong to the same boundary circle

C ij of center (C ijx , C ijy ) = (C x , C y ) + (i, j) -(1/2, 1/2
) then the center of C ij has to belong to the perpendicular bisector of p and q. Therefore the 0-Flake annulus F centers belong to its parallel passing through the points (C ijx , C ijy ) + (1/2, 1/2) -(i, j). -If p belongs to the boundary circle C ij and q to the boundary circle C kl then obviously the point q = q + (i -k, j -l) belongs to C ij and the previous reasoning works with p and q at the condition that p is different from q . In this case there is no center axis but all the points in space can be centers. We can actually discard such configurations because in such a case it is easy to see that there exist an equivalent configuration with two points of S on the boundary circles that do not have this problem. One has simply to discard one of the two points, for instance by keeping p, and use the principle of [START_REF] Andres | Optimal Consensus Set and Preimage of 4-connected circles in a noisy environment[END_REF] to find another point on a boundary circle. Since only four points around p may cause such a problem, we have either other points or a set of four neighboring points that can easily be dealt with otherwise. The corresponding optimal solutions will therefore be treated by some other configurations of points.

This proves that there is a maximum of 16 center axes. The actual center axis equation for p ∈ C ij and q ∈ C kl is given by:

2(p x -q x + i -k)C x + 2(p y -q y + j -l)C y + (p x -1/2 + i) 2 +(p y -1/2 + j) 2 -(q x -1/2 + k) 2 -(q y -1/2 + l) 2 = 0
Let us now consider a point t of S and a center axis defined by p and q belonging to C ij and C kl respectively, with i, j, k, l ∈ {0, 1}. The point t is an inlier if it is inside of at least one of the four boundary circles and not inside all four boundary circles (see Figure 1.a). Let us determine when, with the center of the flake annulus moving along the center axis, t enters or leaves a boundary circle C mn and thus when it may be inside 0,1,2,3 or 4 boundary circles. Different cases have to be examined:

-Let us suppose that t -(m, n) = p -(i, j) and t -(m, n) = q -(k, l).
Let us consider the following three points p, q = q + (i -k, j -l) and t = t + (i -m, j -n). There is of course only one circumcenter c for p, q and t . There is therefore a unique center point c = c + (1/2, 1/2) -(i, j) on the center axis such that p ∈ C ij , q ∈ C kl and t ∈ Cmn. On one side of c on the center axis, t will be inside the boundary circle C mn while for all the centers on the other side of c on the center axis, t will be outside the boundary circle C mn .

-If t -(m, n) = p -(i, j) or t -(m, n) = q -(k, l) then t belongs to C mn for
all the Flake annuli with center on the center axis. Now, for each center axis defined by p and q, with some parametrization of the center axis, for each point t we have four intervals of type ]-∞, x], [x, +∞[ or ]-∞, +∞[. The intersection of four such intervals is a straight line segment on the center axis, an half-line on the center axis, the complete center axis or is empty. By considering all the center axes we obtain the result of the proposition.

Fitting Algorithm

Using the above proposed flake annuli characterization, our fitting problem can be described as follows: given a finite set S = (P x , P y ) ∈ Z 2 of n points such that n ≥ 2, and given a fixed thickness 1 we would like to find a 0-Flake annulus such that it contains the maximum number of points of S. Points belonging to the annulus are called inliers; otherwise they are called outliers.

The idea behind our fitting method is inspired by [START_REF] Diaz-Banez | The largest empty annulus problem[END_REF] where the authors try to maximize the width of an empty annulus. In [START_REF] Diaz-Banez | The largest empty annulus problem[END_REF], given two points p and q, they define a dual space where the perpendicular bisector of the two points becomes the abscissa axis. These are all the centers of the circles that have p and q on its boundary. For any point t, the ordinate value is given by its distance to a point of the bisector and thus to the center of a circle that has p and q on its boundary. It allows them to determine when a point t enters a circle centered on the bisector. By sorting these entry points relatively to the abscissa axis, they determine the biggest empty annulus. Since they look for the biggest empty annulus, they do not represent an annulus in their parameter space but only circles. It is the biggest empty interval projected on the abscissa axis that will define the looked for annulus.

Our purpose is quite different but their idea of taking the axes where the possible centers of the annuli are located can be adapted in the following way. One of the main difference with our problem is that we deal with Flake annuli and therefore we have four boundary circles that are not concentric: for two given points p and q, the 0-Flake annuli centers may follow 16 different straight lines, called center axis. Each of these center axis will be considered separately. We do not consider an actual dual space. There is no ordinate axis since the distance from p and q to the center axes and thus to the center of the Flake annuli are not equal. We simply consider a parametrization of each center axis and determine the parameter λ t ij for which a given point t enters the boundary circle C ij of a flake annulus centered on the considered center axis. This corresponds to a set of a maximum 4 parameter values that are sorted. We complete this list by adding -∞ and +∞. Each parameter interval (between two consecutive values of the list) is tested to check if the point t is inside or outside the corresponding 0-Flake annulus. One needs only to test the midpoint of each interval and in the case of semi open intervals such as ]-∞, λ] (respectively [λ, +∞[), we test a value that is significantly smaller (respectively bigger) than λ in order to avoid numerical problems. This leads to a set of one or two intervals where t is inside a 0-Flake. In order to avoid interval sorting (which might have a O(n 2 ) worst case complexity), these intervals are then simply coded as a general parameter list as follows: let us suppose that the point t belongs to a 0-Flake annulus for the interval [a, b], then we add the elements (a, +1) and (b, -1) to a general parameter list. This codes for the fact that at parameter value a the number of inliers is increased by 1 and at parameter value b it is decreased by 1. This is repeated for each point t (different from p and q) of the set S. The general parameter list is then sorted by parameter value and, starting at parameter value -∞, the number of inliers are counted by summing up the +1 and -1. This results in a list of intervals for which a maximum of inliers is obtained. These intervals and their corresponding generator values p, q, i, j, k and l are added to the already existing maximal inlier interval list. If the maximum of inliers increases, then the former maximal inlier interval list is wiped and replaced by a new one.

A pair of points defines a maximum of 16 center axes. For each other point, we determine the parameter values on each center axis for which it is inside a flake annulus. There is a maximum of 4 such parameter values per point. All these are sorted for each center axis with a time complexity of therefore n log n. scanning each list to determine the interval where we have a maximum consensus set is linear in the number of parameter values and thus in n. Since this is repeated for every couple of points in the set, the final complexity is O(n 3 log n).

Example: Here is an example of values obtained while fitting the points (0, 0), [START_REF] Fiorio | Arithmetic Discrete Hyperspheres and Separatingness[END_REF][START_REF] Andres | Analytical Description of Digital Circles[END_REF] and [START_REF] Andres | Optimal Consensus Set and Preimage of 4-connected circles in a noisy environment[END_REF][START_REF] Zrour | Optimal consensus set for annulus fitting[END_REF]. At some point we have a (already sorted) set of parameter values -23.4953, -4.0588, -3.08697, 8.57493 for a center axis corresponding to (0, 0) and [START_REF] Fiorio | Arithmetic Discrete Hyperspheres and Separatingness[END_REF][START_REF] Andres | Analytical Description of Digital Circles[END_REF]. The corresponding general parameter list looks like ((-∞, 1), (-3.08697, -1), (8.57493, 1), (+∞, -1)). This means that the point t (in this case (2, 1)) belongs to a 0-Flake annulus for the parameter intervals ]-∞, -3.08697] and [8.57493, +∞[. The parameter values -23.4953 and -4.0588 disappear as they correspond to t leaving or entering a boundary circle inside the annulus. Note that (+∞, -1) is not really needed for the inlier computation but it is useful for expressing the intervals.

Fig. 2 gives an example of a 0-Flake annulus with p ∈ C 11 and q ∈ C 00 . Doing this for all the couple of points among the set of points to fit yields the optimal 0-Flake annulus in terms of number of inliers.

Experiments

We used Mathematica for implementing our method. We applied our method for 2D noisy 0-Flake annuli as shown in fig. 4(a). A bounding region (center,radius) of all the possible solutions corresponding to optimal consensus sets for this image are shown in fig. 4(b).

The figure 5 presents a 0-Flake circular arc of 100 points and some degraded versions of it: In each image, we keep 100 points but for the different degraded versions of x% noise, we kept 100 -x random points of the original arc and shows one solution for each case, the optimal number of inliers found and the number of distinct limit solutions (corresponding to an center interval end point).

Conclusion and Perspectives

In this paper we have presented a new method for fitting 0-Flake digital circles to a set of points while fixing the thickness. Various papers have been written on fitting circles or annuli but usually they have not dealt with fixed thicknesses which is a fundamental property of digital circles. Our approach guarantees optimal results from the point of view of maximal consensus sets: we are guaranteed to fit a digital circle with the least amount of outliers. In terms of computation time, this approach has a lower time complexity than the one presented in [START_REF] Andres | Optimal Consensus Set and Preimage of 4-connected circles in a noisy environment[END_REF]. The method is general enough that is can be extended to 1-Flake circles, Andres circles and probably most other types of digital circles [START_REF] Andres | Analytical Description of Digital Circles[END_REF][START_REF] Toutant | Digital Circles, Spheres and Hyperspheres: From Morphological Models to Analytical Characterizations and Topological Properties[END_REF] with thicknesses not limited to 1. This work opens many interesting perspectives for the future. One obvious question that remains open is the question of the optimal time complexity we can expect for such a problem. We have reasons to believe that we can not beat a O(n 3 ) time complexity simply because this is the optimal time complexity for a similar problem of 3D plane fitting [START_REF] Aiger | Efficient Robust Digital Hyperplane Fitting with Bounded Error[END_REF]. Now, the reason why we suspect that the optimal time complexity might be the same is simply because of some arguments coming from conformal space representations. This needs however to be proved and an according method would need to be found. One of the interesting aspects that has not been yet fully explored is that computing optimal consensus sets or near optimal consensus sets allows us to classify points and introduce notions of strong or weak inliers . We can for instance, differentiate Fig. 3. A representation of the number of times a point belongs to the optimal consensus sets found for, on the left side an example with 85% noise and on the right side an example with 90% noise.

inliers that belong to many optimal or near optimal consensus sets from points that only belong to some of those solutions (See Figure 6. for an example). The method we proposed seems to extends pretty well to higher dimension but we need a formal proof of the Flake annulus characterization in higher dimensions. A last perspective is of course fitting of other types of digital curves such as digital conics for instance.

Fig. 1 .

 1 Fig. 1. (a) 0-Flake circle and Boundary circles, (b) 0-Flake annulus and (c) corresponding 4-connected digital circle.

Algorithm 1 : 2 initialize 4 foreach p ∈ S do 5 foreach q ∈ S do 6 foreach 10 foreach

 1245610 0-Flake annulus fitting input : A set S of n grid points output: A list V of centers and radius values for the best fitted 0-Flake annuli 1 begin M ax = 0; 3 initialize the list V to the empty list; of the 16 different configurations of p and q do 7 compute the straight line ∆pq where the center are located; 8 initialize the list of parameters L λ ; foreach t ∈ S do 9 initialize the valide interval to []; For each one of the four boundary circle : do 11 compute the parameter λ for which the point t is ON the boundary circles; 12 test a value in the interval ]∞, λ] to know if the point is inside the boundary circle for this interval; 13 keep the valid interval It where t is inlier with the following rule: when t belongs to the zero or four circles it is an outlier; 14 foreach sub-interval [min, max] in It do 15 Add the couples (min, 1) and (max, -1) to the parameter list L λ ; 16 Sort the pair elements (λ k , f k ) of L λ with the values λ k as keys; 17 Initialize F = 0; 18 foreach couple (λ k , f k ) in L λ do 19 F = F + f k ; 20 if F > M ax and f k+1 = -1 then 21 Set M ax = F ; Erase V and set it to the interval [λ k , λ k+1 ] ; 22 if F = M ax and f k+1 = -1 then 23 Add the interval [λ k , λ k+1 ] to V 24 return V;

Fig. 2 .

 2 Fig.2. The 0-Flake annulus with p ∈ C11 and q ∈ C00 and an interval where the point t belongs to the Flake annulus.

Fig. 4 .

 4 Fig. 4. a) Fitting of 2D noisy 0-Flake circles. b) bounding region of all the optimal centers,

Acknowledgments. The work for this paper was partly financed by Egide, franco-Japanese PHC Sakura project n 27608XJ and by the Poitou Charentes region project n 11/RPC-R-051.