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 "src/enc/vp8i_enc.h"
19#include "src/enc/cost_enc.h"
20#include "src/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 // 'alpha' will later be clipped to [0..MAX_ALPHA] range, clamping outer
115 // values which happen to be mostly noise. This leaves the maximum precision
116 // for handling the useful small values which contribute most.
117 const int max_value = histo->max_value;
118 const int last_non_zero = histo->last_non_zero;
119 const int alpha =
120 (max_value > 1) ? ALPHA_SCALE * last_non_zero / max_value : 0;
121 return alpha;
122}
123
124static void InitHistogram(VP8Histogram* const histo) {
125 histo->max_value = 0;
126 histo->last_non_zero = 1;
127}
128
129//------------------------------------------------------------------------------
130// Simplified k-Means, to assign Nb segments based on alpha-histogram
131
132static void AssignSegments(VP8Encoder* const enc,
133 const int alphas[MAX_ALPHA + 1]) {
134 // 'num_segments_' is previously validated and <= NUM_MB_SEGMENTS, but an
135 // explicit check is needed to avoid spurious warning about 'n + 1' exceeding
136 // array bounds of 'centers' with some compilers (noticed with gcc-4.9).
137 const int nb = (enc->segment_hdr_.num_segments_ < NUM_MB_SEGMENTS) ?
138 enc->segment_hdr_.num_segments_ : NUM_MB_SEGMENTS;
139 int centers[NUM_MB_SEGMENTS];
140 int weighted_average = 0;
141 int map[MAX_ALPHA + 1];
142 int a, n, k;
143 int min_a = 0, max_a = MAX_ALPHA, range_a;
144 // 'int' type is ok for histo, and won't overflow
145 int accum[NUM_MB_SEGMENTS], dist_accum[NUM_MB_SEGMENTS];
146
147 assert(nb >= 1);
148 assert(nb <= NUM_MB_SEGMENTS);
149
150 // bracket the input
151 for (n = 0; n <= MAX_ALPHA && alphas[n] == 0; ++n) {}
152 min_a = n;
153 for (n = MAX_ALPHA; n > min_a && alphas[n] == 0; --n) {}
154 max_a = n;
155 range_a = max_a - min_a;
156
157 // Spread initial centers evenly
158 for (k = 0, n = 1; k < nb; ++k, n += 2) {
159 assert(n < 2 * nb);
160 centers[k] = min_a + (n * range_a) / (2 * nb);
161 }
162
163 for (k = 0; k < MAX_ITERS_K_MEANS; ++k) { // few iters are enough
164 int total_weight;
165 int displaced;
166 // Reset stats
167 for (n = 0; n < nb; ++n) {
168 accum[n] = 0;
169 dist_accum[n] = 0;
170 }
171 // Assign nearest center for each 'a'
172 n = 0; // track the nearest center for current 'a'
173 for (a = min_a; a <= max_a; ++a) {
174 if (alphas[a]) {
175 while (n + 1 < nb && abs(a - centers[n + 1]) < abs(a - centers[n])) {
176 n++;
177 }
178 map[a] = n;
179 // accumulate contribution into best centroid
180 dist_accum[n] += a * alphas[a];
181 accum[n] += alphas[a];
182 }
183 }
184 // All point are classified. Move the centroids to the
185 // center of their respective cloud.
186 displaced = 0;
187 weighted_average = 0;
188 total_weight = 0;
189 for (n = 0; n < nb; ++n) {
190 if (accum[n]) {
191 const int new_center = (dist_accum[n] + accum[n] / 2) / accum[n];
192 displaced += abs(centers[n] - new_center);
193 centers[n] = new_center;
194 weighted_average += new_center * accum[n];
195 total_weight += accum[n];
196 }
197 }
198 weighted_average = (weighted_average + total_weight / 2) / total_weight;
199 if (displaced < 5) break; // no need to keep on looping...
200 }
201
202 // Map each original value to the closest centroid
203 for (n = 0; n < enc->mb_w_ * enc->mb_h_; ++n) {
204 VP8MBInfo* const mb = &enc->mb_info_[n];
205 const int alpha = mb->alpha_;
206 mb->segment_ = map[alpha];
207 mb->alpha_ = centers[map[alpha]]; // for the record.
208 }
209
210 if (nb > 1) {
211 const int smooth = (enc->config_->preprocessing & 1);
212 if (smooth) SmoothSegmentMap(enc);
213 }
214
215 SetSegmentAlphas(enc, centers, weighted_average); // pick some alphas.
216}
217
218//------------------------------------------------------------------------------
219// Macroblock analysis: collect histogram for each mode, deduce the maximal
220// susceptibility and set best modes for this macroblock.
221// Segment assignment is done later.
222
223// Number of modes to inspect for alpha_ evaluation. We don't need to test all
224// the possible modes during the analysis phase: we risk falling into a local
225// optimum, or be subject to boundary effect
226#define MAX_INTRA16_MODE 2
227#define MAX_INTRA4_MODE 2
228#define MAX_UV_MODE 2
229
230static int MBAnalyzeBestIntra16Mode(VP8EncIterator* const it) {
231 const int max_mode = MAX_INTRA16_MODE;
232 int mode;
233 int best_alpha = DEFAULT_ALPHA;
234 int best_mode = 0;
235
236 VP8MakeLuma16Preds(it);
237 for (mode = 0; mode < max_mode; ++mode) {
238 VP8Histogram histo;
239 int alpha;
240
241 InitHistogram(&histo);
242 VP8CollectHistogram(it->yuv_in_ + Y_OFF_ENC,
243 it->yuv_p_ + VP8I16ModeOffsets[mode],
244 0, 16, &histo);
245 alpha = GetAlpha(&histo);
246 if (IS_BETTER_ALPHA(alpha, best_alpha)) {
247 best_alpha = alpha;
248 best_mode = mode;
249 }
250 }
251 VP8SetIntra16Mode(it, best_mode);
252 return best_alpha;
253}
254
255static int FastMBAnalyze(VP8EncIterator* const it) {
256 // Empirical cut-off value, should be around 16 (~=block size). We use the
257 // [8-17] range and favor intra4 at high quality, intra16 for low quality.
258 const int q = (int)it->enc_->config_->quality;
259 const uint32_t kThreshold = 8 + (17 - 8) * q / 100;
260 int k;
261 uint32_t dc[16], m, m2;
262 for (k = 0; k < 16; k += 4) {
263 VP8Mean16x4(it->yuv_in_ + Y_OFF_ENC + k * BPS, &dc[k]);
264 }
265 for (m = 0, m2 = 0, k = 0; k < 16; ++k) {
266 m += dc[k];
267 m2 += dc[k] * dc[k];
268 }
269 if (kThreshold * m2 < m * m) {
270 VP8SetIntra16Mode(it, 0); // DC16
271 } else {
272 const uint8_t modes[16] = { 0 }; // DC4
273 VP8SetIntra4Mode(it, modes);
274 }
275 return 0;
276}
277
278static int MBAnalyzeBestUVMode(VP8EncIterator* const it) {
279 int best_alpha = DEFAULT_ALPHA;
280 int smallest_alpha = 0;
281 int best_mode = 0;
282 const int max_mode = MAX_UV_MODE;
283 int mode;
284
285 VP8MakeChroma8Preds(it);
286 for (mode = 0; mode < max_mode; ++mode) {
287 VP8Histogram histo;
288 int alpha;
289 InitHistogram(&histo);
290 VP8CollectHistogram(it->yuv_in_ + U_OFF_ENC,
291 it->yuv_p_ + VP8UVModeOffsets[mode],
292 16, 16 + 4 + 4, &histo);
293 alpha = GetAlpha(&histo);
294 if (IS_BETTER_ALPHA(alpha, best_alpha)) {
295 best_alpha = alpha;
296 }
297 // The best prediction mode tends to be the one with the smallest alpha.
298 if (mode == 0 || alpha < smallest_alpha) {
299 smallest_alpha = alpha;
300 best_mode = mode;
301 }
302 }
303 VP8SetIntraUVMode(it, best_mode);
304 return best_alpha;
305}
306
307static void MBAnalyze(VP8EncIterator* const it,
308 int alphas[MAX_ALPHA + 1],
309 int* const alpha, int* const uv_alpha) {
310 const VP8Encoder* const enc = it->enc_;
311 int best_alpha, best_uv_alpha;
312
313 VP8SetIntra16Mode(it, 0); // default: Intra16, DC_PRED
314 VP8SetSkip(it, 0); // not skipped
315 VP8SetSegment(it, 0); // default segment, spec-wise.
316
317 if (enc->method_ <= 1) {
318 best_alpha = FastMBAnalyze(it);
319 } else {
320 best_alpha = MBAnalyzeBestIntra16Mode(it);
321 }
322 best_uv_alpha = MBAnalyzeBestUVMode(it);
323
324 // Final susceptibility mix
325 best_alpha = (3 * best_alpha + best_uv_alpha + 2) >> 2;
326 best_alpha = FinalAlphaValue(best_alpha);
327 alphas[best_alpha]++;
328 it->mb_->alpha_ = best_alpha; // for later remapping.
329
330 // Accumulate for later complexity analysis.
331 *alpha += best_alpha; // mixed susceptibility (not just luma)
332 *uv_alpha += best_uv_alpha;
333}
334
335static void DefaultMBInfo(VP8MBInfo* const mb) {
336 mb->type_ = 1; // I16x16
337 mb->uv_mode_ = 0;
338 mb->skip_ = 0; // not skipped
339 mb->segment_ = 0; // default segment
340 mb->alpha_ = 0;
341}
342
343//------------------------------------------------------------------------------
344// Main analysis loop:
345// Collect all susceptibilities for each macroblock and record their
346// distribution in alphas[]. Segments is assigned a-posteriori, based on
347// this histogram.
348// We also pick an intra16 prediction mode, which shouldn't be considered
349// final except for fast-encode settings. We can also pick some intra4 modes
350// and decide intra4/intra16, but that's usually almost always a bad choice at
351// this stage.
352
353static void ResetAllMBInfo(VP8Encoder* const enc) {
354 int n;
355 for (n = 0; n < enc->mb_w_ * enc->mb_h_; ++n) {
356 DefaultMBInfo(&enc->mb_info_[n]);
357 }
358 // Default susceptibilities.
359 enc->dqm_[0].alpha_ = 0;
360 enc->dqm_[0].beta_ = 0;
361 // Note: we can't compute this alpha_ / uv_alpha_ -> set to default value.
362 enc->alpha_ = 0;
363 enc->uv_alpha_ = 0;
364 WebPReportProgress(enc->pic_, enc->percent_ + 20, &enc->percent_);
365}
366
367// struct used to collect job result
368typedef struct {
369 WebPWorker worker;
370 int alphas[MAX_ALPHA + 1];
371 int alpha, uv_alpha;
372 VP8EncIterator it;
373 int delta_progress;
374} SegmentJob;
375
376// main work call
377static int DoSegmentsJob(void* arg1, void* arg2) {
378 SegmentJob* const job = (SegmentJob*)arg1;
379 VP8EncIterator* const it = (VP8EncIterator*)arg2;
380 int ok = 1;
381 if (!VP8IteratorIsDone(it)) {
382 uint8_t tmp[32 + WEBP_ALIGN_CST];
383 uint8_t* const scratch = (uint8_t*)WEBP_ALIGN(tmp);
384 do {
385 // Let's pretend we have perfect lossless reconstruction.
386 VP8IteratorImport(it, scratch);
387 MBAnalyze(it, job->alphas, &job->alpha, &job->uv_alpha);
388 ok = VP8IteratorProgress(it, job->delta_progress);
389 } while (ok && VP8IteratorNext(it));
390 }
391 return ok;
392}
393
394#ifdef WEBP_USE_THREAD
395static void MergeJobs(const SegmentJob* const src, SegmentJob* const dst) {
396 int i;
397 for (i = 0; i <= MAX_ALPHA; ++i) dst->alphas[i] += src->alphas[i];
398 dst->alpha += src->alpha;
399 dst->uv_alpha += src->uv_alpha;
400}
401#endif
402
403// initialize the job struct with some tasks to perform
404static void InitSegmentJob(VP8Encoder* const enc, SegmentJob* const job,
405 int start_row, int end_row) {
406 WebPGetWorkerInterface()->Init(&job->worker);
407 job->worker.data1 = job;
408 job->worker.data2 = &job->it;
409 job->worker.hook = DoSegmentsJob;
410 VP8IteratorInit(enc, &job->it);
411 VP8IteratorSetRow(&job->it, start_row);
412 VP8IteratorSetCountDown(&job->it, (end_row - start_row) * enc->mb_w_);
413 memset(job->alphas, 0, sizeof(job->alphas));
414 job->alpha = 0;
415 job->uv_alpha = 0;
416 // only one of both jobs can record the progress, since we don't
417 // expect the user's hook to be multi-thread safe
418 job->delta_progress = (start_row == 0) ? 20 : 0;
419}
420
421// main entry point
422int VP8EncAnalyze(VP8Encoder* const enc) {
423 int ok = 1;
424 const int do_segments =
425 enc->config_->emulate_jpeg_size || // We need the complexity evaluation.
426 (enc->segment_hdr_.num_segments_ > 1) ||
427 (enc->method_ <= 1); // for method 0 - 1, we need preds_[] to be filled.
428 if (do_segments) {
429 const int last_row = enc->mb_h_;
430 const int total_mb = last_row * enc->mb_w_;
431#ifdef WEBP_USE_THREAD
432 // We give a little more than a half work to the main thread.
433 const int split_row = (9 * last_row + 15) >> 4;
434 const int kMinSplitRow = 2; // minimal rows needed for mt to be worth it
435 const int do_mt = (enc->thread_level_ > 0) && (split_row >= kMinSplitRow);
436#else
437 const int do_mt = 0;
438#endif
439 const WebPWorkerInterface* const worker_interface =
440 WebPGetWorkerInterface();
441 SegmentJob main_job;
442 if (do_mt) {
443#ifdef WEBP_USE_THREAD
444 SegmentJob side_job;
445 // Note the use of '&' instead of '&&' because we must call the functions
446 // no matter what.
447 InitSegmentJob(enc, &main_job, 0, split_row);
448 InitSegmentJob(enc, &side_job, split_row, last_row);
449 // we don't need to call Reset() on main_job.worker, since we're calling
450 // WebPWorkerExecute() on it
451 ok &= worker_interface->Reset(&side_job.worker);
452 // launch the two jobs in parallel
453 if (ok) {
454 worker_interface->Launch(&side_job.worker);
455 worker_interface->Execute(&main_job.worker);
456 ok &= worker_interface->Sync(&side_job.worker);
457 ok &= worker_interface->Sync(&main_job.worker);
458 }
459 worker_interface->End(&side_job.worker);
460 if (ok) MergeJobs(&side_job, &main_job); // merge results together
461#endif // WEBP_USE_THREAD
462 } else {
463 // Even for single-thread case, we use the generic Worker tools.
464 InitSegmentJob(enc, &main_job, 0, last_row);
465 worker_interface->Execute(&main_job.worker);
466 ok &= worker_interface->Sync(&main_job.worker);
467 }
468 worker_interface->End(&main_job.worker);
469 if (ok) {
470 enc->alpha_ = main_job.alpha / total_mb;
471 enc->uv_alpha_ = main_job.uv_alpha / total_mb;
472 AssignSegments(enc, main_job.alphas);
473 }
474 } else { // Use only one default segment.
475 ResetAllMBInfo(enc);
476 }
477 if (!ok) {
478 return WebPEncodingSetError(enc->pic_,
479 VP8_ENC_ERROR_OUT_OF_MEMORY); // imprecise
480 }
481 return ok;
482}
483
484