{'fraction_non_alphanumeric': 0.03880488249225724, 'fraction_numerical': 0.010488509486505478, 'mean_word_length': 4.501718213058419, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Gait Phase Partitioning and Footprint Detection Using Mutually Constrained Piecewise Linear Approximation with Dynamic Programming

Human gait analysis has been widely used in medical and health fields. It is essential to extract spatio-temporal gait features (e.g., single support duration, step length, and toe angle) by partitioning the gait phase and estimating the footprint position/orientation in such fields. Therefore, we propose a method to partition the gait phase given a foot position sequence using mutually constrained piecewise linear approximation with dynamic programming, which not only represents normal gait well but also pathological gait without training data. We also propose a method to detect footprints by accumulating toe edges on the floor plane during stance phases, which enables us to detect footprints more clearly than a conventional method. Finally, we extract four spatial/temporal gait parameters for accuracy evaluation: single support duration, double support duration, toe angle, and step length. We conducted experiments to validate the proposed method using two types of gait patterns, that is, healthy and mimicked hemiplegic gait, from 10 subjects. We confirmed that the proposed method could estimate the spatial/temporal gait parameters more accurately than a conventional skeleton-based method regardless of the gait pattern. key words: gait phase partitioning, piecewise linear approximation, dynamic programming, footprint detection, rehabilitation


Introduction
Human gait analysis has been widely used in many research fields, such as forensics [1]- [3], biomechanics, medical, and health research fields. There is a rich body of literature on human gait analysis, particularly in the fields of medical and health research, including research on change detection in the gait of elderly people [4], fall risk estimation [5], [6], gait evaluation of disabled people [7]- [9], and diagnosis support for normal pressure hydrocephalus [10] and mild dementia [11].
Human gait analysis techniques can be mainly divided into invasive methods and non-invasive methods. Invasive methods often use wearable sensors, such as accelerometers [12], [13], gyroscopes [14], [15], inertial measurement units [16], [17], and motion capture systems with markers attached to body joints [18], [19]. However, for invasive methods, it takes a relatively long time to attach the Manuscript  wearable sensors or markers to subjects' body parts and may also constrain subjects' movement, which is unsuitable in real applications. By contrast, because non-invasive methods do not require the attachment of a sensor/marker to the body, they are more suitable for real applications. A typical approach to non-invasive methods is video-based gait analysis. Generally, video-based gait analysis is further divided into two categories: appearance-based and model-based methods.
Appearance-based methods extract a gait feature directly from a captured video without assuming a human body model. Various appearance-based gait representations have been proposed, including the size-normalized silhouette sequence [20], gait energy image [21], frequencydomain feature [22], and local binary pattern [23]. However, the above-mentioned appearance-based features do not explicitly represent gait parameters, such as duration of stance/swing phases, step length (SL), stride, toe angle (TA), and walking speed. Those explicit gait parameters are essential for medical/health applications. For example, the relationship between spatio-temporal gait asymmetry and balance for chronic stroke patients has been reported [24].
Model-based methods [25]- [27] assume an articulated human body model, and fit it to a walking video. They are therefore generally more suitable to medical/health applications than appearance-based methods because the fit model is useful for extracting the above-mentioned gait parameters. However, traditional model fitting approaches suffer from error-prone estimation results and high computational cost. By contrast, recent deep learning-based approaches to human pose estimation [28]- [31] have improved the situation and hence are used in gait recognition field [32]. However, most deep learning-based approaches estimate the human pose frame by frame and hence do not guarantee temporal consistency (e.g., left and right feet are sometimes falsely swapped between adjacent time frames). Moreover, the joints of detailed body parts, such as ankles and toes, are still difficult to estimate accurately using these methods. Consequently, it may not be possible to accurately extract gait parameters, such as the single support duration (SSD) and the TA, even using deep learning-based pose estimation methods.
Therefore, we propose a non-invasive method using an RGBD (i.e., color and depth) image sequence to estimate Copyright c 2021 The Institute of Electronics, Information and Communication Engineers four gait parameters, that is, SSD, double support duration (DSD), TA, and SL, which are often used in medical/health applications [10]. For this purpose, we partition the entire image sequence into gait phases (e.g., stance and swing phases) to compute the SSD/DSD, and also extract a footprint on the ground plane to compute the TA and SL, as outlined in Fig. 1.
Regarding gait phase partitioning, we first extract the position sequences of the left and right feet using depth image analysis. Because the position remains still during the stance phase and moves during the swing phase, we cast stance/swing phase partitioning as the problem of the piecewise linear approximation of the position sequence. A straightforward application of the piecewise linear approximation to each foot may not always result in a reasonable phase transition; for example, after a swing phase of the left foot, another swing phase of the same foot may come before a swing phase of right foot, which is unlikely to occur in reality. Therefore, we propose a unified piecewise linear approximation method in which the piecewise lines for the left and right feet are constrained by each other to prevent the above-mentioned unlikely transition.
Regarding footprint extraction, we build our method on a feature-point accumulation method [33], where a series of footprints on an image plane is used as a guide for pedestrian detection. If we directly apply the original method [33] for our purpose, we may, however, suffer from blurry footprints that include accumulated feature points not only during the stance phase but also during the swing phase, which can still be a sufficient guide for pedestrian detection but would be insufficient for the accurate estimation of the TA and the SL. Therefore, we extend the method to obtain a clearer footprint by accumulating features during the stance phase only, which are recognized by the aforementioned gait partitioning method. The contributions of this paper are mainly summarized as the following two points:

Mutually constrained piecewise linear approximation for gait phase partitioning
Piecewise linear approximation has been widely studied and many approaches using dynamic programming (DP) have been proposed for a curve [34], [35], waveform [36], and polygon [37]. They aim at a single target (e.g., point series of a single closed curve); however, we aim at jointly partitioning the phases of both the left and right feet. More specifically, we design a DP-based framework of joint piecewise linear approximation on position sequences of the left and right feet, where invalid states (e.g., a state for which the left and right feet are swung simultaneously) and invalid state transitions (e.g., the direct transition from the left swing phase to the right swing phase) are prohibited.

Footprint extraction using toe edge accumulation
The original method [33] accumulates feature points regardless of the gait phases; however, we accumulate foot edges only for the stance phase because the footprint is observed in it, which contributes to clearer footprint extraction that is free from unnecessary and irrelevant edges during swing phases. Additionally, the original method accumulates features on an image plane; however, we do this on the ground plane via depth image analysis, which enables us to obtain the TA and SL.

Gait Phase Partitioning
A gait cycle is partitioned into a different number of phases depending on the purpose of the research. For example, a two-phase model [38], [39] includes the stance phase and swing phase. A three-phase model divides a gait cycle into two half-stance phases and a swing phase [40]. The first half-stance phase ranges from the heel strike to the middle of the mid-stance, whereas the second half-stance ranges from the middle of the mid-stance to toe-off. A six-phase model is composed of the initial contact, loading response, midstance, terminal stance, pre-swing, and swing phase [41]. In this study, we use the simple yet useful two-phase model because the two phases, that is, stance and swing phases, capture the most fundamental part of the gait, and can be observed by a vision sensor.

Machine Learning-Based Approaches
Machine learning-based approaches typically train a gait phase partitioning model using training data with groundtruth labels of the phases. Liu and Sarkar [42] proposed a gait phase partitioning method for gait recognition using a population hidden Markov model. They divided the gait cycle into 20 phases in a temporally uniform manner, and hence the partitioned phases did not correspond to physical gait events, such as stance phase and swing phase, which are required to compute gait parameters such as the stance phase time. Tang et al. [43] proposed a deep learning-based method to output the toe-off event using a consecutive silhouettes difference map generated by the frame difference. However, the toe-off event alone is insufficient for calculating gait parameters such as the stance phase time, which also requires the heel strike event.
Additionally, the necessity of a sufficient amount of training data is another shortcoming of machine learningbased approaches, and this becomes more problematic when they are applied to medical/health fields. This is because it is time-consuming to collect training data for each targeted disease in medical applications, such as when recruiting patients with a specific disease and setting up a data capturing system in a hospital or care home. Although we may construct a generic pre-trained model that is trained on healthy subjects, it may not work well for pathological gait because of significant differences in gait between healthy subjects and patients.

Rule-Based Approaches
Rule-based approaches partition the gait phase using predefined rules without the training data that are required for machine learning-based approaches.
Auvinet et al. [44] proposed a heel strike detection algorithm using an RGBD sensor by searching the temporal local maxima of the distance between the left and right knee joints along the walking longitudinal axis. However, the heel strike event alone is insufficient for calculating gait parameters such as the stance phase time, which also requires the toe-off event. Latorre et al. [45] proposed a method for detecting the heel strike and toe-off event based on the antero-posterior distance between the ankle and sacral joints, which were extracted using the Microsoft Kinect SDK. More specifically, it detects the heel strike and toeoff when the ankle joint is located most anterior and posterior to the sacrum, respectively. However, the method does not guarantee a physically plausible gait phase transition because it processes the left and right feet independently; for example, it may skip a double support phase when toe-off is accidentally detected earlier than the heel strike.

Footprint Detection
Promising approaches to footprint detection are methods that use the temporal accumulation of feature points (e.g., corners or edges) at each pixel in a gait image sequence [33], [46], [47]. The intuition behind this approach is based on the fact that, during the stance phase (i.e., time duration from the heel strike to toe-off), the foot remains at the same place, and the accumulation of foot feature points over time highlights the foot position during the stance phase (i.e., heel strike or toe-off position).
Early work by Bouchrika et al. [33] demonstrated that a series of heel strikes is highlighted well by the corner points voting over time, and that they are useful as a guide for pedestrian detection. Jung et al. [46] further extended the previous work [33] to obtain a more accurate foot position during the stance phase. They extracted key frames at the local maxima of the vertical head position time-series and composed a filtered accumulated image using the silhouette at each key frame, which more clearly highlighted the foot position at each step. Because these two methods accumulate feature points on an image plane, the position/posture of the footprint in the world coordinate cannot be estimated.
By contrast, Evans et al. [47] used multiple calibrated cameras to extract footprints on the floor plane (i.e., the world coordinate). They accumulated foreground pixels over multiple views and frames (time) on the floor plane and then extracted footprints using thresholding. The method is, however, not practical in a clinical setting because it takes time to set up and calibrate multiple cameras onsite.

Overview
In this section, we outline the proposed method along with Fig. 1. Given background and input depth images, we extract a silhouette of a person using depth-based background subtraction [48], and then project it to the world coordinate to obtain a three-dimensional (3D) point cloud.
Next, we extract a left/right foot point cloud, compute its center of gravity (CoG), and then partition temporal sequences of the CoG into gait phases using the proposed piecewise linear approximation. Thereafter, we extract edges from RGB images and then project them to the world coordinate to obtain a 3D edge point cloud.
Subsequently, we select foot edge points based on the vertical position of the 3D edge points and then accumulate the edges during the stance phases obtained by the above-mentioned gait phase partitioning. Finally, we compute the spatio-temporal gait parameters (e.g., SL and SSD) using the foot model fitted to the accumulated edge image on the floor plane.

Floor Plane Detection
The floor plane is extracted from background RGB and depth images averaged over multiple frames. The area of the floor plane, where a carpet with a pre-defined color is placed, is detected using a chroma key technique (Fig. 2). The depth data in the floor plane area are converted to a 3D point cloud, and then the floor plane geometry (e.g., the surface normal) is obtained using a plane model fitted using RANSAC [49], [50].

Silhouette Extraction
Silhouettes were extracted from the background and input depth images using depth-based background subtraction [48], which considers the depth value in addition to the observation probability. An example of the input depth image and extracted silhouette is shown in (Fig. 3 (a), (b)).

World Coordinate Setting
To calculate the direction of the left and right feet, and the SL with respect to the walking direction, we define the Zaxis of the world coordinate to coincide with the walking direction, whereas we define the Y and X-axes as the vertical direction (i.e., the direction of the surface normal of the floor plane) and remaining orthogonal direction (i.e., mediolateral direction), respectively.
For this purpose, we estimate the walking direction from the whole body CoG sequence. First, we compute the CoG of the point cloud of the extracted silhouette ( Fig. 3 (c)), and then apply a moving average filter to the time-series of the CoGs to obtain the whole body CoG. We then obtain the walking direction using the line segment that connects the start and end points of the whole body CoG. We perform all subsequent calculations in this world coordinate system.

Foot Position Extraction
We extract left and right feet position sequences from the 3D feet point cloud of a person, which are used as input data for gait phase partitioning. First, we extract the top and bottom of the person point cloud, and then compute the person's height as their difference in the vertical direction. Next, we extract the left and right feet centroid positions for each frame.
We extract the feet point cloud as a subset of the point cloud that is included within 10% of the body height from the bottom (Fig. 3 (c)), and compute the centroid of the point   Fig. 3 (c), respectively). The Z-axis component of the centroid in the t-th frame is set to z cog f (t), where f means a variable that represents either the left or right foot, that is, The above-mentioned straightforward method may, however, fail to estimate the foot position when the rear foot is not sufficiently visible because of self-occlusion (e.g., when walking with the legs crossing). Specifically, when the rear foot is not visible, the method forces the point cloud of the other visible foot to be partitioned into the left and right foot, and hence the rear foot position is suddenly located near the visible front foot position.
Moreover, outliers are more clearly observed in the medio-lateral component (X-axis) than the walking direction component (Z-axis) because the Z-axis components typically change a great deal during walking, that is, it is difficult to differentiate the sudden change because of mis-detection from the normal walking movement, whereas the X-axis component remains relatively still, even during walking. Therefore, we detect the mis-detection by identifying the outliers based on the medio-lateral component ( Fig. 4 (a)). More specifically, we observe both raw timeseries and smoothed time-series, and determine that misdetection takes place when the raw time-series is clearly biased to the other foot position compared with the smoothed time-series.
First, we define the medio-lateral (X-axis) component of the foot position in the t-th frame as x cog f (t), and its smoothed version using a moving average filter asx cog f (t), (see Fig. 4 (a)). Given a set of time indices defined as T = {1, . . . , T }, where T is the length of the time-series, that with the correct estimation (i.e., inliers) is defined as where x thresh is the threshold for outlier detection and g f is a sign indicator for foot f to judge whether the foot position is biased to the other foot, which returns +1 and −1 for the left and right feet, respectively. We then recover the Z-axis components of the outliers by applying a cubic spline interpolation obtained from the inlier set T , and define the interpolated Z-axis component at the t-th frame asz cog f (t). The final foot position in the t-th frame is obtained as . (2)

Piecewise Linear Approximation Using DP [37]
We build our gait phase partitioning method on the piecewise linear approximation using DP [37]. The original method [37] aims at piecewise linear approximation for a two-dimensional (2D) polygonal curve; however, we apply it to the foot position sequence {z f (t)}. In this section, we briefly describe the method [37] for our problem setting to better understand the proposed method and make this paper self-contained. Additionally, for simplicity, we omit the subscript for the foot in this section. The piecewise linear approximation for the point sequence is defined by either of the following two problems: where a and b are the inclination and intercept of the line segment, respectively, the approximation error for the m-th line segment by the least square is Consequently, the total minimum accumulation error E(M) over M line segments is derived as To solve this optimization task, a DP algorithm [51] is used. We define a discrete 2D state space Ω = {(t, m) | t = 0, . . . , T, m = 0, . . . , M}, where each state (t, m) represents a sub-problem of the piecewise linear approximation of the 2D point subsequence up to the t-th frame, that is, P 1:t = {p(1), . . . , p(t)} by m line segments. In the DP framework, note that state (T, M) represents the original problem and hence is regarded as the goal state, whereas the state (0, 0) is the initial state. Additionally, a path from the initial state (0, 0) to the goal state (T, M) contains a set of pairs of an end frame and a line segment index Q = {(t m , m) | m = 0, . . . , M}, and hence it naturally corresponds to one approach to piecewise linear approximation with M line segments (see Fig. 5).
The remaining problem is how to obtain the optimal path that satisfies Eq. (4). For this purpose, we define the accumulation error D(t, m) at state (t, m), that is, the minimal error given by the optimal piecewise linear approximation of the subsequence P 1:t by m line segments. After initializing the accumulation error at the initial state as D(0, 0) = 0, we then recursively update it for each state as where t s (t, m) is the time index of the previous state that minimizes the accumulation error D(t, m) up to the current state, and T (t) is a set of time indices of possible previous states that can be transitioned to the t-th frame, and is simply defined as T (t) = {t | t < t}. Once the update reaches the goal state (T, M), we recursively obtain the optimal path by backtracking with t s (t, m); for example, given the optimal solution to the end frame of the m-th line segment t m , the previous state is simply derived as t m−1 = t s (t m , m). Second, we describe the min-# problem. Because this problem considers the maximum error tolerance Δ tol per line segment, the set of possible previous time indices T in Eq. (6) is redefined to satisfy the condition T (t) = {t | t < t, e 2 (t , t) < Δ tol }. We then scan the state in the last frame {(T, m) | m = 1, . . .} and find the minimum M * that can Once we obtain the goal state (T, M * ), we obtain the optimal path similarly to the case of the minproblem.

Definition of States and Transitions for a Gait Cycle
As discussed in the Introduction, if we directly apply the above-mentioned piecewise linear approximation to each left and right foot independently, reasonable phase transitions may not be necessarily obtained (e.g., simultaneous swing phases for both the left and right leg take place). Therefore, we extend it to a mutually constrained piecewise linear approximation to guarantee a reasonable phase transition between the left and right legs. More specifically, we define four states S = {s 1 , s 2 , s 3 , s 4 } for a gait cycle, as shown in Table 1, and also consider cyclic state transitions H = {(s 1 → s 2 ), (s 2 → s 3 ), (s 3 → s 4 ), (s 4 → s 1 )}, as shown in Fig. 6. We then define a 2D discrete state space for DP as Ω cycle = {(t, s) | t = 0, . . . , T, s ∈ S}, whereas the conventional method defines the 2D discrete space of time and piecewise line index Ω for each left and right foot independently. We then obtain the state transition by finding the optimal path in the state space Ω cycle (see Fig. 7 (b)), whereas the conventional method does this in the state space Ω (see Fig. 5 (b)).

Phase-Dependent Piecewise Line Segments
The conventional piecewise linear approximation does not consider constraints on the piecewise line segments; however, we consider them for a more reasonable approximation. Specifically, the foot position moves during the swing phase, whereas it essentially stays still during the stance phase. Therefore, we modify the line segment equation to enforce this property: Additionally, each stance and swing phase should last for a certain period, that is, it is unlikely that a swing phase starts within a short moment (e.g., a few milliseconds) after a stance phase starts, and hence we introduce the minimum and maximum time elapsed for each phase as Δt min and Δt max , which we use later to narrow the range of state transitions.

Keeping/Switching Transitions
Moreover, the stance phase for each foot lasts for three states (i.e., s 2 , s 3 , and s 4 for the right foot and s 4 , s 1 , and s 2 for the left foot), whereas the swing phase lasts for only a single state (i.e., s 1 for the right foot and s 3 for the left foot), as shown in Table 1. Because it is reasonable to approximate each swing and stance phase using a single line segment, we should keep the single line segment at state transitions within the stance phase (we call it a keeping transition), whereas we should switch to a new line segment at the transition between the stance and swing phases (we call it a switching transition), as summarized in Table 2.
To reflect this in the piecewise linear approximation using the DP framework, we need a special treatment for line fitting errors when transitioning from the previous state (t , h(s)) to the current state (t, s), where h(s) is a mapping function from the current state s to the previous state defined as h(s) = (s − 1) mod 4. For example, assuming a transition from the previous state (t , s 3 ) to the current state (t, s 4 ) for the left foot, the line fitting error e 2 left (t , t) between the t p -th frame and t-th frame alone does not make sense because the stance phase has already started, not in the t -th frame but at the beginning of state s 2 (let it be the t p -th frame). By taking this into account, the updated line fitting errorẽ 2 left (t, t , s 4 ) can be computed by first cancelling (subtracting) the line fitting error e 2 left (t p , t ) between the t p -th frame and t -th frame, and then adding the line fitting error e 2 left (t p , t) between the t p -th frame and t-th frame.
Consequently, we need to store not only the time index t s (t, s) of the optimal previous state but also the footdependent time index t p f (t, s) of the optimal previous phase. To summarize, the foot-dependent time index t p f (t, s) follows from the optimal previous state if its transition is a keeping transition: where H keep f is a set of keeping transitions for foot f defined in Table 2. Finally, we can compute the updated line fitting errorẽ 2 f (t , t, s) as

Recursive Update
We can now define the recursive update for the mutually constrained piecewise linear approximation using the DP framework. Specifically, the time index t s (t, s) of the optimal previous state and the cumulative error D f (t, s) are defined as where Note that Δt min and Δt max denote the minimum and maximum time elapsed for each state, respectively, as we described above. Additionally, note that the cumulative errors at the initial states are initialized as D f (0, s) = 0 ∀s. Once we complete the update, we determine the optimal terminal state: and then obtain the state transition by backtracking based on the stored time indices for the optimal previous states t s (t, s) similarly to the case of the conventional piecewise linear approximation.

Toe Edge Extraction on the Floor Plane
As addressed in the overview section, the first step to footprint detection is toe edge extraction on the floor plane. For this purpose, we first extract an edge image from an input RGB image using an edge detection method [52], which outputs the edge likelihood per pixel (see Fig. 8 (a)). We then convert the edge pixels in the RGB image to those in the depth image coordinate, and obtain a 3D edge point cloud by projecting the converted edge pixels to the world coordinate based on a depth value for each edge pixel (see Fig. 8 (b)). Thereafter, we set a 3D toe ROI at the t-th frame around the foot position on the floor plane [x cog where we experimentally set Δx = 20 cm, Δy = 3 cm, and Δz = 20 cm.
Next, the 3D toe edges in the ROI X ROI f (t) for each stance phase of each foot are voted on the floor plane image whose image resolution is 1 cm 2 /pixel. We set a voting weight w for the edge intensity I using a type of soft thresholding with a hyperparameter α as w = 1−e −αI , whose range is [0, 1]. Once we obtain the toe voting value at the (i, j)-th pixel as I vote (i, j), we then obtain its smoothed version using max pooling with distance attenuation: (16) where N (i, j) is the nearest region around (i, j) and β is a hyperparameter that controls distance attenuation. Fig. 8 Toe edge extraction. In (a), the brighter the pixels, the higher the edge likelihood. In (b), cyan and magenta represent the right and left toe edge points, respectively.

Footprint Estimation Using Ellipse Model Fitting
We estimate the position and orientation of a footprint by fitting the ellipse model to the smoothed voting imageĨ vote . The ellipse model can be defined by five parameters θ = {a, b, i 0 , j 0 , θ}, where a and b are the half lengths of the major and minor axes, respectively, (i 0 , j 0 ) is the ellipse center, and θ is the inclination angle of the major axis, and its equation is Next, we introduce a set of pixels M(θ) that belongs to the ellipse with the parameters θ, and then we obtain the optimal parameter θ * by maximizing the summation of the votes as

Gait Feature Extraction
In this section, we introduce four gait features using the proposed method that we use for accuracy evaluation in the experiments.

Single support duration (SSD) [s]
The SSD is the time when either the left or right foot is in the stance phase while the other foot is in the swing phase. It is specifically the time duration of state s 1 and s 3 for the left and right feet, respectively (see Table 1 and Fig. 6).

Double support duration (DSD) [s]
The DSD is the time when both feet are in stance phases. It is specifically s 4 or s 2 in the case in which either the left or right foot is in front, respectively (see Table 1 and Fig. 6).

Toe angle (TA) [deg]
The TA is the orientation of the ellipse chosen to fit the footprint. The TA is 0 [deg] when it is parallel to the walking direction. Additionally, the TA is positive if it is in the lateral direction and vice versa (see Fig. 9 (a)).

Step length (SL) [m]
The SL is the difference between the front ends of the Fig. 9 Spatial gait features. elliptic models of two temporally adjacent left and right stance phases in the walking direction (see Fig. 9 (b)).

Setup
We collected data from 10 subjects: eight men and two women. We asked each subject to walk along a path in a normal manner. Moreover, to investigate the effectiveness of the proposed method for a pathological gait, we also asked each subject to mimic a right-side hemiplegia patient by shortening the SSDs of his/her right foot, by dragging his/her toe during the swing phase, and by positioning his/her toe outward. We set up a data capturing system for experimental validation. We installed an RGBD camera (Microsoft Kinect v2) and three color cameras (PointGrey Flea3 FL3-U3-13E4C) with a lens (SPACECOM 3.5 mm) on a straight walking path of 6m, as shown in Fig. 10. The RGBD camera captured an RGB image with a 1,920 × 1,080 pixel-size and a depth image with a 512 × 424 pixel size at 30 fps, which were used as input data for the proposed method. By contrast, each color camera captured an RGB image with a 1,280 × 1,024 pixel size at 60 fps, which was used to prepare the ground-truth gait features. We installed one of the three color cameras on the side of the walking path and the other two on the ceiling.
We manually detected the heel strike and toe-off event to define the ground truth of the SSD and DSD using the side view camera. By contrast, we used the cameras installed on the ceiling to obtain the ground truth of the TA and the SL. For this purpose, we converted a raw captured image ( Fig. 11 (a)) to a calibrated image ( Fig. 11 (b)) using lens distortion correction and homography transformation, and then obtained the ground truth of the TA and SL by manually fitting the ellipse model to the foot. For the calibration purpose, we placed white markers at 50 cm intervals, and set the image resolution after the homography transformation to 1 cm 2 /pixel.
The average absolute error between the estimated gait features and the ground truth gait features was evaluated for each left and right foot. As a benchmark, we adopted a method proposed by Latorre et al. [45], which is based on skeletal information detected by Kinect, and evaluated the errors in the same manner, except for the TA because Latorre et al. did not propose a method for estimating the TA. The paired t-test was used to calculate the statistical significance probability between the proposed and benchmark method. The significance level was set to 5% in each feature.

Results
Data for a total of 50 steps (26 steps to the right and 24 steps to the left) and 161 steps (81 steps to the right and 80 steps to the left) were collected and analyzed for normal gait and mimicked hemiplegic gait, respectively.  We summarize the estimation accuracy of gait features in Table 3. Regarding the temporal parameters (i.e., SSD and DSD) of a normal gait, the estimation error of the proposed method was 0.04 s at most, and the laterality was 0.01 s. Additionally, regarding the spatial parameters, the SL estimation error of the proposed method was 0.03 m at most, and the laterality was 0.01 m. The TA estimation errors were 4.6 deg and 5.5 deg for right and left feet, respectively. There was no significant difference between the proposed method and the benchmark method for SSD, DSD, and SL.
By contrast, regarding the temporal parameters of the mimicked hemiplegic gait, the estimation error of the proposed method was 0.05 s at the maximum, and the laterality was 0.01 s. Moreover, the proposed method yielded a 0.06 s and 0.04 s smaller SSD and DSD than the benchmark method for the right side, which was the paralyzed side. Regarding the spatial parameters, the SL estimation error of the proposed method was 0.03 m at most, and the proposed method yielded a 0.04 m smaller SL error than the benchmark method. The right and left side TA errors were 5.7 and 3.3 deg, respectively. Both SSD and DSD had significantly smaller errors on the paralyzed side than the benchmark method. The error of SL was significantly smaller than that of the benchmark method on both the non-paralyzed  [45] 0.10 (0.05) 0.05 (0.06) 0.08 (0.05) 0.06 (0.05) --0.07 (0.08) 0.04 (0.03) There are average absolute error and standard deviation in parentheses of each feature. †: The error of the proposed method is statistically significantly smaller than that of the benchmark method. side and the paralyzed side.

Discussion
First, we discuss the difference in the estimation accuracy between the normal and mimicked hemiplegic gait. There was no significant difference for SSD, DSD, and SL between the proposed and benchmark method in the normal gait. However, the proposed method showed significantly smaller error than the benchmark method in mimicked hemiplegic gait in SSD, DSD, and SL especially on the paralyzed side. This is because pose estimation sequences obtained using Kinect may well fit the normal gait, but not the movement of paralyzed limbs. By contrast, the proposed method, which does not require training data, fits a variety of gait types well, including the hemiplegic gait used in the experiment.
In [53], the authors proposed a method for estimating temporal parameters using the IMU, and reported errors with respect to the method using marker-based motion capture. The results were reported as 12.9 ms for the swing time and 10.3 ms for the stance time. Although higher accuracy than that achieved using our method has been reported, we consider that it is difficult to maintain the same accuracy for people with disabilities because the authors' approach is a learning-based method in which only healthy subjects are used.
In [54], the authors proposed a method to estimate the heel strike and toe-off timings while walking on a treadmill using marker-based motion capture data, and reported the error from the method using ground reaction force (GRF) plate data. The subjects were seven healthy people and 11 impaired people, including stroke survivors. In the healthy subjects, the average error was within one frame (16.7 ms) of the GRF events for both event timings. In the impaired subjects, the events were within two frames (33.4 ms) of the GRF events, and the estimation error increased. Because the authors did not estimate the swing time or the stance time, it was difficult to compare their results with those of the proposed method. However, we consider that our method is superior in that the estimation accuracy can be maintained, even for impaired people.
Additionally, it is generally difficult to estimate a TA using a depth sensor such as Kinect because the depth difference between the foot and the floor plane is subtle; however, the proposed method achieved 5 deg accuracy approximately by incorporating a color edge accumulation framework. We consider the TA estimation accuracy to be meaningful because a therapist generally measures the joint angle with a resolution of 5 deg [55].

Conclusion
We proposed a novel gait phase partitioning method and footprint detection method using one RGBD sensor. The proposed method was effective for both a healthy and mimicked hemiplegic gait, and more accurate than the conventional skeleton-based method. Some issues remain in the proposed method.
First, regarding the gait phase partitioning algorithm, we approximated the swing phase using a single line segment, assuming that the foot swing speed was constant. It is possible that some people with disabilities may drag the toe at the initial swing phase and the swing speed may not be constant. Therefore, it is necessary to improve the algorithm to approximate the swing phase for some line segments according to the change in the swing speed.
Second, regarding the footprint detection algorithm, a carpet is required to reduce the luster to avoid detecting the edges of the person reflected on the floor. It is necessary to improve the toe edge detection method, which is robust to the floor material.
Additionally, because of the characteristics of the sensor, the footprint detection accuracy changes according to the distance from the sensor. It is also necessary to evaluate the appropriate measurement range in a clinical measurement. We will develop a gait analysis system with improvements to the above issues and proceed with application experiments in clinical settings.