Tracking: Implement tracks average operator

Average selected tracks into the new one. This can be used to improve
stability of tracking on blurry or non-very-sharp feature shapes.

Averaging happens for all position, pattern corners and search area.
Disabled markers do not take effect on averaging. Keyframed flag is
copied from source.

Gaps in the source tracks will be linearly interpolated, to reduce
result track jump. Note that this only applies to gaps "inbetween".
This means that if an input track doesn't have markers in the
beginning/end of it, there is nothing to interpolate with and the
result track will jump.

Available from the Track panel, under the Merge category.

Differential Revision: https://developer.blender.org/D6323

release/scripts/startup/bl_ui/space_clip.py

@@ -502,7 +502,9 @@ class CLIP_PT_tools_tracking(CLIP_PT_tracking_panel, Panel):
         col = layout.column(align=True)
         row = col.row(align=True)
         row.label(text="Merge:")
-        row.operator("clip.join_tracks", text="Join Tracks")
+        sub = row.column()
+        sub.operator("clip.join_tracks", text="Join Tracks")
+        sub.operator("clip.average_tracks", text="Average Tracks")
 
 
 class CLIP_PT_tools_plane_tracking(CLIP_PT_tracking_panel, Panel):
@@ -1482,6 +1484,7 @@ class CLIP_MT_track(Menu):
         layout.separator()
 
         layout.operator("clip.join_tracks")
+        layout.operator("clip.average_tracks")
 
         layout.separator()
 
@@ -1608,6 +1611,7 @@ class CLIP_MT_tracking_context_menu(Menu):
             layout.separator()
 
             layout.operator("clip.join_tracks")
+            layout.operator("clip.average_tracks")
 
             layout.separator()
 

source/blender/blenkernel/BKE_tracking.h

@@ -89,6 +89,23 @@ struct MovieTrackingTrack *BKE_tracking_track_duplicate(struct MovieTrackingTrac
 void BKE_tracking_track_unique_name(struct ListBase *tracksbase, struct MovieTrackingTrack *track);
 void BKE_tracking_track_free(struct MovieTrackingTrack *track);
 
+void BKE_tracking_track_first_last_frame_get(const struct MovieTrackingTrack *track,
+                                             int *r_first_frame,
+                                             int *r_last_frame);
+
+void BKE_tracking_tracks_first_last_frame_minmax(/*const*/ struct MovieTrackingTrack **tracks,
+                                                 const int num_tracks,
+                                                 int *r_first_frame,
+                                                 int *r_last_frame);
+
+int BKE_tracking_count_selected_tracks_in_list(const struct ListBase *tracks_list);
+int BKE_tracking_count_selected_tracks_in_active_object(/*const*/ struct MovieTracking *tracking);
+
+/* Get array of selected tracks from the current active object in the tracking structure.
+ * If nothing is selected then the result is nullptr and `r_num_tracks` is set to 0. */
+struct MovieTrackingTrack **BKE_tracking_selected_tracks_in_active_object(
+    struct MovieTracking *tracking, int *r_num_tracks);
+
 void BKE_tracking_track_flag_set(struct MovieTrackingTrack *track, int area, int flag);
 void BKE_tracking_track_flag_clear(struct MovieTrackingTrack *track, int area, int flag);
 
@@ -96,10 +113,15 @@ bool BKE_tracking_track_has_marker_at_frame(struct MovieTrackingTrack *track, in
 bool BKE_tracking_track_has_enabled_marker_at_frame(struct MovieTrackingTrack *track, int framenr);
 
 void BKE_tracking_track_path_clear(struct MovieTrackingTrack *track, int ref_frame, int action);
+
 void BKE_tracking_tracks_join(struct MovieTracking *tracking,
                               struct MovieTrackingTrack *dst_track,
                               struct MovieTrackingTrack *src_track);
 
+void BKE_tracking_tracks_average(struct MovieTrackingTrack *dst_track,
+                                 /*const*/ struct MovieTrackingTrack **src_tracks,
+                                 const int num_src_tracks);
+
 struct MovieTrackingTrack *BKE_tracking_track_get_named(struct MovieTracking *tracking,
                                                         struct MovieTrackingObject *object,
                                                         const char *name);

source/blender/blenkernel/intern/tracking.c

@@ -587,15 +587,15 @@ MovieTrackingTrack *BKE_tracking_track_add(MovieTracking *tracking,
 {
   const MovieTrackingSettings *settings = &tracking->settings;
 
+  MovieTrackingTrack *track = BKE_tracking_track_add_empty(tracking, tracksbase);
+  MovieTrackingMarker marker;
+
   const float half_pattern_px = settings->default_pattern_size / 2.0f;
   const float half_search_px = settings->default_search_size / 2.0f;
 
   const float pattern_size[2] = {half_pattern_px / width, half_pattern_px / height};
   const float search_size[2] = {half_search_px / width, half_search_px / height};
 
-  MovieTrackingTrack *track = BKE_tracking_track_add_empty(tracking, tracksbase);
-
-  MovieTrackingMarker marker;
   memset(&marker, 0, sizeof(marker));
   marker.pos[0] = x;
   marker.pos[1] = y;
@@ -665,6 +665,86 @@ void BKE_tracking_track_free(MovieTrackingTrack *track)
   }
 }
 
+/* Get frame numbers of the very first and last markers.
+ * There is no check on whether the marker is enabled or not. */
+void BKE_tracking_track_first_last_frame_get(const MovieTrackingTrack *track,
+                                             int *r_first_frame,
+                                             int *r_last_frame)
+{
+  BLI_assert(track->markersnr > 0);
+  const int last_marker_index = track->markersnr - 1;
+  *r_first_frame = track->markers[0].framenr;
+  *r_last_frame = track->markers[last_marker_index].framenr;
+}
+
+/* Find the minimum starting frame and maximum ending frame within given set of
+ * tracks.
+ */
+void BKE_tracking_tracks_first_last_frame_minmax(/*const*/ MovieTrackingTrack **tracks,
+                                                 const int num_tracks,
+                                                 int *r_first_frame,
+                                                 int *r_last_frame)
+{
+  *r_first_frame = INT_MAX;
+  *r_last_frame = INT_MIN;
+  for (int i = 0; i < num_tracks; ++i) {
+    const struct MovieTrackingTrack *track = tracks[i];
+    int track_first_frame, track_last_frame;
+    BKE_tracking_track_first_last_frame_get(track, &track_first_frame, &track_last_frame);
+    *r_first_frame = min_ii(*r_first_frame, track_first_frame);
+    *r_last_frame = max_ii(*r_last_frame, track_last_frame);
+  }
+}
+
+int BKE_tracking_count_selected_tracks_in_list(const ListBase *tracks_list)
+{
+  int num_selected_tracks = 0;
+  LISTBASE_FOREACH (const MovieTrackingTrack *, track, tracks_list) {
+    if (TRACK_SELECTED(track)) {
+      ++num_selected_tracks;
+    }
+  }
+  return num_selected_tracks;
+}
+
+int BKE_tracking_count_selected_tracks_in_active_object(/*const*/ MovieTracking *tracking)
+{
+  ListBase *tracks_list = BKE_tracking_get_active_tracks(tracking);
+  return BKE_tracking_count_selected_tracks_in_list(tracks_list);
+}
+
+MovieTrackingTrack **BKE_tracking_selected_tracks_in_active_object(MovieTracking *tracking,
+                                                                   int *r_num_tracks)
+{
+  *r_num_tracks = 0;
+
+  ListBase *tracks_list = BKE_tracking_get_active_tracks(tracking);
+  if (tracks_list == NULL) {
+    return NULL;
+  }
+
+  /* Initialize input. */
+  const int num_selected_tracks = BKE_tracking_count_selected_tracks_in_active_object(tracking);
+  if (num_selected_tracks == 0) {
+    return NULL;
+  }
+
+  MovieTrackingTrack **source_tracks = MEM_malloc_arrayN(
+      num_selected_tracks, sizeof(MovieTrackingTrack *), "selected tracks array");
+  int source_track_index = 0;
+  LISTBASE_FOREACH (MovieTrackingTrack *, track, tracks_list) {
+    if (!TRACK_SELECTED(track)) {
+      continue;
+    }
+    source_tracks[source_track_index] = track;
+    ++source_track_index;
+  }
+
+  *r_num_tracks = num_selected_tracks;
+
+  return source_tracks;
+}
+
 /* Set flag for all specified track's areas.
  *
  * area - which part of marker should be selected. see TRACK_AREA_* constants.
@@ -918,6 +998,96 @@ void BKE_tracking_tracks_join(MovieTracking *tracking,
   BKE_tracking_dopesheet_tag_update(tracking);
 }
 
+static void accumulate_marker(MovieTrackingMarker *dst_marker,
+                              const MovieTrackingMarker *src_marker)
+{
+  BLI_assert(dst_marker->framenr == src_marker->framenr);
+
+  if (src_marker->flag & MARKER_DISABLED) {
+    return;
+  }
+
+  add_v2_v2(dst_marker->pos, src_marker->pos);
+  for (int corner = 0; corner < 4; ++corner) {
+    add_v2_v2(dst_marker->pattern_corners[corner], src_marker->pattern_corners[corner]);
+  }
+  add_v2_v2(dst_marker->search_min, src_marker->search_min);
+  add_v2_v2(dst_marker->search_max, src_marker->search_max);
+
+  BLI_assert(is_finite_v2(src_marker->search_min));
+  BLI_assert(is_finite_v2(src_marker->search_max));
+
+  dst_marker->flag &= ~MARKER_DISABLED;
+  if ((src_marker->flag & MARKER_TRACKED) == 0) {
+    dst_marker->flag &= ~MARKER_TRACKED;
+  }
+}
+
+static void multiply_marker(MovieTrackingMarker *marker, const float multiplier)
+{
+  mul_v2_fl(marker->pos, multiplier);
+  for (int corner = 0; corner < 4; ++corner) {
+    mul_v2_fl(marker->pattern_corners[corner], multiplier);
+  }
+  mul_v2_fl(marker->search_min, multiplier);
+  mul_v2_fl(marker->search_max, multiplier);
+}
+
+void BKE_tracking_tracks_average(MovieTrackingTrack *dst_track,
+                                 /*const*/ MovieTrackingTrack **src_tracks,
+                                 const int num_src_tracks)
+{
+  /* Get global range of frames within which averaging would happen. */
+  int first_frame, last_frame;
+  BKE_tracking_tracks_first_last_frame_minmax(
+      src_tracks, num_src_tracks, &first_frame, &last_frame);
+  if (last_frame < first_frame) {
+    return;
+  }
+  const int num_frames = last_frame - first_frame + 1;
+
+  /* Allocate temporary array where averaging will happen into. */
+  MovieTrackingMarker *accumulator = MEM_calloc_arrayN(
+      num_frames, sizeof(MovieTrackingMarker), "tracks average accumulator");
+  int *counters = MEM_calloc_arrayN(num_frames, sizeof(int), "tracks accumulator counters");
+  for (int frame = first_frame; frame <= last_frame; ++frame) {
+    const int frame_index = frame - first_frame;
+    accumulator[frame_index].framenr = frame;
+    accumulator[frame_index].flag |= (MARKER_DISABLED | MARKER_TRACKED);
+  }
+
+  /* Accumulate track markers. */
+  for (int track_index = 0; track_index < num_src_tracks; ++track_index) {
+    /*const*/ MovieTrackingTrack *track = src_tracks[track_index];
+    for (int frame = first_frame; frame <= last_frame; ++frame) {
+      MovieTrackingMarker interpolated_marker;
+      if (!BKE_tracking_marker_get_interpolated(track, frame, &interpolated_marker)) {
+        continue;
+      }
+      const int frame_index = frame - first_frame;
+      accumulate_marker(&accumulator[frame_index], &interpolated_marker);
+      ++counters[frame_index];
+    }
+  }
+
+  /* Average and store the result. */
+  for (int frame = first_frame; frame <= last_frame; ++frame) {
+    /* Average. */
+    const int frame_index = frame - first_frame;
+    if (!counters[frame_index]) {
+      continue;
+    }
+    const float multiplier = 1.0f / (float)counters[frame_index];
+    multiply_marker(&accumulator[frame_index], multiplier);
+    /* Store the result. */
+    BKE_tracking_marker_insert(dst_track, &accumulator[frame_index]);
+  }
+
+  /* Free memory. */
+  MEM_freeN(accumulator);
+  MEM_freeN(counters);
+}
+
 MovieTrackingTrack *BKE_tracking_track_get_named(MovieTracking *tracking,
                                                  MovieTrackingObject *object,
                                                  const char *name)

source/blender/editors/space_clip/clip_intern.h

@@ -191,6 +191,7 @@ void CLIP_OT_clear_solution(struct wmOperatorType *ot);
 
 void CLIP_OT_clear_track_path(struct wmOperatorType *ot);
 void CLIP_OT_join_tracks(struct wmOperatorType *ot);
+void CLIP_OT_average_tracks(struct wmOperatorType *ot);
 
 void CLIP_OT_disable_markers(struct wmOperatorType *ot);
 void CLIP_OT_hide_tracks(struct wmOperatorType *ot);

source/blender/editors/space_clip/space_clip.c

@@ -514,6 +514,7 @@ static void clip_operatortypes(void)
   /* clean-up */
   WM_operatortype_append(CLIP_OT_clear_track_path);
   WM_operatortype_append(CLIP_OT_join_tracks);
+  WM_operatortype_append(CLIP_OT_average_tracks);
   WM_operatortype_append(CLIP_OT_track_copy_color);
 
   WM_operatortype_append(CLIP_OT_clean_tracks);

source/blender/editors/space_clip/tracking_ops.c

@@ -1490,6 +1490,97 @@ void CLIP_OT_join_tracks(wmOperatorType *ot)
   ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
 }
 
+/********************** Average tracks operator *********************/
+
+static int average_tracks_exec(bContext *C, wmOperator *op)
+{
+  SpaceClip *space_clip = CTX_wm_space_clip(C);
+  MovieClip *clip = ED_space_clip_get_clip(space_clip);
+  MovieTracking *tracking = &clip->tracking;
+
+  /* Collect source tracks. */
+  int num_source_tracks;
+  MovieTrackingTrack **source_tracks = BKE_tracking_selected_tracks_in_active_object(
+      tracking, &num_source_tracks);
+  if (num_source_tracks == 0) {
+    return OPERATOR_CANCELLED;
+  }
+
+  /* Create new empty track, which will be the averaged result.
+   * Makes it simple to average all selection  to it. */
+  ListBase *tracks_list = BKE_tracking_get_active_tracks(tracking);
+  MovieTrackingTrack *result_track = BKE_tracking_track_add_empty(tracking, tracks_list);
+
+  /* Perform averaging. */
+  BKE_tracking_tracks_average(result_track, source_tracks, num_source_tracks);
+
+  const bool keep_original = RNA_boolean_get(op->ptr, "keep_original");
+  if (!keep_original) {
+    for (int i = 0; i < num_source_tracks; i++) {
+      clip_delete_track(C, clip, source_tracks[i]);
+    }
+  }
+
+  /* Update selection, making the result track active and selected. */
+  /* TODO(sergey): Should become some sort of utility function available for all operators. */
+
+  BKE_tracking_track_select(tracks_list, result_track, TRACK_AREA_ALL, 0);
+  ListBase *plane_tracks_list = BKE_tracking_get_active_plane_tracks(tracking);
+  BKE_tracking_plane_tracks_deselect_all(plane_tracks_list);
+
+  clip->tracking.act_track = result_track;
+  clip->tracking.act_plane_track = NULL;
+
+  /* Inform the dependency graph and interface about changes. */
+  DEG_id_tag_update(&clip->id, 0);
+  WM_event_add_notifier(C, NC_MOVIECLIP | NA_EDITED, clip);
+
+  /* Free memory. */
+  MEM_freeN(source_tracks);
+
+  return OPERATOR_FINISHED;
+}
+
+static int average_tracks_invoke(bContext *C, wmOperator *op, const wmEvent *UNUSED(event))
+{
+  PropertyRNA *prop_keep_original = RNA_struct_find_property(op->ptr, "keep_original");
+  if (!RNA_property_is_set(op->ptr, prop_keep_original)) {
+    SpaceClip *space_clip = CTX_wm_space_clip(C);
+    MovieClip *clip = ED_space_clip_get_clip(space_clip);
+    MovieTracking *tracking = &clip->tracking;
+
+    const int num_selected_tracks = BKE_tracking_count_selected_tracks_in_active_object(tracking);
+
+    if (num_selected_tracks == 1) {
+      RNA_property_boolean_set(op->ptr, prop_keep_original, false);
+    }
+  }
+
+  return average_tracks_exec(C, op);
+}
+
+void CLIP_OT_average_tracks(wmOperatorType *ot)
+{
+  /* Identifiers. */
+  ot->name = "Average Tracks";
+  ot->description = "Average selected tracks into active";
+  ot->idname = "CLIP_OT_average_tracks";
+
+  /* API callbacks. */
+  ot->exec = average_tracks_exec;
+  ot->invoke = average_tracks_invoke;
+  ot->poll = ED_space_clip_tracking_poll;
+
+  /* Flags. */
+  ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
+
+  /* Properties. */
+  PropertyRNA *prop;
+
+  prop = RNA_def_boolean(ot->srna, "keep_original", 1, "Keep Original", "Keep original tracks");
+  RNA_def_property_flag(prop, PROP_SKIP_SAVE);
+}
+
 /********************** lock tracks operator *********************/
 
 enum {