Add support for multiple visibility clustering algorithms.
The original visibility based preconditioning paper and
implementation only used the canonical views algorithm.
This algorithm for large dense graphs can be particularly
expensive. As its worst case complexity is cubic in size
of the graph.
Further, for many uses the SCHUR_JACOBI preconditioner
was both effective enough while being cheap. It however
suffers from a fatal flaw. If the camera parameter blocks
are split between two or more parameter blocks, e.g,
extrinsics and intrinsics. The preconditioner because
it is block diagonal will not capture the interactions
between them.
Using CLUSTER_JACOBI or CLUSTER_TRIDIAGONAL will fix
this problem but as mentioned above this can be quite
expensive depending on the problem.
This change extends the visibility based preconditioner
to allow for multiple clustering algorithms. And adds
a simple thresholded single linkage clustering algorithm
which allows you to construct versions of CLUSTER_JACOBI
and CLUSTER_TRIDIAGONAL preconditioners that are cheap
to construct and are more effective than SCHUR_JACOBI.
Currently the constants controlling the threshold above
which edges are considered in the single linkage algorithm
are not exposed. This would be done in a future change.
Change-Id: I7ddc36790943f24b19c7f08b10694ae9a822f5c9
diff --git a/include/ceres/solver.h b/include/ceres/solver.h
index 0b3a18e..7d8e4e2 100644
--- a/include/ceres/solver.h
+++ b/include/ceres/solver.h
@@ -98,7 +98,7 @@
#endif
preconditioner_type = JACOBI;
-
+ visibility_clustering_type = CANONICAL_VIEWS;
dense_linear_algebra_library_type = EIGEN;
sparse_linear_algebra_library_type = SUITE_SPARSE;
#if defined(CERES_NO_SUITESPARSE) && !defined(CERES_NO_CXSPARSE)
@@ -385,6 +385,11 @@
// Type of preconditioner to use with the iterative linear solvers.
PreconditionerType preconditioner_type;
+ // Type of clustering algorithm to use visibility based
+ // preconditioning. This option is used only when the
+ // preconditioner_type is CLUSTER_JACOBI or CLUSTER_TRIDIAGONAL.
+ VisibilityClusteringType visibility_clustering_type;
+
// Ceres supports using multiple dense linear algebra libraries
// for dense matrix factorizations. Currently EIGEN and LAPACK are
// the valid choices. EIGEN is always available, LAPACK refers to
@@ -886,6 +891,11 @@
// step. Only meaningful when an iterative linear solver is used.
PreconditionerType preconditioner_type;
+ // Type of clustering algorithm used for visibility based
+ // preconditioning. Only meaningful when the preconditioner_type
+ // is CLUSTER_JACOBI or CLUSTER_TRIDIAGONAL.
+ VisibilityClusteringType visibility_clustering_type;
+
// Type of trust region strategy.
TrustRegionStrategyType trust_region_strategy_type;
