Peaks.java (7370B)
1 /* 2 * _______ _____ _____ _____ 3 * |__ __| | __ \ / ____| __ \ 4 * | | __ _ _ __ ___ ___ ___| | | | (___ | |__) | 5 * | |/ _` | '__/ __|/ _ \/ __| | | |\___ \| ___/ 6 * | | (_| | | \__ \ (_) \__ \ |__| |____) | | 7 * |_|\__,_|_| |___/\___/|___/_____/|_____/|_| 8 * 9 * ------------------------------------------------------------- 10 * 11 * TarsosDSP is developed by Joren Six at IPEM, University Ghent 12 * 13 * ------------------------------------------------------------- 14 * 15 * Info: http://0110.be/tag/TarsosDSP 16 * Github: https://github.com/JorenSix/TarsosDSP 17 * Releases: http://0110.be/releases/TarsosDSP/ 18 * 19 * TarsosDSP includes modified source code by various authors, 20 * for credits and info, see README. 21 * 22 */ 23 24 /* 25 Copyright (C) 2001, 2006 by Simon Dixon 26 27 This program is free software; you can redistribute it and/or modify 28 it under the terms of the GNU General Public License as published by 29 the Free Software Foundation; either version 2 of the License, or 30 (at your option) any later version. 31 32 This program is distributed in the hope that it will be useful, 33 but WITHOUT ANY WARRANTY; without even the implied warranty of 34 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 35 GNU General Public License for more details. 36 37 You should have received a copy of the GNU General Public License along 38 with this program (the file gpl.txt); if not, download it from 39 http://www.gnu.org/licenses/gpl.txt or write to the 40 Free Software Foundation, Inc., 41 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. 42 */ 43 44 package be.tarsos.dsp.beatroot; 45 46 import java.util.LinkedList; 47 48 public class Peaks { 49 50 public static boolean debug = false; 51 public static int pre = 3; 52 public static int post = 1; 53 54 /** 55 * General peak picking method for finding n local maxima in an array 56 * @param data input data 57 * @param peaks list of peak indexes 58 * @param width minimum distance between peaks 59 * @return The number of peaks found 60 */ 61 public static int findPeaks(double[] data, int[] peaks, int width) { 62 int peakCount = 0; 63 int maxp = 0; 64 int mid = 0; 65 int end = data.length; 66 while (mid < end) { 67 int i = mid - width; 68 if (i < 0) 69 i = 0; 70 int stop = mid + width + 1; 71 if (stop > data.length) 72 stop = data.length; 73 maxp = i; 74 for (i++; i < stop; i++) 75 if (data[i] > data[maxp]) 76 maxp = i; 77 if (maxp == mid) { 78 int j; 79 for (j = peakCount; j > 0; j--) { 80 if (data[maxp] <= data[peaks[j-1]]) 81 break; 82 else if (j < peaks.length) 83 peaks[j] = peaks[j-1]; 84 } 85 if (j != peaks.length) 86 peaks[j] = maxp; 87 if (peakCount != peaks.length) 88 peakCount++; 89 } 90 mid++; 91 } 92 return peakCount; 93 } // findPeaks() 94 95 /** General peak picking method for finding local maxima in an array 96 * @param data input data 97 * @param width minimum distance between peaks 98 * @param threshold minimum value of peaks 99 * @return list of peak indexes 100 */ 101 public static LinkedList<Integer> findPeaks(double[] data, int width, 102 double threshold) { 103 return findPeaks(data, width, threshold, 0, false); 104 } // findPeaks() 105 106 /** General peak picking method for finding local maxima in an array 107 * @param data input data 108 * @param width minimum distance between peaks 109 * @param threshold minimum value of peaks 110 * @param decayRate how quickly previous peaks are forgotten 111 * @param isRelative minimum value of peaks is relative to local average 112 * @return list of peak indexes 113 */ 114 public static LinkedList<Integer> findPeaks(double[] data, int width, 115 double threshold, double decayRate, boolean isRelative) { 116 LinkedList<Integer> peaks = new LinkedList<Integer>(); 117 int maxp = 0; 118 int mid = 0; 119 int end = data.length; 120 double av = data[0]; 121 while (mid < end) { 122 av = decayRate * av + (1 - decayRate) * data[mid]; 123 if (av < data[mid]) 124 av = data[mid]; 125 int i = mid - width; 126 if (i < 0) 127 i = 0; 128 int stop = mid + width + 1; 129 if (stop > data.length) 130 stop = data.length; 131 maxp = i; 132 for (i++; i < stop; i++) 133 if (data[i] > data[maxp]) 134 maxp = i; 135 if (maxp == mid) { 136 if (overThreshold(data, maxp, width, threshold, isRelative,av)){ 137 if (debug) 138 System.out.println(" peak"); 139 peaks.add(new Integer(maxp)); 140 } else if (debug) 141 System.out.println(); 142 } 143 mid++; 144 } 145 return peaks; 146 } // findPeaks() 147 148 public static double expDecayWithHold(double av, double decayRate, 149 double[] data, int start, int stop) { 150 while (start < stop) { 151 av = decayRate * av + (1 - decayRate) * data[start]; 152 if (av < data[start]) 153 av = data[start]; 154 start++; 155 } 156 return av; 157 } // expDecayWithHold() 158 159 public static boolean overThreshold(double[] data, int index, int width, 160 double threshold, boolean isRelative, 161 double av) { 162 if (debug) 163 System.out.printf("%4d : %6.3f Av1: %6.3f ", 164 index, data[index], av); 165 if (data[index] < av) 166 return false; 167 if (isRelative) { 168 int iStart = index - pre * width; 169 if (iStart < 0) 170 iStart = 0; 171 int iStop = index + post * width; 172 if (iStop > data.length) 173 iStop = data.length; 174 double sum = 0; 175 int count = iStop - iStart; 176 while (iStart < iStop) 177 sum += data[iStart++]; 178 if (debug) 179 System.out.printf(" %6.3f %6.3f ", sum / count, 180 data[index] - sum / count - threshold); 181 return (data[index] > sum / count + threshold); 182 } else 183 return (data[index] > threshold); 184 } // overThreshold() 185 186 public static void normalise(double[] data) { 187 double sx = 0; 188 double sxx = 0; 189 for (int i = 0; i < data.length; i++) { 190 sx += data[i]; 191 sxx += data[i] * data[i]; 192 } 193 double mean = sx / data.length; 194 double sd = Math.sqrt((sxx - sx * mean) / data.length); 195 if (sd == 0) 196 sd = 1; // all data[i] == mean -> 0; avoids div by 0 197 for (int i = 0; i < data.length; i++) { 198 data[i] = (data[i] - mean) / sd; 199 } 200 } // normalise() 201 202 /** Uses an n-point linear regression to estimate the slope of data. 203 * @param data input data 204 * @param hop spacing of data points 205 * @param n length of linear regression 206 * @param slope output data 207 */ 208 public static void getSlope(double[] data, double hop, int n, 209 double[] slope) { 210 int i = 0, j = 0; 211 double t; 212 double sx = 0, sxx = 0, sy = 0, sxy = 0; 213 for ( ; i < n; i++) { 214 t = i * hop; 215 sx += t; 216 sxx += t * t; 217 sy += data[i]; 218 sxy += t * data[i]; 219 } 220 double delta = n * sxx - sx * sx; 221 for ( ; j < n / 2; j++) 222 slope[j] = (n * sxy - sx * sy) / delta; 223 for ( ; j < data.length - (n + 1) / 2; j++, i++) { 224 slope[j] = (n * sxy - sx * sy) / delta; 225 sy += data[i] - data[i - n]; 226 sxy += hop * (n * data[i] - sy); 227 } 228 for ( ; j < data.length; j++) 229 slope[j] = (n * sxy - sx * sy) / delta; 230 } // getSlope() 231 232 public static double min(double[] arr) { return arr[imin(arr)]; } 233 234 public static double max(double[] arr) { return arr[imax(arr)]; } 235 236 public static int imin(double[] arr) { 237 int i = 0; 238 for (int j = 1; j < arr.length; j++) 239 if (arr[j] < arr[i]) 240 i = j; 241 return i; 242 } // imin() 243 244 public static int imax(double[] arr) { 245 int i = 0; 246 for (int j = 1; j < arr.length; j++) 247 if (arr[j] > arr[i]) 248 i = j; 249 return i; 250 } // imax() 251 252 } // class Peaks