General neighborhood sequences in Zn

General neighborhood sequences in Zn Andr´as Hajdu a,1Lajos Hajdu b,2Robert Tijdeman c,3 aFaculty of Informatics, University of Debrecen, H-4010 Debrecen, P.O.Box 12. bNumber Theory Research Group of the Hungarian Academy of Sciences, and Institute of Mathematics, University of Debrecen, H-4010 Debrecen, P.O.Box 12. cMathematical Institute, Leiden University, NL-2300 RA Leiden, Postbus 9512. Abstract Neighborhoods and neighborhood sequences play important roles in several branches of pattern analysis. In earlier papers in Znonly certain special (e.g. periodic or octagonal) sequences were investigated. In this paper we study neighborhood sequences which are either ultimately periodic or allow at every neighborhood to do nothing at no cost. We give finite procedures and descriptive theoretical criteria for certain important (e.g. metrical) properties of the sequences. Our results are valid for several types of classical neighborhood sequences and for generated distance functions (e.g. octagonal and chamfer distances) which are widely applied in digital image processing. We conclude the paper by showing how our results contribute to the theory of distance transformations. Key words: Combinatorial algorithms, Path and circuit problems, Geometric algorithms, languages and systems, Image processing and computer vision PACS: 68U10, 41A50 1 Introduction In [30] Yamashita and Ibaraki introduced the concept of general periodic neighborhood sequences in Zn. They investigated when such sequences gen1Research supported in part by the OTKA grant F043090, and by the IKTA4 grant 6/2001. 2Research supported in part by the Netherlands Organization for Scientific Research (NWO), the J´anos Bolyai Research Fellowship of the Hungarian Academy of Sciences and by the OTKA grants T042985, F034981, F043090, and T048791. 3Research supported in part by the Netherlands Organization for Scientific Research (NWO). erate metrics, and the relation of these metrics and the Euclidean one. Their main results are the exhibition of certain procedures, which decide about the metricity and related properties. Das et al. [6] specialized this theory to the so-called octagonal sequences, based on the traditional neighboring relations of digital image processing. For various results in this direction we refer to [1,3,5,7–10,23,27], and the references given there. Recently, Fazekas et al. [12] dropped the periodicity requirement from the model of [6] by introducing general (not necessarily periodic) octagonal neighborhood sequences. This extension is important not only from a theoretical but also from a practical point of view, since e.g. the Euclidean metric can be approximated more precisely by general octagonal neighborhood sequences than by periodic ones, see [18]. Further results about general octagonal neighborhood sequences can be found e.g. in [16,17,24–26]. The purpose of this paper is twofold. On the one hand, we extend the theory of general (not necessarily octagonal) neighborhood sequences from the periodic case (investigated in [30]) to the case of neighborhood sequences which are defined over an arbitrary finite alphabet, and are either ultimately periodic or allow at every neighborhood to do nothing at no cost. The set of ultimately periodic neighborhood sequences has the advantage to be rather large, although such a sequence is determined by only finitely many data. We give procedures and provide theorems for certain important criteria (e.g. metricity). These theoretical results give a good insight into the behavior of such sequences. We have not computed the complexity of our procedures, it is left as an open issue (see Section 9). The structure of the paper is as follows. In Section 2 we give the basic notation and definitions. Some preliminary results are presented in Section 3. In Section 4 we show how certain sequences can be simplified keeping their metrical properties. We characterize the neighborhood sequences for which Zn is connected in Section 5. In Section 6 the metrical behaviour of neighborhood sequences is investigated. Section 7 contains our results on approximating the Euclidean metric with distance functions based on neighborhood sequences. In Section 8 we show how our model can be used e.g. in the theory of distance transformations. Finally, we discuss on current relating research results, and conclude in Section 9. 2 Basic concepts and notation Let R,Q,Z,Ndenote the sets of real numbers, rational numbers, integers and positive integers, and write R≥0,Q≥0,Z≥0for the subsets consisting of the non-negative elements of these sets, respectively. We fix a positive integer 2 nfor the whole paper, and write Ofor the origin of Rn. Let H={hi∈Zni= 1,...,m}and X⊆R. Then the cone generated by H over Xis defined as H<(X) = (m X i=1 λihiλi∈X, i = 1,...,m). A neighborhood is a pair (P, w), where the point set P⊆Znis finite, and w:P→R≥0is a so-called weight function on P. For p∈P,w(p) is the weight of pwith respect to w. The neighborhood (P, w) is called symmetric, if for any p∈P,−p∈Pand w(p) = w(−p). Let Λ be a finite set of neighborhoods. An n-dimensional (shortly nD) neighborhood sequence is defined as a sequence N= (Ni)∞ i=1 over Λ, that is, Ni∈Λ for all i∈N. We call Λ the alphabet used for N. Let Sndenote the set of all nD-neighborhood sequences. If for some j∈N,Ni=Ni+jfor all i∈N, then Nis called periodic with period j. In this case we use the brief notation N=N1N2. . . Nj. If j= 1 then Nis called a constant neighborhood sequence. Let N(k)denote the neighborhood sequence obtained by omitting the first k elements of N∈Sn. The sequence N= (Ni)∞ i=1 is called ultimately periodic, if N(k)is periodic for some k∈N. If N(k)has period length l−k, then we write N=N1N2. . . NkNk+1 . . . Nl. For technical reasons it is useful to avoid the degenerate case k= 0. Thus throughout the paper we assume that the periodic sequence N=N1N2. . . Nlis given by N=N1N2. . . NlN1N2. . . Nl. We use the following notation for some special subsets of the set of nDneighborhood sequences Sn: Sp n={N∈SnNis periodic}, Su n={N∈SnNis ultimately periodic}, SO n={N= (Ni)∞ i=1 ∈Sn|Ni= (Pi, wi),O∈Pi, wi(O) = 0 for all i∈N}. The set SO nwill play a special and important role throughout the paper. Moreover, it is clear that Sp n(Su n. We can measure distance by the help of neighborhood sequences in a natural way (see e.g. [6,12,30]). Let qand rbe two points in Zn, and N= (Ni)∞ i=1 ∈Sn, with Ni= (Pi, wi). The point sequence s= [q0, q1,...,qm], where q=q0, r=qm, and qi−qi−1∈Pi, is called an N-path between qand r. Define the relation ∼on the set A:= {(q1−q0,1),...,(qm−qm−1, m)}as (qi−qi−1, i)∼ (qj−qj−1, j) if and only if qi−qi−1=qj−qj−1and wi(qi−qi−1) = wj(qj−qj−1). Obviously, ∼is an equivalence relation on A. Consider the partition A=t S i=1 Ai induced by ∼on Awith the appropriate t∈N. Then, as a shorthand, we write 3 s=r−q=t P i=1 λixi, where xiis the common first entry of the pairs in Ai, and λi=|Ai|denotes the cardinality of Ai(i= 1,...,t). The length of sis defined as ℓ(s;N) = m P i=1 wi(qi−qi−1) = t P i=1 λiw(i)(xi), where w(i)denotes the common weight of the first entries of the pairs in Ai. If Nis fixed, then we shortly write ℓ(s;N) = ℓ(s). The N-distance W(q, r;N) between qand ris defined as the length of a shortest N-path between them, if such a path exists. Put W(q, q;N) = 0 for q∈Zn(empty path). If there is no path between qand r, we set W(q, r;N) = ∞. We write W(N) for the distance function itself defined by Non Zn, and also use the brief notation W(q, r), if Nis fixed. Moreover, we put W(q;N) = W(q) = W(O, q). If for all q, r, s ∈Znwe have W(q, r;N)<∞(Wis finite) W(q, r;N)≥0, W(q, r;N) = 0 iff q=r(Wis positive definite) W(q, r;N) = W(r, q;N) (Wis symmetric) W(q, r;N) + W(r, s;N)≥W(q, s;N) (Wsatisfies triangle inequality) then we call W(N) a metric, and use the notation d(q, r;N) = W(q, r;N), or shortly d(q, r) = W(q, r) and d(N) = W(N). Moreover, we write d(q;N) = d(q) for d(O, q). For x∈Rn, let ||x||1:= n P i=1 |xi|and ||x||2:= sn P i=1 x2 idenote the diamond norm and Euclidean norm, respectively. We say that Znis N-connected, if for any two points of Znthere exists an N-path between them. If Nis fixed, we will shortly say that Znis connected. Note that Znis N-connected if and only if W(q) is finite for all q∈Zn. A set T⊆Znis said to allow a finite covering of Zn, if Zncan be covered by the union of finitely many translates of T. By a lattice we mean a subgroup of Zn. A lattice is called full if it has rank n. We introduce a partial ordering relation on Sn, which will be important in our investigations. We note that for certain special neighborhood sequences such a relation was used by Das et al. [6], Fazekas [11] and by Fazekas et al. [12]. Let N, N′∈Sn. We define the relation ⊒∗on Snby N⊒∗N′if and only if W(q, r;N)≤W(q, r;N′) for all q, r ∈Zn, and we can also say that Nis faster than N′. 4 3 Preliminary results From the following proposition we can see that the neighborhood model is suitable for measuring distances, since it assures the existence of a shortest path, if Znis connected. Proposition 1 Let N= (Ni)∞ i=1 ∈Snwith Ni= (Pi, wi). Then for all q, r ∈ Zn,W(q, r;N)exists. PROOF. If there is no path between qand rthen by definition W(q, r;N) = ∞. Otherwise, let sbe an arbitrary but fixed path from qto rof length ℓ(s), having the short form s=t P i=1 λixi. Suppose that s′=t′ P j=1 λ′ jx′ jis a path from qto rof length ℓ(s′) such that ℓ(s′)< ℓ(s). Then for any j∈ {1,...,t′}, for the coefficients λ′ jof those x′ jin s′for which w(j)(x′ j)>0, we have λ′ j≤ ℓ(s)/w(j)(x′ j). Thus, as there are only finitely many neighborhoods, and every neighborhood contains only finitely many points, there are only finitely many possibilities for the lengths of such paths s′from qto r. Hence the statement follows. 2 The following examples explain why the restrictions |Pi|<∞for all i∈N, and |Λ|<∞are necessary to have Proposition 1. In our first example we show why we avoid infinite neighborhoods. Example 2 Let N=N1∈Sp 1be a constant neighborhood sequence, with N1= (Z, w1). For every i∈Z, let w1(i) = |1/i|if i6= 0, and let w1(0) = 0. In this case W(0,1; N)does not exist, since there is no shortest path between 0 and 1. For example, the length of the path 0,−i, 1is 1 i+1 i+1 for every i∈N. Our next example shows why it would be inappropriate to define neighborhood sequences over an infinite alphabet. Example 3 Let N= (Ni)∞ i=1 ∈S1, with Ni= (Pi, wi), where Pi={±i, 0}, wi(±i) = |1/i|and wi(0) = 0 for every i∈N. Now the alphabet of neighborhoods Λis not finite, and similarly to the previous example, W(0,1; N)does not exist, because there is no shortest path between 0and 1. 4 Equivalent neighborhood sequences In this section we investigate under what circumstances the structure of a neighborhood sequence can be simplified without affecting its distance mea5 surement. Remark 4 Note that our model allows positive weight for keeping place during the movement. Using sequences from SO nmakes it possible to keep place and avoid involuntary movements to undesired places. In particular, we have the following statement: Proposition 5 For any N∈SO nthere exists an M∈Su nof the form M= M1. . . MkMk+1, such that the functions W(N)and W(M)are identical on Zn. PROOF. The neighborhood Mk+1 = (P′ k+1, w′ k+1) can be defined as follows. Let I={i|Ni= (Pi, wi) occurs infinitely often in N}. Put P′ k+1 =S i∈I Pi, w′ k+1(p) = min i∈I{wi(p)|p∈Pi}for each p∈P′ k+1. Let the sequence of neighborhoods M1,...,Mkbe the subsequence of Nconsisting of the elements of N which occur only finitely many times and write M=M1. . . MkMk+1. Clearly, by these choices we have W(N) = W(M). 2 Yamashita and Ibaraki [30] showed that if N∈Sp nand W(N) is a metric, then there exists a constant neighborhood sequence M∈Sp nsuch that d(N) is identical with d(M). The following example shows that this result cannot be extended in this form to the ultimately periodic case. Example 6 Let n= 1,N1= (P1, w1),N2= (P2, w2), with P1={0}, P2={±1},w1(0) = 1,w2(±1) = 1, and consider N=N1N2. It is obvious, that W(N)is a metric, since W(0; N) = 0 (as always, by definition) and W(x;N) = |x|+ 1 for any x∈Z\ {0}. However, it can be easily seen that N cannot be replaced by a constant neighborhood sequence. It turns out that a variant of the above result is still valid for ultimately periodic sequences. Proposition 7 Let N=N1. . . NkNk+1 . . . Nl∈Su nwith Ni= (Pi, wi)for i∈ {1,...,l}. Then there exists an M∈Su nof the form M=M1. . . MkMk+1 such that W(N)and W(M)are identical on Zn. PROOF. Let P= l−1 [ t=k(t X i=k bibi∈Pi, i =k,...,t),and 6 P′=   l X i=k+1 bibi∈Pi, i =k+ 1,...,l   . Consider the neighborhood T= (P, wP), where for every x∈P wP(x) = min (t X i=k wi(bi)x= t X i=k bi, t =k,...,l−1, bi∈Pi, i =k, . . . t), and T′= (P′, wP′), where for every x∈P′ wP′(x) = min    l X i=k+1 wi(bi)x= l X i=k+1 bi, bi∈Pi, i =k+ 1,...,l   . The neighborhood sequence M=N1. . . Nk−1TT′obviously has the desired property, and the proof of the proposition is complete. 2 From Example 6 we see that it is not true that for every neighborhood sequence we can find a constant one such that they induce the same metric. Now we show that, on the contrary, the elements of SO nhave this property. Theorem 8 Suppose that N∈SO ninduces a metric on Zn. Then there is a constant neighborhood sequence which induces the same metric on Zn. PROOF. By Proposition 5 we may assume that N=N1. . . NkNk+1 with Ni= (Pi, wi) for i∈ {1,...,k+ 1}. Let dbe the metric induced by Non Zn, and let P=k+1 S i=1 Pi. Moreover, for every x∈Pset wP(x) = min {wi(x)x∈Pi, i = 1,...,k+ 1}, and put T= (P, wP) and M=T. We claim that d=W(M). By the definition of Mit is clear that Znis M-connected, and that for every x∈Znwe have d(x)≥W(x;M). Take an arbitrary x∈Zn, and choose a shortest M-path [O=q0, q1,...,qt=x] from Oto x. Then using that wP(y)≥d(y) for every y∈Pand that dsatisfies the triangle inequality, we have W(x;M) = t X i=1 wP(qi−qi−1)≥ t X i=1 d(qi−qi−1)≥d(x). Hence W(M) = don Zn.2 It is clear that if in Theorem 8 the neighborhoods in Nare given, then the constant neighborhood sequence can be constructed by a simple procedure. 7 Proposition 9 Suppose that N= (Ni)∞ i=1 ∈SO ninduces a metric don Zn, and wi(x) = 1 for each x∈Pi\ {O}, for all i∈N. Then dis completely determined by the set {xd(x) = 1}. PROOF. Clearly, d(x) = 0 if and only if x=O, and d(x) = 1 if and only if x∈P:= ∞ S i=1 Pi\ {O}. Since wP≡1 and dis completely determined by (P, wP), the statement follows. 2 5 Connectedness of Zn In this section we characterize the ultimately periodic neighborhood sequences for which Znis connected. For this purpose we need the following lemma. Lemma 10 Let H={hi∈Zni= 1,...,m}. Then H<(Z≥0)allows a finite covering of Znif and only if it is a full lattice. PROOF. Clearly, if H<(Z≥0) is a full lattice, then it allows a finite covering of Zn. To prove the other direction, assume that H<(Z≥0) allows a finite covering of Zn. We note that it is well-known that the set of integral points in the cone H<(Q≥0) have a (so-called Hilbert’s) basis; see e.g. [15]. As H<(Q≥0) is a rational cone, either it is contained in a (rational) halfspace of Qn, or H<(Q≥0) = Qnholds. Since H<(Z≥0) allows a finite covering of Zn, the former case can be excluded. In the latter case, let l∈ {1,...,m}be arbitrary. Then there are non-negative integers ri, siwith si6= 0 (i= 1,...,m), such that −hl=m P i=1 ri sihi. Hence −hl=   (rl+sl) m Y j=1 j6=l sj−1   hl+ m X i=1 i6=l    ri m Y j=1 j6=i sj   hi, implying −hl∈H<(Z≥0). Hence H<(Z≥0) is a lattice. The fact that this lattice is full follows from H<(Q≥0) = Qn, and the proof is complete. 2 Theorem 11 Let N=N1. . . NkNk+1 . . . Nl∈Su nwith Ni= (Pi, wi)for i∈ {1,...,l}, and put Qf= l−1 [ t=k(t X i=1 bibi∈Pi, i = 1,...,t), 8 Q∞=   l X i=k+1 bibi∈Pi, i =k+ 1,...,l   . Then Znis N-connected if and only if Q< ∞(Z≥0)is a full lattice in Rnand Qf represents all the cosets of the lattice Q< ∞(Z≥0)in Zn. Moreover, the connectedness of Zncan be checked by a finite procedure. PROOF. The sufficiency of the condition is clear. To prove the necessity, assume that Znis N-connected. Observe that then Q< ∞(Z≥0) allows a finite covering of Zn. By Lemma 10 this is equivalent to saying that Q< ∞(Z≥0) is a full lattice. Moreover, for the connectedness of Zn, we also need that all the cosets in Znof the lattice Q< ∞(Z≥0) are represented by Qf. Clearly, it is a finite procedure to check whether Q< ∞(Z≥0) is a full lattice or not. Actually, it is sufficient to check whether Q∞contains nlinearly independent vectors over Q, and that −h∈Q< ∞(Z≥0) for every h∈Q∞. The former problem is easy. The latter one leads to an integer programming problem of the form Ax =b, x ≥0 in x∈Zm,(1) where b=−h∈Zn,m=|Q∞|, and the column vectors of the n×mtype matrix Aare just the elements of Q∞. The algorithmic solution of (1) is well-known, even if an objective function m P i=1 cixi,x= (x1,...,xm), ci∈R (i= 1,...,m) should also be maximized (see e.g. [13]). If Q< ∞(Z≥0) is a full lattice, then we need only a finite amount of computation to verify the second part of the condition. It suffices to enumerate Qfand to check whether all the cosets in Znof the lattice Q< ∞(Z≥0) are represented or not. Thus we have a finite procedure to check the connectedness of Zn, and the theorem follows. 2 Corollary 12 If Nis a constant neighborhood sequence then Znis N-connected if and only if Q< ∞(Z≥0) = Zn. Corollary 13 Let N∈SO n. Let M=M1. . . MkMk+1 ∈Su nbe the neighborhood sequence defined in the proof of Proposition 5. Put Q′ f=nk P i=1 bibi∈ Pi, i = 1,...,ko. Then Znis N-connected if and only if M< k+1(Z≥0)is a full lattice in Rnand Q′ frepresents all the cosets of M< k+1(Z≥0)in Zn. In Fig. 1 we consider the 2D-neighborhood sequence N=N1N2N3N4∈Su 2, with Ni= (Pi, wi), where P1={(−1,0)},P2={(0,2),(3,2)},P3={(0,1)}, P4={(−2,−1),(1,1),(2,−1),(−1,−3)}and the weights are arbitrary. 9 for every hwith h∈ {1,...,t}we have b0+ h X l=1 bil≤2|b0|+X b∈B |b|, where Bis the set {bj|j= 1, . . . , t, bj6=b0}. PROOF. By Lemma 18 there is a permutation (j0, j1,...,jt) of (0,1,...,t) such that for every hwith h∈ {0,...,t}we have h P l=0 bjl≤ |b0|+P b∈B |b|. Let rbe the index for which jr= 0 and put il=     jl−1,if 1 ≤l < r jl,if l≥r. Let h∈ {1,...,t}. If h≥rthen b0+ h X l=1 bil= h X l=0 bjl≤ |b0|+X b∈B |b|. On the other hand, if h < r we have b0+ h X l=1 bil≤ |b0|+ h X l=1 bil=|b0|+ h−1 X l=0 bjl≤2|b0|+X b∈B |b|. This implies the statement. 2 Theorem 20 Let N=N1. . . NkNk+1 . . . Nl∈Su nwith Ni= (Pi, wi)for i∈ {1,...,l}. Then there is a finite procedure to decide whether W(N)is symmetric on Znor not. PROOF. First we introduce some notation. Put Ar={a1+···+arai∈Pi(i= 1,...,r)} for 1 ≤r < l, and A=k−1 S r=1 Ar,B=l−1 S r=k Ar. Moreover, set C={ak+1 +···+alai∈Pi(i=k+ 1,...,l)}. Write R=P α∈C |α|+ 4 max a∈B{|a|}, and let Qdenote the number of those p∈Zn for which |p| ≤ Rholds. Define the set Dby D={a+α1+···+αca∈A∪B, 0≤c≤2Q, αi∈C(i= 1,...,c)}. 16 Clearly, Dis a finite set. Hence by Theorem 14, we can check whether W(b) = W(−b) holds for every b∈D∪(−D), or not. If not, then Ndoes not induce a metric. So assume that Wis symmetric on D∪(−D). If Wis also symmetric on Zn\(D∪(−D)), then we are done. Thus suppose that W(b)6=W(−b) for some b∈Zn\(D∪(−D)). Then, a shortest path from Oto bis of the form b=a+α1+α2+···+αtwith a∈B,t≥2Q+ 1 and αi∈Cfor i= 1,...,t. Similarly, a shortest path to −bis given by −b=a′+α′ 1+α′ 2+···+α′ t′with a′∈B,t′≥2Q+ 1 and α′ i∈Cfor i= 1,...,t′. We can further assume that t+t′is minimal with the property W(b)6=W(−b) (b6∈ D∪(−D)). Observe that W(a+α1+α2+···+αr) = ℓ(a) + ℓ(α1) + ℓ(α2) + ···+ℓ(αr) (13) for t−2Q < r ≤tand similarly for a′+α′ 1+α′ 2+···+α′ r′. Moreover, observe that in the above formulae we may permute α1,...,αtarbitrarily as well as α′ 1,...,α′ t′without affecting the validity of the statements. Now apply Corollary 19 with b0=a+a′to (a+a′) + α1+···+αt+α′ 1+···+α′ t′=b+ (−b) = O. Then there exists a sequence i1,...,it+t′such that α∗ 1,...,α∗ t+t′is a permutation of α1,...,αt, α′ 1,...,α′ t′and a+a′+T P j=1 α∗ j≤4 max a∈B{|a|} +P α∈C |α|=R for T= 1,...,t+t′. Since there are exactly Qvectors p∈Znwith |p| ≤ R and by t, t′>2Q, we obtain the existence of Tand T′with 0 ≤T < T′≤Q such that a+a′+T P j=1 α∗ j=a+a′+T′ P j=1 α∗ jwhich implies T′ P j=T+1 α∗ j=O. After suitable permutations of α1,...,αtand α′ 1,...,α′ t′, we may assume that T′ P j=T+1 α∗ j=αs+1+···+αt+α′ s′+1+···+α′ t′, where t≥s≥Q+1, t′≥s′≥Q+1, (t−s) + (t′−s′) = T′−T≤Q. Hence a+α1+···+αs+a′+α′ 1+···+α′ s′=O.(14) From the minimality condition it follows that W(a+α1+···+αs) = W(a′+α′ 1+···+α′ s′),(15) hence by (13), ℓ(αs+1+···+αt)6=ℓ(α′ s′+1+···+α′ t′) in view of W(b)6=W(−b). By applying the above reasoning to (14) we obtain after suitable permutation integers r, r′with s≥r≥1, s′≥r′≥1, 0 <(s−r) + (s′−r′)≤Qand a+α1+···+αr+a′+α′ 1+···+α′ r′=O. 17 From (15) and the minimality condition it follows that W(a+α1+···+αr) = W(a′+α′ 1+···+α′ r′), hence by (13) ℓ(αr+1 +···+αs) = ℓ(α′ r′+1 +···+α′ s′).(16) However, we can as well consider a+α1+···+αr+αs+1 +···+αt+a′+α′ 1+···+α′ r′+α′ s′+1 +···+α′ t′=O. By the minimality condition we have W(a+α1+···+αr+αs+1 +···+αt) = W(a′+α′ 1+···+α′ r′+α′ s′+1 +···+α′ t′). Comparing this with W(b)6=W(−b), by (s−r) + (s′−r′)≤Qwe conclude that ℓ(αr+1 +···+αs)6=ℓ(α′ r′+1 +···+α′ s′) in contradiction with (16). Hence the theorem follows. 2 6.3 Metricity By combining the results obtained for the triangle inequality and symmetry with some additional observations, we obtain the following statement. Theorem 21 Let N=N1. . . NkNk+1 . . . Nl∈Su nwith Ni= (Pi, wi)for i∈ {1,...,l}. Then there is a finite procedure to decide whether Ninduces a metric on Znor not. PROOF. First we have to check whether Znis N-connected. This can be done by a finite procedure according to Theorem 11. From Theorems 17 and 20 we know that the triangular and symmetric behavior of W(N) also can be checked by a finite procedure. So only the positivity of W(N) which remains to check. To test positivity, we do the following. Let i∈ {1,...,l}be the maximal index for which for j= 1,...,i there exists a pj∈Pjsuch that wj(pj) = 0. Then W(N) is positive if and only if we have pj=Owhenever wj(pj) = 0 for j= 1,...,i. Clearly, this property can be checked by a finite procedure. Hence the theorem follows. 2 The following corollary extends the results of Das et al. [6] and Nagy [25] obtained for periodic octagonal and for general octagonal neighborhood sequences, respectively, in the finite dimensional case. 18 Corollary 22 Suppose that N= (Ni)∞ i=1 ∈Snwith Ni= (Pi, wi), such that N(j)⊒∗Nfor every j∈N,Znis N-connected, Niis symmetric, and wi(x)>0 for all x∈Pi\ {O}(i∈N). Then W(N)is a metric on Zn. PROOF. Let Wdenote the distance function induced by N. The second part of Theorem 15 guarantees that the triangle inequality holds for W. All the other necessary properties of metricity follow from our assumptions. 2 Corollary 23 Let N=N1∈Snwith N1= (P1, w1). If Znis N-connected, N1is symmetric, and w1(x)>0for all x∈P1\ {O}, then W(N)is a metric on Zn. PROOF. The statement easily follows from Corollary 22 by noting that W(q, r;N(j)) = W(q, r;N) for all q, r ∈Znand j∈Nin this case. 2 Corollary 24 Let N= (Ni)∞ i=1 ∈SO nwith Ni= (Pi, wi), such that for every i∈N,Nioccurs infinitely often in N. Suppose that Znis N-connected, Ni is symmetric, and wi(x)>0for all x∈Pi\ {O}(i∈N). Then W(N)is a metric on Zn. PROOF. As by our assumption there is no neighborhood Nioccurring only finitely many times in N, Proposition 5 and its proof show that there exists a constant neighborhood sequence Msuch that W(N) is identical with W(M). Hence the statement follows from Corollary 23. 2 7 Approximating the Euclidean metric The approximation of the Euclidean distance by digital metrics is a key problem in digital geometry. In this section we present some results towards this direction. Yamashita and Ibaraki [30] showed that for any N∈Sp n, if W(N) is a metric then there exist c1, c2∈R>0such that c1d(x;N)≤ ||x||2≤c2d(x;N) for any x∈Zn.(17) Now we investigate whether the Euclidean distance can be minorated/majorated or not in our more general model. 19 Proposition 25 Let N∈Snand suppose that W(N)is a metric. Then there exists a c1∈R>0, such that c1d(x;N)≤ ||x||2for any x∈Zn. PROOF. In fact the proof of Theorem 5 of Yamashita and Ibaraki [30] for periodic neighborhood sequences can be extended to this case. However, for the convenience of the reader, we recall the main steps of the proof. Let c0= max d(e;N)e= (e1,...,en), ei∈ {0,1},n P i=1 ei= 1. Note that c0>0, since W(N) is a metric. Then d(x;N)≤c0 n P i=1 |xi|=c0||x||1for any x= (x1,...,xn)∈Zn. It is well-known that 1 √n||x||1≤ ||x||2. Thus c1d(x;N)≤ ||x||2with c1=1 c0√n.2 From the following example we can see that there exists Nsuch that the Euclidean distance cannot be majorated in terms of d(x;N), even not with metrics generated by ultimately periodic neighborhood sequences. Example 26 Let n= 1,N1= (P, w1)with P={±1}and w1(±1) = 1, and let N2= (P, w2)with w2(±1) = 0. Consider N=N1N2∈Su 1. Then d(x;N) = 1 for any x∈Z(x6= 0), and thus there exists no c2∈R>0such that ||x||2≤c2d(x;N)for any x∈Z. The next two propositions show that property (17) holds under suitable mild conditions. Proposition 27 If N∈SO ninduces a metric on Zn, then there exists a c2∈ R>0such that ||x||2≤c2d(x;N)for any x∈Zn. PROOF. Theorem 8 and its proof guarantee that there exists a constant (periodic) neighborhood sequence, which generates the same metric as N. Since the statement holds for periodic sequences (see [30]), the proof is complete. 2 Proposition 28 Let N=N1. . . NkNk+1 . . . Nl∈Su nwith Ni= (Pi, wi)for i∈ {1,...,l}such that W(N) =: d(N)is a metric. Then there exists a c3∈R>0such that ||x||2≤c3d(x;N)for every x∈Zn if and only if ℓ(s)>0for every s∈Q∞\ {O}, where Q∞is defined in Theorem 11. 20 PROOF. We may assume without loss of generality that N=N1. . . NkNk+1 with Ni= (Pi, wi) for i= 1,...,k+ 1 using Proposition 7. Thus to prove the statement, we can replace the condition ”ℓ(s)>0 for every s∈Q∞\ {O}” by ”wk+1(y)>0 for every y∈Pk+1 \ {O}”. First we prove necessity. Suppose that there exists a y∈Pk+1 \ {O}such that d(y) = 0. Consider an arbitrary path s= [O, x1,...,xk] (the empty path if k= 0) and continue this path by always selecting y∈Pk+1 from the neighborhood Nk+1. Using this path we can move arbitrarily far from the origin with respect to the Euclidean distance. However, all the points on the path have length at most ℓ(s). This means that we cannot majorate the Euclidean distance, and proves the necessity part. To prove sufficiency assume that wk+1(y)>0 for every y∈Pk+1 \ {O}. Put b1= min (ℓ(s) ||s||2 s∈ k [ t=1 (t X i=1 uiui∈Pi, i = 1,...,t)), b2= min (wk+1(y) ||y||2 y∈Pk+1 \ {O}), and put b3= min{b1, b2}. Note that b3>0, since d(N) is a metric and wk+1(y)>0 for every y∈Pk+1 \ {O}. Let xbe an arbitrary point of Zn, and consider a shortest N-path from Oto x,O=q0,...,qr=xsay. If r≤kthen ||x||2≤1 b1d(x;N). Otherwise, d(x;N) = ℓ([O,...,qk])+ r P i=k+1 wk+1(qi−qi−1)≥ b1||qk||2+b2 r P i=k+1 ||qi−qi−1||2≥b3||x||2. Hence c3d(x;N)≥ ||x||2with c3=1 b3, and the proof is complete. 2 8 Applications Neighborhood sequences have already been applied successfully for practical image processing purposes like segmentation [20], and retrieval [22]. In this section we show how our current results can be used in the theory of distance transformations. On one hand we indicate how ultimately periodic neighborhood sequences can provide a new tool in some well-known image processing procedures. On the other hand we present an application scheme for neighborhood sequences from SO n. 21 8.1 Distance transformations Distance transformations provide a very useful basis for many image processing problems. To indicate how widely this technique is applied, we refer to [2,4,14,28] and the references given there as characteristic examples. Usually the classical families of distance transformations (n-Neighbor, chamfer, octagonal, D-Euclidean) are considered in applications. These families are deeply investigated by Borgefors in [1]. These distance transformations are based on a mask of given size (e.g. 3×3 or 5×5 in Z2), with certain non-negative weights assigned to the entities of the mask. For example, Fig. 2 shows the general 3×3 mask used by Borgefors in [1] to compose various distance transformations. Fig. 2. Classical 3×3 mask operator for distance transformations with non-negative weights d1,d2. Using this mask, the distance of two points of the domain is calculated just as in our model, by considering a constant neighborhood sequence N=M, where the neighborhood Mis the mask of the distance transformation together with the assigned weights. Note that the distance transformation families investigated by Borgefors [1] are special cases of the model given by Yamashita and Ibaraki in [30], who used periodic neighborhood sequences. However, Yamashita and Ibaraki [30] showed that if the distance function generated by a periodic neighborhood sequence is a metric then the periodic sequence is equivalent to a constant sequence (with respect to the generated distance functions). Thus we yet again have a constant sequence if the important property of metricity is required. Ultimately periodic sequences presented in our model obviously cover periodic ones and thus also the classical families in [1]. Hence the use of such sequences opens up new possibilities to achieve more general distance transformations. We underline Example 6 which shows that ultimately periodic sequences cannot be replaced by constant ones, even if metricity is required. Especially, as a key problem, we mention the famous results of Borgefors [1] about finding suitable weights for a distance transformation to approximate the Euclidean distance. It is natural to expect that in our more general model better approximations can be found for the Euclidean metric than in case of using constant sequences. 22 8.2 Optimal usage of resources We show an application scheme to demonstrate the importance and applicability of our results about SO n. Using sequences belonging to SO n, intuitively we have the opportunity to ignore undesired elements of the sequence, by doing nothing for no cost at a step (by using Owith weight 0). Moreover, we do not have to deal with the order of the neighborhoods in the sequence when finding a shortest path between two points, as according to Remark 4 and Proposition 5 the elements of such sequences can be freely permuted. In general, we can interpret this case as if we have resources with given costs, such that some of the resources can be used only a prescribed number of times, while others infinitely often. More precisely, we can think of moving in the space. Suppose that our task is to find an optimal path to our destination. If we know which path would be optimal then regardless of the order, we can pick up the desired vectors freely and build up our path. To make our ideas more clear we consider a concrete example. Let the neighborhoods N1, N2, N3, N4be as shown in Figure 3(a), where the black discs represent the neighborhood vectors and the values inside their weights. Let N=N1N2N3N4N1{Ni}∞ i=5 be any sequence such that Ni∈ {N3, N4}for i≥5, with both Ni=N3and Ni=N4infinitely often. Then clearly, N∈SO 2. Now, as it can be seen also in Figure 3(b), to reach (2,2) from the origin we can take O, (1,0), Oand (1,2) from N1,N2,N3and N4, respectively, to obtain the shortest path. In other words we can ”skip” N1and N3, and use N2and N4freely to build up the path. Using Proposition 5 we can determine an ultimately constant neighborhood sequence N′equivalent to N. This sequence is given by N′=N1N1N2N0, where N0is shown in Figure 3(c). When investigating metricity, we can restrict our attention from the general case to ultimately periodic sequences. To see this, consider a (not necessarily ultimately periodic) neighborhood sequence from SO n. Let N1, N2,...,Nkbe the neighborhoods which occur only finitely often with the right multiplicities, and Nk+1,...,Nlthe neighborhoods which occur infinitely often. Then, as shown in the paper, the metrical properties of the sequence are the same as of N1N2. . . NkNk+1 . . . Nl. So we can apply the theory in the paper for ultimately periodic sequences to study the metrical properties of such neighborhood sequences. We may even combine N1. . . Nkto one neighborhood and Nk+1 . . . Nlto another to simplify formulas, but then we loose control on the sizes of the neighborhoods as shown above. 23 (a) (b) (c) Fig. 3. Choosing optimal neighborhood elements to obtain a shortest path using a sequence N∈SO 2; (a) the elements of N, (b) the shortest path to (2,2) using N2and N4, (c) the neighborhood to compose the equivalent ultimately constant sequence N′=N1N1N2N0. 9 Conclusion Since the first submission of the paper, the authors went on with their research regarding neighborhood sequences. As corresponding results, we highlight the derivation of integer values to be used in chamfering to approximate the Euclidean metric [19,29], the application of ultimately periodic neighborhood sequences in image retrieval [22], and the application of weighted neighborhoods to approximate non metrical Minkowski distances [21]. We also note that the complexity analysis of the finite procedures we have given to decide on several properties regarding neighborhood sequences has been left as an open issue. Acknowledgment The authors are grateful to the referees for their thorough work and valuable comments. 24 References [1] G. Borgefors: Distance transformations in arbitrary dimensions, Comput. Vision Graphics Image Process. 27 (1984), 321-345. [2] G. Borgefors: Hierarchical chamfer matching: a parametric edge matching algorithm, IEEE Transactions on Pattern Analysis and Machine Intelligence, 10(6) (1988), 849-865. [3] P.E. Danielsson: 3D octagonal metrics, Eighth Scandinavian Conf. Image Process., 1993, pp. 727-736. [4] P.E. Danielsson: Euclidean distance mapping, Computer Graphics and Image Processing,14 (1980), 227-248. [5] P.P. Das: Best simple octagonal distances in digital geometry, J. Approx. Theory 68 (1992), 155-174. [6] P.P. Das, P.P. Chakrabarti and B.N. Chatterji: Distance functions in digital geometry, Inform. Sci. 42 (1987), 113-136. [7] P.P. Das, P.P. Chakrabarti and B.N. Chatterji: Generalised distances in digital geometry, Inform. Sci. 42 (1987), 51-67. [8] P.P. Das and B.N. Chatterji: Estimation of errors between Euclidean and mneighbor distance, Inform. Sci. 48 (1989), 1-26. [9] P.P. Das and B.N. Chatterji: Hyperspheres in digital geometry, Inform. Sci. 50 (1990), 73-91. [10] P.P. Das and B.N. Chatterji: Octagonal distances for digital pictures, Inform. Sci. 50 (1990), 123-150. [11] A. Fazekas: Lattice of distances based on 3D-neighbourhood sequences, Acta Math. Acad. Paedagog. Nyh´azi. 15 (1999), 55-60. [12] A. Fazekas, A. Hajdu and L. Hajdu: Lattice of generalized neighbourhood sequences in nD and ∞D, Publ. Math. Debrecen 60 (2002), 405-427. [13] R. Garfinkel and G.L. Nemhauser: Integer Programming. John Wiley and Sons, New York, 1972. [14] Y. Ge and J.M. Fitzpatrick: On the generation of skeletons from discrete euclidean distance maps., IEEE Transactions on Pattern Analysis and Machine Intelligence,18 (1996), 1055-1066. [15] J.H. Grace and A. Young: The Algebra of Invariants. New York: Chelsea, 1965. [16] A. Hajdu: Geometry of neighbourhood sequences, Pattern Recognition Lett. 24/15 (2003), 2597-2606. [17] A. Hajdu and L. Hajdu: Velocity and distance of neighbourhood sequences, Acta Cybernet. 16 (2003), 133-145. 25