A framework for digital topology

A F amewo k o Digi al Topology E. Dom’nguez A.R. F anc& Dp o. Ing. EMc ica e In o mi ica Facul ad de Ciencias. U. de Za agoza E-50009 Za agoza (SPAIN) Dp o. Ing. Elk ica e In o m& ica Facul ad de Ciencias. U. de Za agoza E-50009 Za agoza (SPAIN) A. Mkquez Dp o. de Algeb a, Geome ia, Topologia y Compu acibn Facul ad de Ma emL icas. U. de Se illa Se illa (SPAIN) Abs mc The main goal o his pape is o show he unc ional a chi ec u e o a amewo k o Dig- i al Topology. This a chi ec u e has ou le els, called De ice, Logical, Concep ual and Con inuous Le els. In each one o hem we can use se e al mod- els acco ding o he pa icula p oblem. The models in he De ice Le el ep esen he physical p oblem whe eas he models in he Con inuous Le el a e opological spaces which allow us o use he well- known esul s o con inuous opology (ac ually, he s onge esul s o polyhed al opology). The o he wo le els a e used o And a digi al solu ion. The Logical Le el is close o he De ice Le el and i is used o p ocessing, o w i ing algo i hms and showing hei co ec ness. The Concep ual Le el is he nea es o he Con inuous Le el and i is used o ansla e esul s and no ions om he Con inuous Le el o he Logical Le el. I. INTRODUCTION The‘main pu pose o Digi al Topology is he s udy o opological p ope ies o disc e e objec s which a e go en digi izing con inuous objec s. Digi al Topology plays a e y impo an ole in compu e ision, im- age p ocessing and compu e g aphics. Bu a comple e heo e ical ounda ion o a consis en heo y o digi al spaces is s ill missing. Kong and Rosen eld gi e in [5] a e y good su ey abou his subjec . Howe e , se e al heo ies ha e been de ised o he analysis o he opological a ibu es o a digi al im- age. Le us ecall, o example, Rosen eld’s combina o- ial heo y [9,lO,ll] (gene alized by Kong and Roscoe ~~ Manusc ip ecei ed July 1, 1993. This wo k was suppo ed in pa by he Dipu acih Gene al de A ag6n, he DGICYT and he Jun a de Andalucia, Spain. in [4]) and Khalimsky’s heo y based in a pa icula opological space [3]. The common d awback o hese heo ies is ha , in o de o include well-known esul s o he Euclidean Topology, hey need o ew i e new p oo s ins ead o exploi ing hose coming om con in- uous opology. The eason is ha hese heo ies a e a om he Euclidean plane (o space). Some o he au ho s (Ko ale sky [7], Ankeney, Ri e [l]) can use esul s coming om Euclidean Topology bu hey ha e p oblems in he image p ocessing because he models a e a om he disc e e objec s which ep esen sc een digi al images. In his pape we in oduce a new poin o iew. We p esen a amewo k, which ies o de ine a gene al heo y o he de elopmen o Digi al Topology. To do his, ou amewo k p oposes a mul ile el a chi ec- u e whose main ea u e is he abili y o ansla ing concep s, s a emen s, p oo s and algo i hms om con- inuous opology wi hou ew i ing a pa allel heo y. The i s le el ep esen s a compu e and he ollow- ing le els consis o models mo e and mo e abs ac . Finally, he las le el ep esen s he Euclidean Topol- ogy. This akes us, om he disc e e wo ld (a compu e sc een), and b ings us close o he con inuous one ( he Euclidean plane o space). In ou amewo k he e is no an uni e sal model which can be used o sol ing all he p oblem in Digi- al Topology. Ins ead, gi en a p oblem we mus choose a sui able model in e e y le el. Acco ding o ou p o- posal, wha is common o all he p oblems is he wo k- ing me hodology and he mul ile el unc ional a chi ec- u e. To show ha ou heo y wo ks we p esen he solu- ion o he well-known Digi al Jo dan Cu e P oblem (as many o he au ho s ha e done in o de o p o e he 65 Figu e 1: Sc een model Figu e 2: A digi al image consis ency o hei heo ies). So, in he second sec ion we choose he models o each le el in he a chi ec u e, and hen, in he hi d sec ion, we gi e he p oo o he esul ha is educed o gi ing he app op ia e no ions and ansla ions. Finally, he o h sec ion is de o ed o explain he unc ional a chi ec u e in a gene al con ex . 11. THE MATHEMATICAL MODELS We conside ha he sc een model is an in ini e ma- ix S o pixels wi h he shape showed in Fig l whe e each pixel can ha e wo s a es ep esen ed by a do ed o black small squa e. In his con ex , a digi al image in he sc een model S is de ined by a se o black poin s (see a digi al cu e in Fig 2). The Digi al Jo dan Cu e P oblem consis s o p o - ing ha a simple closed digi .al cu e, as ,lia o Fig 2, di ides he sc een in wo connec ed componen s. E i- den ly i is necessa y o de ine he meaning o “simple closed digi al cu e” and “connec ed componen s.” Fo his, we will s a by de ining he ma hema ical models used in each le el o ou amewo k. Since ou p oblems has a ,opological na u e, i is na u al o conside a ans o ma ion om he sc een model S o he g aph E8 ep esen ed in he Fig 3. Fo he sake o simplici y we will suppose ha he e ex Figu e 3: The g aph E8 Figu e 4: The g aph E: se o E8 is Z2, which is he se o all pai s o in ege numbe s. The e ices o he g aph ep esen he pixels and wo e ices a e adjacen i and only i hei co - esponding pixels a e con iguous in he ob ious sense. In o de o sol e ou p oblem, his ma hema ical model ep esen s he Logical Le el. In i he cu e becomes he subg aph induced by he e ices co esponding o black pixels. Because E8 is no plana , i is well-known ha wi hin i we canno ep esen he ,opology o he Euclidean plane (see Rosen eld [9]). To sol e ha p oblem we la en ou his g aph in a na .u al way and we ge he plana g aph E; ep esen ed in he Fig 4. In his g aph he e a e wo di e en kinds o e ices. Some o hem ep esen he pixels and he o he s, called middle poin s, ep esen a deg ee o nea ness be ween he co - esponding pixels; in ac i is he diagonal nea ness. Obse e ha his g aph is a iangula ion o he Eu- clidean plane. This makes up he Concep ual Le el o 66 Figu e 5: A digi al cu e C in E8 Figu e 6: A digi al cu e C' in ES sol e ou p oblem. On he o he hand, we de ine a digi al image (o digi al subspace) o one o hese g aphs as an induced subg aph; ha is, a subg aph which con ains an edge i and only i i con ains he wo e ices o he edge. We ep esen he se o digi al images in E8 and E: by U(&) and U(&), espec i ely. Now we ha e a na u al ans o ma ion A : O( Es) - U(E;) de ined as ollows: Gi en a digi al image C in Ea, n(C) = c' is he subg aph induced by he e ices in C and he middle e ices de ined by wo diagonal e ices in C (see he Fig 5 and 6). In a na u al way we ha e a ans o ma ion A* : o(E,') - o(E8). Gi en a digi al image C' in E,' n*(C*) = C is he subg aph in- duced by he e ices in C' ha a e no middle e ices. Also we ha e a ans o ma ion j : (?(E,) - ,C(R2) in- duced by he embedding o E, in he Euclidean plane R2, whe e C(R2) is he se o polygona subspaces. In his way. we ha e he a chi ec u e ep esen ed by he ollowing diag am whe e O(S) is he se o digi al images in he sc een model S and i is he 1-1 ans o ma ion be ween O(E8) and O(S). 67 III. THE DIGITAL JORDAN CURVE THEOREM In he logical and concep ual le els, a simple digi al cu e is he subg aph induced by a sequence o e ices {PO,. . . ,pn} SO ha Pi is adjacen o pj i and only i li - jl 5 1. The cu e is called closed i , in addi ion, po = pn. Then a digi al objec in he sc een model S is called a simple closed digi al cu e i i s image by i-' is his ype o cu e in Ea. These de ini ions ag ee wi h. hose usually adop ed in he li e a u e (see [5]). In his way, a simple closed digi al cu e C in he sc een model S is, by de ini ion, ans o med h ough i in such a cu e in Ea, deno ed also by C. I is ob ious ha he image by 17 o a simple closed digi al cu e C in E8 is a simple closed digi al cu e C' in E;. And, also, he image by he embedding j o C is a polygonal Jo dan Cu e C' in R2 (see Fig 5, 6). In his way, we ha e ansla ed ou ini ial Jo dan Cu e P oblem o he Sc een Model o analogous p oblems in Ea, E,' and R2. Now hen, i is well-known ha he solu ion o his p oblem in R2 is he Polygonal Jo dan Cu e Theo em. So ha , ou goal is o ansla e his heo em, by mean o he ans o ma ions j and R', o E8 in o de o ind a solu ion o ou p oblem in his model. In he li e a u e, he e exis s se e al equi alen s a emen s o he Polygonal Jo dan Cu e Theo em. He e, we conside one o hem ha is app op ia ed o ind an algo i hm sol ing his p oblem and o p o e i s co ec ness. The base o his s a emen is he no ion o ans e sal in e sec ion be ween a hal -line, which is pa allel o he axis OX, and a polygonal cu e. Le D be a polygonal cu e in R2 whose se o e ices {PO,. . . ,pn} is coun e -clockwise o de ed. Le , = {(z,y); y = y, and z 2 zq} be a hal -line, whe e q = ( z, y,). The e exis s a ans e sal in e sec ion be- ween D and q i one o he ollowing si ua ions occu s: (a) , in e sec s he edge de ined by he e ices pi and p1+i in only a poin P B {pi,Pi+1}- (b) he e exis s i E (0,. . . , n} such ha o some k 2 0 2- Pi-1 > Yq and Yi+k+l < Yq o Pi-1 < Yq and Yi+k+1 > Yq 3. x, 2 xq o e e y i 5 j L i + k. Wi h his de ini ion we can s a e he nex well-known esul . Polygonal Jo dan Cu e Theo em. Le D be a simple closed polygonal cu e in R2, hen R2 D has wo connec ed componen s (one o hem bounded and he o he one unbounded). Mo eo e , a poin q E R2 D belongs o he bounded componen i and only i #( , 4 D) E 1 (mod 2), whe e #( q ,+, D) ep esen s he numbe o ans e sal in e sec ions be ween D and q. I is impo an o poin ou ha he esul we wan o ansla e o E8 is applied o polygonal cu es c' coming om a digi al cu e C in E8 and hal -lines p , whe e p' belongs o Z2. In his way, i is easy o obse e ha he ans e sal in e sec ions be ween one o such a hal -line pl and one o such a cu e C' ne e occu s in case (a) o he de ini ion abo e. Tha is, his kind o in e sec ion always has a e ex o he cu e. So ha , we can ansla e he no ion o ans e sal in e sec ion o E8 and E,' in such a way ha #@p' m C') = #(.P' 1 C') = #(.p m C) On he o he hand, in he Concep ual Le el, ep- esen ed by E;, we can conside he na u al no ion o connec ion induced by he g aph s uc u e. This no ion coincides wi h he no ion o connec ion induced by he opology o he Euclidean plane h ough he embed- ding j. So we can conside he connec ed componen s o E: c'. Since E; is a iangula ion o R2 i is no di icul o p o e ha he numbe b connec ed compo- nen s o E,' C' and R2 C' ag ee; e en mo e, each componen I<* o E; c' is he ini e iangula ion o a componen IC' o R2 C' in he ollowing sense: 1. Gi en Ii' he e is one and only one componen I " o R2 C' such ha I<* c IC'. 2. I{* is induced by he e ices o E,' in I;'. These p ope ies show us ha he componen s o E,' c' ep esen he componen s o R' C'. Now we can ansla e .he Jo dan Cu e Theo em o E,' in he ollowing way. Jo dan Cu e Theo eiu in E;. Le C' be a simple closed digi al cu e in E;, hen E; C" has wo connec ed componen s (one o hem bounded and he o he one unbounded). Mo eo e , a poin y' E E: C' belongs o he bounded componen i and only i #( p. mC) E 1 (mod 2). Figu e 7: Componen s o E,' C' 68 Figu e 8: Top-componen s o E8 c Finally, we need o conside an app op ia e no ion o componen in &. Le c be a simple closed digi al cu e in Ea. we call a op-componen o E8 c o he image by i ' o a connec ed componen o E; c'. Obse e ha , in gene al, a op-componen o E8 c does no coincide wi h a connec ed componen o ES C (see Fig 7, 8). In his way we ha e p o ed Jo dan Cu e Theo em in Ea. Le C be a simple closed digi al cu e in Ea. hen E0 C has wo con- nec ed op-componen s (one o hem bounded and he o he one unbounded). Mo eo e , a poin p E E8 C belongs o he bouiided op-componen i and only i #( l, C) E 1 (mod 2). Obse e ha ile p e ious p oo no oul~ p o es he gi en p oblem bu also allows o ansla e he well- known algo i hm o P epa a a [8] (coming om Com- pu a ional Geome y) o sol e he digi al cu e inclu- sion p obleni. IV. THE FUNCTIONAL ARCHITECTURE The p e ious sec ions con ain a pa icula ins ance o he me hodology p oposed in ou amewo k. In his sec ion, we will p esen he gene al unc ional a chi ec- u e o his amewo k. Ou amewo k has ou le - els, called De ice, Logical, Concep ual and Con inuous Le els. In he De ice Le el we ep esen he objec s in a compu e sc een ( ypically a digi al image). This le el has a e y small deg ee o abs ac ion and we only ep- esen he physical aspec s o he objec s. A second le el o abs ac ion is ob ained in he Log- ical Le el. We conside in i he aspec s o p oximi y o he objec s so, we can s udy some p ope ies o opo- logical na u e. The main unc ion o his le el is o be he suppo o w i ing he algo i hms and o p o e hei co ec ness. In gene al, he le el abo e is a om he ma hema - ical model in which we ha e a solu ion o ou p oblem. So we need he Concep ual Le el as an in e ace be- ween he le el abo e and he Con inuous Le el. To ealize his in e ace i is necessa y o ansla e: (1) Ob- jec s and p ope ies om he Logical Le el o he Con- cep ual Le el and ice e sa; (2) Objec s and p ope ies om he Concep ual Le el o he Con inuous Le el; (3) P ope ies o objec s in he Con inuous Le el o p op- e ies o objec s in he Concep ual Le el. Finally, he Con inuous Le el is used o ind a con- inuous solu ion. Obse e ha , ac ually, he objec s and concep s ob ained oni lie Logical Le el a e in- side lie Polyhed al Topology a he han he Con in- uous Topology and so we can use he mo e powe ul ools o his ield. Tlie objec s o ou physical p oblem ha e been ansla ed by consecu i e abs ac ions om lie De ice Le el. Now we mus ind a con inuous so- lu ion in his le el by using he well-known esul s o Polyhed al Topology and we aiisla e i a o he Logical Le el ac oss he Concep ual Le el. When we ha e a coiic e e p oblem and a pa icula sc een model we mis , choose speci ic models in each le el and unc ions which can suppo he unc .ioliali y liab we ha e desc ibed. Speci ically, suppose ha hese chosen niodels a e U, L, C a id S o he De ice, Log- ical, Concep ual and Con inuous Le el, espec i ely. Le C?(D), (?(I,), O(C) and O(S) be he se s o lie ob- jec s (i.e., subs uc u es in sonie ma ~hema ical sense) o liese models. So we lia e 4he ollowing unc ional a chi ec u e We ep esen ou physical'objec s in he mode! D and we ansla e i o he model L by he unc ion i. I we ha e in L enough knowledge o sol e he p oblem we do no need o use he es o he models; when we ha e he solu ion, we in e p e i in D by he unc ion i. O he wise, we ansla e he objec s o he model C. I we can ind a solu ion in i we ansla e i o he model L by he unc ion T*. Bu i e en in C we canno ind a solu ion, we ansla e he objec s o he model S whe e we can apply all o he qui e powe ul ools and eml s o Polyhed al Topology and, i we ind a solu ion, we ansla e i o L by he unc ions j and T*. F om a heo e ical poin o iew, he pa icula s uc u es ha we need in he le els depend on he p oblem we wan o sol e. Bu , in gene al, he e is a basic s uc u e o a wide ange o p oblems. Fo exam- ple, he basic s uc u e o he plana Digi al Topology is he one shown in he pa ag aphs abo e. In addi ion, his amewo k can be used o sol e p oblems which ha e no been p oposed up ill now in Digi al Topology. An impo an example is he digi- al Shoen lies heo em which s a es ha a simple closed digi al Jo dan cu e su ounds a digi al disk. The solu- ion o his p oblem is well-known in Plana Euclidean Topology. Thus, ou mul ile el me hodology can be applied (choosing sui able models) o ob ain he co e- sponding digi al e sion. Mo eo e , his amewo k also wo ks in highe di- mensions. As an example, he p oo gi en o he digi al Jo dan cu e heo em can easily be adap ed o sol e he co esponding 3-dimensional p oblem (compa e his so- lu ion wi h [GI, whe e Koppe man e al. ew i e a new p oo o his esul ). V. FINAL REMARKS In his pape , we ha e de eloped a gene al ame- wo k ha allows o use e y powe ul ools and e- sul s ( hose o Polyhed al Topology) in Digi al Topol- ogy. Tlie models used in he a chi ec u e depend on he Sc een Model. Fo example, i ou Sc een Model is ep esen ed by he Fig 9(a), he g aph used as Logi- cal Model is he one in he Fig 9(b) (called hexagonal g aph). In his case, each pai o cells has he same con- nec i i y deg ee and he g aph is plana , so we choose lie same g aph o ep esen he Concep ual Le el. Ob- se e ha , in his case, his model e i ies he Jo dan Cu e Theo em. The p oo is he same as in he case o he g aph o he &adjacencies. The e a e models which do no e i y he Jo dan Cu e Theo em. An example o his is he g aph E4, ep esen ed by lie Fig 10(b), which is he logical model o lie sc een model ep esen ed by he Fig 10(a). This g aph is plana , so we mus conside he same g aph 69 Figu e 9: (a) Sc een model; (b) The g aph E6 (4 (b) Figu e 10: (a) Sc een model; (b) The g aph E4 in he Concep ual Le el. Thus he op-connec ion is equi alen o he 4connec ion. Now, he e ices o a minimal cycle on his g aph de ine a closed simple digi al cu e bu i s complemen is connec ed. Ve y equen ly, some au ho s ha e shown a p oo o he Digi al Jo dan Cu e Theo em in o de o p o e he consis ency o hei heo ies. Fo his eason we also ha e chosen i o ou amewo k. In he li e a u e he e a e se e al p oo s o his heo em using di e - en echniques. The i s au ho who ga e a p oo was Rosen eld who p esen ed wo e sions in a se ies o pa- pe s ([9,10,12]). One is aking an 8-cu e (i.e., a cu e in he g aph E8) and p o ing ha i s complemen has wo 4-connec ed componen s (i.e., connec ed by a cs in he g aph E4 o he 4adjacencies). The o he is aking a 4cu e (i.e., a cu e in he g aph E4) and p o ing ha i s complemen has wo $-connec ed componen s (i.e., connec ed by a cs in E*). I is easy o obse e ha he heo em p esen ed ill his pape includes bo h e sions. This is a di ec conse- quence o he ollowing p ope y. Gi en a closed digi al cu e c in E8, hen: 2. I C is an 4cu e, he op-componen s o E8 C coincide wi h he 8-connec ed componen s. - ACKNOWLEDGEMENTS We would like o hank Julio Rubio o his e y use ul commen s on an ea lie d a o his pape . REFERENCES [l] L.A. Ankeney and G.H. Ri e , Cellula Topol- ogy and i s Applica ions in Image P ocessing, In . Jou n. Comp . In . Sciences 12, 1983, 433-455. [2] B. BollobL, G aph Theo y: an in oduc o y . cou se, G adua e Tex s in Ma h., ol. 63, Sp inge - Ve lag, 1979. [3] E. Khalimsky, R. Koppe man, P.R. Meye , Com- pu e g aphics and Connec ed Topologies on ini e o de ed se s, Topology and Appl. 36, 1990, 1-17. [4] T.Y. Kong, A.W. Roscoe, A Theo y o Bina y Dig- i al Pic u es, Compu . Vision G aphics Image P o- cess. 32, 1985, 221-243. [5] T.Y. Kong and A. Rosen eld, Digi al Topology: In- oduc ion and Su ey, Compu e Vision, G aph- ics and Image P ocessing 48, 1989, 357-393. [6] R. Koppe man, P.R. Meye , R.G. Wilson, A Jo - dan Su ace Theo em o h ee-dimensional Digi al Spaces, Disc e e and Compu a ional Geome y 6, 1991, 155-161. [7] E. Ko ale sky, The opology o cellula complexes as applied o image p ocessing, in Compu e Anal- ysis o Images and Pa e ns, P oc. I1 In . Con- e ence CAIP'87 on Au oma ic Image P ocessing, 1987, 162-173. [8] F.P. P epa a a, M.I. Shamos, Compu a ional Ge- ome y: an in oduc ion, Tex s and Monog aphs in Compu e Science, Sp inge -Ve lag, 1985. [9] A. Rosen eld, Connec i i y in Digi al Pic u es, dou n. Assoc. Compl. Mach. 17, 1970, 146160. [lo] A. Rosen eld, A cs and Cu es in Digi al Pic u es, Jou n. Assoc. Comp . Mach. 20, 1973, 81-87. [ll] A. Rosen eld, Adjaceiicy iii Digi al Pic u es, 111- o ma ion and Coii i l 26, 1974, 24-33. [la] A. Rosen eld, Digi al Topology, A ie . Ma h.. Mon hly 86, 1979, 621-630. 1. I c is an 8-cu e, he op-componen s o E8 C' coincide wi h he 4-connec ed componen s. 70