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 28static 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 72static WEBP_INLINE int clip(int v, int m, int M) { 73 return (v < m) ? m : (v > M) ? M : v; 74} 75 76static 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 108static int FinalAlphaValue(int alpha) { 109 alpha = MAX_ALPHA - alpha; 110 return clip(alpha, 0, MAX_ALPHA); 111} 112 113static 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 131static 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 142static 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 240static 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 264static 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 306static 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 329static 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 360static 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 378static 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 393typedef 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 402static 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 417static 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 425static 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 443int 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 499