WO2012093842A2

WO2012093842A2 - Apparatus and method for detecting location information using navigation algorithm

Info

Publication number: WO2012093842A2
Application number: PCT/KR2012/000065
Authority: WO
Inventors: Kyong-Ha Park; Chan-Gook Park; Hyun-Su Hong; Sung-Min Park; Seung-Hyuck Shin
Original assignee: Samsung Electronics Co Ltd; Seoul National University R&DB Foundation
Current assignee: Samsung Electronics Co Ltd; SNU R&DB Foundation
Priority date: 2011-01-07
Filing date: 2012-01-04
Publication date: 2012-07-12
Anticipated expiration: 2013-07-07
Also published as: US20130282275A1; KR101796322B1; CN103299209A; EP2661643A2; EP2661643A4; WO2012093842A3; US9410808B2; KR20120080489A

Abstract

A method and apparatus for detecting location information using a navigation algorithm are provided, in which neighboring Global Positioning System (GPS) satellites are searched for, pseudo-range information is received from at least one of the detected GPS satellites and stored, a displacement of a pedestrian terminal is calculated based on step detection from a pedestrian, the calculated displacement of the pedestrian terminal is corrected using the received pseudo-range information, and the location of the pedestrian terminal is measured using the corrected displacement.

Description

APPARATUS AND METHOD FOR DETECTING LOCATION INFORMATION USING NAVIGATION ALGORITHM

The present invention relates to detection of location information about a user, and more particularly, to an apparatus and method for detecting location information about a user using a radio navigation system and a pedestrian navigation system.

A personal navigation system was designed to provide person-centered route guidance. It locates a pedestrian to be route-guided and guides the pedestrian to a route based on his or her location. Personal navigation systems can be classified into a satellite navigation system, an inertial navigation system, a pedestrian navigation system, etc. according to movement types.

The satellite navigation system provides information about a current location and a route to a desired destination to a user using satellites. A major example of the satellite navigation system is a car navigation system.

The car navigation system locates a vehicle, provides the vehicle's driver with an optimum route, and guides the driver along the optimum route. In general, this car navigation system calculates the current location of the vehicle using a Global Positioning System (GPS) sensor and provides route guidance from the current location to a destination.

The inertial navigation system calculates the acceleration of a user by means of an accelerometer such as a gyroscope sensor, calculates the current velocity of the user based on the acceleration, and detects the current location of the user based on the velocity. The inertial navigation system is applied mainly to a submarine, an aircraft, a missile, etc. Recently, route guidance has been provided to vehicles or aircrafts using a composite navigation system having an accelerometer in addition to the satellite navigation system.

The pedestrian navigation system provides pedestrian-centered route guidance, not car-centered route guidance. Although the pedestrian navigation system is similar to the card navigation system, the former measures the location of a route-guidance object more accurately and provides more detailed route guidance than the latter because the route-guidance object is a pedestrian slower than a car.

Accordingly, the car navigation system and the pedestrian navigation system provide route guidance using different algorithms. For example, the navigation system locates a car using a GPS sensor, whereas the pedestrian navigation system locates a pedestrian by detecting the pedestrian's steps and strides. Therefore, these two navigation systems should their dedicated navigation devices for performing their own algorithms.

However, in the case where both a car navigation device and a pedestrian navigation device should be used, a user should purchase the two navigation devices, resulting in increased cost and less portability. In this context, a composite navigation device has recently been developed to enable the car navigation system and the pedestrian navigation system to be used together.

A shortcoming with the composite navigation device is that a user should manually switch an operation mode between the car navigation system and the pedestrian navigation system. That is, to use the pedestrian navigation system while using the car navigation system, the user should end the car navigation system manually and then activate the pedestrian navigation system, or vice versa.

Therefore, the conventional navigation device inconveniently requires a user to manually select the car navigation system or the pedestrian navigation system. Moreover, if the user selects a wrong navigation system by mistake, wrong route guidance may be provided to the user.

An aspect of embodiments of the present invention is to address at least the problems and/or disadvantages and to provide at least the advantages described below. Accordingly, an aspect of embodiments of the present invention is to provide an apparatus and method for detecting the location of a user, automatically using car navigation or pedestrian navigation selectively or both the car navigation and pedestrian navigation in combination without user manipulation in a composite navigation device that provides a car navigation system and a pedestrian navigation system.

In accordance with an embodiment of the present invention, there is provided a method for measuring a location of a pedestrian terminal, in which neighboring Global Positioning System (GPS) satellites are searched for, pseudo-range information is received from at least one of the detected GPS satellites and stored, a displacement of the pedestrian(a displacement of the pedestrian terminal) is calculated based on step detection from a pedestrian, the calculated displacement of the pedestrian is corrected using the received pseudo-range information, and the location of the pedestrian terminal is measured using the corrected displacement.

The displacement of the pedestrian may be calculated by a Pedestrian Dead Reckoning (PDR) algorithm that estimates a location of a pedestrian according to gait characteristics of the pedestrian.

The displacement of the pedestrian may be confirmed by a pedestrian navigation system, a distance between the pedestrian terminal and the at least one GPS satellite may be calculated using the calculated displacement of the pedestrian and orbit information about the at least one GPS satellite, and the displacement of the pedestrian may be corrected using a difference between the received pseudo-range information and the calculated distance between the pedestrian terminal and the at least one GPS satellite.

The pseudo-range information may be received from the at least one of the detected GPS satellites, an error of the received pseudo-range information may be detected and corrected using a filter, and the corrected pseudo-range information may be stored.

In accordance with another embodiment of the present invention, there is provided an apparatus for measuring a location of a pedestrian terminal, in which a user interface interfaces with a user, a GPS receiver searches for neighboring GPS satellites and receives pseudo-range information from at least one of the detected GPS satellites, and a controller calculates a displacement of the pedestrian based on step detection from a pedestrian, corrects the calculated displacement of the pedestrian using the received pseudo-range information, and measures the location of the pedestrian terminal using the corrected displacement.

The controller may calculate the displacement of the pedestrian by a PDR algorithm that estimates a location of a pedestrian according to gait characteristics of the pedestrian.

The controller may confirm the displacement of the pedestrian by a pedestrian navigation system, may calculate a distance between the pedestrian terminal and the at least one GPS satellite using the calculated displacement of the pedestrian and orbit information about the at least one GPS satellite, and may correct the displacement of the pedestrian using a difference between the received pseudo-range information and the calculated distance between the pedestrian terminal and the at least one GPS satellite.

The apparatus may further include a filter unit for detecting and correcting an error of the received pseudo-range information.

The controller may control selective coupling of predetermined two navigation algorithms or use of only one of the two navigation algorithms according to the number of GPS signals received through the GPS receiver.

The apparatus may further include an accelerometer for measuring an acceleration of the apparatus according to a motion of the apparatus.

The controller may include a satellite navigation algorithm executer for receiving information about a location of a user from a visible satellite and providing information about the location of the user, and a PDR algorithm executer for estimating a location of a user according to gait characteristics of the user.

If the number of GPS signals received through the GPS receiver is 4 or larger, the controller may use a loosely coupled scheme in which a location and velocity of the GPS receiver are used as measurements for a coupled system.

If the number of GPS signals received through the GPS receiver is 3 or smaller, the controller may compare strengths of the GPS signals with a predetermined threshold, and if the strengths of the GPS signals are higher than the predetermined threshold, the controller may use a tightly coupled scheme in which pseudo-range information and pseudo-range change rate information received through the GPS receiver are used as measurements.

If no GPS signal is received through the GPS receiver, the controller may detect location information about the user using one of predetermined two navigation algorithms, the one navigation algorithm being the PDR algorithm.

As is apparent from the above description of the present invention, in a composite navigation device that provides a satellite navigation system and a PDR system, a car navigation system and a pedestrian navigation system are automatically used selectively or in combination, without a user's manipulation. Therefore, accurate location information about a user can be provided in an environment where the car navigation system cannot provide the location information about the user.

The above and other objects, features and advantages of certain embodiments of the present invention will be more apparent from the following detailed description taken in conjunction with the accompanying drawings, in which:

FIG. 1 is a block diagram of a navigation device according to an embodiment of the present invention;

FIG. 2 is a flowchart illustrating an operation for notifying the location of a user using the navigation device according to an embodiment of the present invention;

FIG. 3 is a flowchart illustrating an error correction operation according to an embodiment of the present invention; and

FIGs. 4a to 5b are graphs illustrating filter tuning results obtained by taking into account gait characteristics according to an embodiment of the present invention.

Throughout the drawings, the same drawing reference numerals will be understood to refer to the same elements, features and structures.

Reference will be made to the preferred embodiment of the present invention with reference to the attached drawings. While the following description includes specific details, it is to be clearly understood to those skilled in the art that the specific details are provided to help comprehensive understanding of the present invention and modifications and variations can be made to them within the scope and spirit of the present invention.

The present invention uses a Pedestrian Dead Reckoning (PDR) system. The PDR system estimates the location of a user based on the gait characteristics of the user. Because a general integrated navigation system model is not viable, it is essential to derive a model specialized for the PDR. The present invention provides a method for coupling the PDR system with a satellite navigation system using the features of the PDR system such as step detection, stride length estimation, and heading estimation regarding a pedestrian.

According to the present invention, the two navigation systems can be loosely coupled or tightly coupled. Depending on the reception state of a Global Positioning System (GPS) signal, the two systems are coupled in a different manner. A composite navigation system with the two systems coupled in it should consider information output from each system on the same coordinate system.

That is, the PDR system provides a location on a local horizontal coordinate system, whereas the satellite navigation system provides a location on an Earth-Centered Earth-Fixed (ECEF) coordinate system. Therefore, the two different coordinate systems should be converted using an appropriate coordinate conversion matrix.

A navigation device that selectively couples the two systems has the following configuration.

FIG. 1 is a block diagram of a navigation device according to an embodiment of the present invention. The navigation device includes a user interface 101, a GPS receiver 103, an accelerometer 105, a navigation algorithm controller 107, and a filter unit 113. The navigation algorithm controller 107 includes a satellite navigation algorithm 109 and a PDR algorithm 111.

Referring to FIG. 1, the user interface 101 may be configured with an input device such as a keypad, a touch panel, etc. for interfacing with a user. For instance, the user interface 101 may receive a request for executing a navigation program from the user and may provide the request to the navigation algorithm controller 107.

The GPS receiver 103 receives a GPS signal from a GPS satellite and transmits the received GPS signal to the navigation algorithm controller 107. The GPS receiver 103 may receive one or more GPS signals which include position information and time information. In addition, the GPS receiver 103 receives information about a pseudo-range from at least one satellite. The accelerometer 105 may be a 3-axis accelerometer and measures an acceleration according to a motion of the navigation device. The accelerometer 105 measures the acceleration of the navigation device according to the motion of the navigation device, using an acceleration sensor.

The filter unit 113 detects an error in an acceleration of the navigation device based on a motion of the navigation device measured by a specific filter and an error between a measured current location of the navigation device and a destination and corrects the errors. That is, when an actual location and an estimated location are different, the error between the actual and estimated locations is detected and corrected so that the estimated location is approximate to the actual location as much as possible. In the present invention, a Kalman filter is used.

The navigation algorithm controller 107 includes the satellite navigation algorithm 109 and the PDR algorithm 111 and controls selective coupling of the two

algorithms

109 and 111 or use of only one of the two

algorithms

109 and 111 by counting the number of GPS signals received from the GPS receiver 103. For example, when four or more GPS signals are received, the satellite navigation algorithm 109 and the PDR algorithm 111 are coupled loosely in such a manner that the satellite navigation algorithm 109 is a main one and the PDR algorithm 111 is an auxiliary one.

The loose coupled scheme is used in most cases, which uses the location and velocity of a GPS receiver as a measurement in a coupled system. Despite the advantage of easy configuration, the loose coupled scheme can provide information about a user's location only if the number of visible satellite is 4 or larger.

In another example, if three or fewer GPS signals are received, the navigation algorithm controller 107 estimates a location and heading by tightly coupling the satellite navigation algorithm 109 with the PDR algorithm 111 in such a manner that information about a current location, velocity, and heading of a user using the navigation device, as obtained by the PDR algorithm 111 is used together with satellite information received through the GPS receiver 103.

According to the tightly coupled scheme, neighboring GPS satellites are detected through the GPS receiver 103, pseudo-range information is received from at least one of the detected GPS satellites, the received pseudo-range information is stored, a displacement of a pedestrian(a displacement of a pedestrian terminal) is calculated using step detection of the pedestrian and corrected using the received pseudo-range information, and the location of the pedestrian l is measured using the corrected value.

The displacement of the pedestrian is calculated by the PDR algorithm that estimates the location of a pedestrian using the gait characteristics of the pedestrian.

The displacement of the pedestrian is corrected by calculating the distance between the pedestrian terminal and a GPS satellite from which the pseudo-range information has been received, using the calculated displacement of the pedestrian and orbit information about the GPS satellite and calculating the difference between the distance and the received pseudo-range information.

The tightly coupled scheme uses pseudo-range information received at the GPS receiver 103 and pseudo-range change rate information as measurements. As far as one or more visible satellites exist, the tightly coupled scheme can provide location information about a user.

An operation for providing location information about a user in the navigation device having the above-described configuration will be described below.

FIG. 2 is a flowchart illustrating an operation for notifying the location of a user using the navigation device according to an embodiment of the present invention.

Referring to FIG. 2, the navigation device receives a GPS signal from the GPS receiver 103 in step 201. If the navigation device is located in a shadowing area, it cannot receive any GPS signal. On the other hand, if the navigation device is located in an area placed in a good GPS reception state, it may receive a plurality of GPS signals.

In step 203, the navigation device determines whether the number of GPS signals received through the GPS receiver 103 is 4 or larger because the satellite navigation algorithm 109 is coupled with the PDR algorithm 111 in a different manner according to the number of received GPS signals.

If the number of GPS signals received through the GPS receiver 103 is 4 or larger, the navigation device determines that it is currently located in an area where GPS signals are actively received and goes to step 205. In step 205, the navigation device loosely couples the satellite navigation algorithm 109 with the PDR algorithm 111 and receives information about a current location and travelling route of the navigation device according to the loosely coupled scheme.

On the other hand, if the number of GPS signals received through the GPS receiver 103 is 3 or smaller, the navigation device determines that it is currently located in a shadowing area where GPS signals cannot be actively received and goes to step 207. In step 207, the navigation device determine whether the number of received GPS signals is smaller than 1.

If the number of received GPS signals is smaller than 1, the navigation device determines that no GPS signal is received and goes to step 211. In step 211, the navigation device estimates the location and heading of the user, using the PDR algorithm 111 only, without the satellite navigation algorithm 109.

If the number of received GPS signals is 1 or larger, the navigation device compares the strength of a received GPS signal with a predetermined threshold in step 209. If the strength of the received GPS is equal to or lower than the threshold, the navigation device estimates the location and heading of the user using the PDR algorithm 111 only in step 211. If the strength of the received GPS is higher than the threshold, the navigation device estimates the current location and heading of the navigation device by tightly coupling the satellite navigation algorithm with the PDR algorithm 111 in step 213. With the tightly coupled algorithms, the location error of the user can be corrected even when the user is located in a shadowing area where 4 or fewer satellite signals are received.

FIG. 3 is a flowchart illustrating an error correction operation according to an embodiment of the present invention. In the present invention, a Kalman filter is used. The Kalman filter is used to obtain an optimum estimate of a state variable and is applied to a linear system that has a linear structure and minimizes the error variance of an estimated state variable.

Referring to FIG. 3, the navigation device receives a GPS signal in step 301. The received GPS signal is transmitted to the Kalman filter. In step 303, the Kalman filter generates a measurement using the received GPS signal. Since the GPS signal carries pseudo-range information and pseudo-range change rate information, the Kalman filter uses the pseudo-range information and pseudo-range change rate information in generating the measurement. Then, a state variable measurement is updated with the generated measurement in step 305. Specifically, a gain of the Kalman filter is calculated and the state variable measurement is updated using the gain. An error of the GPS signal is corrected using the updated state variable measurement in step 307 and the error-corrected GPS signal is applied to the PDR system in step 309.

In accordance with the present invention, an error of a reference value is expressed as a state variable of a Kalman filter using the Kalman filter and this estimated state variable is fed back as an input to the system. This is called indirect feedback. That is, the error propagation characteristics of the system are maintained linearly by use of the indirect feedback Kalman filter. The step for calculating an estimate at the Kalman filter is divided into measurement update performed when a measurement is given and time propagation calculated with passage of time. In the present invention, an error of the system is corrected through feedback of an error state variable estimated by measurement updating to the system. Thus, the time propagation of the state variable on a system model is not performed after the feedback. Rather, the state variable of the Kalman filter is reset to 0 and measurement updating using a measurement is repeated in the next step.

Later-described graphs illustrate estimates of a current location or destination of a user that uses a navigation device in a composite navigation system that tightly couples the PDR system with the satellite navigation system. In the case of the tightly coupled scheme, a location error of the satellite navigation system is corrected using a Kalman filter.

FIGs. 4a to 5b are graphs illustrating filter tuning results obtained by taking into account gait characteristics according to an embodiment of the present invention. Specifically, FIGs. 4a and 4b are graphs illustrating filter tuning results obtained by taking into account gait characteristics on a straight trajectory and FIGs. 5a and 5b are graphs illustrating filter tuning results obtained by taking into account gait characteristics on a moving trajectory.

It can be noted from FIGs. 4a to 5b that GPS data approximate to an actual trajectory are tracked successfully irrespective of a heading bias error.

While the present invention has been particularly shown and described with reference to embodiments thereof, it will be understood by those of ordinary skill in the art that various changes in form and details may be made therein without departing from the spirit and scope of the present invention as defined by the following claims.

Claims

A method for measuring a location of a pedestrian terminal, the method comprising:

searching for neighboring Global Positioning System (GPS) satellites;

receiving pseudo-range information from at least one of the detected GPS satellites and storing the received pseudo-range information;

calculating a displacement of a pedestrian based on step detection from a pedestrian;

correcting the calculated displacement of the pedestrian terminal using the received pseudo-range information; and

measuring the location of the pedestrian terminal using the corrected displacement.
The method of claim 1, wherein the displacement calculation comprises calculating the displacement of the pedestrian terminal by a Pedestrian Dead Reckoning (PDR) algorithm that estimates a location of a pedestrian according to gait characteristics of the pedestrian.
The method of claim 2, wherein the displacement correction comprises:

confirming the displacement of the pedestrian by a pedestrian navigation system;

calculating a distance between the pedestrian terminal and the at least one GPS satellite using the calculated displacement of the pedestrian and orbit information about the at least one GPS satellite; and

correcting the displacement of the pedestrian using a difference between the received pseudo-range information and the calculated distance between the pedestrian terminal and the at least one GPS satellite.
The method of claim 1, wherein the reception and storing of pseudo-range information comprises receiving the pseudo-range information from the at least one of the detected GPS satellites, detecting and correcting an error of the received pseudo-range information using a filter, and storing the corrected pseudo-range information.
An apparatus for measuring a location of a pedestrian terminal, the apparatus comprising:

a user interface for interfacing with a user;

a Global Positioning System (GPS) receiver for searching for neighboring GPS satellites and receiving pseudo-range information from at least one of the detected GPS satellites; and

a controller for calculating a displacement of a pedestrian based on step detection from a pedestrian, correcting the calculated displacement of the pedestrian using the received pseudo-range information, and measuring the location of the pedestrian terminal using the corrected displacement.
The apparatus of claim 5, wherein the controller calculates the displacement of the pedestrian by a Pedestrian Dead Reckoning (PDR) algorithm that estimates a location of a pedestrian according to gait characteristics of the pedestrian.
The apparatus of claim 6, wherein the controller confirms the displacement of the pedestrian by a pedestrian navigation system, calculates a distance between the pedestrian and the at least one GPS satellite using the calculated displacement of the pedestrian terminal and orbit information about the at least one GPS satellite, and corrects the displacement of the pedestrian terminal using a difference between the received pseudo-range information and the calculated distance between the pedestrian and the at least one GPS satellite.
The apparatus of claim 5, further comprising a filter unit for detecting and correcting an error of the received pseudo-range information.
The apparatus of claim 5, wherein the controller controls selective coupling of predetermined two navigation algorithms or use of only one of the two navigation algorithms according to the number of GPS signals received through the GPS receiver.
The apparatus of claim 5, further comprising an accelerometer for measuring an acceleration of the apparatus according to a motion of the apparatus.
The apparatus of claim 5, wherein the controller comprises:

a satellite navigation algorithm executer for receiving information about a location of a user from a visible satellite and providing information about the location of the user; and

a PDR algorithm executer for estimating a location of a user according to gait characteristics of the user.
The apparatus of claim 5, wherein if the number of GPS signals received through the GPS receiver is 4 or larger, the controller uses a loosely coupled scheme in which a location and velocity of the GPS receiver are used as measurements for a coupled system.
The apparatus of claim 5, wherein if the number of GPS signals received through the GPS receiver is 3 or smaller, the controller compares strengths of the GPS signals with a predetermined threshold, and if the strengths of the GPS signals are higher than the predetermined threshold, the controller uses a tightly coupled scheme in which pseudo-range information and pseudo-range change rate information received through the GPS receiver are used as measurements.
The apparatus of claim 6, wherein if no GPS signal is received through the GPS receiver, the controller detects location information about the user using one of predetermined two navigation algorithms, the one navigation algorithm being the PDR algorithm.