Auto(Bot)ware SGM clustering Vs Autoware euclidean_cluster

Khaled_Elmadawi · 2021-05-18T09:25:08.760Z

Dear All,
Due the rdiscussion in this topic, this article will benchmark the difference between Auto(Bot)ware spherical grid map clustering, and Autoware euclidean clustering. starting with the setup and configuration the two algorithms, KPIs, results and conclusions.
and sorry for taking sometime, I fine tuned both algorithms because I believe being honest is more important than being right.

Simulation test rig setup:
test rig is an array of cars setup in a 5x5 grid each grid with a distance of 10 meters between each cone, and the robot is in the middle of it
as shown in the below figure.

image1920×1080 487 KB

Sensor model:
we will use two sensors first is 16 layer velodyne sensor, second is 64 layer velodyne sensor, to measure the change of point cloud density on the detection algorithms.

Autobotware setup:
clone the repo and “catkin build”
will set two sets of configurations:

“use_morphological_filter” = false.
“ground_segmentation_threshold” = 0.1

Autoware setup:
Follow the setup guide and build the lidar_euclidean_cluster_detect package.
will set two sets of configurations:

“remove_ground” = true.
“keep_lanes” = false.
“clip_min_height” = -5.
“clip_max_height” = 5.
“output_frame” = 3.
“downsample_cloud” = true.

KPIs:
the KPI that i think fit the most is range of detection, as both are detection algorithms, so simply how far can each algorithm can detect, and how the frequency will be.

Experiment1:

velodyne16-SGM algorithm with ground segmentation threshold of 0.1
result:
effective detection range around 15.9m, detection frequency beween 137 and 150 hz

image985×637 88 KB

image534×528 55.9 KB
velodyne16-euclidean algorithm with downsample = true
result:
effective detection range 25.5m, detection frequency between 74 and 90 hz

image1269×724 105 KB

image493×574 57 KB

Experiment2:

velodyne64-SGM algorithm with ground segmentation threshold of 0.1
result:
effective detection range around 60.4m, detection frequency beween 22 and 33 hz

image1031×732 140 KB

image644×615 63.4 KB
velodyne64-euclidean algorithm with downsample = true
result:
effective detection range around 63.2m, detection frequency beween 12 and 15 hz

image1006×733 111 KB

image521×692 74.3 KB

Conclusion:

euclidean clustering has better detection range than SGM clustering by around 60% in velodyne16(less dense), and around 4% in velodyne64( denser point cloud).
SGM is faster than euclidean clustering in velodyne16 by around 66%~84%, and in velodyne64 by around 83%~102%.
SGM is faster, losless, less thresholds/parameters, euclidean clustering can deal better with less points, but it is a lossy data clustering.
SGM requires V2 implementation where it can deal with far clusters, and we have added it to our action plan.
SGM provides freespace euclidean clustering doesn’t, euclidean clustering provides pose estimation, SGM doesn’t.

which approach to choose:
choosing which approach to use based on your usecase:

if you have a high dense LiDAR sensor, then 4% difference in the detection range by using SGM clustering is acceptable in exchange you will have more time to do mapping/planning/tracking/controlling within the same perception time stamp(56msec~69ms) on the other side euclidean clustering will only offer around 20msec~37msec, so it is a designer choice.
if you will use the detection output in other process then lossy point cloud output will bound you either with post processing else if you are just using it for detection as an input for tracking, then it is good enough I think.
if you are working with less dense LiDAR, then Euclidean clustering will be good enough for your case.

as in fact you may find someone thinking the same way you are thinking but in the other side of the world, here is another SGM clustering, the implementation is different but the same idea.

Euclidean clustering in autoware.

and finally, all opinions and feedback are welcomed, please follow the community rules.
Thanks,
Khalid elmadawi

Khaled_Elmadawi · 2021-05-18T12:22:09.681Z

one important aspect I didn’t mention, the station that I used for this benchmark. I used Lenovo LEGION intel corei5 10th gen, 16GB ram, and both algorithms ran on CPU.

I didn’t benchmark the two algorithms on RPI, but I benchmarked Velodyne16 SGM clustering before:
raspberry pi demo for point cloud semantic segmentaiton, object and freespace detection on raspberry pi for velodyne16
setup:
1- rosbag publish tf, tf_static, velodyne point cloud sensor.
2- roscore master runs on raspberry pi.
3- velodyne sensor point cloud is 16 layer, each layer has 2048 points, 32768 scan points in total.
4- velodyne input frequency is 10hz, output clustered point cloud is 10 hz.
5- clustering algorithm runs in 20~23 hz( 2x~2.3x required speed).
6- rviz just for visualizing what is happening on rpi, rviz runs on pc.

Hope this be informative for everyone :),
Thanks,
Khalid

Khaled_Elmadawi · 2021-05-31T14:38:33.952Z

Hi All,
First I would Love to thank you for your feedback, without it we wouldn’t have reached the below results.
Second, this is SGM clustering V2 results

GitHub

Robotion-AI/Autobotware

Autobotware is an all-in-one open-source software for autonomous UGVs and industrial robots. the target industries that Autobotware is working on are farming industry, mining industry, warehouses i...

Experiment1:

velodyne16-SGM algorithm with ground segmentation threshold of 0.1

result:

SGM effective detection range around 48m, detection frequency beween 143 and 160 hz

sgm_16_v2_performance566×552 40.2 KB

sgm_16_v2_range1356×725 94.3 KB

Experiment2:

velodyne64-SGM algorithm with ground segmentation threshold of 0.1

result:

effective detection range around 99.3m(max range), detection frequency beween 35 and 38 hz

sgm_64_v2_performance

sgm_v2_64_range798×637 55.7 KB

Conclusion:

SGM V2 clustering ~2x longer range than euclidean clustering in velodyne 16 and ~1.57x longer detection range in velodyne 64.
SGM V2 better in performance than euclidean clustering in velodyne16 by around 66%~84%, and in velodyne64 by around 150%~190%.
SGM is losless, doesnot lose pointcloud textures or downsample it, euclidean clustering requires downsampling to actually work, which may result to a deformation or object splitting into multiple objects.
SGM provides freespace euclidean clustering doesn’t, euclidean clustering provides pose estimation, SGM doesn’t.

now I can withstand my claims, better performance, more robust, I said that before based on my understanding of how the two algorithms work, but I realized that some changes were required to be done in our SGM implementation, so pardon me for that I take the blame for this, in all the ways we hope we contribute to the community, we don’t need to do business together to help you, if you need any help just ask , i think this is the reason for this community .
Thanks,
Khalid