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 #define MAX_ITERS_K_MEANS  6
  23
  24 //------------------------------------------------------------------------------
  25 // Smooth the segment map by replacing isolated block by the majority of its
  26 // neighbours.
  27
  28 static void SmoothSegmentMap(VP8Encoder* const enc) {
  29   int n, x, y;
  30   const int w = enc->mb_w_;
  31   const int h = enc->mb_h_;
  32   const int majority_cnt_3_x_3_grid = 5;
  33   uint8_t* const tmp = (uint8_t*)WebPSafeMalloc(w * h, sizeof(*tmp));
  34   assert((uint64_t)(w * h) == (uint64_t)w * h);   // no overflow, as per spec
  35
  36   if (tmp == NULL) return;
  37   for (y = 1; y < h - 1; ++y) {
  38     for (x = 1; x < w - 1; ++x) {
  39       int cnt[NUM_MB_SEGMENTS] = { 0 };
  40       const VP8MBInfo* const mb = &enc->mb_info_[x + w * y];
  41       int majority_seg = mb->segment_;
  42       // Check the 8 neighbouring segment values.
  43       cnt[mb[-w - 1].segment_]++;  // top-left
  44       cnt[mb[-w + 0].segment_]++;  // top
  45       cnt[mb[-w + 1].segment_]++;  // top-right
  46       cnt[mb[   - 1].segment_]++;  // left
  47       cnt[mb[   + 1].segment_]++;  // right
  48       cnt[mb[ w - 1].segment_]++;  // bottom-left
  49       cnt[mb[ w + 0].segment_]++;  // bottom
  50       cnt[mb[ w + 1].segment_]++;  // bottom-right
  51       for (n = 0; n < NUM_MB_SEGMENTS; ++n) {
  52         if (cnt[n] >= majority_cnt_3_x_3_grid) {
  53           majority_seg = n;
  54           break;
  55         }
  56       }
  57       tmp[x + y * w] = majority_seg;
  58     }
  59   }
  60   for (y = 1; y < h - 1; ++y) {
  61     for (x = 1; x < w - 1; ++x) {
  62       VP8MBInfo* const mb = &enc->mb_info_[x + w * y];
  63       mb->segment_ = tmp[x + y * w];
  64     }
  65   }
  66   WebPSafeFree(tmp);
  67 }
  68
  69 //------------------------------------------------------------------------------
  70 // set segment susceptibility alpha_ / beta_
  71
  72 static WEBP_INLINE int clip(int v, int m, int M) {
  73   return (v < m) ? m : (v > M) ? M : v;
  74 }
  75
  76 static void SetSegmentAlphas(VP8Encoder* const enc,
  77                              const int centers[NUM_MB_SEGMENTS],
  78                              int mid) {
  79   const int nb = enc->segment_hdr_.num_segments_;
  80   int min = centers[0], max = centers[0];
  81   int n;
  82
  83   if (nb > 1) {
  84     for (n = 0; n < nb; ++n) {
  85       if (min > centers[n]) min = centers[n];
  86       if (max < centers[n]) max = centers[n];
  87     }
  88   }
  89   if (max == min) max = min + 1;
  90   assert(mid <= max && mid >= min);
  91   for (n = 0; n < nb; ++n) {
  92     const int alpha = 255 * (centers[n] - mid) / (max - min);
  93     const int beta = 255 * (centers[n] - min) / (max - min);
  94     enc->dqm_[n].alpha_ = clip(alpha, -127, 127);
  95     enc->dqm_[n].beta_ = clip(beta, 0, 255);
  96   }
  97 }
  98
  99 //------------------------------------------------------------------------------
 100 // Compute susceptibility based on DCT-coeff histograms:
 101 // the higher, the "easier" the macroblock is to compress.
 102
 103 #define MAX_ALPHA 255                // 8b of precision for susceptibilities.
 104 #define ALPHA_SCALE (2 * MAX_ALPHA)  // scaling factor for alpha.
 105 #define DEFAULT_ALPHA (-1)
 106 #define IS_BETTER_ALPHA(alpha, best_alpha) ((alpha) > (best_alpha))
 107
 108 static int FinalAlphaValue(int alpha) {
 109   alpha = MAX_ALPHA - alpha;
 110   return clip(alpha, 0, MAX_ALPHA);
 111 }
 112
 113 static int GetAlpha(const VP8Histogram* const histo) {
 114   int max_value = 0, last_non_zero = 1;
 115   int k;
 116   int alpha;
 117   for (k = 0; k <= MAX_COEFF_THRESH; ++k) {
 118     const int value = histo->distribution[k];
 119     if (value > 0) {
 120       if (value > max_value) max_value = value;
 121       last_non_zero = k;
 122     }
 123   }
 124   // 'alpha' will later be clipped to [0..MAX_ALPHA] range, clamping outer
 125   // values which happen to be mostly noise. This leaves the maximum precision
 126   // for handling the useful small values which contribute most.
 127   alpha = (max_value > 1) ? ALPHA_SCALE * last_non_zero / max_value : 0;
 128   return alpha;
 129 }
 130
 131 static void MergeHistograms(const VP8Histogram* const in,
 132                             VP8Histogram* const out) {
 133   int i;
 134   for (i = 0; i <= MAX_COEFF_THRESH; ++i) {
 135     out->distribution[i] += in->distribution[i];
 136   }
 137 }
 138
 139 //------------------------------------------------------------------------------
 140 // Simplified k-Means, to assign Nb segments based on alpha-histogram
 141
 142 static void AssignSegments(VP8Encoder* const enc,
 143                            const int alphas[MAX_ALPHA + 1]) {
 144   // 'num_segments_' is previously validated and <= NUM_MB_SEGMENTS, but an
 145   // explicit check is needed to avoid spurious warning about 'n + 1' exceeding
 146   // array bounds of 'centers' with some compilers (noticed with gcc-4.9).
 147   const int nb = (enc->segment_hdr_.num_segments_ < NUM_MB_SEGMENTS) ?
 148                  enc->segment_hdr_.num_segments_ : NUM_MB_SEGMENTS;
 149   int centers[NUM_MB_SEGMENTS];
 150   int weighted_average = 0;
 151   int map[MAX_ALPHA + 1];
 152   int a, n, k;
 153   int min_a = 0, max_a = MAX_ALPHA, range_a;
 154   // 'int' type is ok for histo, and won't overflow
 155   int accum[NUM_MB_SEGMENTS], dist_accum[NUM_MB_SEGMENTS];
 156
 157   assert(nb >= 1);
 158   assert(nb <= NUM_MB_SEGMENTS);
 159
 160   // bracket the input
 161   for (n = 0; n <= MAX_ALPHA && alphas[n] == 0; ++n) {}
 162   min_a = n;
 163   for (n = MAX_ALPHA; n > min_a && alphas[n] == 0; --n) {}
 164   max_a = n;
 165   range_a = max_a - min_a;
 166
 167   // Spread initial centers evenly
 168   for (k = 0, n = 1; k < nb; ++k, n += 2) {
 169     assert(n < 2 * nb);
 170     centers[k] = min_a + (n * range_a) / (2 * nb);
 171   }
 172
 173   for (k = 0; k < MAX_ITERS_K_MEANS; ++k) {     // few iters are enough
 174     int total_weight;
 175     int displaced;
 176     // Reset stats
 177     for (n = 0; n < nb; ++n) {
 178       accum[n] = 0;
 179       dist_accum[n] = 0;
 180     }
 181     // Assign nearest center for each 'a'
 182     n = 0;    // track the nearest center for current 'a'
 183     for (a = min_a; a <= max_a; ++a) {
 184       if (alphas[a]) {
 185         while (n + 1 < nb && abs(a - centers[n + 1]) < abs(a - centers[n])) {
 186           n++;
 187         }
 188         map[a] = n;
 189         // accumulate contribution into best centroid
 190         dist_accum[n] += a * alphas[a];
 191         accum[n] += alphas[a];
 192       }
 193     }
 194     // All point are classified. Move the centroids to the
 195     // center of their respective cloud.
 196     displaced = 0;
 197     weighted_average = 0;
 198     total_weight = 0;
 199     for (n = 0; n < nb; ++n) {
 200       if (accum[n]) {
 201         const int new_center = (dist_accum[n] + accum[n] / 2) / accum[n];
 202         displaced += abs(centers[n] - new_center);
 203         centers[n] = new_center;
 204         weighted_average += new_center * accum[n];
 205         total_weight += accum[n];
 206       }
 207     }
 208     weighted_average = (weighted_average + total_weight / 2) / total_weight;
 209     if (displaced < 5) break;   // no need to keep on looping...
 210   }
 211
 212   // Map each original value to the closest centroid
 213   for (n = 0; n < enc->mb_w_ * enc->mb_h_; ++n) {
 214     VP8MBInfo* const mb = &enc->mb_info_[n];
 215     const int alpha = mb->alpha_;
 216     mb->segment_ = map[alpha];
 217     mb->alpha_ = centers[map[alpha]];  // for the record.
 218   }
 219
 220   if (nb > 1) {
 221     const int smooth = (enc->config_->preprocessing & 1);
 222     if (smooth) SmoothSegmentMap(enc);
 223   }
 224
 225   SetSegmentAlphas(enc, centers, weighted_average);  // pick some alphas.
 226 }
 227
 228 //------------------------------------------------------------------------------
 229 // Macroblock analysis: collect histogram for each mode, deduce the maximal
 230 // susceptibility and set best modes for this macroblock.
 231 // Segment assignment is done later.
 232
 233 // Number of modes to inspect for alpha_ evaluation. We don't need to test all
 234 // the possible modes during the analysis phase: we risk falling into a local
 235 // optimum, or be subject to boundary effect
 236 #define MAX_INTRA16_MODE 2
 237 #define MAX_INTRA4_MODE  2
 238 #define MAX_UV_MODE      2
 239
 240 static int MBAnalyzeBestIntra16Mode(VP8EncIterator* const it) {
 241   const int max_mode = MAX_INTRA16_MODE;
 242   int mode;
 243   int best_alpha = DEFAULT_ALPHA;
 244   int best_mode = 0;
 245
 246   VP8MakeLuma16Preds(it);
 247   for (mode = 0; mode < max_mode; ++mode) {
 248     VP8Histogram histo = { { 0 } };
 249     int alpha;
 250
 251     VP8CollectHistogram(it->yuv_in_ + Y_OFF,
 252                         it->yuv_p_ + VP8I16ModeOffsets[mode],
 253                         0, 16, &histo);
 254     alpha = GetAlpha(&histo);
 255     if (IS_BETTER_ALPHA(alpha, best_alpha)) {
 256       best_alpha = alpha;
 257       best_mode = mode;
 258     }
 259   }
 260   VP8SetIntra16Mode(it, best_mode);
 261   return best_alpha;
 262 }
 263
 264 static int MBAnalyzeBestIntra4Mode(VP8EncIterator* const it,
 265                                    int best_alpha) {
 266   uint8_t modes[16];
 267   const int max_mode = MAX_INTRA4_MODE;
 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 = MAX_UV_MODE;
 310   int mode;
 311
 312   VP8MakeChroma8Preds(it);
 313   for (mode = 0; mode < max_mode; ++mode) {
 314     VP8Histogram histo = { { 0 } };
 315     int alpha;
 316     VP8CollectHistogram(it->yuv_in_ + U_OFF,
 317                         it->yuv_p_ + VP8UVModeOffsets[mode],
 318                         16, 16 + 4 + 4, &histo);
 319     alpha = GetAlpha(&histo);
 320     if (IS_BETTER_ALPHA(alpha, best_alpha)) {
 321       best_alpha = alpha;
 322       best_mode = mode;
 323     }
 324   }
 325   VP8SetIntraUVMode(it, best_mode);
 326   return best_alpha;
 327 }
 328
 329 static void MBAnalyze(VP8EncIterator* const it,
 330                       int alphas[MAX_ALPHA + 1],
 331                       int* const alpha, int* const uv_alpha) {
 332   const VP8Encoder* const enc = it->enc_;
 333   int best_alpha, best_uv_alpha;
 334
 335   VP8SetIntra16Mode(it, 0);  // default: Intra16, DC_PRED
 336   VP8SetSkip(it, 0);         // not skipped
 337   VP8SetSegment(it, 0);      // default segment, spec-wise.
 338
 339   best_alpha = MBAnalyzeBestIntra16Mode(it);
 340   if (enc->method_ >= 5) {
 341     // We go and make a fast decision for intra4/intra16.
 342     // It's usually not a good and definitive pick, but helps seeding the stats
 343     // about level bit-cost.
 344     // TODO(skal): improve criterion.
 345     best_alpha = MBAnalyzeBestIntra4Mode(it, best_alpha);
 346   }
 347   best_uv_alpha = MBAnalyzeBestUVMode(it);
 348
 349   // Final susceptibility mix
 350   best_alpha = (3 * best_alpha + best_uv_alpha + 2) >> 2;
 351   best_alpha = FinalAlphaValue(best_alpha);
 352   alphas[best_alpha]++;
 353   it->mb_->alpha_ = best_alpha;   // for later remapping.
 354
 355   // Accumulate for later complexity analysis.
 356   *alpha += best_alpha;   // mixed susceptibility (not just luma)
 357   *uv_alpha += best_uv_alpha;
 358 }
 359
 360 static void DefaultMBInfo(VP8MBInfo* const mb) {
 361   mb->type_ = 1;     // I16x16
 362   mb->uv_mode_ = 0;
 363   mb->skip_ = 0;     // not skipped
 364   mb->segment_ = 0;  // default segment
 365   mb->alpha_ = 0;
 366 }
 367
 368 //------------------------------------------------------------------------------
 369 // Main analysis loop:
 370 // Collect all susceptibilities for each macroblock and record their
 371 // distribution in alphas[]. Segments is assigned a-posteriori, based on
 372 // this histogram.
 373 // We also pick an intra16 prediction mode, which shouldn't be considered
 374 // final except for fast-encode settings. We can also pick some intra4 modes
 375 // and decide intra4/intra16, but that's usually almost always a bad choice at
 376 // this stage.
 377
 378 static void ResetAllMBInfo(VP8Encoder* const enc) {
 379   int n;
 380   for (n = 0; n < enc->mb_w_ * enc->mb_h_; ++n) {
 381     DefaultMBInfo(&enc->mb_info_[n]);
 382   }
 383   // Default susceptibilities.
 384   enc->dqm_[0].alpha_ = 0;
 385   enc->dqm_[0].beta_ = 0;
 386   // Note: we can't compute this alpha_ / uv_alpha_ -> set to default value.
 387   enc->alpha_ = 0;
 388   enc->uv_alpha_ = 0;
 389   WebPReportProgress(enc->pic_, enc->percent_ + 20, &enc->percent_);
 390 }
 391
 392 // struct used to collect job result
 393 typedef struct {
 394   WebPWorker worker;
 395   int alphas[MAX_ALPHA + 1];
 396   int alpha, uv_alpha;
 397   VP8EncIterator it;
 398   int delta_progress;
 399 } SegmentJob;
 400
 401 // main work call
 402 static int DoSegmentsJob(SegmentJob* const job, VP8EncIterator* const it) {
 403   int ok = 1;
 404   if (!VP8IteratorIsDone(it)) {
 405     uint8_t tmp[32 + ALIGN_CST];
 406     uint8_t* const scratch = (uint8_t*)DO_ALIGN(tmp);
 407     do {
 408       // Let's pretend we have perfect lossless reconstruction.
 409       VP8IteratorImport(it, scratch);
 410       MBAnalyze(it, job->alphas, &job->alpha, &job->uv_alpha);
 411       ok = VP8IteratorProgress(it, job->delta_progress);
 412     } while (ok && VP8IteratorNext(it));
 413   }
 414   return ok;
 415 }
 416
 417 static void MergeJobs(const SegmentJob* const src, SegmentJob* const dst) {
 418   int i;
 419   for (i = 0; i <= MAX_ALPHA; ++i) dst->alphas[i] += src->alphas[i];
 420   dst->alpha += src->alpha;
 421   dst->uv_alpha += src->uv_alpha;
 422 }
 423
 424 // initialize the job struct with some TODOs
 425 static void InitSegmentJob(VP8Encoder* const enc, SegmentJob* const job,
 426                            int start_row, int end_row) {
 427   WebPGetWorkerInterface()->Init(&job->worker);
 428   job->worker.data1 = job;
 429   job->worker.data2 = &job->it;
 430   job->worker.hook = (WebPWorkerHook)DoSegmentsJob;
 431   VP8IteratorInit(enc, &job->it);
 432   VP8IteratorSetRow(&job->it, start_row);
 433   VP8IteratorSetCountDown(&job->it, (end_row - start_row) * enc->mb_w_);
 434   memset(job->alphas, 0, sizeof(job->alphas));
 435   job->alpha = 0;
 436   job->uv_alpha = 0;
 437   // only one of both jobs can record the progress, since we don't
 438   // expect the user's hook to be multi-thread safe
 439   job->delta_progress = (start_row == 0) ? 20 : 0;
 440 }
 441
 442 // main entry point
 443 int VP8EncAnalyze(VP8Encoder* const enc) {
 444   int ok = 1;
 445   const int do_segments =
 446       enc->config_->emulate_jpeg_size ||   // We need the complexity evaluation.
 447       (enc->segment_hdr_.num_segments_ > 1) ||
 448       (enc->method_ == 0);  // for method 0, we need preds_[] to be filled.
 449   if (do_segments) {
 450     const int last_row = enc->mb_h_;
 451     // We give a little more than a half work to the main thread.
 452     const int split_row = (9 * last_row + 15) >> 4;
 453     const int total_mb = last_row * enc->mb_w_;
 454 #ifdef WEBP_USE_THREAD
 455     const int kMinSplitRow = 2;  // minimal rows needed for mt to be worth it
 456     const int do_mt = (enc->thread_level_ > 0) && (split_row >= kMinSplitRow);
 457 #else
 458     const int do_mt = 0;
 459 #endif
 460     const WebPWorkerInterface* const worker_interface =
 461         WebPGetWorkerInterface();
 462     SegmentJob main_job;
 463     if (do_mt) {
 464       SegmentJob side_job;
 465       // Note the use of '&' instead of '&&' because we must call the functions
 466       // no matter what.
 467       InitSegmentJob(enc, &main_job, 0, split_row);
 468       InitSegmentJob(enc, &side_job, split_row, last_row);
 469       // we don't need to call Reset() on main_job.worker, since we're calling
 470       // WebPWorkerExecute() on it
 471       ok &= worker_interface->Reset(&side_job.worker);
 472       // launch the two jobs in parallel
 473       if (ok) {
 474         worker_interface->Launch(&side_job.worker);
 475         worker_interface->Execute(&main_job.worker);
 476         ok &= worker_interface->Sync(&side_job.worker);
 477         ok &= worker_interface->Sync(&main_job.worker);
 478       }
 479       worker_interface->End(&side_job.worker);
 480       if (ok) MergeJobs(&side_job, &main_job);  // merge results together
 481     } else {
 482       // Even for single-thread case, we use the generic Worker tools.
 483       InitSegmentJob(enc, &main_job, 0, last_row);
 484       worker_interface->Execute(&main_job.worker);
 485       ok &= worker_interface->Sync(&main_job.worker);
 486     }
 487     worker_interface->End(&main_job.worker);
 488     if (ok) {
 489       enc->alpha_ = main_job.alpha / total_mb;
 490       enc->uv_alpha_ = main_job.uv_alpha / total_mb;
 491       AssignSegments(enc, main_job.alphas);
 492     }
 493   } else {   // Use only one default segment.
 494     ResetAllMBInfo(enc);
 495   }
 496   return ok;
 497 }
 498