An Optimisation Algorithm for enhancing precision in stride segmentation using Multi-Dimensional Subsequence Dynamic Time Warping on sensor data

Gait analysis is the systemic study of human locomotion and plays an important role in detecting patterns in such activity. Inertial Measurement Units (IMUs), due to their very low consumption, can be battery powered and are promising tools for long-term ambulatory monitoring outside clinical facilities or laboratories; moreover, considering their low cost, inertial sensors have become particularly popular in the gait analysis research and development field. Stride segmentation, answers the specific clinical needs for analysing human gait. Stride segmentation is the procedure of dividing the gait into strides, where a stride begins with one ’heel strike’ (i.e when the heel makes contact with the ground) and ends with the heel strike of the following step. The ability to automatically and robustly segment individual strides from gait sequences derived using inertial sensors during different gait activities is crucial for the estimation of gait parameters and for the creation of a reliable gait dataset, without requiring the manual segmentation of recordings. When considering stride segmentation done with IMUs, multiple techniques and algorithms have been proposed: among those, template-based methods such as Dynamic Time-Warping algorithms have also shown promising performance due to their ability to identify multiple strides in a sequence, even though they might differ in length and amplitude. In this work, a new algorithm for segmenting strides given raw data built upon the Multi-dimensional Subsequence Dynamic Time-Warping (msDTW) Algorithm proposed by Barth et. al is presented, extending and extensively explaining the functionality and the procedures that need to be followed in order to implement it. With the goal of enhancing the performance of the msDTW, an Optimisation Procedure which improves the precision of the stride segmentation and reduces the computational time of execution of the segmentation is proposed. The dataset used in this work is provided by Luo,Y et al., from which data from two IMU sensors placed on the right shank and on the right thigh are considered, representing subjects walking on a planar surface, walking on a positive tilt, walking on a negative tilt, ascending stairs and descending stairs. All these recorded data are associated with the category of Free Walking, i.e. uncontrolled environment. The performance of a Peak Detection Algorithm, the msDTW algorithm proposed by Barth et. al and the proposed msDTW Optimised Algorithm is compared in terms of Accuracy, Recall, Precision and F1-Score; moreover, a comparison of the msDTW Optimised method with Barth et. al’s msDTW is provided in terms of time of execution. With the use of the proposed msDTW Optimised method it was possible to identify the best Sensor Set for each activity considered and achieve a Precision of 99.05% for the activity Stair Ascent Walking, an Accuracy of 98.26% for the activity Downhill Walking and a reduction of the computation time of up to 37.97%, when compared to Barth et. al’s msDTW. Finally, a demonstration that the proposed algorithm is a robust and reliable alternative method for the construction of a gait dataset which requires no human involvement is provided. Thanks to its high Accuracy and Precision, one can argue that the proposed method is suitable for clinically relevant applications and could be adapted to different gait activities and scenarios.