Encoding data generation method and device

In a coded data generation method of resampling a road shape for setting a plurality of nodes, arranging position information of each node represented by a deflection angle from the immediately preceding node to generate a data string of the deflection angles, converting the deflection angles into predicted difference values each indicating the difference from the predicted value, and variable-length coding the data string of the predicted difference values, the data string of the predicted difference values when the deflection angles are converted into the predicted difference values is evaluated and a prediction expression to calculate the predicted value is selected adaptively from among a plurality of prediction expressions φ=1, φ=2, φ=3, and φ=4 based on the evaluation result. The prediction expression to calculate the predicted value is selected adaptively in response to road shape A, B, C, D, so that the data compression effectiveness is enhanced.

TECHNICAL FIELD

This invention relates to a generation method of coded data representing a road position, etc., on a digital map and an apparatus for generating and decoding the coded data and is intended for reducing the data amount of the coded data.

BACKGROUND ART

Hitherto, VICS (Vehicle Information Communication System) has conducted the service for providing vehicle information indicating a congestion zone and the travel time through FM multiplex broadcasting and beacon for a vehicle navigation system installing a digital map database. The vehicle navigation system receives the vehicle information and displays a colored congestion zone on a map displayed on a screen and calculates the required time to the destination for display.

Thus, to provide the vehicle information, it becomes necessary to pass position information of a road on a digital map. It is also necessary to report the recommended route and the run locus on a digital map to the associated party in the service for receiving the information on the current location and the destination and providing information on the recommended route through which the destination will be reached in the shortest time and a vehicle information collection system (probe information collection system) for collecting locus information, speed information, etc., from a running vehicle (probe car) advanced in study in recent years.

Hitherto, to report the road position on the digital map, generally the link numbers assigned to roads and the node numbers determining nodes such as intersections have been used. However, the node numbers and the link numbers defined in a road network need to be replaced with new numbers with new construction or change of a road and the digital map data produced by each company must also be updated accordingly and thus the system using the node numbers and the link numbers involves an enormous social cost for maintenance.

To improve such a point, JP-A-2003-23357 discloses a method of reporting the road position on the digital map without using the node numbers or the link numbers and in a small data amount.

In this method, sampling points are again set at given intervals in the road zone on the digital map to be reported (called “equal-distance resample”) and compression coding processing is performed for the data string with the position data of the sampling points arranged in order, and the compressed and coded data is transmitted. At the reception party receiving the data, the data string of the position data of the sampling points is reconstructed and the road shape is reproduced on the digital map of the reception party. Using the position data, position determination and position reference are carried out (map matching) on the digital map of the reception party for determining the road zone, as required.

The compression coding for the data string of the position data is performed in the order of (1) conversion of position data to a single variable, (2) conversion of the value represented by the single variable to a value having a statistical bias, and (3) variable-length coding of the provided value as described later:

(1) Conversion of Position Data to a Single Variable

FIG. 26(a) represents sampling points in a road zone set in equal-distance resample as PJ-1and PJ. This sampling point (PJ) is uniquely determined by two dimensions of distance (resample length) L from the adjacent sampling point (PJ-1) and angle Θ. Assuming that the distance is constant (L), the sampling point (PJ) can be represented by the single variable of only the angle component Θ from the adjacent sampling point (PJ-1). InFIG. 26(a), as the angle Θ, the angle Θ based on “absolute azimuth” with the due north azimuth (upper part of the drawing) as 0 degrees and the magnitude specified clockwise in the range of 0 to 360 degrees is shown (absolute azimuth from the due north). When xy coordinates (latitude, longitude) of PJ-1and PJ are (xj−1, yj−1) and (xj, yj), the angle Θ can be calculated according to the following expression:
Θj−1=tan−1{(xj−xj−1)/(yj−yj−1)}

Therefore, the road zone can be represented by the data string of the angle components of the sampling points by indicating the constant distance L between the sampling points and the latitude and longitude of the sampling point as the start or the termination (reference point) separately.

(2) Conversion of a Single Variable Value to a Value Having a Statistical Bias

As shown inFIG. 26(b), the angle component of each sampling point is represented by the displacement difference from the angle component of the adjacent sampling point, namely, “deflection angle” θj so that the single variable values of the sampling point become statistically biased values suited for variable-length coding. The deflection angle θj is calculated as
θj=Θj−Θj−1
If the road is linear, the deflection angles θ of the sampling points concentrate on the vicinity of 0 and become data having a statistical bias.

The angle component of the sampling point can be converted into data having a statistical bias by representing the deflection angle θj of an attention sampling point PJ by difference value (predicted difference value or predicted error) Δθj from predicted value Sj of the sampling point PJ predicted using deflection angles θj−1, θj−2, . . . of the preceding sampling points PJ-1, PJ-2, . . . as shown inFIG. 26(c). The predicted value Sj, for example, can be defined as
Sj=θj−1
or can be defined as
Sj=(θj−1+θj−2)/2
The predicted difference value Δθj is calculated as
Δθj=θj−Sj
If the road is curved at a constant curvature, the predicted difference values Δθ of the sampling points concentrate on the vicinity of 0 and become data having a statistical bias.

FIG. 26(d) is a graph to show the data occurrence frequency when a linear road zone is displayed as the deflection angle θ and a curvilinear road zone is displayed as the predicted difference value Δθ. The maximum appears at θ (or Δθ)=0° and the occurrence frequency of θ and Δθ has a statistical bias.

Next, the data string values converted into values having a statistical bias are variable-length coded. Various types of variable-length coding method such as a fixed numeric value compression method (0 compression, etc.,), a Shannon-Fano code method, a Huffman code method, an arithmetic code method, and a dictionary method exist; any method may be used.

Here, the case where the most general Huffman code method is used will be discussed.

In this variable-length coding, highly frequently occurring data is coded with a small number of bits and less frequently occurring data is coded with a large number of bits for reducing the total data amount. The relationship between the data and code is defined based on a code table.

Now, assume that a list of Δθ at the sampling points of a road zone represented in 1° units is

The case where a code table shown inFIG. 27combining variable-length coding and run-length coding is used to code the data string will be discussed. The code table defines as follows: Minimum angle resolution (δ) is set to 3° and the representative angle of Δθ in the range of −1° to +1° is 0° and is represented as code “0” and when five successive occurrences of 0° exist, they are represented as code “100” when 10 successive occurrences of 0° exist, they are represented as code “1101.” The code table also defines as follows: The representative angle of Δθ in the range of ±2° to 4° is ±3° and when the value is +, additional bit “0” is added to code “1110” and when the value is −, additional bit “1” is added to code “1110.” The representative angle of Δθ in the range of ±5° to 7° is ±6° and additional bit indicating positive or negative is added to code “111100.” The representative angle of Δθ in the range of ±8° to 10° is ±9° and additional bit indicating positive or negative is added to code “111101.”

Thus, the above-mentioned data string is coded as follows:

At the reception party receiving the data, the data string of Δθ is reconstructed using the same code table as that used for coding, and processing opposite to that at the transmission party is performed for reproducing the sampling point position data.

The data is thus coded, whereby the data amount of the coded data can be reduced.

JP-A-2003-23357 mentioned above proposes a method of setting distance L2of equal-distance resample short in a zone B where the curvature of the road shape is large and setting distance L1of equal-distance resample long in a linear zone A with a small curvature, as shown inFIG. 28. The reason is that if a largely curved road with a large curvature is resampled at a long distance, it becomes impossible to place a sampling point at a position indicating the characteristic road shape, the reproducibility of the road shape at the reception party worsens, and the possibility that erroneous matching may occur becomes high.

Thus, the value that can be taken by resample length Lj in each zone j (quantization resample length) is preset to, for example, 40/80/160/320/640/1280/2560/5120 meters, Lj is found according to the following expression using curvature radius ρj of the zone j, and the quantization resample length closest to the value is determined the resample length Lj:
Lj=ρj·Kr(where Kr is a fixed parameter)

The method disclosed in JP-A-2003-23357 mentioned above was tried using the following three prediction expressions:

Prediction expression 1: Sj=0: Deflection angle is used as it is (substantially prediction is not conducted)

Prediction expression 2: Sj=θj−1: Deflection angle of the preceding node is used

Prediction expression 3: Sj=(θj−1+θj−2)/2: Deflection angle average value of the preceding and preceding preceding nodes is used

Consequently, the compression efficiency of prediction expression 1 was high on average, but to examine the target roads separately, the compression efficiency of prediction expression 2 or 3 was high in some roads.

Specifically, often prediction expression 2 or 3 was suited in roads including a large number of long and gentle curves, such as an express highway; often prediction expression 1 was suited in ordinary roads.

To make a comparison between prediction expressions 2 and 3 of prediction expressions of the same kind, often prediction expression 3 compared a little favorably with prediction expression 2 in compression efficiency.

It is an object of the invention to provide a coded data generation method of efficiently compressing data and generating coded data of a road shape, etc., on a digital map and provide an apparatus for generating the coded data and decoding the coded data.

DISCLOSURE OF THE INVENTION

As a result of considering the above-described points, the following results were introduced:In a “gentle curve” portion of an express highway, etc., a comparatively small curvature becomes almost constant over a long distance. Thus, focusing attention on one small zone, the curvature of the part can be very easily predicted from the upstream zone curvature. Thus, prediction expression 2 or 3 for predicting the deflection angle of the zone using the deflection angle of the preceding or preceding preceding node is suited.Particularly, prediction expression 3 is prediction using the average curvature of the upstream preceding and preceding preceding zones, and the curvature error for each zone is smoothed. Therefore, highly accurate prediction is made possible in a “gentle curve over a long distance” as mentioned above.

However, if the curve zone is comparatively short, as compared with prediction expression 2, prediction expression 3 receives the effect of an upstream longer zone and thus prediction on the periphery of the start or end part of the curve (=periphery of the part where the curvature changes) easily fails. As the effect is received, if the curve zone is comparatively short, prediction expression 2 compares favorably with prediction expression 3 in some cases.On the other hand, in ordinary roads, of ten the road is curved at right angle in an intersection, etc., or if a curve exists, a comparatively large curvature is applied only at a short distance. This means that it is difficult to predict the curvature of one small zone from the curvature of the upstream preceding zone and if the curvature of one small zone is predicted, the prediction easily fails. In such a case, prediction expression 1 of substantially conducting no prediction (using the deflection angle intact) is suited.

Taking a survey of the whole roads from the try results described above, it was seen that generally the efficiency of prediction expression 1 (using the deflection angle intact without conducting prediction) is good, but prediction expression 2 or 3 (for predicting the curvature of the corresponding point from the upstream curvature) is suited in some roads focusing attention on the discrete roads or road zones.

Based on the points described above, in the invention, in a coded data generation method of resampling a linear object having a linear shape for setting a plurality of nodes, arranging position information of each node represented by a deflection angle from the immediately preceding node to generate a data string of the deflection angles, converting the deflection angles into predicted difference values each indicating the difference from the predicted value, and variable length coding the data string of the predicted difference values, a prediction expression to calculate the predicted value is selected from among a plurality of prediction expressions.

Thus, the prediction expression to calculate the predicted value is selected dynamically, whereby the effectiveness of data compression can be enhanced. Particularly, in the described configuration, the data string of the predicted difference values when the deflection angles are converted into the predicted difference values is evaluated and a prediction expression is selected based on the evaluation result.

The coded data generation method described above can include the following steps (1) to (6):

(1) Step of resampling a linear object for setting a plurality of nodes.

(2) Step of arranging position data of each node represented by a deflection angle from the immediately preceding node to generate a data string of the deflection angles.

(3) Step of providing a plurality of prediction expressions to calculate a predicted value of the position data of each of the nodes based on the data string of the deflection angles.

(4) Step of calculating the predicted value using a predetermined prediction expression of the plurality of prediction expressions.

(5) Step of converting the data string of the deflection angles into a data string of predicted difference values each indicating the difference from the calculated predicted value.

(6) Step of variable-length coding the data string of the predicted difference values to provide the coded data.

The coded data generation method can further include the steps of acquiring the data strings of the predicted difference values corresponding to the plurality of prediction expressions for each of the plurality of prediction expressions according to the step (5); evaluating the data strings of the predicted difference values; and selecting the predetermined prediction expression in the step (4) from among the plurality of prediction expressions based on the evaluation result of the evaluating step.

In the coded data generation method of the invention, the plurality of prediction expressions contain a prediction expression with 0 as a predicted value.

Usually, the prediction expression can be used to provide efficient data compression.

The plurality of prediction expressions can contain at least one prediction expression implemented as a function using at least one deflection angle preceding an attention deflection angle as a parameter.

In the coded data generation method of the invention, the plurality of prediction expressions contain a prediction expression with the deflection angle in the immediately preceding node as a predicted value.

If the prediction expression is used on the periphery of a gentle curve, efficient data compression can be provided.

In the coded data generation method of the invention, the plurality of prediction expressions contain a prediction expression with the average or the weighted average of a plurality of preceding deflection angles as a predicted value.

If the prediction expression is used on the periphery of a gentle curve, efficient data compression can be provided.

In the coded data generation method of the invention, the plurality of prediction expressions contain a prediction expression with the angle resulting from inverting the positive or negative sign of the deflection angle of the immediately preceding node as a predicted value.

If the resample shape is a zigzag trace, efficient data compression can be provided by using the prediction expression.

In the coded data generation method of the invention, all deflection angles contained in the data string of the deflection angles are converted into predicted difference values, the data string of the predicted difference values is evaluated, and a prediction expression to convert all deflection angles into predicted difference values is selected based on the evaluation result.

The prediction expression can be changed dynamically in the shape data units of a linear object for enhancing the data compression effectiveness.

In the coded data generation method of the invention, each deflection angle contained in the data string of the deflection angles corresponding to a part zone of the linear object is converted into a predicted difference value and the data string of the predicted difference values is evaluated, and a prediction expression to convert the deflection angles corresponding to the part zone into predicted difference values is selected based on the evaluation result.

The prediction expression can be changed dynamically at the midpoint of the shape data of the linear object for furthermore enhancing the data compression effectiveness.

In the coded data generation method of the invention, the data string of the deflection angles is classified according to state transition patterns and a prediction expression to convert the deflection angles into predicted difference values is selected in the pattern units.

To adopt the mode, the prediction expression suited for each pattern can be selected.

In the coded data generation method of the invention, the data string of the deflection angles is classified into blocks each containing a predetermined number of data pieces of the deflection angles and a prediction expression to convert the deflection angles into predicted difference values is selected for each of the blocks.

To adopt the mode, the selected prediction expression appears in the units of the given number of data pieces in the coded data, so that it becomes unnecessary to insert a marker code into the coded data.

In the coded data generation method of the invention, the data string of the deflection angles is classified into blocks matching the change points of the resample length of the resampling and a prediction expression to convert the deflection angles into predicted difference values is selected for each of the blocks.

The characteristic of the shape data often changes at the change point of the resample length. Thus, to adopt the mode, the prediction expression matching the characteristic of the shape data can be selected.

In the coded data generation method of the invention, a prediction expression to convert the attention deflection angle into a predicted difference value is selected in response to the evaluation result for the data string of the predicted difference values of a predetermined number of deflection angles preceding the attention deflection angle in the data string of the deflection angles.

The mode can be realized as both the encoding and decoding parties set a rule based on a program.

Here, as many deflection angles as the predetermined number may be converted into a plurality of data strings of predicted difference values using the plurality of selection expressions and only if the evaluation result for the data string of the predicted difference values based on a predetermined selection expression satisfies a predetermined requirement, the currently used prediction expression may be changed to the predetermined prediction expression and then the attention deflection angle may be converted into a predicted difference value.

In the attention deflection angle or block, a prediction expression may be selected with reference to the prediction expression selection state in the deflection angles or blocks preceding and following the attention deflection angle or block.

In the attention deflection angle or block, if a prediction expression different from the prediction expressions adopted in the deflection angles or blocks preceding and following the attention deflection angle or block is selected, a penalty value may be added to the evaluation value of the evaluation criterion of the predicted difference value string in the attention deflection angle or block. The penalty value can be set in response to the occurrence frequency of each prediction expression.

In the coded data generation method of the invention, the data string of the predicted difference values is evaluated according to the number of 0s contained in the data string and the prediction expression with the largest number of 0s is selected.

Thus, the data concentrates on 0 and the data compression effectiveness provided by variable-length coding is enhanced.

In the coded data generation method of the invention, the data string of the predicted difference values is evaluated according to the statistical value (variance, standard deviation, etc.) of the predicted difference values contained in the data string and the prediction expression with the variance or standard deviation becoming the smallest is selected.

Thus, the data is statistically biased and the data compression effectiveness provided by variable-length coding is enhanced.

In the coded data generation method of the invention, the evaluation value for each predicted difference value is preset in response to the occurrence frequency of the predicted difference value and the data string of the predicted difference values is evaluated according to the sum value of the evaluation values the predicted difference values contained in the data string.

When the occurrence frequency of the predicted difference value is the evaluation value, the prediction expression with the largest sum value is selected.

When the code length of the predicted difference value is the evaluation value, the prediction expression with the smallest sum value is selected.

In the invention, a coded data generation apparatus includes a shape data resample processing section for resampling a linear object for setting a plurality of nodes and arranging position data of each node represented by a deflection angle from the immediately preceding node to generate a data string of the deflection angles; a prediction expression determination section, when the data string of the deflection angles is converted into predicted difference values indicating the difference from a predicted value to predict the position data of each of the nodes, for evaluating the data string of the predicted difference values and selecting a prediction expression to calculate the predicted value from among a plurality of prediction expressions based on the evaluation result; and a variable-length coding processing section for converting each deflection angle contained in the data string of the deflection angles generated by the shape data resample processing section into a predicted difference value from the predicted value calculated using the prediction expression determined by the prediction expression determination section and variable-length coding a data string of the predicted difference values.

The apparatus can carry out the coded data generation method described above and can efficiently compress the data amount of the coded data.

In the invention, a coded data reconstruction apparatus includes a coded data decoding section for decoding variable-length coded data representing position information of a linear object and reproducing shape data containing a data string of difference values each indicating the difference between a deflection angle and a predicted value; a prediction expression determination section for determining the prediction expression used to calculate the predicted value from the provided shape data; and a shape data reconstruction section for calculating a predicted value using the prediction expression determined by the prediction expression determination section and reproducing position information of nodes of the linear object from the data string of the predicted difference values provided by the coded data decoding section.

The apparatus can reproduce the position information of the linear object from the coded data of the position information of the linear object.

Further, the invention also contains a program for causing a computer to execute generation of code data provided by coding a linear object. The program causes the computer to execute the steps of resampling a linear object for setting a plurality of nodes and arranging position data of each node represented by a deflection angle from the immediately preceding node to generate a data string of the deflection angles; when the data string of the deflection angles is converted into predicted difference values indicating the difference from a predicted value to predict the position data of each of the nodes, evaluating the data string of the predicted difference values; selecting a prediction expression to calculate the predicted value from among a plurality of prediction expressions based on the evaluation result; and converting each deflection angle contained in the data string of the deflection angles generated by a shape data resample processing section into a predicted difference value from the predicted value calculated using the determined prediction expression and variable-length coding a data string of the predicted difference values.

Further, the invention also contains a program for causing a computer to decode code data representing a linear object. The program causes the computer to execute the steps of decoding variable length coded data representing position information of a linear object and reproducing shape data containing a data string of difference values each indicating the difference between a deflection angle and a predicted value; determining the prediction expression used to calculate the predicted value from the provided shape data; and calculating a predicted value using the determined prediction expression and reproducing position information of nodes of the linear object from the provided data string of the predicted difference values. To generate coded data, the coded data generation method of the invention can efficiently compress data.

The apparatus of the invention can carry out the coded data generation method and can effectively compress and code the shape data of a linear object and can reconstruct the original shape data from the coded data.

BEST MODE FOR CARRYING OUT THE INVENTION

In a coded data generation method in an embodiment of the invention, to code a road shape on a digital map of one example of a linear object and generate coded data, the coded data is generated roughly in the order of:(a) resampling of the road shape at the resample length responsive to the curvature radius of the road(b) conversion of position data at sampling point (node) to deflection angle θ(c) conversion of the position data represented by the deflection angle θ to a value having a statistical bias(d) variable-length coding of the provided value.

Resampling of the road shape in (a) is executed according to the method described in JP-A-2003-23357 and the linear object is resampled for setting a plurality of nodes. For the conversion to deflection angle θ in (b), the position data of each node is represented as the angle component according to the method described in JP-A-2003-23357 and then the angle component is converted into the deflection angle θ.FIGS. 2(a), (b), and (c) show (deflection angle) data strings representing the position data in the nodes of the shape data of object roads A, B, and C (which will be hereinafter referred to as “deflection angle strings”). Each row is made up of 10 pieces of data, and the data numbers are shown at the left end. The numeral enclosed in < > in the deflection angle string is the resample length change code indicating the quantization code of the resample length, and the numeric values to the right of the code are representations each of the position data of each node provided by resampling at the resample length of the code as the deflection angle θ (deg). The position data of each node is represented as the deflection angle from the immediately preceding node, and the pieces of the position data are collected to generate the deflection angle data string.

The conversion of the position data to a value having a statistical bias in (c) is processing of adaptively using a calculation expression of a predicted value Sj (prediction expression) for predicting the value of position data to calculate Sj and converting the deflection angle θ in the deflection angle string into the difference value from the predicted value Sj (predicted difference value).

The variable-length coding in (d) is processing of variable-length coding of the predicted difference value (predicted error) of the shape data converted into predicted difference value string and is performed according to the method described in JP-A-2003-23357.

Therefore, the coded data generation method is characterized by the position data conversion processing in (c).

In the position data conversion processing in (c), any of the following four prediction expressions (φ=1, φ=2, φ=3, φ=4) is used to predict the predicted value Sj. The expressions are provided and are recorded in predetermined memory, etc.

That is, the position data of each node j is represented as the deflection angle θj, and the predicted value is 0.

That is, the position data of each node j is represented as (θj−θj−1).

That is, the position data of each node j is represented as {θj−(θj−1+θj−2)/2}.

That is, the position data of each node j is represented as (θj+θj−1).

If φ=2 or φ=3 is used when the position data of each underscored curve part in the deflection angle string inFIG. 2, high compression efficiency is provided.

φ=2, φ=3, φ=4 is implemented as a function using at least one deflection angle preceding the attention deflection angle as a parameter.

In φ=2, the deflection angle immediately preceding the attention deflection angle is used as the predicted value.

In φ=3, the average of the two deflection angles preceding the attention deflection angle is used as the predicted value. However, the number of the deflection angles preceding the attention deflection angle is arbitrary, and a weighted average like (aθj−1+bθj−2)/(a+b) may be used as the predicted value (a and b are each a real number larger than 0).

In φ=4, the angle of the deflection angle immediately preceding the attention deflection angle with the sign provided by inverting the positive or negative sign of the deflection angle immediately preceding the attention deflection angle is used as the predicted value.

As shown inFIG. 3, the resample shape (solid line) may show a zigzag in the bend part of the road shape (dotted line); if φ=4 is used when the position data of such a part is converted, high compression efficiency is provided. If the angle resolution δat the resampling time is set and the road shape is traced, the angles that can be used are limited and thus the zigzag phenomenon inevitably occurs (inevitability involved in angle quantization). In the deflection angle string inFIG. 2(a), the position data of the parts where a zigzag phenomenon occurs are displayed as italic characters.

If φ=1 is used when the road shape is close to a line (containing the case where if a curve exists, it immediately reaches the end and the case where the road is almost a line and the angle is occasionally corrected), high compression efficiency is provided. To convert the position data of a usual road shape, φ=1 is used.

The prediction expression of the predicted value Sj used for conversion processing of the deflection angle θ is selected dynamically in response to the road shape. To select the prediction expression,(1) a mode of dynamically selecting a prediction expression for each object road (called “object road unit selection mode”)(2) a mode of detecting the pattern of the deflection angle string of the object road and selecting a prediction expression in the pattern unit (called “pattern unit selection mode”)(3) a mode of dividing the deflection angle string of the object road into blocks each made up of a given number of data pieces and selecting a prediction expression in the block unit (called “block unit selection mode”)(4) a mode of selecting a prediction expression each time the resample length change code is changed in the deflection angle string of the object road (called “resample length linkage mode”)(5) a mode of selecting a prediction expression in accordance with a program rule from the situation in the N pieces of position data upstream from the attention position data in the deflection angle string of the object road (called “sequential selection mode”)
and the like are considered. Which mode is to be used needs to be predetermined between the transmission party and the reception party.

FIG. 1schematically shows the relationship between each prediction expression selected in the resample length linkage mode and the road shape. The road shape is indicated by the dotted line, the resample shape is indicated by the solid line, and the resample length change points are indicated by <M1>, <M2>, and <M3>. φ=1 is selected in range A in which the road shape is linear; φ=4 is selected in range B in which a zigzag phenomenon occurs; φ=2 or φ=3 is selected in curve range C; and φ=1 is selected in range D in which the road shape is undetermined.

Next, the processing in each mode will be discussed in detail.

(1) Object Road Unit Selection Mode

A flowchart ofFIG. 4shows a processing procedure in the object road unit selection mode. The shape data of the object road is acquired from a digital map database (step1), and the position data of each node generated in resample is represented as the deflection angle θ and a deflection angle string is generated (step2).

The processing at step2is performed according to a procedure shown inFIG. 5in detail. That is, the angle resolution δ at each deflection angle of each resample length is preset (step21), the shape data of the object road is converted into a curvature function (step22), and the resample length L of each zone is determined from the curvature (step23). Next, the object road is resampled according to the representative angle of the angle resolution δresponsive to the resample length L and the deflection angle (step24), and the shape data of the object road is converted into a deflection angle string of a list of resample zone length change code and deflection angle quantization values (step25).

Upon completion of generation of the deflection angle string, the prediction expressions φ=1, φ=2, φ=3, and φ=4 are applied to the whole deflection angle string of the object road, the deflection angle θ in the deflection angle string is converted into the difference value from the predicted value Sj (predicted difference value), and which prediction expression is optimum is determined (step3). The processing at step3is performed according to a procedure shown inFIG. 6in detail. That is, the deflection angle string to be evaluated (in the object road unit selection mode, the whole deflection angle string of the object road) is acquired (step31), the prediction expressions are used in order starting at φ=1 (step32), the predicted value Sj is calculated according to each prediction expression, the deflection angle θ in the deflection angle string is converted into a predicted difference value string represented as predicted difference value (=Δθj=θj−Sj) (step33), and the evaluation value of the deflection angle string is calculated (step34).

The evaluation value is calculated as below in (i) to (iii):(i) The number of 0s contained in the predicted difference value string is used as the evaluation value and higher evaluation is given to the predicted difference value string having a larger number of 0s (the prediction expression containing the greatest number of 0s is selected).(ii) The calculation value of the statistical value of data contained in the predicted difference value string (for example, variance, standard deviation, etc.) is used as the evaluation value and higher evaluation is given to the predicted difference value string having smaller variance or standard deviation.(iii) The score responsive to the occurrence frequency is preset in data appearing in the predicted difference value string, the cumulative value resulting from adding the scores of the data appearing in the predicted difference value string to be evaluated is used as the evaluation value, and evaluation responsive to the cumulative value is given. In a Huffman table inFIG. 7, the occurrence frequency (or occurrence probability) of each angle is described and shorter code is assigned to the angle having the higher occurrence frequency. To add the value of the corresponding occurrence frequency in the table in response to the angle appearing in the predicted difference value string to be evaluated, the cumulative value is used as the evaluation value and higher evaluation is given to the predicted difference value string having the higher cumulative value. To add the code length of the angle in response to the angle appearing in the predicted difference value string to be evaluated, the cumulative value is used as the evaluation value and higher evaluation is given to the predicted difference value string having the smaller cumulative value. Such a score table corresponding to the occurrence frequencies is previously possessed, whereby the evaluation in (iii) is also possible if variable-length coding other than the Huffman coding is performed.

All prediction expressions are used to perform the processing at steps33and34and upon completion of the processing (step35,36), the prediction expression of the best evaluation value is determined (step37). That is, for each of the prediction expressions φ=1, φ=2, φ=3, and φ=4, the corresponding predicted difference data value string is generated and the data strings are evaluated.

The prediction expression of the best evaluation value is thus selected and the deflection angle θ in the deflection angle string is converted into the predicted difference value from the predicted value calculated according to the prediction expression (step4) and the whole shape data converted into the predicted difference value string is compressed by variable-length coding (step5). The used prediction expression is defined for the provided coded data (step6).

FIG. 8shows the data format of the coded data generated according to the object road unit selection mode. Here, the data representing the used prediction expression is inserted before the shape data main body of the object road.

A flowchart ofFIG. 9shows a processing procedure of reproducing the shape data of the object road from the coded data. The shape data subjected to the variable length decoding processing is taken out from the coded data (step41), a header is referenced for determining the prediction expression (step42), the angle data read from the shape data is converted into the deflection angle according to the prediction expression (step43), and the shape data of the object road is reproduced (step44).

(2) Pattern Unit Selection Mode

A flowchart ofFIG. 10shows a processing procedure in the pattern unit selection mode. Shape data acquiring (step51) and resample and deflection angle string conversion processing (step52) are similar to those in the object road unit selection mode (FIGS. 4 and 5).

The provided deflection angle string is scanned, a curve pattern (underscore portion inFIG. 2) to which φ=2 or φ=3 is to be applied where P or more data pieces of non-0 having the same positive or negative sign are successive or a zigzag pattern (italic portion inFIG. 2(a)) to which φ=4 is to be applied where Q or more data pieces of the same absolute value with an alternating pattern of positive and negative signs are successive is extracted, and the deflection angle string data is classified into pattern groups and a group not belonging to any patterns to which φ=1 is to be applied (step53). The prediction expression of the best evaluation value is selected for each group and the deflection angle string is converted into-a-predicted difference value string (step54). At this time, if the best prediction expression corresponding to one group is not uniquely determined, a plurality of prediction expressions are applied to the deflection angle string of the group and the prediction expression of the best evaluation value is determined according to the procedure inFIG. 6.

Next, the whole shape data converted into the predicted difference value string is compressed by variable-length coding (step55), and the used prediction expression is defined for the provided coded data for each group (step56).

In the embodiment, the deflection angle data strings are classified into blocks (groups) corresponding to state transition patterns of the deflection angles. The optimum prediction expression is selected for each block.

FIG. 11shows the data format of the coded data generated according to the pattern unit selection mode. Here, the prediction expression initial value representing the prediction expression used in the first group is inserted before the shape data main body of the object road, and preceding the position data of each subsequent group, a prediction expression marker indicating prediction expression insertion and the prediction expression number of the prediction expression used in the group are inserted.

A flowchart ofFIG. 12shows a processing procedure of reproducing the shape data of the object road from the coded data (decoding method of the coded data). The shape data subjected to the variable-length decoding processing is taken out from the coded data (step61), the number of the angle data read from the shape data is set to the initial value and the first used prediction expression is set to the prediction expression represented by the prediction expression initial value (step62), the corresponding angle data is read from the shape data (step63), and whether or not prediction expression change code is inserted before the angle data is determined (step64). If prediction expression change code is not inserted, the setup prediction expression is used as it is (step66), and the angle data is converted into the deflection angle according to the prediction expression (step67). If prediction expression change code is inserted, the prediction expression is changed to a new prediction expression specified by the code (step65), and the angle data is converted into the deflection angle according to the prediction expression (step67). Such processing is performed for all angle data (steps68and69) and the shape data of the object road is reproduced (step70).

In the mode, the data string of the deflection angles corresponding to a part zone of the linear object (road shape) rather than the whole is converted into a data string of the predicted difference values and the optimum prediction expression for converting the deflection angles corresponding to the part zone into the predicted difference values is selected based on the evaluation result of the data string of the predicted difference values. This philosophy is adopted common to the modes in (3) to (5) described below.

(3) Block Unit Selection Mode

A flowchart ofFIG. 13shows a processing procedure in the block unit selection mode. Shape data acquiring (step71) and resample and deflection angle string conversion processing (step72) are similar to those in the object road unit selection mode (FIGS. 4 and 5).

For example, one block is made up of 10 pieces of data on one row of the deflection angle string shown inFIG. 2, the prediction expressions φ=1, φ=2, φ=3, and φ=4 are applied to the deflection angle string in the block units for converting the deflection angle θ in the deflection angle string into predicted difference values, and which prediction expression is optimum is determined (step73). The evaluation method is the same as that in the object road unit selection mode (FIG. 6). The prediction expression of the best evaluation value is selected for each block and the deflection angle string is converted into a predicted difference value string (step74), the whole shape data converted into the predicted difference value string is compressed by variable-length coding (step75), and the used prediction expression is defined for the provided coded data for each block (step76).

FIG. 14shows the data format of the coded data generated according to the block unit selection mode. Here, the prediction expression initial value representing the prediction expression used in the first block is inserted before the shape data main body of the object road, and preceding the position data of each subsequent block, the prediction expression number is inserted. Since the insertion position of the prediction expression number is automatically determined by the number of data pieces contained in the block, a prediction expression marker need not be inserted.

A flowchart ofFIG. 15shows a processing procedure of reproducing the shape data of the object road from the coded data. The shape data subjected to the variable-length decoding processing is taken out from the coded data (step81), the number of the block read from the shape data is set to the initial value and the first used prediction expression is set to the prediction expression represented by the prediction expression initial value (step82), the angle data in the block is read from the shape data (step83), and the angle data is converted into the deflection angle according to the prediction expression defined in the block (step84). Such processing is performed for all blocks (steps85and86) and the shape data of the object road is reproduced (step87).

In the mode, the predetermined number of data pieces of the deflection angles contained in one block is 10, but the number can be changed as desired.

(4) Resample Length Linkage Mode

A flowchart ofFIG. 16shows a processing procedure in the resample length linkage mode. Shape data acquiring (step91) and resample and deflection angle string conversion processing (step92) are similar to those in the object road unit selection mode (FIGS. 4 and 5).

In the deflection angle string shown inFIG. 2, the angle data existing between one resample length change code and the next resample length change code (two resample length change points), resampled at the same resample length is one block (block between the numerals enclosed in < >), the prediction expressions φ=1, φ=2, φ=3, and φ=4 are applied to the deflection angle string in the block units for converting the deflection angle θ in the deflection angle string into predicted difference values, and which prediction expression is optimum is determined (step93). The evaluation method is the same as that in the object road unit selection mode (FIG. 6). The prediction expression of the best evaluation value is selected for each block and the deflection angle string is converted into a predicted difference value string (step94), the whole shape data converted into the predicted difference value string is compressed by variable-length coding (step95), and the used prediction expression is defined for the provided coded data for each block (step96).

FIG. 17shows the data format of the coded data generated according to the resample length linkage mode. Here, the prediction expression initial value representing the prediction expression used in the first block is inserted before the shape data main body of the object road, and the prediction expression number of the prediction expression used in each subsequent block is defined in zone length information following a zone length marker, inserted into the start position of the angle data resampled at the same resample length.

A flowchart ofFIG. 18shows a processing procedure of reproducing the shape data of the object road from the coded data. The shape data subjected to the variable-length decoding processing is taken out from the coded data (step101), the number of the block of the same resample length read from the shape data is set to the initial value (step102), all angle data contained in the block with the same resample length and the prediction expression associated with the resample length change code are acquired (step103), and the angle data in the block is converted into the deflection angle according to the prediction expression (step104). Such processing is performed for all blocks each with the same resample length (steps105and106) and the shape data of the object road is reproduced (step107).

(5) Sequential Selection Mode

A flowchart ofFIG. 19shows a processing procedure in the sequential selection mode. Shape data acquiring (step111) and resample and deflection angle string conversion processing (step112) are similar to those in the object road unit selection mode (FIGS. 4 and 5).

The number of angle data extracted from a deflection angle string is set to initial value and the first used prediction expression is set to φ=1 (step113). The corresponding angle data and a predetermined number of (here, P) samples upstream from the angle data are extracted from the deflection angle string (step114), the prediction expressions φ=1, φ=2, φ=3, and φ=4 are applied to the deflection angle string made up of the extracted data for converting the deflection angle θ in the deflection angle string into predicted difference values, and prediction expression of the best evaluation value φnew is selected (step115). The evaluation method is the same as that in the object road unit selection mode (FIG. 6).

Based on the evaluation result, whether or not the already setup prediction expression needs to be changed is determined according to the prediction expression change condition (step116). That is, in the mode, while the upstream shape of the position data to be coded is referenced, whether or not the optimum prediction expression used for the position data is to be changed is determined.

As the change condition, for example, the following (i) or (iii) condition is set:

(i) If evaluation value difference Δ between the currently used prediction expression φ and the prediction expression φnew is greater than a predetermined value, the prediction expression is changed.

(ii) If a state in which higher evaluation is given to the prediction expression φnew rather than the currently used prediction expression φ continues Q times or more, the prediction expression is changed.

If the change condition is not satisfied, the already setup prediction expression is used as it is (step118), and the angle data is converted into predicted difference value (step119). If the change condition is satisfied, the prediction expression is changed to the prediction expression φnew (step117), and the angle data is converted into predicted difference value (step119). Such processing is performed for all angle data (steps120and121) and the whole shape data converted into the predicted difference value string is compressed by variable-length coding (step122).

The prediction expression change rule is determined in the program defining the coding processing.

In the embodiment, a prediction expression for converting the attention deflection angle into the predicted difference value is selected in response to the evaluation result for the data string of the predicted difference values of the predetermined number of (P) deflection angles preceding the attention deflection angle. Further, only if the evaluation result satisfies the predetermined requirement, the currently used prediction expression is changed to a predetermined prediction expression.

FIG. 20shows the data format of the coded data generated according to the sequential selection mode. Since the coded data does not contain information specifying a prediction expression, the data amount is also small. The prediction expression used in decoding is selected based on the rule of the program defining the decoding of the coded data.

A flowchart ofFIG. 21shows a processing procedure of reproducing the shape data of the object road from the coded data. The shape data subjected to the variable-length decoding processing is taken out from the coded data (step131), the number of the angle data read from the shape data is set to the initial value, and the first used prediction expression is set to φ=1 (step132). The corresponding angle data and the P samples upstream from the angle data are read (step133), the prediction expressions φ=1, φ=2, φ=3, and φ=4 are applied to the deflection angle string made up of the read data for converting the deflection angle θ in the deflection angle string into predicted difference values, and prediction expression of the best evaluation value φnew is selected (step134). Next, based on the evaluation result, whether or not the already setup prediction expression needs to be changed is determined according to the prediction expression change condition (step135). If the change condition is not satisfied, the already setup prediction expression is used as it is (step137), and the angle data is converted into a deflection angle according to the prediction expression (step138). If the change condition is satisfied, the prediction expression is changed to the prediction expression φnew (step136), and the angle data is converted into a deflection angle according to the prediction expression (step138). Such processing is performed for all angle data (steps139and140) and the shape data of the object road is reproduced (step141).

Thus, to generate the coded data of the road shape, the prediction expression used for calculating the predicted value to convert the position data into a predicted difference value is selected adaptively for each road or for each road portion, whereby the data amount of the coded data can be compressed efficiently.

By the way, in the modes in (1) to (4) described above, to change the prediction expression in one shape data, it becomes necessary to incorporate information of “explicitly describing prediction expression change and specifying the prediction expression ID” in data. This can result in one factor of an increase in the data amount. Further, for example, when “although generally prediction expression 1 is good in the whole road zone, another prediction expression is good instantaneously,” it is not much desirable to frequently change the prediction expression. To at least change the prediction expression, it is desirable that “the data amount reduction effect provided by adopting a new prediction expression” should be over “the loss involved in changing the prediction expression.”

Then, it is considered that “change penalty” is added to “the evaluation value provided by each prediction expression” and “whether or not the prediction expression is to be changed” is determined according to the evaluation result. In other words, it is considered that the prediction expression change is provided with hysteresis.

FIG. 22is a drawing to show a total evaluation method of the evaluation values provided by the prediction expressions and the change penalty involved in changing the prediction expression.

InFIG. 22(a), as the prediction expression is changed, the data amount can be reduced and the data transmission efficiency can be enhanced and therefore the prediction expression is changed. On the other hand, inFIG. 22(b), as the prediction expression is not changed, good transmission efficiency is provided and therefore the prediction expression is not changed.

If the numbers of data classification blocks and deflection angles increase, a combination optimization problem such that “what combination is most efficient?” occurs. As the numbers of blocks and deflection angles increase, it becomes difficult to find out an optimal solution easily and rapidly.

Then, as a method of finding out a quasi-optimal solution rapidly, the following two modes are possible:

(i) The change penalty is made relatively small for a highly frequently occurring prediction expression and is made large for a less frequently occurring prediction expression. If a less frequently occurring prediction expression is adopted, the possibility that the prediction expression may be changed to another prediction expression in the next block is large and therefore change to the less frequently occurring prediction expression is suppressed.

(ii) Usually, processing is performed in order in one direction and thus the downstream situation is estimated from the upstream result of the attention block and the change penalty is changed dynamically.

Further, it is considered that the optimum prediction expression occurrence frequency changes according to the compression rate. For example, if the compression rate is raised, there is a trend for the regularity of the deflection angles to disappear and for φ=1 to become an optimum expression. In contrast, if the compression rate is lowered, there is a trend to enhance the regularity of the deflection angles and for φ=2 or φ=3 to become an optimum expression.

Therefore, in (i), it is considered that a method of “once calculating the evaluation value of each prediction expression for the whole shape data and determining the change penalty in response to the evaluation value” is good.

FIG. 23is a drawing to show a method of dynamically varying the change penalty involved in changing the prediction expression.

FIG. 24shows the configurations of an information transmission apparatus (coded data generation apparatus)20for executing the coded data generation method to report the vehicle information object road and an information utilization apparatus (coded data reconstruction apparatus)40such as a vehicle-installed navigation system or a personal computer to make the most of the provided vehicle information. The information transmission apparatus20includes an event information input section21to which congestion information and traffic accident information are input, a shape data extraction section23for extracting the road shape data in the object road zone of vehicle information from a digital map database A22, a shape data resample processing section26for resampling the road shape data extracted in the shape data extraction section23and generating a deflection angle string of node position data, a prediction expression determination section25for determining a prediction expression to convert the deflection angle string into a predicted difference value string, a variable-length coding processing section28for converting the deflection angle of the shape data into a predicted difference value using the prediction expression determined by the prediction expression determination section25and performing compression and coding, a compressed data storage section27for storing the compressed and coded road shape data and providing the stored data for an external medium, and a shape data transmission section29for transmitting the compressed and coded road shape data.

On the other hand, the information utilization apparatus40includes a shape data reception section41for receiving the provided road shape data, a coded data decoding section42for decoding the compressed and coded data, a prediction expression determination section47for identifying the prediction expression used at the conversion time to the predicted difference value, a shape data reconstruction section43for reconstructing the shape data using the prediction expression identified by the prediction expression determination section47, a map matching section45for performing map matching using data in a digital map database B46and determining a road zone represented by node points on a digital map, and an information utilization section44for making the most of the provided information.

In the information transmission apparatus20, the shape data extraction section23extracts the road shape data of the object road, and the shape data resample processing section26resamples the road shape data and generates a deflection angle string of the road shape data. The prediction expression determination section25determines the prediction expression to convert the deflection angle string into a predicted difference value string according to the “object road unit selection mode,” the “pattern unit selection mode,” the “block unit selection mode,” the “resample length linkage mode,” or the “sequential selection mode” described above. The variable-length coding processing section28calculates a predicted value according to the prediction expression determined by the prediction expression determination section25, subtracts the predicted value from each deflection angle in the deflection angle string to generate a predicted difference value string, and variable-length codes the predicted difference value string.

The road shape data compressed by variable-length coding is recorded on an external medium and is provided, or is transmitted from the shape data transmission section29.

In the information utilization apparatus40receiving the road shape data, the coded data decoding section42decodes the compressed and coded data. The prediction expression determination section47identifies the prediction expression to decode the deflection angle from the provided data, and the shape data reconstruction section43reproduces the deflection angle string using the prediction expression and converts each deflection angle into latitude and longitude data to reproduce the road shape data. The resample shape concatenating the nodes reproduced is superposed on the digital map for display on a screen of the information utilization apparatus40.

To accurately determine the road zone, the map matching section45performs map matching between the position data of the node point reproduced and the map data in the digital map database B46and determines the object road on the digital map data. The information utilization apparatus40can also implement a car navigation receiver or a map display terminal.

FIG. 25shows the configurations of a probe car installed machine (coded data generation apparatus)60for executing the coded data generation method to report the run locus and a probe information collection center (coded data reconstruction apparatus)50for collecting probe information. The probe car installed machine60includes a home vehicle position determination section61for determining the home vehicle position based on information received from a GPS antenna73and detection information of a gyro74, a digital map database69, a run locus storage section62for storing the run locus of the home vehicle, a run locus shape resample processing section63for resampling the run locus and generating a deflection angle string of node position data, a prediction expression determination section68for determining a prediction expression to convert the deflection angle string into a predicted difference value string, a variable-length coding processing section64for converting the deflection angle of the run locus shape data into a predicted difference value using the prediction expression determined by the prediction expression determination section68and performing compression and coding, a compressed data storage section65for storing the compressed and coded run locus shape data, and a run locus transmission section66for transmitting the compressed and coded run locus shape data.

On the other hand, the probe information collection center50includes a run locus reception section51for receiving the run locus shape data provided by the probe car installed machine60, a coded data decoding section52for decoding the compressed and coded reception data, a prediction expression determination section55for identifying the prediction expression used at the conversion time to the predicted difference value, a run locus shape reconstruction section53for reconstructing the run locus shape using the prediction expression identified by the prediction expression determination section55, and a run locus and measurement information utilization section54for making the most of the run locus and measurement information collected from the probe car installed machine60to generate vehicle information.

The home vehicle position detected in the home vehicle position determination section61is stored in the run locus storage section62of the probe car installed machine60in sequence as the run locus. The run locus shape resample processing section63reads the run locus data stored in the run locus storage section62, resamples the run locus, and generates a deflection angle string of the run locus shape data. The prediction expression determination section68determines the prediction expression to convert the deflection angle string into a predicted difference value string according to the “object road unit selection mode,” the “pattern unit selection mode,” the “block unit selection mode,” the “resample length linkage mode,” or the “sequential selection mode” described above. The variable-length coding processing section64calculates a predicted value according to the prediction expression determined by the prediction expression determination section68, subtracts the predicted value from each deflection angle in the deflection angle string to generate a predicted difference value string, and variable-length codes the predicted difference value string. The compressed and coded data is transmitted to the probe information collection center50at the probe information transmission timing. The data may be stored on an external medium so as to be provided for the probe information collection center50.

In the probe information collection center50, the coded data decoding section52decodes the data collected from the probe car installed machine60. The prediction expression determination section55identifies the prediction expression to decode the deflection angle from the provided data, and the run locus shape reconstruction section53reproduces the deflection angle string using the prediction expression and converts each deflection angle into latitude and longitude data to reproduce the run locus data. The most of the run locus information is made to generate vehicle information together with the measurement information of the speed, etc., measured in the probe car installed machine60.

Thus, the information transmission apparatus and the probe car installed machine can efficiently compress the data amount by generating the coded data of the object road and the run locus using the coded data generation method of the invention.

A probe car system is constructed using the probe car installed machine60and the probe information collection center50in combination, and an information transmission method in the probe car system is accomplished between them; this method is accomplished using the coded data generation method and the coded data decoding method of the invention in combination.

In the example described above, the coded data generation apparatus is the information transmission apparatus20or the probe car installed machine60of an information transmission center; it is an embodiment in the information transmission party and may be any if it is an apparatus or terminal that can transmit information. Further, the generated coded data can also be recorded on a medium so as to be provided for any other apparatus. The information utilization apparatus40and the probe information collection center50of coded data reconstruction apparatus are also examples and may be any apparatus if the apparatus can make the most of information, such as a person computer or a mobile terminal. Of course, similar advantages can also be provided in the information collection center or the apparatus in the center that can reconstruct the coded data. Further, similar advantages can also be provided by performing reconstruction processing using a medium, etc., recording the coded data, needless to say.

The invention also contains a program for causing a computer to execute generation of code data provided by coding a linear object. The program causes the computer to execute the steps of resampling a linear object for setting a plurality of nodes and arranging position data of each node represented by a deflection angle from the immediately preceding node to generate a data string of the deflection angles; when the data string of the deflection angles is converted into predicted difference values indicating the difference from a predicted value to predict the position data of each of the nodes, evaluating the data string of the predicted difference values; selecting a prediction expression to calculate the predicted value from among a plurality of prediction expressions based on the evaluation result; and converting each deflection angle contained in the data string of the deflection angles generated by a shape data resample processing section into a predicted difference value from the predicted value calculated using the determined prediction expression and variable-length coding a data string of the predicted difference values. Such a program is incorporated in the information transmission apparatus20and the probe car installed machine60in various formats. For example, the program can be recorded in predetermined memory in the information transmission apparatus20, the probe car installed machine60or an external apparatus. The program may be recorded in an information record unit such as a hard disk and an information record medium such as a CD-ROM, a DVD-ROM, or a memory card. The program may be downloaded via a network.

Further, the invention also contains a program for causing a computer to decode code data representing a linear object. The program causes the computer to execute the steps of decoding variable-length coded data representing position information of a linear object and reproducing shape data containing a data string of difference values each indicating the difference between a deflection angle and a predicted value; determining the prediction expression used to calculate the predicted value from the provided shape data; and calculating a predicted value using the determined prediction expression and reproducing position information of nodes of the linear object from the provided data string of the predicted difference values.

Such a program is also incorporated in the information utilization apparatus40and the probe information collection center50in various formats. For example, the program can be recorded in predetermined memory in the information utilization apparatus40, the probe information collection center50or an external apparatus. The program may be recorded in an information record unit such as a hard disk and an information record medium such as a CD-ROM, a DVD-ROM, or a memory card. The program may be downloaded via a network.

The information transmission apparatus20and the information utilization apparatus40of the invention or the probe car installed machine60and the probe information collection center50are used in combination to make up a map data distribution system.

The algorithm (program) complying with the coded data generation method of the invention can be recorded on a record medium recording the map data corresponding to various pieces of map information in the map data main body. Accordingly, it is made possible to compress and code the map data main body.

In the description of the embodiment, the linear object is the road shape for position reference by way of example. However, the linear object is not limited to the road shape. The “linear object” contains all elongated shapes including various forms of a line, a curve, etc., and can contain all geographic information that can be represented by linear shapes on a map. Further, it also contains all represented by linear shapes, not relating to a map, such as fingerprints.

While the invention has been described in detail with reference to the specific embodiment, it will be obvious to those skilled in the art that various changes and modifications can be made without departing from the spirit and the scope of the invention.

The present application is based on Japanese Patent Application (No. 2003-357730) filed on Oct. 17, 2003, which is incorporated herein by reference.

INDUSTRIAL APPLICABILITY

The coded data generation method of the invention can be used when coded data representing position information of road shapes, rivers, railways, administrative district boundaries, contour lines, etc., of a digital map is generated and is transmitted, stored, retained, etc. In addition to the digital map, the coded data generation method can also be applied when coded data representing linear objects of various patterns, fingerprints, etc., is generated and is transmitted, stored, retained, etc.