1 | // Copyright 2016 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 | // Image transform methods for lossless encoder. |
11 | // |
12 | // Authors: Vikas Arora (vikaas.arora@gmail.com) |
13 | // Jyrki Alakuijala (jyrki@google.com) |
14 | // Urvang Joshi (urvang@google.com) |
15 | // Vincent Rabaud (vrabaud@google.com) |
16 | |
17 | #include "src/dsp/lossless.h" |
18 | #include "src/dsp/lossless_common.h" |
19 | #include "src/enc/vp8i_enc.h" |
20 | #include "src/enc/vp8li_enc.h" |
21 | |
22 | #define MAX_DIFF_COST (1e30f) |
23 | |
24 | static const float kSpatialPredictorBias = 15.f; |
25 | static const int kPredLowEffort = 11; |
26 | static const uint32_t kMaskAlpha = 0xff000000; |
27 | |
28 | // Mostly used to reduce code size + readability |
29 | static WEBP_INLINE int GetMin(int a, int b) { return (a > b) ? b : a; } |
30 | |
31 | //------------------------------------------------------------------------------ |
32 | // Methods to calculate Entropy (Shannon). |
33 | |
34 | static float PredictionCostSpatial(const int counts[256], int weight_0, |
35 | float exp_val) { |
36 | const int significant_symbols = 256 >> 4; |
37 | const float exp_decay_factor = 0.6f; |
38 | float bits = (float)weight_0 * counts[0]; |
39 | int i; |
40 | for (i = 1; i < significant_symbols; ++i) { |
41 | bits += exp_val * (counts[i] + counts[256 - i]); |
42 | exp_val *= exp_decay_factor; |
43 | } |
44 | return (float)(-0.1 * bits); |
45 | } |
46 | |
47 | static float PredictionCostSpatialHistogram(const int accumulated[4][256], |
48 | const int tile[4][256]) { |
49 | int i; |
50 | float retval = 0.f; |
51 | for (i = 0; i < 4; ++i) { |
52 | const float kExpValue = 0.94f; |
53 | retval += PredictionCostSpatial(tile[i], 1, kExpValue); |
54 | retval += VP8LCombinedShannonEntropy(tile[i], accumulated[i]); |
55 | } |
56 | return (float)retval; |
57 | } |
58 | |
59 | static WEBP_INLINE void UpdateHisto(int histo_argb[4][256], uint32_t argb) { |
60 | ++histo_argb[0][argb >> 24]; |
61 | ++histo_argb[1][(argb >> 16) & 0xff]; |
62 | ++histo_argb[2][(argb >> 8) & 0xff]; |
63 | ++histo_argb[3][argb & 0xff]; |
64 | } |
65 | |
66 | //------------------------------------------------------------------------------ |
67 | // Spatial transform functions. |
68 | |
69 | static WEBP_INLINE void PredictBatch(int mode, int x_start, int y, |
70 | int num_pixels, const uint32_t* current, |
71 | const uint32_t* upper, uint32_t* out) { |
72 | if (x_start == 0) { |
73 | if (y == 0) { |
74 | // ARGB_BLACK. |
75 | VP8LPredictorsSub[0](current, NULL, 1, out); |
76 | } else { |
77 | // Top one. |
78 | VP8LPredictorsSub[2](current, upper, 1, out); |
79 | } |
80 | ++x_start; |
81 | ++out; |
82 | --num_pixels; |
83 | } |
84 | if (y == 0) { |
85 | // Left one. |
86 | VP8LPredictorsSub[1](current + x_start, NULL, num_pixels, out); |
87 | } else { |
88 | VP8LPredictorsSub[mode](current + x_start, upper + x_start, num_pixels, |
89 | out); |
90 | } |
91 | } |
92 | |
93 | #if (WEBP_NEAR_LOSSLESS == 1) |
94 | static WEBP_INLINE int GetMax(int a, int b) { return (a < b) ? b : a; } |
95 | |
96 | static int MaxDiffBetweenPixels(uint32_t p1, uint32_t p2) { |
97 | const int diff_a = abs((int)(p1 >> 24) - (int)(p2 >> 24)); |
98 | const int diff_r = abs((int)((p1 >> 16) & 0xff) - (int)((p2 >> 16) & 0xff)); |
99 | const int diff_g = abs((int)((p1 >> 8) & 0xff) - (int)((p2 >> 8) & 0xff)); |
100 | const int diff_b = abs((int)(p1 & 0xff) - (int)(p2 & 0xff)); |
101 | return GetMax(GetMax(diff_a, diff_r), GetMax(diff_g, diff_b)); |
102 | } |
103 | |
104 | static int MaxDiffAroundPixel(uint32_t current, uint32_t up, uint32_t down, |
105 | uint32_t left, uint32_t right) { |
106 | const int diff_up = MaxDiffBetweenPixels(current, up); |
107 | const int diff_down = MaxDiffBetweenPixels(current, down); |
108 | const int diff_left = MaxDiffBetweenPixels(current, left); |
109 | const int diff_right = MaxDiffBetweenPixels(current, right); |
110 | return GetMax(GetMax(diff_up, diff_down), GetMax(diff_left, diff_right)); |
111 | } |
112 | |
113 | static uint32_t AddGreenToBlueAndRed(uint32_t argb) { |
114 | const uint32_t green = (argb >> 8) & 0xff; |
115 | uint32_t red_blue = argb & 0x00ff00ffu; |
116 | red_blue += (green << 16) | green; |
117 | red_blue &= 0x00ff00ffu; |
118 | return (argb & 0xff00ff00u) | red_blue; |
119 | } |
120 | |
121 | static void MaxDiffsForRow(int width, int stride, const uint32_t* const argb, |
122 | uint8_t* const max_diffs, int used_subtract_green) { |
123 | uint32_t current, up, down, left, right; |
124 | int x; |
125 | if (width <= 2) return; |
126 | current = argb[0]; |
127 | right = argb[1]; |
128 | if (used_subtract_green) { |
129 | current = AddGreenToBlueAndRed(current); |
130 | right = AddGreenToBlueAndRed(right); |
131 | } |
132 | // max_diffs[0] and max_diffs[width - 1] are never used. |
133 | for (x = 1; x < width - 1; ++x) { |
134 | up = argb[-stride + x]; |
135 | down = argb[stride + x]; |
136 | left = current; |
137 | current = right; |
138 | right = argb[x + 1]; |
139 | if (used_subtract_green) { |
140 | up = AddGreenToBlueAndRed(up); |
141 | down = AddGreenToBlueAndRed(down); |
142 | right = AddGreenToBlueAndRed(right); |
143 | } |
144 | max_diffs[x] = MaxDiffAroundPixel(current, up, down, left, right); |
145 | } |
146 | } |
147 | |
148 | // Quantize the difference between the actual component value and its prediction |
149 | // to a multiple of quantization, working modulo 256, taking care not to cross |
150 | // a boundary (inclusive upper limit). |
151 | static uint8_t NearLosslessComponent(uint8_t value, uint8_t predict, |
152 | uint8_t boundary, int quantization) { |
153 | const int residual = (value - predict) & 0xff; |
154 | const int boundary_residual = (boundary - predict) & 0xff; |
155 | const int lower = residual & ~(quantization - 1); |
156 | const int upper = lower + quantization; |
157 | // Resolve ties towards a value closer to the prediction (i.e. towards lower |
158 | // if value comes after prediction and towards upper otherwise). |
159 | const int bias = ((boundary - value) & 0xff) < boundary_residual; |
160 | if (residual - lower < upper - residual + bias) { |
161 | // lower is closer to residual than upper. |
162 | if (residual > boundary_residual && lower <= boundary_residual) { |
163 | // Halve quantization step to avoid crossing boundary. This midpoint is |
164 | // on the same side of boundary as residual because midpoint >= residual |
165 | // (since lower is closer than upper) and residual is above the boundary. |
166 | return lower + (quantization >> 1); |
167 | } |
168 | return lower; |
169 | } else { |
170 | // upper is closer to residual than lower. |
171 | if (residual <= boundary_residual && upper > boundary_residual) { |
172 | // Halve quantization step to avoid crossing boundary. This midpoint is |
173 | // on the same side of boundary as residual because midpoint <= residual |
174 | // (since upper is closer than lower) and residual is below the boundary. |
175 | return lower + (quantization >> 1); |
176 | } |
177 | return upper & 0xff; |
178 | } |
179 | } |
180 | |
181 | static WEBP_INLINE uint8_t NearLosslessDiff(uint8_t a, uint8_t b) { |
182 | return (uint8_t)((((int)(a) - (int)(b))) & 0xff); |
183 | } |
184 | |
185 | // Quantize every component of the difference between the actual pixel value and |
186 | // its prediction to a multiple of a quantization (a power of 2, not larger than |
187 | // max_quantization which is a power of 2, smaller than max_diff). Take care if |
188 | // value and predict have undergone subtract green, which means that red and |
189 | // blue are represented as offsets from green. |
190 | static uint32_t NearLossless(uint32_t value, uint32_t predict, |
191 | int max_quantization, int max_diff, |
192 | int used_subtract_green) { |
193 | int quantization; |
194 | uint8_t new_green = 0; |
195 | uint8_t green_diff = 0; |
196 | uint8_t a, r, g, b; |
197 | if (max_diff <= 2) { |
198 | return VP8LSubPixels(value, predict); |
199 | } |
200 | quantization = max_quantization; |
201 | while (quantization >= max_diff) { |
202 | quantization >>= 1; |
203 | } |
204 | if ((value >> 24) == 0 || (value >> 24) == 0xff) { |
205 | // Preserve transparency of fully transparent or fully opaque pixels. |
206 | a = NearLosslessDiff((value >> 24) & 0xff, (predict >> 24) & 0xff); |
207 | } else { |
208 | a = NearLosslessComponent(value >> 24, predict >> 24, 0xff, quantization); |
209 | } |
210 | g = NearLosslessComponent((value >> 8) & 0xff, (predict >> 8) & 0xff, 0xff, |
211 | quantization); |
212 | if (used_subtract_green) { |
213 | // The green offset will be added to red and blue components during decoding |
214 | // to obtain the actual red and blue values. |
215 | new_green = ((predict >> 8) + g) & 0xff; |
216 | // The amount by which green has been adjusted during quantization. It is |
217 | // subtracted from red and blue for compensation, to avoid accumulating two |
218 | // quantization errors in them. |
219 | green_diff = NearLosslessDiff(new_green, (value >> 8) & 0xff); |
220 | } |
221 | r = NearLosslessComponent(NearLosslessDiff((value >> 16) & 0xff, green_diff), |
222 | (predict >> 16) & 0xff, 0xff - new_green, |
223 | quantization); |
224 | b = NearLosslessComponent(NearLosslessDiff(value & 0xff, green_diff), |
225 | predict & 0xff, 0xff - new_green, quantization); |
226 | return ((uint32_t)a << 24) | ((uint32_t)r << 16) | ((uint32_t)g << 8) | b; |
227 | } |
228 | #endif // (WEBP_NEAR_LOSSLESS == 1) |
229 | |
230 | // Stores the difference between the pixel and its prediction in "out". |
231 | // In case of a lossy encoding, updates the source image to avoid propagating |
232 | // the deviation further to pixels which depend on the current pixel for their |
233 | // predictions. |
234 | static WEBP_INLINE void GetResidual( |
235 | int width, int height, uint32_t* const upper_row, |
236 | uint32_t* const current_row, const uint8_t* const max_diffs, int mode, |
237 | int x_start, int x_end, int y, int max_quantization, int exact, |
238 | int used_subtract_green, uint32_t* const out) { |
239 | if (exact) { |
240 | PredictBatch(mode, x_start, y, x_end - x_start, current_row, upper_row, |
241 | out); |
242 | } else { |
243 | const VP8LPredictorFunc pred_func = VP8LPredictors[mode]; |
244 | int x; |
245 | for (x = x_start; x < x_end; ++x) { |
246 | uint32_t predict; |
247 | uint32_t residual; |
248 | if (y == 0) { |
249 | predict = (x == 0) ? ARGB_BLACK : current_row[x - 1]; // Left. |
250 | } else if (x == 0) { |
251 | predict = upper_row[x]; // Top. |
252 | } else { |
253 | predict = pred_func(¤t_row[x - 1], upper_row + x); |
254 | } |
255 | #if (WEBP_NEAR_LOSSLESS == 1) |
256 | if (max_quantization == 1 || mode == 0 || y == 0 || y == height - 1 || |
257 | x == 0 || x == width - 1) { |
258 | residual = VP8LSubPixels(current_row[x], predict); |
259 | } else { |
260 | residual = NearLossless(current_row[x], predict, max_quantization, |
261 | max_diffs[x], used_subtract_green); |
262 | // Update the source image. |
263 | current_row[x] = VP8LAddPixels(predict, residual); |
264 | // x is never 0 here so we do not need to update upper_row like below. |
265 | } |
266 | #else |
267 | (void)max_diffs; |
268 | (void)height; |
269 | (void)max_quantization; |
270 | (void)used_subtract_green; |
271 | residual = VP8LSubPixels(current_row[x], predict); |
272 | #endif |
273 | if ((current_row[x] & kMaskAlpha) == 0) { |
274 | // If alpha is 0, cleanup RGB. We can choose the RGB values of the |
275 | // residual for best compression. The prediction of alpha itself can be |
276 | // non-zero and must be kept though. We choose RGB of the residual to be |
277 | // 0. |
278 | residual &= kMaskAlpha; |
279 | // Update the source image. |
280 | current_row[x] = predict & ~kMaskAlpha; |
281 | // The prediction for the rightmost pixel in a row uses the leftmost |
282 | // pixel |
283 | // in that row as its top-right context pixel. Hence if we change the |
284 | // leftmost pixel of current_row, the corresponding change must be |
285 | // applied |
286 | // to upper_row as well where top-right context is being read from. |
287 | if (x == 0 && y != 0) upper_row[width] = current_row[0]; |
288 | } |
289 | out[x - x_start] = residual; |
290 | } |
291 | } |
292 | } |
293 | |
294 | // Returns best predictor and updates the accumulated histogram. |
295 | // If max_quantization > 1, assumes that near lossless processing will be |
296 | // applied, quantizing residuals to multiples of quantization levels up to |
297 | // max_quantization (the actual quantization level depends on smoothness near |
298 | // the given pixel). |
299 | static int GetBestPredictorForTile(int width, int height, |
300 | int tile_x, int tile_y, int bits, |
301 | int accumulated[4][256], |
302 | uint32_t* const argb_scratch, |
303 | const uint32_t* const argb, |
304 | int max_quantization, |
305 | int exact, int used_subtract_green, |
306 | const uint32_t* const modes) { |
307 | const int kNumPredModes = 14; |
308 | const int start_x = tile_x << bits; |
309 | const int start_y = tile_y << bits; |
310 | const int tile_size = 1 << bits; |
311 | const int max_y = GetMin(tile_size, height - start_y); |
312 | const int max_x = GetMin(tile_size, width - start_x); |
313 | // Whether there exist columns just outside the tile. |
314 | const int have_left = (start_x > 0); |
315 | // Position and size of the strip covering the tile and adjacent columns if |
316 | // they exist. |
317 | const int context_start_x = start_x - have_left; |
318 | #if (WEBP_NEAR_LOSSLESS == 1) |
319 | const int context_width = max_x + have_left + (max_x < width - start_x); |
320 | #endif |
321 | const int tiles_per_row = VP8LSubSampleSize(width, bits); |
322 | // Prediction modes of the left and above neighbor tiles. |
323 | const int left_mode = (tile_x > 0) ? |
324 | (modes[tile_y * tiles_per_row + tile_x - 1] >> 8) & 0xff : 0xff; |
325 | const int above_mode = (tile_y > 0) ? |
326 | (modes[(tile_y - 1) * tiles_per_row + tile_x] >> 8) & 0xff : 0xff; |
327 | // The width of upper_row and current_row is one pixel larger than image width |
328 | // to allow the top right pixel to point to the leftmost pixel of the next row |
329 | // when at the right edge. |
330 | uint32_t* upper_row = argb_scratch; |
331 | uint32_t* current_row = upper_row + width + 1; |
332 | uint8_t* const max_diffs = (uint8_t*)(current_row + width + 1); |
333 | float best_diff = MAX_DIFF_COST; |
334 | int best_mode = 0; |
335 | int mode; |
336 | int histo_stack_1[4][256]; |
337 | int histo_stack_2[4][256]; |
338 | // Need pointers to be able to swap arrays. |
339 | int (*histo_argb)[256] = histo_stack_1; |
340 | int (*best_histo)[256] = histo_stack_2; |
341 | int i, j; |
342 | uint32_t residuals[1 << MAX_TRANSFORM_BITS]; |
343 | assert(bits <= MAX_TRANSFORM_BITS); |
344 | assert(max_x <= (1 << MAX_TRANSFORM_BITS)); |
345 | |
346 | for (mode = 0; mode < kNumPredModes; ++mode) { |
347 | float cur_diff; |
348 | int relative_y; |
349 | memset(histo_argb, 0, sizeof(histo_stack_1)); |
350 | if (start_y > 0) { |
351 | // Read the row above the tile which will become the first upper_row. |
352 | // Include a pixel to the left if it exists; include a pixel to the right |
353 | // in all cases (wrapping to the leftmost pixel of the next row if it does |
354 | // not exist). |
355 | memcpy(current_row + context_start_x, |
356 | argb + (start_y - 1) * width + context_start_x, |
357 | sizeof(*argb) * (max_x + have_left + 1)); |
358 | } |
359 | for (relative_y = 0; relative_y < max_y; ++relative_y) { |
360 | const int y = start_y + relative_y; |
361 | int relative_x; |
362 | uint32_t* tmp = upper_row; |
363 | upper_row = current_row; |
364 | current_row = tmp; |
365 | // Read current_row. Include a pixel to the left if it exists; include a |
366 | // pixel to the right in all cases except at the bottom right corner of |
367 | // the image (wrapping to the leftmost pixel of the next row if it does |
368 | // not exist in the current row). |
369 | memcpy(current_row + context_start_x, |
370 | argb + y * width + context_start_x, |
371 | sizeof(*argb) * (max_x + have_left + (y + 1 < height))); |
372 | #if (WEBP_NEAR_LOSSLESS == 1) |
373 | if (max_quantization > 1 && y >= 1 && y + 1 < height) { |
374 | MaxDiffsForRow(context_width, width, argb + y * width + context_start_x, |
375 | max_diffs + context_start_x, used_subtract_green); |
376 | } |
377 | #endif |
378 | |
379 | GetResidual(width, height, upper_row, current_row, max_diffs, mode, |
380 | start_x, start_x + max_x, y, max_quantization, exact, |
381 | used_subtract_green, residuals); |
382 | for (relative_x = 0; relative_x < max_x; ++relative_x) { |
383 | UpdateHisto(histo_argb, residuals[relative_x]); |
384 | } |
385 | } |
386 | cur_diff = PredictionCostSpatialHistogram( |
387 | (const int (*)[256])accumulated, (const int (*)[256])histo_argb); |
388 | // Favor keeping the areas locally similar. |
389 | if (mode == left_mode) cur_diff -= kSpatialPredictorBias; |
390 | if (mode == above_mode) cur_diff -= kSpatialPredictorBias; |
391 | |
392 | if (cur_diff < best_diff) { |
393 | int (*tmp)[256] = histo_argb; |
394 | histo_argb = best_histo; |
395 | best_histo = tmp; |
396 | best_diff = cur_diff; |
397 | best_mode = mode; |
398 | } |
399 | } |
400 | |
401 | for (i = 0; i < 4; i++) { |
402 | for (j = 0; j < 256; j++) { |
403 | accumulated[i][j] += best_histo[i][j]; |
404 | } |
405 | } |
406 | |
407 | return best_mode; |
408 | } |
409 | |
410 | // Converts pixels of the image to residuals with respect to predictions. |
411 | // If max_quantization > 1, applies near lossless processing, quantizing |
412 | // residuals to multiples of quantization levels up to max_quantization |
413 | // (the actual quantization level depends on smoothness near the given pixel). |
414 | static void CopyImageWithPrediction(int width, int height, |
415 | int bits, uint32_t* const modes, |
416 | uint32_t* const argb_scratch, |
417 | uint32_t* const argb, |
418 | int low_effort, int max_quantization, |
419 | int exact, int used_subtract_green) { |
420 | const int tiles_per_row = VP8LSubSampleSize(width, bits); |
421 | // The width of upper_row and current_row is one pixel larger than image width |
422 | // to allow the top right pixel to point to the leftmost pixel of the next row |
423 | // when at the right edge. |
424 | uint32_t* upper_row = argb_scratch; |
425 | uint32_t* current_row = upper_row + width + 1; |
426 | uint8_t* current_max_diffs = (uint8_t*)(current_row + width + 1); |
427 | #if (WEBP_NEAR_LOSSLESS == 1) |
428 | uint8_t* lower_max_diffs = current_max_diffs + width; |
429 | #endif |
430 | int y; |
431 | |
432 | for (y = 0; y < height; ++y) { |
433 | int x; |
434 | uint32_t* const tmp32 = upper_row; |
435 | upper_row = current_row; |
436 | current_row = tmp32; |
437 | memcpy(current_row, argb + y * width, |
438 | sizeof(*argb) * (width + (y + 1 < height))); |
439 | |
440 | if (low_effort) { |
441 | PredictBatch(kPredLowEffort, 0, y, width, current_row, upper_row, |
442 | argb + y * width); |
443 | } else { |
444 | #if (WEBP_NEAR_LOSSLESS == 1) |
445 | if (max_quantization > 1) { |
446 | // Compute max_diffs for the lower row now, because that needs the |
447 | // contents of argb for the current row, which we will overwrite with |
448 | // residuals before proceeding with the next row. |
449 | uint8_t* const tmp8 = current_max_diffs; |
450 | current_max_diffs = lower_max_diffs; |
451 | lower_max_diffs = tmp8; |
452 | if (y + 2 < height) { |
453 | MaxDiffsForRow(width, width, argb + (y + 1) * width, lower_max_diffs, |
454 | used_subtract_green); |
455 | } |
456 | } |
457 | #endif |
458 | for (x = 0; x < width;) { |
459 | const int mode = |
460 | (modes[(y >> bits) * tiles_per_row + (x >> bits)] >> 8) & 0xff; |
461 | int x_end = x + (1 << bits); |
462 | if (x_end > width) x_end = width; |
463 | GetResidual(width, height, upper_row, current_row, current_max_diffs, |
464 | mode, x, x_end, y, max_quantization, exact, |
465 | used_subtract_green, argb + y * width + x); |
466 | x = x_end; |
467 | } |
468 | } |
469 | } |
470 | } |
471 | |
472 | // Finds the best predictor for each tile, and converts the image to residuals |
473 | // with respect to predictions. If near_lossless_quality < 100, applies |
474 | // near lossless processing, shaving off more bits of residuals for lower |
475 | // qualities. |
476 | int VP8LResidualImage(int width, int height, int bits, int low_effort, |
477 | uint32_t* const argb, uint32_t* const argb_scratch, |
478 | uint32_t* const image, int near_lossless_quality, |
479 | int exact, int used_subtract_green, |
480 | const WebPPicture* const pic, int percent_range, |
481 | int* const percent) { |
482 | const int tiles_per_row = VP8LSubSampleSize(width, bits); |
483 | const int tiles_per_col = VP8LSubSampleSize(height, bits); |
484 | int percent_start = *percent; |
485 | int tile_y; |
486 | int histo[4][256]; |
487 | const int max_quantization = 1 << VP8LNearLosslessBits(near_lossless_quality); |
488 | if (low_effort) { |
489 | int i; |
490 | for (i = 0; i < tiles_per_row * tiles_per_col; ++i) { |
491 | image[i] = ARGB_BLACK | (kPredLowEffort << 8); |
492 | } |
493 | } else { |
494 | memset(histo, 0, sizeof(histo)); |
495 | for (tile_y = 0; tile_y < tiles_per_col; ++tile_y) { |
496 | int tile_x; |
497 | for (tile_x = 0; tile_x < tiles_per_row; ++tile_x) { |
498 | const int pred = GetBestPredictorForTile( |
499 | width, height, tile_x, tile_y, bits, histo, argb_scratch, argb, |
500 | max_quantization, exact, used_subtract_green, image); |
501 | image[tile_y * tiles_per_row + tile_x] = ARGB_BLACK | (pred << 8); |
502 | } |
503 | |
504 | if (!WebPReportProgress( |
505 | pic, percent_start + percent_range * tile_y / tiles_per_col, |
506 | percent)) { |
507 | return 0; |
508 | } |
509 | } |
510 | } |
511 | |
512 | CopyImageWithPrediction(width, height, bits, image, argb_scratch, argb, |
513 | low_effort, max_quantization, exact, |
514 | used_subtract_green); |
515 | return WebPReportProgress(pic, percent_start + percent_range, percent); |
516 | } |
517 | |
518 | //------------------------------------------------------------------------------ |
519 | // Color transform functions. |
520 | |
521 | static WEBP_INLINE void MultipliersClear(VP8LMultipliers* const m) { |
522 | m->green_to_red_ = 0; |
523 | m->green_to_blue_ = 0; |
524 | m->red_to_blue_ = 0; |
525 | } |
526 | |
527 | static WEBP_INLINE void ColorCodeToMultipliers(uint32_t color_code, |
528 | VP8LMultipliers* const m) { |
529 | m->green_to_red_ = (color_code >> 0) & 0xff; |
530 | m->green_to_blue_ = (color_code >> 8) & 0xff; |
531 | m->red_to_blue_ = (color_code >> 16) & 0xff; |
532 | } |
533 | |
534 | static WEBP_INLINE uint32_t MultipliersToColorCode( |
535 | const VP8LMultipliers* const m) { |
536 | return 0xff000000u | |
537 | ((uint32_t)(m->red_to_blue_) << 16) | |
538 | ((uint32_t)(m->green_to_blue_) << 8) | |
539 | m->green_to_red_; |
540 | } |
541 | |
542 | static float PredictionCostCrossColor(const int accumulated[256], |
543 | const int counts[256]) { |
544 | // Favor low entropy, locally and globally. |
545 | // Favor small absolute values for PredictionCostSpatial |
546 | static const float kExpValue = 2.4f; |
547 | return VP8LCombinedShannonEntropy(counts, accumulated) + |
548 | PredictionCostSpatial(counts, 3, kExpValue); |
549 | } |
550 | |
551 | static float GetPredictionCostCrossColorRed( |
552 | const uint32_t* argb, int stride, int tile_width, int tile_height, |
553 | VP8LMultipliers prev_x, VP8LMultipliers prev_y, int green_to_red, |
554 | const int accumulated_red_histo[256]) { |
555 | int histo[256] = { 0 }; |
556 | float cur_diff; |
557 | |
558 | VP8LCollectColorRedTransforms(argb, stride, tile_width, tile_height, |
559 | green_to_red, histo); |
560 | |
561 | cur_diff = PredictionCostCrossColor(accumulated_red_histo, histo); |
562 | if ((uint8_t)green_to_red == prev_x.green_to_red_) { |
563 | cur_diff -= 3; // favor keeping the areas locally similar |
564 | } |
565 | if ((uint8_t)green_to_red == prev_y.green_to_red_) { |
566 | cur_diff -= 3; // favor keeping the areas locally similar |
567 | } |
568 | if (green_to_red == 0) { |
569 | cur_diff -= 3; |
570 | } |
571 | return cur_diff; |
572 | } |
573 | |
574 | static void GetBestGreenToRed( |
575 | const uint32_t* argb, int stride, int tile_width, int tile_height, |
576 | VP8LMultipliers prev_x, VP8LMultipliers prev_y, int quality, |
577 | const int accumulated_red_histo[256], VP8LMultipliers* const best_tx) { |
578 | const int kMaxIters = 4 + ((7 * quality) >> 8); // in range [4..6] |
579 | int green_to_red_best = 0; |
580 | int iter, offset; |
581 | float best_diff = GetPredictionCostCrossColorRed( |
582 | argb, stride, tile_width, tile_height, prev_x, prev_y, |
583 | green_to_red_best, accumulated_red_histo); |
584 | for (iter = 0; iter < kMaxIters; ++iter) { |
585 | // ColorTransformDelta is a 3.5 bit fixed point, so 32 is equal to |
586 | // one in color computation. Having initial delta here as 1 is sufficient |
587 | // to explore the range of (-2, 2). |
588 | const int delta = 32 >> iter; |
589 | // Try a negative and a positive delta from the best known value. |
590 | for (offset = -delta; offset <= delta; offset += 2 * delta) { |
591 | const int green_to_red_cur = offset + green_to_red_best; |
592 | const float cur_diff = GetPredictionCostCrossColorRed( |
593 | argb, stride, tile_width, tile_height, prev_x, prev_y, |
594 | green_to_red_cur, accumulated_red_histo); |
595 | if (cur_diff < best_diff) { |
596 | best_diff = cur_diff; |
597 | green_to_red_best = green_to_red_cur; |
598 | } |
599 | } |
600 | } |
601 | best_tx->green_to_red_ = (green_to_red_best & 0xff); |
602 | } |
603 | |
604 | static float GetPredictionCostCrossColorBlue( |
605 | const uint32_t* argb, int stride, int tile_width, int tile_height, |
606 | VP8LMultipliers prev_x, VP8LMultipliers prev_y, |
607 | int green_to_blue, int red_to_blue, const int accumulated_blue_histo[256]) { |
608 | int histo[256] = { 0 }; |
609 | float cur_diff; |
610 | |
611 | VP8LCollectColorBlueTransforms(argb, stride, tile_width, tile_height, |
612 | green_to_blue, red_to_blue, histo); |
613 | |
614 | cur_diff = PredictionCostCrossColor(accumulated_blue_histo, histo); |
615 | if ((uint8_t)green_to_blue == prev_x.green_to_blue_) { |
616 | cur_diff -= 3; // favor keeping the areas locally similar |
617 | } |
618 | if ((uint8_t)green_to_blue == prev_y.green_to_blue_) { |
619 | cur_diff -= 3; // favor keeping the areas locally similar |
620 | } |
621 | if ((uint8_t)red_to_blue == prev_x.red_to_blue_) { |
622 | cur_diff -= 3; // favor keeping the areas locally similar |
623 | } |
624 | if ((uint8_t)red_to_blue == prev_y.red_to_blue_) { |
625 | cur_diff -= 3; // favor keeping the areas locally similar |
626 | } |
627 | if (green_to_blue == 0) { |
628 | cur_diff -= 3; |
629 | } |
630 | if (red_to_blue == 0) { |
631 | cur_diff -= 3; |
632 | } |
633 | return cur_diff; |
634 | } |
635 | |
636 | #define kGreenRedToBlueNumAxis 8 |
637 | #define kGreenRedToBlueMaxIters 7 |
638 | static void GetBestGreenRedToBlue( |
639 | const uint32_t* argb, int stride, int tile_width, int tile_height, |
640 | VP8LMultipliers prev_x, VP8LMultipliers prev_y, int quality, |
641 | const int accumulated_blue_histo[256], |
642 | VP8LMultipliers* const best_tx) { |
643 | const int8_t offset[kGreenRedToBlueNumAxis][2] = |
644 | {{0, -1}, {0, 1}, {-1, 0}, {1, 0}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}}; |
645 | const int8_t delta_lut[kGreenRedToBlueMaxIters] = { 16, 16, 8, 4, 2, 2, 2 }; |
646 | const int iters = |
647 | (quality < 25) ? 1 : (quality > 50) ? kGreenRedToBlueMaxIters : 4; |
648 | int green_to_blue_best = 0; |
649 | int red_to_blue_best = 0; |
650 | int iter; |
651 | // Initial value at origin: |
652 | float best_diff = GetPredictionCostCrossColorBlue( |
653 | argb, stride, tile_width, tile_height, prev_x, prev_y, |
654 | green_to_blue_best, red_to_blue_best, accumulated_blue_histo); |
655 | for (iter = 0; iter < iters; ++iter) { |
656 | const int delta = delta_lut[iter]; |
657 | int axis; |
658 | for (axis = 0; axis < kGreenRedToBlueNumAxis; ++axis) { |
659 | const int green_to_blue_cur = |
660 | offset[axis][0] * delta + green_to_blue_best; |
661 | const int red_to_blue_cur = offset[axis][1] * delta + red_to_blue_best; |
662 | const float cur_diff = GetPredictionCostCrossColorBlue( |
663 | argb, stride, tile_width, tile_height, prev_x, prev_y, |
664 | green_to_blue_cur, red_to_blue_cur, accumulated_blue_histo); |
665 | if (cur_diff < best_diff) { |
666 | best_diff = cur_diff; |
667 | green_to_blue_best = green_to_blue_cur; |
668 | red_to_blue_best = red_to_blue_cur; |
669 | } |
670 | if (quality < 25 && iter == 4) { |
671 | // Only axis aligned diffs for lower quality. |
672 | break; // next iter. |
673 | } |
674 | } |
675 | if (delta == 2 && green_to_blue_best == 0 && red_to_blue_best == 0) { |
676 | // Further iterations would not help. |
677 | break; // out of iter-loop. |
678 | } |
679 | } |
680 | best_tx->green_to_blue_ = green_to_blue_best & 0xff; |
681 | best_tx->red_to_blue_ = red_to_blue_best & 0xff; |
682 | } |
683 | #undef kGreenRedToBlueMaxIters |
684 | #undef kGreenRedToBlueNumAxis |
685 | |
686 | static VP8LMultipliers GetBestColorTransformForTile( |
687 | int tile_x, int tile_y, int bits, |
688 | VP8LMultipliers prev_x, |
689 | VP8LMultipliers prev_y, |
690 | int quality, int xsize, int ysize, |
691 | const int accumulated_red_histo[256], |
692 | const int accumulated_blue_histo[256], |
693 | const uint32_t* const argb) { |
694 | const int max_tile_size = 1 << bits; |
695 | const int tile_y_offset = tile_y * max_tile_size; |
696 | const int tile_x_offset = tile_x * max_tile_size; |
697 | const int all_x_max = GetMin(tile_x_offset + max_tile_size, xsize); |
698 | const int all_y_max = GetMin(tile_y_offset + max_tile_size, ysize); |
699 | const int tile_width = all_x_max - tile_x_offset; |
700 | const int tile_height = all_y_max - tile_y_offset; |
701 | const uint32_t* const tile_argb = argb + tile_y_offset * xsize |
702 | + tile_x_offset; |
703 | VP8LMultipliers best_tx; |
704 | MultipliersClear(&best_tx); |
705 | |
706 | GetBestGreenToRed(tile_argb, xsize, tile_width, tile_height, |
707 | prev_x, prev_y, quality, accumulated_red_histo, &best_tx); |
708 | GetBestGreenRedToBlue(tile_argb, xsize, tile_width, tile_height, |
709 | prev_x, prev_y, quality, accumulated_blue_histo, |
710 | &best_tx); |
711 | return best_tx; |
712 | } |
713 | |
714 | static void CopyTileWithColorTransform(int xsize, int ysize, |
715 | int tile_x, int tile_y, |
716 | int max_tile_size, |
717 | VP8LMultipliers color_transform, |
718 | uint32_t* argb) { |
719 | const int xscan = GetMin(max_tile_size, xsize - tile_x); |
720 | int yscan = GetMin(max_tile_size, ysize - tile_y); |
721 | argb += tile_y * xsize + tile_x; |
722 | while (yscan-- > 0) { |
723 | VP8LTransformColor(&color_transform, argb, xscan); |
724 | argb += xsize; |
725 | } |
726 | } |
727 | |
728 | int VP8LColorSpaceTransform(int width, int height, int bits, int quality, |
729 | uint32_t* const argb, uint32_t* image, |
730 | const WebPPicture* const pic, int percent_range, |
731 | int* const percent) { |
732 | const int max_tile_size = 1 << bits; |
733 | const int tile_xsize = VP8LSubSampleSize(width, bits); |
734 | const int tile_ysize = VP8LSubSampleSize(height, bits); |
735 | int percent_start = *percent; |
736 | int accumulated_red_histo[256] = { 0 }; |
737 | int accumulated_blue_histo[256] = { 0 }; |
738 | int tile_x, tile_y; |
739 | VP8LMultipliers prev_x, prev_y; |
740 | MultipliersClear(&prev_y); |
741 | MultipliersClear(&prev_x); |
742 | for (tile_y = 0; tile_y < tile_ysize; ++tile_y) { |
743 | for (tile_x = 0; tile_x < tile_xsize; ++tile_x) { |
744 | int y; |
745 | const int tile_x_offset = tile_x * max_tile_size; |
746 | const int tile_y_offset = tile_y * max_tile_size; |
747 | const int all_x_max = GetMin(tile_x_offset + max_tile_size, width); |
748 | const int all_y_max = GetMin(tile_y_offset + max_tile_size, height); |
749 | const int offset = tile_y * tile_xsize + tile_x; |
750 | if (tile_y != 0) { |
751 | ColorCodeToMultipliers(image[offset - tile_xsize], &prev_y); |
752 | } |
753 | prev_x = GetBestColorTransformForTile(tile_x, tile_y, bits, |
754 | prev_x, prev_y, |
755 | quality, width, height, |
756 | accumulated_red_histo, |
757 | accumulated_blue_histo, |
758 | argb); |
759 | image[offset] = MultipliersToColorCode(&prev_x); |
760 | CopyTileWithColorTransform(width, height, tile_x_offset, tile_y_offset, |
761 | max_tile_size, prev_x, argb); |
762 | |
763 | // Gather accumulated histogram data. |
764 | for (y = tile_y_offset; y < all_y_max; ++y) { |
765 | int ix = y * width + tile_x_offset; |
766 | const int ix_end = ix + all_x_max - tile_x_offset; |
767 | for (; ix < ix_end; ++ix) { |
768 | const uint32_t pix = argb[ix]; |
769 | if (ix >= 2 && |
770 | pix == argb[ix - 2] && |
771 | pix == argb[ix - 1]) { |
772 | continue; // repeated pixels are handled by backward references |
773 | } |
774 | if (ix >= width + 2 && |
775 | argb[ix - 2] == argb[ix - width - 2] && |
776 | argb[ix - 1] == argb[ix - width - 1] && |
777 | pix == argb[ix - width]) { |
778 | continue; // repeated pixels are handled by backward references |
779 | } |
780 | ++accumulated_red_histo[(pix >> 16) & 0xff]; |
781 | ++accumulated_blue_histo[(pix >> 0) & 0xff]; |
782 | } |
783 | } |
784 | } |
785 | if (!WebPReportProgress( |
786 | pic, percent_start + percent_range * tile_y / tile_ysize, |
787 | percent)) { |
788 | return 0; |
789 | } |
790 | } |
791 | return 1; |
792 | } |
793 | |