84:
74:
53:
185:
158:
253:
22:
349:
The displayed algorithm is actually the
Levenstein distance. The Levenstein or string edit distance is a particular case of DTW, when the sequences consist of discrete symbol, and the distance between any two different symbols (including the 'empty' symbol) is 1, and 0 for identical symbols. However,
443:
About locality constraint.. Consider algorithm with following parameters: n=10, m=20, w=5, which means "min(m, i+w)" is always i+w, so DTW which is returned by DTWDistance-with-locality-constraint function will always be infinity. So if the algorithm with locality constraint is correct (prooflink?),
427:
The thing is that if you serialize a 2d sequence (e.g., concatenate the rows of an image), you loose the connections between each pixel and its neighbors above and below, and can match only in the horizontal direction, each row indepent of the other rows. For example, if you want to match the pixels
289:
I think that it would be useful if the formal definition was given, instead of just a code implementation. The code is useful, but it would be easier to understand if the formal definition was given first. Also, it would be useful if there was a formal derivation of the algorithm, with proof given
411:
This statement seems to be false: "The extension of the problem for two-dimensional "series" like images (planar warping) is NP-complete, while the problem for one-dimensional signals like time series can be solved in polynomial time." All 2-D, n-D series can be serialized (and usually are). The
557:
Probably there is an error in the first algorithm. According to V.Athitsos et al, "Approximate embedding...", section 3.3, equation (8) the first boundary condition should be 0 instead of infinity: DTWÂ := 0. I tested this in Matlab, and with this correction it actually produces better results.
664:
The figure showing a matching between two piecewise linear curves does not show an optimal matching, since it can be improved by assigning the 4th vertex of the upper curve to the 3rd vertex of the lower curve. (The left ends are counted as 1st vertices).
644:
that was calculated wrongly. It is quite clear that one can find a middle node of the optimal warping path and then recurse on the two new subproblems, as it is simply a shortest path problem in a planar grid graph.
140:
308:
I believe that the second algorithm is wrong. As it is, it reads unitialized memory when j=i-w or j=i+w. A simple solution would be to initialize the whole matrix with infinity.
721:
458:
Finding an average sequence with regard to DTW has been proven to be hard, but required for many statistical and data mining issues. Should we add something about it?
706:
696:
243:
233:
130:
716:
267:
106:
691:
526:
357:
395:
377:
309:
209:
701:
614:
594:
330:
573:
Series start at s and t. If anything in row or column 0 (except DTW) is not infinity, the algorithm will produce out-of-bounds matches.
711:
350:
in its most general form, the sequences may consist of continuous feature vectors. I think this should be made clear in the page.
97:
58:
731:
492:
192:
163:
726:
262:
168:
640:
be used to compute the DTW cost in linear space. This claim seems to be wrong as it relies on an example from the paper
33:
530:
381:
361:
399:
313:
634:
618:
598:
334:
463:
205:
323:
The distance d is defined in the text, please don't pass it as a matrix to the function. That's silly.
39:
83:
522:
480:
459:
449:
445:
353:
326:
563:
484:
21:
650:
488:
294:
208:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
105:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
89:
73:
52:
559:
673:
578:
546:
508:
477:
Please, someone, fix the formatting where it talks about "bold" it doesn't show in the code.
372:
The algorithms look almost identical. Prehaps a translation of both into C would claify this?
298:
654:
293:
It would be nice if there was an example or note how can be the DTW array used afterwards.
646:
417:
685:
433:
669:
574:
542:
504:
345:
Can someone please explain the difference between DTW and
Levenshtein distance?
102:
677:
622:
602:
582:
567:
550:
534:
512:
496:
467:
453:
437:
421:
403:
385:
365:
338:
317:
302:
252:
184:
157:
79:
613:
A very simple example with concrete numbers/symbols would be useful. —DIV (
413:
201:
593:
It isn't clear why return DTW is returned, rather than return DTW. —DIV (
429:
197:
519:
Why is DTW = 0 in the first algorithm instead of DTW = d(s, t)? --
394:
The obviousness escapes me. You can't compare two pseudocodes.
428:
of two images, you get a pretty stripey correspondence map. --
15:
444:
this should be fixed by "return DTW" or something like this.
642:
SparseDTW: A Novel
Approach to Speed up Dynamic Time Warping
251:
376:
No. All algorithms should be in pseudocode. Obviously.
196:, a collaborative effort to improve the coverage of
101:, a collaborative effort to improve the coverage of
668:The illustration should be corrected or removed.
8:
722:C-Class software articles of Low-importance
412:NP-complete assertion is also unreferenced.
478:
152:
47:
629:Linear Space Using Hirschberg's Algorithm
154:
49:
19:
660:Figure with 2 piecewise linear curves
7:
190:This article is within the scope of
95:This article is within the scope of
38:It is of interest to the following
633:There are sources that claim that
14:
707:Low-importance Computing articles
697:Low-priority mathematics articles
115:Knowledge:WikiProject Mathematics
717:Low-importance software articles
285:Suggested errors and improvments
183:
156:
118:Template:WikiProject Mathematics
82:
72:
51:
20:
238:This article has been rated as
218:Knowledge:WikiProject Computing
135:This article has been rated as
655:13:29, 17 September 2021 (UTC)
454:11:20, 13 September 2011 (UTC)
221:Template:WikiProject Computing
1:
678:20:03, 6 September 2022 (UTC)
468:02:44, 21 November 2012 (UTC)
366:12:04, 16 December 2008 (UTC)
339:12:52, 20 November 2009 (UTC)
318:14:33, 19 December 2009 (UTC)
303:16:28, 19 December 2009 (UTC)
290:of its various properties.
260:This article is supported by
212:and see a list of open tasks.
109:and see a list of open tasks.
692:C-Class mathematics articles
583:13:19, 24 January 2017 (UTC)
551:13:19, 24 January 2017 (UTC)
535:10:20, 21 October 2014 (UTC)
513:13:19, 24 January 2017 (UTC)
497:20:46, 5 October 2016 (UTC)
748:
702:C-Class Computing articles
438:21:57, 20 March 2011 (UTC)
386:04:37, 20 April 2008 (UTC)
244:project's importance scale
712:C-Class software articles
628:
568:07:23, 15 June 2010 (UTC)
422:03:46, 26 July 2010 (UTC)
404:01:09, 17 June 2011 (UTC)
259:
237:
178:
134:
67:
46:
623:09:54, 5 July 2018 (UTC)
603:09:53, 5 July 2018 (UTC)
541:Series start at s and t.
141:project's priority scale
98:WikiProject Mathematics
732:All Computing articles
635:Hirschberg's algorithm
256:
206:information technology
28:This article is rated
727:All Software articles
255:
193:WikiProject Computing
263:WikiProject Software
121:mathematics articles
257:
224:Computing articles
90:Mathematics portal
34:content assessment
525:comment added by
499:
483:comment added by
356:comment added by
329:comment added by
282:
281:
278:
277:
274:
273:
151:
150:
147:
146:
739:
537:
368:
341:
226:
225:
222:
219:
216:
187:
180:
179:
174:
171:
160:
153:
123:
122:
119:
116:
113:
92:
87:
86:
76:
69:
68:
63:
55:
48:
31:
25:
24:
16:
747:
746:
742:
741:
740:
738:
737:
736:
682:
681:
662:
631:
611:
591:
527:130.149.232.110
520:
475:
358:131.231.126.100
351:
324:
287:
223:
220:
217:
214:
213:
172:
166:
120:
117:
114:
111:
110:
88:
81:
61:
32:on Knowledge's
29:
12:
11:
5:
745:
743:
735:
734:
729:
724:
719:
714:
709:
704:
699:
694:
684:
683:
661:
658:
630:
627:
610:
607:
590:
587:
586:
585:
556:
554:
553:
518:
516:
515:
503:Already fixed.
474:
471:
441:
440:
409:
408:
407:
406:
396:70.225.163.208
389:
388:
378:65.183.135.231
370:
369:
344:
322:
310:201.79.213.251
307:
286:
283:
280:
279:
276:
275:
272:
271:
268:Low-importance
258:
248:
247:
240:Low-importance
236:
230:
229:
227:
210:the discussion
188:
176:
175:
173:Low‑importance
161:
149:
148:
145:
144:
133:
127:
126:
124:
107:the discussion
94:
93:
77:
65:
64:
56:
44:
43:
37:
26:
13:
10:
9:
6:
4:
3:
2:
744:
733:
730:
728:
725:
723:
720:
718:
715:
713:
710:
708:
705:
703:
700:
698:
695:
693:
690:
689:
687:
680:
679:
675:
671:
666:
659:
657:
656:
652:
648:
643:
639:
636:
626:
624:
620:
616:
615:120.18.188.52
608:
606:
604:
600:
596:
595:120.18.188.52
588:
584:
580:
576:
572:
571:
570:
569:
565:
561:
552:
548:
544:
540:
539:
538:
536:
532:
528:
524:
514:
510:
506:
502:
501:
500:
498:
494:
490:
486:
482:
472:
470:
469:
465:
461:
456:
455:
451:
447:
439:
435:
431:
426:
425:
424:
423:
419:
415:
405:
401:
397:
393:
392:
391:
390:
387:
383:
379:
375:
374:
373:
367:
363:
359:
355:
348:
347:
346:
342:
340:
336:
332:
331:96.20.156.153
328:
320:
319:
315:
311:
305:
304:
300:
296:
291:
284:
269:
266:(assessed as
265:
264:
254:
250:
249:
245:
241:
235:
232:
231:
228:
211:
207:
203:
199:
195:
194:
189:
186:
182:
181:
177:
170:
165:
162:
159:
155:
142:
138:
132:
129:
128:
125:
108:
104:
100:
99:
91:
85:
80:
78:
75:
71:
70:
66:
60:
57:
54:
50:
45:
41:
35:
27:
23:
18:
17:
667:
663:
641:
637:
632:
612:
592:
555:
521:— Preceding
517:
479:— Preceding
476:
457:
442:
410:
371:
343:
321:
306:
292:
288:
261:
239:
191:
137:Low-priority
136:
96:
62:Low‑priority
40:WikiProjects
352:—Preceding
325:—Preceding
112:Mathematics
103:mathematics
59:Mathematics
686:Categories
589:Pseudocode
460:Fpetitjean
446:Antisergey
647:AnusserWP
485:Gforman44
215:Computing
202:computing
198:computers
164:Computing
523:unsigned
493:contribs
481:unsigned
473:Obsolete
354:unsigned
327:unsigned
169:Software
670:AVM2019
609:Example
575:Rgiusti
543:Rgiusti
505:Rgiusti
295:Petulda
242:on the
139:on the
30:C-class
638:cannot
204:, and
36:scale.
674:talk
651:talk
619:talk
599:talk
579:talk
564:talk
560:Stys
547:talk
531:talk
509:talk
489:talk
464:talk
450:talk
434:talk
418:talk
414:Enon
400:talk
382:talk
362:talk
335:talk
314:talk
299:talk
430:IdS
234:Low
131:Low
688::
676:)
653:)
625:)
621:)
605:)
601:)
581:)
566:)
558:--
549:)
533:)
511:)
495:)
491:•
466:)
452:)
436:)
420:)
402:)
384:)
364:)
337:)
316:)
301:)
270:).
200:,
167::
672:(
649:(
617:(
597:(
577:(
562:(
545:(
529:(
507:(
487:(
462:(
448:(
432:(
416:(
398:(
380:(
360:(
333:(
312:(
297:(
246:.
143:.
42::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
