Improving environment detection by behavior association for context-adaptive navigation

3.1 Features selection and classification

In Gao and Groves,³⁰ different time-domain and frequency-domain features were extracted from sensor measurements. They are summarized in Table 1. Time-domain features describe temporal variations of the motions during the sliding window, including range, variance, skewness, and kurtosis extracted from all sensors. In addition, the zero-crossing rate (ZCR) has also been extracted from the accelerometer signals and is used to differentiate the periods of pedestrian activities changing with the time. Frequency-domain features describe the periodic characteristics of motions during the sliding window. Following a fast Fourier transform (FFT), peaks are centered on different frequency values for different behaviors. For this reason, features in the frequency spectrum can capture significant information on the motion periods of different behaviors and vibration frequencies of different vehicles. Using all of the proposed features, the corresponding classification accuracies of the human-vehicle, human activity, and vehicle motion classifiers were 98.9%, 97.6%, and 91.0%, respectively.

A good set of feature measurements can often provide accurate and comprehensive descriptions of patterns from which the differences between behaviors are easily discerned. However, some of the extracted features may be redundant, introducing noise and irrelevant information. This can cause a deterioration of the classification performance. Feature selection techniques are therefore implemented in order to identify the most relevant features for distinguishing different activities. To explore the best combination of features, the sequential forward floating selection (SFFS) algorithm³² is applied in this paper. The SFFS algorithm aims to identify the feature subset that minimize the misclassified samples over all feasible feature subsets to obtain better classification performance.

The SFFS procedures are presented in Figure 3. It initializes with an empty set and consists of two main procedures: a new feature is added into the current feature subset if better classification performance is achieved; a conditional exclusion is then applied to the new feature subset, from which the least significant feature is determined. If the least significant feature is the last one added, the algorithm goes back to select a new feature. Otherwise, the least significant feature is excluded and moved back to the available feature subsets and conditional exclusion is continued. This cycle is repeated until there is no further improvement of classification performance. The main advantage of the SFFS algorithm is that the discarded features can be selected again in the inclusion and exclusion procedures.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 3

Sequential forward floating selection block diagram

The SFFS algorithm was implemented for behavioral recognition, by using the same dataset and the same corresponding machine learning algorithms for each classifier described in Gao and Groves.³⁰ Figure 4 shows the average classification accuracy of the three classifiers as a function of the number of features selected by SFFS. The shadow area in the figure indicates the standard deviation using fivefold cross-validation. The results show that the classification performance of each classifier can be slightly improved from 98.9% (20 features, human-vehicle classifier), 97.6% (21 features, human activity classifier), and 91.0% (31 features, vehicle motion classifier), obtained by using all extracted features, to 99.3% (four features), 97.9% (13 features), and 91.5% (27 features), respectively. After feature selection, the corresponding dimensions of features for each classifier are reduced at the same time.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 4

Feature selection performances for three classifiers

3.2 Connectivity

Behavior connectivity describes the time-domain relationship between the current and previous behavior categories. The direct transitions between some behaviors are more likely than others.¹ The behaviors to determine in this paper cover both pedestrian and vehicle activities. Among them, stationary vehicle behaviors can connect directly to pedestrian behaviors such as sitting or walking. However, pedestrian behavior does not directly connect to moving vehicle behaviors (eg, a moving bus or train) because a vehicle must normally stop to enable a person to get in or out.

Behavioral connectivity is represented in a probabilistic way. Compared with a Boolean approach, there are two advantages. First, a Boolean implementation may occasionally result in the decisions being stuck on incorrect context categories following a faulty selection. This can occur when the correct context category in practice is directly connected to the faulty category determined from the classification algorithm and the other categories are poor matches to the measurement data. Expressing the results in terms of probabilities is a more flexible way to both increase the likelihood of the directly connected categories and minimize the unlikely ones. Second, a probabilistic scheme permits transitions between context categories that are rare, but not impossible. For instance, landing on water directly is possible for amphibious aircraft, but not for most others.

To represent the time-domain relationship in quantity, the likelihoods of direct connections between behaviors are listed in the connectivity matrix in Table 2, where the permitted direct connections in reality are set to 0.9 and the unlikely connections are set to 0.1. The parameters are well tuned to permit direct connection between behaviors and tolerant faulty outputs from machine learning algorithms at the same time.

Figure 5 shows the behavior connectivity algorithm, comprising the following five steps at each epoch.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 5

Block diagram of behavior connectivity

• 1. A smoothing method is first applied to compute the provisional estimates of behavior probabilities at the current epoch by combining the probabilities z_k output from the machine learning algorithms with the estimates from the last epoch :

  1

  The filter gain, α, was set to 0.5, indicating equal importance of the measurements at the current epoch and the estimates at previous epoch.

• 2. The relationship between current and previous behaviors can then be expressed as a transfer matrix Ω_k, calculated from the estimated probabilities, and :

  2

  where the superscript † refers to the operation of Moore-Penrose pseudoinverse,³³ which satisfies the relationship defined in Equation (3) where matrix I refers to the identity matrix. The calculation procedures were first introduced in Golub and Kahan.³⁴

  3

• 3. After obtaining the transfer matrix, it is reestimated using the connectivity matrix C:

  4

  The notation ∘ in Equation (4) denotes element-wise multiplication, satisfying (Ω ∘ C)_i,j = Ω_i,jC_i,j where the subscript i and j refer to the ith row and jth column of the matrix, respectively.

• 4. Then the likelihoods of the behavioral estimates at current epoch are updated by multiplying the previous behavioral probabilities by the new transfer matrix:

  5

• 5. Finally, the probability of each behavior at current epoch is obtained by rescaling the likelihoods with the following equation:

  6

  where is the probability of behavior i at epoch k.

4.1 Categorization

A good environment categorization for navigation is expected to provide an indication of the positioning techniques applicable for determining position in that environment. For most land navigation applications, locating whether the user is indoor or outdoor is a prerequisite task because indoor and outdoor positionings depends on inherently distinct techniques. In an outdoor environment, GNSS or enhanced GNSS techniques perform well while Wi-Fi positioning or Bluetooth positioning are better options when staying inside a building. In reality, some connection areas between indoor and outdoor environments exist, rendering such scenarios hard to be classified as either indoor or outdoor. Thus, the intermediate category, where a client is adjacent to a building or in a partially enclosed environment, is included as one of the categories. In an intermediate environment, indoor positioning techniques (eg, Wi-Fi and Bluetooth) can still work well, while direct LOS GNSS reception can be limited. Note that the occurrence of intermediate scenarios is quite rare for vehicles, so this category is ignored when the subject is identified as a vehicle. Typical examples of each environment category for both pedestrian and vehicle are summarized in Figure 6.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 6

Examples of different environment categories

GNSS signals are used for environment detection in this study for two reasons. First, among smartphone sensors, the availability and quality of satellite signals tend to be less affected by factors other than the environment type. For example, Wi-Fi, Bluetooth, and cellular signals strongly rely on the allocation density of the broadcasting station. Their signal strengths also depend on the distance away from the stations, whereas GNSS signal strengths are roughly constant across Earth’s surface. Second, the globally distributed properties of GPS and GLONASS ensure that we can infer environments from the availability and strength of GNSS signals anywhere on Earth. The full development of Galileo and Beidou Systems in the future would further enhance the detection performance. The main drawback of GNSS is its relatively high power consumption when being constantly updated. As the research advances, other sensors could be added into the context-determination framework to improve the environment detection using the GNSS module.

4.2 Features for environment detection

In an indoor environment, most GNSS signals are attenuated by the structure of the building or received by non– line-of-sight (NLOS) paths, rendering them weaker (or unavailable) indoors compared with intermediate and outdoor environments. Thus, features comprising the total number of satellites received and the total measured carrier-power-to-noise-density ratio (C/N₀) summed across all satellites received at each epoch are extracted.

To show the effectiveness of the proposed features, a set of GNSS measurements was collected on the Pixel I smartphone. The person holding the smartphone kept walking from an outdoor into an indoor environment. The transition happened at about the 30th second. Figure 7 demonstrates the differences in availability and strength of GNSS signals in the indoor and outdoor environments, respectively. The number of satellites received decreased gradually after moving indoors, as more satellite signals were blocked by the building. Concerning the C/N₀ outputs from the selected three satellites, a drop of about 5 dB-Hz was observed when the person was nearing the building, followed by a sharp decrease when they entered. It was also noted that most of the satellite signals indoors were weaker than 20 dB-Hz and more satellites lost track after 80 seconds as the person moved further deeper indoors.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 7

Number of satellites received (left) and selected C/N₀ values (right) during an indoor-outdoor transition

However, on the basis of the findings in Radu et al²² and Gao and Groves,³⁰ these two features are not sufficient for a reliable indoor/outdoor classification. In particular, it is difficult to distinguish “shallow indoor” and “deep urban” scenarios from each other with only these two features. More environmental features are therefore required.

As investigated in Gao and Groves,³⁰ the feature comprising the total C/N₀ values summed across the satellite signals above 25 dB-Hz was proven to be more useful rather than the single summed C/N₀ values used alone in indoor/outdoor classification for a pedestrian. Therefore, in addition to the two features described above, it is adopted as a third feature for pedestrian-based environment classification, denoted as sumCNR₂₅. The similar feature metric optimized for vehicle context will be discussed in Section 5.2.

4.3 Probabilistic support vector machine

The SVM is a supervised classification algorithm derived from statistical learning theory and kernel-based methods.^35,36 The significant property of the SVM is that it does not depend on any prior probabilities and can offer accurate results with small training samples in the nonlinear classification problem. Given the training samples with corresponding target labels (y_i∈{−1, +1}), the SVM can construct a classification hyperplane in high-dimensional feature space that maximizes the margin between two classes and minimizes the error.

Suppose f (t_k) is the output of the SVM that measures the distance between the test sample t_k and the hyperplane. Platt³⁷ proposed an approach to obtain the classification probability by fitting the SVM output with a sigmoid function:

7

In this equation, y_k is the predictive label of t_k. The scalar parameters A and B of Equation (7) are learned using maximum likelihood estimation from the training data and their corresponding target values. It is worth noting that the training set can be but does not have to be the same set as used for training the SVM.³⁸

Fundamentally, the SVM is a binary classifier. This is sufficient to classify two vehicle environment categories (indoor and outdoor). To extend the method for pedestrian environment classification situations with three environment categories, three binary classifiers can be trained. Each SVM classifier will output a pair of probabilities to distinguish every two of the three environment categories. For multiclass application, the probability of each category can be obtained by taking account of all pairs of probabilities. Using Platt’s method for each SVM, these pairwise probabilities are combined into posterior probabilities by adopting the method proposed in Price et al³⁹ as

8

where S_i (i = 1, …, L) denotes the ith environment context in this research and there are L = 3 environmental contexts for pedestrian cases.

4.4 Hidden Markov model

An HMM is a time-sequential pattern recognition algorithm, which assumes a Markov process⁴⁰ with the states (indoor, intermediate, or outdoor environment) in this study. A first-order Markov process predicts the future states of a process relying only on the present state, not on the sequence of events that preceded it, so it is capable of modeling the process of a device moving from one environment to another according to observations. Within an HMM, the probabilities that the system is in each of the states are estimated, so that the navigation system knows the certainty of the decision.

Figure 8 is an illustration of a first-order HMM, where Z_k refers to the environments to determine at epoch k and t_k is the test sample that is also called observation in the context of HMM. Given the sequence of the observations, the most likely sequence of the contexts can be inferred using the Viterbi algorithm,^36,40 from which the probabilities of each context at each epoch are estimated.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 8

Structure of a first-order hidden Markov model

To construct an HMM, the essential parameters of the model are determined as follows.

The initial state probability distribution defines the probabilities of the states being at the first epoch. Clearly, the indoor and outdoor contexts occur much more frequently than the intermediate context. As there is no prior information about the initial state, when there is insufficient information to correctly determine the context, it is better to select the intermediate context than to incorrectly select the indoor or outdoor context. The initial probabilities were therefore set as follows:

9

where S₁, S₂, and S₃ denote three hidden states indoor, intermediate, and outdoor, respectively.

Each element of the state transition probabilities matrix A defines the probability that a state S_i at the immediately prior epoch transits to another state S_j at the current epoch. Since the sample interval here is 1 second, when a user was previously indoors, the current state is highly likely to be indoor and might be intermediate, but is not likely to be outdoor. This is because the user rarely moves directly from indoors to a fully outdoor GNSS reception environment. However, when the user is at the intermediate state, he/she can move directly to either of the other states. On the basis of these assumptions and with reference to the parameters applied in indoor-outdoor detection,^21,24 the values of the transition probability were as listed in Table 3. Note that the values are selected in order to obtain an experimental balance between responsiveness to change and vulnerability to noise.

The emission probabilities describe the conditional distributions of getting an observation from different states. In this paper, the emission probabilities are constructed from the SVM probabilistic outputs. Given the test samples t_k, the emission probability of the HMM can be transformed from P (S_i|t_k) of SVM in Equation (8) by using Bayes’ rule:

10

where P (S_i) is the prior probability of the class. Their values are set the same as the initial probabilities in Equation (9). In the practical implementation, the prior probability can be obtained from the distribution of the scenarios.

5.1 Transition probability of HMM

The transition matrix A₀ given by Table 3 is proposed for general cases without considering the behaviors of the users. In reality, a stationary user will stay in the same environment, making it impossible to transit from one to another. This inspires an update to the transition probability with the probability of conducting static behaviors. The modification of transition matrix based on static behavior recognition results is expressed in Equation (11).

11

where I is the identity matrix and p_stat denotes the detected probability of being stationary for both a pedestrian and vehicle.

The updated transition probabilities are linear combinations of the identity matrix that represents no change in environment and the parameters proposed for general situations, according to the probability of static behaviors. If the user is stationary (p_stat = 1), the transition matrix will be equal to the identity matrix, indicating an unchanged environment; if the user is detected to be moving (p_stat = 0), the transition probabilities for general cases will be used in HMM.

5.2 Pedestrian/vehicle association

When a smartphone is put inside a vehicle, the GNSS signals are received by passing through the vehicles’ metal shell and windows, which makes the signal strengths different inside a vehicle than on a pedestrian. Figure 9 shows the normalized distributions of GNSS C/N₀ inside a vehicle and on a pedestrian under indoor scenarios. The measurements were both collected at static positions for about 10 minutes on a Google Pixel I smartphone at London Paddington train station. The two collection sites were about 1 m away from each other, so they can be treated as similar indoor scenarios. The pedestrian data were collected about 2 minutes after collecting the vehicle data.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 9

Comparison of vehicle and pedestrian indoor data (both data were collected at London Paddington train station, the vehicle data were collected inside a Heathrow Express train, and the pedestrian data were collected standing close to the train, about 1 m away from the inside point)

Since the two sets of data were not collected at the same time, the positions of the satellites changed during the short time interval. Thus, the GNSS C/N₀ distributions of all satellites are plotted to show different GNSS reception conditions rather than the C/N₀ values of individual satellites. It can be seen that the average signal strength of the vehicle data is about 5 to 10 dB-Hz weaker than the corresponding pedestrian value as a result of attenuation by the vehicle’s shell. Therefore, for environment detection based on the signal strength, different environment classification models should be implemented for vehicles and pedestrians.

We also consider the application of a similar metric for vehicular environment classification. Meanwhile, because of the greater signal attenuation inside vehicles, we revised the sumCNR₂₅ feature for vehicle contexts by finding suitable C/N₀ cut-off thresholds optimized for vehicles. In order to determine the threshold giving the best classification performance, features with different cut-off thresholds were tested by the vehicle dataset that will be described in Section 6.1. A fivefold cross-validation strategy was applied to train and test the classifier using the vehicle dataset. Using this strategy, the dataset is randomly divided into five equally sized folders. Each time, four of them are used as training sets while the remaining one is used as a test set. This procedure is repeated five times to ensure that all of the samples are used equally in testing, while maintaining independence of training and testing data for model learning.

The three input features to the SVM are the total C/N₀ values summed across the satellite signals above different thresholds, along with the total number of received satellites and total signal strength of the GNSS signals. The classification performance obtained with different thresholds is shown in Table 4. The feature “total C/N₀ values summed across the satellite signals above 30 dB-Hz” shows better performance than others and is thus selected for vehicle-based environment classification. It is denoted as sumCNR₃₀. A summary of the features for both pedestrian and vehicle-based environment classification is presented in Table 5.

The HMM parameters in Section 4.4 are proposed for pedestrian situations with three categories; thus, the corresponding modifications should be made for vehicular environment classification because of the change in the categorization. The corresponding initial and transition probabilities are adjusted for vehicle situations in the following Equation (12) and Table 6, respectively. The initial probabilities are set equal for indoor and outdoor contexts. The transition probabilities in Table 6 are obtained by keeping the same values in Table 3 of indoor or outdoor environment connecting to the same context and the same values of transiting to another context. The emission probabilities of the HMM for vehicle context can still be obtained from the probabilistic classification results of a binary SVM classifier as in Equation (10).

12

6.1 Environment training dataset

The environment dataset was collected using a Google Pixel I smartphone running Android GNSS logging applications. Both GPS and GLONASS data were logged at 1 Hz. GNSS measurements, comprising time tags, PRN (pseudorandom number) of the satellites, the C/N₀ measurements, satellite azimuths, and elevations can all be logged in files for processing.

The training dataset consists of both the pedestrian and vehicle data to construct the classification models. The pedestrian part was collected by the data collector holding the smartphone in hand. The others were collected inside the vehicle, putting the smartphone on the seats of the buses or on the table of the trains. Table 7 summarizes the dataset that covers different kinds of scenarios in indoor, intermediate, and outdoor environments. Note that all the pedestrian environmental data were collected statically.

6.2 Pedestrian experiments

To test the environment detection ability under different GNSS reception conditions, the proposed environment detection methods were examined under four different scenarios. Each scenario was conducted for 20 minutes. They are shown in Figure 10. Among two outdoor scenarios, Scenario One is an open-sky park while Scenario Two is a typical traditional European area with narrow streets and buildings packed closely together. It is important to note that all the data collections in this section were conducted in January 2018. Thus, the time between training dataset and the test data was at least longer than half a year, allowing the satellite positions to change significantly. Therefore, all the collected test data are independent of the training dataset. During the data collection, the experimenter was allowed to hold the smartphone and behave as normal within the experimental area, such as walking, running, waiting for traffic, and standing to take photos.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 10

Pedestrian experiment sites

A GMM-HMM (GMM, Gaussian mixture model) environment detection approach was proposed in Gao and Groves,²⁴ where emission probabilities were modeled by a mixture of Gaussian distributions on the basis of the fitting database. To access the performance, the classification results of GMM-HMM, SVM alone, and SVM-HMM with and without association (whether adopting the static/nonstatic strategy) are presented and compared in Table 8.

First, comparing SVM alone results with those smoothed by HMM, it can be seen that a substantial improvement in detecting indoor and outdoor environments is achieved. It is more obvious for the second and fourth scenarios in urban and indoor environments, where the classification accuracy was improved from 87.25% to 96.5% and from 81.58% to 100%, respectively. This shows that the consideration of the time-sequential relationships between environments can improve context detection. Second, comparing SVM-HMM classification results with and without association in Table 8, the accuracy of context detection in open-sky, intermediate, and indoor environments improved while the correct detected samples decreased a little in urban areas. This finding suggests that the adjustment of transition probabilities with stationary probability does not always improve the environment detection, depending on the situation. When the estimation of the previous epoch is correct, the adjustment is helpful; otherwise, it is not. Third, for the indoor and outdoor classification tasks, the proposed SVM-HMM method with association mechanisms all perform better than the GMM-HMM approach. This third result implies that using SVM to model the emission probability of HMM is more accurate than fitting from the empirical dataset.

From Table 8, it is also noticed that some contexts are more difficult to distinguish than others. The urban environment in Scenario Two is harder to detect than the open-sky environment in Scenario One, although these two scenarios are both outdoor areas. The classification performances of Scenario Three are poor for all approaches, showing the intermediate context is far more difficult to distinguish than indoor and outdoor contexts. One possible reason is that the awning is made of conventional glass that is transparent to GNSS signals. This means that a high proportion of the samples were misclassified to the outdoor environment.

6.3 Vehicle experiment

To assess and compare the performance of different approaches on a vehicle, a practical test was conducted on a bus. The user holding the smartphone was seated inside the bus. At the same time, the sensor measurements for both behavior and environment detection were recorded for postprocessing. The bus traveled along South Colonnade Street in the Canary Wharf district of London and stopped at the bus station under the bridge for about 20 seconds, as shown in Figure 11. This route was designed to incorporate both indoor and outdoor environments, as well as moving and stationary vehicle motions.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 11

An aerial view of the bus route (satellite image from Google Earth)

The context detection results are shown in Figure 12. Figure 12A shows the behavior recognition results where the effectiveness of connectivity can be identified. Comparing the decisions from the RVM with ground truth, some of the samples were misclassified. However, they were corrected after behavioral connectivity, showing that the proposed connectivity mechanism can improve the performance of behavior recognition. The connectivity mechanism is effective when the unlikely connections appear in the detection results. However, for some behavioral connections, such as from walking to taking the bus, the advantage of connectivity cannot stand out since all behaviors can be connected directly. The selection of a 4-second window length for feature selection resulted in about a 3-second time delay in the behavior recognition, as the extracted features contained the information in the previous 3 seconds. Although a shorter window length gives shorter detection latency, it would incur degraded classification accuracy at the same time. A good choice of window length needs to balance cautiously between accuracy and latency to meet the requirement of the specific navigation system. Investigations on how to obtain an optimum window length are foreseen for future work.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 12

Performance of vehicle context detection. Note. B, moving buses; T, moving diesel trains; U, moving electric trains; V, stationary vehicles with the engine on; H, human activities

Figure 12B shows the environment detection results. The top figure provides the probabilistic outputs of indoor and outdoor detections of the proposed method, and the bottom lines compare the classification performance of different approaches. In Figure 12B, it can be observed that the behavior-aided SVM determination and SVM-HMM methods are able to recognize most indoor and outdoor contexts on the bus. On the contrary, the GMM-HMM approach failed to detect most outdoor samples especially when the bus traveled into the outdoor environment from indoors. The SVM-HMM method with vehicle features gives slightly better classification accuracy than the one with pedestrian features. This proves that using association to adopt different (vehicle/pedestrian) models in environment detection according to the recognized behavior can improve the performance of environment detection in a vehicle. Meanwhile, it is also observed that the combination of HMM and SVM performs slightly better than the SVM method alone. The optimization of HMM transition probabilities by considering the status of the behaviors may further improve the environment detection accuracy; thus, the SVM-HMM method considering all associations gives the best detection performance among the listed approaches.