Main
Cellular neural networks and visual computing: foundation and applications
Cellular neural networks and visual computing: foundation and applications
Leon O. Chua, Tamas Roska
0 /
0
How much do you like this book?
What’s the quality of the file?
Download the book for quality assessment
What’s the quality of the downloaded files?
Cellular Nonlinear/Neural Network (CNN) technology is both a revolutionary concept and an experimentally proven new computing paradigm. Analogic cellular computers based on CNNs are set to change the way analog signals are processed. This unique undergraduate level textbook includes many examples and exercises, including CNN simulator and development software accessible via the Internet. It is an ideal introduction to CNNs and analogic cellular computing for students, researchers and engineers from a wide range of disciplines. Leon Chua, coinventor of the CNN, and Tamàs Roska are both highly respected pioneers in the field.
Categories:
Year:
2002
Edition:
1st
Publisher:
Cambridge University Press
Language:
english
Pages:
410
ISBN 10:
0521652472
ISBN 13:
9780511040511
File:
PDF, 4.55 MB
Download (pdf, 4.55 MB)
 Open in Browser
 Checking other formats...
 Convert to EPUB
 Convert to FB2
 Convert to MOBI
 Convert to TXT
 Convert to RTF
 Converted file can differ from the original. If possible, download the file in its original format.
 Please login to your account first

Need help? Please read our short guide how to send a book to Kindle
The file will be sent to your email address. It may take up to 15 minutes before you receive it.
The file will be sent to your Kindle account. It may takes up to 15 minutes before you received it.
Please note: you need to verify every book you want to send to your Kindle. Check your mailbox for the verification email from Amazon Kindle.
Please note: you need to verify every book you want to send to your Kindle. Check your mailbox for the verification email from Amazon Kindle.
You may be interested in Powered by Rec2Me
Most frequently terms
cnn^{1043}
template^{623}
fig^{502}
output^{469}
input^{443}
a00^{332}
cell^{326}
templates^{285}
boolean^{231}
binary^{217}
function^{213}
cells^{197}
applications^{185}
pixel^{175}
xij^{157}
circuit^{151}
cnns^{145}
analog^{143}
logic^{141}
equilibrium^{140}
linear^{139}
synaptic^{139}
systems^{133}
pixels^{130}
hence^{127}
theory and applications^{125}
cellular neural^{123}
processing^{121}
dynamic^{117}
chip^{116}
functions^{111}
uncoupled^{111}
slope^{107}
stable^{107}
theorem^{106}
roska^{105}
neural networks^{105}
global^{104}
analysis^{104}
circuits and systems^{103}
corresponding^{102}
equation^{101}
analogic^{98}
digital^{96}
cnn universal^{95}
follows^{95}
ieee transactions^{94}
visual^{94}
shown in fig^{92}
observe^{92}
region^{90}
unit^{89}
wij^{87}
variables^{86}
circuit theory^{85}
chua^{85}
zero^{84}
boundary^{84}
0 comments
You can write a book review and share your experiences. Other readers will always be interested in your opinion of the books you've read. Whether you've loved the book or not, if you give your honest and detailed thoughts then people will find new books that are right for them.
1

2

This page intentionally left blank Cellular neural networks and visual computing Cellular Nonlinear/neural Network (CNN) technology is both a revolutionary concept and an experimentally proven new computing paradigm. Analogic cellular computers based on CNNs are set to change the way analog signals are processed and are paving the way to an entire new analog computing industry. This unique undergraduatelevel textbook includes many examples and exercises, including CNN simulator and development software accessible via the Internet. It is an ideal introduction to CNNs and analogic cellular computing for students, researchers, and engineers from a wide range of disciplines. Although its prime focus is on visual computing, the concepts and techniques described in the book will be of great interest to those working in other areas of research, including modeling of biological, chemical, and physical processes. Leon Chua is a Professor of Electrical Engineering and Computer Science at the University of California, Berkeley where he coinvented the CNN in 1988 and holds several patents related to CNN Technology. He received the Neural Network Pioneer Award, 2000. Tamás Roska is a Professor of Information Technology at the Pázmány P. Catholic University of Budapest and head of the Analogical and Neural Computing Laboratory of the Computer and Automation Research Institute of the Hungarian Academy of Sciences, Budapest and was an early pioneer of CNN technology and a coinventor of the CNN Universal Machine as an analogic supercomputer, He has also spent 12 years as a parttime visiting scholar at the University of California at Berkeley. Cellular neural networks and visual computing Foundation and applications Leon O. Chua and Tamás Roska The Pitt Building, Trumpington Street, Cambridge, United Kingdom The Edinburgh Building, Cambridge CB2 2RU, UK 40 West 20th Street, New York, NY 100114211, USA 477 Williamstown ; Road, Port Melbourne, VIC 3207, Australia Ruiz de Alarcón 13, 28014 Madrid, Spain Dock House, The Waterfront, Cape Town 8001, South Africa http://www.cambridge.org © Cambridge University Press 2004 First published in printed format 2002 ISBN 0511040512 eBook (netLibrary) ISBN 0521652472 hardback To our wives, Diana and Zsuzsa Contents Acknowledgements page xi 1 Introduction 1 2 Notation, definitions, and mathematical foundation 7 2.1 Basic notation and deﬁnitions 7 2.2 Mathematical foundations 3 4 vii 14 Characteristics and analysis of simple CNN templates 35 3.1 Two case studies: the EDGE and EDGEGRAY templates 35 3.2 Three quick steps for sketching the shifted DP plot 49 3.3 Some other useful templates 50 Simulation of the CNN dynamics 100 4.1 Integration of the standard CNN differential equation 100 4.2 Image input 101 4.3 Software simulation 102 4.4 Digital hardware accelerators 110 4.5 Analog CNN implementations 111 4.6 Scaling the signals 113 4.7 Discretetime CNN (DTCNN) 114 viii Contents 5 Binary CNN characterization via Boolean functions 115 5.1 5.2 5.3 115 122 124 6 7 Uncoupled CNNs: unified theory and applications 139 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9 139 140 142 155 156 161 162 166 173 The complete stability phenomenon Explicit CNN output formula Proof of completely stable CNN theorem The primary CNN mosaic Explicit formula for transient waveform and settling time Which local Boolean functions are realizable by uncoupled CNNs? Geometrical interpretations How to design uncoupled CNNs with prescribed Boolean functions How to realize nonseparable local Boolean functions? Introduction to the CNN Universal Machine 183 7.1 7.2 7.3 7.4 7.5 184 184 188 190 7.6 7.7 8 Binary and universal CNN truth table Boolean and compressed local rules Optimizing the truth table Global clock and global wire Set inclusion Translation of sets and binary images Opening and closing and implementing any morphological operator Implementing any prescribed Boolean transition function by not more than 256 templates Minimizing the number of templates when implementing any possible Boolean transition function Analogtodigital array converter 195 198 201 Back to basics: Nonlinear dynamics and complete stability 205 8.1 8.2 8.3 8.4 8.5 205 205 210 214 219 A glimpse of things to come An oscillatory CNN with only two cells A chaotic CNN with only two cells and one sinusoidal input Symmetric A template implies complete stability Positive and signsymmetric A template implies complete stability ix Contents 8.6 8.7 A 9 10 11 Positive and celllinking A template implies complete stability Stability of some signantisymmetric CNNs Appendix to Chapter 8 The CNN Universal Machine (CNNUM) 239 9.1 9.2 9.3 9.4 240 244 246 254 The architecture A simple example in more detail A very simple example on the circuit level Language, compiler, operating system Template design tools 258 10.1 10.2 10.3 10.4 258 260 264 265 Various design techniques Binary representation, linear separability, and simple decomposition Template optimization Template decomposition techniques CNNs for linear image processing 11.1 Linear image processing with B templates is equivalent to spatial convolution with FIR kernels 11.2 Spatial frequency characterization 11.3 A primer on properties and applications of discretespace Fourier transform (DSFT) 11.4 Linear image processing with A and B templates is equivalent to spatial convolution with IIR kernels 12 13 224 231 236 267 267 269 272 272 Coupled CNN with linear synaptic weights 276 12.1 12.2 12.3 12.4 278 283 284 286 Active and inactive cells, dynamic local rules Binary activation pattern and template format A simple propagating type example with B/W symmetrical rule The connectivity problem Uncoupled standard CNNs with nonlinear synaptic weights 290 13.1 Dynamic equations and DP plot 291 x Contents 14 Standard CNNs with delayed synaptic weights and motion analysis 296 14.1 Dynamic equations 14.2 Motion analysis – discrete time and continuous time image acquisition 15 Visual microprocessors – analog and digital VLSI implementation 304 of the CNN Universal Machine 15.1 15.2 15.3 15.4 15.5 16 296 297 The analog CNN core Analogic CNNUM cell Emulated digital implementation The visual microprocessor and its computational infrastructure Computing power comparison 304 310 312 313 318 CNN models in the visual pathway and the ‘‘Bionic Eye” 320 16.1 Receptive ﬁeld organization, synaptic weights, and cloning template 16.2 Some prototype elementary functions and CNN models of the visual pathway 16.3 A simple qualitative “engineering” model of a vertebrate retina 16.4 The “Bionic Eye” implemented on a CNN Universal Machine 321 322 329 338 Notes Bibliography Exercises Appendices Index 339 348 361 389 390 Acknowledgements We started to teach a formal course devoted entirely to CNN only in 1996, in the Spring Semester, at Berkeley and in the Autumn Semester in Budapest. Since then, several versions of Lecture Notes have been iterated. We are indebted to many of our former students – some of whom have become our coworkers – who have helped us in various forms we are thankful to all of them. Dr. Ákos Zarándy, Dr. Ken Crounse, Dr. Csaba Rekecky, Dr. ChaiWah Wu, Dr. László Kék, Dr. László Nemes, Dr. András Radványi, and Dr. Péter Szolgay, as well as Tao Yang, AnShan Huang, Dávid Bálya, Katalin Keserű, István Petrás and István Szatmári made special efforts to help us during the many years of forming the text to this present version. We are also grateful to Phil Meyler for his kind initiative to publish this textbook. Leon O. Chua and Tamás Roska Berkeley–Budapest, May 2000 xi 1 Introduction Scenario Recent history of the electronic and computer industry can be viewed as three waves of revolutionary processes.1 The ﬁrst revolution, making cheap computing power available via microprocessors in the 1970s, led to the PC industry of the 1980s. The cheap laser and ﬁber optics, which resulted in cheap bandwidth at the end of the 1980s, led to the Internet industry of the 1990s. The third wave, the sensor revolution at the end of the 1990s, will also provide for a new industry. Sensor revolution means that cheap sensor and MEMS (microelectromechanical system) arrays are proliferating in almost all the conceivable forms. Artiﬁcial eyes, nose, ears, taste, and somatosensory devices as well as sensing all physical, chemical, and biological parameters, together with microactuators, etc. are becoming commodities. Thousands and millions of generically analog signals are produced waiting for processing. A new computing paradigm is needed. The cited technology assessment1 reads: The longterm consequence of the coming sensor revolution may be the emergence of a newer analog computing industry in which digital technology plays a mere supporting role, or in some instances plays no role at all. For processing analog array signals, the revolutionary Analogic Cellular Computer paradigm is a major candidate. The core of this computer is a Cellular Nonlinear/neural network2 (CNN), an array of analog dynamic processors or cells. The computer architecture is the CNN Universal Machine,3 with its various physical implementations. At the same time, Analogic CNN computers mimic the anatomy and physiology of many sensory and processing organs with an additional capability of stored programmability. Recent studies on optical and nanoscale implementations open up new horizons on the atomic and molecular levels. The CNN was invented by Leon O. Chua and Lin Yang in Berkeley in 1988. Unlike cellular automata, CNN host processors accepting and generating analog signals, the time is continuous, and the interaction values are also real values. Unlike lattice dynamics, the input of the CNN array plays an important role. Moreover, CNN becomes a rigorous framework for complex systems exhibiting emergent behavior and the various forms of emergent computations. The notion of the cloning template, the 1 2 Introduction representation of the local interconnection pattern, is crucial. This allows not only modeling but also engineering of complex systems. Stored programmability, invented by John von Neumann, was the key for endowing digital computers with an almost limitless capability within the digital universe of signals, opening the door to human invention via digital algorithms and software. Indeed, according to the Turing–Church thesis, any algorithms on integers conceived by humans can be represented by Recursive functions/Turing Machines/Grammars. The CNN Universal Machine is universal not only in a Turing sense but also on analog array signals. Due to stored programmability, it is also open to human intelligence with a practically limitless capability within the universe of analog array signals, via analogic spatiotemporal algorithms and software. The new world opened by the Analogic CNN computing paradigm is nowadays a reality. There are operational focal plane visual microprocessors with 4096 or 16 000 processors, which are fully stored, programmable, and there are Walkmansize selfcontained units with image supercomputer speed. The CNN Universal Chip4 highlighted on the cover of this book represents a milestone in information technology because it is the ﬁrst operational, fully programmable industrialsize brainlike storedprogram dynamic array computer in the world. This complete computer on a chip consists of an array of 64 × 64 0.5 micron CMOS cell processors, where each cell is endowed not only with a photo sensor for direct optical input of images and videos, but also with communication and control circuitries, as well as local analog and logic memories. Each CNN cell is interfaced with its nearest neighbors, as well as with the outside world. This massively parallel focalplane array computer is capable of processing 3 trillion equivalent digital operations per second (in analog mode), a performance which can be matched only by supercomputers. In terms of the SPA (speed, power, area) measures, this CNN universal chip is far superior to any equivalent DSP implementation by at least three orders of magnitude in either speed, power, or area. In fact, by exploiting the stateoftheart vertical packaging technologies, close to peta (1015 ) OPS CNN universal cube can be fabricated with such universal chips, using 200 × 200 arrays. There are many applications which call for TeraOPS or even PetaOPS in a Walkmansize device. Some of these applications include highspeed target recognition and tracking, realtime visual inspection of manufacturing processes, intelligent vision capable of recognizing context sensitive and moving scenes, as well as applications requiring realtime fusing of multiple modalities, such as multispectral images involving visible, infrared, long wave infrared, and polarized lights. In addition to the immense image and video processing power of the CNN universal chip, we can exploit its unique brainlike architecture to implement brainlike information processing tasks which conventional digital computers have found wanting. Such brainlike processing operations will necessarily be nonnumeric and spatiotemporal in nature, and will require no more than the accuracy of common neurons, which is 3 Introduction less than eight bits. Since the computation is a noniterative wavelike process, the input–output accuracy is not constrained by the iterative digital process. The CNN universal chip is therefore an ideal tool for developing and implementing brainlike information processing schemes. It is this vision of brainlike computing via the CNN universal chip that makes the publication of this textbook both a timely and historic event, the ﬁrst undergraduate textbook on this new computing paradigm. The textbook Cellular Nonlinear/neural Networks (CNN) is an invention with rapid proliferation. After the publication of the cited original paper by Chua and Yang in 1988, several papers explored the rich dynamics inherent in this simple architecture. Indeed, many artiﬁcial, physical, chemical, as well as living (biological) systems and organs can be very conveniently modeled via CNN. Hence, the book is written in such a way that no electronic circuit knowledge is needed to understand the ﬁrst 14 chapters of this book. Indeed, it is our teaching experience, at Berkeley and in Budapest, that undergraduate students from different backgrounds and with a modest knowledge of mathematics and physics taught in engineering, physics, and chemistry departments, as well as biology students from similar backgrounds can understand the book. In Chapter 2, the basic notations, deﬁnitions, and mathematical foundation are presented. The standard CNN architecture is introduced. The cell, the interconnection structure, the local connectivity pattern, the canonical equations and some useful notations, and the biological motivation are described. The importance of the local interconnection “synaptic weight” pattern, the cloning template, or gene, is emphasized. Indeed, these templates, mostly deﬁned by 19 parameters, deﬁne the complete array dynamics, which generate an output “image” from an input “image.” In Chapter 3, after two examples, a simple technique for determining array dynamics, based on cell dynamics, is introduced and explained. Next, 11 useful templates are shown with examples and rigorous mathematical analysis. Chapter 4 is devoted to the digital computer simulation of CNN dynamics. Numerical integration algorithms, digital hardware accelerators, as well as the analog implementation are discussed. An accompanying simulator CANDY is provided in the Appendix. In Chapter 5 the characterization of the simplest form of a CNN is explored and the binary input binary output case is described. It is quite surprising that even this very basic form with a 3 × 3 neighborhood template could implement 2512 ∼ 10134 different local Boolean functions. Uncoupled CNN templates constitute a simple class of CNN. Their uniﬁed theory and applications described in Chapter 6 provide a thorough understanding of this class of CNN. 4 Introduction In Chapter 7, we begin the introduction of the CNN computer represented by the CNN Universal Machine architecture. We emphasize the need for local analog and logic memory, a global clock and global wire, as well as a local logic unit. It is shown, for example, that every local Boolean function can be realized by using these simple elements in each cell processor. In Chapter 8, “Back to Basics,” the mathematical analysis of the stability of CNN in terms of cloning templates is presented. It turns out that, in most cases, simple conditions are available to test the templates deﬁning completely stable CNN. The complete architecture of the CNN Universal Machine is shown in Chapter 9. Moreover, the computational infrastructure consisting of a highlevel language, a compiler, operating system, and a development system are introduced. An example describing all the elementary details uncovers the basic implementation techniques. Chapter 10 presents template design and optimization algorithms. The use of a simple program TEMPO for template optimization and decomposition is prepared and provided in the Appendix. Many twodimensional linear ﬁlters can be represented by CNN. These techniques are shown in Chapter 11 which also introduces the discrete space Fourier transform. Once we allow spatial coupling, the dynamics of the CNN becomes not only much richer, but also exotic. The coupled CNN is described in Chapter 12 with a design method for binary propagation problems. In particular, it turns out that the global connectivity problem, long considered impossible by locally connected arrays, can be solved by a quite simple coupled CNN. Nonlinear and delay type synaptic weights and their use are introduced in Chapters 13 and 14, respectively. These types of CNN are typical in modeling living neural networks as well as in solving more complex image processing problems. In Chapter 15, we show the basics of the CMOS analog and digital implementation of the CNN Universal Machine. Indeed, the ﬁrst visual microprocessor and its computational infrastructure are described. A computing power comparison is really breathtaking: about three orders of magnitude speed advantage for complex spatiotemporal problems on the same area of silicon. Finally, in Chapter 16, the surprising similarity between CNN architecture and models of the visual pathway is highlighted. Models and some measurements in living retina are compared. In addition to the many examples in the text, exercises at the end of the book help both students as well as lecturers to make practical use of the textbook. The Appendices, provided via the Internet, contain a CNN template library (TEMLIB), a simple yet efﬁcient simulator (CANDY), and a template design and optimization tool (TEMPO/TEMMASTER). These design tools provide for a working environment for the interested reader as well as for the students to explore this new ﬁeld of modeling and computing. The text can be taught, typically, as a onesemester course. 5 Introduction New developments More than 1000 reviewed papers and books have been published since the seminal paper by Chua and Yang on CNN technology. Recently, the scope has started to broaden in many directions. Various new forms of physical implementations have started to emerge. Optical implementation is already emerging using molecular level analog optical memory (Bacteriorhodopsine or polymer materials) and atomic5 and molecular6 level implementation of the CNN array as well as of the CNN Universal Machine may become feasible; the Analogic Cellular Computer represents a new platform for computing. However, this notion of computing contains brandnew elements and techniques, partially reﬂecting some forms of naturemade information processing. Naturemade information processing has several different manifestations. On the molecular level this means the protein structures or interacting molecules on a two or threedimensional grid; on the neuronal level it may mean the many sensory organs and subsequent neural processing. On the functional neuronal level it may mean the information representation in spatiotemporal memory, the functional laterality of the brain, as well as the parallel processing places and functional units learned via PET, NMR, fNMR, etc. On the mathematicalphysical level it may mean several dynamic spatiotemporal processes and phenomena represented by different nonlinear partial differential equations (PDEs). Autowaves, spiral waves, trigger waves are just a few of these exotic waves. In modern image processing, PDEbased techniques are becoming the most challenging and important new directions. For the analogic CNN computer these are the native, elementary instructions like the multiplication, addition, XOR, NAND, etc. in digital computers. A new understanding about computing itself is emerging. The striking intellectual and scientiﬁc challenge is how to combine these diverse phenomena in useful algorithms running on a standard spatiotemporal computer, based on the CNN Universal Machine. The analogic cellular visual microprocessors, embedded in a complete programming environment,7 offer surprising system performance. Two types of tasks are becoming tractable: Class K: Kilo realtime [K r/t] frame rate class. The frame rate of the process in this class is in the order of about a thousand times faster than the realtime video frame rate (30 frames per second). A typical experiment is where a pattern classiﬁcation with more than 10,000 frames per second was tested (more than 0.33 K r/t). Using current CMOS technology, 1.5 K r/t, that is about 50,000 frame per second, is feasible. In this Class K, the high frame rate is the key in the computation. Clearly, the sensing and computing tasks are to be physically integrated. In standard digital technology, 6 Introduction there is no time for A to D conversion and to complete the calculation, all within a few microseconds. Class T: TeraOPS equivalent computing power class. Even if the frame rate is small, like realtime video (30 frames per second), the required computing power (per chip) is enormous. Indeed, a trillion operations per second are to be – and can be – achieved. These TeraOPS chips are capable of solving a nonlinear PDE on a grid in a few microseconds. The detection of a moving inner boundary of the left ventricle in an echocardiogram, via an analogic CNN algorithm combining several waves, local logic, and morphology operators, took only 250 microseconds on the ACE4K analogic Visual Microprocessor Chip made in Seville. These chips hosted 4096 cell processors on a chip. This means about 3.0 TeraOPS equivalent computing power, which is about a thousand times faster than the computing power of an advanced Pentium processor. A major challenge, not yet solved by any existing technologies, is to build analogic adaptive sensorcomputers,8 where sensing and computing understanding are fully and functionally integrated on a chip. Adaptive tuning of the sensors, pixel by pixel, is performed based on the content and context of the dynamically changing scene under sensing. 2 Notation, definitions, and mathematical foundation 2.1 Basic notation and definitions Deﬁnition 1: Standard CNN architecture A standard CNN architecture consists of an M × N rectangular array of cells (C(i, j)) with Cartesian coordinates (i, j), i = 1, 2, . . . , M, j = 1, 2, . . . , N (Fig. 2.1). 1 2 3 Column j N 1 2 3 C(i, j) Row i M Fig. 2.1. Remark: There are applications where M = N . For example, a 5 × 512 CNN would be more appropriate for a scanner, fax machine, or copy machine. Deﬁnition 2: Sphere of inﬂuence of cell C(i, j) The sphere of inﬂuence, Sr (i, j), of the radius r of cell C(i, j) is deﬁned to be the set of all the neighborhood cells satisfying the following property Sr (i, j) = {C(k, l) max 1≤k≤M,1≤l≤N where r is a positive integer. 7 {k − i, l − j} ≤ r } (2.1) 8 Notation, definitions, and mathematical foundation C(i, j ) C(i, j ) (a) (b) Fig. 2.2. (a) r = 1 (3 × 3 neighborhood), (b) r = 2 (5 × 5 neighborhood). We will sometimes refer to Sr (i, j) as a (2r + 1) × (2r + 1) neighborhood. For example, Fig. 2.2(a) shows an r = 1 (3 × 3) neighborhood. Fig. 2.2(b) shows an r = 2 (5 × 5) neighborhood. Remarks: 1 In IC implementations, every cell is connected to all its neighbors in Sr (i, j) via “synaptic” circuits. 2 When r > N /2, and M = N , we have a fully connected CNN where every cell is connected to every other cell and Sr (i, j) is the entire array. This extreme case corresponds to the classic Hopﬁeld Net. It is impractical to build any reasonable size (several thousand cells) Hopﬁeld Net in a VLSI chip. There exists a “commercial” Hopﬁeldlike chip by INTEL called “ETANN,” type 80170 ($500 in 1995). This chip has 64 cells which makes it more of an expensive “toy.” Deﬁnition 3: Regular and boundary cells A cell C(i, j) is called a regular cell with respect to Sr (i, j) if and only if all neighborhood cells C(k, l) ∈ Sr (i, j) exist. Otherwise, C(i, j) is called a boundary cell (Fig. 2.3). Remark: The outermost boundary cells are called edge cells. Not all boundary cells are edge cells if r > 1. Deﬁnition 4: Standard CNN A class 1 M × N standard CNN is deﬁned by an M × N rectangular array of cells C(i, j) located at site (i, j), i = 1, 2, . . . , M, j = 1, 2, . . . , N . Each cell C(i, j) is deﬁned mathematically by: 1 State equation ẋi j = −xi j + C(k,l)∈Sr (i, j) A(i, j; k, l)ykl + C(k,l)∈Sr (i, j) B(i, j; k, l)u kl + z i j (2.2) 9 2.1 Basic notation and definitions Boundary cell (if r = 1) Corner cell Fig. 2.3. where xi j ∈ R, ykl ∈ R, u kl ∈ R, and z i j ∈ R are called state, output, input, and threshold of cell C(i, j), respectively. A(i, j; k, l) and B(i, j; k, l) are called the feedback and the input synaptic operators to be deﬁned below. 2 Output equation 1 1 yi j = f (xi j ) = xi j + 1 − xi j − 1 2 2 (2.3) This is called standard nonlinearity (Fig. 2.4). yij 1 –1 0 1 xij –1 Fig. 2.4. 3 Boundary conditions The boundary conditions are those specifying ykl and u kl for cells belonging to Sr (i, j) of edge cells but lying outside of the M × N array. 10 Notation, definitions, and mathematical foundation 4 Initial state xi j (0), i = 1, . . . , M, j = 1, . . . , N (2.4) Remarks: 1 The input u kl is usually the pixel intensity of an M × N grayscale image or picture P, normalized without loss of generality, to have the range −1 ≤ u kl ≤ +1 where “white” is coded by −1 and “black” is coded by +1. For a still image, u kl is a constant for all time, for a moving image (video) u kl will be a function of time. Other variables (x(0), y, z) can also be speciﬁed as images. 2 In the most general case, A(i, j; k, l), B(i, j; k, l), and z i j may vary with position (i, j) and time t. Unless otherwise stated, however, we will assume they are space and time invariant. 3 In the most general case both A(i, j; k, l) and B(i, j; k, l) are nonlinear operators1 which operate on xkl (t), ykl (t), u kl (t), xi j (t), yi j (t), and u i j (t), 0 ≤ t ≤ t0 , to produce a scalar (A(i, j; k, l) ◦ ykl )(t0 ) and (B(i, j; k, l) ◦ u kl )(t0 ), 0 ≤ t ≤ t0 . 4 We may also introduce synaptic laws depending on the states (C template) and on mixed variables (D template), respectively. That is (C(i, j; k, l) ◦ xkl )(t0 ) and (D(i, j; k, l) ◦ (u kl , xkl , ykl )(t0 ). Unless otherwise stated, however, A(i, j; k, l)ykl and B(i, j; k, l)u kl will denote ordinary multiplication with real coefﬁcients where they may be nonlinear functions of states, inputs, and outputs of cells C(i, j), C(k, l) and may involve some time delays (i.e., they may contain a ﬁnite time history, as in the case of having a time delay). The following are some space and time invariant nonlinear examples chosen from the CNN catalog of applications (CNN Software Library). See some of them in TEMLIB (Appendix A). EXAMPLE 2.1: a( yij ) 1 – 0.025 0.025 –1 Fig. 2.5. yij 11 2.1 Basic notation and definitions A(i, j; k, l) = a(yi j ): depends on output (from TEMPLATE MajorityVoteTaker) (Fig. 2.5). EXAMPLE 2.2: C(i, j; k, l) = c(xi j ): depends on state (from TEMPLATE LGTHTUNE) (Fig. 2.6). c(xij) 1 0 0.2 xij –3 Fig. 2.6. EXAMPLE 2.3: A(i, j; k, l) = a(u i j , u kl ) and B(i, j; k, l) = b(u i j , u kl ): depends on two inputs (from TEMPLATE GrayscaleLineDetector) (Fig. 2.7). a(uij, ukl ) 1 –0.15 0.15 uij – ukl b(uij, ukl) 1 0.25 uij – ukl Fig. 2.7. EXAMPLE 2.4: A(i, j; k, l) = a(yi j , ykl ): depends on two outputs (from TEMPLATE GlobalMaximumFinder) (Fig. 2.8). 12 Notation, definitions, and mathematical foundation a( yij, ykl ) 0.25 0.125 –2 yij – ykl –1 Fig. 2.8. EXAMPLE 2.5: C(i, j; k, l) = c(xi j , xkl ): depends on two states (from TEMPLATE EXTREME) (Fig. 2.9). c(xij , xkl ) 1 0.2 – 0.2 xij – xkl –1 –2 Fig. 2.9. EXAMPLE 2.6: D(i, j; k, l) = d(u kl , yi j ): depends on input and output (from TEMPLATE EROSION) (Fig. 2.10). d (ukl , yij ) 1 0 ukl – yij –1 Fig. 2.10. Some examples of timedelay operators: 13 2.1 Basic notation and definitions EXAMPLE 2.7: (A(i, j; k, l)ykl )(t) = 0.68ykl (t − 10): depends on the past of the output (from TEMPLATE SpeedDetection). EXAMPLE 2.8: (B(i, j; k, l)u kl )(t) = −0.25u kl (t − 10), (k, l) = (i, j): depends on the past of the input (from TEMPLATE ImageDifferenceComputation). Remarks: 1 A grayscale image can be represented pixelwise using a onetoone map between a picture element (pixel) and a cell. The luminance value of the pixel would be coded as: black → +1, white → −1, gray → (−1, +1). 2 It is useful and correct to think of the triple {A(i, j; k, l), B(i, j; k, l), z i j } as an elementary CNN instruction (macro), because they specify how an M × N input image U at t = 0 will be transformed to produce an M × N output image Y(t) for all t ≥ 0. Deﬁnition 5: Spaceinvariant or isotropic CNN A CNN is spaceinvariant or isotropic if and only if both the synaptic operators A(i, j; k, l), B(i, j; k, l) and the threshold z i j do not vary with space. In this case, we can write A(i, j; k, l)ykl = A(i − k, j − l)ykl k−i≤r l− j≤r C(k,l)∈Sr (i, j) B(i, j; k, l)u kl = B(i − k, j − l)u kl k−i≤r l− j≤r C(k,l)∈Sr (i, j) zi j = z (2.5) A standard CNN (with linear synaptic operators) has the following state equation (using the same notation as in (2.2)): ẋi j =−xi j + C(k,l)∈Sr (i, j) + C(k,l)∈Sr (i, j) A(i, j; k, l)ykl + C(i, j; k, l)xkl + B(i, j; k, l)u kl + z i j C(k,l)∈Sr (i, j) C(k,l)∈Sr (i, j) D(i, j; k, l)(u kl , xkl , ykl ) (2.2∗ ) 14 Notation, definitions, and mathematical foundation 2.2 Mathematical foundations 2.2.1 Vector and matrix representation and boundary conditions The system of n = M N ordinary differential equations (ODE) deﬁning a standard (not necessarily spaceinvariant) CNN can be recast in the form ẋi j = h i j (x̃i j , t), i = 1, 2, . . . , M, j = 1, 2, . . . , N (2.6) where h i j (x̃i j , t) = −xi j (t) + A(i, j; k, l)ykl (t) + si j (t) C(k,l)∈Sr (i, j) where ykl = f (xkl ) si j (t) = B(i, j; k, l)u kl (t) + z i j (t) C(k,l)∈Sr (i, j) x̃i j is a vector of length (2r + 1)2 whose components include all variables xkl ∈ Sr (i, j), i.e. {xkl : k − i ≤ r, l − j ≤ r } We can cast Eq. (2.6) into the following M × N matrix differential equation which exhibits a onetoone correspondence with the CNN architecture ẋ12 ... ẋ1N ẋ11 ẋ ẋ22 ... ẋ2N 21 .. .. .. . . . ẋ M−1,1 ẋ M−1,2 . . . ẋ M−1,N ẋ M1 ẋ M2 ... ẋ M N h 11 (x̃11 ) h 12 (x̃12 ) ... h 1N (x̃1N ) h 21 (x̃21 ) h 22 (x̃22 ) ... h 2N (x̃2N ) . . . .. .. .. = (2.7) h M−1,1 (x̃ M−1,1 ) h M−1,2 (x̃ M−1,2 ) . . . h M−1,N (x̃ M−1,N ) h M2 (x̃ M2 ) ... h M N (x̃ M N ) h M1 (x̃ M1 ) Deﬁnition 6: Virtual cells Any cell C(k, l), with k − i ≤ r, l − j ≤ r , and k ∈ / {1, 2, . . . , M} and/or l ∈ / {1, 2, . . . , N } is called a virtual cell, and the associated xkl , ykl , u kl , and z kl are called virtual state, virtual output, virtual input, and virtual threshold, respectively. 15 2.2 Mathematical foundations Boundary conditions Any virtual variable in xi j of Eq. (2.6) must be speciﬁed via various boundary conditions which are the most commonly used for a 3 × 3 neighborhood. 1 Fixed (Dirichlet) boundary conditions u i,0 = β1 , i = 1, 2, . . . , M Left virtual cells: yi,0 = α1 , Right virtual cells: yi,N +1 = α2 , u i,N +1 = β2 , i = 1, 2, . . . , M u 0, j = β3 , j = 1, 2, . . . , N Top virtual cells: y0, j = α3 , Bottom virtual cells: y M+1, j = α4 , u M+1, j = β4 , j = 1, 2, . . . , N where αi and βi are user prescribed constants (usually equal to zero). Circuit interpretation: Add one row or column along the boundary and force each cell to have a ﬁxed input and output by batteries (Fig. 2.11). M×N CNN Fig. 2.11. The circuit interpretation of the ﬁxed (Dirichlet) boundary condition. 2 Zeroﬂux (Neumann) boundary conditions (Fig. 2.12) u i,0 = u i,1 , i = 1, 2, . . . , M Left virtual cells: yi,0 = yi,1 , Right virtual cells: yi,N +1 = yi,N , u i,N +1 = u i,N , i = 1, 2, . . . , M Top virtual cells: y0, j = y1, j , u 0, j = u 1, j , j = 1, 2, . . . , N Bottom virtual cells: y M+1, j = y M, j , u M+1, j = u M, j , j = 1, 2, . . . , N . Remark: This boundary condition usually applies to the case where there is no input, i.e., u i j = 0 for all (i, j). Because any input would cause energy and/or material ﬂow from the outside making the system an “open system” in the sense of thermodynamics, CNN 16 Notation, definitions, and mathematical foundation x11 x1N x1N x11 M×N CNN xM1 xMN xM1 xMN Fig. 2.12. The circuit interpretation of the Neumann boundary condition. with zero input is called autonomous CNN, and constitutes an important class with widespread applications in pattern formation and “autowave” generation. 3 Periodic (Toroidal) boundary conditions u i,0 = u i,N , i = 1, 2, . . . , M Left virtual cells: yi,0 = yi,N , Right virtual cells: yi,N +1 = yi,1 , u i,N +1 = u i,1 , i = 1, 2, . . . , M u 0, j = u M, j , j = 1, 2, . . . , N Top virtual cells: y0, j = y M, j , Bottom virtual cells: y M+1, j = y1, j , u M+1, j = u 1, j , j = 1, 2, . . . , N . A A M N D CNN D B B C C Fig. 2.13. The circuit interpretation of the Periodic (Toroidal) boundary condition. Identify each cell from the top row with the corresponding cell in the bottom row, identify each cell from the left column with the corresponding cell in the right column. 17 2.2 Mathematical foundations This is equivalent to fabricating a CNN chip on a silicon torus as its substrate. Vector differential equation Since virtually all theorems and numerical techniques for solving systems of ODE are formulated in vector form, we must repack the M × N matrix ODE (2.6) into an M N × 1 vector ODE. There are many ways to order the variables. We consider three typical orders: 1 Rowwise packing scheme 2 Diagonal packing scheme 3 Columnwise packing scheme These packing schemes are shown in Figs 2.14(a), (b), and (c), respectively. 11 11 1N 21 2N 21 31 3N 12 13 22 23 14 1N 11 12 13 M1 M2 M3 1N 2N 31 3N 41 51 MN M1 M1 MN (a) (b) MN (c) Fig. 2.14. Three (among many others) possible packing schemes. After repacking, we obtain a system of n = M N vector systems x̂˙ 1 x̂1 ẑ 1 ŷ1 û 1 ˙x̂ 2 x̂2 ŷ2 û 2 ẑ 2 . + . + . .. + .. = − . . . . . .. . x̂n ŷn û n ẑ n x̂˙ n ẋ x Â y B̂ u z or in vector form ẋ = −x + Ây + B̂u(t) + z(t) yi = f (xi ) (2.8) where x = [x̂1 , x̂2 , . . . , x̂n ]T is the state vector with the same order of state variables. The two matrices Â and B̂ are n × n matrices whose nonzero entries are the synaptic weights A(i, j; k, l) and B(i, j; k, l), respectively, corresponding to the above three 18 Notation, definitions, and mathematical foundation 0 q q 0 Fig. 2.15. The band structure of Â and B̂. packing schemes. Each matrix is quite sparse (most entries are zero) with the band structure shown in Fig. 2.15. For M = N , the band has a bandwidth w = 2q + 1 where q = N + 1 for rowwise packing schemes, q = 2N − 2 for diagonal packing schemes, q = 2N − 1 for columnwise packing schemes. The band corresponding to the above three packing schemes can be divided into two or more diagonal subbands, each of which is a sparse matrix. Remarks: Â and B̂ are very large matrices, e.g., for M = N = 1000 (for HDTV applications), n = 1,000,000, q = 1001, w = 2003 for rowwise packing scheme, which is only 0.2% of L = 106 (L is the bandwidth of the full matrix). This shows Â and B̂ are very sparse matrices. 2.2.2 Existence and uniqueness of solutions To motivate the importance of the questions of “existence and uniqueness of solutions” for a CNN, a question which has never been an issue in linear circuit and system theory, consider the following three simple nonlinear circuits. Example 1 Consider the circuit shown in Fig. 2.16(a) whose state equation is given by ẋ = − 1 , 2x t ≥0 (2.9) 19 2.2 Mathematical foundations The characteristics of the righthand side are shown in Fig. 2.16(b). The solution of Eq. (2.9) with initial condition x(0) = x0 > 0 is given by x(t) = x02 − t, t ≥0 (2.10) and sketched in Fig. 2.16(c). Observe that this circuit has no solution with any initial state x0 > 0 for t ≥ T = x02 . + + i= 1 2v x= – 1 2x x x0 x x0 v 0 1F t 0 – – x (a) (b) T = x02 (c) Fig. 2.16. Example of a circuit which has no solution after a ﬁnite time T . Example 2 Consider the circuit shown in Fig. 2.17(a) whose state equation is given by 3 1/3 x (2.11) 2 The characteristics of the righthand side are shown in Fig. 2.17(b). The solution of Eq. (2.11) with initial condition x(0) = 0 is given by ẋ = x(t) = 0, (t − T )3/2 , 0≤t ≤T t>T (2.12) for any T ∈ R. This solution is shown in Fig. 2.17(c) for different choices of T = T1 , T2 , . . . , TN . Since T is arbitrary, this circuit has an inﬁnite number of distinct solutions. Example 3 Consider the circuit shown in Fig. 2.18(a) whose state equation is given by ẋ = x 2 (2.13) The characteristics of the righthand side are shown in Fig. 2.18(b). The solution of Eq. (2.13) with initial state x(0) = 1 is given by x= 1 1−t (2.14) 20 Notation, definitions, and mathematical foundation + + x i=– 3 3 v 2 x= x 3 1/3 x 2 v 1F x 0 – – 0 T1 T2 (a) (b) t TN (c) Fig. 2.17. Example of a circuit having inﬁnitely many distinct solutions, all with the same initial state x(0) = 0. As shown in Fig. 2.18(c), this circuit has a solution which cannot be continuous beyond t ≥ 1 because it blows up at t = 1. This phenomenon is called a ﬁnite escape time. x + + i = –v2 x= x2 x0 x v 1F – – (a) 0 1 x 1 t 0 (b) 1 (c) Fig. 2.18. Example of a circuit having a ﬁnite escape time. The examples in Fig 2.18 show that even a simple twoelement nonlinear circuit may not have a solution, and even if a solution exists it may not be unique, or may not be continued for all times t ≥ 0. How do we determine whether a nonlinear circuit has a unique solution for all times t ≥ 0. This is of fundamental importance for us since we will be concerned with asymptotic behavior as t → ∞. There is no general method to answer this fundamental question since any method or theorem must exclude such simple equations as (2.9), (2.11), and (2.13)! Fortunately, for CNN, we can prove the following: Theorem 1: Global existence and uniqueness theorem Assume the standard CNN described by Eq. (2.2) satisﬁes the following three hypotheses: 21 2.2 Mathematical foundations H1: The synaptic operators are linear and memoryless, i.e., A(i, j; k, l)ykl and B(i, j; k, l)u kl are scalar multiplications, where A(i, j; k, l) and B(i, j; k, l) are real numbers. H2: The input u i j (t) and threshold z i j (t) are continuous functions of time. H3: The nonlinearity f (x) is Lipschitz continuous in the sense that there exists a constant L such that for all x , x ∈ R f (x ) − f (x ) ≤ Lx − x (2.15) (Note: for the scalar case, the norm is equivalent to the absolute value.) Then for any initial state xi j (0) ∈ R, the CNN has a unique solution for any t ≥ 0 (see Fig. 2.19). f (x) –L 0 L x x Fig. 2.19. Remark: The standard CNN satisﬁes all three hypotheses H1, H2, and H3. Proof: Hypotheses H1 implies we can recast Eq. (2.1) into the vector form ẋ = −x + Ây + B̂u(t) + z(t) = h(x, t) x yi = f (xi ) (2.16) We show ﬁrst that h(x, t) is Lipschitz continuous with respect to x. Choose any x , ∈ Rn , and let y = [ f (x1 ), . . . , f (xn )]T , so that, y = f(x ) and y = f(x ). h(x , t) − h(x , t) = −x + Ây + x − Ây = x − x + Â(y − y ) ≤ x − x + Ây − y (2.17) 22 Notation, definitions, and mathematical foundation Now y − y = f (x 1 ) f (x 2 ) .. . − f (x n ) f (x n ) f (x 1 ) f (x 2 ) .. . =  f (x 1 ) − f (x 1 )2 + · · · +  f (x n ) − f (x n )2 ≤ L 2 x1 − x1 2 + L 2 x2 − x2 2 + · · · + L 2 xn − xn 2 (in view of hypothesis H3) x1 − x1 x − x 2 2 = L .. . x − x n n = L x − x (2.18) Substituting equation (2.18) into equation (2.17), we obtain h(x , t) − h(x , t) ≤ 1 + L Â x − x = L̂x − x (2.19) where L̂ = 1 + LÂ is a global Lipschitz constant, independent of x and t. Hence, h(x, t) is uniformly Lipschitz continuous with respect to x. Moreover, since for each x0 ∈ Rn , h(x0 , t) is continuous for all t, in view of H2, we can ﬁnd a bound Mx0 t0 a (which in general depends on x0 , t0 , and a) such that h(x 0 , t) ≤ Mx0 ,t0 ,a ∀ t ∈ [t0 , t0 + a] Then for all x, such that x − x0 ≤ b, t ∈ [t0, t0 + a] h(x, t) ≤ Mx0 ,t0 ,a + L̂b in view of the Lipschitz continuity of h(x, t). It follows from the Picard–Lindelof Theorem2 that a unique solution exists for a time duration of b second min a, Mx0 ,t0 ,a + L̂b By choosing b large enough and a > 1/ L̂, one can see that a solution exists for approximately 1/ L̂ seconds where L̂ is independent of x0 , t0 , a, and b. We can use the same procedure to show a unique solution exists for the next 1/ L̂ seconds, etc. So, a unique solution exists for any time. 23 2.2 Mathematical foundations 2.2.3 Boundedness of solutions Theorem: Explicit solution bound For all initial states, inputs, and thresholds satisfying xi j (0) ≤ 1, u i j (t) ≤ 1, z i j (t) ≤ z max the solution xi j (t) of the standard CNN with linear memoryless synaptic operators A(i, j; k, l) and B(i, j; k, l) is uniformly bounded in the sense that there exists a constant xmax such that xi j (t) ≤ xmax ∀t ≥ 0, 1 ≤ i ≤ M, 1≤ j ≤N where xmax = 1 + z max + max 1≤i≤M 1≤ j≤N C(k,l)∈Sr (i, j) (A(i, j; k, l) + B(i, j; k, l)) Lemma 1 (Appendix 1) The complete solution of ẋ = −x + f (t) x(0) = x0 is given by x(t) = x0 e−t + t e−(t−τ ) f (τ ) dτ, t ≥0 0 In the special case where f (τ ) = f 0 where f 0 is a constant, we have x(t) = x0 e−t + f 0 (1 − e−t ), t ≥0 The equivalent electrical circuit is as shown in Fig. 2.20. + x(t) – Fig. 2.20. 1Ω f (t) (2.20) 24 Notation, definitions, and mathematical foundation Proof of Theorem 2: ẋi j = −xi j + A(i, j; k, l)ykl + C(k,l)∈Sr (i, j) αi j (t) B(i, j; k, l)u kl +z i j (2.21) C(k,l)∈Sr (i, j) βi j (u(t)) f (t) where αi j (t) and βi j (t) are deﬁned for all t ≥ 0 in view of Theorem 1. Applying Lemma 1, t e−(t−τ ) [αi j (τ ) + βi j (u(τ )) + z i j (τ )] dτ (2.22) x(t) = xi j (0) e−t + 0 Applying triangular inequality t x(t) ≤ xi j (0) e−t  + e−(t−τ ) [αi j (τ ) + βi j (u(τ )) + z i j (τ )] dτ 0 t −t ≤ xi j (0)e  + (αmax + βmax + z max ) e−(t−τ ) dτ (2.23) 0 where αmax = max αi j (t) ≤ t≥0 But t (2.24) B(i, j; k, l) max u kl (t) (2.25) βmax = max βi j (u) ≤ u A(i, j; k, l) max ykl (t) t≥0 C(k,l)∈Sr (i, j) u C(k,l)∈Sr (i, j) e−(t−τ ) dτ = 1 − e−t < 1, t ≥0 (2.26) 0 u kl (t) ≤ 1 (2.27) xi j (0) ≤ 1 (2.28) Hence, (2.21)–(2.28) imply xi j (t) ≤ xi j (0) e−t  + αmax + βmax + z max ≤ 1 + z max + A(i, j; k, l) + C(k,l)∈Sr (i, j) ≤ 1 + z max + max = xmax independent of (i, j). 1≤i≤M 1≤ j≤N C(k,l)∈Sr (i, j) B(i, j; k, l) C(k,l)∈Sr (i, j) (A(i, j; k, l) + B(i, j; k, l)) 25 2.2 Mathematical foundations Remarks: 1 For spaceinvariant CNN, xi j (t) is bounded by x̂max = 1 + z max + Akl  + B kl  (2.29) 1≤k≤M 1≤l≤N 2 Theorem 2 imposes a minimum power supply voltage for any CNN circuit implementation, and is fundamental for designing a CNN circuit. 2.2.4 Spaceinvariant CNN Cloning template representation Since the majority of all CNN applications use only spaceinvariant standard CNNs with a 3 × 3 neighborhood (sphere of inﬂuence r = 1), it will be extremely convenient to introduce some concise notations and terminologies for future analysis. Consider a typical cell C(i, j) ∈ Sr (i, j) as follows C(i − 1, j − 1) C(i − 1, j) C(i − 1, j + 1) C(i, j − 1) C(i, j) C(i, j + 1) C(i + 1, j − 1) C(i + 1, j) C(i + 1, j + 1) Let us examine the contributions from the two synaptic operators and the threshold items in (2.21). 1 Contributions from the feedback synaptic operator A(i, j; k, l) In view of spaceinvariance, we can write A(i, j; k, l) ykl = A(k − i, l − j)y kl k−i≤1 l− j≤1 C(k,l)∈Sr (i, j) = a−1,−1 yi−1, j−1 + a−1,0 yi−1, j + a−1,1 yi−1, j+1 a0,−1 yi, j−1 + a0,0 yi, j + a0,1 yi, j+1 a1,−1 yi+1, j−1 + a1,0 yi+1, j + a1,1 yi+1, j+1 = 1 1 ak,l yi+k, j+l (2.30) k=−1 l=−1 where amn = A(m, n) a−1,−1 = a0,−1 a1,−1 a−1,0 a0,0 a1,0 a−1,1 yi−1, j−1 a0,1 yi, j−1 a1,1 yi+1, j−1 yi−1, j yi, j yi+1, j yi−1, j+1 yi, j+1 = A Yi j yi+1, j+1 (2.31) where the 3 × 3 matrix A is called the feedback cloning template, and the symbol “” denotes the summation of dot products, henceforth called a template dot product. In 26 Notation, definitions, and mathematical foundation discrete mathematics, this operation is called “spatial convolution.” The 3 × 3 matrix Yi j in (2.31) can be obtained by moving an opaque mask with a 3 × 3 window to position (i, j) of the M × N output image Y , henceforth called the output image at C(i, j). An element akl is called a center (resp., surround) element, weight, or coefﬁcient, of the feedback template A, if and only if (k, l) = (0, 0) (resp., (k, l) = (0, 0)). It is sometimes convenient to decompose the A template as follows A = A0 + Ā (2.32) 0 0 A = 0 a0,0 0 0 0 Ā = a−1,−1 a0,−1 a1,−1 0 0 0 a−1,0 0 a1,0 a−1,1 a0,1 a1,1 where A0 and Ā are called the center and surround component templates, respectively. 2 Contributions from the input synaptic operator B(i, j; k, l) Following the above notation, we can write B(i, j; k, l)y kl = B(k − i, l − j) u kl k−i≤1 l− j≤1 C(k,l)∈Sr (i, j) = 1 1 bkl u i+k, j+l (2.33) k=−1 l=−1 b−1,−1 = b0,−1 b1,−1 b−1,0 b0,0 b1,0 b−1,1 u i−1, j−1 b0,1 u i, j−1 b1,1 u i+1, j−1 u i−1, j u i, j u i+1, j u i−1, j+1 u i, j+1 = B Ui j u i+1, j+1 (2.34) where the 3 × 3 matrix B is called the feedforward or input cloning template, and Ui j is the translated masked input image. Similarly, we can write B = B0 + B̄ 0 0 B = 0 b0,0 0 0 0 B̄ = b−1,−1 b0,−1 b1,−1 (2.35) 0 0 0 b−1,0 0 b1,0 b−1,1 b0,1 b1,1 where B0 and B̄ are called the center and surround feedforward template, respectively. 27 2.2 Mathematical foundations 3 Contribution from the threshold terms zi j = z Using the above notations, a spaceinvariant CNN is completely described by ẋi j = −xi j + A Yi j + B Ui j + z (2.36) We will usually decompose (2.36) as follows ẋi j = −xi j + a00 f (xi j ) + Ā ⊗ Yi j + B ⊗ Ui j + z g(xi j ) (2.37) wi j (t) where h i j (xi j ; wi j ) = g(xi j ) + wi j (xi j , t) (2.38) is called the rate function, g(xi j ) is called the drivingpoint (DP) component because it is closely related to a central concept from nonlinear circuit theory, and wi j (xi j , t) = Ā Yi j + B Ui j + z is called the offset level. 2.2.5 Three simple CNN classes Each CNN is uniquely deﬁned by three terms of the cloning templates {A, B, z}, which consist of 19 real numbers for a 3 × 3 neighborhood (r = 1). Since real numbers are uncountable, there are inﬁnitely many distinct CNN templates, of which the following three subclasses are the simplest and hence mathematically tractable. Deﬁnition 7: Excitatory and Inhibitory synaptic weights (Fig. 2.21) A feedback synaptic weight akl is said to be excitatory (resp., inhibitory) if and only if it is positive (resp., negative). A synaptic weight is “excitatory” (resp., inhibitory) because it makes the rate function h i j (xi j , wi j ) more positive (less positive) for a positive input, and hence increases (resp., decreases) ẋi j , namely the rate of growth of xi j (t). Deﬁnition 8: Zerofeedback (feedforward) class C (0, B, z) (Fig. 2.22) A CNN belongs to the zerofeedback class C (0, B, z) if and only if all feedback template elements are zero, i.e., A ≡ 0. Each cell of a zerofeedback CNN is described by ẋi j = −xi j + B Ui j + z (2.39) 28 Notation, definitions, and mathematical foundation (a) (A, B, z) B A Input U Output Y State X z (b) U B + uij x ij – x ij ∫ dt f( ) y ij A Y Fig. 2.21. A spaceinvariant CNN C(A, B, z) with a 3 × 3 neighborhood S1 (i, j). (a) Signal ﬂow structure of a CNN with a 3 × 3 neighborhood. The two shaded cones symbolize the weighted contributions of input and output voltages of cell C(k, l) ∈ S1 (i, j) to the state voltage of the center cell C(i, j). (b) System structure of a cell C(i, j). Arrows printed in bold mark parallel data paths from the input and the output of the surround cells u kl and ykl , respectively. Arrows with thinner lines denote the threshold, input, state, and output, z, u i j , xi j , and yi j , respectively. Deﬁnition 9: Zeroinput (Autonomous) class C (A, 0, z) (Fig. 2.23) A CNN belongs to the zeroinput class C (A, 0, z) if and only if all feedforward template elements are zero, i.e., B ≡ 0. Each cell of a zeroinput CNN is described by ẋi j = −xi j + A Yi j + z (2.40) Deﬁnition 10: Uncoupled (scalar) class C (A0 , B, z) (Fig. 2.24) A CNN belongs to the uncoupled class C (A0 , B, z) if and only if ai j = 0 except i = j, i.e., Ā ≡ 0. Each cell of an uncoupled CNN is described by a scalar nonlinear ODE which is not coupled to its neighbors: ẋi j = −xi j + a00 f (xi j ) + B Ui j + z (2.41) 29 2.2 Mathematical foundations Fig. 2.22. Zerofeedback (feedforward) CNN ∈ C(0, B, z). (a) Signal ﬂow structure of a zerofeedback CNN with a 3 × 3 neighborhood. The cone symbolizes the weighted contributions of input voltages of cells C(k, l) ∈ S1 (i, j) to the center cell C(i, j). (b) System structure of a cell C(i, j). Arrows printed in bold denotes the input signal from the surround cells. In this case, there is no selffeedback, and no couplings from the outputs of the surround cells. Fig. 2.23. Zeroinput (Autonomous) CNN ∈ C(0, B, z). (a) Signal ﬂow structure of a zeroinput CNN with a 3 × 3 neighborhood. The cone symbolizes the weighted contributions of the output voltage of cells C(k, l) ∈ S1 (i, j) to the center cell C(i, j). (b) System structure of a center cell C(i, j). Arrow printed in bold denotes the signal fedback from the outputs of the surround cells. In this case, there are no input signals. 30 Notation, definitions, and mathematical foundation Fig. 2.24. Uncoupled CNN ∈ C(0, B, z). (a) Signal ﬂow structure of an uncoupled CNN with a 3 × 3 neighborhood. The cone symbolizes the weighted contributions of the input voltages of cells C(k, l) ∈ S1 (i, j) to the center cell C(i, j). (b) System structure of a center cell C(i, j). Arrow printed in bold denotes the input signals from the surround cells. In this case, the data streams simpliﬁed into simple streams marked by thinner arrows, indicating only a “scalar” selffeedback, but no couplings from the outputs of the surround cells. So far, we have not mentioned the details of the physical or biological meaning of the various terms in the CNN equations. To highlight some of these issues, next we show a possible electronic circuit model of a cell. In Fig. 2.25, voltagecontrolled current sources are used to implement various coupling terms. These transconductances can be easily constructed on CMOS integrated circuits. The details will be discussed in Chapter 15. A very rough sketch of a typical living neuron with interacting neighbors is shown in Fig. 2.26. A more detailed discussion can be found in Chapter 16. 2.2.6 Synaptic signal flow graph representation Sometimes it will be more convenient to use a synaptic signal ﬂow graph representation3 for both the A and the B templates as shown in Figs 2.27 and 2.28, respectively. These two ﬂow graphs show explicitly the directions of the signal ﬂows from neighboring cells and their associated synaptic weights akl and bkl , respectively. Except for the symbols {a00 , akl } for the synaptic signal ﬂow graph A, and {b00 , bkl } 2.2 Mathematical foundations synaptic current sources controlled by the inputs of surround cells i– 1, j– 1 u , 0 b –1, ,1u i–1 b –1 b0,–1 bi, j–1 synaptic current sources controlled by the outputs of surround cells total fe curr edback ent total fe curr edforwa ent rd uij ,j a 1, –1 A Y ij y i–1 0 y i+ 1, j– 1 a –1, a0,1 yi, j+1 a0,–1yi, j–1 a1 i– 1, j– 1 j+1 b1,0ui+1, j u i+ 1, j– 1 b0,1ui, j+1 u i+1, b 1,1 1, –1 current summing node ij of cell C(ij) –1 , j+ 1 u 1 j+ yi ,j i–1 1,1 –1 ,– 1 a– b b ,1 + yi +1 ,j +1 a1,0 yi+1, j y –1 ,– 1 a 31 uij – xij bij uij zij input voltage of cell C(ij) internal core of cell C(ij) 1 xij + xij – aij y ij threshold current of cell C(ij) + f (xij ) 1 y ij – state voltage of cell C(ij) output voltage of cell C(ij) Fig. 2.25. Cell realization of a standard CNN cell C(i, j). All diamondshape symbols denote a voltagecontrolled current source which injects a current proportional to the indicated controlling voltage u kl or ykl , weighted by bkl or akl , respectively, except for the rightmost diamond f (xi j ) in the internal core which is a nonlinear voltage controlled current source, resulting in an output voltage yi j = f (xi j ). Notation, definitions, and mathematical foundation sensory neuron C(mn) axon ymn 32 cell body enclosed by a membrane ic nu mn rit nd b m de put in neuron C(ij) a synapse from the axon of a sensory (input) neuron (say from the “olfactory bulb”) to a dendrite of neuron C(ij) axon yij dendrite re fe curr ed en ba t ck a kl y kl neuron C(kl) axon ykl a synapse from the axon (output) of neuron C(kl) to a dendrite of neuron C(ij) Fig. 2.26. A caricature of a typical neuron C(i, j) receiving an input from a sensory neuron on the left and a neighbor neuron below through respective “synapses.” for the synaptic signal ﬂow graph B, these two signal ﬂow graphs are identical and hence easy to remember. Observe that the bold heavy edges indicate signal ﬂowing into cell C(i, j), whereas the light edges indicate signal ﬂowing out from cell C(i, j). Observe that each synaptic weight occurs exactly twice in each ﬂow graph, and that they are always associated with a pair of edges, one bold edge and one light edge, with arrows pointing in the same directions. For example, the coefﬁcient a−10 is associated with the two edges originating from the North (N) cell and terminating in the South (S) 33 2.2 Mathematical foundations (a) a−1,−1 a0,−1 a1,−1 a−1,0 a00 a1,0 a−1,1 a0,1 a1,1 NW N yi–1, j–1 NE yi–1, j a1,1 a–1,0 yi–1, j+1 a1,0 a–1,1 a1,–1 a–1,–1 a 0,1 a0,1 a00 W yi, j–1 E a0,–1 a0,–1 a1,1 a–1,1 a–1,–1 a–1,0 a1,0 a1,–1 yi+1, j–1 (b) SW yi, j+1 yi+1, j yi+1, j+1 S SE Fig. 2.27. Feedback synaptic signal ﬂow graph A associated with the A template.3 (a) The A template with selffeedback synaptic weight a00 , (b) Signal ﬂow graph A. cell. This is because the “top” cell C(i − 1, j) is North of the center cell C(i, j), which is itself North of the “bottom” cell C(i + 1, j). The same observation applies to the horizontal pairs, and all diagonal pairs of similarlydirected boldlight edges. Observe also that for each zero coefﬁcient akl = 0, or bkl = 0, two corresponding edges will disappear from the corresponding signal ﬂow graph. Hence, for templates with only a few nonzero entries, their associated synaptic signal ﬂow graphs are particularly simple. It is in such situations where useful insights can be obtained, specially when two or more such synaptic signal ﬂow graphs are interconnected to form a composite synaptic system graph. 34 Notation, definitions, and mathematical foundation (a) b−1,−1 b0,−1 b1,−1 b−1,0 b00 b1,0 b−1,1 b0,1 b1,1 NW N ui–1, j–1 NE ui–1, j b1,1 b–1,0 ui–1, j+1 b1,0 b–1,1 b1,–1 b–1,–1 b 0,1 b0,1 b00 W ui, j–1 E b0,–1 b0,–1 b1,1 b–1,1 b–1,–1 b–1,0 b1,0 b1,–1 ui+1, j–1 (b) SW ui, j+1 ui+1, j ui+1, j+1 S SE Fig. 2.28. Input synaptic signal ﬂow graph B associated with the B template. (a) B template with selfinput synaptic weight b00 . (b) Signal ﬂow graph B. 3 Characteristics and analysis of simple CNN templates 3.1 Two case studies: the EDGE and EDGEGRAY templates 3.1.1 The EDGE CNN EDGE: binary edge detection template 0 0 0 A= 0 0 0 0 0 0 −1 −1 −1 B = −1 8 −1 −1 −1 −1 z = −1 I Global task Given: static binary image P Input: U(t) = P Initial state: X(0) = Arbitrary (in the examples we choose xi j (0) = 0) Boundary conditions:1 Fixed type, u i j = 0, yi j = 0 for all virtual cells, denoted by [U] = [Y] = [0] Output: Y(t) ⇒ Y(∞) = Binary image showing all edges of P in black. Remark The Edge CNN template is designed to work correctly for binary input images only. If P is a grayscale image, Y(∞) will in general be grayscale where black pixels correspond to sharp edges, nearblack pixels correspond to fuzzy edges, and nearwhite pixels correspond to noise. II Local rules static input u i j → steady state output yi j (∞) 1 white pixel → white, independent of neighbors 2 black pixel → white, if all nearest neighbors are black 3 black pixel → black, if at least one nearest neighbor is white 4 black, gray or white pixel → gray, if nearest neighbors are gray 35 36 Characteristics and analysis of simple CNN templates III Examples EXAMPLE 3.1: Image size: 15 × 15 (see also Fig. 3.1) input initial state t = 0.0 t = 0.5 A C B t = 1.0 t = 2.0 ⇑ –1.0 ⇑ 0.0 t = 3.0 ⇑ 1.0 Snapshots are shown in gray scale with 256 levels. Integration time step = 0.1. time t Fig. 3.1. Cell transient at three different locations in image of example 3.1. —— ——: state variable xi j ; ——: output variable yi j ; ***: output and state are the same. 37 3.1 The EDGE and EDGEGRAY templates time t Fig. 3.1. Continued. EXAMPLE 3.2: Image size: 100 × 100 input t = 1.0 state, t = 0.0 t = 2.0 t = 3.0 EXAMPLE 3.3: Image size: 100 × 100 input t = 0.5 final output 38 Characteristics and analysis of simple CNN templates EXAMPLE 3.4: Image size: 100 × 100 input final output IV Mathematical analysis State and output equation ẋi j = g(xi j ) + wi j = h i j (xi j , wi j ) yi j = f (xi j ) (3.1) where g(xi j ) = −xi j (3.2) wi j = −1 + 8u i j − u i+1, j−1 − u i+1, j − u i+1, j+1 − u i, j−1 − u i, j+1 − u i−1, j−1 −u i−1, j − u i−1, j+1 − 1 + 8u i j − u kl (3.3) kl∈S1 (i, j) kl=i j We will often refer to the loci of h i j (xi j ; wi j ) associated with the state equation ẋi j = h i j (x i j ; wi j ) as the drivingpoint (DP) plot of cell C(i, j), because this plot has a special signiﬁcance in “nonlinear circuit theory”; namely, it is just the drivingpoint characteristics of the nonlinear resistive oneport N R connected across the capacitor with the port current assumed to be directed away from N R . Property 1 For any initial state xi j (0) ∈ R, for any constant input u i j ∈ R, the circuit is completely stable in the sense that all trajectories, independent of initial conditions, tend to an equilibrium point of Eq. (3.1). In particular, yi j (∞) = limt→∞ yi j (t) ∈ R. Moreover, if u i j ∈ {−1, 1}, then y(∞) ∈ {−1, 1}. Proof: Consider the DP plot deﬁned by h i j (x i j ; wi j ) = −xi j + wi j in Fig. 3.2. Since any trajectory (i.e. solution) of the state equation ẋi j = h i j (x i j ; wi j ) originating from any 39 3.1 The EDGE and EDGEGRAY templates xij = hij (x ij, wij ) Γx xij = hij (x ij ,wij ) Γx wij > 1 Q –1 x Q1 xij = hij (x ij , wij ) Γx Q1 xij –1 Q2 1 xij xQ –1 xij xQ2 wij < –1 yij yij Γy Γy Q1 1 yQ xij –1 (a) Q –1 (b) yij Γy yQ2 = 1 yQ2 Q2 xij xij (b) Fig. 3.2. The dynamic route corresponding to the edge detection template. (a) wi j ≤ −1; (b) −1 < wi j < 1; (c) wi j ≥ 1. initial state must move along in accordance with the direction indicated, the directed loci x in Fig. 3.2 is called the state dynamic route. The intersection Q of x with the horizontal axis is called an equilibrium point. Observe from the three dynamic routes in Fig. 3.2 that all trajectories originating from any initial state tend to the equilibrium xi j = xQ . The output yi j can be obtained from the associated output dynamic route y . It follows from y that wi j , if wi j  < 1 y(∞) = (3.4) 1, if wi j ≥ 1 −1, if w ≤ −1 ij Property 2 (Local rule 1) If u i j = −1, then yi j (∞) = −1, independent of u kl ∈ {−1, 1}, k, l ∈ S1 (i, j). Proof: Since −8 ≤ kl∈S1 (i, j) u kl ≤ 8, it follows that kl=i j wi j = −1 + 8( − 1) − u kl ≤ −1 (3.5) kl∈Sl (i, j) kl=i j Eqs (3.4) and (3.5) ⇒ yi j (∞) = −1. 40 Characteristics and analysis of simple CNN templates Property 3 (Local rule 2) If u i j = 1 and u kl = 1 for all k, l ∈ S1 (i, j), then yi j (∞) = −1. Proof: Since kl∈S1 (i, j) u kl = 8 kl=i j wi j = −1 + 8(1) − u kl = −1 (3.6) Eqs (3.4) and (3.6) ⇒ yi j (∞) = −1. kl∈S1 (i, j) kl=i j Property 4 (Local rule 3) If u i j = 1 and if u αβ = −1 for some C(α, β) ∈ S1 (i, j), then yi j (∞) = 1. Proof: Since kl∈S1 (i, j) u kl ≤ 6 kl=i j wi j = −1 + 8(1) − u kl ≥ 1 (3.7) Eqs (3.4) and (3.7) ⇒ yi j (∞) = 1. kl∈S1 (i, j) kl=i j Property 5 (Local rule 4) If u i j ∈ [−1, 1] and u kl ∈ [−1, 1] , k, l ∈ S1 (i, j), then yi j (∞) ∈ [1, 1]. Proof: Since kl∈S1 (i, j) u kl ∈ [−8, 8] and this sum is not an integer in general, it follows kl=i j that wi j ∈ [−17, 15] and is in general not an integer. 3.1.2 The EDGEGRAY CNN One objection to the Edge CNN template in Section 3.1.1 is that it works well only for binary input images. For grayscale input images, the output may not be a binary image. Our next CNN template called Edgegray will overcome this problem by accepting grayscale input images and always converging to a binary output image. Any imperfection in the input which we called “noise” will also converge to a binary output. One application of this CNN template is to convert grayscale images into binary images, which can then be used as inputs to many imageprocessing tasks which require a binary input image. From an efﬁcient informationprocessing point of view, 41 3.1 The EDGE and EDGEGRAY templates grayscale images contain too much redundancy and require many more “bits” than binary images. Consequently, in most imageprocessing systems, the grayscale input image at the front end is quickly converted into a binary image which contains only the relevant information to be extracted, the most important of which being the binary edges. EDGEGRAY: grayscale edge detection template 0 0 0 A= 0 2 0 0 0 0 −1 −1 −1 B = −1 8 −1 −1 −1 −1 z = −0.5 I Global task Given: static grayscale image P Input: U(t) = P Initial state: X(0) = 0 Output: Y(t) ⇒ Y(∞) = Binary image where the black pixels correspond to pixels lying on sharp edges of P, or to fuzzy edges deﬁned roughly to be the union of gray pixels of P which form onedimensional (possibly short) line segments, or arcs, such that the intensity of pixels on one side of the arc differs signiﬁcantly from the intensity of neighbor pixels on the other side of the arc. Remarks 1 Some “edges” in the output may arise due to poor input image quality, or to artifacts introduced by sensors due to reﬂections and improper illuminations. Since the black pixels resulting from these situations are not edges, they must be regarded as noise.3 2 The above template B is an example of an important class of input templates, called a Laplacian template, having the properties that all “surround” input synaptic weights are inhibitory and identical, i.e., bkl = b < 0, but the center synaptic weight is excitatory and the average of all input synaptic weights is zero; i.e., kl=0 bkl + b00 = 0. II Local rules Ui j (0) → yi j (∞) 1 white pixel → white, independent of neighbors 2 black pixel → white, if all nearest neighbors are black 3 black pixel → black, if at least one nearest neighbor is white 4 gray pixel → black, if the Laplacian ∇ 2 Ui j = B Ui j > 0.5 and xi j (0) = 0 5 gray pixel → white, if the Laplacian ∇ 2 Ui j < 0.5 and xi j (0) = 0 42 Characteristics and analysis of simple CNN templates black, if the Laplacian = 0.5 and x(0) > 0 white, if the Laplacian = 0.5 and x(0) < 0 6 gray pixel → if the Laplacian = 0.5 and x(0) = 0 0, in this case, yi j (∞) = 0 is unstable. III Examples EXAMPLE 3.5: Image size: 15 × 15 (shows the transient waveforms at pixel A, B, and C) t = 0, input t = 0, state t=5 A C B t = 10 t = 20 t = 30 time t Fig. 3.3. Cell state and output transients for 30 steps at three different locations in the image of example 3.5 represented by bold and thinner lines, respectively. 43 3.1 The EDGE and EDGEGRAY templates time t Fig. 3.3. Continued. EXAMPLE 3.6: Image size: 100 × 100 t = 0, input t = 0, state t=5 t = 10 t = 20 t = 30 EXAMPLE 3.7: Image size: 100 × 100 input final output 44 Characteristics and analysis of simple CNN templates EXAMPLE 3.8: Noisy image, image size: 100 × 100 input final output IV Mathematical analysis State and output equations ẋi j = g(xi j ) + wi j = h i j (xi j ; wi j ) yi j = f (xi j ) (3.8) where g(xi j ) = −xi j + a00 f (xi j ) = −xi j + 2 f (xi j ) = −xi j + xi j + 1 − xi j − 1 (3.9) wi j = −0.5 + 8u i j − u i+1, j−1 − u i+1, j − u i+1, j+1 − u i, j−1 − u i, j+1 − u i−1, j−1 − u i−1, j − u i−1, j+1 = −0.5 + 8u i j − u kl (3.10) kl∈S1 (i, j) kl=i j Property 6 For any initial state xi j (0), for any constant input u i j ∈ [−1, 1], the CNN is completely stable in the sense that all trajectories of Eq. (3.1) tend to some equilibrium point whose location in general depends on the initial state xi j (0), i = 1, 2, . . . , M, j = 1, . . . , N . In particular yi j (∞) = 1, if wi j > 0 and wi j = 1 = −1, if wi j < 0 and wi j = −1 (3.11) 45 3.1 The EDGE and EDGEGRAY templates 1 if wi j = 0, then yi j (∞) = 1, if xi j (0) ∈ (−∞, −2) ∪ (0, 2] yi j (∞) = −1, if xi j (0) ∈ [−2, 0) ∪ (2, ∞) = 0, if xi j (0) = 0 (3.12) In this case, the equilibrium point Q− is unstable. 2 if wi j = 1, then if xi j (0) > −1 yi j (∞) = 1, = −1, if xi j (0) ≤ −1 3 if wi j = −1, then yi j (∞) = −1, = 1, if xi j (0) < 1 if xi j (0) ≥ 1 (3.13) (3.14) In this case, the equilibrium point Q0 is unstable. Proof of Property 1 and Rules 4–6: The ﬁrst step is to examine the internal DP plot given by Eq. (3.2). Although this can be easily sketched directly from the explicit equation given in Eq. (3.2), it is instructive for our future analysis of more complicated CNNs to construct this curve graphically by adding the two components −xi j and 2 f (xi j ) as shown in the upper part of Fig. 3.4. Now since wi j = −0.5 + B Ui j and assuming the Laplacian ∇ 2 Ui j = B Ui j = 0.5 it follows that the offset level wi j = 0 and hence h i j (xi j ; wi j ) = gi j (xi j ) In this case, the state dynamic route x is identical to the internal DP plot gi j (xi j ), except for the addition of arrowheads which indicate the direction a trajectory from any point on x must follow. It follows that of the three equilibrium points {Q− , Q0 , Q+ }, only Q− and Q+ are locally asymptotically stable. To determine the asymptotic output yi j (∞) = limt→∞ yi j (t), we simply sketch the output dynamic route y directly below x with the vertical axes aligned with each other, as shown in Fig. 3.4. 46 Characteristics and analysis of simple CNN templates –xij Γx hij (xij , 0) 2 f (xij ) 2 Central segment (linear region) 1 Q+ Q– Left segment –1 –2 Q0 1 0 xij 2 Right segment –1 gij (xij ) –2 yij Positive saturation region 1 Q+ Q0 –2 –1 0 1 2 Γy xij Q– –1 Negative saturation region Fig. 3.4. State and output dynamic routes for the special case of zero offset level (wi j = 0). Since x in Fig. 3.4 corresponds to the case ∇ 2 Ui j = 0.5, Local rule 6 follows directly from this dynamic route. For future analysis, it is crucial to note here that whenever the equilibrium point lies on the left segment, where xi j < −1, or on the right segment, where xi j > 1, the output saturates and is always equal to yi j (∞) = −1, or yi j (∞) = +1, respectively. Now for wi j = 0, the external DP plot deﬁned by h i j (xi j ; wi j ) = gi j (xi j ) + wi j can be simply obtained by using the internal DP plot gi j (xi j ) from Fig. 3.4 as a drafting template and translating it along the vertical direction upwards (resp., downwards) by an amount equal to the offset level wi j if wi j > 0 (resp., wi j < 0). This geometrical interpretation is quite general and extremely useful – this is the reason for calling wi j the offset level. Since ẋi j = h i j (xi j ; wi j ), the dynamic route x associated with the 47 3.1 The EDGE and EDGEGRAY templates hij (xij , wij ) hij (xij , wij ) Γx 1 –1 0 –1 Γx (xij (0), wij ) (xij (0), wij ) Q– Q 0 xij Q– 1 –1 0 1 Q+ xij –1 (d) 0 < wij < 1 (a) wij < –1 hij (xij , wij ) Q– 1 –1 hij (xij , wij ) Γx Q+ 0 xij 1 –1 (xij (0), wij ) 0 Q– 1 –1 Γx (xij (0), wij ) –2 1 –1 Q+ xij (e) wij = 1 (b) wij = –1 hij (xij , wij ) hij (xij , wij ) 1 Q– –1 Γx 1 Q+ 0 0 Q10 –1 (xij (0), wij ) Γx (xij (0), wij ) xij –1 0 1 xij Q+ (f) 1 < wij < ∞ (c) –1 < wij < 0 Fig. 3.5. State dynamic route for wi j = 0. rate function h i j (xi j ; wi j ) for each of the six mutually exclusive cases (which covers the entire range of wi j = 0) is shown in Figs 3.5(a)–(f), respectively. Observe that any trajectory originating from any point on the upper (resp., lower) half plane must move towards right (resp., left) and settle on the right (resp., left) segment. Hence, at equilibrium the output is always binary: yi j (∞) = +1, or −1. Now since wi j = −0.5 + ∇ 2 Ui j > 0, if ∇ 2 Ui j > 0.5, then the associated state dynamic route is given by Figs 3.5(d)–(f), where all trajectories originating from xi j (0) = 0 tend to Q+ . Since xi j (Q+ ) > 1, we have yi j (∞) = 1, which implies Local rule 4. Similarly, Local rule 5 (which corresponds to ∇ 2 Ui j < 0.5, or equivalently wi j < 0) follows from the state dynamic routes shown in Figs 3.5(a)–(c). 48 Characteristics and analysis of simple CNN templates Proof of Local rules 1–3: If u i j = −1, then wi j = −0.5 + 8(−1) − u kl < 0, for all u kl ∈ [−1, 1]. kl∈S1 (i, j) kl=i j Hence, Local rule 1 then follows from Eq. (3.8), since the trajectories move to Q− . If u i j = 1, and u kl = 1, for all kl ∈ S1 (i, j), then wi j = −0.5 + 8(1) − u kl = −0.5 < 0 kl∈S1 (i, j) kl=i j Hence, Local rule 2 then follows from Eq. (3.8), since the trajectories move to Q− . If u i j = 1, and there exist u αβ = −1, then u kl ≥ 1.5, for all u kl ∈ [−1, 1]. wi j = −0.5 + 8(1) + 1 − kl∈S1 (i, j) kl=i j,kl=αβ Hence, Local rule 3 then follows from Eq. (3.4). V Basins of attraction Fig. 3.5 shows that the EDGEGRAY CNN has a unique equilibrium point Q− if wi j < −1 (Fig. 3.5(a)), or Q+ if wi j > 1 (Fig. 3.5(f)). In these cases, all trajectories xi j (t) will tend to a unique equilibrium point, independent of the initial states xi j (0). A CNN operating under this initialstateindependent condition is said to be globally asymptotically stable, or monostable for brevity, and the associated equilibrium point is called a global point attractor Q. The union of all initial states B (Q) whose corresponding trajectories tend to Q is called the Basin of attraction of Q. In the above case we have simply B (Q− ) = B (Q+ ) = R, the real line. Consider next the two typical cases wi j ∈ (−1, 0) and wi j ∈ (0, 1), as shown in Figs 3.5(c) and 3.5(d), where there are two locally stable equilibrium points Q− and Q+ , respectively. However, unlike the monostable case, which of the two equilibrium points the trajectory will converge to depends on the initial state xi j (0). In both Figs 3.5(c) and 3.5(d), the basin of attraction of Q− is given by all points lying to the left of the unstable equilibrium point Q0 ; namely, B (Q− ) = {xi j : −∞ < xi j < xQ0 }. Similarly, the basin of attraction of Q+ is given by B (Q+ ) = {xi j : x Q 0 < xi j < ∞}. In this case, the unstable equilibrium point Q0 separates the set of all initial states xi j (0) ∈ R into two basins of attraction and the CNN is said to be bistable. Observe that the initial state X(0) = 0 which we have prescribed for the EDGEGRAY CNN guarantees that the trajectories corresponding to any input grayscale image will converge to the correct output image. Finally, consider the two singular cases wi j = −1 and wi j = 1, as shown in Figs 3.5(b) and 3.5(e), where there are only two equilibrium points. In these cases, only one 49 3.2 Three quick steps for sketching the shifted DP plot equilibrium point is locally stable; namely, Q− in Fig. 3.5(b) with a basin of attraction B (Q− ) = {xi j : −∞ < xi j < xQ+ } and Q+ in Fig. 3.5(e) with a basin of attraction B (Q+ ) = {xi j : xQ− < xi j < ∞}. The equilibrium points Q+ in Fig. 3.5(b) and Q− in Fig. 3.5(e) are said to be semistable because they lie on the boundaries of these basins so that arbitrarily small perturbations will cause the trajectories to diverge away from the basins. Since “noise” is inevitable in any hardware realization, or computer simulation, these two semistable equilibrium points are not observable in practice and are, therefore, practically speaking, unstable. 3.2 Three quick steps for sketching the shifted DP plot Since the most useful tool for studying the nonlinear dynamics of any uncoupled CNN is to analyze its state dynamic route x it is essential that we develop the skill to quickly sketch the shifted DP plot x (wi j ), which, in general, depends on both the threshold z i j and the inputs u kl ∈ Sr (i, j) of all cells belonging to the sphere of inﬂuence Sr (i, j). The following three simple steps are all that is needed: Given: threshold z i j and inputs u kl ∈ Sr (i, j). Step 1: Calculate the slope of the middle segment s00 = a00 − 1 and the offset level wi j = z i j + B Ui j . Step 2: Draw a straightline segment with slope equal to s00 at the point ẋi j = wi j on the vertical axis and ends at xi j = −1 and xi j = 1, respectively. The two end points are the left and the right breakpoints of the shifted DP plot. Step 3: Draw a half line with slope equal to −1 starting from each breakpoint, and tending to inﬁnity in each direction. xij Left saturation region Central linear region + P (Right breakpoint) slope = s00 = a00 – 1 –1 slope = –1 0 1 xij xij = wij slope = –1 – P (Left breakpoint) Right saturation region Fig. 3.6. A typical shifted DP plot x (wi j ). 50 Characteristics and analysis of simple CNN templates 3.3 Some other useful templates Our object in this section is to select a gallery of CNN templates which can be analyzed mathematically and explained. Some are specially developed to illustrate a particular property – mainly for pedagogical values – and are not necessarily the best choice for the intended tasks. These templates will be analyzed in the order of their tractability and complexity. Each CNN is carefully chosen to illustrate either a new paradigm, mechanism, or application. For ease of reference, we will always follow a consistent style: each CNN will be identiﬁed by a code name (which may not be very meaningful) copied from the CNN template library, together with an expanded name which suggests the task it is designed to implement. This will be followed by a listing of (A, B, z) templates, and the following standard sections: I Global task A nontechnical description will be given of the input–output image transformation at the complete image level. II Local rules A precise recipe of how an input pixel transforms into an output pixel. Ideally, these local rules must be complete in the sense that each output pixel can be uniquely determined by applying these rules to the state and input of all pixels within that sphere of inﬂuence. The local rules may sometimes be redundant if they help to simplify the interpretation of the recipe, provided they are consistent (do not contradict each other). The local rule may be more general than needed to specify the global task. For example, it may apply to a grayscale input even if the global task speciﬁes only binary inputs. III Examples Several examples will be given. The ﬁrst example will include: (a) The input picture U and initial state X(0). (b) Several consecutive snapshots in time until the transient settles down to a static output image Y(∞) at t = t∞ , where t∞ is called the transient settling time. (c) Time waveforms of both state xi j (t) and output yi j (t) at several strategically identiﬁed points on the output image Y(t) will be given. The time axis is labeled in units of the CNN time constant τCNN . For current VLSI technology, 30 ns ≤ τCNN ≤ 200 ns (ns: nanosecond). The transient settling time can be read off directly from these waveforms by multiplying t∞ with τCNN . (d) The ﬁrst example will be repeated for a scaledup array (usually ten times larger in each direction) in order to compare their settling times. IV Mathematical analysis Ideally, a rigorous mathematical proof will be given for each local rule. Whenever this is not available (either because a proof has not yet been developed, or the rules do not 51 3.3 Some other useful templates always hold and therefore need modiﬁcation) an intuitive proof, often supplemented by various numerical studies, will be given. 3.3.1 CORNER: convex corner detection template 0 0 0 A= 0 2 0 0 0 0 −1 −1 −1 B = −1 8 −1 −1 −1 −1 z = −8.5 I Global task Given: static binary image P Input: U(t) = P Initial state: X(0) = 0 Output: Y(t) ⇒ Y(∞) = Binary image, where black pixels correspond to convex corners in P (where, roughly speaking, a black pixel is a convex corner if it is part of a convex boundary line of the input image). II Local rules u i j (0) → yi j (∞) 1 white pixel → white, independent of neighbors 2 black pixel → black, if and only if it has three or fewer black nearest neighbors (or equivalently ﬁve or more white nearest neighbors) III Examples EXAMPLE 3.9: Image size: 15 × 15 input initial state output, t = 0.2 A B C t = 0.4 t = 0.6 Normalized time unit tu = τCNN . t = 1.0 52 Characteristics and analysis of simple CNN templates EXAMPLE 3.10: Image size: 100 × 100 input initial state output, t = 0.2 t = 0.4 t = 0.6 t = 1.0 EXAMPLE 3.11: Realistic scene (100 × 100) input final output EXAMPLE 3.12: Corner template for image containing pixel level textures (50 × 50) input final output 53 3.3 Some other useful templates time t Fig. 3.7. Cell state and output transients for 30 equidistant time steps at three different locations in ——: state variable xi j ; ——: output variable yi j . the image of example 3.9. —— IV Mathematical analysis Since the EDGEGRAY and the CORNER CNN have the same A template, their internal DP plots gi j (xi j ) are identical, as already derived earlier in Fig. 3.5(a) (for the EDGEGRAY template). Moreover, since they have the same B template, the output of the CORNER CNN is also given by Eq. (3.4) of the EDGEGRAY CNN; namely if wi j > 0 and wi j = 1 yi j (∞) = 1, = −1, if wi j < 0 and wi j = −1 (3.15) 54 Characteristics and analysis of simple CNN templates where in this case wi j = −8.5 + 8u i j − u kl (3.16) kl∈S1 (i, j) kl=i j Now, since u i j = −1 implies wi j < 0 independent of u kl , it follows that any white input pixel must map into a white output pixel (Local rule 1). It remains to analyze the case where u i j = 1 (black). In this case, Eq. (3.16) becomes wi j = −0.5 − ( pb − pw ) (3.17) where pb and pw denote, respectively, the total number of black and white surround (nearest neighbor) pixels of the center cell C(i, j). Since pb + pw = 8, Eq. (3.17) implies wi j = −0.5 − (2 pb − 8) = 7.5 − 2 pb = −0.5 − (8 − 2 pw ) = −8.5 + 2 pw (3.18) It follows from Eq. (3.18) that wi j < 0, if pb ≥ 4 (or, pw ≤ 4) > 0, if pb ≤ 3 (or, pw ≥ 5) (3.19) Hence, a black input pixel will map to a black output pixel if and only if it has three or less black surround cells, or it has ﬁve or more white surround cells (Local rule 2). It is interesting to observe that the nonlinear dynamics of the CORNER CNN tend to extract one pixelwide horizontal and vertical edges which form the boundary of a square (e.g., see output image at t = 0.4). In other words, the CORNER CNN seems to exhibit some intelligence in selforganization by programming itself to carry out the prescribed global task in two steps: (1) extract horizontal and vertical edges at the perimeter of a square, and (2) extract the extreme “end” pixel of these edges. This fascinating selfprogramming phenomenon can be explained by examining carefully the time evolution of the transient process. 3.3.2 THRESHOLD: grayscale to binary threshold template 0 0 0 A= 0 2 0 0 0 0 0 0 0 B= 0 0 0 0 0 0 z = −z ∗ , 55 3.3 Some other useful templates I Global task Given: static grayscale image P and threshold z ∗ Input: U(t) = arbitrary or default to U(t) = 0 Initial state: X(0) = P Output: Y(t) ⇒ Y(∞) = binary image when all pixels P with grayscale intensity pi j > z ∗ becomes black. II Local rules xi j (0) → yi j (∞) 1 xi j (0) < z ∗ → white, independent of neighbors 2 xi j (0) > z ∗ → black, independent of neighbors 3 xi j (0) = z ∗ → z ∗ , assuming zero noise III Examples EXAMPLE 3.13: Image size: 63 × 63 input initial state output, t = 0.1 t = 0.2 t = 0.3 t = 0.5 Normalized time unit tu = τCNN , z ∗ = −0.4. 56 Characteristics and analysis of simple CNN templates EXAMPLE 3.14: Image size: 63 × 63 input output, z* = 0.8 output, z* = 0.4 output, z* = 0.0 output, z* = –0.4 output, z* = –0.8 EXAMPLE 3.15: Image size: 128 × 128 input output, z* = 0.0 output, z* = 0.5 output, z* = –0.5 57 3.3 Some other useful templates EXAMPLE 3.16: Image size: 100 × 100 input output, z* = 0.5 output, z* = 0.0 output, z* = –0.5 Observe that the last two examples show that any image P can be transformed into a completely black image by a THRESHOLD template with z ∗ = −4, or a completely white image by choosing z ∗ = 4. Since these two transformations are quite useful for many imageprocessing tasks, we have recognized their importance by classifying them as separate CNNs in the CNN template Library under the names FILBLACK and FILWHITE, respectively, which we reproduce in Section 3.3.3. IV Mathematical analysis (for THRESHOLD) Since bkl = 0, wi j = −z ∗ , there is only one shifted DP plot for each threshold z ∗ , as shown in Fig. 3.8, independent of the inputs of the neighbors (which is arbitrary for this template). It follows from the dynamic route shown in Fig. 3.8. that yi j (∞) = −1, = 1, = z∗, if xi j (0) < z ∗ (Local rule 1) if xi j (0) > z∗ (Local rule 2) if xi j (0) = z∗ (Local rule 3) Observe that yi j (∞) = z ∗ when xi j (0) = z ∗ because xi j = z ∗ in Fig. 3.8 is an equilibrium point (Q0 ). However, since Q0 is unstable, any “noise” x would eventually drive the “theoretical” grayscale output to either black (if the noise 58 Characteristics and analysis of simple CNN templates slope = –1 slope = –1 slope = 1 Q+ Q– –1 0 xij 1 –z* Q 0(xij = z*) –1 Γx (wij) Fig. 3.8. Shifted DP plot x (wi j ) and its dynamic route. xi j (0) > 0), or white (if the noise xi j (0) < 0). Hence, in practice, the above THRESHOLD CNN will always give a binary output image, assuming one waits long enough for the transients to settle down. 3.3.3 FILBLACK and FILWHITE templates FILBLACK: Grayscale to black CNN 0 0 0 A= 0 2 0 0 0 0 0 0 0 B= 0 0 0 0 0 0 z= 4 I Global task Given: static grayscale image P Input: U(t) = arbitrary or default to U(t) = 0 Initial state: X(0) = P Output: Y(t) ⇒ Y(∞) = black image (all pixels are black) II Local rules xi j (0) → yi j (∞) Arbitrary xi j (0) ∈ (−∞, ∞) → yi j (∞) = 1 59 3.3 Some other useful templates III Example EXAMPLE 3.17: Image size 128 × 128 Input Output, z = 4.0 FILWHITE: Grayscale to white CNN 0 0 0 A= 0 2 0 0 0 0 0 0 0 B= 0 0 0 0 0 0 z = −4 I Global task Given: static grayscale image P Input: U(t) = arbitrary or default to U(t) = 0 Initial state: X(0) = P Output: Y(t) ⇒ Y(∞) = white image (all pixels are white) II Local rules xi j (0) → yi j (∞) Arbitrary xi j (0) ∈ (−∞, ∞) → yi j (∞) = −1 III Example EXAMPLE 3.18: Image size 128 × 128 Input Output, z = – 4.0 60 Characteristics and analysis of simple CNN templates 3.3.4 LOGNOT: Logic NOT and set complementation (P → P̄ = Pc ) template 0 0 0 A= 0 1 0 0 0 0 0 0 0 B = 0 −2 0 0 0 0 z= 0 I Global task Given: static binary image P Input: U(t) = P Initial state: X(0) = 0 Output: Y(t) ⇒ Y(∞) = binary image where each black pixel in P becomes white, and vice versa. In settheoretic or logic notation: Y(∞) = Pc = P̄, where the bar denotes the “Complement” or “Negation” operator. II Local rules xi j (0) → yi j (∞) 1 black pixel → white pixel, independent of initial states 2 white pixel → black pixel, independent of initial states III Example EXAMPLE 3.19: Image size: 15 × 15 input initial state output, t = 0.1 t = 0.2 t = 0.3 t = 0.5 Normalized time unit tu = tCNN . IV Mathematical analysis (for LOGNOT) Since s00 = a00 − 1 = 0, and wi j = −2u i j , where u i j ∈ {−1, 1}, only the two shifted DP plots shown in Figs 3.9(a) and 3.9(b) need to be considered. The above dynamic routes show that the LOGNOT template gives rise to a globally asymptotically stable 61 3.3 Some other useful templates xij xij Q– Q+ –1 1 0 xij –1 0 1 xij –1 –2 (b) uij = –1 ⇒ w ij = 2 (a) u ij = 1⇒ w ij = –2 Fig. 3.9. Shifted DP plots for the cases u i j = 1 and u i j = −1. (monostable) CNN provided the inputs are binary. Local rules 1 and 2 follow directly from Figs 3.9(a) and 3.9(b), respectively. Remarks Note that since the middle segment of the shifted DP plot in Figs 3.9 is horizontal, an ambiguous situation can occur if the inputs are not binary. In particular, when u i j = 0, the horizontal segment coincides with the closed unit interval [−1, 1] of the xi j axis, which implies that all points xi j ∈ [−1, 1] are equilibrium points. Moreover, this continuum of nonisolated equilibrium points possesses a weaker form of stability in the sense that if we perturb any equilibrium point on the interior of [−1, 1] by a sufﬁciently small amount so that it remains within [−1, 1], then the state of this CNN will assume this new position, unlike the previous semistable case where the trajectory eventually moves to another point outside of [−1, 1]. In other words, yi j (∞) can assume any grayscale value −1 ≤ yi j ≤ 1. Although the above singular situation rarely occurs in practical CNNs, the possibility of such weird phenomena can greatly complicate the derivation of a rigorous proof of many quite general mathematical properties. Even worse, it can make some such seemingly reasonable properties incorrect. Consequently, it will often be advisable, if not necessary, to add the reasonable hypothesis that the class of CNNs being considered for a rigorous mathematical proof has only isolated, and hence a ﬁnite number1 of equilibrium points. 3.3.5 LOGOR: Logic OR and set union ∪ (disjunction ∨) template 0 0 0 A= 0 3 0 0 0 0 0 0 0 B= 0 3 0 0 0 0 z= 2 62 Characteristics and analysis of simple CNN templates I Global task Given: two static binary images P1 and P2 Input: U(t) = P1 Initial state: X(0) = P2 Output: Y(t) ⇒ Y(∞) = binary output of the logic operation OR between P1 and P2 . In logic notation, Y(∞) = P1 ∨ P2 , where ∨ denotes the “disjunction” operator. In settheoretic notation, Y(∞) = P1 ∪ P2 , where ∪ denotes the “set union” operator. II Local rules u i j (0) xi j (0) → yi j (∞) 1 white pixel white pixel → white, independent of neighbors 2 white pixel black pixel → black, independent of neighbors 3 black pixel white pixel → black, independent of neighbors 4 black pixel black pixel → black, independent of neighbors III Examples EXAMPLE 3.20: Image size: 15 × 15 input initial state output, t = 0.1 t = 0.2 t = 0.3 t = 0.5 Normalized time unit tu = tCNN . 63 3.3 Some other useful templates EXAMPLE 3.21: Image size: 100 × 100 input t = 0.2 initial state t = 0.3 output, t = 0.1 t = 0.5 IV Mathematical analysis (for LOGOR) Since this is our ﬁrst template which belongs to the domain of “Boolean algebra,” or “switching logic circuits,” where the numbers {0, 1} are used not in a numeric sense, but in a symbolic sense, it is particularly important to translate any logic truth table represented in Boolean variables into an equivalent CNN truth table represented in numerical values before any numerical calculation is made. The reason we will use both logic truth tables and CNN truth tables in this book is to avail ourselves of the large body of results in the literature on Boolean functions and their numerous combinatorial properties. To illustrate the importance of distinguishing these two equivalent truth table representations, let us consider the logic truth table 3.1(a) and its equivalent CNN truth table 3.1(b) for deﬁning the LOGOR CNN. Let us now derive the dynamic routes associated with the LOGOR templates. Since s00 = a00 − 1 = 2 and wi j = 2 + 3u i j , only the two shifted DP plots shown in Figs 3.10(a) and 3.10(b) are needed. Consider ﬁrst the case u i j = −1 (white) so that the dynamic route is given by Fig. 3.10(a). In this case, if: 1 xi j (0) = −1 (white), then yi j (∞) = −1 (white), which is Local rule 1. 64 Characteristics and analysis of simple CNN templates Table 3.1. Two equivalent representations of the LOGOR template. (b) CNN truth table (a) Logic truth table for OR operation. for OR operation. 0 1 2 3 U X(0) Y(∞) 0 0 1 1 0 1 0 1 0 1 1 1 0 1 2 3 U X(0) Y(∞) −1 −1 −1 1 −1 1 −1 1 −1 1 1 1 xij xij slope = 2 slope = 2 5 Q– Q+ –1 0 slope = –1 –1 –3 1 xij slope = –1 slope = –1 Q0 slope = –1 (a) uij = –1 ⇒ w ij = –1 Q+ –1 0 xij 1 (b) uij = 1 ⇒ w ij = 5 Fig. 3.10. Dynamic routes of the LOGOR CNN. 2 xi j (0) = 1 (black), then yi j (∞) = 1 (black), which is Local rule 2. Consider next the case u i j = 1 (black) so that the dynamic route is given by Fig. 3.10(b). In this case the CNN is globally asymptotically stable and yi j (∞) = 1, regardless of the initial conditions, which implies Local rule 3 and Local rule 4. 3.3.6 LOGAND: Logic AND and set intersection ∩ (conjunction ∨) template 0 0 0 A = 0 1.5 0 0 0 0 0 0 0 B = 0 1.5 0 0 0 0 z = −1.5 65 3.3 Some other useful templates I Global task Given: two static binary images P1 and P2 Input: U(t) = P1 Initial state: X(0) = P2 Output: Y(t) ⇒ Y(∞) = binary output of the logic operation “AND” between P1 and P2 . In logic notation, Y(∞) = P1 ∧P2 , where ∧ denotes the “conjunction” operator. In settheoretic notation, Y(∞) = P1 ∩ P2 , where ∩ denotes the “intersection” operator. II Local rules u i j (0) xi j (0) → yi j (∞) 1 white pixel white pixel → white, independent of neighbors 2 white pixel black pixel → white, independent of neighbors 3 black pixel white pixel → white, independent of neighbors 4 black pixel black pixel → black, independent of neighbors III Examples EXAMPLE 3.22: Image size: 15 × 15 input initial state t = 0.3 t = 0.5 Normalized time unit tu = tCNN . output, t = 0.15 t = 0.8 66 Characteristics and analysis of simple CNN templates EXAMPLE 3.23: Image size: 100 × 100 input initial state t = 0.4 t = 0.6 output, t = 0.2 t = 1.0 IV Mathematical analysis (for LOGAND) The logic and CNN truth tables for the LOGAND CNN are shown in Tables 3.2(a) and 3.2(b), respectively. Table 3.2. Two equivalent representations of the LOGAND template. (b) CNN truth table (a) Logic truth table for AND operation. for AND operation. 0 1 2 3 U X(0) Y(0) 0 0 1 1 0 1 0 1 0 0 0 1 0 1 2 3 U X(0) Y(0) −1 −1 1 1 −1 1 −1 1 −1 −1 −1 1 Let us now derive the dynamic routes associated with the LOGAND templates. Since s00 = a00 − 1 = 0.5 and wi j = −1.5 + 1.5u i j , only the two shifted DP plots shown in Figs 3.11(a) and 3.11(b) are needed. Consider ﬁrst the case u i j = −1 (white) so that the dynamic route is given by 67 3.3 Some other useful templates xij xij Q– –1 –1 0 –1 –2 slope = –1 –3 1 2 Q0 Q+ xij xij Q– 0 1 slope = –1 slope = 0.5 (a) u ij = –1 ⇒ w ij = –1.5 – 1.5 = –3 (b) u ij = 1 ⇒ w ij = –1.5 + 1.5 = 0 Fig. 3.11. Dynamic routes of the LOGAND CNN. Fig. 3.11(a). In this case, the CNN is globally asymptotically stable, and yi j (∞) = −1 (white), regardless of the initial condition, which implies Local rule 1 and Local rule 2. Consider next the case u i j = 1 (black) so that the dynamic route is given by Fig. 3.11(b). In this case, if: (a) xi j (0) = −1 (white), then yi j (∞) = −1 (white), which is Local rule 3. (b) xi j (0) = 1 (black), then yi j (∞) = 1 (black), which is Local rule 4. Remark In our original CNN template library, and previous publications, the threshold value for the LOGAND template was assigned the value z = −1. While both computer simulations and measurements made on an early version of the CNN universal chip3 had veriﬁed the correct operation of this template, the dynamic routes shown in Fig. 3.12 corresponding to z = −1 show that this threshold value was a poor choice (see Fig. 3.12(b)), and could lead to incorrect operations in practice. In particular, if the initial state xi j (0) = −1, then the output yi j (∞) in Fig. 3.12(b) coincides with the semistable equilibrium point at Q− (xi j = −1). The following two situations in practice could occur and lead to an incorrect output yi j (∞) = 1 (black), thereby violating Local rule 3. First, any positive perturbation in the state xi j > 0 in Fig. 3.12(b) (to the right of Q− ) would cause the trajectory to move to Q+ where yi j (∞) = 1. Second, due to manufacturing tolerance in the chip fabrication technology, it is virtually impossible to guarantee for the left breakpoint to be exactly located as shown in Fig. 3.12(b). If this breakpoint is slightly displaced upward so that only one equilibrium point (Q+ ) remains, then the trajectory would converge to 68 Characteristics and analysis of simple CNN templates xij xij 1 Q– Q+ –1 –1 0 –1 1 xij Q– 0 1 xij –2 –2.5 (b) uij = 1 ⇒ w ij = –1 + 1.5 = 0.5 (a) uij = –1 ⇒ wij = –1 – 1.5 = –2.5 Fig. 3.12. Dynamic routes for the threshold value z = −1. Q+ . Since these two scenarios are quite common, it is astonishing to recall that our previous computer simulations and actual measurements on a physical chip based on this ﬂaky design did not expose this potentially disastrous problem. One explanation could be that the perturbations due to the inevitable numerical or physical noise are small enough to require a longer “observation time” than had been given. The above remark clearly points to the usefulness of our dynamic route approach for analyzing the validity and reliability of CNN templates, and for optimizing their reliability by ﬁnding more robust template coefﬁcients. 3.3.7 LOGDIF: Logic difference and relative set complement (P1 \ P2 = P1 − P2 ) template 0 0 0 A= 0 1 0 0 0 0 0 0 0 B = 0 −1 0 0 0 0 z = −1 I Global task Given: two static binary input images P1 and P2 Input: U(t) = P2 Initial state: X(0) = P1 Output: Y(t) ⇒ Y(∞) = binary image representing the settheoretic, or logic complement of P2 relative to P1 . In settheoretic or logic notation, P1 \ P2 = P1 − P2 = {x ∈ P1 : x ∈ P2 }, Y(∞) = P1 \ P2 , or Y(∞) = P1 − P2 , i.e., P1 minus P2 . 69 3.3 Some other useful templates II Local rules u i j (0) xi j (0) → yi j (∞) 1 white pixel ∈ P2 white pixel ∈ P1 → white 2 black pixel ∈ P2 white pixel ∈ P1 → white 3 black pixel ∈ P2 black pixel ∈ P1 → white 4 white pixel ∈ P2 black pixel ∈ P1 → black III Examples EXAMPLE 3.24: Image size: 15 × 15 input initial state output, t = 0.2 C B t = 0.4 t = 0.6 A t = 1.0 time (τ) Fig. 3.13. Cell state and output transients for 40 equidistant time steps (0.1) at three different locations in the image of example 1. The origin (0, 0) is the lower left corner. The pixel locations: ——: state variable xi j ; ——: output A(7, 7), B(5, 3), C(7, 8). Normalized time unit tu = tCNN . —— variable yi j ; ***: output and state are the same. 70 Characteristics and analysis of simple CNN templates Fig. 3.13. Continued. EXAMPLE 3.25: Image size: 100 × 100 input initial state t = 0.4 t = 0.6 output, t = 0.2 t = 1.0 71 3.3 Some other useful templates IV Mathematical analysis (for LOGDIF) Since s00 = a00 − 1 = 0 and wi j = −1 − u i j , u i j ∈ {−1, 1}, only the two shifted DP plots shown in Figs 3.14(a) and 3.14(b) need to be considered. xij xij Q– –1 0 1 xij –1 0 1 xij –1 –2 (a) u ij = –1 ⇒ wij = 0 (b) u ij = 1 ⇒ wij = –2 Fig. 3.14. Shifted DP plots for the LOGDIF CNN for a00 = 1 where u i j = −1 and u i j = 1, respectively. Consider ﬁrst the case when u i j = −1 (i.e., pixel in P2 is white). It follows from the dynamic route in Fig. 3.14(a) that if: (a) xi j (0) = −1 (white), then yi j (∞) = −1 (white), which is Local rule 1. (b) xi j (0) = 1 (black), then yi j (∞) = 1 (black), which is Local rule 4. Consider next the case when u i j = 1 (i.e., pixel in P2 is black). It follows from the dynamic route in Fig. 3.14(b) that if: (a) xi j (0) = −1 (white), then yi j (∞) = −1 (white), which is Local rule 2. (b) xi j (0) = 1 (black), then yi j (∞) = −1 (white), which is Local rule 3. Remarks Unlike the preceding LOGNOT CNN where both equilibrium points are locally stable (for binary inputs) in the usual sense, the left equilibrium point xi j = −1 in the LOGDIF CNN is locally stable in an “unusual” sense, even for binary inputs (in this case, for u i j = −1). Here, any perturbation of the initial condition towards the origin will cause the output to be in gray scale (i.e., −1 < yi j (∞) < 1). This is because any point xi j (0) on the unit interval [−1, 1] is an equilibrium point of this CNN when u i j = −1, and will therefore remain dormant wherever the initial state xi j (0) lies, so long as xi j (0) ∈ (−1, 1). To overcome this “sensitivitytoinitialcondition” drawback, we only need to enlarge the center feedback synaptic weight from a00 = 1 to any value satisfying 72 Characteristics and analysis of simple CNN templates 1 < a00 < 3. Observe that this CNN will not function correctly if a00 > 3 because in this case the shifted DP plots in Fig. 3.15, drawn for a00 = 4.0, would violate Local rule 3. This analysis demonstrates that the shifted DP plot can be used not only for studying the nonlinear dynamics of the CNN, but it can also be used to determine its “failure” boundary, as well as to engineer a “cure,” thereby designing a much more robust if not optimal CNN for carrying out the same task. xij xij 1 Q– slope = 3 –1 Q+ Q– –1 0 1 0 xij –2 Q 0 1 Q0 slope = –1 slope = –1 xij Q+ slope = –1 slope = –1 –5 –3 (a) u ij = –1 ⇒ w ij = 0 (b) u ij = 1 ⇒ wij = –2 Fig. 3.15. Shifted DP plot for the case a00 = 4. 3.3.8 SHIFT: Translation (by 1 pixelunit) template 0 0 0 A= 0 1 0 0 0 0 b−1,−1 B = b0,−1 b1,−1 b−1,0 b0,0 b1,0 b−1,1 b0,1 b1,1 z= 0 where the input template B is chosen from one of eight possibilities corresponding to the eight compass directions shown in Fig. 3.16. I Global task3 Given: static binary image P Input: U(t) = P Initial state: X(0) = 0 Boundary conditions: ykl = −1, u kl = −1 for all boundary “virtual” cells C(k, l). Output: Y(t) → Y(∞) = P(x − α, y − β) = translation of the input image P by one pixel unit along one of eight compass directions (α, β), where α, β ∈ {−1, 0, 1}, and (x, y) denotes the Cartesian coordinate of any pixel of P. 73 3.3 Some other useful templates 0 0 0 B(NW) = 0 0 0 0 0 1 0 0 0 B(N) = 0 0 0 0 1 0 0 0 0 B(NE) = 0 0 0 1 0 0 N NE NW 0 0 0 B(W) = 0 0 1 0 0 0 W 0 0 0 B(E) = 1 0 0 0 0 0 E SE SW S 0 0 1 B(SW) = 0 0 0 0 0 0 0 1 0 B(S) = 0 0 0 0 0 0 1 0 0 B(SE) = 0 0 0 0 0 0 Fig. 3.16. Input templates for translating an image by onepixel unit along the indicated directions. II Local rules u i j (0) → yi j (∞) 1 arbitrary (−1 or 1) → 1 (black) if u i+α, j+β = 1 2 arbitrary (−1 or 1) → −1 (white) if u i+α, j+β = −1. III Examples EXAMPLE 3.26: Image size: 15 × 15 input t = 0.4 initial state output, t = 0.1 t = 0.8 t = 1.0 74 Characteristics and analysis of simple CNN templates EXAMPLE 3.27: Input Output Input Output Input Output EXAMPLE 3.28: EXAMPLE 3.29: 75 3.3 Some other useful templates EXAMPLE 3