Merged
Merged
Conversation
This PR includes faster covariance computation for small blocks, as a follow up for #2610. This is achieved by storing the inversion of the triangular matrix L from sparse Cholesky rather than storing the full covariance matrix.
This brings ~5x constant speed up on the computation of per-image pose covariance while the asymptotic complexity is still cubic (as in the table below, the sparse cholesky operation is already cubic).
Below are some benchmark timing results for per-pose covariance estimation. Control points were used to fix the Gauge ambiguity.
| # images | # pose parameters | sparse cholesky (in both methods) | full time before from #2610 | full time in this PR |
|---|---|---|---|---|
| 400 | 2400 | 1.9s | 13.3s | 3.8s |
| 600 | 3600 | 6.9s | 52.9s | 13.4s |
| 800 | 4800 | 16.9s | 147.8s | 31.9s |
| 1200 | 7200 | 56.6s | 487.4s | 105.7s |
| 1800 | 10800 | 189.1s | 1644.7s | 374.6s |
The asymptotic complexity is O(n^3) with a very stable constant so one can estimate the time needed for larger reconstruction using the numbers from this table. The time may vary a bit depending on the level of connection (shared 3D points across images) in the reconstruction. Same unit tests from #2610 were done here to verify the correctness.
To be able to use this feature in Python one just needs to substitute estimator.compute() into estimator.factorize() for the colmap estimator pycolmap.BundleAdjustmentCovarianceEstimator. Note that the method Compute() is still preferred if one wants the full covariance matrix (n_parameters by n_parameters ).
Labels
None yet