WO2005050593A1 - Position specifying method and device for executing that method - Google Patents

Abstract

A position specifying method uses positional data arranged with the positional information on nodes on a linear object of a digital map for correlating the linear object to the map data of its own digital map. The positional data is divided into a plurality of blocks and the position is specified in the unit of block. (a) In case of positional data including six nodes, the number of combinations of three candidate points becomes 729, (b) and when they are divided into tree blocks, the number of combinations of candidate points becomes 27. Consequently, high speed processing can be realized and the quantity of memory to be used can be reduced.

Description

 Specification

 Positioning method and device for implementing it

 Technical field

 The present invention relates to a position specifying method for specifying a position on a digital map from position data of roads and the like, and an apparatus for executing the method, which suppresses the amount of work memory used for the processing and reduces the amount of work required. It implements processing.

 Background art

 [0002] Currently, VICS (Road Traffic Information and Communication System), which provides a service for providing road traffic information to car navigation devices and the like, specifies a road using a link number defined in the road network, and identifies the road. Is displayed.

 However, the link numbers defined in the road network need to be replaced with new numbers when new or changed roads are established, and the digital map data produced by each company must be updated accordingly. The method of specifying the location of the road imposes a large social cost on maintenance.

 [0003] In order to improve such a point, Patent Document 1 below proposes a method of transmitting a road position on a digital map without using a common link number. In this method, the transmitting side sets multiple nodes pi, ρ2, and 'ρ に in the road section to be transmitted on the digital map of the transmitting side, as shown in Fig. 15 (a). As shown in (1), "road position data" in which the position data of the plurality of nodes pi, ρ2,. Then, the traffic information in the road section expressed by the distance of the reference node (for example, pi) force and the road position data are transmitted to the receiving side. The receiver identifies the road section by associating each node position included in the road position data with its own digital map, identifies the road section, and reproduces the traffic situation based on the information on the distance from the reference node.

 [0004] Further, Patent Document 2 below proposes a method of reducing the data amount by performing variable length coding on the road position data. In this method, as shown in Fig. 16 (a), nodes P, P are set at fixed distance intervals L on the road section to be transmitted (this is referred to as "equidistant resampling").

 H i

), And the position data of each node excluding the starting end is declination 0 j from the adjacent node (Fig. 16 (b)). Or, the deviation of the statistical statistical prediction value Δ 0 j (Fig. 16 (c)) (the predicted value obtained by predicting the declination of the node を j using the declination of the previous node (Θ1, 22 · ·) And the actual declination Θj), which is subjected to variable-length coding, and the coded data and the starting latitude / longitude data are transmitted to the receiving side. The receiving side decodes the encoded data to restore the position data of each node, and specifies the position to specify the road section.

[0005] Several methods are known for map matching as position identification. For example, the macro map matching algorithm used by a car navigation device to identify the position of the vehicle on a digital map is as follows.

 (1) As shown in Fig. 17 (a), on the digital map, search for a link around the point WP (waypoint) assigned by the GPS receiver, and search for a link centered on the first WP1. A link with a direction within ± B ° (for example, about 45 °) that is less than ± B ° (for example, about 45 °) from the direction of travel of the vehicle is detected within four meters (about 250m), and this link is set as a candidate point (marked with X). . The number of links (n) at the candidate points is about 5-8. In FIG. 17 (b), the candidate points of WP1 are 1-1, 1-2, and 1-3.

 [0006] (2) As shown in Fig. 17 (b), a link with a direction within ± B ° of the difference between the traveling direction of the vehicle and the direction of travel of the vehicle is detected within the A meter square centered on the next WP2. , And n links are set as candidate points (2-1, 2-2, 2-3).

 (3) Repeat this process until the last WP is reached.

 (4) Each candidate point is connected along a road link to create a shape pattern. In the case where the candidate points do not connect along the road (for example, WP3 candidate points 3-3 and 3-2 cannot be connected to the next WP4 candidate point along the road), Do not create a pattern. (5) Each shape pattern is compared with the shape of WP1, WP2, ···, and the most similar shape pattern, that is, the shape of WP1, WP2, ··· evaluated by the standard deviation at a short distance, etc. One with a small variation is selected.

 [0007] Such a position specifying method and a map matching method can also be applied to a case where a target road represented by road position data is specified on a digital map. Each node whose position is given by the road position data is referred to as a WP. , The target road can be determined.

Patent Document 1: JP 2001-41757 A Patent Document 2: Japanese Patent Application Laid-Open No. 2003-23357

[0008] In this road position data, the efficiency of data compression by variable-length coding improves as the number of nodes increases. However, the localization, M-number the number of WP, when the average number of candidate points per each WP and the N, wherein the stage obtained shape pattern of (4), and N ^M number of combinations Therefore, when the number of nodes (= the number of WPs) is large, the processing amount becomes enormous, and a long processing time is required. If the distance of the target road is long, a work memory with a large amount of memory is required to develop the map data.

 Disclosure of the invention

 Problems to be solved by the invention

[0009] The present invention solves such a conventional problem. Even when the number of nodes included in the position data is large, the shape can be digitally mapped on a digital map with a small amount of memory usage and at a high speed. The purpose of the present invention is to provide a method for specifying a position that can be specified in any other way, and to provide an apparatus for performing the method.

 Means for solving the problem

[0010] In the present invention, in a position specifying method for receiving position data of nodes arranged on a linear object on a digital map and associating the linear object with map data on the digital map on the receiving side, After the edited position data is edited on the receiving side, the association is performed.

 Therefore, by editing the received position data, the receiving side can specify the shape on the digital map with a small amount of memory usage and at high speed.

In the present invention, position data is divided into a plurality of blocks, and position identification is performed in units of blocks.

 Therefore, the number of generated shape patterns is reduced, and high-speed processing can be performed. Also, less memory is used.

 In the present invention, a block is generated by cutting position data at a fixed distance.

In this case, the fixed distance is set to be equal to or less than the length of one side of the minimum unit of the map data. I have to set.

 In this way, location identification can be performed simply by loading map data for at most four units into memory.

 [0013] Further, when the linear object has a road shape, a cut portion at a fixed distance is made to coincide with a change point of the road type.

 By doing so, the operation efficiency of the “hierarchical position identification method” described later increases.

Further, in the present invention, the block is generated by cutting the position data in units of the length of one side of the unit of the map data for displaying the linear object.

 In this way, it is possible to cut the position data efficiently without wasting power.

[0015] In this case, the cutting position of the position data is set to be aligned with the boundary of the unit.

 By doing so, the number of units to be used can be reduced.

Further, in the present invention, the block is generated by cutting the position data at a fixed number of nodes.

 By doing so, even when the nodes are locally dense, the number of generated shape patterns can be reduced, and the overall processing amount can be reduced.

Further, according to the present invention, when the linear object has the road shape of the target road of the traffic information, the block is generated by cutting the position data in accordance with the division unit of the traffic information. I have.

 By doing so, it is easier to match traffic information with the target road.

Further, in the present invention, the nodes that do not cause the erroneous matching in the position data force are thinned out, and the position specifying method is performed using the position data in which the nodes are thinned out.

 When the number of nodes decreases, the number of generated shape patterns decreases, and high-speed processing becomes possible.

In this case, a node to be decimated is selected in consideration of the distance and declination between the node and an adjacent node, and the density of a linear object around the node. .

 In this way, a sword that does not cause misidentification can be selected.

In the present invention, the position force of the map data corresponding to the position information of the node The angle range in which to search for the candidate points is adaptively set according to the degree of bending of the linear object.

 By doing so, if the degree of bending of the linear object is large, the angle range is expanded, and the true linear object is not leaked from the candidates! If the degree of bending of the linear object is small, the angle range can be narrowed so that the number of candidate points does not increase unnecessarily.

 In this case, the angle range is set in consideration of the degree of bending of the linear object in a predetermined distance section before or after or in front of the node and the density of the linear object in the predetermined distance section. ing.

 By doing so, the angle range can be set adaptively.

Further, in the present invention, a parameter used for associating a remaining portion of a linear object is adaptively changed with reference to an association result of a portion of the linear object which has already been associated. I have to.

 By doing so, the average error occurrence situation is learned from the error situation of the linear object in the section where the position identification method has already been completed, and the candidate points in the position identification method in the subsequent sections are learned based on the learning result. The search range and candidate point search direction range can be set adaptively.

 In the present invention, the information processing apparatus further includes a position data acquisition unit that acquires position data of nodes arranged on a linear object on the digital map, and a position data cutting unit that divides the position data into a plurality of blocks. And a node thinning-out processing unit that thins out nodes that do not cause erroneous identification based on the block power, and a search range for searching for candidate points of nodes included in this block are adaptively set. A candidate point search direction range deciding unit that sets candidate points of nodes included in the search range on the digital map data, and a shape corresponding to the linear object is displayed on the map data based on the set candidate points. And a position specification processing unit specified by.

 This device can perform position identification at high speed without using much memory. The present invention also includes a program for causing a computer to execute the above-described position specifying method.

The invention's effect The position specifying method of the present invention can perform a map matching process at a high speed without using a large amount of memory, and can achieve a memory saving and a high-speed mapping.

 In addition, the apparatus of the present invention that performs this position specifying method can be configured using a small-capacity memory, and nevertheless, can perform high-speed processing.

 Brief Description of Drawings

 FIG. 1 is a diagram illustrating a process of dividing road position data by a position specifying method according to a first embodiment of the present invention.

 FIG. 2 is a diagram for explaining a situation in which a used memory amount is reduced in a road position data dividing process according to the first embodiment of the present invention.

 FIG. 3 is a block diagram illustrating a configuration of an apparatus that executes a position specifying method according to the first embodiment of the present invention.

 FIG. 4 is a diagram showing units of map data.

 FIG. 5 is a diagram illustrating the reason why the number of units used is reduced by the division processing of road position data according to the first embodiment of the present invention.

 FIG. 6 is an example of a map displaying road position data.

 FIG. 7 is a diagram for explaining node thinning-out processing in the position identification method according to the first embodiment of the present invention.

 FIG. 8 is a flowchart showing a procedure for thinning-out nodes in the first embodiment of the present invention.

 FIG. 9 is a flow chart showing a procedure for adaptively setting a candidate point search azimuth range in the embodiment of the present invention.

 FIG. 10 is a diagram illustrating candidate points obtained by adaptively setting a candidate point search azimuth range according to the first embodiment of the present invention.

 FIG. 11 is a flowchart showing a procedure for matching traffic information with the position specifying method according to the first embodiment of the present invention.

 FIG. 12 is a diagram showing a correction process of an end point of a target road block in the position specifying method according to the first embodiment of the present invention.

FIG. 13 schematically illustrates a method for adaptively setting a candidate point search range according to the second embodiment of the present invention. FIG.

FIG. 14 is a flowchart showing a procedure for adaptively setting a candidate point search range in the second embodiment of the present invention.

[15] FIG. 15 is a diagram illustrating road position data.

 FIG. 16 is a diagram illustrating a process for encoding road position data.

FIG. 17 is a diagram showing a conventional position specifying method.

Explanation of symbols

10 Information processing equipment

 11 Location dataTraffic information receiver

 12 Encoded data decoder

 13 Position data restoration unit

 14 Position data cutting section

 15 Node thinning processing unit

 16 Candidate point search range determination unit

 17 Digital Tanole Map Database

 18 Shape pattern generation 'evaluation unit

 19 Traffic Information Editor

 20 Cutting shape correctionTraffic information superimposition section

 21 Information Utilization Department

BEST MODE FOR CARRYING OUT THE INVENTION

 (First Embodiment)

 In the position specifying method according to the embodiment of the present invention, the receiving side that has received the road position data edits and processes the road position data so that the position can be specified in a short amount of memory and in a short time. Map matching is performed using the processed road position data. On the receiving side, in order to reduce the amount of memory used for location identification and shorten the processing time,

 (1) Road position data division

(2) Thinning out nodes from road position data (3) Adaptive setting of candidate point search range

 Are executed. The outline of each process will be described.

 In the present embodiment, the road on the digital map corresponds to the linear object. The shape of the road is not particularly limited, such as a straight line, a curve, and a zigzag shape.

 In addition, the position identification method in this specification also includes the concept of map matching when the position data is regarded as road shape data. While position data is defined by a set of nodes, it is also possible that the set of nodes forms a linear shape. What defines such a shape can be considered as shape data. That is, in the map matching, the road shape (road shape data) on the transmitting side is directly associated with the road shape (road shape data) on the receiving side.

(1) Division of road position data

 In order to increase the compression efficiency, a large number of nodes are included. The length of the road position data is appropriately cut according to the convenience of the receiving side, and the divided road position data (called “road position data block”) is obtained. Specify the location in units.

[0029] For example, as shown in Fig. 1 (a), if the road position data including six nodes is specified as it is, when the average number of candidate points per WP is three, the combination of shape patterns is used. the number is a 3 ⁶ = 729, as shown in FIG. 1 (b), when the road location data is divided into three road location data blocks performs location specified including two nodes, the number of combinations of shapes pattern is, 3 X 3 ² = 27 pieces and makes the processing amount decreases.

 In addition, as schematically shown in FIG. 2, the amount of memory used can be reduced by cutting the road position data and individually specifying the road position data blocks. In general, the amount of memory required for location identification increases in proportion to the square of the length of the road location data. For example, when the maximum length of road position data is 10 km, a force that requires a memory size to expand map data for 10 km square (100 square km) is 1 km square when the maximum length of road position data is 1 km. (1 square km) of memory.

[0030] (2) Thinning out nodes from road position data

In general, the higher the number of nodes, the higher the accuracy of position identification, but the number of WPs increases accordingly, so the number of combinations of shape patterns increases exponentially, and processing performance increases. Deteriorate. By selecting and thinning out a zone that has little risk of deteriorating the position identification accuracy, the processing time can be reduced and the work memory usage can be reduced.

 (3) Adaptive setting of candidate point search range

 In the conventional position identification method, when extracting candidate points for WP, the condition of candidate points is that the angle difference from the heading of the vehicle is within ± B °, and this ± B ° is used as an invariant value (Predetermined value). The smaller the value of B, that is, the smaller the candidate point search range related to the search azimuth (“candidate point search azimuth range”), the smaller the number of WP candidate points and the higher the processing performance. May occur, and the possibility of erroneous matching increases. On the other hand, when the value of B is increased, the accuracy increases, but the number of candidate points increases, and the processing performance deteriorates.

 [0032] In the position identification of the car navigation device, it is not known what the "road to go to" will be, but in the position identification based on the road position data, attention is paid to the roads that are going to be overtly specified. Observe the predetermined distance before and after or in front of the WP (100 to 200 m, since the map error is about 100 m at the maximum), observe the curve situation, and if a straight line continues, reduce the value of B to 10 °, If there is a curve, the candidate point search direction range can be made variable, such as expanding to 60 °.

 By adaptively changing the candidate point search range in this way, roads that are extremely unlikely to be “true roads” can be efficiently excluded as candidate powers, and the processing performance for position identification can be improved. The amount of work memory used for calculation can be reduced.

 FIG. 3 shows the configuration of the information processing apparatus 10 that performs this position identification method.

 The information processing device 10 receives traffic information and road position data of a target road from an information providing device, identifies a target road by performing position identification, a car navigation device, a PC, a PDA, a mobile phone, and the like. Or a probe information collection center (information collection) that receives measurement information (traffic information) and road position data indicating the traveling locus from the on-board equipment of the probe car and identifies the traveling locus by performing position identification. Distribution center).

[0034] The information processing device 10 includes a digital map database 17, position data for receiving road position data and traffic information from an information transmitting device and a traffic information receiving unit 11, and decodes encoded data. Coded data decoding unit 12 to restore road position data A position data restoring unit 13, a position data cutting unit 14 for performing "division of road position data" processing, and a traffic information editing unit 19 for editing traffic information so as to be consistent with the divided road position data blocks. A node thinning-out processing unit 15 that performs “node thinning of road position data” and a candidate point search range determining unit 16 that performs “adaptive setting of a candidate point search range” and sets a node candidate point; A shape pattern generation and evaluation unit 18 generates and evaluates a shape pattern connecting the node candidate points and specifies a road section (referred to as a “target road block”) corresponding to each of the road position data blocks. Correct the end of each target road block so that the road blocks are continuous, and reproduce the traffic information of each target road block. And an information utilization unit 21.

 The position data of the information processing apparatus 10 and the road position data and the traffic information received by the traffic information receiving unit 11 are decoded by the encoded data decoding unit 12 and become the position data train of the node. The road position data is restored by the position data restoration unit 13.

(A) Division processing of road position data by the position data cutting unit 14

 The position data cutting unit 14 cuts the restored road position data by one of the following methods (a-1) and (a-6).

 (a-1) The road position data is cut at a fixed distance determined in advance (or equally cut so as to be less than or equal to the fixed distance).

 As shown in Fig. 4, the map data stored in the digital map database 17 is usually divided into four sub-meshes of approximately 10km x 10km (the exact size depends on the location). It is composed of units divided into 1Z2), 16 divisions (1Z4), and 64 divisions (1Z8), and the units in each region are set so that the data amount of each unit is approximately the same level. The smallest unit of 64 divisions is about 1.25 km square. Therefore, when cutting road position data at a fixed distance, the length of the fixed distance is set to about lk m. In this way, the position of the divided road position data blocks can be specified only by using the map data of at most four units.

FIG. 5 shows this pattern. Here, one side of the unit size is 1 km, and the length of road position data is 3.2 km. Locating road position data with the exact length In such a case, as shown in Fig. 5 (a), it is necessary to prepare a memory that can expand 4 x 4 unit data at worst. On the other hand, if the road position data is cut at the cutting point to make the length 1 km, as shown in Fig. 5 (b), this can be handled by the amount of memory that expands 2 x 2 unit data.

 [0038] (a-2) When the road position data is cut at a fixed distance (or a fixed distance or less), the changing point of the road type is set as the cutting point.

 The present inventor has previously proposed a position specifying method called “hierarchical position specifying”. In this method, the map data is hierarchized with reference to the road type, the upper layer includes only the main roads, and as the level goes down, the hierarchical map data in which roads of the new road type are sequentially added is used. To determine the position. In this method, the processing time can be reduced by specifying the position using the map data of the highest hierarchy as possible.

 [0039] When the road position data is cut off according to (a-2), the map data of the hierarchy to be used is specified in the hierarchical position specification, so that the operation efficiency of the hierarchical position specification is improved. In addition, it is more efficient that the change point of the road type that should be the cutting point is made to correspond to the road type that distinguishes the hierarchy in the hierarchical map data.

 (A-3) The road position data is cut in accordance with the unit size around the pertinent location.

 If the road position data represents a road in an area of a unit of 64 division size, the road position data is cut in units of one side length (approximately lkm) of the size of 64 division, and the area of the unit of 16 division size is cut. If the road is indicated in, the road position data is cut in units of one side (2.5 km) of 16 division sizes. Therefore, referring to the map data in the digital map database 17, the unit size of the area where the road position data can be accommodated is determined from the latitude and longitude of both ends of the road position data or the midpoint, and the unit length of cutting is determined. I do.

 (A-4) The road position data is cut in accordance with the unit boundaries.

When the road position data is cut according to the unit size of the location, the latitude and longitude of the boundary (left / right / up / down) of the cut are obtained from the digital map database 17, and along the boundary (or the boundary). Disconnect the road position data). By doing so, the number of units read from the digital map database 17 can be reduced, and It is possible to reduce the amount of memory for expanding the cut data.

 (A-5) The road position data is cut into units of a fixed number of nodes.

 There are cases where many nodes are concentrated locally on roads in densely populated areas in urban areas or on mountain pass roads. In this case, if the road position data is cut at a fixed distance, there is a possibility that a number of nodes are included in some road position data blocks.

 [0043] The processing performance of the position identification greatly depends on the number of nodes as well as the distance in terms of the processing algorithm. When the road position data block includes a large number of nodes, the processing amount of the block is enormous. This results in an increase in the overall processing amount. Therefore, it is better to cut the road position data in units of a certain number of nodes and to equalize the number of nodes in each road position data block so that road position data blocks containing many nodes do not appear. The number of combinations of the shape patterns shown in 1 can be reduced, and the total processing time can be reduced.

 (A-6) The road position data is cut in accordance with the division unit of the traffic information.

 If the information transmission device cuts the target road for traffic information into unit lengths and encodes and transmits the traffic information divided into the unit, the road position data is cut according to the divided position of the traffic information. I do.

 The problem when disconnecting the road position data is the correspondence with the traffic information linked to the road position data. In other words, it is necessary to edit traffic information appropriately so as to correspond to the road position data block. Since the traffic information is created based on the map data of the information transmission device and positioned on the target road, if the traffic information is simply cut at a distance, the traffic information may deviate from the road distance of the target road block after the position is specified. There is. When the information transmitting device transmits traffic information in units of unit length, the road position data is cut off according to the divided position of the traffic information, so that there is no extra calculation for the correspondence with the traffic information. Very easy to take.

[0045] (b) Inter-node bow processing by the node I processing unit 15

 The inter-node bow I processing unit 15 performs a process of thinning out nodes included in the road position data block.

The basic concept of thinning out nodes is as follows (b-1), (b-2), and (b-3). (b-1) If the declination value of the node is less than a certain value, thinning is performed.

 (b-2) If the distance between nodes is equal to or smaller than a certain value, thinning is performed.

 (b-3) Considering the road density in the surrounding area, when the road density is high, refrain from thinning nodes so that erroneous matching does not occur. When the road density is low, nodes are thinned out because there is little risk of erroneous matching.

 When executing the node thinning process, a thinning condition combining these ideas is set, and whether to thin the node is determined in light of the condition.

 For example, the thinning conditions are set as follows.

 "When the surrounding road density is P1, (1) if the absolute value of the declination of the node is less than 1, and (2) the node interval is less than β1, skip the nodes."

 The peripheral road density P1 is a value (ranked value) indicating a road extension per unit area around the target node. This P1 is also a value (ranked value) indicating the size of the unit in which the target node exists. In other words, since the unit size differs depending on the road density, the surrounding road density can be estimated by checking the unit size.

 [0047] Comparing the road position data near ぉ and Α (main line) with the road position data near B (connection road) in the map of Fig. 6, the peripheral road density P1 and the distance between nodes are Although there is no significant difference between the two, the angle near the node A is small and the angle near the node B is large. Therefore, the nodes near A can be thinned out, but the nodes near B do not meet the thinning conditions. If the node near B crosses I, there is a possibility of erroneous matching to the main line.

 FIG. 7 shows, step by step, how the nodes included in the road position data are decimated.

Node 1 is left as the starting point (a). Node 2 is left because the declination has a constant value of 1 or more (α 1: approximately 1 2 °) (b). Node 3 is deleted because the argument is within a constant value α1 and the node interval is within β1 (c). Node 4 has the declination within a1, but keeps it because the node interval is j8 1 or more (c). Node 5 is deleted because the argument is within a fixed value α1 and the node interval is within j81 (d). Node 6 is left because the declination has a constant value of 1 or more (e). Node 7 is left for termination (e). FIG. 8 shows a processing flow of the node thinning processing section 15.

 Obtain the road position data block to be decimated (Step 1), start from the node with node number n = 1 (Step 2), acquire the information on node n (Step 3), and do not worry about thinning! It is determined whether or not (step 4).

[0050] There are the following nodes that are not supported by thinning and that cannot be thinned.

 'Start and end

 • Nodes that clearly indicate the position for the purpose other than the shape used for specifying the position, such as the block code or event occurrence position (event occurrence point, attribute change point, block end point position, etc.)

 In the case of a node that can be thinned out, the surrounding road density P1 is calculated from the latitude and longitude of the node, and the thinning-out parameters α 1 and β 1 are determined (step 5).

 Next, the absolute value of the argument α between the node (η-1) → node η and the distance j8 between the nodes are calculated (Step 6), and it is determined whether α <α 1 and whether β is less than β1. Is determined (step 7), and if yes, the node n is thinned out (step 8). If No, do not skip. This process is performed sequentially for all nodes (steps 9 and 10).

(C) Candidate Point Search Range Determination Unit 16 Adaptively Setting Candidate Point Search Range

 The candidate point search range determination unit 16 adaptively determines a candidate point search range in position identification with respect to the road position data block that has been thinned out by the inter-node bow processing unit 15, and determines the search range power of the node. Search and set candidate points.

 The basic idea when the candidate point search range determination unit 16 determines the candidate point search azimuth range is the following (c1) or (c2) and (c3).

 (c 1) Look at the situation (the degree of curvature) of road position data several tens and several hundreds meters before and after the node of interest, and determine the candidate point search azimuth range of the node.

 (c 2) The degree of bending of the road position data in the direction in which the position of the node of interest is to be specified in the future is determined, and the candidate point search azimuth range of the node is determined.

 (c 3) Consider road density.

FIG. 9 shows a processing flow of the candidate point search range determination unit 16.

The road position data block for which the candidate point is set is obtained (step 11), and the node number n = The node power of 1 is also obtained in order (step 12), and information on each node existing within the fixed section length determined before and after node n is obtained (step 13). The absolute value of the declination is calculated, and the statistical value (maximum value / average value) of the declination absolute value is calculated (step 14). Considering the road density around node n, the azimuth range B at the time of candidate point search is calculated by, for example,

 B = Statistical value X τ + γ (τ and γ are parameters determined according to road density) (Step 15).

 Next, on the map of the digital map database 17, it exists within Α meters around the position of the node η and within the azimuth range of “the azimuth of the node n ± B °” from the position of the node n. A candidate point is set for the link to be made (step 16). This process is performed for all nodes (steps 17 and 18).

 By determining the candidate point search azimuth range by such a procedure, as shown in FIG. 10, in the case of WP 3, WP4, and WP5, there are curves before and after that, so that the candidate point search azimuth range is Widely set, and candidate points are definitely set on "true roads". In the case of WP6 and WP7, the value power S of B becomes smaller, so that (6-2) and (7-2) also deviate from the candidate power, and the subsequent formed pattern generation processing can be performed efficiently.

 The shape pattern generation / evaluation unit 18 connects the candidate points set by the candidate point search range determination unit 16 along a road link to create a road shape pattern. In the digital map, candidate points are connected along the road. In some cases, no road shape pattern is created. Next, each road shape pattern was compared with the shapes of node 1 (WP1), node 2 (WP2), and the like, and the most similar road shape pattern, that is, the standard deviation of a short distance, was evaluated. WP1, WP2, ··· Select one with small variation from the shape.

 Thus, the target road block is specified by specifying the position of the road position data block.

 Cutting shape correction • The traffic information superimposing unit 20 corrects the “displacement” at the end of each target road block so that the target road block is connected to an adjacent target road block.

[0058] On the other hand, the traffic information editing unit 19 obtains information on the cutting unit of the road position data from the position data cutting unit 14, and matches the received traffic information with each road position data block. Edit to

 The cutting shape correction / traffic information superimposing section 20 obtains the traffic information edited in block units by the traffic information editing section 19 and superimposes the traffic information on the target road block whose end point has been corrected, thereby reproducing the traffic information in block units.

 [0059] The flowchart of FIG. 11 shows a procedure leading to reproduction of traffic information.

 When the data is received (step 21), the position data cutting unit 14 determines the cutting unit of the road position data (step 22), and cuts the road position data into road position data blocks. The traffic information editing unit 19 edits the traffic information so as to be consistent with each road position data block (step 23). When the road position data is cut by the method described in (a-6) (the road position data is cut according to the division unit of the traffic information), there is no need to edit the traffic information.

 [0060] The node thinning processing unit 15, the candidate point search range determination unit 16, and the shape pattern generation / evaluation unit 18 perform the above-described processing in the order of the road position data block power of the block number n = l, and specify the position. To identify the target road block n of the road position data block n (step 25). When the processing of step 25 is completed for all road position data blocks (steps 26 and 27), the cut shape correction 'traffic information superimposing unit 20 checks the connectivity of the end points of each target road block (step 26). 28) If there is a “displacement” at the end point of the target road block, a correction process is performed (step 29).

 FIG. 12 schematically shows a correction process for a deviation of a target road block end point.

 The road position data blocks are individually located (a), and if the end points of the target road block are shifted (b), the midpoint of the end points of both target road blocks is set as the end point of the target road block ( c).

 [0062] In this correction process, the latitude and longitude of the road position data block N after the position identification on the starting end side are (XI, ΥΙ), and the latitude and longitude of the end position of the road position data block (Ν + 1) are specified. When longitude is (Χ2, Υ2), the point on the road closest to X = (Xl + X2) / 2 and Υ = (Yl + Y2) / 2 is the end point of the target road block. Processing.

Cut shape correctionThe traffic information superimposing unit 20 superimposes the traffic information edited by the traffic information editing unit 19 on each target road block whose end point has been corrected, and Reproduce (Step 30).

As described above, when specifying the position of the road position data,

 (1) Road position data division

 (2) Thinning out nodes from road position data

 (3) Adaptive setting of candidate point search range

 By doing so, the processing efficiency is improved, the processing time is shortened, and the amount of memory used can be reduced.

 Here, in specifying the position of the road position data, the force described in the case of performing all of the above (1), (2), and (3) is only required to perform one or two of these forces. However, it is clear that processing efficiency can be improved, processing time can be shortened, and the amount of memory used can be reduced.

 (Second Embodiment)

 In the second embodiment of the present invention, another method relating to the adaptive setting processing of the candidate point search range performed by the candidate point search range determination unit 16 of the information processing apparatus 10 in FIG. 3 will be described.

 When the receiving side identifies the position using the road position data sent from the transmitting side and identifies the road section on its own digital map, the transmitting side uses the digital map to create the road position data. If the data and the digital map data used by the receiver for location identification are similar! / ヽ, the difference between the WP and the candidate point on the target road ("true road") identified from the WP will be smaller and similar. If not, the difference is large.

[0066] The difference between the WP and the candidate points on the "true road" is the scale difference (1Z25,000, 1 / 10,000, 1 / 2,500, etc.) in the maps on both the transmitting and receiving sides. ) And the differences in the mapping rules of map creators. For example, if the road location data generated from Company A's 1Z2,500 map is to be located on Company B's 1Z2,500 map, the error between the WP and the candidate point on the `` true road '' may vary. If the road location data generated from the 1Z25,000 map of Company A is specified on the 1Z2,500 map of Company B, an error of several tens of meters will occur.

Therefore, on the receiving side, the state of the map data on the transmitting side (scale, map creation rules, etc.) The answer is that the search range of the candidate point in the position specification can be changed in accordance with.

 [0067] In general, the receiving side may or may not know the status of the map data on the transmitting side. However, when the road position data is divided to specify the position, the road position data of the section whose position has been successfully specified is determined. Learn the average error occurrence situation from the error situation between the data and the specific road, and adaptively set the candidate point search range in position identification in subsequent sections based on the learning result. Becomes possible.

 FIG. 13 schematically shows this pattern. As shown in Fig. 13 (a), for divided section 1 of the road position data, candidate points included in the candidate point search range of the default size determined in advance are searched, and the "true road" To identify. When the location of the divided section 1 is completed, as shown in Fig. 13 (b), the error distance between each node (node A and node B) on the "true road" and the WP is calculated, and the average 'Calculate the minimum error distance. For divided section 2 of the road position data, the candidate point search range is adjusted and optimized based on the average 'maximum' and minimum error distances in divided section 1 as shown in Fig. 13 (c).

 [0069] As described above, by estimating the error occurrence situation in the other part of the road position data from the error occurrence situation in a part of the road position data and setting the candidate point search range, "the map difference between transmission and reception is reduced. The smaller the value, the shorter the processing time for position identification, and the larger the value, the longer the processing time. "

 In FIG. 13, the candidate point search range is displayed as a rectangle. However, the same applies to the case where the candidate point search azimuth range indicating the angle range of the candidate point search is determined. The search range naturally includes the candidate point search direction range.

 FIG. 14 shows that the candidate point search range determination unit 16 estimates the error occurrence state in the other part of the road position data from the error occurrence state in one part of the road position data and adapts the candidate point search range. Show the processing flow when you set it! / Puru.

Reset the various parameters (such as WP force distance, _τ , _Ύ, etc.) related to the setting of the candidate point search range to the initial values (step 31), and focus on the first (Μ = 1) road position data ((step 32), the road position data Μ is divided (step 33), the first (Μη = Μ1) road position data block Μη is targeted (step 34), and the road position data of the block Μη is obtained (step 35). ), And specify the location (step 36), and determine whether the location was successful. Is determined (step 37). If an appropriate candidate point is not obtained and the position identification fails, change the parameters so that the search range is expanded (step 38) and repeat the position identification.

[0072] When the position is specified successfully (Yes in Step 37), the error between the road position data and the specified road is calculated (Step 39), and the parameters of the error situation are updated. (Step 40).

 [0073] For example, when the error of each WP (distance between the WP and the candidate point on the "true road") is Di, the distance of the WP force that defines the candidate point search range is set as follows. I do.

 • Set to P times the maximum error Dmax in Di.

 • Set the average of Di to Daverage + 2σ (a level at which 98% of the total parameters fall within the candidate point search range).

 • Set to Daverage + P-σ (Ρ is a constant that adjusts so that Ν% of the whole parameter is within the candidate point search range).

 [0074] For the road position data block following the road position data Μ, the processing of steps 35-40 is performed using the updated parameters, and such a procedure is performed for all the road position data blocks Μη of the road position data Μ. (Steps 41 and 42). When the processing for all the road position data blocks Μη of the road position data 終了 has been completed, the next and subsequent position specifying parameters are updated (step 43), and step 33— The processing of step 43 is performed, and such a procedure is repeated for all the road position data Μ (steps 44 and 45).

 [0075] According to such a procedure, a candidate point search range in another part of the road position data can be adaptively set based on an error occurrence state of a part of the road position data. In many cases, the occurrence of the distance error between maps depends on the road attributes such as whether the road is an expressway or a main line or a connecting road.Therefore, the parameter adjustment of the candidate point search range is performed in units of classification such as road attributes. It is also possible to do it.

 Further, since the occurrence of the angle error between the maps greatly changes depending on the magnitude of the declination, the classification of the declination absolute value of the road position data (within 10 °, 10−45 °, 45 ° or more, etc.) It is also conceivable to adjust the parameters of the candidate point search range for each unit.

In each embodiment, the case where the road position data is specified is described. The position identification method of the present invention is also used for position identification to associate linear objects on a digital map using position data of linear objects such as railways, waterways, contour lines, administrative boundaries, etc., which are not only roads. Applicable.

 [0078] The information processing device 10 receives traffic information and road position data of the target road from the information providing device, and performs position identification to identify the target road, a car navigation device, a PC, a PDA, and a mobile phone. Or a probe information collection center (Information Terminal) that receives the information on the in-vehicle capability of the probe car (traffic information) and the road position data indicating the travel trajectory and identifies the travel trajectory by performing position identification. Collection and distribution center).

 [0079] The present invention also includes a program for causing a computer to execute the above-described position specifying method. Such a program is incorporated into the information processing device 10 in various formats. For example, the program can be recorded in a predetermined memory in the information processing device 10 or in a device outside these devices. Further, the program may be recorded on an information recording device such as a hard disk, or an information recording medium such as a CD-ROM, a DVD-ROM, or a memory card. Alternatively, the program may be downloaded via a network.

 Although the present invention has been described in detail and with reference to specific embodiments, it will be apparent to those skilled in the art that various changes and modifications can be made without departing from the spirit and scope of the invention. is there.

 [0081] The present application is based on a Japanese patent application filed on November 19, 2003 (Japanese Patent Application No. 2003-389006), the contents of which are incorporated herein by reference.

 Industrial applicability

[0082] The position specifying method of the present invention can be used in all fields that require memory saving and high-speed processing when specifying a position. For example, a traffic information providing system, a probe information collecting system, a railway system, and the like. Canal 'Contours · It can be widely used in systems that provide map data such as administrative boundaries.

 Further, the device of the present invention can be used to identify a location such as a car navigation device that receives and reproduces traffic information, an information terminal such as a PC, a PDA, or a mobile phone, or a probe information collection center that collects probe car information. Can be applied to many devices that implement

Claims

The scope of the claims  [1] receiving position data of nodes arranged on a linear object on the digital map;  Editing and processing the received position data on the receiving side;  Associating the linear object with map data of the digital map on the receiving side after the editing and processing step.  [2] The location specifying method according to claim 1, wherein  A position specifying method, wherein the position data is divided into a plurality of blocks, and the associating step is performed in units of the blocks. [3] The location specifying method according to claim 2, wherein  A position specifying method for generating the block by cutting the position data at a fixed distance. [4] The location specifying method according to claim 3, wherein  A position specifying method for setting the fixed distance to be equal to or less than the length of one side of the minimum unit of the map data.  [5] The location specifying method according to claim 4, wherein  A position specifying method in which, when the linear target has a road shape, a cut portion at a certain distance matches a change point of a road type. [6] The location specifying method according to claim 2, wherein  A position specifying method of generating the block by cutting the position data in units of one side of a unit of the map data that displays the linear object. [7] The location specifying method according to claim 6, wherein  A position specifying method for aligning a cut portion of the position data with a boundary of the unit. [8] The location specifying method according to claim 2, wherein  A position specifying method for generating the block by cutting the position data at a fixed number of nodes.  [9] The location specifying method according to claim 2, wherein When the linear object has the road shape of the target road of traffic information, the position data is cut in accordance with the division unit of the traffic information to generate the block. Method.  [10] The location specifying method according to claim 1, wherein  A map matching method for thinning out nodes that do not cause erroneous identification and performing the associating step using the position data with the nodes thinned out.  [11] The location specifying method according to claim 10, wherein  A position specifying method for selecting the node to be thinned in consideration of a distance and an argument between the node and an adjacent node, and a density of the linear object around the node.  [12] receiving position data of nodes arranged on a linear object on the digital map;  A step of adaptively setting an angle range for searching for a candidate point of the node from a position of the map data corresponding to the position information of the node in accordance with a degree of bending of the linear object;  Associating the linear object with map data of a digital map on a receiving side. [13] The position specifying method according to claim 12, wherein  A position specifying method for setting the angle range in consideration of a degree of bending of the linear object in a predetermined distance section before and after or in front of the node and a density of the linear object in the predetermined distance section. [14] receiving position data of nodes arranged on a linear object on the digital map;  Associating the linear object with map data of a digital map on a receiving side; and referring to a result of the association of the portion where the associating step has been completed among the linear objects, the remaining portion of the linear object is referred to. Adaptively changing parameters used in the associating step. [15] The location specifying method according to claim 14, wherein A position specifying method for adaptively changing, as the parameter, an angle range for searching for a candidate point of the node. [16] The location specifying method according to claim 15, wherein  A position specifying method for adaptively changing, as the parameter, a size of a search range of the node candidate point. [17] A position data acquisition unit for acquiring position data of nodes arranged on a linear object on the digital map,  A position data cutting unit that divides the position data into a plurality of blocks,  A node thinning-out processing unit for thinning out nodes that do not cause erroneous identification from the block, and a search range for searching for candidate points of nodes included in the block are adaptively set, and map data of the digital map of the self is used. A candidate point search range determining unit that sets a candidate point of the node included in the search range above;  A position specifying processing unit that specifies a shape corresponding to the linear object on the map data based on the set candidate points;  An information processing device comprising: [18] A procedure for receiving position data of nodes arranged on a linear object on the digital map, a procedure for editing and processing the received position data on a receiving side,  After the editing and processing step, a step of associating the linear object with map data of the digital map on the receiving side. [19] A procedure for receiving position data of a node arranged on a linear object on a digital map, and an angle range for searching for a candidate point of the node from a position of the map data corresponding to the position information of the node, A procedure for adaptively setting according to the degree of bending of the linear object,  Associating the linear object with map data of a digital map on a receiving side. [20] a step of receiving position data of nodes arranged on a linear object of the digital map, a step of associating the linear object with map data of a digital map on a receiving side, and A procedure for adaptively changing a parameter used in the step of associating the remaining portion of the linear object with reference to the result of the association of the portion where the associating step has been completed.