We introduce a solution for a specific case of Indoor Localization which involves a directed signal, a reflected signal from the wall and the time diference between them. This solution includes robust localization with a given wall, finding the right wall from a group of walls, obtaining the reflecting wall from measurements, using averaging techniques for improving measurements with errors and successfully grouping measurements regarding reflecting walls. It also includes performing self-calibration by computation of wall distance and direction introducing algorithms such as All pairs, Disjoint pairs and Overlapping pairs and clustering walls based on Inversion and Gnomonic Projection. Several of these algorithms are then compared in order to ameliorate the efects of measurement errors.
Our solution localizes indoor objects using zero initialization, self-calibration and mapping of the room.
Previous works in this area of research have used triangulation and trilateration techniques in which the source was at the same location as the receiver. This did not compute the correct walls in the end. To address this issue, the Indoor Localization of Directed and Reflected Signals (ILDARS) approach proposes a mathematical model separating the source from the receiver. Using the information of the direction of the actual signal, reflection from the wall and the time diference between these, one can then compute the wall distance using various techniques as mentioned in subsequent sections of the paper. Problem Description We refer to our problem as Indoor Localization of Directed and Relfected Signals (ILDARS). Given -Line of Sight order one reflection and time diference of arrival measurements (abbreviated from hereon as LOS-T1R-TDoA), we need to compute all sources such as 1, 2, ...., . Assuming that the number of walls is and that atleast two sources reflect from the same wall, it is possible to solve the problem for two exact inputs in general position in 3D as well as the problem for two exact inputs in general position in 2D. This makes a straight-forward generalization with quadratic run-time possible. The practical problem however remains to find a stable solution for real-world inputs for random sources in 3D.
Ribiero et al 2011[
The Indoor Localization Directed and Reflected Signals (ILDARS) approach includes input signals coming in, localization based on reception which involves real-time part with same inputs and localization using diferent walls and a self-calibration part. The self-calibration aspect includes clustering and computation of walls. The output of this consists of position of sound source. Our approach could also be extended to other types of signals, such as light, from a mathematical point of view but for a realistic case concerning light, we would also require mirroring walls and have to take into account scattering from walls.
Problem Description Assume two general positioned sources in 3D, one reflecting wall with LOS-T1R-TDoA measurements. Given the directions, ⃗1 and ⃗2 of two signals, the directions ⃗1 and ⃗2 of their reflections from the same wall, the time delays of signals and reflections, Δ1 and Δ2. Compute the distances, 1 and 2 from signals to the origin.
If ⃗1, ⃗2, ⃗1 and ⃗2 are not co-planar, compute intersecting direction: ⃗ = and normal vector to the wall, ⃗ = ⃗. The term is the distance between the origin and the wall, following the same construction as in Fig. 6.
The ⃗ for the case where ⃗ ̸= ± ⃗ is a vector of unspecified length and inside the plane given by ⃗ and ⃗, parallel to the reflecting plane. Since we simulate real-world data, we assume all points and directions in general positions. The Indoor Localization Directed and Reflected Signals (ILDARS) 3D approach has been shown in Fig. 1.
For = 1, 2, ⃗ = ⃗ = ⃗ = (⃗ × ⃗) × ⃗
⃗ Δ⃗ ((⃗ − ⃗) · ⃗)
Testing out all combinations of LOS-T1R-TDoA pair leads to conflicts including construction of false positive walls, multiple walls for a reflection and replicated walls because of erroneous inputs. The conclusion of ILDARS for 3D is that it does not scale and hence does not compute the required distances, 1 and 2. (1) (2) (3) (4)
For this paper, we define a wall as a simple polygon in a plane and a room as a collection of walls. We then denote the position of the listener device as ⃗ ∈ R3. Further, we need at least two sound sources ⃗1, ⃗2, . . . , ⃗ ∈ R3. The sound sources then emit sound signals which the listener receives and then computes measurements from. A measurement is a triple (⃗, ⃗, Δ) where ⃗ is the direction of a direct signal, ⃗ is the direction of a reflected signal, which originates from the same sound source as ⃗, and Δ is the time diference between receiving the direct and the reflected signal as shown in Fig. 6.
Our goal is to compute the position of the sound sources ⃗1, ⃗2, . . . , ⃗. Note that, because all measurement are relative to the sender, we assume ⃗ = 0 in the setup shown here in Fig. 2. Fig. 3 shows an overview of the design of the ILDARS system: The first step is to find clusters of measurements, each corresponding to one wall, such that all reflected signals in one cluster are reflected from the same wall. For this clustering step we introduce two alternatives called Inversion and Gnomonic Projection.
After the measurements have been clustered, we can use one cluster of measurements to compute the direction of the corresponding wall. Once the wall’s direction is known, we can also compute the distance.
For computing the direction of the wall, we need to average over selected pairs of measurements. We have three options for selecting such pairs, called All Pairs, Disjoint Pairs and Overlapping Pairs.
Clustering the measurements and computing the direction and distance of the walls is what we refer to as the Self-Calibration step. Using the computed wall positions, we can then compute the position of the sender for a given measurement in the Localization step. The reason for separating the process into these two steps is that the Self-Calibration step could be executed once, and then it’s results could be used for new individual measurements in an online variant of the localization step.
As our initial input, we get a large set of measurements from diferent walls. In the self calibration phase, we need to separate these measurements by the walls that the respective reflections were reflected from. In addition to that, we also compute the direction and distance of the wall.
From a triple→(− →,− , Δ), we can construct circular segments which intersect with the wall from whic→h− was reflected, as illustrated in Fig. 4. Assuming the measurements to not contain any error, circular segments from the same wall would intersect, which could be used to find reflections from the same wall. With measurement errors, the circular segments would not perfectly intersect, but segments from the same wall would still be close to each other, meaning that we need to identify close segments in order to find segments belonging to the same wall.
One approach we use to determine the closeness of two circular segments is to apply Unit Sphere Inversion to their respective endpoints, which gives us the endpoints of a finite line segment.
For a given vector ⃗ = (, , ), we compute it’s inversion ′ := 2(+,2,+)2 . This definition
is based on the Book "Introduction to Geometry" by Coxeter [
Let ℓ be the list of all finite line segments we get from our measurements, we now want to ifnd subsets of ℓ with close lines which will then be our measurement clusters. We iterate over each line ∈ ℓ and check whether there is a cluster for which the distance (, ) is below a threshold . If (, ) ≤ , we add line to cluster and then continue with the next line. Since we don’t have any clusters in the beginning, we initialize out first cluster with the first line. When computing the distance (, ) for a given line and a cluster , there are two cases: (, ) = {︃(, )
if = {} (, ) if‖‖ > 1 (5) The first case applies if contains only one line . The second case applies if contains at least two lines. Once we add a second line to a cluster with only one line, we also store the clusters , which is initialized with the closest points between two lines and is adjusted if we add more lines.
Once all lines are added to a cluster, for each cluster of lines we get one cluster of measurements containing the respective measurements the lines were originally computed from. In the worst case, we get one cluster per line meaning that our Inversion algorithm has (2) time complexity, where is the number of measurements.
As an alternative approach to the Unit Sphere Inversion approach, we can also use Gnomonic
Projection to cluster the circular segments, discussed in section 5.1.1. This technique was
introduced by Rico Giessler [
It’s performance is significantly worse, compared to the Inversion approach, as can be seen later in section 8. In this technique, we first project each circular segment onto the unit sphere with radius 1, assuming the receiver to be at the origin. For a vector , we simply compute ′ := ‖‖ to map onto the unit sphere. Applying this normalization to the two end points of a circular segment, we can then compute the latitude and longitude of the end points using = arcsin() = arctan(/) Next, we choose twelve evenly spaced hemisphere center points ℎ1, . . . , ℎ12 on the unit sphere with a random rotation. For each of these hemisphere center points, we also compute their latitude and longitude.
For a given hemisphere center point ℎ, supposing ℎ and ℎ be the latitude and longitude respectively. For a given end point of an arc on the sphere, and are the latitude and longitude of the point respectively. With this information, we can now compute the gnomonic coordinates of on the hemisphere around ℎ using = = with cos( ) sin( − ℎ )
cos() 1 cos() · (cos( ℎ ) cos( ) − sin( ℎ ) cos( ) cos( − ℎ1 )) () = sin( ℎ ) sin( ) + cos( ℎ ) cos( ) cos( − ℎ1 )
Computing the gnomonic coordinates of the two endpoints of an arc gives us the two end points on a two-dimensional plane, which we refer to as the gnomonic projection. The intersection graph , is then created, where each line in the gnomonic projection is represented by one node. Two nodes in the intersection graph are connected if. the respective lines are intersecting. We finally return the connected components of as our clusters.
The clustering step, discussed in section 5.1, computes sets of measurements (, , Δ) such that all reflected signals in one set were reflected from the same wall, apart from some false positives. We call these sets clusters.
For each cluster, we compute the direction and the distance of the respective wall, which is necessary to then compute the sender positions in section 6. A wall’s distance and direction is (6) (7) (8) (9) (10) ⃗ = Due to the non-commutativety of the cross product, we need to either select ⃗ or − ⃗ as the wall’s direction. We do so by comparing both options ⃗ and − ⃗ to the reflected signals ⃗1, ⃗2 and select the option which minimizes the function : ⃗ ↦→ |⃗ · ⃗1 − 1| + |⃗ · ⃗2 − 1|. Note that all vectors ⃗, ⃗1, ⃗2 have length 1.
To use the formula above to more than two measurements, we simply apply it to pairs of measurements and then take the average over all results. This leads to the question which pairs to use. For measurements 1, . . . , , we compare the following selections of pairs of measurements: • All Pairs: All possible combinations of pairs of measurements.
(1, 2), (1, 3), . . . , (2, 3), . . . , (− 1, ) • Disjoint Pairs: (1, 2), (3, 4), . . . , (− 1, ) • Overlapping Pairs: (1, 2), (2, 3), . . . , (− 1, ) Note that using the All Pairs method leads to a quadratic algorithm, while using the Disjoint Pairs or Overlapping Pairs methods gives us an algorithm with linear time complexity.
Once we know the direction ⃗ of a given wall, we also compute it’s distance. For a given measurement (⃗, ⃗, Δ), we can compute the position ⃗ of the respective sender using the Wall Direction formula: encoded by it’s wall normal vector which, geometrically can be defined as the vector from the receivers position to the closest point on the wall.
For two given measurements (⃗1, ⃗1, Δ1), (⃗2, ⃗2, Δ2), for which the reflections are from the same wall, we can compute the direction of the wall using the nested cross product : (11) i.e. (12) (13) (14) using ⃗ = (⃗ × ⃗) × ⃗ We can then compute the distance := ‖⃗‖ for
⃗ = ⃗ =
Δ⃗ · ⃗ (⃗ − ⃗) · ⃗ ⃗ = ⃗ + ( + Δ)⃗ 2 · ⃗ We compute this distance for each available measurement and then take the average over all results as the final distance of the wall.
Using a measurement cluster and respective wall normal vector as input, we introduce four methods for computing the position of a sender for each measurement.
Map to Normal Vector The Map to Normal Vector method computes the position ⃗ of a sender using Equation (12), with Reflection Geometry The Reflection Geometry sender using Equation (12), with method computes the position ⃗ of a = (2⃗ − Δ⃗) · ⃗
(⃗ + ⃗) · ⃗ =
2(⃗ · ⃗)(⃗ · ⃗) (⃗ · ⃗)(⃗ · ⃗) + (⃗ · ⃗)(⃗ · ⃗) (15) (16) where ⃗ = (⃗ × ⃗) × ⃗ is a vector parallel to the wall. The diagrams for both the localization techniques, i.e; computing sender position using a single wall using the Map to Normal and Reflection geometry have been shown in the Fig. 5. Wall Direction The formula for this method has already been introduced in section 5.2.2, where it is used for computing the distance of a given sender, using just the direction ⃗ of a wall in Equations (13) and (14).
The diagram for this method has been shown here in Fig. 6.
Closest Lines The Closest Lines method computes a senders position by computing the closest point between two lines. For the lines we choose
( ) : = ⃗ ℎ( ) : = 1 + ⃗ (17) (18) Where 1 := 2⃗ is the mirrored receiver position and ⃗ := ⃗ − 2(⃗ · ⃗) · ‖⃗‖ ⃗ is ⃗ mirrored on the wall. In Fig. 7, line is drawn in green and ℎ is drawn in blue.
Note that the introduced methods to compute sender positions only use one wall, while in the clustering step we compute multiple clusters of measurements from which we can compute multiple wall normal vectors. This leads to the question which wall to use in the localization step. We introduce three simple methods for choosing a wall. Largest Cluster will simply use the wall where the respective measurement cluster contains the most elements. For a diferent method called Narrowest Cluster, we compute the average angular distance of the reflected signals to the wall normal vector that is generated using the respective cluster. We then choose the cluster which minimizes this value. For our third method, Unweighted Average, we simply compute each sender position once for each wall and then take the average position for each sender as the final output.
Another approach to sender localization we introduce is to use multiple walls in one algorithm.
This algorithm titled Closest Lines Extended is based on the Closest Lines approach. For a
given direct signal, we consider all the respective reflected signals which were assigned in the
clustering step, which means for each of the reflected signals we have one wall normal vector.
We then take a line like with Closest Lines and then we also use one additional line for
each pair of wall normal vector and reflected signal, using the same formulas as in the regular
Closest Lines approach. We then use an algorithm introduced in [
For testing the presented algorithms, we first generate simulated measurements using 20 randomly placed sender positions in a 2 × 2 × 2 meters cube. We set the receiver position to be exactly at the center of the room. For simulating the data, we assume that the receiver receives one direct signal from each sender and one direct sender from each wall for each sender. We assume angle of incidence to be equal to the exit angle for the reflected signals. To get a more realistic simulation of input signals, we apply three types of errors the simulated data.
Firstly, we use a von Mises distribution to alter the angle of all direct and reflected signals ⃗ and ⃗. For the von Mises distribution, we use a concentration value = 131.312. We also use a normal distribution with a standard deviation of 10 to simulate errors on the Δ values. If this results in a negative Δ, we take the absolute value instead. In addition to the simulated error on the measurements itself, we also randomly assign 5% of reflected signals to a diferent direct signal.
Using the simulated input data, as described in section 7, we now run all possible combinations of algorithms on the same inputs. For each computed sender position, we save the euclidean distance to the actual position of the sender that the respective direct signal was emitted from. In the following, we will refer to this euclidean distance as the ofset. We ran 500 experiments, each with new random sound source positions, and then analysed all the ofset values from all experiments.
For readability reasons, we use abbreviations for the algorithm names in Fig. 9 to 11. I stands for Inversion, G for Gnomonic Projection, A for All Pairs, O for Overlapping Pairs, D for Disjoint Pairs, U for Unweighted Average, N for Narrowest Cluster, L for Largest Reflection Cluster , C for Closest Lines, W for Wall Direction, R for Reflection Geometry , E for Closest Lines Extended and M for Map to Normal Vector.
Note that, when the Closest Lines Extended algorithm is used, there is no need to choose one of the computed walls, since Closest Lines Extended uses all walls. Therefore, all combinations of algorithms using the Closest Lines Extended algorithm will implicitly use the Unweighted Average method for wall selection. Fig. 9 represents all combinations of algorithms sorted in increasing order of mean ofset values. This is also verified using the box-whisker plot, Fig. 13 which shows a similar trend but is specific to the first five most accurate combinations of algorithms based on mean ofset.
Fig. 10 represents all combinations of algorithms sorted in increasing order of median ofset values. This is also verified using the box-whisker plot, Fig. 12 with a similar trend but only shows the first five most accurate combinations of algorithms based on median ofset.
Fig. 11 represents all combinations of algorithms sorted in increasing order of standard deviation of the ofset values.
Fig. 12 presents the ofsets of the five algorithms with the lowest median ofset using a boxwhisker plot. The plot shows that the combination of the Inversion clustering method and the All Pairs method for wall direction computation yields the most accurate results, judging by the median ofset. For wall selection, the Narrowest Cluster method, combined with the Closest Lines algorithm for localization, gives the most accurate results.
Fig. 13 shows the 5 most accurate combinations of algorithms judging by the average ofset. Note that the mean ofset, indicated by the green line, for all combinations is significantly higher than the orange line indicating the respective median. This can be attributed to outliers with large ofset values.
Compared to Fig. 12, the Closest Lines Extended algorithm produces lower average ofset values compared to Closest Lines algorithm using a single wall.
In this paper, we illustrate various techniques to compute the distance, between sender and receiver depending on various configurations of sender-receiver pairs with respect to the wall and the normal vector to it. We also cover various techniques of grouping multiple reflections together using projection and inversion. In the final results we compare multiple algorithms combining several of the aforementioned techniques and come to the conclusion that the combinations involving Inversion perform significantly better than those with Gnomonic Projection as can be verified from the mean and median bar as well as box-whisker plots for the ofsets in section 8. As a possible future work, we would like to move forward into employing the above techniques on real-world experimental data instead of simulations as have been currently used here since it is not clear how comparable our simulated data is especially in regards to the simulated errors, compared to data from real-world experiments.
The resources related to our work and the webpage of our group are available at : • GitHub repository of our project, • Webpage of Prof. Dr. C. Schindelhauer’s group.