Thursday, May 29, 2008

More path detection updates & videos

Following a suggestion by Nir I changed the algorithm to work using offline sampling for the creation of the road and non-road models, I built a small application that allows a user to highlight areas that should be included in the road/non-road model and used it to train the GMM on some path images I've taken (the rest of the algorithm is the same, read the previous post for details).
This has improved the performance of the algorithm and helped reduce running time a little bit, but the algorithm still has difficulties with some scenes, mainly when shadows are involved.
I'm posting 2 nice videos that show the algorithm's abilities :)

1) Detecting an obstacle
video

2) Moving between two types of paths

video

Wednesday, May 7, 2008

Path Detection algorithm - Now we are getting somewhere :)

hi All,
The exam season was appon us and along with the passover holiday caused the project to slumber a little bit. When it was over we got back into full development mode.
While Keren & Dror started working on local map building and path planning I returned to working on the path detection algorithm. After spending a lot of time on the localization module, tweaking noise parameters and believe functions, it felt good to switch to a completely different type of work.

Here is a short description of the algorithm as it is now:
I start by sampling 2 small rectangles in the picture - one at the bottom is used as an example of road pixels and the other (sampled from the top of the image) is used as non-road pixels.
From each rectangle I build a data set and train a mixture of Gaussians over the RGB space, which provides a model for road (or non-road) pixel distribution. Then I calculate the probability for each pixel in the image to belong to either one of the models and classify it according to Maximum Likelihood.
This provides a pretty good first guess as to which part of the image is the road, but it still lacks the accuracy needed for HANS to reliably drive on the path.
I decided to try and use a technique used sometimes in image segmentation - applying the known min-cut algorithm.
It basically works by building a graph where nodes are image pixels and edges are connections between pixels. The Source and Sink nodes are the labels (in our case Road and Non-Road) The cost to cut a node from the source/sink is the probability it belongs to the appropriate Gaussian Mixture. The cost to break an edge between to pixel-nodes is based in pixel color similarity. The min-cut algorithm is then used to find the cut with the smallest cost.
This produced much better results! The video included with this post shows 4 stages in the detection process:
1) the original frame is captured.
2) The GMM are trained and used to classify the pixels.
3) Min-cut is used to create a better segmentation between road and non-road parts.
4) the drivable area is marked ontop of the original frame (in red).

video

As can be seen in the video the results for most frames are excellent, but some frames still have a bit of trouble, this is common in the group of videos I tried it on. In addition, while most of the steps in this algorithm (GMM building and ML classification) are very fast, using the min-cut approach is very costly in terms of running time. As a consequence the algorithm works at a speed of approx. 1.5 fps.
So my upcoming work on this module will focus on these directions:
a) Gather more test data and see how robustly the module handles them.
b) Fine tune the parameters of the algorithm to try and overcome the difficult frames.
c) Improve the total speed of the algorithm. To do this I might need to find a different approach than min-cut. One idea is to use only Gaussian mixtures but have them adapt to changes over time (as was done by Thrun et al., Stanley: The robot that won the Darpa grand challenge)
That's it for now, I will post more news as the occur.
Happy Independence day :)