drom - Slashdot User

+ - Google releases key part of Street View pipeline-> 0

Submitted by drom on Tuesday May 01, 2012 @12:23PM

drom writes "Google released a key part of their Street View pipeline as open source today: Ceres Solver. It's a large-scale nonlinear least squares minimizer. What does that mean? It's a way to fit a model (like expected position of a car) to data (like GPS positions or accelerometers). The library is completely general and works for many problems. It offers state of the art performance for bundle adjustment problems typical in 3D reconstruction, among others."
Link to Original Source

Comment: Re:Very cool, but np-complete? (Score 5, Informative) 48

by drom on Thursday February 19, 2009 @08:41PM (#26924419) Attached to: Found In Space (On Flickr)

You can think of our search as randomly trying millions of possibilities and hoping for the best. The reason it's so fast is that we order the random attempts very cleverly and tend to find the answer fast if it is indeed solvable. The algorithm usually terminates because it finds a match or times out; rarely does it exhaust the search space in time. The actual complexity of our system is roughly O(N choose 4) where N is the number of stars in the image. Interestingly, this is polynomial, roughly O(N^4), though probably closer to O(N^5) once verification is added.

In summary: the astrometry problem is not NP-hard when approached like we do.

Disclaimer: I am one of the astrometry.net contributors.