Line data Source code
1 : /*
2 : * Copyright (c) 2016, Alliance for Open Media. All rights reserved
3 : *
4 : * This source code is subject to the terms of the BSD 2 Clause License and
5 : * the Alliance for Open Media Patent License 1.0. If the BSD 2 Clause License
6 : * was not distributed with this source code in the LICENSE file, you can
7 : * obtain it at www.aomedia.org/license/software. If the Alliance for Open
8 : * Media Patent License 1.0 was not distributed with this source code in the
9 : * PATENTS file, you can obtain it at www.aomedia.org/license/patent.
10 : */
11 :
12 : #include <stdlib.h>
13 : #include <memory.h>
14 : #include <math.h>
15 :
16 : #include "./av1_rtcd.h"
17 : #include "av1/encoder/corner_match.h"
18 :
19 : #define SEARCH_SZ 9
20 : #define SEARCH_SZ_BY2 ((SEARCH_SZ - 1) / 2)
21 :
22 : #define THRESHOLD_NCC 0.75
23 :
24 : /* Compute var(im) * MATCH_SZ_SQ over a MATCH_SZ by MATCH_SZ window of im,
25 : centered at (x, y).
26 : */
27 0 : static double compute_variance(unsigned char *im, int stride, int x, int y) {
28 0 : int sum = 0;
29 0 : int sumsq = 0;
30 : int var;
31 : int i, j;
32 0 : for (i = 0; i < MATCH_SZ; ++i)
33 0 : for (j = 0; j < MATCH_SZ; ++j) {
34 0 : sum += im[(i + y - MATCH_SZ_BY2) * stride + (j + x - MATCH_SZ_BY2)];
35 0 : sumsq += im[(i + y - MATCH_SZ_BY2) * stride + (j + x - MATCH_SZ_BY2)] *
36 0 : im[(i + y - MATCH_SZ_BY2) * stride + (j + x - MATCH_SZ_BY2)];
37 : }
38 0 : var = sumsq * MATCH_SZ_SQ - sum * sum;
39 0 : return (double)var;
40 : }
41 :
42 : /* Compute corr(im1, im2) * MATCH_SZ * stddev(im1), where the
43 : correlation/standard deviation are taken over MATCH_SZ by MATCH_SZ windows
44 : of each image, centered at (x1, y1) and (x2, y2) respectively.
45 : */
46 0 : double compute_cross_correlation_c(unsigned char *im1, int stride1, int x1,
47 : int y1, unsigned char *im2, int stride2,
48 : int x2, int y2) {
49 : int v1, v2;
50 0 : int sum1 = 0;
51 0 : int sum2 = 0;
52 0 : int sumsq2 = 0;
53 0 : int cross = 0;
54 : int var2, cov;
55 : int i, j;
56 0 : for (i = 0; i < MATCH_SZ; ++i)
57 0 : for (j = 0; j < MATCH_SZ; ++j) {
58 0 : v1 = im1[(i + y1 - MATCH_SZ_BY2) * stride1 + (j + x1 - MATCH_SZ_BY2)];
59 0 : v2 = im2[(i + y2 - MATCH_SZ_BY2) * stride2 + (j + x2 - MATCH_SZ_BY2)];
60 0 : sum1 += v1;
61 0 : sum2 += v2;
62 0 : sumsq2 += v2 * v2;
63 0 : cross += v1 * v2;
64 : }
65 0 : var2 = sumsq2 * MATCH_SZ_SQ - sum2 * sum2;
66 0 : cov = cross * MATCH_SZ_SQ - sum1 * sum2;
67 0 : return cov / sqrt((double)var2);
68 : }
69 :
70 0 : static int is_eligible_point(int pointx, int pointy, int width, int height) {
71 0 : return (pointx >= MATCH_SZ_BY2 && pointy >= MATCH_SZ_BY2 &&
72 0 : pointx + MATCH_SZ_BY2 < width && pointy + MATCH_SZ_BY2 < height);
73 : }
74 :
75 0 : static int is_eligible_distance(int point1x, int point1y, int point2x,
76 : int point2y, int width, int height) {
77 0 : const int thresh = (width < height ? height : width) >> 4;
78 0 : return ((point1x - point2x) * (point1x - point2x) +
79 0 : (point1y - point2y) * (point1y - point2y)) <= thresh * thresh;
80 : }
81 :
82 0 : static void improve_correspondence(unsigned char *frm, unsigned char *ref,
83 : int width, int height, int frm_stride,
84 : int ref_stride,
85 : Correspondence *correspondences,
86 : int num_correspondences) {
87 : int i;
88 0 : for (i = 0; i < num_correspondences; ++i) {
89 0 : int x, y, best_x = 0, best_y = 0;
90 0 : double best_match_ncc = 0.0;
91 0 : for (y = -SEARCH_SZ_BY2; y <= SEARCH_SZ_BY2; ++y) {
92 0 : for (x = -SEARCH_SZ_BY2; x <= SEARCH_SZ_BY2; ++x) {
93 : double match_ncc;
94 0 : if (!is_eligible_point(correspondences[i].rx + x,
95 0 : correspondences[i].ry + y, width, height))
96 0 : continue;
97 0 : if (!is_eligible_distance(correspondences[i].x, correspondences[i].y,
98 0 : correspondences[i].rx + x,
99 0 : correspondences[i].ry + y, width, height))
100 0 : continue;
101 0 : match_ncc = compute_cross_correlation(
102 0 : frm, frm_stride, correspondences[i].x, correspondences[i].y, ref,
103 0 : ref_stride, correspondences[i].rx + x, correspondences[i].ry + y);
104 0 : if (match_ncc > best_match_ncc) {
105 0 : best_match_ncc = match_ncc;
106 0 : best_y = y;
107 0 : best_x = x;
108 : }
109 : }
110 : }
111 0 : correspondences[i].rx += best_x;
112 0 : correspondences[i].ry += best_y;
113 : }
114 0 : for (i = 0; i < num_correspondences; ++i) {
115 0 : int x, y, best_x = 0, best_y = 0;
116 0 : double best_match_ncc = 0.0;
117 0 : for (y = -SEARCH_SZ_BY2; y <= SEARCH_SZ_BY2; ++y)
118 0 : for (x = -SEARCH_SZ_BY2; x <= SEARCH_SZ_BY2; ++x) {
119 : double match_ncc;
120 0 : if (!is_eligible_point(correspondences[i].x + x,
121 0 : correspondences[i].y + y, width, height))
122 0 : continue;
123 0 : if (!is_eligible_distance(
124 0 : correspondences[i].x + x, correspondences[i].y + y,
125 0 : correspondences[i].rx, correspondences[i].ry, width, height))
126 0 : continue;
127 0 : match_ncc = compute_cross_correlation(
128 0 : ref, ref_stride, correspondences[i].rx, correspondences[i].ry, frm,
129 0 : frm_stride, correspondences[i].x + x, correspondences[i].y + y);
130 0 : if (match_ncc > best_match_ncc) {
131 0 : best_match_ncc = match_ncc;
132 0 : best_y = y;
133 0 : best_x = x;
134 : }
135 : }
136 0 : correspondences[i].x += best_x;
137 0 : correspondences[i].y += best_y;
138 : }
139 0 : }
140 :
141 0 : int determine_correspondence(unsigned char *frm, int *frm_corners,
142 : int num_frm_corners, unsigned char *ref,
143 : int *ref_corners, int num_ref_corners, int width,
144 : int height, int frm_stride, int ref_stride,
145 : int *correspondence_pts) {
146 : // TODO(sarahparker) Improve this to include 2-way match
147 : int i, j;
148 0 : Correspondence *correspondences = (Correspondence *)correspondence_pts;
149 0 : int num_correspondences = 0;
150 0 : for (i = 0; i < num_frm_corners; ++i) {
151 0 : double best_match_ncc = 0.0;
152 : double template_norm;
153 0 : int best_match_j = -1;
154 0 : if (!is_eligible_point(frm_corners[2 * i], frm_corners[2 * i + 1], width,
155 : height))
156 0 : continue;
157 0 : for (j = 0; j < num_ref_corners; ++j) {
158 : double match_ncc;
159 0 : if (!is_eligible_point(ref_corners[2 * j], ref_corners[2 * j + 1], width,
160 : height))
161 0 : continue;
162 0 : if (!is_eligible_distance(frm_corners[2 * i], frm_corners[2 * i + 1],
163 0 : ref_corners[2 * j], ref_corners[2 * j + 1],
164 : width, height))
165 0 : continue;
166 0 : match_ncc = compute_cross_correlation(
167 0 : frm, frm_stride, frm_corners[2 * i], frm_corners[2 * i + 1], ref,
168 0 : ref_stride, ref_corners[2 * j], ref_corners[2 * j + 1]);
169 0 : if (match_ncc > best_match_ncc) {
170 0 : best_match_ncc = match_ncc;
171 0 : best_match_j = j;
172 : }
173 : }
174 : // Note: We want to test if the best correlation is >= THRESHOLD_NCC,
175 : // but need to account for the normalization in compute_cross_correlation.
176 0 : template_norm = compute_variance(frm, frm_stride, frm_corners[2 * i],
177 0 : frm_corners[2 * i + 1]);
178 0 : if (best_match_ncc > THRESHOLD_NCC * sqrt(template_norm)) {
179 0 : correspondences[num_correspondences].x = frm_corners[2 * i];
180 0 : correspondences[num_correspondences].y = frm_corners[2 * i + 1];
181 0 : correspondences[num_correspondences].rx = ref_corners[2 * best_match_j];
182 0 : correspondences[num_correspondences].ry =
183 0 : ref_corners[2 * best_match_j + 1];
184 0 : num_correspondences++;
185 : }
186 : }
187 0 : improve_correspondence(frm, ref, width, height, frm_stride, ref_stride,
188 : correspondences, num_correspondences);
189 0 : return num_correspondences;
190 : }
|
