search

colmap / glomap

GLOMAP - Global Structured-from-Motion Revisited
BSD 3-Clause "New" or "Revised" License
1.3k stars 76 forks source link

Speed up reconstruction using iterative solvers #48

Closed eduardohenriquearnold closed 1 month ago

eduardohenriquearnold commented 1 month ago

I noticed that GLOMAP uses the SPARSE_SCHUR solver and the CLUSTER_TRIDIAGONAL preconditioner regardless of the number of images, whilst in COLMAP the solver/preconditioner for N>1000 images is ITERATIVE_SCHUR and SCHUR_JACOBI. Similarly, the GlobalPositioning optimization uses SPARSE_SCHUR and CLUSTER_TRIDIAGONAL.

I observed a significant speed up in reconstruction times for a large number of images (10k) when using the iterative linear solver (see details below). Specifically, a single global position optimization iteration was taking 280s (dominated by the linear solver), while the iterative solver iterations are generally in the order of seconds.

Is there any reason why the solver and preconditioner choices are different from COLMAP? Would a PR for this be welcome?

For context, I'm sharing excerpts of the logs below:

Original Solver/Preconditioner: SPARSE_SCHUR/CLUSTER_TRIDIAGONAL

Loading Images 10755 / 10755
Loading Image Pair 120741 / 120741
I0807 21:40:04.847411    32 colmap_converter.cc:301] Pairs read done. 127 / 120741 are invalid
I0807 21:40:04.860626    32 global_mapper.cc:76] Loaded database
-------------------------------------
Running preprocessing ...
-------------------------------------
I0807 21:40:04.913038    32 view_graph_manipulation.cc:244] Decompose relative pose for 120614 pairs
I0807 21:40:04.944976    32 view_graph_manipulation.cc:294] Decompose relative pose done. 8225 pairs are pure rotation
I0807 21:40:04.945501    32 timer.cc:87] Elapsed time: 0.08483 [seconds]
-------------------------------------
Running view graph calibration ...
-------------------------------------
I0807 21:40:04.945541    32 view_graph_calibration.cc:16] Start ViewGraphCalibrator
I0807 21:40:05.025068    32 view_graph_calibration.cc:33] No cameras to optimize
-------------------------------------
Running relative pose estimation ...
-------------------------------------
I0807 21:40:05.096072    32 image_undistorter.cc:17] Undistorting images..
I0807 21:40:05.289376    32 image_undistorter.cc:43] Image undistortion done
I0807 21:40:05.304637    32 relpose_estimation.cc:23] Estimating relative pose for 120614 pairs
 Estimating relative pose: 100%
I0807 21:52:38.941715    32 relpose_estimation.cc:69] Estimating relative pose done
I0807 21:52:40.857707    32 relpose_filter.cc:46] Filtered 8099 relative poses with inlier number < 30
I0807 21:52:40.871500    32 relpose_filter.cc:63] Filtered 45 relative poses with inlier ratio < 0.25
I0807 21:52:40.961160    32 timer.cc:87] Elapsed time: 755.86935 [seconds]
-------------------------------------
Running rotation averaging ...
-------------------------------------
I0807 21:52:54.937844    32 relpose_filter.cc:31] Filtered 2140 relative rotation with angle > 10 degrees
I0807 21:53:05.627408    32 relpose_filter.cc:31] Filtered 4 relative rotation with angle > 10 degrees
I0807 21:53:05.742159    32 global_mapper.cc:95] 10727 / 10755 images are within the connected component.
I0807 21:53:05.742187    32 timer.cc:87] Elapsed time: 24.78098 [seconds]
-------------------------------------
Running track establishment ...
-------------------------------------
 Initializing pairs 120741 / 120741
 Establishing pairs 120741 / 120741
 Establishing tracks 433326 / 433326
I0807 21:53:35.844884    32 track_establishment.cc:149] Discarded 14858 tracks due to inconsistency
I0807 21:53:38.062836    32 global_mapper.cc:115] Before filtering: 433326, after filtering: 215104
I0807 21:53:38.062876    32 timer.cc:87] Elapsed time: 32.31579 [seconds]
-------------------------------------
Running global positioning ...
-------------------------------------
I0807 21:53:38.782073    32 image_undistorter.cc:17] Undistorting images..
I0807 21:53:38.782231    32 image_undistorter.cc:43] Image undistortion done
I0807 21:53:38.782253    32 global_positioning.cc:43] Setting up the global positioner problem
I0807 21:53:39.571408    32 global_positioning.cc:134] Constrained positions: 10727
I0807 21:53:39.572266    32 global_positioning.cc:183] 215104 point to camera constriants were added to the position estimation problem.
I0807 21:53:39.572276    32 global_positioning.cc:200] Point to camera weight scaled: 1
I0807 21:53:42.597080    32 global_positioning.cc:68] Solving the global positioner problem
iter      cost      cost_change  |gradient|   |step|    tr_ratio  tr_radius  ls_iter  iter_time  total_time
   0  1.980000e+07    0.00e+00    5.31e+01   0.00e+00   0.00e+00  1.00e+04        0    9.77e-01    6.65e+00
   1  4.845751e+06    1.50e+07    2.28e+01   2.04e+04   1.51e+00  3.00e+04        1    2.84e+02    2.90e+02
   2  1.183440e+06    3.66e+06    9.78e+00   1.17e+04   1.51e+00  9.00e+04        1    2.81e+02    5.71e+02
   3  2.915622e+05    8.92e+05    4.41e+00   7.12e+03   1.50e+00  2.70e+05        1    2.81e+02    8.51e+02
   4  7.512704e+04    2.16e+05    8.87e+00   6.91e+03   1.45e+00  8.10e+05        1    2.80e+02    1.13e+03
   5  2.923402e+04    4.59e+04    4.38e+03   1.16e+05   1.16e+00  2.43e+06        1    2.81e+02    1.41e+03
   6  2.797865e+04    1.26e+03    4.46e+03   3.26e+04   7.06e-02  1.49e+06        1    2.79e+02    1.69e+03
   7  2.567539e+04    2.30e+03    4.50e+03   2.70e+04   1.34e-01  1.07e+06        1    2.78e+02    1.97e+03
   8  2.274001e+04    2.94e+03    4.44e+03   4.50e+04   1.82e-01  8.50e+05        1    2.78e+02    2.25e+03
   9  1.994631e+04    2.79e+03    4.49e+03   5.20e+04   1.91e-01  6.88e+05        1    2.78e+02    2.53e+03
  10  1.649637e+04    3.45e+03    4.51e+03   5.04e+04   2.62e-01  6.21e+05        1    2.78e+02    2.80e+03
[...]

Solver/Preconditioner: ITERATIVE_SCHUR/SCHUR_JACOBI

-------------------------------------                                                                                
Running global positioning ...                                                                                       
-------------------------------------                                                                                
I0807 22:29:58.665625    32 image_undistorter.cc:17] Undistorting images..                                           
I0807 22:29:58.665735    32 image_undistorter.cc:43] Image undistortion done                                         
I0807 22:29:58.665741    32 global_positioning.cc:43] Setting up the global positioner problem                       
I0807 22:29:59.453136    32 global_positioning.cc:134] Constrained positions: 10727                                  
I0807 22:29:59.453969    32 global_positioning.cc:183] 215104 point to camera constriants were added to the position 
estimation problem.                                                                                                  
I0807 22:29:59.453979    32 global_positioning.cc:200] Point to camera weight scaled: 1                              
I0807 22:30:02.589502    32 global_positioning.cc:68] Solving the global positioner problem                          
iter      cost      cost_change  |gradient|   |step|    tr_ratio  tr_radius  ls_iter  iter_time  total_time          
   0  1.980000e+07    0.00e+00    5.31e+01   0.00e+00   0.00e+00  1.00e+04        0    8.67e-01    2.90e+00          
   1  1.423978e+05    1.97e+07    2.82e+01   1.26e+03   1.98e+00  3.00e+04        2    3.05e+00    5.95e+00
   2  1.419064e+05    4.91e+02    3.56e+02   1.86e+05   9.24e-03  1.54e+04        3    3.30e+00    9.25e+00
   3  1.256365e+05    1.63e+04    1.86e+03   6.24e+05   3.01e-01  1.45e+04        3    3.75e+00    1.30e+01
   4  1.048112e+05    2.08e+04    3.00e+03   1.09e+06   3.76e-01  1.43e+04        3    3.29e+00    1.63e+01
   5  6.310880e+04    4.17e+04    4.58e+03   7.85e+05   8.04e-01  1.84e+04        3    3.29e+00    1.96e+01
   6  4.686433e+04    1.62e+04    4.54e+03   4.65e+05   5.06e-01  1.84e+04        6    3.73e+00    2.33e+01
   7  3.646131e+04    1.04e+04    3.78e+03   3.30e+05   4.28e-01  1.84e+04        4    3.43e+00    2.67e+01
   8  3.055635e+04    5.90e+03    3.63e+03   1.96e+05   3.04e-01  1.74e+04       12    4.69e+00    3.14e+01
   9  2.549611e+04    5.06e+03    3.64e+03   1.97e+05   3.09e-01  1.64e+04        6    3.72e+00    3.51e+01
  10  2.235586e+04    3.14e+03    3.64e+03   1.22e+05   2.25e-01  1.41e+04       16    5.26e+00    4.04e+01
  11  1.940977e+04    2.95e+03    3.58e+03   1.30e+05   2.32e-01  1.22e+04       78    1.48e+01    5.52e+01
  12  1.705174e+04    2.36e+03    2.94e+03   8.97e+04   2.16e-01  1.03e+04       12    4.69e+00    5.99e+01
  13  1.413151e+04    2.92e+03    2.70e+03   1.19e+05   3.04e-01  9.73e+03        6    3.72e+00    6.36e+01
  14  1.308238e+04    1.05e+03    2.64e+03   4.24e+04   1.28e-01  6.90e+03       66    1.29e+01    7.65e+01
  15  1.184906e+04    1.23e+03    2.35e+03   4.19e+04   1.63e-01  5.28e+03       44    9.62e+00    8.62e+01
[...]
lpanaf commented 1 month ago

Hi, for the iterative solver, my experiments show a significant performance drop (in terms of accuracy) when changing to an iterative solver. Also, after some iterations, the inner iteration numbers become quite large and the run time becomes long. Have you checked the result? Do they look similar in your case?

eduardohenriquearnold commented 1 month ago

Hi @lpanaf , thanks for your reply and apologies for the delay - running the experiments with original solvers/parameters took some time.

I can confirm what you have observed: the iterative solver seems to converge to some bad local minima for the scene I have tried, despite being much faster than the sparse Schur solver. Specifically, the default solver took 31h to reconstruct the scene with the vast majority of time being spent on BA (24h) and global positioning (6h). On the other hand, the iterative solver completed the reconstruction within 6h.

I believe BA can be made more efficient by tuning the #iterations and termination criteria at the expense of some accuracy. Potentially using the iterative solver only for BA could also work.

I wonder if the iterative solver is more prone to get stuck in bad local minima in the Global Positioning step, do you think this could be the case? Or do you have other hypothesis that explain this?

For completeness, I'm attaching the poses (camera centers) obtained by GLOMAP in blue and the iterative solver variant in orange. The lines link sequential frames.

glomap glomap_is

lpanaf commented 1 month ago

Hi, for your question, I cannot remember very clearly, but I can confirm that the global positioning step is quite sensitive to the iterative solver. For the bundle adjustment part, I remember that the iterative solver is also problematic for sequential input (it is somewhat better for unordered input). As for the reason, my guess would be the same as yours: local minima

eduardohenriquearnold commented 1 month ago

That's helpful to know, thanks. I'm closing this issue for now as it doesn't seem to be feasible to use iterative solvers for the aforementioned reasons.