Adding audio RepetitionDetector in AudioProcessingModule.

webrtc/modules/audio_processing/repetition_detector.cc

+/*
+ *  Copyright (c) 2015 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/repetition_detector.h"
+
+#include <string.h>  // memset
+
+#include "webrtc/base/checks.h"
+
+namespace webrtc {
+
+namespace {
+static const RepetitionDetector::Pattern kRepetitionPatterns[] = {

[peah-webrtc, 2015/08/12 11:02:54]

Both look_back_range_ and  length_range_ are zero both in the code and the
unittests. Therefore the code corresponding to these is not being exercised and
is untested (at least in this code). Please add active use of that code (by
using nonzero values of the aforementioned variables), both in the unittests and
the detector.

[minyue-webrtc, 2015/08/12 11:32:14]

Maybe not enough but there is a unittest around this, called RangedLookBack.

[peah-webrtc, 2015/08/12 21:05:16]

Sorry, I missed the unit test. Great! 

+    // {id_, look_back_, look_back_range_, length_, length_range_}
+    {0, 10, 0, 10, 0},
+    {1, 100, 0, 100, 0}
+};
+}
+
+RepetitionDetector::RepetitionDetector()
+    : audio_buffer_(nullptr),
+      num_channels_(0),
+      buffer_length_samples_(0),
+      buffer_end_(0) {
+  RegisterRepititionPatterns(kRepetitionPatterns,
+                             sizeof(kRepetitionPatterns) / sizeof (Pattern));
+  CreateBuffer();
+}
+
+RepetitionDetector::~RepetitionDetector() {
+  DeleteBuffer();
+}
+
+
+void RepetitionDetector::RegisterRepititionPatterns(const Pattern* patterns,

[peah-webrtc, 2015/08/12 11:02:54]

Typo, should be RegisterRepetitionPatterns

[minyue-webrtc, 2015/08/12 11:32:14]

Acknowledged.

+                                                    int num_patterns) {
+  int max_look_back = 0;
+  Pattern pattern;
+  for (int idx = 0; idx < num_patterns; idx++) {
+    pattern = patterns[idx];
+    for (int offset = -pattern.look_back_range_;

[peah-webrtc, 2015/08/12 11:02:54]

In the specified patterns, look_back_range_ is set to zero. What is the intended
role of it being nonzero? The number of states, and the complexity depends a lot
on the values for this.

[minyue-webrtc, 2015/08/12 11:32:14]

I think the look_back and length may not be necessarily exact. It may be too
strict if we allow only exact match. But this is disputable.

+        offset <= pattern.look_back_range_; offset++) {
+      states_.push_back(State(pattern.id_, pattern.look_back_ + offset,
+                              pattern.length_, pattern.length_range_));
+    }
+    if (pattern.look_back_ + pattern.look_back_range_ > max_look_back) {
+      max_look_back = pattern.look_back_ + pattern.look_back_range_;
+    }
+  }
+  buffer_length_samples_ = max_look_back;
+}
+
+void RepetitionDetector::ClearRepititionPatterns() {

[peah-webrtc, 2015/08/12 11:02:54]

A typo, should be ClearRepetitionPatterns

[minyue-webrtc, 2015/08/12 11:32:14]

Acknowledged.

+  states_.clear();
+  buffer_length_samples_ = 0;
+}
+
+void RepetitionDetector::CreateBuffer() {
+  if (audio_buffer_) {
+    return;
+  }
+  audio_buffer_ = new int16_t*[num_channels_];
+  for (int ch = 0; ch < num_channels_; ch++) {
+    audio_buffer_[ch] = new int16_t[buffer_length_samples_];
+    memset(audio_buffer_[ch], 0, buffer_length_samples_ * sizeof(int16_t));
+  }
+  buffer_end_ = 0;
+}
+
+void RepetitionDetector::DeleteBuffer() {
+  if (!audio_buffer_) {
+    return;
+  }
+  for (int ch = 0; ch < num_channels_; ch++) {
+    delete[] audio_buffer_[ch];
+  }
+  delete[] audio_buffer_;
+  audio_buffer_ = nullptr;
+}
+
+void RepetitionDetector::Reset(int new_num_channels) {
+  DeleteBuffer();
+  num_channels_ = new_num_channels;
+  CreateBuffer();
+  for (auto& state : states_) {
+    state.count_ = 0;
+  }
+  // We do not reset |occurances_| to be able to count issues that have

[hlundin-webrtc, 2015/08/12 14:12:04]

What is occurances_?

[minyue-webrtc, 2015/08/12 14:20:20]

Sorry. it was a counter, but now removed, since I plan to do one report at a
time.

+  // happened.
+}
+
+void RepetitionDetector::Detect(const int16_t* data, int samples_per_channel,
+                                int num_channels) {
+  DCHECK_GT(states_.size(), 0ul);
+  if (num_channels != num_channels_) {
+    Reset(num_channels);
+  }
+
+  int look_back_pointer;

[hlundin-webrtc, 2015/08/12 14:12:04]

This is not a pointer. Suggest look_back_index or look_back_ix. And declare it
in the for loop instead.

+  int new_buffer_end = buffer_end_;
+  const int16_t* sample = data;
+
+  for (int idx = 0; idx < samples_per_channel; idx++) {

[hlundin-webrtc, 2015/08/12 14:12:04]

This nested for loop and its associated code is very complicated. Shouldn't the
following be enough?

for each offset to check {
  if 0 == memcmp(audio_buffer_[at offset], data, length(data));  // Compare all
channels.
    // We have a match; report it.
}

// Write all of data to buffer in one operation.

[minyue-webrtc, 2015/08/12 14:20:20]

It can happen that repetition starts in the middle of a frame?

[hlundin-webrtc, 2015/08/12 14:38:00]

Hm, ok. But I still have a feeling you could simplify the implementation. I may
be wrong...

[peah-webrtc, 2015/08/12 21:05:16]

I agree that this feels more complex than needed. And for sure if the
look_back_range and length_range are used it could get significantly complex. 

Since this occurs rather seldomly, I think it would make sense to optimize for
the most common case.

What about a probalistic solution where for each frame (for simplicity assuming
a linear buffer)
{
repetition_detected = false;
buffer_index = last_buffer_insertion_index-frame_length; // Assume at least one
frame of repetition length
while (buffer_index > (last_buffer_insertion_index - 10 * frame_length) //
Search over 10 frames 
{
  // Find a match candidate if two values in a row are identical (also need to
take values 0, 32767, -32767 and -32768 specially into account (see below)
  if ((sample[0] == audio_buffer[buffer_index]) && (sample[1] ==
audio_buffer[buffer_index+1])) {
     // Assume 10 matching samples in a row sufficient for a repeated audio
being present with a very high probability
     int k;
     for (k = 0; k < 8; k++) 
        if ( sample[2+k] != audio_buffer[buffer_index+2+k])
          break;
     if (k == 8)
         SendUMAMessage("Repetition found")
   }
  buffer_index--;
}
}

That code will find any type of repetition pattern, but will fail to report the
length of the repetition.

+    for (auto& state : states_) {
+      new_buffer_end = (buffer_end_ + 1) % buffer_length_samples_;
+      look_back_pointer = (new_buffer_end - state.look_back_ +
+          buffer_length_samples_) % buffer_length_samples_;

[peah-webrtc, 2015/08/12 11:02:54]

The addition of buffer_length_samples_ seems to be redundant, as it always
results in 0 in the modulus operation

[minyue-webrtc, 2015/08/12 11:32:13]

This is to avoid negative, e,g, -2%3=-2

[peah-webrtc, 2015/08/12 21:05:16]

Good point! Thanks!

+
+      // For multichannel audio, all channels have to repeat the same way.

[peah-webrtc, 2015/08/12 11:02:54]

Is this a neccessary requirement, would it not just be sufficient to look at the
leftmost channel for repetitions? If we are to look at the repetitions for both
channels, I think we should look at them separately, and count a repetition if
any of them contains a repetition

[minyue-webrtc, 2015/08/12 11:32:14]

I consulted Chromium people. It is supposed that should always happen in both
channels. But this is disputable too, since detection may be made looser.

[hlundin-webrtc, 2015/08/12 14:12:04]

I agree with Per. Look at only one channel for now.

[minyue-webrtc, 2015/08/28 14:27:00]

In our recordings, we found that repetition should happen to both channels.

In the new implementation, I take the advantage of this and made the detector
(and API) simpler. Let me know if you think it is still better good to check one
channel only

+      bool sample_repeated = true;
+      for (int ch = 0; ch < num_channels_; ch++) {
+        if (sample[ch] != audio_buffer_[ch][look_back_pointer]) {
+          sample_repeated = false;

[peah-webrtc, 2015/08/12 21:05:16]

Inequality is not a sufficient condition for repeated audio. That would for
instance cause a constant zero signal to count as repeated audio, which is not
neccessarily.

Most likely we should treat the value zero specially, as well as the saturating
values (in case we have a very strong sound constantly saturating the microphone
signal (-32768, -32767 and 32767 in 16 bit integers).

We most probably also should take a constant DC offset from zero as a special
case, depending on whether we HP filter the signal before the check or not.

[minyue-webrtc, 2015/08/28 14:27:00]

Zeros are treated specially now.

+        }
+      }
+
+      if (sample_repeated) {
+        state.count_++;
+      }
+      if (state.count_>= state.look_back_ ||  // To break multiple repetitions.
+          !sample_repeated) {
+        if (state.count_ >= state.length_ - state.length_range_ &&

[peah-webrtc, 2015/08/12 11:02:54]

I'm not fully sure about the role of the length_range_ since it is always set to
zero in the code, could you please explain its role in a comment, or specify a
pattern where it is nonzero.

[minyue-webrtc, 2015/08/12 11:32:14]

see discussion on look_back_range

+            state.count_ <= state.length_ + state.length_range_) {
+          ReportRepetition(state.id_);
+        }
+        state.count_ = 0;
+      }
+    }
+
+    // Update buffer.
+    for (int ch = 0; ch < num_channels_; ch++, sample++) {
+      audio_buffer_[ch][new_buffer_end] = *sample;
+    }
+    buffer_end_ = new_buffer_end;
+  }
+}
+
+}  // namespace webrtc