ISCAS
2000
-
IEEE
in e na ional Symposium on Ci cui s and Sys ems, May
28-31,
2000,
Gene a, Swi ze land
Implemen a ion
o
Non-Linea Templa es using a Decomposi ion Technique
by
a
0.5pm CMOS CNN Uni e sal Chip.
G.
Liiihn,
P
Foldesy,
A.
Rod iguez-Vhzquez,
S.
Espejo and
R.
Dominguez-Cas o.
Ins i u o
de
Mic oelec hica
de
Se illa
-
CNM-CSIC
Edi icio CICA-CNM, C/Ta ia s/n,
41012-
Se illa, SPAIN
Phone:
+34
95
4239923, Fax:
+34
95
4231832, E-mail: [email p o ec ed]
ABSTRACT?
This pape demons a es he p ocessing capabili ies o a
ecen ly designed Analog P og ammable A ay P ocesso
[l].
This new p o o ype, ha
is
called CNNUC3, ollows he Cellula
Neu al Ne wo k Uni e sal Machine compu ing pa adigm
[2],
[3],
[4].
Due o i s e y ad anced ea u es and algo i hmic capa-
bili ies, his chip has been demons a ed o be able o pe o m no
only linea empla es execu ions, bu also o be e y adequa e o
he implemen a ion o non-linea empla es by using a decompo-
si ion me hod. This pape ocus on he applica ion examples
o
he execu ion o non-linea empla es wi h he CNNUC3 p o o-
ype. A b ie desc ip ion
o
he heo e ical backg ound is also
p esen ed in he pape .
1.
INTRODUCTION.
Cellula Neu al Ne wo ks (CNNs)
[2]
exhibi s ou s anding
image p ocessing capabili ies. When conside ing he CNN pa a-
digm, linea and nonlinea ope a ions
(so
called empla es) can
be dis inguished. The linea ope a ions a e mainly linea con o-
lu ions among he pixel alues, ega dless he alue o he pixel
ha
is
being p ocessed. On he o he hand, he nonlinea em-
pla es p esen he p ope y o changing
o
adap ing he s eng h
o
he connec ions be ween di e en cells (weigh s) acco ding o
he cu en alue o he pixels unde ope a ion.
These nonlinea unc ions play an impo an
ole
in image
p ocessing. Howe e , he nowadays a ailable CNN implemen a-
ions
a e
no capable
o
implemen such ope a ions because o
he ha dwa e di icul y
o
implemen ing, and mo eo e make
hem p og ammable, non-linea i ies. To sol e his p oblem some
algo i hmic me hods ha e been de eloped
[5].
These algo i hms
use
simple nonlinea unc ions and ex ensions o he o iginal
CNN pa adigm. Fo una ely, hese ex ensions a e de ined in he
CNN Uni e sal Machine a chi ec u e
[3],
[4],
which comp ises
he g ay-scale
(o
analog) and bina y (o logic) ope a ions wi h
dis ibu ed in e nal memo ies.
The CNNUC3 p o o ype
[I]
is, by a , he mos complex
CNN implemen a ion epo ed
up
o now. This is he i s
high-densi y CNN chip ha can p ocess and p o ide g ay-scale
images also con aining many ad anced ea u es poin ing
owa ds he CNNUM. Among
hese
ex ensions we could empha-
size:
The algo i hmic capabili y o he chip is enough o un algo-
i hms wi h dozens
o
ope a ions wi hou ex e nal code
o
da a mo emen .
I can s o e ou g ay-scale and ou bina y images.
I can sum o sub ac g ay-scale images.
I has he capabili y o selec ing which cells a e going
o
be
p ocessed
(so
called eezing map).
I is possible o combine wo bina y images by any logic
ope a ion (such as logic “and”,
“o ”,
o ha pu pose,
i
con-
ains
a
ully
p og ammable
wo inpu digi al de ice wi hin
each cell).
The pape is o ganized as ollows; Sec ion
2
es ablishes a
heo e ical backg ound abou he echnique o non-linea em-
pla es decomposi ion. Sec ion
3
desc ibes some applica ions
examples. Some addi ional commen s a e p o ided in Sec ion
4.
Finally, he conclusions a e p esen ed in Sec ion
5.
2.
DECOMPOSITION
OF
NON-LINEAR
TEMPLATES.
Implemen ing a non-linea empla e by decomposing i in o
he execu ion o se e al linea
ones
is no a new p oblem o em-
pla es enginee s. In his sec ion we will b ie ly desc ibe he
me hod epo ed in
[5]
in o de o accomplish his uans o ma-
ion.
The e o e, we will deal wi h he decomposi ion o
3
x
3
empla es whe e only he
B
e m is a non-linea unc ion. Fu -
he mo e, we will assume ha he non-linea i ies appea ing on
he eed o wa d e m a c piecewise linea unc ions and ha he
inpu image is ime in a ian .
Wi h hese assump ions, he dynamic e olu ion o a cell
(conside ing he
FSR
model
[6])
is gi en by:
.
This
wo k
has
been pa ially
unded
by
ONR-NlCOP
N68
17
1
-98-C-9004
and DICTAM
IST-1999- 19007.
0-7803-5482-6/99/$10.00 02000
IEEE
11-40
1
The p oblem
is
how o subs i u e he non-linea i ies associa ed
Le
us
suppose ha he non-linea piecewise unc ion can be
o he
B
e m by using
a
sequence o linea empla es.
exp essed as:
Y(5)
=
Y(a
’
+
P
’
uk )
(3)
whe e
CI
and
P
a e eal numbe s, and ha he linea egions
a e de ined by
a
se o
m
b eaking poin s
{
c2,
...
,
,}.
In ha
case, ha
is
also he mos common in p ac ice, he non-linea em-
pla e can be decomposed in o a sequence o linea empla e execu-
ions. The algo i hm ha is exhaus i ely desc ibed and examined
in
[5],
uns as ollows:
The p ocess s a s by selec ing
he
i s linea egion o he
non-linea unc ion. Le
us
call
R,
his egion ha is de ined
by he b eaking poin s
c1
,
c2.
The nex s ep
is
o selec which a e he cells belonging o ha
egion. This calcula ion is ealized by wo empla es execu-
ions and
a
logic ope a ion (all o hem a e done on-chip).
Wi h he i s empla e, he
so
called h eshold empla e, we
d i e o black
all
hose cells ha ing
5
>
c1
,
while wi h he
second one, he
so
called in e se h eshold, we d i e o black
all
hose cells ha ing
5
<
2.
Finally
a
logic AND ope a ion
o
bo h
esul s
will selec hose pixels whe e
k1
<
5
<
2
*.
Equa ions
(4),
(5),
show he h eshold and he in e se
h eshold empla e .
A=[;;i
000
B=[:-;i
400,
2=52
(5)
The non-selec ed cells a e “ ozen”, by using he eezing
mask p o ided by he chip, while in he selec ed ones he co -
esponding con ibu ion o he s a e equa ion is e alua ed and
s o ed
as
a
“bias map” ha will be upda ed (o no ) in he nex
i e a ion by adding he new esul o he one ha was p e i-
ously s o ed. The upda ing law o he s a e a iables o he
cells ha a e selec ed mus be gi en by he equa ion o
a
s aigh line (due o he ac ha
“(5)
is
linea be ween each
wo b eaking poin s) c ossing he poin s and
2.
All he
poin s belonging o his line sa is y:
$.
Keep in mind ha
5
=
c
.
uij
+
p
ukl
and he subindex
kl
deno es
he cell’ neighbo s.
ii.
These
a e he
FSR
e sion
o
he empla es.
In
o de o ge he o iginal
Chua-Yang empla e inc ease by one he sel - eedback e m.
And om he
CNN
heo y, i can be demons a ed ha his
ela ionship
is
ob ained
i
he ollowing empla e is exe-
cu ed*$:
A=[;:i
000
B=[:
k.(3
k;ai
0 0
z
=
y(41)-k.51
(7)
whe e,
The p ocess con inues o he nex linea egion.
Finally, a empla e execu ion is needed. In his empla e he
eedback e m
is
he same as in he’o iginal one de ined in
(I),
he eed o wa d e m is se o ze o (modi ied
B
empla e),
since
i
has been al eady calcula ed, and he o se e m is he
addi ion o he o iginal one
z
,
and he
“bins
map”
ha
is
s o ed in some memo y on he cell.
3.
APPLICATION EXAMPLES.
3.1
Absolu e Value Calcula ion.
In his subsec ion we conside only pixel-wise ans o ma-
ions,
o
wi h o he wo ds,
B
empla es wi h he size o
1x1
As
a
consequence
o
missing neighbo connec ions he decom-
posi ion me hod can be simpli ied, a oiding he accumula ion o
he pa ial esul s. Mo eo e , he selec ion o cells belonging a
gi en in e al
is
done by he wo h eshold empla es, which
also
con ain only cen al elemen s (whe e
c
=
1
,
p
=
0
and
=
0):
000
000
A=[;mJ
B=[;;i
z=-51
(9)
As an example we show how he absolu e alue can be calcu-
la ed. The used ope a ion and empla e
is
shown in Fig..
A
Fig. 1:
The absolu e alue calcula ion empla e
Since he e a e wo in e als, he posi i e and nega i e alued
cells, he e a e wo cell maps. The i s one con ains black pixels a
he cell posi ions whe e he inpu image con ained nega i e alues
and he second
is
he opposi e
o
i .
As
a special case, he i s
$$.
The posi ion o he
P
coe icien mus be o a ed in o de
o
pe o m
his ope a ion o each o he neighbo s
o
he cell appea ing as a non-linea
connec ion on he o iginal
B
empla e. The e o e, each linea egion could
equi e up o
16
empla es and 8 logic ope a ions
o
be selec ed, 8 em-
pla es o upda e he s a e a iable, and 8 empla es o pe o m he addi ion
o he esul s, ha
is
32
empla es and
8
logic ope a ions.
11-402
ans o ma ion
is
equal o in e sion and he second one p ac ically
can be a oided (since i le s he cells unchanged a hei o iginal
alues). Fig.. shows he esul o he execu ion
o
he absolu e
alue calcula ion.
(a)
Inpu
(b)
Absolu e alue
Fig.
2:
The absolu e alue calcula ion.
3.2
G adien calcula ion
h esholded g adien .
The second example
is
he calcula ion o he g adien and he
The g adien empla e is de ined as ollows:
--
A
=
I ]
El
=
( )
Y( )
Y(<)
0
Y(S)
Y( j
y;Lj-ug
-2
2
Y(<)
Y(S)
Y(S)
z=o
Fig.
3:
The g adien empla e.
The empla e con ains eigh neighbo ing connec ions ha can
belong o wo in e als. A e he usage o he decomposi ion
me hod he o al numbe o linea empla e execu ions and h esh-
old
unc ions
is
32.
The h esholded g adien ope a ion di e s om he g adien
calcula ions in he alues o he modi ied
B
empla e.
000
000
A
=
[;
,
B
=
[;
;
j
=
Zjh eshold
(10)
Execu ion examples can be seen in Fig.. and in Fig..
3.3
Con ou De ec ion on G ay-Scale Images.
The hi d example is he con ou de ec ion. The ope a ion is
de ined
in
such
a
way ha he ou pu con ains black pixel a he cell
(a) Inpu
Fig.
4:
The g adien calcula ion.
I
1
(b)
G adien
(a) Inpu
(b)
Th esholded g adien
Fig.
5:
The h esholded g adien ex ac ion.
posi ion whe e he inpu alue
o
he cell is la ge han some o he
neighbo s by
a
ce ain amoun
(0.1
in he case
o
Fig.).
Fig. 6:
The con ou De ec ion Templa e.
Bo h he numbe
o
used mask gene a ing empla es and ans-
o ma ion empla es a e
16
?++.
The esul o he execu ion o his
sequence o a g ay scale image can be obse ed in Fig..
(a)
Inpu
(b)
De ec ed con ou
Fig.
7:
Con ou De ec ion on G ay-Scale Images.
3.4 Local Maxima
This example shows how he local
(3
x
3
)
maxima can be
ex ac ed. The cell's ou pu is black
(o
con ains
a
local maxima)
i he cell's inpu alue is la ge by ce ain amoun
(0.05
in he
case o he empla e in Fig.) han any
o
he neighbo s.
The decomposi ion is simila o he p e ious one, bu in his
case
all
o he pa ial esul s should p o ide
a
posi i e de ec ion,
while he con ou ope a ion equi ed only one posi i e de ec ion.
The decomposed sequence con ains
8
empla es. An example o
he applica ion
o
his empla e can be seen in Fig..
.
See ha he numbe o equi ed empla es is no 64 as i should
co -
espond o he case
o
ha ing 8 non-linea connec ions.
This
is explained
by he ac ha he linea egions ha e
an
in ini e
o
ze o slope, and
so,
he
linea ans o ma ion de ined by
(7)
is
no needed.
11-403
Fig.
8:
The Local Maxima Templa e
(a) Inpu
(b)
Local maxima
Fig.
9:
The local maxima de ec ion.
4.
ADDITIONAL COMMENTS.
In his sec ion we men ion some addi ional ideas abou he
decomposi ion, which educe he numbe o he equi ed ope a-
ions. This educ ion a ises om some special unc ions ha a e
a ailable in he CNNUC3 chip.
The i s example shows ha when he numbe o in e als
is
only wo, he “ eezing” masks a e he opposi e
o
each o he .
This
implies ha he
calcula ion
o
he second mask by em-
pla e execu ion can be eplaced by a logic ope a ion.
The hi d and ou h examples demons a e ha he e a e spe-
cial cases when he gene al me hod can be modi ied in o de
o ge a mo e e icien decomposi ion. Specially, when he
pa ial esul s con ains only black o whi e pixels.
In hese cases, he gene a ed in e al maps con ain all he
in o ma ion abou he pa ial esul s. Tha means ha he lin-
ea ans o ma ion ( he hi d s ep
o
he algo i hm in Sec ion
2)
is
no needed. Mo eo e , when he inal esul
is
he logic
sum (ope a ion OR)
o
logic p oduc (ope a ion AND) o he
pa ial ou pu s, he inal esul can be accumula ed by he
Local Logic Uni (LLU) in a Local Logic Memo y (LLM)
ins ead o by using he g ay-scale accumula ion p ocess in an
analog memo y.
4.1
P ocessing, P ecision, and Time
Since we use an VLSI analog implemen a ion, p ecision and
p ocessing ime a e impo an issues ha should be men ioned.
The global p ecision o he chip is sligh ly below 8 bi s, ha
e e s o he spa ial uni o mi y. On he o he hand, he nonlin-
ea - o-linea ans o ma ion
o
a piecewise unc ion con aining
abou
8-10
b eaking poin s
is
possible. Fu he mo e, a non-linea
unc ion no belonging o he piecewise class, could also be imple-
men ed i he e exis a good enough piecewise app oxima ion
(con aining up o
10
b eaking poin s).
The p ocessing ime o a single empla e execu ion and a logic
ope a ion a e 20ps (including in e nal calib a ing phases and he
se ling ime o changing he empla e coe icien s) and
Ips
espec i ely.
Fig.
10:
Piecewise app oxima ion o a gene ic unc ion
5.
CONCLUSIONS.
The execu ions o non-linea empla es de ines an impo an
applica ion a ea in he ield o image p ocessing. Howe e , p e i-
ous
VLSI CNNs implemen a ions did no p o ide o he empla e
enginee s su icien ly accu a e and e sa ile ea u es o
mxp
he
nonlinea - o-linea exis ing algo i hms. We ha e p esen ed expe -
imen al e idences in his pape abou how
a
wide se
o
non-].inea
empla es can be execu ed wi h a easonable accu acy wi h a
ecen ly designed CNN p o o ype, he
so
called CNNUC3. We
ha e also b ie ly ou lined a gene al decomposi ion me hod o
implemen ing non-linea - o-linea empla e ans o ma ions.
6.
REFERENCES.
[I]
G.
Liiibn, P. Foldesy,
S.
Espejo, R. Dom’nguez-Cas o and A.
Rod iguez-Vizquez.
“
A 0.5mm CMOS 106 T ansis o s Ana-
log P og ammable A ay P ocesso
o
Real-Time Image P o-
cessing’’,
P oc.
o
he
25‘h
Eu opean
Solid-s a e Ci cui s
Con e ence,
pp.
358-36,
Duisbu g-Ge many, Sep .
1999.
[2] L.O. Chua and
L.
Yang. “Cellula Neu al Ne wo ks: Theo y”,
IEEE T ans. Ci cui s and Sys ems, ol. 35, pp. 1257-1272,
Oc . 1988.
[3] T. Roska and L.O. Chua.
“The
CNN Uni e sal Machine: An
Analogic A ay Compu e ”, IEEE T ans. Ci cui s and Sys-
ems
11,
Vol. 40, pp 163-173, Ma ch 1993.
[4] L.O. Chua and T. Roska. “The CNN Pa adigm”,
IEEE
T ans.
Ci cui s and Sys ems
I,
~01.40, pp.147-156, Ma ch 1996.
[5] L. Kek and A. Za andy. “Implemen a ion
o
La ge Neighbo -
hood Non-Linea Templa es on he CNN Uni e sal
Machine”.
In e na ional Jou nal o Ci cui Theo y and Appli-
ca ions,
o1.26, No. 6, pp. 551-566,
1998.
[6]
S.
Espejo,
R.
Ca mona,
R.
Dom’nguez-Cas o and A.
Rod iguez-Vbzquez: “A VLSI-O ien ed Con inuous-Time
CNN Model”.
In e na ional Jou nal
o
Ci cui Theo y and
Applica ions.
Vol24, No. 3, pp 341-356, May-June 1996.
11-404