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 | |
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 | |
72 | static WEBP_INLINE int clip(int v, int m, int M) { |
73 | return (v < m) ? m : (v > M) ? M : v; |
74 | } |
75 | |
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 | |
108 | static int FinalAlphaValue(int alpha) { |
109 | alpha = MAX_ALPHA - alpha; |
110 | return clip(alpha, 0, MAX_ALPHA); |
111 | } |
112 | |
113 | static 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 | |
124 | static 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 | |
132 | static 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 | |
230 | static 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 | |
255 | static 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 | |
278 | static 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 | |
307 | static 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 | |
335 | static 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 | |
353 | static 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 |
368 | typedef 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 |
377 | static 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 |
395 | static 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 |
404 | static 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 |
422 | int 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 | |