A N O N L I N E A R S W I T C H E D - C A P A C I T O R N E T W O R K F O R E D G E D E T E C T I O N IN E A R L Y VISION Roderick A . Barman B. A . Sc. (Hons.) University of British Columbia A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF T H E REQUIREMENTS FOR T H E D E G R E E OF M A S T E R OF APPLIED SCIENCE in T H E FACULTY OF G RADUATE STUDIES DEPARTMENT OF E L E C T R I C A L ENGINEERING We accept this thesis as conforming to the required standard T H E UNIVERSITY OF BRITISH COLUMBIA Sept 1990 (c) Roderick A. Barman, 1990 In presenting this thesis in partial fulfillment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of Electrical Engineering The University of British Columbia 2356 Main Mal l Vancouver, Canada Abstract A nonlinear switched-capacitor (SC) network for solving the early vision variational prob-lem of edge detection has been designed and constructed using standard SC techniques and a novel nonlinear externally controlled SC resistive element. This new SC element al-lows, to a limited extent, the form of the variational problem to be "programmable". This allows nonconvex variational problems to be solved by the network using continuation-type methods. Appropriately designed SC networks are guaranteed to converge to a locally stable steady-state. As well, SC networks offer increased accuracy over analog networks composed of nonlinear resistances built from multiple MOSFETs . The operation of the network was analyzed and found to be equivalent to the numerical analysis minimization algorithm of gradient descent. The network's capabilities were demonstrated by "programming" the network to perform the graduated nonconvexity algorithm. A high-level functional network simulation was used to verify the correct operation of the G N C algorithm. A one-dimensional six node CMOS VLSI test chip was designed, simulated and submitted for fabrication. n Table of Contents Abstract ii List of Figures vi Acknowledgement viii 1 Introduction 1 1.1 Thesis Structure 3 2 Edge Detection 5 2.1 Introduction 5 2.2 Image Acquisition 6 2.3 Ill-Posed Problems 7 2.4 Regularization 8 2.5 Piecewise Continuous Regularization 10 2.6 Continuation Methods 11 2.7 The Graduated Nonconvexity Algorithm 13 3 Analog Resistive Networks 17 in 3.1 Introduction 17 3.2 Network Principles 18 3.3 A First-Order Regularization Network 19 3.4 VLSI Implementation Constraints 22 4 Nonlinear Switched-Capacitor Networks 24 4.1 Introduction 24 4.2 Switched-Capacitor Principles 24 4.2.1 Networks 26 4.2.2 Synthesis and Analysis 26 4.3 VLSI SC Nonideal Sources of Error 27 4.4 Nonlinear SC Networks 27 4.4.1 Nonlinear SC Principles 28 4.4.2 A Nonlinear SC Network 30 4.4.3 The G N C Algorithm 30 4.5 SC Network Operation 31 4.5.1 Effect of the Ratio r 35 4.5.2 Form of Problem Solved 35 4.5.3 Iterations to Converge 36 4.6 Network Simulation 36 iv 4.7 Summary 36 5 VLSI Design 38 5.1 Design 38 5.1.1 Comparator Cell 39 5.1.2 Switch Cell 41 5.2 Simulation 42 5.3 Fabrication and Test 42 6 Discussion 45 6.1 Shape from Shading 45 6.2 SC Constraint Boxes 46 7 Conclusions 49 7.1 Future Work 50 References 52 v List of Figures 2.1 Ideal Image Profile 6 2.2 Noisy Image Profile 7 2.3 First-Order Regularization 9 2.4 Piecewise First-Order Regularization 11 2.5 Operation of the Continuation Method 12 2.6 Functions g(t) and l(t) 1 4 2.7 Function gW(t) 15 2.8 Function g'{p)(t) 16 2.9 G N C Algorithm 16 3.1 General Resistive Network 20 3.2 Linear Resistive Network 21 4.1 SC Resistor 25 4.2 SC Resistor in a Network 26 4.3 Nonlinear SC Resistor 29 4.4 SC Nonlinear Network 31 4.5 SC Network Timing Diagram 32 vi 4.6 The function VR(VA) for G N C 33 5.1 Test Chip Layout 39 5.2 Physical Layout of One Node 40 5.3 Comparator and Switch Schematics 41 5.4 HSPICE Network Simulation 43 5.5 Simulation Control Signals 44 6.1 Shape from Shading Network 47 6.2 SC Constraint Boxes 48 vii Acknowledgement I would like to thank the following people: • Dan Camporese for running the VLSI lab and explaining to me at least 20 times how a photodiode works. • Bob Woodham for sparking my interest in vision and suggesting the topic of analog V L S I and vision. • Mike Bolotski and Dave Gagne for making sure the lab always has the latest version of every piece of public domain software. • J im Little for always having time for a discussion about Vision and VLSI. • Dominique Bajard for help, understanding, patience and persuasive finish-thesis-now techniques. • Mr . Liam and Ms. Odelia (extreme furriness: X + l ) for keeping me company while I worked and for always reminding me when it was time for a break. • My parents for putting up with a son who likes electronics and cars. And finally, thanks to Dan, Dom, Bob, Jim, Peter and Mike for reading revisions of this thesis and making many excellent comments. viii Chapter 1 Introduction Vision is a powerful means of human perception. The evidence is our ability to passively navigate and identify objects in unfamiliar environments. Despite the apparent ease with which humans utilize visual perception, the analytical study of visual processing, called computational vision, has proven to be complex and challenging. Computational vision has been decomposed roughly into a number of levels, the first called early or low-level vision. Early vision processes image intensities to obtain intermediate descriptions that are robust with respect to input noise. This thesis is concerned with the implementation of a system which performs the early vision task of edge detection. If a vision system is to operate in real-time, early vision tasks will require an enormous amount of computational resources. One approach to this computational need is the development of massively parallel computers, such as the Connection Machine [14], to exploit the parallelism, simplicity and locality of operations present in many early vision algorithms. However, such computers are expensive and physically large. As well, the general purpose flexibility of a programmable computer is unnecessary. A potentially better alternative is offered by a biologically-styled model of computation defined by Ullman[35, p. 88] and Knight[19]. A biologically-styled information processing system • is parallel, 1 Chapter 1. Introduction 2 • has local connections, • has simple individual elements, • and is robust to local failures. Many early vision algorithms map naturally onto this model of computation. There are many possible mechanisms for implementing such a network of simple processing elements: biological, electrical, chemical and mechanical. Analog electrical networks are particularly interesting because the constraints of a biologically-styled system meet the requirements for feasible VLSI implementation [19]. Image intensities may be directly input into the network by on-chip photosensors, thereby further increasing integration. These features make VLSI-based analog electrical networks an attractive mechanism for implementing early vision processes. Much work has been done in this area (see, for example Mead [24]). A n ideal electrical network cannot be practically implemented with current VLSI technol-ogy due to the limitations imposed by a standard VLSI process. One major limitation is the lack of small-scale, accurate, high-impedance resistances in standard CMOS technolo-gies. This makes it difficult to design a reasonable circuit time constant which depends on the resistance-capacitance (RC) product since capacitors of moderate size have a very small value. Appropriate resistances can be realized with active devices composed of mul-tiple MOSFETs[30] but these circuits suffer problems, such as internal-dynamics, errors from mismatched MOSFETs and increased area requirements. A n alternative approach to a VLSI implementation, pioneered in the field of telecom-munications, is based on the techniques used in switched-capacitor (SC) filters. SC techniques are suitable for a VLSI implementation because accurate capacitor ratios can be built with CMOS technologies. SC circuits are compatible with digital circuits and Chapter 1. Introduction 3 are relatively insensitive to process variations. In this thesis, the application of SC techniques to biologically-styled analog electrical networks for performing an early vision task is explored. The ultimate goal, of which this thesis represents one small step, is to produce on a single chip a biologically-styled system integrated with on-chip photosensors that performs the early vision task of edge detection. If such a goal is reached, it would be technically and economically possible to incorporate primitive vision systems into many new applications, much the way that the inexpensive microprocessor has found its way into common place items. The future availability of three-dimensional VLSI may one day allow the implementation of an integrated multi-level vision system. 1 . 1 T h e s i s S t r u c t u r e The rest of the thesis addresses the SC-based implementation of a nonlinear resistive network for edge detection. In Chapter 2 the relevant aspects of the theory of early vision and edge detection are presented. Errors associated with the image acquisition process and their effect on the edge detection problem is discussed. The formulation of the edge detection problem as the minimization of a nonconvex functional is given and a solution technique based on "continuation methods" is presented. Finally, an example, called the "Graduated Nonconvexity (GNC) algorithm[4]," is given. Chapter 3 investigates the isomorphism between the functional formulation and analog electrical networks. By way of introduction, linear networks and their parallel to standard variational problems are discussed. Nonlinear networks are then shown to map to non-convex functionals and a theorem guaranteeing nonlinear network stability is presented. Chapter 1. Introduction 4 A network for solving the G N C algorithm is discussed and the chapter ends considering the constraints imposed by VLSI implementation of a nonlinear network. Chapter 4 concentrates on SC techniques and their application to nonlinear networks. SC element and network principles are summarized and the nonlinear SC element is introduced. The non-ideal errors arising from a VLSI implementation and methods for their minimization are presented. Finally, the operation of the G N C algorithm on the SC-based network is analyzed to determine the characteristics of the network and the effects of the design parameters. A proof-of-concept VLSI chip design and simulation is presented in Chapter 5. The chip is composed of four simple cells, each of which is described in some detail. Simulation results are presented, network performance is estimated, and the proposed testing environment is discussed. Chapter 6 examines the application of nonlinear SC networks to other early vision tasks while Chapter 7 discusses the progress made in this thesis and outlines the work still to be done to complete a single-chip vision subsystem. Finally, conclusions on the viability of the SC approach are given. Chapter 2 Edge Detection 2.1 Introduction Early vision is traditionally thought of as a collection of relatively independent modules that process image properties such as intensity changes, motion, texture and shading. These modules operate directly on a two-dimensional image intensity array to extract physical properties of a three-dimensional scene. This chapter focuses on the task per-formed by the edge detection module. There are four main physical properties that affect image intensities: object geometry, object reflectance, scene illumination, and observer viewpoint[22]. Changes in intensity can be due to one of these properties or a combination of them. The goal of the edge detection module is defined to be the detection and localization of significant discon-tinuities in image intensity caused by a corresponding abrupt change in one or more physical properties. The output of the edge detection module can be used, for instance, to segment the image into separate regions. Since the one-dimensional edge detection problem is, in general, a straight forward sim-plification of the two-dimensional problem, the one-dimensional case will be studied to reduce the complexity of the analysis and examples. To demonstrate the operation of the techniques presented here, a one-dimensional ideal image profile, shown in Figure 2.1 and denoted by ti,-, will be used as an example throughout the thesis. 5 Chapter 2. Edge Detection 6 50-Figure 2.1: A one-dimensional synthetic image profile. This example was created from a number of piecewise quadratic functions. 2.2 Image Acquisition In real-time vision systems, an image is usually acquired by projecting a three-dimen-sional scene onto a plane and converted to a two-dimensional array of image intensities. A potential source of uncertainty in the image intensities is due to the statistical properties of photon measurement. For example, a semiconductor photosensor measures local image brightness by detecting the electron-hole pairs generated when photons strike the sensor's surface. Some of the generated electrons (and holes) are swept across a depletion region and separated. The number of electrons collected is a Poisson random variable whose standard deviation is the root of the mean[15]. Therefore a large number of electrons need to be collected if an accurate result is desired, necessitating a trade-off between spatial or temporal resolution and accuracy. Even if a large number of electrons is collected, it still represents only a small charge which is difficult to transfer, amplify or measure without adding noise. These difficulties are the primary reasons why image intensities are typically low-precision values and quantized to only 8-bits. Chapter 2. Edge Detection 7 The effect of these noise sources is traditionally modelled by assuming that the measure-ment was formed by addition of noise[28], i.e. 9i = di + e,-. ( 2 . 1 ) where # is the image intensity measurements, and di is the original intensity values, and ti is the error introduced by the measurement process. Figure 2.2 shows the ideal cross-section from Figure 2.1 corrupted by noise to simulate the effect of the image measurement process. 50 • Figure 2.2: A n image profile formed by the addition of Gaussian random noise with p. = 0 and cr = 2 to the data in Figure 2.1. 2.3 Dl-Posed Problems The nature of the image measurement process causes many early vision tasks, including edge detection, to be ill-posed problems. A n ill-posed problem does not satisfy one or more of the conditions in Hadamard's definition of a well-pOsed problem[9]. A problem is well-posed if its solution 1. exists, 2. is unique, Chapter 2. Edge Detection 8 3. and depends continuously on the data. Edge detection, because it examines changes in image intensities, is equivalent to numer-ical differentiation. Numerical differentiation does not depend continuously on the data and consequently is ill-posed[28]. A n intuitive example of the sensitivity of numerical differentiation to noise can be found by analyzing a function g(x) that is formed by the addition of sinusoidal noise to another function f(x). g(x) = f(x) + esin(u;a;) (2.2) The derivative of g(x) is g'(x) = f'(x) + eu cos(u>x). So for a small e, g'(x) and f'(x) can be very far apart if u> is sufficiently large. It is therefore important to process the image to produce a description of the edges which is robust with respect to added noise. 2.4 Regularization The key to making an ill-posed problem well-posed and thus solvable, is to introduce a priori knowledge about the solution. Regularization theory[34] is a rigorous method of recovering / from the given data g. If the data is formed with the operator A, 9 = Af, (2.3) the solution / can be found by minimizing the functional ||A/-0||2 + A||J7||2 (2.4) where A is the regularization parameter. Usually, A and P axe linear operators and the norms are quadratic. The parameter A controls the trade-off between the closeness of the solution to the original data and the effect of the stabilizing functional Chapter 2. Edge Detection 9 representing a priori constraints on the solution. When linear operators are used, the solution is found using variational calculus; however, the solution is restricted to that of generalized splines. The order of these splines is determined by the form of the stabilizing functional. For example, for a first-order model, the stabilizing functional is Pf = / ' . If standard quadratic norms are used Equation 2.4, becomes The discrete form is found once a choice is made for approximating f'(x). The simplest choice is /,• — /,•_! which leads to the discrete form The solution is equivalent to the physical analog of fitting a elastic string to the data. In Figure 2.3, a first-order regularization has been performed on the example data. (2.5) N N JKfi-diY + ^ i f i - f ^ ) 2 . (2.6) o 1 5 0 Figure 2.3: First order regularization of the data in Figure 2.1 obtained by minimizing the functional in Equation 2.6 with A = 9. Chapter 2. Edge Detection 10 2.5 Piecewise Continuous Regularization The application of standard regularization theory to the problem of edge detection yields physically implausible results because the stabilizing functional assumes global continu-ity. In Figure 2.3, intensity values near the original discontinuities have been pulled together and smoothed. A more realistic requirement is to assume that image intensi-ties are "continuous almost everywhere" [22] and to only apply regularization to regions between discontinuities, not to the discontinuities themselves. The approach taken here is to explicitly incorporate a binary function, indicating the presence of a discontinuity, into the first-order stabilizer[8, 2]. This adds another function to the minimization and increases the computational complexity of the problem. It does, however, lead to a more realistic solution within the simple framework of regularization although it is no longer guaranteed to be well-posed with the same rigor as the standard regularization method. The new model is called the "weak string" by Blake[4] because the physical analog of an elastic string is improved by including the possibility that the string may break at points of high tension. Equation 2.6, with the addition of a binary function /, becomes £(/,• - 9i? + A £ ( / , • - / ^ ) 2 ( 1 - /.•) + a E /,-. (2.7) 0 1 1 The stabilizer acts the same as that of Equation 2.6 except if two nodes /,• and / ,_! are further than yJct/\ apart. It then becomes less costly to set /,• = 1, thus removing the continuity constraint between / , and / ,_! and take a fixed penalty of a. The application of the model to the example data is shown in Figure 2.4. Although this model is superior, the addition of a binary function to the minimization has made the solution a difficult nonconvex problem. A nonconvex problem has more than one minimum, only one of which is the global minimum. For the variational functional of Equation 2.7, there Chapter 2. Edge Detection 11 50 fi Figure 2.4: A first-order regularization with a discontinuity binary function applied to the example noisy data from Figure 2.2. The solution is found by minimizing Equation 2.7 with A = 9 and a = 600. are 2^ local minima or one for every possible binary function value. To find this global minimum, a more sophisticated solution method than simple gradient descent is needed. 2.6 Continuation Methods There exist many stochastic and deterministic methods for solving nonconvex variational problems[8, 23, 21, 4, 7]. One deterministic method, based on continuation methods, is particularly suitable to analog network implementation. Continuation methods also require less computation and produce better results[3] than stochastic alternatives. Continuation methods[26, 37] are a means of obtaining sufficiently close starting points to a given nonconvex problem so that an iterative method, such as gradient descent, will find the global minimum. This is accomplished by reformulating the problem being minimized so that the amount of "nonconvexity" can be controlled by an extra parameter, called p. When the parameter p is one, the problem is transformed into being convex. As p is decreased towards zero, the problem is smoothly transformed, with increasing nonconvexity, into the original nonconvex problem. The global minimum is tracked throughout the transformation. Chapter 2. Edge Detection 12 In practice, the interval for p of [ 0 , 1 ] must be partitioned into a finite number of intervals 0 = p 0 <Pi <P2 < ••• <Pn = 1. (2.8) Initially, at p = 1, the iterative method is applied to the convex problem to find the global minimum. For each p,-, the iterative method is used to find the local minimum starting from the minimum of the p , + 1 solution. The global minimum will be found if at each stage the starting point is within the "domain of attraction" of the correct local minimum. A pictorial example of this process is shown in Figure 2.5 for an example minimization problem of one variable. Figure 2.5: A pictorial example of the operation of the continuation method for p = p 2 , P i , p e . The hollow ball represents the current starting point while the new mini-mum is represented by the solid ball. At each step, starting from the previous minimum, the ball "falls" into the next minimum. Chapter 2. Edge Detection 13 2.7 The Graduated Nonconvexity Algorithm The graduated nonconvexity (GNC) algorithm [4] is one specific reformulation of the variational problem of Equation 2.7 so that the continuation method can be applied. The first step in adding the dependence on the parameter p, is to note that the binary function /,• may be independently minimized from the solution /,-. To accomplish this, the minimization is rewritten as n ^ { / „ , } J B / . - 9i? + E h ((/, - / ,_!) , /,)} (2-9) where h(t, u) = Xt2(l — u) -f au. Since h(t, u) is the only function dependent on it can be independently minimized. The minimization is then ^ { / ,} JE(/,- - 9if + J£g(fi - / . - i ) } (2-io) where g(t) = min u G{ 0,i}h(t,u). The new function is Xt2 if |*| < sJcTJx a otherwise. 9(t) = (2.11) If desired, the value /, can be recovered by /,• = I ' ' V ' (2.12) 0 otherwise. v Figure 2.6 shows both g(t) and /,-. Once the binary function has been explicitly removed from the minimization, the next step is to replace g(i) with a new function g^v\i) that allows the relative amount of nonconvexity to be controlled through a parameter p as required by the continuation Chapter 2. Edge Detection 14 -1 fa fa fa fa "V A V * V A V * (a) (b) Figure 2.6: The two functions a) g^t) and b) ifi-fi-i) method. The new function g^(t) (see Blake[4] for the derivation) is Xt2 if \t\ < q a - ( l < | - r ) 7(4p) if 9 < |*| < r* a i f | i | > r where r 2 = a(4p + y ) a n d <? = T~-X Xr (2.13) The function g^p\i) replaces the first derivative discontinuity at \J~o~Jx by a quadratic whose size is controlled by the parameter p. The function g^p\t) for the sequence p = 1' 2' 4' • • • ' '7A 3 5 u s e a m ^ n e G N C algorithm is shown in Figure 2.7. The reformulation of the variational problem of Equation 2.7 is N N ^(/) = E ( / . - ^ ) 2 + E^ p ) ( / . - / . - i ) - (2.14) At each stage, an iterative method is needed to find the next minimum. Gradient descent [6] is a reasonably efficient algorithm that can be applied to problems whose first derivative is readily available. The direction of steepest descent of E(f) in Equa-tion 2.14 is —VE(f). For gradient descent, the new / is found on the line / — nWE(f) Chapter 2. Edge Detection 15 Figure 2.7: The function g^p\t). The outer most curve is for p = 1. The curve moves inwards for decreasing values of p. where (0 < rj < oo). In order to ensure convergence of the method for a simultaneous update of / , the value of rj cannot exceed (see Blake[4] for the details). For the iterative minimization of Equation 2.14, the n t h iteration is fl (n+1) = ft (") i d 2 + 4A df, ^ {I;(//B)-ft)2+I;^(p)(//")-yi(B)-l), ' l 0 1 (n) 2 ( / i n ) - gt) + g ' M ( j f > - / £ } ) + g'^Kf\n) - fll\) where g'M(t) = 2 + 4A 2Ai, if \t\ < q - £ ( l < | - r ) s i g n ( * ) , i f « < | < | < r 0, if \t\ > r. (2.15) (2.16) The function g'^p'(t) is shown in Figure 2.8. A n outline of the complete G N C algorithm is shown in Figure 2.9. This concludes the discussion of background material on early vision and edge detection relevant to this thesis. In the next chapter, the relationship between nonlinear analog networks and nonconvex variational problems will be investigated. Chapter 2. Edge Detection 16 Figure 2.8: The function g'^(t). As p is decreased towards zero, the slope of the line segment above becomes steeper. Eventually when p = 0 there is a discontinuity at GIVEN g, A and a DEFINE e: convergence criteria SET f° = g F O R p = l , i , i , . . . , ^ WHILE ||fn - f " " 1 ! ! > € FOR i = 0...N C P T _ f ( n ) 2(/(")-g,)+g-(P)(/('')-/(:>)+ 3-(P)(/,'")-/W) 3£jJ- Ji - Ji ~ 2+4A Figure 2.9: A n outline of the Graduated Nonconvexity Algorithm. The results in Fig-ure 2.4 were obtained using the G N C algorithm. Chapter 3 Analog Resistive Networks 3.1 Introduction The type of variational problems found in early vision can be solved by simple analog resistive networks. Resistive networks are inherently parallel and, depending on the dy-namics of the network, can converge quickly. This results in fast computation. Resistive networks are also robust against random errors in their elements[18]. Finally, they are compact when compared to digital implementations of such a network. The one major disadvantage of analog computation is low precision. This fact and the programmability of digital computers have contributed to the current lack of popularity of analog computation. For early vision, however, the low-precision nature of the image intensity inputs means that analog computation can be designed to not significantly degrade the already low accuracy of the result. Standard quadratic regularization can be solved by networks containing only linear, pos-sibly negative, resistances and voltage or current sources[27]. The Euler equations for this type of regularization correspond to common field problems found in applied physics and engineering. There exists a large body of work on solving field problems with re-sistive networks[18]. Nonconvex variational problems correspond to networks containing nonlinear resistive elements. 17 Chapter 3. Analog Resistive Networks 18 3.2 Ne twork Pr inciples The stationary and dynamic behavior of resistive networks is governed by a few basic principles. A l l electrical networks, whether linear or nonlinear, obey KirchhofT's laws. The lumped circuit equivalent of the physical continuity and conservation laws is "Kirch-hofT's current law" (KCL) i = 0 at a node (3.1) all branches and "KirchhofT's voltage law" (KVL) v = 0 around any mesh (3.2) each branch respectively. Both K C L and K V L are obeyed at every instant in time. The generalization of Maxwell's minimum heat theorem, applicable to both linear and nonlinear networks, is the minimization of resistor co-content[25]. The co-content of an arbitrary two-terminal voltage-controlled resistance TZ specified by / = 1(V) is J(V) = F l(V')dV. (3.3) Jo For a linear resistance with conductance G, the co-content is \GV2 or half the dissipated power. For a network composed of ./V resistors the total co-content minimized is J^ = JZMVk). (3.4) o A l l real resistive networks have parasitic capacitance and are consequently dynamic. It is possible that such networks containing nonlinear resistances may oscillate and fail to converge. Fortunately, there exists a theorem, as described below, which proves that the network co-content acts like a Lyapunov function, guaranteeing network convergence to a locally stable steady-state. Chapter 3. Analog Resistive Networks 19 Theorem 1 (Stability) Consider a network of arbitrary topology consisting of ideal nonlinear voltage-controlled resistors, ideal time-invariant voltage sources, and nonlinear but positive capacitors described by 1^ = CkiVk)^-, with Ck(Vk) > 0 everywhere. Then J n e t is strictly decreasing at each instant during any transient, % ^ < 0, (3.5) dt and the inequality is strict except at equilibrium. The proof is presented in Harris[12]. Note that implementations of nonlinear resistances from multiple MOSFETs have internal dynamics and violate the assumptions of the the-orem resulting in possible network instability. Recent work[32] has described stability criteria for nonlinear, incrementally-passive, resistances but these results are not appli-cable to the type of networks containing incrementally-active resistances of interest here. 3.3 A First-Order Regularization Network A nonlinear resistive network solves a variational problem when the network co-content is of the same form as the variational problem. A general resistive network suitable for solving a first-order regularization of the form £ ( / < - * ) 2 + £ > ( / . - / . - i ) (3-6) o 1 where <{)() is an arbitrary function, is shown in Figure 3.1. Inputs to the network are given by setting the value of the voltage sources gi. Once the network has settled to a steady state, the solution can be found by measuring the potentials /,-. To see that the network in Figure 3.1 solves the variational problem in Equation 3.6, it is necessary to compute the network co-content by finding the co-content for each resistance using Equation 3.3 Chapter 3. Analog Resistive Networks 20 9* 91 9* 9t Figure 3.1: The general first-order resistive network. and summing over all the resistances. The potential difference across each nonlinear resistance TZA is /,• — / , _ i and the co-content is denoted — / t_i) - The potential difference across each hnear resistance RB is /,• — gi and the co-content is j^(fi — gi)2-Summing over all nodes gives the network co-content of N N Jnet — J2(fi-9i)2 + EUfi-fi-i) (3.7) 2RB o ! Equating Equation 3.6 to Equation 3.7 and taking the derivative to find J ^ V ) , the I -V characteristic for TZA , gives UV) = 2 ] £ * W . (3.8) A particular variational problem can be solved by setting the correct I -V characteristic of TZA to give the appropriate function (f>(t). For example, consider the simple first-order regularization given by Equation 2.6 in which <j>(t) = Xt2. Using Equation 3.8 to find 2U(V) gives 1A(V) = j^V. (3.9) Chapter 3. Analog Resistive Networks This simple linear resistive network is shown in Figure 3.2 21 R R R Figure 3.2: The linear first-order resistive network. The G N C algorithm can be implemented using the network shown in Figure 3.1. For G N C , <j){t) = gW(t) and MV) = ^ ' ^ n (3-10) The I -V characteristic of HA is also controlled by signals representing the values of a, A and p. A G N C network computes the solution in a number of stages. At each stage, the value of p is decreased, the shape of 71A changes, and the network settles to a new state. This repeats until the final solution is reached. Chapter 3. Analog Resistive Networks 22 3.4 VLSI Implementation Constraints The implementation of ideal networks for solving early vision problems is constrained by the restrictions imposed by VLSI CMOS technology. CMOS technology provides a limited subset of circuit elements: p - and n-channel MOSFETs , capacitors and low resistive wires for interconnection. It is possible to construct other elements, such as parasitic bipolar transistors, but in general, they require larger silicon area. The limited variety of available circuit elements imposes constraints on the implementation of such networks. A wide range of circuit elements can be built from MOSFETs[24]. In fact, a nonlinear resistive network for solving early vision problems using a GNC-type algorithm has been built[12] using multiple M O S F E T elements. There are, however, a number of disadvantages to a network built from multiple M O S F E T elements. Four of these are discussed below. 1. MOSFET threshold voltage variations. Due to differences in gate doping densities, the threshold voltages of CMOS MOSFETs do not match precisely[33]. This is important since many circuits rely on matched MOSFETs . Errors are compounded in a nonlinear resistive element formed from a number of MOSFETs. 2. Internal dynamics. Nonlinear resistive elements made from MOSFETs have inter-nal dynamics. A network composed of multiple M O S F E T resistances may fail to converge to a steady-state under all conditions. 3. Increasing Implementation Size with Complexity. The complexity of an I -V charac-teristic is limited by the number of MOSFETs used to build a nonlinear resistance. A nonlinear resistance with a complex I -V characteristic requires a large number of M O S F E T s and requires considerable area to implement. Chapter 3. Analog Resistive Networks 23 4. Inflexibility of network. By designing the I -V characteristic into the nonlinear resistive element, the network is restricted to solving a single type of variational problem. Obviously, this cannot be altered once the network is fabricated. This concludes the discussion of resistive nonlinear networks and their relationship to early vision variational problems. In the next chapter, it is be shown how switched-capacitor techniques avoid the VLSI constraints discussed in the previous section. Chapter 4 Nonlinear Switched-Capacitor Networks 4.1 Introduction Switched-capacitor (SC) techniques were originally developed for use in audio telecom-munication filters. SC-based filters[31] have gained popularity because they can easily and accurately be implemented in VLSI . VLSI SC filters derive their precision from the accurate capacitor ratios of CMOS technology, not from the absolute value of circuit elements. SC techniques can also be applied to the implementation of analog networks for solving variational problems. A SC implementation avoids many of the VLSI limitations dis-cussed in the previous chapter, but is not feasible using standard SC techniques, as they are limited to linear circuits. However, a nonlinear SC resistive element can be created by the addition of a comparator to a standard SC resistor. Using such an element, a nonlinear resistive network can be created with SC techniques. 4.2 Switched-Capacitor Principles A simple linear parallel SC resistor is formed from two switches and a capacitor. The SC resistor is shown connected between a node at potential V\ and a node at potential V2 in Figure 4.1. When switch (j>\ is closed, the potential on the capacitor is V\ and the 24 Chapter 4. Nonlinear Switched-Capacitor Networks 25 (b) Figure 4.1: a) A simple linear serial SC resistor and b) the clocking signals to drive it. charge is Q = CRV\. If is opened and (f>2 is closed, the charge on the capacitor becomes Q — CRV2 and CR(VI — V2) is transferred between the two nodes. Current I is defined as the amount .of charge Q per second that is transferred. If this process is repeated at a frequency / , then the current 7, defined as the charge transferred per second, that flows between the two nodes is CR/(VI — V2) and the effective linear resistance is R = ^ j . For example, to make a large SC resistance, normally expensive in area in CMOS, a small capacitance or a slow clock is required. Small capacitances are preferable since they require less silicon area. However, there are difficulties, which are discussed later, that arise from having capacitances that are too small. The switching frequency can be slow as long as it does not interfere with the operation of the circuit, although it does have the negative effect of slowing down the computation. Since only the steady-state solution of the network is of interest here, a slow switching frequency is a viable choice. It is also clear why SC circuits depend only on capacitor ratios. If one node of the SC resistor in Figure 4.1 is connected to a capacitance of value Cc, the time constant of the circuit is T = RC = jc^- The accuracy of r is determined by an externally generated clock signal and the ratio between capacitors Cc and CR. Chapter 4. Nonlinear Switched-Capacitor Networks 26 4.2.1 Networks In any real application, SC resistors will be used in a network, not in isolation with ideal voltage sources. The above derivation assumes that the SC resistor is connected between two nodes that have zero impedance. A more realistic example is if the SC element is connected between two nodes of capacitance Cjv as in Figure 4.2. If CR <jt CN, then the 9, 9, to other elements to other elements N R N Figure 4.2: The SC resistor in a network connected to nodes with capacitance Cjv-assumption that the charge transferred is CR(V\ — V2) for every clock cycle is incorrect. The actual amount of charge transferred will be less and the effective resistance will be[5] (CN + CR)2 1 C2N Cnf 4.2.2 Synthesis and Analysis (4.1) A resistive SC network can be formed by replacing regular resistances with SC elements and assuming the behavior predicted by continuous analysis is still valid. This method is approximate but convenient. A more accurate approach is to use difference equation or Z-transform methods to analyze Chapter 4. Nonlinear Switched-Capacitor Networks 27 the clocked operation of the network. Difference equation analysis is used in Section 4.5 to prove equivalence between the operation of a nonlinear SC resistive network and the gradient descent numerical analysis method. 4.3 VLSI SC Nonideal Sources of Error There are two main sources of error that affect VLSI SC implementations[5], both ar-tifacts of the MOSFET-based implementation of ideal switches. The first, clock feed-through, is due to the capacitive coupling between the clock signal and the switched signal. The magnitude of the switch induced error depends on the size of the capaci-tances used for CR and CN, the clock signal rise and fall times, and the dimensions of the M O S F E T s used in the switch. A multitude of compensation schemes have been proposed to cancel the effects of this phenomena[13, 1, 38]. For an analysis of clock feedthrough error see Sheu[29]. The second major source of error, incomplete charge transfer, is due to the on-resistance of MOSFET-based switches. If the clock pulse width is too short, the potentials on CR and the adjacent node may not have time to equalize. This can be solved, at least for the types of networks presented here, by trivially increasing the length of the clock pulse. There are secondary sources of error, such as switch offset error, switch noise, and non-linear capacitive junction effects, that also affect the operation of SC networks. 4.4 Nonlinear SC Networks A novel modification to the standard SC element in Figure 4.1 allows for an almost arbitrary I - V characteristic. The nonlinear SC element proposed here is unique in that Chapter 4. Nonlinear Switched-Capacitor Networks 2 8 the I -V characteristic is derived from the behavior of an externally generated signal. This allows for some degree of programmability after the network has been fabricated. In addition, the accuracy of the element is improved since only a small number of matched M O S F E T s are required for implementation. There has been some previous work on nonlinear SC elements. For instance, Huertas[17] describes nonlinear SC elements that can be assembled to form any piecewise-linear I -V characteristic. This approach requires many circuit components to implement complex I -V characteristics and is therefore impractical for VLSI implementation. 4.4.1 Nonlinear SC Principles A nonlinear SC resistor can be created by adding a comparator and two externally generated analog signals to the simple SC resistor in Figure 4.1. The comparator output is connected to the input of one of the switches and the external signal V R is connected to the base of capacitor CR as shown in Figure 4.3. A n external voltage signal, V A , is applied to the base of the capacitance C J V of node 2 . The external signal, V A , ramps from the negative to the positive maximum difference between nodes. The I -V characteristic is controlled by the shape of the signal V R as V A changes. The nonlinear SC element operates in two phases. During the first phase, the signal fa is enabled and V A starts at its maximum negative value. This starting point ensures that the switch controlled by the comparator is closed. As V A rises, a point will be reached where V\ — V2 equals V A and the switch opens. At this instant, the potential across on the capacitance CR is V I — VR where V ^ is a the value of the signal VR when VA equals Vi — V2. When V A reaches the maximum potential difference, the signal fa is disabled and V R is set to zero. During the second phase, the switch fa closes and a charge of Chapter 4. Nonlinear Switched-Capacitor Networks 29 Figure 4.3: a) The nonlinear SC resistor and b) the signals required to drive it. CR {VI — V<i — VR} is transferred between the two nodes. At a cycle frequency of / , the current through the SC element is CR/ {VI — V2 — VR}. Equating this current to an arbitrary I-V characteristic, I = X(V\ — V2), and rearranging terms to find an expression for VR gives VR = J ( c ~ / 2 ) " W ~ v*)- (4-2) Since VR is the value of V R when V& equals Vi — V2, the above equation can be rewritten as VR(VA) = ^ - V A . (4.3) The sequence of signals in a cycle is shown in Figure 4.3. Because V 2 is compared to V i , the node voltage range has to be three times larger than the range of voltage values at a node. This requirement is equivalent to reducing the dynamic range of node voltages by two-thirds. Chapter 4. Nonlinear Switched-Capacitor Networks 30 4.4.2 A Nonlinear SC Network The nonlinear SC resistor can be combined with the linear SC resistor to form the network of Figure 3 . 1 by replacing the ideal components with their SC equivalents. There are two optimizations possible when incorporating the nonlinear SC resistor into a network. First, if adjacent nonlinear resistances are to be clocked simultaneously they will interfere with each other. The solution is to update the network in two cycles, one even and one odd. This requires two ramp signals, V A E and V A O ? to replace V A and two external enable signals, <J>IE and <f>\o, to replace <f>i Second, if the inputs to the comparators are moved from nodal capacitances to C'R, the inputs to the comparator will not be affected by the charge flowing on and off CV as V R changes. This is an important improvement if CR is not a lot smaller than C^. By careful selection of the switching order of the circuit, the potential on C'R will be exactly the same as that of the node potential. V&.E a n d V A O are now connected to C'R. The nonlinear SC resistive network is shown in Figure 4 . 4 and a timing diagram for one cycle of operation is shown in Figure 4 . 5 . 4.4.3 The GNC Algorithm The network in Figure 4 . 4 is suitable for implementing the G N C algorithm. To compute the required shape of V R ( V A ) , Equation 4 . 3 and Equation 3 . 1 0 are combined. If the same value for CR is assumed to be used in both the linear and nonlinear SC resistances, then VR(VA) = ±g'M(VA)- V A . ( 4 . 4 ) The function VR(V&) is shown in Figure 4 . 6 . Chapter 4. Nonlinear Switched-Capacitor Networks 31 Figure 4.4: A nonlinear SC resistive network. 4.5 SC Network Operation There are three issues related to the operation of the network that have yet to be ad-dressed. The first is the effect of the value of the ratio of CR to C/v- The second is that the variational problem solved by the SC equivalent network in Figure 4.4 is not exactly the same as that of the original network. The third is the number of iterations required Chapter 4. Nonlinear Switched-Capacitor Networks 32 Phase B Figure 4.5: One cycle of the SC network showing all the control signals. for the network to settle during each phase of the continuation method solution process. A l l of these issues are dependent on how the network is programmed with the VR(VA) function. These three issues will be examined for the case where VR(VA) is set for the G N C algorithm. Chapter 4. Nonlinear Switched-Capacitor Networks 33 VA Figure 4.6: The function VR(VA) for the G N C algorithm. To aid the analysis of the exact ideal operation of the network, one cycle of operation is divided into three phases: Phase A : (J>XE turns on and off, <f>io turns on and off Phase B: <j>2 turns on. Phase C: r/>4 turns on and off, 4>z turns on and off, 4>2 turns off The following constants are defined: r CR CN ' r , and P 1 + r' r o~ 1 + 2r For phase A: Chapter 4. Nonlinear Switched-Capacitor Networks 34 = fi ~ P(fi ~ {hi+1 + V H » = fi ~ P(fi ~ + 9 ' { f t + 1 2 - f i ) - (fi+1 - /,)} = fi + P9U+1" f i ) (4.5) For phase B: ff = f>A- p(fA - hi) = ft-p(fA-{fL-Vn)) = fA~ p(f? ~ {fti ~ [ 9 U - f l - l ] - - fi.,))}) = fA-pUA-n + fi-x-fL + ) = fi - ^^-{gU - f i - i ) - g'(fi+i - m (4.6) For phase C: f? = f?-°U?-9i) (4-7) The final update is: = //n) - P(l - " °){9'if'n) ~ ^ - g ' { t i [ - f n } + *(fW - 9l) =rtn) - ^ rrryvin) - ft\) - g'u\:\ - f\n))\+2u(n) - 9i)} (4.8) The form of the final update shows that the operation of the network corresponds to the gradient descent algorithm described in Chapter 2. For comparison, Equation 2.15 is repeated below. Note that g'^p)(t) = -g'^(-t). f(n+i) _ ,(n) _ 2(/}n) - gt) + g'M(fln) ~ / £ } ) + 9'{p)(fln) - /&}) q ) Ji -Ji 2 + 4 A V*) Chapter 4. Nonlinear Switched-Capacitor Networks 35 4.5.1 Effect of the Ratio r It is easy to see that there must be constraints on the maximum value of r. To reduce clock feedthrough errors, it is desirable to have r as large as possible. However, the SC model assumes CR is much smaller than the nodal capacitance CN- Equation 4.8 shows that the constant ^ controls the size of the gradient descent step taken for each cycle. If ^ is too large, the co-content of the network may not decrease for all steps and the network might oscillate. For the G N C algorithm, the maximum value of r for which the network will converge is found by equating | to J+AX- The result is Network oscillations have been observed during simulation when r is larger than this maximum. 4.5.2 Form of Problem Solved There is an intuitive reason to believe that the variational problem solved by the network is not exactly the same as in the continuous case. The reason is that the linear resistance and the nonlinear resistance do not operate simultaneously but instead update the state of the network independently. The result is that error terms of order r 2 are introduced. For a value of r <C 1, these terms are insignificant. But as r gets larger, the solution computed is not exactly that of Equation 2.14 because of these error terms. Since in the one-dimensional case, one of the updates is linear, it is possible to compensate for the error by scaling g'(t) by 1 + r. r < (4.10) Chapter 4. Nonlinear Switched-Capacitor Networks 36 4.5.3 Iterations to Converge It is difficult to quantitatively determine the number of iterations required for the network to find the solution since the problem is nonlinear. Blake and Zissermann[4] have found that by running a number of examples, they can estimate an upper bound on the number of iterations. This is the simplest and most practical approach. 4.6 Network Simulation Before proceeding with the VLSI design of the network in Figure 4.4, a high-level simula-tion of the network was performed. A C program was written to compute the transfer of charge as each switch opened and closed in each phase of operation. The ideal operation of the network and the theoretical effect of some system parameters were verified. The results of the simulation for a 64 node network identically match those obtained with the digital implementation of the G N C algorithm. The input data used was the standard example shown in Figure 2.2. 4.7 Summary A new nonlinear SC network for nonconvex functional minimization has been presented. The network has a number of advantages: 1. It requires a small amount of extra circuitry to implement nonlinear resistances. 2. The majority of the network accuracy is determined by externally generated signals. 3. The nonlinear resistor is externally controlled and thus the network is partially programmable. Chapter 4. Nonlinear Switched-Capacitor Networks 37 The network has a number of disadvantages: 1. The loss of dynamic range due to the comparison of adjacent nodes required by the nonlinear SC resistor. 2. The preference for small CR leads to errors from clock feedthrough. 3. Even-odd updating is required for operation of the nonlinear SC resistor. Each of these disadvantages will be addressed in turn. The loss of dynamic range, though significant for an implementation in 5V CMOS process, is not very important in an analog process, such as Northern Telecom's CM0S4 bipolar process, which has a 30V range. The requirement for a small CR is a difficult constraint to meet, not only for reasons of network operation, but also because of silicon area limitations. If the techniques above are to be successfully applied to a full scale implementation, clock feedthrough cancellation techniques must be investigated and incorporated. Fortunately, this problem is also prevalent in SC filters and many cancellation techniques have been studied. The need for even-odd updating does require extra control signals. There is, however, no additional area penalty for a two-dimensional implementation, since checkerboard type updating requires the same number of extra signals. In the next chapter, a one-dimensional proof of concept VLSI CMOS implementation will be presented. Chapter 5 VLSI Design This chapter is composed of three sections. The first section discusses the VLSI circuit design and physical layout of elements used in the network, and the assembly of these elements to form the network of Figure 4.6. In the second section, results from simulating the VLSI network using HSPICE, a commercial version of the Berkeley SPICE program, are presented. Finally, the third section describes the proposed testing environment. Two simplifications were made to reduce the complexity of the VLSI network and to enhance its testability. First, the integration of on-chip photosensors was left for future work. Data inputs to the network are instead supplied by externally applied voltages. Network testing is simplified since inputs can be directly controlled and network error can be determined precisely. Second, the nodal capacitances CN were not integrated in the design. The effect of r on network convergence can be studied during testing by externally altering the value of CN-5.1 Design A six-node nonlinear SC network was designed, simulated, and submitted for fabrication in CMOS V L S I technology. Unfortunately, due to delays in fabrication, the chip was not returned with sufficient time for testing. The physical layout of the chip is shown in Figure 5.1. The network is composed of three distinct elements or cells: comparators, 38 39 f1 f2 f3 f4 f5 f6 phi2 philO philE phi3 Figure 5.1: The physical layout of the test chip. The chip was implemented in Northern Telecom's CMOS3 technology. CMOS3 is a double-level metal single-poly 3-micron process. The chip is approximately 3800 by 1200 microns. switches, and capacitors. While the design of the capacitor cell is relatively straightfor-ward, there are many possible circuits that could be used to implement the comparator and switch cells. Different cell implementations optimize different combinations of the de-sign goals of simplicity, size, speed and accuracy. For this preliminary design, the primary goal was correct operation and therefore simplicity and ease of design were emphasized. The layout of one node is shown in Figure 5.2. 5.1.1 Comparator Cell The comparator design is based on a transconductance amplifier[36]. A transconductance amplifier produces as its output a current that is proportional to the voltage difference between its two inputs. It can be modified to act as a comparator with the addition of a N A N D gate connected to its output. The N A N D gate serves the dual function of adding output hysteresis and allowing the comparator output to be turned off. The accuracy Chapter 5. VLSI Design 40 Figure 5.2: Physical layout of node three of Figure 5.1. The two cells at the bottom are 2 pf capacitors. The five cells along the middle are a comparator cell surrounded by two switch cells on either side. of the comparator is determined by the matching of the symmetrical MOSFETs used in the differential pair and the current mirror. The matching of these MOSFETs was improved by making them larger than minimum size. The amount of current passing through the differential pair and current mirror is controlled by the external signal H i a s -The schematic diagram of the comparator is shown in Figure 5.3A. There are many different ways to implement a comparator in VLSI (for a SC like method see Knight[19]). The transconductance amplifier based comparator was chosen primarily Chapter 5. VLSI Design 41 because it has been previously designed and tested in work preliminary to this thesis. 5.1.2 Switch Cell A common implementation in VLSI SC designs is to use a single N - M O S F E T as a switch. Due the requirements of nonlinear SC resistors, switches must be able to conduct well across the entire middle third of the voltage range. For digital C M O S , this is from 1.67V to 3.33V. A single N-MOSFETs on-resistance significantly increases for a switched voltage of greater than 3V. For this reason, a complementary switch composed of a P - M O S F E T and a N - M O S F E T is used. A n inverter is incorporated into the switch to eliminate the need to propagate both the clock and the inverted clock signals. The schematic diagram of the switch is shown in Figure 5.3B. m (A) (B) Figure 5.3: Schematics of the a) comparator and b) switch. While an inverter is a simple method of generating clock signals, clock feedthrough errors Chapter 5. VLSI Design 42 can be reduced in a complementary switch if there is minimal clock skew. This could be accomplished by using a CMOS set-reset logic shift register to generate the clock and inverted clock signals [30]. 5.2 Simulation The HSPICE simulator was used to simulate the circuit extracted from the physical layout of the network. It was found that the network functioned well with a conservative cycle time of 2.2/zs. In Figure 5.4, the simulation of the network for few iterations of the initial stage of the G N C algorithm is shown. The single cycle in Figure 5.5 shows all of the control signals used to drive the network. The sequence of these signals is identical to that of the high-level simulation discussed in Chapter 4. 5.3 Fabrication and Test The design, called IC3BCHIC, was submitted for fabrication in Northern Telecom's CMOS3 process in Apri l 1990 to the Canadian Microelectronics Corporation. Fabricated chips were scheduled to be returned at the beginning of August 1990. Due to fabrication difficulties, the designs were not returned until the middle of September 1990. In the interim, work was begun on a suitable testing environment. Due to the special nature of this design, it was decided that a Motorola 68HC11 single-board computer would be the best choice for a testing host. Two 10-bit signed D / A converters were added to drive the signals that control the nonlinear SC resistances on the chip. Input data will be set using variable precision resistors. The results will be measured using the 68HCl l ' s integrated 8-Bit A / D converter. Using this test configuration, it will be Chapter 5. VLSI Design 43 hspice template control file [x in seconds) 3.6! 3.58J 3.56J 3.54t V V \t „ ^ ^ r 7f5 in volts 3.7£ " * 3.65 3.6 3.55 3.5 3.45 3.4 j aoi V O l t ' 9 3.5 3.45 3.4 3.35 3.3 3.25 A3 i mm 35u ' 4&u ' ' 45u Figure 5.4: A n HSPICE simulation of the network. The input data to the network are the voltages 2.5,2.3,2.3,3.5,3.7,3.6. The G N C parameters were A = 4 and a = 0.75. The nodal capacitances were set to the theoretical minimum value of 7 times the resistor capacitors. possible to obtain plots of the operation of the network similar to those produced by the HSPICE simulation. Chapterd. VLSI Design 44 Figure 5.5: The control signals used in the network simulation. A conservative cycle time of 2.2/is was used. Chapter 6 Discussion In this chapter, the application of SC techniques to more advanced early vision problems is investigated. The edge detection network outputs processed image intensities and a binary function indicating the presence of an intensity discontinuity. The binary function can be recovered by a latch whose clock input is connected to the comparator output of the nonlinear SC resistor and whose input is fed by an externally generated control signal. These outputs can be used as inputs into a second network. Possible candidate early vision tasks for implementation as a second network are optical flow and shape from shading. Both of these tasks can be formulated as variational problems and can be solved with a combination of resistive networks and constraint boxes[ll]. Like resistive networks, constraint boxes can also be implemented with SC techniques. To illustrate, a one-dimensional SC-based shape from shading network is proposed. 6.1 Shape from Shading A one-dimensional discrete version of the variational shape from shading problem[16] based on the coupled depth/slope model[10] is 0 1 1 45 Chapter 6. Discussion 46 Here R(p) is the one-dimensional reflectance function, p; is the surface gradient, and Z{ is the surface height. The reflectance function R(p) is arbitrary function of p but can locally be approximated by its linearized form found through Taylor series expansion and ignoring higher-order terms R(p) = Rfa) + (P - Po)-^(Po) + .-.. (6-2) The reflectance function can now be rewritten as R(p) « A + Bp where A — R(po) — PojfciPo) a n < ^ & = dRdp°^'• The value po is the best approximation for p available at each node. For example, in an SC implementation p0 could be the value of p from the previous cycle. The network in Figure 6.1 minimizes Equation 6.1 for this approximate reflectance function. The values of the factors A and B are dependent on the value of p. 6.2 SC Constraint Boxes There are three constraint boxes in Figure 6.1: addition, subtraction and multiplication. Voltage-based constraint boxes can be implemented with SC techniques. A design for a SC subtraction constraint box due to Knight[20] is shown in Figure 6.2a. A proposed SC addition constraint box is shown in Figure 6.2b. There is some indication that the multiplication constraint box can be implemented with the SC techniques used to create nonlinear resistances. Chapter 6. Discussion 47 Figure 6.1: A network composed of constraint boxes and resistive grids for solving shape from shading. ^ Chapter 6. Discussion 48 V. 9 1 <P2 V - . W—• v. 1 9. 9- 9. 9, V (a) (b) Figure 6.2: The a) subtraction and b) addition SC constraint boxes. Chapter 7 Conclusions In conclusion, this thesis has demonstrated that switched-capacitor (SC) techniques can be applied to the implementation of nonlinear networks for solving early vision nonconvex variational problems. SC networks are easily implemented in CMOS VLSI . In comparison to continuous networks composed of multiple M O S F E T elements, such networks are stable under a wider variety of conditions, are more accurate due to a minimal dependence on matching MOSFETs , and are more flexible in their operation. SC networks designed with an appropriate ^ ratio are guaranteed to converge to a steady-state. The operation of a nonlinear SC network is shown to be equivalent to the numerical gradient descent minimization technique and therefore provably convergent. Multiple MOSFET-based networks, since the nonlinear resistive elements have dynamics and are incrementally active, have no similar guarantee of convergence. The SC nonlinear resistive element contains only one comparator with two matching pairs of MOSFETs . A multiple M O S F E T nonlinear resistance contains approximately ten matching pairs[12]. As well, there exists the possibility of implementing this com-parator using SC techniques[19] thereby eliminating all dependence of the network on matched MOSFETs . The external signal that controls the I-V characteristic contributes to the accuracy of the nonlinear SC resistance and is the reason that the network is programmable. 49 Chapter 7. Conclusions 50 Potentially, different early vision variational problems could be solved using the same network by reprogramming the nonlinear resistance. The design simplicity of the CMOS VLSI test network shows the suitability of bio-logically-styled systems to VLSI implementation. Although SC techniques look promis-ing, their superiority over standard analog VLSI is an open question until a complete edge detection module is implemented. 7.1 Future Work This thesis is one step towards the goal of a single-chip edge detection module. The following still remains to be accomplished: • Clock feedthrough analysis and cancellation. Many potential techniques exist for clock feedthrough cancellation. Successful reduction in this error source will result in smaller resistor and nodal capacitances. This, in turn, will increase the viability of an SC-based design. • Two-dimensional analysis. Although the extension of SC techniques to two-dimen-sions is straightforward, the analysis of the error terms from multiple updates and the minimization of those errors remains to be done. • Conversion of photosensor output. A circuit design is needed which converts the output of a photosensor into the correct voltage range. One possibility is a pho-todiode connected to a capacitive integrator. Elements already present in the SC network could be used for the majority of these functions. The ideas presented here can also be applied to networks for solving other early vision tasks expressed as variational problems such as optical flow and surface reconstruction. Chapter 7. Conclusions 51 And finally, the variety of proposed nonconvex variational functionals increases for the two-dimensional edge detection task. These functionals can also be solved with the nonlinear SC networks described in this thesis. References [1] L . A . Bienstman and H . De Man. An 8-channel 8b /xp compatible NMOS converter with programmable ranges. In International Solid State Circuits Conference. IEEE, 1980. [2] A . Blake. The least-disturbance principle and weak constraints. Pattei^n Rec. Lett., 1:393-399, 1983. [3] A . Blake. Comparison of the efficiency of deterministic and stochastic algorithms in visual reconstruction. IEEE Trans. Pattern Anal. Machine Intell, 11:2-12, 1989. [4] A . Blake and A . Zisserman. Visual Reconstruction. MIT Press, Cambridge, M A , 1987. [5] J . T. Caves et al. Sampled analog filtering using switched-capacitors as resistor equivalents. IEEE J. Solid-State Circuits, 12:592-599, 1977. [6] G. Forsythe, M . Malcom, and C. Moler. Computer Methods for Mathematical Com-putations. Prentice-Hall, Englewood Cliffs, N J , 1977. [7] D. Geiger and F. Girosi. Parallel and deterministic algorithms for MRFs: Surface reconstruction and integration. AI Lab Memo 1114, MIT, 1989. [8] S. Geman and D. Geman. Stochastic relaxation, Gibbs distribution, and the Bayesian restoration of images. IEEE Trans. Pattern Anal. Machine Intell., 6:721-741, 1985. [9] J . Hadamard. Lectures on the Cauchy Problem in Linear Partial Differential Equa-tions. Yale University Press, New Haven, C T , 1923. 52 References 53 [10] J . Harris. The coupled depth/slope approach to surface reconstruction. A l Lab Memo 908, MIT, 1986. [11] J . Harris. Solving early vision problems with VLSI constraint networks. In Neural Architectures for Computer Vision Workshop, Minneapolis, M N , 1988. A A A I . [12] J . Harris, C. Koch, J . Luo, and J . Wyatt. Resistive fuses: Analog hardware for detecting discontinuities in early vision. In C. Mead and M . Ismail, editors, Analog VLSI Implementations of Neural Systems, pages 27-56. Kluwer Academic, Norwell, M A , 1989. [13] K . Haug, G . C. Temes, and K . Martin. Improved offset-compensation schemes for switched-capacitors. In International Circuits and Systems Conference. IEEE, 1984. [14] W. D. Hillis. The Connection Machine. MIT Press, Cambridge, M A , 1985. [15] B . K . P. Horn. Robot Vision. MIT Press, Cambridge, M A , 1986. [16] B . K . P. Horn. Height and gradient from shading. A l Lab Memo 1105, MIT, 1989. [17] J .L. Huertas et al. Nonlinear switched-capacitor networks: Basic principles and piecewise—linear design. IEEE Trans. Circuits Syst., 32:305-319, 1985. [18] W. J . Karplus. Analog Simulation: Solution of Field Problems. McGraw-Hil l , New York, 1958. [19] T. F. Knight. Design of an Integrated Optical Sensor with On-Chip Preprocessing. PhD thesis, MIT, 1983. [20] T. F. Knight, personal communication, September 1990. [21] C. Koch, J . Marroquin, and A. Yuille. Analog "neuronal" networks in early vision. Proc. Natl. Acad. Sci., 83:4263-4267, 1986. [22] D. Marr. Vision. W. H. Freeman, New York, 1982. References 5 4 [23] J . Marroquin, S. Mitter, and T. Poggio. Probabilistic solution of ill-posed problems in computational vision. J. Amer. Statistical Assoc., 82(397):76-89, 1987. [24] C. A . Mead. Analog VLSI and Neural Systems. Addison-Wesley, New York, 1 9 8 9 . [25] W. Millar. Some general theorems for nonlinear systems possessing resistance. Phil. Mag., 42:1150-1160, 1951. [26] J . M . Ortega and W.C . Rheinboldt. Iterative Solution of Nonlinear Equations with Several Variables. Academic, New York, 1970. [27] T. Poggio and C. Koch. Ill-posed problems in early vision: From computational theory to analogue networks. Proc. R. Soc. Lond. B, 226:303-323, 1 9 8 5 . [28] T. Poggio and V . Torre. Ill-posed problems and regularization analysis in early vision. A l Lab Memo 773, MIT, 1984. [29] B. J . Sheu and C. Hu. Switch-induced error voltage on a switched-capacitor. IEEE J. Solid-State Circuits, 19:519-525, 1984. [30] M . A . Sivilotti, M . A . Mahowald, and C. A . Mead. Real-time visual computa-tion using analog CMOS processing arrays. In 1987 Stanford Conference on VLSI, Cambridge, M A , 1987. MIT Press. [31] C. Solomon. Switched-capacitor filters: Precise, compact and inexpensive. IEEE Spectrum, 25(6):28-32, 1988. [32] D. L . Standley and J . L . Wyatt. Stability criterion for lateral inhibition and related networks that is robust in the presence of integrated circuit parasitics. IEEE Trans. Circuits Syst., 36:675-681, 1989. [33] J . E . Tanner. Integrated Optical Motion Detection. PhD thesis, California Institute of Technology, 1986. [34] A . N . Tikhonov and V . Y . Arsenin. Solutions of Ill-Posed Problems. Winston, Washington, D C , 1977. References 55 [35] S. Ullman. Interpretation of Visual Motion. MIT Press, Cambridge, M A , 1979. [36] E . A . Vittoz. Micropower techniques. In Design of MOS VLSI Circuits for Telecom-munications, Englewood Cliffs, N J , 1985. Prentice-Hall. [37] E. Wasserstrom. Numerical solutions by the continuation method. SIAM Rev., 15:89-119, 1973. [38] R. C. Yen and P. R. Gray. A MOS switched-capacitor instrumentation amplifier. IEEE J. Solid-State Circuits, 17:1008-1013, 1982.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- A nonlinear switched-capacitor network for edge detection...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
A nonlinear switched-capacitor network for edge detection in early vision Barman, Roderick A. 1990
pdf
Page Metadata
Item Metadata
Title | A nonlinear switched-capacitor network for edge detection in early vision |
Creator |
Barman, Roderick A. |
Publisher | University of British Columbia |
Date Issued | 1990 |
Description | A nonlinear switched-capacitor (SC) network for solving the early vision variational problem of edge detection has been designed and constructed using standard SC techniques and a novel nonlinear externally controlled SC resistive element. This new SC element allows, to a limited extent, the form of the variational problem to be "programmable". This allows nonconvex variational problems to be solved by the network using continuation-type methods. Appropriately designed SC networks are guaranteed to converge to a locally stable steady-state. As well, SC networks offer increased accuracy over analog networks composed of nonlinear resistances built from multiple MOSFETs. The operation of the network was analyzed and found to be equivalent to the numerical analysis minimization algorithm of gradient descent. The network's capabilities were demonstrated by "programming" the network to perform the graduated nonconvexity algorithm. A high-level functional network simulation was used to verify the correct operation of the GNC algorithm. A one-dimensional six node CMOS VLSI test chip was designed, simulated and submitted for fabrication. |
Subject |
Computer vision Image processing |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-10-22 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0098203 |
URI | http://hdl.handle.net/2429/29460 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1990_A7 B37.pdf [ 3.02MB ]
- Metadata
- JSON: 831-1.0098203.json
- JSON-LD: 831-1.0098203-ld.json
- RDF/XML (Pretty): 831-1.0098203-rdf.xml
- RDF/JSON: 831-1.0098203-rdf.json
- Turtle: 831-1.0098203-turtle.txt
- N-Triples: 831-1.0098203-rdf-ntriples.txt
- Original Record: 831-1.0098203-source.json
- Full Text
- 831-1.0098203-fulltext.txt
- Citation
- 831-1.0098203.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0098203/manifest