The aim of this project was to develop methods for indexing, retrieval, and data mining of motion trajectories in video databases. Computer vision techniques were devised for detection and tracking of moving objects, as well as estimation of statistical time-series models that describe each object's motion, that can be used in motion-based indexing and retrieval. Algorithms were developed that can discover clusters and other patterns in the extracted motion time-series data, and to identify common versus unusual motion patterns. The hope is that the products of this research effort can enable numerous applications that are valuable to society: homeland security; video-based analysis of human biomechanics for occupational safety, as well as dance and sports training; archive management and analysis for news, entertainment, and sports video; and video database management for non-intrusive monitoring of the motion patterns of handicapped, infirm, or elderly people to detect decline, danger, or to alert caregivers when needed.

This was a joint project between the Database and Image and Video Computing research groups.

This work was supported by the National Science Foundation under Grant No. NSF IIS-0308213, "Mining and Indexing Spatio-Temporal Patterns in Video Databases of Human Motion," September 2003 -- August 2007. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.

Principal Investigators

Stan Sclaroff

Margrit Betke

George Kollios

Students Affiliated with the Research Project

Joni Alon, PhD 2006.

Vassilis Athitsos, PhD 2006

Johanna Brewer, MA 2004

Ching Chang, MA 2006

Murat Erdem, PhD student

Mikhail Gorman, MA 2006

Oleg Gusyatin, BA/MA 2004

Rui Li, PhD student

John Magee, PhD student

William Mullally, PhD student

Panagiotis Papapetrou, PhD student

Matthew Scott, BA 2004

Ashwin Thangali, PhD student

Tai-peng Tian, PhD student

Mikhail Urison, MA 2003

Benjamin Waber, MA/BA 2006

Jingbing Wang, PhD 2007

Zheng Wu, PhD student

Project Highlights

In this project we developed new methods for extracting motion information from video data and indexing and mining this information in a novel and effective way. New systems and techniques have been developed that identify motion patterns in video streams. These patterns can be used to enhance human computer interaction and allow querying large databases of motion data more efficiently and effectively. We provided novel embedding based techniques for efficient indexing and classification of motion data that achieve orders of magnitude improvement on query and classification time compared to the previous best techniques. We also proposed new ways to model and query motion data. Furthermore, the proposed approaches opened up new areas of research that offer very promising directions for further investigation. The following is a list of some of the research highlights from research that was supported in part through this grant:

Motion indexing, retrieval, analysis and mining

• Prof. Kollios worked with Prof. Nikos Mamoulis and Prof. Yufei Tao and their students to design data mining algorithms for finding approximate periods in object trajectories and using these periods for efficient indexing and approximate query answering.
• PhD student Ashwin Thangali worked with PI Sclaroff to develop a novel method for detecting periodic motion patterns in video databases. Samples from the video are taken along appropriately chosen directions in space-time. A windowed frequency analysis technique is used to determine the period for each of the sample paths. Dominant periodic motions in the shot are detected by clustering the sample paths having the same period.
• PhD student Tai-peng Tian worked with PI Sclaroff to develop a method for matching novel video of human motion to an existing archive of 3D human motion capture data. The method automatically produces a similarity ranking of the 3D motion capture data, without the need to recover the camera calibration of 3D structure from motion for the query video.
• Visiting PhD candidate Walter Nunziati, with PI Sclaroff and Prof. Alberto Del Bimbo of the U. of Florence developed trajectory-based indexing and retrieval methods for video databases.
• PhD student Jonathan Alon, with PI's Kollios and Sclaroff, develop methods to model, match, index, and/or retrieve motion patterns in video databases; e.g., human activity patterns, gestures, moving objects. He produced new algorithms and a demonstratin system for learning sparse temporal models that focus on the most discriminative features for matching and classification of motion trajectories.
• Co-PI George Kollios along with Dr. Michail Vlachos (IBM Research) and Prof. Dimitrios Gunopulos (UC Riverside) investigated techniques for analysis and retrieval of object trajectories extracted from video clips of human motion (among others).
• PhD student U. Murat Erdem and PI Sclaroff developed methods for data mining, modeling, and then predicting human motion and traffic flow in a distributed collection of PTZ video cameras.

Applications for individuals with disabilities and for physical rehabilitation

• Graduate students Oleg Gusyatin and Mikhail Urison worked with Co-PI Margrit Betke on methods for finding similarities in human motion patterns created with pointer input devices for human-computer interaction. They proposed a method called SymbolDesign that can be used to design user-centered interfaces for pen-based input devices. It can also extend the functionality of pointer input devices such as the traditional computer mouse, or camera-based computer interface such as the Camera Mouse for individuals with limited movement.
• Co-PI Margrit Betke and her graduate student Mikhail Gorman collaborated with rehabilitation specialist Prof. Elliot Saltzman from Boston University and his PhD student Amir Lahav to develop a camera-based human-computer interface called ``MusicMaker'' to provide a music-making rehabilitation tool. The proposed system uses a (1) video camera to record a subject performing therapeutic exercises, (2) detects and analyzes the subject's motion patterns, and (3) reacts to the motion patterns by producing music. The system can be adjusted to a patient's particular therapeutic needs and provides quantitative tools for monitoring the recovery process and assessing therapeutic outcomes.

Nearest-neighbor indexing and retrieval methods

• PhD students Vassilis Athitsos and Jonathan Alon, along with PI's Sclaroff and Kollios developed a strategy for approximation of expensive distance measures used in indexing and nearest neighbor classification problems. Using Lipshitz embeddings, 'vantage objects' are embeded in a Euclidean space in which similarities can be rapidly measured using a weighted Manhattan distance. Embedding construction is formulated as a machine learning task, where AdaBoost is used to combine many simple, 1D embeddings into a multidimensional embedding that preserves a significant amount of the proximity structure in the original space.
• Dr. Vassilis Athitsos along with co-PI George Kollios and PhD students Panagiotis Papapetrou and Michalis Potamias proposed a new hash based method for indexing spaces with arbitrary distance measures. Hashing methods, such as Locality Sensitive Hashing (LSH), have been successfully applied for similarity indexing in vector spaces and string spaces under the Hamming distance. The key novelty of the proposed hashing technique is that it can be applied to spaces with arbitrary distance measures.

Publically-Available Software

• BoostMap approximate nearest neighbor retrieval software
• Frequent Temporal Interval Pattern finding software

Publically-Available Datasets

• Datasets for training and evaluation of Nearest Neighbor retrieval methods
• Labeled video datasets of American Sign Language (collected on a different NSF grant, but useful for this research)