Sample refinement method of multiple mode probability density estimation

• US 6,353,679 B1
• Filed: 11/03/1998
• Issued: 03/05/2002
• Est. Priority Date: 11/03/1998
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Compaq Computer Corporation (HP Inc.)
• Inventors: Cham, Tat-Jen, Rehg, James Matthew
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): CHOOBIN, BARRY
• Application Number:
  US09/185,278
• Time in Patent Office: 1,218 Days
• Field of Search: 701/207, 382/224, 382/181, 382/228, 382/103, 345/419, 345/420
• US Class Current: 382/228
• CPC Class Codes: G06F 18/2321 using statistics or function optimisation, e.g. modelling of probability density functions
• CPC Class Codes: G06T 7/277 involving stochastic approaches, e.g. using Kalman filters

Abstract

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.

Claims

1. A method of modeling an object using data, comprising:

storing said data as a frame in a pixel by pixel data structure, said data structure written into a computer memory;

selecting a set of starting points in a state space by a random selection process, said state space used for computing a probability density function;

computing a probability density function in response to said starting points, said probability density function giving a probability that a model represents said data, said probability density function plotted in state space, said state space having dimensions corresponding to parameters of said model;

determining multiple peaks in said probability density function, each said peak corresponding to a state space point, and each said state space point corresponding to a peak being referred to as a hypothesis point, and each said peak being a maximum of the probability density function;

computing a new probability density function in response to a plurality of said hypothesis points to determine a set of starting points to locate further peaks in said probability density function.

2. The method of claim 1 wherein said random selection process further comprises:

choosing a selected peak in said probability density function;

using a Gaussian selection process having a mean centered on said selected peak and a variance determined from said selected peak.

3. The method of claim 1 further comprising:

collecting said data as a sequence of frames of data, and computing said probability density function for a first frame of data as a first probability density function;

finding first peaks in said first probability density function, and selecting said set of starting points from said first peaks as a first set of starting points;

collecting a second frame of data;

computing a second probability density function in response to said second frame of data, and in response to said multiple peaks in said first probability density function;

starting a numerical search from said first set of starting points to find peaks in said second probability density function.

4. The method of claim 1 further comprising:

collecting said data as a single frame of data;

computing said probability density function as a first probability density function in response to said single frame of data and in response to a first model for said data as a first probability density function;

locating first peaks in said first probability density function and selecting first starting points in response to said first peaks;

computing a said probability density function as a second probability density function in response to said single frame of data and in response to a second model for said data as a second probability density function, and using said first starting points compute a numerical search for second peaks in said second probability function.

5. The method of claim 1 further comprising:

storing said data in a memory of a computer;

performing said computing step by a central processor unit in said computer.

6. The method of claim 1 further comprising:

choosing a number of said starting points in response to a value of said probability density function at a peak in said probability density function.

7. The method of claim 1 further comprising:

storing said data in a matrix data structure in a memory of a computer;

executing a program in a central processor unit of said computer, said computer reading and writing to said memory as said probability density function is searched numerically for peaks.