| OLD | NEW |
|---|
| (Empty) |
| 1 /* | |
| 2 * Copyright (c) 2012 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/audio_processing/utility/delay_estimator.h" | |
| 12 | |
| 13 #include <assert.h> | |
| 14 #include <stdlib.h> | |
| 15 #include <string.h> | |
| 16 | |
| 17 // Number of right shifts for scaling is linearly depending on number of bits in | |
| 18 // the far-end binary spectrum. | |
| 19 static const int kShiftsAtZero = 13; // Right shifts at zero binary spectrum. | |
| 20 static const int kShiftsLinearSlope = 3; | |
| 21 | |
| 22 static const int32_t kProbabilityOffset = 1024; // 2 in Q9. | |
| 23 static const int32_t kProbabilityLowerLimit = 8704; // 17 in Q9. | |
| 24 static const int32_t kProbabilityMinSpread = 2816; // 5.5 in Q9. | |
| 25 | |
| 26 // Robust validation settings | |
| 27 static const float kHistogramMax = 3000.f; | |
| 28 static const float kLastHistogramMax = 250.f; | |
| 29 static const float kMinHistogramThreshold = 1.5f; | |
| 30 static const int kMinRequiredHits = 10; | |
| 31 static const int kMaxHitsWhenPossiblyNonCausal = 10; | |
| 32 static const int kMaxHitsWhenPossiblyCausal = 1000; | |
| 33 static const float kQ14Scaling = 1.f / (1 << 14); // Scaling by 2^14 to get Q0. | |
| 34 static const float kFractionSlope = 0.05f; | |
| 35 static const float kMinFractionWhenPossiblyCausal = 0.5f; | |
| 36 static const float kMinFractionWhenPossiblyNonCausal = 0.25f; | |
| 37 | |
| 38 // Counts and returns number of bits of a 32-bit word. | |
| 39 static int BitCount(uint32_t u32) { | |
| 40 uint32_t tmp = u32 - ((u32 >> 1) & 033333333333) - | |
| 41 ((u32 >> 2) & 011111111111); | |
| 42 tmp = ((tmp + (tmp >> 3)) & 030707070707); | |
| 43 tmp = (tmp + (tmp >> 6)); | |
| 44 tmp = (tmp + (tmp >> 12) + (tmp >> 24)) & 077; | |
| 45 | |
| 46 return ((int) tmp); | |
| 47 } | |
| 48 | |
| 49 // Compares the |binary_vector| with all rows of the |binary_matrix| and counts | |
| 50 // per row the number of times they have the same value. | |
| 51 // | |
| 52 // Inputs: | |
| 53 // - binary_vector : binary "vector" stored in a long | |
| 54 // - binary_matrix : binary "matrix" stored as a vector of long | |
| 55 // - matrix_size : size of binary "matrix" | |
| 56 // | |
| 57 // Output: | |
| 58 // - bit_counts : "Vector" stored as a long, containing for each | |
| 59 // row the number of times the matrix row and the | |
| 60 // input vector have the same value | |
| 61 // | |
| 62 static void BitCountComparison(uint32_t binary_vector, | |
| 63 const uint32_t* binary_matrix, | |
| 64 int matrix_size, | |
| 65 int32_t* bit_counts) { | |
| 66 int n = 0; | |
| 67 | |
| 68 // Compare |binary_vector| with all rows of the |binary_matrix| | |
| 69 for (; n < matrix_size; n++) { | |
| 70 bit_counts[n] = (int32_t) BitCount(binary_vector ^ binary_matrix[n]); | |
| 71 } | |
| 72 } | |
| 73 | |
| 74 // Collects necessary statistics for the HistogramBasedValidation(). This | |
| 75 // function has to be called prior to calling HistogramBasedValidation(). The | |
| 76 // statistics updated and used by the HistogramBasedValidation() are: | |
| 77 // 1. the number of |candidate_hits|, which states for how long we have had the | |
| 78 // same |candidate_delay| | |
| 79 // 2. the |histogram| of candidate delays over time. This histogram is | |
| 80 // weighted with respect to a reliability measure and time-varying to cope | |
| 81 // with possible delay shifts. | |
| 82 // For further description see commented code. | |
| 83 // | |
| 84 // Inputs: | |
| 85 // - candidate_delay : The delay to validate. | |
| 86 // - valley_depth_q14 : The cost function has a valley/minimum at the | |
| 87 // |candidate_delay| location. |valley_depth_q14| is the | |
| 88 // cost function difference between the minimum and | |
| 89 // maximum locations. The value is in the Q14 domain. | |
| 90 // - valley_level_q14 : Is the cost function value at the minimum, in Q14. | |
| 91 static void UpdateRobustValidationStatistics(BinaryDelayEstimator* self, | |
| 92 int candidate_delay, | |
| 93 int32_t valley_depth_q14, | |
| 94 int32_t valley_level_q14) { | |
| 95 const float valley_depth = valley_depth_q14 * kQ14Scaling; | |
| 96 float decrease_in_last_set = valley_depth; | |
| 97 const int max_hits_for_slow_change = (candidate_delay < self->last_delay) ? | |
| 98 kMaxHitsWhenPossiblyNonCausal : kMaxHitsWhenPossiblyCausal; | |
| 99 int i = 0; | |
| 100 | |
| 101 assert(self->history_size == self->farend->history_size); | |
| 102 // Reset |candidate_hits| if we have a new candidate. | |
| 103 if (candidate_delay != self->last_candidate_delay) { | |
| 104 self->candidate_hits = 0; | |
| 105 self->last_candidate_delay = candidate_delay; | |
| 106 } | |
| 107 self->candidate_hits++; | |
| 108 | |
| 109 // The |histogram| is updated differently across the bins. | |
| 110 // 1. The |candidate_delay| histogram bin is increased with the | |
| 111 // |valley_depth|, which is a simple measure of how reliable the | |
| 112 // |candidate_delay| is. The histogram is not increased above | |
| 113 // |kHistogramMax|. | |
| 114 self->histogram[candidate_delay] += valley_depth; | |
| 115 if (self->histogram[candidate_delay] > kHistogramMax) { | |
| 116 self->histogram[candidate_delay] = kHistogramMax; | |
| 117 } | |
| 118 // 2. The histogram bins in the neighborhood of |candidate_delay| are | |
| 119 // unaffected. The neighborhood is defined as x + {-2, -1, 0, 1}. | |
| 120 // 3. The histogram bins in the neighborhood of |last_delay| are decreased | |
| 121 // with |decrease_in_last_set|. This value equals the difference between | |
| 122 // the cost function values at the locations |candidate_delay| and | |
| 123 // |last_delay| until we reach |max_hits_for_slow_change| consecutive hits | |
| 124 // at the |candidate_delay|. If we exceed this amount of hits the | |
| 125 // |candidate_delay| is a "potential" candidate and we start decreasing | |
| 126 // these histogram bins more rapidly with |valley_depth|. | |
| 127 if (self->candidate_hits < max_hits_for_slow_change) { | |
| 128 decrease_in_last_set = (self->mean_bit_counts[self->compare_delay] - | |
| 129 valley_level_q14) * kQ14Scaling; | |
| 130 } | |
| 131 // 4. All other bins are decreased with |valley_depth|. | |
| 132 // TODO(bjornv): Investigate how to make this loop more efficient. Split up | |
| 133 // the loop? Remove parts that doesn't add too much. | |
| 134 for (i = 0; i < self->history_size; ++i) { | |
| 135 int is_in_last_set = (i >= self->last_delay - 2) && | |
| 136 (i <= self->last_delay + 1) && (i != candidate_delay); | |
| 137 int is_in_candidate_set = (i >= candidate_delay - 2) && | |
| 138 (i <= candidate_delay + 1); | |
| 139 self->histogram[i] -= decrease_in_last_set * is_in_last_set + | |
| 140 valley_depth * (!is_in_last_set && !is_in_candidate_set); | |
| 141 // 5. No histogram bin can go below 0. | |
| 142 if (self->histogram[i] < 0) { | |
| 143 self->histogram[i] = 0; | |
| 144 } | |
| 145 } | |
| 146 } | |
| 147 | |
| 148 // Validates the |candidate_delay|, estimated in WebRtc_ProcessBinarySpectrum(), | |
| 149 // based on a mix of counting concurring hits with a modified histogram | |
| 150 // of recent delay estimates. In brief a candidate is valid (returns 1) if it | |
| 151 // is the most likely according to the histogram. There are a couple of | |
| 152 // exceptions that are worth mentioning: | |
| 153 // 1. If the |candidate_delay| < |last_delay| it can be that we are in a | |
| 154 // non-causal state, breaking a possible echo control algorithm. Hence, we | |
| 155 // open up for a quicker change by allowing the change even if the | |
| 156 // |candidate_delay| is not the most likely one according to the histogram. | |
| 157 // 2. There's a minimum number of hits (kMinRequiredHits) and the histogram | |
| 158 // value has to reached a minimum (kMinHistogramThreshold) to be valid. | |
| 159 // 3. The action is also depending on the filter length used for echo control. | |
| 160 // If the delay difference is larger than what the filter can capture, we | |
| 161 // also move quicker towards a change. | |
| 162 // For further description see commented code. | |
| 163 // | |
| 164 // Input: | |
| 165 // - candidate_delay : The delay to validate. | |
| 166 // | |
| 167 // Return value: | |
| 168 // - is_histogram_valid : 1 - The |candidate_delay| is valid. | |
| 169 // 0 - Otherwise. | |
| 170 static int HistogramBasedValidation(const BinaryDelayEstimator* self, | |
| 171 int candidate_delay) { | |
| 172 float fraction = 1.f; | |
| 173 float histogram_threshold = self->histogram[self->compare_delay]; | |
| 174 const int delay_difference = candidate_delay - self->last_delay; | |
| 175 int is_histogram_valid = 0; | |
| 176 | |
| 177 // The histogram based validation of |candidate_delay| is done by comparing | |
| 178 // the |histogram| at bin |candidate_delay| with a |histogram_threshold|. | |
| 179 // This |histogram_threshold| equals a |fraction| of the |histogram| at bin | |
| 180 // |last_delay|. The |fraction| is a piecewise linear function of the | |
| 181 // |delay_difference| between the |candidate_delay| and the |last_delay| | |
| 182 // allowing for a quicker move if | |
| 183 // i) a potential echo control filter can not handle these large differences. | |
| 184 // ii) keeping |last_delay| instead of updating to |candidate_delay| could | |
| 185 // force an echo control into a non-causal state. | |
| 186 // We further require the histogram to have reached a minimum value of | |
| 187 // |kMinHistogramThreshold|. In addition, we also require the number of | |
| 188 // |candidate_hits| to be more than |kMinRequiredHits| to remove spurious | |
| 189 // values. | |
| 190 | |
| 191 // Calculate a comparison histogram value (|histogram_threshold|) that is | |
| 192 // depending on the distance between the |candidate_delay| and |last_delay|. | |
| 193 // TODO(bjornv): How much can we gain by turning the fraction calculation | |
| 194 // into tables? | |
| 195 if (delay_difference > self->allowed_offset) { | |
| 196 fraction = 1.f - kFractionSlope * (delay_difference - self->allowed_offset); | |
| 197 fraction = (fraction > kMinFractionWhenPossiblyCausal ? fraction : | |
| 198 kMinFractionWhenPossiblyCausal); | |
| 199 } else if (delay_difference < 0) { | |
| 200 fraction = kMinFractionWhenPossiblyNonCausal - | |
| 201 kFractionSlope * delay_difference; | |
| 202 fraction = (fraction > 1.f ? 1.f : fraction); | |
| 203 } | |
| 204 histogram_threshold *= fraction; | |
| 205 histogram_threshold = (histogram_threshold > kMinHistogramThreshold ? | |
| 206 histogram_threshold : kMinHistogramThreshold); | |
| 207 | |
| 208 is_histogram_valid = | |
| 209 (self->histogram[candidate_delay] >= histogram_threshold) && | |
| 210 (self->candidate_hits > kMinRequiredHits); | |
| 211 | |
| 212 return is_histogram_valid; | |
| 213 } | |
| 214 | |
| 215 // Performs a robust validation of the |candidate_delay| estimated in | |
| 216 // WebRtc_ProcessBinarySpectrum(). The algorithm takes the | |
| 217 // |is_instantaneous_valid| and the |is_histogram_valid| and combines them | |
| 218 // into a robust validation. The HistogramBasedValidation() has to be called | |
| 219 // prior to this call. | |
| 220 // For further description on how the combination is done, see commented code. | |
| 221 // | |
| 222 // Inputs: | |
| 223 // - candidate_delay : The delay to validate. | |
| 224 // - is_instantaneous_valid : The instantaneous validation performed in | |
| 225 // WebRtc_ProcessBinarySpectrum(). | |
| 226 // - is_histogram_valid : The histogram based validation. | |
| 227 // | |
| 228 // Return value: | |
| 229 // - is_robust : 1 - The candidate_delay is valid according to a | |
| 230 // combination of the two inputs. | |
| 231 // : 0 - Otherwise. | |
| 232 static int RobustValidation(const BinaryDelayEstimator* self, | |
| 233 int candidate_delay, | |
| 234 int is_instantaneous_valid, | |
| 235 int is_histogram_valid) { | |
| 236 int is_robust = 0; | |
| 237 | |
| 238 // The final robust validation is based on the two algorithms; 1) the | |
| 239 // |is_instantaneous_valid| and 2) the histogram based with result stored in | |
| 240 // |is_histogram_valid|. | |
| 241 // i) Before we actually have a valid estimate (|last_delay| == -2), we say | |
| 242 // a candidate is valid if either algorithm states so | |
| 243 // (|is_instantaneous_valid| OR |is_histogram_valid|). | |
| 244 is_robust = (self->last_delay < 0) && | |
| 245 (is_instantaneous_valid || is_histogram_valid); | |
| 246 // ii) Otherwise, we need both algorithms to be certain | |
| 247 // (|is_instantaneous_valid| AND |is_histogram_valid|) | |
| 248 is_robust |= is_instantaneous_valid && is_histogram_valid; | |
| 249 // iii) With one exception, i.e., the histogram based algorithm can overrule | |
| 250 // the instantaneous one if |is_histogram_valid| = 1 and the histogram | |
| 251 // is significantly strong. | |
| 252 is_robust |= is_histogram_valid && | |
| 253 (self->histogram[candidate_delay] > self->last_delay_histogram); | |
| 254 | |
| 255 return is_robust; | |
| 256 } | |
| 257 | |
| 258 void WebRtc_FreeBinaryDelayEstimatorFarend(BinaryDelayEstimatorFarend* self) { | |
| 259 | |
| 260 if (self == NULL) { | |
| 261 return; | |
| 262 } | |
| 263 | |
| 264 free(self->binary_far_history); | |
| 265 self->binary_far_history = NULL; | |
| 266 | |
| 267 free(self->far_bit_counts); | |
| 268 self->far_bit_counts = NULL; | |
| 269 | |
| 270 free(self); | |
| 271 } | |
| 272 | |
| 273 BinaryDelayEstimatorFarend* WebRtc_CreateBinaryDelayEstimatorFarend( | |
| 274 int history_size) { | |
| 275 BinaryDelayEstimatorFarend* self = NULL; | |
| 276 | |
| 277 if (history_size > 1) { | |
| 278 // Sanity conditions fulfilled. | |
| 279 self = malloc(sizeof(BinaryDelayEstimatorFarend)); | |
| 280 } | |
| 281 if (self == NULL) { | |
| 282 return NULL; | |
| 283 } | |
| 284 | |
| 285 self->history_size = 0; | |
| 286 self->binary_far_history = NULL; | |
| 287 self->far_bit_counts = NULL; | |
| 288 if (WebRtc_AllocateFarendBufferMemory(self, history_size) == 0) { | |
| 289 WebRtc_FreeBinaryDelayEstimatorFarend(self); | |
| 290 self = NULL; | |
| 291 } | |
| 292 return self; | |
| 293 } | |
| 294 | |
| 295 int WebRtc_AllocateFarendBufferMemory(BinaryDelayEstimatorFarend* self, | |
| 296 int history_size) { | |
| 297 assert(self != NULL); | |
| 298 // (Re-)Allocate memory for history buffers. | |
| 299 self->binary_far_history = | |
| 300 realloc(self->binary_far_history, | |
| 301 history_size * sizeof(*self->binary_far_history)); | |
| 302 self->far_bit_counts = realloc(self->far_bit_counts, | |
| 303 history_size * sizeof(*self->far_bit_counts)); | |
| 304 if ((self->binary_far_history == NULL) || (self->far_bit_counts == NULL)) { | |
| 305 history_size = 0; | |
| 306 } | |
| 307 // Fill with zeros if we have expanded the buffers. | |
| 308 if (history_size > self->history_size) { | |
| 309 int size_diff = history_size - self->history_size; | |
| 310 memset(&self->binary_far_history[self->history_size], | |
| 311 0, | |
| 312 sizeof(*self->binary_far_history) * size_diff); | |
| 313 memset(&self->far_bit_counts[self->history_size], | |
| 314 0, | |
| 315 sizeof(*self->far_bit_counts) * size_diff); | |
| 316 } | |
| 317 self->history_size = history_size; | |
| 318 | |
| 319 return self->history_size; | |
| 320 } | |
| 321 | |
| 322 void WebRtc_InitBinaryDelayEstimatorFarend(BinaryDelayEstimatorFarend* self) { | |
| 323 assert(self != NULL); | |
| 324 memset(self->binary_far_history, 0, sizeof(uint32_t) * self->history_size); | |
| 325 memset(self->far_bit_counts, 0, sizeof(int) * self->history_size); | |
| 326 } | |
| 327 | |
| 328 void WebRtc_SoftResetBinaryDelayEstimatorFarend( | |
| 329 BinaryDelayEstimatorFarend* self, int delay_shift) { | |
| 330 int abs_shift = abs(delay_shift); | |
| 331 int shift_size = 0; | |
| 332 int dest_index = 0; | |
| 333 int src_index = 0; | |
| 334 int padding_index = 0; | |
| 335 | |
| 336 assert(self != NULL); | |
| 337 shift_size = self->history_size - abs_shift; | |
| 338 assert(shift_size > 0); | |
| 339 if (delay_shift == 0) { | |
| 340 return; | |
| 341 } else if (delay_shift > 0) { | |
| 342 dest_index = abs_shift; | |
| 343 } else if (delay_shift < 0) { | |
| 344 src_index = abs_shift; | |
| 345 padding_index = shift_size; | |
| 346 } | |
| 347 | |
| 348 // Shift and zero pad buffers. | |
| 349 memmove(&self->binary_far_history[dest_index], | |
| 350 &self->binary_far_history[src_index], | |
| 351 sizeof(*self->binary_far_history) * shift_size); | |
| 352 memset(&self->binary_far_history[padding_index], 0, | |
| 353 sizeof(*self->binary_far_history) * abs_shift); | |
| 354 memmove(&self->far_bit_counts[dest_index], | |
| 355 &self->far_bit_counts[src_index], | |
| 356 sizeof(*self->far_bit_counts) * shift_size); | |
| 357 memset(&self->far_bit_counts[padding_index], 0, | |
| 358 sizeof(*self->far_bit_counts) * abs_shift); | |
| 359 } | |
| 360 | |
| 361 void WebRtc_AddBinaryFarSpectrum(BinaryDelayEstimatorFarend* handle, | |
| 362 uint32_t binary_far_spectrum) { | |
| 363 assert(handle != NULL); | |
| 364 // Shift binary spectrum history and insert current |binary_far_spectrum|. | |
| 365 memmove(&(handle->binary_far_history[1]), &(handle->binary_far_history[0]), | |
| 366 (handle->history_size - 1) * sizeof(uint32_t)); | |
| 367 handle->binary_far_history[0] = binary_far_spectrum; | |
| 368 | |
| 369 // Shift history of far-end binary spectrum bit counts and insert bit count | |
| 370 // of current |binary_far_spectrum|. | |
| 371 memmove(&(handle->far_bit_counts[1]), &(handle->far_bit_counts[0]), | |
| 372 (handle->history_size - 1) * sizeof(int)); | |
| 373 handle->far_bit_counts[0] = BitCount(binary_far_spectrum); | |
| 374 } | |
| 375 | |
| 376 void WebRtc_FreeBinaryDelayEstimator(BinaryDelayEstimator* self) { | |
| 377 | |
| 378 if (self == NULL) { | |
| 379 return; | |
| 380 } | |
| 381 | |
| 382 free(self->mean_bit_counts); | |
| 383 self->mean_bit_counts = NULL; | |
| 384 | |
| 385 free(self->bit_counts); | |
| 386 self->bit_counts = NULL; | |
| 387 | |
| 388 free(self->binary_near_history); | |
| 389 self->binary_near_history = NULL; | |
| 390 | |
| 391 free(self->histogram); | |
| 392 self->histogram = NULL; | |
| 393 | |
| 394 // BinaryDelayEstimator does not have ownership of |farend|, hence we do not | |
| 395 // free the memory here. That should be handled separately by the user. | |
| 396 self->farend = NULL; | |
| 397 | |
| 398 free(self); | |
| 399 } | |
| 400 | |
| 401 BinaryDelayEstimator* WebRtc_CreateBinaryDelayEstimator( | |
| 402 BinaryDelayEstimatorFarend* farend, int max_lookahead) { | |
| 403 BinaryDelayEstimator* self = NULL; | |
| 404 | |
| 405 if ((farend != NULL) && (max_lookahead >= 0)) { | |
| 406 // Sanity conditions fulfilled. | |
| 407 self = malloc(sizeof(BinaryDelayEstimator)); | |
| 408 } | |
| 409 if (self == NULL) { | |
| 410 return NULL; | |
| 411 } | |
| 412 | |
| 413 self->farend = farend; | |
| 414 self->near_history_size = max_lookahead + 1; | |
| 415 self->history_size = 0; | |
| 416 self->robust_validation_enabled = 0; // Disabled by default. | |
| 417 self->allowed_offset = 0; | |
| 418 | |
| 419 self->lookahead = max_lookahead; | |
| 420 | |
| 421 // Allocate memory for spectrum and history buffers. | |
| 422 self->mean_bit_counts = NULL; | |
| 423 self->bit_counts = NULL; | |
| 424 self->histogram = NULL; | |
| 425 self->binary_near_history = | |
| 426 malloc((max_lookahead + 1) * sizeof(*self->binary_near_history)); | |
| 427 if (self->binary_near_history == NULL || | |
| 428 WebRtc_AllocateHistoryBufferMemory(self, farend->history_size) == 0) { | |
| 429 WebRtc_FreeBinaryDelayEstimator(self); | |
| 430 self = NULL; | |
| 431 } | |
| 432 | |
| 433 return self; | |
| 434 } | |
| 435 | |
| 436 int WebRtc_AllocateHistoryBufferMemory(BinaryDelayEstimator* self, | |
| 437 int history_size) { | |
| 438 BinaryDelayEstimatorFarend* far = self->farend; | |
| 439 // (Re-)Allocate memory for spectrum and history buffers. | |
| 440 if (history_size != far->history_size) { | |
| 441 // Only update far-end buffers if we need. | |
| 442 history_size = WebRtc_AllocateFarendBufferMemory(far, history_size); | |
| 443 } | |
| 444 // The extra array element in |mean_bit_counts| and |histogram| is a dummy | |
| 445 // element only used while |last_delay| == -2, i.e., before we have a valid | |
| 446 // estimate. | |
| 447 self->mean_bit_counts = | |
| 448 realloc(self->mean_bit_counts, | |
| 449 (history_size + 1) * sizeof(*self->mean_bit_counts)); | |
| 450 self->bit_counts = | |
| 451 realloc(self->bit_counts, history_size * sizeof(*self->bit_counts)); | |
| 452 self->histogram = | |
| 453 realloc(self->histogram, (history_size + 1) * sizeof(*self->histogram)); | |
| 454 | |
| 455 if ((self->mean_bit_counts == NULL) || | |
| 456 (self->bit_counts == NULL) || | |
| 457 (self->histogram == NULL)) { | |
| 458 history_size = 0; | |
| 459 } | |
| 460 // Fill with zeros if we have expanded the buffers. | |
| 461 if (history_size > self->history_size) { | |
| 462 int size_diff = history_size - self->history_size; | |
| 463 memset(&self->mean_bit_counts[self->history_size], | |
| 464 0, | |
| 465 sizeof(*self->mean_bit_counts) * size_diff); | |
| 466 memset(&self->bit_counts[self->history_size], | |
| 467 0, | |
| 468 sizeof(*self->bit_counts) * size_diff); | |
| 469 memset(&self->histogram[self->history_size], | |
| 470 0, | |
| 471 sizeof(*self->histogram) * size_diff); | |
| 472 } | |
| 473 self->history_size = history_size; | |
| 474 | |
| 475 return self->history_size; | |
| 476 } | |
| 477 | |
| 478 void WebRtc_InitBinaryDelayEstimator(BinaryDelayEstimator* self) { | |
| 479 int i = 0; | |
| 480 assert(self != NULL); | |
| 481 | |
| 482 memset(self->bit_counts, 0, sizeof(int32_t) * self->history_size); | |
| 483 memset(self->binary_near_history, | |
| 484 0, | |
| 485 sizeof(uint32_t) * self->near_history_size); | |
| 486 for (i = 0; i <= self->history_size; ++i) { | |
| 487 self->mean_bit_counts[i] = (20 << 9); // 20 in Q9. | |
| 488 self->histogram[i] = 0.f; | |
| 489 } | |
| 490 self->minimum_probability = kMaxBitCountsQ9; // 32 in Q9. | |
| 491 self->last_delay_probability = (int) kMaxBitCountsQ9; // 32 in Q9. | |
| 492 | |
| 493 // Default return value if we're unable to estimate. -1 is used for errors. | |
| 494 self->last_delay = -2; | |
| 495 | |
| 496 self->last_candidate_delay = -2; | |
| 497 self->compare_delay = self->history_size; | |
| 498 self->candidate_hits = 0; | |
| 499 self->last_delay_histogram = 0.f; | |
| 500 } | |
| 501 | |
| 502 int WebRtc_SoftResetBinaryDelayEstimator(BinaryDelayEstimator* self, | |
| 503 int delay_shift) { | |
| 504 int lookahead = 0; | |
| 505 assert(self != NULL); | |
| 506 lookahead = self->lookahead; | |
| 507 self->lookahead -= delay_shift; | |
| 508 if (self->lookahead < 0) { | |
| 509 self->lookahead = 0; | |
| 510 } | |
| 511 if (self->lookahead > self->near_history_size - 1) { | |
| 512 self->lookahead = self->near_history_size - 1; | |
| 513 } | |
| 514 return lookahead - self->lookahead; | |
| 515 } | |
| 516 | |
| 517 int WebRtc_ProcessBinarySpectrum(BinaryDelayEstimator* self, | |
| 518 uint32_t binary_near_spectrum) { | |
| 519 int i = 0; | |
| 520 int candidate_delay = -1; | |
| 521 int valid_candidate = 0; | |
| 522 | |
| 523 int32_t value_best_candidate = kMaxBitCountsQ9; | |
| 524 int32_t value_worst_candidate = 0; | |
| 525 int32_t valley_depth = 0; | |
| 526 | |
| 527 assert(self != NULL); | |
| 528 if (self->farend->history_size != self->history_size) { | |
| 529 // Non matching history sizes. | |
| 530 return -1; | |
| 531 } | |
| 532 if (self->near_history_size > 1) { | |
| 533 // If we apply lookahead, shift near-end binary spectrum history. Insert | |
| 534 // current |binary_near_spectrum| and pull out the delayed one. | |
| 535 memmove(&(self->binary_near_history[1]), &(self->binary_near_history[0]), | |
| 536 (self->near_history_size - 1) * sizeof(uint32_t)); | |
| 537 self->binary_near_history[0] = binary_near_spectrum; | |
| 538 binary_near_spectrum = self->binary_near_history[self->lookahead]; | |
| 539 } | |
| 540 | |
| 541 // Compare with delayed spectra and store the |bit_counts| for each delay. | |
| 542 BitCountComparison(binary_near_spectrum, self->farend->binary_far_history, | |
| 543 self->history_size, self->bit_counts); | |
| 544 | |
| 545 // Update |mean_bit_counts|, which is the smoothed version of |bit_counts|. | |
| 546 for (i = 0; i < self->history_size; i++) { | |
| 547 // |bit_counts| is constrained to [0, 32], meaning we can smooth with a | |
| 548 // factor up to 2^26. We use Q9. | |
| 549 int32_t bit_count = (self->bit_counts[i] << 9); // Q9. | |
| 550 | |
| 551 // Update |mean_bit_counts| only when far-end signal has something to | |
| 552 // contribute. If |far_bit_counts| is zero the far-end signal is weak and | |
| 553 // we likely have a poor echo condition, hence don't update. | |
| 554 if (self->farend->far_bit_counts[i] > 0) { | |
| 555 // Make number of right shifts piecewise linear w.r.t. |far_bit_counts|. | |
| 556 int shifts = kShiftsAtZero; | |
| 557 shifts -= (kShiftsLinearSlope * self->farend->far_bit_counts[i]) >> 4; | |
| 558 WebRtc_MeanEstimatorFix(bit_count, shifts, &(self->mean_bit_counts[i])); | |
| 559 } | |
| 560 } | |
| 561 | |
| 562 // Find |candidate_delay|, |value_best_candidate| and |value_worst_candidate| | |
| 563 // of |mean_bit_counts|. | |
| 564 for (i = 0; i < self->history_size; i++) { | |
| 565 if (self->mean_bit_counts[i] < value_best_candidate) { | |
| 566 value_best_candidate = self->mean_bit_counts[i]; | |
| 567 candidate_delay = i; | |
| 568 } | |
| 569 if (self->mean_bit_counts[i] > value_worst_candidate) { | |
| 570 value_worst_candidate = self->mean_bit_counts[i]; | |
| 571 } | |
| 572 } | |
| 573 valley_depth = value_worst_candidate - value_best_candidate; | |
| 574 | |
| 575 // The |value_best_candidate| is a good indicator on the probability of | |
| 576 // |candidate_delay| being an accurate delay (a small |value_best_candidate| | |
| 577 // means a good binary match). In the following sections we make a decision | |
| 578 // whether to update |last_delay| or not. | |
| 579 // 1) If the difference bit counts between the best and the worst delay | |
| 580 // candidates is too small we consider the situation to be unreliable and | |
| 581 // don't update |last_delay|. | |
| 582 // 2) If the situation is reliable we update |last_delay| if the value of the | |
| 583 // best candidate delay has a value less than | |
| 584 // i) an adaptive threshold |minimum_probability|, or | |
| 585 // ii) this corresponding value |last_delay_probability|, but updated at | |
| 586 // this time instant. | |
| 587 | |
| 588 // Update |minimum_probability|. | |
| 589 if ((self->minimum_probability > kProbabilityLowerLimit) && | |
| 590 (valley_depth > kProbabilityMinSpread)) { | |
| 591 // The "hard" threshold can't be lower than 17 (in Q9). | |
| 592 // The valley in the curve also has to be distinct, i.e., the | |
| 593 // difference between |value_worst_candidate| and |value_best_candidate| has | |
| 594 // to be large enough. | |
| 595 int32_t threshold = value_best_candidate + kProbabilityOffset; | |
| 596 if (threshold < kProbabilityLowerLimit) { | |
| 597 threshold = kProbabilityLowerLimit; | |
| 598 } | |
| 599 if (self->minimum_probability > threshold) { | |
| 600 self->minimum_probability = threshold; | |
| 601 } | |
| 602 } | |
| 603 // Update |last_delay_probability|. | |
| 604 // We use a Markov type model, i.e., a slowly increasing level over time. | |
| 605 self->last_delay_probability++; | |
| 606 // Validate |candidate_delay|. We have a reliable instantaneous delay | |
| 607 // estimate if | |
| 608 // 1) The valley is distinct enough (|valley_depth| > |kProbabilityOffset|) | |
| 609 // and | |
| 610 // 2) The depth of the valley is deep enough | |
| 611 // (|value_best_candidate| < |minimum_probability|) | |
| 612 // and deeper than the best estimate so far | |
| 613 // (|value_best_candidate| < |last_delay_probability|) | |
| 614 valid_candidate = ((valley_depth > kProbabilityOffset) && | |
| 615 ((value_best_candidate < self->minimum_probability) || | |
| 616 (value_best_candidate < self->last_delay_probability))); | |
| 617 | |
| 618 UpdateRobustValidationStatistics(self, candidate_delay, valley_depth, | |
| 619 value_best_candidate); | |
| 620 if (self->robust_validation_enabled) { | |
| 621 int is_histogram_valid = HistogramBasedValidation(self, candidate_delay); | |
| 622 valid_candidate = RobustValidation(self, candidate_delay, valid_candidate, | |
| 623 is_histogram_valid); | |
| 624 | |
| 625 } | |
| 626 if (valid_candidate) { | |
| 627 if (candidate_delay != self->last_delay) { | |
| 628 self->last_delay_histogram = | |
| 629 (self->histogram[candidate_delay] > kLastHistogramMax ? | |
| 630 kLastHistogramMax : self->histogram[candidate_delay]); | |
| 631 // Adjust the histogram if we made a change to |last_delay|, though it was | |
| 632 // not the most likely one according to the histogram. | |
| 633 if (self->histogram[candidate_delay] < | |
| 634 self->histogram[self->compare_delay]) { | |
| 635 self->histogram[self->compare_delay] = self->histogram[candidate_delay]; | |
| 636 } | |
| 637 } | |
| 638 self->last_delay = candidate_delay; | |
| 639 if (value_best_candidate < self->last_delay_probability) { | |
| 640 self->last_delay_probability = value_best_candidate; | |
| 641 } | |
| 642 self->compare_delay = self->last_delay; | |
| 643 } | |
| 644 | |
| 645 return self->last_delay; | |
| 646 } | |
| 647 | |
| 648 int WebRtc_binary_last_delay(BinaryDelayEstimator* self) { | |
| 649 assert(self != NULL); | |
| 650 return self->last_delay; | |
| 651 } | |
| 652 | |
| 653 float WebRtc_binary_last_delay_quality(BinaryDelayEstimator* self) { | |
| 654 float quality = 0; | |
| 655 assert(self != NULL); | |
| 656 | |
| 657 if (self->robust_validation_enabled) { | |
| 658 // Simply a linear function of the histogram height at delay estimate. | |
| 659 quality = self->histogram[self->compare_delay] / kHistogramMax; | |
| 660 } else { | |
| 661 // Note that |last_delay_probability| states how deep the minimum of the | |
| 662 // cost function is, so it is rather an error probability. | |
| 663 quality = (float) (kMaxBitCountsQ9 - self->last_delay_probability) / | |
| 664 kMaxBitCountsQ9; | |
| 665 if (quality < 0) { | |
| 666 quality = 0; | |
| 667 } | |
| 668 } | |
| 669 return quality; | |
| 670 } | |
| 671 | |
| 672 void WebRtc_MeanEstimatorFix(int32_t new_value, | |
| 673 int factor, | |
| 674 int32_t* mean_value) { | |
| 675 int32_t diff = new_value - *mean_value; | |
| 676 | |
| 677 // mean_new = mean_value + ((new_value - mean_value) >> factor); | |
| 678 if (diff < 0) { | |
| 679 diff = -((-diff) >> factor); | |
| 680 } else { | |
| 681 diff = (diff >> factor); | |
| 682 } | |
| 683 *mean_value += diff; | |
| 684 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1878613002:
Changed the delay estimator to be built using C++ (Closed)
Base URL: https://chromium.googlesource.com/external/webrtc.git@master