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. A. Yilmaz, O. Javed, and M. Shah, "Object tracking: a survey," ACM Computing Surveys, vol. 38, no. 4, p. 13, 2006.
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. I. J. Cox, "A review of statistical data association techniques for motion correspondence," International Journal of Computer Vision, vol. 10, no. 1, pp. 53-66, 1993.
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. D. Terzopoulos and R. Szeliski, "Tracking with Kalman snakes," in Active Vision, pp. 3-20, MIT Press, Cambridge, Mass, USA, 1993.
11. M. Isard and A. Blake, "Condensation--conditional density propagation for visual tracking," International Journal of Computer Vision, vol. 29, no. 1, pp. 5-28, 1998.
12. J. MacCormick and A. Blake, "A probabilistic exclusion principle for tracking multiple objects," International Journal of Computer Vision, vol. 39, no. 1, pp. 57-71, 2000.
13. N. Paragios and R. Deriche, "Geodesic active regions for motion estimation and tracking," in Proceedings of the 7th IEEE International Conference on Computer Vision (ICCV '99), vol. 1, pp. 688-694, Kerkyra, Greece, September 1999.
14. A. Criminisi, G. Cross, A. Blake, and V. Kolmogorov, "Bilayer segmentation of live video," in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR '06), vol. 1, pp. 53-60, New York, NY, USA, June 2006.
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. Y. Shi and W. C. Karl, "Real-time tracking using level sets," in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR '05), vol. 2, pp. 34-41, San Diego, Calif, USA, June 2005.
17. M. Bertalmio, G. Sapiro, and G. Randall, "Morphing active contours," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22, no. 7, pp. 733-737, 2000.
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. A.-R. Mansouri, "Region tracking via level set PDEs without motion computation," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 24, no. 7, pp. 947-961, 2002.
20. R. Ronfard, "Region-based strategies for active contour models," International Journal of Computer Vision, vol. 13, no. 2, pp. 229-251, 1994.
21. A. Yilmaz, X. Li, and M. Shah, "Contour-based object tracking with occlusion handling in video acquired using mobile cameras," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 11, pp. 1531-1536, 2004.
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. D. Comaniciu, V. Ramesh, and P. Meer, "Kernel-based optical tracking," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 25, no. 5, pp. 564-577, 2003.
26. D. Freedman and M. W. Turek, "Illumination-invariant tracking via graph cuts," in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR '05), vol. 2, pp. 10-17, San Diego, Calif, USA, June 2005.
27. R. Kjeldsen and J. Kender, "Finding skin in color images," in Proceedings of the 2nd International Conference on Automatic Face and Gesture Recognition (FG '96), pp. 312-317, Killington, Vt, USA, October 1996.
28. M. Singh and N. Ahuja, "Regression based bandwidth selection for segmentation using Parzen windows," in Proceedings of the 9th IEEE International Conference on Computer Vision (ICCV '03), vol. 1, pp. 2-9, Nice, France, October 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. O. Juan and Y. Boykov, "Active graph cuts," in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR '06), vol. 1, pp. 1023-1029, New York, NY, USA, June 2006.
33. P. Kohli and P. Torr, "Effciently solving dynamic markov random fields using graph cuts," in Proceedings of the 10th IEEE International Conference on Computer Vision (ICCV '05), pp. 922-929, Beijing, China, October 2005.
34. Y. Wang, J. F. Doherty, and R. E. Van Dyck, "Moving object tracking in video," in Proceedings of the 29th Applied Imagery Pattern Recognition Workshop (AIPR '00), p. 95, Washington, DC, USA, October 2000.
35. D. Comaniciu and P. Meer, "Mean shift: a robust approach toward feature space analysis," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 24, no. 5, pp. 603-619, 2002.
36. Y. Boykov, O. Veksler, and R. Zabih, "Fast approximate energy minimization via graph cuts," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 23, no. 11, pp. 1222-1239, 2001.
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. Y. Boykov and V. Kolmogorov, "An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 9, pp. 1124-1137, 2004.
41. Y. Boykov, O. Veksler, and R. Zabih, "Markov random fields with efficient approximations," in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR '98), pp. 648-655, Santa Barbara, Calif, USA, June 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. L. Zhao and L. S. Davis, "Closely coupled object detection and segmentation," in Proceedings of the 10th IEEE International Conference on Computer Vision (ICCV '05), vol. 1, pp. 454-461, Beijing, China, October 2005.
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

• Computing methodologies

  • Artificial intelligence

    • Computer vision

      • Computer vision problems

        • Interest point and salient region detections

        • Object recognition

        • Tracking

      • Computer vision tasks

        • Scene understanding

  • Computer graphics

    • Image manipulation

  • Machine learning

    • Machine learning algorithms

      • Feature selection

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms