## 3 Methodology
### Feature-Enhanced Point Transformer
#### 3.1.2 Ball Tree Downsampling Module  
The transition down layer in the point transformer network performs downsampling operations, and the module is shown in Figure 7. However, KNN sampling is usually used to obtain a set of neighboring points around a point when processing point clouds. Due to differences in the density and sampling methods of point clouds, the number of neighboring points around each point may be very different, resulting in different sizes of local regions  
Figure 5: Network encoding structure of the point transformer. Figure 6: Feature-enhanced local spatial encoding network structure. being used for calculations [53]. This makes it difficult for the network to converge, as local regions of different sizes cannot receive appropriate weight adjustments. Therefore, it is necessary to adopt a more concise and accurate method for feature downsampling. The ball tree is a spatial partitioning data structure used to organize points in a multidimensional space. The ball tree algorithm is an extension of the KNN algorithm designed for high-dimensional data. In this study, we optimized the efficiency of a point transformer to process high-dimensional point cloud data by introducing the ball tree algorithm. This optimization was conducted to achieve more accurate and stable sampling results, as illustrated in Figure 8.  
The ball tree algorithm is a tree-like structure used for performing a rapid nearest neighbor search, and it ensures a fixed local neighborhood, which is beneficial for learning local features [19]. The construction of the ball tree involves two steps: computing the spherical range and partitioning the data points. In each node, the spherical range for all data points is computed, and the two farthest points are selected as splitting points. Then, the data points are divided into left and right subsets based on these splitting points, and corresponding child nodes are created. This process continues until a node contains only one or less K data points. The abovementioned process is illustrated in Figure 9.  
Figure 8: Ball tree-based downsampling module. Figure 7: Transition down layer. The search algorithm for the ball tree method is a top-down recursive algorithm used to find the nearest neighbor of a target point. It begins at the root node and moves downward, locating the leaf node that contains the target point. Within that leaf node, it identifies the observation point closest to the target point. This distance serves as an upper bound for the nearest neighbor distance. Then, the algorithm checks if any sibling nodes of the leaf node might contain observation points closer to the target point than this upper bound. If a sibling node's region cannot possibly contain the desired observation points, the algorithm stops the recursive search for that sibling node. Otherwise, the algorithm continues to recursively search the sibling nodes and their child nodes until it finds the nearest neighbor or has searched all nodes. As the algorithm traverses each node, it calculates the distance between that node and the target point. If this distance is shorter than the current minimum distance, the algorithm updates the current minimum distance to this distance and designates the current node as the current nearest neighbor. The pseudocode for search Algorithm 1 is presented below.