AbstractÐHidden Markov models (HMMs) have become the workhorses of the monitoring and event recognition literature because they bring to time-series analysis the utility of density estimation and the convenience of dynamic time warping. Once trained, the internals of these models are considered opaque; there is no effort to interpret the hidden states. We show that by minimizing the entropy of the joint distribution, an HMM's internal state machine can be made to organize observed activity into meaningful states. This has uses in video monitoring and annotation, low bit-rate coding of scene activity, and detection of anomalous behavior. We demonstrate with models of office activity and outdoor traffic, showing how the framework learns principal modes of activity and patterns of activity change. We then show how this framework can be adapted to infer hidden state from extremely ambiguous images, in particular, inferring 3D body orientation and pose from sequences of low-resolution silhouettes. Index TermsÐVideo activity monitoring, hidden Markov models, hidden state, parameter estimation, entropy minimization. ae A discrete-time hidden Markov model is a mixture model augmented with dynamics by conditioning its hidden state in time t on that of time tÀI. An HMM of x hidden states and Gaussian emission distributions is specified by the 4-tuple f ijj Y i Y " " i Y u u i gY I iY j x, where ijj are multinomial transition probabilities between hidden states, i is the initial probability of state i, and " " i Y u u i parameterize emission distributions for each state, in this case, means and covariances of the Gaussian densities Prob(x xj state i) = x x xY " " i Y u u i . The likelihood of a multivariate time-series is the product of all transition and emission probabilities associated with a hidden state sequence fs I Y s I Y Y s g, summed over all possible state sequences: Dynamic programming algorithms are available for the basic inference tasks: Given a time-series, the Viterbi algorithm computes the most probable hidden state sequence; the forwardbackward algorithm computes the data likelihood and expected sufficient statistics of hidden events such as state transitions and occupancies. These statistics are used in Baum-Welch parameter reestimation to maximize the likelihood of the model given the data. The expectation-maximization (EM) algorithm for HMMs consists of forward-backward analysis and Baum-Welch reestimation iterated to convergence at a local likelihood maximum. The principle of maximum likelihood (ML) is not valid for small data sets; in most vision tasks, the training data is rarely large enough to ªwash outº sampling artifacts (e.g., noise) that obscure the data-generating mechanism's essential regularities. It is not widely appreciated that this is an acute problem in hiddenvariable models, where most of the parameters are only supported by small subsets of the data. That, combined with the fact that the models have high-order symmetries that allow many different parameterizations of the same distribution, results in a learning problem that is riddled with local optima. Consequently, ML hidden-variable models are typically both under-fit, failing to capture the hidden structure of the signal, and over-fit, with a surfeit of weakly supported parameters that inadvertently model accidental properties of the signal such as noise and sample bias. This leads to poor predictive power and modest generalization that supports only limited inference tasks, such as classifying one of a small set of events of interest. We advocate replacing the Baum-Welch formulñ with parameter estimators that minimize entropy. Entropy minimization exploits the duality between learning and compression to approximate an optimal separation between essential properties (regularities and hidden structure in the data that should be captured by the model) and accidental properties (noise and sampling artifacts that should be ignored). In doing so, it reveals hidden structures in the data that tend to be highly correlated with meaningful partitions of the data-generating mechanism's behavior. In this article, we outline entropy minimization for HMMs and show how three video interpretation tasks can be treated as problems of inferring hidden state: annotating office activity, monitoring traffic intersections, and inferring 3D motion from monocular video. A common thread in these applications is the emphasis of inference over image processing or scene modeling; high-level inferences are made from relatively impoverished sensing via learned priors rather than engineered algorithms. Small HMMs and HMM-based hybrids have enjoyed wide success in spoken word and visual gesture recognition, partly because it is feasible to hand-design an adequate transition topology, which is the dominating constraint in the learning problem. However, their usefulness for more complicated systems is seriously curtailed by the fact that for models of nontrivial size, one must probe for an appropriate topology using very expensive search techniques. Although the literature of HMM-based visual event classification is extensive, to our knowledge it does not touch on the focus of this articleÐdiscovering a set of event types that efficiently describes action in the videoÐso we will only review it categorically. One may consult the proceedings [11], [8], [14] to see the bulk of the visual monitoring and event recognition literature in the last two years: Over 30 such papers use a small battery of HMMs as a postvisual processing event classification engine. Nearly all use the HMMs as a standard Bayesian MAP classifier: Each HMM is trained on a few examples of the event of interest; after training, novel events are classified via likelihood ratios. The HMMs have a hand-designed topology, typically corresponding to a band-diagonal transition matrix; the number of bands and states is found by experimentation. Related models, such as dynamic Bayes' nets, also require careful hand-crafting. The problem of finding appropriate HMM topologies is the subject of intense research interest outside of the vision literature; [5] reviews 12 of the most current approaches to learning HMM topology, all involving heuristic generate-and-test search or heuristic clustering methods. In this article, we will explore an unsupervised approach in which entropy minimization automatically induces a partitioning of the signal into events of interest. This framework yields monotonic (hillclimbing) algorithms for simultaneous estimation of model topology and parameters. As our applications will show, the result is a single, sparsely connected HMM containing the entire classification engine. This allows us to 844 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 22, NO. 8, AUGUST 2000 . M. Brand is with Mitsubishi
REF use an entropy-based function instead of the Maximum-Likelihood estimator in the E-step of the EMalgorithm for learning parameters of Hidden Markov Mod-els (HMM).
Discovery and Segmentation of Activities in Video
IEEE Trans. Pattern Anal. Mach. Intell.
IEEE Trans. Pattern Anal. Mach. Intell.
Computer Science