commit 36042696002856ab98f477991d5df424b81ffdf4
author Rachel Barker <rachelbarker@google.com> Wed Jan 11 18:09:43 2023 +0000
committer Rachel Barker <rachelbarker@google.com> Wed Jan 18 21:52:28 2023 +0000
tree 3129db15688e2700aa7bdfa0fa3b4aac397c065a
parent 738c4f4d8507f6c0eb8a8f6e25dde2df85569925

Use SSE instead of variance in RANSAC

Causes noise-level changes to both BDRATE and encode time

STATS_CHANGED

Change-Id: I2e66f04d712ed7eb2fec384d46f19e9e0f0bfa15

aom_dsp/flow_estimation/ransac.c

diff --git a/aom_dsp/flow_estimation/ransac.c b/aom_dsp/flow_estimation/ransac.c
index d153385..ab8d389 100644
--- a/aom_dsp/flow_estimation/ransac.c
+++ b/aom_dsp/flow_estimation/ransac.c
@@ -28,6 +28,7 @@
 #define MINPTS_MULTIPLIER 5
 
 #define INLIER_THRESHOLD 1.25
+#define INLIER_THRESHOLD_SQUARED (INLIER_THRESHOLD * INLIER_THRESHOLD)
 #define MIN_TRIALS 20
 
 // Flag to enable functions for finding TRANSLATION type models.
@@ -234,7 +235,7 @@
 
 typedef struct {
   int num_inliers;
-  double variance;
+  double sse;  // Sum of squared errors of inliers
   int *inlier_indices;
 } RANSAC_MOTION;
 
@@ -245,8 +246,8 @@
 
   if (motion_a->num_inliers > motion_b->num_inliers) return -1;
   if (motion_a->num_inliers < motion_b->num_inliers) return 1;
-  if (motion_a->variance < motion_b->variance) return -1;
-  if (motion_a->variance > motion_b->variance) return 1;
+  if (motion_a->sse < motion_b->sse) return -1;
+  if (motion_a->sse > motion_b->sse) return 1;
   return 0;
 }
 
@@ -264,11 +265,11 @@
   }
 }
 
-static const double kInfiniteVariance = 1e12;
+static const double kInfinity = 1e12;
 
 static void clear_motion(RANSAC_MOTION *motion, int num_points) {
   motion->num_inliers = 0;
-  motion->variance = kInfiniteVariance;
+  motion->sse = kInfinity;
   memset(motion->inlier_indices, 0,
          sizeof(*motion->inlier_indices) * num_points);
 }
@@ -340,9 +341,6 @@
   }
 
   while (MIN_TRIALS > trial_count) {
-    double sum_distance = 0.0;
-    double sum_distance_squared = 0.0;
-
     clear_motion(&current_motion, npoints);
 
     int degenerate = 1;
@@ -374,36 +372,31 @@
     model_info->project_points(params_this_motion, corners1, image1_coord,
                                npoints, 2, 2);
 
+    double sse = 0.0;
     for (i = 0; i < npoints; ++i) {
       double dx = image1_coord[i * 2] - corners2[i * 2];
       double dy = image1_coord[i * 2 + 1] - corners2[i * 2 + 1];
-      double distance = sqrt(dx * dx + dy * dy);
+      double squared_error = dx * dx + dy * dy;
 
-      if (distance < INLIER_THRESHOLD) {
+      if (squared_error < INLIER_THRESHOLD_SQUARED) {
         current_motion.inlier_indices[current_motion.num_inliers++] = i;
-        sum_distance += distance;
-        sum_distance_squared += distance * distance;
+        sse += squared_error;
       }
     }
 
     if (current_motion.num_inliers >= worst_kept_motion->num_inliers &&
         current_motion.num_inliers > 1) {
-      double mean_distance;
-      mean_distance = sum_distance / ((double)current_motion.num_inliers);
-      current_motion.variance =
-          sum_distance_squared / ((double)current_motion.num_inliers - 1.0) -
-          mean_distance * mean_distance * ((double)current_motion.num_inliers) /
-              ((double)current_motion.num_inliers - 1.0);
+      current_motion.sse = sse;
       if (is_better_motion(&current_motion, worst_kept_motion)) {
         // This motion is better than the worst currently kept motion. Remember
-        // the inlier points and variance. The parameters for each kept motion
+        // the inlier points and sse. The parameters for each kept motion
         // will be recomputed later using only the inliers.
         worst_kept_motion->num_inliers = current_motion.num_inliers;
-        worst_kept_motion->variance = current_motion.variance;
+        worst_kept_motion->sse = current_motion.sse;
         memcpy(worst_kept_motion->inlier_indices, current_motion.inlier_indices,
                sizeof(*current_motion.inlier_indices) * npoints);
         assert(npoints > 0);
-        // Determine the new worst kept motion and its num_inliers and variance.
+        // Determine the new worst kept motion and its num_inliers and sse.
         for (i = 0; i < num_desired_motions; ++i) {
           if (is_better_motion(worst_kept_motion, &motions[i])) {
             worst_kept_motion = &motions[i];