KR20170092861A

KR20170092861A - Map-matching Method for the Pedestrian Location-based Services

Info

Publication number: KR20170092861A
Application number: KR1020160014072A
Authority: KR
Inventors: 유기윤; 방윤식
Original assignee: 서울대학교산학협력단
Priority date: 2016-02-04
Filing date: 2016-02-04
Publication date: 2017-08-14
Also published as: KR101845276B1

Abstract

The present invention relates to a map matching method for a pedestrian location-based service, comprising: (a) a step in which a location signal input module receives a location signal through a GPS; (b) a step in which a search radius calculation module calculates a search radius based on the location signal to match the input location signal with a pedestrian detailed road network map; (c) a step in which a similarity measurement module measures geometric similarities with road network map road objects in the search radius based on the location signal; and (d) a step in which a location correction module moves the location signal to a center point location of a road object with the highest similarity. The current location based on a movement state of a user is determined in real time, and is able to accurately display on the road network map. It is possible to provide a more precise user current location in consideration of the movement characteristics of a pedestrian and the pedestrian detailed road network map; thereby reducing a possibility of a wrong route guidance caused by erroneous matching.

Description

{Map-matching Method for Pedestrian Location-based Services}

The present invention relates to a map matching method for a pedestrian-based location-based service, more specifically, by matching a position signal of a user with a detailed road network for a pedestrian precisely in real time, The present invention relates to a positioning method capable of accurately displaying on a road network.

The demand for location-based services (such as navigation systems) for pedestrians is increasing with the development of personalized and various sensors equipped smartphones and wearable smart devices. Users of the location-based services for pedestrians are able to navigate to the destination You can be informed about the route and its surroundings while on the move.

For pedestrian location-based services, the position of the user who is walking should be precisely provided to the user. In particular, providing a navigation service for pedestrians requires more precise and concise map matching techniques than map matching techniques used in existing car navigation systems.

Here, the map matching is a method of correcting the position coordinates (which may be caused by GPS or the road network) inputted through the position sensor, such as GPS, through the geometric method, assuming that the position exists on the road To a location on the road where the user is located and to provide the location to the user. It is assumed that the user usually moves along the road defined by the road network by preliminarily constructing the road network information that the user can pass. The road or road network refers to a road to which a pedestrian can pass.

Road information for pedestrians is information indicating the way that ordinary pedestrians can go, which is the center line of roadside, the center line that follows the alley, the center line of the crosswalk, and the center line of the overpass. This information has been steadily built up nationwide through research and development support from the government, pilot projects, and investment in private companies.

Positioning and map matching of pedestrians is challenging compared to other cases (generally vehicles). The pedestrian movement pattern is characterized by a very frequent and irregular redirection, while the speed of the pedestrian is slow and the variation of position is small compared with the vehicle. In the case of vehicle positioning and map matching, it is possible to compensate the error due to the high speed position change by the position prediction method considering the moving direction and the pattern, but in the case of the pedestrian, the position prediction is relatively difficult due to the irregularity of the direction change .

Particularly, in 2000, ITS / telematics technology has been rapidly developed and car map matching techniques have been studied. However, most of them are combined with additional information such as DR to GPS GPS signal to predict exact location. Automotive map matching techniques focus on solving the problem of GPS tracking speeds lagging behind normal vehicle speeds. In contrast, the navigation environment for pedestrians, on the other hand, is more problematic due to the fact that the position error of the GPS exceeds the range of the position prediction according to the slow moving speed of the pedestrian, instead of the problem of the GPS tracking speed. (1) frequent change of direction (pedestrian movement is more freer than vehicle), (2) increase of error due to proximity to obstacles including buildings, (3) complexity of detailed road network for pedestrians, etc. The cause of the problem.

However, it is not a real-time positioning technique applicable to location-based services. Most of the techniques are for matching the entire or part of the movement trajectory of the pedestrian with the road network. Also, the application range is narrow because it is not based on the detailed road network for pedestrians.

Since the detailed road network for pedestrians is also more complicated than the commonly used road network for vehicles, it becomes relatively more difficult to accurately display the user's position on the road on which he is actually located.

Although GPS or Wi-Fi and other user-motion recognition technologies have been able to accurately determine the user's location, the error between the detailed road network for pedestrians and the actual location is still a problem to be solved.

As a prior art related to the present invention, Korean Patent Registration No. 10-1427982 discloses a method for estimating the position of a pedestrian while a mobile terminal is moving, comprising the steps of: communicating with a plurality of access points ; Acquiring and storing two-dimensional position coordinates of the moving pedestrian at a predetermined time interval through communication with the access point; Calculating an average and a variance of coordinate values for each of the two-dimensional position coordinates; Comparing the magnitude of the axial variance; And correcting the two-dimensional position coordinate according to the magnitude of the axial dispersion. In the prior art, however, the positional coordinate is corrected by calculating an error for each section without using road data The user's current position can not be accurately displayed on the road network in real time.

Korean Patent Registration No. 10-1427982 (Published on Aug. 31, 2014), entitled "Mobile terminal and method for estimating pedestrian position"

SUMMARY OF THE INVENTION The present invention has been made in order to solve the above problems, and it is an object of the present invention to provide a navigation system, Based service for pedestrians, which can accurately determine road markings on the road network in real time.

It is another object of the present invention to provide a location-based service for a pedestrian by providing a precise user's current location in consideration of the moving characteristics of a pedestrian and the detailed road network for a pedestrian without using the map matching technology applied to a conventional vehicle service as it is The present invention provides a map matching method for a location-based service for a pedestrian, which can reduce the possibility of false route guidance due to mis-matching.

According to another aspect of the present invention, there is provided a position signal input module, comprising: (a) receiving a position signal through a GPS in a position signal input module; (b) calculating a search radius around the position signal to match the position signal inputted from the search radius calculation module with the detailed road network for a pedestrian; (c) measuring a degree of similarity between the position signal and the road network road objects in the search radius centering on the position signal in the similarity measurement module, and (d) And moving the center point to a center point position.

In the present invention, in the step (a), the position signal may be an (X, Y) coordinate value, and an accuracy value may be input along with the coordinate value.

Further, the present invention is characterized in that in the step (b), the search radius is calculated by the following equation,

(n = 2, 3, 4, ....) (where R _n Is the search radius of the nth matched position signal,

(E _n _-1 is the error range of the (n-1) th position signal, R _n _-1 is the search radius of the (n-1) th position signal, B _n _-1 is the distance moved the n- k is a correlation coefficient), D _n _{, n-1} is the shortest distance between the road object matched with the (n-1) th position signal and the n th position signal).

The present invention is characterized in that the k value is set to 0.5 in consideration of the randomness and uniformity of the error magnitude in order to obtain an effective map matching result.

In the present invention, if the calculated radius of the search radius is more than twice the accuracy value of the corresponding position signal, the position signal is regarded as a road network or road object does not exist in the vicinity and processed as 'map matching failure' Signal.

Also, the present invention is characterized in that the degree of similarity in the steps (c) and (d) is the length of a road object in a portion overlapping with the inside of the search radius, and a road object having a long length is matched with the position signal.

In the present invention, the steps (a) to (d) are performed sequentially for each position signal of the position signal locus, and when the position signal is not received at the end position signal of the position signal locus, And the matching is terminated.

In the map matching method for the pedestrian based location service according to the present invention, the position signal of the user inputted through the GPS sensor is precisely matched with the detailed road network for the pedestrian in real time, It is possible to precisely display it on the road network and to provide a more precise user current position in consideration of the moving characteristics of pedestrians and the detailed road network for pedestrians, thereby reducing the possibility of false route guidance due to mis- It is effective.

BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a block diagram illustrating a system for a map matching method for a location-based service for a pedestrian according to the present invention; FIG.
2 is a flowchart of a map matching method for a location-based service for a pedestrian according to the present invention.
3 is a diagram illustrating a search radius calculation process for matching GPS position signals in a map matching method for a location-based service for a pedestrian according to the present invention.
4 is a diagram illustrating a process of measuring similarity with road objects in a search radius and correcting a GPS position signal in a map matching method for a location-based service for a pedestrian according to the present invention.
FIG. 5 is a conceptual diagram of the Fresch distance value utilized by the present invention; FIG.
FIG. 6 is a conceptual diagram for adjusting the search radius by applying and improving the Fresch distance value; FIG.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Hereinafter, preferred embodiments of the present invention will be described in detail with reference to the accompanying drawings. It is to be understood that the appended drawings and foregoing description are intended for purposes of illustration only and are not intended to limit the scope of the present invention. .

1, a user terminal 1 is a mobile terminal or a notebook PC, such as a smart phone or a tablet PC, connected to a server 2 that provides a detailed road network diagram for a pedestrian through a communication network and transmits / receives various information data . In the user terminal 1, a location based service application 10 is installed. The location-based service application 10 can be downloaded from the server 2 and downloaded and installed in various app stores.

The location-based service application 10 includes a location signal input module 11 for receiving a location signal via GPS, a search radius calculation module 12 for calculating a search radius for matching the input location signal with the detailed road network for pedestrians, A similarity measurement module 13 for measuring the geometric similarity with the road objects in the search radius around the corresponding position signal, a position modification module 14 for moving the position signal to the center point position of the road object having the highest similarity, . Here, the position signal means a position signal of the user, assuming that the position signal of the user is inputted through the GPS sensor in the user terminal and the detailed road network for the pedestrian in the area where the user is located is constructed. Also, the server 2 is provided with a detailed road network DB 3 for pedestrians for inputting and outputting various geographical information in real time for a pedestrian-based location-based service.

FIG. 2 is a flowchart illustrating a map matching method for a location-based service for a pedestrian according to the present invention.

First, when the user terminal starts to use the location-based service, the position signal input module 11 receives a position signal having an (X, Y) coordinate value through a global positioning system (GPS) , The input period of the position signal depends on a predetermined time interval set by the user.

Also, an accuracy value measured together with the coordinate value is input together. The accuracy value is represented by a constant distance value from the coordinate value. The input position signal and its accuracy value are immediately transmitted to the search radius calculation module 12, but the position signal with an accuracy value of 10 m or more is not transmitted.

Second, the search radius calculation module 12 determines a search radius to be used for matching based on the coordinate value of the position signal. In other words, a search radius for matching the position signal inputted from the position signal input module 11 with the detailed road network for the pedestrian is calculated (S20).

First, an error range of the position signal matched immediately before the current position signal is calculated. As shown in Figure 3, the current position signal is the second position signal (P2) days when 1 is moved to the position signal (P1) navigation R _1, one first position signal (P1) a radius matched to the second distance (position correction amount) When the called B _1, an error range (E ₁ of the first position signal (P1)), is calculated by the following equation (1).

The above equation (1) can be generalized with respect to all the position signals.

(Where n = 2, 3, 4, ....)

In Equations (1) and (2), k is a correlation coefficient of the error range of the GPS position signal, and is a coefficient indicating the randomness of the error magnitude. If k is set to 0, the error magnitude is updated to the minimum value every time the position signal is input, thereby minimizing the search radius of the next position signal. On the other hand, if k is set to 1, the error magnitude of the next position signal becomes equal to the search radius of the previous position signal, so that the search radius is kept large. In other words, if the value of k is made small, the search range becomes narrow and the matching rate lowers. On the other hand, if the value is large, the search range becomes wider as the trajectory advances, thereby increasing the matching error. In the case of the map matching for the pedestrian, if the value of k is 0.5, it is desirable to obtain an effective map matching result by appropriately considering the pros and cons of both sides (randomness and uniformity).

Next, as shown in Figure 3, the first position signal (P1) and the road object D ₂₁ less than the distance between the current position signal with the second position signal (P2) matched to the , The search radius R ₂ of the second position signal P ₂ is calculated by the following equation (3).

That is, it is equal to the larger of E ₁ and D ₂₁ . In other words, since the search radius is at least equal to or greater than the shortest distance D, matching road objects can be continuously connected. However, since the first position signal P1 can not calculate the search radius because there is no previous position signal, the accuracy value of the first position signal is directly used as the search radius.

If the above Equation (3) is generalized for all the position signals, Equation (4) is obtained.

(Where n = 2, 3, 4, ....)

Accordingly, as the position signal corresponding to the movement of the user is continuously inputted, the map matching proceeds while continuously adjusting the search radius through the above process. However, if the calculated radius of the search radius is more than twice the accuracy of the position signal, the position signal is regarded as a road network or road object does not exist in the vicinity, It goes to the next position signal.

Thirdly, the similarity measurement module 13 measures the geometric similarity with individual road entities by matching the locus signal with the detailed road network for pedestrians. In other words, the road network in the search radius corresponding to each position signal is measured to measure the geometric similarity with road objects (S30).

4, a circle corresponding to the search radius R is drawn from each of the position signals P1, P2, P3, P4, ... corresponding to the coordinate values, And extracts the road entities overlapping in the interior with matching candidates. The similarity of the extracted matching candidates is calculated as the total length value of the corresponding road object. That is, as the length of the portion overlapping with the inside of the search radius is longer, the road object is matched with the GPS position signal. For example, in FIG. 4, there are two matching candidates, which are road objects overlapping within the search radius of the fourth position signal P4. Among them, a road object having a long portion overlapping with the inside of the search radius Object) is matched with the position signal.

Fourth, based on the similarity value calculated by the similarity degree measurement module 13, the position correction module 14 finds a road object, which is a matching candidate having the highest degree of similarity with respect to each position signal, Modifies the position signal to the position of the geometric center point of the object (center of gravity). The modified position signal ( x in Fig. 4) is immediately displayed on the terminal screen as the current position of the service user. In other words, the position signal is moved to the center point position of the road object having the highest degree of similarity (S40).

4, there are two matching candidate objects for the fourth position signal P4, and since the similarity degree of the road object located at the lower side is higher, the position signal is located at the lower side of the road object The position is corrected to the center point of the center.

As shown in FIG. 2, the series of processes (S10 to S40) are sequentially progressed separately for each position signal (after the steps S10 to S40 are performed for the position signal P1, The same process is performed), and the map matching ends when the last position signal of the position signal locus is received and no more position signal is received. And the series of processes is performed by a program directly coding an algorithm through a program language in order to execute the program with a computer.

In the present invention, a map matching method reflecting the characteristics of the pedestrian's movement and the detailed road network for a pedestrian is presented, and the concept of Frechet distance, which is one of the linear geometric similarity measurement techniques, is utilized. Fréques distance is one of the measuring methods for calculating the distance between two curves. Assuming a moving object moving in a certain direction along each curve, the minimum value of the distance between two moving objects varies with the distance between two curves define.

This Frécé's distance concept is appropriate for the trajectory of a moving object because it regards the linear object as a position function over time. Therefore, in the present invention, the geometric similarity between the linear road made of the position signal of the pedestrian and the detailed road network for the pedestrian is measured by utilizing the Fresch distance concept.

In order to apply this concept to the map matching process, first the initial search radius is set, and then road objects coming in the search radius are searched from the individual position signals of the pedestrian. As the pedestrian moves and the position signal is continually input, the road object coming in the search radius from the signal is constantly searched for. If there is no road object coming in within the search radius, the road object is searched while increasing the search radius.

That is, in FIG. 5, road entities matching the locus of the GPS position signal are Road (1), Road (2), and Road (3) The minimum search radius value required to come in.

However, there is a problem in applying this Fresche distance concept to actual GPS position signals. This is because the accuracy values of all the position signals continuously change. Therefore, when a signal having a significantly lower accuracy is input to the GPS position signal, the Fresch distance value becomes larger than necessary due to the signal of the portion, which makes it difficult to accurately find a road object that matches the position signal of the other portion.

In order to overcome this problem, in the present invention, instead of calculating a single Frescian distance value, a new Frescale distance value is adjusted for each individual GPS position signal. That is, if the matching of the road object in a GPS position signal is matched to a road relatively close to the search radius, it can be considered that the search radius in the present position signal is wider than necessary. If you set the search radius of the next position signal to a smaller value, you can increase the accuracy of the map matching. Conversely, if there is no road object coming in the search radius, the search radius is increased to find the matching road object. That is, the present invention introduces the correlation coefficient (k) by applying and improving the Freschel distance value concept and derives the above Equations (1) to (4) including the correlation coefficient (k) I adjust the radius.

That is, in FIG. 6, since the distance from the road object gradually increases in the front portion of the GPS position signal, the search radius is also gradually widened. On the other hand, the signals in the middle part gradually become closer to the road object, so that the search radius gradually decreases.

When adjusting the search radius to be small, the degree of adjustment can be determined by introducing correlation coefficient k. If the position error is a trend to decrease, the adjustment of the search radius is performed as shown in Equation (5).

Here, R _i-1 is the final search radius, B _i of the previous position _signal-1 refers to the map matching results position correction amount from the previous position signal. And k is a correlation coefficient and may have a value between 0 and 1. That is, if k is set to 1, R _i = R _i _-1 , the search range is not adjusted and the search range of the previous position signal remains unchanged. On the other hand, if k is set to 0, R _i = B _i _-1 , the search radius is adjusted by the position correction amount according to the matching result in the previous position signal, that is, the road object is searched for only the expected minimum range. That is, in the present invention, the concept of the Fréchet distance value is applied and improved, and the equation (5) derived by introducing the correlation coefficient (k) is derived and the equation (1)

In addition, if there is no road object coming in the search radius and the search radius is to be increased, the road object is increased to a search radius value that is constantly searchable regardless of the value of k (see Equations 3 and 4 above). In this case, if the search radius value increases too rapidly, the position signal is erroneously input due to an error, or the detailed road network is erroneously constructed. Therefore, it is regarded as a matching failure and a new map matching operation is started. In this way, the GPS position signal can be matched to the detailed road network for pedestrians.

Therefore, according to the present invention, the position signal of the user inputted through the GPS sensor is precisely matched with the detailed road network for the pedestrian in real time, so that the current position according to the moving state of the user can be determined in real time, It is possible to reduce the possibility of wrong route guidance due to mis-matching by providing more precise user's current position in consideration of the movement characteristics of pedestrians and the detailed road network for pedestrians, Direction and distance can be determined more accurately.

1: User terminal 2: Server
3: Detailed road network for pedestrians DB 10: Location-based service application
11: Position signal input module 12: Search radius calculation module
13: similarity measurement module 14: position modification module

Claims

(a) receiving a position signal through the GPS in the position signal input module 11;
(b) calculating a search radius around the position signal to match the position signal inputted from the search radius calculation module 12 with the detailed road network for a pedestrian;
(c) measuring the geometric similarity of the road network road objects in the search radius with respect to the position signal in the similarity measurement module 13, and
(d) moving the position signal to the center point position of the road object having the highest degree of similarity in the position correcting module (14).

The method according to claim 1,
Wherein the position signal comprises an (X, Y) coordinate value, and an accuracy value is also input along with the coordinate value in the step (a).

The method according to claim 1,
In the step (b), the search radius is calculated by the following equation,

(E _n _-1 is the error range of the (n-1) th position signal, R _n _-1 is the search radius of the (n-1) th position signal, B _n _-1 is the distance moved the n- k is a correlation coefficient), D _n _{, n-1} is the shortest distance between the road object matched with the (n-1) th position signal and the n th position signal). .

The method of claim 3,
Wherein the k value is set to 0.5 in consideration of randomness and uniformity of the error size to obtain an effective map matching result.

3. The method of claim 2,
If the size of the calculated search radius is more than twice the accuracy value of the position signal, the position signal is regarded as a road network or road object does not exist in the vicinity and processed as 'map matching failure' Wherein the method comprises the steps of:

The method according to claim 1,
Wherein the degree of similarity in the steps (c) and (d) is a length of a road object in a portion overlapping the inside of the search radius, and a road object having a long length is matched with the position signal. Map matching method.

The method according to claim 1,
The steps (a) to (d) are sequentially progressed individually for each position signal of the position signal locus, and when the position signal is not received at the last position signal of the position signal locus, map matching is terminated Wherein the method comprises the steps of: