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   const int nb = enc->segment_hdr_.num_segments_;
 145   int centers[NUM_MB_SEGMENTS];
 146   int weighted_average = 0;
 147   int map[MAX_ALPHA + 1];
 148   int a, n, k;
 149   int min_a = 0, max_a = MAX_ALPHA, range_a;
 150   // 'int' type is ok for histo, and won't overflow
 151   int accum[NUM_MB_SEGMENTS], dist_accum[NUM_MB_SEGMENTS];
 152
 153   assert(nb >= 1);
 154   assert(nb <= 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 (k = 0, n = 1; k < nb; ++k, n += 2) {
 165     assert(n < 2 * nb);
 166     centers[k] = min_a + (n * range_a) / (2 * nb);
 167   }
 168
 169   for (k = 0; k < MAX_ITERS_K_MEANS; ++k) {     // few iters are enough
 170     int total_weight;
 171     int displaced;
 172     // Reset stats
 173     for (n = 0; n < nb; ++n) {
 174       accum[n] = 0;
 175       dist_accum[n] = 0;
 176     }
 177     // Assign nearest center for each 'a'
 178     n = 0;    // track the nearest center for current 'a'
 179     for (a = min_a; a <= max_a; ++a) {
 180       if (alphas[a]) {
 181         while (n + 1 < nb && abs(a - centers[n + 1]) < abs(a - centers[n])) {
 182           n++;
 183         }
 184         map[a] = n;
 185         // accumulate contribution into best centroid
 186         dist_accum[n] += a * alphas[a];
 187         accum[n] += alphas[a];
 188       }
 189     }
 190     // All point are classified. Move the centroids to the
 191     // center of their respective cloud.
 192     displaced = 0;
 193     weighted_average = 0;
 194     total_weight = 0;
 195     for (n = 0; n < nb; ++n) {
 196       if (accum[n]) {
 197         const int new_center = (dist_accum[n] + accum[n] / 2) / accum[n];
 198         displaced += abs(centers[n] - new_center);
 199         centers[n] = new_center;
 200         weighted_average += new_center * accum[n];
 201         total_weight += accum[n];
 202       }
 203     }
 204     weighted_average = (weighted_average + total_weight / 2) / total_weight;
 205     if (displaced < 5) break;   // no need to keep on looping...
 206   }
 207
 208   // Map each original value to the closest centroid
 209   for (n = 0; n < enc->mb_w_ * enc->mb_h_; ++n) {
 210     VP8MBInfo* const mb = &enc->mb_info_[n];
 211     const int alpha = mb->alpha_;
 212     mb->segment_ = map[alpha];
 213     mb->alpha_ = centers[map[alpha]];  // for the record.
 214   }
 215
 216   if (nb > 1) {
 217     const int smooth = (enc->config_->preprocessing & 1);
 218     if (smooth) SmoothSegmentMap(enc);
 219   }
 220
 221   SetSegmentAlphas(enc, centers, weighted_average);  // pick some alphas.
 222 }
 223
 224 //------------------------------------------------------------------------------
 225 // Macroblock analysis: collect histogram for each mode, deduce the maximal
 226 // susceptibility and set best modes for this macroblock.
 227 // Segment assignment is done later.
 228
 229 // Number of modes to inspect for alpha_ evaluation. We don't need to test all
 230 // the possible modes during the analysis phase: we risk falling into a local
 231 // optimum, or be subject to boundary effect
 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 = MAX_INTRA16_MODE;
 238   int mode;
 239   int best_alpha = DEFAULT_ALPHA;
 240   int best_mode = 0;
 241
 242   VP8MakeLuma16Preds(it);
 243   for (mode = 0; mode < max_mode; ++mode) {
 244     VP8Histogram histo = { { 0 } };
 245     int alpha;
 246
 247     VP8CollectHistogram(it->yuv_in_ + Y_OFF,
 248                         it->yuv_p_ + VP8I16ModeOffsets[mode],
 249                         0, 16, &histo);
 250     alpha = GetAlpha(&histo);
 251     if (IS_BETTER_ALPHA(alpha, best_alpha)) {
 252       best_alpha = alpha;
 253       best_mode = mode;
 254     }
 255   }
 256   VP8SetIntra16Mode(it, best_mode);
 257   return best_alpha;
 258 }
 259
 260 static int MBAnalyzeBestIntra4Mode(VP8EncIterator* const it,
 261                                    int best_alpha) {
 262   uint8_t modes[16];
 263   const int max_mode = MAX_INTRA4_MODE;
 264   int i4_alpha;
 265   VP8Histogram total_histo = { { 0 } };
 266   int cur_histo = 0;
 267
 268   VP8IteratorStartI4(it);
 269   do {
 270     int mode;
 271     int best_mode_alpha = DEFAULT_ALPHA;
 272     VP8Histogram histos[2];
 273     const uint8_t* const src = it->yuv_in_ + Y_OFF + VP8Scan[it->i4_];
 274
 275     VP8MakeIntra4Preds(it);
 276     for (mode = 0; mode < max_mode; ++mode) {
 277       int alpha;
 278
 279       memset(&histos[cur_histo], 0, sizeof(histos[cur_histo]));
 280       VP8CollectHistogram(src, it->yuv_p_ + VP8I4ModeOffsets[mode],
 281                           0, 1, &histos[cur_histo]);
 282       alpha = GetAlpha(&histos[cur_histo]);
 283       if (IS_BETTER_ALPHA(alpha, best_mode_alpha)) {
 284         best_mode_alpha = alpha;
 285         modes[it->i4_] = mode;
 286         cur_histo ^= 1;   // keep track of best histo so far.
 287       }
 288     }
 289     // accumulate best histogram
 290     MergeHistograms(&histos[cur_histo ^ 1], &total_histo);
 291     // Note: we reuse the original samples for predictors
 292   } while (VP8IteratorRotateI4(it, it->yuv_in_ + Y_OFF));
 293
 294   i4_alpha = GetAlpha(&total_histo);
 295   if (IS_BETTER_ALPHA(i4_alpha, best_alpha)) {
 296     VP8SetIntra4Mode(it, modes);
 297     best_alpha = i4_alpha;
 298   }
 299   return best_alpha;
 300 }
 301
 302 static int MBAnalyzeBestUVMode(VP8EncIterator* const it) {
 303   int best_alpha = DEFAULT_ALPHA;
 304   int best_mode = 0;
 305   const int max_mode = MAX_UV_MODE;
 306   int mode;
 307
 308   VP8MakeChroma8Preds(it);
 309   for (mode = 0; mode < max_mode; ++mode) {
 310     VP8Histogram histo = { { 0 } };
 311     int alpha;
 312     VP8CollectHistogram(it->yuv_in_ + U_OFF,
 313                         it->yuv_p_ + VP8UVModeOffsets[mode],
 314                         16, 16 + 4 + 4, &histo);
 315     alpha = GetAlpha(&histo);
 316     if (IS_BETTER_ALPHA(alpha, best_alpha)) {
 317       best_alpha = alpha;
 318       best_mode = mode;
 319     }
 320   }
 321   VP8SetIntraUVMode(it, best_mode);
 322   return best_alpha;
 323 }
 324
 325 static void MBAnalyze(VP8EncIterator* const it,
 326                       int alphas[MAX_ALPHA + 1],
 327                       int* const alpha, int* const uv_alpha) {
 328   const VP8Encoder* const enc = it->enc_;
 329   int best_alpha, best_uv_alpha;
 330
 331   VP8SetIntra16Mode(it, 0);  // default: Intra16, DC_PRED
 332   VP8SetSkip(it, 0);         // not skipped
 333   VP8SetSegment(it, 0);      // default segment, spec-wise.
 334
 335   best_alpha = MBAnalyzeBestIntra16Mode(it);
 336   if (enc->method_ >= 5) {
 337     // We go and make a fast decision for intra4/intra16.
 338     // It's usually not a good and definitive pick, but helps seeding the stats
 339     // about level bit-cost.
 340     // TODO(skal): improve criterion.
 341     best_alpha = MBAnalyzeBestIntra4Mode(it, best_alpha);
 342   }
 343   best_uv_alpha = MBAnalyzeBestUVMode(it);
 344
 345   // Final susceptibility mix
 346   best_alpha = (3 * best_alpha + best_uv_alpha + 2) >> 2;
 347   best_alpha = FinalAlphaValue(best_alpha);
 348   alphas[best_alpha]++;
 349   it->mb_->alpha_ = best_alpha;   // for later remapping.
 350
 351   // Accumulate for later complexity analysis.
 352   *alpha += best_alpha;   // mixed susceptibility (not just luma)
 353   *uv_alpha += best_uv_alpha;
 354 }
 355
 356 static void DefaultMBInfo(VP8MBInfo* const mb) {
 357   mb->type_ = 1;     // I16x16
 358   mb->uv_mode_ = 0;
 359   mb->skip_ = 0;     // not skipped
 360   mb->segment_ = 0;  // default segment
 361   mb->alpha_ = 0;
 362 }
 363
 364 //------------------------------------------------------------------------------
 365 // Main analysis loop:
 366 // Collect all susceptibilities for each macroblock and record their
 367 // distribution in alphas[]. Segments is assigned a-posteriori, based on
 368 // this histogram.
 369 // We also pick an intra16 prediction mode, which shouldn't be considered
 370 // final except for fast-encode settings. We can also pick some intra4 modes
 371 // and decide intra4/intra16, but that's usually almost always a bad choice at
 372 // this stage.
 373
 374 static void ResetAllMBInfo(VP8Encoder* const enc) {
 375   int n;
 376   for (n = 0; n < enc->mb_w_ * enc->mb_h_; ++n) {
 377     DefaultMBInfo(&enc->mb_info_[n]);
 378   }
 379   // Default susceptibilities.
 380   enc->dqm_[0].alpha_ = 0;
 381   enc->dqm_[0].beta_ = 0;
 382   // Note: we can't compute this alpha_ / uv_alpha_ -> set to default value.
 383   enc->alpha_ = 0;
 384   enc->uv_alpha_ = 0;
 385   WebPReportProgress(enc->pic_, enc->percent_ + 20, &enc->percent_);
 386 }
 387
 388 // struct used to collect job result
 389 typedef struct {
 390   WebPWorker worker;
 391   int alphas[MAX_ALPHA + 1];
 392   int alpha, uv_alpha;
 393   VP8EncIterator it;
 394   int delta_progress;
 395 } SegmentJob;
 396
 397 // main work call
 398 static int DoSegmentsJob(SegmentJob* const job, VP8EncIterator* const it) {
 399   int ok = 1;
 400   if (!VP8IteratorIsDone(it)) {
 401     uint8_t tmp[32 + ALIGN_CST];
 402     uint8_t* const scratch = (uint8_t*)DO_ALIGN(tmp);
 403     do {
 404       // Let's pretend we have perfect lossless reconstruction.
 405       VP8IteratorImport(it, scratch);
 406       MBAnalyze(it, job->alphas, &job->alpha, &job->uv_alpha);
 407       ok = VP8IteratorProgress(it, job->delta_progress);
 408     } while (ok && VP8IteratorNext(it));
 409   }
 410   return ok;
 411 }
 412
 413 static void MergeJobs(const SegmentJob* const src, SegmentJob* const dst) {
 414   int i;
 415   for (i = 0; i <= MAX_ALPHA; ++i) dst->alphas[i] += src->alphas[i];
 416   dst->alpha += src->alpha;
 417   dst->uv_alpha += src->uv_alpha;
 418 }
 419
 420 // initialize the job struct with some TODOs
 421 static void InitSegmentJob(VP8Encoder* const enc, SegmentJob* const job,
 422                            int start_row, int end_row) {
 423   WebPGetWorkerInterface()->Init(&job->worker);
 424   job->worker.data1 = job;
 425   job->worker.data2 = &job->it;
 426   job->worker.hook = (WebPWorkerHook)DoSegmentsJob;
 427   VP8IteratorInit(enc, &job->it);
 428   VP8IteratorSetRow(&job->it, start_row);
 429   VP8IteratorSetCountDown(&job->it, (end_row - start_row) * enc->mb_w_);
 430   memset(job->alphas, 0, sizeof(job->alphas));
 431   job->alpha = 0;
 432   job->uv_alpha = 0;
 433   // only one of both jobs can record the progress, since we don't
 434   // expect the user's hook to be multi-thread safe
 435   job->delta_progress = (start_row == 0) ? 20 : 0;
 436 }
 437
 438 // main entry point
 439 int VP8EncAnalyze(VP8Encoder* const enc) {
 440   int ok = 1;
 441   const int do_segments =
 442       enc->config_->emulate_jpeg_size ||   // We need the complexity evaluation.
 443       (enc->segment_hdr_.num_segments_ > 1) ||
 444       (enc->method_ == 0);  // for method 0, we need preds_[] to be filled.
 445   if (do_segments) {
 446     const int last_row = enc->mb_h_;
 447     // We give a little more than a half work to the main thread.
 448     const int split_row = (9 * last_row + 15) >> 4;
 449     const int total_mb = last_row * enc->mb_w_;
 450 #ifdef WEBP_USE_THREAD
 451     const int kMinSplitRow = 2;  // minimal rows needed for mt to be worth it
 452     const int do_mt = (enc->thread_level_ > 0) && (split_row >= kMinSplitRow);
 453 #else
 454     const int do_mt = 0;
 455 #endif
 456     const WebPWorkerInterface* const worker_interface =
 457         WebPGetWorkerInterface();
 458     SegmentJob main_job;
 459     if (do_mt) {
 460       SegmentJob side_job;
 461       // Note the use of '&' instead of '&&' because we must call the functions
 462       // no matter what.
 463       InitSegmentJob(enc, &main_job, 0, split_row);
 464       InitSegmentJob(enc, &side_job, split_row, last_row);
 465       // we don't need to call Reset() on main_job.worker, since we're calling
 466       // WebPWorkerExecute() on it
 467       ok &= worker_interface->Reset(&side_job.worker);
 468       // launch the two jobs in parallel
 469       if (ok) {
 470         worker_interface->Launch(&side_job.worker);
 471         worker_interface->Execute(&main_job.worker);
 472         ok &= worker_interface->Sync(&side_job.worker);
 473         ok &= worker_interface->Sync(&main_job.worker);
 474       }
 475       worker_interface->End(&side_job.worker);
 476       if (ok) MergeJobs(&side_job, &main_job);  // merge results together
 477     } else {
 478       // Even for single-thread case, we use the generic Worker tools.
 479       InitSegmentJob(enc, &main_job, 0, last_row);
 480       worker_interface->Execute(&main_job.worker);
 481       ok &= worker_interface->Sync(&main_job.worker);
 482     }
 483     worker_interface->End(&main_job.worker);
 484     if (ok) {
 485       enc->alpha_ = main_job.alpha / total_mb;
 486       enc->uv_alpha_ = main_job.uv_alpha / total_mb;
 487       AssignSegments(enc, main_job.alphas);
 488     }
 489   } else {   // Use only one default segment.
 490     ResetAllMBInfo(enc);
 491   }
 492   return ok;
 493 }
 494