# Sound Source Localization Indoors Based on Two-Level Reference Points Matching
## 4 Experimental Results
### Simple Scene  
In order to investigate the effectiveness and stability of the greedy search algorithm in searching the target point's adjacent sub-database, this paper carried out a verification experiment in a simple location scene indoors. The scale of the local search sub-database is set as nine; that is, the current search center (a randomly selected RP of the database) and the eight RPs around it are included in one search process. In the offline sampling stage, the RPs have been sorted by row and column, so the relative positions of the RPs in the database can be directly calculated and compared with the ordinal numbers of its rows and columns. For example, if the RP(a, b) (the RP at row a and column b) is randomly selected as the search center, other RPs of the local search group can be selected as:  
\[\left\{\begin{array}{ccc}\text{RP}_{a+1,b-1}&\text{RP}_{a+1,b}&\text{RP}_{ a+1,b+1}\\ \text{RP}_{a,b-1}&\text{RP}_{a,b}&\text{RP}_{a,b+1}\\ \text{RP}_{a-1,b-1}&\text{RP}_{a-1,b}&\text{RP}_{a+1,b+1}\end{array}\right\} \tag{14}\]  
The adjacent sub-database search process was independently run 10 times for each test point, and the search results are shown in Table 1. Where, \(Step_{w}\) refers to the maximum number of searching steps beyond the optimal number in 10 independent tests for each test point:  
\[Step_{w}=\text{Max}(steps_{i}^{a}-steps_{i}^{a}),\ \ \ i=1,2,\ldots 10. \tag{15}\]  
and \(Step_{m}\) represents the average number of steps beyond the optimal number as:  
\[Step_{m}=\frac{1}{10}\sum_{i=1}^{10}steps_{i}^{a}-steps_{i}^{a}. \tag{16}\]  
As shown in Table 1, the actual searching steps are basically the same as the optimal number for most test points, and the worst value is two steps beyond the optimal number. Even with the initial search center randomly selected, the greedy search algorithm can steadily find the adjacent sub-database that contains the locating target, and the search path is close to the optimal path.  
\begin{table}
\begin{tabular}{c c c} \hline \hline
**No.** & \(Step_{w}\) & \(Step_{m}\) \\ \hline
1 & 2 & 0.15 \\
2 & 0 & 0 \\
3 & 1 & 0.1 \\
4 & 0 & 0 \\
5 & 0 & 0 \\
6 & 0 & 0 \\
7 & 0 & 0 \\
8 & 1 & 0.1 \\
9 & 0 & 0 \\
10 & 0 & 0 \\
11 & 1 & 0.2 \\
12 & 0 & 0 \\
13 & 0 & 0 \\ \hline \hline \end{tabular}
\end{table}
Table 1: The relative searching steps of the actual path to the ideal path at each test point.  
As an example, the ninth test point was selected to illustrate the stability of the greedy search algorithm. As shown in Figure 6, there are 9 different search paths appearing in the 10 independent searches, among which search path 3 in Figure 6c appeared 2 times. All the search paths successfully completed the search of the adjacent sub-database, and all the search paths except path 7 were optimal paths, but path 7 did not increase the time of the search steps.  
All of the test points gained equally precise results as the traditional linear matching method in the experiments. What is more, as Figure 7 shows, RP numbers 54, 55, 60 and 62 are selected as the adjacent RPs of test point 9 by the traditional linear matching method, where RP 60 is the mismatched adjacent RP, which results in test point 9 gaining a positioning error of 0.1293 m at last, which is more than the position method based on the greedy RPs searching method. By which the adjacent RPs mismatch phenomenon is avoided, and the positioning error is improved to 0.0377 m.  
Figure 6: The search path of 10 independent tests for the ninth test point.