Move from Ordering to ParameterBlockOrdering. Change-Id: I9320afff13ee62be407c725f42f41a18f537bcc1
diff --git a/examples/bundle_adjuster.cc b/examples/bundle_adjuster.cc index bd405e4..16a9c1e 100644 --- a/examples/bundle_adjuster.cc +++ b/examples/bundle_adjuster.cc
@@ -176,22 +176,22 @@ return; } - ceres::Ordering* ordering = new ceres::Ordering; + ceres::ParameterBlockOrdering* ordering = + new ceres::ParameterBlockOrdering; // The points come before the cameras. for (int i = 0; i < num_points; ++i) { - ordering->AddParameterBlockToGroup(points + point_block_size * i, 0); + ordering->AddElementToGroup(points + point_block_size * i, 0); } for (int i = 0; i < num_cameras; ++i) { // When using axis-angle, there is a single parameter block for // the entire camera. - ordering->AddParameterBlockToGroup(cameras + camera_block_size * i, 1); + ordering->AddElementToGroup(cameras + camera_block_size * i, 1); // If quaternions are used, there are two blocks, so add the // second block to the ordering. if (FLAGS_use_quaternions) { - ordering->AddParameterBlockToGroup( - cameras + camera_block_size * i + 4, 1); + ordering->AddElementToGroup(cameras + camera_block_size * i + 4, 1); } }
diff --git a/include/ceres/ceres.h b/include/ceres/ceres.h index b28c016..9b8f212 100644 --- a/include/ceres/ceres.h +++ b/include/ceres/ceres.h
@@ -43,7 +43,7 @@ #include "ceres/local_parameterization.h" #include "ceres/loss_function.h" #include "ceres/numeric_diff_cost_function.h" -#include "ceres/ordering.h" +#include "ceres/ordered_groups.h" #include "ceres/problem.h" #include "ceres/sized_cost_function.h" #include "ceres/solver.h"
diff --git a/include/ceres/ordered_groups.h b/include/ceres/ordered_groups.h index 5f41dd4..d9210b3 100644 --- a/include/ceres/ordered_groups.h +++ b/include/ceres/ordered_groups.h
@@ -28,6 +28,9 @@ // // Author: sameeragarwal@google.com (Sameer Agarwal) +#ifndef CERES_PUBLIC_ORDERED_GROUPS_H_ +#define CERES_PUBLIC_ORDERED_GROUPS_H_ + #include <map> #include <set> #include "ceres/collections_port.h" @@ -144,3 +147,5 @@ typedef OrderedGroups<double*> ParameterBlockOrdering; } // namespace ceres + +#endif // CERES_PUBLIC_ORDERED_GROUP_H_
diff --git a/include/ceres/ordering.h b/include/ceres/ordering.h deleted file mode 100644 index c302aad..0000000 --- a/include/ceres/ordering.h +++ /dev/null
@@ -1,128 +0,0 @@ -// Ceres Solver - A fast non-linear least squares minimizer -// Copyright 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: sameeragarwal@google.com (Sameer Agarwal) - -#include <map> -#include <set> -#include "ceres/internal/port.h" -#include "glog/logging.h" - -namespace ceres { - -// The order in which variables are eliminated in a linear solver can -// have a significant of impact on the efficiency and accuracy of the -// method. e.g., when doing sparse Cholesky factorization, there are -// matrices for which a good ordering will give a Cholesky factor with -// O(n) storage, where as a bad ordering will result in an completely -// dense factor. -// -// Ceres allows the user to provide varying amounts of hints to the -// solver about the variable elimination ordering to use. This can -// range from no hints, where the solver is free to decide the best -// possible ordering based on the user's choices like the linear -// solver being used, to an exact order in which the variables should -// be eliminated, and a variety of possibilities in between. Instances -// of the Ordering class are used to communicate this infornation to -// Ceres. -// -// Formally an ordering is an ordered partitioning of the parameter -// blocks, i.e, each parameter block belongs to exactly one group, and -// each group has a unique integer associated with it, that determines -// its order in the set of groups. -// -// Given such an ordering, Ceres ensures that the parameter blocks in -// the lowest numbered group are eliminated first, and then the -// parmeter blocks in the next lowest numbered group and so on. Within -// each group, Ceres is free to order the parameter blocks as it -// chooses. -// e.g. Consider the linear system -// -// x + y = 3 -// 2x + 3y = 7 -// -// There are two ways in which it can be solved. First eliminating x -// from the two equations, solving for y and then back substituting -// for x, or first eliminating y, solving for x and back substituting -// for y. The user can construct three orderings here. -// -// {0: x}, {1: y} - eliminate x first. -// {0: y}, {1: x} - eliminate y first. -// {0: x, y} - Solver gets to decide the elimination order. -// -// Thus, to have Ceres determine the ordering automatically using -// heuristics, put all the variables in group 0 and to control the -// ordering for every variable, create groups 0..N-1, one per -// variable, in the desired order. -// -// Bundle Adjustment -// ----------------- -// -// A particular case of interest is bundle adjustment, where the user -// has two options. The default is to not specify an ordering at all, -// the solver will see that the user wants to use a Schur type solver -// and figure out the right elimination ordering. -// -// But if the user already knows what parameter blocks are points and -// what are cameras, they can save preprocessing time by partitioning -// the parameter blocks into two groups, one for the points and one -// for the cameras, where the group containing the points has an id -// smaller than the group containing cameras. -class Ordering { - public: - // Add a parameter block to a group with id group_id. If a group - // with this id does not exist, one is created. This method can be - // called any number of times for a parameter block. - void AddParameterBlockToGroup(double* parameter_block, int group_id); - - // Remove the parameter block from the ordering, no matter what - // group it is in. If the parameter block is not known to the - // ordering, calling this method will result in a crash. - void RemoveParameterBlock(double* parameter_block); - - // Return the group id for the parameter block. If the parameter - // block is not known to the Ordering, calling this method results - // in a crash. - int GroupIdForParameterBlock(double* parameter_block) const; - - // This function always succeeds. For a group_id unknown to the - // ordering is treated as empty groups and the function returns - // zero. - int GroupSize(int group_id) const; - - bool ContainsParameterBlock(double* parameter_block) const; - int NumParameterBlocks() const; - int NumGroups() const; - const map<int, set<double*> >& group_id_to_parameter_blocks() const; - - private: - map<int, set<double*> > group_id_to_parameter_blocks_; - map<double*, int> parameter_block_to_group_id_; -}; - -} // namespace ceres
diff --git a/include/ceres/solver.h b/include/ceres/solver.h index 7922f1c..e7b6b32 100644 --- a/include/ceres/solver.h +++ b/include/ceres/solver.h
@@ -38,11 +38,11 @@ #include "ceres/internal/macros.h" #include "ceres/internal/port.h" #include "ceres/iteration_callback.h" +#include "ceres/ordered_groups.h" #include "ceres/types.h" namespace ceres { -class Ordering; class Problem; // Interface for non-linear least squares solvers. @@ -245,13 +245,14 @@ // variables should be eliminated, and a variety of possibilities // in between. // - // Instances of the Ordering class are used to communicate this - // infornation to Ceres. + // Instances of the ParameterBlockOrdering class are used to + // communicate this information to Ceres. // - // Formally an ordering is an ordered partitioning of the parameter - // blocks, i.e, each parameter block belongs to exactly one group, and - // each group has a unique integer associated with it, that determines - // its order in the set of groups. + // Formally an ordering is an ordered partitioning of the + // parameter blocks, i.e, each parameter block belongs to exactly + // one group, and each group has a unique non-negative integer + // associated with it, that determines its order in the set of + // groups. // // Given such an ordering, Ceres ensures that the parameter blocks in // the lowest numbered group are eliminated first, and then the @@ -261,8 +262,41 @@ // // If NULL, then all parameter blocks are assumed to be in the // same group and the solver is free to decide the best - // ordering. (See ordering.h for more details). - Ordering* ordering; + // ordering. + // + // e.g. Consider the linear system + // + // x + y = 3 + // 2x + 3y = 7 + // + // There are two ways in which it can be solved. First eliminating x + // from the two equations, solving for y and then back substituting + // for x, or first eliminating y, solving for x and back substituting + // for y. The user can construct three orderings here. + // + // {0: x}, {1: y} - eliminate x first. + // {0: y}, {1: x} - eliminate y first. + // {0: x, y} - Solver gets to decide the elimination order. + // + // Thus, to have Ceres determine the ordering automatically using + // heuristics, put all the variables in group 0 and to control the + // ordering for every variable, create groups 0..N-1, one per + // variable, in the desired order. + // + // Bundle Adjustment + // ----------------- + // + // A particular case of interest is bundle adjustment, where the user + // has two options. The default is to not specify an ordering at all, + // the solver will see that the user wants to use a Schur type solver + // and figure out the right elimination ordering. + // + // But if the user already knows what parameter blocks are points and + // what are cameras, they can save preprocessing time by partitioning + // the parameter blocks into two groups, one for the points and one + // for the cameras, where the group containing the points has an id + // smaller than the group containing cameras. + ParameterBlockOrdering* ordering; // Some non-linear least squares problems have additional // structure in the way the parameter blocks interact that it is
diff --git a/internal/ceres/CMakeLists.txt b/internal/ceres/CMakeLists.txt index e0e8afa..3d7d496 100644 --- a/internal/ceres/CMakeLists.txt +++ b/internal/ceres/CMakeLists.txt
@@ -64,7 +64,6 @@ local_parameterization.cc loss_function.cc normal_prior.cc - ordering.cc partitioned_matrix_view.cc polynomial_solver.cc problem.cc @@ -234,7 +233,6 @@ CERES_TEST(minimizer) CERES_TEST(normal_prior) CERES_TEST(numeric_diff_cost_function) - CERES_TEST(ordering) CERES_TEST(ordered_groups) CERES_TEST(parameter_block) CERES_TEST(partitioned_matrix_view)
diff --git a/internal/ceres/inner_iteration_minimizer.cc b/internal/ceres/inner_iteration_minimizer.cc index 6a9b419..36748ef 100644 --- a/internal/ceres/inner_iteration_minimizer.cc +++ b/internal/ceres/inner_iteration_minimizer.cc
@@ -35,7 +35,7 @@ #include "ceres/evaluator.h" #include "ceres/linear_solver.h" #include "ceres/minimizer.h" -#include "ceres/ordering.h" +#include "ceres/ordered_groups.h" #include "ceres/parameter_block.h" #include "ceres/problem_impl.h" #include "ceres/program.h" @@ -58,7 +58,7 @@ string* error) { program_.reset(new Program(outer_program)); - Ordering ordering; + ParameterBlockOrdering ordering; int num_inner_iteration_parameter_blocks = 0; if (parameter_blocks_for_inner_iterations.size() == 0) { @@ -79,9 +79,9 @@ for (int i = 0; i < parameter_block_ordering.size(); ++i) { double* ptr = parameter_block_ordering[i]->mutable_user_state(); if (i < num_inner_iteration_parameter_blocks) { - ordering.AddParameterBlockToGroup(ptr, 0); + ordering.AddElementToGroup(ptr, 0); } else { - ordering.AddParameterBlockToGroup(ptr, 1); + ordering.AddElementToGroup(ptr, 1); } } } else { @@ -95,18 +95,18 @@ for (int i = 0; i < parameter_blocks.size(); ++i) { double* ptr = parameter_blocks[i]->mutable_user_state(); if (parameter_block_ptrs.count(ptr) != 0) { - ordering.AddParameterBlockToGroup(ptr, 0); + ordering.AddElementToGroup(ptr, 0); } else { - ordering.AddParameterBlockToGroup(ptr, 1); + ordering.AddElementToGroup(ptr, 1); } } num_inner_iteration_parameter_blocks = ordering.GroupSize(0); if (num_inner_iteration_parameter_blocks > 0) { - const map<int, set<double*> >& group_id_to_parameter_blocks = - ordering.group_id_to_parameter_blocks(); + const map<int, set<double*> >& group_to_elements = + ordering.group_to_elements(); if (!SolverImpl::IsParameterBlockSetIndependent( - group_id_to_parameter_blocks.begin()->second, + group_to_elements.begin()->second, program_->residual_blocks())) { *error = "The user provided parameter_blocks_for_inner_iterations " "does not form an independent set";
diff --git a/internal/ceres/ordering.cc b/internal/ceres/ordering.cc deleted file mode 100644 index 4b3ec25..0000000 --- a/internal/ceres/ordering.cc +++ /dev/null
@@ -1,95 +0,0 @@ -// Ceres Solver - A fast non-linear least squares minimizer -// Copyright 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: sameeragarwal@google.com (Sameer Agarwal) - -#include <map> -#include <set> -#include "ceres/internal/port.h" -#include "ceres/ordering.h" -#include "glog/logging.h" - -namespace ceres { - -void Ordering::AddParameterBlockToGroup(double* parameter_block, int group_id) { - const map<double*, int>::const_iterator it = - parameter_block_to_group_id_.find(parameter_block); - - if (it != parameter_block_to_group_id_.end()) { - group_id_to_parameter_blocks_[it->second].erase(parameter_block); - if (group_id_to_parameter_blocks_[it->second].size() == 0) { - group_id_to_parameter_blocks_.erase(it->second); - } - } - - parameter_block_to_group_id_[parameter_block] = group_id; - group_id_to_parameter_blocks_[group_id].insert(parameter_block); -} - -void Ordering::RemoveParameterBlock(double* parameter_block) { - const int current_group_id = GroupIdForParameterBlock(parameter_block); - group_id_to_parameter_blocks_[current_group_id].erase(parameter_block); - if (group_id_to_parameter_blocks_[current_group_id].size() == 0) { - group_id_to_parameter_blocks_.erase(current_group_id); - } - - parameter_block_to_group_id_.erase(parameter_block); -} - -int Ordering::GroupIdForParameterBlock(double* parameter_block) const { - const map<double*, int>::const_iterator it = - parameter_block_to_group_id_.find(parameter_block); - CHECK(it != parameter_block_to_group_id_.end()) - << "Tried finding the group id of a parameter block unknown to " - << "the ordering: " << parameter_block; - return it->second; -} - -bool Ordering::ContainsParameterBlock(double* parameter_block) const { - const map<double*, int>::const_iterator it = - parameter_block_to_group_id_.find(parameter_block); - return (it != parameter_block_to_group_id_.end()); -} - -int Ordering::NumParameterBlocks() const { - return parameter_block_to_group_id_.size(); -} - -int Ordering::NumGroups() const { return group_id_to_parameter_blocks_.size(); } - -int Ordering::GroupSize(int group_id) const { - map<int, set<double*> >::const_iterator it = - group_id_to_parameter_blocks_.find(group_id); - return (it == group_id_to_parameter_blocks_.end()) ? 0 : it->second.size(); -} - -const map<int, set<double*> >& Ordering::group_id_to_parameter_blocks() const { - return group_id_to_parameter_blocks_; -} - -} // namespace ceres
diff --git a/internal/ceres/ordering_test.cc b/internal/ceres/ordering_test.cc deleted file mode 100644 index 9bd43b3..0000000 --- a/internal/ceres/ordering_test.cc +++ /dev/null
@@ -1,140 +0,0 @@ -// Ceres Solver - A fast non-linear least squares minimizer -// Copyright 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: sameeragarwal@google.com (Sameer Agarwal) - -#include "ceres/ordering.h" - -#include <cstddef> -#include <vector> -#include "gtest/gtest.h" -#include "ceres/collections_port.h" - -namespace ceres { -namespace internal { - -TEST(Ordering, EmptyOrderingBehavesCorrectly) { - Ordering ordering; - EXPECT_EQ(ordering.NumGroups(), 0); - EXPECT_EQ(ordering.NumParameterBlocks(), 0); - EXPECT_EQ(ordering.GroupSize(1), 0); - double x; - EXPECT_DEATH_IF_SUPPORTED(ordering.GroupIdForParameterBlock(&x), - "Tried finding"); - EXPECT_DEATH_IF_SUPPORTED(ordering.RemoveParameterBlock(&x), - "Tried finding"); -} - -TEST(Ordering, EverythingInOneGroup) { - Ordering ordering; - double x[3]; - ordering.AddParameterBlockToGroup(x, 1); - ordering.AddParameterBlockToGroup(x + 1, 1); - ordering.AddParameterBlockToGroup(x + 2, 1); - ordering.AddParameterBlockToGroup(x, 1); - - EXPECT_EQ(ordering.NumGroups(), 1); - EXPECT_EQ(ordering.NumParameterBlocks(), 3); - EXPECT_EQ(ordering.GroupSize(1), 3); - EXPECT_EQ(ordering.GroupSize(0), 0); - EXPECT_EQ(ordering.GroupIdForParameterBlock(x), 1); - EXPECT_EQ(ordering.GroupIdForParameterBlock(x + 1), 1); - EXPECT_EQ(ordering.GroupIdForParameterBlock(x + 2), 1); - - ordering.RemoveParameterBlock(x); - EXPECT_EQ(ordering.NumGroups(), 1); - EXPECT_EQ(ordering.NumParameterBlocks(), 2); - EXPECT_EQ(ordering.GroupSize(1), 2); - EXPECT_EQ(ordering.GroupSize(0), 0); - - EXPECT_DEATH_IF_SUPPORTED(ordering.GroupIdForParameterBlock(x), - "Tried finding"); - EXPECT_EQ(ordering.GroupIdForParameterBlock(x + 1), 1); - EXPECT_EQ(ordering.GroupIdForParameterBlock(x + 2), 1); -} - -TEST(Ordering, StartInOneGroupAndThenSplit) { - Ordering ordering; - double x[3]; - ordering.AddParameterBlockToGroup(x, 1); - ordering.AddParameterBlockToGroup(x + 1, 1); - ordering.AddParameterBlockToGroup(x + 2, 1); - ordering.AddParameterBlockToGroup(x, 1); - - EXPECT_EQ(ordering.NumGroups(), 1); - EXPECT_EQ(ordering.NumParameterBlocks(), 3); - EXPECT_EQ(ordering.GroupSize(1), 3); - EXPECT_EQ(ordering.GroupSize(0), 0); - EXPECT_EQ(ordering.GroupIdForParameterBlock(x), 1); - EXPECT_EQ(ordering.GroupIdForParameterBlock(x + 1), 1); - EXPECT_EQ(ordering.GroupIdForParameterBlock(x + 2), 1); - - ordering.AddParameterBlockToGroup(x, 5); - EXPECT_EQ(ordering.NumGroups(), 2); - EXPECT_EQ(ordering.NumParameterBlocks(), 3); - EXPECT_EQ(ordering.GroupSize(1), 2); - EXPECT_EQ(ordering.GroupSize(5), 1); - EXPECT_EQ(ordering.GroupSize(0), 0); - - EXPECT_EQ(ordering.GroupIdForParameterBlock(x), 5); - EXPECT_EQ(ordering.GroupIdForParameterBlock(x + 1), 1); - EXPECT_EQ(ordering.GroupIdForParameterBlock(x + 2), 1); -} - -TEST(Ordering, AddAndRemoveEveryThingFromOneGroup) { - Ordering ordering; - double x[3]; - ordering.AddParameterBlockToGroup(x, 1); - ordering.AddParameterBlockToGroup(x + 1, 1); - ordering.AddParameterBlockToGroup(x + 2, 1); - ordering.AddParameterBlockToGroup(x, 1); - - EXPECT_EQ(ordering.NumGroups(), 1); - EXPECT_EQ(ordering.NumParameterBlocks(), 3); - EXPECT_EQ(ordering.GroupSize(1), 3); - EXPECT_EQ(ordering.GroupSize(0), 0); - EXPECT_EQ(ordering.GroupIdForParameterBlock(x), 1); - EXPECT_EQ(ordering.GroupIdForParameterBlock(x + 1), 1); - EXPECT_EQ(ordering.GroupIdForParameterBlock(x + 2), 1); - - ordering.AddParameterBlockToGroup(x, 5); - ordering.AddParameterBlockToGroup(x + 1, 5); - ordering.AddParameterBlockToGroup(x + 2, 5); - EXPECT_EQ(ordering.NumGroups(), 1); - EXPECT_EQ(ordering.NumParameterBlocks(), 3); - EXPECT_EQ(ordering.GroupSize(1), 0); - EXPECT_EQ(ordering.GroupSize(5), 3); - EXPECT_EQ(ordering.GroupSize(0), 0); - - EXPECT_EQ(ordering.GroupIdForParameterBlock(x), 5); - EXPECT_EQ(ordering.GroupIdForParameterBlock(x + 1), 5); - EXPECT_EQ(ordering.GroupIdForParameterBlock(x + 2), 5); -} - -} // namespace internal -} // namespace ceres
diff --git a/internal/ceres/solver_impl.cc b/internal/ceres/solver_impl.cc index 4f914fa..c052aeb 100644 --- a/internal/ceres/solver_impl.cc +++ b/internal/ceres/solver_impl.cc
@@ -41,7 +41,7 @@ #include "ceres/linear_solver.h" #include "ceres/map_util.h" #include "ceres/minimizer.h" -#include "ceres/ordering.h" +#include "ceres/ordered_groups.h" #include "ceres/parameter_block.h" #include "ceres/problem.h" #include "ceres/problem_impl.h" @@ -260,15 +260,15 @@ LOG(WARNING) << summary->error; return; } - options.ordering = new Ordering(*original_options.ordering); + options.ordering = new ParameterBlockOrdering(*original_options.ordering); } else { - options.ordering = new Ordering; + options.ordering = new ParameterBlockOrdering; const ProblemImpl::ParameterMap& parameter_map = problem_impl->parameter_map(); for (ProblemImpl::ParameterMap::const_iterator it = parameter_map.begin(); it != parameter_map.end(); ++it) { - options.ordering->AddParameterBlockToGroup(it->first, 0); + options.ordering->AddElementToGroup(it->first, 0); } } @@ -334,7 +334,7 @@ // Only Schur types require the lexicographic reordering. if (IsSchurType(options.linear_solver_type)) { const int num_eliminate_blocks = - options.ordering->group_id_to_parameter_blocks().begin()->second.size(); + options.ordering->group_to_elements().begin()->second.size(); if (!LexicographicallyOrderResidualBlocks(num_eliminate_blocks, reduced_program.get(), &summary->error)) { @@ -415,7 +415,7 @@ bool SolverImpl::IsOrderingValid(const Solver::Options& options, const ProblemImpl* problem_impl, string* error) { - if (options.ordering->NumParameterBlocks() != + if (options.ordering->NumElements() != problem_impl->NumParameterBlocks()) { *error = "Number of parameter blocks in user supplied ordering " "does not match the number of parameter blocks in the problem"; @@ -428,8 +428,7 @@ for (vector<ParameterBlock*>::const_iterator it = parameter_blocks.begin(); it != parameter_blocks.end(); ++it) { - if (!options.ordering->ContainsParameterBlock( - const_cast<double*>((*it)->user_state()))) { + if (!options.ordering->IsMember(const_cast<double*>((*it)->user_state()))) { *error = "Problem contains a parameter block that is not in " "the user specified ordering."; return false; @@ -439,7 +438,7 @@ if (IsSchurType(options.linear_solver_type) && options.ordering->NumGroups() > 1) { const set<double*>& e_blocks = - options.ordering->group_id_to_parameter_blocks().begin()->second; + options.ordering->group_to_elements().begin()->second; if (!IsParameterBlockSetIndependent(e_blocks, residual_blocks)) { *error = "The user requested the use of a Schur type solver. " "But the first elimination group in the ordering is not an " @@ -478,7 +477,7 @@ // Strips varying parameters and residuals, maintaining order, and updating // num_eliminate_blocks. bool SolverImpl::RemoveFixedBlocksFromProgram(Program* program, - Ordering* ordering, + ParameterBlockOrdering* ordering, double* fixed_cost, string* error) { vector<ParameterBlock*>* parameter_blocks = @@ -547,7 +546,7 @@ if (parameter_block->index() == 1) { (*parameter_blocks)[j++] = parameter_block; } else { - ordering->RemoveParameterBlock(parameter_block->mutable_user_state()); + ordering->Remove(parameter_block->mutable_user_state()); } } parameter_blocks->resize(j); @@ -568,10 +567,10 @@ CHECK_NOTNULL(options->ordering); Program* original_program = problem_impl->mutable_program(); scoped_ptr<Program> transformed_program(new Program(*original_program)); - Ordering* ordering = options->ordering; + ParameterBlockOrdering* ordering = options->ordering; const int min_group_id = - ordering->group_id_to_parameter_blocks().begin()->first; + ordering->group_to_elements().begin()->first; const int original_num_groups = ordering->NumGroups(); if (!RemoveFixedBlocksFromProgram(transformed_program.get(), @@ -603,7 +602,7 @@ << "to the developers."; for (int i = 0; i < schur_ordering.size(); ++i) { - ordering->AddParameterBlockToGroup(schur_ordering[i]->mutable_user_state(), + ordering->AddElementToGroup(schur_ordering[i]->mutable_user_state(), (i < num_eliminate_blocks) ? 0 : 1); } } @@ -764,7 +763,7 @@ linear_solver_options.use_block_amd = options->use_block_amd; const map<int, set<double*> >& groups = - options->ordering->group_id_to_parameter_blocks(); + options->ordering->group_to_elements(); for (map<int, set<double*> >::const_iterator it = groups.begin(); it != groups.end(); ++it) { @@ -783,15 +782,15 @@ } bool SolverImpl::ApplyUserOrdering(const ProblemImpl::ParameterMap& parameter_map, - const Ordering* ordering, + const ParameterBlockOrdering* ordering, Program* program, string* error) { - if (ordering->NumParameterBlocks() != program->NumParameterBlocks()) { + if (ordering->NumElements() != program->NumParameterBlocks()) { *error = StringPrintf("User specified ordering does not have the same " "number of parameters as the problem. The problem" "has %d blocks while the ordering has %d blocks.", program->NumParameterBlocks(), - ordering->NumParameterBlocks()); + ordering->NumElements()); return false; } @@ -800,7 +799,7 @@ parameter_blocks->clear(); const map<int, set<double*> >& groups = - ordering->group_id_to_parameter_blocks(); + ordering->group_to_elements(); for (map<int, set<double*> >::const_iterator group_it = groups.begin(); group_it != groups.end(); @@ -934,7 +933,7 @@ evaluator_options.num_eliminate_blocks = (options.ordering->NumGroups() > 0 && IsSchurType(options.linear_solver_type)) - ? options.ordering->group_id_to_parameter_blocks().begin()->second.size() + ? options.ordering->group_to_elements().begin()->second.size() : 0; evaluator_options.num_threads = options.num_threads; return Evaluator::Create(evaluator_options, program, error);
diff --git a/internal/ceres/solver_impl.h b/internal/ceres/solver_impl.h index eb81696..140de95 100644 --- a/internal/ceres/solver_impl.h +++ b/internal/ceres/solver_impl.h
@@ -34,12 +34,11 @@ #include <string> #include <vector> #include "ceres/internal/port.h" +#include "ceres/ordered_groups.h" #include "ceres/solver.h" #include "ceres/problem_impl.h" namespace ceres { -class Ordering; - namespace internal { class Evaluator; @@ -79,7 +78,7 @@ // return value of true indicates success and false indicates an // error was encountered whose cause is logged to LOG(ERROR). static bool ApplyUserOrdering(const ProblemImpl::ParameterMap& parameter_map, - const Ordering* ordering, + const ParameterBlockOrdering* ordering, Program* program, string* error); @@ -116,7 +115,7 @@ // NULL, the residual blocks that are removed are evaluated and the // sum of their cost is returned in fixed_cost. static bool RemoveFixedBlocksFromProgram(Program* program, - Ordering* ordering, + ParameterBlockOrdering* ordering, double* fixed_cost, string* error);
diff --git a/internal/ceres/solver_impl_test.cc b/internal/ceres/solver_impl_test.cc index 3148024..5f4a82c 100644 --- a/internal/ceres/solver_impl_test.cc +++ b/internal/ceres/solver_impl_test.cc
@@ -31,7 +31,7 @@ #include "gtest/gtest.h" #include "ceres/autodiff_cost_function.h" #include "ceres/linear_solver.h" -#include "ceres/ordering.h" +#include "ceres/ordered_groups.h" #include "ceres/parameter_block.h" #include "ceres/problem_impl.h" #include "ceres/program.h" @@ -88,10 +88,10 @@ string error; { - Ordering ordering; - ordering.AddParameterBlockToGroup(&x, 0); - ordering.AddParameterBlockToGroup(&y, 0); - ordering.AddParameterBlockToGroup(&z, 0); + ParameterBlockOrdering ordering; + ordering.AddElementToGroup(&x, 0); + ordering.AddElementToGroup(&y, 0); + ordering.AddElementToGroup(&z, 0); Program program(*problem.mutable_program()); EXPECT_TRUE(SolverImpl::RemoveFixedBlocksFromProgram(&program, @@ -100,7 +100,7 @@ &error)); EXPECT_EQ(program.NumParameterBlocks(), 3); EXPECT_EQ(program.NumResidualBlocks(), 3); - EXPECT_EQ(ordering.NumParameterBlocks(), 3); + EXPECT_EQ(ordering.NumElements(), 3); } } @@ -112,8 +112,8 @@ problem.AddResidualBlock(new UnaryCostFunction(), NULL, &x); problem.SetParameterBlockConstant(&x); - Ordering ordering; - ordering.AddParameterBlockToGroup(&x, 0); + ParameterBlockOrdering ordering; + ordering.AddElementToGroup(&x, 0); Program program(problem.program()); string error; @@ -123,7 +123,7 @@ &error)); EXPECT_EQ(program.NumParameterBlocks(), 0); EXPECT_EQ(program.NumResidualBlocks(), 0); - EXPECT_EQ(ordering.NumParameterBlocks(), 0); + EXPECT_EQ(ordering.NumElements(), 0); } TEST(SolverImpl, RemoveFixedBlocksNoResidualBlocks) { @@ -136,10 +136,10 @@ problem.AddParameterBlock(&y, 1); problem.AddParameterBlock(&z, 1); - Ordering ordering; - ordering.AddParameterBlockToGroup(&x, 0); - ordering.AddParameterBlockToGroup(&y, 0); - ordering.AddParameterBlockToGroup(&z, 0); + ParameterBlockOrdering ordering; + ordering.AddElementToGroup(&x, 0); + ordering.AddElementToGroup(&y, 0); + ordering.AddElementToGroup(&z, 0); Program program(problem.program()); @@ -150,7 +150,7 @@ &error)); EXPECT_EQ(program.NumParameterBlocks(), 0); EXPECT_EQ(program.NumResidualBlocks(), 0); - EXPECT_EQ(ordering.NumParameterBlocks(), 0); + EXPECT_EQ(ordering.NumElements(), 0); } TEST(SolverImpl, RemoveFixedBlocksOneParameterBlockConstant) { @@ -163,10 +163,10 @@ problem.AddParameterBlock(&y, 1); problem.AddParameterBlock(&z, 1); - Ordering ordering; - ordering.AddParameterBlockToGroup(&x, 0); - ordering.AddParameterBlockToGroup(&y, 0); - ordering.AddParameterBlockToGroup(&z, 0); + ParameterBlockOrdering ordering; + ordering.AddElementToGroup(&x, 0); + ordering.AddElementToGroup(&y, 0); + ordering.AddElementToGroup(&z, 0); problem.AddResidualBlock(new UnaryCostFunction(), NULL, &x); problem.AddResidualBlock(new BinaryCostFunction(), NULL, &x, &y); @@ -181,7 +181,7 @@ &error)); EXPECT_EQ(program.NumParameterBlocks(), 1); EXPECT_EQ(program.NumResidualBlocks(), 1); - EXPECT_EQ(ordering.NumParameterBlocks(), 1); + EXPECT_EQ(ordering.NumElements(), 1); } TEST(SolverImpl, RemoveFixedBlocksNumEliminateBlocks) { @@ -198,10 +198,10 @@ problem.AddResidualBlock(new BinaryCostFunction(), NULL, &x, &y); problem.SetParameterBlockConstant(&x); - Ordering ordering; - ordering.AddParameterBlockToGroup(&x, 0); - ordering.AddParameterBlockToGroup(&y, 0); - ordering.AddParameterBlockToGroup(&z, 1); + ParameterBlockOrdering ordering; + ordering.AddElementToGroup(&x, 0); + ordering.AddElementToGroup(&y, 0); + ordering.AddElementToGroup(&z, 1); Program program(problem.program()); string error; @@ -211,9 +211,9 @@ &error)); EXPECT_EQ(program.NumParameterBlocks(), 2); EXPECT_EQ(program.NumResidualBlocks(), 2); - EXPECT_EQ(ordering.NumParameterBlocks(), 2); - EXPECT_EQ(ordering.GroupIdForParameterBlock(&y), 0); - EXPECT_EQ(ordering.GroupIdForParameterBlock(&z), 1); + EXPECT_EQ(ordering.NumElements(), 2); + EXPECT_EQ(ordering.GroupId(&y), 0); + EXPECT_EQ(ordering.GroupId(&z), 1); } TEST(SolverImpl, RemoveFixedBlocksFixedCost) { @@ -230,10 +230,10 @@ problem.AddResidualBlock(new BinaryCostFunction(), NULL, &x, &y); problem.SetParameterBlockConstant(&x); - Ordering ordering; - ordering.AddParameterBlockToGroup(&x, 0); - ordering.AddParameterBlockToGroup(&y, 0); - ordering.AddParameterBlockToGroup(&z, 1); + ParameterBlockOrdering ordering; + ordering.AddElementToGroup(&x, 0); + ordering.AddElementToGroup(&y, 0); + ordering.AddElementToGroup(&z, 1); double fixed_cost = 0.0; Program program(problem.program()); @@ -250,9 +250,9 @@ &error)); EXPECT_EQ(program.NumParameterBlocks(), 2); EXPECT_EQ(program.NumResidualBlocks(), 2); - EXPECT_EQ(ordering.NumParameterBlocks(), 2); - EXPECT_EQ(ordering.GroupIdForParameterBlock(&y), 0); - EXPECT_EQ(ordering.GroupIdForParameterBlock(&z), 1); + EXPECT_EQ(ordering.NumElements(), 2); + EXPECT_EQ(ordering.GroupId(&y), 0); + EXPECT_EQ(ordering.GroupId(&z), 1); EXPECT_DOUBLE_EQ(fixed_cost, expected_fixed_cost); } @@ -273,10 +273,10 @@ problem.AddResidualBlock(new BinaryCostFunction(), NULL, &x, &y); problem.AddResidualBlock(new UnaryCostFunction(), NULL, &y); - Ordering* ordering = new Ordering; - ordering->AddParameterBlockToGroup(&x, 0); - ordering->AddParameterBlockToGroup(&y, 0); - ordering->AddParameterBlockToGroup(&z, 1); + ParameterBlockOrdering* ordering = new ParameterBlockOrdering; + ordering->AddElementToGroup(&x, 0); + ordering->AddElementToGroup(&y, 0); + ordering->AddElementToGroup(&z, 1); Solver::Options options; options.linear_solver_type = DENSE_SCHUR; @@ -335,10 +335,10 @@ problem.AddResidualBlock(new BinaryCostFunction(), NULL, &x, &z); // 6 x problem.AddResidualBlock(new UnaryCostFunction(), NULL, &y); // 7 - Ordering* ordering = new Ordering; - ordering->AddParameterBlockToGroup(&x, 0); - ordering->AddParameterBlockToGroup(&z, 0); - ordering->AddParameterBlockToGroup(&y, 1); + ParameterBlockOrdering* ordering = new ParameterBlockOrdering; + ordering->AddElementToGroup(&x, 0); + ordering->AddElementToGroup(&z, 0); + ordering->AddElementToGroup(&y, 1); Solver::Options options; options.linear_solver_type = DENSE_SCHUR; @@ -396,9 +396,9 @@ problem.AddParameterBlock(&y, 1); problem.AddParameterBlock(&z, 1); - Ordering ordering; - ordering.AddParameterBlockToGroup(&x, 0); - ordering.AddParameterBlockToGroup(&y, 1); + ParameterBlockOrdering ordering; + ordering.AddElementToGroup(&x, 0); + ordering.AddElementToGroup(&y, 1); Program program(problem.program()); string error; @@ -418,10 +418,10 @@ problem.AddParameterBlock(&y, 1); problem.AddParameterBlock(&z, 1); - Ordering ordering; - ordering.AddParameterBlockToGroup(&x, 0); - ordering.AddParameterBlockToGroup(&y, 2); - ordering.AddParameterBlockToGroup(&z, 1); + ParameterBlockOrdering ordering; + ordering.AddElementToGroup(&x, 0); + ordering.AddElementToGroup(&y, 2); + ordering.AddElementToGroup(&z, 1); Program* program = problem.mutable_program(); string error; @@ -452,7 +452,7 @@ options.linear_solver_type = DENSE_QR; options.linear_solver_max_num_iterations = -1; // CreateLinearSolver assumes a non-empty ordering. - options.ordering = new Ordering; + options.ordering = new ParameterBlockOrdering; string error; EXPECT_EQ(SolverImpl::CreateLinearSolver(&options, &error), static_cast<LinearSolver*>(NULL)); @@ -463,7 +463,7 @@ options.linear_solver_type = DENSE_QR; options.linear_solver_min_num_iterations = -1; // CreateLinearSolver assumes a non-empty ordering. - options.ordering = new Ordering; + options.ordering = new ParameterBlockOrdering; string error; EXPECT_EQ(SolverImpl::CreateLinearSolver(&options, &error), static_cast<LinearSolver*>(NULL)); @@ -474,7 +474,7 @@ options.linear_solver_type = DENSE_QR; options.linear_solver_min_num_iterations = 10; options.linear_solver_max_num_iterations = 5; - options.ordering = new Ordering; + options.ordering = new ParameterBlockOrdering; string error; EXPECT_EQ(SolverImpl::CreateLinearSolver(&options, &error), static_cast<LinearSolver*>(NULL)); @@ -486,11 +486,11 @@ options.num_linear_solver_threads = 2; // The Schur type solvers can only be created with the Ordering // contains at least one elimination group. - options.ordering = new Ordering; + options.ordering = new ParameterBlockOrdering; double x; double y; - options.ordering->AddParameterBlockToGroup(&x, 0); - options.ordering->AddParameterBlockToGroup(&y, 0); + options.ordering->AddElementToGroup(&x, 0); + options.ordering->AddElementToGroup(&y, 0); string error; scoped_ptr<LinearSolver> solver( @@ -504,7 +504,7 @@ Solver::Options options; options.trust_region_strategy_type = DOGLEG; // CreateLinearSolver assumes a non-empty ordering. - options.ordering = new Ordering; + options.ordering = new ParameterBlockOrdering; string error; options.linear_solver_type = ITERATIVE_SCHUR; EXPECT_EQ(SolverImpl::CreateLinearSolver(&options, &error), @@ -520,7 +520,7 @@ scoped_ptr<LinearSolver> solver; options.linear_solver_type = DENSE_QR; // CreateLinearSolver assumes a non-empty ordering. - options.ordering = new Ordering; + options.ordering = new ParameterBlockOrdering; string error; solver.reset(SolverImpl::CreateLinearSolver(&options, &error)); EXPECT_EQ(options.linear_solver_type, DENSE_QR); @@ -549,8 +549,8 @@ double x; double y; - options.ordering->AddParameterBlockToGroup(&x, 0); - options.ordering->AddParameterBlockToGroup(&y, 0); + options.ordering->AddElementToGroup(&x, 0); + options.ordering->AddElementToGroup(&y, 0); options.linear_solver_type = DENSE_SCHUR; solver.reset(SolverImpl::CreateLinearSolver(&options, &error));
diff --git a/internal/ceres/system_test.cc b/internal/ceres/system_test.cc index 4d78de7..8f1722a 100644 --- a/internal/ceres/system_test.cc +++ b/internal/ceres/system_test.cc
@@ -44,7 +44,7 @@ #include <string> #include "ceres/autodiff_cost_function.h" -#include "ceres/ordering.h" +#include "ceres/ordered_groups.h" #include "ceres/problem.h" #include "ceres/rotation.h" #include "ceres/solver.h" @@ -387,15 +387,15 @@ problem_.AddResidualBlock(cost_function, NULL, camera, point); } - options_.ordering = new Ordering; + options_.ordering = new ParameterBlockOrdering; // The points come before the cameras. for (int i = 0; i < num_points_; ++i) { - options_.ordering->AddParameterBlockToGroup(points + 3 * i, 0); + options_.ordering->AddElementToGroup(points + 3 * i, 0); } for (int i = 0; i < num_cameras_; ++i) { - options_.ordering->AddParameterBlockToGroup(cameras + 9 * i, 1); + options_.ordering->AddElementToGroup(cameras + 9 * i, 1); } options_.max_num_iterations = 25;