# Soft Segmentation of Terrestrial Laser Scanning Point Cloud of Forests
## 2 Data and Methods
### Soft Segmentation Algorithm
#### 2.2.3 Modified Hard Segmentation  
At first, the traditional hard segmentation algorithm is described in the following. After the rough segmentation, the next step is to detect the individual tree from the group points that have overlap regions with the neighboring tree crowns. Similar to the literature [33], the Delaunay graph is built with roots as sites, which can be used to search the neighboring trees. According to the Delaunay graph, we use the minimum cut plane to partition two neighbor trees. The first step is to partition points into vertical slices. Assuming that the thickness \(\Delta_{vb}\) of each slice is 0.2 m, then the number of slices \(N_{vb}\) is the quotient obtained by dividing the distance between \(C_{1}\) and \(C_{2}\) by \(\Delta_{vb}\), i.e.,  
\[N_{vb}=\frac{|C_{1}C_{2}|}{\Delta_{vb}}, \tag{1}\]  
where \(C_{1}\) and \(C_{2}\) are the roots of two adjacent trees. Figure 7a illustrates the method of generating slices along line \(C_{1}\) to \(C_{2}\). Note that the partition is performed in a 3D space, and the local coordinate system \(\left[C_{1};\ \overset{\longrightarrow}{C_{1}C_{2}}\ \overset{o}{,C_{1}Y},\ \overset{ \longrightarrow}{C_{1}Z}\right]\) has been built. In this coordinate system, \(\overset{\longrightarrow}{  
The second step is to find the optimal dividing line, which is defined by the minimum cut plane and can be obtained with the solution of the minimum-maximum optimal problem as follows:  
\[i^{*}=\underset{i}{\text{argmin}}\underset{j}{\text{min}}\left\{z_{j}|\forall p _{j}(z_{j},z_{j},z_{j})\in B_{i}\right\} \tag{2}\]  
For convenient application, the optimal segment place series number \(i^{*}\) is transformed to the distance \(d^{*}\), as follows:  
\[d^{*}=\left\langle\Delta_{vb}\cdot i^{*}\right\rangle \tag{3}\]  
In Equation (3), symbol \(\left\langle x\cdot y\right\rangle\) is the inner product of vectors \(x\) and \(y\). In this way, the problem of judging which side of a plane any point lies on is transformed into judging based on the projection distance along the direction \(\overset{\longrightarrow}{\text{C}_{1}\text{C}_{2}}^{\text{ \  
2.2.4. Refined by KNN and Contour Constraints  
To determine which tree these points at the pending region belong to, three steps are proposed as follows. Figure 8: The individual tree identification with the hard segmentation. The three vertices of the black triangle show the positions of three roots. (**a**) The segmentation result of Forest B; (**b**) the top view of (**a**). Figure 10: Key steps and results of refined segmentation. (**a**) Generating horizontal layers; (**b**) building the contours of all layers; (**c**) refining by KNN and contour constraints; (**d**) one representative layer of (**b**); (**e**) refined contour and classification of (**d**). Figure 9: The pending region is introduced to the hard segmentation algorithm. Step 1: Generating horizontal layers. Given that the overlap of adjacent crowns only occurs at some layers, the forest point cloud can be segmented in a horizontal direction. The thickness of each layer is a constant number, for example, 0.4 m. The experimental result is shown in Figure 10a. Step 2: Build the contours of all layers. Based on the results of modified hard segmentation and the generation of horizontal layers, the contour curve of each layer in every initial individual tree point cloud can be constructed using the 2D alpha-shape method [34], as shown in Figure 10b. This initial contour, used as the boundary of partitioning individual trees, has more options than the constraints resulting only from the contour generated by projecting points onto the ground. Step 3: Refining by KNN and contour constraints. For these unlabeled regions, an approximate K-Nearest Neighbor (KNN) algorithm [35] is employed to label some unclassified points. For an unclassified point \(p_{i}\) in the pending region, as the dashed black circle shown in Figure 10c, the classifying rule is as follows:  
\[L(p_{i})=\left\{