Video retrieval using spatio-temporal descriptors

ABSTRACT

This paper describes a novel methodology for implementing video search functions such as retrieval of near-duplicate videos and recognition of actions in surveillance video. Videos are divided into half-second clips whose stacked frames produce 3D space-time volumes of pixels. Pixel regions with consistent color and motion properties are extracted from these 3D volumes by a threshold-free hierarchical space-time segmentation technique. Each region is then described by a high-dimensional point whose components represent the position, motion and, when possible, color of the region. In the indexing phase for a video database, these points are assigned labels that specify their video clip of origin. All the labeled points for all the clips are stored into a single binary tree for efficient $k$-nearest neighbor retrieval. The retrieval phase uses video segments as queries. Half-second clips of these queries are again segmented to produce sets of points, and for each point the labels of its nearest neighbors are retrieved. The labels that receive the largest numbers of votes correspond to the database clips that are the most similar to the query video segment. We illustrate this approach for video indexing and retrieval and for action recognition. First, we describe retrieval experiments for dynamic logos, and for video queries that differ from the indexed broadcasts by the addition of large overlays. Then we describe experiments in which office actions (such as pulling and closing drawers, taking and storing items, picking up and putting down a phone) are recognized. Color information is ignored to insure independence to people's appearance. One of the distinct advantages of using this approach for action recognition is that there is no need for detection or recognition of body parts.

REFERENCES

• 1: Mark Allmen , Charles R. Dyer, Computing spatiotemporal relations for dynamic perceptual organization, CVGIP: Image Understanding, v.58 n.3, p.338-351, Nov. 1993 [doi>10.1006/ciun.1993.1046]
• 2: R.C. Bolles, H.H. Baker and D.H. Marimont, "Epipolar-Plane Image Analysis: An Approach to Determining Structure from Motion", Int. J. of Computer Vision, 1(1), pp. 7--55, 1987.
• 3: E. Bruno , Denis Pellerin, Global Motion Fourier Series Expansion for Video Indexing and Retrieval, Proceedings of the 4th International Conference on Advances in Visual Information Systems, p.327-337, November 02-04, 2000
• 4: E. Bruno , D. Pellerin, Video Structuring, Indexing and Retrieval Based on Global Motion Wavelet Coefficients, Proceedings of the 16 th International Conference on Pattern Recognition (ICPR'02) Volume 3, p.30287, August 11-15, 2002
• 5: Yizong Cheng, Mean Shift, Mode Seeking, and Clustering, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.8, p.790-799, August 1995 [doi>10.1109/34.400568]
• 6: 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]
• 7: A. Del Bimbo, P. Pala and L. Tanganelli, "Video Retrieval based on Dynamics of Color Flows", ICPR 2000, vol. 1, pp. 851--854.
• 8: D. DeMenthon, "Spatio-Temporal Segmentation of Video by Hierarchical Mean Shift Analysis", SMVP 2002 (Statistical Methods in Video Processing Workshop), Copenhagen, Denmark, 2002.
• 9: Nevenka Dimitrova , Forouzan Golshani, Motion recovery for video content classification, ACM Transactions on Information Systems (TOIS), v.13 n.4, p.408-439, Oct. 1995 [doi>10.1145/211430.211433]
• 10: N. Dimitrova and M. Abdel-Mottaleb, "Content-based Video Retrieval by Example Video Clip", Proc. SPIE vol. 3022, Storage and Retrieval for Image and Video Databases, pp. 59--70, 1997.
• 11: R. Fablet, P. Bouthemy and P. Perez, "Non-parametric Motion Characterization using Causal Probabilistic Models for Video Indexing and Retrieval", IEEE Trans. on Image Processing, vol. 11(4), pp. 393--407, 2002.
• 12: Myron Flickner , Harpreet Sawhney , Wayne Niblack , Jonathan Ashley , Qian Huang , Byron Dom , Monika Gorkani , Jim Hafner , Denis Lee , Dragutin Petkovic , David Steele , Peter Yanker, Query by Image and Video Content: The QBIC System, Computer, v.28 n.9, p.23-32, September 1995 [doi>10.1109/2.410146]
• 13: Keinosuke Fukunaga, Introduction to statistical pattern recognition (2nd ed.), Academic Press Professional, Inc., San Diego, CA, 1990
• 14: A. Hampapur, A. Gupta, B. Horowitz, C-F. Shu, C. Fuller, J. Bach, M. Gorkani and R. Jain, "Virage Video Engine", Proc. SPIE vol. 3022, Storage and Retrieval for Image and Video Databases, pp. 188--198, 1997.
• 15: Yuri A. Ivanov , Aaron F. Bobick, Recognition of Visual Activities and Interactions by Stochastic Parsing, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.852-872, August 2000 [doi>10.1109/34.868686]
• 16: V. Kobla, and D. Doermann, "Indexing and Retrieval of MPEG-compressed Video", Journal of Electronic Imaging, pp. 294--307, 1998.
• 17: Yee Leung , Jiang-She Zhang , Zong-Ben Xu, Clustering by Scale-Space Filtering, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.12, p.1396-1410, December 2000 [doi>10.1109/34.895974]
• 18: R. Lienhart, W. Effelsberg and R. Jain, "Visual GREP: A Systematic Method to Compare and Retrieve Video Sequences", Proc. SPIE vol. 3312, Storage and Retrieval for Image and Video Databases, pp. 271--282, 1998.
• 19: C. Merkwirth, U. Parlitz and W. Lautherborn, "Fast Nearest-Neighbor Searching for Nonlinear Signal Processing", Phys. Review E., vol. 62, pp. 2089--2097, 2000. TSTool package available at http://www.physik3.gwdg.de/tstool/
• 20: Randal C. Nelson , Andrea Selinger, A Cubist Approach to Object Recognition, Proceedings of the Sixth International Conference on Computer Vision, p.614, January 04-07, 1998
• 21: Nuria M. Oliver , Barbara Rosario , Alex P. Pentland, A Bayesian Computer Vision System for Modeling Human Interactions, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.831-843, August 2000 [doi>10.1109/34.868684]
• 22: C. S. Pinhanez , A. F. Bobick, Human Action Detection Using PNF Propagation of Temporal Constraints, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.898, June 23-25, 1998
• 23: Yann Ricquebourg , Patrick Bouthemy, Real-Time Tracking of Moving Persons by Exploiting Spatio-Temporal Image Slices, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.797-808, August 2000 [doi>10.1109/34.868682]
• 24: Cordelia Schmid , Roger Mohr, Local Grayvalue Invariants for Image Retrieval, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.5, p.530-535, May 1997 [doi>10.1109/34.589215]
• 25: H. Sun, T. Feng and T. Tan, "Spatio-Temporal Segmentation for Video Surveillance", ICPR 2000, vol. 1, pp. 843--846, 2000.
• 26: E. Sahouria, A. Zakhor, "Motion Indexing of Video", ICIP, vol. 2, pp. 526--529, 1997.
• 27: T. F. Syeda-Mahmood, A. Vasilescu and S. Sethi, "Recognizing Action Events in Video", IEEE Workshop on Event Detection and Recognition in Video, pp. 64--72, 2001.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Additional Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.1 Multimedia Information Systems

  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.6 Segmentation

General Terms:
Algorithms, Design

Keywords:
action recognition, content-based indexing and retrieval, object motion, space-time segmentation, spatio-temporal descriptors, video retrieval of near-duplicates