Add algorithm for Residual Echo Detector.

webrtc/modules/audio_processing/echo_detector/echo_detector.cc

Index: webrtc/modules/audio_processing/echo_detector/echo_detector.cc
diff --git a/webrtc/modules/audio_processing/echo_detector/echo_detector.cc b/webrtc/modules/audio_processing/echo_detector/echo_detector.cc
index 842be9e2db3a5a999de4dd07c02c40ec41c879db..7608ec1059c452de240d6ff7dbaa5243c2c5a858 100644
--- a/webrtc/modules/audio_processing/echo_detector/echo_detector.cc
+++ b/webrtc/modules/audio_processing/echo_detector/echo_detector.cc
@@ -10,21 +10,114 @@
 
 #include "webrtc/modules/audio_processing/echo_detector/echo_detector.h"
 
+#include <algorithm>
+#include <numeric>
+
+#include "webrtc/base/logging.h"
+
+namespace {
+
+float Power(rtc::ArrayView<const float> input) {
+  return std::inner_product(input.begin(), input.end(), input.begin(), 0.f);
+}
+
+}  // 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;
+
+constexpr size_t EchoDetector::kLookbackFrames;
+constexpr size_t EchoDetector::kRenderBufferSize;
+
+void EchoDetector::BufferRender(rtc::ArrayView<const float> render) {
+  if (render_buffer_.Size() == 0) {
+    render_buffer_zero_ = 0;
+  }
+  if (render_buffer_zero_ >= kRenderBufferSize) {

[peah-webrtc, 2016/10/20 15:08:24]

you can add an else if here, as the latter if-statement will never be true if
the first statement is true.

[ivoc, 2016/10/21 12:21:15]

Done.

+    LOG(LS_ERROR) << "Clockdrift detected in residual echo detector. Ignoring "
+                  << "a render frame.";

[peah-webrtc, 2016/10/20 15:08:24]

Please add to the comment which frame you are ignoring, "the latest" or "the
most recent"

[ivoc, 2016/10/21 12:21:15]

It is actually the oldest frame in the buffer that is being discarded, since the
render buffer is a FIFO queue. I will add it to the log message.

+    render_buffer_.Pop();
+    render_buffer_zero_ = 0;
+  }
+  ++render_buffer_zero_;
+  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 should only happen in case of clock drift. For now we will just

[peah-webrtc, 2016/10/20 15:08:24]

Please update the comment to include that it can also happen initially, or when
there is a glitch, or alternatively change the comment so that it includes that
it could happen otherwise as well, but not in a as a normal case.

[ivoc, 2016/10/21 12:21:15]

Done.

+    // ignore the "extra" capture value.
+    if (!first_process_call_) {
+      // Don't spam error messages before the first process call.
+      LOG(LS_ERROR) << "Clockdrift detected in residual echo detector. "
+                       "Ignoring capture frame.";
+    }
+    return;
+  }
+  // Update the render statistics, and store the .

[peah-webrtc, 2016/10/20 15:08:24]

The comment seems to have been ended in the middle.

[ivoc, 2016/10/21 12:21:15]

Oh, that was sloppy, I fixed it.

+  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(

[peah-webrtc, 2016/10/20 15:08:24]

Do you take any account of the reliability on the likelihood. I.e., in the
initial phase ,e.g., the first frame, it should not be reliable. The same
probably holds for when there has been clock-drift.

[ivoc, 2016/10/21 12:21:15]

That's an interesting idea. I think one additional factor that could indicate
reduced reliability is when both standard deviations are very low. Since the
covariance is divided by the product of the these standard deviations, in cases
where they're both very low, we're providing a substantial gain. I think this
can be caused in cases where both sides are near silent. What do you think is
the best way to keep track of the reliability? Should it be another adaptively
estimated variable that starts at zero and is gradually increased/reduced
depending on things like clock drift, standard deviations etc? 

+        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