Image analysis – Applications – Motion or velocity measuring
Reexamination Certificate
1999-09-08
2003-01-14
Boudreau, Leo (Department: 2621)
Image analysis
Applications
Motion or velocity measuring
C382S103000
Reexamination Certificate
active
06507661
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to generally to the field of machine vision, and in particular to a method for efficiently estimating the optical flow between two or more images.
BACKGROUND OF THE INVENTION
Motion estimation is an important issue which arises in many different machine vision tasks, such as robotics (including navigation and obstacle avoidance), autonomous vehicles, medical image analysis (including nonrigid motion such as angiography), etc. When the motion between two or more generally sequential images is small, it is described by the optical flow defined as the two-dimensional motion field between two different views. The optical flow indicates objects in the image which are moving, where they are moving to and how fast.
Under a constant brightness assumption (“CBA”), the pixel motion can be constrained along a single dimension. However, since the flow at a pixel has two components (i.e. orientation (direction and angle) and magnitude (i.e. speed)), optical flow estimation is an inherently difficult problem. Consequently, several attempts have been made to address this problem.
Most prior art methods overcome this problem by “regularizing” the flow field, i.e. by enforcing some form of smoothness on the flow field. See K. Horn et al., “Determining Optical Flow,”
Artificial Intelligence, Vol.
17, pp. 185-203 (1981); H. Nagel et al., “On The Estimation Of Optical Flow: Relations Between Different Approaches And Some New Results,”
Artificial Intelligence,
Vol. 33, pp. 299-324 (1987). The CBA can also be cast as an energy minimization, where the flow field is estimated by minimizing the least squares difference between two images. See P. Anandan, “A Computational Framework And An Algorithm For The Measurement Of Structure From Motion,”
Int'l Journal of Computer Vision,
Vol. 2, pp. 283-310 (1989); A. Singh,
Optic Flow Computation: A Unified Perspective,
IEEE Computer Society Press (1992). Optical flow can also be computed by “intersecting” local brightness constraints over a small image patch. See B. Lucas et al., “An Iterative Image Registration Technique With An Application To Stereo Vision,”
DARPA IU Workshop,
pp. 121-130 (1981). The smoothness problem can also be addressed by fitting a parametric global motion model. See S. Srinivasan et al., “Optical Flow Using Overlapped Basis Functions For Solving Global Motion Problems,”
Proceedings of European Conference on Computer Vision,
Freiburg, Germany, pp. 288-304 (1998).
Many prior art estimation methods achieve a balance between the brightness constraint and smoothness by minimizing a cost function. Since they depend on iterative, non-linear techniques, these methods are not guaranteed to converge to the global minimum and thus give unsatisfactory results when they converge to a local minimum.
The method of the present invention overcomes the above limitations by formulating the problem of flow estimation as a labeling problem in a Markov Random Field (“MRF”) framework. Thus, the present invention solves for the dense, non-parametric flow while preserving discontinuities in the flow field.
For certain classes of MRF's, the exact Maximum A Posteriori (“MAP”) estimate can be obtained efficiently by a maximum flow computation on a graph. Being guaranteed to be optimal, this computation avoids the problem of local minima. For examples of some recent methods that use the MRF formulation and a graph-theoretic solution, see: S. Roy et al., “A Maximum-Flow Formulation Of The n-Camera Stereo Correspondence Problem,”
Int'l Conference on Computer Vision,
Mumbai, India, pp. 492-499 (1998); U.S. patent application. Ser. No. 08/978,834, filed Nov. 26, 1997, by S. Roy entitled “Maximum Flow Method For Stereo Correspondence” (hereinafter referred to as “the '834 Application,” and which is hereby incorporated herein by this reference); H. Ishikawa et al., “Occlusions, Discontinuities, and Epipolar Lines In Stereo,”
Proceedings of European Conference on Computer Vision,
Freiburg, Germany, pp. 232-237 (1998); Y. Boykow et al., “Markov Random Fields With Efficient Approximations,”
Proceedings of IEEE Conference on Computer Vision and Pattern Recognition,
pp. 648-655 (1998).
Another significant problem in flow estimation is the computation of image derivatives. Since the image is discretized in the spatial, temporal and intensity dimensions, the accuracy of the discrete computation of spatio-temporal derivatives is limited. This problem is partially addressed by sophisticated derivative filters. In practice, the derivatives are also corrupted due to deviations from the constant brightness assumption such as change of illumination, brightness scaling and specularities. Hence the brightness constraint should not be considered to be a “true” rigid constraint. To capture and account for this notion of uncertainty, the present invention casts the brightness constraint in a probabilistic framework. A related example of a probabilistic interpretation of optical flow is described in an article by E. Simoncelli et al. entitled “Probability Distributions of Optical Flow,” in
Proceedings of IEEE Conference on Computer Vision and Pattern Recognition,
pp. 310-315 (1991), which overcomes some of the problems of non-probabilistic approaches but suffers in performance from an oversimplistic optical flow model which fails to account for nonlinear characteristics of optical flow probabilities and fails to properly account for errors in image derivatives.
What is needed is a method for estimating optical flow that properly models the errors in the measurement of image derivatives while enforcing the brightness constraint, and which also efficiently provides a globally optimal solution to the optical flow in the context of said model.
SUMMARY OF THE INVENTION
Generally speaking, in accordance with the invention, a method for estimating the optical flow between a plurality of images is provided. The method includes obtaining a motion orientation component and a motion magnitude component. Determining the motion orientation component includes creating, a first graph using spatio-temporal derivatives of the plurality of images, solving for a first maximum-flow in the first graph to thereby obtain a first minimum-cut therefrom, and computing the motion orientation component from the first minimum-cut. Determining the motion magnitude component includes creating a second graph using spatio-temporal derivatives of the plurality of images and the motion orientation component, solving for a second maximum-flow in the second graph to thereby obtain a second minimum-cut therefrom, and computing the motion magnitude component from the second minimum-cut. The motion orientation component and the motion magnitude component together comprise the estimate of the optical flow between the plurality of images. The method properly models errors in the measurement of image derivatives while enforcing a brightness constraint, and efficiently provides a globally optimal solution to the optical flow in the context of the model.
Accordingly, an object of the invention is to provide a method for estimating optical flow which efficiently and accurately estimates the optical flow between a plurality of images.
Another object of the invention is to provide a method for estimating optical flow which properly models errors in the measurement of image derivative while enforcing a constant brightness assumption constraint.
A further object of the invention is to provide a method for estimating optical flow which efficiently provides a globally optimal solution to the optical flow in the context of its model.
Other objects of the present invention will become more readily apparent in light of the following description in conjunction with the accompanying drawings.
REFERENCES:
patent: 5680487 (1997-10-01), Markandey
patent: 5684887 (1997-11-01), Lee et al.
patent: 5751838 (1998-05-01), Cox et al.
Barron, J.L. et al., “Performance of Optical Flow Techniques”,Int. J. Computer Vision,2(1): 43-77, 1994.
Horn, K. et al., “Deter
Azarian Seyed
Boudreau Leo
Isztwan Andrew G.
NEC Research Institute Inc.
LandOfFree
Method for estimating optical flow does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for estimating optical flow, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for estimating optical flow will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3054008