Image analysis – Pattern recognition – Classification
Reexamination Certificate
1998-11-03
2001-05-01
Tran, Phuoc (Department: 2621)
Image analysis
Pattern recognition
Classification
Reexamination Certificate
active
06226409
ABSTRACT:
RELATED APPLICATIONS
This Application is related to the patent applications titled “Sample Refinement Method of Multiple Mode Probability Density Estimation” by Tat-Jen Cham and James M. Rehg, filed on Nov. 3, 1998 with Serial Number to be assigned, all disclosures of which are incorporated herein by reference, and “Multiple Mode Probability Density Estimation with Application to Multiple Hypothesis Tracking” by Tat-Jen Cham and James M. Rehg, filed on Nov. 3, 1998 with Serial Number to be assigned, all disclosures of which are incorporated herein by reference.
FIELD OF THE INVENTION
This invention relates to analyzing objects in an image by a succession of different analysis steps.
BACKGROUND
Multidimensional data can be collected by means of many different physical processes, for example: images may be collected by a video camera; by radar systems; by sonar systems; by infrared systems; by astronomical observations of star systems; by medical imaging using x-rays with dynamic image recording, magnetic resonance imaging, ultrasound, satellite imaging of the Earth, or by any other technology capable of generating an image of physical objects. The image data may then be analyzed in order to track targets of interest. Tracking is the recursive estimation of a sequence of states that best explains a sequence of observations. The states are specifications of the configuration of a model which is designed to explain the observations.
Modem detectors often return a very large amount of data. For example, a simple video camera produces approximately 30 frames per second (depending on the video protocol) with each frame having approximately 300 pixels horizontally across the image and 200 rows of pixels vertically in the image to yield 60,000 pixels in each image (again the details depending upon the video protocol). It is a very computation intensive process to generate a predicted image for each frame and to compare the predicted image with the actual data in order to refine the state of a model for tracking purposes.
In the event that it is desired to find an image of a face in a video image, there are approximately 60,000 pixels which must be examined for a “face” pattern. Also, a photograph or video image of an automobile running a red light requires extensive analysis in order to read the license number which may be contained in a few pixels of the image. Similarly, analysis of a portion of the Earth by examining an image, for example a television image, from a satellite in orbit around the Earth also will have a correspondingly large amount of data in which a pattern must be sought.
Kalman filter tracking has been successful as a tool for refining the parameters of a model in cases where a probability density function is sufficiently simple. Kalman filters are described by Eli Brookner in the book
Tracking and Kalman Filtering Made Easy
, published by John Wiley & Sons, Inc., in 1998, all disclosures of which are incorporated herein by reference. However, as data gathered by detectors becomes more complex, and the complex data requires the models to distinguish between ambiguous representations of the data, the simple approach to tracking by Kalman filtering breaks down.
There is needed an improved method for refining the state of a model of objects, where predictions of the model are compared with the large amounts of data produced by modern detectors.
SUMMARY OF THE INVENTION
The invention recognizes that a probability density function for fitting a model to a complex set of data often has multiple modes, each mode representing a reasonably probable state of the model when compared with the data. Particularly, an image may require a complex sequence of analyses in order for a pattern embedded in the image to be ascertained. Computation of the probability density function of the model state involves two main stages: (1) state prediction, in which the prior probability distribution is generated from information known prior to the availability of the data, and (2) state update, in which the posterior probability distribution is formed by updating the prior distribution with information obtained from observing the data. In particular this information obtained purely from data observations can also be expressed as a probability density function, known as the likelihood function. The likelihood function is a multimodal (multiple peaks) function when a single data frame leads to multiple distinct measurements from which the correct measurement associated with the model cannot be distinguished. The invention analyzes a multimodal likelihood function by numerically searching the likelihood function for peaks. The numerical search proceeds by randomly sampling from the prior distribution to select a number of seed points in state-space, and then numerically finding the maxima of the likelihood function starting from each seed point. Furthermore, kernel functions are fitted to these peaks to represent the likelihood function as an analytic function. The resulting posterior distribution is also multimodal and represented using a set of kernel functions. It is computed by combining the prior distribution and the likelihood function using Bayes Rule. The peaks in the posterior distribution are also referred to as ‘hypotheses’, as they are hypotheses for the states of the model which best explain both the data and the prior knowledge.
The invention solves the problem of ambiguous data frames or ambiguous model predictions which can occur when the objects occlude each other, or a particular data frame is otherwise difficult or impossible to interpret. The model follows the most probable set of model states into the future, and any spurious paths will usually develop low probabilities in future data frames, while good (i.e. “correct”) model states continue to develop high probabilities of representing the new data frames, as they are detected. By following predictions from a reasonable number of points in state space, the analysis scales well with large amounts of detected data.
REFERENCES:
patent: 5961571 (1999-10-01), Gorr et al.
Ahrens, J. H. et al, Extensions of Forsythe's Method for Random Sampling from the Normal Distribution, Math. Comput., 27 124 (Oct. 1973), pp. 927-937, Netlib repository at http://www.netlib.org/particularly in the file www.netlib.org/random/ranlib.c.tar.gz. Also, www.netlib.org/TOMS/599.
Anderson, B.D.O. et al., Optimal Filtering, Prentice-Hall, Inc., 1970.
Astrom, K.J., Introduction to Stochastic Control Theory, Academic Press.
Bar-Shalom, Yaakov, Tracking and Data Association, Academic Press—Harcourt, Brace, Jovanovich, 1980.
Bregler, C. et al., Video Motion Capture, www.cs.berkeley.edu/bregler/digmuy.html.
Brookner, Eli, Tracking and Kalman Filtering Made Easy, John Wiley & Sons, Inc., pp. 1-64, 1998.
Cox, I., et al., A Bayesian Multiple-Hypothesis Approach to Edge Grouping and Contour Segment, International Journal of Computer Vision, 11:1, 5-24, 1993.
Cox, I., et al., An Efficient Implementation of Reid's Multiple Hypothesis Tracking Algorithm and Its Evaluation for the Purpose of Visual Tracking, IEEE Transactions On Pattern Analysis and Machine Intelligence, vol. 18, No. 2, Feb. 1996, pp. 138-150.
Gavrila, et al., 3D Model-Based Tracking of Humans in Action: A Multi-View Approach, www.umiacs.umd.edu/users/{gavrila, lsd}/ CAR-TR-799, CS-TR-3555, Nov. 1995.
Hoel, P., Introduction to Mathematical Statistics, Third Edition, John Wiley and Sons, Inc., 1962, pp. 1-17.
Isard, M. et al., Condensation—conditional density propagation for visual tracking, International Journal of Computer Vision 29:1, 5-28, 1998.
Isard, M. t al., A mixed-state Condensation tracker with automatic model-switching, pp. 107-112.
Ju, S. et al., Cardboard People: A Parameterized Model of Articulated Image Motion, juxuan@vis.toronoto.edu, black@parc.xerox.com, yaser@umiacs.umd.edu, undated.
Kakadiaris, I., Model-Based Estimation of 3D Human Motion with Occlusion Based on Active Multi-Viewpoint Selection, CVPR 1996, pp. 81-87.
Knuth, D.E., The Art o
Cham Tat-Jen
Rehg James Matthew
Cesari and McKenna LLP
Compaq Computer Corporation
Johnston A. Sidney
Tran Phuoc
LandOfFree
Multiple mode probability density estimation with... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiple mode probability density estimation with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiple mode probability density estimation with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2441255