domingo, 28 de abril de 2013

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


Spatial Nearest Neighbor 

 Multivariable segmentation

Well, and that's the first results of this metric.
In the Next post i will draw some conclusions.

domingo, 21 de abril de 2013

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. 


domingo, 14 de abril de 2013

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).  


  • 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.


quinta-feira, 11 de abril de 2013

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