a7aab42915
Addressing comments, fixing style issues Change-Id: I91b72ab5cdf80d68476858f442616ab3af41e709
214 lines
8.6 KiB
C
214 lines
8.6 KiB
C
/*
|
|
* Copyright (c) 2015 The WebM project authors. All Rights Reserved.
|
|
*
|
|
* Use of this source code is governed by a BSD-style license
|
|
* that can be found in the LICENSE file in the root of the source
|
|
* tree. An additional intellectual property rights grant can be
|
|
* found in the file PATENTS. All contributing project authors may
|
|
* be found in the AUTHORS file in the root of the source tree.
|
|
*
|
|
*/
|
|
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <memory.h>
|
|
#include <math.h>
|
|
|
|
#include "vp9_corner_match.h"
|
|
|
|
#define MATCH_SZ 15
|
|
#define MATCH_SZ_BY2 ((MATCH_SZ - 1)/2)
|
|
#define MATCH_SZ_SQ (MATCH_SZ * MATCH_SZ)
|
|
#define SEARCH_SZ 9
|
|
#define SEARCH_SZ_BY2 ((SEARCH_SZ - 1)/2)
|
|
|
|
#define THRESHOLD_NCC 0.80
|
|
|
|
static double compute_variance(unsigned char *im, int stride,
|
|
int x, int y, double *mean) {
|
|
double sum = 0.0;
|
|
double sumsq = 0.0;
|
|
double var;
|
|
int i, j;
|
|
for (i = 0; i < MATCH_SZ; ++i)
|
|
for (j = 0; j < MATCH_SZ; ++j) {
|
|
sum += im[(i + y - MATCH_SZ_BY2) * stride + (j + x - MATCH_SZ_BY2)];
|
|
sumsq += im[(i + y - MATCH_SZ_BY2) * stride + (j + x - MATCH_SZ_BY2)] *
|
|
im[(i + y - MATCH_SZ_BY2) * stride + (j + x - MATCH_SZ_BY2)];
|
|
}
|
|
var = (sumsq * MATCH_SZ_SQ - sum * sum) / (MATCH_SZ_SQ * MATCH_SZ_SQ);
|
|
if (mean) *mean = sum / MATCH_SZ_SQ;
|
|
return var;
|
|
}
|
|
|
|
static double compute_cross_correlation(unsigned char *im1, int stride1,
|
|
int x1, int y1,
|
|
unsigned char *im2, int stride2,
|
|
int x2, int y2) {
|
|
double sum1 = 0;
|
|
double sum2 = 0;
|
|
double cross = 0;
|
|
double corr;
|
|
int i, j;
|
|
for (i = 0; i < MATCH_SZ; ++i)
|
|
for (j = 0; j < MATCH_SZ; ++j) {
|
|
sum1 += im1[(i + y1 - MATCH_SZ_BY2) * stride1 + (j + x1 - MATCH_SZ_BY2)];
|
|
sum2 += im2[(i + y2 - MATCH_SZ_BY2) * stride2 + (j + x2 - MATCH_SZ_BY2)];
|
|
cross += im1[(i + y1 - MATCH_SZ_BY2) * stride1 + (j + x1 - MATCH_SZ_BY2)] *
|
|
im2[(i + y2 - MATCH_SZ_BY2) * stride2 + (j + x2 - MATCH_SZ_BY2)];
|
|
}
|
|
corr = (cross * MATCH_SZ_SQ - sum1 * sum2) / (MATCH_SZ_SQ * MATCH_SZ_SQ);
|
|
return corr;
|
|
}
|
|
|
|
static int is_eligible_point(double pointx, double pointy,
|
|
int width, int height) {
|
|
return (pointx >= MATCH_SZ_BY2 && pointy >= MATCH_SZ_BY2 &&
|
|
pointx + MATCH_SZ_BY2 < width && pointy + MATCH_SZ_BY2 < height);
|
|
}
|
|
|
|
static int is_eligible_distance(double point1x, double point1y,
|
|
double point2x, double point2y,
|
|
int width, int height) {
|
|
const int thresh = (width < height ? height : width) >> 4;
|
|
return ((point1x - point2x) * (point1x - point2x) +
|
|
(point1y - point2y) * (point1y - point2y)) <= thresh * thresh;
|
|
}
|
|
|
|
static void improve_correspondence(unsigned char *frm, unsigned char *ref,
|
|
int width, int height,
|
|
int frm_stride, int ref_stride,
|
|
correspondence *correspondences,
|
|
int num_correspondences) {
|
|
int i;
|
|
for (i = 0; i < num_correspondences; ++i) {
|
|
double template_norm = compute_variance(frm, frm_stride,
|
|
correspondences[i].x,
|
|
correspondences[i].y, NULL);
|
|
int x, y, best_x = 0, best_y = 0;
|
|
double best_match_ncc = 0.0;
|
|
for (y = -SEARCH_SZ_BY2; y <= SEARCH_SZ_BY2; ++y) {
|
|
for (x = -SEARCH_SZ_BY2; x <= SEARCH_SZ_BY2; ++x) {
|
|
double match_ncc;
|
|
double subimage_norm;
|
|
if (!is_eligible_point(correspondences[i].rx + x,
|
|
correspondences[i].ry + y,
|
|
width, height))
|
|
continue;
|
|
if (!is_eligible_distance(
|
|
correspondences[i].x, correspondences[i].y,
|
|
correspondences[i].rx + x, correspondences[i].ry + y,
|
|
width, height))
|
|
continue;
|
|
subimage_norm = compute_variance(ref, ref_stride,
|
|
correspondences[i].rx + x,
|
|
correspondences[i].ry + y, NULL);
|
|
match_ncc = compute_cross_correlation(
|
|
frm, frm_stride,
|
|
correspondences[i].x, correspondences[i].y,
|
|
ref, ref_stride,
|
|
correspondences[i].rx + x, correspondences[i].ry + y) /
|
|
sqrt(template_norm * subimage_norm);
|
|
if (match_ncc > best_match_ncc) {
|
|
best_match_ncc = match_ncc;
|
|
best_y = y;
|
|
best_x = x;
|
|
}
|
|
}
|
|
}
|
|
correspondences[i].rx += (double) best_x;
|
|
correspondences[i].ry += (double) best_y;
|
|
}
|
|
for (i = 0; i < num_correspondences; ++i) {
|
|
double template_norm = compute_variance(
|
|
ref, ref_stride, correspondences[i].rx, correspondences[i].ry, NULL);
|
|
int x, y, best_x = 0, best_y = 0;
|
|
double best_match_ncc = 0.0;
|
|
for (y = -SEARCH_SZ_BY2; y <= SEARCH_SZ_BY2; ++y)
|
|
for (x = -SEARCH_SZ_BY2; x <= SEARCH_SZ_BY2; ++x) {
|
|
double match_ncc;
|
|
double subimage_norm;
|
|
if (!is_eligible_point(correspondences[i].x + x,
|
|
correspondences[i].y + y, width, height))
|
|
continue;
|
|
if (!is_eligible_distance(
|
|
correspondences[i].x + x, correspondences[i].y + y,
|
|
correspondences[i].rx, correspondences[i].ry, width, height))
|
|
continue;
|
|
subimage_norm = compute_variance(
|
|
frm, frm_stride,
|
|
correspondences[i].x + x, correspondences[i].y + y, NULL);
|
|
match_ncc = compute_cross_correlation(
|
|
frm, frm_stride, correspondences[i].x + x, correspondences[i].y + y,
|
|
ref, ref_stride, correspondences[i].rx, correspondences[i].ry) /
|
|
sqrt(template_norm * subimage_norm);
|
|
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;
|
|
}
|
|
}
|
|
|
|
int determine_correspondence(unsigned char *frm,
|
|
int *frm_corners, int num_frm_corners,
|
|
unsigned char *ref,
|
|
int *ref_corners, int num_ref_corners,
|
|
int width, int height,
|
|
int frm_stride, int ref_stride,
|
|
double *correspondence_pts) {
|
|
// Debargha: Improve this to include 2-way match
|
|
int i, j;
|
|
correspondence *correspondences = (correspondence *)correspondence_pts;
|
|
int num_correspondences = 0;
|
|
for (i = 0; i < num_frm_corners; ++i) {
|
|
double best_match_ncc = 0.0;
|
|
double template_norm;
|
|
int best_match_j = -1;
|
|
if (!is_eligible_point(frm_corners[2 * i], frm_corners[2 * i + 1],
|
|
width, height))
|
|
continue;
|
|
template_norm = compute_variance(
|
|
frm, frm_stride, frm_corners[2 * i], frm_corners[2*i+1], NULL);
|
|
for (j = 0; j < num_ref_corners; ++j) {
|
|
double match_ncc;
|
|
double subimage_norm;
|
|
if (!is_eligible_point(ref_corners[2 * j], ref_corners[2 * j + 1],
|
|
width, height))
|
|
continue;
|
|
if (!is_eligible_distance(frm_corners[2 * i], frm_corners[2 * i + 1],
|
|
ref_corners[2 * j], ref_corners[2 * j + 1],
|
|
width, height))
|
|
continue;
|
|
subimage_norm = compute_variance(
|
|
ref, ref_stride, ref_corners[2*j], ref_corners[2 * j + 1], NULL);
|
|
match_ncc = compute_cross_correlation(frm, frm_stride,
|
|
frm_corners[2 * i],
|
|
frm_corners[2 * i + 1],
|
|
ref, ref_stride,
|
|
ref_corners[2 * j],
|
|
ref_corners[2 * j + 1]) /
|
|
sqrt(template_norm * subimage_norm);
|
|
if (match_ncc > best_match_ncc) {
|
|
best_match_ncc = match_ncc;
|
|
best_match_j = j;
|
|
}
|
|
}
|
|
if (best_match_ncc > THRESHOLD_NCC) {
|
|
correspondences[num_correspondences].x = (double) frm_corners[2 * i];
|
|
correspondences[num_correspondences].y = (double) frm_corners[2 * i + 1];
|
|
correspondences[num_correspondences].rx = (double)
|
|
ref_corners[2 * best_match_j];
|
|
correspondences[num_correspondences].ry = (double)
|
|
ref_corners[2 * best_match_j + 1];
|
|
num_correspondences++;
|
|
}
|
|
}
|
|
improve_correspondence(frm, ref, width, height, frm_stride, ref_stride,
|
|
correspondences, num_correspondences);
|
|
return num_correspondences;
|
|
}
|