Encoding data generation method and device

• US 7,271,746 B2
• Filed: 10/15/2004
• Issued: 09/18/2007
• Est. Priority Date: 10/17/2003
• Status: Active Grant

• Current Assignee: Panasonic Corporation (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Adachi, Shinya
• Primary Examiner(s): Young; Brian
• Application Number:
  US10/556,178
• Publication Number:
  US 20060227020A1
• Time in Patent Office: 1,068 Days
• Field of Search: 341/50, 341/59, 341/76, 341/150, 701/1, 701/29, 701/35
• US Class Current: 341/76
• CPC Class Codes: G06T 9/20 Contour coding, e.g. using detection of edges
• CPC Class Codes: G09B 29/00 Maps; Plans; Charts; Diagrams, e.g. route diagram star maps G09B27/04; devices for holding or supporting maps A47B97/02; for computing purposes G06G1/14, G09B1/16; display boards G09F
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code

Abstract

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.

Claims

1. A generation method of coded data provided by coding a linear object, said coded data generation method comprising the steps of:

(1) resampling the linear object for setting a plurality of nodes;

(2) 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) 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) calculating the predicted value using a predetermined prediction expression of the plurality of prediction expressions;

(5) 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; and

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

2. The coded data generation method as claimed in claim 1 further comprising 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 said step (5);

evaluating the data strings of the predicted difference values; and

selecting the predetermined prediction expression in said step (4) from among the plurality of prediction expressions based on the evaluation result of the evaluating step.

3. The coded data generation method as claimed in claim 1 wherein

the plurality of prediction expressions contain at least one prediction expression with 0 as a predicted value.

4. The coded data generation method as claimed in claim 1 wherein

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

5. The coded data generation method as claimed in claim 4 wherein

the prediction expression implemented as the function contains at least one prediction expression with the deflection angle immediately preceding the attention deflection angle as a predicted value.

6. The coded data generation method as claimed in claim 4 wherein

the prediction expression implemented as the function contains at least one prediction expression with an average or a weighted average of a plurality of deflection angles preceding the attention deflection angle as a predicted value.

7. The coded data generation method as claimed in claim 4 wherein

the prediction expression implemented as the function contains at least one prediction expression with the angle resulting from inverting the positive or negative sign of the deflection angle of the node immediately preceding the attention deflection angle as a predicted value.

8. The coded data generation method as claimed in claim 2 wherein

in said step (5), the data string of the deflection angles corresponding to a part zone of the linear object is converted into a data string of the predicted difference values, 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 for the data string of the predicted difference values.

9. The coded data generation method as claimed in claim 8 wherein

the data string of the deflection angles is classified into blocks corresponding to state transition patterns of the deflection angles and a prediction expression to convert the deflection angles into predicted difference values is selected for each of the blocks.

10. The coded data generation method as claimed in claim 8 wherein

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.

11. The coded data generation method as claimed in claim 8 wherein

the data string of the deflection angles is classified into blocks matching the change points of the resample length of the resampling in said step (1) and a prediction expression to convert the deflection angles into predicted difference values is selected for each of the blocks.

12. The coded data generation method as claimed in claim 8 wherein

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.

13. The coded data generation method as claimed in claim 12 wherein

as many deflection angles as the predetermined number are 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 is changed to the predetermined prediction expression and then the attention deflection angle is converted into a predicted difference value.

14. The coded data generation method as claimed in claim 8 wherein

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

15. The coded data generation method as claimed in claim 14 wherein

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 is added to the evaluation value of the evaluation criterion of the predicted difference value string in the attention deflection angle or block.

16. The coded data generation method as claimed in claim 15 wherein

the penalty value is set in response to the occurrence frequency of each prediction expression.

17. The coded data generation method as claimed in claim 2 wherein

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.

18. The coded data generation method as claimed in claim 2 wherein

the data string of the predicted difference values is evaluated according to the statistical value of the predicted difference values contained in the data string and a prediction expression is selected based on the result of the statistical value.

19. The coded data generation method as claimed in claim 18 wherein

the statistical value is at least either of variance and standard deviation of the predicted difference values.

20. The coded data generation method as claimed in claim 2 wherein

the evaluation value for each predicted difference value is preset 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.

21. The coded data generation method as claimed in claim 20 wherein

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

22. The coded data generation method as claimed in claim 20 wherein

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

23. An information transmission apparatus comprising:

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 said shape data resample processing section into a predicted difference value from the predicted value calculated using the prediction expression determined by said prediction expression determination section and variable-length coding a data string of the predicted difference values.

24. An information transmission apparatus comprising:

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 said 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 said coded data decoding section.

25. A program recorded on a computer-readable medium that executes generation of code data provided by coding a linear object, said program comprising:

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 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.

26. A program recorded on a computer-readable medium that decodes code data representing a linear object, said program comprising:

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.