src/third_party/libwebp/enc/filter.c

   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 // Selecting filter level
  11 //
  12 // Author: somnath@google.com (Somnath Banerjee)
  13
  14 #include "./vp8enci.h"
  15
  16 #if defined(__cplusplus) || defined(c_plusplus)
  17 extern "C" {
  18 #endif
  19
  20 // NOTE: clip1, tables and InitTables are repeated entries of dsp.c
  21 static uint8_t abs0[255 + 255 + 1];     // abs(i)
  22 static uint8_t abs1[255 + 255 + 1];     // abs(i)>>1
  23 static int8_t sclip1[1020 + 1020 + 1];  // clips [-1020, 1020] to [-128, 127]
  24 static int8_t sclip2[112 + 112 + 1];    // clips [-112, 112] to [-16, 15]
  25 static uint8_t clip1[255 + 510 + 1];    // clips [-255,510] to [0,255]
  26
  27 static int tables_ok = 0;
  28
  29 static void InitTables(void) {
  30   if (!tables_ok) {
  31     int i;
  32     for (i = -255; i <= 255; ++i) {
  33       abs0[255 + i] = (i < 0) ? -i : i;
  34       abs1[255 + i] = abs0[255 + i] >> 1;
  35     }
  36     for (i = -1020; i <= 1020; ++i) {
  37       sclip1[1020 + i] = (i < -128) ? -128 : (i > 127) ? 127 : i;
  38     }
  39     for (i = -112; i <= 112; ++i) {
  40       sclip2[112 + i] = (i < -16) ? -16 : (i > 15) ? 15 : i;
  41     }
  42     for (i = -255; i <= 255 + 255; ++i) {
  43       clip1[255 + i] = (i < 0) ? 0 : (i > 255) ? 255 : i;
  44     }
  45     tables_ok = 1;
  46   }
  47 }
  48
  49 //------------------------------------------------------------------------------
  50 // Edge filtering functions
  51
  52 // 4 pixels in, 2 pixels out
  53 static WEBP_INLINE void do_filter2(uint8_t* p, int step) {
  54   const int p1 = p[-2*step], p0 = p[-step], q0 = p[0], q1 = p[step];
  55   const int a = 3 * (q0 - p0) + sclip1[1020 + p1 - q1];
  56   const int a1 = sclip2[112 + ((a + 4) >> 3)];
  57   const int a2 = sclip2[112 + ((a + 3) >> 3)];
  58   p[-step] = clip1[255 + p0 + a2];
  59   p[    0] = clip1[255 + q0 - a1];
  60 }
  61
  62 // 4 pixels in, 4 pixels out
  63 static WEBP_INLINE void do_filter4(uint8_t* p, int step) {
  64   const int p1 = p[-2*step], p0 = p[-step], q0 = p[0], q1 = p[step];
  65   const int a = 3 * (q0 - p0);
  66   const int a1 = sclip2[112 + ((a + 4) >> 3)];
  67   const int a2 = sclip2[112 + ((a + 3) >> 3)];
  68   const int a3 = (a1 + 1) >> 1;
  69   p[-2*step] = clip1[255 + p1 + a3];
  70   p[-  step] = clip1[255 + p0 + a2];
  71   p[      0] = clip1[255 + q0 - a1];
  72   p[   step] = clip1[255 + q1 - a3];
  73 }
  74
  75 // high edge-variance
  76 static WEBP_INLINE int hev(const uint8_t* p, int step, int thresh) {
  77   const int p1 = p[-2*step], p0 = p[-step], q0 = p[0], q1 = p[step];
  78   return (abs0[255 + p1 - p0] > thresh) || (abs0[255 + q1 - q0] > thresh);
  79 }
  80
  81 static WEBP_INLINE int needs_filter(const uint8_t* p, int step, int thresh) {
  82   const int p1 = p[-2*step], p0 = p[-step], q0 = p[0], q1 = p[step];
  83   return (2 * abs0[255 + p0 - q0] + abs1[255 + p1 - q1]) <= thresh;
  84 }
  85
  86 static WEBP_INLINE int needs_filter2(const uint8_t* p,
  87                                      int step, int t, int it) {
  88   const int p3 = p[-4*step], p2 = p[-3*step], p1 = p[-2*step], p0 = p[-step];
  89   const int q0 = p[0], q1 = p[step], q2 = p[2*step], q3 = p[3*step];
  90   if ((2 * abs0[255 + p0 - q0] + abs1[255 + p1 - q1]) > t)
  91     return 0;
  92   return abs0[255 + p3 - p2] <= it && abs0[255 + p2 - p1] <= it &&
  93          abs0[255 + p1 - p0] <= it && abs0[255 + q3 - q2] <= it &&
  94          abs0[255 + q2 - q1] <= it && abs0[255 + q1 - q0] <= it;
  95 }
  96
  97 //------------------------------------------------------------------------------
  98 // Simple In-loop filtering (Paragraph 15.2)
  99
 100 static void SimpleVFilter16(uint8_t* p, int stride, int thresh) {
 101   int i;
 102   for (i = 0; i < 16; ++i) {
 103     if (needs_filter(p + i, stride, thresh)) {
 104       do_filter2(p + i, stride);
 105     }
 106   }
 107 }
 108
 109 static void SimpleHFilter16(uint8_t* p, int stride, int thresh) {
 110   int i;
 111   for (i = 0; i < 16; ++i) {
 112     if (needs_filter(p + i * stride, 1, thresh)) {
 113       do_filter2(p + i * stride, 1);
 114     }
 115   }
 116 }
 117
 118 static void SimpleVFilter16i(uint8_t* p, int stride, int thresh) {
 119   int k;
 120   for (k = 3; k > 0; --k) {
 121     p += 4 * stride;
 122     SimpleVFilter16(p, stride, thresh);
 123   }
 124 }
 125
 126 static void SimpleHFilter16i(uint8_t* p, int stride, int thresh) {
 127   int k;
 128   for (k = 3; k > 0; --k) {
 129     p += 4;
 130     SimpleHFilter16(p, stride, thresh);
 131   }
 132 }
 133
 134 //------------------------------------------------------------------------------
 135 // Complex In-loop filtering (Paragraph 15.3)
 136
 137 static WEBP_INLINE void FilterLoop24(uint8_t* p,
 138                                      int hstride, int vstride, int size,
 139                                      int thresh, int ithresh, int hev_thresh) {
 140   while (size-- > 0) {
 141     if (needs_filter2(p, hstride, thresh, ithresh)) {
 142       if (hev(p, hstride, hev_thresh)) {
 143         do_filter2(p, hstride);
 144       } else {
 145         do_filter4(p, hstride);
 146       }
 147     }
 148     p += vstride;
 149   }
 150 }
 151
 152 // on three inner edges
 153 static void VFilter16i(uint8_t* p, int stride,
 154                        int thresh, int ithresh, int hev_thresh) {
 155   int k;
 156   for (k = 3; k > 0; --k) {
 157     p += 4 * stride;
 158     FilterLoop24(p, stride, 1, 16, thresh, ithresh, hev_thresh);
 159   }
 160 }
 161
 162 static void HFilter16i(uint8_t* p, int stride,
 163                        int thresh, int ithresh, int hev_thresh) {
 164   int k;
 165   for (k = 3; k > 0; --k) {
 166     p += 4;
 167     FilterLoop24(p, 1, stride, 16, thresh, ithresh, hev_thresh);
 168   }
 169 }
 170
 171 static void VFilter8i(uint8_t* u, uint8_t* v, int stride,
 172                       int thresh, int ithresh, int hev_thresh) {
 173   FilterLoop24(u + 4 * stride, stride, 1, 8, thresh, ithresh, hev_thresh);
 174   FilterLoop24(v + 4 * stride, stride, 1, 8, thresh, ithresh, hev_thresh);
 175 }
 176
 177 static void HFilter8i(uint8_t* u, uint8_t* v, int stride,
 178                       int thresh, int ithresh, int hev_thresh) {
 179   FilterLoop24(u + 4, 1, stride, 8, thresh, ithresh, hev_thresh);
 180   FilterLoop24(v + 4, 1, stride, 8, thresh, ithresh, hev_thresh);
 181 }
 182
 183 //------------------------------------------------------------------------------
 184
 185 void (*VP8EncVFilter16i)(uint8_t*, int, int, int, int) = VFilter16i;
 186 void (*VP8EncHFilter16i)(uint8_t*, int, int, int, int) = HFilter16i;
 187 void (*VP8EncVFilter8i)(uint8_t*, uint8_t*, int, int, int, int) = VFilter8i;
 188 void (*VP8EncHFilter8i)(uint8_t*, uint8_t*, int, int, int, int) = HFilter8i;
 189
 190 void (*VP8EncSimpleVFilter16i)(uint8_t*, int, int) = SimpleVFilter16i;
 191 void (*VP8EncSimpleHFilter16i)(uint8_t*, int, int) = SimpleHFilter16i;
 192
 193 //------------------------------------------------------------------------------
 194 // Paragraph 15.4: compute the inner-edge filtering strength
 195
 196 static int GetILevel(int sharpness, int level) {
 197   if (sharpness > 0) {
 198     if (sharpness > 4) {
 199       level >>= 2;
 200     } else {
 201       level >>= 1;
 202     }
 203     if (level > 9 - sharpness) {
 204       level = 9 - sharpness;
 205     }
 206   }
 207   if (level < 1) level = 1;
 208   return level;
 209 }
 210
 211 static void DoFilter(const VP8EncIterator* const it, int level) {
 212   const VP8Encoder* const enc = it->enc_;
 213   const int ilevel = GetILevel(enc->config_->filter_sharpness, level);
 214   const int limit = 2 * level + ilevel;
 215
 216   uint8_t* const y_dst = it->yuv_out2_ + Y_OFF;
 217   uint8_t* const u_dst = it->yuv_out2_ + U_OFF;
 218   uint8_t* const v_dst = it->yuv_out2_ + V_OFF;
 219
 220   // copy current block to yuv_out2_
 221   memcpy(y_dst, it->yuv_out_, YUV_SIZE * sizeof(uint8_t));
 222
 223   if (enc->filter_hdr_.simple_ == 1) {   // simple
 224     VP8EncSimpleHFilter16i(y_dst, BPS, limit);
 225     VP8EncSimpleVFilter16i(y_dst, BPS, limit);
 226   } else {    // complex
 227     const int hev_thresh = (level >= 40) ? 2 : (level >= 15) ? 1 : 0;
 228     VP8EncHFilter16i(y_dst, BPS, limit, ilevel, hev_thresh);
 229     VP8EncHFilter8i(u_dst, v_dst, BPS, limit, ilevel, hev_thresh);
 230     VP8EncVFilter16i(y_dst, BPS, limit, ilevel, hev_thresh);
 231     VP8EncVFilter8i(u_dst, v_dst, BPS, limit, ilevel, hev_thresh);
 232   }
 233 }
 234
 235 //------------------------------------------------------------------------------
 236 // SSIM metric
 237
 238 enum { KERNEL = 3 };
 239 static const double kMinValue = 1.e-10;  // minimal threshold
 240
 241 void VP8SSIMAddStats(const DistoStats* const src, DistoStats* const dst) {
 242   dst->w   += src->w;
 243   dst->xm  += src->xm;
 244   dst->ym  += src->ym;
 245   dst->xxm += src->xxm;
 246   dst->xym += src->xym;
 247   dst->yym += src->yym;
 248 }
 249
 250 static void VP8SSIMAccumulate(const uint8_t* src1, int stride1,
 251                               const uint8_t* src2, int stride2,
 252                               int xo, int yo, int W, int H,
 253                               DistoStats* const stats) {
 254   const int ymin = (yo - KERNEL < 0) ? 0 : yo - KERNEL;
 255   const int ymax = (yo + KERNEL > H - 1) ? H - 1 : yo + KERNEL;
 256   const int xmin = (xo - KERNEL < 0) ? 0 : xo - KERNEL;
 257   const int xmax = (xo + KERNEL > W - 1) ? W - 1 : xo + KERNEL;
 258   int x, y;
 259   src1 += ymin * stride1;
 260   src2 += ymin * stride2;
 261   for (y = ymin; y <= ymax; ++y, src1 += stride1, src2 += stride2) {
 262     for (x = xmin; x <= xmax; ++x) {
 263       const int s1 = src1[x];
 264       const int s2 = src2[x];
 265       stats->w   += 1;
 266       stats->xm  += s1;
 267       stats->ym  += s2;
 268       stats->xxm += s1 * s1;
 269       stats->xym += s1 * s2;
 270       stats->yym += s2 * s2;
 271     }
 272   }
 273 }
 274
 275 double VP8SSIMGet(const DistoStats* const stats) {
 276   const double xmxm = stats->xm * stats->xm;
 277   const double ymym = stats->ym * stats->ym;
 278   const double xmym = stats->xm * stats->ym;
 279   const double w2 = stats->w * stats->w;
 280   double sxx = stats->xxm * stats->w - xmxm;
 281   double syy = stats->yym * stats->w - ymym;
 282   double sxy = stats->xym * stats->w - xmym;
 283   double C1, C2;
 284   double fnum;
 285   double fden;
 286   // small errors are possible, due to rounding. Clamp to zero.
 287   if (sxx < 0.) sxx = 0.;
 288   if (syy < 0.) syy = 0.;
 289   C1 = 6.5025 * w2;
 290   C2 = 58.5225 * w2;
 291   fnum = (2 * xmym + C1) * (2 * sxy + C2);
 292   fden = (xmxm + ymym + C1) * (sxx + syy + C2);
 293   return (fden != 0.) ? fnum / fden : kMinValue;
 294 }
 295
 296 double VP8SSIMGetSquaredError(const DistoStats* const s) {
 297   if (s->w > 0.) {
 298     const double iw2 = 1. / (s->w * s->w);
 299     const double sxx = s->xxm * s->w - s->xm * s->xm;
 300     const double syy = s->yym * s->w - s->ym * s->ym;
 301     const double sxy = s->xym * s->w - s->xm * s->ym;
 302     const double SSE = iw2 * (sxx + syy - 2. * sxy);
 303     if (SSE > kMinValue) return SSE;
 304   }
 305   return kMinValue;
 306 }
 307
 308 void VP8SSIMAccumulatePlane(const uint8_t* src1, int stride1,
 309                             const uint8_t* src2, int stride2,
 310                             int W, int H, DistoStats* const stats) {
 311   int x, y;
 312   for (y = 0; y < H; ++y) {
 313     for (x = 0; x < W; ++x) {
 314       VP8SSIMAccumulate(src1, stride1, src2, stride2, x, y, W, H, stats);
 315     }
 316   }
 317 }
 318
 319 static double GetMBSSIM(const uint8_t* yuv1, const uint8_t* yuv2) {
 320   int x, y;
 321   DistoStats s = { .0, .0, .0, .0, .0, .0 };
 322
 323   // compute SSIM in a 10 x 10 window
 324   for (x = 3; x < 13; x++) {
 325     for (y = 3; y < 13; y++) {
 326       VP8SSIMAccumulate(yuv1 + Y_OFF, BPS, yuv2 + Y_OFF, BPS, x, y, 16, 16, &s);
 327     }
 328   }
 329   for (x = 1; x < 7; x++) {
 330     for (y = 1; y < 7; y++) {
 331       VP8SSIMAccumulate(yuv1 + U_OFF, BPS, yuv2 + U_OFF, BPS, x, y, 8, 8, &s);
 332       VP8SSIMAccumulate(yuv1 + V_OFF, BPS, yuv2 + V_OFF, BPS, x, y, 8, 8, &s);
 333     }
 334   }
 335   return VP8SSIMGet(&s);
 336 }
 337
 338 //------------------------------------------------------------------------------
 339 // Exposed APIs: Encoder should call the following 3 functions to adjust
 340 // loop filter strength
 341
 342 void VP8InitFilter(VP8EncIterator* const it) {
 343   int s, i;
 344   if (!it->lf_stats_) return;
 345
 346   InitTables();
 347   for (s = 0; s < NUM_MB_SEGMENTS; s++) {
 348     for (i = 0; i < MAX_LF_LEVELS; i++) {
 349       (*it->lf_stats_)[s][i] = 0;
 350     }
 351   }
 352 }
 353
 354 void VP8StoreFilterStats(VP8EncIterator* const it) {
 355   int d;
 356   const int s = it->mb_->segment_;
 357   const int level0 = it->enc_->dqm_[s].fstrength_;  // TODO: ref_lf_delta[]
 358
 359   // explore +/-quant range of values around level0
 360   const int delta_min = -it->enc_->dqm_[s].quant_;
 361   const int delta_max = it->enc_->dqm_[s].quant_;
 362   const int step_size = (delta_max - delta_min >= 4) ? 4 : 1;
 363
 364   if (!it->lf_stats_) return;
 365
 366   // NOTE: Currently we are applying filter only across the sublock edges
 367   // There are two reasons for that.
 368   // 1. Applying filter on macro block edges will change the pixels in
 369   // the left and top macro blocks. That will be hard to restore
 370   // 2. Macro Blocks on the bottom and right are not yet compressed. So we
 371   // cannot apply filter on the right and bottom macro block edges.
 372   if (it->mb_->type_ == 1 && it->mb_->skip_) return;
 373
 374   // Always try filter level  zero
 375   (*it->lf_stats_)[s][0] += GetMBSSIM(it->yuv_in_, it->yuv_out_);
 376
 377   for (d = delta_min; d <= delta_max; d += step_size) {
 378     const int level = level0 + d;
 379     if (level <= 0 || level >= MAX_LF_LEVELS) {
 380       continue;
 381     }
 382     DoFilter(it, level);
 383     (*it->lf_stats_)[s][level] += GetMBSSIM(it->yuv_in_, it->yuv_out2_);
 384   }
 385 }
 386
 387 void VP8AdjustFilterStrength(VP8EncIterator* const it) {
 388   int s;
 389   VP8Encoder* const enc = it->enc_;
 390
 391   if (!it->lf_stats_) {
 392     return;
 393   }
 394   for (s = 0; s < NUM_MB_SEGMENTS; s++) {
 395     int i, best_level = 0;
 396     // Improvement over filter level 0 should be at least 1e-5 (relatively)
 397     double best_v = 1.00001 * (*it->lf_stats_)[s][0];
 398     for (i = 1; i < MAX_LF_LEVELS; i++) {
 399       const double v = (*it->lf_stats_)[s][i];
 400       if (v > best_v) {
 401         best_v = v;
 402         best_level = i;
 403       }
 404     }
 405     enc->dqm_[s].fstrength_ = best_level;
 406   }
 407 }
 408
 409 #if defined(__cplusplus) || defined(c_plusplus)
 410 }    // extern "C"
 411 #endif