src/third_party/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