to the different walking habits of different user,the relatively By getting the liftoff time and landing time by algorithm variety angle of moving direction is not exactly the angle of 1.we calculate the turning degree by Eg.(7).As the foot is foot direction.So we need to estimate the moving direction swing around the z-axis of gyroscope,we integral on g:from by the measured foot direction. liftoff time to landing time,getting the turning degree of foot Observation and Intuition.When the users are turning direction B:of the current step.And according to Theorem left/right,they always take the gravity direction as the axis.As 1,we have the turning degree of the moving direction for the depicted in Fig.1 (b),the direction of z-axis is opposite to the current step a;is equal to Bi.For a n-step turning process,we gravity direction.Thus we measure the g=,which is strongly then sum the ai up to get the turning degree a for one foot relative with the turning movement. by equation Then we use the mean of the two feet as the turning degree. d,foot direction d moving direction ai=Bi= gz(t)dt (7) T E.Reference Position Estimator By Step Length Estimator and Moving Direction Estimator, 0+ we can accurately estimate the user's moving trace.However, we still need to fix the moving trace into the global indoor map.To determine the location of the user by the moving trace and the indoor map,we have two basic intuitions.First,the user's moving trace is constrained by the topological structure of indoor environment,which is to say that the user can B、 not walking through the wall.Second,due to the reference Fig.12.Foot direction and moving direction position,such as elevators and stairs are fixed in the indoor For a specific user,we assume the angle between the foot map,we can accurately locate the user when he/she is doing the reference activities. direction,i.e.,df,and moving direction,i.e.,d,is invariable To locate the user,and further track the user in the indoor during his walking process.The assumption is reasonable in environment,we adopt Snake Game[18]strategy as depicted our scene.That is because for a person,the degree of toe-in and toe-out is almost constant in a long time.For the propose in Fig.14.As shown in (a),the user firstly taking an elevator, of getting the turning degree,which is ai.we rely on the then turning right after walking a short distance.At this time, following theorem, there are three possible location according to the moving trace and the position of elevator.When it comes to (b),the Theorem 1.Assume the angle p between the foot direction, user keep walking.Limited by the topological structure of i.e.,df,and moving direction,i.e.,dm is invariable.Then the indoor environment,the infeasible moving trace (2)and (3) degree of the turning,i.e.,oi,is equal to the relatively variety are filtered out,and the trace (1)is the actual moving trace of angle of moving direction,i.e.,Bi. the user. Proof.Without loss of generality,as shown in Fig.12,the user makes a turning with angle of degree a around the point O. Let the direction from O to the foot as do,the foot direction 明 as df,the moving direction as dm,the angle between the foot (1) (2)(3 (2, direction and moving direction are and +1,the variety 固画 固笛 angle of foot direction is Bi,and the variety angle of moving direction is yy.Since dw is orthogonal to do,then ai=. (a)Feasible traces. (b)Filter out infeasible traces As the vertically opposite angles is equal,we can have that Fig.14.Snake Game strategy. Y+p:+入=月：+Pi+1+入.According to the assumption, As we have got the class of the user's activity by Activity i=i+1,then y=Bi.So we have ai Bi. Classifier,if the user is ascending/descending an elevator or ascending/descending the stairs,we find the elevator or stairs' Moving Direction Estimation.FootStep-Tracker use low-pass location in the given indoor map as the reference position filter to extract the turning steps from the steps of walking After employing Snake Game strategy,we determine the actual straight ahead.Besides,for a single turning step,we find user's moving trace and location.Then we keep tracking the that the actual time which makes the foot turn is during user's location in time by the moving trace. phase (3),from the liftoff time to the landing time.That is because at phase(1)-(2).the heel lift up,preparing the forward V.PERFORMANCE EVALUATION movement.And at the phase (4)-(5),the foot is under the A.Implementation landing process.At those time,the feet has no rotation around Hardware:As shown in Fig.1 (a),our system consists the z-axis.To divide each phase,we need to extract the critical of a TEXAS-INSTRUMENTS CC2541 SensorTag[4].and a times,which is already given by Algorithm 1. SAMSUNG Galaxy S5 Android smart phone.to the different walking habits of different user, the relatively variety angle of moving direction is not exactly the angle of foot direction. So we need to estimate the moving direction by the measured foot direction. Observation and Intuition. When the users are turning left/right, they always take the gravity direction as the axis. As depicted in Fig.1 (b), the direction of z-axis is opposite to the gravity direction. Thus we measure the gz, which is strongly relative with the turning movement. φi+1 βi γ df dm φi O dm df αi df foot direction dm moving direction do do λ λ Fig. 12. Foot direction and moving direction For a specific user, we assume the angle between the foot direction, i.e., df , and moving direction, i.e., dw, is invariable during his walking process. The assumption is reasonable in our scene. That is because for a person, the degree of toe-in and toe-out is almost constant in a long time. For the propose of getting the turning degree, which is αi , we rely on the following theorem, Theorem 1. Assume the angle ϕ between the foot direction, i.e., df , and moving direction, i.e., dm, is invariable. Then the degree of the turning, i.e., αi , is equal to the relatively variety angle of moving direction, i.e., βi . Proof. Without loss of generality, as shown in Fig.12, the user makes a turning with angle of degree α around the point O. Let the direction from O to the foot as do, the foot direction as df , the moving direction as dm, the angle between the foot direction and moving direction are ϕi and ϕi+1, the variety angle of foot direction is βi , and the variety angle of moving direction is γ. Since dw is orthogonal to do, then αi = γ. As the vertically opposite angles is equal, we can have that γ + ϕi + λ = βi + ϕi+1 + λ. According to the assumption, ϕi = ϕi+1, then γ = βi . So we have αi = βi . Moving Direction Estimation. FootStep-Tracker use low-pass filter to extract the turning steps from the steps of walking straight ahead. Besides, for a single turning step, we find that the actual time which makes the foot turn is during phase (3), from the liftoff time to the landing time. That is because at phase (1)-(2), the heel lift up, preparing the forward movement. And at the phase (4)-(5), the foot is under the landing process. At those time, the feet has no rotation around the z-axis. To divide each phase, we need to extract the critical times, which is already given by Algorithm 1. By getting the liftoff time and landing time by algorithm 1, we calculate the turning degree by Eq.(7). As the foot is swing around the z-axis of gyroscope, we integral on gz from liftoff time to landing time, getting the turning degree of foot direction βi of the current step. And according to Theorem 1, we have the turning degree of the moving direction for the current step αi is equal to βi . For a n-step turning process, we then sum the αi up to get the turning degree α for one foot by equation α = Pn i=1 αi . Then we use the mean of the two feet as the turning degree. αi = βi = Z Td Tl gz(t) dt (7) E. Reference Position Estimator By Step Length Estimator and Moving Direction Estimator, we can accurately estimate the user’s moving trace. However, we still need to fix the moving trace into the global indoor map. To determine the location of the user by the moving trace and the indoor map, we have two basic intuitions. First, the user’s moving trace is constrained by the topological structure of indoor environment, which is to say that the user can not walking through the wall. Second, due to the reference position, such as elevators and stairs are fixed in the indoor map, we can accurately locate the user when he/she is doing the reference activities. To locate the user, and further track the user in the indoor environment, we adopt Snake Game[18] strategy as depicted in Fig. 14. As shown in (a), the user firstly taking an elevator, then turning right after walking a short distance. At this time, there are three possible location according to the moving trace and the position of elevator. When it comes to (b), the user keep walking. Limited by the topological structure of indoor environment, the infeasible moving trace (2) and (3) are filtered out, and the trace (1) is the actual moving trace of the user. (1) (2) (3) (a) Feasible traces. (1) (2) (3) (b) Filter out infeasible traces. Fig. 14. Snake Game strategy. As we have got the class of the user’s activity by Activity Classifier, if the user is ascending/descending an elevator or ascending/descending the stairs, we find the elevator or stairs’ location in the given indoor map as the reference position. After employing Snake Game strategy, we determine the actual user’s moving trace and location. Then we keep tracking the user’s location in time by the moving trace. V. PERFORMANCE EVALUATION A. Implementation Hardware: As shown in Fig.1 (a), our system consists of a TEXAS-INSTRUMENTS CC2541 SensorTag[4]. and a SAMSUNG Galaxy S5 Android smart phone