1 /*
2  * Copyright (C) 2015 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package org.drrickorang.loopback;
18 
19 import android.os.Bundle;
20 import android.os.Parcel;
21 import android.os.Parcelable;
22 import android.util.Log;
23 
24 
25 /**
26  * This class is used to automatically estimate latency and its confidence.
27  */
28 
29 public class Correlation implements Parcelable {
30     private static final String TAG = "Correlation";
31 
32     private int       mBlockSize = Constant.DEFAULT_CORRELATION_BLOCK_SIZE;
33     private int       mSamplingRate;
34     private double [] mDataDownsampled;
35     private double [] mDataAutocorrelated;
36 
37     public double mEstimatedLatencySamples = 0;
38     public double mEstimatedLatencyMs = 0;
39     public double mEstimatedLatencyConfidence = 0.0;
40     public double mAverage = 0.0;
41     public double mRms = 0.0;
42 
43     private double mAmplitudeThreshold = 0.001;  // 0.001 = -60 dB noise
44 
45     private boolean mDataIsValid = false; // Used to mark computed latency information is available
46 
Correlation()47     public Correlation() {
48         // Default constructor for when no data will be restored
49 
50     }
51 
init(int blockSize, int samplingRate)52     public void init(int blockSize, int samplingRate) {
53         setBlockSize(blockSize);
54         mSamplingRate = samplingRate;
55     }
56 
computeCorrelation(double [] data, int samplingRate)57     public void computeCorrelation(double [] data, int samplingRate) {
58         log("Started Auto Correlation for data with " + data.length + " points");
59         mSamplingRate = samplingRate;
60         mDataDownsampled = new double [mBlockSize];
61         mDataAutocorrelated = new double[mBlockSize];
62         downsampleData(data, mDataDownsampled, mAmplitudeThreshold);
63 
64         //correlation vector
65         autocorrelation(mDataDownsampled, mDataAutocorrelated);
66 
67 
68         int N = data.length; //all samples available
69         double groupSize =  (double) N / mBlockSize;  //samples per downsample point.
70 
71         double maxValue = 0;
72         int maxIndex = -1;
73 
74         double minLatencyMs = 8; //min latency expected. This algorithm should be improved.
75         int minIndex = (int) (0.5 + minLatencyMs * mSamplingRate / (groupSize * 1000));
76 
77         double average = 0;
78         double rms = 0;
79 
80         //find max
81         for (int i = minIndex; i < mDataAutocorrelated.length; i++) {
82             average += mDataAutocorrelated[i];
83             rms += mDataAutocorrelated[i] * mDataAutocorrelated[i];
84            if (mDataAutocorrelated[i] > maxValue) {
85                maxValue = mDataAutocorrelated[i];
86                maxIndex = i;
87            }
88         }
89 
90         rms = Math.sqrt(rms / mDataAutocorrelated.length);
91         average = average / mDataAutocorrelated.length;
92         log(String.format(" Maxvalue %f, max Index : %d/%d (%d)  minIndex = %d", maxValue, maxIndex,
93                           mDataAutocorrelated.length, data.length, minIndex));
94         log(String.format("  average : %.3f  rms: %.3f", average, rms));
95 
96         mAverage = average;
97         mRms = rms;
98 
99         mEstimatedLatencyConfidence = 0.0;
100         if (average > 0) {
101             double factor = 3.0;
102 
103             double raw = (rms - average) / (factor * average);
104             log(String.format("Raw: %.3f", raw));
105             mEstimatedLatencyConfidence = Math.max(Math.min(raw, 1.0), 0.0);
106         }
107         log(String.format(" ****Confidence: %.2f", mEstimatedLatencyConfidence));
108 
109         mEstimatedLatencySamples = maxIndex * groupSize;
110         mEstimatedLatencyMs = mEstimatedLatencySamples * 1000 / mSamplingRate;
111         log(String.format(" latencySamples: %.2f  %.2f ms", mEstimatedLatencySamples,
112                           mEstimatedLatencyMs));
113 
114         mDataIsValid = mEstimatedLatencyMs > 0.0001;
115     }
116 
117     // Called by LoopbackActivity before displaying latency test results
isValid()118     public boolean isValid() {
119         return mDataIsValid;
120     }
121 
122     // Called at beginning of new test
invalidate()123     public void invalidate() {
124         mDataIsValid = false;
125     }
126 
setBlockSize(int blockSize)127     public void setBlockSize(int blockSize) {
128         mBlockSize = clamp(blockSize, Constant.CORRELATION_BLOCK_SIZE_MIN,
129                 Constant.CORRELATION_BLOCK_SIZE_MAX);
130     }
131 
downsampleData(double [] data, double [] dataDownsampled, double threshold)132     private boolean downsampleData(double [] data, double [] dataDownsampled, double threshold) {
133         log("Correlation block size used in down sample: " + mBlockSize);
134 
135         boolean status;
136         for (int i = 0; i < mBlockSize; i++) {
137             dataDownsampled[i] = 0;
138         }
139 
140         int N = data.length; //all samples available
141         double groupSize =  (double) N / mBlockSize;
142 
143         int ignored = 0;
144 
145         int currentIndex = 0;
146         double nextGroup = groupSize;
147         for (int i = 0; i < N && currentIndex < mBlockSize; i++) {
148 
149             if (i > nextGroup) { //advanced to next group.
150                 currentIndex++;
151                 nextGroup += groupSize;
152             }
153 
154             if (currentIndex >= mBlockSize) {
155                 break;
156             }
157 
158             double value =  Math.abs(data[i]);
159             if (value >= threshold) {
160                 dataDownsampled[currentIndex] += value;
161             } else {
162                 ignored++;
163             }
164         }
165 
166         log(String.format(" Threshold: %.3f, ignored:%d/%d (%%.2f)",
167                 threshold, ignored, N, (double) ignored/(double)N));
168 
169         status = true;
170         return status;
171     }
172 
173 
autocorrelation(double [] data, double [] dataOut)174     private boolean autocorrelation(double [] data, double [] dataOut) {
175         boolean status = false;
176 
177         double sumsquared = 0;
178         int N = data.length;
179         for (int i = 0; i < N; i++) {
180             double value = data[i];
181             sumsquared += value * value;
182         }
183 
184         if (sumsquared > 0) {
185             //correlate (not circular correlation)
186             for (int i = 0; i < N; i++) {
187                 dataOut[i] = 0;
188                 for (int j = 0; j < N - i; j++) {
189 
190                     dataOut[i] += data[j] * data[i + j];
191                 }
192                 dataOut[i] = dataOut[i] / sumsquared;
193             }
194             status = true;
195         }
196 
197         return status;
198     }
199 
200     /**
201      * Returns value if value is within inclusive bounds min through max
202      * otherwise returns min or max according to if value is less than or greater than the range
203      */
204     // TODO move to audio_utils
clamp(int value, int min, int max)205     private int clamp(int value, int min, int max) {
206 
207         if (max < min) throw new UnsupportedOperationException("min must be <= max");
208 
209         if (value < min) return min;
210         else if (value > max) return max;
211         else return value;
212     }
213 
214     @Override
describeContents()215     public int describeContents() {
216         return 0;
217     }
218 
219     // Store the results before this object is destroyed
220     @Override
writeToParcel(Parcel dest, int flags)221     public void writeToParcel(Parcel dest, int flags) {
222         Bundle bundle = new Bundle();
223         bundle.putBoolean("mDataIsValid", mDataIsValid);
224         if (mDataIsValid) {
225             bundle.putDouble("mEstimatedLatencySamples", mEstimatedLatencySamples);
226             bundle.putDouble("mEstimatedLatencyMs", mEstimatedLatencyMs);
227             bundle.putDouble("mEstimatedLatencyConfidence", mEstimatedLatencyConfidence);
228             bundle.putDouble("mAverage", mAverage);
229             bundle.putDouble("mRms", mRms);
230         }
231         dest.writeBundle(bundle);
232     }
233 
234     // Restore the results which were previously calculated
Correlation(Parcel in)235     private Correlation(Parcel in) {
236         Bundle bundle = in.readBundle(getClass().getClassLoader());
237         mDataIsValid = bundle.getBoolean("mDataIsValid");
238         if (mDataIsValid) {
239             mEstimatedLatencySamples    = bundle.getDouble("mEstimatedLatencySamples");
240             mEstimatedLatencyMs         = bundle.getDouble("mEstimatedLatencyMs");
241             mEstimatedLatencyConfidence = bundle.getDouble("mEstimatedLatencyConfidence");
242             mAverage                    = bundle.getDouble("mAverage");
243             mRms                        = bundle.getDouble("mRms");
244         }
245     }
246 
247     public static final Parcelable.Creator<Correlation> CREATOR
248             = new Parcelable.Creator<Correlation>() {
249         public Correlation createFromParcel(Parcel in) {
250             return new Correlation(in);
251         }
252 
253         public Correlation[] newArray(int size) {
254             return new Correlation[size];
255         }
256     };
257 
log(String msg)258     private static void log(String msg) {
259         Log.v(TAG, msg);
260     }
261 
262 }
263