CeresSolver采用稀疏矩阵求解大规模BA时参数块设定

CeresSolver采用稀疏矩阵求解大规模BA时参数块设定

前言

在大规模BA求解中，通常会关注到相机位姿与路标参数构成矩阵的稀疏性，将相机位姿参数与路标点参数分组，采用舒尔补充等方法进行消元求解数据量大的组别，提升求解效率，具体可以参考ceres的LinearSolver¶部分。

在实际使用中，构造代价函数时需明确哪些参数为路标点参数，需要被消去；哪些参数为相机参数，首先求解，相当于将参数分组，并决定其消去的顺序。ceres内置了自动分组的方法，但有时不能奏效，此时就需要我们手工指定参数块的分组，并且来决定参数被消去的顺序。

CeresSolver教程相关说明

Ordering¶

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. For example 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.

线性解算器中变量的消除顺序对方法的效率和准确性有重大影响。例如，在进行稀疏Cholesky分解时，对于某些矩阵，良好的排序将给出具有O（n）存储的Cholesky因子，而糟糕的排序将导致完全稠密因子。

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 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.

Ceres允许用户向解算器提供不同数量的关于变量消除顺序使用的提示。这可能包括从没有提示，解算器可以根据用户的选择（如使用的线性解算器）自由决定最佳顺序，到消除变量的确切顺序，以及介于两者之间的各种可能性。

Instances of the ParameterBlockOrdering class are used to communicate this information to Ceres.

[ParameterBlockOrdering]的实例类用于将此信息传达给Ceres。

Formally an ordering is an ordered partitioning of the parameter blocks. 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. We call these groups Elimination Groups

形式上，排序是参数块的有序划分。每个参数块只属于一个组，每个组都有一个与之关联的唯一整数，该整数决定了它在组集中的顺序。我们称之为消除组*

Given such an ordering, Ceres ensures that the parameter blocks in the lowest numbered elimination group are eliminated first, and then the parameter blocks in the next lowest numbered elimination group and so on. Within each elimination group, Ceres is free to order the parameter blocks as it chooses. For example, consider the linear system

给定这样的顺序，Ceres确保首先消除编号最低的消除组中的参数块，然后消除下一个编号最低的消除组中的参数块，依此类推。在每个消除组中，Ceres可以根据自己的选择自由排列参数块。例如，考虑线性系统
x + y = 3 2 x + 3 y = 7 x+y=3\\ 2x+3y=7 x+y=32x+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.

有两种方法可以解决这个问题。首先从两个方程中消除x，解出y，然后反代x，或者先消除y，解出x，反代y。用户可以在这里构造三个排序s。

1. {0:x},{1:y} : Eliminate x first.
2. {0:y},{1:x} : Eliminate y first.
3. {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 the same elimination group. The identity of the group does not matter. This is the same as not specifying an ordering at all. To control the ordering for every variable, create an elimination group per variable, ordering them in the desired order.

因此，为了让Ceres使用启发法自动确定排序，将所有变量放在同一个消除组中。团体的身份无关紧要。这与根本不指定排序相同。要控制每个变量的顺序，请为每个变量创建一个消除组，并按所需顺序对它们进行排序。

If the user is using one of the Schur solvers (DENSE_SCHUR, SPARSE_SCHUR, ITERATIVE_SCHUR) and chooses to specify an ordering, it must have one important property. The lowest numbered elimination group must form an independent set in the graph corresponding to the Hessian, or in other words, no two parameter blocks in in the first elimination group should co-occur in the same residual block. For the best performance, this elimination group should be as large as possible. For standard bundle adjustment problems, this corresponds to the first elimination group containing all the 3d points, and the second containing the all the cameras parameter blocks.

如果用户正在使用一个舒尔解算器（“稠密舒尔”、“稀疏舒尔”、“迭代舒尔”），并选择指定排序，则它必须具有一个重要属性。编号最低的消除组必须在对应于Hessian的图中形成一个独立集，或者换句话说，第一个消除组中的两个参数块不应同时出现在同一个剩余块中。为了获得最佳性能，该淘汰组应尽可能大。对于标准束调整问题，这对应于包含所有3d点的第一个消除组，以及包含所有摄影机参数块的第二个消除组。

If the user leaves the choice to Ceres, then the solver uses an approximate maximum independent set algorithm to identify the first elimination group [LiSaad].

如果用户将选择权留给Ceres，则解算器使用近似最大独立集算法来识别第一个消除组[LiSaad].

CeresSolver中对应类的实现

ParameterBlockOrdering¶

• class ParameterBlockOrdering¶

  ParameterBlockOrdering is a class for storing and manipulating an ordered collection of groups/sets with the following semantics:Group IDs are non-negative integer values. Elements are any type that can serve as a key in a map or an element of a set.An element can only belong to one group at a time. A group may contain an arbitrary number of elements.Groups are ordered by their group id.

  ParameterBlockOrdering是一个用于存储和操作有序的组/集集合的类，具有以下语义：组ID是非负整数值。元素是可以作为地图中的键或集合中的元素的任何类型。一个元素一次只能属于一个组。一个组可以包含任意数量的元素。组按其组id排序。

• bool ParameterBlockOrdering::AddElementToGroup(const double *element, const int group)¶

  Add an element to a group. If a group with this id does not exist, one is created. This method can be called any number of times for the same element. Group ids should be non-negative numbers. Return value indicates if adding the element was a success.

  向组中添加元素。如果不存在具有此id的组，则会创建一个组。对于同一个元素，可以多次调用此方法。组ID应该是非负数。返回值指示添加元素是否成功。

• void ParameterBlockOrdering::Clear()¶

  Clear the ordering.

  清除命令。

• bool ParameterBlockOrdering::Remove(const double *element)¶

  Remove the element, no matter what group it is in. If the element is not a member of any group, calling this method will result in a crash. Return value indicates if the element was actually removed.

  移除该元素，无论它在哪个组中。如果元素不是任何组的成员，调用此方法将导致崩溃。返回值指示元素是否已实际删除。

• void ParameterBlockOrdering::Reverse()¶

  Reverse the order of the groups in place.

  颠倒分组顺序。

• int ParameterBlockOrdering::GroupId(const double *element) const¶

  Return the group id for the element. If the element is not a member of any group, return -1.

  返回元素的组id。如果元素不是任何组的成员，则返回-1。

• bool ParameterBlockOrdering::IsMember(const double *element) const¶

  True if there is a group containing the parameter block.

  如果存在包含参数块的组，则为True。

• int ParameterBlockOrdering::GroupSize(const int group) const¶

  This function always succeeds, i.e., implicitly there exists a group for every integer.

  这个函数总是成功的，也就是说，每个整数隐式地存在一个组。

• int ParameterBlockOrdering::NumElements() const¶

  Number of elements in the ordering.

  排序中的元素数。

• int ParameterBlockOrdering::NumGroups() const¶

  Number of groups with one or more elements.

  包含一个或多个元素的组数。

代码实战

ceres::ParameterBlockOrdering* ordering = new ceres::ParameterBlockOrdering();
 
// set all points in ordering to 0
for(int i = 0; i < num_points; i++){
    ordering->AddElementToGroup(points + i * point_block_size, 0);
}
// set all cameras in ordering to 1
for(int i = 0; i < num_cameras; i++){
    ordering->AddElementToGroup(cameras + i * camera_block_size, 1);
}