Real-Time Visual Place Recognition for Personal Localization on a Mobile Device

Personal indoor localization is still a problem to be solved without using an additional infrastructure. A number of emerging applications of mobile devices require user localization with respect to predefined objects or places. Although much work has been done on practical localization in indoor environments where GPS signals are not accessible, resulting in commercially available solutions,¹ there is a need for approaches that are independent of the artificial sources of signals, such as RFID/BLE beacons or WiFi networks. Whereas external infrastructure can be easily applied for localization in limited areas [1], many applications benefit from infrastructure-free indoor localization. Examples range from guidance of visitors in large buildings or exhibition areas to location-aware advertising in shopping centres [2]. Nowadays, smartphones and tablets have the considerable computing power and are equipped with high-quality cameras. The ever increasing performance of such mobile devices allows us to consider vision-based algorithms for personal indoor localization. Localization utilizing visual information can operate regardless of the availability of particular infrastructure or the presence of specific features in the environment. In particular, visual localization by place recognition is similar to the way people and animals localize themselves in a surrounding environment, associating the current visual perception to the past episodic memories [3].

The application of cameras for localization was already researched extensively in robotics, resulting in a number of Visual Odometry (VO) [4] and Simultaneous Localization and Mapping (SLAM) [5] algorithms. Unfortunately, the use of VO/SLAM on mobile devices is challenging due to the rapid, unconstrained motion of the embedded camera, limited availability of point features, and the high computing power demanded by VO/SLAM systems. Among the state-of-the-art visual localization methods, the Parallel Tracking and Mapping (PTAM) algorithm [6] was implemented on iPhone [7], whereas the SVO system [8] was demonstrated working in real-time on the limited-power Odroid platform. However, the iPhone implementation of PTAM has limited functionality with only the camera pose tracking running in real-time in small workspaces, which made this system more suitable for augmented reality applications than for personal localization in buildings. Also, the SVO, which was developed for small aerial vehicles, is rather unsuitable for personal localization, as it requires a very fast camera and makes strong assumptions as to the camera motion [8].

More typical monocular SLAM algorithms, such as the recent ORB-SLAM [9] that demonstrated very accurate camera trajectory estimation on several benchmarks, cannot be used in real-time on mobile devices due to the high computing power requirements of their underlying graph optimization techniques. Although the SlamDunk system, also based on graph optimization has been re-implemented on a mobile device [10], it utilizes RGB-D data to simplify 3-D perception and requires a Kinect-type sensor connected to the device, which is infeasible for most applications. Whereas new sensors aimed at enhancing mobile devices with RGB-D perception, such as the Intel RealSense become available, this technology still offers relatively short-range perception. So far it is suitable rather for 3-D object recognition or augmented reality than for building-scale localization.

Our experience from implementing a typical monocular VO pipeline on Android-based devices [11] suggests that robust, real-time operation of purely visual odometry is possible only if the acquired images do not show significant motion blur, and the device held in hand makes no sudden orientation changes. This, together with the high computation burden of the motion estimation algorithms [11] makes VO impractical for personal indoor localization. Although the recently developed VO algorithms based on visual and inertial information [12, 13] can overcome to a great extent the problems related to sudden motions of a handheld camera, they still need relatively high computing power [14], and thus drain a lot of energy from the device’s battery. Vision-based tracking was already integrated with WiFi and inertial data for personal localization [15], but using a setup that only resembled a mobile device, thus avoiding the computing power and energy efficiency issues.

Another possibility in visual localization is the appearance-based place recognition [16]. Contrary to the VO/SLAM algorithms, the place recognition methods only determine if the observed place is similar to an already visited location. However, the place recognition methods scale better for large environments than typical SLAM algorithms [17]. In the appearance-based methods each image is processed and described by descriptors of salient features, or directly described by a vector of numerical values constituting a whole-image descriptor [18]. Direct matching of local image features is inefficient for place recognition [16], thus the Bag of Visual Words (BOVW) technique [19] is commonly used, which organizes the features into a visual vocabulary. Images described by visual words can be efficiently matched using a comparison of binary string or histograms. One prominent example of a place recognition algorithm that employs the BOVW technique is FAB-MAP [20], which implements efficient comparison of images with a histogram-based method. This algorithm and its further developments have demonstrated impressive results over very long sequences of images in various environments [21].

Recent approaches to direct image description involve usage of image sequences [22]. The use of sequences instead of individual images exploits the temporal coherence of vision data acquired by a moving camera [23], thus decreasing the number of false positives in place recognition for environments with self-similarities, and increasing the tolerance to local scene changes. This idea is used by the ABLE-M [24] algorithm, which substantially scales down the processed images, and compares global binary descriptors using the quick to compute Hamming distance.

Image retrieval techniques similar to those applied in appearance-based localization were already used on smartphones in the context of object recognition [25]. However, only a few papers tackle the problem of appearance-based localization on mobile devices. An algorithm that combined WiFi fingerprinting without a pre-surveyed database of fingerprints, and a simple visual appearance-based location verification technique was presented in [26]. This work demonstrated that although the appearance-based recognition on a smartphone returned a higher number of false positives than the WiFi-based method, the number of locations correctly identified using the visual data was still much bigger than the number of locations identified by matching WiFi fingerprints. If a database of images acquired at known positions is available, it is possible to compute user position and orientation using an image acquired with the smartphone camera, as demonstrated in [27]. However, this approach seems to have a limited potential in practical applications, as collecting the database of images requires a special trolley with a multi-sensor set up for accurate localization. To the best knowledge of the authors, their recent paper [28] was the first one systematically investigating vision-only appearance-based localization on an actual smartphone, and demonstrating the feasibility of an algorithm based on sequences of images for personal localization.

In this article we significantly extend our preliminary research, presented in the recent conference paper [28]. This research revealed that the ABLE-M algorithm based on image sequences is particularly beneficial for place recognition in corridor-like environments, where not enough salient features are available for reliable comparison based on a single query image. Moreover, the local binary descriptors used in ABLE-M make it very fast at computing individual matches between images. This makes ABLE-M an interesting choice for implementation on mobile devices for the use in large buildings. However, as we show using the experimental data, and confirm by the theoretical analysis, the processing time of the ABLE-M algorithm does not scale well for long database sequences. Therefore, we propose a much faster version of the ABLE-M algorithm, called FastABLE, that suits the needs of personal localization on mobile devices. In the improved version, the processing time is independent of the size of the comparison window. The FastABLE code is publicly available as open source, together with the test sequences, to make our results fully verifiable. Thus, the main contribution of this work is twofold: (1) thorough experimental and theoretical analysis of the properties of the two representative appearance-based place recognition algorithms in the context of implementation on a mobile device; (2) new appearance-based localization algorithm tailored specifically to the requirements of the mobile devices with limited computing power and typical characteristics of indoor environments.

Before the FAB-MAP is ready to recognize places, pre-training and training processes must be performed. In the pre-training process, the system determines the types of descriptors that can be found in the environment by creating the BOVW vocabulary. Therefore, the pre-training images should represent the characteristic of the target operational environment. In this step, all descriptors found in the pre-training images are clustered using the k-means algorithm with the Euclidean distance measure. Each cluster constitutes a single word from the center of belonging members which is then inserted in the vocabulary. This vocabulary is used in the Chow-Liu training procedure that is performed with the Meilǎ’s algorithm [31]. In turn, in the training process, the taken images are processed to create a database of places for recognition. For each image, the BOVW is computed that is used in the recognition phase.

During recognition, the FAB-MAP describes features in the image and computes the BOVW based on the occurrences of those descriptors. The final step involves computing the set of probabilities that the observed image was taken in the place recorded in the database. The i-th place is usually considered as recognized when the probability \(P(L_i | \mathcal {Z}^k)\) exceeds the chosen threshold \(t_p\). The overview of the FAB-MAP processing is presented in Fig. 1.

The OpenFABMAP system has one major parameter to tune, which is the probability threshold \(t_p\). In the preliminary tests [28], we couldn’t find a single setting of \(t_p\) that would allow achieving no false positives with the satisfactory number of correct recognitions. Therefore, we decided to modify the OpenFABMAP operation to include information about a sequence of images. Whereas in the original OpenFABMAP the i-th place is recognized in the k-th frame if the probability \(P(L_i | \mathcal {Z}^k)\) exceeds \(t_p\), in our improved version the i-th place is considered to be recognized in the k-th frame only if the probability exceeds \(t_p\) for all frames in the window spanning from \((k-c_w+1)\)-th to k-th frame:where \(c_w\) is the size of the comparison window. The modification is presented with red color in Fig. 1. The justification for the above formula is the fact, that the individual image recognition acts are assumed to be independent in the FAB-MAP algorithm. However, in the indoor localization task, we have a continuous motion of the user (and thus the camera). Therefore, we expect frames in a short sequence to be observations of approximately the same location.

The introduced modification added the second parameter (\(c_w\)) to set up but finally allowed us to find a parametrization of OpenFABMAP that suits the indoor environment. The value of \(c_w\) influences a ratio between false positive and correct recognitions. The higher the value the longer the comparison window and therefore the sequence of frames matched to the same image from the database has to be longer. It implicates that higher values prevent the algorithm from making mistakes, but also lowers the number of places that are correctly recognized. Analogously, a shorter \(c_w\) window results in more false positives, but also more places are recognized. Further discussion is provided in Sect. 4.2.

The ABLE-M algorithm processes sequences of images, thus the processing of individual frames has to be very fast to allow real-time operation. To this end, ABLE-M resizes the processed images to the size of \(64\times 64\) pixels. Next, a global variant of the LDB feature descriptor is computed with respect to the whole resized image. The binary LDB descriptor [33] is computed by comparing individual intensities of pairs of points along the predefined lines. LDB was designed to suit the needs of mobile devices, thus it can be computed with minimal effort. It should be noted that prior to image description ABLE-M can perform the reduction of illumination changes in the sequence using the method of McManus et al. [34]. However, the illumination invariance is turned off by default in the OpenABLE implementation. As illumination changes in building interiors are limited, comparing it to outdoor scenes, we have decided to let this option be turned off, to make the processing faster.

The next step in the algorithm is the matching phase, in which the distance matrix \(\mathbf {D} = \{d_{i,j}\}\) between positions registered in the sequences train and test is computed. As the train sequence contains n global image descriptors, and the test sequence contains m descriptors, the matrix size is \((n-c_l + 1)\times (m-c_l + 1)\):where \(c_l\) is the length of the sub-sequence used for matching (in [28] it was denoted compareLength and in [24] \(d_{length}\)). The function \(\mathrm{hamming}(x,y)\) computes the Hamming distance between the descriptors of the sequences denoted as x and y. Finally, the resulting distance matrix \(\mathbf {D}\) is normalized. The notation \(train[i,i+c_l-1]\) represents the concatenation of descriptors from i-th to \((i+c_l-1)\)-th frame of the train sequence. The processing of the algorithm is presented with blue color in Fig. 2.

The computational complexity of the baseline algorithm (ABLE-M) is equal to \(\mathcal {O}(n m c_l)\), as for each image in the recognition sequence (m) we slide the window n times and compare the sub-sequences in \(c_l\) operations.

The original ABLE-M algorithm compares two sequences of images to determine if loop closure has occurred. The value in the distance matrix in the i-th row and j-th column corresponds to the distance computed between the sub-sequence from i-th to \((i+c_l-1)\)-th frame in the training sequence, and the sub-sequence from j-th to \((j+c_l-1)\)-th frame in the testing sequence. The \(c_l\) parameter has to be chosen depending on the environment characteristics. Originally, the distance matrix is normalized after the whole testing sequence was processed and the places are marked as recognized if the value at the (i, j)-th position in the matrix is lower than the recognition threshold \(t_r\), set prior to operation. The \(t_r\) value is the second parameter that requires tuning depending on the environment. Both of parameters, \(c_l\) and \(t_r\), are set experimentally and no formal learning phase is performed.

The choice of \(c_l\) greatly impacts the performance of the algorithm. Longer comparison windows make the system more robust, as larger parts of the training and testing trajectories have to match to achieve a recognition from the system. Unfortunately, longer windows also require the user to walk longer along the same trajectory as the one recorded in training sequences, making the localization system impractical, whenever multiple crossroads are located next to each other. Also, the OpenABLE system becomes more vulnerable to changes in the walking speed of the user, as longer trajectories have to match each other. Shorter comparison windows, on the other hand, reduce the recognition capabilities of the OpenABLE system, as less information is used for comparison, which makes the system susceptible to local self-similarities.

Another problem with the practical application of OpenABLE for personal localization is the large number of recognitions we usually obtain in our target environments. If the testing sequence contains a long trajectory recorded along the same path as the training sequence, the system yields a large number of positive recognitions, as the query sub-sequence of images can be successfully matched against multiple overlapping sub-sequences in the training sequence. The value at (i, j) position in the distance matrix is usually similar to the value in \((i+1,j+1)\) position in the same matrix. This can be observed especially with larger values of the window size \(c_l\), as a large portion of the computed distance is the same in both of those cases. The large number of recognitions in the same place inflates the statistics of positive matches, but yet does not introduce a novel information about user location.

Therefore, we propose to cluster the positive recognitions obtained from OpenABLE to achieve a reasonable number of distinct recognitions and the full processing scheme is presented in Fig. 2. In our implementation, we use DBScan [35], which is an unsupervised clustering algorithm that does not require a priori information about the expected number of clusters. In our modification of OpenABLE, the DBScan algorithm clusters two-dimensional elements of the distance matrix \(\mathbf{D}\) to select parts of the sequence where the algorithm correctly recognized user position. If both \(\mathbf{D}(i,j)\) and \(\mathbf{D}(k,l)\) exceed the recognition threshold \(t_r\), then those elements are clustered according to the Euclidean norm:which directly considers the indices of the distance matrix elements. The norm (4) is computed using integer indices, because the actual distances between the recognized locations are unknown, and they are irrelevant for appearance-based localization. We assume that the user walks with approximately constant speed over the recognized trajectory pieces. Considering that the images are acquired with a constant frequency set on the mobile device, we can conclude that the distances between the neighboring recognized locations are approximately constant. Therefore, the indices of the recognized locations provide reasonable estimates of the (unobservable) metric distances, and we can safely cluster the recognitions that are close to each other using this approach. The metrics given by (4) will not work if the approximately constant speed motion assumption does not hold anymore, e.g. if the user starts to run. However, the original OpenFABMAP is also not prepared to perform recognitions in such situations.

The clustering algorithm is tuned according to two parameters—the maximum distance \(db_\mathrm{eps}\) that allows adding a new point to the cluster, and the minimal number of points to form a cluster (\(db_\mathrm{min\_pts}\)). The \(db_\mathrm{eps}\) was set to 2, and \(db_\mathrm{min\_pts}\) was equal to 1. To ease the comparison with FAB-MAP, each cluster is represented by the average indices of the cluster members to verify the correctness of the recognitions belonging to the cluster.

The experiments were conducted at Poznan University of Technology (PUT) in two buildings of quite a different topology. The PUT Lecturing Centre (PUT LC) is a modern style building with many open spaces that are illuminated by sunlight coming trough multiple glass panels in the walls. The PUT Mechatronic Centre (PUT MC) is a building of the more classic structure, with many similar corridors. As the existing windows do not provide enough sunlight, artificial light is commonly used.

The first test inside the PUT LC building consisted of a single trajectory around the main lecturing hall. During the training phase, 6 positions with images taken in both directions were produced for FAB-MAP, and two sequences in both directions containing 458 and 438 images respectively were registered for ABLE-M. In Fig. 3 the FAB-MAP training places are marked as blue rectangles, whereas the ABLE-M training sequences are marked by a line of green dots. Additionally, the training data were augmented with 5 images for FAB-MAP and a sequence of 410 images for ABLE-M taken in the new PUT Library, which is a different building of a very similar structure to the PUT LC building. The purpose of adding images from an outside of the experimental sites was to make tests more challenging and check if systems are capable of discriminating different sites.

After the training phase, the performance evaluation of the OpenFABMAP and OpenABLE systems was accomplished on two test sequences acquired in the same environment: PUT LC test and PUT LC test 2. The user was asked to walk roughly along the trajectory marked by the green dots in Fig. 3. The PUT LC test sequence consists of 466 images, and the PUT LC test 2 sequence contains 448 images.

The structure of PUT MC results in multiple junctions, and therefore the ABLE-M learning trajectories can either map all available paths, or they can consist of disjointed trajectories not covering the junctions. We have chosen the latter option and divided PUT MC into 4 trajectories containing 1256 images altogether, as presented by the green dots in Fig. 4. For the training purposes of FAB-MAP 17 places were chosen, that are marked by blue rectangles in Fig. 4. The final training data set for FAB-MAP was augmented by images of 5 places from another floor of the same building, whereas the ABLE-M training data additionally included one sequence of 274 images from that floor.

Because PUT MC contains multiple corridors, we decided to have two different test trajectories, PUT MC short and PUT MC long, recorded on the third floor. The trajectories are presented in Fig. 5 by green dots (PUT MC short) and by red dots (PUT MC long). Both trajectories started and ended in a place marked by ’S’ in Fig. 5, while the direction of motion is marked by an arrow. The shorter trajectory is equal to approximately 60 metres and contains 620 images, while the longer trajectory is approximately 120 metres long with 996 images. Taking into account the choice of training places, 10 FAB-MAP test locations are put along the PUT MC short trajectory, and 15 test locations are put along the PUT MC long trajectory.

To verify the robustness of the evaluated place recognition systems in populated environments, we additionally recorded two sequences with people (individual or in groups) appearing at random in the same corridors. These sequences were registered during a break between classes when many students stay at the corridors or they wait at the doors of the classrooms. The PUT MC people short consists of 525 images, and in the PUT MC people long 864 images were recorded.

The FAB-MAP algorithm needs a pre-training and training process. For the pre-training we used a separate set of images that were collected in the same environment and were not overlapping with the database of known places used for training. As it comes to the parameters of the modified OpenFABMAP, they need to be adjusted before the system can be applied in real-life operation. The PUT LC test and PUT MC short were chosen for the initial validation and the results of system testing are presented in Table 1. As already mentioned, setting the sequence size n to 1 results in incorrect recognitions even if the recognition threshold \(t_p\) is set to 0.99. As any incorrect recognition may be critical for indoor localization [38], these results strongly suggest that OpenFABMAP in the original version was incapable of operation in the target environment. Increasing \(c_w\) allows to suppress the number of incorrect recognitions to 0, but might also lower the number of correct recognitions as the system needs to properly match several images in a sequence. Therefore, the window size of 3 or 5 is the best choice in our case. As performing recognition on several images is more descriptive, it is possible to lower \(t_p\) increasing the number of correct recognitions without any additional incorrect matches.

The parameters found in the previous analysis were used on datasets PUT LC test 2 and PUT MC long, and the datasets with people moving inside corridors PUT MC people long and PUT MC people short. The results confirm that the proper choice of windows size \(c_w\) usually allows minimizing the number of incorrect matches. In some cases, the characteristic of the environment contains multiple, misleading features making recognition a challenging task. Such case is presented in Fig. 6a as multiple features are visible on windows, misleading the FAB-MAP. Similarly, the people present in the corridors make it difficult to correctly recognize the places. Such situation is presented in Fig. 6b and Table 2.

The OpenABLE results depend on the choice of two parameters. The first one, \(c_l\) denotes the number of frames used when comparing sequences whereas the second \(t_r\) is the recognition threshold in the normalized distance matrix. The authors of OpenABLE do not provide any procedure for setting those parameters, and therefore we perform an experimental evaluation for different settings on PUT LC test dataset. The most significant results are presented in Table 3 containing tests for \(c_l\) ranging from 2 to 40 images and two values of \(t_r\). For the convenience of the readers, we only provide the clustered recognized places, which is a more intuitive performance measure than the total number of positive results from OpenABLE.

The OpenABLE algorithm was at first tested with \(t_r\) set to 0.4 and different sizes of \(c_l\). For small window sizes, likes 2 or 10, the algorithm recognizes more incorrect than correct places but even for \(c_l\) equal to 2 the number of positive hits from OpenABLE (16936) exceeds the number of incorrect recognitions (10962). The poor performance can be attributed to the fact that OpenABLE extracts not enough information from individual images, as those images are reduced in size and described by a global descriptor. The strength of the algorithm lies in exploring the sequences of images. For greater \(c_l\) the system produces much fewer false positives, but a long recognition window also negatively affects the number of positive recognitions, as longer sequences have to match in order to obtain a correct place recognition.

Similar results can be also obtained for \(t_r\) set to 0.3. In this case, OpenABLE achieves fewer incorrect matches due to the more strict \(t_r\) threshold. Regardless of the choice of \(t_r\) (0.3 or 0.4), the OpenABLE produces zero incorrect recognitions when the comparison window \(c_l\) is set to 40. The sequence of 40 images in our case corresponds to the operation for approximately 5 s. From our experience, the value of \(t_r\) is influenced by the structure of images and usually is hard to tune for sequences containing different parts of the building and the value of \(c_l\) should be chosen based on the similarity of places in the dataset. For example, if the database consists of several similar corridors, it is usually better to increase \(c_l\). From the first experiment, we assumed \(c_l\) to be 40 and \(t_r\) of 0.4 and wanted to verify the performance inside the building with a different structure. The choice of those parameters was also evaluated on PUT LC test 2. The system correctly recognized 6 places on the trajectory with 4529 positive recognitions from OpenABLE. Moreover, the system presented no false positives.

The PUT MC has a different structure than PUT LC and therefore the parameters of OpenABLE have to take into account those differences. The results obtained on PUT MC short, PUT MC long and the sequences with people being present in the field of view are shown in Table 4.

Setting the \(c_l\) results in almost every case in some incorrectly recognized places. Even if there are no incorrectly recognized places for \(c_l\) equal to 40, small change in \(t_r\) from 0.4 to 0.5 results in significant increase of incorrect recognitions, which can be observed for PUT MC short and PUT MC long. As corridors are hard to distinguish even for humans, the window size \(c_l\) was extended as shorter sequences might not provide sufficient information for place recognitions. This is necessary as building structure contains similar corridors, like those presented in Fig. 7a. Increasing \(c_l\) to 80 images corresponds to the 8 s of motion.

Another important aspect of real-life operation is the influence of people on recognition. Therefore, we recorded and can compare the same trajectories with and without people occluding the view from the camera. In both cases, PUT MC people short and PUT MC people long, there were no incorrect recognitions when \(c_l\) was set to 60. Compared to sequences without people, the system recognizes fewer different places. This is normal as people can occlude a significant part of the images changing the properties of images for comparison. Therefore, larger values of \(c_l\) might result in more robust recognition in the case of small disturbances, like a single person in the field of view, but even very long windows are inefficient in a crowded scene. Nevertheless, OpenABLE exhibits impressive performance correctly recognizing places even in such situations as the one presented in Fig. 7b.

The initial experiments proved that OpenFABMAP and OpenABLE can be successfully used in indoor environments. Nevertheless, the obtained results cannot be simply compared with respect to the number of correct and incorrect recognitions, due to the conceptual differences between the FAB-MAP and ABLE-M algorithms. Therefore, we present the results on shared figures that allow to visually compare the achieved recognitions and to draw conclusions about the algorithms. In each case, we present the best results for parameter settings that yielded no incorrect place recognitions.

In Fig. 8 we present the results obtained on PUT LC test 2 sequence. It can be observed that the OpenFABMAP correctly recognized all of the places along the test trajectory. The OpenABLE failed to achieve recognitions in the middle part of the trajectory but provided continuous localization in the beginning and the end of the sequence. Depending on the application, both systems provided valuable information for the localization purposes.

In Fig. 9 we present the results obtained for the PUT MC long sequence. The OpenFABMAP managed to correctly recognize user location on 10 out of 15 possible places along the trajectory. The OpenABLE recognized the user in 7 parts of the trajectory, but some of those parts are equal to several seconds providing the system with continuous user localization. The main difference between algorithms is visible close to junctions—OpenABLE cannot recognize user on those locations, while OpenFABMAP works correctly. This suggests that these solutions are suitable for buildings of different structure or might be combined in a robust visual place recognition system.

One of the main challenges of visual place recognition is the presence of people in front of the camera. Therefore, in Fig. 10 we present the results obtained along the same trajectory as PUT MC long, but during the student break with many people walking along the corridors. In such conditions, the OpenFABMAP recognized the user in 7 out of 15 possible places along the trajectory. The OpenABLE recognized the user in 7 parts of the trajectory, but the recognized parts were shorter when compared to the recognition results obtained when the people were not present. Both systems correctly recognized the images of re-visited places if the presence od people only slightly disturbed the original view of the scene. Therefore, in many cases, the OpenFABMAP was able to correctly recognize a place based on images taken when people just passed by, which was not possible to OpenABLE. On the other hand, OpenABLE required a longer sequence of similar images for successful recognition but was more robust to small, but continuous disturbance introduced by the presence of people, which led to some surprisingly correct recognitions, as presented in Fig. 7b. Neither of the algorithms provided incorrect recognitions due to the people obscuring the field of view.

The most important modification in the FastABLE implementation aims at significantly increasing the speed of the matching phase and therefore increasing the related energy efficiency [11]. Although ABLE-M can employ the FLANN library [41] for fast nearest neighbor search [24], this is an approximate technique, which improves processing time mainly for very long sequences and is not implemented in OpenABLE. Thus, we propose a purely algorithmic modification, that enables the use of our system for real-time indoor localization on mobile devices. To introduce the idea, we analyze the steps taken during processing in ABLE-M (Fig. 16).

In ABLE-M and the OpenABLE implementation, after a new image is captured, the window of descriptors computed on the last \(c_l\) images is moved along the pre-recorded sequence and the corresponding Hamming distances are computed. The distance computations between the same pairs of global descriptors in the database sequence and the sliding window are repeated. This can be observed in Fig. 16, as for example the distance between the descriptors B and 2 is computed in iteration 1 step 1, and in iteration 2 step 2.

In contrary, in FastABLE we maximally re-use the information already computed. In the first iteration, the corresponding distances are computed and saved in an auxiliary array prev. In the next iterations, we compute the distance for the first step the same way as in OpenABLE. However, in the following \(n-1\) steps it is possible to use the previously stored distance values. The distance d for the iteration \(j+1\) and the \((i+1)\)-th step is computed as:where the sequence frames are indexed from 1. The idea is to compute the current distance as the result of the previous iteration reduced by a distance for the first element in the previous comparison, but increased by a distance for the last element in the current sliding window. As we manipulate integer Hamming distances, no residual errors accumulate due to the computations, and the results are numerically identical with those obtained from OpenABLE. In Fig. 16 the distance from the second step in second iteration, \(d_{2,2}\), is the distance between substring \(\{B,C,D\}\) from pre-recorded sequence and substring \(\{2,3,4\}\) from the query sequence. Distance \(d_{2,2}\) according to FastABLE is computed by taking the distance \(d_{1,1}\) (distance between substring \(\{A,B,C\}\) and substring\(\{1,2,3\}\)), subtracting the distance between A and 1 and increasing the result by the distance between D and 4. Each new distance updates the array prev, so that in the next iteration it is possible to re-use the previous results.

The computational complexity of FastABLE is equal to \(\mathcal {O}(n m)\), as we perform computations for each new image in the recognition sequence (m), and we slide the window n times, but the comparison is performed in constant time (\(\mathcal {O}(1))\). Therefore, it is evident that the complexity of the modified algorithm became independent of the length of the comparison window \(c_l\), comparing it to the \(\mathcal {O}(n m c_l)\) complexity of OpenABLE. The computations are done at an increased memory cost to store the distances computed in the previous iteration.

The proposed algorithm was implemented and is available on GitHub in a version for PC⁴, and in a version for Android devices.⁵

We started analyzing the FastABLE performance from a test that verified how much the FastABLE algorithm execution time depends on the length of the used image sequences: the database size, and the query sequence length, which, assuming a constant frame rate of the camera, is proportional to the distance covered by the user. We performed an experiment for an arbitrarily chosen window length \(c_l\)=20, and increasing lengths of the training database and the query sequence (Fig. 17). For real-life scenarios, the window \(c_l\) is usually much shorter than the length of the query sequence, and therefore we present results for query sequences of length from 500 to 2000 frames. From Fig. 17 it is evident that the speed improvement of FastABLE over OpenABLE is almost the same for different lengths of the query sequence. Small differences are attributed to the non-deterministic execution time of the multi-thread application. Considering these results, we assume the query sequence of 1000 frames for all further experiments.

Next, the FastABLE performance was evaluated by comparing the processing time for different \(c_l\) lengths, and different lengths of the database sequence.

Results presented in Fig. 18 prove that the size of the sliding window \(c_l\) does not have an influence on the processing time anymore. Moreover, the obtained total processing times are much smaller than the times required to process the same data by OpenABLE. The maximum processing time took by FastABLE for a database of 4000 frames with \(c_l\) = 80 is below 24 ms, whereas OpenABLE needed 832 ms to accomplish the same task. Table 6 shows how many times faster is FastABLE with respect to OpenABLE for several database sizes and \(c_l\) values. Gains due to the improved algorithm are especially evident for longer comparison windows.

Similarly to the previous analysis, we can determine the maximal number of frames that can be processed in real-time. As FastABLE can work in real-time on a smartphone, we present those results with respect to the CPU usage, assuming that images from the smartphone’s camera are taken at 10 Hz, which simulates a realistic scenario for localization. The results obtained for SGN3 are presented in Fig. 19.

The FastABLE on SGN3 can easily work in the background for small database sizes or can process huge databases at the cost of high CPU usage. Similar results are obtained for the LS8-50 device (Fig. 20). As we consider a mobile device application, we recommend recording short databases and keeping the CPU usage low, to avoid a negative influence on battery life.

The possible gains of FastABLE were also evaluated on the long Nordland dataset. We wanted to compare the FastABLE matching time with the OpenABLE implementation. The experiments were conducted for a query sequence containing 1000 frames, and are presented in Table 7. In this experiment, FastABLE proved to be at least 100 times faster than the OpenABLE implementation regardless of the length of the database sequence.

When considering the PC version, FastABLE is even faster than the reference implementation of ABLE-M with the multi-probe LSH presented in [24], as for a database of 100,000 images FastABLE performs a single matching in 205 ms, while ABLE-M with LSH requires 420 ms, as stated in [24]. Moreover, FastABLE provides exact results, whereas the LSH version returns only an approximation. It should be noted, that the FastABLE results were obtained on a slower PC than the results presented in [24]. When it comes to mobile devices, the FastABLE algorithm significantly speeds up the processing, but appearance-based localization still cannot be accomplished in real-time for huge databases, e.g. containing images from several multi-floor buildings. Therefore, we recommend to use FastABLE and additionally divide a huge database into smaller sequences utilizing prior information from other sources [39].

The FastABLE parameters \(t_r\) and \(c_l\) can be set manually to maximize the number of correct recognitions without false positives, but we propose to automatize this process. The parameter \(c_l\) should be large enough to ensure robustness to self-similarity of the environment, but cannot exceed the length of the shortest sequence used as query. Due to crossings inside the building, the pre-recorded video inside building consists of p non-overlapping sequences. Knowing the value of \(c_l\) we match each of those sequences against the remaining \(p-1\) pre-recorded sequences to find the minimal Hamming distance between the corresponding sub-sequences. As neither of the p parts overlap, no recognitions should be found, and \(t_r\) is computed individually for the a-th sequence:where \(t_r^a\) is the distance threshold found for \(train_a\), which is part a of the training sequence. This solution sets different thresholds for different parts of the database, as different areas in the environment can differ significantly in their appearance.

To verify the feasibility of FastABLE for indoor localization on mobile devices, we performed experiments on the first floor of the PUT MC building. The pre-recorded data consisted of 14 sequences recorded on non-overlapping paths in both directions of motion. The database amounted to 2127 images, while the query trajectory consisted of 320 images (Fig. 21). FastABLE reported 5625 correct place recognitions localizing the user on over a half of the trajectory, only with the camera images. FastABLE returned 7 incorrect recognitions informing about localization in another part of the building that could be further removed by checking the consistency of localizations. The results were obtained with automatically set parameters (\(c_l\),\(t_r\)), and could be further improved by manual tuning for the specific environment.

The same query sequence was processed by the OpenFABMAP implementation of the FAB-MAP algorithm with minor modifications (as presented in Sect. 2). OpenFABMAP correctly recognized user locations at 6 places along the path from 30 training places (Fig. 22), but provided only sparse location information that might not be suitable for some applications.