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/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(
