Dynamic time warping

Dynamic Time Warping (DTW) is an elastic matching algorithm used in pattern recognition. DTW finds the optimal warp path between two vectors. DTW is used as a distance metric often implemented in speech recognition, data mining, robotics, and in this case, image similarity. The distance metric measures how far from each other two points, A and B, are in a geometric space. We commonly use the Euclidian Distance, which draws a direct line between a pair of points. In the following image, we might see different kinds of paths between point A and B, such as the Euclidian distance (with the arrow), but we also see the Manhattan (or taxicab) distance (with the dotted lines). Imagine that you are looking for the shortest path to a destination—the straight line will not work due to all the buildings, so the Taxicab distance simulates the way a New York taxi navigates through the buildings, as shown in the following diagram:

DTW is used to define the similarity between time...