Digital map position information compressing method and device

• US 7,340,341 B2
• Filed: 06/11/2004
• Issued: 03/04/2008
• Est. Priority Date: 06/11/2003
• Status: Expired due to Fees

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Adachi, Shinya
• Primary Examiner(s): ARTHUR JEANGLAUDE, GERTRUDE
• Application Number:
  US10/560,064
• Publication Number:
  US 20060155463A1
• Time in Patent Office: 1,362 Days
• Field of Search: 701/200, 701/207, 701/208, 701/212, 340/988, 340/995.12, 340/995.17, 340/995.22
• US Class Current: 701/208
• CPC Class Codes: G01C 21/3819 Road shape data, e.g. outline of a route
• CPC Class Codes: G01C 21/3837 Data obtained from a single source
• CPC Class Codes: G01C 21/3844 Data obtained from position sensors only, e.g. from inertial navigation

Abstract

The present invention provides a method and apparatus for compressing data of position information such as a road on a digital map in order to realize an accurate transmission of the position information in a small volume of data. A shape vector of an object road segment is resampled, and as this occurs, a sampling point is represented by quantized angle information. By selecting preferably the sampling point and an angle resolution of the quantized angle information, an error in position information can be reduced. For example, in a method for compressing position information by setting appropriately an angle resolution δ which constitutes a quantization unit of an angle, the angle resolution is set according the length of a resampling length L which regulates an interval of resampling, a road shape contained in a digital map is divided into one or a plurality of segments, road shapes in the segments are resampled by a constant resampling length L, and the position of the road shapes is represented by a data string of quantized angle information indicating the position of a sampling point, and data of the data string are variable length coded for transmission. By making the angle resolution δ and the resampling length L interlock with each other, the angle resolution is made small when the resampling length is long, whereas when the resampling length is short, the angle resolution is increased, whereby position information such as road can be transmitted accurately in a small volume of data.

Claims

1. A method of compressing shape data which indicate position information on a digital map and which have a shape represented by a coordinate point series, the method comprising the steps of:

sampling a vector shape by a constant sampling length in such a manner that a distance error between a straight line which links between sampling points and the vector shape does not deviate to either the left or the right of the straight line in a longitudinal direction thereof so as to set a sampling point;

representing the vector shape by a data string of angle information indicating the position of the sampling point; and

variable length coding data of the data string.

2. The method of compressing shape data according to claim 1, wherein:

when setting the sampling point, the sampling point is set in consideration of a difference between an area located between the straight line and the vector shape on the right side of the straight line and an area located between the straight line and the vector shape on the left side of the straight line.

3. The method of compressing shape data according to claim 1, wherein:

when setting the sampling point, the sampling point is set in consideration of a difference between the length of a line segment of the vector shape located on the right side of the straight line and the length of a line segment of the vector shape located on the left side of the straight line.

4. The method of compressing shape data according to claim 1, wherein:

when setting the sampling point, the sampling point is set in consideration of a difference between a maximum distance error between the straight line and the vector shape on the right side of the straight line and a maximum distance error between the straight line and the vector shape on the left side of the straight line.

5. The method of compressing shape data according to claim 1, wherein:

when setting the sampling point, the sampling point is set in consideration of a larger maximum distance error out of a maximum distance error between the straight line and the vector shape on the right side of the straight line and a maximum distance error between the straight line and the vector shape on the left side of the straight line.

6. The method of compressing shape data according to claim 1, wherein:

when setting the sampling point, the sampling point is set in consideration of a deflection angle absolute value of the straight line.

7. A receiver that receives data which is compressed by a method according to claim 1.

8. An information providing apparatus for providing data containing position information on a digital map, the apparatus comprising:

shape data extracting means for extracting shape data of an object road from a digital map database;

shape data sample processing means for sampling the shape data by a constant sampling length in such a manner that a distance error between a straight line which links between sampling points and the shape data does not deviate to either the left or the right of the straight line so as to set a sampling point and representing the object road by a data string of quantized angle information which indicates the position of the sampling point;

variable length coding means for variable length coding data of the data string; and

providing means for providing means for providing data coded by the variable length coding means.

9. A probe car on-board apparatus for providing information on a traveling path, the apparatus comprising:

own vehicle position detecting means for detecting a position of an own vehicle;

storing means for storing sequentially the positions of the own vehicle detected by the own vehicle position detecting means as a traveling path;

shape data sample processing means for sampling the traveling path by a constant sampling length in such a manner that a distance error between a straight line which links between sampling points and the traveling path does not deviate to either the left or the right of the straight line so as to set a sampling point and representing the traveling path by a data string of quantized angle information which indicates the position of the sampling point;

variable length coding means for variable length coding data of the data string; and

transmitting means for transmitting data coded by the variable length coding means.

10. A method of compressing position information on a digital map, the method comprising the steps of:

changing an angle resolution which constitutes a quantization unit of an angle depending on a length of a sampling length;

dividing a linear shape contained in a digital map into one or a plurality of segments and sampling linear shapes in the segments by a constant sampling length;

representing the position of the linear shape by a data string of quantized angle information indicating the position of a sampling point; and

variable length coding data of the data string.

11. A compressing method as set forth in claim 10, wherein:

when setting the angle resolution, the magnitude of the angle resolution is set large when the sampling length is short.

12. The compressing method according to claim 10, wherein:

when setting the angle resolution, the sampling length or the angle resolution is set such that a distance error between the linear shape and a sampling shape does not exceed a permissible error that has been regulated in advance.

13. The compressing method according to claim 11, further comprising the step of:

setting an upper limit on the angle resolution.

14. The compressing method according to claim 10, wherein:

when setting the angle resolution, the magnitude of the angle resolution is changed according to the magnitude of an absolute value of a deflection angle, so that the angle resolution when the absolute value of the deflection angle is small is set small.

15. The compressing method according to claim 10, wherein:

when sampling the linear shape,

a plurality of candidate points are set at positions which are away by the sampling length from a adjacent sampling point in respective directions that the quantized angle can take; and

of the candidate points, the candidate point which approximates to the linear shape most truly is set as a sampling point.

16. The compressing method according to claim 12, further comprising the step of:

setting an upper limit on the angle resolution.

17. A receiver that receives data which is compressed by a method according to claim 10.

18. An information providing apparatus for providing position information on a digital map, the apparatus comprising:

angle resolution determination means for setting an angle resolution which constitutes a quantization unit of an angle according to a length of a sampling length;

shape data sampling processing means for dividing the road shape of an object road contained in a digital map into one or a plurality of segments, sampling shapes in the segments using a constant sampling length and an angle resolution set according to the length of the sampling length and producing a data string of quantized angle information indicating a position of a sampling point; and

variable length coding means for variable length coding data of the data string; and

wherein,

data coded by the variable length coding means are provided as position information of the object road.

19. A probe car on-board apparatus for providing information on a traveling path, the apparatus comprising:

own vehicle position determination means for detecting a position of an own vehicle;

storing means for storing a traveling path;

sampling length and angle resolution determination means for determining a sampling length based on the shape of the traveling path or information of a sensor installed in a vehicle and determining an angle resolution which constitutes a quantization unit of an angle according to the length of the sampling length;

traveling path sample processing means for sampling the traveling path using the sampling length and the angle resolution which are determined by the sampling length and angle resolution determination means and producing a data string of quantized angle information indicating the position of a sampling point; and

a variable length coding means for variable length coding data of the data string, and wherein;

data coded by the variable length coding means are provided as information on the traveling path.

20. A computer readable recording medium storing a program for executing the compression of shape data indicating position information on a digital map, wherein:

a computer is made to execute;

sampling a vector shape by a constant sampling length in such a manner that a distance error between a straight line which links between sampling points and the vector shape does not deviate to either the left or the right of the straight line in a longitudinal direction thereof so as to set a sampling point;

representing the vector shape by a data string of angle information indicating the position of the sampling point; and

variable length coding data of the data string.

21. A computer readable recording medium storing a program for executing the compression of position information on a digital map, wherein:

a computer is made to execute;

setting an angle resolution which constitutes a quantization unit of an angle according to a sampling length;

dividing a linear shape contained in a digital map into one or a plurality of segments and sampling linear shapes in the segments by a constant sampling length;

representing the position of the linear shape by a data string of quantized angle information indicating the position of a sampling point; and

variable length coding data of the data string.

22. A method of compressing position information on a digital map, comprising the steps of:

sampling an object road segment by a constant sampling length in such a manner that a distance error between a straight line which links between sampling points in the object road segment and the object road segment does not deviate to either the left or the right of the straight line in a longitudinal direction thereof so as to set a sampling point;

representing the object road segment by a data string of angle information indicating the position of the sampling point; and

variable length coding data of the data string.

23. A receiver that receives data which is compressed by a method according to claim 22.

24. A method for compressing position information on a digital map, comprising the steps of:

setting an angle resolution which constitutes a quantization unit of an angle according to the length of a sampling length;

dividing a road contained in a digital map into one or a plurality of segments and sampling the segments by a constant sampling length;

representing the position of the segments by a data string of quantized angle information indicating the position of a sampling point; and

variable length coding data of the data string.

25. A receiver that receives data which is compressed by a method according to claim 24.