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