Add algorithm for Residual Echo Detector.

webrtc/modules/audio_processing/echo_detector/echo_detector.cc

 /*
  *  Copyright (c) 2016 The WebRTC project authors. All Rights Reserved.
  *
  *  Use of this source code is governed by a BSD-style license
  *  that can be found in the LICENSE file in the root of the source
  *  tree. An additional intellectual property rights grant can be found
  *  in the file PATENTS.  All contributing project authors may
  *  be found in the AUTHORS file in the root of the source tree.
  */
 
 #include "webrtc/modules/audio_processing/echo_detector/echo_detector.h"
 
+#include <algorithm>
+#include <numeric>
+
+namespace {
+
+float Power(rtc::ArrayView<const float> input) {
+  return std::inner_product(input.begin(), input.end(), input.begin(), 0.f);
+}
+
+constexpr size_t kLookbackFrames = 650;
+// TODO(ivoc): Verify the size of this buffer.
+constexpr size_t kRenderBufferSize = 30;
+
+}  // namespace
+
 namespace webrtc {
 
-void EchoDetector::BufferFarend(const rtc::ArrayView<const float>& /*farend*/) {
-  // TODO(ivoc): Add implementation.
-  RTC_NOTREACHED();
+EchoDetector::EchoDetector()
+    : render_buffer_(kRenderBufferSize),
+      render_power_(kLookbackFrames),
+      render_power_mean_(kLookbackFrames),
+      render_power_std_dev_(kLookbackFrames),
+      covariances_(kLookbackFrames){};
+
+EchoDetector::~EchoDetector() = default;
+
+void EchoDetector::BufferRender(rtc::ArrayView<const float> render) {
+  if (render_buffer_.Size() == 0) {
+    frames_since_zero_buffer_size_ = 0;
+  } else if (frames_since_zero_buffer_size_ >= kRenderBufferSize) {
+    // This can happen in a few cases: at the start of a call, due to a glitch
+    // or due to clock drift. The excess capture value will be ignored.
+    // TODO(ivoc): Include how often this happens in APM stats.
+    render_buffer_.Pop();
+    frames_since_zero_buffer_size_ = 0;

[hlundin-webrtc, 2016/10/24 00:42:14]

I don't understand the logic of frames_since_zero_buffer_size_. No matter what,
it will always come out as 1 when this method returns, and it is neither read
nor written anywhere else. Confused.

[ivoc, 2016/10/24 15:25:19]

The idea is to count how long ago it was since the buffer was zero. The
reasoning is that in the case of clockdrift, this buffer will never return to
zero (it will slowly fill up), so we can use this as a signal to detect that. 

I don't think it will come out as 1 no matter what: if
frames_since_zero_buffer_size_ is < kRenderBufferSize and the buffer is not
zero, neither the if nor the else-if will be run, and it will simply be
incremented below.

[hlundin-webrtc, 2016/10/27 13:05:48]

Oh, it was an if--elseif statement. I read it as if-else. Mea culpa.

You may want to reconsider the name of the state variable, or comment more in
detail what it is actually counting.

[ivoc, 2016/10/27 13:55:29]

Added more comments in the header, because naming stuff is hard.

+  }
+  ++frames_since_zero_buffer_size_;
+  float power = Power(render);
+  render_buffer_.Push(power);
 }
 
-void EchoDetector::Process(const rtc::ArrayView<const float>& /*nearend*/) {
-  // TODO(ivoc): Add implementation.
-  RTC_NOTREACHED();
+void EchoDetector::Process(rtc::ArrayView<const float> capture) {
+  if (first_process_call_) {
+    // On the first process call (so the start of a call), we must flush the
+    // render buffer, otherwise the render data will be delayed.
+    render_buffer_.Clear();
+    first_process_call_ = false;
+  }
+
+  // Get the next render value.
+  const rtc::Optional<float> buffered_render_power = render_buffer_.Pop();
+  if (!buffered_render_power) {
+    // This can happen in a few cases: at the start of a call, due to a glitch
+    // or due to clock drift. The excess capture value will be ignored.
+    // TODO(ivoc): Include how often this happens in APM stats.
+    return;
+  }
+  // Update the render statistics, and store the statistics in circular buffers.
+  render_statistics_.Update(*buffered_render_power);
+  RTC_DCHECK_LT(next_insertion_index_, kLookbackFrames);
+  render_power_[next_insertion_index_] = *buffered_render_power;
+  render_power_mean_[next_insertion_index_] = render_statistics_.mean();
+  render_power_std_dev_[next_insertion_index_] =
+      render_statistics_.std_deviation();
+
+  // Get the next capture value, update capture statistics and add the relevant
+  // values to the buffers.
+  const float capture_power = Power(capture);
+  capture_statistics_.Update(capture_power);
+  const float capture_mean = capture_statistics_.mean();
+  const float capture_std_deviation = capture_statistics_.std_deviation();
+
+  // Update the covariance values and determine the new echo likelihood.
+  echo_likelihood_ = 0.f;
+  for (size_t delay = 0; delay < covariances_.size(); ++delay) {
+    const size_t read_index =
+        (kLookbackFrames + next_insertion_index_ - delay) % kLookbackFrames;
+    RTC_DCHECK_LT(read_index, render_power_.size());
+    covariances_[delay].Update(capture_power, capture_mean,
+                               capture_std_deviation, render_power_[read_index],
+                               render_power_mean_[read_index],
+                               render_power_std_dev_[read_index]);
+    echo_likelihood_ = std::max(
+        echo_likelihood_, covariances_[delay].normalized_cross_correlation());
+  }
+
+  // Update the next insertion index.
+  ++next_insertion_index_;
+  next_insertion_index_ %= kLookbackFrames;
 }
 
-void EchoDetector::Initialize(int /*sample_rate_hz*/) {
-  // TODO(ivoc): Add implementation.
-  RTC_NOTREACHED();
+void EchoDetector::Initialize() {
+  render_buffer_.Clear();
+  std::fill(render_power_.begin(), render_power_.end(), 0.f);
+  std::fill(render_power_mean_.begin(), render_power_mean_.end(), 0.f);
+  std::fill(render_power_std_dev_.begin(), render_power_std_dev_.end(), 0.f);
+  render_statistics_.Clear();
+  capture_statistics_.Clear();
+  for (auto& cov : covariances_) {
+    cov.Clear();
+  }
+  echo_likelihood_ = 0.f;
+  next_insertion_index_ = 0;
 }
 
 }  // namespace webrtc