enc_palette.cc (24805B)
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