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