| // Ceres Solver - A fast non-linear least squares minimizer |
| // Copyright 2010, 2011, 2012 Google Inc. All rights reserved. |
| // http://code.google.com/p/ceres-solver/ |
| // |
| // 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) |
| |
| #include "ceres/gradient_checking_cost_function.h" |
| |
| #include <algorithm> |
| #include <cmath> |
| #include <numeric> |
| #include <string> |
| #include <vector> |
| |
| #include "ceres/cost_function.h" |
| #include "ceres/internal/eigen.h" |
| #include "ceres/internal/scoped_ptr.h" |
| #include "ceres/parameter_block.h" |
| #include "ceres/problem.h" |
| #include "ceres/problem_impl.h" |
| #include "ceres/program.h" |
| #include "ceres/residual_block.h" |
| #include "ceres/dynamic_numeric_diff_cost_function.h" |
| #include "ceres/stringprintf.h" |
| #include "ceres/types.h" |
| #include "glog/logging.h" |
| |
| namespace ceres { |
| namespace internal { |
| |
| using std::abs; |
| using std::max; |
| using std::string; |
| using std::vector; |
| |
| namespace { |
| |
| // True if x and y have an absolute relative difference less than |
| // relative_precision and false otherwise. Stores the relative and absolute |
| // difference in relative/absolute_error if non-NULL. |
| bool IsClose(double x, double y, double relative_precision, |
| double *relative_error, |
| double *absolute_error) { |
| double local_absolute_error; |
| double local_relative_error; |
| if (!absolute_error) { |
| absolute_error = &local_absolute_error; |
| } |
| if (!relative_error) { |
| relative_error = &local_relative_error; |
| } |
| *absolute_error = abs(x - y); |
| *relative_error = *absolute_error / max(abs(x), abs(y)); |
| if (x == 0 || y == 0) { |
| // If x or y is exactly zero, then relative difference doesn't have any |
| // meaning. Take the absolute difference instead. |
| *relative_error = *absolute_error; |
| } |
| return abs(*relative_error) < abs(relative_precision); |
| } |
| |
| class GradientCheckingCostFunction : public CostFunction { |
| public: |
| GradientCheckingCostFunction(const CostFunction* function, |
| double relative_step_size, |
| double relative_precision, |
| const string& extra_info) |
| : function_(function), |
| relative_precision_(relative_precision), |
| extra_info_(extra_info) { |
| DynamicNumericDiffCostFunction<CostFunction, CENTRAL>* |
| finite_diff_cost_function = |
| new DynamicNumericDiffCostFunction<CostFunction, CENTRAL>( |
| function, |
| DO_NOT_TAKE_OWNERSHIP, |
| relative_step_size); |
| |
| const vector<int32>& parameter_block_sizes = |
| function->parameter_block_sizes(); |
| for (int i = 0; i < parameter_block_sizes.size(); ++i) { |
| finite_diff_cost_function->AddParameterBlock(parameter_block_sizes[i]); |
| } |
| *mutable_parameter_block_sizes() = parameter_block_sizes; |
| set_num_residuals(function->num_residuals()); |
| finite_diff_cost_function->SetNumResiduals(num_residuals()); |
| finite_diff_cost_function_.reset(finite_diff_cost_function); |
| } |
| |
| virtual ~GradientCheckingCostFunction() { } |
| |
| virtual bool Evaluate(double const* const* parameters, |
| double* residuals, |
| double** jacobians) const { |
| if (!jacobians) { |
| // Nothing to check in this case; just forward. |
| return function_->Evaluate(parameters, residuals, NULL); |
| } |
| |
| int num_residuals = function_->num_residuals(); |
| |
| // Make space for the jacobians of the two methods. |
| const vector<int32>& block_sizes = function_->parameter_block_sizes(); |
| vector<Matrix> term_jacobians(block_sizes.size()); |
| vector<Matrix> finite_difference_jacobians(block_sizes.size()); |
| vector<double*> term_jacobian_pointers(block_sizes.size()); |
| vector<double*> finite_difference_jacobian_pointers(block_sizes.size()); |
| for (int i = 0; i < block_sizes.size(); i++) { |
| term_jacobians[i].resize(num_residuals, block_sizes[i]); |
| term_jacobian_pointers[i] = term_jacobians[i].data(); |
| finite_difference_jacobians[i].resize(num_residuals, block_sizes[i]); |
| finite_difference_jacobian_pointers[i] = |
| finite_difference_jacobians[i].data(); |
| } |
| |
| // Evaluate the derivative using the user supplied code. |
| if (!function_->Evaluate(parameters, |
| residuals, |
| &term_jacobian_pointers[0])) { |
| LOG(WARNING) << "Function evaluation failed."; |
| return false; |
| } |
| |
| // Evaluate the derivative using numeric derivatives. |
| finite_diff_cost_function_->Evaluate( |
| parameters, |
| residuals, |
| &finite_difference_jacobian_pointers[0]); |
| |
| // See if any elements have relative error larger than the threshold. |
| int num_bad_jacobian_components = 0; |
| double worst_relative_error = 0; |
| |
| // Accumulate the error message for all the jacobians, since it won't get |
| // output if there are no bad jacobian components. |
| string m; |
| for (int k = 0; k < block_sizes.size(); k++) { |
| // Copy the original jacobian blocks into the jacobians array. |
| if (jacobians[k] != NULL) { |
| MatrixRef(jacobians[k], |
| term_jacobians[k].rows(), |
| term_jacobians[k].cols()) = term_jacobians[k]; |
| } |
| |
| StringAppendF(&m, |
| "========== " |
| "Jacobian for " "block %d: (%ld by %ld)) " |
| "==========\n", |
| k, |
| static_cast<long>(term_jacobians[k].rows()), |
| static_cast<long>(term_jacobians[k].cols())); |
| // The funny spacing creates appropriately aligned column headers. |
| m += " block row col user dx/dy num diff dx/dy " |
| "abs error relative error parameter residual\n"; |
| |
| for (int i = 0; i < term_jacobians[k].rows(); i++) { |
| for (int j = 0; j < term_jacobians[k].cols(); j++) { |
| double term_jacobian = term_jacobians[k](i, j); |
| double finite_jacobian = finite_difference_jacobians[k](i, j); |
| double relative_error, absolute_error; |
| bool bad_jacobian_entry = |
| !IsClose(term_jacobian, |
| finite_jacobian, |
| relative_precision_, |
| &relative_error, |
| &absolute_error); |
| worst_relative_error = max(worst_relative_error, relative_error); |
| |
| StringAppendF(&m, "%6d %4d %4d %17g %17g %17g %17g %17g %17g", |
| k, i, j, |
| term_jacobian, finite_jacobian, |
| absolute_error, relative_error, |
| parameters[k][j], |
| residuals[i]); |
| |
| if (bad_jacobian_entry) { |
| num_bad_jacobian_components++; |
| StringAppendF( |
| &m, " ------ (%d,%d,%d) Relative error worse than %g", |
| k, i, j, relative_precision_); |
| } |
| m += "\n"; |
| } |
| } |
| } |
| |
| // Since there were some bad errors, dump comprehensive debug info. |
| if (num_bad_jacobian_components) { |
| string header = StringPrintf("Detected %d bad jacobian component(s). " |
| "Worst relative error was %g.\n", |
| num_bad_jacobian_components, |
| worst_relative_error); |
| if (!extra_info_.empty()) { |
| header += "Extra info for this residual: " + extra_info_ + "\n"; |
| } |
| LOG(WARNING) << "\n" << header << m; |
| } |
| return true; |
| } |
| |
| private: |
| const CostFunction* function_; |
| internal::scoped_ptr<CostFunction> finite_diff_cost_function_; |
| double relative_precision_; |
| string extra_info_; |
| }; |
| |
| } // namespace |
| |
| CostFunction *CreateGradientCheckingCostFunction( |
| const CostFunction *cost_function, |
| double relative_step_size, |
| double relative_precision, |
| const string& extra_info) { |
| return new GradientCheckingCostFunction(cost_function, |
| relative_step_size, |
| relative_precision, |
| extra_info); |
| } |
| |
| ProblemImpl* CreateGradientCheckingProblemImpl(ProblemImpl* problem_impl, |
| double relative_step_size, |
| double relative_precision) { |
| // We create new CostFunctions by wrapping the original CostFunction |
| // in a gradient checking CostFunction. So its okay for the |
| // ProblemImpl to take ownership of it and destroy it. The |
| // LossFunctions and LocalParameterizations are reused and since |
| // they are owned by problem_impl, gradient_checking_problem_impl |
| // should not take ownership of it. |
| Problem::Options gradient_checking_problem_options; |
| gradient_checking_problem_options.cost_function_ownership = TAKE_OWNERSHIP; |
| gradient_checking_problem_options.loss_function_ownership = |
| DO_NOT_TAKE_OWNERSHIP; |
| gradient_checking_problem_options.local_parameterization_ownership = |
| DO_NOT_TAKE_OWNERSHIP; |
| |
| ProblemImpl* gradient_checking_problem_impl = new ProblemImpl( |
| gradient_checking_problem_options); |
| |
| Program* program = problem_impl->mutable_program(); |
| |
| // For every ParameterBlock in problem_impl, create a new parameter |
| // block with the same local parameterization and constancy. |
| const vector<ParameterBlock*>& parameter_blocks = program->parameter_blocks(); |
| for (int i = 0; i < parameter_blocks.size(); ++i) { |
| ParameterBlock* parameter_block = parameter_blocks[i]; |
| gradient_checking_problem_impl->AddParameterBlock( |
| parameter_block->mutable_user_state(), |
| parameter_block->Size(), |
| parameter_block->mutable_local_parameterization()); |
| |
| if (parameter_block->IsConstant()) { |
| gradient_checking_problem_impl->SetParameterBlockConstant( |
| parameter_block->mutable_user_state()); |
| } |
| } |
| |
| // For every ResidualBlock in problem_impl, create a new |
| // ResidualBlock by wrapping its CostFunction inside a |
| // GradientCheckingCostFunction. |
| const vector<ResidualBlock*>& residual_blocks = program->residual_blocks(); |
| for (int i = 0; i < residual_blocks.size(); ++i) { |
| ResidualBlock* residual_block = residual_blocks[i]; |
| |
| // Build a human readable string which identifies the |
| // ResidualBlock. This is used by the GradientCheckingCostFunction |
| // when logging debugging information. |
| string extra_info = StringPrintf( |
| "Residual block id %d; depends on parameters [", i); |
| vector<double*> parameter_blocks; |
| for (int j = 0; j < residual_block->NumParameterBlocks(); ++j) { |
| ParameterBlock* parameter_block = residual_block->parameter_blocks()[j]; |
| parameter_blocks.push_back(parameter_block->mutable_user_state()); |
| StringAppendF(&extra_info, "%p", parameter_block->mutable_user_state()); |
| extra_info += (j < residual_block->NumParameterBlocks() - 1) ? ", " : "]"; |
| } |
| |
| // Wrap the original CostFunction in a GradientCheckingCostFunction. |
| CostFunction* gradient_checking_cost_function = |
| CreateGradientCheckingCostFunction(residual_block->cost_function(), |
| relative_step_size, |
| relative_precision, |
| extra_info); |
| |
| // The const_cast is necessary because |
| // ProblemImpl::AddResidualBlock can potentially take ownership of |
| // the LossFunction, but in this case we are guaranteed that this |
| // will not be the case, so this const_cast is harmless. |
| gradient_checking_problem_impl->AddResidualBlock( |
| gradient_checking_cost_function, |
| const_cast<LossFunction*>(residual_block->loss_function()), |
| parameter_blocks); |
| } |
| |
| // Normally, when a problem is given to the solver, we guarantee |
| // that the state pointers for each parameter block point to the |
| // user provided data. Since we are creating this new problem from a |
| // problem given to us at an arbitrary stage of the solve, we cannot |
| // depend on this being the case, so we explicitly call |
| // SetParameterBlockStatePtrsToUserStatePtrs to ensure that this is |
| // the case. |
| gradient_checking_problem_impl |
| ->mutable_program() |
| ->SetParameterBlockStatePtrsToUserStatePtrs(); |
| |
| return gradient_checking_problem_impl; |
| } |
| |
| |
| } // namespace internal |
| } // namespace ceres |
