1/* 2 * Copyright (c) 2011 The WebM project authors. All Rights Reserved. 3 * 4 * Use of this source code is governed by a BSD-style license 5 * that can be found in the LICENSE file in the root of the source 6 * tree. An additional intellectual property rights grant can be found 7 * in the file PATENTS. All contributing project authors may 8 * be found in the AUTHORS file in the root of the source tree. 9 */ 10 11#include <assert.h> 12 13#include "error_concealment.h" 14#include "onyxd_int.h" 15#include "decodemv.h" 16#include "vpx_mem/vpx_mem.h" 17#include "vp8/common/findnearmv.h" 18#include "vp8/common/common.h" 19 20#define FLOOR(x,q) ((x) & -(1 << (q))) 21 22#define NUM_NEIGHBORS 20 23 24typedef struct ec_position 25{ 26 int row; 27 int col; 28} EC_POS; 29 30/* 31 * Regenerate the table in Matlab with: 32 * x = meshgrid((1:4), (1:4)); 33 * y = meshgrid((1:4), (1:4))'; 34 * W = round((1./(sqrt(x.^2 + y.^2))*2^7)); 35 * W(1,1) = 0; 36 */ 37static const int weights_q7[5][5] = { 38 { 0, 128, 64, 43, 32 }, 39 {128, 91, 57, 40, 31 }, 40 { 64, 57, 45, 36, 29 }, 41 { 43, 40, 36, 30, 26 }, 42 { 32, 31, 29, 26, 23 } 43}; 44 45int vp8_alloc_overlap_lists(VP8D_COMP *pbi) 46{ 47 if (pbi->overlaps != NULL) 48 { 49 vpx_free(pbi->overlaps); 50 pbi->overlaps = NULL; 51 } 52 53 pbi->overlaps = vpx_calloc(pbi->common.mb_rows * pbi->common.mb_cols, 54 sizeof(MB_OVERLAP)); 55 56 if (pbi->overlaps == NULL) 57 return -1; 58 59 return 0; 60} 61 62void vp8_de_alloc_overlap_lists(VP8D_COMP *pbi) 63{ 64 vpx_free(pbi->overlaps); 65 pbi->overlaps = NULL; 66} 67 68/* Inserts a new overlap area value to the list of overlaps of a block */ 69static void assign_overlap(OVERLAP_NODE* overlaps, 70 union b_mode_info *bmi, 71 int overlap) 72{ 73 int i; 74 if (overlap <= 0) 75 return; 76 /* Find and assign to the next empty overlap node in the list of overlaps. 77 * Empty is defined as bmi == NULL */ 78 for (i = 0; i < MAX_OVERLAPS; i++) 79 { 80 if (overlaps[i].bmi == NULL) 81 { 82 overlaps[i].bmi = bmi; 83 overlaps[i].overlap = overlap; 84 break; 85 } 86 } 87} 88 89/* Calculates the overlap area between two 4x4 squares, where the first 90 * square has its upper-left corner at (b1_row, b1_col) and the second 91 * square has its upper-left corner at (b2_row, b2_col). Doesn't 92 * properly handle squares which do not overlap. 93 */ 94static int block_overlap(int b1_row, int b1_col, int b2_row, int b2_col) 95{ 96 const int int_top = MAX(b1_row, b2_row); // top 97 const int int_left = MAX(b1_col, b2_col); // left 98 /* Since each block is 4x4 pixels, adding 4 (Q3) to the left/top edge 99 * gives us the right/bottom edge. 100 */ 101 const int int_right = MIN(b1_col + (4<<3), b2_col + (4<<3)); // right 102 const int int_bottom = MIN(b1_row + (4<<3), b2_row + (4<<3)); // bottom 103 return (int_bottom - int_top) * (int_right - int_left); 104} 105 106/* Calculates the overlap area for all blocks in a macroblock at position 107 * (mb_row, mb_col) in macroblocks, which are being overlapped by a given 108 * overlapping block at position (new_row, new_col) (in pixels, Q3). The 109 * first block being overlapped in the macroblock has position (first_blk_row, 110 * first_blk_col) in blocks relative the upper-left corner of the image. 111 */ 112static void calculate_overlaps_mb(B_OVERLAP *b_overlaps, union b_mode_info *bmi, 113 int new_row, int new_col, 114 int mb_row, int mb_col, 115 int first_blk_row, int first_blk_col) 116{ 117 /* Find the blocks within this MB (defined by mb_row, mb_col) which are 118 * overlapped by bmi and calculate and assign overlap for each of those 119 * blocks. */ 120 121 /* Block coordinates relative the upper-left block */ 122 const int rel_ol_blk_row = first_blk_row - mb_row * 4; 123 const int rel_ol_blk_col = first_blk_col - mb_col * 4; 124 /* If the block partly overlaps any previous MB, these coordinates 125 * can be < 0. We don't want to access blocks in previous MBs. 126 */ 127 const int blk_idx = MAX(rel_ol_blk_row,0) * 4 + MAX(rel_ol_blk_col,0); 128 /* Upper left overlapping block */ 129 B_OVERLAP *b_ol_ul = &(b_overlaps[blk_idx]); 130 131 /* Calculate and assign overlaps for all blocks in this MB 132 * which the motion compensated block overlaps 133 */ 134 /* Avoid calculating overlaps for blocks in later MBs */ 135 int end_row = MIN(4 + mb_row * 4 - first_blk_row, 2); 136 int end_col = MIN(4 + mb_col * 4 - first_blk_col, 2); 137 int row, col; 138 139 /* Check if new_row and new_col are evenly divisible by 4 (Q3), 140 * and if so we shouldn't check neighboring blocks 141 */ 142 if (new_row >= 0 && (new_row & 0x1F) == 0) 143 end_row = 1; 144 if (new_col >= 0 && (new_col & 0x1F) == 0) 145 end_col = 1; 146 147 /* Check if the overlapping block partly overlaps a previous MB 148 * and if so, we're overlapping fewer blocks in this MB. 149 */ 150 if (new_row < (mb_row*16)<<3) 151 end_row = 1; 152 if (new_col < (mb_col*16)<<3) 153 end_col = 1; 154 155 for (row = 0; row < end_row; ++row) 156 { 157 for (col = 0; col < end_col; ++col) 158 { 159 /* input in Q3, result in Q6 */ 160 const int overlap = block_overlap(new_row, new_col, 161 (((first_blk_row + row) * 162 4) << 3), 163 (((first_blk_col + col) * 164 4) << 3)); 165 assign_overlap(b_ol_ul[row * 4 + col].overlaps, bmi, overlap); 166 } 167 } 168} 169 170void vp8_calculate_overlaps(MB_OVERLAP *overlap_ul, 171 int mb_rows, int mb_cols, 172 union b_mode_info *bmi, 173 int b_row, int b_col) 174{ 175 MB_OVERLAP *mb_overlap; 176 int row, col, rel_row, rel_col; 177 int new_row, new_col; 178 int end_row, end_col; 179 int overlap_b_row, overlap_b_col; 180 int overlap_mb_row, overlap_mb_col; 181 182 /* mb subpixel position */ 183 row = (4 * b_row) << 3; /* Q3 */ 184 col = (4 * b_col) << 3; /* Q3 */ 185 186 /* reverse compensate for motion */ 187 new_row = row - bmi->mv.as_mv.row; 188 new_col = col - bmi->mv.as_mv.col; 189 190 if (new_row >= ((16*mb_rows) << 3) || new_col >= ((16*mb_cols) << 3)) 191 { 192 /* the new block ended up outside the frame */ 193 return; 194 } 195 196 if (new_row <= (-4 << 3) || new_col <= (-4 << 3)) 197 { 198 /* outside the frame */ 199 return; 200 } 201 /* overlapping block's position in blocks */ 202 overlap_b_row = FLOOR(new_row / 4, 3) >> 3; 203 overlap_b_col = FLOOR(new_col / 4, 3) >> 3; 204 205 /* overlapping block's MB position in MBs 206 * operations are done in Q3 207 */ 208 overlap_mb_row = FLOOR((overlap_b_row << 3) / 4, 3) >> 3; 209 overlap_mb_col = FLOOR((overlap_b_col << 3) / 4, 3) >> 3; 210 211 end_row = MIN(mb_rows - overlap_mb_row, 2); 212 end_col = MIN(mb_cols - overlap_mb_col, 2); 213 214 /* Don't calculate overlap for MBs we don't overlap */ 215 /* Check if the new block row starts at the last block row of the MB */ 216 if (abs(new_row - ((16*overlap_mb_row) << 3)) < ((3*4) << 3)) 217 end_row = 1; 218 /* Check if the new block col starts at the last block col of the MB */ 219 if (abs(new_col - ((16*overlap_mb_col) << 3)) < ((3*4) << 3)) 220 end_col = 1; 221 222 /* find the MB(s) this block is overlapping */ 223 for (rel_row = 0; rel_row < end_row; ++rel_row) 224 { 225 for (rel_col = 0; rel_col < end_col; ++rel_col) 226 { 227 if (overlap_mb_row + rel_row < 0 || 228 overlap_mb_col + rel_col < 0) 229 continue; 230 mb_overlap = overlap_ul + (overlap_mb_row + rel_row) * mb_cols + 231 overlap_mb_col + rel_col; 232 233 calculate_overlaps_mb(mb_overlap->overlaps, bmi, 234 new_row, new_col, 235 overlap_mb_row + rel_row, 236 overlap_mb_col + rel_col, 237 overlap_b_row + rel_row, 238 overlap_b_col + rel_col); 239 } 240 } 241} 242 243/* Estimates a motion vector given the overlapping blocks' motion vectors. 244 * Filters out all overlapping blocks which do not refer to the correct 245 * reference frame type. 246 */ 247static void estimate_mv(const OVERLAP_NODE *overlaps, union b_mode_info *bmi) 248{ 249 int i; 250 int overlap_sum = 0; 251 int row_acc = 0; 252 int col_acc = 0; 253 254 bmi->mv.as_int = 0; 255 for (i=0; i < MAX_OVERLAPS; ++i) 256 { 257 if (overlaps[i].bmi == NULL) 258 break; 259 col_acc += overlaps[i].overlap * overlaps[i].bmi->mv.as_mv.col; 260 row_acc += overlaps[i].overlap * overlaps[i].bmi->mv.as_mv.row; 261 overlap_sum += overlaps[i].overlap; 262 } 263 if (overlap_sum > 0) 264 { 265 /* Q9 / Q6 = Q3 */ 266 bmi->mv.as_mv.col = col_acc / overlap_sum; 267 bmi->mv.as_mv.row = row_acc / overlap_sum; 268 } 269 else 270 { 271 bmi->mv.as_mv.col = 0; 272 bmi->mv.as_mv.row = 0; 273 } 274} 275 276/* Estimates all motion vectors for a macroblock given the lists of 277 * overlaps for each block. Decides whether or not the MVs must be clamped. 278 */ 279static void estimate_mb_mvs(const B_OVERLAP *block_overlaps, 280 MODE_INFO *mi, 281 int mb_to_left_edge, 282 int mb_to_right_edge, 283 int mb_to_top_edge, 284 int mb_to_bottom_edge) 285{ 286 int row, col; 287 int non_zero_count = 0; 288 MV * const filtered_mv = &(mi->mbmi.mv.as_mv); 289 union b_mode_info * const bmi = mi->bmi; 290 filtered_mv->col = 0; 291 filtered_mv->row = 0; 292 mi->mbmi.need_to_clamp_mvs = 0; 293 for (row = 0; row < 4; ++row) 294 { 295 int this_b_to_top_edge = mb_to_top_edge + ((row*4)<<3); 296 int this_b_to_bottom_edge = mb_to_bottom_edge - ((row*4)<<3); 297 for (col = 0; col < 4; ++col) 298 { 299 int i = row * 4 + col; 300 int this_b_to_left_edge = mb_to_left_edge + ((col*4)<<3); 301 int this_b_to_right_edge = mb_to_right_edge - ((col*4)<<3); 302 /* Estimate vectors for all blocks which are overlapped by this */ 303 /* type. Interpolate/extrapolate the rest of the block's MVs */ 304 estimate_mv(block_overlaps[i].overlaps, &(bmi[i])); 305 mi->mbmi.need_to_clamp_mvs |= vp8_check_mv_bounds( 306 &bmi[i].mv, 307 this_b_to_left_edge, 308 this_b_to_right_edge, 309 this_b_to_top_edge, 310 this_b_to_bottom_edge); 311 if (bmi[i].mv.as_int != 0) 312 { 313 ++non_zero_count; 314 filtered_mv->col += bmi[i].mv.as_mv.col; 315 filtered_mv->row += bmi[i].mv.as_mv.row; 316 } 317 } 318 } 319 if (non_zero_count > 0) 320 { 321 filtered_mv->col /= non_zero_count; 322 filtered_mv->row /= non_zero_count; 323 } 324} 325 326static void calc_prev_mb_overlaps(MB_OVERLAP *overlaps, MODE_INFO *prev_mi, 327 int mb_row, int mb_col, 328 int mb_rows, int mb_cols) 329{ 330 int sub_row; 331 int sub_col; 332 for (sub_row = 0; sub_row < 4; ++sub_row) 333 { 334 for (sub_col = 0; sub_col < 4; ++sub_col) 335 { 336 vp8_calculate_overlaps( 337 overlaps, mb_rows, mb_cols, 338 &(prev_mi->bmi[sub_row * 4 + sub_col]), 339 4 * mb_row + sub_row, 340 4 * mb_col + sub_col); 341 } 342 } 343} 344 345/* Estimate all missing motion vectors. This function does the same as the one 346 * above, but has different input arguments. */ 347static void estimate_missing_mvs(MB_OVERLAP *overlaps, 348 MODE_INFO *mi, MODE_INFO *prev_mi, 349 int mb_rows, int mb_cols, 350 unsigned int first_corrupt) 351{ 352 int mb_row, mb_col; 353 vpx_memset(overlaps, 0, sizeof(MB_OVERLAP) * mb_rows * mb_cols); 354 /* First calculate the overlaps for all blocks */ 355 for (mb_row = 0; mb_row < mb_rows; ++mb_row) 356 { 357 for (mb_col = 0; mb_col < mb_cols; ++mb_col) 358 { 359 /* We're only able to use blocks referring to the last frame 360 * when extrapolating new vectors. 361 */ 362 if (prev_mi->mbmi.ref_frame == LAST_FRAME) 363 { 364 calc_prev_mb_overlaps(overlaps, prev_mi, 365 mb_row, mb_col, 366 mb_rows, mb_cols); 367 } 368 ++prev_mi; 369 } 370 ++prev_mi; 371 } 372 373 mb_row = first_corrupt / mb_cols; 374 mb_col = first_corrupt - mb_row * mb_cols; 375 mi += mb_row*(mb_cols + 1) + mb_col; 376 /* Go through all macroblocks in the current image with missing MVs 377 * and calculate new MVs using the overlaps. 378 */ 379 for (; mb_row < mb_rows; ++mb_row) 380 { 381 int mb_to_top_edge = -((mb_row * 16)) << 3; 382 int mb_to_bottom_edge = ((mb_rows - 1 - mb_row) * 16) << 3; 383 for (; mb_col < mb_cols; ++mb_col) 384 { 385 int mb_to_left_edge = -((mb_col * 16) << 3); 386 int mb_to_right_edge = ((mb_cols - 1 - mb_col) * 16) << 3; 387 const B_OVERLAP *block_overlaps = 388 overlaps[mb_row*mb_cols + mb_col].overlaps; 389 mi->mbmi.ref_frame = LAST_FRAME; 390 mi->mbmi.mode = SPLITMV; 391 mi->mbmi.uv_mode = DC_PRED; 392 mi->mbmi.partitioning = 3; 393 mi->mbmi.segment_id = 0; 394 estimate_mb_mvs(block_overlaps, 395 mi, 396 mb_to_left_edge, 397 mb_to_right_edge, 398 mb_to_top_edge, 399 mb_to_bottom_edge); 400 ++mi; 401 } 402 mb_col = 0; 403 ++mi; 404 } 405} 406 407void vp8_estimate_missing_mvs(VP8D_COMP *pbi) 408{ 409 VP8_COMMON * const pc = &pbi->common; 410 estimate_missing_mvs(pbi->overlaps, 411 pc->mi, pc->prev_mi, 412 pc->mb_rows, pc->mb_cols, 413 pbi->mvs_corrupt_from_mb); 414} 415 416static void assign_neighbor(EC_BLOCK *neighbor, MODE_INFO *mi, int block_idx) 417{ 418 assert(mi->mbmi.ref_frame < MAX_REF_FRAMES); 419 neighbor->ref_frame = mi->mbmi.ref_frame; 420 neighbor->mv = mi->bmi[block_idx].mv.as_mv; 421} 422 423/* Finds the neighboring blocks of a macroblocks. In the general case 424 * 20 blocks are found. If a fewer number of blocks are found due to 425 * image boundaries, those positions in the EC_BLOCK array are left "empty". 426 * The neighbors are enumerated with the upper-left neighbor as the first 427 * element, the second element refers to the neighbor to right of the previous 428 * neighbor, and so on. The last element refers to the neighbor below the first 429 * neighbor. 430 */ 431static void find_neighboring_blocks(MODE_INFO *mi, 432 EC_BLOCK *neighbors, 433 int mb_row, int mb_col, 434 int mb_rows, int mb_cols, 435 int mi_stride) 436{ 437 int i = 0; 438 int j; 439 if (mb_row > 0) 440 { 441 /* upper left */ 442 if (mb_col > 0) 443 assign_neighbor(&neighbors[i], mi - mi_stride - 1, 15); 444 ++i; 445 /* above */ 446 for (j = 12; j < 16; ++j, ++i) 447 assign_neighbor(&neighbors[i], mi - mi_stride, j); 448 } 449 else 450 i += 5; 451 if (mb_col < mb_cols - 1) 452 { 453 /* upper right */ 454 if (mb_row > 0) 455 assign_neighbor(&neighbors[i], mi - mi_stride + 1, 12); 456 ++i; 457 /* right */ 458 for (j = 0; j <= 12; j += 4, ++i) 459 assign_neighbor(&neighbors[i], mi + 1, j); 460 } 461 else 462 i += 5; 463 if (mb_row < mb_rows - 1) 464 { 465 /* lower right */ 466 if (mb_col < mb_cols - 1) 467 assign_neighbor(&neighbors[i], mi + mi_stride + 1, 0); 468 ++i; 469 /* below */ 470 for (j = 0; j < 4; ++j, ++i) 471 assign_neighbor(&neighbors[i], mi + mi_stride, j); 472 } 473 else 474 i += 5; 475 if (mb_col > 0) 476 { 477 /* lower left */ 478 if (mb_row < mb_rows - 1) 479 assign_neighbor(&neighbors[i], mi + mi_stride - 1, 4); 480 ++i; 481 /* left */ 482 for (j = 3; j < 16; j += 4, ++i) 483 { 484 assign_neighbor(&neighbors[i], mi - 1, j); 485 } 486 } 487 else 488 i += 5; 489 assert(i == 20); 490} 491 492/* Interpolates all motion vectors for a macroblock from the neighboring blocks' 493 * motion vectors. 494 */ 495static void interpolate_mvs(MACROBLOCKD *mb, 496 EC_BLOCK *neighbors, 497 MV_REFERENCE_FRAME dom_ref_frame) 498{ 499 int row, col, i; 500 MODE_INFO * const mi = mb->mode_info_context; 501 /* Table with the position of the neighboring blocks relative the position 502 * of the upper left block of the current MB. Starting with the upper left 503 * neighbor and going to the right. 504 */ 505 const EC_POS neigh_pos[NUM_NEIGHBORS] = { 506 {-1,-1}, {-1,0}, {-1,1}, {-1,2}, {-1,3}, 507 {-1,4}, {0,4}, {1,4}, {2,4}, {3,4}, 508 {4,4}, {4,3}, {4,2}, {4,1}, {4,0}, 509 {4,-1}, {3,-1}, {2,-1}, {1,-1}, {0,-1} 510 }; 511 mi->mbmi.need_to_clamp_mvs = 0; 512 for (row = 0; row < 4; ++row) 513 { 514 int mb_to_top_edge = mb->mb_to_top_edge + ((row*4)<<3); 515 int mb_to_bottom_edge = mb->mb_to_bottom_edge - ((row*4)<<3); 516 for (col = 0; col < 4; ++col) 517 { 518 int mb_to_left_edge = mb->mb_to_left_edge + ((col*4)<<3); 519 int mb_to_right_edge = mb->mb_to_right_edge - ((col*4)<<3); 520 int w_sum = 0; 521 int mv_row_sum = 0; 522 int mv_col_sum = 0; 523 int_mv * const mv = &(mi->bmi[row*4 + col].mv); 524 mv->as_int = 0; 525 for (i = 0; i < NUM_NEIGHBORS; ++i) 526 { 527 /* Calculate the weighted sum of neighboring MVs referring 528 * to the dominant frame type. 529 */ 530 const int w = weights_q7[abs(row - neigh_pos[i].row)] 531 [abs(col - neigh_pos[i].col)]; 532 if (neighbors[i].ref_frame != dom_ref_frame) 533 continue; 534 w_sum += w; 535 /* Q7 * Q3 = Q10 */ 536 mv_row_sum += w*neighbors[i].mv.row; 537 mv_col_sum += w*neighbors[i].mv.col; 538 } 539 if (w_sum > 0) 540 { 541 /* Avoid division by zero. 542 * Normalize with the sum of the coefficients 543 * Q3 = Q10 / Q7 544 */ 545 mv->as_mv.row = mv_row_sum / w_sum; 546 mv->as_mv.col = mv_col_sum / w_sum; 547 mi->mbmi.need_to_clamp_mvs |= vp8_check_mv_bounds( 548 mv, 549 mb_to_left_edge, 550 mb_to_right_edge, 551 mb_to_top_edge, 552 mb_to_bottom_edge); 553 } 554 } 555 } 556} 557 558void vp8_interpolate_motion(MACROBLOCKD *mb, 559 int mb_row, int mb_col, 560 int mb_rows, int mb_cols, 561 int mi_stride) 562{ 563 /* Find relevant neighboring blocks */ 564 EC_BLOCK neighbors[NUM_NEIGHBORS]; 565 int i; 566 /* Initialize the array. MAX_REF_FRAMES is interpreted as "doesn't exist" */ 567 for (i = 0; i < NUM_NEIGHBORS; ++i) 568 { 569 neighbors[i].ref_frame = MAX_REF_FRAMES; 570 neighbors[i].mv.row = neighbors[i].mv.col = 0; 571 } 572 find_neighboring_blocks(mb->mode_info_context, 573 neighbors, 574 mb_row, mb_col, 575 mb_rows, mb_cols, 576 mb->mode_info_stride); 577 /* Interpolate MVs for the missing blocks from the surrounding 578 * blocks which refer to the last frame. */ 579 interpolate_mvs(mb, neighbors, LAST_FRAME); 580 581 mb->mode_info_context->mbmi.ref_frame = LAST_FRAME; 582 mb->mode_info_context->mbmi.mode = SPLITMV; 583 mb->mode_info_context->mbmi.uv_mode = DC_PRED; 584 mb->mode_info_context->mbmi.partitioning = 3; 585 mb->mode_info_context->mbmi.segment_id = 0; 586} 587 588void vp8_conceal_corrupt_mb(MACROBLOCKD *xd) 589{ 590 /* This macroblock has corrupt residual, use the motion compensated 591 image (predictor) for concealment */ 592 593 /* The build predictor functions now output directly into the dst buffer, 594 * so the copies are no longer necessary */ 595 596} 597