Realization of non-linear templates using the CNNUC3 prototype

2000 STH IEEE International Workshop on Cellular Neural Networks and neir Applications Proceedings Realization of Non-Linear Templates using the CNNUC3 Prototype G. LiAh, I! Fokiesy, A. Rodriguez-V6zque.c S. Espejo and R. Lbmhguez-Casm Instituto de Miaoelectr6nica de Sevilla - CNM-CSIC Edifcio CICA-CNM. ClIama dn. 41012- Sevilla, SPAIN Phone: +34 95 4239923, Fax: +34 95 4231832, E-mail: [email protected] ABSTRACC This paper demonstrates the processing capabilities of a recently designed Analag Programmable Array Processor chip 111 - CNNUC3 - which follows the Cellular Neural Network Universal Machine computing paradigm [2][3][4]. Due to its very advancedfeatures andalgorithmic capabilities, this chip has been demonstrated to be able to perform not only linear templates executions, but alro to be very adequate for the implementation of non-linear templates by using a decomposition method This paper focus on the application examples of the execution of non-linear templates with the CNNUC3 prototype. A brief description of the theoretical background is also presented in the paper. I. INTRODUCTION? Cellular Neural Networks (CNNs) [2] exhibits outstanding image processing capabilities. They are capable to realize linear as well as nonlinear operations by using either linear or non-linear templates. Linear templates correspond to the case where interaction strengths (weights) are independent of signal values. Non-linear templates correspond to the case where interaction strengths depend on signal values. Non-linear templates are needed for the realization of important image processing tasks. Techniques to implement non-linearities using integrated circuit primitives are available elsewhere [5][6]. However, incorporating these techniques into CNN chips seriously compromises cell density. Actually, CNN chips reported to now are only capable of establishing linear interactions. Still, piecewise-linear interactions can be emulated by taking advantage of the internal memory and the reconfigurability capabilities of last generation CNN-UM chips. Particularly, the so-called CNNUC3 chip [ 11 incorporates the following advanced CNN-UM features: capability to run algorithm with dozens of operations without external code or data movement; capability of storing four gray-scale and four binary images, on a pixel-by-pixel basis; capability to sum or subtract gray-scale images. also pixel-by-pixel; capability of selecting which cells are going to be processed (so called freezing map); ‘capability to combine, pixel-by-pixel, two binary images through any user-selectable logic operation (such as This paper experimentally demonstrates that these capabilities can be exploited for the realization of piecewise-linear templates based on the algorithmic methods presented in [7]. The paper is organized as follows; Section 2 establishes a theoretical background about the technique of non-linear templates decomposition. Section 3 describes some applications examples. Some additional comments are provided in Section 3.4. Section 4 deals with the implementation of arbitrary non-linear functions. Finally, the conclusions are presented in Section 5. logic “AND”, “OR”). 2. DECOMPOSITION OF NON-LINEAR TEMPLATES Implementing a piecewise-linear template by decomposing it into several linear ones is not a new idea. It has been previously studied in [7] at the algorithmic level. However, until now such implementation has never been demonstrated using actual CNN chips. As in [7], his paper deals with the case where only the B template is piecewise-linear, and assumes that the template is a 3 x 3 one. CNNUC3 employs the so-called FSR CNN model [SI where cell dynamic evolution is given by: t. lhis work has been partiaUy funded by ONR-NICOP N68171-98-(2-9004, DICTAM IS-1999-19007 and TIC 990826. 0-7803-6344-2/00/$10.00 02000 EEE 219 where entries of the B template. are linear. Let us consider now that these entries are non-linear, namely, B~, jit ud = Y(a . utj + B . url) where a and p are real numbers. Let us define, (3) (4) and assume that Y(5) is apiecewise-linear function with m breaking points {cl, E,2, ... , .E,,}. Then, as demonstrated in [71, the non-linear template can be decomposed into a sequence of linear ones by using the algorithm described below [71. The process starts by selecting the first linear region of the non-linear function. Let us call RI this region that E, = a ’ U,, + p ’ Utl is defined by the breaking points kl, E,2. The next step is to select which are the cells belonging to that region. This calculation is realized by two templates executions and a logic operation (all of them are done on-chip). With the first template, the so called threshold template, we drive to black all those cells having 5 > c1, while with the second one, the so called inverse threshold, we drive to black all those cells having 5 < c2. Finally a logic AND operation of both results will select those pixels where E,, c 6 < C2 *. Equations (5). (6). show the threshold and the inverse threshold templatett. The non-selected cells are “frozen”, by using the freezing mask provided by the chip, while in the selected ones the corresponding contribution to the state equation is evaluated and stored as a “bias map” that will be updated (or not) in the next iteration by adding the new result to the one that was previously stored. The updating law for the state variables of the cells that are selected must be given by the equation of a straight line (due to the fact that Y(5) is linear between each two breaking points) crossing the points k1 and k2. All the points belonging to this line satisfy: And from the CNN theory, it can be demonstrated that this relationship is obtained if the following template is executed? 2. Keep in mind that 5 = a . uij + p. utl and the subindex kl denotes the cell’ neighbours. tt. These are the FSR version of the templates. In order to get the original cllua-Yang template increme by one the self-feedback term 220 where, The process continues for the next linear region. Finally, a template execution is needed. In this template the feedback term is the same as in the original one defined in (1). the feedforward term is set to zero (modified B template), since it has heen already calculated, and the offset term is the addition of the original one z, and the “bins map” that is stored in some memory at the cell. 3. APPLICATION EXAMPLES 3.1- Absolute Value Calculation Fig. 1 shows the corresponding templates and non-linearity. Because the transformation is pixel-wise - B template has 1 x 1 size - the decomposition method can be simplified, precluding accumulation of partial results. Besides, sub-interval selection reduces to estimating sign of the input and can be accomplished by using threshold templates, particularly where a = 1 , p = 0 and = 0. Since there are two sub-intervals, the number of cell maps is also two. The first one contains black pixels at the cell positions where the corresponding input image pixels are negative, and the second is the opposite. As a special case, the first transformation is equal to inversion and the second one can be avoided in practice since it lets the cells.unchanged at their original values. Fig.2. shows the result of the execution of the absolute value calculation on CNNUC3. A = [I] B = oul(6) o = 0 E:! Fig. 1: Thc absolute value calculation template. 3.2 Gradient Calculation ,The gradient template is defined in Fig.3. This template contains eight non-zero entries each of which has two possible intervals. Thus, the decomposition method results into a total of 32 linear template executions and threshold functions. *+. me position of the p coefficient wt be rotated in order to perform this operation for each of the neighbours of the ceU appearing iu a non-linear connection cm the original B template. Wefore, each linear region could require up to 16 templates and 8 logic operations to be seld 8 templates to update thc state variable, and 8 templatw to peaform the addition of the mulu, that is 32 templates and 8 logic operatiom. 221 (a) Input @) Absolute value Fig. 2: The absolute value calculation. Fig. 3: The Gradienl calculation template. The thresholded gradient operation is similar to the previous. The only difference is a shifting in the offset term, = -Zrhrerhold (11) Thus, the black pixels in the output image correspond to the input locations where the absolute value of the gradient Fig.4 show measurements taken from CNNUC3 which demonstrate the implementation of both gradient and is larger than Zlhrcrhold . thresholded gradient templates on silicon. (a) Input @) Gradient (c) Threrholded gradient Fig. 4: Thr Gradient and Thresholded Gradienl Calculation Templates. 33 Contour Detection on Grayscale Images Fig.5 shows the associated templates and non-linear- ity. The result of this operation is an image having black pixel at those locations where the corresponding input is larger than some of the neighbours by a certain amount - 0.1 in the case of Fig5 Both the number of used mask generating templates and transformation templates are 16 ttt. Fig.6@) shows the result of executing this non-linear template on CNNUC3 with the input image of Fig.b(a). Fig. 5: The contdur Detection Template. 222 (a) Input (b) Detected contour fig. 6: Contour Detection on Gmy-Scale Images. 3.4 Additional Comments This section contains some additional ideas about decomposition, which are intended to reduce the number of required operations. This reduction is made possible due to some special functions incorporated to the C"Ua If the number of intervals is only two, the "freezing" masks are opposite. Hence, the calculation of the second mask through template execution can be replaced by a logic operation. There are special cases where the general method can be modified in order to get a more efficient decomposition. Specially, when the partial results contains only B&W pixels.In those cases, the generated interval maps contain all the information about the partial results. Moreover, when the final result is the logic sum (operation OR) or logic product (operation AND) of the partial outputs, the final result can be accumulated by the Local Logic Unit (LLU) in a Local Logic Memory (LLM) instead of by using the gray-scale accumulation process in an analog memory. chip. 4. IMPLEMENTATION OF A GENERIC NON-LINEAR FUNCTION ' The above described decomposition method can be used for piecewiselinear approximation of general non-lin- ear entries "(a. uij + f3 uI,) taking advantage of the fact that CNNUC3 is capable to distinguish 20 breaking points within a characteristic curve. Assume that the non-linear coefficient can be approximated by: where, (13) 1 52-0 = {o othawise Then, the decomposition method can be applied to implement the approximated the function. Another technique consists of approximating the non-linear function into a stair-steps type non-linearity. In this case, the non-linear function is sampled at N points (up to 20 different in CNNUC3). and approximated by: Fig. 7: "he Cubic Template in (IS) ttt. See that the number of rapired templates U not 64 as it should comespond lo the ca9e of having 8 non-linear connections. This is explained by the fad Ulat the linear regions have an iNiniie or zero slope, and so. the linear tnuwformation defined by (8) U not needed. 223 To illustrate this technique we have implemented the following non-linear cubic-type function, considering an approximation containing 12 sampling points. a(u..) ‘I = u...(u..-0.75).(uij+0.75) ‘I ‘I (15) Fig.B(a) shows the result of the simulation of this template while Fig.8@) shows the result provided by the CNNUC3 prototype. The input image has been already displayed in Fig2 (a). Due to the sampling process, the output image needs post-processing - low-pass filtering also implemented by the chip - for proper signal reconstruction. (a) Simulated @) By CNNUC3 Fig. 8: Cubic Template Execufion 5. CONCLUSIONS The executions of non-linear templates define an important application area in the field of image processing. However, previous VLSI CNNs implementations did not provide to the template engineers sufficiently accurate and versatile features to map the non-linear-to-linear existing algorithms. This paper presents experimental evidences about how a wide set of non-linear templates can be executed with by using CNNUC3. We have also briefly outlined the general decomposition method for implementing non-linear-to-linear template transformations in [7]. 6. REFERENCES G. LiBBn. S.Espejo. R. Domlnguez-Cashw and A. Rodriguez-Vbzqucz, “The CNNUC3 An Analog U0 64 x 64 CNN UN- versa1 Machine Chip Pmtotype with 7-bil Analog Accuracy”. Pmc. of Ihe CNN2ooO. subnutled. L.O. Chua and L. Yang, “Cellular Neural Networks: Theory”. lEEE Trans. Circuifs and Syslem. Vol. 35. pp. 1257- 1272. Oct 1988. T. Roska and L.O. Chua, “The CNN Universal Machne: An Analogic Array Computer”. IEEE Trans. Circuits andSystems /I. Vol. 40. pp 163-173. March 1993. L.O. Chua and T. Roska, ‘The CNN Paradigm”. IEEE Trans. Circuits and Systems I, V01.40. pp. 147- 156. March 1996. A. Rodriguez-Viqzquei M. Dclgado-Restihlto, J.L. Hue- and E Wdal, “Synthesis and Design of Nonlinear Cilruils“. Chapter 32 in The Cinuils and Fillers Handbook (W.K. Chen -editor), CRC Pms, New-York 1995. M. Delgado-Restitute. A. Rodriguez-Vbzquez and F. Vidak “Nonlinear Synthesis using ICs”. in Encyclopedra ofElcclncal and Elecfmnics Engineering (J.G. Wcbster-&tor), John Wiley & Sons 1999. L. Kck and A. Zarandy. “Implementation of Large Neighborhood Non-Linear Tcm lam on the CNN Universal Machine”. lnfernafional Journal of Circuit Theory andApplirations. Vol.26. pp. 551.566. 19&. S. Espejo. R. Carmona. R. Domlngucz-Castm and A. Rodriguez-Vbzquez: “A VLSI-Oriented Conhnuous-Time CNN Model“. lnrernafionol Journal of Circuit77zeory andApplications. Vol24, pp. 34 1-356, May-June 1996. 224