# Brain-Like Navigation Scheme based on MEMS-INS and Place Recognition
## 3 Algorithm
### Grid-Based Motion Statistics Algorithm  
Grid-based motion statistics algorithm (GMS) is a simple statistics-based solution to the feature matching problem. The general process of algorithm execution is: firstly, perform any kind of detection and the description calculation of feature points (ORB features are used in our experiment). Then, perform a BF (Brute Force) algorithm and finally perform a GMS to eliminate the mismatch. The principle of the GMS algorithm is as follows. For a certain matching point \((x_{i},x_{i}^{\prime})\), \(N_{i}\) is the score of the match which can be thought as a measure of neighborhood support. It can be deduced that \(N_{i}\) obeys a binomial distribution:  
\[N_{i}\sim\left\{ \begin{array}{ll}B(M,p_{r}),&\text{if $x_{i}$ is the right match point}\\ B(M,p_{w}),&\text{if $x_{i}$ is the wrong match point}\end{array} \right., \tag{13}\]  
where \(M\) is the number of supporting features of \(x_{i}\) in its neighborhood. \(p_{r}\) is the probability that, when \(\left(x_{i},x_{i}^{\prime}\right)\) is the correct match, the matching points corresponding to other feature points in the neighborhood of \(x_{i}\) are in the neighborhood of \(x_{i}^{\prime}\). \(p_{w}\) is the probability that, when \(\left(x_{i},x_{i}^{\prime}\right)\) is the wrong match, the matching points corresponding to other feature points in the neighborhood of \(x_{i}\) are in the neighborhood of \(x_{i}^{\prime}\). The mean value and standard deviation are:  
\[\left\{ \begin{array}{ll}\mu_{r}=Mp_{r},&s_{r}=\sqrt{Mp_{r}(1-p_{r})}&\text{ if $x_{i}$ is the right match point}\\ \mu_{w}=Mp_{w},&s_{w}=\sqrt{Mp_{w}(1-p_{w})}&\text{if $x_{i}$ is the wrong match point}\end{array} \right.. \tag{14}\]  
The target function is:  
\[\max\quad G=\frac{\mu_{r}-\mu_{w}}{s_{r}+s_{w}}. \tag{15}\]  
In order to turn the above theoretical analysis into an algorithm that can be used in practice, four problems need to be considered:  
(a) Efficient calculation of the score through grid-cells;  
(b) Grouping match neighborhoods for robustness;  
(c) Number of grid-cells to use;  
(d) Calculation of the effective threshold \(S\);  
The solutions are summarized as follows:  
(a) Divide the image into \(G=20\times 20\) grids, iterate through each potential cell-pair once to compute the scores, accept all true matches between cell-pairs. (b) For robustness purposes, group the cell-pairs, i.e., neighborhoods that match. A \(3\times 3=9\) grid around the network is calculated, as shown in the red region in Figure 6.  
Figure 5: Raw image, region of interest (ROI) area and the scanline profile of the image. For grid \(m\) and grid \(n\), the similarity score is calculated by the following formula:  
\[S_{mn}=\sum_{i=1}^{9}\bigl{|}\Omega_{n\
eq i\
eq i}\bigr{|}, \tag{16}\]  
where \(\bigl{|}\Omega_{n\
eq i\
eq i}\bigr{|}\) is the number of matching points between grid \(m^{i}\) and grid \(n^{i}\). (c) The number of grids is usually the empirical value \(G=20\times 20\) cells for 10,000 features. (d) Categorize the cell-pairs into the true set and the false set by thresholding \(S_{mn}\). \[C(m,n)= \begin{cases}1,&\text{if }S_{mn}>\alpha\sqrt{t_{i}}\\ 0,&\text{otherwise}\end{cases} , \tag{17}\]  
where \(\alpha=6\) is determined from experiment and \(t_{i}\) is the total number of features present in a single cell of the nine cells in Figure 6. The value of \(C(m,n)\) indicates whether the grid area where \(m\) and \(n\) are a pair of corrected matching points. The advantages of GMS are high matching accuracy, strong adaptability to the environment and almost zero misjudgment rate of the scene. Meanwhile, compared with the traditional feature matching algorithm, the matching time cost of GMS is significantly reduced, which basically meets the requirements of real-time processing (it takes about 31 ms to process a pair of images under the configuration Intel i7 CPU+GTX980 GPU).