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
VPMDeflickering()54 VPMDeflickering::VPMDeflickering()
55 : id_(0) {
56 Reset();
57 }
58
~VPMDeflickering()59 VPMDeflickering::~VPMDeflickering() {}
60
ChangeUniqueId(const int32_t id)61 int32_t VPMDeflickering::ChangeUniqueId(const int32_t id) {
62 id_ = id;
63 return 0;
64 }
65
Reset()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
ProcessFrame(I420VideoFrame * frame,VideoProcessingModule::FrameStats * stats)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 */
PreDetection(const uint32_t timestamp,const VideoProcessingModule::FrameStats & stats)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 */
DetectFlicker()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
404