Dynamic time warping (DTW)
Dynamic time warping (DTW) is an elastic matching algorithm used in pattern recognition. DTW finds the optimal warp path between two time series. 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 are two points A and B from each other in a geometric space. We commonly use the Euclidian distance which draws a direct line between the pair of points. In the following figure, we can see different kinds of paths between the points A and B such as the Euclidian distance (with the arrow) but also we see the Manhattan (or taxicab) distance (with the dotted lines), which simulate the way a New York taxi moves through the buildings.
DTW is used to define similarity between time series for classification, in this example, we will implement the same metric with sequences of pixels. We can say that if the distance between the sequence A and B is small, these...
