The localization of a user is a widely used feature in mobile devices these days. Localization is needed in many applications, from the maps and navigation applications, through games such as PokemonGo or Geocaching, to sharing location with friends and linking photos in your gallery to place where the photo was taken. The localization capabilities are an essential part of our everyday life. Although one may feel like the localization precision is sufficient these days, there may be situations where it is not. No one likes when their GPS (Global Positioning System) is targeting them on the map in a different place, especially when they want to get from place A to B (see picture below), but their A is 10 meters off the mark. This is a big issue, especially when the user is located in a building, where the signal is blocked by the roof and the surrounding walls. The signal coming from the satellite does not penetrate the materials, and therefore it is impossible to pin us on the map as well as it is possible in open space. With new technologies coming to our lives, the demands on localization accuracy will only increase. Navigation of drones through the city areas, which may be used to deliver packages or supervise the city traffic, have to be able to avoid the buildings, electrical wiring, and other moving objects such as other drones or birds. VR (Virtual Reality) headsets used in VR entertaining rooms require very high accuracy in localization of the player, as well as his limbs and held tools, in order to play high-demand multi-player games there.
While increasing the precision of the localization, especially in buildings and for use cases where the localization precision has to be in centimeter-accuracy ranges, new positioning schemes are being utilized apart from more traditional GPS or other GNSS (Global Navigation Satellite Systems). Although there are quite many of these new approaches, there is one thing the have in common, and that is the big amount of data they work with. One of the most discussed positioning schemes these days is called “fingerprinting”. Fingerprinting takes the so-called ”fingerprint” created by a mobile device at a specific location and compares it with a huge database of pre-created fingerprints linked to a specific location. From there, the system is capable to find the closest fingerprints to the new one and to approximate the location of the mobile device that just created last fingerprint, pinning the user on the map with way higher accuracy that the stand-alone GPS would. These fingerprints are usually just a set of measurements such as Received Signal Strength (RSS) from several surrounding base stations such as Wi-Fi routers (see picture below).
This otherwise simple scheme has several drawbacks – one of the biggest one being the size and quality of the database it requires to run properly. This is the reason why many researchers try to come up with a scheme to compress these data in one way or the other. In case the database of fingerprints is left unprocessed, there may be too much data and it could take a long to find the closest fingerprints leading to delays in localization – and no-one likes to wait!
“Compression” stands for the process of reducing the size of data. These data may be of various types such as pictures, soundtracks, or document files. On one hand, compression is a useful tool that not only enables data to take less space, but also allows them to be transferred faster. It may also help with faster processing or searching through big files and in some cases, it may even boost the performance of the system. On the other hand, compressing the data usually also means reducing their quality, as most compression schemes belong to lossy compression family. An everyday example of this may be found in picture compression. When the user wants to send a picture via channels such as Facebook or WhatsApp, the picture is compressed in order to take less space, be transferred faster, and make the data exchange more dynamic. However, such compression also reduces the resolution of the picture, and makes colors less bright and vibrant. Luckily enough, this does not have to be a disadvantage for the positioning systems.
One of the examples of fingerprinting dataset compression may be found in [1]. There, the authors compress several fingerprinting datasets using so called k-means clustering. The measured values of Received Signal Strength (RSS) are grouped together into predefined number of clusters (groups) based on their similarity and the specific RSS values are replaced with value representing given cluster. This process significantly compresses the whole dataset, making the processing much faster, mainly due to lower number of values the system has to go through in order to find the closest fingerprint. Interestingly, this method also improved the positioning capabilities in several presented databases. Although the database “resolution” was lowered (only one value per cluster instead of the whole database of different values), the positioning was more accurate. This is happening mainly because there are many inaccuracies in the RSS fingerprinting databases caused for example by the measuring device and the blockages in the way of the signal (e.g. walls). The compression method the authors presented filtered some of these inaccuracies out of the data, improving the outcome of the system.
Another example may be found in [2][3]. Here, the authors transform the RSS measurements dataset for indoor positioning into an image, creating RSS map of the building, which is compressed using Discrete Cosine Transform (DCT), which is the same scheme used as the main part of JPEG (picture) compression. The compressed image is then also used for positioning. Thanks to the smaller resolution of the color range of the figure after the compression, the map takes less space, but also eliminates the values that are too high or too low. This kind of filtering has proven to be beneficial and improved the indoor positioning accuracy.
Moreover, data compression is not only used for indoor positioning, but it is also applied in outdoor positioning applications in order to reduce the computational load in mobile devices. For example, [4] developed an online compression algorithm to compress data points (feature points) before uploading them to the server for further processing. Thereby, once the data is compressed, the authors are also able to compute non-feature points and reconstruct the user route.
Combined with outdoor positioning, we have Augmented Reality (AR) applications and ego-positioning. In general, these applications or solutions are often resource-intensive and challenging to deploy in low profile devices. That is why some authors have proposed compression methods to reduce the computational load without affecting the user experience. [5] proposed a novel compression method to reduce the 3D data point scene without altering scene structure. Once the 3D scene is compressed, the data points are equally distributed through all the scene dimensions. As a result, the authors reduced the computational load and positioning error (sub-meter accuracy).
To sum up, these examples expose only a few of many benefits of data compression for location-based services in mobile phones. As we can see, data compression permits more efficient management of storage resources, reduces the time search, provides computational efficiency and it even may help to reduce the positioning error. Thus, with the proliferation of new technologies and devices, data compression is a crucial point to provide more effective localization systems, which can be used in various devices such as mobile phones, smartwatches, smart glasses, among others.
[1] L. Klus, D. Quezada-Gaibor, J. Torres-Sospedra, E. S. Lohan, C. Granell and J. Nurmi, “RSS Fingerprinting Dataset Size Reduction Using Feature-Wise Adaptive k-Means Clustering,” 2020 12th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), Brno, Czech Republic, 2020, pp. 195-200, doi: 10.1109/ICUMT51630.2020.9222458.
[2] Talvitie, J., Renfors, M., Valkama, M. and Lohan, E.S., 2017. Method and analysis of spectrally compressed radio images for mobile-centric indoor localization. IEEE Transactions on Mobile Computing, 17(4), pp.845-858.
[3] Talvitie, Jukka, Markku Renfors, and Elena Simona Lohan. “Novel indoor positioning mechanism via spectral compression.” IEEE Communications Letters 20, no. 2 (2015): 352-355.
[4] Wei, P., Chunlong, Y., Xu, L. and Lan, S., 2014. An online compression algorithm for positioning data acquisition. Informatica, 38(4).
[5] Chen, K.W., Wang, C.H., Wei, X., Liang, Q., Yang, M.H., Chen, C.S. and Hung, Y.P., 2015. To Know Where We Are: Vision-Based Positioning in Outdoor Environments. arXiv preprint arXiv:1506.05870.
Graphics were reused from https://www.freepik.com/
by Lucie Klus and Darwin Quezada