Clustering method and system for vehicle line of crowdsourced map, and storage medium

[0001] This application claims priority to Chinese Patent Application No. 202310107097.5, filed Feb. 13, 2023, the contents of which are incorporated by reference herein in their entirety.

[0002] The present disclosure belongs to the technical field of high-precision maps, and specifically relates to a clustering method and system for a vehicle line of a crowdsourced map, and a storage medium.

[0003] The development of artificial intelligence has driven the development of autonomous driving technology rapidly, making the autonomous driving technology highly concerned by the society. The implementation of autonomous driving relies on the assistance of high-precision maps, and the use of crowdsourced maps can collect lane-level vehicle line information. The vehicle line information of roads can be roughly divided into dotted lines, long lines, double solid lines, double dotted lines, and other types of lines. As the most basic constraints and traffic signs for vehicles in the process of driving on the road, vehicle lines can be effectively detected and play a key role in the play of autonomous driving systems.

[0004] At present, most consider only clustering of road lane lines, but lack clustering of complex vehicle line information. For example, patent document CN111695389A discloses a clustering method and apparatus for a vehicle line, where the method mentions a method for extracting pixel points related to a lane line from a lane line image to form eigenvectors for clustering and horizontally clustering selected feature point groups according to preset conditions, which has good clustering effects on Y-shaped and V-shaped roads. However, the method excessively relies on preset rules and preset lane reservation conditions in the early stage, and cannot be applied to clustering of complex vehicle lines. For another example, in a clustering method and apparatus for a lane line instance, an electronic device, and a storage medium disclosed in patent document CN112084988A, a lane line eigenvector histogram is mainly obtained according to binary segmentation results of a lane line and lane line eigenvectors, thereby achieving clustering. However, the method has high computational complexity and high quality requirements for clustering networks, and cannot be compatible with poor data sources.

[0005] Common clustering methods for lane lines are mostly based on images or features thereof, which cannot distinguish complex vehicle line information well. When faced with a huge data volume and poor data sources, computed quantities of the clustering methods increase greatly, thereby seriously affecting the recognition results of vehicle lines.

[0006] Therefore, it is necessary to develop a clustering method for a vehicle line of a crowdsourced map, a storage medium, a device, and a vehicle.

[0007] The present disclosure aims to provide a clustering method and system for a vehicle line of a crowdsourced map, and a storage medium, which can achieve clustering of complex vehicle lines with high computational efficiency.

[0008] In a first aspect, a clustering method for a vehicle line of a crowdsourced map described in the present disclosure includes the following steps:

• • [0009] S1: collecting road element object data of the crowdsourced map, and classifying and extracting vehicle line road elements to obtain to-be-clustered data lists of different vehicle lines;
  • [0010] S2: computing a mean Z value of each sample in the to-be-clustered data list of the vehicle line to obtain a mean Z value list of the vehicle line; computing centroid coordinates of each sample in the to-be-clustered data list of the vehicle line to obtain a centroid coordinate list of the vehicle line;
  • [0011] S3: looping through the to-be-clustered data list of the vehicle line to obtain a current sample, and determining E neighborhood samples of the current sample to obtain an E neighborhood sample list of the current sample;
  • [0012] S4: obtaining a mean Z value of the current sample from the mean Z value list of the vehicle line, randomly obtaining an E neighborhood sample from the E neighborhood sample list of the current sample, computing a difference between the mean Z value of the current sample and the mean Z value of the E neighborhood sample, performing distance threshold determination when the difference between the two is less than a preset difference threshold, and putting the samples that conform to the distance threshold determination into a first list of the current sample until the E neighborhood sample list of the current sample is fully looped through;
  • [0013] S5: using the current sample as a nucleus seed if a length of the first list of the current sample is greater than a minimum clustering sample number threshold, and storing, with the current sample, data that conform to the distance threshold determination;
  • [0014] S6: repeating steps S3 to S5 until all nucleus seeds that meet requirements and data associated with the nucleus seeds are found;
  • [0015] S7: looping through a nucleus seed list to obtain a cluster CK where the current sample is located, finding all nucleus seeds located in the current cluster CK, and updating the nucleus seed list until all the nucleus seeds are clustered; and
  • [0016] S8: merging all the clusters to obtain final clustering results, where the merging is skipped if a cover area of two clusters is less than a preset cover area threshold, or the merging is performed if a cover area of two clusters is greater than or equal to the preset cover area threshold.

[0017] Optionally, after step S6 and before step S7, the following step is further performed:

• • [0018] removing repeated nucleus seeds from the nucleus seed list.

[0019] Optionally, step S7 specifically includes:

• • [0020] step 71, looping through the nucleus seed list to obtain a current nucleus seed A, putting the current nucleus seed A into a list list_query, and then solving a difference set of a list set_nucleu and the nucleus seed list to obtain a new nucleus seed list set_nucleu;
  • [0021] step 72, looping through the list list_query when the list list_query is not empty, taking out data sample associated with the current nucleus seed A, and deleting data samples already associated with other nucleus seeds to obtain a cluster CK where the nucleus seed A is located;
  • [0022] step 73, solving an intersection set of the cluster CK where the nucleus seed A is located and the nucleus seed list set_nucleu to obtain all nucleus seeds located in the current cluster CK, and updating the list list_query to obtain a new list list_query; solving a difference set of the cluster CK and the nucleus seed list set_nucleu to obtain a list set_nucleu of all unclustered nucleus seeds; and
  • [0023] step 74, repeating steps 71 to 73 until all the nucleus seeds are clustered.

[0024] Optionally, in step S2, the computing a mean Z value of each sample specifically includes:

• • [0025] obtaining a point sequence coordinate list of a single geometric object, and determining that the mean Z value of the sample is 0 when a length of the point sequence coordinate list is equal to 0 or greater than 0 and less than 3; and looping through the point sequence coordinate list when the length of the point sequence coordinate list is equal to 3 to obtain each point, determining whether each point contains Z value coordinates, taking out a Z value of the point if the point contains the Z value coordinates, and computing a mean value of Z values of the entire point sequence coordinate list, namely, obtaining the mean Z value of the sample.

[0026] Optionally, the vehicle line is any one of a dotted line, a long line, and a double solid line.

[0027] Optionally, when the vehicle line is a long line, after step S1 and before step S2, the following steps are further performed:

• • [0028] computing lengths of longest edges of all samples in the to-be-clustered data list of the vehicle line, capturing first d % of data area_list in ascending order, and computing a mean value mean and standard deviation std of the captured data as filtering conditions for filtering the to-be-clustered data list of the vehicle line.

[0029] Optionally, the computing lengths of longest edges of all samples specifically include:

• • [0030] assuming an object sample, obtaining a point sequence coordinate list of the object sample, and extracting first three coordinates a(x_a, y_a, z_a), b(x_b, y_b, z_b), and c(x_c, y_c, z_c) of the point sequence coordinate list;
  • [0031] computing a length dis(a,b) of edge ab, a length dis(b,c) of edge bc, and a length dis(a,c) of edge ac of the object sample;
  • [0032] putting dis(a,c) into the list, sorting the longest edges in ascending order, capturing first d % of data area_list, and computing a mean value mean and standard deviation std of the captured data; and
  • [0033] using the object sample as a to-be-clustered sample if the difference between the length dis(a,c) of the longest edge of the object sample and the mean value mean is greater than or equal to the negative standard deviation std.

[0034] Optionally, when the vehicle line is a long line and a double solid line, azimuth angles of objects need to be determined before nucleus seeds are searched, and if the angles of two long lines are greater than a preset angle threshold, the two long lines are not clustered together.

[0035] In this embodiment, in step S4, the distance threshold determination specifically includes:

• • [0036] assuming two objects, with centroid points M(x_m, y_m, z_m) and N(x_n, y_n, z_n);
  • [0037] computing a centroid distance dis(M,N) between the two objects, specifically:

[0038] $dis\left(M,N\right)=\sqrt{{\left(x_m-x_n\right)}^2+{\left(y_m-y_n\right)}^2+{\left(z_m-z_n\right)}^2}$

• • [0039] putting the samples that conform to the distance threshold determination into the first list when the centroid distance dis(M,N) between the two objects is less than a preset distance threshold.

[0040] In this embodiment, in step S4, the distance threshold determination specifically includes:

• • [0041] assuming two objects A and B, where both object A and object B have K points, namely, A=[M₁, M₂, . . . , M_K], object B=[N₁, N₂, . . . , N_K], and a minimum distance min(A,B) between object A and object B is:

[0042] $\min \left(A,B\right)=\min \left(dis\left(M_i,N_i\right),i\in \left(1,2,\dots ,K\right)\right)$

• • [0043] putting the samples that conform to the distance threshold determination into the first list when min(A,B) is less than a preset distance threshold.

[0044] Optionally, if the length of the long line is less than a preset length threshold, the present disclosure considers that there is an error in type determination. For better compatibility with the long line, the long line cluster having a length less than the preset length threshold is determined as a dotted line and put into the to-be-clustered data list of dotted lines for re-clustering.

[0045] In a second aspect, a clustering system for a vehicle line of a crowdsourced map described in the present disclosure includes a processor and a memory, where the memory stores a computer-readable program, and when the computer-readable program is called by the processor, the steps of the clustering method for a vehicle line of a crowdsourced map as described in the present disclosure can be performed.

[0046] In a third aspect, a storage medium described in the present disclosure stores a computer-readable program, and when the computer-readable program is called, the steps of the clustering method for a vehicle line of a crowdsourced map as described in the present disclosure can be performed.

[0047] The present disclosure has the following advantages:

• • [0048] (1) On the basis of conventional DBSCAN clustering algorithms, the present disclosure incorporates strong filtering determination of nucleus seeds, which prevents objects with small areas from becoming nucleus seeds, thereby improving computational efficiency and effectively filtering out abnormal points.
  • [0049] (2) The present disclosure combines factors such as angles, areas, distances, and lengths of objects for comprehensive determination, and can thus be more suitable for practical clustering of vehicle lines.
  • [0050] (3) The present disclosure considers the accuracy of recognizing object elements by vehicle end sensors, and comprehensively considers the basic features of objects for clustering, thereby enabling better fault-tolerant processing.

[0051] In summary, the present disclosure combines a plurality of determination elements such as distances, angles, areas, and lengths of vehicle line objects, thereby satisfying the complexity and specificity of clustering of vehicle line factors. The nucleus seeds are skillfully filtered in the clustering process, which effectively improves the efficiency of the algorithm and can well avoid the impact of abnormal points. The present disclosure further performs fault-tolerant processing on recognized erroneous types, which can better be compatible with erroneous data types.

[0056] The present disclosure will be explained in detail below with reference to the accompanying drawings.

[0057] As shown in FIG. 1, in an embodiment, a clustering method for a vehicle line of a crowdsourced map includes the following steps:

• • [0058] At S1: road element object data of the crowdsourced map are collected, and vehicle line road elements are classified and extracted to obtain to-be-clustered data lists of different vehicle lines;
  • [0059] At S2: a mean Z value of each sample in the to-be-clustered data list of the vehicle line is computed to obtain a mean Z value list of the vehicle line; centroid coordinates of each sample in the to-be-clustered data list of the vehicle line are computed to obtain a centroid coordinate list of the vehicle line;
  • [0060] At S3: the to-be-clustered data list of the vehicle line are looped through to obtain a current sample, and E neighborhood samples of the current sample are determined to obtain an E neighborhood sample list of the current sample;
  • [0061] At S4: a mean Z value of the current sample is obtained from the mean Z value list of the vehicle line, an E neighborhood sample is randomly obtained from the E neighborhood sample list of the current sample, a difference between the mean Z value of the current sample and the mean Z value of the E neighborhood sample is computed, distance threshold determination is performed when the difference between the two is less than a preset difference threshold, and the samples that conform to the distance threshold determination are put into a first list of the current sample until the E neighborhood sample list of the current sample is fully looped through;
  • [0062] At S5: the current sample is used as a nucleus seed if a length of the first list of the current sample is greater than a minimum clustering sample number threshold, and data that conform to the distance threshold determination with the current sample are stored;
  • [0063] At S6: steps S3 to S5 are repeated until all nucleus seeds that meet requirements and data associated with the nucleus seeds are found;
  • [0064] At S7: a nucleus seed list is looped through to obtain a cluster CK where the current sample is located, all nucleus seeds located in the current cluster CK are found, and the nucleus seed list is updated until all the nucleus seeds are clustered;
  • [0065] At S8: all the clusters are merged to obtain final clustering results, where the merging is skipped if a cover area of two clusters is less than a preset cover area threshold, or the merging is performed if a cover area of two clusters is greater than or equal to the preset cover area threshold.

[0066] In this embodiment, types of the vehicle line include dotted lines, long lines, and double solid lines. In step S1, extracted dotted lines are put into the corresponding to-be-clustered data list of dotted lines to obtain a to-be-clustered data list of dotted lines; extracted long lines are put into the corresponding to-be-clustered data list of long lines to obtain a to-be-clustered data list of long lines; and extracted double solid lines are put into the corresponding to-be-clustered data list of double solid lines to obtain a to-be-clustered data list of double solid lines.

[0067] In this embodiment, in step S2, the mean Z value of each sample is computed as follows:

• • [0068] A point sequence coordinate list of a single geometric object is obtained, and the mean Z value of the sample is 0 when a length of the point sequence coordinate list is equal to 0 or greater than 0 and less than 3; the point sequence coordinate list is looped through when the length of the point sequence coordinate list is equal to 3 to obtain each point, whether each point contains Z value coordinates is determined, a Z value (namely, Point(Z_j)) of the point is taken out if the point contains the Z value coordinates, and a mean value of Z values of the entire point sequence coordinate list is computed, namely, the mean Z value (namely, Mean_z) of the sample is obtained.

[0069] In this embodiment, a computational formula for Mean_z is as follows:

[0070] $\begin{array}{cc}{\mathrm{Mean}}_z=\left({\sum }_{j=1}^p\mathrm{Point}\left(Z_j\right)\right)/p;& \left(1\right)\end{array}$

[0071] Here, Point(Z_j) is a Z value of the j-th point in the point sequence coordinate list, j=1, 2, . . . , p; and p is the number of points in the point sequence coordinate list.

[0072] In this embodiment, when the length of the point sequence coordinate list is equal to 0, it indicates that the object has no point, namely, no Z value. When the length of the point sequence coordinate list is greater than 0 and less than 3, it indicates that the number of points of the geometric object does not meet a minimum requirement, so subsequent operations are skipped. The minimum requirement for the number of points of the geometric object is 3. The length of the point sequence coordinate list is equal to 3, indicating that the coordinates of the points all have X-axis, Y-axis, and Z-axis coordinates.

[0073] In this embodiment, in step S4, the distance threshold determination is as follows:

• • [0074] Two objects are assumed, with centroid points M(x_m, y_m, z_m) and N(x_n, y_n, z_n);
  • [0075] A centroid distance dis(M,N) between the two objects is computed, specifically:

[0076] $\begin{array}{cc}dis\left(M,N\right)=\sqrt{{\left(x_m-x_n\right)}^2+{\left(y_m-y_n\right)}^2+{\left(z_m-z_n\right)}^2}& \left(2\right)\end{array}$

[0077] The samples that conform to the distance threshold determination are put into the first list when the centroid distance dis(M,N) between the two objects is less than a preset distance threshold.

[0078] In this embodiment, the distance threshold determination in step S4 may alternatively be as follows:

[0079] Two objects A and B are assumed, where both object A and object B have K points, namely, A=[M₁, M₂, . . . , M_K], object B=[N₁, N₂, . . . , N_K], and a minimum distance min(A,B) between object A and object B is:

[0080] $\begin{array}{cc}\min \left(A,B\right)=\min \left(dis\left(M_i,N_i\right),i\in \left(1,2,\dots ,K\right)\right)& \left(3\right)\end{array}$

[0081] The samples that conform to the distance threshold determination are put into the first list when min(A,B) is less than a preset distance threshold.

[0082] As shown in FIG. 2, in this embodiment, when a vehicle line is a long line, due to the influence of abnormal points, some objects having low density and poor data will become nucleus seeds, thereby affecting a clustering effect. Therefore, before nucleus seeds are filtered, short objects are removed for long line clustering, making them unable to become nucleus seeds. Accordingly, after step S1 and before step S2, the following steps are further performed:

[0083] Lengths of longest edges of all samples in the to-be-clustered data list of the vehicle line are computed, first d % of data area_list are captured in ascending order, and a mean value mean and standard deviation std of the captured data are computed as filtering conditions for filtering to-be-clustered samples.

[0084] In this embodiment, the lengths of the longest edges of the samples are computed as follows:

• • [0085] An object sample is assumed, a point sequence coordinate list of the object sample is obtained, and first three coordinates a(x_a, y_a, z_a), b(x_b, y_b, z_b), and c(x_c, y_c, z_c) of the point sequence coordinate list are taken out; a length dis(a,b) of edge ab, a length dis(b,c) of edge bc, and a length dis(a,c) of edge ac of the object sample are computed,

[0086] $\begin{array}{cc}dis\left(a,b\right)=\sqrt{{\left(x_a-x_b\right)}^2+{\left(y_a-y_b\right)}^2}& \left(4\right)\end{array}$ $\begin{array}{cc}\mathrm{dis}\left(b,c\right)=\sqrt{{\left(x_b-x_c\right)}^2+{\left(y_b-y_c\right)}^2}& \left(5\right)\end{array}$ $\begin{array}{cc}\mathrm{dis}\left(a,c\right)=\sqrt{di{s\left(a,b\right)}^2+di{s\left(b,c\right)}^2}& \left(6\right)\end{array}$

[0087] Here, dis(a,c) is the length of the longest edge of the sample; dis(a,c) is put into the list and sorted in ascending order, first d % of data area_list are captured, and a mean value mean and standard deviation std of the captured data are computed. The object sample is used as a to-be-clustered sample if the difference between the length dis(a,c) of the longest edge of the object sample and the mean value mean is greater than or equal to the negative standard deviation std.

[0088] In this embodiment, a range of d % is 10% to 20%, depending on an actual situation.

[0089] In this embodiment, if the length of the long line is less than a preset length threshold, it is considered that there is an error in type determination of the vehicle line. For better compatibility with the long line, the long line cluster having a length less than the preset length threshold is determined as a dotted line and put into the to-be-clustered data list of dotted lines for re-clustering. Before the length of the long line cluster is computed, a plurality of objects of the long line cluster need to be merged to obtain a latest object, and then the length of the long line cluster is computed using formulas (4) to (6).

[0090] In this embodiment, when the vehicle line is a long line and a double solid line, azimuth angles angle_dif of objects need to be determined before nucleus seeds are searched. If the angles of object 1 and object 2 are greater than a preset angle threshold, the two objects are not clustered together.

[0091] A difference angle_dif in the azimuth angles of the two objects is computed as follows:

[0092] $\begin{array}{cc}{\mathrm{angle}}_{\mathrm{dif}}=\mathrm{angle}1-\mathrm{angle}2& \left(7\right)\end{array}$

[0093] Here, angle1 is the azimuth angle of object 1, and angle2 is the azimuth angle of object 2.

[0094] If angle_dif is greater than 180 degrees, the following is used:

[0095] $\begin{array}{cc}{\mathrm{angle}}_{\mathrm{dif}}=360-{\mathrm{angle}}_{\mathrm{dif}}.& \left(8\right)\end{array}$

[0096] In this embodiment, the computed mean Z value of the sample is stored in the corresponding mean Z value list of the vehicle line, and can be directly called for subsequent use without repeated computation and storage. Similarly, the centroid coordinates of the object are extracted and put into the corresponding centroid coordinate list of the vehicle line for subsequent use.

[0097] In this embodiment, after step S6 and before step S7, the following step is further performed: repeated nucleus seeds are removed from the nucleus seed list to improve computational efficiency and accuracy.

[0098] In this embodiment, step S7 is specifically as follows:

• • [0099] At step 71, the nucleus seed list is looped through to obtain a current nucleus seed A, the current nucleus seed A is put into a list list_query, and then a difference set of a list set_nucleu and the nucleus seed list is solved to obtain a new nucleus seed list set_nucleu;
  • [0100] At step 72, the list list_query is looped through when the list list_query is not empty, data sample associated with the current nucleus seed A is taken out, and data samples already associated with other nucleus seeds are deleted to obtain a cluster CK where the nucleus seed A is located;
  • [0101] At step 73, an intersection set of the cluster CK where the nucleus seed A is located and the nucleus seed list set_nucleu is solved to obtain all nucleus seeds located in the current cluster CK, and the list list_query is updated to obtain a new list list_query; a difference set of the cluster CK and the nucleus seed list set_nucleu is solved to obtain a list set_nucleu of all unclustered nucleus seeds;
  • [0102] At step 74, steps 71 to 73 are repeated until all the nucleus seeds are clustered.

[0103] FIG. 3 shows a plurality of determination elements for a vehicle line in an embodiment, including angles, areas, lengths, distances, distances between long edges, mean Z values, and the like of objects. The method combines a plurality of determination elements such as distances, angles, areas, and lengths of vehicle line objects, thereby satisfying the complexity and specificity of clustering of vehicle line elements. The nucleus seeds are skillfully filtered in the clustering process, which effectively improves the efficiency of the algorithm and can well avoid the impact of abnormal points. The method further performs fault-tolerant processing on recognized erroneous types, which can better be compatible with erroneous data types.

[0104] In an embodiment, a clustering system for a vehicle line of a crowdsourced map includes a processor and memory, where the memory stores a computer-readable program, and when the computer-readable program is called by the processor, the steps of the clustering method for a vehicle line of a crowdsourced map in the foregoing embodiment can be performed.

[0105] In an embodiment, a storage medium stores a computer-readable program, and when the computer-readable program is called, the steps of the clustering method for a vehicle line of a crowdsourced map in the foregoing embodiment can be performed.

[0106] It should be noted that the storage medium shown in this embodiment may be a computer-readable signal medium, a computer-readable storage medium, or any combination of the above two. For example, the computer-readable storage medium may be, an electrical, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device, or any combination of the above. More specific examples of the computer-readable storage medium may include, but are not limited to: an electrical connection with one or more wires, a portable computer disk, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read only memory (EPROM), a flash, an optical fiber, a portable compact disk read-only memory (CD-ROM), an optical storage device, a magnetic storage device, or any suitable combination of the above. In this embodiment, the computer-readable signal medium may include data signals in a base band or propagated as some of carriers, in which the computer-readable program is carried. The propagated data signals may be in various forms, including but not limited to electromagnetic signals, optical signals, or any suitable combination of the above. The computer-readable signal medium may alternatively be any other computer-readable medium other than the computer-readable storage medium. The computer-readable medium is capable of sending, propagating or transmitting a program used by an instruction execution system, apparatus or device or a combination thereof. The computer program included in the computer-readable medium may be transmitted by any suitable medium, including but not limited to wireless, wired, or any suitable combination of the above.

[0107] The foregoing embodiments are preferred implementations of the present disclosure, but the implementations of the present disclosures are not limited by the foregoing embodiments. Any other changes, modifications, substitutions, combinations, or simplifications made without departing from the spirit essence and principle of the present disclosure shall be equivalent replacements, and shall fall within the protection scope of the present disclosure.