Assorted camera tracker improvements

- Add support for refining the camera's intrinsic parameters
  during a solve. Currently, refining supports only the following
  combinations of intrinsic parameters:

    f
    f, cx, cy
    f, cx, cy, k1, k2
    f, k1
    f, k1, k2

  This is not the same as autocalibration, since the user must
  still make a reasonable initial guess about the focal length and
  other parameters, whereas true autocalibration would eliminate
  the need for the user specify intrinsic parameters at all.

  However, the solver works well with only rough guesses for the
  focal length, so perhaps full autocalibation is not that
  important.

  Adding support for the last two combinations, (f, k1) and (f,
  k1, k2) required changes to the library libmv depends on for
  bundle adjustment, SSBA. These changes should get ported
  upstream not just to libmv but to SSBA as well.

- Improved the region of convergence for bundle adjustment by
  increasing the number of Levenberg-Marquardt iterations from 50
  to 500. This way, the solver is able to crawl out of the bad
  local minima it gets stuck in when changing from, for example,
  bundling k1 and k2 to just k1 and resetting k2 to 0.

- Add several new region tracker implementations. A region tracker
  is a libmv concept, which refers to tracking a template image
  pattern through frames. The impact to end users is that tracking
  should "just work better". I am reserving a more detailed
  writeup, and maybe a paper, for later.

- Other libmv tweaks, such as detecting that a tracker is headed
  outside of the image bounds.

This includes several changes made directly to the libmv extern
code rather expecting to get those changes through normal libmv
channels, because I, the libmv BDFL, decided it was faster to work
on libmv directly in Blender, then later reverse-port the libmv
changes from Blender back into libmv trunk. The interesting part
is that I added a full Levenberg-Marquardt loop to the region
tracking code, which should lead to a more stable solutions. I
also added a hacky implementation of "Efficient Second-Order
Minimization" for tracking, which works nicely. A more detailed
quantitative evaluation will follow.

Original patch by Keir, cleaned a bit by myself.

5 files changed, 126 insertions, 21 deletions

diff --git a/source/blender/blenkernel/BKE_tracking.h b/source/blender/blenkernel/BKE_tracking.h
index a8fb2c836de..af852d49d82 100644
--- a/source/blender/blenkernel/BKE_tracking.h
+++ b/source/blender/blenkernel/BKE_tracking.h
@@ -91,6 +91,8 @@ void BKE_tracking_sync_user(struct MovieClipUser *user, struct MovieTrackingCont
 int BKE_tracking_next(struct MovieTrackingContext *context);
 
 /* Camera solving */
+int BKE_tracking_can_solve(struct MovieTracking *tracking, char *error_msg, int error_size);
+
 float BKE_tracking_solve_reconstruction(struct MovieTracking *tracking, int width, int height);
 
 struct MovieReconstructedCamera *BKE_tracking_get_reconstructed_camera(struct MovieTracking *tracking, int framenr);
diff --git a/source/blender/blenkernel/intern/tracking.c b/source/blender/blenkernel/intern/tracking.c
index d65840720cd..4989e8f1b55 100644
--- a/source/blender/blenkernel/intern/tracking.c
+++ b/source/blender/blenkernel/intern/tracking.c
@@ -47,6 +47,7 @@
 #include "BLI_listbase.h"
 #include "BLI_ghash.h"
 #include "BLI_path_util.h"
+#include "BLI_string.h"
 
 #include "BKE_global.h"
 #include "BKE_tracking.h"
@@ -1260,7 +1261,28 @@ static struct libmv_Tracks *create_libmv_tracks(MovieTracking *tracking, int wid
 	return tracks;
 }
 
-static int retrieve_libmv_reconstruct(MovieTracking *tracking, struct libmv_Reconstruction *libmv_reconstruction)
+static void retrieve_libmv_reconstruct_intrinscis(MovieTracking *tracking, struct libmv_Reconstruction *libmv_reconstruction)
+{
+	struct libmv_CameraIntrinsics *libmv_intrinsics = libmv_ReconstructionExtractIntrinsics(libmv_reconstruction);
+
+	float aspy= 1.0f/tracking->camera.pixel_aspect;
+
+	double focal_length, principal_x, principal_y, k1, k2, k3;
+	int width, height;
+
+	libmv_CameraIntrinsicsExtract(libmv_intrinsics, &focal_length, &principal_x, &principal_y,
+			&k1, &k2, &k3, &width, &height);
+
+	tracking->camera.focal= focal_length;
+	tracking->camera.principal[0]= principal_x;
+
+	/* todo: verify divide by aspy is correct */
+	tracking->camera.principal[1]= principal_y / aspy;
+	tracking->camera.k1= k1;
+	tracking->camera.k2= k2;
+}
+
+static int retrieve_libmv_reconstruct_tracks(MovieTracking *tracking, struct libmv_Reconstruction *libmv_reconstruction)
 {
 	int tracknr= 0;
 	int sfra= INT_MAX, efra= INT_MIN, a, origin_set= 0;
@@ -1373,7 +1395,68 @@ static int retrieve_libmv_reconstruct(MovieTracking *tracking, struct libmv_Reco
 	return ok;
 }
 
+static int retrieve_libmv_reconstruct(MovieTracking *tracking, struct libmv_Reconstruction *libmv_reconstruction)
+{
+	/* take the intrinscis back from libmv */
+	retrieve_libmv_reconstruct_intrinscis(tracking, libmv_reconstruction);
+
+	return retrieve_libmv_reconstruct_tracks(tracking, libmv_reconstruction);
+}
+
+static int get_refine_intrinsics_flags(MovieTracking *tracking)
+{
+	int refine= tracking->settings.refine_camera_intrinsics;
+	int flags= 0;
+
+	if(refine&REFINE_FOCAL_LENGTH)
+		flags|= LIBMV_REFINE_FOCAL_LENGTH;
+
+	if(refine&REFINE_PRINCIPAL_POINT)
+		flags|= LIBMV_REFINE_PRINCIPAL_POINT;
+
+	if(refine&REFINE_RADIAL_DISTORTION_K1)
+		flags|= REFINE_RADIAL_DISTORTION_K1;
+
+	if(refine&REFINE_RADIAL_DISTORTION_K2)
+		flags|= REFINE_RADIAL_DISTORTION_K2;
+
+	return flags;
+}
+
+static int count_tracks_on_both_keyframes(MovieTracking *tracking)
+{
+	int tot= 0;
+	int frame1= tracking->settings.keyframe1, frame2= tracking->settings.keyframe2;
+	MovieTrackingTrack *track;
+
+	track= tracking->tracks.first;
+	while(track) {
+		if(BKE_tracking_has_marker(track, frame1))
+			if(BKE_tracking_has_marker(track, frame2))
+				tot++;
+
+		track= track->next;
+	}
+
+	return tot;
+}
+#endif
+
+int BKE_tracking_can_solve(MovieTracking *tracking, char *error_msg, int error_size)
+{
+#if WITH_LIBMV
+	if(count_tracks_on_both_keyframes(tracking)<8) {
+		BLI_strncpy(error_msg, "At least 8 tracks on both of keyframes are needed for reconstruction", error_size);
+		return 0;
+	}
+
+	return 1;
+#else
+	BLI_strncpy(error_msg, "Blender is compiled without motion tracking library", error_size);
+
+	return 0;
 #endif
+}
 
 float BKE_tracking_solve_reconstruction(MovieTracking *tracking, int width, int height)
 {
@@ -1384,6 +1467,7 @@ float BKE_tracking_solve_reconstruction(MovieTracking *tracking, int width, int
 		struct libmv_Tracks *tracks= create_libmv_tracks(tracking, width, height*aspy);
 		struct libmv_Reconstruction *reconstruction = libmv_solveReconstruction(tracks,
 		        tracking->settings.keyframe1, tracking->settings.keyframe2,
+		        get_refine_intrinsics_flags(tracking),
 		        camera->focal,
 		        camera->principal[0], camera->principal[1]*aspy,
 		        camera->k1, camera->k2, camera->k3);
diff --git a/source/blender/editors/space_clip/tracking_ops.c b/source/blender/editors/space_clip/tracking_ops.c
index e9006f5b1e9..1b08a9aee4c 100644
--- a/source/blender/editors/space_clip/tracking_ops.c
+++ b/source/blender/editors/space_clip/tracking_ops.c
@@ -1504,24 +1504,6 @@ void CLIP_OT_track_markers(wmOperatorType *ot)
 
 /********************** solve camera operator *********************/
 
-static int check_solve_track_count(MovieTracking *tracking)
-{
-	int tot= 0;
-	int frame1= tracking->settings.keyframe1, frame2= tracking->settings.keyframe2;
-	MovieTrackingTrack *track;
-
-	track= tracking->tracks.first;
-	while(track) {
-		if(BKE_tracking_has_marker(track, frame1))
-			if(BKE_tracking_has_marker(track, frame2))
-				tot++;
-
-		track= track->next;
-	}
-
-	return tot>=8;
-}
-
 static int solve_camera_exec(bContext *C, wmOperator *op)
 {
 	SpaceClip *sc= CTX_wm_space_clip(C);
@@ -1530,9 +1512,11 @@ static int solve_camera_exec(bContext *C, wmOperator *op)
 	MovieTracking *tracking= &clip->tracking;
 	int width, height;
 	float error;
+	char error_msg[255];
+
+	if(!BKE_tracking_can_solve(tracking, error_msg, sizeof(error_msg))) {
+		BKE_report(op->reports, RPT_ERROR, error_msg);
 
-	if(!check_solve_track_count(tracking)) {
-		BKE_report(op->reports, RPT_ERROR, "At least 8 tracks on both of keyframes are needed for reconstruction");
 		return OPERATOR_CANCELLED;
 	}
 
diff --git a/source/blender/makesdna/DNA_tracking_types.h b/source/blender/makesdna/DNA_tracking_types.h
index b359ea3544d..e1aff048626 100644
--- a/source/blender/makesdna/DNA_tracking_types.h
+++ b/source/blender/makesdna/DNA_tracking_types.h
@@ -123,6 +123,11 @@ typedef struct MovieTrackingSettings {
 	/* ** reconstruction settings ** */
 	int keyframe1, keyframe2;	/* two keyframes for reconstrution initialization */
 
+	/* ** which camera intrinsics to refine. uses on the REFINE_* flags */
+	short refine_camera_intrinsics;
+
+	char pad2[6];
+
 	/* ** tool settings ** */
 
 	/* set scale */
@@ -203,6 +208,12 @@ enum {
 #define TRACKING_SPEED_QUARTER		4
 #define TRACKING_SPEED_DOUBLE		5
 
+/* MovieTrackingSettings->refine_camera_intrinsics */
+#define REFINE_FOCAL_LENGTH			(1<<0)
+#define REFINE_PRINCIPAL_POINT		(1<<1)
+#define REFINE_RADIAL_DISTORTION_K1	(1<<2)
+#define REFINE_RADIAL_DISTORTION_K2	(1<<4)
+
 /* MovieTrackingStrabilization->flag */
 #define TRACKING_2D_STABILIZATION	(1<<0)
 #define TRACKING_AUTOSCALE			(1<<1)
diff --git a/source/blender/makesrna/intern/rna_tracking.c b/source/blender/makesrna/intern/rna_tracking.c
index 2c6384c75d8..3e783d06dc4 100644
--- a/source/blender/makesrna/intern/rna_tracking.c
+++ b/source/blender/makesrna/intern/rna_tracking.c
@@ -229,6 +229,23 @@ static void rna_def_trackingSettings(BlenderRNA *brna)
 		{0, NULL, 0, NULL, NULL}
 	};
 
+	static EnumPropertyItem refine_items[] = {
+		{0, "NONE", 0, "Nothing", "Do not refine camera intrinsics"},
+		{REFINE_FOCAL_LENGTH, "FOCAL_LENGTH", 0, "Focal Length", "Refine focal length"},
+		{REFINE_FOCAL_LENGTH|
+		 REFINE_PRINCIPAL_POINT, "FOCAL_LENGTH_PRINCIPAL_POINT", 0, "Focal Length, Principal Point", "Refine focal length and principal point"},
+		{REFINE_FOCAL_LENGTH|
+		 REFINE_PRINCIPAL_POINT|
+		 REFINE_RADIAL_DISTORTION_K1|
+		 REFINE_RADIAL_DISTORTION_K2,
+		 "FOCAL_LENGTH_PRINCIPAL_POINT_RADIAL_K1_K2", 0, "Focal Length, Principal Point, K1, K2", "Refine focal length, principal point and radial distortion K1 and K2"},
+		{REFINE_FOCAL_LENGTH|
+		 REFINE_RADIAL_DISTORTION_K1|
+		 REFINE_RADIAL_DISTORTION_K2, "FOCAL_LENGTH_RADIAL_K1_K2", 0, "Focal length, K1. K2", "Refine focal length and radial distortion K1 and K2"},
+		{REFINE_FOCAL_LENGTH|REFINE_RADIAL_DISTORTION_K1, "FOCAL_LENGTH_RADIAL_K1", 0, "Focal length, K1", "Refine focal length and radial distortion K1"},
+		{0, NULL, 0, NULL, NULL}
+	};
+
 	srna= RNA_def_struct(brna, "MovieTrackingSettings", NULL);
 	RNA_def_struct_ui_text(srna, "Movie tracking settings", "Match moving settings");
 
@@ -271,6 +288,13 @@ static void rna_def_trackingSettings(BlenderRNA *brna)
 	RNA_def_property_int_sdna(prop, NULL, "keyframe2");
 	RNA_def_property_ui_text(prop, "Keyframe B", "Second keyframe used for reconstruction initialization");
 
+	/* intrinsics refinement during bundle adjustment */
+	prop= RNA_def_property(srna, "refine_intrinsics", PROP_ENUM, PROP_NONE);
+	RNA_def_property_enum_sdna(prop, NULL, "refine_camera_intrinsics");
+	RNA_def_property_clear_flag(prop, PROP_ANIMATABLE);
+	RNA_def_property_enum_items(prop, refine_items);
+	RNA_def_property_ui_text(prop, "Refine", "Refine intrinsics during camera solving");
+
 	/* tool settings */
 
 	/* distance */