This work presents a vision-based navigation system designed for Indoor localization. The suggested framework operates as a standalone 3D positioning system by fusing a sophisticated optical- ow pedometry with map-constrains using an advanced particle lter. The presented method requires no personal calibration and works on standard smart-phones with relatively low energy consumption. Preliminary eld experiments on Android smart-phones show that the expected 3D error is about 1 2 meters in most real-life scenarios.
Indoor positioning is an important capability for a wide range of applications
including: location base services (LBS), public safety ( rst responders) and
autonomous robotics (indoor navigation). While LBS related applications mainly
target smart-phone users navigating in a shopping mall [
Utilizing particle lter for localization problem is common, both for indoor
and outdoor scenarios [
Real-time: For a natural and intuitive positioning results.
Privacy: The suggested solution should be able to work in an "o -line" mode (i.e., " ight-mode" or "standalone" mode).
Bring your own device: The suggested solution should work on existing COT S smart-phones. 1.1
This work presents a smart-phones indoor positioning system (IP S) based on recent AR and M R (Augmented and Mix Reality) tools such as Google's ARCore or Apple's ARKit. The AR tools are used as visual pedometry (scaled opticalow) sensor, which is then fused with an advanced version of localization particle lter to produce a both accurate and robust solution for various indoor positioning applications. The presented method allows a simple and e cient mapping solution that, combined with the localization particle lter, allows 1-2 meter positioning accuracy in most standard indoor scenarios. 2
The user global position can be retrieved from existing geolocation services (e.g., Google Maps Geolocation AP I). Such user location is commonly approximated using RF signals (4G 3G, W LAN , BLE) and even weak global navigation satellite system (GN SS). The accuracy of such methods is considered to be "building level" (10-30 meter) or "room level" (5-10 meter).
The user relative position is often computed using a pedometer. Smart-phone based pedometer is composed of two major virtual-sensors: (i) "Step-counter": which detects discrete step-events. (ii) Orientation sensor: which approximates the user global / relative direction. Combined the two parts allow a step based relative path computations. Naturally such method tends to drift in time (and steps). Many modern IP S are combining the above two positioning method in order to allow an accurate and global localization (with no drift). 2.1
This section discusses possible naive particle lter algorithm for localization estimation. Since particle lter method represents the posterior distribution of a set of particles P (jP j = n) on a given map, the result of such algorithm (for each step) is a new set of particles P 0 with a (slightly) di erent distribution. The goal of this algorithm is to get all the particles to converge into a single (compact) region on the map in few steps (re-sampling). Figure 1 presents a basic demonstration of such process. After converging, the algorithm computes the expected position using some variant of weighted average over the particles (or simply reports the location of the particle with the highest grades / likelihood). Before presenting the algorithm some terms should be clari ed: { Map: The particle lter methods estimates the internal state in a given region of interest (ROI). Thus, the input of this algorithm is a 2D, 2:5D or 3D map of the region, this map should include as many constraints as possible (for example rooms, walls, doors, stairs, etc'). The map constrains are used to determine each particle grade as particles with impossible location on the map will be downgraded. { Particle: At the beginning of the localization process we "spread" a set of particles P on the map. Each particle xi 2 P will have these attributes: location: < x; y; z > , orientation: w and grade: g. In each step all particles location and orientation will be modi ed as well as their grades. Since these particles represent the internal state-distribution, the sum of P particles grade is 1 in each step. At the initial step each particle xi grade is jP1 j . The grade of each particle will be set higher as its location on the map seems most likely to represent the internal state. { Move function (Action function): With each step all the particles in the map should be relocated according to the internal movement. Hence, for each step we calculate the movement vector (in 2D or 3D) and the di erence in orientation, then we move all the particles accordingly. The movement of each step is computed by the pedometer (step counter with orientation) as commonly used in smart-phone. { Sense function: The sensors of the device are used to determine each particle grade. The sense method predict each particle sense for each step and then grade it with respect to the correlation between the particle prediction and the internal sense. In the simpli ed case, the sense function computes the distance from each particle to the general estimated position (computed by some geo-location service) and evaluate each particle accordingly, e.g., if the distance from some particle p is larger than the estimated error (of the geo-location service) reduce the grade of p. The map constrains are also used in order to evaluate the probability (i.e., grade) of each particle. { Re-sampling: The process of choosing a new set of particles P 0 from P .
The re-sampling process can be done using various methods but the purpose of this processes is common; to choose the particles with high weight (i.e., grade likelihood) over the low weight ones. { Get best: The method that compute the output of the particle lter algorithm - the estimated position. Traditionally performed by one of three ways: return the best particle position, return the weighted average position of the particles or the combined approach, return the weighted average position of the particles that are in the range of some determined radius from the best particle.
Algorithm 1 presents the process of 2D localization using particle lter method with mobile pedometry sense (see Figure 1).
The naive algorithm is relatively time e cient, however, its precision might be insu cient in cases of large areas with few constraints. In the next section we proposes an improved version of the particle lter algorithm which support 3D, has better accuracy and improved robustness. 3
In this section an advanced localization algorithm is suggested: An improved map-constrains combined with adjusted sense function allows better accuracy.
end Algorithm 1: Generic particle lter localization algorithm: a black and white map is used in order to present the geo-constrains used by the particle lter.
The next subsections explain the improved mapping process and the advanced particle lter algorithm. 3.1
The advanced particle lter algorithm relies on the existence of a pre-made map of the region of interest. Such map assembled by our system using to the following technique: 1. AR measurements tools surface detection, which allows us to conclude the sampled region of interest boundaries. 2. The map is represented in the form of painted image, using the de ned colors: A, B, C, D to represent the verity of the di erent constrains.
The colors will be placed on the map according to the following logic:
{ A: Accessible area.
{ B: Unaccessible area, such as walls, xed barriers, etc. Sensed by AR tool.
{ C: Partially accessible regions. This area represents locations with relatively
low probability for a user to at (e.g., tables)
{ D: Floor changing regions, such as stairs, escalators and elevators.
A 2:5D map such as presented in Figure 2 will be the base for the particle lter
algorithm, and will later on be used to determine the particles grade.
Indoor navigation methods often use the device IM U sensor in order to
implement a pedometer which detect the device global orientation and count "steps".
Yet, such method introduces signi cant inaccuracy both in the distance
measured and in the orientation. Therefore, we use optical ow with plan and range
detection [
The naive and the advanced particle lter algorithm di er mainly by their sense functions. While the naive algorithm simply evaluate the weight of the particles according to their map location (a particle in B or A area), the advanced algorithm performs actual sense to determine how far each particle is from the truth. The sense performed by AR measurement tool detects the front plan region and compare it to the front plan region of each particle. This comparison gives us the ability to re-weight the particles in more precise way. 3.4
The orientation reported by smartphones often su ers from signi cant errors due to magnetic interference. In order to reduce the orientation inaccuracy related to compass noise and bias, the particle-state may also include additional dimension to estimate the compass original bias, and current drift. Initially, each particle starts with some Gaussian random value of compass bias. During the re-sampling process, each new particle will be assigned a compass related state according to the values of its nearest neighbors, with some minor noise. Each particle will use the smartphone's compass measured data combined with its bias and drift for the move function. 4
In this section we present an accuracy evaluation of suggested indoor positioning method. The main result addresses the Microsoft Indoor Localization Competition IP SN 2018 in which a preliminary version of the suggested algorithm was implemented which allows us a 1-2 meter accuracy in relative complicated 3D scenario. We conclude with few implementation remarks regarding the IPIN2018 results in which the suggested method took part and although got to the rst place, its accuracy was insu cient. 4.1
Since 2014 an annual Indoor Localization Competition is being organized by
Microsoft , see [
Fig. 4. The Particle Filter 2D convergence: Assuming the correct oor is known the
horizontal position converge from an error of 4.5 meters to about 1.3 meters within 10
seconds (about 15 steps). During the rest of the test the horizontal error is about 1
meter, while the vertical error is (on average) below half a meter.
During September 2018 an indoor positioning competition was held in a large
shopping mall at Nantes, France, as part of the IP IN 2018 Conference on Indoor
Positioning [