# Recovering Walking Trajectories from Local Measurements and Inertia Data

Authors: Lifeng Zhu; Chenghao Xu; Ke Shi; Wei Li; Aiguo Song; Xinhua Tang
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Capturing walking trajectories is useful for motion planning and various location-based services. Traditionally, it is a challenging task because it is expensive to install infrastructures, especially in an outdoor setting. As another choice, the reconstructed walking trajectories suffer from the drifting problem from captured inertia data. In this work, we study the biped walking motion and propose a method to recover walking trajectories by introducing local measurements between the feet to the system, in combination with the orientation from inertia data. We design a few local measurements which can be passively captured. After analyzing these measurements, the walking trajectory is progressively recovered by solving a set of small-scale optimization problems. By comparing with the trajectories extracted from optical motion capture systems, we tested our method on different subjects, and the quality of the recovered walking trajectory is evaluated.


---

## Body

## 1. Introduction

As a typical motion of humans, walking is the most common way to locomote. Capturing the walking trajectories is helpful for localizing the subject, synthesizing walking motions, or even understanding the human activities. Sensing walking trajectories is one important task in various areas, including humanoid robots, human-robot interaction, location-based services, rehabilitation, and computer graphics.There are various solutions to capture the walking trajectories with different degrees of precision. For outdoor walking, global navigation satellite system (GNSS) is widely used to track the pedestrians. However, the precision of GNSS positioning is usually within 5 to10 meters. Due to the vulnerability of the GNSS wireless signal, the performance of GNSS stand-alone navigation equipment is susceptible to multiple nuisances including interference, multipath effect, and spoofing. In this context, additional sensors or techniques are normally needed to enhance the navigation system.On the contrary, optical motion capture systems can be used to precisely capture the indoor walking motion, from which the walking trajectory can be easily extracted. However, it is expensive to install corresponding infrastructures. Other active systems such as ultra-wide band radio positioning systems are also suffering from similar problems. The requirements of preinstalled infrastructures also prohibit their use in outdoor environments. In addition, multipath effects and occlusion also introduce complex errors to the captured position.A unified way to get the walking trajectories in both indoor or outdoor environments is to extract them from the data measured by inertial sensors. The dead-reckoning method has been applied to compute the walking trajectories. Although measurements from acoustic or optical sensors can be fused to reduce the drift commonly observed in inertial systems, the accumulated error is still hard to eliminate in walking motion. Even equipped with zero velocity update, it is still challenging to have the integrated sensory system work for a long period.Data fusion is another trend to deal with the challenges in navigation. Advanced Kalman filters are proposed to integrate the information from inertia sensors, GNSS, and optical data. Due to the uncertainty of the noise model, it is important to estimate the statistical characteristics of system noises if the walking trajectory should be stably recovered. More prior knowledge on the walking pattern will be useful to reconstruct the walking trajectory.In this work, we propose a new type of measurements which can be fused to sense walking trajectories. Note that the generic positioning techniques do not make full use of the features of the walking motion itself; we therefore adapt the positioning techniques by considering the features of biped walking motion, which leads to a method specially designed for recovering walking trajectories of humans. We make assumptions that there is always one foot standing on the ground with no slippage. Our insight is that, by regarding the standing foot as a base station, the relative position of the moving foot will be inferred. By switching the standing foot and iteratively updating the position of the stationary foot in the walking session, we can recover the entire walking trajectory.Based on the observed walking patterns, we design a set of candidate local measurements, which record the relative distance between two feet and can be used to reconstruct the walking trajectories. We then study the walking motion from the trajectories extracted from optical motion capture (mocap) systems and design algorithms to reconstruct the walking trajectories from the designed measurements. We test our method on different subjects on the mocap data, and the quality of the recovered walking trajectory is evaluated. We also make a simplified system to prototype our method with a long walking sequence in an outdoor space and report our preliminary results.


## 2. Related Work

Probably, the most reliable way to capture the walking trajectories is to use optical motion capture systems [1, 2]. By installing a set of calibrated cameras, retroreflective markers in sight of the cameras are precisely tracked. It is usually expensive to set up the infrastructures of optical motion capture systems. Recently, markerless optical motion capture systems are also widely used [3]. They work well only in sight of the cameras, which limits their usage in open environments.Another strand of motion capture systems is based on inertial sensors, such as Xsens [4]. In inertial motion capture systems, gyroscopes or accelerometers are placed on feet, and the rotational and linear accelerations are measured. The walking trajectories are recovered by integrating the accelerations, which will unfortunately drift over time periods. Zero velocity update is a commonly used technique to alleviate the problem [5–7]. However, it still does not guarantee to work in a long period.In parallel to inertial motion capture systems, other self-contained systems based on acoustic sensors [8], radio signals [9], pressure sensors [10], magnetism [11], exoskeletons [12], or even body-mounted cameras [13, 14] were also proposed recently. To further overcome their shortcomings, hybrid systems integrate multiple types of sensors and fuse different measurements [15–17]. Advanced Kalman filters are promising tools to fuse information from different sources. Based on the maximum likelihood principle, the data from inertia sensors and GNSS are fused for locating vehicles [18]. In addition, moving horizon estimation [19] and model prediction [20] have also been introduced to improve the unscented Kalman filter. These systems are mostly for general purposes and not aware of the walking motion. We propose to add motion priors to help the reconstruction of walking trajectories.There are various ways to incorporate motion priors into motion capture. The captured data are regularized by comparing with the kinematically or dynamically simulated motion [14, 17]. Gait model was also introduced as a prior to assist the motion capture from visual and inertia data in a limited space [21]. We propose to combine different sensory data in this task and show how they work in a large space. As another class of solution, data-driven methods were reported to stabilize the captured motions. By preparing a database of captured motions, sparse accelerometer data are used to retrieve the closest motion [22, 23] as the reconstructed motion.


## 3. Materials and Methods

In this section, we will firstly introduce the local measurements what we choose for recovering the walking trajectories. After preprocessing the measurements, we show the observed pattern of walking motions. By exploiting the walking pattern, we design an algorithm to reconstruct the foot trajectories from the chosen measurements.


### 3.1. Measurement Design

#### 3.1.1. Measurements

The local measurements what we use are shown in Figure1. We locate three markers on each foot. Taking the left foot as an example, one marker p¯1 is at the heel, one marker p¯2 is at the big toe mound, and the other marker p¯3 is at the inner ankle. Corresponding markers on the right foot are denoted by q¯1, q¯2, and q¯3. The Euclidean distance between each pair of the markers is measured when the subject is walking. In the following, dijk=dpik,qjk, i, j ∈ {1, 2, 3}, denotes the measured distance between the marker pi and qi at the kth frame. During walking, the distances between the three markers on the same foot are constant, which will be presented by pij=dp¯ip¯j and qij=dq¯iq¯j; pij and qij are measured once before walking using rulers. These distance measurements are the key components to reconstruct the walking trajectories. The heading orientations of the two feet hl and hr are also measured from inertia sensors during walking. In addition, we also measure the pressure by attaching multiple force-sensing resistors under the heel and toe mound regions to indicate the standing status. The overview of our information fusion strategy is shown in Figure 1(b). In the next section, we will elaborate on the details of our solver.Figure 1
(a) The designed measurements. The markersp¯i and q¯j and their relative distances dij (three of them are illustrated in this figure) on two feet together with the heading directions hlandhr are designed to be the local measurements in our method and the pressures under the heel f1, g1 and toe mound f2, g2. (b) The overview of the information fusion pipeline.
(a)(b)


#### 3.1.2. Design Consideration

We design the markers at the locations in which they are visible so that it is possible to acquire their relative distances. We propose to use three markers per foot if we are interested in getting the three-dimensional (3D) walking trajectory. We can remove the markersp¯3 and q¯3 if we only need to obtain the two-dimensional (2D) walking path. In the following, we will establish our method for the 3D cases first and then briefly talk about the 2D cases. It seems reasonable to set only one marker on each foot and reconstruct the trajectories by adding the orientation information from a compass. However, in this case, anthropometric data will be required, and the error of the measured anthropometry may lead to observable systematic errors.


#### 3.1.3. Preprocessing

After the local measurements are obtained, we preprocess the signals before using them to recover the walking trajectories. First, we denoise the relative distancesdijkk=1,…,n by conservatively applying a low-pass filter. The noise from the sensors is suppressed. Then, we resample the signals to ensure that there is a sufficient amount of samples between each local maximum and local minimum of the signals. Since the computational cost increases as the temporal resolution gets higher, we downsample the signal if there are too many samples in each period. A typical choice is to make sure there are 10 to 20 samples in each period. Linear interpolation is used to resample the signals.


### 3.2. Standing Status Detection and the Pattern of Walking

During walking, there are four types of status, as shown in Figure2. During a walking step, the supporting foot is first completely in touch with the ground, and the beginning of this status is denoted by tst. The supporting foot remains on the ground until the moving foot is ready to land. Then, the heel of the supporting foot starts to move up at time thu, while the ball of the foot remains in touch with the ground. When the ankle rotates to approach its joint limit, the forefoot leaves the ground at time tfu and makes the entire foot off the ground. The supporting foot switches to the moving foot and swings to make a step. Before the moving foot switches back to the supporting foot, its heel lands first at time thd, and later, the forefoot lands to make the foot completely on the ground again, which forms a cycle of walking step. Pressure sensors installed under the heel and the ball of the foot can be used to detect the landing status. If the measured pressure is less than the threshold, we regard that the heel or the ball of the foot is leaving the ground.Figure 2
An illustration of the standing status during a walking step, where the nodes turn to be grey if they leave the ground.By looking into the walking motion, we find that there are two typical patterns of the landing status, as shown in Figure3. The first pattern is common when the subject is walking forward. In this pattern, before the moving foot B is landing its heel on the ground at time thdB, the supporting foot A is already lifting its heel up at time thuA, i.e., thuA<thdB. We also find that tfuA≈tstB. During this short gap, the subject is only supported by the forefoot of A. The subject is not as stably supported as the status that one foot is completely on the ground. It is the momentum that makes this short period smoothly transit to the next stable status, which essentially saves the effort and makes the walking motion more energy-efficient.Figure 3
Two typical walking patterns of the standing status and their time slots corresponding to subproblems I and II.
(a)(b)The second pattern is usually observed when the walking subject is walking slowly or making a turn. As shown in the lower row of Figure3, in this pattern, the heel of the supporting foot A is not moving until the moving foot B is completely landing on the ground, i.e., thuA>tstB. The walking motion which follows this pattern always keeps a foot completely on the ground, which is more stable but less energy-efficient than the first walking pattern. It usually happens when a more stable control is required to prevent falling down in the turn.While we observe the walking patterns from mocap data, we also point out that complex walking patterns have been studied in biomechanics [24, 25]. The difference is that the walking pattern observed here is for a computational method to recover the walking motion.


### 3.3. Foot Trajectory Reconstruction

Having observed the two walking patterns, we are now ready to design our algorithms to reconstruct the foot trajectory in this section. We decompose the two basic walking patterns into substeps and summarize the foot trajectory reconstruction into the following two subproblems, which will be written as subproblem I and subproblem II in the following. We will establish the 3D walking trajectories in detail.The first subproblem I is to solve for the trajectory of the moving foot if the supporting foot is completely on the ground. It fits to the time slottstAthuA and tstBthuB in the first pattern. The second pattern can be decomposed into time slots tstAtstB and tstBtst2B, which cover all the periods of the second pattern. In all the above time slots, either the foot A or the foot B is completely on the ground. Here, we make the first assumption of our method: there is no slippage of the supporting foot during walking. This is not a strong assumption since the fiction is generally large enough to make the supporting leg stable during walking, unless in some special circumstances, such as walking on the ice.


#### 3.3.1. Subproblem I

Our key idea to solve subproblem I is to regard the standing foot as a base station. By fixing the location of the standing foot, we solve the trajectory of the lifting foot by using the distance measurements and orientation measurements. In the following, we will write the time slot as [0, m] for simplicity. Without loss of generality, it is assumed that the supporting foot is the left foot. The markers on the left foot have known positions, i.e.,pik=pi0, k ∈ [0, m]. The unknowns are the position of the right foot, which are represented by qik in our system. They can be solved from the following optimization problem:(1)q1k,q2k,q3k=argminq1,q2,q3Edq1,q2,q3=argminq1,q2,q3∑i,jqj−pi02−dijk22,s.t.qi−qj=qij,i,j∈1,2,3,i≠j, where dijk and qij are introduced in the previous section and illustrated in Figure 1. Although it is sufficient to determine the position of one point if its distance to three noncollinear points is given, we formulate the relative distance measurements as an energy term due to the presence of noises.As shown in Figure4, optimization problem (1) may have two global optimal, up to a mirror transform with respect to the plane defined by the three points pi0, i = {1, 2, 3}. To prevent this ambiguity, we add a momentum term Emq1,q2,q3 to equation (1):(2)Emq1,q2,q3=∑iqi−qik−1+vqik−12, where vqik−1=qik−1−qik−2 estimates the velocity of qi at time k and qik−1+vqik−1 provides a rough guess of qik.Figure 4
There are two possible positions fitting the measured distances. The two solutions are symmetric about the plane defined by the markers on the supporting foot.The detected heading direction is another useful information to correct the reconstructed trajectory. As the heading direction is defined to be the vectorq2−q1, we model the orientation term as(3)Eoq1,q2,q3=∑ihr−q2−q12.The introduced redundancy is helpful to further reduce the error.After adding the momentum term and the orientation term, the subproblem is finally formulated as(4)q1k,q2k,q3k=argminq1,q2,q3Edq1,q2,q3+wmEdq1,q2,q3+woEoq1,q2,q3,s.t.qi−qj=qij,i,j∈1,2,3,i≠j.


#### 3.3.2. Subproblem II

The second subproblem deals with the remaining time slots in the first walking pattern, i.e., from the time when the heel of the supporting foot leaves the ground to the time when the moving foot completely lands,thuAtstB and thuBtst2A. In these time slots, both feet are moving, and no foot is statically located on the ground. In this case, we do not have a base station fixed on the ground. We have tested to regard the location of all the markers in these time slots as unknown variables and try to estimate them from the distance and orientation measurements with the assumption of smoothness trajectory. However, the error easily accumulates and makes the recovered trajectories to quickly drift. We instead propose a two-step method and try to reuse the solver for subproblem I here. We regard the lifting foot as a moving base station and try to estimate its trajectory as the first step. As the second step, we take the estimated trajectory of the lifting foot as the boundary condition and solve for the trajectory of the landing foot from equation (4).By observing that the lifting foot has a relatively simple pattern, as shown in Figure5, we propose to estimate its trajectory and set it as a moving base station. From Figure 5, we find that the trajectory of the lifting foot is related to its orientation. Because the orientation of the lifting foot can be sensed from the inclinometers attached on it, we will use the orientation to estimate the trajectory of the lifting foot. Note that we take the MARG orientation from IMU [26], and the error of the sensed orientation does not significantly accumulate in the short time slot.Figure 5
Typical trajectories of markers on the (a) lifting foot and (b) landing foot. We observe a strong correlation between the orientation and the translation of the lifting foot.
(a)(b)Taking the left foot as the lifting foot as an example and having [0, m] denote the time slot for simplicity, our goal in the first step is to estimatep1k,p2k,p3k, k ∈ [0, m], from the sensed heading orientation hlk and up direction ulk of the left foot. Our assumption is that the trajectory relates to the sensed orientation with a simple model. Because the orientation has three degrees of freedom, we parameterize the orientation with an axis-angle representation, i.e., we convert rotation matrix hlk,ulk,hlk,×ulk into a vector alk, with its direction as the axis of the rotation and its magnitude as the rotation angle. We test a linear model between the orientation of the lifting foot alk and the trajectory of the markers pik:(5)pik=Wialk+bi, where the constant matrix Wi and vector bi encode the coefficients in the linear relationship. In order to find the coefficients, we design a training session. We sample walking session II with trajectories of the lifting foot and its orientation from walking motions from publicly available motion capture data, denoted by p˜ij and a˜lj, j = 1, 2, ..., n. Then, we solve the following least square problem and obtain the coefficients:(6)Wi,bi=argmin∑j=1nWia˜lj+bi−p˜ij2.We feed least square fitting with samples collected from different walking mocap data and precompute the coefficientsWi and bi before the trajectory estimation. After we get the coefficients, the trajectory of the lifting foot is computed by equation (5).After we obtain the trajectory of the lifting footpik, k ∈ [0, m], from each frame, the location of the markers on the standing foot pi0 in equation (1) is replaced by pik. We then solve equation (4) again to recover the trajectory of the landing foot.


#### 3.3.3. Wrap Up the Solver

Combining the walking pattern detection and the above two subproblems, our foot trajectory reconstruction method is summarized in Algorithm1. The two subproblems are all nonlinear least square problems, and we use the Gauss–Newton algorithm to solve the subproblem by converting the hard constraints into soft constraints with large weights. In our experiments, the weights wm and wo in (4) are set as 0.2 and 10 by default. Subproblem I is solved step by step. The position of each marker at the k − 1th frame is set as the initial guess for solving the marker positions at the kth frame. In subproblem II, we first estimate the position of the lifting foot and then solve for the landing foot trajectory. Since problem (4) is nonlinear, we set the initial guess by linearly extrapolating the trajectory of each marker. We simply threshold the pressure under the foot to determine the walking pattern. During the process, we alternatively switch the supporting foot and solve for the trajectory of the moving foot. With our initialization, the algorithm terminates with less than ten iterations for most cases. After the foot trajectory is reconstructed, we simply average the markers’ positions to obtain the position of the center of mass (CoM) as the walking trajectory if the information of foot orientation is not required. Note that the geometry of the reconstructed trajectory is dependent on the coordinate system, which is defined to fit the up direction and forward direction at the first frame here. It can be registered to other maps if the coordinate system is given.Algorithm 1: Foot Trajectory Reconstruction and The peusedo-code of our algorithm.
(1)
Initialization(2)
u←0,1,0,f0,0,1,s←u×f(3)
p10←0,0,0,,p200,0,p12,(4)
p30←0,a,b,s.t.dp10,p30=p13dp20,p30=p23(5)
q10←p12,0,0,q20←p12,0,p12,q30←p12,a,b(6)
end(7)
PrecomputeWi,bii=1,2,3 for lifting foot trajectory estimation by solving (6)(8)
Detect Standing StatuststA,thuA,tstB,thuB,… (Section 3.2)(9)
for each framek do(10)
ifk in tstA,minthuA,tstBortstB,minthuB,tstA   //subproblem I(11)
p1k,p2k,p3k,q1k,q2k,q3k←p1k−1,p2k−1,p3k−1,q1k−1,q2k−1,q3k−1(12)
Solve (4) for q1k,q2k,q3k, if k in tstA,minthuA,tstB or Solve (4) for p1k,p2k,p3k by switching pi and qi, if k in tstB,minthuB,tstA(13)
k←k+1(14)
else   //subproblemII(15)
ifk in tstA,minthuA,tstB   //the left foot is lifting(16)
Estimatep1k,p2k,p3k from equation (5)(17)
Setp10,p20,p30←p1k,p2k,p3k(18)
Solve (4) forq1k,q2k,q3k(19)
else             //the right foot is lifting(20)
Estimateq1k,q2k,q3k from equation (5) by switching pi and qi(21)
Setq10,q20,q30←q1k,q2k,q3k(22)
Solve (4) for p1k,p2k,p3k by switching pi and qi(23)
end if(24)
k←k+1(25)
end if(26)
end for2D cases: if we only need to sense walking on a 2D plane, the proposed model can be simplified. In this case, we do not need to use nodesp3 and q3 and do not measure the distance between any node to them. We parameterize the unknown positions of the nodes as 2D coordinates, and only d11, d12, d21, and d22 are in the data term Ed. In 2D cases, we do not need the regression for the 3D trajectory of the lifting foot. We only compute the regression of the 2D trajectory in the case. Under the above modifications, our method can be adapted to solve the problem in 2D cases.


## 3.1. Measurement Design

### 3.1.1. Measurements

The local measurements what we use are shown in Figure1. We locate three markers on each foot. Taking the left foot as an example, one marker p¯1 is at the heel, one marker p¯2 is at the big toe mound, and the other marker p¯3 is at the inner ankle. Corresponding markers on the right foot are denoted by q¯1, q¯2, and q¯3. The Euclidean distance between each pair of the markers is measured when the subject is walking. In the following, dijk=dpik,qjk, i, j ∈ {1, 2, 3}, denotes the measured distance between the marker pi and qi at the kth frame. During walking, the distances between the three markers on the same foot are constant, which will be presented by pij=dp¯ip¯j and qij=dq¯iq¯j; pij and qij are measured once before walking using rulers. These distance measurements are the key components to reconstruct the walking trajectories. The heading orientations of the two feet hl and hr are also measured from inertia sensors during walking. In addition, we also measure the pressure by attaching multiple force-sensing resistors under the heel and toe mound regions to indicate the standing status. The overview of our information fusion strategy is shown in Figure 1(b). In the next section, we will elaborate on the details of our solver.Figure 1
(a) The designed measurements. The markersp¯i and q¯j and their relative distances dij (three of them are illustrated in this figure) on two feet together with the heading directions hlandhr are designed to be the local measurements in our method and the pressures under the heel f1, g1 and toe mound f2, g2. (b) The overview of the information fusion pipeline.
(a)(b)


### 3.1.2. Design Consideration

We design the markers at the locations in which they are visible so that it is possible to acquire their relative distances. We propose to use three markers per foot if we are interested in getting the three-dimensional (3D) walking trajectory. We can remove the markersp¯3 and q¯3 if we only need to obtain the two-dimensional (2D) walking path. In the following, we will establish our method for the 3D cases first and then briefly talk about the 2D cases. It seems reasonable to set only one marker on each foot and reconstruct the trajectories by adding the orientation information from a compass. However, in this case, anthropometric data will be required, and the error of the measured anthropometry may lead to observable systematic errors.


### 3.1.3. Preprocessing

After the local measurements are obtained, we preprocess the signals before using them to recover the walking trajectories. First, we denoise the relative distancesdijkk=1,…,n by conservatively applying a low-pass filter. The noise from the sensors is suppressed. Then, we resample the signals to ensure that there is a sufficient amount of samples between each local maximum and local minimum of the signals. Since the computational cost increases as the temporal resolution gets higher, we downsample the signal if there are too many samples in each period. A typical choice is to make sure there are 10 to 20 samples in each period. Linear interpolation is used to resample the signals.


## 3.1.1. Measurements

The local measurements what we use are shown in Figure1. We locate three markers on each foot. Taking the left foot as an example, one marker p¯1 is at the heel, one marker p¯2 is at the big toe mound, and the other marker p¯3 is at the inner ankle. Corresponding markers on the right foot are denoted by q¯1, q¯2, and q¯3. The Euclidean distance between each pair of the markers is measured when the subject is walking. In the following, dijk=dpik,qjk, i, j ∈ {1, 2, 3}, denotes the measured distance between the marker pi and qi at the kth frame. During walking, the distances between the three markers on the same foot are constant, which will be presented by pij=dp¯ip¯j and qij=dq¯iq¯j; pij and qij are measured once before walking using rulers. These distance measurements are the key components to reconstruct the walking trajectories. The heading orientations of the two feet hl and hr are also measured from inertia sensors during walking. In addition, we also measure the pressure by attaching multiple force-sensing resistors under the heel and toe mound regions to indicate the standing status. The overview of our information fusion strategy is shown in Figure 1(b). In the next section, we will elaborate on the details of our solver.Figure 1
(a) The designed measurements. The markersp¯i and q¯j and their relative distances dij (three of them are illustrated in this figure) on two feet together with the heading directions hlandhr are designed to be the local measurements in our method and the pressures under the heel f1, g1 and toe mound f2, g2. (b) The overview of the information fusion pipeline.
(a)(b)


## 3.1.2. Design Consideration

We design the markers at the locations in which they are visible so that it is possible to acquire their relative distances. We propose to use three markers per foot if we are interested in getting the three-dimensional (3D) walking trajectory. We can remove the markersp¯3 and q¯3 if we only need to obtain the two-dimensional (2D) walking path. In the following, we will establish our method for the 3D cases first and then briefly talk about the 2D cases. It seems reasonable to set only one marker on each foot and reconstruct the trajectories by adding the orientation information from a compass. However, in this case, anthropometric data will be required, and the error of the measured anthropometry may lead to observable systematic errors.


## 3.1.3. Preprocessing

After the local measurements are obtained, we preprocess the signals before using them to recover the walking trajectories. First, we denoise the relative distancesdijkk=1,…,n by conservatively applying a low-pass filter. The noise from the sensors is suppressed. Then, we resample the signals to ensure that there is a sufficient amount of samples between each local maximum and local minimum of the signals. Since the computational cost increases as the temporal resolution gets higher, we downsample the signal if there are too many samples in each period. A typical choice is to make sure there are 10 to 20 samples in each period. Linear interpolation is used to resample the signals.


## 3.2. Standing Status Detection and the Pattern of Walking

During walking, there are four types of status, as shown in Figure2. During a walking step, the supporting foot is first completely in touch with the ground, and the beginning of this status is denoted by tst. The supporting foot remains on the ground until the moving foot is ready to land. Then, the heel of the supporting foot starts to move up at time thu, while the ball of the foot remains in touch with the ground. When the ankle rotates to approach its joint limit, the forefoot leaves the ground at time tfu and makes the entire foot off the ground. The supporting foot switches to the moving foot and swings to make a step. Before the moving foot switches back to the supporting foot, its heel lands first at time thd, and later, the forefoot lands to make the foot completely on the ground again, which forms a cycle of walking step. Pressure sensors installed under the heel and the ball of the foot can be used to detect the landing status. If the measured pressure is less than the threshold, we regard that the heel or the ball of the foot is leaving the ground.Figure 2
An illustration of the standing status during a walking step, where the nodes turn to be grey if they leave the ground.By looking into the walking motion, we find that there are two typical patterns of the landing status, as shown in Figure3. The first pattern is common when the subject is walking forward. In this pattern, before the moving foot B is landing its heel on the ground at time thdB, the supporting foot A is already lifting its heel up at time thuA, i.e., thuA<thdB. We also find that tfuA≈tstB. During this short gap, the subject is only supported by the forefoot of A. The subject is not as stably supported as the status that one foot is completely on the ground. It is the momentum that makes this short period smoothly transit to the next stable status, which essentially saves the effort and makes the walking motion more energy-efficient.Figure 3
Two typical walking patterns of the standing status and their time slots corresponding to subproblems I and II.
(a)(b)The second pattern is usually observed when the walking subject is walking slowly or making a turn. As shown in the lower row of Figure3, in this pattern, the heel of the supporting foot A is not moving until the moving foot B is completely landing on the ground, i.e., thuA>tstB. The walking motion which follows this pattern always keeps a foot completely on the ground, which is more stable but less energy-efficient than the first walking pattern. It usually happens when a more stable control is required to prevent falling down in the turn.While we observe the walking patterns from mocap data, we also point out that complex walking patterns have been studied in biomechanics [24, 25]. The difference is that the walking pattern observed here is for a computational method to recover the walking motion.


## 3.3. Foot Trajectory Reconstruction

Having observed the two walking patterns, we are now ready to design our algorithms to reconstruct the foot trajectory in this section. We decompose the two basic walking patterns into substeps and summarize the foot trajectory reconstruction into the following two subproblems, which will be written as subproblem I and subproblem II in the following. We will establish the 3D walking trajectories in detail.The first subproblem I is to solve for the trajectory of the moving foot if the supporting foot is completely on the ground. It fits to the time slottstAthuA and tstBthuB in the first pattern. The second pattern can be decomposed into time slots tstAtstB and tstBtst2B, which cover all the periods of the second pattern. In all the above time slots, either the foot A or the foot B is completely on the ground. Here, we make the first assumption of our method: there is no slippage of the supporting foot during walking. This is not a strong assumption since the fiction is generally large enough to make the supporting leg stable during walking, unless in some special circumstances, such as walking on the ice.


### 3.3.1. Subproblem I

Our key idea to solve subproblem I is to regard the standing foot as a base station. By fixing the location of the standing foot, we solve the trajectory of the lifting foot by using the distance measurements and orientation measurements. In the following, we will write the time slot as [0, m] for simplicity. Without loss of generality, it is assumed that the supporting foot is the left foot. The markers on the left foot have known positions, i.e.,pik=pi0, k ∈ [0, m]. The unknowns are the position of the right foot, which are represented by qik in our system. They can be solved from the following optimization problem:(1)q1k,q2k,q3k=argminq1,q2,q3Edq1,q2,q3=argminq1,q2,q3∑i,jqj−pi02−dijk22,s.t.qi−qj=qij,i,j∈1,2,3,i≠j, where dijk and qij are introduced in the previous section and illustrated in Figure 1. Although it is sufficient to determine the position of one point if its distance to three noncollinear points is given, we formulate the relative distance measurements as an energy term due to the presence of noises.As shown in Figure4, optimization problem (1) may have two global optimal, up to a mirror transform with respect to the plane defined by the three points pi0, i = {1, 2, 3}. To prevent this ambiguity, we add a momentum term Emq1,q2,q3 to equation (1):(2)Emq1,q2,q3=∑iqi−qik−1+vqik−12, where vqik−1=qik−1−qik−2 estimates the velocity of qi at time k and qik−1+vqik−1 provides a rough guess of qik.Figure 4
There are two possible positions fitting the measured distances. The two solutions are symmetric about the plane defined by the markers on the supporting foot.The detected heading direction is another useful information to correct the reconstructed trajectory. As the heading direction is defined to be the vectorq2−q1, we model the orientation term as(3)Eoq1,q2,q3=∑ihr−q2−q12.The introduced redundancy is helpful to further reduce the error.After adding the momentum term and the orientation term, the subproblem is finally formulated as(4)q1k,q2k,q3k=argminq1,q2,q3Edq1,q2,q3+wmEdq1,q2,q3+woEoq1,q2,q3,s.t.qi−qj=qij,i,j∈1,2,3,i≠j.


### 3.3.2. Subproblem II

The second subproblem deals with the remaining time slots in the first walking pattern, i.e., from the time when the heel of the supporting foot leaves the ground to the time when the moving foot completely lands,thuAtstB and thuBtst2A. In these time slots, both feet are moving, and no foot is statically located on the ground. In this case, we do not have a base station fixed on the ground. We have tested to regard the location of all the markers in these time slots as unknown variables and try to estimate them from the distance and orientation measurements with the assumption of smoothness trajectory. However, the error easily accumulates and makes the recovered trajectories to quickly drift. We instead propose a two-step method and try to reuse the solver for subproblem I here. We regard the lifting foot as a moving base station and try to estimate its trajectory as the first step. As the second step, we take the estimated trajectory of the lifting foot as the boundary condition and solve for the trajectory of the landing foot from equation (4).By observing that the lifting foot has a relatively simple pattern, as shown in Figure5, we propose to estimate its trajectory and set it as a moving base station. From Figure 5, we find that the trajectory of the lifting foot is related to its orientation. Because the orientation of the lifting foot can be sensed from the inclinometers attached on it, we will use the orientation to estimate the trajectory of the lifting foot. Note that we take the MARG orientation from IMU [26], and the error of the sensed orientation does not significantly accumulate in the short time slot.Figure 5
Typical trajectories of markers on the (a) lifting foot and (b) landing foot. We observe a strong correlation between the orientation and the translation of the lifting foot.
(a)(b)Taking the left foot as the lifting foot as an example and having [0, m] denote the time slot for simplicity, our goal in the first step is to estimatep1k,p2k,p3k, k ∈ [0, m], from the sensed heading orientation hlk and up direction ulk of the left foot. Our assumption is that the trajectory relates to the sensed orientation with a simple model. Because the orientation has three degrees of freedom, we parameterize the orientation with an axis-angle representation, i.e., we convert rotation matrix hlk,ulk,hlk,×ulk into a vector alk, with its direction as the axis of the rotation and its magnitude as the rotation angle. We test a linear model between the orientation of the lifting foot alk and the trajectory of the markers pik:(5)pik=Wialk+bi, where the constant matrix Wi and vector bi encode the coefficients in the linear relationship. In order to find the coefficients, we design a training session. We sample walking session II with trajectories of the lifting foot and its orientation from walking motions from publicly available motion capture data, denoted by p˜ij and a˜lj, j = 1, 2, ..., n. Then, we solve the following least square problem and obtain the coefficients:(6)Wi,bi=argmin∑j=1nWia˜lj+bi−p˜ij2.We feed least square fitting with samples collected from different walking mocap data and precompute the coefficientsWi and bi before the trajectory estimation. After we get the coefficients, the trajectory of the lifting foot is computed by equation (5).After we obtain the trajectory of the lifting footpik, k ∈ [0, m], from each frame, the location of the markers on the standing foot pi0 in equation (1) is replaced by pik. We then solve equation (4) again to recover the trajectory of the landing foot.


### 3.3.3. Wrap Up the Solver

Combining the walking pattern detection and the above two subproblems, our foot trajectory reconstruction method is summarized in Algorithm1. The two subproblems are all nonlinear least square problems, and we use the Gauss–Newton algorithm to solve the subproblem by converting the hard constraints into soft constraints with large weights. In our experiments, the weights wm and wo in (4) are set as 0.2 and 10 by default. Subproblem I is solved step by step. The position of each marker at the k − 1th frame is set as the initial guess for solving the marker positions at the kth frame. In subproblem II, we first estimate the position of the lifting foot and then solve for the landing foot trajectory. Since problem (4) is nonlinear, we set the initial guess by linearly extrapolating the trajectory of each marker. We simply threshold the pressure under the foot to determine the walking pattern. During the process, we alternatively switch the supporting foot and solve for the trajectory of the moving foot. With our initialization, the algorithm terminates with less than ten iterations for most cases. After the foot trajectory is reconstructed, we simply average the markers’ positions to obtain the position of the center of mass (CoM) as the walking trajectory if the information of foot orientation is not required. Note that the geometry of the reconstructed trajectory is dependent on the coordinate system, which is defined to fit the up direction and forward direction at the first frame here. It can be registered to other maps if the coordinate system is given.Algorithm 1: Foot Trajectory Reconstruction and The peusedo-code of our algorithm.
(1)
Initialization(2)
u←0,1,0,f0,0,1,s←u×f(3)
p10←0,0,0,,p200,0,p12,(4)
p30←0,a,b,s.t.dp10,p30=p13dp20,p30=p23(5)
q10←p12,0,0,q20←p12,0,p12,q30←p12,a,b(6)
end(7)
PrecomputeWi,bii=1,2,3 for lifting foot trajectory estimation by solving (6)(8)
Detect Standing StatuststA,thuA,tstB,thuB,… (Section 3.2)(9)
for each framek do(10)
ifk in tstA,minthuA,tstBortstB,minthuB,tstA   //subproblem I(11)
p1k,p2k,p3k,q1k,q2k,q3k←p1k−1,p2k−1,p3k−1,q1k−1,q2k−1,q3k−1(12)
Solve (4) for q1k,q2k,q3k, if k in tstA,minthuA,tstB or Solve (4) for p1k,p2k,p3k by switching pi and qi, if k in tstB,minthuB,tstA(13)
k←k+1(14)
else   //subproblemII(15)
ifk in tstA,minthuA,tstB   //the left foot is lifting(16)
Estimatep1k,p2k,p3k from equation (5)(17)
Setp10,p20,p30←p1k,p2k,p3k(18)
Solve (4) forq1k,q2k,q3k(19)
else             //the right foot is lifting(20)
Estimateq1k,q2k,q3k from equation (5) by switching pi and qi(21)
Setq10,q20,q30←q1k,q2k,q3k(22)
Solve (4) for p1k,p2k,p3k by switching pi and qi(23)
end if(24)
k←k+1(25)
end if(26)
end for2D cases: if we only need to sense walking on a 2D plane, the proposed model can be simplified. In this case, we do not need to use nodesp3 and q3 and do not measure the distance between any node to them. We parameterize the unknown positions of the nodes as 2D coordinates, and only d11, d12, d21, and d22 are in the data term Ed. In 2D cases, we do not need the regression for the 3D trajectory of the lifting foot. We only compute the regression of the 2D trajectory in the case. Under the above modifications, our method can be adapted to solve the problem in 2D cases.


## 3.3.1. Subproblem I

Our key idea to solve subproblem I is to regard the standing foot as a base station. By fixing the location of the standing foot, we solve the trajectory of the lifting foot by using the distance measurements and orientation measurements. In the following, we will write the time slot as [0, m] for simplicity. Without loss of generality, it is assumed that the supporting foot is the left foot. The markers on the left foot have known positions, i.e.,pik=pi0, k ∈ [0, m]. The unknowns are the position of the right foot, which are represented by qik in our system. They can be solved from the following optimization problem:(1)q1k,q2k,q3k=argminq1,q2,q3Edq1,q2,q3=argminq1,q2,q3∑i,jqj−pi02−dijk22,s.t.qi−qj=qij,i,j∈1,2,3,i≠j, where dijk and qij are introduced in the previous section and illustrated in Figure 1. Although it is sufficient to determine the position of one point if its distance to three noncollinear points is given, we formulate the relative distance measurements as an energy term due to the presence of noises.As shown in Figure4, optimization problem (1) may have two global optimal, up to a mirror transform with respect to the plane defined by the three points pi0, i = {1, 2, 3}. To prevent this ambiguity, we add a momentum term Emq1,q2,q3 to equation (1):(2)Emq1,q2,q3=∑iqi−qik−1+vqik−12, where vqik−1=qik−1−qik−2 estimates the velocity of qi at time k and qik−1+vqik−1 provides a rough guess of qik.Figure 4
There are two possible positions fitting the measured distances. The two solutions are symmetric about the plane defined by the markers on the supporting foot.The detected heading direction is another useful information to correct the reconstructed trajectory. As the heading direction is defined to be the vectorq2−q1, we model the orientation term as(3)Eoq1,q2,q3=∑ihr−q2−q12.The introduced redundancy is helpful to further reduce the error.After adding the momentum term and the orientation term, the subproblem is finally formulated as(4)q1k,q2k,q3k=argminq1,q2,q3Edq1,q2,q3+wmEdq1,q2,q3+woEoq1,q2,q3,s.t.qi−qj=qij,i,j∈1,2,3,i≠j.


## 3.3.2. Subproblem II

The second subproblem deals with the remaining time slots in the first walking pattern, i.e., from the time when the heel of the supporting foot leaves the ground to the time when the moving foot completely lands,thuAtstB and thuBtst2A. In these time slots, both feet are moving, and no foot is statically located on the ground. In this case, we do not have a base station fixed on the ground. We have tested to regard the location of all the markers in these time slots as unknown variables and try to estimate them from the distance and orientation measurements with the assumption of smoothness trajectory. However, the error easily accumulates and makes the recovered trajectories to quickly drift. We instead propose a two-step method and try to reuse the solver for subproblem I here. We regard the lifting foot as a moving base station and try to estimate its trajectory as the first step. As the second step, we take the estimated trajectory of the lifting foot as the boundary condition and solve for the trajectory of the landing foot from equation (4).By observing that the lifting foot has a relatively simple pattern, as shown in Figure5, we propose to estimate its trajectory and set it as a moving base station. From Figure 5, we find that the trajectory of the lifting foot is related to its orientation. Because the orientation of the lifting foot can be sensed from the inclinometers attached on it, we will use the orientation to estimate the trajectory of the lifting foot. Note that we take the MARG orientation from IMU [26], and the error of the sensed orientation does not significantly accumulate in the short time slot.Figure 5
Typical trajectories of markers on the (a) lifting foot and (b) landing foot. We observe a strong correlation between the orientation and the translation of the lifting foot.
(a)(b)Taking the left foot as the lifting foot as an example and having [0, m] denote the time slot for simplicity, our goal in the first step is to estimatep1k,p2k,p3k, k ∈ [0, m], from the sensed heading orientation hlk and up direction ulk of the left foot. Our assumption is that the trajectory relates to the sensed orientation with a simple model. Because the orientation has three degrees of freedom, we parameterize the orientation with an axis-angle representation, i.e., we convert rotation matrix hlk,ulk,hlk,×ulk into a vector alk, with its direction as the axis of the rotation and its magnitude as the rotation angle. We test a linear model between the orientation of the lifting foot alk and the trajectory of the markers pik:(5)pik=Wialk+bi, where the constant matrix Wi and vector bi encode the coefficients in the linear relationship. In order to find the coefficients, we design a training session. We sample walking session II with trajectories of the lifting foot and its orientation from walking motions from publicly available motion capture data, denoted by p˜ij and a˜lj, j = 1, 2, ..., n. Then, we solve the following least square problem and obtain the coefficients:(6)Wi,bi=argmin∑j=1nWia˜lj+bi−p˜ij2.We feed least square fitting with samples collected from different walking mocap data and precompute the coefficientsWi and bi before the trajectory estimation. After we get the coefficients, the trajectory of the lifting foot is computed by equation (5).After we obtain the trajectory of the lifting footpik, k ∈ [0, m], from each frame, the location of the markers on the standing foot pi0 in equation (1) is replaced by pik. We then solve equation (4) again to recover the trajectory of the landing foot.


## 3.3.3. Wrap Up the Solver

Combining the walking pattern detection and the above two subproblems, our foot trajectory reconstruction method is summarized in Algorithm1. The two subproblems are all nonlinear least square problems, and we use the Gauss–Newton algorithm to solve the subproblem by converting the hard constraints into soft constraints with large weights. In our experiments, the weights wm and wo in (4) are set as 0.2 and 10 by default. Subproblem I is solved step by step. The position of each marker at the k − 1th frame is set as the initial guess for solving the marker positions at the kth frame. In subproblem II, we first estimate the position of the lifting foot and then solve for the landing foot trajectory. Since problem (4) is nonlinear, we set the initial guess by linearly extrapolating the trajectory of each marker. We simply threshold the pressure under the foot to determine the walking pattern. During the process, we alternatively switch the supporting foot and solve for the trajectory of the moving foot. With our initialization, the algorithm terminates with less than ten iterations for most cases. After the foot trajectory is reconstructed, we simply average the markers’ positions to obtain the position of the center of mass (CoM) as the walking trajectory if the information of foot orientation is not required. Note that the geometry of the reconstructed trajectory is dependent on the coordinate system, which is defined to fit the up direction and forward direction at the first frame here. It can be registered to other maps if the coordinate system is given.Algorithm 1: Foot Trajectory Reconstruction and The peusedo-code of our algorithm.
(1)
Initialization(2)
u←0,1,0,f0,0,1,s←u×f(3)
p10←0,0,0,,p200,0,p12,(4)
p30←0,a,b,s.t.dp10,p30=p13dp20,p30=p23(5)
q10←p12,0,0,q20←p12,0,p12,q30←p12,a,b(6)
end(7)
PrecomputeWi,bii=1,2,3 for lifting foot trajectory estimation by solving (6)(8)
Detect Standing StatuststA,thuA,tstB,thuB,… (Section 3.2)(9)
for each framek do(10)
ifk in tstA,minthuA,tstBortstB,minthuB,tstA   //subproblem I(11)
p1k,p2k,p3k,q1k,q2k,q3k←p1k−1,p2k−1,p3k−1,q1k−1,q2k−1,q3k−1(12)
Solve (4) for q1k,q2k,q3k, if k in tstA,minthuA,tstB or Solve (4) for p1k,p2k,p3k by switching pi and qi, if k in tstB,minthuB,tstA(13)
k←k+1(14)
else   //subproblemII(15)
ifk in tstA,minthuA,tstB   //the left foot is lifting(16)
Estimatep1k,p2k,p3k from equation (5)(17)
Setp10,p20,p30←p1k,p2k,p3k(18)
Solve (4) forq1k,q2k,q3k(19)
else             //the right foot is lifting(20)
Estimateq1k,q2k,q3k from equation (5) by switching pi and qi(21)
Setq10,q20,q30←q1k,q2k,q3k(22)
Solve (4) for p1k,p2k,p3k by switching pi and qi(23)
end if(24)
k←k+1(25)
end if(26)
end for2D cases: if we only need to sense walking on a 2D plane, the proposed model can be simplified. In this case, we do not need to use nodesp3 and q3 and do not measure the distance between any node to them. We parameterize the unknown positions of the nodes as 2D coordinates, and only d11, d12, d21, and d22 are in the data term Ed. In 2D cases, we do not need the regression for the 3D trajectory of the lifting foot. We only compute the regression of the 2D trajectory in the case. Under the above modifications, our method can be adapted to solve the problem in 2D cases.


## 4. Results and Discussion

In this section, we design experiments to validate our method in two phases. We primarily validate our algorithms by comparing with the motion data from mocap systems in the first experiment. In the second phase, we design a simplified system to check the prototype of our method in the outdoor space.


### 4.1. Experiment with Mocap Data

We use the walking motions from the CMU motion capture database. Since the mocap data are based on joint angles, we use forward kinematics to convert the sequence of joint angles into the trajectories of the predefined markers on feet. The trajectories extracted from mocap data are used as references to evaluate our method. We extracted the local measurements including the relative distance and foot orientation from the mocap data. Then, these measurements are sent to test our solvers. In order to better validate our method, we also perturb the local measurements to simulate the noises of sensor systems. In our experiment, the noises added on the measured distance and the orientation angles are 1 mm and 0.05°, respectively. This is in accordance with several typical sensors which will be discussed later. In this experiment, we run our algorithms on a single CPU thread with 1.6 GHz, and the recovered walking trajectories are interactively displayed. The trajectory can be solved less than 0.015 seconds per frame in solving subproblem I and 0.02 seconds per frame in solving subproblem II.We test the normal walking motions from two different subjects, as shown in Figure6. The walking trajectories are computed as the average of the trajectories of two feet. In our test, the recovered trajectories well fit the references. The maximum error is less than 0.18 m, and the rooted mean square error is less than 0.10 m in our test.Figure 6
(a) The recovered forward walking trajectories of the center of mass from our method (red) and optical motion capture data (black). (b) The recovered trajectories of the markers (solid lines) and the reference trajectories from the mocap system (dashed lines). The results shown in the upper row and the lower row are from two different subjects.
(a)(b)We then test our method with two walking motions with a right turn and 90-degree left turn, as shown in Figure7. The maximum error and average error are about 10 cm and 6.5 cm in these two examples. The precision of the recovered trajectories is comparable with the precision of ultra-wide band radio systems for indoor positioning applications.Figure 7
The recovered trajectories of (a) right and (b) left turning. The trajectories of the center of mass (CoM) and all the markers are shown in the upper and lower rows.
(a)(b)We verify our method with different levels of noises on the local measurements. We perturb the local measurements by adding white noise to the relative distances with the variance up to 2 mm. The orientation is also perturbed with a white noise whose variance is up to 0.2°. The recovered walking trajectories are shown in Figure8. In our test, as the levels of the noises increase, the rooted mean square error increases from 3.91 cm to 7.21 cm. We still do not lose tracking of the walking trajectories compared to the references. Note that the mocap data itself are not free of the noise, which makes the data not perfectly fit with our assumptions. For example, the supporting foot may oscillate on the ground or even penetrate with the ground. Even with those noises, our system works by fusing the local measurements and inertia data for recovering 3D walking trajectories.Figure 8
The recovered trajectories from the local measurements with different levels of noises. The corresponding rooted mean square errors are listed in the table.


### 4.2. Experiment with Outdoor Walk

We also try our system in a walking session in the outdoor environment. A user is invited to walk on the ground, and we mark the footprints on the ground as the groundtruth for the evaluation. In this experiment, the user is walking for a longer distance. As the walking distance is significantly larger than the height of the lifting foot, we use the 2D version of the proposed method here. We use the ECA30PL encoder to measure the distance between the feet. The user is not walking fast, and the module works when the string is tensioned. The ground is planar and has no obstacles. We also measure the footprints with a tape to obtain the relative distances and verify the measured distances from sensors are correct. The foot orientation is measured by the WT901C module.With the collected local measurements, we reconstructed the walking trajectory and compared them with the groundtruth. Because the user is walking slowly, the case that no foot is on the ground rarely happens, and we only solve the first subproblem in this experiment. As shown in Figure9, the reconstructed footprints well match with the groundtruth. We also plot the tracking error with respect to the walking distance. From the results, we find that the error slowly accumulates with the marching of the user. For a walk session up to 120 meters, the maximum error is less than 12 cm.Figure 9
Two experimental results (a, b) in the outdoor environment. In the upper row, the groundtruth and recovered footprints are shown in blue and red, respectively. The heel of the foot is represented as a dot. In the lower row, we plot the error of CoM w.r.t the walking distance.
(a)(b)


#### 4.2.1. Comments on Hardware Design

The designed local measurements are allowed to be passively captured. Although we focus on the computational method to solve for the trajectories in this work, we also report our experience of hardware choice from our preliminary design. For the relative distances between the nodes located on two feet, one design option is to equip ultrasonic sources and receivers on two feet. The measured distance is with the accuracy up to 2 mm. One problem with this design is that the ultrasonic sensors have a limited field of view and do not always report the distance when the receivers are out of the angle of the sources. An array of ultrasound sensors can be exploited to broaden the target angle. As shown in Figure10(a), a tape structure combined with a rotary encoder is another option to measure the relative distances. The module is hooked in-between two nodes, allowing changing directions of the string during walking. ECA30PL and WXY80 modules report a precision higher than 0.5 mm. We use them in our prototype for the experiments with outdoor walk data. However, in order to guarantee that the measurement system is working normally, no obstacle should be allowed in-between the sensors, and the strings should be tensioned. It limits the usage of the prototype to some extents. The foot orientation is measured by the WT901C module, whose angle precision is 0.05. In addition to the above measurements, we use FSR402 sensors to detect the pressure under the foot. The pressure data are used to indicate the contact status between the foot and the ground. These sensors are all with a small size and can be worn on the feet. The limitation of this design is that the tape structure may disturb the gait motion, while at the same time, it is acceptable for the applications such as rehabilitation since it can also be extended to a cable-driven exoskeleton for rehabilitation. We also make a preliminary design to measure the relative distances without contact. As shown in Figure 10(b), two binocular cameras are installed on one foot, and markers are decorated on the other foot. By reading the distance between markers and cameras, we obtain the relative distances between the feet. Although the cameras are not strictly placed as the marker shown in Figure 1, our method still applies in the 2D case because we do not assume perfect locations for the markers. As long as the markers at different feet can see each other, we can solve the trajectory. In addition, we are also working on the preliminary design of hardware for a miniature design.Figure 10
Two preliminary designs of hardware to obtain the local measurements used in our experiment. (a) A tape structure with an encoder measures the relative distances between feet. (b) Binocular cameras measure their distances to the markers on the feet.
(a)(b)


### 4.3. Limitations and Future Work

In this work, we propose a set of the local measurements and the algorithms to recover walking trajectories from them. The concept and the algorithm are verified with mocap data and outdoor walking data from a simplified prototype. Although the local measurements can be passively captured, we still need to work for a better hardware solution in integrating them as the commercially available sensors still have limits, e.g., their sizes are not small enough. A low-cost and miniature sensor to acquire the local measurements without disturbing the walking experience should be customized for our application.Our method works under the assumption that the supporting foot does not slip. Although slippage rarely appears in general walking motion, some occasional slippage will introduce systematic error to the reconstructed trajectories. Besides, it is challenging to reconstruct the foot trajectories for motions such as running or jumping because there are periods when the two feet are all off the ground. We focus on typical walking trajectories in this work. We will also study the running motion or the motion that is close to running as it may share similar features as walking.The other assumption we made is about the environment. Our assumption about the supporting foot may break if the subject is walking on an uneven terrain. The walking motion is also changing to crawling or even climbing if the terrain is complex, which is ultimately out of our scope. We are also interested in studying how to incorporate the terrain information for walking trajectory recovery.We could also incorporate more measurements from various sensors to further improve the results. For example, the acceleration measurements from inertial sensors are also easy to be passively captured. Though the system gets to be more complicated, its precision and stability can be further improved. For the chosen measurements, we are also planning to test our method with more real large-scale data. At last, the online computation for applications such as augmented reality remains to be developed.


## 4.1. Experiment with Mocap Data

We use the walking motions from the CMU motion capture database. Since the mocap data are based on joint angles, we use forward kinematics to convert the sequence of joint angles into the trajectories of the predefined markers on feet. The trajectories extracted from mocap data are used as references to evaluate our method. We extracted the local measurements including the relative distance and foot orientation from the mocap data. Then, these measurements are sent to test our solvers. In order to better validate our method, we also perturb the local measurements to simulate the noises of sensor systems. In our experiment, the noises added on the measured distance and the orientation angles are 1 mm and 0.05°, respectively. This is in accordance with several typical sensors which will be discussed later. In this experiment, we run our algorithms on a single CPU thread with 1.6 GHz, and the recovered walking trajectories are interactively displayed. The trajectory can be solved less than 0.015 seconds per frame in solving subproblem I and 0.02 seconds per frame in solving subproblem II.We test the normal walking motions from two different subjects, as shown in Figure6. The walking trajectories are computed as the average of the trajectories of two feet. In our test, the recovered trajectories well fit the references. The maximum error is less than 0.18 m, and the rooted mean square error is less than 0.10 m in our test.Figure 6
(a) The recovered forward walking trajectories of the center of mass from our method (red) and optical motion capture data (black). (b) The recovered trajectories of the markers (solid lines) and the reference trajectories from the mocap system (dashed lines). The results shown in the upper row and the lower row are from two different subjects.
(a)(b)We then test our method with two walking motions with a right turn and 90-degree left turn, as shown in Figure7. The maximum error and average error are about 10 cm and 6.5 cm in these two examples. The precision of the recovered trajectories is comparable with the precision of ultra-wide band radio systems for indoor positioning applications.Figure 7
The recovered trajectories of (a) right and (b) left turning. The trajectories of the center of mass (CoM) and all the markers are shown in the upper and lower rows.
(a)(b)We verify our method with different levels of noises on the local measurements. We perturb the local measurements by adding white noise to the relative distances with the variance up to 2 mm. The orientation is also perturbed with a white noise whose variance is up to 0.2°. The recovered walking trajectories are shown in Figure8. In our test, as the levels of the noises increase, the rooted mean square error increases from 3.91 cm to 7.21 cm. We still do not lose tracking of the walking trajectories compared to the references. Note that the mocap data itself are not free of the noise, which makes the data not perfectly fit with our assumptions. For example, the supporting foot may oscillate on the ground or even penetrate with the ground. Even with those noises, our system works by fusing the local measurements and inertia data for recovering 3D walking trajectories.Figure 8
The recovered trajectories from the local measurements with different levels of noises. The corresponding rooted mean square errors are listed in the table.


## 4.2. Experiment with Outdoor Walk

We also try our system in a walking session in the outdoor environment. A user is invited to walk on the ground, and we mark the footprints on the ground as the groundtruth for the evaluation. In this experiment, the user is walking for a longer distance. As the walking distance is significantly larger than the height of the lifting foot, we use the 2D version of the proposed method here. We use the ECA30PL encoder to measure the distance between the feet. The user is not walking fast, and the module works when the string is tensioned. The ground is planar and has no obstacles. We also measure the footprints with a tape to obtain the relative distances and verify the measured distances from sensors are correct. The foot orientation is measured by the WT901C module.With the collected local measurements, we reconstructed the walking trajectory and compared them with the groundtruth. Because the user is walking slowly, the case that no foot is on the ground rarely happens, and we only solve the first subproblem in this experiment. As shown in Figure9, the reconstructed footprints well match with the groundtruth. We also plot the tracking error with respect to the walking distance. From the results, we find that the error slowly accumulates with the marching of the user. For a walk session up to 120 meters, the maximum error is less than 12 cm.Figure 9
Two experimental results (a, b) in the outdoor environment. In the upper row, the groundtruth and recovered footprints are shown in blue and red, respectively. The heel of the foot is represented as a dot. In the lower row, we plot the error of CoM w.r.t the walking distance.
(a)(b)


### 4.2.1. Comments on Hardware Design

The designed local measurements are allowed to be passively captured. Although we focus on the computational method to solve for the trajectories in this work, we also report our experience of hardware choice from our preliminary design. For the relative distances between the nodes located on two feet, one design option is to equip ultrasonic sources and receivers on two feet. The measured distance is with the accuracy up to 2 mm. One problem with this design is that the ultrasonic sensors have a limited field of view and do not always report the distance when the receivers are out of the angle of the sources. An array of ultrasound sensors can be exploited to broaden the target angle. As shown in Figure10(a), a tape structure combined with a rotary encoder is another option to measure the relative distances. The module is hooked in-between two nodes, allowing changing directions of the string during walking. ECA30PL and WXY80 modules report a precision higher than 0.5 mm. We use them in our prototype for the experiments with outdoor walk data. However, in order to guarantee that the measurement system is working normally, no obstacle should be allowed in-between the sensors, and the strings should be tensioned. It limits the usage of the prototype to some extents. The foot orientation is measured by the WT901C module, whose angle precision is 0.05. In addition to the above measurements, we use FSR402 sensors to detect the pressure under the foot. The pressure data are used to indicate the contact status between the foot and the ground. These sensors are all with a small size and can be worn on the feet. The limitation of this design is that the tape structure may disturb the gait motion, while at the same time, it is acceptable for the applications such as rehabilitation since it can also be extended to a cable-driven exoskeleton for rehabilitation. We also make a preliminary design to measure the relative distances without contact. As shown in Figure 10(b), two binocular cameras are installed on one foot, and markers are decorated on the other foot. By reading the distance between markers and cameras, we obtain the relative distances between the feet. Although the cameras are not strictly placed as the marker shown in Figure 1, our method still applies in the 2D case because we do not assume perfect locations for the markers. As long as the markers at different feet can see each other, we can solve the trajectory. In addition, we are also working on the preliminary design of hardware for a miniature design.Figure 10
Two preliminary designs of hardware to obtain the local measurements used in our experiment. (a) A tape structure with an encoder measures the relative distances between feet. (b) Binocular cameras measure their distances to the markers on the feet.
(a)(b)


## 4.2.1. Comments on Hardware Design

The designed local measurements are allowed to be passively captured. Although we focus on the computational method to solve for the trajectories in this work, we also report our experience of hardware choice from our preliminary design. For the relative distances between the nodes located on two feet, one design option is to equip ultrasonic sources and receivers on two feet. The measured distance is with the accuracy up to 2 mm. One problem with this design is that the ultrasonic sensors have a limited field of view and do not always report the distance when the receivers are out of the angle of the sources. An array of ultrasound sensors can be exploited to broaden the target angle. As shown in Figure10(a), a tape structure combined with a rotary encoder is another option to measure the relative distances. The module is hooked in-between two nodes, allowing changing directions of the string during walking. ECA30PL and WXY80 modules report a precision higher than 0.5 mm. We use them in our prototype for the experiments with outdoor walk data. However, in order to guarantee that the measurement system is working normally, no obstacle should be allowed in-between the sensors, and the strings should be tensioned. It limits the usage of the prototype to some extents. The foot orientation is measured by the WT901C module, whose angle precision is 0.05. In addition to the above measurements, we use FSR402 sensors to detect the pressure under the foot. The pressure data are used to indicate the contact status between the foot and the ground. These sensors are all with a small size and can be worn on the feet. The limitation of this design is that the tape structure may disturb the gait motion, while at the same time, it is acceptable for the applications such as rehabilitation since it can also be extended to a cable-driven exoskeleton for rehabilitation. We also make a preliminary design to measure the relative distances without contact. As shown in Figure 10(b), two binocular cameras are installed on one foot, and markers are decorated on the other foot. By reading the distance between markers and cameras, we obtain the relative distances between the feet. Although the cameras are not strictly placed as the marker shown in Figure 1, our method still applies in the 2D case because we do not assume perfect locations for the markers. As long as the markers at different feet can see each other, we can solve the trajectory. In addition, we are also working on the preliminary design of hardware for a miniature design.Figure 10
Two preliminary designs of hardware to obtain the local measurements used in our experiment. (a) A tape structure with an encoder measures the relative distances between feet. (b) Binocular cameras measure their distances to the markers on the feet.
(a)(b)


## 4.3. Limitations and Future Work

In this work, we propose a set of the local measurements and the algorithms to recover walking trajectories from them. The concept and the algorithm are verified with mocap data and outdoor walking data from a simplified prototype. Although the local measurements can be passively captured, we still need to work for a better hardware solution in integrating them as the commercially available sensors still have limits, e.g., their sizes are not small enough. A low-cost and miniature sensor to acquire the local measurements without disturbing the walking experience should be customized for our application.Our method works under the assumption that the supporting foot does not slip. Although slippage rarely appears in general walking motion, some occasional slippage will introduce systematic error to the reconstructed trajectories. Besides, it is challenging to reconstruct the foot trajectories for motions such as running or jumping because there are periods when the two feet are all off the ground. We focus on typical walking trajectories in this work. We will also study the running motion or the motion that is close to running as it may share similar features as walking.The other assumption we made is about the environment. Our assumption about the supporting foot may break if the subject is walking on an uneven terrain. The walking motion is also changing to crawling or even climbing if the terrain is complex, which is ultimately out of our scope. We are also interested in studying how to incorporate the terrain information for walking trajectory recovery.We could also incorporate more measurements from various sensors to further improve the results. For example, the acceleration measurements from inertial sensors are also easy to be passively captured. Though the system gets to be more complicated, its precision and stability can be further improved. For the chosen measurements, we are also planning to test our method with more real large-scale data. At last, the online computation for applications such as augmented reality remains to be developed.


## 5. Conclusions

In this work, we present a set of new local distance measurements and demonstrate that they can be fused with inertia data to recover the walking trajectories. By looking into the pattern of walking motion, we design a small set of measurements and efficiently recover the foot trajectories by alternatively solving small-scale optimization problems. We believe that, with proper customization of the sensor system, our method can be applied to track pedestrians without installing infrastructures and without modeling the map. Localization is a key component connecting the real world and the virtual world. We expect more exciting applications of the proposed approach in the future.



---

*Source: 8825647-2020-11-06.xml*