Home | History | Annotate | Download | only in ceres 
      1 // Ceres Solver - A fast non-linear least squares minimizer
      2 // Copyright 2012 Google Inc. All rights reserved.
      3 // http://code.google.com/p/ceres-solver/
      4 //
      5 // Redistribution and use in source and binary forms, with or without
      6 // modification, are permitted provided that the following conditions are met:
      7 //
      8 // * Redistributions of source code must retain the above copyright notice,
      9 //   this list of conditions and the following disclaimer.
     10 // * Redistributions in binary form must reproduce the above copyright notice,
     11 //   this list of conditions and the following disclaimer in the documentation
     12 //   and/or other materials provided with the distribution.
     13 // * Neither the name of Google Inc. nor the names of its contributors may be
     14 //   used to endorse or promote products derived from this software without
     15 //   specific prior written permission.
     16 //
     17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
     18 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     19 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     20 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
     21 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
     22 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
     23 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
     24 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
     25 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
     26 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
     27 // POSSIBILITY OF SUCH DAMAGE.
     28 //
     29 // Author: sameeragarwal (at) google.com (Sameer Agarwal)
     30 
     31 #ifndef CERES_INTERNAL_COORDINATE_DESCENT_MINIMIZER_H_
     32 #define CERES_INTERNAL_COORDINATE_DESCENT_MINIMIZER_H_
     33 
     34 #include <string>
     35 #include <vector>
     36 
     37 #include "ceres/evaluator.h"
     38 #include "ceres/minimizer.h"
     39 #include "ceres/problem_impl.h"
     40 #include "ceres/solver.h"
     41 
     42 namespace ceres {
     43 namespace internal {
     44 
     45 class Program;
     46 
     47 // Given a Program, and a ParameterBlockOrdering which partitions
     48 // (non-exhaustively) the Hessian matrix into independent sets,
     49 // perform coordinate descent on the parameter blocks in the
     50 // ordering. The independent set structure allows for all parameter
     51 // blocks in the same independent set to be optimized in parallel, and
     52 // the order of the independent set determines the order in which the
     53 // parameter block groups are optimized.
     54 //
     55 // The minimizer assumes that none of the parameter blocks in the
     56 // program are constant.
     57 class CoordinateDescentMinimizer : public Minimizer {
     58  public:
     59   bool Init(const Program& program,
     60             const ProblemImpl::ParameterMap& parameter_map,
     61             const ParameterBlockOrdering& ordering,
     62             string* error);
     63 
     64   // Minimizer interface.
     65   virtual ~CoordinateDescentMinimizer();
     66   virtual void Minimize(const Minimizer::Options& options,
     67                         double* parameters,
     68                         Solver::Summary* summary);
     69 
     70   // Verify that each group in the ordering forms an independent set.
     71   static bool IsOrderingValid(const Program& program,
     72                               const ParameterBlockOrdering& ordering,
     73                               string* message);
     74 
     75   // Find a recursive decomposition of the Hessian matrix as a set
     76   // of independent sets of decreasing size and invert it. This
     77   // seems to work better in practice, i.e., Cameras before
     78   // points.
     79   static ParameterBlockOrdering* CreateOrdering(const Program& program);
     80 
     81  private:
     82   void Solve(Program* program,
     83              LinearSolver* linear_solver,
     84              double* parameters,
     85              Solver::Summary* summary);
     86 
     87   vector<ParameterBlock*> parameter_blocks_;
     88   vector<vector<ResidualBlock*> > residual_blocks_;
     89   // The optimization is performed in rounds. In each round all the
     90   // parameter blocks that form one independent set are optimized in
     91   // parallel. This array, marks the boundaries of the independent
     92   // sets in parameter_blocks_.
     93   vector<int> independent_set_offsets_;
     94 
     95   Evaluator::Options evaluator_options_;
     96 };
     97 
     98 }  // namespace internal
     99 }  // namespace ceres
    100 
    101 #endif  // CERES_INTERNAL_COORDINATE_DESCENT_MINIMIZER_H_
    102