quant_levels_dec_utils.c (9072B)
1 // Copyright 2013 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 // Implement gradient smoothing: we replace a current alpha value by its 11 // surrounding average if it's close enough (that is: the change will be less 12 // than the minimum distance between two quantized level). 13 // We use sliding window for computing the 2d moving average. 14 // 15 // Author: Skal (pascal.massimino@gmail.com) 16 17 #include "src/utils/quant_levels_dec_utils.h" 18 19 #include <string.h> // for memset 20 21 #include "src/utils/utils.h" 22 #include "src/webp/types.h" 23 24 // #define USE_DITHERING // uncomment to enable ordered dithering (not vital) 25 26 #define FIX 16 // fix-point precision for averaging 27 #define LFIX 2 // extra precision for look-up table 28 #define LUT_SIZE ((1 << (8 + LFIX)) - 1) // look-up table size 29 30 #if defined(USE_DITHERING) 31 32 #define DFIX 4 // extra precision for ordered dithering 33 #define DSIZE 4 // dithering size (must be a power of two) 34 // cf. https://en.wikipedia.org/wiki/Ordered_dithering 35 static const uint8_t kOrderedDither[DSIZE][DSIZE] = { 36 { 0, 8, 2, 10 }, // coefficients are in DFIX fixed-point precision 37 { 12, 4, 14, 6 }, 38 { 3, 11, 1, 9 }, 39 { 15, 7, 13, 5 } 40 }; 41 42 #else 43 #define DFIX 0 44 #endif 45 46 typedef struct { 47 int width, height; // dimension 48 int stride; // stride in bytes 49 int row; // current input row being processed 50 uint8_t* src; // input pointer 51 uint8_t* dst; // output pointer 52 53 int radius; // filter radius (=delay) 54 int scale; // normalization factor, in FIX bits precision 55 56 void* mem; // all memory 57 58 // various scratch buffers 59 uint16_t* start; 60 uint16_t* cur; 61 uint16_t* end; 62 uint16_t* top; 63 uint16_t* average; 64 65 // input levels distribution 66 int num_levels; // number of quantized levels 67 int min, max; // min and max level values 68 int min_level_dist; // smallest distance between two consecutive levels 69 70 int16_t* correction; // size = 1 + 2*LUT_SIZE -> ~4k memory 71 } SmoothParams; 72 73 //------------------------------------------------------------------------------ 74 75 #define CLIP_8b_MASK (int)(~0U << (8 + DFIX)) 76 static WEBP_INLINE uint8_t clip_8b(int v) { 77 return (!(v & CLIP_8b_MASK)) ? (uint8_t)(v >> DFIX) : (v < 0) ? 0u : 255u; 78 } 79 #undef CLIP_8b_MASK 80 81 // vertical accumulation 82 static void VFilter(SmoothParams* const p) { 83 const uint8_t* src = p->src; 84 const int w = p->width; 85 uint16_t* const cur = p->cur; 86 const uint16_t* const top = p->top; 87 uint16_t* const out = p->end; 88 uint16_t sum = 0; // all arithmetic is modulo 16bit 89 int x; 90 91 for (x = 0; x < w; ++x) { 92 uint16_t new_value; 93 sum += src[x]; 94 new_value = top[x] + sum; 95 out[x] = new_value - cur[x]; // vertical sum of 'r' pixels. 96 cur[x] = new_value; 97 } 98 // move input pointers one row down 99 p->top = p->cur; 100 p->cur += w; 101 if (p->cur == p->end) p->cur = p->start; // roll-over 102 // We replicate edges, as it's somewhat easier as a boundary condition. 103 // That's why we don't update the 'src' pointer on top/bottom area: 104 if (p->row >= 0 && p->row < p->height - 1) { 105 p->src += p->stride; 106 } 107 } 108 109 // horizontal accumulation. We use mirror replication of missing pixels, as it's 110 // a little easier to implement (surprisingly). 111 static void HFilter(SmoothParams* const p) { 112 const uint16_t* const in = p->end; 113 uint16_t* const out = p->average; 114 const uint32_t scale = p->scale; 115 const int w = p->width; 116 const int r = p->radius; 117 118 int x; 119 for (x = 0; x <= r; ++x) { // left mirroring 120 const uint16_t delta = in[x + r - 1] + in[r - x]; 121 out[x] = (delta * scale) >> FIX; 122 } 123 for (; x < w - r; ++x) { // bulk middle run 124 const uint16_t delta = in[x + r] - in[x - r - 1]; 125 out[x] = (delta * scale) >> FIX; 126 } 127 for (; x < w; ++x) { // right mirroring 128 const uint16_t delta = 129 2 * in[w - 1] - in[2 * w - 2 - r - x] - in[x - r - 1]; 130 out[x] = (delta * scale) >> FIX; 131 } 132 } 133 134 // emit one filtered output row 135 static void ApplyFilter(SmoothParams* const p) { 136 const uint16_t* const average = p->average; 137 const int w = p->width; 138 const int16_t* const correction = p->correction; 139 #if defined(USE_DITHERING) 140 const uint8_t* const dither = kOrderedDither[p->row % DSIZE]; 141 #endif 142 uint8_t* const dst = p->dst; 143 int x; 144 for (x = 0; x < w; ++x) { 145 const int v = dst[x]; 146 if (v < p->max && v > p->min) { 147 const int c = (v << DFIX) + correction[average[x] - (v << LFIX)]; 148 #if defined(USE_DITHERING) 149 dst[x] = clip_8b(c + dither[x % DSIZE]); 150 #else 151 dst[x] = clip_8b(c); 152 #endif 153 } 154 } 155 p->dst += p->stride; // advance output pointer 156 } 157 158 //------------------------------------------------------------------------------ 159 // Initialize correction table 160 161 static void InitCorrectionLUT(int16_t* const lut, int min_dist) { 162 // The correction curve is: 163 // f(x) = x for x <= threshold2 164 // f(x) = 0 for x >= threshold1 165 // and a linear interpolation for range x=[threshold2, threshold1] 166 // (along with f(-x) = -f(x) symmetry). 167 // Note that: threshold2 = 3/4 * threshold1 168 const int threshold1 = min_dist << LFIX; 169 const int threshold2 = (3 * threshold1) >> 2; 170 const int max_threshold = threshold2 << DFIX; 171 const int delta = threshold1 - threshold2; 172 int i; 173 for (i = 1; i <= LUT_SIZE; ++i) { 174 int c = (i <= threshold2) ? (i << DFIX) 175 : (i < threshold1) ? max_threshold * (threshold1 - i) / delta 176 : 0; 177 c >>= LFIX; 178 lut[+i] = +c; 179 lut[-i] = -c; 180 } 181 lut[0] = 0; 182 } 183 184 static void CountLevels(SmoothParams* const p) { 185 int i, j, last_level; 186 uint8_t used_levels[256] = { 0 }; 187 const uint8_t* data = p->src; 188 p->min = 255; 189 p->max = 0; 190 for (j = 0; j < p->height; ++j) { 191 for (i = 0; i < p->width; ++i) { 192 const int v = data[i]; 193 if (v < p->min) p->min = v; 194 if (v > p->max) p->max = v; 195 used_levels[v] = 1; 196 } 197 data += p->stride; 198 } 199 // Compute the mininum distance between two non-zero levels. 200 p->min_level_dist = p->max - p->min; 201 last_level = -1; 202 for (i = 0; i < 256; ++i) { 203 if (used_levels[i]) { 204 ++p->num_levels; 205 if (last_level >= 0) { 206 const int level_dist = i - last_level; 207 if (level_dist < p->min_level_dist) { 208 p->min_level_dist = level_dist; 209 } 210 } 211 last_level = i; 212 } 213 } 214 } 215 216 // Initialize all params. 217 static int InitParams(uint8_t* const data, int width, int height, int stride, 218 int radius, SmoothParams* const p) { 219 const int R = 2 * radius + 1; // total size of the kernel 220 221 const size_t size_scratch_m = (R + 1) * width * sizeof(*p->start); 222 const size_t size_m = width * sizeof(*p->average); 223 const size_t size_lut = (1 + 2 * LUT_SIZE) * sizeof(*p->correction); 224 const size_t total_size = size_scratch_m + size_m + size_lut; 225 uint8_t* mem = (uint8_t*)WebPSafeMalloc(1U, total_size); 226 227 if (mem == NULL) return 0; 228 p->mem = (void*)mem; 229 230 p->start = (uint16_t*)mem; 231 p->cur = p->start; 232 p->end = p->start + R * width; 233 p->top = p->end - width; 234 memset(p->top, 0, width * sizeof(*p->top)); 235 mem += size_scratch_m; 236 237 p->average = (uint16_t*)mem; 238 mem += size_m; 239 240 p->width = width; 241 p->height = height; 242 p->stride = stride; 243 p->src = data; 244 p->dst = data; 245 p->radius = radius; 246 p->scale = (1 << (FIX + LFIX)) / (R * R); // normalization constant 247 p->row = -radius; 248 249 // analyze the input distribution so we can best-fit the threshold 250 CountLevels(p); 251 252 // correction table 253 p->correction = ((int16_t*)mem) + LUT_SIZE; 254 InitCorrectionLUT(p->correction, p->min_level_dist); 255 256 return 1; 257 } 258 259 static void CleanupParams(SmoothParams* const p) { 260 WebPSafeFree(p->mem); 261 } 262 263 int WebPDequantizeLevels(uint8_t* const data, int width, int height, int stride, 264 int strength) { 265 int radius = 4 * strength / 100; 266 267 if (strength < 0 || strength > 100) return 0; 268 if (data == NULL || width <= 0 || height <= 0) return 0; // bad params 269 270 // limit the filter size to not exceed the image dimensions 271 if (2 * radius + 1 > width) radius = (width - 1) >> 1; 272 if (2 * radius + 1 > height) radius = (height - 1) >> 1; 273 274 if (radius > 0) { 275 SmoothParams p; 276 memset(&p, 0, sizeof(p)); 277 if (!InitParams(data, width, height, stride, radius, &p)) return 0; 278 if (p.num_levels > 2) { 279 for (; p.row < p.height; ++p.row) { 280 VFilter(&p); // accumulate average of input 281 // Need to wait few rows in order to prime the filter, 282 // before emitting some output. 283 if (p.row >= p.radius) { 284 HFilter(&p); 285 ApplyFilter(&p); 286 } 287 } 288 } 289 CleanupParams(&p); 290 } 291 return 1; 292 }