Santos approach metric results

Greetings,

in this post i will present the results obtained bu the Santos approach from the Dietmayer Segmentation, this algorithm took a little while because it was the only one which its threshold value depends on 2 parameters, the C0 which is a constant parameter used for noise reduction (the same as in the Dietmayer Segmentation) and an additional parameter β which aims to reduce the dependence of the segmentation with respect to the distance between the laser and the objects.

Just to recall the Threshold condition:

The tests:
The procedure was similar to the testing of the other algorithms - Divied in route in 3 parts and compared the results with the ground truth results using the metric presented 2 posts ago. 

However with this particular algorithm i divided the tests in 2 parts:

1. To inquire the influence of the C0 parameter, I fixed the value of β = 10º
2. To inquire the influence of β, I fixed the values of C0 = 1 (m)

Complete route:

β = 10º
Minimum Energy value:  148.4237
Minimum Energy C0 value: 1.375

C0 = 1.0 m

Minimum Energy value: 222.7269
Minimum Energy β value:  5º


Comments:

• The performance of the algorithm is far more dependable form the C0 parameter than the  β value.
• The  β curve has a global minimum for the 5º reversal, them stabilizes, once again shows that the applied metric may not be the most appropriated for testing.

Straight road:

β = 10º
Minimum Energy value:  155.0718
Minimum Energy C0 value: 1.375

C0 = 1.0 m

Minimum Energy value: 357.3028
Minimum Energy β value:  25º and 27.5º 





Comments:

• The  β curve has a sharp decline from 15º to 17.5º and them stabilizes again  

Roundabout approach:

β = 10º
Minimum Energy value:   129.5992
Minimum Energy C0 value: 1.75

C0 = 1.0 m

Minimum Energy value:  130.2633
Minimum Energy β value:  10º 


Comments:

• This time the C0 presented a sinusoidal form.
• The  β curve presented a "peak" for 15º. Pretty constant for the other  β values 

Roundabout:

β = 10º
Minimum Energy value:    146.9297
Minimum Energy C0 value: 1.375 and 1.500

C0 = 1.0 m

Minimum Energy value:   124.3453
Minimum Energy β value:   5º


Comments:

• For this course the C0 present also small variations, minimum energy value = 146.9297 and the maximum energy value =  147.4547
• The  β curve has a global minimum for the 5º reversal, them stabilizes, once again shows that the applied metric may not be the most appropriated for testing.

MAIN CONCLUSIONS:

1. The performance of the algorithm is far more dependable form the C0 parameter than the  β value.
2. Once again the results are not very satisfying - We cant conclude what is the best threshold value for the algorithm

Metric final results

As mentioned in the previous post, a metric for comparison of the validity was applied to the Segmentation Algorithms implemented in order to find out which method was the best.

This time i divided the car's course in 3 parts:

1. Straight line route
2. Roundabout approach
3. Roundabout

Just to give you an idea how this pathways look like I've taken some pictures from the Google Maps Street View.

Here is the straight road:

The roundabout approach:

The roundabout

Now you have an idea how the tested scenarios look like.

This time, there were made 21 essays between the values i thought that held physical meaning and that i    considered that were acceptable. Keepin mind that the lower the energy, the better the closest the results to the ground truth.

Here is the results:

Complete route:

Minimum energy value: 143.2369

Minimum energy threshold value: 1.3750 m

Minimum energy value: 78.4062

Minimum energy C0 value: 1.3750 m

Minimum energy value: 160.7339

Minimum energy lamda value: 6.5 degrees

Minimum energy value: 143.9026

Minimum energy threshold value: 2.750  m

Minimum energy value: 136.6162

Minimum energy cosine distance value: 0.475  

Comments:

• The simple segmentation, the Dietmayer and the Spacial Nearest Neighbor presented a similar type of curve.
• The ABD present a very irregular curve.
• The best result was achieved by the Dietmayer Segmentation. 

 Straight Road:

Minimum energy value: 155.0718

Minimum energy threshold value: 1.3750 m

Minimum energy value: 154.7607

Minimum energy C0 value: 1.3750 m

Minimum energy value: 211.7002

Minimum energy lamda value: 6.5 degrees

Minimum energy value: 247.6670

Minimum energy threshold value: 1.250  m

Minimum energy value: 206.2954

Minimum energy cosine distance value: 0.725  

Comments:

• The simple segmentation, the Dietmayer and the Spacial Nearest Neighbor presented a similar type of curve.
• The ABD present a very irregular curve.
• The best result was achieved by the Multivariable Segmentation. 

Roundabout approach:

Minimum energy value: 129.9531

Minimum energy threshold value: 1.750 m

Minimum energy value: 31.8815

Minimum energy C0 value: 3 m

Minimum energy value: 88.8079

Minimum energy lamda value: 15.5 degrees

Minimum energy value: 140.9477

Minimum energy threshold value: 1.00  m

Minimum energy value: 69.9323

Minimum energy cosine distance value: 0.475 

Comments:

• The simple segmentation, the Dietmayer and the Spacial Nearest Neighbor presented a similar type of curve.
• The ABD present a very irregular curve.
• The best result was achieved by the Dietmayer Segmentation. 

Roundabout:

Minimum energy value: 134.9820

Minimum energy threshold value: 0.500  m

Minimum energy value: 18.5544

Minimum energy C0 value: 1.50 m

Minimum energy value: 134.5345

Minimum energy lamda value: 4.7 degrees

Minimum energy value: 111.3381

Minimum energy threshold value: 3  m

Minimum energy value: 52.4475

Minimum energy cosine distance value: 0.475 

Comments:

• The simple segmentation, and the Dietmayer presented a similar type of curve.
• The ABD present a very irregular curve.
• the Spacial Nearest Neighbor has a kinda strange curve as well.
• The best result was achieved by the Dietmayer Segmentation. 

Main conclusion:

1. In general the Dietmayer Segmentation and the Multivarible Segmentation present the best results based only on the energy values.
2. The metric is not fully perfected -   Some of the minimum values occur for the extreme values and theoretically the Spacial Nearest Neighbor Algorithm should be one of the more viable algorithms

Final Note:

The results for the Santos approach will be presented in the next post (it is the only method with 2 variables) 

Some results

Some important developments were made this week.

One important topic is that we improved the metric i presented in the previous post.
Here is the new metric:

Main advantages of this metric:

• Same treatment for all the tested algorithms
• Penalizes the distance between the clusters 
• Penalizes differences between the clusters sizes
• The Number of clusters

Notice that the lower the Medium energy, the similar are the results presented by the algorithm (compared with the groundtruth)

So i achieved the following results:

Simple segmentation

Dietmayer segmentation

ABD

Spatial Nearest Neighbor 

 Multivariable segmentation

Well, and that's the first results of this metric.

In the Next post i will draw some conclusions.

The metric

Well, in the past week i had losts of problems in synchronizing the Matlab imported data with the groundtruth and the data from the rosbag.

So we decided to use the txt file with the groundtruth data to also use the x and y positions in the file to be segmented with the already implement Segmentation Algorithms:

1. Simple Segmentation
2. Multivariable Segmentation
3. Dietmayer Segmentation (or Jump distance segmentation)
4. Santos approach of the Dietmayer Segmentation
5. Adaptative Breakpoint Detector 
6. Spacial Nearest Neighbor 

Note: The Lee Segmentation Algorithm described on the previous post, presented very poor results. So we decided to discard it.

So we need to create a metric to compare the performance of the several algorithms:

For each cluster:

• Calculate the distance to every groundtruth cluster (central point distance)
• Energy function, for each iteration (scan): 


• E = ∑ min_distance( Cluster - GroundtruthCluster ) x (Number_clusters / Number_clusters_groudtruth)
• In the end we sum the Energies for all the iterations.

Note: This metric will probably be improved.

In the next post i hope i will be able to present some results. 

   

Halfway there

Greetings once again,

Well there are less than 9 weeks for the project's deadline, so there will be few more new objectives to add.

First i think i will add at lest 2 more distance-based segmentation algorithms:

• Segmentation algorithm used by Santos, et al., 2003, this algorithms is based on the approach used by Dietmayer (already used in my project) but with and additional parameter  β. This parameter aims to reduce the dependence of the segmentation with respect to the distanc between the laser range finder and the objects. This is the threshold condition: 

Where C0 and C1 are the same as in the Dietmayer approach.

• The other approach is used by Lee, et al. 2001, is a simple method of segmentation with the following threshold condition:

The objective of adding these 2 more algorithms is just to test as much segmentation algorithms as possible to enrich the project, as the the ros and the rviz platforms are built it does't add that much work to add more algorithms.

There might be a novelty in this project which is the Segmentation of Vegetation

In the last post, i referred this issue, as the laser range points in a vegetation area are kind of disperse random point cloud, the potential final goal is to preform the segmentation of these dispersed clusters.

I will try to implement the popular k-means algorithm using only the small objects (1 or 2 points) in the scan. If the points the clusters given by the k-means have few dispersion the we have a group(a brush or a tree).  

REFERENCES:

• Santos, S., J.E. Faria, F. Soares, R. Araujo and U.Nunes (2003). Tracking of Multi-Obstacles with Laser Range Data for Autonomous Vehicles. In: Proc. 3rd National Festival of RoboticsScientific Meeting (ROBOTICA), pp. 59-65, Lisbon, Portugal.
• Lee, K.J. (2001). Reactive navigation for an outdoor autonomous vehicle. Master Thesis. University of Sydney, Department of Mechanical and Mechatronic Engineering.

  

Week 1 - 8 April

Achievements made this week:

• Successful implementation of a Spacial Nearest Neighbor algorithm. This is a recursive algorithm      which calculates the distance between a point and all the other points the are not yet assigned to a cluster, if that distance is lower than the clustering threshold then the points are assigned to that cluster.

I also represent the results of the segmentation with this last algorithm on rviz plataform:

Once again, each layer represents the clusters obtained for each segmentation method (counting upwards):

1. Simple Segmentation
2. Multivariable Segmentation
3. Dietmayer Segmentation (or jump distance segmentation)
4. Adaptative Breakpoint Detector 
5. Spacial Nearest Neighbor

The comparison between the algorithms

In order to compare which algorithm offers less error, a manual "groundtruth" labeling was preformed.

Well, last week i only labeled the moving objects, however he decided that the segmentation of those objects alone weren't enough to compare the performance of each algorithm. So during the week i've been labeling all the objects in the scans obtained in a quick tour in a roundabout near Aveiro. 

The next image is an example of my manual labeling:    

 

Just to remember: 

This was made via Matlab, the program reads the laser scans data form a .txt file, then the data is converted into Cartesian coordinates and creates a structure composed by the coordinates and a label

So i've segmented all the 1220 scan the best as i possibly could, however, not all scans were as pretty, clean and easy to label like the one presented in the latest figure.

Now i give you a pair of problematic scans example:

The roundabout where the car's journey was made, has some trees in it which was kind of hard to label (group of those single points on the top left of the image).

"With some objects, the outline seen by the scanner appears to fluctuate in a random way as the

scanner moves and vegetation has this problem" - MacLachlan, Robert (2005).  Tracking moving objects from a moving vehicle using a laser scanner. Pittsburgh: Carnegie Mellon University.  

 

In the next example i present an example of a zone very subjective to segment (the one delimited by the red "circle"), the problem with that marked zone is that i am not sure what that range points may represent in the "real world" so the main point here is that for groundtruth purposes scans like this one will not be used for comparison so they don't compromise the truth of the results when the comparison between the Several algorithms is made.  

Other achievements:

• Write the results of the manual labeling on a txt file (number of the sacan, cartesian coordinates of the ranges and their respective lalbels)
• Read those results on the ros platform 

Next tasks:

• Post the groundtruth segmentation on the rviz plataform
• Compare the groundtruth segmentation with the other algorithms

Week 24 - 31

Achievements made this week:

1. Successful implementation of the Multivariable Segmentation 
2. Representation on the rviz platform of the Segmentation methods proposed, as it is shown on the figure below: 

            Each layer represents the clusters obtained for each Segmentation method (counting upwards):

• Simple segmentation 
• Multivariable Segmentation
• Dietmayer Segmentation
• Adaptative Breakpoint Detector

The next step, is to compare these results with a "groundtruth" and check the errors given by each method when the "threshold" values varies. 

So, a "groundtruth" to make the comparison between the methods is needed.

For that I use a Matlab program made by my Co-Supervisor Jorge Almeida, this program reads the laser scans data form a .txt file, then the data is converted into Cartesian coordinates and creates a structure composed by the coordinates and a label. Then we preform the hand labeling of the data to obtain the target "groundtruth".

The data was collected during a ride to a big roundabout nearby Aveiro. In order to help the hand labeling of the laser data, I use some images took by the car's cameras.  

In 1220 scans (iterations) I identified 17 moving cars and 1 bike.

Meanwhile, I've already started to think in the next phase of the project which is "Feature Extraction Algorithms". So i made a research of some state of art feature extraction algorithms and I've started to implement the algorithm developed by Kai O. Arras in "Using Boosted Features for the Detection of People in 2D Range Data", University of Freiburg.