CN109031263B - Indoor fingerprint map construction method based on mobile crowd sensing data - Google Patents

Abstract

The invention relates to an indoor fingerprint map construction method based on mobile crowd intelligence sensing data. The invention includes crowd intelligence sensing data collection, closed-loop detection and graph construction, and a graph optimization algorithm based on Graph SLAM. Using mobile users in the environment as sensing units to automatically collect fingerprint data and user trajectories can reduce the survey workload required for fingerprint positioning, and is conducive to the rapid deployment of fingerprint positioning systems in unknown environments.

Description

An indoor fingerprint map construction method based on mobile crowd-sensing data

technical field

The invention relates to the technical field of indoor fingerprint positioning, in particular to an indoor fingerprint map construction method based on mobile crowd intelligence perception data.

Background technique

With the development of the Internet of Things and the demand for location-based service applications, indoor positioning has received more and more attention in recent years. Due to the occlusion of urban buildings, the outdoor positioning technology represented by GPS is no longer available indoors, so people need a convenient, universal and accurate indoor positioning technology solution. In fact, researchers at home and abroad began to explore indoor positioning more than 20 years ago. Some attempts include deploying specialized hardware devices, such as magnetic tags, infrared, RFID and laser sensors, at key locations indoors, and positioning can be achieved by measuring distance or bearing. Although these techniques can provide good localization accuracy, additional hardware overhead, special equipment, and early deployment limit the popularization and application of these methods.

A large number of mobile communication devices (smartphones, laptops) on the market are embedded with inexpensive and diverse sensors, such as Wi-Fi modules, motion sensors, GPS and cameras. Wi-Fi access points (APs) are deployed in most indoor environments, so indoor positioning based on Wi-Fi has become a hot research topic at present. In fact, Wi-Fi has been used by many companies (including Google, Apple, Microsoft, Baidu, and Skyhook) for indoor positioning and navigation. At present, the location fingerprint method is widely used and the most advanced Wi-Fi indoor positioning method. This method needs to survey the indoor environment in advance, and establish a fingerprint map to record the fingerprint information corresponding to each location point in the environment. The positioning of the device can be realized. The biggest difficulty faced by this method is the construction of a huge fingerprint database. In particular, the urban buildings are huge and the structure is very complex, and the survey of the environment often requires special equipment and professional technicians, so the survey engineering costs a lot. With the change of indoor environment, it is necessary to update the fingerprint map and repeat manual survey, which has become a bottleneck restricting the popularization of fingerprint positioning methods.

In some domestic and foreign researches, the SLAM idea is introduced into Wi-Fi positioning, and the high-dimensional signal strength space is mapped to the low-dimensional two-dimensional position space by using the Gaussian process latent variable model. These methods often need to rely on the signal propagation model, and need to estimate the parameters of the signal propagation model of the AP at the same time when realizing self-positioning.

SUMMARY OF THE INVENTION

The technical problem to be solved by the present invention is to provide an indoor fingerprint map construction method based on mobile crowd intelligence perception data, so as to solve the problem of huge survey engineering in the existing fingerprint positioning method.

The technical solution of the present invention to solve the above technical problems is as follows: an indoor fingerprint map construction method based on mobile crowd intelligence perception data, comprising the following steps:

S1. Collect the user's fingerprint information and dead reckoning information through the mobile phone terminal, and upload them to the server;

S2, analyze the fingerprint information and dead reckoning information through the server, obtain the fingerprint similarity and user trajectory data, and use the fingerprint similarity and user trajectory data to construct a "vertex-constraint" graph;

S3. Optimizing the "vertex-constraint" graph through a graph optimization algorithm to obtain a fingerprint map.

On the basis of the above technical solutions, the present invention can also be improved as follows.

Further, the construction method of the "vertex-constraint" graph in the step S2 is:

S21. The pose of the user is formed into vertices, and the positional relationship between the vertices is an edge;

S22, perform closed-loop detection on the edge to obtain "fingerprint-closed-loop" and "turn-closed-loop";

S23. Construct a "vertex-constraint" graph through "fingerprint-closed loop" and "turn-closed loop".

Further, the calculation formula of the dead reckoning information R(t,τ) in the step S1 is:

In formula (1), μ(t,τ) and σ(t,τ) are the mean and standard deviation of the acceleration between t and t+τ, τ is the time delay parameter, l is a variable, ranging from 0 to τ-1, a(t+l) is the acceleration value at time t+l, μ(t+τ,τ) and σ(t+τ,τ) are the average sum of the acceleration between t+τ and t+2τ standard deviation.

Further, the calculation method of the fingerprint similarity s _ij in the step S2 is:

In formula (2), F _i is the fingerprint information collected at time i, F _j is the fingerprint information collected at time j, L is the number of detected APs, f _i,l is the signal strength of the lth AP at time i , f _j,l is the signal strength of the l-th AP at time j.

Further, the calculation method of "fingerprint-closed loop" in the step S22 is:

A1. Calculate the relative distance d _ij between the corresponding positions of fingerprint i and fingerprint j. The calculation formula is:

In formula (3), x _i and x _j are the abscissas of pattern i and fingerprint j, respectively, and y _i and y _j are the abscissas of fingerprint i and fingerprint j, respectively;

A2. Calculate the relative angle θ _ij between the corresponding positions of fingerprint i and fingerprint j. The calculation formula is:

θ _ij =|θ _i -θ _j | (4)

In formula (4), θ _i is the angle of fingerprint i, and θ _j is the angle of fingerprint j;

A3. When the relative distance d _ij is less than the distance threshold, the relative angle θ _ij is less than the angle threshold, and the fingerprint similarity s _ij is greater than the similarity threshold, then the fingerprint i and the fingerprint j form a "fingerprint-closed loop".

Further, the calculation method of "turning-closed loop" in the step S22 is:

B1. Divide the user trajectory data through the sliding window w to obtain the set Ct of trajectories at time t:

Ct={xt'} (5)

In formula (5), t is the time, t' is the moment when the sliding window condition is satisfied, |t'-t|≤w, x is the user's pose;

B2. In the set Ct, the average value in the direction less than time t is denoted as θ-, and the average value in the direction greater than time t is denoted as θ+. If the difference between θ- and θ+ exceeds 60°, it is in a turning state at time t.

Further, the graph optimization algorithm in described step S3 is to minimize function:

In formula (6), X _t =(x _t , y _t , θ _t ) is the user’s dead reckoning data at time t, t=i, j, i and j are both vertices, and (x _t , y _t ) is The two-dimensional position information of the user at time t, θ _t is the orientation information of the user at time t, C is the set of all constraints in the graph, and z _ij is the rigid body transformation between vertex i and vertex j.

The beneficial effects of the present invention are as follows: the present invention includes crowd-sensing data collection, closed-loop detection and graph construction, and graph optimization algorithm based on Graph SLAM. Using the mobile users in the environment as the sensing unit to realize the automatic collection of fingerprint data and user trajectories can reduce the survey workload required for fingerprint positioning and facilitate the rapid deployment of fingerprint positioning systems in unknown environments.

Description of drawings

Fig. 1 is the schematic flow chart of the present invention;

Fig. 2 is the schematic flow chart of step S2 of the present invention;

3 is a schematic diagram of constraints within and between users in crowd sensing according to the present invention;

4 is a schematic diagram of the periodic change of the IMU acceleration data when the user walks according to the present invention;

5 is a schematic diagram of the uncertainty model of fingerprint similarity and distance of the present invention;

6 is a schematic diagram of the original trajectory and turning of the user of the present invention;

FIG. 7 is a schematic diagram of turning detection and matching using a user trajectory according to the present invention.

Detailed ways

The principles and features of the present invention will be described below with reference to the accompanying drawings. The examples are only used to explain the present invention, but not to limit the scope of the present invention.

As shown in Figure 1, an indoor fingerprint map construction method based on mobile crowdsensing data includes the following steps:

S1. Collect the user's fingerprint information and dead reckoning information through the mobile phone terminal, and upload them to the server;

S2, analyze the fingerprint information and dead reckoning information through the server, obtain the fingerprint similarity and user trajectory data, and use the fingerprint similarity and user trajectory data to construct a "vertex-constraint" graph;

S3. Optimizing the "vertex-constraint" graph through a graph optimization algorithm to obtain a fingerprint map.

As shown in Figure 2, the construction method of the "vertex-constraint" graph in step S2 is:

S21. The pose of the user is formed into vertices, and the positional relationship between the vertices is an edge;

S22, perform closed-loop detection on the edge to obtain "fingerprint-closed-loop" and "turn-closed-loop";

S23. Construct a "vertex-constraint" graph through "fingerprint-closed loop" and "turn-closed loop".

As shown in Figure 3, a schematic diagram of the constraints within and between users in crowdsensing. Since there is a certain error in the observation data, all constraints are attached with an uncertainty parameter, which makes the graph-based SLAM problem transformed into optimization pose to minimize the error caused by constraints.

In the embodiment of the present invention, the graph optimization algorithm in step S3 is to minimize the function:

In formula (6), X _t =(x _t , y _t , θ _t ) is the user’s dead reckoning data at time t, t=i, j, i and j are both vertices, and (x _t , y _t ) is The two-dimensional position information of the user at time t, θ _t is the orientation information of the user at time t, C is the set of all constraints in the graph, and z _ij is the rigid body transformation between vertex i and vertex j.

For laser scanners, this transformation can be estimated by scan matching (eg iterative closest point algorithm, ICP); for vision sensors, this transformation can be obtained by feature matching. Given the signal strength of an AP, it is possible to quickly determine whether a user has revisited the area, because each AP has a unique hardware address, but it is very difficult to estimate the relative bit relationship between two measurement points from the signal strength, because RSS The data itself does not provide any distance or direction information.

Use the method of location fingerprint to perform closed-loop detection. The fingerprint describes the AP detected at a certain location and the corresponding signal strength; just like human fingerprints and DNA, Wi-Fi fingerprints can be used to uniquely describe a certain location. Overcome the influence of the environment on signal propagation; and the distance between two locations can be measured by the similarity of fingerprints.

If the similarity value of the two fingerprints is higher than a certain threshold, it is considered that the two positions are the same, thus a closed loop is detected, and this error is compensated by adding an uncertainty covariance parameter. In the application of , you can choose a diagonal matrix with a large value. To improve the accuracy of the system, a training process is used to build uncertainty models of similarity and distance.

Figure 4 shows the change rule of vertical acceleration when the human body is walking. At present, smartphones are embedded with low-power inertial navigation components. Simple dead reckoning can be realized by double integration of acceleration. Due to the influence of data drift and noise , the continuous double integration will bring a large cumulative error. The pedometer algorithm based on human walking dynamics can effectively overcome this shortcoming, and realize dead reckoning by identifying human behavior and counting the number of steps. The algorithm used is the autocorrelation analysis method. When a person is moving, the overall acceleration value has obvious periodic changes. The autocorrelation pedometer algorithm uses the autocorrelation coefficient of the acceleration sequence of the current pedometer cycle and the previous pedometer cycle. Step count is used to realize dead reckoning. The calculation formula of the dead reckoning information R(t,τ) in step S1 is:

In formula (1), μ(t,τ) and σ(t,τ) are the mean and standard deviation of the acceleration between t and t+τ, τ is the time delay parameter, l is a variable, ranging from 0 to τ-1, a(t)+l) is the acceleration value at time t+l, μ(t+τ,τ) and σ(t+τ,τ) are the average values of acceleration between t+τ and t+2τ and standard deviation.

和

和

之间的偏差即为两个坐标系之间的位移

为：Under mobile crowd sensing, each user collects data individually, and its motion trajectory is based on the starting position of each user without a common reference coordinate system. Therefore, the trajectories between users need to be merged, so that each user It has a common frame of reference and gives full play to the power of crowd perception. According to the movement direction of the user, consider the following two cases: In the first case, it is assumed that the direction of the user can be obtained by the compass of the mobile phone. In this way, the movement direction of each mobile phone is under the same reference frame (earth reference frame), and only the coordinate system has displacement. Given two users a and b, use the following formula to find the two fingerprints with the largest similarity in the two trajectories

and

and

The deviation between is the displacement between the two coordinate systems

for:

和

表示位移，

表示旋转，这三个参数可以通过最小化下面的距离函数来获得：In the second case, the direction error of the mobile compass is often very large, and some low-end mobile phones do not support compass sensors, so some dead reckoning systems do not provide the direction of movement relative to the earth's reference frame. In this case, use

and

represents displacement,

Representing the rotation, these three parameters can be obtained by minimizing the following distance function:

为用户b的轨迹与a中指纹t最相似指纹的位置，d()为两点之间的欧式距离。In formula (8), R is the rotation matrix between the two coordinate systems,

is the position where the trajectory of user b is most similar to the fingerprint t in a, and d() is the Euclidean distance between the two points.

Radio frequency fingerprints use radio frequency signals (such as Wi-Fi, RFID and Bluetooth) to describe a certain location, which can well overcome the influence of the environment on wireless signal propagation. Therefore, fingerprints are widely used in indoor positioning. Just like visual features, fingerprint information can be used to identify a certain scene. However, the extraction of visual features requires complex algorithms, but fingerprint information does not have this problem, because the hardware address of the AP in the fingerprint is unique in the world.

In the embodiment of the present invention, the calculation method of the fingerprint similarity s _ij in step S2 is:

In formula (2), F _i is the fingerprint information collected at time i, F _j is the fingerprint information collected at time j, L is the number of detected APs, f _i,l is the signal strength of the lth AP at time i , f _j,l is the signal strength of the l-th AP at time j.

The computational complexity of fingerprint similarity has a great relationship with the number of APs detected by two fingerprints. In the environment of an airport or a gym, hundreds of APs can often be obtained in one scan, and the computational overhead at this time is not negligible. Therefore, the concept of signal strength threshold is introduced to filter out the measurement data whose signal strength is less than that. On the one hand, filtering out some APs can greatly save the computing overhead of the system; on the other hand, due to the influence of environmental multipath effects, the signal strength that is too small often represents more noise, while the larger signal strength can make more noise. OK to limit the location.

s_k表示两个指纹的相似度，d_k表示两个指纹之间的距离。然后使用分箱方法来对样本进行训练，得到一个模型用于表示某一相似度对应距离的不确定性。也就是说，给定一个相似度s，计算与相似度s间隔为b的所有样本的方差var(s)：Figure 5 shows a schematic diagram of the uncertainty model of fingerprint similarity and distance. Each edge in Graph SLAM needs to specify its uncertainty. For the edges constructed by the odometer, the uncertainty can be obtained by the motion model, so it is necessary to specify the uncertainty of the fingerprint constraint (fingerprint closed loop), and use the odometry data to train the uncertainty model. Under normal circumstances, the odometer is still very accurate in the range of 30 meters. Therefore, the similarity of all fingerprints with distances less than 30 meters is calculated, and K training data are obtained:

s _k represents the similarity of the two fingerprints, and d _k represents the distance between the two fingerprints. Then use the binning method to train the samples, and get a model to represent the uncertainty of the distance corresponding to a certain similarity. That is, given a similarity s, calculate the variance var(s) of all samples with an interval b from the similarity s:

In formula (9), c(b) is the number of samples whose statistical similarity falls within the interval b, and b(s) is the sample whose similarity is between [s-b/2, s+b/2].

As shown in Figure 6 and Figure 7, a typical indoor environment often contains many landmarks, such as turns, elevators, and stairs, and the detection of these features often greatly improves the accuracy of indoor positioning systems. The present invention fuses the turning features in the environment into the SLAM system. After a fingerprint closed loop is obtained, the user's motion trajectory is analyzed to detect whether it is a turn, and the turn is matched to obtain a turn closed loop. Due to the limitation of the environment, the actual positions of the two correctly matched turns are often very close, which is much smaller than the uncertainty brought by the fingerprint closed loop. For example, the width of a corridor is often less than 3 meters, and the positioning accuracy of the fingerprint is often much greater than 3 meters. Meter. Figure 7 is a schematic diagram of trajectory-based turn detection and matching.

In the embodiment of the present invention, the calculation method of "fingerprint-closed loop" in step S22 is:

A1. Calculate the relative distance d _ij between the corresponding positions of fingerprint i and fingerprint j. The calculation formula is:

In formula (3), x _i and x _j are the abscissas of pattern i and fingerprint j, respectively, and y _i and y _j are the abscissas of pattern i and fingerprint j, respectively;

A2. Calculate the relative angle θ _ij between the corresponding positions of fingerprint i and fingerprint j. The calculation formula is:

θ _ij =|θ _i -θ _j | (4)

In formula (4), θ _i is the angle of fingerprint i, and θ _j is the angle of fingerprint j;

A3. When the relative distance d _ij is less than the distance threshold, the relative angle θ _ij is less than the angle threshold, and the fingerprint similarity s _ij is greater than the similarity threshold, then the fingerprint i and the fingerprint j form a "fingerprint-closed loop".

In the embodiment of the present invention, the calculation method of "turn-closed loop" in step S22 is:

B1. Divide the user trajectory data through the sliding window w to obtain the set Ct of trajectories at time t:

Ct={xt'} (5)

In formula (5), t is the time, t' is the moment when the sliding window condition is satisfied, |t'-t|≤w, x is the user's pose;

B2. In the set Ct, the average value in the direction less than time t is denoted as θ-, and the average value in the direction greater than time t is denoted as θ+. If the difference between θ- and θ+ exceeds 60°, it is in a turning state at time t.

In laser scan matching, ICP (Iterative Closest Point Algorithm) is often used to find the coordinate transformation between two sets of scanned point clouds, so as to minimize the sum of the distances between the corresponding points of the two sets of point clouds. So ICP is used to determine whether two turns match. Due to the low sampling frequency of dead reckoning, two sets of motion trajectories are interpolated before performing ICP. If the average distance value of corresponding points obtained by ICP is less than a certain threshold θ _f , the two turns are considered to be matched, and this closed loop is added to the turn closed loop.

The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. Any modification, equivalent replacement, improvement, etc. made within the spirit and principle of the present invention shall be included in the protection of the present invention. within the range.

Claims (4)

1. an indoor fingerprint map construction method based on mobile crowd intelligence perception data, is characterized in that, comprises the following steps: S1. Collect the user's fingerprint information and dead reckoning information through the mobile phone terminal, and upload them to the server; S2, analyze the fingerprint information and dead reckoning information through the server, obtain the fingerprint similarity and user trajectory data, and use the fingerprint similarity and user trajectory data to construct a "vertex-constraint" graph; The construction method of the "vertex-constraint" graph in the step S2 is: S21. The pose of the user is formed into vertices, and the positional relationship between the vertices is an edge; S22, perform closed-loop detection on the edge to obtain "fingerprint-closed-loop" and "turn-closed-loop"; The calculation method of "fingerprint-closed loop" in the step S22 is: A1. Calculate the relative distance d _ij between the corresponding positions of fingerprint i and fingerprint j. The calculation formula is:

In formula (3), x _i and x _j are the abscissas of fingerprint i and fingerprint j, respectively, and y _i and y _j are the abscissas of fingerprint i and fingerprint j, respectively; A2. Calculate the relative angle θ _ij between the corresponding positions of fingerprint i and fingerprint j. The calculation formula is: θ _ij =|θ _i -θ _j | (4) In formula (4), θ _i is the angle of fingerprint i, and θ _j is the angle of fingerprint j; A3. When the relative distance d _ij is less than the distance threshold, the relative angle θ _ij is less than the angle threshold, and the fingerprint similarity s _ij is greater than the similarity threshold, then the fingerprint i and the fingerprint j form a "fingerprint-closed loop"; The calculation method of "turning-closed loop" in the step S22 is: B1. Divide the user trajectory data through the sliding window w to obtain the set Ct of trajectories at time t: Ct={xt′} (5) In formula (5), t is the time, t' is the moment when the sliding window condition is satisfied, |t'-t|≤w, x is the user's pose; B2. In the set Ct, the average value of the direction less than time t is recorded as θ-, and the average value of the direction greater than time t is recorded as θ+, if the difference between θ- and θ+ exceeds 60°, then it is in a turning state at time t; S23. Construct a "vertex-constraint" graph through "fingerprint-closed loop" and "turn-closed loop"; S3. Optimizing the "vertex-constraint" graph through a graph optimization algorithm to obtain a fingerprint map. 2. the indoor fingerprint map construction method based on mobile crowd intelligence perception data according to claim 1, is characterized in that, in described step S1, the calculation formula of dead reckoning information R (t, τ) is:

In formula (1), μ(t,τ) and σ(t,τ) are the mean and standard deviation of the acceleration between t and t+τ, τ is the time delay parameter, l is a variable, ranging from 0 to τ-1, a(t+l) is the acceleration value at time t+l, μ(t+τ,τ) and σ(t+τ,τ) are the average sum of the acceleration between t+τ and t+2τ standard deviation. 3. the indoor fingerprint map construction method based on mobile crowd intelligence perception data according to claim 1, is characterized in that, in described step S2, the calculation method of fingerprint similarity s _ij is:

In formula (2), F _i is the fingerprint information collected at time i, F _j is the fingerprint information collected at time j, L is the number of detected APs, f _i,l is the signal strength of the lth AP at time i , f _j,l is the signal strength of the l-th AP at time j. 4. the indoor fingerprint map construction method based on mobile crowd intelligence perception data according to claim 1, is characterized in that, the graph optimization algorithm in described step S3 is the minimization function:

In formula (6), Xt=(x _t , y _t , θ _t ) is the user’s dead reckoning data at time t, t=i, j, i and j are all vertices, (x _t , y _t ) is t The two-dimensional position information of the user at time, θ _t is the orientation information of the user at time t, C is the set of all constraints in the graph, and z _ij is the rigid body transformation between vertex i and vertex j.

Images