Jean Serge

Dimitri Ouattara
email: jean.ouattara@univ-poitiers.fr

Eric Andres
email: eric.andres@univ-poitiers.fr

Gaëlle Largeteau-Skapin
email: gaelle.largeteau-skapin@univ-poitiers.fr

Rita Zrour
email: rita.zrour@univ-poitiers.fr

Marie-Yves Tapsoba
email: theo_tapsoba@univ-ouaga.bf

Remainder Approach for the Computation of Digital Straight Line Subsegment Characteristics

Keywords: Remainder, Digital Straight Line Subsegment Recognition, Discrete geometry

.

Introduction

One of the simplest primitives in digital geometry, the Digital Straight Line (DSL) and the Digital Straight line Segment (DSS), have very interesting and rich structures that have been studied for a long time now [START_REF] Morse | Symbolic dynamics ii. sturmian trajectories[END_REF]. See [START_REF] Klette | Digital straightness -a review[END_REF] for a historical overview. There are immediate links to Sturmian and Christoffel words, the Stern-Brocot tree, the Farey fans, etc. [START_REF] Klette | Digital straightness -a review[END_REF]. The study are regained some interest when J-P. Reveillès, proposed, among previous authors [START_REF] Brons | Linguistic methods for the description of a straight line on a grid[END_REF][START_REF] Coven | Sequences with minimal block growth[END_REF], an analytical description of a DSL 0 ≤ axbyc < ω in [START_REF] Reveillès | Calcul en Nombres Entiers et Algorithmique[END_REF] (where (a, b, c) are called the characteristics or parameters of the DSL). The immediate possibilities of extensions to higher dimensions and to different scales sparked interest among arithmeticians [START_REF] Berthé | An arithmetic and combinatorial approach to three-dimensional discrete lines[END_REF] and researchers in image processing [START_REF] Said | Multiscale discrete geometry[END_REF][START_REF] Vacavant | A combined multi-scale/irregular algorithm for the vectorization of noisy digital contours[END_REF]. In this paper we are interested in a particular class of DSS recognition problems. The problem is related to multiscale geometry [START_REF] Said | Multiscale discrete geometry[END_REF][START_REF] Vacavant | A combined multi-scale/irregular algorithm for the vectorization of noisy digital contours[END_REF]. It is indeed important, when inspecting geometrical features at multiple scales, to be able to recompute the new, scaled, characteristics and that, as rapidly as possible. The intricate structure of DSLs is at the heart of many DSS recognition algorithms. While there are too many papers to cite them all, let us just recall some emblematic papers that did explore various approaches such as those based on convex hull computation [START_REF] Anderson | Representation of digital line segments and their preimages[END_REF][START_REF] Buzer | Digital line recognition, convex hull, thickness, a unified and logarithmic technique[END_REF], on arithmetic properties [START_REF] Kovalevsky | New definition and fast recognition of digital straight segments and arcs[END_REF] or on pre-images of a digital straight line segment [START_REF] Dorst | Discrete straight line segments: Parameters, primitives and properties[END_REF][START_REF] Sivignon | New results about digital intersections[END_REF]. In [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF], I. Debled-Rennesson proposed an algorithm that allows to compute the characteristics of a DSS in linear time complexity with a very simple straight forward algorithm that made the link between the characteristics of a DSS and leaning points which can be described arithmetically as points with limit remainder values or geometrically as pivot points. Let us consider a DSL with known characteristics (a, b, c) and two points A and B of the DSL. What are the characteristics of the DSS defined by those two points? We may consider a DSS as a segment of DSL at various scales and being able to characterize those DSSs allows multiscale shape analysis for example. The problem differs from the classical DSL recognition problem because we have a very important information we usually do not have: the whole set of points of the DSS belongs to a known DSL. This leads to algorithms in logarithmic time which is, of course, not possible if we do not know in advance which points belong to the DSS [START_REF] Lachaud | Two efficient algorithms for computing the characteristics of a subsegment of a digital straight line[END_REF][START_REF] Sivignon | Walking in the farey fan to compute the characteristics of a discrete straight line subsegment[END_REF]. In classical Euclidean geometry, the characteristics of a segment are the same as those of the straight line. This is not true in digital geometry. There can be an infinite number of different triplets of DSS characteristics for a same set of points (and no, using a simple Greatest Common Divisor is not enough). Although there is an infinite set of characteristics, there is a unique minimal characteristic triplet. For naive DSS (ω = b, 0 ≤ a ≤ b) it corresponds to the characteristics with the minimal b. This problem has been the focus of some attention lately in conjunction with new multiscale shape analysis methods [START_REF] Lachaud | Two efficient algorithms for computing the characteristics of a subsegment of a digital straight line[END_REF][START_REF] Said | Multiscale discrete geometry[END_REF], and various approaches have been tried: in [START_REF] De | Revisiting digital straight segment recognition[END_REF], De Vieilleville and Lachaud exhibited relations describing the possible changes in the characteristics of a DSS by examining its combinatoric description. They established new analytic relations and made explicit the relation with the Stern Brocot tree. In [START_REF] Lachaud | Two efficient algorithms for computing the characteristics of a subsegment of a digital straight line[END_REF] Said and Lachaud used these results and presented two algorithms. Those determine the minimal characteristics of a DSS by moving in a bottom-up and top-down way along the Stern-Brocot tree. They demonstrated that the worst-time complexity is proportional to the difference of depth, in the Stern-Brocot tree, of the slope of the input line and the slope of the output segment and is thus logarithmic in the coefficients of the input slope. Sivignon in [START_REF] Sivignon | Walking in the farey fan to compute the characteristics of a discrete straight line subsegment[END_REF] proposed a method that computes the characteristics of a DSS using a walk in the so called Farey Fans; this algorithm is logarithmic in terms of the length of the subsegment. The main problem with both these methods, aside from the fact that they are not trivial to program, is that they do not offer an obvious extension to higher dimensions.

In this paper we propose a new algorithm for the computation of the minimal characteristics of a DSS defined as a subsegment of a DSL with known characteristics. Our approach is entirely based on the remainders of the DSL points. For a DSL defined by 0 ≤ axbyc < b (with 0 ≤ a ≤ b), the remainder is simply the value R a,b,c (x) = axbyc = ax-c b where n m stands for n mod m (y is a function of x; there is one and only one DSL point per abscissa). We show that there is, under some conditions, an order relationship between the remainders of a point relatively to the DSL and to the DSS minimal characteristics. We show especially that the points with minimum and maximum DSL remainders are leaning points of the DSS. The third leaning point is obtained in a similar way on a sub-interval. The second important result of the paper is that the minimum and maximum of a remainder sequence can be computed in logarithmic time with a very simple algorithm that is akin to the Euclidean algorithm. Determining the three leaning points of a DSS that allow us to determine its characteristics is resumed by searching three times for a minima or maxima in remainder sequences. The resulting algorithm is very simple and efficient, being significantly faster as previous methods [START_REF] Lachaud | Two efficient algorithms for computing the characteristics of a subsegment of a digital straight line[END_REF][START_REF] Sivignon | Walking in the farey fan to compute the characteristics of a discrete straight line subsegment[END_REF]. An interesting aspect of this approach is that it offers a new way, with remainders, to explore higher dimensions. It is not however, as can be seen in the conclusion, straightforward.

This paper is organized as follows: Section 2, deals with remainders and the properties of minimal DSS. Section 3 is devoted to the computation of the minimum and maximum of a remainder sequence. Section 4 presents briefly the algorithm for DSS characterization and shows some results and some comparisons of our approach with previous ones. Finally section 5 proposes a conclusion and some perspectives.

Remainders of minimal DSS

In this section we present our notations, definitions and properties of Digital Straight Segments. We are especially going to explore the properties of the remainders of minimal DSS and relations to the remainders of corresponding DSL.

Notations, Definitions

A [START_REF] Lachaud | Two efficient algorithms for computing the characteristics of a subsegment of a digital straight line[END_REF]. The characteristics of a DSL are therefore not adapted for manipulating DSSs especially since there is no direct method to establish the equality between two DSSs with two different sets of characteristics without comparing the points on the interval. For this reason we use the notion of minimal characteristics: the minimal characteristics of a DSS are the characteristics of the corresponding DSL with a minimal b. It is easy to see that there exists only one DSL with minimal b [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF]. The DSL with minimal characteristics is called the minimal DSL for the DSS. By extension, we refer simply to a DSS defined by minimal characteristics as a minimal DSS. The notions of leaning lines, leaning points and weakly exterior points are extended to minimal DSS. Two DSSs are said to be equivalent if they share the same minimal characteristics DSL even if the endpoints are different. A DSS is minimal if and only if the DSS contains at least three leaning points [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF][START_REF] De | Revisiting digital straight segment recognition[END_REF] of the minimal DSL. This means that two minimal DSSs with different endpoints will be equivalent if they contain a common set of three leaning points or if they contain each a set of three leaning points from the same DSL. The upper and lower leaning points alternate in a DSL: between two consecutive upper (respectively lower) leaning points we have one lower (respectively upper) leaning point. A span of a DSL or a DSS is a set of (connected) points that have the same ordinate.

We will use the notation a b for a mod b [START_REF] Reveillès | Calcul en Nombres Entiers et Algorithmique[END_REF]. The remainder R a,b,c (x) at abscissa

x is the value R a,b,c (x) = ax -by -c = ax-c b . The sequence of the remainders for a DSS S (D, u, v) of minimal characteristics (a, b, c) is noted R a,b,c (u, v).
Let us call DSS dilation or simply dilation the operation of adding a discrete point at the left or right of a DSS S of minimal characteristics (a, b, c): S (D, u, v)∪(v+1, y) or S (D, u, v)∪(u-1, y ′ ). From the line segment recognition algorithm of I. Debled-Renesson [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF], we have some immediate dilation properties: let us dilate the DSS by the right (respectively the left) then the resulting set is a DSS iff the remainder of the new point relatively to the minimal characteris-

tics of S verifies -1 ≤ R a,b,c (v + 1) ≤ b (respectively -1 ≤ R a,b,c (u -1) ≤ b). The new DSS is equivalent to S (the minimal characteristics are (a, b, c)) iff 0 ≤ R a,b,c (v + 1) ≤ b -1 (respectively 0 ≤ R a,b,c (u -1) ≤ b -1)
. This means that the dilated S is a DSS with new minimal characteristics iff the new point is weakly exterior. In this case the added point is a leaning point for the new minimal characteristics (upper leaning point if it was a weakly upper exterior point and lower leaning point if it was a weakly lower exterior point). Let us call DSS erosion or simply erosion the operation of removing an endpoint of a DSS S. Except, of course, if S is composed only of one point, the erosion of a DSS is always a DSS. The erosion of a DSS is not equivalent to S (the minimal characteristics are different) iff S contained only three leaning points and if the removed point was one of them [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF][START_REF] Roussillon | Algorithmes d'extraction de modeles géométriques discrets pour la représentation robuste des formes[END_REF]. Definition 1. Let us consider a DSS S = S (D, u, v). We say that S ′ is a right pivot dilation (or simply pivot dilation when there is no ambiguity) of S iff S ′ = S (D, u, v ′ ) is not equivalent to S but its erosion S (D, u, v ′ -1) is. We say that S ′′ is a right pivot erosion (or simply pivot erosion when there is no ambiguity) of S iff S ′′ = S (D, u, v ′′ ) is not equivalent to S but its dilation S (D, u, v ′′ + 1) is. An equivalent definition goes for left pivot dilation and left pivot erosion.

There are some immediate properties of pivot dilations and pivot erosions. Within a DSS associated to a minimal DSL, the right dilation of a right pivot erosion is equivalent to the right erosion of a right pivot dilation and vice-versa (same for the left). The pivot dilation of a DSS always contains exactly three leaning points (with regard to the minimal characteristics of the pivot dilated DSS).

On Figure 1, we can see a DSS S i and its right pivot dilation DSS S i+1 . The DSS S ′ i is the right pivot erosion of S i+1 . The DSSs S i and S ′ i are equivalent, so DSS S i+1 is also a right pivot dilation of S ′ i . Note that for the clarity of some figures, we will represent a DSS not by its set of points (x, y) but by a set of points (x, R a,b,c (x)). This way the lines axbyc are represented horizontally and it is easier to see how leaning points or weakly exterior points play a role in the evolution of minimal characteristics. In Figure 1, the blue disks correspond to interior points of the DSS and the blue circles to leaning points of the right pivot dilation DSS S i+1 . All the DSSs that have equivalent right pivot dilations are equivalent. All the DSS that have equivalent right pivot erosions are equivalent. Same goes for the left of course.

Slope of a DSS and its pivot dilation/erosion

The goal of the following subsections is to establish a link between the remainders of a DSL and its DSSs. This will allow us to determine the minimal characteristics of the DSSs. In what follows, we are going to consider mainly a right pivot dilation approach for the construction and definition of a sequence of DSSs. To establish the link between the characteristics of a DSL D and the minimal characteristics of a segment S (D, u, v), we will start with the DSS S (D, u, v) and repeatedly add points of D so as to establish a sequence of right pivot dilations until we obtain a segment S (D, u, v n ) where v n corresponds to the abscissa of the third leaning point of D at the right of P D (u) (as mentioned in the notations, P D (u) is the point of D of abscissa u). Then we know that the minimal characteristics of S (D, u, v n ) are those of D. We build the sequence v i of the abscissa for which the minimal characteristics change with the pivot dilations and the associated minimal characteristics of those successive DSSs.

u v i v ' i v i+1 S i S' i S i+1 D i D i+1
Our aim is to show that the variations of the remainders for the minimal DSSs are linked to the variations of the remainders of the minimal DSL D.

The following lemma shows a link between a minimal DSS and its pivot dilation/erosion:

S ′′ = S (D, u, v ′ + 1
) is equivalent to S as we already mentioned. We know that S ′′ has exactly three leaning points for the characteristics (a, b, c). Let us suppose that in S ′′ we have U 0 (x 0 , v ′ + 1a) and U 2 (x 0 + b, v ′ + 1) as two consecutive upper leaning points in S ′′ . The point U 2 is a weakly upper exterior point which means for

S ′ : α(x 0 + b) -β(v ′ + 1) -γ = -1.
We know also from [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF] that U 0 remains an upper leaning point for S ′ so αx 0β(v ′ + 1a)γ = 0 which leads to the result. The arguments with two lower leaning points, with a left pivot dilation or left or right pivot erosions are similar.

The result is quite obvious actually. Indeed if the vectors (a, b) and (α, β) were not unimodular then we would have additional discrete points on the interval [u ′ , v ′ ] which is contradictory to our construction.

Remainders and Leaning Points

The following proposition states that the remainders of a DSS and the remainders of its pivot dilation (respectively the remainders of its pivot erosion) are ordered in the same way as long as the points we are considering are close enough:

Proposition 1. Let us consider a DSL D and two DSSs S = S (D, u, w) of minimal characteristics (a, b, c) and S ′ = S (D, u, v) of minimal characteristics (α, β, γ) such that either S is a right pivot dilation of S ′ or S ′ is a right pivot erosion of S. Then: . We also have R α,β,γ (x) = αxβyγ. The same equalities stand for (x ′ , y ′ ). Note that, since both DSSs are segments of D, they have the same points (x, y) for x ∈ [u, v]. The ordinates are equal. We can therefore write:

∀x, x ′ ∈ [u, v], |x -x ′ | ≤ b : R a,b,c (x) < R a,b,c (x ′ ) ⇒ R α,β,γ (x) ≤ R α,β,γ (x ′ ) Let us note that while [u, v] ⊂ [u, w], it does not mean however that v - u ≤ b.
R α,β,γ (x) -R α,β,γ (x ′ ) = αx -βy -γ -(αx ′ -βy ′ -γ).
We replace y and y ′ by their value expressed using the characteristics of D:

R α,β,γ (x) -R α,β,γ (x ′ ) = αx -β ax -c -R a,b,c (x) b -αx ′ -β ax ′ -c -R a,b,c (x ′ ) b .
Which leads to:

R α,β,γ (x) -R α,β,γ (x ′ ) = (αb -βa)(x -x ′ ) b - β b (R a,b,c (x ′ ) -R a,b,c (x)). Since R a,b,c (x) < R a,b,c (x ′ ) there exists 1 ≤ k ≤ b -1 such that R a,b,c (x ′ ) - R a,b,c (x) = k. So: R α,β,γ (x) -R α,β,γ (x ′ ) = (αb-βa)(x-x ′ ) b -kβ b . We have |x -x ′ | ≤ b and lemma 1 provides (αb -βa) = ±1. We know that 1 ≤ β ≤ b-1 and 1 ≤ k ≤ b-1 so: R α,β,γ (x)-R α,β,γ (x ′ ) ≤ 1-1 b . The remainder difference is an integer therefore R α,β,γ (x) -R α,β,γ (x ′ ) ≤ 0.
The following corollary of proposition 1 states that a leaning point of a DSS stays a leaning point for its pivot erosion. Let us denote m (resp. M ) the upper (resp. lower) leaning point of S that belongs to S ′ . Then the point m (resp. M ) is also an upper (resp. lower) leaning point for S ′ .

Note that the results of this corollary can also be deduced from the generation algorithm of I. Debled-Renesson [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF] and the work on erosions in the PhD. Thesis of T. Roussillon [START_REF] Roussillon | Algorithmes d'extraction de modeles géométriques discrets pour la représentation robuste des formes[END_REF]. We provide here the result as a direct consequence of the above proposed proposition.

Proof. Let us first note that S ′ as pivot erosion of S contains exactly two leaning points of S. Let (a, b, c) be the minimal characteristics of S. Since m(x m , y m ) is the only upper leaning point of

S in [u, v], we have ∀x ∈ [u, v], 0 = R a,b,c (x m ) < R a,b,c (x) and ∀x ∈ [u, v], |x m -x| < b
otherwise there would be another upper leaning point of S in the DSS. The proposition 1 can be applied and directly leads to the result. The demonstration for M is similar.

This second corollary states that for two DSSs linked by a pivot dilation / pivot erosion relation, on a subsegment common to both DSSs, the points of minimal and maximal remainders are the same for both DSSs: Proof. The proof is based on the recursive application of the preceding corollaries on a sequence of DSSs defined as follow: the sequence starts with S = S 0 = S (D, u, v 0 ) (with v 0 = v) of minimal characteristics (a 0 , b 0 , c 0 ). The second DSS of the sequence, S 1 = S (D, u, v 1 ) of minimal characteristics (a 1 , b 1 , c 1 ), is defined as the right pivot dilation of S 0 . The minimum of the sequence of remainders R a1,b1,c1 (u, v) is the minimum of the remainders R a0,b0,c0 (u, v) (Corollary 2). The DSS S = S 0 is defined on [u, v] and thus the minimum remainder for the minimal characteristics of S 0 is 0 since there are three leaning points in the DSS and therefore at least one upper leaning point. Since the remainder 0 defines an upper leaning point, the abscissa of the minimum of the remainders of S 1 is the abscissa of an upper leaning point of S. The next DSS S 2 is defined as the right pivot dilation of S 1 and corollary 2 states that the minimum of the remainders of S 2 corresponds to the minimum of the remainders of S 1 which is an upper leaning point of S. This process is repeated until the minimal characteristics of the pivot dilation S i are (a, b, c). The intervals defining the DSSs of the sequence are strictly increasing. So, at some point, we reach an interval such that there are three leaning points of D in the segment. Corollary 2 can be applied at each step of the recursion. The same reasoning applies for the maximum of the remainder sequence as well.

min (R a,b,c (u, v)) = R a,b,c (x m ) ⇒ min (R α,β,γ (u, v)) = R α,β,γ (x m ) . Proof. If v-u
Example 1. Let us consider the DSL D = D (5, 13, 0) and DSS S = S 0 = S (D, 6, 9) with minimal characteristics (1, 2, 2). We apply repeated right pivot dilations and look at the sequence of remainders of the points of D on the interval [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF]26] for the DSSs minimal characteristics. The minimal characteristics of each DSS S i (underlined in the example) are computed with forthcoming proposition 2. We are interested in the behaviour of the remainders on the interval [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF][START_REF] Klette | Digital straightness -a review[END_REF] (over-lined) defining S 0 :

• S = S 0 = S (D, 6, 9) with minimal characteristics (1, 2, 2).

The sequence of remainders of the points of D for (1, 2, 2) on the interval [6, 26] is {0, 1, 0, 1, 2, 1, 2, 1, 2, 3, 2, 3, 4, 3, 4, 3, 4, 5, 4, 5, 4}.

The weakly lower exterior point is at abscissa 10 (in bold).

• S 1 = S (D, 6, 10) with minimal characteristics (1, 3, -1).

The sequence of remainders of the points of D for (1, 3, -1) on the interval [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF]26] is {1, 2, 0, 1, 2, 0, 1, -1, 0, 1, -1, 0, 1, -1, 0, -2, -1, 0, -2, -1, -3}. The weakly upper exterior point is at abscissa 13 (in bold). The minimum and maximum remainders on [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF][START_REF] Klette | Digital straightness -a review[END_REF] (over-lined, bold) are upper and lower leaning points for S. The reverse is not true: all the upper and lower leaning points of S are not remainders' minima and maxima for S 1 on [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF][START_REF] Klette | Digital straightness -a review[END_REF]. Note also that the two leaning points of S 1 in [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF][START_REF] Klette | Digital straightness -a review[END_REF] are leaning points of S.

• S 2 = S (D, 6, 13) with minimal characteristics (2, 5, 1).

The sequence of remainders of the points of D for (2, 5, 1) on the interval [6, 26] is {1, 3, 0, 2, 4, 1, 3, 0, 2, 4, 1, 3, 5, 2, 4, 1, 3, 5, 2, 4, 1}. The weakly lower exterior point is at abscissa 18 (in bold). The minimum and maximum remainders on [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF][START_REF] Klette | Digital straightness -a review[END_REF] (over-lined, bold) are upper and lower leaning points for S. Note here that while we had two leaning points in [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF][START_REF] Klette | Digital straightness -a review[END_REF] for S 1 we have only one left in S 2 in [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF][START_REF] Klette | Digital straightness -a review[END_REF].

• S 3 = S (D,

Third leaning point

In the previous subsection, we presented a way of locating an upper and a lower leaning point of a minimal DSS S = S (D, u, v) with the remainders of D on the interval [u, v]. In order to determine the minimal characteristics of S two leaning points are not sufficient, we need a third leaning point. Once we have a third leaning point, we have either at least two lower or two upper leaning points which immediately yields the characteristics. The third leaning point is either an upper or a lower leaning point. As the following proposition states, the location of this third leaning point depends on the location of the first two leaning points. The remainder of the third leaning point we are looking for is the minimum or maximum remainder on a particular sub-interval.

largest interval [u ′ , v ′ ] among the intervals [u, x m -1], [x m +1, v], [u, x M -1] or [x M + 1, v]. Then: • If the largest interval is [u, x m -1] or [x m + 1, v],
the third leaning point is the point with the smallest remainder of the interval.

• If the largest interval is [u, x M -1] or [x M + 1, v],
the third leaning point is the point with the biggest remainder of the interval.

If there are several largest intervals then the third leaning point can be found in any of these largest intervals.

Proof. We know that there exists a third leaning point. Considering corollary 2, we know that this leaning point is an extremal remainder in one of the four intervals. It is either a point of minimal remainder in [u,

x m -1], [x m + 1, v] or a point of maximal remainder in [u, x M -1] or [x M + 1, v].
Let us suppose that the third leaning point is not located in the largest interval among the four, but in one of the others. Since the consecutive leaning points of same type have always the same difference of abscissa β, where (α, β, γ) are the minimal characteristics of the DSS S, there would also be a leaning point in the largest interval. There is therefore always a leaning point is the largest interval among the four.

Proposition 2 is enough to determine the minimal characteristics. If T (x t , y t ) is the third leaning point found with help of the proposition and A(x A , y A ) is the other leaning point of same type then we know that β

= |x A -x T | k and α = |y A -y T | k for k = gcd (|x A -x T | , |y A -y T |)
, with (α, β, γ) the minimal characteristics of the DSS. The translation constant γ is trivial to compute. Before we show that the third leaning point obtained with help of the previous proposition leads always to k = 1, let us introduce a lemma that links the remainders of a DSL, of a minimal subsegment of it and their respective periods.

• if u ≤ x < x + β ≤ v then R a,b,c (x + β) = R a,b,c (x) + (aβ -αb) ; • if u ≤ x < x + b ≤ v then R α,β,γ (x + b) = R α,β,γ (x) -(aβ -αb).
Proof. Let y (resp. α) be the y-coordinate of the point of D with x (resp. β) as x-coordinate. Then R a,b,c (x + β) = a(x + β)b(y + α)c. By developing the last equation we obtain R a,b,c (x + β) = axbyc + aβαb which is equivalent to R a,b,c (x + β) = R a,b,c (x) + (aβαb). The proof for the second part of the lemma is similar.

We now have three leaning points which means that we have two leaning points of the same type. We do not know, however, if the third leaning point is close to the previous one of same type obtained with proposition 2. This is the object of this last theorem that tells us that it is and therefore that we can compute directly the minimal characteristics: Theorem 2. Let us consider a DSL D = D (a, b, c) and a DSS S = S (D, u, v) with minimal characteristics (α, β, γ) such that LP 1 (x 1 , y 1 ) and LP 2 (x 2 , y 2 ) are the two leaning points of same type (upper or lower) determined by Theorem 1 and proposition 2. Then the minimal characteristics of S are given by:

(α, β, γ) = (|y 1 -y 2 | , |x 1 -x 2 | , αx 1 -βy 1 ) Proof. Let

Determining minimal and maximal remainders

In Section 2, we have shown that remainders minima and maxima determine the location of upper and lower leaning points of a minimal discrete straight segment. In this section we will show how to determine such a minimum and a maximum in an efficient way. Let us show that the minimum and maximum can be determined in pretty much the same way as the Greatest Common Divisor computation in the Euclidean algorithm. Let us first note that our method supposes that we compute the Bezout coefficients for the DSL D = D(a, b, c). This computation is one of the first steps in the method.

Let us also note that if the DSS S = S(D, u, v) of the DSL D = D(a, b, c) is defined in such a way that vu ≥ b then the remainder value 0 and the remainder value b -1 are necessarily in the remainder subsequence R a,b,c (u, v) and thus the search for the minimum and maximum is unnecessary. Let us note as well that if we have the Bezout coefficients for a and b, it is easy to determine if 0 or b -1 belong to R a,b,c (u, v) which can of course happen even if vu < b. In these cases as well, we do not have to search for the minimum and/or the maximum remainder. Lastly, let us note that we may consider only DSL with a translation coefficient equal to 0. Indeed, let us consider the Bezout coefficient (α, β) of (a, b) such that aαbβ = 1. Then a solution of axby = c is (cα, cβ) and axby = c is equivalent to axby = a(cα)b(cβ) which leads to a(x -(cα))b(y -(cβ)) = 0. Therefore we have the following remainder sequence equality R a,b,c (u, v) = R a,b,0 (ucα, vcα). However, since cα can be a very big integer compared to u this can pose computational concerns. It is however easy to see that, since there is a periodicity of b, this is the same as

R a,b,c (u, v) = R a,b,0 u -cα b , v -cα b .

Span Start and Span End remainder sequences

The following theorem states that the span start and end remainders are arithmetic progression modulo sequences:

Theorem 3. Let us consider the remainder subsequence ζ = R a,b,0 (u, v), with 0 ≤ a ≤ b and gcd (a, b) = 1. • if au b = av b then min(ζ) = au b and max(ζ) = av b ; • otherwise min(ζ) ∈ ζ ′ where ζ ′ = R { -b a },a, 0 1 + a(u-1) b , av b ;
• and max(ζ

) ∈ ζ ′′ where ζ ′′ = b -a + R { -b a },a,0 1 + au b , a (v+1) b .
These results have already been proposed in part by J-P Reveilles [START_REF] Reveillès | Calcul en Nombres Entiers et Algorithmique[END_REF]. The main difference lies in the determination of the interval bounds.

Proof. As preliminary remark, let us just recall that ζ = R a,b,0 (u, v) is the remainder sequence of a minimal DSS S = S(D, u, v) associated to a DSL D with minimal characteristics (a, b, 0). On each span of ordinate ax b , the remainders are ordered in increasing order. A span is a set of connected points of D with same ordinate. If the points P D (u) and P D (v) are on the same span, au b = av b , then the minimum remainder can be found at abscissa u and the maximum at abscissa v. Let us suppose for what follows that P D (u) and P D (v) are not on the same span. The minimum of the sequence is necessarily at the beginning of one of these spans. Now, it is easy to see that the sequence of span starting remainders is the remainder sequence we are looking for: Firstly, let us notice that the remainder r is in the beginning of a span iff ra < 0 and thus if 0 ≤ r < a. The next starting span remainder r ′ verifies r + k.a = b + r ′ , where k is the number of times you add a to r to reach the next span. So r ′ = r + k.ab. Since we have 0 ≤ r ′ < a, r ′ = r-b a . The sequence of starting remainder values is thus given by the arithmetic progression congruence sequence { -b a }x a .

We know now that the span start remaining sequence is R { -b a },a,0 (u ′ , v ′ ) with u ′ and v ′ to be determined. The spans in the DSS may be incomplete spans of D. The first span in S is incomplete iff P D (u -1) is in the same span than P D (u) and the last span is incomplete iff P D (v + 1) is in the same span than P D (v) for D. Since all start span remainders are smaller than any other remainder, for the last span of our sequence ζ it does not really matter if the span is incomplete since we just want the start of the span. The value v ′ is thus simply given by the corresponding ordinate of the corresponding digital line (to each ordinate, one span) so v ′ = av b . For the same reason, the minimum of ζ can not be in the first span if it is incomplete (for P D (u) and P D (v) on different spans). For the beginning of ζ ′ we want the first span start of the subsequence which is on the first span if it is complete or otherwise the second span and thus

u ′ = 1 + a(u-1) b .
For the maximum of the remainders, it is easy to see that if the span start remainders form the sequence

a-{ b a }x a ; u ′ ≤ x ≤ v ′ then the end of the span forms the sequence b -a + a-{ b a }(x+1) a ; u ′′ ≤ x ≤ v ′′ since the point
that follows the end of a span is the beginning of the next span. The first value of this maximum sequence is the remainder that is followed by the second span start remainder, thus the x + 1. The new sequence start and end values are simply given by au b and a(v+1) b -1. That is however not exactly what our theorem says. In fact, in order to handle an abscissa x in our algorithm and not x and x + 1, we replace x by x + 1 and thus u ′′ becomes u ′′ + 1 and v ′′ becomes v ′′ + 1 which leads to the given formulas.

Theorem 3 tells us that we can build two sequences of remainder sequences that allows us to compute the minimum and the maximum of a remainder sequence. This process may however not be very efficient: we replace a sequence modulo b by a sequence modulo a which means that we replace a number of points in the DSS by a number of spans. If the slope if close to 1, the number of points is similar to the number of spans and we do not gain much by replacing one sequence by the other. There is however a simple way to make it efficient: ; 1 ≤ x ≤ 88 leads to the following steps in the search for the minimum. Note that we took Fibonacci sequence numbers as parameters (and of course an interval without the remainder 0) to maximize the number of steps in this example. We call ζ i the minimum sequences: Proof. In the first step we replace a sequence of v-u remainders by a sequence of min(a, ba) remainders. Then at each following step we divide the number of values in the remainder sequence by at least a factor 2 (lemma 3).

• ζ 0 = R 55,
Proposition 3 is only a quite crude estimation of the computational complexity of the minimum (and maximum) search. A closer look has to be taken. Since the method is close to the Euclidean algorithm, some clues can be taken from the complexity studies of the Euclidean algorithm. However, since many intervals may contain the remainders 0 or b -1 and thus transform some part of the minimum (or maximum) search into constant time searches, our guess is that the Euclidean algorithm complexity as it has been proposed, times three, is also only an upper bound. The fine study of this computational complexity is a difficult problem here and goes beyond the scope of the paper. It represents an interesting question for the future.

Note also that the overall complexity of the method includes the computation of the Bezout coefficients for the DSL coefficients (a, b) with a well known complexity of O(log(a)) (since 0 ≤ a < b and in regard of Theorem of Lamé [START_REF] Knuth | The Art of Computer Programming[END_REF]). This is therefore the overall complexity of the method. Of course, if many different DSS are computed for a single DSL, then the Bezout coefficients need to be computed only once.

Algorithm 1 presents the search for the minimum. The search for the maximum is similar (do not forget to accumulate the values ba from the formula describing the maximum sequences in Theorem 3). Once a minimum or a maximum is obtained, it is easy to determine its position but that supposes that we have computed the Bezout coefficients of the DSL slope coefficients.

Experiments

We implemented our algorithm in C++ and used the open-source library DGTAL [START_REF] Dgtal | Digital geometry tools and algorithms library[END_REF] in order to compare our approach to the algorithm proposed by I. Sivignon and the ReversedSmartDSS algorithm proposed by Saïd and al. [START_REF] Lachaud | Two efficient algorithms for computing the characteristics of a subsegment of a digital straight line[END_REF].

Firstly, we accomplished experiments along the same protocol as the one proposed in [START_REF] Lachaud | Two efficient algorithms for computing the characteristics of a subsegment of a digital straight line[END_REF][START_REF] Sivignon | Walking in the farey fan to compute the characteristics of a discrete straight line subsegment[END_REF] on a 2.10 GHz Intel Dual Core. We first choose a maximal value N that corresponds to the maximal value that b can take. We fix a maximal value for the length n of the DSS. Then we randomly choose the parameters of the DSL, a and b such that a < b ≤ N , and the translation constant c as well as an abscissa for the first point of the DSS. Each experiment has been conducted with 10000 randomly chosen parameters. For each experiment, we find the minimal characteristics of the DSS contained in the DSL and compute the average running time. Figure 3 shows the results of our algorithm compared to the two algorithms in [START_REF] Lachaud | Two efficient algorithms for computing the characteristics of a subsegment of a digital straight line[END_REF][START_REF] Sivignon | Walking in the farey fan to compute the characteristics of a discrete straight line subsegment[END_REF] for the value of N : 10 9 . On this figure, the experiments are done by varying the length n of the DSS in the form 10 × 2 k in the interval [10, N ]. We can observe that our approach (Ouat and al.) is faster than the two other algorithms regardless of the length n of the DSS. This first diagrams give an idea on how these different algorithms behave on a long range of values.

Then we accomplished experiments in order to check the previous comparisons when common values of b are used in regard of the common sizes of pictures. On Figure 4, the experiments are done for the value of N : 10 4 by varying the length n of the DSS in the form n i + k where n i is the length of the previous step, k is a random value in the interval [START_REF] Anderson | Representation of digital line segments and their preimages[END_REF]100] and n i is in the interval [10, N ]. We can observe that our approach is still faster than the two other algorithms regardless of the length n of the DSS. Note that with this protocol, Figure 4 is not a simple zoom of Figure 3 as the complexity of the different algorithms may vary with vu (as charted) but also with a or b.

Finally, On Figure 5, we show the logarithmic behaviour of our approach in terms of the distance y vy u . To do so, we vary a value e that corresponds to y vy u in an interval [START_REF] Anderson | Representation of digital line segments and their preimages[END_REF]400000] by step of 1000. For each value of e, we ran our algorithm 10000 times with randomly chosen parameters. For this, we randomly choose a value for a but we ensure e 2 ≤ a ≤ e 2 + 10 6 . We choose a random b such that a < b and for each pair of characteristics a and b we randomly choose 10 values u and v so that y vy u = e and vu ≤ 2 × b (to avoid having 3 leaning points in the interval). At last, for each pair of values u and v we make 10 times the computation of the minimal characteristics of the DSS contained in the DSL. After 10 6 runs for a given e we compute the average running time.

Conclusion

We have proposed a new logarithmic-time algorithm to determine the minimal characteristics of any DSS. This algorithm takes, as input, the characteristics of the digital straight line (DSL) as well as the two endpoints of the DSS. Our method is based on modulo remainders that can be associated to each point of the DSL and DSS. We show that these remainders are ordered in a similar way for the DSL and DSS and that the extremes in the DSL remainders correspond to leaning points in the DSS. This allows us to determine the minimal characteristics of the DSS. The main algorithmic aspects of the method is the computation of the remainder minimum and maximum on an interval. We give a method, akin to the Euclidean algorithm, that determines this minimum and this maximum in logarithmic time. Experiments show that our algorithm is faster than previous algorithms proposed in [START_REF] Lachaud | Two efficient algorithms for computing the characteristics of a subsegment of a digital straight line[END_REF][START_REF] Sivignon | Walking in the farey fan to compute the characteristics of a discrete straight line subsegment[END_REF]. One of the advantages compared to previous methods is that it is extremely simple with the main procedure akin to the Euclidean algorithm. This opens the way to future improvements especially in the computational aspects although our method is already the fastest so far.

Previous methods [START_REF] Lachaud | Two efficient algorithms for computing the characteristics of a subsegment of a digital straight line[END_REF][START_REF] Sivignon | Walking in the farey fan to compute the characteristics of a discrete straight line subsegment[END_REF] were based on the exploration of the Stern-Brocot tree or Farey fans. A link between these methods and our approach should shed new lights on these exploration schemes. We have considered a DSL with a 0 2 0 0 0 0 1 00 0 00 200 000 300 000 40 0 00 0 2 2 .2

Variation of the vertical length of the DSS Execution time in microseconds rational slope. What about irrational slopes and the link to Sturmian words? One of the main interest of this new method is that it opens the way to exploring remainder properties in higher dimensions. This however seems to be complicated. As one can see on Figure 6. By removing a row from the 3D plane segment P of characteristics (3, 7, 18, 0) (0 ≤ 3x + 7y + 18z + 0 < 18) on the (x, y)-interval [START_REF] Anderson | Representation of digital line segments and their preimages[END_REF][START_REF] Dgtal | Digital geometry tools and algorithms library[END_REF] × [START_REF] Berthé | An arithmetic and combinatorial approach to three-dimensional discrete lines[END_REF][START_REF] Coven | Sequences with minimal block growth[END_REF], we obtain a new plane segment P ′ of characteristics (2, 5, 11, -3) where a point of remainder 2 in P becomes leaning point for P ′ while a point of remainder 1 in P does not. The equivalent of Theorem 1 is not verified in, at least, dimension 3. This raises numerous questions: the remainder order property of Theorem 1 seems however still mostly true. Is there a weaker property? In this example we chose to minimize the coefficient in z (with appropriate symmetries) to determine the 3D minimal characteristics of the plane segment. Are there other possible choices that would preserve the remainder order of Theorem 1 in 3D? What about the erosion process in dimension 3? Is there a more appropriate alternative to removing a complete row or column? This opens numerous perspectives.

1 .

 1 Digital Straight Line (DSL for short) D (a, b, c) of integer characteristics (a, b, c) is the set of digital points (x, y) ∈ Z 2 such that 0 ≤ axbyc < max (|a| , |b|) with gcd (a, b) = 1. These DSL are 8-connected and called naive DSL [6]. The slope of the DSL is the fraction a b . The value c is sometimes called the translation constant. In this paper, without loss of generality, we assume that 0 ≤ a ≤ b. This corresponds to a DSL in the first octant with slopes 0 ≤ a b ≤ In this case, we have one and only one point, denoted P D (x), in D with abscissa x. The ordinate is then y = ax-c b . A DSL can also be defined as the integer points of a strip delimited by the lower leaning line D L : ax-by-c = b-1 and the upper leaning line D U : ax-by-c = 0 [6]. Upper (resp. Lower ) leaning points are the digital points of the DSL lying on the upper (resp. lower) leaning lines. A weakly exterior point is a point of D that verifies axbyc = -1 (in this case we speak also of a weakly upper exterior point) or axbyc = b (in this case we speak also of a weakly lower exterior point). A Digital Straight Segment (DSS for short) S (D, u, v) associated to the DSL D = D (a, b, c) and endpoints P D (u) and P D (v) is the subset of D with points of abscissa in [u, v]. A DSS is a finite 8-connected subset of a DSL. The characteristics of a DSS are those of a corresponding DSL however contrary to what happens for continuous straight line segments, a DSS is a subset of an infinite number of DSLs with different characteristics: for instance, the DSS of characteristics (5, 8, 0) and (8, 13, -1) have the same points of abscissa on interval [0,

Figure 1 :

 1 Figure 1: Illustration of the DSS in the dilation serie.

Lemma 1 .

 1 Let us consider a DSL D and two DSSs S = S (D, u, v) of minimal characteristics (a, b, c) and a pivot erosion (or pivot dilation) of S: S ′ = S (D, u ′ , v ′ ) of minimal characteristics (α, β, γ). Then the following equality stands: aβαb = ±1. Proof. Let us consider the DSS S = S (D, u, v) of minimal characteristics (a, b, c) and a right pivot erosion of S: S ′ = S (D, u, v ′ ) of minimal characteristics (α, β, γ). The right pivot dilation of S ′ :

  For instance, for D = D (5, 13, 0), the DSS S (D, -7, 13) (of minimal characteristics (5, 13, 0)) is the right pivot dilation of the DSS S (D, -7, 12) (of minimal characteristics (3, 8, 0)). In this example, [u, v] = [-7, 12] while b = 13. The proposition does not provide a complete answer over [u, v] because of the condition |xx ′ | < b. We believe that this condition is not necessary but we have not a proof yet. Proof. We have R a,b,c (x) = axbyc and so y = ax-c-R a,b,c (x) b

Corollary 1 .

 1 Let us consider a DSL D, a DSS S = S (D, u, w) and the right pivot erosion DSS S ′ = S (D, u, v).

Corollary 2 .

 2 Let us consider a DSL D, two DSSs S = S (D, u, w) of minimal characteristics (a, b, c) and S ′ = S (D, u, t) of minimal characteristics (α, β, γ) such that S is the right pivot dilation of S ′ . Let us also consider an interval [u, v] such that u ≤ v ≤ t < w Then:

  ≥ b then there exist an upper m(x m , y m ) and a lower M (x M , y M ) leaning point of D in the DSS S (D, u, v). Corollary 1 can be applied and we have R a,b,c (x m ) = 0 = R α,β,γ (x m ) and the result stands. When vu < b then proposition 1 can directly be applied. Let us now present one of the main results of this paper: Theorem 1. Let us consider a DSL D = D (a, b, c) and the minimal DSS S = S (D, u, v). Then the point m(x m , y m ) (resp. M (x M , y M )) of minimal (resp. maximal) remainder of D on [u, v] is an upper (resp. lower) leaning point for S.

Proposition 2 .

 2 Let us consider a DSL D = D (a, b, c) and a DSS S = S (D, u, v) such that m(x m , y m ) is the upper leaning point of S with minimal remainder for D on [u, v] and M (x M , y M ) is the lower leaning point of S with maximal remainder for D on [u, v]. The abscissa of the third leaning point we are searching is in the

Lemma 2 .

 2 Let us consider a DSL D = D (a, b, c) and a DSS S = S (D, u, v) of minimal characteristics (α, β, γ). Then:

  us consider the DSL D = D (a, b, c) of minimal characteristics (a, b, c) and a DSS S = S (D, u, v) of minimal characteristics (α, β, γ). Let us call LP 2 the third leaning point leaning point of S we are looking for. The different leaning points belong to the leaning line of the DSS and verify lemma 2. All the leaning points on this leaning line have remainders R a,b,c (x m ) + k |aβ -αb| or R a,b,c (x M )k |aβ -αb| depending if LP 2 is upper or lower leaning point. LP 2 is the one with the leaning point with second largest or smallest remainder for D on the corresponding largest sub-interval (proposition 2).

Figure 2

 2 Figure 2 illustrates the last part of the proof of Theorem 2. We represented the points of the DSL and DSS with a remainder representation (x, R 13,28,0 (x)). Horizontally are the points with same DSL remainder. Diagonally (the black thin lines) we have the points with same DSS remainder. We can see the aligned upper leaning points of the DSS with the two leaning points at the bottom that have respectively the lowest DSL remainder (black circle) and the lowest DSL remainder on the left of the other leaning point (grey disk). A little additional remark on the figure. The upper leaning points in the figure are on the bottom because the figure represents horizontally the remainders of D. Upper leaning points are called upper because when drawing the leaning lines axbyc = 0 and axbyc = b -1 with 0 ≤ a ≤ b the leaning line axbyc = 0 lies over the leaning line axbyc = b -1 and thus the upper leaning points (geometrically upper) are those with the lower remainder values.

Figure 2 :

 2 Figure 2: Remainder representation of the DSL D = D (13, 28, 0) and the convex Hull of the DSS S (D, 3, 16) of minimal characteristics (5, 11, -1). The two big circles correspond the two leaning points with maximal and minimal remainder. The grey disk corresponds to the third leaning point.

Lemma 3 .Example 2 .

 32 Let us consider the remainder subsequence ζ = R a,b,0 (u, v), with 0 ≤ a ≤ b and gcd (a, b) = 1. Let us suppose that 2a > b then:min(ζ) ∈ ζ ′ and max(ζ) ∈ ζ ′ where ζ ′ = R -a,b,0 (-v, -u) Proof. It is simple to see that -axb is the sequence ζ in reverse order with a fixed remainder 0. The values of both sequences are the same. The minimum and maximum values are thus preserved. With Lemma 3, we transform a sequence with a spans into a sequence with ba spans and a DSS of slope a b > 1 2 into a DSS of slope b-a b < 1 2 . The spans are bigger and the computation time is reduced. The remainder sequence ζ = R 55,89,0 (1, 88) = 55x 89

The new parameters are: -89 34 = 13 , 89 = - 1 . 13 = 5 ,= - 1 . 3 . 2 . 3 .

 34138911351323 u ′ = 1 + 34 * (-34) 89 = -12 and v ′ = 34 * (-1) You can note that all the span start values are forming up this new sequence (of course, the incomplete starting span 34, 68 excluded).• ζ 3 = R 5,13,0 (-12, -1) = {5, 10, 2, 7, 12, 4, 9, 1, 6, 11, 3, 8}.The new parameters are: -34 u ′ = 1 + 13 * (-13) 34 = -4 andv ′ = 13 * (-1)34 You can note that all the span start values are forming up this new sequence (of course, the incomplete starting span 13, 26 excluded).• ζ 4 = R 2,5,0 (-4, -1) = {2, 4, 1, 3}. • ζ 5 = R 1,2,0 (-1, -1) = {1}.We have now the minimal value on the interval. Some thoughts on the computational complexity Proposition The complexity of searching a minimum (respectively a maximum) in a sequence of remainders defined on an interval [u, v] is bounded by O(log(min(a, ba))).

Figure 3 :

 3 Figure 3: Maximal value for b: 10 9 . DSS Length charted.

Figure 4 :

 4 Figure 4: Maximal value for b: 10 4 . DSS Length charted.

Figure 5 :

 5 Figure 5: Varying the distance yvyu let be e. Minimal value for a is e 2 + k, where k is a randomly chosen positive integer. Likely b is chosen so that vu ≤ 2 × b. DSS vertical length (yvyu) charted.

Figure 6 :

 6 Figure 6: 3D Planes with remainders. In the center, the plane of characteristics (3, 7, 18, 0) on the (x, y)-interval [1, 7] × [2, 5]. Around it, the plane segments obtained by removing one row or column with the new plane characteristics. In red, leaning points. In pink (in the center), points that have maximal and minimal remainders, would be leaning points in all the plane segments if Theorem 1 were respected in dimension 3.

  [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF][START_REF] Kovalevsky | New definition and fast recognition of digital straight segments and arcs[END_REF] with minimal characteristics(3, 8, -1). The sequence of remainders of the points of D for (3, 8, -1) on the interval[START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF] 26] is {3, 6, 1, 4, 7, 2, 5, 0, 3, 6, 1, 4, 7, 2, 5, 0, 3, 6, 1, 4, -1}. The weakly upper exterior point is at abscissa 26 (in bold). The minimum and maximum remainders on[START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF][START_REF] Klette | Digital straightness -a review[END_REF] (over-lined, bold) are upper and lower leaning points for S. There is no leaning point of S 3 in[START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF][START_REF] Klette | Digital straightness -a review[END_REF] any more. The property of the minimum and maximum remainders stands however.

	• S 4 = S (D, 6, 26) with minimal characteristics (5, 13, 0). We reached the
	characteristics of D.
	The sequence of remainders of the points of D for (5, 13, 0) on the interval
	[6, 26] is {4, 9, 1, 6, 11, 3, 8, 0, 5, 10, 2, 7, 12, 4, 9, 1, 6, 11, 3, 8, 0}. There are
	no more weakly exterior points. The minimum and maximum remainders
	for D on [6, 9] (over-lined, bold) are upper and lower leaning points for S.

  One can see that the two sequences ζ 0 and ζ 1 are exactly in reverse order but while ζ 0 has spans of size 1 and 2, ζ 1 has spans of size 2 and 3. The span starting and span end values stay the same.• Now we start reducing the size of the sequence ζ 2 = R 13,34,0 (-33, -1) =

	89,0 (1, 88) = {55, 21, 76, 42, 8, 63, 29, 84, 50, 16, 71, 37, 3, 58, 24, 79,
	45, 11, 66, 32, 87, 53, 19, 74, 40, 6, 61, 27, 82, 48, 14, 69, 35, 1, 56, 22, 77, 43,
	30, 85, 51, 17, 72, 38, 4, 59, 25, 80, 46, 12, 67, 33, 88, 54, 20, 75, 41, 7, 62, 28, 83, 49,
	15, 70, 36, 2, 57, 23, 78, 44, 10, 65, 31, 86, 52, 18, 73, 39, 5, 60, 26, 81, 47, 13, 68, 34}
	• We had 2×55 > 89 so as first step we apply lemma 3: ζ 1 = R 34,89,0 (-88, -1) =
	{34, 68, 13, 47, 81, 26, 60, 5, 39, 73, 18, 52, 86, 31, 65, 10, 44, 78, 23, 57, 2, 36, 70,
	15, 49, 83, 28, 62, 7, 41, 75, 20, 54, 88, 33, 67, 12, 46, 80, 25, 59, 4, 38, 72, 17, 51, 85,
	30, 64, 9, 43, 77, 22, 56, 1, 35, 69, 14, 48, 82, 27, 61, 6, 40, 74, 19, 53, 87,
	32, 66, 11, 45, 79, 24, 58, 3, 37, 71, 16, 50, 84, 29, 63, 8, 42, 76, 21, 55}.
	{13, 26, 5, 18, 31, 10, 23, 2, 15, 28, 7, 20, 33, 12, 25, 4, 17, 30, 9, 22, 1, 14, 27,
	6, 19, 32, 11, 24, 3, 16, 29, 8, 21}.

Acknowledgements:

We would like to thank Valérie Berthé for her suggestions. Our special thanks to Isabelle Debled-Renesson for the result in Lemma 1 which proved to be the link between the remainders of DSL and DSS we were looking for.

Algorithm 1: ComputeMin (In: a, b, c, u, v. Out: mini) --a,b,c: characteristics of the DSL; u,v: abscissa of the DSS endpoints; mini: minimal remainder)

break (* We have our minimal remainder *) ;