# A Hybrid Marker-Based Indoor Positioning System for Pedestrian Tracking in Subway Stations
## 3 The Proposed HMIPS
### Indoor Map Registration and Modeling
#### Modeling of Indoor Spaces  
To install markers and represent them in relation to locations, modeling of the indoor space is required. By using information such as spaces and walls obtained from the registered indoor map, it is possible to determine separate spaces, walls, and connection spaces. Subsequently, spatial modeling work is performed that divides each separated space into smaller spaces for marker-based positioning. The Voronoi tessellation technique is used for this spatial division [34].  
* Voronoi tessellation  
In mathematics, the Voronoi diagram is a technique that divides a space based on the distance of specific points on a plane. The location of the seeds corresponding to the number of spaces to be divided is pre-arranged, and for each seed, an area composed of all the points closer to the seed than to the other seeds is created. Each of these areas is called a Voronoi cell. In this case, the Euclidean distance is used as the distance to the point, as in Equation (1).  
\[(d[(x_{1},y_{1}),(x_{2},y_{2})])=\sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}} \tag{1}\]  
Figure 1: Process of hybrid marker-based indoor positioning system.  
where, \(x\) and \(y\) denotes coordinates of the seed.  
However, if only this Voronoi spatial segmentation technique is applied to the spatial modeling work, there is a large difference in the expanse of each area depending on the initial location of the seeds. This can also be seen in Figure 3a. Additional corrections are required.  
* Lloyd's relaxation  
This algorithm, also known as Lloyd's algorithm or Voronoi iteration, is an algorithm for dividing the Euclidean space into uniform shapes and sizes [35]. The algorithm uses a Voronoi diagram and is performed by repeating the task of moving the seeds of each Voronoi cell to the corresponding centroid after calculating each Voronoi cell's centroid. This repetition is stopped when the center of gravity of each Voronoi cell and the seed match. As can be seen in Figure 3b, Lloyd's relaxation can be used as a spatial model because it is possible to divide a region of an even size to some extent. In addition, even if the initial seed location is not uniform, the result can be divided evenly through correction if the seed location is randomly selected. Finally, it can be easily applied to buildings with complex shapes other than simple rectangles because this method is based on the center of gravity calculation.  
* Connection space calculation and route finding  
Figure 3: Modeling of indoor spaces: (**a**) Voronoi diagram; (**b**) Process of Lloyd’s relaxation.  
Figure 2: Planning tool of the HMIPS.  
If the spatial division is completed through Voronoi tessellation and Lloyd's relaxation, the spatial connection process is performed. Two adjacent Voronoi cells are connected as a movable space, and the space, wall, and connection space obtained from the registered indoor map are connected to the moving path based on this information. The space where pedestrians can move can be obtained from indoor map information. In other words, the movable space refers to a path through which pedestrians can pass without being obstructed by obstacles such as walls. The connection data are then used for path finding.