[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [52857] branches/soc-2011-tomato: Motion tracking: automatic keyframe selection

Sergey Sharybin sergey.vfx at gmail.com
Mon Dec 10 17:38:59 CET 2012


Revision: 52857
          http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=52857
Author:   nazgul
Date:     2012-12-10 16:38:58 +0000 (Mon, 10 Dec 2012)
Log Message:
-----------
Motion tracking: automatic keyframe selection

This commit contains implementation of automatic keyframe selection algorithm
based on Pollefeys's criteria (F-GRIC is smaller than H-GRIC and correspondence
ratio is more then 90%). It is implemented as a part of simple pipeline and
returns vector of keyframe images for a given Tracks structure.

For simple pipeline reconstruction two best keyframes are selecting from list
of all possible keyframes. Criteria for this selection is reprojection error
of solution from two candidate keyfames.

In Blender side added an option in Solve panel to enable Keyframe Selection.
If this option enabled, libmv will detect two best keyframes and use them for
solution. This keyframes will be set back to the interface when solution is
done.

Modified Paths:
--------------
    branches/soc-2011-tomato/extern/libmv/CMakeLists.txt
    branches/soc-2011-tomato/extern/libmv/libmv/multiview/fundamental.h
    branches/soc-2011-tomato/extern/libmv/libmv/simple_pipeline/initialize_reconstruction.cc
    branches/soc-2011-tomato/extern/libmv/libmv/simple_pipeline/tracks.cc
    branches/soc-2011-tomato/extern/libmv/libmv/simple_pipeline/tracks.h
    branches/soc-2011-tomato/extern/libmv/libmv-capi.cpp
    branches/soc-2011-tomato/extern/libmv/libmv-capi.h
    branches/soc-2011-tomato/release/scripts/startup/bl_ui/space_clip.py
    branches/soc-2011-tomato/source/blender/blenkernel/intern/tracking.c
    branches/soc-2011-tomato/source/blender/makesdna/DNA_tracking_types.h
    branches/soc-2011-tomato/source/blender/makesrna/intern/rna_tracking.c

Added Paths:
-----------
    branches/soc-2011-tomato/extern/libmv/libmv/simple_pipeline/keyframe_selection.cc
    branches/soc-2011-tomato/extern/libmv/libmv/simple_pipeline/keyframe_selection.h

Modified: branches/soc-2011-tomato/extern/libmv/CMakeLists.txt
===================================================================
--- branches/soc-2011-tomato/extern/libmv/CMakeLists.txt	2012-12-10 16:38:39 UTC (rev 52856)
+++ branches/soc-2011-tomato/extern/libmv/CMakeLists.txt	2012-12-10 16:38:58 UTC (rev 52857)
@@ -58,6 +58,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
@@ -119,6 +120,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: branches/soc-2011-tomato/extern/libmv/libmv/multiview/fundamental.h
===================================================================
--- branches/soc-2011-tomato/extern/libmv/libmv/multiview/fundamental.h	2012-12-10 16:38:39 UTC (rev 52856)
+++ branches/soc-2011-tomato/extern/libmv/libmv/multiview/fundamental.h	2012-12-10 16:38:58 UTC (rev 52857)
@@ -81,6 +81,26 @@
 double SymmetricEpipolarDistance(const Mat &F, const Vec2 &x1, const Vec2 &x2);
 
 /**
+ * Calculates the sum of the distances from the points to the epipolar lines.
+ *
+ * Templated and not optimized version of function above
+ */
+template<typename T> inline
+T SymmetricEpipolarDistance(const Eigen::Matrix<T, 3, 3> &F,
+                            const Eigen::Matrix<T, 2, 1> &x1,
+                            const Eigen::Matrix<T, 2, 1> &x2) {
+  Eigen::Matrix<T, 3, 1> x(x1(0), x1(1), T(1.0));
+  Eigen::Matrix<T, 3, 1> y(x2(0), x2(1), T(1.0));
+
+  Eigen::Matrix<T, 3, 1> F_x = F * x;
+  Eigen::Matrix<T, 3, 1> Ft_y = F.transpose() * y;
+  T y_F_x = y.dot(F_x);
+
+  return Square(y_F_x) * (  T(1) / F_x.head(2).squaredNorm()
+                          + T(1) / Ft_y.head(2).squaredNorm());
+}
+
+/**
  * Compute the relative camera motion between two cameras.
  *
  * Given the motion parameters of two cameras, computes the motion parameters

Modified: branches/soc-2011-tomato/extern/libmv/libmv/simple_pipeline/initialize_reconstruction.cc
===================================================================
--- branches/soc-2011-tomato/extern/libmv/libmv/simple_pipeline/initialize_reconstruction.cc	2012-12-10 16:38:39 UTC (rev 52856)
+++ branches/soc-2011-tomato/extern/libmv/libmv/simple_pipeline/initialize_reconstruction.cc	2012-12-10 16:38:58 UTC (rev 52857)
@@ -31,22 +31,6 @@
 namespace libmv {
 namespace {
 
-void CoordinatesForMarkersInImage(const vector<Marker> &markers,
-                                  int image,
-                                  Mat *coordinates) {
-  vector<Vec2> coords;
-  for (int i = 0; i < markers.size(); ++i) {
-    const Marker &marker = markers[i];
-    if (markers[i].image == image) {
-      coords.push_back(Vec2(marker.x, marker.y));
-    }
-  }
-  coordinates->resize(2, coords.size());
-  for (int i = 0; i < coords.size(); i++) {
-    coordinates->col(i) = coords[i];
-  }
-}
-
 void GetImagesInMarkers(const vector<Marker> &markers,
                         int *image1, int *image2) {
   if (markers.size() < 2) {

Added: branches/soc-2011-tomato/extern/libmv/libmv/simple_pipeline/keyframe_selection.cc
===================================================================
--- branches/soc-2011-tomato/extern/libmv/libmv/simple_pipeline/keyframe_selection.cc	                        (rev 0)
+++ branches/soc-2011-tomato/extern/libmv/libmv/simple_pipeline/keyframe_selection.cc	2012-12-10 16:38:58 UTC (rev 52857)
@@ -0,0 +1,310 @@
+// 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 "ceres/ceres.h"
+#include "libmv/logging/logging.h"
+#include "libmv/multiview/homography.h"
+#include "libmv/multiview/fundamental.h"
+#include "libmv/simple_pipeline/keyframe_selection.h"
+
+#include <stdio.h>
+
+namespace libmv {
+
+namespace {
+template<typename T>
+T SymmetricGeometricDistance(const Eigen::Matrix<T, 3, 3> &H,
+                                  const Eigen::Matrix<T, 2, 1> &x1,
+                                  const Eigen::Matrix<T, 2, 1> &x2) {
+  Eigen::Matrix<T, 3, 1> x(x1(0), x1(1), T(1.0));
+  Eigen::Matrix<T, 3, 1> y(x2(0), x2(1), T(1.0));
+
+  Eigen::Matrix<T, 3, 1> H_x = H * x;
+  Eigen::Matrix<T, 3, 1> Hinv_y = H.inverse() * y;
+
+  H_x /= H_x(2);
+  Hinv_y /= Hinv_y(2);
+
+  return (H_x.head(2) - y.head(2)).squaredNorm() +
+         (Hinv_y.head(2) - x.head(2)).squaredNorm();
+}
+
+class HomographySymmetricGeometricCostFunctor {
+ public:
+  HomographySymmetricGeometricCostFunctor(Mat &x1, Mat &x2)
+      : x1_(x1),
+        x2_(x2) {
+  }
+
+  template<typename T>
+  bool operator()(const T *homography_parameters, T *residuals) const {
+    typedef Eigen::Matrix<T, 3, 3> Mat3;
+    typedef Eigen::Matrix<T, 2, 1> Vec2;
+
+    Mat3 H(homography_parameters);
+
+    T symmetric_error = T(0.0);
+
+    for (int i = 0; i < x1_.cols(); i++) {
+      Vec2 x1(T(x1_(0, i)), T(x1_(1, i)));
+      Vec2 x2(T(x2_(0, i)), T(x2_(1, i)));
+
+      symmetric_error += SymmetricGeometricDistance(H, x1, x2);
+    }
+
+    residuals[0] = symmetric_error;
+
+    return true;
+  }
+
+  const Mat &x1_;
+  const Mat &x2_;
+};
+
+void ComputeHomographyFromCorrespondences(Mat &x1, Mat &x2, Mat3 *H) {
+  // Algebraic homography estimation
+  Homography2DFromCorrespondencesLinear(x1, x2, H);
+
+  // Refine matrix using Ceres minimizer
+  ceres::Problem problem;
+
+  HomographySymmetricGeometricCostFunctor *homography_symmetric_geometric_cost_function =
+       new HomographySymmetricGeometricCostFunctor(x1, x2);
+
+  problem.AddResidualBlock(
+      new ceres::AutoDiffCostFunction<
+          HomographySymmetricGeometricCostFunctor,
+          1, /* 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_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);
+
+  LG << "Summary:\n" << summary.FullReport();
+}
+
+class FundamentalSymmetricEpipolarCostFunctor {
+ public:
+  FundamentalSymmetricEpipolarCostFunctor(Mat &x1, Mat &x2)
+      : x1_(x1),
+        x2_(x2) {
+  }
+
+  template<typename T>
+  bool operator()(const T *fundamental_parameters, T *residuals) const {
+    typedef Eigen::Matrix<T, 3, 3> Mat3;
+    typedef Eigen::Matrix<T, 2, 1> Vec2;
+
+    Mat3 F(fundamental_parameters);
+
+    T error = T(0.0);
+
+    for (int i = 0; i < x1_.cols(); i++) {
+      Vec2 x1(T(x1_(0, i)), T(x1_(1, i)));
+      Vec2 x2(T(x2_(0, i)), T(x2_(1, i)));
+
+      error += SymmetricEpipolarDistance(F, x1, x2);
+    }
+
+    residuals[0] = error;
+
+    return true;
+  }
+
+  const Mat &x1_;
+  const Mat &x2_;
+};
+
+void ComputeFundamentalFromCorrespondences(Mat &x1, Mat &x2, Mat3 *F)
+{
+  // Algebraic fundamental estimation
+  NormalizedEightPointSolver(x1, x2, F);
+
+  // Refine matrix using Ceres minimizer
+  ceres::Problem problem;
+
+  FundamentalSymmetricEpipolarCostFunctor *fundamental_symmetric_epipolar_cost_function =
+       new FundamentalSymmetricEpipolarCostFunctor(x1, x2);
+
+  problem.AddResidualBlock(
+      new ceres::AutoDiffCostFunction<
+          FundamentalSymmetricEpipolarCostFunctor,
+          1, /* 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);
+
+  LG << "Summary:\n" << summary.FullReport();
+}
+
+// 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(Vec e, int d, int k, int r) {
+  int n = e.cols();
+  double lambda1 = log((double) r);
+  double lambda2 = log((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, but it also seems to be using base 2 for logarithms as
+  // well, so probably we need to alter coefficients above too
+  double lambda3 = 2.0;
+
+  // Compute squared standard deviation sigma2 of the error
+  double mean_value = 0;
+  for (int i = 0; i < n; i++)

@@ Diff output truncated at 10240 characters. @@



More information about the Bf-blender-cvs mailing list