# Sound Source Localization Indoors Based on Two-Level Reference Points Matching
## 1 Introduction
An interpolation is a mathematical tool for estimating the unknown function value using available function values of other variables. Interpolation methods for scattered data are widely implemented in mathematical, industrial and manufacturing applications. Radial basis function (RBF) [25], linear [26], inverse distance weighting (IDW) [27] and kriging [28] are well-known interpolation methods for positioning database expansion. Due to the initial RP reduction, the interpolation methods can effectively increase the collection efficiency in the fingerprint database [29]. However, since the virtual RPs generated by the interpolation method still needed to participate in the adjacent RPs matching, the interpolation method cannot obviously improve the efficiency of the online positioning phase of the fingerprint-based SSL indoors. Selective matching of the target point and the RPs can reduce the computation amount of the online positioning procedure. Many studies consider dividing the database into many sub-databases, and then selecting the sub-database that is most likely to contain the adjacent RPs to reduce the computation amount for matching RPs [30]. Study [31] introduces a variety of database partition methods based on coordinate grid division, which can effectively improve the efficiency and stability of the fingerprint-based localization method. [PERSON] et al. [32] proposed a minimum enclosure method to realize the flexible definition of the grid size in the coordinate grid division method. However, the coordinate partitioning method may be affected by the subjective judgment of the operator, which may lead to problems such as inconsistent database partitioning results and high positioning errors caused by the mismatching of adjacent RPs. According to the complexity of sound field characteristics, indoor position scenes can be divided into simple and complex scenes. For a simple scene, the problem of adjacent RPs searching can be regarded as a spatial distance optimization problem that satisfies the optimal substructure. The local search algorithm is a kind of general algorithm that can solve global optimization problems through a series of local optimization processes. The greedy search algorithm is a simple and efficient local search algorithm that can improve search efficiency by avoiding the exhaustive exercises usually needed to find the optimal solution. For complex indoor scenes, cluster analysis can automatically divide the different RPs into the same sub-databases where samples have high similarity. Compared with the coordinate partitioning method, the feature clustering partitioning method is more consistent with the distributed rule of adjacent RPs [33]. In this paper, we deal with the issue of improving the localization efficiency of the fingerprint-based SSL method. A two-level RPs matching strategy is proposed in this paper to improve the search rate for the adjacent RPs. In the first-level matching process, two methods are adopted to shrink the adjacent RPs search scope. For simple scenes, a greedy search strategy is adopted for fast searching of the sub-database that contains the adjacent RPs, and for complex scenes, the search scope can be compressed by sub-databases matching based on the database partition by clustering method. The performance of the proposed algorithms is evaluated by comparing them with the traditional linear RPs matching method, and the practical experiment results verify the effectiveness of the proposed method. The rest of the paper is organized as follows: In Section 2, the general process of fingerprinting acoustic localization is briefly introduced. In Section 3, the two-stage RPs matching method is stated to improve the efficiency of SSL. In the first level search, the greedy algorithm and the Fuzzy c-means clustering algorithm are proposed separately to shrink the RPs search range of the second level search in the two different scenes indoors. Section 4 presents the implementation details and evaluates the performance of the novel methods from the results obtained.