4

I am analyzing a stream of data and I want to seed every new instance with the best guess output (line) of the previous, so as to eventually converge.

Given that Scikit Learn - RANSAC is an iterative model is it possible to seed it with a best-guess / prior linear model to aid outlier detection and model-fitting?

Update: Context

I am working on a lane detection system using a stream of video frames. I use RANSAC for lane detection after passing the image through various filters. Given that lanes do not vary much across adjacent frames I could seed the output of the previous frame to the current (useful when the filters don't yield a good signal/noise ratio, for example: bridge shadows / sun glare in frames).

Manav Kataria
  • 93
  • 7

1 Answers1

4

Here's RANSAC in a nutshell:

  1. Pick a random subset of samples
  2. Fit the model on the subset
  3. Add any sample with a small residual to the subset
  4. Score the model on the subset, and test if it's the best score so far
  5. If it is, store the model
  6. Try again

Notice that the only information used from previous iterations is the best-so-far score. So the only way you could "seed" RANSAC is to provide the score of your linear model on the subset closest to the line.

Now SKL doesn't support that functionality out the box, but fortunately Python is an interpreted language, so it's pretty easy to add. All you need to do is take the RANSAC source and

  • Change all references of score_best to self.score_best
  • Change the initialization score_best = np.inf to if not self.score_best: self.score_best = np.inf
  • Then you can seed the model by instantiating a RANSACRegressor object and setting model.score_best.
Andy Jones
  • 2,146
  • 9
  • 10
  • Thanks for the answer @andy-jones! I've never messed with SKL source. Your answer is an encouragement to start! I want to seed a line/estimator model for which I am considering using `subset_idxs` as a seed. Thoughts? Would just seeding `score_best` yield a worthy estimator? – Manav Kataria Jan 13 '15 at 23:57
  • I'm not quite sure what you want: do you want the active set to be carried forward through iterations, with each iteration adding/removing a few indices and refitting the model to see if it's better? If so, that isn't RANSAC. It'd be better suited by simulated annealing. – Andy Jones Jan 14 '15 at 00:14
  • I've just reread your post and remembered you're working with data streams. [Could this be what you want](http://stats.stackexchange.com/questions/6920/efficient-online-linear-regression), an "online" (stream) algorithm for fitting linear regression models? – Andy Jones Jan 14 '15 at 00:20
  • Andy, your answers and comments have definitely pointed me in the right direction! Unfortunately, I didn't understand well in advance that the bounty would be lost and not auto-assigned even if you were the only one who had provided an answer, my bad. I will provide you with another bounty for your timely help. To answer your comment above - I am not yet sure what model would suit me best RANSAC, Simulated Annealing or Online Linear Regression. It might be a combination. I am working to figure it out. I've added context. – Manav Kataria Jan 16 '15 at 00:53
  • StackOverflow isn't letting me add another bounty to this question to reward you back unfortunately. My apologies for not being decisive enough! – Manav Kataria Jan 16 '15 at 00:56
  • Don't worry about the bounty. WRT lane detection, is there a reason you're inventing your own scheme rather than using one of the extant algorithms or implementations? If you're keen to stick with your current approach, I can sketch a simulated-annealing-based scheme that would do what I think you're wanting RANSAC to do. – Andy Jones Jan 16 '15 at 02:24
  • I am not bound to this or any approach. I am simply trying to solve a problem and learning a huge amount along the way by attempting to implement the ideas. I am more interested in learning than a ready solution. – Manav Kataria Jan 16 '15 at 03:06