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 404