1 /* 2 * curvefit.h 3 * scorealign 4 * 5 * Created by Roger B. Dannenberg on 10/20/07. 6 * Copyright 2007 by Roger B. Dannenberg. All rights reserved. 7 * 8 * Dynamic programming does a good job of getting a rough alignment 9 * that is very good in a global sense, but there are often short-term 10 * "digressions" where the optimal path wanders off the "true" path. 11 * These digressions are hard to correct with simple smoothing. This 12 * module is intended to assert a "steady tempo" constraint to improve 13 * the path. It starts with the dynamic programming path, which is likely 14 * to be close to the correct path. The DP path (in pathx[] and pathy[]) 15 * is divided evenly into segments of approximately line_time seconds 16 * along the x axis. For a segment from x1 to x2, linear regression is 17 * performed on the DP path from x1 to x2. This specifies an initial 18 * line segment. Next, the end-points are joined by averaging: if 19 * the segment from x1 to x2 ends at y-end and the segment from x2 to x3 20 * starts at y-start, then the end of line x1--x2 and the beginning of 21 * line x2--x3 are adjusted to (y-end + y-start)/2. Now the fun starts: 22 * the endpoints of all the lines are adjusted up and down in order to 23 * minimize a distance function. The distance function estimates the 24 * integral of the distance matrix value along the line. Since the line 25 * falls between discrete points in the matrix, interpolation is used. 26 * The end result is converted back into a discrete path. (Maybe in the 27 * future, the pathx[]/pathy[] representation should be generalized to 28 * allow for non-integer path coordinates.) The resulting path will 29 * have steady tempo at least within each segment. What I hope will 30 * happen is that when there are chord changes or melody changes, there 31 * will be "narrow" pathways in the distance matrix. Getting the 32 * alignment wrong at these transitions will cost a lot. Other places 33 * are not so critical, which is why I think DP wanders off the true 34 * path. The straight-line path will ensure that for the most part, the 35 * score alignment is determined by the transitions, and where alignment 36 * is not critical, the alignment will avoid any rubato or over-fitting. 37 */ 38 39 void curve_fitting(Scorealign *sa, bool verbose); 40 41