Debian Codegraph @

lib/jxl/modular/transform/enc_palette.cc

raw
1 // Copyright (c) the JPEG XL Project Authors. All rights reserved.
2 //
3 // Use of this source code is governed by a BSD-style
4 // license that can be found in the LICENSE file.
5
6 #include "lib/jxl/modular/transform/enc_palette.h"
7
8 #include <jxl/memory_manager.h>
9
10 #include <array>
11 #include <map>
12 #include <set>
13
14 #include "lib/jxl/base/common.h"
15 #include "lib/jxl/base/status.h"
16 #include "lib/jxl/image_ops.h"
17 #include "lib/jxl/modular/encoding/context_predict.h"
18 #include "lib/jxl/modular/modular_image.h"
19 #include "lib/jxl/modular/transform/enc_transform.h"
20 #include "lib/jxl/modular/transform/palette.h"
21
22 namespace jxl {
23
24 namespace palette_internal {
25
26 static constexpr bool kEncodeToHighQualityImplicitPalette = true;
27
28 // Inclusive.
29 static constexpr int kMinImplicitPaletteIndex = -(2 * 72 - 1);
30
31 float ColorDistance(const std::vector<float> &JXL_RESTRICT a,
32 const std::vector<pixel_type> &JXL_RESTRICT b) {
33 JXL_DASSERT(a.size() == b.size());
34 float distance = 0;
35 float ave3 = 0;
36 if (a.size() >= 3) {
37 ave3 = (a[0] + b[0] + a[1] + b[1] + a[2] + b[2]) * (1.21f / 3.0f);
38 }
39 float sum_a = 0;
40 float sum_b = 0;
41 for (size_t c = 0; c < a.size(); ++c) {
42 const float difference =
43 static_cast<float>(a[c]) - static_cast<float>(b[c]);
44 float weight = c == 0 ? 3 : c == 1 ? 5 : 2;
45 if (c < 3 && (a[c] + b[c] >= ave3)) {
46 const float add_w[3] = {
47 1.15,
48 1.15,
49 1.12,
50 };
51 weight += add_w[c];
52 if (c == 2 && ((a[2] + b[2]) < 1.22 * ave3)) {
53 weight -= 0.5;
54 }
55 }
56 distance += difference * difference * weight * weight;
57 const int sum_weight = c == 0 ? 3 : c == 1 ? 5 : 1;
58 sum_a += a[c] * sum_weight;
59 sum_b += b[c] * sum_weight;
60 }
61 distance *= 4;
62 float sum_difference = sum_a - sum_b;
63 distance += sum_difference * sum_difference;
64 return distance;
65 }
66
67 static int QuantizeColorToImplicitPaletteIndex(
68 const std::vector<pixel_type> &color, const int palette_size,
69 const int bit_depth, bool high_quality) {
70 int index = 0;
71 if (high_quality) {
72 int multiplier = 1;
73 for (int value : color) {
74 int quantized = ((kLargeCube - 1) * value + (1 << (bit_depth - 1))) /
75 ((1 << bit_depth) - 1);
76 JXL_DASSERT((quantized % kLargeCube) == quantized);
77 index += quantized * multiplier;
78 multiplier *= kLargeCube;
79 }
80 return index + palette_size + kLargeCubeOffset;
81 } else {
82 int multiplier = 1;
83 for (int value : color) {
84 value -= 1 << (std::max(0, bit_depth - 3));
85 value = std::max(0, value);
86 int quantized = ((kLargeCube - 1) * value + (1 << (bit_depth - 1))) /
87 ((1 << bit_depth) - 1);
88 JXL_DASSERT((quantized % kLargeCube) == quantized);
89 if (quantized > kSmallCube - 1) {
90 quantized = kSmallCube - 1;
91 }
92 index += quantized * multiplier;
93 multiplier *= kSmallCube;
94 }
95 return index + palette_size;
96 }
97 }
98
99 } // namespace palette_internal
100
101 int RoundInt(int value, int div) { // symmetric rounding around 0
102 if (value < 0) return -RoundInt(-value, div);
103 return (value + div / 2) / div;
104 }
105
106 struct PaletteIterationData {
107 static constexpr int kMaxDeltas = 128;
108 bool final_run = false;
109 std::vector<pixel_type> deltas[3];
110 std::vector<double> delta_distances;
111 std::vector<pixel_type> frequent_deltas[3];
112
113 // Populates `frequent_deltas` with items from `deltas` based on frequencies
114 // and color distances.
115 void FindFrequentColorDeltas(int num_pixels, int bitdepth) {
116 using pixel_type_3d = std::array<pixel_type, 3>;
117 std::map<pixel_type_3d, double> delta_frequency_map;
118 pixel_type bucket_size = 3 << std::max(0, bitdepth - 8);
119 // Store frequency weighted by delta distance from quantized value.
120 for (size_t i = 0; i < deltas[0].size(); ++i) {
121 pixel_type_3d delta = {
122 {RoundInt(deltas[0][i], bucket_size),
123 RoundInt(deltas[1][i], bucket_size),
124 RoundInt(deltas[2][i], bucket_size)}}; // a basic form of clustering
125 if (delta[0] == 0 && delta[1] == 0 && delta[2] == 0) continue;
126 delta_frequency_map[delta] += sqrt(sqrt(delta_distances[i]));
127 }
128
129 const float delta_distance_multiplier = 1.0f / num_pixels;
130
131 // Weigh frequencies by magnitude and normalize.
132 for (auto &delta_frequency : delta_frequency_map) {
133 std::vector<pixel_type> current_delta = {delta_frequency.first[0],
134 delta_frequency.first[1],
135 delta_frequency.first[2]};
136 float delta_distance =
137 std::sqrt(palette_internal::ColorDistance({0, 0, 0}, current_delta)) +
138 1;
139 delta_frequency.second *= delta_distance * delta_distance_multiplier;
140 }
141
142 // Sort by weighted frequency.
143 using pixel_type_3d_frequency = std::pair<pixel_type_3d, double>;
144 std::vector<pixel_type_3d_frequency> sorted_delta_frequency_map(
145 delta_frequency_map.begin(), delta_frequency_map.end());
146 std::sort(
147 sorted_delta_frequency_map.begin(), sorted_delta_frequency_map.end(),
148 [](const pixel_type_3d_frequency &a, const pixel_type_3d_frequency &b) {
149 return a.second > b.second;
150 });
151
152 // Store the top deltas.
153 for (auto &delta_frequency : sorted_delta_frequency_map) {
154 if (frequent_deltas[0].size() >= kMaxDeltas) break;
155 // Number obtained by optimizing on jyrki31 corpus:
156 if (delta_frequency.second < 17) break;
157 for (int c = 0; c < 3; ++c) {
158 frequent_deltas[c].push_back(delta_frequency.first[c] * bucket_size);
159 }
160 }
161 }
162 };
163
164 Status FwdPaletteIteration(Image &input, uint32_t begin_c, uint32_t end_c,
165 uint32_t &nb_colors, uint32_t &nb_deltas,
166 bool ordered, bool lossy, Predictor &predictor,
167 const weighted::Header &wp_header,
168 PaletteIterationData &palette_iteration_data) {
169 JXL_QUIET_RETURN_IF_ERROR(CheckEqualChannels(input, begin_c, end_c));
170 JXL_ENSURE(begin_c >= input.nb_meta_channels);
171 JxlMemoryManager *memory_manager = input.memory_manager();
172 uint32_t nb = end_c - begin_c + 1;
173
174 size_t w = input.channel[begin_c].w;
175 size_t h = input.channel[begin_c].h;
176 if (input.bitdepth >= 32) return false;
177 if (!lossy && nb_colors < 2) return false;
178
179 if (!lossy && nb == 1) {
180 // Channel palette special case
181 if (nb_colors == 0) return false;
182 std::vector<pixel_type> lookup;
183 pixel_type minval;
184 pixel_type maxval;
185 compute_minmax(input.channel[begin_c], &minval, &maxval);
186 size_t lookup_table_size =
187 static_cast<int64_t>(maxval) - static_cast<int64_t>(minval) + 1;
188 if (lookup_table_size > palette_internal::kMaxPaletteLookupTableSize) {
189 // a lookup table would use too much memory, instead use a slower approach
190 // with std::set
191 std::set<pixel_type> chpalette;
192 pixel_type idx = 0;
193 for (size_t y = 0; y < h; y++) {
194 const pixel_type *p = input.channel[begin_c].Row(y);
195 for (size_t x = 0; x < w; x++) {
196 const bool new_color = chpalette.insert(p[x]).second;
197 if (new_color) {
198 idx++;
199 if (idx > static_cast<int>(nb_colors)) return false;
200 }
201 }
202 }
203 JXL_DEBUG_V(6, "Channel %i uses only %i colors.", begin_c, idx);
204 JXL_ASSIGN_OR_RETURN(Channel pch,
205 Channel::Create(memory_manager, idx, 1));
206 pch.hshift = -1;
207 pch.vshift = -1;
208 nb_colors = idx;
209 idx = 0;
210 pixel_type *JXL_RESTRICT p_palette = pch.Row(0);
211 for (pixel_type p : chpalette) {
212 p_palette[idx++] = p;
213 }
214 for (size_t y = 0; y < h; y++) {
215 pixel_type *p = input.channel[begin_c].Row(y);
216 for (size_t x = 0; x < w; x++) {
217 for (idx = 0;
218 p[x] != p_palette[idx] && idx < static_cast<int>(nb_colors);
219 idx++) {
220 // no-op
221 }
222 JXL_DASSERT(idx < static_cast<int>(nb_colors));
223 p[x] = idx;
224 }
225 }
226 predictor = Predictor::Zero;
227 input.nb_meta_channels++;
228 input.channel.insert(input.channel.begin(), std::move(pch));
229
230 return true;
231 }
232 lookup.resize(lookup_table_size, 0);
233 pixel_type idx = 0;
234 for (size_t y = 0; y < h; y++) {
235 const pixel_type *p = input.channel[begin_c].Row(y);
236 for (size_t x = 0; x < w; x++) {
237 if (lookup[p[x] - minval] == 0) {
238 lookup[p[x] - minval] = 1;
239 idx++;
240 if (idx > static_cast<int>(nb_colors)) return false;
241 }
242 }
243 }
244 JXL_DEBUG_V(6, "Channel %i uses only %i colors.", begin_c, idx);
245 JXL_ASSIGN_OR_RETURN(Channel pch, Channel::Create(memory_manager, idx, 1));
246 pch.hshift = -1;
247 pch.vshift = -1;
248 nb_colors = idx;
249 idx = 0;
250 pixel_type *JXL_RESTRICT p_palette = pch.Row(0);
251 for (size_t i = 0; i < lookup_table_size; i++) {
252 if (lookup[i]) {
253 p_palette[idx] = i + minval;
254 lookup[i] = idx;
255 idx++;
256 }
257 }
258 for (size_t y = 0; y < h; y++) {
259 pixel_type *p = input.channel[begin_c].Row(y);
260 for (size_t x = 0; x < w; x++) p[x] = lookup[p[x] - minval];
261 }
262 predictor = Predictor::Zero;
263 input.nb_meta_channels++;
264 input.channel.insert(input.channel.begin(), std::move(pch));
265 return true;
266 }
267
268 Image quantized_input(memory_manager);
269 if (lossy) {
270 JXL_ASSIGN_OR_RETURN(quantized_input, Image::Create(memory_manager, w, h,
271 input.bitdepth, nb));
272 for (size_t c = 0; c < nb; c++) {
273 JXL_RETURN_IF_ERROR(CopyImageTo(input.channel[begin_c + c].plane,
274 &quantized_input.channel[c].plane));
275 }
276 }
277
278 JXL_DEBUG_V(
279 7, "Trying to represent channels %i-%i using at most a %i-color palette.",
280 begin_c, end_c, nb_colors);
281 nb_deltas = 0;
282 bool delta_used = false;
283 std::set<std::vector<pixel_type>> candidate_palette;
284 std::vector<std::vector<pixel_type>> candidate_palette_imageorder;
285 std::vector<pixel_type> color(nb);
286 std::vector<float> color_with_error(nb);
287 std::vector<const pixel_type *> p_in(nb);
288 std::map<std::vector<pixel_type>, size_t> inv_palette;
289
290 if (lossy) {
291 palette_iteration_data.FindFrequentColorDeltas(w * h, input.bitdepth);
292 nb_deltas = palette_iteration_data.frequent_deltas[0].size();
293
294 // Count color frequency for colors that make a cross.
295 std::map<std::vector<pixel_type>, size_t> color_freq_map;
296 for (size_t y = 1; y + 1 < h; y++) {
297 for (uint32_t c = 0; c < nb; c++) {
298 p_in[c] = input.channel[begin_c + c].Row(y);
299 }
300 for (size_t x = 1; x + 1 < w; x++) {
301 for (uint32_t c = 0; c < nb; c++) {
302 color[c] = p_in[c][x];
303 }
304 int offsets[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
305 bool makes_cross = true;
306 for (int i = 0; i < 4 && makes_cross; ++i) {
307 int dx = offsets[i][0];
308 int dy = offsets[i][1];
309 for (uint32_t c = 0; c < nb && makes_cross; c++) {
310 if (input.channel[begin_c + c].Row(y + dy)[x + dx] != color[c]) {
311 makes_cross = false;
312 }
313 }
314 }
315 if (makes_cross) color_freq_map[color] += 1;
316 }
317 }
318 // Add colors satisfying frequency condition to the palette.
319 constexpr float kImageFraction = 0.01f;
320 size_t color_frequency_lower_bound = 5 + input.h * input.w * kImageFraction;
321 for (const auto &color_freq : color_freq_map) {
322 if (color_freq.second > color_frequency_lower_bound) {
323 candidate_palette.insert(color_freq.first);
324 candidate_palette_imageorder.push_back(color_freq.first);
325 }
326 }
327 }
328
329 std::map<std::vector<pixel_type>, bool> implicit_color;
330 std::vector<std::vector<pixel_type>> implicit_colors;
331 implicit_colors.reserve(palette_internal::kImplicitPaletteSize);
332 for (size_t k = 0; k < palette_internal::kImplicitPaletteSize; k++) {
333 for (size_t i = 0; i < nb; i++) {
334 color[i] = palette_internal::GetPaletteValue(nullptr, k, i, 0, 0,
335 input.bitdepth);
336 }
337 implicit_color[color] = true;
338 implicit_colors.push_back(color);
339 }
340
341 std::map<std::vector<pixel_type>, size_t> color_freq_map;
342 uint32_t implicit_colors_used = 0;
343 for (size_t y = 0; y < h; y++) {
344 for (uint32_t c = 0; c < nb; c++) {
345 p_in[c] = input.channel[begin_c + c].Row(y);
346 }
347 for (size_t x = 0; x < w; x++) {
348 if (lossy && candidate_palette.size() >= nb_colors) break;
349 for (uint32_t c = 0; c < nb; c++) {
350 color[c] = p_in[c][x];
351 }
352 const bool new_color = candidate_palette.insert(color).second;
353 if (new_color) {
354 if (implicit_color[color]) {
355 implicit_colors_used++;
356 } else {
357 candidate_palette_imageorder.push_back(color);
358 if (candidate_palette_imageorder.size() > nb_colors) {
359 return false; // too many colors
360 }
361 }
362 }
363 color_freq_map[color] += 1;
364 }
365 }
366
367 nb_colors = nb_deltas + candidate_palette_imageorder.size();
368
369 // not useful to make a single-color palette
370 if (!lossy && nb_colors + implicit_colors_used == 1) return false;
371 // TODO(jon): if this happens (e.g. solid white group), special-case it for
372 // faster encode
373
374 for (size_t k = 0; k < palette_internal::kImplicitPaletteSize; k++) {
375 color = implicit_colors[k];
376 // still add the color to the explicit palette if it is frequent enough
377 if (color_freq_map[color] > 10) {
378 nb_colors++;
379 candidate_palette_imageorder.push_back(color);
380 }
381 }
382 for (size_t k = 0; k < palette_internal::kImplicitPaletteSize; k++) {
383 color = implicit_colors[k];
384 inv_palette[color] = nb_colors + k;
385 }
386
387 JXL_DEBUG_V(6, "Channels %i-%i can be represented using a %i-color palette.",
388 begin_c, end_c, nb_colors);
389
390 JXL_ASSIGN_OR_RETURN(Channel pch,
391 Channel::Create(memory_manager, nb_colors, nb));
392 pch.hshift = -1;
393 pch.vshift = -1;
394 pixel_type *JXL_RESTRICT p_palette = pch.Row(0);
395 intptr_t onerow = pch.plane.PixelsPerRow();
396 intptr_t onerow_image = input.channel[begin_c].plane.PixelsPerRow();
397 const int bit_depth = std::min(input.bitdepth, 24);
398
399 if (lossy) {
400 for (uint32_t i = 0; i < nb_deltas; i++) {
401 for (size_t c = 0; c < 3; c++) {
402 p_palette[c * onerow + i] =
403 palette_iteration_data.frequent_deltas[c][i];
404 }
405 }
406 }
407 // Separate the palette in two buckets, first the common colors, then the
408 // rare colors.
409 // Within each bucket, the colors are sorted on luma (times alpha).
410 float freq_threshold = 4; // arbitrary threshold
411 int x = 0;
412 if (ordered && nb >= 3) {
413 JXL_DEBUG_V(7, "Palette of %i colors, using luma order", nb_colors);
414 // sort on luma (multiplied by alpha if available)
415 std::sort(candidate_palette_imageorder.begin(),
416 candidate_palette_imageorder.end(),
417 [&](std::vector<pixel_type> ap, std::vector<pixel_type> bp) {
418 float ay;
419 float by;
420 ay = (0.299f * ap[0] + 0.587f * ap[1] + 0.114f * ap[2] + 0.1f);
421 if (ap.size() > 3) ay *= 1.f + ap[3];
422 by = (0.299f * bp[0] + 0.587f * bp[1] + 0.114f * bp[2] + 0.1f);
423 if (bp.size() > 3) by *= 1.f + bp[3];
424 // put common colors first, transparent dark to opaque bright,
425 // then rare colors, bright to dark
426 ay = color_freq_map[ap] > freq_threshold ? -ay : ay;
427 by = color_freq_map[bp] > freq_threshold ? -by : by;
428 return ay < by;
429 });
430 } else {
431 JXL_DEBUG_V(7, "Palette of %i colors, using image order", nb_colors);
432 }
433
434 for (auto pcol : candidate_palette_imageorder) {
435 JXL_DEBUG_V(9, " Color %i : ", x);
436 for (size_t i = 0; i < nb; i++) {
437 p_palette[nb_deltas + i * onerow + x] = pcol[i];
438 JXL_DEBUG_V(9, "%i ", pcol[i]);
439 }
440 inv_palette[pcol] = x;
441 x++;
442 }
443 std::vector<weighted::State> wp_states;
444 for (size_t c = 0; c < nb; c++) {
445 wp_states.emplace_back(wp_header, w, h);
446 }
447 std::vector<pixel_type *> p_quant(nb);
448 // Three rows of error for dithering: y to y + 2.
449 // Each row has two pixels of padding in the ends, which is
450 // beneficial for both precision and encoding speed.
451 std::vector<std::vector<float>> error_row[3];
452 if (lossy) {
453 for (auto &row : error_row) {
454 row.resize(nb);
455 for (size_t c = 0; c < nb; ++c) {
456 row[c].resize(w + 4);
457 }
458 }
459 }
460 for (size_t y = 0; y < h; y++) {
461 for (size_t c = 0; c < nb; c++) {
462 p_in[c] = input.channel[begin_c + c].Row(y);
463 if (lossy) p_quant[c] = quantized_input.channel[c].Row(y);
464 }
465 pixel_type *JXL_RESTRICT p = input.channel[begin_c].Row(y);
466 for (size_t x = 0; x < w; x++) {
467 int index;
468 if (!lossy) {
469 for (size_t c = 0; c < nb; c++) color[c] = p_in[c][x];
470 index = inv_palette[color];
471 } else {
472 int best_index = 0;
473 bool best_is_delta = false;
474 float best_distance = std::numeric_limits<float>::infinity();
475 std::vector<pixel_type> best_val(nb, 0);
476 std::vector<pixel_type> ideal_residual(nb, 0);
477 std::vector<pixel_type> quantized_val(nb);
478 std::vector<pixel_type> predictions(nb);
479 for (double diffusion_multiplier : {0.55, 0.75}) {
480 for (size_t c = 0; c < nb; c++) {
481 color_with_error[c] =
482 p_in[c][x] + (palette_iteration_data.final_run ? 1 : 0) *
483 diffusion_multiplier * error_row[0][c][x + 2];
484 color[c] = Clamp1(lroundf(color_with_error[c]), 0l,
485 (1l << input.bitdepth) - 1);
486 }
487
488 for (size_t c = 0; c < nb; ++c) {
489 predictions[c] = PredictNoTreeWP(w, p_quant[c] + x, onerow_image, x,
490 y, predictor, &wp_states[c])
491 .guess;
492 }
493 const auto TryIndex = [&](const int index) {
494 for (size_t c = 0; c < nb; c++) {
495 quantized_val[c] = palette_internal::GetPaletteValue(
496 p_palette, index, /*c=*/c,
497 /*palette_size=*/nb_colors,
498 /*onerow=*/onerow, /*bit_depth=*/bit_depth);
499 if (index < static_cast<int>(nb_deltas)) {
500 quantized_val[c] += predictions[c];
501 }
502 }
503 const float color_distance =
504 32.0 / (1LL << std::max(0, 2 * (bit_depth - 8))) *
505 palette_internal::ColorDistance(color_with_error,
506 quantized_val);
507 float index_penalty = 0;
508 if (index == -1) {
509 index_penalty = -124;
510 } else if (index < 0) {
511 index_penalty = -2 * index;
512 } else if (index < static_cast<int>(nb_deltas)) {
513 index_penalty = 250;
514 } else if (index < static_cast<int>(nb_colors)) {
515 index_penalty = 150;
516 } else if (index < static_cast<int>(nb_colors) +
517 palette_internal::kLargeCubeOffset) {
518 index_penalty = 70;
519 } else {
520 index_penalty = 256;
521 }
522 const float distance = color_distance + index_penalty;
523 if (distance < best_distance) {
524 best_distance = distance;
525 best_index = index;
526 best_is_delta = index < static_cast<int>(nb_deltas);
527 best_val.swap(quantized_val);
528 for (size_t c = 0; c < nb; ++c) {
529 ideal_residual[c] = color_with_error[c] - predictions[c];
530 }
531 }
532 };
533 for (index = palette_internal::kMinImplicitPaletteIndex;
534 index < static_cast<int32_t>(nb_colors); index++) {
535 TryIndex(index);
536 }
537 TryIndex(palette_internal::QuantizeColorToImplicitPaletteIndex(
538 color, nb_colors, bit_depth,
539 /*high_quality=*/false));
540 if (palette_internal::kEncodeToHighQualityImplicitPalette) {
541 TryIndex(palette_internal::QuantizeColorToImplicitPaletteIndex(
542 color, nb_colors, bit_depth,
543 /*high_quality=*/true));
544 }
545 }
546 index = best_index;
547 delta_used |= best_is_delta;
548 if (!palette_iteration_data.final_run) {
549 for (size_t c = 0; c < 3; ++c) {
550 palette_iteration_data.deltas[c].push_back(ideal_residual[c]);
551 }
552 palette_iteration_data.delta_distances.push_back(best_distance);
553 }
554
555 for (size_t c = 0; c < nb; ++c) {
556 wp_states[c].UpdateErrors(best_val[c], x, y, w);
557 p_quant[c][x] = best_val[c];
558 }
559 float len_error = 0;
560 for (size_t c = 0; c < nb; ++c) {
561 float local_error = color_with_error[c] - best_val[c];
562 len_error += local_error * local_error;
563 }
564 len_error = std::sqrt(len_error);
565 float modulate = 1.0;
566 int len_limit = 38 << std::max(0, bit_depth - 8);
567 if (len_error > len_limit) {
568 modulate *= len_limit / len_error;
569 }
570 for (size_t c = 0; c < nb; ++c) {
571 float total_error = (color_with_error[c] - best_val[c]);
572
573 // If the neighboring pixels have some error in the opposite
574 // direction of total_error, cancel some or all of it out before
575 // spreading among them.
576 constexpr int offsets[12][2] = {{1, 2}, {0, 3}, {0, 4}, {1, 1},
577 {1, 3}, {2, 2}, {1, 0}, {1, 4},
578 {2, 1}, {2, 3}, {2, 0}, {2, 4}};
579 float total_available = 0;
580 for (int i = 0; i < 11; ++i) {
581 const int row = offsets[i][0];
582 const int col = offsets[i][1];
583 if (std::signbit(error_row[row][c][x + col]) !=
584 std::signbit(total_error)) {
585 total_available += error_row[row][c][x + col];
586 }
587 }
588 float weight =
589 std::abs(total_error) / (std::abs(total_available) + 1e-3);
590 weight = std::min(weight, 1.0f);
591 for (int i = 0; i < 11; ++i) {
592 const int row = offsets[i][0];
593 const int col = offsets[i][1];
594 if (std::signbit(error_row[row][c][x + col]) !=
595 std::signbit(total_error)) {
596 total_error += weight * error_row[row][c][x + col];
597 error_row[row][c][x + col] *= (1 - weight);
598 }
599 }
600 total_error *= modulate;
601 const float remaining_error = (1.0f / 14.) * total_error;
602 error_row[0][c][x + 3] += 2 * remaining_error;
603 error_row[0][c][x + 4] += remaining_error;
604 error_row[1][c][x + 0] += remaining_error;
605 for (int i = 0; i < 5; ++i) {
606 error_row[1][c][x + i] += remaining_error;
607 error_row[2][c][x + i] += remaining_error;
608 }
609 }
610 }
611 if (palette_iteration_data.final_run) p[x] = index;
612 }
613 if (lossy) {
614 for (size_t c = 0; c < nb; ++c) {
615 error_row[0][c].swap(error_row[1][c]);
616 error_row[1][c].swap(error_row[2][c]);
617 std::fill(error_row[2][c].begin(), error_row[2][c].end(), 0.f);
618 }
619 }
620 }
621 if (!delta_used) {
622 predictor = Predictor::Zero;
623 }
624 if (palette_iteration_data.final_run) {
625 input.nb_meta_channels++;
626 input.channel.erase(input.channel.begin() + begin_c + 1,
627 input.channel.begin() + end_c + 1);
628 input.channel.insert(input.channel.begin(), std::move(pch));
629 }
630 nb_colors -= nb_deltas;
631 return true;
632 }
633
634 Status FwdPalette(Image &input, uint32_t begin_c, uint32_t end_c,
635 uint32_t &nb_colors, uint32_t &nb_deltas, bool ordered,
636 bool lossy, Predictor &predictor,
637 const weighted::Header &wp_header) {
638 PaletteIterationData palette_iteration_data;
639 uint32_t nb_colors_orig = nb_colors;
640 uint32_t nb_deltas_orig = nb_deltas;
641 // preprocessing pass in case of lossy palette
642 if (lossy && input.bitdepth >= 8) {
643 JXL_RETURN_IF_ERROR(FwdPaletteIteration(
644 input, begin_c, end_c, nb_colors_orig, nb_deltas_orig, ordered, lossy,
645 predictor, wp_header, palette_iteration_data));
646 }
647 palette_iteration_data.final_run = true;
648 return FwdPaletteIteration(input, begin_c, end_c, nb_colors, nb_deltas,
649 ordered, lossy, predictor, wp_header,
650 palette_iteration_data);
651 }
652
653 } // namespace jxl