TWI472716B - Use the map of the indoor positioning method - Google Patents

Description

Indoor location method using map

The present invention relates to indoor positioning, and more particularly to an indoor positioning method using a map.

Press, GPS is mostly used for driving navigation. With the advancement of technology, the satellite receiver of the global positioning system has been integrated into mobile devices (such as smart phones), making the global positioning system no longer limited to driving navigation, but also applicable to personal walking positioning, such as pedestrian walking records. Device. However, the use of GPS has its limitations, that is, it must be used in outdoor environments where the sky is not obscured, and satellite receivers can receive satellite positioning signals. When indoors, the global positioning system cannot be located due to the obscuration of the building. Therefore, the user can only know the approximate location through other positioning technologies (such as the A-GPS technology commonly used in smart phones) indoors. However, in a large indoor space (such as an exhibition hall or museum), if the precise location is not known, the positioning technology will not be extended to indoor applications.

In view of this, the main object of the present invention is to provide an indoor positioning method using a map, which can calculate the relative position of the user on a map.

In order to achieve the above object, the present invention provides an indoor positioning method using a map, which is applied to an arithmetic device including a displacement sensing unit. The device is provided for the user to hang on the body, and the method comprises the following steps:

A. Obtaining a plurality of position information detected by the displacement sensing unit, and establishing a movement track of the user according to the position information, each of the position information includes a moving distance and a rotation angle.

B. A link-node model of a map having a plurality of nodes; each node has a node edge between each adjacent node.

C. detecting a plurality of characteristic turns in the moving track by the rotation angle of the moving track, and sequentially arranging into a feature steering sequence; each of the two adjacent feature turns has a first edge.

D. comparing the angles of the nodes with the angle of the feature steering to find a plurality of possible paths that conform to the steering sequence of the feature; wherein each of the possible paths has a plurality of corner nodes, and the angle pairs of the corner nodes The angle at which the features are turned in the feature steering sequence; each of the two adjacent corner nodes has a second edge, and the second edge includes at least one of the node edges.

E. Perform an alignment step according to the lengths of the first edge lines and the angles of the corner nodes, and the lengths of the second edge lines and the angles of the features, to find the possible paths. A possible path that is most similar to the movement trajectory.

The present invention further provides an indoor positioning method using a map, which is applied to An arithmetic device comprising a displacement sensing unit for the user to be attached to the body, the method comprising the following steps:

A. Obtain a plurality of position information detected by the displacement sensing unit, and establish a movement track of the user according to the position information.

B. Obtain a link-node model of a map.

C. Find a plurality of possible paths that match the movement trajectory from the connected node model.

D. Perform an alignment step to find a possible path that is most similar to the movement trajectory from the possible paths.

Thereby, by using the indoor positioning method of the map, the relative position of the user on the map can be effectively matched to achieve the effect of indoor positioning.

In order that the present invention may be more clearly described, the preferred embodiments are illustrated in the accompanying drawings.

The indoor positioning method using the map according to a preferred embodiment of the present invention is applied to an arithmetic device, which is provided for the user to hang around the waist, and includes a displacement sensing unit capable of detecting the moving distance and the steering angle. . The indoor positioning method using the map includes the following steps as shown in FIG. 1:

A. Detecting a plurality of position information of the user while traveling through the displacement sensing unit, wherein each of the position information includes a moving distance and a rotation angle. After obtaining the location information, the user travels based on the location information A moving track in the middle.

B. The map used in this embodiment is a map with a scale. The map is converted into a link-node model, and a plurality of nodes in the connected node model and a length of a node edge between each two adjacent nodes are obtained.

For example, referring to FIG. 2A, the intersection of the lines is the node. Each node represents every turn on the map, and each node edge represents the aisle on the map. Then, using a Rotaton Matrix algorithm, the angles of the nodes are calculated from the connected node model.

C. detecting a plurality of characteristic turns in the moving track by the rotation angle of the moving track, and sequentially arranging into a feature steering sequence; each of the two adjacent feature turns has a first edge.

For example, taking the movement trajectory shown in FIG. 2B as an example, the persons indicated by A′, B′, C′, and D′ in FIG. 2B are feature directional, and each line segment constituting the movement trajectory is the first Sideline.

Since the user is walking, the steering is not only performed when the corner is encountered. In many cases, the user may move back and forth. Therefore, the rotation angle in the position information includes the steering caused by the movement back and forth. Defined as a false turn) and a true turn (defined as a feature turn). In this embodiment, the user's fake rotation is excluded by a sliding window algorithm. To detect, to obtain the characteristics of the user. When the standard deviation of the rotation angles of the position information of the user in a window is higher than a predetermined value, it is determined that the feature is turned, wherein the predetermined value is estimated in advance by the straight-line route test. Then, each of the detected features is sequentially recorded and arranged into the feature steering sequence.

For example, referring to FIG. 3, the rotation angles of the position information detected by the user's movement track are sequentially 0, 0, 15, 60, and 90 degrees, and the predetermined value is 30, and the sliding window is Each window has a size of 3. The first window of the sliding window is 0, 0, and 15 degrees, and the standard deviation is 8.6, which is lower than the predetermined value of 30, and is judged to be straight. The second window is 0, 15, 60 degrees, and its standard deviation is 31, which is higher than the predetermined value 30, and is judged to be a characteristic turn. The third window is 15, 60, 90 degrees, and its standard deviation is 37, which is higher than the predetermined value of 30, and is judged to be a characteristic turn.

After the steering of the features is obtained, the length of each first edge can be calculated by using the moving distance measured by the displacement sensing unit.

D. Comparing the angles of the nodes with the angle of the feature steering to find a plurality of possible paths that conform to the steering sequence of the feature. Wherein, the nodes in each of the possible paths that meet the angle of the steering of the features are defined as corner nodes, and the angles of the corner nodes correspond to the angles of the features in the feature steering sequence. Each of the possible paths has a second edge between each two adjacent corner nodes, and each of the second edges includes at least one node edge. The possible path shown in Figure 2A is For example, those represented by A, B, C, and D in FIG. 2A are corner nodes, and each line segment constituting the possible path is the second edge. The length of each second edge is the sum of the lengths of the node edges that make up the second edge.

E. Perform an alignment step according to the lengths of the first edge lines and the angles of the corner nodes, and the lengths of the second edge lines and the angles of the feature turns, to find out the possible paths. One of the possible paths most similar to the movement trajectory.

In this embodiment, a shape screening step, an angle screening step, and a proportional screening step are utilized to remove possible paths of low similarity. Wherein: the shape screening step is used to compare a shape similarity between the shape of each possible path and the shape of the moving track, and remove possible paths in the possible paths whose shape similarity is lower than a predetermined value of a shape. The shape screening step includes: separately calculating a centroid of each of the possible paths and the moving track.

Produces a plurality of straight lines through individual centroids.

The number of intersections of each of the possible paths and the straight lines passing through the centroid thereof, and the number of intersections of the moving trajectories with the straight lines passing through the centroid thereof are calculated and recorded in a one-dimensional array, respectively.

For example, please refer to FIG. 4 , which takes the moving trajectory of FIG. 2B as an example, and calculates the number of intersections of the straight lines passing through the centroids of the centroids with the moving trajectory, and generates one every 18 degrees from 0 degrees. A straight line produces a total of 10 straight lines. The number of intersections of the straight lines with the moving track, recording In one of the dimensional arrays shown in FIG.

Comparing each of the possible paths with the one-dimensional array of the moving trajectory to generate the shape similarity; and removing possible paths in the possible paths whose shape similarity is lower than the predetermined value of the shape, if the number of remaining possible paths is one , then keep the possible path.

The angle screening step is used to compare an angle similarity between the angle of the corner node of each possible path and the angle of the characteristic steering of the moving track, and remove the possibility that the angle similarity of the possible paths is lower than a predetermined value of an angle path. The angle screening step includes: converting the possible paths and the moving track into a chain code.

The angles of the respective corner nodes and the direction of each second edge are obtained from each of the chain codes of the possible paths; the angle of each feature turn and the direction of each first edge are obtained from the chain code of the moving track.

For example, taking one of the possible paths shown in FIG. 5 as an example, the possible path can be converted into a chain code according to the defined direction: 000011100. From the chain code shown in Figure 5, the angles of the two corner nodes can be obtained, respectively 90 degrees and -90 degrees; the directions of the two second edges are 0 degrees, 90 degrees and 0 degrees, respectively.

Comparing the angle of the corner node of each of the possible paths with the angle of the characteristic steering of the moving track to generate the angular similarity; Removing possible paths in which the angle similarities are lower than the predetermined value of the angle, and removing the angle similarities in the possible paths from the angle predetermined value and the direction of each second edge is different from the moving track A possible path in the direction of the first side line, wherein if the number of remaining possible paths is one, the possible path is retained.

The ratio screening step is configured to compare a proportional similarity between the length of each second edge of each possible path and the length of each first edge of the moving track, and remove the proportional similarity in the possible paths. A possible path for a predetermined value. The ratio screening step includes: calculating a length of each first edge of the moving track and a normalized edge ratio and storing the first vector as a first vector, wherein the normalized edge ratio is the length of the first edge divided by Moves the total length of all first edges.

Calculating a length of each second edge of each possible path and a normalized edge ratio and storing the second edge as a second vector, wherein the normalized edge ratio is the length of the second edge divided by a second of the possible paths The total length of the edges.

For example, taking the chain code shown in FIG. 5 as an example, the total length of the second edge is 9, and the length of the first edge (ie, 0000 in the chain code) is 4, and the normalized edge ratio is 4. /9; the second edge (ie, 111 in the chain code) has an edge length of 3 and a normalized edge ratio of 3/9; the third edge (ie, 00 in the chain code) has an edge length of 2, which The normalized edge ratio is 2/9

A second vector of each of the possible paths is compared to a first vector of the moving trajectory to produce the proportional similarity. The proportional similarity is calculated by L-p norm.

The possible paths in which the proportional similarities in the possible paths are lower than the predetermined value of the ratio are removed, wherein if the number of remaining possible paths is one, the possible paths are retained.

Thereby, through the indoor positioning method using the map described above, the possible path closest to the user's movement trajectory can be obtained, which can correspond to the position of the user on the map. In addition, since the existing angle component exists in the shape screening step described above, in practice, for a simple map, the angle screening step may not be used in the comparison step, and the shape screening step and the proportional screening step may be directly performed. The screening of possible paths can also find one of the possible paths that is most similar to the moving trajectory.

In the foregoing embodiment, the map used is a map drawn in proportion, and such a map is not easily available to the general public. In general, maps that are readily available (such as a plan view) are usually not drawn to scale. In an embodiment, a map that is not drawn to scale may be used as the positioning, and only a conversion step is added in step B above to calculate nodes of two adjacent nodes in the joint node model of the map that is not drawn to scale. The actual length of the edge. The conversion step includes: obtaining a joint node model of the map that is not drawn to scale, and performing the A plurality of motion tests are performed to obtain a plurality of test tracks, each of which includes a plurality of test turns, and each of the two adjacent test turns has a test turn edge.

The length of each test turn edge is obtained from the test tracks.

The original length of each node edge is obtained from the joint node model of the map that is not drawn to scale.

The original length of each node edge is the length of the corresponding test turn edge to obtain the actual length of each node edge.

In the case where the starting position is known together, in the joint node model, the node connected to the initial position is found, and the original length of the node edge of the initial position to the node to which it is connected is obtained. Then, from the test tracks, the test turn connected to the initial position is found. Since the aforementioned test steering system corresponds to the aforementioned node, only the original length of the node edge line connected to the initial position, corresponding to the length of the aforementioned test steering edge line, can be obtained between the initial position and the connected node. The true length of the node edge.

Then, the node is used as the other starting position, and the corresponding correspondence is repeated until the original lengths of all the node edges are completed, and the true length of all the node edges in the connected node model can be obtained. This allows you to convert unscaled maps into scaled maps.

In practice, the method of obtaining the connected node model of the map may be stored in the computing device in advance, or may be used online, in addition to being calculated by the computing device. The computing device (such as a smart phone) is connected to a server and downloaded to the computing device.

Through the indoor positioning method using the map of the present invention, the relative position of the user on the map can be effectively matched, thereby achieving the effect of positioning within the fixed position.

The above is only a preferred embodiment of the present invention, and equivalent changes to the scope of the present invention and the scope of the patent application are intended to be included in the scope of the present invention.

1 is a flow chart of a method for positioning an indoor using a map according to a preferred embodiment of the present invention; FIG. 2A is a schematic diagram of a connected node model, and discloses a possible path; FIG. 2B is a schematic diagram of a moving track; FIG. 3 is a sliding window algorithm detecting feature. Turning to the schematic diagram; FIG. 4 is a schematic diagram of the one-dimensional array generated by the shape screening step; and FIG. 5 is a schematic diagram of the possible path conversion into a chain code.

Claims (12)

An indoor positioning method using a map is applied to an arithmetic device including a displacement sensing unit, the arithmetic device is provided for the user to be attached to the body, and the method comprises the following steps: A. obtaining the displacement sensing unit Detecting a plurality of position information, and establishing a movement track of the user according to the position information, each position information includes a moving distance and a rotation angle; B. obtaining a link-node model of a map The joint node model has a plurality of nodes; each of the two adjacent nodes has a node edge; C. detects a plurality of characteristic turns in the moving track by the rotation angle of the moving track, and sequentially arranges a feature steering sequence; each of the two adjacent feature turns has a first edge; D. an angle of the node and an angle of the feature to find a plurality of possible paths that conform to the feature steering sequence; Wherein each of the possible paths has a plurality of corner nodes, and the angles of the corner nodes correspond to angles of the features in the feature steering sequence; each two phases Between the adjacent corner nodes, there is a second edge line, the second edge line includes at least one of the node edge lines; and E, according to the length of the first edge lines and the angles of the corner nodes, and the lengths of the second edge lines The angles of the features are turned, and a comparison step is performed to find out the most A similar possible path; wherein the map is an unscaled map, and step B includes a conversion step for calculating the actual length of each node edge in the connected node model. The indoor positioning method using the map according to claim 1, wherein the converting step comprises the following steps: obtaining a plurality of test tracks, each of the test tracks includes a plurality of test turns; and each of the two adjacent test turns has a test Turning to the edge line; obtaining the length of each test turning edge line from the test tracks; obtaining the original length of each node edge line from the joint node model; and making the original length of each node edge line the length of the corresponding test turning edge line To get the actual length of each node's edge. An indoor positioning method using a map is applied to an arithmetic device including a displacement sensing unit, the arithmetic device is provided for the user to be attached to the body, and the method comprises the following steps: A. obtaining the displacement sensing unit Detecting a plurality of position information, and establishing a movement track of the user according to the position information, each position information includes a moving distance and a rotation angle; B. obtaining a link-node model of a map The joint node model has a plurality of nodes; each of the two adjacent nodes has a node edge; C. detects a plurality of characteristic turns in the moving track by the rotation angle of the moving track, and sequentially arranges a characteristic steering sequence; each two adjacent The sign has a first edge; D. an angle of the node and an angle of the feature to find a plurality of possible paths that conform to the feature steering sequence; wherein each of the possible paths has a plurality of corners a node, and the angles of the corner nodes correspond to angles of the features in the feature steering sequence; each of the two adjacent corner nodes has a second edge, the second edge includes at least one of the node edges; and And performing an alignment step according to the lengths of the first edge lines and the angles of the corner nodes, and the lengths of the second edge lines and the angles of the features, to find out from the possible paths. a possible path that is most similar to the moving trajectory; wherein the step of comparing E includes: a shape screening step for comparing a shape similarity between a shape of each of the possible paths and a shape of the moving trajectory, and Removing a possible path in which the shape similarity is lower than a predetermined value of the shape; an angle screening step for comparing the angle of the corner node of each of the possible paths with the movement The feature of the trajectory turns to an angular similarity of the angle, and removes possible paths in which the angular similarity is lower than a predetermined value of an angle; and a proportional screening step for comparing each second of each possible path a proportional similarity between the length of the edge line and the length of each first edge of the moving track, and removing the possible paths in which the proportional similarities are lower than a predetermined value; wherein, if the foregoing steps are remaining The number of possible paths is one, then it is retained The possible path. An indoor positioning method using a map according to claim 3, wherein the shape screening step comprises the steps of: separately calculating each of the possible paths and a centroid of the moving track; generating a plurality of straight lines passing through the individual centroids; The number of intersections of the possible paths with the straight lines passing through their centroids, and the number of intersections of the moving trajectories with the straight lines passing through their centroids, and respectively recorded in a one-dimensional array; comparing the possibilities a one-dimensional array of paths and the movement trajectory to produce the shape similarity; and removing possible paths in the possible paths where the shape similarity is lower than a predetermined value of the shape. An indoor positioning method using a map according to claim 3, wherein the angle screening step comprises the steps of: converting the possible paths and the moving track into a chain code individually; each of the possible paths The angle of each corner node and the direction of each second edge are obtained in the chain code; the angle of each feature steering and the direction of each first edge are obtained from the chain code of the moving track; and the corner nodes of each possible path are compared An angle of the angle of the movement of the moving trajectory to produce the angular similarity; and removing the possibility that the angular similarity of the possible paths is lower than the predetermined value of the angle a path, and removing possible paths in which the angular similarity is higher than the predetermined value of the angle and the direction of each second edge is different from the direction of each first edge of the moving track. An indoor positioning method using a map according to claim 3, wherein the proportional screening step comprises the steps of: calculating a length of each first edge of the moving track and a normalized edge ratio and storing the first vector as a first vector; Comparing the length of each second edge of each possible path with a normalized edge and storing it as a second vector; comparing the second vector of each possible path with the first vector of the moving track to generate the proportional similarity And removing possible paths in which the proportional similarities are below a predetermined value of the ratio. An indoor positioning method using a map is applied to an arithmetic device including a displacement sensing unit, the arithmetic device is provided for the user to be attached to the body, and the method comprises the following steps: A. obtaining the displacement sensing unit Detecting a plurality of position information, and establishing a movement track of the user according to the position information, each position information includes a moving distance and a rotation angle; B. obtaining a link-node model of a map The joint node model has a plurality of nodes; each node has a node edge (edge); C. detecting a plurality of characteristic turns in the moving track by the rotation angle of the moving track, and sequentially arranging into a feature steering sequence; each of the two adjacent features has a first edge between the turns; D. An angle of the nodes and an angle of the feature steering to find a plurality of possible paths that conform to the steering sequence of the feature; wherein each of the possible paths has a plurality of corner nodes, and the angles of the corner nodes correspond to the feature steering sequence The angle at which the features are turned; each of the two adjacent corner nodes has a second edge, the second edge includes at least one of the node edges; and E, according to the length of the first edge and the corner nodes An angle, and a length of the second edge line and an angle of the feature steering, performing a comparison step for finding a possible path that is most similar to the moving track from the possible paths; wherein, the step The step of comparing E includes: a shape screening step for comparing a shape similarity between the shape of each possible path and the shape of the moving track, and removing the possible paths a possible path that is lower than a predetermined value of a shape; and a proportional screening step for comparing a length of each second edge of each of the possible paths with a length of each first edge of the moving track Similarity, and removing the possible paths in which the proportional similarities are lower than a predetermined value; wherein if the number of possible remaining paths in the foregoing steps is one, the possible paths are retained. An indoor positioning method using a map according to claim 7, wherein the shape screening step comprises the steps of: individually calculating each of the possible paths and a centroid of the moving track; generating a plurality of straight lines passing through the individual centroids; The number of intersections of the possible paths with the straight lines passing through their centroids, and the number of intersections of the moving trajectories with the straight lines passing through their centroids, and respectively recorded in a one-dimensional array; comparing the possibilities a one-dimensional array of paths and the movement trajectory to produce the shape similarity; and removing possible paths in the possible paths where the shape similarity is lower than a predetermined value of the shape. The indoor positioning method using the map according to claim 7, wherein the proportional screening step comprises the steps of: calculating a length of each first edge of the moving track and a normalized edge ratio and storing the first vector as a first vector; Comparing the length of each second edge of each possible path with a normalized edge and storing it as a second vector; comparing the second vector of each possible path with the first vector of the moving track to generate the proportional similarity And removing possible paths in which the proportional similarities are below a predetermined value of the ratio. An indoor positioning method using a map, which is applied to include a sense of displacement An arithmetic device of the measuring unit, the computing device is provided for the user to be attached to the body, and the method comprises the following steps: A: obtaining a plurality of position information detected by the displacement sensing unit, and establishing the use according to the position information a moving trajectory; B, obtaining a link-node model of a map; C, finding a plurality of possible paths conforming to the moving trajectory from the connected node model; and D, performing a comparison a step of finding, by the possible paths, a possible path that is most similar to the moving track; wherein the connected node model has a plurality of nodes, and each node has an edge between each adjacent node; The map is an unscaled map; step B includes a conversion step for calculating the actual length of each node edge in the joint node model. An indoor positioning method using a map according to claim 10, wherein the step C includes a steering detection step for detecting a plurality of feature steerings in the moving track, and in the C, the connected node model is used in the method Find the possible paths that match the angle at which the features are turned. An indoor positioning method using a map according to claim 11, wherein each of the two adjacent feature turns has a first edge; each of the possible paths has a plurality of corner nodes, and each of the two adjacent corner nodes Having a second edge; the comparison step includes: a shape screening step for comparing the shape of each of the possible paths with the moving track a shape similarity of the shape of the trace, and removing possible paths in which the shape similarity is lower than a predetermined value of the shape; an angle screening step for comparing the angle of the corner node of each possible path with the moving track Characterizing the angle of similarity of the angle of view and removing possible paths in which the angular similarity is below a predetermined value of an angle; and a proportional screening step for comparing each second edge of each of the possible paths a ratio of the length to the length of each first edge of the movement trajectory, and removing the possible paths in which the proportional similarities are lower than a predetermined value; wherein, if the remaining steps are If the number of possible paths is one, the possible path is retained.