[time]
2020-11-29T14:34:08+01:00

[team_name]
imec-WAVES/Ghent University

[team_institution]
Ghent Universtity, WAVES-intec

[logolink]
https://www.waves.intec.ugent.be/files/waves_v5.svg

[system_name]


[website]


[track]
3

[reference_person]
Cedric De Cock

[email]
cedric.decock@ugent.be

[description]
Description short (100-200 words):
Our system consists of 4 parts. The first part uses intertial sensordata to detect steps, estimate step length and heading estimation and to recognize walking modes. The second part uses the PDR algorithm to interpolate between the sparse ground truth positions. The interpolated positions are used to create a radiomap. The third part uses the barometer and RSS measurements from the training data to detect floor transitions, to estimate during which steps the user is using the stairs and to calculate the most likely sequence of floors visited by the user. In the final part, a backtracking particle filter (BPF) is used to estimate the trajectory. The step lengths and headings are used to propagate the particles. The positions of walls are used to remove particles that were propagated through a wall. The weighted centroid of the k best RSS matches is used to weigh each particle, based on its distance to the matched position. The locations of staircases are used to decrease the weight of particles outside of staircases when the barometer detects a height change. The floor transitions are used to load the next floor map and radiomap.

Description long (500-2500 words):
Our system consists of 4 parts: Pedestrian Dead reckoning, RSS fingerprinting, floor (transition) detection and particle filtering.
1.	Pedestrian Dead Reckoning
The AHRS data (pitch and roll) are used to transform the accelerometer and magnetometer data from the local (smartphone) coordinate system to the horizontal plane and to calculate the horizontal angular rate from the gyroscope data. The gravity component and high frequency noise are removed from the vertical acceleration. The latter is then used for step detection by searching for local maxima. Estimation of the step length is based on the Weinberg method, but the coefficient is adapted for every step depending on the estimated velocity during that step [1]. 

The direction of the step is estimated by integrating the horizontal angular rate to the ‘gyroscope yaw’. The gyroscope yaw is relative to an initial angle. This initial angle is determined by aligning the gyroscope yaw with the ‘magnetometer yaw’, which is calculated from the horizontal magnetometer data. The alignment of the gyroscope yaw with the magnetometer yaw is done by detecting the time interval during calibration when the smartphone is held still. The average difference between gyroscope and magnetometer yaw during this interval is added to all gyroscope yaw data. The magnetometer and gyroscope yaw are then fused, based on their correlation and magnetometer stability [2].

The walking mode is determined for each step by a KNN-classifier. The features used are average and variance of both roll and pitch from the AHRS data during the step. The competition training data only include one walking mode: holding the smartphone in front of the body. Additional training data was generated by the team to train the classifier on data of different walking modes (swinging and calling).   

2.	RSS fingerprinting

The training data include ground truth positions at turning points. The user always walked in a straight line between these points. To construct a radiomap, the RSS data are first matched to the timestamp of the closest step detection. Different RSS values from the same access point (AP) at a matched timestamp are averaged. The detected steps and their relative estimated length are then used to interpolate the position of the fingerprint on a straight line between two consecutive ground truth positions. The ground truth positions include the floor number. This number is also added to each fingerprint of the radiomap.
A Weighted K-NN fingerprint matching algorithm is used to estimate the user position. The Euclidean distance metric is used to match RSS vectors in the validation/evaluation data with RSS vectors in the radiomap. The metric can only be applied to a subset of RSS values for each vector, depending on the AP the vectors have in common. A penalty is added to the Euclidean distance for each AP that is not in the subset. This prevents a good match when the RSS vector only has a few AP in common with the radiomap RSS vector but with similar RSS values. The weighted centroid of the k best matches is selected as the estimated position.

3.	Floor (transition) detection

The barometer can be used to estimate height changes [3]. The pressure during each detected step is converted to height difference relative to the first step. A low pass filter is then used to remove noise. If the absolute height change is more than 1.5m within a window of 15 consecutive steps, these steps are labeled as ‘on stairs’. The pressure changes with time regardless of the actual height difference. If the time between two steps is more than 1.5s, the height difference between these steps is removed to prevent false stair detections in case the user is standing still for a significant amount of time. The height difference during each sequence of ‘on stairs’ labels is then used to estimate the floor difference. The middle step of each ‘on stairs’ sequence is labeled as ‘transition’. The barometer method can accurately detect transitions, but can have errors in the estimated floor differences because the true floor height is unknown. The visited floor itself can be determined by matching RSS measurements with the radiomap, but sometimes the wrong floor is matched for a short time interval. The Viterbi algorithm was used for the previous competition in 2019 to perform localization [4]. It is now used used to find the most likely sequence of visited floors by fusing the RSS matching and barometer methods. This allows to differentiate between a short floor visit or a false RSS match.

4.	Particle filtering

The particle filter is used to fuse the output of previous parts and to perform map matching. 
To enable the latter, the provided floor plan images are converted to XML files containing the locations of each wall and staircase. This is done with the WHIPP tool [5], where the user can upload an image, set the scale and draw the walls over the image. The particle filter implemented in this system is the backtracking particle filter (BPF) [6]. The BPF has an output buffer or ‘tail’ that allows to smooth the filtered state at time T - tail_length, using the filtered states at times [T - tail_length, T], with T the time of the current BPF iteration.
At initialization, the BPF generates a large set of thousands of particles equally distributed over the floor plan, because the initial position is unknown. However, the amount of particles is drastically reduced during the next iterations. The step length and heading of the detected steps are used to propagate the particles. The artificial Gaussian noise added to the heading depends on the detected walking mode. In general, the heading estimation is robust when the user is holding the phone in front of the body. The artificial noise standard deviation is therefore relatively low. However, when the user simulates a phone call, the estimated heading is unstable, especially during transition between the walking modes. Therefore, the added noise is increased to allow the algorithm to divert from the heading during this interval. The floor plan is used to remove all particles that crossed a wall during propagation. If RSS measurements are available for the current step, the position is estimated with the WKNN algorithm and a gaussian function is used to weigh the particles based on their distance to the estimated position. If the step is labeled as ‘on stairs’, the weights of particles outside of staircases are decreased proportional to their distance to the closest staircase. If the step is also labeled as ‘transition’, the next floor plan and radiomap are loaded. Resampling is performed when the amount of particles drops below a threshold. As with the heading noise, this threshold depends on the walking mode. 500 particles are used when the user is holding the phone in front of the body, while 1000 particles are used when the user is simulating a phone call. After resampling, the amount of particles is restored to the corresponding threshold.

References:
1)	Ho, Ngoc-Huynh 

[Truong,_Phuc_]


[Jeong,_Gu-Min__(2016)__Step-Detection_and_Adaptive_Step-Length_Estimation_for_Pedestrian_Dead-Reckoning_at_Various_Walking_Speeds_Using_a_Smartphone__Sensors__16__1423__10_3390/s16091423_
2)	Kang,_Wonho_]


[Han,_Youngnam__(2014)__SmartPDR:_Smartphone-Based_Pedestrian_Dead_Reckoning_for_Indoor_Localization__IEEE_Sensors_Journal__15__1-1__10_1109/JSEN_2014_2382568_
3)	Li,_Binghao_]


[Harvey,_Bruce_]


[Gallagher,_Thomas__(2013)__Using_barometers_to_determine_the_height_for_indoor_positioning__1-7__10_1109/IPIN_2013_6817923_
4)	Trogh,_Jens_]


[Plets,_David_]


[Martens,_Luc_]


[Joseph,_Wout__(2015)__Advanced_Real-Time_Indoor_Tracking_Based_on_the_Viterbi_Algorithm_and_Semantic_Data__International_Journal_of_Distributed_Sensor_Networks__2015__1-11__10_1155/2015/271818_
5)	Ghent_University_IMEC,_“Wica_heuristic_indoor_propagation_prediction_tool_(whipp),”_https://www_waves_intec_ugent_be/exposure-tool/expertedition,_2020
6)	Widyawan,_Widyawan_]


[Klepal,_Martin_]


[Beauregard,_Stéphane__(2008)__A_novel_backtracking_particle_filter_for_pattern_matching_indoor_localization__79-84__10_1145/1410012_1410031_
]


[references]