A framework for digital topology

A Framework for Digital Topology E. Dom’nguez A.R. Franc& Dpto. Ing. EMctrica e Informitica Facultad de Ciencias. U. de Zaragoza E-50009 Zaragoza (SPAIN) Dpto. Ing. Elktrica e Inform&tica Facultad de Ciencias. U. de Zaragoza E-50009 Zaragoza (SPAIN) A. Mkquez Dpto. de Algebra, Geometria, Topologia y Computacibn Facultad de MatemLticas. U. de Sevilla Sevilla (SPAIN) Abstmct The main goal of this paper is to show the functional architecture of a framework for Digital Topology. This architecture has four levels, called Device, Logical, Conceptual and Continuous Levels. In each one of them we can use several models according to the particular problem. The models in the Device Level represent the physical problem whereas the models in the Continuous Level are topological spaces which allow us to use the wellknown results of continuous topology (actually, the stronger results of polyhedral topology). The other two levels are used to And a digital solution. The Logical Level is closer to the Device Level and it is used for processing, for writing algorithms and showing their correctness. The Conceptual Level is the nearest to the Continuous Level and it is used to translate results and notions from the Continuous Level to the Logical Level. I. INTRODUCTION The‘main purpose of Digital Topology is the study of topological properties of discrete objects which are gotten digitizing continuous objects. Digital Topology plays a very important role in computer vision, image processing and computer graphics. But a complete theoretical foundation of a consistent theory for digital spaces is still missing. Kong and Rosenfeld give in [5] a very good survey about this subject. However, several theories have been devised for the analysis of the topological attributes of a digital image. Let us recall, for example, Rosenfeld’s combinatorial theory [9,lO,ll] (generalized by Kong and Roscoe ~~ Manuscript received July 1, 1993. This work was supported in part by the Diputacih General de Arag6n, the DGICYT and the Junta de Andalucia, Spain. in [4]) and Khalimsky’s theory based in a particular topological space [3]. The common drawback of these theories is that, in order to include well-known results of the Euclidean Topology, they need to rewrite new proofs instead of exploiting those coming from continuous topology. The reason is that these theories are far from the Euclidean plane (or space). Some other authors (Kovalevsky [7], Ankeney, Ritter [l]) can use results coming from Euclidean Topology but they have problems in the image processing because the models are far from the discrete objects which represent screen digital images. In this paper we introduce a new point of view. We present a framework, which tries to define a general theory for the development of Digital Topology. To do this, our framework proposes a multilevel architecture whose main feature is the ability for translating concepts, statements, proofs and algorithms from continuous topology without rewriting a parallel theory. The first level represents a computer and the following levels consist of models more and more abstract. Finally, the last level represents the Euclidean Topology. This takes us, from the discrete world (a computer screen), and brings us closer to the continuous one (the Euclidean plane or space). In our framework there is not an universal model which can be used for solving all the problem in Digital Topology. Instead, given a problem we must choose a suitable model in every level. According to our proposal, what is common for all the problems is the working methodology and the multilevel functional architecture. To show that our theory works we present the solution to the well-known Digital Jordan Curve Problem (as many other authors have done in order to prove the 65 Figure 1: Screen model Figure 2: A digital image consistency of their theories). So, in the second section we choose the models for each level in the architecture, and then, in the third section, we give the proof of the result that is reduced to giving the appropriate notions and translations. Finally, the forth section is devoted to explain the functional architecture in a general context. 11. THE MATHEMATICAL MODELS We consider that the screen model is an infinite matrix S of pixels with the shape showed in Fig l where each pixel can have two states represented by a dotted or black small square. In this context, a digital image in the screen model S is defined by a set of black points (see a digital curve in Fig 2). The Digital Jordan Curve Problem consists of proving that a simple closed digit.al curve, as t,liat of Fig 2, divides the screen in two connected components. Evidently it is necessary to define the meaning of “simple closed digital curve” and “connected components.” For this, we will start by defining the mathematical models used in each level of our framework. Since our problems has a t,opological nature, it is natural to consider a transformation from the screen model S to the graph E8 represented in the Fig 3. For the sake of simplicity we will suppose that the vertex Figure 3: The graph E8 Figure 4: The graph E: set of E8 is Z2, which is the set of all pairs of integer numbers. The vertices of the graph represent the pixels and two vertices are adjacent if and only if their corresponding pixels are contiguous in the obvious sense. In order to solve our problem, this mathematical model represents the Logical Level. In it the curve becomes the subgraph induced by the vertices corresponding to black pixels. Because E8 is not planar, it is well-known that within it we cannot represent the t,opology of the Euclidean plane (see Rosenfeld [9]). To solve that problem we flatten out this graph in a nat.ural way and we get the planar graph E; represented in the Fig 4. In this graph there are two different kinds of vertices. Some of them represent the pixels and the others, called middle points, represent a degree of nearness between the corresponding pixels; in fact it is the diagonal nearness. Observe that this graph is a triangulation of the Euclidean plane. This makes up the Conceptual Level to 66 Figure 5: A digital curve C in E8 Figure 6: A digital curve C' in ES solve our problem. On the other hand, we define a digital image (or digital subspace) of one of these graphs as an induced subgraph; that is, a subgraph which contains an edge if and only if it contains the two vertices of the edge. We represent the set of digital images in E8 and E: by U(&) and U(&), respectively. Now we have a natural transformation A : O( Es) - U(E;) defined as follows: Given a digital image C in Ea, n(C) = c' is the subgraph induced by the vertices in C and the middle vertices defined by two diagonal vertices in C (see the Fig 5 and 6). In a natural way we have a transformation A* : o(E,') - o(E8). Given a digital image C' in E,' n*(C*) = C is the subgraph induced by the vertices in C' that are not middle vertices. Also we have a transformation j : (?(E,) - ,C(R2) induced by the embedding of E, in the Euclidean plane R2, where C(R2) is the set of polygonat subspaces. In this way. we have the architecture represented by the following diagram where O(S) is the set of digital images in the screen model S and i is the 1-1 transformation between O(E8) and O(S). 67 III. THE DIGITAL JORDAN CURVE THEOREM In the logical and conceptual levels, a simple digital curve is the subgraph induced by a sequence of vertices {PO,. . . ,pn} SO that Pi is adjacent to pj if and only if li - jl 5 1. The curve is called closed if, in addition, po = pn. Then a digital object in the screen model S is called a simple closed digital curve if its image by i-' is this type of curve in Ea. These definitions agree with. those usually adopted in the literature (see [5]). In this way, a simple closed digital curve C in the screen model S is, by definition, transformed through i in such a curve in Ea, denoted also by C. It is obvious that the image by 17 of a simple closed digital curve C in E8 is a simple closed digital curve C' in E;. And, also, the image by the embedding j of C is a polygonal Jordan Curve C' in R2 (see Fig 5, 6). In this way, we have translated our initial Jordan Curve Problem for the Screen Model to analogous problems in Ea, E,' and R2. Now then, it is well-known that the solution to this problem in R2 is the Polygonal Jordan Curve Theorem. So that, our goal is to translate this theorem, by mean of the transformations j and R', to E8 in order to find a solution to our problem in this model. In the literature, there exists several equivalent statements for the Polygonal Jordan Curve Theorem. Here, we consider one of them that is appropriated to find an algorithm solving this problem and to prove its correctness. The base of this statement is the notion of transversal intersection between a half-line, which is parallel to the axis OX, and a polygonal curve. Let D be a polygonal curve in R2 whose set of vertices {PO,. . . ,pn} is counter-clockwise ordered. Let r, = {(z,y); y = y, and z 2 zq} be a half-line, where q = ( z, y,). There exists a transversal intersection between D and rq if one of the following situations occurs: (a) r, intersects the edge defined by the vertices pi and p1+i in only a point P B {pi,Pi+1}- (b) there exists i E (0,. . . , n} such that for some k 2 0 2Pi-1 > Yq and Yi+k+l < Yq or Pi-1 < Yq and Yi+k+1 > Yq 3. x, 2 xq for every i 5 j L i + k. With this definition we can state the next well-known result. Polygonal Jordan Curve Theorem. Let D be a simple closed polygonal curve in R2, then R2 \ D has two connected components (one of them bounded and the other one unbounded). Moreover, a point q E R2 \ D belongs to the bounded component if and only if #(r, 4 D) E 1 (mod 2), where #(rq ,+, D) represents the number of transversal intersections between D and rq. It is important to point out that the result we want to translate to E8 is applied to polygonal curves c' coming from a digital curve C in E8 and half-lines rpt, where p' belongs to Z2. In this way, it is easy to observe that the transversal intersections between one of such a half-line rpl and one of such a curve C' never occurs in case (a) of the definition above. That is, this kind of intersection always has a vertex of the curve. So that, we can translate the notion of transversal intersection to E8 and E,' in such a way that #@p' m C') = #(.P' 1 C') = #(.p m C) On the other hand, in the Conceptual Level, represented by E;, we can consider the natural notion of connection induced by the graph structure. This notion coincides with the notion of connection induced by the topology of the Euclidean plane through the embedding j. So we can consider the connected components of E: \ c'. Since E; is a triangulation of R2 it is not difficult to prove that the number bf connected components of E,' \ C' and R2 \ C' agree; even more, each component I<* of E; \ c' is the finite triangulation of a component IC' of R2 \ C' in the following sense: 1. Given Ii' there is one and only one component Ir" of R2 \ C' such that I<* c IC'. 2. I{* is induced by the vertices of E,' in I;'. These properties show us that the components of E,' \ c' represent the components of R' \ C'. Now we can translate t.he Jordan Curve Theorem to E,' in the following way. Jordan Curve Theoreiu in E;. Let C' be a simple closed digital curve in E;, then E; \ C" has two connected components (one of them bounded and the other one unbounded). Moreover, a point y' E E: \ C' belongs to the bounded component if and only if #(rp. mC) E 1 (mod 2). Figure 7: Components of E,' \ C' 68 Figure 8: Top-components of E8 \ c Finally, we need to consider an appropriate notion of component in &. Let c be a simple closed digital curve in Ea. we call a top-component of E8 \ c to the image by ir' of a connected component of E; \ c'. Observe that, in general, a top-component of E8 \ c does not coincide with a connected component of ES \ C (see Fig 7, 8). In this way we have proved Jordan Curve Theorem in Ea. Let C be a simple closed digital curve in Ea. then E0 \ C has two connected top-components (one of them bounded and the other one unbounded). Moreover, a point p E E8 \ C belongs to the bouiided top-component if and only if #( rl, C) E 1 (mod 2). Observe that tile previous proof not oul~ proves the given problem but also allows to translate the wellknown algorithm of Preparata [8] (coming from Computational Geometry) to solve the digital curve inclusion probleni. IV. THE FUNCTIONAL ARCHITECTURE The previous sections contain a particular instance of the methodology proposed in our framework. In this section, we will present the general functional architecture of this framework. Our framework has four levels, called Device, Logical, Conceptual and Continuous Levels. In the Device Level we represent the objects in a computer screen (typically a digital image). This level has a very small degree of abstraction and we only represent the physical aspects of the objects. A second level of abstraction is obtained in the Logical Level. We consider in it the aspects of proximity of the objects so, we can study some properties of topological nature. The main function of this level is to be the support for writing the algorithms and to prove their correctness. In general, the level above is far from the mathematical model in which we have a solution for our problem. So we need the Conceptual Level as an interface between the level above and the Continuous Level. To realize this interface it is necessary to translate: (1) Objects and properties from the Logical Level to the Conceptual Level and vice versa; (2) Objects and properties from the Conceptual Level to the Continuous Level; (3) Properties of objects in the Continuous Level to properties of objects in the Conceptual Level. Finally, the Continuous Level is used to find a continuous solution. Observe that, actually, the objects and concepts obtained froni tlie Logical Level are inside tlie Polyhedral Topology rather than the Continuous Topology and so we can use the more powerful tools of this field. Tlie objects of our physical problem have been translated by consecutive abstractions from tlie Device Level. Now we must find a continuous solution in this level by using the well-known results of Polyhedral Topology and we traiislate ita to the Logical Level across the Conceptual Level. When we have a coiicrete problem and a particular screen model we mist, choose specific models in each level and functions which can support the funct.ioliality tliab we have described. Specifically, suppose that these chosen niodels are U, L, C arid S for the Device, Logical, Conceptual and Continuous Level, respectively. Let C?(D), (?(I,), O(C) and O(S) be the sets of tlie objectsr(i.e., substructures in sonie mat~hematical sense) of tliese models. So we liave t4he following functional architecture We represent our physical'objects in the mode! D and we translate it to the model L by the function i. If we have in L enough knowledge to solve the problem we do not need to use the rest of the models; when we have the solution, we interpret it in D by the function i. Otherwise, we translate the objects to the model C. If we can find a solution in it we translate it to the model L by the function T*. But if even in C we cannot find a solution, we translate the objects to the model S where we can apply all of the quite powerful tools and remlts of Polyhedral Topology and, if we find a solution, we translate it to L by the functions j and T*. From a theoretical point of view, the particular structures that we need in the levels depend on the problem we want to solve. But, in general, there is a basic structure for a wide range of problems. For example, the basic structure for the planar Digital Topology is the one shown in the paragraphs above. In addition, this framework can be used to solve problems which have not been proposed up till now in Digital Topology. An important example is the digital Shoenflies theorem which states that a simple closed digital Jordan curve surrounds a digital disk. The solution to this problem is well-known in Planar Euclidean Topology. Thus, our multilevel methodology can be applied (choosing suitable models) to obtain the corresponding digital version. Moreover, this framework also works in higher dimensions. As an example, the proof given for the digital Jordan curve theorem can easily be adapted to solve the corresponding 3-dimensional problem (compare this solution with [GI, where Kopperman et al. rewrite a new proof of this result). V. FINAL REMARKS In this paper, we have developed a general framework that allows to use very powerful tools and results (those of Polyhedral Topology) in Digital Topology. Tlie models used in the architecture depend on the Screen Model. For example, if our Screen Model is represented by the Fig 9(a), the graph used as Logical Model is the one in the Fig 9(b) (called hexagonal graph). In this case, each pair of cells has the same connectivity degree and the graph is planar, so we choose tlie same graph to represent the Conceptual Level. Observe that, in this case, this model verifies the Jordan Curve Theorem. The proof is the same as in the case of the graph of the &adjacencies. There are models which do not verify the Jordan Curve Theorem. An example of this is the graph E4, represented by tlie Fig 10(b), which is the logical model of tlie screen model represented by the Fig 10(a). This graph is planar, so we must consider the same graph 69 Figure 9: (a) Screen model; (b) The graph E6 (4 (b) Figure 10: (a) Screen model; (b) The graph E4 in the Conceptual Level. Thus the top-connection is equivalent to the 4connection. Now, the vertices of a minimal cycle on this graph define a closed simple digital curve but its complement is connected. Very frequently, some authors have shown a proof of the Digital Jordan Curve Theorem in order to prove the consistency of their theories. For this reason we also have chosen it for our framework. In the literature there are several proofs of this theorem using different techniques. The first author who gave a proof was Rosenfeld who presented two versions in a series of papers ([9,10,12]). One is taking an 8-curve (i.e., a curve in the graph E8) and proving that its complement has two 4-connected components (i.e., connected by arcs in the graph E4 of the 4adjacencies). The other is taking a 4curve (i.e., a curve in the graph E4) and proving that its complement has two $-connected components (i.e., connected by arcs in E*). It is easy to observe that the theorem presented ill this paper includes both versions. This is a direct consequence of the following property. Given a closed digital curve c in E8, then: 2. If C is an 4curve, the top-components of E8 \ C coincide with the 8-connected components. - ACKNOWLEDGEMENTS We would like to thank Julio Rubio for his very useful comments on an earlier draft of this paper. REFERENCES [l] L.A. Ankeney and G.H. Ritter, Cellular Topology and its Applications in Image Processing, Int. Journ. Compt. Inf. Sciences 12, 1983, 433-455. [2] B. BollobL, Graph Theory: an introductory . course, Graduate Texts in Math., vol. 63, SpringerVerlag, 1979. [3] E. Khalimsky, R. Kopperman, P.R. Meyer, Computer graphics and Connected Topologies on finite ordered sets, Topology and Appl. 36, 1990, 1-17. [4] T.Y. Kong, A.W. Roscoe, A Theory of Binary Digital Pictures, Comput. Vision Graphics Image Process. 32, 1985, 221-243. [5] T.Y. Kong and A. Rosenfeld, Digital Topology: Introduction and Survey, Computer Vision, Graphics and Image Processing 48, 1989, 357-393. [6] R. Kopperman, P.R. Meyer, R.G. Wilson, A Jordan Surface Theorem for three-dimensional Digital Spaces, Discrete and Computational Geometry 6, 1991, 155-161. [7] E. Kovalevsky, The topology of cellular complexes as applied to image processing, in Computer Analysis of Images and Patterns, Proc. I1 Int. Conference CAIP'87 on Automatic Image Processing, 1987, 162-173. [8] F.P. Preparata, M.I. Shamos, Computational Geometry: an introduction, Texts and Monographs in Computer Science, Springer-Verlag, 1985. [9] A. Rosenfeld, Connectivity in Digital Pictures, dourn. Assoc. Compl. Mach. 17, 1970, 146160. [lo] A. Rosenfeld, Arcs and Curves in Digital Pictures, Journ. Assoc. Compt. Mach. 20, 1973, 81-87. [ll] A. Rosenfeld, Adjaceiicy iii Digital Pictures, 111formation and Coiitivl 26, 1974, 24-33. [la] A. Rosenfeld, Digital Topology, Artier. Math.. Monthly 86, 1979, 621-630. 1. If c is an 8-curve, the top-components of E8 \ C' coincide with the 4-connected components. 70