Image Segmen a ion using Tissue-like P Sys ems
wi h Mul iple Auxilia y Cells
Ra´ul Reina-Molina, Ja ie Ca ne o, Daniel D´ıaz-Pe nil
1Resea ch G oup on Compu a ional Topology and Applied Ma hema ics
Depa men o Applied Ma hema ics I
Uni e si y o Se ille
[email p o ec ed], [email p o ec ed], [email p o ec ed]
Abs ac . We p esen a solu ion o he segmen a ion p oblem using a
dis ibu ed, non de e minis ic and pa allel compu a ional model known
as issue-like P sys ems. We p esen a new echnique o segmen images
wi h espec o he algo i hm appea ed in [1], whe e we use mul iple
auxilia y cells and no only one.
1 In oduc ion
Memb ane sys ems a e dis ibu ed and pa allel compu ing de ices p ocessing
mul ise s o objec s in compa men s delimi ed by memb anes. Compu a ion is
ca ied ou by applying gi en ules o e e y memb ane con en , usually in a
maximal non-de e minis ic way, al hough o he seman ics a e being explo ed.
In ou wo k, we p esen a amily o issue-like P sys ems ( lP sys ems) which
sol es he Segmen a ion P oblem in Digi al Image y using mul iple cells. Seg-
men a ion in compu e ision (see [4]) 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). Image segmen a ion is yp-
ically used o loca e objec s and bounda ies (lines, cu es, e c.). 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, one can ind se e al a emp s o b idging p oblems om
Digi al Image y wi h Memb ane Compu ing. We can ci e he wo ks by K.G.
Sub amanian e al. [?] o ecen ly some p oblems om Digi al Image y ha e
been sol ed in he amewo k o Memb ane Compu ing (see [3]).
2 Image P ocessing: Segmen a ion P oblem
The m-D Segmen a ion P oblem wi h k auxilia y cells (mDSP-kC) can be se led
as ollows: gi en an m-D digi al image, Io size nm, o de e mine he edge pixels
o his image using kauxilia y cells.
The usual de ini ion o edge pixel p esen s p oblems om a p ac ical poin
o iew wi h he noise and he deg ada ion o colou s, because we ake as bo de
poin s a lo o pixels ha a e no edge pixels om a p ac ical poin o iew.
25
(a) Ini ial con en (b) Con en o second
cell
(c) Con en o second cell
a e cleaning s age
(d) Con en o second
cell be o e edge de ec ion
s age
(e) Con en o second cell
a e edge de ec ion
( ) Con en o i s cell
once hal ing condi ion is
eached
Fig. 1: Full segmen a ion p ocess zoomed.
Nex , we will show ha 2DSP-kC can be sol ed in linea ime (in he numbe
o pixels o he image) by a amily o lP sys ems (see Fig.1). To his aim, le
us cons uc a amily Π={Π(n, k):n, k ∈N}whe e each sys em o he amily
will p ocess e e y ins ance uo he p oblem (a 2D image Iwi h n2pixels)
and using kauxilia y cells. Mo e o mally, we de ine he size o he ins ance as
s(u)="n, k#, whe e "x, y#=(x+y)(x+y+ 1)/2+xis he G¨odel mapping. In
o de o p o ide a sui able encoding o his ins ances in o he sys ems, we will
use he objec s I(ij)ij , wi h 1 ≤i, j ≤n, o ep esen he pixels o he g aph,
and we will p o ide cod(u) as he ini ial mul ise o he sys em, whe e cod(u)
is he mul ise o objec s I(ij)!
ij o 1 ≤i, j ≤n.
Then, gi en an ins ance uo he 2DSP-kC p oblem, he sys em Π(s(u))
wi h inpu cod(u) gi e a solu ion o his p oblem, implemen ed in he ollowing
s ages:
–Cleaning noise.
–Homogenize colou s using a gene al h esholding in colou space.
–Segmen ing image p ocess.
The amily Π={Π(n, k):n, k ∈N}o lP sys ems o deg ee k+1 is de ined
as ollows: o each n, k ∈N,
Π(n, k) = (Γ,Σ,E,w
1, . . . , wk+1,R,i
Π,o
Π),
de ined as ollows:
–Γ=Σ∪{aija!!
ij,¯aij,A
ij,A
!
ij,A
!!
ij,¯
Aij :1≤i, j ≤n, a ∈C} ∪{∗ij,∗ji :i=
0,n+1,0≤j≤n+1},Σ={a!
ij :1≤i, j ≤n, a ∈C},E=Γ−Σ,
26
–w1=∗ij,∗ji wi h i=0,n+1,0≤j≤n+ 1, w2=· · · =wk+2 =T!n2/k",
–Ris he ollowing se o communica ion ules:
•(1,a
#
ij/a8
ijAij,0) o 0 ≤i, j ≤n+ 1 and a∈C∪{∗}
•
1,
ci−1j−1di−1jei−1j+1
bij−1Aij ij+1
oi+1j−1hi+1jgi+1j+1
/ T, 

o 1 ≤i, j ≤n,a, b, c, d, e, , g, h, o ∈C∪{∗}and 2 ≤ ≤k+1 indica ing
an auxilia y wo king cell.
These ules a e used o gene a e new elemen s. The P sys em uses hese
elemen s o wo k wi h he noise o ou image.
•
 ,
ci−1j−1di−1jei−1j+1
bij−1Aij ij+1
oi+1j−1hi+1jgi+1j+1
/z
"
ij ,0
,
 ,
ci−1j−1di−1jei−1j+1
bij−1Aij ij+1
oi+1j−1hi+1jgi+1j+1
/a
"
ij ,0

o 1 ≤i, j ≤n,a, b, c, d, e, , g, h, o ∈C∪{∗}. We ake µas he numbe
o pixels adyacen s o he ij possi ion wi h colou s in Cand ∗= 0. Then,
a =(b+c+d+e+ +g+h+o)/µ and z= max{s∈C:s≤a }and
|a−a |≤ρ1, whe e ρ1∈(0,+∞).
This se o ules is used o de ec he noise and co ec i wi h he a e age
o colou s o i s adjacen pixels. We ind he e a local h esholding (wi h
espec o he colou s) wi h p ede ined h eshold ρ1. The use o ∗g an s
a simple wo king o pixels in he bo de o I.
•( , b#
ij/A#
ij,0) o 1 ≤i, j ≤n,ν=(|C|/ρ2), l=0,1,2,...,ρ2. I b∈C
hen a∈C(a<b≤a+(ν−1) and a=ν·l) o (b=a=ν·l) and, i
b=∗ hen A=∗.
These ules a e used o disc e ize he colou s di iding he se o colou s in
ρ2subse s o leng h ν. We ind he e a gene al h esholding (wi h espec
o he colou s) wi h p ede ined h eshold ν.
•( , A#
ij/T, 1) o a∈C,0≤i, j ≤n+ 1 and 2 ≤ ≤k+ 1.
This se o ules a e used o send ou ans o med image o he cell 1.
Now, he objec s A#
ij codi y he pixels o ou image.
•(1,A
#
ij/A##
ija8
ij,0) o a∈C∪{∗}and 0 ≤i, j ≤n+ 1.
The P sys em uses hese ules o gene a e an numbe o copies o ou
image o do he segmen a ion p ocess in he cells 2, . . . , k and k+ 1.
•
0,
ci−1j−1di−1jei−1j+1
bij−1A##
ij ij+1
ii+1j−1hi+1jgi+1j+1
/ T, 

o 1 ≤i, j ≤nand a, b, c, d, e, , g, h, i ∈C∪{∗}.
These ules a e de ined o send o he emainde o cells he new objec s.
•( , A##
ijbkl/Aij,0), o 1 ≤i, j, k, l ≤n,(i, j),(k, l) adjacen pixels, a, b ∈C
and a<b.
These ules a e used o ma k edge pixels. When we ha e wo adjacen
pixels wi h di e en colou , we ake as edge pixel he pixel wi h less
associa ed colou . In ac , he P sys em b ings om he en i onmen an
objec Aij (in his case).
•( , Aij/T, 1) o a∈Cand 1 ≤i, j ≤n.
These ules send o he cell 1 he ou pu objec s.
27
–iΠ=oΠ= 1.
A li le s udy o he complexi y aspec s o his solu ion is gi en by he Fig.2
showing his is an e icien algo i hm om a heo e ical poin o iew.
mDSP-kC P oblem
Complexi y
Numbe o s eps o compu a ion 9
Resou ces needed
Size o he alphabe 8n2+4n+5
Ini ial numbe o cells k+1
Ini ial numbe o objec s (n+ 2)2
Numbe o ules O(n2
·h9
·k)
Uppe bound o he leng h o he ules 10
Fig. 2: Complexi y aspec s, whe e he size o he inpu da a is O(n2), |C| =his
he numbe o colou s o he image and kis he numbe o wo king cells.
3 Final Rema ks
We ha e designed a amily o issue-like P sys ems o do a segmen a ion o a
digi al image. Wi h his algo i hm we wo k wi h mul iple cells, so we can ob ain
a bigge pa alleliza ion wi h espec o he design p esen ed in [1].
Acknowledgemen
DDP acknowledges he suppo o he p ojec s TIN2008-04487-E and TIN-2009-
13192 o he Minis e io de Ciencia e Inno aci´on o Spain and he suppo o he
P ojec o Excellence o he Jun a de Andaluc´ıa, g an P08-TIC-04200.
Re e ences
1. Ca ne o, J., D´ıaz-Pe nil, D., Molina-Ab il, H., Real, P.: Image segmen a ion in-
spi ed by cellula models using ha dwa e p og amming. Image-A 1(3), 143–150
(2010)
2. Ce e chi, R., G ama o ici, R., Jonoska, N., Sub amanian, K.G.: Tissue-like P sys-
ems wi h ac i e memb anes o pic u e gene a ion. Fundamen a In o ma icae
56(4), 311–328 (2003)
3. D´ıaz-Pe nil, D., Gu i´e ez-Na anjo, M.A., Molina-Ab il, H., Real, P.: Designing
a new so wa e ool o digi al image y based on P sys ems. Na u al Compu ing,
pages 1–6, 2011.
4. Shapi o, L.G., S ockman, G.C.: Compu e Vision. P en ice Hall PTR, Uppe Sad-
dle Ri e , NJ, USA (2001)
28