Determining optical flow
`Determining optical flow
`
`Berthold K. P. Horn, Brian G. Schunck
`Berthold K. P. Horn, Brian G. Schunck
`Artificial Intelligence Laboratory, Massachusetts Institute of Technology
`Artificial Intelligence Laboratory, Massachusetts Institute of Technology
`545 Technology Square, NE43-811, Cambridge, Massachusetts 02139
`545 Technology Square, NE43 -811, Cambridge, Massachusetts 02139
`
`Abstract
`Abstract
`
`Optical flow cannot be computed locally, since only one independent
`Optical flow cannot be computed locally, since only one independent
`measurement is available from the image sequence at a point, while the
`measurement is available from the image sequence at a point, while the
`flow velocity has two components. A second constraint is needed. A
`now velocity has two components. A second constraint is needed. A
`method for finding the optical flow pattern is presented which assumes
`method for finding the optical flow pattern is presented which assumes
`that the apparent velocity of the brightness pattern varies smoothly al(cid:173)
`that the apparent velocity of the brightness pattern varies smoothly al-
`most everywhere in the image. An iterative implementation is shown
`most C\ er where in the image. An iterative implementation is shown
`which successfully computes the optical flow for a number of synthetic
`which successfully computes the optical flow for a number of synthetic
`image sequences. The algorithm is robust in that it can handle image
`image sequences. The algorithm is robust in that it can handle image
`sequences that are quantized rather coarsely in space and time.
`It is
`sequences that are quantized rather coarsely in space and time.
`It is
`also insensitive to quantization of brightness levels and additive noise.
`also ii sensitive to quantization of brightness levels and additive noise.
`Hxaniples are included where the assumption of smoothness is violated
`1..xamples are included where the assumption of smoothness is violated
`at singular points or along lines in the image.
`at singular points or along lines in the image.
`
`A recent review [28] of computational techniques for the analysis of
`A recent review [28] of computational techniques for the analysis of
`image sequences contains over 150 references.
`image sequences contains over 150 references.
`The optical flow cannot be computed at a point in the image in(cid:173)
`The optical flow cannot be computed at a point in the image in-
`dependently of neighboring points without introducing additional con(cid:173)
`dependently of neighboring points without introducing additional con-
`straints, because the velocity field at each image point has two com(cid:173)
`straints, because the velocity field at each image point has two com-
`ponents while the change in image brightness at a point in the image
`ponents while the change in image brightness at a point in the image
`plane due to motion yields only one constraint. Consider, for example,
`plane due to motion yields only one constraint. Consider, for example,
`a patch of a pattern where brightness 1 varies as a function of one image
`a patch of a pattern where brightness' varies as a function of one image
`coordinate but not the other. Movement of the pattern in one direc(cid:173)
`coordinate but not the other. Movement of the pattern in one direc-
`tion alters the brightness at a particular point, but motion in the other
`tion alters the brightness at a particular point, but motion in the other
`direction yields tio change. Thus components of movement in the latter
`direction yields no change. Thus components of movement in the latter
`direction cannot be determined locally.
`direction cannot be determined locally.
`
`1.
`I.
`
`Introduction
`Introduction
`
`Optical flow is the distribution of apparent velocities of movement
`Optical flow is the distribution of apparent velocities of movement
`of brightness patterns in an image. Optical flow can arise from
`of brightness patterns in an image. Optical flow can arise from
`relative motion of objects and the viewer [8, 9]. Consequently, optical
`relative motion of objects and the viewer [8, 9]. Consequently, optical
`flow can give important information about the spatial arrangement of
`flow' can give important information about the spatial arrangement of
`the objects viewed and the rate of change of this arrangement [10].
`the objects viewed and the rate of change of this arrangement [10].
`Discontinuities in the optical flow can help in segmenting images into
`Discontinuities in the optical flow can help in segmenting images into
`regions that correspond to different objects [29]. Attempts have been
`regions that correspond to different objects 1291. Attempts have been
`made to perform such segmentation using differences between succes(cid:173)
`inade to perform such segmentation using differences between succes-
`sive image frames [17, 18, 19, 22, 3, 27]. Several papers address the
`sive image francs 117. 18, 19, 22, 3, 27]. Several papers address the
`problem of recovering the motions of objects relative to the viewer
`problem of recovering the motions of objects relative to the viewer
`fiom the optical flow [12, 20, 21, 23, 31]. Some recent papers provide
`(ion) the optical flow- [12, 20, 21, 23, 31]. Sonic recent papers provide
`a clear exposition of this enterprise [32, 33]. The mathematics can
`a clear exposition of this enterprise [32, 33]. The mathematics can
`be made rather difficult, by the way, by chosing an inconvenient coor(cid:173)
`he made rather ditheriit, by the way, by chosing an inconvenient coor-
`dinate system. In some cases information about the shape of an object
`dinate system. In some cases information about the shape of an object
`may also be recovered [4, 20, 21].
`may also be recovered [4, 20, 211.
`These papers begin by assuming that the optical flow has already
`These papers begin by assuming that the optical flow has already
`been determined. Although some reference has beer, made to schemes
`been determined. Although some reference has been made to schemes
`for computing the flow from successive views of a scene [7, 12], the
`for computing the flow from successive views of a scene [7, 121, the
`specifics of a scheme for determining the flow from the image have
`specifics of a scheine for determining the flow from the image have
`not been described. Related work has been done in an attempt to
`not been described. Related work has been done in an attempt to
`formulate a model for the short range motion detection processes in
`formulate a model for the short range motion detection processes in
`human vision [2, 24]. The pixel recursive equations of Nctravali and
`human vision [2, 24]. The pixel recursive equations of Netravali and
`Robbins [30], designed for coding motion in television signals, bear
`Robbins [34 designed for coding motion in television signals, bear
`some similarity to the iterative equations developed in this paper.
`some similarity to the iterative equations developed in this paper.
`
`2. Relationship to Object Motion
`2. Relationship to Object Motion
`
`The relationship between the optical flow in the image plane
`The relationship between the optical flow in the image plane
`and the velocities of objects in the three dimensional world is not
`and the velocities of objects in the three dimensional world is not
`necessarily obvious. We perceive motion when a changing picture is
`necessarily obvious. We perceive motion when a changing picture is
`projected onto a stationary screen, for example. Conversely, a moving
`projected onto a stationary screen, for example. Conversely, a moving
`object may give rise to a constant brightness pattern. Consider, for ex(cid:173)
`object may give rise to a constant brightness pattern. Consider, for ex-
`ample, a uniform sphere which exhibits shading because its surface ele(cid:173)
`ample, a uniform sphere which exhibits shading because its surface ele-
`ments are oriented in many different directions. Yet, when it is rotated,
`ments are oriented in many different directions. Yet, when it is rotated,
`the optical flow is zero at all points in the image, since the shading
`the optical flow is zero at all points in the image, since the shading
`does not move with the surface. Also, specular reflections move with
`does not move with the surface. Also, specular reflections move with
`a velocity characteristic of the virtual image, not die surface in which
`a velocity characteristic of the virtual image, not the surface in which
`light is reflected.
`light is reflected.
`For convenience, we tackle a particularly simple world where the
`For convenience, we tackle a particularly simple world where the
`apparent velocity of brightness patterns can be directly identified with
`apparent velocity of brightness patterns can be directly identified with
`the movement of surfaces in the scene.
`the movement of surfaces in the scene.
`
`3. The Restricted Problem Domain
`3. The Restricted Problem Domrain
`
`To avoid variations in brightness due to shading effects we initially
`'l'o avoid variations in brightness due to shading effects we initially
`assume that the surface being imaged is flat. We further assume that
`assume that the surface being imaged is flat. We further assume that
`die incident illumination is uniform across the surface. The brightness
`the incident illumination is uniform across the surface. The brightness
`
`1
`In this paper, the term brightness means image irradiance. The brightness pattern
`In this paper, the term brightness means image irradiance. The brightness pattern
`I
`is the distribution of irradiance in the image.
`is the distribution of irradiance in the image.
`
`SPIE Vol 281 Techniques and Applications of /mage Understanding (1981) / 319
`SP/E Vol. 281 Techniques and Applications of Image Understanding (1981) / 319
`
`Downloaded From: http://proceedings.spiedigitallibrary.org/ on 03/21/2017 Terms of Use: http://spiedigitallibrary.org/ss/termsofuse.aspx
`
`Page 1 of 13
`
`SAMSUNG EXHIBIT 1016
`Samsung v. Image Processing Techs.
`
`

`

`at a point in the image is then proportional to the reflectance of the sur(cid:173)
`at a point in the image is then proportional to the reflectance of the sur-
`face at the corresponding point on the object. Also, we assume at first
`face at the corresponding point on the object. Also, we assume at first
`that reflectance varies smoothly and has no spatial discontinuities. This
`that reflectance varies smoothly and has no spatial discontinuities. This
`latter condition assures us that the image brightness is differentiate.
`latter condition assures its that the image brightness is differentiable.
`We exclude situations where objects occlude one another, in part, be(cid:173)
`We exclude situations where objects occlude one another, in part, be-
`cause discontinuities in reflectance arc found at object boundaries. In
`cause discontinuities in reflectance are found at object boundaries. In
`two of the experiments discussed later, some of the problems occa(cid:173)
`two of the experiments discussed later, some of the problems occa-
`sioned by occluding edges arc exposed.
`sioned by occluding edges are exposed.
`Jn the simple situation described, the motion of the brightness
`In the simple situation described, the motion of the brightness
` patterns in the image is determined directly by the motions of cor(cid:173)
`patterns in the image is determined directly by the motions of cor-
`responding points on the surface of the object. Computing the
`responding points on the surface of the object.
`Computing the
`velocities of points on the object is a matter of simple geometry once
`velocities of points on the object is a matter of simple geometry once
`the optical flow is known.
`the optical flow is known.
`
`4. Constraints
`4. Constraints
`
`We will derive an equation that relates the change in image
`We will derive an equation that relates the change in image
`brightness at a point to the motion of the brightness pattern. Let the
`brightness at a point to the motion of the brightness pattern. I_et the
`image brightness at the point (2,;/) in the image plane at time ( be
`image brightness at the point (x, y) in the image plane at time t be
`denoted by E"(z, %/, f). Now consider what happens when the pattern
`denoted by E(x, y, t). Nov,' consider what happens when the pattern
`moves, 'flic brightness of a particular point in Lhc pattern is constant, so
`movess.'l'hr brightness of a particular point in the pattern is constant, so
`mat
`that
`
`dE
`
` 0
`0
`dt
`Using the chain rule fur differentiation we see that,
`Using the chain rule for differentiation we see that,
`aE
`
`a.rdt aydtat -
`
`aF,dy
`
`dx
`
`5. The Smoothness Constraint
`5. The Smoothness Constraint
`
`If every point of the brightness pattern can move independently,
`If every point of the brightness pattern can move independently,
`there is little hope of recovering the velocities. More commonly we
`there is little hope of recovering the velocities. More commonly we
`view opaque objects of finite size undergoing rigid motion or defor(cid:173)
`view opaque objects of finite size undergoing rigid motion or defor-
`mation.
`In this case neighboring points on the objects have similar
`mation.
`In this case neighboring points on the objects have similar
`velocities and the velocity Acid of the brightness patterns in the image
`velocities and the velocity field of the brightness patterns in the image
`varies smoothly almost everywhere. Discontinuities in flow can be ex(cid:173)
`varies smoothly almost everywhere. Discontinuities in flow can be ex-
`pected where one object occludes another. An algorithm based on a
`pected where one object occludes another. An algorithm based on a
`smoothness constraint is likely to have difficulties with occluding edges
`smoothness constraint is likely to have difficulties with occluding edges
`as a result.
`as a result.
`One way to express the additional constraint is to minimize the
`One way to express the additional constraint is to minimize the
`square of the magnitude of the gradient of the optical How velocity:
`square of the magnitude of the gradient of the optical flow velocity:
`
`2
`
`2
`
`Y
`
`(ax) + (ay)
`
`and
`
`(ax )
`Another measure of the smoothness of the optical flow field is the sum
`Another measure of the smoothness of the optical flow field is the sum
`of the squares of the Laplacians of the two velocity components. The
`of the squales of the Laplacians of the two velocity components. The
`Laplacians oft* and u arc defined as
`Laplacians of u and v are defined as
`
`2
`
`(y)
`
`V2u
`
`á-'u
`(9,2
`
`J-
`r31u
`a z
`
`v2v=
`
`and
`
`a2v
`á2v
`Óz2 + ay2
`
`In simple situations, both Laplacians arc zero. If the viewer translates
`In simple situations, both Laplacians arc zero. If the viewer translates
`parallel to a Oat object, rotates about a line perpendicular to the surface
`parallel to a Ilat object, rotates about a line perpendicular to the surface
`or travels orthogonally to the surface, then the second partial deriva(cid:173)
`or travels orthogonally to the surface, then the second partial deriva-
`tives of both it and t; vanish (assuming perspective projection in the
`tives of both u and y vanish (assuming perspective projection in the
`image formation.)
`image formation.)
`In this paper, we will use the square of the magnitidc of the
`In this paper, we will use the square of the magnitide of the
`gradient as our smoothness measure. Note that our approach is in
`gradient as our smoothness measure. Note that our approach is in
`contrast with that of [7], who propose an algorithm that incorporates
`contrast with that of [7], who propose an algorithm that incorporates
`additional assumptions such as constant flow velocities within discrete
`additional assumptions such as constant flow velocities v ithin discrete
`regions of the image. Their method, based on cluster analysis, cannot
`regions of the image. Their method, based on cluster analysis, cannot
`deal with rotating objects, since these give rise to a continuum of flow
`deal with rotating objects, since these give rise to a continuum of flow
`velocities.
`velocities.
`
`6. Quantization and Noise
`6. Quantization and Noise
`
`Images may be sampled at intervals on a fixed grid of points.
`Images may be sampled at intervals on a fixed grid of points.
`While tessclations other than the obvious one have certain advantages
`While tesselations other than the obvious one have certain'advantages
`[11, 25], fbrcomenicnce we will assume that the image is sampled on a
`[11, 25], for connenicnee we will assume that the image is sampled on a
`square grid at regular intervals. Let the measured brightness beE^t
`square grid at regular intervals. let the measured brightness be E1,1,k
`at the intersection of the i-tli row and j-th column in the A;-th image
`at the intersection of the i-tlt row and j -th column in the k -th image
`frame. Ideally, each measurement should be an average over the area
`frame. Ideally, each measurement should be an average over the area
`of a picture cell and over the length of the time interval. In the experi(cid:173)
`of a picture cell and over the length of the time interval. In the experi-
`ments cited here we have taken samples at discrete points in space and
`ments cited here we have taken samples at discrete points in space and
`time instead.
`time instead.
`In addition to being quantized in space and time, the measure(cid:173)
`In addition to being quantized in space and time, the measure-
`ments will in practice be quantized in brightness as well. Further, noise
`ments will in practice be quantized in brightness as well. Further, noise
`will be apparent in measurements obtained in any real system.
`will be apparent in measurements obtained in any real system.
`
`(See Appendix A for a more detailed derivation.) If we let
`(See Appendix A for a more detailed derivation.) If we let
`
`u
`
`dy
`dx
`_..,
`._
`'e = dt'
`dt
`then it is easy to sec that we have a single linear equation in the two
`then it is easy tu see that we have a single linear equation in the two
`unknowns?* and?;,
`unknowns +t and y,
`
`and
`
`E,-u- f- E,v+Et =0,
`
`where we have also introduced the additional abbreviations f%r, 6^,, and
`where we have also introduced the additional abbreviations E1., E and
`j% for the partial derivatives of im<ige brightness with respect to z, %/
`Et for the partial derivatives of image brightness with respect to x, y
`and (, respectively. The constraint on the local How velocity expressed
`and t, respectively. The constraint on the local flow velocity expressed
`by this equation is illustrated in Figure 1. Writing the equation in still
`by this equation is illustrated in Figure 1. Writing the equation in still
`another way,
`another way,
`
`(E,,EJ.(«*,t/) = -S.
`(Ei, E5) ' (u, v) = -Et.
`Thus the component of the movement in the direction of the bright(cid:173)
`Thus the component of the movement in the direction of the bright-
`ness gradient (Er, ^/) equals
`ness gradient (E,,, E,t) equals
`
``E2
`V x
`
`y
`
`We cannot, however determine the component of the movement in the
`We cannot, however determine the component of the movement in the
`direction of the iso-brightncss contours, at right angles to the bright(cid:173)
`direction of the iso- brightness contours, at right angles to the bright-
`ness gradient. As a consequence, the flow velocity (t&, u) cannot be
`ness gradient. As a consequence, the flow velocity (u, v) cannot be
`computed locally without introducing additional constraints.
`computed locally without introducing additional constraints.
`
`320 / SPIE Vol 281 Techniques and Applications of /mage Understanding (1981)
`320
`
`Downloaded From: http://proceedings.spiedigitallibrary.org/ on 03/21/2017 Terms of Use: http://spiedigitallibrary.org/ss/termsofuse.aspx
`
`SAMSUNG EXHIBIT 1016
`Page 2 of 13
`
`

`

`7. Estimating the Partial Derivatives
`7. Estimating the Partial Derivatives
`
`9. IVlinimi/ation
`9. Minimization
`
`We must estimate the derivatives of brightness from the discrete
`We must estimate the derivatives of brightness from the discrete
`It is important that
`set of image brightness measurements available.
`It is important that
`set of image brightness measurements available.
`the estimates of Ex , Eyt and Et be consistent. That is, they should all
`the estimates of Er, Ey, and E be consistent. That is, they should all
`refer to the same point in the image at the same time. While there
`refer to the same point in the image at the same time. While there
`are many formulas for approximate differentiation [5, 13] we will use
`l3] we will use
`are many f'o17nulas for approximate differentiation 15.
`a set which gives us an estimate ofEx , Ey , Et at a point in the center
`a set which gives us an estimate of Er, Ey, Ei at a point in the center
`of a cube formed by eight measurements. The relationship in space
`of a cube formed by eight measurements. The relationship in space
`and time between these measurements is shown in Figure 2. Bach of
`and time between these measurements is shown in Figure 2. Each of
`the estimates is the average of four first differences taken over adjacent
`the estimates is the average of four first differences taken over adjacent
`measurements in the cube.
`measurements in the cube.
`
`14{Ei,3 +l,k -- Eiit - Ei+t,J+r,k
`Ex f*s*-{
`Ez
`-FEi,7+i,k+i - Ei,7,k+t +Ei+1,J+1,k+1 -Ei-I-1,J,k+1}
`1
`4{Ei+t,í,k -Ei,J,k -i. Ei+i,J+i,k -Ei,J+t,k
`Ey ^-
`Ey
`+Ei+1,7,k+I --Ei,9,k+t +Ei+1,J+1,k-i-1 -Ei,7+1,k+1}
`
`1
`Et &-{
`Et
`
`Ei,i,k+u - Ei,J,k + Ei+r,J,k+i - Ei+1,J,k
`Ei,j+1,k +Ei+1,1+i,k+1
`
`Here the unit of length is the grid spacing interval in each image frame
`Here the unit of length is the grid spacing interval in each image frame
`and the unit of time is the image frame sampling period. We avoid es(cid:173)
`and the unit of time is the image frame sampling period. We avoid es-
`timation formulae with larger support, since these typically arc equiv(cid:173)
`timation formulae with larger support, since these typically are equiv-
`alent to formulae of small support applied to smoothed images [16].
`alent to formulae of small support applied to smoothed images [16].
`
`8. Estimating the Laplacian of the Flow Velocities
`8. Estimating the Laplacian of the Flow Velocities
`
`As will be shown in the next section, we will also need to ap(cid:173)
`As will be shown in the next section, we will also need to ap-
`proximate the I.aplacians of u and v. One convenient approximation
`proximate the l.aplacians of u and v. One convenient approximation
`takes the following form
`takes the following form
`
`V'2 u f*& K,(ui,j,k ^i,j,k)
`i ik
`V212 2t
`
`and V2v .r.;. ic(Zi,J,k -
`and V 2?; ^ K(vij,k ^i,j,k),
`
`where the local averages u and v are defined as follows
`where the local averages it and v are defined as follows
`
`{ui-tJ,k + Ui, J+t ,k + ui-1-1,J,k
`úi,J,k =
`Uijfi = ^ u i-\,j,k + Uij+i tk + Ui-\-\J,k + Ui 7 j_ 1|fe }
`6
`
`+ ^{ ui-\:i-\,k + Ui-ij+ lik + Ui+u+ ltk + ui+lj_i k}
`+ 12 {7le- I.J-t,k1+
`i,Jk = {7Ji-tJk T tii,7+1 ,k + tii.+t,J k + vi,7-1 ,k}
`*>ij,k = 6 {""-I ,3,k + vi,3 + \,k + ViH-lj.fc + "ij-l.fc}
`
`12 {vi-1,J-1,k + tii-t,J+t,k + vi+1,J+1,k + i-}-1,j-1,k)
`The proportionality factor K equals 3 if the average is computed as
`The proportionality factor is equals 3 if the average is computed as
`shown and we again assume that the unit of length equals the grid
`shown and we again assume that the unit of length equals the grid
`spacing interval. Figure 3 illustrates the assignment of weights to neigh(cid:173)
`spacing interval. Figure 3 illustrates the assignment of weights to neigh-
`boring points. The approximation for the Lapbcian using the center
`bodng points. The approximation for the Laplacian using the center
`cell and all eight neighbors is more stable than the usual one based on
`cell and all eight neighbors is more stable than the usual one based on
`the center cell and its four horizontal and vertical neighbors only.
`the center cell and its four horizontal and vertical neighbors only.
`
`The problem then is to minimize the sum of the errors in the
`The problem then is to minimize the sum of the errors in the
`equation for the rate of change of image brightness,
`equation for the rate of change of image brightness,
`
`gb°Ezu+Evv+Et,
`
`and the measure of the departure from smoothness in the velocity flow,
`and the measure of the departure from smoothness in the velocity flow,
`
`g! - (2 h12 +
`
`+ ar2
`
`What should be the relative weight of these two factors? In practice
`What should be the relative weight of these two factors? In practice
`the image brightness measurements will be corrupted by quantization
`the image brightness measurements will be corrupted by quantization
`error and noise so that we cannot expect 6<, to be identically zero. This
`error and noise so that we cannot expect gb to be identically zero. This
`quantity will tend to have an error magnitude that is proportional to
`quantity will tend to have an error magnitude thát is proportional to
`the noise in the measurement. This fact guides us in choosing a suitable
`the noise in the measurement. This fact guides us in choosing a suitable
`weighting factor, denoted by a2 , as will be seen later.
`weighting factor. denoted by a2, as will be seen later.
`Let the total error to be minimized be
`I_et the total error to be minimized be
`
`6 -u a2g + gb dx d y.
`
`The minimization is to be accomplished by finding suitable values for
`The minimization is to be accomplished by finding suitable values for
`the optical flow velocity (u, v). Using the calculus of variations [6, pp.
`the optical flow velocity (u, y). Using the calculus of variations [6, pp.
`191-92], we obtain
`191 -921, we obtain
`EÌu + EEvv = a2 V 2u - ErEt
`E2tu + ExEyv = a2 V 2u ExEt
`ErEqu +Eiv = a2O2v -EyE1.
`E^u + Elv = a2 V 2v - EJSt.
`Using the approximation to the Laplacian introduced in the previous
`Using the approximation to the Laplacian introduced in the previous
`section,
`section,
`
`E1Equ + (a2 + Ey2)v = (a2i - EyEt).
`
`(a2 + E2)u -f- E.,Eyv = (a2ú - E%Et)
`a2 u - ExEt)
`ExEyu + (a2
`The determinant of the coefficient matrix equals a2(a2 -)- E2 + £"2 ).
`Ei + Eÿ)
`The determinant of the coefficient matrix equals a2
`(a2
`Solving for u and v we find that
`Solving for u and y we find that
`(a2 E; -}- E2y)u = + (a2
`EEt
`EL)ü EEyv
`(o2 + E'i + £> = + (a2 + El)u - ExEav - EJ2t
`(a2 + Ei + Ey)v = - E.Eyü -{- (a2
`(a2 + E} + El)v = - £,£> + (a2 + E2> - EyEt .
`EyEt.
`
`10. Difference of How at a Point from Local Average
`l0. Difference of Flow at a Point from Local Average
`
`These equations can be written in the alternate form
`"These equations can be written in the alternate form
`(a2 +E; +E,)(u -ft) =- EX[EÜ -[-E +E1)
`(a2 + El + El)(u - 6) = - Ez [Exu + Eyv + Et]
`(02 + E + Eÿ)(v - v) = - Ey[EÜ + Evv + Ed.
`(a2 + El + El)(v - 0) = - Ey[Ef* + Eyv + Et].
`This shows that the value of the flow velocity (u, v) which minimizes
`This shows that the value of the flow velocity (u, y) which minimizes
`the error 82 lies in the direction towards the constraint line along a
`the error g2 lies in the direction towards the constraint line along a
`line that intersects the constraint line at right angles. This relationship
`line that intersects the constraint line at right angles. This relationship
`is illustrated geometrically in Figure 4. The distance from the local
`is illustrated geometrically in Figure 4. The distance from the local
`average is proportional to the error in the basic formula for rate of
`average is proportional to the error in the basic formula for rate of
`change of brightness when ft, v are substituted for u and v. Finally
`change of brightness when u, v are substituted for u and v. Finally
`we can see that a2 plays a significant role only for areas where the
`we can see that a2 plays a significant role only for areas where the
`brightness gradient is small, preventing haphazard adjustments to the
`brightness gradient is small, preventing haphazard adjustments to the
`estimated flow velocity occasioned by noise in the estimated deriva(cid:173)
`estimated flow velocity occasioned by noise in the estimated deriva-
`tives. This parameter should be roughly equal to the expected noise in
`tives. This parameter should be roughly equal to the expected noise in
`the estimate of £2 +£2 .
`the estimate of E! +E t.
`
`SPIE Vol 281 Techniques and Applications of /mage Understanding (1981 ) / 321
`SP/E Vol. 281 Techniques and Applications of Image Understanding (1981) / 321
`
`Downloaded From: http://proceedings.spiedigitallibrary.org/ on 03/21/2017 Terms of Use: http://spiedigitallibrary.org/ss/termsofuse.aspx
`
`SAMSUNG EXHIBIT 1016
`Page 3 of 13
`
`

`

`11. Const ruined Minimization
`I l. Constrained l\ linimization
`
`When we allow a2 to tend to zero we obtain the solution to a
`When we allow a2 to tend to zero we obtain the solution to a
`constrained minimization problem. Applying the method of Lagrange
`constrained minimization problem. Applying the method of Lagrange
`multipliers [35, 36] to the problem of minimizing Sj! while maintaining
`multipliers [35, 36] to the problem of minimizing b' while maintaining
`6(, = 0 leads to
`gb = 0 leads to
`EyV^u ^ g,V\ g,u + gyv + E"( = 0.
`EEO2u = ErV2v, Emu -[- Eyv -{- Et = O.
`Approximating the Laplacian by me difference of the velocity at a
`Approximating the Laplacian by the difference of the velocity at a
`point and the average of its neighbors then gives us
`point and the average of its neighbors then gives us
`(E,. -}- E211)(u - it) =- - E.[E,.it { Eyv + 1%t]
`(E. .2 + Ey)(v - v) =
`- Eyv + Et].
`Ei[I=
`Referring again to Figure 4, we note that the point computed here lies
`Referring again to Figure 4, we note that the point computed here lies
`at the intersection of the constraint line and the line at right angles
`at the intersection of' the constraint line and the line at right angles
`through the point (u, i>). We will not use these equations since we do
`through the point (v, v). We v\ ill not use these equations since we do
`expect errors in the estimation of the partial derivatives.
`expect errors in the estimation of the partial derivatives.
`
`12. Iterative Solution
`12. Iterative Solution
`
`We now have a pair of equations for each point in the image. It
`We now have a pair of equations for each point in the image. It
`would be very costly to solve these equations simultaneously by one
`would be very costly to solve these equations simultaneously by one
`of the standard methods, such as Gauss-Jordan elimination [13, 14].
`of the standard methods, such as Gauss -Jordan elimination [13, 14].
`The corresponding matrix is sparse and very large since the number
`The corresponding matrix is sparse and very large since the number
`of rows and columns equals twice the number of picture cells in the
`of rows and columns equals twice the number of picture cells in the
`Iterative methods, such as the Gauss-Scidcl method [13, 15],
`image.
`image. Iterative methods, such as the Gauss -Seidel method [13, 15],
`suggest themselves. We can compute a new set of velocity estimates
`suggest themselves. We can compute a new set of velocity estimates
`v +t) from the estimated derivatives and the average of the
`(u""^,u"+') from the estimated derivatives and the average of the
`previous velocity estimates (t*", u") by
`previous velocity estimates (0, v") by
`-E.[Er f +Eye (- Et] /(a2 +Ez +Ey)
`v,+1 =v" - Ey[Erun +Evo + Et] /(a2 + Es + ED.
`
`0 +1
`
`(It is interesting to note that the new estimates at a particular point do
`(It is interesting to note that the new estimates at a particular point do
`not depend directly on the previous estimates at the same point.)
`not depend directly on the previous estimates at the same point.)
`The natural boundary condition for the variational problem turns
`The natural boundary condition for the variational problem turns
`out to be a zero normal derivative. At the edge of the image, some of
`out to be a zero normal derivative. At the edge of the image, some of
`the points needed to compute the local average of velocity lie outside
`the points needed to compute the local average of velocity lie outside
`the image. Here we simply copy velocities from adjacent points further
`the image. Here we simply copy velocities from adjacent points further
`in.
`in.
`
`13. Filling In Uniform Regions
`13. Filling In Uniform Regions
`
`In parts of the image where the brightness gradient is zero, the
`In parts of the image where the brightness gradient is zero, the
`velocity estimates will simply be averages of the neighboring velocity
`velocity estimates will simply be averages of the neighboring velocity
`estimates. There is no local information to constrain the apparent
`estimates. There is no local information to constrain the apparent
`velocity of motion of the brightness pattern in these areas. Eventually
`velocity of motion of the brightness pattern in these areas. Eventually
`the values around such a region will propagate inwards. If the velocities
`the