Automatic detection of human gait events: a simple but versatile 3D algorithm

Abstract

Background

Detecting Foot Strike and Foot Off events in human gait, which is cyclic yet variable, consistently requires expert correction. This subjective correction can reduce spatiotemporal parameters, joint kinematic and kinetic accuracy, regardless of the gait event detection algorithm used from the literature. Recently developed methods have combined existing algorithms to better capture this gait variability, using Ground Reaction Forces. However, those methods do not fully account for intra-individual variability, particularly in the case of multiple and simultaneous gait patterns.

Method

We developed a deterministic algorithm called the Multi-Condition algorithm. This algorithm identifies the Foot Strike when the first of the foot markers loses its degrees of freedom and the Foot Off when the last of the foot markers regains its degrees of freedom.

Results

This algorithm was tested on 819 C3D gait files from 9 healthy individuals and 50 individuals with stroke, multiple sclerosis, spinal cord injury, cerebral palsy, polio, neuromuscular disease or amputation. The Multi-Condition algorithm detected both Foot Strike and Foot Off within a range of three frames, which was more accurate and precise than the inter-rater variability of expert correction. Detection of gait events required only a few seconds, regardless of the pathology or gait pattern, even when considering intra-individual variability.

Conclusion

Accurately identifying gait events is the first critical step in providing reliable gait analysis parameters for clinicians. The Multi-Condition algorithm aims to achieve deterministic consensus in the accurate and precise identification of gait events, regardless of the pathology or the gait pattern. To promote its adoption and ongoing testing, the Multi-Condition algorithm is available as an open-access resource.

Ethical committee

The study was approved by the University of Paris-Saclay Research Ethics Committee (No. CER-Paris-Saclay-2024-35) and was performed in accordance with the Declaration of Helsinki.

Introduction

Human gait is the result of constant learning and adjustments. It evolves with physical activity, age, and everyday life experiences [1]. In various situations, humans adapt their gait to the ground materials, slopes, obstacles and can change speed and direction. Pathological gait must additionally adapt to neuromuscular impairments (e.g. weakness or balance disorders) and associated complications (e.g. pain, stiffness or limited range of motion) [2].

Instrumented gait analysis is recommended to obtain objective quantitative data and assist clinicians in decision-making. Gait analysis involves calculating spatiotemporal parameters and joint kinematics and kinetics. For accurate calculation, two gait events need to be detected: Foot Strike and Foot Off [3].

In clinical settings, gait events are often automatically detected, to save time. Different algorithms have been developed for this purpose, depending on data from the sensors used in gait analysis. Kinetic data from force plates embedded in the ground is generally considered the gold standard. However, often only one step at a time can be detected by force platforms and this method becomes invalid in the case of slide or drag gait patterns, or the use of walking aids. In these cases, kinematic data from marker-based motion capture are used to detect gait events.

Many studies have proposed deterministic algorithms using the position [4, 5], the velocity [6,7,8], or the acceleration [9, 10] of foot markers. Differences in cohorts and analysis protocols have required comparison studies in order to assess reliability and efficiency. Comparisons of these methods mostly identified Ghoussayni’s algorithm as the most reliable [11,12,13]. However, for a clinically diverse cohort, their precision remains insufficient, and expert correction is still needed.

Deep learning-based approaches [14,15,16] and an auto-selection approach [17] have recently been developed to address this issue. Deep learning is promising but has drawbacks because it relies on a large training database, with good characteristics, and is unable to explain the process that leads to event detection. The auto-selection approach uses Ground Reaction Forces (GRF) to compare deterministic algorithms and select the most precise one for a specific condition, side, and type of event. The general precision improves significantly compared to that of deterministic algorithms. However, the use of a few “clean hits” on force platforms excludes a large proportion of gait cycles. Furthermore, if an individual’s gait changes between cycles, the induced variability is not taken into account. Additionally, gait cycles outside the force platforms might still require expert correction.

Therefore, the starting point of this study is the need for an approach that copes with versatility in large and diverse cohorts. To adapt to the variability of patterns between gait cycles, we adopted a twofold approach:

• Instead of using one hindfoot marker for Foot Strike and one forefoot marker for Foot Off, we considered every part (marker) of the system (foot).

• We considered contact with the ground as comparable to the addition of a kinematic rigid foot-ground link with no degrees of freedom for a very short time.

This approach allowed us to describe Foot Strike and Foot Off as follows:

$$\text{FS} = \text{First of the foot markers to stop moving} \;({\text{in}}\;3\;{\text{dimensions}})$$

(1)

$$\text{FO} = \text{Last of the foot markers to start moving}\;(\text{in}\; 3\; \text{dimensions})$$

(2)

Following this, we developed a new algorithm, called Multi-Condition, and tested it for validation with clinical data. We compared its performance with that of other algorithms in the literature, with expert-rater considered the gold standard, which was also discussed. In addition, we optimised the quadruplet of calibration parameters and evaluated the algorithm’s performance using different foot markersets.

Materials and methods

The experimental protocol was divided into four steps. The first step defined the required accuracy and precision of event detection by evaluating inter-rater reliability. The second step performed parametric optimisation to set the four calibration parameters of the Multi-Condition algorithm to achieve the accuracy and precision specified in the first step. The third step compared the algorithm’s performance (accuracy and precision) with that of other algorithms in literature. The fourth step analysed its sensitivity to the used markerset to determine which foot markers were most important for accurate and precise detection of Foot Strike and Foot Off.

Clinical setup

We used a database of gait analyses from healthy individuals and people with pathological gait. All participants walked barefoot (or with a prosthesis) over a 10-metre instrumented walkway, either at their comfortable walking speed only, or at their comfortable and maximum walking speed, depending on the purpose of the gait analysis. Kinematic and kinetic data were collected at a sampling frequency of 100Hz using the Motive version 3.0.3 optoelectronic motion capture system (15 Prime$^{\text{X}}$ 13 cameras, Optitrack, Natural Point, Corvallis, OR, USA). We used 58 markers based on the Conventional Gait Model v.2.5 [18]. In addition, during the development of the Multi-Condition algorithm, one more marker was added on the 1st interphalangeal joint of each foot, resulting in 7 foot markers (Fig. 1) and 60 markers in total. Thus, the inter-rater reliability evaluation was carried out prior to the introduction of these two markers, while the development of the Multi-Condition algorithm was carried out with the 60 markers.

Fig. 1

The foot markerset based on the Conventional Gait Model v.2.5 [18], with an additional marker on the 1st interphalangeal joint. HEE: calcaneus, ANK: lateral malleolus, TOE: 2nd metatarsocuneiform joint, VMH: 5th metatarsophalangeal joint, SMH: 2nd metatarsophalangeal joint, FMH: 1st metatarsophalangeal joint, HLX: 1st interphalangeal joint marker

The acquired data were manually cleaned by filling all discontinuities in the marker trajectories with a polynomial and/or relational algorithm. Each marker was labelled using Qualisys Track Manager version 2020.2. The gait event detection algorithms listed in Table 1 are programmed to run on Matlab version 2018a and rely on the BTK biomechanical toolkit library [19]. Labelled gait events were checked visually using Mokka version 0.6.2 before being computed by the biomechanical model pyCGM version 2.5 [18] to obtain the spatiotemporal parameters and joint kinematics and kinetics.

Table 1 Outline of the gait event detection algorithms compared in this study

Description of the inter-rater reliability evaluation

Methods recently introduced in the literature consider GRF as the gold standard for evaluating the accuracy and precision of gait event detection algorithms [6, 13, 14, 16, 17]. However, after implementing the auto-selection method from Fonseca et al. [17], which uses the vertical GRF with a threshold of 20N to select the best algorithm (among those listed in Table 1), we found that expert correction was still necessary. We concluded that, since participants do not walk on an instrumented treadmill, only a small proportion of steps strike the force platforms, and as a consequence, intra-individual gait variability cannot be fully considered. Furthermore, during Foot Off, the participants’ feet often slid over the platform, regardless of their gait pattern, and thus continued to generate a GRF. As illustrated in Fig. 2, using the Hallux marker, we found that the foot began to move relative to the ground at frame 624, whereas the vertical GRF at a threshold of 20N detected Foot Off at frame 631.

Fig. 2

GRF cannot be used as a gold standard to specify the four calibration parameters for the Multi-Condition algorithm. GRF-based Foot Off (grey circle on the GRF dashed curve) is delayed by seven frames compared to Multi-Condition-based Foot OFF (orange circle on Hallux Antero-Posterior position solid curve). The green, blue and red vertical lines on the graph represent three instants illustrated with the same colour code in the picture

Ultimately, since expert correction remained necessary regardless of the deterministic algorithm implemented, we considered it as the gold standard for our study, as suggested in Bruening and Ridge [11]. Therefore, six raters manually labelled a retrospective subset of 730 events (368 Foot Strike and 362 Foot Off events). These events were acquired from ten participants with pathological gait, selected by a Physical and Rehabilitation Medicine (PRM) doctor who was not involved in the evaluation. They represented different gait patterns (steppage, equinus, slide/drag, stiff knee gait, miscellaneous) and types of foot contact (forefoot, hindfoot, medial, lateral, flat). It is important to note that this experiment was conducted before introducing a marker on the Hallux and was based on the original markerset from Leboeuf et al. [18]. The six raters (three physiotherapists and three engineers) had different levels of experience in labelling gait events (beginner, intermediate, and expert). Since the expert raters could potentially have developed bad habits in labelling gait events, no weighting was applied among raters. So, none of the raters were considered the gold standard; instead, the mean of the six raters’ labelled events was used for each event.

Description of the Multi-Condition algorithm

The Multi-Condition algorithm—MC7—was implemented as follows (Fig. 3):

Fig. 3

Workflow of the Multi-Condition algorithm with 7 foot markers—MC7. This algorithm uses four calibration parameters: the low-pass filter frequency cut-off, and three thresholds on the X, Y and Z axes defined as fractions of the antero-posterior mean walking speed

• 1. The cleaned and labelled marker positions were smoothed using a Butterworth 4th order low-pass filter, whose cut-off frequency is one of the four calibration parameters. We chose not to use the three position components of each marker as the antero-posterior and medio-lateral axes would have generated non-cyclic signals. Instead, we used markers’ velocity components to obtain cyclic signals.

• 2. A windowing technique was applied to each C3D file, based on the antero-posterior velocity peaks of the marker, which occur in the middle of the swing phase when neither Foot Strike nor Foot Off can appear.

• 3. Three binary thresholds were applied to the X, Y and Z components of each marker velocity. We believe that the step towards 3D detection is necessary [6], but that each component needs to be analysed separately. As the task consisted of straight line walking, the antero-posterior mean velocity was much higher than that of the other components. Using the 3D velocity, would place too much importance on the antero-posterior component and medio-lateral and vertical information would be lost. The thresholds for each component were set as fractions of the mean antero-posterior walking speed of the individual. These thresholds composed the three other calibration parameters of the algorithm. This detection is based on the hypothesis that foot marker velocities reach their lowest values when the foot is in single stance phase and is rigidly linked to the ground. If the marker velocity component was lower than the set threshold, the algorithm assigned a value of 1 to the related frame; otherwise, it assigned a value of 0.

• 4. For each frame, the three binary vectors—X, Y, Z—of each foot marker were summed. The first and the last frame numbers for which this sum was equal to three were kept as the potential Foot Strike and the potential Foot Off.

• 5. Finally, we combined each marker’s detection in vectors of potential events. The first potential Foot Strike and the last potential Foot Off were assigned as the Foot Strike and the Foot Off for the related gait cycle.

Thus, the algorithm adapted to intra-individual variability meaning that within a single gait session, different markers could be decisive for the detection of each gait event. Four parameters were calibrated to set the Multi-Condition algorithm: (1) the low-pass filter cut-off frequency, (2) the V^X threshold, (3) the V^Y threshold and (4) the V^Z threshold.

Calibration process of the Multi-Condition algorithm

The next step involved finding the best quadruplet of calibration parameters to meet the requirement specifications defined by the inter-rater reliability evaluation. Numerical optimisation processes are quite standard in mechanical engineering when modelling with numerous outputs depends on multiple inputs. A drawback of such processes is that if one simulation is time-consuming, the number of inputs tested must be limited. Various numerical methods exist to find the best inputs using a limited number of simulations (Newton, Gauss-Newton, etc.). However, there is a risk of finding only local rather than global solutions, and potentially failing to meet requirement specifications.

In our case, such a constraint does not apply since one simulation, on several hundred C3D files, lasts less than one minute. Therefore, we decided to conduct a parametric optimisation with a regular distribution of the explored space of input parameters. So, low-pass filter frequency values were tested in the range [5Hz–15Hz] with steps of 2Hz, consistent with values reported in the literature [6, 11, 13]. To set ranges for the V^X, V^Y, and V^Z thresholds, a preliminary meta-model with 10% steps was established to determine consistent values. This led to ranges of [10%–30%], [25%–45%], and [6%–22%] respectively, with increments of 2%, resulting in 6 534 simulations of quadruplets.

For this part of the study, we used a retrospective database (after the Hallux markers were added) of 50 individuals with pathological gait (stroke, multiple sclerosis, spinal cord injury, cerebral palsy, polio, traumatic brain injury, neuromuscular disease and amputees) and 9 healthy individuals, with a female/male ratio of 53%/47% and a median age of 45 years (range: [19 73] years). The 6 534 simulations were then repeated on 819 C3D gait files, representing 10 910 gait events (5 503 Foot Strike and 5 407 Foot Off).

Comparison with existing literature and sensitivity analysis

Once the calibration process was completed and the specifications defined in the inter-rater reliability evaluation had been achieved, we compared the performance (precision and accuracy) of the Multi-Condition algorithm to that of the eight deterministic algorithms shown in Table 1.

Not all motion analysis laboratories use the same marker set, especially in terms of foot markers. Therefore, we conducted a sensitivity analysis by comparing the performance of the Multi-Condition algorithm with calculations based on fewer foot markers.

Results

Results of the inter-rater reliability evaluation

Rater expertise seemed more relevant than GRF as a gold standard for our study to define the desired accuracy and precision of the Multi-Condition algorithm. The results are illustrated in box plots in Fig. 4. For both Foot Strike and Foot Off, the median is centred on 0. However, although the inter-whisker range is quite narrow for Foot Strike (± 2.1 frames), it is much wider for Foot Off (+ 6.1/− 6.4 frames). This dispersion for Foot Off was explicitly reported by the raters and was attributed to the absence of a marker at the tip of the foot, which led the raters to infer the moment the foot left the ground.

Fig. 4

Box-plots (min, lower quartile, median, upper quartile, max) for the inter-rater reliability evaluation: the difference between the mean of six raters’ evaluations and related events. Ratings were done on a subset of 730 events, 368 Foot Strike and 362 Foot Off

Thus, the first step of this study defined the parametric optimisation process requirement specifications for Foot Strike as within a range of ± 2.1 frames and for Foot Off as + 6.1/− 6.4 frames, as shown in Fig. 4. However, since the Hallux marker was subsequently introduced and we could not re-evaluate the inter-rater variability, we considered that the best quadruplet of calibration parameters for the Multi-Condition algorithm should lead to a maximum range of ± 2.1 frames for both Foot Strike and Foot Off.

Results of the Multi-Condition calibration process

The Multi-Condition calibration process required approximately 90 h to compute on a desktop computer, equating to around 0.06 s per C3D file. The 6 534 simulations are depicted in Fig. 5. On the left side (yellow background), the four calibration parameters—low-pass frequency, V^X, V^Y, and V^Z —explore the space of possible values. On the right side (green background), the resulting output values are presented. Absolute values of medians are displayed instead of raw medians to facilitate visual identification of the optimal solution. The aim is to find the quadruplet that results in unitary output values close to zero (best accuracy and precision) while minimizing their sum (best tradeoff).

Fig. 5

Parametric optimisation plot. Based on 6534 simulations on 819 C3D gait files, representing 10,910 gait events, four input calibration parameters (left side) led to find the lowest four output values (right side). Bullseyes help reading output values: for both Foot Strike and Foot Off, the closer the median and inter-centile values are to zero, the more accurate and precise the results

The best quadruplet of calibration parameters [9Hz, 18%, 31%, 8%] is highlighted in red on the figure. It resulted in Foot Strike/Off median values of 0 and − 1 frame, and Foot Strike/Off [5%, 95%] inter-centile values of 3 and 4 frames, respectively.

The delay of one frame in the Foot Off median frame value could be explained by an order-of-magnitude calculation: for a mean walking speed of 1 m/s, at a frequency acquisition of 100 Hz, 1 frame corresponds to around 1 cm, which is approximately the distance between the Hallux marker and the actual tip of the hallux. However, although the participants well tolerated the Hallux marker on the medial position, they found it uncomfortable when positioned on the tip of the toe, particularly in the swing phase, at minimum foot clearance. Therefore, considering the results in Fig. 5, the subsequent results of MC7 were adjusted by one frame to compensate for the marker position. We name the adjusted MC7 as MC7*.

MC7* Performances: accuracy and precision

The previously calibrated MC7*—with the quadruplet [9Hz, 18%, 31%, 8%]—was compared to the algorithms listed in Table 1 (Fig. 6).

Fig. 6

Error plots (min, lower quartile, median, upper quartile, max) for each algorithm from Table 1, estimating Foot Strike and Foot Off compared to rater expertise. The light green areas come from the inter-rater reliability evaluation (Fig. 4). Dark green areas are the Foot Strike specifications applied on Foot Off

Data were analysed by repeated measures ANOVA and associated post-hoc tests, using JASP®, version 0.19.1.0, with an $\alpha$-value set at 5% (Table 2). In each case, the null hypothesis was rejected with a p-value lower than 0.001, so differences between each algorithm are significant. In order not to limit this quantitative analysis to mean and variance, we also performed bootstrapping with Matlab to evaluate the influence of the samples in the dataset [20]. The bootstrap method is a resampling procedure that uses data from a dataset to generate a sampling distribution by repeatedly taking random samples from it, with replacement. This method is conventionally repeated a thousand times and results in the calculation of a 95% confidence interval around the values of interest, in this study, the lower whisker, median and upper whisker.

Table 2 Quantitative statistics analysis from Fig. 6

Thus, only the algorithm by [9] and the MC7* algorithm have a lower error variability than the inter-rater variability: ± 2.1 frames for Foot Strike and + 6.1/− 6.4 frames for Foot Off. However, only MC7* fitted within a range of ± 2.1 frames for both foot strike and foot off.

Sensitivity analysis

Since motion analysis laboratories use different number of foot markers, we tested the Multi-Condition algorithm on the same dataset using several reduced markersets (Fig. 7).

Fig. 7

Error plots (min, lower quartile, median, upper quartile, max) for MC7* estimating Foot Strike/Off compared to rater expertise for each decreased marker set. The light green areas show the inter-rater reliability evaluation (Fig. 4). The dark green areas show the Foot Strike specifications applied to Foot Off

Similarly to the comparison with the algorithms from literature, data from Fig. 7 were analysed by repeated measures ANOVA and associated post-hoc tests, with an $\alpha$-value set at 5% (Table 3). In each case, the null hypothesis was rejected with a p-value lower than 0.001, so differences between each markerset are significant, what could be explained by the size of the dataset (5 503 Foot Strike and 5 407 Foot Off) and a low related variance. Again, in order not to limit this quantitative analysis to mean and variance, we also performed bootstrapping on lower whisker, median and upper whisker.

Table 3 Quantitative statistics analysis from Fig. 7

Thus, the Heel and Hallux markers appeared to be essential for detecting Foot Strike and Foot Off, respectively. Similarly, an MC4* configuration with Heel, 5th metatarsophalangeal joint, 2nd metatarsophalangeal joint, and Hallux markers yielded the same results as MC7* (which is consistent as it covers the entire foot area on the ground). Finally, if only two markers can be placed on the foot, we recommend using Heel and Hallux markers.

Discussion

Although the Multi-Condition algorithm fulfilled the specifications defined by the inter-rater reliability evaluation, some points still require discussion, such as the initial hypothesis, the use of the algorithm in gait conditions other than spontaneous and fast, the choice of a fixed low-pass filter frequency cut-off, and the size of the cohort.

As with each tested algorithm from the literature, some outliers were generated by MC7*. We hypothesised that the only times that foot marker velocities dropped below the identified thresholds was when a rigid link was established with the ground. However, some false positives occurred, particularly for Foot Strike, when the foot moves slowly backwards just before touching the ground. Increasing the cohort size in the future and rerunning the optimisation process should improve the parameter set, reducing false positive occurrences.

Motion analysis laboratories systematically evaluate spontaneous (and fast) gait conditions, considered as a gold standard, rather than more ecological walking tasks. Our study set three different thresholds for V^X, V^Y, and V^Z relative to the mean walking speed. These thresholds should continue to be effective for tasks such as obstacle stepping, where the main axis of motion is antero-posterior. However, a new optimisation process should be conducted if the walking task has a larger medio-lateral component, such as turning or slaloming.

The initial steps in developing the Multi-Condition algorithm led us to choose V^X, V^Y, and V^Z thresholds relative to the individual’s mean walking speed. Therefore, to set the low-pass frequency, we also tested a variable frequency adapted to each individual by applying a threshold of 90% or 95% to the signal energy contained in the vertical position vector of the foot markers (the only one of the three position components that is necessarily cyclic due to the contact with the ground). However, the parametric optimisation process yielded slightly better outcomes (accuracy and precision) with a constant low-pass frequency. Although this approach may not be consistently reliable, we believe it warrants further detailed exploration.

Finally, although the Multi-Condition algorithm detected both Foot Strike and Foot Off more accurately than expert detection because of the associated inter-rater variability, this result must be interpreted in the light of some limitations. The cohort was relatively small and was further reduced because of the introduction of the Hallux marker during the study. Even though we now exclusively use the Multi-Condition algorithm for the clinical detection of gait events, greatly limiting expert detection bias, it should be tested in different motion analysis laboratories, with larger and more diverse cohorts, and with different acquisition systems.

Perspectives

This work has many implications for clinical practice and future research.

The Multi-Condition algorithm was developed using kinematic data obtained from a 10-metre instrumented walkway using an optoelectronic motion capture system and primarily operates using velocity data. Therefore, it should be adapted for ecological walking tasks involving accelerometry, and it will be interesting to adapt this algorithm to work with data acquired from embedded equipment [21]. Additionally, and for the same reason, the application of the Multi-Condition algorithm could be extended to gait analyses conducted on instrumented treadmills by incorporating the belt speed into the calculations.

As stated in the introduction, algorithms based on deep learning methods have also been developed for gait event detection. Although we believe that these methods could be relevant, they require a large and, above all, homogeneous database (i.e., similar age-group and pathology), which is not representative of the people attending our laboratory. This is why we chose a more deterministic approach. However, although we proposed an algorithm based on the 3D components of the foot marker velocities, we also considered data based on marker position, velocity or acceleration, or any linear combination of these. Artificial intelligence processes might help to identify such potential data.

Conclusion

In this study, we developed a deterministic algorithm to objectively, accurately and precisely detect gait events, thereby limiting expert-rater bias in expert correction, which could lead to incorrect evaluation of spatiotemporal parameters, joint kinematics and kinetics. The approach involves considering the foot as only rigidly linked to the ground during the single stance phase and uses the 3D components of each foot marker.

We recommend adding a marker on the medial position of the 1st interphalangeal joint (Hallux) (Fig. 1). If the biomechanical foot marker set includes only two markers, we recommend placing them on the calcaneus and the Hallux. If four markers can be used, we recommend the 5th metatarsophalangeal joint, the 2nd metatarsophalangeal joint, the calcaneus, and the 1st interphalangeal joint.

To conclude, the Multi-Condition algorithm detects Foot Strike and Foot Off within a 3-frame range—better than expert-rater variability—in a few seconds of calculation, regardless of the pathology or gait pattern, even considering intra-individual variability. To promote adoption and ongoing testing, both the Multi-Condition algorithm and the parametric optimisation routine is available as open-access resources.