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