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 <assert.h>
  15 #include "./vp8enci.h"
  16 #include "../dsp/dsp.h"
  17
  18 // This table gives, for a given sharpness, the filtering strength to be
  19 // used (at least) in order to filter a given edge step delta.
  20 // This is constructed by brute force inspection: for all delta, we iterate
  21 // over all possible filtering strength / thresh until needs_filter() returns
  22 // true.
  23 #define MAX_DELTA_SIZE 64
  24 static const uint8_t kLevelsFromDelta[8][MAX_DELTA_SIZE] = {
  25   { 0,   1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15,
  26     16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
  27     32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
  28     48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63 },
  29   { 0,  1,  2,  3,  5,  6,  7,  8,  9, 11, 12, 13, 14, 15, 17, 18,
  30     20, 21, 23, 24, 26, 27, 29, 30, 32, 33, 35, 36, 38, 39, 41, 42,
  31     44, 45, 47, 48, 50, 51, 53, 54, 56, 57, 59, 60, 62, 63, 63, 63,
  32     63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63 },
  33   {  0,  1,  2,  3,  5,  6,  7,  8,  9, 11, 12, 13, 14, 16, 17, 19,
  34     20, 22, 23, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41, 43,
  35     44, 46, 47, 49, 50, 52, 53, 55, 56, 58, 59, 61, 62, 63, 63, 63,
  36     63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63 },
  37   {  0,  1,  2,  3,  5,  6,  7,  8,  9, 11, 12, 13, 15, 16, 18, 19,
  38     21, 22, 24, 25, 27, 28, 30, 31, 33, 34, 36, 37, 39, 40, 42, 43,
  39     45, 46, 48, 49, 51, 52, 54, 55, 57, 58, 60, 61, 63, 63, 63, 63,
  40     63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63 },
  41   {  0,  1,  2,  3,  5,  6,  7,  8,  9, 11, 12, 14, 15, 17, 18, 20,
  42     21, 23, 24, 26, 27, 29, 30, 32, 33, 35, 36, 38, 39, 41, 42, 44,
  43     45, 47, 48, 50, 51, 53, 54, 56, 57, 59, 60, 62, 63, 63, 63, 63,
  44     63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63 },
  45   {  0,  1,  2,  4,  5,  7,  8,  9, 11, 12, 13, 15, 16, 17, 19, 20,
  46     22, 23, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41, 43, 44,
  47     46, 47, 49, 50, 52, 53, 55, 56, 58, 59, 61, 62, 63, 63, 63, 63,
  48     63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63 },
  49   {  0,  1,  2,  4,  5,  7,  8,  9, 11, 12, 13, 15, 16, 18, 19, 21,
  50     22, 24, 25, 27, 28, 30, 31, 33, 34, 36, 37, 39, 40, 42, 43, 45,
  51     46, 48, 49, 51, 52, 54, 55, 57, 58, 60, 61, 63, 63, 63, 63, 63,
  52     63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63 },
  53   {  0,  1,  2,  4,  5,  7,  8,  9, 11, 12, 14, 15, 17, 18, 20, 21,
  54     23, 24, 26, 27, 29, 30, 32, 33, 35, 36, 38, 39, 41, 42, 44, 45,
  55     47, 48, 50, 51, 53, 54, 56, 57, 59, 60, 62, 63, 63, 63, 63, 63,
  56     63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63 }
  57 };
  58
  59 int VP8FilterStrengthFromDelta(int sharpness, int delta) {
  60   const int pos = (delta < MAX_DELTA_SIZE) ? delta : MAX_DELTA_SIZE - 1;
  61   assert(sharpness >= 0 && sharpness <= 7);
  62   return kLevelsFromDelta[sharpness][pos];
  63 }
  64
  65 //------------------------------------------------------------------------------
  66 // Paragraph 15.4: compute the inner-edge filtering strength
  67
  68 static int GetILevel(int sharpness, int level) {
  69   if (sharpness > 0) {
  70     if (sharpness > 4) {
  71       level >>= 2;
  72     } else {
  73       level >>= 1;
  74     }
  75     if (level > 9 - sharpness) {
  76       level = 9 - sharpness;
  77     }
  78   }
  79   if (level < 1) level = 1;
  80   return level;
  81 }
  82
  83 static void DoFilter(const VP8EncIterator* const it, int level) {
  84   const VP8Encoder* const enc = it->enc_;
  85   const int ilevel = GetILevel(enc->config_->filter_sharpness, level);
  86   const int limit = 2 * level + ilevel;
  87
  88   uint8_t* const y_dst = it->yuv_out2_ + Y_OFF;
  89   uint8_t* const u_dst = it->yuv_out2_ + U_OFF;
  90   uint8_t* const v_dst = it->yuv_out2_ + V_OFF;
  91
  92   // copy current block to yuv_out2_
  93   memcpy(y_dst, it->yuv_out_, YUV_SIZE * sizeof(uint8_t));
  94
  95   if (enc->filter_hdr_.simple_ == 1) {   // simple
  96     VP8SimpleHFilter16i(y_dst, BPS, limit);
  97     VP8SimpleVFilter16i(y_dst, BPS, limit);
  98   } else {    // complex
  99     const int hev_thresh = (level >= 40) ? 2 : (level >= 15) ? 1 : 0;
 100     VP8HFilter16i(y_dst, BPS, limit, ilevel, hev_thresh);
 101     VP8HFilter8i(u_dst, v_dst, BPS, limit, ilevel, hev_thresh);
 102     VP8VFilter16i(y_dst, BPS, limit, ilevel, hev_thresh);
 103     VP8VFilter8i(u_dst, v_dst, BPS, limit, ilevel, hev_thresh);
 104   }
 105 }
 106
 107 //------------------------------------------------------------------------------
 108 // SSIM metric
 109
 110 enum { KERNEL = 3 };
 111 static const double kMinValue = 1.e-10;  // minimal threshold
 112
 113 void VP8SSIMAddStats(const DistoStats* const src, DistoStats* const dst) {
 114   dst->w   += src->w;
 115   dst->xm  += src->xm;
 116   dst->ym  += src->ym;
 117   dst->xxm += src->xxm;
 118   dst->xym += src->xym;
 119   dst->yym += src->yym;
 120 }
 121
 122 static void VP8SSIMAccumulate(const uint8_t* src1, int stride1,
 123                               const uint8_t* src2, int stride2,
 124                               int xo, int yo, int W, int H,
 125                               DistoStats* const stats) {
 126   const int ymin = (yo - KERNEL < 0) ? 0 : yo - KERNEL;
 127   const int ymax = (yo + KERNEL > H - 1) ? H - 1 : yo + KERNEL;
 128   const int xmin = (xo - KERNEL < 0) ? 0 : xo - KERNEL;
 129   const int xmax = (xo + KERNEL > W - 1) ? W - 1 : xo + KERNEL;
 130   int x, y;
 131   src1 += ymin * stride1;
 132   src2 += ymin * stride2;
 133   for (y = ymin; y <= ymax; ++y, src1 += stride1, src2 += stride2) {
 134     for (x = xmin; x <= xmax; ++x) {
 135       const int s1 = src1[x];
 136       const int s2 = src2[x];
 137       stats->w   += 1;
 138       stats->xm  += s1;
 139       stats->ym  += s2;
 140       stats->xxm += s1 * s1;
 141       stats->xym += s1 * s2;
 142       stats->yym += s2 * s2;
 143     }
 144   }
 145 }
 146
 147 double VP8SSIMGet(const DistoStats* const stats) {
 148   const double xmxm = stats->xm * stats->xm;
 149   const double ymym = stats->ym * stats->ym;
 150   const double xmym = stats->xm * stats->ym;
 151   const double w2 = stats->w * stats->w;
 152   double sxx = stats->xxm * stats->w - xmxm;
 153   double syy = stats->yym * stats->w - ymym;
 154   double sxy = stats->xym * stats->w - xmym;
 155   double C1, C2;
 156   double fnum;
 157   double fden;
 158   // small errors are possible, due to rounding. Clamp to zero.
 159   if (sxx < 0.) sxx = 0.;
 160   if (syy < 0.) syy = 0.;
 161   C1 = 6.5025 * w2;
 162   C2 = 58.5225 * w2;
 163   fnum = (2 * xmym + C1) * (2 * sxy + C2);
 164   fden = (xmxm + ymym + C1) * (sxx + syy + C2);
 165   return (fden != 0.) ? fnum / fden : kMinValue;
 166 }
 167
 168 double VP8SSIMGetSquaredError(const DistoStats* const s) {
 169   if (s->w > 0.) {
 170     const double iw2 = 1. / (s->w * s->w);
 171     const double sxx = s->xxm * s->w - s->xm * s->xm;
 172     const double syy = s->yym * s->w - s->ym * s->ym;
 173     const double sxy = s->xym * s->w - s->xm * s->ym;
 174     const double SSE = iw2 * (sxx + syy - 2. * sxy);
 175     if (SSE > kMinValue) return SSE;
 176   }
 177   return kMinValue;
 178 }
 179
 180 void VP8SSIMAccumulatePlane(const uint8_t* src1, int stride1,
 181                             const uint8_t* src2, int stride2,
 182                             int W, int H, DistoStats* const stats) {
 183   int x, y;
 184   for (y = 0; y < H; ++y) {
 185     for (x = 0; x < W; ++x) {
 186       VP8SSIMAccumulate(src1, stride1, src2, stride2, x, y, W, H, stats);
 187     }
 188   }
 189 }
 190
 191 static double GetMBSSIM(const uint8_t* yuv1, const uint8_t* yuv2) {
 192   int x, y;
 193   DistoStats s = { .0, .0, .0, .0, .0, .0 };
 194
 195   // compute SSIM in a 10 x 10 window
 196   for (x = 3; x < 13; x++) {
 197     for (y = 3; y < 13; y++) {
 198       VP8SSIMAccumulate(yuv1 + Y_OFF, BPS, yuv2 + Y_OFF, BPS, x, y, 16, 16, &s);
 199     }
 200   }
 201   for (x = 1; x < 7; x++) {
 202     for (y = 1; y < 7; y++) {
 203       VP8SSIMAccumulate(yuv1 + U_OFF, BPS, yuv2 + U_OFF, BPS, x, y, 8, 8, &s);
 204       VP8SSIMAccumulate(yuv1 + V_OFF, BPS, yuv2 + V_OFF, BPS, x, y, 8, 8, &s);
 205     }
 206   }
 207   return VP8SSIMGet(&s);
 208 }
 209
 210 //------------------------------------------------------------------------------
 211 // Exposed APIs: Encoder should call the following 3 functions to adjust
 212 // loop filter strength
 213
 214 void VP8InitFilter(VP8EncIterator* const it) {
 215   if (it->lf_stats_ != NULL) {
 216     int s, i;
 217     for (s = 0; s < NUM_MB_SEGMENTS; s++) {
 218       for (i = 0; i < MAX_LF_LEVELS; i++) {
 219         (*it->lf_stats_)[s][i] = 0;
 220       }
 221     }
 222   }
 223 }
 224
 225 void VP8StoreFilterStats(VP8EncIterator* const it) {
 226   int d;
 227   VP8Encoder* const enc = it->enc_;
 228   const int s = it->mb_->segment_;
 229   const int level0 = enc->dqm_[s].fstrength_;  // TODO: ref_lf_delta[]
 230
 231   // explore +/-quant range of values around level0
 232   const int delta_min = -enc->dqm_[s].quant_;
 233   const int delta_max = enc->dqm_[s].quant_;
 234   const int step_size = (delta_max - delta_min >= 4) ? 4 : 1;
 235
 236   if (it->lf_stats_ == NULL) return;
 237
 238   // NOTE: Currently we are applying filter only across the sublock edges
 239   // There are two reasons for that.
 240   // 1. Applying filter on macro block edges will change the pixels in
 241   // the left and top macro blocks. That will be hard to restore
 242   // 2. Macro Blocks on the bottom and right are not yet compressed. So we
 243   // cannot apply filter on the right and bottom macro block edges.
 244   if (it->mb_->type_ == 1 && it->mb_->skip_) return;
 245
 246   // Always try filter level  zero
 247   (*it->lf_stats_)[s][0] += GetMBSSIM(it->yuv_in_, it->yuv_out_);
 248
 249   for (d = delta_min; d <= delta_max; d += step_size) {
 250     const int level = level0 + d;
 251     if (level <= 0 || level >= MAX_LF_LEVELS) {
 252       continue;
 253     }
 254     DoFilter(it, level);
 255     (*it->lf_stats_)[s][level] += GetMBSSIM(it->yuv_in_, it->yuv_out2_);
 256   }
 257 }
 258
 259 void VP8AdjustFilterStrength(VP8EncIterator* const it) {
 260   VP8Encoder* const enc = it->enc_;
 261   if (it->lf_stats_ != NULL) {
 262     int s;
 263     for (s = 0; s < NUM_MB_SEGMENTS; s++) {
 264       int i, best_level = 0;
 265       // Improvement over filter level 0 should be at least 1e-5 (relatively)
 266       double best_v = 1.00001 * (*it->lf_stats_)[s][0];
 267       for (i = 1; i < MAX_LF_LEVELS; i++) {
 268         const double v = (*it->lf_stats_)[s][i];
 269         if (v > best_v) {
 270           best_v = v;
 271           best_level = i;
 272         }
 273       }
 274       enc->dqm_[s].fstrength_ = best_level;
 275     }
 276   } else if (enc->config_->filter_strength > 0) {
 277     int max_level = 0;
 278     int s;
 279     for (s = 0; s < NUM_MB_SEGMENTS; s++) {
 280       VP8SegmentInfo* const dqm = &enc->dqm_[s];
 281       // this '>> 3' accounts for some inverse WHT scaling
 282       const int delta = (dqm->max_edge_ * dqm->y2_.q_[1]) >> 3;
 283       const int level =
 284           VP8FilterStrengthFromDelta(enc->filter_hdr_.sharpness_, delta);
 285       if (level > dqm->fstrength_) {
 286         dqm->fstrength_ = level;
 287       }
 288       if (max_level < dqm->fstrength_) {
 289         max_level = dqm->fstrength_;
 290       }
 291     }
 292     enc->filter_hdr_.level_ = max_level;
 293   }
 294 }
 295
 296 // -----------------------------------------------------------------------------