src/third_party/webrtc/modules/video_processing/main/source/deflickering.cc

   1 /*
   2  *  Copyright (c) 2011 The WebRTC project authors. All Rights Reserved.
   3  *
   4  *  Use of this source code is governed by a BSD-style license
   5  *  that can be found in the LICENSE file in the root of the source
   6  *  tree. An additional intellectual property rights grant can be found
   7  *  in the file PATENTS.  All contributing project authors may
   8  *  be found in the AUTHORS file in the root of the source tree.
   9  */
  10
  11 #include "webrtc/modules/video_processing/main/source/deflickering.h"
  12
  13 #include <math.h>
  14 #include <stdlib.h>
  15
  16 #include "webrtc/common_audio/signal_processing/include/signal_processing_library.h"
  17 #include "webrtc/system_wrappers/interface/logging.h"
  18 #include "webrtc/system_wrappers/interface/sort.h"
  19
  20 namespace webrtc {
  21
  22 // Detection constants
  23 // (Q4) Maximum allowed deviation for detection.
  24 enum { kFrequencyDeviation = 39 };
  25 // (Q4) Minimum frequency that can be detected.
  26 enum { kMinFrequencyToDetect = 32 };
  27 // Number of flickers before we accept detection
  28 enum { kNumFlickerBeforeDetect = 2 };
  29 enum { kmean_valueScaling = 4 };  // (Q4) In power of 2
  30 // Dead-zone region in terms of pixel values
  31 enum { kZeroCrossingDeadzone = 10 };
  32 // Deflickering constants.
  33 // Compute the quantiles over 1 / DownsamplingFactor of the image.
  34 enum { kDownsamplingFactor = 8 };
  35 enum { kLog2OfDownsamplingFactor = 3 };
  36
  37 // To generate in Matlab:
  38 // >> probUW16 = round(2^11 *
  39 //     [0.05,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,0.95,0.97]);
  40 // >> fprintf('%d, ', probUW16)
  41 // Resolution reduced to avoid overflow when multiplying with the
  42 // (potentially) large number of pixels.
  43 const uint16_t VPMDeflickering::prob_uw16_[kNumProbs] = {102, 205, 410, 614,
  44     819, 1024, 1229, 1434, 1638, 1843, 1946, 1987}; // <Q11>
  45
  46 // To generate in Matlab:
  47 // >> numQuants = 14; maxOnlyLength = 5;
  48 // >> weightUW16 = round(2^15 *
  49 //    [linspace(0.5, 1.0, numQuants - maxOnlyLength)]);
  50 // >> fprintf('%d, %d,\n ', weightUW16);
  51 const uint16_t VPMDeflickering::weight_uw16_[kNumQuants - kMaxOnlyLength] =
  52     {16384, 18432, 20480, 22528, 24576, 26624, 28672, 30720, 32768}; // <Q15>
  53
  54 VPMDeflickering::VPMDeflickering()
  55     : id_(0) {
  56   Reset();
  57 }
  58
  59 VPMDeflickering::~VPMDeflickering() {}
  60
  61 int32_t VPMDeflickering::ChangeUniqueId(const int32_t id) {
  62   id_ = id;
  63   return 0;
  64 }
  65
  66 void VPMDeflickering::Reset() {
  67   mean_buffer_length_ = 0;
  68   detection_state_ = 0;
  69   frame_rate_ = 0;
  70
  71   memset(mean_buffer_, 0, sizeof(int32_t) * kMeanBufferLength);
  72   memset(timestamp_buffer_, 0, sizeof(int32_t) * kMeanBufferLength);
  73
  74   // Initialize the history with a uniformly distributed histogram.
  75   quant_hist_uw8_[0][0] = 0;
  76   quant_hist_uw8_[0][kNumQuants - 1] = 255;
  77   for (int32_t i = 0; i < kNumProbs; i++) {
  78     // Unsigned round. <Q0>
  79     quant_hist_uw8_[0][i + 1] = static_cast<uint8_t>(
  80         (prob_uw16_[i] * 255 + (1 << 10)) >> 11);
  81   }
  82
  83   for (int32_t i = 1; i < kFrameHistory_size; i++) {
  84     memcpy(quant_hist_uw8_[i], quant_hist_uw8_[0],
  85            sizeof(uint8_t) * kNumQuants);
  86   }
  87 }
  88
  89 int32_t VPMDeflickering::ProcessFrame(I420VideoFrame* frame,
  90     VideoProcessingModule::FrameStats* stats) {
  91   assert(frame);
  92   uint32_t frame_memory;
  93   uint8_t quant_uw8[kNumQuants];
  94   uint8_t maxquant_uw8[kNumQuants];
  95   uint8_t minquant_uw8[kNumQuants];
  96   uint16_t target_quant_uw16[kNumQuants];
  97   uint16_t increment_uw16;
  98   uint8_t map_uw8[256];
  99
 100   uint16_t tmp_uw16;
 101   uint32_t tmp_uw32;
 102   int width = frame->width();
 103   int height = frame->height();
 104
 105   if (frame->IsZeroSize()) {
 106     return VPM_GENERAL_ERROR;
 107   }
 108
 109   // Stricter height check due to subsampling size calculation below.
 110   if (height < 2) {
 111     LOG(LS_ERROR) << "Invalid frame size.";
 112     return VPM_GENERAL_ERROR;
 113   }
 114
 115   if (!VideoProcessingModule::ValidFrameStats(*stats)) {
 116     return VPM_GENERAL_ERROR;
 117   }
 118
 119   if (PreDetection(frame->timestamp(), *stats) == -1) return VPM_GENERAL_ERROR;
 120
 121   // Flicker detection
 122   int32_t det_flicker = DetectFlicker();
 123   if (det_flicker < 0) {
 124     return VPM_GENERAL_ERROR;
 125   } else if (det_flicker != 1) {
 126     return 0;
 127   }
 128
 129   // Size of luminance component.
 130   const uint32_t y_size = height * width;
 131
 132   const uint32_t y_sub_size = width * (((height - 1) >>
 133       kLog2OfDownsamplingFactor) + 1);
 134   uint8_t* y_sorted = new uint8_t[y_sub_size];
 135   uint32_t sort_row_idx = 0;
 136   for (int i = 0; i < height; i += kDownsamplingFactor) {
 137     memcpy(y_sorted + sort_row_idx * width,
 138         frame->buffer(kYPlane) + i * width, width);
 139     sort_row_idx++;
 140   }
 141
 142   webrtc::Sort(y_sorted, y_sub_size, webrtc::TYPE_UWord8);
 143
 144   uint32_t prob_idx_uw32 = 0;
 145   quant_uw8[0] = 0;
 146   quant_uw8[kNumQuants - 1] = 255;
 147
 148   // Ensure we won't get an overflow below.
 149   // In practice, the number of subsampled pixels will not become this large.
 150   if (y_sub_size > (1 << 21) - 1) {
 151     LOG(LS_ERROR) << "Subsampled number of pixels too large.";
 152     return -1;
 153   }
 154
 155   for (int32_t i = 0; i < kNumProbs; i++) {
 156     // <Q0>.
 157     prob_idx_uw32 = WEBRTC_SPL_UMUL_32_16(y_sub_size, prob_uw16_[i]) >> 11;
 158     quant_uw8[i + 1] = y_sorted[prob_idx_uw32];
 159   }
 160
 161   delete [] y_sorted;
 162   y_sorted = NULL;
 163
 164   // Shift history for new frame.
 165   memmove(quant_hist_uw8_[1], quant_hist_uw8_[0],
 166       (kFrameHistory_size - 1) * kNumQuants * sizeof(uint8_t));
 167   // Store current frame in history.
 168   memcpy(quant_hist_uw8_[0], quant_uw8, kNumQuants * sizeof(uint8_t));
 169
 170   // We use a frame memory equal to the ceiling of half the frame rate to
 171   // ensure we capture an entire period of flicker.
 172   frame_memory = (frame_rate_ + (1 << 5)) >> 5;  // Unsigned ceiling. <Q0>
 173                                                  // frame_rate_ in Q4.
 174   if (frame_memory > kFrameHistory_size) {
 175     frame_memory = kFrameHistory_size;
 176   }
 177
 178   // Get maximum and minimum.
 179   for (int32_t i = 0; i < kNumQuants; i++) {
 180     maxquant_uw8[i] = 0;
 181     minquant_uw8[i] = 255;
 182     for (uint32_t j = 0; j < frame_memory; j++) {
 183       if (quant_hist_uw8_[j][i] > maxquant_uw8[i]) {
 184         maxquant_uw8[i] = quant_hist_uw8_[j][i];
 185       }
 186
 187       if (quant_hist_uw8_[j][i] < minquant_uw8[i]) {
 188         minquant_uw8[i] = quant_hist_uw8_[j][i];
 189       }
 190     }
 191   }
 192
 193   // Get target quantiles.
 194   for (int32_t i = 0; i < kNumQuants - kMaxOnlyLength; i++) {
 195     // target = w * maxquant_uw8 + (1 - w) * minquant_uw8
 196     // Weights w = |weight_uw16_| are in Q15, hence the final output has to be
 197     // right shifted by 8 to end up in Q7.
 198     target_quant_uw16[i] = static_cast<uint16_t>((
 199         weight_uw16_[i] * maxquant_uw8[i] +
 200         ((1 << 15) - weight_uw16_[i]) * minquant_uw8[i]) >> 8);  // <Q7>
 201   }
 202
 203   for (int32_t i = kNumQuants - kMaxOnlyLength; i < kNumQuants; i++) {
 204     target_quant_uw16[i] = ((uint16_t)maxquant_uw8[i]) << 7;
 205   }
 206
 207   // Compute the map from input to output pixels.
 208   uint16_t mapUW16;  // <Q7>
 209   for (int32_t i = 1; i < kNumQuants; i++) {
 210     // As quant and targetQuant are limited to UWord8, it's safe to use Q7 here.
 211     tmp_uw32 = static_cast<uint32_t>(target_quant_uw16[i] -
 212         target_quant_uw16[i - 1]);
 213     tmp_uw16 = static_cast<uint16_t>(quant_uw8[i] - quant_uw8[i - 1]);  // <Q0>
 214
 215     if (tmp_uw16 > 0) {
 216       increment_uw16 = static_cast<uint16_t>(WebRtcSpl_DivU32U16(tmp_uw32,
 217           tmp_uw16)); // <Q7>
 218     } else {
 219       // The value is irrelevant; the loop below will only iterate once.
 220       increment_uw16 = 0;
 221     }
 222
 223     mapUW16 = target_quant_uw16[i - 1];
 224     for (uint32_t j = quant_uw8[i - 1]; j < (uint32_t)(quant_uw8[i] + 1); j++) {
 225       // Unsigned round. <Q0>
 226       map_uw8[j] = (uint8_t)((mapUW16 + (1 << 6)) >> 7);
 227       mapUW16 += increment_uw16;
 228     }
 229   }
 230
 231   // Map to the output frame.
 232   uint8_t* buffer = frame->buffer(kYPlane);
 233   for (uint32_t i = 0; i < y_size; i++) {
 234     buffer[i] = map_uw8[buffer[i]];
 235   }
 236
 237   // Frame was altered, so reset stats.
 238   VideoProcessingModule::ClearFrameStats(stats);
 239
 240   return VPM_OK;
 241 }
 242
 243 /**
 244    Performs some pre-detection operations. Must be called before
 245    DetectFlicker().
 246
 247    \param[in] timestamp Timestamp of the current frame.
 248    \param[in] stats     Statistics of the current frame.
 249
 250    \return 0: Success\n
 251            2: Detection not possible due to flickering frequency too close to
 252               zero.\n
 253           -1: Error
 254 */
 255 int32_t VPMDeflickering::PreDetection(const uint32_t timestamp,
 256   const VideoProcessingModule::FrameStats& stats) {
 257   int32_t mean_val;  // Mean value of frame (Q4)
 258   uint32_t frame_rate = 0;
 259   int32_t meanBufferLength;  // Temp variable.
 260
 261   mean_val = ((stats.sum << kmean_valueScaling) / stats.num_pixels);
 262   // Update mean value buffer.
 263   // This should be done even though we might end up in an unreliable detection.
 264   memmove(mean_buffer_ + 1, mean_buffer_,
 265       (kMeanBufferLength - 1) * sizeof(int32_t));
 266   mean_buffer_[0] = mean_val;
 267
 268   // Update timestamp buffer.
 269   // This should be done even though we might end up in an unreliable detection.
 270   memmove(timestamp_buffer_ + 1, timestamp_buffer_, (kMeanBufferLength - 1) *
 271       sizeof(uint32_t));
 272   timestamp_buffer_[0] = timestamp;
 273
 274 /* Compute current frame rate (Q4) */
 275   if (timestamp_buffer_[kMeanBufferLength - 1] != 0) {
 276     frame_rate = ((90000 << 4) * (kMeanBufferLength - 1));
 277     frame_rate /=
 278         (timestamp_buffer_[0] - timestamp_buffer_[kMeanBufferLength - 1]);
 279   } else if (timestamp_buffer_[1] != 0) {
 280     frame_rate = (90000 << 4) / (timestamp_buffer_[0] - timestamp_buffer_[1]);
 281   }
 282
 283   /* Determine required size of mean value buffer (mean_buffer_length_) */
 284   if (frame_rate == 0) {
 285     meanBufferLength = 1;
 286   } else {
 287     meanBufferLength =
 288         (kNumFlickerBeforeDetect * frame_rate) / kMinFrequencyToDetect;
 289   }
 290   /* Sanity check of buffer length */
 291   if (meanBufferLength >= kMeanBufferLength) {
 292     /* Too long buffer. The flickering frequency is too close to zero, which
 293      * makes the estimation unreliable.
 294      */
 295     mean_buffer_length_ = 0;
 296     return 2;
 297   }
 298   mean_buffer_length_ = meanBufferLength;
 299
 300   if ((timestamp_buffer_[mean_buffer_length_ - 1] != 0) &&
 301       (mean_buffer_length_ != 1)) {
 302     frame_rate = ((90000 << 4) * (mean_buffer_length_ - 1));
 303     frame_rate /=
 304         (timestamp_buffer_[0] - timestamp_buffer_[mean_buffer_length_ - 1]);
 305   } else if (timestamp_buffer_[1] != 0) {
 306     frame_rate = (90000 << 4) / (timestamp_buffer_[0] - timestamp_buffer_[1]);
 307   }
 308   frame_rate_ = frame_rate;
 309
 310   return VPM_OK;
 311 }
 312
 313 /**
 314    This function detects flicker in the video stream. As a side effect the
 315    mean value buffer is updated with the new mean value.
 316
 317    \return 0: No flickering detected\n
 318            1: Flickering detected\n
 319            2: Detection not possible due to unreliable frequency interval
 320           -1: Error
 321 */
 322 int32_t VPMDeflickering::DetectFlicker() {
 323   uint32_t  i;
 324   int32_t  freqEst;       // (Q4) Frequency estimate to base detection upon
 325   int32_t  ret_val = -1;
 326
 327   /* Sanity check for mean_buffer_length_ */
 328   if (mean_buffer_length_ < 2) {
 329     /* Not possible to estimate frequency */
 330     return(2);
 331   }
 332   // Count zero crossings with a dead zone to be robust against noise. If the
 333   // noise std is 2 pixel this corresponds to about 95% confidence interval.
 334   int32_t deadzone = (kZeroCrossingDeadzone << kmean_valueScaling);  // Q4
 335   int32_t meanOfBuffer = 0;  // Mean value of mean value buffer.
 336   int32_t numZeros     = 0;  // Number of zeros that cross the dead-zone.
 337   int32_t cntState     = 0;  // State variable for zero crossing regions.
 338   int32_t cntStateOld  = 0;  // Previous state for zero crossing regions.
 339
 340   for (i = 0; i < mean_buffer_length_; i++) {
 341     meanOfBuffer += mean_buffer_[i];
 342   }
 343   meanOfBuffer += (mean_buffer_length_ >> 1);  // Rounding, not truncation.
 344   meanOfBuffer /= mean_buffer_length_;
 345
 346   // Count zero crossings.
 347   cntStateOld = (mean_buffer_[0] >= (meanOfBuffer + deadzone));
 348   cntStateOld -= (mean_buffer_[0] <= (meanOfBuffer - deadzone));
 349   for (i = 1; i < mean_buffer_length_; i++) {
 350     cntState = (mean_buffer_[i] >= (meanOfBuffer + deadzone));
 351     cntState -= (mean_buffer_[i] <= (meanOfBuffer - deadzone));
 352     if (cntStateOld == 0) {
 353       cntStateOld = -cntState;
 354     }
 355     if (((cntState + cntStateOld) == 0) && (cntState != 0)) {
 356       numZeros++;
 357       cntStateOld = cntState;
 358     }
 359   }
 360   // END count zero crossings.
 361
 362   /* Frequency estimation according to:
 363   * freqEst = numZeros * frame_rate / 2 / mean_buffer_length_;
 364   *
 365   * Resolution is set to Q4
 366   */
 367   freqEst = ((numZeros * 90000) << 3);
 368   freqEst /=
 369       (timestamp_buffer_[0] - timestamp_buffer_[mean_buffer_length_ - 1]);
 370
 371   /* Translate frequency estimate to regions close to 100 and 120 Hz */
 372   uint8_t freqState = 0;  // Current translation state;
 373                           // (0) Not in interval,
 374                           // (1) Within valid interval,
 375                           // (2) Out of range
 376   int32_t freqAlias = freqEst;
 377   if (freqEst > kMinFrequencyToDetect) {
 378     uint8_t aliasState = 1;
 379     while(freqState == 0) {
 380       /* Increase frequency */
 381       freqAlias += (aliasState * frame_rate_);
 382       freqAlias += ((freqEst << 1) * (1 - (aliasState << 1)));
 383       /* Compute state */
 384       freqState = (abs(freqAlias - (100 << 4)) <= kFrequencyDeviation);
 385       freqState += (abs(freqAlias - (120 << 4)) <= kFrequencyDeviation);
 386       freqState += 2 * (freqAlias > ((120 << 4) + kFrequencyDeviation));
 387       /* Switch alias state */
 388       aliasState++;
 389       aliasState &= 0x01;
 390     }
 391   }
 392   /* Is frequency estimate within detection region? */
 393   if (freqState == 1) {
 394     ret_val = 1;
 395   } else if (freqState == 0) {
 396     ret_val = 2;
 397   } else {
 398     ret_val = 0;
 399   }
 400   return ret_val;
 401 }
 402
 403 }  // namespace webrtc