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

ABSTRACT

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.

REFERENCES

• 1: Aseem Agarwala , Mira Dontcheva , Maneesh Agrawala , Steven Drucker , Alex Colburn , Brian Curless , David Salesin , Michael Cohen, Interactive digital photomontage, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 2: Luis Alvarez , Rachid Deriche , Théo Papadopoulo , Javier Sánchez, Symmetrical Dense Optical Flow Estimation with Occlusions Detection, International Journal of Computer Vision, v.75 n.3, p.371-385, December 2007 [doi>10.1007/s11263-007-0041-4]
• 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.
• 4: J. L. Barron , D. J. Fleet , S. S. Beauchemin, Performance of optical flow techniques, International Journal of Computer Vision, v.12 n.1, p.43-77, Feb. 1994 [doi>10.1007/BF01420984]
• 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.
• 6: Michael J. Black , P. Anandan, The robust estimation of multiple motions: parametric and piecewise-smooth flow fields, Computer Vision and Image Understanding, v.63 n.1, p.75-104, Jan. 1996 [doi>10.1006/cviu.1996.0006]
• 7: Yuri Boykov , Olga Veksler , Ramin Zabih, Fast Approximate Energy Minimization via Graph Cuts, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.11, p.1222-1239, November 2001 [doi>10.1109/34.969114]
• 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.
• 9: Shenchang Eric Chen , Lance Williams, View interpolation for image synthesis, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.279-288, August 02-06, 1993, Anaheim, CA [doi>10.1145/166117.166153]
• 10: Andrew Fitzgibbon , Yonatan Wexler , Andrew Zisserman, Image-based rendering using image-based priors, Proceedings of the Ninth IEEE International Conference on Computer Vision, p.1176, October 13-16, 2003
• 11: Davi Geiger , Bruce Ladendorf , Alan L. Yuille, Occlusions and Binocular Stereo, Proceedings of the Second European Conference on Computer Vision, p.425-433, May 19-22, 1992
• 12: Rafael C. Gonzalez , Richard E. Woods, Digital Image Processing (3rd Edition), Prentice-Hall, Inc., Upper Saddle River, NJ, 2006
• 13: Jiaya Jia , Chi-Keung Tang, Image Stitching Using Structure Deformation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.30 n.4, p.617-631, April 2008 [doi>10.1109/TPAMI.2007.70729]
• 14: Jiaya Jia , Jian Sun , Chi-Keung Tang , Heung-Yeung Shum, Drag-and-drop pasting, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 15: Kolmogorov, V., and Zabih, R. 2001. Computing visual correspondence with occlusions using graph cuts. Proc. IEEE Int. Conf. Computer Vision, 508--515.
• 16: Vivek Kwatra , Arno Schödl , Irfan Essa , Greg Turk , Aaron Bobick, Graphcut textures: image and video synthesis using graph cuts, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 17: Leonard McMillan , Gary Bishop, Plenoptic modeling: an image-based rendering system, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.39-46, September 1995 [doi>10.1145/218380.218398]
• 18: Etienne Mémin , Patrick Pérez, Hierarchical Estimation and Segmentation of Dense Motion Fields, International Journal of Computer Vision, v.46 n.2, p.129-155, February 2002 [doi>10.1023/A:1013539930159]
• 19: Patrick Pérez , Michel Gangnet , Andrew Blake, Poisson image editing, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 20: Daniel Scharstein , Richard Szeliski, A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms, International Journal of Computer Vision, v.47 n.1-3, p.7-42, April-June 2002 [doi>10.1023/A:1014573219977]
• 21: Arno Schödl , Richard Szeliski , David H. Salesin , Irfan Essa, Video textures, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.489-498, July 2000 [doi>10.1145/344779.345012]
• 22: Steven M. Seitz , Charles R. Dyer, View morphing, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.21-30, August 1996 [doi>10.1145/237170.237196]
• 23: Jian Sun , Yin Li , Sing Bing Kang , Heung-Yeung Shum, Symmetric Stereo Matching for Occlusion Handling, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 2, p.399-406, June 20-26, 2005 [doi>10.1109/CVPR.2005.337]
• 24: Hongcheng Wang , Ramesh Raskar , Narendra Ahuja, Seamless Video Editing, Proceedings of the Pattern Recognition, 17th International Conference on (ICPR'04) Volume 3, p.858-861, August 23-26, 2004 [doi>10.1109/ICPR.2004.806]
• 25: Hongcheng Wang , Ning Xu , Ramesh Raskar , Narendra Ahuja, Videoshop: A New Framework for Spatio-Temporal Video Editing in Gradient Domain, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 2, p.1201, June 20-26, 2005 [doi>10.1109/CVPR.2005.369]
• 26: George Wolberg, Digital Image Warping, IEEE Computer Society Press, Los Alamitos, CA, 1994
• 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.
• 28: C. Lawrence Zitnick , Nebojsa Jojic , Sing Bing Kang, Consistent Segmentation for Optical Flow Estimation, Proceedings of the Tenth IEEE International Conference on Computer Vision, p.1308-1315, October 17-20, 2005 [doi>10.1109/ICCV.2005.61]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.m Miscellaneous

Additional Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.m Miscellaneous

Keywords:
3D Poisson reconstruction, interpolation, occlusion handling, path framework, transition point