Autoware.Auto


Abstractly, euclidean clustering groups points into clusters such that for any two points in a cluster, there exists a chain of points also within that cluster between both points such that the projected distance between subsequent points in the chain is less than some threshold.
Projected distance is the distance between two points projected onto the xy plane in the vehicle frame. Clusters are valid objects if the number of points in the cluster is above a given threshold.
Another way of looking at the result is that a connectivity graph is generated, and clusters are connected components with more than a certain number of vertices.
Vertices in this view are point cloud points, and edges are drawn between points with a project distance below some threshold.
Concretely, the algorithm to construct these clusters works in the following way:
The following modifications were made for a simplified algorithm and higher speed:
The algorithm consists of the following steps:
n
points into spatial hash (O(n)
to insert): O(n^2)
n
points that are unseen:k
near neighbors (O(1)
lookup time, though it is possible to construct adversarial O(n)
examples)This results in an algorithm that is O(n^2 + n^2)
, but is in practice O(n)
. In practice, the first term should be O(n)
as inserting into a hashmap is average case O(1)
.
The second term should also be O(n)
because pruning should result in each point showing up in a nearneighbor query exactly once, and marking points as seen should result in skipping many inner iterations of the main loop.
The module consists of the following components:
O(n)
:O(n + n + A * n)
, where A
is an arbitrary constant (load factor)O(n + n)
O(n + B * n)
where B <= 1
is a constant factor (1 / points per cluster)This results in O(n)
space complexity.
Conceptually, the clustering algorithm has three states:
The second state, clustering, can be thought of as a separate state because it performs destructive operations on the underlying data structure.
By contrast, the first state, point acquisition, performs constructive (additive) operations on the underlying data structure.
Finally, the result ready state occurs between clustering and cleanup. This state is available such that operations or manipulations may be done on the resulting (large) cluster data.
For more details on the API, see the documentation.
This class uses externally allocated output, which supports the use case of performing further operations on the output, such as sorting during a hull formation process.
Finally, get_error and throw_stored_error are provided separately from cluster because some errors during the clustering process do not necessarily invalidate the remainder of the results. Recovery action should still be taken, but to some extent, the result is still valid, if incomplete.
Euclidean clustering is based off a core algorithm provided in pcl with modifications from CPFL's Autoware.