Establishing reference criteria for diagnosing normal gait patterns similarity using dynamic time warping
Article information
Abstract
The purpose of this study was to establish reference criteria for evaluating gait pattern similarity during normal gait in research using dynamic time warping (DTW). For this purpose, the DTW algorithm was implemented using the R programming language, and DTW analyses were conducted on normal gait data collected from the ankle, knee, and hip joints via 3-dimensional motion analysis in a sample of 55 healthy participants. The final optimal warping path identified by DTW was defined as the path having the smallest cumulative perpendicular distance from the diagonal of the cost matrix. DTW analyses were categorized into three groups: (1) same lower-limb within-subject, comparing identical limbs within each participant; (2) same lower-limb between-subjects, comparing identical limbs between different participants; and (3) opposite lower-limb within-subject, comparing the left and right limbs within each participant. A generalized linear model was employed to analyze the effects of group and gender. Reference criteria for gait pattern similarity are provided as estimated marginal means and 95% confidence intervals according to group and gender for each lower-limb joint during normal gait. Given statistically significant differences among groups, the results underscore the necessity of evaluating not only whether patient gait patterns align within the normal range of healthy individuals but also the similarity between the patient’s own limbs for precise rehabilitation assessment.
INTRODUCTION
Among various methods utilized to assess a patient’s level of normal gait or rehabilitation progress, gait pattern similarity assessment biomechanically compares human movements by leveraging the periodic characteristics inherent in gait. The diagnosis of normal gait through exercise rehabilitation extends beyond merely evaluating the physiological recovery of muscles, tendons, and ligaments; it encompasses the restoration of functional mobility. This broader approach is essential because stable and balanced bipedal locomotion is necessary to achieve gait without risking injury. Consequently, gait pattern similarity methods have been extensively employed to evaluate normal gait functionality.
Traditional methods for evaluating gait pattern similarity have included correlation analysis, autocorrelation analysis, and symmetry index (SI). However, these methods have inherent limitations because gait patterns are fundamentally nonlinear, and variability exists both within-subject and between-subjects. Recently, to overcome these limitations, Researchers have applied the dynamic time warping (DTW) algorithm.
Initially introduced by Velichko and Zagoruyko (1970) as a method for verifying similarities in speech signals, DTW is a robust algorithm capable of assessing similarities between nonlinear patterns regardless of differences in sequence lengths (Efrat et al., 2007). DTW has been utilized across various research fields, including signature verification in online environments, temporal similarity analyses of COVID-19 infection and mortality rates, and analyses of biological signals such as electromyography and electrocardiograms (Huang et al., 2010; Li et al., 2013).
Research also supports applying DTW in gait pattern similarity studies. Barth et al. (2015) employed multi-dimensional subsequence DTW on accelerometer and gyroscope data to analyze differences between normal individuals and patients. Gaspar et al. (2017) compared DTW with other statistical methods such as Pearson correlation coefficients, cross-correlation, and root mean square error for improved validation of time-series data in musculoskeletal simulation studies, demonstrating DTW’s sensitivity and applicability in assessing direct and indirect quantitative validity. DTW was used to analyze continuous gait pattern similarities, thereby assessing gait stability. Lee (2019) reported that applying the DTW algorithm in gait similarity studies provided more robust results than the SI, even when evaluating normal gait, and emphasized its practical utility in gait analysis.
Although previous studies highlight DTW’s advantages and applicability in gait pattern similarity research, they have not yet established reference criteria for assessing gait pattern similarity. DTW evaluates sequence similarity by calculating a cost sum derived from the cumulative distance along the optimal warping path (OWP) between two sequences. Establishing criteria for determining similarity based on the OWP is critical for practical applications such as clinical diagnosis and research. However, to date, no standardized theoretical or experimental criteria have been proposed. This lack of criteria presents challenges in achieving objectivity and validity in determining normal gait patterns or evaluating similarities between two gait sequences.
Determining the presence of normal gait is fundamental and essential in gait research. It is crucial not only for evaluating subjects’ gait during experiments or assessing rehabilitation levels after treatment but also for prescribing and developing exercise programs for rehabilitation therapy. As previously mentioned, gait patterns exhibit variability between individuals, within individuals, and even between left and right foot steps. Therefore, establishing reference criteria for determining OWP similarity in normal gait is essential for conducting more objective and valid research. Specifically, deciding the acceptable threshold for normal gait is central to setting precise criteria. Consequently, this study aims to propose similarity evaluation criteria for normal gait necessary for gait pattern similarity research utilizing DTW.
MATERIALS AND METHODS
Implementation of the DTW algorithm
The DTW algorithm was implemented using the R programming language, and a symmetric step-pattern was employed. Among multiple generated warping paths, DTW identifies the OWP as the one having the smallest cumulative local cost. However, previous research indicates that traditional DTW often produces multiple OWPs with identical minimal local costs sum, thus limiting the use of the cumulative local cost sum alone for determining the optimal solution (Lee et al., 2024). Therefore, in this study, when multiple OWPs with equal minimal local costs sum were identified, the OWP exhibiting the smallest sum of perpendicular distances between the OWP and the diagonal of the cost matrix (PDWP) was selected as the final OWP. The rationale for utilizing the PDWP is that when two sequences are identical, the OWP aligns exactly along the diagonal of the cost matrix. The calculated PDWPs were normalized by dividing them by the sum of the lengths of the two sequences (N) for mutual comparison.
The reliability and validity of the implemented DTW algorithm were verified through three different approaches. First, the consistency of results was confirmed by direct comparison between outcomes obtained using the traditional DTW method and those calculated using the DTW algorithm implemented in R, hereafter referred to as gait-specific DTW. Second, the results were compared with those obtained using the established dtw package in R (Giorgino, 2009), employing sine signal data (i.e., sine vs. sine, sine vs. sine of half amplitude, sine vs. sine of 75% period) (Fig. 1A). Third, consistency of results was further confirmed by applying the implemented DTW algorithm to real gait data collected from a three-dimensional motion capture experiment, and comparing these results with those from the existing dtw package and gait-specific DTW (Fig. 1B).
Comparison between gDTW and DTW results using sine signals and gait data. (A) Comparison of gDTW and DTW using sine signals. (B) Comparison of gDTW and DTW using gait data. gDTW, gait-specific dynamic time warping implemented in R; DTW, dynamic time warping implemented using the R package dtw.
Participants
Anthropometric data of the participants are summarized in Table 1. The number of participants for the three-dimensional motion analysis experiment was calculated using G*Power software based on a two-way analysis of variance with the following parameters: effect size (η2)=0.16, significance level (α)=0.05, statistical power=0.8, numerator degrees of freedom (df)=2, and number of groups=6. Although the calculated sample size was 54 participants, considering potential dropout during the experimental period, the final number was determined as 55 participants (male=27, female=28). However, since the actual data used for analysis in this study was based on the number of DTW analyses rather than the number of participants, the effective sample size is presented in Table 2. Participants were healthy adults in their 20s who had no history of musculoskeletal injuries or gait-related diseases within the past 3 months. Before beginning the experiment, all participants received explanations about the purpose and procedures involved, and voluntarily provided informed consent (KUIRB-2021-0250-03).
Anthropometric data of participants
Number of DTW analysis by groups
Experiment of 3-dimensional motion analysis
Three-dimensional motion analysis experiment was conducted to acquire normal gait data using a motion capture system (Motion Analysis Corp.). Ten infrared cameras were employed at a sampling frequency of 120 frames per second and a shutter speed of 1/1,000 sec. Each participant had 40 reflective markers attached as shown in Fig. 2. and performed 5 min of walking practice at a self-selected walking speed before data collection to alleviate possible tension associated with the experimental environment and to ensure natural gait patterns.
Markerset attached to the participants. R, right; L, left; V, virtual; ASIS, anterior superior iliac spine; JC, joint center.
During the main experiment, participants walked at their preferred walking speed along a predefined 10-meter walkway in the laboratory. Three trials of normal gait were captured for each participant, and two strides were extracted from each trial for subsequent analysis. Marker trajectory data were filtered using a 2nd-order zero-lag Butterworth low-pass filter with a cutoff frequency of 6 Hz. Spatial-temporal and kinematic variables for the hip, knee, and ankle joints were calculated from the acquired normal gait data collected through the three-dimensional motion analysis.
Analysis methods
The normal gait dataset used for DTW analysis comprised 1,980 sequences representing the angular data from three lower-limb joints (hip, knee, and ankle). These sequences were derived from 55 subjects×3 trials×2 strides per trial×2 sides (left and right)× 3 joints.
The DTW analyses were conducted according to three groups. First, the same lower-limb within-subject (SLWS) group included comparisons among the six stride sequences obtained from each participant. Thus, a total of 4,950 DTW analyses were performed (subjects [55]×joints [3]×feet [2]×stride pairs [15]=4,950). Second, the same lower-limb between-subjects (SLBS) group included comparisons of the six stride sequences from each participant against those from all other participants, resulting in 157,464 DTW analyses. Third, the opposite lower-limb within-subject (OLWS) group performed DTW analyses stride sequences between the left and right lower-limb within each subject, totaling 990 DTW analyses (subjects [55]×joints [3]×stride pairs [6]=990).
OWPs obtained from the DTW analyses were normalized as previously described and subsequently used for statistical analysis. Given that the dependent variable, PDWP, did not meet the assumptions of normality due to inconsistent variations in gait patterns across subjects, and considering that homogeneity of variances across ankle, knee, and hip joints could not be assumed, a generalized linear model was employed. Since the overall distribution of PDWP was positively skewed, it was assumed to follow a gamma distribution. Different link functions (e.g., log, identity) were initially tested, but the Akaike information criterion and deviance values were identical across these functions. Thus, for ease of interpretation, the identity link function was ultimately selected. The identical values of Akaike information criterion and deviance indicate that the independent variables—group and gender —are categorical, and that the overall data structure satisfies linearity assumptions. Post hoc analyses for interaction effects were conducted using the Bonferroni correction.
RESULTS
Descriptive statistics and 95% confidence intervals by group
Descriptive statistics for the PDWP values normalized by the sum of the lengths of two sequences (N), which is the conventional normalization method for OWPs calculated by DTW, are presented in Table 3. The within-subject group comparing the same lower limb (SLWS) showed lower PDWP values compared to the between-subjects group (SLBS). This indicates that within-subject variation in gait patterns is smaller than variation between-subjects. The within-subject opposite lower-limb (OLWS) group, which compared stride sequences between the left and right lower limbs within each subject, showed higher PDWP values than the SLWS group, but lower than the SLBS group. Thus, the rank order of groups according to gait pattern similarity (highest to lowest similarity) was SLWS>OLWS>SLBS.
Descriptive statistics and 95% confidence intervals (CIs) of PDWP
Difference analysis by group and gender
A generalized linear model was employed to investigate differences in PDWP values according to group and gender. There were significant interaction effects between group and gender for the ankle and knee joints (ankle: estimate=−0.39, P<0.001; knee: estimate=−0.33, P<0.00) whereas for the hip joint, no interaction was observed, although significant main effects of group and gender were found (Table 4). Post hoc analyses (Table 5, Figs. 3–5) showed no significant gender differences for the ankle joint within the OLWS and SLWS groups; however, all other pairwise comparisons revealed significant differences. For the knee joint, no significant gender differences were found within the OLWS group, and females in the SLWS group did not differ significantly from males or females in the OLWS group. All other comparisons showed significant differences (Table 5). Regarding the hip joint, where significant main effects were identified, all pairwise comparisons between groups were statistically significant.
Results of the generalized linear model for the joints
Post hoc test for the interaction effect
Post hoc for ankle joint. Circles in the figure indicate comparisons of all possible pairs. PDWP, perpendicular distances between the optimal warping path and the diagonal of the cost matrix; CI, confidence intervals; SLWS, same lower-limb within-subject group; SLBS, same lower-limb between-subjects group; OLWS, opposite lower-limb within-subject group. ***P<0.001.
Post hoc for knee joint. Circles in the figure indicate comparisons of all possible pairs. PDWP, perpendicular distances between the optimal warping path and the diagonal of the cost matrix; CI, confidence intervals; SLWS, same lower-limb within-subject group; SLBS, same lower-limb between-subjects group; OLWS, opposite lower-limb within-subject group. ***P<0.001.
Post hoc for hip joint. Squares in the figure represent groups. PDWP, perpendicular distances between the optimal warping path and the diagonal of the cost matrix; CI, confidence intervals; SLWS, same lower-limb within-subject group; SLBS, same lower-limb between-subjects group; OLWS, opposite lower-limb within-subject group. ***P<0.001.
Reference criteria of normal gait by joint
Estimated marginal means and corresponding 95% confidence intervals (CIs) proposed as reference criteria for evaluating normal gait pattern similarity by lower-limb joint are presented in Table 6.
Estimated marginal means with 95% confidence intervals (CIs)
DISCUSSION
This study aimed to establish reference criteria for evaluating gait pattern similarity in normal gait using DTW, presenting criteria values as estimated marginal means and 95% CI according to group and gender, as shown in Table 6.
Correlation analysis, previously utilized for evaluating gait pattern similarity, is based on linearity and thus has limitations when applied to gait data, which inherently exhibits nonlinear patterns. The SI, another traditional approach, classifies gait patterns as similar when deviations between two sequences fall within 10% of the mean value (Herzog et al., 1989; Perttunen et al., 2004; Robinson et al., 1987). However, SI is limited in effectively capturing variations in gait patterns. Furthermore, both correlation analysis and SI require the compared sequences to have equal lengths. These traditional methods are therefore not compatible with DTW-based analyses. In contrast, DTW is advantageous as it is robust to variations in sequence lengths and effectively handles nonlinear data, enabling its application to gait data collected under various experimental conditions. Despite these advantages, previous DTW-based gait pattern similarity studies have primarily relied on the relative comparison of cost sum values to determine normal gait or gait pattern similarity, as there are currently no established reference criteria (Jeong and Baek, 2021; Li et al., 2019). Such approaches inherently depend on researchers’ subjective judgments regarding acceptable differences in cost sum values, thereby limiting the objectivity, reliability, and validity of the studies. In this context, the results of the present study provide objectively derived variation ranges (95% CI) of gait patterns both within and between-subjects during normal gait, which can serve as valuable reference criteria in future gait research to improve objectivity, reliability, and validity.
The results of this study demonstrated significant differences between groups, with the between-subjects group (SLBS) showing higher PDWP values than the within-subject groups (SLWS and OLWS). These findings suggest that even if a rehabilitation patient’s gait pattern falls within the normal gait range determined from between-subject variability, it may be insufficient to conclude complete recovery of gait function. This is because safe and stable gait requires symmetry and balance between the right and left lower limbs. Therefore, it is essential to additionally evaluate the similarity of the patient’s gait patterns between their own lower limbs. Specifically, rehabilitation success can be effectively assessed through a two-step approach: first, confirming whether the patient’s gait pattern falls within the normal gait range (95% CI of the SLBS group), and second, evaluating the similarity of gait patterns within the patient’s own limbs (95% CI of SLWS and OLWS groups).
The criteria proposed in this study represent a minimal reference standard rather than an absolute threshold. Thus, exceeding the proposed reference criteria values indicates a potential deviation from normal gait but does not necessarily confirm abnormality. Although this study attempted to fully capture variations in gait patterns through exhaustive DTW analyses of all possible combinations, it is important to note that the participants were restricted to individuals in their 20s. DTW can accommodate differences in sequence durations, making these results potentially applicable to other age groups, such as elderly individuals with slower gait speeds. However, caution is warranted, as the current findings do not reflect the diverse gait characteristics associated with other age ranges.
Notes
CONFLICT OF INTEREST
No potential conflict of interest relevant to this article was reported.
ACKNOWLEDGMENTS
This work was supported by the Ministry of Education of the Republic of Korea and the National Research Foundation of Korea (NRF-2021S1A5A8063345).