MAP MATCHING SYSTEM, MAP MATCHING METHOD AND PROGRAM

• US 20100114484A1
• Filed: 03/25/2008
• Published: 05/06/2010
• Est. Priority Date: 03/27/2007
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Fujiyama, Kenichiro, Kida, Kouji
• Granted Patent: US 8,355,864 B2
• Time in Patent Office: Days
• US Class Current: 701/208
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

Provided is a general-purpose map matching system enabling high-speed map matching while maintaining a precision of an analysis based on a map matching result even when event data is transmitted from numerous vehicles.

The grid road generation unit 8 generates each grid obtained by the division of a region in which a road network exists into a latitude direction and a longitude direction by equal spaces based on data stored in the road network storage unit. Then, combine grids whose sets of roads passing are the same. The event grid matching unit correlates event data collected from a vehicle and a grid. When the number of pieces of event data correlated with the grid is large, the event processing priority determination unit selects a part of the data. The event road matching unit correlates the selected event data and a road in the grid.

Claims

1. A map matching system, comprising:

a road network storing unit for storing data expressing a road network by a position of a node as a crossing and by an arc which is a road with a crossing as a start point and an end point;

a road grid dividing unit for deriving a grid obtained by the division of a region where a road network exists in a latitude direction and a longitude direction by equal spaces and correlating the grid and an arc crossing the grid;

a grid road combining unit for assigning a common arc ID to a plurality of grids which are adjacent to each other and whose sets of arcs correlated are coincident and assigning an arc ID to a grid whose set of arcs correlated is different from a set of arcs of any of adjacent grids and storing information indicative of a relationship among a range of a grid derived by said road grid dividing unit, a grid ID and an arc passing the grid to a storage device;

an event collecting unit for receiving event data indicative of a position and a state of a vehicle;

an event grid matching unit for specifying a grid ID of a grid to which a generation position included in event data received by said event collecting unit belongs to generate information with the grid ID and the event data correlated with reference to the information stored in said storage device;

an event data selecting unit for selecting, on a basis of a grid ID correlated with event data by said event grid matching unit, when the number of pieces of event data correlated is larger than a threshold value, as many pieces of event data as the threshold value and when the number of pieces of event data correlated is not more than the threshold value, selecting all the event data correlated;

an event road matching unit for specifying, on a basis of each event data selected by said event data selecting unit, an arc closest to a generation position of the event data from among arcs correlated with a grid ID corresponding to the event data; and

an event road storing unit for storing information indicative of a correspondence relationship between an arc specified by said event road matching unit and event data.

2. The map matching system according to claim 1, further comprising

a threshold value control unit for determining a threshold value for use by said event data selecting unit on a grid ID basis such that the threshold value becomes larger as the number of arcs corresponding to the grid ID is increased.

3. The map matching system according to claim 1, further comprising

a threshold value control unit for calculating a length of an arc in a grid corresponding to each grid ID based on data stored in said road network storage unit to determine a threshold value for use by said event data selecting unit on a grid ID basis such that the threshold value becomes larger as the length of the arc in the grid corresponding to the grid ID is increased.

4. The map matching system according to claim 1, further comprising

an event distribution analyzing unit for calculating, with reference to information with a grid ID and event data correlated which is generated by said event grid matching unit, a degree of variation in speed in the event data corresponding to the grid ID on a grid ID basis, and

a threshold value control unit for determining a threshold value for use by said event data selecting unit on a grid ID basis such that the threshold value becomes larger as a degree of variation in speed becomes higher.

5. The map matching system according to claim 4, wherein said event distribution analyzing unit calculates a dispersion as a degree of variation in speed.

6. The map matching system according to claim 1, wherein

said event mid matching unit, said event data selecting unit and said event road matching unit are realized by a computer, and which comprises

a threshold value control unit for determining a threshold value uses by said event data selecting unit such that the threshold value becomes larger as a load of said computer is increased.

7. The map matching system according to claim 6, further comprising

a load information storing unit for storing the number of processes according to a load determined to have a larger value as a load of the computer is decreased and monitoring the load of the computer to specify the number of processes according to the load, wherein

said threshold value control unit calculates a value obtained by dividing the number of processes according to a load by the total number of arcs to determine, on a grid ID basis, a threshold value to be a value not more than a value obtained by multiplying the number of arcs corresponding to a girl ID by said division result.

8. The map matching system according to claim 1, further comprising

a monitoring unit for determining whether the number of pieces of event data received by said event collecting unit is increasing or decreasing, and

a threshold value control unit for varying a threshold value for use by said event data selecting unit according to whether the number of pieces of event data received by said event collecting unit is increasing or decreasing.

9. The map matching system according to claim 8, wherein said monitoring unit counts the number of pieces of event data at fixed time intervals to determine, when being positive continues as a difference obtained by subtracting, from the count result, an immediately preceding count result, that the number is increasing and when being negative as the difference continues, determine that the number is decreasing.

10. The map matching system according to claim 1, wherein said event grid matching unit includes

an event storing unit for temporarily storing event data received by said event collecting unit,

a processing target event storing unit for storing event data which is stored in said event storing unit and which is a target of the processing of correlating with a grid ID, and

a matching unit for specifying a grid ID of a grid including a generation position included in event data stored in said processing target event storing unit to generate information with the grid ID and the event data correlated with reference to the information stored in said storage device.

11. The map matching system according to claim 1, comprising an event analyzing unit for analyzing a traffic condition based on information stored in said event road storing unit.

12. A map matching device accessible to a road data storage device which stores information indicative of a relationship among a range of each grid obtained by dividing a region where a road network exists in a latitude direction and a longitude direction by equal spaces, a grid ID unitarily assigned to each set of grids whose sets of arcs which are roads are common and an are passing the grid, comprising:

an event collecting unit for receiving event data indicative of a position and a state of a vehicle;

an event grid matching unit for specifying a grid ID of a grid to which a generation position included in event data received by said event collecting unit belongs to generate information with the grid ID and the event data correlated with reference to the information stored in said road data storage device;

an event data selecting unit for selecting, on a basis of a grid ID correlated with event data by said event grid matching unit, when the number of pieces of event data correlated is larger than a threshold value, as many pieces of event data as the threshold value and when the number of pieces of event data correlated is not more than the threshold value, selecting the event data correlated;

an event road matching unit for specifying, on a basis of each event data selected by said event data selecting unit, an arc closest to a generation position of the event data from among arcs correlated with a grid ID corresponding to the event data; and

an event road storing unit for storing information indicative of a correspondence relationship between an arc specified by said event road matching unit and event data.

13. The map matching device according to claim 12, further comprising

a threshold value control unit for determining a threshold value for use by said event data selecting unit on a grid ID basis such that the threshold value becomes larger as the number of arcs corresponding to the grid ID is increased.

14. The map matching device according to claim 12, further comprising

a threshold value control unit for calculating a length of an arc in a grid corresponding to each grid ID to determine a threshold value for use by said event data selecting unit on a grid ID basis such that the threshold value becomes larger as the length of the arc in the grid corresponding to the grid ID is increased.

15. The map matching device according to claim 12, further comprising

an event distribution analyzing unit for calculating, with reference to information with a grid ID and event data correlated which is generated by said event grid matching unit, a degree of variation in speed in the event data corresponding to the grid ID on a grid ID basis, and

a threshold value control unit for determining a threshold value for use by said event data selecting unit on a grid In basis such that the threshold value becomes larger as a degree of variation in speed becomes higher.

16. The map matching device according to claim 12, further comprising:

a threshold value control unit for determining a threshold value for use by said event data selecting unit such that the threshold value becomes larger as a load of the map matching device is increased.

17. The map matching device according to claim 12, further comprising:

a monitoring unit for determining whether the number of pieces of event data received by said event collecting unit is increasing or decreasing, and

a threshold value control unit for varying a threshold value for use by said event data selecting unit according to whether the number of pieces of event data received by said event collecting unit is increasing or decreasing.

18. A road data generation device which is accessible to a road network storage unit for storing data expressing a road network by a position of a node as a crossing and by an arc that is a road with a crossing as a start point and an end point and which generates data for use in map matching, comprising:

a road grid dividing unit for deriving a grid obtained by the division of a region where a road network exists in a latitude direction and a longitude direction by equal spaces and correlating the grid and an arc crossing the grid; and

a grid road combining unit for assigning a common arc ID to a plurality of grids which are adjacent to each other and whose sets of arcs correlated are coincident and assigning an arc ID to a grid whose set of arcs correlated is different from a set of arcs of any of adjacent grids to generate information indicative of a relationship among a range of a grid derived by said road grid dividing unit, a grid ID and an arc passing the grid.

19. A map matching method to be applied to a map matching device accessible to a road data storage device which stores information indicative of a relationship among a range of each grid obtained by dividing a region where a road network exists in a latitude direction and a longitude direction by equal spaces, a grid ID unitarily assigned to each set of grids whose sets of arcs which are roads are common and an arc passing the grid, wherein

an event collecting unit receives event data indicative of a position and a state of a vehicle,

an event grid matching unit specifies a grid ID of a grid to which a generation position included in event data received by said event collecting unit belongs to generate information with the grid ID and the event data correlated with reference to the information stored in said road data storage device,

an event data selecting unit selects, on a basis of a grid ID correlated with event data by said event grid matching unit, when the number of pieces of event data correlated is larger than a threshold value, as many pieces of event data as the threshold value and when the number of pieces of event data correlated is not more than the threshold value, selects all the event data correlated, and

an event road matching unit specifies, on a basis of each event data selected by said event data selecting unit, an arc closest to a generation position of the event data from among arcs correlated with a grid ID corresponding to the event data.

20. The map matching method according to claim 19, wherein a threshold value control unit determines a threshold value for use by said event data selecting unit on a grid ID basis such that the threshold value becomes larger as the number of arcs corresponding to the grid ID is increased.

21. The map matching method according to claim 19, wherein

a threshold value control unit calculates a length of an arc in a grid corresponding to each grid ID to determine a threshold value for use by said event data selecting unit on a grid ID basis such that the threshold value becomes larger as the length of the arc in the grid corresponding to the grid ID is increased.

22. The map matching method according to claim 19, wherein

an event distribution analyzing unit calculates, with reference to information with a grid ID and event data correlated which is generated by said event grid matching unit, a degree of variation in speed in the event data corresponding to the grid ID on a grid ID basis, and

a threshold value control unit determines a threshold value for use by said event data selecting unit on a grid ID basis such that the threshold value becomes larger as a degree of variation in speed is becomes higher.

23. The map matching method according to claim 19, wherein

a threshold value control unit determines a threshold value for use by said event data selecting unit such that the threshold value becomes larger as a load of the map matching device is increased.

24. The map matching method according to claim 19, wherein

a monitoring unit determines whether the number of pieces of event data received by said event collecting unit is increasing or decreasing, and

a threshold value control unit varies a threshold value for use by said event data selecting unit according to whether the number of pieces of event data received by said event collecting unit is increasing or decreasing.

25. A computer readable medium storing a map matching program mounted on a computer accessible to a road data storage device which stores information indicative of a relationship among a rang of each grid obtained by dividing a region where a road network exists in a latitude direction and a longitude direction by equal spaces, a grid ID unitarily assigned to each set of grids whose sets of arcs which are roads are common and an arc passing the grid, said map matching program causes said computer to execute:

an event collecting processing of receiving event data indicative of a position and a state of a vehicle;

an event grid matching processing of specifying a grid ID of a grid to which a generation position included in event data received belongs to generate information with the grid ID and the event data correlated with reference to the information stored in said road data storage device;

an event data selecting processing of selecting, on a basis of a grid ID correlated with event data by said event grid matching processing, when the number of pieces of event data correlated is larger than a threshold value, as many pieces of event data as the threshold value and when the number of pieces of event data correlated is not more than the threshold value, selecting all the event data correlated; and

an event road matching processing of specifying, on a basis of each event data selected by said event data selecting processing, an arc closest to a generation position of the event data from among arcs correlated with a grid ID corresponding to the event data.

26. The computer readable medium according to claim 25, said map matching program causes said computer to execute a threshold value control processing of determining a threshold value for use in said event data selecting processing on a grid ID basis such that the threshold value becomes larger as the number of arcs corresponding to the grid ID is increased.

27. The computer readable medium according to claim 25, said map matching program causes said computer to execute

a threshold value control processing of calculating a length of an arc in a grid corresponding to each grid ID to determine a threshold value for use in said event data selecting processing on a grid ID basis such that the threshold value becomes larger as the length of the arc in the grid corresponding to the grid ID is increased.

28. The computer readable medium according to claim 25, said map matching program causes said computer to execute

an event distribution analyzing processing of calculating, with reference to information with a grid ID and event data correlated which is generated by said event grid matching processing, a degree of variation in speed in the event data corresponding to the grid ID on a grid ID basis, and

a threshold value control processing of determining a threshold value for use in said event data selecting processing on a grid ID basis such that the threshold value becomes larger as a degree of variation in speed becomes higher.

29. The computer readable medium according to claim 25, said map matching program causes said computer to execute

a threshold value control processing of determining a threshold value for use in said event data selecting processing such that the threshold value becomes larger as a load of said computer is increased.

30. The computer readable medium according to claim 25, said map matching program causes said computer to execute

a monitoring processing of determining whether the number of pieces of event data received is increasing or decreasing, and

a threshold value control processing of varying a threshold value for use in said event data selecting processing according to whether the number of pieces of event data received is increasing or decreasing.

31. A computer readable medium storing road data generation program mounted on a computer accessible to a road network storage device which stores data expressing a road network by a position of a node as a crossing and by an arc that is a road with a crossing as a start point and an end point, said road data generation program causes said computer to execute:

a road grid dividing processing of deriving a grid obtained by the division of a region where a road network exists in a latitude direction and a longitude direction by equal spaces and correlating the grid and an arc crossing the grid; and

a grid road combining processing of assigning a common arc ID to a plurality of grids which are adjacent to each other and whose sets of arcs correlated are coincident and assigning an arc ID to a grid whose set of arcs correlated is different from a set of arcs of any of adjacent grids to generate information indicative of a relationship among a range of a grid derived by said road grid dividing processing, a grid ID and an arc passing the grid.