EchoSuppressor.cpp revision 13e2c821a765845e3df0d64b9b92748c31310927
1c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh/* 2c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh * Copyrightm (C) 2010 The Android Open Source Project 3c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh * 4c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh * Licensed under the Apache License, Version 2.0 (the "License"); 5c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh * you may not use this file except in compliance with the License. 6c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh * You may obtain a copy of the License at 7c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh * 8c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh * http://www.apache.org/licenses/LICENSE-2.0 9c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh * 10c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh * Unless required by applicable law or agreed to in writing, software 11c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh * distributed under the License is distributed on an "AS IS" BASIS, 12c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh * See the License for the specific language governing permissions and 14c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh * limitations under the License. 15c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh */ 16c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh 17c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh#include <stdio.h> 18c464603d67d5ec9d74c199fab3f18dd23a8169dbChung-yih Wang#include <string.h> 19c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh#include <stdint.h> 20919cd86bc78559f1e33af0fb66913cf0a94468f1Marco Nelissen#include <string.h> 21c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh#include <math.h> 22c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh 23c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh#define LOG_TAG "Echo" 24c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh#include <utils/Log.h> 25c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh 26c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh#include "EchoSuppressor.h" 27c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh 282e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh// It is very difficult to do echo cancellation at this level due to the lack of 292e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh// the timing information of the samples being played and recorded. Therefore, 302e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh// for the first release only echo suppression is implemented. 312e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh 322e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh// The algorithm is derived from the "previous works" summarized in 332e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh// A new class of doubletalk detectors based on cross-correlation, 342e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh// J Benesty, DR Morgan, JH Cho, IEEE Trans. on Speech and Audio Processing. 352e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh// The method proposed in that paper is not used because of its high complexity. 362e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh 372e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh// It is well known that cross-correlation can be computed using convolution, 382e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh// but unfortunately not every mobile processor has a (fast enough) FPU. Thus 392e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh// we use integer arithmetic as much as possible and do lots of bookkeeping. 402e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh// Again, parameters and thresholds are chosen by experiments. 412e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh 422e85359f74a5280ee733d35ff5f63b3943140632Chia-chi YehEchoSuppressor::EchoSuppressor(int sampleCount, int tailLength) 43c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh{ 442e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh tailLength += sampleCount * 4; 452e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh 462e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh int shift = 0; 472e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh while ((sampleCount >> shift) > 1 && (tailLength >> shift) > 256) { 482e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh ++shift; 49c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 50c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh 512e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mShift = shift + 4; 522e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mScale = 1 << shift; 53c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh mSampleCount = sampleCount; 542e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mWindowSize = sampleCount >> shift; 552e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mTailLength = tailLength >> shift; 562e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mRecordLength = tailLength * 2 / sampleCount; 57c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh mRecordOffset = 0; 58c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh 592e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mXs = new uint16_t[mTailLength + mWindowSize]; 602e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh memset(mXs, 0, sizeof(*mXs) * (mTailLength + mWindowSize)); 612e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mXSums = new uint32_t[mTailLength]; 622e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh memset(mXSums, 0, sizeof(*mXSums) * mTailLength); 632e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mX2Sums = new uint32_t[mTailLength]; 642e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh memset(mX2Sums, 0, sizeof(*mX2Sums) * mTailLength); 652e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mXRecords = new uint16_t[mRecordLength * mWindowSize]; 662e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh memset(mXRecords, 0, sizeof(*mXRecords) * mRecordLength * mWindowSize); 672e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh 682e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mYSum = 0; 692e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mY2Sum = 0; 702e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mYRecords = new uint32_t[mRecordLength]; 712e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh memset(mYRecords, 0, sizeof(*mYRecords) * mRecordLength); 722e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mY2Records = new uint32_t[mRecordLength]; 732e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh memset(mY2Records, 0, sizeof(*mY2Records) * mRecordLength); 742e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh 752e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mXYSums = new uint32_t[mTailLength]; 762e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh memset(mXYSums, 0, sizeof(*mXYSums) * mTailLength); 772e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mXYRecords = new uint32_t[mRecordLength * mTailLength]; 782e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh memset(mXYRecords, 0, sizeof(*mXYRecords) * mRecordLength * mTailLength); 79c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh 80c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh mLastX = 0; 81c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh mLastY = 0; 822e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mWeight = 1.0f / (mRecordLength * mWindowSize); 83c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh} 84c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh 85c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi YehEchoSuppressor::~EchoSuppressor() 86c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh{ 87c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh delete [] mXs; 882e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh delete [] mXSums; 892e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh delete [] mX2Sums; 902e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh delete [] mXRecords; 912e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh delete [] mYRecords; 922e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh delete [] mY2Records; 932e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh delete [] mXYSums; 94c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh delete [] mXYRecords; 95c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh} 96c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh 97c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yehvoid EchoSuppressor::run(int16_t *playbacked, int16_t *recorded) 98c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh{ 99c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh // Update Xs. 1002e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh for (int i = mTailLength - 1; i >= 0; --i) { 1012e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mXs[i + mWindowSize] = mXs[i]; 102c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 1032e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh for (int i = mWindowSize - 1, j = 0; i >= 0; --i, j += mScale) { 1042e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh uint32_t sum = 0; 105c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh for (int k = 0; k < mScale; ++k) { 1062e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh int32_t x = playbacked[j + k] << 15; 107c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh mLastX += x; 1082e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh sum += ((mLastX >= 0) ? mLastX : -mLastX) >> 15; 1092e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mLastX -= (mLastX >> 10) + x; 110c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 1112e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mXs[i] = sum >> mShift; 112c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 113c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh 1142e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh // Update XSums, X2Sums, and XRecords. 1152e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh for (int i = mTailLength - mWindowSize - 1; i >= 0; --i) { 1162e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mXSums[i + mWindowSize] = mXSums[i]; 1172e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mX2Sums[i + mWindowSize] = mX2Sums[i]; 118c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 1192e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh uint16_t *xRecords = &mXRecords[mRecordOffset * mWindowSize]; 1202e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh for (int i = mWindowSize - 1; i >= 0; --i) { 1212e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh uint16_t x = mXs[i]; 1222e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mXSums[i] = mXSums[i + 1] + x - xRecords[i]; 1232e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mX2Sums[i] = mX2Sums[i + 1] + x * x - xRecords[i] * xRecords[i]; 1242e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh xRecords[i] = x; 125c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 126c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh 127c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh // Compute Ys. 1282e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh uint16_t ys[mWindowSize]; 1292e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh for (int i = mWindowSize - 1, j = 0; i >= 0; --i, j += mScale) { 1302e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh uint32_t sum = 0; 131c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh for (int k = 0; k < mScale; ++k) { 1322e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh int32_t y = recorded[j + k] << 15; 133c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh mLastY += y; 1342e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh sum += ((mLastY >= 0) ? mLastY : -mLastY) >> 15; 1352e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mLastY -= (mLastY >> 10) + y; 136c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 1372e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh ys[i] = sum >> mShift; 138c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 139c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh 1402e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh // Update YSum, Y2Sum, YRecords, and Y2Records. 1412e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh uint32_t ySum = 0; 1422e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh uint32_t y2Sum = 0; 1432e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh for (int i = mWindowSize - 1; i >= 0; --i) { 1442e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh ySum += ys[i]; 1452e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh y2Sum += ys[i] * ys[i]; 146c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 1472e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mYSum += ySum - mYRecords[mRecordOffset]; 1482e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mY2Sum += y2Sum - mY2Records[mRecordOffset]; 1492e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mYRecords[mRecordOffset] = ySum; 1502e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mY2Records[mRecordOffset] = y2Sum; 1512e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh 1522e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh // Update XYSums and XYRecords. 1532e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh uint32_t *xyRecords = &mXYRecords[mRecordOffset * mTailLength]; 1542e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh for (int i = mTailLength - 1; i >= 0; --i) { 1552e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh uint32_t xySum = 0; 1562e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh for (int j = mWindowSize - 1; j >= 0; --j) { 1572e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh xySum += mXs[i + j] * ys[j]; 158c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 1592e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mXYSums[i] += xySum - xyRecords[i]; 1602e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh xyRecords[i] = xySum; 161c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 162c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh 1632e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh // Compute correlations. 164c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh int latency = 0; 1654136e2ac4eeca9b80a9da223f5256bba03f71c66Chia-chi Yeh float corr2 = 0.0f; 1664136e2ac4eeca9b80a9da223f5256bba03f71c66Chia-chi Yeh float varX = 0.0f; 1672e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh float varY = mY2Sum - mWeight * mYSum * mYSum; 1682e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh for (int i = mTailLength - 1; i >= 0; --i) { 1692e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh float cov = mXYSums[i] - mWeight * mXSums[i] * mYSum; 1704136e2ac4eeca9b80a9da223f5256bba03f71c66Chia-chi Yeh if (cov > 0.0f) { 1714136e2ac4eeca9b80a9da223f5256bba03f71c66Chia-chi Yeh float varXi = mX2Sums[i] - mWeight * mXSums[i] * mXSums[i]; 1724136e2ac4eeca9b80a9da223f5256bba03f71c66Chia-chi Yeh float corr2i = cov * cov / (varXi * varY + 1); 1734136e2ac4eeca9b80a9da223f5256bba03f71c66Chia-chi Yeh if (corr2i > corr2) { 1744136e2ac4eeca9b80a9da223f5256bba03f71c66Chia-chi Yeh varX = varXi; 1754136e2ac4eeca9b80a9da223f5256bba03f71c66Chia-chi Yeh corr2 = corr2i; 1764136e2ac4eeca9b80a9da223f5256bba03f71c66Chia-chi Yeh latency = i; 1774136e2ac4eeca9b80a9da223f5256bba03f71c66Chia-chi Yeh } 178c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 179c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 18013e2c821a765845e3df0d64b9b92748c31310927Steve Block //ALOGI("corr^2 %.5f, var %8.0f %8.0f, latency %d", corr2, varX, varY, 1814136e2ac4eeca9b80a9da223f5256bba03f71c66Chia-chi Yeh // latency * mScale); 182c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh 1832e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh // Do echo suppression. 1844136e2ac4eeca9b80a9da223f5256bba03f71c66Chia-chi Yeh if (corr2 > 0.1f && varX > 10000.0f) { 1852e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh int factor = (corr2 > 1.0f) ? 0 : (1.0f - sqrtf(corr2)) * 4096; 186c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh for (int i = 0; i < mSampleCount; ++i) { 1872e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh recorded[i] = recorded[i] * factor >> 16; 188c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 189c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 190c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh 191c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh // Increase RecordOffset. 192c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh ++mRecordOffset; 193c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh if (mRecordOffset == mRecordLength) { 194c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh mRecordOffset = 0; 195c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 196c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh} 197