Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We present an interactive system for efficiently extracting foreground objects from a video. We extend previous min-cut based image segmentation techniques to the domain of video with four new contributions. We provide a novel painting-based user interface that allows users to easily indicate the foreground object across space and time. We introduce a hierarchical mean-shift preprocess in order to minimize the number of nodes that min-cut must operate on. Within the min-cut we also define new local cost functions to augment the global costs defined in earlier work. Finally, we extend 2D alpha matting methods designed for images to work with 3D video volumes. We demonstrate that our matting approach preserves smoothness across both space and time. Our interactive video cutout system allows users to quickly extract foreground objects from video sequences for use in a variety of applications including compositing onto new backgrounds and NPR cartoon style rendering.

REFERENCES

• 1: Agarwala, A., Dontcheva, M., Agrawala, M., Drucker, S., Colburn, A., Curless, B., Salesin, D., and Cohen, M. 2004. Interactive digital photomontage. In Proceedings of ACM SIGGRAPH. 294--302.
• 2: Agarwala, A., Hertzmann, A., Salesin, D. H., and Seitz, S. M. 2004. Keyframe-based tracking for rotoscoping and animation. In Proceedings of ACM SIGGRAPH, 584--591.
• 3: S. Belongie , J. Malik , J. Puzicha, Shape Matching and Object Recognition Using Shape Contexts, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.4, p.509-522, April 2002 [doi>10.1109/34.993558]
• 4: Eric P. Bennett , Leonard McMillan, Proscenium: a framework for spatio-temporal video editing, Proceedings of the eleventh ACM international conference on Multimedia, November 02-08, 2003, Berkeley, CA, USA [doi>10.1145/957013.957049]
• 5: Blake, A., and Isard, M. 1998. Active Contours. Springer-Verlag.
• 6: 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]
• 7: Chuang, Y.-Y., Curless, B., Salesin, D. H., and Szeliski, R. 2001. A bayesian approach to digital matting. In Proceedings of IEEE CVPR 2001, vol. 2, 264--271.
• 8: Yung-Yu Chuang , Aseem Agarwala , Brian Curless , David H. Salesin , Richard Szeliski, Video matting of complex scenes, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 9: Collomosse, J. P., Rowntree, D., and Hall, P. M. 2003. Stroke surfaces: A spatio-temporal framework for temporally coherent non-photorealistic animations. University of Bath, Technical Report CSBU 2003--01 (June 2003).
• 10: Comaniciu, D., Ramesh, V., and Meer, P. 2001. The variable bandwidth mean shift and data-driven scale selection. In Proc. IEEE 8th Int. Conf. on Computer Vision.
• 11: Dementhon, D., and Megret, R. 2002. Spatio-temporal segmentation of video by hierarchical mean shift analysis. In University of Maryland Technical Report LAMP-TR-090, CAR-TR-978, CS-TR-4388, UMIACS-TR-2002-68.
• 12: Sidney Fels , Kenji Mase, Interactive video cubism, Proceedings of the 1999 workshop on new paradigms in information visualization and manipulation in conjunction with the eighth ACM internation conference on Information and knowledge management, p.78-82, November 02-06, 1999, Kansas City, Missouri, United States [doi>10.1145/331770.331789]
• 13: Michael Gleicher, Image snapping, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.183-190, September 1995 [doi>10.1145/218380.218441]
• 14: J. Hall , D. Greenhill , G. A. Jones, Segmenting film sequences using active surfaces, Proceedings of the 1997 International Conference on Image Processing (ICIP '97) 3-Volume Set-Volume 1, p.751, October 26-29, 1997
• 15: Incorp., A. S. 2002. Adobe photoshop user guide.
• 16: Kass, M., Witkin, A., and Terzopoulos, D. 1987. Snakes: Active contour models. International Journal of Computer Vision 1, 4, 321--331.
• 17: Allison W. Klein , Peter-Pike J. Sloan , Adam Finkelstein , Michael F. Cohen, Stylized video cubes, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545264]
• 18: Kwatra, V., Shoedl, A., Essa, I., Turk, G., and Bobick, A. 2003. Graphcut textures: Image and video synthesis using graph cuts. In Proceedings of ACM SIGGRAPH, 277--286.
• 19: Li, Y., Sun, J., Tang, C.-K., and Shum, H.-Y. 2004. Lazysnapping. In Proceedings of ACM SIGGRAPH, 303--308.
• 20: Lucas, B. D., and Kanade, T. 1981. An iterative image registration technique with an application to stereo vision. In Proceedings of the 7th International Joint Conference on Artificial Intelligence (IJCAI '81), 674--679.
• 21: Luo, H., and Eleftheriadis, A. 1999. Spatial temporal active contour interpolation for semi-automatic video object generation. In International Conference on Image Processing (ICIP), 944--948.
• 22: Eric N. Mortensen , William A. Barrett, Intelligent scissors for image composition, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.191-198, September 1995 [doi>10.1145/218380.218442]
• 23: Prez, P., Blake, A., and Gangnet, M. 2001. Jetstream: Probabilistic contour extraction with particles. In Proc. Int. Conf. on Computer Vision, vol. II, 524--531.
• 24: Reese, L. J., and Barrett, W. A. 2002. Image editing with intelligent paint. Proceedings of Eurographics 21, 3, 714--724.
• 25: Rother, C., Kolmogorov, V., and Blake, A. 2004. Grabcut - interactive foreground extraction using iterated graph cut. In Proceedings of ACM SIGGRAPH, 309--314.
• 26: Ruzon, M., and Tomasi, C. 2000. Alpha estimation in natural images. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, vol. I, 18--25.
• 27: Wang, J., Xu, Y.-Q., Shum, H.-Y., and Cohen, M. F. 2004. Video tooning. In Proceedings of ACM SIGGRAPH, 574--583.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.1 Multimedia Information Systems
          Subjects: Video (e.g., tape, disk, DVI)

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Video analysis

General Terms:
Algorithms, Theory

Keywords:
alpha matting, graph-cut, interactive video processing, mean-shift segmentation, min-cut