Track and cut: simultaneous tracking and segmentation of multiple objects with graph cuts

ABSTRACT

This paper presents a new method to both track and segment multiple objects in videos using min-cut/max-flow optimizations. We introduce objective functions that combine low-level pixel wise measures (color, motion), high-level observations obtained via an independent detection module, motion prediction, and contrast-sensitive contextual regularization. One novelty is that external observations are used without adding any association step. The observations are image regions (pixel sets) that can be provided by any kind of detector. The minimization of appropriate cost functions simultaneously allows "detection-before-track" tracking (track-to-observation assignment and automatic initialization of new tracks) and segmentation of tracked objects. When several tracked objects get mixed up by the detection module (e.g., a single foreground detection mask is obtained for several objects close to each other), a second stage of minimization allows the proper tracking and segmentation of these individual entities despite the confusion of the external detection module.

REFERENCES

• 1: Alper Yilmaz , Omar Javed , Mubarak Shah, Object tracking: A survey, ACM Computing Surveys (CSUR), v.38 n.4, p.13-es, 2006 [doi>10.1145/1177352.1177355]
• 2: A. Bugeau and P. Pérez, "Detection and segmentation of moving objects in highly dynamic scenes," in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR '07), pp. 1-8, Minneapolis, Minn, USA, June 2007.
• 3: A. Bugeau and P. Pérez, "Track and cut: simultaneous tracking and segmentation of multiple objects with graph cuts," in Proceedings of the 3rd International Conference on Computer Vision Theory and Applications (VISAPP '08), pp. 1-8, Madeira, Portugal, January 2008.
• 4: R. Kalman, "A new approach to linear filtering and prediction problems," Journal of Basic Engineering, vol. 82, pp. 35-45, 1960.
• 5: N. J. Gordon, D. J. Salmond, and A. F. M. Smith, "Novel approach to nonlinear/non-Gaussian Bayesian state estimation," IEE Proceedings F: Radar and Signal Processing, vol. 140, no. 2, pp. 107-113, 1993.
• 6: D. Reid, "An algorithm for tracking multiple targets," IEEE Transactions on Automatic Control, vol. 24, no. 6, pp. 843-854, 1979.
• 7: Ingemar J. Cox, A review of statistical data association for motion correspondence, International Journal of Computer Vision, v.10 n.1, p.53-66, Feb. 1993 [doi>10.1007/BF01440847]
• 8: Y. Bar-Shalom and X. Li, Estimation and Tracking: Principles, Techniques, and Software, Artech House, Boston, Mass, USA, 1993.
• 9: Y. Bar-Shalom and X. Li, Multisensor-Multitarget Tracking: Principles and Techniques, YBS Publishing, Storrs, Conn, USA, 1995.
• 10: Demetri Terzopoulos , Richard Szeliski, Tracking with Kalman snakes, Active vision, MIT Press, Cambridge, MA, 1993
• 11: Michael Isard , Andrew Blake, C$ONDENSATION$—Conditional Density Propagation forVisual Tracking, International Journal of Computer Vision, v.29 n.1, p.5-28, Aug. 1998 [doi>10.1023/A:1008078328650]
• 12: John MacCormick , Andrew Blake, A Probabilistic Exclusion Principle for Tracking Multiple Objects, International Journal of Computer Vision, v.39 n.1, p.57-71, Aug. 2000 [doi>10.1023/A:1008122218374]
• 13: Nikos Paragios , Rachid Deriche, Geodesic Active Regions for Supervised Texture Segmentation, Proceedings of the International Conference on Computer Vision-Volume 2, p.926, September 20-25, 1999
• 14: A. Criminisi , G. Cross , A. Blake , V. Kolmogorov, Bilayer Segmentation of Live Video, Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.53-60, June 17-22, 2006 [doi>10.1109/CVPR.2006.69]
• 15: N. Paragios and G. Tziritas, "Adaptive detection and localization of moving objects in image sequences," Signal Processing: Image Communication, vol. 14, no. 4, pp. 277-296, 1999.
• 16: Yonggang Shi , W. Clem Karl, Real-Time Tracking Using Level Sets, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 2, p.34-41, June 20-26, 2005 [doi>10.1109/CVPR.2005.294]
• 17: Marcelo Bertalmío , Guillermo Sapiro , Gregory Randall, Morphing Active Contours, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.7, p.733-737, July 2000 [doi>10.1109/34.865191]
• 18: D. Cremers and C. Schnörr, "Statistical shape knowledge in variational motion segmentation," Image and Vision Computing , vol. 21, no. 1, pp. 77-86, 2003.
• 19: Abdol-Reza Mansouri, Region Tracking via Level Set PDEs without Motion Computation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.7, p.947-961, July 2002 [doi>10.1109/TPAMI.2002.1017621]
• 20: Rémi Ronfard, Region-based strategies for active contour models, International Journal of Computer Vision, v.13 n.2, p.229-251, Oct. 1994 [doi>10.1007/BF01427153]
• 21: Alper Yilmaz , Xin Li , Mubarak Shah, Contour-Based Object Tracking with Occlusion Handling in Video Acquired Using Mobile Cameras, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.11, p.1531-1536, November 2004 [doi>10.1109/TPAMI.2004.96]
• 22: N. Xu and N. Ahuja, "Object contour tracking using graph cuts based active contours," in Proceedings of the IEEE International Conference on Image Processing (ICIP '02), vol. 3, pp. 277-280, Rochester, NY, USA, September 2002.
• 23: J. Shi and C. Tomasi, "Good features to track," in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR '94), pp. 593-600, Seattle, Wash, USA, June 1994.
• 24: D. Comaniciu, V. Ramesh, and P. Meer, "Real-time tracking of non-rigid objects using mean shift," in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR '00), vol. 2, pp. 142-149, Hilton Head Island, SC, USA, June 2000.
• 25: Dorin Comaniciu , Visvanathan Ramesh , Peter Meer, Kernel-Based Object Tracking, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.5, p.564-575, May 2003 [doi>10.1109/TPAMI.2003.1195991]
• 26: Daniel Freedman , Matthew W. Turek, Illumination-Invariant Tracking via Graph Cuts, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 2, p.10-17, June 20-26, 2005 [doi>10.1109/CVPR.2005.182]
• 27: R. Kjeldsen , J. Kender, Finding skin in color images, Proceedings of the 2nd International Conference on Automatic Face and Gesture Recognition (FG '96), p.312, October 14-16, 1996
• 28: Maneesh Singh , Narendra Ahuja, Regression based Bandwidth Selection for Segmentation using Parzen Windows, Proceedings of the Ninth IEEE International Conference on Computer Vision, p.2, October 13-16, 2003
• 29: B. D. Lucas and T. Kanade, "An iterative technique of image registration and its application to stereo," in Proceedings of the 7th International Joint Conference on Artificial Intelligence (IJCAI '81), Vancouver, Canada, August 1981.
• 30: A. D. Jepson, D. J. Fleet, and T. F. El-Maraghi, "Robust online appearance models for visual tracking," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 25, no. 10, pp. 1296-1311, 2003.
• 31: H. T. Nguyen and A. W. M. Smeulders, "Fast occluded object tracking by a robust appearance filter," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 8, pp. 1099-1104, 2004.
• 32: Olivier Juan , Yuri Boykov, Active Graph Cuts, Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.1023-1029, June 17-22, 2006 [doi>10.1109/CVPR.2006.47]
• 33: Pushmeet Kohli , Philip H. S. Torr, Effciently Solving Dynamic Markov Random Fields Using Graph Cuts, Proceedings of the Tenth IEEE International Conference on Computer Vision, p.922-929, October 17-20, 2005 [doi>10.1109/ICCV.2005.81]
• 34: Yiwei Wang , John F. Doherty , Robert E. Van Dyck, Moving Object Tracking in Video, Proceedings of the 29th Applied Imagery Pattern Recognition Workshop, p.95, October 16-18, 2000
• 35: Dorin Comaniciu , Peter Meer, Mean Shift: A Robust Approach Toward Feature Space Analysis, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.5, p.603-619, May 2002 [doi>10.1109/34.1000236]
• 36: 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]
• 37: Y. Boykov and M.-P. Jolly, "Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images," in Proceedings of the 8th IEEE International Conference on Computer Vision (ICCV '01), vol. 1, pp. 105-112, Vancouver, Canada, July 2001.
• 38: S. Kullback and R. A. Leibler, "On information and sufficiency," Annals of Mathematical Statistics, vol. 22, no. 1, pp. 79-86, 1951.
• 39: A. Blake, C. Rother, M. Brown, P. Pérez, and P. Torr, "Interactive image segmentation using an adaptive GMMRF model," in Proceedings of the 8th European Conference on Computer Vision (ECCV '04), pp. 428-441, Prague, Czech Republic, May 2004.
• 40: 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]
• 41: Y. Boykov , O. Veksler , R. Zabih, Markov Random Fields with Efficient Approximations, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.648, June 23-25, 1998
• 42: M. Bray, P. Kohli, and P. Torr, "PoseCut: simultaneous segmentation and 3D pose estimation of humans using dynamic graph-cuts," in Proceedings of the 9th European Conference on Computer Vision (ECCV '06), pp. 642-655, Graz, Austria, May 2006.
• 43: J. Rihan, P. Kohli, and P. Torr, "Objcut for face detection," in Proceedings of the 4th Indian Conference on Computer Vision, Graphics and Image Processing (ICVGIP '06), pp. 861-871, Madurai, India, December 2006.
• 44: Liang Zhao , Larry S. Davis, Closely Coupled Object Detection and Segmentation, Proceedings of the Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1, p.454-461, October 17-20, 2005 [doi>10.1109/ICCV.2005.55]
• 45: D. Ramanan, "Using segmentation to verify object hypotheses," in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR '07), Minneapolis, Minn, USA, June 2007.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.8 Scene Analysis
          Subjects: Tracking

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.6 Segmentation
          Subjects: Pixel classification; Edge and feature detection
      I.4.7 Feature Measurement
      I.4.8 Scene Analysis
          Subjects: Object recognition
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection

General Terms:
Algorithms, Design, Measurement