# Gradient Based Adaptive Algorithm for Echo Cancellation from Recorded Echo Corrupted Speech

Authors: Upal Mahbub; Shaikh Anowarul Fattah
Journal: Advances in Electrical Engineering
 (2014)

---

## Abstract

An offline single channel acoustic echo cancellation (AEC) scheme is proposed based on gradient based adaptive least mean squares (LMS) algorithm considering a major practical application of echo cancellation system for enhancing recorded echo corrupted speech data. The unavailability of a reference signal makes the problem of single channel adaptive echo cancellation to be extremely difficult to handle. Moreover, continuous feedback of the echo corrupted signal to the input microphone can significantly degrade the quality of the original speech signal and may even result in howling. In order to overcome these problems, in the proposed scheme, the delayed version of the echo corrupted speech signal is considered as a reference. An objective function is thus formulated and thereby a modified LMS update equation is derived, which is shown to converge to the optimum Wiener-Hopf solution. The performance of the proposed method is evaluated in terms of both subjective and objective measures via extensive experimentation on several real-life echo corrupted signals and very satisfactory performance is obtained.


---

## Body

## 1. Introduction

The phenomenon of acoustic echo occurs when the output speech signal from a loudspeaker gets reflected from different surfaces, like ceilings, walls, and floors, attenuated, and then fed back to the microphone. In real-life scenarios, such as a lecture in a large conference hall or in the public address system of a trade fair, acoustic echo is a very common phenomenon [1, 2]. Severe echo in these scenarios may degrade the quality of the speech signal to a great extent leading to complete loss of intelligibility and thereby cause public annoyance and produce severe sound pollution. A continuous acoustic feedback of a significant proportion of the sound energy transmitted by the loudspeaker back to the microphone may result in extreme howling [1, 3].An acoustic echo canceller is usually incorporated in the design of a communication channel or a conference room environment. As communication links are mostly dual channel, the adaptive filter algorithms, which by principle require two separate channels, are widely used for acoustic echo cancellation (AEC) in communication links [4–8]. In these AEC systems, the near-end signal, which is available at hand, is fed to the adaptive filter as a reference to cancel the far-end echoed signal [9]. Here, the channel acoustic response parameters are updated adaptively to produce an estimate of echo. Among different adaptive filter algorithms, the gradient based least mean squares (LMS) algorithm and its modifications, such as normalized LMS (NLMS) and variable step size LMS (VLMS) algorithms, are widely used for their satisfactory performances, less computational burden, and ease of implementation [2, 9, 10]. A faster algorithm is the recursive least mean squares (RLS) algorithm which is, however, computationally expensive [9].A rather different problem of single channel echo cancellation arises in large room environments where there is only one available channel for signal transmission [1]. The echo corrupted output of the loudspeakers may get echoed again and added to the input speech to produce extreme corruption of the speech data. In this case, handling the problem of AEC with adaptive filter seems to be much difficult as a desired reference signal is not available [11]. Instead, echo suppressors, earphones, and directional microphones have been conventionally used in order to combat the problem of single channel acoustic echo at large room environments. However, these instruments generally place restrictions on the talkers' movement [3]. The acoustic engineers also employ different manual measures, such as sound absorbers and manually tuned filters, to suppress the room echoes. Some digital filtering based approaches are also found in the literature [12–14]. A more critical problem is to cancel out echo from the recorded echo corrupted speech data, for example, recorded speech in a conference room environment. In this case, the echo cancellation operation needs to be carried out in offline mode where the only available data is the highly echo corrupted speech signal. Moreover, the level of echo corruption is very severe as the echo corrupted output of the loudspeaker is echoed back to the microphone again and again. The problem of developing an offline single channel acoustic echo canceller based on adaptive filter algorithms is rarely addressed in the literature.Considering the unavailability of a separate channel, an offline single channel AEC scheme based on the gradient based adaptive LMS algorithm is developed in this paper. Assuming the worst realistic case of continuous feedback of echo corrupted sound from the loudspeaker to the microphone, a delayed version of the echo corrupted signal is utilized as a reference to the adaptive filter for echo cancellation from current sample. The major advantage in this procedure is that an excellent performance of echo suppression is being achieved while a separate reference channel is no longer required. In this paper, starting from a modified objective function, the LMS update equation is derived and convergence of the resulting update to the optimum Wiener-Hopf solution is proved. Finally, considering various acoustic environments, the echo cancellation performance of the proposed method is evaluated in terms of both subjective and objective measures.


## 2. Proposed Echo Cancellation Method

A simplified block diagram representing the echo generation process in an acoustic room environment is shown in Figure1. In this figure, the nth samples of the input speech and echo are denoted by s
(
n
) and x
(
n
), respectively, and corresponding echo corrupted speech is written as
(1)
y
(
n
)
=
s
(
n
)
+
x
(
n
)
.
It is evident from the figure that the echo is actually a reflected and attenuated version of y
(
n
). For echo generating acoustic environment the conventional practice is to model the room response as a finite impulse response (FIR) with a predefined flat delay k
0. The minimum time required for the speech sample to travel directly from the loudspeaker to the microphone is termed as flat delay [15]. Therefore, the coefficients of FIR filter representing the flat delay portion of the room response can be assumed to be zero. Now, if the room response filter is considered to have p unknown coefficients, the echo x
(
n
) produced by the acoustic environment can be expressed as
(2)
x
(
n
)
=
{
0
,
if
0
≤
n
<
k
0
;
a
n
T
s
(
n
-
k
0
)
,
if
k
0
≤
n
<
2
k
0
;
a
n
T
y
(
n
-
k
0
)
,
if
n
≥
2
k
0
,
where y
(
n
-
k
0
)
=
[
y
(
n
-
k
0
-
1
)
,
y
(
n
-
k
0
-
2
)
,
…
,
y
(
n
-
k
0
-
p
)
]
T is a vector of p previous values of y
(
n
) with predefined flat delay k
0 and a
n
=
[
a
n
(
1
)
,
a
n
(
2
)
,
…
,
a
n
(
p
)
]
T is the vector of the unknown room response filter coefficients. The number p of unknown attenuation coefficients a
n
(
k
) depends on the characteristics of the room. Note that in (2), for echo generation, three different cases are considered with respect to time in order to ensure that the most critical case of repeated feedback is incorporated. During the flat delay period (equivalently k
0 samples) there will be no echo generation. At or after flat delay period first, only the delayed version of original signal (with respect to current input) will be played through the microphone and reflected back and thus echo is generated, which is presented in (2) for k
0
≤
n
<
2
k
0. During this period the microphone is receiving current original speech input along with echo; that is, y
(
n
)
=
s
(
n
)
+
x
(
n
). Thus, next time as y
(
n
) will be played through the loudspeaker, for n
≥
2
k
0, echo will be generated by delayed version of y
(
n
) instead of s
(
n
). It is to be noted that, for n
≥
k
0, for every instance in echo generation, instead of original input, echo corrupted input y
(
n
) is considered, which makes the echo cancellation problem extremely difficult.Figure 1
Echo generation: offline method.The task of the proposed AEC system is to cancel the echo from the echo corrupted signaly
(
n
) and retrieve the input speech signal s
(
n
) adaptively. In Figure 2, the schematic diagram of the proposed model is depicted. It can easily be apprehended from the figure that the echo corrupted signal y
(
n
) is fed to an adaptive filter block as an input. The task of the adaptive filter block is to produce an estimate x
^
(
n
) of the echo signal x
(
n
), which is present in y
(
n
). The estimate x
^
(
n
) is then subtracted from y
(
n
) to produce error signal given by
(3)
e
(
n
)
=
y
(
n
)
-
x
^
(
n
)
.
The task of the adaptive filter block is to generate an accurate estimate of echo such that the error signal contains the original signal s
(
n
). However, the resulting echo suppressed signal, namely, s
^
(
n
)
=
s
(
n
)
+
ς
(
n
), may contain ς
(
n
), known as residual echo. Finally s
^
(
n
) is then transmitted to the loudspeaker.Figure 2
Echo cancellation: offline method.To produce an estimation of the echo signalx
(
n
), the adaptive filter requires an input signal, which is undoubtedly y
(
n
) in this case, and a reference. Since there is no scope to provide a separate reference in single channel AEC problem, we propose to utilize some delayed versions of the input echo corrupted signal y
(
n
) as the reference signal. This is because, from the echo generation process, it is evident that the added echo is actually a delayed and attenuated version of the previous echo corrupted signal; that is, echo is generated when samples of previous echo corrupted signal pass the room response filter. Therefore, the estimated echo x
^
(
n
), generated by the adaptive filter block, can be expressed as
(4)
x
^
(
n
)
=
{
0
,
if
0
≤
n
<
k
0
;
w
^
n
T
s
(
n
-
k
0
)
,
if
k
0
≤
n
<
2
k
0
;
w
^
n
T
y
(
n
-
k
0
)
,
if
n
≥
2
k
0
,
where w
^
n
=
[
w
^
n
(
1
)
,
w
^
n
(
1
)
,
…
,
w
^
n
(
p
)
]
T consists of the current estimate of the room attenuation parameters to be estimated by the adaptive filter block.The objective function required to obtainw
^
(
n
) can be defined as the mean square estimation of the error function e
(
n
); namely,
(5)
J
n
=
E
{
e
2
(
n
)
}
=
E
{
s
2
(
n
)
}
+
E
{
[
x
(
n
)
-
x
^
(
n
)
]
2
}
+
2
E
{
[
s
(
n
)
(
x
(
n
)
-
x
^
(
n
)
)
]
}
.
The last term at the right-hand side can be neglected based on the assumptions that the correlation between the input speech s
(
n
) and its delayed version s
(
n
-
k
0
) is negligible at higher lags. As a result, the objective function in (5) reduces to
(6)
J
n
=
E
{
s
2
(
n
)
}
+
E
{
[
(
a
n
T
-
w
^
n
T
)
y
(
n
-
k
0
)
]
2
}
.Minimizing the objective function (6) with respect to w
^
n
T, that is, considering ∂
J
n
/
∂
w
^
n
T
=
0, one can obtain
(7)
E
{
[
x
(
n
)
-
x
^
(
n
)
]
y
(
n
-
k
0
)
}
=
0
,
which can be expressed as
(8)
E
{
x
(
n
)
y
(
n
-
k
0
)
}
=
w
^
n
T
E
{
y
(
n
-
k
0
)
y
(
n
-
k
0
)
}
.
The above equation is similar to Wiener-Hopf equation and its solution can be written as
(9)
w
^
n
T
=
R
y
y
(
n
-
k
0
)
-
1
r
x
y
(
n
-
k
0
)
,
where r
x
y is the cross-correlation matrix between x
(
n
) and y
(
n
-
k
0
), while R
y
y is the autocorrelation matrix of y
(
n
-
k
0
). The Wiener-Hopf solution, w
^
n
T, is undoubtedly the most optimum solution possible. Hence, it is shown that even for a single channel AEC problem the most optimum solution w
^
n can be achieved based on the assumption of negligibility of cross-correlation terms in (5).In order to avoid any correlation measurements or matrix inversion involved in (9), an adaptive LMS algorithm is employed. The update equation of the weight vector of conventional LMS adaptive algorithm is generally expressed as [9]
(10)
w
^
n
+
1
T
=
w
^
n
T
-
μ
∇
ξ
(
n
)
,
where μ is the step factor controlling the stability and rate of convergence, ξ
(
n
) is the cost function, and ∇ is the gradient operator. Unlike the objective function defined in (5), conventional LMS algorithm simply approximates the cost function ξ
(
n
) as the square of the instantaneous error e
(
n
); that is, ξ
(
n
)
=
e
2
(
n
), where e
(
n
) is defined in (3). The gradient of ξ
(
n
), therefore, can be written as
(11)
∇
ξ
(
n
)
=
∂
ξ
(
n
)
∂
w
^
n
T
=
-
2
e
(
n
)
y
(
n
-
k
0
)
.
Thus, the update equation (10) can be expressed as
(12)
w
^
n
+
1
T
=
w
^
n
T
+
2
μ
e
(
n
)
y
(
n
-
k
0
)
.
For the kth unknown filter parameter at the nth iteration the update equation can be written as
(13)
w
^
n
+
1
T
(
k
)
=
w
^
n
T
(
k
)
+
2
μ
e
(
n
)
y
(
n
-
k
0
-
k
)
,
where k
=
1,2
,
…
,
p.


## 3. Convergence Analysis of the Proposed LMS Update

Considering expectation operation on both sides of (12), one can obtain
(14)
w
^
_
n
+
1
T
=
w
^
_
n
T
+
2
μ
E
{
e
(
n
)
y
(
n
-
k
0
)
}
.
Here an underline beneath w
^
n
T is introduced to represent the expected value E
{
w
^
n
T
}. Based on the assumptions on the negligibility of the cross-correlation terms as stated earlier, (14) can be written as
(15)
w
^
_
n
+
1
T
=
w
^
_
n
T
-
2
μ
R
y
y
(
n
-
k
0
)
w
^
_
n
T
+
2
μ
r
x
y
(
n
-
k
0
)
.
Evaluating the homogeneous and particular solutions of (15), the total solution can be obtained as (see Appendix)
(16)
w
^
_
n
+
1
T
U
(
k
)
=
C
k
(
1
-
2
μ
λ
(
k
)
)
n
+
1
λ
(
k
)
r
x
y
U
(
n
-
k
0
-
k
)
,
where λ
(
k
) is the kth diagonal element of the eigenvalue matrix obtained by eigenvalue decomposition of R
y
y
(
n
-
k
0
) and r
x
y
U
(
n
-
k
0
-
k
) is the kth element of U
T
r
x
y
(
n
-
k
0
)
=
r
x
y
U
(
n
-
k
0
) with the matrix U consisting of eigenvectors corresponding to eigenvalues. Since in the iterative update procedure the homogeneous part (
1
-
2
μ
λ
(
k
)
)
n diminishes with iterations, (16) in a matrix form can be expressed as
(17)
w
^
_
T
=
U
Λ
-
1
U
T
r
x
y
(
n
-
k
0
)
=
R
y
y
-
1
(
n
-
k
0
)
r
x
y
(
n
-
k
0
)
.
Thus, it is found that the average value of the weight vector converges to the Wiener-Hopf solution, which is the optimum solution with increasing number of iterations.


## 4. Experimental Results

The performance of the proposed AEC algorithm is investigated in terms of objective and subjective measures and different echo corrupted speech signals under various acoustic room environments are considered. Speech samples uttered by several male and female speakers available in the TIMIT database are utilized for performance evaluation [16]. An acoustic room environment is simulated using an FIR filter of length N
f, where as per conventional approaches filter coefficients during the flat delay portion are assumed to be zero. The flat delay time (
k
0
) can be precalculated based on the distance between the microphone and the speaker [15]. Because of the implicit zeros corresponding to the flat delay, it is evident that a few number (
N
f
-
k
0
) of unknown coefficients have to be determined. In the proposed method, a smaller step size is used in order to obtain a smooth convergence.The echo corrupted signal recorded at different acoustic environments and the corresponding echo suppressed signals produced by using the proposed method are successively played to 5 individual listeners. From the overall response of the listeners in terms of mean objective score (MOS), a very satisfactory performance of the proposed method is obtained even under severe echo generating conditions in noise.Next, two objective measures are employed to quantify the improvement in speech quality. One of the objective measures, the echo return loss enhancement (ERLE) in dB, represents the amount of attenuation of the echo introduced by the adaptive filter alone. It is the ratio of the instantaneous power of the residual echo remaining in the echo suppressed signalη
s
^
-
s
(
n
) and that of the input echo η
x
(
n
) and is expressed in dB as [1]
(18)
ERLE
(
n
)
=
-
10
log
⁡
⁡
η
s
^
-
s
(
n
)
η
x
(
n
)
.
The average value of ERLE
(
n
) in dB over time is used as the criteria of performance evaluation in this experiment. Another objective evaluation criterion, the signal to distortion ratio (SDR) in dB, is a measure of the ratio of signal power to the power of the distortion introduced. The SDR is computed at the input and output sides of the AEC system and the difference in these SDR values, namely, SDR improvement (SDRI), is considered as an indicator of the system performance and defined as
(19)
SDRI
=
SD
R
out
-
SD
R
in
,
where
(20)
SD
R
in
=
10
log
⁡
⁡
P
s
P
x
,
SD
R
out
=
10
log
⁡
⁡
P
s
P
s
^
-
s
.
Here, P
s is the overall power of the original signal s
(
n
), P
x is the overall power of echo at the microphone input, and P
s
^
-
s
(
n
) is the total power of distortion (residual noise and echo) present in the echo suppressed output signal. The higher the value of SDRI is, the better the performance of the echo canceller is.The proposed algorithm has been tested on several different sentences taken from the TIMIT database. In order to demonstrate the principle of selecting different threshold values required in the proposed updating constraints, as a typical example, a sample utterance “good service should be rewarded by big tips” taken from the TIMIT database is shown in Figure3(a) [16]. The echo corrupted speech signal is shown in Figure 3(b). The outcome of the proposed adaptive filter method, the echo suppressed speech signal, is plotted in Figure 3(c). The marked areas in the figure help to clearly visualize the AEC performance of the proposed method by comparing the waveform of the echo suppressed signal to that of the echo corrupted and the original input signal. It can be easily apprehended that the echo suppressed signal almost resembles the original input signal and the effect of echo is significantly reduced.Figure 3
AEC performance obtained by the proposed method in time domain: (a) original signals
(
n
), (b) echo corrupted signal y
(
n
), and (c) echo suppressed signal s
^
(
n
).For a better understanding of the performance of the echo canceller, spectral analysis of the AEC performance is introduced. The spectrograms of the original speech signals
(
n
), the echo corrupted signal y
(
n
), and the echo suppressed signal s
^
(
n
) are depicted, respectively, in Figures 4(a), 4(b), and 4(c). It is observed that the spectrum of the echo corrupted signal is quite different from that of the original signal at different frequency levels because of the presence of unwanted signals resulting from the echo signals (as can be seen from some sample marked regions). Especially, the effect of noise corruption at high frequency regions of the spectrogram is quite prominent at different time instances. The main reason behind such effect is the continuous feedback of echo corrupted speech sample to the input microphone. To human ear, this noise is a high pitched sound present alongside the utterance. This noise may grow to a high magnitude if the echo power is increased in a conference room due to bad acoustics and may result in total loss of intelligibility. However, it is clearly evident in the spectrum of the echo suppressed signal obtained by the proposed method that the unwanted high pitch noise has been drastically reduced.Figure 4
AEC performance obtained by the proposed method in spectral domain: (a) spectrogram of original signals
(
n
), (b) spectrogram of echo corrupted signal y
(
n
), and (c) spectrogram of echo suppressed signal s
^
(
n
).For further experimentation, another sample utterance “she had your dark suit in greasy wash water all year” from the TIMIT database is considered and shown in Figure5(a). The echo corrupted speech signal and the echo suppressed speech signal for this utterance are shown in Figures 5(b) and 5(c), respectively. Moreover, the spectrograms of the utterance 2, the echo corrupted signal, and the echo suppressed utterance are shown in Figures 6(a), 6(b), and 6(c), respectively. From these figures it is evident that the proposed single channel AEC scheme can enhance speech quality by suppressing echo from the echo corrupted recorded speech.Figure 5
AEC performance obtained by the proposed method in time domain for utterance 2: (a) original signals
(
n
), (b) echo corrupted signal y
(
n
), and (c) echo suppressed signal s
^
(
n
).Figure 6
AEC performance obtained by the proposed method in spectral domain for utterance 2: (a) original signals
(
n
), (b) echo corrupted signal y
(
n
), and (c) echo suppressed signal s
^
(
n
).In order to demonstrate the effect of various acoustic environments on the echo cancellation performance obtained by the proposed method, the number of room response filter coefficients is varied while generating the recorded data. In Tables1 and 2, the performance variation of the proposed method for both utterances with the change in number of nonzero filter coefficients is reported in terms of SDRI (dB) and average ERLE (dB), respectively. Performance is evaluated for different number of unknown coefficients ranging from 4 to 12. It is found from the tables that the performance of the proposed method remains consistently better irrespective of the number of filter coefficients. Hence, it is evident that the proposed method exhibits robust performance at different acoustic echo generating environments.Table 1
SDRI (dB) for utterances 1 and 2 with the variation of filter coefficients.
Number of nonzero coefficients
SDRI (dB) for utterance1
SDRI (dB) for utterance2
4
5.2897
6.1964
6
4.6421
4.8228
8
3.9279
4.0238
10
3.1135
3.4416
12
2.6421
2.9611Table 2
Average ERLE (dB) for utterances 1 and 2 with the variation of filter coefficients.
Number of coefficients
Average ERLE (dB) for utterance1
Average ERLE (dB) for utterance2
4
11.7145
12.5277
6
10.9917
10.846
8
10.3702
10.4019
10
10.4008
9.334
12
9.6586
8.8276


## 5. Conclusion

A practical approach of single channel acoustic echo cancellation from recorded echo corrupted data using gradient based adaptive LMS algorithm is developed in this paper. The major problem of unavailability of the reference signal required for successful adaptation operation of the adaptive filter has tactfully been overcome by using the delayed version of echo corrupted input signal as the reference. This calls for a modification in the conventional objective function of the gradient based adaptive LMS algorithm and a theoretical proof of convergence of the adaptive scheme to the optimal solution is given. The echo cancellation performance of the proposed method is evaluated by means of subjective and objective measures and in time and frequency domain at different acoustic recording conditions. It is found that the proposed offline AEC algorithm is capable of providing a very satisfactory echo cancellation performance for recorded echo corrupted speech in terms of average ERLE (dB) and SDR improvement (dB) under various acoustic room environments. Different competing adaptive algorithms, other than the LMS algorithm and blind deconvolution, can be implemented in the proposed frame work to handle single channel echo cancellation. Moreover, keeping the proposed framework intact, it may be possible in the future to incorporate optimization algorithms other than the LMS, such as block LMS and RLS, in order to obtain single channel echo cancellation system. Also, the proposed scheme may be extended for online echo and noise cancellation, which would be an interesting future work.



---

*Source: 869721-2014-06-11.xml*