Author Topic: RANSAC  (Read 5005 times)

0 Members and 1 Guest are viewing this topic.

Offline benjiTopic starter

  • Supreme Robot
  • *****
  • Posts: 830
  • Helpful? 0
RANSAC
« on: January 17, 2008, 04:35:07 PM »
anybody of you folks have ready SLAM for dummies, i need someone to explain the RANSAC algorithm to extract the landmark lines,, i didnt get it quite well,,,,
good ol' BeNNy

Offline Admin

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,703
  • Helpful? 173
    • Society of Robots
Re: RANSAC
« Reply #1 on: January 17, 2008, 04:40:21 PM »
hmmmm haven't heard of it . . .

but google seems to have a lot about RANSAC and SLAM

Offline dunk

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 1,086
  • Helpful? 21
    • dunk's robot
Re: RANSAC
« Reply #2 on: January 17, 2008, 06:10:43 PM »
what don't you understand exactly?
RANSAC is performing SLAM by identifying straight lines in the surroundings and using them as features to  track the bot's position.
the doc does not tell you how to extract the lines. it presumes if you are thinking about tackling the SLAM problem then you will be able to work this bit out on your own.

for some background on straight line extraction try searching for "Hough transform".
it appears RANSAC is using a "least squares" algorithm to identify the line.

for what it's worth i played with line extraction as a method of finding features for SLAM but found it too processor intensive.
admittedly RANSAC appears to be far more efficient at extracting the line than my algorithm. i'll need to give that more thought.


dunk.

Offline Kohanbash

  • Supreme Robot
  • *****
  • Posts: 430
  • Helpful? 1
Re: RANSAC
« Reply #3 on: January 17, 2008, 07:46:23 PM »
Here is some psudo code for RANSAC that I use for stereo:

Do n times:

– Find a set of point correspondences between the images
– Start with a random incorect answer in the correct form (In my case finding the fundemental matrix)
– Compute the error between the points and the computed random error
– If error > errorConstant , recompute random solution and iterate n

Returned solution
Robots for Roboticists Blog - http://robotsforroboticists.com/

Offline Admin

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,703
  • Helpful? 173
    • Society of Robots
Re: RANSAC
« Reply #4 on: January 18, 2008, 07:36:15 AM »
to add on to what sdk32285 said . . .

you need to account for multiple matches based on an IMU (for example, a house has dozens of corners and walls that look exactly alike)

Offline benjiTopic starter

  • Supreme Robot
  • *****
  • Posts: 830
  • Helpful? 0
Re: RANSAC
« Reply #5 on: January 19, 2008, 04:51:58 PM »
thanks folks for the answers and sorry for not defining my question, actually i could extract straight lines in ransac with least square approximation
,,my problem is not here,, but ok , i had one sharp ir scan and i extracted the stright lines, then move the robot and do another scan and do extract stright lines,,but how do i associate these to the old ones?

how can i know that i have seen the same wall(straight line) how would the robot know if this is the same line???????
that is what makes me confused !!!!!
good ol' BeNNy

Offline Kohanbash

  • Supreme Robot
  • *****
  • Posts: 430
  • Helpful? 1
Re: RANSAC
« Reply #6 on: January 19, 2008, 06:29:59 PM »
usually you would use an IMU/GPS so that you know where each line is relative to another
Robots for Roboticists Blog - http://robotsforroboticists.com/

Offline benjiTopic starter

  • Supreme Robot
  • *****
  • Posts: 830
  • Helpful? 0
Re: RANSAC
« Reply #7 on: January 20, 2008, 06:06:05 AM »
how do u implement this in a robot?
good ol' BeNNy

Offline dunk

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 1,086
  • Helpful? 21
    • dunk's robot
Re: RANSAC
« Reply #8 on: January 20, 2008, 07:57:13 AM »
Quote
how can i know that i have seen the same wall(straight line) how would the robot know if this is the same line?HuhHuh
the robot knows approximately how far it has moved and the direction it has moved in.
based on this information it will expect to see an object in the same place it last saw one. if it sees an object in a slightly different position it has to decide the probability of whether it's a new object or whether it's the same object and the robot is off course.
the robot does not ever know this 100%. it has to decide which is the most likely solution.

as i think has already been said in another thread, SLAM is not easy.
i get the impression you want to do this with only IR distance sensors?
expect to spend a *lot* of time thinking about probability and statistics and quite possibly never getting a working solution.

good luck!

dunk.

Offline Kohanbash

  • Supreme Robot
  • *****
  • Posts: 430
  • Helpful? 1
Re: RANSAC
« Reply #9 on: January 20, 2008, 09:22:59 AM »
If you are only using an IR distance sensor than accurate wheel odometry is very important. So for example consideration like driving on concrete vs sand  and ackerman steering vs differential steering (commonly called skid steering) are critical (you slip more on sand, and you skid a lot with differential drive).
Robots for Roboticists Blog - http://robotsforroboticists.com/

Offline benjiTopic starter

  • Supreme Robot
  • *****
  • Posts: 830
  • Helpful? 0
Re: RANSAC
« Reply #10 on: January 20, 2008, 03:59:04 PM »
im gonna use a sharp IR with a compass , and my robot is a hexapod . so im expecting a good odometry.
 

good news dunk,,lol,, thats very motivating, have you tried on this one?
good ol' BeNNy

Offline dunk

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 1,086
  • Helpful? 21
    • dunk's robot
Re: RANSAC
« Reply #11 on: January 20, 2008, 05:10:12 PM »
Quote
good news dunk,,lol,, thats very motivating, have you tried on this one?
i'm working on it. haven't done anything with the SLAM part of my project for a few weeks.
i'm taking a different approach to you i think. i won't have particularly accurate optometry but my ranging data will be very good. i'm using my home made laser ranging system. details in this thread: http://www.societyofrobots.com/robotforum/index.php?topic=2220.0

i plan to implement the ATLAS approach but i have not really written much code for for loop closing yet.

out of interest, what are you going to be using as an on-board processor for this?


dunk.

Offline benjiTopic starter

  • Supreme Robot
  • *****
  • Posts: 830
  • Helpful? 0
Re: RANSAC
« Reply #12 on: January 21, 2008, 06:15:39 AM »
im using an atmega32 on a robot connected to the pc by a serial port ,,the brain of slam is gonna be implemented in matlab so the avr would just have walking arrangement commands,, what abouyt yours?
good ol' BeNNy

Offline dunk

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 1,086
  • Helpful? 21
    • dunk's robot
Re: RANSAC
« Reply #13 on: January 21, 2008, 08:42:22 AM »
i'm using a re-flashed Linksys NSLU2 on-board. http://www.nslu2-linux.org/
i suspect i'll need to upgrade to a more powerful processor before the project is finished but the NSLU2 works fine for what i'm doing so far.

dunk.

Offline benjiTopic starter

  • Supreme Robot
  • *****
  • Posts: 830
  • Helpful? 0
Re: RANSAC
« Reply #14 on: January 21, 2008, 08:54:34 AM »
i always prefer somthin big like matlab to do mathematic algorithms,,, that eases work a lot, programing in matlab language gives the ability to use the matlab functions ,,which you always would use, specially dealing with matrix
good ol' BeNNy

Offline benjiTopic starter

  • Supreme Robot
  • *****
  • Posts: 830
  • Helpful? 0
Re: RANSAC
« Reply #15 on: February 02, 2008, 11:21:37 AM »
this is a RANSAC MATLAB toolbox for anyone interested,,someone did a nice job

www.mathworks.com go to the exhange files section its there
good ol' BeNNy

 


Get Your Ad Here

data_list