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



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

6 comments:

Anonymous said...

Nice work.
Is it also working with obstacles?

Yair Movshovitz-Attias said...

The path finding algorithm works even when there are obstacles on the path (I might upload a video demo of it soon) The next challange we have is to calculate the exact distance from the obstacle in order to plan a path around it.

Anonymous said...

I wish not concur on it. I assume polite post. Specially the designation attracted me to be familiar with the whole story.

Anonymous said...

порно найти
порно видео присланные
сиски смотреть
видео фильмы секс порно
эксклюзивный порно журнал

Anonymous said...

Good dispatch and this enter helped me alot in my college assignement. Say thank you you seeking your information.

Anonymous said...

Brim over I assent to but I think the list inform should acquire more info then it has.