segmentation.c 11.3 KB
Newer Older
Jingning Han's avatar
Jingning Han committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
 *  Copyright (c) 2012 The WebM project authors. All Rights Reserved.
 *
 *  Use of this source code is governed by a BSD-style license
 *  that can be found in the LICENSE file in the root of the source
 *  tree. An additional intellectual property rights grant can be found
 *  in the file PATENTS.  All contributing project authors may
 *  be found in the AUTHORS file in the root of the source tree.
 */


#include <limits.h>

#include "vpx_mem/vpx_mem.h"

16
17
#include "vp10/common/pred_common.h"
#include "vp10/common/tile_common.h"
Jingning Han's avatar
Jingning Han committed
18

19
20
#include "vp10/encoder/cost.h"
#include "vp10/encoder/segmentation.h"
21
#include "vp10/encoder/subexp.h"
Jingning Han's avatar
Jingning Han committed
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

void vp10_enable_segmentation(struct segmentation *seg) {
  seg->enabled = 1;
  seg->update_map = 1;
  seg->update_data = 1;
}

void vp10_disable_segmentation(struct segmentation *seg) {
  seg->enabled = 0;
  seg->update_map = 0;
  seg->update_data = 0;
}

void vp10_set_segment_data(struct segmentation *seg,
                          signed char *feature_data,
                          unsigned char abs_delta) {
  seg->abs_delta = abs_delta;

  memcpy(seg->feature_data, feature_data, sizeof(seg->feature_data));
}
void vp10_disable_segfeature(struct segmentation *seg, int segment_id,
                            SEG_LVL_FEATURES feature_id) {
  seg->feature_mask[segment_id] &= ~(1 << feature_id);
}

void vp10_clear_segdata(struct segmentation *seg, int segment_id,
                       SEG_LVL_FEATURES feature_id) {
  seg->feature_data[segment_id][feature_id] = 0;
}

// Based on set of segment counts calculate a probability tree
53
54
static void calc_segtree_probs(unsigned *segcounts,
    vpx_prob *segment_tree_probs, const vpx_prob *cur_tree_probs) {
Jingning Han's avatar
Jingning Han committed
55
  // Work out probabilities of each segment
56
57
58
59
60
61
62
63
64
65
66
67
  const unsigned cc[4] = {
    segcounts[0] + segcounts[1], segcounts[2] + segcounts[3],
    segcounts[4] + segcounts[5], segcounts[6] + segcounts[7]
  };
  const unsigned ccc[2] = { cc[0] + cc[1], cc[2] + cc[3] };
#if CONFIG_MISC_FIXES
  int i;
#endif

  segment_tree_probs[0] = get_binary_prob(ccc[0], ccc[1]);
  segment_tree_probs[1] = get_binary_prob(cc[0], cc[1]);
  segment_tree_probs[2] = get_binary_prob(cc[2], cc[3]);
Jingning Han's avatar
Jingning Han committed
68
69
70
71
  segment_tree_probs[3] = get_binary_prob(segcounts[0], segcounts[1]);
  segment_tree_probs[4] = get_binary_prob(segcounts[2], segcounts[3]);
  segment_tree_probs[5] = get_binary_prob(segcounts[4], segcounts[5]);
  segment_tree_probs[6] = get_binary_prob(segcounts[6], segcounts[7]);
72
73
74
75
76
77
78
79
80
81
82

#if CONFIG_MISC_FIXES
  for (i = 0; i < 7; i++) {
    const unsigned *ct = i == 0 ? ccc : i < 3 ? cc + (i & 2)
        : segcounts + (i - 3) * 2;
    vp10_prob_diff_update_savings_search(ct,
        cur_tree_probs[i], &segment_tree_probs[i], DIFF_UPDATE_PROB);
  }
#else
  (void) cur_tree_probs;
#endif
Jingning Han's avatar
Jingning Han committed
83
84
85
}

// Based on set of segment counts and probabilities calculate a cost estimate
86
static int cost_segmap(unsigned *segcounts, vpx_prob *probs) {
Jingning Han's avatar
Jingning Han committed
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
  const int c01 = segcounts[0] + segcounts[1];
  const int c23 = segcounts[2] + segcounts[3];
  const int c45 = segcounts[4] + segcounts[5];
  const int c67 = segcounts[6] + segcounts[7];
  const int c0123 = c01 + c23;
  const int c4567 = c45 + c67;

  // Cost the top node of the tree
  int cost = c0123 * vp10_cost_zero(probs[0]) +
             c4567 * vp10_cost_one(probs[0]);

  // Cost subsequent levels
  if (c0123 > 0) {
    cost += c01 * vp10_cost_zero(probs[1]) +
            c23 * vp10_cost_one(probs[1]);

    if (c01 > 0)
      cost += segcounts[0] * vp10_cost_zero(probs[3]) +
              segcounts[1] * vp10_cost_one(probs[3]);
    if (c23 > 0)
      cost += segcounts[2] * vp10_cost_zero(probs[4]) +
              segcounts[3] * vp10_cost_one(probs[4]);
  }

  if (c4567 > 0) {
    cost += c45 * vp10_cost_zero(probs[2]) +
            c67 * vp10_cost_one(probs[2]);

    if (c45 > 0)
      cost += segcounts[4] * vp10_cost_zero(probs[5]) +
              segcounts[5] * vp10_cost_one(probs[5]);
    if (c67 > 0)
      cost += segcounts[6] * vp10_cost_zero(probs[6]) +
              segcounts[7] * vp10_cost_one(probs[6]);
  }

  return cost;
}

Yaowu Xu's avatar
Yaowu Xu committed
126
static void count_segs(const VP10_COMMON *cm, MACROBLOCKD *xd,
Jingning Han's avatar
Jingning Han committed
127
                       const TileInfo *tile, MODE_INFO **mi,
128
129
130
                       unsigned *no_pred_segcounts,
                       unsigned (*temporal_predictor_count)[2],
                       unsigned *t_unpred_seg_counts,
Jingning Han's avatar
Jingning Han committed
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
                       int bw, int bh, int mi_row, int mi_col) {
  int segment_id;

  if (mi_row >= cm->mi_rows || mi_col >= cm->mi_cols)
    return;

  xd->mi = mi;
  segment_id = xd->mi[0]->mbmi.segment_id;

  set_mi_row_col(xd, tile, mi_row, bh, mi_col, bw, cm->mi_rows, cm->mi_cols);

  // Count the number of hits on each segment with no prediction
  no_pred_segcounts[segment_id]++;

  // Temporal prediction not allowed on key frames
  if (cm->frame_type != KEY_FRAME) {
    const BLOCK_SIZE bsize = xd->mi[0]->mbmi.sb_type;
    // Test to see if the segment id matches the predicted value.
    const int pred_segment_id = get_segment_id(cm, cm->last_frame_seg_map,
                                               bsize, mi_row, mi_col);
    const int pred_flag = pred_segment_id == segment_id;
    const int pred_context = vp10_get_pred_context_seg_id(xd);

    // Store the prediction status for this mb and update counts
    // as appropriate
    xd->mi[0]->mbmi.seg_id_predicted = pred_flag;
    temporal_predictor_count[pred_context][pred_flag]++;

    // Update the "unpredicted" segment count
    if (!pred_flag)
      t_unpred_seg_counts[segment_id]++;
  }
}

Yaowu Xu's avatar
Yaowu Xu committed
165
static void count_segs_sb(const VP10_COMMON *cm, MACROBLOCKD *xd,
Jingning Han's avatar
Jingning Han committed
166
                          const TileInfo *tile, MODE_INFO **mi,
167
168
169
                          unsigned *no_pred_segcounts,
                          unsigned (*temporal_predictor_count)[2],
                          unsigned *t_unpred_seg_counts,
Jingning Han's avatar
Jingning Han committed
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
210
211
212
213
214
                          int mi_row, int mi_col,
                          BLOCK_SIZE bsize) {
  const int mis = cm->mi_stride;
  int bw, bh;
  const int bs = num_8x8_blocks_wide_lookup[bsize], hbs = bs / 2;

  if (mi_row >= cm->mi_rows || mi_col >= cm->mi_cols)
    return;

  bw = num_8x8_blocks_wide_lookup[mi[0]->mbmi.sb_type];
  bh = num_8x8_blocks_high_lookup[mi[0]->mbmi.sb_type];

  if (bw == bs && bh == bs) {
    count_segs(cm, xd, tile, mi, no_pred_segcounts, temporal_predictor_count,
               t_unpred_seg_counts, bs, bs, mi_row, mi_col);
  } else if (bw == bs && bh < bs) {
    count_segs(cm, xd, tile, mi, no_pred_segcounts, temporal_predictor_count,
               t_unpred_seg_counts, bs, hbs, mi_row, mi_col);
    count_segs(cm, xd, tile, mi + hbs * mis, no_pred_segcounts,
               temporal_predictor_count, t_unpred_seg_counts, bs, hbs,
               mi_row + hbs, mi_col);
  } else if (bw < bs && bh == bs) {
    count_segs(cm, xd, tile, mi, no_pred_segcounts, temporal_predictor_count,
               t_unpred_seg_counts, hbs, bs, mi_row, mi_col);
    count_segs(cm, xd, tile, mi + hbs,
               no_pred_segcounts, temporal_predictor_count, t_unpred_seg_counts,
               hbs, bs, mi_row, mi_col + hbs);
  } else {
    const BLOCK_SIZE subsize = subsize_lookup[PARTITION_SPLIT][bsize];
    int n;

    assert(bw < bs && bh < bs);

    for (n = 0; n < 4; n++) {
      const int mi_dc = hbs * (n & 1);
      const int mi_dr = hbs * (n >> 1);

      count_segs_sb(cm, xd, tile, &mi[mi_dr * mis + mi_dc],
                    no_pred_segcounts, temporal_predictor_count,
                    t_unpred_seg_counts,
                    mi_row + mi_dr, mi_col + mi_dc, subsize);
    }
  }
}

Yaowu Xu's avatar
Yaowu Xu committed
215
void vp10_choose_segmap_coding_method(VP10_COMMON *cm, MACROBLOCKD *xd) {
Jingning Han's avatar
Jingning Han committed
216
  struct segmentation *seg = &cm->seg;
217
218
219
220
221
#if CONFIG_MISC_FIXES
  struct segmentation_probs *segp = &cm->fc->seg;
#else
  struct segmentation_probs *segp = &cm->segp;
#endif
Jingning Han's avatar
Jingning Han committed
222
223
224
225
226
227

  int no_pred_cost;
  int t_pred_cost = INT_MAX;

  int i, tile_col, mi_row, mi_col;

228
229
230
231
232
233
234
235
236
#if CONFIG_MISC_FIXES
  unsigned (*temporal_predictor_count)[2] = cm->counts.seg.pred;
  unsigned *no_pred_segcounts = cm->counts.seg.tree_total;
  unsigned *t_unpred_seg_counts = cm->counts.seg.tree_mispred;
#else
  unsigned temporal_predictor_count[PREDICTION_PROBS][2] = { { 0 } };
  unsigned no_pred_segcounts[MAX_SEGMENTS] = { 0 };
  unsigned t_unpred_seg_counts[MAX_SEGMENTS] = { 0 };
#endif
Jingning Han's avatar
Jingning Han committed
237
238
239
240
241

  vpx_prob no_pred_tree[SEG_TREE_PROBS];
  vpx_prob t_pred_tree[SEG_TREE_PROBS];
  vpx_prob t_nopred_prob[PREDICTION_PROBS];

242
243
244
#if CONFIG_MISC_FIXES
  (void) xd;
#else
Jingning Han's avatar
Jingning Han committed
245
246
  // Set default state for the segment tree probabilities and the
  // temporal coding probabilities
247
248
249
  memset(segp->tree_probs, 255, sizeof(segp->tree_probs));
  memset(segp->pred_probs, 255, sizeof(segp->pred_probs));
#endif
Jingning Han's avatar
Jingning Han committed
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271

  // First of all generate stats regarding how well the last segment map
  // predicts this one
  for (tile_col = 0; tile_col < 1 << cm->log2_tile_cols; tile_col++) {
    TileInfo tile;
    MODE_INFO **mi_ptr;
    vp10_tile_init(&tile, cm, 0, tile_col);

    mi_ptr = cm->mi_grid_visible + tile.mi_col_start;
    for (mi_row = 0; mi_row < cm->mi_rows;
         mi_row += 8, mi_ptr += 8 * cm->mi_stride) {
      MODE_INFO **mi = mi_ptr;
      for (mi_col = tile.mi_col_start; mi_col < tile.mi_col_end;
           mi_col += 8, mi += 8)
        count_segs_sb(cm, xd, &tile, mi, no_pred_segcounts,
                      temporal_predictor_count, t_unpred_seg_counts,
                      mi_row, mi_col, BLOCK_64X64);
    }
  }

  // Work out probability tree for coding segments without prediction
  // and the cost.
272
  calc_segtree_probs(no_pred_segcounts, no_pred_tree, segp->tree_probs);
Jingning Han's avatar
Jingning Han committed
273
274
275
  no_pred_cost = cost_segmap(no_pred_segcounts, no_pred_tree);

  // Key frames cannot use temporal prediction
276
  if (!frame_is_intra_only(cm) && !cm->error_resilient_mode) {
Jingning Han's avatar
Jingning Han committed
277
278
    // Work out probability tree for coding those segments not
    // predicted using the temporal method and the cost.
279
    calc_segtree_probs(t_unpred_seg_counts, t_pred_tree, segp->tree_probs);
Jingning Han's avatar
Jingning Han committed
280
281
282
283
284
285
286
    t_pred_cost = cost_segmap(t_unpred_seg_counts, t_pred_tree);

    // Add in the cost of the signaling for each prediction context.
    for (i = 0; i < PREDICTION_PROBS; i++) {
      const int count0 = temporal_predictor_count[i][0];
      const int count1 = temporal_predictor_count[i][1];

287
288
289
290
291
#if CONFIG_MISC_FIXES
      vp10_prob_diff_update_savings_search(temporal_predictor_count[i],
                                           segp->pred_probs[i],
                                           &t_nopred_prob[i], DIFF_UPDATE_PROB);
#else
Jingning Han's avatar
Jingning Han committed
292
      t_nopred_prob[i] = get_binary_prob(count0, count1);
293
#endif
Jingning Han's avatar
Jingning Han committed
294
295
296
297
298
299
300
301
302

      // Add in the predictor signaling cost
      t_pred_cost += count0 * vp10_cost_zero(t_nopred_prob[i]) +
                     count1 * vp10_cost_one(t_nopred_prob[i]);
    }
  }

  // Now choose which coding method to use.
  if (t_pred_cost < no_pred_cost) {
303
    assert(!cm->error_resilient_mode);
Jingning Han's avatar
Jingning Han committed
304
    seg->temporal_update = 1;
305
306
307
308
#if !CONFIG_MISC_FIXES
    memcpy(segp->tree_probs, t_pred_tree, sizeof(t_pred_tree));
    memcpy(segp->pred_probs, t_nopred_prob, sizeof(t_nopred_prob));
#endif
Jingning Han's avatar
Jingning Han committed
309
310
  } else {
    seg->temporal_update = 0;
311
312
313
#if !CONFIG_MISC_FIXES
    memcpy(segp->tree_probs, no_pred_tree, sizeof(no_pred_tree));
#endif
Jingning Han's avatar
Jingning Han committed
314
315
316
  }
}

317
318
319
320
321
322
void vp10_reset_segment_features(VP10_COMMON *cm) {
  struct segmentation *seg = &cm->seg;
#if !CONFIG_MISC_FIXES
  struct segmentation_probs *segp = &cm->segp;
#endif

Jingning Han's avatar
Jingning Han committed
323
324
325
326
  // Set up default state for MB feature flags
  seg->enabled = 0;
  seg->update_map = 0;
  seg->update_data = 0;
327
328
329
#if !CONFIG_MISC_FIXES
  memset(segp->tree_probs, 255, sizeof(segp->tree_probs));
#endif
Jingning Han's avatar
Jingning Han committed
330
331
  vp10_clearall_segfeatures(seg);
}