Classifying Human Movement Using Discrete Fréchet and DTW Distances

Akitaya, Hugo A; Carlos, João; De Almeida, Canto; Fonseca, Lucas; Shahrouzi, Gabriel

Abstract

Individuals with motor disabilities often rely on assistive devices for support. However, conditions that affect upper limbs, particularly hand function, pose a challenge in the user interface design. In this context, inertial sensor-based movement classification rises as a method to interact with these devices by exploring residual motor capabilities [17]. State-of-the-art movement classification systems are based on machine learning algorithms. These, even the ones described as "explainable", are not transparent and user-friendly when it comes to movement analysis and understanding, which is vital for this demographic [9, 16, 10].

Addressing these concerns, we present a novel movement classifier that uses Fréchet and Dynamic Time Warping (DTW) distances based on inertial data. Our classifier aims to be customizable to individuals with various levels of motor impairment, following the work by Fonseca et al. (2019 and 2022) [9, 8]. In these studies, sensors were placed on the upper limbs of participants with tetraplegia. Inertial data was captured in pre-defined time windows and used to calculate features as input for machine learning classifiers. In [9], Fonseca et al. developed an adapted version of the k-nearest neighbour using PCA for feature dimension reduction. In [8], Fonseca et al. achieved superior results with an SVM algorithm. However, in both cases, unknown movements were incorrectly classified as one of the trained ones. Furthermore, incorrect classifications were difficult to assess, particularly by the participants.

The classifier proposed here introduces several enhancements over existing models. Our nearest centroid classifier is straightforward in identifying movements outside existing classes, providing an intuitive visualization of movements, and is independent of specific features. The integration of "time warping" distance functions introduces flexibility to variances in the speed of movements, no longer requiring a time window. Finally, our classifier facilitates a swifter classification (both Fréchet and DTW distances take quadratic time to compute). This is particularly beneficial in assistive technologies, where rapid actuation is crucial.

Contribution. We present a novel nearest centroid classifier for movements that utilizes Fréchet and Dynamic Time Warping (DTW) distances. We aim to enhance explainability, a critical yet often underemphasized aspect in assistive technology interfaces [10]. To define the centroids under DTW for each class, we use DTW Barycenter Averaging (DBA). For Fréchet distance, we define a DBA-like heuristic to produce a representative curve for each class. We then generate a simple data set to test our system.

Related work. The training data for each class is given by a set of m polygonal curves, each with at most n points. We wish to obtain a representative (centroid) curve for each class to act as the class centroid. A natural choice would be to compute an "average" curve. A natural definition of an average curve is the curve that minimizes the sum of distances from the average curve to the curves in the set (as in [4]). This is also called the mean curve. Unfortunately, Bulteau, Froese and Niedermeier [6] showed that, under DTW distance, computing the mean curve is NP- and W[1]-hard (when parameterized by m). Buchin, Driemel and Struijs [4] show the same under discrete (and continuous) Fréchet distance. They also describe approximation algorithms that run in time polynomial in m, n and the length ℓ of the median curve. Petitjean, Ketterlin and Gançarski [13] introduced a popular heuristic algorithm called DTW Barycenter Averaging (DBA) to approximate the mean curve under DTW. Another good candidate for centroid is the center curve, defined as the curve minimizing the maximum distance from itself to a curve in the set. Buchin et al. [3] showed that computing the center curve under discrete Fréchet distance is NP-hard, and they also give approximation algorithms whose runtime depend on the length ℓ of the output curve. In the context of clustering, a method similar to DBA was proposed by Buchin et al. [5] for the continuous Fréchet distance to improve a candidate for a center curve. Our method is basically the same but applied to the discrete Fréchet distance. We are unaware of literature investigating the computation of the center curve under DTW distance.

Considerable previous work has been done regarding k-clustering using Fréchet and DTW distances ([4, 3 , 7, 11] to name a few). There are some applications that use DTW in nearest cluster classifiers [14, 12]. However, we are unaware of any application using Fréchet distance in the same setting.

Citation

Akitaya, H. A., Carlos, J., De Almeida, C., Fonseca, L., & Shahrouzi, G. (2024, November). Classifying Human Movement Using Discrete Fréchet and DTW Distances. Presented at 31st Annual Fall Workshop on Computational Geometry, Tufts University, Medford, MA, USA

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 31st Annual Fall Workshop on Computational Geometry
• Start Date: Nov 15, 2024
• End Date: Nov 16, 2024
• Acceptance Date: Oct 12, 2024
• Online Publication Date: Nov 17, 2024
• Publication Date: Nov 16, 2024
• Deposit Date: Dec 9, 2024
• Publicly Available Date: Dec 10, 2024
• Peer Reviewed: Peer Reviewed
• Keywords: Nearest centroid classifier; Fréchet distance; Dynamic Time Warping; Assistive devices; Movement analysis
• Public URL: https://nottingham-repository.worktribe.com/output/42831416
• External URL: https://www.cs.tufts.edu/research/geometry/FWCG24/papers/FWCG_24_paper_15.pdf