Michael J. Black: Thesis

Robust Incremental Optical Flow

Ph.D. Thesis, Yale University, Department of Computer Science. Research Report YALEU-DCS-RR-923, 1992.

This thesis addresses the problem of recovering 2D image velocity, or optical flow, robustly over long image sequences. We develop a robust estimation framework for improving the reliability of motion estimates and an incremental minimization framework for recovering flow estimates over time.

Attempts to improve the robustness of optical flow have focused on detecting and accounting for motion discontinuities in the optical flow field. We show that motion discontinuities are one example of a more general class of model violations and that by formulating the optical flow problem as one of robust estimation the problems posed by motion discontinuities can be reduced, and the violations can be detected. Additionally, robust estimation provides a powerful framework for early vision problems that generalizes the popular ``line process'' approaches.

We formulate a temporal continuity constraint, which reflects the fact that the motion of a surface changes gradually over time. We exploit this constraint to develop a new incremental minimization framework and show how it is related to standard recursive estimation techniques. Within this framework we implement two incremental algorithms for minimizing non-convex objective functions over time; Incremental Stochastic Minimization (ISM) and Incremental Graduated Non-Convexity (IGNC).

With this approach, motion estimates are always available, they are refined over time, the algorithm adapts to scene changes, and the amount of computation between frames is kept fixed. The psychophysical implications of temporal continuity are discussed and the power of the incremental minimization framework is demonstrated by extending image feature extraction over time.

Retrieve the postscript. (2MB compressed, 10MB uncompressed)
Retrieve the pdf. (1.8MB uncompressed)

Historical Observation:

The thesis proposed an Incremental Stochastic Minimization algorithm not unlike the modern-day particle filter. The goals and sampling framework are very similar however the ISM algorithm provided a stochastic search for the maximum a posteriori estimate rather than a discrete approximation to the full posterior distribution.

Related Publications

Black, M., Rangarajan, A., On the unification of line processes, outlier rejection, and robust statistics with applications in early vision, International Journal of Computer Vision Vol. 19, No. 1, pp. 57-92, July, 1996. (abstract)

Black, M. J. and Anandan, P., The robust estimation of multiple motions: Parametric and piecewise-smooth flow fields, Computer Vision and Image Understanding, CVIU, 63(1), pp. 75-104, Jan. 1996. (abstract) (software)

Black, M. J. and Anandan, P., A framework for the robust estimation of optical flow, Fourth International Conf. on Computer Vision, ICCV-93, Berlin, Germany, May, 1993, pp. 231-236. (postscript)

Black, M. J. and Anandan, P., Robust dynamic motion estimation over time, Proc. Computer Vision and Pattern Recognition, CVPR-91, Maui, Hawaii, June 1991, pp. 296-302. (abstract) (postscript)

Black, M. J. and Anandan, P., A model for the detection of motion over time, Proc. Int. Conf. on Computer Vision, ICCV-90, Osaka, Japan, Dec. 1990, pp. 33-37; also Yale Research Report YALEU/DCS/RR-822, September 1990. (abstract)

Tarr, M. J. and Black, M. J., Psychophysical implications of temporal persistence in early vision: A computational account of representational momentum, Investigative Ophthalmology and Visual Science Supplement, Vol. 33, May 1992, p. 1050. (abstract)

Black, M., Recursive non-linear estimation of discontinuous flow fields, Proc. Third European Conf. on Computer Vision, ECCV'94, J. Eklundh (Ed.), Springer Verlag, LNCS 800, Stockholm, Sweden, May 1994, pp. 138-145. (abstract)

Black, M. J., Combining intensity and motion for incremental segmentation and tracking over long image sequences, in Proc. Second European Conf. on Computer Vision, ECCV-92, G. Sandini (Ed.), Springer Verlag, LNCS 588, May 1992, pp. 485-493. (abstract)