Case 6:21-cv-00755-ADA Document 45-8 Filed 02/28/22 Page 1 of 11
`
` Exhibit 8
`
`

`

`
`
`
`
`Downloadedfromhttps://royalsocietypublishing.org/on13February2022
`
`Case 6:21-cv-00755-ADA Document 45-8 Filed 02/28/22 Page 2 of 11
`Case 6:21-cv-00755-ADA Document 45-8 Filed 02/28/22 Page 2 of 11
`Vision for mobile robots
`
`MICHAEL BRADY ann HAN WANG
`
`Robotics Research Group, Department of Engineering Science, University of Oxford, Oxford OXI 3PJ, U.K.
`
`SUMMARY
`
`Localized feature points, particularly corners, can be computed rapidly andreliably in images, and they
`are stable over image sequences. Corner points provide more constraint than edge points, and this
`additional constraint can be propagated effectively from corners along edges. Implemented algorithms
`are described to compute optic flow and to determinescene structure for a mobile robot using stereo or
`structure from motion. It is argued that a mobile robot may not need to compute depth explicitly in
`order to navigate effectively.
`
`1. INTRODUCTION
`
`This paperis concerned with the information that can
`be computedefficiently and reliably by a mobile robot
`to support effective navigation,
`including obstacle
`avoidance. Object recognition, and the generation of
`collision avoiding trajectories are discussed elsewhere
`(Reid & Brady 1992; Hu et al. 1991). Though weare
`concerned primarily with mobile robots, the issues we
`discuss have also figured in our work on model-based
`(reduced bandwidth) image coding, medical
`image
`processing, and attentional control, for example to
`support automated surveillance systems.
`Mobile robots are used increasingly in flexible
`manufacturing systems, as a programmable alter-
`native to fixtured material transfer schemes such as
`conveyor belts. The mobile robot we work on at
`Oxford is functionally equivalent to a fielded commer-
`cial system that maintains a software model ofthe
`layout of a factory, and determines its position by
`retroreflecting infrared illumination from bar-coded
`targets placed in accurately known locations in the
`environment. Using this data, the mobile robot can
`calculate its position to better than a centimetre over
`40 m, andits orientation to a few degrees. In most
`practical applications this is more than sufficient.
`Paths are planned using the software model of the
`factory. However,
`the fielded mobile robot cannot
`detect unexpected obstacles and plan detours around
`them, nor can it recognize objects to be acquired, for
`example pallets
`from a loading bay. These two
`problems have been the foci of work at Oxford.
`Successful systems have been developed using sonar
`sensing for obstacle detection (Hu et al. 1991) and a
`laser range scanner for recognising objects such as
`palletised goods that vary parametrically (Reid &
`Brady 1992). It is far from obvious that the additional
`poweroffered by visual guidance of vehicles is neces-
`sary for many industrial purposes, particularly inside
`a factory, while the computational cost and unreliabi-
`lity of visual processing currently makes it unattrac-
`
`tive to production engineers, Outdoor applications
`are, however, a different proposition,
`and_ vision
`may well be put
`to cost-effective, practical use in
`applications such as automating work in stockyards,
`mining, agriculture, and for a number of military
`purposes.
`In the next section we argue that the information
`provided at the different locations in an image provide
`vastly different
`local
`information, hence differing
`constraint. This is most obviously the motivation for
`edge detection; but applies equally to the detection, as
`primitives, of distinctive feature points, which, rather
`loosely, we call ‘corners’. Section 3 presents a number
`of techniques
`for computing such feature points
`robustly and reliably, and shows they maybe used for
`segmenting an optic flow field. Section 4 shows two
`approaches to computing scene structure from the
`motion of such feature points. In each case, the depth
`is computed explicitly at each feature point,
`then a
`depth map for the environment is interpolated from
`the discrete set of values. To do even this in real time
`requires a powerful parallel computer architecture;
`the one that has been assembled in Oxford is sketched
`in § 5. In § 6, we discuss the problem of propagating
`constraint from ‘corner’ feature points along contours
`defined by significant
`intensity changes (‘edges’), a
`process that refines Hildreth’s influential early work
`(Hildreth, 1984) on edge-based optic flow. Finally, in
`§ 7, we ask whether depth doesafter all need to be
`made explicit, present some work that shows that
`information that is useful for navigation and collision
`avoidance can be computed without precise camera
`calibration, and say why such a scheme is
`to be
`preferred.
`
`2. THE INEQUALITY OF INFORMATION
`Notall pixels in an image carry the same amount of
`information, even as a constant signal carries no
`information. Our ability as humans to readily inter-
`pret line drawings made from images, suggest that an
`
`Phil. Trans. R. Soc. Lond. B (1992) 337, 341-350
`Printed in Great Britain
`
`341
`
`© 1992 The Royal Society and the authors
`
`
`
`

`

`Case 6:21-cv-00755-ADA Document 45-8 Filed 02/28/22 Page 3 of 11
`342 Case@.6:2 1nevt00755-ADAon Doeument45-8 Filed 02/28/22 Page 3 of 11
`
`
`
`
`
`Downloadedfromhttps://royalsocietypublishing.org/on13February2022
`
`important early processing step is to extract intensity
`changes, a suggestion reinforced by physiological
`studies of simple cells in visual cortex, Indeed, under
`certain weak conditions, an image can be recon-
`structed fromits intensity changes. A (static) image
`can be regarded as a surface,
`in which case the
`extraction of intensity changes amounts to developing
`numerical approximations to the gradient V/ and
`image (local) surface curvatures. Several approxima-
`tions tofirst and higher order derivatives of the image
`intensity function have been proposed typically pre-
`ceded by convolving with a smoothingfilter such as a
`Gaussian G,. A number of edge detection schemes
`have been proposed, extensively evaluated, and imple-
`mentedin real time, for example using recursive filters
`(Canny 1986; Deriche 1987). The Canny filter, for
`example,
`serves
`to emphasize the importance of
`nonlinear filtering. Over the past
`five years three
`novel nonlinear filters have been developed: Fleck’s
`(1988) application of finite-resolution cell complexes
`to compute high frequency texture edges; Owens &
`Venkatesh’s
`(1989)
`local energy model based on
`Hilbert quadrature pairs and local phase; and mor-
`phological filtering.
`
`3. COMPUTING ‘CORNERS’
`
`‘Corners’ carry even more information than edges,
`though they are more difficult
`to extract accurately
`and reliably. In the next section, we describe a system
`that computes structure from motion by tracking
`corners over a sequence of images, and in §6 we use
`corners as seed points in an algorithm to compute
`optic flow. We first address the question of how
`corners can be modeled and extracted. One approach
`considers a corner to be a point on anintensity change
`contour (edge) where the curvature along the edge
`attains a maximum. More formally, let 2 be the unit
`vector in the direction of the intensity gradient. The
`edge curvature K,, can be measured by the image
`surface normal curvature in the tangential direction
`orthogonal
`to n. Elementary differential geometry
`showsthat:
`
`Kyo
`
`ee + iis - SEL
`1
`;
`R+E
`"14+ h+EL
`This formula was discretized and used in an early
`corner finder by Kitchen & Rosenfeld (1982). A later
`implementation by Zuniga & Haralick (1983) worked
`out the expression analytically for the coefficients of a
`bicubic polynomial
`fit
`locally to the image surface.
`Both implementations were highly sensitive to noise.
`Recently, the authors introduced a novel algorithm of
`this sort, which we review following a discussion of an
`alternative formulation for a corner.
`The most attractive alternative model is to identify
`corners with pixels whose intensities are significantly
`different from those surrounding neighbouring pixels.
`One way to do this is
`to use the local
`image
`autocorrelation function; but
`this
`tends
`to place
`corners at some remove from the ideal location, and
`although this does not affect tracking, it does affect
`
`the estimation of three-dimensional depth. A recent
`variant
`to this theme is
`the Harris corner finder
`(Harris & Pike 1987), which has been used in the
`DROID system discussed below. The algorithm consists
`of three steps.
`1. Compute the partial derivatives of the image /,
`and /,, and compute the Gaussian smoothed products:
`<>, <>,
`and <i).
`2. Compute the eigenvalues 4),A2 of the matrix
`
`ct) a(Idy> <>
`
`3. Mark points as corners where the product Aj/2
`divided by the sum 4; + 2 is greater than a threshold.
`Noble’s
`(1989)
`thesis presents a Taylor’s series
`analysis of the grey level function /(x,y) in the vicinity
`of a Harris corner. It shows that the Harris algorithm
`combineslinearly an estimate of the intensity gradient
`and anestimate of the image curvature. Both need to
`be large for a pixel to be marked by Harris’ algorithm.
`Recently, Wang & Brady (1991) developed an
`algorithm that estimates the tangential curvature Ky)
`using the linear
`interpolation and non-maximum
`suppression techniques used originally in Canny’s
`edge finding algorithm. Refer to figure 1. Suppose
`that the image gradient |V/|
`is above a threshold at
`the point C shown, andlet the edge tangent t=n1 be
`in the direction shown. The intensity function J is
`interpolated at locations Jp, 44, Ic,
`ly, Ir, and the
`second derivative a =Kn, is estimated from thefinite
`difference approximation:
`1
`Dil =~ ( — Wp, — I, + 6le + I+ 2p),
`
`r=VJ//, when the
`spatially, e.g.
`where 7 varies
`tangential direction is less than z/4. Corner points are
`marked where(i) Dil> @|VJ\, and (ii) non-maxima
`are suppressed. Figure 2 shows one synthetic image
`and the corners found by Wang & Brady’s corner
`finder. The corner finder has been implemented on
`the parallel architecture PARADOX,describedin § 5,
`and computes corners at 14 Hz. The Wang & Brady
`algorithm exhibits interesting scale space behaviour,
`
`“:
`
`hn
`
`_ -~-------2
`-\------#
`
`2
`
`x
`
`Figure
`
`1, Linear
`
`interpolation for
`addressing.
`
`intermediate pixel
`
`Phil. Trans. R. Soc. Lond. B (1992)
`[ 90 |
`
`
`

`

`
`
`
`
`Downloadedfromhttps://royalsocietypublishing.org/on13February2022
`
`Case 6:21-cv-00755-ADA Document 45-8 Filed 02/28/22 Page 4 of 11
`
`Case 6:21-cv-00755-ADA Document4S-8orFiledO2/28i22ay Rage 4vOfid1 343
`
`Figure 2. Left, a synthetic image; right, corners located by Wang & Brady’s cornerfinder.
`
`reminiscent of the early algorithm of Asada & Brady
`for further details,
`1986); see Wang & Brady
`(1992
`The quest for feature-finding algorithms continues.
`Since Wang & Brady’s algorithm was invented, Smith
`1992
`has devised a scheme that is a hybrid of an
`autocorrelation and morphological filter. It has been
`used to generate a fast, though approximate, segmen-
`tation of the moving objects in motion sequences. ‘Torr
`et al.
`(1991
`report initial experiments with a system
`that consists of a number of such modules
`each of
`
`limited scope but which are combined in a
`motion estimation system.
`
`robust
`
`4. COMPUTING SCENE STRUCTURE USING
`CORNERS
`
`This section reports two schemes for determining scene
`structure using the feature points computed for each
`image in a sequence by the algorithms described in
`the previous section. First, we review the structure
`from motion algorithm prRotporiginally developed by
`Harris & Pike (1987), The authors have worked on an
`Esprit grant vorLA with the prop team to develop a
`revised version to run on the parallel architecture
`PARADOX. Second, wedescribe an algorithm based
`on disparity gradient to match the feature points in a
`stereo pair of images.
`DROID determines the three-dimensional structure
`of a scene bytracking imagefeatures over a sequence
`of frames.
`It works as follows.
`
`1. Thestate of the system at time¢ consists of a set of
`feature points, each of which has an associated
`vector [x,(t)y;(t)z,(t)e,(t)e, (d)e.(0)a,]". Thefirst three
`components are the estimated three-dimensional
`position of the feature. The second three compo-
`nents are the semi-axes of an ellipsoidal represen-
`tation of uncertainty. Initially,
`the uncertaintyis
`low in the image coordinates, but large in depth.
`As the vehicle circumnavigates a feature (assuming
`that it does), the uncertainty in depth reduces by
`
`Phil. Trans. R. Soc. Lond. B (1992
`
`[ 91
`
`Oo
`
`+is a
`intersecting ellipsoids. The final component
`flag that says whether the feature is
`temporarily
`invisible (e.g. because it
`is occluded).
`2. Given an estimate of the motion between the
`imaging position at
`time ¢ and time /+ 1,
`thestate
`prediction at
`time ‘+1 can be made, and, after
`perspective projection using a pinhole model,
`the
`positions of the feature points in the ¢+ Ist
`image
`can bepredicted.
`image.
`Features can be extracted from the {+ Ist
`Originally,
`features computed using the Harris
`algorithm were used. Now we use the Wang-Brady
`This is by
`far
`the
`or Smith algorithms.
`most
`the
`intensive
`step of
`compu-
`computationally
`tation.
`4. The correspondence is computed between the
`predicted locations of points in step 2 and the
`feature points found in step 3. Ambiguous matches
`are decided by matching descriptions of the pre-
`dicted and found points that
`involve the intensity
`value and gradients.
`5. Thestate estimate is updated using a Kalman filter
`algorithm, and the algorithm loops to step 2.
`6. Optionally, at each loop, the image locations of the
`feature points are triangulated, using the Delaunay
`triangulation that minimises
`long thin triangles
`Floriani 1987).
`The triangles are deprojected into
`recall
`the scene
`that
`the z component of each
`feature point has been estimated). The surface
`normal of each deprojected triangular
`facet’
`is
`computed, Driveable regions are computed as
`the transitive closure of
`the facets lying close to
`the horizontal plane, starting just
`in front of
`the
`vehicle.
`
`number of careful
`(1992
`Wang et al.
`report
`a
`experiments with the prorp algorithm using cameras
`mounted on the robot vehicle described in the first
`section and which can compute its position using the
`on-board infrared sensor. There is no integral action
`in
`the controller,
`but
`subject
`to
`this
`limitation,
`velocity and position estimates are resonably accurate
`
`GNTX0001632
`
`

`

`
`
`
`
`Downloadedfromhttps://royalsocietypublishing.org/on13February2022
`
`Case 6:21-cv-00755-ADA Document 45-8 Filed 02/28/22 Page 5 of 11
`
`
`
`Figure 3. Stereo images of the laboratory as seen from cameras mounted on the mobile robot.
`
`However, precise camera calibration is required, and,
`in view of the inevitable vibrations of the mobile
`robot, this is the most sensitive part of the system. We
`return to this point below; but note in passing that the
`system has more in common with photogrammetry
`than human vision.
`The authors have explored an alternative method
`for computing scene structure by stereo matching the
`corner feature points in a pair of images (Wang &
`Brady 1992).
`(We have also integrated the stereo
`algorithm and the structure from motion algorithm
`prop.) The stereo algorithm consists of two steps:
`correlation matching; followed by a verification step
`that enforces the disparity gradient limit
`(pGL) con-
`straint
`(Pollard et al. 1985), uncovered for human
`stereopsis (Burt & Julesz 1980).
`
`the left and right images surrounding each feature
`point. For each feature pointin the left image,a set
`of candidate matching feature points in the right
`image are determined to satisfy the epipolar con-
`straint. For each feature point in theleft image, the
`right image feature point whose surrounding region
`maximises the normalized cross correlation with
`that of the left image point (see Wanget al. (1990)
`for more details)
`is noted. This procedure is
`repeated for matches from right to left and pairs
`that maximize each other are recorded as candi-
`date matches.
`. Verification. The DGL is used to confirm matches.
`For point pairs that are in sparse regions of the
`image,
`the disparity gradient is computed as the
`difference in disparity divided by the Euclidean
`distance. The mean ofthe local disparity gradient
`provides a statistical measure of the local support
`
`1. Matching. The match operation proceeds in two
`passes. First, regions of a fixed size are identified in
`
`for a match.
`
`Figure 4. Corners detected in the left image of the stereo pair.
`
`Phil. Trans. R. Soc. Lond. B (1992)
`
`[ 92 ]
`
`GNTX0001633
`
`

`

`Case 6:21-cv-00755-ADA Document 45-8 Filed 02/28/22 Page 6 of 11
`Destdh To abbile WobtsY
`
`VE: Beedy antut. Wah 345
`
`Figure 5. Corners detected in the right image of the stereo pair.
`
`rise to image feature points using structure from
`motion or stereo. The algorithms rely on precise
`camera calibration. They more closely resemble
`photogrammetric mapping procedures than human
`stereopsis or motion parallax. It is not clear that the
`accurate depth mapsthat result from such algorithms
`are in fact required for successful navigation by a
`mobile robot (or animal).
`
`5. REAL-TIME ARCHITECTURE
`
`PARADOX is a hybrid architecture, designed and
`configured especially for vision- and image-processing
`algorithms. It consists of three major functional parts:
`a commercial (Datacube) pipelined image-processing
`system, a MIMD network of Transputers, and a
`
`
`
`Figure 3 showsa stereo imagepair of the laboratory
`as seen by a pair of ccp cameras mounted on the
`mobile robot. The cameras were carefully calibrated.
`i Figures 4 and 5 show the corner features detected in
`the left and right
`images
`(they are computed to
`subpixel accuracy).
`Figure 6 shows the corners matched in the stereo
`pair and indicates the disparities computed for each.
`Finally, figure 7 shows the three-dimensional surface
`reconstructed from the
`sparse disparity values.
`Thacker has also reported an approach of matching
`corners using correlation scheme, although thereis not
`verification stage for discarding ambiguous matches
`n noise data (Thacker 1990).
`To summarize this section: it is possible to compute
`the depths from images to the scene points that give
`
`
`
`
`
`Downloadedfromhttps:Sisagaoieon13February2022
`
`a 0
`
`Figure 6. Matched corner pairs are shown as the disparity vectors. The cameras have been calibrated so that
`epipolars align with camera scan lines, so that disparity, a vector valued quantity, can be given by a scalar value,
`
`Phil. Trans. R. Soc. Lond. B (1992)
`
`[ 93 ]
`
`GNTX0001634
`
`

`

`
`
`
`
`Downloadedfromhttps://royalsocietypublishing.org/on13February2022
`
`Case 6:21-cv-00755-ADA Document 45-8 Filed 02/28/22 Page 7 of 11
`
`346 GaseaGi2dncvi0OO7%55-ADAn /Document45-8 Filed 02/28/22 Page 7 of 11
`
`Figure 7. The three-dimensional surface reconstructed from the sparse disparity information.
`
`controlling workstation. The architecture of PARA-
`DOX, used in the current parallel implementation of
`DROID,
`is shownin figure 8.
`The commercial system contains more than 20
`types of VME-based pipelined processing and input-
`output modules which can perform a range of image
`processing operations at video rates.
`Image data is
`passed between modules via a video bus. This system
`can beusedfor the digitization, storage anddisplayof
`images, andalso for a wide range of video frame-rate
`pixel-based processing operations. For example, con-
`volution and morphological operations can be sup-
`ported directly in the hardware. System control is by
`means of the VME bus from the controlling work-
`station.
`The MIMD network consists of a board that
`contains 32 T800 Transputers, each with one Mbyte
`
`together with both hardwired and _pro-
`of RAM,
`grammable switching devices to allow the network
`topology to be altered. A wide range of network
`topologies can be implemented including parallel one-
`dimensional arrays (Wang e/ al. 1991), a two-dimen-
`sional array or a ring structure. This board delivers
`a peak performance of 320 MIPS. The connection
`between the image processing system and the Trans-
`puter network is by way of an interface board
`designed by the British Aerospace Sowerby Research
`Centre (Sheen 1988).
`In the parallel implementation of prorp (Wang &
`Bowman 1991), the Datacubeis used to digitize, store
`anddisplay the image sequence and graphics overlays;
`corner detection is carried out by the Transputer
`array; whereas the relatively undemanding structure
`from motion filtering is carried out on the workstation.
`
`
`
`Transtech MCP 1000
`31 Transputer Network
`
`Figure 8. Machine architecture PARADOX (propincarnation).
`
`Phil. Trans. R. Soc. Lond. B (1992)
`
`[ 94 ]
`
`GNTX0001635
`
`

`

`Case 6:21-cv-00755-ADA Document 45-8 Filed 02/28/22 Page 8 of 11
`Case 6:21-cv-00755-ADA Document 45-8,filled02/28/22ahags.8 of 11
`1si0n
`70
`ang 347
`
`takes O(N?)
`then it
`if the curve has N points,
`iterations to converge. Because in many practical cases
`N = 1000, this can be significant. The solution to this
`problem is somehow to reduce NV. Nagel’s early work
`suggested (Nagel 1987)
`that optic flow might be
`computed at
`image locations that he called ‘image
`corners’,
`though his mathematical definition of a
`corner location can be challenged (see Noble’s thesis).
`The second reason is that the edge points suggested
`by Hildreth are the zero-crossings of a Laplacian ofa
`Gaussian filtered version of the image: V?G,*/, which
`is often approximated by the difference of Gaussian
`(blurred) versions of the image. A feature ofthis set of
`putative edge points is that they form closed image
`contours. If image edges were always two-connected,
`this wouldin principle be satisfactory; but it simply
`cannot cope with multiway junctions typified by
`occlusion.
`If the wrong occlusion interpretation is
`made by the edgefilter (and it often is in practice),
`then inevitably the optic flow estimates of (say) a
`moving object and static background are interpreted
`as a single moving object and the results intermingle
`and degrade badly. The solution is only partly
`alleviated by moving to better edge detectors, such as
`that proposed by Deriche (Deriche 1987), since it
`requires that optic flow estimates be inhibited from
`being confused across
`two independently moving
`objects.
`Wehaveinvestigated a different approach in which
`the Taylor’s series approximation to the image func-
`tion is
`truncated to second order
`in the image
`variables and first order in time. This is not elegant
`mathematically, but reflects the massive difference in
`sampling in space and time of images. Gong & Brady
`(1990) observe that a second order expansion of the
`image function along a curve yields the constraint:
`
`(t'Hn) (t'Ha+Vi-t) =0,
`
`
`
`
`
`Downloadedfromhttps://royalsocietypublishing.org/on13February2022
`
`It is quite straightforward to do thefiltering on the
`‘Transputer network.
`
`6. PROPAGATING CONSTRAINT FOR OPTIC
`FLOW
`
`In this section we review the work of Brady, Gong,
`and Wang aimed at
`improving in certain respects
`Hildreth’s edge-based optic flow algorithm, whose
`salient points we review. In our variant, we compute
`the full optic flow at corners lying on edges,
`then
`propagate the flow along the edge between such
`locations using a mixed wave-diffusion process.
`As a viewer moves relative to the scene, the image
`brightness pattern changes. Moreprecisely, let J(x,y,/)
`denote the imageat time /. Truncatingto first order a
`Taylor’s series approximation to the expansion ofthe
`image function at
`time and position /(x+dx,y+ dy,
`1+6t), which effectively amounts
`to assuming a
`constant brightness distribution locally,
`leads to the
`motion constraint equation (Horn 1986), given by:
`
`eat
`n*4=—-,
`A~ vill
`
`where n is a unit vector in the direction of the image
`gradient n=V//\|V/\|, and ~=[x y]" is the optic flow.
`This equation showsthatso far asa first order analysis
`is concerned, only the component of optic flow in the
`direction of the image gradient can be computed, an
`observation that is known as the aperture problem.
`Hildreth (Hildreth 1984) proposed to compute
`the optic flow only at edge points of an object.
`The underlying reason is that the magnitude of the
`gradient of the image function ||/V/|| appears in the
`denominator of the motion constraint equation, hence
`the result will be poorly conditioned if this quantity is
`small. But
`large |/V/|| corresponds to edge points.
`Hildreth suggested
`a variational
`principle
`that
`attempted to estimate the optic flow s(s) along a
`(closed zero-crossing)
`image contour r(s) given the
`local
`(aperture problem) estimates of the normal
`component g*(s). More precisely, Hildreth suggested
`computing the optic flow field ¢(s) that minimizes:
`
`Ou?
`
`far(%) es ie + r(m(s) + n(s) — wr(s))?,
`
`(0m,
`
`Thefirst two of these terms enforces a smooth flow
`field,
`the latter enforces agreement with the data.
`Hildreth tested her algorithm primarily on simulated
`data, for which she demonstrated remarkable agree-
`ment with psychophysical observations. We may say
`that Hildreth’s work represents an important step in
`understanding human visual motion competence, but
`her algorithm certainly is not practical, for two major
`reasons.
`
`is that her algorithm is inevitably slow
`The first
`even if it is implemented on a parallel computer (she
`did not consider how this might be done). The reason
`is that
`the optic flow value finally computed at a
`location 5; along the curve depends both in principle
`and in practice on the values computed (including the
`initial value) at every other curve location s2. In fact,
`
`where t is the unit tangent vector to the curve, # the
`unit normal, and H/ the image Hessian matrix as used
`in Nagel’s oreinted smoothness algorithm. Gong &
`Brady (1990) developed an algorithm that improves
`upon Hildreth’s by minimizing
`
`Ou?
`
`jas(#) +(#) + A(p(s) *n(s) — a(s))?
`pee
`detH
`+ a he Ms
`
`on,\"
`
`;
`
`where ¢=det/det//~!.
`to reduce substantially the
`The effect of this is
`computation time of Hildreth’s algorithm by reducing
`the distance over which information has to be propa-
`gated. However,
`it still turns out to be too slowfor
`* real-time implementation.
`In essence, the problemis as follows. Initially, the
`full optic flow a(s1) and f(sg) is computedat succes-
`sive corners along a piecewise smooth contour, and the
`normal component f(s),91<S<S5Q is computed in
`between. Thedifficulty is to propagate efficiently the
`additional constraint provided at the end points along
`the curve. Yuille (1988) proposed a ‘motion coherence
`algorithm’, which essentially amounts to a diffusion
`
`Phil. Trans. R. Soc. Lond. B (1992)
`
`[ 95 ]
`
`
`€
`

`

`
`
`
`
`Downloadedfromhttps://royalsocietypublishing.org/on13February2022
`
`Case 6:21-cv-00755-ADA Document 45-8 Filed 02/28/22 Page 9 of 11
`
`348 «GaseG:2de¢0V-00495-ADAfoDoeument 45-8 Filed 02/28/22 Page 9 of 11
`
`Figure 9. Two images from a sequence wherethe head rotates about an axis passing through the neck and pointing
`forwards.
`
`process which propagates the end point constraints at
`a rate that is proportional to the square root of the
`numberofiterations, hence requires time proportional
`to the square of the distance separating the corners.
`An alternative scheme, introduced for shape analysis
`by Scott et al. (1988) of Oxford, combines a diffusion
`with a wave process.
`Moreprecisely, a corner constraint is propagated in
`both directions from the corner at a constant speed,
`with half the strength in each direction. The wave
`transmits the tangential component of the flow, but
`does not conserve its value. To reduce thesensitivity
`to the velocity measure, we smooth sharp changes
`using a Gaussian (diffusion). The coupled diffusion
`process reducesits value. Clearly, contour points near
`a corner are morestrongly influenced bythe value of
`the tangenial component at
`the nearby corner than
`they are by the value at
`the adjacent corner point
`further away. The algorithm runs in time propor-
`tonal
`to the arclength separating adjacent corners,
`which, given therestriction to propagation along the
`contour, is hard to improve on. Subsequent work by
`Wanget al. (1990) has described a parallel implemen-
`tation of this process on a network of Transputers.
`Figure 9 showsa pair of images from a sequence(from
`an investigation of model-based image coding)
`in
`which the head rotates in the plane of the shoulder
`
`
`
`Figure 10. Propagated flow.
`
`blades fromthe right shoulder towardsthe left. Figure
`10 shows the optic flow computed by the Gong-
`Brady—Wang algorithm,
`
`7. MUST WE COMPUTE DEPTH
`EXPLICITLY?
`
`An important step in the development of machine
`vision was the demonstration that three-dimensional
`scene layout could be computed by processes such as
`stereo, structure from motion, or shape from shading,
`contour, or
`texture. An analysis of the viewing
`geometry in a small number of images (e.g. two in the
`case ofstereo) led, via cameracalibration, to a sparse
`depth map, and then, via surface interpolation,
`to a
`dense depth map. The quality of the resulting depth
`map was evaluated in a number of ways, most
`stringently by requiring robot arms to pick and place
`objects in the field of view. Manyrecent systems have
`exploited parallel hardware simply to execute more
`quickly multistep algorithms devised originally for
`serial processors. More interestingly, parallel hard-
`ware enables more images to be processed; a system
`can always take another look, and can close the loop
`between sensing and action.
`However, closed loop control is no panacea. A key
`issue concerns the choice of control variable, and this
`straightway leads back to calibration, which we
`earlier identified as the Achilles’ heel of three-dimen-
`sional vision systems. Recall, for example,
`the error
`ellipsoids used in the pRorp system. Theerrors in the
`imageplanedirections are small, since corner feature
`points can be localised accurately; but
`the error in
`depth is
`large and circumnavigation ofthe corres-
`ponding scene point is required to give accurate depth
`values. More generally, the distance to a point in the
`scene
`is
`related nonlinearly to image quantities
`(observables) such as disparity that can be computed
`accurately. The nonlinearity corresponds to the cali-
`bration parameters, which are notoriously difficult to
`estimate accurately. From a control theoretic stand-
`point,
`filtering on depth involves a measurement
`equation that is a linear approximation to the hard-
`to-estimate nonlinear imaging geometry, a situation
`that mitigates against robustness.
`
`Phil. Trans. R, Soc. Lond. B (1992)
`
`[ 96 ]
`
`GNTX0001637
`
`

`

`Case 6:21-cv-00755-ADA Document 45-8 Filed 02/28/22 Page 10 of 11
`Case 6:21-cv-00755-ADA+Documéint458FiledO2/28/22.dPageHlO\ofd 1 349
`
`Larry Shapiro, and Steve Smith, This research was sup-
`ported by the SERC ACME Directorate and the EC under
`grants VOILA and FIRST.
`
`REFERENCES
`
`for example,
`Is there an alternative? Can we,
`compute information that is useful to a mobile robot
`directly from observables such as optic flow, disparity,
`and rate of changeofdisparity (or invariant quantities
`computed from these measures), and altogether avoid
`camera calibration. Recent work at Oxford, particu-
`larly by Cipolla (1992) and Blake & Cipolla (1990),
`suggests that we can, First, Blake & Cipolla show
`formally that if an observer makes deliberate motions
`relative to a scene containing a planar closed curve,
`then the surface normal of the plane containing the
`curve can be estimated from the symmetric compo-
`nent of the deformation of the imageof the curve, and
`the time to contact with the curve can be estimated
`from the divergence. Algorithms based on moments of
`the sequence of image curves are developed. Second,
`but again making deliberate motions, an observer can
`distinguish bounding contours of an object (where the
`surface normal turns smoothly away from the viewer)
`from edges fixed in space (for example surface creases
`or
`reflectance changes). Furthermore,
`the surface
`curvature along a bounding contour can be estima-
`ted accurately from the relative motions of surface
`features. Blake et al. (1991) discussed how this might
`be used by a moving observer to navigate among
`smooth objects, and the scheme has been refined and
`implemented by Blake et al. (1992).
`In our current work we are investigating this
`proposition further as we are developing analgorithm
`that, without knowing the motion of the observer,
`groups coplanar sets of features points,
`then deter-
`mines the orientation relative to the observer of each
`planar group, and computes the time to contact it. A
`test for coplanarity based on projective invariants has
`been developed.
`
`8. CONCLUSIONS
`
`Downloadedfromhttps://royalsocietypublishing.org/on13February2022
`
`
`
`
`
`1986 The curvature primal
`Asada, H. & Brady, J.M.
`sketch. JEEE Transactions on Pattern Analysis and Machine
`Intelligence PAMI-8 (1), 2-14.
`Blake, A. & Cipolla, R. 1990 Robust estimation of surface
`curvature from deformation of apparent contours. In Proc.
`Ist European Conf. on Computer Vi