Data processing: artificial intelligence – Miscellaneous
Reexamination Certificate
1998-01-30
2001-04-03
Powell, Mark R. (Department: 2762)
Data processing: artificial intelligence
Miscellaneous
C706S049000, C706S012000, C706S014000
Reexamination Certificate
active
06212510
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the robust detection of normative behavior of an individual as detected by a video camera and more particularly to a system for detecting unusual human behavior through the use of real time video analysis of a scene using a hidden Markov model trained with an entropic prior.
BACKGROUND OF THE INVENTION
In the past, there has been considerable interest in detecting and classifying movement of individuals for time and motion studies, for security and for general monitoring purposes. The bulk of such monitoring systems require a priori knowledge so as to be able to detect preselected or predetermined behaviors. In these systems motion captured by a video camera is matched against histograms or other types of templates. However, all of these systems require some idea of normative behavior and the non-normative behavior sought to be detected in order to make the histograms or templates.
As a result, there is wide interest in learning normative models of activity from vision through the use of hidden Markov models. However their use results in unsatisfactory results due to exceedingly low accuracies.
Note that in an article entitled “Generation of semantic regions from image sequences,” J. H. Fernyhough, A. G. Cohn, and D. C. Hogg have shown how to learn characteristic motion maps for pedestrian plazas, which are themselves representations of non-parametric distributions over collections of pedestrian trajectories. Their account can be found in European Conference on Computer Vision, 1996, volume 2, pages 475-484. Their models lack some of the important properties of the subject invention, notably concision and accurate recovery of the essential structure of the signal.
The literature of structure-learning in HMMs is, to date, based entirely on generate-and-test algorithms. These algorithms work by selecting a single state to be merged or split, then retraining the model to see if any advantage has been gained. Though these efforts use a variety of heuristic techniques and priors to avoid failures, much of the computation is squandered and reported run-times range from hours to days. Andreas Stolcke and Stephen Omohundro detail a merging algorithm in “Best-first model merging for hidden Markov model induction,” International Commputer Science Institute Technical Report 94-003, University of California Berkeley, April 1994. Shiro Ikeda details a splitting algorithm in “Construction of Phoneme Models—Model Search of Hidden Markov Models,” proceedings of the International workshop on Intelligent Signal Processing and Communication Systems, Sendai, October 1993.
Hidden Markov models are widely used for modeling and classifying signals. The Baum-Welch algorithm efficiently estimates maximum likelihood, ML, parameters, but the user is obliged to specify the graphical structure of the model. Typically the user makes several guesses at the state count and transition topology; testing each guess is computationally intensive.
The process is tedious but necessary. Since structure is the primary determinant of a model's selectivity and speed of computation.
SUMMARY OF THE INVENTION
In the subject invention, motion is classified using a hidden Markov model, the accuracy of which is greatly improved through the use of structure learning that is folded into the parameter estimation process in the form of &thgr;
&thgr;
. The result of using the entropic prior is to trim the hidden Markov model in a way not heretofore possible to eliminate or remove parameters which have little information content. Not only is accuracy improved enough to achieve a robust system, processing times are greatly reduced.
In one embodiment, the entropic prior is introduced over multinomials which favors parameters with large dynamic ranges, meaning strong odds. Iterative maximum a posteriori, MAP, estimation using this prior produces parameter values such that uninformative parameters are driven toward extinction. When applied to HMM training, the resulting models are topologically simpler and show superior generalization. To amplify the parameter extinction process, the subject invention establishes when low conditional probabilities can be zeroed, wholly eliminating transitions. Finally, the subject invention determines how and when to delete unnecessary states.
Each transform removes the model from a local probability maximum, simplifies it, and opens it to further training. All operations are monotonic in posterior probability, so that training proceeds directly to a locally optimal structure and parameterization. All algorithms presented herein have the same computational complexity as conventional Baum-Welch reestimation, e.g., linear in the size of the data and linear in the number of transitions.
More specifically, an algorithm is provided for structure discovery in signals and is used to learn a normative theory about the behavior of the visual world from coarse image representations. The theory takes the form of the transition graph and receptive fields, e.g., continuous output distributions, of a Hidden Markov Model. The learning algorithm introduces and exploits and entropic prior in the form of &thgr;
&thgr;
for fast simultaneous structure and parameter estimation. In contrast to coventionally trained HMMs, the resulting model is so highly structured that it is intelligible to humans, and can be automatically converted into a flowchart and/or a map of characteristic activities such as motion patterns in the field of view.
In the subject invention, the system is one which learns a model of human behavior from medium-to-long-term ambient video. Desiderata for such a model include that the model should partition the visual data stream into coherent activities; that it should allow the detection of anomalous behaviors; and that it should be computationally lightweight. All of these criteria are met with the subject algorithm that learns low-entropy probabilistic finite-state models from a time-series of coarse image representations. Moreover, these models are often concise enough to be intelligible to humans.
Moreover, they are normative models of activity that are readable as flowcharts or as maps of characteristic activities such as motion patterns in the field of view.
The key to this result is a new expectation-maximization, EM, algorithm for simultaneous structure and parameter learning in Hidden Markov Models.
The algorithm finds a low-entropy representation of the hidden structure of a signal by trimming uninformative edges from the state transition graph and sometimes removes entire states. The basis of the algorithm is an entropic prior on the HMM parameter values in the form of &thgr;
&thgr;
and a solution for the MAP estimate. As will be shown, the MAP estimate minimizes the entropy of the model and its cross-entropy with the data's sufficient statistics. By data's sufficient statistics is meant the fraction of times that each different kind of event occurs in the data. Iterative estimation tends to extinguish uninformative parameters, which can the be trimmed from the model. This yields a concise and computationally lightweight model. In practice, surviving states tend to be highly correlated with meaningful partitions of the data, while surviving transitions provide a least ambiguous model of the signal dynamics.
More specifically, the subject system observes the world through a video camera and/or other sensors, automatically learns a probabilistic model of normative behavior through the use of a Hidden Markov Model, and uses that model to infer the kind of activity currently under view and detect unusual behavior. The use of hidden Markov models is made possible by entropic training of the model with an &thgr;
&thgr;
entropic trainer that folds structure learning into the parameter estimation process for the Hidden Markov Model to remove parameters from the Hidden Markov Model which have little information content. This permits real time robust unusual behavior detection. In one embodiment, the system consists of three components:
Brinkman Dirk
Mitsubishi Electric Research Laboratories Inc.
Powell Mark R.
Starks Wilbert
LandOfFree
Method for minimizing entropy in hidden Markov models of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for minimizing entropy in hidden Markov models of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for minimizing entropy in hidden Markov models of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2480130