{"title": "Segmentation Circuits Using Constrained Optimization", "book": "Advances in Neural Information Processing Systems", "page_first": 797, "page_last": 804, "abstract": null, "full_text": "Segmentation Circuits Using Constrained \n\nOptimization \n\nJohn G. Harris'\" \n\nMIT AI Lab \n\n545 Technology Sq., Rm 767 \n\nCambridge, MA 02139 \n\nAbstract \n\nA novel segmentation algorithm has been developed utilizing an absolute(cid:173)\nvalue smoothness penalty instead of the more common quadratic regu(cid:173)\nlarizer. This functional imposes a piece-wise constant constraint on the \nsegmented data. Since the minimized energy is guaranteed to be convex, \nthere are no problems with local minima and no complex continuation \nmethods are necessary to find the unique global minimum. By interpret(cid:173)\ning the minimized energy as the generalized power of a nonlinear resistive \nnetwork, a continuous-time analog segmentation circuit was constructed. \n\n1 \n\nINTRODUCTION \n\nAnalog hardware has obvious advantages in terms of its size, speed, cost, and power \nconsumption. Analog chip designers, however, should not feel constrained to map(cid:173)\nping existing digital algorithms to silicon. Many times, new algorithms must be \nadapted or invented to ensure efficient implementation in analog hardware. Novel \nanalog algorithms embedded in the hardware must be simple and obey the natural \nconstraints of physics. Much algorithm intuition can be gained from experimenting \nwith these continuous-time nonlinear systems. For example, the algorithm described \nin this paper arose from experimentation with existing analog segmentation hard(cid:173)\nware. Surprisingly, many of these \"analog\" algorithms may prove useful even if a \ncomputer vision researcher is limited to simulating the analog hardware on a digital \ncomputer [7] . \n\n... A portion of this work is part. of a Ph.D dissertation at Caltech [7]. \n\n797 \n\n\f798 \n\nHarris \n\n2 ABSOLUTE-VALUE SMOOTHNESS TERM \n\nRather than deal with systems that. have many possible stable states , a network \nt.hat has a unique stable stat.e will be studied . Consider a net.work that minimizes: \n\nE(u) = ~ I:(d i -\n\n2 \n\n. \n\n1 \n\nlid:? +,\\ I: 11I i+1 -\n\n. \n\nI \n\nlIi l \n\n(2) \n\nThf' absolute-vahIf.' function is used for the smoothness penalty instead of the more \nfamiliar quadratic term. There are two intuitive reasons why the absolut.e-value \npena1t.y is an improvement over the quadratic penalty for piece-wise const.ant. seg(cid:173)\nnwntation. First, for large values of Illi - 1Ii+11, the penalty is not. as severE\" which \nmeans that edges will be smoothed less. Second, small values of Illi -\nlIi+11 are \npenalized more than they are in t.he quadratic case, resulting in a flat.ter surface \nbet.ween edges. Since no complex continuation or annealing methods are necessary \nt.o avoid local minima. this computat.ional model is of interest to vision researchers \nindependent of any hardware implicat.ions. \n\nThis method is very similar to constrained optimization methods uisclIssed by Platt \n[14] and Gill [4]. Uncler this interpretation, the problem is to minimize L(di - Ui f \nwith t.he constraint. that lIj = lIi+l for all i. Equation 1 is an inst.ance of the penalty \nmet.hod, as ,\\ ~ (Xl, the const.raint lIi = lIi+l is fulfilled exactly. The absolute-value \nvalue penalt.y function given in Equat.ion 2 is an example of a nondifferent.ial pena.lty. \nThe const.raint. lli = Ui+1 is fulfilled exactly for a finit.e value of ,\\. Howewr, unlike \ntypical constrained optimization methous, this application requires some of these \n\"exact ,. constraints to fail (at discontinuities) and others to be fulfilled . \n\nThis algorithm also resembles techniques in robust st.at.istics, a field pioneered and \nformalized by Huber [9]. The need for robust estimation techniques in visual pro(cid:173)\ncessing is clear since, a single out.lier may cause wild variations in standard regular(cid:173)\nization networks which rely on quadrat.ic data constraint.s [171. Rather than use the \nquadratic data constraints, robust. regression techniques tend to limit the infl uence \nof outlier dat.a points. 2 The absolut.e-value function is one method commonly used \nto reduce outlier succeptability. In fact, the absolute-value network developed in \nthis paper is a robust method if discontinuities in the data are interpret.ed as out(cid:173)\nliers. The line process or resistive fuse networks can also be interpreted as robust \nmethods using a more complex influence functions. \n\n3 ANALOG MODELS \n\nAs pointed out by Poggio and Koch [15], the notion of minimizing power in linear \nnetworks implementing quadrat.ic \"regularized\" a.lgorithms must be replaced by t.he \nmore general notion of minimizing the total resistor co-content [1:31 for nonlinear \nnetworks. For a voltage-controlled resistor characterized by I = f(V), the co(cid:173)\ncontent is defined as \n\nJ(V) = i f(V')dV' \n\nv \n\n(3) \n\n20utlier detect.ion techniques have been mapped to analog hardware [8). \n\n\fSegmentation Circuits Using Constrained Optimization \n\n799 \n\n\u2022 \u2022 \u2022 \n\n\u2022\u2022\u2022 \n\nFigure 1: Nonlinear resist.ive network for piece-wise const.ant segmentation. \n\nOne-dimensional surface int.erpolation from dense dat.a will be used as the model \nproblem in t.his paper, but these techniques generalize to sparse data in multiple \ndimensions. A standarJ technique for smoothing or int.erpolating noisy input.s di is \nto minimize an energy! of the form: \n\n(1) \n\nThe first. term ensures t.hat the solution Ui will be close to the data while the second \nterm implements a smoothness constraint. The parameter A controls the tradeoff \nbetween the degree of smoothness and the fidelity to the data. Equation 1 can \nbe interpreted as a regularization method [1] or as the power dissipa.ted the linear \nversion of the resistive network shown in Figure 1 [16]. \n\nSince the energy given by Equation 1 oversmoothes discontinuities, numerous re(cid:173)\nsearchers (starting with Geman and Geman [3]) have modified Equa.tion 1 with \nline processes and successfully demonstrated piece-wise smooth segmentation. In \nthese methods, the resultant energy is nonconvex and complex annealing or con(cid:173)\ntinuation methods are required to converge to a good local minima of the energy \nspace. This problem is solved using probabilistic [11] or deterministic annealing \ntechniques [2, 10]. Line-process discontinuities have been successfully demonstrated \nin analog hardware using resistive fuse networks [5], but continuation methods are \nstill required to find a good solution [6]. \n\nlThe term ene'yy is used throughout this paper as a cost functional to be minimized. \n\nIt does not necessarily relate t.o any true energy dissipated in the real world. \n\n\f800 \n\nHarris \n\n(b) 6 = lOOmV \n\n(c) S = lOmV \n\n(d)S=lmV \n\nFigure 2: Various examples of tiny-tanh network simulation for varying 6. The I-V \ncharacteristic of the saturating resistors is I = ,\\ tanh(V /6). (a) shows a synthetic \n1.0V tower image with additive Gaussian noise of q = O.3V which is input to the \nnetwork. The network outputs are shown in Figures (b) 6 = 100mV, (c) 6 = 10mV \nand (d) 6 = 1m V. For all simulations ,\\ = 1. \n\n\fSegmentation Circuits Using Constrained Optimization \n\n801 \n\n\\'i \n\n~'R .....-ji-t-------------t \n\nFigure 3: Tiny tanh circuit. The saturating tanh characteristic is measured between \nnodes VI and \\/2, Controls FR and VG set the conductance and saturation voltage \nfor the device. \n\nFor a linear resistor, I = ev, the co-cont.ent. is given by ~ev2, which is half the \ndissipa.ted power P = eV~. \n\nThe absolute-value functional in Equat.ion 2 is not strictly convex. Also, since the \nabsolut.e-value function is nondifferentiable at the origin, hardware and software \nmethods of solution will be plagued with instabilities and oscillations. We approx(cid:173)\nimate Equation 2 with the following well-behaved convex co-content: \n\n(4) \n\nThe co-content becomes the absolute-va.lue cost function in Equation 2 in the lim(cid:173)\niting case as 8 -----t O. The derivative of Equation 2 yields Kirchoff's current equation \nat each node of the resistive network in Figure 1: \n\n(Uj-dj)+Atanh( \n\n8 \n\nUj - Ui+l \n\n)+Atanh( \n\n8 \n\n)=0 \n\nUi - Uj-l \n\n(5) \n\nTherefore, construction of this network requires a nonlinear resistor with a hyper(cid:173)\nbolic tangent I-V characteristic with an extremely narrow linear region. For this \n\n\f802 \n\nHarris \n\nreason, t.his element. is called t.he tiTly-tanh resist.or. This saturating resistor is used \nas the nonlinear element. in the resistive network shown in Figure 1. Its I-V charac(cid:173)\nt.eristic is I = -\\ tanh(l' / b). It is well-known that any circuit made of inuependent. \nvoltage sources and two-terminal resistors \\'\\lit.h strictly increasing 1-V characterist.ics \nhas a unique st.able st.ate. \n\n4 COMPUTER SIMULATIONS \n\nFigure 2a shows a synthetic 1.0V tower image with additive Gaussian noise of \n(J = 0.3V. Figure 2b shows the simulated result for b = 100m V and -\\ = 1. As \nMead has observed, a network of saturating resistors has a limited segmentation \neffect. [12]. Unfortunately, as seen in the figure, noise is still evident in the output, \nand the curves on either side of the step have started t.o slope toward one anot.her. \nAs -\\ is increased to further smooth the noise, the t.wo sides of the st.ep will blend \ntogether into one homogeneous region. However, a'3 the width of the linear region \nof t.he sat.urating resist.or is reduced, network segmentation propert.ies are greatly \nenhanced. Segmentation performance improves for b = 10m V shown in Figure LC \nand further improves for f, = 1mF in Figure 2d. The best. segment.ation occurs when \nthe I-V curve resembles a step function, and co-content., therefore, approximates an \nabsolute-value. Decreasing b less than 1m V shows no discernible change in the \noutput.. 3 \n\nOne drawback of this net.work is t.hat it does not. recover the exact heights of input \nsteps. Rather it. subtracts a const.ant from the height of each input. It is st.raight.for(cid:173)\nward to show that the amount each uniform region is pulled towards the background \nis given by -\\(perimeter/area) [7]. Significant features with large area/perimeter ra(cid:173)\ntios will retain their original height. Noise point.s have small area/perimeter ratios \nand therefore will be pulled towards the background. Typically, the exact values of \nthe height.s are less important than the location of the discontinuities. Furthermore, \nit. would not be uifficult to construct a t.wo-stage network t.o recover the exact values \nof the step height.s if desired. In this scheme a tiny-tanh network would control the \nswitches on a second fuse network. \n\n5 ANALOG IMPLEMENTATION \n\nMead has constructed a CMOS saturating resistor with an I-V characteristic of the \nform I = -\\ tanh(ll/b), where delta must be larger than 50mV because of funda(cid:173)\nmental physical limitations [12]. Simulation results from section 4 suggest that for \na tower of height h to be segmented, h/8 must be at least on the order of 1000. \nTherefore a network using Mead's saturating resistor (8 = 50m V) could segment a \ntower on the order of 50V, which is much too large a voltage to input to these chips. \nFurt.hermore, since we are typically interested in segmenting images into more than \ntwo levels even higher voltages would be required. The tiny-tanh circuit (shown in \nFigure 3) builds upon an older version of Mead's saturating resistor [18] using a \ngain stage t.o decrease the linear region of the device. This device can be made to \nsaturate at voltages as low as 5m V. \n\n3These simulations were also used to smooth and segment noisy depth da.ta from a \n\ncorrelation-based stereo algorithm run on real images [7). \n\n\f(V) \n\n3.2 \n\n2.8 \n\n2.4 \n\n2.0 \n\nSegmentation Circuits Using Constrained Optimization \n\n803 \n\n:3.6 \n\n(V) \n\n:3.2 \n\n2.8 \n\n2.4~'''''''''' ... Jt.j'\"\"'''''''''''.11.''''\"\",,,,,,\u00b7,,,~,,~,,,,,,,,, \n\n2.0 \n\nChip Input \n\nSegment.ed Step \n\nFigure 4: Measured segmentat.ion performance of the tiny-tanh network for a step. \nThe input shown 011 the left. is about. a IV step. The out.put shown on the right. is \na sf'gment.ed step about 0.5V in height. \n\nBy implementing the nonlinear resistors in Figure 1 with the tiny-t.anh circuit. a \nID segmentation network was successfully fabricated and t.ested. Figure 4 shows \nt.he segmentation which resulted when a st.ep (about 1 V) ,vas scanned into the chip. \nThe segment.ed step has been reduced to about 0.5V. No special annealing met.hods \n,,,ere necessary because a convex energy is being minimized. \n\n6 CONCLUSION \n\nA novel energy functional was developed for piece-wise constant segmentatioll. 4 \nThis computational model is of interest to vision researchers independent of any \nhardware implications, because a convex energy is minimized. In sharp contrast to \nprevious solutions of t.his problem, no complex continuation or annealing methods \nare necessary to avoid local minima. By interpreting this Lyapunov energy as the \nco-content of a nonlinear circuit, we have built and demonstrated the tiny-tanh \nnetwork, a cont.inuous-time segmentation network in analog VLSI. \n\nAcknowledgements \n\nMuch of this work was perform at Calt.ech with the support of Christof Koch and \nCarver Mead. A Hughes Aircraft graduate student fellowship and an NSF postdoc(cid:173)\ntoral fellowship are gratefully acknowledged. \n\n4This work has also been extended to segment piece-wise lillea.r regions, instead of the \n\npurely piece-wise constant processing discussed in this paper [7]. \n\n\f804 \n\nHarris \n\nReferences \n\n[1] M. Bert.ero, T. Poggio, and V. Torre. Ill-posed problems in early vision . Proc. \n\nIEEE, 76:869-889, 1988. \n\n[2] A. Blake and A. Zisserman. Visual Reconstruction. MIT Press. Cambridge, \n\nMA. 1987. \n\n[3] S. Geman and D. Geman. Stochast.ic relaxation. gibbs distribut.ion and the \nIEEE Trans. Pafifrll Anal. Mach. Intdl., \n\nbayesian rest.oration of images. \n6:721-741, 1984. \n\n[4] P. E. Gill, \"V. Murray, and M. H. 'Vright. Practical Optimization. Academic \n\nPress, 1981. \n\n[5] .J. G. Harris, C. Koch, and .J. Luo. A two-dimensional analog VLSI circuit for \n\ndetecting discontinuities in early vision. Science, 248:1209-1211,1990. \n\n[6] .J. G. Harris, C. Koch, .J. Luo, and .J . 'Wyat.t.. Resist.ive fuses: analog hardware \nfor det.ecting discontinuities in early vision. In Ivl. Mead, C.and Ismail, editor, \nAnalog VLSI Implementations of Neural Systems. Kluwer, Norwell. MA, 1989. \n[7] .J .G. Harris. Analog models for early vision. PhD thesis, California Inst.itut.e of \nTechnology, Pasadena, CA, 1991. Dept. of Computat.ion and Neural Syst.ems. \n[8] .J .G. Harris, S.C. Liu, and B. Mathur. Discarding out.liers in a nonlinear re(cid:173)\n\nsistive network. In blter1lational Joint Conference 011 NEural .Networks, pages \n501-506, Seattie, 'VA., July 1991. \n\n[9] P .. l. Huber. Robust Statistics . . J. 'Viley & Sons, 1981. \n[10] C. Koch, .J. Marroquin, and A. Yuille. Analog \"neuronal\" networks in early \n\nvision. Proc Nail. Acad. Sci. B. USA, 83:4263-4267, 1987. \n\n[11] J. Marroquin, S. Mitter, and T. Poggio. Probabilistic solut.ion of ill-posed \n\nproblems in computational vision. J. Am. Statistic Assoc. 82:76-89, 1987. \n\n[12] C. Mead. Analog VLSI and Neural Systems. Addison-\\Vesley, 1989. \n[13] w. Millar. Some general theorems for non-linear systems possessing resistance. \n\nPhil. Mag., 42:1150-1160, 1951. \n\n[14] .J. Platt. Constraint methods for neural networks and computer graphics. Dept. \nof Comput.er Science Technical Report Caltech-CS-TR-89-07, California Insti(cid:173)\ntute of Technology, Pasadena, CA, 1990. \n\n[15] T. Poggio and C. Koch. An analog model of computation for the ill-posed prob(cid:173)\n\nlems of early vision. Technical report, MIT Artificial Intelligence Laboratory, \nCambridge, MA, 1984. AI Memo No. 783. \n\n[16] T. Poggio and C. Koch. Ill-posed problems in early vision: from computational \n\ntheory to analogue networks. Proc. R. Soc. Lond. B, 226:303-323, 1985. \n\n[17] B.G. Schunck. Robust computational vision. In Robust methods in computer \n\ntJision workshop., 1989. \n\n[18] M. A. Sivilotti, M. A. Mahowald, and C. A. Mead. Real-time visual compu(cid:173)\n\ntation using analog CMOS processing arrays. In 1987 Stanford Conference on \nVery Large Scale Integration, Cambridge, MA, 1987. MIT Press. \n\n\f", "award": [], "sourceid": 500, "authors": [{"given_name": "John", "family_name": "Harris", "institution": null}]}