GoogleGit

blob: 6a5a68924f0fdce6a5fbf31c14b62fcd7af7f7da [file] [log] [blame]
  1. // Ceres Solver - A fast non-linear least squares minimizer
  2. // Copyright 2014 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: keir@google.com (Keir Mierle)
  30. // sameeragarwal@google.com (Sameer Agarwal)
  31. #ifndef CERES_PUBLIC_LOCAL_PARAMETERIZATION_H_
  32. #define CERES_PUBLIC_LOCAL_PARAMETERIZATION_H_
  33. #include <vector>
  34. #include "ceres/internal/port.h"
  35. #include "ceres/internal/disable_warnings.h"
  36. namespace ceres {
  37. // Purpose: Sometimes parameter blocks x can overparameterize a problem
  38. //
  39. // min f(x)
  40. // x
  41. //
  42. // In that case it is desirable to choose a parameterization for the
  43. // block itself to remove the null directions of the cost. More
  44. // generally, if x lies on a manifold of a smaller dimension than the
  45. // ambient space that it is embedded in, then it is numerically and
  46. // computationally more effective to optimize it using a
  47. // parameterization that lives in the tangent space of that manifold
  48. // at each point.
  49. //
  50. // For example, a sphere in three dimensions is a 2 dimensional
  51. // manifold, embedded in a three dimensional space. At each point on
  52. // the sphere, the plane tangent to it defines a two dimensional
  53. // tangent space. For a cost function defined on this sphere, given a
  54. // point x, moving in the direction normal to the sphere at that point
  55. // is not useful. Thus a better way to do a local optimization is to
  56. // optimize over two dimensional vector delta in the tangent space at
  57. // that point and then "move" to the point x + delta, where the move
  58. // operation involves projecting back onto the sphere. Doing so
  59. // removes a redundent dimension from the optimization, making it
  60. // numerically more robust and efficient.
  61. //
  62. // More generally we can define a function
  63. //
  64. // x_plus_delta = Plus(x, delta),
  65. //
  66. // where x_plus_delta has the same size as x, and delta is of size
  67. // less than or equal to x. The function Plus, generalizes the
  68. // definition of vector addition. Thus it satisfies the identify
  69. //
  70. // Plus(x, 0) = x, for all x.
  71. //
  72. // A trivial version of Plus is when delta is of the same size as x
  73. // and
  74. //
  75. // Plus(x, delta) = x + delta
  76. //
  77. // A more interesting case if x is two dimensional vector, and the
  78. // user wishes to hold the first coordinate constant. Then, delta is a
  79. // scalar and Plus is defined as
  80. //
  81. // Plus(x, delta) = x + [0] * delta
  82. // [1]
  83. //
  84. // An example that occurs commonly in Structure from Motion problems
  85. // is when camera rotations are parameterized using Quaternion. There,
  86. // it is useful only make updates orthogonal to that 4-vector defining
  87. // the quaternion. One way to do this is to let delta be a 3
  88. // dimensional vector and define Plus to be
  89. //
  90. // Plus(x, delta) = [cos(|delta|), sin(|delta|) delta / |delta|] * x
  91. //
  92. // The multiplication between the two 4-vectors on the RHS is the
  93. // standard quaternion product.
  94. //
  95. // Given g and a point x, optimizing f can now be restated as
  96. //
  97. // min f(Plus(x, delta))
  98. // delta
  99. //
  100. // Given a solution delta to this problem, the optimal value is then
  101. // given by
  102. //
  103. // x* = Plus(x, delta)
  104. //
  105. // The class LocalParameterization defines the function Plus and its
  106. // Jacobian which is needed to compute the Jacobian of f w.r.t delta.
  107. class CERES_EXPORT LocalParameterization {
  108. public:
  109. virtual ~LocalParameterization();
  110. // Generalization of the addition operation,
  111. //
  112. // x_plus_delta = Plus(x, delta)
  113. //
  114. // with the condition that Plus(x, 0) = x.
  115. virtual bool Plus(const double* x,
  116. const double* delta,
  117. double* x_plus_delta) const = 0;
  118. // The jacobian of Plus(x, delta) w.r.t delta at delta = 0.
  119. //
  120. // jacobian is a row-major GlobalSize() x LocalSize() matrix.
  121. virtual bool ComputeJacobian(const double* x, double* jacobian) const = 0;
  122. // local_matrix = global_matrix * jacobian
  123. //
  124. // global_matrix is a num_rows x GlobalSize row major matrix.
  125. // local_matrix is a num_rows x LocalSize row major matrix.
  126. // jacobian(x) is the matrix returned by ComputeJacobian at x.
  127. //
  128. // This is only used by GradientProblem. For most normal uses, it is
  129. // okay to use the default implementation.
  130. virtual bool MultiplyByJacobian(const double* x,
  131. const int num_rows,
  132. const double* global_matrix,
  133. double* local_matrix) const;
  134. // Size of x.
  135. virtual int GlobalSize() const = 0;
  136. // Size of delta.
  137. virtual int LocalSize() const = 0;
  138. };
  139. // Some basic parameterizations
  140. // Identity Parameterization: Plus(x, delta) = x + delta
  141. class CERES_EXPORT IdentityParameterization : public LocalParameterization {
  142. public:
  143. explicit IdentityParameterization(int size);
  144. virtual ~IdentityParameterization() {}
  145. virtual bool Plus(const double* x,
  146. const double* delta,
  147. double* x_plus_delta) const;
  148. virtual bool ComputeJacobian(const double* x,
  149. double* jacobian) const;
  150. virtual bool MultiplyByJacobian(const double* x,
  151. const int num_cols,
  152. const double* global_matrix,
  153. double* local_matrix) const;
  154. virtual int GlobalSize() const { return size_; }
  155. virtual int LocalSize() const { return size_; }
  156. private:
  157. const int size_;
  158. };
  159. // Hold a subset of the parameters inside a parameter block constant.
  160. class CERES_EXPORT SubsetParameterization : public LocalParameterization {
  161. public:
  162. explicit SubsetParameterization(int size,
  163. const std::vector<int>& constant_parameters);
  164. virtual ~SubsetParameterization() {}
  165. virtual bool Plus(const double* x,
  166. const double* delta,
  167. double* x_plus_delta) const;
  168. virtual bool ComputeJacobian(const double* x,
  169. double* jacobian) const;
  170. virtual bool MultiplyByJacobian(const double* x,
  171. const int num_cols,
  172. const double* global_matrix,
  173. double* local_matrix) const;
  174. virtual int GlobalSize() const {
  175. return static_cast<int>(constancy_mask_.size());
  176. }
  177. virtual int LocalSize() const { return local_size_; }
  178. private:
  179. const int local_size_;
  180. std::vector<int> constancy_mask_;
  181. };
  182. // Plus(x, delta) = [cos(|delta|), sin(|delta|) delta / |delta|] * x
  183. // with * being the quaternion multiplication operator. Here we assume
  184. // that the first element of the quaternion vector is the real (cos
  185. // theta) part.
  186. class CERES_EXPORT QuaternionParameterization : public LocalParameterization {
  187. public:
  188. virtual ~QuaternionParameterization() {}
  189. virtual bool Plus(const double* x,
  190. const double* delta,
  191. double* x_plus_delta) const;
  192. virtual bool ComputeJacobian(const double* x,
  193. double* jacobian) const;
  194. virtual int GlobalSize() const { return 4; }
  195. virtual int LocalSize() const { return 3; }
  196. };
  197. } // namespace ceres
  198. #include "ceres/internal/reenable_warnings.h"
  199. #endif // CERES_PUBLIC_LOCAL_PARAMETERIZATION_H_