Video object segmentation by motion-based sequential feature clustering

ABSTRACT

Segmentation of video foreground objects from background has many important applications, such as human computer interaction, video compression, multimedia content editing and manipulation. Most existing methods work on image pixels or color segments which are computationally expensive. Some methods require extensive manual inputs, static cameras, and/or rigid scenes. In this paper we propose a fully automatic foreground segmentation method based on sequential clustering of sparse image features. The sparseness makes the method computationally efficient. We use both edge and corner points extracted from each video frame. A joint spatio-temporal linear regression method is developed to compute sparse motion layers of M consecutive frames jointly under the temporal consistency constraint. Once the sparse motion layers have been identified for each frame, the corresponding dense motion layers are created using the Markov Random Field (MRF) model. The MRF model assigns the rest of the image pixels to the motion layers by considering both the color attributes and the spatial relations between each pixel and its surrounding edge/corner points. Experimental evaluations on videos taken by webcams show the effectiveness of the proposed method.

REFERENCES

• 1: N. Apostoloff and A.W. Fitzgibbon. Bayesian video matting using learnt image priors. In CVPR04, pages I: 407--414, 2004.
• 2: S. Ayer , H. S. Sawhney, Layered representation of motion video using robust maximum-likelihood estimation of mixture models and MDL encoding, Proceedings of the Fifth International Conference on Computer Vision, p.777, June 20-23, 1995
• 3: Yuri Boykov , Vladimir Kolmogorov, An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.9, p.1124-1137, September 2004 [doi>10.1109/TPAMI.2004.60]
• 4: J Canny, A computational approach to edge detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.8 n.6, p.679-698, Nov. 1986
• 5: Yung-Yu Chuang , Aseem Agarwala , Brian Curless , David H. Salesin , Richard Szeliski, Video matting of complex scenes, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 6: Y.Y. Chuang, B. Curless, D.H. Salesin, and R. Szeliski. A bayesian approach to digital matting. In CVPR01, pages II:264--271, 2001.
• 7: A. Criminisi and A. Blake. The sps algorithm: patching figural continuity and transparency by split-patch search. In CVPR, pages I: 342--349, 2004.
• 8: Trevor Darrell , Alex P. Pentland, Cooperative Robust Estimation Using Layers of Support, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.5, p.474-487, May 1995 [doi>10.1109/34.391395 ]
• 9: A.P. Dempster, N.M. Laird, and D.B. Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society, 39(B):1--38, September 1977.
• 10: S. Geman and D. Geman. Stochastic relaxation, gibbs distributions, and the bayesian restoration of images. IEEE Transactions on PAMI, 6:721--741, 1984.
• 11: Alexander T. Ihler, John W. Fisher, and Alan S. Willsky. Message errors in belief propagation. In Lawrence K. Saul, Yair Weiss, and Léon Bottou, editors, Advances in Neural Information Processing Systems 17, pages 609--616. MIT Press, Cambridge, MA, 2005.
• 12: A.D. Jepson and M.J. Black. Mixture models for optical ow computation. In CVPR93, 1993.
• 13: Allan D. Jepson , David J. Fleet , Michael J. Black, A Layered Motion Representation with Occlusion and Compact Spatial Support, Proceedings of the 7th European Conference on Computer Vision-Part I, p.692-706, May 28-31, 2002
• 14: N. Jojic and B.J. Frey. Learning exible sprites in video layers. In CVPR01, pages I:199--206, 2001.
• 15: Q. Ke and T. Kanade. A subspace approach to layer extraction. In CVPR01, pages I:255--262, 2001.
• 16: S. Khan and M. Shah. Object based segmentation of video using color, motion and spatial information. In CVPR01, pages II:746--751, 2001.
• 17: V. Kolmogorov , A. Criminisi , A. Blake , G. Cross , C. Rother, Bi-Layer Segmentation of Binocular Stereo Video, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 2, p.1186, June 20-26, 2005 [doi>10.1109/CVPR.2005.90]
• 18: Yin Li , Jian Sun , Heung-Yeung Shum, Video object cut and paste, ACM SIGGRAPH 2005 Papers, July 31-August 04, 2005, Los Angeles, California
• 19: B.D. Lucas and T. Kanade. An iterative image registration technique with an application to stereo vision. In IJCAI81, pages 674--679, 1981.
• 20: C. Rother, V. Kolmogorov, and A. Blake. Grabcut - interactive foreground extraction using iterated graph cuts. In ACM SIGGRAPH 2004, pages 309--314, 2004.
• 21: M.A. Ruzon and C. Tomasi. Alpha estimation in natural images. In CVPR00, pages I: 18--25, 2000.
• 22: Jianbo Shi , Jitendra Malik, Motion Segmentation and Tracking Using Normalized Cuts, Proceedings of the Sixth International Conference on Computer Vision, p.1154, January 04-07, 1998
• 23: Heung-Yeung Shum , Jian Sun , Shuntaro Yamazaki , Yin Li , Chi-Keung Tang, Pop-up light field: An interactive image-based modeling and rendering system, ACM Transactions on Graphics (TOG), v.23 n.2, p.143-162, April 2004 [doi>10.1145/990002.990005]
• 24: J. Sun, J.Y. Jia, C.K. Tang, and H.Y. Shum. Poisson matting. In ACM SIGGRAPH 2004, pages 315--321, 2004.
• 25: Philip H. S. Torr , Richard Szeliski , P. Anandan, An Integrated Bayesian Approach to Layer Extraction from Image Sequences, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.3, p.297-303, March 2001 [doi>10.1109/34.910882 ]
• 26: Jue Wang , Michael F. Cohen, An Iterative Optimization Approach for Unified Image Segmentation and Matting, Proceedings of the Tenth IEEE International Conference on Computer Vision, p.936-943, October 17-20, 2005 [doi>10.1109/ICCV.2005.37]
• 27: J.Y.A. Wang and E.H. Adelson. Representing moving images with layers. IP, 3(5):625--638, September 1994.
• 28: Yang Wang , Qiang Ji, A Dynamic Conditional Random Field Model for Object Segmentation in Image Sequences, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 1, p.264-270, June 20-26, 2005 [doi>10.1109/CVPR.2005.26]
• 29: J. Xiao and M. Shah. Motion layer extraction in the presence of occlusion using graph cuts. In CVPR04, pages II: 972--979, 2004.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.6 Segmentation
          Subjects: Pixel classification

General Terms:
Algorithms

Keywords:
feature clustering, feature extraction, linear regression, markov random field, object segmentation