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;
diff --git a/include/ceres/types.h b/include/ceres/types.h
index ffa743a..c8c9cfe 100644
--- a/include/ceres/types.h
+++ b/include/ceres/types.h
@@ -102,21 +102,49 @@
// Block diagonal of the Gauss-Newton Hessian.
JACOBI,
+ // Note: The following three preconditioners can only be used with
+ // the ITERATIVE_SCHUR solver. They are well suited for Structure
+ // from Motion problems.
+
// Block diagonal of the Schur complement. This preconditioner may
// only be used with the ITERATIVE_SCHUR solver.
SCHUR_JACOBI,
// Visibility clustering based preconditioners.
//
- // These preconditioners are well suited for Structure from Motion
- // problems, particularly problems arising from community photo
- // collections. These preconditioners use the visibility structure
- // of the scene to determine the sparsity structure of the
- // preconditioner. Requires SuiteSparse/CHOLMOD.
+ // The following two preconditioners use the visibility structure of
+ // the scene to determine the sparsity structure of the
+ // preconditioner. This is done using a clustering algorithm. The
+ // available visibility clustering algorithms are described below.
+ //
+ // Note: Requires SuiteSparse.
CLUSTER_JACOBI,
CLUSTER_TRIDIAGONAL
};
+enum VisibilityClusteringType {
+ // Canonical views algorithm as described in
+ //
+ // "Scene Summarization for Online Image Collections", Ian Simon, Noah
+ // Snavely, Steven M. Seitz, ICCV 2007.
+ //
+ // This clustering algorithm can be quite slow, but gives high
+ // quality clusters. The original visibility based clustering paper
+ // used this algorithm.
+ CANONICAL_VIEWS,
+
+ // The classic single linkage algorithm. It is extremely fast as
+ // compared to CANONICAL_VIEWS, but can give slightly poor
+ // results. For problems with large number of cameras though, this
+ // is generally a pretty good option.
+ //
+ // If you are using SCHUR_JACOBI preconditioner and have SuiteSparse
+ // available, CLUSTER_JACOBI and CLUSTER_TRIDIAGONAL in combination
+ // with the SINGLE_LINKAGE algorithm will generally give better
+ // results.
+ SINGLE_LINKAGE
+};
+
enum SparseLinearAlgebraLibraryType {
// High performance sparse Cholesky factorization and approximate
// minimum degree ordering.
@@ -400,6 +428,10 @@
const char* PreconditionerTypeToString(PreconditionerType type);
bool StringToPreconditionerType(string value, PreconditionerType* type);
+const char* VisibilityClusteringTypeToString(VisibilityClusteringType type);
+bool StringToVisibilityClusteringType(string value,
+ VisibilityClusteringType* type);
+
const char* SparseLinearAlgebraLibraryTypeToString(
SparseLinearAlgebraLibraryType type);
bool StringToSparseLinearAlgebraLibraryType(
