Digital map position information compressing method and device

• US 20060155463A1
• Filed: 06/11/2004
• Published: 07/13/2006
• Est. Priority Date: 06/11/2003
• Status: Active Grant

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Adachi, Shinya
• Granted Patent: US 7,340,341 B2
• Time in Patent Office: Days
• 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 vector data which indicate position information on a digital map and which have a shape represented by a coordinate point series, the method being characterized by comprising the steps of:

resampling a vector shape by a constant resampling 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 vector data according to claim 1, characterized in that:

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 vector data according to claim 1, characterized in that:

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 vector data according to claim 1, characterized in that:

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 vector data according to claim 1, characterized in that:

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 vector data according to claim 1, characterized in that:

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

7. An information providing apparatus for providing data containing position information on a digital map, being characterized by comprising:

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

shape data resample processing means for resampling the road shape data by a constant resampling length in such a manner that a distance error between a straight line which links between sampling points and the road 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.

8. A probe car on-board apparatus for providing information on a traveling path, being characterized by 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 resample processing means for resampling the traveling path by a constant resampling 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.

9. A method of compressing position information on a digital map, being characterized by comprising the steps of:

changing an angle resolution which constitutes a quantization unit of an angle depending on a length of a resampling length which regulates an interval of resampling;

dividing a linear shape contained in a digital map into one or a plurality of segments and resampling linear shapes in the segments by a constant resampling 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.

10. A compressing method as set forth in claim 9, characterized in that:

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

11. The compressing method according to claim 9, characterized in that:

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

12. The compressing method according to claim 10, characterized by comprising further the step of:

setting an upper limit on the angle resolution.

13. The compressing method according to claim 9, characterized in that:

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

14. The compressing method according to claim 9, characterized in that:

when resampling the linear shape,

a plurality of candidate points are set at positions which are away by the resampling 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.

21. The compressing method according to claim 11, characterized by comprising further the step of:

setting an upper limit on the angle resolution.

15. An information providing apparatus for providing position information on a digital map, being characterized by comprising:

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

shape data resampling processing means for dividing the road shape of an object road contained in a digital map into one or a plurality of segments, resampling road shapes in the segments using a constant resampling length and an angle resolution set according to the length of the resampling 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

characterized in that,

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

16. A probe car on-board apparatus for providing information on a traveling path, being characterized by comprising:

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

storing means for storing a traveling path;

resampling length and angle resolution determination means for determining a resampling length which regulates an interval of resampling 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 resampling length;

traveling path resample processing means for resampling the traveling path using the resampling length and the angle resolution which are determined by the resampling 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 characterized in that;

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

17. A computer readable recording medium storing a program for executing the compression of vector data indicating position information on a digital map, being characterized in that:

a computer is made to execute;

resampling a vector shape by a constant resampling 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.

18. A computer readable recording medium storing a program for executing the compression of position information on a digital map, being characterized in that:

a computer is made to execute;

setting an angle resolution which constitutes a quantization unit of an angle according to a resampling length which regulates an interval of resampling;

dividing a linear shape contained in a digital map into one or a plurality of segments and resampling linear shapes in the segments by a constant resampling 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.

19. A method of compressing position information on a digital map, being characterized by comprising the steps of:

resampling an object road segment by a constant resampling 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.

20. A method for compressing position information on a digital map, being characterized by comprising the steps of:

setting an angle resolution which constitutes a quantization unit of an angle according to the length of a resampling length which regulates an interval of resampling;

dividing a road contained in a digital map into one or a plurality of segments and resampling the segments by a constant resampling 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.