In this milestone, we’ll solve the problem generated by the recording of the signal emitted by our speakers that is captured by our microphone, generating an unpleasant feedback that difficults our conversation (using InterCom). First, we’ll formalize the problem and then we will explore different solutions, with varying effectiveness and computational requirements.
One of the first problems we encounter with the use of the buffer.py module1 is that, if we don’t use headphones, the sound that comes out of our PC’s (loud)speaker some time (miliseconds) later reaches our mic(rophone), and more some time later, that sound reaches our interlocutor (the “far-end” ... in the system we are the “near-end”) in the form of an echo (signal) of its own voice, which is reproduced by his/her speaker, which can be captured again (some time later) by his/her mic and sent it back to us ... and so on, generating a rather unpleasant feedback “noise”.
To formalize this problem, let’s define:
where
where \(\tilde {\cdot }\) represents an approximation of \(\cdot \). We have here approximations because the signals are modified when they travel through the air.
Our problem here is to minimize the energy of \(\tilde {s}\), i.e., to make
Use a headset. In this case,
because in this case, \(s(t)\approx \tilde {s}(t)\approx 0\).
Decrease the gain of the amplifier of your speaker to do (the energy of) \(\tilde {s}\) as small as possible. Unfortunately, this also decreases the volume of the far-end signal \(s\) (the voice of our interlocutor) :-/
Lets \(\mathbf m\) the digital version of \(m\), and \({\mathbf m}[t]\) it’s \(t\)-th sample4. In this “simplest” solution, we send
where \(a\) is an attenuation (scalar) value, and \(d\) represents the delay5 (measured in sample-times) required to propagate the sound waves from our speaker to our mic. We define
as the estimated6 feedback/echo signal that reaches our microphone at the same instant of time that the sample \({\mathbf n}[t]\) would have been captured in the ausence of the feedback.
Notice that it have been used the notation \(\hat {\cdot }\) to emphasize that \(\hat {\mathbf s}\) is a (“registered”7) prediction for \(s\) reaching our microphone. Notice also that, if \({\mathbf s}[0]\) is the first sample of a chunk (for example, the \(c\)-th chunk), the sample \({\mathbf s}[-d]\) could belong to a previous chunk (the \((c-1)\)-th chunk).
Finally, \(a\) should be choosen considering that under ausence of voice in each end, \(s(t)\approx 0\). For example, Skype estimates \(d\) and \(a\) using a “call-signal” (a sequence of more-or-less tonal sounds). \(d\) is determined measuring the propagation time of the call-signal between our speaker and our mic.
This algorithm is ineffective because:
We can improve the performance of the previous feedback cancellation solution if we take also into consideration that the feedback signal \(\tilde {s}\) that finally reaches our microphone is (at least in part) the convolution of \(s\) and a signal \(h\) that represents the impulse response of our local audioset (speaker, mic, walls, monitor, keyboard, our body, ...) to an impulse signal \(\delta (t)\).8 In other words, we can modify Eq. \eqref{eq:simplest} to compute
where \(\ast \) represents the (digital) convolution between (in our case of) digital signals, and \(\mathbf h\) is the digitalized version of \(h(t)\).
Notice that in this solution, Eq. \eqref{eq:minimal_filter} (the estimation for the echo signal) becomes
The convolution of digital signals in the time domain can be expensive (with computational complexity \(O^2\), where \(O\) is the number of elements to process) if the number of samples or/and filter coefficientsis is high. Fortunately, thanks to the convolution theorem [1, 2], the convolution can be replaced by the dot product (with complexity \(O\)), when we consider the signals in the frequency domain. Thanks to this, we can rewrite the Eq. \eqref{eq:using_convolution} as
where \(\mathbf S\) is the (digital) Fourier transform9 of \(\mathbf s\), \(\mathbf H\) is the Fourier transform10 of \(\mathbf h\), and \({\mathcal F}^{-1}\) represents the inverse (digital) Fourier transform. Notice that all these transforms are applied to digital signals, and there exist fast algorithms (with complexity \(O\log _2O\)) to “travel” from the signal domain to the frecuency domain, and viceversa.
Unfortunately, even when we expect that this improved echo supression algorithm is going to perform better than the previous one, the computation of the filter weights \(\mathbf h\) requires emitting impulses that can be heard by the user. Furthermore, while the acoustic response of the environment is being analyzed, the near-end should remain silent; otherwise, its own voice would be treated as an echo and attenuated by the filter.
We can avoid having to generate the impulses if we are able to construct a mathematical model of our acoustic environment’s response to those impulses (or to any other audio signal, such as the one output by our speakers). For the sake of simplicity, we will assume that this model is a FIR filter and attempt to estimate its coefficients.
The LMS algorithm can find \(\mathbf {h}\) adaptively. For this, we model
and define that the error (what we should send through the network) is
So, for each input (audio) sample, we have
After substituting this result in \eqref{eq:LMS_error}) we obtain that
Now, we compute
Thus, the Mean Squared Error is
As can be seen, the MSE is a cuadratic function of \(\mathbf {h}\), i.e., a (in general hyper11-) paraboloid in which we can find the minimum (the optimal values for \(\mathbf {h}\)) using the Steepest Decent Algorithm. Ideally, we should compute (iteratively)
where \(\mu >0\) is the learning rate, and the (ideal) gradient is
Unfortunatelly, we don’t have \(\xi \), but we can approximate it using the instanteneous error (consider \eqref{eq:LMS_error} and the derivative of \eqref{eq:e_squared}). Thus
obtaining finally that
Stability requires \(0 < \mu < 2/(L · \sigma ^2(s))\), so the step size depends on the input power. For speech, whose level varies enormously, this is a problem. So use NLMS, which normalizes by the input energy
where
We can avoid having to generate the impulses if we are able to construct a mathematical model of our acoustic environment’s response to those impulses (or to any other audio signal, such as the one output by our speakers). For the sake of simplicity, we will assume that this model is a FIR filter and attempt to estimate its coefficients.
The LMS algorithm can find \(\mathbf {h}\) adaptively. For this, we model
and define that the error (what we should send through the network) is
So, for each input (audio) sample, we have
After substituting this result in \eqref{eq:LMS_error}) we obtain that
Now, we compute
Thus, the Mean Squared Error is
As can be seen, the MSE is a cuadratic function of \(\mathbf {h}\), i.e., a (in general hyper12-) paraboloid in which we can find the minimum (the optimal values for \(\mathbf {h}\)) using the Steepest Decent Algorithm. Ideally, we should compute (iteratively)
where \(\mu >0\) is the learning rate, and the (ideal) gradient is
Unfortunatelly, we don’t have \(\xi \), but we can approximate it using the instanteneous error (consider \eqref{eq:LMS_error} and the derivative of \eqref{eq:e_squared}). Thus
obtaining finally that
Stability requires \(0 < \mu < 2/(L · \sigma ^2(s))\), so the step size depends on the input power. For speech, whose level varies enormously, this is a problem. So use NLMS, which normalizes by the input energy
where \(\epsilon \) should be small and \(\epsilon >0\) to avoid division by zero.
\(L\) must cover the echo path
where \(T\) is the echo tail (the acoustic delay plus reverberation). At \(f_s=44.1\) kHz and 50–100 ms of latency, that’s about 2000-4500 taps. Also, any system latency (audio buffers, chunk size) between playing \(\mathbf {s}\) and recording it shows up as leading zeros in \(\mathbf {h}\). Remember that you must update the filter coefficients for every input sample!
import numpy as np class NLMS: def __init__(self, L=2048, mu=0.5, eps=1e-6): self.L, self.mu, self.eps = L, mu, eps self.w = np.zeros(L) self.hist = np.zeros(L - 1) # last L-1 reference samples def process(self, x, d): """x: reference chunk (played), d: microphone chunk. Float arrays, same length.""" buf = np.concatenate((self.hist, x)) e = np.empty_like(d) for n in range(len(d)): u = buf[n:n + self.L][::-1] # [x(n), x(n-1), ..., x(n-L+1)] e[n] = d[n] - self.w @ u self.w += (self.mu * e[n] / (self.eps + u @ u)) * u self.hist = buf[-(self.L - 1):] return e
When the local person speaks while the far end speaks, \(\mathbf {n}\) corrupts the adaptation (the filter “diverges”). So, it is necessary to use a double-talk detector and disable the learning while I’m speaking :-/
Lets recap. Our problem is that, without a headset, we have that the signal that we send is
where \(\tilde {\mathbf {n}}\) is the version of our voice captured by our mic, and \(\hat {\mathbf {s}}\) is a aproximated-and-multy-echo version of \(\mathbf {s}\), the signal played by our speaker(s). And if we were able to make \(\hat {\mathbf {s}}=\mathbf {0}\), our feedback problem would vanish, ... at least, theoretically.
But wait ..., as a polite person, if I don’t speak when I am listening to (my interlocutor), I could assume that \(\hat {\mathbf {s}}=\mathbf {0}\) when I am speaking because my interlocutor should do the same (be silent when I speak)! But, if this is not true? A solution is: if I am speaking, can attenuate \(\mathbf {s}\) (the signal played by my speaker).
Summarizing: you should be able to control the volume of \(s\) (the analog signal that comes out from my speaker) and cut it down (or even off, if necessary) when you are speaking or your mic is recording a signal \(m\) with enough energy.