官术网_书友最值得收藏!

DTW

Despite its Sci-Fi name, DTW has little to do with time travel, except for the fact that this technique was popular for speech recognition back in the 1980s. Imagine two signals as two springs oriented along the time axis. We place them next to each other on the table, and want to measure how similar (or how different... what's the same?) they are. One of them will serve as a template. And we start stretching and compressing another one, piece by piece, until it looks exactly as the first one (or the most similar). Then we account for how much effort we put into align two springs—we sum up all tensions and stretches together, and get the DTW distance.

DTW distance between two sound signals tells us how similar to each other they are. For example, having the record of an unknown voice command, we can compare it to voice commands in the database, and find the most similar one. DTW can be used not only with audio, but with many other types of signals. We will use it to calculate distance between signals from motion sensors:

  
Figure 3.3: DTW alignment of two accelerometer signals. On the left: walking sample against another walking sample. On the right: brushing teeth against walking. The shorter the alignment is, the closer the two signals are to one another. Plots created using [1] and [2].

Let's demonstrate this with a simple example. Say we have two arrays: [5, 2, 1, 3] and [10, 2, 4, 3]. How do we calculate the distance between two arrays of length one: [5] and [10]? You can use squared difference as a measure; for example, (5 - 10)= 25. Okay, now let's extend one of them: [5, 2] and [10], and calculate the cumulative difference:

Let's extend another array to have [5, 2] and [10, 2]. Now, how to calculate the cumulative difference is not as clear as it was before, but let's assume that we are interested in the simplest way to transform one array into another (minimal distance, in other words):

By extending arrays in such a way further, eventually we will get the following table:

The bottom-right cell of the table contains the quantity we're interested in: DTW distance between two arrays, the measure of how hard it is to transform one array into another. We've just checked all the possible ways to transform arrays, and found the easiest of them (marked with a gray shading in the table). Movement along the diagonal of the table indicates the perfect match between arrays, while horizontal direction stands for deletion of the elements from the first array, and vertical movement indicates insertion into it (compare with Figure 3.3). The final array alignment looks like this:

[5, 2, 1, 3, -]

[10, 2, -, 4, 3]

By the way, DTW can be applied not only to arrays of single numbers. Replace squared difference with Euclidean or Manhattan distance, and you can compare trajectories in a three-dimensional space or taxi routes.
主站蜘蛛池模板: 濮阳县| 年辖:市辖区| 马边| 平罗县| 汾阳市| 多伦县| 富蕴县| 喀什市| 昆明市| 高要市| 长沙市| 探索| 清流县| 吉隆县| 铅山县| 嫩江县| 象州县| 亳州市| 察雅县| 保德县| 普安县| 玉田县| 巴南区| 天镇县| 忻州市| 莱芜市| 康定县| 祥云县| 镇沅| 抚远县| 石河子市| 天镇县| 阿克苏市| 固原市| 碌曲县| 石台县| 嘉荫县| 江都市| 兰西县| 安阳县| 新田县|