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, 60 insertions, 23 deletions

diff --git a/source/blender/makesdna/DNA_tracking_types.h b/source/blender/makesdna/DNA_tracking_types.h
index 823ecbbbba6..c5b0174a3c9 100644
--- a/source/blender/makesdna/DNA_tracking_types.h
+++ b/source/blender/makesdna/DNA_tracking_types.h
@@ -35,6 +35,7 @@
 #ifndef __DNA_TRACKING_TYPES_H__
 #define __DNA_TRACKING_TYPES_H__
 
+#include "DNA_defs.h"
 #include "DNA_listBase.h"
 
 /* match-moving data */
@@ -69,6 +70,27 @@ typedef struct MovieTrackingCamera {
 
 typedef struct MovieTrackingMarker {
 	float pos[2];	/* 2d position of marker on frame (in unified 0..1 space) */
+
+	/* corners of pattern in the following order:
+	 *
+	 *       Y
+	 *       ^
+	 *       | (3) --- (2)
+	 *       |  |       |
+	 *       |  |       |
+	 *       |  |       |
+	 *       | (0) --- (1)
+	 *       +-------------> X
+	 *
+	 * the coordinates are stored relative to pos.
+	 */
+	float pattern_corners[4][2];
+
+	/* positions of left-bottom and right-top corners of search area (in unified 0..1 units,
+	 * relative to marker->pos
+	 */
+	float search_min[2], search_max[2];
+
 	int framenr;	/* number of frame marker is associated with */
 	int flag;		/* Marker's flag (alive, ...) */
 } MovieTrackingMarker;
@@ -79,8 +101,19 @@ typedef struct MovieTrackingTrack {
 	char name[64];	/* MAX_NAME */
 
 	/* ** setings ** */
-	float pat_min[2], pat_max[2];		/* positions of left-bottom and right-top corners of pattern (in unified 0..1 space) */
-	float search_min[2], search_max[2];	/* positions of left-bottom and right-top corners of search area (in unified 0..1 space) */
+
+	/* positions of left-bottom and right-top corners of pattern (in unified 0..1 units,
+	 * relative to marker->pos)
+	 * moved to marker's corners since planar tracking implementation
+	 */
+	float pat_min[2] DNA_DEPRECATED, pat_max[2] DNA_DEPRECATED;
+
+	/* positions of left-bottom and right-top corners of search area (in unified 0..1 units,
+	 * relative to marker->pos
+	 * moved to marker since affine tracking implementation
+	 */
+	float search_min[2] DNA_DEPRECATED, search_max[2] DNA_DEPRECATED;
+
 	float offset[2];					/* offset to "parenting" point */
 
 	/* ** track ** */
@@ -96,35 +129,32 @@ typedef struct MovieTrackingTrack {
 	int flag, pat_flag, search_flag;	/* flags (selection, ...) */
 	float color[3];						/* custom color for track */
 
-	/* tracking algorithm to use; can be KLT or SAD */
+	/* ** control how tracking happens */
 	short frames_limit;		/* number of frames to be tarcked during single tracking session (if TRACKING_FRAMES_LIMIT is set) */
 	short margin;			/* margin from frame boundaries */
 	short pattern_match;	/* re-adjust every N frames */
 
-	short tracker;			/* tracking algorithm used for this track */
-
-	/* ** KLT tracker settings ** */
-	short pyramid_levels, pad2;		/* number of pyramid levels to use for KLT tracking */
-
-	/* ** SAD tracker settings ** */
+	/* tracking parameters */
+	short motion_model;     /* model of the motion for this track */
+	int algorithm_flag;    /* flags for the tracking algorithm (use brute, use esm, use pyramid, etc */
 	float minimum_correlation;			/* minimal correlation which is still treated as successful tracking */
 
-	struct bGPdata *gpd;            /* grease-pencil data */
+	struct bGPdata *gpd;		/* grease-pencil data */
 } MovieTrackingTrack;
 
 typedef struct MovieTrackingSettings {
 	int flag;
 
 	/* ** default tracker settings */
-	short default_tracker;				/* tracking algorithm used by default */
-	short default_pyramid_levels;		/* number of pyramid levels to use for KLT tracking */
-	float default_minimum_correlation;	/* minimal correlation which is still treated as successful tracking */
-	short default_pattern_size;			/* size of pattern area for new tracks */
-	short default_search_size;			/* size of search area for new tracks */
-	short default_frames_limit;			/* number of frames to be tarcked during single tracking session (if TRACKING_FRAMES_LIMIT is set) */
-	short default_margin;				/* margin from frame boundaries */
-	short default_pattern_match;		/* re-adjust every N frames */
-	short default_flag;					/* default flags like color channels used by default */
+	short default_motion_model;         /* model of the motion for this track */
+	short default_algorithm_flag;       /* flags for the tracking algorithm (use brute, use esm, use pyramid, etc */
+	float default_minimum_correlation;  /* minimal correlation which is still treated as successful tracking */
+	short default_pattern_size;         /* size of pattern area for new tracks */
+	short default_search_size;          /* size of search area for new tracks */
+	short default_frames_limit;         /* number of frames to be tarcked during single tracking session (if TRACKING_FRAMES_LIMIT is set) */
+	short default_margin;               /* margin from frame boundaries */
+	short default_pattern_match;        /* re-adjust every N frames */
+	short default_flag;                 /* default flags like color channels used by default */
 
 	short motion_flag;		/* flags describes motion type */
 
@@ -258,10 +288,17 @@ enum {
 #define TRACK_PREVIEW_GRAYSCALE	(1<<9)
 #define TRACK_DOPE_SEL		(1<<10)
 
-/* MovieTrackingTrack->tracker */
-#define TRACKER_KLT		0
-#define TRACKER_SAD		1
-#define TRACKER_HYBRID		2
+/* MovieTrackingTrack->motion_model */
+#define TRACK_MOTION_MODEL_TRANSLATION                 0
+#define TRACK_MOTION_MODEL_TRANSLATION_ROTATION        1
+#define TRACK_MOTION_MODEL_TRANSLATION_SCALE           2
+#define TRACK_MOTION_MODEL_TRANSLATION_ROTATION_SCALE  3
+#define TRACK_MOTION_MODEL_AFFINE                      4
+#define TRACK_MOTION_MODEL_HOMOGRAPHY                  5
+
+/* MovieTrackingTrack->algorithm_flag */
+#define TRACK_ALGORITHM_FLAG_USE_BRUTE 1
+#define TRACK_ALGORITHM_FLAG_USE_NORMALIZATION 2
 
 /* MovieTrackingTrack->adjframes */
 #define TRACK_MATCH_KEYFRAME		0