Architectural Optimizations For Particle Filters

Particle filters have shown great promise in dealing with non-linear and non-Gaussian state estimation problems. However, their applications to practical real-time scenarios are severely restricted due to their inherent computational complexities. Therefore, it is necessary, under such circumstances, to turn to their hardware implementations. This paper puts forward multiple optimizations for both centralized and distributed architectures of particle filters from the point of speed and memory.In centralized architecture, we reduce the memory utilization of resampling by state rewriting and reuse of the weight memory, which make it unnecessary to use dedicated index memory and replicated factor memory; meanwhile, we reduce the memory requirement of state storage in sampling by state compression in which a particle state is decomposed into an initial state and a code indicating the deviation of the two states. To speed up filtering processing, the judgment of effective particle numbers as well as interval resampling is introduced to decrease the times of resampling; further, a local weight mean comparison scheme is proposed, improving the speed by times.In distributed architecture, a weight sorting scheme is proposed, including complete sorting and partial sorting, to avoid the redistribution of particles by balancing the weight summations of each processing element. Also presented is a hierarchical resampling method. While dividing resampling into hierarchies, either in coarse grain or in fine grain, it generates identical results as centralized resampling in statistics. Compared with traditional distributed architectures, better trade-offs among speed, storage and accuracy can be obtained in structures based on the above two methods.