Basic Image AlgorithmS Library  2.8.0
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
Public Member Functions | Static Public Member Functions | Protected Member Functions | Static Protected Member Functions | Protected Attributes | Static Protected Attributes | List of all members
BIAS::Condensation Class Referenceabstract

CONDENSATION (CONditional DENSity EstimATION) is a state estimator very similiar to the Kalman Filter, not only for Gaussian-, but also for any multi-modal distribution. More...

#include <StateEstimator/Condensation.hh>

+ Inheritance diagram for BIAS::Condensation:
+ Collaboration diagram for BIAS::Condensation:

Public Member Functions

void AddDebugLevel (const long int lv)
 
void AddDebugLevel (const std::string &name)
 
 Condensation ()
 
bool DebugLevelIsSet (const long int lv) const
 
bool DebugLevelIsSet (const std::string &name) const
 
virtual void EvaluateImportanceWeights ()
 If you want to use importance sampling, then overload this function, which is the importance function. More...
 
virtual void EvaluateObservationDensities ()=0
 most important function, here u have to calculate a probability for each sample position based on your observations and assign this prob. More...
 
int GetDebugLevel () const
 
std::ostream & GetDebugStream () const
 
void GetDebugStream (std::ostream &os) const
 
Vector< double > GetMean ()
 returns the mean state of the density distribution More...
 
double GetMeanWeight () const
 Returns the mean weight of all samples. More...
 
const std::vector
< BIAS::Vector< double > > & 
GetSamplePositions ()
 
double GetVariance () const
 returns the weighted variance as a scalar More...
 
bool GetVariance (Vector< double > &var) const
 Returns the variance of the sample positions in var. More...
 
bool GetWeightedVariance (Vector< double > &var) const
 Returns the "weighted variance" of the sample positions in var. More...
 
int Init (unsigned int nrSmaples)
 Init the Condensation directly after constructor, with the desired amount of Samples, there more the better the approximation of the real densities. More...
 
virtual void InitModelDefaults ()=0
 Here u can specify the model and process defaults. More...
 
int InitPrior ()
 sets the sample positions for first time step More...
 
virtual void InitPriorPositions (unsigned int nrOfInitSamples)=0
 The Prior condition is used to init the first sample positions. More...
 
long int Name2DebugLevel (const std::string &name) const
 looks up a debuglevel in the internal map, returns 0 if not found More...
 
long int NewDebugLevel (const std::string &name)
 creates a new debuglevel More...
 
int PredictNewSamplePositions ()
 
void PrintDebugLevel (std::ostream &os=std::cout) const
 
void Process ()
 This really does one iteration of Condensation. More...
 
void RemoveDebugLevel (const long int lv)
 
void RemoveDebugLevel (const std::string &name)
 
void SetDebugLevel (const long int lv)
 
void SetDebugLevel (const std::string &name)
 
void SetDebugStream (const std::ostream &os)
 
void SetDefaultInitFraction (double fraction)
 Set the amount of samples, whose position is always taken by the prior distribution. More...
 
void SetImportanceSampleFraction (double fraction)
 Only specifiy a value unlike zero, if EvaluateImportanceWeights() is overloaded. More...
 
void SetPredictionOffset (const BIAS::Vector< double > &offSet)
 all samples are moved by this offset at the prediction step More...
 
void SetProcessMean (const BIAS::Vector< double > &newProcessMean)
 set a new processMean for the PredictSamplePosition step, see SecondOrderARP_() More...
 
void ShowDebugLevel (std::ostream &os=std::cout) const
 prints all internally known debuglevels More...
 
virtual ~Condensation ()
 

Static Public Member Functions

static long int GetGlobalDebugLevel ()
 
static void SetGlobalDebugLevel (long int lev)
 

Protected Member Functions

virtual void AddDiffusions_ ()
 Adds gaussian noise to the position, can be overwritten if some other (i.e. More...
 
virtual void AddOffsets_ ()
 adds offSet_ to the samplePosNew_, can be overwritten if some other offset mechanism is needed More...
 
virtual void CalculateBaseWeights_ ()
 Once all the unweighted sample positions have been computed using predict_new_bases, this routine computes the weights by evaluating the observation density at each of the positions. More...
 
void CalculateMean_ ()
 
long ConsumeNextFreeDebuglevel_ ()
 returns the next available debuglevel More...
 
unsigned int PickImportanceSample_ ()
 
unsigned int PickOneSample_ ()
 The process model for a first-order auto-regressive process is:
x_{t+1} - mean = (x_t - mean)*scaling + sigma*w_t
where w_t is unit iid Gaussian noise, which is added by AddDiffusion. More...
 
void SecondOrderARP_ (unsigned int indexOldSample, Vector< double > &newSample)
 question: real pos_tminus2 of each sample or better old mean value for all samples? More...
 

Static Protected Member Functions

static int compdouble (const void *l, const void *r)
 

Protected Attributes

bool _doSecondOrderARP
 
long int _liDebugLevel
 
long int _liNextDebugLevel
 new concept, debuglevel are managed here in the debug class More...
 
double * _randomArray
 
std::map< std::string, long int > _String2Debuglevel
 
std::vector< double > correctionOfImportanceWeights_
 
std::vector< double > cumulProbArray_
 
std::vector< double > cumulProbArrayImportance_
 
double defaultInitFraction_
 
Vector< double > diffusionSigma_
 Process parameters. More...
 
double importanceFraction_
 
std::vector< unsigned int > indexTminus2_
 
bool initial_
 
Vector< double > mean_
 
Vector< double > meanTminus1_
 
unsigned int Nsamples_
 
BIAS::Vector< double > offSet_
 
std::vector< unsigned int > oldIndices_
 
Vector< double > processFirstOrderScale_
 
Vector< double > processMean_
 
Vector< double > processSecondOrderScale_
 
Random random_
 
std::vector< double > sampleImportanceWeights_
 
std::vector< Vector< double > > samplePosNew_
 
std::vector< Vector< double > > samplePosOld_
 
std::vector< Vector< double > > samplePosTminus2_
 
std::vector< double > sampleWeights_
 
unsigned int stateDim_
 
double sumOfImportanceWeights_
 
double sumOfWeights_
 

Static Protected Attributes

static std::ostream _zDebugStream
 
static long int GlobalDebugLevel = 0
 

Detailed Description

CONDENSATION (CONditional DENSity EstimATION) is a state estimator very similiar to the Kalman Filter, not only for Gaussian-, but also for any multi-modal distribution.

Also it is a rather simple algorithm.

The current state of a system, described by a state vector, is estimated using a certain number of samples, which approximate the real densities. This is done by incorporating measurements ( p(Z|X) ) with a prior distribution p(X)= p(X_t-1 | z_t).

Usage:

  1. Write a class derived from Condensation and overload the three necessary functions. See CondensImg and Examples/condensImgExample for examples.
  2. In your main program, just call Init() once with the desired amount of samples
  3. optional, set parameter for the initial prior distribution(write your own function)
  4. call InitPrior(), which calls InitPriorPositions() and precalculates the weigths etc.

In the loop:

  1. call PredictNewSamplePositions();
  2. GetSamplePositions() and measure at those positions
  3. call your own necessary functions to give the condensation your observation values, e. g.SetObservation()
  4. call Process(), which calls EvaluateObservationDensities() and calculates the mean etc.
  5. Get the real state of the system, e.g. the mean with GetMean()
    Author
    Daniel Grest, Feb. 2004

Definition at line 81 of file Condensation.hh.

Constructor & Destructor Documentation

Condensation::Condensation ( )

Definition at line 38 of file Condensation.cpp.

Condensation::~Condensation ( )
virtual

Definition at line 53 of file Condensation.cpp.

Member Function Documentation

void BIAS::Debug::AddDebugLevel ( const long int  lv)
inlineinherited
void BIAS::Debug::AddDebugLevel ( const std::string &  name)
inlineinherited

Definition at line 362 of file Debug.hh.

void Condensation::AddDiffusions_ ( )
protectedvirtual

Adds gaussian noise to the position, can be overwritten if some other (i.e.

non gaussian) noise is needed

Definition at line 275 of file Condensation.cpp.

void Condensation::AddOffsets_ ( )
protectedvirtual

adds offSet_ to the samplePosNew_, can be overwritten if some other offset mechanism is needed

Definition at line 292 of file Condensation.cpp.

void Condensation::CalculateBaseWeights_ ( )
protectedvirtual

Once all the unweighted sample positions have been computed using predict_new_bases, this routine computes the weights by evaluating the observation density at each of the positions.

Cumulative probabilities are also computed at the same time, to permit an efficient implementation of pick_base_sample using binary search.

Definition at line 301 of file Condensation.cpp.

References BIAS::TimeMeasure::GetRealTime(), BIAS::TimeMeasure::Reset(), BIAS::TimeMeasure::Start(), and BIAS::TimeMeasure::Stop().

void BIAS::Condensation::CalculateMean_ ( )
inlineprotected
static int BIAS::Condensation::compdouble ( const void *  l,
const void *  r 
)
inlinestaticprotected

Definition at line 252 of file Condensation.hh.

long BIAS::Debug::ConsumeNextFreeDebuglevel_ ( )
inlineprotectedinherited

returns the next available debuglevel

Author
woelk 09/2006

Definition at line 521 of file Debug.hh.

bool BIAS::Debug::DebugLevelIsSet ( const long int  lv) const
inlineinherited
bool BIAS::Debug::DebugLevelIsSet ( const std::string &  name) const
inlineinherited

Definition at line 350 of file Debug.hh.

virtual void BIAS::Condensation::EvaluateImportanceWeights ( )
inlinevirtual

If you want to use importance sampling, then overload this function, which is the importance function.

It should be a density distribution, which gives hint where to measure the object state.
Evaluate here the samplePosOld_, not the new ones
IMPORTANT: the scale of the importance weights must be equal to the normal weights, like in EvaluateObservationDensities()

Reimplemented in BIAS::CondensImg.

Definition at line 177 of file Condensation.hh.

virtual void BIAS::Condensation::EvaluateObservationDensities ( )
pure virtual

most important function, here u have to calculate a probability for each sample position based on your observations and assign this prob.

as a weight to the sample

Implemented in BIAS::CondensHisto, and BIAS::CondensImg.

int BIAS::Debug::GetDebugLevel ( ) const
inlineinherited
std::ostream& BIAS::Debug::GetDebugStream ( ) const
inlineinherited

Definition at line 405 of file Debug.hh.

void BIAS::Debug::GetDebugStream ( std::ostream &  os) const
inlineinherited

Definition at line 414 of file Debug.hh.

static long int BIAS::Debug::GetGlobalDebugLevel ( )
inlinestaticinherited

Definition at line 431 of file Debug.hh.

Vector<double> BIAS::Condensation::GetMean ( void  )
inline

returns the mean state of the density distribution

Examples:
ExampleCondensImg.cpp.

Definition at line 115 of file Condensation.hh.

double Condensation::GetMeanWeight ( ) const

Returns the mean weight of all samples.

Initialization samples and importance samples are not used in calculation.

Author
woelk 12/2004

Definition at line 432 of file Condensation.cpp.

const std::vector<BIAS::Vector<double> >& BIAS::Condensation::GetSamplePositions ( )
inline

Definition at line 107 of file Condensation.hh.

double Condensation::GetVariance ( ) const

returns the weighted variance as a scalar

Author
grest

Definition at line 375 of file Condensation.cpp.

bool Condensation::GetVariance ( Vector< double > &  var) const

Returns the variance of the sample positions in var.

Initialization samples and importance samples are not used in calculation.

Author
woelk 12/2004

Definition at line 412 of file Condensation.cpp.

References BIAS::Vector< T >::ElementwiseProduct(), TNT::Vector< T >::newsize(), and BIAS::Vector< T >::SetZero().

bool Condensation::GetWeightedVariance ( Vector< double > &  var) const

Returns the "weighted variance" of the sample positions in var.

Initialization samples and importance samples are not used in calculation.

Author
woelk 12/2004

Definition at line 390 of file Condensation.cpp.

References BIAS::Vector< T >::ElementwiseProduct(), TNT::Vector< T >::newsize(), and BIAS::Vector< T >::SetZero().

int Condensation::Init ( unsigned int  nrSmaples)

Init the Condensation directly after constructor, with the desired amount of Samples, there more the better the approximation of the real densities.

The other Init functions are called here also.

Examples:
ExampleCondensHisto.cpp, and ExampleCondensImg.cpp.

Definition at line 58 of file Condensation.cpp.

virtual void BIAS::Condensation::InitModelDefaults ( )
pure virtual

Here u can specify the model and process defaults.

Implemented in BIAS::CondensHisto, and BIAS::CondensImg.

int Condensation::InitPrior ( )

sets the sample positions for first time step

Examples:
ExampleCondensHisto.cpp, and ExampleCondensImg.cpp.

Definition at line 113 of file Condensation.cpp.

References BIAS::TimeMeasure::GetRealTime(), BIAS::TimeMeasure::Start(), and BIAS::TimeMeasure::Stop().

virtual void BIAS::Condensation::InitPriorPositions ( unsigned int  nrOfInitSamples)
pure virtual

The Prior condition is used to init the first sample positions.

Calculates a initial pos for all samples. The prior cond. maybe defined by an image (if state vector is 2-dim) or by a mixture of gaussions or Uniform_distributed or ... or ...

Implemented in BIAS::CondensHisto, and BIAS::CondensImg.

long int BIAS::Debug::Name2DebugLevel ( const std::string &  name) const
inlineinherited

looks up a debuglevel in the internal map, returns 0 if not found

Author
woelk 09/2006

Definition at line 454 of file Debug.hh.

long int BIAS::Debug::NewDebugLevel ( const std::string &  name)
inlineinherited
unsigned int BIAS::Condensation::PickImportanceSample_ ( )
inlineprotected
unsigned int BIAS::Condensation::PickOneSample_ ( )
inlineprotected

The process model for a first-order auto-regressive process is:
x_{t+1} - mean = (x_t - mean)*scaling + sigma*w_t
where w_t is unit iid Gaussian noise, which is added by AddDiffusion.

This is binary search using cumulative probabilities to pick a base sample. The use of this routine makes Condensation O(NlogN) where N is the number of samples. It is probably better to pick base samples deterministically, since then the algorithm is O(N) and probably marginally more efficient, but this routine is kept here for conceptual simplicity and because it maps better to the published literature.

Definition at line 258 of file Condensation.hh.

References cumulProbArray_, BIAS::Random::GetUniformDistributed(), Nsamples_, random_, and sumOfWeights_.

int Condensation::PredictNewSamplePositions ( )

now pick samples from the last time step using the weights

most probably from the process model

most probably gaussian noise

Examples:
ExampleCondensHisto.cpp, and ExampleCondensImg.cpp.

Definition at line 142 of file Condensation.cpp.

References BIAS::TimeMeasure::GetRealTime(), BIAS::TimeMeasure::Reset(), BIAS::TimeMeasure::Start(), and BIAS::TimeMeasure::Stop().

void BIAS::Debug::PrintDebugLevel ( std::ostream &  os = std::cout) const
inlineinherited

Definition at line 383 of file Debug.hh.

void Condensation::Process ( )

This really does one iteration of Condensation.

It calls PredictSamplePosition() and EvaluateObservationDensity() in the necessary order.

Examples:
ExampleCondensHisto.cpp, and ExampleCondensImg.cpp.

Definition at line 332 of file Condensation.cpp.

References BIAS::TimeMeasure::GetRealTime(), BIAS::TimeMeasure::Reset(), BIAS::TimeMeasure::Start(), and BIAS::TimeMeasure::Stop().

void BIAS::Debug::RemoveDebugLevel ( const long int  lv)
inlineinherited

Definition at line 369 of file Debug.hh.

void BIAS::Debug::RemoveDebugLevel ( const std::string &  name)
inlineinherited

Definition at line 376 of file Debug.hh.

void BIAS::Condensation::SecondOrderARP_ ( unsigned int  indexOldSample,
Vector< double > &  newSample 
)
inlineprotected

question: real pos_tminus2 of each sample or better old mean value for all samples?

Definition at line 303 of file Condensation.hh.

References indexTminus2_, processFirstOrderScale_, processMean_, processSecondOrderScale_, samplePosOld_, samplePosTminus2_, and stateDim_.

void BIAS::Debug::SetDebugLevel ( const long int  lv)
inlineinherited
void BIAS::Debug::SetDebugLevel ( const std::string &  name)
inlineinherited

Definition at line 325 of file Debug.hh.

void BIAS::Debug::SetDebugStream ( const std::ostream &  os)
inlineinherited

Definition at line 398 of file Debug.hh.

void Condensation::SetDefaultInitFraction ( double  fraction)

Set the amount of samples, whose position is always taken by the prior distribution.

Default is 0.2.
fraction must be in [0..1];

Definition at line 260 of file Condensation.cpp.

static void BIAS::Debug::SetGlobalDebugLevel ( long int  lev)
inlinestaticinherited

Definition at line 424 of file Debug.hh.

void Condensation::SetImportanceSampleFraction ( double  fraction)

Only specifiy a value unlike zero, if EvaluateImportanceWeights() is overloaded.

Definition at line 268 of file Condensation.cpp.

void BIAS::Condensation::SetPredictionOffset ( const BIAS::Vector< double > &  offSet)
inline

all samples are moved by this offset at the prediction step

Definition at line 103 of file Condensation.hh.

void BIAS::Condensation::SetProcessMean ( const BIAS::Vector< double > &  newProcessMean)
inline

set a new processMean for the PredictSamplePosition step, see SecondOrderARP_()

Definition at line 152 of file Condensation.hh.

void BIAS::Debug::ShowDebugLevel ( std::ostream &  os = std::cout) const
inlineinherited

prints all internally known debuglevels

Author
woelk 09/2006

Definition at line 496 of file Debug.hh.

Member Data Documentation

bool BIAS::Condensation::_doSecondOrderARP
protected

Definition at line 177 of file Condensation.hh.

long int BIAS::Debug::_liDebugLevel
protectedinherited

Definition at line 510 of file Debug.hh.

Referenced by BIAS::Debug::operator=(), and BIAS::ImageBase::operator=().

long int BIAS::Debug::_liNextDebugLevel
protectedinherited

new concept, debuglevel are managed here in the debug class

Definition at line 516 of file Debug.hh.

Referenced by BIAS::Debug::operator=().

double* BIAS::Condensation::_randomArray
protected

Definition at line 249 of file Condensation.hh.

std::map<std::string, long int> BIAS::Debug::_String2Debuglevel
protectedinherited

Definition at line 517 of file Debug.hh.

Referenced by BIAS::Debug::operator=().

std::ostream BIAS::Debug::_zDebugStream
staticprotectedinherited

Definition at line 511 of file Debug.hh.

Referenced by BIAS::Debug::operator=().

std::vector<double> BIAS::Condensation::correctionOfImportanceWeights_
protected

Definition at line 236 of file Condensation.hh.

std::vector<double> BIAS::Condensation::cumulProbArray_
protected

Definition at line 234 of file Condensation.hh.

Referenced by PickOneSample_().

std::vector<double> BIAS::Condensation::cumulProbArrayImportance_
protected

Definition at line 235 of file Condensation.hh.

Referenced by PickImportanceSample_().

double BIAS::Condensation::defaultInitFraction_
protected

Definition at line 245 of file Condensation.hh.

Vector<double> BIAS::Condensation::diffusionSigma_
protected

Process parameters.

Definition at line 241 of file Condensation.hh.

long int BIAS::Debug::GlobalDebugLevel = 0
staticprotectedinherited

Definition at line 513 of file Debug.hh.

double BIAS::Condensation::importanceFraction_
protected

Definition at line 246 of file Condensation.hh.

std::vector<unsigned int> BIAS::Condensation::indexTminus2_
protected

Definition at line 230 of file Condensation.hh.

Referenced by SecondOrderARP_().

bool BIAS::Condensation::initial_
protected

Definition at line 244 of file Condensation.hh.

Vector<double> BIAS::Condensation::mean_
protected

Definition at line 232 of file Condensation.hh.

Referenced by CalculateMean_().

Vector<double> BIAS::Condensation::meanTminus1_
protected

Definition at line 232 of file Condensation.hh.

unsigned int BIAS::Condensation::Nsamples_
protected

Definition at line 223 of file Condensation.hh.

Referenced by CalculateMean_(), PickImportanceSample_(), and PickOneSample_().

BIAS::Vector<double> BIAS::Condensation::offSet_
protected

Definition at line 250 of file Condensation.hh.

std::vector<unsigned int> BIAS::Condensation::oldIndices_
protected

Definition at line 230 of file Condensation.hh.

Vector<double> BIAS::Condensation::processFirstOrderScale_
protected

Definition at line 242 of file Condensation.hh.

Referenced by SecondOrderARP_().

Vector<double> BIAS::Condensation::processMean_
protected

Definition at line 241 of file Condensation.hh.

Referenced by SecondOrderARP_().

Vector<double> BIAS::Condensation::processSecondOrderScale_
protected

Definition at line 242 of file Condensation.hh.

Referenced by SecondOrderARP_().

Random BIAS::Condensation::random_
protected

Definition at line 248 of file Condensation.hh.

Referenced by PickImportanceSample_(), and PickOneSample_().

std::vector<double> BIAS::Condensation::sampleImportanceWeights_
protected

Definition at line 235 of file Condensation.hh.

std::vector<Vector<double> > BIAS::Condensation::samplePosNew_
protected

Definition at line 225 of file Condensation.hh.

std::vector<Vector<double> > BIAS::Condensation::samplePosOld_
protected

Definition at line 226 of file Condensation.hh.

Referenced by CalculateMean_(), and SecondOrderARP_().

std::vector<Vector<double> > BIAS::Condensation::samplePosTminus2_
protected

Definition at line 227 of file Condensation.hh.

Referenced by SecondOrderARP_().

std::vector<double> BIAS::Condensation::sampleWeights_
protected

Definition at line 234 of file Condensation.hh.

Referenced by CalculateMean_().

unsigned int BIAS::Condensation::stateDim_
protected

Definition at line 224 of file Condensation.hh.

Referenced by SecondOrderARP_().

double BIAS::Condensation::sumOfImportanceWeights_
protected

Definition at line 238 of file Condensation.hh.

Referenced by PickImportanceSample_().

double BIAS::Condensation::sumOfWeights_
protected

Definition at line 238 of file Condensation.hh.

Referenced by CalculateMean_(), and PickOneSample_().


The documentation for this class was generated from the following files: