How to reduce the running time of global ba when there are some many tracks?

sephyli commented 1 month ago

Data description

I'm working on video captured by driving cars with surrounding-view cameras.
For each camera, I have a roughly calibrated intrinsic and I set it as the prior.
For each image, I have an estimated pose from SLAM.
I want to refine bose the intrinsic and the pose with colmap/glomap.
For one sample video, the amount of images are about 3000. After filtering, the image pairs are about 37w, tracks are about 70w.

Questions

I run the whole glomap pipeline, and the global ba costs more than 20 hours and are still running. Is that normal?
Since I have the prior pose for bose location and rotation, can I just skip the relative pose estimation, rotation averaging and global positioning part, to save some times? Before BA, can I just filter the image pairs, do triangulation, and create tracks?

lpanaf commented 1 month ago

Hi, for your questions, I think this sounds like an abnormal behavior, as I have one scene with >35k images and about 2M points, on my single CPU (16 threads), it finishes in about 5.5h. Can you try compiling it again to ensure it is in Release mode? Also, do you still have the log of your run? It should tell you how much time it spends on each step. Regarding to your questions on the skipping rotation averaging and global positioning, it is possible, but not well supported by the current command line interface. However, you can load data yourself into the data structure, and skip steps as desired. You can refer to this file as a start

sephyli commented 1 month ago

I check my build type in CMakeCache.txt, it seems already to be Release.
Here is the log.

 Loading Images 3128 / 3128
 Loading Image Pair 374007 / 374007
WARNING: Logging before InitGoogleLogging() is written to STDERR
I0730 19:39:47.195724 2735935 colmap_converter.cc:301] Pairs read done. 126921 / 374007 are invalid
I0730 19:39:47.233152 2735935 global_mapper.cc:75] Loaded database
-------------------------------------
Running preprocessing ...
-------------------------------------
I0730 19:39:47.401818 2735935 view_graph_manipulation.cc:244] Decompose relative pose for 0 pairs
I0730 19:39:47.401957 2735935 view_graph_manipulation.cc:294] Decompose relative pose done. 0 pairs are pure rotation
I0730 19:39:47.401966 2735935 timer.cc:87] Elapsed time: 0.16877 [seconds]
-------------------------------------
Running view graph calibration ...
-------------------------------------
I0730 19:39:47.401998 2735935 view_graph_calibration.cc:14] Start ViewGraphCalibrator
W0730 19:39:47.735778 2735935 preprocessor.cc:62] Specified options.num_threads: 16 exceeds maximum available from the threading model Ceres was compiled with: 10.  Bounding to maximum number available.
I0730 19:39:51.732638 2735935 view_graph_calibration.cc:155] 0 cameras are rejected in view graph calibration
I0730 19:39:51.845935 2735935 view_graph_calibration.cc:190] invalid / total number of two view geometry: 22422 / 477110
-------------------------------------
Running relative pose estimation ...
-------------------------------------
I0730 19:39:52.002002 2735935 image_undistorter.cc:17] Undistorting images..
I0730 19:39:55.865980 2735935 image_undistorter.cc:43] Image undistortion done
I0730 19:39:55.924628 2735935 relpose_estimation.cc:17] Estimating relative pose for 224664 pairs
 Estimating relative pose: 100%
I0730 22:42:12.401743 2735935 relpose_estimation.cc:68] Estimating relative pose done
I0730 22:42:15.341876 2735935 relpose_filter.cc:46] Filtered 58782 relative poses with inlier number < 30
I0730 22:42:15.374949 2735935 relpose_filter.cc:63] Filtered 1 relative poses with inlier ratio < 0.25
I0730 22:42:15.508324 2735935 timer.cc:87] Elapsed time: 10943.51168 [seconds]
-------------------------------------
Running rotation averaging ...
-------------------------------------
I0730 22:42:36.290331 2735935 relpose_filter.cc:31] Filtered 60224 relative rotation with angle > 10 degrees
I0730 22:42:41.494740 2735935 relpose_filter.cc:31] Filtered 577 relative rotation with angle > 10 degrees
I0730 22:42:41.633034 2735935 global_mapper.cc:95] 3128 / 3128 images are within the connected component.
I0730 22:42:41.633076 2735935 timer.cc:87] Elapsed time: 26.12470 [seconds]
-------------------------------------
Running track establishment ...
-------------------------------------
 Initializing pairs 374007 / 374007
 Establishing pairs 374007 / 374007
 Establishing tracks 1795425 / 1795425I0730 22:43:22.715252 2735935 track_establishment.cc:148] Discarded 26678 tracks due to inconsistency
I0730 22:43:29.131139 2735935 global_mapper.cc:115] Before filtering: 1795425, after filtering: 838221
I0730 22:43:29.131191 2735935 timer.cc:87] Elapsed time: 47.49066 [seconds]
-------------------------------------
Running global positioning ...
-------------------------------------
I0730 22:43:30.521596 2735935 image_undistorter.cc:17] Undistorting images..
I0730 22:43:31.509505 2735935 image_undistorter.cc:43] Image undistortion done
I0730 22:43:31.509567 2735935 global_positioning.cc:43] Setting up the global positioner problem
I0730 22:43:47.180464 2735935 global_positioning.cc:68] Solving the global positioner problem
W0730 22:43:47.674564 2735935 preprocessor.cc:62] Specified options.num_threads: 16 exceeds maximum available from the threading model Ceres was compiled with: 10.  Bounding to maximum number available.
I0730 23:57:08.880455 2735935 global_positioning.cc:77] Ceres Solver Report: Iterations: 72, Initial cost: 4.250212e+07, Final cost: 1.266453e+03, Termination: CONVERGENCE
I0730 23:57:09.582855 2735935 track_filter.cc:86] Filtered 106270 / 838221 tracks by angle error
I0730 23:57:09.582901 2735935 timer.cc:87] Elapsed time: 4419.06146 [seconds]
-------------------------------------
Running bundle adjustment ...
-------------------------------------
I0730 23:57:17.513415 2735935 global_mapper.cc:167] Bundle adjustment start
W0730 23:57:24.585985 2735935 preprocessor.cc:62] Specified options.num_threads: 16 exceeds maximum available from the threading model Ceres was compiled with: 10.  Bounding to maximum number available.
I0731 00:18:11.655805 2735935 bundle_adjustment.cc:47] Ceres Solver Report: Iterations: 54, Initial cost: 1.353828e+08, Final cost: 9.576590e+07, Termination: CONVERGENCE
I0731 00:18:11.655879 2735935 global_mapper.cc:183] Global bundle adjustment iteration 1 / 3, stage 1 finished (position only)
I0731 00:18:11.655884 2735935 timer.cc:87] Elapsed time: 1254.14245 [seconds]
W0731 00:18:20.495401 2735935 preprocessor.cc:62] Specified options.num_threads: 16 exceeds maximum available from the threading model Ceres was compiled with: 10.  Bounding to maximum number available.
I0731 02:46:20.438001 2735935 bundle_adjustment.cc:47] Ceres Solver Report: Iterations: 49, Initial cost: 9.576590e+07, Final cost: 8.745723e+07, Termination: CONVERGENCE
I0731 02:46:20.438059 2735935 global_mapper.cc:195] Global bundle adjustment iteration 1 / 3, stage 2 finished
I0731 02:46:20.438062 2735935 timer.cc:87] Elapsed time: 10142.92463 [seconds]
I0731 02:46:20.438241 2735935 image_undistorter.cc:17] Undistorting images..
I0731 02:46:24.868148 2735935 image_undistorter.cc:43] Image undistortion done
I0731 02:46:24.868186 2735935 global_mapper.cc:206] Filtering tracks by reprojection ...
I0731 02:46:25.473134 2735935 track_filter.cc:48] Filtered 95320 / 838221 tracks by reprojection error
W0731 02:46:34.339233 2735935 preprocessor.cc:62] Specified options.num_threads: 16 exceeds maximum available from the threading model Ceres was compiled with: 10.  Bounding to maximum number available.
I0731 03:15:48.874449 2735935 bundle_adjustment.cc:47] Ceres Solver Report: Iterations: 107, Initial cost: 6.738130e+07, Final cost: 6.080566e+07, Termination: CONVERGENCE
I0731 03:15:48.874502 2735935 global_mapper.cc:183] Global bundle adjustment iteration 2 / 3, stage 1 finished (position only)
I0731 03:15:48.874506 2735935 timer.cc:87] Elapsed time: 11911.36107 [seconds]
W0731 03:15:57.690181 2735935 preprocessor.cc:62] Specified options.num_threads: 16 exceeds maximum available from the threading model Ceres was compiled with: 10.  Bounding to maximum number available.
I0731 11:09:07.279567 2735935 bundle_adjustment.cc:47] Ceres Solver Report: Iterations: 192, Initial cost: 6.080566e+07, Final cost: 4.833117e+07, Termination: CONVERGENCE
I0731 11:09:07.279621 2735935 global_mapper.cc:195] Global bundle adjustment iteration 2 / 3, stage 2 finished
I0731 11:09:07.279624 2735935 timer.cc:87] Elapsed time: 40309.76619 [seconds]
I0731 11:09:07.279810 2735935 image_undistorter.cc:17] Undistorting images..
I0731 11:09:11.760955 2735935 image_undistorter.cc:43] Image undistortion done
I0731 11:09:11.760996 2735935 global_mapper.cc:206] Filtering tracks by reprojection ...
I0731 11:09:12.356626 2735935 track_filter.cc:48] Filtered 123743 / 838221 tracks by reprojection error
W0731 11:09:20.831864 2735935 preprocessor.cc:62] Specified options.num_threads: 16 exceeds maximum available from the threading model Ceres was compiled with: 10.  Bounding to maximum number available.
W0731 11:19:59.172716 2735935 levenberg_marquardt_strategy.cc:115] Linear solver failure. Failed to compute a step: CHOLMOD warning: Matrix not positive definite.
W0731 11:20:11.886597 2735935 levenberg_marquardt_strategy.cc:115] Linear solver failure. Failed to compute a step: CHOLMOD warning: Matrix not positive definite.
I0731 11:22:15.725402 2735935 bundle_adjustment.cc:47] Ceres Solver Report: Iterations: 52, Initial cost: 2.993109e+07, Final cost: 2.776875e+07, Termination: CONVERGENCE
I0731 11:22:15.725463 2735935 global_mapper.cc:183] Global bundle adjustment iteration 3 / 3, stage 1 finished (position only)
I0731 11:22:15.725466 2735935 timer.cc:87] Elapsed time: 41098.21203 [seconds]
W0731 11:22:24.007905 2735935 preprocessor.cc:62] Specified options.num_threads: 16 exceeds maximum available from the threading model Ceres was compiled with: 10.  Bounding to maximum number available.
I0731 17:32:43.736562 2735935 bundle_adjustment.cc:47] Ceres Solver Report: Iterations: 170, Initial cost: 2.776875e+07, Final cost: 2.349477e+07, Termination: CONVERGENCE
I0731 17:32:43.736613 2735935 global_mapper.cc:195] Global bundle adjustment iteration 3 / 3, stage 2 finished
I0731 17:32:43.736778 2735935 image_undistorter.cc:17] Undistorting images..
I0731 17:32:48.211515 2735935 image_undistorter.cc:43] Image undistortion done
I0731 17:32:48.211566 2735935 global_mapper.cc:206] Filtering tracks by reprojection ...
I0731 17:32:48.773917 2735935 track_filter.cc:48] Filtered 129894 / 838221 tracks by reprojection error
I0731 17:32:51.640856 2735935 image_undistorter.cc:17] Undistorting images..
I0731 17:32:56.144773 2735935 image_undistorter.cc:43] Image undistortion done
I0731 17:32:56.144816 2735935 global_mapper.cc:232] Filtering tracks by reprojection ...
I0731 17:32:56.678895 2735935 track_filter.cc:48] Filtered 0 / 838221 tracks by reprojection error
I0731 17:32:56.911772 2735935 track_filter.cc:123] Filtered 218395 / 838221 tracks by too small triangulation angle
I0731 17:32:56.911803 2735935 timer.cc:87] Elapsed time: 63339.39837 [seconds]
-------------------------------------
Running retriangulation ...
-------------------------------------
I0731 17:32:56.911841 2735935 database_cache.cc:65] Loading cameras...
I0731 17:32:56.913597 2735935 database_cache.cc:75]  8 in 0.002s
I0731 17:32:56.913625 2735935 database_cache.cc:83] Loading matches...
I0731 17:33:06.999504 2735935 database_cache.cc:89]  247654 in 10.086s
I0731 17:33:06.999559 2735935 database_cache.cc:105] Loading images...
I0731 17:33:18.476226 2735935 database_cache.cc:155]  3128 in 11.477s (connected 3128)
I0731 17:33:18.476797 2735935 database_cache.cc:166] Building correspondence graph...
I0731 17:33:30.044433 2735935 database_cache.cc:195]  in 11.568s (ignored 0)
 Triangulating image 3128 / 3128
 Global bundle adjustment iteration 5 / 5
I0731 17:46:38.394500 2735935 timer.cc:87] Elapsed time: 821.48268 [seconds]
-------------------------------------
Running bundle adjustment ...
-------------------------------------
I0731 17:46:38.394565 2735935 global_mapper.cc:263] Bundle adjustment start
W0731 17:46:45.286201 2735935 preprocessor.cc:62] Specified options.num_threads: 16 exceeds maximum available from the threading model Ceres was compiled with: 10.  Bounding to maximum number available.
^A1W0731 18:49:57.956492 2735935 levenberg_marquardt_strategy.cc:115] Linear solver failure. Failed to compute a step: CHOLMOD warning: Matrix not positive definite.
I0731 18:51:58.093842 2735935 bundle_adjustment.cc:47] Ceres Solver Report: Iterations: 92, Initial cost: 4.322504e+06, Final cost: 2.453510e+06, Termination: CONVERGENCE
I0731 18:51:58.098277 2735935 image_undistorter.cc:17] Undistorting images..
I0731 18:52:02.728241 2735935 image_undistorter.cc:43] Image undistortion done
I0731 18:52:02.728283 2735935 global_mapper.cc:271] Filtering tracks by reprojection ...
I0731 18:52:03.434981 2735935 track_filter.cc:48] Filtered 147449 / 762079 tracks by reprojection error
W0731 18:52:14.054122 2735935 preprocessor.cc:62] Specified options.num_threads: 16 exceeds maximum available from the threading model Ceres was compiled with: 10.  Bounding to maximum number available.
I0731 19:24:42.535974 2735935 bundle_adjustment.cc:47] Ceres Solver Report: Iterations: 45, Initial cost: 2.247241e+06, Final cost: 2.208386e+06, Termination: CONVERGENCE
I0731 19:24:42.536026 2735935 timer.cc:87] Elapsed time: 6705.62419 [seconds]
I0731 19:24:46.222750 2735935 image_undistorter.cc:17] Undistorting images..
I0731 19:24:50.825677 2735935 image_undistorter.cc:43] Image undistortion done
I0731 19:24:50.825722 2735935 global_mapper.cc:286] Filtering tracks by reprojection ...
I0731 19:24:51.692404 2735935 track_filter.cc:48] Filtered 5239 / 762079 tracks by reprojection error
I0731 19:24:52.100497 2735935 track_filter.cc:123] Filtered 155803 / 762079 tracks by too small triangulation angle
I0731 19:24:52.100540 2735935 global_mapper.cc:81] Reconstruction done in 85504.9 seconds
I0731 19:24:53.152590 2735935 colmap_io.cc:27] Extracting colors ...
I0731 19:25:38.261420 2735935 global_mapper.cc:86] Export to COLMAP reconstruction done

yuancaimaiyi commented 1 month ago

@sephyli First of all, the first question: I think it is normal. The complexity of BA is (6N+3n)^3. Because your data volume is not small, BA takes a long time. The second question: You have a priori pose. If your pose is accurate, your problem is to build 3D based on the known pose, which only requires triangulation. However, your requirement is to optimize the pose, so you must perform a complete In the sfm process, since the position (C) in the pose (R|C) obtained by slam is relatively accurate, you can use the position to fuse SfM. This is called GPS-aided aerial triangulation in the photogrammetry . You You can use my improved colmap (fusion gps) https://github.com/yuancaimaiyi/colmap-fusion-gps/tree/fusion-gps . In addition, everyone knows that both glomap and colmap are relatively slow to process large scenes. At this time You need to do hierarchical sfm, as shown in the figure below: V1 is my vismap version (improved colmap) but without hierarchical. V2 is hierarchical-vismap, which is about 20 times faster than without hierarchical. I believe you can do it too!

lpanaf commented 1 month ago

It seems that relative pose estimation is taking quite a long time to finish, maybe you did not enable openmp? This should save you a lot of time. The run time of global positioning seems to be good. Also, one step of the global BA is taking very long to finish, maybe you can try to lower the allowed number of iterations by changing --BundleAdjustment.max_num_iterations to 100 (with caution, as this can lead to performance degradation). Also, you can get the most updated version of GLOMAP, there, we expose more options for glomap mapper, and you can try to decrease --TrackEstablishment.max_num_tracks, for example, to 1000 * n. Also, we just released a simple tutorial on improving your reconstruction at here. You can also check it out :)

sephyli commented 1 month ago

Thanks for your great work! I will surely have a try.

colmap / glomap

How to reduce the running time of global ba when there are some many tracks? #10