CN111325229A - Clustering method for object space closure based on single line data analysis of laser radar - Google Patents

Abstract

The invention discloses a clustering method for closing an object space based on single line data analysis of a laser radar, which comprises the following steps of S1: extracting single line data from the laser radar Velodyne, and mapping each group of single line data to a two-dimensional plane; step S2: extracting object edge lines by using the two-dimensional plane data in the step S1 and using a tangent method for each group of data, and sequentially segmenting and extracting the edges of a single object; step S3: processing the divided object edge point set to obtain the central point of the object and the area occupied by the object in the horizontal direction; step S4: and combining the single line data of all the two-dimensional planes, and determining the final accurate positions and the occupied area in the horizontal direction of all the objects in the three-dimensional space. The method has better robustness for the segmentation and clustering of the space objects with too close distance.

Description

A clustering method for object space closure based on single-line data analysis based on lidar

technical field

The invention relates to the technical field of assisted driving of vehicles, in particular to a clustering method for object space closure based on single-line data analysis of laser radar.

Background technique

Environmental perception is one of the core parts of unmanned driving, of which the positioning and tracking of space objects is the most important part. Lidar, which is widely used today, has quite high accuracy for the detection of target position, speed and other characteristic quantities. Compared with other environmental perception methods, Lidar has considerable advantages.

Lidar is a radar system that emits a laser beam to detect the position, velocity and other characteristic quantities of the target. Its working principle is to transmit a detection signal (laser beam) to the target, and then compare the received signal (target echo) reflected from the target with the transmitted signal, and after proper processing, the relevant information of the target can be obtained, such as Target distance, azimuth, height, speed, attitude, and even shape and other parameters; lidar has the advantages of high resolution, good concealment, strong anti-active interference, good low-altitude detection performance, small size, and light weight.

The process of dividing a collection of lidar point clouds in physical space into multiple classes consisting of similar objects is called point cloud clustering. A cluster generated by clustering is a collection of data objects, which are similar to objects in the same cluster and different from objects in other clusters, and this collection is considered as a single individual.

General clustering algorithms, such as K-Means, mean shift, and DBSCAN clustering algorithms, cluster points in three-dimensional space in one dimension, and calculate the center point of space objects; and most algorithms focus on The change of point cloud density is used to track the position of space objects. When two objects are too close together, these algorithms are prone to misclassify two different objects as the same object; and because the penetration effect of lidar is poor, it cannot be captured. For the points facing away from the lidar, the clustering effect is often only half of the actual object, and even the clustering contour may be deviated. The above factors easily affect the clustering effect, and the effect is very unstable.

SUMMARY OF THE INVENTION

The purpose of the present invention is to solve the problem that when two objects are too close to each other, the point cloud is too dense, and the clustering algorithm will mistake the two objects as the same object. Therefore, The invention proposes a clustering method with better robustness.

In order to solve the deficiencies of existing algorithm clustering, the present invention proposes a clustering method for object space closure based on single-line data analysis of lidar, including the following steps:

Step S1: extracting single-line point cloud sets from the lidar Velodyne to generate multiple sets of data, and then mapping each set of single-line data to a two-dimensional plane;

Step S2: using the two-dimensional plane data in step S1, extract the edge point sets of all objects by using the tangent method for each group of data;

Step S3: Connect the first and last points of the edge point set of each object, the midpoint of the connection line is used as the center, and center symmetry is performed on the point set to complement the edge points on the back of the object to form a closed point set circle ; At this time, the midpoint of the connecting line is the center of the object in the section, and the area occupied by the closed point set circle is the area of the object in the section;

Step S4: Combine all the single-line plane two-dimensional data, and determine the final precise position and the area occupied by the horizontal direction of all objects in the three-dimensional space.

The key of step S1 is to parse the multi-line lidar message protocol, process the collected multi-line lidar point cloud data into a single-line point cloud set, and then map each group of single-line point cloud data to a two-dimensional plane.

The step S2 uses the tangent method to extract the edge point set of all objects, including the following steps:

Step S2A: first select two similar random scatter point pairs in the lidar single-line point set data;

Step S2B: connect the points to generate a straight line, and take two relative, fan-shaped regions with a certain angle and width in the two opposite directions of this straight line;

Step S2C: Find points in the two fan-shaped areas in step S2B, mark the obtained new lidar point, it can be considered that the obtained new lidar point and the two points in step S2A belong to the edge point set of the same object ;

Step S2D: Repeat steps S2B and S2C until the unmarked point cannot be found in the sector area described in step S2B;

Step S2E: Finally, determine whether there are unmarked points in the two-dimensional point set of the plane, and if so, repeat steps S2A, S2B, S2C, and S2D.

Obtaining the center point and the horizontal direction area of the object through the object edge point set described in step S3 includes the following steps:

Step S3A: Through step S2, a point set that approximates an arc can be obtained. The horizontal plane of each arc represents a tangent plane of an object. Connect the two points at the beginning and end of the point set, and use the connecting line as the axis of symmetry to do center symmetry and complement. The point of the surface of the object facing the direction of the radar, then a closed point set of the object section can be obtained, the center is denoted as O, and the height of the section is H;

Step S3B: Using the rotating caliper (rotating jamming) algorithm, the shapes W and V of the circumscribed rectangle of the point set of the tangent plane of the object are obtained.

Step S4 is to combine and iterate the data between different groups. When the edge point sets of the two objects in different groups overlap by more than 50% in the vertical space, it can be considered that the two pairs of information come from the same space object. Different heights, then update the center position and minimum circumscribed square of the object, and iteratively combine different sets of data, and finally obtain the accurate position of the object and the footprint information in the horizontal direction.

Different from the general density-based clustering algorithm, the present invention comprehensively considers the shape factors of the object, and recognizes and divides the object through the change of the contour curve of the object. The effect of uneven density distribution in the vertical direction. Therefore, the present invention has better robustness to the clustering of objects with uneven density distribution in the close distance and vertical direction.

Description of drawings

1 is a flowchart of a clustering method for object space closure based on single-line data analysis of lidar according to the present invention;

FIG. 2 is a schematic diagram of the present invention for obtaining an object edge point set;

3 is a schematic diagram of the clustering principle of the present invention.

Detailed ways

In order to make the objectives, technical solutions and advantages of the present invention clearer, the present invention will be further described in detail below in conjunction with the specific implementation process, as shown in FIG. 1 and with reference to the accompanying drawings.

The invention proposes a clustering method based on single-line data analysis of lidar to close object space. The number of lines that lidar can emit laser ranges from 1 to 128, and correspondingly there are point cloud data of 1 to 128 lines obtained by feedback. , the invention is based on the analysis of the single-line point cloud data of the multi-line radar; when the three-dimensional point distribution of the laser radar is directly observed, the single-line data of the multi-line laser radar can present an obvious object outline on the outer surface of the object, so the invention The key point is to achieve clustering by fitting the outer contour of the object through the point cloud.

First, extract all single-line point clouds from the lidar Velodyne to generate multiple sets of data.

Map each set of single-line data onto a 2D plane, using only x and y in 3D point coordinates (x, y, z), i.e. (x, y).

Use the tangent method to extract the edge point set of all objects on the two-dimensional plane, including the following steps:

Step S2A: in the single-line point set data on the two-dimensional plane, first select two closest random scatter pairs A and B that are not incorporated into the point set, as shown in Figure 2, are classified into the point set S;

Step S2B: connect A and B to generate a straight line, take two opposite ones in the two directions of this straight line, take A and B as vertices, take this straight line as the fan-shaped area of the bisector, the angle threshold of the fan-shaped area and The widths are α and L;

Step S2C: search for points in the fan-shaped area of step S2B, obtain the point A1 in the A direction and the point B1 in the B direction, classify A1 and B1 into the point set S, and mark these two points;

Step S2D: Taking A, A1 and B, B1 as two new sets of point pairs, repeating steps S2B and S2C until no unmarked point can be found in the sector area described in step S2B.

Step S2E: Finally, determine whether there are any unmarked points in the two-dimensional plane, and if so, repeat steps S2A, S2B, S2C, and S2D.

The said obtaining the center point and the horizontal direction area of the object through the object edge point set, as shown in Figure 3, includes the following steps:

Step S3A: Through step S2, a point set that approximates an arc can be obtained. The horizontal plane of each arc represents the tangent plane of an object, and the first and last points of the arc point set are connected, and the line is used as the axis of symmetry to do center symmetry. , to complement the point of the surface of the object facing the direction of the radar, then a closed point set of the tangent plane of the object can be obtained, the center is denoted as O, and the height of the tangent plane is H;

H=(H ₁ +H ₂ +...+H _n )/n

Step S3B: Using the rotating caliper (rotating jamming) algorithm, the shapes W and V of the circumscribed rectangle of the point set of the tangent plane of the object are obtained.

The combined single-line plane two-dimensional data is used to determine the final precise position and the area occupied by the horizontal direction of all objects in the three-dimensional space, such as O ₁ , W ₁ , V ₁ , H ₁ and O ₂ , W ₂ , V ₂ , H ₂ (the two pairs of information are from different groups), when there is more than 50% overlap in the vertical space, it is reasonable to believe that the two pairs of information are from different heights of the same space object, and then update the object's center position and minimum circumscribed Square, constantly superimposed and updated.

O=(O ₁ +O ₂ )/2

H=(H ₁ +H ₂ )/2.

Claims (5)

1. A clustering method for object space closure based on laser radar single line data analysis is characterized in that the number of lines of laser emitted by a laser radar is different from 1 to 128, and correspondingly, point cloud data of 1 to 128 lines are obtained through feedback, the method is based on single line point cloud data analysis of a multi-line radar, and then analysis results of all single lines are combined to realize space object clustering, and comprises the following steps:

step S1: extracting a single-line point cloud set from the laser radar Velodyne to generate a plurality of groups of data, and then mapping each group of data to a two-dimensional plane;

step S2: extracting edge point sets of all objects in the group of data by using the two-dimensional plane data in the step S1 and using a tangent method for each group of data, wherein the edge point set of each object presents a circular arc shape on the two-dimensional plane;

step S3: connecting the first and last points of the edge point set of each object, taking the middle point of the connecting line as the center, and performing central symmetry on the point set to complement the edge points on the back of the object to form a closed point cluster; the middle point of the connecting line is the center of the object on the tangent plane, and the area occupied by the closed point ring is the area of the object on the tangent plane;

step S4: and combining the two-dimensional data of all the single line planes, and determining the final accurate positions and the occupied area in the horizontal direction of all the objects in the three-dimensional space.

2. The method of claim 1, wherein the single line data analysis of the multi-line lidar is performed by directly observing the three-dimensional point cloud distribution of the lidar such that the single line data of the multi-line lidar can present a distinct object contour on the outer surface of the object, and the step S1 is performed by analyzing the multi-line lidar message protocol to process the collected multi-line lidar point cloud data into a single line point cloud set, and then mapping each set of single line point cloud data to a two-dimensional plane.

3. The method for clustering object space closure based on lidar single-line data analysis according to claim 1, wherein the step S2 is to extract the edge point sets of all objects by using a tangent method, comprising the following steps:

step S2A: firstly, selecting two similar random scattered point pairs in the laser radar single line point set data;

step S2B: the connecting point pair generates a straight line, and two opposite fan-shaped areas with certain angles and widths are taken in two opposite directions of the straight line;

step S2C: searching points in the two fan-shaped areas in the step S2B, marking the obtained new laser radar point, and considering that the obtained new laser radar point and the two points in the step S2A belong to an edge point set of the same object;

step S2D: repeating steps S2B, S2C until no unmarked points can be found in the sector area described in step S2B;

step S2E: and finally, judging whether the plane two-dimensional data has unmarked points or not, and if so, repeating the steps S2A, S2B, S2C and S2D.

4. The method for clustering object space closure based on lidar single-line data analysis according to claim 1, wherein the step S3 of obtaining the center point and the horizontal area of the object by the object edge point set comprises the following steps:

step S3A: a point set approximate to circular arcs can be obtained through the step S2, the horizontal plane of each circular arc represents a tangent plane of an object, two points at the head and the tail of the point set are connected, a connecting line is used as a symmetry axis to be centrosymmetric, points of the plane of the object opposite to the radar direction are complemented, and at this time, a closed point set of the tangent plane of the object can be obtained, the center is marked as O, and the height of the tangent plane is H;

step S3B: using a rotating caliper (rotating cassette) algorithm, the shape W, V of the circumscribed rectangle of the object tangent point set is obtained.

5. The method for clustering objects with spatial closure based on single line data analysis of lidar according to claim 1, wherein after steps S1, S2, S3 are completed, a plurality of sets of data are obtained, each set representing a set of edge points of an object obtained by analyzing a certain single line data and detailed attitude information of each object in a tangent plane of the set of points; step S4 is to perform combination iteration on the data between different groups, and when the edge point set tangent planes of two objects in different groups overlap by more than 50% in the vertical space, it can be considered that the two pairs of information come from different heights, i.e. different planes, of the same object in space, then update the center position and the minimum circumscribed square of the object, and continuously iterate and combine the data of different groups, and finally obtain the accurate position of the object and the floor area information in the horizontal direction.

Images