EchoSuppressor.cpp revision 4136e2ac4eeca9b80a9da223f5256bba03f71c66
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> 20c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh#include <math.h> 21c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh 22c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh#define LOG_TAG "Echo" 23c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh#include <utils/Log.h> 24c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh 25c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh#include "EchoSuppressor.h" 26c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh 272e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh// It is very difficult to do echo cancellation at this level due to the lack of 282e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh// the timing information of the samples being played and recorded. Therefore, 292e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh// for the first release only echo suppression is implemented. 302e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh 312e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh// The algorithm is derived from the "previous works" summarized in 322e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh// A new class of doubletalk detectors based on cross-correlation, 332e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh// J Benesty, DR Morgan, JH Cho, IEEE Trans. on Speech and Audio Processing. 342e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh// The method proposed in that paper is not used because of its high complexity. 352e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh 362e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh// It is well known that cross-correlation can be computed using convolution, 372e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh// but unfortunately not every mobile processor has a (fast enough) FPU. Thus 382e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh// we use integer arithmetic as much as possible and do lots of bookkeeping. 392e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh// Again, parameters and thresholds are chosen by experiments. 402e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh 412e85359f74a5280ee733d35ff5f63b3943140632Chia-chi YehEchoSuppressor::EchoSuppressor(int sampleCount, int tailLength) 42c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh{ 432e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh tailLength += sampleCount * 4; 442e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh 452e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh int shift = 0; 462e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh while ((sampleCount >> shift) > 1 && (tailLength >> shift) > 256) { 472e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh ++shift; 48c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 49c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh 502e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mShift = shift + 4; 512e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mScale = 1 << shift; 52c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh mSampleCount = sampleCount; 532e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mWindowSize = sampleCount >> shift; 542e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mTailLength = tailLength >> shift; 552e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mRecordLength = tailLength * 2 / sampleCount; 56c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh mRecordOffset = 0; 57c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh 582e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mXs = new uint16_t[mTailLength + mWindowSize]; 592e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh memset(mXs, 0, sizeof(*mXs) * (mTailLength + mWindowSize)); 602e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mXSums = new uint32_t[mTailLength]; 612e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh memset(mXSums, 0, sizeof(*mXSums) * mTailLength); 622e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mX2Sums = new uint32_t[mTailLength]; 632e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh memset(mX2Sums, 0, sizeof(*mX2Sums) * mTailLength); 642e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mXRecords = new uint16_t[mRecordLength * mWindowSize]; 652e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh memset(mXRecords, 0, sizeof(*mXRecords) * mRecordLength * mWindowSize); 662e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh 672e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mYSum = 0; 682e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mY2Sum = 0; 692e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mYRecords = new uint32_t[mRecordLength]; 702e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh memset(mYRecords, 0, sizeof(*mYRecords) * mRecordLength); 712e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mY2Records = new uint32_t[mRecordLength]; 722e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh memset(mY2Records, 0, sizeof(*mY2Records) * mRecordLength); 732e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh 742e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mXYSums = new uint32_t[mTailLength]; 752e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh memset(mXYSums, 0, sizeof(*mXYSums) * mTailLength); 762e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mXYRecords = new uint32_t[mRecordLength * mTailLength]; 772e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh memset(mXYRecords, 0, sizeof(*mXYRecords) * mRecordLength * mTailLength); 78c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh 79c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh mLastX = 0; 80c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh mLastY = 0; 812e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mWeight = 1.0f / (mRecordLength * mWindowSize); 82c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh} 83c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh 84c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi YehEchoSuppressor::~EchoSuppressor() 85c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh{ 86c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh delete [] mXs; 872e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh delete [] mXSums; 882e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh delete [] mX2Sums; 892e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh delete [] mXRecords; 902e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh delete [] mYRecords; 912e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh delete [] mY2Records; 922e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh delete [] mXYSums; 93c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh delete [] mXYRecords; 94c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh} 95c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh 96c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yehvoid EchoSuppressor::run(int16_t *playbacked, int16_t *recorded) 97c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh{ 98c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh // Update Xs. 992e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh for (int i = mTailLength - 1; i >= 0; --i) { 1002e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mXs[i + mWindowSize] = mXs[i]; 101c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 1022e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh for (int i = mWindowSize - 1, j = 0; i >= 0; --i, j += mScale) { 1032e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh uint32_t sum = 0; 104c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh for (int k = 0; k < mScale; ++k) { 1052e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh int32_t x = playbacked[j + k] << 15; 106c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh mLastX += x; 1072e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh sum += ((mLastX >= 0) ? mLastX : -mLastX) >> 15; 1082e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mLastX -= (mLastX >> 10) + x; 109c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 1102e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mXs[i] = sum >> mShift; 111c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 112c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh 1132e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh // Update XSums, X2Sums, and XRecords. 1142e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh for (int i = mTailLength - mWindowSize - 1; i >= 0; --i) { 1152e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mXSums[i + mWindowSize] = mXSums[i]; 1162e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mX2Sums[i + mWindowSize] = mX2Sums[i]; 117c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 1182e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh uint16_t *xRecords = &mXRecords[mRecordOffset * mWindowSize]; 1192e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh for (int i = mWindowSize - 1; i >= 0; --i) { 1202e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh uint16_t x = mXs[i]; 1212e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mXSums[i] = mXSums[i + 1] + x - xRecords[i]; 1222e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mX2Sums[i] = mX2Sums[i + 1] + x * x - xRecords[i] * xRecords[i]; 1232e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh xRecords[i] = x; 124c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 125c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh 126c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh // Compute Ys. 1272e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh uint16_t ys[mWindowSize]; 1282e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh for (int i = mWindowSize - 1, j = 0; i >= 0; --i, j += mScale) { 1292e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh uint32_t sum = 0; 130c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh for (int k = 0; k < mScale; ++k) { 1312e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh int32_t y = recorded[j + k] << 15; 132c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh mLastY += y; 1332e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh sum += ((mLastY >= 0) ? mLastY : -mLastY) >> 15; 1342e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mLastY -= (mLastY >> 10) + y; 135c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 1362e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh ys[i] = sum >> mShift; 137c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 138c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh 1392e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh // Update YSum, Y2Sum, YRecords, and Y2Records. 1402e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh uint32_t ySum = 0; 1412e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh uint32_t y2Sum = 0; 1422e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh for (int i = mWindowSize - 1; i >= 0; --i) { 1432e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh ySum += ys[i]; 1442e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh y2Sum += ys[i] * ys[i]; 145c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 1462e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mYSum += ySum - mYRecords[mRecordOffset]; 1472e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mY2Sum += y2Sum - mY2Records[mRecordOffset]; 1482e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mYRecords[mRecordOffset] = ySum; 1492e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mY2Records[mRecordOffset] = y2Sum; 1502e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh 1512e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh // Update XYSums and XYRecords. 1522e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh uint32_t *xyRecords = &mXYRecords[mRecordOffset * mTailLength]; 1532e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh for (int i = mTailLength - 1; i >= 0; --i) { 1542e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh uint32_t xySum = 0; 1552e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh for (int j = mWindowSize - 1; j >= 0; --j) { 1562e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh xySum += mXs[i + j] * ys[j]; 157c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 1582e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh mXYSums[i] += xySum - xyRecords[i]; 1592e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh xyRecords[i] = xySum; 160c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 161c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh 1622e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh // Compute correlations. 163c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh int latency = 0; 1644136e2ac4eeca9b80a9da223f5256bba03f71c66Chia-chi Yeh float corr2 = 0.0f; 1654136e2ac4eeca9b80a9da223f5256bba03f71c66Chia-chi Yeh float varX = 0.0f; 1662e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh float varY = mY2Sum - mWeight * mYSum * mYSum; 1672e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh for (int i = mTailLength - 1; i >= 0; --i) { 1682e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh float cov = mXYSums[i] - mWeight * mXSums[i] * mYSum; 1694136e2ac4eeca9b80a9da223f5256bba03f71c66Chia-chi Yeh if (cov > 0.0f) { 1704136e2ac4eeca9b80a9da223f5256bba03f71c66Chia-chi Yeh float varXi = mX2Sums[i] - mWeight * mXSums[i] * mXSums[i]; 1714136e2ac4eeca9b80a9da223f5256bba03f71c66Chia-chi Yeh float corr2i = cov * cov / (varXi * varY + 1); 1724136e2ac4eeca9b80a9da223f5256bba03f71c66Chia-chi Yeh if (corr2i > corr2) { 1734136e2ac4eeca9b80a9da223f5256bba03f71c66Chia-chi Yeh varX = varXi; 1744136e2ac4eeca9b80a9da223f5256bba03f71c66Chia-chi Yeh corr2 = corr2i; 1754136e2ac4eeca9b80a9da223f5256bba03f71c66Chia-chi Yeh latency = i; 1764136e2ac4eeca9b80a9da223f5256bba03f71c66Chia-chi Yeh } 177c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 178c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 1794136e2ac4eeca9b80a9da223f5256bba03f71c66Chia-chi Yeh //LOGI("corr^2 %.5f, var %8.0f %8.0f, latency %d", corr2, varX, varY, 1804136e2ac4eeca9b80a9da223f5256bba03f71c66Chia-chi Yeh // latency * mScale); 181c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh 1822e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh // Do echo suppression. 1834136e2ac4eeca9b80a9da223f5256bba03f71c66Chia-chi Yeh if (corr2 > 0.1f && varX > 10000.0f) { 1842e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh int factor = (corr2 > 1.0f) ? 0 : (1.0f - sqrtf(corr2)) * 4096; 185c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh for (int i = 0; i < mSampleCount; ++i) { 1862e85359f74a5280ee733d35ff5f63b3943140632Chia-chi Yeh recorded[i] = recorded[i] * factor >> 16; 187c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 188c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 189c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh 190c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh // Increase RecordOffset. 191c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh ++mRecordOffset; 192c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh if (mRecordOffset == mRecordLength) { 193c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh mRecordOffset = 0; 194c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh } 195c7092775516e15983053a58b3b43ff3eb58ac46fChia-chi Yeh} 196