commit 9123e2f624a218f84835717ab5300f879d77f1f0
author Sameer Agarwal <sameeragarwal@google.com> Tue Sep 18 21:49:06 2012 -0700
committer Sameer Agarwal <sameeragarwal@google.com> Tue Sep 25 11:13:39 2012 -0700
tree f22fd987812211492a1736824b7cd7bf0c4129c9
parent b23fd4e6675fc76761a63bf76e80696a5a69dd35

An implementation of Ruhe & Wedin's Algorithm II.

A non-linear generalization of Ruhe & Wedin's algorithm
for separable non-linear least squares problem. It is implemented
as coordinate descent on an independent subset of the parameter
blocks at the end of every successful Newton step. The resulting
algorithm has much improved convergence at the cost of some
execution time.

Change-Id: I8fdc5edbd0ba1e702c9658b98041b2c2ae705402

examples/bundle_adjuster.cc

diff --git a/examples/bundle_adjuster.cc b/examples/bundle_adjuster.cc
index 6cd8c6a..bd405e4 100644
--- a/examples/bundle_adjuster.cc
+++ b/examples/bundle_adjuster.cc
@@ -68,6 +68,15 @@
 DEFINE_string(input, "", "Input File name");
 DEFINE_string(trust_region_strategy, "levenberg_marquardt",
               "Options are: levenberg_marquardt, dogleg.");
+DEFINE_string(dogleg, "traditional_dogleg", "Options are: traditional_dogleg,"
+              "subspace_dogleg.");
+
+DEFINE_bool(inner_iterations, false, "Use inner iterations to non-linearly "
+            "refine each successful trust region step.");
+
+DEFINE_string(blocks_for_inner_iterations, "cameras", "Options are: "
+            "automatic, cameras, points");
+
 DEFINE_string(linear_solver, "sparse_schur", "Options are: "
               "sparse_schur, dense_schur, iterative_schur, sparse_normal_cholesky, "
               "dense_qr, dense_normal_cholesky and cgnr.");
@@ -77,8 +86,6 @@
 DEFINE_string(sparse_linear_algebra_library, "suite_sparse",
               "Options are: suite_sparse and cx_sparse.");
 DEFINE_string(ordering, "automatic", "Options are: automatic, user.");
-DEFINE_string(dogleg, "traditional_dogleg", "Options are: traditional_dogleg,"
-              "subspace_dogleg.");
 
 DEFINE_bool(use_quaternions, false, "If true, uses quaternions to represent "
             "rotations. If false, angle axis is used.");
@@ -125,8 +132,35 @@
 }
 
 void SetOrdering(BALProblem* bal_problem, Solver::Options* options) {
+  const int num_points = bal_problem->num_points();
+  const int point_block_size = bal_problem->point_block_size();
+  double* points = bal_problem->mutable_points();
+
+  const int num_cameras = bal_problem->num_cameras();
+  const int camera_block_size = bal_problem->camera_block_size();
+  double* cameras = bal_problem->mutable_cameras();
+
   options->use_block_amd = FLAGS_use_block_amd;
 
+  if (options->use_inner_iterations) {
+    if (FLAGS_blocks_for_inner_iterations == "cameras") {
+      LOG(INFO) << "Camera blocks for inner iterations";
+      for (int i = 0; i < num_cameras; ++i) {
+        options->parameter_blocks_for_inner_iterations.push_back(cameras + camera_block_size * i);
+      }
+    } else if (FLAGS_blocks_for_inner_iterations == "points") {
+      LOG(INFO) << "Point blocks for inner iterations";
+      for (int i = 0; i < num_points; ++i) {
+        options->parameter_blocks_for_inner_iterations.push_back(points + point_block_size * i);
+      }
+    } else if (FLAGS_blocks_for_inner_iterations == "automatic") {
+      LOG(INFO) << "Choosing automatic blocks for inner iterations";
+    } else {
+      LOG(FATAL) << "Unknown block type for inner iterations: "
+                 << FLAGS_blocks_for_inner_iterations;
+    }
+  }
+
   // Bundle adjustment problems have a sparsity structure that makes
   // them amenable to more specialized and much more efficient
   // solution strategies. The SPARSE_SCHUR, DENSE_SCHUR and
@@ -142,13 +176,6 @@
     return;
   }
 
-  const int num_points = bal_problem->num_points();
-  const int point_block_size = bal_problem->point_block_size();
-  double* points = bal_problem->mutable_points();
-  const int num_cameras = bal_problem->num_cameras();
-  const int camera_block_size = bal_problem->camera_block_size();
-  double* cameras = bal_problem->mutable_cameras();
-
   ceres::Ordering* ordering = new ceres::Ordering;
 
   // The points come before the cameras.
@@ -181,6 +208,7 @@
   CHECK(StringToTrustRegionStrategyType(FLAGS_trust_region_strategy,
                                         &options->trust_region_strategy_type));
   CHECK(StringToDoglegType(FLAGS_dogleg, &options->dogleg_type));
+  options->use_inner_iterations = FLAGS_inner_iterations;
 }
 
 void SetSolverOptionsFromFlags(BALProblem* bal_problem,
@@ -267,8 +295,8 @@
   Solver::Options options;
   SetSolverOptionsFromFlags(&bal_problem, &options);
   options.solver_log = FLAGS_solver_log;
-  options.gradient_tolerance = 1e-12;
-  options.function_tolerance = 1e-12;
+  options.gradient_tolerance = 1e-16;
+  options.function_tolerance = 1e-16;
   Solver::Summary summary;
   Solve(options, &problem, &summary);
   std::cout << summary.FullReport() << "\n";