Documentation changes. 1. Add documentation for cubic_interpolation.h 2. Remove the list of publications. It is an incomplete list which is a pain to maintain. 3. Add a note about the interaction between manifolds and NumericDiffCostFunction. 4. Fix some of the comments in cubic_interpolation.h to better reflect reality. 5. Updated the version history. Change-Id: I0b4a5a6f3361d3fc85f1b4aec685cd80540934f1
diff --git a/docs/source/bibliography.rst b/docs/source/bibliography.rst index bd99758..bab6e61 100644 --- a/docs/source/bibliography.rst +++ b/docs/source/bibliography.rst
@@ -44,6 +44,10 @@ with indeterminacy**, *IEEE Transactions on Information Theory* 47(5):2017-2028, 2001. +.. [Keys] R. G. Keys, **Cubic convolution interpolation for digital + image processing**, *IEEE Trans. on Acoustics, Speech, and Signal + Processing*, 29(6), 1981. + .. [KushalAgarwal] A. Kushal and S. Agarwal, **Visibility based preconditioning for bundle adjustment**, *In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition*, 2012.
diff --git a/docs/source/nnls_modeling.rst b/docs/source/nnls_modeling.rst index 37f7c59..f9e9de6 100644 --- a/docs/source/nnls_modeling.rst +++ b/docs/source/nnls_modeling.rst
@@ -67,8 +67,8 @@ :math:`f_i\left(x_{i_1},...,x_{i_k}\right)` and the matrices .. math:: J_{ij} = \frac{\partial}{\partial - x_{i_j}}f_i\left(x_{i_1},...,x_{i_k}\right),\quad \forall j - \in \{1, \ldots, k\} + x_{i_j}}f_i\left(x_{i_1},...,x_{i_k}\right),\quad \forall j + \in \{1, \ldots, k\} .. class:: CostFunction @@ -495,6 +495,39 @@ argument. Please be careful when setting the size parameters. +Numeric Differentiation & LocalParameterization +----------------------------------------------- + + If your cost function depends on a parameter block that must lie on + a manifold and the functor cannot be evaluated for values of that + parameter block not on the manifold then you may have problems + numerically differentiating such functors. + + This is because numeric differentiation in Ceres is performed by + perturbing the individual coordinates of the parameter blocks that + a cost functor depends on. In doing so, we assume that the + parameter blocks live in an Euclidean space and ignore the + structure of manifold that they live As a result some of the + perturbations may not lie on the manifold corresponding to the + parameter block. + + For example consider a four dimensional parameter block that is + interpreted as a unit Quaternion. Perturbing the coordinates of + this parameter block will violate the unit norm property of the + parameter block. + + Fixing this problem requires that :class:`NumericDiffCostFunction` + be aware of the :class:`LocalParameterization` associated with each + parameter block and only generate perturbations in the local + tangent space of each parameter block. + + For now this is not considered to be a serious enough problem to + warrant changing the :class:`NumericDiffCostFunction` API. Further, + in most cases it is relatively straightforward to project a point + off the manifold back onto the manifold before using it in the + functor. For example in case of the Quaternion, normalizing the + 4-vector before using it does the trick. + **Alternate Interface** For a variety of reason, including compatibility with legacy code, @@ -571,6 +604,10 @@ As a rule of thumb, try using :class:`NumericDiffCostFunction` before you use :class:`DynamicNumericDiffCostFunction`. + **WARNING** The same caution about mixing local parameterizations + with numeric differentiation applies as is the case with + :class:`NumericDiffCostFunction``. + :class:`CostFunctionToFunctor` ============================== @@ -1686,3 +1723,121 @@ .. function:: void AngleAxisRotatePoint<T>(const T angle_axis[3], const T pt[3], T result[3]) .. math:: y = R(\text{angle_axis}) x + + +Cubic Interpolation +=================== + +Optimization problems often involve functions that are given in the +form of a table of values, for example an image. Evaluating these +functions and their derivatives requires interpolating these +values. Interpolating tabulated functions is a vast area of research +and there are a lot of libraries which implement a variety of +interpolation schemes. However, using them within the automatic +differentiation framework in Ceres is quite painful. To this end, +Ceres provides the ability to interpolate one dimensional and two +dimensional tabular functions. + +The one dimensional interpolation is based on the Cubic Hermite +Spline, also known as the Catmull-Rom Spline. This produces a first +order differentiable interpolating function. The two dimensional +interpolation scheme is a generalization of the one dimensional scheme +where the interpolating function is assumed to be separable in the two +dimensions, + +More details of the construction can be found `Linear Methods for +Image Interpolation <http://www.ipol.im/pub/art/2011/g_lmii/>`_ by +Pascal Getreuer. + +.. class:: CubicInterpolator + +Given as input a one dimensional array like object, which provides +the following interface. + +.. code:: + + struct Array { + enum { DATA_DIMENSION = 2; }; + void GetValue(int n, double* f) const; + int NumValues() const; + }; + +Where, ``GetValue`` gives us the value of a function :math:`f` +(possibly vector valued) on the integers :code:`{0, ..., NumValues() - +1}` and the enum ``DATA_DIMENSION`` indicates the dimensionality of +the function being interpolated. For example if you are interpolating +a color image with three channels (Red, Green & Blue), then +``DATA_DIMENSION = 3``. + +:class:`CubicInterpolator` uses Cubic Hermite splines to produce a +smooth approximation to it that can be used to evaluate the +:math:`f(x)` and :math:`f'(x)` at any real valued point in the +interval :code:`[0, NumValues() - 1]`. For example, the following code +interpolates an array of four numbers. + +.. code:: + + const double data[] = {1.0, 2.0, 5.0, 6.0}; + Array1D<double, 1> array(x, 4); + CubicInterpolator interpolator(array); + double f, dfdx; + CHECK(interpolator.Evaluate(1.5, &f, &dfdx)); + + +In the above code we use ``Array1D`` a templated helper class that +allows easy interfacing between ``C++`` arrays and +:class:`CubicInterpolator`. + +``Array1D`` supports vector valued functions where the various +coordinates of the function can be interleaved or stacked. It also +allows the use of any numeric type as input, as long as it can be +safely cast to a double. + +.. class:: BiCubicInterpolator + +Given as input a two dimensional array like object, which provides +the following interface: + +.. code:: + + struct Array { + enum { DATA_DIMENSION = 1 }; + void GetValue(int row, int col, double* f) const; + int NumRows() const; + int NumCols() const; + }; + +Where, ``GetValue`` gives us the value of a function :math:`f` +(possibly vector valued) on the integer grid :code:`{0, ..., +NumRows() - 1} x {0, ..., NumCols() - 1}` and the enum +``DATA_DIMENSION`` indicates the dimensionality of the function being +interpolated. For example if you are interpolating a color image with +three channels (Red, Green & Blue), then ``DATA_DIMENSION = 3``. + +:class:`BiCubicInterpolator` uses the cubic convolution interpolation +algorithm of R. Keys [Keys]_, to produce a smooth approximation to it +that can be used to evaluate the :math:`f(r,c)`, :math:`\frac{\partial +f(r,c)}{\partial r}` and :math:`\frac{\partial f(r,c)}{\partial c}` at +any real valued point in the quad :code:`[0, NumRows() - 1] x [0, +NumCols() - 1]`. + +For example the following code interpolates a two dimensional array. + +.. code:: + + const double data[] = {1.0, 3.0, -1.0, 4.0, + 3.6, 2.1, 4.2, 2.0, + 2.0, 1.0, 3.1, 5.2}; + Array2D<double, 1> array(data, 3, 4); + BiCubicInterpolator interpolator(array); + double f, dfdr, dfdc; + CHECK(interpolator.Evaluate(1.2, 2.5, &f, &dfdr, &dfdc)); + +In the above code, the templated helper class ``Array2D`` is used to +make a ``C++`` array look like a two dimensional table to +:class:`BiCubicInterpolator`. + +``Array2D`` supports row or column major layouts. It also supports +vector valued functions where the individual coordinates of the +function may be interleaved or stacked. It also allows the use of any +numeric type as input, as long as it can be safely cast to double.
diff --git a/docs/source/users.rst b/docs/source/users.rst index d04927d..20f0e18 100644 --- a/docs/source/users.rst +++ b/docs/source/users.rst
@@ -48,29 +48,3 @@ .. _calibrating robot-camera systems: http://rosindustrial.org/news/2014/9/24/industrial-calibration-library-update-and-presentation .. _skinned control meshes: http://research.microsoft.com/en-us/projects/handmodelingfrommonoculardepth/ - - -Publications -============ - -Ceres Solver is used (and cited) in the following publications: - -#. **User-Specific Hand Modeling from Monocular Depth - Sequences**, J. Taylor, R. Stebbing, V. Ramakrishna, C. Keskin, J. Shotton, S. Izadi, A. Hertzmann, - and A. Fitzgibbon, CVPR 2014. - -#. **Global Fusion of Relative Motions for Robust, Accurate and - Scalable Structure from Motion**, P. Moulon, P. Monasse - and R. Marlet, ICCV 2013. - -#. **Recurrent neural networks for voice activity - detection**, T. Hughes and K. Mierle, ICASSP 2013. - -#. **Street View Motion-from-Structure-from-Motion**, B. Klingner, D. Martin - and J. Roseborough, ICCV 2013. - -#. **Adaptive Structure from Motion with a contrario model - estimation**, P. Moulon, P. Monasse and R. Marlet, ACCV 2012. - -#. **Visibility based preconditioning for bundle - adjustment**, A. Kushal and S. Agarwal, CVPR 2012.
diff --git a/docs/source/version_history.rst b/docs/source/version_history.rst index f666fb5..f9e9c7b 100644 --- a/docs/source/version_history.rst +++ b/docs/source/version_history.rst
@@ -12,15 +12,43 @@ #. Added ``CubicInterpolator`` and ``BiCubicInterpolator`` to allow smooth interpolation of sampled functions and integration with automatic differentiation. +#. Add method to return covariance in tangent space. (Michael Vitus & + Steve Hsu) +#. Add Homogeneous vector parameterization. (Michael Vitus) -Bug Fixes ---------- +Bug Fixes & Minor Changes +------------------------- +#. Rename macros in the public API to have a ``CERES_`` prefix. +#. Fix ``OrderedGroup::Reverse()`` when it is empty. +#. Update the code to point to ceres-solver.org. +#. Update documentation to point to the GitHub issue tracker. +#. Disable ``LAPACK`` for iOS builds. (Greg Coombe) +#. Force use of single-thread in ``Problem::Evaluate()`` without OpenMP. +#. Less strict check for multithreading. (Chris Sweeney) +#. Update tolerances in small_blas_test.cc (Philipp Hubner) +#. Documentation corrections (Steve Hsu) +#. Fixed ``sampled_function.cc`` (Pablo Speciale) +#. Fix example code in the documentation. (Rodney Hoskinson) +#. Improve the error handling in Conjugate Gradients. +#. Improve preconditioner documentation. +#. Remove dead code from fpclassify.h. +#. Make Android.mk threads sensitive. +#. Changed the ``CURRENT_CONFIG_INSTALL_DIR`` to be a variable local + to Ceres. (Chris Sweeney) +#. Fix typo in the comments in ``Jet.h``. (Julius Ziegler) +#. Add the ASL at ETH Zurich to the list of users. +#. Fixed a typo in the documentation. (Richard Stebbing) +#. Fixed a boundary handling bug in the BiCubic interpolation + code. (Bernhard Zeisl) +#. Fixed a ``MSVC`` compilation bug in the cubic interpolation code + (Johannes Schönberger) #. Add covariance related files to the Android build. #. Update Ubuntu 14.04 installation instructions. (Filippo Basso) #. Improved logging for linear solver failures. #. Improved crash messages in ``Problem``. #. Hide Homebrew related variables in CMake GUI. -#. Add SuiteSparse link dependency for compressed_col_sparse_matrix_utils_test. +#. Add SuiteSparse link dependency for + compressed_col_sparse_matrix_utils_test. #. Autodetect Homebrew install prefix on OSX. #. Lint changes from William Rucklidge and Jim Roseborough. #. Remove ``using namespace std:`` from ``port.h``
diff --git a/include/ceres/cubic_interpolation.h b/include/ceres/cubic_interpolation.h index 5f3e183..9e63d01 100644 --- a/include/ceres/cubic_interpolation.h +++ b/include/ceres/cubic_interpolation.h
@@ -122,9 +122,9 @@ // // Example usage: // -// const double x[] = {1.0, 2.0, 5.0, 6.0}; -// Array1D data(x, 4); -// CubicInterpolator interpolator(data); +// const double data[] = {1.0, 2.0, 5.0, 6.0}; +// Array1D<double, 1> array(x, 4); +// CubicInterpolator<Array1D<double, 1> > interpolator(array); // double f, dfdx; // CHECK(interpolator.Evaluator(1.5, &f, &dfdx)); template<typename Array> @@ -243,6 +243,17 @@ // // http://en.wikipedia.org/wiki/Cubic_Hermite_spline // http://en.wikipedia.org/wiki/Bicubic_interpolation +// +// Example usage: +// +// const double data[] = {1.0, 3.0, -1.0, 4.0, +// 3.6, 2.1, 4.2, 2.0, +// 2.0, 1.0, 3.1, 5.2}; +// Array2D<double, 1> array(data, 3, 4); +// BiCubicInterpolator<Array2D<double, 1> > interpolator(array); +// double f, dfdr, dfdc; +// CHECK(interpolator.Evaluate(1.2, 2.5, &f, &dfdr, &dfdc)); + template<typename Array> class CERES_EXPORT BiCubicInterpolator { public: