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