Induction.java (11602B)
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 /* BeatRoot: An interactive beat tracking system 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 Free Software Foundation, Inc., 40 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. 41 */ 42 43 package be.tarsos.dsp.beatroot; 44 45 import java.util.ListIterator; 46 47 /** Performs tempo induction by finding clusters of similar 48 * inter-onset intervals (IOIs), ranking them according to the number 49 * of intervals and relationships between them, and returning a set 50 * of tempo hypotheses for initialising the beat tracking agents. 51 */ 52 public class Induction { 53 54 /** The maximum difference in IOIs which are in the same cluster */ 55 public static double clusterWidth = 0.025; 56 57 /** The minimum IOI for inclusion in a cluster */ 58 public static double minIOI = 0.070; 59 60 /** The maximum IOI for inclusion in a cluster */ 61 public static double maxIOI = 2.500; 62 63 /** The minimum inter-beat interval (IBI), i.e. the maximum tempo 64 * hypothesis that can be returned. 65 * 0.30 seconds == 200 BPM 66 * 0.25 seconds == 240 BPM 67 */ 68 public static double minIBI = 0.3; 69 70 /** The maximum inter-beat interval (IBI), i.e. the minimum tempo 71 * hypothesis that can be returned. 72 * 1.00 seconds == 60 BPM 73 * 0.75 seconds == 80 BPM 74 * 0.60 seconds == 100 BPM 75 */ 76 public static double maxIBI = 1.0; // 60BPM // was 0.75 => 80 77 78 /** The maximum number of tempo hypotheses to return */ 79 public static int topN = 10; 80 81 /** Flag to enable debugging output */ 82 public static boolean debug = false; 83 84 /** Performs tempo induction (see JNMR 2001 paper by Simon Dixon for details). 85 * @param events The onsets (or other events) from which the tempo is induced 86 * @return A list of beat tracking agents, where each is initialised with one 87 * of the top tempo hypotheses but no beats 88 */ 89 public static AgentList beatInduction(EventList events) { 90 int i, j, b, bestCount; 91 boolean submult; 92 int intervals = 0; // number of interval clusters 93 int[] bestn = new int[topN];// count of high-scoring clusters 94 double ratio, err; 95 int degree; 96 int maxClusterCount = (int) Math.ceil((maxIOI - minIOI) / clusterWidth); 97 double[] clusterMean = new double[maxClusterCount]; 98 int[] clusterSize = new int[maxClusterCount]; 99 int[] clusterScore = new int[maxClusterCount]; 100 101 ListIterator<Event> ptr1, ptr2; 102 Event e1,e2; 103 ptr1 = events.listIterator(); 104 while (ptr1.hasNext()) { 105 e1 = ptr1.next(); 106 ptr2 = events.listIterator(); 107 e2 = ptr2.next(); 108 while (e2 != e1) 109 e2 = ptr2.next(); 110 while (ptr2.hasNext()) { 111 e2 = ptr2.next(); 112 double ioi = e2.keyDown - e1.keyDown; 113 if (ioi < minIOI) // skip short intervals 114 continue; 115 if (ioi > maxIOI) // ioi too long 116 break; 117 for (b = 0; b < intervals; b++) // assign to nearest cluster 118 if (Math.abs(clusterMean[b] - ioi) < clusterWidth) { 119 if ((b < intervals - 1) && ( 120 Math.abs(clusterMean[b+1] - ioi) < 121 Math.abs(clusterMean[b] - ioi))) 122 b++; // next cluster is closer 123 clusterMean[b] = (clusterMean[b] * clusterSize[b] +ioi)/ 124 (clusterSize[b] + 1); 125 clusterSize[b]++; 126 break; 127 } 128 if (b == intervals) { // no suitable cluster; create new one 129 if (intervals == maxClusterCount) { 130 System.err.println("Warning: Too many clusters"); 131 continue; // ignore this IOI 132 } 133 intervals++; 134 for ( ; (b>0) && (clusterMean[b-1] > ioi); b--) { 135 clusterMean[b] = clusterMean[b-1]; 136 clusterSize[b] = clusterSize[b-1]; 137 } 138 clusterMean[b] = ioi; 139 clusterSize[b] = 1; 140 } 141 } 142 } 143 if (debug) { // output IOI histogram in Matlab format 144 System.out.println("Inter-onset interval histogram:\n" + 145 "StartMatlabCode\n" + 146 "ioi = ["); 147 for (b = 0; b < intervals; b++) 148 System.out.printf("%4d %7.3f %7d\n", 149 b, clusterMean[b], clusterSize[b]); 150 System.out.println("]; ioiclusters(ioi, name);\nEndMatlabCode\n"); 151 } 152 for (b = 0; b < intervals; b++) // merge similar intervals 153 // TODO: they are now in order, so don't need the 2nd loop 154 // TODO: check BOTH sides before averaging or upper gps don't work 155 for (i = b+1; i < intervals; i++) 156 if (Math.abs(clusterMean[b] - clusterMean[i]) < clusterWidth) { 157 clusterMean[b] = (clusterMean[b] * clusterSize[b] + 158 clusterMean[i] * clusterSize[i]) / 159 (clusterSize[b] + clusterSize[i]); 160 clusterSize[b] = clusterSize[b] + clusterSize[i]; 161 --intervals; 162 for (j = i+1; j <= intervals; j++) { 163 clusterMean[j-1] = clusterMean[j]; 164 clusterSize[j-1] = clusterSize[j]; 165 } 166 } 167 if (intervals == 0) 168 return new AgentList(); 169 for (b = 0; b < intervals; b++) 170 clusterScore[b] = 10 * clusterSize[b]; 171 bestn[0] = 0; 172 bestCount = 1; 173 for (b = 0; b < intervals; b++) 174 for (i = 0; i <= bestCount; i++) 175 if ((i < topN) && ((i == bestCount) || 176 (clusterScore[b] > clusterScore[bestn[i]]))){ 177 if (bestCount < topN) 178 bestCount++; 179 for (j = bestCount - 1; j > i; j--) 180 bestn[j] = bestn[j-1]; 181 bestn[i] = b; 182 break; 183 } 184 if (debug) { 185 System.out.println("Best " + bestCount + " clusters (before):"); 186 for (b = 0; b < bestCount; b++) 187 System.out.printf("%5.3f : %5d\n", clusterMean[bestn[b]], 188 clusterScore[bestn[b]]); 189 } 190 for (b = 0; b < intervals; b++) // score intervals 191 for (i = b+1; i < intervals; i++) { 192 ratio = clusterMean[b] / clusterMean[i]; 193 submult = ratio < 1; 194 if (submult) 195 degree = (int) Math.round(1/ratio); 196 else 197 degree = (int) Math.round(ratio); 198 if ((degree >= 2) && (degree <= 8)) { 199 if (submult) 200 err = Math.abs(clusterMean[b]*degree - clusterMean[i]); 201 else 202 err = Math.abs(clusterMean[b] - clusterMean[i]*degree); 203 if (err < (submult? clusterWidth : clusterWidth * degree)) { 204 if (degree >= 5) 205 degree = 1; 206 else 207 degree = 6 - degree; 208 clusterScore[b] += degree * clusterSize[i]; 209 clusterScore[i] += degree * clusterSize[b]; 210 } 211 } 212 } 213 if (debug) { 214 System.out.println("Best " + bestCount + " clusters (after):"); 215 for (b = 0; (b < bestCount); b++) 216 System.out.printf("%5.3f : %5d\n", clusterMean[bestn[b]], 217 clusterScore[bestn[b]]); 218 } 219 if (debug) { 220 System.out.println("Inter-onset interval histogram 2:"); 221 for (b = 0; b < intervals; b++) 222 System.out.printf("%3d: %5.3f : %3d (score: %5d)\n", 223 b, clusterMean[b], clusterSize[b], clusterScore[b]); 224 } 225 226 AgentList a = new AgentList(); 227 for (int index = 0; index < bestCount; index++) { 228 b = bestn[index]; 229 // Adjust it, using the size of super- and sub-intervals 230 double newSum = clusterMean[b] * clusterScore[b]; 231 //int newCount = clusterSize[b]; 232 int newWeight = clusterScore[b]; 233 for (i = 0; i < intervals; i++) { 234 if (i == b) 235 continue; 236 ratio = clusterMean[b] / clusterMean[i]; 237 if (ratio < 1) { 238 degree = (int) Math.round(1 / ratio); 239 if ((degree >= 2) && (degree <= 8)) { 240 err = Math.abs(clusterMean[b]*degree - clusterMean[i]); 241 if (err < clusterWidth) { 242 newSum += clusterMean[i] / degree * clusterScore[i]; 243 //newCount += clusterSize[i]; 244 newWeight += clusterScore[i]; 245 } 246 } 247 } else { 248 degree = (int) Math.round(ratio); 249 if ((degree >= 2) && (degree <= 8)) { 250 err = Math.abs(clusterMean[b] - degree*clusterMean[i]); 251 if (err < clusterWidth * degree) { 252 newSum += clusterMean[i] * degree * clusterScore[i]; 253 //newCount += clusterSize[i]; 254 newWeight += clusterScore[i]; 255 } 256 } 257 } 258 } 259 double beat = newSum / newWeight; 260 // Scale within range ... hope the grouping isn't ternary :( 261 while (beat < minIBI) // Maximum speed 262 beat *= 2.0; 263 while (beat > maxIBI) // Minimum speed 264 beat /= 2.0; 265 if (beat >= minIBI) { 266 a.add(new Agent(beat)); 267 if (debug) 268 System.out.printf(" %5.3f", beat); 269 } 270 } 271 if (debug) 272 System.out.println(" IBI"); 273 return a; 274 } // beatInduction() 275 276 /** For variable cluster widths in newInduction(). 277 * @param low The lowest IOI allowed in the cluster 278 * @return The highest IOI allowed in the cluster 279 */ 280 protected static int top(int low) { 281 return low + 25; // low/10; 282 } // top() 283 284 /** An alternative (incomplete) tempo induction method (not used). 285 * Uses integer (millisecond) resolution. 286 * @param events The events on which tempo induction is performed 287 */ 288 public static void newInduction(EventList events) { 289 final int MAX_MS = 2500; 290 int[] count = new int[MAX_MS]; 291 for (int i=0; i < MAX_MS; i++) 292 count[i] = 0; 293 ListIterator<Event> ptr1, ptr2; 294 Event e1,e2; 295 ptr1 = events.listIterator(); 296 while (ptr1.hasNext()) { 297 e1 = ptr1.next(); 298 ptr2 = events.listIterator(); 299 e2 = ptr2.next(); 300 while (e2 != e1) 301 e2 = ptr2.next(); 302 while (ptr2.hasNext()) { 303 e2 = ptr2.next(); 304 int diff = (int) Math.round((e1.keyDown - e2.keyDown) * 1000); 305 if (diff < MAX_MS) 306 count[diff]++; 307 else 308 break; 309 } 310 } 311 int clnum; 312 final int MAX_CL = 10; 313 int[] cluster = new int[MAX_CL]; 314 int[] csize = new int[MAX_CL]; 315 for (clnum = 0; clnum < MAX_CL; clnum++) { 316 int sum = 0; 317 int max = 0; 318 int maxp = 0; 319 int hi = 70; 320 int lo = hi; 321 while (hi < MAX_MS) { 322 if (hi >= top(lo)) 323 sum -= count[lo++]; 324 else { 325 sum += count[hi++]; 326 if (sum > max) { 327 max = sum; 328 maxp = lo; 329 } 330 } 331 } 332 if (max == 0) 333 break; 334 hi = top(maxp); 335 if (hi > MAX_MS) 336 hi = MAX_MS; 337 int cnt = sum = 0; 338 for (lo = maxp; lo < hi; lo++) { 339 sum += lo * count[lo]; 340 cnt += count[lo]; 341 count[lo] = 0; 342 } 343 if (cnt != max) 344 System.err.println("Rounding error in newInduction"); 345 cluster[clnum] = sum / cnt; 346 csize[clnum] = cnt; 347 System.out.printf(" %5.3f", sum / 1000.0 / cnt); 348 //System.out.println("Cluster " + (clnum+1) ": " + (sum/cnt) + 349 // "ms (" + cnt + " intervals)"); 350 } 351 System.out.println(" IBI"); 352 // System.out.println("END OF NEW_INDUCTION"); 353 } // newInduction() 354 355 } // class Induction