“Moving gradients: a path-based method for plausible image interpolation” by Mahajan, Huang, Matusik, Ramamoorthi and Belhumeur

  • ©Dhruv Mahajan, Fu-Chung Huang, Wojciech Matusik, Ravi Ramamoorthi, and Peter Belhumeur




    Moving gradients: a path-based method for plausible image interpolation



    We describe a method for plausible interpolation of images, with a wide range of applications like temporal up-sampling for smooth playback of lower frame rate video, smooth view interpolation, and animation of still images. The method is based on the intuitive idea, that a given pixel in the interpolated frames traces out a path in the source images. Therefore, we simply move and copy pixel gradients from the input images along this path. A key innovation is to allow arbitrary (asymmetric) transition points, where the path moves from one image to the other. This flexible transition preserves the frequency content of the originals without ghosting or blurring, and maintains temporal coherence. Perhaps most importantly, our framework makes occlusion handling particularly simple. The transition points allow for matches away from the occluded regions, at any suitable point along the path. Indeed, occlusions do not need to be handled explicitly at all in our initial graph-cut optimization. Moreover, a simple comparison of computed path lengths after the optimization, allows us to robustly identify occluded regions, and compute the most plausible interpolation in those areas. Finally, we show that significant improvements are obtained by moving gradients and using Poisson reconstruction.


    1. Agarwala, A., Dontcheva, M., Agrawala, M., Drucker, S., Colburn, A., Curless, B., Salesin, D., and Cohen, M. 2004. Interactive digital photomontage. ACM Trans. on Graphics (SIGGRAPH 2004) 23, 3 (aug), 294–302. Google ScholarDigital Library
    2. Alvarez, L., Deriche, R., Papadopoulo, T., and Sanchez, J. 2007. Symmetrical dense optical flow estimation with occlusions detection. Int. Journal of Computer Vision 75, 3 (December), 371–385. Google ScholarDigital Library
    3. Baker, S., Scharstein, D., Lewis, J. P., Roth, S., Black, M. J., and Szeliski, R. 2007. A database and evaluation methodology for optical flow. In Proc. IEEE Int. Conf. Computer Vision, 1–8.Google Scholar
    4. Barron, J., Fleet, D., and Beauchemin, S. 1994. Performance of optical flow techniques. Int. Journal of Computer Vision 12, 1, 43–77. Google ScholarDigital Library
    5. Belhumeur, P., and Mumford, D. 1992. A bayesian treatment of the stereo correspondence problem using half-occluded regions. Proc. IEEE Conf. Computer Vision and Pattern Recognition, 506–512.Google Scholar
    6. Black, M., and Anandan, P. 1996. The robust estimation of multiple motions: Parametric and piecewise-smooth flow-fields. Computer Vision and Image Understanding 63, 1 (January), 75–104. Google ScholarDigital Library
    7. Boykov, Y., Veksler, O., and Zabih, R. 2001. Fast approximate energy minimization via graph cuts. IEEE Trans. Pattern Analysis and Machine Intelligence 23, 11, 1222–1239. Google ScholarDigital Library
    8. Brox, T., Bruhn, A., Papenberg, N., and Weickert, J. 2004. High accuracy optical flow estimation based on a theory for warping. In Proc. European Conf. Computer Vision, vol. 3024, 25–36.Google Scholar
    9. Chen, S., and Williams, L. 1993. View interpolation for image synthesis. In Proc. SIGGRAPH 93, 279–288. Google ScholarDigital Library
    10. Fitzgibbon, A. W., Wexler, Y., and Zisserman, A. 2003. Image-based rendering using image-based priors. In Proc. IEEE Int. Conf. Computer Vision, 1176–1183. Google ScholarDigital Library
    11. Geiger, D., Ladendorf, B., and Yuille, A. 1992. Occlusions and binocular stereo. In Proc. European Conf. Computer Vision, 425–433. Google ScholarDigital Library
    12. Gonzalez, and Woods. 2002. Digital Image Processing. Prentice Hall Inc. Google ScholarDigital Library
    13. Jia, J., and Tang, C. 2008. Image stitching using structure deformation. IEEE Trans. Pattern Analysis and Machine Intelligence 30, 4, 617–631. Google ScholarDigital Library
    14. Jia, J., Sun, J., Tang, C., and Shum, H. 2006. Drag-and-drop pasting. ACM Trans. on Graphics (SIGGRAPH 2006) 25, 3 (jul), 631–637. Google ScholarDigital Library
    15. Kolmogorov, V., and Zabih, R. 2001. Computing visual correspondence with occlusions using graph cuts. Proc. IEEE Int. Conf. Computer Vision, 508–515.Google Scholar
    16. Kwatra, V., Schödl, A., Essa, I., Turk, G., and Bobick, A. 2003. Graphcut textures: Image and video synthesis using graph cuts. ACM Trans. on Graphics (SIGGRAPH 2003) 22, 3 (July), 277–286. Google ScholarDigital Library
    17. McMillan, L., and Bishop, G. 1995. Plenoptic modeling: An image-based rendering system. In In Proc. SIGGRAPH 95, 39–46. Google ScholarDigital Library
    18. Mémin, E., and Pérez, P. 2002. Hierarchical estimation and segmentation of dense motion fields. Int. Journal of Computer Vision 46, 2, 129–155. Google ScholarDigital Library
    19. Pérez, P., Gangnet, M., and Blake, A. 2003. Poisson image editing. ACM Trans. on Graphics (SIGGRAPH 2003) 22, 3 (jul), 313–318. Google ScholarDigital Library
    20. Scharstein, D., and Szeliski, R. 2002. A taxonomy and evaluation of dense two-frame stereo correspondence algorithm. Int. Journal of Computer Vision 47, 1, 7–42. Google ScholarDigital Library
    21. Schödl, A., Szeliski, R., Salesin, D., and Essa, I. 2000. Video textures. ACM Trans. on Graphics (SIGGRAPH 2000), 489–498. Google ScholarDigital Library
    22. Seitz, S., and Dyer, C. 1996. View morphing. In In Proc. SIGGRAPH 96, 21–30. Google ScholarDigital Library
    23. Sun, J., Li, Y., Kang, S., and Shum, H. 2005. Symmetric stereo matching for occlusion handling. Proc. IEEE Conf. Computer Vision and Pattern Recognition 2, 399–406. Google ScholarDigital Library
    24. Wang, H., Raskar, R., and Ahuja, N. 2004. Seamless video editing. In Int. Conf. on Pattern Recognition, vol. 3, 858–861. Google ScholarDigital Library
    25. Wang, H., Xu, N., Raskar, R., and Ahuja, N. 2005. Videoshop: A new framework for spatio-temporal video editing in gradient domain. Proc. IEEE Conf. Computer Vision and Pattern Recognition 2, 1201. Google ScholarDigital Library
    26. Wolberg, G. 1990. Digital Image Warping. IEEE Press. Google ScholarDigital Library
    27. Xiao, J., Cheng, H., Sawhney, H., Rao, C., and Isnardi, M. 2006. Bilateral filtering-based optical flow estimation with occlusion detection. In Proc. European Conf. Computer Vision, vol. 1, 211–224. Google ScholarDigital Library
    28. Zitnick, C. L., Jojic, N., and Kang, S. B. 2005. Consistent segmentation for optical flow estimation. In Proc. IEEE Int. Conf. Computer Vision, 1308–1315. Google ScholarDigital Library

ACM Digital Library Publication: