[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [42376] branches/soc-2011-tomato: Add a new hybrid region tracker for motion tracking to libmv, and

Keir Mierle mierle at gmail.com
Sat Dec 3 23:27:35 CET 2011


Revision: 42376
          http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=42376
Author:   keir
Date:     2011-12-03 22:27:32 +0000 (Sat, 03 Dec 2011)
Log Message:
-----------
Add a new hybrid region tracker for motion tracking to libmv, and
add it as an option (under "Hybrid") in the tracking settings. The
region tracker is a combination of brute force tracking for coarse
alignment, then refinement with the ESM/KLT algorithm already in
libmv that gives excellent subpixel precision (typically 1/50'th
of a pixel)

This also adds a new "brute force" region tracker which does a
brute force search through every pixel position in the destination
for the pattern in the first frame. It leverages SSE if available,
similar to the SAD tracker, to do this quickly. Currently it does
some unnecessary conversions to/from floating point that will get
fixed later.

The hybrid tracker glues the two trackers (brute & ESM) together
to get an overall better tracker. The algorithm is simple:

1. Track from frame 1 to frame 2 with the brute force tracker.
   This tries every possible pixel position for the pattern from
   frame 1 in frame 2. The position with the smallest
   sum-of-absolute-differences is chosen. By definition, this
   position is only accurate up to 1 pixel or so.
2. Using the result from 1, initialize a track with ESM. This does
   a least-squares fit with subpixel precision.
3. If the ESM shift was more than 2 pixels, report failure.
4. If the ESM track shifted less than 2 pixels, then the track is
   good and we're done. The rationale here is that if the
   refinement stage shifts more than 1 pixel, then the brute force
   result likely found some random position that's not a good fit.

Modified Paths:
--------------
    branches/soc-2011-tomato/extern/libmv/CMakeLists.txt
    branches/soc-2011-tomato/extern/libmv/libmv-capi.cpp
    branches/soc-2011-tomato/extern/libmv/libmv-capi.h
    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/tracking/brute_region_tracker.cc
    branches/soc-2011-tomato/extern/libmv/libmv/tracking/brute_region_tracker.h
    branches/soc-2011-tomato/extern/libmv/libmv/tracking/hybrid_region_tracker.cc
    branches/soc-2011-tomato/extern/libmv/libmv/tracking/hybrid_region_tracker.h

Modified: branches/soc-2011-tomato/extern/libmv/CMakeLists.txt
===================================================================
--- branches/soc-2011-tomato/extern/libmv/CMakeLists.txt	2011-12-03 22:15:13 UTC (rev 42375)
+++ branches/soc-2011-tomato/extern/libmv/CMakeLists.txt	2011-12-03 22:27:32 UTC (rev 42376)
@@ -53,6 +53,8 @@
 	libmv/image/array_nd.cc
 	libmv/tracking/pyramid_region_tracker.cc
 	libmv/tracking/sad.cc
+	libmv/tracking/brute_region_tracker.cc
+	libmv/tracking/hybrid_region_tracker.cc
 	libmv/tracking/esm_region_tracker.cc
 	libmv/tracking/trklt_region_tracker.cc
 	libmv/tracking/klt_region_tracker.cc
@@ -100,6 +102,8 @@
 	libmv/image/sample.h
 	libmv/image/image.h
 	libmv/tracking/region_tracker.h
+	libmv/tracking/brute_region_tracker.h
+	libmv/tracking/hybrid_region_tracker.h
 	libmv/tracking/retrack_region_tracker.h
 	libmv/tracking/sad.h
 	libmv/tracking/pyramid_region_tracker.h

Added: branches/soc-2011-tomato/extern/libmv/libmv/tracking/brute_region_tracker.cc
===================================================================
--- branches/soc-2011-tomato/extern/libmv/libmv/tracking/brute_region_tracker.cc	                        (rev 0)
+++ branches/soc-2011-tomato/extern/libmv/libmv/tracking/brute_region_tracker.cc	2011-12-03 22:27:32 UTC (rev 42376)
@@ -0,0 +1,310 @@
+// Copyright (c) 2011 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/tracking/brute_region_tracker.h"
+
+#ifdef __SSE2__
+#include <emmintrin.h>
+#endif
+
+#include <malloc.h> // For memalign.
+
+#include "libmv/image/image.h"
+#include "libmv/image/convolve.h"
+#include "libmv/image/sample.h"
+#include "libmv/logging/logging.h"
+
+namespace libmv {
+namespace {
+
+// TODO(keir): It's stupid that this is needed here. Push this somewhere else.
+void *aligned_malloc(int size, int alignment) {
+#ifdef _WIN32
+  return _aligned_malloc(size, alignment);
+#else  // TODO(keir): Will this work on Mac OS X?
+  return memalign(alignment, size);
+#endif
+}
+
+void aligned_free(void *ptr) {
+#ifdef _WIN32
+  _aligned_free(ptr);
+#else
+  free(ptr);
+#endif
+}
+
+bool RegionIsInBounds(const FloatImage &image1,
+                      double x, double y,
+                      int half_window_size) {
+  // Check the minimum coordinates.
+  int min_x = floor(x) - half_window_size - 1;
+  int min_y = floor(y) - half_window_size - 1;
+  if (min_x < 0.0 ||
+      min_y < 0.0) {
+    return false;
+  }
+
+  // Check the maximum coordinates.
+  int max_x = ceil(x) + half_window_size + 1;
+  int max_y = ceil(y) + half_window_size + 1;
+  if (max_x > image1.cols() ||
+      max_y > image1.rows()) {
+    return false;
+  }
+
+  // Ok, we're good.
+  return true;
+}
+
+#ifdef __SSE2__
+
+// Compute the sub of absolute differences between the arrays "a" and "b". 
+// The array "a" is assumed to be 16-byte aligned, while "b" is not. The
+// result is returned as the first and third elements of __m128i if
+// interpreted as a 4-element 32-bit integer array. The SAD is the sum of the
+// elements.
+//
+// The function requires size % 16 valid extra elements at the end of both "a"
+// and "b", since the SSE load instructionst will pull in memory past the end
+// of the arrays if their size is not a multiple of 16.
+inline static __m128i SumOfAbsoluteDifferencesContiguousSSE(
+    const unsigned char *a,  // aligned
+    const unsigned char *b,  // not aligned
+    unsigned int size,
+    __m128i sad) {
+  // Do the bulk of the work as 16-way integer operations.
+  for(unsigned int j = 0; j < size / 16; j++) {
+    sad = _mm_add_epi32(sad, _mm_sad_epu8( _mm_load_si128 ((__m128i*)(a + 16 * j)),
+                                           _mm_loadu_si128((__m128i*)(b + 16 * j))));
+  }
+  // Handle the trailing end.
+  // TODO(keir): Benchmark to verify that the below SSE is a win compared to a
+  // hand-rolled loop. It's not clear that the hand rolled loop would be slower
+  // than the potential cache miss when loading the immediate table below.
+  //
+  // An alternative to this version is to take a packet of all 1's then do a
+  // 128-bit shift. The issue is that the shift instruction needs an immediate
+  // amount rather than a variable amount, so the branch instruction here must
+  // remain. See _mm_srli_si128 and  _mm_slli_si128.
+  unsigned int remainder = size % 16u;
+  if (remainder) {
+    unsigned int j = size / 16;
+    __m128i a_trail = _mm_load_si128 ((__m128i*)(a + 16 * j));
+    __m128i b_trail = _mm_loadu_si128((__m128i*)(b + 16 * j));
+    __m128i mask;
+    switch (remainder) {
+#define X 0xff
+      case  1: mask = _mm_setr_epi8(X, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0); break;
+      case  2: mask = _mm_setr_epi8(X, X, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0); break;
+      case  3: mask = _mm_setr_epi8(X, X, X, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0); break;
+      case  4: mask = _mm_setr_epi8(X, X, X, X, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0); break;
+      case  5: mask = _mm_setr_epi8(X, X, X, X, X, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0); break;
+      case  6: mask = _mm_setr_epi8(X, X, X, X, X, X, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0); break;
+      case  7: mask = _mm_setr_epi8(X, X, X, X, X, X, X, 0, 0, 0, 0, 0, 0, 0, 0, 0); break;
+      case  8: mask = _mm_setr_epi8(X, X, X, X, X, X, X, X, 0, 0, 0, 0, 0, 0, 0, 0); break;
+      case  9: mask = _mm_setr_epi8(X, X, X, X, X, X, X, X, X, 0, 0, 0, 0, 0, 0, 0); break;
+      case 10: mask = _mm_setr_epi8(X, X, X, X, X, X, X, X, X, X, 0, 0, 0, 0, 0, 0); break;
+      case 11: mask = _mm_setr_epi8(X, X, X, X, X, X, X, X, X, X, X, 0, 0, 0, 0, 0); break;
+      case 12: mask = _mm_setr_epi8(X, X, X, X, X, X, X, X, X, X, X, X, 0, 0, 0, 0); break;
+      case 13: mask = _mm_setr_epi8(X, X, X, X, X, X, X, X, X, X, X, X, X, 0, 0, 0); break;
+      case 14: mask = _mm_setr_epi8(X, X, X, X, X, X, X, X, X, X, X, X, X, X, 0, 0); break;
+      case 15: mask = _mm_setr_epi8(X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 0); break;
+#undef X
+    }
+    sad = _mm_add_epi32(sad, _mm_sad_epu8(_mm_and_si128(mask, a_trail),
+                                          _mm_and_si128(mask, b_trail)));
+  }
+  return sad;
+}
+#endif
+
+// Computes the sum of absolute differences between pattern and image. Pattern
+// must be 16-byte aligned, and the stride must be a multiple of 16. The image
+// does pointer does not have to be aligned.
+int SumOfAbsoluteDifferencesContiguousImage(
+    const unsigned char *pattern,
+    unsigned int pattern_width,
+    unsigned int pattern_height,
+    unsigned int pattern_stride,
+    const unsigned char *image,
+    unsigned int image_stride) {
+#ifdef __SSE2__
+  // TODO(keir): Add interleaved accumulation, where accumulation is done into
+  // two or more SSE registers that then get combined at the end. This reduces
+  // instruction dependency; in Eigen's squared norm code, splitting the
+  // accumulation produces a ~2x speedup. It's not clear it will help here,
+  // where the number of SSE instructions in the inner loop is smaller.
+  __m128i sad = _mm_setzero_si128();
+  for (int r = 0; r < pattern_height; ++r) {
+    sad = SumOfAbsoluteDifferencesContiguousSSE(&pattern[pattern_stride * r],
+                                                &image[image_stride * r],
+                                                pattern_width,
+                                                sad);
+  }
+  return _mm_cvtsi128_si32(
+             _mm_add_epi32(sad,
+                 _mm_shuffle_epi32(sad, _MM_SHUFFLE(3, 0, 1, 2))));
+#else
+  int sad = 0;
+  for (int r = 0; r < pattern_height; ++r) {
+    for (int c = 0; c < pattern_width; ++c) {
+      sad += abs(pattern[pattern_stride * r + c] - image[image_stride * r + c]);
+    }
+  }
+  return sad;
+#endif
+}
+
+// Sample a region of size width, height centered at x,y in image, converting
+// from float to byte in the process. Samples from the first channel. Puts
+// result into *pattern.
+void SampleRectangularPattern(const FloatImage &image,
+                              double x, double y,
+                              int width,
+                              int height,
+                              int pattern_stride,
+                              unsigned char *pattern) {
+  // There are two cases for width and height: even or odd. If it's odd, then
+  // the bounds [-width / 2, width / 2] works as expected. However, for even,
+  // this results in one extra access past the end. So use < instead of <= in
+  // the loops below, but increase the end limit by one in the odd case.
+  int end_width = (width / 2) + (width % 2);
+  int end_height = (height / 2) + (height % 2);
+  for (int r = -height / 2; r < end_height; ++r) {
+    for (int c = -width / 2; c < end_width; ++c) {
+      pattern[pattern_stride * (r + height / 2) +  c + width / 2] =
+          SampleLinear(image, y + r, x + c, 0) * 255.0;
+    }
+  }
+}
+
+// Returns x rounded up to the nearest multiple of alignment.
+inline int PadToAlignment(int x, int alignment) {
+  if (x % alignment != 0) {
+    x += alignment - (x % alignment);
+  }
+  return x;
+}
+
+// Sample a region centered at x,y in image with size extending by half_width
+// from x. Samples from the first channel. The resulting array is placed in
+// *pattern, and the stride, which will be a multiple of 16 if SSE is enabled,
+// is returned in *pattern_stride.
+//

@@ Diff output truncated at 10240 characters. @@



More information about the Bf-blender-cvs mailing list