summaryrefslogtreecommitdiffstats
path: root/third_party/aom/aom_dsp/flow_estimation/corner_match.c
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--third_party/aom/aom_dsp/flow_estimation/corner_match.c317
1 files changed, 184 insertions, 133 deletions
diff --git a/third_party/aom/aom_dsp/flow_estimation/corner_match.c b/third_party/aom/aom_dsp/flow_estimation/corner_match.c
index dc7589a8c6..c78edb8910 100644
--- a/third_party/aom/aom_dsp/flow_estimation/corner_match.c
+++ b/third_party/aom/aom_dsp/flow_estimation/corner_match.c
@@ -17,62 +17,84 @@
#include "aom_dsp/flow_estimation/corner_detect.h"
#include "aom_dsp/flow_estimation/corner_match.h"
+#include "aom_dsp/flow_estimation/disflow.h"
#include "aom_dsp/flow_estimation/flow_estimation.h"
#include "aom_dsp/flow_estimation/ransac.h"
#include "aom_dsp/pyramid.h"
#include "aom_scale/yv12config.h"
-#define SEARCH_SZ 9
-#define SEARCH_SZ_BY2 ((SEARCH_SZ - 1) / 2)
-
#define THRESHOLD_NCC 0.75
-/* Compute var(frame) * MATCH_SZ_SQ over a MATCH_SZ by MATCH_SZ window of frame,
- centered at (x, y).
+/* Compute mean and standard deviation of pixels in a window of size
+ MATCH_SZ by MATCH_SZ centered at (x, y).
+ Store results into *mean and *one_over_stddev
+
+ Note: The output of this function is scaled by MATCH_SZ, as in
+ *mean = MATCH_SZ * <true mean> and
+ *one_over_stddev = 1 / (MATCH_SZ * <true stddev>)
+
+ Combined with the fact that we return 1/stddev rather than the standard
+ deviation itself, this allows us to completely avoid divisions in
+ aom_compute_correlation, which is much hotter than this function is.
+
+ Returns true if this feature point is usable, false otherwise.
*/
-static double compute_variance(const unsigned char *frame, int stride, int x,
- int y) {
+bool aom_compute_mean_stddev_c(const unsigned char *frame, int stride, int x,
+ int y, double *mean, double *one_over_stddev) {
int sum = 0;
int sumsq = 0;
- int var;
- int i, j;
- for (i = 0; i < MATCH_SZ; ++i)
- for (j = 0; j < MATCH_SZ; ++j) {
+ for (int i = 0; i < MATCH_SZ; ++i) {
+ for (int j = 0; j < MATCH_SZ; ++j) {
sum += frame[(i + y - MATCH_SZ_BY2) * stride + (j + x - MATCH_SZ_BY2)];
sumsq += frame[(i + y - MATCH_SZ_BY2) * stride + (j + x - MATCH_SZ_BY2)] *
frame[(i + y - MATCH_SZ_BY2) * stride + (j + x - MATCH_SZ_BY2)];
}
- var = sumsq * MATCH_SZ_SQ - sum * sum;
- return (double)var;
+ }
+ *mean = (double)sum / MATCH_SZ;
+ const double variance = sumsq - (*mean) * (*mean);
+ if (variance < MIN_FEATURE_VARIANCE) {
+ *one_over_stddev = 0.0;
+ return false;
+ }
+ *one_over_stddev = 1.0 / sqrt(variance);
+ return true;
}
-/* Compute corr(frame1, frame2) * MATCH_SZ * stddev(frame1), where the
- correlation/standard deviation are taken over MATCH_SZ by MATCH_SZ windows
- of each image, centered at (x1, y1) and (x2, y2) respectively.
+/* Compute corr(frame1, frame2) over a window of size MATCH_SZ by MATCH_SZ.
+ To save on computation, the mean and (1 divided by the) standard deviation
+ of the window in each frame are precomputed and passed into this function
+ as arguments.
*/
-double av1_compute_cross_correlation_c(const unsigned char *frame1, int stride1,
- int x1, int y1,
- const unsigned char *frame2, int stride2,
- int x2, int y2) {
+double aom_compute_correlation_c(const unsigned char *frame1, int stride1,
+ int x1, int y1, double mean1,
+ double one_over_stddev1,
+ const unsigned char *frame2, int stride2,
+ int x2, int y2, double mean2,
+ double one_over_stddev2) {
int v1, v2;
- int sum1 = 0;
- int sum2 = 0;
- int sumsq2 = 0;
int cross = 0;
- int var2, cov;
- int i, j;
- for (i = 0; i < MATCH_SZ; ++i)
- for (j = 0; j < MATCH_SZ; ++j) {
+ for (int i = 0; i < MATCH_SZ; ++i) {
+ for (int j = 0; j < MATCH_SZ; ++j) {
v1 = frame1[(i + y1 - MATCH_SZ_BY2) * stride1 + (j + x1 - MATCH_SZ_BY2)];
v2 = frame2[(i + y2 - MATCH_SZ_BY2) * stride2 + (j + x2 - MATCH_SZ_BY2)];
- sum1 += v1;
- sum2 += v2;
- sumsq2 += v2 * v2;
cross += v1 * v2;
}
- var2 = sumsq2 * MATCH_SZ_SQ - sum2 * sum2;
- cov = cross * MATCH_SZ_SQ - sum1 * sum2;
- return cov / sqrt((double)var2);
+ }
+
+ // Note: In theory, the calculations here "should" be
+ // covariance = cross / N^2 - mean1 * mean2
+ // correlation = covariance / (stddev1 * stddev2).
+ //
+ // However, because of the scaling in aom_compute_mean_stddev, the
+ // lines below actually calculate
+ // covariance * N^2 = cross - (mean1 * N) * (mean2 * N)
+ // correlation = (covariance * N^2) / ((stddev1 * N) * (stddev2 * N))
+ //
+ // ie. we have removed the need for a division, and still end up with the
+ // correct unscaled correlation (ie, in the range [-1, +1])
+ double covariance = cross - mean1 * mean2;
+ double correlation = covariance * (one_over_stddev1 * one_over_stddev2);
+ return correlation;
}
static int is_eligible_point(int pointx, int pointy, int width, int height) {
@@ -87,65 +109,14 @@ static int is_eligible_distance(int point1x, int point1y, int point2x,
(point1y - point2y) * (point1y - point2y)) <= thresh * thresh;
}
-static void improve_correspondence(const unsigned char *src,
- const unsigned char *ref, int width,
- int height, int src_stride, int ref_stride,
- Correspondence *correspondences,
- int num_correspondences) {
- int i;
- for (i = 0; i < num_correspondences; ++i) {
- int x, y, best_x = 0, best_y = 0;
- double best_match_ncc = 0.0;
- // For this algorithm, all points have integer coordinates.
- // It's a little more efficient to convert them to ints once,
- // before the inner loops
- int x0 = (int)correspondences[i].x;
- int y0 = (int)correspondences[i].y;
- int rx0 = (int)correspondences[i].rx;
- int ry0 = (int)correspondences[i].ry;
- for (y = -SEARCH_SZ_BY2; y <= SEARCH_SZ_BY2; ++y) {
- for (x = -SEARCH_SZ_BY2; x <= SEARCH_SZ_BY2; ++x) {
- double match_ncc;
- if (!is_eligible_point(rx0 + x, ry0 + y, width, height)) continue;
- if (!is_eligible_distance(x0, y0, rx0 + x, ry0 + y, width, height))
- continue;
- match_ncc = av1_compute_cross_correlation(src, src_stride, x0, y0, ref,
- ref_stride, rx0 + x, ry0 + y);
- if (match_ncc > best_match_ncc) {
- best_match_ncc = match_ncc;
- best_y = y;
- best_x = x;
- }
- }
- }
- correspondences[i].rx += best_x;
- correspondences[i].ry += best_y;
- }
- for (i = 0; i < num_correspondences; ++i) {
- int x, y, best_x = 0, best_y = 0;
- double best_match_ncc = 0.0;
- int x0 = (int)correspondences[i].x;
- int y0 = (int)correspondences[i].y;
- int rx0 = (int)correspondences[i].rx;
- int ry0 = (int)correspondences[i].ry;
- for (y = -SEARCH_SZ_BY2; y <= SEARCH_SZ_BY2; ++y)
- for (x = -SEARCH_SZ_BY2; x <= SEARCH_SZ_BY2; ++x) {
- double match_ncc;
- if (!is_eligible_point(x0 + x, y0 + y, width, height)) continue;
- if (!is_eligible_distance(x0 + x, y0 + y, rx0, ry0, width, height))
- continue;
- match_ncc = av1_compute_cross_correlation(
- ref, ref_stride, rx0, ry0, src, src_stride, x0 + x, y0 + y);
- if (match_ncc > best_match_ncc) {
- best_match_ncc = match_ncc;
- best_y = y;
- best_x = x;
- }
- }
- correspondences[i].x += best_x;
- correspondences[i].y += best_y;
- }
-}
+typedef struct {
+ int x;
+ int y;
+ double mean;
+ double one_over_stddev;
+ int best_match_idx;
+ double best_match_corr;
+} PointInfo;
static int determine_correspondence(const unsigned char *src,
const int *src_corners, int num_src_corners,
@@ -154,56 +125,136 @@ static int determine_correspondence(const unsigned char *src,
int width, int height, int src_stride,
int ref_stride,
Correspondence *correspondences) {
- // TODO(sarahparker) Improve this to include 2-way match
- int i, j;
+ PointInfo *src_point_info = NULL;
+ PointInfo *ref_point_info = NULL;
int num_correspondences = 0;
- for (i = 0; i < num_src_corners; ++i) {
- double best_match_ncc = 0.0;
- double template_norm;
- int best_match_j = -1;
- if (!is_eligible_point(src_corners[2 * i], src_corners[2 * i + 1], width,
- height))
+
+ src_point_info =
+ (PointInfo *)aom_calloc(num_src_corners, sizeof(*src_point_info));
+ if (!src_point_info) {
+ goto finished;
+ }
+
+ ref_point_info =
+ (PointInfo *)aom_calloc(num_ref_corners, sizeof(*ref_point_info));
+ if (!ref_point_info) {
+ goto finished;
+ }
+
+ // First pass (linear):
+ // Filter corner lists and compute per-patch means and standard deviations,
+ // for the src and ref frames independently
+ int src_point_count = 0;
+ for (int i = 0; i < num_src_corners; i++) {
+ int src_x = src_corners[2 * i];
+ int src_y = src_corners[2 * i + 1];
+ if (!is_eligible_point(src_x, src_y, width, height)) continue;
+
+ PointInfo *point = &src_point_info[src_point_count];
+ point->x = src_x;
+ point->y = src_y;
+ point->best_match_corr = THRESHOLD_NCC;
+ if (!aom_compute_mean_stddev(src, src_stride, src_x, src_y, &point->mean,
+ &point->one_over_stddev))
continue;
- for (j = 0; j < num_ref_corners; ++j) {
- double match_ncc;
- if (!is_eligible_point(ref_corners[2 * j], ref_corners[2 * j + 1], width,
- height))
- continue;
- if (!is_eligible_distance(src_corners[2 * i], src_corners[2 * i + 1],
- ref_corners[2 * j], ref_corners[2 * j + 1],
- width, height))
+ src_point_count++;
+ }
+ if (src_point_count == 0) {
+ goto finished;
+ }
+
+ int ref_point_count = 0;
+ for (int j = 0; j < num_ref_corners; j++) {
+ int ref_x = ref_corners[2 * j];
+ int ref_y = ref_corners[2 * j + 1];
+ if (!is_eligible_point(ref_x, ref_y, width, height)) continue;
+
+ PointInfo *point = &ref_point_info[ref_point_count];
+ point->x = ref_x;
+ point->y = ref_y;
+ point->best_match_corr = THRESHOLD_NCC;
+ if (!aom_compute_mean_stddev(ref, ref_stride, ref_x, ref_y, &point->mean,
+ &point->one_over_stddev))
+ continue;
+ ref_point_count++;
+ }
+ if (ref_point_count == 0) {
+ goto finished;
+ }
+
+ // Second pass (quadratic):
+ // For each pair of points, compute correlation, and use this to determine
+ // the best match of each corner, in both directions
+ for (int i = 0; i < src_point_count; ++i) {
+ PointInfo *src_point = &src_point_info[i];
+ for (int j = 0; j < ref_point_count; ++j) {
+ PointInfo *ref_point = &ref_point_info[j];
+ if (!is_eligible_distance(src_point->x, src_point->y, ref_point->x,
+ ref_point->y, width, height))
continue;
- match_ncc = av1_compute_cross_correlation(
- src, src_stride, src_corners[2 * i], src_corners[2 * i + 1], ref,
- ref_stride, ref_corners[2 * j], ref_corners[2 * j + 1]);
- if (match_ncc > best_match_ncc) {
- best_match_ncc = match_ncc;
- best_match_j = j;
+
+ double corr = aom_compute_correlation(
+ src, src_stride, src_point->x, src_point->y, src_point->mean,
+ src_point->one_over_stddev, ref, ref_stride, ref_point->x,
+ ref_point->y, ref_point->mean, ref_point->one_over_stddev);
+
+ if (corr > src_point->best_match_corr) {
+ src_point->best_match_idx = j;
+ src_point->best_match_corr = corr;
+ }
+ if (corr > ref_point->best_match_corr) {
+ ref_point->best_match_idx = i;
+ ref_point->best_match_corr = corr;
}
}
- // Note: We want to test if the best correlation is >= THRESHOLD_NCC,
- // but need to account for the normalization in
- // av1_compute_cross_correlation.
- template_norm = compute_variance(src, src_stride, src_corners[2 * i],
- src_corners[2 * i + 1]);
- if (best_match_ncc > THRESHOLD_NCC * sqrt(template_norm)) {
- correspondences[num_correspondences].x = src_corners[2 * i];
- correspondences[num_correspondences].y = src_corners[2 * i + 1];
- correspondences[num_correspondences].rx = ref_corners[2 * best_match_j];
- correspondences[num_correspondences].ry =
- ref_corners[2 * best_match_j + 1];
+ }
+
+ // Third pass (linear):
+ // Scan through source corners, generating a correspondence for each corner
+ // iff ref_best_match[src_best_match[i]] == i
+ // Then refine the generated correspondences using optical flow
+ for (int i = 0; i < src_point_count; i++) {
+ PointInfo *point = &src_point_info[i];
+
+ // Skip corners which were not matched, or which didn't find
+ // a good enough match
+ if (point->best_match_corr < THRESHOLD_NCC) continue;
+
+ PointInfo *match_point = &ref_point_info[point->best_match_idx];
+ if (match_point->best_match_idx == i) {
+ // Refine match using optical flow and store
+ const int sx = point->x;
+ const int sy = point->y;
+ const int rx = match_point->x;
+ const int ry = match_point->y;
+ double u = (double)(rx - sx);
+ double v = (double)(ry - sy);
+
+ const int patch_tl_x = sx - DISFLOW_PATCH_CENTER;
+ const int patch_tl_y = sy - DISFLOW_PATCH_CENTER;
+
+ aom_compute_flow_at_point(src, ref, patch_tl_x, patch_tl_y, width, height,
+ src_stride, &u, &v);
+
+ Correspondence *correspondence = &correspondences[num_correspondences];
+ correspondence->x = (double)sx;
+ correspondence->y = (double)sy;
+ correspondence->rx = (double)sx + u;
+ correspondence->ry = (double)sy + v;
num_correspondences++;
}
}
- improve_correspondence(src, ref, width, height, src_stride, ref_stride,
- correspondences, num_correspondences);
+
+finished:
+ aom_free(src_point_info);
+ aom_free(ref_point_info);
return num_correspondences;
}
bool av1_compute_global_motion_feature_match(
TransformationType type, YV12_BUFFER_CONFIG *src, YV12_BUFFER_CONFIG *ref,
- int bit_depth, MotionModel *motion_models, int num_motion_models,
- bool *mem_alloc_failed) {
+ int bit_depth, int downsample_level, MotionModel *motion_models,
+ int num_motion_models, bool *mem_alloc_failed) {
int num_correspondences;
Correspondence *correspondences;
ImagePyramid *src_pyramid = src->y_pyramid;
@@ -212,19 +263,19 @@ bool av1_compute_global_motion_feature_match(
CornerList *ref_corners = ref->corners;
// Precompute information we will need about each frame
- if (!aom_compute_pyramid(src, bit_depth, src_pyramid)) {
+ if (aom_compute_pyramid(src, bit_depth, 1, src_pyramid) < 0) {
*mem_alloc_failed = true;
return false;
}
- if (!av1_compute_corner_list(src_pyramid, src_corners)) {
+ if (!av1_compute_corner_list(src, bit_depth, downsample_level, src_corners)) {
*mem_alloc_failed = true;
return false;
}
- if (!aom_compute_pyramid(ref, bit_depth, ref_pyramid)) {
+ if (aom_compute_pyramid(ref, bit_depth, 1, ref_pyramid) < 0) {
*mem_alloc_failed = true;
return false;
}
- if (!av1_compute_corner_list(ref_pyramid, ref_corners)) {
+ if (!av1_compute_corner_list(src, bit_depth, downsample_level, ref_corners)) {
*mem_alloc_failed = true;
return false;
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-19 02:19:49 +0000