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.