diff options
| author | jzern@chromium.org <jzern@chromium.org@0039d316-1c4b-4281-b951-d872f2087c98> | 2012-08-07 04:04:45 +0000 |
|---|---|---|
| committer | jzern@chromium.org <jzern@chromium.org@0039d316-1c4b-4281-b951-d872f2087c98> | 2012-08-07 04:04:45 +0000 |
| commit | 4260fdd0ac22af2f134ed904af47455e43e59e2c (patch) | |
| tree | 26bba129e88ff4aac6786d7165cafc99e172b89c /third_party/libwebp/utils/quant_levels.c | |
| parent | 44b517ae9cea786f7d8a5959d689c15bd2bb3799 (diff) | |
| download | chromium_src-4260fdd0ac22af2f134ed904af47455e43e59e2c.zip chromium_src-4260fdd0ac22af2f134ed904af47455e43e59e2c.tar.gz chromium_src-4260fdd0ac22af2f134ed904af47455e43e59e2c.tar.bz2 | |
libwebp: update snapshot to v0.2.0-rc1
adds lossless encoder/decoder with alpha support. the same is to used to
add alpha+VP8 support.
BUG=139925
BUG=133161
TEST=webkit layout tests
Review URL: https://chromiumcodereview.appspot.com/10832153
git-svn-id: svn://svn.chromium.org/chrome/trunk/src@150264 0039d316-1c4b-4281-b951-d872f2087c98
Diffstat (limited to 'third_party/libwebp/utils/quant_levels.c')
| -rw-r--r-- | third_party/libwebp/utils/quant_levels.c | 154 |
1 files changed, 154 insertions, 0 deletions
diff --git a/third_party/libwebp/utils/quant_levels.c b/third_party/libwebp/utils/quant_levels.c new file mode 100644 index 0000000..f688439 --- /dev/null +++ b/third_party/libwebp/utils/quant_levels.c @@ -0,0 +1,154 @@ +// Copyright 2011 Google Inc. All Rights Reserved. +// +// This code is licensed under the same terms as WebM: +// Software License Agreement: http://www.webmproject.org/license/software/ +// Additional IP Rights Grant: http://www.webmproject.org/license/additional/ +// ----------------------------------------------------------------------------- +// +// Quantize levels for specified number of quantization-levels ([2, 256]). +// Min and max values are preserved (usual 0 and 255 for alpha plane). +// +// Author: Skal (pascal.massimino@gmail.com) + +#include <assert.h> + +#include "./quant_levels.h" + +#if defined(__cplusplus) || defined(c_plusplus) +extern "C" { +#endif + +#define NUM_SYMBOLS 256 + +#define MAX_ITER 6 // Maximum number of convergence steps. +#define ERROR_THRESHOLD 1e-4 // MSE stopping criterion. + +// ----------------------------------------------------------------------------- +// Quantize levels. + +int QuantizeLevels(uint8_t* const data, int width, int height, + int num_levels, uint64_t* const sse) { + int freq[NUM_SYMBOLS] = { 0 }; + int q_level[NUM_SYMBOLS] = { 0 }; + double inv_q_level[NUM_SYMBOLS] = { 0 }; + int min_s = 255, max_s = 0; + const size_t data_size = height * width; + int i, num_levels_in, iter; + double last_err = 1.e38, err = 0.; + const double err_threshold = ERROR_THRESHOLD * data_size; + + if (data == NULL) { + return 0; + } + + if (width <= 0 || height <= 0) { + return 0; + } + + if (num_levels < 2 || num_levels > 256) { + return 0; + } + + { + size_t n; + num_levels_in = 0; + for (n = 0; n < data_size; ++n) { + num_levels_in += (freq[data[n]] == 0); + if (min_s > data[n]) min_s = data[n]; + if (max_s < data[n]) max_s = data[n]; + ++freq[data[n]]; + } + } + + if (num_levels_in <= num_levels) goto End; // nothing to do! + + // Start with uniformly spread centroids. + for (i = 0; i < num_levels; ++i) { + inv_q_level[i] = min_s + (double)(max_s - min_s) * i / (num_levels - 1); + } + + // Fixed values. Won't be changed. + q_level[min_s] = 0; + q_level[max_s] = num_levels - 1; + assert(inv_q_level[0] == min_s); + assert(inv_q_level[num_levels - 1] == max_s); + + // k-Means iterations. + for (iter = 0; iter < MAX_ITER; ++iter) { + double q_sum[NUM_SYMBOLS] = { 0 }; + double q_count[NUM_SYMBOLS] = { 0 }; + int s, slot = 0; + + // Assign classes to representatives. + for (s = min_s; s <= max_s; ++s) { + // Keep track of the nearest neighbour 'slot' + while (slot < num_levels - 1 && + 2 * s > inv_q_level[slot] + inv_q_level[slot + 1]) { + ++slot; + } + if (freq[s] > 0) { + q_sum[slot] += s * freq[s]; + q_count[slot] += freq[s]; + } + q_level[s] = slot; + } + + // Assign new representatives to classes. + if (num_levels > 2) { + for (slot = 1; slot < num_levels - 1; ++slot) { + const double count = q_count[slot]; + if (count > 0.) { + inv_q_level[slot] = q_sum[slot] / count; + } + } + } + + // Compute convergence error. + err = 0.; + for (s = min_s; s <= max_s; ++s) { + const double error = s - inv_q_level[q_level[s]]; + err += freq[s] * error * error; + } + + // Check for convergence: we stop as soon as the error is no + // longer improving. + if (last_err - err < err_threshold) break; + last_err = err; + } + + // Remap the alpha plane to quantized values. + { + // double->int rounding operation can be costly, so we do it + // once for all before remapping. We also perform the data[] -> slot + // mapping, while at it (avoid one indirection in the final loop). + uint8_t map[NUM_SYMBOLS]; + int s; + size_t n; + for (s = min_s; s <= max_s; ++s) { + const int slot = q_level[s]; + map[s] = (uint8_t)(inv_q_level[slot] + .5); + } + // Final pass. + for (n = 0; n < data_size; ++n) { + data[n] = map[data[n]]; + } + } + End: + // Store sum of squared error if needed. + if (sse != NULL) *sse = (uint64_t)err; + + return 1; +} + +int DequantizeLevels(uint8_t* const data, int width, int height) { + if (data == NULL || width <= 0 || height <= 0) return 0; + // TODO(skal): implement gradient smoothing. + (void)data; + (void)width; + (void)height; + return 1; +} + +#if defined(__cplusplus) || defined(c_plusplus) +} // extern "C" +#endif |