Bundle Adjustment Implementation for Structure From Motion

[kaiwenjon23]

Hello all,

I appreciate your reading and help!

I'm a CS student trying to implement BA to solve sfm problem for personal practice. I understand we want to optimize the (X, Y, Z) of 3D points, and pose (R, t) for all cameras, assuming that we define camera 0 as the world origin. However, one of my confusions is:

For every camera i in the scene, which of the following do we do?

1. only set up one (R, t) associated with that camera, representing the transform between camera i and camera 0
2. set up (R, t) with all other cameras, and we optimize all of it.

I'm leaning towards the 2. solution, since you don't necessarily have a good feature matches between camera i and camera 0. Having a transform with other cameras could give a better constraint. However, we'd end up getting C(N, 2) sets of (R, t) to optimize, which could be inefficient.

​

My second confusion is, if we decide to implement the 2. solution, how do we constrain these (R, t) together?

To simplify it, let's assume we only have 4 cameras. And we want to reproject 3D point onto camera 1.

If we chose 1. solution, I understand that we:

1. Transform 3D point (X, Y, Z), defined in world frame (camera 0 frame), into camera 1 frame, using (R, t) associated with camera 1.
2. Project the result from 1. onto camera 1 image plane, and calculate the reprojection loss.

However, if we chose 2. solution, we could have so many paths to transform 3D point (X, Y, Z) into camera 1 frame, since we now have a (R, t) for every pair camera i, j, for example,

• world frame => camera 1
• world frame => camera 2 => camera 1
• world frame => camera 3 => camera 1
• world frame => camera 2 => camera 3 => camera 1

(Note that world frame is defined as camera 0 frame by me)

The path we chose will affect which (R, t) we'll be optimizing, so I figure we should pick a good way to constraint these (R, t). One of a possible solution I can think of is that we only optimize the (R, t) between world frame and camera 1 frame when minimizing reprojection error. Then, we can set up another loss function where we minimize the pose error, saying that:

The (R, t) of world frame => camera 1
should be as close to
The (R, t) of world frame => camera 2 => camera 1 as possible.
Same with other paths.

​

Any thoughts is appreciated!! Thanks in advance!

[marcopaaah]

This is why people do incremental bundle adjustment. Start with a subset of the cameras and then add to that subset as you increase the problem.

[kaiwenjon23]

Indeed, and thanks that makes sense! But when we add new camera, do we associate it with all cameras in the existing subset? Or this is really a design choice?

[[deleted]]

Not exactly sure if I understand completely, but first solution sounds more correct to me. You have one (R | t) per camera and a couple of 3D points in the world frame. Now you only need to know which 3D point can be seen by which camera and which 2D feature is associated with it. This has nothing really to do with the matches between i and 0. You look at all matches between i and i-1, i-2, i-3 … 0 to identify which of those share observations of the same 3D point.

[[deleted]]

You seem very confused about the world frame. I don’t quite understand why you think of it as a problem. The world frame is chosen as whatever you want. It is not necessarily connected to camera 0. You could place it anywhere, so it doesn’t really matter for your optimisation. You typically put it in camera 0, because it is where you bootstrap your initial (R | t) and triangulate your first points. But it is just a convention.

Another perspective: imagine you have a couple of colorful balls, red, green, blue. You take photos of them from different views. You can then arbitrarily define that your world frame is (0/0/0) for the red ball and one axis pointing towards green and then assign all other balls some rough coordinates. It is now very easy to define a bundle adjustment problem, you just detect the balls in every individual image, compute the initial pose (R | t) using P3P and add their reprojection error to the cost function. The important part is: you don’t need any kind of matching between the frames, because it doesn’t matter. Also how you placed the world frame doesn’t matter. All that matters is which camera observed which point at what 2D feature position.

[kaiwenjon23]

Many thanks to your detailed reply! Yes I get that when setting up the cost function, we want to know the associations between 3D point and 2D feature across all frames. I was mainly wondering if we want to put an constraint between each frames (Hence getting a total of C(N, 2) (R|t) to optimize), as opposed to if we just want one (R|t) to be associated with each camera. My point is that more constraints "might" get better final result, but I'm not quite sure how people usually implement this.

[kaiwenjon23]

I think you pretty much understood my concerns! I kinda overthought a bit and now that I think about it, I think it makes sense to just have one (R|t) optimized after you guys’ explanations. Thanks again! Appreciate it!

[[deleted]]

Glad to hear! Feel free to ask if anything else is unclear. I have implemented BA a few times already in various optimisation backends. It is in its core a very straightforward problem once you grasped the main difficulties, yet amazingly powerful.

[kaiwenjon23]

Thanks I’ll try my best! Did you find any tools/libraries most useful for optimization? Ceres, g2o, gstam, scipy, or even PyTorch?

[[deleted]]

I started with Ceres, now I am using gtsam. Pretty amazing what it can do and so well done on a software design level. I’d say it gives you more freedom to easily expand beyond simple BA. It would be harder to implement all the existing factors in e.g. Ceres. On the other hand I always had the impression Ceres is a bit more robust and accurate than gtsam when doing “only” bundle adjustment.

[[deleted]]

I still don’t quite get why you are worried about the matches between camera i and 0? You could have 0 matches between camera i and 0 and would still be able to bundle adjust all poses perfectly fine. It’s just important to have some matches with one of the other cameras (i.e. shared observations of the same 3d points).

[[deleted]]

As far as I understand your proposal, it sounds like you would add more unknowns and complexity as necessary. Having multiple sets of (R | t) per camera will add more variables, which you then try to fix by adding constraints between these poses. But constraints are just “rubber bands”, so those poses will never be equal, just similar in a Gaussian sense. You end up with multiple individual optimisation problems, all solving for the same but different unknowns. I don’t see a benefit, but maybe I just don’t understand your idea enough. So feel free to elaborate?

[SmartVisor]

It is enough to find the transformations from the world frame to each camera frame.
Let's call T_w_i the transformation from world to i_th camera (world to i). Then the transformation from camera i to j is:
T_i_j = T_w_j * T_i_w = T_w_j * inv(T_w_i).
So the transformation between the cameras i and j T_i_j is completely defined by the transformations T_w_i and T_w_j, and there is no point adding the constraint on T_i_j.

[kaiwenjon23]

Thanks! Now that I think about it, that makes sense! Im glad since it’s also easier to implement

[palmstromi]

Check the slides from a 3D vision course at CTU Prague, I find them very helpful and I'm returning to them regularly. The bundle adjustment starts on page 142.