# Research on Rapid and Accurate 3D Reconstruction Algorithms Based on Multi-View Images
## 3 Materials and Methods
### Principles of the Enhanced Feature Matching Algorithm
#### 3.2.2 Multidimensional Binary Search Tree (KD-Tree) Feature Point Matching  
After the SIFT algorithm obtains feature points, feature point matching is conducted. Usually, Euclidean distance is used to determine whether there is a similarity between two descriptors. If the SIFT descriptors in two images to be matched are \(X_{i}=(X_{i1},X_{i2},\cdots,X_{i128})\) and \(Y_{i}=(Y_{i1},Y_{i2},\cdots,Y_{i128})\), the degree of similarity between these descriptors is determined from their Euclidean distance, as expressed in the following formula:  
\[d=\sqrt{\sum_{j=1}^{128}\left(X_{ij}-Y_{ij}\right)^{2}} \tag{10}\]  
Brute-force matching (BF) is a straightforward and direct matching technique. It iterates through all feature point descriptors and computes the distances between them. Then, it ranks these distances and selects the nearest feature points as matches. For two sets of feature descriptors extracted from two images, for each descriptor \(X_{i}\) in the first set, it calculates the distance to every descriptor in the second image. The shortest distances are chosen as matched points after filtering. While the brute-force method is simple, it has disadvantages. When image resolutions are excessively high, the number of feature points increases, resulting in substantial computational loads for pairwise comparisons. This leads to longer algorithm processing times and a higher incidence of erroneous matches, including cases of one-to-many matches.  
The Multidimensional Binary Search Tree (KD-Tree), KD-Tree-based feature matching method is employed to achieve faster and more efficient feature point extraction. The KD-Tree method [20] contains a spatial partitioning data structure, forming a K-dimensional binary tree where each node represents K-dimensional data. An illustrative example is shown in Figure 4, where (a) depicts a KD tree, and (b) illustrates the planar partitioning of the KD tree.  
The KD-Tree algorithm is utilized for the nearest neighbor search to identify the nearest and second-nearest feature points corresponding to each feature. If the ratio of the nearest distance to the second-nearest distance falls below a specified threshold, scale-space matching complexity may result in numerous similar Euclidean distances. The author recommends setting this threshold at 0.8. However, considering the perspective variations between different matched images, a threshold of 0.4 to 0.6 is more appropriate. A value too low may yield insufficient matches, while a value too high may lead to excessive mismatches. Typically, a threshold of 0.5 is set to designate the nearest neighbor feature point as a matching point.  
As previously mentioned, during the matching process, image information complexity and the limitations of computational methods can lead to the emergence of similar feature points, resulting in numerous mismatches. Ultimately, the Random sample consensus (RANSAC) method [21], a robust random sample consensus approach, is utilized to eliminate mismatches and achieve optimal matching pairs. The RANSAC algorithm serves as a strong parameter estimation method, working iteratively to find the best solution. The specific steps include first randomly selecting four pairs of matching points to establish an initial model. This model is then used to detect other matching points, counting the number of mismatched points to see if they meet a defined threshold. If the threshold is met, the model is accepted as the final method; if not, the process restarts by randomly selecting four new pairs of matching points.