JP2004252651A - Shape data encoder and shape data encoding method - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a shape data encoder and a shape data encoding method, capable of encoding shape data into a text format. <P>SOLUTION: In order to obtain the shape data having statistical deviation, a prescribed road section is sampled from map data at even intervals with a resampling section length L having a constant distance. Accordingly, a displacement difference in an absolute direction in each relative node, i.e., a difference (hereinafter referred to as a 'predicted value difference') Δθ between a deflection angle θ and a deflection angle statistical predicted value S (a predicted value represented by the deflection angle) is calculated, and the predicted value difference Δθ is set to angle information about each the relative node. By assigning a character code to a data string wherein the predicted value differences Δθ are arranged in relative node order, the angle information about the relative node is encoded into the text format. <P>COPYRIGHT: (C)2004,JPO&NCIPI

Description

[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention relates to a shape data encoding device and a shape data encoding method for encoding shape data into a text format.
[0002]
[Prior art]
A car navigation system used for a vehicle or the like uses a digital map database to display a map around the position of the own vehicle on a screen based on position data calculated from information received by a GPS receiver, or to display a traveling locus or the like. It has a function to display the route search result to the destination together with the map. It also has a function to receive traffic information such as accident information and traffic congestion information, display the point where the accident occurred, congestion section, etc. on a map, and provide route guidance using travel time etc. I have.
[0003]
As shown in FIG. 1, a digital map database used in the system stores nodes 11 and links 13 that can represent road sections. The node 11 is a reference point on a map such as an intersection or a boundary line, and the position is represented by latitude, longitude, or the like. Note that connection information with other nodes linked to indicate a road or the like is also stored as information on the node. The link 13 is a line connecting the nodes.
[0004]
In this system, a `` shape vector '' indicating a predetermined road section or the like is generated from map data stored in a digital map database in order to display a point where an accident has occurred or a congested section on a map. It is distributed to each vehicle together with event information such as traffic jams. As shown in FIG. 2, the shape vector includes a shape vector column identification number, a type of vector data such as a road, a total number of nodes and node numbers constituting the shape vector, an absolute coordinate (latitude / longitude) or a relative position of each node, and the like. Is composed of data indicating There are two types of nodes constituting the shape vector. One is a "base point node" that represents some points in a road section by absolute positions (absolute latitude / longitude and absolute azimuth), and the other is a "base node" represented by relative positions with adjacent nodes. Relative node ". Each node is obtained by sampling a road section on the map.
[0005]
In the conventional shape vector, in order to obtain shape data having a statistical bias, as shown in FIG. 3, a road shape (original shape) is sampled at regular intervals with a resampling section length L having a fixed distance. was there. In this case, since the distance between the nodes is a constant value L, only the angle information is required as the position information of each relative node, and there is an effect that the data size of the shape vector can be reduced. The angle information is roughly classified into three types shown in (a), (b), and (c) of FIG.
[0006]
First, as shown in FIG. 3A, the azimuth of the north of each relative node (upward in the figure) is 0 degree, and the magnitude is specified in the range of 0 to 360 degrees clockwise. It can be represented by the angle θ. However, in this case, as shown in FIG. 3A, no statistical bias appears in the frequency of occurrence of the angle θ. Further, as shown in FIG. 3 (b), it can be represented by a displacement difference of an absolute azimuth at each relative node, that is, a deflection angle θ. In this case, in an area where there are many straight roads, the occurrence frequency of the declination θ has a maximum at θ = 0 ° as shown in FIG.
[0007]
Further, as shown in FIG. 3C, a difference (hereinafter, referred to as a “prediction value difference”) Δθ between the argument θ at each relative node and the argument statistical prediction value S (predicted value represented by the argument). It can also be represented. The deviation angle statistical predicted value S, the deflection angle θj of interest relative node P _J, a value estimated using the argument of it to a previous relative node P _J-1. Since most road shapes are straight lines or curves that bend gently, the predicted value difference Δθ of the declination θ concentrates around 0 °, and the predicted value indicating each relative node as shown in FIG. The occurrence frequency of the difference Δθ shows a strong bias around Δθ = 0 °.
[0008]
Conventionally, variable-length encoding is performed by assigning a code consisting of 0 and 1 according to the value of the predicted value difference Δθ to the predicted value difference Δθ of the angle information obtained in this manner, particularly the declination angle θ. . FIG. 6 is an explanatory diagram illustrating an example of a code table assigned to the predicted value difference Δθ. As shown in the figure, Δθ = 0 is coded to “0”, Δθ = + 1 is coded to 1000 by adding an additional bit 0 representing + to code 100, and Δθ = −1 is − to code 100. The additional bit 1 is added and encoded to 1001.
[0009]
As described above, arithmetic processing is performed on the shape data to give a statistical bias, and then variable-length coding is performed, whereby the data amount of the shape vector can be reduced. As a specific example, a relative node can be represented by about 3 to 6 bits per node, and especially around 0 ° can be represented by about 1 to 3 bits by performing variable length coding.
[0010]
[Patent Document 1]
WO 02/091587 Pamphlet [0011]
[Problems to be solved by the invention]
By the way, the shape data obtained by the above-described conventional technique is in a binary format. However, on the other hand, a method of expressing the shape data in a text format has been desired.
[0012]
The present invention has been made in view of the above-described conventional needs, and has as its object to provide a shape data encoding device and a shape data encoding method capable of encoding shape data in a text format.
[0013]
[Means for Solving the Problems]
In order to achieve the above object, a shape data encoding device according to the present invention converts data representing a shape vector on a digital map for specifying a shape by map matching (hereinafter, referred to as “shape data”) into a text format. A shape data encoding device for encoding, wherein arithmetic processing is performed on position information of each node constituting the shape vector, the position information is converted into data having a statistical bias, and the statistically biased data is obtained. Is encoded in a text format using a code table in which a data string composed of at least one of the values having a statistically strong bias among the data having the character code corresponding to one character code. Therefore, the shape data can be encoded in a text format.
[0014]
Further, in the shape data encoding apparatus according to the present invention, the shape vector resamples each node at a position where a distance from an adjacent node is equally spaced, and the data having a statistical bias is It is desirable that the angle information is the angle information of each node constituting the sampled shape vector.
[0015]
Further, it is preferable that the shape data encoding device according to the present invention express the angle information as a linear argument extending from the adjacent node, and encode the argument in a text format.
[0016]
Further, the shape data encoding device according to the present invention represents the angle information as a difference between a deviation angle of a straight line extending from the adjacent node and a deviation statistical prediction value (hereinafter, referred to as a “prediction value difference”). It is desirable to encode the predicted value difference in a text format.
[0017]
A shape data encoding method according to the present invention encodes data representing a shape vector on a digital map composed of a plurality of nodes (hereinafter referred to as “shape data”) in a text format. The arithmetic processing is performed on the position information of each node constituting the shape vector to convert the position information into data having a statistical bias, and among the data having the statistical bias, The data is encoded in a text format using a code table in which a data string composed of at least one value having a strong bias is associated with one character code.
[0018]
Further, in the shape data encoding method according to the present invention, the shape vector is such that each node is resampled at a position where a distance from an adjacent node is equally spaced, and the data having a statistical bias is: It is angle information of each node constituting the resampled shape vector.
[0019]
In the shape data encoding method according to the present invention, the angle information is represented by a linear argument extending from the adjacent node, and the argument is encoded in a text format.
[0020]
Further, in the shape data encoding method according to the present invention, the angle information is represented by a difference between an argument of a straight line extending from the adjacent node and an argument statistical prediction value (hereinafter, referred to as a “prediction value difference”). The prediction value difference is encoded in a text format.
[0021]
BEST MODE FOR CARRYING OUT THE INVENTION
Hereinafter, embodiments of a shape data encoding device and a shape data encoding method according to the present invention will be described in detail with reference to the drawings. In the following description, an encoder having a shape data encoding device that generates a shape vector and encodes data representing the shape vector (hereinafter, referred to as “shape data”) by the shape data encoding method of the present embodiment will be described. A car navigation system including a decoder mounted on each vehicle and performing a predetermined process based on a shape vector or the like will be described.
[0022]
In the car navigation system, the decoder has a function of receiving traffic information such as accident information and congestion information from the encoder and displaying a point where an accident has occurred, a congestion section, and the like on a map. For this reason, the encoder generates a "shape vector" indicating a predetermined road section or the like from map data stored in the digital map database, and distributes the "shape vector" to the decoder of each vehicle together with event information such as an accident or traffic jam.
[0023]
In the digital map database used in the system, as shown in FIG. 1, nodes 11 and links 13 that can represent road sections are stored. The node 11 is a reference point on a map such as an intersection or a boundary line, and the position is represented by latitude, longitude, or the like. Note that connection information with other nodes linked to indicate a road or the like is also stored as information on the node. The link 13 is a line connecting the nodes.
[0024]
As shown in FIG. 2, the shape vector includes a shape vector column identification number, a type of vector data such as a road, a total number of nodes and node numbers constituting the shape vector, an absolute coordinate (latitude / longitude) or a relative position of each node, and the like. Is composed of data indicating Further, there are two types of nodes constituting the shape vector. One is a "base point node" that represents some points in a road section by absolute positions (absolute latitude / longitude and absolute azimuth), and the other is a "base node" represented by relative positions with adjacent nodes. Relative node ". Each node is obtained by sampling a road section on the map.
[0025]
In this embodiment, in order to obtain shape data (shape vector data) having a statistical bias, as shown in FIG. 3, a predetermined distance from a predetermined road section is determined from map data stored in a digital map database. Sampling is performed at the same interval with the resampling section length L. Therefore, only the angle information may be used as the position information of each relative node, but in the present embodiment, the displacement difference of the absolute azimuth at each relative node, that is, the argument θ and the argument statistical prediction value S (expressed by the argument) (Hereinafter, referred to as “predicted value difference”) Δθ, and the predicted value difference Δθ is used as angle information of each relative node.
[0026]
The deviation angle statistical predicted value S, the deflection angle θj of interest relative node P _J, a value estimated using the argument of it to a previous relative node P _J-1. Since most road shapes are straight lines or curves that bend gently, the predicted value difference Δθ of the declination θ concentrates around 0 °, and the predicted value indicating each relative node as shown in FIG. The occurrence frequency of the difference Δθ shows a strong bias around Δθ = 0 °. Therefore, most of the angle information is a value such as the predicted value difference Δθ = 0, ± 1.
[0027]
In the present embodiment, the angle information of the relative node is encoded in a text format by assigning a character code to a data string in which the predicted value difference Δθ as the angle information is arranged in the order of the relative node. FIG. 4 is an explanatory diagram illustrating an example of a code table assigned to the prediction difference value Δθ according to the present embodiment. As shown in the figure, the data sequence “0” of the predicted value difference Δθ is encoded into a character code A, “+1” is encoded into B, “−1” is encoded into C, and “0, 0” is encoded. Encode to D, encode “0, + 1” to E, encode “0, −1” to F, encode “+1,0” to G, encode “−1,0” to H I do. In addition, for any other value whose predicted difference value Δθ is other than these, it is encoded into a character string represented by + or-and a three-digit number in addition to the character code X.
[0028]
The data indicating the section length L of the equal interval resampling is encoded into a character string represented by a one-digit number in addition to the section length change code Y. The one-digit number is a value determined in advance according to the section length L, such as “1” when the section length L = 20 m and “2” when L = 40 m. Further, an EOD (End Of Data) code Z is added to the end of the shape data.
[0029]
For example, a data string “0,0,0,0,0, −1, −1,0, + 1,0,0,0,0,0,0,0” in which angle information of 26 relative nodes are arranged in order. , 0, 0, 0, 0, 0, 0, 0, 0, -42, 0 ", according to the code table shown in FIG. 4," 00, 00, 0-1, -10, +10, 00, 00, 00, 00, 00, 00, 00, -42, 0 ", and is encoded into a character string in a text format such as" DDFHGDDDDDDDX-042A ".
[0030]
Further, the base node is represented by the absolute position (absolute latitude / longitude and absolute direction) as described above, and the numerical value can be directly represented by a character code. Add a character (+ or-) to the latitude and longitude information. Note that the absolute azimuth is expressed in the range of 0 to 360 degrees clockwise, with the azimuth north of the base node being 0 degrees.
[0031]
Therefore, the position of the base node is 35 ° 53′23 ″ 9 north latitude, 135 ° 15′43 ″ 2 east longitude, the absolute azimuth to the next relative node is 143 °, and the equidistant resample is performed with the section length L = 40 m. The relative node angle information is “0,0,0,0,0, −1, −1,0, + 1,0,0,0,0,0,0,0,0,0,0,0, The shape vector of “0, 0, 0, 0, −42, 0” is encoded into a character string in a text format such as “+ 135515432 + 355329143Y2DDFHGDDDDDDDX-042AZ”. That is, the character string can be divided into "+135515432, +3553239, 143, Y2DDFHGDDDDDDDX-042A, Z", "+135154432" is the latitude information of the base node, "+3553239" is longitude information of the base node, and "143" is the base point The absolute azimuth information of the node, “Y2DDFHGDDDDDDDX-042A” indicates the position information of the relative node, and “Z” indicates the EOD code.
[0032]
As described above, the shape data encoded in the text format is distributed from the encoder to the decoder of each vehicle together with event information such as an accident or traffic congestion. On the decoder side, the received shape data is decoded into shape data according to the rules of the code table shown in FIG. 4, and the map data stored in the digital map database of the decoder and the shape vector indicated by the decoded shape data are converted. After the map matching, the shape vector is displayed over the map.
[0033]
FIG. 5 is a configuration diagram illustrating the car navigation system of the present embodiment described above. As shown in the figure, the car navigation system according to the present embodiment includes an encoder 200 and a decoder 300, and transmits shape data described later from the encoder 200 to the decoder 300.
[0034]
The encoder 200 includes an event information input unit 201, a shape vector extraction unit 203, a digital map database 205, a shape data encoding unit 207 corresponding to the shape data encoding device according to the claims, and a code table storage. Unit 209 and a shape data transmission unit 211. The decoder 300 has a shape data receiving unit 301, a shape data decoding unit 303, a code table storage unit 305, a digital map database 307, a map matching unit 309, and a display unit 311.
[0035]
Hereinafter, each component of the encoder 200 and the decoder 300 included in the car navigation system of the present embodiment will be described. First, the event information input unit 201 of the encoder 200 is for inputting event information such as an accident or traffic congestion. The shape vector extraction unit 203 extracts a shape vector corresponding to the event information input to the event information input unit 201 from the digital map database 205.
[0036]
Further, the shape data encoding unit 207 performs, as described above, resampling of the shape data at equal intervals, encoding to the text format, and the like. A code table as shown in FIG. 4 is stored in the code table storage unit 209, and encoding into a text format by the shape data encoding unit 207 is performed according to the code table. The shape data transmitting unit 211 transmits the shape data encoded in the text format by the shape data encoding unit 207 to the decoder 300.
[0037]
Next, the shape data receiving unit 301 included in the decoder 300 receives the shape data transmitted from the encoder 200. The shape data decoding unit 303 decodes the shape data received by the shape data receiving unit 301 and specifies a shape vector. The code table as shown in FIG. 4 is also stored in the code table storage unit 305 of the decoder 300, and the shape data is decoded by the shape data decoding unit 303 according to the code table.
[0038]
Further, the map matching unit 309 performs a map matching between the shape vector specified by the shape data decoding unit 303 and the map data stored in the digital map database 307. The display unit 311 displays the shape vector subjected to the map matching so as to be superimposed on the map of the digital map database 307.
[0039]
As described above, according to the car navigation system including the shape data encoding device that encodes the shape data by the shape data encoding method of the present embodiment, the encoder side converts the shape vector data (shape data) into text. Format. When the shape data is in the text format, the data can be transmitted more stably than in the binary format when the network between the encoder and the decoder is the Internet. Further, even if the encoder or the decoder is a personal computer or the like, it is possible to flexibly use the shape data.
[0040]
In the present embodiment, the angle information of each relative node is described as the predicted value difference Δθ, but the declination θ shown in FIG. 3B may be used as the angle information.
[0041]
【The invention's effect】
As described above, according to the shape data encoding device and the shape data encoding method according to the present invention, the position information of each node constituting the shape vector on the digital map for specifying the shape by map matching is arithmetically added. Processing is performed to convert the position information into statistically biased data, and among the statistically biased data, a data sequence composed of at least one value having a statistically strong bias is obtained. Since the data is encoded in a text format using a code table corresponding to one character code, the shape data can be encoded in a text format.
[Brief description of the drawings]
FIG. 1 is an explanatory diagram showing an example of a shape vector. FIG. 2 is an explanatory diagram showing a data string of a shape vector. FIG. 3 is a diagram showing angle information of each relative node of a shape vector resampled at equal intervals with a section length L. FIG. 4 is an explanatory diagram showing an example of a code table assigned to a predicted difference value Δθ of the embodiment. FIG. 5 is a configuration diagram showing a car navigation system of an embodiment. FIG. 6 is a diagram showing a predicted value difference Δθ. Diagram showing an example of a code table to be assigned by means of [Description of code]
200 Encoder 300 Decoder 201 Event information input unit 203 Shape vector extraction unit 205, 307 Digital map database 207 Shape data encoding unit 209, 305 Code table storage unit 211 Shape data transmission unit 301 Shape data reception unit 303 Shape data decoding unit 309 Map matching unit 311 Display unit

Claims (8)

A shape data encoding device that encodes data representing a shape vector on a digital map (hereinafter, referred to as “shape data”) for specifying a shape by map matching into a text format,
The position information of each node constituting the shape vector is subjected to arithmetic processing to convert the position information into data having a statistical bias,
The data string composed of at least one of the statistically strongly biased values of the statistically biased data is encoded in a text format using a code table corresponding to one character code. A shape data encoding apparatus characterized in that the shape data is encoded. The shape vector resamples each node at a position where the distance from the adjacent node is at equal intervals,
The shape data encoding apparatus according to claim 1, wherein the data having a statistical bias is angle information of each node constituting the resampled shape vector. The angle information is represented by a declination of a straight line extending from the adjacent node,
3. The shape data encoding device according to claim 2, wherein the argument is encoded in a text format. The angle information is represented by a difference between the argument of a straight line extending from the adjacent node and the argument statistical prediction value (hereinafter, referred to as “prediction value difference”),
3. The shape data encoding device according to claim 2, wherein the prediction value difference is encoded in a text format. A shape data encoding method for encoding data representing a shape vector on a digital map composed of a plurality of nodes (hereinafter, referred to as “shape data”) into a text format,
The position information of each node constituting the shape vector is subjected to arithmetic processing to convert the position information into data having a statistical bias,
The data string composed of at least one of the statistically strongly biased values of the statistically biased data is encoded in a text format using a code table corresponding to one character code. A shape data encoding method characterized in that: The shape vector, each node is resampled at a position where the distance from the adjacent node is equidistant,
6. The shape data encoding method according to claim 5, wherein the statistically biased data is angle information of each node constituting the resampled shape vector. The angle information is represented by a declination of a straight line extending from the adjacent node,
7. The shape data encoding method according to claim 6, wherein the argument is encoded in a text format. The angle information is represented by a difference between the argument of a straight line extending from the adjacent node and the argument statistical prediction value (hereinafter, referred to as “prediction value difference”),
7. The shape data encoding method according to claim 6, wherein the prediction value difference is encoded in a text format.

Images