# Segmenting Individual Tree from TLS Point Clouds Using Improved DBSCAN
## 2 Methods and Materials
### Trunk Detection
#### 2.1.1 Generate the Optimal Parameters Based on DDM  
The automatic generating parameter method is mainly based on DDM to determine the parameters \(\varepsilon\) and _MinPts_, which makes full use of the dataset's own distribution characteristics. The DDM represents the matrix composed of the distances between each point in the dataset and other points [28]. The following is the introduction of parameter adaptive generation method based on DDM:  
Firstly, calculate the Euclidean distance [30] between the current point \(p_{i}(i=1,\;2,\ldots,N)\) and other \(N-1\) points in the point cloud slice dataset, and establish the distance feature vector \(D_{i}\)[31] (Equation (1)). The Euclidean distance \(D\big{(}p_{i},p_{j}\big{)}\) between two points \(p_{i}\) and \(p_{j}\) is shown in Equation (2):  
\[D_{i}=[D(p_{i},p_{1}),\;D(p_{i},p_{2}),\;\ldots,\;D(p_{i},p_{N})], \tag{1}\]  
\[D\big{(}p_{i},p_{j}\big{)}=\sqrt{\big{(}p_{i}\!:\!x-p_{j}\!:\!x\big{)}^{2}+ \big{(}p_{i}\!:\!y-p_{j}\!:\!y\big{)}^{2}+\big{(}p_{i}\!:\!z-p_{j}\!:\!z\big{)} ^{2}}(j=1,\;2,\ldots,N), \tag{2}\]  
Secondly, \(N\) elements of distance feature vector \(D_{i}\) corresponding to point \(p_{i}\) are arranged in ascending order to obtain ascending distance feature vector \(D_{s,i}\) of point \(p_{i}\) (\(s=1,\,2,\,\ldots,N\)). The value of the \(k\)th element in the ascending distance feature vector \(D_{s,i}\) represents the distance between point \(p_{i}\) and its \(k\)th neighbor. The point of the front element indicates that it is closer to point \(p_{i}\). The point of the back element indicates that it is farther from point \(p_{i}\). Then, calculate the ascending DDM \(D_{s}\) of all points in the dataset [28] (Equation (3)):  
\[D_{s}=\left[\begin{array}{cccc}D_{1,1}&D_{2,1}&\cdots&D_{N,1}\\ D_{1,2}&D_{2,2}&\cdots&D_{N,2}\\ \vdots&\vdots&\ddots&\vdots\\ D_{1,N}&D_{2,N}&\cdots&D_{N,N}\end{array}\right], \tag{3}\]  
Thirdly, the mean values of each column of the DDM \(D_{s}\) are calculated successively, which are used as \(N\) candidate values of neighborhood parameter \(\varepsilon\) of DBSCAN algorithm. Then, for each \(\varepsilon\) candidate value, calculate the sum of number of points in the \(\varepsilon\) neighborhood of all points in the dataset. Additionally, its average value is taken as the corresponding \(MinPts\) of the \(\varepsilon\) candidate value (Equation (4)):  
\[MinPts=\frac{\sum_{1}^{N}\lvert N_{\varepsilon}(p_{i})\rvert}{N}, \tag{4}\]  
Finally, \(N\) groups of parameters \(\varepsilon\) and \(MinPts\) are successively taken as input parameters of DBSCAN algorithm to obtain the cluster number corresponding to each group of parameters. With the increase in the parameter \(\varepsilon\), the number of clustering clusters decreases gradually. If the cluster number to the intermediate continuous multiple groups of parameters is the same, it is considered that the cluster number has the best adaptability, so it can be regarded as the optimal cluster number.  
The automatic generating parameter method does not need manual parameter tuning, which can avoid the interference of subjective factors in clustering results and reduce the error of artificial parameter setting. By calculating the distance feature vector between point \(p_{i}\) and other points in the dataset, the ascending distance matrix \(D_{s}\) of all points is established. This reflects the distribution characteristics of the dataset itself and makes the clustering process pay more attention to the data itself.