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
SmoothSegmentMap(VP8Encoder * const enc)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
clip(int v,int m,int M)72 static WEBP_INLINE int clip(int v, int m, int M) {
73 return (v < m) ? m : (v > M) ? M : v;
74 }
75
SetSegmentAlphas(VP8Encoder * const enc,const int centers[NUM_MB_SEGMENTS],int mid)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
FinalAlphaValue(int alpha)108 static int FinalAlphaValue(int alpha) {
109 alpha = MAX_ALPHA - alpha;
110 return clip(alpha, 0, MAX_ALPHA);
111 }
112
GetAlpha(const VP8Histogram * const histo)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
MergeHistograms(const VP8Histogram * const in,VP8Histogram * const out)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
AssignSegments(VP8Encoder * const enc,const int alphas[MAX_ALPHA+1])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
MBAnalyzeBestIntra16Mode(VP8EncIterator * const it)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
MBAnalyzeBestIntra4Mode(VP8EncIterator * const it,int best_alpha)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
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 = 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
MBAnalyze(VP8EncIterator * const it,int alphas[MAX_ALPHA+1],int * const alpha,int * const uv_alpha)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
DefaultMBInfo(VP8MBInfo * const mb)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
ResetAllMBInfo(VP8Encoder * const enc)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
DoSegmentsJob(SegmentJob * const job,VP8EncIterator * const it)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
MergeJobs(const SegmentJob * const src,SegmentJob * const dst)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
InitSegmentJob(VP8Encoder * const enc,SegmentJob * const job,int start_row,int end_row)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
VP8EncAnalyze(VP8Encoder * const enc)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
499