Forgot your password?

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

Submitted by drom
drom (26464) 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 (#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 contributors.

Computers can figure out all kinds of problems, except the things in the world that just don't add up.