Constraints for the Estimation of Displacement Vector Fields From Image Sequences
Proceedings of the Eighth International Joint Conference on Artificial Intelligence. Vision. Pages 945-950.
© 1983 International Joint Conferences on Artificial Intelligence
Abstract
Smoothness constraints have been used to facilitate the estimation of displacement vector fields. Differing from HORN and SCHUNCK 81 who employ a general smoothness requirement, this contribution reports an analysis of an "oriented smoothness" requirement: a change in the displacement vector field is only constrained in the direction perpendicular to the characteristic gray value variation based on which the displacement vector is estimated. An iterative solution for the resulting system of nonlinear partial differential equations is developed. It is shown how this system of equations relates to the one derived by HORN and SCHUNCK 81.
- Nagel 82b Overview on Image Sequence Analysis H.-H. Nagel Proc. NATO Advanced Study Institute on Image Sequence Processing and Dynamic Scene Analysis, June 22-July 2, 1982, Braunlage/FR Germany;
- T.S. Huang (ed.), Springer-Verlag Berlin/Heidel- berg/New York 1983 Nagel 83a Displacement Vectors Derived from Second Order Intensity Variations in Image Sequences H.-H. Nagel Computer Vision, Graphics, and Image Processing 21 (1983) 85-117
- Nagel 83b On the Estimation of Dense Displacement Vector Fields from Image Sequences H.-H. Nagel Proc. ACM SIGGRAPH/SIGART Interdisciplinary Workshop on Motion: Representation and Percep- tion, Toronto/Canada, April 4-6, 1983,pp.59-65 Nagel and Enkelmann 82 Investigation of Second Order Greyvalue Varia- tions to Estimate Corner Point Displacements H.-H. Nagel and W. Enkelmann Proc. Int. Conference on Pattern Recognition, Munich, October 19-22, 1982, pp. 768-773
- Nagel and Enkelmann 83 Iterative Estimation of Displacement Vector Fields from TV-Frame Sequences H.-H. Nagel and W. Enkelmann Proc. Second European Signal Processing Confer- ence EUSIPC:0-83) Erlangen/FR Germany, September 12-16, 1983 (in press)
- Schunck and Horn 81 Constraints on Optical Flow Computation B.G. Schunck and B.K.P. Horn Proc. IEEE PRIP-81, Dallas/TX, August 3-5, 1981, pp. 205-210
- Wu et al. 82 Determining Velocities by Propagation Z. Wu, H. Sun, and L.S. Davis Proc. ICPR-82, Munich/FR Germany, October 19-22, 1982, pp. 1147-1149 Yachida 82 Determining Velocity Maps by Spatia-Temporal Neighborhoods from Image Sequences M. Yachida preprint (February 1982), Dept. of Control Eng., Osaka University, Osaka/Japan; see, too, Proc. IJCAI-81, pp. 716-718.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1. INTRODUCTION
The reliable estimation of displacement vector fields is of great importance for the interpreta tion of image sequences about scenes with tempo ral variations. An upsurge of interest in this topic during the last few years has led to a con siderable number of contributions which attack this estimation problem. The majority among them attempt to estimate the displacement vector only at isolated image locations. Moreover, they are , based on more or less ad-hoc approaches which have not been investigated sufficiently to allow a re liable judgement on their validity and their lim its of applicability. A recent survey of the lit erature about this topic can be found in NAGEL 82a+b.
HORN and SCHUNCK 81 took an important step away from ad-hoc solutions towards a more systematic approach. They started from a well-known approxi mation (see NAGEL 81 for references to the earli er literature) which rel~es the spatial gray val ue gradient Vg = (g., gy) to the temporal change g~ = dg/dt in order to estimate the interframe displacement U = (u, v)T of certain image regions

Since equation (1) is insufficient to determine both components of the displacement vector field U(X), HORN and SCHUNCK 81 demand in addition that the displacement vector field varies smoothly as a function of the position vector X in the image. This requirement is combined with equation (1) in the following minimization approach:
Hans-Hellmut Nagel und 7500 Karlsruhe 1 I FR Germany

They employ the variational calculus to transform equation (2) into a system of second order partial differential equations for the two components u(X) and v(X). Using a particular approximation on a 3x3 pixel grid for the Laplacian of u and v, this system of two coupled partial differential equa tions has been converted into a sparse system of linear equations with two unknowns for each pixel in the image. An iterative solution of this large system of equations has been employed in order to study various examples.
Two aspects of this approach let it appear espe cially attractive. First, all hypotheses are in troduced explicitly into a rigorous mathematical framework. Second, well-known mathematical methods are employed to derive the solution so that the consequences of the various hypotheses and approxi mations can be studied in detail. One can recognize three sources of difficulties in the approach of HORN and SCHUNCK 81:
- The smoothness requirement is applied indis criminately across all gray value edges de spite the fact that such edges might separate image regions with discontinuous displacement vector fields (see SCHUNCK and HORN 81).
- ii) No advantage is taken of the fact that cer tain nonlinear gray value variations may con strain possible displacement vectors much stronger than image areas with smoothly vary ing gray values or straight line gray value transitions.
- iii) The solution outlined in HORN and SCHUNCK 81 does not indicate how to handle situations where a two-pixel gradient estimate or an approximation to the Laplacian based on a 3x3 pixel window appear inappropriate.
2. "ORIENTED SMOOTHNESS" REQUIREMENTS
Several approaches have been investiqated in order to cope especially with difficulty (i). YACHIDA 82 assumes that a displacement vector can be esti mated at prominent points. He propagates such esti mates into neighboring areas with large gray value gradients, based on the method of HORN and SCHUNCK
81. His iterative improvement scheme, however, em ploys the inverse variance of displacement esti mates from a 5x5 window as a weight in order to suppress the propagation of displacement estimates with large local variations.
CORNELIUS and KANADE 83 deactivate the smoothness requirement in the neighborhood of zero-crossing contours in order to avoid that estimates spill across potential discontinuities of the displace ment vector field, for example associated with occluding contours.
WU et al. 82 propagate a displacement estimate only along a contour line between corner points. At each new contour point, they combine the esti mated displacement vector from the previous con tour point with new estimates of the contour di rection and of the displacement component perpen dicular to the contour in order to update the tangential component of the displacement vector.
HILDRETH 83 minimizes the sum of two terms, inte grated along a zero-crossing contour. The first term is the squared difference between the 'meas ured' and the estimated displacement component perpendicular to the contour. The second term rep resents the squared derivative of the displacement vector field with respect to the arclength along the zero-crossing contour, expressing the smooth ness requirement (see also HILDRETH 82).
The current contribution proposes a broader ap proach. An "oriented smoothness" r'equirement will be introduced, constraining the variation of the displacement vector field only in those directions alonq which a displacement vector component can not be infe_rred from the spatia-temporal gray val ue changes. This "oriented smoothness" constraint will be tied directly to the gray value variation, th s avoiding the introduction of additional machinery such as the variance of displacement estimates or the separate, prior determination of gray value contour lines. Moreover, a single mini mization task will be used both to estimate dis placement vector fields from nonlinear gray value variations and to take into account the "oriented smoothness" requirement.
Two possibilities will be formulated to express an "oriented smoothness" constraint. Both can be com bined into a weight matrix which constrains the variation of the displacement vector field (NAGEL 83b). A matrix with the same structure appeared in earlier investigations to estimate displacement vectors at gray value corner points (NAGEL 83a). Experiments with this earlier approach yielded encouraging results (NAGEL and ENKELMANN 82 + 83) and thus motivated the current investigation.
3. SMOOTHNESS PERPENDICULAR TO THE GRADIENT DIRECTION
As it is well known, equation (1) only restricts the displacement vector U along the gradient di rection. It is therefore demanded that the varia tion of U in the direction perpendicular to the gradient direction becomes as small as possible. The first variation of U is captured by . the func tional matrix of first derivatives where ux = ou/ox' etc.:
A vector perpendicular to the gray value gradient Vg = (gll, g_).,. is given by (g , -gx)'T'. The varia tion of U ir the direction pefpendicular to the gradient orientation is given by the vector
In order to minimize this variation of U we need a scalar entity which can be simply obtained by forming the scalar product of this vector (4) wi th
It is a known matrix theorem that the trace of a product of two matrices which yields a square ma trix remains the same if the two matrix factors are swapped - even if the two matrix factors are non-square. Since the scalar product of (4) with itself results in a square 1x1 matrix, we may
The outer product matrix of rank one
thus appears as a weight matrix in an expression (6b) which represents one possibility to define a norm of a matrix.
4. SMOOTHNESS PERPENDICULAR TO PRINCIPAL CURVATURE DIRECTIONS
There are situations where the gradient vanishes and nevertheless the gray values exhibit a charac teristic variation, for example a relative ex tremum of the gray value. Since such positions are locally unique, it appears attractive to estimate their displacement because it should allow the~ determination of both components of U = (u, v) .
Let us assume that the image coordinate system has been aligned with the principal curvature direc tions of g(X) at location X. The matrix of second partial derivatives of g(X) with respect to x and y will, therefore, be diagonal
with g = ~ 2 g/OX 2 etc. XX U
A strong curvature gxx of g(X) along the x-direc tion represents a characteristic gray value varia tion which should allow to determine the x-compo nent u of the displacement vector. We therefore demand only that the variation of the displacement vector along the other principal curvature is kept small, for example by minimizing some expression of the product gxx · u as well as gxx · v!t. In a nalogy, a strong curvMture.g~~ of g(X) along t~e y-direction should result 1n a smoothness requlre ment only for the x-direction. This could be for mulated by minimizing the product g~~· ux and g~~ · vx.
Exploiting our special coordinate conventio~s~ these requirements can be expressed by comb1n1ng equation (8) with the functional matrix VU from equation (3) to form
which contains just the products we are interested in. Now we drop the assumption that the coordinate system is aligned with the principal curvat~re di rection and exploit our knowledge that the 1nverse of VVg can be expressed as
Equation (9) can therefore be written in a general form:
~ce the matrix on the right hand side of equa-( 1 ~ tion (11) can be conceived as the combination of two column vectors, we employ a matrix notation to compute the. equivalent to equation (6a) for each of these column vectors:

5. COMBINATION OF BOTH SMOOTHNESS REQUIREMENTS
Since it cannot be said in general which require ment appears more important, both are combined in the form

with
Here, b denotes a normalization factor whereas the factor a 2 - with the dimension of the squared unit of length - measures the relative strenghts be tween these two contributing weight matrices. The intent formulated so far has been to minimize the variation of U in particular directions indicated by properties of the gray value distribution at a location X. In order to obtain some normalization with respect to the size of the gradient vector or the curvature matrix, we look for a norm of the weight matrix F. Experience with a matrix of simi lar structure reported in NAGEL and ENKELMANN 83 suggests
should be used as the normalized weight matrix where F is given by equation (13b). Straightfor ward calculations show that (14) represents the inverse of the matrix
6. MINIMIZATION APPROACH
We now have all the ingredients to formulate the expression to be minimized, using the notation g1(X) = g(X,t~) and g2(X) = g(X,t 4 ):
It is assumed that the gray values do not change · except for position and possibly the effects of (dis-)occlusion. The first term of this expression has been introduced and discussed in NAGEL 83a. This expression specializes to the approach of HORN and SCHUNCK 81 if we make the following as sumptions:
- The influence of smoothness requirements ori ented alonq the principal curvature direc tions is dropped, i.e. a 2 =D.
- ii) The directional sensitivity of the smooth ness requirement is suppr~sed, i.e. the out er product matrix (Vg)(Vg)' is replaced by the unit matrix.
- iii) The difference in the first term of equation (16) is approximated by a first order Taylor expansion.
The Euler-Lagrange equations for the minimization problem of (16) yield
The right hand side immediately shows that large eigenvalues of the matrix C tend to suppress the influence from the smoothness requirement in their direction.
"Gray value corners" can be characterized as the location of maximum curvature in the locus line of extremal gray value slope (see NAGEL 83a). At gray value corners, both eigenvalues become large and damp down the influence of the smoothness require ment. This is advantageous because a gray value corner is defined well enough to allow the deter mination of both displacement vector components by "virtually local" measurements.
According to our assumptions we may write for not to 1 arge U
The dotted underline indicates the operand of the differentiation operators. An analogous equation&8~ results for the second component v of U.
Let c~ denote the upper left eigenvalue of C and c~ the other eigenvalue. Assume that the coordi nate system happens to be chosen in such a way that the matrix Cat location X is diagonal. Then the smoothness term for the first component of the displacement vector takes the form:
Since
the coupled system (17) of partial differentiat equations can therefore be written as
7. APPROXIMATIVE SOLUTION
In order to get some insight into the structure of solutions of the system of two equations (22) we assume that an approximative solution U (X) is known. The true solution U(X) should differ from U 0 (X) by a small correction vector field .1U(X):
t,U(X) = (t,u(X), t. v(X)) is supposed to be small so that we may neglect terms with higher than first powers of components of ~U :
The second bracket in equation (22) contains a term which corresponds to the slope of g1 at loca tion X-U. This term is approximated by the slope of g1 at location x-uo:
Introduction of these approximations into equa tion (22) yields a system of equations which are linear in the components of the correction vector field U(X) :
It appears natural to evaluate all partial deriv atives of g1(X) at the location X-U 0 , including those which enter through the "smoothness" term multiplied bycx 2 · We obtain
This system of linear equations for.1U cannot be solved without f~ther consideration because the matrix (~g1)(~g1) has been derived from an outer product and, therefore, has only rank one rather than two.
A way to cope with this problem is suggested by earlier investigations. For digitized images, the partial derivatives of g(X) are computed using the operators of BEAUDET 78 which are based on a bivariate polynomial approximation of g(X) within a square window centered at X. The same operators should be used to compute the partial derivatives of U(X) which appear, for example, in equation (22). In this manner, a more general approach than that described by HORN and SCHUNCK 81 is employed here. The use of these operators implies that the entities appearing in equation (22) are the result of a kind of averaging across the operator win dow.
zero. Moreover, the strength~ 2 of the smoothness term in equation (27) is taken to be a function of the iteration count. It is set to zero initially. If the window is reasonably small, we may represent the first derivative of g as a linear function of the deviation (§, 7) from the window center:
Introduction of these approximations into equati~ (27), forming the average over the window and using the fact that the window is squared and centered at the origion of the local coordinate sys tern (!, ( ) with the consequences
as well as leads to the result:
P· 2: If we equate s = ~ with the constant a 2 which has been introduced to denote the relative strength between the gradient term and the curvature term in the smoothness requirement - see equation (13) - then equation (30) becomes identical to the defini tion of the matrix C in equation (15).
This matrix has the full rank of two if both prin cipal curvatures of the gray value distribution at location X differ significantly from zero. In this case we may invert the modified equation (27) and obtain
U = U 0 + .1U =flU at image locations where the con ditions for a "gray value corner" are satisfied. It is, therefore, suggested to estimate U at such locations using equation (31b). Once these esti mates have stabilized after a certain number of iterations, the start value U(X) at all other locations is set to zero and the smoothness con straint is switched on by setting oc 2 to the de: sired value. During the subsequent iterations, equations (31a) are employed, using the BEAUDET operators to compute the required derivatives of g1(X-U0 ) as well as U(X). The smoothness term will spread the non-zero estimates of the displacement vectors which have been obtained during the first few iterations at the "gray value corners". The matrix C is prevented from becoming singular by introduction of minimum values for the partial derivatives of g derived from the errors in the gray value measurements (see appendix of NAGEL 83a).
8. DISCUSSION
In order to overcome some problems with the ap proach of HORN and SCHUNCK 81 , the concept of "oriented smoothness constraint" has been. intro duced. As a result, a coupled system of nonlinear partial differential equations (22) for the dis placement vector field U(X) has been derived. In order to study solutions of this system, an iter ative method has been employed which is based on earlier experience. This approach comprises three steps:

This result has to be handled in the following manner: initially, 01.. 2 = o and U 0 (X):= 0. It has been shown (NAGEL 83a, NAGEL and ENKELMANN 83) that
yields a very reasonable estimate of The first two steps have already been implemented during investigations of the approach presented in NAGEL 83a. The very encouraging results have been presented in NAGEL and ENKELMANN 82 for step i) and in NAGEL and ENKELMANN 83 for step ii). The experience gained through these studies led to the - heuristic - proposal to use the inverse of the matrix given in equation (30) as a weight for some kind of oriented smoothness requirement (NAGEL 83b) The current contribution is an attempt to derive this heuristic suggestion in a rigorous manner from clearly stated assumptions. Moreover, all ap proximations are outlined in a derivation of a closed expression for an interative solution to the discretized version of the resulting system of coupled nonlinear partial differential equations. This approach is currently being studied experimen tally.
i) Estimate both components of the displacement vector at "gray value corners" - see equa tion (31 b);
ii) Improve these estimates through iteration at such locations, still with suppressed smooth ness constraint;
iii) Spread the resulting estimates by further iterations, but now taking into account the "oriented smoothness constraint" as repre sented in equation (31a).
9. ACKNOWLEDGEMENT
I thank W. Enkelmann for many discussions during our experimental investigations. Valuable comments by G. Winkler on a draft version of this contribu tion are gratefully acknowledged.
10. REFERENCES
- Beaudet 78 Rotationally Invariant Image Operators P.R. Beaudet ICPR-78, pp. 579 - 583
Cornelius and Kanade 83 Adapting Optical Flow to Measure Object Motion in Reflectance and X-Ray Image Sequences N. Cornelius and T. Kanade Proc. ACM SIGGRAPH/SIGART Interdisciplinary Workshop on Motion: Representation and Percep tion, Toronto/Canada, April 4-6, 1983,pp.50-58
- Hildreth 82 The Integration of Motion Information along Contours E.C. Hildreth Proc. Workshop on Computer Vision: Representa- tion and Control, Rindge/NH, August 23-25, 1982' pp. 83-91
- Hildreth 83 Computing the Velocity Field along Contours E. C. Hildreth Proc. ACM SIGGRAPH/SIGART Interdisciplinary Workshop on Motion : Representation and Percep tion, Toronto/Canada, April 4-6, 1983, pp.26-32
- Horn and Schunck 81 Determining Optical Flow B.K.P; Horn and B.G. Schunck Artificial Intelligence 17 (1981) 185-203
- Nagel 81 Image Sequence Analysis: What Can We Learn from Applications? H.-H. Nagel in Image Sequence Analysis, pp. 19-228 T.S. Huang (ed.) Springer-Verlag Berlin/Heidelberg/New York 1981
- Nagel 82 a Recent Advances in Motion Interpretation Based on Image Sequences H.-H. Nagel Proc. International Conference on Acoustics, Speech, and Signal Processing
Paris, May 3-5, 1982, pp. 1179-1186. Nagel 82b Overview on Image Sequence Analysis H.-H. Nagel Proc. NATO Advanced Study Institute on Image Sequence Processing and Dynamic Scene Analysis, June 22-July 2, 1982, Braunlage/FR Germany; berg/New York 1983
- Wu et al. 82 Determining Velocities by Propagation Z. Wu, H. Sun, and L.S. Davis 1982, pp. 1147-1149
T.S. Huang (ed.), Springer-Verlag Berlin/Heidel Nagel 83a Displacement Vectors Derived from Second Order Intensity Variations in Image Sequences H.-H. Nagel Computer Vision, Graphics, and Image Processing 21 (1983) 85-117 Nagel 83b On the Estimation of Dense Displacement Vector Fields from Image Sequences H.-H. Nagel Proc. ACM SIGGRAPH/SIGART Interdisciplinary Workshop on Motion: Representation and Percep tion, Toronto/Canada, April 4-6, 1983,pp.59-65 Nagel and Enkelmann 82 Investigation of Second Order Greyvalue Varia tions to Estimate Corner Point Displacements H.-H. Nagel and W. Enkelmann Proc. Int. Conference on Pattern Recognition, Munich, October 19-22, 1982, pp. 768-773 Nagel and Enkelmann 83 Iterative Estimation of Displacement Vector Fields from TV-Frame Sequences H.-H. Nagel and W. Enkelmann Proc. Second European Signal Processing Confer ence EUSIPC:0-83) Erlangen/FR Germany, September 12-16, 1983 (in press) Schunck and Horn 81 Constraints on Optical Flow Computation B.G. Schunck and B.K.P. Horn Proc. IEEE PRIP-81, Dallas/TX, August 3-5, 1981, pp. 205-210 Proc. ICPR-82, Munich/FR Germany, October 19-22,
- Yachida 82 Determining Velocity Maps by Spatia-Temporal Neighborhoods from Image Sequences M. Yachida preprint (February 1982), Dept. of Control Eng., Osaka University, Osaka/Japan; see, too, Proc. IJCAI-81, pp. 716-718.
@inproceedings{ijcai1983p223,
title = {Constraints for the Estimation of Displacement Vector Fields From Image Sequences},
author = {Nagel, Hans-Hellmut},
booktitle = {Proceedings of the Eighth International Joint Conference on
Artificial Intelligence, {IJCAI-83}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Alan Bundy},
pages = {945--950},
year = {1983},
note = {Vision},
url = {https://ijcai.org/proceedings/1983/223},
}
TY - CPAPER TI - Constraints for the Estimation of Displacement Vector Fields From Image Sequences AU - Nagel, Hans-Hellmut T2 - Proceedings of the Eighth International Joint Conference on Artificial Intelligence, IJCAI-83 PB - International Joint Conferences on Artificial Intelligence PY - 1983 SP - 945 EP - 950 UR - https://ijcai.org/proceedings/1983/223 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: