Google Releases Key Part of Street View Pipeline

New submitter drom writes "Google released a key part of their Street View pipeline as open source on Tuesday: 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."

Mind telling us what are the "Better Technology" ?

[Taco Cowboy]

Good effort I guess, but there is much better technology out there.

Mind telling us what are the "Better Technology" ?

Thank you !

Re:

[S3D]

Well, I did some 3d reconstruction so I can answer that. The deficiency (not so important for most potential users) is that methods mostly 10-20 years old, no latest methods present. In robust estimators sections ("robust cost function) only "soft" L1 estimator present, no nonsmooth L1 estimators with solvers based on thresholds like Split Bregman and others. No constrained minimizers (solvers) which use Interior Point, Augmented Lagrangian etc. No dense and patch based reconstruction methods support. No g

Poor effort, there's much better trolls out there

[Anonymous Coward]

Your comment suggests you don't know what at minimizer is, and I think you just wanted to say "Google is bad" to the first story related to Google.

Which is a pity, but smarter trolls than you will have a go at them later.

If this is a constrained minimizer then Libre Office and Open Office will suddenly get a major improvement in their solver functionality for example, because at the heart of a solver is a decent non linear minimizer.

----
Fox News loves Bin Laden, hates President Obama for killing him.

Re:

[Garble Snarky]

Where is there a solver in open office?

Extra features

[Canazza]

Does it come with built-in Wi-Fi snooping?

Re:

[mcgrew]

Fanboys get mod points sometimes. As do employees. Hell, I've been modded down for mentioning Sony's evils in a story about Sony.

Re:

[Anonymous Coward]

I'd imagine it's probably because you're a troll.

Re:

[Anonymous Coward]

"git clone https://code.google.com/p/ceres-solver/ [google.com]" asks you for account with real name?

What exactly are you talking about?

Nonlinear least squares for dummies?

[bjourne]

Can any math pro explain what practical uses solving nonlinear least squares equations have? The Wikipedia page is to high-brow for me. :)

Re:

[justdiver]

How does failure to watch a video make someone illiterate? There's not even text in the video.

Ignore dvh

[Anonymous Coward]

The video shows you how they use it, not what it is. Parent is just trolling.

Take a curve, represented by some function with parameters.
Take a set of data points.
Fit the curve to the data points by changing the parameters.
Minimizing the error distances between data points and curve so you get a best fit.

It's easy enough for lines and polynomials, but for more general functions it becomes a real pain. The maths is straightforward, but the implementation can make a huge difference. Google's library looks like a well implemented minimizer and it's been road tested too.

This is good.

Re:

[Anonymous Coward]

To be fair, he did ask for *practical uses*, not what it is mathematically. Practical uses include the examples given in the article. Another example from computer vision would be to find world positions of 2D image features based on a set of pictures from different positions.

Re:

[Frans Faase]

Aside from the fact that it is a linear problem to solve (simple polynomial if you add lens correction), you also need a good feature extractor to create a 3D model from a set of 2D pictures. There are some excellent packages for doing 3D reconstruction, but they also come with a high price tag. There are some free implementations as well, but they are not very good.

Is seems to be an interesting solver, but you have to add a lot more for building an application for 3D reconstruction. I wonder if Google is g

Re:

[Anonymous Coward]

http://www.cs.washington.edu/education/courses/cse455/10wi/lectures/455sfm.ppt [washington.edu]

Re:

[qubezz]

To be fair, he did ask for practical uses...

Your "another example" is the example from the article...

I also have some authority in practical uses of technology (such as HTML 2.0-level markup), so I'll pipe up. For munitions guidance, this could be used to refine the inertial navigation position model for intercontinental delivery of ordinance by missile, maybe? When they outlaw nuclear missiles, only outla^h^h^h^h^h they will have nuclear missiles.

Re:

[mcgrew]

For illiterates like you

Don't you mean "innumerates?"

Re:

[gnapster]

No, GP meant "illiterate", because GGP was unable to read and understand the Wikipedia page.

Re:

[Anonymous Coward]

Least squares is an optimization goal which minimizes a particular metric for a global deviation between an ideal and an achievable solution, that metric being the sum of the squares of individual deviations. A non-linear optimizer performs the optimization for a problem which is formulated in nonlinear equations (i.e. which is not described by a matrix).

Re:

[Hatta]

Can any math pro explain what practical uses solving nonlinear least squares equations have?

Mapping the expected position of a car to GPS data, for example.

Re:

[LeDopore]

Kalman filters assume a linear relationship between predictor and response, while nonlinear least squares allow there to be a parametric known nonlinear relationship.

Re:

[Ouilsen]

Least squares is also often used in parameter fitting. Suppose you have a simulation with an somehow unknown parameter p. First you use a first guess as a value of p. That you run your simulation and get observed values y_obs.

Now you compare the computed values y_obs with the measured values y_mes using squares: cost = (y_obs - y_mes)^2.

By computing d p / d cost you may adapt p and redo the above steps till the squares are minimized... thus a least squares problem.

Re:

[BlackPignouf]

Let's say you have a very weird car with 4 engines, 12 wheels turning in different directions, 8 steering wheels, 5 gearboxes and 20 buttons.
You have no idea what each control does : some appear not to have any influence, some need to be used together, some have delayed influence, some cancel each other...
You can probably forget to get a perfect understanding of the car, and will never find the perfect driving strategy.

You just need a driver assistance system that will minimise the time needed as well as th

Yeah...

[IamTheRealMike]

From the source code:

// The reason why the Triggs approximation becomes so poor is
// because the curvature correction that it applies to the gauss
// newton hessian goes from being a full rank correction to a rank
// deficient correction making the inversion of the Hessian fraught
// with all sorts of misery and suffering.

Yeah, that's pretty much how maths makes me feel as well ...

Re:

[systemeng]

And it is clear as Mudd to me!

Re:

[rdnetto]

Wow, I actually understood some of that. And they said I'd never have a use for anything we learnt in linear algebra...

Usefulness of least squares

[Anonymous Coward]

When you have several measured points, and you want to fit a function to them, least squares is how you measure how closely your function fits. This is useful anytime you want to infer a trend into the future (extrapolation) or infer what values come between the measured values (interpolation).

If you can speed up least-squares calculation, you can test your theories faster and possibly using less hardware - making that kind of statistical analysis more accessible.

In Google's case, they are using it to adjust their raw GPS data so that they can get a more accurate idea of where they are.

3D Reconstruction

[wasteoid]

With this code, one could develop an application that can automatically render a 3D model from a series of images or a video. In other words, you could use a camera to "paint" a nearly photorealistic 3D model - no hours/days/weeks of Blender/CAD work to create a model, just scan with cheap camera. They state, "We have a working Android port but it's not ready yet." Envision an Android app that does this - scan your friends or nearby person into a 3D model - get complete geometry (height, calculated weigh

The RatSLAM project

[fragfoo]

The video at the Ceres Solver page reminded me a lot of the RatSLAM project. A project about mapping streets using a single camera as the only mapping sensor.

Related video here:

http://www.youtube.com/watch?v=-0XSUi69Yvs [youtube.com]

RatSLAM paper here:

http://eprints.qut.edu.au/32812/1/32812_Milford_2011000124.pdf [qut.edu.au]