Image analysis – Pattern recognition – Classification
Reexamination Certificate
1998-11-03
2002-03-05
Boudreau, Leo (Department: 2721)
Image analysis
Pattern recognition
Classification
C382S224000, C382S181000
Reexamination Certificate
active
06353679
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to explaining data representing physical objects by a model of those objects through a probability method of analysis.
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, images of the Earth by satellite imagery, 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.
As an example, in tracking a human figure in a sequence of video frames a human “stick model” can be used. A line having both length and orientation can be used to represent each major skeletal bone such as lower arm, upper arm, lower leg, upper leg, trunk, head, shoulder girdle, etc. A particular frame of the video can be specified by giving the length, position, and orientation of each of the lines used in the stick model. The “state” is the collection of data required to completely specify the model. The state is used to compute a predicted image in the next video frame, and the recursive estimation process is used to refine the state values by comparing the predicted image with the data gathered by the video camera. As a further example, radar, acoustic, x-ray, etc. data can be used to generate images of the physical objects being observed, and a model of the objects can be used to aid in computation of a predicted image. The state is the set of data required to completely specify the model, for example the location of each aircraft in a radar produced-image for air traffic control purposes.
Modem detectors often return a very large amount of data. For example, a simple video camera produces approximately 30 flames 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.
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, sequential data such as are collected from detection of moving objects in three dimensional space are placed into data frames. Also, a single frame of data may require analysis by a sequence of analysis operations. 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: 5745600 (1998-04-01), Chen et al.
patent: 5751831 (1998-05-01), Ono
patent: 5903454 (1999-05-01), Hoffberg et al.
patent: 5920477 (1999-07-01), Hoffberg et al.
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. et al., A mixed-state Condensation tracker with automatic model-switching, pp. 107-112.
Ju, S. et al., Cardboard People: A Parameterized Model of Artic
Cham Tat-Jen
Rehg James Matthew
Boudreau Leo
Cesari and McKenna LLP
Choobin M B
Compaq Computer Corporation
LandOfFree
Sample refinement method of multiple mode probability... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Sample refinement method of multiple mode probability..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sample refinement method of multiple mode probability... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2865657