Patent Publication Number: US-2013238648-A1

Title: Road data creating device, road data creating method, and program

Description:
INCORPORATION BY REFERENCE 
     The disclosure of Japanese Patent Application No. 2011-248574, filed on Nov. 14, 2011, including the specification, drawings, and abstract thereof, is incorporated herein by reference in its entirety. 
     BACKGROUND 
     1. Related Technical Fields 
     Related technical Fields include road data creating devices, methods, and programs that create road data for received road information. 
     2. Related Art 
     Conventionally, various kinds of technologies for creating road data for received road information are proposed. 
     For example, restored coordinates are created by restoring in a restoring part element coordinates specifying a position of a road with coordinates of at least a start point and an end point that are included in road information transmitted from a road information transmitting device. There are road information receiving devices, in which road matching processing specifying the position of the road based on the restored coordinates and road coordinate data stored in map coordinate data recording part is executed in a road specifying processing part (for example, refer to Japanese Patent Application; Publication No. JP-A-2003-346285). 
     SUMMARY 
     In the road matching processing of the road specifying processing part in the road information receiving device described in the aforementioned Patent Application; Publication No. JP-A-2003-346285, when distances from roads drawn by the road coordinate data to a road drawn by the restored coordinates are long, normal lines are extended from direct lines connecting the road coordinate data to the road drawn by the restored coordinates, the direct lines connecting the map coordinate data corresponding to the road drawn by the restored coordinates are selected based on the lengths of the normal lines. Thereafter, the road drawn by the map coordinate data located closest to the road drawn by the restored coordinates is selected among the selected direct lines connecting the road coordinate data. 
     However, if there are a plurality of roads drawn by the road coordinate data having a shape similar to the road drawn by the restored coordinates, a road drawn by wrong map coordinate data could be selected, which lowers the accuracy of specifying the position of the road. 
     Exemplary implementations of the broad inventive principles described herein provide road data creating devices, methods, and a programs that are capable of specifying with high accuracy a link on a map corresponding to received road information. 
     Exemplary implementations provide road data creating devices, methods, and a programs that access map information including map coordinate data indicating a position on a map with a coordinate, and access a matching table. A coordinate point sequence specifying a position of a road on the map with, at least two coordinates is stored in the table in association with a link ID identifying a link of the map information, the coordinate point sequence having been delivered from a road information transmitting system. A coordinate difference pattern between the position of the road specified by the coordinate point sequence and the position of the link specified by the map coordinate data is stored in the table in association with the link ID. The devices, methods, and a programs acquire road information including the coordinate point sequence delivered from the road information transmitting system and determine whether the link ID corresponding to the coordinate point sequence included in the road information is stored in the matching table. When the link ID corresponding to the coordinate point sequence included in the road information is stored in the matching table, the devices, methods, and a programs convert the coordinate point sequence into the link ID corresponding to the coordinate point sequence. When the link ID corresponding to the coordinate point sequence included in the road information is not stored in the matching table, the devices, methods, and a programs extract one or more candidate links as candidates for the link corresponding to the coordinate point sequence based on the map information. When one candidate link has been extracted, the devices, methods, and a programs convert the coordinate point sequence into the link ID of the one candidate link. When a plurality of candidate links have been extracted, the devices, methods, and a programs convert the coordinate point sequence into the link ID of one candidate link among the plurality of candidate links based on the coordinate difference patterns corresponding to the link IDs stored in the matching table among the link IDs of the links within a predetermined area in the vicinity of the plurality of candidate links. 
     According to exemplary implementations, when the link ID corresponding to the coordinate point sequence included in the road information is stored in the matching table, the coordinate point sequence is converted into the link ID. Therefore, it is possible to accurately and rapidly specify the link on the map corresponding to the coordinate point sequence included in the road information. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block diagram showing an example of configuration of a navigation device according to the present example. 
         FIG. 2  illustrates communication between the navigation device and road information transmitting systems. 
         FIG. 3  shows an example of a matching data file stored in a matching DB. 
         FIG. 4  is a main flowchart showing an algorithm for a “link ID converting processing” method to convert a coordinate point sequence included in road information into a link ID, which is executed by the navigation device. 
         FIG. 5  is a sub-flowchart showing an algorithm for a “matching table updating processing” shown in  FIG. 4 . 
         FIG. 6  is a sub-flowchart showing an algorithm for a “matching table updating processing” shown in  FIG. 4 . 
         FIG. 7  shows an example of converting the coordinate point sequence into a link ID of one candidate link from two candidate links based on coordinate difference amounts. 
         FIG. 8  is a flowchart showing an algorithm for a “coordinate point sequence determining processing” method to determine a provisionally determined coordinate point sequence stored in respective matching tables. 
     
    
    
     DETAILED DESCRIPTION OF EXEMPLARY IMPLEMENTATIONS 
     A road data creating device, a road data creating method, and a program are described in further detail below with reference to an example in conjunction with the accompanying drawings. 
     I. Schematic Structure of Navigation Device 
     First, a schematic structure of the navigation device according to the present example will be explained with reference to  FIGS. 1 and 2 .  FIG. 1  is a block diagram showing a navigation device  1  according to the present example.  FIG. 2  illustrates communication between the navigation device  1  and an A road information transmitting system  3 A to a C information transmitting system  3 C. 
     As shown in  FIG. 1 , the navigation device  1  according to the present example is composed of a current position detecting processing part  11  that detects a current position of a vehicle and the like; a data recording part  12  in which various kinds of data is recorded; a controller (e.g., navigation controlling part  13 ) that performs various kinds of arithmetic processing based on input information; an operating part  14  that accepts an operation from an operator; a liquid crystal display (LCD)  15  that displays information of a map and the like to the operator; a speaker  16  that outputs audio guidance regarding route guidance and the like; a communication device  17  that performs communication with the A road information transmitting system  3 A, the B road information transmitting system  3 B, the C road information transmitting system  3 C, a road information delivery center (not shown), and the like via a cellular phone network; and a touch panel  18  installed on a surface of the liquid crystal display  15 . Output signals of a vehicle speed sensor (not shown) that detects a travel speed of the vehicle may be inputted to the navigation controlling part  13 . 
     In addition, as shown in  FIG. 2 , the navigation device  1  is connected with the A road information transmitting system  3 A, the B road information transmitting system  3 B, and the C road information transmitting system  3 C through a network  2 . The A road information transmitting system  3 A, the B road information transmitting system  3 B, and the C road information transmitting system  3 C deliver “traffic information” such as information regarding congestion of roads and the like, traffic regulation information, and the like, which are created by collecting information of traffic control systems of police, Japan Highway Public Corporation, and the like, “coordinate point sequences” specifying positions of roads associated with the respective traffic information, and latest road information including a system ID identifying the road information transmitting system  3 A to  3 C at predetermined time intervals (for example, intervals of 5 minutes). In addition, as the network  2 , communication systems of, for example, a cellular phone network, a telephone network, a public communication network, a private communication network, a communication network such as an Internet can be utilized. 
     The navigation device  1  is capable of receiving the latest road information delivered from the respective road information transmitting systems  3 A to  3 C through the network  2  at predetermined time intervals (for example, at intervals of 5 minutes). In addition, the “traffic information” is detailed information regarding traffic information such as road congestion information regarding congestion of roads and the like, traffic regulation information due to road construction, building construction, and the like. In case of the road congestion information, the detailed information includes actual length of congestion, expected time when the congestion is solved, and the like. In case of the traffic regulation information, the detailed information includes duration of road construction, building construction, and the like, closed roads, one-way traffic, types of traffic regulation such as restricted lane, time period of traffic regulation, and the like. 
     In addition, the “coordinate point sequence” specifying the position of the road is composed of at least two coordinates (a start point and an end point) to specify the position of the road from map coordinate data stored in the respective road information transmitting systems  3 A to  3 C. In addition, the “coordinate point sequence” specifying the position of the road is provided with shape interpolating points optimal to the number of curvatures if the road includes complicated curvatures. For example, in case of a road having a curvature with right angle, the coordinate point sequence is composed of a start point, an end point, and a shape interpolating point that is set to the point of the curvature with right angle. 
     Hereinafter, the respective components composing the navigation device  1  are explained. The current position detecting processing part  11  includes a GPS  31  and the like, and can detect the current position of the vehicle, a vehicle direction, a travel distance, and the like. The current position detecting processing part  11  may be connected with a directional sensor (not shown), a distance sensor (not shown), and the like. 
     The data recording part  12  is provided with: various storage mediums including a hard disk (not shown) and a flash memory (not shown) serving as an external storage device; a driver (not shown) for reading a map information database (a map information DB)  25 , a traffic information database (a traffic information DB)  27 , a matching database (a matching DB)  28 , and a predetermined program, and the like, which are recorded in a storage medium and the like, and writing predetermined data in the hard disk, the flash memory; and the like. (Note: the term “storage medium” as used herein is not intended to encompass transitory signals.) 
     In addition, the map information DB  25  stores navigation map information  26  to be utilized for travel guidance and route calculation of the navigation device  1 . In addition, the traffic information DB  27  stores current traffic information in association with one or more link IDs of the navigation map information  26 , which are converted from coordinate point sequences corresponding to each traffic information, as described later. The current traffic information is information regarding current status of congestion of roads composed of actual length of the congestion, required time, cause of the congestion, expected time when the congestion is solved, and the like, which is created by collecting the traffic information received from the respective road information transmitting systems  3 A to  3 C. 
     The matching DB  28  stores a matching data file  51  (refer to  FIG. 3 ) storing link IDs of the navigation map information  26 , to which the coordinate point sequences received from the respective road information transmitting systems  3 A to  3 C are converted for matching tables F 1  to F 3  respectively associated with the A road information transmitting system  3 A, the B road information transmitting system  3 B, and the C road information transmitting system  3 C. 
     The navigation map information  26  here is composed of various kinds of information necessary for route guidance and map display, for example, newly-constructed road information for specifying newly-constructed roads, map display data for displaying a map, intersection data regarding intersections, node data regarding node points, link data regarding roads (links), route calculation data for calculating routes, facility data regarding POIs (Point of Interests) such as shop as a kind of facility, point search data for searching for a point, and the like. 
     The node data includes data regarding branch points (including intersections, T-shaped roads, and the like) on actual roads, coordinates (positions) of nodes set every predetermined distance according to curvature radius on each road and the like, node attributes indicating whether the respective nodes correspond to intersections and the like, connected link number lists that are lists of link IDs serving as identification numbers of links connected to the respective nodes, adjacent node number lists that are lists of node numbers of nodes adjacent through links to the respective nodes, and the like. 
     The link data includes: regarding the respective links forming roads, data indicating link IDs specifying links, link lengths indicating lengths of the links, coordinate positions (for example, latitude and longitude) of start points and end points of the links, presence or absence of center divider, widths of roads that the links belong to, inclination, cant, bank, condition of road surface, the number of lanes of roads, positions where the number of lanes decrease, positions where the widths are narrowed, rail crossing, and the like; regarding corners, data indicating curvature radii, intersections, T-shaped roads, entrances and exits of corners and the like; regarding road attributes, data indicating downhill lanes, uphill lanes, and the like; and regarding road types, data indicating general roads such as national roads, prefectural roads, narrow streets, and the like, toll roads such as national highways, intercity highways, general toll roads, toll bridges, and the like. 
     The facility data includes data indicating names, addresses, telephone numbers, coordinate positions on the map (for example, latitudes and longitudes of center positions, entrances, exits, and the like), facility icons and landmarks indicating positions of facilities on the map, and the like regarding POIs. The POIs include hotels in each region, amusement parks, palaces, hospitals, gas stations, parking tots, stations, airports, ferry ports, interchanges (IC), junctions (JCT), parking areas (PA), and the like. The data is stored together with facility IDs specifying POIs. 
     In addition, the contents of the map information DB  25  is updated by downloading update information delivered from a map information delivery center (not shown) through the communication device  17 . 
     As shown in  FIG. 1 , the navigation controlling part  13  composing the navigation device  1  is provided with: a CPU  41  serving as a computing device and a control device for performing overall control of the navigation device  1 ; internal storage mediums such as a RAM  42  used as a working memory when the CPU  41  executes various arithmetic processing and in which route data or the like when the route has been calculated is stored, a ROM  43  which records a program for control, and the like; a timer  45  for measuring a time; and the like. 
     The ROM  43  stores a program of “link ID converting processing” (refer to  FIG. 4 ) to convert coordinate point sequences specifying positions of roads associated with respective pieces of traffic information into link IDs of the navigation map information  26 . The coordinate point sequences are included in the road information received from the after-mentioned road information transmitting systems  3 A to  3 C. In addition, the ROM  43  stores a program of “coordinate point sequence determining processing (refer to  FIG. 8 ) to convert provisionally determined coordinate point sequences stored in the after-mentioned matching tables F 1  to F 3  into determined coordinate point sequences and store link IDs of the navigation map information  26  corresponding to the coordinate point sequences. 
     Further, the navigation controlling part  13  is electrically connected to respective peripheral devices (actuators) of the operating part  14 , the liquid crystal display  15 , the speaker  16 , the communication device  17 , and the touch panel  18 . 
     The operating part  14  is operated when correcting the current position at the time of starting travel and inputting a departure point as a guidance start point and a destination as a guidance end point, or when performing search for information relating to a facility, and is composed of various keys and a plurality of operation switches. The navigation controlling part  13  performs control to execute various operations according to a switch signal outputted by the operation such as pressing of each switch. 
     On the liquid crystal display  15 , map information of currently-traveling area, (refer to  FIG. 7  and the like), map information of the vicinity of the destination, operation guidance, an operation menu, key guidance, a recommended route from the current position to the destination, guidance information along the recommended route, traffic information, news, weather forecast, time, E-mail, TV programs, and the like are displayed. 
     The speaker  16  outputs audio guidance for traveling along the recommended route based on an instruction from the navigation controlling part  13 , and the like. For example, the audio guidance as “200 m ahead, to the right direction at XX intersection.” is provided. 
     The communication device  17  is a communication unit that performs communication with the road information transmitting systems  3 A to  3 C, the map information delivery center (not shown) through a cellular phone network or the like. The communication device  17  receives the latest road information delivered from the respective road information transmitting systems  3 A to  3 C and transmits and receives the latest version of the update map information to and from the map information delivery center. 
     The touch panel  18  is a transparent panel-type touch switch provided on the surface of the display screen of the liquid crystal display  15 , and configured such that various kinds of instruction commands can be inputted by pressing a button or the map displayed on a screen of the liquid crystal display  15  and, when performing drag by pressing the display screen with finger, the detection of the movement direction and movement speed of each finger and the detection of the number of fingers pressing the display screen can be performed. The touch panel  18  may employ an optical sensor type liquid crystal system where the screen of the liquid crystal display  15  is directly pressed. 
     Next, an example of the matching data file  51  stored in the matching DB  28  is described with reference to  FIG. 3 . 
     As shown in  FIG. 3 , the matching data file  51  is composed of the matching tables F 1  to F 3  which are associated with the A road information transmitting system  3 A, the B road information transmitting system  3 B, and the C road information transmitting system  3 C respectively. The matching tables F 1  to F 3  have the same structure. Therefore, the structure of the matching table F 1  is described. 
     The matching table F 1  is composed of “link ID,” “coordinate point sequence of A road information transmitting system,” “coordinate difference amount,” and “determination flag.” The “link ID” includes link IDs of the navigation map information  26 . In addition, the “coordinate point sequence of A road information transmitting system” includes coordinate point sequences specifying positions of roads, which are included in the road information received from the A road information transmitting system  3 A. Consequently, the coordinates of the start points and the end points of the coordinate point sequences are the coordinates of the map coordinate data stored in the A road information transmitting system  3 A and correspond to the coordinates of the nodes of both ends of the links. 
     In addition, the “coordinate difference amount” includes coordinate difference amounts in a X-direction and a Y-direction of the links of the navigation map information  26  identified by the “link IDs” against the coordinate point sequences when the “coordinate point sequences of A road information transmitting system” are allocated on the map of the navigation map information  26 . The east-west direction of the map of the navigation map information  26  is defined as the X-direction. The difference amount in the east direction is indicated with “+” and in the west direction with “−.” In addition, the north-south direction of the map of the navigation map information  26  is defined as the Y-direction. The difference amount in the north direction is indicated with “+” and in the south direction with “−.” 
     For example, when “X-direction” of the “coordinate difference amount” is “−15” and “Y-direction” is “+20,” the “coordinate difference amount” indicates that the link of the navigation map information  26  identified by the “link ID” is located at the position shifted by “−15” to the west direction and by “+20” to the north direction from the coordinate point sequence when the “coordinate point sequence of A road information transmitting system” is allocated on the map of the navigation map information  26 . 
     The “determination flag” includes “1” representing that the “link ID” and the “coordinate difference amount” corresponding to the “coordinate point sequence of A road information transmitting system” are stored and the coordinate point sequence is being determined and “0” representing that the “link ID” and the “coordinate difference amount” corresponding to the “coordinate point sequence of A road information transmitting system” are not stored and the coordinate point sequence is a provisionally determined coordinate point sequence of a new road. 
     That is, when “0” is stored in the “determination flag,” the coordinate point sequence included in the road information received from the A road information transmitting system  3 A is stored as the “provisionally determined coordinate point sequence” in the “coordinate point sequence of A road information transmitting system” and data is not stored in the “link ID” and the “coordinate difference amount” (refer to  FIG. 5 ), as described later. 
     Consequently, the coordinate point sequences specifying positions of roads that are included in the road information received from the B road information transmitting system  3 B are stored in “coordinate point sequence of B road information transmitting system” of the matching table F 2 . The coordinate point sequences specifying positions of roads that are included in the road information received from the C road information transmitting system  3 C are stored in “coordinate point sequence of C road information transmitting system” of the matching table F 3 . 
     II. Link ID Converting Processing 
     Next, the “link ID converting processing” method to convert the coordinate point sequences specifying the positions of the roads associated with the respective pieces of traffic information that are included in the received road information into the link IDs of the navigation map information  26 , is described with reference to  FIGS. 4 to 7 . The algorithms shown in  FIGS. 4-6  may be implemented in the form of a computer program that is stored in, for example, one or more of the storage mediums included in the navigation device  1 , and executed by the controller CPU  41 . Although the structure of the above-described navigation device  1  is referenced in the description of the process, the reference to such structure is exemplary, and the method need not be limited by the specific structure of the navigation device  1 . 
     The program may be executed when the road information has been received from any one of the road information transmitting systems  3 A to  3 C. 
     As shown in  FIG. 4 , the CPU  41  stores in the RAM  42  the road information received from any one of the road information transmitting systems  3 A to  3 C through the communication device  17  at Step (hereinafter, referred to as “S”)  11 . 
     At S 12 , the CPU  41  reads out the received road information from the RAM  42  and acquires a system ID in the road information, the system ID identifying the road information transmitting systems  3 A to  3 C. That is, the CPU  41  specifies using the system ID from which system among the road information transmitting systems  3 A to  3 C the road information has been delivered. 
     At S 13 , the CPU  41  sequentially reads out the “coordinate point sequences” included in the received road information from the RAM  42  and converts each of the “coordinate point sequences” into the “link ID” corresponding to the “coordinate point sequence” as the “coordinate point sequence” of the matching table corresponding to the system ID acquired at S 12 . That is, the CPU  41  sequentially stores the respective “link IDs” read from the matching table corresponding to the system ID acquired at S 12  in association with the respective “coordinate point sequences” in the RAM  42 . In addition, the CPU  41  stores the coordinate point sequences that have not been converted into the “link IDs” among the “coordinate point sequences” included in the road information as “unconverted coordinate point sequences” in the RAM  42 . 
     Specifically, for example, when the system. ID acquired at S 12  is the system ID identifying the A road information transmitting system  3 A, the CPU  41  sequentially reads out the “coordinate point sequences” included in the road information, reads out the “link ID” corresponding to each of the coordinate point sequences as the “coordinate point sequence of A road information transmitting system” of the matching table F 1 , and stores the read “link ID” in association with the “coordinate point sequence” in the RAM  2 . 
     For example, as shown in  FIG. 3 , when the coordinate point sequence of the road information received from the A road information transmitting system  3 A is “X1, Y1, X2, Y2, X3, Y3,” the CPU  41  stores a link ID “100” in the matching table F 1  in association with the coordinate point sequence “X1, Y1, X2, Y2, X3, Y3” in the RAM  42 . 
     Subsequently, at S 14 , the CPU  41  executes judging processing to judge whether all of the “coordinate point sequences” included in the road information have been converted into “link IDs” using the matching table corresponding to the system ID acquired at S 12 . That is, the CPU  41  executes judging processing to judge whether the “coordinate point sequences” included in the road information are being stored as the “unconverted coordinate point sequences” in the RAM  42 . 
     When it has been judged that all of the “coordinate point sequences” included in the road information have been converted into “link IDs,” that is, when it has been judged that the “coordinate point sequences” included in the road information are not being stored as the “unconverted coordinate point sequences” in the RAM  42  (S 14 : YES), the CPU  41  terminates the current processing. 
     On the other hand, when it has been judged that there is a “coordinate point sequence” that has not been converted into a “link ID,” that is, when it has been judged that a coordinate point sequence included in the road information is stored as the “unconverted coordinate point sequence” in the RAM  42  (S 14 : NO), the CPU  41  proceeds to the processing at S 15 . At S 15 , the CPU  41  executes judging processing to judge whether the coordinate point sequence stored in the RAM  42  as the “unconverted coordinate point sequence” is already stored as the “provisionally determined coordinate point sequence” of which the “determination flag” is set to “0” in the matching table corresponding to the system ID acquired at S 12 . 
     When it has been judged that a coordinate point sequence stored in the RAM  42  as the “unconverted coordinate point sequence” is already stored as the “provisionally determined coordinate point sequence” of which the “determination flag” is set to “0” in the matching table corresponding to the system ID acquired at S 12  (S 15 : YES), the CPU  41  terminates the current processing. 
     For example, as shown in  FIG. 3 , when the coordinate point sequence “X8, Y8, X9, Y9, X10, Y10” stored in the RAM  42  as the “unconverted coordinate point sequence” is stored as the provisionally determined coordinate point sequence “X8, Y8, X9, Y9, X10, Y10” in the “coordinate point sequence of A road information transmitting system” of which the “determination flag” is set to “0” in the matching table F 1  corresponding to the system ID acquired at S 12  (S 15 : YES), the CPU  41  terminates the current processing. 
     On the other hand, when it has been judged that a coordinate point sequence stored in the RAM  42  as the “unconverted coordinate point sequence” is not stored as the “provisionally determined coordinate point sequence” of which the “determination flag” is set to “0” in the matching table corresponding to the system ID acquired at S 12  (S 15 : NO), the CPU  41  judges that the coordinate point sequence is a coordinate point sequence of a newly-created road and proceeds to the processing at S 16 . At S 16 , the CPU  41  executes sub-processing of after-mentioned “matching table updating processing (refer to  FIGS. 5 and 6 ), and thereafter terminates the current processing. 
     III. Matching Table Updating Processing 
     Next, the sub-processing of the “matching table updating processing” to be executed by the CPU  41  at S 16  is described with reference to  FIGS. 5 to 7 . 
     As shown in  FIGS. 5 and 6 , firstly, at S 111 , the CPU  41  reads out an “unconverted coordinate point sequence” from the RAM  42  and draws the “unconverted coordinate point sequence” on the map of the navigation map information  26 . 
     The CPU  41  extracts as “candidate links” one or more links that have a shape similar to and a direction along the “unconverted coordinate point sequence” within a predetermined area in the vicinity (for example, within a 300 m square centered at the “unconverted coordinate point sequence”) of the “unconverted coordinate point sequence” among links of roads drawn by the map coordinate data of the navigation map information  26  and stores the link IDs of the respective candidate links. 
     Subsequently, at S 112 , the CPU  41  executes judging processing to judge whether a plurality of candidate links have been extracted, that is, judge whether there are a plurality of link IDs of the candidate links by reading out the link IDs of the candidate links from the RAM  42 . When it has been judged that only one candidate link has been extracted (S 112 : NO), the CPU  41  proceeds to the processing at S 113 . At S 113 , the CPU  41  converts the “unconverted coordinate point sequence” included in the road information received at S 11  into the link ID of the candidate link. That is, the CPU  41  stores the link ID of the candidate link in association with the “unconverted coordinate point sequence” in the RAM  42 . 
     At S 114 , the CPU  41  stores the “unconverted coordinate point sequence” in the “coordinate point sequence” of the matching table corresponding to the system ID acquired at S 12  and stores the link ID of the candidate link in the “link ID” of the matching table, and stores “1” in the “determination flag” of the matching table. In addition, the CPU  41  calculates a coordinate difference amount in the X direction and the Y direction of the candidate link against the “unconverted coordinate point sequence” allocated on the map of the navigation map information  26 , stores the respective values in the “X direction” and the “Y direction” of the “coordinate difference amount” of the matching table, and updates the matching table. 
     The CPU  41  reads out the “difference correction flag” from the RAM  42 , sets “OFF” to the “difference correction flag,” and stores it anew in the RAM  42 . Thereafter, the CPU  41  terminates the current sub-processing, returns to the main flowchart, and terminates the current processing. The “difference correction flag” is stored in the RAM  42  being set to “OFF” when the navigation device  1  has been started. 
     On the other hand, when it has been judged that a plurality of candidate links have been extracted (S 112 : YES), the CPU  41  proceeds to the processing at S 115 . At S 115 , the CPU  41  extracts link IDs of links existing within a predetermined area (for example, within 400 m square centered at each of the plurality of candidate links) in the vicinity of the plurality of candidate links among the link IDs stored in the “link ID” of the matching table corresponding to the system ID acquired at S 12  and stores the extracted link IDs in the RAM  42 . 
     Subsequently, at S 116 , the CPU  41  executes judging processing to judge whether two or more link IDs of the links existing within the predetermined area in the vicinity of the plurality of candidate links among the link IDs stored in the “link ID” of the matching table have been extracted. When it has been judged that there are no or one link ID of the link existing within the predetermined area in the vicinity of the plurality of candidate links among the link IDs stored in the “link ID” of the matching table (S 116 : NO), the CPU  41  proceeds to the processing at S 117 . 
     At S 117 , the CPU  41  stores the “unconverted coordinate point sequence” as the “provisionally determined coordinate point sequence” in the “coordinate point sequence” of the matching table corresponding to the system ID acquired at S 12 , stores “0” in the “determination flag” corresponding to the “provisionally determined coordinate point sequence” of the matching table, and updates the matching table. Consequently, no data is stored in the “link ID” and the “coordinate difference amount” corresponding to the “provisionally determined coordinate point sequence” of the matching table. In addition, the CPU  41  reads out the “difference correction flag” from the RAM  42 , sets the difference correction flag to “OFF,” and stores it anew in the RAM  42 . Thereafter, the CPU  41  terminates the current sub-processing, returns to the main flowchart, and terminates the current processing. 
     For example, as shown in  FIG. 3 , the CPU  41  stores the coordinate point sequence “X8, Y8, X9, Y9, X10, Y10,” which is stored in the RAM  42  as the “unconverted coordinate point sequence,” as the provisionally determined coordinate point sequence “X8, Y8, X9, Y9, X10, Y10” in the “coordinate point sequence of A road information transmitting system” of the matching table F 1  corresponding to the system ID acquired at S 12 . In addition, the CPU  41  stores “0” in the “determination flag” corresponding to the provisionally determined coordinate point sequence “X8, Y8, X9, Y9, X10, Y10” of the matching table F 1 . In addition, the CPU  41  does not store data in the “link ID” and the “coordinate difference amount” corresponding to the provisionally determined coordinate point sequence “X8, Y8, X9, Y9, X10, Y10” of the matching table F 1 . 
     On the other hand, when it has been judged that there are two or more link IDs of the links existing within the predetermined area in the vicinity of the plurality of candidate links among the link IDs stored in the “link ID” of the matching table (S 116 : YES), the CPU  41  proceeds to the processing at S 118 . At S 118 , the CPU  41  reads out data in the X-direction and the Y-direction of the “coordinate difference amounts” corresponding to the respective two or more link IDs of the matching table corresponding to the system ID acquired at S 12  and executes judging processing to judge whether the respective “coordinate difference amounts” are almost in the same direction and almost in the same distance, that is, the respective “coordinate difference amounts” are in the same direction pattern. 
     When it has been judged that the “coordinate difference amounts” corresponding to the respective two or more link IDs are almost in the same direction and almost in the same distance, that is, it has been judged that the “coordinate difference amounts” corresponding to the respective two or more link IDs are in the same direction pattern (S 118 : YES), the CPU  41  proceeds to the processing at S 119 . 
     At S 119 , the CPU  41  calculates the coordinate difference amounts in the X-direction and the Y-direction of the respective candidate links against the “unconverted coordinate point sequence” allocated on the map of the navigation map information  26 . The CPU  41  extracts the candidate link, of which the coordinate difference amount in the X-direction and the Y-direction against the “unconverted coordinate point sequence” is almost in the same direction and almost in the same distance as the “coordinate difference amounts” corresponding to the respective two or more link IDs among the respective candidate links, as the candidate link corresponding to the “unconverted coordinate point sequence.” 
     For example, as shown in  FIG. 7 , the CPU  41  extracts as the “candidate links” links  61  and  62 , which are similar to and in the direction along an “unconverted coordinate point sequence Q 1 ” composed of coordinates P 1 , P 2  and P 3 , within the predetermined area in the vicinity of the “unconverted coordinate point sequence Q 1 ” and stores the link IDs of the candidate links  61  and  62  in the RAM  42 . 
     The CPU  41  extracts link IDs of links  63  and  64  existing within the predetermined area in the vicinity of the candidate links  61  and  62  from the “link ID” of the matching table corresponding to the system ID acquired at S 12 . Thereafter, because the “coordinate difference amounts” corresponding to the link IDs of the links  63  and  64  of the matching table, that is, the “coordinate difference amounts” of the links  63  and  64  against coordinate point sequences R 1  and R 2  are almost in the same direction and almost in the same distance, the CPU  41  judges that the “coordinate difference pattern” is in the same direction pattern. 
     The CPU  41  extracts, as the candidate link corresponding to the “unconverted coordinate point sequence Q 1 ,” the candidate link  62 , of which the “coordinate difference amount” is in the almost same direction and in the almost same distance as the “coordinate difference amounts” corresponding to the link IDs of the links  63  and  64  of the matching table among the candidate links  61  and  62 . 
     As shown in  FIG. 5 , at S 120 , the CPU  41  converts the “unconverted coordinate point sequence” included in the road information received at S 11  into the link ID of the candidate link. That is, the CPU  41  stores the link ID of the candidate link in association with the “unconverted coordinate point sequence” in the RAM  42 . 
     Subsequently, at S 121 , the CPU  41  stores the “unconverted coordinate point sequence” in the “coordinate point sequence” of the matching table corresponding to the system ID acquired at S 12 , stores the link ID of the candidate link stored in association with the “unconverted coordinate point sequence” in the “link ID” of the matching table, and stores “1” in the “determination flag” of the matching table. 
     In addition, the CPU  41  calculates the coordinate difference amount in the X-direction and the Y-direction of the candidate link, of which the link ID has been stored in the matching table, against the “unconverted coordinate point sequence” allocated on the map of the navigation map information  26 , stores the respective values in the “X-direction” and the “Y-direction” of the “coordinate difference amount” of the matching table, and updates the matching table. In addition, the CPU  41  reads out the “difference correction flag” from the RAM  42 , sets the difference correction flag to “OFF,” and stores it anew in the RAM  42 . Thereafter, the CPU  41  terminates the current sub-processing, returns to main flowchart, and terminates the current processing. 
     On the other hand, when it has been judged at S 118  that the “coordinate difference amounts” corresponding to the respective two or more link IDs are not almost in the same direction and almost in the same distance, that is, it has been judged that the “coordinate difference amounts” corresponding to the respective two or more link IDs are not in the same direction pattern (S 118 : NO), the CPU  41  proceeds to the processing at S 122  shown in  FIG. 6 . At S 122 , the CPU  41  reads out the “difference correction flag” from the RAM  42  and executes judging processing to judge whether the difference correction flag is set to “ON,” that is, whether the difference is already corrected. 
     When it has been judged that the difference correction flag is set to “ON,” that is, the difference is already corrected (S 122 : YES), the CPU  41  proceeds to the processing at S 123 . At S 123 , the CPU  41  stores the “unconverted coordinate point sequence” as the “provisionally determined coordinate point sequence” in the “coordinate point sequence” of the matching table corresponding to the system ID acquired at S 12 , stores “0” in the “determination flag” corresponding to the “provisionally determined coordinate point sequence” of the matching table, and updates the matching table. 
     Consequently, data is not stored in the “link ID” and “coordinate difference amount” corresponding to the “provisionally determined coordinate point sequence” of the matching table. In addition, the CPU  41  reads out the “difference correction flag” from the RAM  42 , sets the difference correction flag to “OFF,” and stores it anew in the RAM  42 . Thereafter, the CPU  41  terminates the current sub-processing, returns to the main flowchart, and terminates the current processing. 
     On the other hand, when it has been judged that the difference correction flag is set to “OFF,” that is, it has been judged that the difference is not corrected (S 122 : NO), the CPU  41  proceeds to the processing at S 124 . At S 124 , the CPU  41  specifies the “coordinate difference pattern” when drawing, on the map of the navigation map information  26 , the “coordinate point sequences” corresponding to the two or more link IDs stored in the “link ID” of the matching table corresponding to the system ID acquired at S 12 , which have been extracted at S 115 , and the links corresponding to the respective link IDs of the navigation map information  26 . 
     Specifically, when against the “coordinate point sequences” corresponding to the respective two or more link IDs stored in the “link ID” of the matching table, the links corresponding to the respective links of the navigation map information  26  are inclined by a predetermined angle, the CPU  41  specifies the “coordinate difference pattern” as a “rotated pattern,” sets the rotated pattern flag to “ON,” and stores it in the RAM  42 . In addition, the CPU  41  calculates an inclination angle and stores it in the RAM  42 . The rotated pattern flag is stored in the RAM  42  being set to “OFF when the navigation device  1  has started. 
     In addition, when against the “coordinate point sequences” corresponding to the respective two or more link IDs stored in the “link ID” of the matching table, the links corresponding to the respective links of the navigation map information  26  are enlarged by a predetermined enlarged ratio, the CPU  41  specifies the “coordinate difference pattern” as an “enlarged pattern,” sets the enlarged pattern flag to “ON,” and stores it in the RAM  42 . In addition, the CPU  41  calculates the enlarged ratio and stores it in the RAM  42 . The enlarged pattern is stored in the RAM  42  being set to “OFF when the navigation device  1  has started. 
     In addition, when against the “coordinate point sequences” corresponding to the respective two or more link IDs stored in the “link ID” of the matching table, the links corresponding to the respective links of the navigation map information  26  are reduced by a predetermined reduced ratio, the CPU  41  specifies the “coordinate difference pattern” as a “reduced pattern,” sets the reduced pattern flag to “ON,” and stores it in the RAM  42 . In addition, the CPU  41  calculates the reduced ratio and stores it in the RAM  42 . The reduced pattern flag is stored in the RAM  42  being set to “OFF when the navigation device  1  has started. 
     Subsequently, at S 125 , the CPU  41  executes judging processing to judge whether the “coordinate difference pattern” is the “rotated pattern.” Specifically, the CPU  41  reads out the rotated pattern flag from the RAM  42  and judges whether the rotated pattern flag is set to “ON.” When it has been judged that the “coordinate difference pattern” is the “rotated pattern,” that is, when it has been judged that the rotated pattern flag is set to “ON” (S 125 : YES), the CPU  41  proceeds to the processing at S 126 . 
     At S 126 , the CPU  41  reads out the inclination angle acquired at S 124  from the RAM  42 , corrects the “unconverted coordinate point sequence” allocated on the map of the navigation map information  26  to the coordinate point sequence rotated by the inclination angle, and stores it anew as the “unconverted coordinate point sequence” in the RAM  42 . In addition, the CPU  41  reads out the difference correction flag from the RAM  42 , sets the difference correction flag to “ON,” and stores it anew in the RAM  42 . In addition, the CPU  41  reads out the rotated pattern flag from the RAM  42 , sets the rotated pattern flag to “OFF,” and stores it anew in the RAM  42 . Thereafter, the CPU  41  executes the processing at Sill and subsequent processing. 
     On the other hand, when it has been judged that the “coordinate difference pattern” is not the “rotated pattern,” that is, it has been judged that the rotated pattern flag is set to “OFF” (S 125 : NO), the CPU  41  proceeds to the processing at S 127 . At S 127 , the CPU  41  executes judging processing to judge whether the “coordinate difference pattern” is the “enlarged pattern.” Specifically, the CPU  41  reads out the enlarged pattern flag from the RAM  42  and judges whether the enlarged pattern flag is set to “ON.” 
     When it has been judged that the “coordinate difference pattern” is the “enlarged pattern,” that is, it has been judged that the enlarged pattern flag is set to “ON” (S 127 : YES), the CPU  41  proceeds to the processing at S 128 . At S 128 , the CPU  41  reads out the enlarged ratio acquired at S 124  from the RAM  42 , corrects the “unconverted coordinate point sequence” allocated on the map of the navigation map information  26  to the coordinate point sequence enlarged by the enlarged ratio, and stores it anew as the “unconverted coordinate point sequence” in the RAM  42 . 
     In addition, the CPU  41  reads out the difference correction flag from the RAM  42 , sets the difference correction flag to “ON,” and stores it anew in the RAM  42 . The CPU  41  reads out the enlarged pattern flag from the RAM  42 , sets the enlarged pattern flag to “OFF,” and stores it anew in the RAM  42 . Thereafter, the CPU  41  executes the processing at S 111  and subsequent processing. 
     On the other hand, when it has been judged that the “coordinate difference pattern” is not the “enlarged pattern,” that is, when it has been judged that the enlarged pattern flag is set to “OFF” (S 127 : NO), the CPU  41  proceeds to the processing at S 129 . At S 129 , the CPU  41  executes judging processing to judge whether the “coordinate difference pattern” is the “reduced pattern.” Specifically, the CPU  41  reads out the reduced pattern flag from the RAM  42  and judges whether the reduced pattern flag is set to “ON.” 
     When it has been judged that the “coordinate difference pattern” is the “reduced pattern,” that is, when it has been judged that the reduced pattern flag is set to “ON” (S 129 : YES), the CPU  41  proceeds to the processing at S 130 . At S 130 , the CPU  41  reads out the reduced ratio acquired at S 124  from the RAM  42 , corrects the “unconverted coordinate point sequence” allocated on the map of the navigation map information  26  to the coordinate point sequence reduced by the reduced ratio, and stores it anew as the “unconverted coordinate point sequence” in the RAM  42 . 
     In addition, the CPU  41  reads out the difference correction flag from the RAM  42 , sets the difference correction flag to “ON,” and stores it anew in the RAM  42 . The CPU  41  reads out the reduced pattern flag from the RAM  42 , sets the reduced pattern flag to “OFF,” and stores it anew in the RAM  42 . Thereafter, the CPU  41  executes the processing at S 111  and subsequent processing. 
     On the other hand, when it has been judged that the “coordinate difference pattern” is not the “reduced pattern,” that is, when it has been judged that the reduced pattern flag is set to “OFF” (S 129 : NO), the CPU  41  reads out the difference correction flag from the RAM  42 , sets the difference correction flag to “ON,” and stores it anew in the RAM  42 . Thereafter, the CPU  41  executes the processing at S 111  and subsequent processing. 
     IV. Coordinate Point Sequence Determining Processing 
     Next, “coordinate point determining processing” method to covert the provisionally determined coordinate point sequence stored in the respective matching table F 1  to F 3  into the determined coordinate point sequence and store the link ID of the navigation map information  26  corresponding to the coordinate point sequence is described with reference to  FIG. 8 . The algorithm shown in  FIG. 8  may be implemented in the form of a computer program that is stored in, for example, one or more of the storage mediums included in the navigation device  1 , and executed by the controller CPU  41 . Although the structure of the above-described navigation device  1  is referenced in the description of the process, the reference to such structure is exemplary, and the method need not be limited by the specific structure of the navigation device  1 . 
     The program shown by the flowchart in  FIG. 8  is regularly (for example, every 24 hours) executed by the CPU  41  during time periods such as late evening when processing such as route guidance is not executed 
     As shown in  FIG. 8 , firstly, at S 211 , the CPU  41  executes judging processing to judge whether “0” is stored in the “determination flag” of the matching table F 1 , that is, whether a “provisionally determined coordinate point sequence” is stored in the “coordinate point sequence of A road information transmitting system.” 
     When it has been judged that “0” is stored in the “determination flag” of the matching table F 1  (S 211 : YES), the CPU  41  proceeds to the processing at S 212 . At S 212 , the CPU  41  executes judging processing to judge whether all of the data of the “coordinate point sequence of A road information transmitting system” and the “determination flag” of the matching table F 1  have been sequentially read out. When it has been judged that all of the data of the “coordinate point sequence of A road information transmitting system” and the “determination flag” of the matching table F 1  have been sequentially read out (S 212 : YES), the CPU  41  proceeds to the processing at S 216 . 
     On the other hand, when it has been judged that there is data that has not been read out in the “coordinate point sequence of A road information transmitting system” and the “determination flag” of the matching table F 1  (S 212 : NO), the CPU  41  proceeds to the processing at S 213 . At S 213 , the CPU  41  reads out a set of data that is not read out yet among the data of the “coordinate point sequence of A road information transmitting system” and the “determination flag” of the matching table F 1 . 
     Subsequently, at S 214 , the CPU  41  executes judging processing to judge whether the coordinate point sequence read out from the matching table F 1  is the “provisionally determined coordinate point sequence,” that is, whether the determination flag is “0.” When the coordinate point sequence read out from the matching table F 1  is not the “provisionally determined coordinate point sequence,” that is, the determination flag is “1” (S 214 : NO), the CPU  41  executes the processing at S 212  and the subsequent processing. 
     On the other hand, when the coordinate point sequence read out from the matching table F 1  is the “provisionally determined coordinate point sequence,” that is, the determination flag is “0” (S 214 : YES), the CPU  41  stores the provisionally determined coordinate point sequence as the “unconverted coordinate point sequence” in the RAM  42 , and thereafter proceeds to the processing at S 215 . At S 215 , the CPU  41  executes the sub-processing of the “matching table updating processing” executed at S 16 , and thereafter executes the processing at S 212  and the subsequent processing. 
     When it has been judged that “0” is not stored in the “determination flag” of the matching table F 1  (S 211 : NO), the CPU  41  proceeds to the processing at S 216 . At S 216 , the CPU  41  executes judging processing to judge whether the processing at  211  and the subsequent processing has been executed for the matching table F 2  and the matching table F 3 . 
     When it has been judged that the processing at  211  and the subsequent processing has not been executed for the matching table F 2 , or it has been judged that the processing at  211  and the subsequent processing has not been executed for the matching table F 3  (S 216 : NO), the CPU  41  selects a matching table, for which the processing at S 211  and the subsequent processing is not executed yet, from the matching table F 2  and the matching table F 3  and executes the processing at  211  and the subsequent processing. 
     On the other hand, when it has been judged that the processing at  211  and the subsequent processing has been executed for the matching table F 2  and the matching table F 3  (S 216 : YES), the CPU  41  terminates the current processing. 
     As described in detail above, the navigation device  1  according to the present example, when the link ID corresponding to the coordinate point sequence included in the road information received from the A road information transmitting system  3 A, the B road information transmitting system  3 B, or the C information transmitting system  3 C is stored in the matching tables F 1  to F 3  corresponding to the road information transmitting system  3 A to  3 C, the CPU  41  converts the coordinate point sequence into the link ID stored in the matching tables F 1  to F 3 . Thereby, the CPU  41  is capable of accurately and rapidly specifying the link on the map of the navigation map information  26  corresponding to the coordinate point sequence included in the road information received from the road information transmitting systems  3 A to  3 C. 
     When the link ID corresponding to the coordinate point sequence included in the road information received from the respective road information transmitting systems  3 A to  3 C is not stored in the matching tables F 1  to F 3  corresponding to the road information transmitting systems  3 A to  3 C, if one candidate link corresponds to the “unconverted coordinate point sequence,” the CPU  41  converts the “unconverted coordinate point sequence” into the link ID of the one candidate link. Thereby, the CPU  41  is capable of accurately specifying the link on the map of the navigation map information  26  corresponding to the road information even when the link ID corresponding to the coordinate point sequence included in the road information received from the respective road information transmitting systems  3 A to  3 C is not stored in the matching tables F 1  to F 3  corresponding to the road information transmitting systems  3 A to  3 C. 
     If a plurality of candidate links correspond to the “unconverted coordinate point sequence,” the CPU  41  selects one candidate link that is located at the position in the same coordinate difference pattern and converts the “unconverted coordinate point sequence” into the link ID of the selected candidate link. Thereby, the CPU  41  is capable of more accurately specifying the link on the map of the navigation map information  26  corresponding to the road information even when the link ID corresponding to the coordinate point sequence included in the road information is not stored in the matching tables F 1  to F 3 . 
     In addition, when the CPU  41  has converted the “unconverted coordinate point sequence” into a link ID not stored in the corresponding matching table among the matching tables F 1  to F 3 , the CPU  41  stores the “unconverted coordinate point sequence” in the “coordinate point sequence” of the corresponding matching table, stores the link ID of the candidate link stored in association with the “unconverted coordinate point sequence” in the “link ID” of the matching table, and stores “1” in the “determination flag” of the matching table. In addition, the CPU  41  calculates the coordinate difference amount in the X-direction and Y-direction of the candidate link, whose link ID was stored in the matching table, against the “unconverted coordinate point sequence” allocated on the map of the navigation map information  26 , stores the respective values in the “X-direction” and the “Y-direction” of the “coordinate difference amount” of the matching table, and updates the matching table. 
     Thereby, when the link ID corresponding to the coordinate point sequence included in the road information delivered from the respective road information transmitting systems  3 A to  3 C is not stored in the corresponding matching table among the matching tables F 1  to F 3 , it is possible to update the matching table by specifying the link ID and the coordinate difference amount corresponding the coordinate point sequence and storing it anew in the matching table. Therefore, it is possible to improve the accuracy of the matching table. 
     In addition, when the CPU  41  regularly executes the “coordinate point sequence determining processing,” if the “provisionally determined coordinate point sequence” is stored in the matching tables F 1  to F 3 , the CPU  41  executes the sub-processing of the “matching table updating processing.” Through such processing, the CPU  41  updates the matching tables F 1  to F 3 . Therefore, it is possible to further improve the accuracy of the matching tables F 1  to F 3 . 
     While various features have been described in conjunction with the examples outlined above, various alternatives, modifications, variations, and/or improvements of those features and/or examples may be possible. Accordingly, the examples, as set forth above, are intended to be illustrative. Various changes may be made without departing from the broad spirit and scope of the underlying principles.