Abstract

Conventional techniques for the computation of optical flow from image gradients are used to formulate the problem as a nonlinear optimization that comprises a gradient constraint term and a field smoothness factor. The results of these techniques are often erroneous, highly sensitive to noise and numerical precision, determined sparsely, and computationally expensive. We regularize the gradient constraint equation by modeling optical flow as a linear combination of a set of overlapped basis functions. We develop a theory for estimating model parameters robustly and reliably. We prove that the extended-least-squares solution proposed here is unbiased and robust to small perturbations in the gradient estimates and to mild deviations from the gradient constraint. Our solution is obtained with a numerically stable sparse matrix inversion, which gives a reliable flow-field estimate over the entire frame. To validate our claims, we perform a series of experiments on standard benchmark data sets at a range of noise levels. Overall, our algorithm outperforms by a wide margin the others considered in the comparison. We demonstrate the applicability of our algorithm to image mosaicking and to motion superresolution through experiments on noisy compressed sequences. We conclude that our flow-field model offers greater accuracy and robustness than conventional optical flow techniques in a variety of situations and permits real-time operation.

© 1999 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. J. Barron, D. Fleet, S. Beauchemin, “Performance of optical flow techniques,” Int. J. Comput. Vis. 12, 43–77 (1994) (software and test sequences available at ftp.csd.uwo.ca/pub/vision).
    [CrossRef]
  2. B. Horn, B. Schunck, “Determining optical flow,” Artif. Intel. 17, 185–203 (1981).
    [CrossRef]
  3. H. Nagel, “On the estimation of optical flow: relations between different approaches and some new results,” Artif. Intel. 33, 299–324 (1987).
    [CrossRef]
  4. S. Uras, F. Girosi, A. Verri, V. Torre, “A computational approach to motion perception,” Biol. Cybern. 60, 79–87 (1989).
    [CrossRef]
  5. B. Lucas, T. Kanade, “An iterative image registration technique with an application to stereo vision,” in Proceedings of the International Joint Conference on Artificial Intelligence (IEEE Computer Society Press, Los Alamitos, Calif., 1981), pp. 674–679.
  6. P. Anandan, “Measuring visual motion from image sequences,” Ph.D. dissertation (University of Massachusetts, Amherst, Mass., 1987).
  7. A. Singh, “An Estimation-Theoretic Framework for Image-Flow Computation,” in Proceedings of the Third International Conference on Computer Vision (IEEE Computer Society Press, Los Alamitos, Calif., 1990), pp. 168–177.
  8. E. P. Simoncelli, “Distributed representation and analysis of visual motion,” Ph.D. dissertation (Massachusetts Institute of Technology, Cambridge, Mass., 1993).
  9. A. Waxman, J. Wu, F. Bergholm, “Convected activation profiles and the measurement of visual motion,” in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (IEEE Computer Society Press, Los Alamitos, Calif., 1988), pp. 717–723.
  10. D. Fleet, A. Jepson, “Computation of component image velocity from local phase information,” Int. J. Comput. Vis. 5, 77–104 (1990).
    [CrossRef]
  11. J. Kearney, W. Thompson, D. Boley, “Optical flow estimation: an error analysis of gradient-based methods with local optimization,” IEEE Trans. Pattern. Anal. Mach. Intell. 9, 229–244 (1987).
    [CrossRef] [PubMed]
  12. J. Weber, J. Malik, “Robust computation of optical flow in a multiscale differential framework,” Int. J. Comput. Vis. 14, 67–81 (1995).
    [CrossRef]
  13. H. Liu, T. Hong, M. Herman, R. Chellappa, “A general motion model and spatiotemporal filters for computing optical-flow,” Int. J. Comput. Vis. 22, 141–172 (1997).
    [CrossRef]
  14. S. Ju, M. Black, A. Jepson, “Skin and bones: multi-layer, locally affine, optical flow and regularization with transparency,” In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (IEEE Computer Society Press, Los Alamitos, Calif., 1996), pp. 307–314.
  15. N. Namazi, J. Lipp, “Nonuniform image motion estimation in reduced coefficient transformed-domains,” IEEE Trans. Image Process. 2, 236–246 (1993).
    [CrossRef]
  16. C. Fan, N. Namazi, P. Penafiel, “A new image motion estimation algorithm based on the EM technique,” IEEE Trans. Pattern. Anal. Mach. Intell. 18, 348–352 (1996).
    [CrossRef]
  17. R. Szeliski, J. Coughlan, “Spline-based image registration,” Int. J. Comput. Vis. 22, 199–218 (1997).
    [CrossRef]
  18. S. Rakshit, C. Anderson, “Computation of optical-flow using basis functions,” IEEE Trans. Image Process. 6, 1246–1254 (1997).
    [CrossRef]
  19. C. Fennema, W. Thompson, “Velocity determination in scenes containing several moving objects,” Comput. Graph. Image Process. 9, 301–315 (1979).
    [CrossRef]
  20. S. Srinivasan, R. Chellappa, “Robust modeling and estimation of optical flow with overlapped basis functions,” (University of Maryland, College Park, Md., 1996) (software available at ftp.cfar.umd.edu/pub/shridhar/Software).
  21. L. Ng, V. Solo, “Errors-in-variables modeling in optical flow problems,” In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (Institute of Electrical and Electronics Engineers, New York, 1998), pp. 2373–2376.
  22. S. V. Huffel, J. Vandewalle, The Total Least Squares Problem—Computational Aspects and Analysis (Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1991).
  23. O. Axelsson, Iterated Solution Methods (Cambridge U. Press, Cambridge, UK, 1994).
  24. W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery, Numerical Recipes in C, 2nd ed. (Cambridge U. Press, Cambridge, UK, 1992).
  25. W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery, Numerical Recipes in C, (Cambridge U. Press, Cambridge, UK, 1988).
  26. Since the publication Ref. 1 researchers14,17 have used the Yosemite sequence as a benchmark and have shown signifi-cantly improved performance figures. However, their comparisons use a cloud-free rendering of the sequence or explicitly crop out the upper portion. In the former case, the sky area is uniformly black and velocity is zero. Figure of merit (32) is meaningless over a significant portion of the frame. Owing to the unavailability of implementations, and to other issues such as sparsity that disallow a direct comparison, we are unable to present an evaluation of these techniques vis a vis ours.
  27. S. Srinivasan, R. Chellappa, “Image stabilization and mosaicking using the overlapped basis optical flow field,” in Proceedings of the IEEE International Conference on Image Processing (IEEE Computer Society Press, Los Alamitos, Calif., 1997), pp. 356–359.
  28. A. M. Tekalp, Digital Video Processing (Prentice-Hall, Englewood Cliffs, N.J., 1995).
  29. M. Irani, S. Peleg, “Improving resolution by image registration,” Graph. Models Image Process. 53, 231–239 (1991).
    [CrossRef]
  30. P. Moulin, R. Krishnamurthy, J. Woods, “Multiscale modeling and estimation of motion fields for video coding,” IEEE Trans. Image Process. 6, 1606–1620 (1997).
    [CrossRef] [PubMed]

1997 (4)

H. Liu, T. Hong, M. Herman, R. Chellappa, “A general motion model and spatiotemporal filters for computing optical-flow,” Int. J. Comput. Vis. 22, 141–172 (1997).
[CrossRef]

R. Szeliski, J. Coughlan, “Spline-based image registration,” Int. J. Comput. Vis. 22, 199–218 (1997).
[CrossRef]

S. Rakshit, C. Anderson, “Computation of optical-flow using basis functions,” IEEE Trans. Image Process. 6, 1246–1254 (1997).
[CrossRef]

P. Moulin, R. Krishnamurthy, J. Woods, “Multiscale modeling and estimation of motion fields for video coding,” IEEE Trans. Image Process. 6, 1606–1620 (1997).
[CrossRef] [PubMed]

1996 (1)

C. Fan, N. Namazi, P. Penafiel, “A new image motion estimation algorithm based on the EM technique,” IEEE Trans. Pattern. Anal. Mach. Intell. 18, 348–352 (1996).
[CrossRef]

1995 (1)

J. Weber, J. Malik, “Robust computation of optical flow in a multiscale differential framework,” Int. J. Comput. Vis. 14, 67–81 (1995).
[CrossRef]

1994 (1)

J. Barron, D. Fleet, S. Beauchemin, “Performance of optical flow techniques,” Int. J. Comput. Vis. 12, 43–77 (1994) (software and test sequences available at ftp.csd.uwo.ca/pub/vision).
[CrossRef]

1993 (1)

N. Namazi, J. Lipp, “Nonuniform image motion estimation in reduced coefficient transformed-domains,” IEEE Trans. Image Process. 2, 236–246 (1993).
[CrossRef]

1991 (1)

M. Irani, S. Peleg, “Improving resolution by image registration,” Graph. Models Image Process. 53, 231–239 (1991).
[CrossRef]

1990 (1)

D. Fleet, A. Jepson, “Computation of component image velocity from local phase information,” Int. J. Comput. Vis. 5, 77–104 (1990).
[CrossRef]

1989 (1)

S. Uras, F. Girosi, A. Verri, V. Torre, “A computational approach to motion perception,” Biol. Cybern. 60, 79–87 (1989).
[CrossRef]

1987 (2)

H. Nagel, “On the estimation of optical flow: relations between different approaches and some new results,” Artif. Intel. 33, 299–324 (1987).
[CrossRef]

J. Kearney, W. Thompson, D. Boley, “Optical flow estimation: an error analysis of gradient-based methods with local optimization,” IEEE Trans. Pattern. Anal. Mach. Intell. 9, 229–244 (1987).
[CrossRef] [PubMed]

1981 (1)

B. Horn, B. Schunck, “Determining optical flow,” Artif. Intel. 17, 185–203 (1981).
[CrossRef]

1979 (1)

C. Fennema, W. Thompson, “Velocity determination in scenes containing several moving objects,” Comput. Graph. Image Process. 9, 301–315 (1979).
[CrossRef]

Anandan, P.

P. Anandan, “Measuring visual motion from image sequences,” Ph.D. dissertation (University of Massachusetts, Amherst, Mass., 1987).

Anderson, C.

S. Rakshit, C. Anderson, “Computation of optical-flow using basis functions,” IEEE Trans. Image Process. 6, 1246–1254 (1997).
[CrossRef]

Axelsson, O.

O. Axelsson, Iterated Solution Methods (Cambridge U. Press, Cambridge, UK, 1994).

Barron, J.

J. Barron, D. Fleet, S. Beauchemin, “Performance of optical flow techniques,” Int. J. Comput. Vis. 12, 43–77 (1994) (software and test sequences available at ftp.csd.uwo.ca/pub/vision).
[CrossRef]

Beauchemin, S.

J. Barron, D. Fleet, S. Beauchemin, “Performance of optical flow techniques,” Int. J. Comput. Vis. 12, 43–77 (1994) (software and test sequences available at ftp.csd.uwo.ca/pub/vision).
[CrossRef]

Bergholm, F.

A. Waxman, J. Wu, F. Bergholm, “Convected activation profiles and the measurement of visual motion,” in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (IEEE Computer Society Press, Los Alamitos, Calif., 1988), pp. 717–723.

Black, M.

S. Ju, M. Black, A. Jepson, “Skin and bones: multi-layer, locally affine, optical flow and regularization with transparency,” In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (IEEE Computer Society Press, Los Alamitos, Calif., 1996), pp. 307–314.

Boley, D.

J. Kearney, W. Thompson, D. Boley, “Optical flow estimation: an error analysis of gradient-based methods with local optimization,” IEEE Trans. Pattern. Anal. Mach. Intell. 9, 229–244 (1987).
[CrossRef] [PubMed]

Chellappa, R.

H. Liu, T. Hong, M. Herman, R. Chellappa, “A general motion model and spatiotemporal filters for computing optical-flow,” Int. J. Comput. Vis. 22, 141–172 (1997).
[CrossRef]

S. Srinivasan, R. Chellappa, “Robust modeling and estimation of optical flow with overlapped basis functions,” (University of Maryland, College Park, Md., 1996) (software available at ftp.cfar.umd.edu/pub/shridhar/Software).

S. Srinivasan, R. Chellappa, “Image stabilization and mosaicking using the overlapped basis optical flow field,” in Proceedings of the IEEE International Conference on Image Processing (IEEE Computer Society Press, Los Alamitos, Calif., 1997), pp. 356–359.

Coughlan, J.

R. Szeliski, J. Coughlan, “Spline-based image registration,” Int. J. Comput. Vis. 22, 199–218 (1997).
[CrossRef]

Fan, C.

C. Fan, N. Namazi, P. Penafiel, “A new image motion estimation algorithm based on the EM technique,” IEEE Trans. Pattern. Anal. Mach. Intell. 18, 348–352 (1996).
[CrossRef]

Fennema, C.

C. Fennema, W. Thompson, “Velocity determination in scenes containing several moving objects,” Comput. Graph. Image Process. 9, 301–315 (1979).
[CrossRef]

Flannery, B. P.

W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery, Numerical Recipes in C, 2nd ed. (Cambridge U. Press, Cambridge, UK, 1992).

W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery, Numerical Recipes in C, (Cambridge U. Press, Cambridge, UK, 1988).

Fleet, D.

J. Barron, D. Fleet, S. Beauchemin, “Performance of optical flow techniques,” Int. J. Comput. Vis. 12, 43–77 (1994) (software and test sequences available at ftp.csd.uwo.ca/pub/vision).
[CrossRef]

D. Fleet, A. Jepson, “Computation of component image velocity from local phase information,” Int. J. Comput. Vis. 5, 77–104 (1990).
[CrossRef]

Girosi, F.

S. Uras, F. Girosi, A. Verri, V. Torre, “A computational approach to motion perception,” Biol. Cybern. 60, 79–87 (1989).
[CrossRef]

Herman, M.

H. Liu, T. Hong, M. Herman, R. Chellappa, “A general motion model and spatiotemporal filters for computing optical-flow,” Int. J. Comput. Vis. 22, 141–172 (1997).
[CrossRef]

Hong, T.

H. Liu, T. Hong, M. Herman, R. Chellappa, “A general motion model and spatiotemporal filters for computing optical-flow,” Int. J. Comput. Vis. 22, 141–172 (1997).
[CrossRef]

Horn, B.

B. Horn, B. Schunck, “Determining optical flow,” Artif. Intel. 17, 185–203 (1981).
[CrossRef]

Huffel, S. V.

S. V. Huffel, J. Vandewalle, The Total Least Squares Problem—Computational Aspects and Analysis (Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1991).

Irani, M.

M. Irani, S. Peleg, “Improving resolution by image registration,” Graph. Models Image Process. 53, 231–239 (1991).
[CrossRef]

Jepson, A.

D. Fleet, A. Jepson, “Computation of component image velocity from local phase information,” Int. J. Comput. Vis. 5, 77–104 (1990).
[CrossRef]

S. Ju, M. Black, A. Jepson, “Skin and bones: multi-layer, locally affine, optical flow and regularization with transparency,” In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (IEEE Computer Society Press, Los Alamitos, Calif., 1996), pp. 307–314.

Ju, S.

S. Ju, M. Black, A. Jepson, “Skin and bones: multi-layer, locally affine, optical flow and regularization with transparency,” In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (IEEE Computer Society Press, Los Alamitos, Calif., 1996), pp. 307–314.

Kanade, T.

B. Lucas, T. Kanade, “An iterative image registration technique with an application to stereo vision,” in Proceedings of the International Joint Conference on Artificial Intelligence (IEEE Computer Society Press, Los Alamitos, Calif., 1981), pp. 674–679.

Kearney, J.

J. Kearney, W. Thompson, D. Boley, “Optical flow estimation: an error analysis of gradient-based methods with local optimization,” IEEE Trans. Pattern. Anal. Mach. Intell. 9, 229–244 (1987).
[CrossRef] [PubMed]

Krishnamurthy, R.

P. Moulin, R. Krishnamurthy, J. Woods, “Multiscale modeling and estimation of motion fields for video coding,” IEEE Trans. Image Process. 6, 1606–1620 (1997).
[CrossRef] [PubMed]

Lipp, J.

N. Namazi, J. Lipp, “Nonuniform image motion estimation in reduced coefficient transformed-domains,” IEEE Trans. Image Process. 2, 236–246 (1993).
[CrossRef]

Liu, H.

H. Liu, T. Hong, M. Herman, R. Chellappa, “A general motion model and spatiotemporal filters for computing optical-flow,” Int. J. Comput. Vis. 22, 141–172 (1997).
[CrossRef]

Lucas, B.

B. Lucas, T. Kanade, “An iterative image registration technique with an application to stereo vision,” in Proceedings of the International Joint Conference on Artificial Intelligence (IEEE Computer Society Press, Los Alamitos, Calif., 1981), pp. 674–679.

Malik, J.

J. Weber, J. Malik, “Robust computation of optical flow in a multiscale differential framework,” Int. J. Comput. Vis. 14, 67–81 (1995).
[CrossRef]

Moulin, P.

P. Moulin, R. Krishnamurthy, J. Woods, “Multiscale modeling and estimation of motion fields for video coding,” IEEE Trans. Image Process. 6, 1606–1620 (1997).
[CrossRef] [PubMed]

Nagel, H.

H. Nagel, “On the estimation of optical flow: relations between different approaches and some new results,” Artif. Intel. 33, 299–324 (1987).
[CrossRef]

Namazi, N.

C. Fan, N. Namazi, P. Penafiel, “A new image motion estimation algorithm based on the EM technique,” IEEE Trans. Pattern. Anal. Mach. Intell. 18, 348–352 (1996).
[CrossRef]

N. Namazi, J. Lipp, “Nonuniform image motion estimation in reduced coefficient transformed-domains,” IEEE Trans. Image Process. 2, 236–246 (1993).
[CrossRef]

Ng, L.

L. Ng, V. Solo, “Errors-in-variables modeling in optical flow problems,” In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (Institute of Electrical and Electronics Engineers, New York, 1998), pp. 2373–2376.

Peleg, S.

M. Irani, S. Peleg, “Improving resolution by image registration,” Graph. Models Image Process. 53, 231–239 (1991).
[CrossRef]

Penafiel, P.

C. Fan, N. Namazi, P. Penafiel, “A new image motion estimation algorithm based on the EM technique,” IEEE Trans. Pattern. Anal. Mach. Intell. 18, 348–352 (1996).
[CrossRef]

Press, W. H.

W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery, Numerical Recipes in C, 2nd ed. (Cambridge U. Press, Cambridge, UK, 1992).

W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery, Numerical Recipes in C, (Cambridge U. Press, Cambridge, UK, 1988).

Rakshit, S.

S. Rakshit, C. Anderson, “Computation of optical-flow using basis functions,” IEEE Trans. Image Process. 6, 1246–1254 (1997).
[CrossRef]

Schunck, B.

B. Horn, B. Schunck, “Determining optical flow,” Artif. Intel. 17, 185–203 (1981).
[CrossRef]

Simoncelli, E. P.

E. P. Simoncelli, “Distributed representation and analysis of visual motion,” Ph.D. dissertation (Massachusetts Institute of Technology, Cambridge, Mass., 1993).

Singh, A.

A. Singh, “An Estimation-Theoretic Framework for Image-Flow Computation,” in Proceedings of the Third International Conference on Computer Vision (IEEE Computer Society Press, Los Alamitos, Calif., 1990), pp. 168–177.

Solo, V.

L. Ng, V. Solo, “Errors-in-variables modeling in optical flow problems,” In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (Institute of Electrical and Electronics Engineers, New York, 1998), pp. 2373–2376.

Srinivasan, S.

S. Srinivasan, R. Chellappa, “Image stabilization and mosaicking using the overlapped basis optical flow field,” in Proceedings of the IEEE International Conference on Image Processing (IEEE Computer Society Press, Los Alamitos, Calif., 1997), pp. 356–359.

S. Srinivasan, R. Chellappa, “Robust modeling and estimation of optical flow with overlapped basis functions,” (University of Maryland, College Park, Md., 1996) (software available at ftp.cfar.umd.edu/pub/shridhar/Software).

Szeliski, R.

R. Szeliski, J. Coughlan, “Spline-based image registration,” Int. J. Comput. Vis. 22, 199–218 (1997).
[CrossRef]

Tekalp, A. M.

A. M. Tekalp, Digital Video Processing (Prentice-Hall, Englewood Cliffs, N.J., 1995).

Teukolsky, S. A.

W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery, Numerical Recipes in C, 2nd ed. (Cambridge U. Press, Cambridge, UK, 1992).

W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery, Numerical Recipes in C, (Cambridge U. Press, Cambridge, UK, 1988).

Thompson, W.

J. Kearney, W. Thompson, D. Boley, “Optical flow estimation: an error analysis of gradient-based methods with local optimization,” IEEE Trans. Pattern. Anal. Mach. Intell. 9, 229–244 (1987).
[CrossRef] [PubMed]

C. Fennema, W. Thompson, “Velocity determination in scenes containing several moving objects,” Comput. Graph. Image Process. 9, 301–315 (1979).
[CrossRef]

Torre, V.

S. Uras, F. Girosi, A. Verri, V. Torre, “A computational approach to motion perception,” Biol. Cybern. 60, 79–87 (1989).
[CrossRef]

Uras, S.

S. Uras, F. Girosi, A. Verri, V. Torre, “A computational approach to motion perception,” Biol. Cybern. 60, 79–87 (1989).
[CrossRef]

Vandewalle, J.

S. V. Huffel, J. Vandewalle, The Total Least Squares Problem—Computational Aspects and Analysis (Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1991).

Verri, A.

S. Uras, F. Girosi, A. Verri, V. Torre, “A computational approach to motion perception,” Biol. Cybern. 60, 79–87 (1989).
[CrossRef]

Vetterling, W. T.

W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery, Numerical Recipes in C, (Cambridge U. Press, Cambridge, UK, 1988).

W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery, Numerical Recipes in C, 2nd ed. (Cambridge U. Press, Cambridge, UK, 1992).

Waxman, A.

A. Waxman, J. Wu, F. Bergholm, “Convected activation profiles and the measurement of visual motion,” in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (IEEE Computer Society Press, Los Alamitos, Calif., 1988), pp. 717–723.

Weber, J.

J. Weber, J. Malik, “Robust computation of optical flow in a multiscale differential framework,” Int. J. Comput. Vis. 14, 67–81 (1995).
[CrossRef]

Woods, J.

P. Moulin, R. Krishnamurthy, J. Woods, “Multiscale modeling and estimation of motion fields for video coding,” IEEE Trans. Image Process. 6, 1606–1620 (1997).
[CrossRef] [PubMed]

Wu, J.

A. Waxman, J. Wu, F. Bergholm, “Convected activation profiles and the measurement of visual motion,” in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (IEEE Computer Society Press, Los Alamitos, Calif., 1988), pp. 717–723.

Artif. Intel. (2)

B. Horn, B. Schunck, “Determining optical flow,” Artif. Intel. 17, 185–203 (1981).
[CrossRef]

H. Nagel, “On the estimation of optical flow: relations between different approaches and some new results,” Artif. Intel. 33, 299–324 (1987).
[CrossRef]

Biol. Cybern. (1)

S. Uras, F. Girosi, A. Verri, V. Torre, “A computational approach to motion perception,” Biol. Cybern. 60, 79–87 (1989).
[CrossRef]

Comput. Graph. Image Process. (1)

C. Fennema, W. Thompson, “Velocity determination in scenes containing several moving objects,” Comput. Graph. Image Process. 9, 301–315 (1979).
[CrossRef]

Graph. Models Image Process. (1)

M. Irani, S. Peleg, “Improving resolution by image registration,” Graph. Models Image Process. 53, 231–239 (1991).
[CrossRef]

IEEE Trans. Image Process. (3)

P. Moulin, R. Krishnamurthy, J. Woods, “Multiscale modeling and estimation of motion fields for video coding,” IEEE Trans. Image Process. 6, 1606–1620 (1997).
[CrossRef] [PubMed]

S. Rakshit, C. Anderson, “Computation of optical-flow using basis functions,” IEEE Trans. Image Process. 6, 1246–1254 (1997).
[CrossRef]

N. Namazi, J. Lipp, “Nonuniform image motion estimation in reduced coefficient transformed-domains,” IEEE Trans. Image Process. 2, 236–246 (1993).
[CrossRef]

IEEE Trans. Pattern. Anal. Mach. Intell. (2)

C. Fan, N. Namazi, P. Penafiel, “A new image motion estimation algorithm based on the EM technique,” IEEE Trans. Pattern. Anal. Mach. Intell. 18, 348–352 (1996).
[CrossRef]

J. Kearney, W. Thompson, D. Boley, “Optical flow estimation: an error analysis of gradient-based methods with local optimization,” IEEE Trans. Pattern. Anal. Mach. Intell. 9, 229–244 (1987).
[CrossRef] [PubMed]

Int. J. Comput. Vis. (5)

J. Weber, J. Malik, “Robust computation of optical flow in a multiscale differential framework,” Int. J. Comput. Vis. 14, 67–81 (1995).
[CrossRef]

H. Liu, T. Hong, M. Herman, R. Chellappa, “A general motion model and spatiotemporal filters for computing optical-flow,” Int. J. Comput. Vis. 22, 141–172 (1997).
[CrossRef]

R. Szeliski, J. Coughlan, “Spline-based image registration,” Int. J. Comput. Vis. 22, 199–218 (1997).
[CrossRef]

J. Barron, D. Fleet, S. Beauchemin, “Performance of optical flow techniques,” Int. J. Comput. Vis. 12, 43–77 (1994) (software and test sequences available at ftp.csd.uwo.ca/pub/vision).
[CrossRef]

D. Fleet, A. Jepson, “Computation of component image velocity from local phase information,” Int. J. Comput. Vis. 5, 77–104 (1990).
[CrossRef]

Other (15)

S. Ju, M. Black, A. Jepson, “Skin and bones: multi-layer, locally affine, optical flow and regularization with transparency,” In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (IEEE Computer Society Press, Los Alamitos, Calif., 1996), pp. 307–314.

B. Lucas, T. Kanade, “An iterative image registration technique with an application to stereo vision,” in Proceedings of the International Joint Conference on Artificial Intelligence (IEEE Computer Society Press, Los Alamitos, Calif., 1981), pp. 674–679.

P. Anandan, “Measuring visual motion from image sequences,” Ph.D. dissertation (University of Massachusetts, Amherst, Mass., 1987).

A. Singh, “An Estimation-Theoretic Framework for Image-Flow Computation,” in Proceedings of the Third International Conference on Computer Vision (IEEE Computer Society Press, Los Alamitos, Calif., 1990), pp. 168–177.

E. P. Simoncelli, “Distributed representation and analysis of visual motion,” Ph.D. dissertation (Massachusetts Institute of Technology, Cambridge, Mass., 1993).

A. Waxman, J. Wu, F. Bergholm, “Convected activation profiles and the measurement of visual motion,” in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (IEEE Computer Society Press, Los Alamitos, Calif., 1988), pp. 717–723.

S. Srinivasan, R. Chellappa, “Robust modeling and estimation of optical flow with overlapped basis functions,” (University of Maryland, College Park, Md., 1996) (software available at ftp.cfar.umd.edu/pub/shridhar/Software).

L. Ng, V. Solo, “Errors-in-variables modeling in optical flow problems,” In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (Institute of Electrical and Electronics Engineers, New York, 1998), pp. 2373–2376.

S. V. Huffel, J. Vandewalle, The Total Least Squares Problem—Computational Aspects and Analysis (Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1991).

O. Axelsson, Iterated Solution Methods (Cambridge U. Press, Cambridge, UK, 1994).

W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery, Numerical Recipes in C, 2nd ed. (Cambridge U. Press, Cambridge, UK, 1992).

W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery, Numerical Recipes in C, (Cambridge U. Press, Cambridge, UK, 1988).

Since the publication Ref. 1 researchers14,17 have used the Yosemite sequence as a benchmark and have shown signifi-cantly improved performance figures. However, their comparisons use a cloud-free rendering of the sequence or explicitly crop out the upper portion. In the former case, the sky area is uniformly black and velocity is zero. Figure of merit (32) is meaningless over a significant portion of the frame. Owing to the unavailability of implementations, and to other issues such as sparsity that disallow a direct comparison, we are unable to present an evaluation of these techniques vis a vis ours.

S. Srinivasan, R. Chellappa, “Image stabilization and mosaicking using the overlapped basis optical flow field,” in Proceedings of the IEEE International Conference on Image Processing (IEEE Computer Society Press, Los Alamitos, Calif., 1997), pp. 356–359.

A. M. Tekalp, Digital Video Processing (Prentice-Hall, Englewood Cliffs, N.J., 1995).

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (12)

Fig. 1
Fig. 1

Sinusoid sequence: (a) first frame at 30-dB SNR; (b) second frame at 20 dB; (c) third frame at 10 dB; (d) true flow field, computed flow field at 10-dB SNR with (e) proposed algorithm and (f) Singh’s7 algorithm.

Fig. 2
Fig. 2

Square sequence: (a) first frame at 30-dB SNR; (b) second frame at 20 dB; (c) third frame at 10 dB; (d) true flow field, computed flow field on noiseless sequence with (e) proposed algorithm and (f) Anandan’s6 algorithm.

Fig. 3
Fig. 3

Translating tree sequence: (a) first frame at 30-dB SNR; (b) second frame at 20 dB; (c) third frame at 10 dB; (d) true flow field, computed flow field at 30-dB SNR with (e) proposed algorithm and (f) algorithm of Uras et al.4

Fig. 4
Fig. 4

Diverging tree sequence: (a) first frame at 30-dB SNR; (b) second frame at 20 dB; (c) third frame at 10 dB; (d) true flow field, computed flow field at 10-dB SNR with (e) proposed algorithm and (f) algorithm of Uras et al.4

Fig. 5
Fig. 5

Yosemite sequence: (a) first frame at 30-dB SNR; (b) second frame at 20 dB; (c) third frame at 10 dB; (d) true flow field, computed flow field at 20-dB SNR with (e) proposed algorithm and (f) algorithm of Uras et al.4

Fig. 6
Fig. 6

SRI trees sequence: (a) first frame at 10-dB SNR, computed flow with proposed algorithm, (b) on noiseless data, and (c) at 10 dB.

Fig. 7
Fig. 7

Coke sequence: (a) first frame at 20-dB SNR, computed flow with proposed algorithm, (b) on noiseless data, and (c) at 20 dB.

Fig. 8
Fig. 8

Rubik’s sequence: (a) first frame at 10-dB SNR, computed flow with proposed algorithm, at (b) 20 dB, and (c) 10 dB.

Fig. 9
Fig. 9

Taxi sequence: (a) first frame at 20-dB SNR, computed flow with proposed algorithm, (b) on noiseless data, and (c) at 20 dB.

Fig. 10
Fig. 10

CPU time requirement of the proposed algorithm on a DEC Alpha 266-MHz workstation.

Fig. 11
Fig. 11

Predator F sequence: (a) first frame, (b) 180th frame, and (c) mosaic with frames 1–180.

Fig. 12
Fig. 12

Super resolution on the Predator B data set: (a) first frame of the MPEG sequence, (b) zoomed area around the car in (a), (c) 4× superresolved image of car, (d) zoomed area around the truck in (a), (e) zoomed area around truck with bilinear interpolator, and (f) 4× superresolved image of truck.

Tables (5)

Tables Icon

Table 1 Performance Results with the Sinusoid Sequence

Tables Icon

Table 2 Performance Results with the Square Sequence

Tables Icon

Table 3 Performance Results with the Translating Tree Sequence

Tables Icon

Table 4 Performance Results with the Diverging Tree Sequence

Tables Icon

Table 5 Performance Results with the Yosemite Sequence

Equations (46)

Equations on this page are rendered with MathJax. Learn more.

ψ(x, y, t)=ψ(x+ut, y+vt, 0).
ψt+u ψx+v ψy=0,x, y, t,
minu,vψt+u ψx+v ψy2+λ2ux2+uy2+vx2+vy2.
minu,vx, yΩw2(x, y)ψt+u ψx+v ψy2.
2ψxt+u 2ψx2+v 2ψxy=02ψyt+u 2ψxy+v 2ψy2=0.
ψit+u ψix+v ψiy=0
u=k=0K-1ukϕk,v=k=0K-1vkϕk.
ψt+kukϕk ψx+kvkϕk ψy=0,x, y, t.
 ψtθdxdy+kukϕk ψxθdxdy+kvkϕk ψyθdxdy=0.
ψˆt+kukϕk ψˆx+kvkϕk ψˆy0,x, y, t.
ϕl ψˆxψˆtdxdy+kukϕkϕlψˆx2dxdy+kvk×ϕkϕl ψˆxψˆydxdy=0,l=0, 1,K-1, ϕl ψˆyψˆtdxdy+kukϕkϕl ψˆxψˆydxdy+kvk×ϕkϕlψˆy2dxdy=0,l=0, 1,K-1.
Ax=b,ARM×N,M>N,
Aˆxbˆ,
eLS(A'A)1A'(δΔx0)(A'A)1RΔx0bias.
xCLS=(AˆAˆ-RΔ)-1Aˆbˆ,
xTLS=-1vn+1, n+1vn+1(n),
μrδ+2bδ-(δA+bΔ)x0-bAeTLS, μx0(AΔ+ΔA+RΔ)x0+AAeTLS-Δb-Aδ.
(rδI-RΔ)x00.
ϕ0 ψˆx ϕK-1 ψˆxϕ0 ψˆy ϕK-1 ψˆy(xi, yi, ti).
[RΔ]0,1=Eϕ0ϕ1ψˆx2,
xELS=Gˆ-1Aˆbˆ.
eELS=Gˆ-1Aˆδ,(AA)-1Aδ,
ϕl ψˆtψˆxdxdy+kukϕkϕl ψˆxψxdxdy+kvkϕkϕl ψˆxψydxdy=0,
l=0, 1,,K-1,
ϕl ψˆtψˆydxdy+kukϕkϕl ψxψˆydxdy+kvkϕkϕl ψyψˆydxdy=0,
l=0, 1,,K-1.
I(y)=ϕkϕl ψˆxψxdx.
I(y)=[ϕkϕlψˆx]=0ψϕkϕl(ψˆ/x)xdx,=ψϕkϕlxψˆxdxψϕlϕkxψˆxdxψϕkϕlψˆxxdx.
kuk ϕkϕl(ψˆ/x)xψ+kvk ϕkϕl(ψˆ/x)yψ=ϕl ψˆtψˆx, kuk ϕkϕl(ψˆ/y)xψ+kvk ϕkϕl(ψˆ/y)yψ=ϕl ψˆtψˆy,
ϕ0(x)+λϕ0(x-w)=λ+(λ-1)(x/w)x[0, w],
ϕ0(x)=[1-(|x|/w)]+.
ϕ0(x)=121+cosπxw,x[-w, w].
w=minw0, rK, cK,
Gˆ=D1U100L2D2U200L3D3U3,
Di, Ui, Li××00×××00×××,
=arccosv0·vv0v.
τk=r¯kG˜-1rkd¯kGˆdk,
xk+1=xk+τkdk,
rk+1=rk+τkGˆdk,
r¯k+1=r¯k+τkGˆdk,
βk=r¯k+1G˜-1rk+1r¯kG˜-1rk,
dk+1=-G˜-1rk+1+βkdk,
d¯k+1=-G˜-1r¯k+1+βkd¯k,
x0=G˜-1Aˆbˆ,
r0=r¯0=Gˆx0-Aˆbˆ,
d0=d¯0=G˜-1r0.

Metrics