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