[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [57133] trunk/blender: Motion tracking: automatic keyframe selection
Sergey Sharybin
sergey.vfx at gmail.com
Thu May 30 11:03:50 CEST 2013
Revision: 57133
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=57133
Author: nazgul
Date: 2013-05-30 09:03:49 +0000 (Thu, 30 May 2013)
Log Message:
-----------
Motion tracking: automatic keyframe selection
Implements an automatic keyframe selection algorithm which uses
couple of approaches to find out best keyframes candidates:
- First, slightly modifier Pollefeys's criteria is used, which
limits correspondence ration from 80% to 100%. This allows to
reject keyframe candidate early without doing heavy math in
cases there're not much common features with first keyframe.
- Second step is based on Geometric Robust Information Criteria
(aka GRIC), which checks whether features motion between
candidate keyframes is better defined by homography or
fundamental matrices.
To be a good keyframe candidate, fundamental matrix need to
define motion better than homography (in this case F-GRIC will
be smaller than H-GRIC).
This two criteria are well described in this paper:
http://www.cs.ait.ac.th/~mdailey/papers/Tahir-KeyFrame.pdf
- Final step is based on estimating reconstruction error of
a full-scene solution using candidate keyframes. This part
is based on the following paper:
ftp://ftp.tnt.uni-hannover.de/pub/papers/2004/ECCV2004-TTHBAW.pdf
This step requires reconstruction using candidate keyframes
and obtaining covariance matrix of 3D points positions.
Reconstruction was done pretty much straightforward using
other simple pipeline routines, and for covariance estimation
pseudo-inverse of Hessian is used, which is in this case
(J^T * J)+, where + denotes pseudo-inverse.
Jacobian matrix is estimating using Ceres evaluate API.
This is also crucial to get rid of possible gauge ambiguity,
which is in our case made by zero-ing 7 (by gauge freedoms
number) eigen values in pseudo-inverse.
There're still room for improving and optimizing the code,
but we need some point to start with anyway :)
Thanks to Keir Mierle and Sameer Agarwal who assisted a lot
to make this feature working.
Modified Paths:
--------------
trunk/blender/extern/libmv/CMakeLists.txt
trunk/blender/extern/libmv/files.txt
trunk/blender/extern/libmv/libmv-capi.cc
trunk/blender/extern/libmv/libmv-capi.h
trunk/blender/release/scripts/startup/bl_ui/space_clip.py
trunk/blender/source/blender/blenkernel/intern/tracking.c
trunk/blender/source/blender/makesdna/DNA_tracking_types.h
trunk/blender/source/blender/makesrna/intern/rna_tracking.c
Added Paths:
-----------
trunk/blender/extern/libmv/libmv/simple_pipeline/keyframe_selection.cc
trunk/blender/extern/libmv/libmv/simple_pipeline/keyframe_selection.h
Modified: trunk/blender/extern/libmv/CMakeLists.txt
===================================================================
--- trunk/blender/extern/libmv/CMakeLists.txt 2013-05-30 02:16:22 UTC (rev 57132)
+++ trunk/blender/extern/libmv/CMakeLists.txt 2013-05-30 09:03:49 UTC (rev 57133)
@@ -67,6 +67,7 @@
libmv/simple_pipeline/detect.cc
libmv/simple_pipeline/initialize_reconstruction.cc
libmv/simple_pipeline/intersect.cc
+ libmv/simple_pipeline/keyframe_selection.cc
libmv/simple_pipeline/modal_solver.cc
libmv/simple_pipeline/pipeline.cc
libmv/simple_pipeline/reconstruction.cc
@@ -125,6 +126,7 @@
libmv/simple_pipeline/detect.h
libmv/simple_pipeline/initialize_reconstruction.h
libmv/simple_pipeline/intersect.h
+ libmv/simple_pipeline/keyframe_selection.h
libmv/simple_pipeline/modal_solver.h
libmv/simple_pipeline/pipeline.h
libmv/simple_pipeline/reconstruction.h
Modified: trunk/blender/extern/libmv/files.txt
===================================================================
--- trunk/blender/extern/libmv/files.txt 2013-05-30 02:16:22 UTC (rev 57132)
+++ trunk/blender/extern/libmv/files.txt 2013-05-30 09:03:49 UTC (rev 57133)
@@ -46,6 +46,8 @@
libmv/simple_pipeline/initialize_reconstruction.h
libmv/simple_pipeline/intersect.cc
libmv/simple_pipeline/intersect.h
+libmv/simple_pipeline/keyframe_selection.cc
+libmv/simple_pipeline/keyframe_selection.h
libmv/simple_pipeline/modal_solver.cc
libmv/simple_pipeline/modal_solver.h
libmv/simple_pipeline/pipeline.cc
Added: trunk/blender/extern/libmv/libmv/simple_pipeline/keyframe_selection.cc
===================================================================
--- trunk/blender/extern/libmv/libmv/simple_pipeline/keyframe_selection.cc (rev 0)
+++ trunk/blender/extern/libmv/libmv/simple_pipeline/keyframe_selection.cc 2013-05-30 09:03:49 UTC (rev 57133)
@@ -0,0 +1,579 @@
+// Copyright (c) 2012 libmv authors.
+//
+// Permission is hereby granted, free of charge, to any person obtaining a copy
+// of this software and associated documentation files (the "Software"), to
+// deal in the Software without restriction, including without limitation the
+// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
+// sell copies of the Software, and to permit persons to whom the Software is
+// furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
+// IN THE SOFTWARE.
+
+#include "libmv/simple_pipeline/keyframe_selection.h"
+
+#include "libmv/numeric/numeric.h"
+#include "ceres/ceres.h"
+#include "libmv/logging/logging.h"
+#include "libmv/multiview/homography.h"
+#include "libmv/multiview/fundamental.h"
+#include "libmv/simple_pipeline/intersect.h"
+#include "libmv/simple_pipeline/bundle.h"
+
+#include <Eigen/Eigenvalues>
+
+namespace libmv {
+namespace {
+
+Vec2 NorrmalizedToPixelSpace(Vec2 vec, const CameraIntrinsics &intrinsics) {
+ Vec2 result;
+
+ double focal_length_x = intrinsics.focal_length_x();
+ double focal_length_y = intrinsics.focal_length_y();
+
+ double principal_point_x = intrinsics.principal_point_x();
+ double principal_point_y = intrinsics.principal_point_y();
+
+ result(0) = vec(0) * focal_length_x + principal_point_x;
+ result(1) = vec(1) * focal_length_y + principal_point_y;
+
+ return result;
+}
+
+Mat3 IntrinsicsNormalizationMatrix(const CameraIntrinsics &intrinsics) {
+ Mat3 T = Mat3::Identity(), S = Mat3::Identity();
+
+ T(0, 2) = -intrinsics.principal_point_x();
+ T(1, 2) = -intrinsics.principal_point_y();
+
+ S(0, 0) /= intrinsics.focal_length_x();
+ S(1, 1) /= intrinsics.focal_length_y();
+
+ return S * T;
+}
+
+class HomographySymmetricGeometricCostFunctor {
+ public:
+ HomographySymmetricGeometricCostFunctor(Vec2 x, Vec2 y)
+ : x_(x), y_(y) { }
+
+ template<typename T>
+ bool operator()(const T *homography_parameters, T *residuals) const {
+ typedef Eigen::Matrix<T, 3, 3> Mat3;
+ typedef Eigen::Matrix<T, 3, 1> Vec3;
+
+ Mat3 H(homography_parameters);
+
+ Vec3 x(T(x_(0)), T(x_(1)), T(1.0));
+ Vec3 y(T(y_(0)), T(y_(1)), T(1.0));
+
+ Vec3 H_x = H * x;
+ Vec3 Hinv_y = H.inverse() * y;
+
+ H_x /= H_x(2);
+ Hinv_y /= Hinv_y(2);
+
+ residuals[0] = H_x(0) - T(y_(0));
+ residuals[1] = H_x(1) - T(y_(1));
+
+ residuals[2] = Hinv_y(0) - T(x_(0));
+ residuals[3] = Hinv_y(1) - T(x_(1));
+
+ return true;
+ }
+
+ const Vec2 x_;
+ const Vec2 y_;
+};
+
+void ComputeHomographyFromCorrespondences(const Mat &x1, const Mat &x2,
+ CameraIntrinsics &intrinsics,
+ Mat3 *H) {
+ // Algebraic homography estimation, happens with normalized coordinates
+ Homography2DFromCorrespondencesLinear(x1, x2, H, 1e-12);
+
+ // Refine matrix using Ceres minimizer
+
+ // TODO(sergey): look into refinement in pixel space.
+ ceres::Problem problem;
+
+ for (int i = 0; i < x1.cols(); i++) {
+ HomographySymmetricGeometricCostFunctor
+ *homography_symmetric_geometric_cost_function =
+ new HomographySymmetricGeometricCostFunctor(x1.col(i),
+ x2.col(i));
+
+ problem.AddResidualBlock(
+ new ceres::AutoDiffCostFunction<
+ HomographySymmetricGeometricCostFunctor,
+ 4, /* num_residuals */
+ 9>(homography_symmetric_geometric_cost_function),
+ NULL,
+ H->data());
+ }
+
+ // Configure the solve.
+ ceres::Solver::Options solver_options;
+ solver_options.linear_solver_type = ceres::DENSE_QR;
+ solver_options.max_num_iterations = 50;
+ solver_options.update_state_every_iteration = true;
+ solver_options.parameter_tolerance = 1e-16;
+ solver_options.function_tolerance = 1e-16;
+
+ // Run the solve.
+ ceres::Solver::Summary summary;
+ ceres::Solve(solver_options, &problem, &summary);
+
+ VLOG(1) << "Summary:\n" << summary.FullReport();
+
+ // Convert homography to original pixel space
+ Mat3 N = IntrinsicsNormalizationMatrix(intrinsics);
+ *H = N.inverse() * (*H) * N;
+}
+
+class FundamentalSymmetricEpipolarCostFunctor {
+ public:
+ FundamentalSymmetricEpipolarCostFunctor(Vec2 x, Vec2 y)
+ : x_(x), y_(y) {}
+
+ template<typename T>
+ bool operator()(const T *fundamental_parameters, T *residuals) const {
+ typedef Eigen::Matrix<T, 3, 3> Mat3;
+ typedef Eigen::Matrix<T, 3, 1> Vec3;
+
+ Mat3 F(fundamental_parameters);
+
+ Vec3 x(T(x_(0)), T(x_(1)), T(1.0));
+ Vec3 y(T(y_(0)), T(y_(1)), T(1.0));
+
+ Vec3 F_x = F * x;
+ Vec3 Ft_y = F.transpose() * y;
+ T y_F_x = y.dot(F_x);
+
+ residuals[0] = y_F_x * T(1) / F_x.head(2).norm();
+ residuals[1] = y_F_x * T(1) / Ft_y.head(2).norm();
+
+ return true;
+ }
+
+ const Mat x_;
+ const Mat y_;
+};
+
+void ComputeFundamentalFromCorrespondences(const Mat &x1, const Mat &x2,
+ CameraIntrinsics &intrinsics,
+ Mat3 *F) {
+ // Algebraic fundamental estimation, happens with normalized coordinates
+ NormalizedEightPointSolver(x1, x2, F);
+
+ // Refine matrix using Ceres minimizer
+
+ // TODO(sergey): look into refinement in pixel space.
+ ceres::Problem problem;
+
+ for (int i = 0; i < x1.cols(); i++) {
+ FundamentalSymmetricEpipolarCostFunctor
+ *fundamental_symmetric_epipolar_cost_function =
+ new FundamentalSymmetricEpipolarCostFunctor(x1.col(i),
+ x2.col(i));
+
+ problem.AddResidualBlock(
+ new ceres::AutoDiffCostFunction<
+ FundamentalSymmetricEpipolarCostFunctor,
+ 2, /* num_residuals */
+ 9>(fundamental_symmetric_epipolar_cost_function),
+ NULL,
+ F->data());
+ }
+
+ // Configure the solve.
+ ceres::Solver::Options solver_options;
+ solver_options.linear_solver_type = ceres::DENSE_NORMAL_CHOLESKY;
+ solver_options.max_num_iterations = 50;
+ solver_options.update_state_every_iteration = true;
+ solver_options.parameter_tolerance = 1e-16;
+ solver_options.function_tolerance = 1e-16;
+
+ // Run the solve.
+ ceres::Solver::Summary summary;
+ ceres::Solve(solver_options, &problem, &summary);
+
+ VLOG(1) << "Summary:\n" << summary.FullReport();
+
+ // Convert fundamental to original pixel space
+ Mat3 N = IntrinsicsNormalizationMatrix(intrinsics);
+ *F = N.inverse() * (*F) * N;
+}
+
+// P.H.S. Torr
+// Geometric Motion Segmentation and Model Selection
+//
+// http://reference.kfupm.edu.sa/content/g/e/geometric_motion_segmentation_and_model__126445.pdf
+//
+// d is the number of dimensions modeled
+// (d = 3 for a fundamental matrix or 2 for a homography)
+// k is the number of degrees of freedom in the model
+// (k = 7 for a fundamental matrix or 8 for a homography)
+// r is the dimension of the data
+// (r = 4 for 2D correspondences between two frames)
+double GRIC(const Vec &e, int d, int k, int r) {
+ int n = e.rows();
+ double lambda1 = log(static_cast<double>(r));
+ double lambda2 = log(static_cast<double>(r * n));
+
+ // lambda3 limits the residual error, and this paper
+ // http://elvera.nue.tu-berlin.de/files/0990Knorr2006.pdf
+ // suggests using lambda3 of 2
+ // same value is used in Torr's Problem of degeneracy in structure
+ // and motion recovery from uncalibrated image sequences
+ // http://www.robots.ox.ac.uk/~vgg/publications/papers/torr99.ps.gz
+ double lambda3 = 2.0;
+
+ // measurement error of tracker
+ double sigma2 = 0.01;
+
+ // Actual GRIC computation
+ double gric_result = 0.0;
+
+ for (int i = 0; i < n; i++) {
+ double rho = std::min(e(i) * e(i) / sigma2, lambda3 * (r - d));
+ gric_result += rho;
+ }
+
+ gric_result += lambda1 * d * n;
+ gric_result += lambda2 * k;
+
+ return gric_result;
+}
+
+// Compute a generalized inverse using eigen value decomposition.
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list