Implementation of non-linear templates using a decomposition technique by a 0.5 /spl mu/m CMOS CNN universal chip

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