10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 1 Development of Complex Curricula for Molecular Bionics and Infobionics Programs within a consortial* framework** Consortium leader PETER PAZMANY CATHOLIC UNIVERSITY Consortium members SEMMELWEIS UNIVERSITY, DIALOG CAMPUS PUBLISHER The Project has been realised with the support of the European Union and has been co-financed by the European Social Fund *** **Molekuláris bionika és InfobionikaSzakoktananyagánakkomplexfejlesztésekonzorciumikeretben ***A projektazEurópaiUniótámogatásával, azEurópaiSzociálisAlaptársfinanszírozásávalvalósulmeg. PETER PAZMANY CATHOLIC UNIVERSITY SEMMELWEIS UNIVERSITY sote_logo.jpg dk_fejlec.gif INFOBLOKK 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 2 Peter Pazmany Catholic University Faculty of Information Technology Cellular Neural Network www.itk.ppke.hu CNN –Celluláris neurális hálózat J. Levendovszky, A. Oláh, K. Tornai Digitális-neurális-, éskiloprocesszorosarchitektúrákonalapulójelfeldolgozás Digital-and Neural Based Signal Processing & KiloprocessorArrays Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network Contents • What is CNN? • The neighboring topology • The new computational paradigm • Art of programming • Applications • Template analysis • Stability –Fix point analysis 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 3 www.itk.ppke.hu Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 www.itk.ppke.hu 4 Motivation • Implementing HNN by analog circuitry• Fully connected too many wires, and intersections• Number of neurons , small network • Number of wires (connections, layers) • Impossible to implement • Idea• Use only local connections less wire, less connection possible to implement Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 www.itk.ppke.hu CNN –Topology • Cellular Neural Networks• Locally connected • 2D arrangement of neurons: Ncolumns, Mrows 5 Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 www.itk.ppke.hu Neighborhood • Neighborhood around neuron C(i,j)with radius r • Number of neuron in neighborhood • Example: r=1, r=2 6 Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network Cells • Regular cells• C(i,j) is regular cell with respect to if and only if all neighborhood cells exist. • Boundary cells• The non-regular cells • Edge cells• The outermost boundary cells 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 7 Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network Cells • r=2• Regular cells • Boundary cells • Edge cells 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 8 Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 www.itk.ppke.hu CNN –Connections • Connections from the neighborhood• Feedback –current state • Feed forward –input image 9 State of CNN Input Image Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 www.itk.ppke.hu • Feedback of state • Feed forward of input image 10 Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 www.itk.ppke.hu Combined figure 11 State of CNN Input Image Inputforward State feedback Neighborhood Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network CNN –Definition • In the following slides the standard cellular neural network architecture will be defined • Standard CNN:• M byN rectangulararrayof cellsC(i,j) whichcellis definedmathematicallybythefollowings:• Stateequation • Output equation • Boundaryconditions • Initialstate 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 12 www.itk.ppke.hu Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network CNN –Definition • 1. State equation state, output, inputandthreshold • And where are called: feedbackand input synapticoperators (will be defined) 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 13 www.itk.ppke.hu Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network CNN –Definition • 2. Output equation: • Standard nonlinearity: 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 14 www.itk.ppke.hu Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network CNN –Definition • 3. Boundary conditions• To specify the for cells belonging to the neighborhood of the boundary and edge cells, but lying out of the array. • 4. Initial state• The initial x values for cells 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 15 www.itk.ppke.hu Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu CNN –Space and time invariance • Aand Boperators: 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 16 Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu Boundary conditions • Virtual cells• Any cell C(k,l)in the neighborhood of cell C(i,j), where and/or • Corresponding are called virtual state, virtual output, virtual inputrespectively. • Any virtual variable must be defined via various boundary conditions. • These conditions are most commonly used for 3x3 neighborhood 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 17 Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu Fixed boundary conditions • Fixed (Dirichlet) boundary conditions• Left virtual cells: • Right virtual cells: • Top virtual cells: • Bottom virtual cells: • The parameters are pre-defined, usually equals to zero 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 18 Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu Zero-flux boundary conditions • Zero-flux (Neumann) boundary conditions• Left virtual cells: • Right virtual cells: • Top virtual cells: • Bottom virtual cells: • The corner virtual cells can be arbitrary defined. 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 19 Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu Periodic boundary conditions • Periodic (Toroid) boundary conditions• Left virtual cells: • Right virtual cells: • Top virtual cells: • Bottom virtual cells: • This is equivalent to fabricating a CNN chip on silicon torus as its substrate 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 20 Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu Boundary conditions Fixed conditions 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 21 =0 Edge cells Virtual cells Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu Boundary conditions Zero-flux conditions 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 22 Virtual cells Edge cells Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network Boundary conditions Toroid conditions www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 23 Virtual cells Edge cells Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu Computational paradigm • Given 2D array of locally interconnected cell (with radius r) • Spatially and time invariant A and B operators• Cloning templates, square matrices with size 2r+1 • One zthreshold parameter • Usually r=3 18+1 free parameters • Nonlinear output function 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 24 Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu Computational paradigm • Differential equation for each cell: • CNN has the following computational model• Given input and initial state, • Given 19 free parameters=??? 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 25 Input Y(t) observable Output Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu Art of programming • The task is to find the appropriate Aand Btemplate values and zthreshold value• (Engineering task) • Special case:• Time and space invariant CNN • The differential equation for each cell: • Where … 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 26 Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu Special case • If r=1 • Neighborhood of one cell C(i,j) 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 27 Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu Special case • The operator 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 28 Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu Special case • Both template can be decomposed as follows • Thus the following equation will be used 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 29 Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu Edge detection • Global task• Given: static binary image P • Input: U(t) = P • Initial state: arbitrary • Boundary conditions: fixed type, =0 • Output: Y(.) = Binary image showing all edges of P in black 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 30 Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu Edge detection • Example • White pixel: –1 , Black pixel: +1 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 31 Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu Edge detection –rules • Local rules• White pixel white pixel, independent of neighbors • Black pixel white, if all nearest neighbors are black • Black pixel black, if at least one nearest neighbor is white 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 32 Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu Solution 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 33 •Radius of locality• Only the closest neighbors are needed • ThisAtemplate is a null template providing a CNN without feedback connections • ThisBtemplate contains threshold values and it is constructed using the previouslocal rules• Will be analyzed Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu Edge detection • Remember • Some notation • This case 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 34 Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu Edge detection –analysis • Rule 1:( ) 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 35 Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu Edge detection –analysis • Rule 2: ( ) • Rule 3: ( ) 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 36 Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu Previous example 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 37 •Consider a previous edge detection template and example • The stability of the state equation can be observed plotting the driving-point(DP) plot • In order to do this the following rules of thumb have to be considered Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu DP –Plot (uncoupled case) • Uncoupled In the Atemplate only the center element is nonzero 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 38 P-left breakpoint P+right breakpoint Slope = -1(left saturation region) Slope = -1(right saturation region) Slope = s00=a00-1(central linear region) xij= wij Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network DP –Plot (uncoupled case) • Stability www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 39 Q-stable point Q+stable point Q0stable point Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 40 Wij<-1 Edge Q stable point Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 41 wij Edge Q stable point Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 42 wij Edge Q stable point Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu Logical not template • Global task• Given: static binary image P • Input: U(t) = P • Initial state: arbitrary • Boundary conditions: fixed type, =0 • Output: Y(.) = Negated image • Local rules• White pixel black pixel, independent of neighbors • Black pixel white pixel, independent of neighbors 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 43 Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu Solution 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 44 •Rule 1 • Rule 2 • In case of rules the g() function: • The state equation Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu DP –Plot 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 45 wij=2 wij=-2 Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu Simulations –Edge template Binary Edge template on binary picture 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 46 Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network Simulations –Edge template Binary Edge template on a grayscalepicture www.itk.ppke.hu 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 47 Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu Simulations –Edge gray template 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 48 Edgegray template on Gray scale images Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu Simulations –Other tasks with one template 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 49 Finding closed shapes in a picture PointSet PointSetGroup Modified diffusion template to find dense clusters Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu Complex task with multiple templates 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 50 Z:\Kami\Dropbox\PHD\Oktatás\TAMOP\piclib_sc\input_13.bmp Z:\Kami\Dropbox\PHD\Oktatás\TAMOP\piclib_sc\output2_13.bmp Z:\Kami\Dropbox\PHD\Oktatás\TAMOP\piclib_sc\input_21.bmp Z:\Kami\Dropbox\PHD\Oktatás\TAMOP\piclib_sc\output1_21.bmp Finding watermark on picture (Further step, remove watermark from the picture) Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu Summary • Cellular Neural Network• It is impossible to implement a HNN • Idea: local connections only • Structure• Local connections, Input connections, Templates • Differential equation as state transition rule• 19 free parameters • Definition of CNN• Templates, boundary conditions, initial state 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 51 Signal processing on digital, neural, and kiloprocessor based architectures: CNN –Cellular Network www.itk.ppke.hu Summary • Image processing, task definition• Local rules • Constructing the templates • Analysis, convergence• DP plot, Edge template analysis • Real examples applications• EDGE, EDGEGRAY • Logical functions • Complex tasks 10/5/2011. TÁMOP –4.1.2-08/2/A/KMR-2009-0006 52