global_motion.c (21139B)
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 <stdio.h> 13 #include <stdlib.h> 14 #include <stdbool.h> 15 #include <memory.h> 16 #include <math.h> 17 #include <assert.h> 18 19 #include "config/aom_dsp_rtcd.h" 20 21 #include "av1/encoder/global_motion.h" 22 23 #include "av1/common/convolve.h" 24 #include "av1/common/warped_motion.h" 25 26 #include "av1/encoder/segmentation.h" 27 28 #define MIN_TRANS_THRESH (1 * GM_TRANS_DECODE_FACTOR) 29 30 // Border over which to compute the global motion 31 #define ERRORADV_BORDER 0 32 33 int av1_is_enough_erroradvantage(double best_erroradvantage, int params_cost, 34 double gm_erroradv_tr) { 35 return best_erroradvantage < gm_erroradv_tr && 36 best_erroradvantage * params_cost < erroradv_prod_tr; 37 } 38 39 static void convert_to_params(const double *params, int32_t *model) { 40 int i; 41 model[0] = (int32_t)floor(params[0] * (1 << GM_TRANS_PREC_BITS) + 0.5); 42 model[1] = (int32_t)floor(params[1] * (1 << GM_TRANS_PREC_BITS) + 0.5); 43 model[0] = (int32_t)clamp(model[0], GM_TRANS_MIN, GM_TRANS_MAX) * 44 GM_TRANS_DECODE_FACTOR; 45 model[1] = (int32_t)clamp(model[1], GM_TRANS_MIN, GM_TRANS_MAX) * 46 GM_TRANS_DECODE_FACTOR; 47 48 for (i = 2; i < 6; ++i) { 49 const int diag_value = ((i == 2 || i == 5) ? (1 << GM_ALPHA_PREC_BITS) : 0); 50 model[i] = (int32_t)floor(params[i] * (1 << GM_ALPHA_PREC_BITS) + 0.5); 51 model[i] = 52 (int32_t)clamp(model[i] - diag_value, GM_ALPHA_MIN, GM_ALPHA_MAX); 53 model[i] = (model[i] + diag_value) * GM_ALPHA_DECODE_FACTOR; 54 } 55 } 56 57 void av1_convert_model_to_params(const double *params, 58 WarpedMotionParams *model) { 59 convert_to_params(params, model->wmmat); 60 model->wmtype = get_wmtype(model); 61 model->invalid = 0; 62 } 63 64 // Adds some offset to a global motion parameter and handles 65 // all of the necessary precision shifts, clamping, and 66 // zero-centering. 67 static int32_t add_param_offset(int param_index, int32_t param_value, 68 int32_t offset) { 69 const int scale_vals[2] = { GM_TRANS_PREC_DIFF, GM_ALPHA_PREC_DIFF }; 70 const int clamp_vals[2] = { GM_TRANS_MAX, GM_ALPHA_MAX }; 71 // type of param: 0 - translation, 1 - affine 72 const int param_type = (param_index < 2 ? 0 : 1); 73 const int is_one_centered = (param_index == 2 || param_index == 5); 74 75 // Make parameter zero-centered and offset the shift that was done to make 76 // it compatible with the warped model 77 param_value = (param_value - (is_one_centered << WARPEDMODEL_PREC_BITS)) >> 78 scale_vals[param_type]; 79 // Add desired offset to the rescaled/zero-centered parameter 80 param_value += offset; 81 // Clamp the parameter so it does not overflow the number of bits allotted 82 // to it in the bitstream 83 param_value = (int32_t)clamp(param_value, -clamp_vals[param_type], 84 clamp_vals[param_type]); 85 // Rescale the parameter to WARPEDMODEL_PRECISION_BITS so it is compatible 86 // with the warped motion library 87 param_value *= (1 << scale_vals[param_type]); 88 89 // Undo the zero-centering step if necessary 90 return param_value + (is_one_centered << WARPEDMODEL_PREC_BITS); 91 } 92 93 static void force_wmtype(WarpedMotionParams *wm, TransformationType wmtype) { 94 switch (wmtype) { 95 case IDENTITY: 96 wm->wmmat[0] = 0; 97 wm->wmmat[1] = 0; 98 AOM_FALLTHROUGH_INTENDED; 99 case TRANSLATION: 100 wm->wmmat[2] = 1 << WARPEDMODEL_PREC_BITS; 101 wm->wmmat[3] = 0; 102 AOM_FALLTHROUGH_INTENDED; 103 case ROTZOOM: 104 wm->wmmat[4] = -wm->wmmat[3]; 105 wm->wmmat[5] = wm->wmmat[2]; 106 AOM_FALLTHROUGH_INTENDED; 107 case AFFINE: break; 108 default: assert(0); 109 } 110 wm->wmtype = wmtype; 111 } 112 113 #if CONFIG_AV1_HIGHBITDEPTH 114 static inline int generic_sad_highbd(const uint16_t *const ref, int ref_stride, 115 const uint16_t *const dst, int dst_stride, 116 int p_width, int p_height) { 117 // This function should only be called for patches smaller than 118 // WARP_ERROR_BLOCK x WARP_ERROR_BLOCK. This keeps the number of pixels 119 // small enough that we don't need a 64-bit accumulator 120 assert(p_width <= WARP_ERROR_BLOCK && p_height <= WARP_ERROR_BLOCK); 121 122 int sad = 0; 123 for (int i = 0; i < p_height; ++i) { 124 for (int j = 0; j < p_width; ++j) { 125 sad += abs(dst[j + i * dst_stride] - ref[j + i * ref_stride]); 126 } 127 } 128 return sad; 129 } 130 131 #if WARP_ERROR_BLOCK != 32 132 #error "Need to change SAD call size in highbd_segmented_frame_error" 133 #endif // WARP_ERROR_BLOCK != 32 134 static int64_t highbd_segmented_frame_error( 135 const uint16_t *const ref, int ref_stride, const uint16_t *const dst, 136 int dst_stride, int p_width, int p_height, int bd, uint8_t *segment_map, 137 int segment_map_stride) { 138 (void)bd; 139 int patch_w, patch_h; 140 const int error_bsize_w = AOMMIN(p_width, WARP_ERROR_BLOCK); 141 const int error_bsize_h = AOMMIN(p_height, WARP_ERROR_BLOCK); 142 int64_t sum_error = 0; 143 for (int i = 0; i < p_height; i += WARP_ERROR_BLOCK) { 144 for (int j = 0; j < p_width; j += WARP_ERROR_BLOCK) { 145 int seg_x = j >> WARP_ERROR_BLOCK_LOG; 146 int seg_y = i >> WARP_ERROR_BLOCK_LOG; 147 // Only compute the error if this block contains inliers from the motion 148 // model 149 if (!segment_map[seg_y * segment_map_stride + seg_x]) continue; 150 151 // avoid computing error into the frame padding 152 patch_w = AOMMIN(error_bsize_w, p_width - j); 153 patch_h = AOMMIN(error_bsize_h, p_height - i); 154 155 if (patch_w == WARP_ERROR_BLOCK && patch_h == WARP_ERROR_BLOCK) { 156 sum_error += aom_highbd_sad32x32( 157 CONVERT_TO_BYTEPTR(ref + j + i * ref_stride), ref_stride, 158 CONVERT_TO_BYTEPTR(dst + j + i * dst_stride), dst_stride); 159 } else { 160 sum_error += generic_sad_highbd(ref + j + i * ref_stride, ref_stride, 161 dst + j + i * dst_stride, dst_stride, 162 patch_w, patch_h); 163 } 164 } 165 } 166 return sum_error; 167 } 168 169 #if WARP_ERROR_BLOCK != 32 170 #error "Need to change SAD call size in highbd_warp_error" 171 #endif // WARP_ERROR_BLOCK != 32 172 static int64_t highbd_warp_error(WarpedMotionParams *wm, 173 const uint16_t *const ref, int ref_width, 174 int ref_height, int ref_stride, 175 const uint16_t *const dst, int dst_stride, 176 int p_col, int p_row, int p_width, 177 int p_height, int subsampling_x, 178 int subsampling_y, int bd, int64_t best_error, 179 uint8_t *segment_map, int segment_map_stride) { 180 int64_t gm_sumerr = 0; 181 const int error_bsize_w = AOMMIN(p_width, WARP_ERROR_BLOCK); 182 const int error_bsize_h = AOMMIN(p_height, WARP_ERROR_BLOCK); 183 DECLARE_ALIGNED(32, uint16_t, tmp[WARP_ERROR_BLOCK * WARP_ERROR_BLOCK]); 184 185 ConvolveParams conv_params = get_conv_params(0, 0, bd); 186 conv_params.use_dist_wtd_comp_avg = 0; 187 for (int i = p_row; i < p_row + p_height; i += WARP_ERROR_BLOCK) { 188 for (int j = p_col; j < p_col + p_width; j += WARP_ERROR_BLOCK) { 189 int seg_x = j >> WARP_ERROR_BLOCK_LOG; 190 int seg_y = i >> WARP_ERROR_BLOCK_LOG; 191 // Only compute the error if this block contains inliers from the motion 192 // model 193 if (!segment_map[seg_y * segment_map_stride + seg_x]) continue; 194 // avoid warping extra 8x8 blocks in the padded region of the frame 195 // when p_width and p_height are not multiples of WARP_ERROR_BLOCK 196 const int warp_w = AOMMIN(error_bsize_w, p_col + ref_width - j); 197 const int warp_h = AOMMIN(error_bsize_h, p_row + ref_height - i); 198 highbd_warp_plane(wm, ref, ref_width, ref_height, ref_stride, tmp, j, i, 199 warp_w, warp_h, WARP_ERROR_BLOCK, subsampling_x, 200 subsampling_y, bd, &conv_params); 201 202 if (warp_w == WARP_ERROR_BLOCK && warp_h == WARP_ERROR_BLOCK) { 203 gm_sumerr += aom_highbd_sad32x32( 204 CONVERT_TO_BYTEPTR(tmp), WARP_ERROR_BLOCK, 205 CONVERT_TO_BYTEPTR(dst + j + i * dst_stride), dst_stride); 206 } else { 207 gm_sumerr += 208 generic_sad_highbd(tmp, WARP_ERROR_BLOCK, dst + j + i * dst_stride, 209 dst_stride, warp_w, warp_h); 210 } 211 212 if (gm_sumerr > best_error) return INT64_MAX; 213 } 214 } 215 return gm_sumerr; 216 } 217 #endif 218 219 static inline int generic_sad(const uint8_t *const ref, int ref_stride, 220 const uint8_t *const dst, int dst_stride, 221 int p_width, int p_height) { 222 // This function should only be called for patches smaller than 223 // WARP_ERROR_BLOCK x WARP_ERROR_BLOCK. This keeps the number of pixels 224 // small enough that we don't need a 64-bit accumulator 225 assert(p_width <= WARP_ERROR_BLOCK && p_height <= WARP_ERROR_BLOCK); 226 227 int sad = 0; 228 for (int i = 0; i < p_height; ++i) { 229 for (int j = 0; j < p_width; ++j) { 230 sad += abs(dst[j + i * dst_stride] - ref[j + i * ref_stride]); 231 } 232 } 233 return sad; 234 } 235 236 #if WARP_ERROR_BLOCK != 32 237 #error "Need to change SAD call size in segmented_warp_error" 238 #endif // WARP_ERROR_BLOCK != 32 239 static int64_t segmented_frame_error(const uint8_t *const ref, int ref_stride, 240 const uint8_t *const dst, int dst_stride, 241 int p_width, int p_height, 242 uint8_t *segment_map, 243 int segment_map_stride) { 244 int patch_w, patch_h; 245 const int error_bsize_w = AOMMIN(p_width, WARP_ERROR_BLOCK); 246 const int error_bsize_h = AOMMIN(p_height, WARP_ERROR_BLOCK); 247 int64_t sum_error = 0; 248 for (int i = 0; i < p_height; i += WARP_ERROR_BLOCK) { 249 for (int j = 0; j < p_width; j += WARP_ERROR_BLOCK) { 250 int seg_x = j >> WARP_ERROR_BLOCK_LOG; 251 int seg_y = i >> WARP_ERROR_BLOCK_LOG; 252 // Only compute the error if this block contains inliers from the motion 253 // model 254 if (!segment_map[seg_y * segment_map_stride + seg_x]) continue; 255 256 // avoid computing error into the frame padding 257 patch_w = AOMMIN(error_bsize_w, p_width - j); 258 patch_h = AOMMIN(error_bsize_h, p_height - i); 259 260 if (patch_w == WARP_ERROR_BLOCK && patch_h == WARP_ERROR_BLOCK) { 261 sum_error += aom_sad32x32(ref + j + i * ref_stride, ref_stride, 262 dst + j + i * dst_stride, dst_stride); 263 } else { 264 sum_error += 265 generic_sad(ref + j + i * ref_stride, ref_stride, 266 dst + j + i * dst_stride, dst_stride, patch_w, patch_h); 267 } 268 } 269 } 270 return sum_error; 271 } 272 273 #if WARP_ERROR_BLOCK != 32 274 #error "Need to change SAD call size in warp_error" 275 #endif // WARP_ERROR_BLOCK != 32 276 static int64_t warp_error(WarpedMotionParams *wm, const uint8_t *const ref, 277 int ref_width, int ref_height, int ref_stride, 278 const uint8_t *const dst, int dst_stride, int p_col, 279 int p_row, int p_width, int p_height, 280 int subsampling_x, int subsampling_y, 281 int64_t best_error, uint8_t *segment_map, 282 int segment_map_stride) { 283 int64_t gm_sumerr = 0; 284 int warp_w, warp_h; 285 const int error_bsize_w = AOMMIN(p_width, WARP_ERROR_BLOCK); 286 const int error_bsize_h = AOMMIN(p_height, WARP_ERROR_BLOCK); 287 DECLARE_ALIGNED(16, uint8_t, tmp[WARP_ERROR_BLOCK * WARP_ERROR_BLOCK]); 288 ConvolveParams conv_params = get_conv_params(0, 0, 8); 289 conv_params.use_dist_wtd_comp_avg = 0; 290 291 for (int i = p_row; i < p_row + p_height; i += WARP_ERROR_BLOCK) { 292 for (int j = p_col; j < p_col + p_width; j += WARP_ERROR_BLOCK) { 293 int seg_x = j >> WARP_ERROR_BLOCK_LOG; 294 int seg_y = i >> WARP_ERROR_BLOCK_LOG; 295 // Only compute the error if this block contains inliers from the motion 296 // model 297 if (!segment_map[seg_y * segment_map_stride + seg_x]) continue; 298 // avoid warping extra 8x8 blocks in the padded region of the frame 299 // when p_width and p_height are not multiples of WARP_ERROR_BLOCK 300 warp_w = AOMMIN(error_bsize_w, p_col + ref_width - j); 301 warp_h = AOMMIN(error_bsize_h, p_row + ref_height - i); 302 warp_plane(wm, ref, ref_width, ref_height, ref_stride, tmp, j, i, warp_w, 303 warp_h, WARP_ERROR_BLOCK, subsampling_x, subsampling_y, 304 &conv_params); 305 306 if (warp_w == WARP_ERROR_BLOCK && warp_h == WARP_ERROR_BLOCK) { 307 gm_sumerr += aom_sad32x32(tmp, WARP_ERROR_BLOCK, 308 dst + j + i * dst_stride, dst_stride); 309 } else { 310 gm_sumerr += 311 generic_sad(tmp, WARP_ERROR_BLOCK, dst + j + i * dst_stride, 312 dst_stride, warp_w, warp_h); 313 } 314 315 if (gm_sumerr > best_error) return INT64_MAX; 316 } 317 } 318 return gm_sumerr; 319 } 320 321 int64_t av1_segmented_frame_error(int use_hbd, int bd, const uint8_t *ref, 322 int ref_stride, uint8_t *dst, int dst_stride, 323 int p_width, int p_height, 324 uint8_t *segment_map, 325 int segment_map_stride) { 326 #if CONFIG_AV1_HIGHBITDEPTH 327 if (use_hbd) { 328 return highbd_segmented_frame_error( 329 CONVERT_TO_SHORTPTR(ref), ref_stride, CONVERT_TO_SHORTPTR(dst), 330 dst_stride, p_width, p_height, bd, segment_map, segment_map_stride); 331 } 332 #endif 333 (void)use_hbd; 334 (void)bd; 335 return segmented_frame_error(ref, ref_stride, dst, dst_stride, p_width, 336 p_height, segment_map, segment_map_stride); 337 } 338 339 // Returns the error between the result of applying motion 'wm' to the frame 340 // described by 'ref' and the frame described by 'dst'. 341 static int64_t get_warp_error(WarpedMotionParams *wm, int use_hbd, int bd, 342 const uint8_t *ref, int ref_width, int ref_height, 343 int ref_stride, uint8_t *dst, int dst_stride, 344 int p_col, int p_row, int p_width, int p_height, 345 int subsampling_x, int subsampling_y, 346 int64_t best_error, uint8_t *segment_map, 347 int segment_map_stride) { 348 if (!av1_get_shear_params(wm)) return INT64_MAX; 349 #if CONFIG_AV1_HIGHBITDEPTH 350 if (use_hbd) 351 return highbd_warp_error(wm, CONVERT_TO_SHORTPTR(ref), ref_width, 352 ref_height, ref_stride, CONVERT_TO_SHORTPTR(dst), 353 dst_stride, p_col, p_row, p_width, p_height, 354 subsampling_x, subsampling_y, bd, best_error, 355 segment_map, segment_map_stride); 356 #endif 357 (void)use_hbd; 358 (void)bd; 359 return warp_error(wm, ref, ref_width, ref_height, ref_stride, dst, dst_stride, 360 p_col, p_row, p_width, p_height, subsampling_x, 361 subsampling_y, best_error, segment_map, segment_map_stride); 362 } 363 364 int64_t av1_refine_integerized_param( 365 WarpedMotionParams *wm, TransformationType wmtype, int use_hbd, int bd, 366 uint8_t *ref, int r_width, int r_height, int r_stride, uint8_t *dst, 367 int d_width, int d_height, int d_stride, int n_refinements, 368 int64_t ref_frame_error, uint8_t *segment_map, int segment_map_stride, 369 double gm_erroradv_tr) { 370 static const int max_trans_model_params[TRANS_TYPES] = { 0, 2, 4, 6 }; 371 const int border = ERRORADV_BORDER; 372 int i = 0, p; 373 int n_params = max_trans_model_params[wmtype]; 374 int32_t *param_mat = wm->wmmat; 375 int64_t step_error, best_error; 376 int32_t step; 377 int32_t *param; 378 int32_t curr_param; 379 int32_t best_param; 380 381 force_wmtype(wm, wmtype); 382 wm->wmtype = get_wmtype(wm); 383 384 if (n_refinements == 0) { 385 // Compute the maximum error value that will be accepted, so that 386 // get_warp_error can terminate early if it proves the model will not 387 // be accepted. 388 int64_t selection_threshold = 389 (int64_t)lrint(ref_frame_error * gm_erroradv_tr); 390 return get_warp_error(wm, use_hbd, bd, ref, r_width, r_height, r_stride, 391 dst + border * d_stride + border, d_stride, border, 392 border, d_width - 2 * border, d_height - 2 * border, 393 0, 0, selection_threshold, segment_map, 394 segment_map_stride); 395 } 396 397 // When refining, use a slightly higher threshold for the initial error 398 // calculation - see comment above erroradv_early_tr for why. 399 int64_t selection_threshold = 400 (int64_t)lrint(ref_frame_error * erroradv_early_tr); 401 best_error = 402 get_warp_error(wm, use_hbd, bd, ref, r_width, r_height, r_stride, 403 dst + border * d_stride + border, d_stride, border, border, 404 d_width - 2 * border, d_height - 2 * border, 0, 0, 405 selection_threshold, segment_map, segment_map_stride); 406 407 if (best_error > selection_threshold) { 408 return INT64_MAX; 409 } 410 411 step = 1 << (n_refinements - 1); 412 for (i = 0; i < n_refinements; i++, step >>= 1) { 413 for (p = 0; p < n_params; ++p) { 414 int step_dir = 0; 415 param = param_mat + p; 416 curr_param = *param; 417 best_param = curr_param; 418 // look to the left 419 // Note: We have to use force_wmtype() to keep the proper symmetry for 420 // ROTZOOM type models 421 *param = add_param_offset(p, curr_param, -step); 422 force_wmtype(wm, wmtype); 423 step_error = 424 get_warp_error(wm, use_hbd, bd, ref, r_width, r_height, r_stride, 425 dst + border * d_stride + border, d_stride, border, 426 border, d_width - 2 * border, d_height - 2 * border, 0, 427 0, best_error, segment_map, segment_map_stride); 428 if (step_error < best_error) { 429 best_error = step_error; 430 best_param = *param; 431 step_dir = -1; 432 } 433 434 // look to the right 435 *param = add_param_offset(p, curr_param, step); 436 force_wmtype(wm, wmtype); 437 step_error = 438 get_warp_error(wm, use_hbd, bd, ref, r_width, r_height, r_stride, 439 dst + border * d_stride + border, d_stride, border, 440 border, d_width - 2 * border, d_height - 2 * border, 0, 441 0, best_error, segment_map, segment_map_stride); 442 if (step_error < best_error) { 443 best_error = step_error; 444 best_param = *param; 445 step_dir = 1; 446 } 447 448 // look to the direction chosen above repeatedly until error increases 449 // for the biggest step size 450 while (step_dir) { 451 *param = add_param_offset(p, best_param, step * step_dir); 452 force_wmtype(wm, wmtype); 453 step_error = 454 get_warp_error(wm, use_hbd, bd, ref, r_width, r_height, r_stride, 455 dst + border * d_stride + border, d_stride, border, 456 border, d_width - 2 * border, d_height - 2 * border, 457 0, 0, best_error, segment_map, segment_map_stride); 458 if (step_error < best_error) { 459 best_error = step_error; 460 best_param = *param; 461 } else { 462 step_dir = 0; 463 } 464 } 465 466 // Restore best parameter value so far 467 *param = best_param; 468 force_wmtype(wm, wmtype); 469 } 470 } 471 472 wm->wmtype = get_wmtype(wm); 473 // Recompute shear params for the refined model 474 // This should never fail, because we only ever consider warp-able models 475 if (!av1_get_shear_params(wm)) { 476 assert(0); 477 } 478 return best_error; 479 } 480 481 #define FEAT_COUNT_TR 3 482 #define SEG_COUNT_TR 48 483 void av1_compute_feature_segmentation_map(uint8_t *segment_map, int width, 484 int height, int *inliers, 485 int num_inliers) { 486 int seg_count = 0; 487 memset(segment_map, 0, sizeof(*segment_map) * width * height); 488 489 for (int i = 0; i < num_inliers; i++) { 490 int x = inliers[i * 2]; 491 int y = inliers[i * 2 + 1]; 492 int seg_x = x >> WARP_ERROR_BLOCK_LOG; 493 int seg_y = y >> WARP_ERROR_BLOCK_LOG; 494 segment_map[seg_y * width + seg_x] += 1; 495 } 496 497 for (int i = 0; i < height; i++) { 498 for (int j = 0; j < width; j++) { 499 uint8_t feat_count = segment_map[i * width + j]; 500 segment_map[i * width + j] = (feat_count >= FEAT_COUNT_TR); 501 seg_count += (segment_map[i * width + j]); 502 } 503 } 504 505 // If this motion does not make up a large enough portion of the frame, 506 // use the unsegmented version of the error metric 507 if (seg_count < SEG_COUNT_TR) 508 memset(segment_map, 1, width * height * sizeof(*segment_map)); 509 }