Google open sources key piece of Street View technology

http://google-opensource.blogspot.com/2012/05/introducing-ceres-solver-nonlinear.html

by mierle • 14 years ago

350 51 14 years ago

google-opensource.blogspot.com

jacquesm• 14 years ago

Neat, what a pity that real hacker news gets under-appreciated!

jlapenna• 14 years ago

The video in the link is awesome. So that's how Google figures out roads and stuff!

mierle14• 14 years ago

This is a key component of Street View. We're really happy to have released this. When we started writing Ceres, there was nothing available like it. It's state of the art; a real contribution to computer vision and other fields which need large scale nonlinear least squares.

Part of the reason I worked on this in my spare time (my real job at Google is something else) was to get it integrated in libmv (http://code.google.com/p/libmv) and subsequently integrated into Blender. This opens the door to many sophisticated tracking features, like autocalibration, rolling shutter, multi-shot solves, tripod solves, planar tracking, and more.

EDIT: Changed link title to make it more provocative

mierle14• 14 years ago

There's some more discussion over at Reddit: http://www.reddit.com/r/programming/comments/t1mo7/ceres_sol...

vibrunazo• 14 years ago

What exactly would you use this in Blender for? As a library for someone to build a script that would turn 2d photos into 3d objects or something? Could you expand on that?

ot3• 14 years ago

I guess that one application would be camera tracking to implement automatic compositing of 3d models into videos.

mierle14• 14 years ago

Blender got integrated matchmoving / tracking with the 2.61 release, by way of libmv (which I am the BDFL of). A critical part of many tasks in 3D reconstruction and tracking is a solid, flexible nonlinear minimizer. Since Ceres is so easy to model problems with, is so fast, and is appropriately licensed (unlike some alternatives), it is an enabler for these more sophisticated tracking operations.

Note that Blender's next open movie, http://mango.blender.org, is live-action done with Blender's tracking tools. Ceres is going to be used for that as well.

yellowbkpk• 14 years ago

When you say "a key component of Street View", which part is it a key component of? Snapping vehicle track data to existing roads? 3D model computation for scene-to-scene jumps? Both?

If you're snapping track data to roads, how do you deal with areas where you have no existing data? Do you take into account aerial imagery?

</openstreetmap-nerd jealous="true">

mierle14• 14 years ago

Unfortunately we can't talk much about this; sorry.

est• 14 years ago

Google Street View was filmed at 30fps video format. You can generate a 2D route map directly from it without GPS or when GPS is not available.

I took some notes during the StreetView Q&A on reddit two years ago: http://blog.est.im/archives/554

davidjohnstone• 14 years ago

It would be nice if we could use it, or (better) if Google exposed the ability in the Maps API, to fit paths to the most likely road, just like is being done in the demo video on the project page.

mierle14• 14 years ago

The roads are not an input to the optimization shown in the examples. How this works is left as an exercise for the reader.

follower• 14 years ago

Thanks for adding your note about integrating this into Blender--that makes the news much more relevant to my interests. :)

I was looking forward to integration of motion tracking into Blender and had a small play with the feature when released. Now I just need to make the time to play some more...

fgcallari2• 14 years ago

Yeah!!

mierle14• 14 years ago

Took long enough but we finally made it!

julienr• 14 years ago

Good job !

strebler• 14 years ago

What exactly is the operation being done in the video? My best guess is a noisy set of GPS coordinates / panoramas being repositioned via bundle adjustment on the street view panoramic captures. Or something.

sandwichmaker5• 14 years ago

In the video, no vision/bundle adjustment is used, just GPS, IMU and other sensors.

leegao• 14 years ago

I think I can sort of see what's going on, we're trying to fit the data of some GPS position taken from a walk around the park or something similar, and fit it to some linear combination of basis of some "street functions" to minimize its two-norm, where the "street function" corresponding to each street for some point (x,y) is some measure of how far away from the street that point is.

For example, in the subproblem of only one-way streets that we can assume to be composed of one or more segments of straight lines per street, we take a simple street-function $\phi_i(x,y)$ corresponding to street i to be the norm of the projection of <x,y> onto that street. Furthermore we also add into the system some "smoothing-function" to ensure that the overall shape of the final path is doable, for example constraining the distance between successive points. Next, we solve the argmin of the norm equation for each point so that each point is now moved to some linear combination of the streets, and truncate all but the most significant street basis, and rerun until we get to some acceptable tolerance.

Maybe?

ot3• 14 years ago

> Automatic differentiation

This is extremely cool. The documentation seems to be a WIP on this, can anyone comment on what kind of cost functions are supported by automatic differentiation?

EDIT: it would be also interesting to see how this compares to Theano [1], which also does symbolic differentiation and can JIT to native code and GPU. It is a largely more generic framework, but I'm not sure how well it can handle large sparse problems.

[1] http://deeplearning.net/software/theano/

sandwichmaker5• 14 years ago

You can define define arbitrary functions. You are only limited by the operator overloads defined in jet.h. Let us know if you think something is missing.

ot3• 14 years ago

I guess you mean arbitrary expressions, just using arithmetic operations and the overloaded functions (I see that abs, log, sin, cos, ... are supported).

What happens if I try to use an if-then or a for loop depending on one of the variables?

ArbitraryLimits2• 14 years ago

It means automatic numerical differentiation, not symbolic.

mierle14• 14 years ago

No, this is not true. Autodiff != numeric diff.

While we do support numeric differentiation, we don't suggest you use it. What we have is automatic differentiation, which is a technique to take exact derivatives without resorting to symbolic differentation.

Check out he jet.h file which is the core implementation of this:

http://code.google.com/p/ceres-solver/source/browse/include/...

The header comment has a nice description of autodiff.

In summary, Ceres supports three ways to compute derivatives:

(1) Automatic differentiation (easiest, fastest, most accurate)

(2) Numeric differentiation (easy, but worse convergence and hazardous)

(3) User-supplied jacobian (use a pen and paper then implement the jacobian for your residual manually)

sandwichmaker5• 14 years ago

From a very brief look Theano is an expression evaluator. It optimizes expressions, it does not solve numerical optimization problems.

I think it can be used as a backend in Ceres to push computations to the GPU, but as it stands it is a different category of software than Ceres.

slig• 14 years ago

In the video they figure out the road inside a tunnel, with no GPS data. How does it do that?

mierle14• 14 years ago

Fusing sensor data (IMU, etc). You can formulate this as a (extremely) giant sparse least squares problem.

cft• 14 years ago

That's no Instagram, no Facebook, this is technology, not Hollywoodisation of Silicon Valley

pkh80• 14 years ago

It'd be great if this is just the start of a trend where Google supports open source mapping tech that would make projects like OSM more viable (for reasons why its not currently viable see my other posts.)

Its a bit like Google being the biggest supporter of Firefox, even though they are also a competitor (Chrome.) Though Google supporting OSM is more like Microsoft supporting OpenOffice, since Google has such a large monopoly in maps right now.

jetsnoc• 14 years ago

Thank you for your contribution. It's great to see a giant, who's gained so much from open source contribute back in a significant and meaningful way! For those interested it appears it was open sourced under the "New BSD license."

rmc2• 14 years ago

Google has often contributed code to the open source world (like this). However they don't AFAIK release any data. Google drove cars around the world photographing everything. But they claim copyright on it all. If they allowed derivative works of it, then Open Street Map could bloom and benefit massively.

rmc2• 14 years ago

Downvotes because I point out how Google can donate data, not just code? ☹

sparky• 14 years ago

Awesome! I just filed a few bugs with patches that let it build out-of-the-box on Ubuntu. There didn't seem to be much in this space outside of levmar ( http://www.ics.forth.gr/~lourakis/levmar/ ); levmar is great for what it does, but some friendly competition is most welcome from my perspective.

It's really surprising how broadly applicable non-linear least squares is.

sandwichmaker5• 14 years ago

Thank you for the bugs and the fixes.

mierle14• 14 years ago

Working on integrating fixes now...

mierle14• 14 years ago

Done!

fgcallari2• 14 years ago

Trust me if I say that this baby's performance on large problems is to good'ole levmar what Ferrari is to tricyle. Or rather, don't, just benchmark them and see for yourself ;-) Kier, Sameer and Co. have done an amazing job here.

eliben• 14 years ago

From a cursory look - that's a nicely organized, formatted and documented piece of code. Well done.

joelthelion• 14 years ago

This is much more than a key piece of Street View. It's an awesome building block for thousands of very diverse AI applications. Great contribution!

JoeCamel• 14 years ago

Johnny Lee has written a short post about Ceres: http://procrastineering.blogspot.se/2012/05/today-sameer-aga... "If I find the time, I might try to post some tutorials on using Ceres. Because I believe this is one of the most powerful tools in modern engineering, and no one ever taught it to me in undergrad or high school. It's like the difference between doing long division by hand and then being handed a calculator."

Google open sources key piece of Street View technology

Related Stories