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
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] = {
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);
52 const uint16_t VPMDeflickering::weight_uw16_[kNumQuants - kMaxOnlyLength] = {
53 16384, 18432, 20480, 22528, 24576, 26624, 28672, 30720, 32768}; // <Q15>
54
VPMDeflickering()55 VPMDeflickering::VPMDeflickering() {
56 Reset();
57 }
58
~VPMDeflickering()59 VPMDeflickering::~VPMDeflickering() {}
60
Reset()61 void 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
ProcessFrame(VideoFrame * frame,VideoProcessing::FrameStats * stats)84 int32_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 */
PreDetection(const uint32_t timestamp,const VideoProcessing::FrameStats & stats)253 int32_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 */
DetectFlicker()321 int32_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