# A Radar Linear Feature Fitting Algorithm Combining Adaptive Clustering and Corner Detection Operator

Authors: Yiting Liu; Lianjie Sui; Peijuan Li; Lei Zhang; Qingzheng Wu; Junfeng Du; Yawen Liu; Hanqi Yu
Journal: Journal of Sensors
 (2023)

---

## Abstract

The precise environmental parameters derived from laser radar scan data can significantly accelerate the process of real-time localization and map-matching technique. One of the research directions is autonomous navigation algorithm based on LiDAR slam. LiDAR has the advantage of having a wide range of accuracy and distance. However, due to the limited amount of LiDAR data available and the influence of sensor noise, it is easy to run into issues such as low accuracy of robot map construction or large positioning errors. At the moment, most of feature extraction algorithms employ an iterative calculation method with high computational complexity and a large amount of computation. Furthermore, due to the dependence of the fixed separation threshold, the algorithms for extracting the linear features of laser radar data are typically undersegment and oversegment. As a result, this paper proposes a radar linear feature fitting algorithm that combines adaptive clustering and corner detection operators. First, bilateral filtering is used to reduce noise and remove invalid data points. Second, the LiDAR data points are classified using adaptive threshold clustering of distance and density. The corner detection operator is applied to the classified data points to determine all possible corners then. Finally, the least square method is used to linearly fit each class and the identified corners within each class. The simulation and experimental results demonstrate that this method avoids the influence of noise points and a fixed segmentation threshold on corner point extraction effectively. The standard variance of length is9.41×10−5m2 for corner feature extraction and localization in the dataset Cartographer ROS 2D Laser SLAM at Deutsches Museum. When compared to PDBS (point distance based methods) and IEPF (iterative end point fit), only about half the time is used, the accuracy of partition processing is improved by 11.6%, and the accuracy of corner detection is improved by 20.1%. The proposed algorithm can extract the corner features of data frames and linear positioning through experimental verification accurately. The features of the laser scan data that fit are more realistic. It has higher calculation efficiency and position accuracy. It ensures real-time mobile robot map construction and is appropriate for autonomous robot map algorithms developed in embedded systems.


---

## Body

## 1. Introduction

Environmental perception is an embodiment of mobile robot intelligence that plays a critical role in mobile robot application [1, 2]. Laser radar is a common piece of equipment for mobile robot environmental perception for its high efficiency, low cost, and broad applicability [3]. However, laser radar is sensitive to light. Due to feature degradation, positioning accuracy will be reduced in a single environment [4]. The environmental features with a specific geometric configuration are extracted by processing the feature points, which can improve the positioning ability and system robustness effectively [5].For corner recognition, Duo and Zhao suggested a microscope image segmentation technique based on Harris multiscale corner detection for the purpose of visual corner recognition. Incorporating the concept of multiresolution analysis, creating a formula for gray intensity change based on wavelet transform, and determining the properties of the scale transform enable the improved Harris corner detection algorithm to be scale, rotation, and translation invariant [6]. Huang suggested a brand-new coarse to fine corner extractor to accurately and effectively extract corner events. A data association approach with spatial, temporal, and velocity direction restrictions is used to track corner events, and the most recent active corner in the vicinity that satisfies the velocity direction criteria is connected with the newly arriving corner event [7]. For point cloud data processing, Chen et al. used density-based clustering with the normal vector of a point cloud (rather than the point cloud itself) to extract the common part for further registration. Multicamera correlation is achieved through local and global calibration, followed by filtering and stitching to obtain the global point cloud after filtering. The proposed point cloud processing algorithm is applicable to a wide range of targets and is self-adaptive under dynamic conditions [8]. A cutting plane-based cylindrical fitting method was put out by Yu et al. for partial point cloud data. First, a bilateral filtering method is used to analyze the point cloud in order to lessen the impact of outliers and noisy points. The precision of the cylindrical point cloud fitting is then increased by choosing the isometric cutting plane of the point cloud, using the edge points on the cutting plane for ellipse fitting and the ellipse center point clustering for situating the cylindrical axis based on RANSAC algorithm [9].The linear feature is widely acknowledged as an important aspect of mobile robot environment perception. The extraction of linear features is divided into two steps: region segmentation and feature extraction [10]. The classification and identification of feature patterns are mostly completed during the regional segmentation stage. Straight lines, arcs, and other feature patterns are determined, and laser data points within the feature pattern region are determined. Feature extraction completes feature pattern parameter and feature point extraction primarily [11, 12]. The commonly used line feature extraction algorithms are Hough transform, LT (line tracking), PDBS (point distance based method), IEPF (iterative end point fit), and so on. The Hough transform method first converts line features from Cartesian to Polar coordinate systems before counting the number of curves at intersections in polar coordinates. The curves are only marked as a line feature when they reach a specific valve. The disadvantage of this method is the extensive computation required [13]. According to the line tracking criterion, the LT algorithm determines whether the subsequent detected points and the previous detected points are in the same line. The drawback of this method is that the extracted segment lacks integrity and has significant errors [14]. PDBS is primarily based on the distance between two adjacent LIDAR points in rectangular coordinates when compared to the setting threshold. When the distance between two points exceeds the threshold, it is assumed that they belong to different regions. The threshold used in this method has a significant impact on the segmentation of line segments. It is easy to oversegment if the threshold is too low. If the threshold is set too high, there will be under segmentation and segmentation failure at the corner [15–17]. The point set is first fitted as a straight line in the IEPF algorithm, and then it is segmented and fitted by judging the relationship of the distance between the point and the straight line with the set threshold [18, 19]. Although this method performs better, it is sensitive to the threshold choice, and line feature extraction might lead to over- or undersegmentation [20].In conclusion, while there are numerous methods for extracting features from laser radar scan points, there is a scarcity of efficient, simple, and accurate algorithms [21]. As a result, based on the characteristics of laser radar scanning, this paper proposes a linear fitting algorithm based on the least square method for extracting noise points and corner features from laser radar scanning data directly. The influence of noise points outside the region and corner threshold selection on this algorithm is greatly reduced.The remainder of this paper is organized as follows: the second section focuses on radar sensor data modeling and noise processing. The third section primarily introduces the adaptive clustering method based on distance and density, the primary corner determination method, the corner detection operator calculation method, and least squares fitting linear features. The fourth section describes the algorithm’s basic flow. The fifth section of the paper introduces the processing of the actual environment, then compares experiments with PDBS and IEPF algorithms, and analyzes the data of this algorithm in the dataset Cartographer ROS 2D Laser SLAM at Deutsches Museum. The sixth section summarizes the flaws of the IEPF and PDBS algorithms as well as the main contributions of this algorithm.


## 2. LiDAR Data Processing

The environment and device characteristics influence the sensor’s measurement accuracy. The laser radar noise interference will result in some isolated points in the data, but this is not the real observation data, which will affect the algorithm results and should be filtered in advance [22]. As a result, denoising the raw data of radar scanning is required to reduce the influence of noise information on line segment feature extraction and improve mapping accuracy [23]. Additionally, the extremely discrete data points that are acquired when the laser radar gathers remote environmental data cause an increase in inaccuracy, an uneven distribution of the scanned points, and a fitting line segment that is very different from the actual environment.


### 2.1. Laser Radar Data Modeling

The distance data received after scanning an obstruction makes up the raw LiDAR data. In this study, the LiDAR modeling processing is based on the returned distance information along with the LiDAR resolution, which is used to calculate the horizontal and vertical coordinate values of each LiDAR scanning point in the plane Cartesian coordinate system and express the model of all LiDAR scanning points in each frame. Figure1 depicts the laser radar scanning angle range coordinate system. φi represents the angle value, expressed in rad, for the ith coordinate point in the Cartesian coordinate system. xi indicates the value of the LiDAR coordinate point’s horizontal coordinate; the unit is m. yi indicates the coordinate point’s ordinate value, and the unit is m. Zt expresses in a plane’s Cartesian coordinate system the coordinates of a LiDAR point. When configuring the laser radar parameters, this paper uses the default value. The scanning angle is 160°, with an angle resolution of 0.33°. The measurement’s initial angle is -80°, and its final angle is 80°. Every 0.33°, the LiDAR outputs a value starting at the initial angle.Figure 1
Definition of LiDAR angle.This is how each beam angle is expressed:(1)φi=−80°+0.33i−1·π180=−80.33°+0.33i∙π180,1≤i≤N.In the formula,i is the serial number of LiDAR return data.The original laser point cloud data are written as follows in Polar coordinates:(2)ri=ρi,φi,φi∈−49π,49π.In the formula,i is the serial number of LiDAR return data, ρi represents the angle of laser beam i in Cartesian coordinate system, and φi represents the distance from the reflecting point to the transmitting point measured by the laser beam i.This method is completed in Cartesian coordinate system, and the original data converted to Cartesian coordinate system are expressed as follows:(3)Pi=ρicosφi,ρisinφi=xi,yi,1≤i≤n.In the formula,i is the serial number of lidar return data, ρi represents the angle of laser beam 0i in Cartesian coordinate system, φi represents the distance from the reflecting point to the transmitting point measured by the laser beam i, xi represents the horizontal coordinate value of laser beam i in the plane rectangular coordinate system, and yi represents the vertical coordinate value of laser beam i in the plane rectangular coordinate system.A set of points representing the scanning characteristics of each frame of the LiDAR laser beam can be obtained by calculating the horizontal and vertical coordinates of the LiDAR scanning points in the Cartesian coordinate system. The point set can clearly judge the breakpoint feature of the inconsistent obstacle contour’s edge point, the corner point feature of the obstacle’s intersection point of two straight lines, and the noise feature of the distorted data point affected by noise.


### 2.2. Noise Point Processing

Point cloud data must be preprocessed in order to increase measurement accuracy as sensor noise, environmental noise, and laser reflectance of objects all affect the performance of LiDAR. To remove noise and safeguard the image’s edge, pretreatment is necessary. LiDAR noise is mostly realized as nonlinear noise, and typical filtering techniques often include wavelet transform, bilateral filtering, and median filtering [24]. Bilateral filtering is chosen in this article because it has the properties of nonlinearity, noise suppression, data smoothing, and superior edge protection compared to other filtering methods.The definition of a bilateral filtering method is(4)Ifilteredx=1WP∑xi∈ΩIxifrIxi−Ixgsxi−x.The weightWp is defined as
(5)WP=∑xi∈ΩfrIxi−Ixgsxi−x.In formula (4), Ifilteredx represents the scanning point distance value of the current filtering, Ω represents the current window area, xi represents the position of the scan points in the window despite the window center, Ixi represents the corresponding distance value, fr represents the kernel function of intensity difference in the smooth range, and gs represents the kernel function for smoothing spatial domain differences. The kernel function in the range and space domain in this study is the Gaussian function.
(6)ωdi,j,k,l=exp−i−k2+j−l22σd2,(7)ωri,j,k,l=exp−fi,j−fk,l22σr2.Weight of each scan point:(8)ωi,j,k,l=ωd·ωr=exp−i−k2+j−l22σd2fi,j−fk,l22σr2.In formula (8), σd represents the kernel function variance in the space domain, σr represents the variance of range kernel function, and in this paper, their values take 4 and 0.3, respectively.After normalizing equation (8), it can be obtained:
(9)IDi,j=∑k,lIk,lωi,j,k,l∑k,lωi,j,k,l.In formula (9), ID represents the filtered scan point. The scan spots will be filtered by repeating the aforementioned procedure.According to Figure2, position pi−1 represents the end of line L1, and point pi+1 represents the beginning of line L2. The center contains the noise point pi. The blue line in Figure 3 depicts the distribution of distances at point pi. This point is a noise point because the distance between it and the two points before and after changes significantly. The noise points will be wrongly labeled as corners when extracting corners if the noise points are not filtered first. After filtering, the laser radar data points are smoother, and the line features are more in line with the actual environment, as indicated by the red line in Figure 3 when the distance between adjacent two data points is smaller than the threshold of ε=0.015.Figure 2
The model of noise point.Figure 3
The pretreatment of noise point.


## 2.1. Laser Radar Data Modeling

The distance data received after scanning an obstruction makes up the raw LiDAR data. In this study, the LiDAR modeling processing is based on the returned distance information along with the LiDAR resolution, which is used to calculate the horizontal and vertical coordinate values of each LiDAR scanning point in the plane Cartesian coordinate system and express the model of all LiDAR scanning points in each frame. Figure1 depicts the laser radar scanning angle range coordinate system. φi represents the angle value, expressed in rad, for the ith coordinate point in the Cartesian coordinate system. xi indicates the value of the LiDAR coordinate point’s horizontal coordinate; the unit is m. yi indicates the coordinate point’s ordinate value, and the unit is m. Zt expresses in a plane’s Cartesian coordinate system the coordinates of a LiDAR point. When configuring the laser radar parameters, this paper uses the default value. The scanning angle is 160°, with an angle resolution of 0.33°. The measurement’s initial angle is -80°, and its final angle is 80°. Every 0.33°, the LiDAR outputs a value starting at the initial angle.Figure 1
Definition of LiDAR angle.This is how each beam angle is expressed:(1)φi=−80°+0.33i−1·π180=−80.33°+0.33i∙π180,1≤i≤N.In the formula,i is the serial number of LiDAR return data.The original laser point cloud data are written as follows in Polar coordinates:(2)ri=ρi,φi,φi∈−49π,49π.In the formula,i is the serial number of LiDAR return data, ρi represents the angle of laser beam i in Cartesian coordinate system, and φi represents the distance from the reflecting point to the transmitting point measured by the laser beam i.This method is completed in Cartesian coordinate system, and the original data converted to Cartesian coordinate system are expressed as follows:(3)Pi=ρicosφi,ρisinφi=xi,yi,1≤i≤n.In the formula,i is the serial number of lidar return data, ρi represents the angle of laser beam 0i in Cartesian coordinate system, φi represents the distance from the reflecting point to the transmitting point measured by the laser beam i, xi represents the horizontal coordinate value of laser beam i in the plane rectangular coordinate system, and yi represents the vertical coordinate value of laser beam i in the plane rectangular coordinate system.A set of points representing the scanning characteristics of each frame of the LiDAR laser beam can be obtained by calculating the horizontal and vertical coordinates of the LiDAR scanning points in the Cartesian coordinate system. The point set can clearly judge the breakpoint feature of the inconsistent obstacle contour’s edge point, the corner point feature of the obstacle’s intersection point of two straight lines, and the noise feature of the distorted data point affected by noise.


## 2.2. Noise Point Processing

Point cloud data must be preprocessed in order to increase measurement accuracy as sensor noise, environmental noise, and laser reflectance of objects all affect the performance of LiDAR. To remove noise and safeguard the image’s edge, pretreatment is necessary. LiDAR noise is mostly realized as nonlinear noise, and typical filtering techniques often include wavelet transform, bilateral filtering, and median filtering [24]. Bilateral filtering is chosen in this article because it has the properties of nonlinearity, noise suppression, data smoothing, and superior edge protection compared to other filtering methods.The definition of a bilateral filtering method is(4)Ifilteredx=1WP∑xi∈ΩIxifrIxi−Ixgsxi−x.The weightWp is defined as
(5)WP=∑xi∈ΩfrIxi−Ixgsxi−x.In formula (4), Ifilteredx represents the scanning point distance value of the current filtering, Ω represents the current window area, xi represents the position of the scan points in the window despite the window center, Ixi represents the corresponding distance value, fr represents the kernel function of intensity difference in the smooth range, and gs represents the kernel function for smoothing spatial domain differences. The kernel function in the range and space domain in this study is the Gaussian function.
(6)ωdi,j,k,l=exp−i−k2+j−l22σd2,(7)ωri,j,k,l=exp−fi,j−fk,l22σr2.Weight of each scan point:(8)ωi,j,k,l=ωd·ωr=exp−i−k2+j−l22σd2fi,j−fk,l22σr2.In formula (8), σd represents the kernel function variance in the space domain, σr represents the variance of range kernel function, and in this paper, their values take 4 and 0.3, respectively.After normalizing equation (8), it can be obtained:
(9)IDi,j=∑k,lIk,lωi,j,k,l∑k,lωi,j,k,l.In formula (9), ID represents the filtered scan point. The scan spots will be filtered by repeating the aforementioned procedure.According to Figure2, position pi−1 represents the end of line L1, and point pi+1 represents the beginning of line L2. The center contains the noise point pi. The blue line in Figure 3 depicts the distribution of distances at point pi. This point is a noise point because the distance between it and the two points before and after changes significantly. The noise points will be wrongly labeled as corners when extracting corners if the noise points are not filtered first. After filtering, the laser radar data points are smoother, and the line features are more in line with the actual environment, as indicated by the red line in Figure 3 when the distance between adjacent two data points is smaller than the threshold of ε=0.015.Figure 2
The model of noise point.Figure 3
The pretreatment of noise point.


## 3. Feature Extraction and Line Fitting

### 3.1. Adaptive Threshold Clustering Based on Distance and Density

The same object surface will reflect back a continuous series of points in a frame of point cloud data, and the locations of these data points are adjacent [25]. When two neighboring points’ positions abruptly change, it typically indicates that the two points originate from two distinct object surfaces or portions. To determine whether two points belong to the same class or not, the position mutation of two neighboring points might be employed [26]. In this paper, an adaptive threshold clustering method based on range and density is proposed. It is based on the adaptive range and the properties of radar point density. Determine whether the result is smaller than a linear threshold dth by first calculating the distance di,i−1 between the current point and the prior point. Radar’s range resolution threshold serves as the foundation for establishing the linear threshold dth. The scanning angular resolution of the LiDAR is φs, as seen in Figure 4. The data that the LiDAR scanned on the object’s surface is indicated in point P1 to P8. The measurement distance affects the distance between adjacent points, and the distance between adjacent points P1P2 in the figure is bigger than P5P6 in the figure.Figure 4
LiDAR scanning modeling.The linear thresholddth is established as follows:
(10)dth=απφs180maxdi−1,di.In formula (10), di−1,di represents the radar ranging value of two adjacent points, maxdi−1,di represents selecting the point with larger distance measurement in the adjacent point, and α represents the adaptive scaling coefficient.The two points belong to the same class if the distancedi,i−1 between the current point, and the previous point is less than the linear threshold. If it is more than the linear threshold, the density mean of the classes prior to the present location is determined. The density of the current point has changed significantly and does not belong to the same object if the difference di,i−1 between the density mean of the class, and the standard deviation of the class is significantly greater than the standard deviation of the class. Otherwise, the two points belong to different classes.The density thresholdρth is established as follows:
(11)μk=1m∑i=1mdi,i−1,m=numCk,i∈Ck,(12)σk=1m∑i=1mdi,i−1−μk2,(13)ρth=μk+ασk.In formula (11)–(13), Ck represents point set of class K, μk represents the mean density of class K, and σk represents the density standard deviation of class K.As seen in Figure5, the original data will appear chaotic when the laser radar scanning data collides with objects with rich levels. Direct feature fitting or feature extraction will be extremely important in this situation. The scanning points that were scanned on various obstacles will be grouped using the adaptive distance clustering approach based on distance and density, which can clearly depict the hierarchical information of each obstacle. Corner points from the scanning data can be retrieved in accordance with several obstacle categories, which can improve corner extraction accuracy and make the fitted obstacle information more realistic.Figure 5
Real point cloud clustering rendering.
(a)
Radar raw data(b)
Adaptive radar data clustering


### 3.2. Corner Feature Extraction Based on Corner Detection Operator

Discrete points are clustered into distinct points using the adaptive clustering method based on distance and density after laser radar scanning. Each point column contains both corner and linear features [27]. As a result, each point column’s corner features are obtained after clustering in this research by using the corner detection operator to identify the principal corners.


#### 3.2.1. Primary Corners

As seen in Figure6, draw a straight line L1 connecting the first point p1 and the last point pn. Then, from all points (from p2 to pn−1), save the first and last, and compute the distance Di to line L1.Figure 6
Primary corners.The distanceL between the point and the straight line can be determined by computing the projection point of the point on the straight line since the coordinates of the point and the straight line expression are known.
(14)L=yp1−ypnxpi+xpn−xp1ypi+xp1ypn−yp1xpnyp1−ypn2+xp1−xpn2.In formula (14), xp1 and yp1 are the coordinates of the starting point p1, respectively, xpn and ypn are coordinates of the end point pn, respectively, and xpi and ypi are coordinates of any point pi, respectively.Determine the location that is furthest from the line and then designate that location as the main corner. The second farthest point can then be discovered by using this location as the starting point for the subsequent cycle. Until all primary corners in the laser scanning data points are located, repeat the aforementioned processes.


#### 3.2.2. Corner Detection Operator

There is a certain “proportional” relationship between the curvature of the origin and the distance between the point near the origin on the parabola and the transverse coordinate axis (the tangent of the parabola at the origin) for a parabola whose opening is upward and tangent to the origin in the plane rectangular coordinate system [28]. The smaller the opening (the greater the curvature of the origin), the greater the distance between the point near the origin and the transverse coordinate axis.An illustration of how to calculate the cumulative distance from a point to a tangent is shown in Figure7. The y=5x2, x∈−1,1 function’s curve is depicted by the solid red line. Additionally, the curve of the function y=x2, x∈−1,1 is shown by the solid blue line. Assuming that x0>0 and x0,0 are points on the tangent line close to the origin, the straight line x=x0 that crosses point x0,0 and perpendicular to tangent y=0 encounters points x0,5x02 and x0,x02 with functions y=5x2 and y=x2, respectively. The radius of the support domain n is defined as the number of radar scanning data points on the left and right sides of the tangent point. The point column xi+j,yi+ji=−nn is the point pixi,yi radius of n support domain.Figure 7
Calculation of cumulative distance from point to tangent.Two arc-length parameter coordinate point columns depending on the arc length parameterize the position coordinate point column in the support domain. In this instance, two pairs of target arc-length parameter coordinates parameterize the target point (horizontal and vertical coordinates) (arc length and abscissa and arc length and ordinate).The arc length parameterization function is(15)si=0si+j=si+j−1+xi+j−xi+j−12+yi+j−yi+j−12,j=1,⋯,n,si+j−1−xi+j+1−xi+j2+yi+j+1−yi+j2,j=−1,⋯,−n.The two coordinate point columns for the two arc-length parameters,si+j,xi+ji=−nn and si+j,yi+ji=−nn, respectively, are fitted by two curves. If xs=α0+α1s+α2s2 is the fitting function; then, α=α0,α1,α2 and β=β0,β1,β2 need to be determined are the indeterminate coefficients. Determine the coefficient α and β, which make xs and ys the solutions of the point set in the least squares fitting sense, respectively. Because of the arc length parameterization si=0 and fulfill xsi=xi and ysi=yi, we may obtain that xs=xi+α1s+α2s2.
(16)fα1,α2=∑j=−n,j≠0nxsi+j−xi+j=∑j=−n,j≠0nα1si+j+α2si+j2+xi−xi+j2.Set the value of the functionα1,α2’s first partial derivative with respect to the variable α1 and α2 to 0.
(17)∂f∂α1=0∂f∂α2=0=>α1∑j=−n,j≠0nsi+j2+α2∑j=−n,j≠0nsi+j3=∑j=−n,j≠0nsi+jxi+j−xi,α1∑j=−n,j≠0nsi+j2+α2∑j=−n,j≠0nsi+j4=∑j=−n,j≠0nsi+j2xi+j−xi.Then(18)α1A11+α2A12=B1,α1A21+α2A22=B2,(19)α1=A22B1−A12B2A11A22−A12A21.We can obtainẋs=α1+α2s by xs=α0+α1s+α2s2. As a result, ẋss=si=ẋ0=α1 is the function xs’s first derivative at the target parameter point s=si=0. Similar to this, the function ys’s first derivative at the target parameter point s=si=0 is ẏss=si=ẏ0=β1.The schematic representation of the target point’s laser radar scanning points is shown in Figure8(a). As seen in Figures 8(b) and 8(c), two arc-length parameter coordinate points are created by parameterizing the points at the target point on the abscissa and ordinate, respectively. These coordinate points are designated as si+j,xi+ji=−nn and si+j,yi+ji=−nn accordingly. The two coordinate points for the arc length parameter are then fitted to produce Figures 8(d) and 8(e). Finally, as shown in Figure 8(f), the tangent direction at the target point is determined using the values of α1 and β1 obtained by fitting two arc length parameter points.Figure 8
Schematic diagram of solving the tangent line at the target point.Consequently, the tangent equation through pointpixi,yi is
(20)l:x1t=xi+tα1y1t=yi+tβ1,t∈R.In formula (20), α1 and β1 are the direction vectors of the tangent at pi, and xi and yi are the abscissa and ordinate values of pi.Any pointxi+j,yi+j in the point column xi+j,yi+ji=−nn and the tangent line L are separated by the following distance:
(21)di+j=β1xi+j−xi−α1yi+j−yiα12+β12.In formula (21), α1 and β1 are the direction vectors of the tangent at pi, xi and yi are the abscissa and the ordinate values of pi, and xi+j and yi+j are the abscissa and ordinate values of the point whose length is the radius of the support domain at point pi .Then, the corner response function from the point to the tangent is the cumulative sum of the distance from the point columnxi+j,yi+ji=−nn to the tangent line l:
(22)T=∑j=−n,j≠0ndi+j=∑j=−n,j≠0nβ1xi+j−xi−α1yi+j−yiα12+β12.In formula (22), di+j is the distance from any point xi+j,yi+j of the point column xi+j,yi+ji=−nn to tangent L.According to Figure9(a), the average repetition rate (the average value of the ratio of angle points to actual angle points is frequently detected after changing the direction of the radar data) increases with the support domain’s radius. The average repetition rate reaches a maximum and then starts to fall when the support domain’s radius is 6. As can be observed, a support domain with an excessively high radius will fuse the corners of diagonal points with equal distances. According to Figure 9(b), the average repetition rate reaches its greatest value at the corner detection operator’s threshold of T=0.66, and oscillation variation is minimal at the maximum point. It is demonstrated that the corner detection operator created by multiplying the total distance between a point and both a chord and a tangent has a high level of robustness. Through the foregoing discussion, it has been found that the threshold size is T=0.66 and that the radius of the support domain is chosen to be 6.Figure 9
Line chart of average repetition rate.
(a)
Average repetition rate distribution of different support domain radius under fixed corner detection operator threshold 0.66(b)
Fixed support domain radius 6, different corner detection average repetition rate distribution of operator domain values


### 3.3. Linear Fitting

By scanning the surrounding area with laser radar, discrete point sets can be obtained [29]. In this research, bilateral filtering is used to smooth the data for the abrupt noise points in the discrete point collection. After the filtered cluttered point set is clustered using adaptive clustering based on distance and density, each point set’s corners are detected using an operator-based approach. After corner detection and clustering, point sets require a linear fitting technique. In this study, linear fitting is done using the least squares method [30].Given a two-dimensional data point columnx1,y1,x2,y2,⋯,xn,yn, the mathematical model of linear fitting is set as y=kx+b. The parameters in the model are calculated using the residual ei=yi−kxi−bi=1,2,3⋯,n. Equation about parameters k and b with the minimum square sum of residual Q=∑i=1nei2=∑i=1nyi−kxi−b2 is taken into account.
(23)∑i=1n2yi−kxi−b×−xi=0,1≤i≤n,(24)∑i=1n2yi−kxi−b×−1=0,1≤i≤n.The fitted line can then be written as(25)y=kx+b=2∑i=1nxiyi−∑i=1nxi×∑i=1nyi2∑i=1nxi2−∑i=1nxi×∑i=1nxix+∑i=1nyi−k∑i=1nxi2.


## 3.1. Adaptive Threshold Clustering Based on Distance and Density

The same object surface will reflect back a continuous series of points in a frame of point cloud data, and the locations of these data points are adjacent [25]. When two neighboring points’ positions abruptly change, it typically indicates that the two points originate from two distinct object surfaces or portions. To determine whether two points belong to the same class or not, the position mutation of two neighboring points might be employed [26]. In this paper, an adaptive threshold clustering method based on range and density is proposed. It is based on the adaptive range and the properties of radar point density. Determine whether the result is smaller than a linear threshold dth by first calculating the distance di,i−1 between the current point and the prior point. Radar’s range resolution threshold serves as the foundation for establishing the linear threshold dth. The scanning angular resolution of the LiDAR is φs, as seen in Figure 4. The data that the LiDAR scanned on the object’s surface is indicated in point P1 to P8. The measurement distance affects the distance between adjacent points, and the distance between adjacent points P1P2 in the figure is bigger than P5P6 in the figure.Figure 4
LiDAR scanning modeling.The linear thresholddth is established as follows:
(10)dth=απφs180maxdi−1,di.In formula (10), di−1,di represents the radar ranging value of two adjacent points, maxdi−1,di represents selecting the point with larger distance measurement in the adjacent point, and α represents the adaptive scaling coefficient.The two points belong to the same class if the distancedi,i−1 between the current point, and the previous point is less than the linear threshold. If it is more than the linear threshold, the density mean of the classes prior to the present location is determined. The density of the current point has changed significantly and does not belong to the same object if the difference di,i−1 between the density mean of the class, and the standard deviation of the class is significantly greater than the standard deviation of the class. Otherwise, the two points belong to different classes.The density thresholdρth is established as follows:
(11)μk=1m∑i=1mdi,i−1,m=numCk,i∈Ck,(12)σk=1m∑i=1mdi,i−1−μk2,(13)ρth=μk+ασk.In formula (11)–(13), Ck represents point set of class K, μk represents the mean density of class K, and σk represents the density standard deviation of class K.As seen in Figure5, the original data will appear chaotic when the laser radar scanning data collides with objects with rich levels. Direct feature fitting or feature extraction will be extremely important in this situation. The scanning points that were scanned on various obstacles will be grouped using the adaptive distance clustering approach based on distance and density, which can clearly depict the hierarchical information of each obstacle. Corner points from the scanning data can be retrieved in accordance with several obstacle categories, which can improve corner extraction accuracy and make the fitted obstacle information more realistic.Figure 5
Real point cloud clustering rendering.
(a)
Radar raw data(b)
Adaptive radar data clustering


## 3.2. Corner Feature Extraction Based on Corner Detection Operator

Discrete points are clustered into distinct points using the adaptive clustering method based on distance and density after laser radar scanning. Each point column contains both corner and linear features [27]. As a result, each point column’s corner features are obtained after clustering in this research by using the corner detection operator to identify the principal corners.


### 3.2.1. Primary Corners

As seen in Figure6, draw a straight line L1 connecting the first point p1 and the last point pn. Then, from all points (from p2 to pn−1), save the first and last, and compute the distance Di to line L1.Figure 6
Primary corners.The distanceL between the point and the straight line can be determined by computing the projection point of the point on the straight line since the coordinates of the point and the straight line expression are known.
(14)L=yp1−ypnxpi+xpn−xp1ypi+xp1ypn−yp1xpnyp1−ypn2+xp1−xpn2.In formula (14), xp1 and yp1 are the coordinates of the starting point p1, respectively, xpn and ypn are coordinates of the end point pn, respectively, and xpi and ypi are coordinates of any point pi, respectively.Determine the location that is furthest from the line and then designate that location as the main corner. The second farthest point can then be discovered by using this location as the starting point for the subsequent cycle. Until all primary corners in the laser scanning data points are located, repeat the aforementioned processes.


### 3.2.2. Corner Detection Operator

There is a certain “proportional” relationship between the curvature of the origin and the distance between the point near the origin on the parabola and the transverse coordinate axis (the tangent of the parabola at the origin) for a parabola whose opening is upward and tangent to the origin in the plane rectangular coordinate system [28]. The smaller the opening (the greater the curvature of the origin), the greater the distance between the point near the origin and the transverse coordinate axis.An illustration of how to calculate the cumulative distance from a point to a tangent is shown in Figure7. The y=5x2, x∈−1,1 function’s curve is depicted by the solid red line. Additionally, the curve of the function y=x2, x∈−1,1 is shown by the solid blue line. Assuming that x0>0 and x0,0 are points on the tangent line close to the origin, the straight line x=x0 that crosses point x0,0 and perpendicular to tangent y=0 encounters points x0,5x02 and x0,x02 with functions y=5x2 and y=x2, respectively. The radius of the support domain n is defined as the number of radar scanning data points on the left and right sides of the tangent point. The point column xi+j,yi+ji=−nn is the point pixi,yi radius of n support domain.Figure 7
Calculation of cumulative distance from point to tangent.Two arc-length parameter coordinate point columns depending on the arc length parameterize the position coordinate point column in the support domain. In this instance, two pairs of target arc-length parameter coordinates parameterize the target point (horizontal and vertical coordinates) (arc length and abscissa and arc length and ordinate).The arc length parameterization function is(15)si=0si+j=si+j−1+xi+j−xi+j−12+yi+j−yi+j−12,j=1,⋯,n,si+j−1−xi+j+1−xi+j2+yi+j+1−yi+j2,j=−1,⋯,−n.The two coordinate point columns for the two arc-length parameters,si+j,xi+ji=−nn and si+j,yi+ji=−nn, respectively, are fitted by two curves. If xs=α0+α1s+α2s2 is the fitting function; then, α=α0,α1,α2 and β=β0,β1,β2 need to be determined are the indeterminate coefficients. Determine the coefficient α and β, which make xs and ys the solutions of the point set in the least squares fitting sense, respectively. Because of the arc length parameterization si=0 and fulfill xsi=xi and ysi=yi, we may obtain that xs=xi+α1s+α2s2.
(16)fα1,α2=∑j=−n,j≠0nxsi+j−xi+j=∑j=−n,j≠0nα1si+j+α2si+j2+xi−xi+j2.Set the value of the functionα1,α2’s first partial derivative with respect to the variable α1 and α2 to 0.
(17)∂f∂α1=0∂f∂α2=0=>α1∑j=−n,j≠0nsi+j2+α2∑j=−n,j≠0nsi+j3=∑j=−n,j≠0nsi+jxi+j−xi,α1∑j=−n,j≠0nsi+j2+α2∑j=−n,j≠0nsi+j4=∑j=−n,j≠0nsi+j2xi+j−xi.Then(18)α1A11+α2A12=B1,α1A21+α2A22=B2,(19)α1=A22B1−A12B2A11A22−A12A21.We can obtainẋs=α1+α2s by xs=α0+α1s+α2s2. As a result, ẋss=si=ẋ0=α1 is the function xs’s first derivative at the target parameter point s=si=0. Similar to this, the function ys’s first derivative at the target parameter point s=si=0 is ẏss=si=ẏ0=β1.The schematic representation of the target point’s laser radar scanning points is shown in Figure8(a). As seen in Figures 8(b) and 8(c), two arc-length parameter coordinate points are created by parameterizing the points at the target point on the abscissa and ordinate, respectively. These coordinate points are designated as si+j,xi+ji=−nn and si+j,yi+ji=−nn accordingly. The two coordinate points for the arc length parameter are then fitted to produce Figures 8(d) and 8(e). Finally, as shown in Figure 8(f), the tangent direction at the target point is determined using the values of α1 and β1 obtained by fitting two arc length parameter points.Figure 8
Schematic diagram of solving the tangent line at the target point.Consequently, the tangent equation through pointpixi,yi is
(20)l:x1t=xi+tα1y1t=yi+tβ1,t∈R.In formula (20), α1 and β1 are the direction vectors of the tangent at pi, and xi and yi are the abscissa and ordinate values of pi.Any pointxi+j,yi+j in the point column xi+j,yi+ji=−nn and the tangent line L are separated by the following distance:
(21)di+j=β1xi+j−xi−α1yi+j−yiα12+β12.In formula (21), α1 and β1 are the direction vectors of the tangent at pi, xi and yi are the abscissa and the ordinate values of pi, and xi+j and yi+j are the abscissa and ordinate values of the point whose length is the radius of the support domain at point pi .Then, the corner response function from the point to the tangent is the cumulative sum of the distance from the point columnxi+j,yi+ji=−nn to the tangent line l:
(22)T=∑j=−n,j≠0ndi+j=∑j=−n,j≠0nβ1xi+j−xi−α1yi+j−yiα12+β12.In formula (22), di+j is the distance from any point xi+j,yi+j of the point column xi+j,yi+ji=−nn to tangent L.According to Figure9(a), the average repetition rate (the average value of the ratio of angle points to actual angle points is frequently detected after changing the direction of the radar data) increases with the support domain’s radius. The average repetition rate reaches a maximum and then starts to fall when the support domain’s radius is 6. As can be observed, a support domain with an excessively high radius will fuse the corners of diagonal points with equal distances. According to Figure 9(b), the average repetition rate reaches its greatest value at the corner detection operator’s threshold of T=0.66, and oscillation variation is minimal at the maximum point. It is demonstrated that the corner detection operator created by multiplying the total distance between a point and both a chord and a tangent has a high level of robustness. Through the foregoing discussion, it has been found that the threshold size is T=0.66 and that the radius of the support domain is chosen to be 6.Figure 9
Line chart of average repetition rate.
(a)
Average repetition rate distribution of different support domain radius under fixed corner detection operator threshold 0.66(b)
Fixed support domain radius 6, different corner detection average repetition rate distribution of operator domain values


## 3.2.1. Primary Corners

As seen in Figure6, draw a straight line L1 connecting the first point p1 and the last point pn. Then, from all points (from p2 to pn−1), save the first and last, and compute the distance Di to line L1.Figure 6
Primary corners.The distanceL between the point and the straight line can be determined by computing the projection point of the point on the straight line since the coordinates of the point and the straight line expression are known.
(14)L=yp1−ypnxpi+xpn−xp1ypi+xp1ypn−yp1xpnyp1−ypn2+xp1−xpn2.In formula (14), xp1 and yp1 are the coordinates of the starting point p1, respectively, xpn and ypn are coordinates of the end point pn, respectively, and xpi and ypi are coordinates of any point pi, respectively.Determine the location that is furthest from the line and then designate that location as the main corner. The second farthest point can then be discovered by using this location as the starting point for the subsequent cycle. Until all primary corners in the laser scanning data points are located, repeat the aforementioned processes.


## 3.2.2. Corner Detection Operator

There is a certain “proportional” relationship between the curvature of the origin and the distance between the point near the origin on the parabola and the transverse coordinate axis (the tangent of the parabola at the origin) for a parabola whose opening is upward and tangent to the origin in the plane rectangular coordinate system [28]. The smaller the opening (the greater the curvature of the origin), the greater the distance between the point near the origin and the transverse coordinate axis.An illustration of how to calculate the cumulative distance from a point to a tangent is shown in Figure7. The y=5x2, x∈−1,1 function’s curve is depicted by the solid red line. Additionally, the curve of the function y=x2, x∈−1,1 is shown by the solid blue line. Assuming that x0>0 and x0,0 are points on the tangent line close to the origin, the straight line x=x0 that crosses point x0,0 and perpendicular to tangent y=0 encounters points x0,5x02 and x0,x02 with functions y=5x2 and y=x2, respectively. The radius of the support domain n is defined as the number of radar scanning data points on the left and right sides of the tangent point. The point column xi+j,yi+ji=−nn is the point pixi,yi radius of n support domain.Figure 7
Calculation of cumulative distance from point to tangent.Two arc-length parameter coordinate point columns depending on the arc length parameterize the position coordinate point column in the support domain. In this instance, two pairs of target arc-length parameter coordinates parameterize the target point (horizontal and vertical coordinates) (arc length and abscissa and arc length and ordinate).The arc length parameterization function is(15)si=0si+j=si+j−1+xi+j−xi+j−12+yi+j−yi+j−12,j=1,⋯,n,si+j−1−xi+j+1−xi+j2+yi+j+1−yi+j2,j=−1,⋯,−n.The two coordinate point columns for the two arc-length parameters,si+j,xi+ji=−nn and si+j,yi+ji=−nn, respectively, are fitted by two curves. If xs=α0+α1s+α2s2 is the fitting function; then, α=α0,α1,α2 and β=β0,β1,β2 need to be determined are the indeterminate coefficients. Determine the coefficient α and β, which make xs and ys the solutions of the point set in the least squares fitting sense, respectively. Because of the arc length parameterization si=0 and fulfill xsi=xi and ysi=yi, we may obtain that xs=xi+α1s+α2s2.
(16)fα1,α2=∑j=−n,j≠0nxsi+j−xi+j=∑j=−n,j≠0nα1si+j+α2si+j2+xi−xi+j2.Set the value of the functionα1,α2’s first partial derivative with respect to the variable α1 and α2 to 0.
(17)∂f∂α1=0∂f∂α2=0=>α1∑j=−n,j≠0nsi+j2+α2∑j=−n,j≠0nsi+j3=∑j=−n,j≠0nsi+jxi+j−xi,α1∑j=−n,j≠0nsi+j2+α2∑j=−n,j≠0nsi+j4=∑j=−n,j≠0nsi+j2xi+j−xi.Then(18)α1A11+α2A12=B1,α1A21+α2A22=B2,(19)α1=A22B1−A12B2A11A22−A12A21.We can obtainẋs=α1+α2s by xs=α0+α1s+α2s2. As a result, ẋss=si=ẋ0=α1 is the function xs’s first derivative at the target parameter point s=si=0. Similar to this, the function ys’s first derivative at the target parameter point s=si=0 is ẏss=si=ẏ0=β1.The schematic representation of the target point’s laser radar scanning points is shown in Figure8(a). As seen in Figures 8(b) and 8(c), two arc-length parameter coordinate points are created by parameterizing the points at the target point on the abscissa and ordinate, respectively. These coordinate points are designated as si+j,xi+ji=−nn and si+j,yi+ji=−nn accordingly. The two coordinate points for the arc length parameter are then fitted to produce Figures 8(d) and 8(e). Finally, as shown in Figure 8(f), the tangent direction at the target point is determined using the values of α1 and β1 obtained by fitting two arc length parameter points.Figure 8
Schematic diagram of solving the tangent line at the target point.Consequently, the tangent equation through pointpixi,yi is
(20)l:x1t=xi+tα1y1t=yi+tβ1,t∈R.In formula (20), α1 and β1 are the direction vectors of the tangent at pi, and xi and yi are the abscissa and ordinate values of pi.Any pointxi+j,yi+j in the point column xi+j,yi+ji=−nn and the tangent line L are separated by the following distance:
(21)di+j=β1xi+j−xi−α1yi+j−yiα12+β12.In formula (21), α1 and β1 are the direction vectors of the tangent at pi, xi and yi are the abscissa and the ordinate values of pi, and xi+j and yi+j are the abscissa and ordinate values of the point whose length is the radius of the support domain at point pi .Then, the corner response function from the point to the tangent is the cumulative sum of the distance from the point columnxi+j,yi+ji=−nn to the tangent line l:
(22)T=∑j=−n,j≠0ndi+j=∑j=−n,j≠0nβ1xi+j−xi−α1yi+j−yiα12+β12.In formula (22), di+j is the distance from any point xi+j,yi+j of the point column xi+j,yi+ji=−nn to tangent L.According to Figure9(a), the average repetition rate (the average value of the ratio of angle points to actual angle points is frequently detected after changing the direction of the radar data) increases with the support domain’s radius. The average repetition rate reaches a maximum and then starts to fall when the support domain’s radius is 6. As can be observed, a support domain with an excessively high radius will fuse the corners of diagonal points with equal distances. According to Figure 9(b), the average repetition rate reaches its greatest value at the corner detection operator’s threshold of T=0.66, and oscillation variation is minimal at the maximum point. It is demonstrated that the corner detection operator created by multiplying the total distance between a point and both a chord and a tangent has a high level of robustness. Through the foregoing discussion, it has been found that the threshold size is T=0.66 and that the radius of the support domain is chosen to be 6.Figure 9
Line chart of average repetition rate.
(a)
Average repetition rate distribution of different support domain radius under fixed corner detection operator threshold 0.66(b)
Fixed support domain radius 6, different corner detection average repetition rate distribution of operator domain values


## 3.3. Linear Fitting

By scanning the surrounding area with laser radar, discrete point sets can be obtained [29]. In this research, bilateral filtering is used to smooth the data for the abrupt noise points in the discrete point collection. After the filtered cluttered point set is clustered using adaptive clustering based on distance and density, each point set’s corners are detected using an operator-based approach. After corner detection and clustering, point sets require a linear fitting technique. In this study, linear fitting is done using the least squares method [30].Given a two-dimensional data point columnx1,y1,x2,y2,⋯,xn,yn, the mathematical model of linear fitting is set as y=kx+b. The parameters in the model are calculated using the residual ei=yi−kxi−bi=1,2,3⋯,n. Equation about parameters k and b with the minimum square sum of residual Q=∑i=1nei2=∑i=1nyi−kxi−b2 is taken into account.
(23)∑i=1n2yi−kxi−b×−xi=0,1≤i≤n,(24)∑i=1n2yi−kxi−b×−1=0,1≤i≤n.The fitted line can then be written as(25)y=kx+b=2∑i=1nxiyi−∑i=1nxi×∑i=1nyi2∑i=1nxi2−∑i=1nxi×∑i=1nxix+∑i=1nyi−k∑i=1nxi2.


## 4. Detailed Steps of the Algorithm

The LiDAR returns a set of ordered two-dimensional LiDAR data after each environment scan. This data is preprocessed, and the point set is(26)P=φi,ρi,i=1,2,⋯,n.In the formula,φi is the angle returned, and ρi is the distance returned when scanning the ith point, respectively.Step 1.
Creates a rectangle coordinate system from the polar coordinate system found in the original data. The following formula is used to determine the polar coordinate value of theith measuring point in Polar coordinates:
(27)Pi=ρicosφi,ρisinφi=xi,yi,1≤i≤n.Step 2.
The bilateral filtering approach is used to remove the impact of noise on the subsequent adaptive clustering and corner feature recognition by filtering the noise in LiDAR data based on the features of nonlinearity, noise suppression, data smoothing, and better edge protection.(28)IDi,j=∑k,lIk,lωi,j,k,l∑k,lωi,j,k,l.Step 3.
Determine whether the distance between the current point and the previous point is greater than the linear threshold from the second point to the last point and classify the starting point as class 1. It is classified into the current class if it is less than the threshold value. Otherwise, determine whether the distance between the current and previous points exceeds the class density threshold. If this is not the case, it is assigned to the current class. Otherwise, a new class is created, and the current point is transferred to it.(29)dth=απφs180maxdi−1,di,(30)ρth=μk+ασk.Step 4.
Determine whether the threshold is smaller than the final point and the starting point. If the first category is smaller than the last category, the latter is not merged under the former. The isolated point set with less than three data points in the class is set as the noise elimination point set.Step 5.
Connect the first and last points in a straight line in each of the categories obtained in the previous step, calculate the distance to the line from points other than the first and last points, find the point that is the furthest away from the line, and define it as the primary corner.(31)L=yp1−ypnxpi+xpn−xp1ypi+xp1ypn−yp1xpnyp1−ypn2+xp1−xpn2.Step 6.
Calculate the curvature value at the main corner within the support radiusn. Save the curve curvature value as Con1 if it above the specified threshold.
(32)T=∑j=−n,j≠0ndi+j=∑j=−n,j≠0nβ1xi+j−xi−α1yi+j−yiα12+β12.Step 7.
Use pointCon1 as the beginning of the subsequent iteration to locate the other principal corner. Calculate the curvature value at the main corner within the support radius n. Save as Con2 if the curve curvature value exceeds the specified threshold T. Continue with Steps 5, 6, and 7 until the curve’s curvature value is below the specified threshold T.Step 8.
The laser point cloud’s shape feature map is fitted using the least square approach after each class, and its recognized corner points have been segmented.


## 5. Experimental Results and Analysis

Table1 shows the hard and software environments for this experiment. In this study, the laser radar’s starting measurement angle is -80°, the termination angle is 80°, the angular resolution is 0.33°, and 481 data sets were collected. The algorithm runs in the Matlab 2020a simulation environment, and the computer’s CPU is an Intel Core i7-7700U with 8 GB of memory.Table 1
Experimental setup environment.
Name of deviceCharacteristic parametersLaser radarSick tim571, scanning range 160°, angular resolution 0.33°Mobile deviceWorkshop handling chassis AGVThe simulation environmentMatlab 2020aParameter of computerIntel Core i7-7700HQ, memory space 8 GB


### 5.1. Real Environment Simulation

Figure10(a) depicts the actual scenes of multilevel obstacle features and multiangle features, while Figure 10(b) depicts the environment fitting results using the algorithm described in this paper.Figure 10
Multilevel obstacle environment feature fitting.
(a)
Multilevel obstacle environment(b)
Fitting feature graph2D LiDAR is lacking in spatial processing because, as seen in Figure10(a), it only gives a collection of data that includes angle and distance information. Occlusion and ghosting issues in multilevel obstacle processing make it challenging to effectively depict the hierarchical information when fitting the provided data information. Due to the information fusion area and the multilayer obstacles, as illustrated in Figure 10(b), the environment-related algorithm will first distinguish the obstacle in distinct regions and levels. Then, avoid differentiating distinct levels at the same level and mix the angle point characteristic with the various degrees of environmental information.With 11 classification features and 5 point corner features, the original laser radar point cloud is clustered in the fitting results successfully. The fitting effect is ideal, and the fitting results match the scanning environment closely.


### 5.2. Contrast Experiment

The proposed algorithm was compared with the PDBS algorithm and the IEPF algorithm in the comparison experiment to compare the fitting effect, the success rate of breakpoint detection, the success rate of corner detection, and the running time of the algorithm in the same environment. The PDBS algorithm is primarily based on a comparison of the distance between two adjacent LiDAR points in a rectangular coordinate system and a predetermined threshold. If the distance between two adjacent measurement points exceeds the threshold, the two points are considered to belong to different areas. The threshold value used in the PDBS method has a significant impact on line segmentation. Oversegmentation is easy to achieve if the threshold value is set too low; undersegmentation is easy to achieve if the threshold value is set too high. At the same time, segmentation failure will occur at corner points due to the influence of corner points. The adaptive clustering method based on distance and density was used in this paper for region division, which is consistent with the main purpose of the PDBS method. As a result, the PDBS method and the method presented in this paper are chosen for the comparison experiment.The primary principle of the IEPF algorithm is to compare the line’s greatest distance with the threshold value between the laser scanning point and the string of beginning and last lines. The laser scanning point is a corner point if the line’s greatest distance exceeds the predetermined threshold. In order to prevent the issue with the PDBS method in feature extraction error at the intersection of two line segments, this approach can extract the corner of the line segment at the intersection of two line segments. However, the IEPF algorithm will regard breakpoints as points on the same line when fitting because it is unable to determine if a point is a breakpoint or not. The corner detection operator method is used in this paper. The IEPF method is chosen to perform a comparison experiment with the suggested algorithm in order to confirm the accuracy and efficiency benefits of the corner detection method utilized by the proposed algorithm.For the same set of environmental data, Figure11 displays the linear fitting results for the proposed approach, the PDBS algorithm, and the IEPF algorithm. The real point cloud data graph returned by LiDAR when scanning a real environment is shown in Figure 11(a).Figure 11
Compared with PDBS and IEPF, the proposed algorithm fits the comparison diagram.
(a)
Raw image of LiDAR scan data(b)
PDBS algorithm fitting result graph(c)
IEPF algorithm fitting result graph(d)
The algorithm in this paper fits the result graphThe PDBS algorithm is used to process the original data, as seen in Figure11(b). As can be seen, the algorithm cannot fit the two lines individually at their intersection because the fitting line is very dissimilar to the actual line.The original data are processed using the IEPF approach, as seen in Figure11(c). The line segment’s fitting impact is enhanced by processing the junction of the two lines. The fitted straight line will differ significantly from the actual line, though, if there are noise points or breakpoints in the fitting. The algorithm presented in this paper is utilized to process the original data, as seen in Figure 11(d). The original point data are first clustered into distinct point sets based on the distance and density of the filtered original point data. Next, the abrupt noise points are filtered by bilateral filtering. The corner points in the clustered point set are then discovered using the corner detection operator, and an automated exit from the corner detection step without a corner feature is also detected. The identified corner is used to segment the clustering point set, and the least square approach is used to fit each point set linearly. The corner point, the regional breakpoint, and the noise point outside the region, which can suit the environmental parameters scanned by the radar well, do not exhibit the fitting failure.


### 5.3. Calculation of Similarity Error

The similarity error between actual data points and fitting feature lines in the three techniques is displayed in Figure12.Figure 12
The graph of three algorithms similarity error.
(a)
The proposed algorithm similarity error(b)
IEPF algorithm similarity error(c)
PDBS algorithm similarity errorThe similarity error between the feature line of the laser scanning point and the actual point varies within 0.01 meters, as illustrated in Figure12(a). The greatest peak value is 2.5×10−2 meters, the maximum variation is 6.51×10−2 meters, and the average error is 3.42×10−3 meters. There is no bigger mistake. As can be observed, the fitting impact is relatively close to the real environment feature, and the similarity error between the linear feature fitted by the technique in this study and the real data point is minimal.The average similarity error of the IEPF is1.21×10−2 meters, the variance is 5.37×10−1 meters, the average similarity error of the PDBS is 8.33×10−3 meters, the variance is 1.8×10−1 meters, and the similarity error between the fitting feature line and the real point fluctuates greatly, reaching a maximum of 0.25 meters, as shown in Figures 12(b) and 12(c). The PDBS algorithm incorrectly converts environmental corner features to linear features at the corner of the line segment in Figure 12(b), which is extremely different from the actual environment. As a result, the peak value of the PDBS method fitting error graph is very large. The IEPF method’s fitting error graph’s peak value in Figure 12(c) is quite big, which suggests that the algorithm fails to accurately fit the true environmental features at regional breakpoints and noise points beyond the region. In conclusion, fitting the optimal actual environment model is challenging because IEPF and PDBS each have advantages and limitations in terms of linear fitting.


### 5.4. Open Source Dataset Simulation

The experimental data was from Cartographer ROS 2D Laser SLAM at Deutsches Museum [31]. There are several locations in the experimental dataset that lack a clear corner feature because it was collected in an indoor setting with numerous hallways. A dataset of environment scan data with glaring corner features is chosen in order to confirm the algorithm’s validity. The data is gathered by the mobile robot scanning the indoor environment by LiDAR at 5 different sites, as illustrated in Figures 13(a)–13(e). As can be seen from the figures, the proposed algorithm is capable of accurately and consistently extracting corner features that are close to right angles, regardless of whether they have convex corner features (corresponding to point A in the figure) or concave corner features (corresponding to point B in the figure) in various directions and positions.Figure 13
Corner feature extraction and localization.
(a)(b)(c)(d)(e)The position accuracy of retrieved features is crucial for feature matching in the localization problem of mobile robot based on feature map. The matching accuracy will increase as the placement precision does. The relative positions of the two features do not vary even though the features derived by the proposed algorithm at various points have different positions in the sensor coordinate system. The distance between the corner features in this paper stays constant. However, due to the differences in environmental scanning data obtained by sensors at different locations, there will be errors in the feature extraction results (ignoring sensor statistical errors), so the relative positions of the two features can only be close. And a good algorithm can ensure that they remain relatively constant. In light of this, this paper assesses feature extraction quality by measuring the distance between two corner features.The average distance between feature sites A and B in Figure12 is computed to be 2.302 m, and the variance is 9.41×10−5m2, as given in Table 2 based on the results of five times of data extraction from different angles in the same environment. It is clear that the proposed algorithm, which combines adaptive clustering with a corner detection operator to extract angle information, has excellent positioning accuracy and can satisfy the needs of autonomous robot positioning and mapping.Table 2
Fitting results of corner points and line segments.
NumberCorner feature ACorner feature BThe length of line segment AB/mX/mY/mX/mY/m16.6328.2337.4290.7972.3014128.7212.7487.9760.55212.31883637.5017.3848.0525.1632.28832748.3973.2997.7771.0822.30206257.7823.9417.3541.6802.301283Average7.80675.12107.71762.91022.302383Mean square error0.53175.02980.79525.10019.411×10−5


### 5.5. Feature Point Extraction Results and Algorithm Time

10 frames were chosen from the experimental dataset to compare the pros and cons of the proposed algorithm with the PDBS algorithm for area detection and the IEPF algorithm for corner feature detection in order to further verify the precision and effectiveness of the proposed algorithm in line fitting.According to Table3, for the same partition number, this algorithm’s time range is [9.6, 25.3] ms, and the average partition processing success percentage is 95.11%. The average success rate of partition processing for the PDBS method is 83.55%, and the time range is [15.8, 36.3] ms. As can be shown, the proposed algorithm has a greater partition processing success rate and nearly saves half the time when compared to the PDBS algorithm. Because the PDBS method does not further analyze the data’s noise point or corner point features, it solely utilizes a fixed threshold to segment the LiDAR data. The proposed algorithm’s time range is [21.6, 38.2] ms for the same number of corner features, with an average corner discrimination success rate of 92.62%. The average corner discrimination success rate according to the IEPF algorithm is 72.51% for the time range of [29.9, 53.4] ms. The proposed algorithm takes less time than the IEPF algorithm. The primary cause is that, in order to deal with corner features optimally, the IEPF algorithm constantly adjusts the fixed threshold. The proposed algorithm, however, combines corner detection operator with adaptive clustering to find corner points for each category after clustering. In order to prevent underfitting and overfitting issues with linear fitting, it lessens the complexity of determining corner points from all data points.Table 3
Comparison of feature point recognition efficiency and success rate of laser scanning data in different scenes.
NumberPartition numberPDBS algorithmProposed algorithmCorner features numberIEPF algorithmProposed algorithmTimes/msSuccess rate/%Times/msSuccess rate/%Times/msSuccess rate/%Times/msSuccess rate/%11320.276.9214.392.31935.277.7825.91002918.988.8910.61001346.876.9230.292.3131636.381.2525.393.75630.183.3323.61004715.885.719.6100.1037.67028.39051019.88013.990.529.910021.610061323.276.9218.61001042.76031.59071524.686.6717.393.33835.662.5030.487.581225.991.6715.591.671248.766.6735.191.679821.387.5015.71001453.464.2938.292.86101024.68017.9901141.963.6433.881.82


## 5.1. Real Environment Simulation

Figure10(a) depicts the actual scenes of multilevel obstacle features and multiangle features, while Figure 10(b) depicts the environment fitting results using the algorithm described in this paper.Figure 10
Multilevel obstacle environment feature fitting.
(a)
Multilevel obstacle environment(b)
Fitting feature graph2D LiDAR is lacking in spatial processing because, as seen in Figure10(a), it only gives a collection of data that includes angle and distance information. Occlusion and ghosting issues in multilevel obstacle processing make it challenging to effectively depict the hierarchical information when fitting the provided data information. Due to the information fusion area and the multilayer obstacles, as illustrated in Figure 10(b), the environment-related algorithm will first distinguish the obstacle in distinct regions and levels. Then, avoid differentiating distinct levels at the same level and mix the angle point characteristic with the various degrees of environmental information.With 11 classification features and 5 point corner features, the original laser radar point cloud is clustered in the fitting results successfully. The fitting effect is ideal, and the fitting results match the scanning environment closely.


## 5.2. Contrast Experiment

The proposed algorithm was compared with the PDBS algorithm and the IEPF algorithm in the comparison experiment to compare the fitting effect, the success rate of breakpoint detection, the success rate of corner detection, and the running time of the algorithm in the same environment. The PDBS algorithm is primarily based on a comparison of the distance between two adjacent LiDAR points in a rectangular coordinate system and a predetermined threshold. If the distance between two adjacent measurement points exceeds the threshold, the two points are considered to belong to different areas. The threshold value used in the PDBS method has a significant impact on line segmentation. Oversegmentation is easy to achieve if the threshold value is set too low; undersegmentation is easy to achieve if the threshold value is set too high. At the same time, segmentation failure will occur at corner points due to the influence of corner points. The adaptive clustering method based on distance and density was used in this paper for region division, which is consistent with the main purpose of the PDBS method. As a result, the PDBS method and the method presented in this paper are chosen for the comparison experiment.The primary principle of the IEPF algorithm is to compare the line’s greatest distance with the threshold value between the laser scanning point and the string of beginning and last lines. The laser scanning point is a corner point if the line’s greatest distance exceeds the predetermined threshold. In order to prevent the issue with the PDBS method in feature extraction error at the intersection of two line segments, this approach can extract the corner of the line segment at the intersection of two line segments. However, the IEPF algorithm will regard breakpoints as points on the same line when fitting because it is unable to determine if a point is a breakpoint or not. The corner detection operator method is used in this paper. The IEPF method is chosen to perform a comparison experiment with the suggested algorithm in order to confirm the accuracy and efficiency benefits of the corner detection method utilized by the proposed algorithm.For the same set of environmental data, Figure11 displays the linear fitting results for the proposed approach, the PDBS algorithm, and the IEPF algorithm. The real point cloud data graph returned by LiDAR when scanning a real environment is shown in Figure 11(a).Figure 11
Compared with PDBS and IEPF, the proposed algorithm fits the comparison diagram.
(a)
Raw image of LiDAR scan data(b)
PDBS algorithm fitting result graph(c)
IEPF algorithm fitting result graph(d)
The algorithm in this paper fits the result graphThe PDBS algorithm is used to process the original data, as seen in Figure11(b). As can be seen, the algorithm cannot fit the two lines individually at their intersection because the fitting line is very dissimilar to the actual line.The original data are processed using the IEPF approach, as seen in Figure11(c). The line segment’s fitting impact is enhanced by processing the junction of the two lines. The fitted straight line will differ significantly from the actual line, though, if there are noise points or breakpoints in the fitting. The algorithm presented in this paper is utilized to process the original data, as seen in Figure 11(d). The original point data are first clustered into distinct point sets based on the distance and density of the filtered original point data. Next, the abrupt noise points are filtered by bilateral filtering. The corner points in the clustered point set are then discovered using the corner detection operator, and an automated exit from the corner detection step without a corner feature is also detected. The identified corner is used to segment the clustering point set, and the least square approach is used to fit each point set linearly. The corner point, the regional breakpoint, and the noise point outside the region, which can suit the environmental parameters scanned by the radar well, do not exhibit the fitting failure.


## 5.3. Calculation of Similarity Error

The similarity error between actual data points and fitting feature lines in the three techniques is displayed in Figure12.Figure 12
The graph of three algorithms similarity error.
(a)
The proposed algorithm similarity error(b)
IEPF algorithm similarity error(c)
PDBS algorithm similarity errorThe similarity error between the feature line of the laser scanning point and the actual point varies within 0.01 meters, as illustrated in Figure12(a). The greatest peak value is 2.5×10−2 meters, the maximum variation is 6.51×10−2 meters, and the average error is 3.42×10−3 meters. There is no bigger mistake. As can be observed, the fitting impact is relatively close to the real environment feature, and the similarity error between the linear feature fitted by the technique in this study and the real data point is minimal.The average similarity error of the IEPF is1.21×10−2 meters, the variance is 5.37×10−1 meters, the average similarity error of the PDBS is 8.33×10−3 meters, the variance is 1.8×10−1 meters, and the similarity error between the fitting feature line and the real point fluctuates greatly, reaching a maximum of 0.25 meters, as shown in Figures 12(b) and 12(c). The PDBS algorithm incorrectly converts environmental corner features to linear features at the corner of the line segment in Figure 12(b), which is extremely different from the actual environment. As a result, the peak value of the PDBS method fitting error graph is very large. The IEPF method’s fitting error graph’s peak value in Figure 12(c) is quite big, which suggests that the algorithm fails to accurately fit the true environmental features at regional breakpoints and noise points beyond the region. In conclusion, fitting the optimal actual environment model is challenging because IEPF and PDBS each have advantages and limitations in terms of linear fitting.


## 5.4. Open Source Dataset Simulation

The experimental data was from Cartographer ROS 2D Laser SLAM at Deutsches Museum [31]. There are several locations in the experimental dataset that lack a clear corner feature because it was collected in an indoor setting with numerous hallways. A dataset of environment scan data with glaring corner features is chosen in order to confirm the algorithm’s validity. The data is gathered by the mobile robot scanning the indoor environment by LiDAR at 5 different sites, as illustrated in Figures 13(a)–13(e). As can be seen from the figures, the proposed algorithm is capable of accurately and consistently extracting corner features that are close to right angles, regardless of whether they have convex corner features (corresponding to point A in the figure) or concave corner features (corresponding to point B in the figure) in various directions and positions.Figure 13
Corner feature extraction and localization.
(a)(b)(c)(d)(e)The position accuracy of retrieved features is crucial for feature matching in the localization problem of mobile robot based on feature map. The matching accuracy will increase as the placement precision does. The relative positions of the two features do not vary even though the features derived by the proposed algorithm at various points have different positions in the sensor coordinate system. The distance between the corner features in this paper stays constant. However, due to the differences in environmental scanning data obtained by sensors at different locations, there will be errors in the feature extraction results (ignoring sensor statistical errors), so the relative positions of the two features can only be close. And a good algorithm can ensure that they remain relatively constant. In light of this, this paper assesses feature extraction quality by measuring the distance between two corner features.The average distance between feature sites A and B in Figure12 is computed to be 2.302 m, and the variance is 9.41×10−5m2, as given in Table 2 based on the results of five times of data extraction from different angles in the same environment. It is clear that the proposed algorithm, which combines adaptive clustering with a corner detection operator to extract angle information, has excellent positioning accuracy and can satisfy the needs of autonomous robot positioning and mapping.Table 2
Fitting results of corner points and line segments.
NumberCorner feature ACorner feature BThe length of line segment AB/mX/mY/mX/mY/m16.6328.2337.4290.7972.3014128.7212.7487.9760.55212.31883637.5017.3848.0525.1632.28832748.3973.2997.7771.0822.30206257.7823.9417.3541.6802.301283Average7.80675.12107.71762.91022.302383Mean square error0.53175.02980.79525.10019.411×10−5


## 5.5. Feature Point Extraction Results and Algorithm Time

10 frames were chosen from the experimental dataset to compare the pros and cons of the proposed algorithm with the PDBS algorithm for area detection and the IEPF algorithm for corner feature detection in order to further verify the precision and effectiveness of the proposed algorithm in line fitting.According to Table3, for the same partition number, this algorithm’s time range is [9.6, 25.3] ms, and the average partition processing success percentage is 95.11%. The average success rate of partition processing for the PDBS method is 83.55%, and the time range is [15.8, 36.3] ms. As can be shown, the proposed algorithm has a greater partition processing success rate and nearly saves half the time when compared to the PDBS algorithm. Because the PDBS method does not further analyze the data’s noise point or corner point features, it solely utilizes a fixed threshold to segment the LiDAR data. The proposed algorithm’s time range is [21.6, 38.2] ms for the same number of corner features, with an average corner discrimination success rate of 92.62%. The average corner discrimination success rate according to the IEPF algorithm is 72.51% for the time range of [29.9, 53.4] ms. The proposed algorithm takes less time than the IEPF algorithm. The primary cause is that, in order to deal with corner features optimally, the IEPF algorithm constantly adjusts the fixed threshold. The proposed algorithm, however, combines corner detection operator with adaptive clustering to find corner points for each category after clustering. In order to prevent underfitting and overfitting issues with linear fitting, it lessens the complexity of determining corner points from all data points.Table 3
Comparison of feature point recognition efficiency and success rate of laser scanning data in different scenes.
NumberPartition numberPDBS algorithmProposed algorithmCorner features numberIEPF algorithmProposed algorithmTimes/msSuccess rate/%Times/msSuccess rate/%Times/msSuccess rate/%Times/msSuccess rate/%11320.276.9214.392.31935.277.7825.91002918.988.8910.61001346.876.9230.292.3131636.381.2525.393.75630.183.3323.61004715.885.719.6100.1037.67028.39051019.88013.990.529.910021.610061323.276.9218.61001042.76031.59071524.686.6717.393.33835.662.5030.487.581225.991.6715.591.671248.766.6735.191.679821.387.5015.71001453.464.2938.292.86101024.68017.9901141.963.6433.881.82


## 6. Conclusions

The filtering of noise points outside the region, adaptive threshold clustering based on range and density, corner feature extraction in accordance with the corner detection operator, and use of the least square approach for linear fitting are all methods developed in this study. Analysis and simulation show that (1) the PDBS approach using fixed threshold is sensitive to breakpoint detection. The corner points of the two regions are combined into one region because the corner information is not recovered. (2) The IEPF algorithm can extract the corner points of a line segment at its junction, but it is unable to determine if a location in the radar data is a breakpoint using this technique.Based on this, the algorithm for fitting radar linear features that combines corner detection and adaptive clustering is proposed in this study. Bilateral filtering has the properties of nonlinearity, noise reduction, data smoothing, and superior edge protection for noise processing. The adaptive clustering method described in this study, which is based on distance and density, can lessen the effects of local breakpoints and faults while processing LiDAR data points. This paper presents a corner feature identification approach based on a corner detection operator that can distinguish between different feature types and lower the corner recognition error rate.The algorithm in this study is more accurate in angular and linear placement, according to simulation and testing. The standard variance of length for corner feature extraction and localization is9.41×10−5m2. Only about half of the time is used compared to PDBS and IEPF, improving the accuracy of corner identification by 20.1% and partition processing by 11.6%. It can precisely determine the corner and partition points’ locations. A major improvement in fitting feature line segment precision makes it appropriate for embedded development of autonomous robots based on SLAM. The primary area of investigation in this study is the processing of LiDAR-extracted environmental data when a mobile robot is immobile. The primary focus of future study will be on figuring out how to remove the motion distortion brought on by mobile robot mobility and the correlation between subsequent data frames.



---

*Source: 6991467-2023-02-24.xml*