CN111985322A - A Lidar-based Road Environment Element Perception Method - Google Patents

Abstract

The invention discloses a method for perceiving road environment elements based on laser radar. The steps include: step 1, down-sampling the original laser radar point cloud data, acquiring the region of interest, and obtaining simplified point cloud data and ground data. Segmentation to obtain results; Step 2, use the voxel-based DBSCAN clustering algorithm to achieve obstacle segmentation of non-ground data; classify and identify obstacles based on multi-features; Step 3, use the data point elevation mutation to design a suitable The road boundary extraction method of vehicle lidar data, after extracting road boundary points, use prior knowledge to screen the boundary points, and use the least squares method to fit the road boundary line; use the grid to mark the barrier-free area to realize lidar The detection of the passable area in the road scene is done. The method of the invention has the advantages of simple algorithm, small data error, safety and reliability.

Description

A Lidar-based Road Environment Element Perception Method

technical field

The invention belongs to the technical field of computer vision and artificial intelligence, and relates to a road environment element perception method based on laser radar.

Background technique

Road environment perception technology is an important technical support for unmanned driving. It is one of the core research contents in computer vision and artificial intelligence, and has broad application prospects.

In the field of computer vision, due to the complexity and real-time variability of the road environment, it is usually necessary to collect multiple datasets from different perspectives and at different times, and each dataset contains a large amount of data and real-time features. By analyzing and processing them to perceive real-time road conditions, important tasks such as real-time vehicle control, path planning, and obstacle avoidance can be realized. At present, the scene data used in many road environment perception research is relatively simple, and the scene contains only a few obstacles. A complex scene of elements. In addition, the realization of the perception task is relatively simple, and one type of scene data is only suitable for solving a certain type of perception task, and it is impossible to perform the perception operation of processing multiple tasks with one scene data.

Therefore, the point cloud data obtained by vehicle lidar is selected as the research object, and research is carried out around several key technologies of road environment perception of unmanned vehicles, including ground segmentation, obstacle segmentation and recognition, road boundary detection and passable area detection. Through the realization of several key technologies, the perception task of the road environment is jointly completed, thereby making up for the defects of the current environment perception research that the data contains less obstacles and the perception task is single. Through the research of lidar environment perception, the detection and perception of the surrounding environment of the unmanned vehicle is completed, which is of great significance for the subsequent analysis of real-time road conditions and the realization of vehicle control, path planning and other operations.

SUMMARY OF THE INVENTION

The purpose of the present invention is to provide a road environment element perception method based on lidar, which solves the problem that the prior art cannot realize a perception operation of multiple tasks of scene data processing, and can perceive road environment elements efficiently in real time.

The technical solution adopted in the present invention is a method for perceiving road environment elements based on laser radar, which is implemented according to the following steps:

Step 1, down-sampling the original lidar point cloud data, acquiring the region of interest, obtaining the simplified point cloud data and segmenting the ground data, and obtaining the result. The specific process is:

1.1) Realize the downsampling algorithm based on the voxel grid to perform data reduction operations;

1.2) Eliminate discrete points and long-distance useless points, and obtain areas of interest for subsequent processing;

1.3) Divide the simplified data obtained in steps 1.1) and 1.2) into ground data. Based on the RANSAC plane detection algorithm, the data is segmented and calibrated and then the ground is segmented, so as to achieve common ground extraction for complex scenes. suitability;

Step 2, implement obstacle segmentation and obstacle recognition,

2.1) Using voxel-based DBSCAN clustering algorithm to achieve obstacle segmentation of non-ground data;

2.2) Multi-feature-based obstacle classification and recognition;

Step 3, carry out road boundary detection and passable area analysis,

3.1) Design a road boundary extraction method suitable for vehicle-mounted lidar data by using the elevation mutation of data points. After extracting road boundary points, use prior knowledge to screen the boundary points, and use the least squares method to fit the road boundary line;

3.2) Use the grid to mark the barrier-free area to realize the detection of the passable area in the lidar road scene, and that's it.

The beneficial effects of the invention are that the algorithm is simple, the data error is small, safe and reliable, the method system of artificial intelligence and computer vision is enriched, the development of machine environment perception is supported, and a road environment perception for the basic technology of unmanned driving is provided. choose.

Description of drawings

Fig. 1a is the input raw data in step 1 of the method embodiment of the present invention;

Fig. 1b is the data obtained after downsampling and obtaining the region of interest in step 1 of the method embodiment of the present invention;

Fig. 1c is the scene ground data obtained after segmentation in step 1 of the method embodiment of the present invention;

Fig. 2a is the input non-ground point cloud original data in step 2 of the method embodiment of the present invention;

Fig. 2b is the data after obstacle segmentation in step 2 of the method embodiment of the present invention;

Fig. 2c is the data obtained after classification and identification of obstacles in step 2 of the method embodiment of the present invention;

Fig. 3a is the road boundary detection result obtained in step 3 of the method embodiment of the present invention;

Fig. 3b is the result of the analysis of the passable area obtained in step 3 of the method embodiment of the present invention;

Detailed ways

The present invention will be described in detail below with reference to the accompanying drawings and specific embodiments.

The present invention is implemented according to the following steps:

Step 1, as shown in Figure 1a, downsample the original lidar point cloud data, acquire the region of interest, obtain the simplified point cloud data shown in Figure 1b and segment the ground data, and obtain Figure 1c The results shown, the specific process is:

1.1) Realize the downsampling algorithm based on voxel grid to simplify the data,

The point cloud data obtained by lidar are scattered and disordered points. The downsampling method based on voxel grid does not need to construct a complex topology structure, and the implementation is simple and the algorithm is efficient. According to the density of the point cloud data distribution, select the three side lengths of the appropriate grid cell, split the point cloud data into small voxel grids, count all the points contained in the cell, and calculate their centroids as the whole The representative of all points in the grid unit, the centroid points of all grid units are combined to form new data, and the downsampling is completed.

1.1.1) Read the point cloud data of the original lidar (as shown in Figure 1a);

1.1.2) Calculate the maximum and minimum points in the point cloud data, that is, the upper right point maxPoint and the lower left point minPoint of the point cloud bounding box, so as to calculate the length Lx, width Ly, and height Lz of the point cloud bounding box;

1.1.3) Set the length Vx, width Vy, and height Vz of the voxel grid unit; divide the point cloud data into a voxel grid to obtain m×n×s units, where m=[Lx/Vx], n=[Ly/Vy], s=[Lz/Vz], the symbol "[]" is the rounding symbol to ensure that the number of grid cells is an integer;

1.1.4) Randomly select any point p, then the grid cell corresponding to point p is:

The one-dimensional grid cell number Index to which point p belongs is:

Index=I _{index_x} *1+I _{index_y} *(m+1)+I _{index_z} *(m+1)*(n+1)(2)

1.1.5) Traverse all the points of the origin cloud and insert the points with the same grid cell number Index into the same Index_vector vector;

1.1.6) Calculate the centroid G(x, y, z) of L points in the grid cell where the same numbered point is located as a representative point to achieve downsampling. The calculation formula is as follows:

1.2) Eliminate discrete points and long-distance useless points, and obtain the area of interest for subsequent processing:

After analyzing the point cloud data obtained by the vehicle-mounted lidar, in order to eliminate discrete points and long-distance useless points, so as to obtain the region of interest for subsequent processing, this step proposes a region of interest acquisition method based on point density statistics. Figure 1a is a frame of point cloud data obtained by vehicle-mounted lidar. The blank circular area in the center is where the lidar device is located. The data takes the forward direction of the vehicle as the positive direction of the X-axis, and the right direction of the vehicle is the Y-axis. The positive direction, the upward direction is the positive direction of the Z axis. By counting the density of points on both sides of the vehicle's forward direction, that is, in the Y-axis direction, and comparing with the set threshold, it can be divided into whether it belongs to the area of interest. The specific process is:

1.2.1) Project the downsampled point cloud data to the yoz plane;

1.2.2) Obtain the projection data from the maximum data Y _min to the minimum data Y _max in the Y-axis direction, and divide the data into M segments in this area, (according to the data size of the test, set M=20);

1.2.3) Count the density D _i of the points in each piece of data, and draw the density curve of the entire point cloud data;

(根据数据以及对应的密度曲线，阈值

优选2000)进行比较，从最左端进行判断，若

则认为此段疏密度较低，包含信息较少，将此段删除；继续比较下一段，若出现

停止此次判断；再从最右端开始判断，若

则将此段删除，直到

时结束判断，1.2.4) Calculate the total density ratio r of each segment density by formula (4), and set the threshold value

(Based on the data and the corresponding density curve, the threshold

Preferably 2000) for comparison, and judge from the leftmost end, if

It is considered that this paragraph has a low density and contains less information, and this paragraph is deleted; continue to compare the next paragraph, if there is

Stop this judgment; then start the judgment from the far right, if

delete this segment until

when the judgment ends,

1.2.5) For the forward direction of the vehicle, select 30m before and after the lidar device as the region of interest in the X-axis direction, use the pass-through filtering method to divide the region, and obtain the down-sampled region of interest as the final simplified scene data. , the results shown in Fig. 1b.

1.3) Divide the simplified data obtained in steps 1.1) and 1.2) into ground data (as shown in Figure 1b). Based on the RANSAC plane detection algorithm, the data is segmented and calibrated and then the ground is segmented to achieve To extract the universality of the ground for complex scenes, the specific process is:

1.3.1) Calculate the minimum value min_x and the maximum value max_x along the X-coordinate axis of the vehicle's driving direction, and divide the point cloud data after simplified processing into N segments of sub-point cloud data with a length of 1m along the X-axis direction, where N=ROUNDUP (max_x-min_x), ROUNDUP(x) is a round-up function;

1.3.2) For each segment of sub-point cloud data, the RANSAC plane detection algorithm is used to detect the ground part of this segment of sub-point cloud data, and the general equation to obtain the fitting plane is:

Ax+By+Cz+D=0, where A, B, C, D are known constants, and A, B, C are not zero at the same time, the normal vector V=(A, B, C); in addition, when using lidar to collect data, the Z axis in the radar coordinate system is kept vertical, then the vertical vector is Q=(0,0,1), and the normal vector of the ground Plane obtained by calculating the fitting The calibration matrix of V and vertical vector Q is called rotation matrix T, and the obtained rotation matrix T is used to calibrate the sub-point cloud data. The specific calibration operation is as follows:

It is known that the vector before calibration is V and the vector after calibration is Q, then:

V·Q＝|V||Q|cosθ (5)

Then the angle between V and Q is:

Assuming that the vector V before calibration is (a1, a2, a3) (this is an instantiation of the formula, which is equivalent to one being a formal parameter and the other being an actual parameter), and the vector Q after calibration is (b1, b2, b3), according to the vector The cross product definition gets the rotation axis C(c1,c2,c3), then there are:

Let the rotation axis C correspond to a unit vector k (k _x , k _y , k _z ), using the rotation angle θ and the unit vector k, according to the Rodrigue rotation formula, an arbitrary vector u in the space rotates along the unit vector k by the angle θ after The resulting vector w is:

w=u cosθ+(k·u)k(1-cosθ)+(k·u)sinθ (8)

Thus, the corresponding rotation matrix T is obtained as:

1.3.3) Realize the ground segmentation of this sub-point cloud data based on the RANSAC plane detection algorithm. The specific steps are:

1.3.3.1) Input the calibrated sub-point cloud data CloudPoint, give the plane model and set the distance threshold t, (this step is based on empirical data, and the threshold t is set to 0.1m);

1.3.3.2) Randomly sample three points in the point cloud data so that these three points are not on the same straight line, and solve the plane model equation formed by the three random sample points;

1.3.3.3) Calculate the distance dis from other points of the point cloud data to the plane, and compare it with the set distance threshold t to obtain an intra-office point set IncloudSet based on the plane model;

1.3.3.4) Count the number of IncloudSets in the in-office point set of the plane model, compare it with the current maximum number, and keep the largest number of the two;

1.3.3.5) Re-estimate the new plane model by keeping the set of all intra-office points with the largest number, and output the intra-office point as the ground point for this calculation;

1.3.3.6) Re-sampling and repeat the above steps; when the number of iterative calculations reaches the maximum number of iterations, exit the iterative loop, select the optimal plane model and the ground point with the largest number of points in the output bureau during the iteration process, and the ground point obtained at this time is is the ground data detected by this point cloud.

1.3.4) Combine the ground data detected by each sub-point cloud data to obtain the final ground data, as shown in Figure 1c, to achieve the segmentation of ground and non-ground data.

Step 2, implement obstacle segmentation and obstacle recognition,

2.1) Using voxel-based DBSCAN clustering algorithm to achieve obstacle segmentation of non-ground data;

2.1.1) As shown in Figure 2a, the non-ground lidar point cloud scene data is used as input to divide the voxel grid unit, and the side length d of the grid unit is set to 15cm, and the point cloud data X, Y, The maximum and minimum values of the three coordinate axes of Z are calculated by using the set side length d of the grid unit to obtain the number of layers m, n, and s of each coordinate axis of the divided grid unit (the number of layers m, n, and s here is not It needs to be distinguished from the previous repeated letters, because it is facing the same operation of different data subjects), taking the X-axis as an example, min_X is the minimum coordinate of the X-axis, and max_X is the maximum coordinate of the X-axis (here min_X, max_X are not It needs to be distinguished from the previous repeated letters, because it is faced with the same operation by different data subjects), there are:

The Y-axis and Z-axis are consistent with the processing methods of the above-mentioned X-axis. After the above steps, the voxel grid unit division of the unit side length d of the scene data can be obtained;

2.1.2) Count the number of points contained in all grid cells, record all non-empty grid cells, and mark these grid cells reasonably to ensure that the overall structure of these grid cells is the same as the original data location information, and determine a certain grid cell. The grid cells in the neighborhood around a grid cell are the same as the original data;

According to the set parameter threshold MinPts (based on the point cloud data used and experimental experience, the parameter threshold MinPts is set to 20), each non-empty grid cell is judged, if the number of points contained in the grid cell is greater than MinPts, the This grid unit is set as the core unit, and the contained points are set as the core points; if the number of points contained in the grid unit is less than MinPts, a secondary judgment is required;

Perform an ε-neighborhood search on the points in this grid unit to determine whether there are neighbor points located in the core unit in the neighborhood. , other points will no longer be judged; if the neighborhood point does not exist, select other points in this grid cell for judgment, until all points have been judged, there is still no neighborhood point located in other core cells, then directly judge this The points in the grid cells are noise points;

2.1.3) Calculate the centroid Q containing R points in each non-noise grid cell in 1.1.2):

2.1.4) Define the calculated set of centroid points as the core point set S, and randomly select any core point P from the set. If there are no less than MinPts points within the radius distance ε of the point P, then the point P is the core point , if not, then this point P is a noise point, calculate other centroid points contained in its ε-neighborhood in turn and add them to the candidate set E, set up a cluster, take point P and other centroid points in its neighborhood as A member of the same cluster, then the grid cells they represent and the points they contain are also in the same cluster, and set the same label for all points in this cluster to distinguish it from other clusters ; Select a centroid point from the candidate set E, and also calculate the centroid points contained in the ε-neighborhood of the centroid point and perform cluster division until there are no elements in the candidate set E, and the clustering cluster is initially completed; then, the core The determined core point objects in the point set S are removed, and then arbitrarily select a point to continue the above operation until the elements in the core point set S are empty;

2.1.5) When the ε-neighborhood in step 2.1.4) contains point search, in order to improve the search speed, a KD-Tree is constructed to search for the nearest neighbor point:

2.1.5.1) Determine whether the input dataset is empty, if it is an empty dataset, return an empty KD-Tree, otherwise perform the following operations;

2.1.5.2) Node generation is mainly divided into two parts, namely the determination of the split domain and the determination of Node-data; first, the data variance of all descriptor data (eigenvectors) in each dimension is counted, and the largest value is selected. A corresponding dimension field is used as the value of the split field, and then the data set is sorted according to the determined value of the split field, and the point in the middle is used as Node-data;

2.1.5.3) According to the determined Node-data, divide the left subspace and the right subspace;

2.1.5.4) Construct KD-Tree recursively;

2.1.6) Select the smaller cluster F in the cluster aggregation, set the cluster with the number of points less than 100 as the smaller cluster, analyze the ε-neighborhood search of all points in the cluster, and determine whether the point exists in the neighborhood Points marked as labels of other clusters, if they exist, merge this cluster with the detected cluster, if all points do not exist, divide it into a cluster by itself, until all smaller clusters The clusters have been judged, and then the points representing the cluster labels are stored; finally, all the points are traversed, the same cluster is output according to the label, and different colors are configured to distinguish;

So far, the segmentation results of non-ground obstacles have been obtained, which are represented by independent clusters of different colors, as shown in Figure 2b.

2.2) Multi-feature-based obstacle classification and recognition,

2.2.1) Obtain the following 6 types of features of the clustered clusters obtained by step 2.1) after clustering:

The f ₁ feature is the length, width and height information of the bounding box;

_The f2 feature is the data volume of the data containing points;

The _f3 feature is the eigenvalue information of the three-dimensional covariance matrix describing the clustered cluster data after cluster segmentation. For a three-dimensional point cloud, the covariance matrix H is expressed as:

In formula (12), take cov(x,y) as an example:

cov(x,y)=E{[x-E(x)][y-E(y)]} (13)

In formula (13), taking E(x) as an example, E(x) is the expected or mean value of x, expressed as

Assuming that the clustered data after segmentation contains j points (x ₁ , y ₁ , z ₁ )...(x _j , y _j , z _j ), then any point (x _i , y _i , z _i ) is expressed as follows:

Then all the eigenvalues λ _i of the covariance matrix are obtained according to formula (15):

|H-λE|=0 (15)

The _f4 feature is to describe the distance information between the clustered cluster data after clustering and the unmanned vehicle lidar device, and the average coordinates of the points in the cluster are calculated by formula (16), which is used as the position coordinate assumption of the obstacle clustering. After segmentation, the cluster data contains T points,;

_The f5 feature is to describe the main direction trend information of the cluster data after cluster segmentation. According to different types of obstacles, the distribution trend of the point cloud data is also different. According to the maximum and minimum values of each direction axis in the cluster data Coordinate values and using AABB bounding box to obtain data elevation, width and length, and through combination to obtain the area size, aspect ratio, aspect ratio and other information of cluster data to determine the main direction trend information of the obstacle;

The _f6 feature is the bi-view shape outline information describing the clustered cluster data after cluster division. By analyzing the shape and outline information of the left view and front view of the clustered cluster data, the type of obstacles represented by the clustered point cloud data can be judged fuzzy.

2.2.2) Obstacle recognition based on JointBoost classification method,

2.2.2.1) Use the six types of features extracted in step 2.2.1 ₎ except the f

2.2.2.2) Select the appropriate sample data set and mark the respective category labels to train the JointBoost classifier, and then classify and identify the test data through the trained classifier to obtain the initial classification result,

The realization of multi-classification by JointBoost is similar to that of SVM multi-classification. It is realized by converting the problem into multiple binary classification combinations. During training, input m pairs of training point cloud feature vectors and corresponding class labels (z _i , c _i ), In the iterative process of each training, a weak classifier h _m (z _i , c _i ) for each binary classification is trained, and the shared features of multiple categories are found in multiple binary classifications through the minimum loss function. The feature combines multiple weak classifiers into a final strong classifier H _m (z _i , c _i ); when testing, input the feature vector to identify the point cloud cluster, and after the strong classifier classification and identification, output this The probability value of all possible categories of the cluster, the category represented by the largest probability value is the category determined by the feature vector input to the point cloud cluster.

2.2.2.3) Because there may be errors in the classification results of the classifier, the classification results obtained by the classifier are optimized, and the cluster is obtained by combining other feature information contained in the road scene, such as spatial feature information, after initially determining the category. the final recognition result.

The specific optimization process is to first count the JointBoost classifier to obtain the classification probability result set of the cluster as U, and sort the probabilities in descending order of U ₁ , U ₂ , U ₃ ,…,U _n , where The category represented by U ₁ can determine the category of the cluster with a high probability, but there is still the possibility of error, and it needs to be judged twice; then, according to the spatial feature information of obstacles in the actual road scene , using the f ₄ feature, the distance information between the cluster and the LiDAR device of the unmanned vehicle is used to identify its classification result.

When the unmanned vehicle is driving on the road, some basic information of the road, such as road width, will be obtained in advance according to the actual situation. Combined with the road width and the distance information from the cluster to the radar device, the identification result of the cluster classifier is used for secondary discrimination.

通过二者的大小比较能够作为确定一个类别信息的判决条件，其判决规则为：若

那么该障碍物已经远离道路区域，属于车辆类别的障碍物概率较低；若

则该障碍物聚类簇属于建筑物等其他类别障碍物的概率低；The average distance of the three coordinate directions of the cluster from the origin is obtained by formula (16). According to the experimental data, the X-axis direction is the road extension direction, and the Y-axis direction is the road width direction; set the road width as W, then a certain The distance to the origin in the width direction of the road is the average of the y-coordinates of all points in the cluster

The comparison of the size of the two can be used as a judgment condition for determining a category of information. The judgment rule is: if

Then the obstacle is far away from the road area, and the probability of the obstacle belonging to the vehicle category is low; if

The probability that the obstacle cluster belongs to other types of obstacles such as buildings is low;

According to the probability set obtained by the JointBoost classification and the secondary discrimination rules, the final classification and recognition result is determined to be:

若最大概率值代表的类别属于车辆类障碍物，则该点云聚类簇便是属于车辆类障碍物；若最大概率值代表的类别属于标志杆树木行人类障碍物，则该点云聚类簇便是属于道路的标志杆树木行人类；若最大概率值代表的类别属于建筑物类障碍物，则此次识别可能错误，重新进行分类，若结果相同则以此为识别结果；if

If the category represented by the maximum probability value is a vehicle obstacle, the point cloud cluster is a vehicle obstacle; if the category represented by the maximum probability value belongs to a sign pole, trees, pedestrians, and a human obstacle, the point cloud cluster The clusters are the signposts, trees and pedestrians belonging to the road; if the category represented by the maximum probability value is a building obstacle, the identification may be wrong this time, and the classification is re-classified. If the results are the same, this is the identification result;

若最大概率值代表的类别属于建筑物类障碍物，则该聚类簇便是属于建筑物类障碍物；若最大概率值代表的类别属于标志杆树木行人类障碍物，则该点云聚类簇便是属于道路的标志杆树木行人类；若最大概率值代表的类别属于车辆类障碍物，则此次识别可能错误，重新进行分类，若结果相同则以此为识别结果。if

If the category represented by the maximum probability value belongs to a building obstacle, the cluster is a building obstacle; if the category represented by the maximum probability value belongs to a sign pole, trees, and human obstacles, the point cloud clustering The clusters are the signposts, trees, pedestrians and people belonging to the road; if the category represented by the maximum probability value belongs to the vehicle obstacle, the identification may be wrong this time, and the classification is re-classified. If the results are the same, this is the identification result.

After the above steps, step 2.2.1) and step 2.1.2), the obstacle classification and recognition result is obtained, as shown in Figure 2c.

Step 3, carry out road boundary detection and passable area analysis,

3.1) Design a road boundary extraction method suitable for vehicle-mounted lidar data by using the elevation mutation of data points. After extracting road boundary points, use prior knowledge to screen the boundary points, and use the least squares method to fit the road boundary line;

3.1.1) Count the Z-axis coordinate values of all points in the lidar point cloud data, and determine the height threshold G of the road boundary according to the road environment; then use the idea of sliding windows in the image to count the sudden changes in the Z-coordinates of the point cloud data points in the window. (that is, the change of the Z coordinate is greater than G), mark it, and the mutation points of these marks are the candidate points of the road boundary; about the determination of the height threshold G, because in the actual situation, curbs, road vehicles, green belts The height difference between buildings, buildings, etc. is large, so it needs to be judged according to the road scene. According to the experimental experience, the height threshold G of the straight road is about 1m, and the height threshold G of the curved road scene area is about 0.5m; according to the elevation distribution and the determined height Threshold G, use the sliding window idea to determine the elevation mutation area in the data, and then determine the mutation point,

First, the lidar point cloud data is cross-cut according to the road extension direction (X-axis direction), and the data is cut into multiple sub-point cloud data with a width of 0.5m along the X direction, and then one of the data is taken out and the following operations are performed:

Operation 1: Perform grid processing on the sub-point cloud segments, divide the point cloud data into grid cells with a length and width of 0.5m each along the Y-axis, and record them in the grid cell sequence F;

Operation 2: Take a certain unit Fi in sequence from the grid unit sequence F, calculate the maximum elevation H of the grid unit, and compare it with the determined height threshold G: if H<G, the grid unit is judged to be close Ground data, do not extract road boundary candidate points; if H>G, the grid cell may contain boundary candidate points, record the grid cell serial numbers in order to form a new grid cell sequence K that needs to extract candidate points;

Operation 3: Use the sliding window idea to extract the candidate road boundary points contained in each grid in the grid unit sequence K, process the grids from left and right at the same time, traverse all points in the entire grid, and move to the left. On the premise that the Z coordinate value is the smallest, the grid cell with the smallest Y coordinate value is used as the candidate point, and the grid cell in the right direction takes the point with the largest Y coordinate value on the premise that the Z coordinate value is the smallest as the candidate point;

Operation 4: Select another sub-point cloud segment to perform the above operations to find road boundary candidate points, until all sub-point clouds have been processed to obtain all road boundary candidate points.

3.1.2) Screen the candidate points of the road boundary, and eliminate the candidate points in the non-road edge area,

Use the ground data obtained in step 1 to extract effective prior knowledge, regard the extracted ground data as a road surface, and obtain two Constraint line, select candidate points within a distance of 0.5m on the left and right sides of the two lines, eliminate other candidate points outside the constraint line area, and finally obtain the point sequence of the two road boundary points, with the points in the respective sequences as the final Road boundary points, fit road boundary lines;

For the detour scene, to obtain the constraint line, the method of segmentation in the ground segmentation in step 1.3) is used. After the preliminary ground data of each segment is extracted in step 1, the approximate width of this segment of data is recorded as the constraint of this segment of data. condition, and then screen the mutation points obtained by each sub-point cloud segment in the candidate point extraction stage, obtain the correct road boundary point of the sub-point cloud segment, and finally combine the correct boundary points of each sub-point cloud segment to get Complete scene boundary points;

3.1.3) Use the least squares method for road boundary fitting, determine a function model to fit the target data, calculate the function model data to minimize the square sum of the error with the target data, and obtain the parameter value of the function model,

Assuming that the n target data to be fitted are (x ₁ , y ₁ ; x ₂ , y ₂ ; L; x _n , y _n ;), the fitted curve model equation is:

y=Ax ² +Bx+C (17)

where A, B, and C are any real numbers, and the expression for solving the minimum error sum of squares is:

When the error is the smallest, A, B, and C are the best estimated parameters. Therefore, the partial derivatives of the three parameters of A, B, and C are calculated to obtain the formula:

Then, the system of equations about parameters A, B, C is obtained, which is expressed in matrix form as:

The parameter values of A, B, and C can be obtained by solving the matrix. At this time, the function model can be determined, and the curve represented by the model is the curve fitted by the target data. The coordinate values are used as input to fit the road boundary line to obtain the road boundary detection result, as shown in Figure 3a.

3.2) Use the grid to mark the barrier-free area to realize the detection of the passable area in the lidar road scene;

3.2.1) Taking the lidar point cloud scene after removing the ground data as the input, assuming that the two boundary lines obtained by the road boundary detection are l ₁ and l ₂ , then the area between the two curves is the road area; Lidar is real road condition information collected in real time. Other vehicles, pedestrians, billboards, etc. driving on the road are obstacles compared to radar vehicles. Unmanned vehicles must avoid these obstacles to avoid accidents. Then the area where the obstacles are located It is the area where the radar vehicle cannot travel; the non-road area outside the two road boundary curves l ₁ and l ₂ is divided, and only the road area between the boundary lines is considered; On the premise of considering the elevation, divide the 3D point cloud scene into a series of grid blocks of equal size, and select a regular quadrilateral with a distance of 0.5m in the X and Y directions for division;

3.2.2) After the road data is processed into grids, each grid is discriminated to determine whether the grid is a grid cell containing obstacle data points, and is divided by counting whether there is point cloud data in the grid cells. Which type of grid does this grid unit belong to? If the grid contains point cloud data, it is determined as an obstacle grid, and if the grid does not contain point cloud data, it is a passable area grid;

3.2.3) The eight-neighbor labeling method is used for judgment, and the grid cells determined as passable areas are marked and expanded,

First, set all grid cell sequences as GridSeq, and determine the passable area grid cell sequence as PassSeq, then arbitrarily select a grid as a seed unit in all grid cell sequences GridSeq, and search for the upper part of the grid seed by looping. , bottom, left, right, top left, top right, bottom left, bottom right eight adjacent grid cells; if the searched grid cell meets the conditions of the passable area grid, it will be marked as the passable area label "1", And add this grid unit to the passable area grid sequence PassSeq; if it does not match, mark it as "0", and then remove the grid unit from the sequence GridSeq; loop processing until the grid sequence GridSeq If it is empty, the grid cells of the passable area in the data are preliminarily determined;

3.2.4) Find the obstacles on the two boundary lines according to the obstacle segmentation implemented in step 2, project them along the road extension direction, and determine the contour shape of the point cloud data point distribution of the obstacles,

According to the actual scene in real life, the billboards on both sides of the road and the extended branches, the main contour shapes are mostly "┌" or "┐". The obstacle is determined to be a suspended obstacle, and the unmanned vehicle can pass, so the grid cell corresponding to the obstacle determined to be passable is changed and marked as "green", indicating that the grid is a passable area grid. ;

3.2.5) Using the obstacle location information, structure information and other features obtained by obstacle segmentation and identification, combined with the determined road passable area, complete the prediction and evaluation of the accessibility path of the unmanned vehicle in this road scene,

The vehicle width of the unmanned vehicle is set to 1.7m. In order to ensure smooth passage without touching obstacles such as other vehicles, a reserved space of 0.3m is added to the left and right of the unmanned vehicle, so the overall passable width should be guaranteed to be greater than L=2.3 The distance of m; on the basis of completing the obstacle segmentation, determine the position of the obstacles on the road surface, calculate the volume of these obstacles with the AABB bounding boxes of the respective obstacles, and use the detected two boundary lines to obtain the obstacle The width of the passable area between objects or between obstacles and the boundary line, and then compared with the determined minimum safe passable distance L to obtain whether the width here can ensure the safe passage of unmanned vehicles.

Claims (8)

1. a road environment element perception method based on lidar, is characterized in that, is implemented according to the following steps: Step 1, down-sampling the original lidar point cloud data, acquiring the region of interest, obtaining the simplified point cloud data and segmenting the ground data, and obtaining the result. The specific process is: 1.1) Implement the downsampling algorithm based on the voxel grid to perform data reduction operations; 1.2) Eliminate discrete points and long-distance useless points, and obtain areas of interest for subsequent processing; 1.3) Divide the simplified data obtained in steps 1.1) and 1.2) into ground data. Based on the RANSAC plane detection algorithm, the data is segmented and calibrated and then the ground is segmented, so as to achieve common ground extraction for complex scenes. suitability; Step 2, implement obstacle segmentation and obstacle recognition, 2.1) Using voxel-based DBSCAN clustering algorithm to achieve obstacle segmentation of non-ground data; 2.2) Multi-feature-based obstacle classification and recognition; Step 3, carry out road boundary detection and passable area analysis, 3.1) Design a road boundary extraction method suitable for vehicle-mounted lidar data by using the elevation mutation of data points. After extracting road boundary points, use prior knowledge to screen the boundary points, and use the least squares method to fit the road boundary line; 3.2) Use the grid to mark the barrier-free area to realize the detection of the passable area in the lidar road scene, and that's it. 2. The road environment element perception method based on lidar according to claim 1, is characterized in that, in described step 1.1), the concrete process is: According to the density of the point cloud data distribution, select the three side lengths of the appropriate grid cell, split the point cloud data into small voxel grids, count all the points contained in the cell, and calculate their centroids as the whole The representative of all points in the grid unit, the centroid points of all grid units are combined to form new data, and the downsampling is completed. 1.1.1) Read the point cloud data of the original lidar; 1.1.2) Calculate the maximum and minimum points in the point cloud data, that is, the upper right point maxPoint and the lower left point minPoint of the point cloud bounding box, so as to calculate the length Lx, width Ly, and height Lz of the point cloud bounding box; 1.1.3) Set the length Vx, width Vy, and height Vz of the voxel grid unit; divide the point cloud data into a voxel grid to obtain m×n×s units, where m=[Lx/Vx], n=[Ly/Vy], s=[Lz/Vz], the symbol "[]" is the rounding symbol to ensure that the number of grid cells is an integer; 1.1.4) Randomly select any point p, then the grid cell corresponding to point p is:

The index of the one-dimensional grid cell number to which point p belongs is: Index=I _{index_x} *1+I _{index_y} *(m+1)+I _{index_z} *(m+1)*(n+1) (2) 1.1.5) Traverse all the points of the origin cloud and insert the points with the same grid cell number Index into the same Index_vector vector; 1.1.6) Calculate the centroid G(x, y, z) of L points in the grid unit where the same numbered point is located as a representative point to achieve downsampling. The calculation formula is as follows:

3. The method for perceiving road environment elements based on lidar according to claim 2, wherein, in the described step 1.2), For the point cloud data obtained by the vehicle-mounted lidar, the central blank circular area is where the lidar device is located. The data takes the forward direction of the vehicle as the positive direction of the X-axis, the right direction of the vehicle is the positive direction of the Y-axis, and the upward direction is the positive direction of the Z-axis; by counting the density of the points on both sides of the vehicle's forward direction, that is, the direction of the Y-axis, and comparing it with the set threshold, it can be divided into whether it belongs to the area of interest. The specific process is: 1.2.1) Project the downsampled point cloud data to the yoz plane; 1.2.2) Obtain the projection data from the maximum data Y _min to the minimum data Y _max in the Y-axis direction, and divide the data into M segments in this area; 1.2.3) Count the density D _i of the points in each piece of data, and draw the density curve of the entire point cloud data; 1.2.4) Calculate the total density ratio r of each segment density by formula (4), and set the threshold value

Compare and judge from the leftmost end, if

It is considered that this paragraph has a low density and contains less information, and this paragraph is deleted; continue to compare the next paragraph, if there is

Stop this judgment; then start the judgment from the far right, if

delete this segment until

when the judgment ends,

1.2.5) For the forward direction of the vehicle, select 30m before and after the lidar device as the region of interest in the X-axis direction, use the pass-through filtering method to divide the region, and obtain the down-sampled region of interest as the final simplified scene data. . 4. the road environment element perception method based on lidar according to claim 3, is characterized in that, in described step 1.3), concrete process is: 1.3.1) Calculate the minimum value min_x and the maximum value max_x along the X-coordinate axis of the vehicle's driving direction, and divide the point cloud data after simplified processing into N segments of sub-point cloud data with a length of 1m along the X-axis direction, where N=ROUNDUP (max_x-min_x), ROUNDUP(x) is a round-up function; 1.3.2) For each segment of sub-point cloud data, the RANSAC plane detection algorithm is used to detect the ground part of this segment of sub-point cloud data, and the general equation to obtain the fitting plane is: Ax+By+Cz+D=0, where A, B, C, D are known constants, and A, B, C are not zero at the same time, the normal vector V=(A, B, C); In addition, when using lidar to collect data, the Z axis in the radar coordinate system is kept vertical, then the vertical vector is Q=(0, 0, 1), and the normal vector of the ground Plane obtained by calculating the fitting The calibration matrix of V and vertical vector Q is called rotation matrix T, and the obtained rotation matrix T is used to calibrate the sub-point cloud data. The specific calibration operation is as follows: It is known that the vector before calibration is V and the vector after calibration is Q, then: V·Q＝|V||Q|cosθ (5) Then the angle between V and Q is:

Assuming that the vector V before calibration is (a1, a2, a3), and the vector Q after calibration is (b1, b2, b3), and the rotation axis C (c1, c2, c3) is obtained according to the definition of the cross product of the vectors, there are:

Let the rotation axis C correspond to a unit vector k (k _x , _ky , k _z ), using the rotation angle θ and the unit vector k, according to the Rodrigue rotation formula, an arbitrary vector u in the space rotates along the unit vector k by the angle θ after The resulting vector w is: w=ucosθ+(k·u)k(1-cosθ)+(k·u)sinθ (8) Thus, the corresponding rotation matrix T is obtained as:

1.3.3) Realize the ground segmentation of this sub-point cloud data based on the RANSAC plane detection algorithm. The specific steps are: 1.3.3.1) Input the calibrated sub-point cloud data CloudPoint, give the plane model and set the distance threshold t; 1.3.3.2) Randomly sample three points in the point cloud data so that these three points are not on the same straight line, and solve the plane model equation formed by the three random sample points; 1.3.3.3) Calculate the distance dis from other points of the point cloud data to the plane, and compare it with the set distance threshold t to obtain an intra-office point set IncloudSet based on the plane model; 1.3.3.4) Count the number of IncloudSets in the in-office point set of the plane model, compare it with the current maximum number, and keep the largest number of the two; 1.3.3.5) Re-estimate the new plane model by keeping the set of all intra-office points with the largest number, and output the intra-office point as the ground point for this calculation; 1.3.3.6) Re-sampling and repeat the above steps; when the number of iterative calculations reaches the maximum number of iterations, exit the iterative loop, select the optimal plane model and the ground point with the largest number of points in the output bureau during the iteration process, and the ground point obtained at this time is is the ground data detected by the point cloud; 1.3.4) Combine the ground data detected by each sub-point cloud data to obtain the final ground data, and realize the segmentation of ground and non-ground data. 5. The method for perceiving road environment elements based on lidar according to claim 4, wherein, in the described step 2.1), the specific process is: 2.1.1) Use the non-ground lidar point cloud scene data as input to divide the voxel grid cells, set the grid cell side length d to 15cm, and obtain the point cloud data X, Y, and Z coordinate axes through calculation. The maximum and minimum values are calculated by using the set side length d of the grid unit to obtain the number of layers m, n, and s of each coordinate axis of the divided grid unit. Taking the X coordinate axis as an example, min_X is the minimum coordinate of the X axis, and max_X is the The maximum coordinate of the X-axis is:

The Y-axis and Z-axis are consistent with the processing methods of the above-mentioned X-axis. After the above steps, the voxel grid unit division of the unit side length d of the scene data can be obtained; 2.1.2) Count the number of points contained in all grid cells, record all non-empty grid cells, and mark these grid cells reasonably to ensure that the overall structure of these grid cells is the same as the original data location information, and determine a certain grid cell. The grid cells in the neighborhood around a grid cell are the same as the original data; According to the set parameter threshold MinPts, each non-empty grid cell is judged. If the number of points contained in the grid cell is greater than MinPts, the grid cell is set as the core cell, and the contained points are set as the core point; if If the number of points contained in the grid cell is less than MinPts, a second judgment is required; Perform an ε-neighborhood search on the points in this grid cell to determine whether there is a neighborhood point located in the core unit in the neighborhood. , other points will no longer be judged; if the neighborhood point does not exist, select other points in this grid cell for judgment, until all points have been judged, there is still no neighborhood point located in other core cells, then directly judge this The points in the grid cells are noise points; 2.1.3) Calculate the centroid Q containing R points in each non-noise grid cell in 1.1.2):

2.1.4) Define the calculated set of centroid points as the core point set S, and randomly select any core point P from the set. If there are no less than MinPts points within the radius distance ε of the point P, then the point P is the core point , if not, then this point P is a noise point, calculate other centroid points contained in its ε-neighborhood in turn and add them to the candidate set E, set up a cluster, take point P and other centroid points in its neighborhood as A member of the same cluster, then the grid cells they represent and the points they contain are also in the same cluster, and set the same label for all points in this cluster to distinguish it from other clusters ; Select a centroid point from the candidate set E, and also calculate the centroid points contained in the ε-neighborhood of the centroid point and perform cluster division until there are no elements in the candidate set E, and the clustering cluster is initially completed; then, the core The determined core point objects in the point set S are removed, and then arbitrarily select a point to continue the above operation until the elements in the core point set S are empty; 2.1.5) When the ε-neighborhood contains point search in step 2.1.4), construct a KD-Tree to search the nearest neighbor point: 2.1.5.1) Determine whether the input dataset is empty, if it is an empty dataset, return an empty KD-Tree, otherwise perform the following operations; 2.1.5.2) Node generation is mainly divided into two parts, namely the determination of the split domain and the determination of Node-data; first, the data variance of all descriptor data in each dimension is counted, and the one corresponding to the largest value is selected. The dimension field is used as the value of the split field, and then the data set is sorted according to the determined value of the split field, and the point in the middle is used as Node-data; according to the determined Node-data, the left subspace and the right subspace are divided; recursion Build KD-Tree; 2.1.6) Select the smaller cluster F in the cluster aggregation, set the cluster with the number of points less than 100 as the smaller cluster, analyze the ε-neighborhood search of all points in the cluster, and determine whether the point exists in the neighborhood Points marked as labels of other clusters, if they exist, merge this cluster with the detected cluster, if all points do not exist, divide it into a cluster by itself, until all smaller clusters The clusters have been judged, and then the points representing the cluster labels are stored; finally, all the points are traversed, the same cluster is output according to the label, and different colors are configured to distinguish; At this point, the segmentation results of non-ground obstacles are obtained, which are reflected in independent clusters of different colors. 6. The method for perceiving road environment elements based on lidar according to claim 5, characterized in that, in the described step 2.2), the specific process is: 2.2.1) Obtain the following 6 types of features of the clustered clusters obtained by step 2.1) after clustering: The f ₁ feature is the length, width and height information of the bounding box; _The f2 feature is the data volume of the data containing points; The _f3 feature is the eigenvalue information of the three-dimensional covariance matrix describing the clustered cluster data after cluster segmentation. For a three-dimensional point cloud, the covariance matrix H is expressed as:

In formula (12), take cov(x, y) as an example: cov(x, y)=E{[x-E(x)][y-E(y)]} (13) In formula (13), taking E(x) as an example, E(x) is the expected or mean value of x, expressed as

Assuming that the clustered data after segmentation contains j points (x ₁ , y ₁ , z ₁ )... (x _j , y _j , z _j ), then any point ( _xi , y _i , z _i ) is expressed as follows:

Then all the eigenvalues λ _i of the covariance matrix are obtained according to formula (15): |H-λE|=0 (15) The _f4 feature is to describe the distance information between the clustered cluster data after clustering and the unmanned vehicle lidar device, and the average coordinates of the points in the cluster are calculated by formula (16), which is used as the position coordinate assumption of the obstacle clustering. After segmentation, the cluster data contains T points,;

_The f5 feature is to describe the main direction trend information of the cluster data after cluster segmentation. According to different types of obstacles, the distribution trend of the point cloud data is also different. According to the maximum and minimum values of each direction axis in the cluster data Coordinate values and using AABB bounding box to obtain data elevation, width and length, and through combination to obtain the area size, aspect ratio, aspect ratio and other information of cluster data to determine the main direction trend information of the obstacle; The feature f6 is to describe the dual _- view shape and outline information of the clustered cluster data after clustering and segmentation. By analyzing the shape and outline information of the left and front views of the clustered cluster data, the obstacles represented by the clustered point cloud data can be fuzzy judged. species; 2.2.2) Obstacle recognition based on JointBoost classification method, 2.2.2.1) Use the six types of features extracted in step 2.2.1 ₎ except the f 2.2.2.2) Select the appropriate sample data set and mark the respective category labels to train the JointBoost classifier, and then classify and identify the test data through the trained classifier to obtain the initial classification result, The realization of multi-classification by JointBoost is similar to that of SVM multi-classification. It is realized by converting the problem into multiple binary classification combinations. During training, input m pairs of training point cloud feature vectors and corresponding class labels (z _i , c _i ), In the iterative process of each training, a weak classifier h _m (z _i , c _i ) for each binary classification is trained, and the shared features of multiple categories are found in multiple binary classifications through the minimum loss function. The feature combines multiple weak classifiers into a final strong classifier H _m (z _i , c _i ); when testing, input the feature vector to identify the point cloud cluster, and after the strong classifier classification and identification, output this The probability value of all possible categories of the cluster, the category represented by the largest probability value is the category determined by the feature vector input to the point cloud cluster. 2.2.2.3) Because there may be errors in the classification results of the classifier, the classification results obtained by the classifier are optimized, and the cluster is obtained by combining other feature information contained in the road scene, such as spatial feature information, after initially determining the category. The final recognition result, The specific optimization process is to first count the JointBoost classifier to obtain the classification probability result set of the cluster as U, and sort the probabilities in descending order of U ₁ , U ₂ , U ₃ ,…,U _n , where The category represented by U ₁ can determine the category of the cluster with a high probability, but there is still the possibility of error, and it needs to be judged twice; then, according to the spatial feature information of obstacles in the actual road scene , using the f ₄ feature, the distance information between the cluster and the LiDAR device of the unmanned vehicle is used to identify its classification result. When the unmanned vehicle is driving on the road, some basic information of the road, such as road width, will be obtained in advance according to the actual situation. Combined with the road width and the distance information from the cluster to the radar device, the identification result of the cluster classifier is used for secondary discrimination. The average distance of the three coordinate directions of the cluster from the origin is obtained by formula (16). According to the experimental data, the X-axis direction is the road extension direction, and the Y-axis direction is the road width direction; set the road width as W, then a certain The distance to the origin in the width direction of the road is the average of the y-coordinates of all points in the cluster

The comparison of the size of the two can be used as a judgment condition for determining a category of information. The judgment rule is: if

Then the obstacle is far away from the road area, and the probability of the obstacle belonging to the vehicle category is low; if

The probability that the obstacle cluster belongs to other types of obstacles such as buildings is low; According to the probability set obtained by the JointBoost classification and the secondary discrimination rules, the final classification and recognition result is determined to be: if

If the category represented by the maximum probability value is a vehicle obstacle, the point cloud cluster is a vehicle obstacle; if the category represented by the maximum probability value belongs to a sign pole, trees, pedestrians, and a human obstacle, the point cloud cluster The clusters are the signposts, trees and pedestrians belonging to the road; if the category represented by the maximum probability value is a building obstacle, the identification may be wrong this time, and the classification is re-classified. If the results are the same, this is the identification result; if

If the category represented by the maximum probability value belongs to a building obstacle, the cluster is a building obstacle; if the category represented by the maximum probability value belongs to a sign pole, trees, and human obstacles, the point cloud clustering The clusters are the signposts, trees, pedestrians and people belonging to the road; if the category represented by the maximum probability value belongs to the vehicle obstacle, the identification may be wrong this time, and the classification is re-classified. If the results are the same, this is the identification result. After the above steps, step 2.2.1) and step 2.1.2), the obstacle classification and recognition result is obtained. 7. The road environment element perception method based on lidar according to claim 6, is characterized in that, in described step 3.1), concrete process is: 3.1.1) Count the Z-axis coordinate values of all points in the lidar point cloud data, and determine the height threshold G of the road boundary according to the road environment; then use the idea of sliding windows in the image to count the sudden changes in the Z-coordinates of the point cloud data points in the window. These marked points are the candidate points of the road boundary; according to the elevation distribution and the determined height threshold G, the sliding window idea is used to determine the elevation mutation area in the data, and then the mutation point is determined. First, the lidar point cloud data is cross-cut according to the road extension direction, and the data is cut into multiple sub-point cloud data with a width of 0.5m along the X direction, and then one of the data is taken out and the following operations are performed: Operation 1: Perform grid processing on the sub-point cloud segments, divide the point cloud data into grid cells with a length and width of 0.5m each along the Y-axis, and record them in the grid cell sequence F; Operation 2: Take a certain unit Fi in sequence from the grid unit sequence F, calculate the maximum elevation H of the grid unit, and compare it with the determined height threshold G: if H<G, the grid unit is judged to be close Ground data, do not extract road boundary candidate points; if H>G, the grid cell may contain boundary candidate points, record the grid cell serial numbers in order to form a new grid cell sequence K that needs to extract candidate points; Operation 3: Use the sliding window idea to extract the candidate road boundary points contained in each grid in the grid unit sequence K, process the grids from left and right at the same time, traverse all points in the entire grid, and move to the left. On the premise that the Z coordinate value is the smallest, the grid cell with the smallest Y coordinate value is used as the candidate point, and the grid cell in the right direction takes the point with the largest Y coordinate value on the premise that the Z coordinate value is the smallest as the candidate point; Operation 4: Select another sub-point cloud segment to perform the above operations to find road boundary candidate points, until all sub-point clouds have been processed to obtain all road boundary candidate points; 3.1.2) Screen the candidate points of the road boundary, and eliminate the candidate points in the non-road edge area, Use the ground data obtained in step 1 to extract effective prior knowledge, regard the extracted ground data as a road surface, and obtain two Constraint line, select candidate points within a distance of 0.5m on the left and right sides of the two lines, eliminate other candidate points outside the constraint line area, and finally obtain the point sequence of the two road boundary points, with the points in the respective sequences as the final Road boundary points, fit road boundary lines; For the detour scene, to obtain the constraint line, the method of segmentation in the ground segmentation in step 1.3) is used. After the preliminary ground data of each segment is extracted in step 1, the approximate width of this segment of data is recorded as the constraint of this segment of data. condition, and then screen the mutation points obtained by each sub-point cloud segment in the candidate point extraction stage, obtain the correct road boundary point of the sub-point cloud segment, and finally combine the correct boundary points of each sub-point cloud segment to get Complete scene boundary points; 3.1.3) Use the least squares method for road boundary fitting, determine a function model to fit the target data, calculate the function model data to minimize the square sum of the error with the target data, and obtain the parameter value of the function model, Assuming that the n target data to be fitted are (x ₁ , y ₁ ; x ₂ , y ₂ ; L; x _n , y _n ;), the fitted curve model equation is: y=Ax ² +Bx+C (17) Where A, B, and C are any real numbers, the expression for solving the minimum error sum of squares is:

When the error is the smallest, A, B, and C are the best estimated parameters. Therefore, the partial derivatives of the three parameters of A, B, and C are calculated to obtain the formula:

Then, the system of equations about parameters A, B, C is obtained, which is expressed in matrix form as:

The parameter values of A, B, and C can be obtained by solving the matrix. At this time, the function model can be determined, and the curve represented by the model is the curve fitted by the target data. The coordinate values are used as input to fit the road boundary line and obtain the road boundary detection result. 8. The method for perceiving road environment elements based on lidar according to claim 7, characterized in that, in the described step 3.2), the specific process is: 3.2.1) Taking the lidar point cloud scene after removing the ground data as the input, assuming that the two boundary lines obtained by the road boundary detection are l ₁ and l ₂ , then the area between the two curves is the road area; The non-road areas outside the two road boundary curves l ₁ and l ₂ are divided, and only the road area between the boundary lines is considered; the road area data is rasterized, and the 3D point cloud The scene is divided into a series of grid blocks of equal size, and a regular quadrilateral with a distance of 0.5m in both the X and Y directions is selected for division; 3.2.2) After the road data is processed into grids, each grid is discriminated to determine whether the grid is a grid cell containing obstacle data points, and is divided by counting whether there is point cloud data in the grid cells. Which type of grid does this grid unit belong to? If the grid contains point cloud data, it is determined as an obstacle grid, and if the grid does not contain point cloud data, it is a passable area grid; 3.2.3) The eight-neighbor labeling method is used for judgment, and the grid cells determined as passable areas are marked and expanded, First, set all grid cell sequences as GridSeq, and determine the passable area grid cell sequence as PassSeq, then arbitrarily select a grid as a seed unit in all grid cell sequences GridSeq, and search for the upper part of the grid seed by looping. , bottom, left, right, top left, top right, bottom left, bottom right eight adjacent grid cells; if the searched grid cell meets the conditions of the passable area grid, it will be marked as the passable area label "1", And add this grid unit to the passable area grid sequence PassSeq; if it does not match, mark it as "0", and then remove the grid unit from the sequence GridSeq; loop processing until the grid sequence GridSeq If it is empty, the grid cells of the passable area in the data are preliminarily determined; 3.2.4) Find the obstacles on the two boundary lines according to the obstacle segmentation implemented in step 2, project them along the road extension direction, and determine the contour shape of the point cloud data point distribution of the obstacles, Change the grid cell corresponding to the obstacle determined to be passable as "green", indicating that this grid is a passable area grid; 3.2.5) Use the obstacle location information and structural information features obtained by obstacle segmentation and identification, combined with the determined road passable area, to complete the prediction and evaluation of the accessibility path of the unmanned vehicle in this road scene, The width of the unmanned vehicle is set to 1.7m, and the reserved space for the left and right sides of the unmanned vehicle is increased by 0.3m, so the overall passable width should be guaranteed to be greater than the distance of L=2.3m; on the basis of completing the obstacle segmentation, determine At the position of the obstacles on the road surface, calculate the volume of these obstacles with the AABB bounding boxes of the respective obstacles, and use the detected two boundary lines to obtain the passable between obstacles or between obstacles to the boundary line The width of the area is then compared with the determined minimum safe passable distance L to obtain whether the width here can ensure the safe passage of unmanned vehicles.

Images