Representing and recognizing temporal sequences
Aaron Bobick, Yifan Shi · 2006
Activity recognition falls in the general area of pattern recognition, but it resides mainly in the temporal domain which leads to very distinctive characteristics. We first point out those important points, then we provide an extensive survey over the existing tools including FSM, HMM, BNT, DBN, SCFG and Symbolic Network Approach (e.g. PNF-network). These tools are inefficient to meet many of the requirements of activity recognition, leading to this work to develop a new graphical model: Propagation Net (P-Net). Many activities can be represented by a partially ordered set of temporal intervals, each of which corresponds to a primitive motion. Each interval has both temporal and logical constraints that control the duration of the interval and its relationship with other intervals. Recognizing such activity requires the processing of multiple, parallel streams of intervals. P-Nets are introduced to take advantage of such fundamental constraints that it provides an graphical conceptual model to describe the human knowledge and an efficient computational model to facilitate recognition and learning. A P-Net associates a node with each interval whose stochastic triggering function depends upon the state of its parent nodes. Each node is also associated with an observation function that describes perceptual evidence. This evidence, generated by a lower level perceptual module, is a unique indicator of the elemental motion that constitutes the activity. P-Nets define an exponentially large joint distribution that standard bayesian inference cannot handle. To execute an inference task on a P-Net, we devise two approximation algorithms to interpret a multi-dimensional observation sequence of evidence as a multi-stream propagation process through P-Net. First, inspired by the Viterbi algorithm, Local Maximal Search Algorithm (LMSA) is constructed with polynomial complexity. LMSA, however, is limited in that it must see the whole process before it can provide an explanation. Second, to facilitate real-time analysis, we introduce a particle filter based framework to explore the conditional state space. By modifying the original Condensation algorithm to sample the discrete state space more efficiently, we obtain Discrete Condensation (D-Condensation) algorithm. To construct a P-Net based activity recognition system, we need two parts: the P-Net and the corresponding detector set. Given the topology information and the detector library, P-Net parameters can be extracted easily from a relatively small number of positive examples. To construct the detector library, one either has to build each detector by hand or to hand label each frame to train the individual detector. Either way, the process is expert-intensive work. To avoid this tedious process, we introduce a semi-supervised learning framework to build a P-Net and the corresponding detectors together. Once the topology of P-Net is manually specified, the P-Net and its evidence detectors are initialized on a small number of fully annotated examples. They are then refined together in a unified EM iteration by using additional non-annotated positive examples. Within this framework, we use boosted stumps as node detectors. Due to the nature of P-Net, detectors for different nodes can fire simultaneously, where normal multi-class boosting algorithm cannot work. Instead, we introduce the Contrast Boosting algorithm that forces the detectors to be as different as possible but not necessary to be non-overlapping. The classification and learning ability of P-Nets are verified on three data sets, which are obtained from vision as well as an alternative sensor platform: (1) vision tracked indoor activity data set; (2) vision tracked glucose monitor calibration data set; (3) sensor data set on simple weight-lifting exercise. Comparison with standard SCFG and HMM prove a P-Net based system is easier to construct and has a superior ability to classify complex human activity and detect anomaly. To facilitate the use of P-Nets, we introduce a hierarchical definition into the P-Net construction process. A special node that references a sub-P-Net is used in the conceptual model during the construction of a P-Net. When the conceptual model is compiled into the computational model, those special nodes are substituted by the sub P-Net so that normal P-Net inference can be performed. In activity domain, the training sequences are usually limited. Even fewer are the sequences with annotation at individual steps. P-Net can be used as a simulation machine to solve this problem. As a proof of generalization ability and the application of P-Net, we will show that, given a P-Net with a generative observation model for each node, the P-Net inference algorithm can be augmented to generate an unlimited number of positive example sequences. These large scale samples can serve as the standard testing set for any novel method.