Planar tracking support for motion tracking

===========================================

Major list of changes done in tomato branch:

- Add a planar tracking implementation to libmv
  This adds a new planar tracking implementation to libmv. The
  tracker is based on Ceres[1], the new nonlinear minimizer that
  myself and Sameer released from Google as open source. Since
  the motion model is more involved, the interface is
  different than the RegionTracker interface used previously
  in Blender.

  The start of a C API in libmv-capi.{cpp,h} is also included.

- Migrate from pat_{min,max} for markers to 4 corners representation

  Convert markers in the movie clip editor / 2D tracker from using
  pat_min and pat_max notation to using the a more general, 4-corner
  representation.

  There is still considerable porting work to do; in particular
  sliding from preview widget does not work correct for rotated
  markers.

  All other areas should be ported to new representation:

  * Added support of sliding individual corners. LMB slide + Ctrl
    would scale the whole pattern
  * S would scale the whole marker, S-S would scale pattern only
  * Added support of marker's rotation which is currently rotates
    only patterns around their centers or all markers around median,

    Rotation or other non-translation/scaling transformation of search
    area doesn't make sense.

  * Track Preview widget would display transformed pattern which
    libmv actually operates with.

- "Efficient Second-order Minimization" for the planar tracker

  This implements the "Efficient Second-order Minimization"
  scheme, as supported by the existing translation tracker.
  This increases the amount of per-iteration work, but
  decreases the number of iterations required to converge and
  also increases the size of the basin of attraction for the
  optimization.

- Remove the use of the legacy RegionTracker API from Blender,
  and replaces it with the new TrackRegion API. This also
  adds several features to the planar tracker in libmv:

  * Do a brute-force initialization of tracking similar to "Hybrid"
    mode in the stable release, but using all floats. This is slower
    but more accurate. It is still necessary to evaluate if the
    performance loss is worth it. In particular, this change is
    necessary to support high bit depth imagery.

  * Add support for masks over the search window. This is a step
    towards supporting user-defined tracker masks. The tracker masks
    will make it easy for users to make a mask for e.g. a ball.

    Not exposed into interface yet/

  * Add Pearson product moment correlation coefficient checking (aka
    "Correlation" in the UI. This causes tracking failure if the
    tracked patch is not linearly related to the template.

  * Add support for warping a few points in addition to the supplied
    points. This is useful because the tracking code deliberately
    does not expose the underlying warp representation. Instead,
    warps are specified in an aparametric way via the correspondences.

- Replace the old style tracker configuration panel with the
  new planar tracking panel. From a users perspective, this means:

  * The old "tracking algorithm" picker is gone. There is only 1
    algorithm now. We may revisit this later, but I would much
    prefer to have only 1 algorithm. So far no optimization work
    has been done so the speed is not there yet.

  * There is now a dropdown to select the motion model. Choices:

        * Translation
        * Translation, rotation
        * Translation, scale
        * Translation, rotation, scale
        * Affine
        * Perspective

  * The old "Hybrid" mode is gone; instead there is a toggle to
    enable or disable translation-only tracker initialization. This
    is the equivalent of the hyrbid mode before, but rewritten to work
    with the new planar tracking modes.

  * The pyramid levels setting is gone. At a future date, the planar
    tracker will decide to use pyramids or not automatically. The
    pyramid setting was ultimately a mistake; with the brute force
    initialization it is unnecessary.

- Add light-normalized tracking

  Added the ability to normalize patterns by their average value while
  tracking, to make them invariant to global illumination changes.

Additional details could be found at wiki page [2]

  [1] http://code.google.com/p/ceres-solver
  [2] http://wiki.blender.org/index.php/Dev:Ref/Release_Notes/2.64/Motion_Tracker

1 files changed, 135 insertions, 14 deletions

diff --git a/extern/libmv/libmv-capi.cpp b/extern/libmv/libmv-capi.cpp
index 6c20d76eeac..ffa065f08fe 100644
--- a/extern/libmv/libmv-capi.cpp
+++ b/extern/libmv/libmv-capi.cpp
@@ -28,6 +28,10 @@
    tracking between which failed */
 #undef DUMP_FAILURE
 
+/* define this to generate PNG images with content of search areas
+   on every itteration of tracking */
+#undef DUMP_ALWAYS
+
 #include "libmv-capi.h"
 
 #include "third_party/gflags/gflags/gflags.h"
@@ -45,6 +49,7 @@
 #include "libmv/tracking/trklt_region_tracker.h"
 #include "libmv/tracking/lmicklt_region_tracker.h"
 #include "libmv/tracking/pyramid_region_tracker.h"
+#include "libmv/tracking/track_region.h"
 
 #include "libmv/simple_pipeline/callbacks.h"
 #include "libmv/simple_pipeline/tracks.h"
@@ -59,7 +64,7 @@
 #include <stdlib.h>
 #include <assert.h>
 
-#ifdef DUMP_FAILURE
+#if defined(DUMP_FAILURE) || defined (DUMP_ALWAYS)
 #  include <png.h>
 #endif
 
@@ -97,7 +102,7 @@ void libmv_initLogging(const char *argv0)
 void libmv_startDebugLogging(void)
 {
 	google::SetCommandLineOption("logtostderr", "1");
-	google::SetCommandLineOption("v", "0");
+	google::SetCommandLineOption("v", "2");
 	google::SetCommandLineOption("stderrthreshold", "1");
 	google::SetCommandLineOption("minloglevel", "0");
 	V3D::optimizerVerbosenessLevel = 1;
@@ -158,20 +163,35 @@ libmv_RegionTracker *libmv_bruteRegionTrackerNew(int half_window_size, double mi
 	return (libmv_RegionTracker *)brute_region_tracker;
 }
 
-static void floatBufToImage(const float *buf, int width, int height, libmv::FloatImage *image)
+static void floatBufToImage(const float *buf, int width, int height, int channels, libmv::FloatImage *image)
 {
-	int x, y, a = 0;
+	int x, y, k, a = 0;
 
-	image->resize(height, width);
+	image->Resize(height, width, channels);
 
 	for (y = 0; y < height; y++) {
 		for (x = 0; x < width; x++) {
-			(*image)(y, x, 0) = buf[a++];
+			for (k = 0; k < channels; k++) {
+				(*image)(y, x, k) = buf[a++];
+			}
+		}
+	}
+}
+
+static void imageToFloatBuf(const libmv::FloatImage *image, int channels, float *buf)
+{
+	int x, y, k, a = 0;
+
+	for (y = 0; y < image->Height(); y++) {
+		for (x = 0; x < image->Width(); x++) {
+			for (k = 0; k < channels; k++) {
+				buf[a++] = (*image)(y, x, k);
+			}
 		}
 	}
 }
 
-#ifdef DUMP_FAILURE
+#if defined(DUMP_FAILURE) || defined (DUMP_ALWAYS)
 void savePNGImage(png_bytep *row_pointers, int width, int height, int depth, int color_type, char *file_name)
 {
 	png_infop info_ptr;
@@ -234,14 +254,14 @@ static void saveImage(char *prefix, libmv::FloatImage image, int x0, int y0)
 		row_pointers[y]= (png_bytep)malloc(sizeof(png_byte)*4*image.Width());
 
 		for (x = 0; x < image.Width(); x++) {
-			if (x0 == x && y0 == y) {
+			if (x0 == x && image.Height() - y0 - 1 == y) {
 				row_pointers[y][x*4+0]= 255;
 				row_pointers[y][x*4+1]= 0;
 				row_pointers[y][x*4+2]= 0;
 				row_pointers[y][x*4+3]= 255;
 			}
 			else {
-				float pixel = image(y, x, 0);
+				float pixel = image(image.Height() - y - 1, x, 0);
 				row_pointers[y][x*4+0]= pixel*255;
 				row_pointers[y][x*4+1]= pixel*255;
 				row_pointers[y][x*4+2]= pixel*255;
@@ -302,19 +322,23 @@ int libmv_regionTrackerTrack(libmv_RegionTracker *libmv_tracker, const float *im
 	libmv::RegionTracker *region_tracker = (libmv::RegionTracker *)libmv_tracker;
 	libmv::FloatImage old_patch, new_patch;
 
-	floatBufToImage(ima1, width, height, &old_patch);
-	floatBufToImage(ima2, width, height, &new_patch);
+	floatBufToImage(ima1, width, height, 1, &old_patch);
+	floatBufToImage(ima2, width, height, 1, &new_patch);
 
-#ifndef DUMP_FAILURE
+#if !defined(DUMP_FAILURE) && !defined(DUMP_ALWAYS)
 	return region_tracker->Track(old_patch, new_patch, x1, y1, x2, y2);
 #else
 	{
-		double sx2 = *x2, sy2 = *y2;
+		/* double sx2 = *x2, sy2 = *y2; */
 		int result = region_tracker->Track(old_patch, new_patch, x1, y1, x2, y2);
 
+#if defined(DUMP_ALWAYS)
+		{
+#else
 		if (!result) {
+#endif
 			saveImage("old_patch", old_patch, x1, y1);
-			saveImage("new_patch", new_patch, sx2, sy2);
+			saveImage("new_patch", new_patch, *x2, *y2);
 		}
 
 		return result;
@@ -329,6 +353,103 @@ void libmv_regionTrackerDestroy(libmv_RegionTracker *libmv_tracker)
 	delete region_tracker;
 }
 
+/* ************ Planar tracker ************ */
+
+/* TrackRegion (new planar tracker) */
+int libmv_trackRegion(const struct libmv_trackRegionOptions *options,
+                      const float *image1, const float *image2,
+                      int width, int height, 
+                      const double *x1, const double *y1,
+                      struct libmv_trackRegionResult *result,
+                      double *x2, double *y2)
+{
+	double xx1[5], yy1[5];
+	double xx2[5], yy2[5];
+	bool tracking_result = false;
+
+	/* Convert to doubles for the libmv api. The four corners and the center. */
+	for (int i = 0; i < 5; ++i) {
+		xx1[i] = x1[i];
+		yy1[i] = y1[i];
+		xx2[i] = x2[i];
+		yy2[i] = y2[i];
+	}
+
+	libmv::TrackRegionOptions track_region_options;
+	switch (options->motion_model) {
+#define LIBMV_CONVERT(the_model) \
+    case libmv::TrackRegionOptions::the_model: \
+		track_region_options.mode = libmv::TrackRegionOptions::the_model; \
+		break;
+		LIBMV_CONVERT(TRANSLATION)
+		LIBMV_CONVERT(TRANSLATION_ROTATION)
+		LIBMV_CONVERT(TRANSLATION_SCALE)
+		LIBMV_CONVERT(TRANSLATION_ROTATION_SCALE)
+		LIBMV_CONVERT(AFFINE)
+		LIBMV_CONVERT(HOMOGRAPHY)
+#undef LIBMV_CONVERT
+	}
+
+	track_region_options.minimum_correlation = options->minimum_correlation;
+	track_region_options.max_iterations = options->num_iterations;
+	track_region_options.sigma = options->sigma;
+	track_region_options.num_extra_points = 1;
+	track_region_options.image1_mask = NULL;
+	track_region_options.use_brute_initialization = options->use_brute;
+	track_region_options.use_normalized_intensities = options->use_normalization;
+
+	/* Convert from raw float buffers to libmv's FloatImage. */
+	libmv::FloatImage old_patch, new_patch;
+	floatBufToImage(image1, width, height, 1, &old_patch);
+	floatBufToImage(image2, width, height, 1, &new_patch);
+
+	libmv::TrackRegionResult track_region_result;
+	libmv::TrackRegion(old_patch, new_patch, xx1, yy1, track_region_options, xx2, yy2, &track_region_result);
+
+	/* Convert to floats for the blender api. */
+	for (int i = 0; i < 5; ++i) {
+		x2[i] = xx2[i];
+		y2[i] = yy2[i];
+	}
+
+	/* TODO(keir): Update the termination string with failure details. */
+	if (track_region_result.termination == libmv::TrackRegionResult::PARAMETER_TOLERANCE ||
+	    track_region_result.termination == libmv::TrackRegionResult::FUNCTION_TOLERANCE  ||
+	    track_region_result.termination == libmv::TrackRegionResult::GRADIENT_TOLERANCE  ||
+	    track_region_result.termination == libmv::TrackRegionResult::NO_CONVERGENCE)
+	{
+		tracking_result = true;
+	}
+
+#if defined(DUMP_FAILURE) || defined(DUMP_ALWAYS)
+#if defined(DUMP_ALWAYS)
+	{
+#else
+	if (!tracking_result) {
+#endif
+		saveImage("old_patch", old_patch, x1[4], y1[4]);
+		saveImage("new_patch", new_patch, x2[4], y2[4]);
+	}
+#endif
+
+	return tracking_result;
+}
+
+void libmv_samplePlanarPatch(const float *image, int width, int height,
+                             int channels, const double *xs, const double *ys,
+                             int num_samples_x, int num_samples_y, float *patch,
+                             double *warped_position_x, double *warped_position_y)
+{
+	libmv::FloatImage libmv_image, libmv_patch;
+
+	floatBufToImage(image, width, height, channels, &libmv_image);
+
+	libmv::SamplePlanarPatch(libmv_image, xs, ys, num_samples_x, num_samples_y,
+	                         &libmv_patch, warped_position_x, warped_position_y);
+
+	imageToFloatBuf(&libmv_patch, channels, patch);
+}
+
 /* ************ Tracks ************ */
 
 libmv_Tracks *libmv_tracksNew(void)