OpenSFM slow for large linear datasets

[BrookRoberts]

OpenSFM starts to take a long time for each additional image for me for longer sequences. Using a sequence of 700 images, the bundle stage starts to take closer to 20 seconds per image, rather than more like 2 seconds per image at the start.

The data I'm using is video, so I know that my images are all in order and only e.g. need to be matched with nearby frames. I don't have exif data, so something like matching_time_neighbors isn't applicable, but I've implemented my own similar config setting that should only take the 3 frames before and after. This indeed speeds up the matching substantially (since it only looks for matching pairs in nearby frames), but the bundle time per frame still grows.

Should it still grow? I presume the bundle is adjusting all of the points in our construction so far, but this seems like possible overkill, since my new points should only be added on the end.

Advice on config settings/directions to look at code to change for linear sequences would be appreciated!

[BrookRoberts]

As a related question (the above question is mostly aimed at - can I get linear time for bundling given I know my poses are linear) - I found the below config settings:

bundle_interval: 0 # bundle adjustment after adding 'bundle_interval' cameras bundle_new_points_ratio: 1.2 # bundle when (new points) / (bundled points) > bundle_outlier_threshold bundle_outlier_threshold: 0.006

Is there a good reason to bundle adjust after every new camera? (and camera here means actually camera, or pose?). And, given that I seem to still to bundle adjust on every frame currently, it's not clear to me what the second is supposed to do. Should the commment on bundle_new_points_ratio be associated instead with bundle_outlier_threshold? Or am I misunderstanding?

[paulinus]

Each bundle adjustment (BA) time grows with the number of images in the reconstruction. By default, OpenSfM runs BA after adding every camera. The reason is to ensure best fit of each camera added. As the reconstruction grows, this becomes very expensive.

You can reduce the number of BA by setting the bundle_interval to, say, 10. This will run BA every 10 images or as soon as the number of points grows by 20% (because of the bundle_new_points_ratio: 1.2). The logic of this is coded here https://github.com/mapillary/OpenSfM/blob/master/opensfm/reconstruction.py#L652-L656

An even better solution would be to code a partial BA that would only optimize the position of the last image added and the neighboring ones. OpenSfM lacks this ability at the moment and would be a great addition.

(The bundle_outlier_threshold is a threshold on the reprojection error of the points and has no effect on the number of bundles)

[BrookRoberts]

Thanks for your comments. I guess I also don't have a great feel for how much I lose by setting a large interval - do you have any sort of feel for what sort of accuracy loss I would get by increasing bundle_interval, and at what stage I would start to hit big problems (lets say if I also increased bundle_new_points_ratio).

[BrookRoberts]

Also, yes, a partial BA sounds like a very good idea, although I don't really know much about how bundling works/have an idea how hard that would be to add in. With default config, both the matching and the bundling exhibit nasty growth for scaling to large datasets. Matching is easy to fix for linear style data sets (and lots of others), so something similar for bundling would probably make opensfm substantially better for large scale reconstructions.

[BrookRoberts]

@paulinus is there any progress on this? I ask because it looks like you've started a branch working on this, so I'm wondering if I should just wait for that work to be finished, or try using your branch, or something else.

[paulinus]

Yes, I did an implementation of local bundle adjustment in the feature-local-bundle branch. You can try it from there.

What remains to be done before merging is deciding on how to trigger that feature.

Doing local bundle is useful for linear datasets where each image shares features with only a limited number of neighbors. I've tested on a 200 image dataset from a drone and each image was connected to half of the dataset, so there was not a big gain in doing the local bundle.

[BrookRoberts]

Great, thanks. Should I just check that branch out and run it, or do I need to play with some config first? If you like I can test it on some larger linear datasets and see what happens.

Do I understand that if I have a linear set of 500 images, and I use order_neighbours to only match each image with 20 images, this should result in a big speed up (e.g. because opensfm will only know about shared features with the neighbouring 20 images, regardless of whether they are in fact shared further).

[derekhoiem]

Another suggestion is to only perform bundle adjustment after a new ratio of images are added, e.g. 1.1 times as many as previous bundle adjustment are added. This is a simplification of the procedure described in VisualSfM and often works well i practice even without local bundle adjustment. The change is easy to make by adding a bundle_ratio test similar to the bundle_interval test.

[paulinus]

Yes, exactly @derekhoiem. That is a simpler way to reduce the number of global BA. Thanks for pointing out. I had forgotten that you can do that in OpenSfM by using the option bundle_new_points_ratio (it counts the ratio of new points instead of the ratio of new images, not sure if that makes any difference).

There is a case where local bundle might be preferable. When you have large linear datasets, for example, taken from a car, new images are only connected to recent images. This has two effects

• On the one hand, not running any bundle while adding a large number of images can break the reconstruction since new images will be added using points for which BA has never been run.
• On the other hand, global bundle adjustment is often unnecessary since the new images have little impact on the reconstruction of the older images.

So running frequent, local bundle adjustment might be a good choice there.

Bundler has an alternative strategy that I like but is not available in OpenSfM: when adding one image that has N points already in the reconstruction, also add any other image that has at least 0.75 * N points in the reconstruction, and bundle after that. This automatically does fewer BA for dense datasets, where most images are redundant, and more frequent ones for linear datasets.

[derekhoiem]

@paulinus, if I remember correctly (I may not), the bundle_new_points_ratio does not have much effect on its own, since BA will still be triggered by the bundle_interval value, but this strategy should work if bundle_interval is set very high (e.g., bundle_new_points_ratio=1.05, bundle_interval=500).

I agree that local bundle adjustment is a good idea, especially when the tracks graph is sparse. The VisualSfM idea combines these, running global on a ratio schedule but local only for the most recently added images. Your local BA addition will be very useful.

I have quite a bit of experience using OpenMVG, which also uses the 0.75*Npoints rule, but the behavior ends up being similar to bundle_interval where you end up having O(Nimages) bundle adjustments.

While we are on the topic of SfM for video sequences, is there any current plan to take advantage of spatial continuity of the camera in video, such as ORB-SLAM style tracking or priors/constraints on camera translations? The SLAM and SfM communities still feel disjoint, but it would be awesome to have one package that can do fast and robust video-based reconstruction as well as reconstruction from unstructured photos.

[pmoulon]

@derekhoiem Did you try to run openMVG GlobalSfM to see if you have enhanced speed (since in GlobalSfM fewer BA steps are performed you must have nice speedup).

[derekhoiem]

@pmoulon, I think we had a higher success rate with IncrementalSfM in early experiments and stuck with it from then on. My understanding from the literature is that GlobalSfM, though much faster, does not tend to produce as high quality solutions (more likely to have cameras with poor alignment due to local minima in optimization), especially if GPS is unavailable. Is that correct?

Btw, thanks very much to both @pmoulon and @paulinus and others for making these excellent tools available.

[pmoulon]

@derekhoiem You're right, incremental SfM reacts better with graphs that have poor image connections or few image tracks connection. But you must give a try on some datasets and see the result, since on many image graphs GlobalSfM can produce better camera poses than Incremental SfM. The most important part is often the construction of a nice input image connection graph (that depends a lot of your feature detector and descriptor).

Tip: You can play with the -v X option on main_ComputeMatches to restrict the pair matching on neighbors frames.

[paulinus]

@derekhoiem on the SLAM vs SfM separation, I totally agree that the problems are much closer to each other than the communities. There is no major reason why there couldn't be a single implementation that can do both SLAM and incremental SfM. And, if you think of SLAM as incremental SfM, then the SLAM methods are much more advanced.

I've been looking closely at ORB-SLAM and there are mainly three concepts that I would like to see added to incremental SfM methods

• pose-graph optimization, so that global alignments can be done faster
• keyframe selection, so that redundant cameras are removed from the optimization
• explicit loop closures. The key reason why SLAM is able to do loop closures is that it matches last frames and map points independently and explicitly decides that the new frame matches both sides. Incremental SfM aligns new frames to map points only via resection. When a loop closure is possible, the new frame will match two different positions but all SfM implementations will just take the one with more inliers and disregard the other one instead of using it to close a loop.

I have the desire to implement the above, but not the agenda.

[derekhoiem]

@pmoulon: Thanks for the comment and tip about global SfM

@paulinus: Thanks for these insights. If I can find an interested student (or get the time to do it myself), maybe I will be able to contribute one of these or another idea from the SLAM community.

[angussmitchell]

Hi, just wondering if anyone can update me on the location of the local bundle adjustment feature? It seems the linked local bundle adjustment branch has disappeared

[paulinus]

It has been merged to master. You can use the local bundle adjustment by adding the following settings to config.yaml

local_bundle_radius: 1          # Max image graph distance for images to be included in local bundle adjustment
bundle_interval: 9999999            # Bundle after adding 'bundle_interval' cameras

The first parameter says only images directly connected to the last added image should be optimized. The second parameter says that full bundle adjustment should be run every X images.

[ManishSahu53]

I don't know how much this would be helpful now as local BA is already merged but I think this paper solve for linear time issue in incremental BA. Towards Linear-time Incremental Structure from Motion