Cars with SAE Level 2 and beyond are already on the streets, with the rapid adoption of ADAS amongst users. With this level of adoption level 3 and beyond is no longer a distant dream. One can expect cars with near full autonomy in this decade. This allows using multiple radars as well as means to effectively use existing radar sensors in the car for extended features.
One of the key parts of sensing algorithms used in radar is clustering/grouping. Reflected radar waves give multiple detections for a single object depending on the surface area of the object. Grouping/clustering the points is required so that each object is identified once as the next task in the processing pipeline. Generally, density-based clustering like DBSCAN is employed for this. DBSCAN works by defining a point as part of a cluster if it belongs to the area density of points above an adaptive threshold. Users define the minimum distance between objects along with minimum points to form a cluster/group. Modified weighted DBSCAN approaches provide advantages specific to radar applications. This algorithm also helps to remove random noise detections, which are common with radar applications.
This blog gives an overview of implementation and optimization of the DBSCAN algorithm for embedded applications. There are various implementation of DBSCAN, but they do not consider various constraints involved with high-resolution radar and embedded implementation.
DBSCAN generally uses the range and angle information for clustering. The issue with the range-angle information is that this approach leads to a non-equidistant sampling density. The sampling distance for the close-by range is shorter and for far off the range is quite long. Having a constant epsilon parameter for all these ranges provides efficient clustering either in the short-range or in the long-range. The epsilon value of DBSCAN can be tuned only to meet either the short-range application or for the long-range application. The radar application can be limited due to this restriction. For use cases such as part assist or automated parking, the DBSCAN parameters can be tuned for a short-range and will meet all such requirements. In the case of high-resolution radar, there is a necessity to detect and group objects both short-range and long-range. This is achievable by grid-based DBSCAN instead of normal Euclidean distance.
The X-Y DBSCAN operates on the x-y cartesian coordinated of the detection points rather than the polar (𝑅,𝜃) coordinates
Priori Value DBSCAN
The epsilon value in DBSCAN denotes the minimum distance between two different objects. The minpts value denotes the minimum number of detection points that can be expected from any cluster. In normal DBSCAN, these two values have to be set properly for optimal detection performance. Since the closeness of detection points varies with respect to range, it is difficult to set a single epsilon value for objects in all ranges. Due to this non-uniform (R,θ) pattern, the same object which is grouped in a closer range does not get grouped at a farther range. Adaptive prior information is required which changes with the measured range of the detection. In grid-based DBSCAN or X-Y DBSCAN, the distance between detection points of an object remains the same. There is a loss of detection points in between the cluster, causing a decrease in density with an increase in range. Hence, with a fixed optimal epsilon value, the grid-based or X-Y DBSCAN will provide better results without much effort. Due to the decrease in density, the minimum points in a cluster can drastically change with an increase in distance.
With high-resolution radar comes the challenge of DBSCAN implementation. This is due to two major reasons. One, the number of points detected by high-resolution radar is quite huge (in thousands). With the increase in detection points, the complexity of distance matrix calculation increases exponentially. Secondly, this also increases the memory requirement to store the distance matrix
DBSCAN based grouping of radar detections is a well-known processing step before tracking or classification. Implementing DBSCAN for high-resolution radars has its problems.
Click on the link for an article by Team PathPartner to learn more about DBSCAN implementation for high-resolution automotive radar link