Array Tissue-like P Systems

A ay Tissue-like P Sys ems Hepzibah A. Ch is inal1, Daniel D´ıaz-Pe nil1, Miguel A. Gu i´e ez-Na anjo2, Ma io J. P´e ez-Jim´enez2 1Resea ch G oup on Compu a ional Topology and Applied Ma hema ics Depa men o Applied Ma hema ics I {hepzi,sbdani}@us.es 2Resea ch G oup on Na u al Compu ing Depa men o Compu e Science and A i icial In elligence {magu ie ,ma pe }@us.es Uni e si y o Se illa, A da. Reina Me cedes s/n, 41012, Se illa, Spain Summa y. A ay g amma s ha e been s udied in he amewo k o Memb ane Compu - ing by using ew i ing ules om ansi ion P sys ems. In his pape we p esen a new app oach o dealing wi h a ay g amma s by using issue-like P sys ems and p esen an applica ion o he segmen a ion o images in wo dimensional compu e g aphics. 1 In oduc ion A ay g amma s can be conside ed as a s aigh o wa d ex ension o s ing g am- ma s o wo dimensional pic u es. Such pic u es a e se s o symbols placed in he poin s wi h in ege coo dina es o he plane. They ha e been widely s udied and ha e a la ge adi ion in he li e a u e (see, e.g. [2, 6, 16, 22]). Recen ly, Memb ane Compu ing has also app oxima ed o a ay g amma s by se ing b idges be ween bo h a eas (see, e.g. [1, 14, 20]). The basic idea in such app oaches is conside ing an a ay (i.e., a ini e se o objec s placed in poin s o he plane wi h in ege coo dina es) as a P sys em objec and using ew i ing ules o he ype used in ansi ion P sys ems [13] o eplacing i . The ype o ule used is x→y( a ) whe e x→yis a con ex - ee ule and a ∈he e, ou , in is he a ge which indica es he memb ane whe e he gene a ed objec will be placed. Such ew i ing ules cap u e he idea o a ay p oduc ion p:A → B wi h Aand Ba ays. In his pape we p esen a new app oach o linking Memb ane Compu ing o a ay g amma s. Ins ead o using ansi ion P sys ems o handle he a ays we p opose o use issue-like P sys ems. This app oach allows us o use he powe o sympo -an ipo ules o designing Memb ane Compu ing algo i hms which deal wi h a ay objec s. In such P sys em model, he ules a e o ype (i, u/ , j) wi h he ollowing in e p e a ion: I he mul ise uoccu s in a memb ane wi h 38 H.A. Ch is inal e al. label iand he mul ise occu s in a memb ane wi h label j, bo h mul ise can be in e changed. We conside an ex ension o his ype o ules. We will conside ha wo a ays Aand Bcan appea ( espec i ely) in he mul ise s uand . The seman ics o such ule will be explained below, bu he in ui ion is ha he a ays in he memb anes iand jwill be pa ially modi ied. As a case s udy, we p esen an applica ion o a ay issue-like P sys ems o he Segmen a ion P oblem in compu e ision. Segmen a ion in compu e ision (see [8]), e e s o he p ocess o pa i ioning a digi al image in o mul iple segmen s (se s o pixels). The goal o segmen a ion is o simpli y and/o change he ep esen a ion o an image in o some hing ha is mo e meaning ul and easie o analyze o an human. Image segmen a ion is ypically used o loca e objec s and bounda ies (lines, cu es, e c.) in images. Mo e p ecisely, image segmen a ion is he p ocess o assigning a label o e e y pixel in an image such ha pixels wi h he same label sha e ce ain isual cha ac e is ics. In he li e a u e, he e exis s di e en echniques o segmen an image. Some o hem a e clus e ing me hods [23], his og am-based me hods [21], Wa e shed ans- o ma ion me hods [25] o g aph pa i ioning me hods [24]. Some o he p ac ical applica ions o image segmen a ion a e medical imaging [23], he s udy o ana om- ical s uc u e, loca e objec s in sa elli e images ( oads, o es s, e c.) [19] o ace ecogni ion [7] among o he s. The pape is o ganized as ollows: Fi s we b ie ly ecall some basic de ini ions ela ed o g aphs and mul ise s and in oduce ou de ini ion o pixel and a ay. Nex , we in oduce a new P sys em model called A ay issue-like P sys ems on he basis o issue P sys ems. In Sec ion 4, his P sys em model is used o ind a solu ion o he segmen a ion p oblem in Digi al Image. 2 De ini ions An alphabe ,Σ, is a non-emp y se , whose elemen s a e called symbols. An o de ed sequence o symbols is a s ing. The numbe o symbols in a s ing uis he leng h o he s ing, and i is deno ed by |u|. As usual, he emp y s ing (o leng h 0) is deno ed by λ. The se o s ings o leng h nbuil wi h symbols om he alphabe Σ is deno ed by Σnand Σ∗=∪n≥0Σn. A language o e Σis a subse o Σ∗. A mul- ise o e a se Ais a pai (A, ) whe e :A→Nis a mapping. I m= (A, ) is a mul ise hen i s suppo is de ined as supp(m) = {x∈A| (x)>0}and i s size is de ined as Px∈A (x). A mul ise is emp y ( esp. ini e) i i s suppo is he emp y se ( esp. ini e). I m= (A, ) is a ini e mul ise o e A, hen i is deno ed by m=a (a1) 1a (a2) 2· · · a (ak) k, whe e supp(m) = {a1, . . . , ak}, and o each elemen ai, (ai) is called he mul iplici y o ai. An undi ec ed g aph Gis a pai G= (V, E) whe e Vis he se o e ices and Eis he se o edges, each one o which is an (uno de ed) pai o (di e en ) e ices. I {u, } ∈ E, we say ha uis adjacen o (and also is adjacen o u). The deg ee o ∈Vis he numbe o adjacen A ay Tissue-like P Sys ems 39 e ices o . In wha ollows we assume ha he eade is al eady amilia wi h he basic no ions and he e minology unde lying P sys ems3. Nex , we gi e a o maliza ion o he a ays conside ed in his pape . De ini ion 1. Gi en a ini e se V, called an alphabe o colo s, a pixel on Vis a pai hx, isuch ha x∈Z2and ∈V. An a ay on V,A, is a ini e se o pixels such ha i hx1, 1i,hx2, 2i ∈ Aand 16= 2 hen x16=x2. Finally, he suppo o he a ay Ais he se supp(A) = {x∈Z2| ∃ ∈Vsuch ha hx, i ∈ A}. Gi en an a ay Aand z∈Z2, we will deno e by A+z he se A+z={hx+z, i | hx, i ∈ A} Example 1. Le V={R, G, B}be he alphabe o colo s and A he a ay on V A={h(3,2), Ri,h(3,3), Gi,h(5,5), Gi}. Le us conside z= (−2,1) ∈Z2. The a ay A+zis {h(1,3), Ri,h(1,4), Gi,h(3,6), Gi}. I he e a e no con usion abou he alphabe o colo s, we will omi i and we alk abou pixels. As usual, we will deno e by V∗2 he se o all wo dimensional a ays o e V. 3 A ay Tissue-like P Sys ems In he ini ial de ini ion o he cell-like model o P sys ems [12], memb anes a e hi- e a chically a anged in a ee-like s uc u e. I s biological inspi a ion comes om he mo phology o cells, whe e small esicles a e su ounded by la ge ones. This biological s uc u e can be abs ac ed in o a ee-like g aph, whe e he oo ep e- sen s he skin o he cell (i.e. he ou e mos memb ane) and he lea es ep esen memb anes ha do no con ain any o he memb ane (elemen a y memb anes). Besides, wo nodes in he g aph a e connec ed i hey ep esen wo memb anes such ha one o hem con ains he o he one. In issue P sys ems, he ee-like memb ane s uc u e is eplaced by a gene al g aph. This model has wo biological inspi a ions (see [9, 10]): in e cellula com- munica ion and coope a ion be ween neu ons. The common ma hema ical model o hese wo mechanisms is a ne o p ocesso s dealing wi h symbols and commu- nica ing hese symbols along channels speci ied in ad ance. The communica ion among cells is based on sympo /an ipo ules, which we e in oduced as commu- nica ion ules o P sys ems in [11]. In sympo ules, objec s coope a e o a e se a memb ane oge he in he same di ec ion, whe eas in he case o an ipo ules, objec s esiding a bo h sides o he memb ane c oss i simul aneously bu in op- posi e di ec ions. Fo mally, a issue-like P sys em o deg ee q≥1 wi h inpu is a uple o he o m Π= (Γ, Σ, E, w1, . . . , wq,R, iΠ, oΠ), whe e 3We e e o [13] o basic in o ma ion in his a es, o [15] o a comp ehensi e p esen- a ion and he web si e [26] o he up- o-da e in o ma ion. 40 H.A. Ch is inal e al. 1. Γis a ini e alphabe , whose symbols will be called objec s, 2. Σ(⊂Γ) is he inpu alphabe , 3. E ⊆ Γ( he objec s in he en i onmen ), 4. w1, . . . , wqa e s ings o e Γ ep esen ing he mul ise s o objec s associa ed wi h he cells a he ini ial con igu a ion, 5. Ris a ini e se o communica ion ules o he ollowing o m: (i, u/ , j), o i, j ∈ {0,1,2, . . . , q}, i 6=j,u, ∈Γ∗, 6. iΠ∈ {0,1,2, . . . , q}, 7. oΠ∈ {0,1,2, . . . , q}. A issue-like P sys em o deg ee q≥1 can be seen as a se o qcells (each one consis ing o an elemen a y memb ane) labeled by 1,2, . . . , q. We will use 0 o e e o he label o he en i onmen , iΠand oΠdeno e he inpu egion and he ou pu egion (which can be he egion inside a cell o he en i onmen ) espec i ely. The s ings w1, . . . , wqdesc ibe he mul ise s o objec s placed in he qcells o he sys em. We in e p e ha E ⊆ Γis he se o objec s placed in he en i onmen , each one o hem a ailable in an a bi a y la ge amoun o copies. The communica ion ule (i, u/ , j) can be applied o e wo cells labeled by i and jsuch ha uis con ained in cell iand is con ained in cell j. The applica ion o his ule means ha he objec s o he mul ise s ep esen ed by uand a e in e changed be ween he wo cells. No e ha i ei he i= 0 o j= 0 hen he objec s a e in e changed be ween a cell and he en i onmen . Rules a e used as usual in he amewo k o memb ane compu ing, ha is, in a maximally pa allel way (a uni e sal clock is conside ed). In one s ep, each objec in a memb ane can only be used o one ule (non-de e minis ically chosen when he e a e se e al possibili ies), bu any objec which can pa icipa e in a ule o any o m mus do i , i.e, in each s ep we apply a maximal se o ules. In o de o unde s and how we can ob ain a compu a ion o one o hese P sys ems we p esen an example o hem: Conside us he ollowing issue-like P sys em Π0= (Γ, Σ, E, w1, w2,R, iΠ, oΠ) whe e 1. Γ={a, b, c, d, e}, 2. Σ=∅, 3. E={a, b, e}, 4. w1=a3e, w2=b2c d, 5. Ris he ollowing se o communica ion ules (a) (1, a/b, 2), (b) (2, c/b2,0), (c) (2, d/e2,0), (d) (1, e/λ, 0), 6. iΠ= 1, 7. oΠ= 0 A ay Tissue-like P Sys ems 41 We can obse e he ini ial con igu a ion o his sys em in he Figu e 1 (a). We ha e ou ules o apply. Fi s ule is (1, a/b, 2). The ule can be applied whene e an objec ’a’ is ounded in cell 1 and one copy o ’b’ appea in cell 2. This ule sends ’a’ o cell 2 and ’b’ om cell 2 o cell 1. Rule 2 is (2, c/b2,0) and implies ha when symbol ’c’ p esen in cell 2 hen his ule akes wo copies o ’b’ om en i onmen and sends ’c’ o he en i onmen (i.e. cell 0). Rule 3 is simila o ule 2. Rule 4, (1, e/λ, 0), sends he objec ’e’ o he en i onmen . So, as we ha e 3 copies o ’a’ and 1 copy o ’e’ in cell 1 and 2 copies o ’b’, one copy o ’c’ and wo copies o ’d’ appea in cell 2. Then, all he ules can be applied in a pa allel manne . Figu e 1(b) show he nex con igu a ion o he sys em a e applying he ules. I eade obse es he ini ial elemen s in he en i onmen o a issue-like P sys ems (in his case a, b), one can obse e he numbe o he copies o hese elemen s always appea as one, because we ha e an a bi a y la ge amoun o copies o hem. The only objec s changing i s numbe o copies in he en i onmen du ing a compu a ion a e he elemen s we e no appea he e ini ially. In his example, dhas wo copies because i is no an ini ial elemen o he en i onmen . Fig. 1. (a) Ini ial Con igu a ion o sys em Π0(b) Following Con igu a ion o Π0 (a) (b) Nex , we in oduce a modi ica ion o his model in o de o deal wi h a ays. An a ay issue-like P sys em o deg ee q≥1 wi h inpu is a uple o he o m Π= (Γ, V, E, w0, w1, . . . , wq, A1, . . . , Aq,R, iΠ, oΠ), whe e 1. Γis a ini e alphabe , whose symbols will be called objec s, 2. Vis he alphabe o colo s e i ying V∩Γ=∅. 3. Eis a ini e subse o a ays on V. 4. w0, w1, . . . , wqa e s ings o e Γ ep esen ing he mul ise s o objec s associ- a ed wi h he cells a he ini ial con igu a ion, 5. A1, . . . , Ana e a ays on V, placed on he co esponding cells a he ini ial con igu a ion. 6. Ris a ini e se o communica ion ules o he ollowing o m: (i, uiWi/ujWj, j), o i, j ∈ {0,1,2, . . . , q}, i 6=j,ui, uj∈Γ∗and Wi, Wj wo a ays on V. 42 H.A. Ch is inal e al. 7. iΠ∈ {0,1,2, . . . , q}is he inpu cell. 8. oΠ∈ {0,1,2, . . . , q}is he ou pu cell. In a simila way o issue-like P sys ems, an a ay issue-like P sys em o deg ee q≥1 can be seen as a se o qcells (each one consis ing o an elemen a y mem- b ane) labeled by 1,2, . . . , q. We will use 0 o e e o he label o he en i onmen , iΠand oΠdeno e he inpu egion and he ou pu egion (which can be he egion inside a cell o he en i onmen ) espec i ely. The s ings w1, . . . , wqdesc ibe he mul ise s o objec s placed in he qcells o he sys em. We in e p e ha w0is he se o objec s placed in he en i onmen , each one o hem a ailable in an a bi a y la ge amoun o copies. Fo each i∈ {1, . . . , q}, each Aiis an a ay placed in he cell iin he ini ial con igu a ion and Eis he se o a ays placed in he en i onmen , each one o hem a ailable in an a bi a y la ge amoun o copies. The emp y a ay ∅always belongs o E. Fo all he non-emp y copies, we will conside ha he le mos pixel o he bo om ow in he a ay co esponds o he coo dina es (0,0). Rules a e used as usual in he amewo k o memb ane compu ing, ha is, in a maximally pa allel way (a uni e sal clock is conside ed), ega dless i he en i onmen is in ol ed o no . In one s ep, each objec in a memb ane can only be used o one ule (non-de e minis ically chosen when he e a e se e al possibili ies), bu any objec which can pa icipa e in a ule o any o m mus do i , i.e, in each s ep we apply a maximal se o ules. The main di e ence wi h espec issue-like P sys ems is ela ed o he appli- ca ion o he ules. De ini ion 2. Le us conside wo index i, j such ha i6= 0 6=jand wo non- emp y a ays Wiand Wj. The communica ion ule (i, uiWi/ujWj, j)is applicable o e wo cells labeled by iand ji he ollowing condi ions a e e i ied: •uiis con ained in cell iand ujis con ained in cell j •The e exis wo a ays, Aiin he cell iand Ajin he cell jand wo pai s z1,z2∈Z2such ha (a) Wi+z1⊆Ai (b) Wj+z2⊆Aj (c) supp(Wi)∩supp(Wj)6=∅ (d) supp(Ai−(Wi+z1)) ∩supp(Wj+z1) = ∅ (e) supp(Aj−(Wj+z2)) ∩supp(Wi+z2) = ∅ The applica ion o his ule means ha he objec s o he mul ise s ep esen ed by uiand uja e in e changed be ween he wo cells. The a ays, Aiin he cell i and Ajin he cell ja e subs i u ed by A0 iand A0 j espec i ely, whe e A0 i= (Ai−(Wi+z1)) ∪(Wj+z1)A0 j= (Aj−(Wj+z2)) ∪(Wi+z2) No e ha i ei he Aio Ajis he emp y a ay, hen he ule is no applicable. A ay Tissue-like P Sys ems 43 Example 2. Le us suppose ha we ha e wo cells wi h labels 1 and 2 wi h he ol- lowing objec s and a ays, [ z2c3A1]1and [ d3k3bA2]2, wi h z2, c3, d3, k3, b objec s and A1,A2a ays o e {R, B, G} A1={h(1,1), Gi,h(1,2), Gi,h(2,2), Ri,h(2,3), Bi} A2={h(5,5), Gi,h(6,5), Gi,h(6,6), Gi} Le us conside he ule 1≡(1, z2W1/ d3k3W2,2) whe e W1and W2a e he a ays W1={h(7,0), Gi,h(7,1), Gi,h(8,1), Ri} W2={h(7,1), Gi,h(8,1), Gi} We will check ha 1is applicable o he cells 1 and 2 •z2is con ained in he cell 1 and d3k3is con ained in he cell 2. •Le us conside z1= (−6,1) ∈Z2and z2= (−2,4) ∈Z2 (a) W1+z1={h(1,1), Gi,h(1,2), Gi,h(2,2), Ri} ⊆ A1 (b) W2+z2={h(5,5), Gi,h(6,5), Gi} ⊆ A2 (c) supp(Wi)∩supp(Wj) = {((7,0),(7,1),(8,1)}∩{(7,1),(8,1)} 6=∅ (d) A1−(W1+z1) = {h(2,3), Bi} and W2+z1={h(1,2), Gi,h(2,2), Gi}. By conside ing hei suppo s we ha e supp(A1−(W1+z1)) = {(2,3)}and supp(W2+z1) = {(1,2),(2,2)}, hen supp(A1−(W1+z1)) ∩supp(W2+z1) = ∅ (e) A2−(W2+z2) = {h(6,6), Gi} and W1+z2={h(5,4), Gi,h(5,5), Gi, h(6,5), Ri}. By conside ing hei suppo s we ha e supp(A2−(W2+z2)) = {(6,6)}and supp(W1+z2) = {(6,4),(5,5),(6,5)}, hen supp(A2−(W2+z2)) ∩supp(W1+z2) = ∅ The ule 1is applicable o he cells 1 and 2, and he esul o applying he ule is [ d3k3c3A0 1]1and [ z2bA0 2]2whe e A0 1= (A1−(W1+z1)) ∪(W2+z1) ={h(2,3), Bi,h(1,2), Gi,h(2,2), Gi} A0 2= (A2−(W2+z2)) ∪(W1+z2) ={h(6,6), Gi,h(5,4), Gi,h(5,5), Gi,h(6,5), Ri} Nex , we de ine he applicabili y o a ule i one o he egions in ol ed is he en i onmen and he a ays a e no emp y. De ini ion 3. Le us conside an index i6= 0 and wo non-emp y a ays Wiand W0. The communica ion ule (i, uiWi/u0W0,0) is applicable o e wo cells labeled by iand 0i he ollowing condi ions a e e i ied: •uiis con ained in cell iand u0is con ained in cell 0 •The e exis an a ay Aiin he cell iand wo pai s zi,z0∈Z2such ha 44 H.A. Ch is inal e al. (a) Wi+zi⊆Ai (b) supp(Wi+zi)∩supp(W0+z0)6=∅ (c) supp(Ai−(Wi+zi)) ∩supp(W0+z0) = ∅ The applica ion o his ule means ha he objec s o he mul ise s ep esen ed by uiis emo ed om he cell iand subs i u ed by he mul ise ep esen ed by u0. The a ays, Aiin he cell iis subs i u ed by A0 iwhe e A0 i= (Ai−(Wi+zi)) ∪(W0+z0) Example 3. Le us suppose he cell 1 wi h he ollowing objec s and a ays, [z3 2c3A1]1and A1 he a ay o e {R, B, G} A1={ h(5,2), Ri,h(6,2), Bi,h(7,2), Gi,h(8,2), Bi} h(9,2), Ri,h(6,1), Bi,h(8,1), Bi} Le us conside he ule 1≡(1, z2W1/ d2W0,0) whe e W1and W0a e he a ays Wi={h(3,3), Bi,h(3,4), Bi} W0={h(0,0), Ri} Le us suppose ha d2belongs o w0and W0belongs o E. In o de o p o e ha 1is applicable, i s we check ha z2is con ained in he cell 1 and, acco ding o he p e ious claim, d2is con ained in he en i onmen . We ha e se e al possibili ies o choose he pai zi,z0. The di e en choices show he no de e minism o he sys em. We also apply he ule wi h maximal pa allelism. In his case we ake he ollowing op ion: he pai zi,z0wi h zi= (3,−2) and z0= (6,1) o he i s applica ion o he ule and he pai z∗ i,z∗ 0wi h z∗ i= (5,−2) and z∗ 0= (8,2) o he second applica ion. (a) W1+zi={h(6,1), Bi,h(6,2), Bi} ⊆ A1 (a) W1+z∗ i={h(8,1), Bi,h(8,2), Bi} ⊆ A1 (b) supp(Wi+zi)∩supp(W0+z0) = {(6,1),(6,2)}∩{(6,1)} 6=∅ (b) supp(Wi+z∗ i)∩supp(W0+z∗ 0) = {(8,1),(8,2)} ∩ {(8,1)} 6=∅ (c) supp(Ai−(Wi+zi)) ∩supp(W0+z0) = {(5,2),(7,2),(8,2),(9,2),(8,1)} ∩ {(6,1)}=∅ (c) supp(Ai−(Wi+zi)) ∩supp(W0+z0) = {(5,2),(6,2)(7,2),(9,2),(861)} ∩ {(8,2)}=∅ The ule 1is applicable and he esul o applying he ule wice is [d2 2z2c3A0 1]1 whe e A0 1= (A1−(W1+z1)−(W1+z1)∗)∪(A0+z0)∪(A0+z∗ 0) ={h(5,2), Ri,h(7,2), Gi,h(9,2), Ri,h(6,1), Ri,h(8,2), Ri} Finally, le us conside he case in which one o he egions in ol ed in he ule is he en i onmen and he a ay conside ed in he en i onmen is he emp y a ay. A ay Tissue-like P Sys ems 45 De ini ion 4. The communica ion ule (i, uiWi/u0,0) is applicable o e wo cells labeled by iand 0i he ollowing condi ions a e e i ied: •uiis con ained in cell iand u0is con ained in cell 0 •The e exis an a ay Aiin he cell iand a pai zi∈Z2such ha Wi+zi⊆Ai The applica ion o his ule means ha he objec s o he mul ise s ep esen ed by uiis emo ed om he cell iand subs i u ed by he mul ise ep esen ed by u0. The a ay Aiin he cell iis subs i u ed by A0 iwhe e A0 i= (Ai−(Wi+zi)) Example 4. Le us suppose he cell 1 wi h he ollowing objec s and a ays, [z3 2c3A1]1and A1 he a ay o e {R, B, G} A1={ h(5,2), Ri,h(6,2), Bi,h(7,2), Gi,h(8,2), Bi} h(9,2), Ri,h(6,1), Bi,h(8,1), Bi} Le us conside he ule 1≡(1, W1/ d, 0) whe e W1is he a ay Wi= {h(3,3), Bi}. Le us suppose ha dbelongs o w0. In his case, we ha e ou possibili ies o choose zi. They a e (3,−2),(3 −1),(5,−2),(5,−1). I is i ial o check ha he ule is applicable. I will be applied wi h maximal pa allelism, so he ule will be applied ou imes and he esul o applying he ule wice is [d4z3 2c3A0 1]1whe e A0 1={h(5,2), Ri,h(7,2), Gi,h(9,2), Ri} 4 Using A ay Tissue-like P Sys ems in Digi al Image In digi al image e minology, gi en a ini e alphabe o colo s Vand a blank objec # such ha # 6∈ V, a wo-dimensional (2D) digi al image is a pai (S, AS), whe e S⊂N2and AS:S→V∪ {#}is an a ay on S. The size o V,|V|, is he numbe o i s elemen s. Mo eo e , we can in oduce an o de o colo s in an image. We de ine he o de ed alphabe associa e o an image like a pai (V, <V), whe e <Vis an o de in he se V. The de ini ion o pixel is associa ed wi h a ays, i.e., wi h equi alence classes o a ays. In his way, i makes sense ha we s udy he adjoining ela ion o wo pixels o gene ic posi ions (i, j) and (i0, j0) by explo ing he ela ion among hese gene ic coo dina es. Fo he sake o simplici y, we w i e he pixel <(i, j), a > as aij. The e exis s wo na u al way o de ining adjacen pixels: 4-adjacency and 8-adjacency [17, 18]. In he i s case, gi en a pixel Kij, he lis o adjacen pixels o his is {Kij−1, Kij+1, Ki−1j, Ki+1j}i.e.; he adjacen pixels o any pixel Kij a e jus no h, sou h, wes , eas o his (no in he diagonal espec o conside ed pixel). In he second we conside he pixel Kij (whe e K=B∨K=W), he lis o adjacen pixels o his is {Ki−1j−1, Ki−1j, Ki−1j+1, Kij−1, Kij+1, Ki+1j−1, Ki+1j, Ki+1j+1}i.e.; he adjacen pixels o a any pixel Kij a e jus up, down, igh and le o his and, mo eo e , we conside he diagonal objec s.