← Back to branch summary

~paparazzi-uav/paparazzi/v5.0-manual

« back to all changes in this revision

Viewing changes to sw/ext/opencv_bebop/opencv/3rdparty/libwebp/enc/analysis.c

  • Committer: Paparazzi buildbot
  • Date: 2016-05-18 15:00:29 UTC
  • Revision ID: felix.ruess+docbot@gmail.com-20160518150029-e8lgzi5kvb4p7un9
Manual import commit 4b8bbb730080dac23cf816b98908dacfabe2a8ec from v5.0 branch.

Show diffs side-by-side

added added

removed removed

Lines of Context:
sw/ext/opencv_bebop/opencv/3rdparty/libwebp/enc/analysis.c
 
1
// Copyright 2011 Google Inc. All Rights Reserved.
 
2
//
 
3
// Use of this source code is governed by a BSD-style license
 
4
// that can be found in the COPYING file in the root of the source
 
5
// tree. An additional intellectual property rights grant can be found
 
6
// in the file PATENTS. All contributing project authors may
 
7
// be found in the AUTHORS file in the root of the source tree.
 
8
// -----------------------------------------------------------------------------
 
9
//
 
10
// Macroblock analysis
 
11
//
 
12
// Author: Skal (pascal.massimino@gmail.com)
 
13
 
 
14
#include <stdlib.h>
 
15
#include <string.h>
 
16
#include <assert.h>
 
17
 
 
18
#include "./vp8enci.h"
 
19
#include "./cost.h"
 
20
#include "../utils/utils.h"
 
21
 
 
22
#if defined(__cplusplus) || defined(c_plusplus)
 
23
extern "C" {
 
24
#endif
 
25
 
 
26
#define MAX_ITERS_K_MEANS  6
 
27
 
 
28
//------------------------------------------------------------------------------
 
29
// Smooth the segment map by replacing isolated block by the majority of its
 
30
// neighbours.
 
31
 
 
32
static void SmoothSegmentMap(VP8Encoder* const enc) {
 
33
  int n, x, y;
 
34
  const int w = enc->mb_w_;
 
35
  const int h = enc->mb_h_;
 
36
  const int majority_cnt_3_x_3_grid = 5;
 
37
  uint8_t* const tmp = (uint8_t*)WebPSafeMalloc((uint64_t)w * h, sizeof(*tmp));
 
38
  assert((uint64_t)(w * h) == (uint64_t)w * h);   // no overflow, as per spec
 
39
 
 
40
  if (tmp == NULL) return;
 
41
  for (y = 1; y < h - 1; ++y) {
 
42
    for (x = 1; x < w - 1; ++x) {
 
43
      int cnt[NUM_MB_SEGMENTS] = { 0 };
 
44
      const VP8MBInfo* const mb = &enc->mb_info_[x + w * y];
 
45
      int majority_seg = mb->segment_;
 
46
      // Check the 8 neighbouring segment values.
 
47
      cnt[mb[-w - 1].segment_]++;  // top-left
 
48
      cnt[mb[-w + 0].segment_]++;  // top
 
49
      cnt[mb[-w + 1].segment_]++;  // top-right
 
50
      cnt[mb[   - 1].segment_]++;  // left
 
51
      cnt[mb[   + 1].segment_]++;  // right
 
52
      cnt[mb[ w - 1].segment_]++;  // bottom-left
 
53
      cnt[mb[ w + 0].segment_]++;  // bottom
 
54
      cnt[mb[ w + 1].segment_]++;  // bottom-right
 
55
      for (n = 0; n < NUM_MB_SEGMENTS; ++n) {
 
56
        if (cnt[n] >= majority_cnt_3_x_3_grid) {
 
57
          majority_seg = n;
 
58
        }
 
59
      }
 
60
      tmp[x + y * w] = majority_seg;
 
61
    }
 
62
  }
 
63
  for (y = 1; y < h - 1; ++y) {
 
64
    for (x = 1; x < w - 1; ++x) {
 
65
      VP8MBInfo* const mb = &enc->mb_info_[x + w * y];
 
66
      mb->segment_ = tmp[x + y * w];
 
67
    }
 
68
  }
 
69
  free(tmp);
 
70
}
 
71
 
 
72
//------------------------------------------------------------------------------
 
73
// set segment susceptibility alpha_ / beta_
 
74
 
 
75
static WEBP_INLINE int clip(int v, int m, int M) {
 
76
  return (v < m) ? m : (v > M) ? M : v;
 
77
}
 
78
 
 
79
static void SetSegmentAlphas(VP8Encoder* const enc,
 
80
                             const int centers[NUM_MB_SEGMENTS],
 
81
                             int mid) {
 
82
  const int nb = enc->segment_hdr_.num_segments_;
 
83
  int min = centers[0], max = centers[0];
 
84
  int n;
 
85
 
 
86
  if (nb > 1) {
 
87
    for (n = 0; n < nb; ++n) {
 
88
      if (min > centers[n]) min = centers[n];
 
89
      if (max < centers[n]) max = centers[n];
 
90
    }
 
91
  }
 
92
  if (max == min) max = min + 1;
 
93
  assert(mid <= max && mid >= min);
 
94
  for (n = 0; n < nb; ++n) {
 
95
    const int alpha = 255 * (centers[n] - mid) / (max - min);
 
96
    const int beta = 255 * (centers[n] - min) / (max - min);
 
97
    enc->dqm_[n].alpha_ = clip(alpha, -127, 127);
 
98
    enc->dqm_[n].beta_ = clip(beta, 0, 255);
 
99
  }
 
100
}
 
101
 
 
102
//------------------------------------------------------------------------------
 
103
// Compute susceptibility based on DCT-coeff histograms:
 
104
// the higher, the "easier" the macroblock is to compress.
 
105
 
 
106
#define MAX_ALPHA 255                // 8b of precision for susceptibilities.
 
107
#define ALPHA_SCALE (2 * MAX_ALPHA)  // scaling factor for alpha.
 
108
#define DEFAULT_ALPHA (-1)
 
109
#define IS_BETTER_ALPHA(alpha, best_alpha) ((alpha) > (best_alpha))
 
110
 
 
111
static int FinalAlphaValue(int alpha) {
 
112
  alpha = MAX_ALPHA - alpha;
 
113
  return clip(alpha, 0, MAX_ALPHA);
 
114
}
 
115
 
 
116
static int GetAlpha(const VP8Histogram* const histo) {
 
117
  int max_value = 0, last_non_zero = 1;
 
118
  int k;
 
119
  int alpha;
 
120
  for (k = 0; k <= MAX_COEFF_THRESH; ++k) {
 
121
    const int value = histo->distribution[k];
 
122
    if (value > 0) {
 
123
      if (value > max_value) max_value = value;
 
124
      last_non_zero = k;
 
125
    }
 
126
  }
 
127
  // 'alpha' will later be clipped to [0..MAX_ALPHA] range, clamping outer
 
128
  // values which happen to be mostly noise. This leaves the maximum precision
 
129
  // for handling the useful small values which contribute most.
 
130
  alpha = (max_value > 1) ? ALPHA_SCALE * last_non_zero / max_value : 0;
 
131
  return alpha;
 
132
}
 
133
 
 
134
static void MergeHistograms(const VP8Histogram* const in,
 
135
                            VP8Histogram* const out) {
 
136
  int i;
 
137
  for (i = 0; i <= MAX_COEFF_THRESH; ++i) {
 
138
    out->distribution[i] += in->distribution[i];
 
139
  }
 
140
}
 
141
 
 
142
//------------------------------------------------------------------------------
 
143
// Simplified k-Means, to assign Nb segments based on alpha-histogram
 
144
 
 
145
static void AssignSegments(VP8Encoder* const enc,
 
146
                           const int alphas[MAX_ALPHA + 1]) {
 
147
  const int nb = enc->segment_hdr_.num_segments_;
 
148
  int centers[NUM_MB_SEGMENTS];
 
149
  int weighted_average = 0;
 
150
  int map[MAX_ALPHA + 1];
 
151
  int a, n, k;
 
152
  int min_a = 0, max_a = MAX_ALPHA, range_a;
 
153
  // 'int' type is ok for histo, and won't overflow
 
154
  int accum[NUM_MB_SEGMENTS], dist_accum[NUM_MB_SEGMENTS];
 
155
 
 
156
  // bracket the input
 
157
  for (n = 0; n <= MAX_ALPHA && alphas[n] == 0; ++n) {}
 
158
  min_a = n;
 
159
  for (n = MAX_ALPHA; n > min_a && alphas[n] == 0; --n) {}
 
160
  max_a = n;
 
161
  range_a = max_a - min_a;
 
162
 
 
163
  // Spread initial centers evenly
 
164
  for (n = 1, k = 0; n < 2 * nb; n += 2) {
 
165
    centers[k++] = min_a + (n * range_a) / (2 * nb);
 
166
  }
 
167
 
 
168
  for (k = 0; k < MAX_ITERS_K_MEANS; ++k) {     // few iters are enough
 
169
    int total_weight;
 
170
    int displaced;
 
171
    // Reset stats
 
172
    for (n = 0; n < nb; ++n) {
 
173
      accum[n] = 0;
 
174
      dist_accum[n] = 0;
 
175
    }
 
176
    // Assign nearest center for each 'a'
 
177
    n = 0;    // track the nearest center for current 'a'
 
178
    for (a = min_a; a <= max_a; ++a) {
 
179
      if (alphas[a]) {
 
180
        while (n < nb - 1 && abs(a - centers[n + 1]) < abs(a - centers[n])) {
 
181
          n++;
 
182
        }
 
183
        map[a] = n;
 
184
        // accumulate contribution into best centroid
 
185
        dist_accum[n] += a * alphas[a];
 
186
        accum[n] += alphas[a];
 
187
      }
 
188
    }
 
189
    // All point are classified. Move the centroids to the
 
190
    // center of their respective cloud.
 
191
    displaced = 0;
 
192
    weighted_average = 0;
 
193
    total_weight = 0;
 
194
    for (n = 0; n < nb; ++n) {
 
195
      if (accum[n]) {
 
196
        const int new_center = (dist_accum[n] + accum[n] / 2) / accum[n];
 
197
        displaced += abs(centers[n] - new_center);
 
198
        centers[n] = new_center;
 
199
        weighted_average += new_center * accum[n];
 
200
        total_weight += accum[n];
 
201
      }
 
202
    }
 
203
    weighted_average = (weighted_average + total_weight / 2) / total_weight;
 
204
    if (displaced < 5) break;   // no need to keep on looping...
 
205
  }
 
206
 
 
207
  // Map each original value to the closest centroid
 
208
  for (n = 0; n < enc->mb_w_ * enc->mb_h_; ++n) {
 
209
    VP8MBInfo* const mb = &enc->mb_info_[n];
 
210
    const int alpha = mb->alpha_;
 
211
    mb->segment_ = map[alpha];
 
212
    mb->alpha_ = centers[map[alpha]];  // for the record.
 
213
  }
 
214
 
 
215
  if (nb > 1) {
 
216
    const int smooth = (enc->config_->preprocessing & 1);
 
217
    if (smooth) SmoothSegmentMap(enc);
 
218
  }
 
219
 
 
220
  SetSegmentAlphas(enc, centers, weighted_average);  // pick some alphas.
 
221
}
 
222
 
 
223
//------------------------------------------------------------------------------
 
224
// Macroblock analysis: collect histogram for each mode, deduce the maximal
 
225
// susceptibility and set best modes for this macroblock.
 
226
// Segment assignment is done later.
 
227
 
 
228
// Number of modes to inspect for alpha_ evaluation. For high-quality settings
 
229
// (method >= FAST_ANALYSIS_METHOD) we don't need to test all the possible modes
 
230
// during the analysis phase.
 
231
#define FAST_ANALYSIS_METHOD 4  // method above which we do partial analysis
 
232
#define MAX_INTRA16_MODE 2
 
233
#define MAX_INTRA4_MODE  2
 
234
#define MAX_UV_MODE      2
 
235
 
 
236
static int MBAnalyzeBestIntra16Mode(VP8EncIterator* const it) {
 
237
  const int max_mode =
 
238
      (it->enc_->method_ >= FAST_ANALYSIS_METHOD) ? MAX_INTRA16_MODE
 
239
                                                  : NUM_PRED_MODES;
 
240
  int mode;
 
241
  int best_alpha = DEFAULT_ALPHA;
 
242
  int best_mode = 0;
 
243
 
 
244
  VP8MakeLuma16Preds(it);
 
245
  for (mode = 0; mode < max_mode; ++mode) {
 
246
    VP8Histogram histo = { { 0 } };
 
247
    int alpha;
 
248
 
 
249
    VP8CollectHistogram(it->yuv_in_ + Y_OFF,
 
250
                        it->yuv_p_ + VP8I16ModeOffsets[mode],
 
251
                        0, 16, &histo);
 
252
    alpha = GetAlpha(&histo);
 
253
    if (IS_BETTER_ALPHA(alpha, best_alpha)) {
 
254
      best_alpha = alpha;
 
255
      best_mode = mode;
 
256
    }
 
257
  }
 
258
  VP8SetIntra16Mode(it, best_mode);
 
259
  return best_alpha;
 
260
}
 
261
 
 
262
static int MBAnalyzeBestIntra4Mode(VP8EncIterator* const it,
 
263
                                   int best_alpha) {
 
264
  uint8_t modes[16];
 
265
  const int max_mode =
 
266
      (it->enc_->method_ >= FAST_ANALYSIS_METHOD) ? MAX_INTRA4_MODE
 
267
                                                  : NUM_BMODES;
 
268
  int i4_alpha;
 
269
  VP8Histogram total_histo = { { 0 } };
 
270
  int cur_histo = 0;
 
271
 
 
272
  VP8IteratorStartI4(it);
 
273
  do {
 
274
    int mode;
 
275
    int best_mode_alpha = DEFAULT_ALPHA;
 
276
    VP8Histogram histos[2];
 
277
    const uint8_t* const src = it->yuv_in_ + Y_OFF + VP8Scan[it->i4_];
 
278
 
 
279
    VP8MakeIntra4Preds(it);
 
280
    for (mode = 0; mode < max_mode; ++mode) {
 
281
      int alpha;
 
282
 
 
283
      memset(&histos[cur_histo], 0, sizeof(histos[cur_histo]));
 
284
      VP8CollectHistogram(src, it->yuv_p_ + VP8I4ModeOffsets[mode],
 
285
                          0, 1, &histos[cur_histo]);
 
286
      alpha = GetAlpha(&histos[cur_histo]);
 
287
      if (IS_BETTER_ALPHA(alpha, best_mode_alpha)) {
 
288
        best_mode_alpha = alpha;
 
289
        modes[it->i4_] = mode;
 
290
        cur_histo ^= 1;   // keep track of best histo so far.
 
291
      }
 
292
    }
 
293
    // accumulate best histogram
 
294
    MergeHistograms(&histos[cur_histo ^ 1], &total_histo);
 
295
    // Note: we reuse the original samples for predictors
 
296
  } while (VP8IteratorRotateI4(it, it->yuv_in_ + Y_OFF));
 
297
 
 
298
  i4_alpha = GetAlpha(&total_histo);
 
299
  if (IS_BETTER_ALPHA(i4_alpha, best_alpha)) {
 
300
    VP8SetIntra4Mode(it, modes);
 
301
    best_alpha = i4_alpha;
 
302
  }
 
303
  return best_alpha;
 
304
}
 
305
 
 
306
static int MBAnalyzeBestUVMode(VP8EncIterator* const it) {
 
307
  int best_alpha = DEFAULT_ALPHA;
 
308
  int best_mode = 0;
 
309
  const int max_mode =
 
310
      (it->enc_->method_ >= FAST_ANALYSIS_METHOD) ? MAX_UV_MODE
 
311
                                                  : NUM_PRED_MODES;
 
312
  int mode;
 
313
  VP8MakeChroma8Preds(it);
 
314
  for (mode = 0; mode < max_mode; ++mode) {
 
315
    VP8Histogram histo = { { 0 } };
 
316
    int alpha;
 
317
    VP8CollectHistogram(it->yuv_in_ + U_OFF,
 
318
                        it->yuv_p_ + VP8UVModeOffsets[mode],
 
319
                        16, 16 + 4 + 4, &histo);
 
320
    alpha = GetAlpha(&histo);
 
321
    if (IS_BETTER_ALPHA(alpha, best_alpha)) {
 
322
      best_alpha = alpha;
 
323
      best_mode = mode;
 
324
    }
 
325
  }
 
326
  VP8SetIntraUVMode(it, best_mode);
 
327
  return best_alpha;
 
328
}
 
329
 
 
330
static void MBAnalyze(VP8EncIterator* const it,
 
331
                      int alphas[MAX_ALPHA + 1],
 
332
                      int* const alpha, int* const uv_alpha) {
 
333
  const VP8Encoder* const enc = it->enc_;
 
334
  int best_alpha, best_uv_alpha;
 
335
 
 
336
  VP8SetIntra16Mode(it, 0);  // default: Intra16, DC_PRED
 
337
  VP8SetSkip(it, 0);         // not skipped
 
338
  VP8SetSegment(it, 0);      // default segment, spec-wise.
 
339
 
 
340
  best_alpha = MBAnalyzeBestIntra16Mode(it);
 
341
  if (enc->method_ >= 5) {
 
342
    // We go and make a fast decision for intra4/intra16.
 
343
    // It's usually not a good and definitive pick, but helps seeding the stats
 
344
    // about level bit-cost.
 
345
    // TODO(skal): improve criterion.
 
346
    best_alpha = MBAnalyzeBestIntra4Mode(it, best_alpha);
 
347
  }
 
348
  best_uv_alpha = MBAnalyzeBestUVMode(it);
 
349
 
 
350
  // Final susceptibility mix
 
351
  best_alpha = (3 * best_alpha + best_uv_alpha + 2) >> 2;
 
352
  best_alpha = FinalAlphaValue(best_alpha);
 
353
  alphas[best_alpha]++;
 
354
  it->mb_->alpha_ = best_alpha;   // for later remapping.
 
355
 
 
356
  // Accumulate for later complexity analysis.
 
357
  *alpha += best_alpha;   // mixed susceptibility (not just luma)
 
358
  *uv_alpha += best_uv_alpha;
 
359
}
 
360
 
 
361
static void DefaultMBInfo(VP8MBInfo* const mb) {
 
362
  mb->type_ = 1;     // I16x16
 
363
  mb->uv_mode_ = 0;
 
364
  mb->skip_ = 0;     // not skipped
 
365
  mb->segment_ = 0;  // default segment
 
366
  mb->alpha_ = 0;
 
367
}
 
368
 
 
369
//------------------------------------------------------------------------------
 
370
// Main analysis loop:
 
371
// Collect all susceptibilities for each macroblock and record their
 
372
// distribution in alphas[]. Segments is assigned a-posteriori, based on
 
373
// this histogram.
 
374
// We also pick an intra16 prediction mode, which shouldn't be considered
 
375
// final except for fast-encode settings. We can also pick some intra4 modes
 
376
// and decide intra4/intra16, but that's usually almost always a bad choice at
 
377
// this stage.
 
378
 
 
379
static void ResetAllMBInfo(VP8Encoder* const enc) {
 
380
  int n;
 
381
  for (n = 0; n < enc->mb_w_ * enc->mb_h_; ++n) {
 
382
    DefaultMBInfo(&enc->mb_info_[n]);
 
383
  }
 
384
  // Default susceptibilities.
 
385
  enc->dqm_[0].alpha_ = 0;
 
386
  enc->dqm_[0].beta_ = 0;
 
387
  // Note: we can't compute this alpha_ / uv_alpha_.
 
388
  WebPReportProgress(enc->pic_, enc->percent_ + 20, &enc->percent_);
 
389
}
 
390
 
 
391
int VP8EncAnalyze(VP8Encoder* const enc) {
 
392
  int ok = 1;
 
393
  const int do_segments =
 
394
      enc->config_->emulate_jpeg_size ||   // We need the complexity evaluation.
 
395
      (enc->segment_hdr_.num_segments_ > 1) ||
 
396
      (enc->method_ == 0);  // for method 0, we need preds_[] to be filled.
 
397
  enc->alpha_ = 0;
 
398
  enc->uv_alpha_ = 0;
 
399
  if (do_segments) {
 
400
    int alphas[MAX_ALPHA + 1] = { 0 };
 
401
    VP8EncIterator it;
 
402
 
 
403
    VP8IteratorInit(enc, &it);
 
404
    do {
 
405
      VP8IteratorImport(&it);
 
406
      MBAnalyze(&it, alphas, &enc->alpha_, &enc->uv_alpha_);
 
407
      ok = VP8IteratorProgress(&it, 20);
 
408
      // Let's pretend we have perfect lossless reconstruction.
 
409
    } while (ok && VP8IteratorNext(&it, it.yuv_in_));
 
410
    enc->alpha_ /= enc->mb_w_ * enc->mb_h_;
 
411
    enc->uv_alpha_ /= enc->mb_w_ * enc->mb_h_;
 
412
    if (ok) AssignSegments(enc, alphas);
 
413
  } else {   // Use only one default segment.
 
414
    ResetAllMBInfo(enc);
 
415
  }
 
416
  return ok;
 
417
}
 
418
 
 
419
#if defined(__cplusplus) || defined(c_plusplus)
 
420
}    // extern "C"
 
421
#endif