Particle Filtering

Particle filtering is essentially a heuristic continious search process. Each particle represents a probe of the whole search space. Thus, the number of particles represents the size of the search space. There are a few key steps in the search process: initialization, update weight, andd resampling. Each of these steps can be heuristically tuned following the physic world rules. A good example of applying particle filtering can be found in “Robust Indoor Localization on a Commercial Smart-Phone”, CMU TR 2011. In the paper, they adopted Importance Resampling which is a typical approach by selecting these important particles each iteration. Alternatively, another popular approach is to learn the distribution of the particles and re-generate them based on the learnt model. For example, we assume the particles follow a Normal distribution (learnt based on mean and stddev of their positions), and the observation implies another Normal distribution (pre-knowledge), we can then use a joint distribution to generate the new batch of particles. Two must read papers are Magicol and this one.

Forward Error Correction

The purpose of FEC is to ease the correction of error packets in a packet-based network. Though there are various ways to accomplish this goal, a easy-to-follow paper is “Effective erasure codes for reliable computer communication protocols”, Sigcomm Comput. Commun. Rev. 1997. The key idea is to treat N packets as N unknowns, and generate M (M greater than or equal N) un-collinear equations such that any N equations (among M) can derive the original N packets. There is actually no inherent difference between FEC and network coding. The key idea of network coding is to exploit the broadcast nature of wireless communication to save as much bandwidth as possible. Dina Katabi has been working on this back to a few years ago, which could be found here.

Periodicity Detection

There are basically two mechanisms: short-time FFT and auto-correlation. A very easy-to-follow paper “On Periodicity Detection and Structural Periodic Similarity” SDM’05. The key idea of that paper is to fuse them for robustness. The paper is written in an interesting fashion. This paper also gives a high-level description on FFT.

Periodicity detection is actually independent to the sensor. However, with different sensors, the specific approach may vary a little bit. A very good reference using RGB camera sensor is “Real-Time Periodic Motion Detection, Analysis, and Applications” CVPR 2000. The approach in the reference paper is quite intuitive and easy to follow.

Though detecting periodic activities has been well studied, it is still challenging to achieve online counting. A good practice for counting is based on a state machine with two states: (1) periodicity detection: where frequency analysis (FFT) is applied to a sliding window and peak energy ratio to tell if a periodic activity is observed; (2) edge detection: the rising/falling edges are counted. There are a few important thresholds. First, the peak energy ratio which describes how “higher” the energy of the peak should be above the ambient. Second, the threshold used to detemine if there’s a rising/falling edge. These choices require definitely domain knowledge and should use real data to learn them.

Local Regression

Regression is used to predict the output of a system based on existing observations. Local regression is thus used to account for locality which is a common phenomena in many physic world scenarios. Andrew Ng’s CS229 lecture notes is a good tutorial for understanding this concept. One example of applying local regression is in the Modellet paper, as well as in “Refining WI-FI Based Indoor Positioning” ISCAICT, 2010. The key technology for avoiding overfitting is leave-one-out cross-validation (LOOCV). The key idea of cross-validation is to ensure good performance on an independent test set. More details can be found in reference paper.

Modulation

A easy-to-follow guide to modulation could be found in here.

Rolling Shutter

One widely used exposure control is called rolling shutter where each row has a different exposure starting time. Therefore, if the scene is varying frequently, the captured data may vary from row to row. One brief introduction of rolling shutter can be found in “Energy characterization and optimization of image sensing toward continuous mobile vision” Mobisys’13. The exposure time for each row is exactly the exposure time of the camera which depends on the lighting condition. The difference of the starting times between adjacent rows is called row readout time, which depends on the hardware. Then, to analyse a shining light signal in the frequency domain, the sampling interval is deemed to be the readout time, and the sampling duration is the exposure time. A special case is that if the sampling duration is the multiple of the signal period, the signal is undetectable. Note that the exposure time doesn’t affect the highest detectable frequency, however, the longer the sampling duration, the lower the SNR.

Using rolling shutter to detect a shinning LED light source is feasible in theory. However, due to factors like imperfect sensor, exposure time, and background interference, the SNR is typically low. In common office condition, the recommended illumination level is 300 to 500 Lux. Therefore, it is impractical to apply this technique under such conditions.

IMU Sensor Fusion

Modern mobile devices ship with low-cost IMU sensors, i.e., accelerometer, gyroscope, and compass. Ideally, they can be used to track the orientation of the rigid body of the device. However, suffering from the drift issue, the sensor outputs cannot be directly used. A common way of dealing with such problems is fusing the readings from various sensors. This in general belongs to the field of Mechatronics and Robotics, and thus the derivation is quite complicated. Fortunately, we can leverage existing work described in the paper “An efficient orientation filter for inertial and inertial/magnetic sensor arrays” by Sebastian Madgwick in 2010. His code is distributed publicly and used by a lot of open source projects like this and this is a port of the algorithm in C.

Recently, I found this place does a very good job explaining the key points on sensor fusion, and a copy in pdf is here.

Random Sample Consensus

Random Sample Consensus is usually referred to as RANSAC, which is an iterative method to estimate parameters of a model from a set of observations. The key idea is very straightforward. The algorithm starts by randomly selecting a subset of all observations to train the unknown parameters of the model. Then, it tests the remain observations and count how many of them fits the model. If the ratio is higher than a threshold, the model is considered acceptable. Otherwise, the model is rejected. The algorithm goes through a finite number of iterations to find the optimal model with the highest consensus ratio. There are two key parameters, namely thresholds of consensus and acceptable model. In order to get a good estimation, the user should have solid domain knowledge of the distribution of the data and outliers. Examples and implementation in C++ could be found at here and here.

One may wounder why not using all data to train the model. The answer is that, sometimes, it is unnecessary to use all data. One example is when you want to calculate the transform matrix from one point cloud to another.

Diff Algorithm

Diff is an important algorithm in various applications such as finding the difference in two code segments. There are various ways of doing this where a representive one is described in the paper “An O(ND) Difference Algorithm and Its Variations”. One salient point of this paper is the formulation of the problem using Edit Graph. A C# implementation and discussions cound be found here. A nicer description can be found here.

Kernel Density Estimation (KDE)

Kernel density estimation (KDE) is a technique typically used to smooth the discrete density function, or more precisely the histogram, learnt from a finite set of samples. For instance, we observed 10 samples of the RSSI of a Wi-Fi access point, ranging from -40dB to -90dB. Then, we can derive the histogram distributing the samples in to 10dB sized bins. However, due to the limited number of samples, we may result in a coarse-grained shape. KDE is used to deal with such situations. The key idea is to “leak” some probability density into neighboring bins. To achieve this goal, KDE involves a kernel, commonly uniform, triangular, bi-weight, normal, or others, and apply it across the histogram. An intuitive example could be found on the Wikipedia with normal kernel. Thus, to perform KDE, one needs to choose an appropriate kernel, as well as a bandwidth for the kernel. Generally, KDE is an empirical method to make the discrete probability density function more reasonable. However, one definitely need to understand the domain knowledge to ensure that KDE really makes some sense.

Apriori Algorithm

Apriori is a classic algorithm for mining association rules in a large dataset. One famous application of Apriori is to mine common merchandise itemset bought by customers. There are two key metric in Apriori, i.e., support and confidence. Support quantify the number of transactions containing the itemset of interest. For instance, there are a total of 1000 transactions where 100 of them contains both bread and butter, then the support ratio is 100/1000=0.1. Another important metric is the confidence which measures the reasoning confidence. Use the same example. If 200 transactions contains bread and only 100 of them have butter, then the confidence is 100/200. In other words, we have 50% confidence to say that if someone buy break, she will also buy butter. Before mining the dataset, one need to specify these two metrics. Typically, confidence is set to a very high value like 99% to ensure the derived rules are significant and meaningful. The ratio of support depends heavily to the domain knowledge. In the market transaction example, support needs to be high to motivate the rearrange the goods being aware of the cost. However, in some cases, we focus more on the confidence, where the support could be low.

The algorithm works in a bottom up way. Apriori first finds out all one-item sets with support higher than the chosen metric. Then it elaborate all combinations of one-item sets to form two-item sets. The process keeps on until no more higher level set satisfies the support metric. Then, Aporiori applies the confidence metric to filter out invalid itemsets. Apriori is with many implementations which can be found easily.