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

1 . A clustering method for a vehicle line of a crowdsourced map, the method used in a precision map to assist automatic driving, comprising the following steps executed from a processor of a clustering system:

S 1 : collecting data on vehicle line road elements of the crowdsourced map, and classifying and extracting the vehicle line road elements to obtain to-be-clustered data lists of different vehicle lines including the vehicle line;

S 2 : 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, wherein each sample in the to-be-clustered data list of the vehicle line is a type 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;

S 3 : 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, among each sample in the to-be-clustered data list of the vehicle line, to obtain an E neighborhood sample list of the current sample;

S 4 : obtaining the 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 E neighborhood 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;

S 5 : using the current sample as a nucleus seed when 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;

S 6 : repeating steps S 3 to S 5 until all nucleus seeds that meet requirements that the length of the first list of each nucleus seed is greater than the minimum clustering sample number threshold, and data associated with the nucleus seeds are found;

S 7 : 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

S 8 : merging all the clusters to obtain final clustering results, wherein the merging is skipped when a cover area of two clusters is less than a preset cover area threshold, or the merging is performed when a cover area of two clusters is greater than or equal to the preset cover area threshold.

2 . The clustering method for the vehicle line of the crowdsourced map according to claim 1 , wherein after step S 6 and before step S 7 , the following step is further performed:

removing repeated nucleus seeds from the nucleus seed list.

3 . The clustering method for the vehicle line of the crowdsourced map according to claim 1 , wherein step S 7 specifically comprises:

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;

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;

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 where the nucleus seed A is located and the nucleus seed list set_nucleu to obtain a list set_nucleu of all unclustered nucleus seeds; and

step 74 , repeating steps 71 to 73 until all the nucleus seeds are clustered.

4 . The clustering method for the vehicle line of the crowdsourced map according to claim 1 , wherein in step S 2 , the computing the mean Z value of each sample specifically comprises:

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; 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 when 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.

5 . The clustering method for the vehicle line of the crowdsourced map according to claim 1 , wherein the vehicle line is any one of a dotted line, a long line, and a double solid line.

6 . The clustering method for the vehicle line of the crowdsourced map according to claim 5 , wherein when the vehicle line is a long line, after step S 1 and before step S 2 , the following steps are further performed:

computing lengths of longest edges of all samples in the to-be-clustered data list of the vehicle line, capturing first 10% to 20% 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.

7 . The clustering method for the vehicle line of the crowdsourced map according to claim 6 , wherein the computing the lengths of the longest edges of all samples specifically comprises:

providing 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;

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;

putting the length dis(a, c) into a list, sorting the longest edges in ascending order, capturing the first 10% to 20% of the data area_list, and computing the mean value mean and the standard deviation std of the captured data; and

using the object sample as a to-be-clustered sample when a 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 a negative standard deviation std.

8 . The clustering method for the vehicle line of the crowdsourced map according to claim 5 , wherein when the vehicle line is a long line or a double solid line, azimuth angles of objects need to be determined before nucleus seeds are searched, and when angles of two long lines are greater than a preset angle threshold, the two long lines are not clustered together.

9 . The clustering method for the vehicle line of the crowdsourced map according to claim 5 , wherein a long line cluster having a length less than a preset length threshold is determined as a dotted line and put into the to-be-clustered data list of dotted lines for re-clustering.

10 . The clustering method for the vehicle line of the crowdsourced map according to claim 1 , wherein in step S 4 , the distance threshold determination specifically comprises:

providing two objects, with centroid points M(x m , y m , z m ) and N(x n , y n , z n );

computing a centroid distance dis(M, N) between the two objects, specifically:

d

⁢

i

⁢

s

⁡

(

M

,

N

)

=

(

x

m

-

x

n

)

2

+

(

y

m

-

y

n

)

2

+

(

z

m

-

z

n

)

2

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.

11 . The clustering method for the vehicle line of the crowdsourced map according to claim 1 , wherein in step S 4 , the distance threshold determination specifically comprises:

providing two objects A and B, wherein both object A and object B have K points, namely, object A=[M 1 , M 2 , . . . , M K ], object B=[N 1 , N 2 , . . . , N K ], and a minimum distance min(A, B) between object A and object B is:

min( A,B )=min(dis( M i ,N i ), i ∈(1,2 , . . . ,K ))

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

12 . The clustering system for the vehicle line of the crowdsourced map, comprising the processor and a memory, wherein 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 the vehicle line of the crowdsourced map according to claim 1 can be performed.

13 . A non-transitory storage medium, storing a computer-readable program, wherein when the computer-readable program is called, the steps of the clustering method for the vehicle line of the crowdsourced map according to claim 1 can be performed.