Results comparison

[charlsb]

Hello Kyle,

It's been a while since your last post here. Hope you are still active. Currently I'm studying your awesome work and I really appreciate you for sharing the code.

After playing around with it I noticed that there were a difference between the results reported in the paper (baseline) and the ones that I obtain, so I would like to share the them with you.

I've run _eccvdemo.py for most of the scenes from the dataset provided at the 1DSfM project page, with no robust loss function neither final BA:

Red horizontal lines represent the median values reported in your paper (Table 2: with 1DSfM, no BA), and boxes represent the distribution of the values obtained.

I have two main concerns:

1. Results are slightly different from the baseline. Not too much, but something substantial, imho. Do you think it is ok to expect this kind of difference?
2. Dispersion of the results is large. From one run to another, result may vary considerably. I guess that it could be related with the stochastic nature of the outlier removal procedure. Nevertheless, the (random) initialization of translations solver could also affect the results. Could you please shed some light on this issue and help me to understand the reason of such behavior?

Best, CB

[wilsonkl]

Hi CB, Thanks for your interest! This is an eight year old paper now, so I'm pleasantly surprised that it's still being looked at.

You'll notice a trend in the work since then to find solvers that don't have so much run-to-run variation. There are some pretty cool projects out there! But 1dsfm was early enough that there wasn't an expectation of that yet. The run-to-run variation is pretty rough.

Your charts are for a single run, right? It looks like a couple datasets landed on solutions that are significantly better that what I reported, and most did worse. It's hard to say if that's signal or randomness. If there is a reason that your results tended to be generally better than what I reported, perhaps it's related to 8 years of improvements to ceres-solver? That's wild speculation.

Run-to-run variation (in my opinion) is about the loss surface. It's poorly conditioned. Many solvers have to deal with non-convex loss functions, where global optimality is not guaranteed. But there are degrees of non-convexity. For example, the bundle adjustment loss is particularly pathological because any motion that moves a point from in front to behind a camera creates a hyperplane of infinite residual in the loss surface. The 1dsfm loss function is angular, which also creates very "spiky" terms in the loss because small spatial motions can result in large changes in angle when two points are close to each other. All that is to say, this loss function is quite non-convex and has a lot of local minima. The noisier the problem, the worse the situation is. Multiple random initializations will often find multiple different local minima.

I think I've gone a bit long with this reply. If I missed part of the question, or you're interested in talking more, I'm happy to continue the conversation.

[charlsb]

Hi Kyle, Thank you so much for your time and your answer. I've found it really useful.

I know that it isn't the latest paper about the topic, but I think that it is a very nice starting point since it is very well explained and the provided code is very intuitive and well documented. It lets other people to modify it easily. In my case, I would like to use it as a baseline, adding to the SfM pipeline a new research I'm helping to as an "intermediate step". In any case, are there any specific newer projects that you would recommend?

Your charts are for a single run, right? ...

Actually, they are for 10 runs, so I could represent the distribution of the results as a box-plot. But I agree with your opinion. Additionally, I'm running it on MacOS, using specific libraries (like Accelerate) and such a new/different configuration can yield to an improved solution.

Run-to-run variation (in my opinion) is about the loss surface. ...

About the run-to-run variation, I was thinking on exactly the same. I'm glad to hear that your opinion is the same as mine (but yours is far more detailed 😅). Moreover, I've modified the code in order to specifically set the random seed and now I'm able to see how the results get better or worse depending on the initialization value.

However, I've perform an additional test and its results are disturbing me. Instead of using the rotations computed by the rotation averaging method (RA), I wanted to directly use the ground-truth rotations from Bundler (GT Bundler) in order to see how "optimal" the results could be. So I've used your already defined function for that purpose: global_rot_ids, global_rots = gt_bundle.all_rots() global_rot_ids = global_rot_ids.astype(np.int32)

Median values look similar to the ones reported on my previous post: (Please, notice again that red horizontal lines represent the values reported in your paper and boxes represent the distribution of the values obtained)

But, surprisingly, mean values are far worse than the ones obtained by the RA-based executions (except for the "Madrid Metropolis" and "Tower of London" datasets):

I know that using the ground-truth rotations directly from Bundler leads a problem with a larger number of views, many of which don't belong to the largest/main connected component. Nevertheless, I've also run another experiment just using the views within the largest/main connected component (and their corresponding ground-truth rotations). Results are pretty much the same. IMHO, the reason behind this strange behavior is the same as in the case of the variation. I mean, the loss surface here presents a narrower global minimum and the local minima gets a higher/"worse" loss value. Any thoughts about it?

I think I've gone a bit long too. I apologize if it is too much and thanks again.

Best, CB

[wilsonkl]

Hi CB,

That was long! Sorry, but it's taken me a while to find time to reply.

In any case, are there any specific newer projects that you would recommend?

I'll start by mentioning that TheiaSfM and openMVG both implement my 1dsfm code inside larger projects. This is really handy because those packages include full pipelines, and they make it easy to swap components in and out.

These are a little more theory-heavy, but here are a few more paper that caught my eye:

• Paul Hand's ShapeFit and ShapeKick give globally optimal solutions to translations problems.
• Eriksson et al did Rotation Averaging and Strong Duality, which (often) gives certifiably optimal solutions to rotations averaging problems

There was also a paper with a novel depth representation that created a much nicer loss surface for translations averaging. Sorry, but I'm not remembering the citation.

Actually, they are for 10 runs...

Ah, okay. I misunderstood. A thought thought- means and medians are quite reductive. As a researcher, I often learned something from visualizing the full distribution of errors.

But, surprisingly, mean values are far worse...

When medians look similar but means are far worse, we're looking at outliers, right? In principle a single camera that got triangulated to a long ways away could cause this behavior. (Also check, are you sure that you're dealing with a single connected component? A problem containing a disconnected small fragment would look like what you're describing.) Any time you're restricting a graph to a subgraph there's a potential of losing connectivity.

IMHO, the reason behind this strange behavior is the same as in the case of the variation.

To me, this sounds plausible but speculative. It's a little tricky to characterize the perturbation that you made. By comparing the RA-based rotations to the Bundler rotations you're changing both the rotation values themselves and also the graph that's underlying the probem. I'd want to understand the nature of that graph change before speculating more. (And for that matter, it's not hard to directly study the change in the rotations themselves. Is that a big change? Are there outliers?)

-Kyle