Map matching method, map matching device, database for shape matching, and shape matching device

• US 20050228584A1
• Filed: 03/28/2003
• Published: 10/13/2005
• Est. Priority Date: 03/29/2002
• Status: Active Grant

• Current Assignee: Panasonic Automotive Systems Company of America (Panasonic Holdings Corporation)
• Original Assignee: Panasonic Corporation (Panasonic Holdings Corporation)
• Inventors: Sato, Makoto, Adachi, Shinya
• Granted Patent: US 7,657,372 B2
• Time in Patent Office: Days
• US Class Current: 701/208
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G09B 29/10 Map spot or coordinate position indicators; Map reading aids optical projection apparatus per se G03B
• CPC Class Codes: G09B 29/106 using electronic means

Abstract

An object of the present invention is to provide a map matching method capable of performing a process operation in a high speed. In the map matching method of the present invention, while employing road network data in which road networks are formed in a plurality of hierarchical layers “a”, “b”, “c”, and a road network of an upper-grade hierarchical layer is established by such a road network which is extracted from a road network having a lower-grade hierarchical layer lower than the road network having the upper-grade hierarchical layer, a road network of the uppermost-grade hierarchical layer “a” is matched with a shape vector indicative of a shape of a objective road in a beginning stage; and when such a candidate road which is matched with the shape vector cannot be obtained in the road network of the uppermost-grade hierarchical layer “a”, since such a road network having another hierarchical layer “b”, or “c” is matched with the shape vector, the objective road is identified. In the most cases, as to a objective road of traffic information and the like, the objective road can be identified by executing a map matching operation with employment of the road network having the uppermost-grade hierarchical layer “a”, and the map matching operation can be carried out in a high speed.

Claims

1. A map matching method comprising the steps of:

setting priority orders to road networks in response to frequencies to be appropriate to a objective road of map matching operation, wherein said road networks has a bias on said frequencies;

restricting a range of said road network matched with said objective road based upon said priority order; and

if a candidate road which is matched with a shape vector of said objective road cannot be obtained, relaxing said restriction made based upon priority order so as to broaden said range of road networks matched with said objective road.

2. A map matching method comprising the steps of:

matching a road network whose weight is relatively large with a shape vector indicating a shape of a objective road, by using road network data of a map including a set of road networks to which different weights have been applied; and

if a candidate road to be appropriate to said shape vector cannot be obtained in the road network whose weight is relatively large, further matching a road network having said road network whose weight is respectively large and a road network whose weight is relatively small, with said shape vector, and identifying said objective road section.

3. A map matching method comprising the steps of:

matching a road network of a relatively upper-grade hierarchical layer with a shape vector indicating a shape of a objective road section, by using road network data including hierarchized road networks in which a road network of an upper-grade hierarchical layer is extracted from a road network having a lower-grade hierarchical layer lower; and

if a candidate road to be appropriate to said shape vector cannot be obtained in said road network of the relatively upper-grade hierarchical layer, further matching a road network having a further lower-grade hierarchical layer with said shape vector, and identifying said objective road.

4. The map matching method as claimed in claim 3, further comprising the step of:

determining a hierarchical layer which is matched in the beginning stage by referring to attribute information of said shape vector.

5. The map matching method as claimed in claim 3, further comprising the step of:

determining each of the hierarchical layers of said hierarchized road networks by a road attribute.

6. The map matching method as claimed in claim 5,

wherein, as said road attribute, a road sort, a road number, tolls road/freeway, a road mode, or identification information as to a traffic information providing objective road is employed.

7. The map matching method as claimed in claim 3, further comprising the step of:

if the candidate road to be appropriate to said shape vector can be obtained, judging whether or not a parallel-traveling resembling shaped road having a resembling shape, which is traveled in a parallel to said candidate road, is present in a road network having a hierarchical layer which is lower than the hierarchical layer of the road network in which said candidate road could be obtained.

8. The map matching method as claimed in claim 7, further comprising the step of:

if said parallel-traveling resembling shaped road is present, comparing a shape of said shape vector, a shape of said candidate road, and a shape of said parallel-traveling resembling shaped road with each other, and judging whether or not an employment of said candidate road is acceptable.

9. The map matching method as claimed in claim 8, further comprising a step of:

if it cannot be judged that the employment of said candidate road is acceptable, re-starting a matching operation with respect to said shape vector by using a road network having a lower hierarchical layer than the hierarchical layer of the road network from which said candidate road has been acquired.

10. The map matching method as claimed in claim 3, further comprising the steps of:

providing an interlayer linking node used to be transferred from a road network having an upper-grade hierarchical layer to another road network having a one-lowered upper-grade hierarchical layer, with said road network having the upper-grade hierarchical layer;

if a matching operation with respect to said shape vector cannot be carried out in a half way of said road network having the upper-grade hierarchical layer, transferring to the road network having the one-lowered upper-grade hierarchical layer by returning to said interlayer linking node; and

matching said road network having the lower grade hierarchical layer with said shape vector.

11. The map matching method as claimed in claim 3, further comprising the steps of:

defining a return distance used to be transferred from a road network having an upper-grade hierarchical layer to another road network having a one-lowered upper-grade hierarchical layer;

if a matching operation with respect to said shape vector cannot be carried out in a half way of said road network having the upper-grade hierarchical layer, transferring to the road network having the one-lowered upper-grade hierarchical layer by returning by said return distance; and

matching said road network having the lower-grade hierarchical layer with said shape vector.

12. The map matching method as claimed in claim 3,

setting data indicative of the uppermost hierarchical layer where respective links are present, to road network data having the respective hierarchical layers except for the uppermost hierarchical layer;

if a matching operation can succeed at one, or more points when a matching operation is carried out between said shape vector and the road network having the hierarchical layer other than the uppermost-grade hierarchical layer, transferring via the link to the road network having the upper-grade hierarchical layer where said link is present; and

matching said road network having the upper-grade hierarchical layer with said shape vector.

13. The map matching method as claimed in claim 3, further comprising the step of:

changing a searching range of a candidate point within the road network to be matched with said shape vector, based upon a magnitude of an error included in said shape vector.

14. The map matching method as claimed in claim 3, further comprising the steps of:

setting a thinning distance of way points to be matched with said shape vector, based upon an averaged link length of the road networks having the respective hierarchical layers; and

setting way points by thinning the way points in accordance with said thinning distance.

15. The map matching method as claimed in claim 3, further comprising the step of:

updating a road section to be included in the road networks having the respective hierarchical layers of said road network data, in response to a frequency at which said road section has been identified as said objective road.

16. The map matching method as claimed in claim 3, further comprising:

copying a road section identified as said objective road at each hierarchical layer, to a cache area,

wherein a road network recorded in said cache area is employed as the road network of said uppermost-grade hierarchical layer.

17. The map matching method as claimed in claim 4, further comprising the steps of:

previously applying parallel-traveling resembling shaped road presence/absence information for indicating as to whether or not said parallel-traveling resembling shaped road is present, to link data of the respective hierarchical layers except for the lowermost-grade hierarchical layer of said road network data; and

judging as to whether or not said parallel-traveling resembling shaped road is present, based upon said parallel-resembling shaped road presence/absence information.

18. The map matching method as claimed in claim 16, further comprising:

creating said parallel-traveling resembling shaped road presence/absence information by using any one, or more items of;

a plurality of way points set on the relevant road of an upper-grade layer;

distances between proximate points of the respective way points on the adjacent roads;

an azimuth difference between proximate points of the respective way points on the adjacent roads;

a connecting characteristic between the proximate points; and

a routed distance.

19. The map matching method as claimed in claim 5, further comprising the step of:

previously applying a shape representative value indicative of a shape of a link, to link data having the respective hierarchical layers of said road network data,

wherein said shape representative value is used for a comparison with respect to the shape of said shape vector.

20. The map matching method as claimed in claim 13,

wherein said thinning distance is defined in such a manner that a way point is set to a feature point of a shape of a link.

21. The map matching method as claimed in claim 9, further comprising the steps of:

if the shape of said shape vector becomes close to the shape of said parallel-traveling resembling shaped road rather than the shape of said candidate road, restarting a matching operation with respect to said shape vector by using a road network of a hierarchical layer including said parallel-traveling resembling shaped road.

22. A receiving device comprising:

a digital map;

road network data for map patching, said road network including hierarchized road network with plural layers formed from said digital map, wherein a road network having an upper-grade hierarchical layer is extracted from a road network having a lower-grade hierarchical layer;

a data receiving unit for receiving data which contains a shape vector indicative of a shape of a objective road; and

a map matching unit for executing a map matching operation of said shape vector by using said road network data so as to identify said objective road,

wherein said map matching unit matches said shape vector with a road network having the uppermost-grade hierarchical layer of said road network data in a beginning stage, and

wherein, if a candidate road to be appropriate to said shape vector cannot be obtained in the road network having the uppermost-grade hierarchical layer, said map matching unit matches said shape vector with a road network having another hierarchical layer and identifies said objective road.

23. An event information providing device comprising:

a digital map;

road network data for map patching, said road network including hierarchized road network with plural layers formed from said digital map, wherein a road network having an upper-grade hierarchical layer is extracted from a road network having a lower-grade hierarchical layer;

a map data information transmitting unit for distributing both said digital map and said road network data;

a shape vector data producing unit for producing a shape vector indicative of a shape of a objective road of event information by using the data of said digital map;

a shape vector deforming unit for performing an adding process operation of information for designating a hierarchical layer of said road network data to said shape vector produced by said shape vector data producing unit; and

an event information transmitting unit for transmitting event information containing said shape vector which is processed by said shape vector deforming unit.

24. An event information providing device comprising:

a digital map;

a parallel-traveling resembling shape calculating unit for calculating a parallel-traveling resembling shape link which is traveled in parallel to a link and has a shape resembled to said link from the data of said digital map;

a shape vector data producing unit for producing a shape vector indicative of a shape of a objective road of event information by using the data of said digital map;

a shape vector deforming unit for identifying as to whether or not said parallel-traveling resembling shaped link is present in the link of said objective road by using the calculation result of said parallel-traveling resembling shape calculating unit, and if said parallel-traveling resembling shape link is present, executing a deforming process operation of said shape vector by extending said objective road up to such a position that the shape of said parallel-traveling resembling shaped link can be discriminated from the shape of said objective road; and

an event information transmitting unit for transmitting event information including said shape vector processed by said shape vector deforming unit.

25. A program causing a computer to execute the processes of:

obtaining a candidate road of an objective road with using road network data including hierarchized road network with plural layers formed from said digital map, said road network having an upper-grade hierarchical layer is extracted from a road network having a lower-grade hierarchical layer, by matching a road network having an uppermost-grade hierarchical layer with a shape vector indicative of a shape of a objective road, and by restarting to match a road network having another hierarchical layer with said shape vector if the candidate road to be appropriate to said shape vector cannot be obtained in the road network having the uppermost-grade hierarchical layer;

if a candidate road matched with said shaped vector can be obtained, judging as to whether or not a parallel-traveling resembling shaped road which is traveled in parallel to said objective road and has a resembling shape thereto is present in a road network having a lower hierarchical layer than the hierarchical layer of said road network where said candidate road could be obtained;

if said parallel-traveling resembling shaped road is present, judging as to whether or not an employment of said candidate road is acceptable by comparing a shape of said shape vector, a shape of said candidate road, and a shape of said parallel-traveling resembling shaped road are with each other; and

if it cannot be judged that the employment of said candidate road is acceptable, restarting to match with respect to said shape vector by using a road network having a lower hierarchical layer than the hierarchical layer of the road network from which said candidate road has been acquired.

26. A database for shape matching, having a plurality of hierarchical layers and in which a road network is expressed by a node and a link in each of the hierarchical layers, said database comprising:

an uppermost-grade hierarchical layer having a node and a link, which represent the most important road; and

respective layers which are sequentially subdivided from said uppermost-grade hierarchical layer to a lower-grade hierarchical layer based upon important characteristics of said node and said link, which represent a road,

wherein both a node and a link which should be shape-matched from said road network are restricted by using said respective layers.

27. A shape matching device for executing a shape matching operation by using both the shape matching-purpose map database and the shape vector, recited in claim 26, wherein:

said shape matching device executes a shape matching operation from said uppermost-grade hierarchical layer;

in the case that the shape matching operation can succeed in said uppermost-grade hierarchical layer and both a node and a link can be identified, the process operation is accomplished;

in the case that both a node and a link, which correspond to said shape vector, cannot be identified, the shape matching operation is transferred to a lower-grade hierarchical layer and a shape matching operation is carried out; and

an object for a shape matching operation is sequentially transferred to a next hierarchical layer so as to perform a shape matching operation.

28. The shape matching device as claimed in claim 27,

wherein, if a common node is provided during said plurality of hierarchical layers, the object of the shape matching operation is transferred from said common node to the next hierarchical layer, and results of shape matching operations in the respective hierarchical layers are coupled to each other by said common node so as to perform a shape matching operation.

29. The shape matching device as claimed in claim 27 or 28,

wherein, if an identifier is applied to a link which is defined also in an upper-grade layer, the shape matching operation is transferred to said upper-grade layer by using said identifier so as to perform a shape matching operation.

30. The shape matching device as claimed in claim 27, 28, or 29,

wherein, in the case that the shape matching operation fails in said predetermined hierarchical layer and if an absolute position indicative of said place is utilized, the shape matching operation is sequentially transferred to a lower-grade layer so as to execute a shape matching operation.

31. The shape vector-purpose database as claimed in claim 26,

wherein the higher the upper-grade layer becomes, the coarser a total node number of the shape vector is made.

32. A shape vector transmitting server storing thereinto the shape vector-purpose database recited in claim 26, or claim 31, and transmitting either a portion or all of the shape vectors in response to a predetermined signal.

33. The shape matching device as claimed in claim 27, 28, 29, or 30,

wherein, if a shape matching operation is carried out in an upper-grade layer, a node is thinned from a node string having a shape vector by using information as to a link length and a shape matching operation is carried out by using a thinned node string.

34. The shape matching device as claimed in claim 27, 28, 29, 30, or 33,

wherein, if additional information is added to a shape vector, a hierarchical layer to be used for firstly shape-matched is selected by using said additional information.