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
SmoothSegmentMap(VP8Encoder * const enc)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
clip(int v,int m,int M)75 static WEBP_INLINE int clip(int v, int m, int M) {
76 return (v < m) ? m : (v > M) ? M : v;
77 }
78
SetSegmentAlphas(VP8Encoder * const enc,const int centers[NUM_MB_SEGMENTS],int mid)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
FinalAlphaValue(int alpha)111 static int FinalAlphaValue(int alpha) {
112 alpha = MAX_ALPHA - alpha;
113 return clip(alpha, 0, MAX_ALPHA);
114 }
115
GetAlpha(const VP8Histogram * const histo)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
MergeHistograms(const VP8Histogram * const in,VP8Histogram * const out)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
AssignSegments(VP8Encoder * const enc,const int alphas[MAX_ALPHA+1])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
MBAnalyzeBestIntra16Mode(VP8EncIterator * const it)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
MBAnalyzeBestIntra4Mode(VP8EncIterator * const it,int best_alpha)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
MBAnalyzeBestUVMode(VP8EncIterator * const it)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
MBAnalyze(VP8EncIterator * const it,int alphas[MAX_ALPHA+1],int * const alpha,int * const uv_alpha)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
DefaultMBInfo(VP8MBInfo * const mb)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
ResetAllMBInfo(VP8Encoder * const enc)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
VP8EncAnalyze(VP8Encoder * const enc)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
422