{"title": "An Integrated Vision Sensor for the Computation of Optical Flow Singular Points", "book": "Advances in Neural Information Processing Systems", "page_first": 699, "page_last": 705, "abstract": null, "full_text": "An Integrated Vision Sensor for the \n\nComputation of Optical Flow Singular Points \n\nCharles M. Higgins and Christof Koch \n\nDivision of Biology, 139-74 \n\nCalifornia Institute of Technology \n\nPasadena, CA 91125 \n\n[chuck,koch]@klab.caltech.edu \n\nAbstract \n\nA robust, integrative algorithm is presented for computing the position of \nthe focus of expansion or axis of rotation (the singular point) in optical \nflow fields such as those generated by self-motion. Measurements are \nshown of a fully parallel CMOS analog VLSI motion sensor array which \ncomputes the direction of local motion (sign of optical flow) at each pixel \nand can directly implement this algorithm. The flow field singular point \nis computed in real time with a power consumption of less than 2 m W. \nComputation of the singular point for more general flow fields requires \nmeasures of field expansion and rotation, which it is shown can also be \ncomputed in real-time hardware, again using only the sign of the optical \nflow field. These measures, along with the location of the singular point, \nprovide robust real-time self-motion information for the visual guidance \nof a moving platform such as a robot. \n\n1 \n\nINTRODUCTION \n\nVisually guided navigation of autonomous vehicles requires robust measures of self-motion \nin the environment. The heading direction, which corresponds to the focus of expansion \nin the visual scene for a fixed viewing angle, is one of the primary sources of guidance \ninformation. Psychophysical experiments [WH88] show that humans can determine their \nheading direction very precisely. In general, the location of the singular point in the visual \nfield provides important self-motion information. \n\nOptical flow, representing the motion seen in each local area of the visual field, is partic-\n\n\f700 \n\nC. M. Higgins and C. Koch \n\nularly compute-intensive to process in real time. We have previously shown [DHK97] a \nfully parallel, low power, CMOS analog VLSI vision processor for computing the local \ndirection of motion. With onboard photoreceptors, each pixel computes in continuous time \na vector corresponding to the sign of the local normal flow. In this article, we show how \nthese motion vectors can be integrated in hardware to compute the singular point of the \noptical flow field. While each individual pixel suffers from transistor mismatch and spatial \nvariability with respect to its neighbors, the integration of many pixels serves to average out \nthese irregularities and results in a highly robust computation. This compact, low power \nself-motion processor is well suited for autonomous vehicle applications. \n\nExtraction of self-motion information has been a topic of research in the machine vision \ncommunity for decades, and has generated volumes of research; see [FA97] for a good \nreview. While many algorithms exist for determining flow field singular points in complex \nself-motion situations, few are suitable for real-time implementation. Integrated hardware \nattempts at self-motion processing have only begun recently, with the work of Indiveri et \nal [IKK96]. The zero crossing in a ID array of CMOS velocity sensors was used to detect \none component of the focus of expansion. In a separate chip, the sum of a radial array \nof velocity sensors was used to compute the rate of flow field expansion, from which the \ntime-to-contact can be calculated. McQuirk [McQ96] built a CCD-based image processor \nwhich used an iterative algorithm to locate consistent stable points in the image, and thus \nthe focus of expansion. More recently, Deutschmann et al. [DW98] have extended Indiveri \net al.'s work to 2D by summing rows and columns in a 2D CMOS motion sensor array and \nusing software to detect zero crossings and find the flow field singular point. \n\n2 SINGULAR POINT ALGORITHM \n\nIn order to compute the flow field singular point, we compute the sum of the sign of optical \nflow over the entire field of view. Let the field of view be centered at (0,0) and bounded \nby \u00b1L in both spatial dimensions; then (vector quantities are indicated in boldface) \n\ns = [:[: U(x , y)dxdy \n\n(1) \n\nwhere U(x,y) = (Ux(x,y),Uy(x,y)) = sgn(V(x,y)) and V(x,y) is the optical flow \nfield. Consider a purely expanding flow field with the focus of expansion (FOE) at the \ncenter of the visual field. Intuitively, the vector sum of the sign of optical flow will be zero, \nbecause each component is balanced by a spatially symmetric component with opposite \nsign. As the FOE moves away from the center of the visual field, the sum will increase or \ndecrease depending on the FOE position. \n\nAn expanding flow field may be expressed as \n\nVe(x, y) = A(x, y) . ((x - Xe), (y - Ye)) \n\n(2) \n\nwhere A(x, y) denotes the local rate of expansion and (Xe, Ye ) is the focus of expansion. \nThe integral (1) applied to this flow field yields \n\nas long as A is positive. Note that, due to the use of optical flow sign only, this quantity is \nindependent of the speed of the flow field components. We will discuss in Section 5 how \nthe positivity requirement of A can be relaxed somewhat. \n\n\fIntegrated Computation of Optical Flow Singular Points \n\nSimilarly, a clockwise rotating flow field may be expressed as \n\nV r (x, y) = B (x, y) . ((y - Yr), - (x - X r)) \n\n701 \n\n(3) \n\nwhere B(x, y) denotes the local rate of rotation and (Xr, Yr) is the axis of rotation (AOR). \nThe integral (1) applied to this flow field yields \n\nas long as B is positive. \n\nS = -4L\u00b7 (Yr , -Xr ) \n\nLet us now consider the case of a combination of these expanding and rotating fields (2) \nand (3): \n\n(4) \nThis flow field is spiral in shape; the parameter a defines the mix of the two field types. The \nsum in this case is more complex to evaluate, but for a small (rotation dominating), \n\nV(x,y) = aVe + (1- a)Vr \n\nand for a large (expansion dominating), \n\nS = -4L\u00b7 (CXe + Yr, CYe - X r) \n\n(5) \n\nS = -4L\u00b7 (Xe + (l/C)Yr, Ye -\n\n(6) \nwhere C = l~:B' Since it is mathematically impossible to recover both the FOE and AOR \nwith only two equations, l let us equate the FOE and AOR and concentrate on recovering the \nunique singular point of this spiral flow field. In order to do this, we need a measurement \nof the quantity C, which reflects the relative mix and strength of the expanding and rotating \nflow fields. \n\n(l/G)Xr) \n\n2.1 COEFFICIENTS OF EXPANSION AND ROTATION \n\nConsider a contour integral around the periphery of the visual field of the sign of optical \nflow components normal to the contour of integration. If we let this contour be a square of \nsize 2L centered at (0,0), we can express this integral as \n\n8LCexp = i: (Uy(x,L) - Uy(x, -L))dx + i: (Ux(L,y) - Ux(-L,y)) dy \n8LCrot = i: (Ux(x, L) - Ux(x, -L)) dx + i: (Uy( -L, y) - Uy(L, y)) dy \n\nThis integral can be considered as a 'template' for expanding flow fields. The quantity \nCexp reaches unity for a purely expanding flow field with FOE within the visual field, and \nreaches zero for a purely rotating flow field. A similar quantity for rotation may be defined \nby an integral of the sign of optical flow components parallel to the contour of integration: \n\n(8) \nIt can be shown that for a small (rotation dominating), Gexp ~ C. As a increases, Cexp \nsaturates at unity. Similarly, for () large (expansion dominating), Crot ~ (l/C). As a \ndecreases, Grot saturates at unity. This suggests the following approximation to equations \n(5) and (6), letting Xs = Xe = Xr and Ys = Ye = Yr \n\n(7) \n\nS = -4L . (CexpXs + CrotYs, GexpYs - CrotXs) \n\n(9) \n\nfrom which equation the singular point (Xs , Ys ) may be uniquely calculated. Note that this \ngeneralized expression also covers contracting and counterclockwise rotating fields (for \nwhich the quantities Cexp and Crot would be negative). \n\n1 In fact, if A and B are constant, there exists no unique solution for the FOE and AOR. \n\n\f702 \n\nC. M. Higgins and C. Koch \n\n3 HARDWARE IMPLEMENTATION \n\nThe real-time hardware implementation of the above algorithm utilizes a fully parallel \n14x 13 CMOS analog VLSI motion sensor array. The elementary motion detectors are \nbriefly described below. Each pixel in the array creates a local motion vector when crossed \nby a spatial edge; this vector is represented by two currents encoding the x and y compo(cid:173)\nnents. These currents persist for an adjustable period of time after stimulation. By using \nthe serial pixel scanners at the periphery of the chip (normally used to address each pixel \nindividually), it is possible to connect all of these currents to the same output wire, thus im(cid:173)\nplementing the sum required by the algorithm. In this mode, the current outputs of the chip \ndirectly represent the sum S in equation (1), and power consumption is less than 2 mW. \n\nA similar sum combining sensor row and column outputs around the periphery of the chip \ncould be used to implement the quantities Gexp and Grot in equations (7) and (8). Due \nto the sign changes necessary, this sum cannot be directly implemented with the present \nimplementation. However, it is possible to emulate this sum by scanning off the vector \nfield and performing the sum in real-time software. \n\n3.1 ELEMENTARY MOTION DETECTOR \n\nThe ID elementary motion detector used in this processor is the IT! (Inhibit, Trigger, and \nInhibit) sensor. Its basic operation is described in Figure 1; see [DHK97] for details. The \nsensor is edge sensitive, approximately invariant to stimulus contrast above 20% and func(cid:173)\ntions over a stimulus velocity range from 10-800 pixels/sec. \n\n~--l \n\n~ PIXEL B \n,-- -~ l \n;TEDj \n\n~ PIXEL A \n~E~j \n~~-- JJ}TJ[ __ ~ \n\n~ \n\n~ PIXEL C \nITED: \n\nMOTION \n\nMOTION \n\nA Intensity \n\nBlntensity \n\nCintensity \n\nDirection voltage \n\n-\n\nVnght \n\n-\n\nVleft \n\nVrlghl \n\nDirection voltage \n\nVlelt \n\nOutput current \n\nlout \n\n__ ~Il~ __________ __ \nL \n\ntime \n\nFigure 1: IT! sensor: a spatial edge crossing the sensor from left to right triggers direc(cid:173)\ntion voltages for both directions Vright and Viejt in pixel B. The same edge subsequently \ncrossing pixel G inhibits the null direction voltage Viejt. The output current is continu(cid:173)\nously computed as the difference between Vright and Viejt; the resulting positive output \ncurrent lout indicates rightward motion. Pixels B and A interact similarly to detect left(cid:173)\nward motion, resulting in a negative output current. \n\nThe output of each ID IT! sensor represents the order in which the three involved photore(cid:173)\nceptors were crossed by a spatial edge. Like all local motion sensors, it suffers from the \naperture problem, and thus can only respond to the optical flow normal to the local gra(cid:173)\ndients of intensity. The final result of this computation is the sign of the projection of the \nnormal flow onto the sensor orientation. Two such sensors placed orthogonally effectively \ncompute the sign of the normal flow vector. \n\n\fIntegrated Computation of Optical Flow Singular Points \n\n703 \n\n15 \n\n05 \no \n\n-05 \n\n-1 \n\n-1 5 \n\nFOE Y coordinate \n\nFOE X coordinate \n\nFOE Y coordinate \n\nFOE X coordinate \n\n(a) X output \n\n(b) Youtput \n\nFigure 2: Hardware FOE computation: the chip was presented with a computer-generated \nimage of high-contrast expanding circles; the FOE location was varied under computer \ncontrol on a 2D grid. The measured chip current output has been scaled by a factor of \n6 x 105 chip radii per Ampere. All FOE locations are shown in chip radii, where a radius \nof 1.0 corresponds to the periphery of the sensor array. Data shown is the mean output over \none stimulus period; RMS variation is 0.27 chip radii. \n\n4 SENSOR MEASUREMENTS \n\nIn Figure 2, we demonstrate the hardware computation of the FOE. To generate this data, \nthe chip was presented with a computer-generated image of high-contrast expanding cir(cid:173)\ncles. The focus of expansion was varied on a 2D grid under computer control, and the \nmean of the chip's output current over one period of the stimulus was calculated for each \nFOE position. This output varies periodically with the stimulus because each motion sen(cid:173)\nsor stops generating output while being crossed by a stimulus edge. The RMS value of \nthis variation for the expanding circles stimulus is 0.27 chip radii; this variation can be \ndecreased by increasing the resolution of the sensor array. The data shows that the FOE \nis precisely located when it is within the chip's visual field. Each component of the chip \noutput is virtually independent of the other. When the FOE is outside the chip's visual field, \nthe chip output saturates, but continues to indicate the correct direction towards the FOE. \n\nThe chip's AOR response to a rotating 'wagon wheel' stimulus is qualitatively and quanti(cid:173)\ntatively very similar, and is not shown for lack of space. \n\nIn Figure 3, the coefficients of expansion and rotation are shown for the same expanding \ncircles stimulus used in Figure 2. Since these coefficients cannot be calculated directly by \nthe present hardware, the flow field was scanned out of the chip and these quantities were \ncalculated in real-time software. While the FOE is on the chip, Gexp remains near unity, \ndropping off as the FOE leaves the chip. As expected, Grot remains near zero regardless \nof the FOE position. Note that, because these coefficients are calculated by integrating a \nring of only 48 sensors near the chip periphery, they have more spatial noise than the FOE \ncalculation which integrates all 182 motion sensors. \n\nIn Figure 4, a spiral stimulus is presented, creating an equal combination of expansion and \nrotation \u00ab() = 0.5 in equation (4)). The singular point is calculated from equation (9) using \nthe optical flow field scanned from the chip. Due to the combination of the coefficients with \nthe sum computation, more spatial noise has been introduced than was seen in the FOE \ncase. However, the singular point is still clearly located when within the chip. When the \n\n\f704 \n\nC. M. Higgins and C. Koch \n\n0 .5 \n\no \n\n- 05 \n\n- 1 \n\no \n\nFOE X coordinate \n\nFOE Y coordinate \n\nFOE X coordinate \n\n(a) Cexp \n\n(b) Grot \n\n- 1 \n\no \n\n- 1 \n\nFOE Y coordinate \n\nFigure 3: Coefficients of expansion and rotation: again using the computer-generated ex(cid:173)\npanding circles stimulus, the FOE was varied on a 2D grid. All FOE locations are shown \nin chip radii, where a radius of 1.0 corresponds to the periphery of the sensor array. Data \nshown is the mean output over one stimulus period. \n\n1.5 \n\n0 .5 \no \n\n-0.5 \n\n-1 \n\n- 15 \n\no \n\n15 \n\n0.5 \no \n\n-0.5 \n\n-1 \n\n-15 \n\nSingular pt. Y coord. \n\nSingular pt. X COOrd. \n\nSingular pt Y coord. \n\nSIngular pt. X coord. \n\n(a) X output \n\n(b) Y output \n\nFigure 4: Singular point calculation: the chip was shown a computer-generated image of a \nrotating spiral; the singular point location was varied under computer control on a 2D grid. \nAll singular point locations are shown in chip radii, where a radius of 1.0 corresponds to \nthe periphery of the sensor array. Data shown is the mean output over one stimulus period. \n\nsingular point leaves the chip, the calculated position drops towards zero as the algorithm \ncan no longer compute the mix of expansion and rotation. \n\n5 DISCUSSION \n\nWe have presented a simple, robust algorithm for computing the singular point of an optical \nflow field and demonstrated a real-time hardware implementation. Due to the use of the \nsign of optical flow only, the solution is independent of the relative velocities of components \nof the flow field. Because a large number of individual sensors are integrated to produce \nthis output, it is quite robust to the spatial variability of the individual motion sensors. We \nhave also shown how coefficients indicating the mix of expansion and rotation may be \ncomputed in hardware. A motion sensor array which directly computes these coefficients, \nas well as the flow field singular point, is currently in fabrication. \n\n\fIntegrated Computation of Optical Flow Singular Points \n\n705 \n\nIn order to derive the equations relating the flow field sums to the FOE, it was necessary \nin Section 2 to make the unrealistic assumption that the optical flow field contains no areas \nof zero optical flow. Due to the persistence time of the motion sensor used, it is possible to \nrelax this assumption significantly. As long as all parts of the visual field receive stimulation \nwithin the persistence time of the motion output, the optical flow field seen by the motion \nsensor array will contain no zeros and the singular point output will remain correct. This \nis a simple example of temporal motion integration. In fact, it is possible in practice to \nrelax this assumption even further: as long as the location of zeros in the optical flow field \nis spatially random, the magnitude of the output will be reduced hut it will continue to \nprovide a clear error signal pointing towards the flow field singular point. \n\nBecause of the fully parallel design of the motion sensor array, larger arrays may be ob(cid:173)\ntained by simply replicating pixels. The FOE summing algorithm is not affected by this \nincrease in the number of pixels. As the number of pixels is increased, the average power \nconsumption will increase sublinearly, because the sum output current (the dominant source \nof prolonged power consumption) can be maintained at approximately the same absolute \nvalue regardless of the number of pixels integrated. However, the periodic variation of \nthe output with the stimulus will be decreased, the precision of the FOE output will be \nimproved, and the need for temporal averaging will be reduced. \n\nAcknowledgments \n\nThis research was supported by the Caltech Center for Neuromorphic Systems Engineering \nas a part of the National Science Foundation's Engineering Research Center program, as \nwell as by the Office of Naval Research. The authors wish to thank Rainer Deutschmann \nfor stimulating discussions. \n\nReferences \n\n[DHK97] R. Deutschmann, e. Higgins, and e. Koch. Real-time analog VLSI sensors for \n2-D direction of motion. In Proceedings of the Int. Con! on Artificial Neural \nNetworks, pages 1163-1168. Springer Verlag, 1997. \n\n[DW98] R. A. Deutschmann and O. G. Wenisch. Compressive computation in analog \n\nVLSI motion sensors. In Proceedings of Deutsche Arbeitsgemeinschaftfiir Mus(cid:173)\ntererkennung, 1998. \n\n[FA97] \n\ne. Fermtiller and Y. Aloimonos. On the geometry of visual correspondence. \nInternational Journal of Computer Vision, 21(3):233-247,1997. \n\n[IKK96] G. Indiveri, 1. Kramer, and e. Koch. Parallel analog VLSI architectures for \ncomputation of heading direction and time-to-contact. In D.S. Touretzky, M.e. \nMozer, and M.E. Hasselmo, editors, Advances in Neural Information Processing \nSystems, volume 8, pages 720-726, Cambridge, MA, 1996. MIT. \n\n[McQ96] I. McQuirk. An analog VLSI chip for estimating the focus of expansion. Tech(cid:173)\n\nnical Report 1577, Massachusetts Institute of Technology, Artificial Intelligence \nLaboratory, 1996. \n\n[WH88] W. Warren and D. Hannon. Direction of self-motion is perceived from optical(cid:173)\n\nflow. Nature, 336(6195):162-163,1988. \n\n\f", "award": [], "sourceid": 1613, "authors": [{"given_name": "Charles", "family_name": "Higgins", "institution": null}, {"given_name": "Christof", "family_name": "Koch", "institution": null}]}