1 // Copyright 2011 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 // Spatial prediction using various filters 11 // 12 // Author: Urvang (urvang (at) google.com) 13 14 #include "./filters.h" 15 #include <assert.h> 16 #include <stdlib.h> 17 #include <string.h> 18 19 #if defined(__cplusplus) || defined(c_plusplus) 20 extern "C" { 21 #endif 22 23 //------------------------------------------------------------------------------ 24 // Helpful macro. 25 26 # define SANITY_CHECK(in, out) \ 27 assert(in != NULL); \ 28 assert(out != NULL); \ 29 assert(width > 0); \ 30 assert(height > 0); \ 31 assert(stride >= width); 32 33 static WEBP_INLINE void PredictLine(const uint8_t* src, const uint8_t* pred, 34 uint8_t* dst, int length, int inverse) { 35 int i; 36 if (inverse) { 37 for (i = 0; i < length; ++i) dst[i] = src[i] + pred[i]; 38 } else { 39 for (i = 0; i < length; ++i) dst[i] = src[i] - pred[i]; 40 } 41 } 42 43 //------------------------------------------------------------------------------ 44 // Horizontal filter. 45 46 static WEBP_INLINE void DoHorizontalFilter(const uint8_t* in, 47 int width, int height, int stride, 48 int inverse, uint8_t* out) { 49 int h; 50 const uint8_t* preds = (inverse ? out : in); 51 SANITY_CHECK(in, out); 52 53 // Filter line-by-line. 54 for (h = 0; h < height; ++h) { 55 // Leftmost pixel is predicted from above (except for topmost scanline). 56 if (h == 0) { 57 out[0] = in[0]; 58 } else { 59 PredictLine(in, preds - stride, out, 1, inverse); 60 } 61 PredictLine(in + 1, preds, out + 1, width - 1, inverse); 62 preds += stride; 63 in += stride; 64 out += stride; 65 } 66 } 67 68 static void HorizontalFilter(const uint8_t* data, int width, int height, 69 int stride, uint8_t* filtered_data) { 70 DoHorizontalFilter(data, width, height, stride, 0, filtered_data); 71 } 72 73 static void HorizontalUnfilter(int width, int height, int stride, 74 uint8_t* data) { 75 DoHorizontalFilter(data, width, height, stride, 1, data); 76 } 77 78 //------------------------------------------------------------------------------ 79 // Vertical filter. 80 81 static WEBP_INLINE void DoVerticalFilter(const uint8_t* in, 82 int width, int height, int stride, 83 int inverse, uint8_t* out) { 84 int h; 85 const uint8_t* preds = (inverse ? out : in); 86 SANITY_CHECK(in, out); 87 88 // Very first top-left pixel is copied. 89 out[0] = in[0]; 90 // Rest of top scan-line is left-predicted. 91 PredictLine(in + 1, preds, out + 1, width - 1, inverse); 92 93 // Filter line-by-line. 94 for (h = 1; h < height; ++h) { 95 in += stride; 96 out += stride; 97 PredictLine(in, preds, out, width, inverse); 98 preds += stride; 99 } 100 } 101 102 static void VerticalFilter(const uint8_t* data, int width, int height, 103 int stride, uint8_t* filtered_data) { 104 DoVerticalFilter(data, width, height, stride, 0, filtered_data); 105 } 106 107 static void VerticalUnfilter(int width, int height, int stride, uint8_t* data) { 108 DoVerticalFilter(data, width, height, stride, 1, data); 109 } 110 111 //------------------------------------------------------------------------------ 112 // Gradient filter. 113 114 static WEBP_INLINE int GradientPredictor(uint8_t a, uint8_t b, uint8_t c) { 115 const int g = a + b - c; 116 return ((g & ~0xff) == 0) ? g : (g < 0) ? 0 : 255; // clip to 8bit 117 } 118 119 static WEBP_INLINE 120 void DoGradientFilter(const uint8_t* in, int width, int height, 121 int stride, int inverse, uint8_t* out) { 122 const uint8_t* preds = (inverse ? out : in); 123 int h; 124 SANITY_CHECK(in, out); 125 126 // left prediction for top scan-line 127 out[0] = in[0]; 128 PredictLine(in + 1, preds, out + 1, width - 1, inverse); 129 130 // Filter line-by-line. 131 for (h = 1; h < height; ++h) { 132 int w; 133 preds += stride; 134 in += stride; 135 out += stride; 136 // leftmost pixel: predict from above. 137 PredictLine(in, preds - stride, out, 1, inverse); 138 for (w = 1; w < width; ++w) { 139 const int pred = GradientPredictor(preds[w - 1], 140 preds[w - stride], 141 preds[w - stride - 1]); 142 out[w] = in[w] + (inverse ? pred : -pred); 143 } 144 } 145 } 146 147 static void GradientFilter(const uint8_t* data, int width, int height, 148 int stride, uint8_t* filtered_data) { 149 DoGradientFilter(data, width, height, stride, 0, filtered_data); 150 } 151 152 static void GradientUnfilter(int width, int height, int stride, uint8_t* data) { 153 DoGradientFilter(data, width, height, stride, 1, data); 154 } 155 156 #undef SANITY_CHECK 157 158 // ----------------------------------------------------------------------------- 159 // Quick estimate of a potentially interesting filter mode to try. 160 161 #define SMAX 16 162 #define SDIFF(a, b) (abs((a) - (b)) >> 4) // Scoring diff, in [0..SMAX) 163 164 WEBP_FILTER_TYPE EstimateBestFilter(const uint8_t* data, 165 int width, int height, int stride) { 166 int i, j; 167 int bins[WEBP_FILTER_LAST][SMAX]; 168 memset(bins, 0, sizeof(bins)); 169 170 // We only sample every other pixels. That's enough. 171 for (j = 2; j < height - 1; j += 2) { 172 const uint8_t* const p = data + j * stride; 173 int mean = p[0]; 174 for (i = 2; i < width - 1; i += 2) { 175 const int diff0 = SDIFF(p[i], mean); 176 const int diff1 = SDIFF(p[i], p[i - 1]); 177 const int diff2 = SDIFF(p[i], p[i - width]); 178 const int grad_pred = 179 GradientPredictor(p[i - 1], p[i - width], p[i - width - 1]); 180 const int diff3 = SDIFF(p[i], grad_pred); 181 bins[WEBP_FILTER_NONE][diff0] = 1; 182 bins[WEBP_FILTER_HORIZONTAL][diff1] = 1; 183 bins[WEBP_FILTER_VERTICAL][diff2] = 1; 184 bins[WEBP_FILTER_GRADIENT][diff3] = 1; 185 mean = (3 * mean + p[i] + 2) >> 2; 186 } 187 } 188 { 189 WEBP_FILTER_TYPE filter, best_filter = WEBP_FILTER_NONE; 190 int best_score = 0x7fffffff; 191 for (filter = WEBP_FILTER_NONE; filter < WEBP_FILTER_LAST; ++filter) { 192 int score = 0; 193 for (i = 0; i < SMAX; ++i) { 194 if (bins[filter][i] > 0) { 195 score += i; 196 } 197 } 198 if (score < best_score) { 199 best_score = score; 200 best_filter = filter; 201 } 202 } 203 return best_filter; 204 } 205 } 206 207 #undef SMAX 208 #undef SDIFF 209 210 //------------------------------------------------------------------------------ 211 212 const WebPFilterFunc WebPFilters[WEBP_FILTER_LAST] = { 213 NULL, // WEBP_FILTER_NONE 214 HorizontalFilter, // WEBP_FILTER_HORIZONTAL 215 VerticalFilter, // WEBP_FILTER_VERTICAL 216 GradientFilter // WEBP_FILTER_GRADIENT 217 }; 218 219 const WebPUnfilterFunc WebPUnfilters[WEBP_FILTER_LAST] = { 220 NULL, // WEBP_FILTER_NONE 221 HorizontalUnfilter, // WEBP_FILTER_HORIZONTAL 222 VerticalUnfilter, // WEBP_FILTER_VERTICAL 223 GradientUnfilter // WEBP_FILTER_GRADIENT 224 }; 225 226 //------------------------------------------------------------------------------ 227 228 #if defined(__cplusplus) || defined(c_plusplus) 229 } // extern "C" 230 #endif 231
