vp9_entropymv.c 15.6 KB
Newer Older
John Koleszar's avatar
John Koleszar committed
1
/*
2
 *  Copyright (c) 2010 The WebM project authors. All Rights Reserved.
John Koleszar's avatar
John Koleszar committed
3
 *
4
 *  Use of this source code is governed by a BSD-style license
5
6
 *  that can be found in the LICENSE file in the root of the source
 *  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.
John Koleszar's avatar
John Koleszar committed
9
10
11
 */


12
13
#include "vp9/common/vp9_onyxc_int.h"
#include "vp9/common/vp9_entropymv.h"
John Koleszar's avatar
John Koleszar committed
14

15
16
17
18
19
//#define MV_COUNT_TESTING

#define MV_COUNT_SAT 16
#define MV_MAX_UPDATE_FACTOR 160

20
21
22
23
#if CONFIG_NEW_MVREF
/* Integer pel reference mv threshold for use of high-precision 1/8 mv */
#define COMPANDED_MVREF_THRESH    1000000
#else
24
25
/* Integer pel reference mv threshold for use of high-precision 1/8 mv */
#define COMPANDED_MVREF_THRESH    8
26
#endif
27

28
29
30
/* Smooth or bias the mv-counts before prob computation */
/* #define SMOOTH_MV_COUNTS */

31
const vp9_tree_index vp9_mv_joint_tree[2 * MV_JOINTS - 2] = {
32
33
34
35
  -MV_JOINT_ZERO, 2,
  -MV_JOINT_HNZVZ, 4,
  -MV_JOINT_HZVNZ, -MV_JOINT_HNZVNZ
};
36
struct vp9_token vp9_mv_joint_encodings[MV_JOINTS];
37

38
const vp9_tree_index vp9_mv_class_tree[2 * MV_CLASSES - 2] = {
39
40
41
42
43
44
  -MV_CLASS_0, 2,
  -MV_CLASS_1, 4,
  6, 8,
  -MV_CLASS_2, -MV_CLASS_3,
  10, 12,
  -MV_CLASS_4, -MV_CLASS_5,
45
46
47
48
  -MV_CLASS_6, 14,
  16, 18,
  -MV_CLASS_7, -MV_CLASS_8,
  -MV_CLASS_9, -MV_CLASS_10,
49
};
50
struct vp9_token vp9_mv_class_encodings[MV_CLASSES];
51

52
const vp9_tree_index vp9_mv_class0_tree [2 * CLASS0_SIZE - 2] = {
53
54
  -0, -1,
};
55
struct vp9_token vp9_mv_class0_encodings[CLASS0_SIZE];
56

57
const vp9_tree_index vp9_mv_fp_tree [2 * 4 - 2] = {
58
59
60
61
  -0, 2,
  -1, 4,
  -2, -3
};
62
struct vp9_token vp9_mv_fp_encodings[4];
63

64
const nmv_context vp9_default_nmv_context = {
65
66
67
  {32, 64, 96},
  {
    { /* vert component */
68
69
70
71
72
73
74
75
      128,                                                  /* sign */
      {224, 144, 192, 168, 192, 176, 192, 198, 198, 245},   /* class */
      {216},                                                /* class0 */
      {136, 140, 148, 160, 176, 192, 224, 234, 234, 240},   /* bits */
      {{128, 128, 64}, {96, 112, 64}},                      /* class0_fp */
      {64, 96, 64},                                         /* fp */
      160,                                                  /* class0_hp bit */
      128,                                                  /* hp */
76
77
    },
    { /* hor component */
78
79
80
81
82
83
84
85
      128,                                                  /* sign */
      {216, 128, 176, 160, 176, 176, 192, 198, 198, 208},   /* class */
      {208},                                                /* class0 */
      {136, 140, 148, 160, 176, 192, 224, 234, 234, 240},   /* bits */
      {{128, 128, 64}, {96, 112, 64}},                      /* class0_fp */
      {64, 96, 64},                                         /* fp */
      160,                                                  /* class0_hp bit */
      128,                                                  /* hp */
86
87
88
89
    }
  },
};

90
MV_JOINT_TYPE vp9_get_mv_joint(MV mv) {
Dmitry Kovalev's avatar
Dmitry Kovalev committed
91
92
93
94
95
96
97
98
  if (mv.row == 0 && mv.col == 0)
    return MV_JOINT_ZERO;
  else if (mv.row == 0 && mv.col != 0)
    return MV_JOINT_HNZVZ;
  else if (mv.row != 0 && mv.col == 0)
    return MV_JOINT_HZVNZ;
  else
    return MV_JOINT_HNZVNZ;
99
100
101
102
}

#define mv_class_base(c) ((c) ? (CLASS0_SIZE << (c + 2)) : 0)

103
MV_CLASS_TYPE vp9_get_mv_class(int z, int *offset) {
104
105
106
107
108
109
110
111
112
  MV_CLASS_TYPE c;
  if      (z < CLASS0_SIZE * 8)    c = MV_CLASS_0;
  else if (z < CLASS0_SIZE * 16)   c = MV_CLASS_1;
  else if (z < CLASS0_SIZE * 32)   c = MV_CLASS_2;
  else if (z < CLASS0_SIZE * 64)   c = MV_CLASS_3;
  else if (z < CLASS0_SIZE * 128)  c = MV_CLASS_4;
  else if (z < CLASS0_SIZE * 256)  c = MV_CLASS_5;
  else if (z < CLASS0_SIZE * 512)  c = MV_CLASS_6;
  else if (z < CLASS0_SIZE * 1024) c = MV_CLASS_7;
113
114
  else if (z < CLASS0_SIZE * 2048) c = MV_CLASS_8;
  else if (z < CLASS0_SIZE * 4096) c = MV_CLASS_9;
115
  else if (z < CLASS0_SIZE * 8192) c = MV_CLASS_10;
116
117
118
119
120
121
  else assert(0);
  if (offset)
    *offset = z - mv_class_base(c);
  return c;
}

122
int vp9_use_nmv_hp(const MV *ref) {
Dmitry Kovalev's avatar
Dmitry Kovalev committed
123
124
  return (abs(ref->row) >> 3) < COMPANDED_MVREF_THRESH &&
         (abs(ref->col) >> 3) < COMPANDED_MVREF_THRESH;
125
126
}

127
int vp9_get_mv_mag(MV_CLASS_TYPE c, int offset) {
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
  return mv_class_base(c) + offset;
}

static void increment_nmv_component_count(int v,
                                          nmv_component_counts *mvcomp,
                                          int incr,
                                          int usehp) {
  assert (v != 0);            /* should not be zero */
  mvcomp->mvcount[MV_MAX + v] += incr;
}

static void increment_nmv_component(int v,
                                    nmv_component_counts *mvcomp,
                                    int incr,
                                    int usehp) {
  int s, z, c, o, d, e, f;
Dmitry Kovalev's avatar
Dmitry Kovalev committed
144
145
  if (!incr)
    return;
146
147
148
149
150
  assert (v != 0);            /* should not be zero */
  s = v < 0;
  mvcomp->sign[s] += incr;
  z = (s ? -v : v) - 1;       /* magnitude - 1 */

151
  c = vp9_get_mv_class(z, &o);
152
153
154
155
156
157
158
159
  mvcomp->classes[c] += incr;

  d = (o >> 3);               /* int mv data */
  f = (o >> 1) & 3;           /* fractional pel mv data */
  e = (o & 1);                /* high precision mv data */
  if (c == MV_CLASS_0) {
    mvcomp->class0[d] += incr;
  } else {
Dmitry Kovalev's avatar
Dmitry Kovalev committed
160
161
    int i;
    int b = c + CLASS0_BITS - 1;  // number of bits
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
    for (i = 0; i < b; ++i)
      mvcomp->bits[i][((d >> i) & 1)] += incr;
  }

  /* Code the fractional pel bits */
  if (c == MV_CLASS_0) {
    mvcomp->class0_fp[d][f] += incr;
  } else {
    mvcomp->fp[f] += incr;
  }

  /* Code the high precision bit */
  if (usehp) {
    if (c == MV_CLASS_0) {
      mvcomp->class0_hp[e] += incr;
    } else {
      mvcomp->hp[e] += incr;
    }
  }
}

#ifdef SMOOTH_MV_COUNTS
static void smooth_counts(nmv_component_counts *mvcomp) {
  static const int flen = 3;  // (filter_length + 1) / 2
  static const int fval[] = {8, 3, 1};
  static const int fvalbits = 4;
  int i;
  unsigned int smvcount[MV_VALS];
  vpx_memcpy(smvcount, mvcomp->mvcount, sizeof(smvcount));
  smvcount[MV_MAX] = (smvcount[MV_MAX - 1] + smvcount[MV_MAX + 1]) >> 1;
  for (i = flen - 1; i <= MV_VALS - flen; ++i) {
    int j, s = smvcount[i] * fval[0];
    for (j = 1; j < flen; ++j)
      s += (smvcount[i - j] + smvcount[i + j]) * fval[j];
    mvcomp->mvcount[i] = (s + (1 << (fvalbits - 1))) >> fvalbits;
  }
}
#endif

static void counts_to_context(nmv_component_counts *mvcomp, int usehp) {
  int v;
  vpx_memset(mvcomp->sign, 0, sizeof(nmv_component_counts) - sizeof(mvcomp->mvcount));
  for (v = 1; v <= MV_MAX; v++) {
    increment_nmv_component(-v, mvcomp, mvcomp->mvcount[MV_MAX - v], usehp);
    increment_nmv_component( v, mvcomp, mvcomp->mvcount[MV_MAX + v], usehp);
  }
}

210
void vp9_increment_nmv(const MV *mv, const MV *ref, nmv_context_counts *mvctx,
211
                       int usehp) {
Dmitry Kovalev's avatar
Dmitry Kovalev committed
212
213
  const MV_JOINT_TYPE type = vp9_get_mv_joint(*mv);
  mvctx->joints[type]++;
214
  usehp = usehp && vp9_use_nmv_hp(ref);
Dmitry Kovalev's avatar
Dmitry Kovalev committed
215
  if (type == MV_JOINT_HZVNZ || type == MV_JOINT_HNZVNZ)
216
    increment_nmv_component_count(mv->row, &mvctx->comps[0], 1, usehp);
Dmitry Kovalev's avatar
Dmitry Kovalev committed
217
218

  if (type == MV_JOINT_HNZVZ || type == MV_JOINT_HNZVNZ)
219
220
221
    increment_nmv_component_count(mv->col, &mvctx->comps[1], 1, usehp);
}

Dmitry Kovalev's avatar
Dmitry Kovalev committed
222
223
static void adapt_prob(vp9_prob *dest, vp9_prob prep, unsigned int ct[2]) {
  const int count = MIN(ct[0] + ct[1], MV_COUNT_SAT);
224
  if (count) {
Dmitry Kovalev's avatar
Dmitry Kovalev committed
225
226
227
    const vp9_prob newp = get_binary_prob(ct[0], ct[1]);
    const int factor = MV_MAX_UPDATE_FACTOR * count / MV_COUNT_SAT;
    *dest = weighted_prob(prep, newp, factor);
John Koleszar's avatar
John Koleszar committed
228
229
  } else {
    *dest = prep;
230
231
232
  }
}

Dmitry Kovalev's avatar
Dmitry Kovalev committed
233
234
235
void vp9_counts_process(nmv_context_counts *nmv_count, int usehp) {
  counts_to_context(&nmv_count->comps[0], usehp);
  counts_to_context(&nmv_count->comps[1], usehp);
Deb Mukherjee's avatar
Deb Mukherjee committed
236
237
}

238
void vp9_counts_to_nmv_context(
Dmitry Kovalev's avatar
Dmitry Kovalev committed
239
    nmv_context_counts *nmv_count,
240
241
242
243
244
245
246
247
248
249
250
251
    nmv_context *prob,
    int usehp,
    unsigned int (*branch_ct_joint)[2],
    unsigned int (*branch_ct_sign)[2],
    unsigned int (*branch_ct_classes)[MV_CLASSES - 1][2],
    unsigned int (*branch_ct_class0)[CLASS0_SIZE - 1][2],
    unsigned int (*branch_ct_bits)[MV_OFFSET_BITS][2],
    unsigned int (*branch_ct_class0_fp)[CLASS0_SIZE][4 - 1][2],
    unsigned int (*branch_ct_fp)[4 - 1][2],
    unsigned int (*branch_ct_class0_hp)[2],
    unsigned int (*branch_ct_hp)[2]) {
  int i, j, k;
Dmitry Kovalev's avatar
Dmitry Kovalev committed
252
  vp9_counts_process(nmv_count, usehp);
253
  vp9_tree_probs_from_distribution(vp9_mv_joint_tree,
254
255
                                   prob->joints,
                                   branch_ct_joint,
Dmitry Kovalev's avatar
Dmitry Kovalev committed
256
                                   nmv_count->joints, 0);
257
  for (i = 0; i < 2; ++i) {
Dmitry Kovalev's avatar
Dmitry Kovalev committed
258
259
260
261
262
263
    const uint32_t s0 = nmv_count->comps[i].sign[0];
    const uint32_t s1 = nmv_count->comps[i].sign[1];

    prob->comps[i].sign = get_binary_prob(s0, s1);
    branch_ct_sign[i][0] = s0;
    branch_ct_sign[i][1] = s1;
264
    vp9_tree_probs_from_distribution(vp9_mv_class_tree,
265
266
                                     prob->comps[i].classes,
                                     branch_ct_classes[i],
Dmitry Kovalev's avatar
Dmitry Kovalev committed
267
                                     nmv_count->comps[i].classes, 0);
268
    vp9_tree_probs_from_distribution(vp9_mv_class0_tree,
269
270
                                     prob->comps[i].class0,
                                     branch_ct_class0[i],
Dmitry Kovalev's avatar
Dmitry Kovalev committed
271
                                     nmv_count->comps[i].class0, 0);
272
    for (j = 0; j < MV_OFFSET_BITS; ++j) {
Dmitry Kovalev's avatar
Dmitry Kovalev committed
273
274
275
276
277
278
      const uint32_t b0 = nmv_count->comps[i].bits[j][0];
      const uint32_t b1 = nmv_count->comps[i].bits[j][1];

      prob->comps[i].bits[j] = get_binary_prob(b0, b1);
      branch_ct_bits[i][j][0] = b0;
      branch_ct_bits[i][j][1] = b1;
279
280
281
282
    }
  }
  for (i = 0; i < 2; ++i) {
    for (k = 0; k < CLASS0_SIZE; ++k) {
283
      vp9_tree_probs_from_distribution(vp9_mv_fp_tree,
284
285
                                       prob->comps[i].class0_fp[k],
                                       branch_ct_class0_fp[i][k],
Dmitry Kovalev's avatar
Dmitry Kovalev committed
286
                                       nmv_count->comps[i].class0_fp[k], 0);
287
    }
288
    vp9_tree_probs_from_distribution(vp9_mv_fp_tree,
289
290
                                     prob->comps[i].fp,
                                     branch_ct_fp[i],
Dmitry Kovalev's avatar
Dmitry Kovalev committed
291
                                     nmv_count->comps[i].fp, 0);
292
293
294
  }
  if (usehp) {
    for (i = 0; i < 2; ++i) {
Dmitry Kovalev's avatar
Dmitry Kovalev committed
295
296
297
298
299
300
301
302
303
304
305
306
      const uint32_t c0_hp0 = nmv_count->comps[i].class0_hp[0];
      const uint32_t c0_hp1 = nmv_count->comps[i].class0_hp[1];
      const uint32_t hp0 = nmv_count->comps[i].hp[0];
      const uint32_t hp1 = nmv_count->comps[i].hp[1];

      prob->comps[i].class0_hp = get_binary_prob(c0_hp0, c0_hp1);
      branch_ct_class0_hp[i][0] = c0_hp0;
      branch_ct_class0_hp[i][1] = c0_hp1;

      prob->comps[i].hp = get_binary_prob(hp0, hp1);
      branch_ct_hp[i][0] = hp0;
      branch_ct_hp[i][1] = hp1;
307
308
309
310
    }
  }
}

John Koleszar's avatar
John Koleszar committed
311
312
313
314
315
316
317
static unsigned int adapt_probs(unsigned int i,
                                vp9_tree tree,
                                vp9_prob this_probs[],
                                const vp9_prob last_probs[],
                                const unsigned int num_events[]) {
  vp9_prob this_prob;

Dmitry Kovalev's avatar
Dmitry Kovalev committed
318
319
320
321
322
323
324
  const uint32_t left = tree[i] <= 0
          ? num_events[-tree[i]]
          : adapt_probs(tree[i], tree, this_probs, last_probs, num_events);

  const uint32_t right = tree[i + 1] <= 0
          ? num_events[-tree[i + 1]]
          : adapt_probs(tree[i + 1], tree, this_probs, last_probs, num_events);
John Koleszar's avatar
John Koleszar committed
325

Dmitry Kovalev's avatar
Dmitry Kovalev committed
326
  uint32_t weight = left + right;
John Koleszar's avatar
John Koleszar committed
327
328
329
  if (weight) {
    this_prob = get_binary_prob(left, right);
    weight = weight > MV_COUNT_SAT ? MV_COUNT_SAT : weight;
Dmitry Kovalev's avatar
Dmitry Kovalev committed
330
    this_prob = weighted_prob(last_probs[i >> 1], this_prob,
John Koleszar's avatar
John Koleszar committed
331
332
333
334
                              MV_MAX_UPDATE_FACTOR * weight / MV_COUNT_SAT);
  } else {
    this_prob = last_probs[i >> 1];
  }
Dmitry Kovalev's avatar
Dmitry Kovalev committed
335
  this_probs[i >> 1] = this_prob;
John Koleszar's avatar
John Koleszar committed
336
337
338
339
  return left + right;
}


340
void vp9_adapt_nmv_probs(VP9_COMMON *cm, int usehp) {
John Koleszar's avatar
John Koleszar committed
341
  int i, j;
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
#ifdef MV_COUNT_TESTING
  printf("joints count: ");
  for (j = 0; j < MV_JOINTS; ++j) printf("%d ", cm->fc.NMVcount.joints[j]);
  printf("\n"); fflush(stdout);
  printf("signs count:\n");
  for (i = 0; i < 2; ++i)
    printf("%d/%d ", cm->fc.NMVcount.comps[i].sign[0], cm->fc.NMVcount.comps[i].sign[1]);
  printf("\n"); fflush(stdout);
  printf("classes count:\n");
  for (i = 0; i < 2; ++i) {
    for (j = 0; j < MV_CLASSES; ++j)
      printf("%d ", cm->fc.NMVcount.comps[i].classes[j]);
    printf("\n"); fflush(stdout);
  }
  printf("class0 count:\n");
  for (i = 0; i < 2; ++i) {
    for (j = 0; j < CLASS0_SIZE; ++j)
      printf("%d ", cm->fc.NMVcount.comps[i].class0[j]);
    printf("\n"); fflush(stdout);
  }
  printf("bits count:\n");
  for (i = 0; i < 2; ++i) {
    for (j = 0; j < MV_OFFSET_BITS; ++j)
      printf("%d/%d ", cm->fc.NMVcount.comps[i].bits[j][0],
                       cm->fc.NMVcount.comps[i].bits[j][1]);
    printf("\n"); fflush(stdout);
  }
  printf("class0_fp count:\n");
  for (i = 0; i < 2; ++i) {
    for (j = 0; j < CLASS0_SIZE; ++j) {
      printf("{");
      for (k = 0; k < 4; ++k)
        printf("%d ", cm->fc.NMVcount.comps[i].class0_fp[j][k]);
      printf("}, ");
    }
    printf("\n"); fflush(stdout);
  }
  printf("fp count:\n");
  for (i = 0; i < 2; ++i) {
    for (j = 0; j < 4; ++j)
      printf("%d ", cm->fc.NMVcount.comps[i].fp[j]);
    printf("\n"); fflush(stdout);
  }
  if (usehp) {
    printf("class0_hp count:\n");
    for (i = 0; i < 2; ++i)
      printf("%d/%d ", cm->fc.NMVcount.comps[i].class0_hp[0],
                       cm->fc.NMVcount.comps[i].class0_hp[1]);
    printf("\n"); fflush(stdout);
    printf("hp count:\n");
    for (i = 0; i < 2; ++i)
      printf("%d/%d ", cm->fc.NMVcount.comps[i].hp[0],
                       cm->fc.NMVcount.comps[i].hp[1]);
    printf("\n"); fflush(stdout);
  }
#endif
#ifdef SMOOTH_MV_COUNTS
  smooth_counts(&cm->fc.NMVcount.comps[0]);
  smooth_counts(&cm->fc.NMVcount.comps[1]);
#endif
John Koleszar's avatar
John Koleszar committed
402
403
404
405
406
407
  vp9_counts_process(&cm->fc.NMVcount, usehp);

  adapt_probs(0, vp9_mv_joint_tree,
              cm->fc.nmvc.joints, cm->fc.pre_nmvc.joints,
              cm->fc.NMVcount.joints);

408
409
410
  for (i = 0; i < 2; ++i) {
    adapt_prob(&cm->fc.nmvc.comps[i].sign,
               cm->fc.pre_nmvc.comps[i].sign,
John Koleszar's avatar
John Koleszar committed
411
412
413
414
415
416
417
               cm->fc.NMVcount.comps[i].sign);
    adapt_probs(0, vp9_mv_class_tree,
                cm->fc.nmvc.comps[i].classes, cm->fc.pre_nmvc.comps[i].classes,
                cm->fc.NMVcount.comps[i].classes);
    adapt_probs(0, vp9_mv_class0_tree,
                cm->fc.nmvc.comps[i].class0, cm->fc.pre_nmvc.comps[i].class0,
                cm->fc.NMVcount.comps[i].class0);
418
419
420
    for (j = 0; j < MV_OFFSET_BITS; ++j) {
      adapt_prob(&cm->fc.nmvc.comps[i].bits[j],
                 cm->fc.pre_nmvc.comps[i].bits[j],
John Koleszar's avatar
John Koleszar committed
421
                 cm->fc.NMVcount.comps[i].bits[j]);
422
423
424
425
    }
  }
  for (i = 0; i < 2; ++i) {
    for (j = 0; j < CLASS0_SIZE; ++j) {
John Koleszar's avatar
John Koleszar committed
426
427
428
429
      adapt_probs(0, vp9_mv_fp_tree,
                  cm->fc.nmvc.comps[i].class0_fp[j],
                  cm->fc.pre_nmvc.comps[i].class0_fp[j],
                  cm->fc.NMVcount.comps[i].class0_fp[j]);
430
    }
John Koleszar's avatar
John Koleszar committed
431
432
433
434
    adapt_probs(0, vp9_mv_fp_tree,
                cm->fc.nmvc.comps[i].fp,
                cm->fc.pre_nmvc.comps[i].fp,
                cm->fc.NMVcount.comps[i].fp);
435
436
437
438
439
  }
  if (usehp) {
    for (i = 0; i < 2; ++i) {
      adapt_prob(&cm->fc.nmvc.comps[i].class0_hp,
                 cm->fc.pre_nmvc.comps[i].class0_hp,
John Koleszar's avatar
John Koleszar committed
440
                 cm->fc.NMVcount.comps[i].class0_hp);
441
442
      adapt_prob(&cm->fc.nmvc.comps[i].hp,
                 cm->fc.pre_nmvc.comps[i].hp,
John Koleszar's avatar
John Koleszar committed
443
                 cm->fc.NMVcount.comps[i].hp);
444
445
446
447
    }
  }
}

448
void vp9_entropy_mv_init() {
449
450
451
452
  vp9_tokens_from_tree(vp9_mv_joint_encodings, vp9_mv_joint_tree);
  vp9_tokens_from_tree(vp9_mv_class_encodings, vp9_mv_class_tree);
  vp9_tokens_from_tree(vp9_mv_class0_encodings, vp9_mv_class0_tree);
  vp9_tokens_from_tree(vp9_mv_fp_encodings, vp9_mv_fp_tree);
453
454
}

455
void vp9_init_mv_probs(VP9_COMMON *cm) {
456
  vpx_memcpy(&cm->fc.nmvc, &vp9_default_nmv_context, sizeof(nmv_context));
457
}