resampling¶
Routines for resampling particles from particle filters based on their current weights. All these routines take a list of normalized weights and returns a list of indexes to the weights that should be chosen for resampling. The caller is responsible for performing the actual resample.
Copyright 2015 Roger R Labbe Jr.
filterpy library. http://github.com/rlabbe/filterpy
Documentation at: https://filterpy.readthedocs.org
Supporting book at: https://github.com/rlabbe/KalmanandBayesianFiltersinPython
This is licensed under an MIT license. See the readme.MD file for more information.

filterpy.monte_carlo.
residual_resample
(weights)[source]¶ Performs the residual resampling algorithm used by particle filters.
Based on observation that we don’t need to use random numbers to select most of the weights. Take int(N*w^i) samples of each particle i, and then resample any remaining using a standard resampling algorithm [1]
Parameters: weights : listlike of float
list of weights as floats
Returns: indexes : ndarray of ints
array of indexes into the weights defining the resample. i.e. the index of the zeroth resample is indexes[0], etc.
References
[R13] J. S. Liu and R. Chen. Sequential Monte Carlo methods for dynamic systems. Journal of the American Statistical Association, 93(443):1032–1044, 1998.

filterpy.monte_carlo.
stratified_resample
(weights)[source]¶ Performs the stratified resampling algorithm used by particle filters.
This algorithms aims to make selections relatively uniformly across the particles. It divides the cumulative sum of the weights into N equal divisions, and then selects one particle randomly from each division. This guarantees that each sample is between 0 and 2/N apart.
Parameters: weights : listlike of float
list of weights as floats
Returns: indexes : ndarray of ints
array of indexes into the weights defining the resample. i.e. the index of the zeroth resample is indexes[0], etc.

filterpy.monte_carlo.
systematic_resample
(weights)[source]¶ Performs the systemic resampling algorithm used by particle filters.
This algorithm separates the sample space into N divisions. A single random offset is used to to choose where to sample from for all divisions. This guarantees that every sample is exactly 1/N apart.
Parameters: weights : listlike of float
list of weights as floats
Returns: indexes : ndarray of ints
array of indexes into the weights defining the resample. i.e. the index of the zeroth resample is indexes[0], etc.

filterpy.monte_carlo.
multinomial_resample
(weights)[source]¶  This is the naive form of roulette sampling where we compute the
 cumulative sum of the weights and then use binary search to select the resampled point based on a uniformly distributed random number. Run time is O(n log n). You do not want to use this algorithm in practice; for some reason it is popular in blogs and online courses so I included it for reference.
Parameters: weights : listlike of float
list of weights as floats
Returns: indexes : ndarray of ints
array of indexes into the weights defining the resample. i.e. the index of the zeroth resample is indexes[0], etc.