blob: 38c958fe34a6aa9dd24755f12bfd8f01e8a7d060 [file] [log] [blame]
// Ceres Solver - A fast non-linear least squares minimizer
// Copyright 2015 Google Inc. All rights reserved.
// http://ceres-solver.org/
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// * Redistributions of source code must retain the above copyright notice,
// this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above copyright notice,
// this list of conditions and the following disclaimer in the documentation
// and/or other materials provided with the distribution.
// * Neither the name of Google Inc. nor the names of its contributors may be
// used to endorse or promote products derived from this software without
// specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.
//
// Author: keir@google.com (Keir Mierle)
#ifndef CERES_INTERNAL_PROGRAM_H_
#define CERES_INTERNAL_PROGRAM_H_
#include <set>
#include <string>
#include <vector>
#include "ceres/internal/port.h"
namespace ceres {
namespace internal {
class ParameterBlock;
class ProblemImpl;
class ResidualBlock;
class TripletSparseMatrix;
// A nonlinear least squares optimization problem. This is different from the
// similarly-named "Problem" object, which offers a mutation interface for
// adding and modifying parameters and residuals. The Program contains the core
// part of the Problem, which is the parameters and the residuals, stored in a
// particular ordering. The ordering is critical, since it defines the mapping
// between (residual, parameter) pairs and a position in the jacobian of the
// objective function. Various parts of Ceres transform one Program into
// another; for example, the first stage of solving involves stripping all
// constant parameters and residuals. This is in contrast with Problem, which is
// not built for transformation.
class Program {
public:
Program();
explicit Program(const Program& program);
// The ordered parameter and residual blocks for the program.
const std::vector<ParameterBlock*>& parameter_blocks() const;
const std::vector<ResidualBlock*>& residual_blocks() const;
std::vector<ParameterBlock*>* mutable_parameter_blocks();
std::vector<ResidualBlock*>* mutable_residual_blocks();
// Serialize to/from the program and update states.
//
// NOTE: Setting the state of a parameter block can trigger the
// computation of the Jacobian of its local parameterization. If
// this computation fails for some reason, then this method returns
// false and the state of the parameter blocks cannot be trusted.
bool StateVectorToParameterBlocks(const double *state);
void ParameterBlocksToStateVector(double *state) const;
// Copy internal state to the user's parameters.
void CopyParameterBlockStateToUserState();
// Set the parameter block pointers to the user pointers. Since this
// runs parameter block set state internally, which may call local
// parameterizations, this can fail. False is returned on failure.
bool SetParameterBlockStatePtrsToUserStatePtrs();
// Update a state vector for the program given a delta.
bool Plus(const double* state,
const double* delta,
double* state_plus_delta) const;
// Set the parameter indices and offsets. This permits mapping backward
// from a ParameterBlock* to an index in the parameter_blocks() vector. For
// any parameter block p, after calling SetParameterOffsetsAndIndex(), it
// is true that
//
// parameter_blocks()[p->index()] == p
//
// If a parameter appears in a residual but not in the parameter block, then
// it will have an index of -1.
//
// This also updates p->state_offset() and p->delta_offset(), which are the
// position of the parameter in the state and delta vector respectively.
void SetParameterOffsetsAndIndex();
// Check if the internal state of the program (the indexing and the
// offsets) are correct.
bool IsValid() const;
bool ParameterBlocksAreFinite(std::string* message) const;
// Returns true if the program has any non-constant parameter blocks
// which have non-trivial bounds constraints.
bool IsBoundsConstrained() const;
// Returns false, if the program has any constant parameter blocks
// which are not feasible, or any variable parameter blocks which
// have a lower bound greater than or equal to the upper bound.
bool IsFeasible(std::string* message) const;
// Loop over each residual block and ensure that no two parameter
// blocks in the same residual block are part of
// parameter_blocks as that would violate the assumption that it
// is an independent set in the Hessian matrix.
bool IsParameterBlockSetIndependent(
const std::set<double*>& independent_set) const;
// Create a TripletSparseMatrix which contains the zero-one
// structure corresponding to the block sparsity of the transpose of
// the Jacobian matrix.
//
// Caller owns the result.
TripletSparseMatrix* CreateJacobianBlockSparsityTranspose() const;
// Create a copy of this program and removes constant parameter
// blocks and residual blocks with no varying parameter blocks while
// preserving their relative order.
//
// removed_parameter_blocks on exit will contain the list of
// parameter blocks that were removed.
//
// fixed_cost will be equal to the sum of the costs of the residual
// blocks that were removed.
//
// If there was a problem, then the function will return a NULL
// pointer and error will contain a human readable description of
// the problem.
Program* CreateReducedProgram(std::vector<double*>* removed_parameter_blocks,
double* fixed_cost,
std::string* error) const;
// See problem.h for what these do.
int NumParameterBlocks() const;
int NumParameters() const;
int NumEffectiveParameters() const;
int NumResidualBlocks() const;
int NumResiduals() const;
int MaxScratchDoublesNeededForEvaluate() const;
int MaxDerivativesPerResidualBlock() const;
int MaxParametersPerResidualBlock() const;
int MaxResidualsPerResidualBlock() const;
// A human-readable dump of the parameter blocks for debugging.
// TODO(keir): If necessary, also dump the residual blocks.
std::string ToString() const;
private:
// Remove constant parameter blocks and residual blocks with no
// varying parameter blocks while preserving their relative order.
//
// removed_parameter_blocks on exit will contain the list of
// parameter blocks that were removed.
//
// fixed_cost will be equal to the sum of the costs of the residual
// blocks that were removed.
//
// If there was a problem, then the function will return false and
// error will contain a human readable description of the problem.
bool RemoveFixedBlocks(std::vector<double*>* removed_parameter_blocks,
double* fixed_cost,
std::string* message);
// The Program does not own the ParameterBlock or ResidualBlock objects.
std::vector<ParameterBlock*> parameter_blocks_;
std::vector<ResidualBlock*> residual_blocks_;
friend class ProblemImpl;
};
} // namespace internal
} // namespace ceres
#endif // CERES_INTERNAL_PROGRAM_H_