Ask Your Question

Shortest path in Blob: autonomous navigation

asked 2014-04-25 09:36:47 -0500

buhbuhbuh gravatar image


I'm trying to use SimpleCV with a car to perform autonomous navigation (on black tape lines on white floor) while avoiding obstacles (also black tape lines). So we realize that we can get the pixels of the image that correspond to the track by finding a blob that corresponds to the track the car is allowed to drive on. But does anyone know a good way of finding the shortest connected path between pixels in the blob? Is there any way we can easily extract all the pixels in the blob and then perhaps perform Dijkstra's algorithm on them?


edit retag flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted

answered 2014-04-29 10:09:16 -0500

kendallv gravatar image

Firstly, each pixel in the source image will probably represent a very short amount of space. Searching that grid is certainly possible, but it will probably be unnecessary. Dijkstra/A* search require a discrete set of points. You could indeed reduce your problem to a graph search problem by searching all the pixels (or, more sensibly, by chopping up the blobs into sections), but this would be throwing away information which might be useful.

I suspect that what you are looking for is a higher-level approach to this. For instance, instead of just finding blobs you might want to perform edge detection on those blobs; then you can follow the edge of the line. There is functionality in SimpleCV/OpenCV for this.

You need to constantly remember that computer vision is a pretty difficult task for computers, even though you are doing something that is conceptually simple for humans. Things like variation in lighting is going to be a problem, in particular if the car is moving; you might want to take inspiration from this video to deal with that particular problem.

edit flag offensive delete link more

answered 2014-05-18 14:18:37 -0500

buhbuhbuh gravatar image

Hi All,

I found the answer to my question and completed the project. You can find a video of what it does here:

The answer to my question was to use the blob's mMask, because this is a binarized version of the blob, with pixels in the blob being white and pixels outside the blob being black.

edit flag offensive delete link more


Awesome! Thanks in particular for linking the google doc in the video.

kendallv gravatar imagekendallv ( 2014-06-19 10:56:52 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2014-04-25 09:36:47 -0500

Seen: 749 times

Last updated: May 18 '14