A ternary relation for structuring the digital plane

A ternary relation for structuring the digital plane Josef Šlapal1, 1 IT4Innovations Centre of Excellence, Brno University of Technology, 616 69 Brno, Czech Republic Abstract. We discuss certain ternary relations, called plain, and show that each of them induces a connectedness on its underlying set. This connectedness allows for definitions of concepts of simple closed and Jordan curves. We introduce a particular plain ternary relation on the digital plane Z2and, as the main result, we prove a digital analogue of the Jordan curve theorem for the connectedness induced by this relation. It follows that the ternary relation introduced may be used as a convenient structure on the digital plane for the study of the geometric properties of digital images that are related to boundaries because boundaries of objects in digital images are represented by digital Jordan curves. An advantage of this structure over the Khalimsky topology is that it allows Jordan curves to turn at the acute angle π 4at some points. 1 Introduction Digital topology is a theory that was founded for the study of geometric and topological properties of digital images. The classical, graph theoretic approach to digital topology is based on using the 4-adjacency and 8-adjacency graphs for structuring Z2(cf. [6] and [7]). Unfortunately, neither 4-adjacency nor 8-adjacency itself allows for an analogue of the Jordan curve theorem (cf. [4]) so that a combination of the two adjacency graphs has to be used. To eliminate this deficiency, a new, purely topological approach to the problem was proposed in [2] which utilizes a convenient topology for structuring the digital plane, namely the Khalimsky topology. The convenience of the Khalimsky topology for structuring the digital plane was shown in [2] by proving an analogue of the Jordan curve theorem for the topology (recall that the classical Jordan curve theorem states that a simple closed curve in the Euclidean plane separates this plane into exactly two connected components). The topological approach was then developed by many authors - see, e.g., [3]-[5] and [9]. Since the Khalimsky topological space is an AlexandroffT0-space, it corresponds to a partial order on Z2, the so-called specialization order. The connectedness in the Khalimsky space then coincides with the connectedness in the underlying (simple) graph of the specialization order. Thus, when studying the connectedness of digital images, this graph, rather than the Khalimsky topology itself, may be used for structuring the digital plane. A disadvantage of this approach is that Jordan curves in the (specialization order of the) Khalimsky topology may never turn at the acute angle π 4. It would, therefore, be useful to find some new, more convenient structures on Z2that would allow Jordan curves to turn, at some points, to form the acute angle π 4. In the present note, to obtain such a conve- e-mail: [email protected].cz nient structure, we replace the specialization order of the Khalimsky topology, hence a binary relation on Z2, with a ternary relation on Z2. We will define a connectedness provided by this ternary relation and will prove a digital Jordan curve theorem for this connectedness thus showing that the ternary relation provides a convenient structure on the digital plane for the study of digital images. 2 Preliminaries For every point (x,y)∈Z2, we denote by A4(x,y) and A8(x,y) the sets of all points that are 4-adjacent and 8adjacent to (x,y), respectively. Thus, A4(x,y)={(x+ i,y +j); i,j∈{−1,0,1},ij =0,i+j0}and A8(x,y)=A4(x,y)∪{(x+i,y+j); i,j∈{−1,1}}. The simple graphs (Z2,A4) and (Z2,A8) are called the 4-adjacency graph and 8-adjacency graph, respectively (for the basic graph-theoretic concepts used see [1]). In digital image processing, the 4-adjacency and 8adjacency graphs are the most frequently used structures on the digital plane. But, since the late 1980’s, another structure on Z2has been used too, namely the Khalimsky topology [2]. The specialization order of the Khalimsky topology (see Introduction) is the binary relation ≤on Z2 given as follows: For any (x,y),(z,t)∈Z2,(x,y)≤(z,t) if and only if •(x,y)=(z,t)or •x,yare even and (z,t)∈A8(x,y)or •xis even, yis odd, z=x+iwhere i∈{−1,1}, and t=y or •xis odd, yis even, z=x, and t=y+iwhere i∈{−1,1}. A portion of the specialization order ≤of the Khalimsky topology is demonstrated in Figure 1 by a directed graph with the vertex set Z2where an oriented edge from a point pto a point qmeans that p≤q. © The Authors, published by EDP Sciences. This is an open access article distributed under the terms of the Creative Commons Attribution License 4.0 (http://creativecommons.org/licenses/by/4.0/). DOI: 10.1051/ ,01012 (2017) 70901012 ITM Web of Conferences 9 AMCSE 2016 itmconf/201           - - - - - - - - - - 66666 66666 ????? ????? rrrrr rrrrr rrrrr rrrrr rrrrr             @@ @R @@ @R @@ @R @@ @R         @ @ @I @ @ @I @ @ @I @ @ @I 01234 1 2 3 4 Figure 1. A portion of the specialization order of the Khalimsky topology. Recall that, given a directed graph (i.e., a set with a binary relation), its underlying (undirected) simple graph is obtained by just ignoring the direction of the edges. A circle in a simple graph is said to be a simple closed curve if, with each of its vertices, it contains precisely two vertices adjacent to it. A simple closed curve Jin a simple graph with the vertex set Vis called a Jordan curve if it separates the set Vinto precisely two components, i.e., if the induced subgraph V−Jhas exactly two components. The famous Jordan curve theorem proved for the Khalimsky topology in [2] may be formulated as follows: Theorem 1 In the underlying graph of the specialization order of the Khalimsky topology, every simple closed curve with at least four points is a Jordan curve. It is readily verified that a simple closed curve (and thus also a Jordan curve) in the underlying graph of the specialization order of the Khalimsky topology may never turn at the acute angle π 4. It could therefore be useful to replace the specialization order of the Khalimsky topology with some more convenient structure (relation on Z2) that would allow Jordan curves to turn at the acute angle π 4at some points. And this is what we will do in the next section. 3 Plain ternary relations and induced connectedness Recall that, given a positive in integer nand a set X,annary relation on Xis a subset R⊆Xn. Thus, the elements of Rare finite sequences (ordered n-touples) (x0,x1, ..., xn)= (xi|i<n) consisting of elements of X(for the basic properties of n-ary relations see [8]). In the sequel, we will restrict our considerations to n=3, i.e., to ternary relations. Definition 1 A ternary relation Ron a set Xis said to be plain if, for any f,g ∈R,fgimplies card(f∩g)≤1. Definition 2 Let Rbe a plain ternary relation on a set X and na nonnegative integer. A sequence C=(ci|i≤n) of elements of Xis called an R-walk if the following two conditions are satisfied: I. For every positive integer i<n, there exists (x0,x1,x2)∈Rsuch that {ci,ci+1}={x0,x1}or {ci,ci+1}={x1,x2}, II. Every (a0,a1,a2)∈Rsatisfies the following two conditions: (i) if there exists i∈{0,1, ..., n−1}such that ci= a1and ci+1=a2, then i>0 and ci−1=a0, (ii) f there exists i∈{1,2, ..., n}such that ci−1=a2 and ci=a1, then i<nand ci+1=a0. An R-walk (ci|i≤n) with the property that n≥2 and ci=cj⇔{i,j}={0,n}is said to be an R-circle. Observe that, if (x0,x1, ..., xn)isanR-walk, then (xn,xn−1, ..., x0)isanR-walk, too (so that R-walks are closed under reversion) and, if (xi|i≤m) and (yi|i≤p) are R-walks with xm=y0, then, putting zi=xifor all i≤mand zi=yi−mfor all iwith m≤i≤m+p, we get an R-walk (zi|i≤m+p) (so that R-walks are closed under composition). Given a plain ternary relation Ron a set X, a subset Y⊆Xis said to be R-connected if, for every pair a,b∈Y, there is an R-walk (ci|i≤n) such that c0=a,cn=b and ci∈Yfor all i∈{0,1, ..., n}. A maximal (with respect to set inclusion) R-connected subset of Xis called an Rcomponent of X. Definition 3 Let Rbe a plain ternary relation on a set X.A nonempty, finite and R-connected subset Jof Xis said to be an R-simple closed curve if every element (a0,a1,a2)∈ Rwith {a0,a1}⊆Jsatisfies a2∈Jand every z∈Jfulfills one of the following two conditions: (1) There are exactly two elements (a0,a1,a2)∈Rsatisfying both {a0,a1,a2}⊆Jand z∈{a0,a2}and there is no element (b0,b1,b2)∈Rsatisfying both {b0,b1,b2}⊆Jand z=b1. (2) There is exactly one element (b0,b1,b2)∈Rsatisfying both {b0,b1,b2}⊆Jand z=b1and there is no element (a0,a1,a2)∈Rsatisfying both {a0,a1,a2}⊆ Jand z∈{a0,a2}. Clearly, every R-simple closed curve is an R-circle. Definition 4 Let Rbe a plain ternary relation on a set X. An R-simple closed curve Jis called an R-Jordan curve if the subset X−J⊆Xconsists (i.e., is the union) of precisely two R-components. From now on, Rwill denote the plain ternary relation on Z2given as follows: For every ((xi,y i)|i<3) such that (xi,y i)∈Z2for every i<3, ((xi,y i)|i<3) ∈Rif and only if one of the following eight conditions is satisfied: (1) x0=x1=x2and there is k∈Zsuch that yi=4k+i for all i<3, (2) x0=x1=x2and there is k∈Zsuch that yi=4k−i for all i<3, 2 DOI: 10.1051/ ,01012 (2017) 70901012 ITM Web of Conferences 9 AMCSE 2016 itmconf/201                   - - - - - - - - - - - - - - - - - - ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 rrrrrrrrr rrrrrrrrr rrrrrrrrr rrrrrrrrr rrrrrrrrr rrrrrrrrr rrrrrrrrr rrrrrrrrr rrrrrrrrr                         @@@ @R @@@ @R @@@ @R @@@ @R @ @ @ @I @ @ @ @I @ @ @ @I @ @ @ @I 012345678 1 2 3 4 5 6 7 8 Figure 2. A portion of the relation R. rrrrrrrrrrrrr rrrrrrrrrrrrr rrrrrrrrrrrrr rrrrrrrrrrrrr rrrrrrrrrrrrr rrrrrrrrrrrrr rrrrrrrrrrrrr rrrrrrrrrrrrr rrrrrrrrrrrrr rrrrrrrrrrrrr rrrrrrrrrrrrr rrrrrrrrrrrrr rrrrrrrrrrrrr                   @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ 0246810 12 2 4 6 8 10 12 Figure 3. R-Jordan curves. (3) y0=y1=y2and there is k∈Zsuch that xi=4k+i for all i<3, (4) y0=y1=y2and there is k∈Zsuch that xi=4k−i for all i<3, (5) there is k∈Zsuch that xi=4k+ifor all i<3 and there is l∈Zsuch that yi=4l+ifor all i<3, (6) there is k∈Zsuch that xi=4k+ifor all i<3 and there is l∈Zsuch that yi=4l−ifor all i<3, (7) there is k∈Zsuch that xi=4k−ifor all i<3 and there is l∈Zsuch that yi=4l+ifor all i<3, (8) there is k∈Zsuch that xi=4k−ifor all i<3 and there is l∈Zsuch that yi=4l−ifor all i<3. A portion of Ris demonstrated in Figure 2. The ordered triples belonging to Rare represented by arrows oriented from first to last terms. Theorem 2 Every circle in the graph demonstrated in Figure 3 that does not turn at any point (4k+2,4l+2), k,l∈Z, is an R-Jordan curve. Proof. Clearly, every circle in the graph demonstrated in Fig. 3 that does not turn at any point (4k+2,4l+2), k,l∈Z,isanR-simple closed curve. Let z=(x,y)∈ Z2be a point such that x=4k+pand y=4l+qfor some k,l,p,q∈Zwith pq =±1. Then we define the fundamental triangle T(z) to be the fifteen-point subset of Z2given as follows: T(z)= ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ {(r,s)∈Z2;4k≤r≤4k+14,4l≤s≤4l+4k+4−r} if x=4k+1 and y=4l+1 for some k,l∈Z, {(r,s)∈Z2;4k≤r≤4k+4,4l≤s≤4l+r−4k} if x=4k+3 and y=4l+1 for some k,l∈Z, {(r,s)∈Z2;4k≤r≤4l,4l+4k+4−r≤s≤4l+4} if x=4k+3 and y=4l+3 for some k,l∈Z, {(r,s)∈Z2;4k≤r≤4k+4,4l+r−4k≤s≤4l+4} if x=4k+1 and y=4l+3 for some k,l∈Z. Graphically, every fundamental triangle T(z) consists of fifteen points and forms a rectangular triangle obtained from a 4 ×4-square by dividing it by a diagonal. More precisely, each of the two diagonals divides the square into just two fundamental triangles having a common hypotenuse coinciding with the diagonal. In every fundamental triangle T(z), the point zis one of the three inside points of the triangle. The (four types of) fundamental triangles are demonstrated in the following figure: rrrrr rrrrr rrrrr rrrrr rrrrr  @ @ @ @ @ @ @ @ 01234 1 2 3 4 z1 z2 z3 z4 T(z1) T(z2)T(z3) T(z4) Given a fundamental triangle, we speak about its sides - it is clear from the above picture which sets are understood to be the sides (note that each side consists of five points and that two different fundamental triangles may have at most one side in common). Now, one can easily see that: (1) Every fundamental triangle is R-connected (so that the union of two fundamental triangles having a common side is connected). (2) If we subtract from a fundamental triangle some of its sides, then the resulting set is still R-connected. (3) If S1,S2are fundamental triangles having a common side D, then the set (S1∪S2)−Mis R-connected whenever Mis the union of some sides of S1or S2 different from D. (4) Every R-connected subset of Z2with at most two points is a subset of a fundamental triangle. 3 DOI: 10.1051/ ,01012 (2017) 70901012 ITM Web of Conferences 9 AMCSE 2016 itmconf/201 We will show that the following is also true: (5) For every circle Cin the graph demonstrated in Fig. 3 that does not turn at any point (4k+2,4l+2), k,l∈Z, there are sequences SF,SIof fundamental triangles, SFfinite and SIinfinite, such that, whenever S∈{S F,SI}, the following two conditions are satisfied: (a) Each member of S, excluding the first one, has a common side with at least one of its predecessors. (b) Cis the union of those sides of fundamental triangles in Sthat are not shared by two different fundamental triangles from S. Put C1=Cand let S1 1be an arbitrary fundamental triangle with S1 1∩C1∅. For every k∈Z,1≤k, if S1 1,S1 2, ..., S1 kare defined, let S1 k+1be a fundamental triangle with the following properties: S1 k+1∩C1∅, S1 k+1has a side in common with S1 kwhich is not a subset of C1and S1 k+1S1 ifor all i,1≤i≤k. Clearly, there will always be a (smallest) number k≥1 for which no such fundamental triangle S1 k+1exists. Denoting by k1 this number, we have defined a sequence (S1 1,S1 2, ..., S1 k1) of fundamental triangles. Let C2be the union of those sides of fundamental triangles in (S1 1,S1 2, ..., S1 k1) that are disjoint from C1and not shared by two different fundamental triangles in (S1 1,S1 2, ..., S1 k1). If C2∅, we construct a sequence (S2 1,S2 2, ..., S2 k2) of fundamental triangles in an analogous way to (S1 1,S1 2, ..., S1 k1) by taking C2instead of C1(and obtaining k2analogously to k1). Repeating this construction, we get sequences (S3 1,S3 2, ..., S3 k3), (S4 1,S4 2, ..., S1 k4), etc. We put S=(S1 1,S1 2, ..., S1 k1,S2 1,S2 2, ..., S2 k2,S3 1,S3 2, ..., S3 k3, ...) if Ci∅for all i≥1 and S= (S1 1,S1 2, ..., S1 k1,S2 1,S2 2, ..., S2 k2, ..., Sl 1,Sl 2, ..., Sl kl)ifCi∅ for all iwith 1 ≤i≤land Ci=∅for i=l+1. Further, let S 1=T(z) be a fundamental triangle such that zSwhenever Sis a member of S. Having defined S 1, let S=(S 1,S 2, ...) be a sequence of fundamental triangles defined analogously to S(by taking S 1instead of S1 1). Then one of the sequences S,Sis finite and the other is infinite. Indeed, Sis finite (infinite) if and only if its first member equals such a fundamental triangle T(z) for which z=(k,l)∈Z2has the property that the cardinality of the set {(x,l)∈Z2;x>k}∩Cis odd (even). The same is true for S. If we put {SF,SI}={S,S}where SFis finite and SIis infinite, then the conditions (a) and (b) are clearly satisfied. Given a circle Cin the graph demonstrated in Fig. 3 that does not turn at any point (4k+2,4l+2), k,l∈Z, let SFand SIdenote the union of all members of SFand SI, respectively. Then SF∪SI=Z2and SF∩SI=C. Let S∗ F and S∗ Ibe the sequences obtained from SFand SIby subtracting Cfrom each member of SFand SI, respectively. Let S∗ Fand S∗ Idenote the union of all members of S∗ Fand S∗ I, respectively. Then S∗ Fand S∗ Iare connected by (1), (2) and (3) and it is clear that S∗ F=SF−Cand S∗ I=SI−C. So, S∗ Fand S∗ Iare the two components of Z2−Cby (4) (SF−Cis called the inside component and SI−Cis called the outside component). The proof is complete. The circles in the graph demonstrated in Fig. 3 that do not turn at any point (4k+2,4l+2), k,l∈Z, which are R-Jordan curves by the previous Theorem, provide a rich enough variety of circles to be used for representing borders of objects in digital images. The advantage of the circles over the Jordan curves in the Khalimsky topology is that they may turn at at acute angle π 4at some points. Example 1 Consider the following (digital picture of a) triangle: rrrrrrrrr rr rr rr r (0,0)=AB CD=(8,0) E=(4,4) While the triangle ADE is a R-Jordan curve, it is not a Jordan curve in the (underlying graph of the specialization order of) Khalimsky topology. For this triangle to be a Jordan curve in the Khalimsky topology, we have to delete the points A,B,C and D. But this will lead to a considerable deformation of the triangle. 4 Conclusions We have shown that every plain ternary relation induces connectedness on its underlying set. This connectedness was used to define concepts of simple closed and Jordan curves in the underlying set of a given plain ternary relation. We then introduced and discussed a particular plain ternary relation on the digital plane Z2and showed that the connectedness induced by this relation allows for a digital analogue of the Jordan curve theorem. Thus, we have shown that the ternary relation introduced provides a convenient structure on the digital plane for the study of digital images. An advantage of this structure over the Khalimsky topology is that it allows the Jordan curves to turn at the acute angle π 4at some points. Since Jordan curves represent borders of objects in digital images, the structure on Z2provided by the ternary relation introduced may be used in digital image processing for solving problems related to boundaries such as pattern recognition, boundary detection, contour filling, data compression, etc. This work was supported by The Ministry of Education, Youth and Sports of the Czech Republic from the National Programme of Sustainability (NPU II) project "IT4Innovations excellence in science - LQ1602". References [1] J.A. Bondy, U.S.R. Murty, Graph Theory (Springer, 2008) [2] E.D. Khalimsky, R. Kopperman, P.R. Meyer, Topology Appl. 36, 1–17 (1990). [3] E.D. Khalimsky, R. Kopperman, P.R. Meyer, Jour. of Appl. Math. and Stoch. Anal. 3, 27–55 (1990) 4 DOI: 10.1051/ ,01012 (2017) 70901012 ITM Web of Conferences 9 AMCSE 2016 itmconf/201 [4] T.Y. Kong, R. Kopperman, P.R. Meyer, Amer. Math. Monthly 98, 902–917 (1991) [5] R. Kopperman, P.R. Meyer, R.G. Wilson, Discr. and Comput. Geom. 6, 155–161 (1991) [6] A. Rosenfeld, Amer. Math. Monthly 86, 621–630 (1979) [7] A. Rosenfeld, Picture Languages (Academic Press, New York, 1979) [8] J. Šlapal, Publ. Math. Debrecen 38, 39–48 (1991) [9] J. Šlapal, Lect. Notes in Comput. Sci. 5852, 425-436 (2009) 5 DOI: 10.1051/ ,01012 (2017) 70901012 ITM Web of Conferences 9 AMCSE 2016 itmconf/201