This study aims to demonstrate that when performing dynamic time warping (DTW) on gait data, multiple optimal warping paths (OWPs) with a minimum sum of local costs can occur and to propose an additional OWP selection method to address this problem. A 3-dimensional motion analysis experiment was conducted on 55 adult participants, including both males and females, to acquire gait data. This study analyzed 990 instances of DTW on gait data to examine the occurrence of multiple OWPs with the minimum sum of local costs. We subsequently applied an additional selection method to the multiple OWPs to determine the feasibility of identifying a single OWP. Multiple OWPs through DTW were observed 82 times, accounting for 8.28%. Notably, on the ankle joint of males, the rate was the highest at 11.11%. Cases with two multiple OWPs were the most prevalent at 56.10%, and cases with ten or more multiple OWPs accounted for 19.51%. The additional selection method proposed in this study was applied to the 82 instances in which multiple OWPs occurred. The results demonstrated the ability to identify a unique OWP in all cases. These results hold significance in identifying the shortcomings of conventional OWP selection methods previously employed and proposing solutions. It enhances the reliability, validity, and accuracy of studies utilizing DTW.

The algorithm aims to find paths that match the two sequences based on three criteria: boundary condition, monotonicity condition, and step size condition. The critical focus of the paths identified through this process is determining the optimal warping path (OWP), representing the optimal matching path. Due to differences between the time series data, multiple matching paths may emerge during this procedure. The standard method for selecting the OWP is to choose the path where the sum of local costs is minimized. If 2-time series data are perfectly identical, the OWP in the cost matrix will be diagonal. However, when there are differences between the time series data, the OWP deviates from the diagonal. When applying DTW to actual gait signals, multiple OWPs with the minimized sum of local costs can occur. Therefore, relying solely on the sum of local costs as a criterion for determining the OWP, as is the traditional method, may not provide a sufficient judgment standard. Nevertheless, most known DTW programs still determine the OWP using only the traditional method. The phenomenon of multiple OWPs has not been reported until recently. Moreover, researchers may not be aware of this possibility if researchers use the traditional method when programming the DTW algorithm. These issues not only pose constraints on various research fields, including gait studies that utilize DTW, but also can have negative implications for the reliability, validity, and accuracy of results. In particular, slight differences can lead to different results when applying DTW to the study of gait pattern similarity, which is utilized in diagnosing and rehabilitating gait-related diseases.

Thus, the method of selecting the OWP becomes crucial. Therefore, this study aims to demonstrate that, when performing DTW with gait data, multiple OWPs with minimized sum of local cost can occur. Then, we propose an additional selection method that utilizes deviations from the diagonal line in the cost matrix to choose a single OWP.

In order to acquire gait data, a 3-dimensional (3D) motion analysis experiment was conducted with a total of 55 participants, 27 males and 28 females. Determining the sample size utilized the GPower program set at an effect size of 0.8, a significance level of 0.05, and a statistical power of 0.8 in the analysis method of independent

Participants underwent a 5-min walking practice at their self-selected speed to acclimate to the laboratory environment and alleviate any tension due to the experiment. The 3D motion analysis equipment utilized Motion Analysis’s motion capture system (6085 State Farm Drive Suite 100, Rohnert Park, CA, USA) and used ten infrared CCD cameras to enhance spatial verification and data collection accuracy for the walking path. The cameras had a sampling frequency of 120 frames per second, and the shutter speed was set at 1/1,000 sec. The obtained 3D coordinate data from the experiment underwent smoothing using a Butterworth low-pass filter. The distance corresponding to two strides of each participant was recorded 3 times, and the angle values of the hip, knee, and ankle joints were calculated. DTW was performed 990 times (55 participants×3 joints×6 strides) with each joint of the participant’s left and right foot as the comparison sequences.

The traditional method for selecting the OWP in DTW is to choose the path with the smallest sum of local costs among those found (

Here, _{p}

Here, (_{xi}_{op}

In this study, a DTW program incorporating the expression mentioned above was developed using the R-language. The results were cross-validated to ensure the program’s validity by comparing them with the DTW package available in R (

When conducting DTW between the left and right feet using gait data, instances of multiple OWPs with minimized local cost sum are presented, as shown in

For the 82 cases where multiple OWPs occurred, executing the additional selection method proposed in the research methodology resulted in finding a unique OWP in all instances. Moreover, after applying the additional selection method, the issue of multiple OWPs did not reoccur.

This study confirmed through analysis that when performing DTW on gait data using only the sum of local costs for optimal path selection, multiple OWPs can arise. Additionally, when multiple OWPs occur, the study demonstrated that an additional selection method can be employed, utilizing the deviations of each of the multiple OWPs from the diagonal line to choose a single, ultimate optimal path. Results in this study are significant as they highlight the limitations of the traditional optimal path selection method and propose a solution. These findings also contribute to enhancing the reliability, validity, and accuracy of studies utilizing DTW.

Upon reviewing prior studies, DTW was the primary analytical tool to resolve intricate research problems across various domains. The relevant studies include the following: robotics and human gait recognition, and gait characteristics of elderly patients (

As observed in the studies above, most have employed DTW as a primary analytical tool or an auxiliary tool to solve research problems and enhance its functionality. However, these studies have yet to report on the occurrence of multiple OWPs during the primary objective of DTW, which is the decision of OWP. The occurrence of multiple OWPs is variable according to the utilized data. Furthermore, when the DTW was programmed in its original algorithm, detecting the existence of multiple OWPs would have been difficult because a single OWP had always been produced. When researchers make the DTW program themselves without information about the potential occurrence of multiple OWPs, the programming code may be composed incompletely without solving code about the occurrence of multiple OWPs. An incomplete DTW program could have a potentially negative impact on the validity and reliability of the research. In this regard, the results of this study not only address the limitations of DTW but also contribute to more accurate research execution. In gait research, DTW has been used to identify abnormal movements by comparing a patient’s gait pattern to a standard gait pattern, and in sports, it has been utilized to compare sports skill patterns to improve specific sports skills. It is also being used to evaluate the effectiveness of treatments and patient progress in rehabilitation for athletes and the general population. As DTW is used as a tool for comparison and diagnosis in exercise and rehabilitation, the results obtained by DTW analysis should be valid and reliable. In this regard, the results of this study will help further strengthen the reliability and validity of DTW analyses in the field of exercise and rehabilitation. Additionally, by proposing an additional method for selecting a single OWP to address the occurrence of multiple optimal paths, this study is expected to assist future researchers who aim to utilize DTW by programming for research purposes.

While this study exclusively utilized gait data, considering the widespread and active application of DTW in medical and rehabilitation fields, as well as various research domains, it is conceivable that similar studies may be conducted in each domain to investigate the occurrence of multiple optimal paths in the data handled in those studies. The results of this study should also lead to caution when using DTW programs written or distributed by other researchers.

This research was supported by the Graduate School of Education, Korea University Grant in 2023.

No potential conflict of interest relevant to this article was reported.

Cost matrix and deviation.

Representative example 1: matching graph of raw data.

Representative example 1: optimal warping paths.

Representative example 2: matching graph of raw data.

Representative example 2: optimal warping paths.

Anthropometric data for participants

Gender | No. | Age | Height | Weight |
---|---|---|---|---|

Female | 28 | 22.71±2.27 | 163.98±6.16 | 57.00±7.00 |

Male | 27 | 25.96±2.20 | 175.50±6.64 | 74.47±10.38 |

Values are presented as mean±standard deviation.

Frequency and percentage of occurrence of multiple OWPs

Gender | Joint | DTW execution | Occurrences of multiple OWPs |
---|---|---|---|

Male | Ankle | 162 | 18 (11.11) |

Hip | 162 | 14 (8.64) | |

Knee | 162 | 12 (7.41) | |

| |||

Female | Ankle | 168 | 12 (7.14) |

Hip | 168 | 12 (7.14) | |

Knee | 168 | 14 (8.33) | |

| |||

Total | 990 | 82 (8.28) |

Values are presented as number (%).

OWP, optimal warping path; DTW, dynamic time warping.

Frequency of occurrence according to the number of optimal warping paths (OWPs)

No. of OWPs | No. of occurrences (%) |
---|---|

2 | 46 (56.1) |

3 | 7 (8.54) |

4 | 5 (6.1) |

5 | 4 (4.88) |

6 | 1 (1.22) |

7 | 2 (2.44) |

8 | 1 (1.22) |

≥10 | 16 (19.51) |

Representative example 1: multiple optimal warping paths on the knee joint of a female

Path No. | Index |
Index |
Path index | Sum of local costs | Sum of deviations | Sum of deviations/( |
---|---|---|---|---|---|---|

2 | 129 | 129 | 161 | 11,023.85 | 528 | 0.031729 |

3 | 129 | 129 | 161 | 11,023.85 | 529 | 0.031799 |

4 | 129 | 129 | 161 | 11,023.85 | 530 | 0.031849 |

5 | 129 | 129 | 161 | 11,023.85 | 531 | 0.031909 |

1 | 129 | 129 | 161 | 11,023.85 | 532 | 0.031969 |

Representative example 2: multiple optimal warping paths on the knee joint of a female

Path No. | Index |
Index |
Path index | Sum of local costs | Sum of deviations | Sum of deviations/( |
---|---|---|---|---|---|---|

9 | 122 | 120 | 141 | 4,939.4 | 278.52 | 0.019025 |

8 | 122 | 120 | 141 | 4,939.4 | 279.15 | 0.019067 |

10 | 122 | 120 | 141 | 4,939.4 | 279.51 | 0.019092 |

7 | 122 | 120 | 141 | 4,939.4 | 280.13 | 0.019135 |

6 | 122 | 120 | 141 | 4,939.4 | 281.11 | 0.019202 |

5 | 122 | 120 | 141 | 4,939.4 | 282.10 | 0.019269 |

4 | 122 | 120 | 141 | 4,939.4 | 283.08 | 0.019336 |

3 | 122 | 120 | 141 | 4,939.4 | 284.07 | 0.019403 |

2 | 122 | 120 | 141 | 4,939.4 | 285.05 | 0.019471 |

1 | 122 | 120 | 141 | 4,939.4 | 286.03 | 0.019538 |