A geometrical characterization of regions of uniqueness and applications to discrete tomography

(1)

This content has been downloaded from IOPscience. Please scroll down to see the full text.

Download details:

IP Address: 131.175.161.12

This content was downloaded on 19/11/2015 at 10:13

Please note that terms and conditions apply.

A geometrical characterization of regions of uniqueness and applications to discrete

tomography

View the table of contents for this issue, or go to the journal homepage for more 2015 Inverse Problems 31 125011

(2)

A geometrical characterization of regions of

uniqueness and applications to discrete

tomography

Paolo Dulio

1,3

, Andrea Frosini

2

and Silvia M C Pagani

1

Dipartimento di Matematica‘F. Brioschi’, Politecnico di Milano, Piazza Leonardo da Vinci 32, I-20133 Milano, Italy

2

Dipartimento di Matematica e Informatica‘U. Dini’, Università di Firenze, viale Morgagni 67/A, I-50134 Firenze, Italy

E-mail:paolo.dulio@polimi.it,andrea.frosini@uniﬁ.itandsilviamaria. pagani@polimi.it

Received 20 July 2015, revised 15 October 2015 Accepted for publication 19 October 2015 Published 18 November 2015

Abstract

In the reconstruction problem of discrete tomography, projections are con-sidered from aﬁnite set  of lattice directions. Employing a limited number of projections implies that the injectivity of the Radon transform is lost, and, in general, images consistent with a given set of projections form a huge class. In order to lower the number of allowed solutions, one usually tries to include in the problem some a priori information. This suggests that modelling the tomographic reconstruction problem as a linear system of equations is pre-ferable. In this paper we propose to restrict the usual notion of uniqueness, related to the solutions of the linear system, and to provide, for each set,a geometrical characterization of the shape of a lattice subset, say region of uniqueness (ROU), forming a partial, fast reconstructible, solution. Any selected set  intrinsically determines its ROU inside an arbitrary lattice grid. For instance, trivially, if  = 1, the ROU is represented by two rectangles having sizes equal to the absolute values of the entries of the unique direction in,and placed at two opposite corners of the chosen grid. Surprisingly, if  = 2, the problem becomes much more complicated. Our purpose is to provide a geometrical characterization of the ROU. This is based on a double Euclidean division algorithm(DEDA), which runs in polynomial time. It turns out that the ROU is delimited by a zigzag proﬁle obtained by means of numerical relations among the entries of the employed directions. According to different inputs in DEDA, the shape of the ROU can change consistently, as it can be easily observed from the provided examples. Moreover, after

Inverse Problems 31(2015) 125011 (31pp) doi:10.1088/0266-5611/31/12/125011

3

(3)

selecting a region of interest(ROI) from a given phantom, we exploit DEDA to reconstruct the part of the ROI which falls in the ROU and, with a few further a priori knowledge, even parts of the ROI which are outside the ROU. Keywords: discrete tomography, Euclidean algorithm, region of interest, region of uniqueness, bad conﬁguration

(Some ﬁgures may appear in colour only in the online journal) 1. Introduction

In computerized tomography(CT) the reconstruction of the density function of an unknown object by means of quantitative data, say projections, collected by incident x-rays, is con-sidered. This can be done by adapting to the real world situation a theoretical mathematical approach, based on the inversion of the Radon transform. The most significant drawback with a purely theoretical approach relies on the fact that the scan devices allow to collect only a finite number of projections along a fixed set of directions, which implies that there are no chances, in general, of achieving an exact reconstruction by the standard mathematical algorithms. As a matter of fact, the reconstructed object may result quite different from the starting unknown one, sometimes even sharing no elements with it. Moreover, in a medical CT scan analysis, the entire field of view often includes only a region of anatomic interest (ROI). This, on the one side, should reduce the needed dose of radiation to be delivered to the patient; from the other side, it prevents the x-rays directions from being arbitrarily chosen, since these must match the requested ROI. In the typical frame of discrete tomography(DT) [14,15] only few types of different densities (say, 2–6) are involved, and, in the special case

of binary tomography (BT) we only want to detect the presence or absence of one single material at different parts. The term discrete relates both to the change of the domain of the unknown density function into the integer two- or three-dimensional lattice, i.e., its dis-cretization, and to the fact that the required number of directions, along which projections are taken, is very limited, in order to avoid damaging the objects to be studied. This leads to strong ambiguities in DT reconstructions, and several approaches for a quantitative description of their uncertainty have been already explored(see for instance [11,24] and the

cited bibliography). 1.1. Algebraic approach

Employing a limited number of projections implies that the injectivity of the Radon transform is lost. This suggests a different approach to the (discrete) tomographic reconstruction pro-blem, which can be considered from an algebraic point of view. Here, the density function to be detected, considered as an image consisting of N pixels, is represented as a column vector

 Î

x N._{The collected data consist of D different arrays, being D the number of involved} directions; the length Li of the ith array depends on the corresponding direction. If

å

= ₌

M _iD₁L ,i then a column vectorpÎM,representing the whole set of collected

mea-surements, is formed. In this way, the tomographic reconstruction problem is modelled as a linear system

=

(4)

where W is an M×N matrix, and

å

= = ¼ = w x p for alli 1, ,M. j N ij j i 1

Reconstructing the image is equivalent to solving the linear system(1).

1.2. Bad configurations

In general, images consistent with a given set of projections form a huge class. Ambiguous reconstructions come out due to the existence of ghosts, that is non-zero functions belonging to the null-space of the Radon transform. In the context of DT forﬁnite lattice sets, ghosts are also known under different names, such as bad conﬁgurations (see for instance [2, 23]),

interchanges, or switching components(this last term has been employed in the literature also in a more general context, see for instance [5, footnote page 2283] for a short comment). More precisely, for a selected set  of D lattice directions, an  -bad conﬁguration is a pair

Z W,

( )of lattice subsets of the working grid,each consisting of K(2D-1_{) distinct lattice}

points z1,¼,zK ÎZ and w1,¼,wK ÎW such that for each direction(a b, )Î, and for

eachzjÎZ,the line through zjin direction a b( , ) contains a pointwjÎW.A regionEÍ

admits an  -bad configuration if an -bad configuration(Z W, )exists for someD2, such thatZ ÍE,W Ì⧹E.When the requirement that points in Z or W are distinct is dropped, then we speak about  -weakly bad configurations. It becomes apparent that, due to bad configurations, faithful reconstruction of an unknown image is, in general, a hopeless task. Therefore,finding and studying bad or weakly bad configurations is a crucial problem in DT as well as in BT.

1.3. Uniqueness models

Despite the fact that exact reconstructions cannot be achieved in real tomographic analysis, applications need theoretical uniqueness models for limited number of projections, in order to have a ﬁnite counterpart of the usual integral Radon inversion formula. In order to gain uniqueness, different strategies have been considered, usually relying on additional geome-trical or combinatorial information about the unknown image. In particular, one can try toﬁnd special sets  of directions which, jointly with some a priori knowledge, can guarantee uniqueness of reconstruction. For instance, in the class of convex lattice sets, any set  such that   7 always ensures uniqueness, as well as suitably selected sets of four lattice directions (see [10]).

A different a priori information, which is often considered, is the knowledge of the size of the grid where the object to be reconstructed is conﬁned. In this case, one can take advantage of the algebraic approach introduced by Hajdu and Tijdeman in[13], which allows

a polynomial representation of switching components. In [12], this has been exploited to

show that uniqueness in a lattice grid can be achieved with four directions satisfying special requests. In[5], this result has been extended to a theoretical uniqueness model for families of

four lattice directions (see also [6] for a generalization to higher dimensions).

1.4. Local uniqueness

Instead of looking for suitable sets of directions which ensure uniqueness in a whole assigned lattice grid,one could try to investigate, without prior information, which part ofcan be uniquely reconstructed by means of a set of very few directions, not selected according to

(5)

some criterion, but arbitrarily given. This idea arises from two different kinds of local approaches to the tomographic reconstruction problem, frequently considered in the literature. From the one side, the use of particularly suitable directions in real applications could be prevented by some physical or mechanical constraints. It occurs, for instance, in electron microscopy [7], digital breast tomosynthesis [21] or dental tomography [16, 19], where

limited angle reconstructions based on truncated sinogram are exploited.

On the other hand, there may exist situations where an exact reconstruction of the whole image is not necessary, since one might be interested in determining features that are included in some ROI. This is the case of medical CT, when a disease has been previously well-localized and a follow-up scan of the deﬁned region is required.

The retrieval of such a local uniqueness was previously studied in [8], where, as a

preliminary step, some particular cases were analyzed. These included one of the situations that lead to the maximal conﬁguration [8, theorem 3], and a case where some of the expected pixels are missing [8, theorem 4]. The present paper generalizes the results proven in [8],

showing a uniﬁed picture of the determination of the local uniqueness for two directions. See also sections2.1and4.5) for more details concerning the old results in [8], and how the new

steps match and extend these particular cases.

1.5. Our work

Due to the physics of the scan device and to the highly destructive behavior of the x-rays scan, the number of directions employed in DT is usually extremely low, so linear systems of the form(1) are often under-determined, and this, in general, makes the related reconstruction

problem NP-hard. In this paper, we wish to explore a kind of prior knowledge that could be exploited in the process, in order to extend the class of polynomial-time reconstructible instances: the shape of a region where uniqueness of the reconstruction is guaranteed for a given set  of directions.

Our proposal is to restrict the usual notion of uniqueness related to the solution of the linear system, and to provide, for each set,a geometrical characterization of the shape of a lattice subset, say region of uniqueness(ROU), forming a partial solution of (1) and that can

be fast reconstructed. About that, we start from deﬁnition 1 that gives a natural iterative algorithm to compute the ROU according to the employed directions, and then we show its geometrical counterpart, i.e., an iterative geometrical process to characterize its shape without computing the internal points.

We remark that similar cases often appear in DT, and they usually provide a valuable tool for deeper combinatorial investigations. As an example, when facing the problem of the enumeration of the ROUs related to a given set  of directions, a geometrical characterization could allow one to deﬁne a constructive method to produce all the ROUs according to the growth of one or more parameters, such as semi-perimeter or area. Usually, the idea is to perform local expansions on each element of a certain size and then construct a set of elements of the successive size. Finally, standard techniques, such as Kernel method, appearing in [17], ECO method [3], Object Grammars [9] etc, allow us to determine the

generating functions of the studied class. A similar construction also leads to an algorithm for the exhaustive generation of the elements of the class. Under some special conditions, this algorithm requires only a constant amount of computation per object, in an amortized sense (algorithms attaining this benchmark are said to have the constant amortized time or CAT property).

Summing up our work, after ﬁxing a sufﬁciently large lattice grid, our purpose is twofold.

(6)

(1) First of all, we aim to characterize the shape of the ROU determined, inside,by the projections taken in a small set  of directions for the grid. When  = 1, the ROU is trivially represented by two rectangles placed at two opposite corners of . The size of the rectangles equals the absolute values of the entries of the unique direction in . Differently, if  = 2, the problem becomes much more complicated. Therefore we are interested in providing a complete description of how the ROU can be reconstructed in this case. This is done by means of a double Euclidean division algorithm (DEDA), which requires an amount of time growing polynomially with the components of the directions. It turns out that the ROU is delimited by a zigzag proﬁle obtained by numerical relations among the entries of the pair of employed directions.

(2) Secondarily, we focus on how DEDA can be exploited to select in advance pairs of suitable directions that allow a given ROI to be partially, and in some cases completely, included in the ROU. This could be useful in real applications, since one could try to adapt the ROU in order to match some ROI of the image x to be reconstructed. Note that, after computing the projections along pairs of assigned directions, reconstructions can be performed merely by a simple linear time recursive algorithm. Simultaneously, we show the ROU determined by DEDA, pointing out that perfect reconstructions are obtained for any portion of image falling in the ROU. In addition, if we assume to know also the number of different densities, the ROU determined by DEDA can be further enlarged, and a greater portion of the ROI can be determined. As a qualitative comment we could observe that the NP-hardness of the algebraic approach based on linear system(1) relies in the reconstruction of the central portion of the

image, while the border part, depending on the set  of employed directions, can be perfectly reconstructed in polynomial time.

Also, it is worth noting that our approach is regardless of the features of the image, such as being binary or with few grey levels.

1.6. Paper organization

The paper is organized as follows. In section2we introduce the basic notations employed in the paper, give the formal deﬁnition of the ROU and recall a few preliminary results obtained in[8]. In section3, we obtain some general properties concerning the ROU. In section4we show our main results, which lead to the geometrical characterization of the shape of the ROU. We show how the ROU changes according to the slopes of the two considered directions, which deserves a special interest even from the pure combinatorial point of view. It is based on numerical relations among the entries of the employed directions and it is explained by applying a modiﬁed version of the Euclidean algorithm (DEDA). Then, in section5, we provide a pseudo-code for DEDA, commenting on its complexity. In section6

we prove the details about the correctness of the algorithm. This turns out to be the most technical part of the paper. Section7is devoted to explicit applications of DEDA. We show the exact reconstruction of the ROU for different choices of the pair of directions a b( , ),

c d, .

( ) Moreover, we exploit DEDA to reconstruct a ROI included in the ROU and also show how one can proﬁt from some further a priori information to partially extend the ROI outside the ROU. The computations are performed both on phantoms and on real data. Finally, section8 gives some perspectives for future works and concludes the paper.

(7)

2. Notations and preliminaries

Let 2_{be the set of points having integer coordinates. We work in a}_{ﬁnite rectangular lattice}

grid Ì2, _having _lower-left _point _in _the _origin, _namely =_{(u v, ₎Î2_∣0u<m, 0v<n_{} for}_{m n}_, _Î_{. A point}_z_Î2 _{can be identi}_ﬁed

with the unit lattice square having z as lower-left corner, and, in this case, a point is also called pixel. We can deﬁne a function f :⟶,mapping each pixel to an integer value, which corresponds to a color or a grey level of the original image.

Let a b( , ) be a discrete direction, i.e., a couple of integers such thatgcd(a b, )=1,with the further assumption that a=1 if b=0 and conversely b=1 if a=0. We say that a ﬁnite set  ={(a bj, j)∣j=1,¼,D} of lattice directions is valid for if

å

<

å

< = = a m, b n. j D j j D j 1 1 ∣ ∣ ∣ ∣

A lattice line is a line containing at least two points in  .2 _{The line sum of f along the lattice}

line with equation ay=bx+t is deﬁned as



å

= + Î f u v, . av bu t, u v, ( ) ( )

The projection of f along the direction a b( , ) is the vector whose entries, in a preassigned order, are the line sums of f along all lattice lines with direction a b( , ) intersecting . Deﬁnition 1. A pixel Q is said to be  -geometrically unique (brieﬂy -unique, or even unique if no confusion arises) if

(a) Q belongs to a line, with direction in,intersecting the grid just in Q, or

(b) Q lies on a line, with direction in, whose further intersections with are uniquely determined pixels.

The above recursive deﬁnition suggests us how to construct the set of -unique pixels: we ﬁrst consider pixels falling in case (a) then we recursively extend the uniqueness region including the pixels lying on lines having more than one intersection with the grid.

Deﬁnition 2. The ROU of  is the set of pixels of  that are  -geometrically unique according to deﬁnition1.

In this paper we are mainly concerned with the determination of the shape of the ROU when  consists of two distinct valid lattice directions, say a b( , ) and c d( , ) where we set,

<

a c, 0,b d, >0. Basing on these choices, the ROU is constructed by filling the grid from its bottom-left corner, and, analogously, from its upper-right corner. Due to symmetry, it suffices to argue only on one of these two regions, say the bottom-left one. Note that our approach is without loss of generality, since, for different choices of the signs of a b c d, , , , the arguments are similar(the ROU just fills different corners of); in particular, if one of the entries is zero, then the corresponding (coordinate) direction gives no contribution to the determination of the ROU. Moreover, up to transposing the grid and/or changing the order in which directions are taken, we can always assume - >a b and-a-c.

(8)

2.1. Previous results

Denote by  =(w w1, 2,¼,wt-1,wt) a SE to NW zigzag path, with alternating horizontal

and vertical steps of lengthsw w1, 2,¼,wt-1,wt,being theﬁrst one (of length w1) a vertical step starting from the bottom-right corner of the ROU, and the last one (of length wt) a

horizontal step ending in the upper-left corner of the ROU (see ﬁgure1(a)).

In [8], the ROU has been already determined in some particular cases, that we detail

below.

- Ifb<d the ROU is always delimited by the zigzag path  =(b,-a d, ,-c)(see [8, theorem 2 and corollary 1]).

- Let l m, be the quotients of the division between -a,-cand b d, respectively, and let

r s, be the corresponding remainders.

- If b>d, and l¹m, then the ROU is the region delimited by the zigzag path  =(d,-c b, -d,- +a c d, ,-c)(see [8, theorem 3]);

- ifb >d, andl=m,0< < -r c 2,s>d 2, then the ROU is the region delimited

by the zigzag path  =(d-s,- -c r s r b, , , -d,-a+c d, -s,- -c r s r, , ) (see [8, theorem 4] );

- ifb>d,l=m,r> -c 2,0< <s d 2, then the ROU is the region delimited by the zigzag path  =(s r d, , -s,- -c r b, -d,- +a c s r d, , , -s,- -c r). (See [8, theorem 5]. )

The above results show that the ROU consists of displacement of rectangular areas, whose sizes depend on numerical relations among the entries of the employed directions. For instance, the two directions (−13, 7), (−8, 5) produce a ROU as in ﬁgure1(b). However, the cases

treated in[8] seemed to be sporadic examples of a more general picture, which bases on integer

division. Our purpose is to complete the characterization of the ROU under two directions. Being-a-c, in the caseb <d we always obtain the largest possible ROU, which consists of the region delimited by the zigzag path  =(b,-a d, ,-c)(see [8]). From now

on we assume thatbd; in this case, differently from before, we are not sure to gain the

largest obtainable area.

3. A few general results

Because of our assumptions, we look for the ROU which is determined in the bottom-left corner of theﬁxed grid . Denote by R0the - ´( a b)-sized rectangle placed in the bottom-left corner of the grid and byR R1, 1¢the two rectangles, of size - ´c d, placed, respectively,

adjacent to the bottom of the grid and to the right side of R0, and adjacent to the left side of the

Figure 1.(a) The lattice region delimited by the zigzag path  = 5, 3, 2, 8, 1, 2 .( ) (b) The ROU associated to the directions(−13, 7), (−8, 5).

(9)

grid and to the upper side of R0(see ﬁgure2(a); in what follows, we will not draw the whole grid, but just the conﬁguration in the bottom-left corner).

Theorem 3. The largest obtainable ROU is that delimited by the zigzag path  =(d,-c b d, - ,- +a c d, ,-c) i.e., it is the union, R0

È

R1

È

R .1¢

Proof. Consider a minimal bad configuration associated to the directions a b( , ) (, c d, ), namely, a parallelogram with sides parallel to the vectors a b( , ) and(c d, ).We place it such that its highest pixel lies on the left margin of the gridand its lowest pixel is placed on the lower side of . By construction, the pixels of such minimal bad configuration are adjacent to the rectanglesR0,R R1, 1¢(see figure2(b)). Our claim is that the pixels on the right and above

the bad conﬁguration are not in the ROU. This is evidently true since a bad conﬁguration including one of such pixels is completely contained in , so its pixels are not uniquely determined. This is equivalent to saying that the ROU is contained in the remaining area of,

i.e., in R0

È

R1

È

R .1¢ ,

Note that all pixels in 0≔R0

È

R1

È

R1¢are uniquely determined, since uniqueness of

reconstruction is equivalent to the absence of bad conﬁgurations. We say that all pixels in0

are algebraically unique, as their values are determined by solving the linear system(1).

As one can see from [8], the ROU is in general different from .0 This is due to the

existence of pixels which do not belong to the ROU even if they are not part of a bad conﬁguration contained in the grid .

Lemma 4. LetQÎ0.Then Q is not in the ROU if and only ifQ+z c d( , )Î ⧹ 0for

some zÎ and Q¢ + ¢z c d( , )Î ⧹ 0 for some z¢ Î, being Q¢ =Q+(a b, )

(orQ-(a b, )).

Proof. By the deﬁnition of uniquely determined pixel, Q is in the ROU if and only if it is the only unknown in at least one of the equations in the linear system associated to the tomographic problem. There are exactly two equations(namely, two lines) containing Q: one with direction

a b,

( ) and one with direction (c d, ). Since a line with direction a b( , ) has at most two intersections with₀, Q belongs to the ROU if and only ifQ¢(if it exists) does so. We then Figure 2.(a) The displacement of the rectanglesR0,R R1, 1¢for the directions(−6, 5), and(−4, 3). (b) The displacement of the minimal bad conﬁguration and the removed area(the colored one). (c) The pixelsQ Q, ¢are not in the ROU.

(10)

look at the other line through Q, with direction c d( , ) Q is in the ROU if and only if there are: no other unknowns on that line, namely no intersections with the grid outside the ROU. , As an example, if (a b, )= -( 6, 5) and (c d, )= -( 4, 3 ,) we can see that the pixel =

Q (9, 2) does not belong to the corresponding ROU. In fact, being

¢ = + =

Q (9, 2) (a b, ) (3, 7 ,) the translates of Q andQ¢by(c d, )(the pixels 5, 5 , 1, 8( ) ( ) and 7, 4 , 11, 1 ,( ) ( ) respectively) are outside0 (see ﬁgure2(c)).

Remark 5. The previous lemma can be generalized as follows. Suppose to know that the ROU is included in a subset  of .0 Then the ROU does not contain a pixelQÎif and

only if, for some zÎ,Q+z c d( , ) falls in  ,⧹ and the same holds also forQ .¢

3.1. Comparing algebraic and geometric uniqueness

The set of algebraically unique pixels equals  ,0 and their values can be computed by solving

the related set of equations. In particular, the values of the pixels in the ROU can be obtained in linear time. This follows from Deﬁnition1, and from Section 5.1. However, differently from the shape of the algebraic unique pixels, the shape of the ROU, usually, is far from being trivial. In the following example we show that the set of  -geometrically unique pixels differs from the set of algebraically unique pixels. In particular, it results that the ROU is properly included in0.

Example 6. Consider an (8 ´7)-sized grid and the directions (-4, 3 ,) (-3, 2 .) The corresponding ROU, computed as explained in section 4, is depicted in ﬁgure 3 (in

light gray). The dark gray pixels correspond to the difference between the set of algebraically unique pixels and the set of geometrically unique pixels. We write the equations involving the non-light gray pixels (the ﬁrst six equations refer to direction -4, 3 ,( ) while

Figure 3.The difference between the geometric ROU(light gray) and the algebraic

ROU(light and dark gray). Here the whole grid  is represented, so that the ROU is shown both in the bottom-left and in the upper-right corners.

(11)

the other ones to(-3, 2)): + = x2 x8 b ,1 ( )2 + = x6 x12 b ,2 ( )3 + = x4 x10 b ,3 + = x3 x9 b ,4 + = x1 x7 b ,5 + = x5 x11 b ,6 + + = x8 x12 k1 b ,7 ( )4 + + = x2 x6 x10 b ,8 ( )5 + = x4 x9 b ,9 + + = x3 x7 x11 b ,10 + + = x1 x5 k2 b ,11

where bis are the projection data and k k1, 2 are known. If we compute(2)+(3)−(4)−(5),

we obtain

= + - -

-x10 b7 b8 b1 b2 k ,1

meaning that x10is uniquely determined, and so are x x3, 4,x9.

3.2. Horizontal and vertical convexity of the ROU

Let  be the minimal bad conﬁguration as in the proof of theorem3. The coordinates of the four pixels B1, B2, B3, B4of  are(0,b+d), -c b( , ), -a d( , ), - -( a c, 0 ,) respectively. Letj,

Î

j {1, 2, 3, 4 ,} be the sets of pixels ofplaced in bottom-left region delimited by Bj, namely                 = + -= - -= - -= -y y b d x y x c y b c b x y x a y d a d x x a c 0, 0 1 , , 0 , 0 , , , 0 , 0 , , , 0 0 1 . 1 2 3 4

}

{( )∣ } {( )∣ ⧹{( ) {( )∣ ⧹{( ) {( )∣ }

Theorem 7. The rectanglesj, jÎ{1, 2, 3, 4 ,} belong to the ROU.

Proof. The pixels of 2

È

3are always mapped outside,when translated along a lattice

line parallel to a b( , ) or(c d, ) (possibly in more than one step, according to deﬁnition1).

Therefore 2

È

3is in the ROU. As concerns the pixels of ,1 these are closer to the bottom

side of the gridthan the pixel B1. Therefore, when moved on a lattice line along each one of the directions a b( , ) and c d( , ) they fall either outside,  or in2

È

3,already included in the ROU. Consequently, also1belongs to the ROU. Analogously, the pixels of4 are

closer to the left side of than B4, and consequently, as above, we can deduce that4is a

part of the ROU. ,

Corollary 8. The lowest row of the ROU has length- -a c and the leftmost column has heightb +d.

(12)

Proof. It sufﬁces to note that  = +1 b d and 4 = - -a c. ,

The above results suggest that the ROU is somehow convex. Actually, the ROU determined by a single direction a b( , ) is convex, since it is a - ´( a b)-sized rectangle: in fact, every line with direction a b( , ) containing a pixel of R0has no further intersection with the grid. However, for more than two directions a weaker notion of convexity is needed. Deﬁnition 9. A region of a grid is said to be horizontally(respectively, vertically) convex if the intersection of each row (respectively, column) of the grid with the region is a connected set.

In [8, theorem 6] the ROU determined by a generic set  of D2 directions, was shown inductively to be horizontally and vertically convex. For the readerʼs convenience, we give below a new proof which better clariﬁes our argument.

Theorem 10. The ROU determined by a set  of directions is horizontally and vertically convex.

Proof. We proceed by induction on the size of the ROU, following its recursive deﬁnition. As a preliminary fact, we note that, by corollary 8, a subset of the lowest row and of the leftmost column of  are always part of the ROU. This implies that the horizontal and vertical convexity is equivalent to saying that, given a pixel in the ROU, all pixels below it and on its left are part of the ROU.

Consider ﬁrst  = = ROU , j j 0 1 4 ⋃

which is horizontally and vertically convex. Then assume the thesis holds for ROU ,n such that

= + n

ROUn ROU0 ,and considerROUn+1=ROUn

È

Q.Since Q is in the ROU, all its

shifts along one of the employed directions are in ROU .n By the inductive argument, all pixels

below the shifts of Q belong to the ROU(as they are in ROUn), and so do also the pixels

below Q by a translation along the considered direction(the pixels below Q are the only ones not yet determined on each line).

This proves that the ROU is vertically convex. The proof of the horizontal convexity is

analogous. ,

4. Algorithmic construction of the ROU

In what follows, we wish to show how the ROU can be determined inside  ,0 and, in each

case, we characterize its shape. We apply a DEDA, obtained by employing the classical Euclidean division algorithm on the absolute values of the horizontal and, contemporarily, the vertical components(- -a, cand b d, , respectively) of the directions a b( , ) and(c d, ).This produces two lists of quotients and remainders:

(13)

- = - + = + - = + = + = + = +    a h c r b k d s c h r r d k s s r h r r s k s s horizontal vertical level 0: , , level 1: , , level 2: , , 0 0 0 0 1 0 1 1 0 1 0 2 1 2 0 2 1 2 ( )

where the two sequences can stop at different levels. In order to compact the notation, we set -a ≕r-2,b ≕s-2, -c≕r-1,d≕s .-1 So, at a generic level j0we have

= + = + - -- -r h r r s k s s , . j j j j j j j j 2 1 2 1

We also set lj≔min{h kj, j}.

4.1. The starting level

As aﬁrst step, we note that the rectangle R0, placed in the bottom-left corner of the grid, is always included in the ROU. In fact all its pixels fall outsideunder a translation of  a b( , ). We write jfor the ROU at step j and consider ﬁrst the set 0=R0

È

R1

È

R .1¢

Focus on the level 0 as above: if one of the remainders is zero, or the two quotients are not equal, we can argue as follows.

Case 1.1: Supposer0=0and note that each line with direction(c d, )through a pixel of the bottom strip of R1, of height s0, contains no lattice points outside R0 and contained in the grid. Consequently, this strip belongs to the ROU. We underline that the length of the strip is precisely -c, sincer0=0.Now, a same-sized strip in the bottom of R₁¢ is part of the ROU, by means of the direction(a b, ).By iterating the procedure for afinite number of times (since d is finite), we have that the whole rectanglesR R1, 1¢are part of the ROU(see figure4).

The same argument can be applied fors0=0.

Case 1.2: Ifr0,s0¹0andh0¹k ,0 then theorem 3 of[8] can be applied withl = h0and

m = k .0 Therefore, as above, we get that the ROU is the largest obtainable one,

i.e., it is0 (see [8, example 2]).

Therefore, in the above cases the sets of algebraic uniqueness and geometric uniqueness coincide.

4.2. Erosive procedure

If the two conditions as above are not fulﬁlled,0undergoes an erosion. Since inside0 a

line with direction a b( , ) has at most two intersections with the grid andR1+(a b, )= ¢R1,a pixel in R1is in the ROU if and only if its translate through a b( , ) inR1¢is, so, from now on,

we will focus just on R1 and provide a quick procedure to compute the resulting ROU. Moreover, theorems7and10imply that the erosion of the rectangles R1andR1¢concerns just

their upper-right part.

Inside the rectangle R1we can construct a stair-shaped region delimited by blocks having horizontal length r0and vertical length s0. This is what we obtain from level 1 of DEDA.

We have to distinguish two cases.

Case 2.1: The ﬁrst block is placed on the bottom-right corner of R1, and its upper-left corner is adjacent to the bottom-right corner of a same-sized block. This one is itself adjacent to another block in its upper-left corner, and so on in order to have

=

(14)

exceed the rectangle R1). A residual block of size ´r1 s1is added to connect the

blocks and the upper-left corner of R1.

Case 2.2: The same as in case 2.1, with the only difference that the ﬁrst block of size ´

r0 s0 is placed on the upper-left corner of R1 (see section 4.3 below for a detailed explanation about how to choose the correct case).

By theorem 10, erosion regards all pixels above and on the right of each such block, which are consequently removed from .0 Let 1be the resulting region.

By means of the same argument as in the above cases 1.1 and 1.2, we get that, if r1or s1 is 0, orh1¹k ,1 then there is no further erosion, and the ROU is  .1 Otherwise, we repeat the

procedure by replacing -c d, withr0,s0,andr0,s0 with r s1, 1respectively. As a result, we

remove from 1 the pixels above and on the right of the l2(r1´s1)-sized blocks and the

´

r2 s2

( )-sized block; we thus obtain 2 at step 2 of DEDA.

Remark 11. What we said for levels 0 and 1 indeed holds for every level of DEDA. Therefore, while the classical Euclidean algorithm stops when the remainder is zero, DEDA checks whether, at level i,

(a) at least one between riand siis zero, or (b) hi¹ki

to stop the algorithm.

In a sense, we have that the erodent block becomes the eroded one.

We then iterate the procedure until one of the two conditions of remark11is fulﬁlled; in this case the algorithm stops, say at step i. In this case, we say that the obtained ROU has erosive level i. To better understand what happens when the algorithm stops and which is the form of the last erosion, we refer to section4.4.

4.3. How to start the erosion

We want to point out that the choice of starting from above or from below in the erosion procedure at level i, i.e., placing the blocks of sizeri-1´si-1starting from the upper-left

Figure 4. Construction of the ROU for the directions

= - =

-a b, 14, 13 , c d, 7, 5 .

( ) ( ) ( ) ( ) (a) Only the lowest strip of R1, of height

=

s0 3,is added, since it is translated inside R0along the direction c d( , ).(b) By means

of a translation along a b( , ),a same strip ofR1¢is added to the ROU, and then also the remaining part of R1, by using again c d( , ).(c) By means of a translation along a b( , ),

(15)

corner or the bottom-right one of the rectangle(s) of size ri-2´si-2 (cases 2.2 and 2.1,

respectively), corresponds to keeping, after such an erosion, the largest possible area. In section6 we prove that this actually represents the ROU.

Note that the removed area consists of two parts: the triangular part, corresponding to the area above(or on the right of) the blocks of sizeri-1´si-1,and the residual part, i.e., the

pixels above(or on the right of) the remainder block of size ´ri si(see ﬁgure5). The name

‘triangular part’ derives from the fact that it consists of a triangular number of blocks of size ´

-

-ri 1 si 1;more precisely, this number is(li-1)li 2and it does not change when starting

from above or from below. The number of pixels belonging to the triangular part is then -- -l l r s 1 2 . i i i 1 i 1

(

)

As concerns the residual part, its size is r si(i-2-si) when starting from above and

-s ri(i 2 ri) when starting from below.

The following lemma holds.

Lemma 12. Starting from above(respectively, below) in the erosion of the blockri-2´si-2,

produces a smaller loss of pixels if and only if - <

-

-r si i 2 s ri i 2 0 ( )6

(respectively,r si i-2-s ri i-2>0).

Proof. From the previous observations, erosion starts from above if and only if

- <

--

-r si(i 2 si) s ri(i 2 r ,i) and (6) follows. Analogously, erosion is from below if and

only ifr si i-2-s ri i-2>0. ,

Remark 13. Equality in (6) is not allowed, since this would imply easily (by moving

backwards in DEDA), that-cand d are not coprime.

The following theorem ensures that there is no need of verifying at each step which is the start position that maximizes the ROU.

Theorem 14. At stepi+1,starting erosion from below(respectively, from above) produces the smallest loss of pixels if and only if the erosion at step i is minimized by starting from above (respectively, from below).

Figure 5.(a) Starting from above, and (b) starting from below. The triangular part has

(16)

Proof. Assume that erosion starts from above at stepi0;this means thatr si i-2 <s ri i-2.

So, by a simple calculation

- < ->  - > -> - < -  - < -< - - - -- - - -- - - -- -+ - + - - -- - + - - + - + - + r l r s s l s r r s s r l r s r s l s s r l r r s s r l r s l s r r s r s l s s r l r r s s r , , , , , , , i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 2 1 2 2 1 2 1 2 1 2 1 1 1 2 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

(

)

(

)

(

)

(

)

(

)

(

)

(

)

(

)

which means that erosion at step +i 1 starts from below. , Remark 15. The starting point is not calculated at level 0, since this step just gives information about the presence or absence of erosion.

We can summarize the previous considerations by saying that, if i is the erosive level, then, for jÎ{0, 1,¼,i-2 ,} the rectanglerj´sj is eroded byrj+1´sj+1,and the

pro-cedure alternates the starts from above and from the below. Moreover, the following result holds.

Corollary 16. The erosion procedure is completely determined by checking whetherr d1 +s c1 0.

Proof. By theorem14, the shape of the ROU is completely determined once we know the start of the erosion procedure at level one. By lemma12, sincer-1= -cands-1=d,this is

equivalent to check whetherr d1 +s c1 0. ,

In what follows, where not speciﬁed, the expression ‘erosion starts from above (below)’ refers to theﬁrst erosive level.

4.4. How to obtain the shape of the last eroded block

In this subsection, our purpose is to explain what happens at the last step(say i) of DEDA, namely, when the algorithm stops and the shape of the ROU is obtained. At this step the erosion does not consist of blocks of size ri-1´si-1 and ri´si, but of slightly different

blocks. In fact, the erosion procedure goes on, by alternating starts from above and below, as long as the remainder block is strictly included in the erodent block. When this condition is not satisﬁed, at least one of the sizes of the remainder block is greater than, or equal to, the size of the corresponding erodent block(see examples in section7). This reﬂects in updating

the last line of DEDA according to one of the conditions of remark 11. More precisely, we proceed as follows.

(a) If one of the remainders is zero, we lower by 1 the corresponding quotient, so that the remainder is updated with the divisor(namely, with the remainder of step -i 1). For

instance, in the case of the horizontal direction, we getri-2=(hi-1)ri-1+ri-1.For

(17)

-h h r r 1, . i i i i 1 ⟵ ⟵

(b) Once no remainder is zero (possibly without step (a)), we then check the quotients: as previously observed, different quotients imply that one of the sides of the erodent block exceeds the bounding rectangle before the same happens to the other one. So we take

=

li min{h ki, i} and rewrite

* * = + = + - -- -r l r r s l s s , ; i i i i i i i i 2 1 2 1

then the rectangle(s) of sizeri-2´si-2 are eroded by liblocks of sizeri-1´si-1,with

remainder block of sizeri*´s .i*

We underline that the minimum among the quotients is computed on the updated quo-tient(s), in the case that one of the remainders is zero (namely, if step (a) occurs). Moreover, note that the case * >ri ri-1and * >si si-1never occurs, since otherwise we could insert an

´

-

-ri 1 si 1

( )-sized block inside the remainder block. This means that, if * >ri ri-1 then

*

-si si 1,and, analogously, if * >si si-1then * ri ri-1.

We can give now a more detailed description of the stopping criteria of DEDA.

Lemma 17. If DEDA stops at level i, thenri*ri-1,or * si si-1.

Proof. We know that DEDA stops when one of the remainders among riand siis zero, or when the quotients hiand ki are different. Ifri=0,then * ri ri-1.Analogously, ifsi=0,

then * si si-1.Ifhi¹k ,i then we take both quotients equal toli=min{h ki, i} so that the,

remainder corresponding to the largest quotient is updated, and one of the inequalities is

satisﬁed. ,

Theorem 18. Let DEDA stop at level i. Then we have

(a)ri* >ri-1, or * =ri ri-1 and si* < si-1, if and only if every (ri-2´si-2)-sized block

formed by DEDA is eroded from below.

(b) * >si si-1, or si* =si-1 and ri* <ri-1, if and only if every (ri-2´si-2)-sized block

formed by DEDA is eroded from above.

Proof. Since DEDA stops at level i, ri-2´si-2 is the last eroded block. Assume that

* >

-ri ri 1; then, as observed before, we have * si si-1,since otherwise we could insert an

´

-

-ri 1 si 1

( )-sized block into the(r_i*´s_i*)-sized block. Therefore we get * - - * = * - < * * - *= - - * *

si

(

ri 2 ri

)

s l ri i i 1 s l ri i i si 1l ri i

(

si 2 si

)

r .i

Consequently, *r si i-2-s ri* i-2>0,and, by lemma12, this implies thatri-2´si-2is eroded

from below. Analogously, in case * =ri ri-1and * <si si-1,we have

* - - * = * - = * *< - *= - - * *

si

(

ri 2 ri

)

s l ri i i 1 s l ri i i si 1l ri i

(

si 2 si

)

r ,i

which still implies that erosion is from below. This proves the direct implication.

Conversely, suppose that every(ri-2´si-2)-sized block formed by DEDA is eroded

(18)

* - < - *

s ri i 1 si 1r .i

Ifri* >ri-1,the result follows. Otherwisesi-1ri*si-1ri-1,so that * <si si-1.By lemma17

this also implies that * =ri ri-1.This proves(a). The proof of (b) is analogous. ,

Note that the case * =ri ri-1and * =si si-1does not occur, as it would imply that-cand

d are not coprime.

4.5. Matching DEDA with previously obtained results

The determination of the ROU for two directions has already been treated in[8], where only

some particular cases are studied. Now we want to show how the previous results can be included in these new ones to obtain a uniﬁed picture. First, note that the case <b d must be treated separately, since step 0 of DEDA cannot be applied, being the quotient equal to zero. This case has been settled out in [8, corollary 1] and leads to an L-shaped ROU.

The caseb >d was differently explored.

(a) Theorem 3 of [8] states that, if the quotients l m, (h0and k0in the present paper) of the division between -a,-c and b d, respectively are not equal, then there is no erosion. This result ﬁts with DEDA, since forh0¹k0 the algorithm stops at step 0 and so the

whole rectangles R1andR1¢are added to the ROU.

(b) In the casel=mit is assumed that, for- =a l(-c)+r0andb=md+s0, r0and s0 are strictly positive numbers. Two different results were found in[8].

(b.1) Whenr0> -c 2ands0<d 2,at step 1 of the Euclidean algorithm we obtain

- = + = + c h r r d k s s , , 1 0 1 1 0 1

with h1=1 (since r0> -c 2), k12 (since s0<d 2). Being h1¹k ,1 the

algorithm stops and the pair of directions has erosive level 1. It means that the rectangle R1is eroded by one block of sizer0´s ,0 with remainder blockr1´s1*

(where s₁* = -d l s1 0=d -s0). Since -cs < -c <r d,

d

0 ₂ 0 we get

-cs0-r d0 <0. Consequently, -cd-r d0 < -cs ,1* hence r d1 +cs1*<0

and, by corollary 16, the erosion starts from above. The zigzag proﬁle of the ROU is then  =(s1*,r s1, 0,r0,- +a c b, -d s, 1*,r s1, 0,r0) in agreement, with the statement of theorem 4 of[8].

(b.2) The case r0< -c 2 and s0>d 2 is obtained analogously, with the only

difference that erosion starts frombelow.

5. A pseudo-code for DEDA

To sum up, DEDA produces the following computations:

* * - = - + = + - = + = + = + = + = + = + - - - -  a l c r b l d s c l r r d l s s r l r r s l s s i r l r r s L s s horizontal vertical level 0: , , level 1: , , level 2: , , level : i i i i , i i i i . 0 0 0 0 1 0 1 1 0 1 0 2 1 2 0 2 1 2 2 1 2 1 ( )

(19)

In terms of zigzag path, we recall that it consists of a series of vertical and horizontal segments delimiting the ROU, starting from its bottom-right zone and ending in the upper-left corner of the ROU. We use the notation s r_[ , _{] to mean that the block r}l _{×s is repeated l times.}

So, at step i the path is modiﬁed as follows:

- -- -- -⎪ ⎪ ⎧ ⎨ ⎩ s r s r s r s r s r

, , , , if starting from above,

, , , if starting from below. 7

i i i i i i l i i l i i 2 2 1 1 1 1 i i

(

)

(

)

( ) ⟼ [ [ ] [ ] ( )

Note that at step i only remainders with indices i and -i 1 appear in the path, as the previous ones are eroded.

In algorithm1, we denote byEithe set of pixels which are eroded at level i, i.e., during

the ith run of the repeat cycle starting at line 12.

5.1. On the computational complexity of DEDA

The computational cost of DEDA can be obtained by analyzing its steps as follows. - Line 1: the region₀ is created by updatingO(- ´a b) pixels of the grid; - lines 2–5: parameters’ initialization can be performed in constant time; - lines 6–8: the output of₀ requiresO(- ´a b) computational time; - lines 9–11: as lines 2–5;

(20)

- lines 12–20: the while part performs, at each cycle, a sequence of parameters’ updates requiring constant time each (also in the if part), and a final ROU update (line 20) that modifies, say erodes, part of the elements of the previously last computed ROU. A simple observation may convince us about the global complexity of these lines: at each step (except the first) at least one pixel is modified, and the number of pixels of the ROU that are modified during the whole while run is bounded by the dimension of the ROU itself, i.e., it is againO(- á b .)

- line 21: again it is performed inO(- ´a b .)

Therefore, theﬁnal computational complexity of DEDA isO(- ´a b .)

Aﬁnal comment about the complexity of the while part of the algorithm is needed. In particular, we want to show the behavior of the worst case of the Euclidean algorithm in order to give an upper bound to the repetition of the division steps: the result follows from the Lamé theorem, whose Knuthʼs version [18] is as follows.

Theorem 1. (Lamé 1845).4Forn1, let u and v be integers withu > >v 0 such that the Euclidean algorithm applied to u and v requires exactly n division steps and such that u is as small as possible satisfying these conditions. Thenu =Fn+2 and v=Fn+1, where Fk is a Fibonacci number.

Finally, the following result is of our interest.

Corollary 20. If 0 u v, N, the number of division steps required by the Euclidean algorithm applied to u and v is at most⎡⎢log_f( 5N)⎤⎥-2.

Remind that f = 1+ 5

2 is the golden ratio. It is remarkable that, if we drop the

requirement of displaying the ROU area, then the algorithm provides, in at most O(logb) iterations (assuming that the modulo function takes constant time), a compact form to represent the boundary of the ROU in terms of walks as (7), whose analogy with

Linden-mayerʼs D0L systems (see [22] for deﬁnitions and main properties) could be exploited.

6. Consistency of DEDA

From the proof of lemma4, we deduce that, in order to show that a pixel Q is in the ROU, we have to consider the line through Q with direction(c d, )and check whether Q is the only not-yet-determined pixel on that line. To do so, we have to check whether the shifts of Q along

c d,

( ) fall in the previously determined ROU or outside . If a shift of Q falls in a region which has not been proven to be in the ROU yet, we cannot argue on it. We can say that proving the consistency of DEDA is obtained by adding pixels to the ROU, starting from the rectangle R0, while DEDA itself acts by removing pixels from the maximal conﬁguration.

As a preliminary case, if DEDA stops at level zero (namely, there is no erosion), consistency has been proven in section4. In the remaining cases, consistency is proven in two steps:ﬁrst, we show that a pixel which is preserved by DEDA actually belongs to the ROU; then, we show that a pixel which is eroded by DEDA is not in the ROU.

4 _{Knuth reported that}_{‘this theorem has the historical claim of being the ﬁrst practical application of the Fibonacci} sequence; since then, many others applications of the Fibonacci numbers to algorithms and to the study of algorithms have been discovered’.

(21)

From now on, we sort blocks of sizeri´si, inside a block of sizeri-1´si-1,from above

to below if erosion at leveli +1 starts from above, and conversely if erosion starts from below.

6.1. DEDA preserves uniquely determined pixels

We divide the set of preserved pixels into two subsets: the pixels below and on the left of the blocks; and the pixels inside the blocks. For the ﬁrst subset, we split the proof between the ﬁrst erosive level and the other ones.

Theorem 21. If erosion starts from above (respectively, below), then every pixel below (respectively, on the left of) the(r0´s0)-sized blocks of R1and R1¢is in the ROU.

Proof. Assume that erosion starts from above and consider the upper rightmost pixel Q below the ﬁrst (r0´s0)-sized block of R1¢ (see ﬁgure 6(a)); its coordinates are

- + -

-r0 1,b d s0 1 .

( ) We move it of -z c d( , ), zÎ. For1  z l0, QÎR .0 Its

further translation of- c d( , )is



- + = - - - - Ï

Q

(

l0 1

)

(c d, ) ( a c 1, 1) ,

so Q is the only not-yet-determined pixel on the line with direction(c d, )containing it, then it is part of the ROU. By horizontal and vertical convexity, also all pixels on the left and below Q are in the ROU, and so do their translates along a b( , ) which are the pixels below the, ﬁrst

´

r0 s0

( )-sized block of R1.

Consider now the upper rightmost pixel S below the second(r0´s0)-sized block ofR ;1¢

its coordinates are (2r0-1,b +d -2s0 -1) (see ﬁgure 6(a)). For 1  z l0-1,

-S z c d( , ) belongs to R0. A further translation of- c d( , )gives

= - = - + - -

-S˜ S l c d0( , )

(

a r0 1,d s0 1 ,

)

meaning that S˜ is the upper rightmost pixel on the left of theﬁrst(r0´s0)-sized block of R1, which is in the ROU by the previous argument. Therefore S is uniquely determined and then in the ROU, and so do all the pixels on its left and below it.

Figure 6.(a) The position of pixels Q and S in ¢R .1 (b) The shifts of the(r0´s0)-sized blocks ofR .1¢

(22)

By recursion, we prove that all pixels below the(r0´s0)-sized blocks are in the ROU. If

erosion starts from below, the proof is similar. ,

In the proof of theorem21, the strategy to prove our results is explained: once the upper rightmost pixel Q below theﬁrst(r0´s0)-sized block ofR1¢is shown to be in the ROU, so

do, by theorem10, the pixels on its left and below it, and also the other pixels with the same position as Q with respect to the other(r0´s0)-sized blocks. The pixel Q is the only one, in

the set of upper rightmost pixels, falling in the previously determined ROU, while the other ones are moved to another upper rightmost pixel of R1, so initially we cannot argue on them. If erosion starts from below, Q is placed on the left of theﬁrst(r0´s0)-sized block of R1, ordered from below.

We now want to extend this argument to all erosive levels; to do so, we need the following deﬁnition.

Deﬁnition 22. If erosion starts from above (respectively, from below), a pivot at erosive level i is a pixel Q ofR₁¢(respectively, R1), such that:

- if erosion at level i is from above, Q is the upper rightmost pixel below an ´

-

-ri 1 si 1

( )-sized block, inside an(ri-2´si-2)-sized block;

- if erosion at level i is from below, Q is the upper rightmost pixel on the left of an ´

-

-ri 1 si 1

( )-sized block, inside an(ri-2´si-2)-sized block.

Lemma 23. Assume erosion starts from above. By translations along the direction c d( , ), pivots ofR₁¢are moved to pivots of R1.

Proof. By a translation of -l c d0( , ) the, λth(r0´s0)-sized block ofR1¢, l =2,¼ l, ,1 is

moved into the(l - 1 th) (r0´s0)-sized block of R1, so the structure of the pivots inside them does not change.

Theﬁrst(r0´s0)-sized block ofR ,1¢ say ,0 when moved of -(l0+1)(c d, ) is shifted,

in the lower-right corner of R1(see ﬁgure6(b)). Then, the residual(r1´s1)-sized block of R1 (at erosive level 1) plays the role of the ﬁrst (from below)(r1´s1)-sized block in the shift of

0 (at level 2). This means that the pivot (at level 2) on the left of the ﬁrst (from below)

´

r1 s1

( )-sized block inside 0is shifted to the lowest pivot of R1(at level 1). Moreover, the pivot(at level 2) on the left of the λth(r1´s1)-sized block inside 0, l =2,¼ l, 2,is moved

to the pivot (at level 2) on the left of the l - 1 th( ) (r1´s1)-sized block inside the l1th ´

r0 s0

( )-sized block of R1.

The residual(at level 1)(r1´s1)-sized block ofR1¢is translated to the upper-right corner

of the l1th(r0´s0)-sized block of R1 (see ﬁgure 6(b)). By theorem 14, the translation preserves the structure of the internal erosion, so the pivot (at level 3) below the ﬁrst (from above)(r2´s2)-sized block of the residual(r1´s1)-sized block ofR1¢is translated to a pivot

of the previous erosive level, while the other pivots fall in other pivots.

As concerns successive erosive levels, the thesis follows from theorem 14. , If erosion starts from below, we have to argue on the pivots of R1; the proof is similar. As a consequence of the previous lemma, by alternating shifts of  a b( , ) and l c d0( , ) (or (l0+1)(c d, )) all pivots are reached.

(23)

Deﬁnition 24. The ith leading pivot Qi is the pixel, among all pivots at erosive level i, such that:

• if erosion starts from above:

– for i even (namely, erosion at level i starts from below), it is the pivot on the left of the ﬁrst(ri-1´si-1)-sized block, inside the leftmost(ri-2´si-2)-sized block ofR :1¢

= - - - - + - - + -

-Qi

(

ri 2 ri 1 1,b d si 2 si 1 1 ;

)

– for i odd (namely, erosion at level i starts from above), it is the pivot above the ﬁrst ´

-

-ri 1 si 1

( )-sized block, inside the rightmost(ri-2´si-2)-sized block of R :1¢

= - - - + - - + - - -

-Qi

(

c ri 2 ri 1 1,b si 2 si 1 1 ;

)

• if erosion starts from below:

– for i even (namely, erosion at level i starts from above), it is the pivot below the ﬁrst (from above)(ri-1´si-1)-sized block, inside the rightmost(ri-2´si-2)-sized block

of R1):

= - - - - + - - -

-Qi

(

a c ri 2 ri 1 1,si 2 si 1 1 ;

)

– for i odd (namely, erosion at level i starts from below), it is the pivot on the left of the ﬁrst (from below) (ri-1´si-1)-sized block, inside the leftmost (ri-2´si-2)-sized

block of R1):

= - + - - - + -

-Qi

(

a ri 2 ri 1 1,d si 2 si 1 1 .

)

We can say that the leading pivot follows a rule similar to the one exposed in theorem14. In the following result, we show that leading pivots are the pivots which are moved to pivots of the previous erosive level.

Theorem 25. If DEDA stops at level I, then all pixels on the left and below the ´

-

-ri 1 si 1

( )-sized blocks of R1andR1¢,i=1,¼, , are in the ROU.I

Proof. Assume that erosion starts from above. Denote by Qi the leading pivot of R1¢ at

erosive level i. We prove by induction on i 1 that Qiis  -geometrically unique. For i=1, the result has been proven by theorem21.

Assume now that the thesis holds at a leveli1;we want to show that the area below the conﬁguration at level +i 1 is in the ROU. Assume that i is odd; the coordinates of the leading pivot at level +i 1 are

= - - + - +

-+ -

-Qi 1

(

ri 1 ri 1,b d si 1 si 1 .

)

Being i+1 even, erosion at level i+1 starts from below and Qi+1 is in the leftmost

´

-

-ri 1 si 1

( )-sized block, so its shifts of -z c d( , ), zÎ{1,¼,l0} remain inside R, 0. A further shift gives

(24)

- + = - - - + - - - +

-+ -

-Qi 1

(

l0 1

)

(c d, )

(

a c r0 ri 1 ri 1,s0 si 1 si 1 .

)

As concerns the ﬁrst component, we can rewrite the terms-cand-r0as follows:

å

- = + = + + = ¼ = + = -+ c l r r l r l r r l r r j i j j i 1 0 1 1 0 3 2 3 0 1 2 2 1 2 and

å

- = - - = - - - = ¼ = - -= -- -r l r r l r l r r l r r . j i j j i 0 2 1 2 2 1 4 3 4 1 1 2 2 2 1 1

Then the ﬁrst component ofQi+1-(l0+1)(c d, ) is then - +a l r1 0-l r2 1+ ¼ +l ri i-1-li-1ri-2-1. An analogous argument on the second coordinate gives us

- + + ¼ - - + - -

-d l s1 0 l s2 1 l si i 1 li 1si 2 1,

meaning thatQi+1-(l0+1)(c d, ) is placed in the l1th(r0´s0)-sized block of R1, in its l2th ´

r1 s1

( )-sized block, in its l3th(r2´s2)-sized block, K, in the upper rightmost position

under its lith(ri-1´si-1)-sized block, namely, by the induction, in the ROU which was

determined at the previous step. So, as in the proof of theorem21, all pixels below and on the left ofQi+1are in the ROU, and so do all other pivots of leveli +1,by lemma23, and the

pixels below them and on their left. This means that all pixels below the conﬁguration at level +

i 1 belong to the ROU.

If i is even, the proof is similar (up to moving Qi+1 of -l c d0( , ) instead of

-(l0+1)(c d, )). If erosion starts from below, the proof is similar. , Theorem 26. If DEDA stops at level i, then the pixels inside the(ri-1´si-1)-sized blocks

and the residual(ri*´si*)-sized block are part of the ROU.

Proof. Assumeﬁrst that erosion starts from above and stops at level one. By theorem 18, there are three possible situations: when * >s1 s0and * =r1 r ;0 when * >s1 s0and * <r1 r ;0 and

when * =s1 s0 and * <r1 r .0

In theﬁrst case, let Q be the lower rightmost pixel inside the residual *(r1 ´s1*)-sized

block of R1, namely Q= - - -( a c 1, 0 .) By theorem 7, the lowest row of the conﬁguration is known to belong to the ROU, as well as the leftmost column. The line through Q with direction(c d, )intersects the grid in R0and in

+ + = - +

-Q

(

l0 1

)

(c d, )

(

r0 1,b d s0

)

,

which is the lower rightmost pixel in the ﬁrst(r0´s0)-sized block of R ,1¢ and therefore is

added to the ROU, as well as all pixels in the lowest strip of such block, by horizontal convexity. Then, by alternating shifts of - a b( , ) and +l c d0( , ) all the lowest strips of the, blocks of size r0´s0 and r1*´s1*are added to the ROU. The last added strip is the one

inside the l1th (r0´s0)-sized block of R1, whose rightmost pixelʼs coordinates are *

- +a l r1 0-1,s1 .

(25)

* * * * * = - + - + = + - - + = + - - + = - - - + Q a l r s l c d l r b s s l r r b s s c b s s 1, , 1 1, 1, 1, , 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1

(

)

(

)

(

)

(

)

(

)

˜ ₍ ₎

which is the rightmost pixel of a certain strip of the residual(r₁*´s₁*)-sized block ofR1¢(not

the lowest one, since * >s₁ s0). This means thatQ˜is part of the ROU, as well as the pixels on

its left and below it. Also, so do their shifts by - a b( , ) in R1. By going on adding strips, we ﬁll all blocks.

If * >s₁ s0and * <r1 r ,0 the previous argument works similarly; the only change consists

in the fact that, being * <r1 r ,0 the lowest strip of the l1th sized block of R1is not completely included in the residual block ofR ,1¢ when moved of l c d0( , ) In this case, we consider just the.

part of the strip falling in the(r₁*´s₁*)-sized block and discard the remaining part(we will prove in the next subsection that the discarded pixels are not in the ROU).

For * =s1 s0and * <r1 r ,0 we argue as before, but by adding vertical strips.

If erosion starts from below, the proof is similar.

If erosion does not stop at level one, our argument starts again from the lower rightmost pixel of R1. The thesis follows from the proof of theorem25, since the lower rightmost pixel of each block of size ri-1´si-1 or *ri ´si* is obtained from a pivot by a translation

of + 0, 1 .( ) ,

6.2. Pixels deleted by DEDA are not uniquely determined

We now prove that pixels which are eroded by DEDA are not part of the ROU.

Theorem 27. Assume that DEDA stops at level one. Then all pixels which are removed by DEDA are not in the ROU.

Proof. Assume that erosion starts from above and consider the pixels inR ,1¢ on the right of

theﬁrst(r0´s0)-sized block. Let Q1be the lower leftmost of such pixels; its coordinates are

+

-r0,b d s0 .

( ) We shift it l0times in direction(c d, ): 

- = - Ï

Q1 l c d0( , ) ( a d, ) 0,

so Q1is not the only unknown on that line. To show that Q1is not uniquely determined, we have to prove that alsoQ2=Q1-(a b, ) is not uniquely determined.

When moved of l c d0( , ), Q2is sent to the lower leftmost pixel on the right of the second ´

r0 s0

( )-sized block ofR1¢, say Q3. This means that

Ï Ï Ï

Q1 ROU⟺Q2 ROU⟺Q3 ROU.

SetQ4=Q3-(a b, ) when translated of; l c d0( , ),it falls in the lower leftmost pixel on the

right of the third(r0´s0)-sized block ofR .1¢ By iterating the argument, we obtain that

Ï Ï ¼ Ï

Q1 ROU⟺Q2 ROU⟺ ⟺Q2l1 ROU, ( )8

where Q2l1= - +( a l r1 0,d-l s1 0) is the lower leftmost pixel on the right of the l1th

´

r0 s0