# Line Structure Extraction from LiDAR Point Cloud Based on the Persistence of Tensor Feature
## 3 Methodology
### Line Structure Extraction Based on the Discrete Morse Theory  
Suppose \(f:S(p)\to R\) is a smooth function on a manifold, and \(\left\{p,f(p)|p\in S\right\}\) can be taken as a smooth surface in 3D space. Besides, the gradient \(\
abla f(p)\) of the function \(f\) at point \(p\) is the direction \(f(p)\) decrease with the largest rate, and the integral line \(\iota\) on the manifold is defined as the maximal path passing through \(p\) whose vectors agree with gradient \(\
abla f(p)\). The start and end point of the integral line are critical points, which are non-degenerate and with gradient values \(\
abla f(p)=0\). In other words, the critical point can be the maxima, minima, or saddle. Hence, the 1-stable manifold \(\iota(p)\) of the critical point \(p\) can be expressed as the line structure whose integral line ends at \(p\) (i.e., the maxima). Intuitively, the 1-stable manifold can be taken as the ridge of the surface, where each point of 1-stable manifold is the local maxima if there is a line profile which is orthogonal to the direction of gradient direction of the point, as depicted in Figure 3.  
For the line structure extraction, line segments can be extracted with the local maximal line saliency value, i.e., the integral line starts from the saddle to the maxima (the black line in Figure 3), as denoted in Equation (11).  
\[\iota(p)=\left\{p\right\}\cup\left\{q\in S_{LCS}|dest(q)=p\right\} \tag{11}\]  
Using the discrete Morse theory, 1-stable manifold of the integral line can be encoded by the Morse-Smale complex, and the persistent geometric feature can be computed. Then 1-stable manifold \(\iota(p)\) starting from the saddle to the maxima can be extracted. To construct the Morse-Smale complex from the quality-unstable point cloud dataset, the \(LCS\) is further resampled by regular grid of space \(S\), and the new \(LCS^{\prime}\) is computed as follows:  
1. compute the bounding box of space \(S\), take the minimum edge as the referenced length, and divide it into \(\kappa\) sub-edges of equal length \(\tau\);
2. divide the edge of bounding box in other 2 dimensions using the length \(\tau\). Then, space \(S\) is divided into subspace \(\varsigma_{i}\) of equal size. Take the center position \(center(\varsigma_{i})\) of \(\varsigma_{i}\) as the coordinate of the point in \(LCS\) ;
3. compute the relation \(\varphi_{i}:\left\{p\left(x,y,z,s_{surface},s_{line},s_{point}\right)|p\in LCS \right\}\rightarrow\varsigma_{i}\) between the point \(p_{i}\) in \(LCS\) and the subspace \(\varsigma_{i}\), and take the point with the max line saliency as the new attribute for \(\varsigma_{i}\), as denoted in Equation (12);
4. count the number \(\delta_{i}\) of \(\varphi_{i}\) in each \(\varsigma_{i}\), and label \(\varsigma_{i}\) with \(\delta_{i}>0\) as the mask area \(\varsigma_{i}^{\prime}\) of mask space \(S^{\prime}=\left\{\varsigma_{i}^{\prime}|\delta_{i}>0\right\}\), for the computation of persistent homology.  
After the resample process, the Morse-Smale complex is constructed based on the discrete Morse theory, and the persistence of the geometric structure is computed. The line segment is extracted using the threshold \(\delta\), and line features with higher persistent value than \(\delta\) are preserved, i.e., \(\left\{p_{critical},l_{connection}\right\}=\left\{\iota(p)\middle|\varsigma_{i}(p)> \delta\right\}\). Finally, the graph is computed and the line structure \(\left\{\iota\right\}\) is constructed with connection information stored in the graph.  
Figure 3: 1-stable manifold of the critical point.